# Dynamic-Width Speculative Beam Decoding for Efficient LLM Inference

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

## Key facts

- Cited by 5 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 22 of its 36 references that are in the map.
- First posted on arXiv 25 Sep 2024.

## Placed in

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [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)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (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)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [Movement Pruning: Adaptive Sparsity by Fine-Tuning](https://mlsanity.com/paper/2005.07683/) (2020)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement](https://mlsanity.com/paper/1802.06901/) (2018)
- [Speculative Decoding with Big Little Decoder](https://mlsanity.com/paper/2302.07863/) (2023)
- [GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM](https://mlsanity.com/paper/2403.05527/) (2024)
- [A Thorough Examination of Decoding Methods in the Era of LLMs](https://mlsanity.com/paper/2402.06925/) (2024)
- [Fast Structured Decoding for Sequence Models](https://mlsanity.com/paper/1910.11555/) (2019)
- [Non-Autoregressive Machine Translation with Auxiliary Regularization](https://mlsanity.com/paper/1902.10245/) (2019)
- [Accelerating the inference of string generation-based chemical reaction models for industrial applications](https://mlsanity.com/paper/2407.09685/) (2024)

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

- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025)
- [C2T: A Classifier-Based Tree Construction Method in Speculative Decoding](https://mlsanity.com/paper/2502.13652/) (2025)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [Hierarchical Verification of Speculative Beams for Accelerating LLM Inference](https://mlsanity.com/paper/2508.03726/) (2025)

## Abstract (arXiv)

Large language models (LLMs) have shown outstanding performance across numerous real-world tasks. However, the autoregressive nature of these models makes the inference process slow and costly. Speculative decoding has emerged as a promising solution, leveraging a smaller auxiliary model to draft future tokens, which are then validated simultaneously by the larger model, achieving a speed-up of 1-2x. Although speculative decoding matches the same distribution as multinomial sampling, multinomial sampling itself is prone to suboptimal outputs, whereas beam sampling is widely recognized for producing higher-quality results by maintaining multiple candidate sequences at each step. This paper explores the novel integration of speculative decoding with beam sampling. However, there are four key challenges: (1) how to generate multiple sequences from the larger model's distribution given drafts sequences from the small model; (2) how to dynamically optimize the number of beams to balance efficiency and accuracy; (3) how to efficiently verify the multiple drafts in parallel; and (4) how to address the extra memory costs inherent in beam sampling. To address these challenges, we propose dynamic-width speculative beam decoding (DSBD). Specifically, we first introduce a novel draft and verification scheme that generates multiple sequences following the large model's distribution based on beam sampling trajectories from the small model. Then, we introduce an adaptive mechanism to dynamically tune the number of beams based on the context, optimizing efficiency and effectiveness. Besides, we extend tree-based parallel verification to handle multiple trees simultaneously, accelerating the verification process. Finally, we illustrate a simple modification to our algorithm to mitigate the memory overhead of beam sampling...