PaperlayerView exact revision on arXiv

Source-linked AI summary

What Fixed-Rollout pass@k Evaluations Can Identify

Pranav Singh, Prashant Singh

arXiv:2609.09245v1stat.MLcs.AIcs.LG

TL;DR

Fixed-n pooled count laws reveal only finitely many moments of the latent task-success distribution, leaving generic pass@k extrapolation beyond n partially identified. The paper proves this boundary, constructs observationally equivalent distributions with incompatible tails, and computes sharp bounds for public evaluation data. It concludes that extrapolated forecasts should be reported alongside their identified sets and model assumptions.

  • Problem

    Fixed-rollout evaluations need to determine what their complete success-count distribution identifies about pass@k beyond the observed rollout depth.

  • Method

    The paper analyzes the pooled/random-task conditional-Binomial model using truncated Hausdorff moment theory, exact count-law-preserving constructions, and principal representations for sharp bounds.

  • Results

    In four public-data configurations, counterfactual n = 16 evaluations leave k = 1000 failure ambiguous by factors from 1.5× to over 2,600×.

  • Takeaways & Limitations

    Extrapolated LLM evaluation should distinguish direct estimates, identified sets, and forecasts conditioned on parametric assumptions.

  • Takeaways & Limitations

    The main theorem applies to pooled/random-task count laws under conditional iid completions, while other designs define different observation models.

Abstract

from arXiv · show

Repeated-sampling evaluations increasingly extrapolate pass@k far beyond the number n of samples collected per problem. We show that, in the pooled/random-task conditional-Binomial model, fixed-n success counts identify only the n free moments of the latent per-task success distribution. Consequently, direct pass@k is identified for k <= n, but generic extrapolated pass@k, tail exponents, and tail constants are not identified for k > n, even with arbitrarily many exchangeable tasks at the same rollout budget. This is stronger than the observation that the usual estimator is undefined beyond n: it characterizes the information missing from the fixed-depth count-law experiment. We give exact count-law-preserving constructions with incompatible extrapolations, state the exceptional unique-extension case, and compute sharp population identified intervals through Hausdorff principal representations. On the public 10,000-rollout-per-problem release of Brown et al., counterfactual n = 16 evaluations leave failure at k = 1000 ambiguous by factors from 1.5 to over 2,600 across four MATH/GSM8K/CodeContests configurations. The calibration shows that intermediate-scale failure share alone does not determine width. Our result does not reject parametric inference-time scaling laws; it supplies the nonparametric baseline against which their assumptions can be evaluated. We give an exact, conservative one-coordinate finite-task confidence certificate and a reporting standard separating direct estimates, identified sets, and model-conditioned forecasts.

1 Introduction

The paper asks what fixed-n success counts identify about pass@k beyond the observed rollout depth. It establishes a nonparametric identification boundary, constructs incompatible extrapolations, and calibrates the resulting ambiguity on public evaluation data.

  • Motivation and contribution: Fixed-n counts identify only n free moments of the latent per-task success distribution, so generic pass@k beyond n is partially identified.This is an information limit of the pooled/random-task count-law experiment, not merely a domain restriction of the usual estimator.
  • Implications: The paper supplies a nonparametric baseline for assessing parametric scaling-law forecasts rather than rejecting those models.Model-based forecasts rely on assumptions about unobserved mixing distributions or moments.
  • Motivation and contribution: Direct pass@k is identified for k ≤ n, while interior moment sequences yield nondegenerate identified intervals for every k > n.Rank-deficient boundary sequences can instead uniquely determine the mixing law and all higher-order functionals.
  • Motivation and contribution: Exact count-law-preserving constructions separate polynomial from exponential failure and can change the leading tail constant while preserving the left-tail exponent.These constructions show that incompatible extrapolations can be observationally equivalent at fixed rollout depth.
  • Empirical calibration: At n = 16 and k = 1000, failure ambiguity ranges from 1.5× to over 2,600× across four MATH/GSM8K/CodeContests configurations.The calibration uses the public 10,000-rollout-per-problem release of Brown et al.

2 Setting and directly relevant work

The paper studies pooled/random-task count laws under a conditional-Binomial model, where fixed-depth observations reveal population moments rather than each task’s latent success probability. This setting differs from a labeled fixed benchmark and makes extrapolation forecasts conditional on their mixing assumptions.

  • Model and assumptions: The evaluation fixes the benchmark, prompt, decoding distribution, resource limit, extraction rule, and scorer, then models completion outcomes through latent per-task probabilities.Conditional iid sampling is the premise of count-based pass@k evaluation.
  • Model and assumptions: In the random-task experiment, latent probabilities are drawn from a mixing distribution and only the marginal count law is observed.Increasing the number of exchangeable tasks improves precision about that count law without revealing additional within-task moments.
  • Relation to prior work: The familiar pass@k quantity is a design-based estimate when k ≤ n, not itself an extrapolation model.Beyond the observed rollout budget, forecasts require assumptions about the latent mixing distribution.
  • Relation to prior work: A fixed labeled benchmark has a formally injective finite product likelihood, whereas the pooled count-law experiment can leave multiple mixing laws observationally equivalent.The paper’s theorem concerns the latter asymptotic experiment, not the unrestricted labeled product model.
  • Relation to prior work: Beta–Binomial and tail-law forecasts can be useful, but their unobserved moments and tail properties are modeling assumptions rather than nonparametric discoveries from fixed-n counts.The paper connects this distinction to the truncated Hausdorff moment problem and partial identification.

3 The fixed-rollout identification boundary

The fixed-rollout count law contains exactly the first n free moments of the latent success distribution. Therefore direct pass@k is identified through n, but generic higher-k extrapolation admits distinct compatible values, including qualitatively different tails.

  • Identification theorem: The Bernstein kernels in the count law span the degree-n polynomials, making the count law equivalent to the first n free moments.The normalization m0 = 1 leaves n free moments.
  • Identification theorem: For every k > n, two distributions can share the complete count law while producing different pass@k values.Interior truncated Hausdorff moment sequences give strictly positive-width sharp identified intervals; some boundary sequences uniquely determine the mixing law.
  • Identification theorem: More tasks make the observed count law more precise, whereas more rollouts per task enlarge the set of directly identified functionals; the two are not substitutes.This is the operational meaning of the fixed-rollout boundary.
  • Exact constructions: Uniform[0, 1] mixing and a finite-support quadrature measure can share the n = 64 count law while producing polynomial versus eventual exponential failure.The count laws agree to machine precision despite divergent extrapolations.
  • Exact constructions: For even n = 64, ε = .8 preserves the count law and α = 1 while changing the tail constants from C = .2 to C = 1.This gives a bounded multiplicative ambiguity even when the tail exponent is fixed.

4 Sharp partial identification and finite-sample inference

The paper computes sharp population identified intervals using Hausdorff principal representations and distinguishes them from finite-sample confidence procedures. It also specifies important boundary and design limitations for adaptive or empirical-count settings.

  • Sharp identified sets: For even n = 2r, interval endpoints are attained by the two Hausdorff principal representations, yielding a sharp continuous solution rather than a grid-restricted range.The endpoints are computed through Gaussian quadrature and can also be expressed as a moment–SOS program.
  • Sharp identified sets: Boundary count laws can have unique atomic extensions, causing the identified interval to collapse even when k > n.The generic ambiguity theorem therefore does not imply that every finite count histogram is ambiguous.
  • Finite-sample inference: An empirical histogram is not automatically an exact Binomial-mixture law, so a plug-in sharp interval is not a confidence interval.Finite-sample inference should begin with a simultaneous confidence region for the complete count law and project it through the moment problem.
  • Finite-sample inference: The paper gives an exact but deliberately conservative one-coordinate finite-task certificate based only on the zero-count probability.This certificate makes finite-task uncertainty explicit but does not replace the sharper complete-count-law projection.
  • Design limitations: Adaptive outcome-dependent rollout counts change the observation model, and sampling hard tasks more often does not by itself identify a generic large-k target nonparametrically.Under misspecification, allocation and extrapolation require joint design-aware sensitivity analysis.

5 Public 10,000-rollout calibration

The calibration applies the fixed-rollout identification analysis to public 10,000-rollout-per-problem data, showing that extrapolation width varies sharply across configurations and conventions. At n = 16 and k = 1000, failure ambiguity ranges from narrow to over three orders of magnitude, while intermediate-scale failure share alone does not determine width.

  • Data and reference conventions: The study analyzes four deliberate MATH, GSM8K, and CodeContests case studies from Brown et al.’s public 10,000-rollout-per-problem release, rather than running a new model evaluation.The cases include 128 MATH problems for two model sizes, 127 GSM8K problems, and 140 CodeContests problems.
  • Data and reference conventions: The counterfactual count laws use raw per-task frequencies and a large-N pooled evaluation at n ∈ {16, 64}, removing ordinary finite-task noise from the identification exercise.The construction asks what an arbitrarily large n-rollout pooled-count evaluation could identify under the stated empirical reference.
  • Data and reference conventions: Jeffreys smoothing changes the reference materially when tasks have zero observed successes: in CodeContests, 87 of 140 tasks have c_i = 0, and the raw and smoothed references are .713 and .678.The two conventions are reported separately because the raw reference is not assigned an uncertainty interval.
  • Sharp calibration results: At n = 16 and k = 1000, sharp MATH failure intervals span factors of 183 for 8B and 2,612 for 70B, whereas raw n = 64 GSM8K is nearly point-like.The reported GSM8K raw-reference relative width is 8.84 × 10−47, while MATH relative widths remain about 3%.
  • Sharp calibration results: Intermediate-scale failure share is only a warning signal: profiles with identical target failure, 45.19% window share, eight window tasks, and effective count 2.81 still yield widths differing by 28× at n = 16 and over 1016× at n = 64.The complete truncated-moment geometry, not window mass alone or a window-mass/dispersion summary, determines width.
  • Model comparison: Under the Jeffreys convention, Beta–Binomial forecasts are 4.5–29% above the upper posterior endpoint for MATH and CodeContests but below GSM8K’s lower endpoint by more than 85×.The apparent agreement with a CodeContests raw reference partly reflects the zero-frequency convention, and the comparison does not validate or refute Beta–Binomial forecasting generally.

6 What to report and conclude

For k > n, reports should separate directly identified quantities, identified sets, and model-conditioned forecasts. The paper also cautions that simple difficulty summaries do not determine extrapolation ambiguity and that calibration conventions affect comparisons.

  • Reporting standard: For k > n, report the exact target and sampling design, an identified-set diagnostic or finite-sample confidence region, and model-conditioned forecasts with held-out calibration.Tail exponents and constants require the same separation between fitted and identified quantities.
  • Reporting standard: More tasks improve precision in the pooled/random-task experiment, whereas deeper per-task sampling changes identification.
  • Interpreting ambiguity: The fraction of target-budget failure near 1/k ≲ p ≲ 1/n does not determine extrapolation ambiguity; concentration and remaining moment geometry can alter sharp bounds.
  • Calibration conventions: Table 1’s brackets are sharp population plug-in sets conditional on the raw induced count law, not confidence intervals or exact-rank certificates.
  • Calibration conventions: Table 2 uses a distinct Jeffreys-smoothed latent-probability convention, so its posterior interval and Beta–Binomial prediction are not error bars for the raw reference.
  • Interpreting forecasts: Power-law or Beta–Binomial forecasts can be useful when they predict held-out budgets, but their evidence is predictive accuracy under a stated model rather than nonparametric tail recovery.

7 Limitations

The main theorem applies to a pooled/random-task count-law experiment under conditional iid completions, not to every evaluation design. The calibration is a population plug-in diagnostic, and the paper does not implement its stronger finite-sample identified-set projection.

  • Scope: The theorem concerns pooled/random-task count laws under conditional iid completions; correlated completions, finite exchangeability, adaptive rollout counts, and pipeline changes define different observation models.
  • Scope: For a fixed labeled benchmark, the unrestricted finite product model is formally identified; the paper’s limitation concerns information supplied by fixed-depth pooled-count designs.
  • Calibration: The public calibration conditions on raw-frequency or Jeffreys conventions and is a population plug-in diagnostic, not a finite-sample confidence interval.
  • Finite-sample inference: A sharper finite-sample identified-set projection would require a confidence region for the complete count law and projection through the moment problem, but the paper does not implement it.

8 Conclusion

Fixed-rollout pass@k evaluation is a finite-moment problem: direct estimates end at k ≤ n, while extrapolated pass@k generally remains only partially identified. Sharp bounds and public calibrations show that uncertainty depends on the full count-law geometry, motivating separate reporting of direct estimates, identified sets, and model-conditioned forecasts.

  • At n = 16, observed failure widths at k = 1000 range from 1.5× to over 2,600× across public calibrations.
  • Extrapolated evaluation should distinguish direct estimates, partial-identification bounds, and model-conditioned forecasts.
  • Window share and task count alone do not characterize sharp-set width.The controlled diagnostic fixes coarse summaries while varying the remaining easy-task probabilities, producing different sharp relative-width ranges.
  • At n = 64, GSM8K can have maximal window share while its identified set is nearly point-like.
  • All four sharp-width trajectories contract as the per-task rollout budget increases, but the relationships remain descriptive rather than reducible to a low-dimensional diagnostic.

A Proofs and implementation details

The proofs establish fixed-n count-law equivalence through polynomial moments and construct analytic or discrete mixing laws with incompatible extrapolations. Hausdorff principal representations compute sharp intervals, while boundary cases and numerical checks delimit when ambiguity disappears or computations are reliable.

  • A.1 Identification and constructions: Fixed-n Binomial counts identify every polynomial functional of the latent success probability of degree at most n.
  • A.1 Identification and constructions: For every k > n, two mixing distributions can share the complete count law while producing different pass@k values.
  • A.2 Legendre perturbations: Uniform mixing and a finite-support quadrature law have identical fixed-n count laws but polynomial versus eventual exponential failure.
  • A.2 Legendre perturbations: Analytic densities can retain the same fixed-n count law while having tail exponents 2 and 1.
  • A.3 Boundary moment sequences and sharp bounds: Rank-deficient flat moment sequences can uniquely determine the representing measure, collapsing the extrapolation interval to a point.
  • B Numerical verification: At 120 and 300 decimal digits, all displayed public endpoints agree, with maximum relative difference 5.6 × 10^-54.

C Exact finite-sample certificate

The paper gives an exact distribution-free confidence certificate for extrapolated failure using only the observed zero-count frequency. It is intentionally conservative and separate from the sharper full-moment finite-task projection, which requires a simultaneous multinomial confidence region.

  • The zero-count statistic follows Binomial(N, q0), where q0 equals the population failure functional at rollout depth n.
  • A Clopper–Pearson interval for q0 yields an exact, distribution-free confidence interval [a(Z)^(k/n), b(Z)] for RF(k).
  • The certificate is intentionally coarse because it uses only q0 rather than the full count histogram.
  • The certificate is wide for all four 100–150-task references, whereas sharp population sets condition on a known count law.
  • A tighter finite-task identified-set interval requires a simultaneous multinomial region and projection through the full moment map.

D Public-data protocol

The public-data protocol combines fixed-depth count-law construction, high-precision principal-representation calculations, and audited model-conditioned forecasts. It distinguishes reproducible parametric projections from nonparametric identification and includes numerical, finite-task, and release controls.

  • Data and count-law construction: The calibration uses eligible source records with Boolean is_corrects vectors of length at least 10,000 under stated frequency conventions.The supplied protocol specifies the public release and task counts, but the passage is truncated before all counts are visible.
  • Moment calculations: The procedure computes even-order principal representations at 120-decimal arithmetic and retains the independent 10,000-rollout direct estimator as a check.The plotted reference is the empirical mixing functional conditioning the plug-in set.
  • Model-conditioned forecast: The Beta–Binomial fit searches over a,b > 0 using log coordinates, log-gamma evaluation, deterministic Nelder–Mead optimization, and five documented starts.The retained solution has the lowest objective and produces a model-conditioned forecast.
  • Interpretation: The model-conditioned forecast is a reproducible projection of the induced count law, not an estimate of a nonparametrically identified tail.
  • Optimization audit: At n ∈ {16, 64}, all five documented starts agree within 4.85 × 10^-14 in normalized count-law cross-entropy, with maximum forecast variation 1.18×10^-7.Extending each start by 900 additional Nelder–Mead iterations changes any forecast by at most 2.94 × 10^-8.
  • Reproducibility and release: The release plans to provide task identifiers, per-task counts, conventions, moment vectors, solver diagnostics, fit starts, objective values, random seeds, and scripts for every table and figure.The manuscript also contains algorithmic details intended to support auditing without an external review-time link.
Loading 2609.09245v1…