手推 self-attention 与 O(n²):除根号 d_k、多头与复杂度怎么答
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 手推一下 self-attention。
- 为什么 self-attention 的复杂度是 O(n²)?
- 为什么要除 √d_k?
- multi-head 到底在表达什么?
- 复杂度里的 n 和 d 分别指什么?
- FlashAttention 改变了这个复杂度吗?
《参考解析》
手推 self-attention:输入序列 X ∈ R^{n×d},用三组可学习权重投影出 Q = XW_Q、K = XW_K、V = XW_V,形状都是 n×d_k(多头时每个头 d_k = d/h)。打分矩阵 S = QK^T / √d_k 是 n×n,每一行表示一个位置对所有位置的相似度;对每一行做 softmax 得到注意力权重 A;输出 O = AV,形状 n×d_v。多头的做法是把 d 维切成 h 份,各自独立算一遍再拼回 n×d,最后过一层输出投影。
复杂度里 n 和 d:n 是序列长度,d 是隐层维度(单头时是 d_k)。QK^T 是 n×d 乘 d×n,计算量 O(n²d);softmax 在 n×n 矩阵上做,是 O(n²);AV 是 n×n 乘 n×d,又是 O(n²d)。所以完整说法是 O(n²d),当 d 固定、只讨论随序列长度的增长时简写成 O(n²)。帖主第一次把两者说混,面试官打断纠正的正是这一点——说「O(n²)」时要明确省略的是 d。
为什么除 √d_k:q 与 k 的各分量独立、方差约为 1 时,点积的方差约为 d_k,维度越高点积绝对值越大。softmax 对大输入会饱和,最大项接近 1、其余接近 0,反向传播时梯度接近消失。除以 √d_k 把方差拉回 1 量级,让 softmax 落在梯度有效的区间。缩放过头会让分布过于平坦、注意力失去区分度;完全不缩放则训练容易不稳定。
多头在表达什么:每个头有独立的投影,可以在不同的子空间里关注不同类型的关系——有的头偏向邻近位置、有的头偏向句法依存、有的头做指代对齐。多个头拼接后再投影,相当于让模型同时从多个角度做加权聚合,表达能力强于单头同维度。头数不是越多越好:d_k 太小会限制每个头的表达能力,通常保持 d_k 在 64 或 128 左右。
FlashAttention 改了什么:它没有改变 O(n²d) 的计算量,而是改变显存访问方式——把 Q、K、V 分块载入 SRAM,在块内做注意力并用在线 softmax 累积结果,避免把 n×n 的完整打分矩阵写回 HBM。所以它的收益来自减少显存读写(IO)而不是减少浮点运算,长序列下速度提升明显、显存占用从 O(n²) 降到 O(n),但复杂度阶数不变。类似的还有稀疏注意力、线性注意力,那些才是从算法层面降低复杂度,代价是表达能力或实现复杂度。