acceptodds
Under review as a conference paper at ICLR 2027

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 tasks with binary paths per task under the hard budget , where each path costs at most responses or episodes. For fixed and , the optimal expected width on the worst pure cohort is when every task is observed and 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
uncertainty quantification, language model evaluation, benchmark evaluation, repeated evaluation, confidence intervals, adaptive sampling, finite-population inference, evaluation efficiency, learning theory

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_VnrsOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the problem of evaluation under a hard budget. In particular, the paper considers the scenario that the learner runs a model with LL seeds on MM tasks, in total M∗LM * L runs, to determine the main performance. However, the learner have only a limited budget of running evaluations, such that they can only run BB of the M∗LM * L total runs. The paper aims at determining the least budget required for an accurate enough estimation, on the assumption that, within the same task, running with different seeds generally yields similar results. The paper shows that, under proposed strategy, the expected width is roughly Θ(1/M(t+1))\Theta(1/\sqrt{M(t+1)}) if at least one run in every task is finished and Θ(1/M(t+M))\Theta(1/\sqrt{M(t+\sqrt{M})}) when omission is allowed. The method is also verified empirically.

Critical strengths
  1. This paper focuses on repeated evaluation with fixed budget, which might be of broad interest as running such experiment is becoming costly given the larger models
  2. The paper proposes a repeat evaluation strategy that leverages the structure that the result within the same task tends to agree, therefore largely reduces the samples required.
Critical weaknesses

I found the paper very difficult to follow. Key terminology and notation are frequently introduced before they are defined, and the presentation does not clearly separate the motivating application, the mathematical setup, and the theoretical objectives. My specific concerns are as follows:

  1. Abstract: The variable tt is not defined, and the term “pure cohort” appears without explanation. Both are essential to understanding the main results and should be introduced explicitly.
  2. Introduction, second paragraph: The phrase “clears a qualification threshold” would be clearer as “exceeds a qualification threshold.” The terms “lower endpoint” and “upper endpoint” appear before the authors explain that the evaluator produces a confidence interval for the score, rather than only a point estimate. Similarly, “fixed cohort” is used without a clear definition.
  3. Table 1: The table relies heavily on technical jargon, making the comparisons difficult to interpret. I would expect such a table to compare assumptions and results explicitly, for example, whether the present work requires stronger, weaker, or incomparable assumptions, and what guarantees it obtains. Instead, the second and third columns provide compressed descriptions of the settings and inferential objects considered in each work. These descriptions are too brief to be self-contained and do not make the substantive differences clear.
  4. Problem formulation in Section 3: The setup would benefit from a more precise mathematical description of the underlying objects, observation model, and evaluator’s output. In particular:
    • Lines 126–128: The term “path” is introduced and described as containing at most KK responses or episodes, but its mathematical representation is unclear. The authors should specify what constitutes a path, what information each observation reveals, and how the terminal binary label is determined.
    • Line 128: “Decisive event” is not explicitly defined.
    • Line 136: The meaning of advancing a path “from observed depth aa to bb” should be defined. The associated cost should also be introduced formally, including what one unit measures and how the stated cost follows from the observation process.
    • Line 143: I(D)I(D) appears without an explicit definition of either II and DD.
  5. Opening of Section 4: The section begins directly with Theorem 1, without first clearly specifying the class of sampling policies and estimators covered by the theorem or explaining why this lower bound is relevant to the paper’s main objective. A short paragraph stating the statistical problem and motivating the result would improve readability.
    • In addition, “MSE” should be expanded to “mean squared error” at its first occurrence.

Given the current status, I believe that the manuscripts requires a substantiative revision before get published

Questions for authors

See weakness.

2 comments
AuthorsOpenReview ↗

Author Response: Definitions and Presentation Revisions

Thank you for the detailed comments. We revised the abstract, introduction, related-work comparison, problem setup, and theory section so that the evaluation setting is defined before the main results.

  1. tt and “pure cohort.” The abstract now defines MM tasks, LL planned binary outcomes per task, and a maximum cost of KK responses or episodes per run. The budget (M+t)K(M+t)K provides tt full-run equivalents beyond one run per task. A pure cohort is defined as one in which the planned outcomes agree within each task. The abstract also states that the target is a confidence interval for the mean of all MLML prespecified outcomes.
  2. Threshold, interval endpoints, and fixed cohort. We replaced “clears a qualification threshold” with “exceeds a threshold.” The introduction now uses a concrete example with 880 tasks and five planned runs per task. These 4,400 prespecified task-run pairs form the fixed cohort. With a budget for 1,100 observations, the evaluator estimates the fixed-cohort mean and reports a confidence interval. A lower endpoint above the threshold supports advancing the model, an upper endpoint below it supports holding the model back, and an interval crossing it indicates that more evidence is needed. We also distinguish this fixed-cohort target from generalization to future tasks or runs.
  3. Related-work comparison. We revised Table 1 and the surrounding discussion to compare the inferential object or guarantee established by each related work with the additional object studied here. The text now distinguishes expected from pathwise hard budgets, population from fixed-cohort inference, terminal-outcome sampling from partially observed paths, and validity guarantees from matching confidence-width rates. Because some works use different estimands or budget guarantees, we state which aspects are comparable rather than imposing a single stronger/weaker ordering.
  4. Observation model. Section 3 now defines the objects, observations, costs, and output explicitly. The fixed cohort contains MM tasks and LL planned paths per task, so N=MLN=ML. For path rr of task ii, Tir∈{1,…,K,K+1}T_{ir}\in\{1,\ldots,K,K+1\} is the first decisive-event index, where K+1K+1 means no decisive event, and Yir=1{Tir>K}Y_{ir}=\mathbf 1\{T_{ir}>K\} is the terminal label. The text explains both first-success and first-failure interpretations. Advancing an unresolved path from depth aa to bb costs min⁡(Tir−a,b−a)\min(T_{ir}-a,b-a) additional units; one unit is one model response or completed agent episode, and observed prefixes are retained. We use DD for the data revealed by the policy and RR for its internal randomization. The evaluator returns I(D)I(D), with coverage
Pr⁡R{θC∈I(D)∣C}≥1−α\Pr_R\{\theta_{\mathcal C}\in I(D)\mid\mathcal C\}\ge1-\alpha

for every fixed cohort C\mathcal C. 5. Motivation and organization of the theory. Section 4 is now titled “How replication controls uncertainty” and begins with a roadmap. It explains that incomplete paths cannot always replace completed outcomes, one run per task cannot reveal whether unobserved repetitions agree, and replication supplies this missing information. It then compares preserving coverage of every task with omitting some tasks to fund more replication. Before Theorem 1, we explain why late decisive events form the relevant worst case. Before the one-run-per-task theorem, we explain how a point estimate can be exact while its uncertainty remains poorly certified. The task-covering and omission results are similarly introduced through the allocation decisions they answer, and each main theorem is followed by a plain-language interpretation. The relevant estimands, policy classes, and budget guarantees are defined before use. “MSE” is expanded as “mean-squared error (MSE)” at first occurrence. The empirical section is now organized around three questions: whether Joint improves precision at the same budget, why it improves, and where the gains weaken. We thank the reviewer for these suggestions; the revision incorporates the requested definitions and structural clarifications.

I thank the authors for the efforts of fixing the issues and adapting my suggestions. Since the new version incorporates substantial revision, it does take some time for me to re-evaluate the manuscripts. I will provide additional feedback and / or adjust my rating accordingly if appropriate.

Reviewer_C6j4OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper talks about repeated evaluation on a fixed set of tasks and planned runs under hard pathwise budget. The main question is simple: how much replication is needed to produce an honest confidence interval, even when one sample per task already gives a good point estimate?

The paper proves two matching rates. When every task must be observed, the optimal worst-pure-cohort width is

Θ ⁣([M(t+1)]−1/2).\Theta\!\left([M(t+1)]^{-1/2}\right).

When tasks may be omitted, it becomes

Θ ⁣([M(t+M)]−1/2).\Theta\!\left([M(t+\sqrt M)]^{-1/2}\right).

The lower bounds cover adaptive policies. Fixed randomized designs attain the rates. The paper also proposes a Joint interval that uses both the sample mean and observed within-task disagreement.

Critical strengths
  1. The lower bounds cover broad adaptive hard-budget policies. Simple fixed designs achieve the same rates. This makes the task-coverage and task-omission laws meaningful.

  2. On LiveCodeBench, Joint and exact uniform sampling both use 1,100 outputs. Joint is narrower in 15 of 16 panels. The median interval width is reduced by 30.6%, and the median MSE is reduced by 87.0%. A same-observation comparison also shows that disagreement information, not only the sampling pattern, produces the gain.

Critical weaknesses

1.The strongest experiment uses K=1K=1, so it tests task allocation and inference rather than early path termination. The omission method also has weak finite constants on LiveCodeBench. The paper reports both points clearly, and neithermake main result.

2.On the agent banks, Joint beats fixed uniform in only 6/144 cells (Appendix N), Audit in 0/144 (Appendix L), and Pair in 1/24 (Appendix J); several refinements (Joint, Pair, the dominance region) were developed after outcomes were known, and Proposition 5 is evaluated with full-cohort descriptors, so it is not a prospective selector

Questions for authors

Is there a K>1K>1 response or agent setting where a theorem-backed honest interval beats exact fixed uniform sampling at the same hard budget?

2 comments
AuthorsOpenReview ↗

Author Response: New K>1 Equal-Budget Evidence

Thank you for identifying the K>1K>1 comparison as the most important missing experiment. We have added a complete equal-hard-budget replay on a K=1000K=1000 response bank and revised the paper to distinguish the positive settings from the overall result.

  • Direct answer Yes, we find specific K>1K>1 settings in which the theorem-backed Joint interval is narrower than exact fixed uniform sampling at the same reserved hard budget, although the advantage is concentrated in a small number of conditions. The replay uses all 22 available model-benchmark panels, two nonoverlapping response halves, both first-success and first-failure events, and six replication budgets, producing 528 comparison cells. Both methods select the same number of paths and reserve B=(M+t)KB=(M+t)K, with K=1000K=1000. No panels, events, budgets, or unfavorable results were excluded. Joint is narrower in 27/528 cells. Twenty wins occur for first-success evaluation on the two MiniF2F-MATH panels, across both halves and every positive replication budget; seven occur on CodeContests with Llama-3-70B-Instruct. Thus, these are concrete positive K>1K>1 settings. However, exact fixed uniform is narrower in the other 501 cells, and the median Joint/uniform width ratio is 1.509. The pooled mean width difference favors uniform in every budget-by-event stratum. Joint has lower point-estimation MSE in 300/528 cells, but generally wider confidence intervals. We now report both findings explicitly.

  • Evidence status Because these response banks had previously been inspected, we classify this as a complete post-hoc comparison rather than independent confirmatory evidence. Before the new replay, we froze the protocol, inputs, budgets, metrics, and success criteria, and retained every eligible condition. The MiniF2F-MATH pattern is therefore a hypothesis for independent validation, not a prospectively confirmed general advantage. Our inventory found no documented untouched K>1K>1 response or agent bank for such confirmation.

  • Agent results and finite-budget boundaries We retain the complete K=2K=2 agent results: Joint is narrower than exact fixed uniform in 6/144 cells, Audit in 0/144, and full-audit Pair in 1/24. Together with the K=1000K=1000 replay, these results show that theorem-backed honesty extends to longer paths, but favorable asymptotic rates need not yield favorable finite-budget constants. The main text now presents the K=1K=1 LiveCodeBench result as evidence about task allocation and inference, while treating the K>1K>1 results as operating boundaries that depend on event structure and cohort.

  • Post-hoc refinements and Proposition 5 The revision distinguishes prospectively locked evidence, complete post-hoc comparisons, and exploratory mechanism analyses. Proposition 5 is now described as a retrospective oracle diagnostic: because it uses full-cohort prevalence and disagreement, it is not a prospective selector without pilot data or a separate selection procedure. We use it only to explain when observed gains are consistent with the theory. The tested omission-enabled procedure also remains wider than exact fixed uniform in all 16 LiveCodeBench panels at the evaluated budgets. We retain the omission theorem as a sharp asymptotic result without presenting the current finite-sample omission construction as the preferred method at this scale. The revision adds the complete K=1000K=1000 replay, all 528 cell-level comparisons, a panel-level width-ratio figure, a consolidated K=1K=1/K=2K=2/K=1000K=1000 evidence table, and an explicit distinction between interval-width and point-estimation gains. We thank the reviewer for prompting this comparison.

Thats address most of my concerns ! Thanks for the reply !

Reviewer_gE5gOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Note: It seems to me that this paper is much more AI-generated compared to what the AI statement suggests. There's a lot of unexplained jargon even from the abstract / introduction. The problem that the paper addresses isn't clear at all. I got through the introduction and then realized that I do not understand anything because it sounds so AI-generated. Given this, I have decided to not create a human review, but I will just paste below what Codex said about this paper. If the authors wish to contest that the paper is AI-generated, I would like to see some clear evidence.

This paper studies how to allocate a fixed evaluation budget between observing different benchmark tasks and repeating evaluations within tasks, with the goal of constructing narrow, statistically valid confidence intervals for the average outcome over a prespecified task–run grid. Its central observation is that accurate point estimation does not necessarily permit narrow uncertainty intervals: when all runs within each task agree, evaluating every task once recovers the grid average exactly, but additional repetitions are needed to establish that agreement. The authors derive matching lower and upper bounds on achievable expected interval width for these internally consistent cohorts, while requiring coverage for every possible outcome grid, and distinguish settings where every task must be observed from those permitting task omission. They construct randomized replication designs and intervals that jointly use observed means and within-task disagreements. In an equal-budget LiveCodeBench replay, their Joint procedure produces narrower intervals in 15 of 16 model panels, with a median width reduction of 30.6%. The guarantees concern the fixed benchmark grid rather than generalization to future tasks or runs.

Critical strengths
  1. It identifies a consequential distinction between estimation accuracy and uncertainty certification. Even when one observation per task gives an exact benchmark estimate, the evaluator may lack evidence that the unobserved repetitions agree. This makes replication valuable for a reason that point-estimation error alone misses and provides a clear motivation for studying confidence-interval width.

  2. The theoretical results characterize fundamental limits and provide procedures that attain them. The paper derives matching lower and upper bounds for both task-covering and omission-permitting designs. The lower bounds include adaptive policies, while simple randomized replication designs attain the rates. The scope is precise: optimal expected width on internally consistent cohorts, subject to coverage over all fixed cohorts and a budget respected on every realization.

  3. The main empirical comparison uses a meaningful baseline under genuinely matched budgets. The LiveCodeBench replay compares Joint with exact pooled-uniform inference using the same number of evaluated outputs. At 1,100 outputs, Joint yields narrower intervals in 15 of 16 model panels, with a median width reduction of 30.6%. The paper also reports unfavorable regimes, helping distinguish where its theoretical advantages translate into practical gains.

Critical weaknesses
  1. The sharp optimality results concern a restrictive class of evaluation outcomes. The main rates describe “pure” cohorts: every repetition of a given task produces the same binary outcome. In practice, repeated LLM evaluations often disagree, and this disagreement is precisely why we repeat evaluations. Crucially, the intervals remain valid outside pure cohorts; what is missing is a comparable characterization of their efficiency there. The simulations explore departures from purity, but do not establish how the optimal replication strategy or achievable interval width changes with disagreement. This limits how directly Theorems 3–4 answer the practical allocation question.

  2. The headline benefit of omitting tasks does not translate into a demonstrated benefit at the tested budgets. One major theoretical contribution is that permitting task omission improves the optimal asymptotic rate. Yet the proposed omission procedure produces wider intervals than exact uniform sampling in all 16 LiveCodeBench panels at its four active budgets (§6.3). This does not contradict the theorem, which concerns rates up to constants, but it leaves an important practical question unanswered: when does the theoretical advantage become large enough to justify leaving benchmark tasks unevaluated? The strongest empirical results instead come from the task-covering Joint procedure.

  3. The paper does not provide a practical way to determine beforehand when its design will outperform uniform sampling. Proposition 5 characterizes a sufficient region for improvement using the full cohort’s outcome prevalence and within-task disagreement. Those quantities are generally unavailable without collecting the outcomes that the procedure is intended to save. The reported agreement between this condition and empirical wins is therefore retrospective. Appendix O explicitly acknowledges that it does not supply a selection rule based on the budgeted observations. A practitioner still needs a justified way to choose between uniform sampling and replication—potentially using a pilot sample—while accounting for its cost and preserving coverage.

Questions for authors

What was the extent of the use of AI models in producing this work and the writeup? Please be as specific as possible.,

Could you please provide some clear evidence of true human contributions in writing the paper? For example, can you articulate here clearly what the main problem is and what the main contributions are? Please be as clear and concrete as possible. I would be very happy to dig deep in the paper and actually review it as a human (even maybe increase my score!) if I get convinced that the human contribution in this work is significant.

5 comments
AuthorsOpenReview ↗

Author Response: Clarified Motivation and Contributions

Thank you for raising this concern. We agree that the previous version introduced too much terminology before establishing the underlying evaluation problem. This made the paper difficult to follow and obscured the scientific contribution and practical meaning of the results. We have substantially revised the abstract, introduction, problem setup, and main theoretical and empirical sections to provide the missing context and explain the results in a more direct sequence.

  • Main problem The paper studies a concrete evaluation-design problem. Suppose an evaluator has a fixed collection of benchmark tasks and several planned runs for each task, but the available budget is insufficient to execute every planned run. The evaluator wants an honest confidence interval for the average outcome over this prespecified task-run grid. The key distinction is between estimating the average and certifying its uncertainty. If all planned runs for each task agree, observing one run per task can already recover the correct average. However, those observations alone do not establish that the unobserved runs would agree. Replication provides information about this within-task stability. The central question is therefore: Under a hard evaluation budget, how much replication is required to obtain a narrow, statistically valid confidence interval, and how should that replication be allocated across tasks?

  • Main contributions The paper makes three central contributions.

  1. Sharp certification laws. We establish matching minimax rates for task-covering and task-omitting evaluation designs. The lower bounds cover adaptive hard-budget policies, while fixed randomized designs attain the same rates.
  2. A constructive finite-budget interval. We introduce the Joint interval, which combines the sampled mean with observed within-task disagreement. This construction translates the theoretical role of replication into an executable confidence interval with finite-sample coverage.
  3. Matched-budget empirical evidence. In the LiveCodeBench replay, Joint and exact pooled uniform sampling both use 1,100 outputs. Joint produces narrower confidence intervals in 15 of 16 model panels, with a median width reduction of 30.6%. The task-covering sampling design also reduces median point-estimation mean-squared error by 87.0%. The revised paper now distinguishes these effects explicitly: the sampling design drives the point-estimation improvement, while the Joint certificate drives the interval-width improvement.
  • Presentation revisions To address the reviewer's concern directly, the revised paper now:
  • begins with the practical evaluation decision before introducing notation;
  • defines the fixed cohort, observations, costs, target mean, and confidence interval in plain language;
  • uses a concrete running example to explain why an accurate point estimate may still have poorly certified uncertainty;
  • explains every non-standard term when it first appears;
  • places intuition before the main theorems and practical interpretations after them;
  • reorganizes the empirical section around three questions: whether replication helps, why it helps, and where its advantages weaken;
  • distinguishes theorem-backed results, complete post-hoc comparisons, and exploratory analyses; and
  • preserves unfavorable empirical regimes as boundary conditions while keeping the paper centered on its supported contribution. We appreciate the reviewer identifying this presentation problem. The revision preserves the underlying theoretical and empirical results while making the motivation, reasoning, and evidence substantially easier to follow and evaluate.

I would like to thank the authors of their response. The scope of the revision is too broad for it to fit within the scope of a conference revision. I encourage the authors to keep improving their work, and submit to the next cycle.

Even your response, however, doesn't address my main concern in my review: there were issues with the statement of AI use in the paper and what I actually think the AI use was.

In a revised submission, i urge the authors to not only write their paper more humanly but also to be more upfront about the use of AI in their statement.

We disclosed the scope of our AI use in the submitted manuscript on page 10 and stand by the accuracy of that disclosure.

The reviewer writes, “It seems to me that this paper is much more AI-generated compared to what the AI statement suggests,” and adds, “I got through the introduction and then realized that I do not understand anything because it sounds so AI-generated.” Readers bring different technical backgrounds to a paper, and we take seriously the reviewer’s difficulty following the introduction. We ask the reviewer to identify the terms, assumptions, or passages that need clarification. If the reviewer believes our disclosure is incomplete, we ask the reviewer to identify the specific use allegedly omitted, point to the passages at issue, and explain what evidence supports the claim. A rigorous scientific review must identify specific shortcomings in the manuscript and support any allegation of undisclosed AI use with verifiable evidence. A claim based solely on subjective impressions of writing style should carry no weight in the review decision.

The reviewer also stated that they chose to paste Codex’s assessment in place of writing their own review. We ask the reviewer to read the full manuscript and provide an independent scientific assessment that explains each substantive concern with reference to the relevant text, equations, or experimental claims.

A rigorous peer-review process requires reviewers to read submissions in full, exercise independent judgment, and ground substantive criticisms in specific, verifiable evidence. A review that lacks both evidence and independent judgment offers authors no actionable basis for revision and should carry no weight in the decision. Holding reviews to this standard serves the broader research community. It fosters an academic environment where disagreements can be examined openly, authors can improve their work through concrete feedback, and researchers can trust that their contributions will be assessed on their scientific merits.

Comments on the paper

1 comment

Dear Reviewers,

The authors have replied to your initial comments. Please have a look and engage in the discussion.

Thanks!

Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.