Attention 真正换了什么：用 O(n²) 计算买下 O(1) 的路径

2017 年，“Attention Is All You Need” 抛出了一个相当激进的主张：序列建模可以完全基于注意力，扔掉 recurrence（RNN/LSTM）和 convolution。

这在当时并不像是稳妥的选择。RNN 是主流，CNN 也在序列任务上有一席之地，论文却把这两条路都放下了。

更值得注意的是，它不是靠更大的模型或更多的数据赢的，而是赢在一个很具体的指标上：WMT 2014 英德翻译 28.4 BLEU、英法翻译 41.8 BLEU，超过当时的集成模型 2 个 BLEU 以上，而且 8 块 P100 只训练了 3.5 天。

我读这篇论文时反复在想一个问题：

自注意力到底用什么东西，换来了这样的结果？

把它的机制拆开看，答案可以浓缩成一笔交易：

用 O(n²) 的计算量，买下任意两个位置之间 O(1) 的交互路径。

这篇文章想解释的，就是这笔交易为什么在 2017 年成立，以及它留下了什么债。

真正的瓶颈是“路径长度”，不只是参数

要理解这笔交易，得先看 RNN 和 CNN 卡在哪。

RNN 有两个老问题。第一，它阻碍并行：序列里每个 token 必须等前一个 token 的隐藏状态算出来才能继续，训练时无法在时间步维度上并行。第二，长距离依赖难：任意两个位置之间信号传递的最短路径是 O(n)，还容易受梯度消失或爆炸影响。

CNN 稍好一点。ConvS2S 把任意两个位置的交互路径降到线性 O(n)，ByteNet 降到对数 O(log n)。它也能并行，但路径仍然随距离增长。

这里我想强调一个容易被忽略的视角：

序列建模的瓶颈，往往不在参数容量，而在“任意两个位置之间信号要传多少步”。

论文里那张关键对比表（Table 1）把这个差异说得很清楚：

自注意力是唯一一个把“最大路径长度”压到 O(1) 的方案。任意一个位置，一步就能看到所有其他位置。RNN 要传 n 步，CNN 要传 log_k n 步，自注意力只要 1 步。

这就是这笔交易“买进”的那一侧。

机制：一步看全局，代价是 O(n²)

自注意力具体怎么做到“一步看全局”？

它把每个位置同时变成 query、key、value，用 query 和所有 key 算相似度，softmax 归一化后对 value 做加权和：

$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right) V$

每个位置都独立地、同时地执行这个计算，不需要等任何其他位置。这就是并行化的来源，也是顺序操作数能降到 O(1) 的原因。

但这套机制有两个直接代价。

第一个代价是计算量变成 O(n²·d)。每个位置都要和所有其他位置算一次相似度，序列一长，计算量按平方膨胀。Table 1 里 Self-Attention 那一列，是三者中唯一带 n² 的。

第二个代价更隐蔽。注意力本质上是对所有 value 做加权平均，这会“稀释”每个位置的有效分辨率。论文用 Multi-Head Attention 来弥补：把注意力拆成 h 个头（论文里 h=8），让不同头关注不同子空间，再拼回来。每个头维度降低（64 而非 512），总计算成本和全维度单头注意力相近。

单头靠平均会丢失信息，多头靠分工把信息找回来。

所以 O(n²) 不是设计疏忽，而是“一步看全局”这件事的标价。问题只是这个标价在当时值不值。

一个容易被漏掉的细节：为什么要除以 √d_k

讲这笔交易不能漏一个细节。注意力公式里为什么要除以 √d_k？

假设 q 和 k 的分量都是均值为 0、方差为 1 的独立随机变量，那么点积 q·k 的方差会随维度 d_k 线性增长。当 d_k 很大时，点积的量级会很大，把 softmax 推进梯度极小的饱和区。

除以 √d_k 把方差缩放回 1，让梯度保持正常。

这件事看似是个实现技巧，但它直接关系到这笔交易能不能落地。Self-Attention 里 d_k 取 64，如果维度上去而不做缩放，注意力在大维度下根本训不动。

没有这个缩放，O(1) 路径的设计就只是理论上的优雅。

它也解释了一个反直觉的对比：小 d_k 时，加性注意力和点积注意力表现接近；大 d_k 时，未缩放的点积注意力反而不如加性注意力。

这笔交易在 2017 年为什么值

回到 BLEU。英德 28.4、英法 41.8，而且训练时间从当时主流的几周缩短到 3.5 天。

这里要区分两件事。

事实是：自注意力在翻译任务上同时拿到了更高的 BLEU 和更短的训练时间。

我的解释是：训练时间的缩短，主要来自并行化——顺序操作数从 O(n) 降到 O(1)，GPU 才能被充分填满；而 BLEU 的提升，更可能来自路径缩短让长距离依赖真正建立起来，而不是靠堆更多层把信号慢慢传过去。

但要诚实地说，这两个因素很难干净地分离。BLEU 提升里有多少来自路径缩短、多少来自注意力本身更强的表达力，论文并没有单独验证。

我目前更倾向于认为：

在 2017 年翻译任务的序列长度下，O(n²) 的代价还没显形，而 O(1) 路径的好处已经兑现。

这才是这笔交易当时成立的关键条件——序列长度 n 还不够大。

它没解决的问题，恰恰是后来所有工作的起点

如果只看到“自注意力赢了”，会漏掉这篇论文真正留下的长期问题。

O(n²) 在翻译任务上不疼，是因为翻译的句子不长。一旦序列变长，n² 的计算和显存开销就会迅速成为瓶颈。后来 Longformer、Linformer、线性注意力、FlashAttention 这些工作，本质上都在回答同一个问题：

怎么在保住“一步看全局”好处的同时，把 O(n²) 的代价还回去一部分。

它们大多是在“能看多远”和“算多快”之间做新的权衡——也就是说，它们都在一定程度上牺牲了 Transformer 最初的 O(1) 路径优势。

另一个没被这篇论文充分回答的问题：Multi-Head 靠分工弥补有效分辨率，但“拆成 8 个子空间再拼回来”是否真的等价于原来的全维度注意力？论文只给了结果，没有把这个等价性讲透。

我从这篇论文里得到的判断

我最初把 Transformer 的成功归结为“注意力机制更强”。但反复看 Table 1 之后，我改变了看法。

Transformer 的关键，不是注意力比 RNN/CNN 更聪明，而是它把信号传递路径压成了常数。

这个改变带来两个连锁好处：顺序操作降到 O(1) 解锁了并行化，最大路径降到 O(1) 解锁了长距离依赖。注意力只是实现这个目标的手段。

所以这笔交易的本质是：

用一个当时序列长度还压得住的 O(n²) 代价，换走了两个 RNN/CNN 结构上很难同时解决的问题。

但 O(n²) 不是免费的。它只是被 2017 年的序列长度暂时掩盖了。后来序列越来越长，这笔债就开始浮现——这也是为什么理解 Transformer，不能只看它赢了什么，还要看它欠下了什么。

下一个值得追问的问题

如果“路径长度”才是理解 Transformer 的关键视角，那它也能帮我们看后来的 scaling：

当上下文从几千 token 扩展到百万 token，O(n²) 的代价会不会反过来吞掉 O(1) 路径的好处？

这其实正是现在长上下文模型、线性注意力、状态空间模型（如 Mamba）在反复博弈的问题。Attention 用的“全局一步可达”是不是不可替代，还是说在超长序列上，我们终究要接受某种“路径变长”的折中。

这笔 2017 年做下的交易，到现在还没真正结清。