A fixed number of rollouts per task cannot alone justify extrapolated pass@k: only pass@k up to the rollout depth n are nonparametrically identified, while forecasts beyond n depend on modeling assumptions and can differ by orders of magnitude in public LLM evaluations.

Main Finding

Fixed-depth (fixed-n) rollout/count experiments identify only the first n free moments of the latent per-task success-probability distribution. Consequently: - Direct pass@k is nonparametrically identified only for k ≤ n. - For k > n, pass@k and tail features (exponents, leading constants) are generically only partially identified: the data admit multiple observationally equivalent mixing laws that produce very different extrapolated pass@k. - Parametric extrapolations (e.g., Beta–Binomial or fitted power laws) are therefore model-conditioned forecasts, not nonparametric discoveries; the paper supplies the sharp nonparametric baseline (identified set) against which such models must be judged.

Key Points

• Identification theorem: the pooled/random-task Binomial count law q = (q0,...,qn) identifies exactly integrals of polynomials of degree ≤ n (equivalently the first n free moments mj = ∫ p^j dF(p) for j = 0,...,n). RF(k) = E[(1−p)^k] is identified for integer k ≤ n but generically not for k > n.
• Constructive counterexamples:
  • Gauss–Legendre quadrature: a uniform(0,1) mixing and a finite-support quadrature have identical fixed-n count laws but qualitatively incompatible extrapolated failure (polynomial vs exponential decay).
  • Legendre perturbation family: can hold tail exponent fixed while changing the leading tail constant—so even fixing α leaves multiplicative ambiguity.
• Sharp partial-identification: using truncated Hausdorff moment theory and Hausdorff principal representations, the paper computes exact identified intervals (endpoints attained by principal atomic representations). For even n = 2r, endpoints are r+1-atom measures containing 0 or 1.
• Finite-sample inference: a plug-in identified set is not an honest confidence interval; one should form a simultaneous confidence region QN for the count law and project S = ⋃_{q ∈ QN} In,k(q). The paper also gives a simple conservative finite-task certificate (Clopper–Pearson based) using only q0.
• Adaptive sampling: changing per-task rollout budgets (outcome-dependent sampling) changes the observation model; such schemes are not summarized by a single fixed-n count law and must be modeled jointly with extrapolation assumptions.

Data & Methods

• Model and experiment:
  • Conditional Binomial (per-task iid completions): Yij | pi ∼ Bernoulli(pi), Ci = Σ_{j=1}^n Yij.
  • Pooled/random-task experiment: latent task probabilities pi ∼ F, observed are marginal success-count probabilities qc = Pr(C = c) = ∫ Binomial(c; n, p) dF(p).
  • Quantity of interest: RF(k) = E[(1−p)^k] (mean failure at rollout budget k); pass@k = 1 − RF(k).
• Mathematical tools:
  • Truncated Hausdorff moment problem: fixed-n counts give n+1 Bernstein-kernel moments; the space of representing measures for those truncated moments is characterized by principal representations, generalized moment extremal problems, and Chebyshev system arguments.
  • Exact constructions via Gauss–Legendre quadrature and Legendre-polynomial perturbations show observational equivalence at fixed n with divergent high-k behavior.
  • Numerical computation: Golub–Welsch implementation to compute principal atomic measures and sharp endpoints at high precision (verified to many decimal places).
• Calibration:
  • Uses the public Brown et al. (2024) “Monkey Business” 10,000-rollout-per-problem release (per-completion correctness labels).
  • Four case studies: MATH (Llama-3-8B and Llama-3-70B), GSM8K (Llama-3-70B), and CodeContests (Llama-3-70B).
  • Counterfactual pooled-counts: from per-task empirical frequencies ˆp_i = c_i/M_i, form the N→∞ pooled Bin(n,ˆp_i) count law for n ∈ {16,64}; also report Jeffreys-smoothed conventions (˜p_i = (c_i+1/2)/(M_i+1)).
  • Main calibration results (selected highlights):
  • At n = 16 and target k = 1000, sharp identified intervals for RF(1000) can vary dramatically across configurations: relative multiplicative width factors ranged from ~1.5 up to >2,600.
  • At n = 64 some configurations (e.g., one GSM8K case) are nearly point-identified, while others (MATH) retain several-percent relative width.
  • The Beta–Binomial forecast (fit to the same count law) can lie substantially outside the nonparametric identified set depending on the mixing convention: e.g., under Jeffreys smoothing, Beta–Binomial predictions were 4.5–29% above the posterior upper endpoint in some cases and understated residual GSM8K failure by >85× in another.
  • Stress-test: synthetic 128-task profiles with identical target failure, window share, and dispersion produced sharp-set widths varying by orders of magnitude—showing intermediate-window mass and dispersion are not sufficient diagnostics.

Implications for AI Economics

• Measurement and inference risk: evaluations that extrapolate pass@k beyond observed per-task depth (n) face inherent non-identifiability unless they impose—and explicitly state—parametric assumptions about the latent task-difficulty mixing F. Economic or policy decisions (e.g., deployment readiness, safety thresholds, pricing of extra compute) based on extrapolated pass@k must account for model conditioning and partial identification.
• Cost–design trade-offs:
  • Adding more tasks (N → ∞) increases precision of the identified objects (the count law q) but does not enlarge the set of functionals identified at fixed per-task depth n.
  • Increasing per-task rollouts (raising n) expands identification (pass@k becomes identified up to larger k). Thus evaluation budgets should be chosen with the target k in mind: to nonparametrically estimate pass@k, ensure n ≥ k.
  • For given resources, there is a structural trade-off between breadth (more tasks) and depth (more rollouts per task); economic optimization of evaluation design must consider which inference target (direct pass@k vs. parametric forecast) matters for decisions.
• Reporting standards and transparency:
  • Regulators, purchasers, benchmark providers, and researchers should separate (and report separately):
  • Direct (design-based) pass@k estimates for k ≤ n.
  • Nonparametric identified sets (sharp bounds) for functionals when k > n, with finite-sample confidence regions projected through these sets where appropriate.
  • Any parametric/extrapolated forecasts (e.g., Beta–Binomial, power laws) as model-conditioned predictions with explicit model and smoothing conventions, and with diagnostics comparing the forecast to the identified set.
  • This separation avoids over-interpreting fitted extrapolations as if they were identified by the data-producing experiment.
• Model evaluation and regulation:
  • Parametric scaling laws used for economic or safety forecasting should be validated against the nonparametric baseline (identified set). Large deviations between a model and the identified set indicate strong, consequential model assumptions, which must be justified when used for high-stakes decisions (deployment limits, required rollouts for certification, or cost forecasts).
  • Adaptive sampling and active allocation strategies can improve effective identification for targeted tasks but they change the data-generating model; their benefits should therefore be evaluated under the correct (design-aware) likelihood.
• Practical guidance for economic analysis:
  • When using pass@k forecasts in cost–benefit calculations (e.g., how much compute to allocate to reach a reliability target), include the identified-set uncertainty as a baseline downside/upside envelope. Parametric point forecasts should be shown relative to that envelope.
  • For market or policy decisions that hinge on low-probability failures at large k, prefer designs that increase per-task depth for sentinel tasks or explicitly model and justify mixing assumptions governing tail mass.
  • Recognize that simple diagnostics (e.g., fraction of tasks with empirical p in [1/k, 1/n]) are useful warnings but do not replace the full truncated-moment geometry needed to assess extrapolation ambiguity.

Summary takeaway: fixed-n pooled rollout experiments fundamentally limit what can be learned nonparametrically about large-rollout pass@k. Extrapolations beyond n require explicit modeling assumptions and should be reported and interpreted as model-conditioned forecasts; the paper provides the exact partial-identification baseline (sharp sets and finite-sample certificates) that economic and policy analyses should use to quantify the uncertainty from extrapolation.