# Can LLMs perform structured graph reasoning?

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

## Key facts

- Cited by 9 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 21 of its 28 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Placed in

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

## Builds on (most cited first, 21 of 21)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [A Prompt Pattern Catalog to Enhance Prompt Engineering with ChatGPT](https://mlsanity.com/paper/2302.11382/) (2023)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [Reasoning with Language Model Prompting: A Survey](https://mlsanity.com/paper/2212.09597/) (2022)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [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)
- [Faithful Reasoning Using Large Language Models](https://mlsanity.com/paper/2208.14271/) (2022)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [ChatGPT is a Knowledgeable but Inexperienced Solver: An Investigation of Commonsense Problem in Large Language Models](https://mlsanity.com/paper/2303.16421/) (2023)
- [Learning Dynamic Belief Graphs to Generalize on Text-Based Games](https://mlsanity.com/paper/2002.09127/) (2020)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [Complex Logical Reasoning over Knowledge Graphs using Large Language Models](https://mlsanity.com/paper/2305.01157/) (2023)
- [A Comparative Study of Open-Source Large Language Models, GPT-4 and Claude 2: Multiple-Choice Test Taking in Nephrology](https://mlsanity.com/paper/2308.04709/) (2023)
- [Stochastic LLMs do not Understand Language: Towards Symbolic, Explainable and Ontologically Based LLMs](https://mlsanity.com/paper/2309.05918/) (2023)

## Built on by (most cited first, 9 of 9)

- [GraphOTTER: Evolving LLM-based Graph Reasoning for Complex Table Question Answering](https://mlsanity.com/paper/2412.01230/) (2024)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Autonomous Control Leveraging LLMs: An Agentic Framework for Next-Generation Industrial Automation](https://mlsanity.com/paper/2507.07115/) (2025)
- [MobilityBench: A Benchmark for Evaluating Route-Planning Agents in Real-World Mobility Scenarios](https://mlsanity.com/paper/2602.22638/) (2026)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Are Large-Language Models Graph Algorithmic Reasoners?](https://mlsanity.com/paper/2410.22597/) (2024)
- [Trace-of-Thought Prompting: Investigating Prompt-Based Knowledge Distillation Through Question Decomposition](https://mlsanity.com/paper/2504.20946/) (2025)
- [TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference](https://mlsanity.com/paper/2510.08808/) (2025)
- [Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism](https://mlsanity.com/paper/2606.09484/) (2026)

## Abstract (arXiv)

Pretrained Large Language Models (LLMs) have demonstrated various reasoning capabilities through language-based prompts alone, particularly in unstructured task settings (tasks purely based on language semantics). However, LLMs often struggle with structured tasks, because of the inherent incompatibility of input representation. Reducing structured tasks to uni-dimensional language semantics often renders the problem trivial. Keeping the trade-off between LLM compatibility and structure complexity in mind, we design various graph reasoning tasks as a proxy to semi-structured tasks in this paper, in order to test the ability to navigate through representations beyond plain text in various LLMs. Particularly, we design 10 distinct problems of graph traversal, each representing increasing levels of complexity, and benchmark 5 different instruct-finetuned LLMs (GPT-4, GPT-3.5, Claude-2, Llama-2 and Palm-2) on the aforementioned tasks. Further, we analyse the performance of models across various settings such as varying sizes of graphs as well as different forms of k-shot prompting. We highlight various limitations, biases and properties of LLMs through this benchmarking process, such as an inverse relation to the average degrees of freedom of traversal per node in graphs, the overall negative impact of k-shot prompting on graph reasoning tasks, and a positive response bias which prevents LLMs from identifying the absence of a valid solution. Finally, we introduce a new prompting technique specially designed for graph traversal tasks (PathCompare), which demonstrates a notable increase in the performance of LLMs in comparison to standard prompting techniques such as Chain-of-Thought (CoT).