← Roadmap

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Yao, Yu, Zhao, Shafran, Griffiths, Cao, Narasimhan · 2023

① Intuition

Chain-of-Thought prompting asks a language model to reason step-by-step before answering. This works well for many tasks — but it commits the model to a single linear trajectory through the reasoning space. Once an early step goes wrong, the chain cannot recover: every subsequent step builds on that mistake, and by the end the model has wasted its entire token budget going in the wrong direction. For hard problems — the Game of 24, creative writing with structural constraints, or mini-crosswords — a wrong early branch dooms the entire attempt.

Tree of Thoughts (ToT) breaks this commitment. Instead of one chain, the model explicitly maintains a tree of partial reasoning states. At each step, a thought generator samples k candidate continuations (using the same LLM with an appropriate prompt). An evaluator — again the same LLM, but prompted differently — scores each candidate thought: “does this partial state look promising?” A search algorithm (BFS, DFS, or best-first) then decides which branches to expand next and which to prune. The result is deliberate, structured exploration of the reasoning space rather than a one-shot commit.

Before using the widget: in the tree below, A1 scores 0.7, A2 scores 0.4, A3 scores 0.1, and A1's child B1 scores 0.9. Which strategy reaches B1 (score 0.9) the fastest — BFS, DFS, or best-first? And why?

Interact with the widget: use the Strategy selector to switch between BFS, DFS, and best-first. Advance through steps with the slider and watch the order in which nodes are highlighted. Observe when the “Best seen so far” value reaches 0.9. Notice that best-first hits 0.9 after only 3 expansions, while BFS needs all of level-1 first.

root0.0A10.7A20.4A30.1B10.9B20.5B30.2B40.8B50.3B60.2

Best seen so far: 0.0

After playing with the widget: DFS expands A1 then B1 then B2 before visiting A2. If the tree were much deeper and A1's subtree had no good nodes past depth 2, what would happen to DFS's token budget?

Retrieval check

Why does Chain-of-Thought fail on the Game of 24 where Tree of Thoughts succeeds?
In Tree of Thoughts, the evaluator is implemented as a separate LLM with different weights from the thought generator. True or false?

Answer all 2 correctly to mark this stage mastered.

② Math

At a node v with partial solution s, the thought generator samples k candidate children:

{c1,…,ck}∼pθthought(⋅∣s)\{c_1, \ldots, c_k\} \sim p_{\theta}^{\text{thought}}(\cdot \mid s)

Each child is scored by the evaluator:

V(ci)=pθvalue(⋅∣s, ci)V(c_i) = p_{\theta}^{\text{value}}(\cdot \mid s,\, c_i)

The frontier F is a priority queue of unexpanded nodes. At each iteration, the search selects the top-T nodes by score (beam search) or the single top node (best-first) and expands them. Define the beam at depth d as:

Bd=top⁡T ⁣{ V(v):v∈F,  depth(v)=d }B_d = \operatorname{top}_T\!\bigl\{\, V(v) : v \in F,\; \text{depth}(v) = d \,\bigr\}

Expanding B_d generates k \cdot T new candidates at depth d+1, each immediately scored, before the beam advances to depth d+1. DFS instead replaces best-first with a LIFO stack, ignoring V except for pruning hopeless branches.

Why does ToT use the LLM itself as the evaluator rather than a hand-written heuristic?
Show next line
V(ci)=pθvalue(⋅∣s, ci)  ⇒  one prompt, any taskV(c_i) = p_{\theta}^{\text{value}}(\cdot \mid s,\, c_i) \;\Rightarrow\; \text{one prompt, any task}
Why does BFS often outperform DFS in the ToT experiments on Game of 24?
Show next line
Bd=top⁡T{V(v)}⇒T live branches vs DFS’s 1B_d = \operatorname{top}_T\{V(v)\} \Rightarrow T\text{ live branches vs DFS's 1}

Retrieval check

In the ToT formulation, what is the role of p_theta^value compared to p_theta^thought?
The Game of 24 requires combining 4 numbers with +, -, *, / to reach 24. How does ToT's structure map onto this problem?

Answer all 2 correctly to mark this stage mastered.

③ Pseudo code

Arrange the five steps of the best-first ToT search loop in the correct order:

  1. Initialize frontier F = [(0.0, root_state)]; set budget = max_expansions
  2. Generate k candidate thoughts: children = thought_generator(state, k)
  3. Pop the highest-scored node (score, state) from F
  4. Score each child: scored = [(value(state, c), c) for c in children]
  5. Push scored children into F; decrement budget; repeat until goal found or budget exhausted

Fill in the blank — the line that extracts the top node from the frontier:

def best_first_step(frontier):
    frontier_sorted = sorted(frontier, key=V, reverse=True)
    best = _______
    remaining = frontier_sorted[1:]
    return best, remaining

Retrieval check

In the ToT pseudo code, why is the evaluator called on each child immediately after generation rather than lazily when the child is popped from the frontier?

Answer all 1 correctly to mark this stage mastered.

④ Code (Python)

Implement best-first node selection in Python. Given a frontier as a list of (score, node_id) tuples, return (popped_node_id, remaining_frontier) where popped_node_id is the id of the highest-scored node and remaining_frontier is the list without that node.

Retrieval check

The best_first_pop function uses sorted() and returns sorted_f[1:] as the remaining frontier. What is the time complexity of this operation relative to frontier size n?

Answer all 1 correctly to mark this stage mastered.

⑤ Original paper

Your browser can't embed PDFs. Download Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al. 2023).

Open in new tab · Download

Suggested reading order: §1 (Introduction — motivation from CoT’s single-trajectory limitation) → §2 (Tree of Thoughts framework — thought generator, evaluator, and search algorithms) → §3 (Experiments — Game of 24, creative writing, mini-crosswords benchmarks).