Tree of Thoughts,
explained.

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 (13−9)=4… dead end, back up, try (10−4)=6, 6×(13−9)=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.

Not an increment — a different regime. The same model, the same weights, an 18× jump purely from changing how inference explores. Creative writing (plan several outlines, pick the best, then write) and 5×5 mini-crosswords (DFS with backtracking) showed the same shape: wherever solving means trying and revising, the tree crushed the chain.

Why is 24 so hard for a linear chain? Because the winning move often looks wrong until the end. The classic set 3, 3, 8, 8 has no clean route — the only solution runs through a fraction:

A greedy chain that commits to "combine the two biggest" never tries dividing by a fraction and dead-ends. A tree search backtracks until it finds it.

That's the whole difference, and it's runnable: the solver below plays Game of 24 both ways — a single greedy chain versus a backtracking tree search — on the same numbers.

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 takes chain-of-thought and gives it a search structure. Instead of committing to one line of reasoning, the model explores a tree: generate several candidate next steps, evaluate how promising each looks, and expand the good branches while pruning the dead ends — classic search (BFS/DFS) applied to reasoning. When a problem needs exploration and backtracking rather than a single forward pass, this is a big jump.

The two new ingredients over CoT are branching and evaluation. Branching lets the model consider multiple paths from any state; evaluation asks the model to judge partial progress ("does this branch look like it's heading somewhere?") so search effort concentrates where it's likely to pay off. That self-evaluation is what turns a blind expansion into a guided one.

It shines on problems where greedy step-by-step reasoning gets stuck — puzzles, planning, and games (the paper's Game of 24 is the canonical demo) where an early wrong turn dooms the whole chain and you need to abandon it and try another. A linear chain can't backtrack; a tree can, which is exactly why it solves cases CoT fails.

The cost is real: exploring many branches with evaluation at each node multiplies the calls, so ToT is a heavyweight tool for genuinely hard problems, not everyday queries. Its lasting influence is conceptual — it reframed reasoning as search over a space of thoughts, a lens that shows up in modern agent planning, deliberate tree/graph search over LLM steps, and the broader move toward spending structured inference-time compute to solve harder problems.