List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression
Authors: Joseph Rowan
Buu Phan
Ashish J Khisti
Venue: NeurIPS 2025 poster ()
Keywords: probability
sampling
compression
speculative decoding
multi-draft speculative sampling
large language models
Primary area: probabilistic_methods
TL;DR: We introduce a technique for coupling probability distributions when several samples are available from one of the distributions, and give applications to multi-draft speculative decoding and distributed lossy compression with side information.

Abstract: We study a relaxation of the problem of coupling probability distributions — a list of samples is generated from one distribution and an *accept* is declared if any one of these samples is identical to the sample generated from the other distribution.
We propose a novel method for generating samples, which extends the Gumbel-max sampling suggested in Daliri et al. (2025) for coupling probability distributions. We also establish a corresponding lower bound on the acceptance probability, which we call the *list matching lemma*.
We next discuss two applications of our setup.
First, we develop a new mechanism for multi-draft speculative sampling that is simple to implement and achieves performance competitive with baselines such as SpecTr and SpecInfer across a range of language tasks.
Our method also guarantees a certain degree of *drafter invariance* with respect to the output tokens which is not supported by existing schemes.
We also provide a theoretical lower bound on the token level acceptance probability.
As our second application, we consider distributed lossy compression with side information in a setting where a source sample is compressed and available to multiple decoders, each with independent side information.
We propose a compression technique that is based on our generalization of Gumbel-max sampling and show that it provides significant gains in experiments involving synthetic Gaussian sources and the MNIST image dataset.

List-Level Distribution Coupling with A Applications to Speculative Decoding and Lossy Compression
Joseph Rowan
Buu Phan'
Ashish Khisti!
University of Toronto
(joseph. rowan, truong phan Maain wtoooottooooooooooooo ca, akhisti@ece www.:eece..urroooocoom
Abstract
We study a relaxation of the problem of coupling probability distributions - list of samples is generated from one distribution and an accept declared if any one of these samples is identical to the sample generated from the other distribution. We propose a novel method for generating samples, which extends the Gumbel- max sampling suggested in Daliri et al. [9] for coupling probability distributions. We also establish a corresponding lower bound on acceptance probability, which we call the list matching lemma. We next discuss two applications of our setup. First, we develop new mechanism for multi-draft speculative sampling that is simple to implement and achieves performance competitive with baselines such as SpecTrr [38] and SpecInfer [34] across a range of language tasks. Our method also guarantees certain degree of drafter invariance with respect to the output tokens which is not supported by existing schemes. We also provide a theoretical lower bound on the token level acceptance probability. As our second application, we consider distributed lossy compression with side information in a setting where source sample is compressed and available to multiple decoders, each with independent side information. We propose a compression technique that is based provides significant gains in experiments involving synthetic Gaussian sources and the MNIST image dataset.
generalization of Gumbel-max sampling and show that it
Introduction
Coordinated sampling, where samples are drawn from two distributions in such a way that the probability of the samples being equal is maximized, is fundamental problem probability [17, 18, 37, 40] with applications to machine learning [9, 25, 38], data compression [12, 39] and information theory [8, 26). The general problem who wish to generate samples X and Y from distributions px and qy respectively. For now, we limit our attention to the case where px and qy are discrete; importance sampling will later allow us to extend the discussion to approximate sampling from continuous distributions well. A first goal is to construct a scheme that Alice and Bob can follow to maximize the matching or acceptance probability Pr[X- Y] while ensuring each sample follows the appropriate marginal distribution. If they both have access to px and (j, the problem reduces to that finding the best joint distribution for X and Y subject to the marginal constraints, which is called maximal coupling between px and qy [40]. For discrete distributions, such an coupling can be found and the resulting optimal matching probability is Pr[X- Y] = drv qy where drv is the total variation distance [17,37, 37, 40].
follows. Consider two parties, Alice and Bob,
However, the requirement that both parties can access Px and qy precludes the use of maximal couplings in many settings where it is desirable to limit communication between Alice and Bob, meaning each can no longer sample with full knowledge of the other's distribution. Sampling methods based on common randomness offer convenient solution, and have been shown to achieve matching probabilities close to that of the maximal coupling despite their relative simplicity [9]. particular,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

if Alice and Bob both sample from px and qy by applying the Gumbel-max trick to shared random
numbers, is possible to achieve Pr[X- Y 2 (1 drv (Px. (rv(Px.9r)))/( (111---40 + (Px (Px.gy)), which is a lower bound in the communication-free setting [2. 9].
In this paper, we interested in extension of the communication-fies coupling problem where one of the parties, say Alice, generates K' independent samples from px. Letting the set of Alice's samples be
the new matching probability is taken to be Pr[Y E (x(1). x(K)) H]; intuitively, Alice's 's output is said match Bob's if at least one sample agrees. However, it is not immediately obvious how Y and x ................................ ((K) should be sampled in this new setting if we wish to maximize the matching probability. As solution, we introduce a simple algorithm that we call Gumbel-max list sampling (GLS) to generate coupled samples, together with corresponding lower bound on the acceptance probability. On the practical side, we apply GLS to derive a new algorithm for multi-drafi speculative decoding [34, 38), popular technique for accelerating inference from large language models (LLMs). Later, we also demonstrate an application to distributed lossy compression when independent side information is available at each of K separate decoders, extending the classical formulation of Wyner and Ziv [45]. In summary, our contributions are:
1. We present GLS as a conceptually simple framework for coordinated sampling from discrete distributions when one party produces multiple proposals, extending the proposal Gumbel-max coupling technique in Daliri et al. [9], and establish a theoretical lower bound on the matching probability.
2. Based on GLS, we describe a novel multi-draft speculative decoding scheme. Our scheme differs from prior approaches [34, 38], as it does not involve rejection sampling and satisfies a certain notion of drafter invariance with respect to the output tokens, for which we give formal definition.
3. We use GLS to devise compression technique for distributed lossy source coding where sample is compressed and sent simultaneously to several decoders, each having access to independent side information. We conduct experiments and show improved rate-distortion performance on Gaussian sources and the MNIST image dataset.
2 Related work
Couplings and coordinated sampling. From theoretical perspective, couplings between proba- bility distributions have been used to prove results in probability theory. including limit theorems, convergence results and various inequalities [17, 18, 40]. A reference on these mathematical tech- niques can be found in Thorisson [40], including algorithms for constructing maximal couplings and their relationship to the total variation distance. More relevant to this paper are techniques that create couplings via common random numbers, which can be applied in very general contexts [13, 14). In particular, applications to categorical distributions have been studied under the name of weighted coordinate sampling [2, 33]. Recently, Daliri et al. [9] demonstrated how Gumbel-mat sampling can be used to generate such couplings and simultaneously introduced the idea of drafter-invariant speculative decoding, though their results and theory were limited to the single-draft case. Part of our contribution is an extension of their work to settings with multiple proposals.
Lossy source coding via channel simulation. Lossy compression schemes based on channel simu- lation rely on similar probabilistic tools to those examined in this paper. While perfect reconstruction can be achieved with an unbounded number of samples, as established by Li and El Gamal [27] through the Poisson functional representation lemma (PFRL), practical methods often resort to importance sampling to communicate approximate samples from continuous distributions [15, 39]. Extending this to the classical problem of source coding with side information at the decoder as posed by Wyner and Ziv [45], Li and Anantharam [26] introduced the Poisson matching lemma (PML), which they used to prove one-shot version of the Wyner-Ziv theorem along with non non- asymptotic variants of other standard results from information theory. However, the PML construction still requires access to infinite number of samples. Phan et al. [36] adapted the PML to practical settings through importance sampling at the cost of allowing a bounded error probability, introducing framework called the importance matching lemma (IML). We use GLS to derive extension where there are several independent decoders with independent side information.
Speculative decoding. Speculative decoding, concurrently introduced by Leviathan et al. [25] and Chen et al. [5], is a popular technique for accelerating inference from LLMs. The main idea is to

---

use small draft model to parallelize autoregressive decoding from larger target model, adopting traff-then--erify approach. uollow-up works have focused on aligning the drafter more closely with the target [32, 49], decreasing the cost of running the draft model [4, 28] or optimizing the length of speculative generation [31]. Most pertinent our work are multi-draft extensions of speculative decoding where several draft tokens are selected as candidates for verification to increase the expected number of accepted tokens [20]. While maximal couplings are generally used for single- draft methods, they prove intractable in the multi-draft case, where methods based on heuristics or approximations of optimal transport are often used instead [34, 38J. Directly relevant to our contribution is the single-draff drafter-invariant speculative decoding technique recently proposed by Daliri et al. (9), which demonstrates a scheme based on common random numbers instead of rejection sampling. Our work extends this idea to the multi-draft setting.
3 Gumbel-man List Sampling
Recalling the setup from section 1, where Bob samples Y from and Alice samples x ..... (K) from px without communication, how should these samples be generated to maximize the acceptance probability? As motivating example, take K = 2 and let the support of px and qy be (1,2). 2). Using the Gumbel-man max approach from Daliri et al. [9], we could start by choosing shared i.i.d. random numbers $1, S2 ~ Exp(1) ) and sampling
{ 4r (1) 9r (2)
S
S₂ } and ( arg min {
S
S2
Y arg min
(I)
(1 px (2)
which would ensure that Pr( = YJ (1 drv (r))))(()1/)) + drv(px, QY)) [9]. But, how should we choose x Unfortunately, if we use Si and S2 again to sample X(2,, we would always get (1) (2) Hence, the matching probability would not increase with the number of samples from Alice. An alternative is to create independent random numbers S3, S4 ~ Exp(1) and take
S3
S4
(²) arg min
(1 px (2)
This does increase the acceptance probability, but there now no coupling between (2) and Y. As result ([x(2) Y] in general can be very small and we cannot expect large gain compared to when Alice only generates (1), The key idea of our GLS algorithm is instead couple ( and (2) with Y simultaneously using a minimum operation over the shared exponential random variables. More precisely, we choose
{ minn(S, min (S),S4) 4y (1)
= arg min
4y (2)
while (1) and (2) sampled in (1) and (2). Intuitively, our approach coordinates (1) and x²) symmetrically with Bob's choice of Y, increasing the probability that at least one matches. We now describe GLS for arbitrary N and K and provide a lower bound on the acceptance probability.
We assume without loss of generality that px and qy are both on the alphabet Ω {1..... NN.. In what follows we will call px the proposal or draft distribution and gy the target distribution; to simplify the notation we define = px(() (i) and qi = qy (f). Further let ((S(A)) 1.v } be K sets of N i.i.d. random variables, with S Exp(1) for all and k. In practice, we can easily generate the s(()ss given source of uniform random numbers by taking S(*) = In u7(h) where each 0,(k) Uni 1). The GLS procedure as follows, and also summarized in algorithm 1.
1. Select Y arg min gigN minigAgK 1(() /qs to generate sample from ςy
2. Select (k) arg minigeen ((()) /p., k I,...,,, K, generate i..d, samples from px-
The acceptance probability is Pr|Y E (X ,.... ( X()) Before stating our main theorem, which will give lower bound on this quantity, the following proposition is needed to establish that GLS returns valid samples from and gy. The proof can be found in appendix A.I.
3

---

Algorithm Gumbel-max List Sampling
1: function SAMPLEGLS(px. Qy)
2: Choose i..d. uniform random variables ((U -
on [0. /i=1de=1
3: < arg min minigagx U. /ql
4: ((k) + arg min s- woowwwwnnt U /pi), 1 < & < K
5: i E (x() , x then return accept else return reject
Proposition 1. The procedure described above (GLS) generates samples such that:
Pr(X(() (8) = j] = Pj for all k E {I....,KK and {1,...,,
2. Pr(Y = = (6 for all j (1....,N..
With these preliminaries out of the way, we can state our lower bound, which we call the list matching lemma (LML). Again, the proof deferred to appendix A.2.
Theorem (List matching lemma). The matching probability is bounded below
K
Pr[Y (X x(KI))
(3)
j=l Zi=1 (max((///))) pc/p3} + (K 1)4./a3)
N
Furthermore, conditioned on Y = we have
Pr[Y (X(1) x(K) 1 =
4
Kp;
Remark 1. The bound in Equation (3) recovers the exact matching probability in three important cases, namely for degenerate distributions where px has all its mass on one element, when K = 1 for any pair of distributions, and when px and qy are identical. These special cases considered further and proven in appendix A.7.
Theorem can be seen as direct extension to the discrete case of the PML in and Anantharam [26, Lemma on p. 3] and is in fact identical when there is single proposal. Li and Anantharam did not however consider any precise counterpart to theorem 1, though they did discuss a different list decoding setting with multiple samples from decoder [26, Remark 10 p. 10]. From (4), that, for any j such that 9j > 0 and > O, the matching probability achieved by GLS approaches for large K. Moreover, an analog proposition 1 holds if instead sample independently from ,,..,,,,''
K potentially different draft distributions ,......> ,,, cumbersome, the formal statement and proof of this extension are relegated appendix A.3.
(K) Since the notation becomes somewhat
Application to drafter-invarian multi-draft speculative decoding
Using GL.S sample from the output distribution of an LLM suggests simple but novel algorithm for drafter-invariant multi-draft speculative decoding, analogous to the single-draft procedure from Daliri al. [9], which uses standard Gumbel-max sampling. In this section, we review the mathematical formulation of multi-draft speculative decoding, define what exactly we mean by drafter invariance and present our new algorithm along with lower bound on the token acceptance probability.
4.1 Problem setup and drafter invariance
Let M& and ( be the target and draft LLMs respectively, where 1 5 < K. Mb and ! take the form of conditional distributions M& æ1:e) and M!!
(k) æ14), which give the probability of a token appearing at position + 1 given the context Tia == (I1,..., Iz). For convenience, we will refer the context and assume the alphabet Q = [I,...,N]] In multi-draft speculative
decoding [34, 38), K independent drafts of length L, which we denote x- 1:1 _ x(() are generated using either batching or tree attention [34] from !! . (..,, and then verified in parallel by the target model. In practice, the draft tokens are often i.i.d. and only single draft model M, is used [38]. If at least one of the K candidate tokens accepted each step, first such token
(1)
appended to the output sequence. If all are rejected, the verification procedure stops and extra

---

token is sampled from an appropriately chosen residual distribution. The final output sequence is Yi:r. where 7 is the number of accepted tokens plus one.
We propose the following notion of drafter invariance, which we later show empirically can be accommodated without decreasing the inference speed. Intuitively, our notion requires that given set of draft sequences must always induce the same output distribution regardless of the draft models that generated them. To state this condition formally, write X = XI.L (M!!)) ) in what follows to show the dependence between each draft sequence and the language model that produced it. In appendix B, further connect our notion to one introduced in Daliri et al. [9] for single-draft speculative decoding only.
Definition (Conditional drafter invariance). A multi-draft speculative decoding algorithm is condi- tionally drafter invariant if, for all S S
Pr[Mi. = yn R, c, (M.) = (1)
Tib (1a((K())) = =v1_1]
[K)
= PP((Y = Visj RR c, XIL(M = (1) Ii.L...... (.. = =x
(K)
for any choice of language models M M M!!) and M ,..., M...,.!!!)
In the following section, we will present conditionally drafter-invariant speculative decoding algorithm based on GLS. Existing schemes, including SpecTTr [38] and SpecInfer [34], do not satisfy conditional drafter invariance since their token verification procedures depend explicitly the draft model's s logits. Consequently, modifications affecting the draft model will propagate to the output even if the draft tokens themselves remain unchanged.
4.2 An algorithm for drafter-invarinn multi-draft speculative decoding
Our approach involves coupled sampling from the draft and target models via GLS. Supposing wish to use K i..dd drafts from a single model M,, at each decoding step we use the proposal distribution px = (. c) and the target distribution qy MM c), then draw coupled samples according to algorithm 1. This procedure is detailed in algorithm 2, which also keeps track of the set of currently viable drafts and accounts for the fact that, in practical speculative decoding implementations, all the draft tokens must be generated autoregressively ahead of time.
The results developed in section 3 allow us to state some important properties of our method. Using the LML directly with the proposal and target distributions as above immediately gives the following lower bound on the token-level acceptance probability.
Proposition 2. Let Ma( c) be px and Ma(- c) be qy. Then, the probability of accepting at least one token at the current step with K active drafts and context e satisfies
K
Pr[accept]
[mxx((// p.p,,
+ (K 1)q:/911
Moreover, proposition leads to guarantee of sequence-level correctness, such that the distribution over all sequences of output tokens matches that of autoregressive inference from the target model. We can also show conditional drafter invariance. Proofs can be found in appendix A.4.
Proposition 3. For any given T and for all 1 j t, the output of algorithm 2 satisfies Pr(Y1:; = yıd) Mo(wig e). Also, algorithm 2 is conditionally drafter invariant in the sense of definition 1.
4.3 Experiments
LLM inference with i.i.d. drafts. Our first experiment evaluates our drafter-invariant multi-draft scheme in a typical LLM inference setting with i.i.d. draws from one draft model. The target model Qwen 2.5-7 B [47] and, following Leviathan et al. [25], we use a smaller model from the same series, Qwen 2.5-0.5 B, as the drafter. To measure performance across a range of language tasks, prompts are executed from the GSMSK [7], HvmanEval [6] and NaturalReasoning [48] datasets. All experiments are run on single Nvidia RTX6000 Ada GPU with 48 GB of memory. Results are summarized in table 1, where we show the number of accepted tokens for each call to the large model, which is referred to as the block efficiency (BE), along with the percentage speedup in token
5

---

GSM8K
HvaanEval
NaturalReasoning
Strategy
BE
TR (%)
BE
TR (%)
BE
TR (%)
SpecInfer [34]
0.00
4.56 0.20
4.54 0.01
7.89 1 0.85
4.19 - 0.01
12.49 1: 0.56
SpecTr [38]
4.78 0.00
1.15
4.56 0.01
7.09 1 0.77
4.22 1 0.01
12.89 0.96
Our scheme
4.00
+.23
4.55 0.01
8.03
+ 0.97
4.18=0000
12.75 + 1.14
Daliri et al. [9]
4.16
0.63 = 0.24
3.69 + 0.01
0.04 0.30
3.32 = 0.00
-2.23 + 0.29
Table 1: L.M inference with i.i.d. drafts; we use I, = and = for the multi-draft methods. Token rates (TR) are shown as percentage speedups relative to single-draft speculative decoding, which has mean block efficiency (BE) 4.18, 3.75 and 3.43 on GSM8K, HumanEval and NaturalReasoning respectively.
rate (TR) relative to single-draft speculative decoding [25]. Further experimental results and details provided in appendix D.I. Our method's token-rate performance matches that of SpecInfer [34] and SpecTrr [38] within one standard error of the mean across all cases, even though these schemes do not offer drafter invariance, and exceeds that of the single-draft invariant scheme in Daliri et al. [9]. Our observations agree with recent results in Khisti et al. [20] showing that existing multi-draft algorithms perform almost equally well when i.i.d. drafts are used.
Guidelines on the choice of K. The choice of K in practical speculative decoding applications presents crucial tradeofT. While increasing K boosts the acceptance probability in line with proposition 2, requires more computation to generate and verify the additional drafts, especially when large models are used. Adding more drafts offers performance gains so long as these operations can be done in parallel, yet there comes a point when available resources become oversubscribed and slowdowns ensue if K is made too large. Furthermore, memory requirements scale linearly with K, VRAM capacity can be become limiting factor, all the more so when KV caching is enabled. We find that increasing K up to 6 and in many cases 8 gives consistent wall-clock speedups, consistent with previous work on multi-draft speculative decoding [19, 34, 38]; concrete measurements for different values of K may be found in appendix D.1.
LLM inference with diverse drafts. Our second experiment examines more challenging scenario where several different drafters are used, each misaligned with the target. Using a collection of draft models, each exhibiting some degree of diversity during the training process, can naturally lead to improved efficiency. For example, training or fine-tuning the draft models on different tasks may alleviate the challenge of finding a single general-purpose. fast drafter. In our present paper we introduce diversity across different models well as potential misalignment with the target model by varying the sampling temperature.
Specifically, we focus on experiments with K = 2 drafts where the temperature of each drafter is changed independently and mismatched the target, which itself has temperature 2.0. SpecTTr verification can no longer be used because it is specialized to identically distributed proposals; comparisons to SpecInfer, which is the dominant verification strategy in concurrent empirical work [28, 29], remain possible. As shown in table 2, our method outperforms SpecInfer with respect to token rates on GSM8K [7], HumanEval [6] and MBPP [1] in the mismatched draft setting, Moreover,
Algorithm 2 Drafter-invarian multi-draft speculative decoding
Choose + sets i.i.d. uniform random variables ((U(())) N p where 1 1SJS SJSLL I
2: for j 1,.., do
3: for k = I,... K do in parallel
4:
(g.R) < M. (:1 (4)
1)) c). x <- arg min, min In ((bi)) /p((.d)
5: for j -, and
I,... do parallel
6:
(h +- Mo( (x)
7: Let the set
of of for l..j=,..,,1 do
active drafts be S (L....,K.. K}.
8:
9:
Y, arg min ming minces| ((1 (g6..))
for E S do
11:
x * Y, then S S S {b}
12: I = then return Yi....,,
13:
YL+1 + arg min SiSN minkes| -nn--nn1 U. 1.)) / (2+1,))
14: return Yi...., 4

---

GSMSK
HvmanEval
MBPP
Strategy
Tmp. 1/2
BE
TR (%)
BE
TR (%)
BE
TR (%)
SpecInfer
0.5/1.0
4.26 + 0.02
0.06 1.02
3.57 1 0.02
-1.6 1 0.67 3.66 - 0.01
1.87 = 0.79
[34]
1.0/0.5
1.4410.00 0.03
4.57 1.80
3.80
4.13 1.60
3.90 0.02
4.77 = 0.55
1.0/1.0
4.51 0.02
6.02
3.87 0.02
6.32
3.95 0.02
5.17 = 1.13
Our
0.5/1.0
4.75 1: 0.02
11.50 +: 1.78
4.00
4.01
3.94 + 0.02
5.64 = 0.66
scheme
4.75 1.0/0.5
0.02
11.40
1.58
3.96 + 0.02
3.77
3.96 # 0.02
5.99 = 1.01
1.011.0
4.83 + 0.02
13.68 = 1.67
4.08 0.02
12.15
4.08 = 0.01
8.57 = 0.60
Table 2: LLM inference with diverse drafts; we use L = 5, K = 2 and the target temperature is 2.0. The temperatures of drafters and 2 vary and are reported in the second column. Token rates (TR) are shown as percentage speedups relative to single-draft speculative decoding with drafter temperature 1.0, which has mean block efficiency (BE) 1. 1.28, 3.65 and 3.71 on GSM8K, HvmanEval and MBPP respectively.
our scheme is less sensitive to the order in which the drafts appear, whereas SpecInfer's recursive rejection scheme [34] favors coupling with the first proposal - comparing the first and second rows of table 2. SpecInfer often exhibits slower token rates than single-draft speculative decoding when the first drafter's temperature deviates the most from the target in the 0.5/ 1.0 configuration, yet this weakness disappears when the drafts' order is swapped. Again, additional experimental results can be found in appendix D.I.
4.4 Limitations
While our GLS-based speculative decoding algorithm presented in algorithm 2 mostly functions as a drop-in replacement for standard speculative decoding [25], care must be taken when the vocabulary size large. As in other multi-draft algorithms [34, 38), memory requirements store the draft and target logits for each step scale as O(N (), while we also need to generate a similarly large quantity of shared random numbers and compute the arg min across these sets. practice, enabling top-K sampling significantly reduces this burden by allowing us to throw away all but M < N high preebbbbbbbblitty tokens. Our experiments use the full Qwen 2.5 set of 151 936 possible tokens, demonstrating that large vocabularies are well-handled by GLS in a real-world inference setting. On the other hand, speculative decoding may fail to enhance performance with poorly aligned draft model or extreme temperature mismatch; our approach can benefit from the proliferation of complementary techniques that encourage better draft-target alignment to obtain more robust performance [46, 49].
5 Application to lossy compression with side information
We now present an application of GLS to a distributed lossy compression problem with one encoder and K decoders, where each has access to independent side information, thereby extending the compression technique presented in Phan al. [36] to list decoding setting. Our setup is distinct from a more common multi-decoder extension of Wyner-Ziv coding where the decoders access side information with different levels of statistical correlation with the source, and are required to produce reconstructions of varying fidelity [41]. In contrast we allow multiple chances to decode the compressed source representation using independent side information samples, related to list decoding approaches in information theory [11]. We are motivated by practical scenarios where shared data is compressed and sent to each decoder for later use in a downstream task, and overall success is predicated on at least one decoder completing the task correctly. Conceptually, this mirrors the metmerrersshp definition of matching probability used in thcorem
As concrete example, consider a decentralized vision-based aircraft detection system where a base station captures a large-scale image of the sky, while several remote sub-stations obtain images with narrower field of view from particular locations. After compressed representation of the base station's 's image is broadcast, each sub-station uses its private image as side information to reconstruct the global view, then uses this reconstruction along with the local image as input to detection algorithm. The system as a whole is declared successful at least one sub-station detects the aircraft overhead, reflecting the standard notion of detection probability in distributed detection theory [42]. In this paper, we limit our discussion to the intermediate reconstruction error, leaving the mechanics of any downstream detection to future work as these will depend on the specifics of the application.
7

---

Encoder
Decoders
Reconstruction
Pwia( a)
8
Pwir( (6)
Source
+
(x)
[1S:
Pwiz [xx)
(()
A
Shared randomness
1 AK
Pria
o)
Side information
Figure I: Problem setting for lossy compression with side information at the decoder.
5.1 Problem setup and coding scheme
Figure 1 gives an overview of our coding scheme. The encoder observes realization of A ~ from the source, which should be broadcast identically to K decoders at a rate of R bits per sample via message M. Decoder k, where 1 S k S. K, further observes the side information T3- ~ Pr14 and combines this with the message sent by the encoder to produce an output Wi that aims follow the conditional distribution PW24 and marginal pw. The Tę 's are taken to be i.i.d. and PwIa is usually
chosen satisfy an expected distortion constraint E(d( A),, where is a distortion metric and Á is the final reconstruction, calculated as = 9WW for some decoding function g. We limit our attention here to discrete probability distributions, although further show in appendix C how our scheme can be extended to continuous distributions through importance sampling.
Following Phan et al. [36], we let PWIT be the conditional distribution of W given the side information
T, which can readily be calculated as Pw]r(W t) = La' (w] a d')P [t). Assuming
W E [1, [1,...,N}, .N. we generate N uniform integers 21,...,f, EN i.i.d. on (1.-.., Immax ). where Lzmax positive integer. We define the random tuple B = (W, E) distributed according to pn(w, E) = Pw (w)/Tmg Tmmx and the associated samples B; = (i, ()) for 1 S i I N, thereby covering the full sample space of W. Using the procedure described in section
also let ((5{ 1. K be K sets of N i.i.d. Exp(1) random variables. To sample from PBIA+ given that A = a is observed, the encoder selects index Y given by
S(()
S(O))
Y = arg min min
arg min min ISiEN ISKSK Pwja(i a)
ISIEN ISASK K (B; a)
Supposing Y = j. the encoder transmits the message M = l so that decoder is has access to the tuple 7, = (Tk, The rate is therefore R log T.max bits, as this is the bit-width of M. The target distribution used by each decoder is taken to be PB) l |t, .g) Pwir(w t) Eÿ}.
Finally, given Tr Lz. decoder ls selects the index (() according
S(()
S( 1315N Pwir(i 1x) = E₁}
(k) (k) arg min
ISIEN (B, tR) = arg min
5.2 Bound on the error probability
To apply GLS in the compression setting, our analysis must include the source, side information and message sent by the encoder. We therefore start by outlining a modified GLS procedure that allows the encoder to condition its output the source A, while the decoder's output is conditioned on a set of related random variables Z = { [ K As in section 3, we consider discrete marginal assume they are related by arbitrary conditional
distributions px and qy on Ω {1, ..... N). but
distributions AY PzIYA and pxiz- The common randomness ((s("))) ) KK is as before. We
also define dj (a) = ( (i a) and py (=) = (x z). The new sampling strategy is as follows:
1. Upon observing A a, the encoder selects arg min minigAsK s(a)) (q)(a) to generate sample from qy JA-
2. Given Y j. we sample Zi...., Zk i.i.d. according to ( j.a).
3. Given Z₃ z4. decoder lt selects (k) arg min sieN S(M¹) /pi(zx).
8

---

1,05
-00
2.C.
Molchig poschnggeeuae poNaNii
yeltubilts
peblabiity
Dideetion eeeeetin (1l))
0.5
21.
0.2
0.2
0.2
(bis)
(bis)
(H00
(b)
(d)
Figure 2: Experiments on a Gaussian source. (a)-c): Matching probability, from left to right: GLS without side information, GLS with side information, baseline with side information. The baseline does not benefit from multiple decoders without side information. (d): Rate-distortion curves for GLS and baseline (BL) schemes.
We also derive corresponding extension of the LML to bound the matching probability of the conditional GLS scheme. Intuitively. while the LML in theorem 1 deals with the case where no communication is permitted, here control the amount of communication by choosing PZIY, Theorem 2 (Conditional LML). Using the strategy above, the error probability satisfies
g5(a) Ps(2k)
Pr|Y E (X(), ..... x(K) | A a, z 1
K
Theorem 2 follows from the LML by realizing that (( 1im }
(Y, - z forms Markov chain, and therefore the Z are conditionally independent of the shared randomness given Y and A. The full proof is given in appendix A.5. Using theorem 2, now have the following bound on the error probability of our coding scheme. The proof can be found in appendix A.6.
Proposition 4. For the coding scheme in section 5.1, the error probability is bounded above as
x(K) S EA,,W [1+ 2:(W:AI2)
-1
Pr|y & (X(1)
(5)
K Lymax
where iw, (w; a log(Pwia(10 a a)/Pw ()) is the conditional information density.
Synthetic Gaussian source. As a canonical example, we consider a Gaussian source NN 1). The side information is T. = A Sk. where Ca (O, 77 and o A 0.5. The encoder's target distribution follows (w a) = (a ((a,ow1a) owja). with oW interpreted as the distortion permitted by the compression scheme. Note that since the target distribution is now continuous, it is not possible achieve perfect reconstruction with finite number of samples. However, can get arbitrarily close by using importance sampling and then applying GLS to an empirical distribution defined by the importance weights, detailed in appendix C. Moreover, a closed form for the decoder's target distribution Pwir exists in the Gaussian case, and turns out to be Pw (r(- t) = (t//o,,, ow 1//0?.) Concerning the reconstruction function g. decoder k forms the minimum mean squared error (MMSE) estimate of A given T' and Wi. and we then choose the estimate with the least distortion among all decoders. The target distribution and MMSE estimator are both derived in appendix D.3, along with other experimental details.
Figure 2 illustrates how the matching probability increases in both the rate and the number of decoders, while the observed distortion decreases. We also show comparisons to a baseline scheme where all decoders share the same set of random numbers; we are not aware of any other competitive baseline for the list decoding setting considered here. GLS-based decoding improves substantially over the baseline when K > particularly low rates, the probability of matching with the encoder least once is increased. For K = 1. both methods are equivalent to the singlc-decoder technique described in Phan al. [36. p. 6].
Lossy compression on MNIST. We now apply our technique to distributed image compression [35, 43] using the MNIST dataset [24]. In our experiments. the right half of each image is the source while the side information is a randomly selected 7 crop from the left half. We adopt a neural compression technique similar to that in Phan et al. [36] using a 3-variational autoencoder

---

Source
3
K =2 GLS
K GLS K 1 BL
BL
K GLS
3. BL
0.08
K - GLS
K 4. BL
Ehender output
3
4
MSB
0.08
Decoder output
7
0.07
Correct decoding
Decoding eIror
Incorrect encoding
3.5
5.5
Rate (bits)
Figure 3: Examples showing success and failure modes of our compression scheme on MNIST.
Figure 4: Rate-distortion curves on MNIST for GLS and baseline (BL) schemes.
(3-VAE) [16]. Details of our setup are given in appendix D.4, where we also describe how the 3-VAE architecture fits into our coding scheme laid out in section 5.1.
Figure shows some representative examples from our image compression pipeline. Errors may occur at the encoder, decoder both; cases where the encoder's s output correct but the decoder's is not are caused by error events of the type dealt with in (5). Our scheme's 's rate-distortion performance improves with the number of decoders as shown in figure 4; comparisons to the same baseline used in the previous experiment, with only one set of random numbers, demonstrate consistent improvements particularly at lower rates.
5.3 Limitations
Unlike speculative decoding applications, which most often operate in single-GPU homogeneous multi-GPU enviromments [4, 28]. lossy compression algorithms may conceivably see deployment in distributed systems and therefore must consider how communicate the shared randomness between the encoder and decoder. This is usually done by sharing or agreeing upon random seed before starting the compression procedure, the cost of which may be amortized across many transmissions [39]. Furthermore, our error probability analysis assumes that floating-pon point operations have the same deterministic behavior at both the encoder and decoder, which may be violated in practice. We emphasize that these limitations are not unique to GLS but rather applicable to methods based Gumbel-max sampling common randomness more generally, which benefit from numerous implementation techniques within the machine learning [22], compression [36, 39] and coordinated sampling [2, 8] literature.
Conclusion
We studied the problem of coupling probability distributions without communication when several samples are available from one of the distributions, and introduced the GL. algorithm draw coupled samples in this setting along with a lower bound on the resulting acceptance probability. These results were then used derive novel algorithms for drafter-invariant multi-draft speculative decoding and lossy compression with side information. Avenues for future work include applying GLS with importance sampling to generalize speculative decoding models with continuous sample spaces such as diffusion models [3]. Furthermore, an alternative relaxation of distribution coupling might allow both parties to generate list and declare an accept the intersection between the lists nonempty. Finding relevant practical applications as well as efficient sampling techniques for such generalization another interesting direction for further research. We have made the code for all our experiments available at https:/ http::////tttin //ggtttt...... com/ Multt wwwteeeeeaaattteeeatataaiieeeeee
7 Acknowledgements
We thank Hitachi Solutions funding the present research. Resources used preparing this research were moreover provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute (www. www.veeeoooisiittteeeeee partnerships/).
10

---

References
[1] J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, and C. Sutton. Program synthesis with large language models, 2021. URL https: //arxiv. http//bbs/118....
[2] M. Bavarian, B. Ghazi, E. Haramaty, P. Kamath, R. L. Rivest, and M. Sudan. Optimality of correlated sampling strategies. Theory of Computing, 16(12)11-18, 2020.
[3] V. D. Bortoli, A. Galashov, A. Gretton, and A. Doucet. Accelerated diffusion models via speculative sampling, In Proceedings of the 42"d International Conference Machine Learning. pages 22590-12631, 2025.
[4] Cai, Y. Li, Z. Geng, Peng. D. Lee, D. Chen, and T. Dao. Medusa: simple LLM inference acceleration framework with multiple decoding heads. In Proceedings of the 41 International Conference on Machine Learning, pages 5209-5235, 2024.
[5] C. Chen, S. Borgeaud, G. Irving, J.-B. Lespiau, L. Sifre, and J. Jumper. Accelerating large language model decoding with speculative sampling, 2023, URL attps://arrt org/abs/ 2302. 2302.01318.
[6] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, Tillet, F. P. Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. H. Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba. Evaluating large language models trained code, 2021. URL /ttps://arxiv org/ abs/2107. 22107.03374,
[7] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers to solve math word problems, 2021. URL http::::///xxv..r//aaassssee//
14168.
[8] P. Cuff. Communication requirements for generating correlated random variables. In 2008 IEEE International Symposium on Information Theory, pages 1393-1397, 2008.
[9] M. Daliri, C. Musco, and A. T. Suresh. Coupling without communication and drafter-invariant speculative decoding. IEEE International Symposium on Information Theory, 2025.
[10] D. Dua, Y. Wang, P. Dasigi, G. Stanovsky, S. Singh, and M. Gardner. DROP: reading comprehension benchmark requiring discrete reasoning over paragraphs. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics, pages 2368 2378, 2019.
[11] P. Elias. List decoding for noisy channels. Technical report, Research Laboratory of Electronics, Massachusetts Institute of Technology, 1957.
[12] G. Flamich, M. Havasi, and J. M. Hernández-Lobaie Compressing images by encoding their latent representations with relative entropy coding. In Advances in Neural Information Processing Systems, volume 33, pages 16131-16141, 2020.
[13] S. Gal, R. Y. Rubinstein, and A. Ziv. On the optimality and efficiency of common random numbers. Mathematics and Computers in Simulation, 26(6):502-51, 1984.
[14] P. Glasserman and D. D. Yao. Some guidelines and guarantees for common random numbers. Management Science, (88(6)8844-88 -08, 1992.
[15] M. Havasi, R. Peharz, and J. M. Hernández-Lobato. Minimal random code learning: getting bits back from compressed model parameters. In 7th International Conference on Learning Representations, 2019.
11

---

[16] I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Ler- chner. 3-VAE: learning basic visual concepts with constrained variational framework. In International Conference on Learning Representations, 2017.
[17] F. D. Hollander. Probability theory: the coupling method. Lecture notes, Leiden University, 2012. URL httpppss/mmaaaamaaaaaaaaaeee..ee hrtp/
in pdf.
[18) P. E. Jacob. Couplings and Monte Carlo. Lecture notes, Harvard University, 2020. URL
https://sites goog:// wttp://l...///e/eeeeeeeeeeeeeeee http////teeeppeeraaaaa////oallla
[19] W. Jeon, M. Gagrani, R. Goel, J. Park, M. Lee, and C. Lott. Recursive speculative decoding: accelerating L.M inference via sampling without replacement, 2024. URL attps://arxiyy org/abs/2402 14160.
[20] A. J. Khisti, M. R. Ebrahimi, H. Dbouk, A. Behboodi, R. Memisevic, and C. Louizos. Multi- draft speculative sampling: canonical decomposition and theoretical limits. In 13th International Conference Leurning Representations, 2025.
[21] D. P. Kingma and J. Ba. Adam: a method for stochastic optimization. In International Conference Learning Representations, 2015.
[22] W. Kool, H. V. Hoof, and M. Welling, Stochastic beams and where to find them: the Gumbel- top-k trick for sampling sequences without replacement. In Proceedings the Conference Machine Learning, pages -499-3508, 2019.
the 36 International
[23] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[24] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):222 86(11):2278-23244 1998.
[25] Y. Leviathan, M. Kalman, and Y. Matias. Fast inference from transformers via speculative decoding. In Proceedings of the 40th International Conference on Machine Learning, pages 19274-1999 19286, 2023.
[26] C. Li and V. Anantharam. A unified framework for one-shot achievability via the poisson matching lemma. In 2019 IEEE International Symposium Information Theory, pages 942-946, 2019.
[27] C. Li and A. El Gamal. Strong functional representation lemma and applications coding theorems. IEEE Transactions on Information Theory, 64(11)669776677, 2018.
[28] Y. Li, F. Wei, C. Zhang, and H. Zhang. EAGLE: speculative sampling requires rethinking feature uncertainty. In Proceedings of the 41 International Conference on Machine Learning, pages 28935-28948 2024.
[29] Y. Li, F. Wei, C. Zhang, and Zhang. EAGLE-2: Faster inference of language models with dynamic draft trees. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024.
[30] C.-Y. Lin. ROUGE: package for automatic evaluation of summaries". In Text Summarization Branches Out, pages 74-81, 2004.
[31] T. Liu, Y. Li, Q. Lv. K. Liu, Zhu, W. Hu, and X. Sun. PEARL: parallel speculative decoding with adaptive draft length. In 13th International Conference on Learning Representations, 2025.
[32] X. Liu, L. Hu, P. Bailis, A. Cheung, Z. Deng, I. Stoica, and H. Zhang. Online speculative decoding. In Proceedings of the 4 International Conference on Machine Learning, pages 31131-31146, 2024.
[33] M. Manasse, McSherry, and K. Talwar. Consistent weighted sampling. Technical Report USR-TR-2010-73 Microsoft Research, 2010.
12

---

[34] X. Miao, G. Oliaro. Z. Zhang, X. Cheng, Z. Wang, Z. Zhang, R. Y. Wong, A. Zhu, L. Yang. X. Shi, C. Shi, Z. Chen, D. Arfeen, R. Abhyankar, and Z. Jia. Specinfer: accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 932-9999209 332-949, 2024.
[35] N. Mital, E. Özyilkan, A. Garjani, and D. Gündüüz. Neural distributed image compression using common information. In 2022 Data Compression Conference, pages 182-191, 2022.
[36] B. Phan, A. Khisti, and C. Louizos. Importance matching lemma for lossy compression with side information. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, pages 1387-1395, 2024.
[37] S. Roch. Modern discrete probability: an essential toolkit. Cambridge University Press, 2024.
[38] Z. Sun, A. T. Suresh, J. H. Ro, A. Beirami, H. Jain, and F. Yu. SpecTTr: fast speculative decoding via optimal transport. In Advances in Neural Information Processing Systems, volume 36, pages 30222-30242, 2023.
[39] L. Theis and N. Y. Ahmed. Algorithms for the communication of samples. In Proceedings of the 39th International Conference on Machine Learning, pages 21308-21328, 2022.
[40] H. Thorisson. Coupling, stationarity, and regeneration. Springer, 2000.
[41] R. Timo, T. Chan, and A. Grant. Rate distortion with side-information many decoders. IEEE Transactions on Information Theory, 57(8):5240-52555 2011.
[42] R. Viswanathan and P. K. Varshney. Distributed detection with multiple sensors: part I fundamentals. Proceedings of the IEEE, 85(1):54-63, 1997. doi: 109/55955.55408.
[43] Whang, A. Nagle, Acharya, Kim, and A. G. Dimakis. Neural distributed source coding. IEFE Journal on Selected Areas in Information Theory, 5:493-508, 2024.
[44] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing: System Demonstrations, pages 38 45, 2020.
[45] A. D. Wyner and J. Ziv. The rate-distortion function for source coding with side information at the decoder. IEEE Transactions on Information Theory, 22(1):1-10, 1976.
[46] H. Xia, Z. Yang, Q. Dong, P. Wang, Li, T. Ge, T. Liu, W. Li, and Z. Sui. Unlocking efficiency in large language model inference: comprehensive survey of speculative decoding. In Findings of the Association for Computational Linguistics, pages 7655-7671, 2024.
[47] A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, Yang. J. Zhou, Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu. Qwen 2.5 technical report, 2025. URL https::t//// //t:://aaxxx org/ at//aabb/.2....////// 2412. 15115.
[48] W. Yuan, J. Yu, S. Jiang, K. Padthe, Y. Li, D. Wang, I. Kulikov, K. Cho, Y. Tian, J. E. Weston, and Li. NaturalReasoning: reasoning in the wild with 2.8M challenging questions, 2025. URL https: //axxiv. .rg/ abs/ 13124.
[49] Y. Zhou, K. Lyu, A. S. Rawat, A. K. Menon, A. Rostamizadeh, S. Kumar, J.-F. Kagy, and R. Agarwal. DietillSpec: improving speculative decoding via knowledge distillation. In 12 International Conference Learning Representations, 2024.
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
the abstract and introduction, we claim to introduce the GLS algorithm and give two applications, one to multi-draft speculative decoding and the other distributed lossy source coding. These are all included in the main paper along with the relevant proofs and experimental results to back up our claims involving formal guarantees and empirical performance.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mention limitations of our theoretical results, e.g. that GLS only allows for approximate sampling from continuous distributions. Also, key assumptions and possible failure cases are outlined in the experimental sections.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
14

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The theorems and propositions in the paper are all proven in the supplementary material. In the main paper, we attempt to provide mathematical intuition about the main results and highlight key ideas in the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
The methodology and parameters used for each experiment are clearly stated, and the algorithms we introduce can be reproduced from the pseudocode included in the main paper. Neural network architectures are also given for the MNIST image compression experiment.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code necessary reproduce the experimental results, along with instruc- tions for running each experiment, is provided as part of the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
Soggli//guiddes/odeeeubbbss
www.sssiiiiiiiiiooooooiooooiiccl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. pttppp/uguiudeesss/ppeppppp/ppep
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: In the supplementary material, we provide extensive details for all experiments in the paper. This includes the datasets used, number of trials, grid search parameters for our compression experiments and procedures used to train the neural networks involved in the proposed image compression scheme.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
16

---

Where appropriate, we report the standard emror of the mean for experimental results that support the claims made the paper, namely performance on speculative sampling tasks and the rate-distortion characteristics of our compression scheme. Guidelines:
Justification:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
While our experiments are not extremely computationally extensive, detail the GPU hardware configuration used in each experiment along with approximate runtimes.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://nente /ttee://eeee...eeeeee cc
Answer: [Yes]
Justification: We have reviewed the Code of Ethics and assert that the research have conducted conforms to the guidelines. We do not anticipate any ethical concerns arising from our research.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
17

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The main contributions of our paper are fundamental, and the applications discussed, i.c. speculative decoding and distributed lossy compression, are already well- established. Therefore, we do not anticipate any social impact from our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairesss considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not involve the creation of any data or models with risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
18

---

Answer: [Yes]
Justification: The datasets and models used in our research are all cited and used within their respective licensing requirements.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
19

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs not used as part of the research methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy (https / http::///euuiepeeeeeee http///urripps.ccoooeeeeeeesee /ttpc//oeeeeeecc///2//////////// for what should or should not be described.
20

---

Appendices
A Proofs
In this section we prove the results in the main paper. For clarity, each theorem is restated and then proof is given.
A.1 Proof of proposition
Proposition 1. The GLS procedure, as described in section 3, generates samples such that:
1. Pr(X = -] Pj for all k E (1....,K) and j NJ.
2. Pr(Y j| 4 for all j (I,...,NN.
Proof. Since the ( s are i.i.d., the X will be also and it therefore suffices to check the distribution of X (1), Note that
5(1)
(1)
x(1) =j
Vi
Dj
pi
S(2)
5
< min
Pt/Pj (#)
The left-hand side is an exponential random variable with parameter À = and the right-hand side is an independent exponential random variable with parameter À Eitz Pi/Pj. So,
(r(x
= = I+ I+E Eitg pi/Pj
Pj
as required. Next, we look at the distribution of Y. Define Sj = min 5/a) Then,
S
5
y=j =
<
Vi
93 4
5
5 < min
4
On the left-hand side, Sj is exponential random variable with parameter K. while the right-hand side is independent exponential random variable with parameter À K Eigs 4s/ 4//g- Finally,
K
Pr[Y =
K K K
its 4/
9j.
A.2 Proof of theorem
Theorem (List matching lemma). The matching probability is bounded below
N
K
Pr[Y e (X(1)
(3)
j=1 lmax(q./ pp/p. + (K - 1)q//g/
Furthermore, conditioned on Y = j. we have
-1
Pr(Y E (X(), (X())...,X(()))
V V== 51
1
qi Kp;
21

---

D Target Proposal
Target
Probability
91
P2
Probability
P1
92
Q1
Ø3
2
12
2
Q2
92
44
2
2
3
4
Index
Index
(a) Target and proposal distributions.
(b) Augmented target distribution.
Figure 5: Distributions used in the proof of theorem 1 in the case of K 2 and N 2.
Proof. To analyze the matching probability, we conceptualize the scheme slightly differently as follows. Instead of taking the minimum over 1 S k S K to obtain {S; Ji=1 like in the proof of proposition 1, we form flattened sequence of the s(A) by defining
(T)
NK i=1
(5
((1) ((()) ...,,
((2)
s(K)
We also introduce augmented target distribution qy the extended alphabet 5 fl...., KNJ defined by the probabilities
91
ON K
Q1
I
W1 (KN)
(6)
K
and corresponding output V. The setup is visualized in figure for the simplest case of = 2 and K 2. There, = 1 for example corresponds to either or y = 3. In general,
Y ==j= = y = j+ + (k- - 1)NV for some {I....,K}.
By symmetry of the construction,
N
Pr[Y E (X(1)
Σ
Pr|Y = j jE
x(x)
=
j=1
N
Σ
KPrl j, jE (x())
X(1
j=1
Σ
KPrl = X =]
j=1
Since the analysis will be the same for any j. we foeus finding the probability of the event
Ý 1 and (1)
=1
T
T
Ti
Ti
< min
and
<
min
91
25 q:
P1
2
P:
T2
TN
TN41
TKN
Ti S min
max ( (2//). P2/P1)
max qN / PNPPPPP /p1 4N+1//1
TKN /
The right-hand side is exponential random variable independent of the left-hand side. If its parameter is À then, taking into account the definition of the q 's,, we have
N
qi
Ps
1
max
i=1
2=
i=1
N
max
+ (K - 1)
q1 P1
91
22

---

Therefore, by the properties of independent exponential random variables,
Pr(Y = 1, x =1 1|
(8)
Ei= (max(a///// Pt/P11 + -K- 111
Combining with (7) establishes the bound in (3). We now turn our attention to (4) and find
Pr(Y J. E (x().
x x()) = Pr/Y j. (x((). (x(").... (x.,)_...".)))))
x
2 Kr - j, x = j]
by the same symmetry argument used to show (7). Since our choice of j = 1 in establishing (8) was arbitrary, we can apply that result for each j to get
K
Pr|y J. Y (x(1)
x(,))) 2
Σ i=
+ (K 1)0s/ad
Finally,
Pr|Y (x(1) x(K)) = 1 Pr\Y j. Y E aa .....
(a..,,((k)]] (k)) Pr(Y 5
K
Ei= |max 9/ q9 Pp/P,} } + (K 1)9
K
K 9, E max Pe/pp qt/4;}
2 K + 4//P3
-1
1 + qi Kpj
As an aside, we now easily find related relaxed version of (3) by means of the relationship
N
Pr|y E (X ,.... x = Σ
Pr(Y = Pr E (xx),....
x y= =
j=1
N
Lj
2
Zj
1 1
Kpj
j=1
since Pr(Y = .] Q3 by proposition 1.
A.3 Extension of proposition non-identically distributed proposals
We briefly consider the case where the proposals are drawn independently from K different dis- tributions. Let these distributions be px ,x. PX (K) and define P. (K) = Px (i) for convenience.
In this setting, (k) is sampled from the corresponding ((x) but the sampling procedure and the common randomness are otherwise identical to the setup in proposition 1, We then have the following extension of that result.
Proposition 5. The procedure described above generates samples such that:
(*) - = P3 (k) for all E (1...., K} and E [1,...,N).
2. Pr(Y = = 4 for all j [1,
Proof. The proof is very similar that of proposition 1. We start by checking the distribution of any (k) for 1 < k < K. Note that
S
(8)
S
(k)
( =
-
Vi
+
j
J3]
RR)
Pj
p
s(
((()
<
min
#
(P)
23

---

The left-hand side is an exponential random variable with parameter À = 1, and the right-hand side is an independent exponential random variable with parameter -iiij Pi (k) (8)
/Pj So.
(x] = 1 Eijs Pi (2) = /p, Pj
(k)
(8)'s at all. Because
as required. Next, note that the selection procedure for Y does not involve the P3 the introduction of these probabilities the only deviation from the setting of proposition 1, the correctness of Y's distribution follows immediately from that result.
A.4 Proof of proposition 3
Proposition 3. For any given T and for all 1 S the ouiput of algorithm 2 satisfies Pr[Y1:; = yndl Mo(gi:j c). Also, algorithm 2 is conditionally drafter invariant in the sense of definition 1.
Proof. We start by proving the first part of the proposition, which establishes sequence-level cor- rectness. For convenience and to connect the setup more easily to GLS, we first abstract the details p
of Gumbel-max sampling by defining sets of independent random variables {{S(5.A) } ) for
all < j S L, where s(iik) = In (((,))))) We then have that each s(5.k) ~ Exp(1). Further let Sj-1 be the set of viable candidate drafts immediately before sampling Y,. which allows us to keep track of changes to S in algorithm 2 during the proof. When the maximum draft length is L, we have E {1,.... L }} due the possibility of selecting an extra token if the full draft sequence is accepted. For any т, we need to verify the distribution of Y1. ....... Y,, which we do by induction. First, consider Y,. Before the first step, Sp- {l..... K), algorithm 2 makes the selection
Y1 arg min min S(1.))
s(1.k)
(1,8) arg min min ISiSN Iskgk Mo c)
ISiSN ISAŞK of
(1.k) = Moli | c) for all k. Then, The second equality follows because the algorithm assigns qi
Pr[M] = yı] = M1 c) for all y1 E Q, by proposition 1. Next, the rejection loop keeps only the drafts i satisfying x = Y1. Hence, x Yı for any h St.
Next we look at the distribution of Y2. Here, we get
5(2 Y22 arg min min (2,4] ISiNN kEs, g;
S(2.k)
arg min min ISISN kES, Mo x x
However, from the previous step know that x(() Y2 for any le E S1. Therefore, Pr[Y2 1/2 Y = y1] = Mo yn, c) by proposition and consequently
Pr[Yi.2 = vı.2] = Ma yı, Ma(M c) = Mo(yn e).
Moreover, if L > the subsequent rejection stage removes from the set of viable candidates any draft not satisfying x* = Y,, and so S₂ = (k ((() = Yi, x Y2) (k x 1:2
Vi:2)-
In general, assume that Pr[yi.j nو = Ma c) and x Yısj for all k E Sj. for some 1 < j < r. Implicitly, j < L + 1, otherwise the generation would have already been completed. The next token is selected according
S(i+1.8)
S(++1A)
S S(1+1,))
Yj+1 arg min min [J+1,8)
arg min min
arg min min ISSN kES, Mu(i Y.g..)
ISiSN kES, q,
I2iSN kES, Ms(i X c)
and hence, Pr[Y,+1 = 1i+1 Vı = Mo(yst Vigi c). Also,
Pr[M1,5+1> = MI:6+1) = Mo(y++1 Mob(cn) c) = MM((1.(44) e).
j < L, the rejection step enures that
S Synk
(k) X
J+1 Y {k]
(k) [x1
YLg X Y2+1 11 1 Yı.
24

---

On the other had, j = L, the entire sequence up to T is now complete because S L + 1, and there are no more sampling or rejection steps. This concludes the inductive step which, along with the case for j = 1, makes up the proof for any S j S т.
We next prove our claim of conditional drafter invariance. The randomness is encapsulated by R = (( J.V 1K Above, as an intermediate step to proving sequence-lever correctness, we showed by induction that for any 0 S j < T, any k in S satisfies x Yi.j- Then, looking the selection of f++1, we have
+ arg min min S(
S
s(1+1A)
arg min min ISiSN kES, Mo(i x (R) 1:f. c)
arg min min ISiSN kes, My Yi.j.
(++..)) ISiSN kES, %
as seen previously, From this, given R, and Yı., 41+ only depends on the draft sequences through Sy. Starting from Y1, we see that since So = fl....,K K},
S(LA)
Y1 arg arg min min IsigN IskeK Mo(i c)
As the draft tokens do not play any role in this expression, we get
Pr[Vi R, (x ( 1:Lk-= = (he ( = Pr[yi = R, cl
which proves drafter invariance for Yi. Note that we have written {x 1- 1k-1 instead of (1) I.L..... Xi to simplify the notation somewhat. Now Y2 chosen according to
K
s(2.k)
s(2,1)
Y2 = arg min min
= arg min min ISiSN kes, 9; (2.4) ISiEN kES, Mo x (R)
Explicitly, 81 -i= {k| x = ).J. Hence, the choice Y2 depends only on the values of the draft
[k] tokens {X k=1 and not on the language models used to generate them. We can then write
Pr[V2= = y2 Yi y1, R, c,
(2) (TI.Lik=1)
= PPr = y/2 Y1 = U1. R. c, (X = (01 Ki
for any choice of M
(K) and (! ,..., M,K) Also,
Pr|Y = V1.2
R, c, {X1.1 (M 3k {o ]
-Pr[Y2 1/2 Y1 y1, R, e, (M 1=
(k) 1K
x Pr[Y = R, c, (M (1) 11k= = -
1K
Pr[Y2 = y/2 Yi = yı R, e, (M -
Pr(Y, 91 R, c, (X -
= Pr|Y = Vı2 R, c, [X (M. f [K
1R=1
Therefore, conditional drafter invariance is satisfied for Y1.2. To extend the general case and thus complete the proof, we assume that Yig satisfies conditional drafter invariance, where S j That is,
Pr[Yi:j = Myy R, e, (M. (1.
= PPr(Vis -nis RR e, (X (A))
for any choice of M()) "..,) and M(s
(KK)
M!!) Since
s sli+1.0)
Y5+ arg min min I5I5N kes, Moli Y).,,)
25

---

and S, {k| x
1:j -1gh,, we again see that Yj+1 only depends on the values of the draft tokens
(k)
{x (k) and not on the underlying probability model. Therefore,
Pr[Y = Ms+1 Y1. = 01:h. R2 c, (M = (1) (111)
Pr|X = ys+1 y Y1:5 = Vi.i R. e, (M (-
By the induction hypothesis,
= Pr(Yi:(f+) = V1 R, C, = (=
(
= Pr(Y = y/++ Y1:5 = Miij R, G, (X (1
x Pr(Y1:; yısj |R, c, (X1: (M!
[=1.]]
Pr(Y++1 = U/+1 Y1:5 -yy R, e, (M = (2) K
f
=
x Pr[ = yuu R, c,
-r(( 11-0+13 R, C, (M. (a
Since we have already shown that conditional drafter invariance holds for Y1, it then holds for all sequences Yig, where j
A.5 Proof of theorem 2
Theorem 2 (Conditional LML). Using the strategy above, the error probability satisfies
K
(a) P. (2(2k)
Pr|Y E ,.... x(0 Y = j, A z x
K +
Proof. We begin by following a similar approach to the proof of theorem 1, but we condition on A and the Z 's where necessary. Following the setup introduced in appendix A.2, we define
K = { S/ (
S of?,,..,,'',
s(K) sk..,,s(k) (k)
and this time use conditional augmented target distribution A on 52 (l...., KN with output
Y. Given A = this distribution is defined by the probabilities
(9)( (a) (a(()
q1 (a)
gr(a)
(KN(())
K
K
K
K
With this setup, we find
Pr|y- = j, j E (x(1) (x.,))..,, A = a,
K = =
K
Σ
Pr|f = ji+ (k- - 1,,,, jE (x(1) ..... )x..,,,(())) A= a, 23 = 1
k=1
Σ k=1
Pr(f =j+ (k: 1)N, x = A= =
(10)
As before, the analysis proceeds in the same manner regardless of the values of j and k. For simplicity, we therefore consider the probability
Pr|ý = 1, (1) = 1 A A= --==a a, z =
_ Pr(x 1 ý 1, A= zK = 1 Pr|r = = A= z = 2. (11)
We start by computing
Pr(x
=1 Ý 1, A= 4=0, Z = 1
= Pr
Ti
min
T₃
Ý = 1, A= = K
(1(21)
25i5N
(1(2))
Ti
T₁
Pr
<
min
v= A=0
(12)
P1 (11)
2 (((22)
26

---

To get the second equality above, we note that by construction (TIEY - (Y, + Z forms Markov chain, noted in section 5.2. Since Y is deterministic function of Y, {Ti) (Y + zí is also Markov chain and hence the T,'s ss are conditionally independent of Z given Y and A. We can now leverage similar analysis that in appendix A.2 compute the required probability by first noting that
Ti
T3 (1)
Pr
min 2SESN
y=1,
A =
(1(
Ti
T. pi(21)
Pr
S min
8 =
A A
/Pr[Y =1 A = a]. (13)
P1
(21)
2SISN
Now, conditioned on A = a,
Ti
T;
S min 2SiSN P((21)
and Y
=1
pi(21)
T
T;
Tj
min
and
S
min
P1 (21)
2 (1(21)
(a)
R (())
T2
= Ti S min
(xx( p2 (z(z)//))))) (/pI(=))
TN
TN+1
TKN
max [āN (a)/ū(()) (NII)//1 (N)1
(KN (a)/
We now note that the Ti's are generated independently of the source A, and therefore remain i.i.d. Exp(1) random variables after conditioning on A a. We can then follow our earlier approach leveraging the properties of independent exponential random variables to see that the right-hand side an exponential random variable and is independent of the left-hand side. Let its parameter be Then, using the definition of the (a)'s
's to simplify the result, we have
(a) p=(21)
(a
1 1+X=
Σ max
(a) (1(21)
41
k=2 1=1
N
(g(aa)
p((21)
(K - k(aa)
max
(a)a) (1(21)
(1)a)
As before, we then get
Ti
T (z()))
Pr
y
pi(z))
2
E (m/0///aaaa////000aaaaaaaa/aaa)) (K- (14)
Putting together (11)-(14) gives
Pr|ý 1, (1)) = 1 A = =
Pr = 1 1 -/
ΣN mmax (a
2 (())/
K (+qq(a) EN (mm.mm0OO((()//(())((())
(a) Pr[r - A =
K (a))p1(2))
Pr(Y = a)
(a) K + (a) Pr|ý 1 A = Z = 1
(1(21)
Pr(ý = =1 A a)
We next note that, given a, the selection procedure for Y is
Y == arg min min S( ISiSN ISkŞK (a)
27

---

and the s 's are i...d. Exp(1) random variables independent of A. As result, the distribution guarantee of proposition 1 still holds for Y such that Y is sampled exactly from 4 and Pr(Y =
1 A a) = qı (a). Then,
Pr[e = 1 | A = d) = (a)
(15)
by symmetry and so
Pr[Y 1, 1, x = =1 A zí = (1+
gi(a) Kpi (21)
Pr = =1 a, z 21
or, generalizing to any j and k.
Pr[y =j+ + (A: 1)N, x(() = A a, z =
= -(1+ (1(a)
=j (k- A P =
Kpy(zx)
Going back to (10), we see that
Pr|Y j.. j e (x())
x(K) } 1 A a, Zf = 1
1+ 1)(a) )* Kpy(ex)
-1
Pr|K = (k- ( A= a, z = 1.
Then. going from the joint the conditional probability.
Pr[Y E (X ..... x(K) ( Y = j, A = z = x
Pr(Y = -. J E fx x(K)) A= a, Z = K]
Pr(Y = =j A = a, 2 =
K
1+ gj(a)
-1 Pr(l =j+ + (k: -1)N A a =k
Σ k=1
(16)
Kpp(zx))
Pr[Y = j | A = a, =x K
We now claim that
Pr[y = j+ 1)N| A a, 7 = = Pr|Y = = a, = (17)
Without loss of generality, assume j = 1 and k = 1. Applying Bayes' rule, we see that
Pr[r A A= a, z = x Priza = 2 E 1, A = a PTP
a=
Pr Pr| 7 = K A=
As seen earlier in (15), Pr(r since Y is a deterministic function of Ý and y + (Y, z forms MMrkov chain,
A A= Pr(y 11 | A =a a)/K by symmetry. Furthermore,
Pr|z = 2 1 A= a] = Pr|z = = y
= 1, 4 1, 4=
= Pr[zk 2 y 1, A=a
and so
Pr[zK = ox< Y 11 1, A
a) Pr(Y =1 1 A= ==
Pr(y = 1/ A a, z x
Pr[Z ズ A A= a]
P = a, zK = =M
Since the same argument works for arbitrary j and k. we have shown (17). Finally, substituting back into (16) gives
K Σ
K + (a(a)
Pr[Y E (X(), ((())),.((())) I = A= a, 2
P7 (5(2))
#
28

---

A.6 Proof of proposition 4
Proposition 4. For the coding scheme in section 5.1, the error probability is bounded above
x S EA,,, [
2'(W:AIT)
Pr[Y $ (X
(5)
K LLmax
where AIT (w; a log(pwIA(10) a)/ htt//w/pp (w]r(())
f))
is the conditional information density.
Proof. To obtain the desired result, it is first necessary to identify the target distributions used at the encoder and decoder in the coding scheme from section 5.1, then match these qy a and px|z 2 in theorem 2. Doing this, we have Qr ( (i a) PBIA ( R, a) and Px]z 1, f) PBIZ Bg L, f). Recall that we defined Z (Tk: Eÿ) to encapsulate the side information and message available to decoder & when the selected index is Y = j. We also defined B; = (i, f.). Given Tj lx. each ( then sampled using the target distribution Px|z(. Lk, Eg), and our sampling process generates
(1) ,...,,,..,., X (K), Applying theorem 2, we get
Pr[Y (x(),
X Y A= a, z -1(4,, K grialil -1
K
Pxiz(i (x,
K
PBIAli,e |a) -1
K +
Pniz(iee txx tx:eg))
k=1
K+ Pwin(j |a) Lmax Pwir(j ( tx)
K
KK + 24 Lmmxx)
where (is (x) = log(pwia(i a)/pwir(i (x) is the conditional information density. After removing the conditioning, we get
K
Pr[Y E (X(1.
x(O)) 2 EA.WET
Σ (K + 2:(W:AIT)
Immax)
KAA.. [(K 2:(W:A|T) [mmax) 21
21(W:A|T)
EAWwT
Limx
By taking the complement finally get bound the error probability,
[1++ 21(W.))T)
Pr|Y & (x(1) ..... x(0 < E.W.T.
Kmmax
A.7 Proof of remark
Degenerate proposal distribution. First consider the case where the distribution Px has all its mass on one element. Without loss of generality, let assume p1 and p; 0 for all j o 1. On the (K) 1 for every outcome in the sample space,
left-hand side of (3), since (1) (2) we get
Pr|Y E (x(1)
(X())..,,X(])) = Pr|Y 1].
Now evaluate the right-hand side of (3). Since 9:/n 2 pp/pi for all siS N, the term in the outer sum evaluates to
K
K
= 41-
Imax (g/ pp/pi) )+ + (K 1)q./q1l
EN199/9 + (K 1)g./1l
K/q1
29

---

We will evaluate the remaining terms more carefully by taking limits. For j # 1,
K
lim
P
Li=1 [max//////
pt/P,) (K 1)9./90l
Kp;
lim Ph +0
Eiz [max P; + (K 1)g:ps/qil lim px- [pp
pa 0 Ei= [m
(K - 1)g:p/ /g/]
We can now directly evaluate the numerator and the denominator separately. The numerator becomes zero, and for the denominator we get
PiPj 9j
qiPj
lim
Pi
+ (K
-1)
P2.PPN
q
(K 1) Pj
91PI
Σ
qiPa PP
+
max
PP
max
4
pa....P
P1
Therefore, # terms are all zero. The hand side of (3) becomes Q1 = Pr/Y = 1], verifying that the bound exact for this class of distributions.
The case of K Next, we will work out the matching probability for K 1 explicitly
special case to confirm that our bound recovers the exact expression. When K = 1, the matching probability
Pr[Y x
Σ Pr = pr x()) x()) 5).
For convenience, we will drop the superscript on (1) and also on the S. during the analysis. With K 1, the GLS procedure can therefore be written more simply as
1. Select Y = arg minigigN St/g: to generate a sample from gy- Without loss of generality assume
2. Select X = arg min sig Si/p; to generate sample from px.
We can then focus on finding the probability of the event
Y = 1 and X = 1
S <
S
S
S
min
and
<
min 2
2
4
P1
S
S < min
25E5N max (g:/ (t.,Pt/P13
The RHS is an exponential random variable independent of the LHS. If its parameter is X, then we get
N
qi
Pi
1+
max
Therefore, by the properties independent exponential random variables.
Pr|Y = 1, X= =
ΣN max(1/gn pp/p))
Therefore after generalizing to arbitrary j we get
Pr|Y = X| =
j=l Einl pxx
This is exactly the RHS of (3) evaluated for K 1.
30

---

Identical draft and proposal distributions. Next, we examine the case when px and qy are identical, i.c. p; qi for all S i S N. From our proof of proposition appendix A.1 recall that
Sj
و S
Sivi
==j=
Vi
48
where Sj min s(k) Therefore, choosing Y = j implies that there exists some k such that
S(k)
S
S 5
v (i,() + (iA)
V Vi
45
4:
4j
45
But, since P; = 9; for all 1 S S N,
(k))
( k)
Vitj x =j
Pi
Ps
In summary, if Y = j then there exists some k such that ( = also, and hence Pr[Y e
(x(1) ..... " x(K]]] = 1. And under our assumption that p; qi for all s S N, the right-hand
side of (3) simplifies to
N
N
K
K
max ( /9: Pp/p,} + (K 1)/
9 + (K- 1)9./9)
j=1
1=
N
4j
1.
-=1
B Connection to the notion of drafter invariance from Daliri et al. [9]
In Daliri et al. [9], an intuitive notion of drafter invariance is proposed for single-draft speculative decoding with the following interpretation: given fixed random numbers, the output of the speculative decoding algorithm is function of the context and target model weights only. Our notion as stated in definition somewhat weaker, since we allow the output to depend also on the draft sequences, yet we still require that a given set of draft sequences always produce the same conditional output distribution. To formalize the notion of Daliri et [9] and extend propose the following more restrictive definition, which we call strong drafter invariance.
the multi-draft case, we
Definition 2 (Strong drafter invariance). Let R be the source of randomness used to draw samples, e.g. the output of random number generator, multi-drafi speculative decoding algorithm is strongly drafter invariant if, for all 1 < TT
Pr(Vi: = Vi:j R, c. x = FILL
(K) l:L
(K) 11L = Pr[Vis = yı.s R, c).
Unfortunately, satisfying definition incurs a performance penalty in multi-draft implementations. which can be seen empirically from the extended results in appendix D.1. To see why, note that the choice of Y, at each step j in algorithm 2 depends on the current set of active drafts S, which itself is function of the preceding draft tokens. To completely remove any dependence on the draft sequences as required by definition 2, we would need keep S fixed throughout the procedure, wastefully coupling the target model's output to draft tokens that have already been rejected. Regardless, now show how our method as described in algorithm can be modified to support strong drafter invariance by way of the following proposition.
Proposition 6. If the minimum is taken over all k E {1,..., K} in lines 9 and 13 of algorithm 2 instead of over E S, strong drafter invariance holds in the sense of definition
Proof. We extend the proof of conditional drafter invariance set out in appendix A.4. There, we showed that
Pr[M y1 R, c, {x (k) [ (2(t))
Pr|y v1 R, cl
31

---

which is enough to prove strong drafter invariance for Y1 As a result, we only need to modify the inductive step the proof. Take some j < т. With the modification that the minimum taken over all l: E (1,..., } instead of over k E S in lines 9 and 13 of algorithm 2, Yj+1 is selected as
S S(1-1A)
Y
arg min min IgigN igkg Mo(i Yiy.))
From this, given R, and Yı., the draft tokens not involved, either directly or indirectly, in the choice of 1+1.. More precisely,
Pr|Y Ms+1 Yi.- yi.j. R, e, (M
)
(6) (f11t/k=1)
= Pr[[2,+1 = Wi+1 |Ygs Wiih R, c).
Now assume that Vi.5 satisfies strong drafter invariance. result,
Pr(Ye++1) = 01.(+1) R, c, (XLL(MM
Pr[Y2+1 = Mj+1 Yıj Vluj, R, C, (ML ( KK
x <rr(Y = Mı R, c, (Xi, = (11.2kkl K k=l
Pr[Y,+1 = Ui++ Yı5
yıyj R, cl Pr[(Ys - myi R, cl
= Pr((i.6+1) = - R, cl
Therefore, strong drafter invariance holds for all sequences Yıgj, where SJST.
We can also obtain lower bound on the token-level acceptance probability of the strongly drafter- invariant scheme. Assume the drafts are i.i.d. from the same model M,. thus using the same setting as proposition? 2. Reexamining the steps in the proof of theorem found in appendix A.2, we see that the number of active drafts at the current step is S K, one these J candidates must match the target for token to be accepted. On the other hand, rejection now occurs if the target matches any of the remaining K - J drafts, or none at all. Specifically, assuming without loss of generality that the active drafts are X ,..,,..., ,x)),, (7) becomes
Pr|Y e (X(),... ....,
Σ JP.l = x = 51.
j=1
However, the augmented target distribution described in (6) remains unchanged, because all K drafts remain coupled through the common randomness. This includes the K drafts that have already been rejected during previous steps. Following the same analysis as in appendix A.2 then shows that the probability of accepting least one token at the current step with context e bounded below as
J
Pr|accept]
E f P./Pp} + +(K 1)
where px = Ma(- | c) and qr = Mr( c). Conversely, with J active drafts proposition 2 gives
J
Pr[accept]
Lillmaxxqu p1/p,) + (J- 1)4./a
for the original conditionally drafter-invariant algorithm. Since J K, can see that requiring strong drafter invariance reduces the lower bound, providing some theoretical insight into the poor performance observed in appendix D.I when using this scheme for LLM inference.
C Extension to continuous distributions via importance sampling
not possible to enumerate the entire sample space when dealing with continuous distributions. At first glance, this appears to preclude the use of GLS in such settings. However, we can obtain approximate samples through importance sampling as described Phan et [36]. For clarity, we skip the general case and instead proceed directly to the source coding application set out in
32

---

section 5.1 of the main paper, removing the assumption that W is discrete. To start, we choose some sufficiently large N and generate ii.d. samples of W following pw. Let these samples be UN = (U:)-_ Recall that pw is the marginal target distribution for the decoder's ss output. Again, let -1....,f.y Ey be uniform random integers selected from (1...., I_ We then have the tuples B, = (U,, 4) forming part of the common randomness, the difference from section 5.1 being that the U,'s are now also random, whereas in the discrete case they were fixed to enumerate the whole sample space.
At the encoder, we want to sample Y approximately from PaJa given the observation a. Therefore, we introduce the unnormalized importance weights
(U.) PBIA BB a) PWIA (W a) PB (B(
Pw (U,)
Similarly, the decoders should use the target distribution PB|z. where decoder k has access to Zi (Tk, (z). Here, j is the selected index at the encoder and Êj is the associated random integer. Given Th- = th, we define
PB (B (2, (w 16) = E,}
x (U.)
(B.).)
pw Pw (U:)
The final normalized importance weights are
\O,((UN) (4,( and (U
p.d (U:)
ΣE= Ans(Us))
Σラn (U,))
The index selection the encoder and decoder simply proceeds as
s(())
S((t)
Y arg min min isigN ISASK (UN) and x-(k arg min
min (1) p.b (UN))
ISiSN
The output of decoder k is then taken be Wi = Ux Conditional on U. the bound on the index matching probability stated in proposition 4 holds. However, we need a bound that is conditional only on Uy. To start, we write down the bound when conditioning on U. drawing from the development in appendix A.6.
Pr|Y E (X(,,
x j, A= z = K UN = =u
-1
K + )
1 (uf²)
A=1
K
(4))
(== Apd (uf²)
(k)
K +
A.j (1z) E (x))
For simplicity, let us assume for now without loss of generality that j = 1. We want to remove the conditioning on U/,,..,, UN. which can be done by taking the expectation to get
Pr[Y E (X(1) x(K) V = 1, A a z
2 K U1 =w]]
K
X (11)
N
(UN)
Euy
K +
1=
y=1,A=a, Z = =k U1
[ (m))
Σ i= XU
A=1
K
À (u1)
2 N
-i (UFN)
Σ Eug
K +
A= Z , U1= = in
(k)
N (Ux((UP))
p.1 (21)
k=1
K
(un) Euy
Di= J00 (UF)
N
2
Σ
K
y= 1, A=
2 =
K -KKKK--
Ap1 (ui)
ΣM (U
k=1
where the last step uses Jensen's 's inequality. To simplify the inner expectation, we use the following lemma, stated here without proof, which extracted from the proof of theorem 3 in Phan et al. [36].
33

---

Lemma ([36, p. 23)). We have that
Σ i= 20 (UP)
Y=1, A=a, zf = = Us un u1
F
S (uu(N,u))
(18)
E (U
where
1 (u1) + N (N un) (qn(( + N
K(N) (1 )pa((r)
)
2w LNN)
(1 I+
)
+
N 1+
+
N
N
N
In the equation above, we define N = N - and
K(N) (1 + (ui)//NN
4(w - 1)
11
(N 1)w
N
(71))(1)) + Ñ )
2 (11) +
2
[11+ (N + 1)W +1
N )
w -
x V
2+ 4
N
I(N) vw - Vascow Pww al: a)) - ds(pw pl a))2
+ +w - 1)ds(Pw PW]ja a))
where, for all m 1,
Pw [PWIA(W a)m
dp+ Pw]a(- (pp. [a)
Ew-
and w is chosen so that, for all a and w. PW] aw]j(w) (w a)/pw (w) S w.
Using lemma 1, or more specifically (18), and generalizing to arbitrary j. we see that
Pr|Y (X(), ..... X Y j, A=a, z 21 U, uz]
K
K + MN(N, Ug)
(1) puj (us)
K
Xmns(n)) (1z))
K K+M(N, Ug)
P.j
where jaN, uz) s Mi (N, Using the definitions of (U,) and (1))),)) (uz),
Pr|Y E (Xa) ..... x(0) Y == A= a, ze = = U, = uz]
K
K + M(N, un) Pwla(us la)/ Tmmax -1 PWIT (uy tx)
km1
K
Σ (K + AAN, 2. Lmmx)=
To proceed and find a counterpart to the coding theorem in proposition 4, we use the fact that for any > O, there exists some M₁ such that μa (N, uz) S 1 + for all N > M2 and S j < N [36. p. 24]. Hence, with M = maxıgk<K Mt, we see that (aNN, uy) I 1 + e for all N 2 M and 1 i N. As result, after removing the conditioning and following the steps used in the proof of proposition 4 in appendix A.6, we get
Pr|Y (x()) x(O EA..T
(1+(1+
A(TT)
K LLmax
and the associated error probability bound is
(1+
((T):
Pr|Y & (x(1) ((.,,,,()))))) EAW.TT
K Lyax
34

---

Acceptance rate
SpecInfer [29]
SpecTTr [33]
Our scheme
0.6
Upper hound
5
10
15
20
Number of drafts
Figure 6: Proof of concept on random toy distributions.
D Additional experimental details
D.1 Multi-draft speculative decoding
Proof concept on toy distributions. As simple demonstration of our method with arbitrary discrete distributions, we generate 100 random instances of px and q each containing N 10 elements, while the number of proposals is varied between and 20. Results are shown in figure 6. As well showing the token-level matching rate achieved by SpecTr [38], SpecInfer [34] and our algorithm, we also plot the optimal multi-draft acceptance rate with communication. which can be computed via linear programming approach [38], at least for distributions small alphabets. Note that while this calculation provides a useful upper bound, there is currently no multi-draft token selection scheme that achieve the optimum in practice. Despite involving communication between the drafter and the target, our algorithm is competitive with sate-of-the-ae methods, especially when the number of drafts is large.
LLM inference. Implementations of SpecInfer [34], SpecTr [38] and our drafter-invariant schemes be found in the provided code. To obtain performance measurements, each speculative decoding configuration is tested on 200 prompts from the GSM8K [7], NaturalReasoning [48], MBPP [1] and DROP [10] datasets, and 164 prompts from HumanEval [6]. Our full set of results is given in tables and 4: please note that not all datasets and configurations are reported in the main paper. We also include results for the strongly drafier-invariant scheme described appendix
The target model is Qwen 2.5-7 B [47] while the drafter is Qwen 2.5-0.5 5 B, and we use top- K sampling with K = 50. For our experiments with i.i.d. drafts table 3, the temperature is 1.0 throughout and the maximum draft length is L = 4. When we use diverse drafts in table 4, the target temperature is 2.0, the two draft temperatures are varied and L =
As described in the main text, the block efficiency is equal to the average number of tokens accepted during each iteration of the speculative decoding algorithm, while token rates calculated from wall-clock measurements and reported as percentage speedups relative to single-draft speculative decoding with the same draft length. We compute the mean across all prompts for each dataset, then repeat the experiments times with different random seeds. For a configuration-datass pair, this gives us five measurements each for the average block efficiency and token rate. Let these be BE,,... BE, and TR2, TRs. As our final result, we report
BE mean (BE, ..... BEs), TR mean (TR....., TRs)
while the error bars show one standard error of the mean,
ØBE = std( BEs)/ V5, OTR = std TRs)/V5
where the std operator the usual sample standard deviation formula. If is vector of M independent measurements in R. this is
M (x; x2 mean
std(x)
M-
a NVIDIA RTX6000 Ada GPU with 48 GB of memory, each configuration can be tested on single dataset in around hour.
35

---

Table 3: LLM inference with i.i.d. drafts; we use L = 4. Token rates (TR) are shown as percentage speedups relative to single- draft speculative decoding which has mean block
efficiency (BE) 4.18, 3.75, 3.43, 3.68, 3.00 and token rate 58 83, 53. 08,08, 48.30 30, 52.54, 42, tokens on GSM8K, SlamanEval, NaturalRcasoniin MBPP and DROP respectivcly.
0.61
10. 16 0.19
10.98 + 0.41
10.60 1 0.24
0.34
10.03 1 0.55
9.97 + 0.34
0.32
5.74 1 0.57
9.98 0.30
10.90 0.26
10.60 + 0.34
3.74 1744:0050 0.24
7.87 1 0.44
7.92 + 0.66
7.40 + 0.99
0.10 0.46
TR
8.08
6.35
8. 8.82
DROP
3.33 +
3.58 + 0.00
3.72 + 0.01
3.82 0.01
3.31 1 0.01
1 0.02
0.01
3 0.01
0.01
3.56 - 0.00
3.73 + 0.01
3882 0.01
+ 0.02
3.53 1 0.01
3.67 0.00
0.02
0.69 0.33 2,94 0.01
3.60
3.72
3.79
3.27
3.25
3.75
6.51 0.51
0.53
12.65 0:45
13.81 0.47
0.43
0.43
11.77 0.29
12.81 0.500
0.27
0.228
12.79 0
18.54 #041
0.600
8.71 8.71 0.17
0
10.85 +
11.46 0
4.29
10.07
5.46
10.72
10.92
5.21
4.29
MBPP
4.04 + 0.01
0.01
+ 0.01
0.01
1 0.01
0.01
0.00
4.50 + 0.01
0.00
0.01
- 0.01
0.01
0.02
0.01
4.38 0.001
0.001
3.61 0.01
4.44
4.30
4.41
4.49
4.04
4.32
4.43
4.02
4.30
4.43
4.51
4.00
4.26
0.26
0.32
0.31
0.56
5.44 1.544
0.33
11.51 0.43
12.80 0.96
4.52 1.42
0.96
12.75 12 1.14
1.10
8.25 - 1.01
9.84 + 1.08
10.32 + 1.13
222 0.29
TR (%)
12.14
NaturalRcasoning
6.26
10.63
12.35
12.49
5.44
10.00
9. 8.86
3.56
3.75 + 0.01
3.99 + 0.01
4.12 + 0.01
4.19 + 0.01
3.76 - 0.01
4.02 + 0.01
4.13 4.13 0.01
4.22 - 0.01
+ 0.02
+ 0.01
4.10 0.01
0.00
+ 0.01
3.91 1 0.01
4.02 + 0.01
4.09 + 0.01
3.32 + 0.00
BE
3.68
3.96
3.65
6.07 + 0.53
0.27
8.00 - 0.92
7 0.85
4.80 1 1.04
1 0.96
0.78
0.77
0.78
0.77
8.54 - 1.02
8.03 0.97
0.87
6.23 0.76
6.69 + 0.55
0.69
0.30
0.30
TR (%)
0.04
HumanEval
8 3.69
7.89
7.39
7.70
7.09
4.70
8.52
8.03
3.18
6.23
6.69
5.99
4.11 0.02
4.35 + 0.01
0.01
4.54 + 0.01
113::000 0.01
1 0.01
4.48 + 0.01
0.01
0:01
4.50 0.01
0.01
4.28 0.01
0.01
0.01
3.09 = 0.01
4.47 1
BE
4.56 =
4.46
4.13
4.36
4.08
4.37
4.03
4.40
4.46
0.21
5.39 + 0.23
4.56 0.20
0.29
1 0.13
4.30 0.35
4.75
4.02+0.2 0.28
26
+ 0.25
1.24
3.02 0.41
1
0.57
5.23 5.23 0.47
4.49 +
0.63
0.24
+
3.75
5.20
4.56
2.27
4.08
4.30
3.02
5.18
5.33
4.83
3.02
4.45
0.63
GSM8K
0.01 0.01
0.01
4.72 + 0.00
+ 0.00
0.01
+ 0.01
4.74 + 0.01
4.78 + 0.00
4.47 1 0.00
4.74 + 0:01
1.88 0.00
145+000 0.01
+ 0.00
+ 0.00
+ 0.01
4.16 0.01
4.47
4.66 +
4.64
4.75
4.46
4.66
4.78
4.45
4.63
4.72
4.76
K
8
4
8
4
6
Specinfer [34]
Daliri et al. [9]
Spec [38]
Strategy
scheme
Strongly invariant
Our
36

---

4.22 # 0.99
7.83 + 1.08
9.11 + 0.74
9.15 1 0.83
5.50 1 0.44
6.28 1 0.79
9.36 + 0.93
4.67 # 0.66
4.79 - 0.51
6.26 - 0.51
6.19 - 0.43
2.80 + 0.36
3.17 # 0.76
7.67 1 0.29
-112 + 0.38
-0.58 + 0.96
-0.90 0.000 0.71
0.22 + 0.86
-3.72 1 0.68
-3.25 # 0.68
0.39 0.56
Table 4: LLM inference with diverse drafts; we use L = 5, K = 2 and the target temperature 2.0. The temperatures of drafters and 2 vary and are reported in the second column. Token rates (TR) are shown as percentage speodups relative single-draft speculative decoding with drafter temperature 1.0, which has mcan block efficieney (BE) 4 4.28 3.65, 3.19. 3.71, 3.06 and token rate 52.00 00, 44.15, 38 61, 14.70, 36. 12 tokens// /s on GSM8K, HumanEval. Natural Reasoning, MBPP and DROP respectively.
(%
TR
DROP
3.21 0.21
3.31 + 0.02
3.31 1 0.02
8.48 0.91 3.30 + 0.02
3.19 3.19 0.01
3.21 2 0.02
3.30 + 0.02
3.21 3 0.01
3.23 - 0.01
3.22 0.01
3.23 - 0.02
3.12 1 0.01
3 0.01
3.27 3.27 + 0.01
3.05 0.02
3.06 + 0.02
3.05 0.00
3.08 1 0.02
2.97 1 0.02
2.88 + 0.01
0.88 3.08 + 0.02
BE
3.13
3.05
1 0.79
4.77 + 0.55
10.70 + 0.59
6.83 + 0.63
6.89 0.33
5.17
0.66
1.01
0.83
9.00 + 0.63
4.95 #.66 0.61
5.74 0
0.60
1.27
0.75
1.34
1.3 0.88
+ 1.21
5.64
TR
5.64
5.99
9.59
5.74
8.57
3.92
4.49
-
0.63
4.24
4.55
0.06
MBPP
0.01
3.00 + 0.02
4.05 + 0.01
0.02
0.01
0.01
0.00
0.02
0.02
0.02
+
0.03
3.88 0.02
0.001
+.03
0.03
0.02
0.01
0.01
3.55 0.02
3.73 0.01
BE
3.95
3.00
3.71
3.94
3.06
3.98
3
3.91
3.95
3.96
4.02
4.00
3.86
4.08
3.00
3.57
3.00
3.71
3.57
-6.5 + 0.61
1.12 + 0.99
11.28 + 0.88
6.06 - 0.37
9.12 1.12:000 0.98
5.71 = 0.73
3.37 3.37 0.44
0.15
= 0.57
4.58 0.36
4.71 4.71 = 0.88
1.74 = 0.69
1.67 1.67 0.56
0.91
0.96
-9.99 0.76
4.35 1 1.16
6.89 1 1.07
6.78 0.77
4.82 1.14
0.37
0.94
4.79 4.79
TR (%)
NaturalReasoning
4,82
-
-0.94
10.09
-3.31
+ 0.67 3.04 + 0.02
3.20 +: 0.02
3.60 + 0.02
8. 8.19 0.82 3.44 + 0.01
6.75 0.72 3.51 + 0.02
4.73 1.22 3.42 + 0.02
+ 0.01
0.01
8.77 0.99 3.25 + 0.01
0.41 3.41 1 0.01
9.17 0.98 3.42 12 0.02
5.79 0.77 3.31 0.01
6.08 0.72 3.32 + 0.01
0.00 + 0.01
4.74 # 1.34 2.98 0.02
2.95 + 0.01
3.14 + 0.01
3.10 + 0.01
3.02 + 0.02
3.02 + 0.02
3.08 + 0.01
BE
6.32 0.36 3.36
9.80 0.82 3.27
4.13 + 1.60
9.67 = 1.26
0.88
55.20 + 1.31
2239 0.60
0.85 + 1.15
0.97
= 1.18
0.94
(%)
HumanEval
TR
1.96
10.42
12.15
5.00
4.17
1.30
3.57 + 0.00
+ 0.03
+ 0.03
0.02
3.88 1 0.01
3.82 - 0.02
= 0.02
1 0.01
1.58 3.06 = 0.02
11.37 1.81 4.03 = 0.01
= 0.03
1 0.02
0.01
0.02
0.01
3.48 + 0.03
3.56 + 0.03
3.63 1 0.03
3.47 1 0.03
- 0.02
3.61 + 0.01
BE
4.08
3.80
3.09
3.95
3.87
4.00
11.56 + 1.57 3.99
3.87
3.87
3.49
3.50
1.02
4.57 + 1.80
8.75 : 1.70
7.43 1.60
+ 1.43
6.53 1.79
6.02 1.35
1.35
1.78
1.78
8.15 1.16
1.16
+: 1.29
+ 1.67
0..07 + 1.00
0.91
1.71 1.71 0.61
0.70
0.73 0.73
1.56 0.68
-1.17
0.68
TR (%)
0.06
6.38
11.50
11.40
8.25
13.68
3.98
0.68
0.73
GSM.KKK
11
+ 0.02
4.44 + 0.03
4.63 + 0.02
4.57 0.03
4.53 1.0
0.01
4.55 4.00
0.02
1.0/1.0 4
4.75 0.02
1.0/0.5 4.75 0.02
4.77 0.02
4.77 1 0.02
2.0/1.0 4.63 1.0 0.02
1 0.03
0.02
0.02
0.03
4.27 + 0.03
+ 0.02
4.35 0.02
4.31 0.00
1.0/2.0 4.29 0.01
4.34 0.02
BE
4.44
1.26
4.75
1.62
4.83
4.22
4.44
1.0/1.0 4.34
Temp.
0.5/1.0
1.0/0.5
1.5/1.0
1.0/1.5
2.0/1.0
1.0/2.0
0.5/1.0
1.5/1.0
1.0/1.5
1.0/2.0
1.011.0
0..5/1.0
1.0/0.5
1.51100
1.0/1.5
2.0/1.0
SpeeInfer [34]
Strategy
scheme
Strongly
invariant
Our
37

---

GSM8K
HvmanEval
NaturalReasoning
Strategy
BE
TR (%)
BE
TR (%)
BE
TR (%)
SpecInfer [34]
2.35
0.00
14.16
1.55
1.98
1 0.01
-0.29 1 0.66
2.14 0.01
11.44
0.73
SpecTr [38]
2.35
0.01
13.41
2.10
1.99
0.01
-0.39 1 1.01
2.14 0.00
11.32
0.48
Our scheme
2.34
0.01
14.65
+ 1.90
2.00
0.01
1.58
2.00
12.08
0.38
Daliri et al. [9]
1.64
0.00
1.39
+ 0.30
1.48
0.00
2.69
0.49
1.54
0.00
2.83 = 0.66
Table 5: LLM inference with i... drafts using L = 4; the drafter is Llama 2-68 M and the target is Llama 2-7 B.
Token rates (TR) are shown as percentage speedups relative to single-draft speculative decoding, which has mean block efficiency (BE) 1.65, 1.48 and 1.55 on GSM8K, HumanEval and Natural respectively.
GSM8K
HvaanEval
MBPP
Strategy
Tmp. 1/2
BE
TR (%)
BE
TR (%)
BE
TR (%)
SpecInfer
0.5/1.0
2.21 + 0.01
12..51 1.09
2.61 + 0.04
-4.73 - 1.67 2.46 0.03
-5.99 + 1.14
[34]
1.0/0.5
:.02
-2.47
= 0.88
2.79
0.03
3.02
2.65 0.02
1.09 + 1.85
1.010
2.57 + 0.01
0.73 2.94
0.02
7.50 1.04
6.86
1.23
Our
0.5/1.0 2.67 + 0.03
5.88
- 1.46
3.63
+ 0.02
33.85 1.11
3,33
0.02
25.71 1
scheme
1.000.5 2.69 + 0.02
6.33
- 1.49
3.67
1 0.04
34.67
+ 1.63 4.31
23.87
1.47
1.0/1.0 2.88 1 0.01
13.00
1.12 3.72
0.03
35.90
1.40 3.51 1 0.03 32.20
2.37
Table 6: I.LM inference with diverse drafts using T. = 5 and a target temperature of 2.0; the drafter is Llama 3-1 B and the target is Llama 3-8 B. Token rates (TR) are shown percentage speedups relative to single-draft speculative decoding with drafter temperature 1.0, which has mean block efficiency (BE) 2.42, 2.73 and 2.61 on GSM8K, HumanEval and MBPP respectively.
speculative decoding framework's 's effectiveness on other popular families of LLMs, we run a smaller set of experiments on open-source Llama models, mirroring those shown in tables 1 and 2 in the main paper. As in those results, we set K 8. In table 5, we use a lightweight Llama 2-68 M drafter distilled by Miao et al. [34] for SpecInfer coupled with a Llama 2-7 B target, and K 8. Since the small 68 M drafter performs badly with temperature mismatch, we use larger models from the Llama 3 series in table 6 with a 1 B drafter and 8 B target. There, we use K- 2.
Results Llama models. To illustrate
Empirical matching probability, comparison to the LML bound and scaling with K. We further provide some numerical results in table comparing the empirical average matching probability, using the target and proposal distributions for the next token seen during our speculative decoding experiments, to our lower bound in theorem 1. These demonstrate that the matching probability and lower bound both increase monotonically with K, and that the LML bound is quite close the true probability for practical distributions of interest.
For completeness, we also show below the same empirical matching probabilities for SpecInfer [34] and SpecTr [38] in table 8. Our approach performs similarly to or in many cases better than these methods, even though they do not offer any drafter-invariance property.
Absolute token rate measurements. Since concrete performance measurements are tightly coupled to our specific hardware configuration and unrelated optimizations enabled by the LLM inference library, in our case Huggingface Transformers [44], we focus on relative speedups to provide fair comparison between different speculative decoding algorithms. Nevertheless, to provide context around our reported gains, it may be necessary to convert to throughput in tokens per second. To facilitate this, we provide the throughput for single-draft speculative decoding the captions of tables 3 and 4. Since all other numbers are relative to this baseline, they may be converted to absolute quantities as needed.
Dataset
K = 2
K 1
K = 6
K 8
Emp.
LML
Emp.
LML
Emp.
LML.
Emp.
LML.
GSM8K
0.949
0.936
0.972
0.956
0.979
0.965
0.982
0.971
HumanFyal
0.919
0.903
0.950
0.931
0.962
0.945
0.971
0.953
NaturalReasoning
0.862
0.844
0.905
0.884
0.926
0.904
0.937
0.916
Table 7: Empirical (Emp.) matching probability during speculative decoding compared to the LML bound.
38

---

Dataset
K
2
K =
K
K = 8
ST
ST
ST
SI
GSM8K
0.948
0.927
0.969
0.938
0.976
0.944
0.981
0.948
HumanEval
0.919
0.891
0.948
0.908
0.960
0.916
0.967
0.922
NaturalReasoning
0.864
0.837
0.904
0.864
0.921
0.878
0.932
0.887
Table 8: Empirical matching probability for both SpecInfer (SI) [34] and SpecTTr (ST) [38].
Dataset
Algorithm
ROUGE-1
ROUGE-2
ROUGE-L
GSM8K
SpecInfer
0.737 + 0.004
0.592 = 0.007
0.647 + 0.008 0.745 + 0.009
Our scheme
0.801 + 0.005
0.701 + 0.011
HvmanEval
SpecInfer
0.656 = 0.003
0.466 = 0.006
0,545 + 0.005
Our scheme
0.710 = 0.001
0.555 = 0.003
0.628 + 0.002
MBPP
SpecInfer
0.676 + 0.004
0.497 + 0.003
0,580 + 0.004
Our scheme
0.728 + 0.006
0.588 = 0.011
0.659 + 0.010
Table ROUGE scores measuring decoding consistency for our scheme and the non-invariant SpecInfer [34].
D.2 Ablation and empirical analysis of drafter invariance
Here, we further justify our definition of drafter invariance by way of ablation study that sets out to show that adopting drafter-invariant speculative decoding has a positive impact on decoding consistency across runs in practice when the draft model is changed. We also provide some salient examples to demonstrate the property's 's robustness.
To quantify the effect of drafter invariance decoding consistency, we run 200 prompts from the
GSM8K [7], HumanEyal [6] and NaturalReasoning [48] datasets using = 2 drafts. Each prompt twice using the same random seed. The drafts are i.i.d., but the drafter model temperature is changed from 1.0 the first run to 0.5 in the second. We compute ROUGE scores [30] to measure the similarity of the two generated output sequences; perfect decoding consistency would mean score of 1.0 for all of the ROUGE-1, ROUGE-2 and ROUGE-L metrics. We let the draft length be L = 4 and average over 4 random seeds. Results are given in table 9, Our conditionally drafter-invariant scheme givens higher similarity scores in each case compared to the non-invariant SpecInfer baseline, confirming that drafter invariance provides more consistent outputs when faced with changes the draft model, even though our notion is not strong enough to guarantee that the outputs always remain exactly the same. Moreover, appendix B we demonstrate slightly modified scheme that provides what we refer to as strong drafter invariance, which provably gives perfect decoding consistency. However, this comes at a cost to the block efficiency, as seen tables and 4.
While the ROUGE scores from our ablation study provide a more comprehensive way to examine the real-world impact of drafter invariance, we also give a concrete example from GSM8K where non-invariant speculative decoding causes the output to diverge significantly from the original after changing the draft model, all while retaining the same random seed. We adopt the same setting as before with K = 2 i...d. drafts and the draft model temperature changing from 0 to 0.5 between runs, comparing against SpecInfer [34]. It should be emphasized that all forms of speculative decoding preserve the output distribution exactly; therefore, it is not the quality of outputs that is degraded but rather their stability or consistency faced with changes to the drafter. In this particular example, our scheme achieves perfect consistency between the two trials; we do not guarantee this in general, but the ROUGE scores from our ablation study demonstrate that we do perform better in this sense on average.
Prompt:
Weng earns $12 hour for babysitting. Yesterday, she just did 50 minutes of babysitting. How much did she earn?
SpecInfer (not invariant), draft lemperature 1.0:
To determine how much Weng earned for babysitting for 50 minutes, we first need convert the time from minutes to hours. We know that there are 60 minutes in an hour, so we can convert 50 minutes to hours by dividing 50 by 60:
N[
39

---

\text(Timme in hours] \frac(60)<60) \frac(5)66) \text( hours)
V]
Next, we calculate the earnings by multiplying the time hours by her hourly rate of $12:
M[
ttxx 12 Atimes
SpecInfer (not invariant), draft temperature 0.5:
To determine much Weng earned for 50 minutes babysitting, we need to follow these steps:
1. Identify Weng's a hourly wage.
2. Convert the babysitting time from minutes to hours.
3. Calculate the earnings based the time worked. First, Weng's s hourly wage $12. Since she babysat for 50 minutes, we need convert 50 minutes into hours. There are 60 minutes in an hour, so we can convert 50 minutes to hours by dividing 50 by 60:
A[ \Text((Tmme in hours} \frac(
Our scheme (invariant), draft temperature 1.0:
To determine much Weng earned hour, we need to follow these steps:
minutes babysitting at rate $12 per
1. Convert the time from minutes to hours.
2.
Multiply the time in hours the hourly rate.
First, convert 50 minutes to hours. Since there 60 minutes hour, divide by 60:
A[
(frac(50)66)) \frac(5)((6) \text( hours)
A]
Next, multiply the time in hours by the hourly of $12:
Our scheme (invariant), draft temperature 0.5:
To determine how much Weng earned for 50 minutes babysitting at a rate $12 per hour, we need to follow these steps: 1. Convert the time from minutes to hours.
2. Multiply the time in hours by the hourly rate.
First, we convert minutes to hours. Since there are minutes an hour, we divide 50 by 60:
M[
(frac(50))60)) \frac(5)(6) \text hours)
\]
Next, we multiply the time in hours by the hourly rate $12:
D.3 Synthetic Gaussian source
In this section, we provide some key derivations and details of our experimental procedure for evaluating GLS on the synthetic Gaussian source, and give more numerical results.
Decoder target distribution. To determine the decoder target distribution Pwir, we first recapitulate the problem setting and the random variables involved. The Gaussian source is A ~ (o 1) while the target distribution the encoder given A is Pw a(: AW a) Naa, oh W(A)) Meanwhile, the
side information at decoder & is Ti- = A + CR. where ÇA ~ (0, o Since we are only analyzing one decoder individually, we will drop the k subscript in what follows and more simply write T and Ç. To summarize, we have
W A 7 and T A+C
where 1/ and are independent zero-mean Gaussians with variances o = oiy and of respectively, From this, see that W and I'' are jointly distributed
=0
=071A
W T
2 ETW
E
WT
Ar (0, EW.)), where Vwr
(19)
2
1 o2
40

---

The variance of W is ow 1 of and that of T is o7 = + or. Gaussian distribution with mean and variance
We then know that PW r is
T
T
Wi1 = 1+ og 1+ 3c
= o
AWIT = 1+ 2
2
T TT
That is, Pw (0) - NN - 1/o3)) as asserted in the main paper.
MMSE estimator. We now derive the MMSE estimator for the synthetic Gaussian source when side information is available at the decoder. To find the estimator, we assume that the encoder and decoder indices match, i.e. Wi- = W. Recall that proposition 4 in the main paper gives lower bound for the probability of this event. We proceed by finding the joint distribution of A, W and T. fact,
A W T
. (o.
(Amm)) where E(W.T), MT (WWTTT)) =
[[AW] E[AT]
1
2w??
and Ewr was found earlier in (19). Then, the MMSE estimate is
[W] T
oeW + o o + oz 02
Å = F[A W. T = (..)) WT
To conclude, given Ti = tg and Wx = Wk. the reconstruction output by decoder is given by
ofwx + of o + of + 0700
g(wn tu)
Experiment parameters and further results. First, we briefly outline the parameters used for the experiment. The number of samples from the prior is N = 2 for all tests and the source, as mentioned in the main paper, is A NO 1). The conditional variance of the side in- formation given A is fixed at TTA = 0.5 throughout. We control the rate by varying Lmax- , mized over the encoder's target distribution by exploring different values of WIA selecting from Wia E {0.01,
considering Lmax ?2,, 23, 24, 25, 29). For each Lmax. the resulting distortion is mini-
0.006, 0.005, 0.003, 0.002, 0.0013 and choosing the best across 10 trials. The distortion incurred by the best configuration is then further evaluated on 10a trials. This procedure is carried out for K E {1, 2, 3, 4). where K is the number of decoders. Finally, the entire experiment is repeated 10 times and the results averaged to obtain those reported in table 10. The error bars show one standard error of the mean, calculated as in appendix D.I using all 10 trials.
Running one full repetition of the experiment takes around 4 hours when performing the calculations on a Nvidia Tesla T4 GPU with 16 GB of memory. The exact same procedure is used to generate results for the baseline scheme described in the main paper, and these are shown in table 11. We also show the value of VWJ that most often minimizes the distortion each case.
K
Lmux
WIA
Distortion (dB)
K
Lmax
OiA
Distortion (dB)
1
2
0.008
-9.7032 + 0.0193
2
0.005
18.3884 = 0.0163
2
0.010
-12.7474 + 0.0226
2
0.003
-21.6187 = 0.0164
23
0,010
-16.0116 # 0.0369
2
0.001
-25.0515 = 0.0213
24
0.003
-19.5491 + 0.0237
24
0.001
-28.5329 = 0.0128
2
0.002
23.4012 + 0.0132
2
0.001
-31.2575
0.0161
26
0,001
27.3477 + 0.0183
26
0.001
-33.1515 = 0.0108
2
2
0.010
15.2069 + 0.0148
4
2
0.005
20.6831 = 0.0176
2
0.005
18.3377 +:2 0.0164
2
0.001
-33.9118
0.0197
23
0.002
-21.7032 = 0.0101
23
0.001
-27.4313 = 0.0106
21
0.001
-25.3886 = 0.0104
2
0.001
-30.4379
0.0188
25
0.001
28.8619 1 0.0169
25
0.001
32.6616
0.0106
26
0.001
31.4737 1 0.0152
26
0.001
34.1082
0.0102
Table 10: Results using GLS with a Gaussian source.
41

---

Lmnax
OIA
Distortion (dB)
Lmax
o
Distortion (dB)
1
2
0,010
-9.7163 + 0.0195
3
2
0.010
- 13.8197 = 0.0368
2
0.008
-12.6968 + 0.0273
2
0,010
- -17.4640
0.0211
23
0.008
-16.0121 + 0.0153
23
0.010
-21.0096 = 0.0185
24
0.003
119.5518 + 0.0270
2
0.003
244.9966 = 0.0126
2
0.001
-23.3905 = 0.0105
2
0.001
28.66864 = 0.0123
26
0.001
-27.3705 = 0.0135
2
0.001
-32.0109 = 0.0156
2
2
0.010
12.5143 + 0.0356
4
2
0.010
14.6125
0.0272
2a
0.010
15.99916 + 0.0205
2
0.010
18.33550 = 0.0157
23
0.008
-19.4843 + 0.0137
2
0.008
-21.9300 = 0.0238
24
0.003
233.1495 + 0.0240
2
0.002
25.52669
0.0210
2
0.001
227.1988 1 0.0092
2
0.001
29.4994 = 0.0100
26
0.001
-30.7772 + 0.0169
2
0.001
-32.7141
0.0208
Table 11: Results using the baseline decoding scheme with Gaussian source.
D.4
Distributed image compression
We now give details on our distributed image compression experiments.
Neural network architectures. The following notations are used to denote the different layers in networks:
1. conv(a, b, c, d, e): convolution layer with input features, output features, kernel size c, stride d and input padding
2. upcouv(a, b, c, d, e, f): A transposed convolution layer with a input features, b output features, kernel size stride d, input padding and output padding f.
3. fc b): A fully-connected layer with input size a and output size
4. do(p): A dropout layer with dropout probability p.
5. cat(a, b): Concatenates two tensors of shapes and b.
The network layers are enumerated in table 12 and follow the network constructions in Phan et al. [36]. The encoder's s target distribution PWIA is taken to be a four-dimensional Gaussian with uncorrelated components, where the mean and variance of each component from an input image. More precisely, we let the image be a, the encoder network produces two embeddings (a) and e2(a), each in R Then, Pw (- a) (ee (a), (a)))), and we arbitrarily choose W ~ (0, 1) the marginal distribution, which is also the 3-VAE's prior. On the other hand, decoder &s is tasked with generating a reconstruction given the side information fy and an embedding we E Rd, which is selected depending on the message sent by the encoder. Rather than using the 14 x 14 side information image directly, we employ a projection network to extract a 1ength-128 feature vector e(l2)) before feeding this representation into the decoder network along with Wt to get à (k) s such that the distortion is minimized.
generated by the encoder network
K. The final estimate à is chosen from among the g( e(tx)) for 1 < k <
The estimator network is another important component our compression protocol, since it acts as proxy for Pwir- Recall from section 5.1 and its extension in appendix C that this distribution is used to select the index at the decoder; using this index, decoder & picks W. from the shared list of samples taken from the prior. In practice, the estimator network takes 14 X 14 side information image as its input and extracts 128-dimensional features, which are then concatenated with a sample 4 The final part of the network is classifies whether this joint embedding comes from the joint distribution Pw,r or the product of the marginals Pw Pr. Its output therefore stands in for Pwir-
Network loss functions. The 3- 3-VAE is trained using the rate-distontion loss function
LVAE(a, à) 3(a à) DKL (= a) || pw].
Note that since the marginal and conditional distributions Pw and РWIд A are both Gaussian, DKL has a closed form. The neural estimator uses the binary cross-entropy (BCE) loss function. If we let its output function of side information t and given sample be h(w, t), the loss is
Lestimator (w, BCE(h(W, t), 1 {w was sampled from Pw]r [t))
42

---

Input (1 x 28 28) conv 128, 1), ReLU
Input (132) [c(132, 512). ReLU
conv(128, 128, 3, 2, 1), ReLU
2
fc(132, 6272), ReLU
conv(128, 128, 3, 2, 1), ReLU fc(6272, 512), ReLU fe(512, 8)
3
upconv (128, 64, 3, 1), ReLU
4
upconv(64, 32, 3, 2. 1), (0.0.)) ReLU
5
upconv 1,3, 1, 0), tanh
(a) Encoder
(b) Decoder
0
Input (1 x 14 14) 30,
ReLU
2
conv(32, 6,, 1), ReLU
Input (1 14 x 14)
3
conv(64, 128, 1), ReLUU
conv(1, 32, 3, 1, 1), ReLU
4
fc(2048, 512), ReLU
2 conv 64, 3, 1), ReLU
5
fc(512, 128), cat(128, 4)
3
conv 128, 3, 2, 1), ReLU fc(2048, 512), ReLU fo(512, 128)
[c(132, 128). LeakyReLU
4
7
fe(128, 128). LeakyReLU
8
fe( (118, 128). LeakyReLU
(c) Projection
9
fc(128, 128), LeakyReLU
10
fc(128, 1), Sigmoid
(d) Estimator
Table 12: Neural network architectures.
where 1 is the indicator function.
Training and evaluation procedure. We use the MNIST dataset [24] with the usual train-test split of 60 000 and 10 000 images respectively and batch size 64. All models are trained for 30 epochs Nvidia Tesla T4 GPU with 16 GB of memory using the Adam optimizer [21]. The learning rate 10-3 and we set 31 0.9, 82 = 0.99. The encoder, decoder, projection and estimator networks 33 E {0.15, 0.35, 0.55, 0.75, 0.95] to cover a broad range of rate-distortion tradeoff's at the encoder side. Jointly training the networks takes around 45 minutes for each 3.
trained jointly in an end-to-end manner, and we create sets of models for
At test time, we vary Lmxx to control the rate, considering Lmax {22, 10:23,33 24, 2$, 2%). For each configuration, prior, and the VAE parameter 3 using a grid search where N E {2², 2,,29, 2 20.2" 2", 212 and 3 {0.15, 0.35, 0.55, 0.75, 0.95). The experiment is repeated 5 times and the results averaged, with the same procedure also being followed for the baseline scheme described in the main paper. We provide error bars showing appendix D.1 with the number of trials now being 5. Each instance of the full experiment takes approximately 6 hours run, and this is done for K E {1, 2, 3, 3)4.. Complete results are given in tables 13 and 14, where we also give the values of N and / that are most often optimal in each case.
additionally optimize over N, which is the number of samples from the
standard error of the mean, which is again calculated in
K
Lyaax
N
3
MSE
K
Lmmax
N
MSE
2²
2
0.15
0.1027 + 0.0002
3
2
29
0.15
0.0791 + 0.0000
2
2
0.15
0.0942
0.0001
2
27
0.15
0.0738
0.0002
2
2
0.15
0.0852 + 0.0002
24
27
0.15
0.0694 4: 0.0001
25
27
0.15
0.0766 0.0001
2a
27
0.15
0.0660
0.0001
2
27
0.15
0.0693 + 0.0002
26
2
0.35
0.0599 + 0.0002
2
2
29
0.15
0.0860 + 0.0001
4
2
27
0.15
0.0751 + 0.0001
23
27
0.15
0.0792 0.0001
23
27
0.15
0.0710
0.0001
24
27
0.15
0.0734 1 0.0001
27
0.15
0.0671 1: 0.0001
25
27
0.15
0.0687 0.0002
25
2
0.35
0.0635 1: 0.0001
28
27
0.35
0.0636 + 0.0002
28
28
0.35
0.0564
0.0001
Table 13: Results using GL.S for distributed image compression on MNIST.
More compression experiments on CIFAR-10. To show that GLS generalizes more complex image datasets, provide some further results on CIFAR-10 10 [23] under the same setup
43

---

K
Lywxx
N
3
MSE
K
LINAx
N
MSE
2²
27
0.15
0.1025 0.0001
3
2
27
0.15
0.0906 + 0.0002
2
0.15
0.0937 + 0.0002
2
0.15
0.0832 0.0003
2
2
0.15
0.0850 + 0.0002
24
2?
0.15
0.0757 + 0.0002
2
2
0.15
0.0764 0.0002
2
2
0.15
0.0704 0.0001
2"
2
0.15
0.0693 + 0.0002
2
2?
0.35
0.0653 + 0.0001
2
2
2
0.15
0.0941 + 0.0002
4
2
29
0.15
0.0886 + 0.0001
23
2
0.15
0.0865 0.0002
2
2
0.15
0.0815 0.0001
24
27
0.15
0.0783 + 0.0002
24
27
0.15
0.0747 + 0.0002
25
2
0.15
0.0718 0.0002
23
2
0.15
0.0694 0.0002
2
0.15
0.0669 + 0.0001
2
0.35
0.0639 + 0.0002
Table 14: Results using the baseline decoding scheme for distributed image compression on MNIST.
MNIST experiments. The side information samples are now x patches uniformly selected from the left half of the 3-channel, 32 x 32 image. Results for the MSE distortion are shown in tables 15 and 16, where we vary both K and Lmax- Note that the baseline and GLS compression schemes are functionally identical for K 1, but as is the
MNIST, GLS offers gains for K > 1. For each K, Lmax pair, setting N 2 and 3 = 0.15 gave the strongest results.
K
Lmax
N
8
MSE
K
Lmax
MSE
27
0.15
0.1119
0.0003
3
2
0.15
0.0839
0.0001
2
2
0.15
0.1054 = 0.0002
2
27
0.15
0.0778 + 0.0003
24
27
0.15
0.0963
0.0001
24
27
0.15
0.0710
0.0001
2
2
0.15
0.0846 + 0.0003
2
27
0.15
0.0641 + 0.0000
26
27
0.15
0.0710 0.0001
26
27
0.15
0.0590 0.0001
22
27
0.15
0.0925 0.0001
2
27
0.15
0.0788
0.0001
23
2
0.15
0,0860 + 0.0002
2
27
0.15
0.0733 + 0.0001
24
2
0.15
0.0787 0.0003
24
27
0.15
0.0673 0.0002
27
0.15
0.0698 + 0.0003
27
0.15
0.0618 + 0.0001
26
27
0.15
0.0616 0.0002
26
27
0.15
0.0579
0.0001
Table 15: Results using GLS for distributed image compression CIFAR-IO.
K
Lmux
N
8
MSE
K
Lmax
N
MSE
2
2
0.15
0.1113 + 0.0001
3
2
27
0.15
0.0982 + 0.0002
23
27
0.15
0.1048
0.0002
2
27
0.15
0.0914
0.0002
27
0.15
0.0959 1 0.0003
27
0.15
0.0831 1: 0.0002
2
27
0.15
0.0846 + 0.0003
2
27
0.15
0.0734 + 0.0004
26
27
0.15
0.0002 0.0710
26
27
0.15
0.0001 0.0639
2
27
0.15
0.1019
0.0003
4
2
0.15
0.0956 0.0002
23
27
0.15
0.0958 + 0.0002
23
27
0.15
0.0888 + 0.0002
24
27
0.15
0.0867 0.0003
24
27
0.15
0.0812 0.0001
27
27
0.15
0.0767 +: 0.0001
25
27
0.15
0.0718 + 0.0003
28
27
0.15
0.0659 0.0002
28
27
0.15
0.0629 0.0001
Table 16: Results using the baseline decoding scheme for distributed image compression on CIFAR-10 10.
44


Reviews:
[{"review_id": "JV93XUufqL", "reviewer": "Reviewer_W4vi", "summary": "This paper proposes Gumbel-max List Sampling (GLS), a method for coupling multiple samples from one distribution with a target sample from another, without requiring communication. It extends the classical Gumbel-max trick to improve the probability that at least one sample matches the target. The authors prove a theoretical lower bound on the match probability (List Matching Lemma), and apply GLS to two tasks: drafter-invariant speculative decoding for language models and distributed lossy compression with decoder-specific side information. GLS achieves comparable performance to baselines while offering better structural simplicity and system compatibility.", "questions": "- The authors are encouraged to include experimental results that illustrate how the actual matching probability scales with the number of samples \\(K\\), and how closely it aligns with the theoretical bound provided by the List Matching Lemma. This would significantly strengthen the empirical foundation of their core theoretical claim.\n\n- A discussion of the likelihood that different draft models (or configurations) generate the same token sequences, along with an empirical analysis of whether such sequences lead to consistent decoding outputs, would help clarify the practical robustness of the proposed draft invariance property.\n\n- The paper should clarify whether the sampling procedure for the target token \\(Y\\) is compatible with deployment in distributed or asynchronous systems. A discussion of how GLS can be implemented across heterogeneous devices without violating its assumptions would enhance the practical relevance of the method.\n\n- Since GLS relies on shared floating-point computations (e.g., \\(-\\log U\\), division, and \\(\\arg\\min\\)), it remains unclear whether decoding outputs are fully reproducible across devices with different hardware or numerical precision. The authors are encouraged to discuss how such numerical variation might affect decoding consistency in practice.\n\n\n- I have a question about the determinism and decoding consistency of GLS in practice. Since the GLS procedure relies on floating-point operations, it’s possible that different devices may produce slightly different results even when using the same random seed. Have the authors considered the impact of hardware-level numerical differences on decoding consistency? If GLS is to be used in distributed or heterogeneous environments, this could affect reproducibility or correctness of the decoding outputs.", "limitations": "While the paper is technically well-executed and does not raise immediate ethical concerns, the authors do not explicitly address the limitations of their work. Given that the proposed method is designed for large language model inference and distributed compression, it would be appropriate to discuss certain assumptions, such as the need for perfectly shared randomness and consistent numerical behavior across devices, which may limit practical deployment. The authors are encouraged to include a brief discussion acknowledging these limitations and potential risks to support responsible and transparent adoption of their approach.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The authors propose a clean generalization of Gumbel-max sampling and back it with a nontrivial theoretical guarantee (List Matching Lemma) on the matching probability. The proposed GLS method is simple to implement, and its probabilistic correctness is rigorously proven. Experiments are conducted on both language modeling and compression tasks, demonstrating reasonable practical viability.\n\n- The method addresses practically relevant problems in speculative decoding and distributed compression, both of which are increasingly important in large-scale, resource-constrained, or distributed systems. The approach provides system-level benefits like deterministic decoding and model-agnostic draft compatibility.\n\n- The paper is clearly written and well-structured. The authors concisely explain the algorithm, provide motivating examples, and include relevant background. The connection between the theoretical core and practical applications is explicitly laid out.\n\n### Weakness\n\n- The paper centers on improving match probability via List Matching Lemma, but it does not report actual acceptance rates or how they scale with the number of proposals K. This weakens the empirical support for its theoretical contribution.\n\n- Although the method is framed as \"communication-free\", the target sample Y is computed via a minimum over all proposal-side Gumbel variables, meaning it is structurally coupled with all proposal samples. This may challenge the interpretation of independence or decoupled sampling in practical implementations.\n\n- The drafter-invariance claim only holds if the draft token sequences are fixed. In practice, changing the draft model even slightly can alter the token sequence, breaking this invariance. No ablation is conducted to examine the robustness of this property.\n\n- The speculative decoding experiments report throughput (tokens/sec), but do not assess generation quality, token correctness, or how many tokens are accepted without fallback. This limits understanding of the method’s true effectiveness. Also, the distributed compression experiments evaluate distortion but do not measure actual bitrates or code length, leaving the full rate-distortion trade-off unquantified.", "was_revised": true, "final_justification": "The paper introduces a technically solid and elegant generalization of the Gumbel-max trick with a rigorous theoretical guarantee (List Matching Lemma), and demonstrates its practical relevance in speculative decoding and distributed compression. The rebuttal convincingly addressed key concerns, providing additional empirical validation of matching probabilities and an ablation on drafter-invariance. While practical deployment limitations (e.g., floating-point consistency, shared randomness) remain, these are not unique to GLS but apply broadly to Gumbel-max–based methods. Overall, the combination of theoretical contribution, simplicity, and practical applicability makes this a valuable addition to the literature. I recommend acceptance.", "rebuttal": "Thank you for your insightful feedback on our paper. We are glad that you liked the simplicity and practical relevance of GLS and we found your comments about deployment to real-world distributed systems especially thought-provoking. Please find your concerns addressed below.\n\n1. **Empirical matching probability, comparison to the LML bound and scaling with K:**\n   Thank you for your suggestion, which we agree will strengthen our main claims around the LML. We have provided further results comparing the empirical average matching probability (using target and proposal distributions for the next token seen during speculative decoding) to our lower bound in Thm. 1, testing $K = 2, 4, 6, 8$.\n   The new results confirm that the matching probability and lower bound increase monotonically with $K$, and the bound is quite close to the true probability in practice.\n\n   |Dataset|$K = 2$|$K = 2$, Eq. 3|$K = 4$|$K = 4$, Eq. 3|$K = 6$|$K = 6$, Eq. 3|$K = 8$|$K = 8$, Eq. 3|\n   |-|-|-|-|-|-|-|-|-|\n   |GSM8K|0.949|0.936|0.972|0.956|0.979|0.965|0.982|0.971|\n   |HumanEval|0.919|0.903|0.950|0.931|0.962|0.945|0.971|0.953|\n   |NaturalReasoning|0.862|0.844|0.905|0.884|0.926|0.904|0.937|0.916|\n\n   For completeness, we also show below the same empirical matching probabilities for SpecInfer (SI) and SpecTr (ST). Our approach performs similarly to or in many cases better than these methods, even though they do not offer any drafter-invariance property.\n\n   |Dataset|$K = 2$, SI|$K = 2$, ST|$K = 4$, SI|$K = 4$, ST|$K = 6$, SI|$K = 6$, ST|$K = 8$, SI|$K = 8$, ST|\n   |-|-|-|-|-|-|-|-|-|\n   |GSM8K|0.948|0.927|0.969|0.938|0.976|0.944|0.981|0.948|\n   |HumanEval|0.919|0.891|0.948|0.908|0.960|0.916|0.967|0.922|\n   |NaturalReasoning|0.864|0.837|0.904|0.864|0.921|0.878|0.932|0.887|\n\n2. **Clarification of our \"communication-free\" claim:**\n   We stress that \"communication-free\" in the context of both our paper and Daliri et al. [1] does *not* mean that $Y$ is independent of the proposal samples. Indeed, the coupling of these variables is exactly what improves the matching probability beyond naïve independent sampling. Rather, our \"communication-free\" claim reflects the fact that $Y$ is selected *without any knowledge of the proposal distribution* $p_X$ and vice versa.\n\n3. **Ablation and empirical analysis of drafter-invariance:**\n   Thank you for raising the need for more evidence around the robustness and practical importance of our conditional drafter-invariance property. As you point out, the output is no longer invariant if the input sequences change. Nevertheless, we find that adopting drafter-invariant speculative decoding significantly improves decoding consistency in practice, which we show through a new ablation study below. Moreover, in appendix B we demonstrate a slightly modified scheme that provides what we call *strong drafter-invariance*, which provably guarantees perfect decoding consistency even if the proposal samples change. However, this alternative scheme significantly reduces the block efficiency, as seen in Tabs. 3 and 4.\n\n   To quantify the effect of drafter-invariance on decoding consistency, we run 200 prompts from three different datasets using $K = 2$ drafts. Each prompt is run twice using the same random seed. The drafts are i.i.d., but the drafter model temperature is changed from 1.0 in the first run to 0.5 in the second. We compute ROUGE scores [2] to measure the similarity of the two output sequences; perfect decoding consistency would be a score of 1.0 for all of the ROUGE-1, ROUGE-2 and ROUGE-L metrics. We set $L = 4$ and average over 4 random seeds. Our conditionally invariant scheme gives higher similarity scores in each case compared to the non-invariant SpecInfer baseline, confirming that drafter-invariance provides more consistent outputs when faced with changes to the draft model, even though our notion is not strong enough to guarantee that the outputs always remain exactly the same.\n\n   |Dataset|Decoding Algorithm|ROUGE-1|ROUGE-2|ROUGE-L|\n   |-|-|-|-|-|\n   |GSM8K|SpecInfer|0.737±0.004|0.592±0.007|0.647±0.008|\n   ||Ours|0.801±0.005|0.701±0.011|0.745±0.009|\n   |HumanEval|SpecInfer|0.656±0.003|0.466±0.006|0.545±0.005|\n   ||Ours|0.710±0.001|0.555±0.003|0.628±0.002|\n   |MBPP|SpecInfer|0.676±0.004|0.497±0.003|0.580±0.004|\n   ||Ours|0.728±0.006|0.588±0.011|0.659±0.010|\n\n4. **Clarification on generation quality, number of accepted tokens, bitrates and other experimental observations:**\n   Thank you for pointing out several details about our experimental results that deserve clarification. We address these separately below:\n\n   - *Generation quality and token correctness:*\n     Speculative decoding, including the original single-draft formulation [3] and multi-draft generalizations [4], comes with an *exact sampling guarantee*, as does our algorithm (Prop. 1). The probability distribution over the output tokens is unchanged from the target $\\mathcal{M}_b$, and the output is thus statistically indistinguishable from what would be obtained using standard autoregressive decoding with $\\mathcal{M}_b$. Hence, our method *provably* incurs no change in generation quality or token correctness, which is a property shared by existing speculative decoding algorithms.\n   - *Number of tokens accepted without fallback:*\n     This is the same as the block efficiency minus one, which we report in Tabs. 1 and 2 in the main paper and Tabs. 3 and 4 in the supplementary.\n   - *Bitrate and code length:*\n      We apologize that these quantities were not made clear enough in the paper. In our compression scheme, the only communication from the encoder to the decoder is the fixed-length message $M$, which has code length $\\log_2(L_{\\mathrm{max}})$. This is exactly the number of bits per transmission i.e. the rate, which is reported on the $x$-axis of our rate-distortion plots.\n\n5. **Considerations and limitations for deployment on distributed or heterogeneous systems:** Thank you for your interest in the real-world deployment of our algorithm. We present our response in two parts, and will include a discussion of these issues in a revised version of the paper:\n\n   - *Availability of shared random numbers:*\n      As you mention, our algorithm assumes that both parties (i.e. encoder and decoder, or drafter and target) have access to a source of common random numbers. In practice, this is easily achieved by sharing or agreeing upon a random seed before beginning the procedure [8]. Since the seed is typically a single integer, the communication cost is small and is incurred only once, making implementation on distributed systems very much possible.\n   - *Consistency of floating-point operations:*\n      We would like to first point out that most speculative decoding applications currently use single-GPU or homogeneous multi-GPU architectures, where we can assume identical floating-point behavior [5,6]. While extensions to heterogeneous environments might make for interesting future work, we did not explicitly consider such settings in our paper and instead chose to limit our attention to the more common single-GPU case. On the other hand, our compression application is more likely to see deployment in distributed and/or heterogeneous systems. Nevertheless, the encoder and decoders can often be assumed to share the same floating-point behavior, as for example enforced by the IEEE 754 standard.\n\n     If this is not the case, you are right to point out that floating-point errors may cause the behavior of GLS to differ from that predicted by the theory. Nevertheless, given the popularity of Gumbel-max sampling in machine learning [7], there are common \"tricks\" to improve numerical stability which we adopt in our code. In particular, unnormalized log probabilities, read directly from the output layer of a neural network, are used instead of $p_X$ and $q_Y$ and the selection step becomes $Y = \\arg\\max_{1 \\leq i \\leq N} [\\ln q_i + \\max_{1 \\leq k \\leq K} [-\\ln(-\\ln(U_i^{(k)}))]]$, $X^{(k)} = \\arg\\max_{1 \\leq i \\leq N} [\\ln p_i - \\ln(-\\ln(U_i^{(k)}))]$ [1]. This removes floating-point division and the need to compute softmax probabilities, reducing the impact of floating-point errors.\n\n[1] M. Daliri, C. Musco, and A. T. Suresh. Coupling without communication and drafter-invariant speculative decoding, 2025. ArXiv: 2408.07978.\n\n[2] C. Y. Lin. ROUGE: A package for automatic evaluation of summaries. *Text Summarization Branches Out*, 2004.\n\n[3] Y. Leviathan, M. Kalman, and Y. Matias. Fast inference from transformers via speculative decoding. *ICML 2023*.\n\n[4] A. J. Khisti, M. R. Ebrahimi, et al. Multi draft speculative sampling: canonical decomposition and theoretical limits. *ICLR 2025*.\n\n[5] Y. Li, F. Wei, C. Zhang, and H. Zhang. EAGLE: speculative sampling requires rethinking feature uncertainty. *ICML 2024*.\n\n[6] T. Cai, Y. Li, Z. Geng, H. Peng, and J. D. Lee. Medusa: simple LLM inference acceleration framework with multiple decoding heads. *ICML 2024*.\n\n[7] W. Kool, H. Van Hoof, and M. Welling. Stochastic beams and where to find them: the Gumbel-top-k trick for sampling sequences without replacement. *ICML 2019*.\n\n[8] L. Theis and N. Yosri. Algorithms for the communication of samples. *ICML 2022*."}, {"review_id": "UAUx785fjr", "reviewer": "Reviewer_Wfqz", "summary": "This paper tackles the problem of coordinated sampling by introducing a list-based extension of the classic Gumbel-max coupling. The authors propose Gumbel-max List Sampling, which allows one party to generate K proposals and achieve a higher acceptance probability. They establish a List Matching Lemma that lower-bounds this probability and demonstrate two key applications: 1. A multi-draft speculative decoding scheme for large language models (LLMs) that is simple to implement, competitive with SpecTr and SpecInfer. 2. A distributed lossy compression mechanism with independent side information at K decoders, showing rate–distortion gains on synthetic Gaussian sources and MNIST images.", "questions": "1.\tOverhead Analysis: How does the wall-clock latency and memory usage of multi-draft speculative decoding scale with K in practice, especially for large transformer-based LLMs?\n2.\tChoice of K: Do the authors have guidelines or heuristics for selecting the number of proposals K to balance acceptance probability gains against computational cost?\n3.\tGeneralization to Correlated Side Information: How would the compression scheme adapt if decoders’ side information are not independent but partially correlated?\n4.\tAblation on Drafter-Invariance: Can the authors quantify the practical impact of drafter-invariance on output quality and convergence, compared to non-invariant multi-draft baselines?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1.\tNovel Theoretical Framework: GLS generalizes single-proposal Gumbel-max coupling to the multi-proposal setting, with a clear algorithm (Algorithm 1) and a rigorous lower bound on acceptance (Theorem 1). \n2.\tFormal Guarantees: Introduction of List Matching Lemma and a token-level acceptance bound for speculative decoding gives the scheme provable reliability properties absent in prior heuristic approaches. \n3.\tBroad Applicability: Beyond decoding acceleration, GLS is applied to distributed lossy compression, demonstrating versatility across machine-learning and information-theory domains. \n\nWeaknesses:\n\n1.\tScalability of K: While acceptance probability grows with the number of proposals K, the computational and memory overhead of generating and verifying multiple drafts is not deeply analyzed.\n2.\tContinuous Distributions: The extension to continuous distributions via importance sampling is only sketched. Empirical validation on continuous tasks is absent.\n3.\tCompression Experiments: Lossy compression results are limited to synthetic Gaussians and MNIST; it remains unclear how GLS-based compression performs on colored high-resolution or more complex datasets (e.g., CIFAR-10 or ImageNet).\n4.\tSide-Information Assumptions: The distributed compression model assumes independent side information across decoders. Real-world scenarios often involve correlated side information, which may degrade performance.", "was_revised": true, "final_justification": "This is a technically solid paper introducing Gumbel-max List Sampling, a novel extension of the Gumbel-max coupling with formal guarantees and broad applicability. The theoretical contributions are clear, and the applications to speculative decoding and distributed lossy compression are well-motivated and convincingly demonstrated. Following the rebuttal, the authors have properly addressed my concerns. I recommend acceptance as my final rating.", "rebuttal": "Thank you for taking the time to review our paper.  We greatly appreciate your suggestions on how to improve our work and are pleased that you found the theoretical framework of GLS novel and rigorous, and the proposed applications relevant and interesting. We have addressed your comments below:\n\n1. **Practical scalability with K and overhead analysis:**\n   As you point out, increasing $K$ boosts the acceptance probability but demands more resources, especially when using large LLMs. The memory consumption and algorithmic complexity both increase linearly with $K$, since $K$ individual drafts must be generated, stored and verified. However, multi-draft speculative decoding leverages the fact that these operations can be done in parallel for all $K$ drafts simultaneously [1]. Therefore, increasing $K$ decreases the wall-clock latency in the real world so long as there are spare memory and parallel compute resources available, which is usually true for non-batched inference on a single GPU.\n\n   When $K$ is made too large, memory and compute become over-subscribed and latency can increase. Our results in Tab. 3 in the supplementary give empirical evidence of this phenomenon. Increasing $K$ from 2 to 6 gives consistent wall-clock speedups, yet the token rate sometimes decreases for certain datasets when going further to $K = 8$, as the increased overhead starts to outweigh the benefits of a higher acceptance probability.\n\n2. **Guidelines on choosing K :**\n   As mentioned in our previous response, the value of $K$ must carefully balance gains in the acceptance probability against limits on available compute and memory resources. Therefore, the choice is necessarily hardware-dependent.\n   Nevertheless, our results in table 3 in the supplementary indicate that $K = 6$ or 8 is usually a good choice to maximize the token rate. Prior works on multi-draft speculative decoding come to similar conclusions about the best choice of $K$ [1,2,3], suggesting that our recommendation should generalize to a range of current hardware platforms.\n\n3. **Applicability to correlated side information:**\n   While our theoretical discussion focuses on (conditionally) independent side information for the sake of simplicity and tractability, on the practical side our MNIST experiment *does* deal with partially correlated side information, providing empirical evidence that GLS works well in this case. More precisely, the $14 \\times 14$ slices taken from the left-hand side of the image are often overlapping and therefore not independent. Nevertheless, the compression performance holds up well, with the distortion decreasing consistently in both the rate and number of side information samples as seen in Fig. 4.\n\n4. **Clarification on the extension to continuous distributions:**\n   Thank you for raising this important point. While the main paper provides only a sketch of the extension to continuous distributions, a more complete description and mathematical analysis is given in Appendix C (pp. 30--32). Regarding empirical validation, we would like to emphasize that the Gaussian source and MNIST experiments are *both* continuous tasks --- the information sources are continuous-valued in both cases, validating that our extension to continuous distributions via importance sampling works well in practice.\n\n5. **Additional compression experiments:**\n   To show that GLS generalizes to more complex datasets, we have completed a new image compression experiment on CIFAR-10 using the same basic setup as our MNIST experiment. The side information samples are now $16\\times16$ patches randomly selected from the left half of the (3-channel, $32 \\times 32$) image. Please find the results in the table below, showing the MSE distortion. We want to emphasize that the baseline and GLS methods are functionally identical for $K = 1$, but as is the case on MNIST, GLS offers gains for $K > 1$.\n\n   |Rate (bits)|$K = 1$, GLS|$K = 1$, BL|$K = 2$, GLS|$K = 2$, BL|$K = 3$, GLS| $K = 3$, BL|$K = 4$, GLS|$K = 4$, BL|\n   |-|-|-|-|-|-|-|-|-|\n   |2|0.1119±0.0003|0.1113±0.0001|0.0925±0.0001|0.1019±0.0003|0.0839±0.0001|0.0982±0.0002|0.0788±0.0001|0.0956±0.0002|\n   |3|0.1054±0.0002|0.1048±0.0002|0.0860±0.0002|0.0958±0.0002|0.0778±0.0003|0.0914±0.0002|0.0733±0.0001|0.0888±0.0002|\n   |4|0.0963±0.0001|0.0959±0.0003|0.0787±0.0003|0.0867±0.0003|0.0710±0.0001|0.0831±0.0002|0.0673±0.0002|0.0812±0.0001|\n   |5|0.0846±0.0003|0.0846±0.0003|0.0698±0.0003|0.0767±0.0001|0.0641±0.0000|0.0734±0.0003|0.0618±0.0001|0.0718±0.0003|\n   |6|0.0710±0.0001|0.0710±0.0002|0.0616±0.0002|0.0659±0.0002|0.0590±0.0001|0.0639±0.0001|0.0579±0.0001|0.0629±0.0001|\n   \n6. **Ablation on drafter-invariance:**\n   Thank you for raising this important point. We agree that it is important to provide experimental results showing the real-world impact of drafter-invariance, in particular our claim that it reduces the sensitivity of the generated outputs to changes affecting the draft model.\n\n   In response, we have provided a new ablation study that examines this question and shows that our approach promotes decoding consistency when the draft model changes, as measured by ROUGE scores [4], compared to non-invariant multi-draft speculative decoding baselines. Please find details of the new experiments and tabulated results in item 3 of our response to reviewer W4vi. The table is also repeated below for your convenience.\n\n   |Dataset|Decoding Algorithm|ROUGE-1|ROUGE-2|ROUGE-L|\n   |-|-|-|-|-|\n   |GSM8K|SpecInfer|0.737±0.004|0.592±0.007|0.647±0.008|\n   ||Ours|0.801±0.005|0.701±0.011|0.745±0.009|\n   |HumanEval|SpecInfer|0.656±0.003|0.466±0.006|0.545±0.005|\n   ||Ours|0.710±0.001|0.555±0.003|0.628±0.002|\n   |MBPP|SpecInfer|0.676±0.004|0.497±0.003|0.580±0.004|\n   ||Ours|0.728±0.006|0.588±0.011|0.659±0.010|\n\n   While our ablation study provides a more rigorous way to examine the real-world impact of drafter-invariance, we also give a concrete example from GSM8K where non-invariant speculative decoding causes the output to diverge significantly from the original after changing the draft model but keeping the same random seed. For this experiment we modify the draft model by decreasing its temperature. We stress that all forms of speculative decoding preserve the output distribution exactly; therefore, it is not the *quality* that is degraded, but rather the *stability* or *consistency* of the outputs. In this particular example, our scheme achieves perfect consistency between the two trials; we do not guarantee this in general, but the ROUGE scores in our ablation study demonstrate that we achieve better consistency than existing schemes on average.\n\n   - *SpecInfer (not invariant), draft temp. 1.0:*\n      ```\n      To determine how much Weng earned for babysitting for 50 minutes, we first need to convert the time from minutes to hours. We know that there are 60 minutes in an hour, so we can convert 50 minutes to hours by dividing 50 by 60:\n      \\[\n      \\text{Time in hours} = \\frac{50}{60} = \\frac{5}{6} \\text{ hours}\n      \\]\n      Next, we calculate the earnings by multiplying the time in hours by her hourly rate of $12:\n      \\[\n      \\text{Earnings} = 12 \\times \\\n      ```\n   - *SpecInfer (not invariant), draft temp. 0.5:*\n      ```\n      To determine how much Weng earned for her 50 minutes of babysitting, we need to follow these steps:\n      1. Identify Weng's hourly wage.\n      2. Convert the babysitting time from minutes to hours.\n      3. Calculate the earnings based on the time worked.\n      First, Weng's hourly wage is $12. Since she babysat for 50 minutes, we need to convert 50 minutes into hours. There are 60 minutes in an hour, so we can convert 50 minutes to hours by dividing 50 by 60:\n      \\[ \\text{Time in hours} = \\frac{\n      ```\n   - *Our scheme (invariant), draft temp 1.0:*\n      ```\n      To determine how much Weng earned for 50 minutes of babysitting at a rate of $12 per hour, we need to follow these steps:\n      1. Convert the time from minutes to hours.\n      2. Multiply the time in hours by the hourly rate.\n      First, we convert 50 minutes to hours. Since there are 60 minutes in an hour, we divide 50 by 60:\n      \\[\n      \\frac{50}{60} = \\frac{5}{6} \\text{ hours}\n      \\]\n     Next, we multiply the time in hours by the hourly rate of $12:\n      ```\n   - *Our scheme (invariant), draft temp. 0.5:*\n      ```\n      To determine how much Weng earned for 50 minutes of babysitting at a rate of $12 per hour, we need to follow these steps:\n      1. Convert the time from minutes to hours.\n      2. Multiply the time in hours by the hourly rate.\n      First, we convert 50 minutes to hours. Since there are 60 minutes in an hour, we divide 50 by 60:\n      \\[\n      \\frac{50}{60} = \\frac{5}{6} \\text{ hours}\n      \\]\n      Next, we multiply the time in hours by the hourly rate of $12:\n      ```\n\n[1] Z. Sun, A. T. Suresh, et al. SpecTr: fast speculative decoding via optimal transport. *NeurIPS 2023*.\n\n[2] W. Jeon, M. Gagrani, R. Goel, J. Park, M. Lee, and C. Lott. Recursive speculative decoding: accelerating LLM inference via sampling without replacement, 2024. ArXiv: 2402.14160.\n\n[3] X. Miao, G. Oliaro, et al. Specinfer: accelerating large language model serving with tree-based speculative inference and verification. *ASPLOS 2024*.\n\n[4] C. Y. Lin. ROUGE: A package for automatic evaluation of summaries. *Text Summarization Branches Out*, 2004."}, {"review_id": "BAWN5vgwjk", "reviewer": "Reviewer_fX9A", "summary": "The paper presents Gumbel-max List Sampling (GLS), an extension of the single-draft Gumbel-max coupling of Daliri et al. to the case of $K$ drafts drawn from a “drafter” distribution $p$.\nBy sharing a structured pool of exponential noise across all drafts and the target draw from $q$, GLS maintains the correct marginals while boosting the probability that at least one draft matches the target.\nThe authors provide explicit lower bounds on the matching probability, which increase with $K$.\nGLS is then applied to (i) multi-draft speculative decoding and (ii) single-encoder multi-decoder lossy compression, with supporting experiments in both settings.", "questions": "Q1: How does the matching probability bound behave in practice for different values of $K$?\nDo we know anything about the tightness of the bound?\n\nQ2: How was $K$ chosen in the experiments, and did you observe any practical trade-offs or patterns when varying $K$?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper is very well presented. Theoretical contributions are clearly motivated and placed in the context of related work. The proposed algorithm is simple and elegant, which is a strength.\n\nWeaknesses:\n\nExperimental evaluation is limited. While the applications are interesting, they are presented more as proofs of concept rather than full empirical studies.\nThere is limited discussion or analysis of the practical behaviour of GLS with respect to the number of drafts $K$, and other practical considerations.\nTheorem 1 provides a useful, monotone lower bound on the match probability, but the paper does not analyse the tightness of this bound for $K>1$.", "was_revised": true, "final_justification": "All my concerns were addressed. I remain at my initial assessment that I believe this is solid work that should be accepted.", "rebuttal": "Thank you for your thoughtful comments and feedback on our work. We are glad that you appreciated the simplicity of the GLS algorithm and the strength of our theoretical contributions. Please find our response to your concerns below:\n\n1. **Behavior of the bound in practice for different values of K:**\n   We agree that computing the bound for different values of $K$ and comparing against the matching probabilities observed during experiments would strengthen our theoretical claims about the LML. To this end, we have used the target and proposal distributions for the next token encountered during speculative decoding experiments to compute the average empirical matching probability and its lower bound in Thm. 1 (i.e. Eq. 3). A table of results can be found in item 1 of our response to reviewer W4vi, where we test $K = 2, 4, 6, 8$. The table is also repeated below for your convenience.\n   The new results verify that our scheme's matching probability and the lower bound in Thm. 1 both increase with $K$, and the bound is quite close to the true probability in practice.\n\n   |Dataset|$K = 2$|$K = 2$, Eq. 3|$K = 4$|$K = 4$, Eq. 3|$K = 6$|$K = 6$, Eq. 3|$K = 8$|$K = 8$, Eq. 3|\n   |-|-|-|-|-|-|-|-|-|\n   |GSM8K|0.949|0.936|0.972|0.956|0.979|0.965|0.982|0.971|\n   |HumanEval|0.919|0.903|0.950|0.931|0.962|0.945|0.971|0.953|\n   |NaturalReasoning|0.862|0.844|0.905|0.884|0.926|0.904|0.937|0.916|\n\n   Below, we also give the corresponding matching probabilities for SpecInfer (SI) and SpecTr (ST), computed over the same next-token distributions. Our scheme's matching probability is similar to and in many cases exceeds that of SpecInfer and SpecTr, even though they do not offer any drafter-invariance property.\n\n   |Dataset|$K = 2$, SI|$K = 2$, ST|$K = 4$, SI|$K = 4$, ST|$K = 6$, SI|$K = 6$, ST|$K = 8$, SI|$K = 8$, ST|\n   |-|-|-|-|-|-|-|-|-|\n   |GSM8K|0.948|0.927|0.969|0.938|0.976|0.944|0.981|0.948|\n   |HumanEval|0.919|0.891|0.948|0.908|0.960|0.916|0.967|0.922|\n   |NaturalReasoning|0.864|0.837|0.904|0.864|0.921|0.878|0.932|0.887|\n\n2. **Tightness of the LML bound:**\n   Our results in the table referenced above show that, in practice, the bound in Thm. 1 is quite close to the true matching probability for commonly encountered distributions such as those seen during LLM inference and draft verification. In response to reviewers' interest, we have also obtained some new results about the bound's theoretical tightness. In particular, we outline several situations below where our bound is provably tight for any $K$:\n   \n   - In a pessimistic scenario where $p_X$ has all its mass on one element, the LML bound (Eq. 3) is tight regardless of $K$ and $q_Y$.\n   - In a best-case scenario where $p_i = q_i$ for all $i$, the LML bound and the true matching probability of GLS both equal 1.\n   - As you already alluded to in your comments, Eq. 3 yields the exact matching probability for $K = 1$.\n\n   We will include the required proofs in a revised version of the paper. Please note that the second, conditional version of the bound in Eq. 4 is a significant relaxation that is provided mostly to allow for a more intuitive expression when we write down the coding theorem of Prop. 4. It is generally quite loose, but lets us intuit the limiting behavior for large $K$. When tight bounds are needed, we advocate for the use of Eq. 3 instead, which also admits a conditional form by removing the outer summation and dividing by $q_j$.\n\n3. **How K was chosen in the experiments:**\n   For the speculative decoding experiments, we tried $K = 2, 4, 6, 8$ --- similar values between 2 and 8 have commonly been used in prior work on multi-draft speculative decoding [1,2,3]. From Tab. 3 in the supplementary, either $K = 6$ or 8 tend to give the best performance in practice, depending on the dataset. This is again broadly consistent with prior works [1,2,3], which often find values of $K$ between 6 and 8 perform best.\n   We use $K = 8$ for Tab. 2 in the main paper as it best shows the relative performance of the different methods.\n   When we vary the draft temperature, we restrict ourselves to $K = 2$ to better isolate the effects of the temperature mismatch, following the basic experimental setup from Khisti et al. [4].\n\n   In the distributed compression experiments, $K$ is equal to the number of side information realizations and hence the number of decoders. Typically we do not have control over this parameter in practice, because the number of available side information samples is fixed.\n   With this in mind, we simply chose values of $K$ that would provide a representative spread of rate-distortion curves in Figs. 2d and 4.\n\n4. **Practical trade-offs when varying K in applications of GLS:**\n   In speculative decoding, the choice of $K$ is a careful trade-off between the benefits of a higher acceptance probability and the additional overhead required to generate and verify more drafts in parallel [1]. We analyze this trade-off further in item 1 of our response to reviewer Wfqz. There, we conclude that increasing $K$ is beneficial for the token rate while there are still spare memory and parallel compute resources available, but the token rate starts decreasing if $K$ is set too high and these resources become over-subscribed. On our test hardware, this starts to occur near or above $K = 8$ in many cases.\n\n   As mentioned in item 3 above, we would typically have less control over $K$ in distributed compression settings, yet we can still make some interesting observations. As suggested by Prop. 4, the error probability and thus rate-distortion performance improves monotonically as $K$ increases. Meanwhile, the computational cost of running the scheme increases linearly with $K$ as the number of decoders increases. This was not a practical concern in our experiments, since the decoder networks are lightweight and moreover can be run independently in parallel, reducing the total decoder-side latency.\n\n[1] Z. Sun, A. T. Suresh, et al. SpecTr: fast speculative decoding via optimal transport. *NeurIPS 2023*.\n\n[2] W. Jeon, M. Gagrani, R. Goel, J. Park, M. Lee, and C. Lott. Recursive speculative decoding: accelerating LLM inference via sampling without replacement, 2024. ArXiv: 2402.14160.\n\n[3] X. Miao, G. Oliaro, et al. Specinfer: accelerating large language model serving with tree-based speculative inference and verification. *ASPLOS 2024*.\n\n[4] A. J. Khisti, M. R. Ebrahimi, et al. Multi draft speculative sampling: canonical decomposition and theoretical limits. *ICLR 2025*."}, {"review_id": "BmiWzCoqYU", "reviewer": "Reviewer_s4tY", "summary": "This paper introduces Gumbel-max List Sampling (GLS), a new algorithmic framework for sampling from discrete distributions when one party samples a list of size K, and a match is declared if any of the K samples equals another sample drawn from a target distribution. The authors provide a theoretical lower bound on the matching probability, named the List Matching Lemma (LML), which extends classical coupling bounds.\nTwo primary applications are discussed:\nMulti-draft Speculative Decoding for LLMs: The paper proposes a drafter-invariant approach based on GLS, outperforming or matching baselines like SpecInfer and SpecTr in various decoding settings.\nDistributed Lossy Compression with Side Information: A generalized version of GLS is applied to a Wyner-Ziv-like compression setup, achieving gains over baselines on synthetic Gaussian and MNIST data.", "questions": "1) Theoretical Tightness: Is the list matching lemma (LML) tight in the worst case, or can it be improved further? Are there classes of distributions for which the bound is known to be loose?\n2) Drafter Invariance in Practice: Can you show a case where non-invariant speculative decoding causes divergence or instability during inference? An empirical ablation would strengthen the case for its necessity.\n3) Compression Baselines: Why not include more recent variational or neural compression schemes as baselines for the MNIST experiments? Shared randomness baselines are quite weak.\n4) Computational Efficiency: Could you provide concrete latency numbers (e.g., ms/token) for your method vs SpecInfer, especially on large vocabularies?\n5) Scalability: Have you considered how GLS performs in high-cardinality spaces, e.g., vocab sizes 50k–100k? Memory usage of O(NK) could become problematic.", "limitations": "The paper discusses limitations to some extent, particularly the extension to continuous distributions and finite sample approximations via importance sampling. However, more explicit discussion of computational overhead and failure modes (e.g., degraded performance at high temperature mismatches, decoding bias) would improve transparency.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1) Theoretical Rigor: The derivation of the LML and conditional LML is mathematically sound and nicely generalizes previous coupling bounds.\n2) Conceptual Clarity: The extension from one-to-one matching to one-to-many (list-level) is natural yet nontrivial, and the paper articulates this progression well.\n3) Novelty in Applications:\n- Drafter-invariant speculative decoding is a valuable contribution in a field where practical methods often lack such guarantees.\n- The compression setup with multiple decoders and side information is well-motivated and leverages the theoretical core effectively.\n4) Experimental Coverage: LLM experiments cover both i.i.d. and diverse draft models; compression is evaluated on synthetic and real data (MNIST).\n5) Error Analysis: The authors carefully analyze matching probability and rate-distortion trade-offs under different setups.\n\nWeaknesses\n1) Theoretical Originality: While well-executed, the core theoretical contribution (GLS + LML) can be seen as a relatively incremental extension of Gumbel-max sampling and Poisson Matching Lemma (PML). The analogy is strong but not fundamentally novel.\n2) Limited Empirical Diversity:\n- Speculative decoding experiments use only Qwen 2.5 models. No results on popular open-source LLMs like LLaMA, Mistral, etc.\n- Compression baselines are somewhat weak; only a shared-randomness baseline is used. No comparisons with alternative list-decoding or variational schemes from recent literature.\n3) Ablation Gaps: There’s no ablation of the importance of drafter invariance, nor is there a comparison of acceptance probabilities with non-GLS alternatives under similar resource constraints.\n4) Algorithmic Complexity: While the method is conceptually simple, it involves O(NK) operations and repeated argmins, which can be computationally intensive in high-cardinality alphabets. The authors mention efficiency but don’t provide run-time benchmarks.\n5) Limited Discussion of Limitations: While some limitations are acknowledged, key concerns — e.g., applicability of GLS to large vocabulary sizes and scalability of decoder-side computation — could be better articulated.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed response. We are glad that you found our presentation of GLS clear and appreciate your comments on the mathematical rigor and novelty of the applications. Please find our responses below:\n\n1. **Originality:**\n   While we agree that our results are natural extensions of Gumbel-max sampling [1] and PML [2], we believe that our method's simplicity is a strength rather than an indicator of insufficient novelty, which is a view shared by reviewers W4vi and fX9A. While our generalization appears simple in hindsight, it is not trivial and requires careful proof. Also, our new list-level setting is more than a theoretical curiosity, having practical applications to LLM inference and distributed compression. We therefore feel that our contribution demonstrates sufficient originality despite the core idea's simplicity.\n\n2. **Empirical diversity:**\n   While Qwen2.5 models are popular open-source LLMs and are representative of many current offerings, we agree that adding experiments on other LLMs would strengthen our claims. We provide results below mirroring those in Tabs. 1 and 2 but for Llama models, showing block efficiencies and percentage token-rate speedups. The first table uses a Llama2 68M drafter distilled by Miao et al. [3], coupled with a Llama2 7B target. As in Tab. 1, this experiment uses $K=8$. Since the small 68M drafter performs badly with a temperature mismatch due to its limited capacity, we use larger Llama3 models in the second table with a 1B drafter and 8B target. We take $K=2$ as in Tab. 2.\n\n   |Strategy|GSM8K BE|TR (%)|HumanEval BE|TR (%)|NaturalReasoning BE|TR (%)|\n   |-|-|-|-|--|-|-|\n   |SpecInfer|2.35±0.00|14.16±1.55|1.98±0.01|-0.29±0.66|2.14±0.01|11.44±0.73|\n   |SpecTr|2.35±0.01|13.41±2.10|1.99±0.01|-0.39±1.01|2.14±0.00|11.32±0.48|\n   |Ours|2.34±0.01|14.65±1.90|2.00±0.01|1.58±0.74|2.13±0.00|12.08±0.38|\n   |Daliri et al.|1.64±0.00|1.39±0.30|1.48±0.00|2.69±0.49|1.54±0.00|2.83±0.66|\n\n   |Strategy|Tmp. 1/2|GSM8K BE|TR (%)|HumanEval BE|TR (%)|MBPP BE|TR (%)|\n   |-|-|-|-|-|-|-|-|\n   |SpecInfer|0.5/1.0|2.21±0.01|-12.51±1.09|2.61±0.04|-4.73±1.67|2.46±0.03|-5.99±1.14|\n   ||1.0/0.5|2.44±0.02|-3.47±0.88|2.79±0.03|3.02±1.17|2.65±0.02|1.09±1.85|\n   ||1.0/1.0|2.57±0.01|2.11±0.73|2.94±0.02|7.50±1.04|2.79±0.01|6.86±1.23|\n   |Ours|0.5/1.0|2.67±0.03|5.88±1.46|3.63±0.02|33.85±1.11|3.33±0.02|25.71±1.81|\n   ||1.0/0.5|2.69±0.02|6.33±1.49|3.67±0.04|34.67±1.63|3.31±0.03|23.87±1.47|\n   ||1.0/1.0|2.88±0.01|13.00±1.12|3.72±0.03|35.90±1.40|3.51±0.03|32.20±2.37|\n\n3. **Tightness of the LML:**\n   Thank you for mentioning the need for a theoretical analysis of our bound's tightness. As reviewer fX9A had similar concerns, we refer you to the discussion under item 2 of our response to their feedback above.\n\n4. **Compression baselines:**\n   We clarify that both the baseline and GLS compression schemes make use of the *same VAE-based neural encoder/decoder pair*, which mirrors that adopted in Phan et al. [4] for a similar compression task.\n   That is, the weights and structure of the encoder and decoder networks, detailed in appendix D.3, are identical for both schemes. GLS itself is not a neural compressor but is rather an algorithm for the information-efficient communication of samples, which occurs *after* the VAE has produced embeddings from the source yet *before* the decoder network outputs its reconstruction. The decision to use GLS or the baseline scheme is therefore independent of the choice of neural compressor, VAE or otherwise. Using a more advanced compressor would likely benefit the rate-distortion performance of both GLS and the baseline, though we leave a full study of the interplay between sampling strategies and encoder/decoder architectures to future work.\n\n5. **Ablation on drafter-invariance:**\n   We have conducted a new ablation study to show the practical benefits of drafter-invariance. Please find our results and discussion in item 3 of our response to reviewer Wv4i. We also have a concrete example where non-invariant speculative decoding causes the output to diverge from the original after changing the draft model, under item 6 of our response to reviewer Wfqz.\n\n6. **Comparision of acceptance probabilities:**\n   We would like to stress that we give comparisons with non-GLS alternatives (SpecTr and SpecInfer) for all experiments in Tabs. 1 and 2, plus Tabs. 3 and 4 in the supplementary. In particular, the empirical token acceptance rate can be computed as $\\Pr[\\text{accept token}] = (\\mathrm{BE} - 1) / L$, where $\\mathrm{BE}$ is the block efficiency.\n   Note that due to extra steps needed to ensure sequence-level correctness, in particular checking $k \\in \\mathcal{S}$ on line 11 of Alg. 2, this is usually smaller than the one-step matching probability in Thm. 1.\n   For comparisons on the one-step matching probability, please refer to item 1 of our response to reviewer W4vi.\n\n   Our results in Tabs. 1 and 2 show that GLS achieves competitive performance in the i.i.d. case and often outperforms alternatives when the drafts are not identically distributed, both in terms of acceptance probabilities and wall-clock token rates.\n   Resource constraints (1×RTX6000 Ada GPU) are identical across these experiments.\n   \n   Please note that the SpecTr and SpecInfer coupling methods are not suitable for distributed compression, since they would require both the encoder and decoder to have full knowledge of the other's distribution; conversely, a useful compression scheme must limit communication between the two. Hence we adopt a simpler baseline, which uses 1 instead of $K$ sets of common random numbers, for the compression experiments.\n\n7. **Latency numbers and run-time benchmarks:**\n   We agree that run-time benchmarks are crucial for evaluating our algorithm.\n   With this in mind, we kindly point you to the results in Tabs. 1 and 2, plus Tabs. 3 and 4 in the supplementary, which contain our performance measurements.\n   All the experiments use the full Qwen2.5 vocabulary, which is large (containing 151,936 tokens).\n   In line with SpecInfer and SpecTr, we focused on token rates (TR, in tokens/second) and reported *relative speedups* instead of absolute measurements [3,6]. This allows for fairer comparisons, since the absolute token rate will vary depending on the hardware configuration and is thus not a good yardstick for judging the relative performance of different speculative decoding algorithms.\n\n   Nevertheless, we provide below versions of our Tabs. 1 and 2 from the main paper below with absolute latency numbers (in ms/token) instead of relative wall-clock percentage speedups. These tables do *not* represent new results, but are rather reinterpretations of the run-time benchmarks already provided.\n\n   |Strategy|GSM8K Latency|HumanEval Latency|NaturalReasoning Latency|\n   |-|-|-|-|\n   |SpecInfer|16.38±0.08|17.74±0.13|18.96±0.10|\n   |SpecTr|16.50±0.09|17.86±0.12|18.88±0.07|\n   |Ours|16.33±0.09|17.71±0.15|18.91±0.06|\n   |Daliri et al.|17.08±0.09|19.24±0.03|22.05±0.14|\n\n   |Strategy|Tmp. 1/2|GSM8K Latency|HumanEval Latency|MBPP Latency|\n   |-|-|-|-|-|\n   |SpecInfer|0.5/1.0|21.27±0.18|25.72±0.12|24.50±0.17|\n   ||1.0/0.5|20.36±0.24|23.96±0.24|22.83±0.20|\n   ||1.0/1.0|19.81±0.16|23.26±0.23|22.55±0.12|\n   |Ours|0.5/1.0|18.38±0.21|22.44±0.14|22.45±0.09|\n   ||1.0/0.5|18.43±0.13|22.73±0.24|22.36±0.20|\n   ||1.0/1.0|18.09±0.14|21.95±0.11|21.85±0.12|\n\n8. **Scalability, algorithmic complexity and related limitations:**\n   Thank you for your interest in the details of our algorithm. While the $O(NK)$ space and time complexity may seem troubling if $N$ is very large, we note that SpecInfer also has the same complexity [3], which has not prevented its widespread adoption. By using top-K sampling as is standard in LLM inference, we can reduce the complexity to $O(MK)$ where $M \\ll N$ is the number of high-probability tokens we wish to keep. These and similar \"tricks\" have meant that Gumbel-max sampling is already an efficient method for sampling from a single LLM [5], and our multi-draft extension can also benefit from them.\n\n   When considering the decoder-side computation in distributed compression, we have explicit control of $N$. As explained in appendices D.2 and D.3, it represents the number of shared samples taken from the prior distribution *before* decoding begins. Typically, this $N$ is quite small, e.g. $\\leq 2^9$ in our MNIST experiments. As a result, the $O(NK)$ complexity does not pose difficulties in practice.\n\n9. **Failure modes, e.g. decoding bias or performance degradation:**\n   First, we note that GLS provably maintains the target distribution. Therefore, our speculative decoding and compression schemes do not suffer from biased outputs. Second, you are right to mention that speculative decoding can sometimes cause degraded performance when the drafter and target are not well-aligned, e.g. with a large temperature mismatch. This limitation is not unique to GLS --- the latency numbers provided in item 7 above show that a large mismatch also increases the latency of SpecInfer and SpecTr. We will add more discussion of these limitations in a revised version of the paper.\n\n[1] M. Daliri, C. Musco, and A. T. Suresh. Coupling without communication and drafter-invariant speculative decoding, 2025. ArXiv: 2408.07978.\n\n[2] C. T. Li, and V. Anantharam. A unified framework for one-shot achievability via the Poisson matching lemma. *ISIT 2019*.\n\n[3] X. Miao, G. Oliaro, et al. Specinfer: accelerating large language model serving with tree-based speculative inference and verification. *ASPLOS 2024*.\n\n[4] B. Phan, A. Khisti, and C. Louizos. Importance matching lemma for lossy compression with side information. *AISTATS 2024*.\n\n[5] W. Kool, H. Van Hoof, and M. Welling. Stochastic beams and where to find them: the Gumbel-top-k trick for sampling sequences without replacement. *ICML 2019*.\n\n[6] Z. Sun, A. T. Suresh, et. al. SpecTr: fast speculative decoding via optimal transport. *NeurIPS 2023*."}]

Author rebuttal:

Meta-review: Paper summary:

The paper tackles the problem of coordinated sampling by introducing a list-based extension of the classic Gumbel-max coupling. The authors propose Gumbel-max List Sampling, which allows one party to generate K proposals and achieve a higher acceptance probability. They establish a List Matching Lemma that lower-bounds this probability and demonstrate two key applications: 1. A multi-draft speculative decoding scheme for large language models (LLMs) that is simple to implement, competitive with SpecTr and SpecInfer. 2. A distributed lossy compression mechanism with independent side information at K decoders, showing rate–distortion gains on synthetic Gaussian sources and MNIST images.

Summary of the discussion:

3 reviewers vote for acceptance, with one of them weakly. One more reviewer votes weakly for rejection. This last reviewer did not respond to the authors' rebuttal and did not engage in the discussion phase. The authors' rebuttal seems to address the reviewer's concerns.

Recommendation:

This is a borderline paper with 3 reviewers voting for acceptance (one weakly) and another reviewer voting weakly for rejection. However, the latter reviewer did not participated in the discussion or engaged with the authors who seemed to address their concerns in the rebuttal. Based on this, I recommend accepting the paper and encourage the authors to use the feedback provided to improve the paper for its camera ready version.
Decision: Accept (poster)