Flash Attention:从内存瓶颈到在线 softmax 的算法重构
一、为什么需要 Flash Attention
标准 Attention 的计算公式是:
Attention(Q,K,V)=softmax(dQKT)V
其中 Q,K,V∈RN×d,序列长度为 N,注意力头维度为 d。
朴素实现分三步:
- 计算 S=QKT∈RN×N(得分矩阵)
- 计算 P=softmax(S)∈RN×N(归一化后的注意力权重)
- 计算 O=PV∈RN×d(输出)
核心问题在于那个 N×N 的中间矩阵。
当 N=8192、d=128 时,S 矩阵的大小是 8192×8192×4B≈256MB(单头单精度浮点)。多头、多 batch 叠加后,这个中间结果远超 GPU SRAM 容量(A100 的 SRAM 约 192KB/SM),只能写回 HBM。
于是整个计算变成了一个典型的 HBM-bound 流程:
HBM → SRAM: 读 Q, K, V
SRAM → SRAM: 计算 S = QK^T
SRAM → HBM: 写回 S ← 256MB 写入
HBM → SRAM: 读回 S ← 256MB 读出
SRAM → SRAM: 计算 P = softmax(S)
SRAM → HBM: 写回 P ← 256MB 写入
HBM → SRAM: 读回 P ← 256MB 读出
SRAM → SRAM: 计算 O = PV
SRAM → HBM: 写回 O
中间矩阵 S 和 P 各经历一次写回 + 一次读回,总共约 4 次 O(N2) 的 HBM 读写。而实际有用的计算量(矩阵乘法)是 O(N2d),读写量是 O(N2),计算强度(arithmetic intensity)只有 O(d),远低于 GPU 的平衡点。
Flash Attention 的核心思想:永远不在 HBM 中实例化 N×N 的中间矩阵。
二、关键算法:分块计算 + 在线 softmax
2.1 难点:softmax 的全局依赖
如果只是分块计算 S=QKT,那分块矩阵乘法就够了。难点在于 softmax:
softmax(x)i=∑jexjexi
分母 ∑jexj 是一个全局求和,需要看到整行才能归一化。这意味着你不能独立地对每个分块做 softmax 再拼接——分块之间的结果有依赖。
Flash Attention 的核心突破是 online softmax(在线 softmax):允许你以流式方式逐块更新 softmax 的分子和分母,最终得到与全局 softmax 完全一致的结果。
2.2 在线 softmax 的数学推导
假设我们要计算 softmax(x),其中 x=[x1,x2,…,xN]。
将其分成两块:x(1)=[x1,…,xm],x(2)=[xm+1,…,xN]。
第一块的局部 softmax:
m(1)=max(x(1)),ℓ(1)=i=1∑mexi−m(1),f(1)=[ex1−m(1),…,exm−m(1)]
这里 m(1) 是局部最大值(用于数值稳定),ℓ(1) 是局部指数和,f(1) 是局部未归一化的指数值。
第二块的局部 softmax:
m(2)=max(x(2)),ℓ(2)=i=m+1∑Nexi−m(2),f(2)=[exm+1−m(2),…,exN−m(2)]
合并两个块:
全局最大值:
m=max(m(1),m(2))
全局指数和:
ℓ=em(1)−m⋅ℓ(1)+em(2)−m⋅ℓ(2)
全局归一化结果(以第一块为例):
softmax(x)i=ℓexi−m=ℓem(1)−m⋅fi(1),i∈[1,m]
关键观察: 合并时只需要三个量——旧的最大值 m(1)、旧的指数和 ℓ(1)、新的块的 m(2) 和 ℓ(2)。旧的逐元素值 f(1) 只需要一个缩放因子 em(1)−m 就能修正到新的全局基准。
这意味着我们可以逐块处理,每处理完一块就更新 (m,ℓ) 这两个标量,不需要保存所有块的原始数据。
2.3 完整的 Flash Attention 算法
将 Q,K,V 沿序列维度分块:
- Q 分成 Br 行一块:Q1,Q2,…,Q⌈N/Br⌉,每块 Qi∈RBr×d
- K,V 分成 Bc 列一块:K1,…,K⌈N/Bc⌉,每块 Kj∈RBc×d
外层循环遍历 Q 的每个行块 Qi,内层循环遍历 K,V 的每个列块 Kj,Vj。
算法: FlashAttention(Q, K, V)
输入: Q, K, V ∈ R^{N×d}, 分块大小 Br, Bc
输出: O ∈ R^{N×d}
1. 初始化 O = 0, ℓ = 0, m = -∞ (每行一个标量)
2. for i = 1 to ⌈N/Br⌉:
3. 加载 Qi 到 SRAM
4. 初始化 Oi = 0, ℓi = 0, mi = -∞
5. for j = 1 to ⌈N/Bc⌉:
6. 加载 Kj, Vj 到 SRAM
7. 计算 Sij = Qi × Kj^T / √d
8.
9.
10. mij = rowmax(Sij)
11. Pij = exp(Sij - mij)
12. lij = rowsum(Pij)
13.
14. mi_new = max(mi, mij)
15. ℓi_new = e^{mi - mi_new} × ℓi + e^{mij - mi_new} × lij
16.
17.
18. Oi = e^{mi - mi_new} × Oi + Pij × Vj
19.
20. mi = mi_new, ℓi = ℓi_new
21. end for
22. Oi = Oi / ℓi
23. 写回 Oi 到 HBM
24. end for
逐步解释关键行:
- 第 7 行:Sij 是一个 Br×Bc 的小矩阵,只要 Br×Bc 能放进 SRAM,就不会写回 HBM。
- 第 10-12 行:对当前小块做局部 softmax 的前半部分(求最大值、指数、求和)。
- 第 14-15 行:用前面推导的合并公式更新全局的 mi 和 ℓi。注意 emi−minew 这个因子——如果新块的最大值更大,旧块的结果需要按比例缩小。
- 第 18 行:输出 Oi 的累加也乘上同样的缩放因子。本质上是在维护未归一化的加权和,最后在第 22 行统一除以 ℓi 完成归一化。
2.4 为什么这样写是对的
最终输出第 i 行的精确值应该是:
Oi=∑jeSij−m∑jeSij−mVj
算法中维护的 Oi(归一化前)恰好是分子 ∑jeSij−mVj,ℓi 恰好是分母 ∑jeSij−m。每次内层迭代用在线公式更新这两个量,数学上等价于先算完所有块再归一化,但不需要存储任何 N×N 的中间矩阵。
三、分块大小的选择与 SRAM 约束
Flash Attention 的正确性和性能都依赖于一个前提:分块矩阵 Sij 和 Pij 能放进 SRAM。
设 SRAM 大小为 M,每个元素 4 字节(FP32),则需要:
Br×Bc×4≤M
同时还要放 Qi(Br×d)、Kj(Bc×d)、Vj(Bc×d)、Oi(Br×d)等,所以实际约束更紧。论文中取 Br=4dM,Bc=min(4dM,d)。
以 A100 为例:M≈192KB,d=128,则 Br≈384。这意味着内层循环每次处理约 384 行 × 128 列的小块,远小于 N×N。
HBM 读写量分析:
| 操作 |
标准 Attention |
Flash Attention |
| 读 Q, K, V |
O(Nd) |
O(Nd) |
| 中间矩阵 S 读写 |
O(N2) |
0(不实例化) |
| 中间矩阵 P 读写 |
O(N2) |
0(不实例化) |
| K, V 重复读取 |
0 |
O(N2d/Br) |
| 写回 O |
O(Nd) |
O(Nd) |
| 总计 |
O(N2+Nd) |
O(N2d2/M+Nd) |
当 N 很大时,Flash Attention 的读写量降低了约 d2M 倍。以 M=192KB, d=128 为例,约降低 12 倍。
四、反向传播:重计算策略
标准 Attention 的反向传播需要用到前向的 P 矩阵(注意力权重)来计算梯度:
dP=(dO⋅VT)⊙P⊙(1−P)
dQ=(dP⋅V)⋅KT/d,dK=(dPT⋅V)⋅QT/d,dV=PT⋅dO
标准做法是前向时把 P 存到 HBM,反向时读回来。但 Flash Attention 前向时没有保存 P——这正是它的优势,也是反向的挑战。
Flash Attention 的解法:重计算(recomputation)。
反向传播时,重新跑一遍前向的分块循环,在 SRAM 中即时重算出当前块的 Sij 和 Pij,然后直接用于梯度计算。这样:
- 前向:不存 P,只存 O 和 ℓ(用于反向时重算 softmax 的归一化),HBM 开销 O(Nd)
- 反向:多一次前向计算量,但避免了 O(N2) 的 HBM 读写
Tradeoff 分析: 重计算增加了约一倍的计算量(FLOPs),但减少了 O(N2) 的 HBM 读写。由于 Attention 本身是 HBM-bound 的,减少读写带来的加速远超额外计算的开销。这就是 Flash Attention 论文标题中 “IO-Aware” 的含义——用额外的计算换更少的 IO,在 IO-bound 场景下这是净赚的。
五、Flash Attention v2 的改进
Flash Attention v2 在 v1 的基础上做了三个关键优化:
5.1 减少非矩阵乘法运算
v1 中在线 softmax 的缩放因子 emi−minew 和指数求和等操作是逐元素的,无法利用 tensor core 的矩阵乘法单元。v2 通过代数重排,将这些标量缩放操作推迟到循环外,减少了内层循环中的非 matmul 运算次数。
具体来说,v2 在内层循环中只维护未缩放的 Oi 和 ℓ~i,将所有缩放因子累积为一个单独的变量,在循环结束后统一应用。这使得内层循环几乎只剩下矩阵乘法。
5.2 交换循环顺序
v1 的循环顺序是外层遍历 K/V 的列块,内层遍历 Q 的行块。这样每个 Q 行块的中间结果 Oi 需要在内层循环中反复更新和写回 HBM。
v2 改为外层遍历 Q 的行块,内层遍历 K/V 的列块。这样每个 Qi 的完整计算在一次外层迭代中完成,Oi 只在循环结束时写回一次 HBM。这个改动减少了 HBM 写回次数。
5.3 更好的并行度
v2 将 Q 的行块分配到不同的线程块(thread block)上,每个线程块独立处理一组 Q 行,互不依赖。对于长序列场景,这提供了 ⌈N/Br⌉ 个并行单元,能更好地利用 GPU 的 SM 数量。同时 v2 还在 thread block 内部进一步拆分,将 K/V 的列块分配到不同的 warp 上做并行累加。
六、一个具体数值例子
为了直观理解在线 softmax 的运作方式,走一个具体例子。
设 x=[2,4,3,1](N=4),分成两块 x(1)=[2,4],x(2)=[3,1]。
标准 softmax
m=4,ex−m=[e−2,1,e−1,e−3]≈[0.135,1,0.368,0.050]
ℓ≈1.553,softmax(x)≈[0.087,0.644,0.237,0.032]
在线 softmax(逐块处理)
处理第一块 x(1)=[2,4]:
m(1)=4,f(1)=[e−2,1]≈[0.135,1],ℓ(1)≈1.135
当前状态:m=4,ℓ=1.135,f=[0.135,1]
处理第二块 x(2)=[3,1]:
m(2)=3,f(2)=[1,e−2]≈[1,0.135],ℓ(2)≈1.135
合并:
mnew=max(4,3)=4
ℓnew=e4−4×1.135+e3−4×1.135=1.135+0.135×1.135≈1.135+0.153=1.288
等等——这和标准 softmax 的 ℓ≈1.553 不一致?让我重新检查。
实际上 ℓ(2) 应该用 m(2)=3 来算:
ℓ(2)=e3−3+e1−3=1+e−2≈1.135
合并时:
ℓnew=em(1)−mnew⋅ℓ(1)+em(2)−mnew⋅ℓ(2)
=e4−4×1.135+e3−4×1.135=1.135+0.368×1.135≈1.135+0.418=1.553
与标准 softmax 的 ℓ≈1.553 完全一致! ✓
最终归一化:
softmax(x)=ℓem(1)−m⋅f(1)∥ℓem(2)−m⋅f(2)
第一块:1.553[0.135,1]≈[0.087,0.644]
第二块:1.553e−1×[1,0.135]=1.553[0.368,0.050]≈[0.237,0.032]
合并结果:[0.087,0.644,0.237,0.032],与标准 softmax 完全一致。✓
七、Flash Attention 与相关技术的关系
7.1 与 KV Cache 的关系
KV Cache 是推理阶段的优化:缓存历史 token 的 K,V 避免重复计算。Flash Attention 是注意力计算本身的优化,两者正交。实际推理引擎中,Flash Attention 直接操作 KV Cache 中的数据——分块读取 KV Cache 的列块,在 SRAM 中完成注意力计算。
7.2 与 Paged Attention 的关系
Paged Attention(vLLM 中的核心优化)将 KV Cache 按固定大小的"页"管理,类似操作系统的虚拟内存分页。Flash Attention 的分块计算天然适配分页 KV Cache:每个 KV 页就是一个 Bc 大小的列块,内层循环逐页读取。vLLM 的实现正是将两者结合——PagedAttention kernel 在 Flash Attention 的分块框架内直接按页索引 KV Cache。
7.3 与 Ring Attention 的关系
当序列长度 N 超过单卡显存容量时,需要跨 GPU 分布式计算 Attention。Ring Attention 将 Q,K,V 分布在不同 GPU 上,沿环形拓扑传递 K,V 块。每张 GPU 在收到 Kj,Vj 后,用 Flash Attention 的在线 softmax 公式更新本地的 Oi 和 (mi,ℓi)。在线 softmax 的流式特性使得这个跨卡累积成为可能——如果 softmax 不是在线的,就必须等所有卡的数据到齐才能归一化,无法重叠通信和计算。
八、工程实现中的细节
8.1 数值稳定性
在线 softmax 的每一步都减去当前最大值 m,保证指数运算的输入 ≤0,避免 ex 溢出。这与标准 softmax 的 max-shifting 技巧相同,但 Flash Attention 中 m 是动态更新的,需要确保合并时的缩放因子 emold−mnew 不会下溢。当 mnew≫mold 时,emold−mnew 趋近于 0,对应的旧块贡献被正确丢弃——这在数学上是正确的(新块中存在远更大的值,旧块的注意力权重本就趋近于零)。
8.2 FP16/BF16 支持
实际训练中通常使用 FP16 或 BF16。Flash Attention 的中间累加在 FP32 中进行(SRAM 内的 Oi、ℓi、mi 都是 FP32),只有 HBM 中的 Q,K,V,O 是低精度。这避免了低精度累加的精度损失,同时保持低精度存储的带宽优势。
8.3 Causal Mask 的优化
对于因果 Attention(下三角 mask),Flash Attention 可以跳过上三角的分块。具体来说,对于行块 Qi,只需要遍历列块 Kj 中 j≤i 的部分。这减少了约一半的计算量,且不需要显式构造 mask 矩阵——mask 的效果通过"跳过分块"直接实现。
九、总结
Flash Attention 的精妙之处在于,它没有改变 Attention 的数学语义,而是通过两个核心技巧重构了计算方式:
- 分块计算(Tiling):将大矩阵乘法拆成小块,让中间结果留在 SRAM 中
- 在线 softmax(Online Softmax):用流式更新的 (m,ℓ) 两个标量替代全局归一化,使分块之间无需显式同步
两者结合,将 Attention 的 HBM 读写从 O(N2) 降到 O(N2d2/M),在不牺牲精度的前提下实现了 2-4 倍的端到端加速。更重要的是,它使得训练超长序列(如 128K token 上下文窗口)在单卡上成为可能——这不是速度优化,而是可行性优化。
从更抽象的视角看,Flash Attention 是 IO-aware algorithm design 的典范:在内存层次结构明确的硬件上,算法的 IO 复杂度而非计算复杂度才是瓶颈,重新设计算法以最小化 IO 可以获得远超"优化实现"量级的提升。这个思路不仅适用于 Attention,也启发了后续对 MLP、LayerNorm 等算子的类似优化。
评论(0)