Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers¶

会议: ICLR 2026
arXiv: 2509.22445
代码: 无
领域: 模型压缩 / 学习理论
关键词: 最小描述长度, 柯尔莫哥洛夫复杂度, Transformer, 计算通用性, 变分目标

一句话总结¶

从柯尔莫哥洛夫复杂度理论出发，提出了"渐近最优描述长度目标"的理论框架，证明了 Transformer 存在这样的目标函数（基于其计算通用性的新证明），并通过构造基于自适应高斯混合先验的可微变分目标进行了实证验证，揭示了重要的优化挑战。

研究背景与动机¶

最小描述长度（MDL）原则是机器学习中奥卡姆剃刀的形式化框架：最佳模型是能最短描述数据的模型。MDL 在统计模型选择、正则化和泛化理论中有着深厚的理论基础。然而，将 MDL 原则应用到 Transformer 等深度神经网络面临根本性困难——缺乏一个有原则的、通用的模型复杂度度量。

传统的 MDL 方法（如 BIC、两部分编码）依赖于参数数量等简单的复杂度度量，但这对于过参数化的深度网络显然不适用——一个拥有数十亿参数的 Transformer 可能只需要很少的"有效参数"来解决特定任务。现有的深度学习压缩方法（如剪枝、量化）虽然在实践中有效，但缺乏与信息论最优性的理论联系。

本文的核心 idea 是：利用柯尔莫哥洛夫复杂度（数据的最短程序描述长度——一个不可计算但理论上最优的复杂度度量）来定义一类"渐近最优"的描述长度目标。具体来说，如果一个目标函数的最小化器能够实现对任意数据集的最优压缩（仅差一个加法常数），那么它就是渐近最优的。关键问题是：这样的目标函数对 Transformer 是否存在？如果存在，是否可以计算？

方法详解¶

整体框架¶

论文的技术路径分三步：（1）定义渐近最优描述长度目标的数学概念；（2）证明 Transformer 具有计算通用性，从而证明渐近最优目标的存在性；（3）构造一个具体的、可微的变分目标并进行实证分析。

关键设计¶

渐近最优描述长度目标的定义: 给定一族参数化模型 \(\{f_\theta : \theta \in \Theta\}\) 和描述长度函数 \(L(\theta, x)\)（表示用参数 \(\theta\) 描述数据 \(x\) 的比特数），如果目标 \(L\) 的最小化器 \(\theta^* = \arg\min_\theta L(\theta, x)\) 满足：对所有数据 \(x\)，当模型资源上界增长时，\(L(\theta^*, x)\) 趋近于柯尔莫哥洛夫复杂度 \(K(x)\)（相差不超过一个与 \(x\) 无关的加法常数），则称 \(L\) 是渐近最优的。换言之，最小化这样的目标等价于找到数据的（近似）最短描述。
Transformer 的计算通用性（新证明）: 为了证明 Transformer 具有渐近最优目标，首先需要证明 Transformer 具备计算通用性——即 Transformer 可以模拟任意图灵机（在有限步数内）。论文给出了一个新的构造性证明，展示了如何用有限深度和宽度的 Transformer 来模拟通用图灵机的计算过程。这一结果本身就是一个重要的理论贡献，因为它提供了比此前工作更精确的资源界限。在此基础上，论文证明了：由于 Transformer 可以模拟任意压缩算法，存在一个描述长度目标使得其最小化器实现渐近最优压缩。
自适应高斯混合先验变分目标: 为了将理论结果转化为实践，论文构造了一个可计算、可微分的变分目标。具体方法是在 Transformer 的权重空间上定义一个自适应高斯混合分布作为先验：
- 先验 \(p(\theta)\) 是多个高斯分量的混合，混合权重和方差参数也作为变量优化
- 描述长度包含两部分：编码模型参数的比特数（由先验决定）+ 用模型描述数据的比特数（由似然决定）
- 通过变分推断的方式使目标可微分，可以用标准梯度下降优化

论文证明了在适当条件下，这个变分目标是渐近最优的（前提是先验足够灵活且优化器能找到全局最优）。

损失函数 / 训练策略¶

变分描述长度目标的形式为两部分编码：

\[L(\theta, x) = \underbrace{-\log p(\theta)}_{\text{模型复杂度}} + \underbrace{-\log p(x | \theta)}_{\text{数据拟合}}\]

其中先验 \(p(\theta)\) 基于自适应高斯混合，\(p(x|\theta)\) 是 Transformer 在参数 \(\theta\) 下的预测分布。训练目标是最小化这个总描述长度，本质上是在数据拟合能力和模型简洁性之间寻找最佳平衡。

实验关键数据¶

主实验¶

论文在算法任务上进行了实证分析（验证描述长度目标能否选择简单且泛化好的方案）：

指标	变分 MDL 目标	标准交叉熵	说明
解的复杂度	低	高	MDL 目标偏好简单解
泛化性能	强	弱	低复杂度解泛化更好
优化难度	高（随机初始化失败）	低	关键发现

消融实验¶

配置	关键指标	说明
高斯混合 vs 单高斯先验	混合更灵活	自适应混合能更好地捕捉权重分布
不同先验权重	影响压缩-拟合平衡	需要仔细调节
从良好初始化开始	MDL 目标可找到好解	初始化质量至关重要
从随机初始化开始	标准优化器失败	暴露了核心优化挑战

关键发现¶

存在性证明是积极的: Transformer 确实存在渐近最优描述长度目标，这为 MDL 原则在深度学习中的应用提供了理论基础
变分目标确实能选择低复杂度解: 在算法任务上，MDL 目标比标准训练更偏好简单、泛化好的解
关键的负面结果: 标准优化器（如 Adam）从随机初始化出发无法可靠地找到这些低复杂度解。这意味着即使理论上存在最优目标，实践中的优化障碍仍是核心瓶颈
这一发现将研究重点从"设计更好的目标函数"转向了"设计更好的优化算法"

亮点与洞察¶

将柯尔莫哥洛夫复杂度与深度学习架起理论桥梁: 这是一个非常有野心的理论工作，试图为深度学习的泛化能力提供信息论层面的深层解释
Transformer 计算通用性的新证明: 给出了更精确的资源界限，是独立有价值的理论贡献
诚实地报告负面结果: 论文没有回避"标准优化器无法找到理论最优解"这一事实，反而将其作为核心发现，指出了未来研究的方向。这种学术诚实值得称赞
MDL 原则的现代化复兴: 在深度学习时代重新审视 MDL 这一经典原则，用现代工具（变分推断 + Transformer 通用性）给出了新的理论理解
理论意义大于实践意义: 当前的价值更多在于提供理论框架和指引研究方向，而非直接可用的算法

局限与展望¶

优化 Gap 是核心限制: 理论证明了最优解的存在，但找到这些解的计算问题未解决。这不仅是本文的局限，也是整个 MDL-深度学习交叉领域的核心开放问题
实验规模有限: 仅在简单的算法任务上验证，离真实的 NLP/CV 任务还有很大距离。理论的渐近保证在有限模型规模下能否体现出优势是未知的
变分 bound 的紧度: 变分目标只是真实 MDL 的上界，bound 的松紧程度直接影响实际效果
与运行中的实际压缩方法的关系: 论文没有将理论框架与量化、知识蒸馏等实际压缩方法联系起来，缺乏与实践的桥接
可能的方向: 结合神经网络剪枝/稀疏化与描述长度优化；开发专门针对 MDL 目标的优化算法（如模拟退火、进化策略）；将框架扩展到序列建模和自回归 LLM

评分¶

新颖性: ⭐⭐⭐⭐⭐
实验充分度: ⭐⭐⭐
写作质量: ⭐⭐⭐⭐⭐
价值: ⭐⭐⭐⭐