Error Compounding in Agent Trajectories

Per-step reliability raised to the power of the horizon — why 95% per step is a failing agent, and what majority voting does and does not repair.

AgentsAdvanced⏱ 1 hour10 min readagentshorizoncompoundingcondorcetself-consistency

6 problems →

AssumesExpectation, Variance and Conditional Expectation · Concentration Inequalities · Scaling Laws, Fine-Tuning and In-Context Learning

The compounding law

PropositionTrajectory success decays geometrically in the horizon

Let an agent take $n$ steps, each succeeding independently with probability $p$ , where the trajectory succeeds only if every step does. Then

\P(\text{trajectory succeeds}) = p^{\,n},

and achieving a target success rate $T$ requires per-step reliability

p \ \ge\ T^{1/n}.

Assumptions

Independence across steps, and a strict conjunction — no step is recoverable. Both are idealisations, and the second is relaxed below. Independence is the more suspect: a mistaken early step often makes later steps harder, which correlates failures positively and makes the true number worse than $p^n$ , not better.

Voting, and when it works

Sampling a step several times and taking the majority is the standard repair. Its guarantee is classical.

TheoremMajority voting with independent votes

Let $V_1,\dots,V_k$ be independent indicators of a correct vote, each with $\P(V_i = 1) = p > 1/2$ , and let the decision be the majority. Then

\P(\text{majority incorrect}) \ \le\ \exp\!\left(-2k\left(p-\tfrac12\right)^2\right),

which tends to $0$ as $k\to\infty$ .

Key idea

The exponent contains $(p - \tfrac12)^2$ . At $p = 0.8$ the bound decays like $e^{-0.18k}$ — about 26 votes to reach 99%. At $p = 0.55$ it decays like $e^{-0.005k}$ , needing over 900. Voting rescues a step that is reliably better than chance; it barely touches one that is marginal, and for $p < 1/2$ it drives confidently to the wrong answer.

Why it usually helps less than that

PropositionCorrelated votes destroy the guarantee

Suppose the votes are generated as $V_i = Z$ for a single Bernoulli $(p)$ variable $Z$ — perfectly correlated. Then for every odd $k$ ,

\P(\text{majority correct}) = p ,

independent of $k$ .

Common mistake

This degenerate case is not far from reality. Repeated samples from one model at moderate temperature share the model's systematic misconceptions: if the model has misread the problem, all $k$ samples misread it the same way. Independence is the assumption the theorem needs and the assumption sampling does not supply.

What the evidence shows is that self-consistency does help on tasks with many distinct valid reasoning paths converging on one answer — arithmetic and multi-step reasoning — and helps much less where the failure is a shared misunderstanding. The effective number of independent votes is smaller than $k$ , sometimes very much smaller, and the honest way to use the theorem is as an upper bound on the benefit. Diversity across different models or prompts recovers some genuine independence, which is why ensembles of unlike models outperform repeated samples of one.

Recovery changes the exponent

The compounding law assumed a step failure is terminal. Agents that can notice a failure and retry are playing a different game.

PropositionDetect-and-retry raises the effective step reliability

Suppose a step succeeds with probability $p$ ; on failure it is detected with probability $d$ ; and a detected failure is retried, independently, up to $m$ times. Then the effective per-step success probability is

p_{\mathrm{eff}} = 1 - (1-p)\,(1-dp)^{m}.

What this does not say

Every model on this page assumes independence somewhere — across steps, across votes, across retries. Real agent trajectories violate all three, generally in the unfavourable direction: a confused agent stays confused, and its self-check is performed by the same confused model. Use these formulas to set expectations and to compare designs, not to predict a deployment's success rate. The measured quantity that matters, and that none of this derives, is the correlation structure of an agent's errors along a trajectory.

Open problem

Open problem — no proof and no counterexample is known to the author of this page.

No accepted model predicts an agent's end-to-end success rate from measurable properties of its base model and its tool environment. The compounding law gives the right qualitative shape and is quantitatively wrong because of the correlations it ignores; there is no established way to estimate an effective horizon or an effective independent-vote count in advance.

Results stated on this page

PropositionTrajectory success decays geometrically in the horizonproof includedUnder independent steps with success probability p, an n-step trajectory succeeds with probability pⁿ, so the per-step bar for a target T is T^(1/n).
TheoremMajority voting with independent votesproof includedFor k independent votes each correct with probability p > 1/2, the majority is wrong with probability at most exp(−2k(p−1/2)²).
PropositionCorrelated votes destroy the guaranteeproof includedWith perfectly correlated errors the majority is exactly as reliable as a single sample, however large k is.
PropositionDetect-and-retry raises the effective step reliabilityproof includedWith detection probability d and m retries, effective per-step success rises to 1 − (1−p)(1−dp)^m under the stated independence.

Problems (6)

All problems