# Can Language Models Solve Graph Problems in Natural Language?

arXiv: https://arxiv.org/abs/2305.10037 · HTML: https://mlsanity.com/paper/2305.10037/

## Key facts

- Cited by 252 papers in the map (data through 14 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.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 30 of 34)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [Large Language Models Can Be Easily Distracted by Irrelevant Context](https://mlsanity.com/paper/2302.00093/) (2023)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [GreaseLM: Graph REASoning Enhanced Language Models for Question Answering](https://mlsanity.com/paper/2201.08860/) (2022)
- [Language Models of Code are Few-Shot Commonsense Learners](https://mlsanity.com/paper/2210.07128/) (2022)
- [Language Models as Agent Models](https://mlsanity.com/paper/2212.01681/) (2022)
- [Solving Math Word Problems by Combining Language Models With Symbolic Solvers](https://mlsanity.com/paper/2304.09102/) (2023)
- [Teaching Algorithmic Reasoning via In-context Learning](https://mlsanity.com/paper/2211.09066/) (2022)
- [NaturalProofs: Mathematical Theorem Proving in Natural Language](https://mlsanity.com/paper/2104.01112/) (2021)
- [NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://mlsanity.com/paper/2205.12910/) (2022)
- [CREPE: Open-Domain Question Answering with False Presuppositions](https://mlsanity.com/paper/2211.17257/) (2022)
- [WIQA: A dataset for "What if..." reasoning over procedural text](https://mlsanity.com/paper/1909.04739/) (2019)
- [Recitation-Augmented Language Models](https://mlsanity.com/paper/2210.01296/) (2022)
- [ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning](https://mlsanity.com/paper/2104.07644/) (2021)
- [Learning Dynamic Belief Graphs to Generalize on Text-Based Games](https://mlsanity.com/paper/2002.09127/) (2020)

## Built on by (most cited first, 30 of 252)

- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [One for All: Towards Training One Graph Model for All Classification Tasks](https://mlsanity.com/paper/2310.00149/) (2023)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning](https://mlsanity.com/paper/2305.19523/) (2023)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Graph Foundation Models: Concepts, Opportunities and Challenges](https://mlsanity.com/paper/2310.11829/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [A Survey of Graph Meets Large Language Model: Progress and Future Directions](https://mlsanity.com/paper/2311.12399/) (2023)
- [ZeroG: Investigating Cross-dataset Zero-shot Transferability in Graphs](https://mlsanity.com/paper/2402.11235/) (2024)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [GRAG: Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2405.16506/) (2024)
- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [Label-free Node Classification on Graphs with Large Language Models (LLMS)](https://mlsanity.com/paper/2310.04668/) (2023)
- [A Survey of Large Language Models for Graphs](https://mlsanity.com/paper/2405.08011/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [UniGraph: Learning a Unified Cross-Domain Foundation Model for Text-Attributed Graphs](https://mlsanity.com/paper/2402.13630/) (2024)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [GraphTranslator: Aligning Graph Model to Large Language Model for Open-ended Tasks](https://mlsanity.com/paper/2402.07197/) (2024)
- [LLMs as Zero-shot Graph Learners: Alignment of GNN Representations with LLM Token Embeddings](https://mlsanity.com/paper/2408.14512/) (2024)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment](https://mlsanity.com/paper/2402.08785/) (2024)
- [KG-RAG: Bridging the Gap Between Knowledge and Creativity](https://mlsanity.com/paper/2405.12035/) (2024)
- [Algorithm Evolution Using Large Language Model](https://mlsanity.com/paper/2311.15249/) (2023)

## 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.