SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications¶
会议: NeurIPS 2025
arXiv: 2411.04975
代码: https://github.com/snowflakedb/ArcticInference
领域: LLM Agent / 推理优化
关键词: 推测解码, 后缀树, Agent推理, 推理加速, 无训练
一句话总结¶
利用后缀树缓存长序列，通过自适应推测长度实现 5.3 倍加速，特别针对 Agent 场景中高度可预测的重复推理任务。
研究背景与动机¶
-
领域现状：推测解码已成为降低 LLM 推理延迟的标准技术，draft 模型+验证器的组合广泛采用。
-
现有痛点：
- 传统推测解码针对多样化请求优化，但 Agent 工作负载是重复推理（多 agent 管线、自优化循环）
-
Draft 模型需学习 diverse 任务分布，难以捕捉 Agent 场景的重复性
-
核心矛盾：Agent 推理中存在大量可缓存的长 token 序列，现有方法未充分利用。
-
切入角度：不需训练 draft 模型，用后缀树精确匹配历史序列，自适应决定推测长度。
-
核心idea一句话：后缀树缓存 prompt 和前序输出中的长 token 序列，无训练、极端推测。
方法详解¶
整体框架¶
SuffixDecoding 由两个核心组件组成：(1) 后缀树索引——缓存 prompt 和 output 中的所有前缀，线性构造 \(O(n)\)，查询最长完全匹配 \(O(m)\)；(2) 自适应推测——根据匹配长度和接受率动态调整推测长度。
关键设计¶
- 后缀树索引:
- 做什么：缓存所有 prompt + 前序 output 的 token 序列
- 核心思路：对当前生成的 token 序列进行后缀查询，返回历史中最长匹配后的后续 token
-
设计动机：Agent 推理中 ~70% 的序列是可预测的重复模式
-
自适应推测长度:
- 做什么：根据接受率动态调整推测 token 数
- 核心思路：高接受率 > T1 → 增加推测长度；低接受率 < T2 → 减少推测长度
- 设计动机：充分利用高确定性时的推测，在不确定时保守
实验关键数据¶
主实验¶
| 方法 | 加速倍数 | 说明 |
|---|---|---|
| EAGLE-2 | 1.9x | 模型基，需训练 |
| Token Recycling | 1.9x | 无训练但推测有限 |
| Draft Model | 2.5x | 需训练 |
| SuffixDecoding | 5.3x | 无训练，极端推测 |
工作负载分析¶
| 指标 | SWE 工作流 | Text-to-SQL | 一般推理 |
|---|---|---|---|
| 可预测序列比例 | ~70% | ~65% | ~30% |
| 平均匹配长度 | 8-12 tokens | 5-9 tokens | 1-3 tokens |
| 推测接受率 | >90% | >85% | ~60% |
| 加速倍数 | 5.3x | 4.7x | 2.1x |
关键发现¶
- Agent 工作负载展现显著序列重复性，与多样化推理差异明显（5.3x vs 2.1x）
- 无需模型训练或微调，直接应用于任何 LLM
- 内存开销线性于缓存 size，可控制
亮点与洞察¶
- 后缀树的复兴：经典数据结构的创新应用，无需学习的精确匹配优于学到的近似推测
- 无训练的优势：避免 draft 模型训练开销，即插即用
- 5.3 倍加速的实际意义：等效 5 倍 GPU 吞吐量提升
局限性 / 可改进方向¶
- Agent 特定性：对多样化推理收益有限（2.1x）
- 大规模部署时缓存内存压力
- 未讨论与 KV cache 压缩、量化等的组合效应
相关工作与启发¶
- vs EAGLE-2/3：需训练 draft 模型，SuffixDecoding 无训练且在 Agent 场景更快
- vs Token Recycling：无模型但推测效率有限，SuffixDecoding 的后缀树能缓存更长序列
评分¶
- 新颖性: ⭐⭐⭐⭐ 经典数据结构创新应用于 Agent 推理
- 实验充分度: ⭐⭐⭐⭐ SWE-Bench + Text-to-SQL 双基准
- 写作质量: ⭐⭐⭐⭐ 动机充分，方案简洁
- 价值: ⭐⭐⭐⭐⭐ 无训练、即插即用、5.3 倍加速 代码: 待确认