# On the Importance of Task Complexity in Evaluating LLM-Based Multi-Agent Systems

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

## Key facts

- Cited by 6 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 21 of its 29 references that are in the map.
- First posted on arXiv 5 Oct 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, 21 of 21)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (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)
- [AndroidWorld: A Dynamic Benchmarking Environment for Autonomous Agents](https://mlsanity.com/paper/2405.14573/) (2024)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks](https://mlsanity.com/paper/2410.11782/) (2024)
- [Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies](https://mlsanity.com/paper/2502.02533/) (2025)
- [DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks](https://mlsanity.com/paper/2309.17167/) (2023)
- [Agents' Room: Narrative Generation through Multi-step Collaboration](https://mlsanity.com/paper/2410.02603/) (2024)
- [MAS-GPT: Training LLMs to Build LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2503.03686/) (2025)
- [ViMo: A Generative Visual GUI World Model for App Agents](https://mlsanity.com/paper/2504.13936/) (2025)
- [Single-agent or Multi-agent Systems? Why Not Both?](https://mlsanity.com/paper/2505.18286/) (2025)
- [Synthesizing Post-Training Data for LLMs through Multi-Agent Simulation](https://mlsanity.com/paper/2410.14251/) (2024)
- [Revisiting Multi-Agent Debate as Test-Time Scaling: A Systematic Study of Conditional Effectiveness](https://mlsanity.com/paper/2505.22960/) (2025)
- [GNNs as Predictors of Agentic Workflow Performances](https://mlsanity.com/paper/2503.11301/) (2025)
- [MASLab: A Unified and Comprehensive Codebase for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2505.16988/) (2025)
- [Beyond Syntax: Action Semantics Learning for App Agents](https://mlsanity.com/paper/2506.17697/) (2025)
- [The cost of coordination can exceed the benefit of collaboration in performing complex tasks](https://mlsanity.com/paper/2009.11038/) (2020)

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

- [Understanding Agent Scaling in LLM-Based Multi-Agent Systems via Diversity](https://mlsanity.com/paper/2602.03794/) (2026)
- [Recognize Your Orchestrator: An Entropy Dynamics Perspective for LLM Multi-Agent Systems](https://mlsanity.com/paper/2606.01351/) (2026)
- [Rethinking the Evaluation of Efficiency Methods for Multi-Agent Systems](https://mlsanity.com/paper/2609.05933/) (2026)
- [Fine-Tuning Small Reasoning Models for Quantum Field Theory](https://mlsanity.com/paper/2604.18936/) (2026)
- [Towards a Science of Collective AI: LLM-based Multi-Agent Systems Need a Transition from Blind Trial-and-Error to Rigorous Science](https://mlsanity.com/paper/2602.05289/) (2026)
- [Attention Tax, Handoff Tax: A Stylised Model of When Multi-Agent LLM Systems Help](https://mlsanity.com/paper/2610.06069/) (2026)

## Abstract (arXiv)

Large language model multi-agent systems (LLM-MAS) offer a promising paradigm for harnessing collective intelligence to achieve more advanced forms of AI behaviour. While recent studies suggest that LLM-MAS can outperform LLM single-agent systems (LLM-SAS) on certain tasks, the lack of systematic experimental designs limits the strength and generality of these conclusions. We argue that a principled understanding of task complexity, such as the degree of sequential reasoning required and the breadth of capabilities involved, is essential for assessing the effectiveness of LLM-MAS in task solving. To this end, we propose a theoretical framework characterising tasks along two dimensions: depth, representing reasoning length, and width, representing capability diversity. We theoretically examine a representative class of LLM-MAS, namely the multi-agent debate system, and empirically evaluate its performance in both discriminative and generative tasks with varying depth and width. Theoretical and empirical results show that the benefit of LLM-MAS over LLM-SAS increases with both task depth and width, and the effect is more pronounced with respect to depth. This clarifies when LLM-MAS are beneficial and provides a principled foundation for designing future LLM-MAS methods and benchmarks.