返回关卡地图
预判 0 / 3 闯关题:0 / 3 XP 0 / 300

Level 20 | 零基础导学关卡

FlashAttention Sim

每个 Mission 先猜一猜(押个假设解锁讲解)→ 看图解原理 → 做巩固题 → 回 notebook 写代码。带着问题学,比直接读记得牢。

20_FlashAttention_Sim.ipynb FlashAttentionOnline SoftmaxTiling
先猜一猜
图解原理
巩固 + 作业
online softmax keeps per-row m and l across blocks
Mission 1 TODO 1 + 两层分块循环

先读懂函数:分块不改答案,只改计算顺序

🎯 先猜一猜(下注解锁)

代码一开始还没有读过任何 score,却要先给每行的最大值 m 一个初值。

m 为什么应该从负无穷开始,而不是从 0 开始?

先押一个假设,下面的讲解就会解锁。猜错完全没关系——带着疑问读,记得最牢。

先补的知识

  • 本 Notebook 暂时没有 Batch 和 Head 维度,q、k、v 都是 [seq_len, dim]。先把二维版本学明白,再迁移到真实多头实现。
  • Python 切片 start:start+block_size 即使越过末尾也不会报错,它会自然返回较短的最后一块。
  • FlashAttention 仍然计算精确 Attention;这里的核心是逐块读取 K/V,并且不把完整 [seq_len, seq_len] 分数矩阵长期保存下来。
  • 对每一行 query,算法只需要持续记住三个状态:当前输出 out、见过的最大值 m、指数和 l。

图解原理

先把代码当成两层翻页:外层固定一小块 Q,内层把 K/V 一块块翻完。每翻一页,就把这一页的信息并入 m、l 和 out;翻完全部 K/V 后,这块 Q 的答案就完成了。

1. 固定 Q 块一次只处理几行 query 2. 扫描 K/V 块内层循环逐块读取 3. 保存滚动状态每行只保留 out、m、l

普通写法:先造出完整分数表

Q [S,D]K^T [D,S]Scores [S,S]

序列变长时,S×S 的中间矩阵按平方增长。这里的模拟作业,就是为了理解如何避免长期保存它。

分块写法:固定 Q 块,逐块读 K/V

Q_i [Bq,D]K_j^T [D,Bk]S_ij [Bq,Bk]

每次只出现一个小分数块。数学结果没有近似,变化的是计算顺序和中间数据的生存时间。

out[seq_len, dim],每个 query 当前已经归一化的输出 m[seq_len, 1],每行目前见过的最大 score;初始值是 -inf l[seq_len, 1],以当前 m 为基准的指数和;初始值是 0 为什么是列向量[seq_len, 1] 可以沿最后一维广播到 score 块的每一列
初始化的含义比写法更重要:还没看任何 K 块,所以输出贡献和指数和都是 0;最大值设为 -inf,保证第一块中任何正常分数都能成为新最大值。

语法热身:用另一个张量练初始化、切片和最后一块

rows, width = 5, 3
x = torch.randn(rows, width)

buffer = torch.zeros((rows, width), device=x.device, dtype=x.dtype)
running_max = torch.full((rows, 1), -float('inf'), device=x.device, dtype=x.dtype)
running_sum = torch.zeros((rows, 1), device=x.device, dtype=x.dtype)

for start in range(0, rows, 3):
    chunk = x[start:start + 3]
    print(chunk.shape)  # [3, 3],然后是 [2, 3]

从例子迁移到 TODO 1

  • buffer 对应需要返回的输出状态,shape 要同时包含序列行和特征列。
  • running_maxrunning_sum 都是每个 query 一份统计量,所以第二维保留为 1。
  • devicedtype 跟随输入,可以避免 CPU/GPU 或精度不一致。
  • 不要手工补齐最后一块;Notebook 的第二个测试专门覆盖 seq_len 不能整除 block_size 的情况。

巩固一下

seq_len=5、block_size=3 时,第二个切片 q[3:6] 的 shape 是什么?

回到 notebook 的作业

这里不直接写答案。你已经拿到足够输入,最后用 notebook 的 TODO 做举一反三。

Mission 2 TODO 2 / TODO 3 / TODO 4 / TODO 5

处理一个 K/V 块:先守住 shape,再更新 m 与 l

🎯 先猜一猜(下注解锁)

固定一个有 Bq 行的 Q 块,再拿一个有 Bk 行的 K 块做点积。

S_ij = q_block @ k_block.transpose(-2, -1) 的 shape 是什么?

先押一个假设,下面的讲解就会解锁。猜错完全没关系——带着疑问读,记得最牢。

先补的知识

  • 矩阵乘法 [Bq,D] @ [D,Bk] 会得到 [Bq,Bk]:每一行属于一个 query,每一列属于当前 K 块中的一个 key。
  • q_block 已经在外层乘过 1/sqrt(dim),所以计算 S_ij 时不要再次缩放。
  • max 和 sum 都要沿最后一维做,因为 softmax 是对每个 query 的所有 key 分数归一化。
  • keepdim=True 会把结果保留为 [Bq,1],后续才能稳定地与 [Bq,Bk] 广播。

图解原理

这一阶段先不碰 V,只处理 softmax 的账本。当前块给出一组新分数;m_new 统一新旧标尺,P_ij 把当前分数换到这把标尺下,l_new 再把旧块和新块的指数贡献合起来。

张量shape每一维在说什么
q_block[Bq, D]Bq 个 query,每个 query 有 D 个特征
k_block.T[D, Bk]转置后 D 对齐做点积,Bk 成为分数列
S_ij[Bq, Bk]每个 query 对当前 Bk 个 key 的分数
m_block / m_new[Bq, 1]每个 query 只保留一个最大值
P_ij[Bq, Bk]当前块在新最大值标尺下的指数值
l_block / l_new[Bq, 1]每个 query 只保留一个指数和
1m_block = row_max(S_ij)只在当前 K 块里找每行最大值
2m_new = maximum(m_i, m_block)把旧块和当前块放到同一个新标尺
3P_ij = exp(S_ij - m_new)减去行最大值,避免 exp 溢出
4old_scale = exp(m_i - m_new)把过去保存的指数和换算到新标尺
5l_new = l_i * old_scale + sum(P_ij)旧贡献修正后,再加当前块贡献

只看一行的小例子

旧块最大值是 2,新块分数是 [4, 0],所以新最大值变成 4。

旧贡献缩放exp(2 - 4) = exp(-2),旧值整体变小 新块指数exp([4, 0] - 4) = [1, exp(-4)] 共同标尺旧块和新块现在都以 m_new=4 为基准

两个最容易漏掉的细节

q_block 已经乘过 scale,S_ij 这里只做矩阵乘法。

m_im_block 是两个同 shape 张量,要逐元素比较,使用的是 torch.maximum

语法热身:用独立矩阵练转置、逐行归约和广播

left = torch.randn(2, 3)   # [Bq=2, D=3]
right = torch.randn(4, 3)  # [Bk=4, D=3]
scores = left @ right.transpose(-2, -1)  # [2, 4]

block_max = scores.max(dim=-1, keepdim=True).values  # [2, 1]
old_max = torch.full((2, 1), -float('inf'))
new_max = torch.maximum(old_max, block_max)
weights = torch.exp(scores - new_max)               # 广播到 [2, 4]
block_sum = weights.sum(dim=-1, keepdim=True)        # [2, 1]

从例子迁移到 TODO 2-5

  • left/right/scores 分别迁移成当前 Q 块、当前 K 块和 S_ij。
  • block_max/new_max 对应局部最大值和新全局最大值。
  • weights 对应当前块的未归一化指数 P_ij;它还不是最终 softmax 概率。
  • block_sum 只是新块贡献,必须和经过 old_scale 修正的旧 l_i 合并。

巩固一下

m_block 和 l_block 为什么都要使用 keepdim=True?

回到 notebook 的作业

这里不直接写答案。你已经拿到足够输入,最后用 notebook 的 TODO 做举一反三。

Mission 3 TODO 6 + 状态更新 + 全局写回

合并输出并写回:把旧答案换到新标尺,再加入当前块

🎯 先猜一猜(下注解锁)

旧 out_i 和当前块的 P_ij @ v_block 都有 [Bq, dim] 的 shape,看起来可以直接相加。

为什么不能直接写 out_i + P_ij @ v_block?

先押一个假设,下面的讲解就会解锁。猜错完全没关系——带着疑问读,记得最牢。

先补的知识

  • out_i 保存的是已经除过 l_i 的归一化输出,不是未归一化分子。
  • 当 m 从 m_i 变成 m_new 时,旧贡献要乘 old_scale = exp(m_i - m_new)。
  • P_ij @ v_block 得到当前 K/V 块对每个 query 的新输出分子,shape 是 [Bq, dim]。
  • 一个 K/V 块处理完后要更新 m_i、l_i;内层循环结束后,再把 out_i、m_i、l_i 写回全局切片。

图解原理

把 out_i 想成旧数据的加权平均。要和新数据合并,不能直接把两个平均数相加;先用旧总权重 l_i 找回旧贡献,再按新最大值缩放,加入新块的加权和,最后除以新的总权重 l_new。

1old_numerator = out_i * l_i * old_scale从旧平均值恢复旧分子,并换到 m_new 标尺
2new_numerator = P_ij @ v_block当前块的指数权重乘 Value
3out_new = (old_numerator + new_numerator) / l_new合并分子,再除以新指数和

与 Notebook 参考公式完全等价

旧部分out_i * (l_i * old_scale / l_new) 新部分(P_ij @ v_block) / l_new 合并out_new = old_part + new_part

用第一块做自检

第一块开始时 out_i=0、l_i=0、m_i=-inf。旧部分自然为 0,只剩当前块贡献除以 l_new,这正是普通 softmax 在第一个块上的结果。

如果第一块就出现 NaN,优先检查是否先算了 l_new、分母是否为 0,以及 m_new 的 shape 是否正确。

每个 j 块后out_i 更新为合并结果 滚动状态m_i=m_new,l_i=l_new 所有 j 完成写回 out/m/l 的 i 切片
8 / 4 / block 2
检查常规分块
5 / 3 / block 3
检查不完整尾块
3 / 2 / block 1
检查逐 token 更新
测试比较的是分块结果与标准 Attention 的最大绝对误差。shape 正确但误差大,通常不是循环边界问题,而是旧贡献没有按 m_new 重缩放、scale 乘了两次,或状态更新/写回漏了一步。

语法热身:用滚动加权平均理解输出合并

# old_avg 已经是归一化平均值,old_total 是旧权重和
old_scale = torch.exp(old_max - new_max)
new_total = old_total * old_scale + block_total

old_share = old_avg * (old_total * old_scale / new_total)
new_share = block_weighted_sum / new_total
merged_avg = old_share + new_share

从例子迁移到 TODO 6 和写回

  • old_avg 对应 out_i,block_weighted_sum 对应 P_ij @ v_block。
  • 先得到新的 out_i,再把 m_i、l_i 更新为 m_new、l_new,下一轮 j 才能接着累计。
  • 内层循环结束只代表当前 Q 块完成;还要把三个局部状态写回全局的 i 切片。
  • 最后依次跑 Notebook 的三个测试,用误差和边界 case 判断是否真正等价。

巩固一下

合并新块前,为什么旧 out_i 需要带上 l_i * old_scale?

回到 notebook 的作业

这里不直接写答案。你已经拿到足够输入,最后用 notebook 的 TODO 做举一反三。

完成 3 道闯关题后,本关即算完成;作业 checklist 用来辅助你回 notebook 练习。
进度只保存在当前浏览器 localStorage,分享 HTML 不会带走你的记录。
上一关:L19 下一关:L21