系列 《现代 LLM 结构:从 GPT-2 到今天的演进》 第 8 / 11 篇 进阶
系列总览 — 为什么这样组织、读它需要什么、读完能做什么 · 幻灯片 — 整个系列的精华,一份可分享的 deck
学习地图 — AI-Infra 工程师学习地图 第 5 / 14 个系列 · AI 算法工程师学习地图 第 6 / 12 个系列
上一篇:MTP——改训练目标而不改主干的多 token 预测下一篇:多模态:vision encoder 的算量与 image token 的 KV 代价
本篇在系列中的位置。 现代 LLM 结构系列的第八篇。《前向的算量与访存量》算出 batch 小时 decode 受带宽限制、Tensor Core 大多空闲;《MTP——改训练目标而不改主干的多 token 预测》的 MTP 模块给了一个现成的草稿来源。本篇不改结构、不改数值格式,改的是解码流程:先猜几个 token,再用一次前向验证,输出分布严格不变。LoRA 不在本系列:参数高效微调的账在《LoRA 专题》。完整地图见总纲。
《前向的算量与访存量》的「核心问题:batch 多大 decode 才 compute-bound」一章算过 decode 的账:batch 为 \(B\) 时权重 GEMM的算术强度约等于 \(B\),距 H100 的 ridge point 295 差两个数量级,每步时间被”把权重读一遍”钉在 4.8 ms 上,Tensor Core 几乎空转。《MTP》的「当投机解码的 draft」一节里,MTP 模块在训练时多预测一个 token,推理时可以丢掉——也可以留下来当”草稿”。本篇把这两件事接起来:既然多算几行几乎不花时间,能不能先猜几个 token,再用一次前向把它们全部验证掉?
投机解码(speculative decoding)就是这个想法。它不改结构、不改数值格式,只改解码流程;收益却不是无条件的。本篇要回答的核心问题是:
同一套投机解码,为什么 batch 1 时加速 2 倍,batch 64 时没有收益?1
一、总览:一个时间模型
投机解码的一轮分两段花时间:草稿模型连出 \(\gamma\) 个 token,目标模型用一次前向把它们全部验证掉;判定本身不做前向。下图把一轮的两段耗时、一轮的产出和加速比连在一起,并标出决定加速比的三个量——接受率 \(\alpha\)、草稿代价 \(c\)、验证行数 \(B(\gamma + 1)\) 与 ridge 的关系——各自从哪里进来:
%%{init: {"flowchart": {"wrappingWidth": 380}}}%%
%% 图:投机解码的时间模型:一轮的两段耗时、期望产出与决定加速比的三个量
flowchart TB
SRC["<b>草稿来源(第二章第 5 节)</b><br/>独立小模型、Medusa、EAGLE、n-gram、MTP 模块<br/>决定接受率 $$\alpha$$ 与单次代价 $$c$$"]
TM["<b>时间模型 T(m)(第一章第 2 节)</b><br/>$$T(m) = \max(\text{读一遍权重},\ 2Nm/F)$$<br/>Llama-3-8B、H100:m 小于 316 时恒为 4.8 ms"]
DR["<b>① 起草:草稿模型自回归 $$\gamma$$ 步</b><br/>耗时 $$\gamma \cdot c \cdot T(B)$$"]
VF["<b>② 验证:目标模型一次前向(第二章第 4 节)</b><br/>算 $$B(\gamma + 1)$$ 行,耗时 $$T(B(\gamma + 1))$$"]
AR["<b>③ 判定:逐个接受,首个拒绝处重采样(第二章第 2 节)</b><br/>不做前向;输出分布严格等于目标分布 $$p$$"]
OUT["<b>本轮产出(第二章第 3 节)</b><br/>1 到 $$\gamma + 1$$ 个,期望 $$\dfrac{1 - \alpha^{\gamma+1}}{1 - \alpha}$$"]
SP["<b>加速比(第二章第 3、4 节)</b><br/>$$\dfrac{\text{期望产出} \times T(B)}{\gamma c \cdot T(B) + T(B(\gamma+1))}$$<br/>• $$B(\gamma+1)$$ 在 ridge 以下:$$\alpha$$ = 0.8、$$\gamma$$ = 4、$$c$$ = 0.1 时 2.4 倍<br/>• 越过 ridge:验证变贵,最低到 0.62 倍"]
SRC -->|"$$c$$"| DR
SRC -. "$$\alpha$$" .-> AR
TM -. "决定两段各花多久" .-> VF
DR -->|"$$\gamma$$ 个草稿 token 与各步的草稿分布 $$q$$"| VF
VF -->|"$$\gamma + 1$$ 个位置的目标分布 $$p$$"| AR
AR --> OUT
OUT --> SP
OUT -->|"KV 截到被接受的前缀,进入下一轮"| DR
classDef draft fill:#fdebd0,stroke:#b9770e;
classDef target fill:#d6eaf8,stroke:#2e6da4;
classDef res fill:#d5f5e3,stroke:#1e8449;
class SRC,DR draft;
class TM,VF target;
class OUT,SP res;
- 草稿来源:草稿可以是一个独立小模型,也可以是挂在目标模型上的几个头、一层 Transformer、上下文里的 n-gram 或 MTP 模块。它们的区别归结为两个数:单个位置的接受率 \(\alpha\),草稿一次前向相对目标一次前向的代价 \(c\)(第二章第 5 节)。
- 时间模型 T(m):一次前向处理 \(m\) 行的时间下界,取”把权重读一遍”与”把 FLOPs 算完”的较大者。\(m\) 小于 316 时它是常数 4.8 ms,多算几行不多花时间(本章第 2 节)。
- ① 起草:草稿模型自回归 \(\gamma\) 步,每步的代价是目标前向的 \(c\) 倍,合计 \(\gamma \cdot c \cdot T(B)\)。这段时间不论草稿最后被接受几个都要花。
- ② 验证:目标模型对”前缀 + \(\gamma\) 个草稿”做一次前向,一次得到 \(\gamma + 1\) 个位置的分布。行数从 \(B\) 变成 \(B(\gamma + 1)\),权重仍只读一遍;它是否仍然只花 \(T(B)\),取决于 \(B(\gamma + 1)\) 有没有越过 ridge(第二章第 4 节)。
- ③ 判定:从第 1 个草稿起,以概率 \(\min(1, p/q)\) 接受;第一次拒绝时从残差分布重采样一个 token,本轮结束。这一步只是在已有的 \(p\)、\(q\) 上做比较与采样,不做前向,并且保证输出分布与不投机时相同(第二章第 2 节)。
- 本轮产出:最少 1 个(第 1 个草稿就被拒),最多 \(\gamma + 1\) 个(全接受再加一个)。\(\alpha\) = 0.8、\(\gamma\) = 4 时期望 3.36 个(第二章第 3 节)。
- 加速比:同样的产出,普通 decode 要花”期望产出 × \(T(B)\)“,投机解码花”起草 + 验证”。小 batch 下验证与一次普通前向同价,加速 2.4 倍;batch 大到 \(B(\gamma + 1)\) 越过 ridge,分母里的验证项成倍增长,加速比降到 1 以下。
一轮里先后出现六样东西。它们何时产生、存在哪里、被拒绝之后怎么处理,各不相同:
| 对象 | 何时产生 | 存在哪里 | 活多久,被拒后怎么处理 |
|---|---|---|---|
| 草稿 token \(x_1, \ldots, x_\gamma\) | 起草阶段,草稿模型逐个采样 | 暂接在这个请求的 token 序列末尾 |
|
| 草稿分布 \(q_1, \ldots, q_\gamma\) | 起草的每一步,草稿模型在词表上的输出 | 每个位置一行概率,留到判定 |
|
| 目标分布 \(p_1, \ldots, p_{\gamma+1}\) | 验证前向,一次全部算出 | 每个位置一行概率 | 判定用完即丢,不跨轮 |
| 重采样 token 或 bonus token | 判定阶段:首次拒绝时从残差分布抽,或全接受后从 \(p_{\gamma+1}\) 抽 | 接在被接受的草稿之后,成为正式输出 | 每轮恰好一个;它的 KV 要到下一轮验证前向才算 |
| 目标模型的 KV | 验证前向为输入的 \(\gamma + 1\) 个位置各算一份 | 这个请求的 KV cache;要为草稿多留 \(\gamma\) 个位置的空间 |
|
| 草稿模型的权重与 KV(草稿是独立小模型时) | 权重常驻;KV 在起草的每一步追加 | 同一张卡的显存,草稿模型自己的一份 KV cache |
|
1. 本文的路线
- 先把《前向的算量与访存量》的 Roofline 压成一个时间模型(本章第 2 节),后面所有估算都用它。
- 再讲投机解码本身(第二章):算法与”输出分布严格不变”的证明、期望接受数与加速比、验证多个 token 为什么几乎免费又何时不再免费、草稿从哪里来。
- 最后把它加进
llm_cost.py,合成文本模型的成本表(第三章)。
2. 一个时间模型
一次前向处理 \(m\) 个 token 行,时间下界是访存时间与计算时间的较大者:
\[T(m) = \max\left( \frac{W_{\text{bytes}}}{BW},\ \frac{2 N m}{F} \right)\]其中 \(W_{\text{bytes}}\) 是要读的权重字节数,\(N\) 是参与 GEMM 的参数量(embedding 是查表,不算),\(F\) 是算力。代入 Llama-3-8B(8.03B 参数,BF16 权重 16.06 GB,每 token 权重 FLOPs 约 15.0 GFLOPs):
\[T_{\text{mem}} = \frac{16.06 \ \text{GB}}{3.35 \ \text{TB/s}} \approx 4.8 \ \text{ms}, \qquad T_{\text{cmp}}(m) = m \times \frac{15.0 \ \text{GFLOPs}}{989 \ \text{TFLOPS}} \approx m \times 15.2 \ \mu\text{s}\]两者相等在 \(m \approx 316\),与 ridge 295 同一量级(差别来自 16.06 GB 包含了 embedding 而 15.0 GFLOPs 不含)。这个模型忽略了 KV cache 读取、activations 与 kernel 效率,是理论下界,不是任何实现的实测。\(m < 316\) 时 \(T(m)\) 是常数——多算几行不多花时间,这就是投机解码的全部空间。
3. 本文的章节安排
| 章 | 主题 | 内容 |
|---|---|---|
| 二 | 投机解码:改变 m | 分布等式、期望接受数与加速比、验证 γ+1 个 token 何时免费、草稿从哪里来 |
| 三 | 实践 | 脚本新增的函数、文本模型的成本表 |
| 四 | 本文小结 | |
| 五 | 自测 | 5 道题 |
二、投机解码:改变 m
1. 问题:一次前向只产出一个 token
decode 每步读 16 GB 权重、产出 \(B\) 个 token。\(B = 1\) 时,4.8 ms 里 Tensor Core 只做了 15 GFLOPs,利用率约 0.3%。第一章的时间模型说:在斜线上,多算几行几乎不多花时间——\(T(m)\) 在 \(m < 316\) 时是常数。如果能一次前向验证多个候选 token,就把串行的产出变成了并行的验证。
问题是候选从哪里来,以及怎么保证结果与原模型一致。
2. 算法与分布等式
记目标模型的分布为 \(p(\cdot \mid \text{prefix})\),一个便宜的草稿模型的分布为 \(q(\cdot \mid \text{prefix})\)。投机解码(Leviathan 等 2023;Chen 等 2023)一轮做四件事:
- 草稿模型自回归采样 \(\gamma\) 个 token \(x_1, \ldots, x_\gamma\),\(x_i \sim q(\cdot \mid \text{prefix}, x_{<i})\);
- 目标模型对 \(\text{prefix}, x_1, \ldots, x_\gamma\) 做一次前向,得到 \(\gamma + 1\) 个位置的分布 \(p_1, \ldots, p_{\gamma+1}\);
- 从 \(i = 1\) 起逐个判定:以概率 \(\min(1, p_i(x_i) / q_i(x_i))\) 接受 \(x_i\);一旦拒绝,从修正分布 \(\text{norm}(\max(0, p_i - q_i))\) 采样一个 token 替代 \(x_i\),本轮结束;
- 若 \(\gamma\) 个全部接受,再从 \(p_{\gamma+1}\) 采样一个 token。
每轮至少产出 1 个 token(拒绝时的重采样或全接受时的额外采样),最多 \(\gamma + 1\) 个。一轮的分支与回退如下:
%% 图:投机解码的一轮:草稿模型自回归 γ 步,目标模型一次前向验证,逐位置接受或拒绝后重采样
flowchart TB
dr["<b>草稿模型自回归 $$\gamma$$ 步</b><br/>$$x_1, \ldots, x_\gamma \sim q$$,成本 $$\gamma \cdot c \cdot T(B)$$"] --> vf["<b>目标模型一次前向 $$\text{prefix}, x_1, \ldots, x_\gamma$$</b><br/>得到 $$p_1, \ldots, p_{\gamma+1}$$,成本 $$T(B(\gamma+1))$$"]
vf --> i1["i = 1"]
i1 --> acc{"以概率 $$\min(1, p_i(x_i) / q_i(x_i))$$<br/>接受 $$x_i$$?"}
acc -->|"接受"| more{"$$i = \gamma$$?"}
more -->|"否,i ← i + 1"| acc
more -->|"是,$$\gamma$$ 个全接受"| bonus["<b>从 $$p_{\gamma+1}$$ 再采样 1 个</b><br/>本轮产出 $$\gamma + 1$$ 个"]
acc -->|"拒绝"| rs["<b>从 $$\text{norm}(\max(0, p_i - q_i))$$ 重采样替代 $$x_i$$</b><br/>本轮产出 i 个"]
rs --> rb["回退:丢弃位置 i 及之后的草稿 token 与其 KV;<br/>位置 i 换成重采样的 token,<br/>它的 KV 下一轮才算"]
rb --> nx["下一轮"]
bonus --> nx
nx --> dr
classDef draft fill:#fdebd0,stroke:#b9770e;
classDef target fill:#d6eaf8,stroke:#2e6da4;
classDef ok fill:#d5f5e3,stroke:#1e8449;
classDef bad fill:#fadbd8,stroke:#c0392b;
class dr draft;
class vf target;
class bonus ok;
class rs,rb bad;
先用一个只有三个词的词表把一个位置的判定走一遍。目标模型与草稿在这个位置的分布是:
| token | 目标 \(p\) | 草稿 \(q\) | 草稿提出它的概率 | 被接受的概率 \(\min(1, p/q)\) | 接受且输出它 \(\min(p, q)\) | 残差 \(\max(0, p - q)\) |
|---|---|---|---|---|---|---|
| A | 0.5 | 0.7 | 0.7 | 0.5 / 0.7 = 0.714 | 0.5 | 0 |
| B | 0.3 | 0.2 | 0.2 | 1 | 0.2 | 0.1 |
| C | 0.2 | 0.1 | 0.1 | 1 | 0.1 | 0.1 |
| 合计 | 1 | 1 | \(\beta\) = 0.8 | \(Z\) = 0.2 |
草稿把 A 估高了(0.7 > 0.5),所以提出 A 时只以 0.714 的概率接受;B、C 估低了,提出就全收。这一步以 0.8 的概率接受草稿,以 0.2 的概率拒绝;拒绝后从残差归一化的分布 (0, 0.5, 0.5) 里重采样。逐个 token 加起来:
- 输出 A:只能来自”接受”,0.5;
- 输出 B:接受 0.2 + 拒绝后抽到 B \(0.2 \times 0.5 = 0.1\),合计 0.3;
- 输出 C:接受 0.1 + 拒绝后抽到 C 0.1,合计 0.2。
三个数正好是 \(p\) = (0.5, 0.3, 0.2)。下面把这个过程写成对任意 \(p\)、\(q\) 都成立的式子。
关键性质:输出分布严格等于 \(p\)。看单步。在某一位置,草稿提出 \(x\) 的概率是 \(q(x)\),被接受的概率是 \(\min(1, p(x)/q(x))\),所以”接受且输出 \(x\)“的概率是
\[q(x) \min\left(1, \frac{p(x)}{q(x)}\right) = \min(q(x), p(x))\]总接受概率
\[\beta = \sum_x \min(p(x), q(x))\]拒绝的概率是 \(1 - \beta\),拒绝后从 \(\text{norm}(\max(0, p - q))\) 采到 \(x\) 的概率是 \(\max(0, p(x) - q(x)) / Z\),归一化常数
\[Z = \sum_y \max(0, p(y) - q(y)) = \sum_y \left( p(y) - \min(p(y), q(y)) \right) = 1 - \beta\]于是输出 \(x\) 的总概率
\[P(x) = \min(p(x), q(x)) + (1 - \beta) \cdot \frac{\max(0, p(x) - q(x))}{1 - \beta} = \min(p(x), q(x)) + \max(0, p(x) - q(x)) = p(x)\]每个位置都从 \(p\) 采样,且被接受的 token 之后的位置以它为条件——与目标模型自回归采样的联合分布逐位相同。greedy 解码是 \(p\) 退化为 one-hot 的特例:接受当且仅当草稿与目标 argmax 一致。这个证明不依赖 \(q\) 是什么——\(q\) 只影响效率,不影响正确性。
三点补充。
1、残差分布的含义。 拒绝后的重采样分布 \(\text{norm}(\max(0, p - q))\) 只在 \(p(x) > q(x)\) 的 token 上有质量,即”目标模型认为比草稿更可能”的那些 token——草稿高估的 token 已经被接受步骤按 \(p/q\) 的比例采纳过了,剩下的概率质量正好是目标模型比草稿多出来的部分。
2、\(\gamma + 1\) 个分布为什么只要一次前向。 因果掩码下每个位置的输出只依赖它之前的 token,草稿序列的每个前缀恰好对应一个位置——这与 prefill 一次算出整个 prompt 所有位置的 KV 是同一件事,投机解码的验证本质上是一次长度为 \(\gamma + 1\) 的小 prefill。
3、KV cache 的回退要精确到位置。 被拒绝的位置 \(i\) 本身的 KV 是按草稿 token \(x_i\) 算的,也要丢掉(或覆盖),保留到 \(i - 1\);重采样出的新 token 占据位置 \(i\),它的 KV 在下一轮验证前向里才会算出来;全接受时的 bonus token 同理。用 \(\gamma = 4\)、前缀已有 100 个 token(位置 0–99,位置 99 是上一轮刚产出、KV 还没算的那个)、第 3 个草稿被拒绝为例:
| 位置 | 99 | 100 | 101 | 102 | 103 |
|---|---|---|---|---|---|
| 验证前向的输入 | 上一轮产出的 token | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) |
| 这个位置输出的分布用来判定 | \(x_1\)(\(p_1\)) | \(x_2\)(\(p_2\)) | \(x_3\)(\(p_3\)) | \(x_4\)(\(p_4\)) | bonus(\(p_5\)) |
| 判定结果 | 接受 \(x_1\) | 接受 \(x_2\) | 拒绝 \(x_3\),重采样得 \(y_3\) | 不再判定 | 不再判定 |
| 本轮算出的 KV | 保留 | 保留 | 保留 | 丢弃(按 \(x_3\) 算的) | 丢弃 |
这一轮产出 \(x_1, x_2, y_3\) 三个 token;KV 保留到位置 101,\(y_3\) 占据位置 102,作为下一轮验证前向的第一个输入,它的 KV 那时才算。
Java 经验参照:乐观锁的”先做、提交时校验、失败回退”
用版本号做乐观锁时,线程先不加锁把活干完,提交时比对版本号,对不上就丢掉这次结果重来。投机解码对得上的有三处:先做便宜的假设性工作(起草),在一个提交点统一校验(一次验证前向),失败只回退到最后一个有效状态(KV 截断到被接受的前缀);冲突率高时乐观锁反而更慢,对应接受率 \(\alpha\) 低时草稿白做。对不上的有两处。其一,乐观锁的校验是确定性的相等比较,这里采样解码时是以概率 \(\min(1, p/q)\) 接受,保证的是输出分布与不投机时相同,而不是与”不投机时本来会抽到的那个 token”相同(只有 greedy 解码才退化成相等比较)。其二,失败不是整体重做:被拒位置之前的草稿照常保留,被拒的位置由残差分布直接给出替代 token,每轮至少前进 1 个。
3. 期望接受数与加速比
记单个位置的接受率 \(\alpha = \mathbb{E}[\beta]\)(它等于 \(1 - \text{TV}(p, q)\),\(p\) 与 \(q\) 的总变差距离的补)。假设各位置独立且接受率相同,一轮产出的 token 数是”连续接受的个数 + 1”,期望
\[\mathbb{E}[\text{tokens}] = 1 + \alpha + \alpha^2 + \cdots + \alpha^\gamma = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}\]\(\alpha = 0.8\)、\(\gamma = 4\):\((1 - 0.8^5)/0.2 = (1 - 0.328)/0.2 = 3.36\)。这个期望可以从一轮产出几个 token 的分布直接加出来:在第 \(n + 1\) 个草稿处第一次被拒绝的概率是 \(\alpha^n (1 - \alpha)\),产出 \(n + 1\) 个;4 个全接受的概率是 \(\alpha^4\),产出 5 个(含 bonus):
| 本轮产出 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 发生的情形 | 第 1 个就被拒 | 第 2 个被拒 | 第 3 个被拒 | 第 4 个被拒 | 全接受 + bonus |
| 概率 | 0.2 | 0.16 | 0.128 | 0.1024 | 0.4096 |
| 产出 × 概率 | 0.2 | 0.32 | 0.384 | 0.4096 | 2.048 |
最后一行加起来是 3.36。最可能的情况是全接受(41%),但有 20% 的轮次只产出 1 个——这一轮的 4 次草稿白做了。
一轮的成本:\(\gamma\) 次草稿前向加一次目标前向。记草稿一次前向的时间是目标前向的 \(c\) 倍,并且——这是关键假设——目标模型验证 \(\gamma + 1\) 个 token 的时间与验证 1 个相同。那么
\[\text{speedup} = \frac{\mathbb{E}[\text{tokens}]}{\gamma c + 1}\]\(c = 0.1\):\(3.36 / 1.4 = 2.4\)。换成毫秒,用第一章 Llama-3-8B 在 H100 上 \(B = 1\) 的数(目标前向 4.79 ms,草稿一次 0.479 ms)摆在同一条时间轴上:
| 普通 decode | 投机解码一轮(\(\gamma = 4\),\(c = 0.1\)) | |
|---|---|---|
| 做了什么 | 目标模型前向 3.36 次,每次产出 1 个 | 草稿前向 4 次,再目标模型前向 1 次(验证 5 个位置) |
| 用时 | \(3.36 \times 4.79 = 16.1\) ms | \(4 \times 0.479 + 4.79 = 6.71\) ms |
| 产出(期望) | 3.36 个 | 3.36 个 |
| 每 token | 4.79 ms | 2.00 ms |
16.1 / 6.71 = 2.4,就是上面的加速比。省下来的是两次多余的”读一遍 16 GB 权重”:投机解码一轮只读一遍目标模型权重,普通 decode 要读 3.36 遍。若草稿几乎免费(\(c = 0.02\),多头或 n-gram 方案),\(3.36 / 1.08 \approx 3.1\)。
几个变体的数字:
| \(\alpha\) | \(\gamma\) | 期望产出 E[tokens] | 加速比(c = 0.1) | 加速比(c = 0.02) |
|---|---|---|---|---|
| 0.6 | 4 | 2.31 | 1.65 | 2.13 |
| 0.8 | 2 | 2.44 | 2.03 | 2.35 |
| 0.8 | 4 | 3.36 | 2.40 | 3.11 |
| 0.8 | 8 | 4.33 | 2.40 | 3.73 |
| 0.9 | 4 | 4.10 | 2.93 | 3.79 |
\(\gamma\) 越大,期望接受数增长越慢(\(\alpha^\gamma\) 衰减),而草稿成本线性增长;\(c = 0.1\) 时 \(\gamma = 4\) 与 \(\gamma = 8\) 的加速比相同(都是 2.40),最优 \(\gamma\) 由 \(\alpha\) 与 \(c\) 共同决定。
4. 为什么验证 γ+1 个 token 几乎免费——以及何时不再免费
“验证 \(\gamma + 1\) 个与验证 1 个同样贵”是 Roofline 的直接推论。目标模型的 GEMM 从 \([B, k] \times [k, n]\) 变成 \([B(\gamma + 1), k] \times [k, n]\):FLOPs 乘 \(\gamma + 1\),权重读取不变。只要 \(B(\gamma + 1)\) 仍在 ridge 之下,
\[T(B(\gamma + 1)) = T(B) = \frac{W_{\text{bytes}}}{BW}\]多出的 FLOPs 填的是本来空转的 Tensor Core。KV cache 读取也一样:验证 5 个 token 的 attention 读同一份 KV cache。
条件是 \(B(\gamma + 1) \lesssim \text{ridge}\),即
\[B \lesssim \frac{\text{ridge}}{\gamma + 1} \approx \frac{300}{5} = 60\]超过这个 batch,验证前向进入 compute-bound,\(T(B(\gamma+1))\) 开始以 \((\gamma + 1)\) 倍于 \(T(B)\) 的斜率增长。极限情况(完全 compute-bound)加速比变为
\[\frac{\mathbb{E}[\text{tokens}]}{\gamma c + (\gamma + 1)} = \frac{3.36}{0.4 + 5} \approx 0.62\]低于 1。原因很朴素:投机解码是用 FLOPs 换延迟——每产出 3.36 个 token 要为 5 个位置做完整前向,FLOPs 效率是 \(3.36/5 = 67\%\),被拒绝的 token 的计算是白做的。当 FLOPs 是瓶颈时,这笔交易亏本。
用第一章的时间模型算 Llama-3-8B 在 H100 上各 batch 的加速比(\(\alpha = 0.8\)、\(\gamma = 4\)、\(c = 0.1\),草稿成本按 \(c \cdot T(B)\) 计):
\[\text{speedup}(B) = \frac{\mathbb{E}[\text{tokens}] \cdot T(B)}{\gamma c \cdot T(B) + T(B(\gamma + 1))}\]| batch B | T(B) ms(峰值算力) | T(5B) ms(峰值算力) | 加速比(峰值算力) | 加速比(60% MFU) |
|---|---|---|---|---|
| 1 | 4.79 | 4.79 | 2.40 | 2.40 |
| 8 | 4.79 | 4.79 | 2.40 | 2.40 |
| 32 | 4.79 | 4.79 | 2.40 | 2.40 |
| 64 | 4.79 | 4.86 | 2.38 | 1.61 |
| 128 | 4.79 | 9.71 | 1.39 | 0.89 |
| 256 | 4.79 | 19.4 | 0.76 | 0.62 |
最后一列按 60% MFU折算实际可达算力(593 TFLOPS,有效 ridge 约 177,转折 batch 约 35;这一列的 \(T(B)\)、\(T(5B)\) 也按 593 TFLOPS 重算,表中未列出):\(B = 64\) 时验证前向已进入计算区,加速比掉到 1.6;\(B = 128\) 时低于 1。再算上真实系统里草稿模型在大 batch 下的开销、每轮调度与采样的固定成本、以及 \(\alpha\) 在不同位置并不独立同分布,“batch 64 时没有收益” 是这条曲线的工程表述——精确的转折位置随模型、硬件、\(\gamma\) 移动,但它的量级由 \(\text{ridge}/(\gamma + 1)\) 决定。
另一种常见的 decode 加速——weight-only 量化(把 BF16 权重压成 INT4,字节数降到四分之一;原理与方法在算法地图的《高效推理与压缩》)——与本章的数字画在同一条 \(T(m)\) 曲线上(对数坐标):量化把 memory-bound 的平台向下移,投机解码把工作点向右推,两者的收益都止于平台与斜线的交点:
INT4 在 \(B < \text{ridge}/4\) 时兑现字节收益,投机解码在 \(B < \text{ridge}/(\gamma+1)\) 时兑现并行验证的收益——两者都只在 Roofline 的斜线上有效,越过 ridge 就消失甚至反转。它们优化的是同一个量:memory-bound 区间里被浪费的算力。这也意味着两者可以叠加:W4A16 的目标模型验证 5 个 token 同样几乎免费,只是转折 batch 变成 \(\text{ridge}/(4 \times 5) \approx 15\)。
5. 草稿从哪里来
草稿方案决定 \(\alpha\) 与 \(c\)。以下区间是各论文与工程报告中通常报告的量级,不是本文实测:
| 方案 | 草稿形态 | c(相对目标一次前向) | alpha(通常报告) |
|---|---|---|---|
| 独立小模型 | 同 tokenizer 的小模型自回归 γ 步 | 参数量之比,~0.05–0.15 | 0.6–0.8(取决于配对) |
| Medusa(Cai 等 2024) | 目标模型顶层加 K 个头并行预测 t+2.. | ≈0(一次前向内) | 约 0.6(EAGLE 论文的对比数字),逐头下降 |
| EAGLE(Li 等 2024) | 一层 Transformer 在特征级自回归起草 | ~0.02–0.05 | 约 0.8(论文报告) |
| n-gram / prompt lookup | 在上下文中查找 n-gram 复制后续 token | ≈0 | 任务依赖:改写/摘要/RAG 高,自由生成低 |
| DeepSeek-V3 MTP | 训练时联合训练的一个额外 block | 1/61 层的量级 | 第二 token 85–90%(技术报告) |
- 独立小模型要求与目标共享 tokenizer(Llama-3-8B 给 70B 起草),\(c\) 约等于参数量之比,在 memory-bound 区间也等于字节数之比。\(\alpha\) 取决于两者分布的接近程度,同系列同数据训练的模型配对最好。
- Medusa 在目标模型最后一层 hidden state 上接 \(K\) 个轻量头,第 \(k\) 个头预测第 \(t + k + 1\) 个 token,一次前向同时出所有草稿;用 tree attention 一次验证多条候选路径。\(c \approx 0\),但各头独立预测(没有以前一个草稿为条件),\(\alpha\) 随头序号下降。论文报告 Medusa-1 约 2.2×、Medusa-2 约 2.3–2.8×。
- EAGLE 的观察是:在特征(倒数第二层的 hidden state)而非 token 层面做自回归,不确定性更低;草稿模块只有一层 decoder,输入是目标模型的特征与已采样 token 的 embedding。论文报告 LLaMA2-Chat 70B 上约 2.7–3.5×,EAGLE-2 用动态草稿树进一步提高。它的 \(\alpha\) 通常高于 Medusa,\(c\) 是一层对全模型的比例。
- n-gram / prompt lookup:把上下文里最近出现的 n-gram 后面接的 token 当草稿,零成本、零训练,在有大量复制的任务(改写、摘要、代码编辑、RAG)上 \(\alpha\) 很高,在自由生成上接近 0——加速比完全依赖任务。
- DeepSeek-V3 的 MTP:训练时就带一个预测下一下个 token 的额外模块,推理时可当草稿用(\(\gamma = 1\))。技术报告称第二个 token 的接受率在 85–90% 之间,对应 \(\mathbb{E}[\text{tokens}] = 1 + \alpha \approx 1.85 \sim 1.9\),报告的解码吞吐提升约 1.8×,与 \(c\) 很小时 \(1.9 / (c + 1)\) 的估算一致。
所有这些方案共享同一条约束:它们提升的是 \(\alpha\) 或降低 \(c\),但都改不了 \(B \lesssim \text{ridge}/(\gamma + 1)\) 这个收益区间。
三、实践:投机解码的期望加速比
1. 脚本新增的函数
延续贯穿全系列的 llm_cost.py,本篇新增 roofline_step_time(第一章的时间模型)与 speculative_speedup。配套仓库里这一版脚本(llm_cost_07_quant_specdec_lora.py)还带着 weight-only 量化字节数与 LoRA 参数量两组函数——它们原来与投机解码同在一篇,现在分别归入算法地图的《高效推理与压缩》与《LoRA 专题》;脚本原样保留以便独立运行与对照输出,下面只讲投机解码那一组。前几篇用到的 param_count、forward_flops_per_token、kv_bytes_per_token 同样重给 dense 版本(MLA 的版本在《Attention 变体与 KV cache》,MoE 的版本在《MoE 的路由、激活参数量与通信形态》)。
from dataclasses import dataclass
@dataclass
class ModelConfig:
name: str
hidden: int
layers: int
n_heads: int
n_kv_heads: int
head_dim: int
d_ff: int
vocab: int
tie_embeddings: bool = False
LLAMA3_8B = ModelConfig("Llama-3-8B", 4096, 32, 32, 8, 128, 14336, 128256)
LLAMA3_70B = ModelConfig("Llama-3-70B", 8192, 80, 64, 8, 128, 28672, 128256)
@dataclass
class GPU:
name: str
hbm_bytes: float
bandwidth: float # bytes/s
bf16_flops: float # FLOP/s
H100 = GPU("H100 SXM", 80e9, 3.35e12, 989e12)
A100 = GPU("A100 80GB", 80e9, 2.0e12, 312e12)
# ---- 前几篇的函数(dense 版本)----
def embedding_params(cfg):
return cfg.vocab * cfg.hidden * (1 if cfg.tie_embeddings else 2)
def param_count(cfg):
"""参数量(重给以便独立运行),返回 dict。"""
d = cfg.hidden
q, kv = cfg.n_heads * cfg.head_dim, cfg.n_kv_heads * cfg.head_dim
attn = d * q + d * kv + d * kv + q * d
ffn = 3 * d * cfg.d_ff
per_layer = attn + ffn + 2 * d
embed = cfg.vocab * d
lm_head = 0 if cfg.tie_embeddings else cfg.vocab * d
total = per_layer * cfg.layers + embed + lm_head + d
return {"per_layer": per_layer, "embedding": embed, "lm_head": lm_head, "total": total}
def forward_flops_per_token(cfg, ctx=0):
# embedding 查表不算 GEMM;lm_head 算
# 输入 embedding 是查表不算 GEMM;tied 模型那张表兼作 lm_head,仍要算
gemm_params = param_count(cfg)["total"] - (0 if cfg.tie_embeddings else cfg.vocab * cfg.hidden)
return 2 * gemm_params + 4 * cfg.hidden * ctx * cfg.layers
def kv_bytes_per_token(cfg, dtype_bytes=2):
return 2 * cfg.layers * cfg.n_kv_heads * cfg.head_dim * dtype_bytes
# ---- 本篇:时间模型与投机解码(量化、LoRA 两组函数见对应专题系列)----
def quantized_weight_bytes(cfg, bits=4, group_size=128, scale_bits=16,
zero_bits=16, keep_embed_bf16=False):
"""weight-only 量化后的权重字节数;返回 (bytes, 等效 bit/权重)。"""
eff_bits = bits + (scale_bits + zero_bits) / group_size
n = param_count(cfg)["total"]
if keep_embed_bf16:
e = embedding_params(cfg)
return (n - e) * eff_bits / 8 + e * 2, eff_bits
return n * eff_bits / 8, eff_bits
def roofline_step_time(cfg, gpu, rows, weight_bytes, mfu=1.0):
"""一次前向处理 rows 个 token 行的时间下界 max(访存, 计算),只计权重部分。"""
t_mem = weight_bytes / gpu.bandwidth
t_cmp = forward_flops_per_token(cfg) * rows / (gpu.bf16_flops * mfu)
return max(t_mem, t_cmp)
def speculative_speedup(alpha, gamma, c, batch, cfg, gpu, mfu=1.0):
"""投机解码相对普通 decode 的加速比;返回 (speedup, E[tokens])。"""
assert 0.0 <= alpha <= 1.0
# alpha == 1 时几何级数的闭式是 0/0,极限是 gamma + 1(全部接受 + bonus)
exp_tokens = gamma + 1 if alpha == 1.0 else (1 - alpha ** (gamma + 1)) / (1 - alpha)
w = param_count(cfg)["total"] * 2 # BF16 目标模型
t_base = roofline_step_time(cfg, gpu, batch, w, mfu)
t_verify = roofline_step_time(cfg, gpu, batch * (gamma + 1), w, mfu)
t_round = gamma * c * t_base + t_verify
return exp_tokens * t_base / t_round, exp_tokens
LORA_TARGETS_ATTN = ("q", "k", "v", "o")
LORA_TARGETS_ALL = ("q", "k", "v", "o", "gate", "up", "down")
def lora_params(cfg, rank=16, targets=LORA_TARGETS_ALL):
d = cfg.hidden
q, kv = cfg.n_heads * cfg.head_dim, cfg.n_kv_heads * cfg.head_dim
shapes = {"q": (d, q), "k": (d, kv), "v": (d, kv), "o": (q, d),
"gate": (d, cfg.d_ff), "up": (d, cfg.d_ff), "down": (cfg.d_ff, d)}
per_layer = sum(rank * (din + dout)
for t in targets for din, dout in [shapes[t]])
return per_layer * cfg.layers
if __name__ == "__main__":
for cfg in (LLAMA3_8B, LLAMA3_70B):
n = param_count(cfg)["total"]
b4, eb = quantized_weight_bytes(cfg)
print(f"{cfg.name}: {n/1e9:.2f}B BF16 {n*2/1e9:.1f} GB "
f"INT4(g128) {eb:.2f} bit -> {b4/1e9:.2f} GB")
print(f" decode 下界 BF16 {n*2/H100.bandwidth*1e3:.2f} ms "
f"W4A16 {b4/H100.bandwidth*1e3:.2f} ms")
print(f" LoRA r=16 attn {lora_params(cfg, 16, LORA_TARGETS_ATTN)/1e6:.2f}M "
f"all {lora_params(cfg, 16)/1e6:.2f}M ({lora_params(cfg, 16)/n*100:.2f}%)")
print("投机解码 alpha=0.8 gamma=4 c=0.1 (Llama-3-8B, H100):")
for B in (1, 8, 32, 64, 128, 256):
s, e = speculative_speedup(0.8, 4, 0.1, B, LLAMA3_8B, H100)
s60, _ = speculative_speedup(0.8, 4, 0.1, B, LLAMA3_8B, H100, mfu=0.6)
print(f" B={B:4d} peak {s:.2f} 60%MFU {s60:.2f} E[tokens]={e:.2f}")
输出:
Llama-3-8B: 8.03B BF16 16.1 GB INT4(g128) 4.25 bit -> 4.27 GB
decode 下界 BF16 4.79 ms W4A16 1.27 ms
LoRA r=16 attn 13.63M all 41.94M (0.52%)
Llama-3-70B: 70.55B BF16 141.1 GB INT4(g128) 4.25 bit -> 37.48 GB
decode 下界 BF16 42.12 ms W4A16 11.19 ms
LoRA r=16 attn 65.54M all 207.09M (0.29%)
投机解码 alpha=0.8 gamma=4 c=0.1 (Llama-3-8B, H100):
B= 1 peak 2.40 60%MFU 2.40 E[tokens]=3.36
B= 8 peak 2.40 60%MFU 2.40 E[tokens]=3.36
B= 32 peak 2.40 60%MFU 2.40 E[tokens]=3.36
B= 64 peak 2.38 60%MFU 1.61 E[tokens]=3.36
B= 128 peak 1.39 60%MFU 0.89 E[tokens]=3.36
B= 256 peak 0.76 60%MFU 0.62 E[tokens]=3.36
前六行里本篇只用到 BF16 的字节数与 decode 下界 4.79 ms——它就是时间模型里的 \(T_{\text{mem}}\);INT4 的 4.27 GB 与 W4A16 的 1.27 ms 对应第二章第 4 节图里下移的那条平台,LoRA 两行不属于本篇。最后六行是投机解码的数字:\(B \le 32\) 时加速比稳定在 2.40,\(B = 64\) 起按 60% MFU 折算的曲线先掉到 1.61,\(B = 128\) 低于 1——与第二章第 4 节的表一致。70B 的 BF16 decode 下界 42 ms 是”假设能放进一张卡”的数值,实际放不进。
2. 文本模型的成本表
前面各篇的数字合到一张表(H100 SXM,理论值;DeepSeek-V3 列用《Attention 变体与 KV cache》的 MLA 版本函数与《MoE 的路由、激活参数量与通信形态》的 MoE 版本函数):
| Llama-3-8B | Llama-3-70B | DeepSeek-V3 | |
|---|---|---|---|
| 参数量 | 8.03B | 70.55B | 671B(每 token 激活 37B) |
| 权重字节 BF16 | 16.06 GB | 141 GB | 1342 GB(FP8 671 GB) |
| 每 token 权重 FLOPs | 15.0 GFLOPs | ~141 GFLOPs | ~74 GFLOPs |
| KV cache / token(BF16) | 128 KiB | 320 KiB | 68.6 KiB(MLA) |
| 128K 上下文 KV cache(BF16) | 16 GiB | 40 GiB | 8.6 GiB |
| decode 下界 B=1,BF16 | 4.8 ms | 不能单卡 | 不能单卡 |
| 投机解码 α=0.8 γ=4 c=0.1 | 2.4×(B ≲ 60) | 2.4×(B ≲ 60) | MTP α≈0.85–0.9 γ=1 → ~1.8× |
DeepSeek-V3 的投机一行按其技术报告的 MTP 接受率转述。《多模态:vision encoder 的算量与 image token 的 KV 代价》给这张表加”一张 1024² 图片”一行,《浮点格式、数值稳定性与混合精度》加精度一列(权重与 KV 换成 FP8 各是多少字节、训练状态每参数几字节)。
四、本文小结
投机解码只改一个变量——每步验证的 token 数:
| 项 | 结论 |
|---|---|
| 正确性 | 以 \(\min(1, p/q)\) 接受、拒绝后从 \(\text{norm}(\max(0, p - q))\) 重采样,输出分布严格等于目标模型 \(p\);草稿 \(q\) 只影响效率 |
| 期望产出 | 一轮 \(\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}\) 个 token;\(\alpha = 0.8\)、\(\gamma = 4\) 时 3.36 |
| 加速比 | \(\mathbb{E}[\text{tokens}] / (\gamma c + 1)\),\(c = 0.1\) 时 2.4×;成立的前提是验证 \(\gamma + 1\) 个 token 与验证 1 个同样贵 |
| 收益区间 | \(B \lesssim \text{ridge}/(\gamma + 1) \approx 60\);越过之后验证进入 compute-bound,被拒绝 token 的 FLOPs 开始花真时间,大 batch 下可低于 1 |
| 草稿来源 | 独立小模型、Medusa、EAGLE、n-gram、MTP 模块——改变的是 \(\alpha\) 与 \(c\),改不了收益区间 |
本篇的数字:
| Llama-3-8B | Llama-3-70B | DeepSeek-V3 | |
|---|---|---|---|
| 投机 E[tokens](α=0.8, γ=4) | 3.36 | 3.36 | 1.85–1.9(MTP) |
| 投机加速比(c=0.1,B ≲ 60) | 2.4× | 2.4× | ~1.8× |
| 投机转折 batch(ridge/(γ+1)) | ~60 | ~60 | — |
本篇只算了投机解码的账。怎么把接受率提上去(草稿的训练目标是蒸馏)、Medusa / EAGLE 的草稿各看到了什么、树状草稿怎么一次验证多条路径、何时投机反而变慢,在《高效推理与压缩》系列的《投机解码:草稿、接受率与树》展开。《多模态:vision encoder 的算量与 image token 的 KV 代价》把输入从 token 换成图片:vision encoder 与 connector 加在哪里、一张图变成多少 token、这些 token 在 decoder 里占多少 KV。
配套代码:transformer-and-llm/llm_cost_07_quant_specdec_lora.py。
五、自测
-
投机解码 \(\alpha = 0.8\)、\(\gamma = 4\)、\(c = 0.1\):一轮期望产出几个 token?加速比多少?batch 多大时失效?
答案
\(E = (1 - 0.8^5)/(1 - 0.8) = 3.36\);加速 \(3.36 / (4 \times 0.1 + 1) = 2.4\times\);验证一次前向要算 \(\gamma + 1 = 5\) 倍的 token,等效 batch 过 ridge 的点是 \(295 / 5 \approx 60\),之后验证不再免费、加速开始随 \(B\) 下降,但不是立刻低于 1:要到验证时间变成基线的 3.36 倍以上才亏(第二章第 4 节的表里 \(B = 64\) 仍有 2.38 倍、\(B = 128\) 是 1.39 倍)。
-
为什么”验证 \(\gamma + 1\) 个 token 与验证 1 个同样贵”?这个说法在什么条件下失效?
答案
目标模型的 GEMM 从 \([B, k] \times [k, n]\) 变成 \([B(\gamma+1), k] \times [k, n]\):FLOPs 乘 \(\gamma + 1\),但权重只从 HBM 读一遍、KV cache 也只读一遍;只要 \(B(\gamma + 1)\) 仍在 ridge 之下,时间由字节数决定,多出的 FLOPs 落在空转的 Tensor Core 上。\(B(\gamma+1)\) 越过 ridge 后验证进入 compute-bound,时间随 \(\gamma + 1\) 线性增长,被拒绝 token 的计算成了真实成本。
-
投机解码的输出分布为什么严格等于目标模型?草稿模型越差,会出错还是只会变慢?
答案
单步”接受且输出 \(x\)“的概率是 \(q(x)\min(1, p(x)/q(x)) = \min(p(x), q(x))\),拒绝的概率是 \(1 - \beta\),拒绝后从 \(\text{norm}(\max(0, p - q))\) 采到 \(x\) 的概率是 \(\max(0, p(x) - q(x)) / (1 - \beta)\),两项相加恰好是 \(p(x)\);每个位置都以已接受的前缀为条件,与自回归采样的联合分布逐位相同。证明不依赖 \(q\),所以草稿再差也不会出错,只是接受率 \(\alpha\) 下降、每轮产出更少、更慢。
-
第二章第 2 节三词词表的例子里,如果草稿把分布改成 \(q\) = (0.5, 0.3, 0.2),即与目标完全相同,接受率 \(\beta\) 是多少?拒绝后的残差分布是什么?
答案
\(\beta = \sum \min(p, q) = 1\),每个草稿都被接受;残差 \(\max(0, p - q)\) 全为 0,拒绝不会发生,所以也用不到它。这是 \(\alpha = 1\) 的极限:每轮产出 \(\gamma + 1\) 个 token。
-
\(\alpha = 0.8\)、\(\gamma = 4\) 时,一轮只产出 1 个 token 的概率是多少?全部接受的概率是多少?
答案
第 1 个草稿就被拒:\(1 - \alpha = 0.2\);全接受:\(\alpha^4 = 0.4096\)。产出数的期望是 \(1 \times 0.2 + 2 \times 0.16 + 3 \times 0.128 + 4 \times 0.1024 + 5 \times 0.4096 = 3.36\),与几何级数的闭式一致。
系列 《现代 LLM 结构:从 GPT-2 到今天的演进》 第 8 / 11 篇 进阶
系列总览 — 为什么这样组织、读它需要什么、读完能做什么 · 幻灯片 — 整个系列的精华,一份可分享的 deck
学习地图 — AI-Infra 工程师学习地图 第 5 / 14 个系列 · AI 算法工程师学习地图 第 6 / 12 个系列
上一篇:MTP——改训练目标而不改主干的多 token 预测下一篇:多模态:vision encoder 的算量与 image token 的 KV 代价
下一个系列:GPU Kernel 工程:从 CUDA 执行模型到 FlashAttention 深入 · 12 篇,约 6.0 小时
本文由 arganzheng 创作,采用 CC BY 4.0 许可协议。在保留原文作者、署名以及完整原文链接(https://arganzheng.life/speculative-decoding-draft-verify-and-payoff.html)的前提下,欢迎各种形式的转载、翻译或商业引用。
COMMENTS
评论存放在 GitHub Discussions, 用 GitHub 账号登录即可发表,支持 Markdown。 想针对正文某句话说?选中那段文字,点浮出的「评论」即可划线评论;觉得哪里写错了,发表时勾上「同时提交 Issue」。 有人回复你时 GitHub 会按你的通知设置发邮件,不用守在这里。