Test-Time Compute, Search and Verification
What you’ll learn. How spending more compute at inference improves results; the math of repeated sampling (pass@k, coverage); best-of-, majority voting and verifier-guided search; tree search with process rewards; reasoning models that “think” at length; and how to choose between spending compute on a bigger model, more samples, or longer reasoning.
The idea
Section titled “The idea”Training-time scaling gives a fixed model. Test-time (inference-time) scaling spends extra compute on a particular problem: sample multiple solutions, search, think longer, verify. For problems with checkable answers this reliably converts compute into accuracy, and it is the mechanism behind modern reasoning models. It is also the bridge between this lecture’s search methods and RL for agents, which trains models to do this internally.
Repeated sampling and coverage
Section titled “Repeated sampling and coverage”Suppose a model solves a problem with probability per independent sample. The chance at least one of samples is correct (coverage, or pass@) is
For : gives about 40%, about 99.4%. Averaged over problems with a distribution of difficulty, coverage grows roughly log-linearly with over several orders of magnitude in studies such as “Large Language Monkeys” (Brown et al., 2024), where on SWE-bench Lite coverage increased substantially with hundreds of samples. The unbiased estimator of pass@ from samples with correct (Chen et al., 2021):
from math import comb
def pass_at_k(n: int, c: int, k: int) -> float: if n - c < k: return 1.0 return 1.0 - comb(n - c, k) / comb(n, k)Coverage is only useful if you can pick the right sample. That requires a selector, and selection is the real problem.
Selection strategies
Section titled “Selection strategies”Majority vote / self-consistency (Wang et al., 2022): sample chains of thought, extract final answers, return the most frequent. Needs no verifier, only a comparable answer format. It saturates: if the plurality answer is wrong, more votes do not help.
Best-of- with a reward model or verifier: score each candidate and return the highest.
Programmatic verification: run unit tests, a checker or a simulator. When available this is the best selector: coverage translates nearly directly into accuracy. This is why code and formal-math settings gain most.
Weighted voting: weight each answer’s votes by verifier score; typically beats either alone.
A sketch:
from collections import Counter
def best_of_n(sample, score, n=16): cands = [sample() for _ in range(n)] return max(cands, key=score)
def self_consistency(sample, extract, n=16): answers = [extract(sample()) for _ in range(n)] return Counter(answers).most_common(1)[0][0]Verifier quality caps the gain
Section titled “Verifier quality caps the gain”With an imperfect verifier, best-of- can decrease in value as grows: the more candidates, the more likely some wrong one fools the verifier (reward hacking in miniature). Empirically, reward-model best-of- often plateaus or turns down at large , while exact verifiers keep improving. Invest in verifier quality (held-out validation, calibration) before scaling .
Search
Section titled “Search”Sampling whole solutions independently wastes compute on samples that went wrong early. Search shares prefixes and prunes.
- Beam search over reasoning steps guided by a process reward model (PRM) that scores partial solutions.
- Best-first / Monte Carlo tree search (MCTS): expand promising nodes, use rollouts or learned value estimates (as in AlphaGo, and applied to LLM reasoning in Tree of Thoughts (Yao et al., 2023) and later work).
- Revision-based scaling: iteratively revise a solution conditioned on previous attempts; Snell et al. (2024) found the best strategy depends on problem difficulty: sequential revision for easier problems, parallel sampling with search for harder ones.
Compute-optimal allocation (Snell et al., 2024) showed that on some tasks, adaptively spending test-time compute can beat a model roughly 14x larger in parameters on easy-to-medium problems; on the hardest problems, a bigger base model still wins. The takeaway is that test-time compute is a substitute for model size only when the base model has nonzero success on the problem.
Long chain-of-thought reasoning models
Section titled “Long chain-of-thought reasoning models”Rather than external search, reasoning models (OpenAI’s o-series, DeepSeek-R1, and successors from several labs) were trained with large-scale RL on verifiable tasks to produce a long internal chain of thought that includes planning, checking, backtracking and alternative attempts. Test-time scaling then happens inside one sample: more thinking tokens, higher accuracy, with a characteristic log-like curve. Some APIs expose a “thinking budget” or effort setting; “budget forcing” (s1, Muennighoff et al., 2025) showed that simply appending “Wait” to extend thinking can improve results after only modest supervised fine-tuning on about a thousand curated traces.
Observations to keep in mind:
- Thinking tokens are billed and add latency; match effort to difficulty.
- Overthinking exists: easy questions can get worse or just slower with long reasoning.
- Long reasoning can be combined with sampling and voting on top.
- Reasoning traces may not be faithful explanations of the model’s actual computation; do not treat them as ground-truth rationales.
Agents: where test-time compute goes
Section titled “Agents: where test-time compute goes”For an agent, extra compute can be spent on:
- More steps (exploration, double-checking).
- Parallel attempts from the same start, then choose by tests or a judge (several coding agents on separate branches).
- Per-step reasoning before each action.
- Verification agents that independently check the result with tools.
- Search over action sequences with rollback (possible when the environment supports resets or snapshots, e.g. a git checkpoint or container snapshot).
task --> [agent attempt 1] --> patch1 --\ --> [agent attempt 2] --> patch2 ---+--> run tests --> choose best/passing --> [agent attempt 3] --> patch3 --/Without cheap verification parallel attempts mostly produce disagreement. With it, “agent plus tests plus N attempts” is a strong recipe.
Cost model
Section titled “Cost model”Let a sample cost and success probability with a perfect verifier. Expected samples to the first success is and expected cost . Two ways to lift accuracy from to : scale (cost ) or use a larger model (cost per sample up by factor ). Pick whichever is cheaper per unit of coverage gained; measure both on a dev set. Also account for latency: parallel samples cost money not time; sequential thinking costs both.
Pitfalls
Section titled “Pitfalls”- Correlated samples: at low temperature samples collapse to the same answer; diversity (temperature, varied prompts, different models) matters for coverage.
- Leaky verifiers: if tests are visible to the generator it may overfit them.
- Evaluation inflation: reporting pass@ as if it were single-shot accuracy. State and whether a verifier was available at deployment.
- Unverifiable tasks: for open-ended writing and research, there is no cheap verifier; gains rely on LLM judges and are smaller.
- Cost surprises: 100 samples of a 20-step agent is 2,000 agent steps.
Key takeaways
Section titled “Key takeaways”- Coverage grows quickly with samples, but you only benefit if you can select the correct one.
- Exact verifiers (tests, checkers) make test-time scaling highly effective; learned reward models plateau and can be gamed.
- Search with process rewards shares compute across candidates; compute-optimal allocation depends on problem difficulty.
- Reasoning models internalize search through RL-trained long chains of thought; thinking budget trades accuracy for latency and cost.
- For agents, prefer parallel attempts plus automated verification when you can reset the environment.
Exercises
Section titled “Exercises”- Compute. A problem has per-sample success . How many independent samples give at least 90% coverage? 99%?
- Hands-on. Use
pass_at_kto compute pass@1, 5, 20 from samples with 8 correct. - Conceptual. Why can best-of- with a learned reward model degrade with large , but best-of- with unit tests does not?
- Hands-on. Implement self-consistency on a numeric task with a noisy fake sampler (correct with prob 0.4, otherwise a random wrong number from a small set) and plot accuracy against . When does it fail?
Solutions (1, 2)
- ; for 99%, .
- pass@1 = 0.08; pass@5 = ; pass@20 is about 0.84.
Further reading
Section titled “Further reading”- Brown et al., “Large Language Monkeys: Scaling Inference Compute with Repeated Sampling” (2024).
- Snell et al., “Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Model Parameters” (2024).
- Wang et al., “Self-Consistency Improves Chain of Thought Reasoning in Language Models” (2022).
- Yao et al., “Tree of Thoughts” (2023); Lightman et al., “Let’s Verify Step by Step” (2023).
- DeepSeek-AI, “DeepSeek-R1” (2025); Muennighoff et al., “s1: Simple test-time scaling” (2025).
- Chen et al., “Evaluating Large Language Models Trained on Code” (2021), for pass@k.