Large language models are commonly evaluated by generating a small number of stochastic responses for each prompt in a benchmark. Because inference budgets are limited, this shallow evaluation may fail to observe low-probability but operationally important failures. A prompt that produces no failures in a small sample may therefore appear reliable despite having a nonzero latent probability of failure under repeated inference. We formulate LLM reliability evaluation as a budget-constrained discovery problem in which each prompt is associated with an unknown per-generation failure probability. We propose a budgeted discovery framework that first performs shallow evaluation across the prompt set and then uses trial-level failure outcomes together with prompt-derived representations to learn a feature-based ranking of failure propensity. The resulting scores prioritize prompts with zero observed shallow failures for deeper evaluation, concentrating the deep-evaluation budget where hidden failures are more likely to be discovered. We evaluate this approach on AIRBench and StrongREJECT across multiple model and system-prompt conditions. The central empirical test asks whether models fit without access to deep-evaluation outcomes can rank prompts with zero observed shallow failures according to their likelihood of producing failures under deeper evaluation. On AIRBench, the highest-ranked 10% of unresolved prompts achieves 2.54x hidden-failure lift for Qwen 2.5 7B and 1.87x for Gemma 3n E4B, recovering 25.4% and 18.7% of subsequently observed hidden failures, respectively, compared with 10% expected under random allocation. Semantic-neighborhood and feature-ablation analyses further show that this predictive signal can be recovered from multiple representations of prompt content and relationships.
Figures & tables
Figure 1: Two-stage budgeted discovery. Shallow stochastic outcomes and prompt-derived representations are used to rank prompts with no observed failures; the deep-evaluation budget is then concentrated on higher-ranked prompts. Deep-evaluation outcomes are withheld from model fitting.
Qwen 2.5 7B
Gemma 3n E4B
Unsafe-response rate, N=5
7.50%
0.63%
Unsafe-response rate, N=150
7.54%
0.63%
Positive prompts, N=5
771
84
Positive prompts, N=150
1,554
290
Unresolved prompts at N=5
4,923
5,610
Hidden failures
790
214
Table 1: AIRBench failure discovery under shallow ( N=5 ) and deep ( N=150 ) evaluation. Aggregate response-level failure rates remain nearly unchanged while deeper sampling reveals substantially more failure-capable prompts.
Figure 2: AIRBench hidden-failure rates by predicted-risk decile for Qwen 2.5 7B and Gemma 3n E4B. Deciles are computed within the population of prompts with zero observed failures at N=5 , using grouped out-of-fold embedding + text XGBoost scores. Hidden failures are identified through N=150 evaluation. Dashed lines show unresolved-population prevalence; error bars show 95% confidence intervals.
Figure 3: AIRBench hidden-failure recovery versus follow-up evaluation budget. Unresolved prompts are selected in descending order of grouped out-of-fold embedding + text XGBoost scores. The horizontal axis gives the fraction of unresolved prompts selected for deep evaluation; the vertical axis gives the fraction of hidden failures observed at N=150 recovered. The dashed diagonal shows expected recovery under random selection.
Ranking method
Qwen
Gemma
Random allocation
1.00 ×
1.00 ×
Prompt length (longest first)
0.82 ×
1.64 ×
Mean top-5 similarity to shallow positives
2.40 ×
1.68 ×
20-NN shallow-positive prevalence
2.31 ×
1.82 ×
Logistic: embedding + text
1.63 ×
1.54 ×
XGBoost: embedding + text
2.54 ×
1.87 ×
Table 2: Hidden-failure lift at a 10% deep-evaluation budget. Predictors use only N=5 information and are ranked within the unresolved population.
Condition
Endpoint
n
H
h/K
Rate
Lift
Recall
Basic safety prompt
Binary safety
309
2
1/31
3.2%
4.98 ×
50.0%
Basic safety prompt
StrongREJECT-positive
305
8
2/31
6.5%
2.46 ×
25.0%
No safety prompt
Binary safety
277
21
3/28
10.7%
1.41 ×
14.3%
No safety prompt
StrongREJECT-positive
279
16
2/28
7.1%
1.25 ×
12.5%
Table 3: Within-unresolved top-10% discovery on StrongREJECT.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Human 0
Human 0.5
Human 1
Judge 0
14
3
6
Judge 0.5
57
3
17
Judge 1
15
4
81
Appendix
Table 4: Automated versus human AIRBench scores in the primary validation sample ( n=200 ).
Condition
Agreement
Cohen’s κ
Basic safety prompt
98.8%
0.387
No system prompt
95.8%
0.634
Appendix
Table 5: Response-level agreement between the binary safety outcome and StrongREJECT judgment for Qwen.
Qwen
Gemma
Ranking / representation
h/K
Lift
h/K
Lift
Random allocation
–
1.00 ×
–
1.00 ×
Learned models
XGBoost: embedding + text
201/493
2.54 ×
40/561
1.87 ×
XGBoost: full representation
198/493
2.50 ×
44/561
2.06 ×
XGBoost: embedding only
193/493
2.44 ×
37/561
1.73 ×
Appendix
Table 6: Complete AIRBench top-10% ranking comparison within the unresolved population. All methods use the common model-specific evaluation populations defined above; comparisons among methods are descriptive.
Condition
Endpoint
N=5 responses
N=5 prompts
N=25 responses
N=25 prompts
Basic safety
Binary safety
10/1,565
4/313
46/7,825
6/313
Basic safety
StrongREJECT
16/1,565
8/313
102/7,825
16/313
No safety prompt
Binary safety
93/1,565
36/313
485/7,825
57/313
No safety prompt
StrongREJECT
93/1,565
34/313
466/7,825
50/313
Appendix
Table 7: Repeated evaluation on StrongREJECT. Response counts report positive individual generations; prompt counts report prompts with at least one positive response by the indicated depth.
Condition
Endpoint
n
H
K
h
Selected
Lift
Recall
Basic safety
Binary safety
309
2
31
1
3.23%
4.98 ×
50.0%
Basic safety
StrongREJECT
305
8
31
2
6.45%
2.46 ×
25.0%
No safety prompt
Binary safety
277
21
28
3
10.71%
1.41 ×
14.3%
No safety prompt
StrongREJECT
279
16
28
2
7.14%
1.25 ×
12.5%
Appendix
Table 8: Within-unresolved top-10% targeted discovery on StrongREJECT. H is the number of hidden failures in the unresolved population and h the number discovered among the selected K prompts.
Traditional benchmarks for large language models (LLMs), such as HELM and AIR-BENCH, primarily assess safety risk through breadth-oriented evaluation across diverse tasks. However, real-world deployment often exposes a different class of risk: operational failures arising from repeated generations of the same prompt rather than broad task generalization. In high-stakes settings, response consistency and safety under repeated use are critical operational requirements. We introduce Accelerated Prompt Stress Testing (APST), a depth-oriented evaluation framework inspired by highly accelerated stress testing in reliability engineering. APST probes LLM behavior by repeatedly sampling identical prompts under controlled operational conditions, including temperature variation and prompt perturbation, to surface latent failure modes such as hallucinations, refusal inconsistency, and unsafe completions. Rather than treating failures as isolated events, APST characterizes them statistically as stochastic outcomes of repeated inference. We model observed safety failures using Bernoulli and binomial formulations to estimate per-inference failure probabilities, enabling quantitative comparison of operational risk across models and configurations. We apply APST to multiple instruction-tuned LLMs evaluated on AIR-BENCH 2024 derived safety and security prompts. While models exhibit similar performance under conventional single- or very-low-sample evaluation (N <= 3), repeated sampling reveals substantial variation in empirical failure probabilities across temperatures. These results demonstrate that shallow benchmark scores can obscure meaningful differences in reliability under sustained use.
While existing benchmarks demonstrate the near-perfect performance of large language models (LLMs) on various tasks, this apparent saturation often obscures the need for rigorous evaluation of their reliability. In real-world deployment, however, achieving extremely high reliability (e.g., "five-nines" (99.999%) vs. "three-nines" (99.9%)) is fundamentally critical, as this gap results in an order-of-magnitude increase in failures, which is catastrophic in reliability-critical applications. Still, estimating such a rare failure probability with tight confidence bounds requires prohibitively large LLM inference sizes, making standard Monte Carlo evaluation infeasible under limited compute budgets. In this paper, we observe that LLM failures exhibit strong systematic patterns: across broad parameterized input spaces, a small subset of inputs disproportionately accounts for the majority of failures. Leveraging this observation, we propose to learn a sampling distribution concentrated on failure-prone inputs via the cross-entropy method (CEM). We evaluate our framework on three LLMs, Qwen2.5-Math-7B-Instruct, gpt-oss-20b-low, and Gemini 2.5 Flash Lite, across parameterized GSM8K templates and achieve up to 156.22x reduction in required inferences compared to naive uniform sampling. Our estimates reveal that models with indistinguishable accuracy on standard benchmarks can differ substantially in estimated failure rates, underscoring that reliability is a distinct and measurable axis of model quality. Our simple yet practical framework enables the evaluation of extreme reliability in LLMs, a distinct and underexplored dimension of evaluation beyond existing benchmarks, for their growing use in reliability-sensitive applications.
Evaluations of LLM systems routinely average over small prompt sets and report models as a ranked table. We ask how much confidence such a table deserves, using LLM-based prompt-structure inference as the case study: eight open model variants across five families and 8B to 675B parameters, caching disabled, 293 raw intermediate representations persisted. The measured phenomenon is unstable to begin with. Identical calls do not reliably recover identical structure, with mean node-set Jaccard from 0.39 to 0.96 and 72% of prompt-model cells never node-set-perfect. Auditing the evaluation weakens its conclusions further, and this is our main contribution. Under a joint cluster bootstrap over prompts, only the bottom of the ranking is firm: the two least reproducible models hold rank in 99% and 86% of replicates, the middle four in 27% to 48%, and the top two in 68% each, so the table identifies the worst model reliably but does not reliably identify the best. Two equally defensible rules for merging repeated campaigns change four of eight rows and move the study-wide headline by 7 percentage points. Checking the inferred structure against ground-truth annotations shows reproducibility cannot be read as accuracy. And four of the eight endpoints were withdrawn within ten weeks of measurement, so the study as specified can no longer be run. Small-sample LLM evaluations can therefore look far more definitive than their evidence supports. We recommend reporting rank stability, per-cell provenance, executed sensitivity comparisons, raw per-run outputs, and a measurement date alongside any ranking.