mlsanityData to 7 Oct 2026

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

arXiv 2609.12265 ↗First posted 10 Sep 2026cs.AIcited by 0

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

also in 1 more
Abstract (arXiv)

Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: https://github.com/xzx34/GTA. The project homepage is available at https://xzx34.github.io/gta/.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning. Builds on 125 of its 139 references that are in the map. First posted on arXiv 10 Sep 2026.

Builds on

125 of 139 references.

Closest ancestors · 19

Same direction, newest first

  1. 2025LLM-Powered Text-Attributed Graph Anomaly Detection via Retrieval-Augmented Reasoning16 Nov
  2. 2025Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners13 Nov
  3. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoning29 Sep
  4. 2025A Fano-Style Accuracy Upper Bound for LLM Single-Pass Reasoning in Multi-Hop QA25 Sep
  5. 2025Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignment1 Jun
  6. 2025G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning24 May
  7. 2025GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks17 Apr
  8. 2025KG-LLM-Bench: A Scalable Benchmark for Evaluating LLM Reasoning on Textualized Knowledge Graphs9 Apr
  9. 2024GraphTool-Instruction: Revolutionizing Graph Reasoning in LLMs through Decomposed Subtask Instruction11 Dec
  10. 2024Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents7 Oct
  11. 2024GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models3 Jul
  12. 2024GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets23 Jun
7 more
  1. 2024Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs10 Apr
  2. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability7 Mar
  3. 2024Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?11 Feb
  4. 2023Graph Agent: Explicit Reasoning Agent for Graphs25 Oct
  5. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Model9 Oct
  6. 2023Can Language Models Solve Graph Problems in Natural Language?17 May
  7. 2022NQE: N-ary Query Embedding for Complex Query Answering over Hyper-Relational Knowledge Graphs24 Nov

Other references · 106

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  5. 2024GPT-4o System Cardcited by 4,467
  6. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  7. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
  8. 2023Improving Factuality and Reasoning in Language Models through Multiagent Debatecited by 1,739
  9. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  10. 2023HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Facecited by 1,173
  11. 2023Quantifying Language Models' Sensitivity to Spurious Features in Prompt Design or: How I learned to start worrying about prompt formattingcited by 778
  12. 2022Decomposed Prompting: A Modular Approach for Solving Complex Taskscited by 554
38 more
  1. 2023Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Modelscited by 550
  2. 2024Automated Design of Agentic Systemscited by 360
  3. 2024Justice or Prejudice? Quantifying Biases in LLM-as-a-Judgecited by 354
  4. 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 309
  5. 2024G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answeringcited by 217
  6. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 209
  7. 2023MetaTool Benchmark for Large Language Models: Deciding Whether to Use Tools and Which to Usecited by 209
  8. 2021Large-Scale Chemical Language Representations Capture Molecular Structure and Propertiescited by 203
  9. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  10. 2025Multi-agent Architecture Search via Agentic Supernetcited by 164
  11. 2023DeID-GPT: Zero-shot Medical Text De-Identification by GPT-4cited by 128
  12. 2024Optimization-based Prompt Injection Attack to LLM-as-a-Judgecited by 123
  13. 2025Preference Leakage: A Contamination Problem in LLM-as-a-judgecited by 119
  14. 2023Opportunities and Challenges for ChatGPT and Large Language Models in Biomedicine and Healthcited by 118
  15. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 112
  16. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  17. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 48
  18. 2024HiGPT: Heterogeneous Graph Language Modelcited by 44
  19. 2023LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?cited by 40
  20. 2024Decoding Echo Chambers: LLM-Powered Simulations Revealing Polarization in Social Networkscited by 31
  21. 2025AgentsNet: Coordination and Collaborative Reasoning in Multi-Agent LLMscited by 31
  22. 2024VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Contextcited by 29
  23. 2026SkillGen: Verified Inference-Time Agent Skill Synthesiscited by 29
  24. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 27
  25. 2026Large-Scale Terminal Agentic Trajectory Generation from Dockerized Environmentscited by 27
  26. 2024AD-LLM: Benchmarking Large Language Models for Anomaly Detectioncited by 25
  27. 2024DataGen: Unified Synthetic Dataset Generation via Large Language Modelscited by 22
  28. 2025DyFlow: Dynamic Workflow Framework for Agentic Reasoningcited by 22
  29. 2024Hazards in Daily Life? Enabling Robots to Proactively Detect and Resolve Anomaliescited by 19
  30. 2024Transformers Struggle to Learn to Searchcited by 19
  31. 2024Graph Neural Network Explanations are Fragilecited by 18
  32. 2025Learning to Deliberate: Meta-policy Collaboration for Agentic LLMs with Multi-agent Reinforcement Learningcited by 18
  33. 2024Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Modelscited by 17
  34. 2025Dissecting Logical Reasoning in LLMs: A Fine-Grained Evaluation and Supervision Studycited by 17
  35. 2024MetaOOD: Automatic Selection of OOD Detection Modelscited by 16
  36. 2025AdaReasoner: Adaptive Reasoning Enables More Flexible Thinking in Large Language Modelscited by 16
  37. 2026Auditing Multi-Agent LLM Reasoning Trees Outperforms Majority Vote and LLM-as-Judgecited by 16
  38. 2025Beyond Prompt Content: Enhancing LLM Performance via Content-Format Integrated Prompt Optimizationcited by 15

50 most cited of 106 All 106 (JSON)

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospects
  2. 2026Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models
  3. 2026GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning
  4. 2025GDS Agent for Graph Algorithmic Reasoning
  5. 2024Can LLM Graph Reasoning Generalize beyond Pattern Memorization?
  6. 2023Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis
  7. 2024Are Large-Language Models Graph Algorithmic Reasoners?
  8. 2025MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications