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
用奇异学习理论把 MDL 推广到神经网络,发现复杂度指标 LLC 与模型可压缩性线性相关,量化实验拟合 R²=0.98。
经典的最小描述长度(MDL)原则把模型当成一段两段式编码:先编码模型本身,再编码数据。模型越简单,总码长越短。可这套理论的严格版本只适用于「正则」模型,要求参数到预测分布的映射一一对应、Fisher 信息矩阵可逆。神经网络不是这样:很多组不同的权重给出同一个预测分布,参数到分布是多对一的,数学上叫「奇异模型」。
正则模型的冗余码长按 (d/2) log n 增长,d 是参数量。那奇异模型呢?Watanabe 的奇异学习理论(SLT)早就给了答案:冗余按 λ log n − (m−1) log log n 增长,其中 λ 是实对数典范阈值,经验估计时常被叫做局部学习系数 LLC,且 λ ≤ d/2。问题是,这个抽象的几何量到底对不对应什么工程上能测的东西?这篇就把 LLC 和最实在的工程属性(模型能压缩多少)对上了。
作者先从 SLT 出发证明了「奇异 MDL」的两段式编码定理,确认 LLC 就是决定冗余的那一项。然后给出可检验的推论:在固定损失容差 ϵ 下,要把模型量化到不掉点,每个参数平均需要的比特数 b 大致随 LLC 线性增长,b(ϵ) ≈ (λ/d) · log₂(1/ϵ)。直觉是,LLC 越大,损失地景里「合格盆地」越小,网格就得画得更细、用更多比特才能把整个格子框在盆地内。LLC 越小(越「退化」),同样的精度就够了,模型更可压。
实验在 Pythia 全家桶上跑,从 14M 到 6.9B 参数,覆盖 2k 到 90k 训练步的多个检查点,用了两类压缩:对称量化(搜索不掉点的最小量化级数 nq)和权重矩阵奇异值分解(截断奇异值)。容差取 ϵ=0.5。
量化这边,临界量化级数 nq 和 LLC 在大量训练步上呈线性关系,所有模型整体拟合 R²=0.98。分解这边也单调上升,只有 Pythia-6.9B 在后期训练步趋于走平。结果对不同 ϵ 取值定性上不敏感。作者还试了不做损失最小化的量化(线性拟合变差)、加高斯噪声(相对噪声与 LLC 负相关,符合预期)。
| 压缩方式 | 指标 | 结果 |
| 量化 | nq vs LLC 线性拟合 R² | 0.98 |
| 分解 | 临界压缩比 vs LLC | 单调上升,6.9B 后期走平 |
| 加噪 | 相对噪声 vs LLC | 负相关 |
LLC 这几年被 Timaeus 等团队拿来刻画训练动态、grokking、甚至对齐相关的现象,但一直是个有点玄的几何量。这篇把它锚定到压缩,一个谁都能复现、用一行量化代码就能测的属性。对从业者有两个直接用处:一是给模型压缩极限一个有理论根据的预测,不用纯靠试;二是 LLC 估计本身依赖 MCMC 采样、又贵又噪,压缩实验可以当它的独立交叉验证。
只测了 Pythia 一族(同架构、同训练数据的解码器 transformer),换架构、换数据是否成立没验证。分解那条线的线性不如量化干净,6.9B 走平说明并非所有压缩手段都服帖。ϵ=0.5 是个人为超参,作者称定性不敏感,但绝对数值会随它变。最关键的是,这是相关性而非因果证明,理论预测了这条关系、实验也吻合,但 LLC 估计自身的噪声没有被充分量化。