AI-generated review 5 min read Intermediate 777 words

Tree of Thoughts

Tree of Thoughts explores multiple reasoning branches with search and self-evaluation, solving problems where single-pass chain-of-thought fails.

tree-of-thoughts reasoning search planning prompting
Applications & prompting · 2023

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.

Reasoning as search Q t1 t2 ✕ t3 ✓ … … generate → evaluate → expand winners, prune losers
Each step branches into candidates; the model scores them and searches only the best.

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 — decision matrix, scorecards and trade-off analysis
Toolkit 7 decision tools Model-agnostic

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.

$24 View on Gumroad

References

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.

How to Remain Valuable When Intelligence Becomes Cheap — book cover
eBook 224 pages

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?

Read the eBook