Step-5 区域选择:只剩 511 项有效历史时,top-k 为什么反而最慢
Step-5 选历史区域时,为什么只剩 511 项反而最慢?
有一批 decode 输入,每行分数预留了 131080 列,却只有前 511 个历史区域有效。Step-5 最多能保留 512 个历史区域,这 511 个本来都能留下。原实验里,旧链路处理这样一批数据要 562.3 µs。有效历史增加到 513 个时,原稿测出的耗时反倒降到了约 177 µs。
这里能省三遍工作:top-k 只扫有历史的列,打分时顺手处理正负零,选完直接沿用已经排好的 ID。下游还要查 KV 页表,这一步也能并入最后一次写回。
把有效长度交给 top-k
原因藏在接口里。原先调用 FlashInfer 的普通 top-k,只传了矩阵宽度。对库来说,每一行都有 131080 个候选。后面十几万项虽然都是代表“未来”的负无穷,也要参加筛选。只有 511 个有效项时,连第 512 个名额都落进了大量同分的负无穷里。
每行到底有多长,模型早就知道。在这条路径上,一个 region 占 8 个 token,位置除以 8 就得到当前行之前的完整 region 数。新实现把它限制在矩阵宽度以内,padding 行填零,然后将这些长度传给 top_k_ragged_transform。长度直接在设备上生成,graph 重放时不必把位置读回 CPU。现在,同一行只需查看前 511 项。单看 profiler 里的 top-k kernel,耗时从 549 µs 降到 1.82 µs。生成长度、整理 ID 和写输出仍有各自的成本。
分数只写一次,选出来的 ID 只排一次
原实现还会复制整张分数表,把里面的 -0.0 统一成 +0.0。数值比较时两者相等,但这条 top-k 路径会先把浮点比特映射成整数排序键,正零和负零可能得到不同的键。同分时取哪个 region 会影响后续注意力读哪段历史,所以正负零的处理得保留。
打分 kernel 本来就要写出每个分数,在写出前检查零的位模式即可。16 行、131080 列的例子里,这样省去了读一遍又写一遍约 8.4 MB 的 FP32 矩阵。另一个可以省下的步骤在 top-k 之后。原实验使用的 FlashInfer 确定性分支已经按 region ID 升序返回结果,无效 ID 排在尾部。_pack_regions 直接消费这个顺序,单次从 6.8 µs 降到约 1.9 µs。
| 有效历史区域数 | 优化后整条 selection 的 graph 重放耗时 |
|---|---|
| 511 | 11.7 µs |
| 513 | 17.9 µs |
| 4096 | 22.3 µs |
| 131072 | 116.0 µs |
读这组数据要区分“预留宽度”和“有效长度”。两者差得越远,可以跳过的工作越多。原稿中的 48 倍来自 511 项这个特定形状。上表测的是 FlashInfer 路径。
最后一次写回,可以顺手算出物理位置
选出的 ID 还是逻辑编号。decode 还需要知道它在 KV 池里的物理位置。早期实现先把 ID 写出去,紧接着再启动一次 kernel,把同一行读回来查页表。既然 _pack_regions 此时已经拿到了 ID,就可以在同一次调用里输出两份结果。
举例说,有 511 个历史区域时,前 511 个槽放历史 ID,第 512 个槽放当前位置。有 512 个历史区域时,当前位置要写到下标 512,也就是第 513 个槽。对每个有效槽,用 region_id × 8 查到物理 token 位置,再按下游约定把物理区域和逻辑偏移打包。输出缓冲区如果比 513 更宽,多出来的槽要清成 -1,否则下一轮可能读到上一批的地址。
在另一组 decode trace 里,两次打包调用合计每层 3.97 µs,合并后为 2.27 µs。这是打包阶段单独的前后对比。仓库的选择入口、打包实现和边界测试可以对照阅读。
跟一行数据走一遍:从位置 4090 到打包地址
假设请求槽位有效,当前 token 的位置是 4090。前面已经走完 4090 // 8 = 511 个区域,历史编号为 0 到 510,当前区域编号为 511。旧入口只看到分数张量的宽度 131080。即使后面的 130569 列都写了负无穷,库仍然要考虑它们。
新入口把每行的起点和长度放在设备上的两段 int32 缓冲里。下面摘出两处相接的代码,第一段在 Triton 中生成长度,第二段由 Python 发起选择:
1 | |
1 | |
各行的逻辑 ID 都从 0 起步,所以 offsets 填零。这一行只需考虑 511 个历史 ID;同批即使有一行已经写满,也按它自己的长度扫描。确定性模式会把选中的 ID 按编号排好,分数相同时按约定选较小 ID。为了让正零、负零也遵守这个约定,打分端在写分数时处理它们的位模式:
1 | |
掩码只在判断时去掉符号位。对任何非零输入,写回的仍是原来的 bits。于是省掉整表复制后,参与排名的非零分数仍保留原样。
选好历史以后,输出还要带上当前区域。对于刚才的例子,打包 kernel 把 0 到 510 写到前 511 个槽,再把 511 写到下标 511,返回的计数是 512。若位置改为 4096,则已有 512 个历史区域,当前编号 512 要写到下标 512。主向量的 tl.arange(0, 512) 只覆盖下标 0 到 511,所以源码有一条单独的尾部写入。
后续融合又给每个有效 ID 生成一个 64 位地址。假设历史 ID 7 的首 token 在请求内偏移 56,查页表得到物理 token 位置 200,那么低 32 位存 56,高 32 位存物理区域号 25:
1 | |
这里直接使用刚选出的 result。有效条件包含 lane == count,因为该槽放当前区域。空请求的计数为零,packed 槽填 -1;当缓冲宽为 516 时,末尾下标 513 到 515 也要清理。这样下一次 graph 重放即使换成更短的请求,也不会捡到旧地址。
后来的 PPU radix 路径:能全选时,连分数也不用读
前面 11.7 µs 的实验仍然调用了 FlashInfer。后来接入 PPU radix 选择器后,可以再往前问一步:如果本行只有 511 个历史区域,512 个名额足够全选,那么无论分数是多少,历史 ID 都是 0 到 510。单线程块和 streaming 两种选择器都能直接产生这串 ID,随后照常追加当前区域。
以三个同批请求为例,假设它们分别有 511、512、513 个历史区域。前两行直接保留所有历史;第三行要从 513 个里淘汰一个,仍然需要有效分数。compact 打分处理这个混合组时,只给第三行的有效列写分。如果整组都像前两行,加载 query 和矩阵乘都可以跳过。padding 行仍由请求槽位识别,最后计数为零。
清理未来列的决定也随消费者改变。调用点使用 clear_future = not (workspace.use_cute or workspace.ppu_selector is not None)。对这里的 PPU 路径,只有实际拿到 radix workspace,才可以依赖“下游只读有效列”这件事。回退到需要完整分数表的路径时,未来列仍须初始化。短历史直出 ID 与打分端的配套修改
对应提交
| 文中改动与代码入口 | 原始提交 |
|---|---|
每行传入有效长度、写分时统一正负零、去掉 pack 的重复排序。这三项出自同一提交,含 511 项的 562.3 → 11.7 µs 基准和对照测试。看 scan_lengths、_plus_zero、_pack_regions。 |
c98eafce19 |
decode 把页表和 packed 输出传进选择调用,在同一次调用里写出物理位置,省掉独立 pack。看 select_step5_regions 的调用差异。 |
484bd782ce |