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

Multi-turn, multi-agent LLM game evaluations exhibit substantial run-to-run variance. In long-horizon interactions, small deviations compound across turns and are amplified by multi-agent coupling, biasing win rate estimates and destabilizing comparative rankings across repeated tournaments. Prompt choice exacerbates this by inducing different effective policies and interaction dynamics. We address both instability and underperformance in games with MEMO: (Memory-augmented MOdel context optimization), a self-play framework that treats inference-time context as an optimizable, agentic object by coupling retention and exploration. Retention distills self-play trajectories into a persistent memory bank of structured insights that act as priors; exploration combines tournament-style prompt evolution under TrueSkill with prioritized replay over decisive states. Across five text-based games and a 2,000-game budget per task, MEMO raises mean win rate from 25.1% to 49.5% for GPT-4o-mini and from 20.9% to 45.0% for Qwen-2.5-7B, while sharply reducing run-to-run dispersion. These results suggest substantial headroom in multi-agent LLM game performance and robustness can be unlocked through memory, with MEMO achieving gains in negotiation and imperfect-information settings, while RL remains more effective in perfect-information settings. Project website: https://yunfeixie233.github.io/MEMO/.

Game-based benchmarks have become the standard for testing modern AI systems, but they're notoriously unstable. When AI agents play against each other over many turns, small early mistakes snowball. When one agent makes an inconsistent move, it throws off the other's responses. Even tiny changes to instruction wording can flip who wins, making fair comparison nearly impossible. The core insight is simple: MEMO optimizes AI game performance through instructions and strategy alone, without changing the underlying model. It maintains a persistent memory bank of lessons from past games—rule clarifications, successful patterns, failure points—and continuously tests different instruction variants, selecting the ones that win reliably while replaying difficult situations to learn from them. The results stand out. Across five text-based games, MEMO nearly doubled win rates using just 2,000 games: GPT-4o-mini went from 25% to 50%, smaller models from 21% to 45%. More fundamentally, this revealed that much of the performance gap in AI games stems from better instructions and strategies, not from a smarter underlying model. The improvements were also notably more stable across repeated evaluations.