acceptodds
Under review as a conference paper at ICLR 2027

SPOON: Strategy-based Prompt Optimization for Multi-Agent LLM Games

Abstract

LLM agents can collaborate, negotiate, and compete in multi-agent settings where each player’s success depends on the actions of others. While multi-agent games provide a useful formalization of these settings, improving LLM agents’ performance in these games often relies on reinforcement learning, requiring access to model parameters and costly training across many optimization iterations. To address this, we propose SPOON, a strategy-based prompt optimizer that represents each player’s strategy as explicit rules written in text and refines them without updating model weights. Our strategic abstractions compress many game histories into shared states, allowing one rule update to improve behavior across multiple situations. Explicit strategies enable our method to examine how both players’ rules interact and guide structured best-response search, directly improving each player’s strategy in response to another as they co-evolve across optimization iterations. Across 19 existing benchmarks spanning classical multi-agent games, practical multi-agent applications, and an extension to prompt optimization for single-agent tasks, our method improves optimization efficiency and held-out performance compared with training-based and prompt optimization baselines.

Primary area:
foundation or frontier models, including LLMs
Keywords:
multi-agent interaction, multi-agent games, prompt optimization, black-box optimization, explicit strategies, co-evolution, self-play

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9Ft5OpenReview ↗
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
  1. 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
  1. 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.

  2. 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
  1. 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.

  2. 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
AuthorsOpenReview ↗

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 ww 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\sigma_w, the opponent strategy saved when the witness was created.

Let π\pi denote the evaluated player’s policy, induced by its frozen model and textual strategy. Write Vw(π)V_w(\pi) for the payoff obtained when this player continues from the recorded situation using π\pi against σw\sigma_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]

AuthorsOpenReview ↗

Response to reviewer 9Ft5 (2/4)

Index player ii’s accepted updates by nn, and let πin\pi_i^n denote its policy after nn accepted updates. An update from πin\pi_i^n to πin+1\pi_i^{n+1} records a witness wnw_n satisfying

Vwn(πin+1)>Vwn(πin).V_{w_n}(\pi_i^{n+1}) > V_{w_n}(\pi_i^n).

Every subsequent accepted update preserves this improvement under the stated conditions, including after the witness is replaced. Hence, for every m>nm>n,

Vwn(πim)≥Vwn(πin+1)>Vwn(πin).V_{w_n}(\pi_i^m) \geq V_{w_n}(\pi_i^{n+1}) > V_{w_n}(\pi_i^n).

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 episode01020306090120150
Briscola win rate against the fixed four-opponent pool (%)25.644.163.564.265.465.965.766.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 iteration0150300450900135018002250
HotpotQA accuracy against the fixed four-adversary pool (%)39.850.254.857.460.361.661.462.2
HotpotQA accuracy on original test questions, one continued submitted run (%)41.6755.6761.3364.6766.3367.3367.0067.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]

AuthorsOpenReview ↗

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)SPOONWithout frontier verification
Briscola, episodes 0–300.88.0
Briscola, episodes 30–1501.211.9
HotpotQA, iterations 0–4501.07.6
HotpotQA, iterations 450–22501.410.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:

NashConv⁡(π1,π2)=∑i=12[max⁡πi′Ji(πi′,π−i)−Ji(πi,π−i)].\operatorname{NashConv}(\pi_1,\pi_2) = \sum_{i=1}^{2} \left[\max_{\pi_i'} J_i(\pi_i',\pi_{-i}) - J_i(\pi_i,\pi_{-i})\right].

Here, JiJ_i 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.

AuthorsOpenReview ↗

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 conditionHotpotQA test score (%)
Optimize solver on original questions; no adversary57.47 ± 0.69
Optimize solver; adversary strategy fixed58.93 ± 0.55
Optimize solver; four adversary strategies fixed59.73 ± 0.55
SPOON: solver–adversary co-evolution64.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 conditionRewardBench Chat-Hard accuracy (%)
Update judge; generator strategy fixed75.09 ± 0.53
Update generator; judge strategy fixed74.65 ± 0.45
Update generator, then judge76.40 ± 0.45
Update judge, then generator76.10 ± 0.35
SPOON: generator–judge co-evolution80.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.

Reviewer_STbNOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces SPOON, a prompt optimization framework for multi-agent games for LLM. It represents the agent's strategies as sets of natural-language strategic state with corresponding behavior rules. Then the method iteratively improves these strategies via structured search. The experiment shows that SPOON improves performance across many games, outperforming previously commonly used prompt optimization frameworks and SFT and RL training methods.

Critical strengths
  1. The method is clear and clean. It introduces an interpretable strategy for LLM to learn its failures during gameplay and make controllable edits to its prompt.

  2. I appreciate that the evaluation and experiment are comprehensive across many different games, comparing different methods and retraining some of the baseline methods. The author provides a detailed ablation study to isolate the contribution of each component.

Critical weaknesses
  1. The method relies on an optimizer LLM to propose strategy revisions and selects among them using replay-based payoff checks. But the paper doesn't provide a direct evaluation of whether these revisions reliably improve the the expected payoff.

  2. The paper provides limited qualitative analysis of the learned strategies. Although the paper provides some examples, but it lacks sufficient analysis. More qualitative examples are needed to assess what strategic knowledge the method learns and how that knowledge transfers across situations.

Questions for authors
  1. Please see and address the questions in the weaknesses.

  2. Do the gains hold in longer games? Since in longer game, the context and errors in memory may accumulate. Does the method have any mechanism for long-horizon situations?

  3. Could the authors provide the prompts for strategy initialization, state selection, and edit generation, together with the proposal budget? Some implementations are missing in the manuscript.

3 comments
AuthorsOpenReview ↗

Response to reviewer STbN (1/3)

We thank the reviewer for the insightful comments.

Critical Weakness 1: Expected-Payoff Improvement and Retention

Following the reviewer’s suggestion, we add two evaluations: a paired before/after comparison of accepted revisions on held-out instances, and historical cross-play to test whether subsequent revisions preserve the gains. These directly examine expected-payoff improvement and its retention beyond the replay examples used for acceptance.

Our submitted results provide aggregate evidence of stronger strategies: held-out performance gains over baselines provide aggregate evidence of improved expected payoff for the final strategies under the respective evaluation conditions.

To isolate the contribution of individual revisions, we evaluate each accepted update separately.

1. Acceptance checks. As described in §3.2, an update must improve payoff on the current game against the current opponent and preserve payoff on checked frontier witnesses against their saved opponents. These are local checks; the following audit tests whether improvements extend beyond the checked examples.

2. Direct revision audit. For each accepted revision, we compare the preceding policy πit,−\pi_i^{t,-} and updated policy πit,+\pi_i^{t,+} against the same frozen opponent σt\sigma_t:

Δt=Ji(πit,+,σt)−Ji(πit,−,σt).\Delta_t = J_i(\pi_i^{t,+},\sigma_t) - J_i(\pi_i^{t,-},\sigma_t).

We estimate this difference using paired complete interactions on the same held-out instances. We use five runs per task: Qwen2.5-7B-Instruct with 30 optimization episodes for Briscola, and Qwen3-8B with 450 update attempts over the 450-example optimization pool for HotpotQA. Both players and the optimizer use the respective backbone.

  • Briscola: Each accepted revision to either player is evaluated on 50 deals in both seats (100 games per policy). Payoff is terminal reward rescaled to [0,1][0,1].
  • HotpotQA: Each accepted solver revision is evaluated on a fixed 300-question panel produced by its frozen adversary, using validated rewrites or the original question if rewriting fails. Payoff is answer correctness.
TaskAccepted revisionsMean payoff change, pp (95% CI)Positive / unchanged / negative estimates
Briscola60+2.7 [1.5, 3.9]47 / 8 / 5
HotpotQA solver100+0.9 [0.4, 1.5]74 / 15 / 11

We average changes within runs, then across seeds; 95% t-intervals use the five run means.

Accepted revisions increase estimated expected payoff on average in all five runs for both tasks. Positive estimates occur for 78.3% of Briscola revisions and 74.0% of HotpotQA solver revisions.

3. Historical cross-play and frontier verification. We test whether later updates undo gains against earlier opponents, extending the same five runs to 150 Briscola episodes and 2250 HotpotQA iterations.

TaskOpponent snapshotsPlayer checkpoints
Briscola (episodes)0, 10, 30, 1500, 10, 20, 30, 60, 90, 120, 150
HotpotQA (iterations)0, 150, 450, 22500, 150, 300, 450, 900, 1350, 1800, 2250

For each frozen opponent, checkpoints use identical held-out cases: 25 Briscola deals in both seats or a fixed 300-question HotpotQA panel generated by that adversary.

We measure the largest payoff drop from any earlier to any later checkpoint against the same opponent, or zero if payoff never decreases. This detects temporary regressions even if performance later recovers.

We calculate drops separately for the original and extended optimization windows below. For each opponent, only checkpoints at or after it was saved are eligible, with at least two required per window. Final opponent snapshots are therefore excluded from this metric. We average across eligible opponents and five runs, and across both player roles for Briscola.

The ablation removes only frontier checks, retaining co-evolution, strategic structure, current-game improvement checks, initialization, models, proposal budget, and optimization horizon. Both methods face identical SPOON opponent snapshots and held-out cases.

Average largest payoff drop, pp; lower is betterSPOONWithout frontier verification
Briscola, episodes 0–300.88.0
Briscola, episodes 30–1501.211.9
HotpotQA, iterations 0–4501.07.6
HotpotQA, iterations 450–22501.410.4

Frontier verification reduces regressions in both windows. Final Briscola win rate against the complete, equally weighted opponent pool, including final snapshots, is also higher: 66.1% versus 58.0%.

The direct revision audit shows positive average changes in estimated expected payoff; historical cross-play shows that frontier verification helps preserve performance during subsequent adaptation. We will include the protocols and per-run results in the revised manuscript.

AuthorsOpenReview ↗

Response to reviewer STbN (2/3)

Critical Weakness 2: Qualitative Analysis

Following the reviewer’s suggestion, we present two case studies tracing failures, new strategies, and transfer to held-out situations. SPOON pairs IF conditions defining strategic states with THEN behavioral rules (§3.1). Histories sharing a state use the same rule, so one correction can benefit other inputs with the same strategic problem (§2.2).

In Briscola, each player contributes one card to a trick; the winner collects both cards’ points. A trump beats any non-trump; otherwise, a responding card must match the opponent’s suit and outrank it. SPOON learned to distinguish winnable tricks from those where it should limit points conceded.

The original strategy was:

IF: All decision histories.

THEN: Play the first card in hand.

Two separate game instances exposed different failures, prompting two new state–rule pairs.

First instance: an available win was missed. Holding [3♦, 3♥, K♠] with spades as trump, the agent faced K♥. The original rule played 3♦ and lost, but 3♥ outranks K♥ and could win without spending a trump.

SPOON added:

IF: The opponent has played a card, and at least one card in hand can win the trick.

THEN: Choose a winning card, preferring non-trumps and then lower-point cards.

This changed the action to 3♥, winning the trick while retaining K♠.

Second instance: an unwinnable trick cost a valuable card. Holding [3♥, 6♣, Q♥] with diamonds as trump, the agent faced 6♠. No card could win. The original rule played the 10-point 3♥ instead of the zero-point 6♣.

SPOON added:

IF: The opponent has played a card, and no card in hand can win the trick.

THEN: Choose a losing card, preferring non-trumps and then lower-point cards.

This changed the action to 6♣: the trick was still lost, but no card points were conceded. The conditions distinguish taking an available win from preserving valuable cards when winning is impossible.

Both rules transferred to held-out situations. With the strategy frozen, we observed these decisions in a reserved evaluation game, with clubs as trump throughout:

Cards heldOpponent’s cardStrategic state selectedAction
[2♦, Q♥, 7♠]J♥A winning card existsPlay Q♥ and win without using a trump.
[A♠, 3♦, K♦]4♣No winning card existsDiscard the 4-point K♦, retaining the 10-point three and 11-point ace.
[A♦, 3♥, A♣]K♠A winning card existsPlay A♣, the only winning card.

The first and third histories selected the same strategic state but required different actions; the second selected the state learned from the unwinnable trick. Neither rule names specific cards or suits. One correction per strategic state guided different hands without further optimization.

HotpotQA combines information from multiple passages. Following GEPA’s task setup (§4.3), our pipeline summarizes an initial retrieval, generates a second query, summarizes the additional evidence, and produces an answer. SPOON learns IF/THEN strategies within these existing modules.

One question asked which university the founders of the sorority led by Yvonne Kennedy came from. The initial evidence identified Delta Sigma Theta but not the university. The second query failed to retrieve it, and the system answered “no.”

SPOON added this rule to the second-query module:

IF: The first summary identifies the entity needed to answer the question, but does not provide the requested fact about that entity.

THEN: Search for that entity by name together with the missing fact requested by the question.

The resulting query was:

“What university did the founders of Delta Sigma Theta sorority come from?”

It retrieved the missing founding information, enabling the answer Howard University. The edit targeted the search instruction responsible for the missing evidence.

The same rule transferred to held-out questions involving different entities and relations:

Held-out questionEntity identified by the first retrievalSecond query generated using the learned ruleFinal answer
What is the birth date of the author whose stories inspired Certain Women?Maile MeloySearch for Maile Meloy’s birth date.January 1, 1972
In which city is the manufacturer of the Suzuki F10D engine headquartered?Maruti SuzukiSearch for Maruti Suzuki’s headquarters city.New Delhi

Despite different subjects, these intermediate histories share one strategic state: the relevant entity is known, while the requested fact is missing. The same THEN directs a targeted search, without separate instructions for sororities, authors, or manufacturers.

In the appendix, we will provide complete before/after strategy entries and annotated trajectories linking each failure to its IF/THEN update and subsequent applications.

AuthorsOpenReview ↗

Response to reviewer STbN (3/3)

Q2 Analysis of Longer Games

Following the reviewer’s suggestion, we clarify the horizons of our reported games and provide an additional evaluation of longer interactions.

The results in Table 1 show performance improvements over the published MEMO baseline on several multi-turn games:

  • Briscola: A complete game comprises 20 tricks—40 card plays, with 20 decisions per player. SPOON achieves 69.33% win rate versus 31.10% for MEMO.
  • TwoDollar: Games allow up to 20 individual negotiation turns. SPOON achieves 50.67% versus 48.40% for MEMO.
  • SimpleTak: The 4×4 setting allows up to 16 legal placements. SPOON achieves 42.00% versus 34.00% for MEMO.

These results demonstrate that the reported improvements extend beyond short exchanges.

SPOON provides repeated state-dependent rule selection and verification through terminal outcomes. At each decision, it selects the applicable IF condition from the current available history and supplies the corresponding THEN rule to the acting model (§3.1). The intended behavior is therefore explicitly specified again as the situation changes. During optimization, candidate edits are checked using the resulting terminal payoff (§3.2), so verification considers their consequences over the completed game. These mechanisms support consistent strategy execution and learning from delayed outcomes.

To directly assess whether gains persist as interaction histories grow, we extended SimpleNegotiation from 10 to 20 and 40 individual turns. We retain the paper’s evaluation protocol (§4.1; Table 6), changing only the within-game horizon: the same model, decoding, opponents, observation format, scoring, and seed protocol, with 450 evaluation games per method and horizon. SPOON and the unstructured-strategy control are optimized separately at each horizon using the same 30-episode optimization budget and proposal cap.

Individual turns per gameUnstructured strategySPOON
10 — original, Tables 1 and 643.11%49.33%
20 — additional evaluation41.11%48.89%
40 — additional evaluation37.78%46.89%

Across the reported multi-turn games and the extended SimpleNegotiation evaluation, SPOON retains its performance gains. The controlled extension further shows that its advantage persists when the same game’s interaction horizon quadruples.

Q3 Prompts and Proposal Budget

Initialization uses fixed task-specific IF/THEN strategies and role instructions; there is no separate initialization call.

The proposal budget is at most 3 attempts per update, except for mathematical reasoning (2) and the HotpotQA adversary (1; the solver uses 3).

We will provide the complete prompts and configurations in the appendix: initial strategies, player state-selection prompts, optimizer state-selection and edit-generation prompts, structured output schemas, and feedback after unsuccessful proposals. We will also specify candidate-selection and stopping rules, retry handling, and token limits.

Reviewer_gs1UOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a method for iteratively updating LLM agents’ prompts in multi-agent systems. Two agents take turns refining their strategies under the guidance of an optimizer agent. The optimizer can check the history of the system and select parts of the overall prompt to modify according to predefined rules. Across classical multi-agent games, adversarial jailbreaking, reward judging, cooperative mathematical reasoning, and single-agent tasks, the paper reports better or comparable performance than training and prompt optimization baselines.

Critical strengths

This work reframes prompt optimization in multi-agent settings from a game theory. The pipeline doesn't need to access to the model weights and finetune the model. As closed source models become increasingly capable while their weights remain inaccessible, this direction has substantial practical relevance.

Critical weaknesses

The paper does not provide any convergence analysis. I think its very important, if the paper is based on game theory. In each round, SPOON lets the losing agent improve against its opponent’s current strategy. Such dynamics can lead to cycles of counterstrategies rather than convergence in some of the games. The authors should characterize its convergence behavior through theoretical analysis or empirical evaluation.

Questions for authors
  1. Can the authors provide a convergence analysis? A theoretical proof would be preferable, but empirical evidence would also be helpful if such a proof is unavailable.
  2. Are the baseline results taken directly from prior papers rather than reproduced by the authors?
  3. How well does this method work on highly capable closed source models, such as frontier models from Anthropic and OpenAI? The paper emphasizes its relevance to closed source models but provides no experiments on these frontier models. Given their already strong reasoning capabilities, it remains unclear whether the proposed method would yield meaningful improvements.
4 comments
AuthorsOpenReview ↗

Response to reviewer gs1U (1/4)

We thank the reviewer for the insightful comments and address the concerns raised below.

Critical Weakness and Q1: Convergence analysis [Addressed in Parts 1–3]

Following the reviewer’s suggestion, we provide three additional analyses: conditional convergence analysis, extended optimization and historical cross-play on Briscola and HotpotQA, and exact best-response evaluation on KuhnPoker. These analyses establish conditions that prevent cycling, show empirical performance stabilization during extended optimization, and demonstrate convergence to a Nash equilibrium within 30 iterations in the evaluated KuhnPoker game.

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.

However, as the reviewer points out, evaluating the final strategies alone does not establish whether the optimization process stabilizes or cycles. We therefore characterize convergence through complementary theoretical and empirical analyses: conditions that prevent cycling, performance stabilization during extended optimization, preservation of gains against earlier opponents, and exact equilibrium evaluation in the tractable KuhnPoker setting.

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 ww 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\sigma_w, the opponent strategy saved when the witness was created.

Let π\pi denote the evaluated player’s policy, induced by its frozen model and textual strategy. Write Vw(π)V_w(\pi) for the payoff obtained when this player continues from the recorded situation using π\pi against σw\sigma_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]

AuthorsOpenReview ↗

Response to reviewer gs1U (2/4)

Index player ii’s accepted updates by nn, and let πin\pi_i^n denote its policy after nn accepted updates. An update from πin\pi_i^n to πin+1\pi_i^{n+1} records a witness wnw_n satisfying

Vwn(πin+1)>Vwn(πin).V_{w_n}(\pi_i^{n+1}) > V_{w_n}(\pi_i^n).

Every subsequent accepted update preserves this improvement under the stated conditions, including after the witness is replaced. Hence, for every m>nm>n,

Vwn(πim)≥Vwn(πin+1)>Vwn(πin).V_{w_n}(\pi_i^m) \geq V_{w_n}(\pi_i^{n+1}) > V_{w_n}(\pi_i^n).

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 episode01020306090120150
Briscola win rate against the fixed four-opponent pool (%)25.644.163.564.265.465.965.766.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 iteration0150300450900135018002250
HotpotQA accuracy against the fixed four-adversary pool (%)39.850.254.857.460.361.661.462.2
HotpotQA accuracy on original test questions, one continued submitted run (%)41.6755.6761.3364.6766.3367.3367.0067.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]

AuthorsOpenReview ↗

Response to reviewer gs1U (3/4)

3. Historical cross-play and the contribution of frontier verification.

A rising pool average can hide a loss of performance against an individual opponent. We therefore ask: after learning to handle an opponent, how much does the player’s performance against that same opponent subsequently decline?

We hold each historical opponent fixed and evaluate later player checkpoints against it 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. Because the opponent and evaluation deals do not change, 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%, for example, 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. Within each window, we use only player checkpoints at or after the opponent was saved, and require at least two checkpoints for comparison. The table averages these largest drops across the included opponents and five optimization seeds, and across both roles for Briscola.

To assess frontier verification, we compare SPOON with an ablation that removes only the frontier checks. It retains co-evolution, strategic structure, current-game improvement checks, and the same initialization, models, proposal budget, and iteration horizon. Both methods are evaluated against the same SPOON reference opponents and the same held-out cases defined above.

Average largest drop against a fixed earlier opponent (percentage points; lower is better)SPOONWithout frontier verification
Briscola, episodes 0–300.88.0
Briscola, episodes 30–1501.211.9
HotpotQA, iterations 0–4501.07.6
HotpotQA, iterations 450–22501.410.4

For example, during Briscola episodes 30–150, the average largest loss against an earlier opponent is 1.2 points with SPOON, compared with 11.9 points 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 fraction of update–witness comparisons with a regression, 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 the role of frontier verification 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:

NashConv⁡(π1,π2)=∑i=12[max⁡πi′Ji(πi′,π−i)−Ji(πi,π−i)].\operatorname{NashConv}(\pi_1,\pi_2) = \sum_{i=1}^{2} \left[\max_{\pi_i'} J_i(\pi_i',\pi_{-i}) - J_i(\pi_i,\pi_{-i})\right].

Here, JiJ_i 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 theory gives conditional stabilization without cycling; Briscola largely stabilizes by episode 30; HotpotQA improves beyond iteration 450 and approaches a plateau over 1350–2250; and binary-payoff KuhnPoker reaches an exactly verified Nash equilibrium. Frontier checks improve retention during continued adaptation. We will add these analyses and results to the revised manuscript.

AuthorsOpenReview ↗

Response to reviewer gs1U (4/4)

Q2: Baseline Sources and Re-evaluation.

The baseline values in Tables 1–5 are taken from the cited papers, as stated in the submitted captions and experimental sections. We retained these as traceable reference results from published implementations and training runs, and have checked the quoted values against their source tables.

We additionally evaluated baselines using available checkpoints and released prompts/programs, alongside the frozen SPOON strategies. These evaluations use shared test inputs and scoring procedures, including the same safety judge and answer extraction, while retaining each baseline’s prescribed prompts and decoding settings. For classical games, all methods face the same opponent pool. These are evaluations of the available models and prompts; baseline training was not repeated.

The re-evaluated scores are as follows (all percentages):

  • Classical games: Default prompting achieves 20.67 mean win rate across the five games, compared with the published 20.90.
  • Safety: On HarmBench ASR / WildJailbreak benign compliance / XSTest benign compliance, base Qwen achieves 28.13 / 98.80 / 95.20, and Self-RedTeam achieves 15.73 / 98.40 / 95.60.
  • RewardBench: On Chat / Chat-Hard, rubric prompting achieves 74.08 / 63.51, Rubric-RM (SFT) 88.38 / 74.56, and Rubric-ARM (RL) 89.55 / 79.39.
  • Mathematical reasoning: CoT achieves 50.64 mean accuracy across the seven benchmarks, compared with the published 50.24.
  • Single-agent tasks: On IFBench / HotpotQA / HoVer, the unoptimized pipelines achieve 36.73 / 42.00 / 35.67, and GEPA achieves 38.44 / 61.67 / 52.00.

These results closely agree with the published references. The revised appendix provides the full per-task results alongside SPOON, checkpoint and prompt versions, and evaluation configurations. We explicitly distinguish independently evaluated results from published reference results throughout.

Q3: Evaluation with a Highly Capable Closed-Source Model.

Following the reviewer’s suggestion, we evaluate whether SPOON improves an already highly capable closed-source model on Briscola and HotpotQA. Both players and the optimizer use Claude Opus 5.5 with high reasoning effort.

TaskDefault unoptimized promptingMEMO / GEPASPOON
Briscola: held-out win rate (%)66.071.074.0
HotpotQA: held-out accuracy (%)68.074.076.3

The unoptimized baselines use MEMO’s default Briscola prompting and GEPA’s default HotpotQA pipeline and prompts, respectively, with the same Opus reasoning settings as SPOON.

We follow our paper’s task setups and SPOON optimization procedure, retaining 30 optimization episodes for Briscola and the 450-example optimization pool for HotpotQA. We rerun MEMO using the authors’ official implementation and published 2,000-game configuration. For HotpotQA, we rerun the official GEPA artifact with its original retrieval pipeline, 6,871-rollout budget, and 150-training/300-validation split.

SPOON improves unoptimized Opus 5.5 by 8.0 and 8.3 percentage points on Briscola and HotpotQA, respectively, and achieves higher mean scores than MEMO and GEPA. These results show that SPOON remains useful for Opus 5.5 on both tasks despite its strong reasoning capabilities. We will include these experiments and their evaluation details in the revised manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

High Level Summary of the Rebuttal

We thank the reviewers for their thoughtful and constructive feedback. SPOON represents LLM agents’ strategies as explicit natural-language condition–rule pairs and refines them through structured search and co-evolution, without updating model weights. Across 19 existing benchmarks spanning classical multi-agent games, practical multi-agent applications, and an extension to prompt optimization for single-agent tasks, SPOON improves optimization efficiency and held-out performance compared with training-based and prompt optimization baselines.

We appreciate reviewers’ recognition of SPOON’s “substantial practical relevance” for models with inaccessible weights (gs1U), its interpretable strategies that support inspection and controllable edits (STbN, 9Ft5), and its “clear and clean” design (STbN). We also appreciate STbN’s recognition of the comprehensive evaluation across many games and competing methods, and the detailed ablation study isolating each component’s contribution.

In response to the reviewers’ feedback, we provide:

  1. Strategic Stability and Convergence (gs1U, 9Ft5). We give theoretical conditions under which accepted strategies cannot cycle and eventually stop changing. We also run optimization five times longer on Briscola and HotpotQA and evaluate against fixed sets of saved opponent strategies. Performance stabilizes, and frontier verification helps preserve earlier gains. In binary-payoff KuhnPoker, exact best-response evaluation verifies a Nash equilibrium within 30 episodes.

  2. Direct Revision Evaluation (STbN). To address whether accepted revisions improve expected payoff beyond the replay examples used for acceptance, we conduct paired before/after evaluations on held-out instances against frozen opponents. Mean estimated payoff increases by 2.7 percentage points on Briscola and 0.9 points on HotpotQA across five runs.

  3. Practical Motivation and Co-evolution (9Ft5). We clarify why safety alignment, preference judging, and cooperative reasoning provide controllable, replayable two-agent workflows. In additional experiments under matched optimization-token budgets, co-evolution improves HotpotQA accuracy from 59.73% with a fixed adversary pool to 64.73%, and RewardBench Chat-Hard accuracy from 76.40% with sequential optimization to 80.44%.

  4. Closed-Source Model Evaluation (gs1U). To evaluate whether SPOON provides meaningful gains on highly capable closed-source models, we ran new experiments using Claude Opus 5.5 at high reasoning effort. SPOON improves unoptimized prompting by 8.0 points on Briscola and 8.3 points on HotpotQA, outperforming rerun MEMO and GEPA baselines, respectively.

  5. Qualitative Analysis and Transfer (STbN). We provide Briscola and HotpotQA case studies tracing failures to specific strategy revisions and their application to held-out situations. These examples illustrate what strategic knowledge SPOON learns and how it generalizes across held-out situations.

  6. Longer Interactions (STbN). We extend SimpleNegotiation from 10 to 20 and 40 turns, optimizing strategies separately at each horizon. SPOON retains its advantage, achieving 46.89% versus 37.78% for unstructured strategies at 40 turns. We also clarify the roles of repeated state-dependent rule selection and terminal-payoff verification.

  7. Baseline Provenance (gs1U). We distinguish published reference results from new evaluations using available checkpoints and released prompts or programs under shared test inputs and scoring procedures.

  8. Implementation Details (STbN). We clarify fixed-strategy initialization and task-specific proposal budgets. Complete prompts, output schemas, and retry and stopping rules will be included in the revised appendix.

We next address all reviewers’ concerns separately. We will also add these changes to the final manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.