What Is Tree of Thoughts and How It Extends Chain-of-Thought Reasoning

Take the Game of 24: given four integers, construct an arithmetic expression that equals 24. A trivially small search space for a human who can try combinations, discover dead ends, and backtrack. GPT-4 with Chain-of-Thought prompting solved it correctly about 4% of the time, per Yao et al. (NeurIPS 2023); the same model guided by Tree of Thoughts solved it 74% of the time. That gap does not come from the model knowing more mathematics — it comes from being given a structurally different process, one that looks more like search than narration.

The Linearity Problem Chain-of-Thought Was Never Designed to Solve

Chain-of-thought prompting operates on a clean assumption: reasoning is sequential. The model externalizes its steps — “first I do this, then I do that, therefore the answer is X” — and the sequence leads to the answer. That assumption is correct for a wide class of problems; it is not correct for problems where the right path only becomes apparent after exploring the wrong ones.

CoT commits; ToT explores.

What is Tree of Thoughts prompting?

Tree of Thoughts, introduced by Shunyu Yao, Dian Yu, and colleagues in “Tree of Thoughts: Deliberate Problem Solving with Large Language Models” (NeurIPS 2023), replaces the linear chain with a search tree. Each node represents a coherent unit of intermediate reasoning — a “thought” — which might be a sentence, a paragraph, or a step in a calculation, depending on how the problem is decomposed.

The framework has four explicit components. Thought decomposition defines how the problem breaks into evaluable units. Thought generation produces candidate thoughts, either by sampling the LLM multiple times or by asking it to explicitly enumerate possibilities. Thought evaluation scores each candidate — via an LLM call that judges whether a partial solution looks promising or unlikely. Search selects which nodes to expand next, applying BFS or DFS over the resulting tree. Each component is a separable design choice; each typically requires at least one additional LLM call to execute.

Compared to ReAct Prompting, which interleaves reasoning with external tool calls and operates over actions in an environment, ToT works entirely within the model’s reasoning space. There is no external environment to query, no action space to enumerate. The search is over intermediate thoughts, not over observations and their consequences — which makes ToT well-suited to problems where all relevant information is already in the prompt and the challenge is combinatorial rather than environmental.

Building and Navigating the Thought Tree

The tree structure is not a fixed template; it is parameterized by the problem’s nature. How many branches to generate per node, how deep to search before pruning, and which traversal strategy to apply are design choices — and the wrong choices compound: an unnecessary branching factor multiplies the call count quadratically; the wrong traversal order can exhaust the inference budget before a valid path is found.

How does Tree of Thoughts explore and evaluate reasoning branches?

Thought generation operates in two modes. Sampling calls the model multiple times with the same prompt, exploiting its stochastic output to produce diverse candidates — useful when the branching space is large and candidates cannot be enumerated. Proposing asks the model to enumerate candidate next steps explicitly (“List three possible continuations”), which works better for structured problems where the branching factor is naturally bounded.

Thought evaluation is where ToT diverges most sharply from Self Consistency sampling. Wang et al. (ICLR 2023) showed that sampling multiple complete reasoning chains and selecting the most consistent final answer by majority vote adds substantial performance over standard chain-of-thought on arithmetic benchmarks — but evaluation happens only at the terminal node. ToT evaluates intermediate states, assigning each thought a heuristic score (promising / likely / impossible) or aggregating votes from multiple LLM judgments on the partial solution. Intermediate evaluation enables backtracking: a branch scored as unpromising can be pruned before the model invests additional calls in expanding it.

Search strategy determines traversal order. Breadth-first search expands all nodes at the current depth before descending — appropriate when solution depth is unknown and early evaluation is reliable enough to prune bad branches quickly. Depth-first search follows one branch to completion before backtracking, which consumes less memory per step but risks spending call budget on paths that will not yield solutions. The original paper applied BFS to the Game of 24, where most invalid branches are detectable early, and DFS to creative writing tasks, where depth was the binding constraint.

The feedback loop between generation, evaluation, and search is the operative mechanism. Evaluation informs which thoughts to expand; search selects which nodes to generate from next; generation produces new candidates that feed back into the tree. That cycle does not exist in chain-of-thought.

Not a smarter model. A different process.

What the Architecture Predicts About When ToT Helps — and When It Doesn’t

The structure makes specific predictions, and they are falsifiable. If a problem has well-defined intermediate states — where a partial solution can be assessed meaningfully on its own — ToT’s intermediate pruning cuts wasted inference and reduces the probability of committing to a losing path early. Mathematical puzzles, formal logic derivations, and planning tasks with checkable subgoals sit in this category. The Game of 24 is a canonical example: arithmetic subexpressions can be evaluated for validity before the final expression is assembled.

If a problem’s quality can only be assessed at the end — a paragraph that lands emotionally, a persuasive argument whose success depends on the full arc, a creative metaphor — intermediate evaluation has little reliable signal to work with. The model’s heuristic judgments about which branch looks “promising” carry enough noise at each node that the errors compound across the tree. In that regime, ToT becomes expensive Prompt Chaining without the structural benefit that justifies its cost.

The call count is structural, not incidental. A single chain-of-thought pass is linear in the number of reasoning steps; a BFS traversal with branching factor b and depth d makes O(b^d) LLM calls. For Game of 24, this is tractable — the problem space is finite and tightly bounded. For open-ended generation with no natural termination condition, the cost structure makes ToT impractical without aggressive pruning guided by a well-specified evaluator.

Orchestration frameworks that enforce typed, validated LLM outputs — including patterns built around Pydantic AI for structured multi-step pipelines — can manage the evaluation loops ToT requires: schema enforcement, retry logic, and aggregation across nodes. What no framework supplies is the evaluation rubric itself. The design question of what “a promising intermediate state” looks like for a given task remains the practitioner’s to specify.

Rule of thumb: If you can define a promising partial solution for your task and an LLM can assess it reliably, ToT’s evaluation mechanism has real signal to search over. If you cannot write down what makes an intermediate step promising, the search is unguided branching at high cost.

When it breaks: ToT’s search quality degrades in direct proportion to the quality of its intermediate evaluations. When evaluation prompts are underspecified, or when the task has no natural intermediate checkpoints, heuristic assessments carry enough noise to mislead the search algorithm — and the noise compounds at each level of the tree. The technique is also sensitive to thought granularity: decompose too coarsely and the tree misses critical decision points; decompose too finely and the node count explodes before useful signal accumulates.

Where Tree Search Went After the Original Paper

Active research extended the tree metaphor in several directions after 2023, per Besta et al. (arXiv). Graph of Thoughts removed the tree constraint to allow cycles — solutions could be combined and re-evaluated rather than simply pruned. LogicTree (2025) applied depth-first proof search specifically to logical reasoning problems, where the validity of intermediate derivations is formally checkable. SSDP (2025) introduced semantic pruning that collapsed semantically equivalent branches before expanding them, achieving substantial speedups. Monte Carlo tree search variants replaced ToT's heuristic evaluator with rollout-based value estimates — borrowing the mechanism that made AlphaGo’s game-tree search tractable.

The convergence with reinforcement learning is not coincidental. Modern frontier models appear to internalize similar search patterns through training rather than implementing them at inference time — a form of Inference Time Scaling that embeds the search into weights rather than prompt scaffolding. For teams considering explicit ToT today, the princeton-nlp reference implementation (Princeton NLP GitHub) carries substantial community interest but has not seen a release since v0.1.0 in July 2023. Search embedded into weights, not prompts, is the direction the field has moved; explicit ToT remains most justified where you need interpretable intermediate states, formally specified evaluation, or domain problems where off-the-shelf reasoning models are unavailable or too expensive.

Compatibility note:

• princeton-nlp/tree-of-thought-llm: Last release v0.1.0, July 2023 — inactive for over three years. Requires an OpenAI API key and was built for the GPT-4 era. Appropriate as a research reference for replicating the paper’s experimental setup; not suitable as maintained production infrastructure. Community LangChain and similar wrappers exist but are third-party implementations without official backing.

The Data Says

Tree of Thoughts addresses a structural problem, not a knowledge problem: chain-of-thought assumes the answer lies along a single path; ToT searches a space of branching possibilities. The empirical gap between the two on combinatorial tasks — 74% versus 4% on Game of 24, per Yao et al. (NeurIPS 2023) — reflects that structural mismatch, not a difference in model capability. The technique is most valuable where intermediate states are evaluable and the evaluation signal is reliable; it is most expensive precisely on the tasks where evaluation is hardest to formalize.