Optimal replicate budgeting improves repeated task evaluations
Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation
Artificial IntelligenceInformation Theory
Summary
When testing things multiple times to get accurate scores, figuring out how many times to repeat each test is tricky. The paper shows the best way to divide a limited number of test attempts across many tasks to get precise uncertainty estimates. The authors prove mathematical limits on how well this can be done and propose practical designs to reach those limits efficiently. Their methods reduce errors and create narrower confidence intervals in real test scenarios with many models and tasks.
What this means in practice
- •For machine learning engineers: Improve model performance testing by optimally allocating limited evaluation runs across benchmark tasks for tighter uncertainty estimates.
- •For software quality assurance teams: Design efficient repeated testing schedules that cover all critical tasks while controlling testing budget and uncertainty in defect detection rates.
Authors
Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu, Yilan Wei, Yankai Zeng, Bojun Lin
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 \ge 3$ and $0 < α\le 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+\sqrt{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.