Beyond "show your work": the reliability problem
Say you are building an AI tutor for AICI's own JEE Physics practice track, and you ask a large language model a single hard numerical problem. You prompt it to reason step by step before answering — the sibling chapter in this course already showed you that trick, and it works: accuracy on multi-step arithmetic and word problems jumps sharply the moment the model is allowed to write out intermediate steps instead of blurting a final number. But if you run that same prompting strategy once each on a hundred different problems of comparable difficulty, something uncomfortable shows up. The model does not solve every one of them. On problems like these it gets right roughly six times out of ten, greedy chain-of-thought (CoT) decoding is really a coin with a 60% bias, not a solved problem. A tutoring product that is wrong four times in ten is not shippable. The question this chapter asks is not "does step-by-step prompting help reasoning" — you already know it does — but two much sharper ones: why does spending more tokens on intermediate steps buy more computation at all, and once you accept that CoT is a noisy sample from a distribution over reasoning paths, how do you engineer around that noise in a real, cost-constrained production system?
Why intermediate tokens buy computation
A transformer decoder has a fixed number of layers, L. Every token position gets exactly one pass through those L layers before it must commit to a probability distribution over the next token. That is a hard ceiling on the amount of sequential computation the model can perform to produce any single token: no matter how large the hidden dimension or how many attention heads, one forward pass through L layers is L sequential computation steps, full stop. Formally, this was pinned down by William Merrill and Ashish Sabharwal in "The Parallelism Tradeoff: Limitations of Log-Precision Transformers" (TACL, 2023): a transformer decoder with realistic (logarithmic) numerical precision, decoding one token at a time with no intermediate output, can only compute functions inside the complexity class TC0 — problems solvable by circuits of constant depth and polynomial size built from threshold gates. That class is a genuinely weak one. It does not contain some problems that are otherwise "easy" in the everyday sense, like composing a long chain of function lookups or verifying certain kinds of graph connectivity, because those require a number of sequential dependency steps that grows with the input, not a constant.
Chain-of-thought prompting is, from this angle, a way of cheating the ceiling. Every generated token gets appended to the context and re-read on the next forward pass. That means the model is not limited to L layers of computation for the whole problem — it gets L layers per generated token, and it can use the tokens themselves as a scratchpad to carry partial results forward. Merrill and Sabharwal's follow-up paper, "The Expressive Power of Transformers with Chain of Thought" (ICLR, 2024), makes this precise: allowing the model T steps of intermediate decoding lets a constant-depth transformer simulate roughly T sequential steps of computation, so as T grows the reachable class of solvable problems strictly grows past TC0. This is the real mechanistic reason CoT "unlocks" reasoning rather than being a persuasion trick that puts the model in a helpful mood: it converts a bounded-depth parallel computation into an unbounded-depth serial one, with token count standing in for compute budget. It also predicts something you can check empirically — problems whose difficulty scales with input size (long multiplication, multi-hop logic, simulating a state machine for many steps) should show the sharpest CoT gains, because those are exactly the problems whose required sequential depth outruns a fixed L. Problems that are already shallow (single-fact lookups, one-step arithmetic) should show little or no CoT benefit, and this is exactly what has been observed in practice.
Self-consistency: sampling the reasoning distribution
Accepting that each CoT decode is one sample from a distribution over reasoning paths reframes the reliability problem as a statistics problem. Wang, Wei, Schuurmans, Le, Chi, Narang, Chowdhery, and Zhou proposed exactly this reframing in "Self-Consistency Improves Chain of Thought Reasoning in Language Models" (ICLR, 2023): instead of decoding one chain greedily, sample k independent chains at temperature > 0, extract the final answer from each, and return the answer that the largest number of chains agree on. The reasoning text of each chain is thrown away after voting — only the final answers are marginalized over. The intuition is direct: correct reasoning paths tend to converge on the same correct answer through different routes, while errors tend to be idiosyncratic and scatter across different wrong answers, so a majority vote suppresses the noise without needing a better model.
Work through this on a concrete problem: a bag has 5 red and 7 blue balls; two balls are drawn without replacement; find P(both red). The correct approach multiplies conditional probabilities: P(1st red) = 5/12, and given the first was red, P(2nd red | 1st red) = 4/11, since one red ball and one ball overall are now gone. Multiplying gives 5/12 × 4/11 = 20/132 = 5/33 ≈ 0.152. Equivalently, by combinations: C(5,2)/C(12,2) = 10/66 = 5/33, the same answer by a different route. The two most common wrong answers come from two specific misconceptions: stopping after the first draw and reporting 5/12, or treating the two draws as independent (sampling with replacement) and computing (5/12)² = 25/144 ≈ 0.174. The diagram below shows five independently sampled chains on this exact question: three converge on 5/33 by two different correct routes, one stops early at 5/12, and one wrongly assumes independence to get 25/144. Majority vote returns 5/33 — the correct answer wins not because any single chain is trustworthy, but because three independent, differently-reasoned chains happened to agree.
Notice that in this particular draw of five samples, 3 of 5 chains were correct — a per-sample accuracy of exactly 0.6. That is not a coincidence I am hiding from you; it is the value used below because it makes the arithmetic line up with the diagram. A tiny implementation of the voting step, once you have already collected k sampled final answers as strings, is a five-line function:
from collections import Counter
def self_consistency_vote(sampled_answers):
"""Return the majority answer and its vote share."""
tally = Counter(sampled_answers)
answer, votes = tally.most_common(1)[0]
confidence = votes / len(sampled_answers)
return answer, confidence
samples = ["5/33", "5/33", "5/33", "5/12", "25/144"]
result, conf = self_consistency_vote(samples)
print(result, conf)Tracing this by hand: Counter(samples) builds the map {'5/33': 3, '5/12': 1, '25/144': 1}; most_common(1) returns the single highest-count entry as a list of one (key, count) tuple, here [('5/33', 3)]; indexing [0] unpacks it to answer = '5/33', votes = 3; and confidence = 3 / 5 = 0.6. The call to sample_llm_k_times(prompt, k, temperature) that would actually produce the samples list in a real pipeline is an assumed helper, not shown — it is just k independent calls to the model's generation endpoint. So print(result, conf) outputs exactly 5/33 0.6.
Now derive, rather than simulate, how much majority voting actually buys you. Model each of the k sampled chains as an independent Bernoulli trial that lands on the correct answer with probability p = 0.6 (matching the sample above) and on some wrong answer otherwise. With k = 5 chains, the vote is correct whenever at least 3 of the 5 trials succeed, i.e. X ∼ Binomial(5, 0.6) and we need P(X ≥ 3):
P(X=3) = C(5,3)(0.6)³(0.4)² = 10 × 0.216 × 0.16 = 0.3456
P(X=4) = C(5,4)(0.6)⁴(0.4)¹ = 5 × 0.1296 × 0.4 = 0.2592
P(X=5) = C(5,5)(0.6)⁵ = 0.07776
P(X≥3) = 0.3456 + 0.2592 + 0.07776 = 0.68256
A single greedy sample is correct 60% of the time; five independent samples with majority voting are correct 68.3% of the time — an 8.3 percentage point gain purchased with zero change to the model's weights, using only extra inference calls. This is the concrete mechanism behind Wang et al.'s headline result: self-consistency reliably improved accuracy over greedy CoT across arithmetic, commonsense, and symbolic reasoning benchmarks, and the reason is exactly this binomial concentration effect, not any change in what the model "knows."
What self-consistency costs at serving time
The gain is not free, and the tradeoff is worth being precise about, because it is the kind of decision an inference-serving engineer actually has to make. Sampling k chains multiplies the number of decode calls by k; if a single greedy CoT answer costs, say, 400 output tokens of generation, k = 5 self-consistency costs roughly 5 × 400 = 2000 output tokens' worth of compute for one answered question, plus the overhead of running the vote. On GPU-served infrastructure this is not simply "5x latency," because the k samples share an identical prompt prefix and can be batched: production serving systems such as vLLM (Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention," SOSP 2023) cache and reuse the key-value (KV) attention state for a shared prompt prefix across concurrently decoded sequences, so the prefill cost of encoding the question is paid once, not k times. But the decode phase — generating each new reasoning token for each of the k chains — still costs real GPU time and KV-cache memory per chain, because each chain's reasoning diverges token by token and needs its own cache going forward. So the honest accounting is: self-consistency amortizes the prompt-encoding cost across k samples but still pays close to k times the decode compute and memory, which is the dominant cost for long chains. Whether that is worth it is an accuracy-per-rupee question, and the diminishing-returns shape of the binomial curve (worked out fully in Active Recall below) is exactly the curve you would plot against inference cost to make that call.
The chain doesn't have to be honest: faithfulness
The most common misconception at this point is to treat the words in a chain-of-thought as a transcript of the model's actual computation — "if the explanation is logically valid, the answer must have been derived that way." Turpin, Michael, Perez, and Bowman directly tested this in "Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting" (NeurIPS, 2023). They inserted a biasing feature into the prompt — for instance, reordering multiple-choice options so the correct answer always sat in a particular position across the few-shot examples, or adding a suggestive cue about which answer a supposedly authoritative source preferred — and found that models shifted their final answers substantially toward the biased option, sometimes flipping accuracy by dozens of percentage points, while the generated chain-of-thought almost never mentioned the bias at all. Instead, the model constructed a fluent, internally consistent-sounding justification for whatever answer the bias had already pushed it toward. The explanation was a plausible post-hoc story, not a report of the actual causal process that produced the answer.
This matters for exactly the systems this chapter has been building toward. Self-consistency voting sidesteps the faithfulness problem partially, by design: it never trusts any individual chain's reasoning text, only the final answer, and only in aggregate across independently sampled chains. But it does not solve faithfulness — if the same bias affects all k samples identically (say, a spuriously ordered option list baked into the prompt template), every chain will rationalize toward the same wrong answer and the vote will confidently converge on it. The correction to internalize is this: a chain-of-thought that reads as coherent, step-by-step, and locally valid is evidence about the model's fluency at generating justifications, and only weak, defeasible evidence about how it actually arrived at the answer. Treat CoT explanations as a diagnostic aid for a human reviewer, not as a verified proof, unless you have independently checked that perturbing irrelevant prompt features does not move the answer.
From one chain to a search tree
Self-consistency samples k chains independently and combines them only at the very end, which wastes information — two chains that agree on the first three steps and then diverge are treated as no more related than two chains that disagree from token one. Two later lines of work restructure the process. Zhou, Schärli, Hou, Wei, Scales, Wang, Schuurmans, Cui, Bousquet, Le, and Chi, in "Least-to-Most Prompting Enables Complex Reasoning in Large Language Models" (ICLR, 2023), split reasoning into two explicit prompted stages: first decompose the problem into an ordered list of simpler subproblems, then solve them one at a time, feeding each solved subproblem's answer into the prompt for the next. This directly targets a failure mode plain CoT does not fix well — problems that need a correct decomposition strategy before any arithmetic starts, where a single linear chain tends to attempt the whole problem at once and lose track partway through.
Yao, Yu, Zhao, Shafran, Griffiths, Cao, and Narasimhan, in "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" (NeurIPS, 2023), generalize self-consistency's flat sampling into an explicit search tree: at each reasoning step, the model proposes several candidate next steps, a separate self-evaluation prompt scores each candidate's promise, and a search procedure (breadth-first or depth-first) keeps the strongest partial paths and prunes or backtracks from weak ones, rather than committing to one full chain per sample and only comparing at the finish line. This costs more inference than self-consistency for the same k, since scoring intermediate states is extra model calls, but it can recover from a bad step three tokens in instead of only ever voting on which full, potentially-derailed chain to trust.
A third direction attacks the same problem from the training side rather than the decoding side: instead of only checking whether the final answer is right, train a separate model to grade each individual reasoning step. Lightman, Kosaraju, Burda, Edwards, Baker, Lee, Leike, Schulman, Sutskever, and Cobbe, in "Let's Verify Step by Step" (2023), compared an outcome-supervised reward model (ORM, trained only on whether the final answer matched) against a process-supervised reward model (PRM, trained on human-labeled correctness of every intermediate step, using their PRM800K step-level dataset on competition math problems). Using the PRM to select the best chain out of many candidates at test time outperformed plain majority-vote self-consistency in their evaluations, because a process-level verifier can reject a chain that reaches the right final number through a broken derivation, or promote a chain that reasoned correctly but made a late arithmetic slip — distinctions a majority vote over final answers alone cannot see.
Active recall
Attempt each question before reading its answer.
- Why does a transformer decoder without any intermediate output tokens have a bounded computational budget for solving a single problem, in terms of the model's own architecture?
- Using the model of independent chains with per-chain correctness probability p = 0.6, what is P(majority correct) with k = 7 samples? Is the gain over k = 5 large or small, and what does that tell you about scaling k further?
- A team improves their base model so that a single greedy CoT chain is now correct with probability p = 0.8 instead of 0.6, and they can now also afford k = 7 samples instead of 5 because prompt-prefix caching cut their per-sample cost. Compute the majority-vote accuracy at (p = 0.8, k = 5) and at (p = 0.8, k = 7). Which factor — the accuracy jump or the sample-count jump — contributed more, and does self-consistency's inference cost scale the same way at k = 7 as it did at k = 5?
- A student claims: "the chain-of-thought explanation the model printed is logically valid, so the final answer must be correct." Using the Turpin et al. finding, explain precisely why this inference is unsound.
- Why can a tree-of-thoughts search recover from an error that a five-sample self-consistency vote cannot, even holding the total number of model calls roughly equal?
Answers
1. Every token position passes through a fixed number of layers L exactly once before the model must output a distribution for the next token; with no intermediate tokens, the entire problem must be solved within that one constant-depth pass, which formally restricts the class of directly-computable functions to something like TC0 (Merrill & Sabharwal, 2023) — constant-depth, bounded computation, regardless of parameter count.
2. With p = 0.6 and k = 7, majority means X ≥ 4 out of Binomial(7, 0.6). Computing: P(X≥4) ≈ 0.7102 (71.0%), versus 0.68256 (68.3%) at k = 5 — a gain of about 2.8 percentage points for two extra samples (a 40% increase in inference calls). Compare that to the 1 → 5 baseline: going from k=1 (60%) to k=5 (68.3%) was an 8.3-point gain for 4 extra samples. The marginal return per extra sample is clearly shrinking (from about 2.1 points/sample early on to about 1.4 points/sample here), which is the diminishing-returns signature of binomial concentration: pushing k further keeps helping but at a steadily falling rate, so past some k the extra inference cost stops being worth the accuracy gain.
3. At p = 0.8, k = 5: majority needs X ≥ 3 out of Binomial(5, 0.8): P(X≥3) = 0.94208 (94.2%). At p = 0.8, k = 7: majority needs X ≥ 4 out of Binomial(7, 0.8): P(X≥4) = 0.966656 (96.7%). Ripple effects to trace fully: (a) raising p alone (k fixed at 5) took accuracy from 68.256% to 94.208%, a 26.0-point jump — far larger than any amount of extra sampling could buy at the old p = 0.6, confirming that a better base model dominates more voting. (b) Adding k = 7 on top of the better model adds only about 2.5 more points (94.2% → 96.7%, precisely 96.6656% − 94.208% = 2.46 points), the same diminishing-returns pattern as question 2, now at a higher baseline where there is less room left to gain. (c) On cost: prefix caching only amortizes the shared prompt-encoding (prefill) cost; the decode cost of generating each chain's reasoning tokens still scales close to linearly with k, so moving from k=5 to k=7 still costs roughly 40% more decode compute and KV-cache memory per question even with caching in place — the caching improves the constant factor, it does not remove the k-dependence. (d) Nothing about raising p or k changes whether the explanations are faithful (question 4's issue is orthogonal to accuracy) — a more accurate, more heavily voted answer is not automatically a more honestly-derived one.
4. Turpin et al. showed that models given a biasing feature in the prompt (e.g. a manipulated answer-key ordering) shifted their final answers toward the induced bias while the printed chain-of-thought never mentioned the bias and instead fabricated a fluent justification for the biased answer. A chain that is locally coherent and logically well-formed can therefore be a post-hoc rationalization rather than a faithful trace of the actual computation, so logical validity of the explanation is not evidence that the stated reasoning caused the stated answer.
5. Self-consistency only compares chains at the very end, after each has committed to a complete, independent path, so a chain that goes wrong at step one still consumes a full sample's worth of compute producing an unusable answer and is simply outvoted. Tree-of-thoughts scores and prunes at each intermediate step, so a branch that goes wrong early gets discarded immediately and the freed search effort is redirected to expanding more promising partial paths instead of finishing a doomed chain to completion — the same total budget is spent more where it matters.
Think About It
Think about this: How would you explain chain-of-thought prompting: unlocking reasoning ability to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Key Takeaways — Summary and Recap
Let us recap what we covered: the core ideas behind chain-of-thought prompting: unlocking reasoning ability, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.