Search papers, labs, and topics across Lattice.
This paper investigates the structural organization of unreliable elementary problem-solvers to determine how they can be combined to reliably solve complex problems. By developing a decomposition algebra that incorporates various combinators and homomorphisms for reliability and cost, the authors derive key results including a verification odds law that shows how verification gates can exponentially amplify correctness odds. The findings reveal critical thresholds for reliability amplification, emphasizing the necessity of independent information and the structured arrangement of solvers to achieve high reliability without incurring prohibitive costs.
Verification gates can exponentially amplify the odds of correctness, but only if the underlying information is independent and strategically organized.
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 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 $螞$, so that $k$ conditionally independent gates yield geometric amplification; (ii) a $reliability~amplification~theorem$, giving target reliability $1-未$ at $O(\log 1/未)$ verification depth whenever $螞>1$; and (iii) a $threshold~dichotomy$: above the critical parameters 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$ 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. 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, so diversity is $necessary$ for unbounded amplification. Reliability, in short, is neither free nor magical: it is bought with independent information, arranged by composition, and bounded by the verifier.
