Token Explosion, Latency, and the Hard Limits of Explicit Tree of Thoughts

The benchmark numbers are genuinely impressive. On the Game of 24 — a combinatorial puzzle requiring four numbers and basic arithmetic to reach exactly 24 — a standard chain-of-thought prompt succeeds roughly 4% of the time. Tree of Thoughts brings that to 74% (Yao et al. 2023). That is not a marginal improvement. It looks like a category shift.

The uncomfortable follow-up question: what does it cost to generate that improvement, and does the improvement survive when you give chain-of-thought an equivalent token budget?

The Branching Tax: What Tree of Thoughts Actually Spends

The fundamental architecture of Prompt Chaining is linear — one generation feeds the next. Tree of Thoughts replaces that linearity with a width-first search across multiple candidate thoughts at each step, evaluating which branches are worth pursuing before committing further. It is a reasonable idea with a predictable consequence: you are paying for every branch, including the ones you discard.

The original paper reports token consumption ranging from 5× to 100× more generated tokens than a single chain-of-thought call, depending on tree depth and branching factor (Yao et al. 2023). A practical depth-3 configuration with branching factor 4 — the kind you might actually run — lands somewhere in the 12–30× range against a standard CoT call, per secondary analysis (futureagi.com). Neither end of that range is cheap.

What are the technical limitations of Tree of Thoughts prompting?

The cost structure has three distinct components, and conflating them is the most common mistake when evaluating whether ToT is worth using.

Generation cost scales with breadth × depth. At each node in the search tree, you generate $b$ candidate thoughts. At depth $d$, you have explored up to $b^d$ paths before selecting the best one. A modest depth-3 tree with branching factor 4 requires up to 64 generation calls for the path nodes alone, before counting evaluation calls. This is not a linear function of task difficulty — it is exponential in the tree structure you specify.

Evaluation cost is often overlooked in rough estimates. Tree of Thoughts requires a scoring mechanism to determine which branches are worth expanding. In the original implementation, this is another LLM call: the model evaluates each candidate thought (“sure / maybe / impossible”) before the search continues. For every generation call, you likely pay one or more evaluation calls. The token budget doubles, at minimum.

Orchestration complexity is not a token cost but a latency cost. The search cannot be fully parallelized — evaluation at depth $d$ depends on generations at depth $d-1$. The critical path through the tree determines minimum wall-clock time; wider branching buys accuracy at the price of sequential dependency chains. On tasks with hard time constraints, this matters more than total token count.

The original paper gives concrete dollar figures from 2023 GPT-4 pricing: for the Game of 24, chain-of-thought best-of-100 runs $0.47 per case, while Tree of Thoughts at branching factor 5 runs $0.74. That 1.6× ratio understates the cost for creative tasks — Tree of Thoughts on the creative writing benchmark cost approximately 5× a standard CoT call (Yao et al. 2023). Current GPT-4 pricing differs from 2023 figures, so treat these as proportional comparisons rather than current rates.

Why is Tree of Thoughts too expensive for most production applications?

The cost question cannot be answered in isolation — it depends on whether the performance gap over cheaper methods is real or a function of unequal token budgets.

Chain-of-thought with Self Consistency is the key comparison. Self-consistency samples $k$ independent chain-of-thought completions from the same prompt and returns the majority answer. It is a flat, parallelizable approach with no sequential evaluation dependencies. It is also surprisingly competitive. On the Game of 24, CoT with self-consistency at $k=100$ samples achieves 9% success — still far below ToT’s 74%, but the comparison is not budget-matched: $k=100$ CoT runs is also a substantial token spend.

The harder comparison comes from Stechly et al. (2024), who examined reasoning strategies under equal token budgets across five datasets. Their finding: chain-of-thought with self-consistency frequently outperforms Tree of Thoughts when compute is equalized. The intuition is that ToT’s tree structure forces sequential evaluation that wastes budget on branching overhead; flat self-consistency can spend the same budget on more diverse candidate answers without the coordination cost.

There is also a model dependency that the original paper does not surface, because it only benchmarks GPT-4. On weaker models, Self Consistency outperforms Tree of Thoughts — the evaluation step that makes ToT work requires the model to reliably distinguish good candidate thoughts from bad ones. GPT-3.5 lacks that discrimination reliability; the tree search degrades into noise-amplification rather than signal extraction. The mixed-model experiment in the original paper is instructive: using GPT-4 for generation but GPT-3.5 for evaluation drops Game of 24 performance from 74% to 64% (Yao et al. 2023). The bottleneck is generation quality, but the evaluation step still matters — and cheaper models reliably underperform.

The Benchmark Deserves Its Asterisks

Game of 24 is a carefully selected test case. It is combinatorially tractable, has a verifiable ground truth, and — crucially — is the kind of task where human-readable intermediate steps genuinely constrain the search. The task design is almost optimal for Tree of Thoughts: discrete states, clear evaluation criteria, bounded search space.

Does Tree of Thoughts consistently outperform chain-of-thought on reasoning benchmarks?

The honest answer: on the tasks the original paper tests, yes, often by a large margin. On arbitrary reasoning tasks at equal token budget, the evidence is considerably thinner.

The crossword experiment tells a more nuanced story. Mini crossword letter accuracy improves from 38.7% (IO) to 78% (ToT); word accuracy improves from 14% to 60%; game completion goes from 0% to 20% (Yao et al. 2023). These are real improvements. But 20% game completion is not a production-ready result — it means 80% of crosswords still fail. The improvement is relative, not absolute.

Creative writing shows a different pattern. GPT-4 coherency scores improve from 6.19 (IO) to 7.56 (ToT), and human raters preferred ToT output in 41 of 100 head-to-head comparisons versus 21 for CoT (Yao et al. 2023). That is a meaningful signal. It is also a domain where Backtracking adds genuine value — narrative coherence is path-dependent in a way that arithmetic puzzles are not.

The benchmark limitation that rarely appears in ToT discussions: these tasks were selected because they exhibit the kind of search structure ToT exploits. Tasks where the search tree is shallow, or where the evaluation criterion is noisy, show less consistent improvement. Stechly et al. (2024) examined five datasets with equalized compute and found frequent cases where self-consistency matched or exceeded ToT. The original paper does not include those cases — not through dishonesty, but because the paper’s goal was to demonstrate the approach on suitable tasks, not to map its failure conditions.

There is also the question of what “frontier models” now internalize. Extended thinking modes in recent models — where the model produces a long chain of exploratory reasoning before its final answer — can implicitly implement tree search without requiring the external orchestration scaffolding. For pure accuracy on math and code tasks, these native reasoning modes typically match or exceed explicit Tree of Thoughts at comparable total token spend, without the latency penalty from sequential evaluation calls (futureagi.com). The architectural premise of explicit ToT — that you need to externally manage the search — is less compelling when the model can manage it internally.

What the Token Budget Actually Predicts

The mechanism underlying Tree of Thoughts’ strengths and limits comes down to a single observation: the value of explicit search depends on how reliably the model can evaluate its own intermediate outputs.

If the model’s self-evaluation is accurate — if it genuinely can distinguish a promising reasoning branch from a dead end — then Tree of Thoughts works as designed. The search prunes unpromising paths and concentrates effort on productive ones. The cost is justified because the evaluation signal is real.

If the model’s self-evaluation is noisy — and for weaker models, it often is — then the tree search amplifies that noise. Bad branches get scored as promising; good branches get pruned. The branching overhead becomes waste without the signal quality to direct it.

This predicts something testable: Tree of Thoughts should work better as model capability increases, and specifically as the model’s ability to evaluate intermediate steps improves. The mixed-model experiments in the original paper confirm this — the generation-evaluation capability gap matters, not just the raw generation quality.

It also predicts when explicit ToT remains justified even in 2026: tasks where you need transparent, auditable reasoning branches; tasks where the search space is well-defined and the evaluation criterion is reliable; situations where you are not runtime-constrained and can afford the sequential depth. The ReAct Prompting pattern covers dynamic tool-use reasoning with a lighter token footprint. Pydantic AI and similar frameworks that wrap structured multi-step generation can implement constrained search with explicit cost controls. These are not replacements for Tree of Thoughts — they are alternatives for the cases where ToT’s cost structure is the binding constraint.

When it breaks: Tree of Thoughts degrades reliably when the model’s intermediate evaluation quality is poor — either because the model is below the capability threshold for reliable self-scoring, or because the task’s evaluation criterion is subjective enough that intermediate scoring becomes inconsistent. Under these conditions, flat self-consistency at equal token budget produces better results with lower orchestration complexity.

Implementation note:

• princeton-nlp/tree-of-thought-llm: The official reference implementation (v0.1.0, July 2023) has had no commits since its initial release. It is research-grade code, not a production library. Use it to understand the algorithm; build your own orchestration for anything that ships.

The Data Says

Tree of Thoughts is a legitimate reasoning improvement — the Game of 24 results (4% CoT → 74% ToT) are reproducible and substantial (Yao et al. 2023). The cost reality is 5–100× more tokens than chain-of-thought, with sequential evaluation dependencies that add latency beyond raw token count. At equal token budgets, chain-of-thought with self-consistency frequently matches ToT performance on standard benchmarks (Stechly et al. 2024). The approach remains valid for tasks requiring transparent search and reliable intermediate evaluation — but the bar for justifying it over simpler alternatives is higher than the benchmark headlines suggest.