Principle:Princeton nlp Tree of thought llm BFS Tree Search

Knowledge Sources	Tree of Thoughts: Deliberate Problem Solving with Large Language Models Reasoning with Language Model is Planning with World Model
Domains	Search_Algorithms, LLM_Reasoning, NLP
Last Updated	2026-02-14 03:30 GMT

Overview

A tree search algorithm that systematically explores LLM-generated intermediate reasoning steps (thoughts) using breadth-first expansion, evaluation, and selection at each depth level.

Description

BFS Tree Search in the Tree of Thoughts framework addresses the limitation of standard LLM prompting methods (IO, Chain-of-Thought) which generate solutions in a single left-to-right pass without the ability to explore alternatives or backtrack. By decomposing a problem into a sequence of intermediate thought steps and maintaining multiple candidate partial solutions at each level, the algorithm enables deliberate search over the space of reasoning paths.

At each depth level of the tree, the algorithm performs three phases:

1. Generation: Expand each current candidate by producing new thought continuations (via sampling or structured proposal).
2. Evaluation: Score each expanded candidate using LLM-based heuristics (value judgments or voting).
3. Selection: Retain the top-k candidates based on scores (greedy or probabilistic sampling).

This process repeats for a fixed number of steps defined by the task, producing a set of complete solution candidates ranked by accumulated evaluation scores.

Usage

Use this principle when the problem can be decomposed into sequential intermediate steps, where exploring multiple reasoning paths and selecting the best one yields better results than single-pass generation. It is particularly effective for combinatorial problems (e.g., Game of 24), constrained generation (e.g., creative writing with specific requirements), and puzzles where partial progress can be meaningfully evaluated.

Theoretical Basis

The algorithm maintains a set of candidates $Y=\{y_1,...,y_k\}$ at each depth level $t$:

$Y_{t+1}=\text{Select}(\text{Evaluate}(\text{Generate}(Y_t,x)),k)$

Where $x$ is the problem input. The three phases are:

Generation:

# Abstract: expand each candidate with new thoughts
for y in candidates:
    new_thoughts = generate(task, input, y)  # propose or sample
    all_candidates.extend(new_thoughts)

Evaluation:

# Abstract: score each candidate
for y in all_candidates:
    score = evaluate(task, input, y)  # value or vote
    scores.append(score)

Selection:

# Abstract: keep top-k candidates
if method == 'greedy':
    selected = top_k(all_candidates, scores, k)
elif method == 'sample':
    selected = sample_proportional(all_candidates, scores, k)

The BFS approach guarantees that all candidates at depth $t$ are expanded before moving to depth $t+1$, ensuring uniform exploration at each level. This contrasts with DFS, which fully explores one branch before backtracking.

Related Pages

Implemented By

• Implementation:Princeton_nlp_Tree_of_thought_llm_Solve_BFS