Compressibility Measures Complexity: Minimum Description Length Meets Singular Learning Theory
Einar Urdshals, Edmund Lau, Jesse Hoogland, Stan van Wingerden, Daniel Murfet
stat.ML, cs.LG
2025-10-14
From singular learning theory: the local learning coefficient predicts how far a network compresses, with quantization critical bits fitting LLC at R²=0.98 across Pythia.
The minimum description length (MDL) principle treats a model as a two-part code: encode the model, then encode the data given it. The shorter the total, the better the model. But the rigorous version of MDL only covers "regular" models, where the parameter-to-distribution map is one-to-one and the Fisher information matrix is invertible. Neural networks are not regular. Many different weight settings produce the same predictive distribution, so the map is many-to-one, mathematically a "singular" model.
For regular models the code redundancy grows as (d/2) log n, with d the parameter count. Singular models follow a different law that Watanabe's singular learning theory (SLT) established long ago: redundancy grows as λ log n − (m−1) log log n, where λ (the real log canonical threshold, estimated empirically as the local learning coefficient, LLC) satisfies λ ≤ d/2. What has been missing is whether this abstract geometric quantity lines up with anything an engineer can measure. This paper ties LLC to the most concrete property of all: how much the model can be compressed.
The authors first prove a "singular MDL" two-part-code theorem from SLT, confirming that LLC is the term that governs redundancy. The testable corollary: at a fixed loss tolerance ϵ, the average bits per parameter needed to quantize without degrading quality, b, should scale roughly linearly with LLC, b(ϵ) ≈ (λ/d) · log₂(1/ϵ). The intuition is that a larger LLC means a smaller admissible basin in the loss landscape, so the grid must be finer (more bits) to keep the whole cell inside the basin. A smaller LLC, meaning more degeneracy, tolerates coarser precision and compresses further.
Experiments run across the Pythia suite, from 14M to 6.9B parameters, across multiple checkpoints from 2k to 90k training steps, with two compression techniques: symmetric quantization (searching the smallest quantization level nq that keeps loss within tolerance) and singular-value decomposition of weight matrices (truncating singular values). Tolerance is ϵ = 0.5.
For quantization, the critical quantization level nq is linear in LLC across a wide range of training steps, with an overall fit of R² = 0.98 across all models. Factorization shows a monotone increase too, except that Pythia-6.9B flattens at later steps. The picture is qualitatively insensitive to the choice of ϵ. The authors also try quantization without loss minimization (the linear fit weakens) and additive Gaussian noise (relative noise correlates negatively with LLC, as expected).
| Compression | Metric | Result |
| Quantization | nq vs LLC linear fit R² | 0.98 |
| Factorization | critical ratio vs LLC | monotone, 6.9B flattens late |
| Noise | relative noise vs LLC | negative correlation |
LLC has been used by groups like Timaeus to characterize training dynamics, grokking, and alignment-adjacent phenomena, but it has remained a somewhat ethereal geometric quantity. This paper anchors it to compression, something anyone can reproduce with a line of quantization code. For practitioners there are two direct uses: it gives a theory-backed prediction of how far a model compresses before quality drops, without pure trial and error; and since LLC estimation itself relies on noisy, expensive MCMC sampling of the loss landscape, a compression experiment serves as an independent cross-check on the estimate.
Only the Pythia family is tested (one architecture, one training dataset, decoder-only transformers); whether the relationship holds for other architectures or data is unverified. The factorization line is less cleanly linear than quantization, and the 6.9B flattening shows not every compression technique obeys the law. The tolerance ϵ = 0.5 is a chosen hyperparameter; the authors claim qualitative insensitivity, but absolute numbers shift with it. Most importantly, this is correlation backed by a theoretical prediction, not a causal proof, and the noise in LLC estimation itself is not quantified.