One-sentence Summary

Researchers from UCL Centre for Artificial Intelligence, University of Liverpool, and Huawei model orchestrator–worker interaction as a bilevel coordination game, proving convergence and impossibility results for reflection, and introduce Stochastic Reflective Memory Ascent (SRMA), which accepts memory updates only under grounded 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), a grounded gating mechanism that commits a candidate memory only when a fixed evaluation protocol certifies a strict decrease in verifier risk, with exact convergence at order-tight geometric or polynomial rates under calibration and non-degenerate corrective mass, plus confidence gating and re-anchoring extensions for piecewise-stationary environments.
• Provides a unified game-theoretic and stochastic-approximation foundation for orchestrator–worker LLM systems: models the interaction as a bilevel coordination game where worker equilibrium slack is controlled by decomposition quality, derives two-sided drift bounds for free-form reflection (worst-case tight upper bound and a universal lower bound under persistent harmful commitment), and proves an information-theoretic impossibility result showing that transcript-only gates cannot improve uniformly over text-indistinguishable environments, whereas an environment-grounded gate can.
• Validates the theory across a hidden-cap resource contest, Overcooked with an exact BFS value table, and SWE-bench, where the complete Kimi-based system resolves 72.2% of 500 instances (361/500) versus a 70.8% public mini-SWE-agent reference, and releases code at the provided repository.

Introduction

Multi-agent LLM systems are increasingly used for tasks too large for a single model, where an orchestrator decomposes the problem, workers solve subtasks, and the team improves by writing critiques and lessons into a shared textual memory. Because model weights are frozen, memory editing is the primary adaptation channel, and these loops often rely on external test harnesses or simulators for grounding. However, existing frameworks are procedural, specifying communication patterns but not the strategic objective agents stabilize to or the quantity reflection improves, leaving open questions about decomposition quality, when reflection plateaus, and why external verifiers can outperform stronger text-only critics.

The authors address these gaps with a unified framework that models orchestrator-worker pipelines as a bilevel coordination game with an approximate potential game in the follower subgame, and textual memory editing as a stochastic process over a discrete semantic state space. They derive a finite-time upper bound for free-form reflection under a one-sided drift condition, showing that unconditional commitment alone is insufficient for a universal positive floor without an additional persistent-harm condition. They also prove an impossibility theorem: in environments with identical text-generation laws but opposite meanings for the same reflections, any transcript-only gate (including an ideal text-only judge) cannot improve both, whereas a grounded verifier can distinguish them and achieve geometric convergence.

Building on 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. SRMA converges at order-tight geometric or polynomial rates under calibration and non-degenerate corrective mass, with a confidence gate for stochastic probes and re-anchoring for piecewise stationarity. The theory is validated 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.

Method

3 Methodology

The authors formalize the resolution of a complex user query as a bilevel coordination game. In a naive single-agent paradigm, the entire output is generated directly from the query via a frozen LLM kernel, which for large tasks induces context dilution and reasoning degradation. Contemporary systems instead let an orchestrator partition the task among workers. The authors model this as a leader-follower structure: the orchestrator (Leader) generates a strategy profile that assigns subtasks to workers, and each worker (Follower) generates a local sub-solution conditioned on its assigned subtask. The global output is then assembled from these local sub-solutions.

Unlike idealised independent decompositions, real multi-agent LLM systems exhibit non-trivial cross-worker interactions: shared variables, common interfaces, and joint constraints. The authors adopt a weakly coupled decomposition in which the global utility admits a separable form: a sum of local worker objectives plus pairwise coupling terms over an interaction graph induced by the strategy profile. The coupling strength and the maximum neighbourhood size jointly quantify decomposition quality. When the coupling is zero, the system reduces to the independent case.

Under this formulation, the workers' subgame is shown to be an approximate potential game with a bounded slack that depends linearly on the maximum neighbourhood size and the coupling strength. This implies that iterated better-response updates by workers converge in finitely many steps to an approximate pure-strategy Nash equilibrium. The orchestrator, anticipating this equilibrium, solves a leader objective that contains an explicit decomposition-quality trade-off: a good decomposition simultaneously raises the achievable local utility and shrinks the coupling penalty. The leader therefore maximises a lower bound that trades achievable local utility against coupling.

3.1 Dual-Memory Drift Dynamics and Hallucination Floors

Since LLM weights are frozen, adaptation proceeds by editing external, non-parametric memories: an execution memory shared by workers and a strategy memory used by the orchestrator. The authors analyse two distinct regimes for how reflections are committed to memory. In the first regime, free-form reflection, every generated reflection is appended unconditionally, mixing corrective information with hallucinated information in the same update. Under a one-sided drift condition, the authors derive a finite-time upper bound on the expected sub-optimality, showing that the mean error converges to a floor proportional to the ratio of the residual error load to the corrective drift rate. This upper bound is shown to be tight in the worst case: there exist processes satisfying the drift condition for which the bound is achieved exactly.

A universal lower bound requires a lower drift condition, which is directly testable by regressing the next-step error on the current error in free-form trajectories. Under persistent harmful commitment, the authors prove that the mean error cannot fall below a positive floor, regardless of the initial condition. Combining both bounds yields a two-sided error tube: the asymptotic mean error lies between the ratio of the lower error load to the upper drift rate and the ratio of the upper error load to the lower drift rate. When the two conditional drift bounds match, the mean error converges exactly to the common ratio.

On the slower timescale, the leader's outer loop follows an analogous affine recursion. The authors use only a finite-episode statement for the leader and make no asymptotic regret claim.

3.2 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. The authors formalise this through a pair of environments that are indistinguishable at the text level. A self-contained gate is any acceptance rule measurable with respect to the generated text process and its internal randomness only, whereas a grounded gate may additionally observe an environment-dependent signal such as realised reward, simulator state, test execution, or a formal-checker result.

The authors construct an ambiguous-pair of environments in which the same text is corrective in one environment and harmful in the other. For every self-contained gate and every horizon, the maximum expected error across the two environments is at least the initial error. Moreover, if the initial error is strictly below one half and the gate accepts at least one ambiguous proposal with positive probability, the inequality is strict. In contrast, the free-form rule that accepts everything drives the error toward one half in both environments, whereas a grounded gate that observes the environment-dependent signal accepts only the corrective class and drives the error to zero geometrically. The impossibility result is minimax over text-indistinguishable environments: textual self-evaluation remains useful when the transcript itself certifies correctness, but when truth depends on external state, judge capacity cannot substitute for grounding.

3.3 SRMA: Verifier-Gated Reflection

The impossibility result 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. The authors therefore separate the stochastic proposal mechanism from the grounded evaluation protocol.

A verifier is a deterministic map that produces a diagnostic score for a candidate output. The verifier risk of a memory is the score of the deterministic evaluation output computed under that memory. The pair of verifier and evaluation protocol 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.

The verifier-gated update proceeds as follows. Given the current execution memory, the authors compute the evaluation output and its diagnostic score. They then sample a reflection conditioned on the output, the diagnostic, the subtask, and the current memory, forming a candidate memory. The candidate is accepted only if its verifier risk is strictly lower than the current risk; otherwise the current memory is retained. Gating on two stochastic one-shot outputs would not suffice, since sample variation could accept a memory with worse expected performance. Exact guarantees therefore assume deterministic or exact expected-risk evaluation.

Under verifier calibration, zero verifier risk certifies zero task sub-optimality. Under a non-degenerate corrective mass assumption, the acceptance probability is bounded below by a power of the current risk. Under a proportional accepted decrement assumption, the expected risk reduction upon acceptance is at least a constant fraction of the current risk. These assumptions yield a monotone multiplicative drift: the expected next-step risk is bounded by the current risk minus a term proportional to a power of the current risk. This leads to exact convergence with rates that depend on the exponent: geometric convergence when the exponent is zero, and polynomial convergence when the exponent is positive. The rates are shown to be tight up to constant factors in the time scale.

When deterministic risk evaluation is unavailable, the authors provide a confidence-gated stochastic evaluation procedure. The current and candidate risks are estimated with independent probes, and acceptance occurs only when the candidate estimate plus a confidence margin is strictly below the current estimate minus the same margin. With high probability, every accepted update strictly decreases the true expected verifier risk. The authors also address piecewise-stationary environments: when the verifier risk changes finitely many times, the convergence guarantee applies on the final stationary segment with the appropriate horizon and initial risk.

The exponent in the drift condition is observable: the geometric regime is linear in log risk versus time, while the polynomial regime is linear in log risk versus log time with slope equal to the negative inverse of the exponent. Estimating this exponent from acceptance frequencies and from trajectory decay enables closed-loop calibration. In practice, the algorithm probes the candidate under the same fixed protocol and commits only a strict improvement; recomputing the current risk enables re-anchoring under piecewise-stationary changes, and under stochastic evaluation the acceptance test is replaced by the confidence-gated procedure.

Experiment

The evaluation spans Resource Contest, Overcooked, and SWE-bench, using environment ground truth or repository test harnesses as verifiers. Grounded SRMA consistently outperforms text-only or ungated baselines: it reaches 98.5-99.5% of oracle reward in Resource Contest while cutting mean regret by 60.8%, improves Overcooked scores by 14-30% across layouts, and halves final risk via better gate selectivity. The adaptive gate matches fixed-sample reliability with 64% fewer verifier calls, and re-anchoring enables fast detection of drifting optima. On SWE-bench, bilevel SRMA with a grounded gate resolves 72.2% of instances versus 58.4% for ungated coordination, with the gain attributed to grounded, gated coordination rather than raw model strength.

Across all Overcooked layouts, the grounded SRMA method consistently achieves the highest scores under matched interaction and model-call budgets, outperforming greedy, no-memory, free-form, and self-gated baselines. The performance gap is most pronounced in the centre_pots layout, where the grounded method more than doubles the greedy baseline score, and least pronounced in cramped_room, where all methods benefit from higher absolute scores. The results indicate that grounding coordination with a deterministic verifier and gating memory updates provides a robust improvement over both ungated and self-gated alternatives. Grounded SRMA achieves the top score in every layout, with the largest relative gain over greedy in centre_pots (260 vs. 40). Self-gated memory consistently outperforms free-form memory, but grounded SRMA exceeds both, showing the value of verifier-based grounding. The improvement from grounded SRMA over self-gated is similar across layouts, roughly 40 points, indicating a consistent benefit from grounding. Greedy scores are the lowest in all layouts, with the smallest gap to other methods in cramped_room, suggesting that layout complexity moderates the benefit of coordination.

On the Resource Contest benchmark, the proposed SRMA method consistently outperforms both epsilon-greedy and a no-memory variant across all difficulty settings, approaching oracle-level performance. The execution-memory ablation shows that adding memory improves average reward and substantially reduces regret, highlighting the importance of memory for coordination. SRMA achieves 98.5% to 99.5% of oracle reward across all RC settings, outperforming both epsilon-greedy and no-memory baselines. Execution memory adds 2.6 reward points on average and cuts mean regret by 60.8%, from 4.33 to 1.70.

Grounded SRMA substantially reduces harmful proposal acceptance and risk compared to free-form or self-gated methods, while improving helpful acceptance. The adaptive gate achieves reliability comparable to fixed verification with far fewer verifier calls, and re-anchoring is critical for quickly adapting to shifted optima. Grounded SRMA cuts harmful acceptance from 100% (free-form) to 6.2% and reduces risk from 0.42 to 0.14, while increasing helpful acceptance from 72.8% to 85.4%. Self-gating already lowers harmful acceptance to 34.5% and risk to 0.28, but grounded SRMA further halves risk and reduces harmful acceptance by more than fivefold. The adaptive gate matches the reliability of fixed K=5 verification (7.1% vs. 6.8% false acceptance) while using 63.6% fewer verifier calls. Re-anchoring the grounded gate cuts post-shift regret by 67.0% and switch time by 67.9% compared to a stale-anchor variant, and the text-only gate fails to detect the shift entirely.

On SWE-bench, the bilevel system with grounded gating outperforms both free-form multi-agent reflection and a single-agent baseline across two backbones. The gain is attributed to the grounded verifier gate, which filters unverified reflections and improves resolution rates under matched budgets. Bilevel SRMA with Kimi K2.5 resolves 72.2% of instances, exceeding free-form multi-agent reflection (58.4%) and the public single-agent reference (70.8%). With DeepSeek, the grounded gate still provides a clear advantage (71.4% vs. 68.2%), showing the effect is not backbone-specific. The free-form ungated variant performs worst, indicating that unverified reflections hurt performance despite having the same multi-agent setup.

Across Overcooked, Resource Contest, and SWE-bench, the grounded SRMA method consistently outperforms greedy, free-form, and self-gated baselines under matched budgets, with the largest gains in coordination-heavy layouts and approaching oracle-level performance on Resource Contest. Grounding via a deterministic verifier and gating memory updates reduces harmful proposal acceptance and risk while improving helpful acceptance, and the adaptive gate matches fixed verification reliability with far fewer verifier calls. Re-anchoring the grounded gate is critical for adapting to shifted optima, cutting post-shift regret and switch time substantially. On SWE-bench, the bilevel system with grounded gating improves resolution rates over free-form reflection and single-agent baselines across two backbones, confirming that unverified reflections are detrimental and that verifier-based grounding provides a robust, backbone-independent benefit.