Test-Time Compute Scaling: Sequential, Parallel, and Tree-Based Strategies

A team ships a coding agent built on GPT-4o. It handles 80% of tasks fine. For the remaining 20% — multi-file refactors, algorithm design, dependency chain analysis — the model's single-pass reasoning consistently misses the mark. The obvious fix seems to be "use a reasoning model." But reasoning model is not one thing; it is shorthand for "a model that has been trained to spend more inference compute." How it spends that compute, and how you control it, determines whether you get a 2x accuracy improvement or a 30-second latency bill.

What sequential scaling actually is

Every forward pass through a language model produces one token. The model then conditions on that token to produce the next. A reasoning chain is just this process extended over many tokens before the final answer token. Sequential scaling means letting this chain run longer.

This is not trivially free. The reasoning tokens still go through the full transformer stack. A 4,000-token thinking trace costs the model roughly 8x the compute of a 500-token one (4,000 × 2 phases × forward pass work, though KV cache reuse keeps the exact multiple lower). For an o3-mini-class model at mid-2026 pricing (~$1.10 per million reasoning tokens), that 4,000-token trace costs about $0.0044 before any output tokens.

But compute cost is not the main constraint. The main constraint is that accuracy does not increase monotonically with chain length. The research on this is consistent: there is an inverse U-shape — accuracy rises with chain length up to a problem-specific optimum, then falls. On easy problems the optimum is short (forcing long chains hurts). On hard problems the optimum is longer, but there is still an optimum.

The mechanism behind the decline is not fully understood, but the empirical pattern is clear: when models push past their optimal chain length, they start introducing spurious sub-steps, second-guess correct intermediate conclusions, and occasionally arrive at the wrong answer confidently. The failure modes article covers overthinking in more depth. The practical implication here is that the thinking budget is a dial you want to tune, not maximize.

Claude extended thinking exposes this dial directly — budget_tokens up to 128k. OpenAI o3 exposes a reasoning_effort parameter (low, medium, high). Both are proxies for the same underlying control: how many tokens the model is allowed to spend before being forced to produce its answer.

import anthropic

client = anthropic.Anthropic()

# Tight budget for faster response on a medium-difficulty problem
response = client.messages.create(
    model="claude-sonnet-4-5",
    max_tokens=8000,
    thinking={"type": "enabled", "budget_tokens": 2000},
    messages=[{
        "role": "user",
        "content": "Solve for x: 3x² - 7x + 2 = 0. Show the discriminant check."
    }]
)

# Extended budget for genuinely hard multi-step problems
response_hard = client.messages.create(
    model="claude-sonnet-4-5",
    # budget_tokens must be strictly less than max_tokens —
    # leave headroom for the final answer after thinking
    max_tokens=20000,
    thinking={"type": "enabled", "budget_tokens": 16000},
    messages=[{
        "role": "user",
        "content": "Design an algorithm for minimum-cost multi-commodity flow in a directed graph with capacity constraints. Prove the complexity bound."
    }]
)

The two-budget pattern is worth making explicit in production: classify your incoming queries and route them to the appropriate budget tier rather than paying the full budget on every request. That classification step is covered in the cost and latency tradeoffs article.

Parallel scaling: Best-of-N sampling

Sequential scaling is limited by a single chain's tendency to go wrong in consistent ways. If the model has a particular bias on a class of problems — say, an off-by-one in recursive algorithms — making the chain longer does not fix the bias; it just elaborates it. Parallel scaling sidesteps this by sampling N independent completions and aggregating.

sequenceDiagram
    participant U as Query
    participant S1 as Sample 1
    participant S2 as Sample 2
    participant S3 as Sample 3
    participant V as Verifier / Vote
    participant A as Final Answer

    U->>S1: generate (temperature=0.7)
    U->>S2: generate (temperature=0.7)
    U->>S3: generate (temperature=0.7)
    S1-->>V: answer A, confidence
    S2-->>V: answer B, confidence
    S3-->>V: answer A, confidence
    V-->>A: majority = A

The canonical version is majority voting: if at least ⌈N/2⌉ samples agree on the same final answer, pick it. For tasks with a small discrete answer space (math answers, classification labels, yes/no decisions), this works surprisingly well. The intuition is that while the model may take different wrong paths, correct paths tend to converge on the same answer.

The practical numbers matter here. At N=8, majority voting on MATH-500 class problems typically gives 6-10 percentage points improvement over a single chain, depending on problem difficulty. At N=32, gains continue but slow. Beyond N=64, the marginal gain per additional sample is close to zero without a smarter aggregation strategy. And at N=64 you are paying 64× the per-call cost with no latency advantage if you are bottlenecked on running them in parallel.

Cost math: Best-of-N for hard coding queries at scale
------------------------------------------------------
Assumptions (illustrative, mid-2026):
  - o3-mini at $1.10/M reasoning tokens, ~800 tokens/call
  - 500 hard coding queries / day
  - ORM verification: ~200 tokens per answer at $0.30/M

ORM scores all N answers: N × 200 tok × $0.30/M per query

N=1:   500 × $0.00088 = $0.44/day
N=4:   500 × $0.00352 = $1.76/day   (+ORM: $0.12 → $1.88/day)
N=8:   500 × $0.00704 = $3.52/day   (+ORM: $0.24 → $3.76/day)
N=16:  500 × $0.01408 = $7.04/day   (+ORM: $0.48 → $7.52/day)

Accuracy lift (illustrative): N=1 → 65%, N=4 → 75%, N=8 → 80%, N=16 → 82%
Marginal accuracy gain per dollar drops rapidly past N=8.
Verdict: N=4 to N=8 + ORM is the practical sweet spot for most production tasks.

Selecting the best answer: voting vs. reward models

Majority voting is free but brittle. It fails when the wrong answer is systematically more likely than any single correct answer — for instance, when a model has a consistent off-by-one in array indexing, N=8 samples may produce 8 slightly-different wrong answers with no majority. This is the amplification-of-bias problem.

The cleaner solution is an Outcome Reward Model (ORM): a separate model trained to score final answers. You run your N samples, run the ORM on each, and pick the highest-scoring answer. The ORM does not need to be large — a 7B or even 1.3B model fine-tuned on (answer, correctness) pairs can score mathematical answers reliably. The overhead is modest: scoring each answer costs ~200 tokens at ORM rates, roughly 7% on top of the N samples at the token counts above.

For tasks with deterministic checking (code that either passes tests or does not, math with checkable numeric results), you can skip the learned ORM entirely and use a rule-based verifier: run the code against unit tests, verify the math answer with a symbolic solver. This is better than either voting or a learned ORM because it cannot be fooled by a confidently wrong model output.

Tree-based scaling: beam search and MCTS

Both sequential and parallel scaling treat each completion as a single trajectory from start to finish. Tree-based methods break the reasoning process into steps and branch at each step, exploring multiple continuations from each partial state.

flowchart TD
    ROOT["Query"] --> S1["Step 1a\n'Let x = ...'"]
    ROOT --> S2["Step 1b\n'Consider the base case...'"]

    S1 --> S1A["Step 2a\n(score: 0.82)"]
    S1 --> S1B["Step 2b\n(score: 0.31 — pruned)"]

    S2 --> S2A["Step 2c\n(score: 0.79)"]
    S2 --> S2B["Step 2d\n(score: 0.91 — best)"]

    S2B --> ANS["Final answer"]

    style S1B fill:#ff2e88,color:#111
    style S2B fill:#15803d,color:#fff
    style ANS fill:#a855f7,color:#fff

Beam search maintains a fixed number of partial reasoning chains (the beam width) at each step. After each step, a scorer ranks all candidates and prunes down to the top-k. The survivors continue to the next step. This is cheaper than MCTS because it runs in a fixed number of forward passes (depth × width), but it is still serial — step N requires step N-1 to complete.

Monte Carlo Tree Search (MCTS) is more flexible: it uses simulation (running a chain to completion from a partial state) and backpropagation (updating scores of parent nodes based on child outcomes) to decide where to expand next. MCTS handles long-horizon problems better because it can backtrack to any previous node and try a different branch, not just adjacent siblings.

The reason step-level search pays for itself is that per-step errors compound: a chain that is 82% reliable per step has only a ~20% chance of surviving eight steps intact. Pruning a bad step early rescues all the downstream compute that a straight-line chain would have wasted.

{ "type": "error-compound", "title": "Why early reasoning errors compound across sequential steps", "accuracy": 0.82, "steps": 8 }

Beam search needs a step-level scorer — in practice a Process Reward Model (PRM) trained to judge intermediate reasoning steps. MCTS can get away without one: rollout-to-completion plus an outcome verifier is the classic formulation, at the cost of many more forward passes per node evaluation. A PRM makes MCTS cheaper, not possible. This step-level scoring is the key difference from parallel scaling, which only needs to score final answers. Training a PRM requires step-level annotations — labeling each step in a reasoning trace as correct or incorrect — which is expensive to collect and model-specific to the task domain. OpenAI released a PRM for math in 2023; no general-purpose PRM exists as of mid-2026.

The latency profile of tree search is the practical blocker for most teams. A beam search with width 4 and depth 10 requires 40 sequential scoring calls, each of which may take hundreds of milliseconds. P99 latency on hard problems can exceed 60 seconds. MCTS has no fixed bound — in pathological cases it keeps exploring until a budget limit forces termination.

Method	Accuracy ceiling	Latency	Requires PRM	Production fit
Sequential (long CoT)	Medium	Moderate	No	High
Best-of-N + majority vote	Medium-high	Low (parallel)	No	High
Best-of-N + ORM	High	Low (parallel)	Outcome only	High
Beam search	High	Medium-serial	Yes	Medium
MCTS	Highest	High-serial, unpredictable	Optional (rollouts + outcome verifier work; PRM is cheaper)	Low except offline

The s1 budget-forcing result

The Stanford s1 paper (January 2025) is worth understanding directly because it changes the intuition about how expensive sequential scaling needs to be.

The finding: fine-tuning a model on 1,000 carefully curated multi-step reasoning examples, then forcing longer thinking at inference — suppressing the end-of-thinking token and appending "Wait" so the model keeps reasoning — produced math benchmark scores exceeding o1-preview on MATH and AIME24 by up to 27%. The training cost was trivial — 1k samples instead of hundreds of thousands. The key variables were: (1) example quality and diversity, not quantity; and (2) the budget-forcing mechanism, which prevented the model from ending its chain prematurely.

The implication for practitioners is that sequential scaling via chain length is not purely a training-time property. You can get meaningful sequential scaling gains on a model that was not originally trained for extended thinking, if you intervene at decode time to prevent premature termination. This is a different tool from what o3 or Claude's extended thinking does — it is a decoding-time intervention layered on a small fine-tune, not a native capability — but it works.

What it does not do: fine-tuning on 1k examples does not give you the ability to generate diverse and independent reasoning trajectories, which is what parallel scaling needs. The s1 result is a data point about sequential scaling efficiency, not an argument against parallel methods.

What breaks

The overthinking trap

Sequential scaling has an accuracy ceiling that is often lower than practitioners expect, because the model starts second-guessing correct conclusions as the chain lengthens. On problems where a 500-token chain gets the right answer, a 4,000-token chain may get a different, wrong answer — the model spent time reconsidering and talked itself out of the correct path.

The operational fix is to run your task-specific benchmark at multiple chain lengths before choosing a production budget. The accuracy-vs-budget curve has a peak, and that peak is not at budget_tokens=max. On classification-adjacent tasks with clear yes/no answers, the peak is often at surprisingly short chains.

Majority voting amplifies systematic bias

At N=32 or N=64, if the model has a consistent error — say it always mishandles negative indices in Python — voting reinforces that error rather than averaging it away. Every sample makes the same mistake, so 64 unanimous wrong answers beats any correct minority. This is not a pathological edge case; it appears in practice on any task where the model has a class of systematic failures.

The detection method: run majority voting and separately run an ORM on the same samples. If the ORM winner and the majority-vote winner consistently disagree, you have a systematic bias problem and voting is the wrong aggregation strategy.

PRM quality is the tree-search ceiling

Tree-based methods are only as good as their PRM. A PRM that scores step 3 of a math proof as "good" when it has a subtle sign error will prune the correct branch and keep the wrong one. Building a reliable PRM for your specific domain requires labeled step-level data that does not exist off-the-shelf for most tasks. Do not use a math PRM to score legal reasoning steps, and do not use a code PRM to score scientific derivations.

Parallel sampling with latency constraints

If you have a latency SLA of 5 seconds, running N=16 samples in parallel on a model that takes 3 seconds per call means you need to run 16 requests simultaneously and some may not complete. The samples that did not complete waste their token budget and return nothing. In practice this means you need a timeout-and-aggregate strategy: take whatever completed within the SLA, vote on those, and fall back to the first completion if fewer than a quorum finish in time.

import asyncio
import anthropic
from collections import Counter

async def best_of_n_with_timeout(
    query: str,
    n: int = 8,
    timeout_seconds: float = 10.0,
    thinking_budget: int = 1500
) -> str:
    client = anthropic.Anthropic()

    # Plain def: the sync client runs in worker threads via asyncio.to_thread
    def single_sample() -> str | None:
        try:
            resp = client.messages.create(
                model="claude-sonnet-4-5",
                max_tokens=4096,
                thinking={"type": "enabled", "budget_tokens": thinking_budget},
                messages=[{"role": "user", "content": query}]
            )
            # Extract the text block (not the thinking block)
            return next(
                (b.text for b in resp.content if b.type == "text"), None
            )
        except Exception:
            return None

    tasks = [asyncio.create_task(asyncio.to_thread(single_sample)) for _ in range(n)]

    done, pending = await asyncio.wait(tasks, timeout=timeout_seconds)
    for t in pending:
        t.cancel()

    answers = [t.result() for t in done if t.result() is not None]
    if not answers:
        raise RuntimeError("All samples timed out")

    # Majority vote on the first 100 chars as a proxy for distinct final answers
    vote = Counter(a[:100] for a in answers)
    best_prefix = vote.most_common(1)[0][0]
    return next(a for a in answers if a[:100] == best_prefix)

MCTS in production is basically never the answer

MCTS on a reasoning task requires serial forward passes whose number is bounded only by your budget. P99 latency of 60–120 seconds is common on hard math problems with MCTS. In a user-facing product this is a non-starter. In a batch scientific computation pipeline, it might be fine. Every team that deploys MCTS in the loop of a real product eventually replaces it with Best-of-N + ORM, because the accuracy ceiling of MCTS is only 5-8 percentage points higher on typical tasks and the latency tail is unacceptable.

The one valid use case is offline evaluation and data generation: run MCTS to generate high-quality reasoning traces for training data, then train the model on those traces. The traces do not need to be generated fast — they need to be correct.

Combining the strategies

The most effective production pattern is not to pick one strategy but to combine them conditionally:

flowchart TD
    Q[Query] --> CLASSIFY{Classify difficulty}
    CLASSIFY -->|Easy / well-defined| SHORT["Short chain\nbudget_tokens: 500"]
    CLASSIFY -->|Medium| MEDIUM["Medium chain\nbudget_tokens: 2000"]
    CLASSIFY -->|Hard / multi-step| PARALLEL["Best-of-N\nN=4-8 + ORM"]
    CLASSIFY -->|Hard + offline / batch| TREE["Beam search\nwidth=4, PRM"]

    SHORT --> ANS1[Answer]
    MEDIUM --> ANS2[Answer]
    PARALLEL --> ANS3[Answer]
    TREE --> ANS4[Answer]

    style SHORT fill:#15803d,color:#fff
    style MEDIUM fill:#0e7490,color:#fff
    style PARALLEL fill:#a855f7,color:#fff
    style TREE fill:#00e5ff,color:#111

This requires a difficulty classifier up front — a fast, cheap call that routes the query. The classifier itself can be a small model or a rule-based system (query length + keyword heuristics + historical task type). The routing cost is negligible compared to the reasoning cost it avoids on easy queries.

The model routing article covers the mechanics of building this kind of routing layer. The key addition for test-time scaling is that routing is not just about which model to use — it is also about which scaling strategy to apply and at what budget.

When to use what

Sequential scaling (longer CoT) is your default for any reasoning model, because it is already built into the model's training. The only decision is the budget. Set it based on your task-specific accuracy-vs-budget curve, not the model's maximum. For most teams, this means testing at budget_tokens of 500, 2,000, 8,000, and 32,000 on a representative sample of your hardest queries, then picking the knee of the curve.

Parallel sampling (Best-of-N) is the right escalation when sequential scaling has plateaued and you have either a deterministic verifier or an ORM for your task. Start at N=4, measure accuracy lift, and only go higher if the lift justifies the cost. Use a rule-based verifier when possible — code execution, unit tests, numeric checking — because it eliminates the ORM quality ceiling entirely.

Tree search belongs in your offline toolbox, not your production path. Use it to generate training data for distillation, to run evaluations on hard benchmark sets where accuracy matters and latency does not, or to validate reasoning traces post-hoc. If your product's latency SLA is under 30 seconds, MCTS should not be in your serving stack.

The underlying principle is that test-time compute is just another resource with a diminishing-returns curve. The right investment depends on where you are on that curve for your specific task, not on which strategy sounds most sophisticated. For the majority of production use cases — code review, document analysis, multi-step planning, agentic tool orchestration — Best-of-4 with a unit-test verifier outperforms elaborate tree search at one-fifth the latency and one-third the cost.

If you want to dig into how the models that enable all of this are trained, the RLVR and GRPO training article is the next stop. If the question is how to integrate test-time scaling into an agent loop with tool calls, see reasoning models plus tools.