Quickest Detection of Hallucination Onset: Delay Bounds and Learned CUSUM Statistics

Igor Itkin

Source-linked AI summary

Quickest Detection of Hallucination Onset: Delay Bounds and Learned CUSUM Statistics

Igor Itkin

arXiv:2606.12476v3Jun 10, 2026cs.LGcs.AIcs.CL

TL;DR

Hallucination onset detectors are usually evaluated as token classifiers, leaving their reaction time under low false-alarm constraints unclear. This paper frames onset detection as quickest change detection and shows that a causal recurrent labeler acts as a learned CUSUM, detecting caught onsets faster than parametric and linear baselines while remaining far above the theoretical floor.

Problem
Hallucination monitors need to detect the onset quickly, but classifier metrics such as token-level AUC do not measure reaction delay.
Method
The paper models hallucination onset as sequential change-point detection and interprets a causal recurrent labeler as a learned CUSUM over causal feature streams.
Results
About 1.3 tokens is the RAGTruth lower bound at a 1% false-alarm rate, while the recurrent labeler detects caught onsets two to three times faster than parametric CUSUM and linear baselines but remains an order of magnitude above the bound.
Takeaways & Limitations
Improving the score’s realized divergence is the main lever for reducing achievable delay, whereas recalibration cannot remove the information-rate deficit.
Takeaways & Limitations
Correlated windowed and cumulative features make the 1.3-token floor optimistic, so the reported gap is a lower bound on the true gap.

Abstract

from arXiv · show

Token-level hallucination detectors are evaluated as classifiers, by AUC over all tokens, yet a streaming monitor is judged by its reaction time: the number of tokens that pass between the onset of a hallucination and the alarm. We formulate hallucination onset detection as a quickest change detection problem. A first-order Markov model of the latent faithful/hallucinated state, validated on RAGTruth, places the task inside classical change-point theory and yields Lorden's lower bound on detection delay: about 1.3 tokens at a false-alarm rate of 0.01. We then show that a causal recurrent labeler acts as a CUSUM with a learned increment. Among the onsets it catches it detects in 11-13 tokens, against 31 for a linear per-token baseline, though at this false-alarm budget every detector catches under a third of onsets and the recall-honest delay is 56-66 tokens: low-false-alarm onset detection is hard. A controlled decomposition attributes the speed advantage mostly to a better per-token score rather than to temporal accumulation. An information-rate optimality theorem of Donsker-Varadhan type explains the remaining order-of-magnitude gap: the learned score realizes only 1/4.5 of the divergence the features carry, a deficit that recalibration cannot remove, with the remainder a finite-horizon effect. Classification metrics conceal this delay structure; sequential analysis makes it measurable.

1 Introduction

The paper reframes hallucination onset detection as quickest change detection, where reaction time at a fixed false-alarm rate matters more than token-level AUC. It derives a 1.3-token lower bound, evaluates learned CUSUM-style detectors, and attributes their remaining delay gap mainly to limited information rate and finite-horizon effects.

Motivation: Quickest change detection measures how many tokens pass between hallucination onset and alarm, whereas conventional evaluation uses token-level ROC AUC over all tokens.A ten-token-late alarm can already expose a false claim to the reader.
Change-point formulation: 1.3 tokens is the Lorden delay floor at a 1% false-alarm rate under a validated first-order Markov model of faithful and hallucinated states.Higher-order fits add under 0.35% of log-likelihood each, while order one captures 99.7% of the structure.
Detector comparison: 11–13 tokens is the learned CUSUM’s delay among caught onsets, versus 31 tokens for the linear per-token baseline at the same false-alarm rate.The recurrent state accumulates evidence, while its learned log-odds serve as cumulative log-likelihood-ratio increments.
Detector comparison: Most of the learned CUSUM’s speedup comes from a better per-token score: the nonlinear per-token model reaches 18 tokens, while sequential accumulation contributes about a quarter of the reduction.The extra causal context is within noise, and the decomposition is significant under bootstrap.
Gap analysis: 1/4.5 of the feature divergence is realized by the learned score, creating a recalibration-invariant information-rate shortfall, with the remainder a finite-horizon effect.The asymptotic correlation penalty overshoots tenfold because detection precedes score mixing.

2 Hallucination Onset as Sequential Change-Point Detection

The section frames hallucination-onset monitoring as a causal quickest-change-detection problem: detect the first hallucinated token quickly while controlling false alarms. It formalizes onset, stopping rules, ARL0, and EDD, and sets the objective of minimizing EDD subject to ARL0 ≥γ.

Definitions: The onset is the first hallucinated token, θ = min{t : y_t = 1}, while hallucination spans are maximal consecutive runs of hallucinated labels.Generations without hallucinations have θ = ∞.
Online detection: A detector reads token features causally and raises an alarm at a stopping time τ determined only by X_1:t.Features include text statistics, NLI signals, and generator log-probabilities.
Change-point formulation: Before onset features follow P0 and from onset onward follow P1, making the task a standard quickest-change-detection problem with detection speed and false alarms in tension.The detector should alarm soon after θ without alarming beforehand.
Markov model: Order one is sufficient for the hallucination-label Markov model because higher orders add under 0.35% of log-likelihood each.Higher orders are significant by the likelihood-ratio test but provide little additional fit.
Operating characteristics: EDD measures tokens from onset to alarm, whereas ARL0 measures the mean number of faithful tokens before a spurious alarm.The paper estimates ARL0 by concatenating hallucination-free generations rather than capping measurement at a single document.
Optimization objective: The detector objective is to minimize EDD subject to ARL0 ≥γ.The following sections derive the lowest achievable delay and evaluate real detectors against it.

3 Theory

The theory models hallucination onset as a first-order Markov change point, establishes a 1.3-token feature-based delay floor, and characterizes recurrent labelers as learned CUSUM-like detectors. It further shows that departures from the floor are governed by the learned score’s realized information rate.

Classical delay bound: 1.3 tokens is the best possible delay from features at ARL0 = 100, while the label-space oracle has a 1.0-token floor.The feature bound uses D(P1∥P0) ≈3.5 nats; the label-space divergence is ≈4.6 nats.
Recurrent realization: A causal recurrent labeler trained by cross-entropy consistently estimates the optimal sequential detector as its approximation and finite-sample score errors vanish.The Bayes-optimal onset detector thresholds a finite-dimensional change posterior filter, while the cross-entropy minimizer supplies the exact log-likelihood-ratio CUSUM increment.
Information-rate optimality: D(p1 ∥p0) /I(s) is the exact multiplicative delay gap for a general score, with equality only when the score is affine in log(p1/p0).The realized information rate is bounded by the feature divergence, and the log-likelihood-ratio score attains the delay floor.
Sources of the gap: The dominant source of delay beyond the floor is the learned score’s realized divergence shortfall, while a smaller residual comes from finite-horizon dependence.The shortfall is a property of score shape rather than scale and is close to irreducible for the features discussed in Section 4.3.

4 Experiments

On RAGTruth, detectors are compared at matched false-alarm budgets using both delay among detected and recall-honest censored EDD. The ForwardGRU is faster largely because of its per-token score, but low-false-alarm onset detection remains difficult and its delay is far above the theoretical floor.

Evaluation setup: 2,700 generations comprise the RAGTruth test split, including 943 hallucinated and 1,757 clean generations.The detectors use 33-dimensional per-token features and are threshold-matched at a common ARL0.
Evaluation metrics: Two delays are reported: delay among detected measures firing speed, while censored EDD charges missed onsets the maximum possible delay.Recall is reported alongside both metrics, preventing low recall from making delay appear artificially favorable.
Detection results: 11.5 tokens versus 30.8 for the linear per-token baseline gives ForwardGRU CUSUM a 2.7× speedup at ARL0 = 100.HistGBM detects in 17.9 tokens without sequence accumulation, closing most of the gap and showing that the advantage is mainly a better per-token score.
Detection results: 41 tokens is the diagonal-Gaussian CUSUM delay, because its misspecified feature model produces a noisy likelihood-ratio increment.Adding features worsens this baseline by adding further Gaussian-model error.
Information-rate analysis: 0.78 nats per token is the learned score’s information rate versus 3.5 nats of feature divergence, yielding a 4.5× first-order delay shortfall.The resulting i.i.d. first-order delay is 5.9 tokens, while the ForwardGRU CUSUM detects in 11.5 tokens against the 1.3-token floor.
Low-false-alarm regime: 56–66 tokens is the recall-honest censored EDD at ARL0 = 100, where recall is near 30% for every drift detector.Most hallucination onsets are therefore not caught within the tight false-alarm budget.

5 Discussion

The discussion argues that quickest-change framing exposes reaction-time limits hidden by token AUC, while the recurrent detector’s empirical advantage comes mainly from better per-token scores. It also shows that low-false-alarm onset detection remains difficult because learned scores capture only about a fifth of available divergence.

Motivation: Token AUC omits reaction time, whereas the Lorden floor measures how quickly any detector could possibly react.The change-point formulation supplies a deployment-relevant yardstick.
First lesson: Two to three times faster: the causal recurrent labeler outperforms parametric CUSUM and linear per-token models at a matched false-alarm rate.It behaves as a learned CUSUM, but most of its gain comes from a better per-token score.
Second lesson: About a fifth: the learned score realizes only this fraction of the divergence carried by the features.This information-rate deficit is invariant to recalibration and barely changes under monotone reshaping, so deeper models are not the direct remedy.
Feature structure: 0.065 higher recall: a covariance-term CUSUM beats the best per-token scalar at ARL0 = 100 on open-weight generators.The 95% bootstrap CI is [0.03, 0.10], with comparable per-detection delay; the gain comes from covariance change rather than a mean shift.
Third point: Under a third: detectors catch fewer than this share of onsets at their first token at the floor’s operating point.Low-false-alarm streaming monitors therefore miss most onsets initially, a difficulty concealed by token-level AUC.

6 Conclusion

The conclusion frames hallucination onset as a change-point, establishing a 1.3-token lower bound at a 1% false-alarm rate and motivating learned CUSUM monitoring. It identifies realizable divergence as the dominant improvement lever while attributing the residual gap to finite-horizon effects.

6 Conclusion: 1.3 tokens at a 1% false-alarm rate is the reaction-time floor for RAGTruth under a first-order Markov faithful/hallucinated state model.The change-point formulation supplies a speed yardstick that the classification view lacks.
6 Conclusion: A causal recurrent labeler acts as a learned CUSUM for hallucination-onset detection.The supplied passage introduces this interpretation before reporting the labeler’s detection range.
6 Conclusion: Doubling D(P1∥P0) halves achievable delay, making realizable divergence a larger lever than recalibration.Improving the feature set changes the information rate, whereas recalibration does not.
6 Conclusion: A factor-of-two residual remains because detection can be faster than score mixing, making both i.i.d. first-order and asymptotic correlation corrections non-tight.The passage points to finite-horizon CUSUM analysis as the needed theoretical direction.

7 Limitations · Appendix

The bounds and theorem rely on idealized independence, parametric divergence estimation, first-order delay analysis, and a single-change setup. Results are corpus- and regime-specific, with uncertainty quantified but precise numerical values not broadly transferable.

7 Limitations: The bound and theorem rely on idealizations that affect how their numerical results should be interpreted.The paper explicitly frames these assumptions as limitations on reading the reported numbers.
7 Limitations: Correlated emissions make the 1.3-token floor optimistic because windowed and cumulative features violate conditional i.i.d. assumptions.Several of the 33 features are windowed or cumulative, reducing per-token evidence below D(P1∥P0).
7 Limitations: 3.5 nats is a diagonal-Gaussian estimate of D(P1∥P0), so the bound should be read as an order of magnitude rather than a three-digit constant.The estimator ignores cross-feature dependence and non-Gaussian shape, although it matches the naive CUSUM baseline for a fair comparison.
7 Limitations: The delay-rate result is first-order and measures rather than bounds its residual because score increments are treated as i.i.d.The leftover factor of two is attributed to a finite-horizon effect: detection precedes the score’s mixing time.
7 Limitations: The analysis covers only the first onset of each generation, leaving multiple spans and detector re-arming after a span ends out of scope.Its single-change optimality matches deployments that stop at the first alarm rather than monitor continuously.
7 Limitations: The transition probabilities p, q, divergence, and bound are estimated on RAGTruth, making specific values and the ARL0 at which recall collapses corpus-specific.The qualitative detector ordering is expected to transfer, but the numerical operating regime may not.
7 Limitations: 95% bootstrap confidence intervals quantify document-level uncertainty, while delay results come from a model trained with seed 42.The paper also seed-averages the decomposition, but the supplied passage ends before reporting further details.

A Data and Label Estimation · B Operating-Characteristic Estimation

The study estimates hallucination-state dynamics from RAGTruth and evaluates detector operating characteristics on concatenated clean and hallucinated streams. It defines onset and alarm delays using token-level state labels and threshold crossings.

A Data and Label Estimation: 2,700 test generations contain 943 with hallucinated spans and 1,757 clean generations, totaling about 341,000 tokens at a 4.16% hallucination rate.The training split contains about 1.98 million tokens for estimating transition probabilities and feature divergence.
A Data and Label Estimation: A token receives label 1 inside a human-annotated hallucination span and label 0 otherwise.These labels define the faithful-versus-hallucinated state sequence used for estimation.
A Data and Label Estimation: The transition matrix is estimated by counting every adjacent label pair into a 2 × 2 table and normalizing each row.Higher-order transition rows use the same count-and-normalize estimator with a length-k context.
A Data and Label Estimation: p ≈0.0044 and q ≈0.907 yield an onset-hazard persistence ratio q/p > 200.Saved detector posteriors differ from reference labels by about 0.05% of tokens, too little to change p, q, or the bound.
B Operating-Characteristic Estimation: ARL0 is estimated by running each detector at a fixed threshold on the concatenation of all hallucination-free generations.This uses a clean stream rather than separately segmented documents.
B Operating-Characteristic Estimation: ARL0 equals total clean tokens divided by distinct alarms, counting each upward threshold crossing before resetting the statistic.Because documents are not used as separate streams, ARL0 is not capped by document length.
B Operating-Characteristic Estimation: Delay is measured on hallucination generations as alarm position minus onset θ when firing occurs at or after θ.The supplied passage also introduces a maximum-delay measure, but its definition is truncated.

C Speedup Decomposition and Bootstrap · D Models and Features

The decomposition uses fixed-threshold conditional bootstrapping and seed averaging to show that sequential accumulation, rather than extra causal context, explains the robust recurrent speedup. All detectors share a 33-dimensional feature vector, while the ForwardGRU and HistGBM provide distinct model implementations.

C Speedup Decomposition and Bootstrap: ARL0 = 100 thresholds are fixed on the full dataset before resampling generations with replacement (B = 1,000).This conditional bootstrap measures document-level variance without re-matching ARL0 on each resample.
C Speedup Decomposition and Bootstrap: −12.9 tokens is the nonlinear-score reduction in delay when moving from LogReg to HistGBM.The reported 95% confidence interval is [8.8, 17.0].
C Speedup Decomposition and Bootstrap: 3.4 ± 0.7 tokens is the seed-averaged delay reduction from recurrent accumulation.Detectors were retrained under five seeds: 0, 1, 2, 7, and 42.
C Speedup Decomposition and Bootstrap: 0.9 ± 1.6 tokens is the seed-averaged effect of adding causal context.This estimate lies within one standard deviation of zero.
C Speedup Decomposition and Bootstrap: 12.2 ± 1.4 tokens is the seed-averaged ForwardGRU-CUSUM delay.The document-variance result carries over to training variance: accumulation is real, whereas extra causal context is not.
D Models and Features: 33-dimensional per-token features combine text statistics, NLI entailment, and generator log-probabilities for every detector.The feature vector comes from the companion multi-signal system.
D Models and Features: The ForwardGRU is a two-layer unidirectional GRU with hidden width 64 and a sigmoid output head.It is trained with binary cross-entropy and AdamW, using weight decay 10−4, seed 42, and a 15% stratified validation split.
D Models and Features: The HistGBM is a gradient-boosted classifier with 500 trees, learning rate 0.05, and up to 63 leaves per tree.It operates on the shared per-token feature vector.

E Closing the Gap: Details

The learned score captures only a fraction of the feature information rate, and temperature scaling cannot close this gap. Strong score autocorrelation makes asymptotic dependent-data predictions overly pessimistic because detection occurs within the correlation time.

Information-rate gap: 4.5× is the ratio between feature divergence D ≈3.5 nats and the learned score’s information rate I(ĝ) = 0.78 nats per token.The learned rate uses Lundberg exponent ω = 0.95 and post-change drift δ₁ = 0.82.
Information-rate gap: Temperature scaling leaves I(ĝ) exactly invariant, with ω transforming to ωT and δ₁ to δ₁/T.Thus rescaling the score does not increase its realized information rate.
Finite-horizon effect: ρ₁ = 0.94 and τ ≈22 indicate strong clean-stream score autocorrelation, while the dependent-data adjustment coefficient is ω⋆≈0.044.The adjustment coefficient is read from the detector’s own ARL₀–threshold curve and falls below the marginal ω by the factor τ.
Finite-horizon effect: 126 tokens is the asymptotic dependent-data delay prediction, versus 11.5 observed, because detection occurs well inside the score’s correlation time.The order-of-magnitude discrepancy is identified as the finite-horizon residual of Section 4.3.

F Robustness of the Deficit

The deficit is governed by standardized separation rather than score scale: context and informative features improve the rate, while variance-only optimization and multivariate accumulation do not reliably reduce delay. Self-consistency adds genuine non-Gaussian information, but richer statistics offer little benefit when mean shifts are weak or thresholds become costly.

Rate anatomy: 10–25% agreement between the Gaussian closed form and empirical rate confirms that the rate depends on standardized separation m/σ_0, not score scale.The increments are close to Gaussian, with skewness |·| < 0.5.
Feature augmentation: +0.83 nats of conditional divergence comes from self-consistency features, versus −0.59 for matched random features and ≈0 under a diagonal-Gaussian model.This gain is measured on the Llama-2-7B-chat subset using K = 5 resamples at temperature 0.8.
Feature augmentation: More context raises standardized separation m/σ_0 from LogReg to recurrent models, lowering the deficit.The rate is I = 2m^2/σ_0^2.
Rate-aware objective: 51.3±.6 →52.6±1.9 tokens shows that penalizing clean-token log-odds variance leaves censored EDD essentially unmoved because m falls with σ_0.The rate-aware objective lowers σ_0 but preserves m/σ_0; a discriminant-ratio objective instead collapses by driving σ_0 →0 and inverting the score.
Multivariate accumulation: 0.40 nats of Mahalanobis mean separation in raw features makes multivariate accumulation poor, while 1.5 nats in hidden states still yields no improvement over the trained scalar head.The hidden-state GLR is worse because its 64-dimensional quadratic form requires a higher alarm threshold to maintain ARL0, costing recall.

G Proofs

The proofs characterize CUSUM delay and false-alarm scaling, then show that the optimal information-rate score is the log-likelihood ratio. The resulting multiplicative gap is D/I(s), estimated as approximately 4.5 for the learned score.

CUSUM setup: The CUSUM uses centered increments Y_t = s(X_t)−k, reflected statistic S_t = max(0, S_{t−1}+Y_t), and stopping time τ = inf{t : S_t ≥ h}.The post-change drift is δ_1 = E_1[Y] > 0, while the Lundberg exponent ω solves E_0[e^(ωY)] = 1.
Delay proof: Under positive post-change drift, the first-order delay satisfies E_1[τ] ≈ h/δ_1 after reflection and overshoot terms become negligible.The reflected walk decomposes into a free random walk plus accumulated reflection, with E_1[L_τ] = O(1).
False-alarm proof: ARL_0 = E_∞[τ] = e^(ωh)(1+o(1)), so the threshold scales as h = ω^−1 ln ARL_0 (1+o(1)).This follows by exponential tilting under the Lundberg condition and a renewal estimate for level crossing.
Information-rate optimality: The delay bound EDD ≈ ln(ARL_0)/I(s) ≥ ln(ARL_0)/D is attained exactly when s is affine in the log-likelihood ratio.The equality condition comes from the Donsker–Varadhan variational formula applied with f = ωY.
Gap identity: D/I(ŝ) ≈ 4.5 for the learned score, quantifying its multiplicative delay deficit relative to the information-theoretic floor.At false-alarm budget ARL_0, score delay is ln(ARL_0)/I(s), while the floor is ln(ARL_0)/D.