Loop Reliability Algebra
Abstract
Fix a DOER/CHECKER loop with a noisy gate (PRR-2026-013): at an uncertified state the gate false-passes with rate α and delivers a wrong exit; at a certified state it false-fails with rate β and merely re-iterates. We study the single lever left free: whether the gate's verdict at a state is drawn fresh every visit or cached (drawn once, reused). (i) Caching is a monotone safety/liveness control. Under the hypothesis that the DOER never returns to a certified state, caching weakly lowers the wrong-exit probability, tight against a self-looping certified counterexample; and along the full lattice of resampling schedules the wrong-exit probability obeys a universal sandwich between the all-cached and all-fresh extremes, while the termination time is pathwise dominated the opposite way, with no hypothesis. (ii) For a memoryless DOER the loop is rejection sampling: the probability of a correct delivery equals the single-step accept-flux ratio and is independent of the iteration count — the loop amplifies no correctness on its own; correctness amplification requires the DOER to condition on the gate's rejection. Under a persistently false-passing fresh gate (false-pass rate bounded below on the states it revisits), a DOER that never certifies delivers a wrong answer with probability one. (iii) Caching a stochastic acceptance verdict biases the sampled law to π_quench ∝ q·a·g for an explicit reweight g; in the rare-acceptance limit the delivered law converges to the acceptance profile ∝ a, forgetting the proposal entirely, and in the frequent-acceptance limit it recovers the target. (iv) The bias is correctable from the loop's own traces by importance weighting, but not from a single run, and never for free: no scheme is at once unbiased, evaluation-saving, and correction-free, the correction cost being exactly a chi-squared divergence that grows with the same acceptance-rarity that produced the bias.
Keywords. DOER/CHECKER loops; verdict caching; quenched and fresh sampling; rejection sampling; error amplification; importance sampling; identifiability; no-free-lunch
1. Introduction
PRR-2026-013 established that a noisy gate turns a loop into an error-amplifier: iteration hands the gate repeated chances to fail. That paper drew each verdict fresh. But a real loop that consults an expensive checker will often cache a verdict — evaluate a candidate once, and on a later encounter reuse the recorded answer rather than pay for it again. This is not a detail of implementation; it is a mathematical choice that changes what the loop delivers, along three axes at once — how safe the loop is, whether it terminates, and what distribution it returns. This paper fixes the DOER and the gate and studies exactly that choice.
The three axes turn out to be governed by a small number of exact facts. Caching is a monotone safety/liveness dial (§3). The loop, stripped to a memoryless proposer, is rejection sampling, and therefore amplifies no correctness by iteration alone (§4). Caching a stochastic verdict biases the delivered sample by an explicit factor, severely so when acceptance is rare (§5). And that bias is correctable, but only from many runs and never without paying a variance cost tied to the bias itself (§6).
2. Preliminaries
Shared with PRR-2026-012/013, unmodified: the semantic domain S, the concrete inference operators C (Markov kernels), the certification family F of a finite-image closure operator (PRR-2026-006 §4), the loop Λ(δ, g) of a DOER δ ∈ C under a gate g, and the two error rates of a noisy gate (PRR-2026-013 Definition 3.2): false-pass α(x) at x ∉ F, false-fail β(x) at x ∈ F. A run visits states, invoking the gate at each; a pass exits at the current state (a wrong exit if the state is uncertified), a fail invokes the DOER and continues. Write W for the probability of a wrong exit (the safety failure) and the loop's non-termination mass for the liveness failure.
A resampling schedule R assigns to each state x a set of visit-indices R(x) ⊆ {1, 2, …}, with 1 ∈ R(x), at which the gate's verdict at x is drawn afresh; at visits not in R(x) the most recent draw is reused. Fresh is R(x) = {1, 2, …} (redraw every visit); sticky (fully cached) is R(x) = {1} (draw once, reuse forever). Order schedules by inclusion: R′ ⊑ R iff R′(x) ⊆ R(x) for all x — R′ caches at least as much. Thus sticky ⊑ R ⊑ fresh for every R.
3. Caching Is a Monotone Safety/Liveness Control
We first fix the DOER's dynamics and vary only the resampling schedule. One structural hypothesis is decisive.
The DOER's dynamics never return to a certified state: every z ∈ F is visited at most once along any trajectory (equivalently, all recurrence is confined to S ∖ F).
Under (H), the sticky loop's wrong-exit probability is no larger than the fresh loop's: W_sticky ≤ W_fresh, for every start. The hypothesis is tight: with a revisited certified state the inequality can strictly reverse.
Proof. Couple both regimes on one probability space: for each state x and visit index k let B(x, k) be independent Bernoulli verdicts of the correct rate, let sticky's frozen verdict be V(x) = B(x, 1), and share the DOER transitions. A pass exits, so a state is revisited only after a fail; thus the two runs agree until the first revisit at which fresh draws a pass while sticky (holding its frozen fail) continues — at that revisit fresh exits and its run ends. A revisited state is, under (H), uncertified, so every such divergence is a fresh wrong exit. Hence if sticky wrong-exits (at its first uncertified first-visit pass) then fresh has already wrong-exited or wrong-exits at the same step: {sticky wrong} ⊆ {fresh wrong} on the coupled space, giving W_sticky ≤ W_fresh. ∎Tightness — a self-looping certified state reverses it
Let c ∈ F self-loop: on false-fail (rate β) go c → c with probability s and c → u with probability 1 − s, where at u ∉ F a wrong exit has rate α (else a safe sink). Then
W_fresh = β(1 − s)α / (1 − βs) W_sticky = βα W_sticky − W_fresh = βα · s(1 − β) / (1 − βs) >
0 (e.g. β = α = ½, s = 0.8: W_sticky = 0.25 vs W_fresh ≈ 0.083)
Here caching is strictly worse for safety, and the only failed hypothesis is (H): the certified state c is revisited.
Under (H), if R′ ⊑ R then W(R′) ≤ W(R): caching more is weakly safer, monotonically along the whole inclusion order. In particular W_sticky ≤ W(R) ≤ W_fresh for every schedule R. Dually and without any hypothesis, the finer (less-cached) schedule terminates no later: for R′ ⊑ R the termination times satisfy τ_R ≤ τ_{R′} pathwise, so caching more weakly increases both non-termination probability and expected iterations.
Proof. The same coupling. Since R′(x) ⊆ R(x), the only asymmetry at a visit is that R may draw a fresh Bernoulli where R′ reuses an earlier one — and a reused verdict is necessarily a fail (a pass would have exited when drawn). Every divergence is therefore an R-exit on a revisit; under (H) that revisited state is uncertified, so it is an R wrong-exit, giving {R′ wrong} ⊆ {R wrong} and W(R′) ≤ W(R). The liveness half needs no (H): reuse never causes an exit, so R exits (correctly or not) no later than R′ on every path, hence τ_R ≤ τ_{R′}. ∎4. The Loop Is Rejection Sampling
Set caching aside and ask the bluntest question: does iterating a loop make it deliver correctly? For a memoryless DOER the answer is exact and negative.
Each iteration the DOER emits an independent candidate, correct with probability p and incorrect with probability 1 − p. The gate passes a correct candidate (correct exit) with probability 1 − β and fails it with probability β; it passes an incorrect candidate (wrong exit) with probability α and fails it with probability 1 − α. A fail re-iterates.
The loop terminates almost surely whenever p(1 − β) + (1 − p)α > 0, and the probability of a correct delivery is
C = p(1 − β) / [ p(1 − β) + (1 − p)α ] = 1 / (1 + ρ), ρ = (1 − p)α / [ p(1 − β) ],
independent of the number of iterations. The loop is exactly rejection sampling: the delivered candidate is the proposal conditioned on acceptance, so C = P(correct | accepted). Iteration buys termination, not correctness.
Proof. The per-iteration exit fluxes are p(1 − β) (correct) and (1 − p)α (wrong), the rest re-iterating; by the geometric/renewal sum the outcome conditioned on exit is the ratio of these fluxes, which carries no dependence on the iteration index. Bayes' rule identifies it with P(correct | accepted). ∎As the DOER degrades, p → 0 gives C → 0 and W → 1. More strongly, under a fresh gate, if the DOER never certifies and revisits uncertified states with false-pass rate bounded below by α_min > 0 infinitely often, then a false-pass occurs almost surely and W = 1: the loop is certain to deliver a wrong answer. Caching caps this — with N distinct reachable uncertified candidates of false-pass at most α_max < 1, W ≤ 1 − (1 − α_max)^N < 1.
Proof. The first claim is the p → 0 limit of Proposition 4.2. The second is the second Borel–Cantelli lemma: independent false-pass trials with divergent probability sum yield a pass with probability one. The cap holds because a cached rejected candidate is never re-accepted, so each of the N candidates gets one false-pass chance. ∎For a fixed imperfect memoryless DOER (p < 1, α > 0), C is pinned below 1 by Proposition 4.2 regardless of iteration count; raising C toward 1 requires changing the proposal distribution — statically a better proposer, or, the only route available mid-loop, the DOER conditioning on the gate's fail to propose a better next candidate. If the DOER eventually proposes a certifiable candidate, correct delivery is bounded below by C ≥ 1 − Σ_n (false-accept flux at iteration n), a union bound over the pre-success iterations. Both a competent proposer and small pre-success false-accept exposure are necessary.
5. Quenched Rejection Sampling — the Sampling Bias of a Cached Verdict
Sections 3 and 4 meet here. A rejection loop whose stochastic acceptance verdict is cached per candidate value does not sample its intended target.
Fix a finite domain, a proposal q(x), and a stochastic acceptance probability a(x) ∈ (0, 1). Standard (annealed) rejection sampling redraws a(x) on every proposal of x; its output law is π_std(x) = q(x)a(x) / Σ_y q(y)a(y). Quenched rejection sampling freezes a set A (each x ∈ A independently with probability a(x)), then proposes x ∼ q and accepts iff x ∈ A; its output is q restricted to A, conditioned on A ≠ ∅.
The quenched output law is
π_quench(x) ∝ q(x) · a(x) · g(x), g(x) = E_{A₋ₓ}[ 1 / (q(x) + q(A₋ₓ)) ],
where the expectation is over freezes A₋ₓ of the other points (each y ≠ x included with probability a(y)). Thus π_quench is π_std reweighted by g(x), and g(x) does not depend on a(x).
Proof. For a nonempty freeze A the output is q(x)𝟙[x ∈ A] / q(A). Averaging, the contribution of x is q(x) · P(x ∈ A) · E[1/q(A) | x ∈ A]; P(x ∈ A) = a(x), and given x ∈ A the normalizer is q(x) + q(A₋ₓ). ∎Let a(x) = ε·c(x) with c fixed and ε → 0. Then π_quench(x) → c(x) / Σ_y c(y) = a(x) / Σ_y a(y): the quenched sampler converges to a law proportional to the acceptance probability alone, independent of the proposal q.
Proof (two routes). As ε → 0, P(A₋ₓ = ∅) → 1, so g(x) → 1/q(x) and π_quench(x) ∝ q(x)a(x)/q(x) = a(x). Equivalently, conditioned on termination the freeze has a single accepted point almost surely for small ε, and P(x is the lone survivor ) = a(x)∏_{y≠x}(1 − a(y)) ≈ a(x). ∎Worked instance — a 90/10 proposal delivered 50/50
Two points, q = (0.9, 0.1), equal acceptance a(1) = a(2) = ε. Exactly, π_quench(1) = [εq₁ + (1 − ε)] / (2 − ε) → ½, whereas π_std(1) = q₁ = 0.9. Caching drags the delivered law from (0.9, 0.1) to (½, ½), discarding the proposal.
If min_x a(x) → 1 then g(x) → 1 and π_quench → π_std.
Proof. Then A₋ₓ → all other points, so q(x) + q(A₋ₓ) → 1 and the reweight vanishes. ∎g(x) is strictly decreasing in q(x) (holding the others fixed), so quenching moves mass from high-proposal toward low-proposal "lone-survivor" points. Whether this sharpens or flattens π_std depends on the correlation between q and a; it is not universal. For q = (0.6, 0.2, 0.2), a = (0.5, 0.9, 0.1) the quenched law flips the mode of π_std and raises its entropy.
Proof. For each fixed A₋ₓ, 1/(q(x) + q(A₋ₓ)) is strictly decreasing in q(x), and the averaging weights do not depend on q(x); a fixed-weight average of strictly decreasing functions is strictly decreasing. The three-point figures are a direct computation. ∎6. Debiasing — a Trilemma
Caching a verdict is a genuine speedup: a candidate is evaluated at most once per run. The bias of §5 is the price. It is correctable — but the correction has an exact structure.
Run M independent cached runs, logging for each the frozen verdict of every candidate it proposed and its delivered sample. Estimate q̂ (proposal frequency) and â(x) (accept fraction among runs that proposed x), form ĝ by plugging q̂, â into g, and report expectations under π_std by self-normalized importance sampling with weights w(x) = 1/ĝ(x). This estimator is consistent for π_std and uses no verdict evaluations beyond the runs themselves.
Proof. The exact importance weight is π_std/π_quench ∝ 1/g. Each run is an independent freeze, so â(x) is a mean of i.i.d. Bernoulli(a(x)) outcomes; it is unbiased provided x's verdict is recorded in every run that proposes x, delivering or not (cap non-terminating freezes) — observation of x is independent of x's verdict because x's first-proposal slot and the first-other-acceptance slot are never equal, whereas restricting to delivered runs conditions on termination and biases â upward. Then ĝ → g and self-normalized importance sampling with a consistent weight is consistent. ∎From one cached run the correction is unidentifiable: each candidate yields a single Bernoulli outcome, but g(x) is a nonlinear function of the acceptance probabilities, which one bit cannot determine. Debiasing intrinsically requires many independent freezes.
No scheme is simultaneously (i) unbiased for π_std, (ii) evaluation-saving, and (iii) correction-free — one may have any two. Only fresh evaluation is strictly unbiased with no correction, and it forgoes the speedup; any caching biases the output (§5), and the correction of Proposition 6.1 costs importance-weight variance equal, exactly, to
CV²(w) = ḡ · E_{π_std}[1/g] − 1 = χ²(π_std ‖ π_quench), ḡ = E_{π_std}[g],
which is ≥ 0 by Jensen, = 0 iff g is constant (frequent acceptance, Theorem 5.4), and diverges as the reweight g ≈ 1/q spreads under rare acceptance (Theorem 5.3). The regime in which caching saves the most evaluations — a strict gate forcing many re-proposals — is exactly the regime of largest bias and largest correction cost.
Proof. Sampling from π_quench with weight 1/g and π_quench = π_std · g/ḡ gives E_{π_quench}[1/g] = 1/ḡ and E_{π_quench}[1/g²] = E_{π_std}[1/g]/ḡ, so CV² = ḡ·E_{π_std}[1/g] − 1, which equals Σ_x π_std(x)²/π_quench(x) − 1 = χ²(π_std ‖ π_quench). The (i)/(ii)/(iii) exclusion is immediate: (ii)∧¬(iii) reuses a frozen verdict, hence biases; (i)∧(ii) is Proposition 6.1, which is a correction. ∎7. Discussion and Conclusion
One lever — whether a checker's verdict is drawn fresh or reused — controls a loop along three independent axes. It is a monotone safety/liveness dial (§3): under the no-return hypothesis, more caching is weakly safer and, unconditionally, weakly slower, with a universal sandwich between the extremes. It does not create correctness (§4): a memoryless loop is rejection sampling and realizes a fixed accept ratio, so amplification lives entirely in the DOER's use of the checker's rejections, and patience under a fresh false-passing gate is actively fatal. It distorts the delivered distribution (§5): caching a stochastic verdict biases the sample by an explicit reweight, discarding the proposal entirely in the rare-acceptance limit. And that distortion is correctable from the loop's own traces (§6), but not from one run, and only by paying a chi-squared cost that tracks the bias — a genuine trilemma among unbiasedness, evaluation-saving, and correction-freedom.
The DOER earned its algebra in PRR-2026-012 and its error theory in PRR-2026-013; here its reliability — safety, liveness, and sampling fidelity — is priced against the single choice of how a verdict is reused.
References
Edwards, R. (2026). Concrete Inferential Algebra. Perspectivity Research Reports, Vol. 1, No. 3, PRR-2026-003.
Edwards, R. (2026). Reasoning Dynamics Algebra. Perspectivity Research Reports, Vol. 1, No. 6, PRR-2026-006.
Edwards, R. (2026). Concrete Loop Algebra. Perspectivity Research Reports, Vol. 1, No. 12, PRR-2026-012.
Edwards, R. (2026). Noisy Gate Algebra. Perspectivity Research Reports, Vol. 1, No. 13, PRR-2026-013.
Andrieu, C., & Roberts, G. O. (2009). The pseudo-marginal approach for efficient Monte Carlo computations. Annals of Statistics, 37(2), 697–725.
Beaumont, M. A. (2003). Estimation of population growth or decline in genetically monitored populations. Genetics, 164(3), 1139–1160.
Kong, A. (1992). A note on importance sampling using standardized weights. Technical Report 348, Department of Statistics, University of Chicago.
Strassen, V. (1965). The existence of probability measures with given marginals. Annals of Mathematical Statistics, 36(2), 423–439.
Peer Review
Every claim is proved or computed in place. The coupling arguments of §3 are checked to the point of the hypothesis that makes them tight — the self-looping counterexample is the right one, and the liveness half is correctly identified as hypothesis-free. The rejection-sampling identity in §4 is stated with the exact accept-ratio and its iteration-independence, and the "patience is dangerous" corollary invokes the correct (independence) Borel–Cantelli. Recommend acceptance.
The quenched-sampling law and its two limits are the paper's most quantitative content, and the rare-acceptance limit — the delivered law converging to the acceptance profile, forgetting the proposal — is both exact and surprising. The debiasing trilemma of §6 is the right closing note: a constructive correction, an identifiability floor, and an exact chi-squared cost that ties the correction back to the very bias it removes. The importance-sampling variance is stated in the correct divergence direction. Recommend acceptance.