Chain-of-thought generates a single linear path from question to answer. This works for problems with straightforward solutions, but many problems require exploration: trying different approaches, evaluating partial solutions, and backtracking when a path leads nowhere. Consider the “Game of 24”: given four numbers, use arithmetic operations to make 24. For example, with {4, 5, 6, 10}: one approach might try 4 × 6 = 24, but then you have unused numbers. Another might try 10 - 4 = 6, then 6 × 5 = 30, which doesn’t work. You need to explore multiple paths. Standard CoT commits to one path and can’t backtrack. Tree-of-Thought (Yao et al., NeurIPS 2023) solves this by treating reasoning as a search problem: generate multiple candidate “thoughts” at each step, evaluate them, and use search algorithms (BFS, DFS) to find the best path.

Tree-of-Thought has four key components: 1. Thought decomposition — define what constitutes a “thought” (a coherent unit of reasoning). For Game of 24, a thought is one arithmetic operation. For creative writing, it might be a paragraph plan. The granularity matters: too fine-grained creates too many branches; too coarse misses opportunities for correction. 2. Thought generation — at each node, generate k candidate next thoughts. Use the LLM to propose multiple continuations (e.g., k = 5 candidates). 3. State evaluation — use the LLM to evaluate each candidate thought: “Is this partial solution promising? Rate it as sure/maybe/impossible.” This is the heuristic that guides the search. 4. Search algorithm — use BFS or DFS to traverse the tree, guided by the evaluations. BFS explores breadth-first (all options at each level); DFS goes deep first and backtracks.

Breadth-First Search (BFS) explores all candidate thoughts at each level before going deeper. At each step, keep the top-b most promising thoughts (beam search). Best for problems where you need to compare multiple approaches at each stage. Used by Yao et al. for Game of 24 (b = 5). Depth-First Search (DFS) explores one path deeply before backtracking. Goes as far as possible along one branch, then backtracks when it hits a dead end or an “impossible” evaluation. Best for problems with deep solution paths where early pruning is effective. Used by Yao et al. for Creative Writing. When to use which: BFS when the solution space is wide but shallow (many options at each step, few steps). DFS when the solution space is narrow but deep (few options, many steps). In practice, BFS with beam search (keep top-b at each level) is the most common approach.

Monte Carlo Tree Search is the algorithm that powered AlphaGo’s victory over Lee Sedol in 2016. It combines tree search with random sampling (rollouts) to efficiently explore large search spaces. Applied to LLM reasoning, MCTS works in four phases: Selection — traverse the tree from root to a leaf node, using UCB1 (Upper Confidence Bound) to balance exploration vs exploitation. Expansion — at the leaf, use the LLM to generate candidate next thoughts. Simulation (rollout) — from each candidate, use the LLM to quickly complete the reasoning to a final answer (possibly with greedy decoding). Backpropagation — update the value estimates of all nodes along the path based on whether the rollout reached a correct answer. MCTS is more compute-intensive than BFS/DFS but handles larger search spaces better. It’s particularly effective when combined with a learned value function (like in AlphaGo).

The Game of 24 is a mathematical puzzle: given four numbers, use +, −, ×, ÷ to make exactly 24. Example: {1, 2, 3, 4} → 1 × 2 × 3 × 4 = 24. This is a perfect test case for ToT because: (1) it requires search — there are many possible operation sequences, (2) it has verifiable answers — you can check if the result equals 24, (3) it requires backtracking — most paths don’t lead to 24. Yao et al. used BFS with b = 5 (keep top 5 candidates at each level). Each “thought” is one arithmetic operation that combines two numbers. The LLM evaluates each partial state as “sure” (definitely solvable), “maybe” (possibly solvable), or “impossible” (can’t reach 24). Results: GPT-4 with standard prompting solved 7.3%, CoT solved 4.0%, CoT + self-consistency (100 samples) solved 9.0%, and ToT solved 74%.

Trees are just the beginning. Researchers have explored richer reasoning structures: Graph-of-Thought (Besta et al., 2023) — allows thoughts to merge and form cycles, not just branch. Two reasoning paths can converge when they reach the same intermediate conclusion. This models how humans reason: we combine insights from different angles. Algorithm-of-Thought (Sel et al., 2023) — teaches LLMs to mimic algorithmic search patterns (like DFS) within a single prompt, without actually running multiple LLM calls. Everything-of-Thought (Ding et al., 2023) — combines MCTS with an external “thought library” of reusable reasoning patterns. Buffer-of-Thought (Yang et al., 2024) — maintains a library of high-level “thought templates” that can be retrieved and adapted for new problems. The trend: increasingly sophisticated reasoning structures that combine LLM generation with classical AI search.

Tree search dramatically improves reasoning but at significant computational cost: LLM calls multiply — ToT with BFS (b = 5, depth = 3) requires generating and evaluating 5 × 3 = 15 thoughts, plus 15 evaluation calls = ~30 LLM calls per problem. Compare to 1 call for standard prompting. Token generation — each thought generation and evaluation produces tokens. Total token count can be 50–100x standard prompting. Latency — sequential search (DFS) adds latency proportional to search depth. BFS can parallelize within a level but still requires multiple rounds. Diminishing returns — increasing beam width or search depth has diminishing returns. Going from b = 5 to b = 10 rarely doubles accuracy. Practical guidance: use search only when the problem genuinely requires exploration. For most reasoning tasks, CoT + self-consistency is sufficient. Reserve ToT/MCTS for search-heavy problems (puzzles, planning, code generation).

ToT demonstrated that search dramatically improves LLM reasoning. But running search externally (orchestrating multiple LLM calls) is expensive and complex. The natural next step: train the search into the model itself. This is exactly what OpenAI did with o1: External search (ToT) — an external program orchestrates multiple LLM calls, manages the tree, and runs the search algorithm. The LLM is a component. Learned search (o1/o3) — the model is trained via reinforcement learning to perform search-like reasoning internally. It generates “thinking tokens” that explore different approaches, evaluate them, and backtrack — all within a single generation. The model has internalized the search process. This is the key insight of Chapter 4 (Test-Time Compute Scaling): you can train a model to do what ToT does externally, but more efficiently and with learned heuristics rather than hand-designed search algorithms.