Research map / Large language models / Reasoning and chain of thought
Towards Optimal Multi-draft Speculative Decoding
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.
Derives a dual/subset-selection formulation of the optimal acceptance rate for multi-draft speculative decoding, computes it efficiently for with- and without-replacement sampling, and proposes a greedy draft construction with a matching verification algorithm.
Problem
Computing the optimal acceptance rate of multi-draft speculative decoding is an exponentially large optimal transport problem, so the theoretical upper bound for realistic vocabularies (thousands of tokens) and the gap of existing verification algorithms (RRS, K-SEQ) were unknown.
Approach
Dualize the optimal transport LP, show total unimodularity so the dual has integer solutions, reducing the optimal acceptance rate to a subset selection problem; exploit q-convexity of the draft-coverage set function to solve it by sorting q/p ratios and a linear scan. Also propose a greedy draft scheme (top n-1 tokens deterministically, last token sampled without replacement) with a verifier that
Key results
- On Alpaca with OPT-125M/OPT-6.7B (with replacement), the optimal acceptance rate is 86.9% versus 85.8% for K-SEQ and 85.4% for RRS.
- Without-replacement sampling achieves higher optimal acceptance than with-replacement (e.g., 89.9% vs 86.9% on Alpaca, OPT pair), and greedy draft reaches 90.7%, matching its theoretical optimum.
- On MT-Bench at T=0.1 with 4 drafts, the greedy method reaches 88.8% acceptance versus 80.4% for RRS without replacement, with a 1.17x speedup.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy draft sampling and verification instead of RRS with without-replacement drafts | MDSD with OPT-125M → OPT-6.7B · Alpaca, CNN-DailyMail, WMT'14 De-En | acceptance rate α: 88.9 ± 0.1 -> 90.7 ± 0.1; 81.5 ± 0.1 -> 84.2 ± 0.1; 75.1 ± 0.1 -> 77.0 ± 0.1 | Helped |
| Use greedy draft sampling instead of without-replacement sampling | MDSD with LLaMA-68M → LLaMA-7B · Alpaca, CNN-DailyMail, WMT'14 De-En | acceptance rate α: 75.7 ± 0.1 -> 78.4 ± 0.1; 70.5 ± 0.1 -> 73.2 ± 0.1; 63.3 ± 0.1 -> 66.1 ± 0.1 | Helped |
| Use greedy draft sampling instead of without-replacement sampling | MDSD with Eagle-0.24B → Vicuna-7B · Alpaca, CNN-DailyMail, WMT'14 De-En | acceptance rate α: 70.9 ± 0.2 -> 72.6 ± 0.2; 63.4 ± 0.1 -> 65.7 ± 0.1; 36.9 ± 0.2 -> 39.5 ± 0.2 | Helped |
| Use greedy draft sampling instead of without-replacement sampling | MDSD with Eagle-0.26B → Qwen2-7B · Alpaca, CNN-DailyMail, WMT'14 De-En | acceptance rate α: 68.3 ± 0.2 -> 69.9 ± 0.2; 52.4 ± 0.1 -> 54.0 ± 0.1; 43.9 ± 0.1 -> 45.5 ± 0.1 | Helped |
| Use sampling without replacement rather than with replacement | MDSD verification methods · Alpaca, CNN-DailyMail, WMT'14 De-En | acceptance rate α | Helped |
| Use greedy rather than RRS without replacement | Vicuna-7B-v1.3 / EAGLE 0.24B · MT-Bench, T=0.1, 2 drafts/4 steps | acceptance rate α: 79.4 ± 0.3 -> 84.7 ± 0.3 | Helped |
| Use greedy rather than SpecHub | Vicuna-7B-v1.3 / EAGLE 0.24B · MT-Bench, 2 drafts/4 steps | acceptance rate α | No clear effect |
| Increase the number of drafts (ablation) | MDSD methods · Datasets in the number-of-drafts ablation | acceptance rate α | Helped |
| Raise temperature (ablation) | MDSD methods · Datasets in the temperature ablation | acceptance rate α | Mixed |
| Raise temperature (ablation) | Greedy sampling relative to RRS without replacement · MT-Bench | acceptance rate α: 84.7 ± 0.3 -> 79.2 ± 0.3 | Hurt |
Surprising findings
- The greedy draft method does not always dominate; at temperature 1.0 it underperforms RRS without replacement under the EAGLE sparse tree setting.
- The gap between existing verifiers and the optimum grows with temperature and with the number of drafts.
Limitations
- Analysis restricted to single-step multi-draft speculative decoding; multi-step tree settings are not covered by the optimality results.
- Experiments use only 1024 samples per task with max 128 tokens to estimate distributions.
- Greedy method's advantage is not uniform across temperatures and settings.
Experimental setup
Datasets: Alpaca WMT'14 De-En CNN-DailyMail MT-Bench
Benchmarks: Alpaca WMT'14 De-En CNN-DailyMail MT-Bench
Metrics: acceptance rate gap to optimal acceptance rate speedup
Baselines: RRS K-SEQ SpecHub RRS without replacement
Builds on: speculative sampling Recursive Rejection Sampling K-SEQ SpecHub EAGLE
Closest papers by meaning
- Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration (NeurIPS 2024 · similarity 0.92)
- UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding (NeurIPS 2026 · similarity 0.92)
- Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Optimization (ICLR 2026 · similarity 0.91)
- Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs (ICLR 2026 · similarity 0.91)
- Learning To Draft: Adaptive Speculative Decoding with Reinforcement Learning (ICLR 2026 · similarity 0.91)
- A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.91)
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.