LLM 推测解码精读笔记 · 01 问题形式化与接受率数学

对应：Leviathan et al., Fast Inference from Transformers via Speculative Decoding（2023）；Inference Engineering Ch5 的 Speculative Decoding 部分。 学完本章你应该能：① 说清自回归解码慢的结构性原因（因果依赖使 GPU 的并行能力被浪费）；② 用"草稿 + 并行验证"一句话解释推测解码为什么能加速；③ 从定义推导期望 token 数公式 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$；④ 推导墙钟加速比公式并手算数值例；⑤ 解释"为什么推测解码是无损的"（拒绝采样的边际分布等于目标分布）。

---

目录（本章） #

1. 本章目标
2. 自回归解码为什么慢：形式化
3. 核心思想：草稿 + 并行验证
4. 接受率数学：α 与 E[N]
5. 墙钟收益模型：速度比 c 与最优 K
6. 为什么无损：拒绝采样的边际分布定理
7. 设计空间：α、K、c 三者如何决定收益
8. 本章小结
9. 习题与解答
10. 延伸阅读

---

1. 本章目标 #

量化系列回答"每一步怎么更快"，本系列回答"怎么用更少的步数生成同样的文本"。本章建立整个系列的数学地基——接受率 α 和期望 token 数 E[N]。后面所有方法（Medusa、EAGLE、n-gram）本质都在做同一件事：提高 α 或降低草稿成本。

---

2. 自回归解码为什么慢：形式化 #

2.1 自回归的结构性约束 #

LLM 按自回归方式生成：

$$ x_{t+1} \sim p(\cdot \mid x_1, \dots, x_t) $$

第 $t+1$ 个 token 依赖前 $t$ 个 token——严格串行：

第 1 步：只算 1 个位置
第 2 步：只算 1 个位置（但前向里其实处理了 2 个位置的 KV）
……
每步只"新增"1 个 token 的预测

2.2 浪费在哪里 #

每次前向，GPU 会并行计算所有 token 位置的表示（矩阵乘天生并行），但自回归只取最后一个位置的输出：

GPU 实际算的：seq_len 个位置的全部激活
解码真正用的：最后 1 个位置的 logits
→ 计算利用率 ≈ 1/seq_len（序列越长越浪费）

更准确地说，decode 阶段是访存密集的（量化系列 03 章的带宽模型）：瓶颈在把权重从 HBM 搬到寄存器，而不是在"算"。但无论算还是搬，每步只为 1 个新 token 付费——这是自回归的根本开销。

2.3 关键矛盾 #

自回归的约束：token 之间存在因果依赖，必须串行决策
GPU 的能力：一次前向可以并行处理 K 个位置的输入

推测解码的思路：用便宜的草稿模型先"猜" K 个 token，再用昂贵的目标模型一次并行验证。如果草稿猜得准，一次目标前向就能产出多个 token。

---

3. 核心思想：草稿 + 并行验证 #

3.1 两个模型 #

目标模型 p：大、准、慢（真正负责质量，输出分布必须由它决定）
草稿模型 q：小、快、不太准（猜，猜错了会被纠正）

3.2 一轮操作的流程（预览） #

1. 草稿：用 q 自回归生成 K 个候选 token（K 步，每步很快）
2. 验证：把 K 个候选一次性喂给 p，一次前向得到 K+1 个位置的 logits
3. 接受：从左到右逐个检查候选是否"与 p 一致"（拒绝采样规则）
4. 纠正：第一个不一致的位置，从修正分布重采样一个 token
5. 产出：这一轮得到 N 个新 token（1 ≤ N ≤ K+1）

关键：验证只花一次目标前向（代价约等于正常解码一步），却可能换来最多 K+1 个 token。这就是加速的来源。

3.3 先记三个量 #

K：每轮草稿长度（典型 4~8）
α：每个草稿 token 被接受的概率
c：目标模型每 token 耗时 / 草稿模型每 token 耗时（典型 5~20）

---

4. 接受率数学：α 与 E[N] #

4.1 定义接受概率 α #

设目标分布 p、草稿分布 q（同一时刻、同一前缀下）。草稿 token 按 q 采样，验证时以概率

$$ \min\left(1, \frac{p(x)}{q(x)}\right) $$

接受它（拒绝采样规则，第 6 节证明它保持分布）。于是无条件接受概率：

$$ \alpha = \sum_x q(x) \cdot \min\left(1, \frac{p(x)}{q(x)}\right) = \sum_x \min(p(x), q(x)) $$

4.2 α 与 TV 距离的关系 #

利用 $\min(a,b) = \frac{a+b-|a-b|}{2}$：

$$ \alpha = \frac{1}{2}\sum_x \left(p(x)+q(x)-|p(x)-q(x)|\right) = 1 - \frac{1}{2}\sum_x |p(x)-q(x)| $$

即

$$ \alpha = 1 - \mathrm{TV}(p, q) $$

α 越接近 1，草稿与目标分布越一致。β = 1 − α 就是每 token 被拒绝的概率。

4.3 期望 token 数 E[N] 的推导 #

设每轮草稿 K 个 token，token 间相互独立（近似；严格版本对历史取条件期望，结论形式相同）。令 α 为单 token 接受概率。

每轮产出 N 个 token。N 的分布由"前 $i-1$ 个草稿 token 都被接受、第 $i$ 个被拒绝（随后补 1 个修正 token）“或"全部 $K$ 个都被接受（随后从 $p$ 直接采 1 个 bonus token）“决定：

$$ P(N = i) = \alpha^{i-1}(1-\alpha), \quad i = 1, \dots, K; \qquad P(N = K+1) = \alpha^{K} $$

期望：

$$ E[N] = \sum_{i=1}^{K} i \cdot \alpha^{i-1}(1-\alpha) + (K+1)\alpha^K $$

用等比数列求和 $\sum_{i=1}^{K} i\alpha^{i-1} = \frac{1-(K+1)\alpha^K + K\alpha^{K+1}}{(1-\alpha)^2}$，整理得：

$$ E[N] = \frac{1-\alpha^{K+1}}{1-\alpha} $$

这是整个系列的"第一公式”。

4.4 数值算例 #

不同 α、K 下的期望每轮 token 数：

α	K=4 时 E[N]	K=8 时 E[N]
0.5	1.94	1.996
0.6	2.31	2.47
0.7	2.77	3.20
0.8	3.36	4.33
0.9	4.10	6.13

验证一例（α=0.8, K=4）：

$$ E[N] = \frac{1-0.8^{5}}{1-0.8} = \frac{1-0.32768}{0.2} = 3.36 $$

直觉：α=0.8 时每轮平均产出 3.36 个 token，而目标只"真正解码"了 1 次。

---

5. 墙钟收益模型：速度比 c 与最优 K #

5.1 一轮的墙钟时间 #

一轮时间 ≈ T_p + K·T_q
         = 一次目标验证 + K 步草稿

（目标验证一次前向处理 K+1 个位置，代价近似一次正常解码 T_p；草稿 K 步串行，每步 T_q。）

5.2 加速比公式 #

目标单独解码：每 token 耗时 $T_p$，每秒 $1/T_p$ 个 token。 推测解码：每轮 $E[N]$ 个 token，耗时 $T_p + K T_q$。

$$ \text{speedup} = \frac{E[N]\cdot T_p}{T_p + K\cdot T_q} = \frac{E[N]\cdot c}{c + K}, \quad c = \frac{T_p}{T_q} $$

5.3 数值算例 #

设 c = 10（目标比草稿慢 10 倍），α = 0.8，K = 4：

$$ E[N] = 3.36, \quad \text{speedup} = \frac{3.36 \times 10}{10+4} = 2.40 $$

即墙钟约快 2.4 倍。再看不同组合：

α	c	K	E[N]	speedup
0.8	10	4	3.36	2.40x
0.8	10	8	4.33	2.40x
0.9	10	8	6.13	3.40x
0.6	10	4	2.31	1.65x
0.8	5	4	3.36	1.87x

5.4 收益的两个边界 #

上界：α → 1 时 $E[N] \to K+1$，加速比 $\to \frac{(K+1)c}{c+K} \to c$。推测解码最多快 c 倍——草稿与目标的速度比是天花板，这解释了为什么要选足够小/快的草稿。

下界：α 太低时加速比 < 1（推测反而拖慢）。需要

$$ E[N] > 1 + \frac{K}{c} $$

5.5 最优 K #

给定 α、c，加速比是 K 的函数：

$$ f(K) = \frac{c}{c+K}\cdot\frac{1-\alpha^{K+1}}{1-\alpha} $$

求整数 K 最大化 f(K)。经验规律：

α 高（0.8+）→ K 取大（8 甚至 16）收益仍增长
α 中（0.6~0.7）→ K 取 4~8 附近有峰值
c 小（草稿不够快）→ K 应该更小

---

6. 为什么无损：拒绝采样的边际分布定理 #

6.1 问题 #

草稿分布 q 和目标分布 p 不一致。为什么最后产出的 token 分布仍然严格等于 p？ 这使推测解码属于"无损"优化（与量化不同，不改变输出分布）。

6.2 拒绝采样规则 #

从 $q$ 采样得到 $x$，然后以概率 $\min(1, p(x)/q(x))$ 接受 $x$（直接输出）；否则从修正分布 $p_r$ 重采样：

$$ p_r(x) = \frac{\max(0, p(x) - q(x))}{\beta}, \qquad \beta = 1 - \alpha $$

6.3 边际分布验证 #

输出 x 的概率 = 直接接受 x 的概率 + 被拒后重采样到 x 的概率：

$$ P_{\text{emit}}(x) = q(x)\min\left(1,\frac{p(x)}{q(x)}\right) + \beta \cdot p_r(x) $$

分两种情形：

$$ P_{\text{emit}}(x) = \begin{cases} q(x) + (p(x) - q(x)) = p(x), & p(x) \ge q(x) \\ p(x) + 0 = p(x), & p(x) < q(x) \end{cases} $$

统一写法：

$$ P_{\text{emit}}(x) = \min(p(x), q(x)) + \max(0, p(x)-q(x)) = p(x) $$

结论：无论草稿多不准，输出分布都精确等于目标分布。 这是"无损"的数学保证。

6.4 一个直觉 #

拒绝采样把"q 猜错的那部分概率"按目标分布 p 重新分配，而不是丢弃：猜对的部分直接保留（min(p,q)），猜错的部分用 p−q 的残差补回来（max(0,p−q)），两者拼起来正好是 p。

---

7. 设计空间：α、K、c 三者如何决定收益 #

收益 = E[N](α, K) × c/(c+K)
     = 接受率    × 草稿开销

提高 α：草稿与目标越像越好（架构、训练数据、草稿规模）——02~05 章所有方法的主战场
提高 c：草稿越小越快（但太小 α 会掉）——权衡
调 K：在"多猜几次"与"多付草稿费"之间找峰值

方法谱系预览（后续章节）：
02 原始推测解码：独立小模型当草稿（α 中等，c 大）
03 Medusa：目标模型自带多头草稿（省草稿前向，α 提升）
04 EAGLE：特征空间草稿（α 大幅提升）
05 n-gram/检索：零训练草稿（c 极大，α 依赖数据）

---

8. 本章小结 #

1. 自回归慢的结构性原因：每步只产出 1 个 token，GPU 的并行能力被因果依赖锁死。
2. 推测解码 = 草稿 + 并行验证：草稿猜 K 个，目标一次验证，产出 E[N] 个。
3. 第一公式：$E[N] = \dfrac{1-\alpha^{K+1}}{1-\alpha}$，其中 $\alpha = \sum_x \min(p(x), q(x)) = 1 - \mathrm{TV}(p,q)$。
4. 墙钟收益：$\text{speedup} = \dfrac{E[N]\cdot c}{c+K}$；上限 c，α 太低会倒挂。
5. 无损性：拒绝采样让边际分布严格等于 p——这是与量化最本质的区别。

一句话记忆：“草稿负责猜，目标负责审；猜得越准（α）审得越快（c），K 是押注的注数。”

---

9. 习题与解答 #

题 1（推导）：期望 token 数 #

从 P(N=i) 出发，完整推导 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$。

题 1 解答

$E[N] = \sum_{i=1}^{K} i\alpha^{i-1}(1-\alpha) + (K+1)\alpha^K$。利用 $\sum_{i=1}^{K} i\alpha^{i-1} = \frac{1-(K+1)\alpha^K+K\alpha^{K+1}}{(1-\alpha)^2}$，代入并通分：分子 = $1-(K+1)\alpha^K+K\alpha^{K+1}+(K+1)\alpha^K-(K+1)\alpha^{K+1} = 1-\alpha^{K+1}$。得 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$。

题 2（计算）：加速比 #

c = 8，α = 0.7。比较 K = 4 与 K = 8 的加速比，并求使加速比 > 1 所需的最小 α（K=4, c=8）。

题 2 解答

α=0.7：EN = (1−0.7⁵)/0.3 = 2.77；speedup = 2.77×8/12 = 1.85x。EN = (1−0.7⁹)/0.3 = 3.20；speedup = 3.20×8/16 = 1.60x——K=4 反而更好（草稿费高）。加速比 > 1 需 E[N] > 1+K/c = 1.5；解 (1−α⁵)/(1−α) > 1.5，试 α=0.34：E[N]=1.51 ✓；α=0.33：E[N]=1.49 ✗（边界约 0.34）。

题 3（推导）：TV 恒等式 #

证明 $\alpha = 1 - \frac{1}{2}\sum_x |p(x)-q(x)|$。

题 3 解答

$\min(a,b) = \frac{a+b-|a-b|}{2}$，代入 $\alpha = \sum_x \min(p,q)$：$\alpha = \frac{1}{2}\sum p + \frac{1}{2}\sum q - \frac{1}{2}\sum|p-q| = 1 - \mathrm{TV}(p,q)$。

题 4（推导）：无损性 #

写出拒绝采样输出分布，证明 $P_{\text{emit}}(x) = p(x)$ 对任意 q 成立。

题 4 解答

$P_{\text{emit}}(x) = q(x)\min(1, p(x)/q(x)) + \beta\cdot\frac{\max(0,p(x)-q(x))}{\beta} = \min(p,q) + \max(0,p-q) = p(x)$。

题 5（思考）：为什么说推测解码是"无损” #

与量化相比，“无损"具体指什么？如果用户看到两次生成结果不同，怎么解释？

题 5 解答要点

无损指输出分布严格等于目标模型的采样分布（对任意解码策略：贪心/采样都保持）。两次生成不同是因为采样本身有随机性，与是否用推测无关。注意：如果实现里"无条件接受第一个草稿 token”（加速常用技巧）或草稿/目标温度不一致，会破坏严格无损——工程上要区分"理论无损"与"实现近似"。

题 6（编程）：模拟接受过程 #

给定两个词表分布 p、q（如 100 维），实现：① 计算 α；② 模拟 10000 轮草稿-验证（K=4），统计每轮产出 token 数的均值，与公式对比。

题 6 解答要点

① α = Σ min(p,q)。② 每轮：从 q 采样 K 个 token，逐个以 min(1,p(x)/q(x)) 接受；第一个拒绝处从残差分布 max(0,p−q)/β 重采样；全接受则再从 p 采 1 个 bonus。统计均值应接近 (1−α⁵)/(1−α)。可再验证输出 token 的经验分布 ≈ p（无损性）。

---

10. 延伸阅读 #

1. Fast Inference from Transformers via Speculative Decoding（arXiv:2211.17192）：本章公式出处（接受率、E[N]、最优草稿规模、墙钟实验）
2. Accelerating LLM Inference with Staged Speculative Decoding（arXiv:2302.01318）：同期独立工作，可对照阅读
3. Inference Engineering Ch5：Speculative Decoding 教材节
4. 下一篇：[02 原始推测解码：草稿模型与拒绝采样]——把本章公式落成完整算法，推导无损性定理并手算完整例子。