Research map / Large language models / Reasoning and chain of thought
Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits
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.
Shows the optimal multi-draft token selection decomposes into importance-weighted selection followed by single-draft speculative sampling, gives closed-form optimal acceptance for K=2 identical drafts, and proposes faster truncated LP and alphabet variants evaluated on OPT models.
Problem
Maximizing the probability that one of K i.i.d. draft tokens is accepted while the output exactly follows the target distribution in multi-draft speculative sampling, where the optimal scheme was previously only known as a linear program with no closed form.
Approach
Decomposes the optimal token-level selection rule into an importance-weighted selection of one intermediate draft token followed by standard single-draft speculative sampling; for K=2 identical drafts derives a necessary and sufficient condition for acceptance probability 1 and an explicit closed-form optimal acceptance probability, plus a truncated LP for faster computation.
Key results
- For K=2 identical drafts with p=[1/3,1/3,1/3] and q=[1/3,q2,2/3-q2], the optimal acceptance probability reaches 1 over a wide range of q2, while SpecTr and SpecInfer reach 1 only at q2=1/3.
- On Dolly with top-k=10 and K=2 drafts, the IS scheme achieves block efficiency 2.48 ± 0.01 versus 2.43 for SpecTr and 2.38 for SpecInfer.
- Across XSum, Dolly, and WMT tasks the proposed importance sampling scheme consistently improves block efficiency and token rate over SpecInfer and the single-draft baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use importance sampling instead of SpecInfer | Multi-draft speculative sampling · XSUM, top-k k=5, K=2 | acceptance probability: 0.4875 -> 0.4933 | Helped |
| Use importance sampling instead of SpecTr | Multi-draft speculative sampling · Dolly, top-k k=5, K=2 | acceptance probability: 0.6246 -> 0.6348 | Helped |
| Use IS instead of SpecTr | Multi-draft speculative sampling · Dolly, top-k k=10, K=2 | block efficiency: $2.43 \pm 0.01$ -> $2.48 \pm 0.01$ | Helped |
| Use IS instead of SpecInfer | Multi-draft speculative sampling · Dolly, top-k k=5, K=3 | block efficiency: $2.55 \pm 0.04$ -> $2.63 \pm 0.03$ | Helped |
| Increase vocabulary truncation size from 10 to 40 (ablation) | IS scheme · Top-p sampling, second draft temperature 2.0 | block efficiency: 1.98 $\pm$ 0.03 -> 2.05 $\pm$ 0.04 | Helped |
| Increase vocabulary truncation size from 10 to 40 (ablation) | IS scheme · Top-p sampling, second draft temperature 2.0 | token rate: -0.57 $\pm$ 3.38\% -> 6.63 $\pm$ 3.18\% | Helped |
| Increase vocabulary truncation size from 40 to 50 (ablation) | IS scheme · Top-p sampling, second draft temperature 2.0 | token rate: 6.63 $\pm$ 3.18\% -> 3.22 $\pm$ 3.39\% | Hurt |
| Set LP truncation threshold to 5 instead of 10 (ablation) | IS scheme · Top-p sampling, second draft temperature 2.0 | token rate: 1.52 $\pm$ 3.47\% -> 6.63 $\pm$ 3.18\% | Helped |
| Set LP truncation threshold to 5 instead of 15 (ablation) | IS scheme · Top-p sampling, second draft temperature 2.0 | token rate: 1.74 $\pm$ 2.36\% -> 6.63 $\pm$ 3.18\% | Helped |
| Increase the number of drafts | Optimal token-level selection · XSUM, top-k k=5 | acceptance probability: 0.5009 -> 0.5226 -> 0.5419 | Helped |
Surprising findings
- With K=2 drafts the optimal acceptance probability can equal 1 even when the draft and target distributions differ, unlike the single-draft case where equality requires p=q.
Experimental setup
Datasets: XSum Databricks-Dolly-15k WMT18
Benchmarks: XSum Databricks-Dolly-15k WMT18
Metrics: block efficiency token rate acceptance probability ROUGE-L BLEU
Baselines: SpecTr SpecInfer single-draft speculative sampling
Builds on: speculative sampling SpecTr SpecInfer
Closest papers by meaning
- Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Optimization (ICLR 2026 · similarity 0.90)
- Accelerated Diffusion Models via Speculative Sampling (ICML 2025 · similarity 0.88)
- Accelerated Speculative Sampling Based on Tree Monte Carlo (ICML 2024 · similarity 0.88)
- Towards Optimal Multi-draft Speculative Decoding (ICLR 2025 · similarity 0.88)
- Learning To Draft: Adaptive Speculative Decoding with Reinforcement Learning (ICLR 2026 · similarity 0.87)
- D-PACE: Dynamic Position-Aware Cross-Entropy for Parallel Speculative Drafting (NeurIPS 2026 · similarity 0.87)
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.