Tree of Thoughts

Chain-of-thought reasoning is a single straight line: think step 1, step 2, step 3, answer. It’s a huge improvement over answering blind — but it has no way back. If the model commits to a wrong move at step 1, every later step builds on the mistake and the whole chain fails. There’s no branching, no comparing alternatives, no undo.

Tree of Thoughts (ToT) reframes reasoning as deliberate search. At each step the model proposes several candidate next thoughts, evaluates how promising each is, and explores the tree of possibilities — keeping the strong branches, pruning the weak ones, and backtracking out of dead ends. It’s the difference between guessing a path through a maze and actually searching it.

Three ingredients

ToT is built from three pieces, each usually the LLM playing a different role:

1. Thought generator. From the current partial state, propose k candidate next steps (e.g. “sample 3 possible next moves” or “propose 3 ways to continue”).
2. State evaluator. Have the model judge each candidate state — as a value (score 0–1), a classification (sure / maybe / impossible), or by voting across samples. This self-assessment is the heuristic that guides the search.
3. Search algorithm. A classic BFS / DFS / beam search over the tree: expand promising states, keep the best b at each level, prune the rest, and backtrack when a branch evaluates as hopeless.

Why branching beats a greedy chain

The failure mode of chain-of-thought is early commitment. Suppose the most attractive-looking first step actually dead-ends, while a less obvious one hides the real solution. A greedy chain takes the shiny step and is stuck; ToT explores both and finds the winner:

# Each edge's score is the LLM's evaluation of that thought.
tree = {
    "root": [("A", 0.6), ("B", 0.5)],
    "A":    [("A1", 0.2), ("A2", 0.3)],   # A looked best up front but dead-ends low
    "B":    [("B1", 0.7), ("B2", 0.9)],   # B's branch hides the real winner
}

# Greedy chain-of-thought: always take the highest-scoring next thought, never look back.
node, path = "root", ["root"]
while node in tree:
    node, _ = max(tree[node], key=lambda c: c[1])
    path.append(node)
greedy_value = 0.3                          # score of the final edge taken (root->A->A2)

# Tree of Thoughts: expand the tree, evaluate every leaf, keep the best.
leaves = [(name, s) for parent in tree for name, s in tree[parent] if name not in tree]
best_name, best_value = max(leaves, key=lambda x: x[1])

print("greedy CoT  :", " -> ".join(path), f"(value {greedy_value})")
print(f"ToT (search): root -> B -> {best_name} (value {best_value})")
print(f"ToT finds {best_value} vs greedy {greedy_value}  ->  {best_value / greedy_value:.1f}x better")

greedy CoT  : root -> A -> A2 (value 0.3)
ToT (search): root -> B -> B2 (value 0.9)
ToT finds 0.9 vs greedy 0.3  ->  3.0x better

The greedy chain never reconsiders its 0.6-vs-0.5 choice, so it’s trapped in A’s weak subtree. ToT’s search reaches B2’s 0.9 — the kind of recovery that lets it solve puzzles (the classic Game of 24), planning problems, and constraint puzzles where a single chain-of-thought reliably fails.

The cost, and when it’s worth it

Search isn’t free. Generating k thoughts and evaluating each, at every level, means many more LLM calls — a branching factor b over depth d is b^d states if unpruned (beam/pruning keeps it bounded, but it’s still multiples of a single chain). So ToT is a deliberate trade: spend far more tokens to crack problems that genuine search unlocks. For straightforward questions a single chain-of-thought is cheaper and just as good — reserve ToT for problems that actually need exploration, lookahead, and backtracking.

In one breath

• Chain-of-thought is a single path with no backtracking — an early wrong step dooms the whole chain.
• Tree of Thoughts makes reasoning a search: a thought generator proposes k next steps, a state evaluator (the LLM scoring/voting sure/maybe/impossible) judges them, and a BFS/DFS/beam search keeps promising branches, prunes weak ones, and backtracks from dead ends.
• It beats greedy CoT on problems needing exploration (the demo: ToT finds 0.9 where greedy commits early and dead-ends at 0.3) — Game-of-24, planning, constraint puzzles.
• The cost is many more LLM calls (b^d unpruned), so it’s a deliberate trade — use it only when the problem genuinely needs search, not for simple Q&A.
• LATS generalizes ToT to agents: MCTS over ReAct trajectories with value backprop and reflection.

Quick check

Next

ToT spends tokens to search; ReWOO spends as few as possible by planning once. The mechanism that lets a tree (or agent) learn from a failed branch is Reflection.