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

Bilevel Coordinated Reflection: A Game-Theoretic Approach to Multi-Agent LLM Systems Yihang Chen1∗ , Yuxiang Chen1∗ , Yuxuan Huang2 , Meng Fang2 , Weilin Luo3 , Jun Wang1†

arXiv:2609.02750v1 [cs.AI] 2 Sep 2026

1

UCL Centre for Artificial Intelligence

2

Abstract

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. First, how does the orchestrator’s decomposition quality control worker coordination? Second, when does unconditional reflection plateau rather than converge? Third, why can an external verifier succeed where a stronger text-only critic may still fail? We address these questions in a single framework. The orchestrator–worker pipeline is modelled as a bilevel coordination game whose follower subgame is an approximate potential game, and textual memory editing as a stochastic process over a discrete semantic state space. For free-form reflection, a one-sided drift condition yields a finite-time upper bound that is tight in the worst case; a universal positive floor requires an additional, explicitly testable persistentharm condition—unconditional commitment alone is not enough. We then isolate the informational role of verification: in two environments with identical text-generation laws but opposite meanings for the same reflections, any possibly randomised, history-dependent gate that observes only the transcript behaves identically and therefore cannot improve both—even an ideal text-only judge—whereas a grounded verifier distinguishes the pair and recovers geometric convergence. Motivated by this separation, we introduce Stochastic Reflective Memory Ascent (SRMA), which commits a candidate memory only when a fixed grounded evaluation protocol certifies a strict decrease in verifier risk. Under calibration and non-degenerate corrective mass, SRMA converges exactly at order-tight geometric or polynomial rates; a confidence gate handles stochastic probes, and re-anchoring restores per-segment convergence under piecewise stationarity. The theory is instantiated on a hidden-cap resource contest, Overcooked with an exact BFS value table, and SWEbench (Jimenez et al. 2024). The controlled environments expose the strategic, memory, and drift quantities directly without an LLM-as-judge; on SWE-bench the complete Kimibased system resolves 361/500 instances (72.2%) versus

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 available at https://github.com/YihangChen9/ Bilevel-Coordinated-Reflection.

1

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 ∗ †

Equal contribution. Corresponding author.

University of Liverpool

3

Huawei

Upper-Level Layer (Bilevel Leader) Orchestrator Agent Update in Timescale 𝛽

Decompose Task 𝜏 ∼ 𝑝LLM ⋅ 𝑞, 𝑚! Aggregated Result

Read

Write

Strategy Memory

Strategy and historical heuristics Memory Update Operator:

𝑚!.%" = ℳℴ 𝑚!. , 𝑐!.%"

Lower-Level Layer (Bilevel Follower) Workers Layer

Read

Execute Task 𝑥 = 𝑥! 𝑥! ∼ 𝑝LLM ⋅ 𝜏! , 𝑚"

% !#$

Write

Execution Memory Worker Workboard

Coordinate Memory with Optimal Reflection

Give ηc -Better Response Worker 1 𝑥"# ∼ 𝑝LLM ⋅ 𝜏" , 𝑚$#

Decomposed Task 𝜏

Update in Timescale 𝛼

Lower-Level Layer (Bilevel Follower) - Discrete Approximate Potential Game

Worker i 𝑥'"#$ ∼ 𝑝LLM ⋅ 𝜏' , 𝑚!"#$

Writ e at

R

Execution Memory time t

+1 et im tt da a e

Worker Workboard

Memory Update Operator:

𝑚$#%" = ℳℯ 𝑚$# , 𝑐"#%" , … , 𝑐'#%" 𝑐(∗ 𝑥( , 𝜏( , 𝑚$ ∈ arg min 𝑅( ℳℯ (𝑚$ , 𝑐( ) *! ∈𝒞𝒾

Asynchronous Read & Write

Memory Update Operator:

𝑚!"#$ = ℳℯ 𝑚!" , 𝑐$"#$ , … , 𝑐&"#$

Figure 1: Bilevel coordinated reflection. The orchestrator (leader) selects a decomposition τ and updates strategy memory mo on the slower timescale; workers (followers) update execution memory me via ηc -better responses on the faster timescale. Under bounded coupling, the followers’ subgame is an approximate potential game with slack ηc ≤ 2dmax κ, while verifier-gated SRMA separately governs which memory proposals are committed. 70.8% for the public mini-SWE-agent v2 reference. In summary, we contribute: (1) a bilevel coordination game linking decomposition coupling to follower equilibrium slack (Sec. 3.1); (2) a two-sided drift analysis of freeform reflection, tight in the worst case, with a universal lower bound under persistent harmful commitment (Sec. 3.2); (3) an impossibility theorem for self-contained text-only gates, with a grounded comparator that converges geometrically (Sec. 3.3); (4) SRMA, with exact convergence, order-tight rates, and a finite-probe confidence extension (Sec. 3.4); and (5) mechanism-level validation on Resource Contest and Overcooked plus end-to-end results on SWE-bench (Sec. 4).

2

Related Work

Multi-agent LLM frameworks. Orchestrator–worker architectures such as AutoGen (Wu et al. 2024), MetaGPT (Hong et al. 2024) and Agyn (Benkovich and Valkov 2026) show strong empirical performance but offer no convergence analysis; failure modes such as hallucination cascades are documented empirically (Liu et al. 2026; Cemri et al. 2025). We provide the missing game-theoretic and stochasticapproximation foundations. Self-reflection, self-evaluation, and grounding. Reflexion (Shinn et al. 2023) and Self-Refine (Madaan et al. 2023) improve outputs by appending self-generated critiques but may plateau, and correlated self-evaluation bias (Zheng et al. 2023; Panickssery, Bowman, and Feng 2024; Wu et al. 2026) weakens model-based judges in practice. Our drift analysis separates a worst-case floor from the persistentharm condition needed for a universal lower bound, and our indistinguishable-environment theorem shows that without an environment-dependent signal even an ideal text-only gate cannot be uniformly correct. Potential games and drift analysis. Our followers’ subgame builds on exact and approximate potential games (Monderer and Shapley 1996; Candogan et al. 2011; Christodoulou and Gairing 2014) and weakly coupled team problems (Srikant and Başar 1992). The convergence analysis uses Foster–Lyapunov drift (Hajek 1982; Meyn and

Tweedie 2009), classical stochastic approximation (Robbins and Monro 1951; Borkar 2008; Bertsekas and Tsitsiklis 2000) and, for the gated regime, multiplicative and variable drift theorems from randomised search heuristics (Doerr, Johannsen, and Winzen 2012; Johannsen 2010; Lehre and Witt 2021); the recursion et+1 ≤ et − c e1+β is the dist crete stochastic analogue of Polyak–Łojasiewicz-type conditions (Karimi, Nutini, and Schmidt 2016; Chung 1954). Two-timescale bilevel structure follows Borkar (1997); Hong et al. (2023).

3

Methodology

Longer derivations are deferred to the supplementary material.

3.1

Problem Formulation: Bilevel Coordination Game

We formalise the resolution of a complex user query q ∈ Q. The objective is a joint structured output x ∈ X maximising a global utility U (x) (logical correctness, constraint satisfaction). In a naive single-agent paradigm the entire output is generated directly from the query via the frozen LLM kernel, x ∼ pLLM (· | q), which for large tasks induces context dilution and reasoning degradation (Liu et al. 2024; Levy, Jacoby, and Goldberg 2024; Du et al. 2025). Contemporary systems instead let an orchestrator partition the task among workers (Wu et al. 2024; Hong et al. 2024; Liu et al. 2025). We model this as a bilevel coordination game. The orchestrator (Leader) generates a strategy profile τ = (τ1 , . . . , τN ) ∈ T , τ ∼ pLLM (· | q),

(1)

assigning subtask τi to worker i (Follower), who generates a local sub-solution xi ∼ pLLM (· | τi ); the global output is x = (x1 , . . . , xN ). Unlike the idealised independent decomposition of classical potential-game analyses (Monderer and Shapley 1996), real multi-agent LLM systems exhibit non-trivial crossworker interactions: shared variables, common interfaces,

joint constraints (Liu et al. 2026). We adopt a weakly coupled decomposition in the spirit of Srikant and Başar (1992); Candogan et al. (2011). Assumption 1 (Weakly Coupled Decomposability). Each worker action set Xi is finite. The worker payoff is the local objective gi (x; τ ) := ui (xi | τi ), while the system-level objective is U . The global utility admits U (x) =

N X

Corollary 1 P (Leader’s Decomposition Trade-off). Let Jloc (τ ) := i maxxi E[ui (xi | τi )] and C(τ ) := dmax (τ ) κ(τ ). For any ηc -approximate equilibrium x∗ (τ ), E[U (x∗ (τ ))] ≥ Jloc (τ ) − 52 N C(τ ).

ui (xi | τi )

i=1

+

Leader’s objective and decomposition quality. The orchestrator anticipates the followers’ equilibrium and solves τ ∗ (q) ∈ arg maxτ E[U (x∗ (τ ))]. Because ηc = 2dmax (τ )κ(τ ) depends on τ , the leader’s objective contains an explicit decomposition-quality term:

X

ψij (xi , xj | τi , τj ),

(2)

(i,j)∈E

where E is an undirected interaction graph induced by τ , with each edge counted once, and κ := sup(i,j)∈E supxi ,xj |ψij (xi , xj | τi , τj )| < ∞. Let Ni be worker i’s coupled neighbours and dmax := maxi |Ni |. When κ = 0 the system reduces to the independent case; κ and dmax jointly quantify decomposition quality. Since LLM generation is stochastic, the system objective is the expected global utility E[U (x)]. Lemma 1 (Approximate Potential Game). Under Assumption 1 and fixed τ , the workers’ subgame is an ηc -approximate potential game with potential E[U (x)] and slack ηc ≤ 2 dmax κ.

(3)

Proof. If worker i unilaterally deviates from xti to xt+1 , i E[U (xt+1 , xt−i )] − E[U (xti , xt−i )] i = E[ui (xt+1 | τi )] − E[ui (xti | τi )] + ∆ψ i i ,

(4)

where the coupling residual ∆ψ i sums at most dmax terms each bounded by 2κ (since |ψij | ≤ κ), so |∆ψ i | ≤ 2dmax κ =: ηc . Every unilateral deviation thus changes the potential within ηc of the local utility change (Candogan et al. 2011; Christodoulou and Gairing 2014). A rational worker performs ηc -better-response updates: E[ui (xt+1 | τi )] − E[ui (xti | τi )] > ηc . If no worker has i such a deviation, the current profile is by definition already an ηc -approximate Nash equilibrium, so the dynamics below are well defined in all cases. Theorem 1 (Convergence of the Followers’ Subgame). Under Lemma 1, iterated ηc -better-response updates converge in finitely many steps to a profile x∗ (τ ) satisfying, for every worker i, E[gi (x∗i , x∗−i ; τ )] ≥ max E[gi (x′i , x∗−i ; τ )] − ηc . ′ xi ∈Xi

(5)

Thus x∗ (τ ) is an ηc -approximate pure-strategy Nash equilibrium of the explicitly defined local-payoff game. Proof sketch. Each update raises the potential E[U (xt )] by a strictly positive amount (Lemma 1); X finite and U bounded imply finite termination. Full proof in the supplementary material.

(6)

Hence the leader maximises a lower bound that trades achievable local utility against coupling: a good decomposition simultaneously raises Jloc and shrinks C(τ ). (Proof in the supplementary material.)

3.2

Dual-Memory Drift Dynamics and Hallucination Floors

LLM weights are frozen, so adaptation proceeds by editing external, non-parametric memories: an execution memory me ∈ Me shared by workers and a strategy memory mo ∈ Mo used by the orchestrator. For a fixed decomposition τ , let Ji (me | τi ) = Exi ∼pLLM (·|τi ,me ) [ui (xi | τi )] and rescale utility so that the sub-optimality Vt := Vi (mte ) = Ji∗ − Ji (mte | τi ) lies in [0, 1]. Let Ft denote the history up to the t-th memory update. The key distinction is whether a proposed reflection is committed unconditionally or evaluated before it enters memory. Unconditional commitment alone does not imply a positive asymptotic error: a universal lower bound requires an explicit condition that harmful commitments keep injecting non-vanishing expected error. We therefore separate an upper guarantee, its worst-case tightness, and a genuine lower bound under persistent harmful drift. Regime A: free-form reflection. When every generated reflection is appended, corrective information and hallucinated information (Huang et al. 2025; Ji et al. 2024) are mixed in the same update. We summarise their net conditional effect by the following one-sided drift condition. Assumption 2 (One-Sided Free-Form Drift). There exist γt ∈ (0, 1] and νt ≥ 0 such that E[Vt+1 | Ft ] ≤ (1 − γt )Vt + νt .

(7)

Here γt Vt is the available corrective drift and νt is the mean residual error load from committed, ungrounded content; νt is a first-moment quantity, not a variance. Theorem 2 (Finite-Time Upper Bound). If γt ≥ γ > 0 and νt ≤ ν, then, for et := E[Vt ], eT ≤ (1 − γ)T e0 +

ν 1 − (1 − γ)T . γ

(8)

Consequently, lim supT →∞ eT ≤ min{1, ν/γ}. (Proof in the supplementary material.) Theorem 2 is an upper guarantee only; the next result is the strongest conclusion available from Assumption 2 alone.

Proposition 1 (Worst-Case Tightness). For every γ ∈ (0, 1] and ν ∈ (0, γ], there exists a free-form process satisfying Assumption 2 with γt ≡ γ and νt ≡ ν such that ν lim E[VT ] = . (9) T →∞ γ Hence the upper bound ν/γ cannot be uniformly improved over the one-sided drift class. Proof sketch. The deterministic recursion Vt+1 = (1 − γ)Vt + ν with 0 < ν ≤ γ maps [0, 1] into itself, attains (7) with equality, and converges to its unique fixed point ν/γ. A lower bound that applies to every process requires a lower drift condition, directly testable by regressing the nextstep error on the current error in free-form trajectories. Assumption 3 (Persistent Harmful Commitment). There exist γ ∈ (0, 1] and ν ∈ (0, γ] such that, on every reachable state, E[Vt+1 | Ft ] ≥ (1 − γ)Vt + ν. (10) The parameter γ upper-bounds how much of the current error can be removed in one expected update, whereas ν > 0 is a persistent net error load that remains because harmful reflections are committed without screening. Theorem 3 (Universal Lower Bound). Under Assumption 3,
ν eT ≥ (1 − γ)T e0 + 1 − (1 − γ)T , (11) γ and therefore ν lim inf eT ≥ > 0. (12) T →∞ γ (Proof in the supplementary material.) Corollary 2 (Two-Sided Error Tube). If Assumptions 2 and 3 both hold, then ν ν ≤ lim inf eT ≤ lim sup eT ≤ . (13) T →∞ γ γ T →∞ When the two conditional drift bounds match, γ = γ = γ and ν = ν = ν, the mean error converges exactly to ν/γ. An operational corollary in the supplementary material re-expresses the tube via estimable per-step correction and harm rates.

Text processes and gates. Let a memory be a finite reflection sequence m = (c1 , . . . , ct ) ∈ C ∗ with append operation m ⊕ c = (c1 , . . . , ct , c). Fix an initial memory m0 and a proposal kernel P (· | m) over C. An environment ε assigns a sub-optimality V ε (m) ∈ [0, 1] to every reachable memory. Across the class considered below, the environment changes this semantic value but not the proposal kernel or any other text-level law. Definition 1 (Self-Contained Gate). A self-contained gate is any possibly randomised, history-dependent acceptance rule measurable with respect to the generated text process and its internal randomness only. A grounded gate may additionally observe an environment-dependent signal, such as realised reward, simulator state, test execution, or a formal-checker result. This class contains text-only LLM-as-judge systems. Correlated-evaluation bias can make such judges weaker in practice (Panickssery, Bowman, and Feng 2024); the result below applies even to an ideal gate with unlimited textprocessing capacity. Ambiguous-pair construction. Let C0 , C1 ⊂ C be disjoint and satisfy P (C0 | m) = P (C1 | m) = µ ∈ (0, 12 ] for every reachable m; all remaining proposals are inert. Fix κ ∈ (0, 1) and define f0 (v) = (1 − κ)v and f1 (v) = κ + (1 − κ)v. In environment ε+ , an accepted proposal from Ca applies fa to the current error; in environment ε− , the roles of C0 and C1 are swapped. Thus the same text is corrective in one environment and harmful in the other. Let eεT = E[V ε (mT )] and assume both environments start at the same e0 ≤ 12 . Theorem 4 (Self-Gating Impossibility). For every selfcontained gate and every horizon T , +

−

max{eεT , eεT } ≥ e0 .

(14)

Moreover, if e0 < 12 and the gate accepts at least one proposal from C0 ∪ C1 with positive probability by time T , then the inequality is strict. In contrast, the free-form rule accepts everything and satisfies eεT → 12 in both environments, whereas the grounded gate that observes V ε accepts only the corrective class and satisfies eεT = e0 (1 − κµ)T → 0 in both environments.

Leader’s outer loop. On the slower timescale, define Vo (mko ) = Φ∗ − Φ(mko ) for Φ(mko ) = E[U (x) | k m∞ e (τ (mo ))]. Under the analogous upper drift condition with γok ≥ γo,min > 0 and νo,k ≤ νo,max , the same affine recursion yields the finite-episode bound E[Vo (mK o )] ≤ (1 − γo,min )K Vo (m0o ) + νo,max /γo,min . We use only this finite-episode statement and make no asymptotic leaderregret claim.

Proof sketch. Couple both environments with shared proposal and gate randomness; the accepted class-label sequence is then identical under ε+ and ε− , and the reflection iden+ − tity f1−a (v) = 1 − fa (1 − v) yields eεT + eεT ≥ 2e0 , strictly when e0 < 21 and an ambiguous proposal is accepted with positive probability. The free-form and grounded rates follow from the induced affine recursions. Full proof in the supplementary material.

3.3

Remark 1 (Scope of the impossibility result). The theorem is minimax over text-indistinguishable environments; textual self-evaluation remains useful when the transcript itself certifies correctness (a fully checkable proof). When truth depends on external state—hidden caps, API responses, simulator state, an evolving repository—judge capacity cannot substitute for grounding.

Why Grounding Is Necessary: Impossibility of Self-Contained Gates

The fundamental informational requirement is grounding: access to a signal whose law depends on the environment rather than only on the generated transcript. We formalise this through a pair of environments that are indistinguishable at the text level.

3.4

SRMA: Verifier-Gated Reflection

Theorem 4 establishes why the gate must have access to an environment-separating signal. Exact convergence additionally requires the gate to compare a fixed error functional of the memory state, rather than two uncontrolled one-shot samples from a stochastic generator. We therefore separate the stochastic proposal mechanism from the grounded evaluation protocol. Definition 2 (Verifier and Evaluation Risk). A verifier is a deterministic map V : X × T → S with deterministic score ρ : S → [0, 1]. Let gi : Ti × Me → Xi be a fixed deterministic evaluation protocol, such as an exact planner or decoding with fixed randomness. The verifier risk of memory me is Ri (me ) := ρ(V(gi (τi , me ), τi )) . (15) The pair (V, gi ) is fixed independently of the reflection proposal distribution. It is grounded when its score depends on an environment signal that is not determined by the generated transcript alone. Grounding supplies information; calibration below connects the score to task utility. Definition 3 (Verifier-Gated SRMA Update). Given mte , compute the evaluation output xti = gi (τi , mte ) and diagnostic sti = V(xti , τi ). Sample a reflection ct+1 ∼ pLLM (· | i t+1 ). Accept iff fe = Me (mte , ct+1 xti , sti , τi , mte ) and form m i Ri (m fe

t+1

) < Ri (mte ).

(16)

Theorem 5 (Exact Verifier Convergence and Rates). Under Assumptions 5–6, let rt := E[Rt ] and c = c1 c2 . Then Rt → 0 almost surely and β=0:

rT ≤ (1 − c)T r0 ,

β ∈ (0, 1] :

rT ≤ r0−β + cβT

(geometric), (22)
−1/β

,

(polynomial). (23)

If Assumption 4 also holds, then E[Vi (mTe )] ≤ LrT and hence the task sub-optimality converges to zero at the same rate up to the factor L. Proof sketch. Taking expectations in (21) and applying Jensen’s inequality to z 7→ z 1+β gives rt+1 ≤ rt − crt1+β ; the rates follow by the standard multiplicative/variable-drift comparison. Rt is non-increasing and non-negative, hence converges almost surely, and rt → 0 forces the limit to be zero. Calibration transfers the bound to the utility gap. Proposition 3 (Rate Tightness for Verifier-Gated Reflection). For every c1 ∈ (0, 1], c2 ∈ (0, 21 ], β ∈ (0, 1], and r0 ∈ (0, 1], there exists a process satisfying Assumptions 5–6 with equality such that, for c = c1 c2 ,
−1/β E[RT ] ≥ r0−β + 4cβT for every T. (24)

t+1

On acceptance set mt+1 =m fe ; otherwise retain mt+1 = e e mte . Gating on two stochastic one-shot outputs would not suffice: sample variation could accept a memory with worse expected performance. Exact guarantees therefore assume deterministic or exact expected-risk evaluation; a finite-sample extension follows below. Assumption 4 (Verifier Calibration). There exists L < ∞ such that, for every reachable memory, Vi (me ) ≤ LRi (me ).

(17)

Thus zero verifier risk certifies zero task sub-optimality. This assumption is appropriate for exact value tables and complete formal checkers; on incomplete test suites, our theorem concerns verifier risk only. Assumption 5 (Non-Degenerate Corrective Mass). There exist c1 ∈ (0, 1] and β ∈ [0, 1] such that, whenever Rt := Ri (mte ) > 0, pt := Pr[accept | Ft ] ≥ c1 Rtβ .

(18)

Assumption 6 (Proportional Accepted Decrement). There exists c2 ∈ (0, 1] such that E[Rt − Rt+1 | Ft , accept] ≥ c2 Rt .

(19)

Proposition 2 (Monotone Multiplicative Drift). Under Definition 3, Rt+1 ≤ Rt almost surely and E[Rt+1 | Ft ] = Rt − pt ∆t , ∆t := E[Rt − Rt+1 | Ft , accept].

(20)

Under Assumptions 5–6, with c = c1 c2 , E[Rt+1 | Ft ] ≤ Rt − cRt1+β .

(21)

For β = 0, the analogous construction gives E[RT ] = (1 − c)T r0 exactly. Hence the geometric rate is exact and the polynomial exponent T −1/β is tight up to a constant factor in the time scale. Proof sketch. Accept with probability c1 Rtβ and set Rt+1 = (1 − c2 )Rt on acceptance, so both assumptions hold with equality. For β > 0, Yt = Rt−β has constant expected increment, and convexity of y 7→ y −1/β gives (24); for β = 0, E[Rt+1 | Ft ] = (1 − c1 c2 )Rt . Full proof in the supplementary material. Proposition 4 (Confidence-Gated Stochastic Evaluation). Suppose deterministic Ri (me ) is unavailable and instead Ri (me ) = E[Z(me )] for an i.i.d. score Z(me ) ∈ [0, 1]. At round t, estimate the current and candidate risks with Kt independent probes and let s log(4/δt ) . (25) at = 2Kt t+1 bt (m bt (mt ) − at . Then, Accept only when R fe )P + at < R e with probability at least 1 − t δt , every accepted update strictly decreases the true expected verifier risk.

Proof sketch. Hoeffding’s inequality bounds each of the two estimation errors by at with joint failure probability at most δt ; a union bound over rounds completes the argument. Exact convergence requires deterministic or exact expected-risk evaluation, or Kt → ∞ with summable δt .

Algorithm 1: Stochastic Reflective Memory Ascent for worker i Require: subtask τi ; verifier (V, ρ); evaluation protocol gi ; memory operator Me ; initial memory m0e ; budget T 1: for t = 0 to T − 1 do 2: xti ← gi (τi , mte ) 3: sti ← V(xti , τi ); Rt ← ρ(sti ) 4: sample ct+1 ∼ pLLM (· | xti , sti , τi , mte ) i t+1 5: m fe ← Me (mte , ct+1 ) i t+1 t+1 6: x ei ← gi (τi , m fe )
e ← ρ V(e 7: R xt+1 , τi ) i e < Rt then 8: if R t+1 9: mt+1 ←m fe e 10: else 11: mt+1 ← mte e 12: end if 13: end for 14: return mT e

Proposition 5 (Piecewise-Stationary Re-Anchoring). Suppose the verifier risk changes finitely many times, with final change at tS , and both current and candidate memories are re-evaluated under the current risk. If Assumptions 5–6 hold on the final stationary segment, then Theorem 5 applies with (t ) horizon T − tS and initial risk rtS = E[Ri S (mteS )]. Remark 2 (Falsifiability and rate prediction). The exponent β is observable: the geometric regime is linear in log R versus t, the polynomial regime in log R versus log t with slope −1/β; estimating β from acceptance frequencies and from trajectory decay gives the closed-loop calibration of Sec. 4. The free-form drift parameters are likewise estimable from conditional drift regressions. Practical realisation. Algorithm 1 probes the candidate under the same fixed protocol and commits only a strict improvement; recomputing the current risk enables the reanchoring of Proposition 5, and under stochastic evaluation line 8 is replaced by the test of Proposition 4.

4

Experiments

We evaluate the theory on Resource Contest (RC; Table 2), Overcooked (Table 1), and SWE-bench (Table 4). RC and Overcooked use frozen MiniMax-M2.7 agents; unless noted otherwise, results are mean±standard deviation over five seeds. SWE-bench uses the backbones listed in Table 4. All metrics come from environment ground truth or the repository test harness rather than an LLM judge. Full prompts, configurations, and per-seed trajectories are in the supplementary material. Resource Contest. RC is a hidden-cap allocation game: workers probe unknown caps Mi ∈ {0, . . . , 10} and the orchestrator allocates a unit budget across workers. The optimal round reward is G⋆t =Pmaxi Mi , and we report cumulative reward and regret t (G⋆t − Gt ). Clipping feedback is generated by the environment and therefore provides

a grounded signal. The four settings vary difficulty: easy (N =3, caps (3, 5, 8), T =15); hard (N =3, caps (6, 7, 8), T =20; tightly packed caps test allocation precision); many (N =6, caps (2, 4, 5, 6, 7, 9), T =20; larger search space); and drift (N =3, caps (3, 5, 8) until t=10, then (9, 5, 4); a moving optimum tests re-adaptation). Since G⋆t = maxi Mi , the oracle Σ-reward is 120, 160, and 180 on easy/hard/many respectively. SRMA reaches 98.5%–99.5% of oracle reward. Execution memory adds 2.6 reward points on average and reduces mean regret from 4.33 to 1.70 (60.8%): grounded cap evidence that is fragmented without memory becomes a functional coordination channel for the orchestrator. Overcooked coordination. We use Overcooked (Carroll et al. 2019) with three two-agent layouts, a horizon of 200, and an exact BFS verifier V (s) = min{joint-action steps from s to the next delivery}. The verifier is deterministic and supplies the risk used for both SRMA and the drift study. The layouts stress complementary coordination demands: mutual blocking in a tight kitchen (cramped_room), role specialisation (asymmetric_advantages), and contention over shared pots (centre_pots). Grounded SRMA is best on every layout (Table 1). Relative to the text-only self-gate, it raises score by 14.3%, 27.3%, and 30.0%, and reaches the first delivery in 22±2, 26±3, and 32±4 steps versus 26±5, 35±6, and 45±8 for self-gating. The ordered improvement from no memory to free-form, self-gating, and grounded SRMA separates decomposition, memory, and grounding effects. Grounding and gate quality. A proposal is downstream harmful when it increases an independently evaluated oracle task risk, not necessarily the verifier score used by the gate. Table 3 shows that grounding sharply improves both selectivity and final risk. Grounded SRMA halves final risk relative to selfgating; the residual 6.2% downstream-harmful rate measures verifier–oracle miscalibration rather than a violation of monotonicity in the verifier’s own risk. Gate-level drift predicts held-out trajectories. From 412 gate events across five seeds, we use three complete seeds for calibration and hold out two entire trajectories. A trajectorylevel bootstrap gives βb = 0.52±0.04, b c1 = 1.25, and b b c2 = 0.38, with pacc (R) ≈ min{1, b c1 Rβ }. Without fitbT = ting trajectory-level parameters, the plug-in prediction R
−1/0.52 −0.52 R0 + 0.247 T tracks the held-out risks with Pearson’s r = 0.94 and RMSE = 0.032, implying decay near O(T −1.92 ). Bootstrap lower bounds c1 = 0.92 and c2 = 0.25 yield a conservative envelope above the empirical mean risk at every recorded step—an empirical certificate on the observed range, not a claim about unobserved states. Statistical resolution. A one-shot stochastic verifier falsely accepts 28.4±5.2% of worsening proposals (score 245.2±38.4); fixed K = 5 cuts this to 6.8±1.5% (score 312.0±18.2) at 225 verifier calls, and the adaptive gate matches that reliability (7.1±1.8%, score 308.6±19.5) with

Table 1: Overcooked score over five seeds under matched interaction and model-call budgets. Score equals deliveries×20; higher is better. Layout

Greedy

No memory

Free-form

Self-gated

Grounded SRMA

cramped_room asymmetric_advantages centre_pots

120±40 80±40 40±0

180±40 140±40 100±40

240±60 180±40 160±60

280±40 220±40 200±40

320±20 280±20 260±20

Table 2: RC results over five seeds (Σ-reward; higher is better). The last two columns form the execution-memory ablation. Setting

Oracle

ε-greedy

No memory

SRMA

easy hard many

120 160 180

113.1±3.0 157.4±1.1 170.9±4.0

115.0±5.2 158.0±2.3 174.0±3.7

118.4±2.2 159.2±0.9 177.3±1.9

Table 3: Accepted proposals and final risk over five seeds. Rates are fractions of harmful/helpful proposals accepted. Method No reflection Free-form Self-gate Grounded SRMA

Harmful↓

Helpful↑

Risk↓

N/A 100.0±0.0% 34.5±4.2% 6.2±1.8%

N/A 100.0±0.0% 72.8±5.1% 85.4±3.6%

0.65±0.05 0.42±0.12 0.28±0.08 0.14±0.03

only 82±14 calls (−63.6%), supporting Proposition 4: grounding supplies information, confidence control supplies resolution. Piecewise stationarity. In RC drift, the optimal cap changes at t = 10 while previously written text remains unchanged, testing the re-anchoring mechanism of Proposition 5. The re-anchored grounded gate detects the shift in 1.2±0.4 rounds, switches to the new optimum in 2.5±0.6, and incurs 12.6±2.8 post-shift regret, versus 2.4±0.5, 7.8±1.2, and 38.2±5.5 for the grounded staleanchor variant—a 67.9% cut in switch time and 67.0% in regret—while the text-only gate fails to detect the change within 20 rounds (regret 85.4±4.2). Grounding detects the shift, but re-anchoring is required to replace stale memory quickly. End-to-end software repair. We evaluate the complete bilevel system on all 500 SWE-bench instances, with the repository test harness as the grounded verifier (an instance counts as resolved only if its submitted patch passes the harness). Each worker is a mini-SWE-agent v2 instance; the bilevel system runs N =2 such workers over a shared repository and workboard for up to three coordination rounds per episode and submits the highest-J patch, whereas the miniSWE v2 row is a single mini-SWE-agent v2 worker with no orchestrator or shared memory. The Free-form MA row keeps the same N =2 multi-agent coordination but commits every proposed reflection ungated (no verifier check), isolating the effect of SRMA’s grounded gate. The public leaderboard row is an external reference, not a controlled ablation.

Table 4: SWE-bench results on 500 instances (% resolved; official test harness). †: controlled runs under matched budget; the public row is an external leaderboard reference, not a controlled ablation. System †

mini-SWE v2 Bilevel SRMA† Free-form MA† mini-SWE v2 (public) Bilevel SRMA

Backbone

Rate↑

DeepSeek DeepSeek Kimi K2.5 Kimi K2.5 Kimi K2.5

68.2% 71.4% 58.4% 70.8% 72.2%

On the Kimi K2.5 backbone the grounded gate is decisive: Bilevel SRMA resolves 72.2% against 58.4% for free-form (ungated) multi-agent reflection at matched backbone and budget, and exceeds the external public mini-SWE-agent v2 reference (70.8%). The controlled DeepSeek runs show the same direction (71.4% vs. 68.2%), indicating that the gain comes from grounded, gated coordination rather than from raw model or compute.

5

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. Multi-agent coordination also spends substantial tokens before the final answer, and the 72.2% Kimi result is compared with a public 70.8% leaderboard run rather than a controlled method-only comparison. Future work should jointly optimise memory quality and budget-aware termination.

References Benkovich, N.; and Valkov, V. 2026. Agyn: A Multi-Agent System for Team-Based Autonomous Software Engineering. arXiv preprint arXiv:2602.01465. Bertsekas, D. P.; and Tsitsiklis, J. N. 2000. Gradient Convergence in Gradient Methods with Errors. SIAM Journal on Optimization, 10(3): 627–642. Borkar, V. S. 1997. Stochastic approximation with two time scales. Systems & Control Letters, 29(5): 291–294. Borkar, V. S. 2008. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press. Candogan, O.; Menache, I.; Ozdaglar, A.; and Parrilo, P. A. 2011. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3): 474–503. Carroll, M.; Shah, R.; Ho, M. K.; Griffiths, T. L.; Seshia, S. A.; Abbeel, P.; and Dragan, A. 2019. On the Utility of Learning about Humans for Human-AI Coordination. In Advances in Neural Information Processing Systems (NeurIPS). Cemri, M.; Pan, M. Z.; Yang, S.; Agrawal, L. A.; Chopra, B.; Tiwari, R.; Keutzer, K.; Parameswaran, A.; Klein, D.; Ramchandran, K.; Zaharia, M.; Gonzalez, J. E.; and Stoica, I. 2025. Why Do Multi-Agent LLM Systems Fail? In Advances in Neural Information Processing Systems (NeurIPS). Christodoulou, G.; and Gairing, M. 2014. The price of stability of weighted congestion games. In International Colloquium on Automata, Languages, and Programming (ICALP). Chung, K. L. 1954. On a Stochastic Approximation Method. The Annals of Mathematical Statistics, 25(3): 463–483. Dang, Y.; Qian, C.; Luo, X.; Fan, J.; Xie, Z.; Shi, R.; Chen, W.; Yang, C.; Che, X.; Tian, Y.; Xiong, X.; Han, L.; Liu, Z.; and Sun, M. 2025. Multi-Agent Collaboration via Evolving Orchestration. In Advances in Neural Information Processing Systems (NeurIPS). ArXiv:2505.19591. Doerr, B.; Johannsen, D.; and Winzen, C. 2012. Multiplicative Drift Analysis. Algorithmica, 64(4): 673–697. Du, Y.; Tian, M.; Ronanki, S.; Rongali, S.; Bodapati, S.; Galstyan, A.; Wells, A.; Schwartz, R.; Huerta, E. A.; and Peng, H. 2025. Context Length Alone Hurts LLM Performance Despite Perfect Retrieval. In Findings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). ArXiv:2510.05381. Hajek, B. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14(3): 502–525. Hong, M.; Wai, H.-T.; Wang, Z.; and Yang, Z. 2023. A twotimescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1): 147–180. Hong, S.; Zhuge, M.; Chen, J.; Zheng, X.; Cheng, Y.; Zhang, C.; Wang, J.; Wang, Z.; Yau, S. K. S.; Lin, Z.; et al. 2024. MetaGPT: Meta programming for a multi-agent collaborative framework. In International Conference on Learning Representations (ICLR).

Hu, S.; Lu, C.; and Clune, J. 2025. Automated Design of Agentic Systems. In The Thirteenth International Conference on Learning Representations (ICLR). Huang, L.; Yu, W.; Ma, W.; Zhong, W.; Feng, Z.; Wang, H.; Chen, Q.; Peng, W.; Feng, X.; Qin, B.; and Liu, T. 2025. A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions. ACM Transactions on Information Systems. Ji, Z.; Lee, N.; Frieske, R.; Yu, T.; Su, D.; Xu, Y.; Ishii, E.; Bang, Y. J.; Madotto, A.; and Fung, P. 2024. Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12): 1–38. Jimenez, C. E.; Yang, J.; Wettig, A.; Yao, S.; Pei, K.; Press, O.; and Narasimhan, K. 2024. SWE-bench: Can Language Models Resolve Real-World GitHub Issues? In International Conference on Learning Representations (ICLR). Johannsen, D. 2010. Random Combinatorial Structures and Randomized Search Heuristics. Ph.D. thesis, Universität des Saarlandes. Karimi, H.; Nutini, J.; and Schmidt, M. 2016. Linear Convergence of Gradient and Proximal-Gradient Methods under the Polyak–Łojasiewicz Condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD), 795–811. Lehre, P. K.; and Witt, C. 2021. Tail Bounds on Hitting Times of Randomized Search Heuristics Using Variable Drift Analysis. Combinatorics, Probability and Computing, 30(4): 550–569. Levy, M.; Jacoby, A.; and Goldberg, Y. 2024. Same Task, More Tokens: The Impact of Input Length on the Reasoning Performance of Large Language Models. In Association for Computational Linguistics (ACL). Liu, N. F.; Lin, K.; Hewitt, J.; Paranjape, A.; Bevilacqua, M.; Petroni, F.; and Liang, P. 2024. Lost in the Middle: How Language Models Use Long Contexts. In Transactions of the Association for Computational Linguistics (TACL). Liu, S.; Liu, Y.; Wang, Z.; Wang, Y.; Wu, H.; Xiang, L.; and He, Z. 2025. Select-Then-Decompose: From Empirical Analysis to Adaptive Selection Strategy for Task Decomposition in Large Language Models. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). ArXiv:2510.17922. Liu, X.; Yang, X.; Li, Z.; Li, P.; and He, R. 2026. AgentHallu: Benchmarking Automated Hallucination Attribution of LLM-based Agents. arXiv preprint arXiv:2601.06818. Madaan, A.; Tandon, N.; Gupta, P.; Hallinan, S.; Gao, L.; Wiegreffe, S.; Alon, U.; Dziri, N.; Prabhumoye, S.; Yang, Y.; et al. 2023. Self-Refine: Iterative refinement with selffeedback. In Advances in Neural Information Processing Systems (NeurIPS). Meyn, S.; and Tweedie, R. L. 2009. Markov Chains and Stochastic Stability. Cambridge University Press, 2nd edition. Monderer, D.; and Shapley, L. S. 1996. Potential games. Games and Economic Behavior, 14(1): 124–143.

Panickssery, A.; Bowman, S. R.; and Feng, S. 2024. LLM Evaluators Recognize and Favor Their Own Generations. arXiv preprint arXiv:2404.13076. Qian, C.; Xie, Z.; Wang, Y.; Liu, W.; Zhu, K.; Xia, H.; Dang, Y.; Du, Z.; Chen, W.; Yang, C.; Liu, Z.; and Sun, M. 2025. Scaling Large Language Model-based Multi-Agent Collaboration. In The Thirteenth International Conference on Learning Representations (ICLR). Robbins, H.; and Monro, S. 1951. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3): 400– 407. Shinn, N.; Cassano, F.; Gopinath, A.; Narasimhan, K.; and Yao, S. 2023. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS). Srikant, R.; and Başar, T. 1992. Asymptotic solutions of weakly coupled stochastic teams with nonclassical information. IEEE Transactions on Automatic Control, 37(2): 163– 173. Wang, Y.; Liu, S.; Fang, J.; and Meng, Z. 2025. EvoAgentX: An Automated Framework for Evolving Agentic Workflows. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), System Demonstrations, 643–655. Wu, Q.; Bansal, G.; Zhang, J.; Wu, Y.; Li, B.; Zhu, E.; Jiang, L.; Zhang, X.; Zhang, S.; Liu, J.; Awadallah, A. H.; White, R. W.; Burger, D.; and Wang, C. 2024. AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversations. In First Conference on Language Modeling (COLM). Wu, S.; Li, X.; Feng, Y.; Li, Y.; Wang, Z.; and Wang, R. 2026. Council Mode: A Heterogeneous Multi-Agent Consensus Framework for Reducing LLM Hallucination and Bias. arXiv preprint arXiv:2604.02923. Xu, W.; Liang, Z.; Mei, K.; Gao, H.; Tan, J.; and Zhang, Y. 2025. A-MEM: Agentic Memory for LLM Agents. In Advances in Neural Information Processing Systems (NeurIPS). Zhang, J.; Xiang, J.; Yu, Z.; Teng, F.; Chen, X.-H.; Chen, J.; Zhuge, M.; Cheng, X.; Hong, S.; Wang, J.; Zheng, B.; Liu, B.; Luo, Y.; and Wu, C. 2025a. AFlow: Automating Agentic Workflow Generation. In The Thirteenth International Conference on Learning Representations (ICLR). Zhang, Z.; Bo, X.; Ma, C.; Li, R.; Chen, X.; Dai, Q.; Zhu, J.; Dong, Z.; and Wen, J.-R. 2025b. A Survey on the Memory Mechanism of Large Language Model-based Agents. ACM Transactions on Information Systems, 43(6): 155. Zheng, L.; Chiang, W.-L.; Sheng, Y.; Zhuang, S.; Wu, Z.; Zhuang, Y.; Lin, Z.; Li, Z.; Li, D.; Xing, E.; et al. 2023. Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena. In Advances in Neural Information Processing Systems (NeurIPS). Zhou, H.; Chen, Y.; Guo, S.; Yan, X.; Lee, K. H.; Wang, Z.; Lee, K. Y.; Zhang, G.; Shao, K.; Yang, L.; and Wang, J. 2025. Memento: Fine-tuning LLM Agents without Finetuning LLMs. arXiv preprint arXiv:2508.16153.

Related documents

• A Deterministic Control Plane for LLM Coding Agents#310744
• LongMINT: Evaluating Memory under Multi-Target Interference in Long-Horizon Agent Systems#200536
• An LLM agent-based framework for analytical characterization of Nash equilibria#377566
• Symmetry-Breaking in Multi-Agent Navigation: Winding Number-Aware MPC with a Learned Topological Strategy#629861
• Symmetry-Breaking in Multi-Agent Navigation: Winding Number-Aware MPC with a Learned Topological Strategy#627999