There’s a fundamental paradox at the heart of LLM reliability: no matter how sophisticated your self-refinement loop is, if the model can occasionally declare a wrong answer as correct, failure is inevitable. It’s not about prompting strategies or chain-of-thought reasoning—it’s a mathematical certainty baked into the structure of the problem. This post explores why single-path refinement is doomed to fail and how a surprisingly simple solution—running multiple paths in parallel and checking for consensus—can provide provable reliability guarantees.

The Termination Problem

Consider a self-refinement loop where an LLM iteratively improves its answer. At each step, the model must decide: is this answer correct? If yes, terminate; if no, keep refining. The critical insight is that the model’s decision is itself fallible. It can:

• False Terminate: Declare an incorrect answer as correct and stop.
• Over-Refine: Declare a correct answer as incorrect and continue (potentially introducing new errors).

Both failure modes are empirically observed, and neither can be eliminated completely without an external oracle. This sets up a race condition between error correction and premature termination.

Formalizing the Refinement Loop

To understand why failure is inevitable, we can model the refinement process as a Markov chain. Let’s define a few key quantities:

• $p_{EC}$: The probability of correcting an erroneous output in one refinement step.
• $\alpha$: The probability of terminating when the output is correct (true positive rate).
• $\beta$: The probability of terminating when the output is incorrect (false positive rate—the critical failure mode).

The refinement loop can be represented as an absorbing Markov chain with four states: correct and continuing ($C$), erroneous and continuing ($E$), terminated correctly ($T_C$), and terminated incorrectly ($T_E$). The last two are absorbing states—once you enter them, you never leave.

The one-step transition matrix $\mathbf{P}$ captures the dynamics:

$$\mathbf{P} = \begin{pmatrix} (1-\alpha)p_{CC} & (1-\alpha)p_{CE} & \alpha & 0 \\ (1-\beta)p_{EC} & (1-\beta)p_{EE} & 0 & \beta \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

The structure of this matrix reveals the inevitability of failure.

The Impossibility Theorem: A Concrete Lower Bound

As long as $\beta > 0$, the probability of eventually being absorbed into the wrong termination state is not just positive—we can derive an explicit lower bound.

Theorem (Single-Path Error Floor): Starting from an erroneous state $E$, the probability of incorrect termination satisfies:

$$\Pr[\text{absorb into } T_E \mid X_0 = E] \geq \frac{\beta}{\beta + (1-\beta)p_{EC} \cdot \frac{\alpha}{1 - (1-\alpha)p_{CC}}}$$

In the limit where refinement is perfect ($p_{EC} \to 1$) and the model never damages correct answers ($p_{CC} = 1$), this simplifies to:

$$\Pr[\text{absorb into } T_E \mid X_0 = E] \geq \frac{\beta}{\beta + \alpha(1-\beta)}$$

Example: With $\alpha = 0.9$ (90% true positive rate) and $\beta = 0.1$ (10% false positive rate), even with perfect refinement, the failure probability is bounded below by:

$$\frac{0.1}{0.1 + 0.9 \cdot 0.9} = \frac{0.1}{0.91} \approx 11\%$$

No amount of refinement iterations can push the error rate below this floor. The key insight is that from the erroneous state, there’s a race between “correct the error and then terminate correctly” versus “terminate incorrectly right now.” The absorbing nature of $T_E$ means that once you lose this race, you can never recover.

The Convergence Rate Distinction

You might object: “But consensus also has strictly positive failure probability!” True—but the crucial difference is the rate of convergence to zero.

Single-path refinement has a failure probability that converges to a constant floor as the number of iterations $n \to \infty$:

$$\lim_{n \to \infty} \Pr[\text{failure after } n \text{ iterations}] = \Pr[\text{absorb into } T_E] \geq \frac{\beta}{\beta + \alpha(1-\beta)} > 0$$

This floor is determined by the system parameters and cannot be improved by running longer. More iterations just means you’re more certain to hit the floor.

Parallel consensus has a failure probability that converges to zero exponentially in the number of paths $K$:

$$\Pr[\text{incorrect consensus}] \leq \exp\left(-2K(p - 1/2)^2\right) \xrightarrow{K \to \infty} 0$$

The rate of decay is $\Theta(K)$ in the exponent—doubling $K$ squares the reliability. This is the fundamental qualitative difference: single-path strategies hit a wall; consensus breaks through it.

The Parallel Consensus Protocol

Having established that single-path refinement is doomed, we now construct a protocol that circumvents this limitation. The key insight is a fundamental asymmetry:

Correctness is a unique attractor; errors are dispersed.

When paths “get it right,” they all converge to the same answer (or semantically equivalent ones). When paths “get it wrong,” they typically produce different wrong answers—different reasoning mistakes, different hallucinations, different numerical errors. Consensus exploits this asymmetry.

The Parallel Consensus Protocol works as follows:

1. Parallel Refinement: Launch $K$ independent refinement paths, each executing the same refinement loop until termination.
2. Output Collection: Collect the final outputs $\{o_1, \ldots, o_K\}$ from each path.
3. Consensus Decision: If a majority of paths agree on the same output $o^*$, return $o^*$. Otherwise, report “No Consensus.”

Quantitative Reliability Bounds

Let each path independently produce a correct output with probability $p$ and an incorrect output with probability $q = 1 - p$. If $p > 1/2$—the model is more often right than wrong—then majority voting over $K$ paths achieves remarkable reliability.

Theorem (Reliability Bound via Majority Vote): Using majority vote over $K$ paths, the probability of incorrect consensus is bounded by Hoeffding’s inequality:

$$\Pr[\text{Incorrect Majority}] \leq \exp\left(-2K(p - 1/2)^2\right)$$

This probability decays exponentially in $K$! To achieve failure probability at most $\varepsilon$, we need:

$$K \geq \frac{\ln(1/\varepsilon)}{2(p - 1/2)^2}$$

Example: If each path has $p = 0.9$ (90% accuracy), achieving one-in-a-million failure ($\varepsilon = 10^{-6}$) requires:

$$K \geq \frac{\ln(10^6)}{2(0.4)^2} = \frac{13.8}{0.32} \approx 43$$

Just 43 parallel paths suffice for million-to-one reliability!

The Entropy Amplification Effect

The analysis above treats all incorrect outputs as equivalent. In reality, the error space is vast—and this helps the consensus protocol enormously.

Let $\pi(s)$ be the distribution over incorrect outputs. The probability that $K$ independent incorrect paths all produce the same wrong answer is:

$$\Pr[\text{unanimous incorrect agreement}] = \sum_{s \in \mathcal{E}} \pi(s)^K$$

If errors are uniformly distributed over $\vert\mathcal{E}\vert$ possible incorrect outputs:

$$\Pr[\text{unanimous incorrect agreement}] = \frac{1}{\vert\mathcal{E}\vert^{K-1}}$$

This decays exponentially in both $K$ and the size of the error space!

Example: For a math problem where the correct answer is a specific integer and wrong answers are uniformly distributed over $10^6$ possible values:

$$\Pr[\text{3 paths agree on same wrong answer}] = \frac{1}{(10^6)^2} = 10^{-12}$$

Even with just 3 paths, unanimous incorrect agreement is astronomically unlikely.

The Complete Picture

Combining per-path error rates with the entropy effect yields the full failure bound:

$$\Pr[\text{incorrect consensus}] \leq q^K \cdot \vert\mathcal{E}\vert^{1-K}$$

This reveals a striking result: even if $q > 1/2$ (the model is more often wrong than right!), consensus can still be reliable if the error space is large. The entropy of the error distribution provides a powerful “second line of defense.”

Practical Guidelines

For system designers deploying reliable LLM systems:

Target $\varepsilon$	$p = 0.7$	$p = 0.8$	$p = 0.9$
$10^{-3}$ (0.1%)	87	39	10
$10^{-6}$ (one in a million)	173	77	19
$10^{-9}$ (one in a billion)	259	116	29

Table: Required number of parallel paths $K$ for target failure probability $\varepsilon$.

The table uses the Hoeffding bound, which is conservative. In practice, the entropy factor can reduce the required $K$ substantially for problems with large error spaces.

Connection to Information Theory

This framework has a beautiful interpretation in information-theoretic terms. The LLM refinement loop is essentially a noisy channel that with probability $p$ transmits the correct answer and with probability $q$ transmits noise. The Parallel Consensus Protocol is a repetition code of rate $1/K$.

Shannon’s noisy-channel coding theorem states that reliable communication is possible if and only if the channel capacity is positive—which for a binary symmetric channel requires $q < 1/2$, or equivalently $p > 1/2$. Our results are direct consequences of this classical insight.

The condition $p > 1/2$ is not just sufficient—it is necessary for majority-vote consensus to provide asymptotic reliability. Below this threshold, adding more paths actually makes things worse.

Conclusion

The mathematics is unambiguous: single-path self-refinement cannot provide reliability guarantees. Any system with non-zero false-termination rate will eventually fail—this is not a matter of prompting or model quality, but a structural property of absorbing Markov chains.

The Parallel Consensus Protocol offers a principled escape. By exploiting the asymmetry between the unique correct answer and the dispersed space of errors, it achieves arbitrarily low failure probability with a calculable number of parallel paths. The entropy of the error space provides additional protection, making unanimous incorrect consensus exponentially unlikely.

For practitioners deploying LLMs in high-stakes applications, these results provide concrete engineering guidance: estimate your per-path accuracy, choose your target reliability, compute the required parallelism, and build systems accordingly.