Functional Compression as Occam's Razor: Algebraic Complexity from Sensitivity Minimization
Organizations: Independent Researcher · IBM Research · University at Albany, SUNY
Abstract
Discovering discrete algebraic structures from data is a fundamental challenge in machine learning. We ask how continuous learning objectives can favor functional compression---representing data through shared algebraic composition rather than low-rank representations. We analyze the global optima of a canonical factorization model for algebraic completion (recovering finite binary operations) that demonstrated a preference for group operations. We measure algebraic complexity by the infimum of parameter sensitivity under exact reconstruction. We establish a universal complexity floor, whose attainment forces geometric alignment and unitarity of the latent representations. At the floor, input representations compose into the corresponding output representations; their reuse across the operation table propagates these local identities to enforce a globally shared algebraic structure. If the floor is not attained, a positive gap separates it from the feasible infimum. For cancellative operations, floor attainment forces the model's latent representation to be an injective homomorphism, equivalent to the target being isotopic to a group. In this case, every global minimizer is equivalent to the underlying group's unitary left-regular representation, up to isotopy and unitary gauge, resolving the central conjecture of Huh (2025). For non-cancellative operations, floor attainment forces exact structural redundancies (identical rows or columns) and is equivalent to a unitary factorization of the target's row- and column-reduced table with orthonormal output matrices, yielding the fewest distinct input matrices compatible with exact reconstruction. The resulting cancellative table then embeds in a group-isotope table. This analysis reveals a structural bias toward functional compression: at the sensitivity floor, algebraic composition of latent representations implements the target operation.
Figures & tables
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 0 | 3 | 2 | 5 | 4 |
| 2 | 2 | 3 | 4 | 5 | 0 | 1 |
| 3 | 3 | 2 | 5 | 4 | 1 | 0 |
| 4 | 4 | 5 | 0 | 1 | 2 | 3 |
| 5 | 5 | 4 | 1 | 0 | 3 | 2 |
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 0 | 3 | 4 | 5 | 2 |
| 2 | 2 | 4 | 5 | 0 | 1 | 3 |
| 3 | 3 | 5 | 4 | 2 | 0 | 1 |
| 4 | 4 | 2 | 1 | 5 | 3 | 0 |
| 5 | 5 | 3 | 0 | 1 | 2 | 4 |
Compositional Representation Learning
Compositional representation learning studies how models encode reusable parts and relations to understand combinations they have not seen.
See all 98 papers