15.3 Search-time Compute

The previous section treated reasoning as an explicit search graph. Test-time compute is the broader systems problem: given a prompt and a latency or cost budget, which inference procedure should run, how much work should it spend, and when should it stop?

Extra tokens are not automatically extra reasoning. A model may explore a useful alternative, repeat itself, rationalize an error, or merely produce a longer explanation. The unit of analysis must be the model–sampler–verifier–budget system, not reasoning-token count in isolation.

1. Three Ways to Spend Inference Compute

Parallel sampling

Generate $N$ candidates and select one with a verifier, reward model, tests, or majority vote. If each independent candidate has probability $p$ of being acceptable, the probability that the set contains at least one acceptable answer is

This is only an upper bound on delivered quality. A fallible verifier may miss the good candidate, samples are correlated, and $p$ varies sharply across prompts. pass@$N$ measures coverage; best@$N$ measures the selector’s delivered result. Conflating them hides selection error.

Sequential search

Beam search, tree search, and process-reward-guided search score partial solutions and discontinue weak branches. They can spend fewer completion tokens than best-of-$N$, but introduce a new failure: an inaccurate process verifier may prune the only recoverable path. Search policy, branch width, expansion depth, and stopping rule are part of the evaluated system.

Learned long-form deliberation

Reasoning-oriented models are trained so that one trajectory may include decomposition, checking, and revision. This can remove an external tree controller, but it does not prove that a visible or hidden trace is a faithful execution log. “The model wrote wait” and “the model recovered from a distinct internal search state” are different claims.

2. What the Scaling Evidence Says

Snell et al. found that compute-optimal allocation can be more than four times as efficient as a best-of-$N$ baseline in their evaluated settings [1]. They also showed cases where a smaller model with test-time compute outperformed a model 14 times larger. The qualifier is that this occurred in difficulty regions where the smaller model already had non-trivial success. It is not a general rule that a small model can replace a large one by emitting enough tokens.

The return curve has three common regimes:

• Already solved: extra samples mostly duplicate correct work.
• Searchable: the model has the required primitives, and sampling or verification can expose a correct composition.
• Capability-limited: the generator rarely proposes a viable path, or the verifier cannot distinguish it. More budget can saturate without solving the task.

Studies also report overthinking: additional inference can reduce accuracy on some tasks through unnecessary revisions or failure to stop [3]. Monotonic “more compute is better” extrapolation is unsafe.

3. Compute-Optimal Routing

Let $a$ denote an action: model, sample count, temperature, maximum tokens, search policy, verifier, and stopping rule. A router can be framed as

subject to latency, safety, and availability constraints. $U$ is task utility, $C$ total compute or monetary cost, and $\lambda$ the product’s cost weighting. In an SLO-bound service, maximizing utility under a p95 latency budget is often easier to operate.

A production router should not use “difficulty” as an uncalibrated label. Useful features include:

• a cheap model’s calibrated probability of success;
• disagreement among small pilot samples;
• verifier margin or entropy;
• tool requirements, prompt length, and expected output length;
• customer tier, deadline, and error cost.

Evaluate routing off-policy or in a randomized shadow experiment. If only hard prompts go to the expensive policy, raw success rates make that policy look worse even when routing is beneficial.

4. Accounting: Tokens Are Not the Whole Bill

For $N$ candidates, a rough ledger is

Prefix sharing may reduce prefill and KV memory. Parallel sampling can lower wall-clock latency without lowering total FLOPs. A verifier with another tokenizer or model needs its own formatted input and attention mask. Tool calls add external latency and cost. Early stopping changes both output-length distribution and selection pool.

The executable reference below isolates these application contracts.

Interface-level example. The generator and verifier come from the serving stack. The example does not pretend generator token IDs can be passed directly to an unrelated verifier. Production code needs tokenizer-native chat templates, batching, retries, deterministic request IDs, cancellation, safety checks, and calibrated scores.

from dataclasses import dataclass
from typing import Callable, Sequence


@dataclass(frozen=True)
class Candidate:
    text: str
    output_tokens: int
    finish_reason: str


@dataclass(frozen=True)
class Selection:
    answer: str
    score: float
    samples: int
    generated_tokens: int


def budgeted_best_of_n(
    prompt: str,
    generate: Callable[[str, int, int], Sequence[Candidate]],
    verify: Callable[[str, str], float],
    *,
    samples: int,
    max_new_tokens: int,
    token_budget: int,
) -> Selection:
    if samples < 1 or max_new_tokens < 1 or token_budget < 1:
        raise ValueError("budgets must be positive")

    candidates = list(generate(prompt, samples, max_new_tokens))
    used = sum(item.output_tokens for item in candidates)
    if used > token_budget:
        raise RuntimeError(f"generator exceeded budget: {used}>{token_budget}")
    if not candidates:
        raise RuntimeError("generator returned no candidate")

    scored = [(verify(prompt, item.text), item) for item in candidates]
    score, winner = max(scored, key=lambda pair: pair[0])
    return Selection(winner.text, score, len(candidates), used)

This boundary makes budget overshoot and empty candidate sets observable. It still needs a selection threshold: if all scores are poor, abstention or escalation can be safer than returning the maximum.

5. Training Models to Deliberate

DeepSeek-R1 is useful because its report distinguishes two recipes [2]:

• DeepSeek-R1-Zero applies reinforcement learning to a base model without an initial supervised reasoning stage. The report describes emergent longer reasoning and self-reflection, along with readability and language-mixing problems.
• DeepSeek-R1 uses a multi-stage pipeline including cold-start data, reasoning-oriented RL, rejection sampling and supervised fine-tuning, followed by alignment-oriented RL. Calling it “pure RL” is inaccurate.

The report uses Group Relative Policy Optimization (GRPO), which estimates a group-relative baseline from multiple responses and avoids a separately trained critic model. That removes one memory cost relative to actor–critic PPO, but rollout generation, policy and optimizer state, reference policy where used for KL control, and verification remain expensive.

Verifiable rewards are easiest for mathematics and code, but even there the objective can be gamed. Unit tests may be incomplete, answer extraction may accept malformed reasoning, and reward normalization can become unstable when every sample in a group gets the same reward. For open-ended work, judge-model bias and rubric ambiguity become part of the target.

Reasoning length is an observable cost, not a reliable proxy for search depth. Report answer quality jointly with generated tokens, total FLOPs or accelerator time, verifier cost, latency, and failure modes.

6. Evaluation and Release Gate

Build an evaluation matrix before tuning budget:

• difficulty and domain slices below and above the model’s capability frontier;
• fixed-compute comparisons across model size and inference policy;
• pass@$N$, best@$N$, verifier regret, calibration, and abstention quality;
• total generated/verifier tokens, accelerator-seconds, p50/p95 latency, and peak KV memory;
• malformed traces, non-termination, repeated reasoning, answer flips, reward hacking, and safety regressions.

Set stopping and rollback thresholds in advance. Stop after a verified terminal answer; cap repeated semantic states; fall back to a larger model when calibrated confidence remains low; roll back when the expensive route misses its paired quality gain or violates latency/cost bounds over the declared window.

Keep reconstructable request IDs, model/verifier versions, sampling parameters, seeds, routing features, candidate hashes, scores, and finish reasons. Without that ledger, a surprising answer cannot be reproduced and the router cannot be audited.

7. Takeaway

Test-time compute is a budget-allocation discipline, not a synonym for long chain-of-thought. It works when the generator can produce useful alternatives, the verifier can rank them, and the router spends compute where marginal utility exceeds marginal cost. The next section examines the component that often becomes the real bottleneck: the verifier.

Quizzes

References

1. Snell, C., Lee, J., Xu, K., & Kumar, A. (2024). Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. arXiv:2408.03314.
2. DeepSeek-AI. (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. arXiv:2501.12948.
3. Ghosal, S. S., et al. (2025). Does Thinking More always Help? Mirage of Test-Time Scaling in Reasoning Models. arXiv:2506.04210.
4. Brown, N., et al. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. arXiv:2407.21787.