ACL Findings2026
When 20 Agents Fail to Sort: The Distributed Sorting Benchmark for Scalable Multi-Agent Systems
Xin Yang, Junhao Wang, Bintao Tang, Xuxin Cheng, Cao Liu, Ke Zeng, Wenyuan Jiang
Abstract
Current LLM-based multi-agent systems remain fragile under scaling, even on algorithmically trivial tasks. We introduce MAS-BENCH, a distributed-sorting benchmark that isolates coordination under explicit communication constraints: each agent observes only a local segment and must collectively produce a globally consistent order via broadcasting, peer-to-peer messaging, or a shared key-value store. Across LLM-based agents, success drops sharply as the number of agents grows, exposing persistent failures in shared state, convention alignment, and consistent termination. To mitigate these breakdowns, we propose CAMOC, a lightweight, drop-in proof-of-concept built on collaboration-aware information sharing, early global metadata exchange, and single-commit verification. CAMOC substantially improves coordination success and efficiency across backends, with the largest gains under shared-state interaction. Overall, MAS-BENCH provides a diagnostic benchmark and CAMOC offers a practical step toward more reliable large-scale LLM collaboration, highlighting a gap between individual reasoning and collective correctness. send_to() ❶ P2P messaging ❷ Broadcasting ❸ Shared K-V store Shared K-V store write_shared() Agent-0 here. My local list: […]. Please share your local list.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Reflexion: language agents with verbal reinforcement learning cites Self-Refine: Iterative Refinement with Self-Feedback
- Reflexion: language agents with verbal reinforcement learning cites Toolformer: Language Models Can Teach Themselves to Use Tools
Builds on17
- Toolformer: Language Models Can Teach Themselves to Use ToolsTimo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu et al.NeurIPS 2023 · 5,989 citations
- Reflexion: language agents with verbal reinforcement learningNoah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan et al.NeurIPS 2023 · 5,828 citations
- Self-Refine: Iterative Refinement with Self-FeedbackAman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan et al.NeurIPS 2023 · 4,972 citations
- SWE-bench: Can Language Models Resolve Real-world Github Issues?Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao et al.ICLR 2024 · 2,082 citations
- CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model SocietyGuohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin et al.NeurIPS 2023 · 1,975 citations
Related papers
- SILO-BENCH: A Scalable Environment for Evaluating Distributed Coordination in Multi-Agent LLM SystemsYuzhe Zhang, Feiran Liu, Yi Shan, Xinyi Huang et al.ACL 2026 · 5 citations
- Systematic Failures in Collective Reasoning under Distributed Information in Multi-Agent LLMsYuxuan Li, Aoi Naito, Hirokazu ShiradoICML 2026 · 9 citations
- MOC: Multi-Order Communication in LLM-based Multi-Agent SystemsYao Guan, Lin Wang, Zhihui Lu, Ziyi Wang et al.ICML 2026
- MultiAgentBench : Evaluating the Collaboration and Competition of LLM agentsKunlun Zhu, Hongyi Du, Zhaochen Hong, Xiaocheng Yang et al.ACL 2025 · 97 citations
- Autonomous Agents for Collaborative Task under Information AsymmetryWei Liu, Chenxi Wang, Yifei Wang, Zihao Xie et al.NeurIPS 2024 · 17 citations
