# A Theoretical Perspective for Speculative Decoding Algorithm

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

## Key facts

- Cited by 29 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 39 of its 48 references that are in the map.
- First posted on arXiv 30 Oct 2024.

## Placed in

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

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

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [RT-1: Robotics Transformer for Real-World Control at Scale](https://mlsanity.com/paper/2212.06817/) (2022)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Imagen Video: High Definition Video Generation with Diffusion Models](https://mlsanity.com/paper/2210.02303/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [ViViT: A Video Vision Transformer](https://mlsanity.com/paper/2103.15691/) (2021)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [AlpacaFarm: A Simulation Framework for Methods that Learn from Human Feedback](https://mlsanity.com/paper/2305.14387/) (2023)
- [A Survey on Visual Transformer](https://mlsanity.com/paper/2012.12556/) (2020)
- [Perceiver-Actor: A Multi-Task Transformer for Robotic Manipulation](https://mlsanity.com/paper/2209.05451/) (2022)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [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)
- [Speculative Decoding: Exploiting Speculative Execution for Accelerating Seq2seq Generation](https://mlsanity.com/paper/2203.16487/) (2022)
- [DistillSpec: Improving Speculative Decoding via Knowledge Distillation](https://mlsanity.com/paper/2310.08461/) (2023)
- [Speculative Decoding with Big Little Decoder](https://mlsanity.com/paper/2302.07863/) (2023)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)
- [Accelerating Transformer Inference for Translation via Parallel Decoding](https://mlsanity.com/paper/2305.10427/) (2023)
- [Online Speculative Decoding](https://mlsanity.com/paper/2310.07177/) (2023)
- [TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding](https://mlsanity.com/paper/2404.11912/) (2024)
- [Cascade Speculative Drafting for Even Faster LLM Inference](https://mlsanity.com/paper/2312.11462/) (2023)
- [Fast and Robust Early-Exiting Framework for Autoregressive Language Models with Synchronized Parallel Decoding](https://mlsanity.com/paper/2310.05424/) (2023)
- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024)
- [An Emulator for Fine-Tuning Large Language Models using Small Language Models](https://mlsanity.com/paper/2310.12962/) (2023)
- [LLMCad: Fast and Scalable On-device Large Language Model Inference](https://mlsanity.com/paper/2309.04255/) (2023)

## Built on by (most cited first, 29 of 29)

- [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025)
- [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025)
- [LK Losses: Direct Acceptance Rate Optimization for Speculative Decoding](https://mlsanity.com/paper/2602.23881/) (2026)
- [Grouped Speculative Decoding for Autoregressive Image Generation](https://mlsanity.com/paper/2508.07747/) (2025)
- [Draft Model Knows When to Stop: Self-Verification Speculative Decoding for Long-Form Generation](https://mlsanity.com/paper/2411.18462/) (2024)
- [L-MTP: Leap Multi-Token Prediction Beyond Adjacent Context for Large Language Models](https://mlsanity.com/paper/2505.17505/) (2025)
- [Speeding up Speculative Decoding via Sequential Approximate Verification](https://mlsanity.com/paper/2502.04557/) (2025)
- [Speculative Coupled Decoding for Training-Free Lossless Acceleration of Autoregressive Visual Generation](https://mlsanity.com/paper/2510.24211/) (2025)
- [Steering Pretrained Drafters during Speculative Decoding](https://mlsanity.com/paper/2511.09844/) (2025)
- [Multi-Drafter Speculative Decoding with Alignment Feedback](https://mlsanity.com/paper/2604.05417/) (2026)
- [DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification](https://mlsanity.com/paper/2604.07622/) (2026)
- [ATTS: Asynchronous Test-Time Scaling via Conformal Prediction](https://mlsanity.com/paper/2509.15148/) (2025)
- [A Practical Investigation of Training-free Relaxed Speculative Decoding](https://mlsanity.com/paper/2607.08690/) (2026)
- [SpecRouter: Adaptive Routing for Multi-Level Speculative Decoding in Large Language Models](https://mlsanity.com/paper/2505.07680/) (2025)
- [Accelerating Speculative Diffusions via Block Verification](https://mlsanity.com/paper/2606.13426/) (2026)
- [SpecMemo: Speculative Decoding is in Your Pocket](https://mlsanity.com/paper/2506.01986/) (2025)
- [Conformal Sparsification for Bandwidth-Efficient Edge-Cloud Speculative Decoding](https://mlsanity.com/paper/2510.09942/) (2025)
- [Polybasic Speculative Decoding Through a Theoretical Perspective](https://mlsanity.com/paper/2510.26527/) (2025)
- [Annealed Relaxation of Speculative Decoding for Faster Autoregressive Image Generation](https://mlsanity.com/paper/2601.09212/) (2026)
- [Improving the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models](https://mlsanity.com/paper/2602.01428/) (2026)
- [When Is a Draft Accepted? A Theory of Acceptance in Speculative Decoding](https://mlsanity.com/paper/2606.30265/) (2026)
- [ResiSpec: Enhancing Multi-Candidate Speculative Sampling via Residual Distribution Shaping](https://mlsanity.com/paper/2608.24411/) (2026)
- [Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks](https://mlsanity.com/paper/2512.11718/) (2025)
- [CSD: Content-aware Speculative Decoding for Efficient Image Generation](https://mlsanity.com/paper/2606.27829/) (2026)
- [BALANCE: Hybrid Autoregressive-Speculative LLM Inference at the Network Edge](https://mlsanity.com/paper/2608.05926/) (2026)
- [Vision Is Not Overhead: One-Pass Block Drafting for Lossless Speculative Decoding in Vision-Language Models](https://mlsanity.com/paper/2609.00355/) (2026)
- [Flash-dLLM: IO-Aware KV Caching and Parallel Decoding for Fast, Memory-Efficient Diffusion LLMs](https://mlsanity.com/paper/2609.26796/) (2026)
- [CAST: Cost-Aware Speculative Trees from One-Pass Block Drafters](https://mlsanity.com/paper/2610.00321/) (2026)
- [SP2ec: Adaptive Self-Speculative Decoding for Vision-Language Models](https://mlsanity.com/paper/2610.18735/) (2026)

## Abstract (arXiv)

Transformer-based autoregressive sampling has been the major bottleneck for slowing down large language model inferences. One effective way to accelerate inference is Speculative Decoding, which employs a small model to sample a sequence of draft tokens and a large model to validate. Given its empirical effectiveness, the theoretical understanding of Speculative Decoding is falling behind. This paper tackles this gap by conceptualizing the decoding problem via markov chain abstraction and studying the key properties, output quality and inference acceleration, from a theoretical perspective. Our analysis covers the theoretical limits of speculative decoding, batch algorithms, and output quality-inference acceleration tradeoffs. Our results reveal the fundamental connections between different components of LLMs via total variation distances and show how they jointly affect the efficiency of decoding algorithms.