# SAM Decoding: Speculative Decoding via Suffix Automaton

arXiv: https://arxiv.org/abs/2411.10666 · HTML: https://mlsanity.com/paper/2411.10666/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 33 of its 42 references that are in the map.
- First posted on arXiv 16 Nov 2024.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 30 of 33)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyond](https://mlsanity.com/paper/1602.06023/) (2016)
- [A Simple and Effective Pruning Approach for Large Language Models](https://mlsanity.com/paper/2306.11695/) (2023)
- [QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs](https://mlsanity.com/paper/2404.00456/) (2024)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [SpinQuant: LLM quantization with learned rotations](https://mlsanity.com/paper/2405.16406/) (2024)
- [SliceGPT: Compress Large Language Models by Deleting Rows and Columns](https://mlsanity.com/paper/2401.15024/) (2024)
- [ShortGPT: Layers in Large Language Models are More Redundant Than You Expect](https://mlsanity.com/paper/2403.03853/) (2024)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding](https://mlsanity.com/paper/2404.16710/) (2024)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [LLM Pruning and Distillation in Practice: The Minitron Approach](https://mlsanity.com/paper/2408.11796/) (2024)
- [CLLMs: Consistency Large Language Models](https://mlsanity.com/paper/2403.00835/) (2024)

## Built on by (most cited first, 30 of 39)

- [DiffuSpec: Unlocking Diffusion Language Models for Speculative Decoding](https://mlsanity.com/paper/2510.02358/) (2025)
- [Seer: Online Context Learning for Fast Synchronous LLM Reinforcement Learning](https://mlsanity.com/paper/2511.14617/) (2025)
- [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025)
- [JetSpec: Breaking the Scaling Ceiling of Speculative Decoding with Parallel Tree Drafting](https://mlsanity.com/paper/2606.18394/) (2026)
- [LogitSpec: Accelerating Retrieval-based Speculative Decoding via Next Next Token Speculation](https://mlsanity.com/paper/2507.01449/) (2025)
- [TALON: Confidence-Aware Speculative Decoding with Adaptive Token Trees](https://mlsanity.com/paper/2601.07353/) (2026)
- [Accelerating Large-Scale Reasoning Model Inference with Sparse Self-Speculative Decoding](https://mlsanity.com/paper/2512.01278/) (2025)
- [Budget-Constrained Agentic Large Language Models: Intention-Based Planning for Costly Tool Use](https://mlsanity.com/paper/2602.11541/) (2026)
- [Parallel Token Prediction for Language Models](https://mlsanity.com/paper/2512.21323/) (2025)
- [CopySpec: Accelerating LLMs with Speculative Copy-and-Paste Without Compromising Quality](https://mlsanity.com/paper/2502.08923/) (2025)
- [DReSD: Dense Retrieval for Speculative Decoding](https://mlsanity.com/paper/2502.15572/) (2025)
- [Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding](https://mlsanity.com/paper/2605.20104/) (2026)
- [SwarmResearch: Orchestrating Coding Agents for Open-Ended Discovery](https://mlsanity.com/paper/2607.02807/) (2026)
- [Shallow Preference Signals: Large Language Model Aligns Even Better with Truncated Data?](https://mlsanity.com/paper/2505.17122/) (2025)
- [Accelerating Mobile Language Model via Speculative Decoding and NPU-Coordinated Execution](https://mlsanity.com/paper/2510.15312/) (2025)
- [ToolSpec: Accelerating Tool Calling via Schema-Aware and Retrieval-Augmented Speculative Decoding](https://mlsanity.com/paper/2604.13519/) (2026)
- [Fast LLM Post-training via Decoupled and Fastest-of-N Speculation](https://mlsanity.com/paper/2511.16193/) (2025)
- [Towards Efficient Agents: A Co-Design of Inference Architecture and System](https://mlsanity.com/paper/2512.18337/) (2025)
- [When, What, and How: Rethinking Retrieval-Enhanced Speculative Decoding](https://mlsanity.com/paper/2511.01282/) (2025)
- [Cacheback: Speculative Decoding With Nothing But Cache](https://mlsanity.com/paper/2511.21699/) (2025)
- [MMSpec: Benchmarking Speculative Decoding for Vision-Language Models](https://mlsanity.com/paper/2603.14989/) (2026)
- [Trees from Marginals: Autoregressive drafting with factorized priors](https://mlsanity.com/paper/2607.06763/) (2026)
- [Accelerated Test-Time Scaling with Model-Free Speculative Sampling](https://mlsanity.com/paper/2506.04708/) (2025)
- [JuDi: Revisiting Judge Decoding from First Principles via Training-Free Distributional Divergence](https://mlsanity.com/paper/2601.04766/) (2026)
- [TailSieve: Partial-Rollout-Guided Tail Routing for LLM Rollouts](https://mlsanity.com/paper/2608.22788/) (2026)
- [SENSE: Semantic Embedding Navigation with Soft-gated Evaluation for Retrieval-based Speculative Decoding](https://mlsanity.com/paper/2606.00021/) (2026)
- [AdaPLD: Adaptive Retrieval and Reuse for Efficient Model-Free Speculative Decoding](https://mlsanity.com/paper/2606.05742/) (2026)
- [OoO-Spec: Out-of-Order Semantic Speculation for Fast Tool Calling](https://mlsanity.com/paper/2608.00814/) (2026)
- [To Copy or Not to Copy: Controlling Speculative Decoding via Intrinsic Model Signals](https://mlsanity.com/paper/2609.20186/) (2026)
- [Fully Rotation-Equivariant Spectral-Spatial Learning for Multispectral Object Detection](https://mlsanity.com/paper/2607.05148/) (2026)

## Abstract (arXiv)

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 hrefhttps://github.com/hyx1999/SAM-Decodingrepository.