How to Implement Tree of Thoughts (ToT) Prompting

Introduction to Tree of Thoughts (ToT) Prompting

Tree of Thoughts (ToT) is an advanced prompting framework designed to enhance the reasoning capabilities of Large Language Models (LLMs). While traditional Chain of Thought (CoT) prompting encourages a model to think linearly—generating a single sequence of thoughts to reach a conclusion—ToT allows the model to explore multiple different reasoning paths simultaneously. It evaluates the progress of each path and can backtrack or look ahead, much like a human solving a complex puzzle.

This technique matters because many real-world problems are not strictly linear. Tasks that require strategic planning, mathematical problem-solving, or creative generation often involve dead ends. By framing the reasoning process as a search problem over a tree structure, ToT significantly improves an LLM's ability to solve complex tasks that require exploration, trial and error, and self-evaluation.

How Tree of Thoughts Works

Implementing ToT requires breaking down the problem-solving process into four distinct components. Understanding these components is crucial before writing any code.

1. Thought Decomposition

The problem must be broken down into intermediate "thought" steps. Depending on the task, a thought could be a few words (for creative writing), a sentence (for crosswords), or a mathematical equation (for math problems). The granularity depends on what makes sense for the LLM to evaluate.

2. Thought Generation

At any given state in the tree, the LLM must generate multiple potential next thoughts. Instead of asking for one continuation, you prompt the model to provide several distinct, plausible next steps. This can be done by sampling multiple times with high temperature or by prompting the model to output a list of ideas in a single call.

3. State Evaluation

Once multiple thoughts are generated, the LLM acts as an evaluator to assess the quality of each state. The model can be prompted to either assign a numerical score (e.g., 1 to 10) or classify the state as "sure", "maybe", or "impossible". This heuristic helps the search algorithm decide which paths are worth exploring.

4. Search Algorithm

ToT utilizes classic search algorithms to traverse the tree of thoughts. The two most common are Breadth-First Search (BFS) and Depth-First Search (DFS). BFS keeps track of a set of the most promising states at each step, while DFS explores one path deeply, backtracking if the evaluator determines the current path is a dead end.

Implementing ToT in Python

To implement ToT, we will create a Python script that utilizes Breadth-First Search (BFS). We will use the OpenAI API to handle thought generation and evaluation. The script will explore multiple paths, evaluate them, and keep only the most promising ones until a solution is reached.

Setting Up the Environment

First, ensure you have the OpenAI Python package installed. You will also need an API key.

pip install openai

Generating and Evaluating Thoughts

Next, we will write the functions to generate multiple thoughts for a given state and evaluate the quality of a state. We will use a generic LLM wrapper to keep the logic clear.

import openai
import json

# Set your OpenAI API key here
openai.api_key = "YOUR_API_KEY"

def call_llm(prompt, temperature=0.7):
    """Helper function to call the LLM."""
    response = openai.ChatCompletion.create(
        model="gpt-4",
        messages=[{"role": "user", "content": prompt}],
        temperature=temperature
    )
    return response.choices[0].message.content.strip()

def generate_thoughts(problem, current_state, num_thoughts=3):
    """Generates multiple next steps based on the current state."""
    prompt = (
        f"You are solving this problem: {problem}\n"
        f"Current progress: {current_state}\n"
        f"Generate {num_thoughts} distinct next steps to continue solving the problem. "
        f"Format as a JSON array of strings."
    )
    response = call_llm(prompt, temperature=0.8)
    try:
        # Parse the JSON array of thoughts
        thoughts = json.loads(response)
        return thoughts
    except json.JSONDecodeError:
        return []

def evaluate_state(problem, state):
    """Evaluates the likelihood of the current state leading to a solution."""
    prompt = (
        f"You are evaluating progress on this problem: {problem}\n"
        f"Current proposed state: {state}\n"
        f"On a scale of 1 to 10, how likely is this state to lead to the correct final solution? "
        f"Output ONLY the integer score."
    )
    response = call_llm(prompt, temperature=0.2)
    try:
        score = int(response)
        return score
    except ValueError:
        return 0

Implementing the BFS Search

Now we combine the generation and evaluation functions into a Breadth-First Search algorithm. At each depth level, we will generate thoughts for all active states, evaluate the new states, and keep only the top breadth states for the next level.

def tree_of_thoughts_bfs(problem, max_depth=3, breadth=3):
    """Executes a Tree of Thoughts search using BFS."""
    # Start with an empty initial state
    current_states = [""]
    
    for depth in range(max_depth):
        print(f"Exploring depth {depth + 1}...")
        all_next_states = []
        
        for state in current_states:
            # Generate multiple thoughts for the current state
            thoughts = generate_thoughts(problem, state, num_thoughts=breadth)
            
            for thought in thoughts:
                # Append the new thought to the current state
                new_state = f"{state} {thought}".strip()
                
                # Evaluate the new state
                score = evaluate_state(problem, new_state)
                all_next_states.append((score, new_state))
        
        if not all_next_states:
            print("No valid thoughts generated. Stopping early.")
            break
            
        # Sort states by score in descending order
        all_next_states.sort(reverse=True, key=lambda x: x[0])
        
        # Keep only the top 'breadth' states for the next iteration
        current_states = [s[1] for s in all_next_states[:breadth]]
        
    # Return the highest scoring state at the final depth
    return current_states[0] if current_states else "No solution found."

# Example Usage
if __name__ == "__main__":
    problem = "Plan a 3-day itinerary for a trip to Paris for a history buff who loves food."
    best_plan = tree_of_thoughts_bfs(problem, max_depth=3, breadth=2)
    
    print("\n--- Best Plan Found ---")
    print(best_plan)

Best Practices for ToT Prompting

While ToT is powerful, it is also resource-intensive. Following best practices will help you get the most out of this technique without unnecessarily inflating costs or latency.

• Define Clear Evaluation Criteria: The success of ToT relies heavily on the LLM's ability to evaluate its own progress. Provide few-shot examples in your evaluation prompt to show the model exactly what constitutes a "good" state versus a "bad" state.
• Control Depth and Breadth: Every node in the tree requires multiple API calls. A depth of 3 and breadth of 3 results in up to 27 thought generations and 27 evaluations. Start with small values (e.g., depth=2, breadth=2) and scale up only if the problem requires it.
• Use Caching: If you are running the same problem multiple times or if the LLM generates identical thoughts, caching API responses can save significant time and money.
• Combine with Few-Shot Prompting: When generating thoughts, providing a few examples of high-quality reasoning steps can guide the model to generate more diverse and logical branches.
• Choose the Right Search Algorithm: Use BFS for problems where you want to explore multiple options broadly (like brainstorming or planning). Use DFS for problems with a large search space where you want to commit to a path and backtrack only upon failure (like solving a Sudoku puzzle).

Conclusion

Tree of Thoughts prompting represents a significant leap forward in how we interact with Large Language Models. By treating reasoning as a search problem rather than a linear generation task, developers can unlock the ability of LLMs to solve complex, multi-step problems that were previously out of reach. While implementing ToT requires more setup and computational resources than standard prompting, the resulting improvements in accuracy, strategic planning, and problem-solving make it an invaluable tool for advanced AI applications. By carefully managing your search depth, breadth, and evaluation prompts, you can build robust systems that truly mimic human-like problem-solving strategies.