Tree of Thoughts (ToT): Mathematical Foundations, Thought Decomposition, State Evaluation, and Tree Search Algorithms in Large Language Models

Autoregressive large language models generate text left-to-right via token-level greedy or stochastic decoding. While Chain-of-Thought (CoT) prompting enables models to generate intermediate reasoning steps, standard inference remains constrained to a single linear trajectory. In complex problem-solving environments requiring combinatorial planning, heuristic evaluation, and lookahead, single-trajectory generation suffers from compounding errors and an inability to backtrack from early dead ends.

The Tree of Thoughts (ToT) framework, introduced by Yao et al. (2023) and independently formalized by Long (2023), generalizes Chain-of-Thought by framing reasoning as search over a decision tree. Under ToT, an LLM serves simultaneously as a thought generator and a heuristic state evaluator, enabling standard search algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS) to explore, evaluate, and backtrack across intermediate reasoning states.

Mathematical Formulation of Tree of Thoughts

In classical AI problem solving, a search problem is defined by a state space, a transition function, and an evaluation heuristic. Tree of Thoughts instantiates these primitives directly within the prompting and sampling mechanics of a pre-trained language model $p_\theta$.

Let $x$ denote the problem input. A reasoning trajectory is decomposed into a sequence of discrete intermediate units termed thoughts:

$$s_t = [x, z_1, z_2, \dots, z_t]$$

where each $z_i \in \mathcal{Z}$ is a coherent text sequence representing an intermediate reasoning step (such as an intermediate arithmetic equation, an outline section, or a candidate move).

The Tree of Thoughts architecture is defined by four core modules:

1. Thought Decomposition

Before initiating search, the problem domain requires a definition of thought granularity. The step size $z_t$ must be large enough for the model to evaluate its promise toward solving $x$, yet small enough to allow diverse branching and pruning before committing to full solutions.

2. Thought Generation Mechanism

Given a current state $s = [x, z_{1 \dots t-1}]$, the thought generator $G(p_\theta, s, k)$ produces a set of $k$ candidate next steps $\{z^{(1)}, z^{(2)}, \dots, z^{(k)}\}$. Two primary generation strategies are used depending on the domain:

• Sample i.i.d. Thoughts: The model samples $k$ independent completions from a generation prompt $z^{(i)} \sim p_\theta(\text{prompt}(s))$. This approach is preferred when the thought space is rich and unconstrained (for example, generating diverse paragraph outlines in creative writing).
• Propose Candidates Sequentially: The model generates all $k$ candidate thoughts in a single prompt call $[z^{(1)}, \dots, z^{(k)}] \sim p_\theta(\text{prompt}(s))$. This is preferred when thoughts are highly constrained (such as listing available arithmetic operations), preventing duplicate generation and saving inference calls.

3. State Evaluation Heuristics

The state evaluator $V(p_\theta, S)$ computes a heuristic quality score for a set of candidate states $S = \{s\}$. Rather than relying on external reward models or hand-crafted scoring functions, ToT queries the language model to deliberate on state quality through two evaluation paradigms:

• Value Prompt (Independent State Valuation): The model evaluates a state $s$ independently, outputting a scalar score $v(s) \in [0, 1]$ or a categorical rating such as sure, maybe, or impossible. Categorical judgments are mapped to numerical heuristics to guide pruning thresholds. Multiple evaluation samples can be averaged to reduce heuristic variance.
• Vote Prompt (Comparative State Valuation): When absolute state quality is difficult to quantify, the model compares a set of candidate states $S$ within a single context window and votes for the most promising continuation $s^* = \arg\max_{s \in S} \text{Vote}(p_\theta, S)$.

4. Search Algorithms

Tree of Thoughts decouples state generation and evaluation from the search traversal algorithm. The two primary search topologies implemented are:

• Breadth-First Search (ToT-BFS): At each step $t \in [1, T]$, the algorithm maintains a beam of the top-$b$ most promising states $S_t$. It expands all states in $S_{t-1}$ using $G(p_\theta, s, k)$, evaluates the resulting candidate frontier $S'_t$ using $V(p_\theta, S'_t)$, and selects the top-$b$ states for the next round. BFS is optimal for fixed-depth planning where candidate pruning early in the tree bounds total compute.
• Depth-First Search (ToT-DFS): The algorithm explores a promising branch until it reaches a leaf node or encounters a state where $V(p_\theta, \{s'\}) < v_{\text{threshold}}$. Upon triggering the threshold condition, the entire subtree is pruned, and the algorithm backtracks to the parent node to evaluate the next candidate branch. DFS is optimal for combinatorial constraint satisfaction problems with variable tree depth.

Reasoning Paradigms: IO vs. CoT vs. CoT-SC vs. ToT

To understand the computational trade-offs of deliberate tree search, we compare four distinct inference paradigms across topology, evaluation timing, and error recovery:

• Input-Output (IO) Prompting:
• Topology: Direct mapping from input $x$ to output $y$.
• State Space: Zero intermediate states ($T = 1$).
• Lookahead: None.
• Backtracking: Impossible.
• Computational Cost: Single generation call ($O(1)$).
• Chain-of-Thought (CoT) Prompting:
• Topology: Linear sequence $x \to z_1 \to z_2 \to \dots \to y$.
• State Space: Single deterministic or sampled path.
• Lookahead: Local autoregressive token logits.
• Backtracking: Impossible; an error at step $t$ corrupts all subsequent steps $t+k$.
• Computational Cost: Single generation call ($O(1)$).
• Chain-of-Thought with Self-Consistency (CoT-SC):
• Topology: Parallel independent chains $[x \to \text{Path}_1, \dots, x \to \text{Path}_k]$.
• State Space: $k$ fully independent linear trajectories.
• Evaluation: Majority voting over final outputs $y_1, \dots, y_k$.
• Backtracking: None; does not evaluate intermediate steps or recombine shared reasoning prefixes.
• Computational Cost: $k$ independent generation trajectories ($O(k)$).
• Tree of Thoughts (ToT):
• Topology: Branching decision tree with explicit node states.
• State Space: Frontier of partial solution states explored via BFS or DFS.
• Evaluation: Step-level heuristic scoring via LM value or vote prompts.
• Backtracking: Full subtree pruning and parent backtracking.
• Computational Cost: Proportional to beam width, branching factor, and depth ($O(b \cdot k \cdot T)$).

Empirical Performance Across Complex Reasoning Benchmarks

The Tree of Thoughts framework was evaluated on three distinct problem domains that require search, planning, and global constraint satisfaction:

Game of 24

In Game of 24, the model is given four numbers and must apply basic arithmetic operations ($+, -, \times, \div$) to reach exactly 24, using each number once. Success requires finding a valid operational sequence out of numerous combinatorial permutations.

• GPT-4 Standard IO Prompting: 4.0% success rate.
• GPT-4 Chain-of-Thought (CoT): 7.3% success rate.
• GPT-4 CoT with Self-Consistency ($k=100$): 9.0% success rate.
• GPT-4 Tree of Thoughts (BFS, beam width $b=5$): 74.0% success rate.

The 10x performance gain highlights the failure of linear decoders on arithmetic planning: while CoT frequently commits to an invalid first operation and fails, ToT evaluates intermediate remaining-number states (rating them sure, maybe, or impossible) and prunes unviable paths before token generation proceeds.

Creative Writing

The creative writing task requires generating a coherent 4-paragraph passage where each paragraph ends with a specific input sentence constraint (out of 4 randomly sampled constraints).

• Evaluation Metric: 100-sample pairwise GPT-4 comparative coherence scoring and human evaluation.
• Results: Standard IO and CoT models frequently fail to satisfy all 4 ending constraints simultaneously or produce disjointed narrative shifts. ToT generates diverse 5-step paragraph plans ($k=5$), votes on the most coherent plan, and then expands each paragraph sequentially with step-level validation, significantly outperforming CoT in plan adherence and overall narrative quality.

5x5 Mini Crosswords

In 5x5 mini crosswords, the model must solve 10 intersecting word clues (5 horizontal, 5 vertical). Errors in one word directly break orthogonal constraints across intersecting cells.

• GPT-4 CoT / CoT-SC Success Rate: Word-level success below 16%, game-level success 0%.
• GPT-4 Tree of Thoughts (DFS with backtracking): Word-level success rate of 60%, solving complete crosswords in 20% of trials.
• Mechanism: Using DFS with a depth limit of 10, ToT proposes candidate words for unfilled slots, verifies cross-clue feasibility, and backtracks when an intersecting letter creates an impossible constraint.

Computational Complexity and Production Serving Optimizations

While Tree of Thoughts achieves significant accuracy gains on planning tasks, it introduces non-trivial inference overhead. For a BFS search with tree depth $T$, branching factor $k$, and beam width $b$, total LLM calls scale as:

$$\mathcal{C}_{\text{calls}} = O(b \cdot k \cdot T)$$

In production LLM serving architectures, this inference overhead can be mitigated through several systems-level optimizations:

• Radix Tree and Prefix Caching: Because all child thoughts at step $t$ share an identical ancestor context $[x, z_1, \dots, z_{t-1}]$, inference engines such as vLLM, SGLang, and TensorRT-LLM can reuse the KV cache of parent nodes via automatic prefix caching, eliminating redundant prefill computation.
• Batched Generation and Evaluation: Multiple candidate thoughts $z^{(1)}, \dots, z^{(k)}$ and their corresponding evaluation prompts can be batched concurrently across GPU worker streams, reducing end-to-end wall-clock latency.
• Dynamic Early Exiting: If any generated leaf state achieves a deterministic verification score (such as exact arithmetic equality to 24 in Game of 24), the search tree can terminate immediately without exploring remaining beam candidates.

Sources

• Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al., NeurIPS 2023 / arXiv:2305.10601)
• Large Language Model Guided Tree-of-Thought (Long, 2023 / arXiv:2305.08291)
• Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (Wei et al., NeurIPS 2022 / arXiv:2201.11903)
• Self-Consistency Improves Chain of Thought Reasoning in Language Models (Wang et al., ICLR 2023 / arXiv:2203.11171)
• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024 / arXiv:2308.09687)