Benefits and Limitations of Communication in Multi-Agent Reasoning
Michael Rizvi-Martel, Satwik Bhattamishra, Neil Rathi, Guillaume Rabusseau, Michael Hahn
Why It Matters
What makes this one worth your time
Understanding the tradeoffs and limitations in multi-agent communication can guide the design of more efficient and scalable AI systems.
The paper provides a theoretical framework for analyzing multi-agent systems' expressivity in complex task decomposition.
Summary
The paper proposes a theoretical framework to analyze the expressivity of multi-agent systems in decomposing complex tasks into manageable ones, focusing on state tracking, recall, and $k$-hop reasoning. It derives bounds on agent requirements, communication structure, and speedups, and validates these with experiments on pretrained LLMs using synthetic benchmarks.
Key contributions
- Proposes a theoretical framework for analyzing multi-agent systems.
- Derives bounds on agent requirements and communication structure.
- Validates theoretical predictions with empirical experiments on synthetic benchmarks.
Notable insights
- Identifies regimes where communication is provably beneficial in multi-agent systems.
- Delineates tradeoffs between agent count and communication bandwidth.
Possible limitations
- Not stated in the abstract
Abstract
arXiv:2510.13903v2 Announce Type: replace-cross Abstract: 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.