Transformer最大的天赋，也许从来不是会计算，而是特别会压缩。 Transformer能把复杂世界塞进了更小的盒子！双指数级简洁性是怎样炼成的？
Transformer隐藏实力曝光：压缩能力远超RNN和有限状态机！ICLR 2026重磅论文：Transformer真正强大的原因找到了
这篇论文发现了一件挺反直觉的事情。很多人都觉得Transformer厉害是因为它能处理很复杂的任务，能记住很长的上下文。
但作者换了个角度，问了一个更刁钻的问题：同样描述一种语言规则，谁用的描述长度最短？结果Transformer赢了，而且赢得非常夸张。
有些语言用Transformer描述只需要很小一段，但换成LTL逻辑公式就要膨胀到指数级，换成有限自动机更是要膨胀到双指数级。这就好比有人能用一张便签纸写下《战争与和平》的完整情节，而别人得用一整面墙才能写完。而RNN输在了表达效率而不是表达能力！
但是，验证Transformer为什么比登月还难！
表达能力不是唯一标准
以前大家比模型，最喜欢比谁能做的事情更多。比如有人说Transformer能处理多长的序列，有人说RNN理论上能识别所有正则语言。这就像两个人在比谁的卡车能拉更重的货。
但作者觉得这个比较方式漏掉了一件重要的事。两辆卡车都能拉十吨货，但一辆卡车自己就能装下，另一辆得挂上十节拖车才能装下。这时候你肯定觉得前面那辆更厉害。
论文里把这种能力叫做“简洁性”。简单说，就是描述同样一种规则，谁用的描述长度更短。这跟表达能力是两回事。表达能力问的是“能不能做到”，简洁性问的是“做得多省事”。
Transformer在简洁性这张卷子上拿了高分。作者证明了存在一批特殊语言，用Transformer描述只需要多项式大小，但换成LTL公式就要指数大小，换成有限自动机就要双指数大小。
你可以想象一下。假设Transformer模型大小是100。那么对应的LTL公式可能需要100万。对应的有限自动机可能直接是个天文数字。
这就是论文标题“Transformers Are Inherently Succinct”的意思。Transformer天生就擅长压缩。
注意力机制偷偷造了个超级计数器
Transformer为什么能这么省空间？作者找到了一个关键原因。
Attention机制不仅能用来找重点，还能用来做计数。而且不是普通的一二三四那种计数，是那种大到离谱的计数。
论文里构造了一个例子。Transformer可以利用Attention模拟一个规模达到2^(2^N)级别的计数器。
这个数字有多大？N等于4的时候，2^(2^4)等于65536。N等于5的时候，2^(2^5)等于四十多亿。N等于6的时候，这个数字已经比地球上所有沙子的总数还多。
关键是Transformer并没有真的存储这么多状态。它用了Attention的特殊性质。每次需要知道当前数到多少的时候，它不是从记忆中读取，而是通过Attention去“看”之前的位置，然后根据那些位置的信息算出当前值。
这就像一个魔术师。你看着他手里只有几张牌，但他能变出整副扑克牌的效果。Attention就是这个魔术师的手。
作者把这个发现用在了语言识别上。他们构造了一些语言，这些语言的最短合法字符串长度是双指数级的。也就是说，如果你想判断一个字符串是不是符合规则，你得先数到一个极其巨大的数字。
有限自动机遇到这种语言就直接崩溃了。因为自动机的状态数量是固定的。你想让它数到双指数级，它就需要双指数级那么多个状态。这就像让一个只有十个格子的计数器去数到一百万，根本不可能。
但Transformer可以。它不需要把计数器里的每一位都显式存下来。它把计数过程编码进了Attention结构里。所以它可以用很小的模型处理极其巨大的计数范围。
RNN看起来更强但输在了体积上
这里有个特别有意思的反转。
以前很多理论研究已经证明了，在固定精度条件下，RNN能识别的语言比Transformer更多。RNN可以覆盖全部正则语言，而Transformer只能覆盖其中一部分。
如果只看表达能力，RNN好像赢了。
但作者指出，现实世界不是这么算账的。表达能力是一回事，表达效率是另一回事。
一个人能背下整本百科全书当然厉害。另一个人能把整本百科全书压缩成一个U盘。在很多实际场景里，后面这个人反而更有用。
论文证明了Transformer相对于RNN存在指数级的简洁性优势。也就是说，同样一个语言，Transformer可能只需要很小的模型就能识别，而RNN需要大得多的模型。
原因跟前面的计数器有关。RNN虽然原则上也能实现大范围计数，但它需要把计数器的状态存在隐藏状态里。固定精度条件下，隐藏状态的表示范围是有限的。你想计更大的数，就得扩大隐藏状态的维度。
Transformer不走这条路。它不把计数器的值存在某个固定位置，而是通过Attention动态地去“查阅”之前的信息。所以它用同样大小的模型，能处理的计数范围比RNN大得多。
这就好比两个人都在搬家。一个人每次只能搬一个箱子，但箱子很大。另一个人能同时看到所有箱子的位置，然后设计一条最短路线一次性搬完。虽然两个人的力气差不多，但后面那个人搬得快得多。
作者还顺便提了一句状态空间模型。因为状态空间模型本质上跟RNN是一类东西，所以Transformer对它们也有类似的简洁性优势。
压缩得越狠验证就越难
当一种表示方式特别紧凑的时候，往往会带来一个副作用。压缩包越小，解压越费劲。
论文里用了一个很直接的例子。Transformer能识别的那批超紧凑语言，你想验证它到底认不认识某个字符串，或者你想判断两个Transformer是不是完全一样，这些问题都极其难算。
作者研究了两个经典问题。
第一个是空语言问题。给你一个Transformer，你要判断它是不是不接受任何字符串。也就是说，它的语言是不是空的。
第二个是等价性问题。给你两个Transformer，你要判断它们识别的是不是同一种语言。
结果发现，这两个问题都达到了EXPSPACE完全级别。
EXPSPACE是什么概念？简单说就是难到爆炸。难到理论计算机科学家看到都会皱眉头。
对比一下就知道差距有多大了。同样的问题，如果换成有限自动机，甚至可以用多项式时间解决。也就是几分钟或者几小时的事情。
但换成Transformer，你需要的计算资源是天文数字。指数级空间已经够吓人了，EXPSPACE是指数级空间的指数级。这就像比谁更远。别人说我家到公司走十分钟。你说我家到公司得坐火箭飞一辈子。
作者不是随便说说，他们真的证明了这两个问题的下界。也就是说，不存在什么神奇的算法能绕过这个难度。除非你想出来的算法能解决理论计算机科学里几十年没解决的问题。
这也解释了为什么现在验证Transformer这么难。不是因为大家写的代码不够优化，而是问题本身就有这么难。
比前人结果翻了一倍
作者在论文里还做了一件挺狠的事。他们把自己的结果跟以前的研究做了对比。
之前已经有人证明过，Transformer比有限自动机更紧凑。但那个结果是指数级的。也就是说，有些语言用Transformer描述只需要多项式大小，用自动机需要指数大小。
作者把这个结果往前推了一大步。他们证明的是双指数级。
双指数和单指数的区别有多大？你可以这样想。指数是说，如果你原来有n，那么对方需要2^n。双指数是说，如果你原来有n，那么对方需要2^(2^n)。
当n等于4的时候，2^(2^4)等于65536。当n等于5的时候，2^(2^5)等于四十多亿。当n等于6的时候，这个数字比可观测宇宙里的原子总数还多。
作者还改进了另一个结果。之前有人做过从Transformer到LTL逻辑公式的转换，那个转换需要双指数级的代价。也就是说，转换出来的公式会变得巨大无比。
作者把这个转换压缩到了单指数级。虽然还是很巨大，但已经从“不可能”变成了“勉强能忍”。
这就像原来翻越两座珠穆朗玛峰才能到的地方，现在只需要翻越一座。虽然还是很累，但至少有人能做到了。
这两个改进加在一起，让整个结论变得非常有说服力。Transformer的简洁性不是一点点，而是压倒性的。
行李箱里装了整个世界
看到这里，你应该已经明白了作者想说什么。
Transformer的真正优势，可能不是它能处理多长的序列，也不是它能模拟多复杂的函数。而是它能用非常小的代价，描述出非常复杂的规则。
这就像收拾行李。普通人出门带一个箱子，能装下几件衣服和一双鞋。收纳大师出门也带一个箱子，但能装下整个衣柜外加洗漱包和笔记本电脑。
Transformer就是那个收纳大师。别人用一百个状态才能记住的东西，它用十个状态就能记住。别人用一万行公式才能描述的语言，它用一百行就能描述。
这种能力不是天上掉下来的。作者证明了，Attention机制在其中起了关键作用。Attention让模型可以在不同位置之间建立联系，而不需要把所有的信息都塞进同一个状态里。
这就像你不需要记住每一个朋友的电话号码。你只需要记住通讯录在哪里，然后需要的时候去查就行了。Transformer也是这么干的。它不需要记住计数器的每一位，它只需要知道去哪里查。
当然，这种简洁性也有代价。你想打开那个收纳大师的行李箱，想搞清楚里面到底装了什么，你会发现拉链打不开，密码你不知道，甚至你可能得花一辈子才能理清楚。
这就是验证Transformer为什么这么难的原因。箱子越小，锁越复杂。
论文最后提了一句，这个问题短期内可能没有完美的解决方案。但至少现在我们知道问题出在哪了。不是算法不够好，是问题本来就难。
这就像医生告诉你，你这个病很难治。但至少你知道难在哪，总比不知道强。
总结
Transformer虽然在“能表达什么语言”这件事上未必比RNN更强，但在“用多小的模型表达同样复杂的语言”这件事上非常夸张。论文证明，固定精度Transformer相对于LTL和RNN具有指数级简洁性优势，相对于有限自动机甚至具有双指数级简洁性优势，同时其验证问题达到EXPSPACE完全级别。
论文信息
- 作者: Pascal Bergsträßer, Ryan Cotterell, Anthony W. Lin
- 机构: RPTU Kaiserslautern-Landau, ETH Zürich, MPI-SWS
- 会议: ICLR 2026
- 核心贡献: 证明UHAT相对LTL和RNN指数级更简洁，相对有限自动机双指数级更简洁；非空问题EXPSPACE完全