AI Prompt Engineering · Lesson

Tree-of-Thought Exploration

Branching and evaluating thoughts.

Tree-of-Thought Exploration is a free AI Prompt Engineering lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the AI Prompt Engineering learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

From Chains to Trees

Tree-of-Thought (ToT, Yao et al., 2023) generalizes chain-of-thought from a single linear path to a search tree of partial solutions. Each node is a coherent intermediate thought; branches explore alternative continuations.

This lets the model deliberate: generate multiple next-steps, evaluate them, keep the promising ones, and backtrack from dead ends, mimicking systematic problem solving rather than committing to the first idea.

class ThoughtNode:
    def __init__(self, state, parent=None):
        self.state = state      # partial solution / reasoning so far
        self.parent = parent
        self.children = []
        self.value = None       # evaluator score

The Four ToT Components

A ToT system has four design choices: thought decomposition (what is a step), the thought generator (how to propose next steps), the state evaluator (how to score partial solutions), and the search algorithm (BFS, DFS, or best-first).

Each is a separate prompt or policy. Designing ToT means specifying all four for your task.

tot = {
    'decompose': step_definition,   # e.g. one equation, one move
    'generate':  propose_thoughts,  # sampling or proposal prompt
    'evaluate':  score_state,        # value/vote prompt
    'search':    bfs_with_beam,      # BFS | DFS | best-first
}

Generating Candidate Thoughts

Two generation strategies: sample several independent thoughts at moderate temperature (good when the space is rich), or propose a set of distinct next steps in one prompt (good when you want explicitly different options).

Generate a small branching factor (often 3 to 5); too many candidates explode the search and cost.

def propose_thoughts(state, k=4):
    prompt = (
        'Given the partial solution below, propose ' + str(k) +
        ' DISTINCT possible next steps.\n' + state
    )
    return parse_list(llm(prompt, temperature=0.7))

Evaluating States

The state evaluator is what makes ToT more than random sampling. It scores how promising a partial solution is, either by a value prompt (rate this state 1 to 10 toward solving the problem) or by a vote prompt (which of these states is most promising).

Voting across candidates is often more robust than absolute scoring because relative judgments are easier for the model.

def score_state(state):
    prompt = (
        'Rate how likely this partial solution leads to a correct '
        'final answer. Reply sure / likely / impossible.\n' + state
    )
    label = llm(prompt, temperature=0).strip().lower()
    return {'sure': 1.0, 'likely': 0.5, 'impossible': 0.0}.get(label, 0.3)

BFS With Beam Search

Breadth-first ToT expands all frontier nodes one level at a time, then keeps only the top-b by evaluator score (a beam). This bounds the explosion while exploring multiple lines in parallel.

Beam width b trades breadth of exploration against cost; a width of 5 with depth 3 is a common starting point for structured puzzles.

def bfs_with_beam(root, depth, branch, beam):
    frontier = [root]
    for _ in range(depth):
        nxt = []
        for node in frontier:
            for t in propose_thoughts(node.state, branch):
                child = ThoughtNode(node.state + '\n' + t, node)
                child.value = score_state(child.state)
                nxt.append(child)
        frontier = sorted(nxt, key=lambda n: -n.value)[:beam]
    return max(frontier, key=lambda n: n.value)

DFS With Backtracking

Depth-first ToT dives down the most promising branch and backtracks when the evaluator deems a state hopeless. This suits problems with a clear notion of an infeasible partial state, like constraint puzzles.

Pruning impossible branches early is the main efficiency win, avoiding wasted expansion of doomed subtrees.

def dfs(node, depth, branch, prune=0.2):
    if depth == 0 or is_solution(node.state):
        return node
    for t in propose_thoughts(node.state, branch):
        child = ThoughtNode(node.state + '\n' + t, node)
        child.value = score_state(child.state)
        if child.value < prune:
            continue                      # backtrack: prune dead end
        res = dfs(child, depth - 1, branch, prune)
        if res and is_solution(res.state):
            return res
    return None

ToT vs Self-Consistency

Self-consistency samples independent complete chains and votes. ToT actively steers exploration with intermediate evaluation and backtracking, investing compute where it is promising.

ToT shines on problems requiring planning, search, or where early mistakes are fatal (Game of 24, crosswords, planning). For tasks with cheap diverse chains and a discrete answer, self-consistency is simpler and often sufficient.

# Rule of thumb
# - reachable by diverse single passes  -> self-consistency
# - needs lookahead / pruning / backtrack -> tree-of-thought
# ToT cost ~ branch * depth * beam * (gen + eval) LLM calls

Cost Explosion and Budgets

ToT is expensive: each node spawns generation and evaluation calls. Total cost scales roughly as branch x depth x beam, plus evaluator calls. Without a hard budget it can balloon.

Cap total LLM calls, use best-first search to spend budget on the highest-value frontier, and fall back to the best partial solution if the budget is exhausted.

import heapq

def best_first(root, max_calls):
    heap = [(-root.value, root)]
    best, calls = root, 0
    while heap and calls < max_calls:
        _, node = heapq.heappop(heap)
        for t in propose_thoughts(node.state, 3):
            calls += 1
            child = ThoughtNode(node.state + '\n' + t, node)
            child.value = score_state(child.state); calls += 1
            if child.value > best.value:
                best = child
            heapq.heappush(heap, (-child.value, child))
    return best

Evaluator Reliability

ToT is only as good as its evaluator. A miscalibrated evaluator prunes correct branches or chases dead ends. Improve it with voting (multiple evaluations per state), few-shot exemplars of good/bad states, or an external verifier (a unit test, a solver, a checker).

Where an objective check exists (does the equation hold, does the code pass), prefer it over an LLM judgment.

def robust_eval(state, votes=3):
    scores = [score_state(state) for _ in range(votes)]
    return sum(scores) / votes        # average to reduce judge noise
# Even better: replace with a deterministic verifier when available

Practical Applicability

ToT pays off on a narrow but valuable class of problems: multi-step planning, combinatorial puzzles, and tasks where verifying a step is cheaper than solving the whole. For most everyday prompting, ToT is overkill.

On reasoning-native models with strong built-in search, an explicit ToT scaffold often adds cost without much gain; benchmark before adopting it.

def choose_strategy(task):
    if task.requires_search and task.step_verifiable:
        return 'tree-of-thought'
    if task.discrete_answer:
        return 'self-consistency'
    return 'single chain-of-thought'

A Minimal ToT Solver

End to end: define a step, propose a small branch of thoughts, evaluate each (with voting or a verifier), search via BFS-beam or DFS-backtrack under a call budget, and return the best terminal state.

Instrument node counts and evaluator scores so you can tune branch, depth, and beam empirically per task.

def solve(problem, branch=4, depth=3, beam=5, budget=200):
    root = ThoughtNode(problem)
    root.value = score_state(root.state)
    node = bfs_with_beam(root, depth, branch, beam)
    return extract_solution(node.state)

Quick Check

Pick the right deliberation strategy.

Recap

Key takeaways:

ToT generalizes CoT into a search tree with thought generation, state evaluation, and a search algorithm.
Use BFS with a beam or DFS with backtracking; keep branching factor small to control explosion.
The state evaluator is the crux; harden it with voting or an external verifier.
Cost scales as branch x depth x beam, so enforce a call budget, often via best-first search.
Reserve ToT for planning/combinatorial, step-verifiable problems; it is overkill for everyday prompting.

Frequently asked questions

Is the “Tree-of-Thought Exploration” lesson free?

Yes — the full text of “Tree-of-Thought Exploration” is free to read here on the web, and the AI Prompt Engineering course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the AI Prompt Engineering course, upgrade to CoddyKit PRO.

What will I learn in “Tree-of-Thought Exploration”?

Branching and evaluating thoughts. You practise AI Prompt Engineering with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start AI Prompt Engineering?

No prior experience is required. AI Prompt Engineering on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Tree-of-Thought Exploration” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this AI Prompt Engineering lesson?

Yes. Every AI Prompt Engineering lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to AI Prompt Engineering