Tree-of-Thoughts (ToT): Branching Decision Trees for Complex Exploration
While Chain-of-Thought (CoT) equips language models with a sequential scratchpad, human cognitive problem-solving rarely proceeds in a single linear pass. Complex tasks—such as mathematical proof discovery, crossword puzzles, creative writing outlines, and architectural system migrations—demand exploring multiple branching hypotheses, looking ahead, evaluating promising trajectories, and backtracking when encountering dead ends.
Tree-of-Thoughts (ToT), formalized by Yao et al. (Princeton/Google DeepMind), generalizes prompt engineering into a formal search problem over an arbitrary state space. In this article, we dissect the state-space representation, heuristic value evaluation, and production Python implementations for both Breadth-First Search (BFS) and Depth-First Search (DFS).
The 4 Core Modalities of Tree-of-Thoughts
- Thought Decomposition: Slicing the macro objective into granular micro-decisions (e.g. generating an arithmetic equation one operator at a time, or scaffolding a database migration table by table).
- Thought Generator $G(p_\theta, s, k)$: Producing $k$ candidate extensions for current state $s$.
- State Evaluator $V(p_\theta, S)$: Assigning scalar heuristic scores $v(s) \in [0, 1]$ or categorical classifications (sure / likely / impossible) by prompting the LLM as an impartial critic.
- Search Algorithm: Orchestrating the frontier using standard Graph Theory traversals (Breadth-First Search or Depth-First Search with branch pruning).
Python Production Implementation: BFS Tree-of-Thoughts
from dataclasses import dataclass, field
from typing import List, Optional
import openai
@dataclass
class ThoughtNode:
state: str
parent: Optional['ThoughtNode'] = None
score: float = 0.0
depth: int = 0
children: List['ThoughtNode'] = field(default_factory=list)
class TreeOfThoughtsSolver:
def __init__(self, model: str = "gpt-4o", max_depth: int = 3, branch_factor: int = 3):
self.model = model
self.max_depth = max_depth
self.branch_factor = branch_factor
self.client = openai.OpenAI()
def generate_thoughts(self, current_state: str) -> List[str]:
prompt = f"Given current state: '{current_state}', propose {self.branch_factor} distinct, promising next steps. List each on a new line starting with '-'."
res = self.client.chat.completions.create(
model=self.model,
temperature=0.7,
messages=[{"role": "user", "content": prompt}]
)
lines = res.choices[0].message.content.split("\n")
return [l.lstrip("- ").strip() for l in lines if l.strip().startswith("-")]
def evaluate_thought(self, state: str) -> float:
prompt = f"Evaluate the viability of this solution state: '{state}'. Output a single float confidence score between 0.0 (impossible) and 1.0 (proven correct)."
res = self.client.chat.completions.create(
model=self.model,
temperature=0.0,
messages=[{"role": "user", "content": prompt}]
)
try:
return float(res.choices[0].message.content.strip())
except ValueError:
return 0.5
def solve_bfs(self, initial_query: str, threshold: float = 0.7) -> Optional[ThoughtNode]:
root = ThoughtNode(state=initial_query, depth=0)
frontier = [root]
for d in range(self.max_depth):
candidates = []
for node in frontier:
thoughts = self.generate_thoughts(node.state)
for t in thoughts:
score = self.evaluate_thought(t)
child = ThoughtNode(state=t, parent=node, score=score, depth=d+1)
node.children.append(child)
if score >= threshold:
candidates.append(child)
if not candidates:
break
# Sort candidates by heuristic score descending, keep top 2
candidates.sort(key=lambda x: x.score, reverse=True)
frontier = candidates[:2]
# Termination check
if frontier[0].score >= 0.95:
return frontier[0]
return frontier[0] if frontier else None