Research map / Large language models / Reasoning and chain of thought
A Theoretical Perspective for Speculative Decoding Algorithm
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.
Gives a Markov-chain theory of speculative decoding: exact expected rejections (= TV distances, hence speedup T/E[rejections]), proves SD is optimal among unbiased rejection-based algorithms, analyzes batch SD, and derives a linear Pareto front between rejection probability and output distribution bias.
Problem
Speculative decoding accelerates LLM inference empirically, but there is no precise theory of how draft/target distribution mismatch determines its speedup, whether it can be improved, and how speed trades off against output quality.
Approach
Model decoding as a Markov chain, show expected rejections equal sums of TV distances between draft and target conditionals (so speedup = T/#rejections), prove unbiased rejection-based algorithms cannot beat SD's rejection count, analyze a batch DFS variant with a closed-form improvement term, and derive the optimal biased-decoding distribution yielding a linear rejection vs. TV-bias Pareto front.
Key results
- Exact formula: expected rejections of speculative decoding equals sum over positions of expected TV distance between draft and target conditionals; in a T=50 Markov-chain simulation the expected rejections converge to 16.41 (acceleration 3.05x).
- Theorem shows no unbiased rejection-based algorithm can have fewer expected rejections than speculative decoding, so SD is instance-optimal in that class.
- On Alpaca-Farm-Eval with pythia-70m draft and pythia-2.8b target, Decoding-OPT beats Decoding-UNO in win rate across epsilon values (e.g., 53% vs 47% at epsilon=0.1 under RM-Mistral-7B).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Decoding-OPT's optimal rejection distribution instead of Decoding-UNO's target distribution, with RM-Mistral-7B evaluation | Decoding-OPT versus Decoding-UNO · Alpaca-Farm-Eval, ε=0.1, 0.2, 0.4, and 0.8 | WinRate: 53% vs 47%; 53.5% vs 46.5%; 57.5% vs 42.5%; 52.5% vs 47.5% | Helped |
| Use Decoding-OPT's optimal rejection distribution instead of Decoding-UNO's target distribution, with GPT-4 evaluation | Decoding-OPT versus Decoding-UNO · Alpaca-Farm-Eval, ε=0.1, 0.2, 0.4, and 0.8 | WinRate: 54.5% vs 45.5%; 53% vs 47%; 53.5% vs 46.5%; 55% vs 45% | Helped |
| Use multiple draft sequences in parallel with batch speculative decoding instead of non-batch speculative decoding | Batch Speculative Decoding · Decoding under draft-target distribution mismatch | Expected rejections | Helped |
| Change the acceptance probability and rejection distribution while requiring distribution unbiasedness | Rejection-based decoding · Sequential decoding | Expected rejections | No clear effect |
Surprising findings
- With batch size going to infinity the expected rejections do not go to zero when draft and target distributions differ substantially, so large draft batches do not guarantee large speedups.
- Accepting a looser acceptance threshold can strictly reduce rejections only at the cost of bias, with a linear Pareto front between rejection probability and TV bias.
Limitations
- Batch speculative decoding is not shown to be optimal; the authors state batch optimality remains open.
- Assumes draft cost is negligible and each oracle call costs O(1), ignoring memory and practical overhead.
- Quality experiment is small (single draft/target pair, 200 prompts) and uses win rate from judge models rather than TV.
Experimental setup
Datasets: Alpaca-Farm-Eval
Benchmarks: Alpaca-Farm-Eval
Metrics: expected rejections TV distance win rate acceleration rate
Baselines: Speculative Decoding Decoding-UNO
Builds on: speculative decoding speculative sampling SpecInfer
Closest papers by meaning
- SPEED-Bench: A Unified and Diverse Benchmark for Speculative Decoding (ICML 2026 · similarity 0.94)
- polybasic Speculative Decoding Through a Theoretical Perspective (ICML 2025 · similarity 0.93)
- Speculative Speculative Decoding (ICLR 2026 · similarity 0.92)
- Scaling LLM Speculative Decoding: Non-Autoregressive Forecasting in Large-Batch Scenarios (AAAI 2026 · similarity 0.92)
- Online Speculative Decoding (ICML 2024 · similarity 0.92)
- MoESD: Unveil Speculative Decoding's Potential for Accelerating Sparse MoE (NeurIPS 2025 · similarity 0.92)
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.