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 是否存在？如果存在，是否可以计算？

方法详解¶

整体框架¶

论文走的是一条"先定义、再证存在、最后构造"的理论路线：先把"渐近最优描述长度目标"这个概念严格写成数学定义，再借助 Transformer 的计算通用性证明这样的目标对 Transformer 确实存在，最后落地成一个可微的变分目标放进算法任务里做实证检验。前两步是纯理论的存在性论证，第三步则把抽象保证翻译成能用梯度下降优化的具体损失。

关键设计¶

1. 渐近最优描述长度目标的定义：把"最优压缩"写成可优化的目标

MDL 原则的难点在于"复杂度"本身没有一个干净的定义，论文用柯尔莫哥洛夫复杂度作锚点来回避这个问题。它先把要优化的对象写成一类通用两部分编码（universal two-part code）：给定一族参数化模型 \(\{f_\theta : \theta \in \Theta\}\) 和描述长度函数 \(L(\theta, x)\)（即用参数 \(\theta\) 描述数据 \(x\) 所需的比特数），如果其最小化器 \(\theta^* = \arg\min_\theta L(\theta, x)\) 满足——对所有数据 \(x\)，当模型的资源上界增长时 \(L(\theta^*, x)\) 趋近于柯尔莫哥洛夫复杂度 \(K(x)\)，且差距不超过一个与 \(x\) 无关的加法常数——就称 \(L\) 是渐近最优的。论文进一步证明，这样的"通用"编码构成一个等价类：任何一个通用两部分编码的最小化器，压缩能力都不弱于其他任何两部分编码，因此最优性与具体先验的选择无关。这个定义的妙处在于，它把"找到数据的近似最短描述"这件不可计算的事，转化成了"最小化某个目标函数"这件原则上可操作的事——剩下的问题就变成了：对 Transformer 而言，这样的 \(L\) 到底存不存在。

2. Transformer 计算通用性的新证明：用模拟图灵机搭起存在性的桥

要回答上面的存在性问题，关键是证明 Transformer 具备计算通用性，即能在有限步内模拟任意图灵机。论文给出了一个新的构造性证明，展示 Transformer 编码器如何模拟通用前缀图灵机（universal prefix Turing machine）的计算过程，相比此前工作给出了更精确的资源界限，本身就是一个独立有价值的理论结果。有了通用性，存在性证明便顺理成章：既然 Transformer 能模拟任意可计算的压缩算法，自然也能模拟那个实现最优压缩的算法，因此必定存在某族描述长度目标，其最小化器在资源上界增长的极限下达到渐近最优压缩。这一步把"是否存在最优目标"从悬而未决变成了肯定答案。

3. 自适应高斯混合先验变分目标：把不可计算的保证落成可微的损失

存在性证明虽然积极，却不给出怎么算，论文于是在 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

评分¶

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