Instead of one linear chain, the model explores a tree of candidate reasoning steps, evaluates each, and searches toward the best answer with backtracking.
ConceptWhat it is
Tree-of-Thoughts is a reasoning loop that generalizes chain-of-thought prompting from a single linear trace into a branching search. Instead of committing to one line of reasoning, the model proposes several candidate thoughts (intermediate reasoning steps) at each stage, evaluates how promising each one looks, then explores the strongest branches while pruning or backtracking away from dead ends.
It exists because many hard problems need deliberate search, not a single confident guess. A greedy chain that takes one wrong turn early cannot recover, but a tree keeps several partial solutions alive, compares them, and abandons the ones that stall. The pattern couples an LLM acting as a proposer and a state evaluator with a classic search strategy such as breadth-first or depth-first search plus backtracking.
How it worksThe mechanics
Frame the problem as a sequence of intermediate states. At each frontier state the model generates several candidate next thoughts; an evaluator (the same LLM scoring each state, or a cheap heuristic) rates how likely each is to lead to a solution; a search controller keeps the top candidates, expands the most promising one deeper, and backtracks to a sibling when a branch is judged a dead end. This propose-evaluate-expand cycle repeats until a branch reaches a complete solution or a budget on depth, width, or calls runs out, at which point the best-scoring reasoning path is returned.
At a glanceSee it
The same tree can be walked breadth first, keeping the best k states per level, or depth first with backtracking — two search regimes the core loop leaves implicit.
Zooming into one step: candidate thoughts come from independent sampling or a sequenced proposal, then get ranked either by a per state value score or by a comparative vote across states.
When to use itWhere it fits
- Hard reasoning where a single greedy chain often takes an unrecoverable wrong turn
- Search and planning problems with many partial states to compare, like puzzles or multi-step constraint tasks
- Tasks where you can write a cheap, reliable way to score whether a partial answer is promising
- When accuracy matters more than latency or token cost, and extra compute is an acceptable trade
When NOT to use itLimits & anti-patterns
- Simple or well-structured tasks where plain chain-of-thought or a single call already succeeds
- Latency- or cost-sensitive paths, since branching multiplies the number of model calls
- Problems with no meaningful way to evaluate partial progress, so the search cannot prune
- Open-ended generation with no clear goal state to search toward
Trade-offsAdvantages & costs
Advantages
- Materially stronger on hard reasoning, planning, and search problems than linear prompting
- Backtracking lets it recover from early mistakes instead of committing to one path
- Exposes an explicit, inspectable tree of alternatives and scores, which helps debugging
- Tunable: trade accuracy against cost by adjusting branching width and search depth
Trade-offs & costs
- Expensive: each node means extra generate and evaluate calls, so cost can blow up combinatorially
- Complex to tune, since branching factor, depth limits, and the evaluator all need careful calibration
- Only as good as its state evaluator; a weak scorer misguides the whole search
- Higher latency and engineering overhead than a single call or a simple chain
ExampleIn the real world
Consider the arithmetic puzzle Game of 24: given four numbers, say 4, 9, 10, and 13, combine them with addition, subtraction, multiplication, and division to make exactly 24. A single chain often guesses one combination and fails. Tree-of-Thoughts instead treats each partial calculation as a state. Picking 10 minus 4 to get 6 leaves 6, 9, and 13 still to combine; the model generates several such first moves, judges each remaining set as sure, likely, or impossible, expands the promising ones, and backtracks from sets it deems impossible. It searches this tree until a branch lands on 24, here 6 times the 4 from 13 minus 9, and returns the full arithmetic path rather than a lucky one-shot guess.
ToolsHow to implement it
- The original Tree of Thoughts reference implementation from Yao and colleagues (the princeton-nlp tree-of-thought-llm repository)
- LangGraph, whose state-graph model lets you build the branching, scoring, and backtracking loop explicitly
- Graph of Thoughts, a published generalization that extends the tree into an arbitrary reasoning graph with its own open implementation
Cost & effortWhat it takes
Cost scales with the search, not the answer: roughly branching width times search depth in model calls, split between generating candidate thoughts and evaluating them, so a single query can cost many times a plain chain-of-thought call. Engineering effort is real too, since you must frame the problem as searchable states, build or prompt a reliable evaluator, and tune width, depth, and stopping budgets. Practical deployments cap the frontier, cache and batch evaluations, and reserve the pattern for the minority of hard queries where the accuracy gain justifies the multiplied compute.