Multi-Agent LLMs Fail to Explore Each Other¶
🕒 Published (v1): 2026-07-13 08:34 UTC · Source: Arxiv · link
Why this paper was selected
Sharon Li lab; empirical proof LLM agents fail exploration — undermines multi-agent reliability assumptions
Ask a follow-up
Open an assistant pre-loaded with this paper's context.
TL;DR¶
Current LLM agents — including GPT-4 and GPT-5 — exhibit premature commitment when selecting collaborators in multi-agent settings, locking onto a single peer within the first few rounds rather than exploring to identify the best one. The authors formalize this as a Partially Observable Stochastic Game (POSG) and introduce MACE (Multi-Agent Contextual Exploration), a LinUCB-based contextual bandit framework that significantly reduces cumulative regret by explicitly incentivizing relational exploration. Theoretical analysis shows exploration benefit grows unboundedly with agent diversity.
Problem¶
Multi-agent LLM systems implicitly assume agents can autonomously balance exploration and exploitation when selecting collaborators, but this has never been rigorously tested. The gap is that no prior work formalizes or addresses the failure mode where agents commit prematurely to a peer before accumulating sufficient evidence about the heterogeneous capability landscape — a problem that compounds across agents and rounds in decentralized, partially observable settings.
Method¶
MACE decomposes the intractable finite-horizon POSG into independent per-agent contextual bandit problems. Each agent \(i\) selects peer \(a\) at round \(t\) by maximizing a LinUCB acquisition:
where \(\hat{\theta}_{i,a} = A_{i,a}^{-1} b_{i,a}\) is a ridge-regression reward estimate and the second term is an uncertainty bonus. The key design choice is the relational feature vector \(x_{i,a,t} \in \mathbb{R}^d\), encoding: (i) response diversity (divergence of peer \(a\)'s answer from agent \(i\)'s current answer), (ii) peer distinctiveness within the network, (iii) historical performance (empirical success rate), and (iv) interaction round index. This lets the agent distinguish globally under-tested peers from context-locally under-tested ones — finer-grained than scalar UCB. Sufficient statistics \((A_{i,a}, b_{i,a})\) are updated online after each interaction.
Key Contributions¶
- Empirical demonstration that frontier LLMs (Qwen2.5-7B, GPT-4, GPT-5) exhibit bimodal, polarized peer-selection distributions in a two-armed bandit setting — evidence of premature commitment rather than exploration.
- Formal definition of the Multi-Agent Exploration problem as a POSG \(\mathcal{G} = \langle \mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{P}, \mathcal{Q}, \mathcal{R} \rangle\) with per-agent cumulative regret objective.
- MACE framework: contextual bandit decomposition with relational feature design and LinUCB-based optimism for tractable, scalable exploration.
- Theoretical regret gap: MACE achieves \(O(\sqrt{T} \log T)\) cumulative regret; a greedy non-exploring policy incurs \(\Omega(\delta T)\), where \(\delta\) is the capability diversity of the agent pool — formalizing that exploration value grows with specialization.
Results¶
- Two-armed bandit (motivating experiment): UCB concentrates selections toward the better peer across 50 rounds; all LLM agents (Qwen2.5-7B, GPT-4, GPT-5) show bimodal distributions concentrated at 0 and 50 selections, indicating premature lock-in to an arbitrarily chosen peer.
- Contextual diversity (HotpotQA, 10 Qwen2.5-7B agents, 600 hard samples): In-Context Exploration produces highly concentrated per-agent selection matrices (e.g., agent A3 directs ~1405/1500 queries to a single peer); MACE produces near-uniform coverage across all 10 peers, substantially lowering cumulative regret offset vs. the Random baseline.
- Parametric diversity (Math500 Level 4-5 / GPQA Diamond, 4 heterogeneous LLMs): MACE achieves lower cumulative regret offset than Pre-defined and In-Context Exploration in both trial-and-error and exploitation phases; In-Context Exploration frequently underperforms Random peer selection.
- Exploitation phase (frozen MACE parameters): Learned peer-selection strategies transfer to held-out samples, indicating the model captures generalizable relational structure rather than task-specific artifacts.
Limitations¶
- The contextual bandit decomposition treats peer interactions as independent across agents, ignoring joint action effects present in the full POSG formulation.
- The linear reward model \(\mu_{i,a,t} \approx x_{i,a,t}^\top \theta_{i,a}\) may underfit complex, non-linear peer utility functions.
- Experiments use small agent pools (4–10 agents) and short interaction horizons (\(R = 3\)–\(5\) rounds); scalability to large open-world populations is unverified.
- The feature set requires access to peer response embeddings for diversity computation, which may be unavailable in black-box API settings.
- Regret bounds assume stationary capability diversity \(\delta\); the theoretical framework does not fully account for peers' own evolving exploration strategies.
Relevance to Agentic AI / LLM Agents¶
This paper directly targets a fundamental assumption in multi-agent LLM architectures — that agents can self-organize effective collaboration without explicit coordination mechanisms — and shows it empirically fails even in frontier models. The POSG formalization and the contextual bandit reduction provide a rigorous language for reasoning about peer-selection policies in heterogeneous agent networks, which is directly applicable to debate-based reasoning systems, tool-routing agents, and open-agent ecosystems where model capabilities differ. The finding that in-context prompting for exploration underperforms random selection is a concrete warning against relying solely on LLM reasoning for adaptive coordination. The theoretical result tying exploration value to capability diversity \(\delta\) gives practitioners a principled criterion for when to invest in active peer-probing versus fixed communication topologies.