mlsanityData to 7 Oct 2026

GraphArena: Evaluating and Exploring Large Language Models on Graph Computation

arXiv 2407.00379 ↗First posted 29 Jun 2024cs.AI cs.CLcited by 48

Not on the map. Why?

Abstract (arXiv)

The ``arms race'' of Large Language Models (LLMs) demands new benchmarks to examine their progresses. In this paper, we introduce GraphArena, a benchmarking tool designed to evaluate LLMs on real-world graph computational problems. It offers a suite of four polynomial-time tasks (e.g., Shortest Distance) and six NP-complete challenges (e.g., Traveling Salesman Problem). GraphArena features a rigorous evaluation framework that classifies LLM outputs as correct, suboptimal (feasible but not optimal), hallucinatory (properly formatted but infeasible), or missing. Evaluation of over 10 LLMs reveals that even top-performing LLMs struggle with larger, more complex graph problems and exhibit hallucination issues. We further explore four potential solutions to address this issue and improve LLMs on graph computation, including chain-of-thought prompting, instruction tuning, code writing, and scaling test-time compute, each demonstrating unique strengths and limitations. GraphArena complements the existing LLM benchmarks and is open-sourced at https://github.com/squareRoot3/GraphArena.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). Builds on 68 of its 92 references that are in the map. First posted on arXiv 29 Jun 2024.

Builds on

68 of 92 references.

References · 68

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  3. 2017Graph Attention Networkscited by 8,854
  4. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  5. 2020Measuring Massive Multitask Language Understandingcited by 7,768
  6. 2017Inductive Representation Learning on Large Graphscited by 6,284
  7. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  8. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  9. 2018How Powerful are Graph Neural Networks?cited by 4,355
  10. 2016SQuAD: 100,000+ Questions for Machine Comprehension of Textcited by 4,115
  11. 2023Qwen Technical Reportcited by 3,273
  12. 2022Survey of Hallucination in Natural Language Generationcited by 2,056
38 more
  1. 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,970
  2. 2024Mixtral of Expertscited by 1,785
  3. 2023MathVista: Evaluating Mathematical Reasoning of Foundation Models in Visual Contextscited by 1,582
  4. 2023LLaVA-Med: Training a Large Language-and-Vision Assistant for Biomedicine in One Daycited by 1,287
  5. 2023A Survey on Evaluation of Large Language Modelscited by 1,227
  6. 2024Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preferencecited by 1,151
  7. 2022When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memoriescited by 1,103
  8. 2024ChatGLM: A Family of Large Language Models from GLM-130B to GLM-4 All Toolscited by 1,096
  9. 2015A Diversity-Promoting Objective Function for Neural Conversation Modelscited by 1,068
  10. 2023A Multitask, Multilingual, Multimodal Evaluation of ChatGPT on Reasoning, Hallucination, and Interactivitycited by 888
  11. 2018Personalizing Dialogue Agents: I have a dog, do you have pets too?cited by 820
  12. 2023Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Modelscited by 695
  13. 2017DailyDialog: A Manually Labelled Multi-turn Dialogue Datasetcited by 649
  14. 2024DeepSeek LLM: Scaling Open-Source Language Models with Longtermismcited by 621
  15. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  16. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  17. 2022Large Language Models Struggle to Learn Long-Tail Knowledgecited by 452
  18. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 328
  19. 2024DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligencecited by 325
  20. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  21. 2023ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solvingcited by 276
  22. 2023ToolQA: A Dataset for LLM Question Answering with External Toolscited by 273
  23. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  24. 2023Specializing Smaller Language Models towards Multi-Step Reasoningcited by 249
  25. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 249
  26. 2023One for All: Towards Training One Graph Model for All Classification Taskscited by 239
  27. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  28. 2024DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Datacited by 225
  29. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  30. 2023Progressive-Hint Prompting Improves Reasoning in Large Language Modelscited by 147
  31. 2023Can ChatGPT Forecast Stock Price Movements? Return Predictability and Large Language Modelscited by 125
  32. 2019Neural Execution of Graph Algorithmscited by 118
  33. 2023Table Meets LLM: Can Large Language Models Understand Structured Table Data? A Benchmark and Empirical Studycited by 116
  34. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 112
  35. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Modelcited by 105
  36. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  37. 2024Benchmarking Benchmark Leakage in Large Language Modelscited by 102
  38. 2021Neural Algorithmic Reasoningcited by 92

50 most cited of 68 All 68 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 27; 2026: 20.

48 papers.

Sort:

By area:

  1. 2025Why Language Models Hallucinatecited by 205
  2. 2025A Survey of Context Engineering for Large Language Modelscited by 120
  3. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimizationcited by 28
  4. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 27
  5. 2025AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?cited by 24
  6. 2025Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunitiescited by 23
  7. 2025HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimizationcited by 19
  8. 2024Benchmarking and Improving Large Vision-Language Models for Fundamental Visual Graph Understanding and Reasoningcited by 17
  9. 2026Graph is a Substrate Across Data Modalitiescited by 13
  10. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimizationcited by 10
  11. 2025GraphThought: Graph Combinatorial Optimization with Thought Generationcited by 9
  12. 2025GraphCogent: Mitigating LLMs' Working Memory Constraints via Multi-Agent Collaboration in Complex Graph Understandingcited by 9
36 more
  1. 2025A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solvingcited by 9
  2. 2025KG-LLM-Bench: A Scalable Benchmark for Evaluating LLM Reasoning on Textualized Knowledge Graphscited by 6
  3. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoningcited by 6
  4. 2025Lost in Serialization: Invariance and Generalization of LLM Graph Reasonerscited by 6
  5. 2025How does Misinformation Affect Large Language Model Behaviors and Preferences?cited by 5
  6. 2025NPG-Muse: Scaling Long Chain-of-Thought Reasoning with NP-Hard Graph Problemscited by 5
  7. 2026OPT-Engine: Benchmarking the Limits of LLMs in Optimization Modeling via Complexity Scalingcited by 5
  8. 2025Large Language Models in Operations Research: Methods, Applications, and Challengescited by 4
  9. 2025Actions Speak Louder than Prompts: A Large-Scale Study of LLMs for Graph Inferencecited by 4
  10. 2025LLMTM: Benchmarking and Optimizing LLMs for Temporal Motif Analysis in Dynamic Graphscited by 4
  11. 2026DynamicGTR: Leveraging Graph Topology Representation Preferences to Boost VLM Capabilities on Graph QAscited by 4
  12. 2026New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Searchcited by 4
  13. 2026FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimizationcited by 4
  14. 2025Large Language Models for Cryptocurrency Transaction Analysis: A Bitcoin Case Studycited by 3
  15. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  16. 2025Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignmentcited by 3
  17. 2025From Sequence to Structure: Uncovering Substructure Reasoning in Transformerscited by 3
  18. 2026Do LLMs Build Spatial World Models? Evidence from Grid-World Maze Taskscited by 2
  19. 2026Evaluating Relational Reasoning in LLMs with RELcited by 2
  20. 2025Improving LLMs' Generalized Reasoning Abilities by Graph Problemscited by 1
  21. 2025Harnessing Adaptive Topology Representations for Zero-Shot Graph Question Answeringcited by 1
  22. 2025PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimizationcited by 0
  23. 2025Efficiently Learning Branching Networks for Multitask Algorithmic Reasoningcited by 0
  24. 2026MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMscited by 0
  25. 2026A Unified Graph Language Model for Multi-Domain Multi-Task Graph Alignment Instruction Tuningcited by 0
  26. 2026XLGoBench: Detecting cross-lingual skill gaps with algorithmic taskscited by 0
  27. 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospectscited by 0
  28. 2026GraphInfer-Bench: Benchmarking LLM's Inference Capability on Graphscited by 0
  29. 2026AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaborationcited by 0
  30. 2026The Generalization Spectrum: A Chromatographic Approach to Evaluating Learning Algorithmscited by 0
  31. 2026OmniRouting: A Semantic-Coupled Multimodal Benchmark for Constraint-Aware Spatial Reasoning in PCB Routingcited by 0
  32. 2026GraphWake: Group Polarization via Memory-Mediated Polarization Cascade in LLM-Agent Communitiescited by 0
  33. 2026ClosureBench: A Constructive Benchmark for Compositional Graph Reasoningcited by 0
  34. 2026Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMscited by 0
  35. 2026GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMscited by 0
  36. 2026PetriBench: Benchmarking LLM Reasoning over Dynamic State Spacescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation
  2. 2025GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks
  3. 2024Are Large-Language Models Graph Algorithmic Reasoners?
  4. 2024Graph Reasoning with Large Language Models via Pseudo-code Prompting
  5. 2026Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
  6. 2024GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets
  7. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path
  8. 2024Can LLMs perform structured graph reasoning?