Transformer 天生简洁:一个表达力理论结果能说明什么、不能说明什么
新论文证明 transformer 表示某些语言时比时序逻辑、循环网络指数级简洁,比有限自动机双指数级简洁。这是一个关于规模的解释,不是一份工程指南。
概述
一篇被 ICLR 2026 接收、并在 Hacker News 收获 148 赞的论文《Transformers are inherently succinct》(Bergsträßer、Cotterell、Lin)提出了一个换角度看 transformer 的命题:不要只问 transformer 能识别哪些语言,而要问它表示这些语言时需要多大规模。作者用形式语言理论里一个经典而精确的概念,即简洁性(succinctness),给出答案:在表示某些语言族时,transformer 可以比线性时序逻辑(LTL)和循环神经网络(RNN)指数级地更简洁,比有限自动机双指数级地更简洁。
这是一个干净的理论结果,也是一个容易被误读的结果。它真正说明的是:存在一些复杂结构,transformer 用多项式大小就能表示,而其它形式系统要表示同样的东西就得膨胀到指数甚至双指数级。它没有说、也不打算说的是:在真实训练里 transformer 一定学得到这些结构、或者它在工程上一定更强。这篇论文对研究者有明确的方向价值,对建设者主要是远期含义;把”理论证明了简洁”等同于”实践中更强大”,是这类结果最常见的误读。
发生了什么
论文研究的不是工程意义上的 transformer,而是一个被广泛采用的理论抽象:唯一硬注意力 transformer(unique-hard attention transformer,UHAT)。在这个模型里,每个位置的注意力只挑选得分最高的那一个位置(并用一个固定的平局打破规则),再叠加仿射变换和 ReLU 层。作者特别强调它工作在固定精度(fixed precision)算术下,也就是每个数值只用常数个二进制位表示,这恰恰是最贴近真实硬件的设定,而不是理论上常见的”任意精度有理数”假设。这个选择让结论更接近现实,值得认可。
核心的衡量工具是简洁性。给定一个语言 L 和一类识别器 C(比如 transformer、有限自动机、LTL 公式),L 相对于 C 的简洁性,就是 C 里能识别 L 的最小那个识别器的规模。这是计算机科学里的老概念:它把”表达力”这个粗糙的问题(谁能识别谁不能)细化成”表达同一个东西要花多大代价”。一个经典先例是,LTL 和有限自动机表达力相同,但 LTL 可以指数级地比自动机更简洁,代价是 LTL 的判定问题相应地更难。这篇论文把 transformer 放进了同一张比较表。
论文在两个方向上都给出了收紧的结果。下界方面(定理 15、17、推论 18):存在一族语言,能被多项式大小的 UHAT 识别,但识别它们的最小 LTL 公式或最小 RNN 必然是指数级大,最小的有限自动机必然是双指数级大。上界方面(命题 16 等):反过来,任何 LTL 公式都能被至多多项式级别更大的 UHAT 表示,任何固定精度 UHAT 也能被翻译成至多指数级大的 LTL 公式,这一步还顺带改进了此前一个双指数级的翻译结果。两个方向合起来,才真正把规模差距”夹”住:在某些语言上,transformer 系统性地、可证明地更小,同时不会反过来吃亏。
让这一切成立的关键技术,是作者展示了 UHAT 如何用注意力机制编码出能从 0 数到双指数级的计数器。一个直观的例子:用一个二进制计数器去枚举所有满足某些相邻约束的字符串,字符串本身的长度就随计数器位数指数增长;再把多个这样的字符串”叠”起来加上纵向约束,最短的可接受字符串长度就能达到双指数级。正因为 transformer 能用很小的描述”展开”出如此庞大的结构,它在简洁性上才占了便宜。需要诚实指出:这些是为证明而精心构造的人造语言,不是自然语言或代码里常见的模式,论文也没有声称后者具备同样性质。
还有一个直接推论被作者明确写了出来(定理 4、定理 19):正因为 transformer 能把如此大的结构压进如此小的描述,分析它就相应地变难。具体说,判断一个给定 UHAT 识别的语言是否为空(非空性问题)、以及判断两个 UHAT 是否识别同一语言(等价性问题),都是 EXPSPACE-完全的。在标准的复杂度假设下,这意味着没有算法能在不到双指数的时间里解决它们。作为对照,同样的问题对确定性有限自动机是多项式时间可解的。简洁性不是免费的:压缩得越狠,把它拆开来验证就越贵。
最后一点要说清楚:这是一篇纯理论论文,没有任何实验。论文不报告训练、不报告基准、不测量真实模型。它的结论是数学定理,适用范围严格限定在 UHAT 这个抽象和固定精度设定之内。作者自己在结语里也承认,关于这类简洁 transformer 是否真的”可学习”(训练能不能找到它们),现有的经验证据是混合的、未有定论的。
为何重要
这篇论文的价值,在于它给一个长期被直觉解释的现象提供了形式化的支点:为什么 transformer 用相对不大的规模,就能表示看上去很复杂的结构?过去大多数表达力研究问的是”能不能”:transformer 能识别哪些语言、不能识别哪些。但”能不能”这个镜头有它的盲区:很多架构在表达力上其实等价(都对应到某类正则语言),却在实际表现上天差地别。简洁性提供了一个更细的镜头,问的是”要多大代价”,而这恰恰可能是更贴近实践差异的那个维度。把 transformer 第一次放进这张以代价计量的比较表里,本身就是一个有意义的贡献。
对理解架构之间的取舍,这给出了一个具体的、可证明的差异点。RNN 在表达力上其实比 transformer 更强(在固定精度下能识别全部正则语言),但这篇论文说明:在某些语言上,要达到同样的识别能力,RNN 的规模得比 transformer 大指数级。这把”transformer 强在哪”从一句模糊的直觉,变成了一个有方向、有量级的陈述。它不能解释 transformer 在实践中的全部优势(实践优势还来自并行训练、优化友好、数据规模等大量与表达力无关的因素),但它至少精确地刻画了其中一块。
同时,这个结果界定了能力的边界,而边界往往比能力本身更有用。简洁性带来的直接代价,就是那个 EXPSPACE-完全的验证难度。如果你希望对 transformer 做形式验证,证明它在所有输入上都不会做某件事,这个结果是一个坏消息:最坏情况下这件事可证明地极难。但它同时也指出了出路:难度来自 transformer 能编码巨大的计数器,所以反过来,如果能识别出那些无法编码这种计数器的 transformer 子类,就有希望得到可在更低复杂度内验证的子类。这是论文留给后续工作的一个明确方向,也是它真正可能影响工程的那条路径,但那是后续工作的事,不是这篇论文已经交付的东西。
对建设者的影响
务实地说,这篇论文今天不会改变你怎么训练模型、怎么选架构、怎么写 prompt。它没有提供任何可以直接落到工程上的方法、技巧或工具。如果你在构建产品,把它读作”背景知识”而非”行动项”是正确的态度。这不是贬低它,理论本来就不靠直接指导工程来体现价值,而是为了避免一种常见的误用:看到”transformer 被证明更简洁”就推断”所以我该更激进地用 transformer”。这个推断不成立,因为论文里那些占便宜的语言是人造构造,与真实任务没有建立起对应关系。
它在远期有两处可能与建设者相关。第一是形式验证。今天对前馈神经网络的验证工具已有相当进展(每年甚至有专门的验证竞赛),但对 transformer 的验证基本还做不到。这篇论文从复杂度上解释了为什么难,也指明了哪些 transformer 子类有可能变得可验证。如果你所在的领域对模型的安全性、可靠性有强保证需求(自动驾驶、医疗、金融风控),那么”哪些 transformer 结构是可验证的”这个问题,长期看与你有关,但能用的工具还不存在,这是研究议程,不是产品选项。
第二是关于规模的直觉校准。这个结果支持一个合理但需要小心使用的直觉:transformer 能用不大的参数规模表示相当复杂的结构。这或许有助于解释为什么中等规模的模型有时表现出超出其规模预期的能力。但请把它当作一个解释性框架,而不是一个可外推的定律:论文证明的是”存在这样的语言”,不是”你的任务就是这样的语言”。在没有把你的具体任务对应到论文的构造之前,任何”所以我的模型应该能用更少参数搞定”的推断,都是没有依据的。
该忽略什么
忽略任何把这个结果当成 transformer 工程优越性证明的解读。论文证明的是表示规模上的简洁性,这与”在真实任务上效果更好""更容易训练""更省算力”是三件不同的事,论文一件都没有声称。尤其要警惕一种链式误读:简洁 → 所以更强 → 所以应该多用 transformer。这条链的每一环都没有论文支撑。
忽略”简洁就一定划算”的暗示。论文自己把代价写得很清楚:简洁性的另一面是验证难度的爆炸(EXPSPACE-完全)。在需要可分析、可验证、可调试的场景里,更简洁反而可能是负担。简洁是一个中性的结构性事实,不是一个褒义的工程指标。
对 Hacker News 上的一类质疑,要分清哪部分成立、哪部分不成立。有评论指出,论文与 LTL 比较时用的是未经化简的表示,如果允许对 LTL 公式做充分化简(例如某些归约),那个指数级优势可能会缩水。这个直觉对”和 LTL 比”这一项有一定道理,值得保留警惕。但要注意,论文对自动机的双指数级下界用的是另一种论证:它依赖最短可接受字符串的长度,而这是一个不随表示方式改变的硬下界(任何识别非空语言的自动机,其规模至少与它能接受的某个字符串长度成线性关系)。所以”换个表示就能抹平差距”这个反驳,对自动机方向并不适用。读这类争论时,要落到具体是哪个定理、哪个对比对象,而不是笼统地接受或否定。
最后,忽略”这是纯理论所以与现实无关”的另一极端。它确实是纯理论、没有实验,适用范围严格限定在 UHAT 和固定精度内;但固定精度恰恰是最贴近真实硬件的设定,UHAT 也是被反复研究的主流抽象。它不直接指导工程,但它精确地解释了一个真实现象的一部分,并为可验证 AI 划出了一条具体的研究路线。对研究者,这是方向;对建设者,这是背景。两者都不该被夸大成另一个。
来源
无官方一手源；本文基于可靠二手报道（具名媒体、交叉印证）写成。