Speculative Decoding 为什么是 Lossless 的 — 详细证明教程

教程 · Chinese walkthrough with full proof · 面向数学基础较弱的工程师
Source: Leviathan et al. 2023 (arXiv:2211.17192) · Chen et al. 2023 (arXiv:2302.01318)
关键词: speculative decoding · rejection sampling · lossless · importance sampling · acceptance probability

速读卡片 (TL;DR)

一句话:这篇教程会从头到尾、用最小的数学跨度,给你证明:speculative decoding 通过 min(1, p/q) 接受 + (p − q)⁺ 重采样,产出 token 的分布正好等于直接用 target 模型自回归采样的分布——没有偏差、没有近似、没有"几乎"。

输出分布偏差 (lossless)

min(1, p/q)

接受概率公式

P(out=x) = p(x)

最终结论

读完你应该能:(a) 解释为什么不能直接用 importance sampling;(b) 推导接受概率为什么是 min(1, p/q);(c) 用一个 3-vocab 的例子手算"接受/拒绝/重采样"的全部概率;(d) 知道 lossless 在浮点 / 温度 / 量化下何时失效。

1 · 为什么需要 lossless guarantee?

1.1 起源

2022 年底到 2023 年初,Google (Leviathan et al.) 和 DeepMind (Chen et al.) 独立而同时提出了一个完全相同的核心思想:用一个小模型 (draft) 提议几个 token,再让大模型 (target/verifier) 一次性"打分",通过一种修正过的 rejection sampling 决定接受或重采样。两篇论文都给出了一条现在看是 spec decoding 招牌的保证:整个流程产出 token 的分布,和直接从 target 采样的分布完全相同。

这条保证在工程上有几个名字:lossless / distribution-preserving / exact / unbiased。意思都一样:加速没有以"偷偷改了你想要的分布"为代价。

1.2 为什么这条保证必须存在

分两类场景看:

场景	如果 lossless 被打破会怎样
Inference serving (部署给用户)	用户拿到的输出分布 ≠ 模型本应产出的分布。质量评估 (BLEU / ROUGE / pass@k) 可能轻微下降,但更糟的是 — 用户看到的多样性、长尾 token 的概率全都变了,而你不知道改了多少。
RL post-training (RLHF / GRPO / PPO)	RL 的训练分布必须等于当前 policy 的采样分布。spec decoding 用来加速 rollout,如果输出分布漂了,那 advantage / reward 全错,GRPO 的 importance sampling correction 也会失效。这就是为什么 NeMo-RL / ReSpec / SPEC-RL 这一系列论文都把 lossless 当成"不能动"的红线。

所以这条保证不是"锦上添花",它是 spec decoding 在 RL 场景下能用的前提条件。本教程要回答的就是:这个保证是怎么数学上成立的?

2 · 符号表 + 直觉热身

2.1 我们要证什么 (用人话说)

给定当前已经写出来的 prefix(比如 "今天天气"),target 模型给出"下一个 token"的概率分布,记作 p。draft 模型给出另一个分布,记作 q。Speculative decoding 的流程是:

从 q 里采样一个候选 token,叫它 t
用某个概率决定"接受 t"还是"扔掉 t"
如果扔掉,从一个修正过的分布里再采样一个 token

我们要证明:这个流程整体输出的 token,服从 p 这个分布——和你直接从 target 采样一模一样。

2.2 符号表 (重要,后面所有公式都用这些)

vocab · 词表,本教程用一个超小的玩具词表 {cat, dog, fish} (只有 3 个 token) 演算。

x · 一个具体的 token。"对所有 x 求和" = 对 cat / dog / fish 三个值各算一次再加起来。

prefix · 已经生成出来的前文。本教程里大部分时候省略,因为我们只看"下一个 token"。

p(x) · target 模型在当前 prefix 下,认为下一个 token 是 x 的概率。例如 p(cat) = 0.6 意思是 target 觉得下一个是 cat 的概率 60%。

q(x) · draft 模型在同一 prefix 下,认为下一个 token 是 x 的概率。

t · 从 q 采样得到的候选 token (一个具体的值,如 t=cat)。

a(x) · 接受概率,定义为 a(x) = min(1, p(x)/q(x))。意义:如果候选 token 是 x,我们以 a(x) 的概率接受它。

r · [0, 1] 上的均匀随机数。算法实现里:采 r 后,如果 r < p(t)/q(t) 就接受,否则拒绝——和"以 min(1, p/q) 概率接受"等价。

(p − q)⁺(x) · "正部",定义为 max(0, p(x) − q(x))。意思是 p 比 q 多出来的部分,如果 q 比 p 还大就记 0。

Z · 归一化常数,Z = ∑_x (p(x) − q(x))⁺。它的作用是把上面那个非负函数变成一个合法的概率分布。

p′(x) · "拒绝时的重采样分布",定义为 p′(x) = (p(x) − q(x))⁺ / Z。

P(...) · 表示"某事件的概率"。比如 P(output = cat ∧ accept) 表示"采样到 cat 并且被接受"的联合概率。

min(p, q)(x) · 简写,表示 min(p(x), q(x)),即两个分布在 x 上较小的那个值。

2.3 全程使用的运行例

本教程 70% 的时间都用下面这一对小分布,把 vocab 限制在 cat / dog / fish 三个 token,这样所有概率都能写出来、加起来、画出来:

target p = (p(cat), p(dog), p(fish)) = (0.6, 0.3, 0.1)
draft q = (q(cat), q(dog), q(fish)) = (0.4, 0.5, 0.1)

target 觉得 cat 最有可能 (0.6),但 draft 觉得 dog 最有可能 (0.5)。两个分布在 dog 上意见分歧最大 (q 比 p 多了 0.2),而在 fish 上完全一致 (都是 0.1)。我们关心的是:从 q 采样后再做 spec decoding 的"修正",最终输出会服从 p 而不是 q。

2.4 一个被讨厌的小问题先放在这

命名混乱预警: Leviathan 2023 用 p = target, q = draft;Chen 2023 用 p = draft, q = target,正好反过来。现代实现 (vLLM, EAGLE 系列) 都跟随 Leviathan 的约定。本教程统一用 p = target, q = draft。读其它资料时记得对照。

3 · 想法的源头: importance sampling 复习

spec decoding 的本质灵感来自 importance sampling (IS),所以我们先花 3 分钟温习。

3.1 IS 解决什么问题

假设你想计算 target 分布 p 下某个函数 f 的期望 (比如"reward 的平均值"),写法是:

𝔼_p[f] = ∑_x p(x) · f(x)

(即 "对所有 x 求和 p(x) 乘 f(x)")

但你不能直接从 p 采样 (比如 p 太贵了),只能从 q 采样。怎么办? IS 的小技巧是:在求和里凭空乘 q(x)/q(x) (= 1),然后重新组合:

𝔼_p[f] = ∑_x p(x) · f(x)
= ∑_x q(x) · p(x)q(x) · f(x)
= 𝔼_q[ (p/q) · f ]

意思是:从 q 采样一堆样本 x₁, x₂, ..., 算 (p(xᵢ)/q(xᵢ)) × f(xᵢ) 的平均值,这个平均值就是 E_p[f] 的无偏估计。p(x)/q(x) 叫 importance weight。

你想问 target 的意见,但只问到了 draft 的回答;那就给 draft 的每个回答加个权重 p/q,补回 target 视角下应有的"重要性"。

3.2 用 cat/dog/fish 例子

x	p(x)	q(x)	p/q (权重)
cat	0.6	0.4	1.5 (target 比 draft 更想要)
dog	0.3	0.5	0.6 (target 没那么想要)
fish	0.1	0.1	1.0 (一致)

p/q 越高,说明 target 比 draft 更"想要"这个 token。在 cat 上 p/q = 1.5 (target 想要 1.5 倍),在 dog 上 p/q = 0.6 (target 没那么想要)。这两个比值是 spec decoding 接受/拒绝判断的核心信号。

3.3 IS 不直接好用的地方

IS 给的是期望的估计。但 spec decoding 要的是样本本身—— 我们要的是真的从 p 中"抽"出一个 token 来拼到序列里,不能交给下游一个加权平均值。把 IS 改造成"采样工具"的过程,就是 rejection sampling。

4 · Rejection Sampling: 把 IS 改造成"采样"工具

4.1 经典 rejection sampling 复习

经典 RS 的设定: 想从 p 采样,只能从 q 采样。已知存在常数 M ≥ 1 使得对所有 x,M·q(x) ≥ p(x) (即 M·q 是 p 的包络/envelope)。流程:

从 q 采样 x
采均匀随机数 r ∈ [0, 1]
如果 r < p(x) / (M·q(x)),接受 x;否则拒绝,重新来。

正确性证明留给经典教科书,直观是: 用 M·q 这个"罩子"把 p 罩住,然后在罩子下"打孔",p 的形状就被你按比例采样出来了。

4.2 但经典 RS 不适合 spec decoding

问题是: 我们需要先知道 M (那个保证 M·q ≥ p 的常数)。在 LLM 里,p 和 q 是巨大模型的输出,在每个 prefix 上 M 都不一样,而且最坏情况下 M 可以巨大 (一个 token 在 q 里几乎为 0,在 p 里中等概率,p/q 就爆炸)。这会让接受率 1/M 趋近 0,完全失去加速意义。

4.3 Spec decoding 的小聪明: 不需要 envelope

Leviathan / Chen 的关键观察是: 我们不需要非要把 p 罩住。如果 q 在某点比 p 小,那就无脑接受 (反正 draft 给得不够多,接受了正好);如果 q 在某点比 p 大 (draft 给多了),那就按比例打折接受,然后从"残差"里补采。

a(x) = min(1, p(x)q(x))

(即 "接受概率 = 1 与 p(x)/q(x) 中的较小者")

读法: 如果 target 觉得 x 比 draft 觉得的更可能 (p ≥ q),那 draft 给出的 x 就 100% 接受;否则按 p/q 这个比例打折接受。这是一个直觉上"对得起 target 也对得起 draft"的折中。

cat 上 p/q = 1.5,但接受概率不可能 > 1,所以裁到 1.0(绿色,无脑接受);dog 上 p/q = 0.6,按比例接受 60%(红色);fish 上正好 1.0。这就是 a(x) = min(1, p/q) 的图像。

但光这一步还不够: 如果某个 x 被拒绝了 (比如采到 dog 但 r > 0.6),我们必须有个"补救"步骤,否则总分布就不对了。这就是修正分布 p' 出场的地方。

5 · 主定理: spec decoding 是 lossless 的

5.1 算法陈述 (一个 token 版,无 γ-step)

给定当前 prefix,target 分布 p,draft 分布 q。执行下面三步,产出一个 token:

SpecSampleOne (一步 spec 采样)

提议:从 q 采样一个候选 t,即 t ∼ q。
判定接受:独立采均匀随机数 r ∼ Uniform[0, 1]。
如果 r < min(1, p(t)/q(t)) (等价于 r·q(t) < p(t)),则接受 t,直接 return t。
否则:从修正分布 p'(x) = max(0, p(x) − q(x)) / Z 重新采样一个 token,return 它。其中 Z = 对所有 x 求和 max(0, p(x) − q(x))。

5.2 主定理

定理 (Leviathan 2023, Appendix A.1; Chen 2023, Theorem 1) · 对任意离散分布 p, q (定义在同一个 vocab 上),上面 SpecSampleOne 算法 return 的 token,服从分布 p。即 P(output = x) = p(x) 对所有 x 成立。

整个流程是一个二选一的随机过程: 要么"采 t 接受",要么"被拒后从修正分布重采"。我们要证明无论走哪条路,综合起来 token x 出现的概率正好是 p(x)。

6 · 详细证明 (核心节)

把证明拆成 3 步。每步给出 (a) 数学推导,(b) 直观解释,(c) 用 cat/dog/fish 验证。

6.1 总策略

我们要算的是: 对任意一个 token x,output 等于 x 的总概率。这个事件可以拆成两个互斥的小事件:

P(output = x) = P(output = x ∧ accept) + P(output = x ∧ reject)

接下来三步分别处理这两项,然后合并。

6.2 Step 1 · 计算 P(output = x ∧ accept)

Step 1 数学

"output 是 x 并且被接受",意味着第 1 步采样时正好采到了 x (概率 q(x)),并且 r < p(x)/q(x) 被判接受 (概率 a(x) = min(1, p(x)/q(x)))。两个采样独立,所以:

P(output = x ∧ accept) = q(x) · a(x) = q(x) · min(1, p(x)q(x))

把 min 拆开看两种情况:

如果 p(x) ≥ q(x): min(1, p/q) = 1, 所以 q(x) · 1 = q(x) = min(p(x), q(x))
如果 p(x) < q(x): min(1, p/q) = p/q, 所以 q(x) · p/q = p(x) = min(p(x), q(x))

两种情况都等于 min(p(x), q(x))。所以:

P(output = x ∧ accept) = min(p(x), q(x))

"采到 x 并接受"的概率,正好是两个分布在 x 这一点的较小值。这个量叫"下包络 (lower envelope)",代表 p 和 q 在 x 上"都同意采样"的那部分概率。如果 p 和 q 都觉得 x 概率高,那 min 就高;只要其中一个低,那 min 就低。

cat: p=0.6, q=0.4, min=0.4。dog: p=0.3, q=0.5, min=0.3。fish: 都=0.1, min=0.1。这三个值加起来是 0.8,是"被接受时输出某个 token 的总概率"。

6.3 Step 2 · 计算 P(reject) (被拒的总概率)

Step 2 数学

"接受"事件按 token 拆开,概率是各 token min(p,q) 之和:

P(accept) = ∑_x P(output = x ∧ accept) = ∑_x min(p(x), q(x))

因为接受/拒绝是互斥且必有其一, P(reject) = 1 − P(accept):

P(reject) = 1 − ∑_x min(p(x), q(x))

拒绝率正好是"两个分布在 vocab 上的总差距"——分布越接近,min 求和越接近 1,拒绝率越接近 0;分布完全不一样 (q 和 p 没有 token 重叠),min 求和 = 0,拒绝率 = 1 (永远拒绝)。这个量叫 total variation distance,是 spec decoding 加速效果的根本指标。

cat/dog/fish 验证:

x	p(x)	q(x)	min(p,q)
cat	0.6	0.4	0.4
dog	0.3	0.5	0.3
fish	0.1	0.1	0.1
合计	1.0	1.0	0.8

所以 P(accept) = 0.8, P(reject) = 0.2。

6.4 Step 3 · 计算 P(output = x ∧ reject) 和最终合成

Step 3a · 重采样分布的归一化常数 Z

定义残差 (p − q)+(x) = max(0, p(x) − q(x))。归一化常数:

Z = ∑_x max(0, p(x) − q(x))

这里有一个非常重要的代数恒等式,后面就靠它合并:

Z = 1 − ∑_x min(p(x), q(x)) = P(reject)

为什么 Z 等于 P(reject)?把恒等式 a + b = min(a,b) + max(a,b) 应用到 p(x) 和 q(x):

p(x) + q(x) = min(p(x), q(x)) + max(p(x), q(x))

而 max(p, q) = p + (q − p)+ = q + (p − q)+,所以 max(p, q) − q = (p − q)+,即:

p(x) − min(p(x), q(x)) = max(0, p(x) − q(x)) = (p − q)⁺(x)

对所有 x 求和: 左边 = 对 p 求和 − 对 min 求和 = 1 − 对 min 求和;右边 = Z。所以:

Z = 1 − ∑_x min(p(x), q(x)) ✓

这个恒等式是整个证明的"核心齿轮"。它告诉我们: 归一化常数 Z 不是某个奇怪的量,它正好等于拒绝概率。这意味着"被拒的总概率"和"修正分布的总质量"是同一个数—— 这种巧合不是凑出来的,是 (p−q)+ 这个公式的设计目的。

Step 3b · P(output = x ∧ reject)

当被拒,我们从 p'(x) = (p−q)+(x) / Z 重采样。所以条件概率:

P(output = x | reject) = p′(x) = (p − q)⁺(x)Z

联合概率 = 条件概率 × 边际:

P(output = x ∧ reject) = P(reject) · p′(x) = Z · (p − q)⁺(x)Z = (p − q)⁺(x)

注意! Z 上下抵消,得到一个非常干净的式子:

P(output = x ∧ reject) = (p − q)⁺(x) = max(0, p(x) − q(x))

代数上 Z 抵消的这一步是设计 (p−q)+ 这个分布的原因—— 设计的人就是想让"边际 × 条件"在合并时干净。如果当初拒绝时不归一化(用 (p−q)+ 作为非概率),Step 3a 的恒等式会保证它"正好"加到 1,但那时它就不是个分布了,采样不了;归一化后再乘回 Z,又把 Z 抵消了。这是个漂亮的循环。

Step 3c · 合并: P(output = x)

把 Step 1 和 Step 3b 加起来:

P(output = x) = P(output = x ∧ accept) + P(output = x ∧ reject)
= min(p(x), q(x)) + (p − q)⁺(x)
= min(p(x), q(x)) + max(0, p(x) − q(x))

分两种情况验证:

如果 p(x) ≥ q(x): min = q(x), max = p(x) − q(x), 加起来 = q(x) + (p(x) − q(x)) = p(x) ✓
如果 p(x) < q(x): min = p(x), max = 0, 加起来 = p(x) + 0 = p(x) ✓

所以无论 p 和 q 在 x 上谁大谁小:

P(output = x) = p(x) ∎

"输出 x"被拆成两部分:(a) min 部分是"两个分布都同意 x 应该有这么多概率"的部分,直接被接受输出;(b) (p−q)+ 部分是"target 比 draft 多想要的部分",在拒绝路径上补回来。两部分加起来正好是 target 的 p(x)。这就是 spec decoding 的灵魂: 用 draft 把容易共识的部分快速确定下来,用拒绝路径修正分歧的部分。

每个 token 上,蓝色 (min) + 绿色 ((p−q)+) 严丝合缝地堆成红色框 (p)。在 cat 上需要补 (p−q)+ = 0.2;在 dog 和 fish 上 p ≤ q,(p−q)+ = 0,只用蓝色就够。这就是为什么最终输出分布 = p。

(选读) 连续分布的情形 — 为什么换成积分还成立

把"对所有 x 求和"换成"对 vocab 上的 Lebesgue 积分",所有 min / max / (·)+ 都按点定义,推导一字不变。本教程不展开,因为 LLM 词表是离散有限的,离散版已经够用。

7 · 几个具体例子 (数值演算)

7.1 例 1: 全程演算 cat/dog/fish

预备量 (从 §6.3 ~ §6.4 算出):

x	p(x)	q(x)	a(x)=min(1,p/q)	min(p,q)	(p−q)+
cat	0.6	0.4	1.0	0.4	0.2
dog	0.3	0.5	0.6	0.3	0
fish	0.1	0.1	1.0	0.1	0
合计	1.0	1.0	—	0.8	Z=0.2

Step 1: 接受路径

P(output=cat ∧ accept) = q(cat)·a(cat) = 0.4 × 1.0 = 0.4
P(output=dog ∧ accept) = q(dog)·a(dog) = 0.5 × 0.6 = 0.3
P(output=fish ∧ accept) = q(fish)·a(fish) = 0.1 × 1.0 = 0.1
P(accept) = 0.4 + 0.3 + 0.1 = 0.8

Step 2: 拒绝总概率

P(reject) = 1 − 0.8 = 0.2。

Step 3: 修正分布 p'

Z = 0.2,所以 p'(cat) = 0.2/0.2 = 1.0,p'(dog) = 0/0.2 = 0,p'(fish) = 0/0.2 = 0。也就是: 一旦被拒,100% 输出 cat。这听起来怪,但符合直觉: 在这个例子里,(p−q)+ 只在 cat 上非零(target 在 cat 上比 draft 多 0.2),所以拒绝补救只能输出 cat。

Step 3 联合概率:

P(output=cat ∧ reject) = 0.2 × 1.0 = 0.2
P(output=dog ∧ reject) = 0.2 × 0 = 0
P(output=fish ∧ reject) = 0.2 × 0 = 0

合并:

x	P(x ∧ accept)	P(x ∧ reject)	P(output = x)	p(x)	match?
cat	0.4	0.2	0.6	0.6	✓
dog	0.3	0	0.3	0.3	✓
fish	0.1	0	0.1	0.1	✓

每行都恢复了 p(x),这就是 lossless 的真实数值演示。

7.2 例 2: 完美 draft (q = p)

如果 draft 的分布完全等于 target,那 (p − q)+(x) = 0 对所有 x,所以 Z = 0,拒绝路径永远不发生 (P(reject) = 0)。每次都接受,达到最大加速。这是为什么 EAGLE / Medusa 等用同源 draft 的方案能拿到最高 acceptance rate。

7.3 例 3: 完全错的 draft (disjoint support)

假设 q 给 cat = 1.0,而 p 只在 dog 和 fish 上有质量 (p(cat)=0)。那 min(p, q)(cat) = 0 (p=0), min(p, q)(dog) = 0 (q=0), min(p, q)(fish) = 0。P(accept) = 0,永远拒绝;每次都进入 (p−q)+ 路径,(p−q)+ = p (因为 q 和 p 不重叠),所以 p' = p。这等于每次都从 p 直接采样—— 没有加速,但仍然 lossless。 spec decoding 在最坏情况下退化成自回归,但永远不会偏。

情况	P(accept)	P(reject)	加速	lossless?
q = p (完美)	1.0	0	最大	✓
cat/dog/fish 例	0.8	0.2	中等	✓
q ⊥ p (不重叠)	0	1.0	无 (退化成 AR)	✓

8 · 常见误解 / 陷阱

Q1 · 拒绝时,为什么不直接从 p 采样?

错。如果拒绝时直接从 p 采样,总分布会是:

P(out = x) = min(p(x), q(x)) + P(reject) · p(x)

这一般不等于 p(x)。具体: 拒绝时如果你"老实"从 p 重采,就双重计算了那些 p 和 q 都同意的部分(min 部分),导致最终分布偏向 p ∩ q 的重叠区,而忽略了 p 中"draft 没覆盖好"的部分。

举例: cat/dog/fish 上,P(reject) = 0.2,如果拒绝时从 p 采样,P(out=cat) = 0.4 + 0.2·0.6 = 0.52 (不是 0.6)。这就破坏了 lossless。

必须用 (p−q)+ 这个有意只补缺口的分布,才能让代数对得上。

Q2 · 为什么是 (p − q)+,不是 |p − q|?

因为我们只想补"target 比 draft 多想要"的那部分。在 q > p 的 token 上 (例如 dog: q=0.5 > p=0.3),draft 已经"过度采样"了,所以接受路径里我们已经按比例打折掉了多余的;此时不需要再"补",只是要避免在拒绝路径再加进去。如果用 |p−q|,你会在 dog 上误加 0.2,把 dog 总概率推到 > 0.3,违反 lossless。

Q3 · 既然 min(1, p/q) 就够,为什么不直接做 importance sampling?

IS 给的是期望的估计 (例如 reward 的期望),不是样本。RL 训练序列、给用户写文章,都需要真实采到的 token,而不是带权重的"虚拟 token"。 IS 的权重无法直接拼成一个序列。Spec decoding 是把"加权"思想变成"接受/拒绝"二值化的版本,从而能产生真正的 token。

Q4 · 浮点精度、KV cache、temperature 都可能破坏 lossless 吗?

是的。证明假设我们能精确计算 p(x), q(x), p(x)/q(x)。在工程上:

用 fp16 / bf16 算 logits,exp 之后做 softmax,p/q 在小概率 token 上数值非常不稳。
target 和 draft 的 KV cache 用了不同 dtype / 量化,p(x) 和"理想 p(x)"之间已经有了误差。
采样温度 T、top-k、top-p、repetition penalty 必须在同一个标准化分布上算 ratio—— 标准做法是把所有这些操作 fold 进 p 和 q,然后再做 spec sampling (Leviathan §2.2 "Standardized Sampling")。如果 target T=0.7、draft T=1.0,那比的是两个不一样的分布,lossless 不再成立。

结论: lossless 是数学上的 exact,工程上是 "lossless within hardware numerics" (Chen 2023 原文用语)。详见 §10。

9 · 多步 / tree-verify 的扩展

9.1 多步 (γ-step) 链式扩展

实际算法一步采 γ 个 draft token,再让 target 一次 forward 计算 γ+1 个位置的 p。然后从左到右逐个判 accept/reject,一旦遇到 reject 就停下来用修正分布重采那一位,丢掉后面的 draft 提议。

每一位的"是否接受"独立用 §6 的逻辑判断,所以每位上局部 lossless。链起来意思是: 第 i 位接受后,prefix 增加了那个 token,target 在 prefix 上的下一位分布 p_{i+1} 是在该 prefix 条件下的分布,而 draft 也是在同一 prefix 条件下采样的 q_{i+1}。所以在每个位置上,前提条件 (prefix) 一致,§6 的证明 1:1 套用。

链式 lossless 的形式归纳: 第一位 lossless ⇒ 第一位输出 token 服从 p(·|prefix);进入第二位,prefix 已经在 target 分布下扩展了一个 token,接下来的判定继续 lossless;以此类推。整段产出的 token 序列服从 target 自回归分布。

9.2 Tree verification (多 draft 分支)

SpecInfer / EAGLE-2 / Medusa 等会让 draft 同时提议多个分支 (一棵树),target 一次 forward 验证所有分支。这种情况下"接受规则"要重新设计 (Token-tree verification),但思想类似:接受规则要保证每个被选出的"叶子路径"上的 token 在条件分布下 lossless。具体公式见:

02_EAGLE_evolution_DFlash.html — EAGLE-2/3 的 dynamic tree verification
SpecInfer (Miao et al.) — 多 sequence rejection 的设计

一旦把 acceptance 规则推广好,整体 lossless 仍然成立,这是 spec decoding 家族能放心扩展到树形结构的根本理由。

10 · 何时 lossless guarantee 失效

失效来源	机制	典型表现
浮点精度	p/q 在 fp16/bf16 下数值误差,某些罕见 token 上可能 ratio 错算几倍	"empirically lossless within numerics" — 大数据集统计指标和 AR 一样,但单个序列可能有微小漂移
Temperature 不一致	target 用 T_p、draft 用 T_q ≠ T_p,比的是不同分布的 ratio	非常常见的 bug;输出分布会偏向 draft 的"风格"
KV cache dtype 漂移	target 跑 bf16,draft 跑 fp8,p(x) 已经不是真正的 target 分布	在 long context 下尤为明显
主动 lossy 系列 (MARS / DropMatch / LK-Losses)	故意放宽接受规则换更高 acceptance,如 lenience l < 1 的 min(p, l·q) 替代	训练 / serving 场景主动选择放弃 lossless 换速度,trade-off 是质量轻微下降

11 · 记忆要点

中心结论 SpecSampleOne 的输出分布 = target 分布 p,无近似无偏差。

关键公式接受概率 a(x) = min(1, p(x)/q(x));拒绝重采分布 p′(x) = (p(x) − q(x))⁺ / Z。

代数核心 Z = 1 − ∑_x min(p, q) = P(reject)。这一步让 (p − q)⁺ 这个非概率的"残差"在归一化时正好和拒绝概率抵消。

Money equation min(p, q) + (p − q)⁺ = p (按点恒成立)。

直观图像蓝色 min = "两边都同意"的部分 (接受);绿色 (p − q)⁺ = "target 比 draft 多想要"的部分 (拒绝补救)。

退化情形 q = p ⇒ 永不拒绝,最大加速;q ⊥ p ⇒ 永远拒绝,退化成 AR,但永远不偏。

陷阱拒绝时不能从 p 重采,会双重计算 min 部分;不能用 |p − q| 替代 (p − q)⁺,会在 q > p 的 token 上多加。

工程红线 Lossless 仅在"target/draft 用同一标准化分布算 ratio"时成立;temperature / top-k / top-p / dtype 必须 fold 进 p 和 q 后再做 spec sampling。

来源 Leviathan et al. 2023 (arXiv:2211.17192),Appendix A.1;Chen et al. 2023 (arXiv:2302.01318),Theorem 1。两篇独立同时给出几乎一致的证明。

本教程改编 / 复述自 Leviathan et al. 2023 和 Chen et al. 2023 的证明,加入了面向工程师的 plain-Chinese 解释、cat/dog/fish 数值演示、money diagram、和工程陷阱列表。原始数学结果归功于上述两组作者。