Tree of Thoughts in Large Language Models: How Search Trees, State Evaluation, and Backtracking Expand Deliberate Reasoning

Standard autoregressive large language models generate text sequentially from left to right. At each step $t$, the network samples the next token according to a conditional probability distribution over the vocabulary:

P(w_t | w_1, w_2, ..., w_{t-1})

While Chain-of-Thought (CoT) prompting (Wei et al., 2022) encourages models to output intermediate reasoning steps, the underlying computational process remains a linear path through token space. If the model makes an early logical error or chooses a suboptimal problem decomposition, subsequent token generation proceeds from that flawed prefix with no native lookahead or error-recovery mechanism.

Sampling methods such as Self-Consistency (Wang et al., 2022) address variance by generating multiple independent reasoning trajectories and taking a majority vote over final answers. However, self-consistency evaluates trajectories only at the final token. It cannot assess intermediate reasoning states, prune unpromising branches early, or combine promising partial solutions from different paths.

Tree of Thoughts (ToT), introduced by Yao et al. (2023) and explored concurrently by Long (2023), formalizes language model reasoning as deliberate search over a state space. By breaking complex tasks into discrete semantic units ("thoughts") and pairing language generation with tree search algorithms, ToT enables systematic exploration, heuristic state evaluation, lookahead, and backtracking.

State Space Formulation

Tree of Thoughts frames problem-solving as traversing a directed tree $T = (V, E)$.

Each node in the tree represents a state $s = (x, z_{1...i})$, where $x$ is the input task description and $z_{1...i} = [z_1, z_2, \dots, z_i]$ is a sequence of intermediate thoughts generated up to depth $i$.

A "thought" $z_i$ is a coherent linguistic unit designed for the specific problem domain. Depending on the task, a thought may correspond to:

• A single mathematical operation or sub-equation.
• A candidate word placement on a crossword grid.
• A paragraph-level outline or reasoning checkpoint.

Directed edges $(s, s')$ represent valid state transitions where child state $s' = (x, z_{1...i}, z_{i+1})$ extends the parent state by appending an additional thought $z_{i+1}$.

Core Architectural Modules

The ToT framework operates through four interconnected components:

1. Thought Decomposition

Before searching, the problem space is structured into discrete decision stages. Unlike token-level beam search, which operates at the subword level and incurs massive combinatorial bloat, thought-level decomposition operates at a higher semantic abstraction. This allows the model to reason over meaningful semantic steps rather than individual tokens.

2. Thought Generator: $G(p_\theta, s, k)$

Given a current state $s$, the thought generator produces $k$ candidate next thoughts $z_{i+1}$. Two primary generation strategies are used:

• Sample Strategy: Generating $k$ independent candidate thoughts by invoking the model $k$ times with an identical prompt and a non-zero temperature parameter ($T > 0$). This is effective when the thought space is rich and diverse (such as generating distinct paragraph drafts).
• Propose Strategy: Generating $k$ distinct candidate thoughts sequentially within a single model invocation using a structured 1-shot or few-shot prompt. This approach minimizes API overhead and prevents duplicate suggestions when the action space is constrained (such as listing available arithmetic operations).

3. State Evaluator: $V(p_\theta, S)$

The evaluator computes heuristic scores for frontier states to guide search direction. Two valuation methods determine whether a state warrants further exploration:

• Value Function (Independent Scoring): The model assesses each state $s$ independently and outputs a scalar score (such as 1 to 10) or a categorical classification ("sure", "likely", "impossible"). For example, in constraint satisfaction tasks, if a partial state violates a rule, the evaluator classifies it as "impossible" and immediately prunes the subtree.
• Vote Function (Comparative Scoring): The model receives multiple candidate states simultaneously and selects the most promising option via pairwise or group comparison. This is preferred when absolute scoring is poorly calibrated or when evaluating creative quality.

4. Search Algorithm

Once candidate generation and state evaluation are defined, classical search algorithms traverse the state space:

• Breadth-First Search (BFS): At each depth step, the algorithm expands all current frontier states, evaluates the new candidates, and retains only the top-$b$ highest-scoring states (beam search over thought nodes). BFS is suited for problems with bounded depth and well-defined intermediate evaluation metrics, such as arithmetic games.
• Depth-First Search (DFS): The algorithm explores the most promising branch until it reaches a terminal solution or until the state value falls below a pruning threshold $\tau$. When a branch fails, the search backtracks to the parent node and explores the next highest-rated alternative. DFS is suited for complex constraint-satisfaction problems where deep exploration is required before reaching a valid state.

Empirical Performance Across Problem Classes

In the benchmark evaluations conducted by Yao et al. (2023), Tree of Thoughts demonstrated marked improvements on tasks requiring lookahead and global planning:

Game of 24

In the Game of 24, the objective is to use four numbers and basic arithmetic operations $(+, -, \times, /)$ to arrive at 24.

• Standard Input-Output (IO) prompting achieved a success rate of 7.3%.
• Chain-of-Thought (CoT) prompting achieved a success rate of 7.3%.
• CoT with Self-Consistency across 100 samples reached 9.0%.
• Tree of Thoughts with BFS ($b=1$) achieved 45.0%.
• Tree of Thoughts with BFS ($b=5$) achieved 74.0%.

The dramatic performance gain stemmed from early pruning: when an intermediate step yielded unreachable numbers (such as fractions or excessively large integers), the evaluator labeled the state "impossible," forcing the search to explore alternative arithmetic branches.

5x5 Mini Crosswords

In 5x5 Mini Crosswords, a model must satisfy intersecting horizontal and vertical clue constraints simultaneously.

• Standard CoT solved only 15.6% of individual words and 0.0% of complete crossword grids.
• Tree of Thoughts using DFS with backtracking solved 60.0% of individual words and 7.8% of complete crossword puzzles.

Backtracking enabled the model to replace conflicting letters when downstream vertical clues became unsolvable, preventing dead-end lock-in.

Creative Writing

In text generation tasks requiring adherence to multiple structural constraints (such as writing a four-paragraph story where each paragraph ends with a specific target sentence), ToT separated planning from writing. The model generated and voted on intermediate paragraph plans before generating final prose. Evaluators preferred ToT outputs over CoT baselines in over 60% of blind comparisons.

Extensions: From Trees to Graphs and World Models

The principles of Tree of Thoughts have been extended into broader search topologies and agent planning architectures:

Graph of Thoughts (GoT)

Besta et al. (2023) generalized ToT to Directed Acyclic Graphs (DAGs). Graph of Thoughts introduces transformations beyond branching and backtracking:

• Thought Combination: Merging multiple distinct thought trajectories into a single consolidated state (such as combining separate document summaries).
• Thought Aggregation: Synthesizing the best elements of several candidate solutions into an improved iteration.
• Thought Refinement Loops: Applying cyclic update operations to refine a thought node based on automated feedback.

Reasoning via World Models (RAP and MCTS)

Hao et al. (2023) introduced Reasoning with Language Model is Planning with World Model (RAP), framing reasoning as Monte Carlo Tree Search (MCTS). In RAP, the language model serves dual roles:

1. An internal world model that predicts environment state transitions.
2. A reward model that provides heuristic evaluation functions to balance exploration and exploitation via the Upper Confidence Bound for Trees (UCT) formula.

Serving Economics and KV Cache Implications

Implementing tree search over language models introduces specific computational costs and memory management challenges:

Computational Complexity

A standard CoT generation requires a single autoregressive sequence of length $L$. In contrast, a Tree of Thoughts execution with branching factor $b$ and search depth $d$ requires up to $O(b^d)$ model invocations. While pruning reduces the active search space, total token consumption remains substantially higher than linear sampling.

KV Cache Management

In standard linear inference engines, key-value (KV) activations are cached sequentially. In tree search, multiple candidate branches share common prefix states (the root and intermediate parent thoughts).

Naive implementations that send the full prefix text on every API call incur redundant prefill computation. Modern serving engines (such as SGLang with RadixAttention or vLLM with prefix caching) maintain tree-structured KV caches in GPU memory. This allows new candidate branches to reuse the parent node's pre-computed KV tensors directly, reducing prefill latency across multi-branch evaluations.

Sources

• Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al., 2023)
• Large Language Model Guided Tree-of-Thought (Long, 2023)
• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., 2023)
• Reasoning with Language Model is Planning with World Model (Hao et al., 2023)
• Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (Wei et al., 2022)
• Self-Consistency Improves Chain of Thought Reasoning in Language Models (Wang et al., 2022)