Tree of Thoughts,
explained.

Rung 2's samples are independent and complete. Each chain is generated start to finish with no knowledge of the others, nothing is evaluated until it is over, and a chain that goes wrong in its second step still consumes the tokens to finish. Left-to-right generation cannot take anything back.

The change is to make reasoning a search. Generate several candidate next thoughts rather than one, have the model evaluate them — is this step promising, is this state still solvable — and then explore the resulting tree deliberately, breadth-first or depth-first, backtracking out of branches judged dead. The units that differ from rung 2: intermediate evaluation, which rung 2 has none of, and the ability to abandon partial work, which rung 2 cannot do because it has no notion of partial work.

The gains are largest exactly where that matters — problems needing a commitment early that is only revealed to be wrong later, where one greedy pass is nearly hopeless and independent sampling is barely better because every sample repeats the same early mistake. On the arithmetic puzzle the paper uses as its showcase, the reported move is from the low single digits to roughly three quarters.

Autoregressive generation is pure System 1: fast, associative, one token after another, no revision. Chain-of-thought made the stream longer and more structured, and self-consistency hedged it by sampling many streams — but every stream is still a one-way street. Nothing in the machinery lets the model consider two alternatives, compare them, or undo a commitment.

For some problems that's fatal by construction. Take Game of 24 — combine 4, 9, 10, 13 with arithmetic to make 24. Humans solve it by trial and error: try 10+13=23, leaving 4, 9, 23… nothing reaches 24, dead end, back up, try 13−9=4, leaving 4, 4, 10, and (10−4)×4=24 ✓. A model that can't back up has to guess the winning line on the first try. GPT-4 with CoT managed 4%.

ToT's first move is choosing the right granularity. Searching over individual tokens would be astronomically branchy; searching over whole solutions is just self-consistency. In between sits the thought: a coherent intermediate step — one equation in a math puzzle, one plan paragraph in an essay, one word placement in a crossword.

It's a deliberate reunion of the two AI traditions: the LLM supplies what search always lacked (rich step generation and judgment), and search supplies what LLMs lacked (exploration and the right to change your mind).

At each frontier node, the model proposes several candidate next thoughts. An evaluator scores each one's promise. A search algorithm — plain BFS keeping the best few candidates per depth, or DFS diving deep and retreating on failure — decides what to expand next and what to prune.

Backtracking is the emotional core of the method: a bad branch costs a retreat, not the whole attempt. The model gets what every human problem-solver takes for granted — the ability to say "that didn't work" and still win.

Classical search needs a heuristic function, hand-built per problem. ToT's second insight: the LLM is the heuristic. Prompt it to assess a partial solution — "can these remaining numbers still reach 24: sure, likely, or impossible?" — and you get a usable value function for free, in natural language, on any domain.

Self-evaluation is noisy, and that's fine: a search heuristic doesn't need to be right, only informative enough to rank siblings. Judging "is this partial state promising?" is reliably easier than generating the full correct solution — the same generator-verifier gap that later powers process reward models and LLM-as-judge everywhere.

Every proposal and every evaluation is a model call. A Game of 24 solve runs ~100 calls; deep DFS problems more. ToT is test-time compute spent aggressively — orders of magnitude beyond a single chain — plus orchestration code to manage the tree, the prompts, and the frontier.

It also needs problems with decomposable steps and evaluable partial states. Where a task is one intuitive leap, or progress can't be judged midway, the tree collapses back into an expensive chain. ToT is a specialist's scalpel, not a default decoding mode.

ToT completed the trilogy that defined LLM reasoning's external era: CoT (make thinking visible) → self-consistency (sample and vote) → ToT (search deliberately, with evaluation and backtracking). Together they proved the capability ceiling wasn't the model — it was the inference procedure.

The final act absorbed the lesson: reasoning models trained with RL now explore, self-check, hit dead ends and say "wait, let me reconsider" inside a single generation — the tree internalized into the stream. When o1-class models budget more thinking for harder problems, they're running ToT's playbook without the scaffolding. The scaffold retired; the idea won.

Tree of Thoughts comes from Shunyu Yao and colleagues at Princeton and Google DeepMind, and was published at NeurIPS 2023. It wraps a frozen language model in a search program. The paper frames any instance of it as four design choices, and each of its three tasks makes those choices differently.

1. Decompose the problem into thoughts. A thought must be small enough that the model can propose good, varied candidates, and big enough that the model can judge whether it is promising. In Game of 24 a thought is one intermediate equation, so a solution is three thoughts deep. In creative writing it is a whole plan for the passage. In 5×5 mini crosswords it is one word placed on the board.
2. Generate candidate thoughts. Two generators. Sample draws k independent thoughts from a chain-of-thought prompt, which suits rich thought spaces such as a paragraph-long plan, where independent samples are naturally different. Propose asks for several next steps in one prompt, which suits narrow spaces such as one equation or one word, where independent samples would repeat each other.
3. Evaluate states. Two evaluators. Value prompts the model to judge one state on its own, as a score or a class. For Game of 24 the classes are sure, likely and impossible, sampled three times per state, and the model reaches them by trying a few quick completions and by noticing when the remaining numbers are obviously too big or too small. Vote shows the model several states at once and asks which is most promising, which suits states that are hard to score alone, such as choosing the best of five writing plans.
4. Search. Breadth-first search keeps the b best states at each depth and suits shallow trees: Game of 24 with b = 5, and creative writing. Depth-first search follows the most promising state until it reaches a solution or the evaluator rules the state impossible, then backtracks to the parent. It suits crosswords, where one bad word can make the board unsolvable several placements later.
5. Return the answer. Once a full-depth state exists, the model writes the final output from it: the equation that makes 24, the passage written from the winning plan, or the filled board.

The three task setups

Game of 24. 100 hard games taken from an online collection of 1,362, ranked by how long people took to solve them. Success means a valid equation that uses each of the four numbers exactly once and equals 24. GPT-4 is the model throughout, sampling at temperature 0.7.

Creative writing. Given four random sentences, write a coherent four-paragraph passage whose paragraphs end with those sentences. The tree is two levels deep: the model writes five plans and votes on the best, then writes five passages from that plan and votes again.

Mini crosswords. 5×5 boards from a puzzle site, solved by depth-first search. The model proposes words for open clues with a confidence for each, fills the most promising one, and prunes the branch as soon as it judges any remaining clue impossible to fill.

The baselines use the same model and examples: input-output prompting, chain-of-thought prompting, self-consistency over chain-of-thought samples and, for some tasks, an iterative self-refinement loop. So any gap comes from the search, not from a different model or a better prompt.

The paper writes the breadth-first version as a loop over depth t. Expand every kept state with the generator G, score the new states with the evaluator V, and keep the b best:

The two evaluators differ in what the model sees at once:

• [s, z] — a state extended by one new thought z
• k — candidates generated per state; b — the breadth kept, 5 for Game of 24
• pθ^value — the model prompted to rate one state alone: sure, likely or impossible in Game of 24
• s* — the state the model picks when shown all of S together

At b = 1 the search keeps only the single best-rated state, which is a greedy chain steered by the evaluator, and Game of 24 success fell from 74% to 45%. Raising b raises cost in proportion, since every kept state is expanded and every child is evaluated. The depth-first variant swaps the argmax for a threshold: a state valued at v_th or below is pruned and the search backtracks to its parent.

Every result uses GPT-4. Game of 24 is scored on 100 hard games. The two oracle rows count a game as solved if any of 100 samples is correct, which no real system could know without checking every one.

Two comparisons carry the argument. Tree of Thoughts at b = 5 beats even the oracle that picks the right answer out of 100 chain-of-thought samples, so the gain is not just more attempts. And breadth matters: keeping one state instead of five drops success from 74% to 45%.

Where chains fail. The error analysis found that about 60% of chain-of-thought samples had already failed after the first step, the first equation, which is exactly the commitment a left-to-right chain cannot revisit.

The other two tasks. In creative writing, GPT-4 scored coherence on a 1 to 10 scale at 6.19 for input-output prompting, 6.93 for chain of thought and 7.56 for Tree of Thoughts, and human judges preferred Tree of Thoughts over chain of thought in 41 of 100 pairs against 21. In mini crosswords, Tree of Thoughts got 60% of words right and solved 4 of 20 games, where the prompting baselines solved almost none. Ablations that removed pruning or removed backtracking both scored clearly lower at the word level, so both parts of the search earn their cost.

The cost is much worse than rung 2's and is admitted: every node needs generation and evaluation, so a search of any breadth costs many model calls per problem, with latency to match. The self-evaluation is also the weak link — the search is only as good as the model's judgement of a partial solution, and that judgement is less reliable than its ability to generate, precisely on the hard problems where pruning matters most.

There is also a scope limit that the showcase tasks obscure: the method needs a task that decomposes into discrete, evaluable intermediate states. Puzzles have those. Open-ended writing and most real questions do not, and the framework has nowhere to put its evaluator.

How it held up: as a framing that mattered more than the implementation. Establishing that reasoning could be search — with generation, evaluation and backtracking as separable components — reorganised how people thought about the problem. What did not persist is the external scaffold: rungs 4 and 5 train the search behaviour into the model, so that backtracking and reconsideration appear inside one generated stream rather than being orchestrated by a program around it. This rung's ideas won; its architecture was absorbed.

Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.

It began as a prompting trick and ended as a training objective. Read in order, the progression from "let's think step by step" to a model trained to.

1. 1Chain-of-Thought Prompting2022
2. 2Self-Consistency2022
3. 3Tree of Thoughts2023
4. 4OpenAI o12024
5. 5DeepSeek-R12025

All 110 papers, in 19 ladders →