Scaling Test-Time Compute

Chapter 1: Two Strategies

The paper identifies two fundamentally different ways to spend test-time compute: parallel sampling (generate many independent solutions) and sequential revision (iteratively improve one solution). Each has different scaling properties.

Strategy 1: Parallel sampling (search)

Generate N independent solutions, score each with a verifier (reward model or process reward model), and select the best. This is the same as best-of-N sampling. The compute cost scales linearly with N.

Where p is the per-attempt success probability. With diminishing returns: doubling N gives less than doubling accuracy. This follows the "coverage" curve — eventually, you've sampled enough that adding more doesn't help.

Strategy 2: Sequential revision

Generate one solution, then iteratively refine it. At each revision step, the model sees its previous attempt and feedback from a verifier. The model can fix errors, try different approaches, or elaborate on partial solutions. This is analogous to a student revising an essay based on feedback.

python
# Strategy 1: Parallel sampling (best-of-N)
def parallel_search(model, verifier, problem, N):
    solutions = [model.generate(problem) for _ in range(N)]
    scores = [verifier.score(s) for s in solutions]
    return solutions[argmax(scores)]
    # Cost: N * (generate_cost + verify_cost)

# Strategy 2: Sequential revision
def sequential_revise(model, verifier, problem, T):
    solution = model.generate(problem)
    for _ in range(T):
        feedback = verifier.critique(solution)
        solution = model.revise(problem, solution, feedback)
    return solution
    # Cost: (T+1) * generate_cost + T * verify_cost

The hybrid approach

The paper also considers hybrids: generate M initial solutions, then revise each T times, for a total of M * (T+1) forward passes. The optimal M and T depend on the problem difficulty and the quality of the verifier.

Chapter 2: Search with Verifiers

The quality of test-time compute scaling depends critically on the verifier — the reward model that scores solutions. A perfect verifier makes best-of-N scale optimally. A poor verifier limits how much test-time compute helps.

Verifier types

The paper compares these verifiers and shows that the verifier quality is the bottleneck for test-time scaling. With an oracle verifier, accuracy scales smoothly with N. With majority voting, it plateaus quickly. PRMs are the sweet spot — high enough quality to enable meaningful scaling without requiring ground truth.

Search with tree-structured reasoning

The paper also studies beam search over reasoning steps (using a PRM as the value function). Instead of generating complete solutions and scoring them, the model generates step by step, with the PRM evaluating each step. Bad branches are pruned early, saving compute.

python
# Beam search with PRM
def beam_search_prm(model, prm, problem, beam_width=5, max_steps=10):
    beams = [("", 1.0)]  # (partial solution, cumulative score)

    for step in range(max_steps):
        candidates = []
        for sol, score in beams:
            # Generate K continuations for each beam
            for _ in range(3):
                next_step = model.generate_step(problem, sol)
                step_score = prm.score_step(problem, sol + next_step)
                candidates.append((sol + next_step, score * step_score))

        # Keep top beam_width candidates
        beams = sorted(candidates, key=lambda x: -x[1])[:beam_width]

    return beams[0][0]  # highest-scoring complete solution

Chapter 3: Sequential Revision

The paper studies a second test-time strategy: instead of sampling many solutions in parallel, generate one solution and revise it iteratively. At each revision, the model sees its previous attempt plus verifier feedback and produces an improved version.

How revision works

The revision model is a fine-tuned LLM that takes (problem, previous_solution, feedback) as input and generates an improved solution. The feedback can come from a PRM ("Step 3 has an error"), a simple correctness check ("Answer is wrong, try again"), or the model's own self-evaluation.

Revision vs sampling: complementary strengths

Sampling excels at exploration. Each sample is independent, so N samples explore N different regions of solution space. If the correct approach exists somewhere in the model's distribution, enough samples will find it.

Revision excels at exploitation. Each revision builds on the previous attempt, fixing specific errors. If the model's first attempt is almost correct (one calculation error), revision can fix it efficiently. But if the first attempt uses a fundamentally wrong approach, revision may get stuck polishing a bad idea.

Chapter 4: Compute-Optimal Allocation

Given a fixed test-time compute budget C, how should you split it between sampling (N attempts) and revision (T revisions per attempt)? The paper formulates this as an optimization problem.

The key finding: the optimal allocation depends on problem difficulty.

Difficulty-conditional allocation

The paper proposes a difficulty-conditional compute allocation policy. Before spending compute, estimate the problem difficulty (e.g., using the verifier's score on the first attempt). Then allocate:

python
# Compute-optimal test-time allocation
def compute_optimal_inference(model, verifier, problem, budget):
    # Step 1: Estimate difficulty with one quick attempt
    first_try = model.generate(problem)
    difficulty = 1 - verifier.score(first_try)  # 0=easy, 1=hard

    # Step 2: Allocate compute based on difficulty
    if difficulty < 0.3:  # easy
        N = budget; T = 0
    elif difficulty < 0.7:  # medium
        N = int(budget**0.5); T = budget // N - 1
    else:  # hard
        N = 2; T = budget // 2 - 1

    # Step 3: Execute strategy
    best_sol = None; best_score = -1
    for _ in range(N):
        sol = model.generate(problem)
        for _ in range(T):
            sol = model.revise(problem, sol, verifier.critique(sol))
        score = verifier.score(sol)
        if score > best_score:
            best_score = score; best_sol = sol

    return best_sol

Chapter 5: The Key Result

The paper's headline finding: a Llama-8B model with compute-optimal test-time scaling matches a Llama-70B model on hard math problems — using the same total FLOPs.

The comparison

With difficulty-conditional allocation, the 8B model matches the 70B model while using less total compute. The key: easy problems are solved with one pass (cheap), and the saved compute is redirected to hard problems (more samples + revision).

Scaling curves

The paper plots accuracy vs. test-time FLOPs for different strategies:

Best-of-N with PRM scales as roughly accuracy ∝ log(N). Each doubling of N gives a constant accuracy improvement.

Revision scales faster initially (first few revisions fix obvious errors) but plateaus sooner (diminishing returns from polishing).

Compute-optimal (combining both) outperforms either strategy alone at every budget level.

Chapter 6: Compute Allocator Simulator

Experience compute-optimal inference. This simulator presents problems of varying difficulty and lets you allocate compute. See how difficulty-conditional allocation outperforms fixed strategies.

Chapter 7: Connections

This paper formalized what OpenAI's o1 and DeepSeek-R1 demonstrated empirically: spending more compute at inference can substitute for model scale. It connects forward to every reasoning-at-inference-time technique.

What this paper got right

The difficulty-conditional insight. The optimal strategy depends on problem difficulty. This insight has been adopted by every subsequent reasoning system.

What it left open

How to estimate difficulty in practice. The paper assumes you can estimate difficulty cheaply. In practice, this is hard — you often need to attempt the problem to know how hard it is.

Self-Consistency — The simplest test-time compute method. Read the SC lesson →

Let's Verify Step by Step — PRMs as verifiers for search. Read the PRM lesson →

DeepSeek-R1 — RL-trained test-time compute. Read the R1 lesson →