PaperlayerView exact revision on arXiv

Source-linked AI summary

MEMO: Memory-Augmented Model Context Optimization for Robust Multi-Turn Multi-Agent LLM Games

Yunfei Xie, Kevin Wang, Bobby Cheng, Jianzhu Yao, Zhizhou Sha, Alexander Duffy, Yihan Xi, Hongyuan Mei, Cheston Tan, Chen Wei, Pramod Viswanath, Zhangyang Wang

arXiv:2603.09022v2cs.AI

TL;DR

Multi-turn, multi-agent LLM game evaluations suffer from compounding trajectory deviations and prompt sensitivity, which destabilize win-rate estimates and rankings. MEMO optimizes inference-time context by coupling persistent memory with tournament-based exploration and prioritized replay. Across five text-based games, it improves mean win rates for both evaluated models while reducing outcome dispersion under a limited self-play budget.

  • Problem

    Compounding deviations, multi-agent coupling, nondeterminism, and prompt sensitivity make multi-turn game evaluations unstable and comparative rankings unreliable.

  • Method

    MEMO is a weight-free self-play framework that stores structured trajectory insights in persistent memory and combines them with TrueSkill-guided context evolution and prioritized replay.

  • Results

    Across five text-based games, mean win rate rises from 25.1% to 49.5% for GPT-4o-mini and from 20.9% to 44.3% for Qwen-2.5-7B-Instruct, using 2,000 self-play games per task.

  • Takeaways & Limitations

    MEMO substantially improves win rates and reduces outcome dispersion, indicating headroom for context optimization without model-weight updates.

  • Takeaways & Limitations

    Transfer effectiveness depends on structural alignment between source and target games, and transferred heuristics can produce negative transfer when they conflict with native strategies.

Abstract

from arXiv · show

Multi-turn, multi-agent LLM game evaluations often exhibit substantial run-to-run variance. In long-horizon interactions, small early deviations compound across turns and are amplified by multi-agent coupling. This biases win rate estimates and makes rankings unreliable across repeated tournaments. Prompt choice worsens this further by producing different effective policies. We address both instability and underperformance with MEMO (Memory-augmented MOdel context optimization), a self-play framework that optimizes inference-time context by coupling retention and exploration. Retention maintains a persistent memory bank that stores structured insights from self-play trajectories and injects them as priors during later play. Exploration runs tournament-style prompt evolution with uncertainty-aware selection via TrueSkill, and uses prioritized replay to revisit rare and decisive states. Across five text-based games, MEMO raises mean win rate from 25.1% to 49.5% for GPT-4o-mini and from 20.9% to 44.3% for Qwen-2.5-7B-Instruct, using $2,000$ self-play games per task. Run-to-run variance also drops, giving more stable rankings across prompt variations. These results suggest that multi-agent LLM game performance and robustness have substantial room for improvement through context optimization. MEMO achieves the largest gains in negotiation and imperfect-information games, while RL remains more effective in perfect-information settings. All code is open-source and available here: https://github.com/openverse-ai/MEMO

1. Introduction

Multi-turn, multi-agent LLM games are unstable because compounding deviations, interaction coupling, nondeterminism, and prompt sensitivity can distort win rates and rankings. MEMO addresses this by combining persistent memory with exploratory context optimization, improving performance and stability under limited self-play.

  • Multi-turn interaction, agent coupling, and nondeterministic outputs can compound deviations, bias win-rate estimates, and destabilize rankings.
  • Small prompt variations can induce different effective policies and reverse model rankings, making context an optimization target rather than a fixed wrapper.
  • MEMO combines tournament-style context exploration, TrueSkill selection, prioritized replay, and a persistent memory bank that reuses structured trajectory insights without weight updates.
  • Exploration alone yields modest gains, whereas persistent memory makes context optimization cumulative across rounds.
  • 49.5% versus 25.1% mean win rate for GPT-4o-mini and 44.3% versus 20.9% for Qwen-2.5-7B-Instruct across five text-based games.MEMO uses 2,000 self-play games per task and reduces run-to-run variance by 7× to a 6.4% relative standard error from 43.3%.

2. Preliminary and Problem Statement

The paper formalizes multi-turn games and defines inference-time context as prompts plus reusable memory. It evaluates full context-optimization pipelines across independent runs using mean performance and relative standard error.

  • The game is a two-player, turn-based, zero-sum, partially observable Markov game with actions represented by complete model responses.
  • MEMO context combines an instruction prompt with inference-time memory distilled from past self-play trajectories and sampled from a persistent memory bank.
  • Each full-pipeline run produces a final context evaluated on a fixed game suite against multiple opponents and swapped first-move orders.
  • Performance is reported as mean run-level win rate together with relative standard error across independent runs.

3. The MEMO Framework

MEMO evolves candidate contexts through tournament selection and proposal operators while retaining structured trajectory insights in a persistent memory bank and replaying rare states.

  • Tournament-Based Context Optimization: Tournament evaluation uses TrueSkill to retain contexts that perform reliably while penalizing high uncertainty.
  • Tournament-Based Context Optimization: New generations combine random proposals for exploration with memory-augmented updates that incorporate trajectory-derived insights into prompt edits.
  • Tournament-Based Context Optimization: The first generation uses only random proposals because the persistent memory bank is initially empty.
  • Retention: Completed self-play trajectories are reflected into typed insights such as rule clarifications, legality constraints, and strategy priors.
  • Retention: The memory bank adds novel insights, removes conflicting ones, and edits similar ones into more actionable knowledge before reinjection into later play.
  • Prioritized Replay: Prioritized replay stores trajectory prefixes and reproducible environment seeds, sampling rare states according to priority while balancing replay with fresh games.

4. Experiment Setup

The experiments compare MEMO with static prompting, prompt optimization, and reinforcement learning across negotiation, imperfect-information, and perfect-information games using two base models. A fixed configuration and specified self-play budget support the comparison.

  • Game Suite: The benchmark spans negotiation, imperfect-information, and perfect-information games representing cooperation, uncertainty, and long-horizon planning.
  • Baselines: Comparisons include static prompts, feedback-based prompt optimizers such as TextGrad, MIPRO, and GEPA, and RL methods such as UnstableBaselines and SPIRAL.
  • Evaluation: Experiments use GPT-4o-mini and Qwen-2.5-7B-Instruct, with independent optimization runs evaluated against held-out opponents.
  • Configuration: The context-optimization loop uses N=8 candidate contexts, G=5 generations, S=50 self-play games per candidate, and 2,000 total games.
  • Configuration: Memory initialization gives insights to 75% of candidates, while replay uses B=100,000, α=0.6, and β=0.4.

5. Results and Analysis

MEMO improves multi-turn game performance and stability by retaining reusable self-play insights while combining structured exploration, replay, and context optimization. Its gains are strongest when persistent memory is paired with tournament exploration, though transfer can be asymmetric across games and models.

  • Efficiency: 91K output tokens on average let MEMO match or exceed alternatives while using about one-quarter of MIPRO’s 354K tokens and fewer tokens than GEPA’s 113K.Retaining high-value insights concentrates learning on fewer, more informative interactions.
  • Stability: 6.4% average relative standard error for MEMO on GPT-4o-mini compares with 12.4% for MIPRO, indicating lower run-to-run variance.The paper attributes the stability gain to cross-episode information reuse amid compounding early decision errors.
  • Ablations: 50.2% mean win rate results when tournament exploration, Memory, and Replay are combined, versus 23.8% for prompt optimization alone.The ablation ladder identifies Memory as the dominant mechanism, with structured exploration and replay adding further gains.
  • Cross-game transfer: +25.9% transfer from SIMPLETAK to KUHNPOKER and +26.4% from TWODOLLAR to SIMPLETAK show that retained contexts can generalize across game families.The retained context functions as a decision scaffold beyond game-specific heuristics.
  • Cross-model transfer: +35% is Gemini-2.5-Flash-Lite’s largest transferred-context gain, while Grok-4-Fast-Non-Reasoning shows mixed results including +23.3% in TWODOLLAR.Transferred context helps the weaker model uniformly but can conflict with strategies already present in stronger models.

6. Related works

MEMO extends prompt optimization and experiential learning to adversarial multi-agent games by combining tournament-based context evolution with persistent memory. It builds on self-play and interactive evaluation traditions while targeting knowledge reuse across episodes.

  • Experiential prompt optimization: MEMO extends experiential optimization to adversarial multi-agent games by combining tournament-based prompt evolution with a persistent memory bank.The memory bank distills self-play trajectories into insights that persist across optimization rounds.
  • Multi-agent evaluation: Interactive game benchmarks evaluate cooperation, planning, negotiation, and strategic play through multi-turn multi-agent interactions.Examples include TextArena, SPIN-Bench, and GT-Bench.
  • Self-play foundations: Classical and language-based self-play methods close improvement loops through repeated matches, self-generated interactions, or zero-sum reasoning games.Evolutionary approaches additionally perform reflective prompt or program search.

7. Conclusion

MEMO addresses instability in multi-turn multi-agent game evaluation with weight-free self-play that combines persistent retention and exploratory context optimization. Across five games, it improves win rates, reduces outcome dispersion, and transfers learned contexts across games and some model families.

  • Conclusion: MEMO couples a persistent memory bank with tournament-style prompt evolution and prioritized replay without updating model weights.The memory bank distills trajectories into reusable insights, while exploration evaluates evolving contexts.
  • Conclusion: MEMO substantially improves win rates across five text-based games while using 19× fewer games than reinforcement-learning baselines.The framework also reduces outcome dispersion.
  • Conclusion: Ablation studies confirm that both retention and exploration components contribute to the framework’s performance.
  • Conclusion: Learned contexts transfer across games and some model families, suggesting headroom through context optimization rather than weight updates.

A. Prompt Sensitivity Analysis

The appendix shows that minor prompt changes can destabilize model performance and rankings, motivating multi-prompt evaluation. It also specifies MEMO’s context-optimization loop, which evolves contexts through tournaments, TrueSkill selection, reflection, memory, and replay.

  • A. Prompt Sensitivity Analysis: Minor prompt wording changes can induce large shifts in absolute and relative performance, motivating multi-prompt evaluation and calibration.
  • A. Prompt Sensitivity Analysis: Kendall’s τ_b compares model-pair ordering across rankings, with values near 1 indicating similarity, near 0 indicating uncorrelated rankings, and negative values indicating reversals.
  • A. Prompt Sensitivity Analysis: The prompt-pair heatmap reveals considerable dispersion, with absolute performance and pairwise rankings frequently reversing across variants.
  • A.1. Prompt Variants Used in Sensitivity Analysis: Five nearly equivalent KuhnPoker prompts preserve rules and action specifications while varying only stylistic framing, yet produce significant ranking instability.The variants use gladiatorial, technical, spiritual, casual, and classified-spy themes.
  • B. Algorithm Details: MEMO initializes a candidate context population from a base context and random proposals, then evaluates contexts through self-play tournaments.The algorithm injects memory into part of the population before tournament evaluation.
  • B. Algorithm Details: TrueSkill ratings and the score S(c) = μ_c − κσ_c select contexts while accounting for uncertainty in tournament outcomes.
  • B. Algorithm Details: After tournaments, MEMO reflects on trajectories to extract typed insights and generates random or memory-informed proposals for the next population.The two proposal paths allocate candidates to exploration and retention.
  • B. Algorithm Details: Replay-augmented tournaments store trajectory prefixes with inverse-frequency priority and use replay-buffer configuration alongside context evolution.

C. Ablation Study

The ablations examine experience-guided initialization, replay settings, and proposal mechanisms, while the accompanying templates define reflection, memory operations, and game-specific starting contexts. Intermediate memory initialization is favored, and replay benefits from broad coverage with moderate prioritization.

  • C.1. Ablation on Experience-Guided Initialization: Intermediate experience-initialization fractions outperform both extremes across TwoDollar and KuhnPoker, with performance peaking within π ∈ [0.25, 0.75].The default is set to π = 0.75, combining stable priors with unguided exploration.
  • C.2. Replay Ablations: Replay uses buffer capacity B, priority exponent α, and replay gate β; the study varies each parameter independently in TwoDollar.
  • C.2. Replay Ablations: The selected replay defaults are B = 100,000, α = 0.6, and β = 0.4, with larger buffers improving performance and moderate prioritization preserving diversity.The reported optimal range for α is approximately 0.3–0.6; α = 1.0 reduces diversity and degrades performance.
  • C.3. Proposal Operators: Random proposal operators inject controlled stylistic diversity while preserving legality, tool descriptions, and input/output schemas.They edit directives through substitution, insertion or deletion, and reordering.
  • C.4. Reflection and Memory: Trajectory reflection analyzes strategically decisive, high-variance states and extracts actionable insights for later optimization.The reflection template supplies state views and outcome statistics.
  • C.4. Reflection and Memory: The memory-operation template compares new insights with the memory bank and applies add, edit, or remove operations to maintain a coherent library.
  • C.5. Game Prompts: The appendix supplies starting prompts for KuhnPoker, Briscola, SimpleNegotiation, TwoDollar, and SimpleTak, including their game rules, objectives, or action formats.

H. Experimental Setup and Baseline Details

The experiments compare prompt optimization methods, reinforcement-learning baselines, and MEMO’s context-evolution strategy using self-play trajectories and repeated evaluations.

  • Prompt optimization: 5 generations, population size 8, 25 self-play rounds, and 25 evaluation rounds define the prompt-optimization settings.
  • TextGrad: TextGrad analyzes trajectory errors with a text-based loss and propagates feedback back to the system prompt.
  • MIPRO: MIPRO samples examples, proposes prompts and few-shot demonstrations, then uses Bayesian search to select high-performing combinations.
  • GEPA: GEPA combines evaluation scores with explicit feedback, retaining newly proposed prompts when they outperform the initial score.
  • Reinforcement-learning baseline: UnstableBaseline trains Qwen2.5-7B-Instruct with LoRA adapters using REINFORCE under its default configuration.
  • MEMO: MEMO evolves prompt populations through elitism, local edits, random exploration, and memory-augmented updates derived from self-play outcomes.

K. Full Results

The full-results evaluation reports MEMO performance across multiple text-based games and opponent models, covering negotiation, imperfect-information, and perfect-information settings.

  • Evaluation results: MEMO results are reported across three independent trials for GPT-4o-mini and Qwen2.5-7B-Instruct, with mean win rates and standard deviations.
  • Evaluation results: Performance is also broken down by opponent model, with win-rate means and standard deviations across opponents.
  • Evaluation results: Benchmark results compare baseline and MEMO across multiple tasks, using win rates averaged over three evaluation models.
  • Negotiation games: The benchmark includes Simple Negotiation and Two Dollar Game, which require trade-off reasoning, asymmetric-information handling, and opponent-value inference.
  • Imperfect-information games: Kuhn Poker and Briscola represent imperfect-information settings involving hidden cards, betting, trump suits, and long-term tactical decisions.
  • Perfect-information games: Simple Tak represents perfect-information play requiring spatial reasoning, foresight, and blocking of the opponent’s path.

M. Insight Case Analysis

MEMO’s memory bank stores reusable strategic and opponent-modeling insights, with examples showing game-specific tactics and transfer across games.

  • Insight categories: Stored insights fall into game-specific strategic principles and opponent-modeling insights.
  • Game-specific strategic principles: Strategic principles encode domain-specific heuristics that help agents make better decisions and avoid rediscovering tactics across episodes.
  • Game-specific strategic principles: Kuhn Poker insights balance betting aggression with hand strength to avoid predictable play and maximize expected value.
  • Game-specific strategic principles: Briscola insights guide trump-card timing and resource allocation toward point capture rather than indiscriminate use of high-value cards.
  • Opponent modeling and negotiation: Simple Negotiation insights identify asymmetric resource valuations and encourage information gathering before offers.
  • Opponent modeling and negotiation: The Two Dollar insight uses finite round structure as a time-pressure tactic during negotiation.
  • Opponent modeling and negotiation: Opponent-modeling insights account for differing preferences, constraints, and structural features such as round limits when crafting responses.
  • Cross-game transfer: A Simple Negotiation prompt transferred to Simple Tak by encouraging explicit reasoning from the opponent’s perspective.
Loading 2603.09022v2…