Tree of Thoughts
Tree of Thoughts explores multiple reasoning branches with search and self-evaluation, solving problems where single-pass chain-of-thought fails.
Primary source: Tree of Thoughts: Deliberate Problem Solving with Large Language Models (arXiv:2305.10601)
Chain-of-thought reasons in a straight line: one path, no backtracking. When an early step goes wrong, the whole answer fails. The 2023 Tree of Thoughts paper treats reasoning as search instead — generate multiple candidate thoughts per step, evaluate them, expand the promising ones, abandon the dead ends. Deliberate problem solving, the way a person works through a hard puzzle.
The framework
ToT generalizes CoT into four components. Thought decomposition breaks the problem into steps sized so the model can judge progress ("one equation" for arithmetic, "one paragraph" for writing). Thought generation proposes several candidates per step, either independently or sequentially. State evaluation scores candidates — by direct value prompts ("sure/likely/impossible") or by voting across samples. Search ties it together with BFS (keep the best b states per level) or DFS (pursue, backtrack past a value threshold).
Nothing is trained. The same frozen model plays generator, evaluator, and searcher through different prompts.
What the results showed
On Game of 24 (combine four numbers to make 24), CoT with GPT-4 solved 4%; ToT with BFS solved 74%. On creative writing and mini-crosswords, ToT beat CoT by 20–40 points. The gains come from exactly where you would expect: tasks needing trial, error, and lookahead, where a single greedy path rarely survives.
The price is compute: ToT makes tens to hundreds of model calls per problem versus one for CoT. It is a test-time scaling method — spend inference, buy accuracy.
BFS versus DFS in practice
The paper runs both. BFS with beam width 5 dominates Game of 24: evaluate all first-step candidates, keep the best 5, expand. DFS with backtracking wins on creative writing, where depth matters more than breadth — pursue one story direction, and only backtrack past a value threshold when the evaluator flags it dead. The choice mirrors classical search exactly, which is the point: ToT ports seventy years of search algorithms onto language-model thoughts.
Evaluation strategy matters as much as search. The paper compares value prompting ("evaluate as sure/likely/impossible") against voting (sample several judgments, take the majority). Voting costs more calls but is far more reliable on hard steps — evaluator noise is the main reason good branches get pruned, and majority vote is the cheapest fix.
The cost question, honestly
ToT on Game of 24 used roughly 100 GPT-4 calls per problem versus 1 for CoT — a 100x inference multiplier for a 70-point accuracy gain. Whether that trades well depends entirely on the stakes: for puzzle benchmarks it is absurd overkill per problem, but it established that test-time compute converts to accuracy on a predictable curve. That curve — not any single result — is what labs now optimize, with learned verifiers and distilled reasoners pushing the same frontier far more cheaply.
Legacy
ToT kicked off the test-time-compute movement: self-consistency, verification, Monte Carlo tree search over thoughts (RAP, AlphaMath), and eventually OpenAI's o1-style reasoning models, which internalize the search the paper did explicitly. The "generate, evaluate, search" pattern now sits inside frontier training pipelines, not just prompts.
From prompted search to learned reasoning
The intermediate steps are worth naming. Math-Shepherd (2023) trained process reward models that score each reasoning step, replacing ToT's prompted evaluator with a learned verifier — same search, better judgment. RAP and rStar ran full MCTS over the thought space with learned value estimates. Then o1 showed the endgame: bake the search into training with RL, and the model learns when to branch, backtrack, and verify internally, emitting only the distilled chain.
Each step moved compute from inference prompts into weights and verifiers, but ToT's decomposition — generate candidates, evaluate states, search deliberately — survived every migration. It is the conceptual API for machine reasoning under a compute budget. For practitioners, the takeaway is procedural: build the evaluator before the search, since a good judge with plain BFS beats a sophisticated searcher with a noisy one.
Bottom line
Tree of Thoughts replaced single-pass reasoning with deliberate search over thought candidates, turning 4% into 74% on planning-heavy puzzles. It proved inference-time compute is a lever as real as parameters — and launched the reasoning-model era.
Sources
- Yao et al., Tree of Thoughts: Deliberate Problem Solving with Large Language Models, 2023. arXiv:2305.10601
- Wei et al., Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, 2022. arXiv:2201.11903
Want the next review in your inbox? The briefing collects them — at most one email a week. Read signup data and removal options.
Cite this report
@misc{knowyourml-tree-of-thoughts-deliberate-problem-solving
title = {Tree of Thoughts},
author = {{Know Your ML}},
year = {2023},
howpublished = {\url{https://knowyourml.yunusemrevurgun.com/report.php?slug=tree-of-thoughts-deliberate-problem-solving}},
note = {AI-generated review of arXiv:2305.10601. Primary sources are listed on the page.}
}
Machine Learning Decision Toolkit
Turn this review into a decision: the Machine Learning Decision Toolkit packages the evaluation scorecards, workload templates and deployment checks behind model, provider and architecture choices.
References
- Tree of Thoughts: Deliberate Problem Solving with Large Language Models (arXiv:2305.10601) — https://arxiv.org/abs/2305.10601
- Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (arXiv:2201.11903) — https://arxiv.org/abs/2201.11903
Frequently asked questions
How does it differ from chain-of-thought?
Chain-of-thought generates one reasoning path left to right. Tree of Thoughts generates several candidate thoughts per step, scores them with the model itself, and searches (BFS/DFS) the most promising branches — with backtracking.
Is the extra search cost worth it?
Yes on tasks needing planning and lookahead: Game of 24 jumped from 4% (CoT) to 74%. The cost is many more model calls, so it suits hard problems where accuracy beats latency.
Part of
Beyond the paper
How to Remain Valuable When Intelligence Becomes Cheap
This report covered one more way the machine gets smarter. The companion eBook asks the question on the other side: which human advantages stay scarce — and valuable — when intelligence itself is cheap?