Research map / Learning theory and algorithms / Sample complexity
List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression
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.
Proposes Gumbel-max list sampling (GLS), a coupling of one target sample with K draft samples via shared exponential races, and applies it to drafter-invariant multi-draft speculative decoding and distributed lossy compression with side information.
Problem
Coupling distributions when one party generates a list of K samples and success requires the other party's sample to match any of them, without communication; applied to multi-draft speculative decoding and distributed lossy compression with side information.
Approach
Extends Gumbel-max coupling to list settings by taking a minimum over shared exponential variables across the K draft races for the target sample, while each draft uses its own race; yields a list matching lemma lower bound and a speculative decoding scheme that does not use rejection sampling and is conditionally drafter invariant.
Key results
- With i.i.d. drafts (K=8, L=4) on Qwen 2.5 7B/0.5B, the GLS scheme matches SpecInfer and SpecTr token rates within one standard error, e.g. 4.83% vs 4.56% and 3.75% on GSM8K.
- With diverse drafts (K=2, mismatched temperatures), GLS outperforms SpecInfer, e.g. 11.50% vs 0.06% token-rate speedup on GSM8K in the 0.5/1.0 configuration.
- On Gaussian and MNIST compression, GLS with multiple decoders improves matching probability and rate-distortion over a shared-randomness baseline, particularly at low rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GLS multi-draft speculative decoding instead of SpecInfer | Qwen 2.5-7B with Qwen 2.5-0.5B i.i.d. drafts · GSM8K | TR (%): 4.56(20) -> 4.83(24) | No clear effect |
| Use GLS multi-draft speculative decoding instead of SpecInfer | Qwen 2.5-7B with Qwen 2.5-0.5B i.i.d. drafts · HumanEval | TR (%): 7.89(85) -> 8.03(97) | No clear effect |
| Use GLS multi-draft speculative decoding instead of SpecTr | Qwen 2.5-7B with Qwen 2.5-0.5B i.i.d. drafts · NaturalReasoning | TR (%): 12.89(96) -> 12.75(114) | No clear effect |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 0.5/1.0 | Qwen 2.5-7B · GSM8K | TR (%): 0.06(102) -> 11.50(178) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 1.0/0.5 | Qwen 2.5-7B · GSM8K | TR (%): 4.57(180) -> 11.40(158) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 1.0/1.0 | Qwen 2.5-7B · GSM8K | TR (%): 6.02(135) -> 13.68(167) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 0.5/1.0 | Qwen 2.5-7B · HumanEval | TR (%): -1.96(67) -> 9.80(82) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 1.0/0.5 | Qwen 2.5-7B · HumanEval | TR (%): 4.13(160) -> 8.77(99) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 1.0/1.0 | Qwen 2.5-7B · HumanEval | TR (%): 6.32(36) -> 12.15(83) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 0.5/1.0 | Qwen 2.5-7B · MBPP | TR (%): -1.87(79) -> 5.64(66) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 1.0/0.5 | Qwen 2.5-7B · MBPP | TR (%): 4.77(55) -> 5.99(101) | Helped |
| Use GLS multi-draft decoding instead of SpecInfer with draft temperatures 1.0/1.0 | Qwen 2.5-7B · MBPP | TR (%): 5.17(1.13) -> 8.57(60) | Helped |
Surprising findings
- SpecInfer can run slower than single-draft speculative decoding when the first drafter's temperature deviates most from the target, a weakness that disappears when draft order is swapped.
Limitations
- Memory and computation scale with vocabulary size O(NK); top-K sampling is needed for large vocabularies.
- Compression requires shared randomness between encoder and decoders, and the error analysis assumes deterministic floating-point behavior.
- Speculative decoding gains vanish with poorly aligned drafts or extreme temperature mismatch.
Experimental setup
Datasets: GSM8K HumanEval NaturalReasoning MBPP MNIST
Benchmarks: GSM8K HumanEval NaturalReasoning MBPP MNIST
Metrics: block efficiency token rate speedup matching probability rate-distortion
Baselines: SpecInfer SpecTr single-draft drafter-invariant speculative decoding (Daliri et al.) single-draft speculative decoding shared-randomness baseline for compression
Builds on: Gumbel-max sampling Daliri et al. drafter-invariant speculative decoding Poisson matching lemma SpecInfer SpecTr
Closest papers by meaning
- A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.89)
- Accelerated Speculative Sampling Based on Tree Monte Carlo (ICML 2024 · similarity 0.88)
- Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding (ICLR 2026 · similarity 0.88)
- Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling (ICLR 2026 · similarity 0.88)
- LK Losses: Direct Acceptance Rate Optimization for Speculative Decoding (ICML 2026 · similarity 0.87)
- Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Optimization (ICLR 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.