Certified Test-Time Scaling Curves

Sources#

• Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves
• How Much Can Language Models Gain from Test-Time Computation?

Summary#

The test-time-compute literature reports its result as a curve: accuracy of the selected answer against the number k of samples (Large-Scale Test-Time Compute, Latent Capability Overhang). Readers then pick a budget off it, usually on a plateau. Sohail (Neel) Sarkar and Shakuntala Baichoo (PMCC AI Lab, University Health Network, Toronto; arXiv 2609.40190, 2026-09-30, 32pp, empirical) point out what that habit needs and does not have. A budget chosen after looking at every point is protected only by a band that covers every budget at once. Pointwise intervals do not protect the choice, and neither does the bootstrap: a within-question bootstrap band at nominal 95% missed the exact curve in 58 of 925 held-out runs (6.3%).

Valid bands exist and are expensive. On 100 MMLU-Pro questions, one 64-answer path per question (6,400 answers) already gives an unbiased estimate of every point on the curve. Certifying the same curve to ±1/32 at 95% with a fixed exact-binomial design takes 192,000. The paper's title is that ratio: the curve is cheap to draw and expensive to trust.

Its argument is that most of the 192,000 pays for the wrong uncertainty. A benchmark is a fixed list of questions, and the reported accuracy is an average over that list. At budget 64 a median ~74% of the variance in a selected answer's correctness lies between questions (62% at k = 1; Figure 1b, 185 held-out pools). An audit that revisits every question need not pay for it. The paper derives what a certified curve must cost, builds an audit that pays close to that price, and tests it against exact curves.

What a band buys#

Proposition 1 is the reason to want simultaneity, and it uses nothing but coverage, so it holds whatever rule picked the budget after seeing the band. Given intervals [l_k, u_k] that all cover and are at most 2ε wide:

• every budget that truly maximizes accuracy lies in {k: u_k ≥ max_j l_j}, so budgets outside that set are certified as not-best;
• the budget maximizing l_k is within 2ε of the best;
• with known per-budget costs and a price λ, maximizing the band midpoint minus λ·cost is within 2ε of the best trade-off;
• if a second system's band sits wholly below the first's at some budget, the first is better there, with joint coverage 1 − δ − δ′.

"A budget that looks best among K pointwise intervals is best by selection as much as by accuracy." This is the statistical version of Compute-Controlled Benchmarking's reporting rule. Plotting performance against budget is the first step, and choosing a budget from the plot is a multiple-comparison problem that the plot does not solve.

The price, and its three parts#

Write M for the number of questions, K for the largest budget, ε for the half-width and δ for the error rate (defaults ε = 1/32, δ = 0.05). Write v̄_k for the within-question variance at budget k averaged over questions, and Σw = Σ_j max_{k≥j} v̄_k for that variance summed along the curve, with each answer position charged for the noisiest budget that still needs it. Theorem 4 gives the minimax number of generated answers over laws with Σw ≤ s, up to logarithmic factors:

K/ε + min(M, ε⁻²) + s/ε²

Each term has a matching lower bound and a different cause (Appendix C):

1. Calibrating the score tail. A valid audit must allow for a rare answer that scores above everything seen so far and carries the minority label. If such an answer turns up with probability 3ε/K per draw, it moves θ_K by more than 2ε, so the audit must generate about K/ε answers before it can rule it out. This term is paid at every law, even with deterministic correctness: every valid audit generates at least 7κ_δK/(32ε) answers in expectation.
2. Telling questions apart. Hidden per-question correctness bits that scores do not reveal force most of them to be observed once M ≤ ε⁻², and about ε⁻² of them otherwise.
3. Within-question noise. A law whose winners change label within a question forces s/ε² answers.

On the paper's MMLU-Pro study (M = 100, K = 64) the three terms are 2,048, 100 and 2,628. With the worst-case envelope s = K/4 the last would be 16,384. The measured within-question variance is about six times below the worst case, and that term sets the bill. Over the 185 held-out pools, Σw is a quarter of its worst case at K = 64 and 6% of it at K = 1,024.

Two facts make the whole curve cheap relative to K separate estimates:

• Nested winners (Lemma 3). For a ≤ k ≤ 2a on one path, E{(W_k − W_a)² | x} ≤ p_a(x){1 − p_a(x)}. Budgets a factor of two apart differ by at most the within-question noise of the smaller one, and no between-question variance enters. One path therefore serves every budget.
• Labels are cheap. A path needs correctness only at its score records, the answers that beat every earlier score. Without ties the k-th answer is a record with probability 1/k whatever the question (Rényi), so a path of length K needs about H_K ≈ log K labels. Labels for the whole curve cost what labels for its first point cost, up to logarithms. The larger budgets are paid for in generation, not grading.

For fresh questions drawn from a population the between-question variance returns, and the price becomes K/ε² generated answers. Simultaneity over all K budgets then adds only a log log K term to the number of questions (Proposition 2).

The price at one benchmark, and why it cannot be had for free#

Theorem 4 is a statement about classes of laws. At a single fixed benchmark the leading term shrinks from Σw to Γ, the variance of one answer's influence under the best allocation of answers to questions (a Neyman allocation over a least-favourable mixture of budgets). Every valid audit pays K/ε + Γ/ε² up to constants, and an audit that learns the allocation attains Γ/ε² up to a logarithm as ε → 0 (Theorem 6).

The gap is large on real data. On the MMLU-Pro study Γ = 0.28 against Σw = 2.57, and over the held-out pools the median Σw/Γ is 12 (IQR 8.4–21.9). Most of it is allocation. The model is right, or wrong, at least 98% of the time on 58 of the 100 MMLU-Pro questions, and the optimal allocation puts 90% of its answers on 23 questions.

Finding those questions costs answers, though. At ε = 1/32 the pilot of the audit behind Theorem 6 alone would use 179,200 answers, more than twice the paired audit's whole bill. Proposition 5 shows that no audit finds them for free at a fixed precision. A guess-and-verify argument means no single audit can be optimal law by law: for every valid audit there is a benchmark where it spends at least M/4 while another valid audit spends about log(2/δ)/ε. This is the formal reason the same evidence cannot be both cheap and adaptive to the benchmark at once, and it names the paper's open problem.

The paired audit#

Stratified sampling removes the between-question variance only if the confidence sequence can see the smaller variance that remains. Two observations from the paper make this the crux:

• Balance alone buys nothing. Nested exact-binomial looks cost the same on balanced rounds as on random questions (ratio 1.01 / 1.00 / 1.03 at K = 64 / 256 / 1,024), because an exact-binomial interval cannot see a smaller variance.
• Plug-in centering pays the between-question variance anyway. Early on, the error of each question's estimated mean is itself a between-question deviation, so the penalty charges exactly what balance was supposed to remove.

The fix is a pair. For two independent Bernoulli draws A, B at the same question, (A − B)² has mean exactly twice the within-question variance, whatever the question's mean. Lemma 7 turns this into an exponential inequality, E exp{±λ(A + B − 2p) − ψ(λ)(A − B)²} ≤ 1 with ψ(λ) = −log(1 − λ) − λ, whose penalty needs no estimated center. The audit runs in rounds, and every round visits every question with a fresh path:

1. Grow only what is needed. Each path is grown to the largest budget whose interval is still wider than 2ε, and correctness is queried only at score records.
2. Update the band. Per budget, multiply the inequality over questions and pairs into two nonnegative supermartingales and apply Ville's inequality with a union over the 2K sides. This gives an anytime-valid simultaneous band.
3. Bet on the variance seen so far. λ_j = min{0.95, ε/(ε + v̂_j)}, with v̂ half the earlier pairs' disagreement rate.
4. Retire and stop. A budget retires at width 2ε. The last 0.05δ goes to an exact-binomial look at a fixed final round, which ends the audit.

That final look needed its own lemma, and the lemma corrects a common shortcut. A pooled count over questions with unequal success rates is not binomial, and Hoeffding's 1956 comparison bounds its tail by the binomial tail only below nθ − 1. Just below the mean it can fail: with two questions at means (1, 2θ − 1), an exact-binomial test at level a rejects with probability 2{1 − (1 − a)^½} > a. Lemma 8 repairs it by testing at a/(1 + a), which changed the final round in none of the configurations run.

Running beside the multilevel audit that attains the Theorem 4 rate, the result is one audit with the minimax rate at no more than 32/31 of the paired audit's own cost, plus K answers (Corollary 11).

The evidence#

Stored pools with exact truth. The primary test bed is 185 held-out score pools from Weaver's public release (Weak-Verifier Ensembling). These are GPQA, MATH500, MMLU and MMLU-Pro questions answered by Llama-3.1-8B- and 70B-Instruct, 100 answers per question, each answer set scored by 19–27 reward models and verifiers. An audit draws with replacement from a question's stored answers, so every pool defines an exact answer law whose curve is computed in closed form, and every miss is visible. Each benchmark's questions were split once, before tuning. 26 audit configurations were compared on the development halves, the best was frozen, and the held-out pools use the other halves (250–360 questions each). The comparator on each pool is the cheapest of three certified audits chosen with hindsight on that pool, an optimistic denominator that favours the competition.

Table 2, reconciled against pdftotext -layout:

The audit is cheaper on all eight answer sets. It missed none of its 3,255 runs against the exact curves across all 217 pools. The competitors missed 17 times in 13,020 runs, all within their δ. A stratified betting sequence with per-question plug-in centering captures much of the saving, and the paired inequality takes the rest. The paired audit beats both per-row variants on 185/185 pools at every horizon, with median savings of 9%, 11% and 17% against the better one.

Where it loses, predicted in advance. The ten held-out pools where it loses at K = 64 are those with little between-question variance to remove: median within-question share 0.45 against 0.24 for the rest, Spearman 0.82 between that share and the cost ratio. The audit pays a start-up of two complete rounds (2KM answers), so the authors recorded a prediction before rerunning at other precisions: start-up dominates at coarse precision and fades at fine. At ε = 1/16 the paired audit loses on every held-out pool (median ratio 1.40). At ε = 1/64 it wins on 179 of 185 (median 0.51). The method's failure mode is cost, not coverage, and its own cost law says in advance when it will lose.

The cost law, used prospectively. Across 1,085 pool-horizon-precision settings, aKM + L(bK/ε + cΣw/ε²) fits measured cost with R² = 0.995 and a median relative error of 4.7%. Replacing Σw with the worst-case envelope K·max_k v̄_k drops R² to 0.906, so the tail sum is the right quantity. The decisive test was fitted before a new study generated any answer: N ≈ 2.16KM + 15.13K/ε + 12.88Σw/ε². Given the study's Σw = 2.57, computed from a separate reference stream, it predicted 78,656 answers. The audit used 79,133, and the prediction's resampled 5–95% range was 69,096–89,152.

A newly generated study. The protocol was fixed first: 100 MMLU-Pro questions in maths, physics, chemistry and engineering; the model gpt-6-luna at temperature 1, eight answers per request; the mean token log-probability of an answer as its verifier score; three audit streams and a separate reference stream. The model produced 716,384 answers for $17.24. Table 3, reconciled against pdftotext -layout:

The certified best-of-k curve costs 41% of the fixed exact-binomial design. Because the grader is a deterministic letter match, fewer than 400 distinct grader calls certify each curve. All 18 bands contain the reference curves at every budget.

What the bands say about selection#

The three curves on the same answers tell different stories, and the certification is what lets them be compared:

• pass@k climbs from 0.736 to 0.960. Its bands rule out every budget below 12 as a best budget in every stream.
• best-of-k, with the model's own log-probability as verifier, gains three points, from 0.736 to 0.767 on the reference curve.
• majority voting reaches 0.787, so plain consensus out-selects the log-probability verifier.
• In every stream the pass@k band at k = 64 lies at least 0.125 above the best-of-k band, so pass@64 exceeds best-of-64 by more than 12 points with probability at least 90%.

The sampler's coverage grew by 22 points and the selector captured 3. In the paper's words: "Most of what sampling could buy on these questions is out of the verifier's reach, as Stroebl et al. (2026) found for imperfect verifiers, and the bands certify it." That is the certified version of Selection Under a Submission Budget's pass@k-versus-n@k gap, and of the selector ceiling on Process vs Outcome Reward Models.

One reading the paper does not state: in Figure 10a, the best-of-k band at k = 1 overlaps the band at k = 64. At ±1/32, a certificate on this study cannot say that best-of-64 beats best-of-1. The paper shades ruled-out budgets only in the pass@k panel. When the gain a curve shows is smaller than 2ε, certifying the curve certifies that the gain is small, not that it exists.

The curves are flat where budgets get chosen. On the held-out pools the median curve comes within 1/32 of its best value by k = 10, 126 of 185 by k = 16 and 174 by k = 64. At K = 64 no curve among all 217 pools sits more than 1/32 below its best value up to 64. This must be read with the pools' own limit, which the paper states: a stored question has only 100 answers, so its top-scored answer appears with probability 0.47 at k = 64 and 0.92 at k = 256, and large budgets redraw a small set. On a 4,000-answers-per-question pool built from the MMLU-Pro reference stream, Σw stays at 12–16% of its worst case, and the paired audit's advantage still grows with K (0.46 / 0.38 / 0.33, no miss in 75 runs).

Read beside SELF-POT's selector replays (2026-10)#

SELF-POT (Yang et al., arXiv 2610.01110, empirical), compiled the same day, measures the selection gap from the other side. It uses few candidates (three), many models (five), strong and weak selectors on identical pools, and no certificate. The two papers agree on three points and differ in a way that is informative.

• Consensus is competitive with a model-based selector. Here majority voting (0.787) out-selects the model's own log-probability (0.767) on one MMLU-Pro answer set. In SELF-POT's maths, the model judging its own three candidates beats vote@3 by only 185 to 182 of 292 pools, with an interval spanning zero, at 12–21% more API cost. Two different model-based selectors, the same verdict: on these tasks a free consensus rule is about as good.
• The gap is the selector's, and an executable selector nearly closes it. This page's log-probability selector converts 3 of pass@k's 22 points. SELF-POT's public-example execution converts 453 of 457 covered coding pools. The certified result does not show that selection is inherently lossy. It shows that a weak selector is, which is the Stroebl et al. reading the paper itself gives, and SELF-POT supplies the strong-selector end of the same axis.
• A new loss this page's setup cannot see. The audit's selector is a deterministic score, so it always returns an answer. SELF-POT's judge is a model call that can fail to return one. That happened on 64 of 81 lost coding pools, and a fallback rule recovers 61 submissions. A curve certified over a scoring rule is silent about selectors that can fail to complete.

Where SELF-POT stops short of this page's standard. Its frontier figure is labelled "point estimates, not certified dominance relations." Its panel intervals are pointwise task bootstraps with "not multiplicity-adjusted" stated. Each cell is sampled once, so the within-question variance this page's Σw is built on is not estimated. Its Holm correction over 44 per-model sign tests is the only simultaneous control. With three budget points per protocol, the multiple-comparison risk of choosing a protocol after seeing the matrix is small next to a 64-point curve, but it is not zero. The paper's own reporting checklist (Direct operating point, coverage, per-stage outcomes, termination status) is the descriptive half of what a band adds the inferential half to.

Extensions, each with its scope#

• pass@k and majority voting are certified by the same paired audit unchanged; only the label count differs. A bounded-mean variant (the all-subsets audit) averages each path's outcome over all its k-subsets as a U-statistic. It needs every answer graded, so it costs more labels unless one grade serves every repeat of an answer.
• A population of questions. Audit a random panel of m questions as a fixed list and widen every radius by {log(2K/α)/(2m)}^½. The between-question price is then paid once, through m.
• Answers that depend on earlier ones (agents that revise, search or reuse context). Proposition 12 gives simultaneous bands for complete trajectories from one fixed policy, sized from any upper bound on how often the winner changes. It gives coverage and a sample size. It does not optimize acquisition.
• Unknown score percentiles. For one question under mean squared error, not knowing the score distribution costs exactly a factor 4/e ≈ 1.47 when generated answers are the bottleneck, and nothing to first order when labels are (Theorem 13).

What it is not: a forecast#

This page and Adaptive Stopping in Evaluation Sampling both make a measured curve cheaper. Neither predicts a curve at budgets nobody paid for, and the paper's calibration term says why a certified version of that prediction is impossible. A rare high-scoring answer could move θ_K, and only drawing about K/ε answers rules it out, at every law. Any distribution-free statement about the budget-K point costs on the order of K/ε generated answers, however regular the curve has looked so far. Forecasts exist (Kazdan et al. 2025 predict pass@k at large k from a beta-binomial fit; MARS stops parallel traces early). They buy cheapness with a modelling assumption, and the paper's verdict on them is one line: "these works report or predict curves; they do not certify them." The open question of forecasting a $10,000 result from $10 runs on Large-Scale Test-Time Compute therefore splits in two. A forecast must be model-based, and its error can only be checked by paying.

What is forecastable is the bill for the measurement. A rough Σw from a pilot or a reference stream, plugged into the cost law, predicted the audit's spend within 0.6% before any answer existed.

Against the other cost levers in the corpus#

The paired audit is the first method in the corpus to report a coverage number against known truth for an adaptive evaluation. It fails the way CollabEval fails, by costing efficiency rather than correctness.

Evidence notes#

• Tier. empirical holds: theorems with proofs, a frozen-protocol held-out evaluation against exact curves, and one prospective prediction. The authors are at a hospital AI lab and have no product or model in the comparison. Generative AI tools assisted with code, experimental design and analysis, literature review, figures and drafting, a disclosure stated in the paper.
• Held-out by question, not by model or benchmark. The development and held-out halves are the same eight Llama-3.1 answer sets split by question, and the 32 development-source pools are reported separately (median ratios 0.52 / 0.43 / 0.36). Every stored pool is single-turn QA or code with 100 answers per question.
• The comparator choices favour the competition. The per-pool minimum over three designs is chosen with hindsight, and the rank-based audit's 1,200-path calibration size was set after its Weaver outcomes were known. One provisional evaluation run of an earlier configuration completed during development, and its output was set aside unread until the final method was frozen.
• The new study is one model, one benchmark, 100 questions, one weak verifier. Two independence checks support the paths-independent-given-question assumption: within-request intraclass correlation of correctness is 0.005, and the audit and reference streams differ by 0.0022 in single-answer accuracy (paired t = 1.30).
• Agentic curves are outside the empirical work. Proposition 12 covers dependent trajectories in theory, for one fixed policy. Nothing was run on an agentic benchmark, where an "answer" is a trajectory and the 2KM start-up is the term that grows.

Connections#

• Large-Scale Test-Time Compute — the hub whose central object this page audits. Brown's thesis is that capability is a curve over budget; this page is the price of trusting one, and its calibration lower bound is why the hub's cheap-run forecasting question cannot be answered with a certificate
• Adaptive Stopping in Evaluation Sampling — the other adaptive cost lever, compared in the table above. optstop buys width and reports ~80% coverage at 94% nominal; the paired audit buys coverage and reports zero misses against exact truth. Both stop sampling what is already settled, optstop by items and this audit by budgets
• Compute-Controlled Benchmarking — the reporting rule this page completes. "Plot performance against budget" is step one. "Report a simultaneous band, not a curve, and choose budgets from it" is the step that makes a budget choice off the plot defensible
• Selection Under a Submission Budget — the generation–selection gap with a certificate: pass@64 exceeds best-of-64 by more than 12 points with probability at least 90% on the MMLU-Pro study, with a log-probability verifier capturing 3 of pass@k's 22 points. It also carries SELF-POT's uncertified counterpart: an executable selector converting 453 of 457 covered coding pools, and a model judge whose main loss is failing to return a choice
• Latent Capability Overhang — the coverage curve this page certifies as pass@k. The overhang is the distance between pass@k and what a selector keeps, and the calibration term is the formal reason its ceiling cannot be read off a cheap run
• Weak-Verifier Ensembling — the data. All 185 held-out pools are Weaver's public answer sets scored by its 19–27 individual verifiers, so this page's curves are single-verifier curves on Weaver's own benchmarks
• Process vs Outcome Reward Models — the selector ceiling seen from the measurement side: on the new study the model's own log-probability as verifier lifts best-of-k by three points while majority voting lifts it by five, so consensus out-selects the weak learned signal here
• Benchmark Score Redundancy — CollabEval is the other evaluation-cost method in the corpus that fails in efficiency rather than correctness; this page is the first to measure that property against exact truth for a whole curve
• UK AI Security Institute — named the "estimate high-budget performance from cheaper runs" problem; this page bounds what a certified answer to it can cost
• Release Certification under Evaluator Drift — a sibling betting-confidence-sequence audit for ship/no-ship decisions: a history-guided and a label-only expert mixed at 50/50, valid for any historical advice, reporting label ratios (0.465× / 0.740×) against the cheapest matched certified monitor

Open Questions#

• Does the paired audit's advantage survive an agentic evaluation, where each answer is a trajectory, M is small, per-answer cost is high, and the 2KM start-up is the dominant term? The stored-pool evidence is all single-turn QA and code, and Proposition 12 gives coverage for dependent trajectories without optimizing acquisition. Falsifiable by replaying a multi-attempt agentic eval log through the audit and the cost law.
• Can an audit learn the Γ allocation as it goes, without a separate pilot, and recover a meaningful share of the median 12× gap between Σw and Γ at practical precision? The paper names this as its open problem: the pilot that learns the allocation costs 179,200 answers at ε = 1/32, and Proposition 5 rules out a free version.
• Is the early plateau real? On the 100-answers-per-question pools the median best-of-k curve is within 1/32 of its best by k = 10, but large budgets there redraw the same small answer set. Does the plateau hold on pools with thousands of answers per question and a strong verifier?

Sources#

• Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves — Sohail (Neel) Sarkar & Shakuntala Baichoo (PMCC AI Lab, Peter Munk Cardiac Centre, University Health Network, Toronto), Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves, arXiv 2609.40190, 2026-09-30, 32pp, empirical (theory plus experiment). Used throughout: Proposition 1 (decisions from a band); §2's variance split and Σw; Proposition 2 and Theorem 4 with the three obstructions and the MMLU-Pro rate terms; Lemma 3 (nested winners); Proposition 5 and Theorem 6 (Γ, Σw/Γ median 12, the 179,200-answer pilot); §6, Lemmas 7–8, Theorem 9 and Corollary 11 (the paired audit and the unequal-means exact-binomial correction); §7 extensions including Proposition 12 and Theorem 13; §8 experiments; §9 related work (Kazdan, MARS, Stroebl, Miller, Fitas); and Appendix G (protocol, competitors, bootstrap misses, the MMLU-Pro protocol and independence checks). Parse note: PDF-derived (docling 2.126.0 / docling-mlx 0.1.1, confidence_grade: excellent, 5 tables, 10 pictures). Tables 2 and 3 were reconciled cell for cell against pdftotext -layout and match. Table 4's header is split in the raw (K = 64 | K = 64, with "/ queries" values pushed into a second column), but the values map correctly; it is not cited row-wise here. Tables 1 and 5 match. Figures 1 and 10 were viewed. The Figure 10a overlap reading is this page's own reading of the figure, not a claim the paper makes. Several displayed equations in §7.4–7.6 carry long runs of docling \ \ \ padding, which is cosmetic
• How Much Can Language Models Gain from Test-Time Computation? — Yang et al. (UIUC / UW / Tsinghua), arXiv 2610.01110, 2026-10-01, empirical. Cited only for the reconciliation section: maths judge 185 vs vote@3 182 (Table 16), public-example conversion 453/457 and the 64/81 no-choice losses (Tables 12–13), and the paper's own statements that its frontiers and intervals are pointwise and uncertified (Figure 6 caption, Appendix J). Full treatment and parse notes on Selection Under a Submission Budget