Verify, Repair, Repeat, or Stop? Robust Stopping for Noisy Verify-Repair Loops in LLM Agents¶

🕒 Published (v1): 2026-07-20 07:52 UTC · Source: Arxiv · link

Why this paper was selected

Formal stopping criteria for noisy verify-repair loops; directly governs agent loop design

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Verify-repair loops in LLM agents fail when both the verifier and repairer are noisy: verifier acceptance rates can keep rising while true plan validity falls. VRR-Stop introduces a four-parameter noise model and belief-filtering framework that stops repair when the expected marginal validity gain turns negative, achieving a 60.6 percentage-point improvement in true validity over fixed five-round repair on GSM8K at an average cost of only 0.72 repair rounds.

Problem¶

Existing verify-repair loop implementations in LLM agents implicitly assume (1) multi-round repair monotonically improves true quality and (2) verifier outputs reflect true validity. Both assumptions fail simultaneously under noisy verifiers and repairers: false rejections trigger harmful repairs that damage valid plans, while false acceptances mask the damage, causing reported verification rates to diverge upward from true validity. No prior work formalizes the stopping decision as an identifiability problem under joint verifier-repairer noise.

Method¶

Four-parameter noise model. The system is characterized by $(\rho_0, \rho_1, \alpha, \beta)$: verifier false-acceptance rate, verifier false-rejection rate, repair success probability (invalid→valid), and repair damage probability (valid→invalid). Youden's discrimination $J = 1 - \rho_0 - \rho_1$ governs whether stopping is identifiable.

Belief filtering (VRR-Stop). Given $M$ independent verification votes per round with acceptance count $S_k$, the committed validity posterior $b_k = \Pr(y_k=1 \mid H_k)$ is updated via a Bayesian observation step: $$b_k = \frac{b_k^-(1-\rho_1)^{S_k}\rho_1^{M-S_k}}{b_k^-(1-\rho_1)^{S_k}\rho_1^{M-S_k} + (1-b_k^-)\rho_0^{S_k}(1-\rho_0)^{M-S_k}}$$ followed by a predict step $b_{k+1}^- = (1-\beta)b_k + \alpha(1-b_k)$ if repair is issued. The one-step marginal gain is $G_k = (1-b_k)\alpha - b_k\beta$, which is zero at the critical belief $b^* = \alpha/(\alpha+\beta)$. The loop commits when $G_k \leq \tau$ and repairs when $G_k > \tau$.

Calibration. $(\rho_0, \rho_1)$ are estimated via binomial-mixture EM on unlabeled repeated verification records; $(\alpha, \beta)$ are frequency estimates from at most 300 labeled before-after plan pairs. Sign identifiability requires $|\hat{G}_k - \tau| > B_k$ (error radius), jointly determined by $J$, sample size, and decision margin $\Delta_k$.

VRR-Guard (fallback). When $J$ is near zero or sign identifiability fails, a conservative keep-best rule replaces the incumbent only when the new plan's vote count exceeds the champion's by a margin $\delta$: $c_k = p_k$ iff $S(p_k) \geq S(c_{k-1}) + \delta$. Erroneous replacement probability is bounded by $\exp(-(MJ+\delta)^2/(2M))$ via Hoeffding.

Key Contributions¶

Four-parameter loop-dynamics model $(\rho_0, \rho_1, \alpha, \beta)$ that explicitly separates verifier noise from repairer noise and characterizes true validity trajectories over repair rounds.
Belief-filtering stopping criterion driven by the sign of the true marginal gain $G_k$, requiring only sign identifiability rather than accurate parameter recovery.
Formal sign-identifiability criterion (Proposition 1): stopping-sign consistency at probability $\geq 1-\eta$ when the error radius $B_k$ does not straddle $\tau$.
VRR-Guard: an estimation-free conservative fallback with an exponential bound on erroneous replacement of valid incumbents.
Empirical characterization of the reliability boundary as a function of verifier discrimination $J$ and decision margin $\Delta$.

Results¶

GSM8K stress setting: VRR-Stop improves final true validity by +60.6 percentage points over fixed five-round repair at a mean cost of 0.72 repair rounds.
Across all tasks (GSM8K, MATH-500, MBPP, BFCL) and model families (Qwen2.5, Mistral, Llama), VRR-Stop avoids the post-peak validity decline exhibited by fixed-budget baselines.
Measured repair damage probability $\beta$ reaches up to 0.94 in practice, confirming the non-corner-case nature of repair harm.
VRR-Guard retreats to near no-repair downside protection when calibration is unreliable, without catastrophic collapse under distribution shift.
Sign-flip risk is governed jointly by $J$ and $\Delta_k$, not by absolute estimation error magnitude alone.
Baselines include fixed-budget repair (Self-Refine style), consecutive-pass-count rules, and score-threshold heuristics.

Limitations¶

The noise model assumes $(\rho_0, \rho_1, \alpha, \beta)$ are stationary within a local decision window; non-stationarity under model/task distribution shift degrades calibration.
Repeated verification queries on the same plan are assumed conditionally independent given true state; within-plan correlation violates this and requires a beta-binomial correction (analyzed in an appendix but not the primary path).
Labeled repair transitions (up to 300 pairs) are required for $\alpha, \beta$ estimation; purely unsupervised calibration of the repairer is not provided.
The stopping criterion is myopic (one-step look-ahead); it may suboptimally stop when a two-step repair trajectory would recover a damaged plan.
VRR-Guard mode selection is done offline via held-out labeled samples, not an online adaptive switch.
Evaluation is limited to binary validity; continuous quality signals are not modeled.

Relevance to Agentic AI / LLM Agents¶

VRR-Stop directly addresses a structural failure mode in the verify-repair-repeat pattern that underpins a wide class of LLM agent architectures for code generation, tool use, and reasoning — the same loop used in Self-Refine, Reflexion, CRITIC, and process-reward-model-guided inference. The core finding — that proxy acceptance signals decouple from true validity under joint verifier-repairer noise, and that repair can actively degrade already-correct plans — challenges the implicit assumption behind much of inference-time scaling and agentic self-correction work. The belief-filtering framework and sign-identifiability analysis provide a principled replacement for the heuristic fixed-budget and consecutive-pass stopping rules widely deployed in production agents, with direct implications for any system that uses iterative LLM feedback to refine plans, code, or tool-call sequences.