acceptodds
Under review as a conference paper at ICLR 2027

Do Multi-Agent LLMs Explore Each Other?

14 views

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 often fail to do so, 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), 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, exploration behavior and downstream task performance substantially improve when MACE is applied. We further provide theoretical insight that MACE achieves a sublinear expected-regret bound. 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 for reproducible research.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Multi Agent LLMs, Exploration, Multi-Agent Exploration

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_NPXXOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines whether LLM agents effectively explore potential collaborators in multi-agent interactions. A controlled two-armed delegation experiment reveals frequent premature commitment in LLM-based peer selection. The authors formulate multi-agent exploration as a partially observable stochastic game and propose Multi-Agent Contextual Exploration (MACE), which uses LinUCB with relational features to guide peer selection. Experiments on HotpotQA, Math500, and GPQA, together with a cross-benchmark transfer evaluation, report improvements over in-context, random, and fixed peer selection; the paper also provides regret guarantees under linear-bandit assumptions.

Critical strengths
  1. The two-armed delegation study and peer-selection distributions highlight premature commitment in LLM-based collaboration. This is an important failure mode for systems that rely on agents to identify useful peers through interaction.

  2. MACE improves peer selection and downstream performance under both contextual and model heterogeneity. Frozen-parameter evaluation, transfer to 2WikiMultihopQA, and additional appendix analyses provide useful evidence beyond the initial experiments.

Critical weaknesses
  1. MACE builds on the well-established LinUCB algorithm, while the main experiments primarily compare against random selection, fixed communication, and LLM-based peer selection. Although the paper includes additional UCB experiments in the appendix, a direct comparison with standard exploration algorithms on the main benchmarks is still missing.

  2. The experiments mainly focus on question-answering tasks with a fixed number of agents and relatively few interaction rounds. While these settings provide useful evidence, they do not fully demonstrate whether MACE remains effective in more dynamic environments where agent capabilities or task requirements change over time.

Questions for authors
  1. Could the authors compare MACE with standard exploration algorithms, such as UCB or LinUCB, on the main benchmarks to better demonstrate its advantages?

  2. The feature ablations in Appendix D.6 are useful, but could the authors further clarify how much of MACE's improvement comes from the explicit exploration mechanism versus the proposed relational features?

  3. Would MACE remain effective in more dynamic multi-agent settings, where peer capabilities or task requirements change over time?

2 comments
Reviewer_NPXXOpenReview ↗

I stand by my score, I support the publication of your paper.

Thank you for addressing my questions. I continue to support your paper, and I hope you achieve a great outcome.

Dear Reviewer NPXX,

We really appreciate your support for our paper! Please let us know if, by any chance, you have any additional questions. Thank you very much!

Best,

The Authors

Reviewer_5NTJOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies premature commitment in peer selection among LLM agents. It proposes MACE, a LinUCB-based selector that uses response-diversity and interaction-history features to balance exploration and exploitation. Experiments evaluate peer selection and answer quality under contextual and model heterogeneity, including cross-task transfer.

Critical strengths
  • The paper identifies premature commitment as a relevant failure mode in multi-agent collaboration, providing a useful empirical diagnosis.
  • MACE improves task performance in both the main experiments and the transfer experiment.
Critical weaknesses
  • Methodological novelty is limited. LinUCB-based LLM and agent selection already exists [1, 2]. MACE mainly contributes a relational feature design and its application to peer interaction.
  • Simple bandit baselines are absent from the main multi-agent tasks. The two-arm UCB controls and feature ablations do not establish MACE's advantage over simpler selectors under matched feedback and interaction budgets.
  • The transfer feedback protocol is unclear. Linear parameters are frozen, but whether reward-derived historical features are also frozen is unspecified. It is therefore unclear whether transfer still uses target-task feedback.

References:
[1] Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution
[2] Symphony-Coord: Adaptive Routing for Multi-Agent LLM Systems

Questions for authors

see weaknesses

2 comments

Dear Reviewer 5NTJ,

Thank you again for taking the time and effort to review our paper! A quick reminder: the discussion period closes this Wednesday, November 18. If you have any remaining questions, we'd be happy to address them before the deadline!

Best regards,

The Authors

Dear Reviewer 5NTJ,

We are glad that most of your concerns have been resolved!

We would like to respectfully note that the central contribution of this work is to identify and formally characterize a previously overlooked problem in multi-agent LLM systems. That said, the proposed method is more of a functional tool that helps demonstrate this problem and how it can be addressed.

Thank you again for your time and thoughtful engagement with our work!

Best,

The Authors

Reviewer_LSBCOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates premature commitment in LLM peer selection and proposes MACE, which applies disjoint LinUCB to relational features of candidate interactions. Experiments consider contextual and model-capability heterogeneity, frozen-selector exploitation, and cross-benchmark transfer. A simplified linear-bandit analysis contrasts optimistic exploration with empirical-mean greedy selection.

Critical strengths
  1. Peer-selection failures are relevant to practical multi-agent systems, and the controlled delegation study makes the failure mode easy to inspect.
  2. The experiments go beyond a single setting. On held-out HotpotQA samples, final-round F1 is 0.3415 for MACE, 0.3001 for In-Context Exploration, and 0.3053 for Random (Tables 2, 3, and 5).
  3. The proposed MACE is straightforward and easy-to-follow. The paper is easy-to-understand.
Critical weaknesses

Heterogeneity type is confounded with benchmark choice.

Contextual diversity is primarily evaluated on HotpotQA, whereas parametric diversity is evaluated on Math500 and GPQA. Agent counts and interaction rounds also differ between these settings. Consequently, differences in peer-selection behavior or feature importance cannot be cleanly attributed to the source of heterogeneity. The homogeneous-model experiment in Appendix D.4 provides a useful partial control, but does not disentangle contextual and parametric heterogeneity. A controlled evaluation on one benchmark, varying model heterogeneity and context allocation independently while fixing agent counts and interaction budgets, would substantially strengthen the mechanistic and generalization claims.

The contextual-bandit objective may not fully address the sequential interaction problem motivating the paper.

The motivation emphasizes that querying a peer changes subsequent responses, information propagation, and future coordination. However, the main MACE algorithm learns from immediate interaction rewards. Its uncertainty bonus supports learning the reward model, but does not explicitly value a query for how it changes future interaction states.

For example, a peer may reveal an intermediate entity that does not immediately improve answer correctness but enables a second peer’s evidence to resolve the question. A one-step reward predictor may undervalue this first interaction relative to a peer offering an immediately plausible answer. Although the uncertainty bonus can encourage trying the informative peer, it does not explicitly assign credit for the downstream benefit enabled by that query. This illustrates the gap between exploring an unknown reward model and planning interactions that change future information states.

Inconsistent metric definition.

It seems the definitions of cumulative regret offset of Fig. 4 in Sec. 5.3 and Appendix C2 are not consistent.

Questions for authors

The interaction counts in Figure 3(b) may need clarification. For selector A1, the In-Context Exploration counts sum to 297 (2 + 294 + 0 + 1), whereas the MACE counts sum to 222 (43 + 63 + 66 + 50). The other MACE rows also sum to 222. However, Appendix C.1 specifies 99 GPQA examples with three interaction rounds per evaluation phase, corresponding to 297 selections per agent. Were different task subsets or interaction budgets used, or is this a plotting/reporting error? Please clarify the evaluation population and report normalized selection frequencies together with the total counts. Without this information, the comparability of the raw-count heatmaps is unclear.

5 comments

Dear Reviewer LSBC,

Thank you again for taking the time and effort to review our paper! A quick reminder: the discussion period closes this Wednesday, November 18. If you have any remaining questions, we'd be happy to address them before the deadline!

Best regards,

The Authors

Reviewer_LSBCOpenReview ↗

Thanks for the rebuttal.

Thank you for the additional controlled experiments. However, the effects of model heterogeneity and contextual heterogeneity are still not fully disentangled.

In the new experiments, the contextual-diversity setting uses identical models with different contexts, while the parametric-diversity setting uses different models with the same context. Thus, the two factors are not independently varied.

I suggest adding one additional control experiment using homogeneous models with identical contexts.

This would allow two controlled comparisons with the existing experiments: (1) homogeneous vs. heterogeneous contexts under identical models, and (2) homogeneous vs. heterogeneous models under identical contexts.

Thank you for the follow-up question! Below, we provide two comparisons (1) homogeneous vs heterogeneous context, and (2) homogeneous vs heterogeneous models.


(1) Homogeneous vs Heterogeneous context

In this setup, four identical Qwen2.5-7B-Instruct agents are provided with identical contexts. To match each agent's marginal probability of receiving gold evidence in our heterogeneous-context experiment, all agents jointly receive the correct supporting context with probability 0.25 and a wrong distractor context with probability 0.75.

HomogeneousTrial-and-error F1Trial-and-error EMExploitation F1Exploitation EM
Pre-defined26.1619.6730.3224.00
Random26.6320.2530.8724.50
In-Context Exploration26.6620.3330.3523.92
MACE26.2919.9231.2024.67
Heterogeneous ContextTrial-and-error F1Trial-and-error EMExploitation F1Exploitation EM
Pre-defined50.5439.8350.7541.83
Random43.8135.4244.7236.00
In-Context Exploration38.2930.0837.5029.92
MACE (Ours)50.9140.6751.3942.17

Peer-selection methods perform similarly when both models and contexts are homogeneous. This suggests limited benefit from adaptive selection when peers offer little complementary information. With heterogeneous contexts, on the other hand, MACE achieves the highest scores across both phases. These results are consistent with the benefit of selecting informative peers when complementary evidence is distributed across agents.


(2) Homogeneous vs Heterogeneous Models

In the homogeneous-model setup, four identical Qwen2.5-7B-Instruct agents receive the same correct supporting context. This matches the context conditions of our original heterogeneous-model experiment.

HomogeneousTrial-and-error F1Trial-and-error EMExploitation F1Exploitation EM
Pre-defined76.3760.3375.9361.33
Random75.7759.7575.9162.17
In-Context Exploration76.1760.5875.2261.50
MACE75.7659.8375.8662.17
Heterogeneous ModelsTrial-and-Error F1Trial-and-Error EMExploitation F1Exploitation EM
Pre-defined73.9356.2571.0854.17
Random74.3457.5870.8055.17
In-Context Exploration74.1757.4271.1654.33
MACE (Ours)75.8958.5872.9956.83

MACE's advantage over the baselines is more consistent with heterogeneous models. In the homogeneous setup, all methods achieve similar performance without a certain method consistently winning over another. With heterogeneous models, MACE consistently outperforms all baselines across both phases. This pattern suggests that adaptive peer selection is more beneficial when agents differ in their capabilities and the information their responses provide.


We hope this addresses your remaining question. Thank you very much!

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.