acceptodds
Under review as a conference paper at ICLR 2027

Zero-Shot Coordination in Text Optimisation: Do Independently Optimised Agents Work Together?

Abstract

Text optimisation improves an agent by letting a language model repeatedly rewrite text artefacts, such as policy code, action tables, or instructions, against a score. These methods are judged almost entirely by that score. In cooperative tasks this hides a problem known from multi-agent reinforcement learning as zero-shot coordination: agents optimised separately may each perform well, yet fail when paired, because every run settles on its own conventions. We study zero-shot coordination in text optimisation. We run independent optimisation processes across language models and optimisation methods, and pair the resulting agents with partners they never met. A small, exactly solvable signalling game reveals the conventions each run adopts, and a cooperative cooking game tests the same question in a larger domain. We find that optimisation replaces shared focal points with conventions tied to each run's presentation of the task. Scoring candidates against independent samples of the unoptimised model preserves compatibility when those samples agree, and rejecting proposals that are not invariant under the game's symmetries preserves it when they disagree. We argue that partner generalisation should be reported alongside the score.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Zero Shot Coordination, Multi Agent, Text Optimisation

Reviews

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

The paper studies the question of if agents that are text-optimised independently can still cooperate with each other. The paper uses a set of coordination toy examples to isolate the problem and show a coordination failure mode of prior work on text optimisation. Using these examples the authors show that agents have have been text-optimised independently can fail to coordinate with each other due to converging on incompatible conventions or behaviour. Several methods to mitigate this coordination failure are proposed and tested and are shown to be effective in the tested examples. The coordination failure was not clearly observed in the overcooked environment.

Critical strengths
  • The paper shows how text optimisation can improve an agent's score while making it less compatible with independently optimised partners. It is shown that agents have a common failure mode where they will fallback to the first alternative in their own list, which can lead to incompatible conventions between agents which have different list orderings.
Critical weaknesses
  • The writing and structure of the paper is poor and confusing. Figure 1 is not understandable without reading section 5, which is 3 pages later. All the tasks are not clearly separated and the narrative continuously jumps between them without clear distinction. Many terms are not defined, and much of the authors intent is vague and unclear. The different game definitions is very fragmented, Eiffel Tower has a section, Overcooked and Signal Relay share a section after the experiments are presented, Hanabi is only described in the appendix in a section that is not referenced in the main text. Also "the tower game" is mentioned and it is unclear if this is the same as the Eiffel Tower game or a different game.
  • The practical importance of the findings is not sufficiently established. The main failures occur in small games designed around incompatible conventions, while the larger Overcooked experiment improves both self-play and cross-play. Some fixes also rely on knowing the game's symmetries or rewarding a known compatible solution. It remains unclear how often this problem arises in realistic text optimisation settings and how useful the proposed fixes would be there.
Questions for authors
  • What practical settings are most likely to exhibit this failure? The Overcooked experiment does not reproduce it, so it would help to clarify when independent text optimisation is expected to reduce coordination outside the small games.
Reviewer_fVsjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates zero-shot coordination between independently optimized LLM agents. The authors show that text optimization methods such as GEPA and evolutionary code search can improve self-play performance while reducing cross-play performance, as independently optimized agents may develop incompatible conventions. The paper further analyzes the underlying mechanisms and explores several remedies, including population scoring and symmetry rejection.

My main concern is the gap between the experimental settings and practical multi-agent LLM systems. The experiments are primarily conducted in game-based environments, while real-world multi-agent systems often involve more structured workflows, such as a manager agent assigning tasks to specialized agents (also they can share information with others). In such settings, coordination may depend more on task decomposition, communication, and information sharing than on implicit conventions learned independently.

Critical strengths
  1. The paper addresses an interesting and relevant problem. As LLM-based multi-agent systems become increasingly common, understanding whether independently optimized agents can coordinate effectively is important.
  2. The paper provides clear experimental observations and useful analyses of how optimization may introduce incompatible conventions. The distinction between self-play and cross-play is particularly valuable.
  3. The authors explore several potential solutions and investigate the phenomenon across different models and environments.
Critical weaknesses
  1. The experiments are primarily conducted in game-based environments, which differ considerably from real-world LLM multi-agent applications.
  2. The experimental environments appear somewhat tailored to the research hypothesis. The simplified coordination games are designed to expose failures caused by incompatible conventions. While such controlled settings are useful and have a long tradition in MARL research (e.g., Hanabi), they may amplify coordination problems that are less prominent in practical systems. In particular, real-world LLM agents can often communicate, clarify their intentions, and adapt their behavior through interaction. Such mechanisms may resolve many of the convention mismatches observed in the paper. Therefore, the generalizability and practical significance of the identified failure mode remain somewhat uncertain.
Questions for authors
  1. To what extent could explicit communication and iterative interaction between agents mitigate the coordination failures observed in the experiments? Is it enough when agents share some information through talking (so that they can coordinate well)?
  2. Given that optimization improves both self-play and cross-play in Overcooked, what characteristics of a task determine whether optimization leads to coordination degradation?
Reviewer_JtmKOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies zero-shot coordination (ZSC) when using iterative text and code optimizers like GEPA and OpenEvolve. The authors test whether optimizing agents in self-play causes them to abandon shared natural-language focal points (like meeting at the Eiffel Tower) in favor of arbitrary, prompt-order-dependent conventions. They evaluate this across a semantic 10-option lever game (the Eiffel Tower problem), a 1-round 2-card signaling matrix (Tiny Hanabi), a 27-state lookup-table game (Signal Relay), and a small Overcooked pilot, proposing population scoring against base models for "shared-prior" models and programmatic symmetry filtering for "split-prior" models.

Critical strengths

Zero-shot coordination is an interesting problem, and it is clear in the problem formulation that this is far from solved as LLMs are trained against stationary distributions and not multi-agent systems

Critical weaknesses

The paper reads as though it was conceived, simplified, executed, and written end-to-end by an autonomous coding agent—which the AI Use Statement on page 10 essentially confirms, noting that Claude Code and Codex were used to propose the hypotheses and remedies, design the protocols, write and monitor the experiments, analyze the results, write the text, and review the drafts. While using AI tools is allowed, the resulting paper exhibits classic failure modes of automated research pipelines optimizing for fast execution over scientific substance.

First, the tasks are far too toy, and the core experiments strip out language agents entirely. Outside of choosing a single café name in the 1-step Eiffel Tower prompt, the main games where remedies are tested (Tiny Hanabi and Signal Relay) do not even use an LLM during gameplay. Instead, the optimizer edits a 10-entry JSON table or a 27-entry Python dictionary (POLICY = {...}) that is scored by exact mathematical enumeration. Optimizing a 10-cell lookup table against an explicit 4 × 3 payoff matrix is just tabular search over a tiny finite state space; it tells us almost nothing about how actual LLM agents coordinate in natural language at runtime.

Second, the paper's flagship remedy for split-prior models ("exact symmetry rejection") is a tautological coding trick rather than a generalizable method. It relies on a hardcoded Python filter given privileged access to the exact algebraic automorphism group of the matrix game and rejects any lookup table that is not invariant under label permutation. In Tiny Hanabi, only one competent deterministic table survives this filter, so achieving perfect 8.00 cross-play across independent runs is guaranteed by construction the moment that single table is proposed. In Signal Relay, the filter simply disables the free-code communication channel (amber/violet) altogether. When the authors tested an actual LLM-based convention critic without hardcoded algebraic symmetries, it failed (p = 0.42), leaving the paper with no workable solution for real language tasks where game symmetries cannot be hand-enumerated.

Finally, the experimental execution is riddled with bugs and shortcuts that were documented like an automated audit log rather than properly fixed. A linear seed-indexing bug caused 87% to 94% of partner-panel samples to share presentation seeds across supposedly independent runs, and the authors admit in Section 11 that even in Table 1, the Sonnet 5 cross-play column with fresh base samples still relies on buggy non-independent seeds. Similarly, the Overcooked population-scoring runs all shared a single training pool rather than independent partner panels, most secondary claims rely on underpowered 4-run (or 1-run) pilots, and the few-shot fictitious-play experiment breaks frequency ties alphabetically by café name—which artificially forces coordination after a reciprocal swap via a hardcoded external tie-breaker. In both few-shot adaptation and Signal Relay, optimized prompts repeatedly blew past token ceilings (168 truncated rounds at the final checkpoint), and the main analysis simply discards failed rounds rather than penalizing them.

Questions for authors

Can you show that your findings and remedies hold in a genuine multi-agent LLM setting where the optimizer rewrites a natural-language system prompt and an LLM actually generates actions in the loop during multi-turn gameplay, rather than editing a 10- or 27-entry static lookup table?

How is "exact symmetry rejection" supposed to work in any realistic natural-language coordination task where the exact algebraic automorphism group of the environment is unknown and cannot be hardcoded into a rejection filter, especially given that your LLM-based critic failed on Tiny Hanabi?

Why was the submission not held until the seed-overlap bug in Table 1 (Sonnet 5 fresh base-sample cross-play) and the shared training pool in Overcooked were properly re-run with independent seeds?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.