Speculative Speculative Decoding — 把 draft↔verify 的串行依赖也打掉

1 · 动机:SD 自己也有一道 Pareto wall

1.1 历史脉络: 从 AR 到 SD,然后 SD 内部的串行难题

Speculative decoding (Leviathan 2023, Chen 2023) 的核心 trick 是: 用并行替代串行 —— 让 draft 一次猜 K 个 token,target 在一次 forward 里并行算 K+1 个位置的 logits,然后用 rejection sampling 保证产出分布等价于纯 AR。这是把 token-level 串行依赖打破的第一刀。但每一轮 SD 本身 仍是串行的:

SSD 的设计目标就是把这个 "draft 等 verify、verify 等 draft" 的乒乓打掉,让两者在两台不同 GPU 上真正并行执行:

1.2 别的"破壁"方案为什么不够

SSD 不是第一个想要并行 draft 与 verify 的工作 —— 但前作要么只覆盖一种 outcome、要么动 verifier、要么在大 batch 下崩。

1.3 为什么"双重投机"不平凡 — 它不是再套一层 SD

读到 "speculative speculative" 这个名字,第一反应往往是: 在 draft 上再加一个 mini-draft 去 spec draft 的结果。错。SSD 的 unlock 不在递归,而在预测 verifier 会怎么裁决。三个真正的难点:

1. Outcome 空间是 O((K+1)·V): 一个 verification outcome 由 (k, t*) 唯一确定,k ∈ [0, K] 是接受的 token 数,t* ∈ V 是 bonus token。V ≈ 128k,K = 5 时空间是 ~10^6。穷举不可能 → 必须在预算 B 下选 top-B 个最可能的 outcome。这是 §5 解决的约束优化。
2. cache hit rate vs acceptance rate 的张力: 想让 cache hit 率高,直觉上要让 bonus token 集中(残差分布尖锐),但这往往要求 draft 分布远离 target,而那又会降 acceptance rate。两个目标都进 §3.2 的 Theorem 7 分子分母 → 必须在同一个 sampling 设计里平衡。这是 §6 的 Saguaro sampling 解决。
3. 大 batch 下 cache miss 概率 → 1: batch 元素的 cache hit 是独立事件,batch=b 时 batch 整体命中率 ~ p_hit^b。b=16, p_hit=0.8 → 整 batch hit 率仅 ~3.5%。一旦 miss,整 batch 都得等 backup speculator,这时 backup 必须极便宜(随机 token / n-gram),否则 SSD 比 SD 还慢。这是 §7 的 Saguaro fallback 解决。

三个问题环环相扣。Saguaro 的贡献就是给三个分别 propose 一个有理论 + 实证的解,组合起来在 H100 上稳赢 SGLang/vLLM/EAGLE-3 30%。

2 · 背景速查

2.1 关键术语

2.2 SD 流程复习 (一行版)

① draft 自回归 K 步出 (s₁, …, s_K)。② target 一次 forward 算 K+1 个位置的 p_target。③ 顺序拒绝采样: 每个 s_i 以 min(1, p_target(s_i)/p_draft(s_i)) 接受,首次拒绝处从 r ∝ max(p_target - p_draft, 0) 抽 bonus token t*;若全接受则 t* 直接从 p_target 抽。④ 输出长度 ∈ [1, K+1]。Theorem (Leviathan): 输出分布 = 纯 AR target 分布。

3 · SSD 框架: 算法骨架与 lossless 论证

3.1 算法 1 的两个并发 process

SSD 把 SD 的单一控制流拆成两个并发 process,跑在不同设备上:

3.2 Lossless 论证

这一点必须看清楚 —— 否则会觉得 SSD "猜得不对"会破坏分布。

• cache 命中时,SSD 返回的 spec chain 就是一个普通 SD speculation,verifier 用同一个 rejection sampling 流程裁决。所以这种情况下产出分布与 SD 完全一致。
• cache miss 时,fallback 是同步 SD(用 backup speculator) → 也是普通 SD,lossless。
• 所以无论命中与否,SSD 的输出分布 = SD 的输出分布 = target 的 AR 分布。

类比: 这正像 CPU 里的speculative execution(Gonzalez 1997)— 用空闲算力预先执行多条可能分支,真正用到哪条由实际控制流决定。猜错的分支白干,但猜对的能直接上 retire 阶段。SSD 等价于 token-level 的 speculative execution。

4 · 公式: 加速量、cache 几何分布、bound

4.1 Theorem 7 (主加速公式)

分子: 一轮期望产出 token 数。分母: 一轮期望耗时(以 verifier forward = 1 单位时间)。把 SSD 全过程归约成一个 条件期望比。

关键直觉:命中时 latency = max(1, T_p),只要保证 Tp < 1(primary draft 在 verify 完成前结束),就 = 1 — drafting 完全被隐藏。Tokens 仍是 E_hit ≈ K+1 个/轮。这就是 "5× over AR" 的来源。

4.2 Corollary 9 (Speedup Sandwich)

双向 bound 表明: SSD 相对 SD 的额外加速 = (1) 隐藏 draft latency 的因子 (1+T_SD) × (2) 因为 draft 可以慢慢算所以 E_hit 比 E_SD 大的因子(T_p 比 T_SD 可以更大)。

(此处取 E_hit/E_SD = 1, 上界形式) — 上界与 p_hit 解耦,但下界严重依赖 p_hit。所以最大化 p_hit 是 SSD 的核心工程目标。

4.3 Theorem 12 (Saguaro Cache 几何分布)

给定 cache 预算 B = ΣF_k,假设 cache hit 率随 fan-out F 服从 power-law (1 - 1/F^r),最优 F_k 服从 capped 几何级数:

物理直觉:验证恰好接受 j 个 token 的概率本身就是几何分布 a^j(1-a) — 越深(j 越大)越罕见,所以越深 fan-out 越小,把预算花在最常发生的 outcome 上。最深的 j=K(全接受)单独一档 — 它的概率 a^K 没有几何衰减,所以 F_K 反而被放大 (1-a)^-1/(1+r)。

4.4 Theorem 15 (Saguaro Sampling 单调性)

即 draft sampling 时把 cache 里的 top-F 个 token 的概率 压低 C 倍。p_hit 单调随 C → 0 增加(可证)。

物理直觉:residual r ∝ max(p_t - p_d, 0)。压低 cache 内 token 在 p_d 上的质量 → 它们在 residual 上的质量增加 → bonus token 更可能落在 cache 内。代价: p_d 偏离 p_t → acceptance α 下降。C 是这个 trade-off 的旋钮,Theorem 19 (Appendix A.3.1) 构造了一个 4-token 例子证明存在 α 不变但 p_hit 升的 C(具体: p_t=(.48,.48,.02,.02), p_d=(.49,.49,.01,.01), C=47/147 → p'_d=(.47,.47,.03,.03), α 仍 = 0.98, 但 p_hit 从 50% 升到 100%)。

5 · Challenge ①: 怎么预测 verification outcome

5.1 Saguaro 的 cache 构造算法

给定预算 B 和几何 fan-out {F_k},Saguaro 的 cache 构造异常简洁:

在 draft 给出 spec s = (s₁, ..., s_K) 的每个位置 k,取 draft logits 的 top-F_k 个 token (排除 s_k 本身,因为 s_k 已经送去 verify,不会成为 bonus token),作为该位置的 bonus token guess。然后对每个 (k, t*) 用 draft 自回归 K 步,得到 length-K speculation 存入 cache。

5.2 命中率有多高?

论文 Figure 3 实测: rejection rate (1 - p_hit) 随 fan-out F 服从 power-law,r ≈ 1。这意味着翻倍 cache size,miss 率减半。在 1B Llama draft + Llama-3.1-70B target 上:

• F=4: p_hit ≈ 0.7
• F=16: p_hit ≈ 0.85
• F=64: p_hit ≈ 0.93
• bonus token 命中率最高可达 90%(论文 abstract 引用)

6 · Challenge ②: cache hit vs acceptance 的张力 — Saguaro Sampling

6.1 问题

残差 r 是 bonus token 的来源(rejection 时)。r 难预测 是因为它依赖 p_target - p_draft 的差;两个尖锐分布相减得到的可能很扁平。要让 r 集中,必须人为把 p_draft 在 cache 候选 token 上压低。但这同时让 p_draft 远离 p_target,acceptance α 下降。

6.2 实证 trade-off 形状

论文 Figure 5 (left) 给出 cache hit rate vs acceptance rate 曲线随 C 变化:典型场景 C 从 1 → 0,hit rate 从 0.65 → 0.80,acceptance rate 从 0.80 → 0.50。曲线非单调推 speedup,需要选 sweet spot。论文采用经验扫描选 C(没有解析最优),原因是 p_target 形状随上下文变化。

7 · Challenge ③: cache miss 的 fallback 策略

7.1 大 batch 是 SSD 的死穴

Corollary 16: batch size = b 时,只要任何一个 batch 元素 cache miss,整个 batch 都得等 backup speculator → effective miss 率是 1 - p_hit^b。

b=16 时 93% 的轮次都进 fallback 路径 → fallback 速度决定大 batch 性能。Theorem 17 给临界 batch size b*: b < b* 用 primary (慢但准),b ≥ b* 切到 backup (快但糙)。Saguaro 的 backup 实现:

• Fast backup: 返回随机 token (T_b ≈ 0,但 acceptance ≈ 0,只能算 +1 bonus)。论文实测在大 batch 上比 neural backup 还快。
• 升级版: 用 n-gram speculator (Liu 2024 Infini-gram, Oliaro 2024 SuffixDecoding) — 也几乎 zero latency 但 acceptance 比随机好。
• Neural backup (与 primary 同模型): 小 batch 下最优,但 b ≥ b* 时拖累整 batch 等它跑完。

8 · Saguaro 的实现: H100×5, FlashAttention, custom mask

8.1 系统架构

Saguaro 是 PyTorch 自研推理引擎,集成 PagedAttention + continuous batching + TP + BF16 + torch.compile + CUDAGraphs。

8.2 Custom attention mask: 一次 forward 出 F·(K+1) 条 chain

整个 SSD 的工程难点。每轮 draft 要为 F·(K+1) 个 outcome 各 spec K 步,共 B·K·(K+1)·F 个 token forward。如果用普通 dense attention 这是 (K+1)F 倍 SD 的 FLOPs。Saguaro 用稀疏 mask + FlashAttention 让所有分支在同一个 forward 里完成。

8.3 Compute / Memory / Communication 开销

关键观察 (作者明言): "most end-to-end speedup comes from hiding draft latency rather than increasing lookahead." 即 SSD 的核心收益不是 "更长 K 让 E_hit 大",而是把整个 drafting 时间从 critical path 上拿掉。这与我们直觉里"花更多 draft compute 换更长 chain"是不同的故事。

9 · Worked example: 一个 verification cycle 全流程

把上面所有抽象具体化。设定: Llama-3.1-70B target,Llama-3.2-1B draft,K=5,几何 fan-out F=(F₀..F₅) = (8,5,3,2,1,4),B=23,batch=1,greedy。当前 prefix 已生成到 "The integral of x squared dx is"。

s = ("equal", "to", "(", "x", "^")

本轮 wall-clock 分解 (命中)

SSD 把这 4 token 用 1 单位时间产出,vanilla SD 要 1+T_SD ≈ 1.3 单位时间。30% 提升的微观来源就在这里。

10 · 实验关键结果

10.1 端到端: Llama-3.1-70B/1B (Table B.3)

读法:SSD 比作者自己的 SD 实现快 1.58×,而后者作者声明已经接近 vLLM/SGLang 水平。HumanEval / GSM8k (代码 / 数学,token 分布更可预测) 加速最猛 → 印证 cache hit rate 是 deterministic-style 任务的优势区。

10.2 SGLang/vLLM/EAGLE-3 比较

论文实测在 SGLang 0.5.9 上 Llama-3.1-70B/1B EAGLE-3 最优配置(steps × topk 搜索)峰值 ~201 tok/s,vLLM EAGLE-3 ~197 tok/s。Saguaro SSD 的 255 tok/s 比这些都快 ≥ 25%。注脚 4: 在该实验里 Llama-3.2-1B 作为 draft 比 EAGLE-3 还略好,作者据此判断没必要再叠 EAGLE-3。

10.3 Pareto frontier (Figure 7 right)

SSD 不仅在 latency 维度赢,在 throughput-latency 双维度都推开 Pareto wall — 即使把多用的 1 张 draft GPU 计入 per-GPU throughput。这意味着作为 cluster level 部署 primitive,SSD 比 SD 节省 GPU。

10.4 Qwen-3 32B/0.6B (Figure 11)

在 Qwen3 上加速比 ~2.3×/AR,~1.5×/SD。比 Llama 系列略低 — 因为 Qwen3-32B 比 Llama-3.1-70B 小,verifier forward 本身已经较快,SD 留给 SSD 的 hide 空间小。

11 · 与同类工作对比

另见 sibling note 09_MirrorSD_2510.13161.html。Mirror-SD 与 SSD 走的是不同方向:Mirror-SD 利用 verifier 自己的 early-exit 作为信号触发 branch — 它需要修改 verifier 的执行图;而 SSD 完全把 verifier 当黑盒,只在 draft 一侧做文章。两者本质上不冲突。

12 · 局限 / 个人 take / 待验证问题

论文承认的局限

• Throughput-bound 工作负载(大规模 RL rollout、离线数据生成)受益不大 — verifier 已经被打到 compute-bound,SSD 只能小幅提 Pareto。这是 conclusion 直白点出的。
• 需要额外 1 张 H100 (1×H100 给 draft, 4×H100 给 target) — 在 cluster 层面要算 ROI;论文显示 per-GPU throughput 仍然占优,但部署上是要"5 张 vs 4 张"的决策。
• Custom-mask attention 是 critical path bottleneck,所以 K 不能太大 — 不能简单"加更多 lookahead"换更高 E_hit。
• 大 batch 下 fast backup ≈ random tokens,acceptance ≈ 0,产出近似 AR,只能做 +1 token / 轮。等于 SSD 在大 batch 退化为 SD 加一点 cache hit 的 buff。

我的疑问 (待验证)

1. 论文用 1B/70B (1.4% 比例)。如果用 7B/70B 之类更强 primary draft,T_p 会逼近 1,Theorem 7 中 max(1, T_p) 项变 active,SSD 退化到 SD;甜点 draft 大小到底在哪?
2. Saguaro sampling 的 C 在论文中是 hand-tuned。能否做 per-context 自适应 C(根据当前 p_target entropy)? 我猜在长 reasoning chain 中,entropy 单调下降,固定 C 是次优。
3. Theorem 12 假设 r power-law 命中率。论文 Figure 3 只验了 Llama 系列,Qwen 系列只在 Appendix F 验。其他更稀疏家族(MoE 如 Mixtral、Qwen3-235B-A22B)上 r 还成立吗?
4. 论文测的全是 H100。AMD MI300 / TPU 上 NCCL 路径不一样,custom-mask attention 没有 FlashAttn-3 同等内核 — 实际工程化到非 H100 集群成本未知。
5. online weight update 场景(如 RL rollout): SSD 用的 draft 是 frozen 还是 follow learner?如果 frozen, drift 在 RL 中会让 cache hit 率下降;如果 follow, NCCL 路径上要传 weight diff,新瓶颈。论文不涉及 RL,但这恰是 sibling note 01 (NeMo-RL) 的应用场。
6. Theorem 19 的 4-token 反例只证 "存在" sampling 提速;实际 V≈128k 时,p_hit gain vs α loss 的真实 trade-off 曲线形状是否在所有 prompt 上都"对 SSD 有利"?

我的 take (一句话)

SSD 是 SD 后第一个把"draft↔verify 串行"这道墙凿开且实现工业化的工作。它的价值不在新的 acceptance 改进 (那是 EAGLE 系列的活),而在把 SD 的硬件部署模型从"draft 寄宿在 target 同卡"升级到"draft 独立 GPU + 高频 NCCL"。这一步是不可逆的 — 一旦验证有效,后续 SD 工作大概率会默认在 SSD 拓扑下衡量收益。

记忆点

精读笔记 v1 · 2026-05-07 · 配套论文 PDF: /data/szhang967/papers/paper-notes/spec-rl/SSD_2603.03251.pdf
sibling notes: 02_EAGLE_evolution_DFlash.html · 09_MirrorSD_2510.13161.html