# Adaptive Graph Pruning for Multi-Agent Communication

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 37 of its 48 references that are in the map.
- First posted on arXiv 3 Jun 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 37)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [ChatEval: Towards Better LLM-based Evaluators through Multi-Agent Debate](https://mlsanity.com/paper/2308.07201/) (2023)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [AFlow: Automating Agentic Workflow Generation](https://mlsanity.com/paper/2410.10762/) (2024)
- [Automated Design of Agentic Systems](https://mlsanity.com/paper/2408.08435/) (2024)
- [Complexity-Based Prompting for Multi-Step Reasoning](https://mlsanity.com/paper/2210.00720/) (2022)
- [Solving General Arithmetic Word Problems](https://mlsanity.com/paper/1608.01413/) (2016)
- [Scaling Large Language Model-based Multi-Agent Collaboration](https://mlsanity.com/paper/2406.07155/) (2024)
- [Exploring Collaboration Mechanisms for LLM Agents: A Social Psychology View](https://mlsanity.com/paper/2310.02124/) (2023)
- [AutoAgents: A Framework for Automatic Agent Generation](https://mlsanity.com/paper/2309.17288/) (2023)
- [Multi-agent Architecture Search via Agentic Supernet](https://mlsanity.com/paper/2502.04180/) (2025)
- [AgentSquare: Automatic LLM Agent Search in Modular Design Space](https://mlsanity.com/paper/2410.06153/) (2024)
- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks](https://mlsanity.com/paper/2410.11782/) (2024)
- [EvoAgent: Towards Automatic Multi-Agent Generation via Evolutionary Algorithms](https://mlsanity.com/paper/2406.14228/) (2024)
- [Self-Organized Agents: A LLM Multi-Agent Framework toward Ultra Large-Scale Code Generation and Optimization](https://mlsanity.com/paper/2404.02183/) (2024)
- [Self-Evolving Multi-Agent Collaboration Networks for Software Development](https://mlsanity.com/paper/2410.16946/) (2024)
- [See and Think: Embodied Agent in Virtual Environment](https://mlsanity.com/paper/2311.15209/) (2023)

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

- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [From Static Templates to Dynamic Runtime Graphs: A Survey of Workflow Optimization for LLM Agents](https://mlsanity.com/paper/2603.22386/) (2026)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [Auditing Multi-Agent LLM Reasoning Trees Outperforms Majority Vote and LLM-as-Judge](https://mlsanity.com/paper/2602.09341/) (2026)
- [SafeSieve: From Heuristics to Experience in Progressive Pruning for LLM-based Multi-Agent Communication](https://mlsanity.com/paper/2508.11733/) (2025)
- [FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search](https://mlsanity.com/paper/2606.00765/) (2026)
- [Adaptive Collaboration with Humans: Metacognitive Policy Optimization for Multi-Agent LLMs with Continual Learning](https://mlsanity.com/paper/2603.07972/) (2026)
- [TodyComm: Task-Oriented Dynamic Communication for Multi-Round LLM-based Multi-Agent System](https://mlsanity.com/paper/2602.03688/) (2026)
- [Self-Improvement of Large Language Models: A Technical Overview and Future Outlook](https://mlsanity.com/paper/2603.25681/) (2026)
- [AgentBalance: Backbone-then-Topology Design for Cost-Effective Multi-Agent Systems under Budget Constraints](https://mlsanity.com/paper/2512.11426/) (2025)
- [Intern-S2-Preview: Scientific Agentic Foundation Model](https://mlsanity.com/paper/2608.13505/) (2026)
- [Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective](https://mlsanity.com/paper/2608.18104/) (2026)
- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [Orchestrator: Active Inference for Multi-Agent Systems in Long-Horizon Tasks](https://mlsanity.com/paper/2509.05651/) (2025)
- [HyperAgent: Leveraging Hypergraphs for Topology Optimization in Multi-Agent Communication](https://mlsanity.com/paper/2510.10611/) (2025)
- [Conjunctive Prompt Attacks in Multi-Agent LLM Systems](https://mlsanity.com/paper/2604.16543/) (2026)
- [Rethinking the Evaluation of Efficiency Methods for Multi-Agent Systems](https://mlsanity.com/paper/2609.05933/) (2026)
- [AgentSlimming: Towards Efficient and Cost-Aware Multi-Agent Systems](https://mlsanity.com/paper/2605.08813/) (2026)
- [Taming "Zombie'' Agents: A Markov State-Aware Framework for Resilient Multi-Agent Evolution](https://mlsanity.com/paper/2605.17348/) (2026)
- [From Cognitive Architectures to Language Agents: A Mechanism-Level Review of Lineage, Convergence, and Migration Gaps](https://mlsanity.com/paper/2607.23942/) (2026)
- [Discovering Efficient and Explainable Communication Topologies for LLM-based Multi-Agent Systems via Causal Inference](https://mlsanity.com/paper/2608.12921/) (2026)
- [MasFACT: Continual Multi-Agent Topology Learning via Geometry-Aware Posterior Transfer](https://mlsanity.com/paper/2605.17361/) (2026)
- [Roles with Rails: Contract-Preserving Role Evolution in Multi-Agent Structured Reasoning](https://mlsanity.com/paper/2605.28433/) (2026)
- [PEAR: Permutation-Equivariant Adaptive Routing Multi-Agent Debate](https://mlsanity.com/paper/2606.20621/) (2026)
- [ForestBench: A Unified Graph Framework for Evaluating Multi-Agent Collaboration](https://mlsanity.com/paper/2608.08605/) (2026)
- [Do We Need Complex Topology Control? Distinct-Peer Random Routing Improves Cost-Efficiency in Sparse Multi-Agent Debate](https://mlsanity.com/paper/2609.27150/) (2026)
- [Concealing LLM-Based Multi-Agent Topology via Phantom Structure Injection](https://mlsanity.com/paper/2609.37567/) (2026)
- [SHarP: Saliency-based Pruning of Agent Harnesses](https://mlsanity.com/paper/2610.04178/) (2026)

## Abstract (arXiv)

Large Language Model (LLM) based multi-agent systems have shown remarkable performance in various tasks, especially when enhanced through collaborative communication. However, current methods often rely on a fixed number of agents and static communication structures, limiting their ability to adapt to varying task complexities. In this paper, we propose Adaptive Graph Pruning (AGP), a novel task-adaptive multi-agent collaboration framework that jointly optimizes agent quantity (hard-pruning) and communication topology (soft-pruning). Specifically, our method employs a two-stage training strategy: firstly, independently training soft-pruning networks for different agent quantities to determine optimal agent-quantity-specific complete graphs and positional masks across specific tasks; and then jointly optimizing hard-pruning and soft-pruning within a maximum complete graph to dynamically configure the number of agents and their communication topologies per task. Extensive experiments demonstrate that our approach is: (1) High-performing, achieving state-of-the-art results across six benchmarks and consistently generalizes across multiple mainstream LLM architectures, with a increase in performance of 2.58%~ 9.84%; (2) Task-adaptive, dynamically constructing optimized communication topologies tailored to specific tasks, with an extremely high performance in all three task categories (general reasoning, mathematical reasoning, and code generation); (3) Token-economical, having fewer training steps and token consumption at the same time, with a decrease in token consumption of 90%+; and (4) Training-efficient, achieving high performance with very few training steps compared with other methods. The performance will surpass the existing baselines after about ten steps of training under six benchmarks.