Bilevel Coordinated Reflection: A Game-Theoretic Approach to Multi-Agent LLM Systems
Yihang Chen, Meng Fang, Jun Wang and colleagues (UCL, Liverpool) give orchestrator-worker multi-agent systems a formal account, modeling them as a bilevel coordination game and proving that transcript-only reflection gates cannot work.
Ask this paper
Coordination as an approximate potential game: Under bounded coupling the workers' local-update game is an approximate potential game whose equilibrium slack is controlled by decomposition quality, which puts a number on 'the orchestrator's task split determines how well the team converges'.
An impossibility result with teeth: No gate that observes only the generated transcript can improve uniformly over text-indistinguishable environments, whereas an environment-grounded gate can. That is a formal argument against reflection loops that only read their own output.
SRMA, the constructive half: Stochastic Reflective Memory Ascent accepts a candidate memory only when a grounded evaluation risk strictly decreases, with proven exact, geometric or polynomial convergence and order-tight rate regimes.
Empirically checked, not just proved: On 500 SWE-bench instances the complete Kimi-based system resolves 72.2 percent against a 70.8 percent mini-SWE-agent reference.
Why it matters: It formalizes what practitioners learned the hard way, that self-reflection reading only its own transcript drifts, and that grounding the gate in the environment is the thing that fixes it.
Abstract
Multi-agent LLM systems commonly use an orchestrator to decompose a task for a team of workers and then improve through textual reflection. Despite strong empirical results, these systems lack a unified account of coordination, memory improvement, and the role of external verification. We model orchestrator-worker interaction as a bilevel coordination game: under bounded coupling, the workers' local-update game is an approximate potential game whose equilibrium slack is controlled by decomposition quality. We then analyse reflection as stochastic movement over semantic memory states. For free-form reflection, we derive a finite-time upper bound, prove worst-case tightness, and give a positive lower bound under a falsifiable persistent-harm condition. We further prove an information-theoretic impossibility result: no gate that observes only the generated transcript can improve uniformly over text-indistinguishable environments, whereas an environment-grounded gate can. Motivated by this separation, we introduce Stochastic Reflective Memory Ascent (SRMA), which accepts a candidate memory only after a grounded evaluation risk strictly decreases. Under calibration and non-degenerate corrective mass, SRMA converges exactly, geometrically or polynomially; matching constructions show that both rate regimes are order-tight. We also provide confidence gating for stochastic evaluation and re-anchoring guarantees for piecewise-stationary environments. Experiments instantiate these objects with environment-grounded metrics and test the predicted coordination and drift laws. On 500 SWE-bench instances, the complete Kimi-based system resolves 72.2% versus a 70.8% public mini-SWE-agent reference. Code: https://github.com/YihangChen9/Bilevel-Coordinated-Reflection