View a PDF of the paper titled Functional Compression as Occam’s Razor: Algebraic Complexity from Sensitivity Minimization, by Dongsung Huh and 2 other authors
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.
Submission history
From: Dongsung Huh [view email]
[v1]
Fri, 28 Nov 2025 12:58:13 UTC (194 KB)
[v2]
Fri, 6 Feb 2026 18:51:28 UTC (214 KB)
[v3]
Fri, 15 May 2026 14:35:54 UTC (1,782 KB)
[v4]
Tue, 19 May 2026 01:43:57 UTC (1,782 KB)
[v5]
Mon, 16 Nov 2026 20:48:26 UTC (1,148 KB)
