Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The paper identifies a gap in deep learning's ability to extrapolate exact algorithmic rules, contrasting its success in continuous domains. It proposes Cayley-table completion as a benchmark to address this, analogous to matrix completion but for discrete algebraic structures. The authors call for research into formal recovery bounds for Cayley-table completion and methods to autonomously discover discrete algorithmic axioms, moving beyond combinatorial search.
Deep learning's struggle with algorithmic extrapolation isn't just a quirk—it highlights a missing inductive bias that Cayley-table completion can help us find.
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.