Game Theory Improves Multi-Agent LLM Coordination and Reflection

Multi-agent Large Language Model (LLM) systems typically rely on an orchestrator to break down tasks for worker agents and enhance performance through textual reflection. Despite their empirical success, these systems often lack a unified theoretical foundation for understanding coordination, memory improvement, and the role of external verification. This research addresses this gap by proposing a game-theoretic model. The interaction between the orchestrator and worker agents is conceptualized as a bilevel coordination game. Under specific conditions, the workers' local-update game approximates a potential game, where the quality of task decomposition directly influences the equilibrium slack. The paper then analyzes reflection as a stochastic movement through semantic memory states. For free-form reflection, the authors derive bounds and conditions for its effectiveness, and importantly, prove an information-theoretic impossibility: a gate observing only the generated transcript cannot consistently improve performance across diverse environments, unlike an environment-grounded gate. Motivated by this insight, the paper introduces Stochastic Reflective Memory Ascent (SRMA). SRMA is a mechanism that accepts a candidate memory update only if a grounded evaluation risk demonstrably decreases. Under conditions of calibration and sufficient corrective mass, SRMA guarantees exact convergence, which can be geometric or polynomial. The research also provides confidence gating for stochastic evaluation and re-anchoring guarantees for environments that change over time. Experimental instantiations of these concepts, using environment-grounded metrics, validate the predicted coordination and drift laws. A Kimi-based system implementing this framework achieved a 72.2% resolution rate on 500 SWE-bench instances, outperforming a public mini-SWE-agent reference.