Chapter 11 · Tree of Thoughts and Prompt Chaining

Chapter goals: Master the search and evaluation mechanisms of Tree of Thoughts (ToT), understand the stepwise strategy of Prompt Chaining, and learn to combine advanced prompt techniques to solve complex problems.

11.1 Tree of Thoughts (ToT)

ToT extends CoT. The core idea: model the reasoning process as a tree structure, generating multiple possible "thoughts" at each step, then selecting the optimal path via a search algorithm.

ToT vs CoT

Feature	CoT	ToT
Reasoning structure	Linear sequence	Tree-shaped branches
Exploration ability	Single path	Multi-path search
Backtracking ability	❌ No	✅ Yes
Computational cost	Low	High
Applicable scenarios	Simple reasoning	Complex planning / search

Three Core Components of ToT

1. Thought Generator: given the current state, generate multiple possible next thoughts
2. State Evaluator: evaluate the potential of each thought (0–1 score)
3. Search Algorithm: breadth-first search (BFS) or best-first search

from typing import List, Tuple
import heapq

class TreeOfThoughts:
    def __init__(self, llm, max_depth=5, branching_factor=3):
        self.llm = llm
        self.max_depth = max_depth
        self.branching_factor = branching_factor
    
    def generate_thoughts(self, state: str, n: int) -> List[str]:
        """Generate n possible next thoughts"""
        prompt = f"""Given the current state: "{state}"
Generate {n} possible next thoughts, each starting with "Thought: "
"""
        response = self.llm.complete(prompt)
        return self._parse_thoughts(response)
    
    def evaluate_thought(self, thought: str, goal: str) -> float:
        """Evaluate how close a thought is to the goal"""
        prompt = f"""On a scale of 0 to 1, how close is this thought to solving the problem?
Goal: {goal}
Thought: {thought}
Rating (0-1):"""
        score = self.llm.complete(prompt)
        return float(score.strip())
    
    def search(self, initial_state: str, goal: str) -> Tuple[str, List[str]]:
        """Use Best-First Search to find a solution"""
        # Priority queue: (-score, depth, state, path)
        heap = [(-1.0, 0, initial_state, [initial_state])]
        visited = {initial_state}
        
        while heap:
            neg_score, depth, state, path = heapq.heappop(heap)
            
            if self._is_goal(state, goal):
                return state, path
            
            if depth >= self.max_depth:
                continue
            
            # Generate new thoughts
            thoughts = self.generate_thoughts(state, self.branching_factor)
            for thought in thoughts:
                if thought not in visited:
                    visited.add(thought)
                    score = self.evaluate_thought(thought, goal)
                    heapq.heappush(heap, (-score, depth + 1, thought, path + [thought]))
        
        return None, path

11.2 Prompt Chaining

Prompt Chaining decomposes a complex task into multiple sub-tasks, where each sub-task's output becomes the next sub-task's input:

Task decomposition:
Original question → Sub-task 1 → Intermediate result 1 → Sub-task 2 → Intermediate result 2 → ... → Final answer

Implementation Example

def prompt_chaining(question: str, llm) -> dict:
    """
    Multi-stage prompt chaining for complex problems
    """
    # Stage 1: Analyze the question, extract key information
    analysis_prompt = f"""Analyze the following question and identify:
1. Key entities and their relationships
2. What type of information is needed
3. Potential sub-questions to answer

Question: {question}

Analysis:"""
    analysis = llm.complete(analysis_prompt)
    
    # Stage 2: Based on analysis, formulate an answer strategy
    strategy_prompt = f"""Based on the analysis, create a step-by-step plan to answer the question.
Analysis: {analysis}

Plan:"""
    plan = llm.complete(strategy_prompt)
    
    # Stage 3: Execute the plan, gather information
    execution_prompt = f"""Execute the following plan to answer the question.
Plan: {plan}
Question: {question}

Evidence gathered:"""
    evidence = llm.complete(execution_prompt)
    
    # Stage 4: Synthesize evidence, generate final answer
    final_prompt = f"""Based on all the evidence, provide a comprehensive answer.
Question: {question}
Evidence: {evidence}

Final Answer:"""
    final_answer = llm.complete(final_prompt)
    
    return {
        'question': question,
        'analysis': analysis,
        'plan': plan,
        'evidence': evidence,
        'final_answer': final_answer
    }

11.3 Meta-Prompting: Letting the Model Optimize Its Own Prompt

Meta-Prompting leverages the model's own capability to improve prompt quality:

def meta_prompt_optimizer(original_prompt: str, llm) -> str:
    """Let the model optimize its own prompt"""
    optimization_prompt = f"""You are an expert prompt engineer. Optimize the following prompt to get better results.
Consider: clarity, specificity, examples, constraints.

Original Prompt:
{original_prompt}

Optimized Prompt:"""
    return llm.complete(optimization_prompt)

Use Cases

• Automated A/B testing: generate multiple prompt variants and compare效果
• Domain adaptation: optimize a generic prompt for a specific domain
• Error recovery: automatically adjust the prompt based on failure cases

11.4 Combining ToT + Prompt Chaining

For hyper-complex problems, ToT and Prompt Chaining can be combined:

def hybrid_approach(question: str, llm) -> dict:
    """
    Combined approach: first decompose the question using Prompt Chaining,
    then use ToT search for each sub-question
    """
    # Step 1: Decompose the question
    decomposition = decompose_question(question, llm)
    
    results = {}
    for sub_question in decomposition:
        # Step 2: Use ToT for each sub-question
        totp_result = run_tot_search(sub_question, llm, max_depth=3)
        results[sub_question] = totp_result
    
    # Step 3: Synthesize all sub-results
    synthesis_prompt = f"""Synthesize the following sub-results into a comprehensive answer.
Question: {question}
Sub-results: {results}

Synthesis:"""
    final_answer = llm.complete(synthesis_prompt)
    
    return {'final_answer': final_answer, 'sub_results': results}

11.5 Practical Advice

1. Try simple methods first: Prompt Chaining is通常 easier to implement and maintain than ToT
2. Evaluate cost-benefit: ToT search cost grows exponentially with depth and branching factor
3. Hybrid strategy: use CoT for simple sub-questions, ToT for complex ones
4. Monitor quality: periodically check the diversity and quality of generated thoughts

Chapter Summary

• ToT: tree-shaped search structure, supports backtracking and multi-path exploration
• Prompt Chaining: stepwise processing, each step focuses on a single sub-task
• Meta-Prompting: use the model's capability to optimize the prompt itself
• Combined strategy: choose the right method based on problem complexity

🧪 随堂测验

点击你认为正确的选项。答错时会展示正确答案与原因解析。

1. What is the main advantage of Tree of Thoughts compared to Chain-of-Thought?

2. What is the core idea of Prompt Chaining?

3. What is the primary use of Meta-Prompting?

4. Which search algorithm is typically NOT included in ToT?

🛠️ Hands-on Practice

1. Implement a simple ToT searcher to solve puzzles requiring multi-step planning (e.g. Sudoku, sliding puzzle).
2. Design a Prompt Chaining system that decomposes "write a technical blog post" into: outline → introduction → body → conclusion.
3. Implement a Meta-Prompting optimizer that automatically improves user-provided prompt templates.

Next chapter: ReAct: Reasoning and Acting in Concert