从熵到Epiplexity：重新思考计算受限智能的信息

From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence

从熵到Epiplexity：重新思考计算受限智能的信息

https://arxiv.org/pdf/2601.03220

摘要
我们能否从数据中学到比其生成过程中原本包含的更多信息？仅通过对现有数据施加确定性变换，能否构造出新颖且有用的信息？在不考虑下游任务的情况下，我们能否评估数据中可学习的内容？在这些问题上，香农信息论和柯尔莫哥洛夫复杂度几乎束手无策，部分原因在于它们假设观察者具有无限的计算能力，且未能聚焦于“有用的信息”内容。

在本研究中，我们识别并举例说明了信息论中的三个看似悖论的现象：
（1）确定性变换无法增加信息；
（2）信息与数据的顺序无关；
（3）似然建模仅仅是分布匹配。

为阐明这些理论结果与现代机器学习实践之间的张力，并量化数据的价值，我们提出了“epiplexity”（表征复杂度）——一种针对计算能力受限的观察者所能从数据中学到的信息的形式化度量。Epiplexity 捕捉数据中的结构性内容，同时排除“时间受限熵”（time-bounded entropy），即由伪随机数生成器和混沌动力系统所体现的、不可预测的随机内容。

借助这些概念，我们展示了：

• 信息如何通过计算被创造出来；
• 信息如何依赖于数据的顺序；
• 似然建模如何能够生成比原始数据生成过程中更复杂的程序。

我们还提出了若干实用的 epiplexity 估计方法，实验证明这些方法能够：

• 捕捉不同数据源之间的差异；
• 与下游任务性能相关联；
• 揭示那些能提升分布外泛化能力的数据集干预措施。

与模型选择原则不同，epiplexity 为数据选择提供了理论基础，指导我们如何为学习系统选择、生成或变换数据。

1 引言

随着人工智能研究朝着更通用的智能系统方向发展，现有用于奠定数学直觉基础的机制开始显现出裂痕。大量学习理论围绕着控制模型在给定分布下的泛化误差而构建，将训练分布视为固定不变，并将优化努力集中在模型的选择上。然而，现代系统通常需要在训练时未指定的任务、领域和目标之间进行迁移，往往是在大规模、多样化且异构的数据上进行预训练之后实现的。在这一范式下，成功或失败往往较少取决于架构选择，而更多取决于模型最初接触的是哪些数据。

追求对分布外任务的广泛泛化，迫使我们转变视角：不再将数据视为给定的、仅优化模型以提升分布内性能，而是需要主动选择和整理数据，以促进对未见任务的泛化能力。这一转变使得“数据本身的价值”成为一个核心问题——模型能从训练中获得多少可用且可迁移的信息？换言之，与其关注模型选择，我们应如何进行数据选择？对于这一问题，现有理论几乎未提供指导，甚至常常与经验观察结果天真地相矛盾。

请考虑合成数据——当现有自然数据已被耗尽时，合成数据对于进一步提升模型能力至关重要（Abdin 等，2024；Maini 等，2024）。然而，信息论中的既有概念（如数据处理不等式）似乎暗示：合成数据并未带来任何额外价值。关于“某一模型究竟从数据中获得了何种信息”这类问题，表面上理应属于信息论的研究范畴，但使用现有工具对其进行量化却出人意料地困难。甚至一些基本问题——例如 AlphaZero 博弈模型权重中所包含的信息来源（Silver 等，2018）——都令人意外地难以回答。AlphaZero 完全不使用任何人类数据，仅从游戏的确定性规则和 AlphaZero 强化学习算法中学习，而这两者本身都很容易描述。然而，由此训练出的模型不仅规模庞大，而且达到了超越人类的性能水平。若据此断言 AlphaZero 在这一过程中几乎没有学到任何信息，显然严重偏离了事实；然而，香农信息论和算法信息论似乎恰恰得出了这样的结论。

在本文中，我们主张：“计算能力受限的观察者能够从数据集中提取的结构性信息量”是一个根本性概念，它构成了许多经验现象的基础。正如我们将要展示的，当试图量化此类信息时，香农信息论和算法信息论的既有概念是不足的。这些理论框架常常为某些直觉或数学信念提供支持，而这些信念实际上掩盖了经验现象中的关键方面。为凸显经典框架的局限性，并阐明计算约束在信息量化中的核心作用，我们识别并展示了三个看似悖论的现象：这些陈述在香农信息论和算法信息论中均可获得数学上的正当性，却与我们的直觉及实际观察到的经验现象相冲突。

悖论 1：信息无法通过确定性过程增加。
对于香农熵和柯尔莫哥洛夫复杂度而言，确定性变换都无法有意义地增加一个对象的信息内容。然而，我们却使用伪随机数生成器来制造随机性，合成数据能够提升模型能力，数学家可以从公理出发、不依赖外部信息推导出新知识，动力系统会产生涌现现象，而像 AlphaZero 这样的自我对弈循环也能从游戏中学习到复杂的策略（Silver 等，2018）。

悖论 2：信息与因式分解顺序无关。
香农熵和柯尔莫哥洛夫复杂度的一个共同性质是，总信息含量在因式分解顺序上保持不变：先观察 X 再观察 Y 所获得的信息，与先观察 Y 再观察 X 是相同的。另一方面，大语言模型（LLMs）在左至右排列的英文文本上学习效果更好，而非逆序文本，这揭示了一种“时间之箭”（Papadopoulos 等，2024；Bengio 等，2019）；同时，密码学正是建立在某些函数在一个方向上计算困难、而在另一方向上容易预测的基础之上。

悖论 3：似然建模仅仅是分布匹配。
最大化似然常被等同于匹配训练数据的生成过程：真实的数据生成过程本身就是自身最完美的模型，任何模型都不可能达到更高的期望似然值。因此，人们通常假设，在某数据集上训练的模型无法提取比数据生成过程本身更多的结构或学习未用于生成数据的有用特征。然而，我们证明，一个计算能力受限的观察者实际上能够发现比数据生成过程中所包含的更多结构。例如，在康威的生命游戏中，数据由作用于二维比特数组的简单程序规则依次生成。应用这些简单规则后，我们看到涌现出的结构——如不同种类的物体以可预测的方式移动和交互。虽然一个无限制的观察者可以精确模拟环境的演化，但一个计算能力受限的观察者则会利用这些涌现结构，学习不同类型物体及其行为模式。

这些理论陈述与经验现象之间的张力，可以通过对观察者施加计算约束，并将随机内容与结构性内容区分开来加以解决。借鉴密码学、算法信息论以及上述尚未解释的经验现象的思想，我们定义了一种新的信息度量——epiplexity（认识复杂度），它形式化地定义了计算能力受限的观察者能从数据中提取的结构性信息量（第 3 节，定义 8）。简言之，epiplexity 是在计算约束下使数据描述长度最小化的模型中所包含的信息。一种简单的启发式度量方法是损失曲线上最终损失以上的面积，而更严谨的方法则是教师模型与学生模型之间的累积 KL 散度（第 4 节，图 2）。

我们的定义捕捉到这样一个直觉：一个对象既包含随机、本质上不可预测的信息（熵），也包含可预测的结构化信息——这种结构化信息使观察者能够通过识别模式实现泛化（epiplexity）。在图 1（左）中，我们展示了这种区分。在顶部一行，我们展示高度冗余且重复的代码与简单的颜色渐变，它们无论结构还是随机性方面都几乎不含信息内容。在中间一行，我们展示某个算法的内部机制及动物图片，它们呈现出元素间复杂的长程相互依赖关系，模型可从中学习复杂的特征和子电路，即使对不同任务也有帮助。相比之下，在底部一行，我们展示的是几乎没有结构的随机数据：随机生成的 API 密钥、文件路径、哈希值、任意布尔标志等，其可学习内容微乎其微，不存在长程依赖或复杂电路结构，因而在此类数据上训练无法产生任何复杂特征或电路。同样，从动物图片中均匀打乱像素所得的数据具有高熵，但本质上不可预测，训练此类数据也不会产生任何复杂特征或电路。

我们这一框架的一个核心特性是：信息是依赖于观察者的——同一个对象，根据观察者所拥有的计算资源不同，可能表现为随机的或结构化的。例如，一个强伪随机生成器的输出，对于任何缺乏密钥（种子）的多项式时间观察者而言，无论其算法或函数类别如何，都与真正的随机性无法区分。在其他情境中，如混沌动力系统，既会产生看似随机的行为，也同时包含结构：系统的状态在长时间尺度上无法被精确预测，但这类观察者仍可学习到有意义的预测分布，正如图1（右上角）所示的不变测度所体现的那样。

用于表示这些分布的模型本质上是计算机程序，而这些程序中的子结构——比如用于执行特定任务的电路，或“归纳头”（Olsson 等，2022）——即使面对看似无关的数据，也可被复用。这种观点促使我们选择高 epiplexity 的数据，因为这类数据能在模型中诱导出更多结构性信息，而这些结构随后可用于未见过的分布外（OOD）任务，如图1（右下角）所示。然而，我们强调，epiplexity 是一种信息度量，并不保证模型在特定 OOD 任务上的泛化能力。Epiplexity 量化的是模型提取的结构性信息量，而不关心这些结构是否与某个具体下游任务相关。

为建立直观理解，我们探索了一系列现象，并提供了实验证据，说明那些现有信息论工具难以解释、却能自然被 epiplexity 容纳的行为。我们展示了信息可通过纯粹的计算过程被创造出来，从而对合成数据提供新见解（第5.1小节）。我们考察了同一数据的不同因式分解方式如何增加结构性信息及下游 OOD 性能——尽管它们可能导致训练损失更差（第5.2小节）。我们阐明为何似然建模不仅仅是分布匹配，并指出“归纳”和“涌现”是两种场景，在其中观察者能够学到比原始数据生成过程中所含更多的信息（第5.3小节）。通过测量 epiplexity，我们可以更好地理解为何基于文本数据的预训练比图像数据迁移范围更广，以及为何某些大语言模型的数据选择策略在经验上取得成功（第6节）。综合来看，我们的结果澄清了最初提出的几个问题：数据的信息内容可以在不依赖特定任务的前提下进行比较；新信息可通过计算被创造；模型可以学到比其生成过程本身所含更多的信息。

简言之，我们指出了信息论现有概念与现代实践之间的脱节，这体现在三个看似悖论的现象中；为此，我们引入 epiplexity，作为一种衡量计算能力受限的观察者所能获取的结构性信息的指标，以帮助解决这些悖论。我们在第3节（定义8）中正式定义 epiplexity，并在第4节中介绍其测量方法。在第5节中，我们展示 epiplexity 和时间受限熵如何揭示这些悖论的本质，包括归纳和涌现现象。最后，在第6节中，我们证明 epiplexity 与分布外泛化能力相关，有助于解释为何某些数据比其他数据更能支持广泛的泛化能力。

2 背景

为了定义信息中那些有趣、结构性且具有预测性的成分，我们必须将其与随机信息区分开来——后者在给定观察者计算约束的前提下，本质上是不可预测的。在此过程中，我们将回顾算法信息论中发展的算法随机性概念，以及密码学中使用的伪随机性概念，并阐明这些概念如何关键地依赖于观察者。

2.1 一个对象“随机”意味着什么？

随机变量与香农信息。关于随机性的许多常见直觉源于随机变量和香农信息。随机变量定义了一个从给定的可测概率空间到不同结果的映射，其概率对应于导致某一特定结果的空间测度。香农信息根据概率 P，为每个结果 x 分配一个自信息（或意外性）log 1/P(x)，并为随机变量 X 定义熵 H(X) = E[log 1/P(X)]，该熵给出了向另一方传递样本所需的平均编码长度的下界（Shannon, 1948）。在香农理论中，信息仅来源于分布和随机变量。非随机的对象必须不包含任何信息。因此，非随机信息似乎自相矛盾，我们必须从更广泛的数学视角来描述这些概念。

在20世纪中期，数学家们开始尝试精确形式化“一个给定样本是从某个分布中随机抽取的”这一含义，以奠定概率论和随机变量理论的基础（Shafer and Vovk, 2006）。一个核心考虑是均匀采样的二进制序列 u₁:∞，从中可以构造出其他感兴趣的分布。这个序列也可以被解释为区间 [0,1] 中某个数的二进制表达式。直观上，人们可能认为所有序列都应被视为同等随机，因为根据概率分布，它们的可能性均等：例如，111111… 与 10011101… 具有相同的概率质量，也具有相同的自信息。然而，观察这些序列的统计特性会揭示这一观点所缺失的内容；例如，根据大数定律，必须满足 limₙ→∞ (1/N) Σᵢ₌₁ᴺ uᵢ =0.5，而全为1的第一个序列显然不满足此条件。

马丁-洛夫随机性：不存在能预测该序列的算法。最初有人试图将随机性形式化为通过所有统计随机性检验的序列，例如针对选定子串的大数定律。然而，在此类定义下，所有序列都无法被认为是随机的，因为像 u₁:∞ ≠ y₁:∞ 这样的测试对任何特定序列 y 都必须被包括在内（Downey and Hirschfeldt, 2019）。这些问题的解决方案是将随机序列定义为那些通过所有“可计算”随机性检验的序列，这种形式化被称为马丁-洛夫随机性（Martin-Löf, 1966）。事实证明，这一定义等价于若干看似不同的定义，例如：任何赌徒都无法利用序列的性质获利，或者随机序列的所有前缀几乎不可压缩（Terwijn, 2016）。对于最后一个定义，我们必须引入柯尔莫哥洛夫复杂度——一种关于可压缩性的概念，也是本文的一个关键概念。

可以将马丁-洛夫随机性扩展到有限序列。我们称一个序列 x ∈ {0,1}ⁿ 是 c-随机的，如果 K(x) > n − c。等价地，随机性偏差（randomness discrepancy）定义为 δ(x) = n − K(x)，

它衡量的是 x 距离具有最大柯尔莫哥洛夫复杂度有多远。若序列 x 满足 δ(x) < c，则称其为 c-随机序列。高柯尔莫哥洛夫复杂度、低随机性偏差的序列，在从均匀随机采样的随机变量中抽样时出现的概率极高。根据克拉夫特不等式（Kraft, 1949; McMillan, 1956），长度 L ≤ n − c 的（前缀无关）程序至多有 2ⁿ⁻ᶜ 个；因此，在对 X ~ Uₙ 进行均匀采样所得的 2ⁿ 种可能性中，K(X) 的大小为 L 或更小的概率为 P(K(X) ≤ n − c) = P(δ(X) ≥ c) < 2⁻ᶜ。因此，序列的随机性偏差可被视为一种检验统计量，据此人们可拒绝“给定对象 X 确实是从均匀分布中随机采样”的零假设（Grünwald 等，2008）。为了让一个序列具有低随机性偏差，它必须不存在任何可识别的模式，因此在客观意义上，1001011100 比 0101010101 更“随机”。

根据马丁-洛夫对无限随机序列的定义，每个随机序列都是不可计算的；换句话说，不存在任何程序能够实现函数 ℕ → {0,1} 来生成该序列的所有比特位。人们应将此类随机数与像 π/4 或 e/3 这类虽然超越但却是可计算的数区分开来——因为确实存在程序可以计算它们二进制表达式的每一位比特。虽然区间 [0,1] 中的可计算数构成一个可数集，但算法上随机的数在 [0,1] 中数量不可数。考虑到随机序列的不可计算性，我们可以理解冯·诺依曼的名言：

“任何考虑用算术方法产生随机数字的人，当然都处于罪恶的状态。”（Von Neumann, 1951）

这句话预示了后来马丁-洛夫的形式化理论。但这一观点也忽略了一些关键内容，正如伪随机数生成、去随机化和密码学的成功所证明的那样。

密码学随机性：不存在多项式时间算法能预测该序列。随机数的一个重要实践与理论发展来自密码学界，其再次通过限制观察者的计算模型来实现。

与马丁-洛夫随机性要求通过所有可计算检验不同，密码学安全的伪随机数生成器（CSPRNG 或 PRG）被定义为能生成通过所有“多项式时间”随机性检验的序列的函数。

通过多项式时间检验所定义的不可区分性，等价于以下关于序列预测失败的定义：不存在任何多项式时间的预测器，能够以显著优于随机猜测的概率，根据序列的前缀预测出下一个比特（Yao, 1982）。

根据不可区分性定义，在绝大多数实际情境中，这种随机性可以替代马丁-洛夫随机性。² 例如，如果某个使用随机性的应用场景（如快速排序算法）在使用密码学安全伪随机数生成器（CSPRNG）序列时比使用真正随机序列需要更多的迭代次数，并且这种差异可以在多项式时间内被检测到（例如通过测量快速排序的运行时间），那么该构造就可以作为一个多项式时间区分器——但根据 CSPRNG 的定义，这样的区分器并不存在。因此，若 CSPRNG 存在，则快速排序在使用伪随机数生成时的运行速度必须几乎与使用真正随机序列时一样快。

CSPRNG 的存在依赖于单向函数的存在，而 CSPRNG 及其他密码学原语正是基于单向函数构建的，构成了现代密码学的基础。例如，Jax 中用于并行随机数生成的核心算法（Bradbury 等，2018），其工作原理是通过对数字 1, 2, …, N 进行加密来生成随机数 u₁, u₂, …, uₙ：uₖ = E(k, s)，其中加密密钥 s 是随机种子，E 是 Threefish 分组密码（Salmon 等，2011）。分组密码与其他密码原理一样，都是利用单向函数构建的。

其中概率是针对 x 的均匀选择（以及 A 内部的随机性）。

虽然密码学家最关心的是多项式时间与非多项式时间计算分离在安全性方面的意义，但人们已构建并相信存在相对于较弱计算分离的单向函数，例如针对二次时间（Merkle, 1978）、准多项式时间（Liu and Pass, 2024），甚至对电路深度的限制（Applebaum, 2016）。尽管本文所证明的结果基于密码学原语中多项式与非多项式计算分离，但在机器学习背景下，更广泛的计算分离可能同样相关——即使它们对密码学的重要性较低。例如，二次或三次时间与更高阶多项式之间的分离，可能与 Transformer 自注意力机制相关；或者固定电路深度与可变深度之间的差距，可能通过“思维链”或其他机制得以实现。

2.2 随机信息 vs 结构信息

有了上述关于随机性的概念，我们便可以利用“什么是随机的”来定义“什么不是随机的”。在算法信息论中，有一个较少为人知的概念恰好捕捉了这一思想，称为“复杂度”（sophistication）（Koppel, 1988），它在香农信息论中没有直接对应的类似概念。尽管该定义有多个变体，但最直接的一种可能是如下：

定义 5（朴素复杂度）（Mota 等，2013）
复杂度与柯尔莫哥洛夫复杂度类似，定义于单个比特串之上，并使用马丁-洛夫随机性中的可压缩性标准来剥离比特串中的随机内容。复杂度被定义为满足以下条件的集合 S 的最小柯尔莫哥洛夫复杂度：x 是该集合中的一个随机元素（在随机性偏差 c 下）。

非正式地，复杂度（sophistication）描述了一个对象的结构性成分；然而，令人惊讶的是，很难给出高复杂度对象的具体例子。寻找高复杂度对象的困难是柴廷不完备性定理（Chaitin, 1974）的一个结果。该定理指出，在给定的形式系统中，存在一个常数 L，使得没有任何证明能够表明任何特定字符串 x 的柯尔莫哥洛夫复杂度 K(x) > L，尽管几乎所有字符串都具有接近最大值的复杂度。由于 nsoph_c(x) > L 意味着 K(x) > L − O(1)，因此也无法证明任何特定字符串的复杂度超过某个常数。已知通过对角化论证可以证明高复杂度字符串的存在（Antunes 等，2005），但我们无法确定任何具体具有高复杂度的字符串。在典型的图灵机上，L 通常不超过几千（Chaitin, 1998），远小于前沿 AI 模型所编码的太字节级信息量。

我们倾向于将复杂系统和行为视为高复杂度对象的可能实例；然而，在许多情况下，这些对象理论上可通过更简单的描述产生，只需消耗巨大的计算量即可。例如，两种流体的混合可因流体动力学的复杂性而产生极其复杂的瞬态行为；但若拥有无限计算能力并选取适当的随机初始数据，人们应能精确复现其动态过程（Aaronson 等，2014）。由于复杂度定义中允许程序拥有无界计算能力，许多原本复杂的对象会因此失去其“复杂性”。此外，对于确实具有高复杂度的字符串，最优程序所需的计算步骤增长速度比任何具有该复杂度内容的可计算函数都要快（Ay 等，2010）。对于计算能力受限的观察者而言，加密消息或密码学安全伪随机数生成器（CSPRNG）的输出是随机的，那些未能识别这种随机性的测量方法并不能反映该观察者的实际处境。复杂度概念的这些局限性导致它与真实系统之间产生了脱节——真实系统的观察者计算能力有限，而我们认为这种脱节是本质性的，且是涌现、归纳、混沌和密码学等现象的核心所在。

2.3 最小描述长度原则

最后，我们回顾最小描述长度原则（MDL），该原则作为模型选择的理论标准，将在定义 epiplexity 时被使用。该原则指出：在所有用于解释数据的模型中，最佳解释是使数据总描述长度最小化的模型，包括使用该模型对数据本身的描述以及模型自身的描述（Rissanen, 2004）。这一思想最常见的实现方式是统计二分码 MDL。

我们在附录 H 中回顾了 MDL 的现代发展。
虽然 MDL 是在给定固定数据集的前提下用于模型选择的标准，但接下来我们将引入的 epiplexity 可被视为其对偶概念：在给定固定计算预算的前提下，用于数据选择的标准。

3 Epiplexity：计算能力受限的观察者可提取的结构性信息

在牢记无界计算设定下结构性信息与随机信息之间的区分，以及密码学中伪随机性所具有的计算本质的基础上，我们现在引入 epiplexity。Epiplexity 捕捉的是计算能力受限的观察者所能感知到的结构性信息。随着该观察者计算约束的变化，随机内容与结构化内容之间的划分也会随之改变。

在本节中，我们首先引入 epiplexity 的定义；随后在第 4 节中，我们将提出若干测量 epiplexity 的方法；在第 5 和第 6 节中，我们将展示 epiplexity 如何阐明信息论中围绕数据价值和分布外（OOD）泛化的若干看似悖论的现象。

首先，我们将定义一个概率分布何时具有“高效实现”（efficient implementation）：要求该分布能在一台前缀无关的通用图灵机（UTM）上实现，并在固定步数内停机。

此处，n 表示底层样本空间的维度（例如，二进制字符串的长度）。
该定义使我们能够约束函数类所能使用的计算量。此类模型类强制要求所关注的函数既可高效采样，又可高效评估，这涵盖了大多数序列模型。虽然在本研究中，我们主要聚焦于我们认为最基础的计算约束，但其他约束（如内存限制或限定于某个特定函数类 ）也可通过将 ₜ 替换为 来纳入考虑，并可能对理解某些特定现象至关重要。³ 在有了这些预备知识之后，我们现在可以将信息中的随机成分与结构成分区分开来。

我们以实现随机变量 X 最佳期望压缩效果的程序为基准，在给定运行时间约束下，用该程序最小化两部分编码长度（模型本身和在给定模型下的数据比特），从而定义 epiplexity 与时间受限熵。

时间受限熵 Hₜ 捕捉的是随机变量中那些随机且不可预测的信息量，而 epiplexity Sₜ 则捕捉在给定计算水平下对象内部可见的结构与规律性信息量。均匀随机变量具有平凡的 epiplexity，因为一个像均匀分布一样简单的模型即可实现较小的两部分编码长度，尽管其时间受限熵较大。具体而言，对于定义在 {0,1}ⁿ 上的均匀随机变量 Uₙ，即使时间约束 T(n) ≥ c₁ 为常数，也有 Sₜ(Uₙ) + Hₜ(Uₙ) ≤ n + c₂，其中 c₂ 是运行时间为 c₁ 的均匀分布程序的长度；又因 Hₜ(Uₙ) ≥ H(Uₙ) = n，故必有 Sₜ(Uₙ) ≤ c₂。具有非常简单模式的随机变量（例如以 1/2 概率出现的 0101010101… 和以 1/2 概率出现的 1010101010…）同样具有低 epiplexity，因为其时间受限 MDL 最优模型是简单的。在此线性时间约束 T(n) = Θ(n) 的情况下，Sₜ(X) = O(1) 且 Hₜ(X) = O(1)。因此，我们将简记 MDLₜ(X) := Sₜ(X) + Hₜ(X)，即总的时间受限信息含量。接下来，我们将列举这些定义的一些基本推论。

命题4（针对在固定时间内运行并实现双射的程序 f）是信息不增性质 K(f(x)) ≤ K(x) + K(f) + c 的一个类比。然而请注意，在我们设定的固定计算预算下，虽然函数 f 及其逆函数 f⁻¹ 的柯尔莫哥洛夫复杂度 K(f) 与 K(f⁻¹) 在加性常数内相等，但拥有一个关于 f⁻¹ 的简短程序并不意味着也存在一个关于 f 的简短程序，反之亦然。这种函数与其逆函数之间的差距，对后文第5节中将讨论的三个悖论具有重要影响。

伪随机数序列具有高随机内容和极少结构。
不同于香农熵、柯尔莫哥洛夫复杂度，甚至资源受限形式的柯尔莫哥洛夫复杂度（Allender 等，2011），我们证明：对于多项式时间观察者而言，密码学安全伪随机数生成器（CSPRNGs）具有接近最大的时间受限熵。此外，尽管 CSPRNGs 产生的是随机内容，它们并不产生结构性内容，因为其 epiplexity 仅略大于某个常数。形式上，令 Uₖ 表示 k 比特上的均匀分布。

相比之下，香农熵为 H(G(Uₖ)) = k；在多项式时间约束下，柯尔莫哥洛夫复杂度最多为 k + c（假设 n 是固定的或预先指定的），因为存在一个简短且可高效运行的程序 G 能够生成输出；类似地，对于其他概念如 Levin 复杂度（Li and Vitányi, 2008）或时间受限的柯尔莫哥洛夫复杂度（Allender 等, 2011）也是如此。综合来看，这些结果表明：epiplexity 恰当地刻画了伪随机数——它们携带大量时间受限的随机性，但本质上几乎不包含任何可学习的结构，这与直觉完全一致。

高 epiplexity 随机变量的存在性。人们可能会质疑：是否真的存在任何具有高 epiplexity 的随机变量？事实上，在单向函数存在的前提下，我们可以通过计数论证证明：存在一系列随机变量，其 epiplexity 至少随维度呈对数增长。

从这一结果中我们得知，至少确实存在具有任意大的 epiplexity 的随机变量；然而，这种对数增长的信息含量仅包含非常有限的信息量，仍远未达到我们在某些自然数据中观察到的幂律缩放现象。

条件熵与 epiplexity。为了描述图像分类等场景——在这些场景中，我们只关心一个能根据图像预测标签的函数，而不关心生成图像本身所包含的信息——我们定义了“条件时间受限熵”和“条件 epiplexity”。

在机器学习场景中，我们用随机变量 X 表示所关注的整个数据集，即通常是从某个给定分布中抽取的大量独立同分布（iid）样本的集合 [X₁, X₂, ...]，而非单个样本；且期望值 [log 1/P(X)] 随数据集规模增长。Epiplexity 通常随数据集规模增大而增长（详见附录 B.4 中关于此现象的详细论证），因为更大的数据集允许识别并提取更复杂精细的结构与模式，这与机器学习训练实践相吻合。此外，正如我们后文将看到的，一个典型数据集的 epiplexity 比其随机信息含量小几个数量级。虽然本文并不聚焦于此，但对确定性字符串进行条件化处理，可以打开理解“哪些额外数据对特定机器学习模型最有用”的可能性，例如用于预训练大语言模型（LLM）后的微调阶段。

4 测量 Epiplexity 和时间受限熵

我们现已引入 epiplexity 和时间受限熵作为衡量数据中结构性和随机性信息的指标。在本节中，我们将介绍用于估计这些量的上界及经验代理指标的实际方法。直观上，我们希望找到一个概率模型 P(·)，它能对数据 X 实现较低的期望损失 [log 1/P(X)]，该模型由一个简短程序 P 描述，且评估 P(X) 所需时间至多为 T(|X|)，我们将其简记为 T。利用这个模型，我们便可将数据的信息分解为其结构性成分与随机性成分，即：

（1）epiplexity Sₜ(X)：程序 |P| 的长度，代表用于建模数据分布所需的比特数；

（2）时间受限熵 Hₜ(X)：使用该模型对数据进行熵编码时的期望长度，代表指定该分布下 X 的具体实现所需的比特数。

我们以类似方式估计条件 epiplexity，即将随机变量作为输入提供给模型。

由于直接在程序空间中搜索是不可行的，我们将注意力集中在由神经网络参数化的概率模型上，因为它们在各类数据模态上均表现出强大的经验压缩能力（MacKay, 2003; Goldblum 等, 2023; Delétang 等, 2023; Ballé 等, 2018），并能捕捉最相关的机器学习现象。一种朴素的方法是让 P 直接存储神经网络的架构与权重，并在给定数据上对其进行评估，但这种方法会显著高估权重中的信息含量，尤其对于在相对少量数据上训练的大模型而言。取而代之的是，我们将采用一种更高效的方法，通过编码生成权重的训练过程来实现。我们将讨论两种编码神经网络训练过程的方法，分别基于 前序编码（prequential coding）（Dawid, 1984）和 序列编码（requential coding）（Finzi 等, 2026）。前者更容易理解和评估，但依赖于启发式方法来分离结构比特与噪声比特；后者则更为严谨，代价是评估起来更困难。幸运的是，这两种方法在不同数据集上的 epiplexity 排名通常相当接近（见第 4.3 节）。

接下来，我们将以浮点运算次数（FLOPs）来衡量时间，以 token 数量来衡量数据集规模。因此，训练一个拥有 N 个参数的模型在 D 个 token 上所需时间约为 6ND（Kaplan 等，2020），而在数据集 X 上评估该模型所需时间为 2ND，其中 D = |X| 表示 X 中的 token 总数。为区分 X 与训练数据集（我们可以自由选择），我们将 X 称为测试数据集，因为它是我们需要进行推理的数据。

4.1 使用前序编码近似模型描述长度

前序编码提供了一种经典的压缩神经网络训练过程的方法。为简化起见，我们假设批大小为 1，但将其推广到更大的批大小是直接可行的。我们从一个随机初始化的网络 P₀ 开始（下标表示时间步），然后迭代进行：在每一步 i，我们使用 log 1/Pᵢ(Zᵢ) 比特对当前训练 token Zᵢ 进行熵编码，然后用该 token 训练模型以产生下一个模型 Pᵢ₊₁。通常，Zᵢ 是从与 X 相同分布中独立同分布（i.i.d.）抽取的。在解码器一侧，维护一个同步的模型；该模型使用 Pᵢ 解码 Zᵢ，然后对其进行训练以产生相同的 Pᵢ₊₁。忽略指定随机初始化、架构和训练算法所需的微小常数开销，总编码长度 L(Z:M, Pₘ) = Σᵢ₌₀ᴹ⁻¹ log 1/Pᵢ(Zᵢ) 比特，即可同时为训练数据 Z:M = {Z₀, ..., Zₘ₋₁} 和最终模型权重 Pₘ 提供一个显式编码。对于一个在 D个 token 上训练、拥有 N个参数的模型（通常 D > M，因为每个样本包含多个 token），该编码可在6ND 时间内完成解码。

4.2 使用序列化编码显式编码模型

4.3 两种方法的比较与实用建议

图2c比较了本工作所用四组数据集上通过两种方法获得的估计表征复杂度：ECA（第5.1节）、简单与困难归纳（第5.3.1节）以及自然数据集（第6.2节）。虽然序贯估计通常比前序估计大数倍，但两者相关性良好，尤其是在每组内数据集具有相似学习动态的情况下。我们在附录C.7中详细说明所用数据集和时间约束。这种总体一致性是预期的，因为前序估计可被视为使用静态教师模型的序贯编码的一种近似（附录B.2）。然而，一般而言，两种估计之间的差异将取决于特定数据集和训练配置，二者之间良好的相关性并不能保证。

尽管序贯编码是更严谨的方法，但它通常比前序编码慢2至10倍，而前序编码仅需标准训练。开销取决于批量大小、序列长度和推理实现方式（大批量和短序列时开销较小），因为序贯编码需要反复从教师模型采样，尽管通过更高效的算法有可能降低开销。因此，我们建议在粗略估计表征复杂度及对不同数据集的表征复杂度进行排序时使用前序编码，特别是当已能获取现有昂贵训练运行的损失曲线时（例如，参见第6.2节中的应用）；而在其他情况下，为获得最精确的估计，则应使用序贯编码。

4.4 表征复杂度与时间约束熵如何随计算量和数据规模变化

5 信息的三个表面悖论

为了说明现有信息理论视角中的空白，我们强调了信息的三个“表面悖论”：(1) 信息不能通过确定性变换产生；(2) 一个对象的总信息量与其分解方式无关；(3) 似然建模只能学会匹配数据生成过程。每一条陈述都捕捉到了机器学习社区内现有的某种共识，可以从香农信息论和算法信息论中得到数学上的支持，但似乎又与直觉和实验观察相冲突。在本节中，我们将通过理论结果和实证证据表明，时间约束和表征复杂度有助于解决这些表面悖论。

5.1 悖论一：信息不能由确定性变换产生

那么，我们如何调和这一事实与像 AlphaZero (Silver 等, 2018) 这样的算法？AlphaZero 能在一个封闭环境中仅靠一个小的确定性程序运行国际象棋游戏，从中提取出关于游戏、不同开局、棋子在不同位置的相对价值、战术和高层策略的洞见，并需要将兆字节的信息存储在权重中？类似地，我们也拥有具有简单底层规律描述的动态系统，却能产生丰富且意想不到的结构，我们可从中学习到关于它们和数学的新知识。

我们也有证据表明合成数据是有用的 (Liu 等, 2024; Gerstgrasser 等, 2024; Maini 等, 2024; OpenAI, 2025)，它有助于提升模型能力；而且，如果我们相信生成自然数据的过程原则上可以在大型计算机上被模拟到足够精度，那么所有数据都可以被等价地替换为合成数据。对于从给定模型和提示中采样并经过变换产生的实用合成数据，这种采样是通过伪随机数生成器完成的，从而使整个变换过程成为确定性的。如果我们把 f f 视为我们用来生成合成数据的变换，而 x x 是我们最初拥有的有限真实数据，这些不等式似乎非常具体地指出：我们的合成数据除了模型和训练数据外，没有添加任何额外信息。

无论当我们说 AlphaZero 在国际象棋中产生了新的、出人意料的洞见，或在数学中获得了新的理论结果，或使用合成数据时所指的“信息”是什么，它都不是香农信息或算法信息。我们认为，信息理论中这些违反直觉的特性，源于假设观察者拥有无限计算能力。在计算能力受限的情况下，对 AlphaZero 算法的描述与运行 AlphaZero 数千 TPU 小时后得到的结果是截然不同的。为了建立直觉，我们从简单的 CSPRNG 开始，它同样通过计算（尽管是随机信息）创造出时间约束信息。

我们可以得到截然不同的结果：产生简单对象、仅产生随机内容，或产生随机与结构化内容的混合。

5.2 悖论二：信息含量独立于分解方式

另一方面，多项研究已观察到，当自然文本（如英文）按从左到右顺序建模时，比按反向顺序建模时压缩效果更好（最终模型达到更高的似然值）(Papadopoulos et al., 2024; Bengio et al., 2019)，这揭示了大语言模型中存在“时间之箭”，即一种方向上的建模优于另一种。似乎对于许多文档而言，其他排序方式可能导致大语言模型提取出更多不同的信息以及下游性能差异。类似地，正如我们稍后将展示的那样，数据的微小重排也可能导致显著不同的损失和下游性能。密码学原语（如单向函数和分组密码）同样提供了例子，表明条件化的顺序会对数据的熵表现产生决定性影响，例如考虑对两个素数及其乘积进行自回归建模，与采用相反顺序建模的情况。这些实验结果和密码学思想表明，可以学到的内容依赖于数据的排序方式，这反过来又暗示从不同排序方式中提取出的“信息”量是不同的。

我们的时间约束定义捕捉到了这一差异。在存在单向置换的情况下，我们可以证明，对于时间约束熵，不同分解方式之间存在预测差距。

作为一个推论，我们证明不存在任何多项式时间的概率模型，能够满足单向函数前向方向的贝叶斯定理（见定理26）。在这些理论结果的基础上，我们实证地考察了单向函数在时间约束熵上的差距，以及在预测国际象棋数据时两种排序方式下熵和表征复杂度的差距。

在图4(a)中，我们选择 f f 为具有大小为 n n 的状态和周期性边界条件的ECA规则30演化8步的结果 (Wolfram and Gad-el Hak, 2003)。尽管与密码学中使用的单向函数不同，规则30被认为是一种单向函数 (Wolfram and Gad-el Hak, 2003)，并且与典型的单向函数不同的是，规则30的前向传递可以通过自回归变换器建模，我们通过在附录D中构建一个显式的RASP-L (Zhou et al., 2023; Weiss et al., 2021) 程序来证明这一点。如图4(a)所示，该模型在前向方向上达到了香农熵（灰色），但在反向方向上存在持续的差距。

除了随机信息如何随排序方式变化之外，结构信息也可能有所不同，正如我们接下来将展示的那样。我们通过在Lichess数据集上训练自回归变换器模型来证明这一事实，该数据集是一个大型的国际象棋对局集合，其中走法以代数记谱法记录。我们考虑该数据集的两个变体：(1) 将每局棋按走法序列后接最终棋盘状态（FEN记谱法）的形式进行格式化；(2) 将每局棋按最终棋盘状态后接走法序列的形式进行格式化，如图4b所示。我们在第C.4节中提供了完整的实验细节。虽然在此设置中没有明确的多项式与非多项式时间分离，但第一种排序方式类似于前向方向，因为最终棋盘状态可以通过一个简单函数直接从走法映射得到，而后者排序方式则类似于反向方向，因为从最终棋盘状态恢复走法需要逆函数来推断中间步骤。我们假设反向方向是一个更复杂的任务，将引导模型获取更多结构信息，例如对棋盘状态更深入的理解。图4c证实了这一假设，显示反向排序方式具有更高的时间约束熵和表征复杂度。当计算预算较小时，这种差距会消失，此时模型可能仅学习到两种排序方式共有的表面统计特征，而在额外的反向任务复杂性迫使模型发展出更丰富的棋盘状态表示之前。

5.3 悖论三：似然建模仅仅是分布匹配

有一种普遍的观点认为，从特定的训练分布出发，我们最多只能期望匹配数据生成过程。如果某个属性或函数不在数据生成过程中，则我们不应期望在模型中学习到它。作为一种延伸，如果生成过程很简单，那么试图匹配它的模型也应同样简单。这种观点可以通过抽象地考虑似然最大化过程 arg ⁡ min ⁡ P E X ∼ Q [ − log ⁡ P ( X ) ] = Q来支持：当两个分布匹配时，测试负对数似然（NLL）达到最小值。分布之间的差异程度被视为由于函数类过于受限或数据不足导致泛化失败。从这些论证出发，我们有理由相信，AI模型在人类数据上预训练时无法超越人类智能。在这里，我们提供两类似乎与此观点相矛盾的现象：归纳和涌现。在这两种情况下，限制提供给AI模型的计算量会导致它们提取比实现生成过程本身所需更多的结构信息。

5.3.1 归纳（Induction）

生成建模领域常常面临一个挑战：既希望采样过程易于处理，又希望似然评估也易于计算。自回归模型、扩散模型、变分自编码器（VAE）、生成对抗网络（GAN）和标准化流（normalizing flows）等方法各自提供了不同的解决路径。对于自然的生成过程而言，通常其中一个方向（采样或似然计算）会比另一个方向简单得多。在此，我们研究一类生成过程：它们通过变换隐变量构造而成，而要计算其似然，就需要对这些隐变量的取值进行归纳推理。

这一现象可从 Ilya Sutskever 的一段引述中获得直观理解：

“你正在读一部谋杀悬疑小说，文本在某个时刻揭示了凶手的身份。……如果模型能够预测出[这个姓名]，那么它必定已经从所提供的证据中推断出[谁是凶手]。”（Sutskever, 2019）

然而，书的作者却未必需要进行同样的归纳推理。相反，作者可能先选定凶手，然后再精心编织一个关于其行为的引人入胜的故事。这个例子突显了生成过程与预测模型所需能力之间的差距——这正是我们接下来通过以下更数学化的设定所要探讨的。

另一方面，书的作者无需进行相同的归纳推理。相反，他们可能先选定凶手，然后编织一个关于其行为的引人入胜的故事。这个例子突显了生成过程与预测模型所需能力之间的差距——我们将在以下更数学化的设定中探讨这一差距。

归纳困难：规则30 ECA

以及通过掩码进行简单后处理来移除比特。这一图像被测量的表征复杂度所镜像：随着模型被迫对缺失比特进行归纳，表征复杂度随之增长。

归纳容易：随机马尔可夫链

在归纳困难和归纳容易的两个例子中，执行归纳策略所需的程序规模都大于生成数据所需的程序规模。我们可以预期，在计算资源受限的情况下，通常无法通过暴力穷举法逆转生成过程；因此，在存在替代性逆向策略的情形下（例如统计归纳头的简单归纳示例），这些额外的策略会增加表征复杂度。鉴于很可能不存在适用于所有问题的单一通用逆向策略，这些策略很可能会成为表征复杂度的一个来源。

为了使上述陈述更精确，似乎不太可能存在常数 ，使得以下性质成立：

对“分布匹配”观点最引人注目的反例之一是“涌现”（emergence）。即使一个系统的底层动力学可以用简单的描述来刻画，一个计算能力有限的观察者也可能需要学习一套更丰富、看似无关的概念集合，才能预测或解释其行为。正如 Anderson (1972) 所阐述的，还原论——即复杂物体的行为源于其组成部分——并不能保证：仅仅了解这些部分就足以让我们预测整体。在生物学和物理学中，多体相互作用会产生一些行为（例如鸟群、康威生命游戏中的模式、分子化学、超导性），这些行为无法仅从微观定律中直接看出。在此，我们简要说明“涌现”如何与观察者的计算约束密切相关，并展示那些预测未来状态的观察者，可能需要比能够完整执行生成过程的无约束对应者学习更多知识。

考虑 Carroll 和 Parola (2024) 分类中的 IIb 型涌现，在该分类中，高层模式由局部规则产生，却抵抗从这些规则进行预测。一个典型例子是康威生命游戏（参见附录 E 以获取定义），其中在一个二维网格上迭代一个简单的计算规则 Φ 会导致复杂的涌现行为。对于缺乏足够计算资源以直接计算迭代演化 的观察者，必须找到一种替代性的描述方式。在状态演化过程中，可以识别出局部化的“物种”（静态块、振荡器、滑翔机、枪），它们在空间和时间中传播。通过将这些物种分类，学习它们的速度，以及它们在与其他物种碰撞时如何被改变，计算能力受限的观察者便能对系统的未来状态做出预测。然而，这样做在描述长度的意义上需要一个更复杂的程序，因此表征复杂度会更高。我们可以将这一直觉形式化为以下关于“涌现”的定义。

在图6中，我们通过训练一个变换器模型来预测ECA规则54（一种产生复杂模式的IV类规则）的迭代动力学，实证地展示了涌现现象。与康威生命游戏类似，计算能力充足的模型可以通过直接迭代每一步规则来精确模拟动力学——这是一种描述长度很短的暴力求解方案。然而，计算资源受限的模型无法承担这种方法，而必须转而学习涌现的模式（例如滑翔机及其碰撞规则），从而近似地绕过不可行的精确模拟。暴力求解方案可以通过学习自回归展开中间ECA状态（而非直接预测最终状态）自然实现，这类似于“思维链”（Wei et al., 2022）或“循环式变换器”（Dehghani et al., 2018; Giannou et al., 2023; Saunshi et al., 2025）的应用。我们在第C.8节提供了实验细节。

尽管最初，非循环模型（直接预测最终状态）随着计算量增加会逐渐获得更好的MDL和更高的表征复杂度，但我们识别出一个关键的计算阈值：超过该阈值后，循环模型突然变得更有利，导致MDL和表征复杂度骤降，这很可能是因为模型学会了简单的暴力求解方案。低于此阈值时，循环模型表现不佳，可能是因为其缺乏足够计算力以完整展开动力学过程。而非循环模型由于无法依赖暴力模拟，必须转而学习日益复杂的涌现规则，识别出更多“物种”及其相互作用，因此表征复杂度起初随计算量增加而上升，之后才下降。

虽然本实验清晰地证明了计算受限的模型如何从数据中学习更丰富的结构，但它是一个罕见的例子：暴力求解方案在实验上是可及的，因此增加计算量反而可能适得其反。在大多数实际场景中（如AlphaZero或建模自然数据），对应的简单暴力求解方案在计算上是不可行的，例如对天文级规模的游戏树进行穷举搜索，或通过模拟物理定律来预测自然数据。因此，在大多数情况下，使用更多计算量训练的模型确实会继续学习到更多结构，因为暴力求解变得可行的阶段仍遥不可及。

我们在附录F中探讨了其他类型的涌现现象，例如在混沌动力系统中或在博弈智能体最优策略中的涌现。这些例子均提供了明确证据：为了追求能最好解释数据的概率分布，计算能力有限的观察者需要比最小数据生成过程具有更长描述长度的模型，才能达到相当的预测性能（Martínez et al., 2006; Redeker, 2010）。表征复杂度提供了一个通用工具，用于理解和量化这些涌现现象，以及理解简单规则如何创造出有意义且复杂的结构，供AI模型从中学习——Zhang等人（2024）最近已对此进行了实证验证。

6 表征复杂度、预训练与分布外泛化

在互联网规模数据上进行预训练已带来了显著的分布外（OOD）泛化能力，然而对这一现象的深入理解仍然不足。什么样的数据能提供最佳信号以实现广泛泛化？为什么在文本数据上进行预训练所获得的能力可以跨领域迁移，而图像数据却不行？随着高质量互联网数据逐渐耗尽，我们应依据何种指标来指导新预训练数据的选择或合成？在本节中，我们将展示表征复杂度（epiplexity）如何帮助回答这些基础性问题。

分布外泛化的本质在于模型习得了多少可复用的结构，而非其在分布内预测得有多好。两个在不同语料库上训练的模型可能达到相同的分布内损失，但在迁移到OOD任务时的能力却大相径庭。这是因为损失仅捕捉了残余的不可预测性——对应于时间约束熵——而并未反映模型为达到该损失所内化的可复用结构量。表征复杂度恰好衡量了这一缺失的成分：即学习到的程序中所包含的信息量。直观地说，损失反映了数据在模型眼中看起来有多“随机”，而表征复杂度则反映了模型必须习得多少结构才能解释掉其中的非随机部分。如果OOD泛化依赖于复用所学机制，而非仅仅记忆表面统计特征，那么表征复杂度就自然成为理解预训练数据与OOD迁移之间关系的一个恰当视角。

作为一个启发性的玩具示例，Zhang 等人（2024）观察到，IV类ECA规则往往对下游任务更有益，这与我们在图3中展示的结果一致：规则54（一种IV类规则）所诱导的表征复杂度远高于其他类型的ECA规则。

6.1 表征复杂度与国际象棋中的分布外泛化呈正相关

我们在第5.2节所述的两种排序方式（走法在前 vs. 棋盘状态在前）上训练的模型基础上，对两个下游任务进行微调：(1) 解国际象棋残局题（chess puzzles），即给定一个棋盘局面，模型需预测最优的下一步走法（Burns 等, 2023）；(2) 预测“厘兵”（centipawn）评估值，即模型根据FEN记谱法对局面优势进行量化评估——这相比预训练中学到的“预测下一步走法”任务构成了更显著的分布偏移。实验细节见第C.4节。

如图7所示，反向排序（先棋盘状态、后走法序列）产生了更高的表征复杂度，并带来了更好的下游任务表现：在国际象棋残局题上的准确率相当，但在厘兵评估任务上的准确率显著更高。这一结果支持了我们的假设：反向排序迫使模型发展出更丰富的棋盘状态表征，以推断中间走法；而这些表征能够迁移到同样需要理解棋盘状态的OOD任务（如厘兵评估）中。

该例子反映了一个更普遍的原则：表征复杂度衡量的是模型从数据中提取并编码到权重中的可学习结构信息量，而这正是可迁移到新任务的信息来源，因此表征复杂度是衡量OOD泛化潜力的一个合理指标。然而，我们强调，更高的表征复杂度并不能保证在任意特定任务上获得更好的泛化效果：表征复杂度衡量的是结构信息的总量，而不涉及其具体内容。一个在高表征复杂度数据上训练的模型可能学到大量结构，但这些结构是否与特定下游任务相关，则另当别论。

6.2 自然数据中结构信息的度量

在各类自然数据模态中，语言被证明在预训练方面具有独特的优势：不仅有助于提升分布内性能（如语言理解能力，Radford 等, 2019），还能有效迁移到分布外任务，例如机器人控制（Ahn 等, 2022）、形式化定理证明（Song 等, 2024）以及时间序列预测（Gruver 等, 2023）。尽管其他模态（如图像和视频）也提供了同样海量的信息（以原始字节数衡量），但在这些数据上进行预训练通常无法带来类似广泛的能力提升。

我们现在展示，表征复杂度（epiplexity）有助于解释这种不对称性，因为它揭示了不同数据集中结构信息的差异。在图8a中，我们展示了使用序贯编码（requential coding）对 OpenWebText、Lichess 和 CIFAR-5M（Nakkiran 等, 2020）三个数据集各50亿（5B）个标记（tokens）所估计的信息分解结果——将总信息分解为表征复杂度（结构部分）和时间约束熵（随机部分），计算时间上限设为

FLOPs，所用模型最大参数量为1.6亿（160M），且每个数据集最多使用50亿个标记进行训练。

在所有情况下，表征复杂度仅占总信息的极小一部分：其中 OpenWebText 数据包含最多的表征复杂度，其次是国际象棋（Lichess）数据。尽管 CIFAR-5M 数据的总信息量最大，但其表征复杂度却最低——超过99%的信息属于随机成分（例如，具体像素值的不可预测性）。

6.4 语言模型的预训练数据选择与课程设计

预训练语言模型的一个关键步骤是设计预训练数据的构成，但目前尚缺乏对此步骤的明确指导原则。现有的数据混合方案通常通过大量试错法设计，并依赖于“多样性”或“高质量”等启发式准则。更重要的是，比较不同训练数据的主要方式是通过保留数据集的困惑度指标以及下游任务表现。然而，这些程序极易受到数据污染、对有限下游评估任务的过拟合以及古德哈特法则的影响。毕竟，没有任何一套下游评估任务能够足够全面地真实捕捉通用语言模型在现实世界中会遇到的任务范围。

正如我们上文所述，表征复杂度衡量的是模型所学习到的结构信息，而这可能会受到数据选择策略的影响。Jiang 等人（2025）证明，不同数据子集的损失曲线可用于在线动态调整数据分布，以优先选择那些训练损失下降更快的数据子集。直观上，这一目标与第4.3节中描述的前序近似表征复杂度是一致的，因为它导致损失曲线下方的面积更大。我们假设，他们提出的算法——自适应数据优化（ADO）——无意中实现了更高的表征复杂度。Jiang 等人（2025）的实验是在仅解码器的变换器模型上进行的，该模型拥有13亿（1.3B）参数，在来自 Pile 数据集（Gao 等, 2020）的1250亿（125B）个标记上进行训练。模型在一套包含7项零样本下游任务以及两个OOD验证数据集（SlimPajama（Soboleva 等, 2023）和 FineWeb（Penedo 等, 2024））上进行评估。

在图8c(c)中，我们展示了基于 Jiang 等人（2025）改编的两个OOD数据集上的估计表征复杂度、下游性能以及困惑度。如 Jiang 等人（2025）所示，ADO 在下游性能上优于一种标准的数据采样策略（即从整个数据集中均匀采样，在图8c中记为 Natural），尽管它并未针对这些指标中的任何一个进行优化。有趣的是，我们看到 ADO 确实通过前序编码测量获得了更高的表征复杂度。虽然这些下游评估无法完全捕捉预训练模型的所有特性，但它们确实提供了证据，表明表征复杂度是一个潜在有用的工具，可用于理解预训练数据的内在价值，而无需依赖特定的下游评估任务。

7 相关工作补充

表征复杂度（Epiplexity）建立在算法信息论与复杂性科学中若干相关思想的基础之上，这些思想试图从理论上刻画“有意义的信息”。一组密切相关的核心概念包括精巧度（sophistication，见2.2小节）、有效复杂度（effective complexity）和逻辑深度（logical depth）。与精巧度类似，有效复杂度旨在将随机成分与结构成分分离开来（Gell-Mann 和 Lloyd, 1996）。从另一个出发点，Bennett（1988）提出了逻辑深度，用以衡量一个接近最优的程序生成给定字符串所需的计算步数；后来研究通过“忙海狸函数”（busy beaver function）证明了逻辑深度与精巧度等价（Antunes 等, 2005；Ay 等, 2010）。

此外，还有若干其他形式化度量被提出，用于量化结构化或有意义的复杂性。算法统计学（Algorithmic statistics）通过引入“算法充分统计量”（algorithmic sufficient statistic）的概念，为数据提供了规则成分与随机成分的原理性分解（Vereshchagin 和 Vitányi, 2004），这一概念与精巧度紧密相关。类似地，计算力学中的统计复杂度（statistical complexity）（Shalizi 和 Crutchfield, 2001）衡量的是在最优预测模型中因果状态的熵，从而捕捉时间序列数据中的结构。

正如我们前文所论证的，这些现有的复杂性概念未能考虑观察者所拥有的有限计算能力——而这一点对于理解机器学习算法至关重要。由于对计算限制视而不见，这些理论无法将密码学安全伪随机数生成器（CSPRNG）或加密对象视为“随机”的。有人或许会认为这些缺陷只是表面问题；例如，一种看似合理的策略是在精巧度定义中（定义5）将柯尔莫哥洛夫复杂度替换为时间约束下的柯尔莫哥洛夫复杂度。然而，这种方法存在多个问题，最明显的是：CSPRNG 的输出确实存在短且可高效运行的生成程序，因此其时间约束柯尔莫哥洛夫复杂度很小。更微妙的原因是，这样做会导致所有字符串的精巧度退化为平凡值（trivial sophistication），我们在附录 A.6 中对此有更详细的讨论。

我们的工作也与若干试图刻画“观察者依赖型信息”（observer-dependent notions of information）的研究密切相关。在密码学中，Barak 等（2003）和 Hsiao 等（2007）讨论了计算伪熵（computational pseudoentropy）的几种可能定义，这是熵的一种观察者依赖型类比。HILL-伪熵（Håstad 等, 1999）相对于某一类测试函数定义：若该类中没有任何测试能以非平凡优势区分某信源与高熵分布，则该信源被视为随机；Yao-伪熵则通过对象的压缩与解压缩过程定义。这两种定义都与时间约束熵密切相关——后者衡量的是在给定计算受限观察者眼中数据的随机成分。然而，我们的表述直接映射到机器学习实践，并且能够分离出结构信息成分，这是我们工作的关键贡献。

最近，Xu 等（2020）提出了 V-熵（V-entropy），它是香农熵在给定概率模型族（如具有特定计算约束的模型）下的最小期望负对数概率的推广。在 V-熵框架下，信息对称性和数据处理不等式均可被违反，尽管论文中并未明确证明这两点。与时间约束熵不同，V-熵中的计算约束仅限制推理时间，而不考虑寻找该模型所需的时间。因此，其最小化器可能远离实际评估的区域（例如在无限数据或无限计算下训练的模型）。虽然通过施加额外的数据约束可以克服这些不良行为，但我们认为，对训练和推理时间施加单一统一的计算上限，能带来更少的概念复杂性。

更重要的是，无论是伪熵还是 V-熵，与时间约束熵一样，它们仅捕捉信息的随机成分，因为它们仍然衡量的是在最佳可行模型下随机变量的不可预测性。而要理解模型究竟学到了哪些有用信息，我们更关注的是由表征复杂度所度量的非随机成分。

利用现有的数据复杂性度量（如 Lempel-Ziv 复杂度和 Wolfram 分类），Zhang 等（2024）表明，在 IV 类 ECA 规则等复杂数据上训练的模型往往在下游任务中表现更好。

另有若干研究探索了如何量化数据复杂性。Dziugaite 和 Roy（2025）提出，在 PAC-Bayes 框架下，一个近似最优参考模型的最小复杂度可视为数据复杂性的度量，并说明这种数据复杂性如何导致经验缩放律。这一视角与表征复杂度相关，因为两者都将数据复杂性与能良好解释数据的紧凑模型的规模联系起来。但二者在关键方面存在差异：PAC-Bayes 表述关注的是存在某个小型参考模型能在分布内取得良好性能，而表征复杂度则刻画了计算受限观察者可提取的结构信息量，并通过一个显式计入模型获取成本的两部分码进行形式化。此外，我们的主要兴趣并非刻画分布内泛化，而是利用表征复杂度来衡量数据在超越监督学习场景中的内在价值。

相关地，Hutter（2021）表明，在对数据生成分布做出特定假设时，幂律学习曲线会自然出现，这说明数据本身的属性可塑造经验缩放行为。尽管这类工作侧重于解释观察到的学习动态而非定义复杂性度量，但它同样强调了数据结构在决定学习结果中的作用。

这些关于数据复杂性的视角可视为“粗粒化”（coarse graining）的实例，即寻求一种压缩表示，同时保留某种“相关”结构。典型例子是信息瓶颈（Information Bottleneck）框架，它将粗粒化形式化为压缩与保留关于相关变量信息之间的权衡（Tishby 等, 2000）。表征复杂度与此视角一致，但不同于通过任务变量或测试可区分性来定义“相关性”，它衡量的是计算受限学习者可提取的结构信息量，并显式计入获取模型的成本。

更广泛地说，我们的工作与若干探讨资源约束如何根本性改变“简洁性”与“可学习性”概念的研究相关。在算法信息论中，Schmidhuber（2002）提出了“速度先验”（speed prior），用一个可计算的半测度替代 Solomonoff 的通用先验，该半测度同时偏好更短的程序长度和更小的计算时间，从而将计算资源直接纳入简洁性的定义。在学习理论中，相关研究表明，计算限制可直接影响从数据中能学到什么。例如，在稀疏 PCA 检测问题中，Berthet 和 Rigollet（2013）证明：尽管存在信息论意义上样本效率最优的算法，但在广泛采用的平均情况硬度假设下，任何多项式时间算法必然需要更多数据。仅内存和空间约束本身也能定性地改变可学习性。Steinhardt 等（2016）表明，即使目标概念本身具有非常简洁的描述，限制学习者的内存也会显著增加所需数据量。他们指出奇偶函数（parity functions）是这种张力的一个典型例子。Raz（2018）后来通过证明：任何内存低于二次方的学习者都需要指数级样本才能从随机样例中学习奇偶函数，从而解决了这一猜想。

原文链接： https://arxiv.org/pdf/2601.03220