# Coupling without Communication and Drafter-Invariant Speculative Decoding

arXiv: https://arxiv.org/abs/2408.07978 · HTML: https://mlsanity.com/paper/2408.07978/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 15 Aug 2024.

## Builds on (most cited first, 18 of 18)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [A Review for Weighted MinHash Algorithms](https://mlsanity.com/paper/1811.04633/) (2018)
- [Sampling Methods for Inner Product Sketching](https://mlsanity.com/paper/2309.16157/) (2023)
- [Consistent Weighted Sampling Made Fast, Small, and Easy](https://mlsanity.com/paper/1410.4266/) (2014)
- [Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation](https://mlsanity.com/paper/2301.05811/) (2023)
- [Stream Sampling for Frequency Cap Statistics](https://mlsanity.com/paper/1502.05955/) (2015)
- [DartMinHash: Fast Sketching for Weighted Sets](https://mlsanity.com/paper/2005.11547/) (2020)
- [Simple Analysis of Priority Sampling](https://mlsanity.com/paper/2308.05907/) (2023)

## Built on by (most cited first, 6 of 6)

- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression](https://mlsanity.com/paper/2506.05632/) (2025)
- [Trees from Marginals: Autoregressive drafting with factorized priors](https://mlsanity.com/paper/2607.06763/) (2026)
- [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026)
- [Watermarkable Multi-Draft Speculative Sampling via Poisson Processes](https://mlsanity.com/paper/2609.21858/) (2026)
- [Rank-Aware Speculative Sampling for Diffusion Draft Trees](https://mlsanity.com/paper/2610.02251/) (2026)

## Abstract (arXiv)

Suppose Alice has a distribution P and Bob has a distribution Q. Alice wants to draw a sample a~ P and Bob a sample b ~ Q such that a = b with as high of probability as possible. It is well-known that, by sampling from an optimal coupling between the distributions, Alice and Bob can achieve Pr[a = b] = 1 - DTV(P,Q), where DTV(P,Q) is the total variation distance between P and Q. What if Alice and Bob must solve this same problem without communicating at all? Perhaps surprisingly, with access to public randomness, they can still achieve Pr[a = b] ≥ frac1 - DTV(P,Q)1 + DTV(P,Q) ≥ 1-2DTV(P,Q) using a simple protocol based on the Weighted MinHash algorithm. This bound was shown to be optimal in the worst-case by [Bavarian et al., 2020]. In this work, we revisit the communication-free coupling problem. We provide a simpler proof of the optimality result from [Bavarian et al., 2020]. We show that, while the worst-case success probability of Weighted MinHash cannot be improved, an equally simple protocol based on Gumbel sampling offers a Pareto improvement: for every pair of distributions P, Q, Gumbel sampling achieves an equal or higher value of Pr[a = b] than Weighted MinHash. Importantly, this improvement translates to practice. We demonstrate an application of communication-free coupling to speculative decoding, a recent method for accelerating autoregressive large language models [Leviathan, Kalman, Matias, ICML 2023]. We show that communication-free protocols can be used to contruct emphCSD schemes, which have the desirable property that their output is fixed given a fixed random seed, regardless of what drafter is used for speculation. In experiments on a language generation task, Gumbel sampling outperforms Weighted MinHash. Code is available at https://github.com/majid-daliri/DISD.