Self-consistency and tree-of-thought

WHY does this exist?

Plain Chain-of-Thought (CoT) prompting asks the model to "think step by step" and produce ONE line of reasoning. Problem: a single chain is a greedy walk through a huge space of possible reasonings. One early mistake dooms the whole answer, and greedy decoding has no way to recover.

WHAT are the two methods?

Axis	Chain-of-Thought	Self-Consistency	Tree-of-Thought
Structure	1 linear chain	$N$ linear chains	branching tree
Combine by	—	majority vote	search + evaluation
Backtracking?	No	No	Yes
Cost	1×	$N$ ×	can be $\gg N$ ×

Figure — Self-consistency and tree-of-thought

HOW self-consistency works — from first principles

Goal. We want the most probable answer $a$ , marginalizing over the hidden reasoning path $r$ :

p(a \mid \text{prompt}) \;=\; \sum_{r} p(a, r \mid \text{prompt}) \;=\; \sum_{r} p(a \mid r)\,p(r \mid \text{prompt}).

Monte Carlo estimate. We can't enumerate all $r$ , so we sample $r^{(i)}\sim p(r\mid\text{prompt})$ for $i=1..N$ (that is exactly what temperature sampling does). Each chain deterministically yields an answer $a^{(i)}$ . Then:

\hat p(a) \;=\; \frac{1}{N}\sum_{i=1}^{N}\mathbf{1}\!\left[a^{(i)} = a\right].

Why the mode beats one sample (the math)

Suppose each independent chain is correct with probability $p>\tfrac12$ and each specific wrong answer is less likely. By the majority-vote (Condorcet) logic, the probability the majority is correct climbs toward 1 as $N$ grows:

P(\text{majority correct}) \;=\; \sum_{k=\lceil (N+1)/2\rceil}^{N} \binom{N}{k} p^{k}(1-p)^{N-k}\;\xrightarrow[N\to\infty]{}\;1 \quad (p>\tfrac12).

HOW tree-of-thought works — from first principles

ToT is CoT reframed as state-space search. Define:

State $s$ = the prompt + partial reasoning so far.
Thought generator $G(s)$ = LLM proposes $k$ candidate next thoughts.
State evaluator $V(s)$ = LLM (or heuristic) scores "how promising is this state?" (e.g. "sure / maybe / impossible", or a numeric value).
Search = BFS keeps the top- $b$ states per depth (beam); DFS goes deep and backtracks when $V$ says a branch is dead.

Cost. A tree of depth $d$ , branching $k$ , kept width $b$ costs roughly

\text{calls} \;\approx\; d \cdot b \cdot k \;(\text{generate}) \;+\; d\cdot b\cdot k\;(\text{evaluate}),

which is far more than SC's $N$ calls. Trade-off: ToT buys harder-problem capability; SC buys cheap accuracy gains.

Common mistakes (steel-manned)

The 80/20 (what actually earns marks)

SC = sample many CoT chains + majority vote, needs temperature $>0$ .
It's a Monte-Carlo estimate of the answer marginal $p(a\mid\text{prompt})=\sum_r p(a\mid r)p(r\mid\text{prompt})$ .
ToT = reasoning as a searchable tree with generate + evaluate + prune + backtrack.
SC cost $N\times$ ; ToT cost $\gg N\times$ but solves harder search problems.

Flashcards

What decoding trick does self-consistency add on top of chain-of-thought?

Sample N independent CoT chains at temperature > 0, then take the majority-vote final answer.

Why must temperature be > 0 for self-consistency?

At temperature 0 all chains are identical, so the vote gives no diversity and no benefit.

Self-consistency is a Monte-Carlo estimate of what quantity?

The answer marginal

p(a\mid\text{prompt})=\sum_r p(a\mid r)p(r\mid\text{prompt})

; the mode of the samples estimates its argmax.

Why do correct answers win the vote?

Correct reasoning paths converge on the same answer while wrong paths make idiosyncratic, scattered mistakes.

What are the three functional components of Tree-of-Thought?

A thought generator G(s), a state evaluator V(s), and a search algorithm (BFS/DFS/beam) with pruning and backtracking.

Key capability ToT has that CoT and SC lack?

Backtracking — it can abandon dead-end partial reasoning and try another branch.

Cost comparison CoT vs SC vs ToT?

CoT 1×, SC N×, ToT roughly d·b·k generate + evaluate calls (≫ N).

If single-chain accuracy p>0.5, what happens to majority accuracy as N grows?

It rises toward 1 (Condorcet/majority-vote theorem).

Recall Feynman: explain to a 12-year-old

Imagine a hard homework problem. If you ask one friend, they might slip up. So you ask forty friends who each solve it their own way, then you go with the answer most of them gave — the correct answer usually shows up again and again, while wrong answers are all different, so it loses. That's self-consistency. Tree-of-thought is like solving a maze: at each fork you try a few directions, quickly check "is this leading somewhere good?", and if a path is a dead end you walk back and try another. The computer branches, checks, and backtracks instead of blindly walking straight ahead.

Connections

Chain-of-Thought Prompting — the base technique both methods extend.
Monte Carlo Estimation — SC is MC marginalization over reasoning paths.
Beam Search and BFS/DFS — the search backbone of ToT.
Ensemble Methods and Majority Voting — statistical justification for the vote.
Temperature and Sampling in LLMs — why diversity requires temp > 0.
Retrieval-Augmented Generation (RAG) — can supply verified facts to each branch/chain.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab hum LLM se "step by step socho" (chain-of-thought) bolte hain, toh model ek hi reasoning ka rasta pakadta hai. Problem yeh hai ki agar shuru mein hi ek chhoti galti ho gayi, toh pura answer galat. Isliye self-consistency ka idea aaya: ek hi chain par bharosa mat karo, balki temperature badha ke (yaani thoda randomness allow kar ke) N alag-alag chains sample karo, aur jo final answer sabse zyada baar aaya, wahi maan lo — bilkul majority voting jaise. Intuition simple hai: sahi answer par bahut saare raaste milte hain, lekin har galat answer apni-apni alag galti se aata hai, toh galat answers bikhar jaate hain aur sahi answer vote jeet jaata hai.

Maths side se, self-consistency actually $p(a\mid\text{prompt})=\sum_r p(a\mid r)p(r\mid\text{prompt})$ ka Monte-Carlo estimate hai — hum reasoning $r$ ko nuisance maan ke uspe sum (marginalize) kar rahe hain, aur sampling se uska mode nikaal rahe hain. Ek important baat: temperature zero mat rakhna, warna saari chains same aa jayengi aur voting bekaar. 0.5–0.7 theek rehta hai.

Tree-of-thought thoda advanced hai. Yahan reasoning ko ek tree ki tarah socho: har node ek partial thought hai. Model har node par kuch candidate next steps banata hai (generate), phir ek evaluator score karta hai ki yeh state achhi hai ya dead-end (evaluate), bekaar branches ko prune kar deta hai, aur zaroorat padne par backtrack karke doosra raasta try karta hai. Yeh puzzles jaise Game-of-24 ya planning problems mein bahut kaam aata hai jahan galat raaste chhodne padte hain — jo simple chain kabhi nahi kar sakti.

Yaad rakho trade-off: self-consistency sasta hai (bas $N$ times run) aur accuracy free mein badha deta hai; tree-of-thought mehenga hai (bahut zyada LLM calls) lekin sach mein mushkil search problems solve karta hai. Exam ke liye 80/20: SC = sample + majority vote (temp>0), ToT = tree + evaluate + prune + backtrack.

WHY does this exist?

WHAT are the two methods?

HOW self-consistency works — from first principles

Why the mode beats one sample (the math)

HOW tree-of-thought works — from first principles

Common mistakes (steel-manned)

The 80/20 (what actually earns marks)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Alignment, Prompting & RAG

Connections