「注意力实际上是对数的」？七年前的Transformer还有新发现，Karpathy点赞

机器之心 · 公众号 · AI · 2025-03-23 12:01

正文

选自 supaiku.com

作者：Spike Doanz

机器之心编译

「注意力实际上是对数的」？今天，一篇博客再次掀起了AI社区对注意力机制的讨论。

作者认为，Transformers 中实现的注意力机制，在计算复杂度上应该被视为对数级别的。

这篇博客，还得到了 Karpathy 的高度肯定：

有时我会在想象中的神经网络完整计算图中将其描述为「广度是免费的，深度是昂贵的」。

据我所知，这首先是 Transformer 背后的主要见解 / 灵感。我第一次真正受到它的震撼是在很久以前我读到 Neural GPU 论文的时候（https://arxiv.org/abs/1511.08228）。

另外，在「从比特到智能」中为什么还要包含 python？删除 python，我认为你可以将其减少约 10 倍，就像 llmc 一样。

我们知道，标准的注意力机制（如 Transformer 中的自注意力）计算步骤如下：

其复杂度主要来源于：

点积计算：QK^⊤ 的矩阵乘法，复杂度为 O (n^2d)，其中 n 是序列长度，d 是特征维度。
Softmax 归一化：对每个位置的注意力权重进行归一化，复杂度为 O (n^2)。

一般来说，研究者认为总复杂度随着序列长度 n 呈平方增长，这也是标准 Transformer 难以处理长序列的核心瓶颈。

而这篇博客，却提出了另外一个全新的视角。

关于如何理解这一观点，我们看看博客内容便知。

博客链接：https://supaiku.com/attention-is-logarithmic

以下是博客内容：

时间复杂度是衡量算法快慢最常用的标准。在 20 世纪 80 年代，那时候计算机大多只有一个核心，大家还不知道什么是单指令多数据（SIMD）技术，所以用时间复杂度来评估算法基本是合理的。

但现在是 2025 年，单核计算机已经很少见了，就连智能手机都有 4 到 8 个核心。在这种情况下，只用时间复杂度来衡量算法的快慢就不够全面了。

举个例子来说，一个时间复杂度为 O (n³) 但能够并行的算法，和一个必须按顺序执行的算法，单从时间复杂度上看不出来它们的区别。而且，有些算法天生就是并行的，比如线性代数，但人们还在用时间复杂度来描述它们，这其实是很荒谬的。

我们需要一种更好的方式来衡量算法的复杂度。「work-depth 模型」分析提供了一个很好的思路。它不仅关注输入大小对应的操作数量，还能从理论下限的角度思考算法的复杂度。

我们不仅要考虑算法执行的原始操作数量（即「work」），更要关注计算图相对于输入大小的「depth」，也就是不可并行的顺序操作的最小数量。因为这些顺序操作是不可避免的，无论你的计算机有多少个核心，它们都会造成阻塞。

我主要研究机器学习系统的性能工程，所以接下来我会重点讨论适用于张量的算法。「work-depth 模型」虽然不完美，但很有用。

在此，我先抛出一个问题：逐个元素相乘的时间复杂度是多少？从这个问题出发，我会进一步阐述我的观点：Transformers 中实现的注意力机制，在计算复杂度上应该被视为对数级别的。

案例 1：逐个元素相乘

给定两个长度相同的向量 a 和 b，逐个元素相乘是将 a 中的每个元素与 b 中对应索引位置的元素相乘，并将结果存储在新向量 c 中（或者直接在原位置修改）。

代码如下：

从时间复杂度的角度看，这好像是线性的。如果用单线程来跑，那确实就是线性的。

然而，如果仔细观察，你会发现在这个问题的计算图中，range (n) 中的各个步骤之间没有依赖关系。它们完全独立。那么为什么不并行执行它们呢？

这正是每个线性代数 / 张量库在底层所做的事情。

你很快会发现，逐个元素相乘实际上根本不是线性时间的！它实际上看起来像是常数时间，直到达到一个神秘的临界点。

具体来说，我们可以分析逐个元素相乘时的「work」和「depth」：

算法里的每一步操作，比如加载数据、做乘法、存储，这些操作本身都不复杂，理论上只需要常数时间就能完成。只要你的计算机有足够的并行计算能力，直到某个临界点，这些操作的时间复杂度都是常数时间。

案例 2：向量求和

向量求和比相乘更复杂一些。在这里，我们可以清楚地看到两个步骤之间存在依赖关系（因为累加需要调用 c 的状态）。这无法完全并行执行。

「注意力实际上是对数的」？七年前的Transformer还有新发现，Karpathy点赞

正文

请到「今天看啥」查看全文