TAI BUI
Back to curriculum
BuildPython

Tree of Thoughts and LATS: Deliberate Search

A single chain-of-thought trajectory has no room to backtrack. ToT (Yao et al., 2023) turns reasoning into a tree with self-evaluation on each node, and LATS (Zhou et al., 2024) folds ToT, ReAct, and Reflexion into Monte Carlo Tree Search. Game of 24 goes from 4% (CoT) to 74% (ToT), and LATS hits 92.7% pass@1 on HumanEval.

TIME: ~75 minutesPREREQUISITES: Phase 14 · 01 (Agent Loop), Phase 14 · 03 (Reflexion)

Learning Objectives

  • Frame reasoning as search: nodes are "thoughts," edges are "expansions," value is "how promising."
  • Implement a stdlib ToT-style BFS tree search with self-evaluation scoring.
  • Extend to a toy LATS MCTS loop with select / expand / simulate / backpropagate.
  • Decide when search is worth the token multiplier (Game of 24, code generation) and when a single trajectory is enough (simple Q&A).

The Problem

Chain-of-thought is a linear walk. If the first step is wrong, every step after it builds on a bad premise. Game of 24 (combine four numbers with + − × ÷ to make 24) shows the damage: GPT-4 with CoT scores 4%. It picks the wrong subexpression early and has no way back.

What the model needs is the ability to propose several candidates, score them, keep the promising ones, and back up when a branch dies. That is search. Tree of Thoughts and LATS are the two canonical ways to bolt it onto an LLM.

Warm-up0/3
1. You are solving a maze and hit a dead end. What lets you recover?Warm-up
2. You are choosing a move in a board game and can only afford to look a few moves ahead. Which approach is sensible?Warm-up
3. A coding agent can judge a generated function by asking the model whether it looks right, or by running a unit test suite. Which is the more trustworthy signal?Warm-up
Check: The Problem0/1
1. Why does chain-of-thought struggle on Game of 24?Explain

The Concept

Tree of Thoughts (Yao et al., NeurIPS 2023)

Tree of Thoughts (ToT) treats reasoning as search over a tree. Each node is a coherent intermediate step, a "thought," and each node expands into K child thoughts. The LLM scores every node with an evaluation prompt, and a search algorithm (BFS, DFS, or beam) decides which branches to keep exploring.

                     (root: "find 24 from 4 6 4 1")
                    /               |            \
           ("6 - 4 = 2")    ("4 + 1 = 5")    ("4 * 6 = 24")  <- Score: HIGH
              /   \              |                  |
          ...    ...          ...                finish

The self-evaluation step carries the whole method. The paper tests three variants: a sure / likely / impossible classification, a 1..10 numeric score, and a vote among candidates. All three beat CoT by a wide margin on Game of 24 (4% to 74% with GPT-4).

LATS (Zhou et al., ICML 2024)

LATS (Language Agent Tree Search) runs ToT, ReAct, and Reflexion together inside Monte Carlo Tree Search. One LLM plays three roles:

  • Policy: proposes candidate next actions, ReAct-style.
  • Value function: scores a partial trajectory, ToT-style.
  • Self-reflector: after a failure, writes a natural-language reflection (Reflexion-style) that reseeds later rollouts.

Environment feedback flows into the value function too, so the search rests on real tool results and not only the model's opinion of itself. At paper time LATS reached 92.7% pass@1 on HumanEval with GPT-4 (state of the art) and a 75.9 average on WebShop with GPT-3.5, approaching gradient-based fine-tuning.

MCTS, minimally

Each iteration runs four phases:

  1. Select: walk from the root to a leaf using UCT (upper confidence bound for trees).
  2. Expand: generate K children with the policy.
  3. Simulate: roll out from a child using the policy, then score the leaf with the value function or the environment reward.
  4. Backpropagate: push the result back up the path, updating visit counts and value estimates.

The UCT formula is Q(s, a) + c * sqrt(ln N(s) / N(s, a)). The first term rewards what has worked so far (exploitation), the second rewards what has been tried least (exploration). Tune c per task.

The cost reality

Search burns tokens. ToT on Game of 24 uses 100-1000x the tokens of CoT, and LATS lands in the same range. Reach for it when:

  • A single trajectory demonstrably fails (Game of 24, hard code problems).
  • Correctness matters more than wall-clock time.
  • You have a cheap, reliable value function, like unit tests for code or an explicit target for math.

If the task has one right answer and your evaluator is noisy, search often makes things worse. It finds a wrong answer that scores well.

2026 positioning

Most production agents don't run LATS. They run ReAct with tool-grounded verification (CRITIC, Lesson 05). Search survives in a few niches:

  • Coding agents that use tests as the value function (HumanEval-style).
  • Deep-research agents that explore several query paths.
  • Planning-heavy workflows inside LangGraph subgraphs.

AlphaEvolve (Lesson 11) is the 2025 extreme: evolutionary search over code with machine-checkable fitness, and frontier results to show for it (the first 4x4 matmul improvement in 56 years).

Check: The Concept0/29
1. What is Tree of Thoughts?Define
2. What is LATS?Define
3. What does UCT do in tree search?Define
4. In a language-agent search, what is the value function?Define
5. What is the policy in LATS?Define
6. What is a rollout in MCTS?Define
7. What does the backpropagate phase do in MCTS?Define
8. What four phases does each MCTS iteration run, in order?Define
9. Which three ways of scoring a node does the Tree of Thoughts paper test?Define
10. Roughly how many times the tokens of CoT should you budget for ToT on Game of 24?Define
11. When reasoning is framed as search, what does an edge in the tree represent?Explain
12. Which part of Tree of Thoughts carries the method and lifts it above chain-of-thought?Explain
13. Which of these is NOT a role the LLM plays in LATS?Explain
14. In UCT, what is the role of the exploration constant c?Explain
15. Why does LATS feed environment feedback into the value function instead of relying only on the model's own score?Explain
16. What would happen to selection if UCT lost its exploration term?Explain
17. What is the self-reflector's output used for in LATS?Explain
18. LATS reaches state-of-the-art HumanEval pass@1 with GPT-4. Which property of coding tasks makes search a good fit?Explain
19. LATS with GPT-3.5 averages 75.9 on WebShop, approaching gradient-based fine-tuning. What does that suggest?Explain
20. When is search actively harmful compared with a single trajectory?Explain
21. Where does search like LATS actually show up in 2026 production agents?Explain
22. Using the UCT formula, what is the score for Q=0.6, c=0.5, ln N(s)=4 and N(s,a)=1?Apply
23. In a toy LATS run, one early branch keeps being selected for nearly every iteration while its visit counts climb and siblings stay barely visited. Which setting is the likely culprit?Analyze
24. A team swaps a ReAct agent for tree search on a task with one correct answer. Their LLM scoring prompt is often wrong, and accuracy drops. What best explains it?Analyze
25. A ToT run costs about 300x the tokens of a CoT baseline on a task where CoT already answers correctly. Which earlier decision failed?Analyze
26. A code-search agent finds patches that pass the model's own self-review but fail the real unit tests. Which LATS ingredient was effectively missing?Analyze
27. You are building an agent that must fix failing tests in a repo. Correctness matters more than latency, and a test suite scores each candidate patch. Which design fits?Design
28. A support bot answers FAQ questions. Each has one right answer, there is no automatic check, and replies must be quick. What should you do?Design
29. A new task has no tests and no known target answer. A teammate proposes adding more branches to improve results. What should come first?Design

Build It

code/main.py implements three pieces:

  • A small ToT BFS on a stylized "pick arithmetic ops" task.
  • A toy LATS MCTS loop on the same task (Select / Expand / Simulate / Backpropagate) with UCT selection.
  • A value function that combines a symbolic score with a self-eval score.

Run it:

python3 code/main.py

The trace shows ToT expanding three candidates per node with BFS, then LATS converging on the best rollout through MCTS. Token counts print for both, so you can see the cost gap for yourself.

Check: Build It0/4
1. In main.py the root state is (6, 4, 4, 1). With the four operators and no division by zero, how many children does expand(root) return?Apply
2. In main.py, what does value() return for the finished state (30.0,) when TARGET is 24?Apply
3. In main.py, a parent has 10 visits. One child has 0 visits and another has Q=0.9 with 5 visits. Which does select() move to?Apply
4. backprop(path, 0.5) runs on a path whose root has visits=2 and value_sum=1.0. What are the root's visits and q afterward?Apply

Use It

LangGraph ships ToT-style exploration as subgraph patterns, and the LangChain team's LATS post (May 2024) is the reference tutorial. LlamaIndex has a TreeOfThoughts agent. In most 2026 production agents the pattern sits behind a gate like if task_complexity > threshold: use_search(). The evaluator-optimizer pattern in Lesson 05 is the neighboring idea.

Ship It

outputs/skill-search-policy.md picks between linear ReAct, ToT, LATS, and evolutionary search based on task shape, budget, and evaluator fidelity.

Author's Note

The most common mistake is reaching for search before checking the evaluator. A tree is only as good as the score on its nodes. If you can't write a value function you'd trust on its own (tests that pass, a target that matches), more branches just give a noisy scorer more chances to pick the wrong answer. Fix the evaluator first. A single ReAct run with a good verifier often beats the tree at a fraction of the cost.

Exercises

  1. Run the toy LATS with UCT c=0.1 vs c=2.0. What changes in the trace?
  2. Swap the value function for a noisier scorer (add random jitter). Does MCTS still find the best leaf? What is the minimum signal-to-noise it tolerates?
  3. Implement beam-search ToT (keep the top-k at each level) and compare it to BFS. Which is better on a tight token budget?
  4. Read LATS Section 5.1. Reproduce the HumanEval trajectory count: how many rollouts does it take to hit the reported pass@1?
  5. Read the LATS paper's discussion of "when LATS helps less." Write a one-paragraph decision rule mapping task shape to search strategy.

Key Terms

TermWhat people sayWhat it actually means
Tree of Thoughts"Branching CoT"Yao et al.: a tree of thought nodes, each scored by self-evaluation
LATS"MCTS for LLMs"Zhou et al.: ToT + ReAct + Reflexion under MCTS
UCT"Upper confidence bound"Selection formula balancing exploitation (Q) and exploration (ln N / n)
Value function"How good is this state"A prompted LLM score or environment reward that feeds backprop
Policy"Action proposer"ReAct-style generator that emits candidate next thoughts or actions
Rollout"Simulated trajectory"A walk from a node to a leaf using the policy, scored with the value function
Backpropagate"Update ancestors"Push the leaf's reward up the path, updating visit counts and Q
Search cost"Token explosion"100-1000x CoT on Game of 24; budget before you adopt

Further Reading

Code

Ships With