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

The paper introduces MEMO, a memory-augmented self-play framework that optimizes inference-time context through structured memory retention and uncertainty-aware prompt exploration, significantly improving the win rates and run-to-run stability of multi-agent LLMs in long-horizon, imperfect-information games.

The Gist

Here is an explanation of the paper MEMO: Memory-Augmented Model Context Optimization, using simple language and creative analogies.

The Big Problem: The "Forgetful Chess Player"

Imagine you are teaching a very smart, but slightly forgetful, robot how to play a complex game like Poker or Negotiation against another robot.

In the past, researchers tried to teach these robots by having them play thousands of games. However, they noticed a weird problem: The robots were incredibly unstable.

• If the robot played a game on Tuesday, it might win 60% of the time.
• If it played the exact same game on Wednesday with the same instructions, it might only win 20% of the time.

Why? Because in long, multi-turn games, a tiny mistake in the first move can snowball into a disaster by the end. Also, the robots tend to "forget" what they learned in Game #1 by the time they start Game #100. They treat every game as if it's their first time ever playing, even though they've played 99 times before.

The Solution: MEMO (The "Super-Notebook" Strategy)

The authors created a new system called MEMO. Think of MEMO not as a robot that gets "smarter" by changing its brain (which is hard and expensive), but as a robot that gets smarter by keeping a better diary.

MEMO works like a Tournament with a Library. Here is how it works, step-by-step:

1. The Tournament (The "Try Everything" Phase)

Imagine a giant arena where 8 different versions of the robot enter a tournament.

• Each robot has a slightly different "instruction manual" (a prompt) telling it how to play.
• They play against each other.
• Instead of just counting wins, the system uses a special rating system (called TrueSkill, like in online gaming) to figure out which robots are consistently good, not just lucky.

2. The Library (The "Memory" Phase)

This is the secret sauce. After the tournament, the system doesn't just throw away the losers. It looks at the games that were played and asks: "What did we learn?"

• It takes the best moments and the worst mistakes and writes them down in a Shared Notebook (Memory Bank).
• Example: In a negotiation game, the notebook might write: "Hey, if the other guy is holding back, don't just accept the first offer. Wait and see if they value the items differently."
• It also has a "Delete" button. If it writes something that turns out to be wrong later, it erases it so the robot doesn't get confused.

3. The Remix (The "Evolution" Phase)

For the next round of the tournament, the robots get a new instruction manual. But this time, the manual isn't just random.

• Retention: The new manual includes the best tips from the Shared Notebook.
• Exploration: The system also tries some wild, new ideas to see if they work (like trying a crazy new poker bluff).
• Prioritized Replay: Sometimes, the system forces the robots to replay specific, rare, or tricky moments from past games (like a "replay" button in a video game) to make sure they don't forget how to handle those specific situations.

Why is this a Big Deal? (The Results)

The paper tested this on five different text-based games (like Poker, Negotiation, and Card games). Here is what happened:

1. Huge Wins: The robots using MEMO went from winning about 25% of games to winning nearly 50% of games. That's like going from a beginner to a pro just by keeping a better diary.
2. Super Stable: Before, the robots were like a drunk sailor—wobbly and unpredictable. With MEMO, they became steady. The difference between their "best day" and "worst day" vanished.
3. Super Efficient: Other methods tried to teach robots by playing 38,000 games. MEMO achieved the same (or better) results with only 2,000 games. It's like learning to drive by reading a manual and watching a few videos, rather than crashing a car 38,000 times.

The Best Analogy: The "Coach vs. The Student"

• Old Way (Reinforcement Learning): Imagine a student trying to learn chess by playing 10,000 games and changing their brain chemistry every time they lose. It's exhausting and slow.
• Old Way (Prompt Engineering): Imagine a student with a fixed instruction book that never changes, even if they keep making the same mistake.
• The MEMO Way: Imagine a student with a great coach.
  • The coach watches the student play.
  • The coach writes down why the student won or lost in a notebook.
  • Before the next game, the coach gives the student a customized cheat sheet based on the notebook, reminding them of their strengths and correcting their specific weaknesses.
  • The student doesn't need to change their brain; they just need better context (the cheat sheet).

The Takeaway

The paper proves that for AI agents playing complex, multi-turn games, you don't need to retrain the AI's brain. Instead, you just need to give it a persistent memory of what it learned and a smart way to organize that memory.

It turns out that the difference between a clumsy AI and a strategic master isn't how "smart" the AI is, but how well it remembers its past mistakes and shares those lessons with its future self.

Technical Summary

Here is a detailed technical summary of the paper "MEMO: Memory-Augmented Model Context Optimization for Robust Multi-Turn Multi-Agent LLM Games."

1. Problem Statement

The paper addresses two critical challenges in evaluating Large Language Models (LLMs) within multi-turn, multi-agent game environments:

• Run-to-Run Instability: Small early deviations in model outputs compound over turns, especially in multi-agent settings where one agent's inconsistent response perturbs the other's best response. This leads to high variance in win-rate estimates and unreliable model rankings across repeated tournaments.
• Context Sensitivity: Evaluation outcomes are highly sensitive to prompt variations. Minor changes in wording can induce different effective policies and even reverse model rankings, making single-prompt evaluations unrepresentative of true capability.
• Limitations of Existing Methods:
  • Static Prompts (CoT, ToT): Do not adapt to failure modes emerging during interaction.
  • Standard Prompt Optimization (TextGrad, MIPRO, GEPA): Often lack persistent memory, treating each optimization run as independent. They fail to retain insights across rounds, leading to high variance and inefficient learning.
  • Reinforcement Learning (RL): While effective, RL requires updating model weights and massive sample budgets (e.g., 38,000+ games), making it computationally expensive and unstable in sparse-reward, multi-turn settings.

2. Methodology: The MEMO Framework

MEMO (Memory-augmented Model context optimization) is a weight-free self-play framework that optimizes the inference-time context (prompts and priors) rather than model weights. It couples Exploration (tournament-style context evolution) with Retention (persistent memory).

Core Components:

1. Tournament-Based Context Optimization (Exploration):

   • Maintains a population of $N$ candidate contexts.
   • Evaluates candidates via self-play against a baseline agent.
   • Uses TRUESKILL, a Bayesian skill rating system, to score contexts based on win/loss outcomes while penalizing high uncertainty. This selects robust contexts rather than those that got lucky in a few games.
   • Generates new candidates via Random Proposals (style-guided edits) and Memory-Augmented Updates (incorporating insights from the memory bank).

2. Trajectory Reflection and Memory Bank (Retention):

   • After each generation, the system samples completed self-play trajectories.
   • An LLM performs Reflection to extract structured, typed insights (e.g., strategy priors, rule clarifications, opponent modeling) from these trajectories.
   • These insights are managed in a Persistent Memory Bank using database-style CRUD operations:
     • Add: New unique insights.
     • Edit: Merging similar insights to generalize or improve them.
     • Remove: Discarding conflicting or contradictory insights to prevent misleading the agent.
   • In subsequent generations, a fraction of candidates are initialized with a sampled subset of this memory bank, acting as priors.

3. Prioritized Replay:

   • To ensure rare but decisive states are revisited, MEMO maintains a Replay Buffer.
   • It stores trajectory prefixes and uses an inverse-frequency scoring mechanism to prioritize sampling rare states (those encountered infrequently) during self-play. This ensures the agent learns from edge cases rather than just common patterns.

3. Key Contributions

1. Demonstration of Context Sensitivity: The authors show that multi-turn LLM game rankings are unstable under minor prompt variations, motivating the need for robust, optimized context rather than fixed wrappers.
2. Unified Framework: Introduction of a framework combining structured reflection, persistent memory, context evolution, and prioritized replay. This allows agents to accumulate and reuse knowledge across rounds without discarding it after each update.
3. Training Efficiency and Stability: MEMO achieves significant performance gains with drastically fewer interactions compared to RL baselines and reduces run-to-run variance, providing more reliable model rankings.

4. Experimental Results

The framework was evaluated across five text-based games (SimpleNegotiation, TwoDollar, KuhnPoker, Briscola, SimpleTak) using GPT-4o-mini and Qwen-2.5-7B-Instruct.

• Performance Gains:

  • GPT-4o-mini: Mean win rate increased from 25.1% (baseline) to 49.5%.
  • Qwen-2.5-7B-Instruct: Mean win rate increased from 20.9% to 44.3%.
  • MEMO outperformed other prompt optimization methods (TextGrad, MIPRO, GEPA) and was competitive with RL baselines.

• Sample Efficiency:

  • MEMO achieved these results using only 2,000 self-play games per task.
  • This is 19× fewer games than the RL baseline (which required ~38,000 games).
  • In Kuhn Poker, MEMO reached a 60% win rate with 2,000 games, whereas the RL baseline required 38,000.

• Stability:

  • MEMO reduced run-to-run variance significantly. The Relative Standard Error (RSE) dropped from 44.9% (baseline) to 6.4% for GPT-4o-mini, indicating highly stable rankings across prompt variations.

• Ablation Studies:

  • Memory is dominant: Adding a memory bank alone provided a +10.4% gain over prompt optimization alone.
  • Synergy: The combination of Tournament-based exploration and Memory yielded the highest gains (+24.3% over baseline), proving that structured exploration is needed to populate the memory with high-signal insights.
  • Generalization: Contexts learned in one game (e.g., SimpleNegotiation) transferred effectively to others (e.g., SimpleTak), improving performance by +25.9% in some cross-game scenarios.

5. Significance and Conclusion

• Paradigm Shift: The paper suggests that context optimization is a highly effective alternative to weight-based RL for improving multi-agent LLM performance, particularly in settings with sparse rewards and long horizons.
• Robustness: By treating context as an optimizable object with persistent memory, MEMO solves the instability inherent in multi-turn evaluations, making model comparisons more fair and reproducible.
• Efficiency: The approach offers a "sweet spot" between the low cost of static prompting and the high cost of RL, achieving superior results with minimal computational overhead.
• Applicability: The framework is particularly effective in negotiation and imperfect-information games, where strategic depth and opponent modeling are crucial, while RL remains slightly more effective in perfect-information settings.

In summary, MEMO demonstrates that accumulating reusable strategic insights via a persistent memory bank, combined with uncertainty-aware tournament selection, allows LLMs to master complex multi-agent games with high stability and sample efficiency.