- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
SPOON optimizes textual strategies for frozen LLM agents in two-player games. Strategies consist of explicit condition–rule pairs, which an LLM optimizer locally revises using game trajectories and both players’ strategies. Candidate updates must improve the current game while preserving performance on selected stored examples. The two players co-evolve through repeated interactions. Experiments cover classical games, several multi-agent applications, and single-agent tasks with an adaptive adversary during optimization, reporting gains over training-based and prompt optimization baselines.
Critical strengths
- Interpretable strategy representation. Explicit condition–rule pairs make strategies easy to inspect and locally revise while keeping model weights fixed. Replay checks against stored examples also provide a sensible safeguard against regressions.
Critical weaknesses
-
Limited validation of stable strategic improvement. Updates improve individual replayed games while checking only one stored witness per strategic state. This does not establish sustained improvement in overall strategy quality. The paper lacks analysis of long-run stability, cycling, or exploitability under co-evolution.
-
Limited practical applicability. SPOON assumes controlled two-player settings where both strategies can be inspected and revised and interactions can be replayed during optimization. It is unclear how often this setup is relevant to realistic downstream LLM applications. The downstream experiments do not sufficiently establish when introducing and co-evolving two explicit strategies addresses a practical need.
Questions for authors
-
Strategic stability. Beyond the checked witnesses, do accepted updates retain their gains against earlier opponent strategies? Evaluation against a fixed pool of opponent snapshots over optimization would help assess whether improvements persist or cycle.
-
Practical motivation. Which concrete downstream workflows motivate access to both strategies and replayable interactions during optimization? Please clarify why jointly evolving two strategies is useful in these settings.
4 comments
Response to reviewer 9Ft5 (2/4)
Index player ’s accepted updates by , and let denote its policy after accepted updates. An update from to records a witness satisfying
Every subsequent accepted update preserves this improvement under the stated conditions, including after the witness is replaced. Hence, for every ,
The later policy cannot be behaviorally identical to the earlier policy because their payoffs differ under the same replay conditions. This argument applies separately to both players, even as their opponents evolve. Accepted policies therefore cannot cycle; with finite induced policy spaces, only finitely many updates can be accepted, so both policies eventually stabilize.
This conditional convergence result does not establish a Nash equilibrium: a finite proposal budget can miss profitable deviations in a large strategy space, and historical constraints can exclude others.
Because the proof uses idealized conditions, we next characterize convergence empirically through longer optimization runs and test whether frontier representatives protect earlier improvements in practice.
2. Performance during extended optimization.
We extend Briscola optimization from 30 to 150 episodes and HotpotQA optimization from 450 to 2250 iterations, using five optimization seeds. Saved checkpoints are evaluated against fixed reference pools assembled after optimization.
For Briscola, both players use Qwen2.5-7B-Instruct. For each seed and player role, the pool contains four opponent strategies from the same SPOON run: initialization and episodes 10, 30, and 150. Every player checkpoint faces this same equally weighted pool. Each seed–snapshot comparison uses 50 games: 25 held-out deals evaluated in both roles, with the same deals across checkpoints and snapshots. Results average both roles and all five seeds.
Note that the SPOON results in Table 1 evaluates generalization to three larger held-out opponents: Qwen3-235B-A22B-Instruct-2507, Gemini-2.5-Flash-Lite, and Grok 4.3. Here, we instead evaluate against saved strategies of the Qwen2.5-7B-Instruct optimization-time opponent, keeping the reference pool fixed to measure progress during optimization.
| Optimization episode | 0 | 10 | 20 | 30 | 60 | 90 | 120 | 150 |
|---|---|---|---|---|---|---|---|---|
| Briscola win rate against the fixed four-opponent pool (%) | 25.6 | 44.1 | 63.5 | 64.2 | 65.4 | 65.9 | 65.7 | 66.1 |
Performance largely stabilizes by the original 30-episode horizon. Continuing to episode 150 preserves the gains and adds 1.9 percentage points, with a 95% paired t-interval of [0.4, 3.4] across optimization seeds.
For HotpotQA, the solver and adversary use Qwen3-8B. Each seed’s pool contains four adversary strategies from the same SPOON run: initialization and iterations 150, 450, and 2250. Each frozen adversary produces a fixed evaluation panel from the 300 held-out questions, using validated rewrites or the original question when no valid rewrite is obtained. Every solver checkpoint receives the same four panels, weighted equally. Pool results average all five optimization seeds.
We also extend the specific optimization run that produced the submitted 64.67% HotpotQA result in Table 5, continuing it from iteration 450 to 2250. At each checkpoint, we evaluate the solver on the same 300 original test questions, with the adversary removed. This original-question row therefore tracks one continued submitted run, while the adversary-pool row averages five runs. Iteration 0 denotes SPOON’s initialized strategy.
| Optimization iteration | 0 | 150 | 300 | 450 | 900 | 1350 | 1800 | 2250 |
|---|---|---|---|---|---|---|---|---|
| HotpotQA accuracy against the fixed four-adversary pool (%) | 39.8 | 50.2 | 54.8 | 57.4 | 60.3 | 61.6 | 61.4 | 62.2 |
| HotpotQA accuracy on original test questions, one continued submitted run (%) | 41.67 | 55.67 | 61.33 | 64.67 | 66.33 | 67.33 | 67.00 | 67.67 |
At the submitted 450-iteration checkpoint, performance has not yet reached the plateau observed during extended optimization. Continuing to iteration 2250 improves pool accuracy by 4.8 points and original-question accuracy by 3.00 points. Over iterations 1350–2250, the respective scores vary within 61.4–62.2% and 67.00–67.67%. The extended runs show further improvement followed by late-stage performance stabilization.
These results include continued strategy revision beyond the original optimization horizons. After the original 30 Briscola episodes, SPOON accepts a mean of 6.2 additional updates per run across both players during episodes 31–150. After the original 450 HotpotQA iterations, it accepts a mean of 11.6 additional solver updates per run during iterations 451–2250. Both means are calculated across the five optimization runs. [continue below]
Response to reviewer 9Ft5 (3/4)
3. Historical cross-play and the contribution of frontier verification.
A rising pool average can hide losses against individual opponents. We ask: after learning to handle an opponent, how much does performance against that opponent subsequently decline?
We evaluate later player checkpoints against each fixed historical opponent on the same held-out cases. For example, the Briscola opponent saved at episode 10 faces player checkpoints from episodes 10, 20, 30, 60, 90, 120, and 150. With the opponent and evaluation deals fixed, any decline reflects a change in the evaluated player.
For each fixed opponent, we record the largest drop from an earlier checkpoint’s score to a later checkpoint’s score. Scores of 60%, 66%, and 62% give a largest drop of 4 percentage points, from 66% to 62%. A score that never decreases receives zero. This captures temporary reversals that comparing only the first and last checkpoints could miss.
We calculate this measure separately before and after the original optimization horizons. Each window includes only player checkpoints at or after the opponent was saved and requires at least two checkpoints. The table averages these largest drops across the included opponents and five optimization seeds, and across both roles for Briscola.
We compare SPOON with an ablation removing only frontier checks. It retains co-evolution, strategic structure, current-game improvement checks, and the same initialization, models, proposal budget, and iteration horizon. Both methods face the same SPOON reference opponents and held-out cases defined above.
| Average largest drop against a fixed earlier opponent (percentage points; lower is better) | SPOON | Without frontier verification |
|---|---|---|
| Briscola, episodes 0–30 | 0.8 | 8.0 |
| Briscola, episodes 30–150 | 1.2 | 11.9 |
| HotpotQA, iterations 0–450 | 1.0 | 7.6 |
| HotpotQA, iterations 450–2250 | 1.4 | 10.4 |
During Briscola episodes 30–150, the average largest loss against an earlier opponent is 1.2 points with SPOON versus 11.9 without frontier verification. The same pattern holds in both tasks before and after their original horizons. Final Briscola win rate against the complete reference pool is also higher with frontier verification: 66.1% versus 58.0%.
We separately test whether current representatives protect the training examples they replaced. After each accepted update, an offline audit replays replaced Briscola witnesses with the preceding and updated policies, using each witness’s original opponent and replay conditions. A regression occurs when the updated policy receives a lower payoff. We report the regression fraction across update–witness comparisons, averaged across seeds.
During episodes 1–30, regression rates are 0.8% with frontier verification versus 13.5% without it; during episodes 31–150, they are 1.1% versus 17.6%. The abstraction is therefore imperfect, but frontier verification substantially reduces reversals of earlier successes.
The cross-play evaluation measures performance on fresh games against earlier opponents; the witness audit checks the original examples that motivated updates. Both support frontier verification’s role in preserving improvements during continued co-evolution.
4. Exact best-response evaluation in binary-payoff KuhnPoker.
We evaluate a single-hand, binary-payoff configuration of the TextArena KuhnPoker environment used by MEMO. We retain the configuration used during our optimization, with Qwen2.5-7B-Instruct for both players. Payoffs depend only on whether the player wins or loses the hand, rather than the number of chips gained or lost. The small game tree permits exact best-response computation under the same payoff and information constraints.
We report NashConv:
Here, is expected payoff over chance outcomes, and the maximization considers all legal unilateral policies respecting the player’s information constraints. Zero means neither player can improve by deviating unilaterally.
NashConv reaches zero within 30 episodes in all five runs and remains zero at episodes 60, 90, 120, and 150. Thus, the learned joint policies reach a Nash equilibrium within the original optimization horizon in this evaluated game.
The fixed-pool evaluations show improved held-out performance followed by stabilization during extended optimization. Historical cross-play shows that gains against earlier opponents are better retained with frontier verification, while the replaced-witness audit tests preservation beyond the examples currently stored in the frontier. The theory establishes conditional stabilization without cycling, and exact best-response evaluation verifies equilibrium in the binary-payoff KuhnPoker variant. We will add these analyses and results to the revised manuscript.
Response to reviewer 9Ft5 (4/4)
Critical Weakness 2 and Q2: Practical Applicability and Motivation
Following the reviewer’s suggestion, we clarify how access to both strategies and replayable interactions arises in practical LLM applications, and provide additional ablations evaluating the benefit of co-evolution.
Practical applicability. The controlled training setting required by SPOON already arises in established practical LLM applications. Our experiments (§4.2) follow Self-RedTeam’s attacker–defender setting for safety alignment, Rubric-ARM’s generator–judge setting for preference judging, and ReMA’s planner–solver setting for mathematical reasoning.
In all three, the training procedure controls the policies for both roles and can rerun their interactions on training examples. These applications therefore provide concrete settings where both policies can be revised and interactions replayed during optimization. The prior methods optimize policies through model parameters; SPOON uses explicit strategy prompts, which can be inspected and edited while keeping model weights frozen. We retain the same agent roles, task interactions, and feedback.
Our optimization rollouts preserve the players’ test-time information constraints. During both optimization and evaluation, each player receives only its own strategy and permitted observations. Only the optimizer sees both strategies (§3.2).
Benefit of jointly evolving two strategies. As discussed in §2.1, repeatedly optimizing against an opponent the agent already handles can provide limited additional feedback. Co-evolution introduces new challenges that expose remaining weaknesses, with the aim of efficiently learning strategies that generalize beyond the current opponent. In cooperative settings, updating both components lets the planner or rubric generator improve its guidance while the solver or judge improves how it uses that guidance.
Table 6 evaluates co-evolution: fixing the opponent reduces mean held-out win rate from 55.07% to 45.96%, with decreases across all five games.
We additionally test this benefit in two downstream applications.
The new comparisons match model backbones, strategy representations, inference pipelines, and total optimization-token budgets, including challenge generation and verification. Results are mean ± standard deviation over five optimization seeds.
HotpotQA. We optimize the solver’s strategy in every variant. Without an adversary, it learns from failures on the original training questions. A fixed adversary generates new question rewrites but keeps its strategy unchanged as the solver improves. The fixed pool samples from four such adversaries. These fixed strategies are optimized against the initial solver, with their construction costs included in the budget. All rewrites undergo the same validity checks. SPOON updates both the solver and adversary throughout optimization.
| Optimization condition | HotpotQA test score (%) |
|---|---|
| Optimize solver on original questions; no adversary | 57.47 ± 0.69 |
| Optimize solver; adversary strategy fixed | 58.93 ± 0.55 |
| Optimize solver; four adversary strategies fixed | 59.73 ± 0.55 |
| SPOON: solver–adversary co-evolution | 64.73 ± 1.01 |
All conditions evaluate the frozen solver on the same 300 held-out questions, with the adversary removed. SPOON achieves 64.73%, compared with 59.73% for the fixed diverse pool. This supports adapting the training adversary to the improving solver, beyond supplying a fixed source of varied challenges.
Preference judging. Both the rubric generator and judge remain present in every variant. We compare updating either strategy alone, updating both sequentially, and co-evolution. Sequential optimization completes all updates to one component before updating the other; co-evolution alternates updates between them. Sequential and alternating runs give each component the same optimization budget.
| Optimization condition | RewardBench Chat-Hard accuracy (%) |
|---|---|
| Update judge; generator strategy fixed | 75.09 ± 0.53 |
| Update generator; judge strategy fixed | 74.65 ± 0.45 |
| Update generator, then judge | 76.40 ± 0.45 |
| Update judge, then generator | 76.10 ± 0.35 |
| SPOON: generator–judge co-evolution | 80.44 ± 0.52 |
All variants evaluate the frozen pipeline on the same 456 held-out preference pairs. SPOON achieves 80.44%, compared with 76.40% for the stronger sequential order. This supports repeatedly adapting the components to each other, even when both receive optimization under the same total budget.
We will include these experiments in §4.4 and clarify the practical settings and information constraints in §§3.2 and 4.2.
Response to reviewer 9Ft5 (1/4)
We thank the reviewer for the insightful comments and address the concerns raised below.
Critical Weakness 1 and Q1: Stable Strategic Improvement [Addressed in Parts 1–3]
Following the reviewer’s suggestion, we evaluate saved strategies against fixed pools of opponent snapshots throughout extended optimization on Briscola and HotpotQA. We additionally measure whether gains against individual historical opponents persist, compare with an ablation removing frontier verification, and audit historical examples whose frontier witnesses have been replaced. These empirical evaluations are complemented by conditional convergence analysis and exact best-response evaluation in binary-payoff KuhnPoker.
SPOON uses co-evolution to expose remaining weaknesses and improve generalization. As discussed in Section 2.1, repeatedly optimizing against an opponent the agent already handles can provide limited additional feedback. Updating the opponent introduces new challenges, with the goal of efficiently learning strategies that remain effective beyond the current opponent.
Our submitted experiments directly test this generalization across classical games and practical applications by evaluating the learned strategies against held-out opponents or held-out test cases. SPOON achieves a mean held-out win rate of 55.07% across five classical games, compared with the published means of 20.90% for default static prompting, 44.30% for MEMO, and 45.00% for UnstableBaseline. HotpotQA accuracy increases from the unoptimized pipeline’s 42.33% to 64.67%.
Table 6 directly compares full SPOON with the no-co-evolution ablation, which keeps the opponent fixed during optimization. Co-evolution improves held-out win rate on all five games, increasing the mean from 45.96% with a fixed opponent to 55.07%. These results support robustness across the tested opponents and task instances, consistent with our goal of learning strategies that generalize beyond the co-evolving training pair.
As the reviewer points out, improvements on individual replayed games and selected witnesses do not establish sustained improvement in overall strategy quality. We therefore examine performance against fixed opponent pools, retention of gains against individual historical opponents, and preservation of examples no longer individually stored in the frontier.
1. Frontier verification and theoretical analysis.
SPOON’s frontier was introduced to prevent new updates from undoing earlier improvements. As described in Section 3.2, each witness stores the opponent strategy under which an improvement was obtained. An update is accepted only if it improves payoff on the current game against the current opponent and preserves payoff on the checked frontier witnesses against their respective saved opponents.
We analyze convergence of the accepted strategies: under the conditions below, they cannot cycle and eventually stop changing when their induced policy spaces are finite.
To formalize the replay procedure in Section 3.2 and Algorithm 1, a witness w fixes a task instance and a recorded situation from which replay begins. This includes the preceding game history, the corresponding environment state, and any replay randomness. It also fixes σw, the opponent strategy saved when the witness was created.
Let π denote the evaluated player’s policy, induced by its frozen model and textual strategy. Write Vw(π) for the payoff obtained when this player continues from the recorded situation using π against σw. When comparing current and candidate policies, each controls its own continuation; the recorded situation, randomness, and saved opponent remain unchanged. Thus, every historical comparison uses that witness’s original opponent snapshot, consistently with the algorithm.
We consider an idealized exact version of the strategic abstraction in Section 3.1, which groups histories into state–rule branches. We assume that any allowed edit that preserves or improves payoff on a state’s stored representative also preserves or improves payoff on every historical example it represents, with each example replayed against its own saved opponent.
Section 3.2 and Algorithm 1, lines 10–12, already specify checking witnesses associated with affected strategic states. We analyze this step under exact deterministic replay, assuming every affected historical witness remains represented by a checked state and the abstraction remains exact after rerouting, state addition, and witness replacement. These conditions make one representative per state sufficient to preserve earlier improvements. [continue below]