Elamur Research⌕
☰
home / papers / 2026 / When 20 Agents Fail to Sort: The Distributed Sorting Benchmark for Scalable Multi-Agent Systems

When 20 Agents Fail to Sort: The Distributed Sorting Benchmark for Scalable Multi-Agent Systems

Paper · 2026 · Xin Yang, Junhao Wang, Bintao Tang et al.

Summary

The paper examines whether LLM-based agents can coordinate without heavy human scaffolding, such as predefined roles or scripted pipelines. It tests this with a task that is easy to compute but requires a lot of coordination: distributed sorting. In MAS-Bench, each of N agents sees only a local segment of K integers. Together, the agents must produce segments that form one globally sorted array. They communicate through one of three symmetric channels: Broadcasting, P2P Messaging, or a Shared K-V Store. The benchmark varies the number of agents, the segment size and how disordered the input is. It scores runs on correctness and on coordination cost.

Across the models tested, success falls steeply as more agents are added, while rounds and token use grow. The Shared K-V setting breaks down most often. The authors propose CAMOC, a coordination layer that works without retraining. It adds three things: collaboration-aware messages, early sharing of coarse global metadata, and a single final commit. CAMOC raises success and efficiency across models. The work suggests that strong reasoning by individual agents does not guarantee correct collective results.

Key points

  • Input structure: Instances are defined by (N, K, E, l), where E is the communication environment and l is the input list. Disorder is measured by the inversion count and a normalized inversion rate. There are five input families: asc, near_asc, random, near_desc and desc. The near_* variants keep 80% of positions fixed.
  • Metrics:
    • Success Rate (SR): an instance counts as solved only when every agent's segment matches the ground truth.
    • Round Number (R): the maximum number of rounds any agent used.
    • Token Efficiency (TE): sorted elements per token, scaled by 10^5.
    • Communication Ratio (CR): the share of tokens spent on coordination.
  • Models and failure patterns: Three frontier LLMs were tested, including GPT-OSS-120B and Qwen3-80B. Common failures involve keeping shared state consistent, agreeing on conventions and ending the task consistently. In P2P, agents tend to over-negotiate.
  • CAMOC results: CAMOC improves success rates by up to 40%, with the largest benefit under Shared K-V. Ablations show that message-level coordination mainly improves efficiency, while structured submission mainly improves correctness. Welch's t-tests found only one significant regression: Qwen3 on P2P, caused by the One-shot Commitment component.
  • Additional tasks and limits: Two extra tasks were added, Distributed Maximum (loosely coupled) and Distributed Prefix Sum (moderately coupled). Base success drops as tasks become more tightly coupled, and CAMOC's relative gain grows accordingly. The data consists only of synthetic integer sequences, with no human data.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Chinese University of Hong KongHong Kong · China159 works · 16,154 citations🎓Zhejiang UniversityHangzhou · China224 works · 13,587 citations🎓ETH ZurichZurich · Switzerland84 works · 9,181 citations🏢MeituanBeijing · China26 works · 3,953 citations🎓Tongji UniversityShanghai · China33 works · 2,993 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Networks and Communications · 100 works

🧭 Topics 1Research subjects and languages the work is about.Evaluation & benchmarks · 1,341 works

Cite

Cite as Xin Yang, Junhao Wang, Bintao Tang, Xuxin Cheng, Cao Liu, Ke Zeng and Wenyuan Jiang. 2026. When 20 Agents Fail to Sort: The Distributed Sorting Benchmark for Scalable Multi-Agent Systems. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1698

@inproceedings{yang2026when,
  title = {{When 20 Agents Fail to Sort: The Distributed Sorting Benchmark for Scalable Multi-Agent Systems}},
  author = {Xin Yang, Junhao Wang, Bintao Tang, Xuxin Cheng, Cao Liu, Ke Zeng and Wenyuan Jiang},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1698},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1698}
}

References

43 references, 21 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. DeepSeek-AI. 2024. Deepseek-v3 technical report. CoRR, abs/2412.19437. find
  2. Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. 2024. Improving factuality and reasoning in language models through multiagent debate. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Proceedings of Machine Lear…
  3. Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, and Shimon Whiteson. 2016. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barce… find
  4. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, E… — Training Compute-Optimal Large Language Models
  5. Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, Yujia Qin, Xin Cong, Ruobing Xie, Zhiyuan Liu, Maosong Sun, and Jie Zhou. 2024. Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors. In The Twelft…
  6. Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. 2024. Metagpt: Meta programming for A multi-agent collaborative framework. In The T…
  7. Xuxin Cheng, Ke Zeng, Zhiquan Cao, Linyi Dai, Wenxuan Gao, Fei Han, Ai Jian, Feng Hong, Wenxing Hu, Zihe Huang, Dejian Kong, Jia Leng, Zhuoyuan Liao, Pei Liu, Jiaye Lin, Xing Ma, Jingqing Ruan, Jiaxing Song, Xiaoyu Tan, Ruixuan Xiao, Wenhui Yu, Wenyu Zhan, Haoxing Zhang, Chao Zhou, Hao Zhou, Shaodon… — [arXiv:2510.13291](https://arxiv.org/abs/2510.13291) find
  8. Bin Hu, Chenyang Zhao, Pu Zhang, Zihao Zhou, Yuanhang Yang, Zenglin Xu, and Bin Liu. 2024. Enabling intelligent interactions between an agent and an LLM: A reinforcement learning approach. RLJ, 3:1289–1305. find
  9. Jeffrey Dean and Sanjay Ghemawat. 2008. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51(1):107–113. find
  10. Zimo Ji, Daoyuan Wu, Wenyuan Jiang, Pingchuan Ma, Zongjie Li, Yudong Gao, Shuai Wang, and Yingjiu Li. 2026. Taming various privilege escalation in llm-based agent systems: A mandatory access control framework. CoRR, abs/2601.11893. — [arXiv:2601.11893](https://arxiv.org/abs/2601.11893) find
  11. Zimo Ji, Daoyuan Wu, Wenyuan Jiang, Pingchuan Ma, Zongjie Li, and Shuai Wang. 2025. Measuring and augmenting large language models for solving capture-the-flag challenges. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS 2025, Taipei, Taiwan, October 13-1… find
  12. Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R. Narasimhan. 2024. Swe-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe…
  13. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. 2020. Scaling laws for neural language models. CoRR, abs/2001.08361.
  14. Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni. 2017. Multi-agent cooperation and the emergence of (natural) language. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. find
  15. Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. 2023. CAMEL: communicative agents for "mind" exploration of large language model society. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 20…
  16. Junyou Li, Qin Zhang, Yangbin Yu, Qiang Fu, and Deheng Ye. 2024. More agents is all you need.
  17. Trans. Mach. Learn. Res., 2024. find
  18. Tian Liang, Zhiwei He, Wenxiang Jiao, Xing Wang, Yan Wang, Rui Wang, Yujiu Yang, Shuming Shi, and Zhaopeng Tu. 2024. Encouraging divergent thinking in large language models through multi-agent debate. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, EMNLP 20…
  19. Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du, Chenhui Zhang, Sheng Shen, Tianjun Zhang, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang. 2024. Agentbench: Evaluating llms…
  20. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. 2023. Self-refine: Iterative refinement with… find
  21. Yohei Nakajima. 2026. Babyagi. GitHub repository. Accessed: 2026-01-04. find
  22. Reza Olfati-Saber, J. Alexander Fax, and Richard M. Murray. 2007. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 95(1):215– 233. find
  23. OpenAI. 2025. gpt-oss-120b & gpt-oss-20b model card. CoRR, abs/2508.10925.
  24. Joon Sung Park, Joseph C. O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. 2023. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, UIST 2023, San Francisco, CA,… find
  25. Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. 2024. Gorilla: Large language model connected with massive apis. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December…
  26. Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen, Yusheng Su, Xin Cong, Juyuan Xu, Dahai Li, Zhiyuan Liu, and Maosong Sun. 2024. Chatdev: Communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computat…
  27. Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural I…
  28. Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. 2023. Hugginggpt: Solving AI tasks with chatgpt and its friends in hugging face. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023,…
  29. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans,…
  30. Yoav Shoham and Kevin Leyton-Brown. 2009. Multi-agent Systems - Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press. find
  31. Significant-Gravitas. 2026. Autogpt. GitHub repository. Accessed: 2026-01-04. find
  32. Qwen Team. 2025. Qwen3 technical report. CoRR, abs/2505.09388.
  33. Michael J. Wooldridge. 2009. An Introduction to Multi-Agent Systems, Second Edition. Wiley. find
  34. Xuhui Zhou, Hao Zhu, Leena Mathur, Ruohong Zhang, Haofei Yu, Zhengyang Qi, Louis-Philippe Morency, Yonatan Bisk, Daniel Fried, Graham Neubig, and Maarten Sap. 2024b. SOTOPIA: interactive evaluation for social intelligence in language agents. In The Twelfth International Conference on Learning Repres…
  35. Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. 2023. Autogen: Enabling next-gen LLM applications via multi-agent conversation framework. CoRR, abs/2308.08155.
  36. Wangyu Wu, Zhenhong Chen, Xiaowen Ma, Wenqiao Zhang, Xianglin Qiu, Siqi Song, Xiaowei Huang, Fei Ma, and Jimin Xiao. 2026. Contrastive prompt clustering for weakly supervised semantic segmentation. Expert Syst. Appl., 316:131880. find
  37. Wangyu Wu, Zhenhong Chen, Xianglin Qiu, Siqi Song, Xiaowei Huang, Fei Ma, and Jimin Xiao. 2025. Llm-enhanced multimodal fusion for cross-domain sequential recommendation. CoRR, abs/2506.17966. — [arXiv:2506.17966](https://arxiv.org/abs/2506.17966) find
  38. Xin Yang, Letian Li, Abudukelimu Wuerkaixi, Xuxin Cheng, Cao Liu, Ke Zeng, Xunliang Cai, and Wenyuan Jiang. 2026. Towards self-robust llms: Intrinsic prompt noise resistance via coipo. CoRR, abs/2603.03314. — [arXiv:2603.03314](https://arxiv.org/abs/2603.03314) find
  39. Xin Yang, Bintao Tang, Yuhao Wang, Zimo Ji, and Wenyuan Jiang. 2025. Can llms write fast system-aware numerical computation code? In IEEE International Conference on Systems, Man, and Cybernetics, SMC 2025, Vienna, Austria, October 5-8, 2025, pages 672–675. IEEE. find
  40. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023a. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023,… find
  41. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. 2023b. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
  42. Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. 2024a. Webarena: A realistic web environment for building autonomous agents. In The Twelfth International Conference on Learning Representatio…
  43. A Artifacts & Open Source Licenses find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yang-2026-when-20-agents-fail-sort/