Thought Nodes, Evaluators, and Search Strategies: Inside the Tree of Thoughts Framework

The number that started this research line was the gap between 4 and 74. Using chain-of-thought, GPT-4 solved the Game of 24 — combine four numbers with arithmetic to reach 24 — at a 4% success rate. Using Tree of Thoughts with the same model and the same task, that number jumped to 74% (Yao et al. 2023). The model’s weights did not change. The structure around the prompts did.

Chain-of-thought gives the model a single thread. Tree of Thoughts gives it branches — and, critically, a mechanism for evaluating which branches are worth following before committing resources to them.

The Four Primitives That Define a Tree of Thoughts System

The name sounds intuitive, but the framework requires unpacking four distinct components that the original NeurIPS paper defines with precision. Understanding them separately is what separates practitioners who know why Tree of Thoughts works from those who treat it as a fancier chain-of-thought prompt.

Think of it like a decision tree in classical machine learning versus a random walk. Both produce paths through a problem space. Only one systematically evaluates and prunes as it goes.

What are the main components of a Tree of Thoughts framework?

The framework has four configurable components (Yao et al. 2023):

Thought decomposition. The problem is broken into units — “thoughts” — that represent intermediate reasoning steps. A thought is not a full solution; it is a partial move in a search space. For the Game of 24, a thought might be “use 4 × 6 = 24” as a candidate sub-operation. Decomposition quality depends on how well you define what constitutes a valid intermediate step. Too coarse and the tree is too shallow to help; too granular and the branching factor becomes prohibitive.

Thought generation. Two strategies exist, as confirmed in the reference implementation (princeton-nlp GitHub). The sample method draws multiple independent candidate thoughts from a chain-of-thought prompt — i.i.d. samples suited to broad, open-ended search spaces. The propose method generates thoughts sequentially through an explicit “propose prompt,” where the model is asked to suggest next moves in order; this reduces redundancy in constrained tasks where the search space has identifiable structure. The right choice depends on whether your problem has a small number of high-quality moves (propose) or a large uncertain space (sample).

State evaluation. After generating candidates, the framework needs to decide which branches merit further exploration. Two evaluation modes exist: value, where the model scores each state categorically — for example, “sure / maybe / impossible” — and vote, where multiple evaluations are aggregated and majority judgment selects which state advances. Value scoring works when individual states carry clear quality signals; vote aggregation is more reliable when any single evaluation might be noisy. Evaluator quality determines whether ToT succeeds — a strong generator paired with a weak evaluator still commits to poor paths.

Search algorithm. Given generated thoughts and evaluated states, a navigation strategy determines which branches get explored next. This is where BFS and DFS enter, covered in the next section. The key structural point is that the search algorithm is a separate, configurable dimension — the same generator and evaluator can be paired with different search strategies depending on problem structure.

Navigating the Branches: Breadth-First vs. Depth-First

Choosing a search algorithm is not a stylistic preference. It is a structural decision that determines what the system can observe across candidate solutions and what it can afford to explore. In tree-of-thoughts, each node evaluation requires an LLM call — meaning branching factors and evaluation depth carry direct token cost implications that do not exist in standard graph traversal.

The adapted versions of BFS and DFS in this framework are designed to account for the asymmetry between cheap thought generation and costly state evaluation.

What is the difference between BFS and DFS search in Tree of Thoughts?

Breadth-first search (BFS) explores all candidate thoughts at the current depth level before advancing to the next. At each step, BFS generates b candidates and evaluates all of them, selecting the best k to expand further. This allows comparison of multiple promising branches before committing to any of them. The Game of 24 implementation used BFS with parallel state evaluation — comparing multiple partial arithmetic paths simultaneously at each step — which is why the evaluator could identify which branches approached the target before resources were spent on dead ends (Yao et al. 2023).

BFS is appropriate when the most promising branches are not obvious early and premature commitment would be costly. The tradeoff: BFS scales with beam width and branching factor. A wide BFS over a large search space generates many candidate thoughts per step, with proportionally more LLM calls. For short-horizon problems with well-defined intermediate states, BFS is usually the correct choice.

Depth-first search (DFS) commits to the most promising branch and explores it vertically — going deeper along a single path until the system reaches a solution or a dead end, at which point Backtracking returns to the last viable branching point and the next candidate gets explored. DFS generates far fewer parallel evaluations at each step, which reduces per-step cost. The tradeoff is sensitivity to evaluator quality: if the branch scored as “most promising” at the first step is actually poor, DFS spends significant depth on it before recovering.

DFS is most appropriate for problems with deep solution paths and where early evaluation can reliably separate promising from poor branches — multi-step proof search or creative plan generation, where going deep on a plausible direction is more valuable than comparing breadth.

Not BFS by default. Not DFS by default. The right choice follows from the problem’s depth-to-solution and the reliability of your state evaluator at early depth levels.

What the Framework Assumes You Already Know

Tree of Thoughts is not a drop-in upgrade for chain-of-thought. It is an orchestration layer that wraps multiple LLM calls inside a search procedure. Reaching for it without understanding the prerequisites tends to produce implementations that either replicate what Self Consistency already achieves more cheaply, or introduce search overhead with no corresponding benefit.

What do you need to understand before using Tree of Thoughts prompting?

Chain-of-thought as baseline. ToT extends CoT; it does not replace it. Before adding a tree structure, you need to understand why chain-of-thought fails on your specific task. If the model commits prematurely to incorrect intermediate steps, a branching search may help. If the model fails because of knowledge gaps — because the training distribution did not cover the problem domain — more branches will not fix it. The failure mode determines whether the architecture fits.

Self-consistency as the cheaper alternative. Self-consistency generates multiple independent reasoning paths and takes a majority vote over final answers. It shares ToT’s multi-path intuition without the evaluation-and-steering layer. For many tasks — particularly classification and multiple-choice problems with clearly verifiable final answers — self-consistency recovers most of the performance gain at a fraction of the orchestration complexity. The standard recommendation: try self-consistency first; add the full tree structure only when self-consistency plateaus (Wang et al. 2022).

Prompt Chaining as the orchestration primitive. ToT requires passing partial states between LLM calls — thought generation depends on prior state, evaluation depends on generated thoughts, next-step expansion depends on evaluation. Understanding how to maintain and pass structured state across multiple LLM calls is a prerequisite before implementing a ToT loop.

What ReAct Prompting offers by comparison. ReAct interleaves reasoning and action traces, but along a single thread without branching or backtracking. If your use case involves external tool calls — search queries, code execution, API lookups — ReAct is a simpler starting point. ToT becomes relevant when the reasoning itself, not the actions, needs to branch and be independently evaluated.

Framework maturity. The official research implementation, princeton-nlp/tree-of-thought-llm (princeton-nlp GitHub), has not had a release since July 2023; treat it as a reference architecture, not a maintained library. Current agent frameworks like Pydantic AI support building multi-step ToT-style workflows. Note that pydantic-ai v2.0.0, released June 23, 2026 (PyPI), introduced breaking changes from v1 — check the migration guide before building on it.

Worth noting as of mid-2026: native reasoning models — including OpenAI’s o-series and Anthropic’s extended thinking — perform tree-like search internally. For many tasks, selecting a reasoning model substitutes for manual ToT orchestration. Manual ToT remains relevant when observable, steerable, inspectable intermediate branches are a hard system requirement.

What the Architecture Predicts — and Where It Fails

Tree of Thoughts makes specific predictions about when it should outperform chain-of-thought. These follow from the structure of the search, not only from benchmark numbers.

If your problem has intermediate steps that can be evaluated before the final answer is known, and the model regularly commits to wrong intermediate steps in chain-of-thought, and the space of plausible branches at each step is small enough to evaluate affordably — ToT is likely to help. The Game of 24 satisfies all three conditions: each arithmetic sub-operation produces an evaluable partial state, standard CoT performance was demonstrably poor, and the branching factor per step was manageable.

If evaluation quality is poor — if the model cannot reliably distinguish “sure” from “maybe” in its state scoring — both search strategies degrade. BFS evaluates all branches at roughly equal value and cannot identify which to expand; DFS commits to whichever branch happens to score highest by noise. The search produces more LLM calls for the same output quality as vanilla chain-of-thought.

The evaluator is the bottleneck, not the generator.

When it breaks: ToT underperforms chain-of-thought on tasks where the model cannot reliably score intermediate state quality — either because the problem lacks clear partial-solution signals, or because the reasoning gap between generated and correct intermediate steps is too large for the model's self-scoring to detect. It also fails when the branching factor is too high to evaluate affordably: a problem requiring many branches per step and many steps deep implies a very large number of LLM calls per depth level.

The Data Says

The 4% to 74% gap on the Game of 24 is the clearest evidence that Tree of Thoughts’ benefit is architectural — it comes from the search structure, not from a stronger model. That benchmark involves a specific combination: well-defined intermediate states, measurable partial progress, and a manageable branching factor. When those conditions hold, Tree of Thoughts outperforms any amount of prompt tuning on a single reasoning chain. When they do not hold, the added orchestration cost produces no corresponding gain. The four components — decompose, generate, evaluate, search — are not a recipe to apply blindly. They are a diagnostic framework for understanding what your reasoning chain is missing.