Language Modeling is Monotone Compression
作者: Noam Mazor, Andrew Morgan, Rafael Pass
分类: cs.IT, cs.AI, cs.CR
发布日期: 2026-10-08
备注: 22 pages, 1 figure. Submitted to ICLR 2027
💡 一句话要点
提出语言建模作为单调压缩以探讨智能与压缩的关系
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 语言模型 单调压缩 信息压缩 密码学 智能 伪熵 机器学习
📋 核心要点
- 现有研究表明，智能与信息压缩能力密切相关，但缺乏理论支持来验证这一假设。
- 本文提出将语言模型视为单调压缩算法，建立了二者之间的等价关系，提供了理论基础。
- 研究结果显示，单调性是等价关系成立的必要条件，并引入了新的密码学概念，具有独立的研究价值。
📝 摘要（中文）
本文探讨了人工智能与压缩之间的关系，提出语言模型（LLMs）可以被视为单调压缩算法。研究表明，LLMs作为下一标记预测器，与单调压缩算法等价，且这种等价性依赖于密码学单向函数的存在。此外，研究还揭示了下一位伪熵与分布的单调不可压缩性之间的等价关系，为密码学提供了新的见解。
🔬 方法详解
问题定义：本文旨在探讨语言模型与压缩算法之间的关系，现有方法未能充分理论化这一联系，导致对智能与压缩的理解不足。
核心思路：论文提出将语言模型视为单调压缩算法，证明二者在保持相同误差的情况下可以相互构造，从而建立理论联系。
技术框架：研究首先定义了语言模型作为下一标记预测器，然后分析了单调压缩算法的性质，最后通过构造性证明展示了二者的等价性。
关键创新：最重要的创新在于将语言模型与单调压缩算法等价化，揭示了智能与信息压缩之间的深层联系，且该等价性依赖于密码学单向函数的存在。
关键设计：论文中定义了单调压缩的编码过程，确保输入顺序的保持，并探讨了下一位伪熵的概念，提供了新的视角来理解信息分布的不可压缩性。
🖼️ 关键图片
📊 实验亮点
实验结果表明，语言模型在压缩能力上表现出色，其性能与知识和推理基准高度相关。此外，研究还首次将下一位伪熵与单调不可压缩性建立了联系，拓展了密码学的研究视野。
🎯 应用场景
该研究的潜在应用领域包括自然语言处理、信息压缩技术以及密码学。通过深入理解语言模型的压缩能力，可以提升模型在知识推理和决策支持系统中的表现，推动智能系统的发展。
📄 摘要（原文）
A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM'24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms---namely, compression algorithms where the encoding process preserves the ordering of the inputs---in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS'23) that incompressibility implies next-bit pseudoentropy.)