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
2
length = tl.where(request > 0, position // 8, 0)
tl.store(Lengths + row, tl.minimum(length, WIDTH).to(tl.int32), mask)
1
2
3
indices = flashinfer.top_k_ragged_transform(
scores, offsets, lengths, 512, deterministic=True, tie_break=1,
)

各行的逻辑 ID 都从 0 起步,所以 offsets 填零。这一行只需考虑 511 个历史 ID;同批即使有一行已经写满,也按它自己的长度扫描。确定性模式会把选中的 ID 按编号排好,分数相同时按约定选较小 ID。为了让正零、负零也遵守这个约定,打分端在写分数时处理它们的位模式:

1
2
bits = score.to(tl.uint32, bitcast=True)
bits = tl.where((bits & 0x7FFFFFFF) == 0, 0, bits)

掩码只在判断时去掉符号位。对任何非零输入,写回的仍是原来的 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
2
3
logical = result.to(tl.int64) * 8
physical = tl.load(Mapping + request * MAP_STRIDE + logical, active, other=0).to(tl.int64)
value = ((physical // 8) << 32) | logical

这里直接使用刚选出的 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

Step-5 区域选择:只剩 511 项有效历史时,top-k 为什么反而最慢
https://dingfen.github.io/2026/11/22/2026-11-22-Step5-ppu03/
作者
Bill Ding
发布于
2026年11月22日
更新于
2026年11月22日
许可协议