Trajectory Search

An agent can make every local decision look reasonable and still lose the task.

A coding agent sees that test_checkout_redirect is failing, concludes there is an implementation bug in checkout.py, and then behaves impeccably for twenty steps: it reads the file, edits it, runs the tests, repairs the new failures its edit introduced, rewrites the patch, and runs the tests again. Every one of those steps is defensible given the step before it.

The run still fails, because the fixture was stale.

The machinery built so far can make this run safer and more legible without solving the root problem. Candidate generation samples several complete proposals and picks one, which helps only when complete alternatives are affordable. Critique and revision improve one candidate, which cannot rescue a route whose initial hypothesis was wrong. Planning represents one intended route, and progress tracking can correctly report that the route is advancing even while it advances toward the wrong explanation.

The missing capability is narrower than any of these:

Preserve several partial trajectories long enough for evidence to distinguish them.

That is search, in the sense used here. Not web search, and not database search. Search over possible futures of the agent itself.

The word doing the work there is partial. The runtime does not wait for every branch to produce a finished answer before deciding which branches deserve another unit of compute.

Deciding that, repeatedly and under a budget, is the whole subject of this chapter.

1. Prefix-level scaling, and why it is a distinct regime

A 2026 review of test-time scaling separates inference into three structural regimes, and the distinction gives this chapter a precise place to stand.[6]

    flowchart LR
    subgraph S[sequential]
        s0[s0] --> s1[s1] --> s2[s2] --> s3[s3]
    end
    subgraph L[leaf-level]
        r1((root)) --> a[answer A]
        r1 --> b[answer B]
        r1 --> c[answer C]
        a & b & c --> sel[select]
    end
    subgraph P[prefix-level]
        r2((root)) --> A1[A1] --> A2[A2]
        A1 --> A3[A3]
        r2 --> B1[B1]
        r2 --> C1[C1] --> C2[C2]
    end
  

Leaf-level scaling and prefix-level scaling are often discussed as if they were the same trick at different sizes. They are not. Best-of-N commits compute to N complete trajectories before selection, which may be affordable when a trajectory is one model call and prohibitive when it is forty tool invocations against a real environment. Prefix-level scaling instead evaluates partial trajectories and can stop allocating further compute to branches that no longer justify continuation.

That can produce a much better cost profile on long trajectories, at the price of needing something Best-of-N does not: a way to evaluate work that is not finished.

Trajectory search is prefix-level test-time scaling over partial agent states.

2. When branching is justified, and what it is not

Search is not automatically better than a single well-run loop, and adding it to a system that does not need it buys latency and a new failure surface. Four conditions should roughly hold: several plausible paths genuinely exist, early choices strongly constrain later outcomes, partial paths can be evaluated by something, and the extra inference or environment work is affordable.

Drop any one of them and a simpler mechanism wins. If the next step is deterministic, search adds machinery without adding capability. If complete answers are cheap to sample, leaf-level selection is sufficient and much easier to reason about. If the first attempt is usually nearly right, targeted revision beats breadth.

Search earns its place when several futures must remain alive at once.

It is worth being precise about what that does and does not overlap with, because three neighbouring mechanisms get conflated with it constantly.

The last row is the one that catches teams out. A system that generates three branches and then revises them all toward the same answer has paid for breadth and kept none of it.

3. A node is a resumable state, not a sentence

A branch labelled “this approach seems promising” is not a search node.

It is a note. A node must carry enough state to continue the branch without reconstructing it from prose.

from dataclasses import dataclass, field
from typing import Any

@dataclass
class SearchNode:
    id: str
    parent_id: str | None
    depth: int
    state: dict[str, Any]
    env_checkpoint: str | None = None
    action: dict[str, Any] | None = None
    observation: dict[str, Any] | None = None
    score: "NodeScore | None" = None
    terminal: bool = False
    pruned_by: "SearchStage | None" = None
    prune_reason: str | None = None
    cost: float = 0.0
    metadata: dict[str, Any] = field(default_factory=dict)

The state object typically carries the goal, current hypothesis, established facts, constraints, artifacts, remaining budget and any memory IDs in play. The test is blunt:

If a branch cannot be resumed from its node, the tree is a diagram rather than a data structure.

env_checkpoint is separate from state on purpose, and it is the field most often missing.

Search assumes competing futures can be considered independently. That assumption is free for pure reasoning and expensive for agents that mutate things. Suppose branch A edits parser.py and branch B then reads parser.py. Branch B has silently inherited branch A’s world, the two are no longer alternatives, and every downstream score measures a state that no search policy chose.

The tree is fiction, and nothing in the trace says so.

The previous chapter on recovery already established the stronger contract: a resumable point needs an agent-side state and an aligned environment state. Search generalises that requirement from one abandoned trajectory to several live trajectories. Isolation may use copy-on-write state, Git worktrees, containers, database transactions, separate browser sessions, or checkpoint-and-restore, but the invariant is the same:

branch A state + branch A environment
must never leak into
branch B state + branch B environment

The checkpoint identifier therefore belongs on the node rather than in a global.

There is one more trap. Two nodes are equivalent only if every difference that could affect their future has been intentionally excluded. A fingerprint that remembers facts but forgets the modified files, browser session, permissions or remaining budget can merge different futures into one. Section 10 makes state equivalence an application-supplied policy rather than pretending a generic tuple can know what matters.

4. Branch freely over proposals, once over side effects

Some branches cannot be executed speculatively at all. Three refunds cannot be issued, three emails sent, or three production deployments performed, with the best one kept afterwards.

The important boundary is therefore not before validation. Validation, authorization and precondition checks are side-effect-free runtime decisions and can be applied to every candidate. The single-valued boundary is real execution.

    flowchart TD
    P[propose candidate continuations] --> A{prepare each proposal:<br/>parse, validate, authorize,<br/>check preconditions}
    A -->|Rejected| R[record rejection stage]
    A -->|Accepted| S[inspect / simulate / preview<br/>in isolation]
    S --> E[score candidate futures]
    E --> C[rank and collapse frontier]
    C --> K{re-check current<br/>authorization + preconditions}
    K -->|Rejected| N[try next ranked candidate]
    N --> K
    K -->|Accepted| X[execute once]
    X --> O[observation]
    style X fill:#f6c8c8,stroke:#b04a4a
  

The single red box is the design constraint.

Everything above it must be side-effect-free or isolated from the real environment. It is not necessarily cheap: a sandboxed test suite can cost minutes, and a simulation can consume significant compute. Reversible is the important property, not inexpensive.

Search may branch over proposed, validated or simulated effects even when the real world must remain single-valued.

The action boundary therefore runs twice when necessary. It filters impossible or forbidden proposals before speculative evaluation, and the winning proposal is checked again immediately before commitment because permissions, budgets or environmental preconditions may have changed while search was running.

Search chooses among candidate futures. It never grants authority to execute one.

5. Five policies, not one algorithm

Most confusion about agent search comes from naming an algorithm and inheriting its assumptions. Beam search, best-first search and MCTS really are different algorithms, but each bundles answers to the same underlying policy questions.

For agent engineering, separating those questions is often more useful than beginning with the algorithm name.

    flowchart LR
    F[frontier] --> EX[expansion]
    EX --> EV[evaluation]
    EV --> AL[allocation]
    AL --> PR[pruning]
    PR --> TE{termination?}
    TE -->|no| F
    TE -->|yes| CM[commit]
  

A fixed-width beam is one particular allocation-and-pruning policy. Best-first search is another. MCTS adds a particular tree policy, value update rule and exploration mechanism. The chapter does not claim those algorithms are interchangeable; it claims the five responsibilities remain inspectable inside whichever one is chosen.

That decomposition matters because the policies can be measured and ablated separately. The next five sections take one each.

6. Expansion: distinct futures, not distinct strings

A nominal branch factor of five means nothing if all five are paraphrases. Consider an expansion that returns inspect parser.py, open parser.py, examine parser implementation, read parser.py carefully and inspect delimiter code in parser.py. Five branches were generated. One region of the search space was explored, and the budget was spent five times over.

Diversity improves when expansion is given semantic roles rather than a temperature. For debugging: the strongest current hypothesis, a competing hypothesis, an information-gathering action, a conservative fallback, and a challenge to a current assumption. For incident response the roles become layers — application, infrastructure, data, recent change. For research they become stances toward the evidence: support the current explanation, seek disconfirming evidence, investigate a competing explanation, test whether a premise is false.

None of that is worth arguing about without a number attached.

from collections import Counter
from typing import Callable, Sequence

def unique_branch_ratio(
    children: Sequence[SearchNode],
    signature: Callable[[SearchNode], object],
) -> float:
    if not children:
        return 0.0
    return len({signature(c) for c in children}) / len(children)

def effective_branch_factor(
    children: Sequence[SearchNode],
    signature: Callable[[SearchNode], object],
) -> float:
    return unique_branch_ratio(children, signature) * len(children)

The signature is where the judgement lives: an action kind plus its target, a hypothesis label, or a fingerprint of the resulting state. What matters is that it is a function you can change and re-measure.

A configuration running branch_factor = 8 at a unique branch ratio of 0.25 has an effective branching factor near two.

Raising N to sixteen will roughly double the bill and leave the effective width exactly where it was.

7. Evaluation: promise and progress are different signals

Terminal states admit direct questions. Did the tests pass, did the transaction complete, does the artifact satisfy the specification. A partial state usually admits none of them, because it is neither correct nor incorrect yet.

It is more or less worth continuing.

So the evaluator estimates something closer to: if I spend more compute here, how promising is this branch, and what measurable progress has it already made? AgentPRM makes essentially this distinction for agent decisions, separating promise from progress rather than treating intermediate actions as simply correct or incorrect.[4]

Two branches make the distinction concrete. Branch A has a hypothesis that strongly explains the observed failure and has attempted no patch. Branch B turned one failing test green and three unrelated tests red. A single undifferentiated score hides the fact that A has promise without progress while B has progress with regressions.

from enum import IntEnum

class EvidenceTier(IntEnum):
    JUDGE = 0            # model judgement
    PROCESS_MODEL = 1   # learned value / process model
    DOMAIN_SIGNAL = 2   # task-specific deterministic signal
    ENVIRONMENT = 3     # direct observation from the task environment

@dataclass(frozen=True)
class NodeScore:
    promise: float
    progress: float
    regressions: int = 0
    violations: int = 0
    tier: EvidenceTier = EvidenceTier.JUDGE
    uncertainty: float = 0.0
    cost: float = 0.0

    @property
    def blocked(self) -> bool:
        return self.violations > 0

    @property
    def rank_key(self) -> tuple:
        return (
            not self.blocked,
            self.progress - 0.5 * self.regressions,
            self.promise,
            int(self.tier),
            -self.cost,
        )

That rank_key is an illustrative policy, not a universal scale. A model confidence of 0.9, a test-pass fraction of 0.9, and a learned value of 0.9 are not automatically commensurate because they share a decimal representation. Production systems should calibrate the signals they combine on held-out trajectories.

The hard rule is simpler: a hard constraint violation is not a slightly worse score, and direct observations should update the state variables they actually establish rather than merely adding points to an evaluator.

The evidence tier is therefore attribution as much as ranking information. When two branches are otherwise close, stronger external evidence is a sensible tie-breaker; it should not be used to pretend incomparable measurements have a universal total order.

Prefer evidence generated by the environment over confidence generated by the model, without pretending every evidence source is calibrated to every other one.

This also guards against the quietest search failure: self-confirmation. When one model generates the branches, scores the branches and explains the winner, the runtime has produced the appearance of diversity over a shared bias.

Three branches evaluated only by their own author are still one evidence source. Diversifying the evidence—deterministic checks, independent tools, environment state, a separate verifier or an authoritative source—matters more than diversifying the wording.

8. Allocation: spend where the decision is unresolved

A fixed beam keeps k branches at every depth, which is easy to explain and rarely optimal. There is no reason the useful width should be constant. Bug diagnosis may want six hypotheses at depth zero and one at depth three; another task may need the opposite.

Depth is only a rough proxy for what actually varies: how unresolved the decision is.

Consider two vote distributions over the next action. Eight votes for read_file against one each for search_code and run_tests look settled. Four, three and three look contentious.

from math import log

def uncertainty(votes: Counter[str]) -> float:
    """Normalised vote entropy in [0, 1]. 0 = unanimous."""
    total = sum(votes.values())
    if total == 0 or len(votes) < 2:
        return 0.0
    entropy = -sum(
        (n / total) * log(n / total)
        for n in votes.values()
        if n
    )
    return entropy / log(len(votes))

def top_two_margin(votes: Counter[str]) -> float:
    ranked = [n for _, n in votes.most_common(2)]
    if len(ranked) < 2:
        return 1.0
    return (ranked[0] - ranked[1]) / sum(votes.values())

Vote entropy and top-two margin are disagreement signals, not truth meters. Ten identical wrong samples have zero entropy. One surviving candidate after nine others fail the action boundary also has no measured disagreement, but that is not evidence that the surviving proposal is uniquely good.

A search policy should therefore distinguish agreement among adequate alternatives from absence of alternatives. Equating either one with correctness can confidently starve the branch that would have contained the fix.

The useful claim is narrower: when these statistics are empirically predictive on the task distribution, they can tell the runtime where additional sampling is more likely to buy information. CATTS reports exactly this pattern for web agents, using vote-derived uncertainty to allocate extra inference selectively and outperform uniform scaling with fewer tokens in its evaluated settings.[5]

That leads to two safeguards:

1. Calibrate uncertainty against downstream outcomes. Do not assume entropy predicts difficulty because it has the right shape.
2. Preserve a minimum exploration floor. A low-uncertainty decision can still be wrong, especially early in a run when all samples share the same missing evidence.

    flowchart LR
    E[explore<br/>wide, cheap, informational] --> D[discriminate<br/>evidence separates branches]
    D --> X[exploit<br/>narrow, deep, transformational]
  

Breadth and depth answer different uncertainties, and the useful regime can change during a task rather than being fixed for it.

Breadth asks which hypothesis deserves survival. Depth asks whether the surviving hypothesis can actually be carried through.

The regime shift also changes which actions are worth taking. Actions divide roughly into informational—read a file, run a targeted test, inspect metrics, query status—and transformational—edit a file, restart a service, submit a form, write to a database. If the agent is torn between a cache bug and a database lock, an immediate edit advances one branch by a step, while a diagnostic query that separates the two may collapse half the frontier.

When transformations are expensive or irreversible, cheap discriminating information is often the better buy. A search policy that scores only immediate task progress will miss that value.

9. Pruning: where a good search goes to die

The generator produces the successful branch. The evaluator scores it. The runtime prunes it. The search fails.

Generation succeeded. Search policy failed later.

Those need different fixes, and end-to-end success cannot tell them apart. The same decomposition used for candidate selection and memory recall applies to the tree, but the stage meanings have to be explicit.

from enum import StrEnum

class SearchStage(StrEnum):
    REACHABLE = "reachable"      # a successful route is expressible
    GENERATED = "generated"      # expansion produced that route/prefix
    DISTINCT = "distinct"        # survived deduplication
    EVALUATED = "evaluated"      # received a usable partial-state score
    SURVIVED = "survived"        # was not pruned while still viable
    COMPLETED = "completed"      # received enough depth to terminate
    VERIFIED = "verified"        # terminal result passed external verification

@dataclass(frozen=True)
class SearchTrial:
    """One labelled task with a known successful trajectory or prefix."""

    task_id: str
    reachable: bool = False
    generated: bool = False
    distinct: bool = False
    evaluated: bool = False
    survived: bool = False
    completed: bool = False
    verified: bool = False

    @property
    def flags(self) -> tuple[tuple[SearchStage, bool], ...]:
        return (
            (SearchStage.REACHABLE, self.reachable),
            (SearchStage.GENERATED, self.generated),
            (SearchStage.DISTINCT, self.distinct),
            (SearchStage.EVALUATED, self.evaluated),
            (SearchStage.SURVIVED, self.survived),
            (SearchStage.COMPLETED, self.completed),
            (SearchStage.VERIFIED, self.verified),
        )

    def validate(self) -> None:
        reached_false = False
        for stage, reached in self.flags:
            if reached_false and reached:
                raise ValueError(
                    f"{self.task_id}: {stage} cannot be reached after an earlier loss"
                )
            reached_false |= not reached

    @property
    def lost_at(self) -> SearchStage | None:
        self.validate()
        for stage, reached in self.flags:
            if not reached:
                return stage
        return None

def _fraction(numerator: int, denominator: int) -> float:
    if denominator == 0:
        return float("nan")

    return numerator / denominator


def oracle_generated_success(trials: Sequence[SearchTrial]) -> float:
    """Fraction of reachable tasks where search generated the known-good route."""
    reachable = [t for t in trials if t.reachable]

    return _fraction(
        sum(1 for t in reachable if t.generated),
        len(reachable),
    )


def selected_success(trials: Sequence[SearchTrial]) -> float:
    """Fraction of reachable tasks converted into externally verified success."""
    reachable = [t for t in trials if t.reachable]

    return _fraction(
        sum(1 for t in reachable if t.verified),
        len(reachable),
    )


def search_gap(trials: Sequence[SearchTrial]) -> float:
    """Generated opportunity that the remainder of search failed to convert."""
    generated = oracle_generated_success(trials)
    selected = selected_success(trials)

    if generated != generated or selected != selected:
        return float("nan")

    return generated - selected


def pruning_regret(trials: Sequence[SearchTrial]) -> float:
    """Known-good generated routes pruned before completion."""
    generated = [t for t in trials if t.reachable and t.generated]

    return _fraction(
        sum(
            1
            for t in generated
            if t.lost_at is SearchStage.SURVIVED
        ),
        len(generated),
    )


def allocation_regret(trials: Sequence[SearchTrial]) -> float:
    """Known-good generated routes kept alive but starved before completion."""
    generated = [t for t in trials if t.reachable and t.generated]

    return _fraction(
        sum(
            1
            for t in generated
            if t.lost_at is SearchStage.COMPLETED
        ),
        len(generated),
    )

Adding COMPLETED matters. Without it, “the branch was alive when the budget expired” and “the branch finished and failed verification” collapse into the same boolean.

The stages point at different subsystems:

oracle_generated_success is the prefix-search analogue of oracle@N: did search create the opportunity at all? selected_success asks whether the system converted that opportunity into a verified result.

Online, pruning_regret and allocation_regret are counterfactual and therefore not directly observable. In a benchmark environment, continue a controlled sample of pruned or starved branches after the point where production search would have stopped them. That experiment estimates how often the policy killed a future that would have succeeded.

Populating SearchNode.pruned_by and prune_reason at the moment of the decision is what makes the diagnosis reconstructable afterwards.

10. Termination: collapsing the frontier

Premature commitment is the failure this chapter exists to fix. Perpetual exploration is its mirror image: another hypothesis, another branch, another diagnostic, no commitment. The trace looks industrious.

Nothing ships.

A termination policy needs conditions that can be inspected: all but one branch violated hard constraints; a terminal branch passed the verifier; the ranking margin stayed stable through another discriminating expansion; the estimated marginal gain fell below marginal cost; or the search budget ended and the runtime must return control.

Model confidence alone is not one of those conditions.

Deduplication belongs beside termination because it changes whether the frontier is genuinely diverse. Two trajectories can arrive at the same effective state by different routes.

Continuing both pays twice for one future—but only if they are actually equivalent.

from collections.abc import Hashable, Mapping
from typing import Callable

StateKey = Callable[[Mapping[str, object]], Hashable]

def coding_state_key(state: Mapping[str, object]) -> Hashable:
    """Example only: include every field that can change future behaviour."""
    return (
        tuple(sorted(state.get("facts", ()))),
        tuple(sorted(state.get("completed", ()))),
        tuple(sorted(state.get("artifacts", ()))),
        state.get("workspace_revision"),
        state.get("environment_version"),
        state.get("goal_phase"),
        state.get("remaining_budget"),
    )

There is no universal state_fingerprint() for agents.

If a key omits a future-relevant variable, deduplication becomes corruption. Two browser nodes with different authenticated sessions are not equivalent because their visible text happens to match. Two coding nodes with different working-tree changes are not equivalent because their facts sets match. Two nodes with different remaining budgets may not be equivalent even if every other field is.

The state key is therefore part of the search protocol and deserves tests of its own.

Even with a correct key, first seen is not automatically best. If two routes reach the same effective state, keep the representative with the better evidence-adjusted score or lower accumulated cost rather than whichever happened to be generated first.

Once equivalent paths can merge, the structure is no longer strictly a tree. Graph of Thoughts formalised a broader graph-structured reasoning view with aggregation and reuse of intermediate states.[2] A production agent does not need that framework to take the useful engineering lesson:

Do not pay twice to explore the same effective future, and do not merge futures until equivalence is actually justified.

11. The loop, assembled

The five policies compose into a search runtime that is still small, but a production-safe skeleton needs a few more guarantees than a toy beam loop: node budgets must be hard, empty frontiers must be representable, terminal nodes must not be expanded, and equivalent states must compete rather than obey first-seen order.

from enum import StrEnum
from typing import Hashable, Protocol

class SearchEnd(StrEnum):
    POLICY_STOP = "policy_stop"
    FRONTIER_EXHAUSTED = "frontier_exhausted"
    MAX_DEPTH = "max_depth"
    MAX_NODES = "max_nodes"

@dataclass(frozen=True)
class SearchResult:
    best: SearchNode | None
    nodes: tuple[SearchNode, ...]
    reason: SearchEnd

class SearchPolicies(Protocol):
    def expand(self, node: SearchNode, width: int) -> list[SearchNode]: ...
    def evaluate(self, node: SearchNode) -> NodeScore: ...
    def width_for(self, node: SearchNode) -> int: ...
    def keep(self, scored: list[SearchNode]) -> list[SearchNode]: ...
    def should_stop(self, frontier: list[SearchNode]) -> bool: ...
    def state_key(self, node: SearchNode) -> Hashable: ...

    def prefer_equivalent(
        self,
        new: SearchNode,
        old: SearchNode,
    ) -> bool: ...

def search(
    root: SearchNode,
    policies: SearchPolicies,
    *,
    max_depth: int = 5,
    max_nodes: int = 50,
) -> SearchResult:
    if max_nodes < 1:
        raise ValueError("max_nodes must be at least 1")

    if root.score is None:
        root.score = policies.evaluate(root)

    if root.parent_id is not None:
        raise ValueError("root node must not have a parent")

    frontier = [root]
    nodes = [root]
    known_ids = {root.id}

    best_by_state: dict[Hashable, SearchNode] = {
        policies.state_key(root): root
    }

    for _ in range(max_depth):
        if policies.should_stop(frontier):
            best = max(frontier, key=lambda n: n.score.rank_key)
            return SearchResult(best, tuple(nodes), SearchEnd.POLICY_STOP)

        candidates = [node for node in frontier if node.terminal]
        expandable = [node for node in frontier if not node.terminal]

        remaining = max_nodes - len(nodes)
        if remaining <= 0:
            best = max(frontier, key=lambda n: n.score.rank_key)
            return SearchResult(best, tuple(nodes), SearchEnd.MAX_NODES)

        for node in expandable:
            width = max(0, policies.width_for(node))
            width = min(width, remaining)
            if width == 0:
                continue

            proposed = policies.expand(node, width)[:width]

            for child in proposed:
                if len(nodes) >= max_nodes:
                    break

                if child.id in known_ids:
                    raise ValueError(f"duplicate search node id: {child.id}")

                if child.parent_id != node.id:
                    raise ValueError(
                        f"{child.id}: parent_id does not match expanded node {node.id}"
                    )

                if child.depth != node.depth + 1:
                    raise ValueError(
                        f"{child.id}: child depth does not follow parent"
                    )

                known_ids.add(child.id)
                child.score = policies.evaluate(child)
                nodes.append(child)

                key = policies.state_key(child)
                incumbent = best_by_state.get(key)

                if incumbent is not None:
                    if not policies.prefer_equivalent(child, incumbent):
                        child.pruned_by = SearchStage.DISTINCT
                        child.prune_reason = "equivalent state, weaker representative"
                        continue

                    incumbent.pruned_by = SearchStage.DISTINCT
                    incumbent.prune_reason = "replaced by better equivalent state"

                best_by_state[key] = child
                candidates.append(child)

            remaining = max_nodes - len(nodes)
            if remaining <= 0:
                break

        candidates = [
            node
            for node in candidates
            if node.pruned_by is None
        ]

        if not candidates:
            scored = [n for n in nodes if n.score is not None]
            best = max(scored, key=lambda n: n.score.rank_key) if scored else None

            return SearchResult(
                best,
                tuple(nodes),
                SearchEnd.FRONTIER_EXHAUSTED,
            )

        kept = policies.keep(candidates)
        kept_ids = {node.id for node in kept}

        for child in candidates:
            if child.id not in kept_ids and child.pruned_by is None:
                child.pruned_by = SearchStage.SURVIVED
                child.prune_reason = "removed by pruning policy"

        frontier = kept

        if not frontier:
            scored = [n for n in nodes if n.score is not None]
            best = max(scored, key=lambda n: n.score.rank_key) if scored else None
            return SearchResult(
                best,
                tuple(nodes),
                SearchEnd.FRONTIER_EXHAUSTED,
            )

        if len(nodes) >= max_nodes:
            best = max(frontier, key=lambda n: n.score.rank_key)
            return SearchResult(best, tuple(nodes), SearchEnd.MAX_NODES)

    best = max(frontier, key=lambda n: n.score.rank_key) if frontier else None
    return SearchResult(best, tuple(nodes), SearchEnd.MAX_DEPTH)

The runtime deliberately knows very little about why a node is good. That belongs to the policies. What the runtime owns are invariants: budgets are real, terminal nodes do not expand, every node is accounted for, equivalent states compete explicitly, and every exit has a name.

Branch isolation is still a contract of expand. For environment-changing agents, expand must resume the parent checkpoint into an isolated environment before producing each child. If it cannot guarantee that, the search is valid only over proposals or simulations and must collapse before real execution.

A more sophisticated implementation can use a priority queue, asynchronous workers, MCTS statistics or learned allocation. Those change scheduling. They do not remove these invariants.

12. Committing once, at the boundary

The generic loop is safe for pure reasoning and isolated environments. For irreversible real actions, production code searches over prepared proposals and previews, then executes one action once.

The action boundary should filter candidates before preview, and the winner should be checked again at commitment time.

from collections.abc import Callable

def search_then_commit(
    state,
    propose: Callable[[object, int], list[object]],
    prepare: Callable[[object], "Decision"],
    preview: Callable[[object, "Action"], object],
    evaluate: Callable[[object, "Action", object], NodeScore],
    execute: Callable[["Action"], object],
    vote_key: Callable[["Action"], str],
    *,
    base_width: int = 2,
    extra_width: int = 3,
    threshold: float = 0.35,
):
    def consider(width: int):
        accepted = []
        for raw in propose(state, width):
            decision = prepare(raw)
            if not isinstance(decision, Accepted):
                continue

            simulated = preview(state, decision.action)
            score = evaluate(state, decision.action, simulated)
            accepted.append((raw, decision.action, score))
        return accepted

    candidates = consider(base_width)

    votes = Counter(
        vote_key(action)
        for _, action, _ in candidates
    )

    insufficient_candidates = len(candidates) < base_width
    unresolved_choice = uncertainty(votes) > threshold

    if extra_width > 0 and (insufficient_candidates or unresolved_choice):
        candidates += consider(extra_width)

    candidates.sort(
        key=lambda item: item[2].rank_key,
        reverse=True,
    )

    for raw, _prepared_action, _score in candidates:
        # Re-run the boundary immediately before the real side effect.
        current = prepare(raw)
        if isinstance(current, Accepted):
            return execute(current.action)

    return None

preview is required to be side-effect-free or isolated. If a capability has no safe preview, omit speculative execution and score the prepared proposal using whatever non-committing evidence exists.

The second prepare is not redundant. Search may take long enough for authorization, budgets or environment preconditions to change. The candidate that was admissible when generated is only a candidate at commitment time.

Search chooses what to propose next. The action boundary decides whether that proposal is still allowed. Execution happens once.

13. What the tree costs

A branch score of 0.82 is not interpretable without knowing what establishing it cost. One branch needed a single read-only call. Another needed four model calls, three tool calls and a sandbox execution. Node accounting should cover model tokens and calls, tool calls, wall time, sandbox cost, and any consumption of an irreversible-risk budget.

With costs attached, the useful question becomes marginal:

What did the next unit of search buy?

The naive expectation is that beam 2 loses to beam 4 loses to beam 8. Several effects break that monotonicity. A weak evaluator gets more chances to be fooled as the search space grows. Branches become redundant. Search budget can steal compute from final verification. Longer trajectories create more opportunities for ordinary execution error. And the proxy-overoptimisation problem from the candidate-selection chapter reappears inside the tree: a larger candidate space gives a flawed evaluator more opportunities to find something that scores well for the wrong reason.

An illustrative curve of the shape worth measuring:

The numbers are illustrative. The experiment is the point, and the object being sought is the quality–compute frontier rather than the largest tree.

Beam-8 is strictly worse than beam-4 in that example on every reported column.

Raw success also flatters expensive systems, so normalise the bill:

def cost_per_verified_success(
    cost_per_run: float,
    verified_success_rate: float,
) -> float:
    if verified_success_rate <= 0:
        return float("inf")
    return cost_per_run / verified_success_rate

A system at 80% success and 1 unit per run costs 1.25 units per verified success. A system at 90% and 4 units per run costs about 4.44. The second may be the right system for a high-value incident and the wrong one for millions of low-value requests.

Verification frequency deserves the same treatment. Scoring every branch after every small step can dominate the bill; scoring rarely lets bad branches consume compute before anyone notices. Process-reward and agent-search work increasingly treats intermediate evaluation as a resource to place where it changes allocation rather than as a free constant.[3][4] Reasonable triggers include meaningful state changes, uncertainty spikes, the point before an expensive transformation, or the point where branches begin to diverge materially.

That is an allocation policy to measure, not a universal schedule.

14. The protocol is part of the system

A single-path agent trace records what happened.

A search trace must also record what nearly happened, or the search becomes unauditable the moment it finishes.

Per node, retain at least the identifier and parent, depth, state key, environment checkpoint, proposed action, observation or preview result, score components, evidence tier, uncertainty, accumulated speculative cost, whether it was expanded, and, if it was pruned, the stage and reason. With that, four questions become answerable: where the winning branch diverged, why a promising branch was pruned, which signal dominated its score, and how much compute went to futures that were never committed.

The configuration needs the same treatment. Search has enough degrees of freedom that two runs described as “beam search” can differ by multiples in cost and behavior.

from dataclasses import asdict
import hashlib
import json

@dataclass(frozen=True)
class SearchProtocol:
    model_id: str
    evaluator_id: str
    temperature: float
    branch_factor: int
    beam_width: int
    scoring_frequency: str
    prune_threshold: float
    uncertainty_threshold: float
    max_nodes: int
    max_depth: int
    tool_budget: int
    state_key_version: str
    isolation_mode: str
    seed: int | None

    def fingerprint(self) -> str:
        payload = json.dumps(asdict(self), sort_keys=True)
        return hashlib.sha256(payload.encode()).hexdigest()[:12]

The state_key_version and isolation_mode belong beside temperature and beam width because they can change the result just as dramatically. A run that merges browser sessions under one key is not the same inference system as a run that keeps them separate.

The 2026 test-time-scaling review makes this broader point explicitly: the evaluated object is the entire inference protocol, not merely the base model, and comparisons are uninterpretable when compute accounting and search procedure are omitted.[6]

A benchmark number without the protocol that produced it is not a reproducible result.

15. Test each policy separately

End-to-end success cannot tell you which of the five policies is failing, so build controlled fixtures for each one.

The termination row matters. A search can have excellent expansion, evaluation and pruning and still waste half its budget after the decision is already settled, or stop one expansion before the evidence would have separated the winner. Those are policy errors, not noise around the final score.

Then run the ablation, holding base model, tool set, task set, final verifier, context and cost envelope fixed:

single trajectory
→ Best-of-N complete trajectories
→ fixed-width search over partial states
→ + objective partial-state evidence
→ + adaptive allocation
→ + equivalence-aware deduplication

Each rung has to earn its complexity against the one below it.

The most informative task set is built around the failure search is supposed to fix: the first plausible route is deliberately misleading. In coding, the obvious file is not the cause. In research, the salient hypothesis is contradicted by primary evidence. In a browser, the first visible button is not the valid next step. In operations, the recent deployment correlates with the incident and did not cause it.

If prefix-level search cannot beat a single-trajectory agent on tasks designed around premature commitment, the implementation has not earned the extra machinery.

16. What search bought

The runtime can now hold several possible futures open, score them with explicit evidence, allocate extra compute where a decision remains unresolved, merge futures only under a declared equivalence relation, and collapse to one action at a boundary that still validates it.

The failure this chapter opened with—twenty competent steps down a path chosen by the first mistaken hypothesis—is now decomposable. Did expansion ever generate the viable route? Did deduplication erase it? Did the evaluator make it uncompetitive? Did pruning kill it? Did allocation starve it? Or did it complete and fail verification?

“Search failed” has become several testable statements.

None of that is a claim that branching makes an agent intrinsically smarter. It is a narrower engineering claim: prefix-level search can improve decisions when useful alternatives genuinely exist, branch state is isolated, partial futures can be evaluated with signals that add information, and additional compute follows evidence rather than habit. Branch diversity, evaluator quality, state equivalence, isolation and economics each cap the benefit independently.

There is also a limit search cannot remove.

A branch can score well at every depth. The frontier can collapse cleanly. The evaluator can be calibrated, the margin stable, the protocol reproducible, and the model can report that the task is complete.

None of those facts establish that the user’s goal was achieved.

Search has answered:

Which future should we commit to?

It has not answered:

What evidence entitles the runtime to call the resulting world a success?

That remaining boundary is the subject of the next chapter.

Research roots

This chapter is an engineering synthesis rather than a survey, and the citations are selective. These works anchor the mechanisms and, more importantly, the cautions.

1. Yao et al. — Tree of Thoughts: Deliberate Problem Solving with Large Language Models (NeurIPS 2023). Explores intermediate reasoning states with lookahead and backtracking; cited as the canonical early example of branching before completion.
   https://arxiv.org/abs/2305.10601
2. Besta et al. — Graph of Thoughts: Solving Elaborate Problems with Large Language Models (AAAI 2024; preprint 2023). Generalises tree-structured reasoning into graph operations including aggregation and reuse of intermediate states; cited for the state-merging discussion in section 10.
   https://arxiv.org/abs/2308.09687
3. Choudhury — Process Reward Models for LLM Agents: Practical Framework and Directions (2025 preprint). Studies agent process rewards, exploration, reward shaping, test-time scaling and reward hacking; cited for the broader case that intermediate evaluation is part of agent search rather than merely terminal grading.
   https://arxiv.org/abs/2502.10325
4. Xi et al. — AgentPRM: Process Reward Models for LLM Agents via Step-Wise Promise and Progress (2025 preprint). Evaluates intermediate agent decisions through goal proximity and progress, and applies the resulting process model to step-level search; cited for the promise/progress split in section 7.
   https://arxiv.org/abs/2511.08325
5. Lee et al. — Agentic Test-Time Scaling for WebAgents (2026 preprint). Finds diminishing returns from uniform per-step sampling and introduces confidence-aware allocation using vote entropy and top-two margin; cited for the adaptive allocation discussion in section 8.
   https://arxiv.org/abs/2602.12276
6. Hariri et al. — Test-Time Scaling in Reasoning LLMs: Inference Regimes, Evaluation, and Reproducibility (2026 preprint). Distinguishes sequential, leaf-level and prefix-level inference and argues that the complete inference protocol is the evaluated system; cited for the regime table and protocol record.
   https://arxiv.org/abs/2608.04001

Next: Evidence and Verification

Search produces a preferred trajectory. Preference is not verification.

The signals used to rank that trajectory may already include valuable external information: test results, environment observations, deterministic checks, independent tools or authoritative sources. Those signals can justify spending more compute on one branch than another and can justify stopping the search once one future clearly dominates its alternatives.

They do not automatically establish the user’s goal. A partial-state evaluator answers which future currently deserves continuation or commitment? Final verification asks a different question: what evidence is sufficient to record that the resulting world actually satisfies the goal?

Confusing those questions is expensive because an evaluator can rank one branch correctly relative to its competitors while every branch still fails the task.

The next chapter makes that final boundary explicit. It separates a completion proposal, an evaluator score, runtime observations and goal-directed evidence, then asks what must be established before the runtime is entitled to record success — including what happens when the verification mechanism itself is incomplete, stale or under attack.