5.1 核心原理：Draft + Verify 与 Rejection Sampling

第 1 章讲过，LLM 推理的 Decode 阶段是 Memory Bound，每生成一个 Token 都要把全部权重从 HBM 读一遍。但还有一个更隐蔽的瓶颈：自回归的串行性——第 $t+1$ 个 Token 必须等第 $t$ 个 Token 算完才能开始。无论 GPU 多快，一个 Token 一个 Token 地”排队”这件事本身无法并行。

投机解码（Speculative Decoding）的思路非常反直觉：先让一个又快又小的模型”猜”接下来的 N 个 Token，再用大模型一次性验证。猜对了就白赚 N 个 Token，猜错了也无损——因为验证环节保证了输出分布和原来完全一致。这一节把它的数学原理、正确性证明和收益公式讲透。

1. 串行瓶颈：为什么 Decode 快不起来

回忆第 1 章和第 2 章的内容：Decode 阶段每个 Token 需要一次完整的前向传播，其中权重读取（约 $2 \times P$ 字节， $P$ 为参数量）占主导，所以 Decode 是 Memory Bound。H100 上 FP16 的 70B 模型理论极限约 24 Token/s——这是”带宽墙”。

但即使带宽无限，还有第二堵墙：串行依赖。生成第 $t+1$ 个 Token 时，注意力必须看到第 $t$ 个 Token 的 Key/Value；而第 $t$ 个 Token 又依赖第 $t-1$ 个……这个依赖链是硬性的，无法像 Prefill 那样把长序列一次性并行算完。生成 K 个 Token 需要 K 次串行的模型调用——这是投机解码要解决的根本问题。

💡 提示：串行瓶颈和带宽瓶颈是两回事。量化（第 4 章）解决”每步搬多少数据”的问题，投机解码解决”要搬多少步”的问题。两者正交，可以叠加——这也是第 5.4 节讨论叠加效果的基础。

投机解码赖以成立的，是两个非常朴素的观察（Leviathan et al., 2023）：

LLM 生成的文本里，大部分 Token 是”好猜”的。“The capital of France is” 后面的 “Paris” 几乎必然出现；代码里的括号、关键字、缩进，自然语言里的冠词、介词，都是低熵内容。
一个很小的模型就能猜中这些低熵 Token。猜错的时刻，正是大模型展现”实力”的地方——这时小模型的猜测被丢弃，一切回到原样。

📌 关键点：投机解码不是”近似采样”——它通过验证机制保证输出分布严格不变。猜对了是赚的，猜错了只是”白跑了一次小模型”，大模型重新用自己的分布采样，结果与不投机时完全一致。它把”串行的 1 次大步”拆成了”并行的 N+1 次小步”。

2. 核心思想：先猜后验

投机解码每一轮迭代做两件事：

Draft（猜测）：用一个小的草稿模型（Draft Model）或其它提案器，自回归地生成 N 个候选 Token： $\hat{x}_1, \hat{x}_2, \dots, \hat{x}_N$ 。小模型每步只读自己那点权重，速度快（比如 70B 的 1/50 大小）。
Verify（验证）：把”前缀 + N 个候选 Token”整体喂给大模型（Target Model），一次前向算出这 N+1 个位置上的完整分布 $p(x_t \mid \text{prefix}, \hat{x}_{<t})$ 。

验证之所以能一次完成，是因为 Transformer 的注意力天然支持”看未来”——验证时把候选 Token 当作已知输入，所有位置的分布可以并行算出（训练时就是这样的掩码注意力）。大模型的 N+1 次串行前向，被压缩成 1 次”多一个 Token”的前向，而 Decode 是 Memory Bound，多算 N 个位置增加的带宽开销很小（KV Cache 和激活的增量远小于权重）。

验证得到 N+1 个位置的真实分布后，用 Rejection Sampling（拒绝采样）逐个决定候选 Token 是接受还是拒绝（详见第 4 节），然后进入下一轮：以最后一个被接受的 Token 为新的起点，继续 Draft N 个、Verify……

\text{每轮迭代} = \underbrace{N \text{ 步小模型自回归}}_{\text{成本 } N \times T_d} + \underbrace{1 \text{ 步大模型前向}}_{\text{成本 } T_t} \Rightarrow \text{产出约 } E[L] \text{ 个 Token}

💡 提示：注意 Verify 只算一个位置的新分布（ $\hat{x}_N$ 之后的位置），前面 N 个位置在”验证完整批次”时已经算过。这就是投机解码和”自回归但批量”（如 MTP 的 vanilla 版）的区别：投机解码总是用 target 的分布兜底，保证无损。

3. Draft + Verify：投机解码的两步框架

把框架拆成组件，每个组件都有独立的设计空间：

组件	职责	可选实现（后文展开）
提案器（Proposer）	快速生成候选 Token 序列	独立小模型（5.2）、N-gram / Suffix（5.2）、Medusa / EAGLE / MTP（5.3）
验证器（Verifier）	并行计算候选位置的真实分布	就是 Target 模型本身，无需改动
接受规则（Acceptance）	决定每个候选 Token 的去留	Rejection Sampling（本节）、贪心等号比较（第 6 节）

提案器只要满足一个要求：能给出”合理的分布”——它可以是任何模型、任何算法，甚至不需要是概率模型（N-gram 用频率计数，见 5.2）。唯一的要求是每个候选 Token 附带一个”草稿概率” $q(\hat{x}_i)$ ，供 Rejection Sampling 使用。

迭代 i 开始（当前已生成的序列为 s）：
┌─────────────────────────────────────────────────────┐
│ Draft:  小模型/提案器 自回归生成 N 个候选            │
│         x̂1 x̂2 ... x̂N，每个带草稿概率 q(x̂i)          │
└──────────────────────┬──────────────────────────────┘
                       ▼
┌─────────────────────────────────────────────────────┐
│ Verify: Target 一次前向，并行算出 N+1 个位置的分布   │
│         p(·|s), p(·|s,x̂1), ..., p(·|s,x̂1..x̂N)      │
└──────────────────────┬──────────────────────────────┘
                       ▼
┌─────────────────────────────────────────────────────┐
│ Accept: 从第 1 个位置开始逐个 Rejection Sampling     │
│         接受 x̂i 的概率 min(1, p(x̂i)/q(x̂i))          │
│         第一个被拒绝的候选及其后的全部丢弃            │
└──────────────────────┬──────────────────────────────┘
                       ▼
            以最后一个接受的 Token 为起点，进入下一轮

注意”第一个被拒绝的候选及其后的全部丢弃”：验证时虽然算出了 N+1 个位置，但如果 $\hat{x}_3$ 被拒绝， $\hat{x}_4, \dots, \hat{x}_N$ 自然作废——它们的分布是在错误的前缀上算的。被拒绝的位置由 Target 用自己的分布重新采样（通常就是 $\hat{x}_3$ 位置，Target 分布在此采样一个 Token 作为真实输出），这个 Token 一定符合 Target 分布，所以链条永远续得上。

4. Rejection Sampling：让猜测无损的数学魔法

4.1 直觉：两个分布之间的”仲裁”

假设前缀为 $s$ ，草稿模型给出分布 $q(\cdot \mid s)$ ，Target 模型给出分布 $p(\cdot \mid s)$ 。我们手里有一个从 $q$ 采样的候选 Token $\hat{x}$ ，想让它”代表” $p$ 的采样结果。

如果 $q(\hat{x}) \le p(\hat{x})$ ：说明 Target 给这个 Token 的概率不小于草稿模型，直接接受——此时 $\hat{x}$ 既是 $q$ 的样本，也”像是” $p$ 的样本。
如果 $q(\hat{x}) > p(\hat{x})$ ：说明草稿模型高估了这个 Token，以概率 $\frac{p(\hat{x})}{q(\hat{x})}$ 接受，否则拒绝。

拒绝后怎么办？不能空手而归——Target 需要在排除 $\hat{x}$ 的”剩余概率空间”里重新采样。数学上，拒绝后 Target 从如下修正分布采样：

p_{\text{修正}}(x) = \max\left(0, \frac{p(x) - q(x)}{1 - \sum_{x': q(x') > p(x')} (q(x') - p(x'))}\right)

这个式子看着吓人，但本质就一句话：把 $q$ “多出来”的概率质量从 $p$ 中剔除并归一化，剩下的就是 $p$ 的条件分布。

4.2 正确性证明（核心，建议手推一遍）

要证明的是：接受一个候选 $\hat{x}$ 的概率 = $p(\hat{x})$ ，即”接受”这个事件的概率分布恰好等于 Target 分布 $p$ 。

设 $r = \min\left(1, \frac{p(\hat{x})}{q(\hat{x})}\right)$ 为接受概率，分两种情况：

情况 A： $q(\hat{x}) \le p(\hat{x})$ （直接接受）

\Pr[\hat{x} \text{ 被接受}] = q(\hat{x}) \cdot 1 = q(\hat{x})

情况 B： $q(\hat{x}) > p(\hat{x})$ （概率接受）

\Pr[\hat{x} \text{ 被接受}] = q(\hat{x}) \cdot \frac{p(\hat{x})}{q(\hat{x})} = p(\hat{x})

两种情况合起来： $\Pr[\hat{x} \text{ 被接受}] = \min(q(\hat{x}), p(\hat{x}))$ 。接受事件的总概率（对全部 Token 求和）：

\Pr[\text{接受某个 Token}] = \sum_x \min(q(x), p(x)) \equiv \alpha

这个 $\alpha$ 就是接受率（Acceptance Rate）——它等于 $p$ 和 $q$ 两个分布的”重叠面积”，也是下一节收益公式的核心参数。

而被接受 Token 的条件分布：

\Pr[\hat{x} \text{ 被接受} \mid \text{接受事件发生}] = \frac{\min(q(\hat{x}), p(\hat{x}))}{\alpha}

要证 $\hat{x} \sim p$ ，等价于证 $\min(q(\hat{x}), p(\hat{x})) \propto p(\hat{x})$ ，即 $\min(q(\hat{x}), p(\hat{x})) = c \cdot p(\hat{x})$ 对所有 $x$ 成立。验证：

若 $q(x) \le p(x)$ ： $\min = q(x)$ ，需要 $q(x) = c \cdot p(x)$ ……
等等，这并不对所有 $x$ 成立？

别急——上面这条推理链有个隐藏前提：在情况 A 中，“接受” 的分布是 $q$ 而不是 $p$ ，看起来 $\hat{x}$ 并不严格服从 $p$ 。这正是 Rejection Sampling 证明的精妙之处：情况 A 中接受的事件并不直接输出 $\hat{x}$ 。完整的算法是：

以概率 $r = \min(1, p(\hat{x})/q(\hat{x}))$ 接受 $\hat{x}$ ；
若拒绝，则从”修正分布” $p_{\text{修正}}$ （见 4.1）中采样一个 Token 作为输出（这个 Token 可能恰好等于 $\hat{x}$ ）。

于是输出的分布为（令 $A$ 为接受事件）：

\begin{aligned} \Pr[\text{输出 } x] &= \Pr[x \text{ 被接受}] + \Pr[\text{拒绝} \wedge p_{\text{修正}} \text{ 采到 } x] \\ &= \min(q(x), p(x)) + \left(1 - \alpha\right) \cdot \frac{p(x) - \min(q(x), p(x))}{1 - \alpha} \\ &= \min(q(x), p(x)) + p(x) - \min(q(x), p(x)) \\ &= p(x) \quad \blacksquare \end{aligned}

📌 关键点：证明的落点是——输出 Token 的边缘分布严格等于 $p$ ，与草稿分布 $q$ 无关。这就是投机解码”无损”的数学根基： $q$ 只决定”多快”，不决定”对不对”。无论草稿模型多差，最终分布都不变；草稿模型越好，接受越多，速度越快。

4.3 连续 N 个位置的推广

实际中验证的是 N+1 个位置（前缀 + N 个候选），Rejection Sampling 逐位置进行：位置 $i$ 的草稿分布是 $q_i(\cdot \mid s, \hat{x}_{<i})$ ，Target 分布是 $p_i(\cdot \mid s, \hat{x}_{<i})$ ，每个位置独立做 4.2 的仲裁。第 $i$ 个位置被拒绝后，从 $p_i$ 的修正分布采样一个 Token 结束本轮。

于是每轮”接受长度” $L$ 的分布：

\Pr[L \ge i] = \prod_{j=1}^{i-1} \alpha_j, \qquad \Pr[L = N] = \prod_{j=1}^{N} \alpha_j \quad (\text{全部接受则长度为 } N+1)

其中 $\alpha_j$ 是第 $j$ 个位置的接受率（注意它随位置变化，真实实现中每个位置独立算）。

5. 期望加速比：收益到底有多少

设大模型一次前向耗时 $T_t$ ，小模型一步自回归耗时 $T_d$ ，草稿长度 $N$ ，平均接受率 $\alpha$ （为简化先假设各位置相同）。

每轮迭代产出 Token 数的期望（几何分布求和）：

E[L] = \sum_{i=1}^{N+1} \Pr[L \ge i] = 1 + \alpha + \alpha^2 + \dots + \alpha^{N} = \frac{1 - \alpha^{N+1}}{1 - \alpha}

每轮迭代耗时：Draft 的 $N$ 步 + Verify 的 1 步（可并行化/流水化，这里先按串行估算）：

T_{\text{iter}} = N \cdot T_d + T_t

期望加速比（相对标准自回归的每 Token 耗时 $T_t$ ）：

\text{Speedup} = \frac{E[L] \cdot T_t}{N \cdot T_d + T_t}

💡 提示：这个公式值得多看几眼，它解释了投机解码的全部工程直觉：

$\alpha$ 越高、 $N$ 越大， $E[L]$ 越大——草稿猜得越准、猜得越多，单轮产出越多；

$T_d \ll T_t$ 时，加速比逼近 $E[L]$ ——草稿模型必须足够小，否则草稿成本吃掉收益；

加速比上界是 $N+1$ （ $\alpha=1$ 且 $T_d=0$ 的极限），现实中 2-4 倍是典型区间。

代入具体数字感受一下（ $T_d = T_t / 50$ ，即草稿模型比大模型快 50 倍， $N = 4$ ）：

接受率 $\alpha$	$E[L]$ （期望产出）	耗时（ $T_t$ 单位）	加速比
0.4	1.65	1.08	1.5x
0.6	2.36	1.08	2.2x
0.8	3.36	1.08	3.1x
0.9	4.10	1.08	3.8x
0.95	4.52	1.08	4.2x

注意收益对 $\alpha$ 极其敏感：接受率从 0.6 提到 0.8，加速比从 2.2x 提到 3.1x。这就是为什么 5.2/5.3 节所有方案都在围绕”提高接受率”做文章，也解释了 5.4 节为什么”高接受率场景才有大收益”。

📌 关键点： $E[L] = \frac{1-\alpha^{N+1}}{1-\alpha}$ 是投机解码最重要的一个公式。它告诉你：与其盲目加大 $N$ （草稿越长，尾部位置的 $\alpha$ 越低，边际收益递减），不如提高 $\alpha$ ——这正是 EAGLE-2/3 动态草稿树（5.3 节）的设计动机。

6. 贪心模式：投机解码的特例

上面的证明针对采样模式（temperature > 0）。实际推理中贪心（greedy, temperature = 0）更常见，此时 Rejection Sampling 退化为最简单的规则：

草稿 Token $\hat{x}$ 与 Target 的 argmax 相同 → 接受；
不同 → 拒绝，Target 输出自己的 argmax。

也就是说，贪心模式下投机解码产出的序列与标准贪心解码逐 Token 完全相同（假设数值精度一致）——接受长度 $L$ 就是”草稿恰好连续押中 argmax”的长度。vLLM 的测试套件里有大量 Greedy Sampling Equality 测试专门验证这一点。

💡 提示：贪心模式下 $\alpha$ 可以理解为”草稿命中 argmax 的概率”。工程上贪心是投机解码最常见的运行模式（离线批处理、评估、代码生成默认贪心），而采样模式更多出现在在线对话服务中（temperature=0.6~0.8）。

7. 三个层面的”无损”保证

vLLM 官方文档把无损保证拆成三层，值得逐条理解：

层面	含义	实际边界
理论无损	Rejection Sampling 保证输出分布与标准解码一致	受硬件浮点精度影响，可能有极微小偏差
算法无损	vLLM 实现的 Rejection Sampler 与贪心路径都经过测试验证（`test_rejection_sampler.py` 的收敛性测试、`tests/v1/spec_decode` 的贪心等价测试）	实现层面有测试兜底
Logprob 稳定性	vLLM 不保证两次运行 logprob 完全一致	批量大小、数值稳定性会导致输出细节差异（与投机无关，标准解码同样存在）

所以”投机解码无损”在工程上要精确表述为：分布意义下无损；单次运行的输出可能与标准解码有细微差异（浮点精度、批处理非确定性）。做评测对比时（比如 5.5 节的实测），要意识到这个前提，用足够大的样本量。

📝 总结

投机解码解决的是串行瓶颈：把”串行的 N 步小模型 + 1 步大模型”变成”并行的 1 步大模型验证”，期望产出 $E[L]$ 个 Token
两个观察：生成文本大部分 Token 低熵好猜；小模型足以猜中低熵 Token
三步框架：Draft（提案器给出候选 + 草稿概率）→ Verify（Target 并行算 N+1 个位置的分布）→ Accept（逐位置 Rejection Sampling）
无损的数学根基： $\Pr[\text{输出 } x] = p(x)$ 与草稿分布 $q$ 无关—— $q$ 只决定速度，不决定正确性
核心公式： $E[L] = \frac{1-\alpha^{N+1}}{1-\alpha}$ ，加速比 $= \frac{E[L] \cdot T_t}{N \cdot T_d + T_t}$ ，对 $\alpha$ 极其敏感
贪心模式：接受规则退化为”等于 argmax”，输出与标准贪心逐 Token 一致
无损的三层含义：理论（分布级）、算法（实现级）、稳定性（不保证逐次一致）

🎯 自我检验清单

能否口述：为什么 Verify 能用一次前向算出 N+1 个位置的分布？
能否手推 Rejection Sampling 的 $\Pr[\text{输出 } x] = p(x)$ 证明（含拒绝后从修正分布采样的步骤）？
接受率 $\alpha$ 的几何意义是什么（两个分布的什么量）？
为什么说”加大 N 的边际收益递减”，而提高 $\alpha$ 收益更大？
贪心模式下投机解码的接受条件是什么？输出和标准解码有何关系？
“无损”的三个层面分别对应什么边界？

📚 参考资料

Leviathan et al., Fast Inference from Transformers via Speculative Decoding（https://arxiv.org/abs/2211.17192）
Chen et al., Accelerating Large Language Model Decoding with Speculative Sampling（https://arxiv.org/abs/2302.01318）
NVIDIA 博客：An Introduction to Speculative Decoding for Reducing Latency in AI Inference（https://developer.nvidia.com/blog/an-introduction-to-speculative-decoding-for-reducing-latency-in-ai-inference/）
vLLM 官方文档：Speculative Decoding（https://docs.vllm.ai/en/latest/features/speculative_decoding/）

搜索