tree of thought
**Tree of Thought (ToT)**
**What is Tree of Thought?**
Tree of Thought extends Chain-of-Thought by exploring multiple reasoning paths in parallel, evaluating them, and searching for the best solution. Think of it like playing chess: looking ahead, evaluating positions, and backtracking from bad moves.
**ToT vs CoT**
**Chain-of-Thought (Linear)**
```
Problem ---> Step 1 ---> Step 2 ---> Step 3 ---> Answer
```
Single path, no backtracking.
**Tree of Thought (Branching)**
```
Problem
Approach A
Step A1 ---> Evaluate: promising
Step A1a ---> Dead end, backtrack
Step A1b ---> Solution found!
Step A2 ---> Evaluate: unpromising, prune
Approach B
Step B1 ---> Still exploring...
```
**Core Components**
**1. Thought Generation**
Generate multiple candidate thoughts at each step:
```python
def generate_thoughts(state, n_candidates=3):
prompt = f"Given current state: {state}. Generate {n_candidates} possible next steps."
return llm.generate(prompt, n=n_candidates)
```
**2. Thought Evaluation**
Score each thought for progress toward solution:
```python
def evaluate_thought(state, thought):
prompt = f"State: {state}. Proposed step: {thought}. Rate progress (1-10):"
score = llm.generate(prompt)
return float(score)
```
**3. Search Algorithm**
Explore the tree systematically:
| Algorithm | Description |
|-----------|-------------|
| BFS | Explore all thoughts at each level before going deeper |
| DFS | Go deep first, backtrack on dead ends |
| Beam Search | Keep top-k most promising branches |
**Use Cases**
| Problem Type | Why ToT Helps |
|--------------|---------------|
| Creative writing | Explore different narrative directions |
| Game playing | Look ahead, evaluate positions |
| Puzzle solving | Try multiple approaches, backtrack |
| Planning | Evaluate plan feasibility before committing |
**Performance Considerations**
- Much higher cost (many LLM calls)
- Requires good evaluation function
- Complex to implement correctly
- Not always necessary: CoT often sufficient
ToT is powerful for complex reasoning but should be reserved for problems where simpler methods fail.