# Benefits and Limitations of Communication in Multi-Agent Reasoning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 35 of its 66 references that are in the map.
- First posted on arXiv 14 Oct 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- 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 35)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned](https://mlsanity.com/paper/1905.09418/) (2019)
- [Mixture-of-Agents Enhances Large Language Model Capabilities](https://mlsanity.com/paper/2406.04692/) (2024)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Zoology: Measuring and Improving Recall in Efficient Language Models](https://mlsanity.com/paper/2312.04927/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [OMEGA: Can LLMs Reason Outside the Box in Math? Evaluating Exploratory, Compositional, and Transformative Generalization](https://mlsanity.com/paper/2506.18880/) (2025)
- [Entity Tracking in Language Models](https://mlsanity.com/paper/2305.02363/) (2023)
- [Learning Compositional Functions with Transformers from Easy-to-Hard Data](https://mlsanity.com/paper/2505.23683/) (2025)
- [HM-RAG: Hierarchical Multi-Agent Multimodal Retrieval Augmented Generation](https://mlsanity.com/paper/2504.12330/) (2025)
- [Do Large Language Models Perform Latent Multi-Hop Reasoning without Exploiting Shortcuts?](https://mlsanity.com/paper/2411.16679/) (2024)
- [Learning to Break: Knowledge-Enhanced Reasoning in Multi-Agent Debate System](https://mlsanity.com/paper/2312.04854/) (2023)
- [MA-RAG: Multi-Agent Retrieval-Augmented Generation via Collaborative Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.20096/) (2025)
- [Group Think: Multiple Concurrent Reasoning Agents Collaborating at Token Level Granularity](https://mlsanity.com/paper/2505.11107/) (2025)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Models](https://mlsanity.com/paper/2402.05359/) (2024)
- [Multi2: Multi-Agent Test-Time Scalable Framework for Multi-Document Processing](https://mlsanity.com/paper/2502.20592/) (2025)
- [AgentGroupChat-V2: Divide-and-Conquer Is What LLM-Based Multi-Agent System Need](https://mlsanity.com/paper/2506.15451/) (2025)
- [Language models can learn implicit multi-hop reasoning, but only if they have lots of training data](https://mlsanity.com/paper/2505.17923/) (2025)
- [A Collaborative Multi-Agent Approach to Retrieval-Augmented Generation Across Diverse Data](https://mlsanity.com/paper/2412.05838/) (2024)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)

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

- [GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2603.19677/) (2026)
- [Beyond Consensus: Trace-Level Synthesis in Mixture of Agents](https://mlsanity.com/paper/2605.29116/) (2026)
- [Improving the Efficiency of Language Agent Teams with Adaptive Task Graphs](https://mlsanity.com/paper/2605.06320/) (2026)
- [Rethinking Scale: Deployment Trade-offs of Small Language Models under Agent Paradigms](https://mlsanity.com/paper/2604.19299/) (2026)
- [Streaming Communication in Multi-Agent Reasoning](https://mlsanity.com/paper/2606.05158/) (2026)
- [Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts](https://mlsanity.com/paper/2607.29496/) (2026)
- [Policy-Backed Selective Regeneration under Tainted Inter-Agent Communication](https://mlsanity.com/paper/2609.26072/) (2026)

## Abstract (arXiv)

Chain-of-thought prompting has popularized step-by-step reasoning in large language models, yet model performance still degrades as problem complexity and context length grow. By decomposing difficult tasks with long contexts into shorter, manageable ones, recent multi-agent paradigms offer a promising near-term solution to this problem. However, the fundamental capacities of such systems are poorly understood. In this work, we propose a theoretical framework to analyze the expressivity of multi-agent systems. We apply our framework to three algorithmic families: state tracking, recall, and k-hop reasoning. We derive bounds on (i) the number of agents required to solve the task exactly, (ii) the quantity and structure of inter-agent communication, and (iii) the achievable speedups as problem size and context scale. Our results identify regimes where communication is provably beneficial, delineate tradeoffs between agent count and bandwidth, and expose intrinsic limitations when either resource is constrained. We complement our theoretical analysis with a set of experiments on pretrained LLMs using controlled synthetic benchmarks. Empirical outcomes confirm the tradeoffs between key quantities predicted by our theory. Collectively, our analysis offers principled guidance for designing scalable multi-agent reasoning systems.