2026-09-21
Columbia 与 NYU 证明常数层 self-attention 与常数轮 MPC 可互模拟。对数深度足以解图连通与 k-hop；RNN、Mamba 与稀疏注意力在同等宽度下需要线性深度。
此前对 Transformer 表达能力的理论，大多落在两个极端。一边是万能逼近：模型足够大就能模拟任何序列函数或图灵机，尺寸随任务爆炸，看不出比 RNN 强在哪。另一边是常数深度的精细下界：层数固定、上下文变长时，括号匹配、布尔公式求值、图连通都做不成。真实大模型走的是中间尺度：上下文长度 N 暴涨，深度 L 和宽度 m 只随 N 亚线性增长。
这篇把这条中间尺度钉在分布式计算上。Columbia 的 Clayton Sanford、Daniel Hsu 和 NYU 的 Matus Telgarsky 证明，常数层 self-attention 可以高效模拟常数轮 Massively Parallel Computation（MPC，每台机器内存亚线性、同步轮次通信的 MapReduce 式模型），也可以被它模拟回来。并行，才是 Transformer 相对 RNN、GNN、稀疏注意力的真正差别。
核心是双向模拟。理论设定里，Q/K/V 映射和 MLP 都是任意的逐位置函数，限制只发生在「多个位置如何交互」；位置可以写进嵌入，因此证明里不需要额外的位置编码。中间计算按 p = Θ(log N) 比特精度，和低精度训练的实践一致。
正向：任意 R 轮、(γ, δ)-MPC 协议（每机内存 s = O(N^δ)，δ < 1）可被深度 L = R + 1、嵌入维 m = O(N^{4δ} log N)、头数 H = O(log log N) 的 Transformer 精确实现。每轮本地计算塞进逐位置 MLP 和 Q/K/V。难的是同时把最多 s 条带地址的消息送到各自目的地。他们用一层 attention 做路由：消息先被做成稀疏冗余的数据包，再用单头稀疏传播（同时对 N 个子集求平均）送到接收方，靠纠错从平均里还原原文。这条路由依赖全对全 attention，论文写明未必存在亚二次近似。δ ≥ 1/4 时嵌入维会到 N 量级，单层就能吞下整段输入，深度优势被假设抹掉，所以有内容的区间是强亚线性内存。
反向：深度 L、mH = O(N^δ) 的 Transformer，可被 O(L/(δ′ − δ)) 轮 MPC 模拟，机器数 O(N²)。三类机器分工：每个 token 一台负责 Q/K/V，每对 token 一台算内积，再一批传播机做 softmax 聚合。
配套玩具任务是 k-hop induction heads。普通 induction head 找「当前 token 上次出现时，它后面那个字」；k-hop 把这个指针追 k 次。表面像要 k 步，他们用指针倍增：前两层做出 1-hop（拷贝前一 token，再做 lastOccurrence），之后每层把指针长度翻倍。深度 L = ⌊log₂ k⌋ + 2、宽度常数、单头因果 Transformer 就够。
图算法直接继承 MPC 文献。直径至多 D 的图，存在 m = O(N^ε)、H = O(log log N)、L = O(log D) 的 Transformer 能标出连通分量，生成森林一类问题同样可搬过来。若「区分一个 N 点环和两个 N/2 点环需要 Ω(log N) 轮亚线性内存 MPC」这则标准猜想成立，则在 mH = O(D^{1-ε}) 时深度必须 Ω(log D)。对数深度接近最优。
对照 GNN 的反差很大。Loukas 在 CONGEST 模型下证明：存在 N 边图，消息传递 GNN 要满足 L√m = Ω̃(N^{1/4}) 才能判断子图连通或是否生成树。Transformer 不沿原图边传消息，每层都能改接线，对数层就够。
k-hop 的下界同样挂在那则猜想上：k = Θ(N^ξ) 且 mH = O(k^{1-ε}) 时，L = Ω(log k)。实验用 HuggingFace 的 GPT-2 式因果 Transformer，N = 100、字母表大小 4、k 到 16，Adam、学习率 10^{-4}、batch 32、训练 10^5 步，无限新样本。4 头、嵌入维 128 时，深度与可解 hop 数呈指数关系：
| 深度 L | 低误差覆盖的 k | 参数量 |
| 2 | 约 k=1，其余任务误差至少 10% | 41 万 |
| 3 | k≤2，误差不超过 1% | 61 万 |
| 4 | 大约 k≤4 | 81 万 |
| 5 | 大约 k≤8 | 101 万 |
| 6 | k≤16，k=16 时误差 6.2% | 121 万 |
阈值落在 ⌊log₂ k⌋ + 2，和构造一致。加宽到 8 头、嵌入维 256，效果大约只相当于再加一层，参数花得更多。训出来的 attention 几乎是「一跳对准一个位置」：第 1 层对齐前驱，后续层分别对齐 find¹、find²、find³、find⁸，和倍增构造对得上。3000 条有限样本已经接近无限样本曲线；1000 条会过拟合，但 6 层仍比 4 层更能做 hop3，靠的是连续堆几个 1-hop，不是倍增。
RNN（推理时等价于 RNN 的 Mamba 也算）要么深度至少 k，要么宽度 m = Ω(N/k⁶)。Performer 一类核近似要把特征维拉到几乎 N 才够；Longformer 要把窗口或全局 token 加密到接近稠密，亚二次优势就没了。单层加 chain-of-thought：思维链长度至少 k，否则宽度同样要 Ω(N/k⁶)。
这给「为什么还要用满注意力、深度不能随便砍」一个可证的说法。常数深度在电路复杂度里几乎是 AC⁰，做不了连通性；对数深度刚好跨过 MPC 里连通性那条坎。想用线性时间的状态空间模型或稀疏注意力换掉满注意力，在需要反复追指针、做全局聚合的任务上，会把对数层变成线性层。
这是表达能力论文，不是新架构，不能直接拿来改训练配方。设计长上下文模型时，有两条能用的推论：全对全 attention 的通信能力可能省不掉；深度对组合任务的收益是指数级的，加宽补不齐。
下界全部依赖 one-versus-two cycle 猜想，不是无条件结果。正向模拟把嵌入维放到 O(s⁴ log N)，后续 Sanford 等人 2024 年的工作已把内存条件放宽到任意严格亚线性，这篇自己的编译损耗不小。MLP 和 Q/K/V 被当成任意逐位置函数，证明的是信息流结构，不是标准 Transformer 用固定宽度 MLP 就能训出同一电路。
实验尺度很小：N=100、字母表只有 4 个符号、最深 6 层、最大约 480 万参数，还是在 M1 笔记本上跑的。嵌入维 128 已经大于上下文 100，浅模型可能把逻辑塞进 MLP 硬记，论文自己点了这一点。k-hop 是合成任务，迁到自然语言有多远没有证据。可学习性没有理论，只有 Adam 能找到类似倍增的解。MPC 也解释不了 GPU 上的训练和推理吞吐。