Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion
Dongsung Huh · 2026
Read Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion by Dongsung Huh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29885.txt.
Introduction
Dongsung Huh poses Cayley-table completion as the standard test for a missing deep-learning bias. Current theory stresses capacity control through norms, margins, and low-rank bias, yet deep nets fail to extrapolate exact discrete algebraic rules. Matrix completion with weight decay leans geometric, toward low rank, while tensor factorizations with a flatness prior lean algorithmic, toward exact associativity. The open problem asks for exact recovery bounds for Cayley-table completion. The challenge extends further: generalize flatness priors to discover broader axioms alone, with no combinatorial search.
Catalog record
| CREATOR | Dongsung Huh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 12391 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29885
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion Dongsung Huh Abstract Modern statistical learning theory and deep learning characterize generalization primarily in terms of continuous capacity control (e.g., norm-based regularization, margin maximization, low-rank bias). While highly successful in continuous domains, deep learning consistently fails to extrapolate exact algorithmic or discrete algebraic rules, reflecting a missing inductive bias toward algorithmic complexity minimization. We propose the Cayley-table completion as the canonical testbed for this missing bias, serving as the discrete algebraic counterpart to matrix completion. Just as matrix factorization combined with weight decay yields an implicit geometric bias toward low linear rank, recent results demonstrate that operator-valued tensor factorizations paired with a flatness prior yield an implicit algorithmic bias toward exact discrete associativity. We pose the open problem of establishing formal exact recovery bounds for Cayley-table completion, and challenge the community to generalize continuous flatness priors to autonomously discover broader discrete algorithmic axioms without combinatorial search. \coltauthor keywords Algorithmic Compression, Cayley-Table Completion, Flat Minima, Implicit Regularization, Matrix Completion, Sample Complexity 1 Introduction: The Failure of Geometric Priors in Algebraic Domains The historical development of Statistical Learning Theory (SLT) reveals a deep theoretical divide between discrete logic and continuous geometry. In its classical formulation, learning was fundamentally framed as Algorithmic Compression . Classical frameworks such as PAC Learning for boolean concepts ( 25 ) , Occam’s Razor bounds ( 4 ) , and Minimum Description Length (MDL) ( 19 ) evaluated generalization based on the recovery of exact, minimal logical rules (e.g., boolean circuits, finite automata). Because optimizing discrete algorithmic complexity is generally NP-hard, modern SLT largely abandoned it in favor of continuous capacity control mechanisms—an approach we term Geometric Compression . Geometric compression assumes that parsimonious underlying concepts lie on smooth manifolds or low-dimensional linear subspaces. This shift was theoretically justified by landmark results in fields like compressed sensing and matrix completion, which rigorously proved that continuous geometric penalties (like \ell_{1} or nuclear norms) serve as perfect convex relaxations for discrete NP-hard properties (like \ell_{0} sparsity or discrete matrix rank) ( 10 ; 6 ) . Consequently, modern SLT assumes that implicit geometric biases toward smoothness, margin maximization, and low linear rank are sufficient for robust generalization ( 23 ; 12 ) . This geometric paradigm fundamentally underpins generalization in modern deep learning. Deep neural networks excel at discovering low-rank embeddings and smooth interpolations within low-dimensional latent spaces ( 3 ; 2 ; 1 ; 15 ; 17 ) , which proves remarkably effective for representing natural, continuous data. However, this geometric surrogate relationship categorically fails in discrete algebraic domains. This theoretical misalignment manifests empirically across modern architectures. Standard neural networks categorically struggle to achieve true length generalization on algorithmic tasks ( 20 ) , and require massive, brittle memorization rather than rule abstraction to simulate deterministic finite automata ( 9 ) . In this open problem, we propose Cayley-table completion as the canonical testbed for learning discrete algebraic structures. In this setting, geometric compression is fundamentally at odds with algorithmic compression, exposing a crucial missing inductive bias in the current paradigm. Motivating Example: Deep Learning’s Inability to Discover Exact Symmetries. A striking manifestation of this missing inductive bias occurs in the context of Geometric Deep Learning (GDL) ( 5 ) . When standard neural networks are trained on symmetry-augmented datasets, they learn only approximate symmetries, consistently failing to natively discover the exact weight-sharing patterns of the underlying symmetry groups. This exposes a fundamental limitation: deep learning lacks the inductive bias to algorithmically compress these continuous approximations into rigid, shared weight structures. Instead, to guarantee out-of-distribution (OOD) generalization, GDL imposes the exact weight-sharing patterns of an a priori known symmetry group via hard-coded equivariant architectures ( 7 ) . 2 Canonical Tasks While the domain of algorithmic compression is vast—spanning formal languages to general automata—establishing a rigorous foundation requires a minimal atomic testbed. Just as Matrix Completion serves as the foundational testbed for the discovery of continuous low-dimensional manifolds, Cayley-Table Completion—the recovery of a discrete binary operation from partial observations ( 14 ; 18 ) —provides the canonical formalization for discovering discrete algebraic rules. This frames a fundamental dichotomy in structural recovery: • Matrix Completion: The underlying structure has low linear rank . The continuous solution is achieved via Matrix Factorization paired with an \ell_{2} penalty. Factoring a matrix M=AB and applying weight decay ( \ell_{2} regularization) yields a variational characterization of the nuclear norm of M : \min_{A,B\text{ s.t. }AB=M}\|A\|^{2}_{F}+\|B\|^{2}_{F}=2\sum_{i}\sigma_{i}(M), which serves as a differentiable (but inexact ) surrogate for linear rank ( 11 ; 22 ; 8 ) . • Cayley-Table Completion: Cayley tables of groups (and quasigroups) are Latin squares, whose rows are permutations of one another, thus inherently precluding linear redundancy. Instead, the true parsimony of algebraic groups stems from the associativity axiom, which tightly constrains the global structure to yield remarkably low algebraic complexity, effectively minimizing its structural description length. The fundamental challenge, therefore, is finding a continuous, differentiable measure that can penalize associativity violations without resorting to intractable combinatorial search. 3 Existence Proof: Differentiable Measures of Algebraic Complexity To formalize this mathematically, let Q be a finite set of n elements equipped with a binary operation \circ:Q\times Q\to Q . The operation’s Cayley table is captured by the structure tensor \delta\in\{0,1\}^{n\times n\times n} , where \delta_{abc}\coloneqq\mathbb{I}_{\{a\circ b=c\}} for a,b,c\in Q . Recently, 14 demonstrated that Cayley-table completion can be exactly solved via an operator-valued tensor factorization T_abc(Θ) ≔ 1 n Tr (A_a B_b C_c), Θ= (A,B,C) where A_{a},B_{b},C_{c} are the n\times n matrix slices (linear operators) indexed by a,b,c\in Q . This factorization is optimized under a flatness prior that penalizes the Hessian trace of the empirical reconstruction loss: H (Θ) ≔ Tr ( ∇^2 ∑_(a,b,c)∈Ω (T_abc(Θ) - δ _abc)^2 ), 13 provided a rigorous landscape analysis of this objective, proving that in the fully-observed limit, the geometric infimum \mathcal{H}_{\inf}(\delta)\coloneqq\inf_{T(\Theta)=\delta}\mathcal{H}(\Theta) implicitly defines an exact, differentiable measure of algebraic complexity. Crucially, the objective \mathcal{H}(\Theta) decomposes into two components: a geometric alignment term (collinearity) and an inverse \ell_{2} penalty. These variational terms strictly induce core discrete properties. Collinearity enforces associativity, while the inverse \ell_{2} term acts as an exact inverse rank penalty within the collinear manifold. This mechanism actively drives the parameters toward full-rank unitarity, diametrically opposing the ubiquitous low-rank bias of standard geometric compression. Consequently, this geometry establishes an absolute lower bound \mathcal{H}_{\inf}(\delta)\geq 3|\delta| (where |\delta|\coloneqq\sum_{abc}\delta_{abc}=n^{2} denotes the table size). This bound is attained if and only if the target operation is isotopic to a group, uniquely characterizing the global minimizer as the regular representation of the underlying group (up to unitary gauge). This establishes a formal proof-of-concept that continuous gradient-based optimization can natively discover discrete algebraic axioms, bypassing combinatorial search entirely. 4 Open Problems in Algorithmic SLT These partial results suggest that exact algorithmic complexity can be natively optimized via continuous geometric penalties. Empirically, correcting this missing inductive bias yields drastic structural benefits: 14 demonstrated that this flatness-regularized tensor factorization does not merely approximate the target operations, but rapidly collapses into exact recovery, achieving state-of-the-art sample efficiency that scales tightly with the true algorithmic complexity of the underlying group. However, the foundational question remains: what is the exact theoretical boundary between generalization via geometric