① 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?
Best-first reaches B1 earliest because it always expands the highest-scoring unexpanded node. After expanding root it sees A1 (0.7), A2 (0.4), A3 (0.1) — it picks A1 and immediately discovers B1 (0.9). BFS would expand all of level-1 before touching level-2. DFS would go deep on A1’s subtree, which happens to work here, but would keep diving into low-scoring branches when A1 looks good early and would not prioritize by score. Best-first is score-guided and finds the best node with the fewest wasted expansions.
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.
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?
DFS would sink its entire budget into A1’s subtree, recursively exploring all its descendants before discovering that A2 contains B4 (score 0.8). This is DFS’s main weakness for ToT: without a score-based cutoff, it can waste O(branch^depth) evaluations on a single bad branch. Best-first avoids this by globally re-ranking across all open branches after each expansion, so a mediocre branch gets deprioritized as soon as a better sibling appears. This is why the paper reports best-first and BFS outperforming DFS on the Game of 24 benchmark.
Retrieval check
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:
Each child is scored by the evaluator:
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:
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.
Show next line
Show next line
Retrieval check
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:
- Initialize frontier F = [(0.0, root_state)]; set budget = max_expansions
- Generate k candidate thoughts: children = thought_generator(state, k)
- Pop the highest-scored node (score, state) from F
- Score each child: scored = [(value(state, c), c) for c in children]
- 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, remainingRetrieval check
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
Answer all 1 correctly to mark this stage mastered.
⑤ Original paper
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).