mlsanityData to 7 Oct 2026

SAM Decoding: Speculative Decoding via Suffix Automaton

arXiv 2411.10666 ↗First posted 16 Nov 2024cs.CL cs.AIcited by 38

On the map: Efficient LLM inference and serving → Speculative decoding

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.

Key facts. Cited by 38 papers in the map (data through 7 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.

Builds on

33 of 42 references.

Closest ancestors · 9

Same direction, newest first

  1. 2024EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees24 Jun
  2. 2024CLLMs: Consistency Large Language Models28 Feb
  3. 2024Break the Sequential Dependency of LLM Inference Using Lookahead Decoding3 Feb
  4. 2024EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty26 Jan
  5. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads19 Jan
  6. 2024Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding15 Jan
  7. 2023REST: Retrieval-Based Speculative Decoding14 Nov
  8. 2023SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification16 May
  9. 2022Fast Inference from Transformers via Speculative Decoding30 Nov

Other references · 24

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  3. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  4. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  5. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  6. 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,779
  7. 2021Program Synthesis with Large Language Modelscited by 3,509
  8. 2024Qwen2 Technical Reportcited by 2,076
  9. 2022GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformerscited by 1,838
  10. 2022SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Modelscited by 1,338
  11. 2023AWQ: Activation-aware Weight Quantization for LLM Compression and Accelerationcited by 1,234
  12. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,107
12 more
  1. 2023SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shotcited by 1,090
  2. 2016Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyondcited by 809
  3. 2023A Simple and Effective Pruning Approach for Large Language Modelscited by 776
  4. 2024QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMscited by 598
  5. 2024SpinQuant: LLM quantization with learned rotationscited by 446
  6. 2024SliceGPT: Compress Large Language Models by Deleting Rows and Columnscited by 378
  7. 2024ShortGPT: Layers in Large Language Models are More Redundant Than You Expectcited by 369
  8. 2024LayerSkip: Enabling Early Exit Inference and Self-Speculative Decodingcited by 302
  9. 2024LLM Pruning and Distillation in Practice: The Minitron Approachcited by 82
  10. 2023HAGRID: A Human-LLM Collaborative Dataset for Generative Information-Seeking with Attributioncited by 55
  11. 2024Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recyclingcited by 48
  12. 2024Streamlining Redundant Layers to Compress Large Language Modelscited by 32

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 15; 2026: 23.

38 papers.

Sort:

By area:

  1. 2025DiffuSpec: Unlocking Diffusion Language Models for Speculative Decodingcited by 40
  2. 2025Seer: Online Context Learning for Fast Synchronous LLM Reinforcement Learningcited by 21
  3. 2025BanditSpec: Adaptive Speculative Decoding via Bandit Algorithmscited by 18
  4. 2025LogitSpec: Accelerating Retrieval-based Speculative Decoding via Next Next Token Speculationcited by 13
  5. 2026TALON: Confidence-Aware Speculative Decoding with Adaptive Token Treescited by 12
  6. 2026JetSpec: Breaking the Scaling Ceiling of Speculative Decoding with Parallel Tree Draftingcited by 12
  7. 2025Accelerating Large-Scale Reasoning Model Inference with Sparse Self-Speculative Decodingcited by 9
  8. 2026Budget-Constrained Agentic Large Language Models: Intention-Based Planning for Costly Tool Usecited by 8
  9. 2025CopySpec: Accelerating LLMs with Speculative Copy-and-Paste Without Compromising Qualitycited by 6
  10. 2025DReSD: Dense Retrieval for Speculative Decodingcited by 6
  11. 2025Parallel Token Prediction for Language Modelscited by 6
  12. 2025Shallow Preference Signals: Large Language Model Aligns Even Better with Truncated Data?cited by 5
26 more
  1. 2026Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decodingcited by 5
  2. 2025Accelerating Mobile Language Model via Speculative Decoding and NPU-Coordinated Executioncited by 4
  3. 2025Fast LLM Post-training via Decoupled and Fastest-of-N Speculationcited by 4
  4. 2025Towards Efficient Agents: A Co-Design of Inference Architecture and Systemcited by 4
  5. 2026ToolSpec: Accelerating Tool Calling via Schema-Aware and Retrieval-Augmented Speculative Decodingcited by 4
  6. 2025Accelerated Test-Time Scaling with Model-Free Speculative Samplingcited by 3
  7. 2025When, What, and How: Rethinking Retrieval-Enhanced Speculative Decodingcited by 3
  8. 2025Cacheback: Speculative Decoding With Nothing But Cachecited by 3
  9. 2026MMSpec: Benchmarking Speculative Decoding for Vision-Language Modelscited by 3
  10. 2026SwarmResearch: Orchestrating Coding Agents for Open-Ended Discoverycited by 2
  11. 2026Trees from Marginals: Autoregressive drafting with factorized priorscited by 2
  12. 2026TailSieve: Partial-Rollout-Guided Tail Routing for LLM Rolloutscited by 2
  13. 2026JuDi: Revisiting Judge Decoding from First Principles via Training-Free Distributional Divergencecited by 1
  14. 2026SENSE: Semantic Embedding Navigation with Soft-gated Evaluation for Retrieval-based Speculative Decodingcited by 1
  15. 2026AdaPLD: Adaptive Retrieval and Reuse for Efficient Model-Free Speculative Decodingcited by 1
  16. 2026Fully Rotation-Equivariant Spectral-Spatial Learning for Multispectral Object Detectioncited by 0
  17. 2026OoO-Spec: Out-of-Order Semantic Speculation for Fast Tool Callingcited by 0
  18. 2026Oilbird: Training-Free Speculative Decoding with Keys the Verifier Already Computescited by 0
  19. 2026ECHO: Early-layer Collaborative Hierarchical Orchestration with Bonus Logits in Speculative Decodingcited by 0
  20. 2026To Copy or Not to Copy: Controlling Speculative Decoding via Intrinsic Model Signalscited by 0
  21. 2026LumoTree: Path-Parallel Speculative Verification for Hybrid Language Modelscited by 0
  22. 2026TSS: Target-Side Sparsification for Speculative Decoding in Domain-Specific Large Language Modelscited by 0
  23. 2026Shallow Queries, Mature Values: Depth-Asynchronous Self-Speculation for Looped Transformerscited by 0
  24. 2026AgSpec: Pushing the Limits of Retrieval-Based Speculative Decoding in Coding Agent Pipelinescited by 0
  25. 2026Trajectory-Retrieval Speculative Decoding: When Does a Model's Own History Help?cited by 0
  26. 2026APEX: Speculate smarter, not deepercited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Tutorial Proposal: Speculative Decoding for Efficient LLM Inference
  2. 2024Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding
  3. 2024Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement
  4. 2026RACER: Retrieval-Augmented Contextual Rapid Speculative Decoding
  5. 2025Scaling Up, Speeding Up: A Benchmark of Speculative Decoding for Efficient LLM Test-Time Scaling
  6. 2024Speculative Decoding via Early-exiting for Faster LLM Inference with Thompson Sampling Control Mechanism
  7. 2024SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications
  8. 2025Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies