Research map / Multi-agent systems and games / LLM agents

Benefits and Limitations of Communication in Multi-Agent Reasoning

ICLR 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent decision making

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a graph-based theoretical framework for multi-agent Transformer systems and derives bounds on agent count, communication, depth and size for associative recall, state tracking (parity/monoids), and k-hop reasoning, with small-scale validation on Llama models.

Problem

Understanding the fundamental expressivity, depth, and communication tradeoffs of multi-agent LLM reasoning systems, which are poorly understood despite their use for long-context and complex reasoning.

Approach

Formalize multi-agent systems as DAGs of agent-state nodes with CoT and communication edges, analyzed under unique hard attention Transformers; derive matching upper and lower bounds for three algorithmic task families, identifying three regimes of depth-communication tradeoffs.

Key results

• Theory: associative recall solvable with O(1) depth and O(1) communication using w agents; state tracking achieves depth O(log w + N/w) with communication budget w(N), and this is near-optimal.
• Majority voting with polynomially many agents requires 2^{Omega(N^c)} agents for parity at O(log N) CoT length, while PrefixSum solves it with N agents and O(log N) depth.
• Experiments show Iterative Query generally outperforms Majority Voting on k-hop reasoning, with the gap widening as hops increase; CoA degrades less than majority voting on needle-in-a-haystack and parity.

Surprising findings

• Majority voting over many agents can be super-polynomially less expressive than a communicating prefix-sum protocol for parity at logarithmic depth.
• For the smallest number of hops (four), majority voting sometimes outperforms Iterative Query.

Limitations

• Experiments use hard-coded simple protocols and prompting rather than optimized systems; the paper is an analysis rather than methods paper.
• Large reasoning models (e.g., o3, DeepSeek-R1) were not evaluated because their hidden CoT prevents controlling the reasoning strategy.
• Analysis restricted to single-token communication, partitioned inputs, and UHAT expressivity; unbounded communication and shared-input debate/voting are out of scope.

Experimental setup

Datasets: synthetic needle-in-a-haystack synthetic parity bitstrings synthetic k-hop fact queries

Benchmarks: needle-in-a-haystack Parity k-hop reasoning

Metrics: accuracy communication (token usage) computation depth

Baselines: Majority Voting (self-consistency) Chain-of-Agent (CoA)

Builds on: chain-of-thought unique hard attention transformers Chain-of-Agents self-consistency

Closest papers by meaning

• Unlocking the Power of Multi-Agent LLM for Reasoning: From Lazy Agents to Deliberation (ICLR 2026 · similarity 0.90)
• Systematic Failures in Collective Reasoning under Distributed Information in Multi-Agent LLMs (ICML 2026 · similarity 0.90)
• Distilling LLM Agent into Small Models with Retrieval and Code Tools (NeurIPS 2025 · similarity 0.88)
• Real-Time Reasoning Agents in Evolving Environments (ICLR 2026 · similarity 0.88)
• Stochastic Self-Organization in Multi-Agent Systems (ICLR 2026 · similarity 0.88)
• MAGDi: Structured Distillation of Multi-Agent Interaction Graphs Improves Reasoning in Smaller Language Models (ICML 2024 · similarity 0.88)