Tree Search Reasoning: Allocating Inference Budget Across Prefixes

Fix one prompt $x$ and a finite rooted tree $\mathcal T$ of possible reasoning prefixes. The root is the empty prefix $\emptyset$. A node is a prefix $h$, taking next step $a$ creates child prefix $ha$, the generator proposes that edge, and the local verifier scores it:

Here $r_\phi(h,a)$ is the process-reward-model style judgment of whether step $a$ is valid after prefix $h$.

At search step $t$, let $\mathcal T_t$ be the visible subtree. The frontier, cumulative local verifier score, deterministic expansion rule, and the max backup used on this page are:

A terminal trace $z$ also has hidden correctness

but $u$ is used only for evaluation, not for search.

Here $b_\phi(h)$ is a prefix heuristic: how promising an unfinished prefix looks before its children are revealed. The $h_t$ line is the simplest deterministic expansion rule: choose the visible unfinished prefix with the highest current path score plus heuristic.

Expanding $h_t$ reveals its children and scores their incoming edges. This is the unit of inference budget.

The backed-up residual value on the visible tree is the $V_t$ recurrence above: terminal nodes contribute no future score, unfinished frontier nodes use their heuristic, and expanded nodes inherit the best visible child continuation.

The recommended visible path follows the best backed-up child:

This is not a convergence theorem or a claim about perfect planning. It means only: among the continuations currently visible under this prefix, choose the one with the highest verifier-backed score.

A compact cost model is

where $A_t(h)$ is the set of generated children revealed when prefix $h$ is expanded.

The contrast with best-of-$N$ is the frontier. Complete-trace search samples $\tau^{(1)},\dots,\tau^{(N)}$ and selects

There is no visible prefix frontier and no bottom-up backup. Tree search replaces "sample another whole trace" with "expand another prefix."

A second method: layerwise pruning

Keep the prefix notation but change the rule. Let $v(h)$ be a given score of a generated prefix $h$: a number attached to that state alone. It is not an edge score, a probability, a continuation estimate or correctness, and it is never added along a path or backed up. Let $k=2$ be the number of children each expanded prefix proposes, $b\in\{1,2\}$ the width and $D=2$ the depth. Start from $S_0=\{\emptyset\}$ and, for $d=1,\dots,D$,

$A(h)$ is revealed only when $h\in S_{d-1}$ is expanded, so no continuation of a pruned prefix in $P_d$ is ever generated or scored. $\operatorname{top}_b$ ranks the whole layer $C_d$ by $v$, not the children of each parent separately, and breaks ties by the lexical order of node IDs. The miniature returns the highest-scoring prefix in $S_D$, with the same tie rule.

Each newly generated prefix costs one generation unit and one scoring unit, $c_{\mathrm{gen}}=c_{\mathrm{score}}=1$. Before layer $d$ the search checks the whole layer against the budget $B$,

using the fixed $k$, never a look at the unseen children. If the check fails, the search stops with no answer; it does not shrink the width or expand part of the layer. The root layer costs $4$ units; width 1 completes at $8$ and width 2 at $12$.

The seven-node tree has root children L ($v=.40$) and R ($.90$); under L, LG ($.95$) and LB ($.20$); under R, RB1 ($.80$) and RB2 ($.70$). Only LG is correct. The search reads scores only; correctness is read after it, to grade what it returned and, because every terminal here is labelled, to diagnose the trace.

• $b=1$, $B=8$: $S_1=\{\mathrm{R}\}$ and $P_1=\{\mathrm{L}\}$, then $S_2=\{\mathrm{RB1}\}$. RB1 is returned, wrong, at cost 8. LG and LB are never generated.
• $b=2$, $B=12$: all six prefixes are generated, $S_2=\{\mathrm{LG},\mathrm{RB1}\}$, and LG is returned, correct, at cost 12. Width changed the cost as well, so this is not a comparison at equal resources.
• $b=2$, $B=8$: after the root layer 4 units remain and the next layer needs 8. There is no answer, and its grade is not applicable.
• $v(\mathrm{L})=.96$ with $b=1$, $B=8$: L is kept and LG returned at cost 8. Changing only an unseen leaf's score at $b=1$ changes nothing, because LG and LB are never scored.
• $v(\mathrm{LG})=.60$ with $b=2$, $B=12$: LG is generated, then pruned at depth 2 behind RB1 and RB2, and RB1 is returned. Generating the correct terminal did not repair its score.

Scores are not path sums. Adding ancestors would give LG $.40+.95=1.35$ against RB1 $.90+.80=1.70$ at width 2 and reverse the return. Unlike $V_t$ above, nothing is backed up.

Source statements, local rules and inference

Source statements. In Yao et al. (arXiv v1, §3 and Algorithm 1), a state is the input together with the thoughts so far. At each step the breadth-first variant generates continuations of every retained state, evaluates the new states and keeps the $b$ highest-valued. Generation may sample thoughts independently or propose them in sequence; evaluation may value each state separately or vote across states, and repeated evaluations can be aggregated. After the last step, Algorithm 1 generates once more from the highest-valued retained state to produce its output. The Game of 24 experiment (§4.1) keeps five states and samples three values for each thought. Lightman et al. (arXiv v1, §§2.1, 2.4 and 2.6, Appendix F.1–F.2) train a process reward model on human labels, each of which judges one written step, in the context of the steps before it, as positive, negative or neutral; supervision stops at the first incorrect step, and the model predicts the current step's label from the prefix that ends there. A complete solution's score is a separate aggregate of those step predictions: the score they adopt multiplies the steps' correctness probabilities, counting neutral with positive, and their best-of-$N$ evaluation selects a complete solution by that score before its final answer is graded.

Local rules. The miniature keeps layerwise proposal, evaluation and global top-$b$ retention. It substitutes hand-written children and scores for model calls, reads each score once instead of sampling or voting, and adds a lexical tie rule and the whole-layer budget above. It omits the final generation and returns a depth-2 terminal directly. Its costs count abstract node operations, not the paper's model calls, tokens, latency or money. This is not a reproduction of either paper, and no result from either is reproduced here.

Inference. A label judges the current written step in its preceding context, as positive, negative or neutral; the whole-solution product is a separate aggregate of such step predictions. Neither target by itself establishes that an unfinished prefix can reach a correct terminal under a specified generator, depth and budget, and the hand-set $v$ here is not a trained reward model. Using a step-label predictor as the state score in this search would need evidence that its ranking of unfinished prefixes tracks observed reachability under that generator and budget, such as graded terminals from continuing many scored prefixes on held-out prompts. This is not evidence that process reward models cannot guide search.

What a trace identifies. A search trace records the generated, kept and pruned prefixes with the scores the search read, the return and the units charged. That alone identifies a whole-layer budget stop. Grading the return uses one more fact, the returned terminal's label. Saying that a correct alternative was pruned before generation, or generated and not returned, needs more still: independently known labels for those alternatives, or counterfactual evidence such as continuing the pruned prefixes and grading their terminals. The miniature has a label for every terminal, so it can make that diagnosis. A real trace without such evidence can leave the reason for a wrong return unidentified: the same width-1 trace fits LG being correct (pruning loss), RB2 being correct (misselection) or no terminal being correct. The labels never enter the search.