Gen AI

Tree of Thoughts

Instead of writing a single chain of logic, the LLM explores multiple branching possibilities, evaluates each branch to see if it's a dead end, and backtracks if necessary to find the optimal solution.

Why Does This Exist?

Chain of Thought (CoT) forces an LLM to think linearly. Step 1 $\rightarrow$ Step 2 $\rightarrow$ Step 3 $\rightarrow$ Answer.

But what if the problem requires planning, foresight, or trial-and-error? What if Step 2 turns out to be a dead end? If a human is solving a crossword puzzle, they don't write down the first word that comes to mind in pen and just keep going. They write a word, look at the intersecting letters, realize it doesn't fit, erase it (backtracking), and try a different word (branching).

Linear CoT cannot backtrack. Once it generates a bad Step 2, it is forced to continue hallucinating until the bitter end.

Tree of Thoughts (ToT) is a framework that forces the LLM to behave like a chess player. It generates multiple possible "next moves," evaluates which move looks the most promising, explores that branch, and if it hits a dead end, it abandons the branch and goes back to explore a different one.

Think of It Like This

Solving a maze

Chain of Thought (Linear): You enter the maze. You take the first left. You hit a dead end. Because you cannot go backwards, you just smash your head against the wall and declare you are finished.

Self-Consistency (Parallel): You send 5 clones into the maze. They all pick a random path and run blindly until they hit a wall. Hopefully, one of the 5 clones randomly makes it to the end.

Tree of Thoughts (Branching): You enter the maze. You reach a fork. You look down the left path, see a wall 10 feet away, and evaluate it as "Bad." You look down the right path, see it continues, and evaluate it as "Good." You walk down the right path. If you later hit a dead end, you retrace your steps back to the fork and try a different way.

How It Actually Works

Tree of Thoughts is not a single prompt you type into ChatGPT; it is a Python script that orchestrates multiple LLM calls using classic computer science search algorithms (like Breadth-First Search or Depth-First Search).

A ToT implementation requires four components:

1. Thought Generator

Given a state, how does the LLM generate the next possible steps? If the task is writing a novel, the current state is "Chapter 1." The Thought Generator asks the LLM: "Give me 3 different ideas for what could happen in Chapter 2."

2. State Evaluator

Once the ideas are generated, the LLM is asked to evaluate them. Prompt: "Look at these 3 ideas for Chapter 2. Rate each one on a scale of 1-10 based on narrative consistency." This evaluation acts as the heuristic for the search algorithm.

3. Search Algorithm

The Python code looks at the evaluations. It picks the idea that scored a 9/10 and moves forward. It ignores the idea that scored a 2/10 (pruning the tree).

4. Backtracking

If the chosen path later results in a logical contradiction (e.g., in Chapter 4, the LLM realizes the plot is broken), the code backtracks to the Chapter 2 ideas and explores the path that originally scored a 7/10.

Show Me the Code

Implementing a full BFS/DFS search tree in Python is lengthy. This is a conceptual snippet showing the core LLM calls inside the ToT loop.

1import openai2
3def generate_thoughts(current_state):4    # Branching: Ask for 3 possible next steps5    prompt = f"Given the state: '{current_state}', brainstorm 3 distinct next steps."6    # ... call LLM ...7    return ["Step A", "Step B", "Step C"]8
9def evaluate_thoughts(current_state, thoughts):10    # Evaluating: Ask the LLM to grade its own ideas11    grades = {}12    for thought in thoughts:13        prompt = f"Given '{current_state}', is '{thought}' a good next step? Rate 1-10."14        # ... call LLM ...15        grades[thought] = int(llm_rating) # e.g., 816    return grades17
18def tree_of_thoughts_loop(initial_state, max_depth=3):19    current_state = initial_state20    21    for depth in range(max_depth):22        # 1. Generate Branches23        thoughts = generate_thoughts(current_state)24        25        # 2. Evaluate Branches26        grades = evaluate_thoughts(current_state, thoughts)27        28        # 3. Prune and Select Best29        best_thought = max(grades, key=grades.get)30        best_score = grades[best_thought]31        32        if best_score < 5:33            print("Dead end reached! Backtracking required.")34            # In a real implementation, you would pop the state stack here35            return False36            37        print(f"Depth {depth}: Chose path -> {best_thought}")38        current_state += f" -> {best_thought}"39        40    return current_state

Watch Out For

Astronomical Cost

Tree of Thoughts is the most expensive prompting technique ever invented. Generating 3 thoughts, evaluating all 3 thoughts, and then doing that again for 5 sequential steps requires 15 to 20 separate LLM calls just to answer a single user question. It is entirely unsuited for real-time applications. It should only be used for autonomous agents doing long-term background tasks (like writing code repositories or solving complex math theorems overnight).

The Quick Version

Chain of Thought forces the LLM to think linearly, which fails if the problem requires trial-and-error or backtracking.
Tree of Thoughts (ToT) combines LLMs with classic search algorithms (like DFS/BFS).
The LLM generates multiple possible "next steps" (branching).
The LLM then evaluates those steps to decide which one is most promising.
The system explores the best branch, but can backtrack to an earlier branch if it hits a dead end.