mlsanityData to 7 Oct 2026

Can Language Models Solve Graph Problems in Natural Language?

arXiv 2305.10037 ↗First posted 17 May 2023cs.CL cs.AIcited by 249

On the map: LLM reasoning → Knowledge- and tool-augmented reasoning

Abstract (arXiv)

Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures, such as planning in robotics, multi-hop question answering or knowledge probing, structured commonsense reasoning, and more. While LLMs have advanced the state-of-the-art on these tasks with structure implications, whether LLMs could explicitly process textual descriptions of graphs and structures, map them to grounded conceptual spaces, and perform structured operations remains underexplored. To this end, we propose NLGraph (Natural Language Graph), a comprehensive benchmark of graph-based problem solving designed in natural language. NLGraph contains 29,370 problems, covering eight graph reasoning tasks with varying complexity from simple tasks such as connectivity and shortest path up to complex problems such as maximum flow and simulating graph neural networks. We evaluate LLMs (GPT-3/4) with various prompting approaches on the NLGraph benchmark and find that 1) language models do demonstrate preliminary graph reasoning abilities, 2) the benefit of advanced prompting and in-context learning diminishes on more complex graph problems, while 3) LLMs are also (un)surprisingly brittle in the face of spurious correlations in graph and problem settings. We then propose Build-a-Graph Prompting and Algorithmic Prompting, two instruction-based approaches to enhance LLMs in solving natural language graph problems. Build-a-Graph and Algorithmic prompting improve the performance of LLMs on NLGraph by 3.07% to 16.85% across multiple tasks and settings, while how to solve the most complicated graph reasoning tasks in our setup with language models remains an open research question. The NLGraph benchmark and evaluation code are available at https://github.com/Arthur-Heng/NLGraph.

Key facts. Cited by 249 papers in the map (data through 7 Oct 2026). Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning. Builds on 34 of its 40 references that are in the map. First posted on arXiv 17 May 2023.

Builds on

34 of 40 references.

Closest ancestors · 1

Same direction, newest first

  1. 2022GreaseLM: Graph REASoning Enhanced Language Models for Question Answering21 Jan

Other references · 33

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  5. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  7. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  8. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  9. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  10. 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,970
  11. 2018CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledgecited by 1,793
  12. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
21 more
  1. 2022Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agentscited by 1,029
  2. 2021Are NLP Models really able to Solve Simple Math Word Problems?cited by 861
  3. 2023Large Language Models Can Be Easily Distracted by Irrelevant Contextcited by 820
  4. 2021Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategiescited by 736
  5. 2017Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problemscited by 642
  6. 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoningcited by 331
  7. 2022Language Models of Code are Few-Shot Commonsense Learnerscited by 160
  8. 2022Language Models as Agent Modelscited by 131
  9. 2023Solving Math Word Problems by Combining Language Models With Symbolic Solverscited by 124
  10. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 111
  11. 2021NaturalProofs: Mathematical Theorem Proving in Natural Languagecited by 80
  12. 2022NaturalProver: Grounded Mathematical Proof Generation with Language Modelscited by 72
  13. 2019WIQA: A dataset for "What if..." reasoning over procedural textcited by 71
  14. 2022CREPE: Open-Domain Question Answering with False Presuppositionscited by 70
  15. 2022Recitation-Augmented Language Modelscited by 65
  16. 2021ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoningcited by 58
  17. 2020Learning Dynamic Belief Graphs to Generalize on Text-Based Gamescited by 49
  18. 2023Code Execution with Pre-trained Language Modelscited by 33
  19. 2021Learning Knowledge Graph-based World Models of Textual Environmentscited by 31
  20. 2021Could you give me a hint? Generating inference graphs for defeasible reasoningcited by 10
  21. 2021An Empirical Study on Few-shot Knowledge Probing for Pretrained Language Modelscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 26; 2024: 83; 2025: 86; 2026: 54.

249 papers.

Sort:

By area:

  1. 2024Graph Retrieval-Augmented Generation: A Surveycited by 320
  2. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  3. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  4. 2023One for All: Towards Training One Graph Model for All Classification Taskscited by 239
  5. 2023Language is All a Graph Needscited by 219
  6. 2024G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answeringcited by 217
  7. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 190
  8. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  9. 2023Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learningcited by 132
  10. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 112
  11. 2023GraphText: Graph Reasoning in Text Spacecited by 110
  12. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Modelcited by 105
38 more
  1. 2023Graph Foundation Models: Concepts, Opportunities and Challengescited by 101
  2. 2023A Survey of Graph Meets Large Language Model: Progress and Future Directionscited by 84
  3. 2024Position: Graph Foundation Models are Already Herecited by 84
  4. 2024ZeroG: Investigating Cross-dataset Zero-shot Transferability in Graphscited by 83
  5. 2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 82
  6. 2024GRAG: Graph Retrieval-Augmented Generationcited by 77
  7. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  8. 2023Label-free Node Classification on Graphs with Large Language Models (LLMS)cited by 72
  9. 2024A Survey of Large Language Models for Graphscited by 71
  10. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  11. 2024Demystifying Chains, Trees, and Graphs of Thoughtscited by 63
  12. 2024GraphTranslator: Aligning Graph Model to Large Language Model for Open-ended Taskscited by 63
  13. 2024UniGraph: Learning a Unified Cross-Domain Foundation Model for Text-Attributed Graphscited by 60
  14. 2024LLMs as Zero-shot Graph Learners: Alignment of GNN Representations with LLM Token Embeddingscited by 60
  15. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capabilitycited by 57
  16. 2024InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignmentcited by 56
  17. 2024KG-RAG: Bridging the Gap Between Knowledge and Creativitycited by 55
  18. 2023Algorithm Evolution Using Large Language Modelcited by 52
  19. 2023Resolving Knowledge Conflicts in Large Language Modelscited by 49
  20. 2023Making Large Language Models Perform Better in Knowledge Graph Completioncited by 48
  21. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 48
  22. 2025UniGraph2: Learning a Unified Embedding Space to Bind Multimodal Graphscited by 47
  23. 2024Can LLM Graph Reasoning Generalize beyond Pattern Memorization?cited by 46
  24. 2023Amazon-M2: A Multilingual Multi-locale Shopping Session Dataset for Recommendation and Text Generationcited by 42
  25. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 42
  26. 2023LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?cited by 40
  27. 2023Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Modelscited by 37
  28. 2024Graph-enhanced Large Language Models in Asynchronous Plan Reasoningcited by 37
  29. 2023Disentangled Representation Learning with Large Language Models for Text-Attributed Graphscited by 36
  30. 2023Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysiscited by 35
  31. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  32. 2024TokenRec: Learning to Tokenize ID for LLM-based Generative Recommendationcited by 35
  33. 2024Graph Machine Learning in the Era of Large Language Models (LLMs)cited by 33
  34. 2024GraphWiz: An Instruction-Following Language Model for Graph Problemscited by 32
  35. 2023Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?cited by 31
  36. 2024GITA: Graph to Visual and Textual Integration for Vision-Language Graph Reasoningcited by 31
  37. 2024LLMs generate structurally realistic social networks but overestimate political homophilycited by 31
  38. 2024How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehensioncited by 30

50 most cited of 249 All 249 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024Graph Reasoning with Large Language Models via Pseudo-code Prompting
  2. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoning
  3. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path
  4. 2025Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation
  5. 2025GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks
  6. 2025Less is More: Learning Graph Tasks with Just LLMs
  7. 2026Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models
  8. 2026GraphDancer: Training LLMs to Explore and Reason over Graphs via Two-Stage Curriculum Post-Training