Self-consistency and tree-of-thought: Exercises

Prerequisites you may lean on: Chain-of-Thought Prompting, Monte Carlo Estimation, Ensemble Methods and Majority Voting, Temperature and Sampling in LLMs, Beam Search and BFS/DFS, Retrieval-Augmented Generation (RAG).

Throughout, we use these already-defined symbols from the parent note:

$N$ = number of independently sampled reasoning chains.
$p$ = probability a single chain reaches the correct final answer.
$1 [\cdot]$ = the indicator: it equals $1$ when the statement inside is true, $0$ otherwise. (Think of it as a light switch that turns on only for a match.)
$(k N)$ = " $N$ choose $k$ " = number of ways to pick which $k$ of the $N$ chains are the correct ones.

Level 1 — Recognition

L1.1

State, in one sentence each, what self-consistency (SC) changes about chain-of-thought, and whether it changes the prompt or the decoding.

Recall Solution

SC keeps the same chain-of-thought prompt but changes the decoding: instead of taking one chain, it samples $N$ chains at temperature $> 0$ and returns the majority-vote final answer. It is a decoding strategy, not a new prompt.

L1.2

Fill the blanks (cloze practice).

SC combines chains by majority vote, requires temperature greater than 0, and its cost scales as == $N \times$ == the cost of one chain.

ToT combines partial thoughts by search + evaluation and its unique extra ability over CoT/SC is backtracking.

Recall Solution

Given inline above. Key checks: SC = majority vote, temp $> 0$ , cost $N \times$ . ToT = search/evaluation, and its distinctive power is backtracking (abandoning a dead branch).

L1.3

Match each method to its structure: CoT, SC, ToT ↔ branching tree, one linear chain, N linear chains.

Recall Solution

CoT ↔ one linear chain. SC ↔ $N$ linear chains. ToT ↔ branching tree.

Level 2 — Application

L2.1

A single CoT chain is correct with probability $p = 0.6$ . You sample $N = 3$ chains and take the majority. Compute $P (majority correct)$ .

Recall Solution

Using the majority threshold $k_{m i n} = ⌈(3 + 1) /2 ⌉ = 2$ : majority of 3 means at least 2 chains correct, i.e. $k \in {2, 3}$ . $P = (2 3) (0.6)^{2} (0.4)^{1} + (3 3) (0.6)^{3} (0.4)^{0} .$ $(2 3) = 3$ , $(3 3) = 1$ . $P = 3 (0.36) (0.4) + 1 (0.216) = 0.432 + 0.216 = 0.648.$ Accuracy rose $60% \to 64.8%$ from voting alone.

L2.2

Same $p = 0.6$ but now $N = 5$ . Confirm the parent note's figure of $0.6826$ .

Recall Solution

Using the majority threshold $k_{m i n} = ⌈(5 + 1) /2 ⌉ = 3$ : majority of 5 means at least 3 correct, $k \in {3, 4, 5}$ . $P = (3 5) (0.6)^{3} (0.4)^{2} + (4 5) (0.6)^{4} (0.4)^{1} + (5 5) (0.6)^{5} .$ $(3 5) = 10, (4 5) = 5, (5 5) = 1$ .

$10 (0.216) (0.16) = 0.3456$
$5 (0.1296) (0.4) = 0.2592$
$1 (0.07776) = 0.07776$

Sum $= 0.68256 \approx 0.6826$ . ✓

L2.3

A ToT run has depth $d = 3$ , branching $k = 4$ thoughts generated per state, and keeps beam width $b = 2$ states per level. Using the parent's estimate, how many generate calls and how many evaluate calls does it make? Compare the total to an SC run with $N = 10$ .

Recall Solution

Why an evaluate step costs a full call. The state evaluator $V (s)$ is itself an LLM prompt: you feed the model the partial reasoning and ask it to score the state ("sure / maybe / impossible" or a number). That is a separate API round-trip with its own tokens, so we count it as one LLM call, on par with a generate call. (If a cheap heuristic evaluator were used instead of the LLM, evaluate calls would be nearly free — but the parent's estimate assumes an LLM evaluator, which is the usual ToT setup.) Parent estimate: generate calls $\approx d \cdot b \cdot k$ and evaluate calls $\approx d \cdot b \cdot k$ . $d \cdot b \cdot k = 3 \cdot 2 \cdot 4 = 24 generate, 24 evaluate .$ Total $\approx 48$ LLM calls. SC with $N = 10$ makes $10$ calls. So ToT here is roughly $4.8 \times$ the SC cost — exactly the " $≫ N$ " regime the parent warns about. On the " $\approx$ ". This is an upper-bound-flavoured order estimate: it holds when every kept state generates a full $k$ children at each of $d$ levels and every child is evaluated. Real runs are usually cheaper — pruning kills branches early (fewer than $b$ survivors at some levels), and early solutions can terminate the search before depth $d$ . So read $\approx d bk$ as "roughly this many, and rarely more," not an exact count.

Level 3 — Analysis

L3.1

Explain, with the Condorcet logic, why raising $N$ helps only when $p > 0.5$ , and what happens to majority accuracy when $p < 0.5$ . Read the figure carefully before answering.

Figure — Self-consistency and tree-of-thought

Recall Solution

Reading the figure. The horizontal axis is $N$ (number of chains, odd values), the vertical axis is $P (majority correct)$ . There are three curves, each for a fixed single-chain accuracy $p$ :

the red solid curve is $p = 0.6$ (the case $p > 0.5$ ),
the black dashed curve is $p = 0.4$ (the case $p < 0.5$ ),
the black dotted curve is $p = 0.5$ (the borderline).

Now the logic:

When $p > 0.5$ (red solid, upper curve), each chain is more often right than wrong, so aggregating more of them pushes the majority toward the correct answer: the curve rises toward 1.
When $p < 0.5$ (black dashed, lower curve), each chain is more often wrong, so the majority increasingly agrees on a wrong answer: the curve falls toward 0.
At exactly $p = 0.5$ (black dotted, flat near the middle) voting adds nothing — it's a coin flip regardless of $N$ .

So SC is an accuracy amplifier, not a fixer: it magnifies whatever tendency the single chain already has. You need a base learner that beats chance.

L3.2

Show that SC is a Monte-Carlo estimate of $p (a ∣ prompt)$ , and explain why sampling with temperature $> 0$ is what draws $r^{(i)} \sim p (r ∣ prompt)$ .

Recall Solution

The target is the marginal over hidden reasoning $r$ : $p (a ∣ prompt) = \sum_{r} p (a ∣ r) p (r ∣ prompt) .$ We cannot enumerate all $r$ , so we draw $N$ samples $r^{(i)} \sim p (r ∣ prompt)$ ; each deterministically yields answer $a^{(i)}$ . The Monte-Carlo estimate of the marginal is the sample frequency $\overset{p}{^} (a) = \frac{1}{N} \sum_{i = 1}^{N} 1 [a^{(i)} = a],$ and $ar g max_{a} \overset{p}{^} (a)$ is exactly the majority vote. Why temperature $> 0$ recovers the model's distribution. At each step the model produces a raw score (logit) $z_{v}$ for every candidate token $v$ . Temperature $T$ rescales these before converting to probabilities: $P (v) = \frac{e x p ( z _{v} / T )}{\sum _{u} e x p ( z _{u} / T )} .$

At $T = 1$ this is the model's native next-token distribution — sampling from it draws genuine samples $r^{(i)} \sim p (r ∣ prompt)$ .
As $T \to 0$ the largest logit dominates the ratio, so $P$ collapses onto the single argmax token: decoding becomes deterministic, every chain is identical, and you have one point, not a sample.
Values like $T \in [0.5, 0.7]$ keep the ordering but soften it enough to draw diverse reasoning paths — which is exactly the diversity the vote needs.

So "temperature $> 0$ " is precisely the knob that makes decoding a draw from a distribution rather than a fixed choice.

L3.3

You run SC with $N = 4$ . The four extracted answers are ${7, 7, 12, 7}$ . Give $\overset{a}{^}$ and $\overset{p}{^} (\overset{a}{^})$ . Then explain why $N = 4$ (an even number) is a slightly awkward choice. (Recall: $\overset{a}{^}, \overset{p}{^}$ are estimators — quantities read off our finite sample, per the definition at the top.)

Recall Solution

Counts: $7$ appears $3$ times, $12$ once. The estimator $\overset{a}{^}$ (the sample mode) is $\overset{a}{^} = 7$ , with $\overset{p}{^} (7) = 3/4 = 0.75$ (our sample estimate of $p (7 ∣ prompt)$ ). Even $N$ risks ties (e.g. ${7, 7, 12, 12}$ ), which have no unique majority and force an arbitrary tie-break. Odd $N$ guarantees a strict winner between two options, so odd $N$ is the safer default.

Level 4 — Synthesis

L4.1

You have three candidate systems for a math-word-problem benchmark: plain CoT, SC ( $N = 20$ ), and ToT ( $d = 4, b = 3, k = 3$ ). For each, state (a) approximate LLM-call cost, (b) whether it can backtrack, and (c) the one task property that most favours it.

Recall Solution

Why ToT's cost doubles the generate count. As in L2.3, ToT with an LLM evaluator makes one generate call and one evaluate call per candidate state, and each evaluate is a full API round-trip — so we multiply the generate estimate by $2$ . (With a free heuristic evaluator the factor would drop toward $1$ .) The counts below are the same order-estimate " $\approx$ " as in L2.3: they assume full branching with no early termination and so are near-upper-bounds; real pruning makes them cheaper.

System	(a) Cost (calls)	(b) Backtrack?	(c) Favoured when…
CoT	$1$	No	task is easy / budget is tiny
SC $N = 20$	$20$	No	single-chain accuracy already $> 0.5$ ; want cheap lift
ToT $d = 4, b = 3, k = 3$	$\approx d bk \times 2 = 4 \cdot 3 \cdot 3 \cdot 2 = 72$	Yes	task has dead-ends needing prune/undo (puzzles, planning)

Cost of ToT here is $\approx 72$ calls vs SC's $20$ — the " $≫ N$ " regime. Choose ToT only when the problem genuinely needs search, not just voting.

L4.2

Design a hybrid: at each ToT leaf you run self-consistency on the final step. Sketch why this is sensible, and estimate the cost if ToT reaches $L$ leaves and each does SC with $N$ votes.

Recall Solution

Sensible because: ToT's search finds promising complete reasoning skeletons (it prunes dead-ends), but the final numeric answer at a leaf can still be noisy. Running SC over the last step at each surviving leaf denoises that final answer via majority vote — search for the structure, vote for the answer. Cost: ToT search cost $\approx 2 d b k$ (generate + evaluate, same order-estimate caveat as above) plus $L \cdot N$ final-answer samples. So total $\approx 2 d bk + L N$ calls. Concretely with $d = 4, b = 3, k = 3, L = 6, N = 5$ : $72 + 30 = 102$ calls.

L4.3

A colleague proposes averaging the raw token probabilities of the $N$ chains and picking the highest-probability answer string, calling it "self-consistency." Explain what's wrong and what SC actually aggregates.

Recall Solution

SC does not average token/confidence probabilities. It marginalizes over reasoning paths by voting over discrete final answers: two chains with completely different reasoning but the same answer each contribute one vote. Averaging token probabilities instead (a) mixes surface form with answer, and (b) lets one over-confident chain dominate — the opposite of the "wisdom of many independent noisy sensors" that makes SC robust. The correct aggregation is $ar g max_{a} \sum_{i} 1 [a^{(i)} = a]$ .

Level 5 — Mastery

L5.1

Prove that for majority voting with odd $N$ and independent chains of accuracy $p$ , the majority accuracy $M (N, p)$ satisfies $M (N, p) > p$ whenever $p > 0.5$ for $N = 3$ , by direct comparison. (Do it concretely for $p = 0.6$ , then state the general condition.)

Recall Solution

For $N = 3$ , threshold $k_{m i n} = 2$ : $M (3, p) = (2 3) p^{2} (1 - p) + p^{3} = 3 p^{2} (1 - p) + p^{3} = 3 p^{2} - 2 p^{3}$ . At $p = 0.6$ : $3 (0.36) - 2 (0.216) = 1.08 - 0.432 = 0.648 > 0.6$ . ✓ General: $M (3, p) - p = 3 p^{2} - 2 p^{3} - p$ . Factor it: $3 p^{2} - 2 p^{3} - p = - p (2 p^{2} - 3 p + 1) = - p (2 p - 1) (p - 1) = p (2 p - 1) (1 - p)$ . For $p \in (0.5, 1)$ : $p > 0$ , $(2 p - 1) > 0$ , $(1 - p) > 0$ → product of three positive factors $> 0$ . Hence $M (3, p) > p$ exactly when $p > 0.5$ . This is the Condorcet result made concrete.

L5.2

Extend the Game-of-24 reasoning: given numbers $4, 9, 10, 13$ , find one valid expression reaching $24$ , and explain which ToT step (generate / evaluate / prune / backtrack) does the heavy lifting.

Recall Solution

One valid solution: $(10 - 4) \times (13 - 9) = 6 \times 4 = 24.$ Which step matters: the evaluate-and-prune step. A greedy CoT that commits early to, say, $4 + 9 = 13$ leaves ${13, 10, 13}$ , which cannot reach $24$ ; CoT gets stuck. ToT's evaluator labels such states "impossible" and prunes them before wasting depth, while backtracking lets the search return to try $10 - 4$ instead. Generation supplies candidates; evaluation + pruning is what turns a hopeless greedy walk into a solvable search.

L5.3

You must ship a system under a hard budget of 30 LLM calls per query for a benchmark where single-chain accuracy is $p = 0.55$ and problems are not combinatorial dead-end puzzles. Choose SC vs ToT, choose the parameter, and justify with numbers.

Recall Solution

The task has no dead-ends, so ToT's backtracking buys little — and ToT would blow the budget fast ( $2 d bk$ grows quickly). Choose SC. With $p = 0.55 > 0.5$ , voting amplifies accuracy, and the whole $30$ -call budget can go to votes. Use the largest odd $N \leq 30$ : $N = 29$ . Sanity check the direction of the gain at a small odd $N = 5$ (threshold $k_{m i n} = 3$ ): $M (5, 0.55) = (3 5) (0.55)^{3} (0.45)^{2} + (4 5) (0.55)^{4} (0.45) + (0.55)^{5}$ $= 10 (0.166375) (0.2025) + 5 (0.09150625) (0.45) + 0.0503284$ $= 0.336909 + 0.205889 + 0.050328 = 0.593126 > 0.55.$ ✓ Already a lift at $N = 5$ ; pushing to $N = 29$ climbs further toward the Condorcet limit. Verdict: SC with $N = 29$ (odd, within budget), no ToT.

Recall One-line self-test before you leave

SC amplifies accuracy by voting (needs $p > 0.5$ , temp $> 0$ , cost $N \times$ ); ToT searches a tree with generate/evaluate/prune/backtrack (cost $≫ N \times$ , wins on dead-end tasks).