0｜基本信息（Metadata）

  • 标题（Title，中英文）：From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence / 《从熵到 Epiplexity：有限计算下的信息新度量》
  • 作者（Authors）：Marc Finzi*（CMU）、Shikai Qiu*（NYU）、Yiding Jiang*（CMU）、Pavel Izmailov（NYU）、J. Zico Kolter（CMU）、Andrew Gordon Wilson（NYU）。四位共同一作，Finzi 专攻贝叶斯优化与信息论，Qiu 研究神经网络压缩与泛化，Jiang 研究数据选择与 pretraining 策略。通讯作者 Wilson 是 NYU 教授，以 scaling law 和贝叶斯深度学习闻名。
  • 期刊 / 会议（Venue）：arXiv 预印本，2026 年 1 月提交，3 月更新。
  • 发表时间（Year）：2026

1｜核心结论（Core Takeaway）

这篇论文提出了 epiplexity（epistemic complexity）——一种基于有限计算观察者的信息度量，用以量化数据中可学习的结构性信息，并将其与不可预测的随机信息（time-bounded entropy）分离。作者指出香农信息论和柯尔莫哥洛夫复杂性在解释现代机器学习实践时存在三个”悖论”，而 epiplexity 提供了统一的理论框架来解决这些冲突。这项工作的重要性在于：它为数据选择而非模型选择提供了理论基础，解释为什么某些数据（如文本）比另一些（如图像/视频）能产生更好的 OOD 泛化，以及为什么合成数据、数据排序、课程学习这些看似”违反信息论”的做法在实践中有效。

2｜研究问题与背景（Problem & Context）

现代机器学习面临一个根本性困境：经典信息论似乎与直觉和经验相矛盾。

  • Shannon 的数据处理不等式（DPI）说确定性变换不能增加信息→但 AlphaZero 从零数据中学会下棋、合成数据确实提升了模型能力
  • 信息对称性说因子分解顺序不影响总信息量→但 LLM 按左到右建模远好于反向排序
  • 似然最大化被认为只是分布匹配→但模型从数据中学到了生成过程中并不存在的归纳结构（如从谋杀小说中推断凶手）

这些”悖论”的核心原因：香农理论和柯尔莫哥洛夫复杂性都假设观察者具有无限计算能力。 当把计算约束加入信息定义，这些矛盾自然消失。

3｜方法主线（Approach）

论文通过三条线构建理论框架：

  1. 三个悖论的识别与形式化：罗列每个悖论在经典信息论中的数学表述，以及它们在 ML 实践中”被违反”的现象
  2. Epiplexity 的数学定义：基于时间受限的 MDL（Minimum Description Length），将数据的总信息分解为
    • Time-bounded Entropy ( H_T(X) )：随机、不可预测的部分
    • Epiplexity ( S_T(X) )：结构性、可学习的部分
    • 二者之和为总时间受限信息 MDL_T(X)
  3. 实用估计方法：通过 prequential coding（训练曲线下面积）和 requential coding（教师-学生 KL 散度）近似计算 epiplexity，用神经网络作为受约束的程序类

4｜创新贡献（Novel Contribution）

创新类型：理论创新（Theoretical）

创新幅度：高

具体而言：

  • 统一了之前零散的概念：将 cryptography 中的 pseudoentropy、algorithmic statistics 中的 sophistication、ML 中 loss curve AUC 的思想统一到一个框架中
  • 以”计算”为核心的信息论：与 Klir 的 V-entropy 和 Barak 的 pseudoentropy 不同，epiplexity 将训练和推理的计算开销统一纳入时间预算，更贴近 ML 实际
  • 形式化了 emergence：给出了基于 epiplexity 涌现定义（Definition 14），量化了”简单规则→复杂行为”的信息代价
  • 提出了”数据选择”而非”模型选择”框架：MDL 是模型选择准则，epiplexity 是它的对偶——在固定计算预算下进行数据选择

5｜关键点（Key Points）

  1. PRG 创造了大量的 time-bounded entropy，但几乎无 epiplexity：一个 CSPRNG 输出的香农熵 = k，柯尔莫哥洛夫复杂度 ≤ k + O(1)，但在多项式时间观察者眼中 time-bounded entropy ≈ n（满），epiplexity ≈ O(1)。这完美匹配直觉：伪随机数”看起来很像随机数，但没什么可学的”

  2. 确定性变换可以创造信息（Paradox 1 的解决）：Theorem 12 证明在有限计算下，PRG 等确定性函数可以大幅增加 time-bounded information。关键是非对称性：正向变换和逆变换的计算代价差异在有限计算下不可忽略

  3. 因子分解顺序影响可学得的信息（Paradox 2）：Chess 数据实验显示，(move sequence → board state) vs (board state → move sequence) 两种排序产生不同的 epiplexity。反向排序迫使模型学习更丰富的棋盘表征，提升了 OOD 泛化

  4. 归纳（induction）作为 epiplexity 的来源（Paradox 3）：模型为了计算似然，需要学会推理缺失信息（hidden bits），这比生成过程本身更复杂。在”induction easy”实验中，llm 学会了 in-context 推断 Markov chain 的缺失行——这个策略在数据生成过程中根本不存在

  5. 文本具有最高的 epiplexity，图像最低：在 1T token 量级用 scaling law 估算，文本数据的 epiplexity 远高于图像和视频。VQ tokenization 显著提升了图像的 epiplexity（去除像素级随机性，保留高层语义结构）

6｜关键数学 / 统计方法（Quantitative Tools）

  1. Prequential Coding（前序编码）：将训练过程本身视为一个编码方案——每一步用当前模型编码当前 token，模型描述长度 ≈ 损失曲线下面积减最终损失。直观但非严格的估计方法

  2. Requential Coding（谐振编码）：用 KL 散度严格构造模型编码。学生模型在教师模型生成的合成数据上训练，编码长度为累积 KL(P_t ∥ P_s)。更准确但 2-10 倍更慢

  3. Scaling Law 外推：基于 Chinchilla law ( L(N, D) = E + (N/N_0)^{-α} + (D/D_0)^{-β} )，可以利用损失曲线的形状参数估计大规模数据集的 asymptotic epiplexity

7｜结果与证据强度（Results & Evidence Strength）

证据强度：中-强

论文提供了充分的实验支撑其理论主张：

  • ECA 实验：3 类规则（II/III/IV）明确展示了 epiplexity 如何区分”简单”、”随机”、”复杂”三种生成过程（Figure 3）——强证据
  • Chess 数据排序：反向排序 ↑ epiplexity → ↑ centipawn evaluation OOD 性能（Figure 7）——直接验证 of epiplexity → OOD 泛化
  • Induction 实验：Rule 30 hidden bits 和 Markov chain 隐藏行——证明了”归纳可以产生额外 epiplexity”（Figure 5）——强证据
  • Emergence 实验：非循环 transformer vs 循环 transformer 在 ECA rule 54 上的对比——展示了计算受限时模型会学到涌现结构（Figure 6）——有说服力的概念验证
  • Natural data 测量：文本 > 棋谱 > 图像 CIFAR 的 epiplexity 排序匹配了实践经验——一致性证据

主要局限：大部分实验使用小型 transformer（~160M 参数），requential coding 的计算开销限制了规模。

8｜局限与注意点（Limitations）

  1. OWF 假设的脆弱性：论文的许多理论结果（如高 epiplexity 的存在性、熵不对称性的证明）依赖于 one-way function 的存在。虽然这是密码学的标准假设，但它尚未被证明
  2. 估计方法的近似性：prequential coding 提供了方便但理论上有漏洞的估计（不保证运行时间约束），requential coding 虽严格但慢 2-10 倍。在实践中使用时需注意两种方法可能给出不同的排序
  3. epiplexity ≠ OOD 泛化的保证：作者明确承认，epiplexity 测量的是”多少结构信息”而非”这些结构是否对特定下游任务有用”。高 epiplexity 数据也可能学到无关结构
  4. 实验规模偏小：最大实验到 160M 参数 / 5B token，离现代 LLM 规模差 1000 倍。Scaling law 外推部分依赖文献数据而非直接验证

9｜可迁移价值（Transferable Value）

  1. 数据选择的新指标：epiplexity 提供了一种无需下游评估即可比较数据质量的方法。对于 pretraining data curation 团队，可以用 prequential coding 快速评估不同来源数据的结构性信息含量
  2. 合成数据生成的理论指南：Theorem 12 的启示——”如果要通过确定性变换创造有用的结构性信息，确保变换的逆不是简单高效的”。这为设计合成数据 pipeline 提供了数学约束
  3. 课程学习的理论基础：为什么数据排序会影响最终模型能力？因为不同的 factorization 产生不同的 epiplexity。这为 curriculum learning 提供了一种新的设计原则：按 epiplexity 递增排列数据

10｜一句话总结（One-line Summary）

香农信息论说确定性变换不能创造信息，但 AlphaZero 和合成数据的成功告诉我们——在计算有限的世界里，计算本身就是信息的生产力，而 epiplexity 度量了这种生产力的产出。