# Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

arXiv: https://arxiv.org/abs/2609.29140 · HTML: https://mlsanity.com/paper/2609.29140/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 25 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 14 of 14)

- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Universal Inference](https://mlsanity.com/paper/1912.11436/) (2019)
- [Stratified Prediction-Powered Inference for Hybrid Language Model Evaluation](https://mlsanity.com/paper/2406.04291/) (2024)
- [Confidence sequences for sampling without replacement](https://mlsanity.com/paper/2006.04347/) (2020)
- [Efficient Evaluation of LLM Performance with Statistical Guarantees](https://mlsanity.com/paper/2601.20251/) (2026)
- [On Randomness in Agentic Evals](https://mlsanity.com/paper/2602.07150/) (2026)
- [Efficient Prediction of Pass@k Scaling in Large Language Models](https://mlsanity.com/paper/2510.05197/) (2025)
- [How Reliable is Language Model Micro-Benchmarking?](https://mlsanity.com/paper/2510.08730/) (2025)
- [How Many Iterations to Jailbreak? Dynamic Budget Allocation for Multi-Turn LLM Evaluation](https://mlsanity.com/paper/2605.06605/) (2026)
- [How Many Tasks Are Enough for Agent Benchmark Decisions? A Replay Analysis of Public LLM Agent Benchmarks](https://mlsanity.com/paper/2607.12338/) (2026)
- [Sequential stratified inference for the mean](https://mlsanity.com/paper/2409.06680/) (2024)
- [Knowing When to Stop: Bayesian Optimal Stopping for LLM Evaluations](https://mlsanity.com/paper/2608.14425/) (2026)

## Abstract (arXiv)

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of M tasks with L binary paths per task under the hard budget (M+t)K, where each path costs at most K responses or episodes. For fixed L ≥ 3 and 0 < α ≤ 1/12, the optimal expected width on the worst pure cohort is Thetaα,L([M(t+1)]-1/2) when every task is observed and Thetaα,L([M(t+√M)]-1/2) when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.