UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding

📄 arXiv: 2605.04543v1 📥 PDF

作者: Yepeng Weng, Qiao Hu, Takehisa Yairi

分类: cs.CL, cs.LG

发布日期: 2026-05-06

💡 一句话要点

提出UniVer，通过条件最优传输统一多步多草稿推测解码，提升LLM推理效率。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 推测解码 大型语言模型 最优传输 加速推理 条件概率

📋 核心要点

  1. 现有推测解码方法在处理多步多草稿时存在割裂，未能充分利用候选树水平和垂直维度间的耦合关系。
  2. UniVer将树状验证视为条件最优传输问题，利用前缀接受概率动态引导草稿选择，实现联合优化。
  3. 实验表明，UniVer在保持分布对齐的同时，显著提升了接受长度，优于现有递归拒绝采样方法。

📝 摘要（中文）

推测解码通过先草稿后验证的方式加速大型语言模型（LLM）的推理过程，其中验证环节可以被视为一个最优传输（OT）问题。现有方法通常孤立地处理多草稿和多步推测，要么对单步草稿应用扁平OT，要么对树状结构的候选应用逐token的拒绝采样。这种分离导致了联合场景（多步依赖与多草稿分支的结合）的优化不足，因为局部验证规则未能充分利用候选树的水平和垂直维度之间的耦合关系。本文提出了一种统一的视角，将基于树的验证视为一个条件OT问题。我们的关键见解是，垂直依赖可以通过前缀接受概率来抽象，这些概率作为动态缩放因子，主动引导水平草稿的选择。基于此，我们引入了UniVer，一种通过在前缀约束下组合局部最优传输方案来联合优化树结构的验证算法。我们证明了UniVer保持无损性，并在提出的条件框架下实现了最优接受率。在不同任务和模型上的大量实验表明，UniVer在保持与目标模型完全分布对齐的同时，比标准的无放回递归拒绝采样提高了4.2%到8.5%的接受长度。

🔬 方法详解

问题定义：论文旨在解决多步多草稿推测解码中，现有方法无法有效利用候选树水平和垂直维度耦合关系的问题。现有方法通常孤立地处理多草稿和多步推测，导致验证效率低下，无法充分加速LLM的推理过程。

核心思路：论文的核心思路是将树状结构的验证过程视为一个条件最优传输（OT）问题。通过引入前缀接受概率，将垂直依赖关系抽象为动态缩放因子，从而指导水平方向上的草稿选择。这种方法能够联合优化树的各个层级，提高整体的接受率。

技术框架：UniVer算法的核心流程包括：1) 生成多步多草稿的候选树；2) 计算每个节点的前缀接受概率，该概率反映了从根节点到当前节点路径被接受的可能性；3) 基于前缀接受概率，构建局部最优传输方案，用于决定接受或拒绝哪些草稿；4) 将局部最优传输方案组合起来，形成全局的验证策略。

关键创新：UniVer的关键创新在于将树状验证问题转化为条件最优传输问题，并利用前缀接受概率来建模垂直依赖关系。与现有方法相比，UniVer能够联合优化树的各个层级，充分利用水平和垂直维度之间的耦合关系，从而提高接受率。

关键设计：UniVer的关键设计包括：1) 前缀接受概率的计算方法，需要考虑从根节点到当前节点的所有路径；2) 局部最优传输方案的构建，需要根据前缀接受概率动态调整传输成本；3) 全局验证策略的组合，需要保证整体的无损性，即保持与目标模型的分布对齐。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，UniVer在不同任务和模型上均取得了显著的性能提升。与标准的无放回递归拒绝采样相比，UniVer的接受长度提高了4.2%到8.5%，同时保持了与目标模型的完全分布对齐。这些结果验证了UniVer算法的有效性和优越性。

🎯 应用场景

UniVer算法可应用于各种需要加速LLM推理的场景，例如在线对话系统、文本生成、机器翻译等。通过提高解码效率，UniVer可以降低计算成本，提升用户体验，并促进LLM在资源受限设备上的部署。该研究对于推动LLM的实际应用具有重要意义。

📄 摘要（原文）

Speculative decoding accelerates Large Language Models via draft-then-verify, where verification can be framed as an Optimal Transport (OT) problem. Existing approaches typically handle multi-draft and multi-step aspects in isolation, applying either flat OT to single-step drafts or per-token rejection sampling to tree-structured candidates. This separation leaves the joint regime (where multi-step dependencies meet multi-draft branching) poorly optimized, as local verification rules fail to exploit the coupling between horizontal and vertical dimensions of candidate trees. In this paper, we propose a unified perspective that casts tree-based verification as a conditional OT problem. Our key insight is that vertical dependencies can be abstracted through prefix acceptance probabilities, which act as dynamic scaling factors to actively guide horizontal draft selection. Based on this principle, we introduce UniVer, a verification algorithm that jointly optimizes across tree levels by composing local optimal transport plans under prefix constraints. We prove that UniVer remains lossless and achieves the optimal acceptance rate under the proposed conditional framework. Extensive experiments across different tasks and models demonstrate that UniVer improves acceptance length by 4.2% to 8.5% over standard recursive rejection sampling without replacement, while maintaining exact distributional alignment with the target model.