# Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement

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

## Key facts

- Cited by 27 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 17 of its 25 references that are in the map.
- First posted on arXiv 21 Feb 2024.

## Placed in

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

## Builds on (most cited first, 17 of 17)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Fast Transformer Decoding: One Write-Head is All You Need](https://mlsanity.com/paper/1911.02150/) (2019)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [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)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)

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

- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024)
- [OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure](https://mlsanity.com/paper/2406.17276/) (2024)
- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [A Theoretical Perspective for Speculative Decoding Algorithm](https://mlsanity.com/paper/2411.00841/) (2024)
- [Accelerating Speculative Decoding with Block Diffusion Draft Trees](https://mlsanity.com/paper/2604.12989/) (2026)
- [On Speculative Decoding for Multimodal Large Language Models](https://mlsanity.com/paper/2404.08856/) (2024)
- [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025)
- [Structuring The Future: Diffusion LLM Speculative Decoding via Calibrated Draft Graphs](https://mlsanity.com/paper/2509.18085/) (2025)
- [Towards Optimal Multi-draft Speculative Decoding](https://mlsanity.com/paper/2502.18779/) (2025)
- [Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits](https://mlsanity.com/paper/2410.18234/) (2024)
- [VOCABTRIM: Vocabulary Pruning for Efficient Speculative Decoding in LLMs](https://mlsanity.com/paper/2506.22694/) (2025)
- [SpecHub: Provable Acceleration to Multi-Draft Speculative Decoding](https://mlsanity.com/paper/2411.05289/) (2024)
- [STree: Speculative Tree Decoding for Hybrid State-Space Models](https://mlsanity.com/paper/2505.14969/) (2025)
- [Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding](https://mlsanity.com/paper/2411.13157/) (2024)
- [Efficient Speculative Decoding for Llama at Scale: Challenges and Solutions](https://mlsanity.com/paper/2508.08192/) (2025)
- [Constrained Decoding with Speculative Lookaheads](https://mlsanity.com/paper/2412.10418/) (2024)
- [Token-Driven GammaTune: Adaptive Calibration for Enhanced Speculative Decoding](https://mlsanity.com/paper/2504.00030/) (2025)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression](https://mlsanity.com/paper/2506.05632/) (2025)
- [Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling](https://mlsanity.com/paper/2604.04987/) (2026)
- [EMS-SD: Efficient Multi-sample Speculative Decoding for Accelerating Large Language Models](https://mlsanity.com/paper/2405.07542/) (2024)
- [Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization](https://mlsanity.com/paper/2511.15898/) (2025)
- [Speculative Sampling with Reinforcement Learning](https://mlsanity.com/paper/2601.12212/) (2026)
- [ConFu: Contemplate the Future for Better Speculative Sampling](https://mlsanity.com/paper/2603.08899/) (2026)
- [Efficient Training-Free Multi-Token Prediction via Embedding-Space Probing](https://mlsanity.com/paper/2603.17942/) (2026)
- [X-CoSD: Communication-Efficient Cross-Vocabulary Collaborative Speculative Decoding](https://mlsanity.com/paper/2609.09166/) (2026)
- [Tsubame: Tree Replay for Diffusion-Based Speculative Decoding](https://mlsanity.com/paper/2609.33652/) (2026)

## Abstract (arXiv)

Speculative decoding is an inference-acceleration method for large language models (LLMs) where a small language model generates a draft-token sequence which is further verified by the target LLM in parallel. Recent works have advanced this method by establishing a draft-token tree, achieving superior performance over a single-sequence speculative decoding. However, those works independently generate tokens at each level of the tree, not leveraging the tree's entire diversifiability. Besides, their empirical superiority has been shown for fixed length of sequences, implicitly granting more computational resource to LLM for the tree-based methods. None of the existing works has conducted empirical studies with fixed target computational budgets despite its importance to resource-bounded devices. We present Recursive Speculative Decoding (RSD), a novel tree-based method that samples draft tokens without replacement and maximizes the diversity of the tree. During RSD's drafting, the tree is built by either Gumbel-Top-k trick that draws tokens without replacement in parallel or Stochastic Beam Search that samples sequences without replacement while early-truncating unlikely draft sequences and reducing the computational cost of LLM. We empirically evaluate RSD with Llama 2 and OPT models, showing that RSD outperforms the baseline methods, consistently for fixed draft sequence length and in most cases for fixed computational budgets at LLM.