Tree of Thoughts: what the paper actually says about LLM search

Reading Yao et al. (Princeton/Google DeepMind, NeurIPS 2023) while debugging why our agent kept solving the easy version of every hard problem.

We had an agent that did competitive analysis: given a company, reason through its market position, identify key risks, structure a strategic summary. The chain-of-thought prompt worked well on moderate inputs. On genuinely ambiguous cases — where the first framing you pick determines everything downstream — it systematically went wrong in one specific way: it committed to an initial interpretation early, then rationalized from there. The reasoning was internally consistent. It was just consistently built on the wrong premise.

You could see it in the traces. The model would write "The primary risk here is X," and every subsequent sentence would be about X. If the right answer required reconsidering whether X was actually the primary risk — stepping back, trying a different angle — the linear chain had no mechanism for that. You've generated "The primary risk here is X." There's no going back.

Tree of Thoughts — "Tree of Thoughts: Deliberate Problem Solving with Large Language Models", Yao, Yu, Zhao, Shafran, Griffiths, Cao, and Narasimhan from Princeton and Google DeepMind, NeurIPS 2023 — is the paper that names and formalizes this problem. The architecture it proposes isn't new in computer science terms. It's basically best-first search applied to LLM generation. The contribution is showing clearly when this matters, why standard generation fails, and exactly what breaks when you try to implement it.

The problem the paper is actually solving

Standard generation — including chain-of-thought — is left-to-right token sampling. You pick a starting token, then the most likely (or sampled) next token given the prefix, and so on. This works well for problems where:

Each step has a roughly independent probability of being correct
Early choices don't lock you into a subspace of solutions
The correct path is locally distinguishable from incorrect paths at each step

Many reasoning problems are not like this. The Game of 24 — use the numbers 4, 9, 10, 13 and the operations +, -, ×, ÷ to reach 24 — requires committing to an operation sequence where early choices determine whether a solution even exists. If you pick the wrong first operation, no amount of good subsequent reasoning recovers you. A linear chain will confidently follow the wrong branch to a confident wrong answer.

The paper frames this in terms of what a reasoning process needs to support:

Exploration: considering multiple different approaches before committing
Lookahead: evaluating whether a partial solution can lead to a valid full solution
Backtracking: returning to an earlier decision point when a path fails

Chain-of-thought has none of these. It generates a single path. The question the paper answers is: what does a generation framework look like that has all three?

The four components of ToT

Tree of Thoughts proposes decomposing the problem into four pieces:

1. Thought decomposition. You define what a "thought" is — a coherent unit of intermediate reasoning. The granularity is problem-specific. For Game of 24, one thought is one arithmetic step: "13 - 9 = 4, leaving 4, 4, 10." For multi-paragraph creative writing, one thought is one paragraph. Too coarse and you have few branches with high commitment per step. Too fine and the tree explodes in width with most branches being noise.

2. Thought generation. Given a state (the problem + all thoughts generated so far), generate candidate next thoughts. Two strategies: sample multiple thoughts from the model in parallel (cheap, random), or ask the model to propose a list of distinct candidates in a single call (more expensive, more structured). The paper uses the propose strategy for Game of 24 and sampling for writing tasks.

3. State evaluation. This is the component that makes ToT work and also the one that most implementations get wrong. You need a way to judge which partial solutions are promising. The paper uses the LM itself as an evaluator: either as a value function (ask the model "Is this partial solution promising? Confident/Likely/Impossible") or as a voting mechanism (generate multiple completions, see which are more frequent). The quality of your evaluator determines the quality of your search — more on this in the failure modes section.

4. Search algorithm. BFS or DFS. BFS maintains a frontier of the k most promising states at each depth level. DFS goes deep, backtracks when stuck. The choice depends on the problem: BFS is better when you can evaluate states at fixed depth (Game of 24: each depth level has the same structure), DFS is better when the tree is deep and you expect most paths to fail early.

What the benchmarks actually show

The paper tests three tasks.

Game of 24. This is the clearest demonstration. The task has a correct/incorrect answer and a well-defined depth structure (4 numbers → 3 steps → result). Standard IO prompting achieves 7.3% success with GPT-4. Chain-of-thought achieves 4% — actually worse, because CoT confidently pursues wrong branches. ToT with BFS achieves 74%. This is not a marginal improvement; it's a different capability class. The tasks where CoT fails aren't hard in the sense of requiring more knowledge. They're hard in the sense of requiring search.

Creative writing. Write a coherent passage satisfying four constraints (e.g., must contain "a frog," "a scientist," a sentence ending with "w," a sentence shorter than 5 words). Human raters prefer ToT outputs over CoT in 41% of cases vs. 20% favoring CoT. Less dramatic, because writing doesn't have the same "commit to wrong branch → unsalvageable" structure.

Mini crosswords. 5×5 crossword with 10 clues. CoT solves 0 of 20 puzzles. ToT with DFS solves 20%. The task requires cross-constraint propagation — filling one word constrains letters available for crossing words — which is exactly the structure ToT is designed for.

The pattern is consistent: problems requiring constraint satisfaction, backtracking, or explicit exploration of a discrete solution space show the largest gains. Problems with primarily sequential reasoning (factual chains, arithmetic) show smaller or no gains.

Production tradeoffs no one mentions in the benchmark post

The cost multiplier is real and gets worse with depth. Game of 24 benchmarks require roughly 10–15 LM calls per puzzle for ToT. The paper uses GPT-4, so that's $0.15–0.50 per puzzle instead of $0.01–0.02 for a single chain. At any non-trivial volume, ToT is 10–50× more expensive than CoT. For tasks where you run thousands of queries per day, this price change changes the business case for the feature.

The cost scales with branching factor × depth, and both are problem-specific. There's no general rule. Before deploying ToT, benchmark the call count distribution — it's often fat-tailed, with some inputs triggering far more exploration than average.

Latency is harder than throughput. You can parallelize thought generation — request all k candidate next thoughts simultaneously. But the search algorithm itself is sequential: evaluate the current frontier, generate next thoughts from the promising states, evaluate again. BFS depth-d requires d sequential evaluation steps even with perfect parallelism. For interactive applications, this makes ToT unsuitable unless you can background the search and stream intermediate results.

The evaluator quality determines everything. The paper uses the same GPT-4 model as both generator and evaluator. In practice this creates a systematic bias: the model rates its own generations as more promising. States that "sound good" to the model will score high even if they're logically flawed. For Game of 24, the paper cross-checks against deterministic arithmetic, so the evaluator has ground truth to anchor against. For open-ended tasks, you have no such check.

I've seen this manifest as: ToT confidently navigates to a local optimum that the model prefers on stylistic grounds, ignoring states that are harder to articulate but more logically sound. The search algorithm is working correctly; the evaluator is miscalibrated.

Thought granularity requires domain expertise. The paper defines thoughts for each task by hand. In practice, you're writing a thought decomposition that fits your specific problem. Too coarse and ToT degenerates to sampling a few full chains and picking the best one — which you could do with CoT + majority voting at lower cost. Too fine and the branching factor explodes. Getting the granularity right requires understanding the failure modes of your specific task well enough to know where backtracking actually helps.

Failure modes in practice

Evaluator-generator coupling. When the same model generates states and evaluates them, the evaluation correlates with superficial features the model learned to associate with quality during training — fluency, confident tone, structural completeness. None of these reliably predict whether the partial solution is actually on the right track. For math problems this doesn't matter because you can verify correctness deterministically. For reasoning tasks without ground truth, you're doing hill-climbing on the model's internal notion of "sounds right."

The practical fix is to use a different, ideally cheaper model for evaluation (or a deterministic checker if the problem admits one). Using GPT-4 to generate and GPT-3.5 to evaluate is worse for reasoning quality but breaks the correlation. For some tasks, this is the right tradeoff.

Budget overruns on adversarial inputs. If your problem space includes inputs that are intrinsically hard to search — many plausible early branches that all eventually fail — ToT can exhaust its call budget without producing a useful answer. Standard generation gives you something in bounded time. ToT can give you nothing after 50 calls. You need explicit fallbacks: a maximum call count after which you return the best partial result from the current frontier.

The "almost backtracking" problem. Teams often implement a shallow version of ToT: generate k thoughts, evaluate them, pick the best, continue linearly from there. This is best-of-k sampling with one branching point, not tree search. It catches some failures (first thought is clearly wrong) but not the cases that require backtracking to a decision point three steps back. True backtracking requires maintaining and revisiting the full search history, which most agent frameworks don't support without explicit implementation.

Prompt length explosion. Each step in a ToT trace includes the full history of decisions. By depth 4–5, your prompt includes the problem statement, all thoughts along the current path, and the evaluation context. For long-horizon tasks this pushes you into long-context territory where model quality degrades and cost scales with context length × number of parallel evaluations.

When not to use Tree of Thoughts

When your problem doesn't require backtracking. Translation, summarization, retrieval, classification — tasks where the first plausible answer is generally the right one. Adding tree search to these adds cost and latency for no benefit. Chain-of-thought or direct prompting is sufficient.

When you don't have a reliable state evaluator. If you can't tell whether a partial solution is promising, your search is random walk with extra steps. The value of tree search comes entirely from the evaluator's ability to prune bad branches early. Without that, you're paying 10–50× more for performance that's approximately equal to sampling multiple chains and taking a majority vote.

When latency is a hard constraint. Interactive applications, streaming responses, anything with a p99 latency SLA. ToT's sequential search structure means you can't parallelize your way out of the latency problem entirely. Background jobs, batch processing, or anything async can absorb the cost. Synchronous user-facing calls generally can't.

When the problem space isn't discrete. ToT is a search algorithm. Search algorithms work on discrete state spaces where you can enumerate candidates. Open-ended creative generation doesn't have natural branch points. You can impose them artificially (generate three opening paragraphs, pick one, continue), but the fit is loose and the gains are smaller. The clearest wins in the paper are on problems with well-defined state transitions: arithmetic steps, constraint satisfaction, word fills.

When your team can't maintain it. ToT implementations are significantly more complex than CoT — multiple prompt templates, an evaluation loop, a search queue, fallback handling, cost instrumentation. That's meaningful operational overhead. For most production applications, CoT with majority voting (self-consistency) is a better starting point: cheaper, simpler, and recovers most of the benefit for tasks where the problem is "first sample is sometimes wrong" rather than "fundamentally need backtracking."

What the paper actually gives you

The core contribution of Tree of Thoughts isn't the specific algorithm — BFS and DFS over LM-generated states is not novel. It's the clear articulation of when LLMs fail because of the structure of their generation, not because of lack of knowledge or capability.

The failure mode is specific: problems requiring backtracking over a discrete decision space will systematically fail with left-to-right generation, regardless of chain-of-thought or model scale. GPT-4 with CoT achieves 4% on Game of 24. GPT-4 with ToT achieves 74%. This gap doesn't close with more parameters or better instruction tuning. It closes with a different generation architecture.

The practical signal for engineers: if you have a task that requires exploring multiple framings before committing, or where early decisions determine whether the rest of the solution is viable, ToT (or any search-based approach) is the right tool and CoT is not. The benchmark suite in the paper is a reasonable heuristic for the right problem class.

For the competitive analysis agent that triggered this post — the one that kept picking the wrong primary risk and rationalizing from there — the fix was a lightweight version of ToT: generate three competing framings for the initial risk assessment, evaluate each against explicit criteria, select the most defensible before continuing. Not full tree search, but one branching point with evaluation. The traces improved substantially. The implementation was 40 lines of Python. The cost increase was 3× on the evaluation step, which ran once per query. That's the right scope for most production applications of this paper's ideas: borrow the evaluation mechanism without implementing the full search.

Tree of Thoughts: Deliberate Problem Solving with Large Language Models — Yao, Yu, Zhao, Shafran, Griffiths, Cao, Narasimhan. NeurIPS 2023.