SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications
作者: Gabriele Oliaro, Zhihao Jia, Daniel Campos, Aurick Qiao
分类: cs.CL, cs.AI, cs.DC, cs.LG
发布日期: 2024-11-07 (更新: 2025-10-07)
备注: NeurIPS 2025 (Spotlight)
🔗 代码/项目: GITHUB
💡 一句话要点
提出SuffixDecoding，利用后缀树缓存加速LLM Agent重复性推理任务。
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 推测解码 大型语言模型 LLM Agent 后缀树 重复性推理
📋 核心要点
- LLM Agent应用中存在大量重复性推理请求，现有推测解码方法对此类长序列的利用不足。
- SuffixDecoding利用后缀树缓存提示和先前输出中的长token序列，自适应地调整推测长度。
- 实验表明，SuffixDecoding在Agent任务上实现了高达5.3倍的加速，显著优于现有方法。
📝 摘要（中文）
推测解码被广泛应用于降低大型语言模型（LLM）推理的延迟，它利用较小的草稿模型来处理各种用户任务。然而，新兴的AI应用，如基于LLM的Agent，呈现出独特的工作负载特征：Agent框架通常提交重复的推理请求，例如执行类似子任务的多Agent流水线或迭代增强输出的自优化循环，而非多样化的独立请求。这些工作负载产生长且高度可预测的序列，而当前的推测解码方法无法有效利用。为了解决这个差距，我们引入了SuffixDecoding，一种新颖的方法，它利用高效的后缀树来缓存来自提示和先前输出的长token序列。通过在接受可能性高时自适应地推测更多token，而在接受可能性低时推测更少的token，SuffixDecoding有效地利用了更长推测的机会，同时在这些机会有限时节省计算。在包括SWE-Bench和Text-to-SQL在内的Agent基准测试中，评估表明SuffixDecoding实现了高达5.3倍的加速，优于最先进的方法——比基于模型的方法（如EAGLE-2/3）快2.8倍，比无模型的方法（如Token Recycling）快1.9倍。SuffixDecoding已在https://github.com/snowflakedb/ArcticInference开源。
🔬 方法详解
问题定义：现有推测解码方法在处理LLM Agent应用中常见的重复性推理请求时效率低下。这些Agent框架会产生长且高度可预测的token序列，而现有方法无法充分利用这些序列中的冗余信息，导致计算资源的浪费。现有方法主要针对多样化的独立请求设计，无法有效适应Agent任务的特点。
核心思路：SuffixDecoding的核心思路是利用高效的后缀树数据结构来缓存先前推理过程中生成的token序列。通过查找当前prompt的后缀是否与缓存中的序列匹配，可以预测接下来可能出现的token。这种方法能够有效地利用Agent任务中存在的重复模式，从而实现更长的推测长度和更高的加速比。自适应调整推测长度，在接受概率高时增加推测，反之减少，平衡了计算效率和准确性。
技术框架：SuffixDecoding的整体框架包括以下几个主要阶段：1) 后缀树构建：利用先前推理生成的token序列构建后缀树。2) 序列匹配：在当前prompt中查找与后缀树中的序列匹配的最长后缀。3) token推测：根据匹配的后缀，推测接下来可能出现的token序列。4) 验证与接受：使用目标LLM验证推测的token序列，并根据验证结果接受或拒绝部分或全部推测的token。5) 后缀树更新：将新生成的token序列添加到后缀树中，以便后续推理使用。
关键创新：SuffixDecoding最重要的技术创新点在于利用后缀树来缓存和检索token序列。与传统的推测解码方法相比，SuffixDecoding无需训练额外的草稿模型，而是直接利用历史数据进行预测。此外，SuffixDecoding的自适应推测长度调整机制能够根据接受概率动态调整推测长度，从而在保证准确性的前提下最大化加速比。与Token Recycling等无模型方法相比，SuffixDecoding能够利用更长的上下文信息，从而实现更准确的预测。
关键设计：SuffixDecoding的关键设计包括：1) 后缀树的实现方式：选择高效的后缀树实现方式，以保证检索速度。2) 匹配长度阈值：设置匹配长度阈值，以避免过度推测。3) 接受概率阈值：设置接受概率阈值，以控制推测的准确性。4) 后缀树更新策略：选择合适的后缀树更新策略，以平衡缓存大小和预测准确性。这些参数需要根据具体的应用场景进行调整，以达到最佳性能。
📊 实验亮点
SuffixDecoding在SWE-Bench和Text-to-SQL等Agent基准测试中取得了显著的性能提升。实验结果表明，SuffixDecoding实现了高达5.3倍的加速，优于最先进的推测解码方法。具体而言，SuffixDecoding比基于模型的方法（如EAGLE-2/3）快2.8倍，比无模型的方法（如Token Recycling）快1.9倍。这些结果表明，SuffixDecoding能够有效地利用Agent任务中的重复模式，从而实现更高的推理效率。
🎯 应用场景
SuffixDecoding在LLM Agent领域具有广泛的应用前景，例如多Agent协作、代码生成、文本摘要和对话系统等。通过加速LLM Agent的推理速度，可以显著提高这些应用的响应速度和用户体验。此外，SuffixDecoding还可以应用于其他具有重复性推理模式的场景，例如视频处理和时间序列预测等。该研究有望推动LLM在更广泛领域的应用。
📄 摘要（原文）
Speculative decoding is widely adopted to reduce latency in large language model (LLM) inference by leveraging smaller draft models capable of handling diverse user tasks. However, emerging AI applications, such as LLM-based agents, present unique workload characteristics: instead of diverse independent requests, agentic frameworks typically submit repetitive inference requests, such as multi-agent pipelines performing similar subtasks or self-refinement loops iteratively enhancing outputs. These workloads result in long and highly predictable sequences, which current speculative decoding methods do not effectively exploit. To address this gap, we introduce \emph{SuffixDecoding}, a novel method that utilizes efficient suffix trees to cache long token sequences from prompts and previous outputs. By adaptively speculating more tokens when acceptance likelihood is high and fewer when it is low, SuffixDecoding effectively exploits opportunities for longer speculations while conserving computation when those opportunities are limited. Evaluations on agentic benchmarks, including SWE-Bench and Text-to-SQL, demonstrate that SuffixDecoding achieves speedups of up to 5.3$\times$, outperforming state-of-the-art methods -- 2.8$\times$ faster than model-based approaches like EAGLE-2/3 and 1.9$\times$ faster than model-free approaches such as Token Recycling. SuffixDecoding is open-sourced at https://github.com/snowflakedb/ArcticInference