MACE: Why Multi-Agent LLMs Fail to Explore Their Peers

An LLM can describe the exploration–exploitation trade-off correctly and still behave as if the first plausible collaborator it meets is the only one worth consulting.

Multi-Agent LLMs Fail to Explore Each Other isolates this failure. In a 50-round two-peer delegation task, Qwen2.5-7B, GPT-4, and GPT-5 frequently commit to one peer after a few noisy observations and persist even when the inferior peer was selected. The paper formalizes the broader setting as the Multi-Agent Exploration problem and introduces Multi-Agent Contextual Exploration (MACE), a lightweight contextual-bandit routing layer that makes exploration algorithmic rather than rhetorical.

The engineering claim is not simply that more communication improves agents. It is that heterogeneous agent systems require an explicit policy for discovering who is useful under which context, because an LLM prompt alone does not reliably convert uncertainty into sequential exploration.

Failure in the simplest delegation setting

The motivating experiment uses two peers with fixed but unknown success probabilities, pA = 0.6 and pB = 0.5. A selector sees delegation counts and outcomes, then chooses one peer for each of 50 arithmetic questions across 30 runs.

UCB exhibits the expected pattern: it samples both arms under uncertainty and increasingly exploits A. The three LLM selectors instead produce polarized distributions near 0 or 50 selections of A. Some runs converge on the better peer; others lock onto B and rarely recover.

This is a useful diagnostic distinction. The models are not failing to verbalize a bandit strategy. They are failing to execute belief revision over a sequence of locally plausible decisions. Larger capacity does not remove the pattern in this setup.

Formalization and tractable reduction

The full system is modeled as a partially observable stochastic game. Each agent chooses a peer, observes only the solicited response and its own history, and receives a task-dependent reward. Peer capabilities are latent, and the interaction graph evolves from decentralized choices.

Exact finite-horizon POSG planning is intractable, so MACE decomposes joint coordination into independent contextual-bandit decisions. For selector i, candidate peer a, and interaction t, expected reward is approximated by a linear model over a relational feature vector. The reported feature design includes:

1. Response diversity: distance between the peer response and the selector's current answer, used as an information-gain signal.
2. Peer distinctiveness: how different the candidate is from the wider agent population.
3. Historical performance: an exploitation feature derived from prior utility.
4. Interaction round: a phase feature that lets exploration intensity vary through a sample.

Peer selection uses a LinUCB score: estimated reward plus an uncertainty bonus controlled by alpha. The essential design choice is that uncertainty lives in relational feature space. A peer can be sufficiently tested globally but still under-tested for a particular selector, task state, or response geometry.

After an interaction, MACE updates ridge-regression sufficient statistics using a reward that averages task performance and response improvement. This reward definition is operationally important: deployment requires a trustworthy online signal or proxy, not only a routing formula.

Figure 3: selection collapse is visible

Figure 3, PDF page 9. The two original vector panels were vertically combined and converted to WebP without changing the data.

This figure is the clearest behavioral evidence in the paper.

In HotpotQA, ten Qwen2.5-7B agents each receive one of ten disjoint passages: two relevant evidence passages and eight distractors. Which agent holds useful context varies by sample. The In-Context Exploration baseline sees the same historical information available to MACE and is explicitly prompted to balance exploration and exploitation, yet several selector rows concentrate almost entirely on one peer. Some counts exceed 1,400 selections.

In the heterogeneous GPQA pool, the collapse is not explained by shared architecture or context. GPT-5 (A1) selects Qwen-7B (A2) in 294 of 297 interactions while almost never testing the remaining peers. MACE produces substantially broader coverage in both panels.

Broad selection is not universally optimal. In a stable pool with one clearly superior generalist, convergence is rational. Here, however, evidence ownership is randomized in the contextual setting, and early favorites are poorly calibrated in the parametric setting. The heatmaps therefore expose premature commitment rather than disciplined exploitation.

Regret, downstream performance, and transfer

The paper reports regret offset relative to random selection. Under contextual diversity, prompted In-Context Exploration can perform worse than random, while MACE improves regret during trial-and-error and retains its advantage after learned parameters are frozen for exploitation.

Round-wise task metrics support the routing result:

• HotpotQA MACE exploration mean EM rises from 0.1497 at round 0 to 0.3133 at round 5; F1 rises from 0.1923 to 0.3941.
• Math500 mean accuracy rises from 0.4027 to 0.6450 in trial-and-error and from 0.4237 to 0.6832 in exploitation.
• GPQA mean accuracy rises from 0.3359 to 0.5404 in trial-and-error and from 0.3283 to 0.5758 in exploitation.

The HotpotQA parameters are also transferred to 2WikiMultihopQA with no task-specific MACE training. MACE runs only in frozen exploitation mode, while other adaptive baselines receive a 300-sample exploration subset, yet it still produces the best reported regret trajectory. This is evidence that the learned relational policy captures some transferable structure, although it is transfer within a closely related multi-hop QA construction rather than across arbitrary agent domains.

Table 17: structured exploration still helps strong models

Table 17, PDF page 42, cropped with its caption and format-converted; higher is better.

This table is the most deployment-relevant quantitative result because it tests whether exploration remains useful when every peer is comparatively strong.

For GPT-5, GPT-4, GPT-5.4-mini, and GPT-5.4-nano on GPQA:

• Trial-and-error final-round mean: 0.7475 with MACE versus 0.7273 with In-Context Exploration.
• Exploitation final-round mean: 0.7652 with MACE versus 0.7222 with In-Context Exploration.

The exploitation difference is +0.043 absolute. The corresponding regret separation is smaller than in more heterogeneous pools, consistent with the paper's diversity theory, but downstream accuracy still improves. Structured exploration may therefore improve information flow even when its main function is not merely avoiding a weak model.

The result remains a point estimate on a bounded experimental split. The table does not provide confidence intervals, significance tests, cost, latency, or token overhead for the additional coordination.

Theory: diversity determines the value of exploration

The paper defines capability diversity delta as the mean distance between each agent's latent capability vector and the population mean. Under its linear realizability, bounded-feature, confidence, and task-distribution assumptions:

• MACE receives a high-probability sublinear regret bound proportional to the square root of T times logarithmic factors.
• A greedy non-exploring policy receives a lower bound proportional to delta times T.
• Their regret gap therefore grows asymptotically with capability diversity.

The intuition is sound and practically useful. If agents are interchangeable, selecting the wrong peer has little cost. If agents specialize, the opportunity cost of repeatedly routing to the wrong collaborator accumulates linearly.

The formal result should not be treated as a universal guarantee for deployed LLM societies. Real peer behavior can be non-stationary, strategic, adversarial, or only partially captured by a linear feature map. The theory establishes a mechanism under explicit assumptions; it does not close the gap between a contextual-bandit approximation and the full POSG.

Production implications

A MACE-inspired router should expose more than top-1 peer accuracy. Useful observability includes:

• peer coverage and selection entropy;
• time-to-first-contact for specialized agents;
• premature-lock-in rate after early success or failure;
• uncertainty calibration by task context;
• reward delay, missingness, and verifier disagreement;
• frozen-policy performance after exploration;
• routing cost, latency, and communication volume;
• collusion, correlated-error, and failure-propagation indicators.

A conservative deployment path can begin without reproducing the entire paper:

1. Enforce minimum cold-start coverage before allowing hard convergence.
2. Keep empirical utility and uncertainty as separate terms.
3. Condition peer capability on task features instead of maintaining a single global ranking.
4. Decay stale evidence and trigger re-exploration when models, tools, or contexts change.
5. Add routing logs and human override for high-stakes actions.
6. Treat the reward model or verifier as part of the safety boundary; a corrupt reward can systematically route the entire network toward a harmful peer.

Limitations and broader safety boundary

The experiments use small-to-medium populations: ten agents in contextual diversity and four in parametric diversity. The paper does not empirically establish behavior for hundreds or thousands of agents, where the action space, communication bottlenecks, delayed feedback, simultaneous updates, and non-stationarity become qualitatively harder.

The reward requires task performance and improvement signals that may not be available online. Proxy rewards can create routing bias. The experiments also do not establish robustness to adversarial peers that manipulate their apparent distinctiveness, produce strategically novel responses, or collude to attract traffic.

Better peer discovery is dual-use. It can improve scientific teams, digital workforces, education, and distributed tool systems; it can also improve scalable manipulation, collusion, and opaque collective action. Human oversight, controllable communication policies, audit trails, and fairness-aware objectives are not optional add-ons to high-performance coordination.

Conclusion

MACE identifies an important mismatch between declarative reasoning and sequential control. Current LLMs can discuss uncertainty while still collapsing onto an early favorite. Prompting the model to explore does not reliably repair that behavior and can underperform random routing.

The paper's core contribution is therefore architectural: treat peer selection as a learned, uncertainty-aware control problem rather than another paragraph in the system prompt. Its strongest lesson is simple: agent diversity is not automatically collective intelligence. Diversity becomes useful only when the system can discover, revisit, and route to the right differences.

Source

• Hyeong Kyu Choi et al., Multi-Agent LLMs Fail to Explore Each Other, arXiv:2607.11250v1, 13 July 2026.
• Figure 3 and Table 17 are reproduced from the paper with layout/crop and format conversion only.