论文:FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness,Dao 等,2022。
论文的核心观点很简单:
Attention 慢,不仅因为浮点运算多,也因为在 GPU 各级内存之间搬运了太多数据。
FlashAttention 保持精确 Softmax attention 的数学计算,但改变计算顺序:不在 HBM 中物化完整注意力矩阵,而是逐 tile 计算,将临时值保留在片上。
标准注意力
对于单个注意力头:
其中:
- :query。
- :key。
- :value。
- :序列长度。
- :头维度。
问题在于中间矩阵:
长序列下, 非常大。标准实现将 写到 HBM,为 Softmax 读回,再将 写到 HBM,最后读回 与 相乘。
因此 GPU 花了大量时间搬运中间矩阵。
内存层次
论文关注三个层次:
- 片上 SRAM:容量小、速度快。
- GPU HBM:容量大,慢于 SRAM。
- CPU DRAM:容量更大,对 GPU kernel 而言更慢。
关键差距在 SRAM 和 HBM 之间。SRAM 很快,但容不下完整的 注意力矩阵;HBM 放得下,但读写昂贵。
所以目标是:
尽量减少 HBM 读写。
这就是论文所谓的 IO 感知:算法设计不仅考虑浮点运算,也围绕数据搬运展开。
为什么精确注意力可以流式计算?
起初,Softmax 看起来需要 的完整一行:
为保证数值稳定,通常减去行最大值:
其中:
似乎必须看过全部分数才能计算最终输出。FlashAttention 使用在线 Softmax,避免保存每个分数。
每行维护两个运行值:
- :当前最大分数。
- :当前 Softmax 分母。
新分数块到来时,计算:
旧分母以 缩放,新分母必须采用 ,因此先重新缩放旧值:
这是关键修正项。新块出现更大最大值时,旧部分和相应缩小。
输出累加器同样需要修正:
最后:
这样就无需保存完整的分数行或概率行。
FlashAttention 前向传播
标准实现执行:
Q, K, V are in HBM
1. compute S = QK^T
2. write S to HBM
3. read S from HBM
4. compute P = softmax(S)
5. write P to HBM
6. read P from HBM
7. compute O = PV
8. write O to HBM
FlashAttention 改为分块执行:
for each K,V tile:
load K tile into SRAM
load V tile into SRAM
for each Q tile:
load Q tile into SRAM
load current output state for this Q tile
compute score tile QK^T
update online softmax max m
update online softmax denominator l
update output accumulator O
write updated output state back to HBM
分数 tile 是临时的,只需在片上存活到在线 Softmax 状态更新完毕。
论文算法 1 在两次 tile 更新之间,为每行保存三项:
- :当前输出累加器。
- :当前 Softmax 分母。
- :当前最大值。
它不保存:
- 完整分数矩阵 。
- 完整概率矩阵 。
这就是主要的内存节省来源。
简单示例
假设一行分数被分为两块:
第 1 块:
则:
第 2 块:
新的最大值为:
旧分母以最大值 2 为基准,因此需要重新缩放:
这等于四个分数一起计算时的稳定 Softmax 分母:
所以在线 Softmax 与普通 Softmax 结果相同,却无需保留全部分数。
复杂度分析
浮点运算量
FlashAttention 与标准精确 attention 的主要数学运算相同:
论文并不声称改善稠密 attention 浮点运算量的渐进复杂度,改进的是数据搬运。
主要矩阵乘法仍然为:
- :
- :
此外,还需对 个分数执行 Softmax。只要 不特别小,主导项仍是 。
HBM 访问量
论文给出的标准 attention 访问量为:
次 HBM 访问。
项来自读写 、、、; 项来自物化注意力矩阵。
FlashAttention 将 HBM 访问量降为:
其中 是 SRAM 大小。
直观理解:
- SRAM 只能容纳有限大小的 tile。
- SRAM 更大,就能采用更大的 tile。
- tile 更大,每次加载的 、、 块可以服务更多计算。
- 重复加载更少,HBM 流量就更小。
关键比较是:
standard attention:
pays for the full N x N matrix in HBM
FlashAttention:
pays for tiled Q, K, V, O movement
avoids storing S and P
论文还证明,在如下 SRAM 大小范围内,IO 复杂度是最优的:
因此,在该范围和论文模型下,算法不仅实践中更快,其 HBM 访问量在渐进意义上也是最优的。
反向传播
训练还需要反向传播。朴素实现可能保存前向的完整注意力矩阵 供反向复用,FlashAttention 也避免了这一点。
前向只保存:
- 输出 。
- Softmax 分母统计量。
反向逐 tile 重算所需的 分数和 Softmax 概率,用额外计算换取更低内存开销。现代 GPU 上,这通常很划算,因为计算往往比 HBM 搬运便宜。为简化讨论,本文不展开反向数学推导。
块稀疏注意力
论文将思路扩展到块稀疏 attention。稠密 attention 中,每个 query token 都关注每个 key token,对应完整矩阵:
块稀疏 attention 将矩阵划分成块,部分激活、部分跳过。设块大小为 ,则注意力矩阵包含:
个块。
定义块 mask:
如果 ,整个分数块都被忽略。对于相应 tile,kernel 无需加载该 tile,也无需计算其分数。
四个块的示例:
dense mask:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
causal block mask:
1 0 0 0
1 1 0 0
1 1 1 0
1 1 1 1
local block mask:
1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1
从块粒度看,因果 attention 会屏蔽未来块,因此具有块稀疏结构;局部 attention 只关注邻近块,也具有块稀疏结构。
简化伪代码如下:
def block_sparse_flash_attention(Q, K, V, block_mask, B):
"""
Q, K, V: [N, d]
block_mask: [N / B, N / B]
block_mask[i][j] = 1 means query block i attends to key/value block j
B: block size along sequence length
"""
N, d = Q.shape
num_blocks = N // B
O = zeros_like(Q)
for q_block_id in range(num_blocks):
q_start = q_block_id * B
q_end = q_start + B
Q_block = Q[q_start:q_end]
# Online softmax state for this query block.
running_max = full([B], -inf)
running_sum = zeros([B])
output_acc = zeros([B, d])
for kv_block_id in range(num_blocks):
if block_mask[q_block_id][kv_block_id] == 0:
continue
kv_start = kv_block_id * B
kv_end = kv_start + B
K_block = K[kv_start:kv_end]
V_block = V[kv_start:kv_end]
scores = Q_block @ K_block.T
block_max = max(scores, axis=1)
new_max = maximum(running_max, block_max)
old_scale = exp(running_max - new_max)
weights = exp(scores - new_max[:, None])
running_sum = running_sum * old_scale + sum(weights, axis=1)
output_acc = output_acc * old_scale[:, None] + weights @ V_block
running_max = new_max
O[q_start:q_end] = output_acc / running_sum[:, None]
return O
关键一行为:
if block_mask[q_block_id][kv_block_id] == 0:
continue
continue 跳过整个 attention tile。其余部分仍与 FlashAttention 相同:计算分数 tile,更新在线 Softmax 状态,再丢弃分数 tile。
若 表示非零块比例,论文给出的块稀疏 FlashAttention HBM 访问量为:
时退化为稠密 FlashAttention; 时加载和计算的 tile 更少。
带来两个收益:
- 浮点运算更少,因为跳过的块不计算 。
- HBM 访问更少,因为跳过的块不加载其 tile。
代价是,除非稀疏 mask 恰好匹配模型需要的注意力模式,否则块稀疏 attention 属于近似计算。