cs.MANov 11, 2026

DecArena: Evaluating Large-Scale Decentralized Multi-Agent Collaboration

Authors: Jiali Cheng, Oleg Rokhlenko, Joo-Kyung Kim, Hadi Amiri, Xingzhi Guo

Organizations: University of Massachusetts Lowell · Amazon Alexa AI

Abstract

Emerging personal AI agents raise fundamental scalability and privacy concerns for centralized multi-agent systems (MASs), which rely on a global orchestrator with broad access to agents, resources, and communication. In decentralized environments, global visibility is unavailable. Agents need to proactively discover non-local resources (e.g. tools, skills), and collaborate with other agents to solve tasks. We study decentralized multi-agent collaboration under graph-constrained communication, a natural reflection of human structures. Each agent observes only its local state and can interact only with neighboring agents. We introduce a benchmark with synthetic scalable distributed tool calling with 100K+ tools. Our experiments reveal that recent LLM agents struggle to discover non-local relevant resources and collaborate in decentralized setting. Moreover, standard reinforcement learning fails to reliably overcome this limitation, suggesting that decentralized MAS needs more explicit harness mechanisms for effective collaboration, even using SOTA LLMs. We then present a strong baseline GraphHarness, combining topology-aware warmup with self-improving LLM-based routing. Results show that GraphHarness substantially improves task success (+48.5) and produces higher quality collaboration (+30.6), while using fewer costs (+34.0) than baselines.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. AgentWorld: Benchmarking Long-Horizon Collaboration of Multi-agent LLMs

    Sep 25, 2026Raphael Shu, Yusen Zhang, Young Min Cho +7Multi-Agent CollaborationAI Agent Benchmarks

  2. Silo-Bench: A Scalable Environment for Evaluating Distributed Coordination in Multi-Agent LLM Systems

    Mar 1, 2026Yuzhe Zhang, Feiran Liu, Yi Shan +8Multi-Agent LLM SystemsMulti-Agent Coordination

  3. MASBench: Benchmarking LLM-based Multi-Agent Collaboration under Partial Observability

    Oct 3, 2026Qizhi Chu, Zekai Yu, Sijie Wen +5Multi-Agent LLM SystemsMulti-Agent Collaboration