Speculative Verification: Exploiting Information Gain to Refine Speculative Decoding

1. 动机:fixed-k SD 的"末段浪费"问题

1.1 历史脉络:从"猜更准"到"猜得短一点也行"

Speculative Decoding(SD,Leviathan 2023)的逻辑很简单:让一个小 draft model 先 autoregressively 走 k 步,然后让大 target model 把这 k 个 token 一次性 forward 一遍,用 rejection sampling 验证。每次 verify 至少能 commit 一个 token(target 自己的那一步是 free 的),最多能 commit k+1 个。k 越大期望接受越多 → 越省 wall-clock。

但故事在大 batch 下崩了。论文的 preliminary 测量给出了两个非常刺眼的数字:

• 40%+ 的 verification compute 被花在最终被拒的 token 上 —— 对 target 而言这就是"白干 forward"。
• 48% 的 SD 步骤 整体上比直接用 target decode 还慢。在大 batch (32–64) 这个比例进一步恶化,SD 甚至变成负优化。

原因不复杂:大 batch 下 target 单步 forward 已经接近 compute-bound,verify 成本接近线性正比于 k;而 SD 的 expected accept length 是次线性的(token 越往后越容易被拒,接受率几何衰减)。所以 fixed-k 在 batch=1 时还能赚,batch=64 时尾巴上的几个 token 几乎不创造价值,只是燃 compute。

研究界的反应是"动态调整 k"。但具体怎么调,出现了三条不同思路 —— 见 1.2。

1.2 别的方案为什么不够 — alternatives 表

预测 acceptance 这件事至少有三类做法,SV 论文逐一论证它们在大 batch 下都不够鲁棒:

核心区别有两点值得反复咀嚼:

1. SV 用的是第二个独立模型给的信号,而不是 draft 自身的内省信号。"draft 自己估自己有多准"在信息论上有天花板:它最多用 H(draft 内部),看不到 target。引入一个独立的 peer,只要不与 draft 完全统计独立(modern LLM 训练数据高度重合,这条几乎自动成立),就能拿到正的 information gain。
2. SV 调的是 verify length 而不是 draft length。这是一个低调但关键的转向 —— 见 1.3。

1.3 为什么是 verify length 而不是 draft length

直觉上"少猜几步就行了",draft length 看似最自然的杠杆。但在生产 serving 场景,draft 和 verify 的成本结构不一样:

• Draft 是 sequential:从位置 1 写到位置 k 必须逐 token autoregressive。先验它要短,意味着在没看到后续 token 之前就拍板,信号最弱(只有 entropy)。
• Verify 是 parallel forward:target 一次拿到 k 个 token 一起算。verify 完之前的状态对每一位 drafted token 都已经写在那里 —— 此时 SV 可以拿 draft 的已写出 token,逐位 query companion 模型给出的 prob,得到一个 per-position acceptance 估计。信号比 draft-time 强得多。

换句话说:draft length 的决策点太早,信号还没到;verify length 的决策点是"已经写完 8 个 token,现在决定送几个进 target",这时位置-by-位置的接受概率可以算出来。SV 把决策点向后推到信息密度最大的瞬间。

更进一步:SV 也没有动 draft 流程 —— draft 还是按固定 k(比如 5 或 7)往前写。SV 只在 verify 阶段决定"送 0~k 中的哪一段进 target"。verify_length ≤ draft_length 始终成立。这种最小侵入性是 SV 能附加在 EAGLE-3 / LayerSkip 等 self-spec 之上的关键。

1.4 估 IG 自身要花钱 — 这个生意划算吗?

论文必须回答的硬问题:companion model 自己也要 forward,它会不会把省下的 verify 又烧回去?

Table 3 给了答案。以 Qwen2.5 (1.5B/0.5B/32B) 为例:

• Verification compute 减少: 16 TFLOPs / 78 (~20%)
• Companion 增加: 1 TFLOPs (~1.3%)
• 净节省: ~18%

更直白地说,companion 的 incremental cost 大约是 verify 节省的 1/16。系统层面再用 MPS 让 companion 与 verify overlap,大部分隐藏在 verify 的等待气泡里。预算确实划算 —— 但只在大 batch 下;小 batch 时 verify 本来就便宜,companion 是纯负担,这也是论文 Figure 7 中 batch=1 时 SV 略输的来源。

2. 背景速查

3. SV 整体框架

从 control-flow 角度看,SV 在每一轮 SD step 的时序大致是:

3.1 关键非平凡点

• companion 不参与 verify:它不替代也不前置 target,只贡献分布信号。区别于 staged SD —— staged SD 让中间模型对 draft 做一次 speculative sampling,然后剩下的进 target;那是一个 "lossy filter",受中间模型能力 cap。SV 的 companion 不做 sampling,只做"打分"。
• 统计独立性是 SV 的最弱前提:论文反复强调,只要 P_c 和 P_d 不完全独立,observing P_c 就能给 X(=acceptance)带来 positive info gain,不需要"draft–companion similarity ≈ draft–target similarity"这种强相关。Modern LLM 共享数据(C4, Wikipedia, Common Crawl),独立性几乎不可能成立。
• P̂(T_i | S, A) 是 offline 估:训练前用 ShareGPT/HumanEvalPack 跑一遍标准 SD,记录 (S, A, accept?) 三元组,做 adaptive binning(数据稠密处更细),得到一张 lookup 表。inference 时 O(1) 查表。这是 SV "cheap online estimator" 的真正实现 —— 不是真有什么实时学习,是预先标定 + 查表。

4. 两个指示量 S 与 A

SV 选择 Y = (S, A) 作为条件随机变量。两者扮演的角色是互补的:

• S 是分布层面对齐度:整个 vocab 上的 1 − TV。S 大 → 当前 context 对 draft 与 companion 都"容易",经验上 target 的分布也类似,token 普遍易被接受。但 S 是 token-agnostic 的:它衡量"这一步整体好不好搞",不区分具体写出哪个 token。
• A 是具体 token 层面的接受概率:就是 SD 的 rejection-sampling 公式,只不过 target 换成了 companion。A 大 → companion 也认这个特定 token,target 大概率也认。

论文 Appendix B.1 报告:S 单独贡献 4–13% info gain,加上 A 之后跳到 30–40%(Table 1 chat:48%, code:37% with adaptive binning)。也就是说token 级信号 A 比分布级信号 S 重要约 5×。直觉上,这是因为 LLM 的接受瓶颈往往不是"context 难易",而是"draft 这个 token 是不是 outlier"。

4.1 Worked example: 计算 S 和 A

假设一个简化 vocab {猫, 狗, 鸟, 鱼},某位置:

Draft 采样到 t_d = "狗"。则:

• S = 0.40 + 0.30 + 0.10 + 0.05 = 0.85(分布很接近)
• A = min(1, 0.40 / 0.30) = 1.0(companion 给 "狗" 的 prob 比 draft 还高 → 必然接受)

查表 P̂(accept | S=0.85, A=1.0) ≈ 0.93。这位置 "强力推送 verify"。

对比另一种情况:t_d = "鱼",A = min(1, 0.10/0.05) = 1.0,但 P_d(鱼)=0.05 本身就是低概率 outlier —— 实际 lookup 表会反映这点(low frequency 区域 acceptance 更不稳)。两个量缺一不可。

4.2 反向论证:只用 S 行不行?

论文 Table 1 的"5×5 binning"给出 H(X|S, A) 与 H(X) 的对比。如果只用 S(等价于砍掉 A 维度),IG 仅 4–13%,relative reduction 不到 10%,远低于论文阈值。物理直觉:S 是整列上的全局对齐,而真正决定单 token accept 的是那一行的 condition(即 A)。

5. Verification length 的动态搜索

给定 P̂(T_i | S_i, A_i),要从 γ ∈ {1, ..., k} 选最优值。期望接受 token 数:

Goodput 即 (E[N|γ] + 1) / latency(γ) —— 加 1 因为 verify 至少额外写一个 free token。SV 从 γ=1 开始递增,只要 goodput 仍上升就继续,一旦下降就回退。论文证明 goodput 关于 γ 是 concave:

• γ 小时 GPU 没填满,latency 增长缓 → 边际收益高;
• γ 一过 compute saturation 拐点,latency 线性增,而 cumulative accept prob 几何衰减 → 边际收益骤降。

所以 first-derivative 式的 hill-climbing 即可,O(k) 一次扫描,k=7 时几十次浮点乘法,完全是 cheap online。

5.1 Batch 模式下的贪心扩展

多查询同时存在时,SV 维护一个空的"待验证 token 集",每轮挑跨 query 边际增益最大的下一个 token 加入,只要 batch 级 goodput 还在涨就继续。这意味着某些 query 这一轮可能根本没 token 进 verify。但 target 那一步仍会从自己的分布在该 query 的"下一位置"采一个 token —— forward progress 永不卡住。

6. Worked example: 8-token rollout

假设 draft length k=8。draft 顺序写出:"我 / 今天 / 想 / 去 / 公园 / 看 / 一下 / 樱花"。每位置 SV 计算 (S, A) 并查表得到 P̂_i:

计算 E[N | γ]:

SV 从 γ=1 起递增。γ=5 时 1.09 仍是局部最大 —— 等等:γ=4 是 1.12 > γ=5 是 1.09,所以 SV 到 γ=5 时发现下降,回退,选 γ*=4。

Fixed-k=7 SD 在这一步会送全部 7 位进 target。等价 latency 5.2ms,但有效贡献 E[N]=3.58,goodput=0.88;比 SV 的 γ*=4 (1.12) 慢 27%。被白白 forward 的 token #5/#6/#7 中,#6 和 #7 几乎肯定被拒(累乘到 P̂≈0.012)。

7. 系统侧:把 companion 的开销藏起来

纯算法层面 SV 已经"省了 verify",但工程上还有两个关键决策:

7.1 NVIDIA MPS + overlap

SV 把 draft / companion 与 target 放进不同进程,通过 NVIDIA Multi-Process Service 让两者并发占用同一张 GPU。MPS 配置上 draft+companion 占 30% SM 资源,target 占其余。两个 micro-batch 同时跑:第 t 步的 verify 与第 t+1 步的 draft+companion。这样 companion forward 大部分时间被 verify 的 latency 吞没。

注意一个细节:profiling latency 必须在 draft+companion 同时运行的状态下测(因为有干扰),否则 γ 搜索会用错误的 latency 表。论文专门提到这一点。

7.2 Prefill 时的 logit 跳过

prefill 阶段 draft / companion 不需要算 logits(它们的输出在 prefill 还没用),论文跳过这一步,prefill overhead 降 3–5%。但即便如此,SV 的 prefill throughput 仍比 SD 低 ~10%(比 target-only 低 30%)。这是 RAG / 短输出场景下 SV 优势收窄的根源。

7.3 输入 tensor compaction + CUDA graph

因 verify length 是 query-级可变的,padding 会浪费大量算力。SV 实现了 variable-length verify 的 input tensor 紧凑化,并修了 FlashInfer 在 CUDA graph 下的 attention bug(让 graph capture 与 padded input 兼容)。这些是必须做对的工程,不是可选。

8. 实验关键结果

8.1 Table 3 — 算账(最承重)

关键观察:

• 当 baseline SD accept rate 极低时(Llama2 68M draft / 13B target,0.14),SV 的相对收益最大(−44.6% TFLOPs)。这与直觉一致:坏 baseline 的尾部最浪费,SV 的"早停"价值最大。
• Companion 的 incremental cost 是 1–4 TFLOPs,而 verify 节省 16–50 TFLOPs。大约 5–20× 杠杆。
• SV accept rate 普遍升高(0.56→0.62, 0.14→0.61),但这要小心解读:它是"被送进 verify 的 token 中"的接受率,不是 sequence-level 的接受率。SV 主动剔除了低质量尾部,显著提升了"分母"。

8.2 Table 1 — info gain 标定

Llama2 13B/160M/68M 在 chat (ShareGPT) 与 code (HumanEvalPack) 上,使用 adaptive binning:

• chat: H(X)=1.38, H(X|S,A)=0.91, IG=0.48 (35%)
• code: H(X)=1.78, H(X|S,A)=1.42, IG=0.37 (21%)

chat 比 code 信号更强 —— 直觉是 chat 的 token-level 模式更稳,companion 给的预测更准;code 的多样性让 acceptance 本身更高熵,IG 比例下降。

8.3 EAGLE-3 整合 — 一个值得标注的失败模式

把 SV 套在 EAGLE-3 上时,小 batch 下反而轻微变慢。原因:EAGLE-3 自身 draft accept 率才 26-27%,意味着 (S, A) 的输入信号本身偏低、companion 难找出靠谱的早停点;同时小 batch 下 verify 本来就便宜,companion 是纯负担。换 SV 自带的更强 draft 后回升 56%。"draft 越烂 + batch 越大 → SV 越赚",这条经验法则可以记住。

8.4 Fairness

1024 query 中,verify 数最少的底部五条平均 2.9 token / step(整体 4.1)。47% step 仅 1–2 token verify,但 39% 仍能拿到 4–5 token —— SV 不挑食得太严重。target verify 至少返回一个 token 保 forward progress 这件事是结构性保证,不靠调度器。

9. 与同类工作对比

简化记忆:所有同类要么调 draft,要么用 draft-内部信号;SV 是唯一一个(a) 调 verify length 且 (b) 用外部 peer model 信号的组合。这两条选择是耦合的:外部信号在 verify 决策点才能拿到充分的 per-position 估计。

10. 局限 / 个人 take / 待验证

• Companion 的获取被一带而过:论文说"fine-tune draft / quantize draft / 现成 model"都行,但 P̂(T|S,A) lookup 表是每对 (D,C,T) 配置都要重新标定的。生产环境每次换 target 都要重跑 ShareGPT 标定?这块工程成本被低估。
• (S, A) 的 lookup 表是离线 binned 的,意味着 distribution shift(domain 切换、长度外推、tool-use)时 P̂ 可能严重失准。论文未做 domain transfer 实验。
• Prefill-heavy workload (RAG, summary) 仍只有 1.39× 提速(decode-heavy 是 1.4–1.9×)。companion 在 prefill 阶段是纯加法,这个结构性劣势改不动。
• EAGLE-3 + SV 的小 batch 退化是真实信号:SV 不是"哪都能加"的开关,弱 draft + 小 batch 是它的明确禁区。
• fairness 分析略弱:1024 query 整体平均给的是均值,bottom-5 给了 2.9,但 worst-case query 可能整批仅 1 token 或 0(被 target free token 兜底)。tail latency 没报。
• 没和 RL post-training rollout 场景对比:SV 的"省尾部"特性恰好可能与 RL on-policy rollout 的"早期 token 重要,后期 reward 稀疏"匹配 —— 但论文没碰这个方向。

10.1 待验证(我会做的下一组实验)

1. 把 P̂(T|S,A) 改成 online sliding-window 估计,看 distribution shift 鲁棒性。
2. 验证"draft 极弱时收益最大"的 monotonicity:从 68M draft 一路放大到 7B,SV 相对收益曲线长什么样?(Table 3 暗示是单调下降但论文没给曲线)
3. SV + EAGLE-3 失败原因是 draft 弱还是 (S, A) 信号本身在 self-spec 下 collapse?(EAGLE-3 的 draft head 与 target 共享 hidden,P_d 与 P_c 可能反而不独立)
4. 把 companion 替换成更便宜的"distilled head"(类似 Medusa head 但只产 P_c),companion forward cost 进一步压缩到 verify 的 1% 以下,会发生什么?
5. "verify length 而非 draft length"是否能配合 EAGLE-2 的 dynamic tree —— 即"动态 tree shape × 动态 verify cut"两条杠杆同时开?

11. Memory points