Multi-Agent LLMs Fail to Explore Each Other

The Problem: LLM Agents Get Stuck in Bad Habits

When multiple large language model (LLM) agents work together, they should explore different ways of interacting to find what works best—much like people experimenting with new teammates. Instead, they don't. The authors demonstrate that modern LLM agents converge on narrow, inflexible interaction patterns early and stick with them, even when better strategies exist. This myopic behavior (focusing only on immediate outcomes) and polarization (clustering around a few repeated actions) lead to poor coordination, wasted effort, and higher regret—a measure of how much worse they perform compared to an optimal strategy.

This matters because autonomous multi-agent systems (robots, distributed AI, collaborative tools) need to reliably coordinate. If the agents powering them can't explore their peers' capabilities, they fail to find good working arrangements.

Framing and Solution

The authors formalize this as a Multi-Agent Exploration problem using game theory. They model it as a partially observable stochastic game (POSG), where agents act with incomplete information about what their peers can do. Each agent must actively probe others—try different interaction strategies—to learn their partners' strengths and weaknesses, then adapt accordingly.

To fix this, they propose Multi-Agent Contextual Exploration (MACE), a framework that nudges agents toward exploration through structured peer selection. Rather than letting agents drift toward familiar patterns, MACE explicitly guides which peers each agent should interact with at each step, encouraging encounters that reveal new information about capabilities. The approach is intentionally lightweight—not requiring retraining of the LLMs themselves, just a wrapper that makes the selection process smarter.

Results

Across two settings—one testing contextual diversity (agents with different types of knowledge or expertise) and another testing parametric diversity (agents of different sizes or capabilities)—MACE substantially improves both exploration behavior and final task performance. Agents using MACE don't just wander less; they actually coordinate better and solve tasks more effectively.

The authors also provide theoretical backing: the value of strategic exploration scales with agent diversity. More diverse teams benefit more from active peer probing, which explains why MACE's gains are largest when agents differ.

Why This Matters

Current LLM-based agents are deployed in real systems—from code generation to business automation to robotics—yet they harbor a fundamental gap: they explore their environment and tools fine, but not each other. This work exposes that limitation and offers a practical fix. By showing that simple, structured guidance can unlock exploration in multi-agent LLM systems, the authors make a case for rethinking how we orchestrate agent collaborations. The insight—that exploration value depends on diversity—also suggests design principles for future multi-agent systems: team composition and interaction structures should be chosen with exploration in mind, not just task coverage.