投机采样 / 投机解码（Speculative Decoding）

一句话：用一个便宜的草稿器先猜若干 token，再让昂贵的目标模型一次并行验证，并用拒绝采样规则接受最长合规前缀。
关键性质：在「接受/拒绝采样」版本下，输出分布与逐字从目标模型采样完全一致（无损）；草稿好坏只影响速度，不影响正确性。

一、为什么需要它：自回归解码是显存带宽瓶颈

生成 1 个 token 要把整个模型权重从显存（HBM）读一遍，但每个权重上只做了很少的计算。即单 token 解码是 memory-bound（显存带宽瓶颈），不是算力瓶颈——GPU 大部分时间在等数据，算力闲置。

由此得到一个关键事实：

对 $K$ 个 token 并行做一次前向，墙钟耗时和对 $1$ 个 token 做一次前向几乎一样（都被「读一遍权重」主导，多算 $K$ 个 token 的额外开销很便宜）。

预填充（prefill）快、逐字解码慢，就是这个原因。投机解码正是来「填满」这段闲置算力。

二、核心思路：草稿 → 验证 → 接受/拒绝

设两个角色：便宜快的草稿器（draft，分布记为 $q$ ），昂贵准的目标模型（target，分布记为 $p$ ，是我们真正想要其输出的大模型）。一轮流程：

第1步  草稿(draft)   : 草稿器自回归地、廉价地猜出 K 个候选 token
第2步  验证(verify)  : 目标模型对这 K 个 token 并行做【一次】前向,
                       同时得到它自己在每个位置上的概率分布
第3步  接受/拒绝     : 从左到右比对, 接受目标模型「认可」的最长前缀;
                       第一个不认可处就地纠正并停下

一次目标模型前向，就可能产出好几个 token，这就是加速来源。

具体例子

上下文为 The cat sat on the，最后一个 token the 记在位置 $t$ 。

草稿阶段：草稿器自回归猜 $K=4$ 个，并记下自己每步的分布 $q_1,\dots,q_4$ ：

给 [...the]             → 猜 x1 = mat   (位置 t+1)
给 [...the mat]         → 猜 x2 = and   (位置 t+2)
给 [...the mat and]     → 猜 x3 = the   (位置 t+3)
给 [...the mat and the] → 猜 x4 = dog   (位置 t+4)

验证阶段：把 4 个草稿 token 拼进输入序列，目标模型对整条序列做一遍前向。因果注意力下，每个位置输出「它下一个 token」的目标分布（输出在位置 $i$ ＝位置 $i{+}1$ 的 token 分布）：

位置:         t       t+1      t+2      t+3      t+4
输入token:   the  →   mat  →   and  →   the  →   dog
              │        │        │        │        │
          ┌───┴────────┴────────┴────────┴────────┴───┐
          │  目标模型, 因果注意力, 【一次】前向          │
          └───┬────────┬────────┬────────┬────────┬───┘
              ▼        ▼        ▼        ▼        ▼
目标分布:     p1       p2       p3       p4       p5(奖励)
目标top1:    mat      and      the      cat      ...
对比草稿:    mat✓     and✓     the✓     dog✗
结果:        接受     接受     接受     拒绝→改成 cat, 停

本轮提交 4 个 token：mat and the cat（前 3 个接受，第 4 个就地纠正）。草稿的 dog 被丢弃。若 4 个全接受，则再用奖励分布 $p_5$ 白送第 5 个，本轮提交 5 个。然后滑动窗口，重复。

三、验证为什么「一次前向」就够

因为中间 token $x_1,\dots,x_4$ 已经被草稿猜好、直接当输入填进去了。计算位置 $t{+}2$ 的分布本需先知道 $t{+}1$ 的 token，而我们用草稿的 mat 顶上，所以不必等——整条序列所有位置可像 prefill 一样并行算完。

每个分布的条件： $p_1$ 只看上下文 → 验证 $x_1$ ； $p_2$ 看「上下文 + $x_1$ 」→ 验证 $x_2$ ；以此类推。
一次前向给出 $K{+}1$ 个分布 $p_1,\dots,p_{K+1}$ 。前 $K$ 个验证草稿，最后一个是全接受时的奖励。
若某草稿 token 错了，它之后那些基于错误前缀算出的分布会被丢弃——但这些计算本就是搭便车免费算的，丢了不亏。

四、接受/拒绝规则（非贪心 / 投机采样）

非贪心是一般形式（即 speculative sampling）。记 $(a)_+ = \max(0,\,a)$ 。某位置上目标分布 $p$ 、草稿分布 $q$ ，草稿采出 token $x$ ：

\text{(1)}\quad \text{以概率}\ \min\!\left(1,\ \frac{p(x)}{q(x)}\right)\ \text{接受}\ x

\text{(2)}\quad \text{若拒绝，从残差分布重采：}\quad p_{\text{fix}}(y)=\frac{\big(p(y)-q(y)\big)_+}{Z},\qquad Z=\sum_{y}\big(p(y)-q(y)\big)_+

直觉：草稿若把某 token 采得比目标多（ $q(x)>p(x)$ ）， $\frac{p(x)}{q(x)}<1$ ，按比例偶尔拒绝压回去；残差 $(p-q)_+$ 恰是「目标想要、却被草稿低估」的质量，补给这些 token。

数值例子（接位置 $t{+}1$ ，温度 $>0$ ）

q=\{\text{mat}:0.6,\ \text{sat}:0.3,\ \text{ran}:0.1\},\qquad p=\{\text{mat}:0.5,\ \text{sat}:0.4,\ \text{ran}:0.1\}

草稿采到 $\text{mat}$ ，则接受概率 $=\min\!\left(1,\frac{0.5}{0.6}\right)\approx 0.83$ 。若拒绝，残差

(p-q)_+=\max\!\big(0,\{\text{mat}:-0.1,\ \text{sat}:0.1,\ \text{ran}:0\}\big)=\{\text{sat}:0.1\}\ \xrightarrow{\text{归一化}}\ \{\text{sat}:1.0\}

即改吐 $\text{sat}$ 。含义：草稿过度偏爱 $\text{mat}$ （ $0.6$ vs 目标 $0.5$ ）， $0.83$ 的接受概率把它压下去，省出的质量流向被低估的 $\text{sat}$ 。

五、为什么输出精确服从目标分布 $p$ （证明）

这是「无损」的全部依据。最终吐出 token $x$ 只有两条路——被草稿提议且接受，或先拒绝再重采中它：

P(\text{吐出}\ x)=\underbrace{P(\text{提议}\ x\ \text{且接受})}_{\text{第一项}}+\underbrace{P(\text{拒绝})\cdot p_{\text{fix}}(x)}_{\text{第二项}}

第一项：

q(x)\cdot \min\!\left(1,\ \frac{p(x)}{q(x)}\right)=\min\big(q(x),\,p(x)\big)

第二项的拒绝概率（按草稿提议哪个 token 用全概率公式求和）：

P(\text{拒绝})=\sum_{y}\underbrace{q(y)}_{P(\text{提议}y)}\Big[1-\min\!\big(1,\tfrac{p(y)}{q(y)}\big)\Big]=\sum_{y}\big(q(y)-p(y)\big)_+

关键恒等式： $p,q$ 均为分布， $\sum_y p(y)=\sum_y q(y)=1$ ，故 $\sum_y\big(p(y)-q(y)\big)=0$ ，即正部与负部质量相等：

Z=\sum_{y}\big(p(y)-q(y)\big)_+=\sum_{y}\big(q(y)-p(y)\big)_+=P(\text{拒绝})

于是第二项 $=P(\text{拒绝})\cdot\frac{(p(x)-q(x))_+}{Z}=\big(p(x)-q(x)\big)_+$ 。合并：

P(\text{吐出}\ x)=\min\big(q(x),p(x)\big)+\big(p(x)-q(x)\big)_+= \begin{cases} q(x)+\big(p(x)-q(x)\big)=p(x), & p(x)\ge q(x)\\[4pt] p(x)+0=p(x), & p(x)< q(x) \end{cases}

\boxed{\ \therefore\ P(\text{吐出}\ x)=p(x)\quad\text{对任意草稿}\ q\ \text{恒成立}\ }

结论：无论草稿 $q$ 多差，输出都精确服从目标分布 $p$ 。草稿质量只影响接受率（速度），绝不影响正确性——方法从不盲信草稿，只把它当提议，再用 $p$ 做数学校正。

六、贪心是采样的特例

温度 $\to 0$ 时 $p,q$ 退化成 one-hot。草稿提议它的 $\arg\max$ ，则 $q(x)=1$ ：

\text{接受概率}=\min\!\left(1,\frac{p(x)}{q(x)}\right)=\min\big(1,p(x)\big)=p(x)= \begin{cases}1,& x=\arg\max p\\ 0,& x\neq\arg\max p\end{cases}

即贪心下「接受 $\iff$ 草稿 token 等于目标 $\arg\max$ 」。

⚠️ 注意：这只在贪心成立。采样模式下，接受某 token 只意味着「目标也给它足够概率（ $p(x)$ 不比 $q(x)$ 小太多）」，并不意味着它是目标的 $\arg\max$ 。反例： $q=\{A:0.5,B:0.3,C:0.2\}$ 、 $p=\{A:0.4,B:0.5,C:0.1\}$ ，草稿提议 $A$ （其 argmax），接受概率 $\min(1,0.4/0.5)=0.8>0$ ， $A$ 有 $80\%$ 被接受，可目标 $\arg\max$ 是 $B$ 。这正是投机采样要复现整个分布、而非只复现众数的体现。

七、加速能有多少

设接受率 $\alpha$ ＝草稿 token 平均被接受的比例，块长 $K$ ，则每次目标前向的期望产出 token 数约为

\mathbb{E}[\text{产出}] \approx \frac{1-\alpha^{\,K+1}}{1-\alpha}

加速取决于三件事：草稿有多像目标（ $\alpha$ 越高越好）、草稿器有多便宜、块长 $K$ （越大单步潜在产出越多，但早早被拒时浪费也越多）。实践中匹配良好的草稿/目标对通常拿到 2–3 倍解码加速。

重要前提：投机解码只在显存带宽瓶颈下有效，即小 batch / 低延迟 / 单流场景。在大 batch 高吞吐服务里，GPU 本就被算力打满，「并行验证几乎免费」的前提失效，收益大幅缩水。

八、草稿从哪来：方法谱系

草稿来源	代表方法	特点
独立小模型	Leviathan’23 / Chen’23	用小模型给大模型起草；要求同词表；最原始
自起草·并行头	Medusa、Blockwise Parallel	在目标模型上加轻量预测头并行猜，配树形注意力；Medusa 基础版用「典型接受」放松了精确性
自起草·特征层	EAGLE / EAGLE-2 / EAGLE-3	在隐状态特征层自回归起草，复用目标输出头，保留因果链，草稿更准
自起草·跳层/早退	Draft & Verify（自投机）、Kangaroo	让目标模型自己跳过部分层快速起草，无需额外模型
多 token 预测（MTP）	Gloeckle’24、DeepSeek MTP	训练即预测多个未来 token，推理时该模块天然可当草稿器
检索 / n-gram	REST、Prompt Lookup	从 prompt 或语料库直接抄，无需任何模型；重复多的任务（摘要、改代码）很划算
Jacobi 并行	Lookahead Decoding	不用草稿器，用 Jacobi 迭代并行求解，亦为无损

树形投机（tree speculation）：不止给一条线性草稿，而是给一棵候选分支树，用「树形注意力」在一次批量前向里同时验证多条路径、取最优路径接受，进一步提高单步期望接受长度（SpecInfer、Sequoia、EAGLE-2）。

九、与 DeepSeek 的联系：MTP 当草稿

DeepSeek-V3 / V4 的 MTP（Multi-Token Prediction）模块被训来「在已知真实下一 token 的条件下预测再下一个 token」，与主模型同分布、本就是模型的一部分，是现成的优质草稿器：

推理时不丢弃 MTP，而是用 MTP 头起草、主模型验证；
V4 的 MTP 深度 $D=1$ ，相当于一次往前看 1 个 token，接受时大致「2 个 token 一拍」地产出；
吸引力在于：同一个为改进训练而加的模块，推理时原样拿来加速，且保持输出分布不变。

十、相关论文清单

截至 2026-05，按主线整理；arXiv 编号均已逐条联网核对。

A. 奠基工作

论文	时间	链接	一句话核心
Blockwise Parallel Decoding for Deep Autoregressive Models（Stern et al.）	2018-11	1811.03115	并行预测多步、回退到最长合规前缀，投机解码的思想雏形（NeurIPS’18）
Fast Inference from Transformers via Speculative Decoding（Leviathan et al., Google）	2022-11	2211.17192	正式提出投机解码 + 无损采样证明，2–3× 加速（ICML’23）
Accelerating LLM Decoding with Speculative Sampling（Chen et al., DeepMind）	2023-02	2302.01318	同期工作，给出修正拒绝采样方案，保持目标分布

B. 自起草（无需独立草稿模型）

论文	时间	链接	一句话核心
Draft & Verify: Self-Speculative Decoding（Zhang et al.）	2023-09	2309.08168	目标模型跳过中间层自起草，单次前向验证，无损
Medusa: Multiple Decoding Heads（Cai et al.）	2024-01	2401.10774	加多个轻量头并行猜 +1/+2/+3 位 + 树形注意力
EAGLE: Rethinking Feature Uncertainty（Li et al.）	2024-01	2401.15077	在特征层自回归起草，无损，1.6× 快于 Medusa（ICML’24）
EAGLE-2: Dynamic Draft Trees（Li et al.）	2024-06	2406.16858	上下文相关的动态草稿树，较 EAGLE 再快 20–40%（EMNLP’24）
EAGLE-3: Training-Time Test（Li et al.）	2025-03	2503.01840	多层特征融合 + 训练时测试，进一步放大加速
Lookahead Decoding（Fu et al.）	2024-02	2402.02057	Jacobi 并行迭代，无需草稿器，精确无损（ICML’24）
Better & Faster LLMs via Multi-token Prediction（Gloeckle et al., Meta）	2024-04	2404.19737	多 token 预测训练目标，可复用为自起草（NeurIPS’24）

C. 树验证 / 服务系统

论文	时间	链接	一句话核心
SpecInfer: Tree-based Speculative Inference（Miao et al.）	2023-05	2305.09781	候选 token 树 + 树形并行验证，面向 LLM 服务（ASPLOS’24）
Sequoia: Scalable, Robust, Hardware-aware（Chen et al.）	2024-02	2402.12374	动态规划求最优草稿树 + 跨温度稳健的采样验证（NeurIPS’24）

D. 检索 / 草稿训练

论文	时间	链接	一句话核心
REST: Retrieval-Based Speculative Decoding（He et al.）	2023-11	2311.08252	用检索代替草稿模型，从数据库取候选（NAACL’24）
DistillSpec: via Knowledge Distillation（Zhou et al.）	2023-10	2310.08461	蒸馏让草稿对齐目标，提升接受率 10–45%（ICLR’24）
Online Speculative Decoding（Liu et al.）	2023-10	2310.07177	在线持续更新草稿模型以适配查询分布（ICML’24）

E. 综述

论文	时间	链接	一句话核心
Unlocking Efficiency: A Comprehensive Survey of Speculative Decoding（Xia et al.）	2024-01	2401.07851	系统梳理草稿器选择与验证策略（ACL’24 Findings）
Speculative Decoding and Beyond: An In-Depth Survey（2025）	2025-02	2502.19732	更新版综述，覆盖树验证、自起草、多模态等新进展

附注

无损与否：接受/拒绝采样（Leviathan、Chen、EAGLE、Lookahead 等）严格保持目标分布；Medusa 基础版的「典型接受」是用精确性换速度的放松。
同词表要求：模型类草稿方法需草稿与目标共享分词器/词表；检索类、自起草类天然满足。
适用边界：投机解码是延迟优化，主打小 batch / 交互式场景；大 batch 高吞吐下收益有限。
与本博客其他笔记的联系：DeepSeek MTP 见 DeepSeek 系列论文清单；其设计在 DeepSeek-V3（2412.19437）中提出、V4 沿用。