# Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents

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

## Key facts

- Cited by 21 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 36 references that are in the map.
- First posted on arXiv 7 Oct 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

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

- [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)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [Self-collaboration Code Generation via ChatGPT](https://mlsanity.com/paper/2304.07590/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [AgentScope: A Flexible yet Robust Multi-Agent Platform](https://mlsanity.com/paper/2402.14034/) (2024)
- [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)
- [A Survey of Distributed Graph Algorithms on Massive Graphs](https://mlsanity.com/paper/2404.06037/) (2024)
- [Controlling Equational Reasoning in Large Language Models with Prompt Interventions](https://mlsanity.com/paper/2307.09998/) (2023)

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

- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [Maestro: Learning to Collaborate via Conditional Listwise Policy Optimization for Multi-Agent LLMs](https://mlsanity.com/paper/2511.06134/) (2025)
- [GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration](https://mlsanity.com/paper/2410.18032/) (2024)
- [Graph Learning in the Era of LLMs: A Survey from the Perspective of Data, Models, and Tasks](https://mlsanity.com/paper/2412.12456/) (2024)
- [The Five Ws of Multi-Agent Communication: Who Talks to Whom, When, What, and Why -- A Survey from MARL to Emergent Language and LLMs](https://mlsanity.com/paper/2602.11583/) (2026)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Rethinking and Benchmarking Large Language Models for Graph Reasoning](https://mlsanity.com/paper/2509.24260/) (2025)
- [Graph-Grounded LLMs: Leveraging Graphical Function Calling to Minimize LLM Hallucinations](https://mlsanity.com/paper/2503.10941/) (2025)
- [UserCentrix: An Agentic Memory-augmented AI Framework for Smart Spaces](https://mlsanity.com/paper/2505.00472/) (2025)
- [Brittleness and Promise: Knowledge Graph Based Reward Modeling for Diagnostic Reasoning](https://mlsanity.com/paper/2509.18316/) (2025)
- [MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications](https://mlsanity.com/paper/2502.18540/) (2025)
- [Exploring the Potential of Large Language Models as Predictors in Dynamic Text-Attributed Graphs](https://mlsanity.com/paper/2503.03258/) (2025)
- [LoopBench: Discovering Emergent Symmetry Breaking Strategies with LLM Swarms](https://mlsanity.com/paper/2512.13713/) (2025)
- [LLM-Guided Agentic Floor Plan Parsing for Accessible Indoor Navigation of Blind and Low-Vision People](https://mlsanity.com/paper/2604.23970/) (2026)
- [Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs](https://mlsanity.com/paper/2509.12743/) (2025)
- [GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning](https://mlsanity.com/paper/2605.06671/) (2026)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)
- [LLMs+Graphs: Toward Graph-Native, Synergistic AI Systems](https://mlsanity.com/paper/2606.11560/) (2026)
- [Towards Self-Evolving Agents: A Human-Inspired Adaptive Exploration-Exploitation Framework for Genetic Network Programming](https://mlsanity.com/paper/2607.11913/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

Recent research has explored the use of Large Language Models (LLMs) for tackling complex graph reasoning tasks. However, due to the intricacies of graph structures and the inherent limitations of LLMs in handling long text, current approaches often fail to deliver satisfactory accuracy, even on small-scale graphs and simple tasks. To address these challenges, we introduce GraphAgent-Reasoner, a fine-tuning-free framework that utilizes a multi-agent collaboration strategy for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. The agents collaborate to solve the overall problem, significantly reducing the amount of information and complexity handled by a single LLM, thus enhancing the accuracy of graph reasoning. By simply increasing the number of agents, GraphAgent-Reasoner can efficiently scale to accommodate larger graphs with over 1,000 nodes. Evaluated on the GraphInstruct dataset, our framework demonstrates near-perfect accuracy on polynomial-time graph reasoning tasks, significantly outperforming the best available models, both closed-source and fine-tuned open-source variants. Our framework also demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.