PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent LLMs Fail to Explore Each Other

Hyeong Kyu Choi, Jiatong Li, Wendi Li, Xin Eric Wang, Sharon Li

arXiv:2607.11250v1cs.MAcs.AI

TL;DR

LLM agents may fail to explore peers effectively under uncertainty, limiting reliable multi-agent autonomy. The paper introduces MACE, which uses structured peer selection to promote exploration and improves exploration and downstream performance across diverse settings.

  • Problem

    It remains unclear whether LLM agents can balance exploration and exploitation when selecting heterogeneous peers under partial observability.

  • Method

    MACE decomposes multi-agent exploration into contextual-bandit peer selection using relational features and explicit uncertainty bonuses.

  • Results

    Across diverse settings, MACE improves exploration and downstream performance, with gains persisting during exploitation and transferring to unseen tasks.

  • Takeaways & Limitations

    Reliable multi-agent autonomy may require explicit exploration rather than relying on exploration to emerge from LLM agents alone.

  • Takeaways & Limitations

    Experiments focus on small- to medium-scale systems and do not empirically establish MACE’s behavior in very large agent populations.

Abstract

from arXiv · show

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

1. Introduction

The introduction frames exploration as foundational to reliable autonomy and especially necessary in multi-agent settings, where agents must probe heterogeneous peers. It identifies current LLM agents’ weak exploration and presents MACE as an explicitly guided, contextual-bandit framework whose benefits grow with agent diversity.

  • Exploration is foundational to autonomous behavior because agents self-generate goals, discover novel states, and acquire reusable strategies without external guidance.
  • In multi-agent environments, agents must proactively explore heterogeneous peers to identify collaborators, uncover complementary information, and adapt to evolving interactions.
  • Current LLM agents fail to explore effectively even in a controlled two-armed bandit, rather than accumulating evidence and converging on the superior peer.
  • The multi-agent exploration problem requires strategically probing adaptive peers whose capabilities or contextual information differ, unlike stationary arms in standard bandits.
  • MACE decomposes this intractable joint problem into independent sequential decisions under contextual bandits, using explicit algorithmic guidance for exploratory peer selection.
  • MACE outperforms existing baselines across contextual and capability diversity, while prompting-only exploration can underperform random peer selection; exploration benefits increase with agent diversity.

2. Can LLMs Explore in Multi-Agent Environments? A Motivating Example

The section frames multi-agent exploration as the need to probe uncertain peers while balancing exploration and exploitation. In a two-peer delegation bandit, LLM agents instead commit prematurely, often locking onto the inferior peer.

  • Motivation: Reliable multi-agent autonomy requires agents to probe their environment for better strategies and collaborators while deciding which uncertain peers to trust.The central uncertainty concerns peers’ capabilities and the appropriate balance between exploration and exploitation.
  • Bandit setup: Agents repeatedly delegate arithmetic questions to peer A or B, whose fixed but unknown correctness probabilities provide evidence for choosing between testing and committing.At each round, the agent observes historical performance and delegation counts before selecting a peer.
  • Evaluation: The evaluation compares Qwen2.5-7B-Instruct, GPT-4, and GPT-5 with Upper Confidence Bound as a classical behavioral reference.Peer selection is based purely on in-context running histories presented at each round.
  • Behavioral reference: UCB predominantly selects peer A while occasionally exploring peer B, producing the desired pattern of exploration followed by consistent preference.Figure 1 summarizes peer A selection across 30 independent runs of T=50 delegation rounds.
  • LLM behavior: All LLM agents produce polarized bimodal selection distributions, concentrating near 0 or 50 peer A selections and revealing premature commitment.The mass near 0 indicates frequent runs in which agents lock onto the inferior peer and never reconsider.

3. The Multi-Agent Exploration Problem: A Formalization

The paper formalizes multi-agent exploration as decentralized peer selection under partial observability, latent heterogeneous capabilities, and dynamically evolving interactions. Agents must balance probing diverse peers to reduce uncertainty and regret against exploiting peers expected to yield high rewards.

  • 3.1. Problem Formalization: The system contains 𝒩={1,...,𝑁} agents interacting over 𝑇 timesteps to solve a sequence of tasks.
  • 3.1. Problem Formalization: Agent capabilities differ across model families or available contexts, remain latent, and become partially observable through direct interactions.
  • 3.1. Problem Formalization: The process is modeled as a Partially Observable Stochastic Game in which latent states encode task information and unknown agent capabilities.
  • 3.1. Problem Formalization: At each round, every agent selects a peer to interact with, making joint decisions that determine the system-level interaction structure.
  • 3.1. Problem Formalization: Interaction decisions propagate information through a transition function, inducing a dynamically evolving graph whose topology depends on agent actions.
  • 3.1. Problem Formalization: Agents receive queried peers’ responses and accumulated interaction histories, then act without access to the full state.
  • 3.1. Problem Formalization: Rewards reflect task performance, including answer correctness, performance gains, or the utility of intermediate responses.
  • 3.2. Regret: Effective policies must balance exploring diverse peers to estimate capabilities and reduce uncertainty and regret against exploiting peers expected to yield high rewards.

4. Multi-Agent Contextual Exploration (MACE)

MACE makes multi-agent exploration tractable by decomposing peer selection into contextual bandit problems and explicitly encouraging exploration. It combines relational features, optimism-based selection, and rewards reflecting both performance and improvement.

  • Framework: Finite-horizon POSG exploration is NEXP-hard because agents must infer adaptive peer capabilities from sparse, noisy interaction histories.MACE addresses this challenge with a tractable, lightweight framework that decomposes the joint problem into independent components.
  • Contextual bandit formulation: MACE models each agent’s peer selection as a contextual multi-armed bandit, with querying peer a at round t treated as pulling an arm.The expected reward is represented as a linear function of interaction context features and corresponding weight vectors.
  • Relational feature design: Relational features capture response diversity, peer distinctiveness, historical performance, and interaction round to balance information gain, exploitation, and time-varying exploration.Response diversity encodes potential information gain, while historical performance provides an exploitation signal.
  • Exploration via optimism: LinUCB selects peers using estimated reward plus an uncertainty bonus, encouraging exploration over relational contexts rather than raw selection counts.This lets agents distinguish peers under-tested globally from peers under-tested in the current relational context.
  • Sufficient statistic updates: After each interaction, the reward averages performance and response improvement, then updates sufficient statistics for recomputing the parameter estimate.The reward therefore reflects both the agent’s performance and the magnitude of improvement after incorporating information from the selected peer.

5. Experiments

Experiments evaluate multi-agent exploration under contextual and parametric diversity, showing that LLM agents often explore insufficiently while MACE produces more distributed peer selection, improves regret, and transfers to an unseen task.

  • Experimental settings: Experiments consider contextual diversity, where agents have different and potentially misleading context, and parametric diversity, where agents differ in intrinsic reasoning ability.The parametric setup uses four heterogeneous LLM types: GPT-5, Qwen2.5-7B-Instruct, Llama3.1-8B-Instruct, and Mistral-7B-v0.3.
  • Exploration behavior: In-Context Exploration produces highly concentrated peer-selection patterns, often locking onto one peer, whereas MACE induces substantially more distributed selections.Under contextual diversity, the relevant context is randomized across samples and interaction rounds, making persistent selection of one peer a failure to explore.
  • Regret and performance: In-Context Exploration can perform worse than Random peer selection under contextual diversity, while MACE substantially improves performance through guided exploration.The comparison uses cumulative regret offset relative to the Random baseline, with lower values indicating better performance.
  • Generalization: MACE transfers parameters learned on HotpotQA to the more challenging 2WikiMultihopQA benchmark and achieves robust performance that outperforms all other baselines.MACE operates purely in exploitation mode with frozen parameters on the unseen benchmark, while other baselines explore on a 300-sample subset.

6. Theoretical Analysis

The theoretical analysis formalizes why explicit exploration benefits multi-agent coordination: MACE has sublinear regret, whereas non-exploring policies incur linear regret. The benefit grows with capability diversity and is consistent with empirical behavior.

  • Regret guarantees: Theorem 1 establishes that MACE achieves sublinear cumulative regret under mild assumptions when its exploration coefficient α is positive.The guarantee applies over T interaction rounds with high probability.
  • Regret guarantees: Theorem 2 shows that a greedy non-exploring policy incurs cumulative regret growing linearly with the number of interaction rounds.The policy selects peers by maximizing estimated reward without an exploration bonus.
  • Capability diversity: Capability diversity δ measures agents’ average deviation from the pool mean and determines the failure rate of non-exploring policies and the benefit of exploration.High δ corresponds to specialized agents and greater cost from selecting the wrong peer, whereas δ≈0 indicates approximately interchangeable agents.
  • Exploration benefit: The regret gap between non-exploring policies and MACE scales as Ω(δT), because non-exploring regret is linear in T while MACE’s regret grows as √T log T.When δ≈0, exploration may have limited performance impact; when δ≫0, its value increases.
  • Empirical validation: Figure 6 compares the theoretical regret bounds and shows that Qwen2.5-7B-Instruct with MACE follows a trend closely matching the theoretical prediction.The figure contrasts MACE’s upper regret bound with the lower regret bound of non-exploring policies.

7. Related Works

Related work spans autonomous multi-agent system overviews, coordination infrastructures, and methods for granting agents autonomy. Adjacent research examines single-agent exploration and delegation under uncertainty, motivating the study of exploration among interacting LLM agents.

  • Autonomous multi-agent overview: Recent overviews organize autonomous multi-agent systems around agent profiling, communication structure, collaboration protocols, and system evolution.They describe a shift from isolated single-agent prompting toward coordinated groups that divide roles, exchange information, and jointly plan or act.
  • Frameworks for multi-agent coordination: General-purpose coordination frameworks include CAMEL, AutoGen, ChatDev, MetaGPT, and AgentScope, spanning role-playing, programmable conversation, and multi-agent orchestration.CAMEL introduced role-playing communicative agents, while AutoGen modeled interaction among agents, humans, and tools.
  • Granting Autonomy to Multi-Agent LLM Systems: Research on multi-agent autonomy studies autonomous communication, role design and assignment, dynamic orchestration, and recruiting sub-agents for task solving.Examples include iAgents, HALO, Puppeteer, MegaAgent, and AgentVerse, alongside domain-specific autonomy and taxonomy work.
  • Single-agent LLM exploration capabilities: Single-agent exploration studies find robust exploration rare in LLMs, while explicit algorithmic support, distillation, and fine-tuning can improve exploratory behavior.These findings come from in-context bandit studies and a benchmark suite for measuring LLM exploration.
  • Delegation, trust, and adjacent capabilities for exploration: Adjacent delegation research models reliance under uncertainty as adaptive decisions over task allocation, authority transfer, and trust.It emphasizes judging when another agent is worth relying on in autonomous delegation.

8. Conclusion · Appendix · A. Appendix for the Delegation Experiment

The paper finds that LLM agents often explore poorly in multi-agent environments, causing premature commitment, poor peer selection, and higher regret. It formalizes this failure as the Multi-Agent Exploration problem and introduces MACE to improve exploration and downstream performance through structured peer selection.

  • 8. Conclusion: LLM agents often fail to explore effectively in multi-agent environments.
  • 8. Conclusion: This failure leads to premature commitment, poor peer selection, and higher regret.
  • 8. Conclusion: The work formalizes ineffective multi-agent exploration as the Multi-Agent Exploration problem.
  • 8. Conclusion: MACE is introduced as a lightweight framework for explicitly inducing exploration.
  • 8. Conclusion: MACE induces exploration through structured peer selection.
  • 8. Conclusion: Across diverse settings, MACE improves both exploration and downstream performance.

A.1. Experimental Setup … C. Appendix for the Main Experiments

The experiments use delegated arithmetic questions and compare LLM delegation behavior with UCB1, while MACE represents peer relationships, rewards interaction quality, and updates a contextual policy. Across the appendix, the results show polarized LLM selection patterns and specify the implementation details underlying MACE and the main experiments.

  • A.1. Experimental Setup: Delegated questions are randomly generated integer arithmetic expressions using addition, subtraction, and multiplication over [1, 100].A selected peer answers correctly with probability p_i and incorrectly otherwise.
  • A.1. Experimental Setup: LLM agents receive the current question and Peer A/B performance histories, with prompts explicitly balancing exploitation against exploration.The history includes prior delegations, correct responses, and empirical success rates.
  • A.1. Experimental Setup: UCB1 provides the exploration baseline, using empirical success rates, confidence bonuses, c = 1.0, and one initial selection of each peer.Its exploitation and exploration terms respectively favor high-performing and under-sampled peers.
  • A.2. Histograms for All 𝑝A Values: All three LLMs produce polarized delegation distributions near 0 or 50 selections, unlike UCB’s smooth distributions near the optimal allocation.The comparison spans the complete histogram set across tested p_A values.
  • A.2. Histograms for All 𝑝A Values: Qwen2.5-7B-Instruct often allocates nearly all selections to Peer A even when p_A = 0.1 and p_B = 0.5, while GPT-5 explores comparatively more broadly.The Qwen behavior is attributed to overreaction to noisy early outcomes and failure to recover through continued exploration.
  • B.1. Feature Design: MACE uses compact relational features combining response diversity, peer distinctiveness, historical performance, normalized interaction round, and a bias term.Features are normalized before use by the bandit or value-based policy.
  • B.2. Reward Function: MACE’s blended reward combines response improvement with absolute post-interaction quality, crediting both gains and high-quality final responses.This avoids assigning zero reward when an already-correct answer remains correct.
  • B.3. Algorithm / C. Appendix for the Main Experiments: Algorithm 1 specifies MACE’s contextual-bandit procedure with T = |𝒬| × R and λ = 1.0, alongside appendix documentation of datasets, backbones, and prompts.The pseudocode initializes per-agent-pair matrices, vectors, counts, mean rewards, and the interaction step.

C.1. Dataset Details … D.2. Sensitivity Analysis of Exploration Coefficient 𝛼

The paper evaluates MACE across contextual and parametric agent diversity using multiple benchmarks, model configurations, and prompt protocols. Further analyses show that MACE improves round-wise performance and transfer, while its exploration coefficient requires balancing insufficient and excessive exploration.

  • C.1. Dataset Details: Agents differ through contextual diversity, where they observe different task-relevant information, or parametric diversity, where model family and scale vary.Contextual-diversity agents share a backbone but receive different context; parametric-diversity agents differ in reasoning capabilities.
  • C.2. Backbone Model Details: Contextual-diversity experiments use ten independently decoded Qwen2.5-7B-Instruct agents with temperature 1.2 and top_p=0.95.Parametric-diversity experiments use GPT-5, Qwen2.5-7B-Instruct, Llama3.1-8B-Instruct, and Mistral-7B-v0.3 with specified decoding settings.
  • C.3. Resources: Contextual-diversity experiments run on one NVIDIA RTX A6000 GPU, while parametric-diversity experiments use three NVIDIA RTX A6000 GPUs and Azure API calls for GPT-5.The resource allocation differs by heterogeneity setting.
  • C.4. Prompt Templates: Prompt protocols require concise tagged answers, dataset-specific reasoning formats, and interaction responses that review and selectively incorporate a chosen peer’s response.Math500 uses boxed answers, whereas GPQA uses answer labels.
  • C.4. Prompt Templates: Peer selection exposes historical choices, rewards, diversity, centrality, and related features, with invalid outputs falling back to the pre-defined neighboring-peer protocol.The selector asks agents to return only an agent number or choose themselves.
  • D.1. Round-wise Performance: MACE consistently improves task performance across interaction rounds on all three benchmarks and outperforms baselines when transferring exploration to 2WikiMultihopQA.The results indicate that learned exploration improves progressively and transfers beyond HotpotQA.
  • D.2. Sensitivity Analysis of Exploration Coefficient 𝛼: MACE’s exploration coefficient α controls the LinUCB uncertainty bonus, and both insufficient and excessive exploration worsen regret behavior.At α=0.1, the policy becomes effectively greedy, prematurely committing to peers from noisy early observations and performing worse than the random baseline.

D.3. Experiments on Stronger LLMs … E.2. Proof of Theorem 1

Across stronger, homogeneous, and temporal-difference settings, MACE improves downstream performance or interaction coverage despite limited regret advantages. Feature analyses and theory explain peer selection through diversity-sensitive exploration, confidence bounds, and regret guarantees.

  • D.3. Experiments on Stronger LLMs: On stronger LLMs, MACE achieves best final-round mean accuracy of 0.7475 in Trial-and-Error and 0.7652 in Exploitation, versus 0.7273 and 0.7222 for In-Context Exploration.MACE and In-Context Exploration show broadly similar cumulative regret trends because comparable capabilities reduce the benefit of identifying the best peer.
  • D.4. Fully Homogeneous Agent Setup: In the fully homogeneous Qwen2.5-7B-Instruct setup, MACE attains final-round mean accuracy of 0.4779 in Trial-and-Error and 0.5053 in Exploitation, exceeding both baselines.Capability diversity is effectively zero, and cumulative regret differences are much less pronounced, but structured exploration still yields small consistent performance gains.
  • D.5. MACE-TD: A Temporal-Difference Extension: MACE-TD models delayed interaction benefits with temporal-difference targets and gamma set to 0.9, while retaining MACE’s optimistic uncertainty-bonus action selection.It accounts for how early peer queries can improve later information states and decisions.
  • D.5. MACE-TD: A Temporal-Difference Extension: MACE-TD produces higher peer selection coverage than In-Context Exploration and encourages specialization across peer subsets, but offers no consistent cumulative-regret advantage over MACE.On GPQA, MACE-TD accumulates noticeably higher regret, suggesting instability when rewards are sparse or noisy.
  • D.6. Feature Importance: MACE assigns broadly positive weights to n-gram-based diversity features, favoring peers whose responses differ from the agent’s own response.Distinctiveness features are close to zero in contextual diversity, where response differences may reflect passage access rather than reliability.
  • E.1. Assumptions: The theoretical analysis assumes bounded features and parameters, sub-Gaussian reward noise, and capability diversity that lower-bounds the expected penalty for selecting a suboptimal peer.Under these assumptions, greater specialization makes choosing the wrong peer more costly.
  • E.2. Proof of Theorem 1: Theorem 1 follows by constructing ridge-regression confidence sets, applying the UCB selection rule, bounding instantaneous regret, and summing with the elliptical potential lemma.The proof applies concentration uniformly across candidate peers and interaction rounds.

E.3. Proof of Theorem 2 · Regret𝑖=∑︁Δ𝑖,𝑎𝑁𝑖,𝑎, · E.4. Discussion

The proof shows that noisy initial estimates can cause greedy policies to commit permanently to suboptimal peers, producing linear regret with constant probability. The discussion contrasts this with MACE’s sublinear regret and explains that exploration becomes more valuable as agent capability diversity increases.

  • E.3. Proof of Theorem 2: With probability at least ρ > 0, noisy finite observations initially rank a suboptimal peer above the optimal peer.This establishes the stochastic event underlying the lower-bound argument.
  • E.3. Proof of Theorem 2: On this misranking event, the greedy policy selects peer b and lacks corrective observations from the unselected optimal peer a⋆ᵢ.The absence of explicit exploration prevents the policy from revising its initial ranking.
  • E.3. Proof of Theorem 2: The persistent misranking makes the policy select b for all T rounds.Because the policy never probes the optimal peer, the initial error persists throughout the interaction horizon.
  • Regret𝑖=∑︁Δ𝑖,𝑎𝑁𝑖,𝑎,: The regret decomposition converts these repeated suboptimal selections into the theorem’s regret bound.The proof explicitly invokes the standard regret decomposition before concluding the lower bound.
  • Regret𝑖=∑︁Δ𝑖,𝑎𝑁𝑖,𝑎,: With constant probability, the non-exploring greedy policy incurs a linear regret bound.This is the proof’s central conclusion for policies without exploration.
  • E.4. Discussion: MACE achieves sublinear regret in the number of interaction rounds.Theorem 1 provides the contrasting guarantee for the exploration-guided method.
  • E.4. Discussion: MACE’s average regret per round vanishes as T grows, whereas greedy non-exploration can incur regret linear in T after premature commitment.The contrast links asymptotic average performance to the failure mode established by Theorem 2.
  • E.4. Discussion: When capability diversity δ is small, peers are nearly interchangeable and explicit exploration offers limited benefit; when δ is large, exploration becomes more valuable.Large δ corresponds to specialized agents and more consequential peer selection, increasing the regret gap.

F. Limitations and Future Directions · G. Broader Impact

The study leaves MACE’s behavior in very large multi-agent populations empirically unestablished and identifies scalability challenges for future work. It also frames socially reliable multi-agent systems as promising but requiring governance, safety mechanisms, and human oversight to manage collective risks.

  • F. Limitations and Future Directions: F. Limitations and Future Directions: Experiments cover small- to medium-scale systems, leaving MACE’s behavior in very large populations empirically unestablished.The untested regime includes swarm-like settings with hundreds or thousands of agents.
  • F. Limitations and Future Directions: F. Limitations and Future Directions: Large-N deployments may face communication bottlenecks, delayed or partial feedback, expanding interaction spaces, and stronger non-stationarity.These challenges arise from many simultaneous agent updates.
  • F. Limitations and Future Directions: F. Limitations and Future Directions: Future work should develop scalable MACE variants and examine whether explicit exploration produces specialization, robust collective behavior, and self-organizing coordination.The proposed investigation targets massive agent populations.
  • G. Broader Impact: G. Broader Impact: Multi-agent AI may increasingly communicate, delegate, negotiate, and coordinate with one another while operating alongside humans.The paper identifies integration into broader social and organizational environments as comparatively underexplored.
  • G. Broader Impact: G. Broader Impact: Socially reliable multi-agent systems could support scientific collaboration, digital workforces, education, healthcare coordination, and public-service decision support.MACE-like methods may help agents discover useful partners, adapt to changing environments, and allocate communication efficiently.
  • G. Broader Impact: G. Broader Impact: Stronger coordination among autonomous agents could enable scalable manipulation, collusion, disinformation campaigns, and opaque collective behavior.These risks may become difficult to monitor as multi-agent capabilities improve.
  • G. Broader Impact: G. Broader Impact: Future coordination research should pair capability advances with controllable communication protocols, fairness-aware objectives, governance, safety mechanisms, and human oversight.The paper presents these safeguards as increasingly important for multi-agent systems.
  • G. Broader Impact: G. Broader Impact: Trustworthy integration of multi-agent AI into real-world social environments may become a central challenge for the next generation of AI.The paper broadens the reliability discussion from individual models to societies of models.
Loading 2607.11250v1…