# BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms

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

## Key facts

- Cited by 20 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 31 of its 53 references that are in the map.
- First posted on arXiv 21 May 2025.

## Placed in

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

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [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)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [Mixture-of-Agents Enhances Large Language Model Capabilities](https://mlsanity.com/paper/2406.04692/) (2024)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [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)
- [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)
- [Online Speculative Decoding](https://mlsanity.com/paper/2310.07177/) (2023)
- [Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding](https://mlsanity.com/paper/2402.12374/) (2024)
- [TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding](https://mlsanity.com/paper/2404.11912/) (2024)
- [GliDe with a CaPE: A Low-Hassle Method to Accelerate Speculative Decoding](https://mlsanity.com/paper/2402.02082/) (2024)
- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [SAM Decoding: Speculative Decoding via Suffix Automaton](https://mlsanity.com/paper/2411.10666/) (2024)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Block Verification Accelerates Speculative Decoding](https://mlsanity.com/paper/2403.10444/) (2024)
- [A Theoretical Perspective for Speculative Decoding Algorithm](https://mlsanity.com/paper/2411.00841/) (2024)
- [Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions](https://mlsanity.com/paper/2010.07904/) (2020)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits](https://mlsanity.com/paper/2410.07638/) (2024)

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

- [Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs](https://mlsanity.com/paper/2510.20064/) (2025)
- [Nightjar: Dynamic Adaptive Speculative Decoding for Large Language Models Serving](https://mlsanity.com/paper/2512.22420/) (2025)
- [Sparse-to-Dense: A Free Lunch for Lossless Acceleration of Video Understanding in LLMs](https://mlsanity.com/paper/2505.19155/) (2025)
- [Multi-Drafter Speculative Decoding with Alignment Feedback](https://mlsanity.com/paper/2604.05417/) (2026)
- [SpecBlock: Block-Iterative Speculative Decoding with Dynamic Tree Drafting](https://mlsanity.com/paper/2605.07243/) (2026)
- [TapOut: A Bandit-Based Approach to Dynamic Speculative Decoding](https://mlsanity.com/paper/2511.02017/) (2025)
- [AHASD: Asynchronous Heterogeneous Architecture for LLM Adaptive Drafting Speculative Decoding on Mobile Devices](https://mlsanity.com/paper/2604.25326/) (2026)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [TIDE: Temporal Incremental Draft Engine for Self-Improving LLM Inference](https://mlsanity.com/paper/2602.05145/) (2026)
- [MineDraft: A Framework for Batch Parallel Speculative Decoding](https://mlsanity.com/paper/2603.18016/) (2026)
- [FASER: Fine-Grained Phase Management for Speculative Decoding in Dynamic LLM Serving](https://mlsanity.com/paper/2604.20503/) (2026)
- [To Copy or Not to Copy: Controlling Speculative Decoding via Intrinsic Model Signals](https://mlsanity.com/paper/2609.20186/) (2026)
- [Speculative Sampling with Reinforcement Learning](https://mlsanity.com/paper/2601.12212/) (2026)
- [LibraSpec: Dynamic Diffusion-Based Speculative Decoding via Marginal-Gain-Driven Optimization](https://mlsanity.com/paper/2608.08721/) (2026)
- [MemSpec: Memory-Aware Runtime for Adaptive Draft Scheduling in Speculative Decoding on Edge Devices](https://mlsanity.com/paper/2608.10362/) (2026)
- [Bandits in Prod: Hyperparameter Optimization at Inference Time](https://mlsanity.com/paper/2609.01335/) (2026)
- [CAST: Cost-Aware Speculative Trees from One-Pass Block Drafters](https://mlsanity.com/paper/2610.00321/) (2026)
- [AdaSpark: Adaptive DSpark with Online Learning for Tree Verification and N-gram Fill](https://mlsanity.com/paper/2610.05774/) (2026)
- [APEX: Speculate smarter, not deeper](https://mlsanity.com/paper/2610.07780/) (2026)
- [SP2ec: Adaptive Self-Speculative Decoding for Vision-Language Models](https://mlsanity.com/paper/2610.18735/) (2026)

## Abstract (arXiv)

Speculative decoding has emerged as a popular method to accelerate the inference of Large Language Models (LLMs) while retaining their superior text generation performance. Previous methods either adopt a fixed speculative decoding configuration regardless of the prefix tokens, or train draft models in an offline or online manner to align them with the context. This paper proposes a training-free online learning framework to adaptively choose the configuration of the hyperparameters for speculative decoding as text is being generated. We first formulate this hyperparameter selection problem as a Multi-Armed Bandit problem and provide a general speculative decoding framework BanditSpec. Furthermore, two bandit-based hyperparameter selection algorithms, UCBSpec and EXP3Spec, are designed and analyzed in terms of a novel quantity, the stopping time regret. We upper bound this regret under both stochastic and adversarial reward settings. By deriving an information-theoretic impossibility result, it is shown that the regret performance of UCBSpec is optimal up to universal constants. Finally, extensive empirical experiments with LLaMA3 and Qwen2 demonstrate that our algorithms are effective compared to existing methods, and the throughput is close to the oracle best hyperparameter in simulated real-life LLM serving scenarios with diverse input prompts.