One-sentence Summary

Researchers from UCL Centre for Artificial Intelligence, University of Liverpool, and Huawei propose a game-theoretic framework that models orchestrator–worker interaction as a bilevel coordination game, proving convergence bounds for reflection and introducing Stochastic Reflective Memory Ascent (SRMA), which accepts candidate memories only under grounded evaluation risk decrease, achieving $72.2\%$72.2% on $500$500 SWE-bench instances versus a $70.8\%$70.8% reference.

Key Contributions

• Introduces Stochastic Reflective Memory Ascent (SRMA), which commits a candidate memory only when a fixed grounded evaluation protocol certifies a strict decrease in verifier risk, and proves exact geometric or polynomial convergence under calibration and non-degenerate corrective mass, with confidence gating and re-anchoring extensions.
• Models orchestrator–worker interaction as a bilevel coordination game, showing that follower equilibrium slack is controlled by decomposition coupling, and derives a two-sided drift analysis of free-form reflection with a worst-case tight upper bound and a positive lower bound under a persistent-harm condition.
• Validates the theory on controlled environments (hidden-cap resource contest and Overcooked with exact BFS value tables) and on SWE-bench, where the complete Kimi-based system resolves 361/500 instances (72.2%) versus 70.8% for the public mini-SWE-agent v2 reference.

Introduction

Multi-agent LLM systems are now a standard approach for tasks that are too large or structured for a single model: an orchestrator breaks down the problem, workers solve the pieces, and the team improves by reflecting on its own outputs through a shared textual memory. Because model weights are frozen at test time, editing this memory is the primary way to adapt, and such loops often work better when grounded by a test harness, simulator, or formal checker. However, existing frameworks describe these systems procedurally, specifying who talks to whom and which buffers get updated, but they fail to capture the strategic objective that agents stabilize to or what reflection actually improves. This leaves open three key questions: how does the orchestrator’s decomposition quality control worker coordination, when does unconditional reflection plateau instead of converge, and why can an external verifier succeed where a stronger text-only critic still fails?

The authors address these questions with a unified framework. They model the orchestrator-worker pipeline as a bilevel coordination game, where the 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, they derive a one-sided drift condition that yields a finite-time upper bound, tight in the worst case, but show that a universal positive floor requires an additional, explicitly testable persistent-harm condition; unconditional commitment alone is not enough. They then isolate the informational role of verification by constructing two environments with identical text-generation laws but opposite meanings for the same reflections. Any gate that observes only the transcript, even an ideal text-only judge, behaves identically in both and cannot improve both, whereas a grounded verifier distinguishes the pair and recovers geometric convergence.

Motivated by this separation, the authors 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, with a confidence gate for stochastic probes and re-anchoring for piecewise stationarity. They validate the theory on a hidden-cap resource contest, Overcooked with an exact BFS value table, and SWE-bench, where the complete Kimi-based system resolves 361/500 instances (72.2%) versus 70.8% for the public mini-SWE-agent v2 reference. The key contributions are a bilevel coordination game linking decomposition coupling to follower equilibrium slack, a two-sided drift analysis of free-form reflection, an impossibility theorem for self-contained text-only gates, the SRMA algorithm with exact convergence guarantees, and mechanism-level validation across controlled and end-to-end benchmarks.

Method

The authors formalize multi-agent LLM coordination as a bilevel game. The orchestrator, acting as the leader, generates a strategy profile $\tau = (\tau_1, \dots, \tau_N)$τ=(τ1​,…,τN​) from the query $q$q, assigning each worker a subtask. Each worker then produces a local sub-solution $x_i$xi​, and the global output is the concatenation of these local outputs. Unlike idealized independent decompositions, real systems exhibit cross-worker interactions through shared variables, interfaces, and joint constraints. To capture this, the authors adopt a weakly coupled decomposition where the global utility is expressed as the sum of local worker objectives plus pairwise coupling terms $\psi_{ij}(x_i, x_j)$ψij​(xi​,xj​) over an interaction graph $\mathcal{E}$E:

$$U(x) = \sum_{i=1}^{N} u_i(x_i \mid \tau_i) + \sum_{(i,j) \in \mathcal{E}} \psi_{ij}(x_i, x_j \mid \tau_i, \tau_j).$$U(x)=i=1∑N​ui​(xi​∣τi​)+(i,j)∈E∑​ψij​(xi​,xj​∣τi​,τj​).

The magnitude of the coupling terms, bounded by $\kappa$κ, and the maximum degree $d_{\text{max}}$dmax​ of the interaction graph jointly quantify the quality of the decomposition. When $\kappa = 0$κ=0, the system reduces to the independent case. The authors prove that under this weakly coupled structure, the workers’ subgame is an $\eta_c$ηc​-approximate potential game with slack $\eta_c \leq 2 d_{\text{max}} \kappa$ηc​≤2dmax​κ. This result ensures that iterated better-response updates by workers converge in finitely many steps to an $\eta_c$ηc​-approximate pure-strategy Nash equilibrium. The leader’s objective is to anticipate this equilibrium and choose a decomposition that maximizes a lower bound on the expected global utility, trading off achievable local utility against coupling cost.

Since the LLM weights are frozen, adaptation occurs through editing external, non-parametric memories: an execution memory shared by workers and a strategy memory used by the orchestrator. The authors analyze the dynamics of these memories under two regimes. In the free-form reflection regime, every generated reflection is appended unconditionally, mixing corrective and hallucinated information. Under a one-sided drift condition, where the expected sub-optimality decreases by a factor $\gamma_t$γt​ but incurs a residual error load $\nu_t$νt​, the authors derive a finite-time upper bound on the expected sub-optimality:

$$e_T \leq (1 - \underline{\gamma})^T e_0 + \frac{\overline{\nu}}{\underline{\gamma}} \left(1 - (1 - \underline{\gamma})^T\right).$$eT​≤(1−γ​)Te0​+γ​ν​(1−(1−γ​)T).

This bound converges to $\overline{\nu}/\underline{\gamma}$ν/γ​, which is shown to be tight in the worst case. However, this is only an upper guarantee. Under a persistent harmful commitment assumption, where a lower drift condition holds, the authors establish a universal lower bound:

$$\liminf_{T \to \infty} e_T \geq \frac{\underline{\nu}}{\overline{\gamma}} > 0.$$T→∞liminf​eT​≥γ​ν​​>0.

This demonstrates that without screening, the mean error cannot vanish, establishing a hallucination floor. The two-sided error tube, formed by the upper and lower bounds, characterizes the asymptotic behavior of the memory dynamics. The leader’s outer loop operates on a slower timescale, with an analogous affine recursion yielding a finite-episode bound, but no asymptotic regret claim is made.

The authors then establish a fundamental impossibility result for self-contained gates. A self-contained gate is any acceptance rule measurable with respect to the generated text process and its internal randomness only, which includes text-only LLM-as-judge systems. The authors construct two environments that are indistinguishable at the text level, where the same reflection is corrective in one environment and harmful in the other. Under this construction, for any self-contained gate and any horizon, the maximum expected sub-optimality across the two environments is at least the initial error:

$$\max\{e_T^{\varepsilon^+}, e_T^{\varepsilon^-}\} \geq e_0.$$max{eTε+​,eTε−​}≥e0​.

This result is strict if an ambiguous proposal is accepted with positive probability. In contrast, a grounded gate that observes the environment-dependent signal achieves exponential convergence to zero error. This theorem establishes that textual self-evaluation cannot substitute for grounding when truth depends on external state, such as hidden caps, API responses, simulator state, or an evolving repository.

Building on this impossibility result, the authors propose SRMA, a verifier-gated reflection mechanism. The key design principle is to separate the stochastic proposal mechanism from the grounded evaluation protocol. A verifier is a deterministic map from an output and task to a diagnostic score, and the verifier risk of a memory is the score of the evaluation output under a fixed deterministic protocol. The SRMA update samples a reflection conditioned on the current output, diagnostic, task, and memory, forms a candidate memory, and accepts it only if the verifier risk strictly decreases:

$$R_i(\widetilde{m}_e^{t+1}) < R_i(m_e^t).$$Ri​(met+1​)<Ri​(met​).

This gating on a deterministic risk, rather than on two uncontrolled one-shot samples, is crucial for exact guarantees. Under a verifier calibration assumption, where zero verifier risk certifies zero task sub-optimality, and assumptions on non-degenerate corrective mass and proportional accepted decrement, the authors prove that the verifier risk converges to zero almost surely. The convergence rate is geometric when the acceptance probability is proportional to the risk ($\beta = 0$β=0) and polynomial when it scales as a power of the risk ($\beta \in (0,1]$β∈(0,1]):

$$\beta = 0: \quad r_T \leq (1-c)^T r_0, \quad \text{(geometric)},$$β=0:rT​≤(1−c)Tr0​,(geometric), $$\beta \in (0,1]: \quad r_T \leq \left(r_0^{-\beta} + c\beta T\right)^{-1/\beta}, \quad \text{(polynomial)}.$$β∈(0,1]:rT​≤(r0−β​+cβT)−1/β,(polynomial).

These rates are shown to be tight up to constant factors. For practical settings where deterministic risk evaluation is unavailable, the authors provide a confidence-gated stochastic evaluation procedure. By estimating the current and candidate risks with independent probes and accepting only when the confidence intervals do not overlap, they guarantee with high probability that every accepted update strictly decreases the true expected risk. Finally, the authors address piecewise-stationary environments by re-anchoring the analysis at the final change point, allowing the convergence guarantees to apply on the final stationary segment.

Experiment

The evaluation spans Resource Contest, Overcooked, and SWE-bench, using grounded environment signals or repository test harnesses as verifiers. Across these settings, grounded SRMA consistently outperforms text-only or ungated baselines, improving oracle reward attainment, coordination scores, and downstream task resolution while reducing regret and harmful proposal acceptance. The adaptive gate provides statistical efficiency comparable to fixed verification at lower cost, and re-anchoring enables rapid detection of distribution shifts. End-to-end software repair results show that grounded, gated multi-agent coordination yields substantial gains over ungated reflection, with the benefit attributed to the grounding mechanism rather than model choice.

Under matched interaction and model-call budgets, the grounded self-gated memory approach (Grounded SRMA) consistently outperforms all baselines across Overcooked layouts, with the largest gains in the most coordination-intensive layout. The results show that grounding coordination signals in environment feedback, rather than relying on free-form or ungated memory, yields higher delivery scores. Grounded SRMA achieves the highest scores on all three Overcooked layouts, with the biggest margin over the no-memory baseline in the centre_pots layout. Self-gated memory without grounding outperforms free-form memory, indicating that selective memory use alone improves coordination. The gap between grounded and free-form approaches widens as layout coordination demands increase, from cramped_room to centre_pots.

Across all RC settings, SRMA consistently achieves the highest cumulative reward, reaching 98.5% to 99.5% of the oracle reward. The execution-memory ablation shows that adding memory improves average reward by 2.6 points and reduces mean regret by 60.8%, demonstrating that grounded cap evidence becomes a functional coordination channel when memory is present. SRMA outperforms both epsilon-greedy and no-memory baselines in every setting, with the largest gains in the many-worker scenario. Execution memory reduces mean regret from 4.33 to 1.70, a 60.8% improvement, while adding 2.6 reward points on average. The hard setting shows the smallest gap to oracle, with SRMA achieving 159.2 out of 160, indicating precise allocation under tightly packed caps.

Grounded SRMA with self-gating substantially reduces harmful proposal acceptance and overall risk compared to free-form or no-reflection baselines, while maintaining high helpful acceptance. The method also improves coordination efficiency, such as faster re-anchoring to changing optima and reduced regret, across different environments. Grounded SRMA cuts harmful acceptance to 6.2% and risk to 0.14, versus 100% harmful and 0.42 risk for free-form reflection. Self-gating alone reduces harmful acceptance to 34.5% but also lowers helpful acceptance to 72.8%, whereas grounded SRMA keeps helpful acceptance at 85.4%. Re-anchored grounded gate detects a shift in the optimal cap in 1.2 rounds and switches in 2.5 rounds, cutting post-shift regret by 67% compared to a stale-anchor variant. In SWE-bench, bilevel SRMA resolves 72.2% of instances versus 58.4% for free-form multi-agent reflection on the Kimi K2.5 backbone, with similar gains on DeepSeek.

On SWE-bench, the bilevel SRMA system with grounded gating outperforms both a free-form multi-agent baseline and a single-agent reference across two backbones, with the largest gains on Kimi K2.5. The controlled DeepSeek runs confirm the same trend, showing the improvement stems from grounded, gated coordination rather than model choice or compute. Bilevel SRMA with grounded gating resolves 72.2% of instances on Kimi K2.5, versus 58.4% for free-form multi-agent reflection under matched budget. The grounded gate also exceeds the external public mini-SWE-agent v2 reference (70.8%) on the same backbone. Controlled DeepSeek runs show the same pattern: Bilevel SRMA reaches 71.4% versus 68.2% for the single-agent baseline.

Across Overcooked, resource collection, and SWE-bench evaluations, the grounded, self-gated memory approach consistently outperforms free-form or ungated baselines under matched budgets, with gains widening as task coordination demands increase. Grounding coordination signals in environment feedback and using selective memory both improve outcomes, with the largest margins in coordination-intensive layouts and many-worker scenarios. The method also reduces harmful proposal acceptance and risk while maintaining high helpful acceptance, and achieves faster re-anchoring to shifting optima with lower regret. On SWE-bench, bilevel grounded gating resolves more instances than free-form multi-agent reflection across two backbones, with controlled runs confirming the improvement stems from the coordination mechanism rather than model choice.