Inexact contraction — convergence with a fallible executor

Parent: analysis

Exact Banach iteration assumes each step is performed perfectly; what happens when every step is executed by a fallible solver with error up to $\varepsilon$? Answer: you still converge — but to a ball of radius $\varepsilon/(1-k)$, not to the point.

Contraction

Let $(X, d)$ be a metric space and $T : X \to X$ a map. We call T a contraction with factor k if there exists $0 \le k < 1$ such that

$$d(Tx, Ty) \le k \, d(x, y) \quad \text{for all } x, y \in X.$$

Banach's fixed-point theorem: T has a unique fixed point $x^* = Tx^*$, and the exact iterates $x_{n+1} = T(x_n)$ converge geometrically to $x^*$ from any starting point $x_0$:

$$d(x_n, x^*) \le k^n d(x_0, x^*).$$

Inexact iteration

An inexact iteration is a sequence $(x_n)$ with the property that

$$d(x_{n+1}, T(x_n)) \le \varepsilon$$

for all n — each step lands within $\varepsilon$ of where T would have put it. The true contraction T is not called; instead, a fallible executor (e.g., an LLM, an approximate solver) produces $x_{n+1}$ subject only to this distance constraint.

Inexact contraction

Let $(x_n)$ be an inexact iteration under contraction T with factor k < 1 and fixed point $x^*$. Then:

$$d(x_n, x^*) \;\le\; k^n d(x_0, x^*) + \varepsilon \, \frac{1-k^n}{1-k}.$$

As $n \to \infty$, the iterates converge to the ball around $x^*$ of radius $\frac{\varepsilon}{1-k}$:

$$\limsup_{n \to \infty} d(x_n, x^*) \;\le\; \frac{\varepsilon}{1-k}.$$

Proof

One step: Apply the triangle inequality and the contraction property to $x_{n+1}$:

$$d(x_{n+1}, x^*) \le d(x_{n+1}, T x_n) + d(T x_n, T x^*) \le \varepsilon + k \, d(x_n, x^*).$$

Unroll the recurrence: Starting from $d(x_0, x^*)$ and applying the one-step bound $n$ times:

$$d(x_n, x^*) \le k \, d(x_{n-1}, x^*) + \varepsilon \le k(k \, d(x_{n-2}, x^*) + \varepsilon) + \varepsilon = k^2 d(x_{n-2}, x^*) + k\varepsilon + \varepsilon \le \cdots$$

Continuing all the way:

$$d(x_n, x^*) \le k^n d(x_0, x^*) + \varepsilon(1 + k + k^2 + \cdots + k^{n-1}) = k^n d(x_0, x^*) + \varepsilon \, \frac{1-k^n}{1-k}.$$

The first term decays geometrically to 0. The second term increases toward $\frac{\varepsilon}{1-k}$ as $n \to \infty$. Since $0 < k < 1$ we have $1 - k^n \to 1$, so $\limsup_{n \to \infty} d(x_n, x^*) \le \frac{\varepsilon}{1-k}$. ∎

Worked trace: halving with constant error

Let $X = \mathbb{R}$, $T(x) = x/2$, so k = 1/2 and the fixed point is $x^* = 0$. Assume worst-case error $\varepsilon = 0.1$ per step — that is, $x_{n+1} = x_n/2 + 0.1$, starting at $x_0 = 1$. By the theorem, the limit ball has radius $\frac{0.1}{1 - 0.5} = \frac{0.1}{0.5} = 0.2$.

The iterates descend from 1.0 toward the limit ball 0.2 = $\frac{\varepsilon}{1-k}$, settling exactly on the guaranteed ceiling predicted by the theorem.

Reading it — the harness translation

In a convergent loop that searches for a fixed point:

• T = one verified step of the loop body (a function that provably steps closer to the goal);
• k = the verification quality — the contraction factor from recursion-convergence-contraction, the measure of how much progress each verified step guarantees;
• $\varepsilon$ = the per-step error of a fallible executor, e.g. an LLM used as the theory solver;
• $\frac{\varepsilon}{1-k}$ = the permanent sloppiness floor — the final ε-neighborhood of the goal, the ball of allowable tolerance, an instance of tolerance by design.

The amplification factor $\frac{1}{1-k}$ is crucial: as k approaches 1 (weak verification, barely contracting), the same per-step sloppiness $\varepsilon$ blows up catastrophically in the limit. For example, at k = 0.9, each unit of $\varepsilon$ becomes 10 units of final error; at k = 0.99 it becomes 100.

The toxicity of non-contraction

Without contraction — that is, if k ≥ 1 — the same one-step recurrence gives only

errors accumulate linearly and never settle. Worse, if k > 1 the error grows exponentially. So softening every step (allowing up to $\varepsilon$ error) is safe only when paired with strong contraction. Tolerance without contraction is drift: you have bought nothing but permission to fail systematically. See kleene-fixed-point for the order-theoretic exact cousin of Banach contraction.