Bilevel Coordinated Reflection: A Game-Theoretic Approach to Multi-Agent LLM Systems

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.

Introduction. Multi-agent LLM systems have become a common recipe for tasks too large or structured for a single agent: an orchestrator decomposes the task, worker models solve the pieces, and the team improves by reflecting—writing critiques, hypotheses, and lessons into a shared textual memory that conditions subsequent generations (Wu et al. 2024; Hong et al. 2024; Shinn et al. 2023; Benkovich and Valkov 2026; Qian et al. 2025). Because model weights are frozen at test time, memory editing is the principal adaptation channel (Zhou et al. 2025; Xu et al. 2025; Zhang et al. 2025b), and such loops often work better when grounded by a test harness, simulator, execution engine, or formal checker. The dominant account of these systems is nevertheless procedural. Existing frameworks (Zhang et al. 2025a; Hu, Lu, and Clune 2025; Dang et al. 2025; Wang et al. 2025) specify who communicates with whom and which buffer is updated, but not the strategic object that the agents stabilise to or the quantity that reflection improves. This leaves three unresolved questions.

Discussion / Conclusion. We gave multi-agent LLM reflection a conditional, information-aware theory: bilevel coupling controls follower equilibrium slack, persistent harmful commitment creates free-form error floors, and no transcript-only gate can improve uniformly when the truth of a reflection depends on external state. SRMA supplies the missing grounding and converges exactly at order-tight geometric or polynomial rates, with confidence-gating and re-anchoring extensions; experiments on Resource Contest, Overcooked, and SWEbench support the predicted coordination, grounding, and resolution mechanisms. Limitations. The guarantees are conditional: bounded coupling, finite action sets, verifier calibration, and nondegenerate corrective mass need not hold in open-ended agent tasks; drift parameters are validated only on observed trajectories; incomplete test suites guarantee monotonicity only for verifier risk, not true task utility; and re-anchoring gives per-segment convergence without a general switchingregret bound.