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:

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:

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.