Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation
Abstract
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 Θα,L([M(t+1)]−1/2) when every task is observed and Θα,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.
Related
- Adaptive Experimentation Can Hide Model Error:Detection Limits and Falsification Budget
- Temporal Degeneracy Limits Message Passing Decoding of QLDPC Codes Under Repeated Noisy Syndrome Measurements
- When Timing Uncertainty Limits Spectral Accuracy: Bias, Variance, and Frequency-Dependent Attenuation
- The ISAC Tradeoff Cliff: Fundamental Limits under Waveform Uncertainty and Finite Blocklength
- ProbabilityBench: Model Evaluation and Calibration with Exact Ground-Truth Uncertainty
BibTeX
@misc{cheng2026sharp,
title = {{Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation}},
author = {Yezhou Cheng and Runjia Du and Zeming Liu and Qibai Chen and Hang Lyu and Yilan Wei and Yankai Zeng and Bojun Lin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29140},
eprint = {2609.29140},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29140},
}
RIS
TY - UNPB
TI - Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation
AU - Yezhou Cheng
AU - Runjia Du
AU - Zeming Liu
AU - Qibai Chen
AU - Hang Lyu
AU - Yilan Wei
AU - Yankai Zeng
AU - Bojun Lin
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29140
UR - https://arxiv.org/abs/2609.29140
AB - 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 Θ_α,L([M(t+1)]^−1/2) when every task is observed and Θ_α,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.
ER -