Odds Law: The Decomposition Algebra
January 01, 1970
Abstract
We ask a structural question: given unreliable elementary problem-solvers, what organizations of them solve hard problems reliably, and what are the limits? We develop a decomposition algebra: elementary solvers are morphisms in a Markov (stochastic) category, and four combinators (sequential composition, parallel ensembling, verification gating, and recursive reduction) generate the space of compound solvers. We equip this algebra with two homomorphisms, a reliability valuation into the ordered monoid \(([0,1],\le)\) and a cost valuation into a commutative semiring, and we derive the composition laws that govern how reliability flows through structure. Our central results are (i) a verification odds law (the result that names this report), showing that a verification gate multiplies the odds of correctness by the verifier’s likelihood ratio \(\Lambda\), so that \(k\) conditionally independent gates yield geometric amplification; (ii) a reliability amplification theorem, giving target reliability \(1-\delta\) at \(O(\log 1/\delta)\) verification depth whenever \(\Lambda>1\); and (iii) a threshold dichotomy: above the critical parameters (\(\Lambda^\star=1\) for verification, \(p^\star=\tfrac12\) for majority voting) reliability can be driven arbitrarily close to one at logarithmic cost, while at or below them no amplification is possible. We then show that self-organization (the spontaneous appearance of layered, verifier-saturated structure) is the least fixed point of a monotone improvement operator on the complete lattice of strategies, and that this fixed point equalizes marginal log-odds gain per unit cost (a water-filling characterization). Finally, we prove matching limits: an information ceiling bounds per-gate amplification by a divergence quantity; shared error causes create a strictly positive voting floor (we characterize exactly when), so diversity is necessary for unbounded amplification; and a no-free-lunch corollary shows that, averaged over all problem families, no decomposition beats its base solver. Reliability, in short, is neither free nor magical: it is bought with independent information, arranged by composition, and bounded by the verifier. These results form Odds Law, the theory layer of a two-part program (Theory: Odds Law \(\rightarrow\) Framework: Maestro Order); the companion report builds the Maestro Order harness on these laws.
1 Introduction↩︎
A single attempt at a hard problem is rarely trustworthy. Yet collections of unreliable attempts, suitably organized, can be made arbitrarily trustworthy; this is the everyday experience of science, engineering, bureaucracy, and biological computation. Von Neumann’s classical question, how to build a reliable organism (or automaton) from unreliable components [1], is the same question one asks of a research group, a compiler with its test suite, or an ensemble of fallible reasoners. The components differ; the organizing principle may not.
This paper takes that organizing principle as its object of study. We fix a population of elementary problem-solvers (each a randomized map from problem instances to candidate answers, and each only partly reliable) and ask which compositions of them are reliable, at what cost, and against what fundamental limits. We deliberately abstract away the internals of a solver (whether it is a person, a heuristic, a learned model, or an exact algorithm) and study only the calculus by which solvers are combined. The thesis is that reliable problem-solving is a property of structure, and that this structure obeys algebraic laws.
1.0.0.1 The four combinators.
Empirically, intelligent systems combine solvers in a small number of recurring ways. They decompose a problem into ordered subproblems and solve them in sequence (planning, proofs, pipelines). They run several attempts and aggregate (committees, juries, self-consistency, ensembles). They check candidate answers and keep only those that pass (proofs verified, code unit-tested, claims corroborated). And they recurse, treating a subproblem with the very same repertoire. We argue that these four (sequential composition, parallel ensembling, verification gating, and recursion) are not an arbitrary list but a generating set for a well-behaved algebra of solvers, in which reliability and cost are homomorphic images of structure.
1.0.0.2 Contributions.
A decomposition algebra (§2–§3). We model solvers as morphisms in the Kleisli category of the subdistribution monad (a Markov category [2], [3]), and define four combinators that generate the free algebra \(\mathfrak{A}(B)\) over a base set \(B\). Reliability and cost are valuations into an ordered monoid and a commutative semiring, respectively.
Composition laws (§4). We prove how each combinator transforms reliability: sequential composition degrades (Lemma 1), majority voting amplifies above a threshold (Lemma 2), and, as our key primitive, a verification gate multiplies the odds of correctness by the verifier’s likelihood ratio (Lemma 3).
Amplification and a threshold dichotomy (§5). Theorem 1 achieves reliability \(1-\delta\) at verification depth \(O(\log 1/\delta)\) whenever the verifier is informative; Theorem 2 shows this is sharp: at the critical parameters, no amplification is possible. This is the problem-solving analogue of fault-tolerance threshold theorems [1], [4].
Self-organization as a fixed point (§6). Strategies form a complete lattice under refinement; a greedy, budget-aware improvement operator is monotone, so by Knaster–Tarski [5] it has a least fixed point, the canonical self-organized strategy, which we characterize as verifier-saturated and marginal-rate-equalizing.
Matching limits (§7). An information ceiling bounds per-gate amplification (Theorem 4); shared error causes impose a strictly positive voting floor exactly when they can push the committee below chance, so diversity is necessary (Theorem 5); and a no-free-lunch corollary [6] shows decomposition gains are paid for with priors matched to the problem.
A companion report instantiates this algebra as a concrete, model-agnostic orchestration harness (Maestro Order) and measures the predicted laws; here we develop the theory in the abstract.
2 The Solver Model↩︎
We work over a problem family: a measurable space of instances \(\mathcal{X}\), an answer space \(\mathcal{A}\) (with a distinguished symbol \(\bot\notin\mathcal{A}\) for abstention), and a correctness oracle \(Y^\star:\mathcal{X}\to 2^{\mathcal{A}}\setminus\{\emptyset\}\) assigning to each instance its nonempty set of acceptable answers. A distribution \(\mathcal{D}\) over \(\mathcal{X}\) specifies which instances occur and how often.
Definition 1 (Solver). A solver* is a Markov kernel \(s:\mathcal{X}\rightsquigarrow \mathcal{A}\cup\{\bot\}\), i.e.a measurable map \(\mathcal{X}\to\Delta(\mathcal{A}\cup\{\bot\})\) from instances to (sub)distributions over answers and abstention. Write \(s(\cdot\mid x)\) for the output law on instance \(x\).*
Two scalar valuations summarize a solver. Let \(\mathrm{cov}(s)\triangleq \relax_{x\sim\mathcal{D}}[\,s(x)\neq\bot\,]\) be its coverage (the probability it commits to an answer).
Definition 2 (Reliability). The reliability* of \(s\) is the conditional correctness rate on committed answers, \[\rho(s)\;\triangleq\; \relax_{x\sim\mathcal{D},\;a\sim s(x)}\!\big[a\in Y^\star(x)\,\big|\,a\neq\bot\big],\] with the convention \(\rho(s)=0\) if \(\mathrm{cov}(s)=0\). We also use the worst-case variant \(\underline{\rho}(s)=\inf_{x\in\mathcal{X}}\relax_{a\sim s(x)}[a\in Y^\star(x)\mid a\neq\bot]\) when distribution-freeness is required.*
Separating coverage from reliability is deliberate: a solver may raise reliability by abstaining more (refusing hard instances), and the coverage/reliability trade-off is a recurring theme (§4, §8).
Definition 3 (Cost). A cost* valuation assigns to \(s\) a value \(c(s)\) in a commutative semiring \((\mathcal{K},\oplus,\otimes,0,1)\). We instantiate \(\mathcal{K}=(\mathbb{R}_{\ge0}\cup\{\infty\},+,\cdot)\), with \(c(s)\) the expected number of base-solver invocations used by \(s\). Sequential work adds (\(+\)); independent repetition multiplies counts by branching factor.*
| Symbol | Meaning |
|---|---|
| \(\X,\A,\bot\) | instances, answers, abstention |
| \(Y^\star(x)\) | acceptable-answer set (oracle) |
| \(s,g,v\) | solver, generator, verifier |
| \(\rel(s)\) | reliability (Def. [def:rel]) |
| \(\mathrm{cov}(s)\) | coverage (commit probability) |
| \(\cost(s)\) | expected base invocations |
| \(\beta,\alpha\) | verifier completeness, false-acceptance |
| \(\LR=\beta/\alpha\) | verifier discrimination (likelihood ratio) |
| \(\odds=\rel/(1{-}\rel)\) | odds; \(\ell=\log\odds\) log-odds |
| \(\seq,\oplus_A,V_v,\mu\) | sequential, vote, verify, recurse |
| \(\Alg(B)\) | decomposition algebra over base \(B\) |
2.0.0.1 Categorical view.
Solvers compose. Fix the Kleisli category \(\mathbf{Stoch}\) of the subdistribution monad: objects are (typed) problem spaces, a morphism \(A\rightsquigarrow B\) is a Markov kernel, and composition is the Chapman–Kolmogorov integral. \(\mathbf{Stoch}\) is a Markov category [2], [3]: it is symmetric monoidal under the product \(\otimes\), with copy/discard structure modelling duplication and erasure of intermediate results. Sequential decomposition is categorical composition; running solvers “side by side” is the monoidal tensor. This is the ambient category in which our algebra lives; we keep the categorical language light and verify all quantitative claims directly. Readers unfamiliar with category theory can read this paragraph as saying only that randomized solvers can be wired together in sequence and in parallel, and that both operations behave well.
3 The Decomposition Algebra↩︎
Let \(B\) be a finite set of base solvers. The decomposition algebra \(\mathfrak{A}(B)\) is the smallest set of solvers containing \(B\) and closed under the four combinators below. Figure 1 depicts them.
3.0.0.1 (1) Sequential composition \(\mathbin{\mathbin{;}}\).
For solvers \(s_1,\dots,s_k\) whose types chain (\(s_{i+1}\) consumes the output of \(s_i\)), the pipeline \(s_k\mathbin{\mathbin{;}}\cdots\mathbin{\mathbin{;}}s_1\) is their Kleisli composite. It models decomposition into dependent subproblems: the final answer is correct only if each stage produces a usable intermediate (we make the dependence precise in Lemma 1).
3.0.0.2 (2) Parallel ensembling \(\oplus_A\).
Given a solver \(s\), a replication count \(n\), and an aggregator \(A:(\mathcal{A}\cup\{\bot\})^n\rightsquigarrow \mathcal{A}\cup\{\bot\}\), the ensemble \(\oplus_A(s,n)\) draws \(n\) independent samples \(a_1,\dots,a_n\sim s(x)\) and returns \(A(a_1,\dots,a_n)\). The canonical aggregator is plurality vote \(A=\mathop{\mathrm{maj}}\).
3.0.0.3 (3) Verification gating \(V_v\).
A verifier is a kernel \(v:\mathcal{X}\times\mathcal{A}\rightsquigarrow \{\textsf{acc},\textsf{rej}\}\). Given a generator \(g\) and budget \(T\in\mathbb{N}\), the gate \(V_v(g,T)\) repeatedly samples \(a\sim g(x)\), returns the first \(a\) with \(v(x,a)=\textsf{acc}\), and abstains (\(\bot\)) after \(T\) rejections. A verifier is summarized by its completeness \(\beta\triangleq\relax[v=\textsf{acc}\mid a\in Y^\star(x)]\) and soundness \(1-\alpha\), where \(\alpha\triangleq\relax[v=\textsf{acc}\mid a\notin Y^\star(x)]\) is its false-acceptance rate. Its discrimination is the likelihood ratio \(\Lambda\triangleq\beta/\alpha\in[0,\infty]\).
3.0.0.4 (4) Recursion \(\mu\).
A reducer \(r:\mathcal{X}\rightsquigarrow \mathcal{X}^{\le m}\) maps an instance to a finite tuple of subinstances, with a recombiner \(\bigsqcup:\mathcal{A}^{\le m}\rightsquigarrow\mathcal{A}\). The recursive solver \(\mu\,F\) is the least solution of \(S = F(S)\) where \(F(S)= \bigsqcup\circ\, S^{\otimes}\circ r\) applies \(S\) to each subinstance. Well-posedness (a least fixed point exists) is established in §6.
Definition 4 (Decomposition algebra). \(\mathfrak{A}(B)\) is the closure of \(B\) under \(\{\mathbin{\mathbin{;}},\oplus_A,V_v,\mu\}\). An element of \(\mathfrak{A}(B)\) is a strategy; its syntax tree is its organization.
3.0.0.5 The algebra is not a metaphor.
The four combinators are the formal skeleton of organizations that already work. Table 2 lists canonical instantiations across very different substrates; in each case the “verifier” is whatever cheaply certifies a candidate, and the reliability laws of §4 apply unchanged. That a jury, a compiler’s test suite, a proof checker, and a MapReduce job are all the same algebra evaluated on different base solvers is the unifying claim of this paper.
| System | Base solver | Verifier \(v\) | Dominant combinator |
|---|---|---|---|
| Math proof | prover | proof checker | \(V_v\) (high \(\LR\)) |
| Software | coder | test suite / types | \(V_v\!\seq\) |
| Jury / panel | juror | — | \(\oplus_{\maj}\) |
| Ensemble ML | weak learner | — | \(\oplus_{\maj}\) |
| Science | lab/group | replication | \(V_v\,\oplus\) |
| MapReduce | mapper | re-execution | \(\mu\,\seq\) |
3.0.0.6 Valuations are (lax) homomorphisms.
Cost is an exact homomorphism into \(\mathcal{K}\): \(c(s_k\mathbin{\mathbin{;}}\cdots\mathbin{\mathbin{;}}s_1)=\sum_ic(s_i)\), \(c(\oplus_A(s,n))=n\,c(s)+c(A)\), and \(c(V_v(g,T))=\mathbb{E}[N]\,(c(g)+c(v))\) with \(N\le T\) the number of rounds. Reliability is a lax homomorphism: it does not factor through structure exactly, but is bounded above and below by explicit functions of the children’s reliabilities. Deriving those bounds is the goal of the next section.
3.0.0.7 Two bands: the log-odds semiring.
Reliability composes most cleanly not in \([0,1]\) but in log-odds. Write \(\ell(s)\triangleq\log\frac{\rho(s)}{1-\rho(s)}\in\mathbb{R}\cup\{\pm\infty\}\). The point of the next section is that the natural operations live in two algebraic bands: a reliability band, where verification cascades add log-odds, and a cost band, where work adds invocation counts.
On the sub-algebra generated by verification gates, the map \(\ell\) is a monoid homomorphism from conditionally independent gate cascades (under composition) to \((\mathbb{R},+)\): stacking gates \(V_{v_1},\dots,V_{v_k}\) sends \(\ell\mapsto \ell+\sum_i\log\Lambda_i\). Pairing \(\ell\) with cost \(c\in(\mathbb{R}_{\ge0},+)\) yields a graded monoid \((\mathbb{R}\times\mathbb{R}_{\ge0},+)\) in which the slope \(\Delta\ell/\Delta c\) is the marginal rate optimized in §6.
Proof. Immediate from Lemma 3 and Theorem 1: \(\ell\) after a cascade is \(\ell_0+\sum_i\log\Lambda_i\), additive and associative with identity the uninformative gate (\(\log\Lambda=0\)). Cost adds by Definition 3. The product monoid is the stated grading. ◻
This is why log-odds is the right currency: it linearizes the strongest combinator and turns “how to organize” into a linear-programming intuition over marginal slopes.
4 Reliability Composition Laws↩︎
Throughout, treat distinct invocations of a base solver as independent unless stated otherwise; §7 removes this assumption and shows how much depends on it.
4.1 Sequential composition degrades↩︎
Lemma 1 (Serial law). Let \(s_1,\dots,s_k\) be stages whose composite is correct iff every stage is correct (no error masking), with per-stage reliabilities \(\rho_i\). Then \[1-\sum_{i=1}^{k}(1-\rho_i)\;\le\;\rho(s_k\mathbin{\mathbin{;}}\cdots\mathbin{\mathbin{;}}s_1)\;\le\; \min_i \rho_i,\] and if stage errors are independent, \(\rho(s_k\mathbin{\mathbin{;}}\cdots\mathbin{\mathbin{;}}s_1)=\prod_{i=1}^k \rho_i\).
Proof. Let \(E_i\) be the event that stage \(i\) errs. Correctness is \(\bigcap_i \overline{E_i}\). The upper bound is monotonicity: \(\relax[\bigcap_i\overline{E_i}]\le \relax[\overline{E_j}]=\rho_j\) for each \(j\). The lower bound is the union bound: \(\relax[\bigcup_i E_i]\le\sum_i(1-\rho_i)\), so \(\relax[\bigcap_i\overline{E_i}]\ge 1-\sum_i(1-\rho_i)\). Independence gives \(\relax[\bigcap_i\overline{E_i}]=\prod_i\relax[\overline{E_i}]=\prod_i\rho_i\). ◻
Interpretation. Pure decomposition into dependent steps can only lose reliability, and it loses geometrically with depth. The error budget \(\sum_i(1-\rho_i)\) is the right first-order accounting. This is the problem that the other three combinators exist to solve.
4.2 Parallel voting amplifies above one half↩︎
Consider a decision with a unique correct answer and a per-sample correctness probability \(p\) (the binary or large-margin case).
Lemma 2 (Vote law). For \(n\) independent samples (take \(n\) odd to avoid ties) aggregated by majority, if \(p>\tfrac12\) then \[\rho(\oplus_{\mathop{\mathrm{maj}}}(s,n))\;\ge\;1-\exp\!\big(-2n(p-\tfrac12)^2\big),\] while if \(p<\tfrac12\) the same argument applied to the complement shows the majority is correct with probability at most \(\exp(-2n(\tfrac12-p)^2)\to0\), and if \(p=\tfrac12\) the votes carry no information about the answer. For \(M\)-ary answers in which the correct answer beats every alternative by expected margin \(\theta>0\), \(\rho\ge 1-(M-1)\exp(-n\theta^2/2)\).
Proof. Let \(X_j=\mathbf{1}[\text{sample }j\text{ correct}]\), i.i.d.Bernoulli\((p)\). Majority is correct iff \(\bar X>\tfrac12\). By Hoeffding’s inequality [7], \(\relax[\bar X\le\tfrac12]=\relax[\bar X-p\le-(p-\tfrac12)]\le \exp(-2n(p-\tfrac12)^2)\) when \(p>\tfrac12\). For \(M\)-ary, apply a Hoeffding bound to the gap between the true answer’s count and each competitor’s and union-bound over the \(M-1\) competitors. ◻
The phase transition at \(p^\star=\tfrac12\) is Condorcet’s jury theorem [8] in quantitative form: a committee of better-than-chance jurors converges to truth; a committee of worse-than-chance jurors converges to falsehood.
4.3 Verification multiplies the odds↩︎
Write the odds of correctness as \(o(s)\triangleq \rho(s)/(1-\rho(s))\). The following lemma is the central tool of the paper.
Lemma 3 (Verification odds law). Let \(g\) generate a correct candidate with probability \(p\), and let \(v\) be a verifier with completeness \(\beta\) and false-acceptance \(\alpha>0\), whose errors are independent of \(g\)’s given correctness. Condition on acceptance. Then the accepted answer’s odds of correctness satisfy \[o_{\mathrm{post}}\;=\;o_{\mathrm{pre}}\cdot \Lambda, \qquad \Lambda=\frac{\beta}{\alpha},\] where \(o_{\mathrm{pre}}=p/(1-p)\). Equivalently the post-acceptance reliability is \(r=\dfrac{p\beta}{p\beta+(1-p)\alpha}\).
Proof. By Bayes’ rule on the event \(\textsf{acc}\), \[\frac{\relax[\text{corr}\mid\textsf{acc}]}{\relax[\text{wrong}\mid\textsf{acc}]} =\frac{\relax[\textsf{acc}\mid\text{corr}]}{\relax[\textsf{acc}\mid\text{wrong}]} \cdot\frac{\relax[\text{corr}]}{\relax[\text{wrong}]} =\frac{\beta}{\alpha}\cdot\frac{p}{1-p}.\qedhere\] ◻
Two consequences are immediate and important. First, verification is a Bayesian update: each gate contributes additively in log-odds, \(\log\left(o_{\mathrm{post}}\right)=\log\left(o_{\mathrm{pre}}\right) + \log\left(\Lambda\right)\). Second, the gain from a single gate is capped by the verifier: one gate multiplies the odds by at most \(\Lambda=\beta/\alpha\), no matter how the candidate was produced; a perfect verifier (\(\alpha=0,\;\Lambda=\infty\)) certifies correctness outright, while an uninformative one (\(\Lambda=1\)) changes nothing. Verification converts generation luck into checking power.
Lemma 4 (Coverage of a gate). The per-round acceptance probability is \(q=p\beta+(1-p)\alpha\), so the gate \(V_v(g,T)\) commits with probability \(1-(1-q)^T\) and the expected number of rounds is \(\mathbb{E}[N]=(1-(1-q)^T)/q\le 1/q\).
Proof. Rounds are i.i.d.; acceptance per round has probability \(q\) by the law of total probability. The commit probability and truncated-geometric mean follow. ◻
5 Amplification and the Threshold Dichotomy↩︎
We now stack gates. Suppose we hold a candidate and submit it to \(k\) verifiers whose errors are conditionally independent given correctness, accepting the candidate only if all accept (re-generating otherwise). By Lemma 3 applied \(k\) times the odds multiply.
Theorem 1 (Reliability amplification). Let the base generator have correctness probability \(p_0\in(0,1)\) and let \(k\) conditionally independent verifiers have discriminations \(\Lambda_1,\dots,\Lambda_k\). Conditioned on joint acceptance, the reliability is \(r_k=o_k/(1+o_k)\) with \(o_k=\frac{p_0}{1-p_0}\prod_{i=1}^k\Lambda_i\). In particular, with each \(\Lambda_i\ge\Lambda>1\), reliability \(1-\delta\) is attained once \[k\;\ge\;\frac{\log\frac{1-\delta}{\delta}+\log\frac{1-p_0}{p_0}}{\log\Lambda} \;=\;O\!\Big(\tfrac{1}{\log\Lambda}\log\tfrac1\delta\Big),\] and the expected number of base invocations is of order \(k/(p_0\prod_i\beta_i)\).
Proof. Joint acceptance has likelihood \(\prod_i\beta_i\) under correctness and \(\prod_i\alpha_i\) under error (conditional independence). The odds form of Bayes gives \(o_k=o_0\prod_i(\beta_i/\alpha_i)=o_0\prod_i\Lambda_i\). Solving \(r_k\ge 1-\delta\iff o_k\ge(1-\delta)/\delta\) and taking logarithms yields the stated \(k\). For cost, by Lemma 4 the per-attempt joint-acceptance probability is at least \(p_0\prod_i\beta_i\), so the expected number of generate-and-check attempts is \(O(1/(p_0\prod_i\beta_i))\), each costing \(k{+}1\) invocations. ◻
The depth is logarithmic in the target error \(\delta\): closing the reliability gap is exponentially cheap in structure, provided the verifier is informative. The next theorem shows that proviso is exactly a phase boundary.
Theorem 2 (Threshold dichotomy). Fix a base solver and consider amplifying its reliability with bounded per-stage cost.
**(Verification.)* If \(\Lambda>1\), then for every \(\delta>0\) there is a strategy of depth \(O(\log\frac{1}{\delta})\) and reliability \(\ge1-\delta\). If \(\Lambda=1\), then for every verification strategy \(\rho\le p_0\); the verifier adds nothing. If \(\Lambda<1\) (that is, \(\beta<\alpha\)), swapping the verifier’s accept and reject verdicts gives discrimination \((1-\beta)/(1-\alpha)>1\), so amplification is again possible and \(\Lambda^\star=1\) is the sole critical value.*
**(Voting.)* If \(p>\tfrac12\), majority voting reaches any \(1-\delta\) with \(n=O\!\big(\frac{1}{(p-\frac{1}{2})^2}\log\frac{1}{\delta}\big)\) samples; if \(p\le\tfrac12\), \(\rho(\oplus_{\mathop{\mathrm{maj}}}(s,n))\) does not exceed \(p\) and tends to \(0\) for \(p<\tfrac12\). The critical value is \(p^\star=\tfrac12\).*
Proof. Part (1), \(\Lambda>1\): Theorem 1. Part (1), \(\Lambda=1\): then \(\beta=\alpha\), so acceptance is independent of correctness; conditioning on \(\textsf{acc}\) leaves \(\relax[\text{corr}\mid\textsf{acc}]=p_0\) by Lemma 3 with \(\Lambda=1\), and composing such gates preserves the posterior, so no strategy built only from uninformative gates exceeds \(p_0\). \(\Lambda<1\): swap the verdicts as in the statement. Part (2): the upper direction is Lemma 2; for \(p<\tfrac12\), \(\bar X\to p<\tfrac12\) a.s.by the law of large numbers, so majority is eventually always wrong and \(\rho\to0\); for \(p=\tfrac12\) the votes are independent of the truth, so no aggregation rule can do better than probability \(\tfrac12\). ◻
This is the problem-solving counterpart of the fault-tolerance threshold theorems for unreliable computation and quantum error-correction [1], [4]: there is a critical component quality above which arbitrarily reliable computation is achievable at modest overhead, and below which it is not. Here the “component quality” that matters for checking is the verifier’s likelihood ratio, and for voting it is being better than chance. Figure 2 plots the two regimes.
6 Self-Organization as a Fixed Point↩︎
We now explain why structure should appear: why a system that locally improves itself converges to a stable, layered organization.
6.0.0.1 The strategy lattice.
Let \(\mathbb{S}\) be the set of strategies for a fixed problem family, augmented with a bottom element \(\bot_{\mathbb{S}}\) (the trivial abstaining solver) and a top element \(\top_{\mathbb{S}}\) (the oracle). Define the refinement order \(\sigma\sqsubseteq\sigma'\) to mean \(\sigma'\) is obtained from \(\sigma\) by a finite sequence of reliability-monotone expansions: wrapping a subtree in a vote (only where the subtree is above chance), in a gate (only with \(\Lambda\ge1\)), or in an additional refinement round, or replacing a leaf by a decomposition whose composite dominates it pointwise. The qualifiers matter: by the laws of §4, these are exactly the conditions under which each expansion cannot decrease reliability.
Lemma 5 (Complete lattice). \((\mathbb{S},\sqsubseteq)\) is a complete lattice: every subset has a supremum (the join obtained by parallel ensembling with a correctness-selecting aggregator) and an infimum.
Proof sketch. Finite joins exist by \(\oplus\) with an idealized selector that returns a correct member if any branch is correct, which dominates each branch in \(\sqsubseteq\); finite meets exist dually by restricting coverage to the common domain. Arbitrary joins/meets exist by Dedekind–MacNeille completion of the resulting poset, which adjoins all suprema and infima while preserving existing ones [9]. The adjoined \(\top_{\mathbb{S}},\bot_{\mathbb{S}}\) are the global bounds. (The join is an idealization used only to give the order a complete-lattice structure; the improvement operator below never needs to construct it.) ◻
6.0.0.2 The improvement operator.
Fix a cost budget \(\kappa\) and a marginal-rate threshold \(\lambda>0\). Define \(\Phi_\kappa:\mathbb{S}\to\mathbb{S}\) as the operator that, given a strategy \(\sigma\), applies the single combinator (add a gate, add a vote, deepen a decomposition) that maximizes the marginal log-odds gain per unit cost, provided that rate exceeds \(\lambda\) and the budget \(\kappa\) is not exhausted; otherwise \(\Phi_\kappa(\sigma)=\sigma\). (Ties in the maximization are broken by a fixed priority order, so \(\Phi_\kappa\) is a well-defined function.)
Algorithm 3 realizes \(\Phi_\kappa\) as hill-climbing on the strategy lattice. Its termination and the structure of its output are not implementation details but theorems:
Lemma 6 (Monotonicity). Under the reliability-monotone expansion order, \(\Phi_\kappa\) is order-preserving: \(\sigma\sqsubseteq\sigma'\Rightarrow \Phi_\kappa(\sigma)\sqsubseteq\Phi_\kappa(\sigma')\).
Proof sketch. Each admissible expansion is, by Lemmas 2–3, reliability non-decreasing and acts on a subtree; applying the same class of expansion to a refinement \(\sigma'\) of \(\sigma\) yields a refinement of \(\Phi_\kappa(\sigma)\) because refinement is preserved under wrapping in a gate/vote and under dependent substitution. Hence the image order is preserved. ◻
Theorem 3 (Existence of a self-organized strategy). \(\Phi_\kappa\) has a least fixed point above any seed \(\sigma_0\) and a greatest fixed point below \(\top_{\mathbb{S}}\). Moreover, the iteration \(\sigma_0\), \(\Phi_\kappa(\sigma_0)\), \(\Phi_\kappa^{2}(\sigma_0)\), … reaches the least fixed point above \(\sigma_0\), denoted \(\sigma^\star_\kappa\), after finitely many steps.
Proof. By Lemma 5 the domain is a complete lattice and by Lemma 6 \(\Phi_\kappa\) is monotone, so the Knaster–Tarski theorem [5] (every order-preserving map on a complete lattice has least and greatest fixed points) applies. For the iteration: every step that changes the strategy adds at least the cost \(c_{\min}>0\) of the cheapest combinator, and total cost is capped by \(\kappa\), so after at most \(\lceil\kappa/c_{\min}\rceil\) steps the iteration is constant at some fixed point \(\sigma^\star_\kappa\sqsupseteq\sigma_0\). It is the least such: if \(\tau\) is any fixed point with \(\tau\sqsupseteq\sigma_0\), monotonicity gives \(\Phi_\kappa^{\,n}(\sigma_0)\sqsubseteq\Phi_\kappa^{\,n}(\tau)=\tau\) for all \(n\), hence \(\sigma^\star_\kappa\sqsubseteq\tau\). ◻
At the fixed point \(\sigma^\star_\kappa\), no admissible combinator yields marginal log-odds gain per unit cost exceeding \(\lambda\). Consequently the organization is verifier-saturated: under the amplification law (Theorem 1), additional gates have been added until their marginal rate \(\log\Lambda/\Delta c\) falls to \(\lambda\), and the optimal allocation of a fixed budget across \(J\) candidate expansions equalizes the marginal rates, \[\frac{\partial \log o}{\partial c}\Big|_{j}=\lambda \quad\text{for all active }j,\] a water-filling condition: budget flows to whichever expansions currently offer the highest return, until all active ones offer the same rate \(\lambda\). (This is the standard first-order condition for constrained maximization.)
Proof. At a fixed point \(\Phi_\kappa(\sigma)=\sigma\), so by definition of \(\Phi_\kappa\) no available expansion has rate \(>\lambda\) within budget; hence every active expansion sits at rate \(=\lambda\) (lower-rate ones are inactive), which is the stationarity (KKT) condition of maximizing \(\log o\) subject to \(c\le\kappa\) with multiplier \(\lambda\). ◻
Two messages follow. First, organization is emergent and inevitable under local improvement: any hill-climbing process on the strategy lattice that prefers higher reliability-per-cost terminates at a layered, verifier-saturated structure; it does not need a designer. Second, the shape of that structure is dictated by the laws of §4: it allocates checking where information is cheapest, exactly as a rational designer would, because the fixed point coincides with the constrained optimum.
7 Fundamental Limits↩︎
Amplification is bounded by information, by correlation, and by the absence of free lunches.
7.1 An information ceiling on verification↩︎
A verifier is a channel from the latent bit “correct/incorrect” to its verdict. Its discrimination cannot exceed the information that channel carries.
Theorem 4 (Information ceiling). Let a verifier output verdict \(W\) from latent correctness \(C\in\{0,1\}\). The expected log-odds gain it produces (averaged over the verdict, given a correct candidate) is the divergence between its two verdict distributions: \[\mathbb{E}\big[\log o_{\mathrm{post}}-\log o_{\mathrm{pre}}\big] =D_{\mathrm{KL}}\!\big(P_{W\mid C=1}\,\|\,P_{W\mid C=0}\big),\] and no cascade of verifiers that are all functions of the same evidence \(Z\) can yield a more reliable decision than the best decision based on \(Z\) itself. In particular, by the data-processing inequality, achievable reliability is limited by the mutual information \(I(C;Z)\) between correctness and all evidence the system can observe.
Proof. The posterior log-odds update on verdict \(W\) is the log-likelihood ratio \(\log\frac{P_{W\mid C=1}(W)}{P_{W\mid C=0}(W)}\); its expectation when \(W\sim P_{W\mid C=1}\) is, by definition, \(D_{\mathrm{KL}}(P_{W\mid1}\|P_{W\mid0})\). Verdicts are (possibly randomized) functions of \(Z\), so by the data-processing inequality [10] \(I(C;\text{verdicts})\le I(C;Z)\), and a decision based on a function of \(Z\) cannot be more accurate than the best decision based on \(Z\). Fano’s inequality then bounds achievable reliability in terms of \(I(C;Z)\). ◻
Stacking gates (Theorem 1) therefore pays off only when each gate contributes new, conditionally independent evidence; gates that re-read the same signal are redundant, and their effective \(\Lambda\) collapses toward \(1\). Amplification consumes information.
7.2 Diversity is necessary↩︎
Independence was assumed in Lemmas 2–3. Real populations of solvers often make errors together: they share training, methods, or blind spots. We now show exactly when shared errors put a hard floor under majority voting.
We model shared causes in the standard way: the voters are conditionally i.i.d.given a latent factor \(S\) that collects everything they have in common. (By de Finetti’s theorem, every infinite exchangeable population has this form, so this is not a special assumption.) Write \(p(S)\) for the per-voter accuracy conditional on \(S\), with \(\mathbb{E}[p(S)]=p\), \(\sigma^2=p(1-p)\), and pairwise correlation \(\gamma=\operatorname{Var}(p(S))/\sigma^2\).
Theorem 5 (Shared-cause voting floor). In the latent-factor model, with \(n\) odd: (i) the vote share satisfies \(\operatorname{Var}(\bar X)=\frac{\sigma^2}{n}+\frac{n-1}{n}\gamma\sigma^2 \xrightarrow{n\to\infty}\gamma\sigma^2\), so for \(\gamma>0\) it never concentrates at \(p\); and (ii) if \(\relax[p(S)=\tfrac12]=0\), then \[\lim_{n\to\infty}\relax[\text{majority wrong}] \;=\;\relax\!\big[p(S)<\tfrac12\big].\] The floor on the right is strictly positive exactly when shared circumstances can push the whole committee below chance, and no amount of replication removes it. In particular, in the Gaussian-copula model (the model used in the companion simulations) the floor is strictly positive for every \(\gamma>0\).
Proof. (i) is the variance expansion of \(\operatorname{Var}(\frac{1}{n}\sum X_j)\) with equal pairwise covariances \(\operatorname{Cov}(X_i,X_j)=\operatorname{Var}(p(S))=\gamma\sigma^2\). (ii) Conditional on \(S\), the law of large numbers gives \(\bar X\to p(S)\) almost surely, so the majority indicator \(\mathbf{1}[\bar X>\tfrac12]\) converges to \(\mathbf{1}[p(S)>\tfrac12]\) outside the null event \(\{p(S)=\tfrac12\}\); bounded convergence yields the limit. For the Gaussian-copula model, \(X_j=\mathbf{1}[\sqrt{\gamma}\,S+\sqrt{1-\gamma}\,\varepsilon_j\le u]\) with independent standard normal \(S,\varepsilon_j\) and \(u=\Phi^{-1}(p)\), where \(\Phi\) is the standard normal distribution function; then \(p(S)=\Phi\big((u-\sqrt{\gamma}\,S)/\sqrt{1-\gamma}\big)\) takes every value in \((0,1)\) with positive density, so \(\relax[p(S)<\tfrac12]>0\) for every \(\gamma>0\). ◻
The characterization has two sides. If shared factors only add noise but never drag the committee below chance (\(p(S)>\tfrac12\) almost surely), majority voting still converges to the truth; correlation merely slows it down. But if some situations make the whole committee wrong together, those situations are lost no matter how many copies vote.
Corollary 1 (Effective committee size). Matching the vote-share variance, correlated voting behaves like independent voting with an effective* sample size \(n_{\mathrm{eff}}=\frac{n}{1+(n-1)\gamma}\to\frac{1}{\gamma}\): in terms of how sharply its vote share concentrates, a correlated committee is never worth more than \(1/\gamma\) independent voters, however many members it has.*
Proof. Match variances: \(\operatorname{Var}(\bar X)=\sigma^2/n_{\mathrm{eff}}\) with the expression of Theorem 5 gives \(n_{\mathrm{eff}}=n/(1+(n-1)\gamma)\), whose limit is \(1/\gamma\). ◻
For example, at correlation \(\gamma{=}0.1\) even a thousand-member committee concentrates no better than about ten independent voters, so the value of one more correlated member is already negligible. Diversity, meaning conditionally independent errors, is therefore not a luxury but a requirement for unbounded amplification. Organizations that clone a single fallible solver inherit its blind spots no matter how large they grow; useful committees are built from members who fail differently.
7.3 No free lunch↩︎
Corollary 2 (No universal decomposition). Averaged uniformly over all problem families with a given answer space, every strategy in \(\mathfrak{A}(B)\) has the same expected reliability as its base solvers: decomposition confers no advantage absent a prior matching structure to problems.
Proof sketch. This is the no-free-lunch theorem for search and optimization [6] transported to our setting: combinators are deterministic re-wirings of base-solver calls, so over the uniform mixture of oracles every fixed strategy induces the same marginal distribution over (instance, answer) correctness as calling the base solvers directly. Gains on a subfamily are exactly offset elsewhere. ◻
The corollary is not nihilistic; it is a statement about where reliability comes from. The combinators do not manufacture reliability; they transport the information already present in solvers and verifiers to the place a decision is made, and they only help on the structured problem families we actually face: those where verifiers are informative and errors are diverse.
8 The Cost–Reliability Frontier↩︎
Collecting the laws, we can compare combinators on a common axis: the cost (base invocations) to reach error \(\delta\).
| Combinator | Work for error \(\delta\) | Regime |
|---|---|---|
| Sequential \(\seq\) | — | anti-amplifying (\(\rel\!\downarrow\)) |
| Voting \(\oplus_{\maj}\) | \(\Theta\!\big(\frac{1}{(p-\frac12)^2}\log\frac1\delta\big)\) | needs \(p>\tfrac12\) |
| Verify \(V_v\) | \(\Theta\!\big(\frac{1}{\log\LR}\log\frac1\delta\big)\) | needs \(\LR>1\) |
| Recurse \(\mu\) | depth-dependent | inherits children |
Both voting and verification reach error \(\delta\) with structure size \(\Theta(\log\frac{1}{\delta})\) (samples for voting, gates for verification), which is optimal for any method whose error decays at most geometrically per unit of structure; verification’s constant is governed by \(\log\Lambda\) and voting’s by \((p-\tfrac12)^2\), so verification dominates whenever a sufficiently discriminating checker exists. Under a fixed budget the reliability-maximizing strategy equalizes marginal log-odds gain per cost across stages (Proposition [prop:sat]), preferring the combinator with the largest current marginal rate.
Proof. Each accepted gate adds \(\log\Lambda\) to the log-odds, and each batch of \(n\) votes adds \(\Theta((p-\tfrac12)^2 n)\) to a Chernoff exponent; both give \(\log(1/\delta)\) scaling, and error that decays at most geometrically per unit of structure needs \(\Omega(\log\frac{1}{\delta})\) structure. The allocation rule is the first-order optimality (KKT) condition of Proposition [prop:sat]. In total calls, verification additionally pays a regeneration factor of at most \(\beta^{-k}\), which equals \(1\) for a complete verifier and stays small for \(\beta\) near \(1\). ◻
8.0.0.1 A worked organization.
Suppose a base solver with \(p_0=0.55\) and a verifier with \(\Lambda=4\) (\(\beta=0.8,\alpha=0.2\)). Each gate multiplies the odds by \(4\); the log-odds grow linearly while reliability saturates toward one (Table 4). Reaching \(\delta=10^{-3}\) needs \(k=\lceil(\log 999+\log\frac{0.45}{0.55})/\log4\rceil=5\) gates, matching Theorem 1. Pure voting from \(p_0=0.55\) would instead need \(\sim\!\frac{1}{2(0.05)^2}\log10^3\approx1400\) samples for the same target: counting all calls (including regenerations), verification is roughly two orders of magnitude cheaper here (a few dozen calls versus about \(1400\)), which is exactly why effective organizations are built around checkers.
| gates \(k\) | odds \(\odds_k\) | reliability \(r_k\) | error \(1-r_k\) |
|---|---|---|---|
| 0 | 1.22 | 0.550 | \(4.5\times10^{-1}\) |
| 1 | 4.89 | 0.830 | \(1.7\times10^{-1}\) |
| 2 | 19.6 | 0.951 | \(4.9\times10^{-2}\) |
| 3 | 78.2 | 0.987 | \(1.3\times10^{-2}\) |
| 4 | 313 | 0.997 | \(3.2\times10^{-3}\) |
| 5 | 1252 | 0.9992 | \(8.0\times10^{-4}\) |
9 Recursive Decomposition: A Reliability Master Theorem↩︎
The recursion combinator \(\mu\) raises the stakes: a problem is reduced to subproblems, each solved by the same repertoire, to a depth \(d\). Without correction, recursion is the serial law (Lemma 1) compounded across an exponentially growing tree, and reliability collapses. With verification at each node it is reliable at polylogarithmic overhead. We make this precise.
Consider a balanced recursion of depth \(d\) and branching \(b\): an internal node reduces its instance to \(b\) subinstances, solves each recursively, and recombines with reliability \(\rho_c\) (the recombiner is correct, given correct children, with probability \(\rho_c\)); a leaf is solved by a base solver of reliability \(p\).
Without per-node verification, the reliability \(r(d)\) of the recursive solver obeys \(r(d)=\rho_c\,r(d-1)^{b}\) with \(r(0)=p\), whose closed form is \[r(d)\;=\;\rho_c^{\,(b^d-1)/(b-1)}\;p^{\,b^d}.\] Hence for \(b\ge2\), unless \(p=\rho_c=1\), \(r(d)\to0\) as \(d\to\infty\), and the decay is doubly exponential in the depth \(d\).
Proof. A node is correct iff its recombiner is correct and all \(b\) children are correct; by independence \(r(d)=\rho_c\,r(d-1)^{b}\). Unrolling the recurrence gives \(r(d)=\rho_c^{\,1+b+\cdots+b^{d-1}}p^{\,b^d} =\rho_c^{\,(b^d-1)/(b-1)}p^{\,b^d}\). Both exponents grow like \(b^d\), so \(r(d)=c^{\,b^d(1+o(1))}\) with \(c=p\,\rho_c^{1/(b-1)}<1\) unless \(p=\rho_c=1\). ◻
This is why naive “decompose-and-recurse” degrades with depth: each level multiplies the number of opportunities for error by the branching factor \(b\). The remedy is to restore each node’s reliability before its result propagates upward.
Theorem 6 (Recursion master theorem). Let the tree have \(N=\frac{b^{d+1}-1}{b-1}\) nodes, and suppose each node is wrapped in a verification gate that drives its local error (given correct inputs) to at most \(\eta\). Then the whole computation is correct with probability at least \(1-N\eta\). Consequently, to achieve overall error \(\delta\) it suffices to verify each node to error \(\eta=\delta/N\), which by Theorem 1 requires per-node verification depth \[k_{\mathrm{node}}=O\!\Big(\tfrac{1}{\log\Lambda}\big(\log\tfrac1\delta+d\log b\big)\Big),\] and total cost \(O\!\big(N\,k_{\mathrm{node}}\big)= O\!\big(b^{d}\,(\log\tfrac1\delta+d\log b)/\log\Lambda\big)\): linear in the work \(b^d\) up to a polylogarithmic overhead, provided \(\Lambda>1\).
Proof. Let \(A_v\) be the event that node \(v\)’s local step errs despite correct inputs, \(\relax[A_v]\le\eta\). The output is correct unless some node errs, so by the union bound the failure probability is at most \(\sum_v\relax[A_v]\le N\eta\). Setting \(N\eta=\delta\) gives \(\eta=\delta/N\); achieving per-node error \(\delta/N\) from a fixed base by Theorem 1 costs \(O(\log(N/\delta)/\log\Lambda)\) gates, and \(\log N=\Theta(d\log b)\). Summing over \(N\) nodes gives the total. The count is in gate evaluations; with an incomplete verifier (\(\beta<1\)), regenerations multiply per-node cost by at most \(\beta^{-k_{\mathrm{node}}}=(N/\delta)^{\ln(1/\beta)/\ln\Lambda}\), a mild polynomial factor that equals \(1\) for a complete checker (\(\beta=1\), e.g.a proof checker). ◻
Corollary 3 (Threshold for recursion). Recursive decomposition is reliability-preserving to arbitrary depth iff an informative verifier exists (\(\Lambda>1\)). At \(\Lambda=1\) no per-node correction is possible and reliability follows the collapsing recurrence of Proposition [prop:collapse].
9.0.0.1 A worked recursion.
Take depth \(d{=}4\), branching \(b{=}3\) (so \(N=\frac{3^5-1}{2}=121\) nodes), target \(\delta{=}10^{-2}\), and a robust verifier with \(\Lambda{=}4\). The master theorem asks each node to reach error \(\eta=\delta/N\approx8.3\times10^{-5}\), i.e.odds \(\approx1.2\times10^{4}\), which from \(p_0{=}0.55\) takes \(k_{\mathrm{node}}=\lceil(\log(1.2{\times}10^4)+\log\frac{0.45}{0.55})/\log4\rceil =7\) gates. The unverified recurrence (Prop. [prop:collapse]) with the same leaves and \(\rho_c{=}0.9\) instead falls to \(0.15\) after one level, \(0.003\) after two, and below \(10^{-7}\) after three, a clear illustration that depth without checking destroys reliability, while depth with logarithmic-overhead checking preserves it.
The master theorem is the recursion-level counterpart of the threshold dichotomy and of fault-tolerant computing: depth is affordable when each level is checked. The polylogarithmic-per-node overhead is precisely the price of preventing error from compounding across the tree; it has the same shape as the overhead in fault-tolerant circuits, but is derived here from the odds law rather than from code distance.
10 Selective Reliability: Abstention and Calibration↩︎
So far reliability was measured on committed answers (Definition 2). The freedom to abstain (\(\bot\)) is itself a reliability lever: a system can decline the instances it is least sure of and raise its reliability on the rest. This is selective prediction [11], [12], and it interacts cleanly with our laws because the verifier already supplies a confidence signal: its log-likelihood-ratio score.
Definition 5 (Risk–coverage). For a score \(\phi(x,a)\) (e.g.the accumulated log-odds after gating) and threshold \(\tau\), the selective solver commits iff \(\phi\ge\tau\). Its coverage is \(\mathrm{cov}(\tau)=\relax[\phi\ge\tau]\) and its risk is \(R(\tau)=\relax[a\notin Y^\star\mid \phi\ge\tau]\). The risk–coverage curve* is \(\tau\mapsto(\mathrm{cov}(\tau),R(\tau))\).*
If \(\phi\) is the true log-odds of correctness (a calibrated score), then \(R(\tau)\) is non-increasing in \(\tau\): tightening the acceptance threshold never worsens reliability on the covered region. Moreover, under costs \(c_{\mathrm{err}}\) for a wrong commit and \(c_{\mathrm{abs}}\) for abstaining, the risk-minimizing policy is Chow’s rule: commit iff the posterior correctness exceeds \(1-c_{\mathrm{abs}}/c_{\mathrm{err}}\), equivalently \(\phi\ge\log\frac{c_{\mathrm{err}}-c_{\mathrm{abs}}}{c_{\mathrm{abs}}}\).
Proof. For calibrated \(\phi\), \(\relax[\text{wrong}\mid\phi]=\sigma(-\phi)\) is decreasing in \(\phi\), so the conditional risk over the region \(\{\phi\ge\tau\}\) is an average of decreasing tails and is non-increasing in \(\tau\). The Bayes-optimal decision compares expected costs \(c_{\mathrm{err}}\,\relax[\text{wrong}\mid\phi]\) against \(c_{\mathrm{abs}}\); commit when the former is smaller, which rearranges to the stated log-odds threshold (Chow’s rule [11]). ◻
Thus the verifier does double duty: as a gate it amplifies reliability (§5); as a score it orders instances for selective abstention (here). The risk–coverage curve is the achievable frontier of an organization, and escalation (abstaining and routing hard instances to a stronger sub-organization) is just abstention with a fallback, inheriting these guarantees.
11 Generator–Verifier Games↩︎
The amplification theorem assumed the generator’s errors are indifferent to the verifier. When a generator instead optimizes for acceptance, as learned systems do under a reward and as nature does under selection, the verifier’s discrimination can silently collapse. This is Goodhart’s law (a proxy measure stops tracking what it was meant to measure once it is optimized directly) expressed in our calculus, and it limits how much reliability organization can manufacture.
Model a Stackelberg interaction: the verifier \(v\) is fixed (the leader); the generator chooses an output distribution \(g\) (the follower) to maximize acceptance probability, possibly concentrating mass on wrong answers that \(v\) nonetheless accepts. Let \(\alpha^\dagger(v)=\sup_{g:\,g\text{ wrong}}\relax[v\;\textsf{acc}\mid g]\) be the adversarial false-acceptance rate.
Definition 6 (Non-gameable verifier). A verifier is \(\Lambda\)-robust* if its discrimination stays above \(\Lambda>1\) against the worst-case generator, i.e. \(\beta/\alpha^\dagger(v)\ge\Lambda\).*
Theorem 7 (Robust amplification). If every gate is \(\Lambda\)-robust with \(\Lambda>1\), the amplification and master theorems (Thms. 1, 6) hold verbatim against adversarial generation, with \(\Lambda\) replaced by the robust \(\Lambda\). If some gate has \(\alpha^\dagger=\beta\) (fully gameable), its effective \(\Lambda\to1\) and it contributes no amplification regardless of its nominal \(\beta/\alpha\) on benign inputs.
Proof. The odds law (Lemma 3) used only \(\relax[\textsf{acc}\mid \text{corr}]\) and \(\relax[\textsf{acc}\mid\text{wrong}]\); substituting the worst-case wrong-acceptance \(\alpha^\dagger\) for \(\alpha\) yields posterior odds multiplied by \(\beta/\alpha^\dagger\ge\Lambda\), and the proofs of Theorems 1 and 6 go through with \(\Lambda\). If \(\alpha^\dagger=\beta\) the multiplier is \(1\), so by the \(\Lambda{=}1\) case of Theorem 2 no amplification occurs. ◻
The lesson sharpens §7: it is not enough for a verifier to be discriminating on average; to support reliable organization under optimization pressure it must be discriminating against an adversary that searches for what it will wrongly accept. Proof checkers and type systems are robust in this sense (their false-acceptance is bounded by soundness, independent of how the prover was chosen); learned reward models and shallow heuristics often are not, which is precisely why reliability built on them erodes as generators are optimized against them. Robust verification is the scarce resource on which reliable intelligence is built.
12 Related Work↩︎
12.0.0.1 Reliable computation from unreliable parts.
Von Neumann’s multiplexing and the subsequent fault-tolerance threshold theorems [1], [4] established that redundancy plus error-correction yields arbitrarily reliable computation above a component-quality threshold. Our Theorem 2 is the analogue for problem-solving, with the verifier’s likelihood ratio in the role of component quality and verification in the role of correction.
12.0.0.2 Aggregation and ensembles.
The Condorcet jury theorem [8], boosting and ensemble learning [13], and concentration of measure [7] explain when many weak deciders make a strong one; our vote law and diversity floor (Theorems 2, 5) are the reliability-calculus form, emphasizing that correlation caps the gain.
12.0.0.3 Verification and learning theory.
The asymmetry that checking can be easier than producing underlies complexity theory’s verifier-centric definitions and PAC learning [14]; Lemma 3 quantifies the value of a checker as a likelihood ratio and connects to information-theoretic limits [10]. Selective prediction and the reject option [11], [12] furnish the abstention frontier of §10, and our generator–verifier analysis (§11) formalizes the Goodhart effect that erodes non-robust checkers under optimization pressure.
12.0.0.4 Compositional and categorical models.
Markov categories give a clean syntax for stochastic composition [2], [3]; lattice and fixed-point methods underlie program semantics [5], [9]. We use both to make “organization” a formal object and to prove that self-organization is a fixed point.
12.0.0.5 Problem-solving architectures.
From the General Problem Solver and means–ends analysis [15] to the society-of-mind view that intelligence is the organization of many small unintelligent processes [16], and the divide-and-conquer paradigm in algorithms and distributed systems [17], the recurring idea is that capability is a property of structure. We supply a reliability-theoretic account of which structures work and why.
13 Discussion and Conclusion↩︎
We modeled problem-solving as an algebra over unreliable solvers and found that a small generating set (sequence, vote, verify, recurse) suffices to express the organizations intelligence actually uses, and that reliability flows through these combinators by explicit laws. Sequencing degrades; voting amplifies above chance; verification multiplies the odds by the checker’s likelihood ratio and so, stacked, closes the error gap at logarithmic depth. Above critical parameters (\(\Lambda^\star=1\), \(p^\star=\tfrac12\)) reliability is essentially free to buy; at or below them it cannot be bought at all. Crucially, the layered, verifier-saturated organizations we observe in capable systems are not accidental: they are the fixed points of local improvement on the strategy lattice, and they coincide with the constrained optima that equalize marginal information per cost. And reliability has hard limits: the information the verifier carries, the diversity of the solvers, and the absence of a universal free lunch.
Three implications stand out. (i) Build checkers, not just generators: when a discriminating verifier exists, verification beats voting by orders of magnitude (§8), so the highest-value engineering is often in the test, not the attempt. (ii) Cultivate diversity: cloning a single solver gains nothing beyond its shared-error floor (Theorem 5). (iii) Expect emergent layering: any system that locally trades cost for reliability will grow verification layers on its own (Theorem 3), so the design question is less whether to layer than where the marginal information is.
13.0.0.1 Why organizations look the way they do.
The same laws explain recurring features of human and biological problem-solving. Peer review, replication, and reproducibility are verification gates; the scientific premium on independent confirmation is Corollary 1 in cultural form. Bureaucratic sign-off chains are gate cascades trading latency for reliability. Modular redundancy in engineering (running three units and taking the majority) is voting above threshold. Division of labor is sequential decomposition made safe by local checking (inspection, unit tests). That such different systems converge on layered, checker-saturated structure is, on this account, not convergent accident but the shared fixed point of local improvement under the reliability laws (Theorem 3).
13.0.0.2 Limitations and future work.
Our assumptions of independence and conditional independence are idealized; §7 bounds the cost of violating them but a tight theory of partially correlated verifier cascades remains open. We treated verifier quality as given; learning the decomposition and the verifier, together with the game-theoretic dynamics when generators adapt to checkers, is the natural sequel, as is a quantitative bridge from these laws to the behavior of real model harnesses, which the companion paper takes up empirically.