Zero-Shot Coordination among LLM Agents

AI summary

Overview

Research area: Multi-agent reinforcement learning and LLM agent evaluation, specifically zero-shot coordination (ZSC) — the problem of independently developed agents cooperating at test time without prior communication or retraining.

Technical level: Intermediate. The paper formalises agents as Dec-POMDP policies and assumes some familiarity with reinforcement learning vocabulary (self-play, cross-play, Nash equilibria), but its central argument — that frontier LLMs fail at basic coordination — is presented through small, intuitive games.

Scope: A systematic empirical study of how text-based and code-generating LLM agents perform under zero-shot coordination across nine simplified cooperative environments, plus a proposed remedy ("coordination-friendly definitions") that can be written by hand or discovered automatically.

What This Paper Is About

When two AI systems built by different organisations must cooperate — two autonomous cars at an intersection, or two coding agents from different providers editing the same file — they have never communicated and cannot be retrained together. This is zero-shot coordination, and it is well studied for traditional RL agents but poorly understood for LLM agents. The authors ask whether frontier LLMs coordinate out of the box when given only a textual description of a cooperative game, and if not, why they fail and what could be done about it.

Key Contributions

1. A formalisation and systematic evaluation of LLM agents under ZSC. The authors define two common scaffolds — text agents (prompted each step for an action given a role and observation history) and code agents (prompted once to emit an entire joint policy as executable code) — and evaluate them under three regimes: self-play (SP), fixed-LLM cross-play (XP_seed), and variable-LLM cross-play (XP_LLM).

2. A suite of nine minimal coordination environments, adapted from the ZSC literature (Cat & Dog, Tiny Hanabi, a lever-game variant, the trampoline–tiger challenge, ad-hoc conventions, a narrow tunnel task, Brittle Bridge, Hint–Guess) plus two new ones designed by the authors (the Semantic Selection Game and Semantic Convention Game). Each isolates one specific coordination challenge, and each is annotated with natural-language descriptions so LLM agents can play it.

3. An analysis of semantics as a new coordination axis. Because LLM agents access environments through text, they can exploit the meaning of observations and actions — something traditional RL agents struggle with. The paper shows this cuts both ways: it enables coordination strategies classical algorithms miss, but also creates competing conventions that agents fail to arbitrate between.

4. Coordination-friendly definitions (CFDs). A CFD is a short set of textual instructions encoding general coordination principles that independent developers could agree on in advance, mirroring the ZSC idea of a shared learning rule (and the "constitution" approach in AI safety). The paper shows both a hand-crafted CFD and an automatically meta-learned CFD improve coordination, and releases code at https://github.com/ahayler/zsc-llm-agents.

Main Findings

• Frontier LLMs fail at coordination even in trivial games. In Cat & Dog — where the safe, ZSC-optimal move is to remove the wall for a guaranteed reward of 5, versus gambling on a signalling convention worth 10 — text agents score well below 5. Grok 4.1 Fast and GPT-5.2 show high failure rates in 7/9 tasks. Code agents show a clear self-play-to-cross-play gap, meaning independently generated policies rely on incompatible strategies.

• Reasoning traces reveal confident, incompatible rationalisation. In one recorded episode, Gemini 3 Pro (as Alice) explicitly recognises that any convention is arbitrary, picks one anyway, and then calls it "natural"; GPT-5.2 (as Bob) independently declares the opposite convention "natural" and never considers bailing.

• Text agents induce degenerate local policies. Sampling each agent 100 times from a fixed state: Grok, Ministral, and Qwen3-Max-Thinking turn the light on regardless of the observed animal; Ministral guesses "dog" with high probability whenever the light is on; Qwen3-Max guesses "cat" when the light is on and "dog" otherwise.

• Smaller models sometimes coordinate better. Qwen3-14B and OLMo-3-32B-Think recover the ZSC-optimal policy, while Qwen3-Max-Thinking (~1T parameters) performs significantly worse than its 14B counterpart. For smaller models such as Grok 4.1 Fast and GPT-5 mini, higher reasoning effort correlates with lower coordination performance, because the models hallucinate a shared convention more often. The trend is mixed overall: Claude Opus 5 and Grok 4.5 reveal more with higher effort, and GPT-5.6 Sol reveals far less often than GPT-5.2.

• Semantics shift behaviour arbitrarily. Relabelling "light on/off" as "red/blue light", or translating the whole game into German, changes policies despite identical payoffs. GPT models become more grounded and reveal more often; Qwen3-14B and OLMo-3-32B reveal less, with Qwen3-14B increasingly bailing as Alice — amplified under the German translation.

• Telling agents their partner is "an identical instance of yourself" makes things worse. GPT-5.2, which initially revealed in about 75% of cases, switches to always turning the light on and reveals in only about 5%; Qwen3-14B and OLMo-3-32B drop from over 95% to around 50% reveal rates when observing a dog. The paper's reading: agents behave as if a consistent internal "natural convention" exists, but none is observed in practice.

• Lexicographic ordering is a brittle coordination rule. Code agents converge on conventions like cat < dog, light on → cat, or treat light off/on as 0/1. This succeeds in Tiny Hanabi Fixed (where agents find (A↦1, C↦2) and beat classical ZSC algorithms that default to the safe fallback), but fails in Tiny Hanabi, whose unique optimal mapping is (A↦2, C↦1). Ordering also inverts across languages — Hund (dog) precedes Katze (cat) in German.

• Text and code agents differ qualitatively. Text agents perform strongly on Hint–Guess, matching the human baselines reported in Ma et al. (2023) and using human-like strategies such as mutual exclusivity and implicature; code agents fall back on arbitrary sorting or positional indexing and never exploit those cues. Code agents are markedly more prone to brittle policies.

• LLMs can find strategies RL misses. Agents reliably discover self-explaining deviations in the trampoline–tiger challenge, where MAPPO and QMIX fail.

• A hand-crafted CFD helps, unevenly. It reduces coordination failure rates in 6/9 environments for Grok 4.1 Fast and 5/9 for GPT-5.2, with a stronger effect on text agents and smaller models. For code agents the effect is confined to Cat & Dog and the Semantic Selection Game. The CFD can also be too restrictive: in ad-hoc conventions environments it pushes agents to the safe fallback, causing under-coordination.

• CFDs can be discovered automatically. Using LLM-driven evolution loosely based on GEPA with Pareto-based candidate selection, meta-training on Cat & Dog and Brittle Bridge with Grok-4.1-Fast as code agent, XP_seed as fitness, and GPT 5.4 as the meta-optimisation agent, the discovered CFD is roughly two-thirds shorter than the hand-crafted one, outperforms it in self-play for Grok 4.1 Fast as a text agent, and yields modest XP_LLM gains for GPT 5.2, Claude 4.5, and Gemini 3 Pro.

Methodology in Plain English

The authors deliberately avoid complex benchmarks. They build small cooperative games where the nature of the coordination problem is unambiguous, then attach plain-English descriptions so an LLM can play. Cat & Dog is the running example: Alice sees an animal and can bail, remove a wall (costing 5), or flash a light for free; Bob sees either the light or the animal and must guess (+10/−10) or bail for 0.5. Two opposite signalling conventions both yield 10, so without prior agreement the rational move is to take the guaranteed 5.

Two agent scaffolds are tested. Text agents are queried step by step: they receive the game description, their role, and their observation history, and return an action. Code agents receive the game description once and return a full joint policy as code. Because a joint policy covers both players, code agents can be sampled repeatedly to produce a distribution of policies, which is what makes the "fixed LLM" cross-play measure possible.

To diagnose failures, the authors repeatedly sample each agent from a fixed state (100 times) to estimate its implicit policy, read the models' reasoning traces, and perturb superficial features — renaming actions, translating the game into German, telling agents their partner is an identical copy of themselves — to see how much behaviour is driven by surface semantics rather than game structure.

The CFD intervention simply inserts a short block of text into the prompt stating coordination principles, such as: is the action relying on an arbitrary convention? Could the roles be flipped? For the meta-learned version, they run an evolutionary loop in which an LLM proposes and refines candidate CFD texts, scored by cross-play performance, and add a "policy critic" that revises generated code policies for CFD compliance while leaving code generation unconditioned so diversity is preserved.

Why This Matters

For research: The paper argues that zero-shot coordination results from RL do not transfer for free to LLM agents, and that LLMs introduce a genuinely new coordination signal — the semantics of the environment — that existing ZSC theory does not model. It also shows capability and reasoning effort are unreliable proxies for coordination ability, which undercuts the assumption that better models will fix this on their own.

Real-world applications:

• AI coding assistants such as Cursor, where agents backed by different LLM providers collaborate on the same codebase.
• Autonomous driving, where vehicles built independently by Waymo, Tesla, and Wayve must negotiate on-road interactions; the narrow tunnel task isolates exactly the tie-breaking failure seen in deployed systems.
• Robotics, where LLM agents generate control policies as code that must interoperate with partners built elsewhere.
• Ad-hoc human–AI teamwork, where an LLM agent deployed by one company must cooperate with agents or people it has never met.

Industry relevance: Any organisation shipping agents that will encounter third-party agents — or that swaps model providers mid-product — inherits this failure mode. The CFD proposal is attractive industrially because it is a prompt-level convention, not a retraining pipeline: independent vendors could in principle agree on a short shared charter without sharing weights or code.

Future Directions

• Beyond prompting. The authors suggest RLHF-based training for CFD compliance, and adapting ZSC principles alongside LLM-RL methods such as GRPO, as ways to bake coordination principles into the model rather than the prompt.
• Richer meta-training distributions. The meta-learned CFD was trained on only two environments; the authors attribute its limited generality to this and expect broader task distributions to yield more robust principles.
• Resolving under- versus over-coordination. A CFD that is too strong suppresses ad-hoc convention formation, while no CFD leads to brittle arbitrary conventions. Finding the balance remains open, and the authors note off-belief learning would face the same tension.
• Separating the causes of failure. Weak theory of mind, failure to recognise that no convention exists, and shallow understanding of the coordination problem are not causally disentangled here; the paper flags this as a target for follow-up work.

Target Audience

Researchers and engineers working on multi-agent systems, LLM agent deployment, and human–AI teaming; reinforcement learning scientists interested in how classical ZSC theory does and does not carry over to language models; and practitioners building products where agents from different vendors must interoperate. Readers without an RL background can follow the game descriptions and the empirical results, but the formal sections assume comfort with Dec-POMDP notation.

Authors’ abstract

We study zero-shot coordination (ZSC), where independently developed agents must coordinate at test time. While ZSC has been well studied in the RL literature, far less is known about the performance of LLM agents despite their increasing deployment in such settings. Existing work on LLM coordination often relies on specialised scaffolding that independently developed agents are unlikely to share in practice. Moreover, evaluations on complex environments (e.g., Hanabi) make it difficult to pinpoint the sources of coordination failure. In contrast, we focus on simple, general-purpose scaffolds in minimal environments designed to isolate specific coordination challenges. Our results show that even in these controlled settings, frontier LLM agents struggle to coordinate, largely due to limited understanding of the coordination problem and weak reasoning about their partner's beliefs. While LLMs introduce semantic information as an additional axis for coordination, they nonetheless fail to exploit this structure effectively. Towards this, we propose Coordination-friendly definitions (CFDs) as a principled approach for enabling robust coordination among LLM agents. Finally, we show that CFDs can be discovered automatically, removing the need for manual engineering. Code is available at https://github.com/ahayler/zsc-llm-agents.