In pre-deployment testing of AI systems such as AI agents, a developer can often deal with known failure modes (e.g., leaking API keys, deleting important databases, or installing a malicious package) by implementing fixes or making contingency plans for when the same issue might occur again. What is more challenging are the unknown unknowns: the unseen failure modes that haven't surfaced during testing. The decision to stop testing and deploy therefore faces an inherent tradeoff: continue testing to observe more behaviors, at the cost of time and resources, or stop testing and deploy, at the risk of failure modes remaining undiscovered. How then does the developer decide when they have tested enough? To answer this, we develop an algorithm that certifies when the probability of observing an unseen failure mode is sufficiently small. The algorithm constructs an anytime-valid upper confidence sequence on this quantity, so the developer can repeatedly test a system, inspect the bound, and decide to stop when it falls below a chosen threshold without invalidating the statistical guarantee. Our problem can be interpreted as a sequential variant of the missing-mass estimation problem which gave rise to the classic Good-Turing estimator (Good, 1953). On SWE-Chat, a dataset of real-world coding agent traces (Baumann et al., 2026), we implement our procedure and show that it achieves tighter upper bounds than a simple multiple-testing corrected Good-Turing baseline, and even dominates a fixed-horizon (non-multiple-testing-corrected) Good-Turing upper confidence bound, which is not anytime valid. Additionally, to better match realistic evaluation pipelines, we extend our method to handle sampling from a different task distribution and imperfect automated failure labeling.
Algorithm 1 Anytime-Valid Confidence Sequence for Controlling the Probability of Unseen Failure
Figure 1: Empirical performance of our anytime-valid upper bound. (a) Our anytime-valid upper bound (purple) is tighter than both the simultaneous Good-Turing UCB (teal) and pointwise Good-Turing UCB (gray, dashed) on SWE-Chat. Our bound achieves empirical simultaneous coverage of 0.973 through t=3000 . Both Good-Turing baselines achieve coverage of 1. Shaded bands show 2.5th–97.5th percentiles across trials. (b) Empirical simultaneous coverage under the distribution where every failure is unseen and Rtunseen=0.05 exactly for all t . Across 10,000 trials, coverage plateaus at 0.9587 , above the nominal level 1−α=0.95 ; shaded band shows ±2 standard errors.
Algorithm 3 Extension of Algorithm 1 using PAC labeling
Hypothesis Threshold
Round
c1=R1
c2=R2
⋯
ct−1=Rt−1
ct=Rt
1.H0:R1≥ci
Es:1(c1)
≥
Es:1(c2)
≥
⋯
≥
Es:1(ct−1)
≥
Es:1(ct)
2.H0:R2≥ci
Es:2(c1)
≥
Es:2(c2)
≥
⋯
≥
Es:2(ct−1)
≥
Es:2(ct)
⋮
⋮
⋮
⋱
⋮
⋮
t−1.H0:Rt−1≥ci
Es:t−1(c1)
≥
Es:t−1(c2)
≥
⋯
≥
Es:t−1(ct−1)
≥
Es:t−1(ct)
t.H0:Rt≥ci
Es:t(c1)
≥
Es:t(c2)
≥
⋯
≥
Es:t(ct−1)
≥
Es:t(ct)
Appendix
Figure 2: Rows show the null hypothesis changing over rounds as true missing mass Rtunseen evolves. Columns show hypothesis test thresholds.
Figure 3: Coverage and stopping times on SWE-Chat. (a) Empirical simultaneous coverage. At each time t , we report the fraction of trials for which the bound covers the true missing mass simultaneously over all rounds 1,…,t . Our anytime-valid UCB (purple) achieves empirical simultaneous coverage of 0.973 through t=3000 , above the nominal level 1−α=0.95 . Both the simultaneous (teal) and pointwise (dotted grey) Good–Turing UCBs achieve coverage of 1 throughout. (b) Stopping time as a function of the stopping threshold ε . We compare the stopping time of our procedure with the oracle stopping time, defined as the first round at which the true missing mass falls below ε . We show only thresholds for which the oracle stopping time is nontrivial ( >1 ) and our procedure stops within the evaluation horizon (t=3000) . Solid lines show mean stopping times and shaded bands show the 2.5th–97.5th percentiles across trials.
Figure 4: Evaluation under known distribution shift. We compare evaluation under the target distribution P (left) with length-biased sampling from Q (right), while maintaining guarantees with respect to P using the likelihood-ratio correction. Top: Anytime-valid upper bounds on the unseen-failure probability together with the true missing mass under each sampling process. Bottom-left: Empirical simultaneous coverage through time t . At t=3000 , coverage is 0.973 under P and 0.980 under Q , both above the nominal level 1−α=0.95 . Bottom-right: Difference in mean stopping time between sampling from Q and sampling from P , as a function of the stopping threshold ε . Sampling from Q leads to modestly later stopping on average. We show only thresholds for which both procedures stop within the evaluation horizon.
Figure 5: Imperfect failure labeling. We compare Algorithm 1 using perfect labels, Algorithm 2 using PPI, and Algorithm 3 using PAC labeling over 1,000 paired trials, sampling uniformly with replacement from 4,961 SWE-Chat sessions with α=0.05 . Left: Mean upper bounds on unseen failure probability; shading shows the pointwise 2.5th–97.5th percentiles across trials. PAC approach uses fixed ζ=0.05 and δ=0.025 . Center: Empirical simultaneous coverage through each sample count; the dotted line marks nominal 95% coverage. Right: Mean ground-truth labels collected through stopping, including random audits, as well as labels collected above the PAC threshold cutoff, with approximate 95% confidence intervals for the mean. Here PAC uses ζ=ε/2 and δ=0.025 . PPI uses a constant audit probability of 0.1 and no residual predictor; PAC uses an audit floor of 0.1 .
Figure 6: Our method remains valid under an online embedding-based failure novelty rule , where a failure is considered unseen when its failure-mode description is insufficiently similar to all previously observed failures under the online embedding-based matching rule. (a) Anytime-valid upper bound on the unseen-failure probability, together with the true unseen-failure probability defined by the same online novelty rule. Solid line is the mean, shaded bands show 2.5th-97.5th percentiles across trials. (b) Empirical simultaneous coverage through time t . Coverage remains above the nominal level 1−α=0.95 throughout the evaluation horizon.
Figure 7: Our method remains valid under set-valued failure observations, where a single session may contain multiple distinct failure modes. (a) Anytime-valid upper bound on the unseen-failure probability, together with the true unseen-failure probability under the set-valued novelty rule (a session is unseen if it contains at least one failure mode that has not been observed previously). Solid lines show the mean across trials, and shaded bands show the 2.5th–97.5th percentiles. (b) Empirical simultaneous coverage through time t . Coverage remains above the nominal level 1−α=0.95 throughout the evaluation horizon.
Figure 8: Robustness to an alternative LLM-based fixed taxonomy. We repeat the main statistical evaluation using a second fixed taxonomy constructed by an LLM-based grouping procedure rather than the clustering-based taxonomy used in the main results. (a) Anytime-valid upper bound on the unseen-failure probability, together with the true missing mass and the simultaneous and pointwise Good-Turing UCBs. Solid lines show the mean, and shaded bands show the 2.5th-97.5th percentiles across trials. (b) Empirical simultaneous coverage through time t . Our method remains above the nominal level 1−α=0.95 throughout the evaluation horizon; both Good–Turing bounds achieve coverage of 1 .
Figure 9: Sensitivity to the choice of betting parameter λ . We compare the finite-grid mixture used in the main results with fixed choices λ∈{0.1,0.25,0.5} . (a) Anytime-valid upper bounds on the unseen-failure probability together with the true missing mass. The grid mixture performs similarly to the fixed- λ alternatives across the evaluation horizon. (b) Empirical simultaneous coverage through time t . All choices remain above the nominal level 1−α=0.95 throughout the evaluation horizon.
Figure 10: Minimal benefit of restart-mixing on SWE-Chat. We compare the restart mixture (solid purple) with a non-restarted betting process (dotted green), using the same equally weighted grid of 100 lambda values and α=0.05 . Left : mean upper confidence bounds across 1,000 paired trials, with shaded bands showing the empirical 2.5th–97.5th percentiles; black denotes the true unseen-failure probability. Right : empirical simultaneous coverage, which is 0.973 with restarts and 0.971 without restarts through 3,000 draws, both above the nominal 0.95 level. Restarting yields modestly tighter bounds on this dataset.
A major bottleneck in characterizing the failure modes of generative AI systems is the cost and time of annotation and evaluation. Consequently, adaptive testing paradigms have gained popularity, where one opportunistically decides which cases and how many to annotate based on past results. While this framework is highly practical, its extreme flexibility makes it difficult to draw statistically rigorous conclusions, as it violates classical assumptions: the number of observations is typically limited (often 10 to 50 cases) and decisions regarding sampling and stopping are made in the midst of data collection rather than based a pre-specified rule. To characterize what statistical inferences can be drawn from highly adaptive audits, we introduce a hypothesis testing framework from two "dueling" perspectives: (i) the model's null that asserts there is no failure mode with performance below a target threshold versus (ii) the auditor's null that asserts they have a sampling strategy that will uncover a failure mode. Leveraging Safe Anytime-Valid Inference (SAVI), we formalize the auditor as conducting "testing by betting," which translates into simultaneous e-processes for testing the dueling null hypotheses. Furthermore, if the auditor is sufficiently powerful, we prove that these two hypotheses are asymptotically inverses of each other, in that passage of such an audit certifies the AI system as being globally robust. Empirically, we demonstrate that our proposed testing procedures maintain anytime-valid Type-I error control, outperform pre-specified testing methods, and can reach statistically rigorous conclusions sometimes with as few as 20 observations.
Siyu Zhou, Patrick Vossler, Venkatesh Sivaraman +2
University of California, San Francisco · Stanford University
Autonomous AI agents are deployed at unprecedented scale, yet no principled methodology exists for verifying that an agent has not regressed after changes to its prompts, tools, models, or orchestration logic. We present AgentAssay, the first token-efficient framework for regression testing non-deterministic AI agent workflows, achieving 78-100% cost reduction while maintaining rigorous statistical guarantees. Our contributions include: (1) stochastic three-valued verdicts (PASS/FAIL/INCONCLUSIVE) grounded in hypothesis testing; (2) five-dimensional agent coverage metrics; (3) agent-specific mutation testing operators; (4) metamorphic relations for agent workflows; (5) CI/CD deployment gates as statistical decision procedures; (6) behavioral fingerprinting that maps execution traces to compact vectors, enabling multivariate regression detection; (7) adaptive budget optimization calibrating trial counts to behavioral variance; and (8) trace-first offline analysis enabling zero-cost testing on production traces. Experiments across 5 models (GPT-5.2, Claude Sonnet 4.6, Mistral-Large-3, Llama-4-Maverick, Phi-4), 3 scenarios, and 7,605 trials demonstrate that behavioral fingerprinting achieves 86% detection power where binary testing has 0%, SPRT reduces trials by 78%, and the full pipeline achieves 100% cost savings through trace-first analysis. Implementation: 20,000+ lines of Python, 751 tests, 10 framework adapters.
AI systems can fail silently. The failure propagates through training loops, evaluation pipelines, and production monitoring stacks until downstream harm makes it visible. This paper introduces evaluation blindness: a measurement function M exhibits evaluation blindness with respect to failure class F when it produces readings indistinguishable from a healthy state while the system is actually failing, with no auxiliary signal flagging the gap. The problem surfaces at two lifecycle stages the literature has treated separately. At training time, reward models are gamed, importance-sampling corrections are silently miscalculated, and benchmark contamination inflates fine-tuning evaluations, all while loss curves look healthy and gradient updates proceed normally. At deployment time, monitoring fails to catch six classes of production failure, including an Operational category that is 100% silent by structural definition. We provide a formal detectability predicate unifying both stages. Four training-time case studies trace concrete breakdowns, including a real implementation bug in TRL PR #6594 where gradients are corrupted as loss decreases normally. A six-class taxonomy validated against 50 real-world incidents from court documents and regulatory filings finds that 53% of verifiable public failures were silent. A failure budget framework ties acceptable failure rates to use-case risk class. The implication is direct: measurement infrastructure is a correctness concern across the full AI lifecycle, not just at evaluation time. Data, code, and taxonomy schema are at https://github.com/priyanka25aug/llm-failure-taxonomy.