Delayed Verification Destabilizes Multi-Agent LLM Belief: Instability Thresholds and Optimal Corrector Placement

Igor Itkin

Source-linked AI summary

Delayed Verification Destabilizes Multi-Agent LLM Belief: Instability Thresholds and Optimal Corrector Placement

Igor Itkin

arXiv:2606.27409v1Jun 25, 2026cs.MAcs.CLcs.LGeess.SY

TL;DR

Delayed verification can destabilize belief in multi-agent LLM debates, but the dynamics behind this failure are not well characterized. The paper models delayed consensus with grounded correctors and shows that verification has dose-delay stability thresholds, with oscillations in signed-belief tasks but not grounded factual answering.

Problem
Multi-agent debate can lose accuracy without a dynamical account of how exchanged claims and delayed verification drive failure.
Method
The paper models delayed consensus on graphs with grounded corrector nodes, derives spectral stability thresholds, and formulates greedy corrector placement.
Results
Across five open models, theory-predicted dose-delay oscillations appeared in signed-belief debates, with overshoot in 96–100% of unstable runs versus 0–4% when stable.
Takeaways & Limitations
Verification has an optimal dose and placement: excessive or delayed correction can destabilize signed belief, whereas grounded factual verification remains stabilizing.
Takeaways & Limitations
The analysis is local and linear, and the placement rule has been validated only on a linear surrogate rather than with LLM agents.

Abstract

from arXiv · show

Multi-agent large language model (LLM) systems often rely on verifier and critic agents to suppress hallucinations, but verification is delayed. During this delay, false claims can propagate through the agent network. We model this process as delayed consensus on a graph with grounded corrector nodes. Spectral decomposition by the grounded Laplacian yields a closed-form stability threshold for the verification dose: correction that is too strong or too delayed can turn consensus into oscillation. The most unstable regime occurs when the communication and verification delays coincide; for delay two, the threshold is the inverse golden ratio. The same framework gives a supermodular placement objective and a greedy (1-1/e)-approximation rule for assigning a limited corrector budget to influential nodes. Experiments across five open models confirm the predicted dose-delay oscillations. By contrast, grounded factual answering makes truth an absorbing boundary and eliminates the effect, suggesting that the instability is specific to signed-belief tasks while grounded verification remains stabilizing

1 Introduction

The paper models delayed LLM verification as a grounded, delayed-consensus process in which propagated false claims can become unstable. It derives dose, delay, and corrector-placement results, then validates a signed-belief instability that does not occur in grounded factual debate.

Motivation: Multi-agent hallucinations become dynamic cascades as agents exchange, revise, and reuse claims, while verification latency allows unverified claims to propagate.The paper frames delayed negative feedback as a potential source of oscillation and instability in the verification loop.
Model and reduction: The corrected multi-agent loop reduces to independent scalar delay recurrences through spectral decomposition of the grounded Laplacian.The model is formulated as delayed consensus with grounded corrector nodes.
Stability thresholds: Above a critical correction strength, the loop oscillates rather than converges; the dose ceiling decreases with verification delay and reaches the inverse golden ratio at delay two.The paper presents this as a closed-form verification-dose limit.
Corrector placement: A supermodular coherence objective yields a greedy corrector-placement rule within 1 −1/e of optimal, concentrating limited budget on amplifier and bridge nodes.Truth-tracking error is governed by a resolvent.
Empirical regime dichotomy: Across five open models, signed numeric-estimation debates show the predicted dose–delay oscillation, whereas grounded factual debates remain convergent under the same delay.The dose was fixed a priori from βc(δ) without fitting, indicating that the instability is specific to signed belief rather than grounded factuality.

2 Related work

The paper connects empirical reliability research in multi-agent LLMs with delayed-feedback control and detection theory, addressing the lack of delay/stability guarantees for factuality verification. It extends prior consensus, feedback-control, and network-control work by modeling verification delay and deriving stability and placement results.

LLM reliability: Prior multi-agent LLM reliability studies characterize how errors arise and spread between agents but generally treat the process statically.Jamshidi et al. report that deeper chains lower explicit hallucination scores while reducing factual accuracy, with confidence-weighted aggregation and selective isolation as mitigations.
Delayed-feedback dynamics: Earlier dynamical models cover DeGroot consensus, hidden-anchor deliberation, and static-threshold self-correction, but not delayed verification.The paper identifies the delayed corrector—not gossip—as the source of its instability, distinguishing its model from the delay-free factuality recurrence of [2].
Detection: Post-hoc failure-step attribution remains difficult, while newer detection work uses trajectory-prefix auditing, cross-channel causal-influence monitoring, and temporal-graph anomaly detection.Frontier models achieve 11–41% step-localization.
Control and detection: The control framework builds on CUSUM, Shiryaev–Roberts and minimax change detection, mature LLM signals such as semantic entropy and SelfCheckGPT, and Kuruklis’s discrete delay-stability result.The paper specializes Kuruklis’s result to obtain its dose boundary.
Corrector placement: Grounded-Laplacian convergence-error coherence is supermodular, enabling greedy (1−1/e) leader-selection guarantees unlike Sherlock’s counterfactual verifier-placement heuristic, which lacks optimality and stability guarantees.This places the paper’s allocation results within classical network control while contrasting them with the only identified LLM-side analogue.

3 Model

The model represents multi-agent deliberation as scalar-belief consensus on a symmetric graph, with grounded correctors restoring beliefs toward truth after delay. Its dynamics assume reciprocal influence, oracle-but-delayed correction, and grounding reachability for all free agents.

Belief and correction dynamics: Agents revise scalar claim beliefs toward neighbours while designated correctors with verified evidence push beliefs toward ground truth after latency.Correctors are modeled as having access to verified evidence, while correction acts after a verifier reads and retrieves evidence.
Belief and correction dynamics: Corrector nodes are held at truth, while free-agent errors evolve under consensus, delayed verification of gain κ and latency δ, and constant faulty forcing.The grounded Laplacian Lg governs consensus; verification applies to the δ-step-old error with strength κ.
Structural assumptions: The analysis assumes symmetric Laplacian influence, so reciprocal peer-debate or blackboard interactions enable orthogonal modal decoupling.Content-level effects such as truth dilution, claim provenance, and epistemic laundering are excluded; the destabilizing ingredient is delay rather than verifier error.
Structural assumptions: Every free-agent component must connect to a corrector, ensuring Lg ≻0, a unique truth equilibrium, and contraction without delay.A disconnected free-agent group creates a zero mode that no verification dose can stabilize.

4 Stability and the verification dose

Grounded-Laplacian spectral decomposition reduces delayed network stability to independent scalar delay modes. The resulting dose boundary decreases with delay and eigenvalue, so excessive or delayed correction produces verification-induced oscillation.

Grounded-Laplacian decoupling: Spectral decomposition decouples the grounded network into independent scalar delay recurrences, reducing stability analysis to one recurrence per grounded-Laplacian eigenvalue.The transformed mode is x_i,t+1 = a_i x_i,t −ηκ x_i,t−δ + ηĝ_i, with a_i = 1 −ηµ_i.
One-step verification: For δ = 1, stability requires ηκ < 1 and µ_i < 2/η + κ for every mode.At the network level, this becomes ηκ < 1 and µ_max(L_g) < 2/η + κ.
Oscillatory boundary: For general delay, the first instability occurs when a complex-conjugate root pair reaches the unit circle, causing oscillation at angular frequency ω = θ⋆.The critical dose is κ_max(a, δ) = β_c/η, where β = ηκ.
Dose monotonicity: The critical dose β_c(a, δ) strictly decreases with both a and δ, with β_c < 1 for all δ ≥2.The Chebyshev reformulation exposes the boundary’s algebraic form and monotonicity.
Binding mode and dose limit: When ηµ_max(L_g) ≤1, the slowest grounded mode sets the network dose limit; stronger grounding raises µ_min(L_g) and relaxes it.Correction at or above κ_max, or increased delay that lowers κ_max, destabilizes the loop into verification-induced oscillation.

5 Optimal corrector placement

With a limited corrector budget, placement is optimized by a greedy rule because average truth-tracking error has a supermodular placement structure. The rule prioritizes amplifier and bridge nodes and achieves a worst-case (1 −1/e)-approximation to optimal placement.

Greedy placement: Greedy prioritizes amplifier, bridge, and cluster-hub nodes where unverified error reaches the most of the network.Its marginal gain is given by a Sherman–Morrison closed form and acts as a resolvent centrality.
Placement effects: Corrector placement decouples stability from steady-state error: stability depends on spec Lg, κ, δ, whereas error depends on (Lg + κI)−1 acting on fault forcing.The placement R controls both through separate spectral and resolvent mechanisms.
Placement effects: Placing correctors never decreases µmin(Lg), thereby relaxing the stability limit and shrinking the steady-state error bound.The bound holds whenever the loop is stable and is independent of step size η and delay δ.
Greedy placement: A one-pass greedy rule achieves a (1 −1/e)-approximation for corrector placement under a cardinality budget.The reduction in coherence is monotone and submodular, yielding the guarantee for every budget k.
Empirical comparison: With k = 8 correctors, greedy reduced residual error tr M(R)−1 from 9.1 to 2.3, versus 2.9 for degree-based and 2.5 for random placement.The result was obtained on three 5-cliques chained by bridges, with the first picks being bridge and cluster-hub nodes.

6 Two coupled delays

With communication and verification delays coupled, each grounded-Laplacian mode obeys a two-delay recurrence whose oscillatory boundary and stability region can be characterized explicitly. Synchronized delays are least stable, collapsing the safe region and yielding a 1/φ ≈0.618 dose ceiling.

Two-delay stability boundary: Each spectral mode follows the two-delay recurrence x_t+1 = x_t −ηµ x_t−d −ηκ x_t−δ, with unit-circle crossings determined by coupled sine and cosine equations.The parameters are communication delay d, verification delay δ, gossip strength ηµ, and verification strength ηκ.
Two-delay stability boundary: For d ≠ δ, the stability region is bounded by the oscillatory boundary and the λ = −1 real-root line.The boundary is obtained using D-decomposition, and the stability region is the component containing the origin.
Two-delay stability boundary: The general boundary degenerates to the single-delay boundary at d = 0 and to the a = 1 corner as d → δ.This provides consistency with the corresponding limiting cases.
Synchronized delays: Synchronizing communication and verification delays is least stable because a = 1 maximizes the branch, attaining the limiting envelope exactly when both lags coincide.For a single-delay mode under Assumption 1, a = 1−ηµmin < 1 strictly, with the 1/φ ceiling approached as µmin →0.

7 Empirical validation

Empirical studies validate the predicted stability ceiling and show that delayed correction produces oscillations specifically in signed-belief debates. Grounded factual verification instead stabilizes convergence, while excessive or ungrounded correction destabilizes it.

Synthetic validation: κcrit tracks the predicted κmax, with onset within 2% and a measured δ=2 period of 9.38 versus the predicted 9.72.Saturation explains the small overshoot above the ceiling.
Grounded factual debate: A grounded verifier drives factual debates to truth with convergence ≈0.8, whereas wholesale correction lowers convergence to ≈0.4 and ungrounded criticism yields 0 convergence.The ungrounded critic also causes majority-answer flipping in 91% of rounds.
Scope and limitation: Delay-induced oscillation is confined to signed-belief tasks: grounded factual consensus-error amplitude is already present at δ=0 under forcing and vanishes when the majority is removed.Strong independent judgment dampens the instability, making deployed agents more stable than the linear worst case.
Signed-belief debate: At α=0.5, signed-error amplitude is 4.5× larger at δ=6 than δ=1, while zero-crossing overshoots occur in 96% versus 0–4% of runs.The prediction was fixed a priori: stable at δ=1 and unstable at δ=6.
Robustness: The signed dose–delay oscillation replicates across five open models, with 8/8 question-level unanimity and Bonferroni-corrected significance.A 12B Mistral-Nemo also shows the effect directionally, with 58% overshoot and p=0.07.

8 Discussion

Verification behaves like delayed negative feedback with a finite stability budget: excessive strength or delay can destabilize signed-belief dynamics, especially when communication and verification latencies coincide. Grounded factual QA avoids this oscillation because truth is an absorbing boundary that clips overshoot and relaxes the dose limit.

Stability budget: Verification has an optimal dose and placement because it is delayed negative feedback with a finite stability budget.A verifier can be too aggressive or too slow, and the slowest grounded mode binds the constraint.
Stability budget: Synchronizing communication and verification latencies produces the worst design for stability.This conclusion is identified as Corollary 3 in the discussion.
Signed-belief dynamics: For α > βc(δ), signed dynamics make the truth equilibrium an unstable focus and produce a bounded limit cycle crossing zero.The instability occurs in the signed numeric-estimation regime, where xt+1 = xt −α σ(xt−δ) and σ is saturating.
Grounded factual QA: Grounded factual QA eliminates the limit cycle because non-negative distance makes truth absorbing and clips overshoot at the boundary.Grounding also relaxes the dose limit by raising µmin(Lg).

9 Conclusion

The paper models verifier loops as delayed consensus with grounded correctors and derives stability limits showing that excessive or delayed correction can induce oscillation. Theory and experiments identify dose and placement as constrained design choices, while factual answering avoids the instability because truth is absorbing.

Stability and placement: Too-strong or too-delayed correction destabilizes factual consensus into oscillation, with the worst case when communication and verification delays coincide.At delay two, the stability ceiling is the inverse golden ratio.
Stability and placement: A limited corrector budget is best assigned greedily to high-influence nodes, and placement can relax the constraint imposed by the slowest grounded mode.The framework identifies both an optimal verification dose and an optimal application location.
Empirical scope: 96–100% of unstable runs overshot through truth versus 0–4% of stable runs across real LLM debates spanning five open models.A synthetic loop reproduced the predicted onset to within 2%, while an a-priori theory-derived experiment reproduced signed dose–delay oscillations.
Empirical scope: Pure factual question answering does not oscillate because truth acts as an absorbing boundary, indicating that the instability is native to signed-belief tasks.The model’s scope is therefore bounded: grounded factual answering remains stabilizing.

10 Limitations · Appendix A Proof of Proposition 2 (oscillatory boundary)

The paper’s limitations concern local linear analysis, surrogate-only placement validation, and weaker quantitative evidence for grounded factual QA. Appendix A shows that, as β increases, complex-conjugate roots reach the unit circle before real-root crossings, including even delays.

10 Limitations: The analysis is local and linear around truth-consensus, while global or contraction analysis remains open.Nonlinear validation supports the local prediction, but does not close the global analysis.
10 Limitations: The placement rule has been validated only on the linear surrogate, not with LLM agents.The dose limit and placement rule therefore have different validation scopes.
10 Limitations: 96–100% versus 0–4% is the signed numeric-estimation test’s near-deterministic overshoot separation, based on question-level units with n=8 and averaged seeds.The test was fixed a priori from theory and replicated across model families, but is not a large-sample effect-size study.
10 Limitations: p=0.06 for the strong-κ delay effect and p=0.47 for the κ×δ interaction show weaker quantitative support in grounded factual QA.The delayed AR map recovered linear coefficients with precision 1.0 and recall 0.24, consistent with absorbing-boundary damping.
10 Limitations: Future extensions include heterogeneous correction gains, stochastic delays, and coupling the controller to an online change detector.These extensions aim to connect hallucination-cascade detection with stable correction.
Appendix A Proof of Proposition 2 (oscillatory boundary): The oscillatory-boundary proof derives the stability boundary parametrically by separating imaginary and real parts.The appendix gives β(θ) through trigonometric relations involving δ and θ.
Appendix A Proof of Proposition 2 (oscillatory boundary): A root can leave the unit disk through λ=+1, λ=−1, or a complex-conjugate crossing, with the λ=−1 condition depending on whether δ is odd or even.At λ=+1, β=a−1≤0; at λ=−1, β=(−1)^δ(a+1).
Appendix A Proof of Proposition 2 (oscillatory boundary): β_c≤1<a+1 for a∈(0,1] and δ≤8, so the complex pair reaches the unit circle first, including the even-δ case.For even δ, the real λ=−1 crossing at β=a+1 occurs strictly later.

Appendix B Proof of Lemma 2 (monotonicity of the dose) … Appendix E Reproducibility

The appendices prove dose monotonicity, derive the general two-delay oscillatory boundary, establish greedy placement guarantees, and document reproducibility through shared code and data.

Appendix B Proof of Lemma 2 (monotonicity of the dose): The Chebyshev recurrence yields a telescoping continued-fraction derivative for aδ(c) = Uδ/Uδ−1, establishing the monotonicity argument.The proof uses induction on the derivative recurrence wherever Uδ−1 ≠ 0.
Appendix B Proof of Lemma 2 (monotonicity of the dose): The correction strength a strictly decreases for every δ; on the binding branch, values for δ = 1, . . . , 8 are 1, 0.618, 0.445, . . . , 0.185.The boundary cases δ=1 and a=0 are exact, consistent with Kuruklis.
Appendix C Proof of Theorem 3 (general two-delay boundary): Setting λ = e^iθ makes the characteristic equation linear in (p, q), and Cramer’s rule produces the oscillatory boundary curve.Evaluating the characteristic equation at z = −1 additionally gives the real-root line.
Appendix C Proof of Theorem 3 (general two-delay boundary): The general two-delay boundary reduces through the degenerations d = 0 and the limit d →δ.These substitutions connect the general boundary to its two limiting cases.
Appendix D Proof of Theorem 2 (greedy placement): Adding a pinned node is a positive-semidefinite update, so H is non-increasing and ρ(R) = H(∅) − H(R) is non-decreasing.The proof defines H(R) = tr M(R)^−1 and ρ(∅) = 0.
Appendix D Proof of Theorem 2 (greedy placement): The grounded-Laplacian M-matrix structure makes marginal gains non-increasing under additional pinning, proving coherence supermodularity.A sweep found the property in 0/4000 grounded-Laplacian trials, while arbitrary positive-definite matrices violated it in 115/4000.
Appendix D Proof of Theorem 2 (greedy placement): The greedy rule that adds the largest-∆i node at each step attains the Nemhauser–Wolsey–Fisher guarantee for non-negative monotone submodular ρ.The guarantee applies when ρ(∅) = 0.
Appendix E Reproducibility: Every figure and reported number is reproducible from the accompanying code and data repository.The appendix provides https://github.com/YehudaItkin/delayed-verification-llm.