少起草，多检索：面向推测解码的混合树构建方法 Graft Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding

Graft 的执行流程可拆成三步：(1) **预算释放（剪枝）**：在草稿树展开到第 $d$ 层时，累计路径分数 $S_{d,j}=S_{d-1,F(j)}+\log q(x_{d,j}\mid h_{d-1,F(j)})$，取 $c_d=\exp\max_j S_{d,j}$，与校准阈值 $\tau_d$ 比较得到 $g_d=\mathbb{1}[c_d>\tau_d]$；若 $g_d=0$ 则在第 $d$ 个 checkpoint 把树截断，跳过更深的草稿展开，浅层 checkpoint 的阈值更严格以减少累积误判。剪枝阶段 $s$ 决定保留的草稿节点数 $K_{draft}^s$（例如 $s\in\{d_0,d_1,d_5\}$ 对应 8/24/40），剩余 $K_{ret}^s=K_{max}-K_{draft}^s$ 个 slot 全部交由检索填充。(2) **检索嫁接**：以当前根 token $x_t$ 为起点，从 GPU 邻接矩阵 $M$ 中按行查找 top-$k$ 后继，即 $x_u=M[x_{F(u)}, r_u]$，并行展开一个 stage-adaptive 模板 $G_{ret}^s$（默认深度/宽度对齐 base tree $D_E/W_E$，但按剪枝阶段取相应子模板）。重要的是，root-centered 的检索在草稿阶段就已经并行开始展开 envelope，只在剪枝结束后截取与 $K_{ret}^s$ 匹配的子模板拼接到 $T_\pi$ 中，因此不会在 critical path 上新增串行阶段。(3) **混合验证与在线更新**：把保留的草稿节点与嫁接的检索节点扁平化成大小为 $K_{max}$ 的 token 列表，重建标准 tree position IDs、ancestor mask 和 candidate path indices 送进目标模型做一次并行验证；接受规则与标准 SD 完全一致，因此保留 lossless 性质。验证后，对每个被验证的 token $\tilde{x}_i$（无论最终是否被接受），都用目标模型在 $i+1$ 位置的 next-token 分布 $\tilde{p}_{i+1}$ 刷新对应行的 top-$k$ 后继，从而让 $M$ 越来越贴合当前上下文。

技术新颖性主要体现在三点：(1) **预算再分配视角**：把「剪枝」从「被动裁剪候选」重新诠释为「主动释放预算」，并把「检索」从「独立 drafter」重新诠释为「预算补偿源」，这是对动态推测解码设计空间的概念性扩展，论文第 2.1 节给出了 $S(T_\pi)/S(T_E)$ 分解公式与 $1-\prod_d(1-\epsilon_d)$ 的累积误判上界来支撑该视角。(2) **prune-then-graft 耦合设计**：作者通过对比实验（Figure 2）证明，纯 root 嫁接 $G_{ret}^{root}$ 会挤占 root 附近强草稿节点导致平均加速比不如 EAGLE-3，纯 tail 嫁接 $G_{ret}^{tail}$ 又强依赖整条草稿前缀被接受，而 prune-then-graft 把检索精确安放在「剪枝真正创造空间」的位置，并配合 stage-adaptive 模板实现端到端最优。(3) **GPU-resident 在线邻接矩阵 + 树状验证路径复用**：$M\in V^{|V|\times k}$ 直接驻 GPU，检索退化为单次 row gather，没有 CPU 通信也不需要额外目标 forward；50 轮 warm-up 也只占 2.32 MB（Table 4）。同时验证阶段完全复用 EAGLE-3 的 tree-attention 接口，$|T^s|=K_{max}$ 恒定，serving kernel 不用做 ragged-batch 适配，这对工业部署至关重要。

**弱点 1：检索的覆盖度受限于 prompt/历史的局部结构。** 现实中很多任务（创意写作、复杂多跳推理、自由对话）几乎没有可复用的 n-gram 模式，邻接矩阵 $M$ 中的 top-$k$ 后继可能与目标分布严重偏离。这种情况下剪枝释放的 slot 难以被有效填满，方法退化为「仅剪枝的 ECHO 类行为」，MAT 提升有限。**改进方向**：可结合「目标模型在 prompt 上的先验分布」做隐式检索，或引入神经网络式 retrieval encoder 把非局部语义模式也编码进 $M$；另一个思路是设计 fallback 机制——当 $M$ 的 top-$k$ 置信度低时，重新分配更多 slot 给草稿端。**弱点 2：Stage-adaptive 模板是手工设计且依赖 base tree 形状。** 论文承认模板的深度/宽度组合 $d=8, w=8$ 来自 Figure 6 的网格搜索，跨模型、跨任务没有自适应。在 MT-Bench 等长尾任务上，最优 $(d, w)$ 可能差异很大。**改进方向**：可学习式模板生成器（比如用一个轻量 policy network 在每个 checkpoint 预测最优形状），或者用预收集的验证集做 offline 校准 + 在线 adapt。**弱点 3：高并发场景的实现不完整。** SGLang 实验明确说没有优化 retrieval kernel 和调度，这意味着 retrieval 邻接矩阵的查表开销在 BS 较大时可能成为新瓶颈。**改进方向**：把邻接矩阵做 kernel fusion 进 tree-attention；用 per-request 缓存避免重复 gather；在调度器层面把同一个 root token 的请求 batch 起来以摊销查表成本。**弱点 4：DFlash block 嫁接只是 demo。** 当前在 block 内部没有 confidence-guided 位置选择，graft 是在整块层做的粗粒度操作。**改进方向**：从 DFlash 草稿 logits 出发做 token 级 confidence 估计，针对 block 内部每个位置独立决定「剪掉 / 保留 / 嫁接」；探索 block 内部树形 expansion 模板。**弱点 5：未与 KV-cache 优化方法深度集成。** 长上下文下 TriForce 等方法通过 sparse KV 草稿降低 attention 成本，但 Graft 没有与这些方法叠加。**改进方向**：把 Graft 嫁接在 sparse-KV 草稿之上，研究两层 Pareto frontier 能否进一步突破。**弱点 6：warm-up 阈值对任务分布敏感。** 虽然 Appendix C.4 显示迁移性可以接受，但仍有 minor 退化。**改进方向**：online calibration 机制——在每个新任务的前几个 step 用小窗口重新校准 $\{\tau_d\}$。**弱点 7：vocab 大的模型上邻接矩阵存储成本上升。** $M\in V^{|V|\times k}$ 在 100K+ vocab 上即便 $k=8$ 也可能到 MB 级。**改进方向**：稀疏化存储（只为高频 token 维护 top-$k$），或用 hash-based 邻接表压缩。

作者在第 4.5 节明确提出了两个延伸方向。**方向 1：Grafting for block drafters (DFlash)**。DFlash 一次并行草稿 16 个 token 显著降低草稿延迟，但块内 token 的接受率并不均匀（MT-Bench 上仍只有 5~7 MAT）。作者已经在 Qwen3-8B 上验证了 Graft-DFLASH 能把 DFlash 的 3.40× 拉到 3.71×（+9.1%），下一步要系统化地设计 block 内 token 级的 confidence 剪枝规则（而非整块级），并设计专门适配 block 拓扑的检索嫁接模板。**方向 2：Hybrid drafting for RL rollouts**。作者观察到大规模 RL rollout（特别是 GRPO 类 group sampling）下，独立的 static draft model 容易因 target policy 漂移而失效；纯检索方法如 Seer 依赖组内 n-gram 重叠，hit 率随温度升高不稳定。作者提议把 MTP（multi-token prediction，挂在 target model 内部）当作「稳定 throughput floor」，把 online n-gram retrieval 当作「高质量 long continuation source」，再用 Graft 风格的 confidence 剪枝决定哪些 MTP 位置让给检索，这对 Agentic RL 中尾请求主导迭代时间的问题尤其有吸引力。除作者提出的方向外，基于本文结果还可以延伸：(3) **与稀疏 KV 草稿叠加**：研究 Graft + TriForce/MagicDec 的两层 Pareto frontier；(4) **跨请求共享邻接矩阵**：同一服务的相似请求共享 $M$ 的一部分 row，进一步降低单请求存储；(5) **任务自适应模板**：用任务 embedding 预测最优 $(d, w)$，实现 zero-shot 部署；(6) **工具调用与结构化输出的检索嫁接**：tool call schema、JSON 模板天然有高重复性，是检索的高价值场景；(7) **Speculative decoding for code agents**：仓库级代码补全（RepoBench-P 已有 +38.6% 增益）可推广到 code agent 的多轮工具调用。

复现性整体较好。**开源情况**：作者来自浙大和阿里 Qwen 应用团队，方法在 HuggingFace transformers + SGLang 框架中实现，所有 attention 都用 PyTorch SDPA 标准化以便对比。论文明确指出「All baselines are reproduced using their official configurations」，并把超参放在 Appendix C。**数据**：短上下文用 EAGLE-3 和 Spec-Bench 的标准 5 个 benchmark（HumanEval、GSM8K、CNN/DM、Alpaca、MT-Bench）；长上下文用 LongBench 的 5 个子集（QMSum、GovReport、MultiNews、LCC、RepoBench-P），并给出 4K/8K/16K/32K 长度缩放切片。warm-up 使用 ShareGPT，与所有评估集不相交，避免了数据污染。**算力**：所有实验在 8 张 NVIDIA H20 GPU 上运行；高并发实验用 SGLang，batch 1~16。EAGLE-3 在 long context 下使用 YaRN 适配的 64K checkpoint。**复现难度**：低-中。方法本身 training-free 和 lossless，不涉及模型重训；模板形状、warm-up 轮数（默认 5 轮）等关键超参都在主文和附录中给出；可变的只有 base tree drafter 的具体选择（论文默认 EAGLE-3，$K_{max}=60$），需要复用其官方 checkpoint。**潜在难点**：(a) GPU 邻接矩阵的具体实现和 gather kernel 需要根据推理框架（vLLM、SGLang、HuggingFace）适配；(b) YaRN 64K 适配的 EAGLE3 checkpoint 需要从 SpecPV 等仓库获取；(c) 高并发场景的 SGLang 集成还处于早期，需要自己补全调度优化。