# Rethinking and Benchmarking Large Language Models for Graph Reasoning

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

## Key facts

- Cited by 6 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 11 of its 31 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Placed in

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

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

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents](https://mlsanity.com/paper/2410.05130/) (2024)
- [Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models](https://mlsanity.com/paper/2409.19667/) (2024)
- [GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration](https://mlsanity.com/paper/2410.18032/) (2024)
- [GCoder: Improving Large Language Model for Generalized Graph Problem Solving](https://mlsanity.com/paper/2410.19084/) (2024)

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

- [Graph is a Substrate Across Data Modalities](https://mlsanity.com/paper/2601.22384/) (2026)
- [TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference](https://mlsanity.com/paper/2510.08808/) (2025)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)
- [Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models](https://mlsanity.com/paper/2608.12391/) (2026)
- [ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning](https://mlsanity.com/paper/2608.18242/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) for Graph Reasoning have been extensively studied over the past two years, involving enabling LLMs to understand graph structures and reason on graphs to solve various graph problems, with graph algorithm problems being the most prevalent. Recent studies underscore the potential of LLMs in handling graph reasoning tasks, but their performance is underwhelming. In this work, we point out issues with existing methods and benchmarks, and rethink the direction that LLMs for graph reasoning should strive toward. We find that base models, e.g., GPT-4o-mini, are largely underestimated due to improper reasoning focus. Base models with reasoning focus redirected from replicating graph algorithms to designing them can easily solve most graph reasoning tasks in existing benchmarks. To truly evaluate the graph reasoning capabilities of LLMs, we construct a more challenging GraphAlgorithm benchmark, comprising 239 different graph problems and 3,041 test instances collected from 4 competition platforms. Finally, we introduce a simple and strong baseline Simple-Reasoning-Then-Coding (Simple-RTC)-which guides LLMs to design graph algorithms first and then code to address graph reasoning tasks. Simple-RTC achieves near-perfect accuracy on existing benchmarks and significantly outperforms GPT-4o-mini and all prior methods on the GraphAlgorithm benchmark. This strong baseline encourages further advancements in LLMs for Graph Reasoning in the future.