ICLR 2026 的两篇杰出论文奖（Outstanding Paper）里有一篇纯理论的工作，叫 Transformers are Inherently Succinct。一篇没有实验、没有 benchmark、全是数学证明的论文能拿最佳论文，评审委员会给的理由是"提出了一个新的视角来解释 Transformer 架构的强大能力"。原论文不太好读，涉及大量形式语言理论和复杂度理论的工具，这篇文章试图把核心结论和构造思路用更直觉的方式讲清楚。

这个"新视角"是什么？过去大家比的是表达力，即"谁能识别的语言范围更广"，这篇论文换了个角度：同样一个语言，谁用更少的篇幅就能描述清楚？

论文用一句话概括了自己的核心结论：

Transformers can describe concepts extremely succinctly.

Transformer 短得多。不是短一点，是短到夸张。同样的语言，有限自动机需要的描述大小可能是 Transformer 的双指数倍。如果 Transformer 用 10 个符号就能描述一个语言，有限自动机可能需要 2^(2^10)，大约 10^308 个状态才能表达同一件事。这个差距比宇宙中原子的数量大得多。

为什么这个问题重要

一个常见的理论结论是：Transformer 能识别的语言类型其实比 RNN 少。固定精度的 Transformer 只能处理一类叫 star-free 的正则语言，而同样是固定精度的 RNN 能处理所有正则语言。从"能力范围"看，RNN 严格强于 Transformer。但实践中 Transformer 全面碾压 RNN，这一直缺少好的理论解释。

以前的思路都是沿着"表达力"这条线走，试图在各种条件下证明 Transformer 能做这个能做那个。这篇论文说的是：也许我们一直在用错误的维度评价架构。表达力（能做什么）和简洁性（做同一件事需要多大的模型）是两个独立的维度。RNN 在第一个维度上赢了，Transformer 在第二个维度上赢得碾压级。

评审委员会看中的也是这一点。评语里提到"鲜明的概念性观点引起了评审委员会及其他专家的兴趣"，尽管论文"存在一些批评意见"。一篇纯理论论文能拿 Outstanding Paper，靠的是它提出的问题足够好。

什么叫"描述同一个语言"

先解释一下设定。在形式语言理论里，一个"语言"就是一组字符串的集合。比如"所有以 ab 结尾的字符串"是一个语言，“所有长度为偶数的字符串"也是一个语言。

描述同一个语言有很多种方式。你可以画一个有限自动机（一张状态转移图），可以写一个逻辑公式（LTL，线性时序逻辑），也可以用一个 Transformer。它们的能力范围可能不同，但在它们都能描述的那些语言里，谁用的"字数"更少？这就是简洁性（succinctness）要回答的问题。

论文研究的具体模型叫 UHAT（Unique Hard Attention Transformer），是理论上最简单的一种 Transformer：硬注意力、固定精度、确定性选择。用最弱的 Transformer 来证明简洁性，结论对更强的模型只会更好。

简洁性比较

论文的核心结果是一个三层的简洁性阶梯：

1
2
3
4
5
6
7
8
9

  Transformer (UHAT)
       |
       | 指数级差距
       v
  LTL 公式 / RNN
       |
       | 指数级差距
       v
  有限自动机

Transformer 到有限自动机是双指数，两个指数叠在一起。这些差距已经是最优的，不可能再缩小了。从 Transformer 翻译到 LTL 最多只有指数级膨胀（改进了之前工作的双指数级翻译），反过来从 LTL 翻译到 Transformer 只需要多项式大小。

RNN 的位置比较微妙。虽然 RNN 能识别更多语言，但在双方都能识别的 star-free 语言上，Transformer 比 RNN 指数级更简洁。原因倒也直接：固定精度的 RNN 说白了就是一个有限自动机，d 维状态向量每维 k bit，总共 2^(kd) 个可能状态。Transformer 到有限自动机的双指数 gap 自然推出了到 RNN 的指数 gap。

Attention 的直接寻址能力

有限自动机只能从左到右扫一遍字符串，每到一个位置只能看当前符号和自己的内部状态。如果你需要检查"当前位置的值跟前面某个特定位置的值是否匹配”，自动机就必须把那个值记在状态里。需要记住的信息量随输入长度指数增长时，状态数也跟着指数增长。

Attention 可以直接"跳"到满足某个条件的位置，把那里的信息取过来。不需要一步步走过去，也不需要把中间信息存在状态里。

论文的具体构造是让 Transformer 检查一个字符串里嵌入的二进制计数器是否在正确递增。字符串的每一段包含一个二进制数和一个符号，用 # 分隔：

1

000a#001b#010c#011a#100b#101c#110a#111b#

要验证计数器从 000 正确数到 111，attention 只需要对每个 # 位置找到前一个 #，然后逐位比较两个二进制数是否相差 1。一个 n 位的计数器有 2^n 个段，但检查它只需要多项式大小的 Transformer。有限自动机要做同样的事，必须记住当前计数器的值，需要 2^n 个状态。

论文把这个构造推到了极限。通过嵌套（把多个计数器串叠成行和列、用垂直约束连接不同行同一列的位置），一个多项式大小的 Transformer 能检查的模式复杂到最短的合法字符串是双指数长的。而有限自动机接受非空语言时，最短字符串不超过状态数量级。两边一比，双指数 gap 就出来了。

这个嵌套构造实际上编码了一个叫 2^n-tiling 的问题：给你一组带颜色边的方块，问能不能铺满一个 2^n 列、任意多行的网格，让相邻方块的颜色匹配。Attention 检查水平约束（找相邻的 #），也检查垂直约束（找同一列上一行的 #，通过要求计数器值完全匹配来定位）。这是一个 EXPSPACE 完全问题，能用多项式大小的 Transformer 编码。

简洁性与验证复杂度

描述越紧凑，分析越难。判断一个有限自动机能不能接受至少一个字符串？多项式时间搞定。LTL 公式？难一个量级。Transformer？EXPSPACE 完全，意思是解决这个问题所需的内存空间会随输入规模指数级增长，属于理论上最难的那一档问题。等价性判定（两个 Transformer 是否识别同一个语言）也是 EXPSPACE 完全。

跟文件压缩一个道理，压缩率越高解压越耗资源。Transformer 是一种压缩率极高的语言描述方式，代价是分析它变得极其困难。你只想回答"这个模型是不是什么都不接受"这种最基本的问题，理论上也逃不掉这个复杂度。

还有一个有趣的细分：如果限制 Transformer 只用单一方向的 attention（只看左边不看右边），复杂度会降低。EXPSPACE 完全性来自可以混合不同方向的 attention，这种灵活性带来了极高的压缩能力。

与实际 LLM 的距离

论文处理的是固定精度硬注意力 Transformer，跟实际 LLM 用的 softmax attention 加浮点精度有距离。最近有工作（Sälzer et al., 2026）表明非固定有限精度的 softmax Transformer 验证甚至是不可判定的，这暗示 softmax 版本的简洁性可能更极端，但目前没有严格的对应结果。

从 worst-case 的简洁性到实际训练中的参数效率，中间还隔着优化和泛化两道关。论文给出的是表示论层面的结构性优势，不能直接等同于"Transformer 训练更好"。但它至少说清楚了一件事：在所有能表达 star-free 语言的模型里，Transformer 是最省字数的那个。纯数学陈述，不依赖任何实验假设。

论文最后提到一个语言学上的类比：根据 Zipf 的缩略定律，高频使用的概念倾向于获得更简洁的描述。阿拉伯数字系统比罗马数字系统指数级更简洁，而正是这种简洁性可能使得现代数学和计算机科学成为可能。Transformer 的简洁性是不是也在某种意义上使得 LLM 成为可能？目前没有答案。