CoT vs DFS — Concept Comparison

TL;DR

What is CoT?

CoT is a linear reasoning strategy. Given a problem, the model writes intermediate steps one after another until it reaches a conclusion. There is only one path — no choices, no dead-ends, no going back.

Problem
  ↓
Step 1
  ↓
Step 2
  ↓
Step 3
  ↓
Answer

Key properties:

• Flat, sequential — like writing out a math solution on paper
• No concept of "other possible paths"
• If reasoning goes wrong, the entire chain needs to be redone
• Zero overhead: no stack, no visited set, no branching logic

Example — "Who stole the cake?"

Clue ①: Crumbs near Alice's room
Clue ②: Bob was in the kitchen
Clue ③: Alice has an alibi (was outside)
Inference: Alice ruled out → Bob is suspect
Check ①: Bob has motive (loves cake)
Check ②: Bob had opportunity (was there)
∴ Conclusion: Bob stole the cake

8 steps, 0 branches, 0 backtracks.

What is DFS?

DFS is a tree search algorithm. Starting from a root state, it picks one child, goes as deep as possible, hits a dead-end or goal, and backtracks to try another branch. It maintains an explicit stack of the current path.

Root
├── Branch A
│   ├── A1  ← visit → dead-end → backtrack
│   └── A2  ← visit → dead-end → backtrack
└── Branch B
    ├── B1  ← visit
    │   └── B1a  ← GOAL ✓
    └── B2  (never reached)

Key properties:

• Explores one branch fully before trying siblings
• Backtracking is a core operation, not an error
• Requires a stack: [Root, B, B1] at every point
• Dead-ends are expected — they prune the search space

Example — Same detective problem as a search tree:

Start
├── Alice?
│   ├── Alibi check → YES → DEAD (has alibi) ✕
│   └── Motive? → DEAD (motive unclear) ✕
├── Bob?            ← backtrack to here
│   ├── Motive? → YES ✓
│   └── Opportunity? → YES ✓ → GOAL ★
└── Carol?          (not reached)

21 actions, 4 dead-ends, multiple backtracks — same answer.

Why They Look Similar (and Why They're Not)

The confusion usually comes from this: both CoT and DFS can produce a single long chain of reasoning steps. But the similarity is superficial.

CoT produces one chain because there is only one chain.
DFS produces one chain at a time because it goes deep first — but it can and will explore others.

A useful way to think about it:

CoT is a pen writing a sentence.
DFS is a pen drawing a tree, lifting off the paper and backtracking when it hits a wall.

When Does CoT Become More Like DFS?

When LLMs use Tree-of-Thought (ToT) or Self-Consistency, they generate multiple CoT chains and compare them. At that point, the outer loop is a form of search:

Tree-of-Thought ≈ multiple CoT chains + a search strategy (BFS or DFS)
Self-Consistency ≈ multiple CoT chains + majority vote

So CoT itself is not a search algorithm, but it can be used as the expansion operator inside one.

Applied to the River Crossing Problem

BFS and DFS discovered the solution. CoT justifies it after the fact. They are complementary, not competing.

Summary

Use CoT when: you have a well-defined problem that can be solved by chaining deductions — math, logic, code explanation.

Use DFS (or BFS, A*) when: the answer is hidden somewhere in a space of states, and you need to explore and backtrack to find it.

The key question to distinguish them:

"Is there a state space to search, or just a chain of reasoning to write down?"

If there's a state space → search algorithm (DFS/BFS/A*).
If it's pure deduction → CoT.