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

arXiv: https://arxiv.org/abs/2609.40190 · HTML: https://mlsanity.com/paper/2609.40190/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 23 of 23)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Prediction-Powered Inference](https://mlsanity.com/paper/2301.09633/) (2023)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Adding Error Bars to Evals: A Statistical Approach to Language Model Evaluations](https://mlsanity.com/paper/2411.00640/) (2024)
- [Active Testing: Sample-Efficient Model Evaluation](https://mlsanity.com/paper/2103.05331/) (2021)
- [The Limits of Inference Scaling Through Resampling](https://mlsanity.com/paper/2411.17501/) (2024)
- [Dynamic Scaling of Unit Tests for Code Reward Modeling](https://mlsanity.com/paper/2501.01054/) (2025)
- [Efficient Prediction of Pass@k Scaling in Large Language Models](https://mlsanity.com/paper/2510.05197/) (2025)
- [Show Your Work with Confidence: Confidence Bands for Tuning Curves](https://mlsanity.com/paper/2311.09480/) (2023)
- [CELEUS: Certifiable and Efficient LLM Evaluation via E-Processes](https://mlsanity.com/paper/2606.20820/) (2026)
- [MARS: Margin-Adversarial Risk-controlled Stopping for Parallel LLM Test-time Scaling](https://mlsanity.com/paper/2606.12935/) (2026)
- [Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation](https://mlsanity.com/paper/2410.14643/) (2024)
- [Sharp Matrix Empirical Bernstein Inequalities](https://mlsanity.com/paper/2411.09516/) (2024)
- [The geometry of AI validation: From structural blindness to reusable audits](https://mlsanity.com/paper/2608.21496/) (2026)

## Abstract (arXiv)

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 ±1/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.