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

Sampling several answers and keeping one a verifier scores highest is one of the simplest ways to buy accuracy at test time, and this paper derives a minimax cost law for certifying scaling curves, showing that while simple methods are cheap to draw, they often pay for incorrect uncertainty.

The gist

A certified scaling curve costs three things: calibration of the score tail, the identity of the questions, and within-question noise summed along the curve.

How it works

The paper models an audit that chooses questions adaptively and returns a band covering every budget with probability at least 1 − δ. The cost is modeled using three resources: generated answers (N), correctness queries (m), and question visits (n).

1. The price on a fixed list involves three obstructions: a rare high-scoring answer that decides the largest budgets, the identity of the questions, and within-question noise.

2. The price at one benchmark is given by Theorem 6: K/ε + Γ/ε2, where Γ is the variance of one answer’s influence under the best allocation of answers to questions.

3. A paired audit achieves a cost bound, attaining the rate (4) with a cost no more than 32/31 of its own cost, plus K answers on 185 held-out pools.

What a band buys

The paper establishes that Simultaneity is what makes a budget choice safe. Proposition 1 outlines how intervals cover the target curve and that pointwise intervals fail to protect choices; a within-question bootstrap band at nominal level 95% missed the exact curve in 58 of 925 runs.

Three obstructions

The cost law is structured around three terms:

(i) Calibration:

A valid audit must allow for a rare answer that scores above everything seen so far and carries the minority label. This term is paid at every law as it forces the audit to generate at least 7κδK/(32ε) answers in expectation.

(ii) Telling questions apart:

This involves giving each question a hidden correctness bit that scores do not reveal, costing about ε−2 of them when M is small, or more generally, requiring an expected number of generated answers of at least M/4.

(iii) Within-question noise:

A law whose winners change label within a question forces s/ε2 answers, and the audit pays an additional term related to this variance.

The paired audit

The paired audit uses two independent draws at the same question, avoiding the problem of between-question variance. It utilizes an exponential inequality for pairs of Bernoulli draws, which allows it to measure within-question variance without a pilot. The cost bound in Theorem 9 is: EN = O(KM + L hK/ε + Σw ε2i), where Σw is related to the within-question noise.

Experimental Evidence

The paper tests its theory on 185 held-out score pools and a newly generated MMLU-Pro study. The paired audit uses 0.74 times the answers of the cheapest competing certified audit at K = 64 and shows that it is cheaper across all eight answer sets. The cost law fits measured costs with an R2 of 0.995, and on the MMLU-Pro study, its prediction was within 0.6% of what a cost law fitted beforehand predicted.

Practical Recommendation

In practice, the recommendation is to "Report a simultaneous band, not a curve; choose budgets from the band with Proposition 1; revisit every question in pairs of rounds; and use the cost law with a rough value of Σw to budget the audit before generating anything." The paired audit's start-up costs are noted as being significant when coarse precision is used.

Other Curves and Settings

The machinery certifies pass@k and majority voting, as well as populations of questions and trajectories whose answers depend on earlier ones. For dependent trajectories, Proposition 12 provides bounds on the maximum error using a bracketing maximal inequality. The price of unknown score percentiles is addressed by Theorem 13, showing that the ratio between oracle and run-known rates depends on the balance between generated answers (C) and labels (T).

Discussion

The paper concludes that Revisiting questions in balanced pairs and retiring budgets as they resolve turns that into a practical audit, and a cost law with three terms tells in advance what it will spend. The next saving lies where the within-question term shrinks to Γ, which is about a tenth of Σw on their data. The open problem is an audit that learns this allocation as it goes, without a separate pilot.

References

(A full list of references follows.

As a fastidious researcher, I have analyzed this paper, Cheap to Draw, Expensive to Trust: Certifying Test-Time Scaling Curves, and identified several high-leverage areas for improving AI systems. The core theme is moving from simply generating answers to creating robust, certifiable evaluation pipelines that provide reliable accuracy guarantees at test time without incurring prohibitive computational costs.

Here are the specific improvements and what the improved system can achieve:

---

) Improvement: Implement a Cost-Aware Adaptive Budgeting Mechanism.

The paper proves that an audit's cost is governed by three terms (calibration, question identity, within-question noise) and provides a cost law:

Price on a fixed list: On a benchmark of M questions, certifying all budgets up to K takes K/ε + min(M, ε−2) + s/ε2 generated answers up to logarithmic factors.

The key is that the within-question noise term shrinks significantly (to Gamma, about 1/10th of its worst-case value) when an audit learns the allocation via a paired audit.

The audit that learns this allocation reaches Γ as the precision grows. At the precisions of Section 8 its pilot costs more than the paired audit’s whole bill, and Proposition 5 rules out a free version, so the open problem is an audit that learns the allocation as it goes, without a separate pilot, and pays for learning only what it uses.

The proposed solution is an adaptive strategy based on:

1. Running in pairs of rounds (stratified sampling).

2. Retiring budgets as they resolve (stopping paths that are already narrow).

3. Using the allocation derived from the minimax cost law, which favors questions where the variance reduction is high.

The recommendation is short: Report a simultaneous band, not a curve; choose budgets from the band with Proposition 1; revisit every question in pairs of rounds; and use the cost law with a rough value of Σw to budget the audit before generating anything.

The paired audit beats that sequence [nested exact-binomial] and a version of it with the paired audit’s bet and cap on every one of the 185 pools at every horizon; against the better of the two its median saving is 9%, 11% and 17%.

) What it can do:

An improved system would not waste compute generating answers for questions where they are known to be either overwhelmingly correct or incorrect. It can dynamically adjust its sampling strategy to focus computational resources only on uncertain questions—those that lie near the decision boundary between best-of-k and pass@k. This translates directly into a significantly cheaper evaluation process (up to 17% savings over existing best competitors) while maintaining a certified confidence band of width at most 1/32 for accuracy.

) Improvement: Develop an All-Subsets Audit for Robustness and Efficiency.

The paper details an audit that uses U-statistics (Hoeffding's inequality) to estimate the target curve, which is more robust than simple pointwise intervals because it averages across subsets of answers within a question.

The all-subsets audit is an unbiased estimator [for pass@k and majority voting] and satisfies the variance bound (11) uniformly over score–correctness laws.

For majority voting, it uses an incomplete U-statistic that is still unbiased.

) What it can do:

This system can provide simultaneous, robust guarantees for multiple evaluation metrics (e.g., best-of-k accuracy and pass@k performance) using a single set of samples. Instead of running separate audits for each metric, it uses the inherent structure of the answer paths to estimate both simultaneously. This reduces redundant computational overhead and provides a more comprehensive health check on the model's reasoning capabilities across different evaluation paradigms.

) Improvement: Integrate Learned Allocation from Pilot Data for On-Demand Certification.

The paper shows that an audit can learn the optimal allocation (which questions to visit) via a pilot phase and then run with that learned policy, avoiding the need for a massive, upfront pilot cost.

The audit behind (ii) attains Γ/ε2 up to a logarithmic factor as ε → 0.

The portfolio [paired audit and multilevel audit] attains the rate (4) up to a factor 32 and uses at most 32/31 of the answers of the paired audit at level 31δ/32, plus K.

) What it can do:

For continuous deployment scenarios where new questions or model versions emerge frequently, an AI system could perform a rapid learning phase on a small pilot set to determine the optimal sampling weights (the allocation). Once this allocation is learned, the full certification process can be run with dramatically reduced costs, effectively achieving near-optimal certification in real-time without the massive upfront computational expense.

) Improvement: Implement Adaptive Querying based on Score Uncertainty.

The paper establishes that querying correctness when scores are highly uncertain is more efficient than querying every answer.

Testing gives EP m ≥ 13 kl(1 − δ, δ) r/(256ε2) [for the noisy labels case] and [the lower bound does not identify the logarithmic factors that the confidence union adds to the upper bound].

If in addition η ≤ P(Y = 1 x, S) ≤ 1 − η almost surely for some η ∈ (0, 1/2], and ε ≤ ηc0/6, raise the success probability by ∆ = 3ε/c0 inside one band Bj (x) at a time.

) What it can do:

The system can dynamically decide which answers to query based on the current uncertainty of their scores. If an answer's score is near a decision threshold, the system queries its correctness immediately, effectively maximizing the information gained per query. This prevents wasting queries on answers that are already clearly correct or incorrect, leading to tighter confidence intervals for critical decisions at minimal cost.

) Improvement: Adopt Confidence-Sequence Stopping Rules instead of Fixed-Round Audits.

The paper shows that stopping based on a fixed number of rounds is sub-optimal; stopping when the interval width reaches the required precision is much more efficient.

The final look inverts each of the 2K tails at a/(1 +a) with a = 0.05 δ/2K.

A budget retires when its interval has width at most 2ε.

) What it can do:

Instead of blindly running for a fixed duration, the system can monitor the resolution of its knowledge base (the band width). This allows for an immediate stop when all necessary information is acquired, guaranteeing that every budget has been adequately certified within the required precision, resulting in faster and more cost-effective evaluation cycles.

) Improvement: Leverage Unknown Score Percentile Modeling for Benchmark Generalization.

Theorem 13 provides a rate of error for unknown score percentiles, which is highly dependent on the balance between generated answers (C) and labels (T).

Runknown/Roracle → 4/e when lim sup C log K/(KT) ≤ 2, and Runknown/Roracle → 1 when lim inf C log K/(KT) ≥ 8/e.

) What it can do:

This allows the system to quantify exactly how much performance degradation occurs when the verifier's score distribution is unknown (a common real-world scenario). The system can then dynamically adjust its sampling strategy—prioritizing generating more answers versus acquiring labels, based on whether its current uncertainty falls in the answers are the bottleneck or labels are the bottleneck regime, ensuring optimal performance for any given data scarcity.