w wyl123ly 的博客
MD

自回归解码与prefill-decode

23 KB 2026.10.22 原文件

自回归解码与prefill-decode

定义

自回归解码(autoregressive decoding)是在给定前缀的条件下,按链式法则把序列的联合概率分解为逐位置条件概率的乘积,并逐位置采样或取最大概率 token 的生成方式:

其中 是第 个位置的 token, 是它的前缀, 是序列长度, 是模型参数。预填充(prefill)是把长度为 的提示一次性送入模型、并行算出所有位置隐状态并只取最后一个位置 logits 的前向过程;解码(decode)是在预填充之后每次只送入一个新 token、复用缓存并产出一个新 token 的串行过程。

符号在全文保持一致。

符号含义单位
提示 token 数,决定 prefill 的序列长度个
生成的 token 数个
词表大小,nanochat 为 32768个
Transformer 层数层
查询头数个
KV 头数,nanochat 中等于查询头数个
单头维度,nanochat 固定为 128维
缓存元素的字节数,bf16 为 2字节
参与矩阵乘的参数个数,num_matmul_params() 的返回值个
权重按存储 dtype 计的字节数字节
上下文长度为 时单行 decode 读取的 KV 缓存字节数字节
解码批大小,即同时推进的序列数条
GPU 峰值显存带宽字节/秒
GPU 峰值浮点算力FLOP/秒

首 token 延迟(time to first token,TTFT)是从请求发出到收到第一个输出 token 的时间;每输出 token 时间(time per output token,TPOT)是解码阶段相邻两个 token 之间的时间。两者不是同一阶段的两个名字:TTFT 由 prefill、缓存分配与首次采样决定,TPOT 由每步的显存读取与批大小决定。

为什么重要

nanochat 的推理入口只有一个类 Engine,而它的全部结构都建立在「prefill 并行、decode 串行」这一区分之上:Engine.generate 先用 batch=1 对提示做一次前向,再把 KV 缓存复制成 num_samples 行,之后每一步只前向一个 token。若不理解这一区分,会把 TTFT 当成模型固有属性、把 TPOT 当成采样参数的结果,从而在错误的维度上调优。

这一区分直接决定三个工程结论。第一,交互式场景的体验由 TTFT 与 TPOT 共同决定:长提示抬高 TTFT,长回答抬高总时延,而两者可用不同的手段优化(提示裁剪与 chunked prefill 对前者有效,批处理与权重量化对后者有效)。第二,decode 每步必须重新读取全部权重,batch=1 时 GPU 算力大量空闲,吞吐的下界由显存带宽而非算力给出;只有把多条序列放进同一批,权重读取才被摊薄。第三,scripts/infer_bench.py 把推理代价本身当作一种评测:CORE 只说明模型是否聪明,TTFT、TPOT、tok/s、MBU 才说明运行它要付多少成本;架构层面的 GQA、sliding window 等选择会直接出现在这些数字上。

在「懂原理、能复现、懂工程」三项中,本篇对应第一项的分解与第二项的生成器协议:能写出概率分解与 roofline 下界,能读懂 Engine.generate 的每一次 yield 对应哪一步计算;第三项的成本换算留给 部署与成本。

原理与推导

1 自回归分解与训练目标的对应

给定长度为 的序列,模型在位置 输出词表上的 logits 向量 ,经 softmax 得到条件分布

训练时整条序列一次前向,所有位置的 logits 同时得到,损失是各位置交叉熵的均值:

推理时没有真实的后继 token,必须从分布中取出一个再喂回模型,这就是「自回归」的操作含义。训练可以并行、推理必须串行,并非实现差异,而是由「第 步的输入包含第 步的输出」这一数据依赖决定的。

采样温度 把 logits 缩放后再归一化:

时分布收敛到 argmax, 越大分布越平坦。温度不改变模型参数,只改变从同一分布中取样的规则。

2 prefill 的并行性

因果掩码保证位置 只能看到 及之前的位置,因此一次前向可以同时算出所有位置的隐状态:第 行的注意力只使用前 个键值,不会读到未来信息。这正是训练与 prefill 共用的计算形式。生成长度为 的提示时,只有最后一个位置的 logits 被用于采样第一个新 token,其余位置的 logits 被丢弃,但它们的计算并不浪费:它们填充了 KV 缓存,后续 decode 直接读取。

单次 prefill 的浮点运算量为

其中 , 是第 层的注意力窗口(全窗口层为 sequence_len,短窗口层为 512)。第一项是全部矩阵乘对 个 token 的贡献,第二项是每层因果注意力的打分与加权求和:前 个位置沿对角线逐步增长,之后每个位置固定看 个键。GPT.estimate_prefill_flops 逐层累加这一项,GPT.estimate_decode_flops 则把 换成 1。

prefill 的算术强度约为 ,随提示长度线性增长。H100 的算力带宽比约为 FLOP/字节;把 KV 写入计入字节后,d24 的 prefill 在 超过约 750 时进入算力受限区。d24 在 时约需 TFLOP,按 40% MFU 计约 8.0 ms; 时约 TFLOP,约 7.0 ms。这些是纯计算的 lower bound,实际 TTFT 还要加上缓存分配、首次采样与调度开销。

3 decode 的串行性与 roofline

decode 的第 步只送入一个 token(每行一个),矩阵乘退化为矩阵-向量乘。单步浮点运算量为

单步必须从显存读取的字节数为

其中 , 是缓存元素字节数, 是 KV 头数。d24、bf16、 时 字节, 字节, FLOP。batch=1 的算术强度为

比 H100 的拐点 295 低约三个数量级,因此 decode 是显存带宽受限(memory-bandwidth-bound)的。单步时间的下界为

在 batch 较小时第二项远小于第一项,时间几乎完全由第一项决定;batch 增大后第一项中的 线性增长,而 只读一次,于是吞吐

先随 近似线性上升,随后趋于饱和值 。两项相等的位置在 ,d24 在 2048 上下文下 。这把「为什么 decode 要 batch」变成了一个可计算的量:batch 小于 时增加批大小几乎免费,大于 后新增的读取主要来自 KV 缓存,吞吐增益递减。

TTFT 与 TPOT 的定义可以写成

其中 是排队时间, 包含缓存复制与第一次采样。scripts/infer_bench.py 用第一次 next(generator) 的耗时作为 TTFT,用后续每次 next 的中位数作为 TPOT,正是这两个定义在代码里的落地。

4 采样:temperature、top-k 与 argmax

给定 logits ,Engine 调用的 sample_next_token 分三条路径。

第一,:直接 torch.argmax,完全确定,与随机数生成器无关。

第二, 且给出 :先取 logits 最大的 个值及其索引,把候选集合 之外的概率置零,再在 上归一化:

第三, 且 为空或 0:在完整词表上做带温度的 softmax 后采样。

sample_next_token 的实际顺序是「先 top-k、后除温度、再 softmax、最后 torch.multinomial」。由于 top-k 只依赖 logits 的相对大小,先选集合再缩放与先缩放再选集合得到同一个集合,因此这一顺序不影响分布。top_k=1 时退化为 argmax;temperature=0 时无论 top_k 为何都走 argmax 分支。随机数生成器在每次 Engine.generate 内用 seed 初始化,因此同一提示、同一参数、同一 seed 的结果可复现;不同行共享同一个生成器,但每步按行采样,行与行之间仍独立。

5 Engine.generate 的生成器协议

Engine.generate 是一个生成器,而不是一次性返回结果的函数。调用它只创建生成器对象;第一次 next() 才执行预填充并产出第一列 token。每一列是一个长度为 num_samples 的列表,同时返回同长度的 mask 列表:采样得到的 token 记 1,被强制注入的 token 记 0。协议可以拆成七步。

  1. 分配 batch=1 的 KVCache,形状 (L, 1, T_p, H_{kv}, D),对提示做一次前向,取最后位置的 logits 并 expand 到 num_samples 行。
  2. 分配 batch=num_samples 的解码缓存,KVCache.prefill 把提示的 K/V 与 prev_embedding 复制到每一行,随后删除预填充缓存。
  3. 为每一行建立 RowState,保存当前 token 序列、待强制注入的 token 队列、是否处于 Python 块、表达式 token 与完成标记。
  4. 每步先检查 max_tokens 与「所有行完成」两个终止条件,再用 sample_next_token 对每行采样一个 token。
  5. 逐行决定实际写入的 token:若该行有强制 token,从队列弹出并记 mask=0;否则用采样值并记 mask=1。随后更新 current_tokens、完成标记与工具状态机。
  6. yield token_column, token_masks。
  7. 消费者再次 next() 时,把这一列 token 作为输入做一次前向,得到下一步 logits,回到第 4 步。

第 6 步与第 7 步的顺序有一个容易忽略的后果:第一次 next() 只包含预填充与第一次采样,不包含第一个新 token 的前向;而最后一次 yield 之后,生成器还会再做一次前向,才在循环顶部因 max_tokens 退出。这次前向的结果没有被使用,它会发生在 StopIteration 之前,因此不被 infer_bench 计入 step time。generate_batch 在 all(completed) 时提前 break,避免继续消耗;infer_bench 的 num_steps 等于 decode_tokens - 1 则是另一个原因:第一个 token 已经被计入 TTFT。

6 与朴素 GPT.generate 的等价性

GPT.generate 是参考实现:batch 固定为 1,每一步把完整前缀重新送入模型,不带缓存,按 temperature 与 top_k 采样或 argmax,逐个 yield 整数。Engine.generate 用缓存避免重算,但数学上应对同一提示、同一温度给出相同分布;在 temperature=0 时两者都退化为 argmax,因此逐 token 应完全一致。

等价性检查写在 nanochat/engine.py 的 __main__ 块,而不是 pytest:它加载 base 检查点,用提示 "The chemical formula of water is"、max_tokens=64、temperature=0.0 分别跑 model.generate 与 Engine.generate,收集 token 列表后逐位比较,最后打印 Match: True/False。这段代码需要真实检查点(通常需要 GPU),因此没有进入单元测试。

tests/test_engine.py 用 Mock 模型验证的是协议性质,不是数值等价:MockModel.forward 返回全零 logits,因此温度大于 0 时各行应采到不同 token。test_multi_sample_first_token_diversity 用 16 个样本、262 词表,断言首 token 不全相同;若实现把预填充 logits 只采样一次再广播,全相同的概率约 ,测试会失败。test_seed_reproducibility 断言同 seed 三次结果一致,test_temperature_zero_determinism 断言 时不同 seed 结果一致,test_max_tokens_respected 断言生成长度不超过上限,test_num_samples_count 断言行数等于 num_samples,test_different_seeds_introduce_variation_when_temperature_nonzero 断言不同 seed 在 时产生变化。test_kv_cache_basic 与 test_kv_cache_prefill 另外验证缓存形状、advance、reset 与 prefill 的复制。

温度大于 0 时不能用逐 token 比较做等价性检查:Engine 一步为 行各取一个随机数,朴素实现对每步只取一个,随机数消耗序列不同,即使分布相同也会得到不同样本。因此仓库只在 下比较。

在 nanochat 中的落地

位置作用关键细节
nanochat/gpt.py 的 forward单次前向kv_cache 为空时训练/朴素生成;非空时把当前 K/V 写入缓存,并在最后一层推进 cache_seqlens
nanochat/engine.py 的 sample_next_token单步采样三条路径:argmax、top-k、全词表;temperature 必须非负
nanochat/engine.py 的 KVCache缓存容器(L, B, T, H_{kv}, D),int32 的 cache_seqlens,prefill 复制提示缓存
nanochat/engine.py 的 Engine.generate流式生成预填充→复制缓存→逐步采样→工具状态机→yield 两列
nanochat/engine.py 的 Engine.generate_batch非流式生成过滤终止 token,返回 token 序列与 mask,全行完成时提前退出
nanochat/gpt.py 的 estimate_prefill_flops、estimate_decode_flops架构级成本核算按窗口逐层累加注意力 FLOPs,矩阵乘按 计
scripts/infer_bench.py 的 bench_generate实测第一次 next 计 TTFT,后续 next 计 step time,读峰值显存

Engine.generate 不保存跨调用的缓存:每次调用都重新分配 KVCache 并重新预填充。对话场景的每一轮都把完整历史重新送入模型,单轮成本随历史长度增长,累计成本约为轮数的二次函数;这也是 CLI与WebUI 中 Web 服务需要显式管理会话状态的根源。

关键直觉

机制性直觉

prefill 与 decode 不是两种模型,而是同一前向在序列维上的两种并行度:prefill 让 个位置同时计算,用算力换 TTFT;decode 每次只算 1 个位置,用带宽换 TPOT。权重字节 在 decode 的每一步都要重读一次,batch 的唯一作用是把这一次读取摊到 行上,因此吞吐的上界是「带宽除以每行必须搬的字节」,而不是「算力除以每 token FLOPs」。

这一直觉与严格定义的关系:TTFT 的定义包含排队与首次采样,因此它不等于 ,只是以 prefill 为主;TPOT 是相邻 token 时间的中位数,因此它不等于单步理论下界,只在该下界之上浮动。把直觉当作近似,把定义当作口径,两者不能互相替代。

例子与代码

例 1:观察 sample_next_token 的三条路径

import torch
from nanochat.engine import sample_next_token

logits = torch.tensor([[0.0, 1.0, 2.0, 3.0, 4.0]])  # (B=1, V=5)
rng = torch.Generator(device="cpu")

rng.manual_seed(0)
print(sample_next_token(logits, rng, temperature=0.0))            # tensor([[4]]):argmax
rng.manual_seed(0)
print(sample_next_token(logits, rng, temperature=0.5, top_k=2))   # tensor([[4]]):只在 [3,4] 中采样
rng.manual_seed(2)
print(sample_next_token(logits, rng, temperature=0.5, top_k=2))   # tensor([[3]])
rng.manual_seed(0)
print(sample_next_token(logits, rng, temperature=1.0, top_k=1))   # tensor([[4]]):top-1 等于贪心

前三行说明 temperature=0 与 top_k 的边界: 时 top_k 被忽略; 且 时 token 0、1、2 的概率被截断为零,无论采样多少次都不会出现。最后一行说明 top_k=1 与 argmax 等价。注意 sample_next_token 的返回值形状是 (B, 1),而 Engine.generate 把它转成 Python 列表后按行处理。

例 2:十行 decode 循环

decode_loop(prompt, max_new):
    cache = allocate_cache(batch=1, length=len(prompt) + max_new)
    logits = forward(prompt, cache)[-1]      # 一次并行前向,写满提示的 KV
    out = []
    for step in range(max_new):
        next_id = argmax(logits) if temperature == 0 else sample(logits, temperature, top_k)
        out.append(next_id)
        if next_id in (assistant_end, bos): break
        logits = forward([next_id], cache)[-1]  # 单 token 前向,读历史缓存
    return out

这十行对应 Engine.generate 去掉工具状态机、批复制与流式 yield 后的骨架。forward(prompt, cache) 这一行是 prefill;forward([next_id], cache) 这一行是 decode。把后者换成 forward(out, cache=None) 就得到朴素实现,其累计计算量从 退回 ,这是 KV Cache原理 的主题。

例 3:一次 TTFT 与 TPOT 计算

P_MM = 729_810_648          # d24 的 num_matmul_params()
W = 4_227_865_640           # 权重按存储 dtype 计的字节数
KV_READ_1920 = 127_401_984  # KVCache 在 1920 上下文下单行读取字节
F_DEC_1920 = 1_587_023_280  # 单步 decode FLOPs
F_PREFILL_1792 = 2_761_865_809_920
BW, PEAK = 3.35e12, 989e12  # H100 SXM
MFU, MBU, B = 0.4, 0.6, 8

ttft = F_PREFILL_1792 / (MFU * PEAK)
tpot = (W + B * KV_READ_1920) / (MBU * BW)
print(f"TTFT lower bound: {ttft*1e3:.1f} ms")        # 7.0 ms
print(f"TPOT at B=8: {tpot*1e3:.2f} ms")             # 2.61 ms
print(f"throughput: {B/tpot:,.0f} tok/s")            # 3065 tok/s

预期输出为 TTFT lower bound: 7.0 ms、TPOT at B=8: 2.61 ms、throughput: 3,065 tok/s。这组数对应 infer_bench 的默认设置:--prompt-tokens=2048 会被夹到 sequence_len - decode_tokens = 1792,--decode-tokens=256,代表上下文取 1792 + 256//2 = 1920。7.0 ms 是纯 prefill 在 40% MFU 下的下界,实测 TTFT 还要叠加缓存复制、首次采样与 Python 开销;2.61 ms 是 batch=8 在 60% MBU 下的下界。

易错点

常见错误

1. 把 TTFT 等同于 prefill 时间,或用平均 step time 代替 TPOT。infer_bench 的 TTFT 是第一次 next() 的墙钟时间,包含预填充、缓存复制与首次采样;TPOT 取排序后的中位数,平均值会被个别抢占或同步停顿的步拉高。

2. 认为某一行完成后它就不再计算,或把 max_tokens 当成每行独立预算。生成循环只在所有行完成或达到共享的 max_tokens 时退出;单行完成后仍会在后续步骤被采样,只是 generate_batch 在收集结果时丢弃这些 token。

3. 用 temperature>0 的输出做逐 token 等价性比较。两步的随机数消耗不同,分布相同也会得到不同样本;engine.py 的等价性检查固定 temperature=0.0 正是这个原因。

4. 把源码注释当成常量。gpt.py 的 _compute_window_sizes 注释写 2048 -> 768,但表达式 -(-2048 // 4 // 128) * 128 实际得到 512;以表达式为准。dev/LOG.md 2026-01-11 的条目写 sequence_len // 2,那是更早版本的口径。

5. 把 num_steps 当成生成的 token 数。infer_bench 的第一次 next() 只计 TTFT,因此扫描表的 steps 通常为 decode_tokens - 1;额外那次未被使用的前向发生在 StopIteration 之前,不计入步时。

6. 忘记生成器需要显式关闭。服务端在客户端断开时若只 break 而不调用 generator.close(),解码缓存与生成器栈帧会延迟到垃圾回收才释放,显存峰值按并发请求数叠加。

关联笔记

  • 前置:KV Cache原理 —— 本篇的 decode 每步读取的 由缓存结构定义;缓存形状、字节公式与 prefill 复制均在该篇,本篇不再重复。
  • 对照:自回归生成与采样 —— 跨库笔记给出温度、top-k、top-p 与重复惩罚的通用形式,本篇只保留 nanochat 实际实现的三条路径。
  • 后续:工具调用与Python沙箱 —— 本篇只提到 yield 的 mask,那篇展开 in_python_block 与强制 token 的三态状态机。
  • 后续:部署与成本 —— TTFT 与 TPOT 进入显存预算、batch 选择与每百万 token 成本。
  • 跨库:模型推理优化 —— 通用原理(量化、连续批处理、KV 分页)见该篇,本篇只讲 nanochat 的落地与 roofline 数字。

达标检测

  • [ ] 能写出自回归分解式,并说明为什么训练可以并行而推理必须串行。
  • [ ] 能写出 prefill 与 decode 的 FLOPs 公式,并解释 estimate_prefill_flops 中 的来源。
  • [ ] 能在给定 、、、 时算出单步时间下界与 tok/s 上界,并判断处于带宽受限还是算力受限。
  • [ ] 能解释 的含义,并算出 d24、2048 上下文下的 。
  • [ ] 能说明 sample_next_token 三条路径的触发条件,以及为什么先 top-k 后除温度不改变分布。
  • [ ] 能复述 Engine.generate 七步协议中的第 1、2、6、7 步,并指出第一次与最后一次 next() 各做了什么。
  • [ ] 能说明 tests/test_engine.py 的八个测试各防止哪一种回归,以及为什么数值等价性检查不在 pytest 里。
  • [ ] 能用 infer_bench 的默认参数手算一次 TTFT 与 TPOT,并指出 7.0 ms 与实测值的差距来自哪些环节。

参考来源

  • Vaswani et al., Attention Is All You Need, arXiv:1706.03762 —— 缩放点积注意力与因果掩码的定义,对应本篇 prefill 并行性的前提。
  • Dao et al., FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision, arXiv:2407.08608 —— decode 阶段 KV 缓存原地更新与窗口注意力的实现背景,对应 roofline 讨论。
  • Karpathy, nanochat(commit 92d63d4),nanochat/engine.py、nanochat/gpt.py、scripts/infer_bench.py —— 本篇全部函数名、默认值与数字的事实来源。
  • PyTorch 文档, torch.multinomial 与 torch.inference_mode —— 采样与推理模式的行为说明,对应 sample_next_token 与 Engine.generate 的实现。
  • Karpathy, nanochat dev/LOG.md(2026-01-11 Sliding Window Attention 条目)—— 窗口模式的早期口径与当前代码的版本差异。