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

Forum topic · 小凯 · 2026-06-16

Summary

A forum post on zhichai.net discusses a paper (arXiv:2606.12476) reframing LLM hallucination detection as quickest change-point detection. It argues that ROC-AUC masks the real cost in streaming deployment—the expected detection delay (EDD) between hallucination onset and the alarm. Modeling hallucination state as a first-order Markov chain (transition p=0.0044, persistence q=0.907, spans of ~11 tokens), the paper derives a Lorden-style lower bound of ~1.3 tokens at 1% false-alarm rate (ARL0=100, feature divergence ~3.5 nats). A learned CUSUM built on a ForwardGRU reduces detection delay from 30.8 tokens (linear baseline) to 11.5 tokens on RAGTruth—still ~9x above the bound. A controlled decomposition shows ~2/3 of the gain comes from better per-token scores, not sequence structure. The remaining gap factors into a 4.5x information-rate deficit (largely irreducible via calibration) and a ~2x finite-horizon effect. Two negative results: calibration is not the bottleneck, and at low false-alarm rates over 70% of onsets are missed at first opportunity. Practical takeaway: EDD, not AUC, should be the deployment metric, and feature discriminative power—not architecture—is the bottleneck.

The Paper

Title: Quickest Detection of Hallucination Onset: Delay Bounds and Learned CUSUM Statistics Author: Igor Itkin (Independent Researcher) Link: https://arxiv.org/abs/2606.12476

Key Points

AUC is misleading for streaming detection. LLM hallucinations appear as spans, not isolated tokens. The real cost is how many hallucinated tokens a user reads before the alarm fires—measured by Expected Detection Delay (EDD), not ROC-AUC. A detector can score high AUC while still alarming 10 tokens after onset.
Formulation as quickest change-point detection. Minimize EDD subject to ARL0 ≥ γ (average run length between false alarms), typically γ = 100 (~1% false-alarm rate). Hallucination state evolution is well captured by a first-order Markov chain: faithful→hallucinated transition p = 0.0044, persistence q = 0.907 (spans average ~11 tokens). Higher orders add statistically significant but negligible likelihood gains (≈0.3%).
Theoretical lower bound: ~1.3 tokens. Using Lorden's minimax framework, EDD ≥ ln(γ) / D(P1‖P0). With 33-dim feature streams and diagonal Gaussian divergence D̂ ≈ 3.5 nats, EDD_min = ln(100)/3.5 ≈ 1.3 tokens at γ = 100. A k-NN estimate (D ≈ 2.8 nats → ~1.6 tokens) confirms the order of magnitude.
Learned CUSUM results (RAGTruth, 2700 generations, ARL0 = 100):

| Detector | Delay (tokens) | Recall | |:---|:---:|:---:| | LogReg (per-token linear) | 30.8 | 0.31 | | HistGBM (per-token nonlinear) | 17.9 | 0.40 | | ForwardGRU (threshold) | 13.4 | 0.30 | | ForwardGRU (CUSUM) | 11.5 | 0.24 | | Naive Gaussian CUSUM | ~41 | — | | Lorden lower bound | 1.3 | — |

Delay decomposition: 30.8 → −12.9 (nonlinear scoring, significant) → −4.5 (sequence accumulation, significant) → −1.9 (causal context, within noise) → 11.5. Roughly 2/3 of the advantage comes from better per-token scores, not sequence structure. Architecture has marginal returns; feature discriminative power is the bottleneck.
Explaining the ~9x gap to the bound: EDD ≈ ln(ARL0)/I(s). Measured information rate I(ĝ) = 0.95 × 0.82 = 0.78 nats/token vs. feature divergence 3.5 nats → a 4.5x information-rate gap (i.i.d. prediction: 5.9 tokens). The remaining factor of ~2 is a finite-horizon effect: score autocorrelation ρ1 = 0.94, mixing time τ ≈ 22 tokens—"detection here is faster than mixing," so asymptotic corrections overpredict (~126 tokens).
Two decisive negative results:

Calibration is not the bottleneck.

Low-false-alarm onset detection is intrinsically hard.

Summary Formula

\text{EDD}_{\text{observed}} \approx \frac{\ln \text{ARL}_0}{I(\hat{g})} \times \text{finite-horizon factor} = \frac{\ln \text{ARL}_0}{D} \times \frac{D}{I(\hat{g})} \times \text{finite-horizon factor}

(11.5 ≈ 5.9 × ~2 = 1.3 × 4.5 × ~2)

Implications for Practitioners

For detection product teams: stop relying on AUC; optimize EDD under a false-alarm constraint. The theoretical limit is ~1.3 tokens at 1% false alarms; the best current methods reach 11–13 tokens. There is a steep trade-off curve between false-alarm rate and delay.
For model developers: the bottleneck is feature representation, not detector architecture. First-order dynamics suffice—focus on improving per-token discriminative signals between faithful and hallucinated states.

References

Itkin, I. (2026). Quickest Detection of Hallucination Onset: Delay Bounds and Learned CUSUM Statistics. arXiv:2606.12476.
RAGTruth dataset: https://github.com/ParticleMedia/RAGTruth
Lorden, G. (1971). Procedures for reacting to a change in distribution. Annals of Mathematical Statistics.
Page, E. S. (1954). Continuous inspection schemes. Biometrika.