Test-Time Scaling Cheatsheet

From sequential/parallel scaling, search, and verifiers to compute-optimal allocation

1. Overview

Test-time scaling (TTS), also called inference-time scaling, means trading more compute spent at inference for higher accuracy, without changing the model weights. It is the core of the o1 / R1 paradigm: the model learns to "think longer", and the evaluation lens shifts from "single-shot accuracy" to "accuracy under a given compute budget".

Train-time compute                       Test-time compute
─────────────────────                    ─────────────────────
+params / +data / +steps                 Sequential: longer chains (long CoT, budget forcing)
one-time cost, fixed               ⇄      Parallel: multi-sample + aggregate (BoN, self-consistency)
inference cost unchanged                  Search: verifier-guided tree/beam search (beam, MCTS)
                                          cost grows linearly/super-linearly with budget

1.1 Paradigm shift: train-time compute → test-time compute

Classic scaling laws focus on train-time investment (params, data, steps); TTS brings another knob to the fore — how much inference compute to spend on a single query. Snell et al. (arXiv:2408.03314, ICLR 2025) argue systematically that under a fixed FLOPs budget, optimally allocating test-time compute (search on hard problems, few samples on easy ones) is, in some settings, more cost-effective than simply scaling up parameters. This pries open the assumption that "capability is fully decided at training time": a portion of capability can be "cashed in on the spot" at inference.

1.2 Two axes: sequential (depth) vs parallel (width)

Search can be viewed as a hybrid of sequential and parallel — expanding step by step (depth) over multiple partial paths (width), with a verifier deciding which to keep.

1.3 Core question: how to optimally allocate a given compute budget

The central question of TTS is not "can we be more accurate", but "given the same N× compute, how do we spend it best":

• Difficulty adaptivity: one of Snell's key findings is that the optimal strategy varies with problem difficulty — easy problems suit a small amount of sequential correction, hard problems suit wider parallel sampling + search.
• Sequential vs parallel ratio: parallel sampling buys coverage, sequential correction buys depth, and the optimal ratio between them depends on the task.
• The verifier is the ceiling: BoN / weighted voting / search ultimately depend on verifier quality to "pick the right one" from the candidates (see §5) — without a reliable verifier, sampling more doesn't help you select better (pure majority-vote self-consistency is the exception, relying on answer aggregatability and whether the majority answer is correct).

Below, §2–§4 unpack the three axes one by one, §5 covers the verifier that runs through all of them, and §6 covers compute-optimal allocation and "how RL teaches a model to use test-time compute well".

2. Sequential Scaling

Sequential scaling means spending more tokens on a single reasoning chain: thinking longer, writing out intermediate steps in full, and going back to fix errors once they're found.

2.1 long CoT and "think longer"

The most naive sequential scaling is simply letting the model generate a longer chain of thought. The core observation of o1 / R1-style models: after RL training, the model spontaneously produces longer reasoning on hard problems (self-reflection, case enumeration, re-checking), and on hard problems, within a suitable budget range, accuracy rises with the number of reasoning tokens (over-long reasoning on easy problems instead hurts, see §6.4). Note there are two layers here: ① whether the model has the ability to use more tokens well (decided by training); ② whether at inference you let it use more tokens (decided by decoding control). §2.2 handles the latter.

2.2 Budget forcing — s1

s1 (Muennighoff et al., arXiv:2501.19393) proposes a minimalist sequential-scaling control — budget forcing: directly manipulate the "thinking budget" during decoding.

• Wants to stop early but below the lower bound → suppress the end token, inject "Wait" to make the model keep thinking (often triggers self-correction);
• Exceeds the upper bound → forcibly truncate thinking and require an answer.

s1 uses only 1000 curated reasoning samples for SFT + budget forcing, yet achieves competitive results on math reasoning, demonstrating that "test-time scaling can be very simple".

# Budget forcing (s1, Muennighoff et al. 2025): control the "thinking budget" at decode time.
# - wants to stop early but below the min token count → inject "Wait" to keep going, forcing
#   the model to think longer (often triggers self-correction);
# - exceeds the max → forcibly stop thinking and switch to answering. Uses a mock decoder to
#   demo the [control logic], with no real model.
def budget_forcing(model_step, min_think, max_think, wait_token="Wait"):
    """model_step(prefix)->(token, wants_stop): one mock decode step, returns the next
       token text and whether "the model wants to stop thinking"."""
    think_tokens, n_wait = [], 0
    while len(think_tokens) < max_think:
        tok, wants_stop = model_step(think_tokens)
        if wants_stop and len(think_tokens) < min_think:
            think_tokens.append(wait_token)   # suppress stop, force continuation
            n_wait += 1
            continue
        if wants_stop:
            break
        think_tokens.append(tok)
    return think_tokens, n_wait

2.3 Self-correction / refinement (self-refine) and its limits

Self-Refine (Madaan et al., arXiv:2303.17651, NeurIPS 2023): use the same LLM in a loop to "generate → self-critique → revise per feedback", with no extra training or supervision data, improving quality on a range of generation tasks.

3. Parallel Scaling

Parallel scaling means independently sampling many complete solutions, then aggregating them in some way. Naturally parallelizable and throughput-friendly, it is the most easily deployable TTS in practice.

3.1 best-of-N and self-consistency (majority voting)

The two most basic aggregations:

• Self-Consistency (Wang et al., arXiv:2203.11171, ICLR 2023): sample many CoTs for the same problem and take a majority vote over the final answers. No verifier needed, only that answers can be normalized and compared; significantly improves math/commonsense reasoning.
• best-of-N (BoN): sample N solutions, use a verifier/RM to score each, and take the single highest-scoring one. Depends on verifier quality (§5).

The difference between the two: majority voting relies on "the mode of the answer distribution", BoN relies on "verifier selection". Weighted self-consistency is the in-between form — weight each vote by the verifier score before voting.

from collections import defaultdict

# Three parallel aggregations (self-consistency from Wang et al. 2022 + BoN variants):
# - majority_vote: take a majority vote over the [final answers] (no verifier needed);
# - weighted_vote: weight each vote by verifier/RM score (weighted self-consistency);
# - best_of_n: directly take the single highest verifier-scoring solution (no voting).
def majority_vote(answers):
    counts = defaultdict(float)
    for a in answers:
        counts[a] += 1.0
    return max(counts, key=counts.get)

def weighted_vote(answers, scores):
    counts = defaultdict(float)        # scores assumed non-negative (e.g. verifier confidence in [0,1])
    for a, s in zip(answers, scores):
        counts[a] += s                 # accumulate weighted by verifier score
    return max(counts, key=counts.get)

def best_of_n(answers, scores):
    return max(zip(answers, scores), key=lambda x: x[1])[0]  # take the single highest-scoring one

3.2 Weighted voting / verifier reranking

When a verifier is available, pure majority voting wastes the signal: a minority but high-confidence correct answer can be voted out by a majority of wrong answers. Weighted voting / verifier reranking lets the verifier score participate in the decision, usually beating pure majority voting — provided the verifier itself is reliable (otherwise it amplifies noise). This is also why §5 verifier quality is the core bottleneck of TTS.

3.3 Coverage vs precision: the ceiling of pass@k

Large Language Monkeys (Brown et al., arXiv:2407.21787) systematically studies "repeated sampling": it defines coverage = the fraction of problems where at least one sample is correct, and finds coverage grows approximately log-linearly with the number of samples across four orders of magnitude. But beware the distinction between two notions:

$$\text{pass@}k = \mathbb{E}\left[1 - \binom{n-c}{k}\big/\binom{n}{k}\right]$$

• pass@k / coverage: "win as long as one correct sample is drawn" — this is the upper bound given an oracle verifier (knowing which one is correct).
• Actually achievable accuracy: limited by whether the real verifier can pick that correct one out of the N.

4. Search-Guided Generation

Search refines "sampling" from "sampling a whole complete solution" to "step-by-step expansion + mid-course pruning": use a verifier to score partial reasoning paths, keeping only the promising branches to continue. It is a hybrid of sequential (depth) and parallel (width).

4.1 step-level beam search and lookahead

Cut reasoning into "steps", expand several candidate next-steps per step, use a PRM (process reward model, §5) to score the current partial path, and keep top-B to continue — i.e. step-level beam search. lookahead goes further: before scoring, first simulate a rollout a few steps forward, using "future" information to estimate the value of the current step (more accurate but more expensive).

# PRM-guided step-level beam search: expand candidate next-steps per step, use the process
# reward model (PRM) to score the [partial reasoning path], keep top-B to keep expanding.
# A path is represented as a list of step texts.
def prm_beam_search(root, expand, prm_score, beam=2, depth=4, n_expand=3):
    """expand(path)->list[next_step]; prm_score(path)->float. Returns the highest-scoring complete path."""
    beams = [(prm_score([root]), [root])]
    for _ in range(depth):
        cands = []
        for _, path in beams:
            for step in expand(path)[:n_expand]:
                new_path = path + [step]
                cands.append((prm_score(new_path), new_path))
        if not cands:
            break
        cands.sort(key=lambda x: x[0], reverse=True)
        beams = cands[:beam]                 # prune: keep only top-B branches
    return max(beams, key=lambda x: x[0])

4.2 Tree of Thoughts / MCTS

• Tree of Thoughts (ToT) (Yao et al., arXiv:2305.10601, NeurIPS 2023): organize reasoning into a tree — nodes are coherent "thoughts", and the model can generate multiple candidate thoughts, self-evaluate, and search with BFS/DFS backtracking, suited to problems needing trial-and-error / planning.
• MCTS (Monte Carlo Tree Search): use the selection-expansion-simulation-backup four steps to allocate the search budget over the reasoning tree, concentrating compute on more promising branches. rStar-Math (Guan et al., arXiv:2501.04519) uses MCTS + a process reward model for self-evolution, getting 1.5B–7B small models to strong math performance without relying on distillation from frontier models.

4.3 PRM-guided search

Whether beam or MCTS, pruning/selection depends on a signal that can score "partial paths" — exactly where the PRM (process reward model) comes in (an ORM can only score complete solutions and cannot directly guide mid-course pruning; it can only estimate partial-path value indirectly by rolling out to the end). The strength of search methods is highly coupled to PRM quality: when the PRM is noisy, search wastes compute on branches that were wrongly over-estimated. For PRM and ORM training details, see §5 and reward-modeling-eval §2.

5. Verifiers

The verifier is the shared bottleneck of TTS: parallel relies on it to rerank, search relies on it to prune. Here we only cover how the verifier is consumed at test time; for its training (RM loss, data construction), see reward-modeling-eval §2.

5.1 ORM vs PRM

Let's Verify Step by Step (Lightman et al., arXiv:2305.20050, ICLR 2024) builds PRM800K (800K human step-level annotations) and argues that on BoN reranking of MATH solutions, process-supervised verifiers beat outcome-supervised ones.

5.2 Automatic process annotation — Math-Shepherd

The pain point of PRMs is that step-level annotation is expensive. Math-Shepherd (Wang et al., arXiv:2312.08935, ACL 2024) proposes annotation-free auto-labeling: for a given step, roll out to the end multiple times from it, and use "the fraction that reaches the correct answer after this step" as the process label for this step, then train a PRM. This PRM can be used for BoN reranking and also as a PPO reward.

5.3 Generative verifiers

Generative Verifiers (GenRM) (Zhang et al., arXiv:2408.15240, ICLR 2025) change verification from "discriminative scoring" to "next-token prediction" — let the verifier generate a CoT judging "is this solution correct", then read out the yes/no probability as the score. Benefits: ① reuse the LLM's generation/reasoning ability for verification; ② the verifier can itself scale verification compute with CoT + majority voting (the verifier can also do TTS). This is the "LLM-as-judge" idea applied to verification.

import numpy as np

# A PRM aggregates "the correctness probability of each step" into "a whole-path score". Three common aggregations:
# - min : the weakest step decides the whole (strictest, common for step-level verification);
# - prod: multiply the per-step independent correctness (equivalent to summing log-probs);
# - last: look only at the last step (approximates outcome-style scoring, not a strict ORM).
def aggregate_prm(step_probs, mode="min"):
    p = np.asarray(step_probs, dtype=float)
    if mode == "min":
        return float(p.min())
    if mode == "prod":
        return float(p.prod())
    if mode == "last":
        return float(p[-1])
    raise ValueError(f"unknown mode: {mode}")

5.4 The fragility of verifiers

6. Compute-Optimal & RL-Learned Reasoning

6.1 Compute-optimal allocation — Snell et al.

Snell et al. (arXiv:2408.03314, ICLR 2025) propose compute-optimal test-time scaling: given a test-time compute budget, adaptively choose the strategy by problem difficulty (sequential correction vs parallel sampling vs search) rather than one-size-fits-all. Conclusions: ① difficulty-adaptive allocation significantly beats fixed strategies; ② in some settings, a small model + optimal TTS can match or even surpass the single-shot inference of a model several times larger — but this has limits and is not universal.

6.2 Reasoning scaling law: the test-time vs add-parameters tradeoff

TTS and scaling up parameters are two ways to spend compute, each with its applicable regime:

• TTS is more cost-effective: when the base model already has the ability but often errs (high coverage, low single-shot accuracy) and the task is verifiable/aggregatable.
• Adding parameters is more cost-effective: when hard problems are fundamentally beyond the model's ability (low coverage, no amount of sampling finds the right one), or there's no reliable verifier to pick from candidates.
• Essence: TTS cashes in "potential"; when potential is insufficient, the returns of test-time compute saturate quickly.

6.3 RL-learned test-time scaling — o1 / R1

TTS methods (§2–§4) are inference-time decoding/search strategies; but whether the model can use this compute well is shaped at training time. This is exactly the point of o1 / R1:

• OpenAI o1 ("Learning to Reason with LLMs", OpenAI, 2024-09, no arXiv paper) uses large-scale RL to train the model to do long chain-of-thought reasoning before answering, publicly showing curves of accuracy rising with test-time compute.
• DeepSeek-R1 (DeepSeek-AI, arXiv:2501.12948, later published in Nature 2025) trains long CoT with GRPO + verifiable rewards (RLVR), and long reasoning behaviors (self-reflection, re-checking) emerge spontaneously through RL; R1-Zero further shows that in its verifiable-task setting, pure RL (no SFT) can trigger them.

In other words: RLVR makes the model acquire effective long-reasoning behaviors at training time, while TTS cashes in that ability and allocates compute at inference time. For training-side details such as GRPO / RLVR / the R1 four-stage recipe, see reasoning-rl-frontier; this page focuses on the inference side.

6.4 Open problems

• over-thinking: forcibly lengthening CoT on easy problems instead hurts and wastes compute; how to adaptively decide how long to think is still an open problem (budget forcing is a coarse-grained attempt).
• Verifier reliability: non-verifiable domains (open-ended writing, multi-turn dialogue) lack reliable verifiers, limiting TTS gains (§5.4).
• Generalization beyond verifiable domains: RL-learned reasoning is mostly trained on math/code; whether it generalizes to general reasoning is still under study.
• The economics of test-time compute: latency and cost rise with the budget, and real deployment must trade off accuracy against per-query cost.

7. Interview Questions

L1 — Fundamentals

L2 — Intermediate

L3 — Advanced

Glossary

For study reference only. Paper conclusions and figures follow the original papers; benchmark scores are illustrative and not head-to-head comparisons.

§A Key Papers Timeline

• 2022-03 · Self-Consistency Improves Chain of Thought Reasoning in Language Models — Wang et al., ICLR 2023. arXiv:2203.11171 — Replaces greedy decoding with sampling many CoTs + a majority vote over final answers, significantly improving arithmetic/commonsense reasoning; one of the earliest parallel test-time scaling methods.

• 2023-03 · Self-Refine: Iterative Refinement with Self-Feedback — Madaan et al., NeurIPS 2023. arXiv:2303.17651 — Uses the same LLM in a "generate→self-critique→revise" loop, improving quality without extra training; follow-up work notes that purely intrinsic self-correction yields limited gains without external signals.

• 2023-05 · Tree of Thoughts: Deliberate Problem Solving with Large Language Models — Yao et al., NeurIPS 2023. arXiv:2305.10601 — Organizes reasoning into a tree: nodes are coherent "thoughts", supporting self-evaluation and BFS/DFS backtracking search, suited to problems needing trial-and-error / planning (there is also a same-named different work, Long et al. 2305.08291).

• 2023-05 · Let's Verify Step by Step — Lightman et al., ICLR 2024. arXiv:2305.20050 — Builds PRM800K (800K human step-level annotations), arguing that process-supervised verifiers beat outcome-supervised ones on BoN reranking of math solutions, establishing the value of PRMs.

• 2023-12 · Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations — Wang et al., ACL 2024. arXiv:2312.08935 — Auto-constructs step-level labels from rollout "the fraction reaching the correct answer after this step" to train a PRM, with no human annotation, usable for BoN reranking and as a PPO reward.

• 2024-07 · Large Language Monkeys: Scaling Inference Compute with Repeated Sampling — Brown et al., preprint. arXiv:2407.21787 — Systematically studies repeated sampling: coverage grows approximately log-linearly with the number of samples across about four orders of magnitude; "sampling + verifier" yields large gains on code/math, but the real gain is limited by verifier quality.

• 2024-08 · Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters — Snell et al., ICLR 2025. arXiv:2408.03314 — Proposes compute-optimal TTS: adaptively allocate test-time compute by problem difficulty; in some settings a small model + optimal TTS can match the single-shot inference of a model several times larger.

• 2024-08 · Generative Verifiers: Reward Modeling as Next-Token Prediction — Zhang et al., ICLR 2025. arXiv:2408.15240 — Changes reward modeling/verification into next-token prediction: the verifier generates a CoT judging correctness and reads out the yes/no probability, reusing generation ability while the verifier itself can do TTS.

• 2024-09 · Learning to Reason with LLMs — OpenAI, blog (no arXiv paper, o1 series release). openai.com — Releases the o1 series: uses large-scale RL to train long chain-of-thought reasoning before answering, showing curves of accuracy rising with test-time compute, igniting the "inference-time scaling" paradigm.

• 2025-01 · rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking — Guan et al., preprint. arXiv:2501.04519 — Uses MCTS + a process reward model for self-evolution, getting 1.5B–7B small models to strong math performance without relying on distillation from frontier models.

• 2025-01 · s1: Simple test-time scaling — Muennighoff et al., preprint. arXiv:2501.19393 — With only 1000 curated reasoning samples for SFT + budget forcing (inject "Wait" / hard-truncate to control the thinking budget), achieves competitive results on math reasoning, arguing TTS can be very simple.

• 2025-01 · DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning — DeepSeek-AI, Nature 2025. arXiv:2501.12948 — Trains long CoT with GRPO + verifiable rewards, with long reasoning behaviors emerging spontaneously through RL (R1-Zero triggers them with pure RL); for the training-side recipe see reasoning-rl-frontier, this page focuses on the inference side.