Communication links control success in multi agent search tasks
Absorbing State Phase Transitions in Multi-Agent Search
Multiagent Systems
Summary
Searching for solutions can be tricky when many AI agents work together, especially if they don’t share information well. The authors studied how the number of connections between agents affects whether they can find the right answer without getting stuck on wrong ideas. They developed a theoretical minimum for how many other agents each one should talk to for the search to succeed. They tested this with AI agents solving real problems and found mixed results, since agents sometimes ignored communication or worked solo in ways that hurt group progress.
What this means in practice
- •For software debugging teams: Improve automated bug-finding scripts by tuning how AI agents communicate to avoid getting stuck on false leads.
- •For machine learning engineers: Design communication networks between AI agents that balance individual strategies and group success in complex discovery tasks.
Authors
Wenwen Zheng, Yuzhe Yang, Helen Qu, Xin Eric Wang, Haewon Jeong
Abstract
Nontrivial dynamics can emerge in large language model (LLM)-based multi-agent systems, and preliminary evidence exists that formalisms from statistical mechanics can be effective at modeling and predicting such behaviors. In parallel, designing multi-agent communication topology for optimal task-solving is an active research question. In this paper, we focus on predicting the success of multi-agent search tasks using the formalism of absorbing state phase transitions. We first taxonomize search tasks into four types, informed by classical results in combinatorial search. We then theoretically derive a critical communication degree $d_c$, the minimum number of agents each agent can communicate with, above which incorrect hypotheses do not proliferate uncontrollably and the search enters the solved state. Finally, we evaluate frontier LLM-based multi-agent systems on real-world search and discovery tasks, software configuration debugging and physical mechanism discovery, and find that agreement with theory is mixed. LLM agents may not communicate with their neighbors and can develop strategies that are individually beneficial but limits the benefits of collaboration.