Research map / Bandits and online learning / Multi-armed bandits
BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames speculative decoding hyperparameter selection (draft model, speculation length) as a multi-armed bandit and proposes training-free UCBSpec and EXP3Spec with a stopping-time regret analysis.
Problem
Speculative decoding uses a fixed configuration (draft model, speculation structure) regardless of prompt, yet the best configuration varies across tasks and prefixes; latency-minimizing per-step selection is needed.
Approach
Model per-round hyperparameter choice as a bandit where reward is accepted token count, and analyze a novel stopping-time regret; UCBSpec (UCB-style with modified confidence radius, self-normalized concentration) and EXP3Spec (anytime EXP3) are training-free and provably near-optimal under stochastic and adversarial settings.
Key results
- On Debug Bench, UCBSpec improves throughput by about 13% for LLaMA3-8B-Instruct and 19% for Qwen2-7B-Instruct over the best fixed baseline (Eagle-2).
- UCBSpec reaches 3.98 MAT and 105.72 tokens/s on Spec Bench with LLaMA3-8B-Instruct, versus 3.94 and 98.15 for Eagle-2.
- In batched serving experiments with speculation length arms, UCBSpec tracks the oracle-best speculation length closely across batch sizes 1 to 50.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive UCB draft-model selection instead of fixed Eagle-2 | LLaMA3-8B-Instruct speculative decoding · Spec Bench, Alpaca, Code Editor, and Debug Bench | Tokens/s: 98.15 -> 105.72; 110.00 -> 125.78; 128.76 -> 138.27; 119.12 -> 135.34 | Helped |
| Use adaptive EXP3 draft-model selection instead of fixed Eagle-2 | LLaMA3-8B-Instruct speculative decoding · Spec Bench, Alpaca, Code Editor, and Debug Bench | Tokens/s: 98.15 -> 102.10; 110.00 -> 120.38; 128.76 -> 137.29; 119.12 -> 132.25 | Helped |
| Use adaptive UCB draft-model selection instead of fixed Eagle-2 | Qwen2-7B-Instruct speculative decoding · Spec Bench, Alpaca, Code Editor, and Debug Bench | Tokens/s: 97.82 -> 112.33; 104.43 -> 114.20; 138.58 -> 161.35; 126.01 -> 151.37 | Helped |
| Use adaptive EXP3 draft-model selection instead of fixed Eagle-2 | Qwen2-7B-Instruct speculative decoding · Spec Bench, Alpaca, Code Editor, and Debug Bench | Tokens/s: 97.82 -> 107.36; 104.43 -> 113.90; 138.58 -> 160.41; 126.01 -> 151.73 | Helped |
| Use UCB rather than EXP3 for adaptive draft-model selection | LLaMA3-8B-Instruct speculative decoding · Spec Bench, Alpaca, Code Editor, and Debug Bench | Tokens/s: 102.10 -> 105.72; 120.38 -> 125.78; 137.29 -> 138.27; 132.25 -> 135.34 | Helped |
| Use UCB rather than EXP3 for adaptive draft-model selection | Qwen2-7B-Instruct speculative decoding · Spec Bench, Alpaca, Code Editor, and Debug Bench | Tokens/s: 107.36 -> 112.33; 113.90 -> 114.20; 160.41 -> 161.35; 151.73 -> 151.37 | Mixed |
| Adapt speculation length with UCB instead of fixing a single length | Eagle-1 speculation-length selection · Alpaca prompts, batch sizes 1 to 50 (LLaMA3-8B-Instruct and Qwen2-7B-Instruct) | throughput improvement over canonical decoding | Helped |
Surprising findings
- The original Eagle-1 with speculation length 4 is inferior to canonical decoding for a portion of prompts, showing fixed configurations can hurt performance.
Limitations
- Theory relies on stationary-mean or oblivious-adversary assumptions that may not match real decoding exactly
- Stopping-time regret analysis uses assumptions such as finite expected generation length and that the best arm stops first
- Only K-armed bandits are considered; structured or contextual extensions are left to future work
Experimental setup
Datasets: Spec Bench Alpaca Code Editor Debug Bench
Benchmarks: Spec Bench Alpaca Code Editor Debug Bench
Metrics: Mean Accepted Tokens (MAT) Tokens/s stopping time regret
Baselines: Vanilla decoding PLD Rest Suffix Tree Eagle-2 Eagle-1 SpecDec++
Builds on: speculative decoding UCB1 EXP3 Medusa Eagle
Closest papers by meaning
- Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs (ICLR 2026 · similarity 0.95)
- A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.91)
- Online Speculative Decoding (ICML 2024 · similarity 0.91)
- Learning To Draft: Adaptive Speculative Decoding with Reinforcement Learning (ICLR 2026 · similarity 0.91)
- Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment (ICLR 2025 · similarity 0.90)
- Reward-Guided Speculative Decoding for Efficient LLM Reasoning (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.