Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation
Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu, Yilan Wei, Yankai Zeng, Bojun Lin
cs.AI · cs.IT
Quick verdict
Proves sharp replication limits for hard-budget LLM evaluation with matching designs and equal-budget evidence; practical gains are regime-dependent.
Summary
This paper develops a design-based theory of how much replication is needed to certify narrow confidence intervals when evaluating a model on a fixed grid of M tasks with L planned binary paths per task, under a hard budget of (M+t)K responses. Its central results are matching Θ rates: with one completed path per task, the optimal worst-pure-cohort expected interval width is of order [M(t+1)]^(-1/2) (Theorem 3); allowing task omission improves the achievable order to [M(t+√M)]^(-1/2) (Theorem 4). Lower bounds cover adaptive budget-spending policies, and fixed random-subset designs attain both rates through disagreement certificates; a joint mean/disagreement interval (Audit, Pair, Joint) makes the theory usable at finite budgets. In an equal-budget replay of LiveCodeBench (16 models, 880 tasks, five outputs per task), Joint and exact pooled uniform inference each consume 1100 outputs; Joint is narrower in 15 of 16 model panels, with median width reduction 30.6% and median MSE reduction 87.0%. Supporting replays of public response and agent banks (2.49 million executions, no budget violations) confirm feasibility. Limitations: the guarantee covers only the realized task grid, not future tasks; synthetic and agent grids show the new intervals lose to fixed uniform sampling in most mixed-cohort conditions, so practical gains are regime-dependent; several interval refinements and one baseline were added post-review.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For fixed L≥3 and 0<α≤1/12, the optimal worst-pure-cohort expected honest-interval width under a pathwise (M+t)K budget is Θ([M(t+1)]^(-1/2)) when every task must be observed, with the lower bound covering all adaptive task-covering policies (Theorem 3).
- Allowing task omission improves the achievable rate to Θ([M(t+√M)]^(-1/2)) uniformly over all hard-budget policies without external cohort information, changing the order at t=0 from M^(-1/2) to M^(-3/4) (Theorem 4).
- Fixed random-subset designs attain both rates through disagreement certificates, and a joint mean/disagreement interval (Audit/Pair/Joint) delivers valid finite-budget inference under the same designs.
- At equal 1100-output budgets on a LiveCodeBench replay (16 models, 880 tasks, five outputs per task), Joint yields narrower mean intervals in 15/16 panels (median width ratio 0.694) and lower MSE in all 144 panel-budget cells (median ratio 0.130 versus exact pooled uniform).
Strengths
Matching sharp laws over adaptive policies
Theorems 3 and 4 give two-sided constants c·√(M(t+1)) and c'·√(M(t+√M)) bracketing the optimal worst-pure-cohort width, with lower bounds (Appendices K, P) proven uniformly over pathwise-(M+t)K adaptive policies — covering task interleaving, stopping, and savings recycling, not just fixed designs. This completeness is rare in the evaluation-methodology literature.
Constructive attainment, not just existence
The fixed random-subset audit with the U(d,δ;t) Chernoff inversion (Eq. 6, App. K.1) attains the upper rate; the Pair (Thm 6, App. A.3) and Joint (App. N, Prop 9, Maclaurin-based joint MGF) refinements improve finite constants while preserving the same sampling design and budget.
Unusually honest empirical reporting
Equal-budget comparison design
Reproducibility engineering
Weaknesses
Regime dependence underplayed in the headline
Fixed-cohort estimand limits decision utility
MSE gain is design-driven, not certificate-driven
Restrictive technical scope
Post-review additions blur the confirmatory line
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies a concrete allocation problem: evaluating a model on a prespecified grid of M tasks with L planned binary repetition paths per task, under a pathwise hard budget of (M+t)K responses, where a path costs at most K. The estimand is deliberately finite-population — the grid mean conditional on realized outcomes (Eq. 1) — with design-based coverage PR{θC ∈ I | C} ≥ 1-α for every fixed cohort. The claims are (i) two sharp minimax laws: width Θ([M(t+1)]^(-1/2)) with mandatory task coverage (Thm 3) and Θ([M(t+√M)]^(-1/2)) with omission allowed (Thm 4), for L≥3, α≤1/12; (ii) fixed random-subset designs attaining both rates via disagreement certificates; (iii) equal-budget LiveCodeBench evidence that the Joint interval beats exact pooled uniform (15/16 panels, median width -30.6%, median MSE -87.0%); and (iv) a finite-cohort dominance region (Prop 5) explaining when task coverage helps.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does 'hard budget' mean in this paper?
A budget of (M+t)K evaluation responses or agent episodes that must hold for every possible outcome pattern and every randomization of the evaluation policy — not merely on average. This is stricter than the expected-budget guarantees common in adaptive evaluation work, and it is what makes the certification (confidence interval) problem hard.
Why is replication needed if one sample per task already estimates the benchmark score exactly?
Estimation and certification differ. On cohorts where all repeated runs within each task agree, one observation per task recovers the grid mean exactly; but a 95% confidence interval must also cover the possibility that unobserved repetitions disagree. Theorem 2 shows any honest interval then needs expected width of order 1/√M even on those internally consistent cohorts, which is why a second draw on t tasks yields width order 1/√(Mt).
What are the headline LiveCodeBench numbers?
On a replay of LiveCodeBench with 16 models, 880 tasks, five outputs per task and K=1, the proposed Joint design and exact pooled uniform sampling each consume 1100 outputs (M+t = 880+220). Joint produces narrower mean confidence intervals in 15 of 16 model panels, with median interval width 30.6% smaller and median MSE 87.0% smaller than pooled uniform, without buying more outputs.
Does the confidence interval say how the model will perform on new tasks?
No. The guarantee is design-based and covers the mean of the specific, already-realized task grid under the evaluator's sampling randomness. Generalizing to a population of future tasks requires an additional Hoeffding term (Appendix D), and the paper deliberately keeps the two guarantees separate.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The arXiv HTML extraction omitted several appendix sections (C, H, I, M, and parts of P/Q) and all figures; judgments rest on the visible theorems, proofs sketches, and tables (2-22).
- Proof correctness was assessed from appendix sketches; coupling constants (e.g., the 5/6 likelihood floor, Paley-Zygmund bounds) were not independently re-derived.
- All empirical evidence is replay of pre-existing public model outputs; no newly generated evaluations, so external validity across future benchmarks is untested by construction.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.