Source-linked AI summary
When More Sampling Hurts: The Modal Ceiling and Correlation Ceiling of Test-Time Scaling
Yong Yi Bay, Kathleen A. Yearick
TL;DR
Test-time scaling can increase coverage without showing whether a deployed system can select the correct answer or estimate benchmark accuracy efficiently. This paper separates these goals and derives effective sample counts, finding that selection and estimation hit low ceilings while coverage can continue rising.
Problem
Coverage rises with more samples, but the limits of selecting one answer and estimating benchmark accuracy are not captured by nominal sample counts.
Method
The paper models sampling as cluster sampling, derives effective sample counts and the correlation ceiling, and separates coverage, estimation, and selection.
Results
Selection stalls while coverage reaches 0.88, with 256 dependent tries reducing to about thirteen and selection correct for only 0.45; benchmark estimation saturates at 1/ρ.
Takeaways & Limitations
Sampling budgets should be set by the goal and reported with effective rather than nominal sample counts, because extra draws eventually stop paying.
Takeaways & Limitations
The paper treats correctness correlation and answer-string concentration as separate quantities, so its exact claims do not equate benchmark estimation with selection.
Abstract
from arXiv · showhide
People overthink; language models over-sample, and the extra effort can talk both into a worse answer. Reasoning systems answer a hard question by sampling it many times (test-time scaling), and the more they draw, the more often a correct answer turns up somewhere, so coverage, the fraction of problems with at least one correct try, climbs and appears to be progress. But a deployed system must return one answer, and choosing it, not knowing which try is right, is selection; selection is capped, and past a point extra samples only make the model surer of a confident mistake, even as every draw adds cost. The gap between climbing coverage and stalled selection, the identifiability gap, is the answer a model can produce but not pick. So the real question is not whether to sample but how far, and the answer is: not far. For picking an answer, the vote has already settled within a few dozen draws, the modal ceiling; for scoring a benchmark, sooner still, the correlation ceiling. Beyond that, extra draws cost compute and add nothing, and can even make the answer worse. This paper turns the cutoff into a single number, the effective number of samples, that any sampling run already reveals. The bottleneck is recognizing a right answer, not generating one.
1 Introduction and roadmap
The introduction distinguishes coverage from selection: more samples can uncover a correct answer without enabling the system to choose it. It also identifies a separate correlation ceiling, where correlated draws provide fewer effective samples than their nominal count suggests, and previews the paper’s derivations and measurements.
- Motivation: Test-time scaling spends inference compute on longer reasoning or on drawing and combining more samples; this paper studies the sampling lever.Coverage is the fraction of problems with at least one correct sample.
- Coverage versus selection: Coverage asks whether any sample is correct, whereas selection must commit to one answer and plurality voting converges to the model’s most common answer.When that modal answer is wrong, additional samples make the wrong answer win more confidently.
- Correlation ceiling: The n attempts are correlated cluster samples from one prompt, so their information is reduced by the design effect deff = 1 + (n −1)ρ.The intraclass correlation ρ measures similarity among attempts.
- Correlation ceiling: The effective sample size saturates at the correlation ceiling 1/ρ, which governs estimation rather than selection.The two ceilings are kept conceptually separate, while the identifiability gap is measured later in Section 4.3.
- Roadmap: The paper derives the effective number of samples, correlation ceiling, and marginal sample value, then separates coverage from selection and measures their identifiability gap.Later sections also analyze within- and between-problem correlations.
2 Test-time sampling is cluster sampling
Test-time samples for one prompt form an exchangeable cluster rather than independent fresh draws, so coverage, estimation, and selection are functions of the same correlated attempts. Under exchangeability, latent per-problem difficulty induces nonnegative correctness correlation, making the design effect and 1/ρ ceiling exact for estimating success rates but not for coverage or selection.
- Cluster sampling: Repeated attempts for one prompt are treated as a cluster, with a verifier assigning each response a binary correctness indicator.For fixed prompt q and decoding settings, n responses are sampled and scored as Yi = 1{oi is correct for q}.
- Cluster sampling: Best-of-n, weighted voting, and self-consistency all derive their outputs from the same sampled distribution.These methods differ in how they read the draws, but each is a function of the repeated attempts.
- Exchangeability: Exchangeability models attempts as conditionally independent given a hidden success rate θ, whose variation across problems creates intraclass correlation ρ.A fresh session first draws θ, representing a strong or weak reasoning basin; attempts then behave as θ-weighted independent coins.
- Exchangeability: ρ ≥ 0, with ρ = 0 representing independence and ρ = 1 total within-session correctness collapse.The nonnegative-correlation result follows from Var(θ) ≥ 0 under the de Finetti representation.
- Estimands: Under exchangeability, deff = 1+(n−1)ρ and the ceiling 1/ρ are exact for the success fraction ˆp = K/n, which estimates per-problem or pooled benchmark accuracy.This design effect governs how precisely a sampling budget estimates the mean success rate.
- Estimands: Coverage depends on the full mixing distribution G, while selection is a separate quantity rather than the mean success fraction.Coverage is pass@n = P[K ≥1]; selection methods such as self-consistency and best-of-n are analyzed separately.
3 The effective number of samples
The effective number of samples, n_eff = n/[1+(n−1)ρ], captures how correlation reduces a sampling run’s information relative to independent draws. With positive correlation, n_eff has a finite ceiling of 1/ρ, reaches half that ceiling near n ≈ 1/ρ, and makes additional samples rapidly redundant.
- Effective sample size: Correlation inflates count variance by the design effect 1+(n−1)ρ, so the success fraction behaves as if estimated from n_eff independent samples.The variance identity is confirmed against Monte Carlo simulation.
- Correlation ceiling: For ρ > 0, n_eff increases with n but converges to the finite correlation ceiling 1/ρ.A cluster with intraclass correlation ρ is worth at most 1/ρ independent draws under equicorrelation.
- Correlation ceiling: n ≈ 1/ρ samples reach half of the effective-sample ceiling, identifying the scale at which additional draws begin yielding sharply diminishing returns.The exact half-ceiling point is n = (1−ρ)/ρ.
- Marginal value: The marginal effective sample from the n-th draw decays quadratically and becomes negligible once n ≫ 1/ρ.Past n ≈ 1/ρ, spending buys redundancy rather than signal.
- Worked example: At ρ = 0.1, the tenth draw contributes approximately 0.25 effective samples while the hundredth contributes approximately 0.008.A thousand-sample run therefore carries roughly the estimation information of its first ten draws.
4 Coverage rises, selection saturates
Coverage keeps rising toward the problems the model can solve, while selection saturates at the modal-hit rate because voting converges on the most common answer. This creates an identifiability gap: correct answers may be sampled but not selected, and extra sampling can reinforce wrong modes.
- Coverage: Coverage is non-decreasing in sample count and converges to 1−π0, the fraction of problems the model can solve at least once.It rises strictly when some problems have intermediate per-sample success rates.
- Coverage: Correlated attempts reduce coverage below the independent-draw bound 1−(1−s)^n, with the shortfall governed by rarely solved problems.Difficulty heterogeneity can make the miss rate decay as n−α rather than exponentially, slowing further gains.
- Selection: Selection converges to the plurality mode, imposing a sample-budget-independent modal ceiling equal to the rate at which that mode is correct.Once sampling reveals the mode, additional samples cannot improve the vote and can worsen it when the mode is wrong.
- Selection: On reachable problems with an incorrect mode, more sampling drives selection accuracy to 0 while coverage rises to 1.This anti-scaling occurs because extra samples sharpen a confident wrong answer; ceiling speed depends on answer-distribution concentration.
5 Decomposition, allocation, and measurement
This section separates pooled correlation into within- and between-problem sources, converts each objective’s ceiling into a compute-allocation rule, and provides an estimator for effective samples from existing sampling logs. Coverage continues to benefit from sampling, selection plateaus near the effective answer count, and benchmark estimation saturates near 1/ρb.
- Correlation decomposition: Pooled correlation separates into within-problem dependence ρw and between-problem difficulty heterogeneity ρb; with ρw ≈0, the pooled ρ is essentially ρb.Section 4.3 measures ˆρw ≈0.0007 under independent decoding.
- Decorrelation: Decorrelation through temperature, nucleus sampling, prompt diversity, or model mixing is the tested lever for raising the selection plateau rather than simply increasing n.The pre-registered protocol tests whether these decoding choices raise the plateau when ˆρw ≈0.
- Compute allocation: Benchmark estimation needs about n ≈1/ρb samples per problem, so remaining compute should go to more problems.At the measured ρb, this is about two samples per problem.
- Compute allocation: Selection without a verifier plateaus near the effective answer count 1/∑a p_q(a)^2 and can anti-scale beyond it, whereas verifier-based coverage keeps improving with more samples.The three goals therefore reach ceilings at different points: coverage without a within-problem ceiling, selection after plurality stabilization, and estimation almost immediately.
- Measurement: Estimate ˆρ from a sampling log, then report neff = n/[1+(n−1)ˆρ] alongside nominal n, with ceiling 1/ˆρ.On saturated benchmarks, the estimator can be small or negative and should be clipped at zero; pooled ˆρ mixes ρb and ρw.
- Practical checklist: The three governing quantities are difficulty correlation ρb, effective answer count, and verifier accuracy, which determine how much of a sampling budget is real for each use.The first two are obtained from sampling-log estimators, while verifier accuracy belongs to the scorer.
6 Conclusion
More sampling raises coverage while selection stalls at the modal ceiling, creating an identifiability gap between solvable problems and returned answers. Benchmark-mean estimation meets a correlation ceiling, so the effective number of samples indicates when additional draws stop paying and shifts the bottleneck toward recognizing correct answers.
- Conclusion: Coverage climbs with more sampling, but selection stalls at the modal ceiling, producing an identifiability gap.The gap consists of solvable problems whose correct answer a vote never returns.
- When to stop: About 1/ρb samples estimate a benchmark mean, while selecting one answer requires roughly the effective number of answers.Coverage has no limit when a verifier can pick the correct sampled answer out.
- When to stop: Reporting the effective number of samples beside nominal n shows how much of the budget counts and where additional sampling stops paying.The effective number is obtained from a closed form solved for rather than searched.
Appendix A: Elementary derivations
The appendix derives the beta-binomial moments, the polynomial tail of zero-success probability, and the asymptotic selection plateau. It also shows why majority voting cannot exceed the modal-hit rate and derives the same-problem design effect.
- Zero-success probability and its tail: Coverage approaches its limit polynomially, not exponentially, because the gamma ratio in the zero-success probability decays as n−α.The none-succeed probability is the beta average of (1−θ)^n, and Stirling’s approximation gives Γ(β+n)/Γ(α+β+n) ∼ n−α.
- The selection plateau: Plurality frequencies converge almost surely to the underlying answer probabilities, so empirical selection converges to the true mode and its modal-hit rate.For each problem, the limiting selected answer is q = argmaxa p_q(a), with accuracy 1{a⋆ = q}; averaging gives πmode.
- The selection plateau: The majority-vote special case is right asymptotically precisely when θ > 1/2, and its bound never exceeds πmode.In the two-answer case, K/n → θ almost surely; when every rival answer remains below 1/2, it also remains below the correct answer.
- Two-stage design effect: The same-problem design effect is 1+(n−1)ρ.The derivation pools attempts across problems, separates between-problem correlation ρb from common within-problem correlation ρw, and applies the law of total covariance.
Appendix B: Reproducibility
The paper is fully reproducible from a clean checkout: scripts verify its key mathematical identities against Monte Carlo simulation, and all checks pass.
- Every number, table, and figure regenerates from a clean checkout.
- scripts/verify_math.py numerically checks the identities from Sections 3–5 against Monte Carlo simulation.The checks include variance identity (6), coverage monotonicity, the modal-answer selection ceiling (13), its anti-scaling corollary, the majority-vote lower bound, and the two-stage decomposition (14).
- All verification checks pass.