arxiv:2607.11250

Multi-Agent LLMs Fail to Explore Each Other

Published on Jul 13

· Submitted by

Hyeong Kyu (Froilan) Choi on Jul 14

University of Wisconsin - Madison

Upvote

Authors:

Abstract

Exploration is essential for reliable autonomy in multi-agent systems, yet it remains unclear whether large language model (LLM) agents can explore effectively when interacting with one another. We show that modern LLM agents fail to do so, often exhibiting myopic and polarized interaction patterns that lead to suboptimal coordination and increased regret. We formalize this challenge as the Multi-Agent Exploration problem, modeling it as a partially observable stochastic game (POSG) problem in which agents must probe peers to infer their capabilities and identify effective interaction strategies. To address this, we introduce Multi- Agent Contextual Exploration (MACE), a lightweight framework that explicitly promotes exploration through structured peer selection. Across both contextual and parametric diversity settings, MACE substantially improves exploration behavior and downstream task performance. We further show theoretically that the value of exploration increases with agent diversity. Overall, our results highlight a fundamental limitation of current LLM agents and underscore the importance of explicitly guided exploration for reliable multi-agent autonomy. Code will be released in https://github.com/deeplearning-wisc/mace

View arXiv page View PDF Add to collection

Community

imhgchoi

Paper submitter about 5 hours ago

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.