Reproduce “Benefits and Limitations of Communication in Multi-Agent Reasoning” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Michael Rizvi-Martel, Satwik Bhattamishra, Neil Rathi, Guillaume Rabusseau, Michael Hahn

A formal theoretical framework analyzes the algorithmic benefits and limitations of communication in multi-agent Large Language Model systems, demonstrating that communication strategies profoundly impact performance across different task families and revealing task-specific tradeoffs between computation depth, the number of agents, and communication overhead. This work shows structured communication protocols can yield super-polynomial advantages over simple voting schemes for certain reasoning tasks.

Key insights

  • Multi-agent reasoning tasks can be categorized into three regimes based on communication and depth tradeoffs: low communication/low depth (associative recall), high communication/reduced depth (state tracking), and high communication/no depth reduction (k-hop reasoning).
  • There is a fundamental tradeoff where increasing the number of agents can reduce computation depth, but only with a corresponding increase in communication, as total computational size is largely conserved.
  • Structured multi-agent protocols, such as Prefix Sum for state tracking, offer a super-polynomial separation in agent requirements compared to naive self-consistency or majority voting schemes for certain tasks.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.