Self-consistency and tree-of-thought: Worked examples

This page drills the two decoding ideas from Self-Consistency and tree-of-thought until no case can surprise you. Before we list situations, we must name the two numbers everything depends on — nothing below uses a symbol you haven't met.

The scenario matrix

Cell	Situation class	What breaks / what to watch	Example
A	$p > \frac{1}{2}$ , odd $N$ — the good regime	Majority accuracy rises toward 1	Ex 1
B	$p < \frac{1}{2}$ — the bad regime	Voting hurts you (accuracy falls)	Ex 2
C	$p = \frac{1}{2}$ exactly (degenerate)	Voting gives no improvement	Ex 3
D	Even $N$ → possible tie ( $p > \frac{1}{2}$ )	Tie-break rule needed	Ex 4
E	Temperature $= 0$ (zero diversity)	All chains identical → vote useless	Ex 5
F	More than two answer options (not just right/wrong)	Plurality, not majority, wins	Ex 6
G	Limiting behaviour $N \to \infty$	Accuracy → 1 (if $p > \frac{1}{2}$ ) or → 0 (if $p < \frac{1}{2}$ )	Ex 7
H	ToT cost accounting (word problem)	Count generate + evaluate calls	Ex 8
I	ToT prune-and-backtrack (exam twist)	Search beats greedy chain	Ex 9
J	Even $N$ and $p < \frac{1}{2}$ (B×D combined)	Ties plus error amplification	Ex 10

Every cell A–J is worked below.

Now look at the picture that summarises the whole topic in one glance:

Figure — Self-consistency and tree-of-thought

Cell A — good regime, odd $N$

Worked example Ex 1 ·

$p = 0.7$ , $N = 5$ Each chain is correct 70% of the time. You sample 5 chains and vote. What is the probability the majority is correct?

Forecast: guess now — will it be below 70%, near 80%, or above 90%?

Step 1 — Find the majority threshold. With $N = 5$ , a strict majority needs $k \geq 3$ correct chains. Why this step? "Majority of 5" means 3, 4, or 5 — we must know exactly which $k$ -values count before summing.

Step 2 — Write the three terms. $P_{maj} = (3 5) (0.7)^{3} (0.3)^{2} + (4 5) (0.7)^{4} (0.3)^{1} + (5 5) (0.7)^{5} (0.3)^{0}$ Why this step? Each term is one "exactly $k$ correct" scenario from the master formula.

Step 3 — Evaluate. $= 10 (0.343) (0.09) + 5 (0.2401) (0.3) + 1 (0.16807) = 0.3087 + 0.36015 + 0.16807 = 0.83692$ Why this step? Plug the numbers; keep terms separate so a slip is easy to spot.

Verify: $0.837 > 0.70$ ✓ — voting raised accuracy from 70% to ~83.7%, exactly the "mode beats one sample" claim. Sanity: probabilities lie in $[0, 1]$ , and each term is positive, so the sum can only push us above the single-chain value in the good regime.

Cell B — bad regime ( $p < \frac{1}{2}$ ): voting HURTS

Cell C — the exact tipping point $p = \frac{1}{2}$

Cell D — even $N$ and ties (good regime)

Worked example Ex 4 ·

$p = 0.6$ , $N = 4$ — what if the vote ties 2–2? With even $N$ , the counts can split evenly, so "majority" is undefined for a 2–2 split. We use the general three-bucket formula.

Forecast: how often does a clean 3+ correct vote happen?

Step 1 — Strict-win bucket $k \geq 3$ . $P_{win} = (3 4) (0.6)^{3} (0.4) + (0.6)^{4} = 4 (0.216) (0.4) + 0.1296 = 0.3456 + 0.1296 = 0.4752$ Why this step? This collects the outcomes where the correct answer is a strict majority (3 or 4 of the 4 chains) — the only outcomes that decide cleanly for the right answer.

Step 2 — Tie bucket $k = 2$ (the $N /2$ term). $P_{tie} = (2 4) (0.6)^{2} (0.4)^{2} = 6 (0.36) (0.16) = 0.3456$ Why this step? A 2–2 split is the "no decision" outcome; it must be handled by a tie-break rule (e.g. pick the answer of the highest-confidence chain, or draw one more sample).

Step 3 — Lose bucket $k \leq 1$ (recall the binomial terms explicitly). The $k = 0$ term is $(0 4) p^{0} (1 - p)^{4} = (0.4)^{4} = 0.0256$ ; the $k = 1$ term is $(1 4) p^{1} (1 - p)^{3} = 4 (0.6) (0.4)^{3} = 0.1536$ . $P_{lose} = 0.0256 + 0.1536 = 0.1792$ Why this step? We spell out each binomial term so the mass-check below has no unexplained pieces.

Verify: the three buckets are disjoint and exhaustive, so they must sum to 1: $P_{win} + P_{tie} + P_{lose} = 0.4752 + 0.3456 + 0.1792 = 1.0000 ✓$ With a fair coin tie-break, effective accuracy $= P_{win} + \frac{1}{2} P_{tie} = 0.4752 + 0.1728 = 0.6480 > 0.6$ ✓ — still a gain, but ties dilute it. Practical rule: prefer odd $N$ so $P_{tie} = 0$ and no tie-break is needed.

Cell E — temperature 0: zero diversity

Worked example Ex 5 · Temperature

$= 0$ , $N = 40$ A student runs self-consistency with 40 chains but at temperature 0. How many distinct votes do they effectively get?

Forecast: guess the "effective $N$ ".

Step 1 — What temperature 0 does. Temperature 0 = greedy decoding: at each step the model always takes the single most probable token. Given the same prompt, the output is deterministic. Why this step? Diversity in SC comes entirely from sampling randomness; kill the randomness and every chain is a carbon copy. (See Temperature and Sampling in LLMs.)

Step 2 — Count distinct chains. All 40 chains are byte-identical → they all give the same answer $a^{(1)}$ . Effective independent samples $= 1$ . Why this step? The vote only "learns" something when chains differ; identical chains contribute the same single vote 40 times over, so 40 copies carry exactly the information of 1 chain.

Verify: the Monte-Carlo estimate $\overset{p}{^} (a) = \frac{1}{N} \sum_{i} 1 [a^{(i)} = a]$ collapses to $1 [a = a^{(1)}]$ — a single point mass. No averaging happened, so accuracy stays at raw single-chain accuracy. Confirms the parent's mistake box: SC needs temperature $> 0$ .

Cell F — more than two answers (plurality)

Worked example Ex 6 · Multi-way answers — plurality vote

You sample $N = 7$ chains on a numeric problem and read off these final answers: ${24, 24, 24, 30, 18, 24, 30}$ Which answer does self-consistency return, and is it a majority or only a plurality?

Forecast: which number wins, and does it clear half the votes?

Step 1 — Tally the votes. $24$ appears 4 times, $30$ appears 2 times, $18$ appears 1 time. Why this step? SC's decision rule is $\overset{a}{^} = ar g max_{a} \sum_{i} 1 [a^{(i)} = a]$ — literally the mode of the answer counts. (This is majority/plurality voting.)

Step 2 — Pick the argmax. Max count is 4 → $\overset{a}{^} = 24$ . Why this step? The decision rule literally is "take the answer with the largest tally"; once the counts are in, selecting the maximum count is the whole of SC's output — no further reasoning is combined.

Step 3 — Majority or plurality? Half of 7 is 3.5; a majority needs $\geq 4$ . Here $24$ has exactly 4 → it is a majority here, but note that if it had only 3 it would still win as a plurality without being a majority. Why this step? With $> 2$ options the winner need not exceed 50%; SC returns the most frequent answer regardless. This is where SC generalizes beyond right/wrong.

Edge case — a tie for the top count. If two answers share the maximum tally (e.g. $24$ and $30$ each with 3 votes), $ar g max$ is not unique and SC has no built-in winner. Standard fixes: break the tie by summing the chains' confidence scores, by preferring the answer whose chains were shorter/simpler, or by drawing one extra chain to break the deadlock — exactly the even- $N$ tie problem of Cell D, now in the multi-answer setting.

Verify: counts sum to $4 + 2 + 1 = 7 = N$ ✓. The winning fraction $4/7 \approx 0.571 > 0.5$ , so both "majority" and "plurality" agree here.

Cell G — the limit $N \to \infty$

Worked example Ex 7 · Where does accuracy go as chains → ∞?

With $p = 0.55$ fixed, what is $lim_{N \to \infty} P_{maj}$ ? And with $p = 0.45$ ?

Forecast: two numbers — one for each $p$ .

Step 1 — Use the law of large numbers. The fraction of correct chains $\overset{p}{^}_{N} = \frac{1}{N} \sum_{i} 1 [chain i correct]$ converges to the true $p$ . The majority is correct exactly when $\overset{p}{^}_{N} > \frac{1}{2}$ . Why this step? SC is a Monte-Carlo estimator; its estimate concentrates on the truth as samples grow.

Step 2 — Read off the limit for each $p$ .

$p = 0.55 > 0.5$ : eventually $\overset{p}{^}_{N} > 0.5$ almost surely → $P_{maj} \to 1$ .
$p = 0.45 < 0.5$ : eventually $\overset{p}{^}_{N} < 0.5$ → majority is wrong → $P_{maj} \to 0$ .
(Boundary $p = 0.5$ : stuck at $0.5$ forever — the Cell C knife-edge.)

Step 3 — Sanity via finite growth. Compute $P_{maj}$ at $p = 0.55$ for growing odd $N$ : it should be increasing toward 1. $N = 3$ : $(2 3) (0.55)^{2} (0.45) + (0.55)^{3} = 3 (0.3025) (0.45) + 0.166375 = 0.408375 + 0.166375 = 0.574750$ . $N = 9$ : sum of the $k = 5..9$ terms $\approx 0.622317$ . Why this step? Watching the finite numbers climb ( $0.574750 \to 0.622317$ ) makes the "→ 1" limit concrete.

Verify: the two limits are $1$ and $0$ , and the finite $p = 0.55$ values increase with $N$ ( $0.622317 > 0.574750$ ) ✓. This is the sharp "phase transition" at $p = \frac{1}{2}$ — above it you win everything, below it you lose everything, in the limit.

Cell H — ToT cost accounting (word problem)

Worked example Ex 8 · Budgeting API calls for a tree

A Tree-of-Thought run has depth $d = 3$ , keeps beam width $b = 5$ states per level, and the generator proposes $k = 4$ candidate thoughts per kept state. Each generated state is scored by one evaluator call. Compare its call count to a self-consistency run with $N = 20$ chains.

Forecast: roughly how many total LLM calls does ToT make — tens? hundreds?

Step 1 — Generate calls. At each of $d$ levels, we expand $b$ states, each into $k$ candidates: $generate = d \cdot b \cdot k = 3 \cdot 5 \cdot 4 = 60.$ Why this step? This is the parent note's cost formula; every kept state at every depth spawns $k$ children.

Step 2 — Evaluate calls. Each generated candidate is scored once: $evaluate = d \cdot b \cdot k = 60.$ Why this step? Search must rank every candidate it just produced to decide which to keep or prune, so there is one evaluator call per generated state — the same $d \cdot b \cdot k$ count as generation.

Step 3 — Total. $total = 60 + 60 = 120 calls .$ Why this step? Generation and evaluation are separate LLM calls, so the run's budget is simply their sum — this is the number you actually pay for.

Verify: SC with $N = 20$ costs $20$ calls; ToT here costs $120$ — a $6 \times$ multiplier ( $120/20 = 6$ ), matching the "ToT $≫ N$ " claim. Units check: everything is counted in LLM calls, so adding generate + evaluate is dimensionally fine.

Cell I — prune-and-backtrack exam twist

Worked example Ex 9 · Why search beats a greedy chain (Game-of-24 style)

Numbers ${4, 9, 10, 13}$ , target 24. A greedy chain commits to the first operation $4 + 9 = 13$ and gets stuck. Show how ToT's evaluate-and-prune recovers, and count how many first-move branches survive one pruning pass.

Forecast: how many of the first-move states get pruned before we go deeper?

Step 1 — Generate first-move candidates (track the multiset carefully). Each first move removes two numbers and inserts their result. From ${4, 9, 10, 13}$ :

$4 + 9 = 13$ → remove $4, 9$ , insert $13$ → ${10, 13, 13}$ .
$13 - 9 = 4$ → remove $13, 9$ , insert $4$ → ${4, 4, 10}$ .
$10 - 4 = 6$ → remove $10, 4$ , insert $6$ → ${6, 9, 13}$ . Why this step? $G (s)$ branches instead of committing; getting the multiset update right (remove-two, insert-one) is essential — each state must have exactly $N - 1 = 3$ numbers.

Step 2 — Apply $V (s)$ to each state.

${10, 13, 13}$ : e.g. $13 + 13 - 10 = 16$ , $13 \times 10/13 = 10$ … target 24 not obviously blocked → $V =$ maybe, keep.
${4, 4, 10}$ : e.g. $4 \times (10 - 4) = 24$ → target is reachable → $V =$ maybe (in fact a winner!), keep.
${6, 9, 13}$ : max product/sum combinations ( $6 \cdot 9 = 54$ then with $13$ : $54 - 13 = 41$ , $54/13 \approx 4.2$ ; $9 + 13 + 6 = 28$ ; $13 \cdot 6 - 9 = 69$ …) — the cheap bound finds no route landing on $24$ and the reachable values straddle away from it → $V =$ impossible, prune. Why this step? $V (s)$ — the very criterion defined above — kills a dead branch before we spend depth on it, which is the core advantage over a linear chain that cannot undo.

Step 3 — Backtrack / keep survivors. After pruning, $3 - 1 = 2$ branches survive; the greedy chain (stuck on ${10, 13, 13}$ without exploring ${4, 4, 10}$ ) had 0 recovery routes. Why this step? Counting survivors shows what search buys: it retains multiple live options and can backtrack to them, whereas the greedy chain has already discarded the winning branch.

Verify: survivor count $= 2$ , pruned count $= 1$ , total generated $= 3$ ; $2 + 1 = 3$ ✓. And the surviving state ${4, 4, 10}$ genuinely solves it: $4 \times (10 - 4) = 4 \times 6 = 24$ ✓. The point that earns marks: backtracking + intermediate evaluation is what SC lacks — SC votes over finished chains and can never undo a bad early step. (Contrast with Beam Search and BFS/DFS, the search backbone of ToT, and note both differ from a plain Chain-of-Thought Prompting chain.)

Cell J — even $N$ AND bad regime ( $p < \frac{1}{2}$ )

Worked example Ex 10 ·

$p = 0.4$ , $N = 4$ — ties and error amplification together The nastiest corner: an even sample size and a below-coin-flip chain. What do the three buckets look like, and what is the effective accuracy after a fair tie-break?

Forecast: compared to the raw 40%, will the effective accuracy be higher or lower?

Step 1 — Win bucket $k \geq 3$ (using $p = 0.4$ ). $P_{win} = (3 4) (0.4)^{3} (0.6) + (0.4)^{4} = 4 (0.064) (0.6) + 0.0256 = 0.1536 + 0.0256 = 0.1792$ Why this step? Same win bucket as Cell D but with the roles of $p$ and $1 - p$ swapped — note it collapses to Cell D's lose bucket, a neat symmetry.

Step 2 — Tie bucket $k = 2$ . $P_{tie} = (2 4) (0.4)^{2} (0.6)^{2} = 6 (0.16) (0.36) = 0.3456$ Why this step? The tie term is symmetric in $p \leftrightarrow 1 - p$ , so it is identical to Cell D's tie ( $0.3456$ ).

Step 3 — Lose bucket $k \leq 1$ . $P_{lose} = (1 4) (0.4) (0.6)^{3} + (0.6)^{4} = 4 (0.4) (0.216) + 0.1296 = 0.3456 + 0.1296 = 0.4752$ Why this step? This mirrors Cell D's win bucket ( $0.4752$ ) — the whole distribution is Cell D reflected.

Verify: buckets sum to $0.1792 + 0.3456 + 0.4752 = 1.0000$ ✓. Effective accuracy with fair tie-break $= P_{win} + \frac{1}{2} P_{tie} = 0.1792 + 0.1728 = 0.3520 < 0.4$ ✗. The lesson: below the hinge, voting still hurts — and the tie bucket does not save you, it just splits the (already losing) mass in half. Even $N$ neither rescues nor worsens the direction; the sign of $(p - \frac{1}{2})$ alone decides win-vs-lose.

Cheat-recall

Recall Which regime helps, which hurts?

Voting helps only when single-chain accuracy $p$ exceeds ::: one half ( $p > \frac{1}{2}$ ); below it, voting amplifies error.

Recall Odd vs even

$N$ ? Prefer odd $N$ because ::: even $N$ can produce a tied vote ( $k = N /2$ ) with no strict majority, forcing a tie-break.

Recall The three buckets for any

$N$ ? $P_{win}$ ( $k > N /2$ ), $P_{tie}$ ( $k = N /2$ ), $P_{lose}$ ( $k < N /2$ ); for odd $N$ ::: $P_{tie} = 0$ so they reduce to the odd- $N$ majority formula.

Recall ToT vs SC in one line?

SC votes over finished chains; ToT ::: generates partial thoughts, evaluates + prunes intermediate states via $V (s)$ , and can backtrack.