LLM tree search

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 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 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 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 2304.11477 §3.3. Nothing is trained in either case.

Three cards cover the concept. Tree of Thoughts defines the method and its headline results. LLM+P 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 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 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 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, 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 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 2305.10601 tab. 2. Card: Tree of Thoughts.

The paper's search-efficiency plot shows the tree beating best-of-k CoT when both are charged by the number of nodes visited 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 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 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% 2305.10601 tab. 3. Search is capped at 100 steps 2305.10601 §4.3. Card: Tree of Thoughts.

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 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 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 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.

Beam search with self-evaluation

The survey lists beam search with self-evaluation as a search-control method, next to Tree of Thoughts 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 2407.11511 tab. 2. The survey's "+" values are relative to a baseline it describes as typically GPT-3.5 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 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 2304.11477 tab. 1. Card: LLM+P.

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 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.

Tree search needs a per-task prompt set. Each task in the paper uses its own thought format, prompts and output parser 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 2305.10601 §3, §4.1. Swap the loop for a recursion with a threshold check to get the depth-first variant.

# 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 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 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 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% 2304.11477 tab. 1. It attributes the weak result mainly to the number of LLM calls, which made many runs time out 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 2305.10601 §3. The survey files Tree-of-Thoughts under reinforcement-learning control in its Table 2 2407.11511 tab. 2, and its text describes the control methods as external algorithms around the LLM 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 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 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 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 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 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 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 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 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 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) 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 2305.10601 §4. The LLM+P results use 20 tasks in each of 7 domains 2304.11477 §5.1.

Papers

• Tree of Thoughts: Deliberate Problem Solving with Large Language Models: 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: 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: taxonomy of prompt-based reasoning (generation, evaluation, control) that places tree search among control methods; reports the cited papers' numbers without re-running them.