Test-Time Scaling Depends on Verifying Rare Correct Answers

Azalia Mirhoseini frames inference scaling as a third lever in language-model development, alongside pre-training and fine-tuning. Pre-training historically consumes the most time, data, and GPU capacity; fine-tuning uses far less data. Inference has conventionally been treated as a cheap, one-shot exchange between a user and a model. The alternative is to spend substantial computation after a query arrives—potentially offline—without changing model parameters or fine-tuning it further.

But the practical sequence is not simply “spend more tokens.” First ask whether the task has a reliable way to judge candidate outputs. Then consider problem difficulty and the task’s tolerance for cost and latency. Only after those constraints are clear does it make sense to decide whether to buy capability through parallel sampling, sequential revision, guided search, or a more elaborate multi-model workflow.

The basic repeated-sampling mechanism has two distinct jobs. Given a problem, generate many candidate solutions, then use a verifier to identify a correct one:

1. Coverage: generate at least one correct solution.
2. Precision: recognize the correct solution among the candidates.

This distinction is decisive. A model that fails on its first attempt may still place a correct solution somewhere in its output distribution. Mirhoseini’s account of the Large Language Monkeys results is that smaller models can surpass stronger single-attempt systems when sampled enough times and paired with accurate selection. The lecture’s benchmark charts show Llama-3 8B and 70B, under repeated sampling with oracle verification, exceeding GPT-4o’s single-attempt performance on formal proofs, coding contests, MATH, and GSM8K.

The same logic applies to agentic coding. On SWE-bench Verified, the displayed coverage curve rises with the number of samples and crosses the lecture slide’s marked 62.2% state-of-the-art result as of December 13, 2024. The slide reports more than 70% coverage from open-source DeepSeek with repeated sampling. In a domain where unit tests can identify successful patches, repeated attempts can become an end-to-end method for producing a more capable system rather than merely a larger pile of possible answers.

The appeal is especially strong for organizations that cannot pre-train frontier-scale models. Rather than paying the up-front cost of building a larger base model, they can use a smaller or open model, allocate a larger per-problem inference budget, and let it keep generating or refining candidates. Mirhoseini presents that tradeoff as viable where output quality justifies the additional cost and latency—and especially where work can run offline.

Repeated sampling is not presented as an unstructured heuristic. Mirhoseini says coverage—the share of problems with at least one correct sampled output—follows an exponentiated power-law relationship with sample count: $c=\exp (a{k}^b)$.

Here, $k$ is the number of samples, $c$ is coverage, and $a$ and $b$ are fitted parameters. The operational value is predictive: estimate the curve for a model and task, then estimate how much inference compute is needed to reach a target coverage level rather than sampling blindly.

The lecture shows fitted curves across Pythia models from 70 million to 12 billion parameters, Gemma variants, and Llama-3 models up to 70 billion parameters, on MATH, CodeContests, and MiniF2F-MATH. Mirhoseini emphasizes that the pattern appears even in a 70-million-parameter model. Test-time scaling is therefore not confined to frontier models, although the useful budget and curve shape vary by model and domain.

The aggregate law is initially counterintuitive because a single problem behaves differently. If a model has one-shot success probability ${\mathrm{pass}}_i@1$ on problem $i$, repeated independent attempts yield ${\mathrm{pass}}_i@k=1-(1-{\mathrm{pass}}_i@1{)}^k$. For an individual problem, the chance of at least one successful attempt rises rapidly as attempts accumulate. Across a benchmark, however, average coverage follows the displayed power-law-like curve.

The explanation presented from How Do Large Language Monkeys Get Their Power (Laws)? is that a long tail of extremely hard problems is necessary and sufficient for that aggregate behavior. Many questions are easy enough to solve at pass@1. Others have progressively lower odds of being solved by any one draw. At the hard end, the correct answer may appear only rarely. Individual problems with a meaningful chance of success improve quickly, but the long tail keeps yielding additional solved problems as the sampling budget rises. That is what stretches the benchmark-level curve.

The lecture’s accompanying histogram slide reports an empirical shortcut: estimating the distribution of pass@1 across problems can predict the power-law exponent with roughly two to four orders of magnitude less inference compute than directly measuring a full high-sample regime.

This motivates a different allocation model. Mirhoseini contrasts an older pattern—more than $100 million on pre-training, much less on fine-tuning, and less than a tenth of a cent per inference call—with a setting in which an inference run might consume $1,000 or more in compute. For valuable, offline, and verifiable work, that can be a rational exchange: inference expenditure becomes a way to purchase higher capability after deployment.

Coverage is not system success. A correct output has no value to a system if it cannot be recognized.

Mirhoseini describes the central limitation as a generation-verification gap: models may generate good responses, while the available selector fails to capture them. Oracle coverage asks what would happen if a system could always identify a correct candidate whenever one had been generated. Practical methods instead rely on mechanisms such as majority vote or reward-model ranking.

Some domains offer strong automated verifiers. Formal proof tools can check whether a proof obeys required rules. Coding systems can run unit tests. In AI-as-a-compiler work, a model can generate lower-level CUDA code from a PyTorch program, then compare their outputs over inputs to assess whether the implementation behaves equivalently.

Mirhoseini uses KernelBench, a benchmark for generating GPU kernels, as an example. The displayed result for its 87 Level 1 problems shows correctness coverage scaling log-linearly with sample count. The advantage is not merely that CUDA generation benefits from more attempts; the source PyTorch program supplies an automatic basis for testing generated code. Similar opportunities can arise in programming-language translation, where behavioral equivalence may be easier to test than it is to produce the translated implementation.

Where no dependable verifier exists, the gap becomes large. Majority vote selects the most common answer. Reward-model approaches score candidates and select the highest-ranked response. On the MATH and GSM8K results presented in the lecture, these practical methods trail oracle coverage, and the gap is larger on harder problems.

The reason is distributional. On a difficult problem, a correct solution might occur once, twice, or a few times among thousands of generations. Incorrect answers can be much more frequent even though one rare candidate is right. Majority vote rewards recurrence, not correctness. It can work on simpler questions, where correct outputs recur reliably, but is poorly matched to a needle-in-the-haystack regime.

The lecture identifies several possible ways to narrow the gap: use simulations or tools to filter incorrect answers, use another model as a selector, or ensemble multiple verifiers. Mirhoseini notes that weakly supervised verifier ensembling is a research direction, while also stressing the substantial compute cost of expanding the verifier ensemble.

Test quality is part of the same constraint. Flaky tests, false negatives, incomplete coverage, and inconsistent test construction can turn apparent verification into false confidence. Mirhoseini says manual inspection of answers on the math problems found correctness in the high nineties, while treating incomplete unit-test coverage as a genuine failure mode. Passing every available test does not establish that a patch is correct. The verifier’s quality remains decisive.

Repeated independent sampling buys breadth: many separate paths through a problem. Sequential revision buys depth: the model produces an initial approach, revises it, and continues improving a conditioned chain before returning a final answer. Sequential behavior can be elicited through prompting; Mirhoseini also notes that reasoning models are increasingly trained to exhibit revision-like behavior internally.

The allocation question is how to divide a fixed generation budget between those two modes. Reward models make more directed allocation possible.

An outcome reward modelA model trained to score the quality of completed answers. scores a completed answer. It supports best-of-N selection: generate several full solutions, score each, and return the top candidate. A process reward modelA model trained to score intermediate steps in a solution., or PRM, scores intermediate steps rather than only a final output.

A PRM can guide beam search. At each stage, the system generates possible next steps, retains the highest-scoring steps according to the PRM, and expands those branches again. In Mirhoseini’s description, a step is an intellectually meaningful chunk—a math step or sentence, for example—rather than necessarily a token. PRMs are generally fine-tuned from language models; they tend to work better in-domain but may generalize to some degree.

The experiment discussed from Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Model Parameters uses the MATH benchmark, PaLM 2-S* (Codey), a PRM, and a revision model trained on trajectories from incorrect answers to correct ones. Difficulty was estimated empirically: each question’s pass@1 was measured from 2,048 samples, then questions were sorted into five increasing-difficulty bins.

The reported conclusion is not that one policy wins everywhere. A compute-optimal mixture of parallel sampling and sequential revisions produces substantial early improvements over best-of-N approaches. Easier questions perform best with fully sequential computation in the reported setup. On harder questions, the useful sequential-to-parallel ratio changes; there is no universal allocation.

One intuitive explanation raised in the class is that easier problems may have many viable paths to a solution, making continued refinement of a plausible path worthwhile. Harder problems may require more independent exploration before the system finds a promising path. Mirhoseini treats this as an intuitive account of the observed pattern rather than a settled explanation.

She also places a boundary around the broader test-time-scaling argument. In the FLOPs-matched comparison displayed in the lecture, added test-time compute was often preferable to additional pre-training for easy and medium questions. On the hardest questions, however, more inference compute produced very little benefit relative to more pre-training.

The economics remain asymmetric: pre-training is paid once and reused across many tasks, while inference compute is paid again for every task. But the comparison still answers a strategic question: can an organization get the necessary performance from repeated use of an existing model, or does it need a better base model? Mirhoseini’s answer is conditional. Smaller and open models become substantially more useful with larger test-time budgets, but stronger pre-trained frontier models continue to do better on the very hardest general problems.

Archon treats test-time scaling as an architecture-search problem. Rather than choose only a sample count or revision depth, it searches for a workflow that combines available models and inference operations under a call budget, optimized for a target benchmark or task class.

The relevant operations can be grouped compactly:

The central idea is that the system need not merely select one answer from a population. It can use the population to create a new answer. Fusion is the clearest example: provide a model with the original question and several candidate responses, then ask it to synthesize an output response from that material.

The lecture’s Archon chart compares random selection, top-ranked selection, oracle selection, fusion, and ranking followed by fusion. Fusion is shown outperforming oracle selection among the original candidates in the reported setting. Ranking candidates before fusing the top five performs better than fusing all available candidates on that chart. The result is empirical and benchmark-specific, but it demonstrates that synthesis can improve on selecting the best already-generated candidate.

The same pattern appears when candidates come from different models rather than repeated samples from one model. Archon therefore makes model choice part of inference design: different models can occupy different roles in a workflow rather than one model performing every operation.

For coding and reasoning tasks, the framework also includes natural-language unit-test generation and evaluation. In the lecture’s bracket-balancing example, a model proposes tests such as rejecting a string beginning with a closing bracket, rejecting an odd number of brackets, and rejecting strings whose brackets are ordered incorrectly. The model can also be asked to generate code for testing those conditions. Archon’s unit-test evaluator is more unusual: rather than necessarily executing a conventional test suite, it asks a model to evaluate a candidate answer against generated unit tests.

The workflows that emerge can be substantially deeper than a standard inference call: generate many candidates, critique them, rank or filter them, fuse them, then repeat parts of that process. The architecture is intended to maximize quality for a specified inference-call budget, not to prescribe the same stack for every query.

Archon searches this design space with constrained Bayesian optimization rather than random configurations. The constraints reduce implausible workflows and make an expensive search tractable: generation occupies the first layer; critiques precede a ranker or fuser; and a unit-test generator must be followed by a unit-test evaluator. These are engineering choices used in the framework’s search space, not general laws of reasoning.

The lecture presents a further result: adding layers of critics and fusers improves performance across the displayed instruction-following, reasoning, math, and coding benchmarks. The deepest shown configuration uses an ensemble plus three layers of critics and fusers before a final fuser. That pattern is compared with both a single use of the best open-source model and repeated samples followed by one fuser.

The 14.1% result is an average across heterogeneous instruction-following, reasoning, math, and coding measures—some reported as pass@1 accuracy and others as win rate—not a uniform gain on every benchmark. Mirhoseini says Archon could be optimized for a particular task class or for broader general-purpose performance. In the displayed table, open-source-only configurations could match or exceed the frontier closed models available at the time on the listed tasks, while task-specific Archon configurations performed better still.

The cost is integral to the claim. A deep workflow with many samples, critics, fusers, and test evaluators is not a universal replacement for a single response. It is a design option for tasks where quality is valuable enough, latency is acceptable enough, and the available verification or evaluation signals are strong enough to justify the extra inference calls.