Multi-Agent LLMs Fail to Explore Each Other

1️⃣ We find that current LLM agents, including frontier models, often fail to systematically explore their peers. Instead, they prematurely commit to a small number of agents, producing myopic and highly polarized interaction patterns.

2️⃣ 𝘞𝘩𝘺 𝘥𝘰𝘦𝘴 𝘵𝘩𝘪𝘴 𝘮𝘢𝘵𝘵𝘦𝘳? In real-world multi-agent systems, agents may possess different knowledge, capabilities, and areas of expertise. To collaborate effectively, an agent must explore its peers, identify complementary strengths, and learn whom to interact with in different contexts. Without effective exploration, even a system of individually capable agents can suffer from poor coordination and miss valuable information.

3️⃣ To address this, we introduce 𝑴𝒖𝒍𝒕𝒊-𝑨𝒈𝒆𝒏𝒕 𝑪𝒐𝒏𝒕𝒆𝒙𝒕𝒖𝒂𝒍 𝑬𝒙𝒑𝒍𝒐𝒓𝒂𝒕𝒊𝒐𝒏 (𝑴𝑨𝑪𝑬), a lightweight framework that uses structured, contextual-bandit-based peer selection to help agents discover effective collaborators.

4️⃣ Theoretically, MACE achieves sublinear regret, whereas non-exploring strategies incur linear regret. Importantly, the value of exploration grows as the agents become more diverse.

🎯 Our results highlight a fundamental lesson for multi-agent autonomy: building stronger individual agents is not enough. We must also enable them to systematically discover and learn from one another.