# How Task Structure Limits Multi-Agent Success: An Information-Theoretic Analysis

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 53 references that are in the map.
- First posted on arXiv 11 Jun 2026.

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

- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [AgentVerse: Facilitating Multi-Agent Collaboration and Exploring Emergent Behaviors](https://mlsanity.com/paper/2308.10848/) (2023)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [AutoCodeRover: Autonomous Program Improvement](https://mlsanity.com/paper/2404.05427/) (2024)
- [Scaling Large Language Model-based Multi-Agent Collaboration](https://mlsanity.com/paper/2406.07155/) (2024)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Chain of Agents: Large Language Models Collaborating on Long-Context Tasks](https://mlsanity.com/paper/2406.02818/) (2024)
- [Rethinking the Bounds of LLM Reasoning: Are Multi-Agent Discussions the Key?](https://mlsanity.com/paper/2402.18272/) (2024)
- [TaskBench: Benchmarking Large Language Models for Task Automation](https://mlsanity.com/paper/2311.18760/) (2023)
- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [Towards a Science of Scaling Agent Systems](https://mlsanity.com/paper/2512.08296/) (2025)
- [Context Length Alone Hurts LLM Performance Despite Perfect Retrieval](https://mlsanity.com/paper/2510.05381/) (2025)
- [Scalable Multi-Robot Collaboration with Large Language Models: Centralized or Decentralized Systems?](https://mlsanity.com/paper/2309.15943/) (2023)
- [AgentNet: Decentralized Evolutionary Coordination for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2504.00587/) (2025)
- [Flow: Modularized Agentic Workflow Automation](https://mlsanity.com/paper/2501.07834/) (2025)
- [Rethinking the Value of Multi-Agent Workflow: A Strong Single Agent Baseline](https://mlsanity.com/paper/2601.12307/) (2026)
- [Unable to Forget: Proactive Interference Reveals Working Memory Limits in LLMs Beyond Context Length](https://mlsanity.com/paper/2506.08184/) (2025)
- [Multi-Agent Coordination via Multi-Level Communication](https://mlsanity.com/paper/2209.12713/) (2022)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [On the Distributed Complexity of Large-Scale Graph Computations](https://mlsanity.com/paper/1602.08481/) (2016)
- [Distributed Information Bottleneck Theory for Multi-Modal Task-Aware Semantic Communication](https://mlsanity.com/paper/2510.04000/) (2025)
- [Communication to Completion: Modeling Collaborative Workflows with Intelligent Multi-Agent Communication](https://mlsanity.com/paper/2510.19995/) (2025)

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

- [The Working Set of a Coding Agent: Coherence Debt in Repository-Scale Tasks](https://mlsanity.com/paper/2608.16630/) (2026)

## Abstract (arXiv)

Multi-agent systems (MAS) were expected to overcome the limitation of single-agent systems (SAS) through collaboration. However, under typicality conditions on the task's constraint graph and bounded inter-agent communication, we prove that the success probability of a MAS is closely tied to the connectivity of task constraints, where each agent has limited information-processing capacity. Specifically, the success probability decays exponentially with an information bottleneck that emerges from partitioning the task's constraint graph among agents. We define this quantity as the minimum cut cost Cmin of the potential constraint graph of each task. This information-theoretic bound applies to both open systems with external feedback and closed systems without. We validate our theory on both synthetic experiments and real-world empirical data from SWE-bench submissions. From our framework, effective MAS design should incorporate task-inherent constraints alongside engineering optimization, and when Cmin is high, practitioners should restructure tasks rather than simply scaling agents or communication.