Self-Consistency Is Just Probability Amplification

Some AI results feel new. This one felt like meeting an old exam question in a new outfit. When I first read the self-consistency paper, the move it describes, sample several answers and take the majority, landed as something every randomized-algorithms course teaches: you can boost a coin that is merely better than fair into one that is almost always right, just by flipping it enough times and trusting the majority. The paper was from 2022; the theorem behind it is decades older.

This is the fourth post in a series that reads modern AI through the classic computer science toolkit. It stands alone, but it pairs naturally with the previous one [4]: that post was about using a separate checker to verify an answer, and this one is about a different robustness trick that needs no checker at all, just repetition and a vote.

The old trick: amplifying a coin that beats a coin flip

Randomized algorithms come in two classic flavours. A Las Vegas algorithm is always correct but takes a random amount of time; a Monte Carlo algorithm runs in bounded time but is only probably correct, with a bounded error probability. Self-consistency lives on the Monte Carlo side. Take the simplest binary case first: one run is correct with probability p, and p is above one-half, so it is right more often than a fair coin. On its own that is not reassuring. The classic fix is amplification: run it k independent times and take the majority answer. As long as each run is independent and p > 1/2, the probability that the majority is wrong shrinks exponentially in k [2].

The intuition is a concentration bound. With k independent trials each correct with probability p > 1/2, the fraction that are correct concentrates around p, so the chance that fewer than half are correct falls off exponentially. A Hoeffding-style bound caps it at exp(-2k(p - 1/2)²), an upper bound, not an estimate, with a tied vote on even k counted as an error: the error decays exponentially in the number of trials k, and faster the further p sits above one-half [2]. That form is the binary case. For a categorical vote over many possible answers the same concentration idea applies, but the rate is governed by the gap between the correct answer’s probability and the largest wrong one, and the vote converges to the correct answer only when that gap is positive. So you do not need p to be large, you need the correct answer ahead of every rival, independent draws, and patience for a few of them.

That is the whole trick. A slightly-better-than-random procedure, repeated and majority-voted, becomes a reliably-correct one, with the error you tolerate setting how many trials you run.

The new trick: self-consistency

Now the 2022 version. Chain-of-thought prompting asks a model to reason step by step before answering. The usual decoding takes one greedy path. Self-consistency, from Wang and colleagues, replaces that with a different decoding strategy: sample a diverse set of reasoning paths at a non-zero temperature, then select the most consistent final answer by marginalising over the sampled paths, which in practice means a plurality vote over the sampled answers [3].

The gains are large. On a range of arithmetic and commonsense benchmarks the paper reports substantial jumps over greedy chain-of-thought decoding, gains of roughly +17.9 percentage points on GSM8K, +11.0 on SVAMP, and +12.2 on AQuA in absolute accuracy [3]. The stated intuition is that a hard problem usually admits several different correct routes to the same answer, so agreement across independently sampled routes is a signal that the answer is right.

The aha: these are the same algorithm

Line the two up and the mapping is almost embarrassingly direct.

Stochastic decoding is the randomness source: fresh random draws turn a deterministic decoder into a sampler, and temperature shapes the distribution those draws come from. Conditional on a fixed prompt, model, decoding configuration, and answer-normalisation rule, we treat the sampled answers as independent draws from that distribution. The model’s distribution over answers is the Monte Carlo output: each sampled chain is one trial, landing on the correct answer with some probability. And the plurality vote over sampled answers is the amplifier, the exact step that turns a favourable answer distribution into a more reliable aggregate.

One wrinkle the coin story hides: a model does not choose between “right” and “wrong”, it spreads probability across many possible answers. So the honest version is plurality voting, take the answer that appears most often, and it amplifies the correct answer whenever that answer is the single most likely one the model emits, not only when the model is right more than half the time. A correct answer at 40% still wins if the wrong answers split 30 and 30; the clean p > 1/2 coin is just the two-outcome special case. This assumes the sampled answers are first normalised to a canonical form, so surface variants of the same answer are counted together, where that is impossible, as in open-ended tasks, plurality voting has little to grip.

Self-consistency is probability amplification rediscovered in a new domain, with one important caveat taken up in the next section: the guarantee depends on the correct answer actually being the model’s most likely one, so the clean exponential decay is a best case rather than a promise. That is not a criticism of the paper; recognising that a practical technique is an instance of a well-understood theorem is exactly what tells you when it will work and when it will not.

The catch complexity theory already flagged

Amplification comes with preconditions, and they are not fine print. They are precisely the conditions under which self-consistency helps or quietly fails.

The correct answer has to be the model’s most likely one. Amplification pushes the vote toward whichever answer carries the most probability mass. If a systematic bias, a shared wrong assumption the training baked in, makes some wrong answer the single most likely one the model emits, plurality voting amplifies that wrong answer with the same exponential confidence. More samples then make you more confidently incorrect, which is worse than a single guess. A shared systematic bias that skews the distribution toward a wrong answer is a distinct failure from statistical dependence, and blurring the two under “correlated errors” hides it.

The bound assumes genuinely independent draws, and it is worth being precise about what that means. Sharing a prompt, weights, and training bias does not by itself make separate samples statistically dependent; fresh decodes at a non-zero temperature can be independent draws from the same, possibly biased, distribution. What a shared bias does is shape that distribution, which is the precondition above. Genuine dependence is something narrower: reused random seeds, shared intermediate state, or adaptive sampling where one draw conditions the next. That is what actually violates the independence the stated bound assumes, and independence is what the theorem uses, not a law of nature. Dependent draws fall outside the bound: no exponential guarantee follows unless you prove a suitable dependence or mixing condition in its place, though the vote itself may still help, stay flat, or even improve under the right kind of dependence. An unfavourable distribution and genuine dependence remain different failures, the first actively amplifies a wrong answer, the second withdraws the guarantee, and the common “correlated errors” shorthand blurs them.

Name those conditions and the behaviour of self-consistency stops being mysterious. It is amplification, so it inherits amplification’s guarantees and amplification’s failure modes.

The cost lens: amplification is not free

Every sample is a full generation. Drawing k samples means roughly k times the tokens of a single answer, and correspondingly more inference compute. That is not the same as k times the latency, independent samples can run in parallel, nor exactly k times the bill, which depends on your pricing mode and any caching. Tokens are the axis that scales cleanly with k; the physical compute behind them shifts with batching, prefix reuse, and serving efficiency, and latency and dollar cost are separate again. This is the token arithmetic the first post in this series worked through: expected token consumption scales roughly linearly with k, and under a token-priced mode that usage is what you are billed for [1].

That reframes self-consistency as a dial, not a default. The error falls exponentially in k when the distribution is favourable, but the token cost rises linearly in k, so the marginal accuracy per extra sample shrinks quickly. When the distribution is favourable, a handful of samples captures most of the available gain; pushing k much higher spends linearly more for exponentially less benefit. The right question is not “should I sample more” but “where on the diminishing-returns curve does another sample stop being worth its tokens.”

If You’re Running This on AWS

Self-consistency is easy to run on Amazon Bedrock: send the same prompt several times at a non-zero temperature and majority-vote the answers. Because the samples are independent requests, they parallelise cleanly, up to your account’s quotas and the model’s limits, and for workloads that can tolerate latency, batch inference can be a better fit than firing many interactive requests. The actual cost difference depends on the pricing mode, so check current Bedrock pricing and batch-inference documentation rather than assuming a saving. The sampling itself is a capability the platform already gives you; the engineering is in choosing k deliberately and voting sensibly.

It also composes with the previous post’s idea, and the choice between them is worth making on purpose. Self-consistency is unsupervised: it needs no checker, just agreement across samples, which makes it easy to apply but blind to a shared systematic bias every sample carries. A verifier can catch a confidently-wrong consensus that voting cannot, at the cost of needing a reliable checker. On Bedrock you can use either or both: vote when a cheap trustworthy check does not exist, verify when it does, and in the hardest cases combine them. As always, whether the extra samples earn their tokens is a measurement question against your accuracy target and your budget.

A thread worth pulling

The pleasure of that first read was recognition. A 2022 paper with strong empirical results turned out to be a clean instance of a theorem from a randomized-algorithms course, which meant the theorem’s fine print was the paper’s fine print too: it works when the correct answer is the model’s most likely one and the draws are independent, and it fails in exactly the ways the bound predicts. That is the recurring move in this series. When a new AI technique looks like magic, it is often an old algorithm wearing new clothes, and reading it that way tells you where its edges are.

So before you crank the sample count on your next hard prompt: is the correct answer actually your model’s most likely single output on this class of problem, and are your draws independent enough for the votes to mean anything? Where do you think the diminishing returns set in for your workloads?

Sources

• [1] Stefan Christoph, “Why AI Tokens Are So Expensive, and What Actually Makes Them Cheaper”, the token arithmetic behind “N samples cost N× the tokens.”
• [2] Motwani and Raghavan, Randomized Algorithms (Cambridge University Press, 1995), the canonical treatment of Monte Carlo algorithms, probability amplification, and Chernoff/Hoeffding concentration bounds.
• [3] Wang et al., “Self-Consistency Improves Chain of Thought Reasoning in Language Models”, 2022 (ICLR 2023); sample diverse reasoning paths and majority-vote, with reported gains including +17.9% on GSM8K.
• [4] Stefan Christoph, “Generate-and-Verify: What P vs NP Teaches Us About AI Reasoning”, the companion post on verifying an answer with a separate checker, the other robustness strategy.

About the Author

Stefan Christoph is a Principal Solutions Architect at AWS, focused on agentic AI, media & entertainment, and helping builders move from demo to production. He writes about AI architecture, developer productivity, and the future of software.

This is a personal blog. Opinions expressed here are my own and do not represent the views or positions of my employer.

Learn more →

• AI
• LLMs
• RandomizedAlgorithms
• Reasoning
• AmazonBedrock