Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves

Sohail; Sarkar; Shakuntala Baichoo

cs.LGSep 30, 2026

Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves

Authors: Sohail, Sarkar, Shakuntala Baichoo

Organizations: Neel · PMCC AI Lab, Peter Munk Cardiac Centre, University Health Network, Toronto, Ontario, Canada

Abstract

Sampling several answers and keeping the one a verifier scores highest is one of the simplest ways to buy accuracy at test time. Its effect is reported as a scaling curve: accuracy against the number $k$ of sampled answers. The curve is cheap to draw and expensive to trust. A budget read off it is chosen after looking at every point, so only a band that covers all budgets at once protects the choice, and on a 100-question benchmark a fixed exact-binomial design needs 192,000 generated answers to certify 64 budgets to within $\pm1/32$ at 95%. Most of that cost pays for the wrong uncertainty. A benchmark is a fixed list of questions; at budget 64, about three quarters of the variance of a selected answer's correctness lies between questions, and an audit that revisits every question need not pay for it. We derive the minimax cost of certifying the whole curve, up to logarithmic factors. It has three parts: calibrating the tail of the score distribution, telling the questions apart, and within-question noise summed along the curve. At a single benchmark the last part sharpens to the variance of one answer's influence under the best allocation of answers to questions, which every valid audit pays and an audit that learns the allocation attains, up to a logarithm, as the precision grows. A paired audit built on an exponential inequality for two independent draws at the same question needs no pilot. On 185 held-out score pools it uses 0.74 times the answers of the cheapest competing certified audit at 64 budgets and 0.53 times at 1,024, and on a newly generated MMLU-Pro study it certified the curve with 79,133 answers, within 0.6% of what a cost law fitted beforehand predicted from the study's within-question variance. The same paths certify pass@ $k$ and majority voting, and the bands extend to populations of questions and to answers that depend on earlier ones.

Figures & tables

Figure 1: Why a certified curve can be cheap. (a) Accuracy curves

p_{k}(x)

of single questions spread from 0 to 1, while the benchmark average rises smoothly (MATH500, answers from Llama-3.1-8B-Instruct, one reward model; 60 of the 250 questions are drawn). (b) Median share of the variance of the selected answer’s correctness that lies between questions, with interquartile band, over the 185 held-out pools. (c) Generated answers needed for 100 MMLU-Pro questions and 64 budgets: an unbiased estimate of every point, a band from a fixed exact-binomial design, and a band from the paired audit of Section 6 , both at half-width

1/32

with 95% simultaneous coverage.

Figure 2: The coupling behind Lemma 3 . The highest score of the whole path lies in block

A

or in block

B

, so the winner at budget

k

is the winner of one of the two blocks. Exchanging the unshared parts of the blocks swaps their winners and leaves the law of the path unchanged.

Figure 3: The price at one benchmark. (a)

\Gamma

of Theorem 6 against

\Sigma_{\mathrm{w}}

K=64

for the 185 held-out pools and the MMLU-Pro study (law of the first 4,000 reference answers per question). The median of

\Sigma_{\mathrm{w}}/\Gamma

is 12. (b) The allocation of answers to questions that attains

\Gamma

on the MMLU-Pro study, sorted by share.

Figure 4: One paired audit, traced round by round (the stored run on the MATH500 pool of Figure 1 a, 250 questions,

K=64

). (a) Answers generated per question visit in each pair of rounds; paths stop at the largest unresolved budget. (b) Half-width of the band at three budgets; a budget retires when it reaches

1/32

, and the final look is at round 18. (c) Answers used so far, against the fixed exact-binomial design and the cheapest of the competing certified audits on the same pool. The audit stops after 12 rounds with 127,500 answers, and its band covers the exact curve.

Figure 5: Theorem 13 : the leading ratio of the minimax errors without and with known score percentiles, as a function of the balance

C\log K/(KT)

between generated answers

C

and labels

T

solutions from	envelope	variance-optimal	fixed-width	primal–dual gap
Llama-3-8B	6,681	6,319	6,113	0.215%
Llama-3-70B	5,398	5,822	5,142	0.233%

Table 1: Sufficient label draws for a band of half-width

1/32

at level 95% over

K=100

budgets with known percentiles, on two complete HumanEval+ pools scored by Llama-3.1-70B unit tests ( Ma et al.,, 2025 ; Liu et al.,, 2023 ) . The designs receive the same pool; answer generation is not charged. Last column: relative gap between the feasible fixed-width proposal and its dual lower bound.

Figure 6: First budget at which the exact curve of a held-out pool comes within

1/32

of its best value over budgets up to 1024.

$K$	answers	interval	pools cheaper	labels
64	0.74	[0.67, 0.88]	175/185	0.73
256	0.66	[0.59, 0.73]	175/185	0.68
1024	0.53	[0.47, 0.58]	173/185	0.61

Table 2: Paired audit on the 185 held-out pools, relative to the cheapest competing certified audit on each pool (median ratio of five-run means). Brackets: 95% bootstrap interval over the eight answer sets. Labels are compared with the cheapest competitor in labels.

Figure 7: (a) Distribution of the ratio of generated answers, paired audit to the cheapest competing certified audit, over the 185 held-out pools. Left of the dashed line the paired audit is cheaper than every competitor on that pool. (b) Median ratio for the designs of the ablation in Section 8.3 ; every design uses the same retirement of resolved budgets.

Figure 8: (a) Cost ratio at

K=64

for every stored pool and three precisions, against

M\varepsilon^{2}

; the start-up of two complete rounds decides the ratio at the right. (b) Median ratio on the held-out pools, whose questions have 100 stored answers, and on a pool with 4,000 answers per question built from the MMLU-Pro reference stream. (c)

\Sigma_{\mathrm{w}}

as a fraction of its worst case

K/4

in the same two settings (held-out: median).

Figure 9: The cost law. (a)

N\approx 2.16\,KM+15.13\,K/\varepsilon+12.88\,\Sigma_{\mathrm{w}}/\varepsilon^{2}

, fitted to two paired audits per stored pool at

K=64

and

\varepsilon=1/32

(

R^{2}=0.958

), against measured cost. The star is the new MMLU-Pro study: the coefficients were fixed before any of its answers existed, and its

\Sigma_{\mathrm{w}}

comes from the separate reference stream. (b) One law

aKM+L(bK/\varepsilon+c\,\Sigma_{\mathrm{w}}/\varepsilon^{2})

for all horizons and precisions (

R^{2}=0.995

curve	audit	answers	labels	grader calls	cost ($)
best-of- $k$	paired	79,133	6,160	256	1.91
best-of- $k$	all-subsets	78,933	55,590	385	1.91
pass@ $k$	paired	60,467	5,943	285	1.46
pass@ $k$	all-subsets	49,067	49,067	385	1.18
majority voting	paired	62,267	58,999	356	1.50
majority voting	all-subsets	49,067	49,067	385	1.18

Table 3: MMLU-Pro study,

M=100

K=64

\varepsilon=1/32

\delta=0.05

: means over three audit streams. Grader calls reuse one grade per distinct question–answer pair; dollars are the generation cost at the price we paid per answer. The designs below the rule certify best-of-

k

with fixed sample sizes.

Figure 10: Certified curves for 100 MMLU-Pro questions (first audit stream): simultaneous bands of half-width at most

1/32

at level 95% from the paired audit and the all-subsets audit, with reference curves estimated from 409,448 separately generated answers. Shaded in (b): budgets that the pass@

k

bands rule out as a best budget.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

design	$K=64$	$K=256$	$K=1024$
exact binomial with completion	1.49 / 1.37	1.98 / 1.47	2.74 / 1.66
nested exact binomial	1.80 / 1.70	2.13 / 1.75	2.73 / 1.78
rank-based stopping	1.37 / 1.57	1.54 / 1.68	1.90 / 1.88
nested rank-based stopping	1.36 / 1.63	1.55 / 1.73	1.87 / 1.94
fixed Hoeffding	2.15 / 1.99	2.69 / 2.00	–
fixed exact binomial	1.65 / 1.53	2.12 / 1.60	–

Appendix

Table 4: Median ratio of each certified design’s cost to the paired audit’s on the 185 held-out pools (answers / correctness queries). The fixed designs and the record design were run at

K=64

and 256.

design	$K=64$	$K=256$	$K=1024$
nested exact binomial, random questions	1.42	1.45	1.45
nested exact binomial, balanced rounds	1.45	1.45	1.47
per-row betting, balanced rounds	0.86	0.75	0.63
per-row betting, matched bet and cap	0.91	0.81	0.70
paired audit	0.74	0.66	0.53
balanced / random nested exact binomial	1.01	1.00	1.03

Appendix

Table 5: Ablation on the 185 held-out pools: median ratio to the cheapest competing certified audit (five-run means).

Explore similar work

Sep 28, 2026cs.AI

Test-Time Scaling via Budgeted Multi-Attribute Verification

Verifying LLM-generated answers under a shared computational budget requires jointly deciding which candidates to inspect and which verification attributes to evaluate. We formulate this problem as multi-attribute good-arm identification under a global budget: each candidate is an arm evaluated along several costly attributes, and the goal is to certify as many candidates as possible whose mean scores exceed the prescribed thresholds on all attributes. We propose \textsc{BMA-GAI}, an algorithm that combines cost-aware arm selection with adaptive sampling of attributes. Every observation serves both to guide adaptive allocation and to support anytime-valid certification, which removes the need for a separate confirmation stage. We establish an asymptotic coverage guarantee for \textsc{BMA-GAI} and derive a matching information-theoretic converse that characterizes the intrinsic complexity of the problem, thereby proving that \textsc{BMA-GAI} is first-order optimal away from critical budget levels. Experiments on synthetic benchmarks and an LLM answer-verification task show that \textsc{BMA-GAI} allocates the verification budget more efficiently and certifies more high-quality candidates than competing methods.

Bo Xue, Ji Cheng, Shen-Huan Lyu +2

City University of Hong Kong · Hohai University · Zhejiang University

Token Budget Allocation Large Language Model Responses Synthetic Benchmark Information-Theoretic Limits

Ask PDF

Sep 30, 2026cs.AI

Budget Boundary Effects in Test-Time Mathematical Reasoning

A cumulative token cap can fall inside a mathematical derivation, forcing a test-time controller to choose between stopping at the cap (strict) and allowing the current attempt to finish (advisory). We measure this boundary choice with paired offline replays of 19,200 public traces: 120 AIME, BrUMO and HMMT problems and two archive configurations of one model. Candidate order and a 16-attempt cap are fixed, and answer selection is blind to reference answers and correctness labels. Three findings emerge. First, at the 4k cap, most advisory accuracy gains replace abstention with a correct answer; strict stopping pays for an unfinished prefix that the completed-only selector cannot use. Second, comparisons along realized cost differ from same-cap comparisons: advisory 4k in low has higher accuracy than strict 8k at comparable mean completion cost, while in high its observed accuracy is 0.42 points below strict 32k using 59% of its mean tokens. These aggregate comparisons do not establish equal-compute superiority or accuracy equivalence. Third, increased candidate coverage does not guarantee higher answer accuracy: a log-probability selector loses accuracy while coverage rises, including after a source-grade consistency repair. Same-cap majority-accuracy differences shrink below 1.3 percentage points at 32k. Budget curves should jointly state the cap, realized cost, eligible candidates, stopping rule and selector information.

Guilin Zhang, Ziqi Tan, Wulan Guo +5

Yantong AI

Mathematical Reasoning Test Time Benchmark Saturation Answer Majority Voting

Ask PDF

Jun 27, 2026cs.LG

When More Sampling Hurts: The Modal Ceiling and Correlation Ceiling of Test-Time Scaling

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.

Yong Yi Bay, Kathleen A. Yearick

University of Illinois at Urbana-Champaign

Test-Time Scaling Reasoning Benchmark Ceiling

Ask PDF