---
kind: concept
slug: llm-tree-search
title: LLM tree search
summary: >-
  Search over a language model's own intermediate reasoning steps: the model proposes candidate next steps, scores partial solutions, and breadth-first or depth-first search keeps promising branches and backtracks. No training. Tree of Thoughts reports 74% vs 4% for CoT on Game of 24 (GPT-4), at $0.74 vs $0.47 per problem for best-of-100 CoT. LLM+P instead hands the search to a classical planner.
tags: [inference, reasoning, search, planning, prompting]
papers: ["2305.10601", "2304.11477", "2407.11511"]
related: [chain-of-thought-prompting, in-context-learning, llm-planning, llm-self-evaluation, neural-symbolic-integration, a-star-search, llm-serving, self-consistency, self-refinement]
status: draft
updated_at: 2026-10-31
---

## Overview

LLM tree search wraps a language model in a search over partial solutions. The
problem is cut into steps, each step is a "thought" (for example one equation,
one paragraph plan or one crossword word), and the search tree's nodes are the
input plus the thoughts chosen so far [arxiv:2305.10601 §3]. A chain of
thought commits to one path. A tree lets the model try several next steps, look
at how promising each partial solution is, and abandon hopeless ones instead of
finishing them [arxiv:2305.10601 §1, §2].

The variants share the search itself: candidate steps are expanded, partial
states are scored, and a classic procedure (breadth-first or depth-first, with
pruning) decides what to expand next [arxiv:2305.10601 §3]. They differ in who
does the search. In the tree-search variants, the same frozen model proposes
the candidates and judges them, so the search is only as good as its judgment
of partial progress. In the offloaded variant, the model only writes a formal
problem file, and a classical planner does the searching [arxiv:2304.11477 §3.3].
Nothing is trained in either case.

Three cards cover the concept. [Tree of Thoughts](/papers/2305.10601) defines the
method and its headline results. [LLM+P](/papers/2304.11477) offers the
offloaded alternative, and its planning baseline is a breadth-first tree search
written by the LLM+P authors. [Multi-Step Reasoning with Large Language Models,
a Survey](/papers/2407.11511) places tree search in a wider taxonomy: it sorts
prompt-based reasoning methods into step generation, step evaluation and
control, and files tree search under control, next to greedy chains and
ensembles [arxiv:2407.11511 §3]. The survey proposes no method and runs no
experiments of its own, so its numbers are copies of the original studies'
results [arxiv:2407.11511 §3, tab. 2]. Other tree-search methods exist, such as
the Monte Carlo tree search of [Reasoning with Language Model is
Planning with World Model](https://arxiv.org/abs/2305.14992), but they have no
card on wikillm, so nothing from them is summarized here.

## Variants

### Breadth-first search with a propose generator and value evaluator

This is the configuration behind the headline results on Game of 24. At each
node a single "propose" prompt returns several candidate next equations in one
call. Each candidate is judged as sure, maybe or impossible to reach the target,
the judgment is sampled several times, and the search keeps the best few states
per level [arxiv:2305.10601 §4.1]. The breadth limit is 5 in the main setting
and 1 as an ablation. With GPT-4, breadth 5 reaches 74% success and breadth 1
reaches 45%, against 4.0% for a single CoT sample and 9.0% for CoT with 100
sampled chains and voting [arxiv:2305.10601 tab. 2]. Card:
[Tree of Thoughts](/papers/2305.10601).

The paper's search-efficiency plot shows the tree beating best-of-k CoT when
both are charged by the number of nodes visited [arxiv:2305.10601 §4.1 fig. 3].

### Depth-first search with pruning and backtracking

For deeper trees, the paper uses depth-first search over up to 10 thoughts, one
per clue in a 5x5 crossword. A state is discarded as soon as any remaining clue
is judged impossible under its letter constraints, and the search backtracks to
the parent [arxiv:2305.10601 §4.3]. On 20 games, word-level success is 60%
against 15.6% for CoT, and the game-level success is 20% against 1 game for
CoT [arxiv:2305.10601 tab. 3]. The paper's ablations show that both parts
matter here. Without pruning, word-level success falls to 41.5%, and without
backtracking it falls to 20% [arxiv:2305.10601 tab. 3]. Search is capped at 100
steps [arxiv:2305.10601 §4.3]. Card: [Tree of Thoughts](/papers/2305.10601).

### Sampled generator with vote evaluator for open-ended text

When thoughts are free text, such as a paragraph-level writing plan, the paper
samples the candidates independently, because independent samples are already
diverse. It then asks the model to vote for the best candidate in a
multiple-choice comparison, instead of asking for a numeric score, because
coherence is hard to score directly. The breadth is 1, with 5 plans and 5 votes
per step [arxiv:2305.10601 §3, §4.2]. On 100 writing prompts, the average GPT-4
coherency score is 7.56 for tree search, 6.93 for CoT and 6.19 for direct
prompting [arxiv:2305.10601 §4.2 fig. 5]. In the paper's blind pairwise
comparison by a subset of the authors, tree search was preferred in 41 pairs,
CoT in 21 and 38 were judged similar [arxiv:2305.10601 §4.2]. The gap is small
in absolute terms and the human judgments come from a few authors, so the result
should be read as a signal rather than a benchmark. Card:
[Tree of Thoughts](/papers/2305.10601).

### Beam search with self-evaluation

The survey lists beam search with self-evaluation as a search-control method,
next to Tree of Thoughts [arxiv:2407.11511 §3.3.3]. Its reported gains for
Codex over chain-of-thought are +6.34 points on GSM8K, +9.56 on AQuA and +5.46
on StrategyQA [arxiv:2407.11511 tab. 2]. The survey's "+" values are relative
to a baseline it describes as typically GPT-3.5 [arxiv:2407.11511 tab. 2], and
the survey gives no detail of the search itself. The cited study has no card on
wikillm, so this page cannot describe its mechanics or settings. Use it only as
a pointer; check the original paper before implementing it.

### Offload the search to a classical planner

Here the model is a translator rather than a searcher. It turns a natural-language
planning task into a PDDL problem file, using one (description, PDDL) example
from the same domain as context. A domain file, written once per domain by a
person, describes the actions. A classical planner (Fast Downward, optimal alias)
then searches for the plan [arxiv:2304.11477 §3.1–§3.3, §5.2]. With GPT-4 over
seven domains, optimal-plan success is 90% on Blocksworld, 95% on Grippers, 85%
on Storage and 0% on Floortile. Direct GPT-4 plans reach at most 35% in any
domain, and the same pipeline without the example scores 0 everywhere
[arxiv:2304.11477 tab. 1]. Card: [LLM+P](/papers/2304.11477).

This variant is not a tree search by the model, and it is not a general method:
it works only where a planner can handle the domain's action model. The paper's
own failure analysis points to the generated problem file, such as a missing
initial condition that makes the problem unsolvable [arxiv:2304.11477 §5.3].

## When to use which

The choices below follow from the constraints each setting imposed in the
paper. The paper measured them on GPT-4 unless stated.

| Situation | Use | Why |
|---|---|---|
| Thoughts are short and constrained (one equation, one word), so independent samples would repeat each other | Propose generator: one call returns several candidates | Keeps candidates distinct within a single context [arxiv:2305.10601 §3] |
| Thoughts are long free text where independent samples differ | Sampled generator, k independent draws | Diversity comes from sampling; no list to parse [arxiv:2305.10601 §3, §4.2] |
| A partial state can be checked for success (can the numbers still reach the target; can this clue still be filled) | Value evaluator with a threshold, to prune | The LM's judgment prunes whole subtrees [arxiv:2305.10601 §4.1, §4.3] |
| Success is hard to score directly (coherence, style) | Vote across candidates, then keep the winner | The paper used a vote for this case, not a numeric score [arxiv:2305.10601 §3, §4.2] |
| Solution has 3 steps or fewer and the frontier can stay small (breadth around 5) | Breadth-first search | The paper uses it for Game of 24 and writing, where depth is small [arxiv:2305.10601 §3] |
| Solution is deeper and dead ends can be detected | Depth-first search with pruning and backtracking | The paper uses it for crosswords, with pruning and backtracking both shown to matter [arxiv:2305.10601 §3, §4.3] |
| The task has a formal action model per domain and a planner that handles it | Offload the search to a classical planner | The planner does the search, so the model only has to write a correct problem file. Results vary by domain: Blocksworld 90%, Grippers 95%, Storage 85%, Floortile 0% [arxiv:2304.11477 tab. 1, §3.3] |
| No formal model exists, and the task is open-ended | LM-driven tree search | The offloaded variant needs a hand-written domain file [arxiv:2304.11477 §3.3]; tree search needs only prompts and an LM judge [arxiv:2305.10601 §3] |
| Many LLM calls per problem would exceed the latency budget | Shallow search, or a single planner call | The LLM+P authors report that the tree baseline usually timed out on planning tasks because of the number of LLM calls [arxiv:2304.11477 §5.3] |
| One chain already does well, such as the zero-shot math and commonsense tasks in the appendix | Plain CoT | Tree search gained only 4 points on GSM8K (86 to 90) and 1 on StrategyQA (82 to 83) [arxiv:2305.10601 app. B tab. 4] |
| Weaker model, such as GPT-3.5 | Tree search, measured before adoption | Gains persist but are smaller: Game of 24 goes from 3% (CoT) to 19% (ToT), and writing from 5.16 to 6.62 [arxiv:2305.10601 app. B tab. 5, tab. 6] |
| Per-call cost is tight | CoT with sampling, or tree search only if its gain justifies the cost | Game of 24 with tree search costs $0.74 per problem, against $0.47 for 100 CoT samples [arxiv:2305.10601 app. B.3 tab. 7] |
| The answer is one short value that independent chains can agree on, and the budget allows several chains | Ensemble of sampled chains with a majority vote, no tree | Voting over chains works when the output space is small enough, such as multiple choice [arxiv:2305.10601 §2]. The survey groups this under the ensemble control strategy [arxiv:2407.11511 §3.3.2] |

Tree search needs a per-task prompt set. Each task in the paper uses its own
thought format, prompts and output parser [arxiv:2305.10601 §4]. Budget
engineering time for that, not only for the search loop.

## Implementation sketch

Breadth-first search with a propose generator and a value evaluator. The
search loop is the common core; the prompts, the thought format and the parser
are per task [arxiv:2305.10601 §3, §4.1]. Swap the loop for a recursion with a
threshold check to get the depth-first variant.

```pseudocode
# State = list of thoughts so far, starting from the problem alone [§3]
def tree_search(problem, llm, depth, breadth, k):
    frontier = [[problem]]
    for step in range(depth):
        # Expand each kept state with up to k candidate next thoughts [§4.1]
        children = []
        for state in frontier:
            for thought in propose_thoughts(llm, state, k):
                children.append(state + [thought])
        # Score each child with the same LM, used as the search heuristic [§3]
        scored = [(score_state(llm, c), c) for c in children]
        # Prune to the best `breadth` states at this depth [§3]
        frontier = [c for _, c in top(scored, breadth)]
    # Write the final answer from the best state the search found [§3]
    best = max(frontier, key=lambda s: score_state(llm, s))
    return write_answer(llm, best)
```

Depth-first pruning differs in three places. Children are tried in order of
promise. A child whose score falls below a threshold is skipped, so its whole
subtree is never explored. The function returns to its parent when no children
remain, which is the backtrack step [arxiv:2305.10601 §3, alg. 2].

The offloaded variant has no tree. It makes one model call for the problem file
from the example, runs the planner on the fixed domain file and that problem
file, and returns the plan [arxiv:2304.11477 §3.3]. A failed or malformed model
reply becomes an unsolvable problem, so check the reply before the planner runs.

## Contradictions

Whether tree search over model-generated thoughts helps on planning tasks. The
Tree of Thoughts paper reports large gains on Game of 24 and mini crosswords
[arxiv:2305.10601 tab. 2, tab. 3]. The LLM+P paper adapts the same breadth-first
search to PDDL planning and reports that it trails its own direct-LLM baseline:
optimal-plan success is 0% on Blocksworld against 20% for direct GPT-4 plans,
and 10% on Grippers against 25% [arxiv:2304.11477 tab. 1]. It attributes the
weak result mainly to the number of LLM calls, which made many runs time out
[arxiv:2304.11477 §5.3]. The two papers use different tasks and search settings,
and the LLM+P version is the LLM+P authors' own adaptation, so the numbers are
not directly comparable. Neither paper tests the other's setting.

A second disagreement is about labels, not results. The Tree of Thoughts paper
keeps the model frozen and trains nothing [arxiv:2305.10601 §3]. The survey
files Tree-of-Thoughts under reinforcement-learning control in its Table 2
[arxiv:2407.11511 tab. 2], and its text describes the control methods as
external algorithms around the LLM [arxiv:2407.11511 §3.3.3]. Reading "reinforcement
learning" in the survey as a training requirement would be wrong for this
method, so check the method's own paper before deciding whether training is
needed.

## Pitfalls

- **Algorithm 2 as printed has a typo.** The pruning test in the depth-first
  listing evaluates the wrong state against the threshold. The text and the
  described method evaluate the child against it [arxiv:2305.10601 alg. 2, §3].
  The listing also does not stop after recording an output at the final depth,
  so an implementation needs an explicit return there [arxiv:2305.10601 alg. 2].
- **Propose mode does not fix the number of children.** The prompt returns as
  many candidates as the model writes, so frontier size and cost vary by node
  [arxiv:2305.10601 §3].
- **Heuristic scores are ad hoc.** The paper describes value judgments as
  qualitative classes (sure, maybe, impossible). Any numeric mapping and any
  weighting of votes is a design choice that changes the ranking
  [arxiv:2305.10601 §4.1, §4.3].
- **Evaluator errors prune correct answers.** On crosswords, the model sometimes
  judges a valid but rare word as impossible, which removes solvable branches
  [arxiv:2305.10601 §4.3]. Even the best state chosen by an oracle solves only
  35% of games, against 20% for the search's own choice [arxiv:2305.10601 tab. 3].
- **Cost grows with evaluation.** Each candidate gets several value calls, and
  the authors estimate 5 to 100 times more generated tokens than CoT, depending
  on prompts and search. The appendix suggests stopping early once a solution
  is found [arxiv:2305.10601 app. B.3].
- **Bad problem files fail silently in the offloaded variant.** The planner
  cannot tell a wrong problem file from an unsolvable task. The paper's main
  failure is a missing or wrong initial condition [arxiv:2304.11477 §5.3].
- **One example per domain.** The offloaded results rest on a single
  (description, PDDL) example per domain, and the paper does not vary it
  [arxiv:2304.11477 §3.2, §5.1].
- **Timeouts fall back to sub-optimal plans.** An optimal planner returns an
  optimal plan only if it finishes within its time limit (200 s in the paper)
  [arxiv:2304.11477 §5.2].
- **Small evaluations.** The main tree-search results use 100 games, 100 writing
  prompts and 20 crosswords. Model snapshots are from May 2023
  [arxiv:2305.10601 §4]. The LLM+P results use 20 tasks in each of 7 domains
  [arxiv:2304.11477 §5.1].

## Papers

- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](/papers/2305.10601): defines the thought-based search with BFS and DFS, and reports results on Game of 24, Creative Writing and Mini Crosswords.
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](/papers/2304.11477): has the LLM write a PDDL problem file from one example and hands the search to a classical planner; its tree-search baseline is an adaptation of Tree of Thoughts to planning.
- [Multi-Step Reasoning with Large Language Models, a Survey](/papers/2407.11511): taxonomy of prompt-based reasoning (generation, evaluation, control) that places tree search among control methods; reports the cited papers' numbers without re-running them.