cs.LGNov 4, 2026

Zero-Shot Coordination among LLM Agents

Authors: Adrian Hayler, Shashank Reddy Chirra, Andrei Lupu, Johannes Forkel, Bidipta Sarkar, Siheng Feng, Jakob Foerster

Organizations: BOLD, University of Oxford

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1: Cat & Dog coordination game. (Left) . Alice observes an animal (cat/dog). She can either bail and end the game for a joint reward of 1, remove the wall for a cost of 5, or use the light bulb to signal for free. Bob either observes the state of the light bulb or the animal if the wall is removed. He can guess the animal (+10/-10) or bail for a reward of 0.5. (Right) XP of text agents in the variable LLM setting with and without CFD. Each cell contains the average score of 10 episodes. Adding the CFD leads the agents to consistently pick the safe fallback for a guaranteed reward of +5+5 .
Figure 2: Reasoning traces from a failed coordination in the Cat and Dog environment. Gemini 3 Pro and GPT-5.2 independently arrive at incompatible strategies.
Figure 3: Local policies induced by text agents on Cat & Dog. Most agents induce degenerate signalling policies; e.g, Qwen3-Max-Thinking and Ministral-14B-2512 turn the light on regardless of the observed animal. Qwen3-14B and OLMo-3-32B-Think induce the ZSC-optimal policy.
Figure 4: SP and XP scores of code agents, aggregated across LLMs. Code agents exhibit a clear SP-XP gap, indicating that independently generated policies use incompatible strategies.
Figure 5: (Left) Semantic Selection game. Agents could either coordinate on the semantic focal point (top) or Dec-POMDP-based focal point (bottom). (Right) XP scores of code agents on both games. The SP-XP gap reveals that agents inconsistently choose between the two strategies.
Figure 6: Hand-crafted and Meta-learned coordination-friendly definitions.
Figure 7: Self-play performance of Grok 4.1 Fast as text agent. Incorporating the meta-learned CFD outperforms the hand-crafted CFD, which in turn improves over the baseline.
Appendix figures & tables45 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: An illustration of the Cat & Dog game taken from [ 23 ] .
Figure 9: Worked example of the natural language descriptions D=(DM,DR,{DHi})\mathcal{D}=(\mathcal{D}_{\mathcal{M}},\mathcal{D}_{\mathcal{R}},\{\mathcal{D}_{\mathcal{H}_{i}}\}) for Cat & Dog with text agents. Both players receive the same game description DM\mathcal{D}_{\mathcal{M}} (top). Each text agent additionally receives its role DR(r)\mathcal{D}_{\mathcal{R}}(r) and a description of its action-observation history DHi(τi)\mathcal{D}_{\mathcal{H}_{i}}(\tau_{i}) , which together fill the Game History field of the text-agent prompt template ( Figure 24 ). The game description is taken verbatim from our implementation. In this episode, Alice plays the ZSC-optimal action of removing the wall, and the players obtain a total joint reward of −5+10=5-5+10=5 . Code agents receive only DM\mathcal{D}_{\mathcal{M}} and generate a joint policy for both roles.
Figure 10: Payoff matrices for Tiny Hanabi adapted from [ 12 ] . On the left side, we show the matrix from the original paper, and on the right side, the matrix of our version with a coordination challenge.
Figure 11: Payoff matrices for the Matrix Game adapted from [ 35 ] . Players simultaneously pick a row and column, respectively, and receive the reward at the selected cell.
Figure 12: Semantic Convention Game. Alice and Bob chose a row and column in the matrix sequentially. Additionally, only Alice is informed of the currently active column, which is chosen at random. Only if the agents end up selecting a cell in the active column do they receive the reward in that cell. Agents must choose between the lexicographical mapping convention (green) and the SP-optimal mapping convention (blue).
Figure 13: XP scores of code agents in the semantic games using the hand-crafted CFD. (Left) Semantic convention game. (Right) Semantic selection game. Scores are averaged across six i.i.d. XP matrices; where each cell contained the mean return over 100 episodes.
Figure 14: Example hint-guess scenarios, adapted from Figure 2 of [ 37 ] . Each panel shows a distinct coordination challenge: exact feature match, partial feature similarity, mutual exclusivity, and a combination of the latter two, which represents implicatures [ 38 , 17 ] . The card outlined in red is the target; the card highlighted in yellow is the human-compatible hint choice. The two rightmost scenarios require reasoning about implicature, where the intuitive hint shares no direct feature with the target.
Figure 15: Illustration of text and code agents. While text agents only act out the local policy associated with their assigned roles, each code agent produces a joint policy in Python code. Code agents receive additional information on the structure of the observation space.
Figure 16: Illustration of the evaluation protocols for text and code agents. Note that XPseed\text{XP}_{\text{seed}} is defined only for code agents, as they generate joint policies, whereas text agents induce only local policies. While text agents induce a joint policy which can be obtained by varying the role assignment (see Figure 15 ), they tend to significantly underperform code agents in self-play as the implicit policies are often not self-compatible (see Figure 18 ).
  w/o CFDw/ CFD
EnvModelSP ScoreCoord. failure rateSP ScoreCoord. failure rate
Cat and DogGrok 4.1 Fast−0.75  ⁣±0.99-0.75\>\!{\scriptstyle\pm 0.99}0.53  ⁣±0.050.53\>\!{\scriptstyle\pm 0.05}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
GPT 5.24.50  ⁣±0.494.50\>\!{\scriptstyle\pm 0.49}0.09  ⁣±0.030.09\>\!{\scriptstyle\pm 0.03}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
Ad Hoc Conv.Grok 4.1 Fast95.80  ⁣±2.6595.80\>\!{\scriptstyle\pm 2.65}0.04  ⁣±0.030.04\>\!{\scriptstyle\pm 0.03}50.00  ⁣±0.0050.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
GPT 5.282.71  ⁣±4.0182.71\>\!{\scriptstyle\pm 4.01}0.16  ⁣±0.050.16\>\!{\scriptstyle\pm 0.05}50.00  ⁣±0.0050.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
Ad Hoc Conv. PSGrok 4.1 Fast82.01  ⁣±3.3082.01\>\!{\scriptstyle\pm 3.30}0.08  ⁣±0.040.08\>\!{\scriptstyle\pm 0.04}49.64  ⁣±0.2849.64\>\!{\scriptstyle\pm 0.28}0.04  ⁣±0.030.04\>\!{\scriptstyle\pm 0.03}
Appendix
Table 1: SP performance comparison of text agents (mean ±\pm SEM) across environments, evaluated with and without the CFD. Results are shown for Grok 4.1 Fast and GPT-5.2. The coordination failure rate captures the frequency of catastrophic coordination breakdowns. Given the simplicity of these environments, we require coordination failure rates to be near zero in order to consider coordination robust. We report the mean and standard error over 100 episodes for single-turn games and 50 episodes for multi-turn games. We find that, with the exception of Narrow Tunnel and Permuted Levers, both Grok 4.1 Fast and GPT-5.2 exhibit high coordination failure rates.
EnvironmentThreshold
Permuted Levers0.00.0
Cat and Dog0.00.0
Brittle Bridge−20.0-20.0
Narrow Tunnel−20.0-20.0
Ad-hoc Conventions49.549.5
Ad-hoc Conventions (Permuted Signals)49.549.5
Appendix
Table 2: Thresholds used to define coordination failures for each environment. An episode counts as a failure if its joint reward is at or below the threshold.
Figure 17: The trampoline tiger environment.
Figure 18: Local policies of text agents in Cat & Dog and its variants. The top-left plot shows action probabilities for the standard Cat & Dog environment; each conditional distribution p(⋅∣c)p(\cdot\mid c) is estimated from 100 samples obtained by repeatedly prompting the model from a fixed game state. The remaining plots show the delta, i.e., the change in action probabilities relative to the standard condition, when the environment semantics are varied (changed action labels, German translation, self-play).
Figure 19: Token-probability local policies of text agents in Cat & Dog and its variants. The top-left plot shows action probabilities for the standard Cat & Dog environment, computed from token-level log-probabilities rather than sampling. The remaining plots show the delta, i.e., the change in action probabilities relative to the standard condition, when the environment semantics are varied (changed action labels, German translation, self-play).
  Mean return
ModelReasoning effortw/o CFDw/ CFD
GPT-5 miniLow3.23 ±0.563.23\,{\scriptstyle\pm 0.56}4.47 ±0.144.47\,{\scriptstyle\pm 0.14}
Medium0.97 ±0.810.97\,{\scriptstyle\pm 0.81}4.88 ±0.074.88\,{\scriptstyle\pm 0.07}
High0.86 ±0.910.86\,{\scriptstyle\pm 0.91}4.92 ±0.064.92\,{\scriptstyle\pm 0.06}
Grok 4.1 FastLow1.20 ±0.981.20\,{\scriptstyle\pm 0.98}5.00 ±0.005.00\,{\scriptstyle\pm 0.00}
Medium−0.75 ±0.99-0.75\,{\scriptstyle\pm 0.99}5.00 ±0.005.00\,{\scriptstyle\pm 0.00}
Appendix
Table 3: XP scores of text agents under varying levels of reasoning effort on Cat & Dog. We evaluate GPT-5 mini and Grok 4.1 Fast under varying levels of reasoning effort, as well as with and without the use of our CFD. XP scores are reported as mean ±\pm standard error over 100 games.
ModelReasoning effortBailRevealSignal
GPT-5.6 SolLow0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.06  ⁣±0.020.06\>\!{\scriptstyle\pm 0.02}0.94  ⁣±0.020.94\>\!{\scriptstyle\pm 0.02}
Medium0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.06  ⁣±0.020.06\>\!{\scriptstyle\pm 0.02}0.95  ⁣±0.020.95\>\!{\scriptstyle\pm 0.02}
High0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.11  ⁣±0.020.11\>\!{\scriptstyle\pm 0.02}0.89  ⁣±0.020.89\>\!{\scriptstyle\pm 0.02}
Claude Opus 5Low0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}1.00  ⁣±0.001.00\>\!{\scriptstyle\pm 0.00}
Medium0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.13  ⁣±0.020.13\>\!{\scriptstyle\pm 0.02}0.87  ⁣±0.020.87\>\!{\scriptstyle\pm 0.02}
High0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.74  ⁣±0.030.74\>\!{\scriptstyle\pm 0.03}0.26  ⁣±0.030.26\>\!{\scriptstyle\pm 0.03}
Appendix
Table 4: Action frequencies of frontier text agents as Alice in Cat & Dog under varying reasoning effort. We report how often Alice bails, reveals the animal by removing the wall (the ZSC-optimal action), or uses the light as a signal. As in Figure 3 , frequencies are estimated by repeatedly prompting each agent 100100 times from a fixed game state. Values are reported as mean ±\pm standard error. Higher reasoning effort increases the reveal rate for all three models, most strongly for Claude Opus 5.
Alice / BobGrok 4.5Gemini 3.1 ProDeepSeek V3.2GPT-5.2
No CFD
Grok 4.50.00  ⁣±4.180.00\>\!{\scriptstyle\pm 4.18}4.00  ⁣±3.674.00\>\!{\scriptstyle\pm 3.67}6.00  ⁣±1.006.00\>\!{\scriptstyle\pm 1.00}3.00  ⁣±3.393.00\>\!{\scriptstyle\pm 3.39}
Gemini 3.1 Pro5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}
DeepSeek V3.2−1.00  ⁣±3.67-1.00\>\!{\scriptstyle\pm 3.67}3.00  ⁣±3.393.00\>\!{\scriptstyle\pm 3.39}7.00  ⁣±1.227.00\>\!{\scriptstyle\pm 1.22}−1.00  ⁣±3.67-1.00\>\!{\scriptstyle\pm 3.67}
GPT-5.25.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}2.00  ⁣±3.002.00\>\!{\scriptstyle\pm 3.00}−1.00  ⁣±3.67-1.00\>\!{\scriptstyle\pm 3.67}6.00  ⁣±1.006.00\>\!{\scriptstyle\pm 1.00}
Few-shot demonstrations
Appendix
Table 5: XP scores of text agents in Cat & Dog without a CFD, with few-shot demonstrations, and with the hand-crafted CFD. Rows denote the LLM playing Alice and columns the LLM playing Bob. The few-shot prompts contain the environment description and a hand-crafted rollout of the ZSC-optimal strategy for Ad-Hoc Conventions, Tiny Hanabi Fixed, and Brittle Bridge. Scores are mean ±\pm standard error over 5 games per cell. The safe fallback of removing the wall yields a score of 5.
 w/o CFDw/ CFD
EnvLLMSPXPseed\text{XP}_{\text{seed}}XPLLM\text{XP}_{\text{LLM}}SPXPseed\text{XP}_{\text{seed}}XPLLM\text{XP}_{\text{LLM}}
C.D.Grok10.00  ⁣±0.0010.00\>\!{\scriptstyle\pm 0.00}3.33  ⁣±5.443.33\>\!{\scriptstyle\pm 5.44}0.68  ⁣±1.750.68\>\!{\scriptstyle\pm 1.75}6.67  ⁣±0.966.67\>\!{\scriptstyle\pm 0.96}3.50  ⁣±0.613.50\>\!{\scriptstyle\pm 0.61}3.94  ⁣±0.373.94\>\!{\scriptstyle\pm 0.37}
GPT9.58  ⁣±0.389.58\>\!{\scriptstyle\pm 0.38}9.54  ⁣±0.379.54\>\!{\scriptstyle\pm 0.37}−3.03  ⁣±1.88-3.03\>\!{\scriptstyle\pm 1.88}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}4.50  ⁣±0.384.50\>\!{\scriptstyle\pm 0.38}
Gemini10.00  ⁣±0.0010.00\>\!{\scriptstyle\pm 0.00}10.00  ⁣±0.0010.00\>\!{\scriptstyle\pm 0.00}−1.63  ⁣±2.05-1.63\>\!{\scriptstyle\pm 2.05}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}4.72  ⁣±0.184.72\>\!{\scriptstyle\pm 0.18}
Claude9.17  ⁣±0.769.17\>\!{\scriptstyle\pm 0.76}−7.50  ⁣±2.04-7.50\>\!{\scriptstyle\pm 2.04}1.20  ⁣±0.551.20\>\!{\scriptstyle\pm 0.55}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}5.00  ⁣±0.005.00\>\!{\scriptstyle\pm 0.00}4.72  ⁣±0.184.72\>\!{\scriptstyle\pm 0.18}
DeepSeek10.00  ⁣±0.0010.00\>\!{\scriptstyle\pm 0.00}−3.33  ⁣±5.44-3.33\>\!{\scriptstyle\pm 5.44}0.26  ⁣±0.860.26\>\!{\scriptstyle\pm 0.86}5.83  ⁣±0.765.83\>\!{\scriptstyle\pm 0.76}4.25  ⁣±0.614.25\>\!{\scriptstyle\pm 0.61}4.44  ⁣±0.184.44\>\!{\scriptstyle\pm 0.18}
Appendix
Table 6: SP and XP scores of code agents across environments, under fixed ( XPseed\text{XP}_{\text{seed}} ) and variable ( XPLLM\text{XP}_{\text{LLM}} ) LLM settings, with and without CFD. Agents tested: GPT-5.2, Grok 4.1 Fast, Claude Opus 4.5, Gemini 3 Pro, and Deepseek V3.2 Terminus.
 w/o CFDw/ CFD
EnvLLMSPXPseed\text{XP}_{\text{seed}}XPLLM\text{XP}_{\text{LLM}}SPXPseed\text{XP}_{\text{seed}}XPLLM\text{XP}_{\text{LLM}}
C.D.Grok0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.33  ⁣±0.270.33\>\!{\scriptstyle\pm 0.27}0.46  ⁣±0.090.46\>\!{\scriptstyle\pm 0.09}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.33  ⁣±0.270.33\>\!{\scriptstyle\pm 0.27}0.02  ⁣±0.020.02\>\!{\scriptstyle\pm 0.02}
GPT0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.63  ⁣±0.100.63\>\!{\scriptstyle\pm 0.10}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.02  ⁣±0.020.02\>\!{\scriptstyle\pm 0.02}
Gemini0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.57  ⁣±0.100.57\>\!{\scriptstyle\pm 0.10}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
Claude0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.83  ⁣±0.140.83\>\!{\scriptstyle\pm 0.14}0.42  ⁣±0.030.42\>\!{\scriptstyle\pm 0.03}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.83  ⁣±0.140.83\>\!{\scriptstyle\pm 0.14}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
DeepSeek0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.67  ⁣±0.270.67\>\!{\scriptstyle\pm 0.27}0.48  ⁣±0.050.48\>\!{\scriptstyle\pm 0.05}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}0.67  ⁣±0.270.67\>\!{\scriptstyle\pm 0.27}0.00  ⁣±0.000.00\>\!{\scriptstyle\pm 0.00}
Appendix
Table 7: SP and XP failure rates of code agents across environments, under fixed- and variable-LLM settings, with and without CFD. Agents tested: GPT-5.2, Grok 4.1 Fast, Claude Opus 4.5, Gemini 3 Pro, and Deepseek V3.2 Terminus.
Figure 20: XP matrices of LLM text and code agents. (Left and Middle) XP matrix in the Hint-Guess game; text agents coordinate well, whereas code agents do not. Human players score 0.750.75 on average [ 37 ] . (Right) XP matrix of text agents on the 3 ×\times 3 Hanabi variant; text agents fall well short of the 7.77.7 achieved by IPPO with high entropy regularization [ 14 ] . For text agents, each cell reports the mean and s.e.m. over 1010 episodes; for code agents, each cell is averaged over 100100 episodes across 66 independent XP matrices.
Figure 21: Hanabi 3 ×\times 3 results of text agents with and without a CFD. We find that the LLM agents achieve low scores in all 33 cases.
HinterExact MatchSimilarity (S)Exclusivity (E)S+E
Claude Sonnet 4.6100 / 100100 / 100100 / 100100 / 100
Gemini 3.1 Pro100 / 100100 / 100100 / 100100 / 0 92
GPT-5.4100 / 100100 / 100100 / 100100 / 100
Grok 4.1 Fast100 / 100100 / 100100 / 1000 75 / 0 75
All100 / 100100 / 100100 / 1000 94 / 0 92
Appendix
Table 8: Hint-Guess Implicatures: Human-compatible hint rate and win rate (%) by scenario. Scenarios correspond exactly to those in Figure 14 . Each cell shows Human % / Win % ( n=12n{=}12 games per hinter–scenario cell). Exact : target card available in hinter’s hand. Similarity (S) : feature similarity required, no exact match. Exclusivity (E) : mutual exclusivity (Gricean implicature) required. S+E : combined similarity + exclusivity scenario. All models give the human-compatible hint perfectly on Exact, Sim, and Excl; failures concentrate in the S+E condition.
Figure 22: XPseed\text{XP}_{\text{seed}} scores of code agents aggregated across different LLM types and scaffolds. Results are shown for Grok 4.1 Fast, GPT-5.2, Gemini 3 Pro, and Opus 4.5. Since the CFD was meta-trained with Grok 4.1 Fast on Cat & Dog and Brittle Bridge, Grok 4.1 Fast is excluded from these two environments in all conditions, including the overall score. Scores are min–max normalised per environment using fixed reward ranges, and error bars denote the standard error over seed pairs.
Figure 23: XPLLM\text{XP}_{\text{LLM}} scores of code agents aggregated across different LLM types and scaffolds. Results are shown for Grok 4.1 Fast, GPT-5.2, Gemini 3 Pro, and Opus 4.5.
SymbolValueQuick explanation
E\mathcal{E}{\textscCatAndDog, \textscBrittleBridge}\{\textsc{CatAndDog},\ \textsc{BrittleBridge}\}Meta-train coordination environments
KK55Number of seed CFDs sampled at initialisation
TevoT_{\mathrm{evo}}2020Outer-loop evolution steps
ncn_{c}1010Size of the XP-matrix in the cheap single-env gate
nfn_{f}1515Size of the XP-matrix in the full all-envs evaluation
LL33Max retries to draw a non-duplicate CFD
Appendix
Table 9: Inputs to Algorithm 3 used in our experiments.
Figure 24: Template of the prompt used for text agents. Blue-shaded fields are filled in at runtime.
Figure 25: Template of the prompt used for code agents. Blue-shaded fields are filled in at runtime.
Figure 26: Template of the prompt used for the policy critic. Blue-shaded fields are filled in at runtime.
Figure 27: Shared background block prepended to every mutation prompt.
Figure 28: Combined template for the four unary_* mutation operators ( unary_add , unary_remove , unary_reformulate , unary_atomic ). The thinking-style blocks substituted into the Task Instructions, Extra Constraints, and Reasoning Prompt placeholders are listed in Figure 29 .
Figure 29: Thinking-style blocks substituted into the unary ( Figure 28 ) and diverse ( Figure 30 ) mutation prompt templates.
Figure 30: Combined template for the four diverse_* mutation operators ( diverse_add , diverse_remove , diverse_reformulate , diverse_atomic ). The differences from the unary template ( Figure 28 ) are that the prompt asks for nproposalsn_{\text{proposals}} diverse candidates and that the singleton new_cfd field is replaced with a proposals list. After parsing, we sample one proposal uniformly at random as the child CFD. Thinking-style blocks ( Figure 29 ) are reused unchanged.
Figure 31: Template used by the reinit operator. The operator calls this prompt with nn candidates per invocation and samples one uniformly at random as the child CFD. The same template is also used to create the initial seed population at the start of the meta-learning loop.
Figure 32: Coordination failure between Gemini 3 Pro and GPT 5.2 in Hanabi 3 ×\times 3 due to mismatched assumptions about the “Good Touch” principle (i.e, all clued cards will be played in the future), a convention widely adopted by human Hanabi players. Gemini provides a rank-1 hint to signal a newly drawn R1 at position 4, but the hint also re-touches an already-played duplicate Y1 at position 3, violating the “Good Touch” principle. GPT, assuming that a cooperative partner “would not hint cards that are already played,” infers that both touched cards must be playable 1s and plays the older hinted card (the Y1 duplicate), costing the team its only life. This failure is compounded by an implicit convention, playing the oldest hinted card, that was not mutually established; had the clue giver anticipated this assumption, they would have avoided giving the hint.
Figure 33: Reasoning traces of GPT 5.2 and Opus 4.5 agents in Tiny Hanabi. GPT 5.2 chooses a joint policy based on SP optimality wheres Opus picks a joint policy based on lexicographical ordering.
Figure 34: Reasoning traces of Grok 4.1 Fast and GPT 5.2 as code agents in Tiny Hanabi Fixed. Both agents independently converge on the lexicographic mapping (A  ≈ \,\approx\, 1, C  ≈ \,\approx\, 2): Grok uses it as an active signalling convention, while GPT uses it to decode the partner’s signal. This shared semantic bias enables agents to coordinate via a convention rather than defaulting to the safe fallback.
Figure 35: Reasoning traces of Grok 4.1 Fast, Gemini 3 Pro and Deepseek V3.2 when generating the most common observed strategies in Adhoc conventions. Note that the three strategies are mutually incompatible.
Figure 36: Reasoning Traces of Gemini 3 Pro and Grok 4.1 Fast in Ad-hoc conventions permuted signals . Although both models converge on a scheme where Alice remains fixed and Bob adapts, they adopt different calibration strategies for Bob, rendering them incompatible.
Figure 37: Reasoning Traces of Grok 4.1 Fast, Deepseek V3.2 and GPT 5.2 in Brittle Bridge. DeepSeek produces a complex role-assignment strategy that performs poorly even in self-play. In contrast, Grok 4.1 Fast and GPT 5.2 each learn role-assignment strategies that are mutually incompatible.
Figure 38: Reasoning Traces of Opus 4.5 and GPT 5.2 in Narrow Tunnel. These traces illustrate the two most common yet incompatible role-assignment strategies: “left goes first” versus “right goes first.”
Figure 39: Reasoning Traces of Opus 4.5 and Deepseek V3.2 in Matrix Game. Opus 4.5 successfully identify different focal points from the payoff matrix.
Figure 40: Reasoning Traces of Opus 4.5 and Deepseek V3.2 in Permuted Levers. Opus 4.5 achieves a low self-play score but exhibits strong cross-play performance when paired with DeepSeek V3.2.
Figure 41: Convention mismatch in Hint-Guess. The hinter gives the trivially correct exact-match hint 1B for target 1B . The guesser, however, applies an over-engineered bijective code in which 1B is re-mapped to a residual slot ( 1A ).
Figure 42: Convention mismatch in Hint-Guess. The hinter uses a simple exact-match strategy: hint 1C because 1C is in both hands. The guesser ignores the direct exact-match signal and instead applies a lexicographic position-based bijection, mapping the 2nd hint in the sorted hinter hand ( 1C ) to the 2nd card in the sorted guesser hand ( 2A ).
Figure 43: Reasoning trace of GPT-5.4 as a code agent in Hint Guess. The policy sorts both hands canonically (1A << 1B << … << 3C), deduplicates, and coordinates by mapping target indices modulo the number of unique hinter cards. Although internally consistent, the convention is essentially arbitrary — another code agent is unlikely to independently arrive at the same convention, hence cross-play coordination breaks down.
More in this topic

Multi-Agent Coordination

Multi-agent coordination studies how autonomous agents align actions, share information, and divide work to achieve individual or collective goals.

See all 533 papers

Explore similar work

CardsList
Apr 19, 2026

Provable Coordination for LLM Agents via Message Sequence Charts

Multi-agent systems built on large language models (LLMs) are difficult to reason about. Coordination errors such as deadlocks or type-mismatched messages are often hard to detect through testing. We introduce a domain-specific language for specifying agent coordination based on message sequence charts (MSCs). The language separates message-passing structure from LLM calls, tool calls, and human control points, whose outcomes remain unpredictable. We define the syntax and semantics of the language and present a syntax-directed projection that generates deadlock-free local agent programs from global coordination specifications. We illustrate the approach with a diagnosis consensus protocol and show how coordination properties can be established independently of LLM nondeterminism. We also describe a runtime planning extension in which an LLM dynamically generates a coordination workflow for which the same structural guarantees apply. An open-source Python implementation of our framework is available as ZipperGen.

Benedikt Bollig, Matthias Függer, Thomas Nowak

Universit´e Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Gif-sur-Yvette, France · Institut Universitaire de France, Paris, France

Multi-Agent LLM SystemsMulti-Agent CoordinationLLM Agent Planning
AskPDF
Jun 6, 2026

Benchmarking Open-Ended Multi-Agent Coordination in Language Agents

As language models are increasingly deployed as autonomous agents, they must coordinate with others over long horizons in open-ended interactive tasks. Yet existing evaluations rarely test these demands together, instead emphasising single-agent tasks, short interactions, or highly structured multi-agent settings. We introduce alemalem, a JAX-based benchmark for open-ended multi-agent coordination built on Craftax-like dynamics. Alem embeds procedurally generated coordination tasks, soft specialisation, communication, and controllable coordination difficulty into a long-horizon survival world with exploration, crafting, trading, and combat. We evaluate 1313 modern LLMs zero-shot within homogeneous teams, with trained MARL agents as reference points. Current LLM agents remain far from solving alem, averaging only ~6% normalised return, but their failures are not uniform. On the hardest coordination setting, zero-shot Gemini-3.1-Pro-High approaches MARL agents trained for one billion steps, while GPT-5.4-High achieves strong base-task reward but much lower coordination reward. This contrast shows that individual task competence does not imply coordination competence. Ablations show that communication is the largest contributor to coordination, while memory and reasoning help when used to maintain multi-step plans. Overall, our results identify coordination as a distinct bottleneck for frontier LLM agents, separate from single-agent capabilities. Alem makes this bottleneck measurable and provides a controlled testbed for developing agents that communicate, allocate roles, and execute shared plans. Code is available at https://github.com/alem-world/alem-env.

Kale-ab Abebe Tessera, Andras Szecsenyi, Cameron Barker +7

University of Edinburgh · University of Oxford · University College London

Multi-Agent CoordinationLLM Agent EvaluationAI Agent BenchmarksLong-Horizon LLM AgentsMulti-Agent CommunicationZero-Shot Coordination
AskPDF
Apr 9, 2026

More Capable, Less Cooperative? When LLMs Fail At Zero-Cost Collaboration

Large language model (LLM) agents increasingly coordinate in multi-agent systems, yet we lack an understanding of where and why cooperation fails. Many real-world coordination problems are not social dilemmas: helping others -- sharing documentation, unblocking a teammate -- costs the helper almost nothing while producing substantial collective benefit. Whether LLM agents cooperate in this regime, where helping is free and they are explicitly instructed to do so, remains unknown. We build a turn-based multi-agent environment that strips away all strategic complexity, making cooperation costless and trivially optimal. Across eight widely used LLMs, capability does not predict cooperation: OpenAI o3 reaches only 17% of optimal collective performance while the weaker o3-mini reaches 50%, despite identical instructions to maximize group revenue. Using a causal decomposition that automates one side of agent communication, we separate cooperation failures from competence failures, and find that several capable models actively withhold information despite gaining nothing from withholding. Targeted interventions address each mode: explicit protocols roughly double the performance of competence-limited models, while small sharing incentives unlock cooperation-limited ones. Our results suggest that scaling intelligence alone will not solve coordination in multi-agent systems, and will require deliberate cooperative design, even when helping costs nothing.

Advait Yadav, Sid Black, Oliver Sourbut

MATS · University of Illinois Urbana-Champaign · UK AI Security Institute +1

Multi-Agent CoordinationMulti-Agent CollaborationLLM AgentsMulti-LLM CollaborationMulti-Agent Communication
AskPDF