- Rating
- 2(−1)
- Confidence
- 1(−1)
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies what pass@k measures when attempts within an agent run share state. It distinguishes procedure success (succ@k), independent-attempt success (pass@k_iid), and pass@k computed from pooled attempts. It characterizes the pooled estimator under a conditionally i.i.d. latent-variable model, establishes a uniqueness result for succ@k under specified constraints, and studies the run-count threshold for unbiased estimation of pass@k_iid, minimax bias, confidence sequences, and sampling costs. Experiments across eight designs and four dependence mechanisms show that pooled pass@4 exceeds the run-level estimate of succ@4.
Critical strengths
-
The paper provides a rigorous characterization of what pass@k measures when attempts share state. By distinguishing procedure-level success, independent-attempt success, and pooled reporting, it clarifies how evaluation design can affect reported scores and lead to misleading interpretations.
-
The paper systematically examines unbiased estimability, statistical inference, and sampling costs under dependent attempts. The theoretical results, together with experiments across multiple dependence mechanisms, provide a coherent framework and practical guidance for evaluating multi-attempt agents.
Critical weaknesses
-
Prior work has already distinguished dependent- and independent-attempt success and emphasized the importance of independent complete runs. The proofs and constructions for several other results, including the run-count threshold and confidence sequences, rely on established statistical principles. Although the exact pooled-score characterization and uniqueness result are valuable, the extent of the conceptual novelty beyond these prior insights remains limited.
-
The ordering between pooled pass@k, succ@k, and pass@k_iid in Proposition 3.2 relies on the conditionally i.i.d. latent-variable model in Definition 3.1. This assumption does not generally hold for adaptive agents, where later attempts depend on earlier outputs or feedback, including the self-debugging and tree-search settings evaluated in the paper. Although the authors acknowledge this limitation, the exact pooled-score characterization does not directly extend to these settings, limiting the generality of this particular theoretical contribution.
Questions for authors
-
Although Tables 38–39 and 51 examine decision-level consequences through simulations, measured runs, and constructed examples, the impact on comparisons between distinct real systems remains unclear. Could the authors examine whether run-aware evaluation changes model rankings, the direction of performance differences, or statistical significance under matched evaluation settings? Reporting all comparable pairs examined, including those whose conclusions remain unchanged, would help establish the practical impact.
-
Theorem A.6 establishes a sharp minimax-bias bound over real-valued estimators, which need not lie in [0,1]. Does this bound remain attainable when estimators are constrained to [0,1]? If not, could the authors provide a simple example illustrating the difference and discuss its implications for practical probability reporting?
What Pooled pass@k Measures When Attempts Share State
Thank you for asking what our work adds. We make four main contributions.
1. What pooled pass@k measures. There are two target probabilities. Following Liu et al. (2025), succ@k is the chance of at least one success within k attempts in one run. Independent-attempt pass@k is the chance of at least one success in k fresh, independent attempts. Pooled pass@k is a score computed by combining attempts across runs of the same problem. We derive its exact expectation for a finite evaluation (Proposition A.21). Under the conditionally i.i.d. model, this expectation lies between the two targets (Proposition 3.2). Changing the number of runs can therefore change the expected score of an unchanged procedure. For adaptive agents, this ordering can fail. Scoring each run 1 if it succeeds within k attempts and 0 otherwise still estimates succ@k without bias (Proposition 3.4). Under Theorem 3.5's conditions, this is the unique scoring rule in [0,1] on one run of k attempts that agrees in expectation with classical pass@k under i.i.d. sampling.
2. How many runs are needed. Applying a classical statistical criterion, Theorem 4.1 shows that, under its assumptions, unbiased estimation of independent-attempt pass@k requires at least k independent runs, and k suffice. More attempts within a run cannot make up the difference. Below this threshold, Theorem A.6 characterizes the smallest achievable worst-case absolute bias.
3. How to report uncertainty. We adapt confidence sequences to both targets so that, under the stated assumptions, intervals remain valid when evaluators use the data to decide when to stop. We also show which part of the variance only fresh runs can reduce. This guides the choice between starting a run and adding an attempt.
4. What happens in practice. Across eight designs covering four forms of dependence, pooled pass@4 exceeded the observed run-success rate by 2.05 to 17.66 percentage points (the pooled excess). Run-level intervals also had better interval scores in all eight designs. On five additional open-weight models, four fresh, independent attempts had a higher estimated chance of success than four attempts sharing one prefix (a positive estimand gap).
Does scoring change the model ranking? For the Qwen2.5 pair in Table 24, 7B led 1.5B under both methods. Both used the same self-debugging procedure on the same 164 HumanEval problems, with 16 runs per model per problem. At k=4, the 7B lead was 22.29 percentage points under pooled scoring (95% CI 17.31 to 27.36) and 28.43 points under run-level scoring (95% CI 23.36 to 33.50). We computed both intervals from the submitted outcomes using 10,000 paired bootstrap resamples of problems. Both intervals exclude zero. Pooling preserved the ranking but narrowed the measured lead by 6.14 points.
Can a bounded estimator reach the bound in Theorem A.6? The lower bound still holds, but it need not be attainable. Take k=2 and one run in which all attempts succeed with probability q and all fail otherwise. The run reveals one binary outcome X, and the independent-attempt target is 2q−q2. The estimator X+1/8 attains the optimal worst-case absolute bias of 0.125, but outputs 9/8 on success. If every output must lie in [0,1], the optimal rule reports 3−22 on failure and 1 on success. Its worst-case absolute bias is 3−22≈0.1716. This quantifies the cost of requiring every reported estimate to be a valid probability.