Tree of Thoughts — Module 13.1

How This Lesson Fits the Module & Volume

Chain-of-thought follows one linear path of reasoning. Tree-of-thoughts (ToT) explores multiple candidate “thoughts” at each step—branching, evaluating, and pruning—more like search than a single monologue.

ToT is heavier than CoT and usually reserved for planning, puzzles, and design tasks where early mistakes are costly. It pairs conceptually with self-consistency (many paths) and reflection (critique and revise), and can be orchestrated via prompt chaining.

Learning Objectives

By the end of this lesson, students should be able to:

Define tree-of-thoughts and contrast it with linear CoT.
Describe the expand → evaluate → select (or prune) loop.
Sketch a ToT prompt that proposes multiple next steps and scores them.
Identify problem types suited to ToT versus plain CoT.
Estimate cost/latency implications of branching search.
Design a minimal ToT controller (LLM-as-generator + LLM-as-judge).

Definition

Tree-of-thoughts is a prompting (and often orchestration) strategy that maintains a tree of intermediate reasoning states: at each depth, the model proposes several candidate thoughts, evaluates them, and expands only the most promising branches until a solution is found or the budget is exhausted.

CoT Line vs ToT Tree

Aspect	Chain-of-Thought	Tree-of-Thoughts
Structure	Single path	Branching tree
Backtracking	Rare / informal	Explicit prune & expand
Cost	One generation (mostly)	Many generations
Best for	Straightforward multi-step	Search / planning / puzzles

The ToT Loop

1. Expand

Propose k next thoughts

2. Evaluate

Score promise / validity

3. Select

Keep top-b branches

4. Stop

Solution or budget hit

Expansion Prompt (Generator)

Problem: {{PUZZLE}}
Current partial plan:
{{STATE}}

Propose 3 distinct next steps that could advance the plan.
For each step, write:
- thought: one concrete action or intermediate claim
- why: one sentence rationale
Do not solve the whole problem yet.

Evaluation Prompt (Judge)

Problem: {{PUZZLE}}
Candidate next thoughts:
{{CANDIDATES}}

Score each candidate from 1–5 for:
(a) validity given constraints
(b) progress toward a solution
Return JSON: [{"id":1,"score":...,"note":"..."}, ...]

When to Use ToT

Good fits

Game / puzzle search.
Multi-option planning.
Creative ideation with pruning.

Usually overkill

Classification and extraction.
Short factual Q&A with retrieval.
Strict latency SLAs.

Cheaper cousins

Single CoT path.
Self-consistency voting.
One reflection pass.

Strengths and Tradeoffs

Strengths

Explores alternatives before committing.
Can recover from early local mistakes.
Makes search policy explicit and tunable.

Tradeoffs

High token and orchestration cost.
Judge model can mis-score branches.
Engineering complexity vs plain prompts.

Common Misconception

“ToT is just saying ‘consider multiple options’ in one prompt.” True ToT maintains state across steps with deliberate branching and pruning—often multiple API calls. A single paragraph that lists options is closer to shallow CoT than to tree search.

Knowledge Check

Short Answer: How does ToT differ structurally from CoT? Answer: ToT branches into multiple intermediate thoughts; CoT is one linear path.
True/False: ToT usually costs more tokens than a single CoT pass. Answer: True.
Multiple Choice: The ToT loop includes: (a) expand/evaluate/select, (b) only dropout, (c) only backprop. Answer: (a).
Short Answer: Name a task family suited to ToT. Answer: Planning, puzzles, multi-option design/search (any).
True/False: Listing three options once in one reply is full ToT. Answer: False—ToT tracks a tree across steps.
Multiple Choice: The judge step primarily: (a) scores candidates, (b) trains LoRA, (c) builds CNNs. Answer: (a).
Short Answer: Why might ToT fail even with branching? Answer: Bad evaluations / prune correct branches / budget exhausted.
True/False: Classification at scale is a classic ToT use case. Answer: False—usually overkill.
Multiple Choice: A cheaper alternative for many paths without a tree controller: (a) self-consistency, (b) full FT only, (c) max-pool. Answer: (a).
Short Answer: What does “prune” mean in ToT? Answer: Discard low-scoring branches so they are not expanded further.

Key Takeaways

ToT searches a tree of thoughts with expand, evaluate, and select.
Use it for hard planning/search; keep CoT for ordinary multi-step tasks.
Budget and judge quality dominate ToT reliability.
Next: Self Consistency.

Trainer’s Guide

Hands-on idea: Solve a small puzzle with CoT once, then with k=3 breadth for two depths; compare cost and success.

Discussion prompt: Where should ToT live—inside one mega-prompt or in an external controller that chains calls?

Recap: Tree-of-thoughts turns reasoning into explicit search over branches. Continue with Self Consistency.