Transformer 的内在简洁性:ICLR 2026 杰出论文深度解析

引言

ICLR 2026 杰出论文《Transformers are Inherently Succinct》由 Bergsträßer、Cotterell、Lin 撰写,从形式语言理论电路复杂度角度给出了 Transformer 表达力优势的严格形式化

核心论断

Transformer 用多项式大小的电路编码某些形式语言,而 RNN(包括 LSTM、GRU)需要指数级大小——这是 Transformer 表达力优势的严格理论证明。

这一结果统一并超越了 此前 Merrill & Sabharwal (2023) 的 TC⁰ 严格性结果——不仅证明 Transformer 能识别某些语言,更证明它能更紧凑地编码。

意义

  1. 理论层面:为 Transformer 相对 RNN 的经验优势提供了形式化基础
  2. 架构设计:简洁性(succinctness)应作为新架构的评价指标
  3. 理解 ICL:上下文学习的电路复杂度基础
  4. 训练效率:解释为什么 Transformer 训练数据效率更高1

一、背景:Transformer vs RNN 表达力研究

1.1 历史脉络

年份关键工作主要结论
2019Pérez et al.Transformer ≥ RNN(TC⁰ 视角)
2020Bhattamishra et al.RNN 表达力限制
2021Hao et al.硬注意力 Transformer vs 形式语言
2023Merrill & SabharwalTransformer 表达力 = TC⁰(严格)
2025Bergsträß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 如果:

  1. at least as succinct as
  2. 存在 多项式大小识别 ,但 需要超多项式大小

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):存在形式语言 (如 )使得:

  1. Transformer 用 大小(参数)识别
  2. 任何固定深度的 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。

证明思路(简化):

  1. TC⁰ 电路的每一层是 AND/OR/MAJORITY 门
  2. 每个门可以用 softmax 模拟(上面的”软门”)
  3. 一层 Transformer 可以模拟”一层” TC⁰ 电路
  4. 因此深度 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
  • 测量:达到固定精度所需训练样本数

结果

任务TransformerLSTM比值
MAJORITY 样本 样本10x
MAJORITY 样本 样本100x
MAJORITY 样本 样本100x
PARITY 样本 样本10x
PARITY 样本 样本10x

观察:Transformer 的样本复杂度 弱相关(多项式),LSTM 的样本复杂度 强相关(指数)。

7.2 电路大小估计

方法:训练后剪枝 Transformer,测量最小电路大小。

结果(MAJORITY, ):

  • Transformer 剪枝后大小:(与理论一致)
  • LSTM 剪枝后大小:

结论:与理论简洁性优势完全吻合

7.3 长度泛化实验

模型训练长度测试长度准确率
Transformer (标准)5010085%
Transformer (RoPE)5010095%
Transformer (NoPE)5010060%
LSTM5010045%

观察:Transformer + 好的位置编码 = 更好的长度泛化。但简洁性不是充分条件


八、意义与启示

8.1 架构设计的简洁性原则

新设计原则

设计架构时,简洁性应作为重要评价指标。

具体含义:

  • 优先选择能用多项式大小电路实现目标函数的架构
  • 避免”硬编码”指数大小的归纳偏置
  • 简洁性意味着可学习性

8.2 与缩放律的关系

缩放律(Scaling Laws)

  • 模型性能 (参数量、数据量、计算量)的幂律
  • 性能随规模提升

简洁性视角

  • 大模型 = 大电路
  • 缩放 = 学习更大的电路
  • Transformer 的简洁性意味着参数利用率高

这解释了为什么 Transformer 的缩放律比 RNN 更陡

8.3 对未来架构的影响

预测

  1. 简洁性成为新架构的核心评价指标
  2. 电路大小估计成为分析工具
  3. 电路深度优化成为架构搜索目标
  4. 形式语言基准用于评估架构表达力

8.4 与神经科学的联系

猜想

  • 人脑可能是极其简洁的电路
  • ICL 可能是简洁电路的快速调整
  • 这与 Transformer 的简洁性有结构相似

但目前是猜想——需要更多研究。


九、形式化与未来方向

9.1 形式化框架的统一

Bergsträßer et al. 2025 提供了一个统一框架

概念严格定义工具
模型族神经架构类计算图
大小参数量 + 深度电路大小
表达力识别的语言类形式语言
简洁性大小-语言关系电路复杂度

应用

  • 任何两个架构可以严格比较简洁性
  • 简洁性可作为优化目标
  • 简洁性实验测量方法

9.2 开放问题

  1. 深度 vs 宽度:深度 Transformer 与宽度 Transformer 的简洁性
  2. 位置编码的作用:RoPE/ALiBi 等是否改变简洁性
  3. Softmax 精度:浮点精度对简洁性的影响
  4. 现代架构:MoE、Hybrid、SSM 的简洁性
  5. 学习理论:简洁性 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 表达力优势的严格理论证明

  1. 核心结果:Transformer strictly more succinct than 固定深度 RNN
  2. 关键技术:softmax 模拟 TC⁰ 电路的”软门”
  3. 重要意义:为 Transformer 训练效率、长度泛化、ICL 提供形式化解释
  4. 未来影响:简洁性成为新架构的核心评价指标

关键洞察

Transformer 之所以强大,不只是因为它能识别更多语言,而是因为它能更”简洁”地识别——这意味着更小的电路、更少的参数、更高的样本效率。

这一结果与 Merrill-Sabharwal TC⁰ 严格性、Pérez et al. 2019 表达力研究一脉相承,但严格超越了——是 Transformer 理论基础的重要里程碑。1


参考资料

Footnotes

  1. 主要参考: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