本篇在系列中的位置。 现代 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/q\) 与残差,本轮结束即丢
  • greedy 解码只比较 argmax,不必保留
目标分布 \(p_1, \ldots, p_{\gamma+1}\) 验证前向,一次全部算出 每个位置一行概率 判定用完即丢,不跨轮
重采样 token 或 bonus token 判定阶段:首次拒绝时从残差分布抽,或全接受后从 \(p_{\gamma+1}\) 抽 接在被接受的草稿之后,成为正式输出 每轮恰好一个;它的 KV 要到下一轮验证前向才算
目标模型的 KV 验证前向为输入的 \(\gamma + 1\) 个位置各算一份 这个请求的 KV cache;要为草稿多留 \(\gamma\) 个位置的空间
  • 被接受位置的保留
  • 被拒位置及其后的丢弃(截断到被接受的前缀)
草稿模型的权重与 KV(草稿是独立小模型时) 权重常驻;KV 在起草的每一步追加 同一张卡的显存,草稿模型自己的一份 KV cache
  • KV 同样截断到被接受的前缀,下一轮起草前补上重采样的 token
  • Medusa 的头、n-gram 查找没有这一项

1. 本文的路线

  1. 先把《前向的算量与访存量》的 Roofline 压成一个时间模型(本章第 2 节),后面所有估算都用它。
  2. 再讲投机解码本身(第二章):算法与”输出分布严格不变”的证明、期望接受数与加速比、验证多个 token 为什么几乎免费又何时不再免费、草稿从哪里来。
  3. 最后把它加进 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)一轮做四件事:

  1. 草稿模型自回归采样 \(\gamma\) 个 token \(x_1, \ldots, x_\gamma\),\(x_i \sim q(\cdot \mid \text{prefix}, x_{<i})\);
  2. 目标模型对 \(\text{prefix}, x_1, \ldots, x_\gamma\) 做一次前向,得到 \(\gamma + 1\) 个位置的分布 \(p_1, \ldots, p_{\gamma+1}\);
  3. 从 \(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\),本轮结束;
  4. 若 \(\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;

先用一个只有三个词的词表把一个位置的判定走一遍。目标模型与草稿在这个位置的分布是:

三词词表上的一次接受—拒绝:草稿高估 A、低估 B 与 C
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 个草稿被拒绝为例:

γ = 4、第 3 个草稿被拒绝时一轮验证的输入、判定与 KV 回退
位置 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):

α = 0.8、γ = 4 时一轮产出 token 数的分布
本轮产出 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)摆在同一条时间轴上:

产出同样 3.36 个 token,普通 decode 与一轮投机解码的时间账(B = 1,理论下界)
  普通 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\)。

几个变体的数字:

投机解码几个 α、γ 组合的期望 token 数与加速比
\(\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 的变化
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 的平台向下移,投机解码把工作点向右推,两者的收益都止于平台与斜线的交点:

Llama-3-8B 在 H100 上的 T(m) 曲线:BF16 与 W4A16 两条平台、共同的 compute 斜线,量化下移平台、投机右移工作点

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 与接受率 α(文献通常报告的量级)
方案 草稿形态 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 版本函数):

前面各篇数字的汇总:三个模型的权重、KV cache、decode 下界与投机解码
  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。

五、自测

  1. 投机解码 \(\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 倍)。

  2. 为什么”验证 \(\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 的计算成了真实成本。

  3. 投机解码的输出分布为什么严格等于目标模型?草稿模型越差,会出错还是只会变慢?

    答案

    单步”接受且输出 \(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\) 下降、每轮产出更少、更慢。

  4. 第二章第 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。

  5. \(\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\),与几何级数的闭式一致。

  1. 投机解码一次前向验证 \(\gamma + 1\) 个 token,等于把每步的 \(m\) 放大 \(\gamma + 1\) 倍;batch 1 时 decode 是 memory-bound 的,多算的 FLOPs 落在空转的算力上,几乎免费,\(\alpha = 0.8\)、\(\gamma = 4\) 时一轮期望产出 3.36 个 token、加速约 2.4 倍。batch 增大到约 \(295/(\gamma+1) \approx 60\) 时验证本身就过了 ridge,多算的 FLOPs 开始花真时间,加速比随 batch 下降。详见第二章第 4 节。 ↩

这篇对你有用?

本文由 arganzheng 创作,采用 CC BY 4.0 许可协议。在保留原文作者、署名以及完整原文链接(https://arganzheng.life/speculative-decoding-draft-verify-and-payoff.html)的前提下,欢迎各种形式的转载、翻译或商业引用。


COMMENTS

评论存放在 GitHub Discussions, 用 GitHub 账号登录即可发表,支持 Markdown。 想针对正文某句话说?选中那段文字,点浮出的「评论」即可划线评论;觉得哪里写错了,发表时勾上「同时提交 Issue」。 有人回复你时 GitHub 会按你的通知设置发邮件,不用守在这里。

×