# Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 16 of its 68 references that are in the map.
- First posted on arXiv 2 Aug 2026.

## Placed in

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

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [DeepSeek-V3 Technical Report](https://mlsanity.com/paper/2412.19437/) (2024)
- [DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligence](https://mlsanity.com/paper/2406.11931/) (2024)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Benchmarking Benchmark Leakage in Large Language Models](https://mlsanity.com/paper/2404.18824/) (2024)
- [NVIDIA Nemotron 3: Efficient and Open Intelligence](https://mlsanity.com/paper/2512.20856/) (2025)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration](https://mlsanity.com/paper/2410.18032/) (2024)
- [CodeGraph: Enhancing Graph Reasoning of LLMs with Code](https://mlsanity.com/paper/2408.13863/) (2024)
- [Rethinking and Benchmarking Large Language Models for Graph Reasoning](https://mlsanity.com/paper/2509.24260/) (2025)
- [Pseudocode-Injection Magic: Enabling LLMs to Tackle Graph Computational Tasks](https://mlsanity.com/paper/2501.13731/) (2025)
- [GraphSkill: Documentation-Guided Hierarchical Retrieval-Augmented Coding for Complex Graph Reasoning](https://mlsanity.com/paper/2603.06620/) (2026)

## Abstract (arXiv)

Graph reasoning provides a promising testbed for evaluating the reasoning ability of large language models (LLMs), as graph instances can be programmatically generated, structurally controlled, and naturally scaled to long-input settings. However, existing graph reasoning benchmarks have limited coverage of data complexity, rely heavily on manual construction, and lack unified evaluation across text-based and code-based reasoning modes. To address these limitations, we propose dataset, a five-stage textitsemi-automatic framework for constructing complex graph reasoning benchmarks. It expands benchmark coverage along five dimensions: textitGraph Size, textitTask Complexity, textitTask Description, textitGraph Loading, and textitTask Source. The framework uses an LLM-based data generator to automatically produce task descriptions, graph data, reference solutions, graph-loading scripts, question forms, and evaluation scripts, while retaining human validation at key quality-control stages. Based on it, we construct a benchmark with 202 tasks and evaluate LLMs under text-based, code-based, and augmented reasoning settings. Experiments show that the complexity dimensions reveal model limitations that are less visible in existing benchmarks; existing fine-tuned models struggle to generalize to GraphGym, whereas retrieval-augmented methods show scenario-dependent adaptability, improving textual reasoning but not consistently improving coding reasoning. These findings suggest that ours serves as a challenging and diagnostic benchmark for graph reasoning and provides empirical guidance for future enhancement methods. Code and dataset will be published soon.