Language Models2023intermediate11 min read

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

شجرة الأفكار: الحل المتأنّي للمسائل باستخدام النماذج اللغوية الكبيرة

Yao, S. · Yu, D. · Zhao, J. · Shafran, I. · Griffiths, T. L. · Cao, Y. · Narasimhan, K. — NeurIPS

The problem

Large language models generate text left-to-right, one at a time, committing to each choice irrevocably. This "System 1" style works for fluent text but fails on tasks that need exploration, planning, or backtracking — like multi-step math puzzles, creative writing under constraints, or crossword solving. helps by adding intermediate reasoning steps, but it still follows a single linear path with no way to branch, compare alternatives, or undo a bad early decision. When GPT-4 uses chain-of-thought on the Game of 24, it solves only 4% of puzzles.

The contribution

(ToT): a general framework that lets LLMs explore multiple reasoning paths organized as a tree. Each node is a "thought" — a coherent chunk of text serving as an intermediate step. The LM itself generates candidate thoughts, evaluates them via self-assessment (value prompts or voting), and a search algorithm (BFS or DFS) navigates the tree with lookahead and backtracking. No is required — only . On the Game of 24, ToT raises GPT-4's success rate from 4% to 74%.

The impact

ToT bridged classical AI search with modern LLMs, showing that "System 2" deliberation dramatically improves reasoning. It inspired a wave of tree-search reasoning methods and directly foreshadowed the scaling behind OpenAI o1. The idea that LLMs can serve as both the generator and the evaluator inside a search loop became a foundational design pattern for .

Imagine you're playing chess. A beginner makes the first move that looks decent and hopes for the best — that's standard prompting. A slightly better player thinks a few moves ahead in a straight line — that's chain-of-thought. But a grandmaster considers multiple opening moves, mentally plays out each branch several moves deep, prunes the hopeless lines, and backtracks to try a different variation — that's Tree of Thoughts.

The key shift: instead of committing to one chain of reasoning, the model maintains a tree of possibilities, evaluates them, and navigates toward the most promising solution.

The problem: LLMs think in straight lines

Language models generate text autoregressively — each token depends only on the tokens before it. Once a word is produced, there is no going back. This is fine for fluent conversation, but catastrophic for problems that require exploration.

Consider the Game of 24: given four numbers, find arithmetic operations that produce 24. With input "4 9 10 13", a left-to-right model might start with "4 + 9 = 13" — and immediately lock itself into a dead end, because repeating 13 violates the rules. A human would try a different first step. The model cannot.

Chain-of-thought prompting partially addresses this by eliciting intermediate reasoning steps. But CoT still follows a single path with no branching. improves things by sampling multiple chains and taking a majority vote — but within each chain there is still no local exploration, and voting only works when the answer space is small (like multiple choice).

The authors draw on dual-process theory from cognitive science: LLMs operate in a fast, automatic "System 1" mode, but many problems demand the slow, deliberate exploration of "System 2" thinking.

Open in Lab

Compare how IO, CoT, CoT-SC, and ToT each handle problem solving. Click each approach to see its reasoning structure.

The demo wakes as you arrive…

The framework: four design decisions

ToT frames any problem as a search over a tree, where each node is a state $s = [x, z_1, \ldots, z_i]$ — the original input plus the thoughts generated so far. Building a ToT system requires answering four questions:

1. Thought decomposition — How big is each "thought"? It could be a single word (crosswords), an equation line (Game of 24), or a whole paragraph plan (creative writing). The granularity must be small enough for the LM to generate diverse candidates, yet large enough to evaluate meaningfully.

2. Thought generation — How to produce candidate next thoughts? Two strategies: (a) i.i.d. sampling from a CoT prompt (good when the thought space is rich, like paragraph plans), or (b) sequential proposal via a "propose prompt" that lists several candidates at once (better when the space is constrained, like equation steps).

3. State evaluation — How to judge which states are promising? Again two strategies: (a) Value each state independently by prompting the LM to classify it as "sure / likely / impossible", or (b) Vote across states by asking the LM to compare several candidates and pick the best. The LM serves as its own heuristic function — flexible, requiring no training, and more sample-efficient than learned evaluators.

4. Search algorithm — How to navigate the tree? The paper explores breadth-first search (BFS), which keeps the top-b states at each depth, and depth-first search (DFS), which dives deep but backtracks when the evaluator deems a state hopeless.

Open in Lab

Explore how ToT builds and navigates a tree of thoughts. Click nodes to expand, evaluate, or prune branches.

The demo wakes as you arrive…

Formal description

Before we see the formulas, let's understand what they capture. Standard prompting maps input $x$ directly to output $y$ . CoT introduces intermediate thoughts $z_1, \ldots, z_n$ sampled sequentially in a single chain. ToT generalizes this: at every step, it generates multiple candidate thoughts, evaluates them, and uses a search algorithm to decide which branches to explore.

y \sim p_\theta^{\text{IO}}(y \mid x)

Standard IO prompting — direct input to output — The simplest baseline: the LM maps input x to output y in a single pass, guided only by task instructions or few-shot examples.

z_i \sim p_\theta^{\text{CoT}}(z_i \mid x, z_{1 \ldots i-1}), \quad y \sim p_\theta^{\text{CoT}}(y \mid x, z_{1 \ldots n})

Chain-of-thought — a single sequential reasoning chain — Each thought zi is sampled given the input and all previous thoughts. The output depends on the complete chain. This is a tree of depth n and breadth 1.

S'_t = \{[s, z] \mid s \in S_{t-1},\; z \in G(p_\theta, s, k)\}, \quad S_t = \arg\!\max_{S \subset S'_t,\, |S|=b} \sum_{s \in S} V(p_\theta, S'_t)(s)

ToT-BFS — breadth-first search over thought states — At each step t, expand every state in the frontier by generating k candidate thoughts (using generator G). Evaluate all resulting states with the value function V. Keep only the top b states. Repeat until depth T, then extract the answer from the best final state.

BFS vs DFS: choosing the right search

The choice between BFS and DFS depends on the problem structure:

BFS (used for Game of 24, Creative Writing) keeps the b best states at each level. It works well when the tree is shallow (few steps to solution) and early pruning is reliable. Think of it as maintaining a "beam" of promising paths — similar to in machine translation, but over semantic thought units instead of tokens.

DFS (used for Mini Crosswords) dives deep along the most promising branch, and backtracks when the evaluator flags a state as impossible. It works well when the tree is deep, the solution lies at a leaf, and wrong branches can be detected early. DFS trades breadth for depth — it uses less memory but might miss solutions on unexplored branches.

A key insight: ToT is a generalization of previous methods. IO prompting is a tree of depth 1 and breadth 1. CoT is depth n, breadth 1. CoT-SC is depth n, breadth k with voting at the final step only. ToT allows arbitrary depth, breadth, and evaluation at every step.

Open in Lab

Toggle between BFS and DFS to see how each algorithm explores a thought tree differently.

The demo wakes as you arrive…

The idea in code

Tree of Thoughts BFS — the core search looppython

Simplified to show the idea — not the real implementation.

def tot_bfs(x, lm, generate, evaluate, steps=3, beam=5, k=5):
    """Tree of Thoughts with breadth-first search."""
    # Start with just the input as the only state
    frontier = [x]

    for step in range(steps):
        # 1. EXPAND: generate k candidate thoughts per state
        candidates = []
        for state in frontier:
            thoughts = generate(lm, state, k)  # e.g. "propose next equation"
            for t in thoughts:
                candidates.append(state + " " + t)

        # 2. EVALUATE: score every candidate via LM self-assessment
        scores = evaluate(lm, candidates)  # e.g. "sure/likely/impossible"

        # 3. SELECT: keep only the top-b most promising states
        ranked = sorted(zip(scores, candidates), reverse=True)
        frontier = [c for _, c in ranked[:beam]]

    # Final step: extract the answer from the best state
    return generate(lm, frontier[0], 1)[0]

# IO prompting   = tot_bfs(x, steps=0)          → depth 0, breadth 1
# CoT prompting   = tot_bfs(x, steps=n, beam=1)  → depth n, breadth 1
# CoT-SC (k=100) = sample 100 CoTs, majority vote → no branching per chain
# ToT (b=5)      = tot_bfs(x, steps=3, beam=5)   → full tree search

Experiments: three tasks that challenge GPT-4

The authors designed three tasks specifically chosen to expose the limits of linear reasoning:

Game of 24 — Given 4 numbers, use arithmetic to make 24. Requires 3 intermediate equation steps. GPT-4 with CoT solves only 4%. ToT with BFS (beam=5) solves 74% — an 18× improvement. Even ToT with beam=1 (no branching, but with evaluation and backtracking) reaches 45%.

Creative Writing — Write a coherent 4-paragraph passage where each paragraph must end with a given random sentence. ToT uses a plan-then-write approach: generate 5 plans, vote for the best, generate 5 passages from that plan, vote again. Humans preferred ToT over CoT in 41 out of 100 comparisons (vs. 21 for CoT).

Mini Crosswords (5×5) — Fill a grid given 10 clues. ToT uses DFS with backtracking: propose words, check if remaining clues are still fillable, backtrack if stuck. ToT achieves 60% word-level accuracy vs. 16% for CoT.

Open in Lab

Success rates across methods and tasks. Hover for detailed numbers.

The demo wakes as you arrive…

Why CoT fails early: error analysis

The paper includes a revealing error analysis of the Game of 24. About 60% of CoT samples fail at the very first step — the first three words of the chain (like "4 + 9"). Once the model commits to a bad opening move, the rest of the chain is doomed because there is no backtracking.

ToT dramatically changes this picture. With beam width 5, even when some branches fail at step 1, the surviving branches continue to step 2 and beyond. Errors are caught early and pruned. This is exactly the benefit of deliberate search: mistakes are local, not fatal.

ToT as a generalization

One of the paper's elegant contributions is showing that existing prompting methods are special cases of ToT:

IO prompting is a degenerate tree with depth 0 — no intermediate thoughts at all. CoT prompting is a tree with depth n but breadth 1 — a single path, no branching. CoT-SC is k independent depth-n trees — branching only at the root, voting only at the leaves. ToT is the full framework: arbitrary depth, arbitrary breadth, evaluation at every intermediate node.

This spectrum also maps to the properties of the search: no exploration (IO), no evaluation (CoT), evaluation at the end only (CoT-SC), and full explore-evaluate loop (ToT). The paper's key argument is that problems requiring genuine search — where early decisions affect later options — need the full framework.

Open in Lab

See how IO, CoT, CoT-SC, and ToT form a spectrum from no exploration to full tree search.

The demo wakes as you arrive…

The legacy: from ToT to o1

2022
Chain-of-Thought (Wei et al.)
Showed that prompting LLMs to "think step by step" dramatically improves reasoning. Single linear chain, no branching.
2022
Self-Consistency (Wang et al.)
Sample multiple CoT chains and take a majority vote. Branches at the root only, no intermediate evaluation.
2023
Tree of Thoughts (Yao et al.)
Full tree search with generation, evaluation, and backtracking at every intermediate step. LM as its own heuristic. 4% → 74% on Game of 24.
2024
OpenAI o1
Scales "test-time compute" — the model thinks longer before answering, using internal chain-of-thought with search. A direct descendant of the ToT philosophy.

ToT's deepest contribution is conceptual, not algorithmic. It demonstrated that the classical AI insight — problem solving is search — applies directly to LLMs. The model doesn't need new weights; it needs a better procedure. This idea, that spending more compute at inference time (test-time compute) can substitute for training, became the central insight behind OpenAI o1 and the broader movement toward reasoning-time scaling.

The paper also showed that LLMs can serve double duty: as the generator of candidate solutions and as the evaluator that prunes bad ones. This generator-evaluator paradigm has become a design pattern across agentic AI, code generation, and scientific reasoning.

CitationYao, Yu, Zhao, Shafran, Griffiths, Cao, Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS, 2023.

Terms in this paper

Tree of Thoughtsشجرة الأفكار
Chain of Thoughtسلسلة التفكير
Self-Consistencyالاتّساق الذاتي
Beam Searchبحث الحزمة
System 1/System 2 Thinkingتفكير النظام الأول والنظام الثاني
Evaluation Functionدالّة التقييم
Branching Factorعامل التفرّع
Dynamic Programmingالبرمجة الديناميكية
Decision Treeشجرة القرار الإحصائية
Combinatorial Optimizationالأمثَلة التوافقية
Self-Reflectionالمراجعة الذاتية