Status note. Every structural claim below is placed against prior art. The quotient/minimization theorem is the Myhill–Nerode congruence [1,2], its stochastic form is causal-state minimality [6,7,8], its MDP form is exact state aggregation [9,10], and its categorical form is the coequalizer / final-coalgebra universal property [13,14,19]. The generated geometry is the Gromov visual metric on a tree boundary [24,25] and the Fisher–Rao geometry of a statistical manifold [31,32,33,34]. The genuinely novel parts are of unequal status: prime weighting (§5.2) and the Riemann “asymptotic lock” (§5.3) remain conjectural, while the solver line’s correctness results are externally verified self-evaluation — witnesses checked against the original instances by separate verifiers [154,155,156,157,158] — even though the Laplace-horizon derivation remains informal. Provenance determines independence; verification determines validity (§7.5).
Contribution. The unifying theorem is not new (Appendix D): it is the universal property of a quotient, i.e. the coequalizer, and it coincides definitionally with Myhill–Nerode, causal-state, bisimulation, and minimal-realization theory. What this paper offers is a common lens and a design criterion, not a new minimality theorem. Appendix D marks every cross-regime bridge as a consequence, an analogy, or a conjecture, and states what would upgrade it. The paper is integrated by design: the solver line (§6.2, §7.3, §7.5) is a reference implementation of the design criterion, and its correctness results are externally verified. §0 states exactly which evidence tier each claim occupies, so that the theory does not borrow the solver’s verification and the solver does not borrow the theory’s novelty.
Abstract
Computational systems face a single tension: retaining exhaustive history grows state without bound and paralyzes search, while discarding it prematurely causes irrecoverable commitment errors [6,7,42,45]. We formalize state reduction as a quotient of histories by future indistinguishability. We show the minimal sufficient state is that quotient and that it satisfies the universal factorization property of a coequalizer [19]; in the finite deterministic case this is the Myhill–Nerode theorem [1,2], in the stochastic case the causal states of computational mechanics [6,7], and in the MDP case exact state aggregation [9,10]. Geometry is then not imposed a priori but generated by distinguishability depth: projective limits of observation partitions yield ultrametric tree boundaries [24,25,26], whose continuous relaxation is the Fisher–Rao/natural-gradient geometry of the uncertainty simplex [31,32,34,35] together with a hyperbolic cusp completion [25,36]. Constraint compatibility is a presheaf local-to-global problem with Čech cohomological obstructions [37,38,39]. Thermodynamic relaxation under log-barrier and prime-weighted potentials is Lyapunov-stable [47,48,59,60]; multiplicative (log-domain) gating preserves gradient direction where additive penalties cancel [52,53]. Four instantiations follow: KV-cache quotienting [83,84,85,130,131], answer-preserving context compression [80,81,87,88,89,134,135], continuous non-greedy constraint solving [41,42,49,50,136,137,138,139], and a computability horizon set by the undecidability of stabilization [73,74,75,76,77,144,145,146,147]. Related recent work unifies these threads via categorical deep learning [101] and sheaf neural networks [110,111,112,113].
0. Claim map: how the theory and the solver line fit
This paper is deliberately integrated: it states a lens, builds one geometric construction for it, and reports a solver line that instantiates it. Keeping the parts together is a claim about the program, not a licence for one part to borrow another’s credibility. Each claim therefore carries its own evidence tier.
| Tier | Claims | Evidence | Does not licence |
|---|---|---|---|
| Background (standard) | quotient universal property (§2); ultrametric from refinement (§3.1); Fisher/natural-gradient flow and Lyapunov dissipation (§5.1); multiplicative gating (§6.1); undecidability horizon (§7.4) | published theorems [1,2,6,7,13,14,15,16,19,20,21,22,24,25,32,52,59,73,75,76] | novelty |
| New mathematics | cusp “well of uncertainty” and quadratic gradient quenching (§3.2); discovery-word lemma (§3.1); transfer criterion (§5.4) | proofs in-text [Eqs. §3.1–3.2]; convexity clause provable on Horn/submodular; parity obstruction from SOS lower bounds [166–174] | general necessary-and-sufficient characterization of when a relaxation realizes the quotient (open) |
| Proved (quantitative) | Chebyshev contraction and quotient-recovery rate (§5.5, Prop. 5.2, Cor. 5.1): identification in $O(\sqrt\kappa\log(D/\rho_0))$ | gradient-polynomial minimax proof [178]; requires a filtered method [175,176,177] | the quotient identification itself — conditional on clauses A and B of §5.4 |
| Proved (conditional) | Thm 5.2 conditional quotient realization: basin map is a well-defined surjection; recovery in $O(\tfrac1\mu\log(D/\rho_0))$ flow time (or $O(\sqrt\kappa\log)$ filtered) | proof in-text; attractor structure via Conley [179] | hypothesis (A) for a concrete class — open; submodular gives only the coarsest quotient [180] |
| Worked instances | 1-D double well: A1 holds, proved; 2-D Gaussian well: A1 fails for $A>\sigma^2/2$ by a saddle-node birth of a spurious minimum (§5.7) | explicit critical-point and Hessian classification | a rich-quotient class with no surplus index-0 components |
| Operational weakening | A1$'$ navigational accessibility (§5.8): the quotient is realized by branch-jump navigation over the Morse decomposition; BAHA operationalizes it | fracture $=$ fold, Lambert-W $=$ fold continuations [61,154,155,162] | A1$'$ proved for a class; false-positive control of the detector |
| SOS-certified A1 | Lemma 5.1 (§5.7.3): a Positivstellensatz certificate of no unlabeled index-$0$ critical points proves A1 exactly on the labeled wells; the fold $\tfrac{x^3}{3}-\mu x$ is the birth mechanism | certificate searched in the Lasserre/SOS hierarchy [55,56,182,183,184] | a rich-quotient class whose certificate exists at bounded degree |
| Externally verified self-evaluation | solver correctness: clause-checked assignments; 10/10 colouring; client-verified hospital schedule; planted $n=400,\alpha=4.0$ 5/5; BAHA’s solved instances; FUTCache exact novelty set $U_\varepsilon(H)$ | independent checkers [154,155,156,157,158]; brute-force oracle equivalence, 134 C tests, exhaustive optimum for $n\le16$ [159] | comparative SOTA; generalization; that the geometry caused the results |
| Self-measured | BAHA effect sizes (+18%, attribution); SUTRA-vs-CP-SAT 9/10; throughput/scaling; 99–100% band; FUTCache 1M-trace suppression and CDCL geometry prediction | self-run harness [160] | anything beyond those specific runs |
| Conditionally proved (formalized) | Riemann-lock algebra (§5.3): downstream implication machine-checked
in Lean 4, no sorry/axiom/admit
[164] |
Lean proof; the hard inputs are named hypotheses, not discharged | that the hypotheses hold |
| Conjecture | prime weighting (§5.2) | consistency arguments | reliability |
| Proposal (no experiments) | evidence compression (§7.2) | — | empirical status |
The integration thesis is narrow and, in principle, testable: the same design criterion — forget when distinctions cease to matter; decide when alternatives cease to differ — organizes both the abstraction theory and the solver’s state/commitment policy. The solver line is a reference implementation of that policy, and its correctness results are externally verified. It is not evidence for the quotient universal property (which is standard), and the universal property is not evidence that the solver works. Connecting them is the open programme (transfer theorem, §D.3.1; mechanism ablation, gap G7).
1. Introduction: premature commitment
Complexity is usually framed as scaling in time and space. The operative failure mode is different: premature commitment. A DPLL/CDCL solver assigns a variable on local evidence (activity counters, phase heuristics) and irrevocably bisects the space; near the random 3-SAT clustering threshold $\alpha\approx4.267$ these miscommitments multiply exponentially and the search fragments [3,41,42]; the clustering transition separating the easy and hard phases was located by entropy computations [43] and characterized via Gibbs states [44]. The opposite pathology is indiscriminate retention: keeping the full history $H_t=(a_0,\dots,a_t)$ exhausts memory, while recency-based forgetting (LRU, sliding attention windows [86], greedy beam pruning) discards distinctions that still carry predictive power, producing catastrophic forgetting [7,8,80,84].
Thesis. Computation is progressive commitment under generated geometry. Each step is dual: forget distinctions that can no longer affect any admissible future (the future-indistinguishability kernel), and decide by pruning futures incompatible with accumulated constraints. The geometry of the state space is not an ambient container; it is generated by distinguishability. Both halves are classical: forgetting is quotienting by the right congruence [1,2] / causal equivalence [6,7] / bisimulation [15,16] / the best abstraction of a Galois connection [17,18]; deciding is the restriction of admissible continuations. What is assembled here is the unification across the discrete, continuous, and memory regimes.
2. The universal factorization theorem
Setup. Let $\mathcal{H}$ be histories, $\mathcal{W}$ continuations, $\mathcal{O}$ outcomes, and $F:\mathcal{H}\times\mathcal{W}\to\mathcal{O}$ the evaluation map [13,21,22]; this is the predictive-state / POMDP view of state [95,96,97].
Definition 2.1 (future equivalence). $h_1\sim_{\mathcal{W}} h_2$ iff $\forall w\in\mathcal{W},\,F(h_1,w)=F(h_2,w)$. Write $\mathcal{M}^*=\mathcal{H}/\!\sim_{\mathcal{W}}$ with projection $Q$.
Definition 2.2 (future-sufficient representation). A pair $(M,R)$ with $R:\mathcal{H}\to M$ is future-sufficient if some $\Phi:M\times\mathcal{W}\to\mathcal{O}$ satisfies $\Phi(R(h),w)=F(h,w)$.
Theorem 2.1 (universal factorization). (1) $(\mathcal{M}^*,Q)$ with $\bar F([h],w):=F(h,w)$ is future-sufficient. (2) For every surjective future-sufficient $(M,R)$ there is a unique $\phi:M\to\mathcal{M}^*$ with $Q=\phi\circ R$.
Proof. (1) Well-definedness is exactly the substitution property of an equivalence relation. (2) Define $\phi(m)=Q(h)$ for any $h\in R^{-1}(m)$; future-sufficiency forces $F(h_1,\cdot)=F(h_2,\cdot)$ on the fibre, so $\phi$ is well-defined; commutativity and uniqueness are immediate. $\blacksquare$
This is not a new theorem: it is the universal property of the coequalizer of the kernel pair in $\mathbf{Set}$ [19,20], and simultaneously the minimal realization theorem for deterministic systems [21,22]; the same universal property organizes categorical deep learning [101,102,103] and geometric deep learning [151]. Specialized:
| Setting | Equivalence | Quotient |
|---|---|---|
| DFA / regular language | $x\equiv_L y$ iff $\forall z,\ xz\in L\Leftrightarrow yz\in L$ | minimal DFA [1,2,3,4,5]; cascade decomposition [23] |
| Stochastic process | same conditional future distribution | causal states / $\epsilon$-machine [6,7]; PSRs [95] |
| Labeled transition system | bisimulation | bisimulation quotient [15,16] |
| MDP (exact / approximate) | same value & dynamics; quantitative bisimulation metrics | exact aggregation [9,10]; bisimulation metrics [11]; near-optimal guarantees [12]; homomorphisms [98,99] |
| Abstract interpretation | Galois connection $(\alpha,\gamma)$ | best abstraction $\alpha$ [17,18] |
Corollaries. Minimal sufficient representations are unique up to unique isomorphism; redundant distinctions are $\ker\phi$; and refining is safe while coarsening is not quotiented correctly [1,2,17,18]; these quotients are computed by partition refinement [4,100].
Monotone coarsening. If $\mathcal{W}_{t+1}\subseteq\mathcal{W}_t$ then $h_1\sim_{\mathcal{W}_t}h_2\Rightarrow h_1\sim_{\mathcal{W}_{t+1}}h_2$. Hence commitment shrinks $\mathcal{W}$, coarsens $\sim_{\mathcal{W}}$, and enlarges equivalence classes, licensing erasure. Deciding without coarsening is exactly the premature-commitment error [3,41,42].
3. Generated geometry
3.1 Discrete regime: projective limits generate an ultrametric
Let $\mathcal{P}_0\prec\mathcal{P}_1\prec\cdots$ be a refining sequence of partitions of an execution space. For a trace $L$ let $D_j(L)$ be its discovery word — cells of $\mathcal{P}_j$ in order of first encounter, re-entries deleted. Refinement induces bonding maps $q_j:X_{j+1}\to X_j$, which are compatible: $q_j(D_{j+1}(L))=D_j(L)$. This is the standard trace / partial-order projection: discovery words are normal forms of interleavings under a Mazurkiewicz trace equivalence [28]; partial-order reduction computes representatives of these classes [29], and event structures supply the underlying concurrent semantics [30]. The inverse system has projective limit $X_\infty=\varprojlim X_j$, compact Hausdorff and non-empty by Tychonoff [20,26].
Separation index $k(x,y)=\inf\{j:x_j\ne y_j\}$ and generated metric $d(x,y)=2^{-k(x,y)}$ give the strong triangle inequality $d(x,z)\le\max\{d(x,y),d(y,z)\}$; hence $(X_\infty,d)$ is a complete, totally disconnected ultrametric space (all balls clopen).
Tree identification. Building the prefix tree $\mathcal{T}$ with vertices $\bigcup_j X_j$, the Gromov product equals lowest-common-ancestor depth, $(u\mid v)_o=\operatorname{depth}(u\wedge v)$, and the visual metric on the Gromov boundary is $d_{\partial\mathcal{T}}(\xi,\eta)=2^{-k(\xi,\eta)}$ [24,25]. So $(X_\infty,d)\cong\partial\mathcal{T}$ isometrically: distance is accumulated failure of indistinguishability. This is the same construction as the ultrametric of a profinite group [26] and of a hierarchical clustering dendrogram [27]; the ultrametric geometry of replica-symmetry-broken spin glasses [92,93] is the physical instance, and ultrametric embedding is a standard ML primitive [108,109].
3.2 Continuous regime: the uncertainty simplex and its completion
Relax $x_i\in\{0,1\}$ to $x_i\in[0,1]$, with $x_i=\tfrac12$ maximal uncertainty and $x_i\in\{0,1\}$ certainty. The natural geometry on this simplex is not Euclidean but the Fisher–Rao metric
the unique (Chentsov) invariant metric of the Bernoulli family [31,32,33]. The induced gradient flow is natural gradient / entropic mirror descent,
whose inverse metric vanishes at the certainty vertices [32,34,35]. The map $z_i\mapsto x_i$ with $z_i=0\leftrightarrow x_i=\tfrac12$, $|z_i|=1\leftrightarrow x_i\in\{0,1\}$ embeds the simplex in the disk $\mathbb{D}$.
Consistency erratum (original §3.4–3.5 vs §5.2). The original paper uses two different inverse metrics: $g^{z\bar z}=\tfrac14|z|^2(1-|z|^2)^2$ (varnishing at the centre) and $g^{ii}=x_i(1-x_i)$ (vanishing at the vertices). These are not the same geometry. We record both roles: the Fisher metric gives the standard, well-posed natural-gradient dynamics of §5; the cusp conformal metric below gives a design-time “well of uncertainty” and should not be conflated with it.
The cusp completion with conformal factor $\Omega(z)=2/(|z|(1-|z|^2))$, i.e. $ds^2=4|dz|^2/(|z|^2(1-|z|^2)^2)$, is a complete hyperbolic-type metric on $\mathbb{D}\setminus\{0\}$ with a cusp at the origin [25,36,104]; hyperbolic embeddings are now standard for hierarchical data [105]. The radial length $\int_\epsilon^R \tfrac{2\,dt}{t(1-t^2)}=\ln\!\big(\tfrac{t^2}{1-t^2}\big)\big|_\epsilon^R\to\infty$ as $\epsilon\to0^+$: the origin (maximal uncertainty) is at infinite geodesic distance from every interior point. Under this metric the Riemannian gradient quenches quadratically,
so isolated or weak constraints exert vanishing drive at maximal uncertainty; only collective constraint pressure of order $|z|^{-2}$ can lift a variable out of the well. This is a designed barrier, not a theorem about SAT; the standard, physically grounded realization of the same “slow near the boundary” effect is natural-gradient/mirror descent [32,34,35]; piecewise-linear relaxations admit a tropical-geometry reading [106], and distances between such generated geometries are measured by optimal transport [107].
4. Compatibility and cohomological obstruction
Let $V=\{x_1,\dots,x_n\}$ and constraints $\mathcal{C}$ over variable supports. The presheaf of local solutions $\mathcal{F}$ assigns to $U\subseteq V$ the partial assignments satisfying all constraints fully inside $U$, with restriction maps $\rho^W_U(\sigma)=\sigma|_U$. Global solutions are global sections $\Gamma(V,\mathcal{F})=\varprojlim_U\mathcal{F}(U)$; a solution exists iff $\Gamma\ne\emptyset$. This is the standard sheaf formulation of constraint networks [37,38,39,40]; sheaf neural networks generalize graph convolution via the sheaf Laplacian [111]; neural sheaf diffusion shows that the learned sheaf structure controls heterophily and oversmoothing [110]; connection-Laplacian variants learn the restriction maps [112]; and [113] surveys the area. Sheaf cohomology can itself encode counting hardness [114].
For a cover $\mathcal{U}=\{U_i\}$ and a coefficient module $\mathcal{A}$ (e.g. $\mathbb{Z}_2$), pairwise compatibility is the 1-cocycle condition $\delta^0\sigma=0$, with $(\delta^0\sigma)_{ij}=\rho^{U_j}_{U_{ij}}\sigma_j-\rho^{U_i}_{U_{ij}}\sigma_i$. Failure of local-to-global gluing is measured by the Čech class $[\omega]\in\check H^1(\mathcal{U},\mathcal{F})=\ker\delta^1/\operatorname{im}\delta^0$ [37,38,39]. The same formalism detects contextuality obstructions in physical systems [37].
Discipline. Cohomology is a language for obstructions to section extension, not a complexity lower bound. Satisfiable instances can be exponentially hard (cryptographic/planted problems), and unsatisfiable instances with $[\omega]\ne0$ can be easy: 2-SAT is linear-time solvable [Aspvall–Plass–Tarjan], Horn-SAT and GF(2) linear systems are polynomial [40, Schaefer]. Hence
5. Dynamical relaxation and spectral competition
5.1 Free energy and Lyapunov stability
Let $x\in(0,1)^n$ and
with graph-Dirichlet kinetic term $E_{\text{kin}}=\tfrac12\operatorname{Tr}(x^\top Lx)$ ($L=D-A$ the constraint-graph Laplacian [56,57,58]), a log-barrier potential
and Bernoulli entropy $S[x]=-\sum_i\big(x_i\ln x_i+(1-x_i)\ln(1-x_i)\big)$. The flow $\dot x_i=-x_i(1-x_i)\partial_{x_i}F$ is the natural-gradient/mirror flow of §3.2 [32,34,35,47]; nonconvex convergence guarantees for it are established in [118]. Loss landscapes of this kind share glassy statistical-mechanics structure with disordered systems [115,116], whose stiffness controls generalization [117].
Theorem 5.1 (monotone dissipation). $F$ is a strict Lyapunov function: $\dot F=-\sum_i x_i(1-x_i)(\partial_{x_i}F)^2\le0$, with equality iff $\nabla F=0$; entropy forces $-\tfrac1\beta\partial_{x_i}S\to\mp\infty$ at $x_i\to0^+/1^-$, so trajectories are confined to the open cube and converge to the largest invariant set inside $\{\dot F=0\}$ by LaSalle’s invariance principle [47,59,60]. Landauer’s bound fixes the erasure cost [119], reversible computing shows that bound is approachable [120], and the free-energy principle [121] supplies a competing variational formulation; predictive-state entropy carries a known thermodynamic cost [122]. The log-barrier is precisely Nesterov–Nemirovskii self-concordant barrier theory; $\epsilon_0>0$ is a standard smoothing [47,48]. $\blacksquare$
5.2 Prime weighting: anti-resonance by linear independence
Assign clause $c$ weight $W(p_c)=(1+\ln p_c)^{-1}$ for the $c$-th prime $p_c$.
Proposition 5.1. $\{\ln p_i\}$ is $\mathbb{Q}$-linearly independent.
Proof. $\sum q_i\ln p_i=0$ clears to $\prod p_i^{c_i}=1$; unique factorization forces all $c_i=0$. $\blacksquare$ [72,71]
This is exactly the hypothesis of the Kronecker–Weyl equidistribution theorem: independent logs give dense, non-resonant joint phases, so the weighted force field cannot phase-lock into accidental harmonic cancellation [71,72]. Equivalently, in log-domain the clause sum is a product of experts [52] and a deterministic instance of multiplicative weights [54,55].
Correction. The original claims $\sum_{c\le K}W(p_c)\sim K$. By the prime number theorem, $W(p_c)\asymp1/\ln c$ and $\sum_{c\le K}1/\ln c=\Theta(K/\ln K)$, so the correct asymptotic is $M_K=\Theta(K/\ln K)$; the linear claim is off by a factor $\ln K$ [72].
5.3 Spectral gap vs. arithmetic fluctuation
Two exponents govern large-scale stability:
- Geometric weakening. Algebraic connectivity (Fiedler value) decays as $\lambda_2(G_K)\asymp K^{-\gamma}$; Fiedler’s algebraic connectivity defines the quantity [56], Cheeger-type inequalities relate the gap to graph expansion [57], and mixing-time bounds connect spectral separation to diffusion rates [58].
- Prime fluctuation. By the explicit formula, $\pi(x)=\operatorname{Li}(x)+\mathcal{O}(x^\sigma\log x)$ with $\sigma=\sup\{\operatorname{Re}\rho:\zeta(\rho)=0\}$; the relative weight variance scales as $\Phi(K)\asymp K^{\sigma-1}$ [67,68].
Stability criterion (heuristic). Linearizing the slowest graph mode, $\dot{\delta x}_2=-\lambda_2(G_K)\delta x_2+\Xi(K)$; the perturbation is dominated when $\Phi/\lambda_2\asymp K^{\sigma-1+\gamma}\to0$, i.e.
Unconditional anchor. Bombieri–Vinogradov gives averaged equidistribution of primes in progressions to level $\theta=\tfrac12$, i.e. an averaged $\Phi(K)\asymp K^{-1/2}$ without RH [64,65,66]; prime fluctuations are themselves random-matrix distributed at leading order [123,124,125], with unconditional regularity from short-interval and prime-gap results [126,127]. Two competing spectral interpretations of the zeros are Connes’ trace-formula program [69] and the Berry–Keating quantum-chaos heuristic [70].
The Riemann lock. If a constructible constraint
family achieves the critical barrier $\gamma\to\tfrac12$, then $1-\sigma>\tfrac12$ forces $\sigma<\tfrac12$; since zeros on the
critical line exist (Hardy) and the functional equation pairs $\rho\leftrightarrow1-\bar\rho$, stability
then requires $\sigma=\tfrac12$ — the
Riemann Hypothesis. The Bost–Connes system provides an arithmetic model
of exactly this kind of phase transition [94]. This is a
conditional equivalence, not a proof, and it remains
open whether such a family exists [67,68]. The downstream implication is
now machine-checked:
ConditionalAsymptoticLock.lean proves, with no
sorry, axiom, or admit, that
under (i) the linear-coupling threshold equality and (ii) the
existence of a critical graph family, asymptotic stability on that
family is equivalent to $\sigma\le\tfrac12$ [164]. Its status is
therefore conditionally proved, not conjectural: the
exponent algebra is verified, while the analytic/spectral hypotheses —
and the existence of the critical family — remain the open inputs
[67,68].
5.4 Transfer criterion: when a relaxation realizes the quotient
Criterion. A continuous relaxation can realize a behavioral quotient when the discrete problem admits an exact convexity preserved by the relaxation, the observables separate quotient classes, and the resulting basins are uniformly conditioned; parity-type affine structure provides a canonical obstruction.
The three clauses are the hypotheses needed for the three obligations of the transfer theorem (Appendix D.3.1):
- Convexity preserved (correctness). The energy must admit an exact convex or discrete-convex extension whose minimizers are integral: median/CAT(0) closure (majority polymorphism, 2-SAT/bijunctive) [168,171], lattice semilinearity (Horn/dual-Horn), submodularity via the Lovász extension [169], or M/L-convexity [170]; bounded treewidth admits exact junction-tree decomposition [174]. This is the discrete version of “generated geometry” made literal — the solution set is a CAT(0) cube complex — and only here does the closure above buy exactness rather than analogy.
- Separation (injectivity). The observables in $\mathcal W$ must distinguish every $\mathcal W$-inequivalent pair; otherwise distinct quotient classes share a basin and the metric bound fails regardless of how well the flow behaves.
- Uniform conditioning (computability and basin refinement). A uniform isolation radius and spectral gap on each basin, together with bounded degree/curvature, yield the computable bi-Lipschitz constants. §5.1 gives global dissipation but not this uniform gap, which is precisely what the $1-\sigma>\gamma$ heuristic of §5.3 was reaching for.
Canonical obstruction. Affine structure (parity/XOR) is tractable but not relaxable: it is closed under no median, lattice, or submodular convexity in $[0,1]^n$, and its LP/SOS relaxations have degree $\Omega(n)$ [172,173]. Tractability of the discrete problem is therefore necessary but not sufficient. More generally, a no-free-lunch boundary applies: if the transfer holds on a class $\mathcal C$ and equilibria are findable in polynomial time, then $\mathrm{CSP}(\mathcal C)\in \mathrm P$, so the realizable class lies inside the tractable side of Schaefer’s dichotomy [166,167] and is in general strictly smaller.
Consequence for the thesis. Geometry is not generated by distinguishability in general; it is available exactly when the discrete problem is already convex in the right sense. Where it is, a relaxation realizes the quotient; where it is not — general 3-SAT, parity at low degree — no convex relaxation can.
5.5 Quantitative recovery rate: conditioning $\Rightarrow$ computable identification
The third clause of §5.4 is quantitative, and on a quadratic basin its exact rate is a Chebyshev minimax problem — the clean object that the spectral heuristic of §5.3 was groping for.
Setup. Let a behavioral class $m$ have representative attractor $x_m$, let $e_0=x_0-x_m$, and suppose that on its basin $F(x)=\tfrac12\langle x-x_m,H(x-x_m)\rangle$ with $H=H^\top\succ0$ and $\mu I\preceq H\preceq LI$, $\kappa=L/\mu$. Any degree-$t$ gradient-polynomial method with fixed point $x_m$ has error $e_t=p_t(H)e_0$ with $\deg p_t\le t$ and $p_t(0)=1$ (the normalization says a zero-curvature mode is left unchanged). Hence $\|e_t\|\le\max_{\lambda\in[\mu,L]}|p_t(\lambda)|\,\|e_0\|$, and the optimal worst-case contraction is
Proposition 5.2 (Chebyshev contraction). The unique minimax polynomial is
and $\max_{\lambda\in[\mu,L]}|p_t^\star(\lambda)|\le 2\big(\tfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\big)^t$. Consequently
Proof. Put $z(\lambda)=\tfrac{L+\mu-2\lambda}{L-\mu}$, so $[\mu,L]\to[-1,1]$ and $\lambda=0\mapsto a=\tfrac{\kappa+1}{\kappa-1}>1$. The problem becomes $\inf_{\deg q\le t,\,q(a)=1}\max_{z\in[-1,1]}|q(z)|$, whose unique solution is $q_t^\star=T_t/T_t(a)$ (Chebyshev extremal property [178]). Since $|T_t|\le1$ on $[-1,1]$, the value is $1/T_t(a)$; and $T_t(a)=\cosh(t\operatorname{arcosh}a)\ge\tfrac12(a+\sqrt{a^2-1})^t$ with $a+\sqrt{a^2-1}=\tfrac{\sqrt\kappa+1}{\sqrt\kappa-1}$. $\blacksquare$
Corollary 5.1 (Chebyshev Quotient-Recovery). If representatives of distinct classes satisfy $\|x_m-x_{m'}\|\ge\rho_0$ ($m\neq m'$), the balls $B(x_m,\rho_0/2)$ are disjoint, and the class is uniquely identifiable once $\|x_t-x_m\|<\rho_0/2$. Writing $D=\|x_0-x_m\|$, this holds after
optimally filtered first-order iterations.
Scope (where this can be attacked). (i) The exact residual-polynomial argument is a theorem for a quadratic basin, i.e. linearized dynamics with a fixed self-adjoint Hessian; for a general nonlinear strongly convex basin the rate $O(\sqrt\kappa\log(1/\varepsilon))$ still holds but via accelerated methods [176], not this proof. (ii) The $\sqrt\kappa$ rate requires a filtered first-order method (Chebyshev semi-iteration or conjugate gradients [175,177]); plain gradient descent — and the continuous flow $\dot x=-g^{-1}\nabla F$ of §5.1 — contracts at $1-O(1/\kappa)$, a factor $\sqrt\kappa$ slower. The lemma therefore does not apply to the flow as written. (iii) It recovers the class given the attractor–class correspondence (clause A of §5.4); it does not establish that correspondence. It is the quantitative half of C, conditional on A and B.
What the spectral heuristic was reaching for. The useful object is the minimax polynomial $T_t$ over the relaxation spectrum, not the zeta-zero exponent $\sigma$; §5.3’s $1-\sigma>\gamma$ is a proxy for $\kappa$ being uniformly bounded.
5.6 Conditional quotient realization (the transfer theorem)
The three clauses of §5.4 compose into a conditional theorem whose only non-trivial hypothesis is exactness (A).
Theorem 5.2 (conditional quotient realization). Let $\Phi$ be a finite constraint system with behavioral quotient $Q:X\to\mathcal M^*$, and let $(K,F_\Phi)$ be a $C^2$ relaxation with rounding $r:K\to X$ and dynamics $\dot x=-\nabla F_\Phi$ (projected to $K$). Assume:
- (A) Exactness. Every reachable attracting component $A_m$ of the flow is associated with exactly one class $m$, with $r(A_m)\subseteq Q^{-1}(m)$; and every class has a reachable component with non-empty basin.
- (B) Separation. $\operatorname{dist}(A_m,A_{m'})\ge\rho_0>0$ for $m\neq m'$.
- (C) Conditioning. On a neighbourhood $U_m$ of each $A_m$, $\mu I\preceq\nabla^2F_\Phi\preceq LI$.
Then:
- The basin map $\pi_\Phi(x)=m$ for $x\in B_m$ is well-defined, and $\pi_\Phi:\bigsqcup_m B_m\to\mathcal M^*$ is a surjection.
- For any $m$ and $x(0)\in U_m$ with $x_m\in A_m$, $\|x(t)-x_m\|\le e^{-\mu t}\|x(0)-x_m\|$, so the class is identified after $t=O\!\big(\tfrac1\mu\log(D/\rho_0)\big)$ flow time with $D=\|x(0)-x_m\|$; with a filtered first-order method the conditioning dependence sharpens to $O(\sqrt\kappa\log(D/\rho_0))$ (Prop. 5.2, Cor. 5.1).
Proof. (1) If $x\in B_m\cap B_{m'}$ then $\omega(x)\subseteq A_m\cap A_{m'}=\varnothing$ by (B), so $m=m'$; surjectivity is (A). (2) On $U_m$, $F$ is $\mu$-strongly convex and $\nabla F(x_m)=0$, so $\tfrac{d}{dt}\tfrac12\|x-x_m\|^2=-\langle x-x_m,\nabla F(x)-\nabla F(x_m)\rangle \le-\mu\|x-x_m\|^2$; Grönwall gives the exponential bound [60]. Separation makes $B(x_m,\rho_0/2)$ a unique-class certificate, and $e^{-\mu t}D<\rho_0/2$ gives the time. The $\sqrt\kappa$ form is Prop. 5.2. $\blacksquare$
Attractor structure is Conley’s. The “attracting components” above are exactly isolated invariant sets in a Morse decomposition, and the basin map is the associated Morse-order projection [179]; (B) is isolation plus separation.
All the content is in (A). (B) is an isolation assumption and (C) is local; (A) is the entire transfer claim. Note also that (C) is strong convexity per basin, not global convexity: $F$ may be non-convex, and must be, if the quotient is to be rich (see below).
A degenerate instance, and the trap. Submodular energies are the cleanest exact case: for submodular $f$ the Lovász extension $\hat f$ is convex and $\min_{[0,1]^n}\hat f=\min_S f(S)$, with layer-cake thresholding of a minimizer yielding discrete minimizers for almost every threshold [169]. But a convex $\hat f$ has a single convex minimizer set, hence a single attracting component. So a submodular relaxation realizes the quotient only when $|\mathcal M^*|=1$ — the coarsest quotient. A rich quotient requires a non-convex $F$ with several basins, which means (A) must be established by Morse-theoretic rather than convexity arguments [180]: non-degenerate critical points with index $0$ in bijection with $\mathcal M^*$, and no critical point whose rounding lies outside a satisfying class. That is the honest target; the submodular case is the warm-up, not the bridge.
5.7 Two worked non-convex instances: A1 holding and failing
5.7.1 One dimension: A1 holds
Let $X=\{-1,+1\}$, $\mathcal M^*=\{[-1],[+1]\}$, and $F(x)=\tfrac14(x^2-1)^2$, with flow $\dot x=-F'(x)=x(1-x^2)$. Then $F'(x)=x(x^2-1)$ vanishes only at $\{-1,0,+1\}$, and $F''(x)=3x^2-1$ gives $F''(\pm1)=2>0$, $F''(0)=-1<0$. Hence $\operatorname{Crit}_0(F)=\{-1,+1\}$ with the origin an index-$1$ saddle whose stable manifold is $W^s(0)=\{0\}$; the basins are $W^s(-1)=(-\infty,0)$ and $W^s(+1)=(0,\infty)$. With the rounding $r(x)=\operatorname{sign}(x)$ the diagram $Q\circ r=\pi\circ\omega$ commutes on $\mathbb R\setminus\{0\}$, so $\operatorname{Crit}_0(F)\cong\mathcal M^*$. Crucially, “no spurious minima” is proved, by solving $F'=0$ and classifying every root through $F''$ — not assumed. Surplus index-$0$ components are the only way A1 can fail.
5.7.2 Two dimensions: a deliberately created spurious minimum (A1 fails)
Let $X=\{-1,+1\}^2$ with the four singleton classes, and
The origin is critical for every $A$, with
So the origin is an index-$0$ minimum exactly when $A>A_c:=\sigma^2/2$, and an index-$2$ maximum when $A<A_c$. The four corners remain non-degenerate minima whenever $A\,e^{-2/\sigma^2}$ is small; e.g. at $\sigma=\tfrac12$, $A=1$ the corner Hessian is $\begin{pmatrix}1.98&-0.02\\-0.02&1.98\end{pmatrix}\succ0$.
Therefore for $A>A_c$, $\operatorname{Crit}_0(F_{A,\sigma})\supseteq\{(\pm1,\pm1)\}\cup\{(0,0)\}$ has at least five elements while $|\mathcal M^*|=4$. No $\pi:\operatorname{Crit}_0\to\mathcal M^*$ is a bijection; the origin has a positive-measure basin and rounds to no behavioral class, so A1 fails and the relaxation does not realize the quotient.
The threshold $A_c$ is a saddle-node bifurcation: the origin’s Hessian eigenvalue crosses zero, and a spurious well is born there [181]. This is the generic mechanism by which a continuous relaxation acquires a spurious attractor, and hence the generic obstruction to A1.
The 1-D instance satisfies this; the 2-D instance violates it for $A>A_c$. The general task is thus to control the perturbation so that no surplus well is born — which is a concrete analytic obligation, not an assumption.
5.7.3 SOS-certified realization: A1 proved, not assumed
The two instances above were analyzed by hand. The general statement is a certificate condition, which makes A1 checkable rather than assumed.
Lemma 5.1 (SOS-certified Morse realization of a finite quotient). Let $F:\mathbb R^n\to\mathbb R$ be a coercive polynomial and let $W_1,\dots,W_k$ be disjoint semialgebraic neighbourhoods labeled by the classes $m_1,\dots,m_k$ of $\mathcal M^*$, with $k=|\mathcal M^*|$. Suppose:
- each $W_i$ contains exactly one critical point $x_i$ of $F$;
- $\nabla^2F(x_i)\succ0$, so $x_i$ has Morse index $0$;
- there is a Positivstellensatz certificate that the set $$\Big\{\,x\notin\bigcup_i W_i:\ \nabla F(x)=0,\ \nabla^2F(x)\succeq0\,\Big\}$$ is empty;
- the rounding $r$ is constant on each attracting basin and $r(W_i)\subseteq Q^{-1}(m_i)$.
Then $\operatorname{Crit}_0(F)=\{x_1,\dots,x_k\}$, and $\pi:\operatorname{Crit}_0(F)\to\mathcal M^*$, $\pi(x_i)=m_i$, is a bijection. So A1 holds.
Proof. By (1)–(2), each $x_i$ is a non-degenerate local minimum and these are the only critical points of $F$ inside the $W_i$. By (3), every critical point outside $\bigcup_i W_i$ has a negative-curvature direction and is therefore not a local minimum. Hence the local minima of $F$ are exactly $\{x_i\}$. Clause (4) makes the class assignment well-defined on basins; with $k=|\mathcal M^*|$ and distinct labels, $\pi$ is a bijection. $\blacksquare$
The certificate. Since $\nabla F=0$ are polynomial equalities and $\nabla^2F\succeq0$ is semialgebraic (all principal minors $\ge0$), the excluded set is semialgebraic and its emptiness can be certified by an identity $$-1=\sigma_0+\sum_j\sigma_j g_j+\sum_\ell h_\ell\,\frac{\partial F}{\partial x_\ell}+\text{PSD terms},$$ with the $\sigma_j$ sums of squares and the $g_j$ describing the complement of $\bigcup_i W_i$ [182,183]. In practice the certificate is searched at increasing degree in the Lasserre/SOS hierarchy [55,56,184]; coercivity of $F$ (equivalently, an added constraint $\|x\|^2\le R^2$) supplies the Archimedean hypothesis.
Scope. The certificate is sufficient, not necessary, and its existence at a fixed degree is not guaranteed: for hard instances the required degree grows, consistent with the parity obstruction [172,173]. Lemma 5.1 therefore turns A1 into a checkable obligation whose degree is the complexity measure — trivial in the submodular case ($k=1$), expensive exactly where the quotient is rich and the language is hard.
Birth of surplus attractors: the fold. As a control parameter varies, the Morse structure changes through folds, with normal form [181] $$V_\mu(x)=\tfrac{x^3}{3}-\mu x,\qquad V_\mu'(x)=x^2-\mu:$$ no real critical pair for $\mu<0$, a degenerate fold at $\mu=0$, and for $\mu>0$ a minimum $x_+=+\sqrt\mu$ and a maximum $x_-=-\sqrt\mu$. The birth of a (minimum, saddle) pair is exactly the event at $A_c$ in §5.7.2. If the newborn index-$0$ component carries no behavioral class, then $\#\operatorname{Crit}_0>|\mathcal M^*|$, A1 fails, and the certificate of Lemma 5.1 ceases to exist. A BAHA-style fracture detector estimates this event, and branch jumping is the runtime response (§5.8).
5.8 BAHA: operational navigation of the Morse decomposition
The failure mode of §5.7 — a surplus index-$0$ component, or a suboptimal basin — is exactly what BAHA detects and acts on, which gives the transfer theorem an operational form rather than a purely existence-theoretic one.
- Fracture $=$ fold. BAHA declares a fracture when the log-partition slope $\rho=|d/d\beta\log Z|$ and its variance (the heat-capacity/susceptibility proxy, since $d^2/d\beta^2\log Z=\operatorname{Var}(E)$) exceed thresholds [162]. Thermodynamically this is the phase transition; dynamically it is the fold (saddle-node) at which $\nabla^2F$ acquires a zero eigenvalue — the same event as $A_c$ in §5.7.2.
- Lambert-W branches $=$ the two continuations through the fold. Near criticality the mean-field order parameter obeys $ue^u=\xi$, whose real branches $W_0$ and $W_{-1}$ are the two stable continuations [61]; Proposition 1 of [155] asserts they enumerate all thermodynamically stable continuations to leading order in $\beta-\beta_c$ (mean-field scope). Lambert-W is thus the normal form of the A1 transition.
- Branch jumping $=$ Morse navigation. Instead of requiring a single flow to reach every index-$0$ component (A1), BAHA detects when its current basin is suboptimal and samples another component [162].
This motivates a weaker, more realistic accessibility condition in place of A1:
A1$'$ (navigational accessibility). Every behavioral class is reachable from some admissible initial state by a finite sequence of gradient descents interleaved with fracture-triggered branch jumps.
If A1$'$ holds together with the separation and conditioning (B), (C), then Theorem 5.2 still yields a well-defined class map on the reachable Morse components, and the quotient is realized by the navigation policy rather than by a single flow. This is the honest, implementable form of the transfer: BAHA is the search over the Morse decomposition that (A) assumes.
Empirical status, stated honestly. BAHA’s own case studies report that fractures are frequent but branch jumps are selective (599 fractures / 4 jumps on VRP; 499 / 8 on network design) [162]: the detector has many false positives and the policy must filter them. That is the operational analogue of the spurious-minimum problem — separating actionable transitions from nuisance ones. The reported ablation gains (fracture detection alone $\approx+18\%$ over SA, [155]) are self-measured, not replicated.
6. Multiplicative gating and thermodynamic transitions
6.1 Direction preservation vs. additive cancellation
Additive penalties $\mathcal L_{\text{add}}=\mathcal L_{\text{data}}+\mu\mathcal L_{\text{constr}}$ produce conflicting gradients that cancel ($\langle\nabla\mathcal L_{\text{data}},\nabla\mathcal L_{\text{constr}}\rangle<0$), the multi-task failure mode addressed by gradient surgery [53] and surveyed in constrained-optimization learning [128]. Multiplicative gating instead sets $\mathcal L_{\text{mult}}=\mathcal L_{\text{data}}\cdot C(v)$, so
Proposition 6.1. On the subspace $\nabla_\theta v=0$ the direction is invariant, $\nabla_\theta\mathcal L_{\text{mult}}\propto\nabla_\theta\mathcal L_{\text{data}}$; off it the data gradient is rescaled, never cancelled. This is the product-of-experts combination rule [52,129] in log space, i.e. an adaptive volume control rather than a competing steering wheel.
Euler gate. $G(v)=\prod_{p\in\mathcal P_{\text{gate}}}(1+p^{\tau v})$ ($G(0)$ normalizable to 1) grows at rate $\sum\tau\ln p$; combined with a self-concordant exponential barrier $B(v)=e^{\kappa v}$, take $C(v)=\max(G(v),B(v))$. Small primes penalize macro-violations, large primes micro-violations; the barrier expels infeasible configurations without rotating the task direction [47,48,54,55].
6.2 Thermodynamic fracture and the Lambert-W jump
As $\beta$ increases, the free-energy landscape of spin-glass-like systems fractures; the clustering transition of random $k$-SAT is the canonical example, and survey propagation is the standard algorithm that jumps the fracture rather than descending into it [41,42,43,44,92,93]. Writing $\Phi(\beta)=\ln Z(\beta)$, the moments are $\langle E\rangle_\beta=-\partial_\beta\ln Z$ and $\operatorname{Var}_\beta(E)=\partial^2_\beta\ln Z$. Near a fold $\beta-\beta_c=u$ with $ue^u=\xi$, the escape jump obeys the fold normal form of catastrophe theory [62,63] and is solved by the principal Lambert-W branch, $\Delta\beta=W_0(\xi)$ [61, Section 6.3]. Using $k!\approx(k/e)^k$ to set the Laplace horizon $k_{\max}\approx T/e$ and $W_0(y)=\ln y-\ln\ln y+o(1)$ gives
This Laplace-horizon derivation is informal, but the method it motivates is not merely asserted. BAHA (Branch-Aware Exact Basin Hopping) detects such fractures and jumps branches, and has been benchmarked: on a 26-domain suite it solves 22/26 (84%); fracture detection alone improves simulated annealing by ≈18%; branch scoring accounts for roughly half the total gain; and on smooth (fracture-free) landscapes it degrades to SA within 5% overhead, with ablations reported over 200 instances at 95% confidence [154,155]. The repository also documents its own failures (XOR-SAT, smooth landscapes, an admitted ChaCha20 cryptanalysis attempt), and its current table reports 22/26 rather than the 23/26 on the hosted article [162]. The claim is therefore empirically supported, not proved: branch completeness is a proposition conditional on mean-field spin-glass structure [155], and the Fisher-information step above remains informal. Experiments to date compare against simulated annealing, not against state-of-the-art CDCL/survey-propagation solvers.
7. Instantiations
M* = H / ~_W (Thm 2.1, = Myhill–Nerode / causal states)
│
┌───────────────────────┼───────────────────────┐
▼ ▼ ▼
[DISCRETE] [CONTINUOUS] [MEMORY]
FUTCache / KV NitroSAT / SOS Evidence compression
ε-quotient of Fisher + barrier quotient by answer-
prompt states + prime gates invariance
7.1 KV cache: $\varepsilon$-quotienting of prompt states
History $=$ prefix tokens; continuations $=$ future queries/completions; outcome $=$ completion distribution (Transformer attention is the substrate [91]). Exact caching uses the identity relation $\mathbf x_1=\mathbf x_2$; the quotient principle replaces it with
which is rate–distortion / information-bottleneck compression of the predictive state [80,81,82] and the approximate form of causal-state minimality [6,7]. Practical systems instantiate coarse versions of this quotient: paged/block KV memory [83], heavy-hitter eviction [84], attention-sink streaming [85], sliding-window attention [86], KV quantization [130], and persistence-based eviction [131]; the broader generation-efficiency stack is surveyed in [132,133]. The quotient viewpoint predicts the right comparison: evict by downstream equivalence class, not by recency or norm. What a transformer can compute at all is itself a formal-language question [142,143]; recent long-context systems make the state itself a learned compression [150].
A concrete realization: FUTCache. FUTCache implements exactly this quotient for novelty decisions rather than token caches. The state is the union $U_\varepsilon(H)=\bigcup_{y\in H}\bar B(y,\varepsilon)$; two histories with the same union are future-equivalent for every later novelty query, so the raw stream can be forgotten [159]. The stored representative set is $\varepsilon$-separated, so its size is bounded by the packing number $P(K,\varepsilon)$ rather than by stream length. Exactness of the interval-union and box-union engines is checked against brute-force oracles (134 C tests), and the submodular selection path is checked against exhaustive optima for $n\le16$ — verification, not assertion [159]. Empirical receipts are self-measured: on 1,000,000 real Alibaba Cloud traces, the net suppressed 72.34% of query work at $\varepsilon=0.55$ and grew sublinearly (65.95 MB at $N=10^6$) [160]; a separate CDCL study reports metric clause geometry predicting exact backjump depth at 20.0% vs a 14.6% matched null ($p=0.007$), rising to 41.3% when combined with LBD [160].
The instantiation also carries a negative result that sharpens the theory: choosing $\varepsilon$ by geometric MDL is not semantic safety. On a labeled semantic-cache benchmark the MDL-optimal radius ($\varepsilon=0.70$) gave F1 0.558 with 11 cross-intent merges, while the supervised optimum was $\varepsilon=0.55$ (F1 0.743) and the zero-false-positive point was $\varepsilon=0.45$ [161]. Geometric compressibility and semantic substitutability are distinct objectives: the quotient must be taken with respect to the task continuation set $\mathcal W$, not the cheapest description. This is the design principle in its sharpest, falsifiable form.
7.2 Answer-preserving context compression
History $=$ retrieved documents $E$; continuations $=$ queries $Q$; quotient $E_1\sim_{\mathcal W}E_2\iff\forall q\in Q,\ \operatorname{Ans}(q,E_1)=\operatorname{Ans}(q,E_2)$; optimal $E^*=\arg\min_{E'\subseteq E}|E'|$ with $Q(E')=Q(E)$. This is the exact quotient projection of documentary history modulo answer-invariance, and it specializes both the information bottleneck [80,81] and causal-state minimality [6,7]. Current prompt compressors — LLMLingua/LLMLingua-2 [87,88], gist tokens [89], retrieval pipelines [90,135], and the survey [134] — optimize surrogate salience or task loss; the quotient criterion makes the invariance target explicit.
7.3 Continuous non-greedy satisfaction (NitroSAT)
Map Boolean variables to the uncertainty simplex/disc (§3.2). Variables with low distinguishability pressure stay at $z_i=0$ ($x_i=\tfrac12$), where the cusp metric quenches $\nabla_gF=\mathcal O(|z|^2)$; the flow refuses to split until global constraint pressure lifts the variable toward certainty. This belongs to the continuous/learned-relaxation family of SAT solvers: Hopfield energy formulations [45], Fourier/algebraic continuous solvers [139], the Goemans–Williamson SDP approximation [49], the Lasserre hierarchy [50] and sum-of-squares relaxations [51] (applied to MAX-SAT in [138]), and neural message-passing solvers [136,137]. The distinctive claim is not convexification but when commitment is licensed: the geometry of §3.2 plus the certificate of §4. The clustering literature [41,42,43,44] supplies the correctness target — a solver should bypass the 1RSB clustered phase the way survey propagation does [140,141]. An implementation (≈2,500 lines of LuaJIT) reports 99–100% clause satisfaction on hard structured instances, linear scaling to 200k variables at 1,200–1,600 clauses/s, and completion on an 80M-clause scheduling instance and a 4M-variable grid-coloring instance [156]. These are single-machine, self-run benchmarks — not independent replication — but the promoted runs are externally verified: the returned assignment is checked clause-by-clause against the original instance, so they are externally verified self-evaluation [156,157]. No experiment isolates the cusp metric, the quotient policy, or the prime gates as the cause of these results: the geometry is motivation for the implementation, not a tested mechanism (gap G7, §7.5).
7.4 The computability horizon
Let $L$ run on an undecidable configuration graph. Each finite $D_j(L)$ is computable, but the coherent profile $x^*\in X_\infty=\varprojlim X_j$ is a limit object.
Theorem 7.1. No general algorithm decides whether a finite prefix $D_j(L)$ has permanently stabilized.
Proof. Encode a Turing machine $T$ so a marked cell $C_{\text{halt}}$ is ever visited iff $T$ halts; a uniform stabilization test would decide the halting problem, which Turing proved undecidable [76]. $\blacksquare$ [73,74,75]
The quotient $\mathcal M^*$ exists as a compact mathematical ceiling but is not constructible by a finite machine; computation proceeds inside finite approximations $M_0\leftarrow M_1\leftarrow\cdots\leftarrow\mathcal M^*$. This is the standard phenomenon of non-computable limits of computable sequences (Specker sequences; Pour-El–Richards; Weihrauch) [73,77,78], of identification in the limit [74,75] — with constructive query-learning as the positive counterpart [5] — of the incompressibility barrier of Kolmogorov complexity [79], and of learnability undecidability [147]. It sits between the super-Turing power of analog/neural models [144,145,148] and the computability limits of realistic quantized networks [146]; see [149] for the statistical backdrop. Every sound algorithm must emit finite witnesses at finite resolution.
7.5 Empirical status, under an explicit evidence standard
Two orthogonal axes govern an empirical claim. Provenance determines independence; verification determines validity. They must not be conflated:
| Level | Criterion | Strength |
|---|---|---|
| Self-reported | solver’s own success flag | weak |
| Externally verified | solver emits a witness; a separate checker validates it against the original instance | valid evidence of correctness |
| Independently replicated | separate implementation or researcher reproduces the result | strongest |
A satisfying assignment for a SAT instance, checked clause-by-clause by a verifier that reads the original CNF, is a proof that the instance is satisfiable and that the solver found a witness — it does not require a competing solver to certify the same assignment. The same standard applies to ablations and metrics: an independent checker can validate outputs even when the harness and the solver share a project. What external verification cannot establish by itself is comparative SOTA performance, freedom from benchmark-selection bias, or generalization beyond the tested distribution.
Correctness claims (verification axis). These are valid evidence that the instances are satisfiable and that the solver found a witness. They say nothing about competitors.
| System | Claim | Separate verifier | Status |
|---|---|---|---|
| NitroSAT (§7.3) | promoted runs return satisfying assignments | clause-by-clause check against the original CNF [157] | valid |
| SUTRA / nitro | 10/10 colouring & list-colouring suite | assignments independently checked against original CNFs [158] | valid |
| SUTRA / nitro | hospital scheduling, 504 vars / 39,842 clauses, SAT ≈0.15 s | client-side independent verifier [158] | valid |
| SUTRA / nitro | planted 3-CNF, $n=400$, $\alpha=4.0$, 5/5 closures | independent witness recount [158] | valid |
| BAHA (§6.2) | 22/26 solved solutions | witness/solution checks on the reported ones [154,155,162] | valid for the solved instances |
| FUTCache (§7.1) | exact novelty set $U_\varepsilon(H)$ | brute-force oracle equivalence (134 C tests); exhaustive optimum for $n\le16$ [159] | valid |
Comparative and aggregate claims (provenance axis; verification cannot validate these). These must be labelled self-measured, not externally verified.
| Claim | Status |
|---|---|
| BAHA ≈+18% over simulated annealing; branch scoring ≈half the gain; within 5% on smooth landscapes | self-measured effect sizes in a self-run harness; not verified, not replicated [155] |
| SUTRA vs CP-SAT 9/10 within 10 s | self-run comparison on a small, unregistered suite; the checked assignments prove SUTRA’s 10, not the fairness of the CP-SAT run [158] |
| NitroSAT throughput (1,200–1,600 clauses/s; 200k vars; 80M-clause; 4M-var completion) | self-run timing; completion is valid only where those assignments were clause-checked, which must be stated per instance [156] |
| 99–100% clause-satisfaction band | partial satisfaction is not a correctness claim; only fully checked assignments certify SAT [156] |
| 26-domain and 10-instance generalization | suites are self-selected; not evidence beyond those instances [154,155,158] |
| FUTCache 72.34% suppression on 1M Alibaba traces; 65.95 MB at $N=10^6$ | self-measured on a public dataset; not replicated [160] |
| FUTCache CDCL backjump prediction 20.0% vs 14.6% null ($p=0.007$); 41.3% with LBD | self-measured with a null model; not replicated [160] |
| FUTCache MDL radius is not semantic safety (F1 0.558 vs supervised 0.743) | self-measured negative result, preserved as a regression test [161] |
What verification cannot establish (gaps). G1 independent replication: absent, all sources are one project. G2 comparative baselines: no CDCL (CaDiCaL/Kissat), no Survey Propagation, no modern MaxSAT (RC2), no H2O/StreamingLLM/LLMLingua. G3 benchmark-selection bias: uncontrolled; suites and “promoted runs” are not pre-registered. G4 generalization: no held-out distribution. G5 UNSAT side: no DRAT/LRAT certificates; all validity evidence is SAT-witness-only. G6 verification coverage: the fraction of runs checked, checker identity, and whether checker code is separate from solver code are unstated. G7 mechanism ablation: no experiment isolates the cusp metric (§3.2) or prime gates (§5.2) as causal. G8 one instantiation (§7.2) has no experiments; FUTCache is implemented and oracle-verified. G9 theory–empirics mismatch: the empirical work does not test the Laplace-horizon derivation, prime weighting, or the Riemann lock. G10 sample sizes: headline aggregates rest on 10, 5, 1, and 26 instances, one machine, one implementation.
7.6 Code and artifacts
All implementations are public and inspectable; the verification recipes live in the repositories.
| Artifact | What it is | Verification present | Ref |
|---|---|---|---|
| FUTCache | C11 metric visited-set; exact interval-union and $L_\infty$ box-union engines; CRDT; Python bindings | brute-force oracle equivalence (134 C tests); exhaustive optimum for $n\le16$; MDL negative result preserved as a regression test | [159,160,161] |
| BAHA | C++/CUDA branch-aware basin hopping; 26-domain table; 109-file validation suite | solution/witness checks; failures documented (XOR-SAT, smooth landscapes, ChaCha20) | [154,155,162] |
| NitroSAT | physics-informed MaxSAT approximator (Python/C/Lua), V3 streaming | independent assignment verification (e.g. 923/923 clauses); Lean 4 proof files for the conditional lock | [156,163,164] |
| Casimir-SAT | physics-inspired SAT prototype (quantum-vacuum / Casimir forces) | benchmark scripts + SAT 2024 dataset; Zenodo DOI | [165] |
| Navokoj / SUTRA evidence bundle | CNF corpus, joined result CSVs, verifier records, manifest hashes | independent assignment checks; witness recount; client-verified artifact | [158] |
Nothing here substitutes for independent replication (G1). But the artifacts make the correctness claims checkable rather than asserted: a reader can recompute every reported counter from the returned witness and re-run the oracle tests.
7.7 Resolution-depth regularisation: the observer bridge
Everything in this paper is indexed by the continuation set $\mathcal W$, and the monotone-coarsening property (Prop. 2.1) is stated in terms of shrinking it. When $\mathcal W$ is infinite and the process never halts, the natural index is not elapsed time but resolution depth: the level $j$ of a refining partition tower, at which $\mathcal W$ has been coarsened to its resolution-$j$ quotient $X_j$.
Substituting resolution depth for time in a survival-weighted observer gives a scalar that couples the quotient to the geometry of its completion. Let $c_j = |X_j|$ be the number of resolution-$j$ quotient classes, and let $q \in (0,1]$ be the stopping probability per resolution level (so $1-q$ is the continuation probability). Define
This is the generating function of the quotient-class counts, so its singularities are fixed by their growth. By Cauchy–Hadamard its radius of convergence is $R = 1/\limsup_j c_j^{1/j}$, and since $O_q = C(1-q)$ the observer converges iff $1-q < R$. Hence in general
and by Pringsheim’s theorem the singularity nearest the origin lies on the positive real axis at $z=R$, so the STOP transition is exactly that singularity written in observer coordinates.
Exponential growth. If $c_j \asymp b^{\,j}$, then under the visual metric $d = 2^{-r}$ on the boundary of the discovery tree, $\dim_B(\partial T_{\mathrm{nov}}) = \log_2 b$, so $R = 2^{-\dim_B}$ and
Equivalently $\dim_B(\partial T_{\mathrm{nov}}) = -\log_2(1-q_c)$: the quotient dimension fixes the stopping rate above which the observer sees a finite value.
Polynomial growth. If $c_j \sim (j+1)^m$, then $\limsup_j c_j^{1/j}=1$, so $R=1$ and there is no interior STOP threshold: $q_c = 0$. The sum is then the object of the STOP residue theorem,
verified symbolically for $m = 0,\dots,6$. The zeta residue is therefore the sub-exponential case of resolution-depth regularisation; exponential growth produces a dimension pole instead.
Status. This is a bridge, not a new minimality theorem, and it is deliberately labelled as elementary. The ingredients — Cauchy–Hadamard, box-counting dimension on a tree boundary, Pringsheim’s theorem, and the residue identity above — are all standard. What is asserted is that resolution depth, not time, is a legitimate stopping axis for the quotient’s completion; that the critical stopping probability is $q_c = 1-R$ with $R$ the radius of convergence of the level generating function; and the geometric corollary $q_c = 1-2^{-\dim_B}$ under regular covering growth. It is not an equivalence of categories: no functor is constructed here, and none is claimed. Whether $q_c$ is independent of the chosen refinement tower is open. Nothing in this subsection bears on the transfer criterion (§5.4) or on hypotheses (A)–(C).
8. Synthesis
| Layer | Category / topology | Discrete (cache, CDCL) | Continuous (relaxation, SOS) | Thermodynamic |
|---|---|---|---|---|
| Distinction | partitions $\mathcal P_j$ [28,29] | variables, cache keys | $z_i\in\mathbb D$, loss surface | microstates |
| Equivalence | $h_1\sim_{\mathcal W}h_2$ [1,2,6,7] | task-invariant prompt class | $\nabla v=0$ subspace | equal macroscopic observables |
| Quotient | terminal/coequalizer $\mathcal M^*$ [19] | minimal cache; UNSAT cores | relaxed classes with equal projections | coarse-grained macrostate |
| Geometry | $d=2^{-k}$, Gromov boundary [24,25,31] | refinement/search trees | Fisher + cusp metric | replica ultrametric [92,93] |
| Compatibility | presheaf, $\check H^1$ [37,38,39] | implication/conflict graphs | prime gates | non-interfering modes |
| Dynamics | bonding maps $q_j$ [28,29] | propagation, backjump, eviction | $\dot x=-g^{-1}\nabla F$ [32,34] | Langevin/annealing [45,46] |
| Selection | coherent profiles $\varprojlim X_j$ | satisfying model | Lyapunov minimum | ground state |
| Witness | finite prefix, section | verification certificate | low-energy readout | local measurement |
9. Conclusion
The unifying observation is a quotient identity:
State is the quotient of what happened by what can happen next. Every component is anchored: quotienting by future indistinguishability is Myhill–Nerode / causal-state / bisimulation / Galois-abstraction theory [1,2,6,7,15,16,17,18]; the generated geometry is the Gromov visual metric and the Fisher–Rao metric [24,25,31,32]; compatibility is sheaf cohomology [37,38,39]; the relaxation is self-concordant log-barrier plus natural gradient, Lyapunov-stable via LaSalle [32,34,47,48,59]; multiplicative gating is product-of-experts / multiplicative weights [52,54,55]; and the horizon is non-computable limits and undecidability [73,74,75,76,77]. Prime weighting and the Riemann lock remain conjectural, the BAHA fracture jump is empirically supported with an informal derivation (§6.2, §7.5), and FUTCache and evidence compression are proposals without experiments. The programme is therefore not a new calculus but a common language for four existing calculi — and the open problems are exactly those flagged in §4, §5.2, §5.3, and Appendix D.
Appendix A. Provenance map (claim → prior art)
| Paper claim | Established grounding |
|---|---|
| Thm 2.1 universal factorization | coequalizer universal property [19,20]; minimal realization [21,22]; categorical DL [101,102,103] |
| Minimal future-sufficient state | Myhill–Nerode [1,2,3]; causal states [6,7]; PSRs [95,96,97]; bisimulation quotient [15,16]; MDP homomorphisms [98,99] |
| Redundancy $=\ker\phi$ | best abstraction of Galois connection [17,18] |
| Monotone coarsening | monotone refinement of partitions / abstract domains [17,18,28] |
| Ultrametric from refinement | profinite/Gromov boundary [24,25,26]; dendrograms [27] |
| Discovery words | Mazurkiewicz traces / partial-order reduction [28,29,30] |
| Fisher metric & natural gradient | Chentsov, Amari, mirror descent [31,32,33,34,35] |
| Cusp/hyperbolic barrier | hyperbolic geometry, Poincaré embeddings [25,36,104,105] |
| Presheaf & $\check H^1$ obstruction | sheaf theory, contextuality, sheaf NNs [37,38,39,40,110,111,112,113,114] |
| Lyapunov dissipation | LaSalle invariance [47,59,60]; thermodynamic flows [119,120,121,122] |
| Log-barrier potential | self-concordant barriers [47,48] |
| Prime independence / anti-resonance | unique factorization, Kronecker–Weyl [71,72] |
| Multiplicative gating | product of experts [52]; multiplicative weights [54,55]; gradient conflict [53] |
| $1-\sigma>\gamma$, Riemann lock | explicit formula, Bombieri–Vinogradov, random-matrix zeta zeros [64,65,67,68,69,70,123,124,125,126,127] |
| Lambert-W jump | Lambert W [61]; fold catastrophe [62,63]; annealing [45,46] |
| KV cache / context compression | rate–distortion, IB, H2O, StreamingLLM, KVQuant, Scissorhands, LLMLingua [80,81,83,84,85,87,88,89,130,131,134] |
| Continuous SAT relaxation | mean-field/clustering, SDP, SOS, NeuroSAT/FourierSAT [41,42,43,44,49,50,51,136,138,139] |
| Computability horizon | Specker sequences, Gold, Rice, Pour-El–Richards, Siegelmann, Caro, Boche [73,74,75,77,78,144,145,146,147] |
| Glassy loss landscapes | DNN vs spin glass, stat-mech of learning, stiffness [115,116,117] |
| Constraint learning | constrained-optimization learning surveys [128] |
| Learned/continuous SAT | NeuroSAT, FourierSAT, neural SAT evaluation [136,137,138,139,140,141] |
| Long-context & efficiency | long-context survey, KV quantization, speculation [130,131,132,133,150] |
Appendix B. Corrections to the original
- Metric inconsistency. §3.4–3.5 uses inverse metric $g^{z\bar z}=\tfrac14|z|^2(1-|z|^2)^2$; §5.2 uses $g^{ii}=x_i(1-x_i)$. They are different geometries. The Fisher/natural-gradient metric is the well-posed one for §5; the cusp metric is a separate design choice (§3.2).
- Prime mass. $\sum_{c\le K}W(p_c)=\Theta(K/\ln K)$, not $\sim K$ [72].
- “NP-hard $\equiv\check H^1\ne0$” is false as stated; the paper already contains the counterexamples (2-SAT, Horn, GF(2)); we make the non-equivalence explicit [40].
- BAHA “Theorem 6.1” is a heuristic derivation, not a theorem; the Fisher-information step is not rigorous [46,61,62]. The method is nevertheless empirically supported by the BAHA benchmark suite [154,155].
- BAHA pass rate. The hosted article reports 23/26 (88%); the repository’s current table reports 22/26 (84%), with VRP, Set Cover, LABS, and HP Protein Folding listed as failures. We use the repository figure [162].
Appendix C. Citation policy
Each reference was admitted only if deleting it would remove a distinct theorem, construction, historical lineage, competing formulation, empirical result, or boundary on a claim; otherwise it was pruned. Grouped citations are used only where the grouped works jointly support one claim, and every clustered reference is either broken out with its specific contribution or removed. The bibliography is therefore load-bearing rather than exhaustive.
Appendix D. Contribution, novelty, and status of the bridges
D.1 The central universal property is not novel. Theorem 2.1 is the universal property of the quotient by an equivalence relation — the coequalizer of the kernel pair in $\mathbf{Set}$ [19,20] — specialized to “same behavior on the continuation set $\mathcal{W}$.” It coincides definitionally with the Nerode right congruence [1,2], the causal-state partition [6,7], bisimulation minimization [15,16], exact MDP aggregation [9,10], and Kalman/Willems minimal realization [21,22]; coalgebraically it is finality up to behavioral equivalence [13,14]. The proof is two lines because it is the definition of a quotient. Two further components are standard, not new:
- $\mathcal{W}$-parameterized coarsening. The quotient depends on the test set $\mathcal{W}$, and $\mathcal{W}_1\subseteq\mathcal{W}_2$ makes $\sim_{\mathcal{W}_1}$ coarser. This is exactly the coarsening used by Angluin’s observation table in active automata learning [5], by predictive state representations, which fix a chosen set of future tests [95], and by testing equivalences [153].
- Monotone coarsening (Prop. 2.1). Shrinking the test set can only merge classes. The forget/decide loop is a variant of the abstract/refine loop of counterexample-guided abstraction refinement, where added constraints shrink admissible behavior and coarsen the abstraction [152].
The “terminal” label carries no content: the quotient is terminal here only because morphisms are defined to run from finer to coarser representations; under the opposite convention it is initial. Nothing depends on the name.
D.2 Status of each bridge.
| Claim | Status | Already given by | What would upgrade it |
|---|---|---|---|
| Universal factorization (Thm 2.1) | definitional consequence | coequalizer [19,20]; Nerode [1,2]; causal states [6,7]; bisimulation [15,16]; MDP aggregation [9,10]; minimal realization [21,22]; final coalgebra [13,14] | — (it is the definition of a quotient) |
| $\mathcal{W}$-parameterized quotient | standard | observation table [5]; PSRs [95]; testing equivalence [153] | complexity of the coarsest task-preserving $\mathcal{W}$ |
| Forget/decide loop (Prop. 2.1) | trivial + analogy | monotonicity under test restriction; CEGAR [152] | a coupled forget/decide theorem with a rate |
| Discrete ultrametric (Thm 3.1) | consequence of the construction | profinite/Gromov boundary [24,25,26]; behavioral pseudometrics [11] | representation theorem: every computational distinguishability is such a limit |
| Tree/Gromov identification | consequence | Gromov visual metric [24] | — |
| Fisher / natural-gradient flow | consequence | Amari [31,32]; mirror descent [34,35] | — |
| Transfer criterion (§5.4) | criterion + partial theorem: convexity clause provable on Horn/submodular, parity obstruction known; full characterization open | discrete convexity, Schaefer dichotomy, Lovász extension, median graphs [166–174] | the necessary-and-sufficient characterization |
| Chebyshev recovery rate (§5.5) | proved (quadratic basin): $O(\sqrt\kappa\log(D/\rho_0))$ identification; filtered method required | Chebyshev minimax [178]; accelerated methods [176]; Chebyshev semi-iteration / CG [175,177] | nonlinear-basin version; application to §5.1’s unfiltered flow |
| Conditional quotient realization (Thm 5.2) | proved conditional on (A); (B), (C) are structural assumptions | Conley Morse decomposition [179]; Chebyshev rate [175–178] | (A) for a concrete class; submodular realizes only the coarsest quotient [180] |
| Worked non-convex instances (§5.7) | proved: 1-D A1 holds; 2-D A1 fails above $\sigma^2/2$ via saddle-node | Morse classification [180]; saddle-node bifurcation [181] | a rich-quotient non-convex class with no surplus index-0 components |
| BAHA navigation / A1$'$ (§5.8) | operational: fracture $\equiv$ fold; Lambert-W branches $\equiv$ fold continuations; branch jumping $\equiv$ Morse navigation | BAHA [154,155,162]; Lambert W [61] | A1$'$ proved for a class; control of detector false positives |
| SOS-certified realization (Lem. 5.1) | proved, conditional on the certificate: A1 holds iff there are no unlabeled index-$0$ critical points; certificate degree is the complexity measure | Positivstellensatz [182,183,184]; SOS hierarchy [55,56] | a bounded-degree certificate for a rich quotient |
| Inverted Poincaré well; quadratic quenching (Thm 3.2–3.3) | new construction (proved); bridge is analogy | hyperbolic geometry [25,36] | transfer theorem: SAT correctness/approximation guarantee |
| Presheaf / Čech machinery (§4) | consequence | sheaf theory [37,40,41] | — |
| Cohomology ↔︎ hardness | analogy (paper disclaims complexity content) | CSP algebra [40]; sheaf contextuality [37] | lower bound on $\check H^1$ dimension vs. runtime for a family |
| Lyapunov dissipation (Thm 5.1) | consequence | LaSalle [59,60]; log-barrier [47,48] | — |
| Prime anti-resonance (§5.2) | conjecture | Kronecker–Weyl [71] gives independence only | proof or counterexample |
| $1-\sigma>\gamma$; Riemann lock (§5.3) | heuristic / conjecture | explicit formula [67]; Bombieri–Vinogradov [64] | prove the coupling, or refute it |
| Multiplicative direction preservation (Prop. 6.1) | trivial consequence | product of experts [52]; barrier methods [47] | — |
| BAHA / Lambert-W jump (§6.2) | empirically supported; derivation heuristic; branch completeness conditional | catastrophe theory [62]; annealing [45]; Lambert W [61]; BAHA benchmarks [154,155] | independent SOTA-baseline comparison; rigor for the Laplace-horizon step |
| KV / context quotient (§7.1–7.2) | reframing of known methods | rate–distortion / IB [8,81]; bisimulation metrics [11]; H2O [84]; StreamingLLM [85]; LLMLingua [87] | estimator + regret bound + experiments |
| Computability horizon (Thm 7.1) | consequence | Turing [76]; Specker [73]; Gold [75] | — |
D.3 What would make the programme a contribution.
- A transfer theorem. Prove that for a class of discrete systems the continuous relaxation’s quotient is isomorphic (or bi-Lipschitz) to the discrete quotient, with a computable constant. Without this, “generated geometry” is an analogy. The structural form of the hypotheses is stated in §5.4: an exact convexity preserved by the relaxation, separation of quotient classes by the observables, and uniform conditioning of the basins — with parity as the canonical obstruction.
- A coupled forget/decide theorem. Define a process interleaving quotienting over $\mathcal{W}_t$ with constraint propagation, and prove soundness and a rate at which $\mathcal{W}_t$ shrinks. Prop. 2.1 alone is trivial.
- Prime weights. Either prove a cancellation-avoidance bound, or report the likely negative result: real clause potentials are not rescued from harmonic cancellation by $\mathbb{Q}$-linear independence of $\log p$ alone, since the relevant obstruction is conditioning of the weighted clause operator.
- Cohomology. Exhibit a family with a lower bound on $\dim\check H^1$ and a matching runtime separation. Otherwise the machinery is decoration.
- Comparative, bias-controlled, replicated experiments. The correctness evidence is already of the right kind — witnesses checked against the original instances by separate verifiers [154,155,156,158] — so the open question is not validity but scope. What is missing is (i) apples-to-apples comparison against modern CDCL / Survey Propagation / MaxSAT solvers and against H2O / StreamingLLM / LLMLingua, (ii) control for benchmark-selection bias,
- generalization beyond the tested distributions, and (iv) independent replication by a third party. Provenance determines independence; verification determines validity; only (i)–(iv) concern provenance and scope.
- The only possibly-new mathematical object is the interaction-aware, $\mathcal{W}$-parameterized terminal quotient as an algorithm-design criterion (does a compressed state preserve the quotient?), not the universal property itself. That is a design principle, and it should be claimed as such.
Appendix E. Outlook: certified behavioral minima, interpretability, and alignment
The transfer machinery has an obvious target beyond constraint solvers: the loss landscape of a trained network. Parameters play the role of histories, an explicit behavioral test family $\mathcal W$ plays the role of the continuation set, and two parameter settings are behaviorally equivalent when they answer every probe in $\mathcal W$ identically. Writing $Q_{\mathcal W}$ for the induced behavioral quotient and $\mathcal M_{\mathcal W}^*=X/\!\sim_{\mathcal W}$, a mechanistic certificate is the following pair of facts.
- Attractor completeness. $\operatorname{Crit}_0(L)/G=\{C_1,\dots,C_k\}$ is finite and isolated modulo a symmetry group $G$ whose orbits preserve the realized function — certified by Lemma 5.1 in a symmetry-reduced or equivariant Morse–Bott formulation [190,191].
- Behavioral correspondence. $\pi:\{C_1,\dots,C_k\}\xrightarrow{\cong}\mathcal M_{\mathcal W}^*$, i.e. the attractors biject onto the $\mathcal W$-classes.
The intended object is the commuting diagram
What this proves, and only this.
If the attracting components of a model’s training dynamics can be certified to correspond exactly to a specified behavioral quotient, then learning acquires a mechanically checkable behavioral certificate: every reachable attractor realizes a known behavior class, and no additional attracting behavior exists within the certified domain.
Equivalently: there are no attracting behavioral modes outside the certified taxonomy — within the modeled parameter region and relative to $\mathcal W$. This is not “we proved it learned the right thing.” It says exactly what has been proved and exactly what remains dependent on the specification $\mathcal W$.
Why “relative to $\mathcal W$” is everything. The quotient is monotone in the test family, $$\mathcal W_1\subset\mathcal W_2\ \Longrightarrow\ Q_{\mathcal W_2}\ \text{refines}\ Q_{\mathcal W_1},$$ so a certificate is only as strong as its probes. If $\mathcal W$ does not test deception, backdoors, or distribution shift, two parameter settings can be $\mathcal W$-equivalent while differing catastrophically outside $\mathcal W$. Alignment is therefore partly a test-completeness problem: the landscape certificate proves there are no extra attractors relative to the partition you specified; it cannot prove the specification captures right behavior. That is the specification gap [193,194], and it is untouched by any amount of SOS degree.
Symmetry. Individual parameter-space minima are the wrong objects: hidden-unit permutation and rescaling generate large equivalence families with identical realized functions [190,191]. The census must be taken over $\operatorname{Crit}_0(L)/G$, or over connected attracting components / function-space equivalence classes, rather than by counting parameter-space critical points.
BAHA as a re-verification trigger. If training crosses a bifurcation at which a new index-$0$ component appears, then $|\operatorname{Crit}_0(L)/G|:k\to k+1$. The certificate remains valid iff the new attractor maps to an already certified $\mathcal W$-class; if it does not, the certificate has just failed. A bifurcation (fracture) detector is thus a trigger for re-verification, not a licence to assume training stayed inside the certified regime. This is the alignment reading of §5.8.
What remains, precisely. Three gaps survive the corrections. (i) Polynomial form: Lemma 5.1 needs a polynomial $F$; the certificate applies to polynomial-activation networks, smooth activations after polynomial approximation, or a certified surrogate. (ii) The behavioral map: the certificate needs a positive bound relating parameter distance to behavioral difference on $\mathcal W$ [192]; without it, certified attractors are not certified semantics. (iii) The specification gap, above.
With these named, the machinery still delivers a real, checkable property: certified behavioral homogeneity of basins. If $B(x_i)$ is certified to lie in a parameter ball of radius $r$, the network is parameter-Lipschitz with constant $\ell$ there, and the probes are $\ell_{\mathcal W}$-Lipschitz, then every parameter in $B(x_i)$ agrees with $x_i$ on every probe to within $\ell\,\ell_{\mathcal W}\,r$. That is the network analogue of a quotient class, and a genuine safety property — behavioral invariance under retraining noise, fine-tuning within a basin, or bounded parameter perturbation.
If $\mathcal W$ is chosen to be a circuit-level probe set [185], the quotient classes are the circuits, and a certified finite attractor census becomes a certified circuit census; probing superposition structure [186] gives the feature-basis variant. Landscape structure makes this plausible rather than hopeless: the surface is highly non-convex with many near-flat directions [187,188], but minima are connected by low-loss paths [189], which is what a finitary Morse–Bott census requires.
References
- Myhill, J. (1957). Finite automata and the representation of events. WADC Technical Report 57-624.
- Nerode, A. (1958). Linear automaton transformations. Proc. AMS 9(4), 541–544.
- Hopcroft, J. E. (1971). An $n\log n$ algorithm for minimizing states in a finite automaton. In Theory of Machines and Computations, 189–196.
- Paige, R., & Tarjan, R. E. (1987). Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989.
- Angluin, D. (1987). Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106.
- Crutchfield, J. P. (1994). The calculi of emergence: computation, dynamics and induction. Physica D 75, 11–54.
- Shalizi, C. R., & Crutchfield, J. P. (2001). Computational mechanics: pattern and prediction, structure and randomness. J. Stat. Phys. 104, 817–879.
- Bialek, W., Nemenman, I., & Tishby, N. (2001). Predictability, complexity, and learning. Neural Comput. 13(11), 2409–2463.
- Givan, R., Dean, T., & Greig, M. (2003). Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence 147(1–2), 163–223.
- Li, L., Walsh, T. J., & Littman, M. L. (2006). Towards a unified theory of state abstraction for MDPs. ISAIM.
- Ferns, N., Panangaden, P., & Precup, D. (2004). Metrics for finite Markov decision processes. UAI, 162–169.
- Abel, D., Hershkowitz, D., & Littman, M. L. (2016). Near-optimal approximate state abstraction. UAI.
- Rutten, J. J. M. M. (2000). Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249(1), 3–80.
- Jacobs, B. (2016). Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge University Press.
- Milner, R. (1989). Communication and Concurrency. Prentice Hall.
- Park, D. (1981). Concurrency and automata on infinite sequences. LNCS 104, 167–183.
- Cousot, P., & Cousot, R. (1977). Abstract interpretation: a unified lattice model for static analysis. POPL, 238–252.
- Cousot, P., & Cousot, R. (1979). Systematic design of program analysis frameworks. POPL, 269–282.
- Mac Lane, S. (1998). Categories for the Working Mathematician (2nd ed.). Springer.
- Adámek, J., Herrlich, H., & Strecker, G. E. (1990). Abstract and Concrete Categories. Wiley.
- Kalman, R. E. (1963). Mathematical description of linear dynamical systems. SIAM J. Control 1(2), 152–192.
- Willems, J. C. (1991). Paradigms and puzzles in the theory of dynamical systems. IEEE Trans. Autom. Control 36(3), 259–294.
- Krohn, K., & Rhodes, J. (1965). Algebraic theory of machines I. Trans. AMS 116, 450–464.
- Gromov, M. (1987). Hyperbolic groups. In Essays in Group Theory, Springer, 75–263.
- Bridson, M. R., & Haefliger, A. (1999). Metric Spaces of Non-Positive Curvature. Springer.
- Ribes, L., & Zalesskii, P. (2010). Profinite Groups (2nd ed.). Springer.
- Carlsson, G., & Mémoli, F. (2010). Characterization, stability and convergence of hierarchical clustering methods. JMLR 11, 1425–1470.
- Mazurkiewicz, A. (1987). Trace theory. LNCS 266, 279–324.
- Godefroid, P. (1996). Partial-Order Methods for the Verification of Concurrent Systems. Springer.
- Winskel, G. (1987). Event structures. LNCS 266, 325–392.
- Chentsov, N. N. (1982). Statistical Decision Rules and Optimal Inference. AMS.
- Amari, S. (1998). Natural gradient works efficiently in learning. Neural Comput. 10(2), 251–276.
- Amari, S., & Nagaoka, H. (2000). Methods of Information Geometry. AMS.
- Raskutti, G., & Mukherjee, S. (2015). The information geometry of mirror descent. IEEE Trans. Inf. Theory 61(7), 3991–4008.
- Beck, A., & Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods. Oper. Res. Lett. 31(3), 167–175.
- Nickel, M., & Kiela, D. (2017). Poincaré embeddings for learning hierarchical representations. NeurIPS.
- Abramsky, S., & Brandenburger, A. (2011). The sheaf-theoretic structure of non-locality and contextuality. New J. Phys. 13, 113036.
- Ghrist, R. (2014). Elementary Applied Topology. CreateSpace.
- Hansen, J., & Ghrist, R. (2019). Toward a spectral theory of cellular sheaves. J. Appl. Comput. Topol. 3, 315–358.
- Schaefer, T. J. (1978). The complexity of satisfiability problems. STOC, 216–226. (see also Aspvall, Plass & Tarjan, Inf. Process. Lett. 8(3), 121–123, 1979.)
- Mézard, M., Parisi, G., & Zecchina, R. (2002). Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812–815.
- Mézard, M., & Montanari, A. (2009). Information, Physics, and Computation. Oxford University Press.
- Monasson, R., & Zecchina, R. (1996). Entropy of the $K$-satisfiability problem. Phys. Rev. Lett. 76(21), 3881–3885.
- Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., & Zdeborová, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems. PNAS 104(25), 10318–10323.
- Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science 220(4598), 671–680.
- Neal, R. M. (2001). Annealed importance sampling. Stat. Comput. 11, 125–139.
- Nesterov, Y., & Nemirovskii, A. (1994). Interior-Point Polynomial Algorithms in Convex Programming. SIAM.
- Nesterov, Y. (2004). Introductory Lectures on Convex Optimization. Springer.
- Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM 42(6), 1115–1145.
- Lasserre, J. B. (2001). Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817.
- Parrilo, P. A. (2003). Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293–320.
- Hinton, G. E. (2002). Training products of experts by minimizing contrastive divergence. Neural Comput. 14(8), 1771–1800.
- Yu, T., Kumar, S., Gupta, A., Levine, S., Hausman, K., & Finn, C. (2020). Gradient surgery for multi-task learning. NeurIPS.
- Kivinen, J., & Warmuth, M. K. (1997). Exponentiated gradient versus gradient descent for linear predictors. Inf. Comput. 132(1), 1–63.
- Arora, S., Hazan, E., & Kale, S. (2012). The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8, 121–164.
- Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Math. J. 23(2), 298–305.
- Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis, Princeton, 195–199.
- Levin, D. A., & Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed.). AMS.
- LaSalle, J. P. (1960). Some extensions of Liapunov’s second method. IRE Trans. Circuit Theory 7(4), 520–527.
- Khalil, H. K. (2002). Nonlinear Systems (3rd ed.). Prentice Hall.
- Corless, R. M., Gonnet, G. H., Hare, D. E. G., Jeffrey, D. J., & Knuth, D. E. (1996). On the Lambert $W$ function. Adv. Comput. Math. 5, 329–359.
- Thom, R. (1972). Stabilité Structurelle et Morphogenèse. Benjamin.
- Zeeman, E. C. (1977). Catastrophe Theory: Selected Papers 1972–1977. Addison-Wesley.
- Bombieri, E. (1965). On the large sieve. Mathematika 12(2), 201–225.
- Vinogradov, A. I. (1965). On the density hypothesis for Dirichlet $L$-series. Izv. Akad. Nauk SSSR 29, 903–934.
- Montgomery, H. L., & Vaughan, R. C. (1974). Hilbert’s inequality. J. London Math. Soc. 2(1), 73–82.
- Titchmarsh, E. C. (1986). The Theory of the Riemann Zeta-Function (2nd ed.). Oxford University Press.
- Ingham, A. E. (1937). On the difference between consecutive primes. Quart. J. Math. 8, 255–266.
- Connes, A. (1999). Trace formula in noncommutative geometry and the zeros of the Riemann zeta function. Selecta Math. 5(1), 29–106.
- Berry, M. V., & Keating, J. P. (1999). The Riemann zeros and eigenvalue asymptotics. SIAM Rev. 41(2), 236–266.
- Weyl, H. (1916). Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann. 77, 313–352.
- Hardy, G. H., & Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.
- Specker, E. (1949). Nicht konstruktiv beweisbare Sätze der Analysis. J. Symbolic Logic 14(3), 145–158.
- Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Trans. AMS 74(2), 358–366.
- Gold, E. M. (1967). Language identification in the limit. Inf. Control 10(5), 447–474.
- Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 2(42), 230–265.
- Pour-El, M. B., & Richards, J. I. (1989). Computability in Analysis and Physics. Springer.
- Weihrauch, K. (2000). Computable Analysis: An Introduction. Springer.
- Li, M., & Vitányi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.). Springer.
- Tishby, N., Pereira, F. C., & Bialek, W. (1999). The information bottleneck method. Allerton.
- Shannon, C. E. (1959). Coding theorems for a discrete source with a fidelity criterion. IRE Nat. Conv. Rec. 7(4), 142–163.
- Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley.
- Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J. E., Zhang, H., & Stoica, I. (2023). Efficient memory management for large language model serving with PagedAttention. SOSP.
- Zhang, Z., Sheng, Y., Zhou, T., Chen, T., Zheng, L., Cai, R., Song, Z., Tian, Y., Ré, C., Barrett, C., Wang, Z., & Chen, B. (2023). H$_2$O: Heavy-hitter oracle for efficient generative inference of large language models. NeurIPS.
- Xiao, G., Tian, Y., Chen, B., Han, S., & Lewis, M. (2023). Efficient streaming language models with attention sinks. ICLR 2024.
- Beltagy, I., Peters, M. E., & Cohan, A. (2020). Longformer: The long-document transformer. arXiv:2004.05150.
- Jiang, H. Z., Wu, Q., Lin, C.-Y., Yang, Y., & Qiu, L. (2023). LLMLingua: Compressing prompts for accelerated inference of large language models. EMNLP.
- Pan, Z., Wu, Q., Jiang, H., Xia, M., Luo, X., Zhang, J., Lin, Q., Rühle, V., Yang, Y., Lin, C.-Y., Zhao, H. V., Qiu, L., & Zhang, D. (2024). LLMLingua-2: Data distillation for efficient and faithful task-agnostic prompt compression. ACL Findings.
- Mu, J., Li, X. L., & Goodman, N. (2023). Learning to compress prompts with gist tokens. NeurIPS.
- Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W., Rocktäschel, T., Riedel, S., & Kiela, D. (2020). Retrieval-augmented generation for knowledge-intensive NLP tasks. NeurIPS.
- Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., & Polosukhin, I. (2017). Attention is all you need. NeurIPS.
- Parisi, G. (1980). The order parameter for spin glasses: a function on the interval $0$–$1$. J. Phys. A 13, 1101–1112.
- Mézard, M., Parisi, G., Sourlas, N., Toulouse, G., & Virasoro, M. (1987). Spin Glass Theory and Beyond. World Scientific.
- Connes, A., & Bost, J.-B. (1995). Hecke algebras, type III factors and phase transitions with spontaneous symmetry breaking in number theory. Selecta Math. 1(3), 411–457.
- Littman, M. L., Sutton, R. S., & Singh, S. (2002). Predictive representations of state. NeurIPS.
- Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence 101(1–2), 99–134.
- Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
- Ravindran, B., & Barto, A. G. (2003). SMDP homomorphisms: an algebraic approach to abstraction in semi-Markov decision processes. IJCAI.
- Biza, O., Platt, R., van de Meent, J.-W., & Wong, L. (2020). Online abstraction with MDP homomorphisms for deep reinforcement learning. AAMAS.
- Dorsch, U., Milius, S., & Schröder, L. (2017). Efficient coalgebraic partition refinement. CONCUR; arXiv:1705.02882.
- Gavranović, B., Lessard, P., Dudzik, A., von Glehn, T., Araújo, J. G. M., & Veličković, P. (2024). Position: Categorical deep learning is an algebraic theory of all architectures. ICML; arXiv:2402.15332.
- Fong, B., & Spivak, D. I. (2019). An Invitation to Applied Category Theory. Cambridge University Press.
- Spivak, D. I. (2014). Category Theory for the Sciences. MIT Press.
- Peng, W., Varanka, T., Mostafa, A., Shi, H., & Zhao, G. (2022). Hyperbolic deep neural networks: a survey. IEEE TPAMI 44(12), 10023–10044.
- Sala, F., De Sa, C., Gu, A., & Ré, C. (2018). Representation tradeoffs for hyperbolic embeddings. ICML.
- Zhang, L., Naitzat, G., & Lim, L.-H. (2018). Tropical geometry of deep neural networks. ICML; arXiv:1805.07091.
- Peyré, G., & Cuturi, M. (2019). Computational optimal transport. Found. Trends Mach. Learn. 11(5–6), 355–607.
- Cohen-Addad, V., Das, A., Karthik, C. S., & Mathieu, C. (2020). On efficient low distortion ultrametric embedding. ICML.
- Bauer, M., Mémoli, F., Needham, T., & Nishino, M. (2025). The Z-Gromov-Wasserstein distance. JMLR 26; arXiv:2408.08233.
- Bodnar, C., Di Giovanni, F., Chamberlain, B. P., Liò, P., & Bronstein, M. M. (2022). Neural sheaf diffusion: a topological perspective on heterophily and oversmoothing in GNNs. NeurIPS; arXiv:2202.04579.
- Hansen, J., & Gebhart, T. (2020). Sheaf neural networks. arXiv:2012.06333.
- Barbero, F., Bodnar, C., Sáez de Ocáriz Borde, H., Bronstein, M., Veličković, P., & Liò, P. (2022). Sheaf neural networks with connection Laplacians. PMLR (Topological, Algebraic and Geometric Learning Workshops).
- Ayzenberg, A., Gebhart, T., Magai, G., & Solomadin, G. (2025). Sheaf theory: from deep geometry to deep learning. arXiv:2502.15476.
- Bach, E. (1999). Sheaf cohomology is #P-hard. J. Symbolic Computation 27(4), 429–433.
- Baity-Jesi, M., Sagun, L., Geiger, M., Spigler, S., Ben Arous, G., Cammarota, C., LeCun, Y., Wyart, M., & Biroli, G. (2019). Comparing dynamics: deep neural networks versus glassy systems. J. Stat. Mech. 124013; arXiv:1803.06969.
- Bahri, Y., Kadmon, J., Pennington, J., Schoenholz, S. S., Sohl-Dickstein, J., & Ganguli, S. (2020). Statistical mechanics of deep learning. Annu. Rev. Condens. Matter Phys. 11, 501–528.
- Fort, S., Nowak, A., Jastrzębski, S., & Narayanan, S. (2021). Stiffness: a new perspective on generalization in neural networks. arXiv:1901.09491.
- Fatkhullin, I., Sokolov, I., Gorbunov, E., & Richtárik, P. (2024). Taming nonconvex stochastic mirror descent with general Bregman divergence. ICML.
- Landauer, R. (1961). Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5(3), 183–191.
- Bennett, C. H. (1973). Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532.
- Friston, K. (2010). The free-energy principle: a unified brain theory? Nat. Rev. Neurosci. 11, 127–138.
- Still, S., Sivak, D. A., Bell, A. J., & Crooks, G. E. (2012). Thermodynamics of prediction. Phys. Rev. Lett. 109, 120604.
- Bogomolny, E. B., & Keating, J. P. (1995). Random matrix theory and the Riemann zeros I: three- and four-point correlations. Nonlinearity 8(6), 1115–1131.
- Keating, J. P., & Snaith, N. C. (2000). Random matrix theory and $\zeta(1/2+it)$. Comm. Math. Phys. 214, 57–89.
- Granville, A., & Soundararajan, K. (2007). Large deviations of the Riemann zeta function. Acta Math. 198, 1–47.
- Maynard, J. (2015). Small gaps between primes. Ann. of Math. 181(1), 383–413.
- Matomäki, K., & Radziwiłł, M. (2016). Multiplicative functions in short intervals. Ann. of Math. 183(3), 1015–1056.
- Kotary, J., Fioretto, F., Van Hentenryck, P., & Wilder, B. (2021). End-to-end constrained optimization learning: a survey. IJCAI.
- Du, Y., Li, S., Tenenbaum, J., & Mordatch, I. (2020). Compositional visual generation with energy based models. NeurIPS.
- Hooper, C., Kim, S., Mohammadzadeh, H., Mahoney, M. W., Shao, Y. S., Keutzer, K., & Gholami, A. (2024). KVQuant: towards 10 million context length LLM inference with KV cache quantization. NeurIPS; arXiv:2401.18079.
- Liu, Z., Desai, A., Liao, F., Wang, W., Xie, V., Xu, Z., Kyrillidis, A., & Shrivastava, A. (2023). Scissorhands: exploiting the persistence of importance hypothesis for LLM KV cache compression at test time. NeurIPS; arXiv:2305.17118.
- Xia, H., Yang, Z., Dong, Q., et al. (2024). Unlocking efficiency in large language model inference: a comprehensive survey of speculative decoding. ACL Findings.
- Huang, Y., Xu, J., Lai, J., Jiang, Z., Chen, T., Li, Z., Yao, Y., Ma, X., Yang, L., Chen, H., Li, S., & Zhao, P. (2023). Advancing transformer architecture in long-context large language models: a comprehensive survey. arXiv:2311.12351.
- Li, Z., Liu, Y., Su, Y., & Collier, N. (2024). Prompt compression for large language models: a survey. NAACL 2025; arXiv:2410.12388.
- Gao, Y., Xiong, Y., Gao, X., Jia, K., Pan, J., Bi, Y., Dai, Y., Sun, J., Wang, M., & Wang, H. (2024). Retrieval-augmented generation for large language models: a survey. arXiv:2312.10997.
- Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., & Dill, D. L. (2019). Learning a SAT solver from single-bit supervision. ICLR; arXiv:1802.03685.
- Mojžíšek, D., Hůla, J., Li, Z., Zhou, Z., & Janota, M. (2025). Neural approaches to SAT solving: design choices and interpretability. arXiv:2504.01173.
- Sinjorgo, L., & Sotirov, R. (2023). On solving MAX-SAT using sum of squares. INFORMS J. Comput.; arXiv:2302.06931.
- Kyrillidis, A., Shrivastava, A., Vardi, M. Y., & Zhang, Z. (2019). FourierSAT: a Fourier expansion-based algebraic framework for solving hybrid Boolean constraints. AAAI; arXiv:1912.01032.
- Braunstein, A., Mézard, M., & Zecchina, R. (2005). Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27(2), 201–226.
- Marino, R., Parisi, G., & Ricci-Tersenghi, F. (2016). The backtracking survey propagation algorithm for solving random K-SAT problems. Nat. Commun. 7, 12996.
- Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. TACL 8, 156–171; arXiv:1906.06755.
- Weiss, G., Goldberg, Y., & Yahav, E. (2021). Thinking like transformers. ICML; arXiv:2106.06981.
- Siegelmann, H. T., & Sontag, E. D. (1995). On the computational power of neural nets. J. Comput. Syst. Sci. 50(1), 132–150.
- Siegelmann, H. T. (1995). Computation beyond the Turing limit. Science 268(5210), 545–548.
- Boche, H., Fojtik, V., Fono, A., & Kutyniok, G. (2024). Computability of classification and deep learning: from theoretical limits to practical feasibility through quantization. arXiv:2408.06212.
- Caro, M. C. (2023). From undecidability of non-triviality and finiteness to undecidability of learnability. Int. J. Approx. Reasoning; arXiv:2106.01382.
- Blum, L., Shub, M., & Smale, S. (1989). On a theory of computation and complexity over the real numbers. Bull. Amer. Math. Soc. 21(1), 1–46.
- Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press.
- Tandon, A., Dalal, K., Li, X., Koceja, D., Rød, M., Buchanan, S., Wang, X., Leskovec, J., Koyejo, S., Hashimoto, T., Guestrin, C., McCaleb, J., Choi, Y., & Sun, Y. (2025). End-to-end test-time training for long context. arXiv:2512.23675.
- Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). Geometric deep learning: grids, groups, graphs, geodesics, and gauges. arXiv:2104.13478.
- Clarke, E., Grumberg, O., Jha, S., Lu, Y., & Veith, H. (2003). Counterexample-guided abstraction refinement for symbolic model checking. JACM 50(5), 752–794.
- De Nicola, R., & Hennessy, M. C. B. (1984). Testing equivalences for processes. Theoret. Comput. Sci. 34(1–2), 83–133.
- Iyer, S. (2026a). Branch Aware Exact Basin Hopping (BAHA): thermodynamic fracture detection with branch jumping. https://sethuiyer.github.io/baha/
- Iyer, S. (2026b). Multiplicative calculus for hardness detection and branch-aware optimization: a computational framework for detecting phase transitions via non-integrable log-derivatives. Zenodo. https://doi.org/10.5281/zenodo.18373732
- Iyer, S. (2026c). NitroSAT: solving MaxSAT through number theory, statistical mechanics, and persistent homology. https://sethuiyer.codeberg.page/NitroSAT/
- Iyer, S. (2026d). NitroSAT V3 witness-recount and clause-level assignment verification protocol. Navokoj evidence workspace. (Independent witness recount; divergent counters are rejected, not propagated.)
- Iyer, S. (2026e). ShunyaBar evidence bundle: Navokoj / NitroSAT / SUTRA reproducibility artifacts, CNF corpus, and independent assignment checks. Hugging Face: sethuiyer/shunyabar-evidence-v1. https://huggingface.co/buckets/sethuiyer/shunyabar-evidence-v1
- Iyer, S. (2026f). FUTCache: a metric visited-set and sufficient-state compressor for future-novelty decisions. GitHub: sethuiyer/FUTCache. https://github.com/sethuiyer/FUTCache
- Iyer, S. (2026g). Empirical scaling benchmark on 1,000,000 real Alibaba Cloud traces, and geometric recurrence in CDCL proof search. FUTCache documentation.
- Iyer, S. (2026h). Negative result: geometric MDL is not semantic safety. FUTCache documentation.
- Iyer, S. (2026i). BAHA: branch-aware basin hopping (C++/CUDA, 26-domain validation suite). GitHub: sethuiyer/baha. https://github.com/sethuiyer/baha
- Iyer, S. (2026j). NitroSAT: physics-informed MaxSAT approximator. GitHub: sethuiyer/NitroSAT. https://github.com/sethuiyer/NitroSAT
- Iyer, S. (2026k). NitroSAT formal proofs in Lean 4 / Mathlib:
ConditionalAsymptoticLock and NitroSATProofs. GitHub:
sethuiyer/NitroSAT. (No
sorry,axiom, oradmit; hard analytic/spectral inputs are named hypotheses.) - Iyer, S. (2026l). Casimir-SAT: solving SAT with quantum vacuum dynamics. GitHub: sethuiyer/casimir-sat-solver; Zenodo DOI 10.5281/zenodo.17394164.
- Schaefer, T. J. (1978). The complexity of satisfiability problems. STOC, 216–226.
- Jeavons, P., Cohen, D., & Gyssens, M. (1997). Closure properties of constraints. JACM 44(4), 527–548.
- Feder, T., & Vardi, M. Y. (1998). The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28(1), 57–104.
- Lovász, L. (1983). Submodular functions and convexity. In Mathematical Programming: The State of the Art, Springer, 235–257.
- Murota, K. (2003). Discrete Convex Analysis. SIAM.
- Chepoi, V. (2000). Graphs of some CAT(0) complexes. Adv. Appl. Math. 24(2), 125–179.
- Grigoriev, D. (2001). Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoret. Comput. Sci. 259(1–2), 613–622.
- Grigoriev, D., & Végh, E. (2012). Complexity of semialgebraic proofs. Mosc. Math. J. 12(4), 647–679.
- Dechter, R. (2003). Constraint Processing. Morgan Kaufmann.
- Golub, G. H., & Varga, R. S. (1961). Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. Numer. Math. 3, 147–168.
- Nesterov, Y. (1983). A method of solving a convex programming problem with convergence rate $O(1/k^2)$. Soviet Math. Dokl. 27, 372–376.
- Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM.
- Rivlin, T. J. (1990). Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory (2nd ed.). Wiley.
- Conley, C. (1978). Isolated Invariant Sets and the Morse Index. CBMS Regional Conference Series in Mathematics 38. AMS.
- Milnor, J. (1963). Morse Theory. Princeton University Press.
- Guckenheimer, J., & Holmes, P. (1983). Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields. Springer.
- Putinar, M. (1993). Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969–984.
- Stengle, G. (1974). A nullstellensatz and a positivstellensatz in semialgebraic geometry. Math. Ann. 207(2), 87–97.
- Schmüdgen, K. (1991). The K-moment problem for compact semi-algebraic sets. Math. Ann. 289(2), 203–206.
- Olah, C., Cammarata, N., Schubert, L., Goh, G., Petrov, M., & Carter, S. (2020). Zoom in: an introduction to circuits. Distill.
- Elhage, N., Hume, T., Olsson, C., et al. (2022). Toy models of superposition. Transformer Circuits Thread.
- Choromanska, A., Henaff, M., Mathieu, M., Ben Arous, G., & LeCun, Y. (2015). The loss surfaces of multilayer networks. AISTATS.
- Li, H., Xu, Z., Taylor, G., Studer, C., & Goldstein, T. (2018). Visualizing the loss landscape of neural nets. NeurIPS.
- Garipov, T., Izmailov, P., Podoprikhin, D., Vetrov, D., & Wilson, A. G. (2018). Loss surfaces, mode connectivity, and fast ensembling of DNNs. NeurIPS.
- Brea, J., Simsek, B., Illing, B., & Gerstner, W. (2019). Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape. arXiv:1907.02911.
- Entezari, R., Al-Shedivat, M., Sau, A., & Ribeiro, A. (2022). The role of permutation invariance in linear mode connectivity of neural networks. ICLR.
- Wong, E., & Kolter, J. Z. (2018). Provable defenses against adversarial examples via the convex outer adversarial polytope. ICML.
- Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., & Mané, D. (2016). Concrete problems in AI safety. arXiv:1606.06565.
- Krakovna, V., Uesato, J., Mikulik, V., Rahtz, M., Everitt, T., Kumar, R., Kenton, Z., Leike, J., & Legg, S. (2020). Specification gaming: the flip side of AI ingenuity. DeepMind.