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

1 Introduction

• For a fixed list, the minimax generated-answer cost has three terms: score-tail calibration, distinguishing questions, and within-question noise summed along the curve.Each term has a matching lower bound; the first is paid under every law.Source: §1 · p. 2
• At one benchmark, every valid audit pays K/ε + Γ/ε^2, while an audit learning the best answer allocation attains the Γ/ε^2 term up to a logarithmic factor as precision grows.At fixed precision, no audit is optimal for every benchmark.Source: §1 · p. 2
• Two fresh paths per question and an exponential inequality for paired Bernoulli draws yield anytime-valid simultaneous bands without a pilot.A corrected exact-binomial final look stops the audit at a fixed round.Source: §1 · p. 2
• The same machinery covers pass@k, majority voting, question populations, and trajectories whose answers depend on earlier answers.With unknown score percentiles, a single question’s minimax mean squared error is asymptotically 4/e times its known-percentile value when generated answers are the bottleneck.Source: §1 · p. 2
• 0.74, 0.66, and 0.53 times the cheapest competing certified audit’s answers at K=64, 256, and 1,024; none of 3,255 runs missed the exact curves.The paired audit was cheaper on all eight generator–benchmark answer sets.Source: §1 · p. 2
• A cost law fitted before a new study predicted its bill within 0.6%.Source: §1 · p. 2

2 The problem

• At each question, independent answers carry a verifier score and correctness bit; the curve records correctness of the highest-scored answer among the first k answers.The score may come from a reward model, unit tests, or the model’s mean token log-probability.Source: §2 · p. 2
• Pass@k counts a question solved if any of its first k answers is correct; majority voting uses the most frequent valid answer, with plurality ties broken uniformly and no valid answer counted incorrect.Source: §2 · p. 2
• A valid audit returns intervals of width at most 2ε that cover every budget with the required probability.Simultaneous coverage makes a budget choice after inspecting the band safe; pointwise intervals do not.Source: §2 · pp. 2–3
• The audit tracks generated answers, correctness queries, and question visits; answers usually dominate because each requires a model forward pass.The stated default settings are δ = 0.05 and ε = 1/32.Source: §2 · p. 3
• For a question drawn uniformly from the benchmark list, selected-answer variance splits into within-question and between-question parts; balanced visits avoid paying for the latter.At MMLU-Pro, the summed within-question variance was 2.57 versus a worst case of K/4 = 16 at K=64.Source: §2 · p. 3

3 Fresh questions: the population price

• Each fresh path starts at a population-drawn question, so every draw carries between-question variance.Source: §3 · p. 3
• Generation costs about K answers per question because the largest budget requires a full path; correctness labels are needed only at score records, about log K per path.The number of questions pays an additional log log K factor for simultaneous coverage over budgets.Source: §3 · p. 4
• Winners at budgets k and ℓ coincide unless the best of the first ℓ answers occurs after position k, an event bounded by 1 − k/ℓ.Consequently, budgets within a factor e r^2 move together within r in root mean square, and chaining adds a log log K price for the supremum.Source: §3 · p. 4

4 A fixed list of questions

• Exchanging the unshared parts of two overlapping path blocks preserves the path law and gives the nested-winner coupling behind controlling differences across budgets.For budgets a ≤ k ≤ 2a, the winners of the whole path and its blocks are used to bound disagreement.Source: §4 · p. 4
• Budgets a factor two apart differ by at most the smaller budget’s within-question noise, so between-question variance does not enter this bound.Source: §4 · p. 4
• The fixed-list cost has three obstructions: rare high-scoring answers that affect large budgets, identifying question correctness, and within-question winner noise.Separate constructions force each cost, and within-question noise also forces correctness-label queries.Source: §4 · p. 5
• On the MMLU-Pro study at K=64, the three rate terms were 2,048, 100, and 2,628; the measured within-question variance was six times smaller than its worst case.These are rate terms rather than a predicted bill; logarithmic factors and audit start-up multiply them.Source: §4 · p. 5
• The multilevel audit estimates θ1 and adds dyadic path corrections that telescope to θk − θ1; stopping each level on its own makes sample size track its variance.Summing level variances yields the within-question tail sum Σw.Source: §4 · p. 5

5 One benchmark at a time

• No audit is optimal at every law at fixed precision: some correctness tables can be checked with about log(2/δ)/ε labels, while no single audit is that cheap for every table.The construction gives a law where another valid audit uses q answers, queries, and visits, while the given audit requires at least M/4 of each in expectation.Source: §5 · pp. 5–6
• Theorem 4 gives a price for classes of laws, whereas the fixed-benchmark result gives a law-specific lower bound and an allocation that attains its leading term.At fixed precision, the best audit can depend on the correctness table.Source: §5 · pp. 5–6
• Γ is the smallest worst-budget variance per answer under an allocation across questions, while Σw/Γ measures the cost of reading one winner per path and visiting questions equally.For the MMLU-Pro study, the optimal allocation puts 90% of answers on 23 questions.Source: §5 · p. 6
• Every valid audit at a fixed law pays at least (κδ/128)(K/ε + Γ/ε2), and an audit matches the leading Γ/ε2 term up to 4 log(2K/δ)/κδ as ε → 0.The attainable allocation gives question x answers in proportion to {P_k λ_k v_k(x)}^1/2 for a least-favorable budget mixture.Source: §5 · p. 6
• On the MMLU-Pro study, Γ = 0.28 against Σw = 2.57, and the median Σw/Γ across held-out pools is 12.The interquartile range is 8.4 to 21.9; at ε = 1/32, the allocation-learning pilot alone would use 179,200 answers.Source: §5 · p. 6

6 The paired audit

• Two independent draws at the same question have squared difference with mean exactly twice the within-question variance, so the paired penalty needs no estimated center or correction term.This lets within-question variance enter the band from the first pair.Source: §6 · pp. 6–7
• Paths grow only to the largest unresolved budget, and a budget retires once its interval is narrow enough; the final exact-binomial look corrects for unequal question means.The final round is the smallest even number of rounds at which every possible count gives an interval of width at most 2ε.Source: §6 · pp. 7–8
• The paired audit gives simultaneous coverage of at least 1 − δ for every answer law and stops by a deterministic round cap, with generated-answer cost shaped by K/ε + Σw/ε2.The bound includes a 2L factor, where L is logarithmic in K, 1/ε, and 1/δ.Source: §6 · p. 8
• On the MATH500 stored run, the audit stopped after 12 rounds with 127,500 answers, and its band covered the exact curve.The run traced 250 questions and K = 64; budgets retired at different times as paths shrank.Source: §6 · p. 8, Figure 4 · p. 9
• Running the paired and multilevel audits side by side preserves the rate everywhere; with ρ = 1/32, the portfolio uses at most 32/31 of the paired audit’s answers at level 31δ/32, plus K.The bound is for generated answers.Source: §6 · pp. 9–10

7.1 Pass@k and majority voting

• Pass@k and majority voting fit the path-outcome audit; all-subsets handles bounded subset averages, while pass@k also admits first-success stopping and a DKW band.All-subsets requires correctness labels for every answer on the path, whereas first-success stopping for pass@k needs correctness only through the first success.Source: §7.1 · p. 10

7.2 One grade per distinct answer

• Reusing deterministic grades for repeated question–answer pairs leaves bands, coverage, and answer counts unchanged while reducing distinct grader calls; MMLU-Pro curves used fewer than 400 calls.Source: §7.2 · p. 10

7.3 A population of questions

• A sampled panel of m questions extends fixed-list bands to a population by adding a radius to every budget; the population-sampling cost is paid through m.The widened band covers the population curve with probability at least 1 −δ −α.Source: §7.3 · p. 10

7.4 Answers that depend on earlier answers

• For dependent paths, independent complete trajectories yield simultaneous bands without within-path independence, but acquisition is unoptimized and the guarantee covers one fixed policy.A complete trajectory costs K answers and, when generation needs no labels, at most its number of records in queries.Source: §7.4 · pp. 10–11

7.5 The price of unknown score percentiles

• 4/e ≈1.47 is the asymptotic price of unknown percentiles when generated answers are the bottleneck; when labels are the bottleneck, knowing percentiles is worth nothing to first order.An estimator using only the observed score order attains the unknown-percentile rate.Source: §7.5 · p. 11, Figure 5 · p. 12

7.6 Spending labels when percentiles are known

• The fixed-width proposal saves 8.50% and 4.74% of the envelope proposal’s labels, and 3.26% and 11.68% versus the variance-optimal proposal on two complete pools.The variance objective can have several near-minimizers with different label counts; the reported variance-optimal proposal is the one returned by the solver.Source: §7.6 · p. 12

8.1 Stored score pools

• The median held-out curve came within 1/32 of its best value by budget 10; 174 of 185 did so by budget 64.Across all 217 stored pools, none was more than 1/32 below its best value over budgets up to 64.Source: §8.1 · p. 12

8.3 Where the saving comes from

• The paired inequality added savings beyond stratified betting: against the better betting variant, median savings were 9%, 11%, and 17% at the three horizons.Balanced rounds alone did not help exact-binomial looks, which cost essentially the same as random rounds.Source: §8.3 · p. 13

8.4 When the audit loses, and why the saving grows

• At ε = 1/16 the paired audit lost on every held-out pool (median ratio 1.40), but at ε = 1/64 it won on 179 of 185 (median 0.51).Its ten losses at K = 64 had a higher median within-question variance share than the other pools, 0.45 versus 0.24; that share correlated with cost ratio at 0.82.Source: §8.4 · p. 13
• On a pool with 4,000 answers per question, the paired-audit cost ratio fell from 0.46 to 0.33 as K rose from 64 to 1,024.In the stored 100-answer pools, the top answer’s appearance probability rises with budget, and Σw falls from 24% to 6% of its worst case.Source: §8.4 · p. 13

8.2 The held-out comparison

• At least 173 of 185 held-out pools favored the paired audit at every horizon, and it was cheaper on all eight answer sets.It missed none of 3,255 runs against exact curves; competitors missed 17 times in 13,020 runs, all within their δ.Source: §8.2 · p. 13, Table 2 · p. 14

8.6 A newly generated study

• 79,133 answers—41% of the fixed exact-binomial design—certified best-of-k, at $1.91 versus $4.61 in generation cost.All 18 bands contained the reference curves at every budget; pass@k rose from 0.736 to 0.960, while best-of-k rose from 0.736 to 0.767.Source: §8.6 · pp. 14–15, Table 3 · p. 15, Figure 10 · p. 16

8.5 The cost law

• 78,656 answers were predicted before the MMLU-Pro study, versus 79,133 used; the prospective cost law had R2 = 0.958.Across 1,085 pool, horizon, and precision settings, the three-term law fit had R2 = 0.995, while replacing the tail sum with its worst-case envelope reduced R2 to 0.906.Source: §8.5 · p. 14, Figure 9 · p. 16

Test-time scaling

• Pass@k, best-of-n selection, and majority voting have been studied as ways to trade computation for accuracy, but those works report or predict curves rather than certify them.Verifier errors have also been shown to bound the gains from resampling, motivating the importance of budget choice.Source: §9 · p. 17

Statistics of model evaluation; Sequential inference and sampling design

• Prior evaluation methods address population accuracy, a single score, or best-score tuning, rather than correctness of a verifier’s choice along a whole generated-answer curve.The related work also connects the paper’s tools to confidence sequences, paired variance estimation, stratified allocation, multilevel Monte Carlo, U-statistics, and record theory.Source: §9 · p. 17

The closest work

• Fitas (2026) studies simultaneous bands for a population of questions, whereas this paper’s fixed-list results have no counterpart there.Its population results establish generated-answer costs proportional to N and discuss the logarithmic cost of labels.Source: §9 · p. 17

10 Discussion

• A fixed-benchmark curve costs score-tail calibration, identifying questions, and within-question noise summed along the curve; balanced paired revisits avoid paying between-question variance.The measured within-question sum is only a fraction of its worst case, and a three-term cost law can forecast audit spending.Source: §10 · p. 17
• At a single benchmark, the within-question term sharpens to Γ, about a tenth of Σw in the reported data, and learning the allocation attains Γ as precision grows.At the study precisions, the pilot costs more than the paired audit’s full bill; the open problem is to learn allocation without a separate pilot.Source: §10 · p. 17
• The fixed-list target covers listed questions; population inference restores between-question variance, and the results for dependent trajectories apply to one fixed generation policy.The paired audit’s two-round start-up can make it lose at coarse precision on a large benchmark.Source: §10 · p. 17
• The practical recommendation is to report simultaneous bands, choose budgets from them, revisit questions in paired rounds, and use a rough Σw to budget before generating answers.The 100-question MMLU-Pro best-of-k band cost $1.91 in generation.Source: §10 · pp. 17–18

Appendix; A Proofs: conventions

• The appendix contains proofs in Appendices A–F and experimental details in Appendix G; the proof conventions frame audit lower bounds as transcript-divergence tests.For laws differing only in answer distributions, transcript divergence is bounded by the expected answer counts at each question times the corresponding KL divergence.Source: Appendix · p. 20, A Proofs: conventions · p. 20

B Proof of Proposition 2

• The proof assumes a known fixed list of M equally weighted questions and targets the population-average selected-answer correctness curve.A valid audit must cover every budget simultaneously with probability at least 1−δ.Source: B Proof of Proposition 2 · p. 20

B.1 A hard family

• Disjoint score bands encode independent correctness signs, and accurate curve estimates recover those signs by rounding.The hard family uses sign-specific Bernoulli correctness within each band and fair correctness elsewhere.Source: §B.1 · p. 20

B.2 Correctness queries

• Adaptive correctness-label queries still require enough labels to decode all band signs under the deterministic cap.The lower-bound argument permits adaptive allocation and stopping.Source: §B.2 · p. 20

B.3 Question visits

• Even revealing every bit at each visited question leaves a lower bound on the number of question visits needed to distinguish all coordinates.An actual audit sees no more information per question than this strengthened experiment.Source: §B.3 · p. 21

B.4 Generated answers

• A hard band near the top-score tail yields an Ω(Kε^-2 log(1/δ)) generated-answer lower bound without an extra log J factor.One stream of generated answers visits all hard bands at once.Source: §B.4 · p. 21

B.5 The record audit

• The record audit uses deterministic caps of O(ε^-2 log(J/δ)), O(Jε^-2 log(J/δ)) correctness queries, and O(Kε^-2 log(1/δ)) generated answers.Its record indicators remain independent with fixed path lengths, and the analysis incurs no hidden log log K.Source: §B.5 · pp. 21–22

C.1 The upper bound

• The upper-bound audit combines a first-budget estimate with corrections across logarithmic budget levels, attaining both answer and query bounds without knowing v or s.Adding the level intervals gives half-width ε simultaneously at every budget, including budgets between powers of two.Source: §C.1 · pp. 22–23

C.2 Lower bounds on generated answers

• A rare high-scoring answer forces an Ω(K/ε) generated-answer calibration cost at every law, while within-question noise can separately force Ω(s/ε²).When s < 8Kε, the calibration bound already covers the within-question term.Source: §C.2 · p. 23

C.3 Lower bounds on correctness queries

• For arbitrary laws, the lower-bound construction changes labels only within disjoint winner-score bands, so each band contributes to the required query count.Source: §C.3 · p. 24
• At continuous-score laws, disjoint score bands yield an Ω(HK/ε) correctness-query lower bound, while a shared law can force both this label cost and the s/ε² answer cost.The label bound counts queried answer occurrences; distinct grader calls are a different resource when a deterministic grader serves repeated answers.Source: §C.3 · p. 24

D.1 Part (i)

• At a fixed benchmark, the lower-bound argument establishes a cost of order K/ε + Γ/ε² for every valid audit.It treats separately the regimes where Γ is large or small relative to εK, using the variance lower bound or the calibration bound.Source: §D.1 · p. 25

D.2 Part (ii)

• A pilot estimates influence variances and selects an allocation; the resulting audit attains the Γ cost up to logarithmic factors as precision grows.The pilot answers and labels are charged, and the allocation is the Neyman allocation for a least-favorable mixture of budgets.Source: §D.2 · p. 26

D.3 Part (iii)

• The conditional influence variance is bounded below by v_k(x)/k and above by p_k(x){1−p_k(x)}, so v_k(x) ≤ k/4.Source: §D.3 · p. 26

D.4 Computing Γ

• On the first 4,000 MMLU-Pro reference answers per question at K = 64, Γ is bracketed at [0.27961, 0.27961]; held-out pools show median Σw/Γ of 12.0.The held-out ratio has interquartile range 8.4 to 21.9.Source: §D.4 · p. 26

• Once n ≥ 20M + 4,000,000 z_k(t+L)/ε², the paired audit’s radius is at most ε simultaneously over budgets with probability at least 1−ε.Rounding to a whole pair adds fewer than 2M rows.Source: E Proof of the cost bound of Theorem 9 · p. 27
• The proof’s constant is loose and does not enter the intervals; answer generation stops when no budget remains active at that position.Source: E Proof of the cost bound of Theorem 9 · p. 27
• Changing the bet cap below 0.95 or between 0.95 and 1 changes constants but leaves the order of the cost bound unchanged.Source: E Proof of the cost bound of Theorem 9 · p. 27

F Proof of Theorem 13

• The answer-limited risk has lower bound (1−o(1))K/(8C), while the unknown-experiment answer construction gives (1−o(1))K/(2eC).Both lower bounds also hold under deterministic caps.Source: F Proof of Theorem 13 · p. 28
• The complete-pool estimator averages selected labels over all subsets of size k, is unbiased for θ_k, and has a variance bound uniform over score–correctness laws.Its variance analysis retains all overlap orders rather than relying on a fixed-k first-projection approximation.Source: F Proof of Theorem 13 · pp. 28–29
• In the label-limited region, the unknown and oracle experiments have equal risk to first order under deterministic label caps.Source: F Proof of Theorem 13 · p. 30

G.1 Stored score pools

• The stored pools comprise finite question-specific sets of scored and graded answers, sampled with replacement to define exact answer laws, including ties.The 185 held-out pools are Weaver evaluation halves; the other 32 pools are from sources seen during development and are reported separately.Source: §G.1 · p. 30

G.2 Protocol

• The paired-audit settings were selected among 26 configurations on Weaver development halves and then frozen for evaluation.Evaluation used five independent audits per pool and horizon at ε = 1/32 and δ = 0.05; the per-pool cheapest-competitor denominator is optimistic.Source: §G.2 · p. 30

G.3 Competing certified audits

• The six comparators include completion and nested exact-binomial stopping, rank-based stopping, fixed Hoeffding or exact-binomial paths, and Fitas's record design.The first four designs draw questions uniformly at random, and all designs target simultaneous half-width ε coverage 1 − δ at every budget.Source: §G.3 · p. 31
• At K = 64 and 256, the cheapest of all six designs was among the three prespecified comparators on every held-out pool.At K = 64, within-question bootstrap bands missed in 58 of 925 runs (6.3%), while the fixed Hoeffding design missed in none of 370 runs.Source: §G.3 · p. 31

G.4 Ablation

• The ablation compares balanced exact-binomial and per-row betting variants with paired-audit settings on stored pools.The held-out paired and per-row costs are reproduced exactly.Source: §G.4 · p. 31, Table 5 · p. 32

G.5 The all-subsets audit

• The all-subsets audit uses an initial zero-bet round to set predictions, and its unbiasedness requires answers within a path to be independent given the question.It splits error between a betting sequence and a fixed-round exact-binomial look on each full path's binary outcome.Source: §G.5 · p. 31

G.6 The cost law

• 12.0% was the cost law's 90th-percentile relative error across settings; a law fitted before the MMLU-Pro study predicted its bill within 0.6%.The earlier law was fitted before any answer from that study, including pilot answers, was generated.Source: §G.6 · p. 32

G.7 The MMLU-Pro study

• Across 100 MMLU-Pro questions, audit-stream single-answer accuracy differed from the reference stream by 0.0022 on average, and within-request correctness ICC was 0.005.The study used 716,384 answers; 5.2% had no valid letter and 12 were truncated.Source: §G.7 · p. 32

G.8 Computation

• A paired audit of R rounds runs in O(N + RMK) time with O(MK) working memory; all six audits' 3,255 stored-pool jobs took 936 seconds on one CPU with eight workers.Updating active budgets after a pair of rounds takes O(MK) operations.Source: §G.8 · p. 32