用后缀自动机加速大模型推理，提升生成速度且适应多领域。
SAM Decoding: Speculative Decoding via Suffix Automaton
- 基于后缀自动机动态匹配文本，实现高效精准的草稿生成。
- 相比现有方法平均提速18%以上，与EAGLE-2结合再增3.28%~11.13%。
- 无需依赖特定数据集，可自适应选择策略，适合各类大模型部署。
推测解码（SD）已被证明是加速大语言模型无损推理的有效技术。基于检索的SD方法作为一类无模型方法，虽取得良好加速效果，但常受限于不完整的检索资源、低效的检索方式，且适用范围狭窄。本文提出一种新颖的基于检索的推测解码方法——SAM-Decoding，利用后缀自动机（SAM）在通用文本语料和动态序列中实现高效准确的草稿生成。与传统n-gram匹配不同，SAM-Decoding可精确找到最长后缀匹配，每步生成的平均时间复杂度为O(1)。该方法可与现有技术融合，根据匹配长度自适应选择生成策略，拓展至更广泛领域。在Spec-Bench上的大量实验表明，本方法比其他基于检索的SD方法快18%以上；当与先进方法EAGLE-2结合时，在不同规模的LLM模型上进一步获得3.28%至11.13%的加速。代码已开源。
原文摘要 · Abstract (English)
Speculative decoding (SD) has been demonstrated as an effective technique for lossless LLM inference acceleration. Retrieval-based SD methods, one kind of model-free method, have yielded promising speedup, but they often rely on incomplete retrieval resources, inefficient retrieval methods, and are constrained to certain domains. This paper presents a novel retrieval-based speculative decoding method that adapts suffix automaton (SAM) for efficient and accurate draft generation by utilizing common text corpus and dynamic text sequence. Unlike existing $n$-gram matching methods, SAM-Decoding finds the exact longest suffix match, achieving an average time complexity of O(1) per generation step of SAM update and suffix retrieval. It can also integrate with existing methods, adaptively selecting a draft generation strategy based on match length to generalize to broader domains. Extensive experiments on Spec-Bench show that our method is $18\%+$ faster than other retrieval-based SD methods. Additionally, when combined with advanced EAGLE-2, it provides an additional speedup of $3.28\%$ -- $11.13\%$ across various-sized LLM backbones. Our code is available at our \href{https://github.com/hyx1999/SAM-Decoding}{repository}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。