Tree of Thoughts and LATS — branching reasoning with self-evaluation
Tree of Thoughts (BFS, beam, or DFS)
root
6-4=2, score 0.2
4+1=5, 0.1
6*4=24, 0.95
done: 24
self-eval at each node picks the frontier.
"sure / likely / impossible" classification,
1..10 numeric score, or majority vote.
Game of 24: CoT 4% -- ToT 74%
GPT-4 baseline vs ToT with beam-5, depth-3.
cost
100-1000x tokens of a single CoT trajectory.
reserve for tasks with weak single-shot success.
LATS = ToT + ReAct + Reflexion + MCTS
Select walk root-to-leaf via UCT
Q(s,a) + c * sqrt(ln N(s) / N(s,a))
Expand policy proposes K children
ReAct-style next-action candidates
Simulate rollout + value function
score with prompted value + env reward
Backpropagate update visits and Q
on failure: write reflection, reseed rollouts
when to pick LATS
coding (tests as value function)
math/olympiad with checkable targets
deep research with multiple query paths
not for short Q&A or chat
LATS HumanEval 92.7% pass@1 (GPT-4)
SOTA at paper time (ICML 2024)
evolutionary search (AlphaEvolve) is the 2025 extreme