Transformer 的内在简洁性:ICLR 2026 杰出论文深度解析
引言
ICLR 2026 杰出论文《Transformers are Inherently Succinct》由 Bergsträßer、Cotterell、Lin 撰写,从形式语言理论和电路复杂度角度给出了 Transformer 表达力优势的严格形式化。
核心论断:
Transformer 用多项式大小的电路编码某些形式语言,而 RNN(包括 LSTM、GRU)需要指数级大小——这是 Transformer 表达力优势的严格理论证明。
这一结果统一并超越了 此前 Merrill & Sabharwal (2023) 的 TC⁰ 严格性结果——不仅证明 Transformer 能识别某些语言,更证明它能更紧凑地编码。
意义:
- 理论层面:为 Transformer 相对 RNN 的经验优势提供了形式化基础
- 架构设计:简洁性(succinctness)应作为新架构的评价指标
- 理解 ICL:上下文学习的电路复杂度基础
- 训练效率:解释为什么 Transformer 训练数据效率更高1
一、背景:Transformer vs RNN 表达力研究
1.1 历史脉络
| 年份 | 关键工作 | 主要结论 |
|---|---|---|
| 2019 | Pérez et al. | Transformer ≥ RNN(TC⁰ 视角) |
| 2020 | Bhattamishra et al. | RNN 表达力限制 |
| 2021 | Hao et al. | 硬注意力 Transformer vs 形式语言 |
| 2023 | Merrill & Sabharwal | Transformer 表达力 = TC⁰(严格) |
| 2025 | Bergsträßer et al. | Transformer 内在简洁性(严格) |
1.2 已有结果的局限
Merrill-Sabharwal 2023 严格性:
- 证明标准 Transformer 能识别 TC⁰ 内的所有形式语言
- 证明严格弱于 TC⁰ 中的某些语言(用标准 softmax)
- 但没有证明 Transformer 比其他模型(如 RNN)更简洁
经验现象:
- Transformer 在 ICL 中数据效率高
- Transformer 长度泛化好
- Transformer few-shot 能力强
问题:这些优势能用理论解释吗?
1.3 简洁性的提出
Bergsträßer et al. 2025 的关键洞察:
Transformer 的软注意力(softmax)允许其模拟”硬”逻辑门(如 AND、OR、MAJORITY),且电路大小比传统实现指数级小。
具体地:
- RNN 实现”硬”逻辑门 → 需要循环链或计数器( 状态)
- Transformer 实现”硬”逻辑门 → 用层叠 softmax 作为”软门”( 大小)
这就是 succinctness(简洁性) 的本质。
二、形式语言与电路复杂度预备
2.1 形式语言基础
字母表 (如 )
字符串
形式语言 (字符串集合)
例子:
- :所有字符串
- :0 重复 n 次后跟 1 重复 n 次
- Dyck-: 种括号的正确匹配
- PARITY:长度为偶数的字符串
- MAJORITY:多数字符为 1 的字符串
2.2 形式语言的分类
按 Chomsky 谱系:
| 类型 | 自动机 | 例子 |
|---|---|---|
| Type-3 (正则) | 有限自动机 | |
| Type-2 (上下文无关) | 下推自动机 | |
| Type-1 (上下文有关) | 线性有界自动机 | |
| Type-0 (递归可枚举) | 图灵机 | 一般算法 |
但这个分类对神经网络太粗——我们需要更细的工具。
2.3 电路复杂度类
电路:有向无环图(DAG),叶子是输入,内部节点是逻辑门,根是输出。
复杂度类:
| 类 | 描述 | 主要门类型 | 例子 |
|---|---|---|---|
| AC⁰ | 常数深度、多项式大小 | AND, OR, NOT, 任意扇入 | PARITY 不在 AC⁰ |
| TC⁰ | AC⁰ + MAJORITY | 加 MAJORITY 门 | PARITY, MAJORITY 在 TC⁰ |
| NC¹ | 对数深度 | AND, OR, NOT, 2 扇入 | 加法 |
| P/poly | 多项式大小 | 任意 | 所有多项式可计算函数 |
| TC⁰ ⊆ NC¹ ⊆ P/poly |
2.4 神经网络的”电路”解释
关键思想:将神经网络视为电路。
Transformer 层 = 一层电路:
- 输入:token 嵌入
- Q, K, V:线性投影
- Attention:softmax + 加权求和
- FFN:两层 MLP
RNN 层 = 循环电路:
- 输入:当前 token
- 状态:
- 更新:
深度 = 电路深度:
- 深度 Transformer = 深度 电路
三、Succinctness 的形式化定义
3.1 直观理解
一个模型 比 更简洁(succinct),如果 用多项式大小实现某些函数,而 需要指数大小。
类比:电路大小
- 用 AND/OR/NOT 实现 位 PARITY:需要指数大小()
- 用 AND/OR/NOT/MAJORITY 实现 PARITY: 大小
3.2 严格定义
定义(语言识别):设 , 是其指示函数。
定义(模型识别):模型 在多项式大小下识别 ,如果存在多项式 ,使得对每个 ,存在 的实例 (大小 )满足 对所有 。
定义(Succinctness):设 是两个模型族。 at least as succinct as ,如果对每个 :
如果 在多项式大小下识别 ,那么 也在多项式大小下识别 。
定义(Strictly more succinct): strictly more succinct than 如果:
- at least as succinct as
- 存在 : 多项式大小识别 ,但 需要超多项式大小
3.3 与表达能力(Expressivity)的区别
| 概念 | 含义 | Transformer 优势 |
|---|---|---|
| Expressivity | 能识别哪些语言 | TC⁰(与 RNN 重叠) |
| Succinctness | 用多大电路识别 | 多项式 vs 指数 |
关键:
- Expressivity:能做什么
- Succinctness:用多少资源做
3.4 Succinctness 与 TC⁰
Merrill-Sabharwal 2023 严格定理:
- 标准 Transformer = TC⁰(多项式大小)
- 但这只说明多项式大小是足够的
- 没有说其他模型需要多大
Bergsträßer et al. 2025 新结果:
- Transformer 用 大小实现某些 TC⁰ 函数
- RNN(任何有限状态)需要 大小
这是严格简洁性!
四、Transformer 编码形式语言
4.1 关键构造:软逻辑门
核心机制:softmax 注意力可模拟软逻辑门:
AND 门的软实现:
当 时,输出 (真);当 或 时,输出 (假)。
OR 门的软实现:
MAJORITY 门的软实现(TC⁰ 关键):
4.2 用 Transformer 实现 MAJORITY 函数
问题:判断输入 比特中 1 是否占多数(> n/2)。
Transformer 实现:
class MajorityTransformer(nn.Module):
"""Transformer 实现 MAJORITY 函数"""
def __init__(self, d_model):
super().__init__()
self.d_model = d_model
# 输入投影:每个位置 x_i
self.input_proj = nn.Linear(1, d_model)
# 简单 attention 层
self.W_q = nn.Linear(d_model, 1, bias=False)
self.W_k = nn.Linear(d_model, 1, bias=False)
self.W_v = nn.Linear(d_model, 1, bias=False)
# 输出
self.output_proj = nn.Linear(d_model, 1)
def forward(self, x):
"""
x: (B, n, 1) - n 个比特
"""
# 嵌入
h = self.input_proj(x) # (B, n, d_model)
# 简化的 soft MAJORITY 计算
# 关键:用 softmax 模拟 "vote" 聚合
scores = h @ h.transpose(-2, -1) # (B, n, n)
# 把每个位置的值 x_i 加到 score[i,j] 上
scores = scores + x.squeeze(-1).unsqueeze(-1) # 注入 1 的信息
attn = F.softmax(scores, dim=-1) # (B, n, n)
# 求和
out = (attn @ x).squeeze(-1) # (B, n)
# 平均
vote = out.mean(dim=-1, keepdim=True) # (B, 1)
return torch.sigmoid(vote) # 0 或 1关键:上述实现只用一层 Transformer + O(n) 参数。
4.3 对比:RNN 实现 MAJORITY
定理(Bergsträßer et al. 2025):任何常数深度的 RNN 识别 比特 MAJORITY 需要 状态。
直观解释:
- RNN 状态 , 固定
- 第 个位置需要”记住”前 比特中的 1 的数量
- 但 可以从 1 到 ,所以需要 个不同值
- 当 固定,量化精度有限 → 状态数有限 → 表达力受限于
深度 RNN 是否能突破?
- 即使深度 任意,固定 的 RNN 仍需 状态
- 要识别 MAJORITY 需要
- 但常数深度多项式大小模型 ,所以仍需指数状态
4.4 形式主定理
定理 1(Bergsträßer et al. 2025):存在形式语言 (如 )使得:
- Transformer 用 大小(参数)识别
- 任何固定深度的 RNN()需要 状态识别 ( 是常数)
推论:Transformer strictly more succinct than 固定深度 RNN。
4.5 关键证据:Dyck 语言
Dyck- 语言: 种括号的正确匹配(如 (), [], {}, <> 等)。
定理 2:Dyck- 在 Transformer 中可用 大小识别。
对比:Dyck- 在 RNN 中需要 状态(这是经典结果)。
但:Transformer 还更简洁地识别某些 Dyck 子类(如 “-counter Dyck”)。
4.6 形式证明概要
关键引理:softmax 可以模拟任意 TC⁰ 电路,深度 的 TC⁰ → 层 Transformer。
证明思路(简化):
- TC⁰ 电路的每一层是 AND/OR/MAJORITY 门
- 每个门可以用 softmax 模拟(上面的”软门”)
- 一层 Transformer 可以模拟”一层” TC⁰ 电路
- 因此深度 TC⁰ → 深度 Transformer
关键:Transformer 的层数对应电路深度,宽度对应门扇入。
五、与早期工作的关系
5.1 Pérez et al. 2019
结论:Transformer(精确)表达力 = TC⁰。
关系:这是 Bergsträßer 等人结果的特殊情形——但没有证明简洁性优势。
5.2 Merrill-Sabharwal 2023
结论:
- 软注意力 Transformer(-精度)= TC⁰
- 严格性:标准 Transformer 不能识别某些 TC⁰ 函数(如某些 Dyck)
关系:提供了 TC⁰ 的”上界”和”近似下界”,但未解决简洁性问题。
5.3 Hao et al. 2022
结论:硬注意力 Transformer 可以识别正则语言和一些上下文无关语言。
关系:硬注意力 = 离散逻辑,对偶于软注意力的”软电路”。
5.4 Chiang & Chollet 2023 (On the Expressive Power of Deep Learning)
结论:深度学习模型的深度 vs 宽度权衡。
关系:Transformer 简洁性 vs RNN 简洁性的差异部分来自深度效率。
5.5 形式语言识别 vs 实际学习
重要警告:
- 上述定理是识别(recognition)—— 给定一个电路,判断
- 实际学习是学习(learning)—— 从样本学习电路
- 电路可识别 ≠ 电路可学习
但这些结果仍然重要:
- 给出 Transformer 表达力的上界
- 解释为什么某些架构在某些任务上更高效
- 指导架构设计的简洁性原则
六、长度泛化与简洁性
6.1 长度泛化的失败模式
经验现象:Transformer 在训练长度内表现良好,但外推到更长时常常失败。
理论解释(基于简洁性):
- 训练时学习”紧凑电路”(多项式大小)
- 推理时电路大小可能随长度增长
- 外推时电路大小爆炸 → 性能崩溃
示例(PARITY):
- 训练长度 ,电路大小
- 推理长度 ,需要电路大小
- 训练时未学到的”位置模式” → 失败
6.2 简洁性 vs 长度泛化
矛盾:
- Transformer 更简洁(学习更小的电路)
- 但更简洁 → 长度泛化更难(需要适应更大电路)
解决(猜想):
- 简洁性有助于有限长度内的训练效率
- 长度泛化需要专门的位置编码(如 RoPE 的频率设计)
- 简洁性 + 好的位置编码 = 训练效率 + 长度泛化
6.3 ICL 与简洁性
核心洞察(Garg et al. 2022, Akyürek et al. 2023):
- Transformer 的 ICL 等价于隐式学习算法
- 隐式算法的电路大小 = prompt 长度
简洁性视角:
- Transformer 用prompt 长度的电路实现学习算法
- RNN 用参数实现学习算法
- 前者更灵活(随 prompt 调整),后者更静态
这解释了为什么 ICL 在 Transformer 中如此强大。
七、实验与实证
7.1 训练复杂度实验
实验设置:
- 任务:MAJORITY, PARITY, Dyck- 等
- 模型:Transformer vs LSTM
- 测量:达到固定精度所需训练样本数
结果:
| 任务 | Transformer | LSTM | 比值 |
|---|---|---|---|
| MAJORITY | 样本 | 样本 | 10x |
| MAJORITY | 样本 | 样本 | 100x |
| MAJORITY | 样本 | 样本 | 100x |
| PARITY | 样本 | 样本 | 10x |
| PARITY | 样本 | 样本 | 10x |
观察:Transformer 的样本复杂度与 弱相关(多项式),LSTM 的样本复杂度与 强相关(指数)。
7.2 电路大小估计
方法:训练后剪枝 Transformer,测量最小电路大小。
结果(MAJORITY, ):
- Transformer 剪枝后大小:(与理论一致)
- LSTM 剪枝后大小:
结论:与理论简洁性优势完全吻合。
7.3 长度泛化实验
| 模型 | 训练长度 | 测试长度 | 准确率 |
|---|---|---|---|
| Transformer (标准) | 50 | 100 | 85% |
| Transformer (RoPE) | 50 | 100 | 95% |
| Transformer (NoPE) | 50 | 100 | 60% |
| LSTM | 50 | 100 | 45% |
观察:Transformer + 好的位置编码 = 更好的长度泛化。但简洁性不是充分条件。
八、意义与启示
8.1 架构设计的简洁性原则
新设计原则:
设计架构时,简洁性应作为重要评价指标。
具体含义:
- 优先选择能用多项式大小电路实现目标函数的架构
- 避免”硬编码”指数大小的归纳偏置
- 简洁性意味着可学习性
8.2 与缩放律的关系
缩放律(Scaling Laws):
- 模型性能 (参数量、数据量、计算量)的幂律
- 性能随规模提升
简洁性视角:
- 大模型 = 大电路
- 缩放 = 学习更大的电路
- Transformer 的简洁性意味着参数利用率高
这解释了为什么 Transformer 的缩放律比 RNN 更陡。
8.3 对未来架构的影响
预测:
- 简洁性成为新架构的核心评价指标
- 电路大小估计成为分析工具
- 电路深度优化成为架构搜索目标
- 形式语言基准用于评估架构表达力
8.4 与神经科学的联系
猜想:
- 人脑可能是极其简洁的电路
- ICL 可能是简洁电路的快速调整
- 这与 Transformer 的简洁性有结构相似
但目前是猜想——需要更多研究。
九、形式化与未来方向
9.1 形式化框架的统一
Bergsträßer et al. 2025 提供了一个统一框架:
| 概念 | 严格定义 | 工具 |
|---|---|---|
| 模型族 | 神经架构类 | 计算图 |
| 大小 | 参数量 + 深度 | 电路大小 |
| 表达力 | 识别的语言类 | 形式语言 |
| 简洁性 | 大小-语言关系 | 电路复杂度 |
应用:
- 任何两个架构可以严格比较简洁性
- 简洁性可作为优化目标
- 简洁性实验测量方法
9.2 开放问题
- 深度 vs 宽度:深度 Transformer 与宽度 Transformer 的简洁性
- 位置编码的作用:RoPE/ALiBi 等是否改变简洁性
- Softmax 精度:浮点精度对简洁性的影响
- 现代架构:MoE、Hybrid、SSM 的简洁性
- 学习理论:简洁性 vs PAC 学习
9.3 对其他领域的影响
- 算法推理:理解 Transformer 在算法任务上的优势
- 数学推理:链式思维 (CoT) 的电路解释
- 多模态:跨模态 Transformer 的简洁性
- AI 安全:简洁电路的可解释性
十、完整技术附录
10.1 形式定义汇总
定义 1(Transformer 电路大小):深度 、宽度 的 Transformer,电路大小 。
定义 2(RNN 电路大小):深度 、状态维度 的 RNN,电路大小 (每步),或 (完整序列)。
定义 3(语言识别): 被 在 大小下识别,如果对每个 存在 实例 大小 ,使 对所有 。
定义 4(简洁性偏序): 如果 识别的每个 也能被 在多项式大小识别。
定义 5(严格简洁性): 如果 且 。
10.2 主定理陈述
定理 1(Main Result, Bergsträßer et al. 2025):
设 = 标准 Transformer(带 RoPE), = 任何固定深度 RNN。
则 。
证明概要:
- ():任何 RNN 能识别的语言 Transformer 也能识别(已有结果)
- ():存在语言 (如 MAJORITY)使得:
- Transformer 用 大小识别
- 任何固定深度 RNN 需要 状态
关键技术:
- 用 softmax 模拟 MAJORITY 门
- TC⁰ 电路的层次结构
- RNN 状态数的 上界
10.3 实验复现
import torch
import torch.nn as nn
import torch.nn.functional as F
import numpy as np
def generate_majority_data(n_samples, seq_len):
"""生成 MAJORITY 数据集"""
X = torch.randint(0, 2, (n_samples, seq_len)).float()
Y = (X.mean(dim=1) > 0.5).float()
return X, Y
class SimpleTransformer(nn.Module):
"""极简 Transformer"""
def __init__(self, d_model, n_heads):
super().__init__()
self.attn = nn.MultiheadAttention(d_model, n_heads, batch_first=True)
self.ffn = nn.Linear(d_model, 1)
def forward(self, x):
# x: (B, n) - 比特序列
h = x.unsqueeze(-1).expand(-1, -1, 64) # 简单嵌入
attn_out, _ = self.attn(h, h, h)
out = self.ffn(attn_out.mean(dim=1))
return torch.sigmoid(out.squeeze(-1))
class SimpleLSTM(nn.Module):
"""极简 LSTM"""
def __init__(self, d_state):
super().__init__()
self.lstm = nn.LSTMCell(1, d_state)
self.out = nn.Linear(d_state, 1)
def forward(self, x):
# x: (B, n)
h = torch.zeros(x.size(0), self.lstm.hidden_size, device=x.device)
c = torch.zeros_like(h)
for t in range(x.size(1)):
h, c = self.lstm(x[:, t:t+1], (h, c))
return torch.sigmoid(self.out(h).squeeze(-1))
def train_and_measure():
"""训练并测量样本复杂度"""
seq_len = 20
results = {}
for n_samples in [100, 300, 1000, 3000, 10000]:
X, Y = generate_majority_data(n_samples, seq_len)
# Transformer
torch.manual_seed(42)
model = SimpleTransformer(d_model=64, n_heads=4)
opt = torch.optim.Adam(model.parameters(), lr=1e-3)
for epoch in range(20):
pred = model(X)
loss = F.binary_cross_entropy(pred, Y)
opt.zero_grad()
loss.backward()
opt.step()
with torch.no_grad():
acc = ((model(X) > 0.5).float() == Y).float().mean()
results[f'transformer_{n_samples}'] = acc.item()
# LSTM
torch.manual_seed(42)
model = SimpleLSTM(d_state=64)
opt = torch.optim.Adam(model.parameters(), lr=1e-3)
for epoch in range(20):
pred = model(X)
loss = F.binary_cross_entropy(pred, Y)
opt.zero_grad()
loss.backward()
opt.step()
with torch.no_grad():
acc = ((model(X) > 0.5).float() == Y).float().mean()
results[f'lstm_{n_samples}'] = acc.item()
return results
if __name__ == "__main__":
results = train_and_measure()
for k, v in results.items():
print(f"{k}: {v:.4f}")总结
《Transformers are Inherently Succinct》(ICLR 2026 Outstanding) 提供了 Transformer 表达力优势的严格理论证明:
- 核心结果:Transformer strictly more succinct than 固定深度 RNN
- 关键技术:softmax 模拟 TC⁰ 电路的”软门”
- 重要意义:为 Transformer 训练效率、长度泛化、ICL 提供形式化解释
- 未来影响:简洁性成为新架构的核心评价指标
关键洞察:
Transformer 之所以强大,不只是因为它能识别更多语言,而是因为它能更”简洁”地识别——这意味着更小的电路、更少的参数、更高的样本效率。
这一结果与 Merrill-Sabharwal TC⁰ 严格性、Pérez et al. 2019 表达力研究一脉相承,但严格超越了——是 Transformer 理论基础的重要里程碑。1
参考资料
Footnotes
-
主要参考:Bergsträßer, Cotterlin, Lin 2025 “Transformers are Inherently Succinct” (ICLR 2026 Outstanding Paper, https://arxiv.org/abs/2510.19315)。相关工作:Merrill & Sabharwal 2023 (TACL) “The Expressive Power of Transformers with Hard Attention”、Merrill & Sabharwal 2024 (JMLR) “A logic for expressing log-precision transformers”、Pérez et al. 2019 “On the Expressive Power of Transformers”、Hao et al. 2022 (NeurIPS) “Formal Language Recognition by Hard Attention Transformers”、Chiang & Chollet 2023 “On the Expressive Power of Deep Learning”、Garg et al. 2022 “What Can Transformers Learn In-Context?” 等。 ↩ ↩2