Accelerated Diffusion Models via Speculative Sampling
Authors: Valentin De Bortoli
Alexandre Galashov
Arthur Gretton
Arnaud Doucet
Venue: ICML 2025 poster (2025)
Keywords: Diffusion models
speculative sampling
maximal coupling
fast sampling of diffusion models
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: Speculative Sampling for Diffusion Models via Reflection-Maximal Coupling

Abstract: Speculative sampling is a popular technique for accelerating inference in Large Language Models by generating candidate tokens using a fast draft model and then accepting or rejecting them based on the target model's distribution. While speculative sampling was previously limited to discrete sequences, we extend it to diffusion models, which generate samples via continuous, vector-valued Markov chains. In this context, the target model is a high-quality but computationally expensive diffusion model. We propose various drafting strategies, including a simple and effective approach that does not require training a draft model and is applicable out-of-the-box to any diffusion model. We demonstrate significant generation speedup on various diffusion models, halving the number of function evaluations while generating exact samples from the target model. Finally, we also show how this procedure can be used to accelerate Langevin diffusions to sample unnormalized distributions.

Accelerated Diffusion Models via Speculative Sampling
Valentin De Bortoli'! Alexandre Galashov Arthur Gretton Arnaud Doucet
Abstract
eral techniques have been proposed to accelerate it. These include distillation techniques (e.g. Salimans & Ho, 2022:
Speculative sampling is a popular technique for accelerating inference in Large Language Models by generating candidate tokens using fast draft model and then accepting rejecting them based on the target model's distribution. While spec- ulative sampling was previously limited to dis- crete sequences, we extend it to diffusion models, which generate samples via continuous, vector- valued Markov chains. In this context, the tar- get model is high-quality but computationally expensive diffusion model. We propose various drafting strategies, including a simple and effec- tive approach that does not require training a draft model and is applicable tit-offthee-bo to any dif- fusion model. We demonstrate significant genera- tion speedup on various diffusion models, halving the number of function evaluations while generat- ing exact samples from the target model. Finally, we also show how this procedure can be used to accelerate Langevin diffusions to sample unnor- malized distributions.
Meng et al.. 2023; Song al., 2023), better sampling schemes (e.g. Karras et al., 2022; Lu et al., 2022; Zhang & Chen, 2023) and parallel simulation methods (e.g. Shih et al., 2023; Chen et al., 2024). However, distillation tech- niques inherently require training student model and often underperform compared to the teacher model (Dieleman, 2024). While better sampling schemes can improve per- formance, using too small a number of steps does degrade performance, see e.g. (Karras et al., 2022). Finally, paral- lel simulation methods relying Picard iterations over sliding window have been proposed (Shih et al., 2023; Chen et al., 2024; Tang et al., 2024). However, they are inher- ently iterative, requiring repeated parallel sampling within a window until errors fall below a pre-specified tolerance.
In the context of Large Language Models (LLMs), various techniques have also been proposed speed up inference. Notably, speculative sampling, first introduced by Leviathan et al. (2023) and later proposed independently by Chen et al. (2023), has become prominent in this area and has spawned numerous extensions (Xia et al., 2024). Given a target L.MM, this algorithm enables faster sampling than serial token de- coding without compromising quality, as the sampled tokens remain exactly distributed according to the target model's s distribution. This is achieved by considering a smaller and faster LLM model generating a draft sequence. The target model is then used to compute in parallel the conditional probabilities of these draft tokens, and these probabilities are used to decide sequentially whether to accept or reject the draft tokens. Upon the first rejection, a new token sampled using an adjusted distribution combining the draft and target distributions. Many extensions of speculative sampling have been proposed to reduce latency; see Xia et al. (2024) and further related works in Section 6.
1. Motivation
Denoising diffusion models (DDMs), introduced by Sohl- Dickstein et al. (2015) and further developed by Ho et al. (2020) and Song et al. (2021), are generative models ex- hibiting state-of-the-art performance in a wide variety of domains. The core concept behind DDMs the progres- sive transformation of data distribution into Gaussian distribution through the addition of noise. Sample gener- ation is achieved by simulating an approximation of the time-reversal of this noising process. This requires multiple evaluations of neural network that approximates the scores of the noising process, and typically involves simulating a Markov chain over hundreds of steps.
In the present work, we adapt speculative sampling to ac- celerate DDMs. We assume a computationally cheap draft model that generates a sequence of draft states for the de- noising Markov chain of target DDM. The transition prob- ability densities of these states under the target model are then computed in parallel and used to sequentially accep- t/rject the draft states. At rejection, a new state is sampled from an adjusted distribution dependent on both the draft and target distributions; see Figure 1. As for LLMs, the pro-
Since sample generation is computationally expensive, sev-
"quual contribution 'Google DeepMind. Correspondence to: Valentin De Bortoli <vdebortoli @ gomm
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Accelerated Diffusson Models via Speculative Sampling
cedure is designed such that it outputs samples distributed exactly according to the target DDM.
2.1. Speculative Sampling for Autoregressive Targets
Speculative sampling generates L candidate tokens accord- ing to the draft model p which are scored in parallel using the target model q. They are then accepted sequentially using an adjusted rejection sampling algorithm. At the first rejection, one needs to sample a new token from an adjusted distribution denoted r. A new set of L candidate tokens is then generated, and so on. This is detailed in Algorithm us- ing notation #):(" = (2k: 2k+1, ..., 2e) for l I & and 2k:d = for k >> E for any sequence (E and [k] = (1, (1.-.. k} for any positive integer k. We denote sequential computations by (Seq.) and parallel computations by (Par.).
Wang et al. (2024) concurrently proposed an adaptation of speculative sampling for continuous- valued autoregressive processes, specifically for Masked Autoregressive models (Li et al., 2024b). In this setting, they sample from the ad- justed distribution appearing at rejection using standard rejection sampling algorithm. However, as demonstrated in Section 3.2, this approach is, on average, more computation- ally expensive than directly sampling from the target model in our context. Furthermore, it exhibits counter-intuitive performance degradation as the draft model more closely approximates the target model. We present a method to cireumvent these issues while retaining the optimality prop- erties of speculative sampling. Our contributions are sum- marized below. Proofs are in the Supplementary Material,
Algorithm Speculative Sampling for LLM
Require: Lookahead integer L, maximum length K, draft model p. target model g. initial context Xoma-
Set 7 f n10
By leveraging the connections between speculative sam- pling and coupling techniques (Lindvall, 1992), first ob- served by Sun et al. (2023) in the context of LLMs, we show in Section 3.3 that we can sample efficiently from a novel adjusted distribution for DDMs using reflection maximal coupling (Bou-Rabee et al., 2020). Our proce- dure returns exact samples from the target model, and it is optimal in the sense that it maximizes the probability of accepting each draft state.
while n < ng + K do
(Seq.) Sample 1+++ ~ p(-(Xoon)
Get Pr+tj = p(-|Xo:as Xntimnt-1), [T.].
(Par.) Get gn+t = (--mXX(m, Xnt1m+j-1). [L].
for k = 1: + do
(og, + REJECTION (pkx Ix. Xx)
not (bool) or X EOS then Exit For Loop
end if end for Set n k end while
We investigate several drafting strategies (Section 3.1 and Appendix B). As with LLMs, one can rely on "cheap" diffusion model as draft model, or use a draft model learned from the target model. We propose here instead a simple and effective approach that proposes a draft model relying solely on the target model. This eliminates any need for learning separate draft model, and is readily applicable any diffusion model.
return X 11n
The rejection mechanism is described in Algorithm 2.
Algorithm 2 REJJCCTION (p, 9)
We present a complexity analysis and a lower bound on the acceptance ratio of the draft states in Section 4.
Require: Proba. distributions p.q and X ~ p.
Sample U ~ Unif(0, 1).
We explain in Section 5 how this method can be adapted to accelerate Langevin diffusions to sample unnormalized distributions.
bool = IU S min(1, (nin(1,(()//p()))]
if bool then Set X == X.
else
The proposed method achieves significant speed-ups for image generation on CIFAR10, and LSUN using pixel space diffusion models, without any loss of quality (Sec- tion 7). Furthermore, we show similar speed-ups in robotics for policy generation.
~ r(-), r(x) x max(0, ((x) - pp()))
end if return (X, bool) where X g.
In (Chen et al., 2023; Leviathan et al., 2023), the draft se- quence is sampled using a "cheap" autoregressive LLM, i.e, Xa+1 ~ p(-[Xomn); Xn+2
2. Speculative Sampling for LLMs
p(- p(-I-oom; X Xntt. ~ p(-]Xoon, X 1n+1m-t-1). However, this does not have to be the case, and any distribution p( 1m can be used, e.g., in Medusa (Cai et al., 2024) one samples the draft tokens in parallel by consid- ering factorized draft distribution p( I:a L. ro..) =
We begin with review of speculative sampling for L.Mss. Consider two probability distributions & and for sequences on some finite space X. In this context, q corresponds to the joint distribution of tokens for the target LLM, while p represents the draft model.
2

---

Accelerated Diffusion Models via Speculative Sampling
accepted sample
x
adjusted sample
diacorded
Verify in Parallel
Iterate
COOEOO
Efficient Draft
Speculative sampling
Figure 1. Speculative Sampling for diffusion models. Draft states are efficiently generated and verified in parallel. Upon the first rejection, state sampled using adjusted distribution combining draft & target models, and the remainder of the draft sequence is discarded.
-k==-11 pom)) Note that in this context, the distri- usually not compat- ible, i.e., they are not the conditional distributions of joint distribution. To be more precise, we should write Pa Pa(2n-imtt (zooo) instead of p(Intim-L/ but we slightly abuse notation here.
3. Speculative Sampling for Diffusion Models
butions ( [20=)) (
We now present our main contribution, which is the adap- tation of speculative sampling DDMs. Our DDM tar- get model and some drafting strategies are given in Sec- tion 3.1, leading Algorithm 3. As for LLMs, this algorithm requires ad- justed rejection sampling procedure. After analyzing the difficulties of an implementation of Algorithm 2 in the con- text of DDMs (Section 3.2), an original solution resolving these difficulties is presented in Section 3.3.
speculative sampling procedure in
2.2. Adjusted Rejection Sampling as Maximal Coupling
At the core of speculative sampling lies an adjusted re- jection sampling mechanism which allows for sampling from the (conditional) distribution of a token q(x) := (plat tokens) for target LLM given the (conditional) distribution p(z) = p(a) past tokens) of token for draft model.
3.1. Denoising diffusion models, draft models and speculative sampling
We first define the target DDM model we want to sample from. Following Song et al. (2021), consider a forward nois- ing process where Xo qaat and dX; ftX, + g,d,, where (B,)rejo.1) is d-dimensional Brownian motion. Let the density of X,, we select St, 9r such that a s (O, We then consider the process (Y:)
As pointed out by Sun et al. (2023), this procedure, sum- marized in Algorithm 2, is well-known in the probability literature, and the joint distribution of (X,Y0 Y') it induces is a so-called maximal coupling; see e.g. (Lindvall, 1992), Section 4.5 in (Thorisson, 2000) and (Jacob, 2021) for comprehensive introduction. Maximal couplings denote any distribution on (X, Y) maximizing the probability that = while X and Y q. For completeness, with- out any claim for originality, see Proposition 2.1 I for formal statement and the supplementary material for a proof.
dY, by (Y,) edl- Yo qn
(1)
(x( = -1- 1x + 1te² (),5)-1(x)
where sx(x) = V log (x)) is the Stein score, (W,)
is another Brownian motion and & 2 0 hyperparam- eter which controls the stochasticity level of (Y.) (Albergo et al., 2023). referred to the churn parameter in the literature (Karras al., 2022). This process such that YI- qi for all t E [0, 1] and corresponds to the time-reversal of (X, (X.)te(o.1] for 1. In practice, b, is ap- proximated using neural network denoted by. At inference we consider K ++ discretization steps and let = 1/K and (tx) with tą = bo; the corresponding distribution the resulting Markov chain obtained by the Fuler Maruyama
Proposition 2.1: Let X p then Algorithm 2 outputs X q. This procedure is optimal in the sense that it max- imizes the probability that X X under the constraints & P. X ~ g. Additionally, we have
P(X + x) = ||p 9llTV,
where ||p 4//TV = Evex (p(x) g(2)).
3

---

Accelerated Diffussin Models via Speculative Sampling
discretisation of (1) and initializzd at (0, Id) Vi is de-
Algorithm 3 Speculative Sampling for DDM
noted q(vo. x) = ((v)) I {yy 19-- where
Require: Lookahead integer L, sequence length K, target model q and draft model p.
q 1)- (y=: m (8k- 1): of Id)),
(2)
Sample Yo ~ (V,, (0, Td) and set O.
with g(yo)= Ny:: Id) a (vo). m (yk+) yk bb, (un) and o% = - The distribution (2) defines the target model in our speculative sampling procedure.
while < K do
Set Y, < Yn
Set n2 < min(n + L, K) and L = nu -
(Seq.) Sample draft states Y Yn+imn ~ p(-11,, using (3).
Speculative sampling requires specifying a draft model. All the draft models we consider are of the form p(yn+Im, Imn 1yn) = T p(yx (v where nn = min(n- + L, K), L the length of the draft sequence and
Get means of Pn+1 - pl p((1Ynnnj--)). E [.].
(Par.) Get means of In+j = q( (0-1(1(+--))))
[T.].
for == n n 1: n2 do
bool) + REJECTION (pe, ts, Yt).
1)) N (yykm"" (
(3)
if not (bool) then Exit For Loop
Independent draft model. A first choice, similar to the original speculative sampling algorithm (Leviathan et al., 2023), is to consider a draft model with the same sam- pling strategy as q but with an approximation by which is cheaper evaluate than bg. Hence, the draft model satisfies p(yslymn:k1) p(yx|y==1) with
end if end for Set n. + k. end while return Yo:K
(Vn:k)) = yk + Tb,, (Uk), ok = Vegi- (4)
Having now defined the target and draft model, we present Algorithm 3, our speculative sampling algorithm for dif- fusion models. This algorithm is similar in principle to Algorithm 1 for LLMs. The evaluation of the means of (Un+j(/nnntj-)) for j E [m n] is done in parallel. The rejection steps within the for loop are also implemented in parallel. However, the REJECTION step in our algorithm requires a substantially different implementation compared to the one defined by Algorithm 2 used for LLMs. This difference arises because directly applying the rejection mechanism of Algorithm 2 to diffusion models presents significant challenges, as we will demonstrate.
This choice of draft requires the availability of a cheaper DDM. For p and q to be close and to obtain better perfor- mance (i.e., higher acceptance rate of the draft states), this requires training p on the same dataset as q, which would be costly and might not be feasible. Even if p and q are trained with the same architecture on the same dataset, there can still be significant mismatch between bz and b".
Frozen target draft model. Another popular choice in speculative sampling is to derive a draft model directly from the target model, see for instance (Cai et al., 2024). In the context of diffusion models, we consider here very simple draft model where p(ynlumm- (mm.k 1) = p(u |ym, (1,, 11- with
3.2. Adjusted Rejection Sampling: Implementation Issues
m2f (Vm.k) yı + >b2, (yn), ox = Viegi-t2. (5)
Using Algorithm 2 to define REJECTION in Algorithm 3 would yield a valid speculative sampling algorithm for dif- fusion models, i.c., this algorithm would produce a Markov chain exactly distributed according to the target model, Yo.k ~ q. and Proposition 2.1 would also apply directly. However, we show below that implementing Algorithm 2 is problematic in the context of diffusion models. If draft state is rejected at iteration k. where k sample Yú from
This draft model is similar to the target model, except that we replace 68, (1K) by 1g, (w.).. Importantly, on a window of size L, we only need query the target model once in order draw draft sequence. This strategy is thus computationally inexpensive, requires no additional training and allows parallel sampling of the draft sequence. However, the differences between the draft and target models can be large near the data distribution as the score function typically exhibits significant variation. Consequently, 6% (yx) may deviate substantially from by, (yn) when k. n, K are close,
> n. we must then
max (0, q(x)) - pp(x)
r(x) JRJ max(0, p(a))dd
(6)
rendering the approximation b2g (yx) b9, (yn) inaccurate.' This issue can be addressed at higher computational cost using alternative and more involved drafting procedures, as discussed in Appendix B.
for ((yx) == ( (0)) p(yx)
p(ue Vnck-1). Al-
though straightforward for LLMs due to the discrete nature
of r(z), satisfactory solution for continuous state-spaces
Mooe sophisticated approximations, such as local linearization (Shoji& & Ozaki, 1998), could improve accuracy but their computa- tional cost is prohibitive in high dimension.
"The proof of Proposition 2.1 recalled in Appendix A extends straightforwardly from X' finite to Rd

---

Accelerated Diffussin Models via Speculative Sampling
remains elusive. Leveraging the fact that
r(x) x ((z)(1 min((1.((=//((x)))
we could sample from r(z) using standard rejection sam- pling. Using ((z) as proposal, the acceptance probability -
so that the average acceptance
probability
/ (1) (1=))1- m(t)) = up--lliv.
This is an approach analyzed by Jacob (2021) and adopted by Wang et al. (2024) for continuous- continuous-valued autoregressive processes. From standard results on rejection sampling. is known that the number of trials to simulate from the target q before acceptance follows geometric distribution with pa- rameter 1p - 2 /Tv. This distribution has mean 1/1lp- al lv and variance (1 - |lp - //llv//
/Ip glfyy (see (Jacob, 2021) for instance). This implementation of Algorithm 2 proves inefficient, as demonstrated by the following simple anal- ysis. With probability llp g/|TV, one needs to sample from (7) and, due the properties of the geometric distri- bution, the expected number of samples from q we need is |le <llTv x (1/llp g/|Tv) = 1. This rejection sampling procedure is thus practically useless, as it requires sampling on average from both p and q, as well as computing the acceptance probability min (1, (1in111(=)//p))))) (p))(())) Another unde- sirable property of this implementation is that the variance of the number of samples from q one would have to simulate increases rapidly the draft model p better approximates the target (i.e., as ||p-g/ gl rv decreases). These issues have been extensively reported in the literature (Jacob, 2021).
Figure 2. Two maximal couplings between p = (0.5, 0.25) and q (1,5,, 0.25): the one given by Algorithm 2 (top) and the reflection maximal coupling from Algorithm 4 (bottom). By def- inition, both couplings have p and g as their marginals. As they are maximal couplings, their probability mass on the diagonal is identical and the maximum among all valid couplings.
procedure is identical to the one used in Algorithm 2. This follows from the fact that /(r)/ = N/2 + 0, Id) with A = (m² - 3/o for Y = m² + oZ. At acceptance, we also have Y Y as in Al- gorithm However, Algorithm 4 differs fundamentally from Algorithm 2, upon rejection of the draft state, the function of the
3.3. Adjusted Rejection Sampling via Reflection-Maxinal Coupling
new state is computed deterministically rejected state, instead of sampling from (6); see Figure 2 for an illustration. This requires only one evaluation of the target ((yx(yk-1) to obtain the state Yz. Therefore, we use Algorithm for REJECTION of speculative sampling. A detailed full implementation is provided in Algorithm 6. The following proposition, which parallels Proposition 2.2, establishes the correctness of the method and follows Section 2.3.2 from Bou-Rabee et al. (2020).
As discussed in Section 2.2, the adjusted rejection sam- pling procedure from Algorithm 2 is identical to a spe- cific maximal coupling described, for example, in (Lind- vall, 1992). For DDMs, we have shown that implement- ing this procedure is challenging. However, it is essen- tial to note that maximal couplings are not unique. Bou- Rabee et al. (2020) proposed algorithm known flection maximal coupling to implement a maximal cou- pling for two Gaussian distributions [(m", IdId) and A(m", Id). This is directly applicable to diffusion mod- els, since p(yx/un:k
our implementation
= (y:: ( (f Id) and ((vk|y%1)) )) = (y): m (Wk-1) ( ( Td) are Gaus- sian distributions with different means but identical vari- ances. Introduced to establish convergence results for Hamil- tonian Monte Carlo, this procedure is noteworthy for its conciseness and its bounded and short running time. We detail it in Algorithm 4.
Proposition 3.1 (Reflection Coupling): Let p(x) = N(:; mp, o g(x) = N(x; Idd) and Y ~ p. Algorithm 4 outputs Y ~ 4. Additionally, maximizes
the probability that Y Y and
P(Y * r) = 11ppp-pp- glll = 2 111m 11mm-1mmm111 m211/2) 1,
where ||l - g|/Tv= = (p(=) - qdx)ldx and & is the c.d.f. of the standard normal random variable.
Direct calculations show that the acceptance probability of the proposal Y ~ NmmP,, Idd computed with this
5

---

Accelerated Diffusion Models via Speculative Sampling
This result shows that the efficiency of speculative sam- pling time k i.e., the probability of accepting a draft state is a decreasing function of 11 mp-1 (Y--(() This means that, as expected, a draft model must reasonably approximate the target for good performance.
which occurs if and only if
B[t]/L 2 Cp/C
(9)
Under the simplifying assumption that the acceptance prob- ability of any draft state is lower bounded by a, independent across the state sequence, one has
L-1
BLL 2 1a (1) Lat = - a + La E=
Algorithm 4 REJECTION (p,q, Y) for two Gaussians with
same covariance
This highlights the competing factors in speculative sam- pling. To satisfy (9), we aim for ELL]/L be as close to one possible, indicating high acceptance ratio and thus draft model that closely approximates the target model. This typically implies that Cp R Cy. Conversely, while (9) is made easier to satisfy by minimizing Cp/C,, this will in practice cause the acceptance ratio to deteriorate, consequently decreasing B[i)/L.
Require: Gaussians p(z) ((=mm,, (id).9(z)
V(:; m², o2 and Y p.
Set A = (m² - ma and e = A/I|A/I.
Let Z = (Y 77-mm -ymm")/rr //o
Sample U ~ Unif(0, 1].
bool 1 U S min
]
(Z
if bool then
Set Y =
else
4.2. Lower bound on acceptance ratio
Set Y = m2 + old 2ee" )Z.
end
We shed light here on how the acceptance ratio depends on the problem parameters and an independent draft model. Let a. WiZ An; 0, Id) Id) for Z (N(0,, Id) where
return (Y, bool) where Y q.
||A, 112 = T 7 + 4) -L, 1 - -00--9911 s9_,, (zr))1
4. Theoretical analysis
We provide an analysis of the proposed methodology. We derive an approximation of the complexity of speculative sampling in Section 4, and lower-bound the accep- tance ratio when using an independent draft model, in Sec- tion 4.2.
for = - - o where both sf and of approximate the true score 8, at differing computational cost. The draft state time n++ is accepted with probability min(1, an). We have the following lower bound.
Lemma 4.2 (Control of acceptance ratio): We have Blan] 2 exp [- -- A.]
4.1. Complexity analysis
We analyze here the computational benefits of using spec- ulative sampling for DDMs under a simplified computa- tional model. We assume an independent draft model p given by (4). The cost of evaluating by and by are C and Cp respectively with C, > Cp. Using a window size I, each step of speculative sampling increases the iteration index n by random variable L. E (l...., L). The cost of running the target model for K iterations is Coriginal = KC₁, while speculative sampling approxi- mately requires Capec (K/ + Cyy. This sim- plified computational model leads directly to the following proposition.
Similar results can established for the frozen draft model.
We next assume that the target model has access the exact score for distribution gdmta and that the draft model score corresponds to exact score for some distribution Pdata (we can think of this as means of characterizing the inexactness of the draft model). We obtain the following result.
Theorem 4.3 (Control of acceptance ratio (ID)): Under assumptions on Pdtta and Qdota detailed in the supplemen- tary material, we have
19 [[an] 2 exp [-
(E+ 1i 1)²
Proposition 4.1 (Average cost ratio): We have that
5
x min (1,2) - -oam) a a² D(pdatus Adata) ]]
EL
ICCooiggnal/
(8)
CC,/C,
where 8n = 1 tm, C a constant and D(pdata: Qdara is some divergence between Paata and Qdasa explicit in the proof.
Note that the average cost ratio (8) is independent of K. Speculative sampling is beneficial if this ratio exceeds one,
6

---

Accelerated Diffusson Models via Speculative Sampling
There are different factors influencing the lower bound of Theorem 4.3:
of r,, but explicit bounds on the bias incurred are available (Durmus & Moulines, 2017).
As 7 -> O, we have [|an] 2 1, implying that a smaller discretization step size leads to higher acceptance rates of draft states. However, smaller step size also necessitates a larger total number of steps to reach the target.
The speculative sampling procedure for DDMs presented in Algorithm 3 and relying on reflection maximal coupling (Algorithm 4) can be easily modified to accelerate the sim-
ulation of (10). In this scenario, (10) plays the role of the target model while
If D(Paata: (data) 0 then E[an] 1. if the draft and target models approximate the same data distribution then we obtain a higher acceptance rate.
This means that
(11) is the draft model. As a cheap proxy, we can also use the frozen draft model strategy, that is set VE(Zn4*) v Ez,,) for k L...,, RL.. Speculative sampling can be interpreted here as pre- fetching technique (Brockwell, 2006; Angelino et al., 2014); see Appendix K for a detailed description of the algorithm. It is an alternative to recent methods proposed to acceler- ate Langevin diffusions relying also on on parallel evalua- tions of V E (Shen & Lee, 2019; Anari et al., 2024; Yu & Dalalyan, 2024; Zhou & Sugiyama, 2024).
X = Xx - -V--VVE(X))) + 2
If (f o1)² + a2) + O as t - 1 then B[a,] 2 for n. close to O. This is the case for classical schedules (t) used in practice. Hence at the beginning of the denoising process, the acceptance rate is high.
The dependency with respect to E is such that both low and high values worsen the lower bound. There exists an optimal parameter (E = 1.0 in this bound). In practice, we sweep over >> 0.
5. Speculative Sampling for Langevin Diffusions
6. Related works
Consider a scenario where we are interested in sampling from an unnormalized density π (x) on Rd, i.e.
Speculative sampling. Introduced in the context of LLMs by Leviathan et al. (2023); Chen al. (2023), speculative sampling relies on a draft model based on a cheap LLM, An early drafting methodology proposing multiple tokens at once was put forth by Stern et al. (2018), 8), while drafting with independent models was explored in (Chen et al., 2023; Leviathan et al., 2023; Spector & Re, 2023; Sun et al., 2023; Christopher et al., 2024). Efficient drafting using the target model with additional feedforward neural network (FFN) heads was considered in (Stern et al., 2018; Sun et al., 2021; Xia et al., 2023; Cai et al., 2024). Finally, it has been pro- posed very recently by Christopher et al. (2024) to use discrete DDM (Austin et al., 2021; Campbell et al., 2022) as draft model for an autoregressive target model. For a comprehensive review of speculative sampling techniques for L.LMs, we refer to Xia al. (2024). Wang et al. (2024) has adapted speculative sampling to continuous state space but sample from the adjusted distribution (6) using rejec- tion sampling, which is computationally inefficient in our context.
x T(x) = exp(- (xp(-EE(x)
Z = ((z)d,,
Z
where the energy function Exx) can be evaluated pointwise, but each evaluation is computationally expensive, and Z is intractable. To sample from such distributions, we typically use Markov chain Monte Carlo (MCMC) techniques which are iterative algorithms requiring evaluating the energy func- tion at each iteration. We show here how we can accelerate MCMC methods when we have access to a computation- ally cheap proxy energy function E(x) s E(x) defining (2) x exp(-E(x)) using speculative sampling. Access to such proxies common in many domains of computa- tional science and engineering: see e.g. (Christen & Fox, 2005; Cui et al., 2011; Sherlock et al., 2017; Peherstorfer et al., 2018).
A standard MCMC technique to sample from æ is the Langevin diffusion defined by
Acceleration of diffussio models. One line of work dis- tills a teacher DDM into a student DDM for faster sampling: see (Luhman & Luhman, 2021: Salimans & Ho, 2022; Berth- clot et al., 2023; Liu al., 2023; Meng et al., 2023; Sauer
dx,- -E, 2dB
where 1200 is a Brownian motion. The limiting distri- bution of this diffusion is π. In practice, the so-called un- adjusted Langevin algorithm (ULA) (Durmus& Moulines, 2017; Vempala & Wibisono, 2019) is often implemented
et al., 2024; Song al., 2023; Katzir et al., 2024; Kim et al., 2024; Xu et al., 2024; Yin et al., 2024). For review of distillation methods, we refer to Luo (2023); Dieleman (2024). Another line of work pursues accelerating sampling through improved integrators (Dockhom et al., 2022: Liu et al., 2022; Lu et al., 2022; Xiao et al., 2022; Zhang & Chen, 2023). Additionally, parallel sampling of DDMs has been
X = Xx (X)) + 2
(10)
for a stepsize y > 0 and W Lid .V(O,d), Due to this time discretization, ULA only samples from an approximation
7

---

Accelerated Diffusson Models via Speculative Sampling
explored in (Shih al., 2023; Chen et al., 2024; Li al., 2024a; Ma et al., 2024; Tang et al., 2024). Our approach complements these approaches and can be combined with parallel sampling and/or better integrators. In Appendix J, we support this claim by combining our method with the parallel sampling integrator from (Shih et al., 2023). Specif- ically, we show that our method can benefit in terms of both NFE and FID from using single parallel call. In addition, method can be seamlessly used in combination with timestep distillation methods, such as those in (Sabour et al., 2024; Tong et al., 2024).
NFE target
10
0.2
0.4 Stochasticity E
0.6
0.8
1.0
7. Experiments
NFE target
10a-
In all of our experiments, we track two different types of met- rics. First, we assess the quality of the output distribution ob- tained with the speculative sampling strategy (Wasserstein-2 in the low dimensional case, FID (Heusel et al., 2017) and IS (Salimans et al., 2016) in the image experiments and reward (Chi et al., 2023) in the robotics setting). We also report the Number of Function Evaluations of the target model; a function evaluation is defined as call to the target model with a batch of data, irrespective of the batch size. Experiments accelerate Langevin diffusions can be found in Appendix K.
10
40 20
Window size
Figure 3. In each figure, the y axis corresponds to the number of evaluations of the target model. Without speculative sampling, we evaluate the target model with 200 steps and show the improve- ments obtained using our approach. Fach dotted line corresponds to INDP ENDENT drafting, each solid line to FROZEN drafting. The color gradient purple yellow corresponds to different di- mensions of the target distribution [2, 4, 8, 32].
Low dimensional experiments. We first investigate Al- gorithm 3 in low dimensional setting order better un- derstand the effect of key hyperparameters of the algorithm. We consider mixture of Gaussians target distribution with dimension varying between [2, 4, 8, 16, 32] and 16 compo- nents. All diffusion models are trained with a velocity objec- tive, see Appendix I.1. We consider two drafting strategies: the INDEPENDENT strategy and the FROZEN strategy as described in Section 3. We also refer Appendix I.1 for the architectural details. In Figure 3, we display the effects on the performance of the algorithm of the stochasticity in the sampler and the window size L.
refer Appendix I.1 for architectural and training de- tails. For all experiments report FID score computed on 50k training samples. Our results are reported in Ta- ble 1. We investigate the effect of temperature on our models. More precisely, we introduce an hyperparameter T > such that (i + A; Id)/N Id)) is replaced by N2 + A; O, rld)/A(( 0. rId)), see Appendix F.1 for more details. Note that upon choosing > 1 we do not sample exactly from but improve the acceptance rate. We sweep over the values of E and r in Table 1 on the CIFAR10 dataset. The main conclusion is that our proposed specu- lative sampling algorithm provides a significant speed-up (x2 to x3) while maintaining the quality of the target model. For example, on CIFAR1O, we reach FID score of 2.34 with only 35 calls to the target model, while the classical sampling procedure requires 100 calls to the target model to reach a FID score of 2.45, which represents reduction of 65% of the number of calls to the target model. Running the target model for only 30 steps on the other hand reduces the image quality, as the FID score worsens to 4.32. It is worth noting that increasing the temperature marginally im-
Figure 3 illustrate that FROZEN drafting is more efficient than ENDEPENNENT drafting as it provides a better reduc- tion of the NFE of the target models. This is in accordance with findings in speculative decoding/sampling for LLMs, e.g. (Cai et al., 2024). Regarding the amount of stochas- ticity E, there appears to be an optimal value for which the speculative sampling gains are optimal in agreement with theoretical insights derived in Theorem 4.3. Finally, increasing the window size L improves the performance of speculative sampling.
Image space experiments. Next, we demonstrate specula- tive sampling in higher dimensional settings on two datasets: CIFARIO (32 x 32 x 3) and LSUN (64 x 64 x 3). In all settings, the backbone architecture is a U-Net. We
8

---

Accelerated Diffusson Models via Speculative Sampling
Configuration
Draft (100 stepe)
Target
(100 steps)
Target (30 steps)
Speculative
FID
I
FID
IS T
FID
IS
FID
1ST
NFE
0,01, 0.5
17,05
8667
2,86
10.10
4.32
10.83
2.84
10.11
65.36
0.01, 7 1.0
17.05
8,67
2,86
10.10
4.32
10.83
2,84
10.11
61.64
= 0.01, 7 2.0
17,05
8.67
2,86
10.10
4.32
10.83
2.83
10.12
57.47
0,25, 7 0.5
81.38
7.60
2,45
7.68
11.32
2.42
10.24
42.44
0.25,
1.0
81.58
7.60
2.45
10.31
7.68
11:32
2.35
10.25
39:31
= 0.25, 7 2.0
81.58
7.60
2.45
10.31
7.68
11:32
2.34
10.32
35.40
0.5,
0.5
115.57
5.25
2,81
10.72
10.59
43,08
0.5. 1.0
115.57
5.25
2,81
10.72
10.28
11.55
2.71
10.57
40.37
0.5, 2.0
113.37
5.25
2.81
10.72
10.28
11.58
2.74
10.52
36.72
1.0, 0.5
188.29
2.64
7.09
11.22
28.93
11.48
7.12
11.14
46.54
188.29
2.64
7.09
11.22
28.93
11.48
7.10
11.18
44.81
1.0 = 2.0
188.29
2.64
7.09
11.22
28.93
11.48
7.11
11.14
42.11
Table 1. CIFAR-10 10 evaluation. For each column, report the best result in bold.
Configuration
Target
Speculative
Reward f
NFE L
Reward f
NFE
L 20, K 100
0.889
0.008
100
0.898 = 0.008
27.245 + 0.002
L 20, K 80
0.882 0.008
80
0.899 + 0.008
23.890 + 0.003
I, -20 K 40
0.898 + 0.008
40
0.875 + 0.008
15.544 + 0.005
L 20, K 20
0.887 0.008
20
0.901 = 0.008
9.430 + 0.004
L 10, K = 10
0.901 + 0.008
10
0.903 + 0.007
5.053 + 0.001
I= 5, K =
0.876 + 0.008
5
0.870 + 0.009
3.000 + 0.000
Table 2. PushT evaluation.
prove FID and IS score for some values of E. We observe similar improvements (around halving the NFE) in the case of LSUN, see Appendix
8. Discussion
We have developed here a novel speculative sampling pro- cedure to accelerate diffusion models. This was achieved by exploiting the connections between speculative sampling and maximal coupling, specifically through the use of re- flection maximal coupling. We have demonstrated that sig- nificant speed-up can be achieved while sampling exactly from the target distribution.
PushT dataset. Finally, we conclude our experimental study by showing that speculative sampling also yields im- provements for roboties task, where the policy is generated using a difffusion model following (Chi et al., 2023). In our setting, we focus on the PushT dataset. The state space is of dimension (16, 2), where 16 corresponds to the predic- tion horizon and is the dimension of the action. We refer to Appendix I.I for more details. The metric we report is the reward r E [0, 1] where r 1.0 means that the policy achieves perfect coverage over episode. For robustness we run 1000 episodes to compute the mean of the maximum rewards. For each episode we run the policy for 300 steps or stop if we reach the maximum reward. We follow the setting of (Chi et al., 2023), see also Appendix 1.1. For our specula- tive sampler we fix т = 1 and do not perform any parallel call. We only consider the FROZEN drafting strategy. We report our results in Table 2. We consistently observe that the speculative sampling strategy reduces the number of call to the target model while preserving the quality of the model. For instance, with only calls to the target model, our speculative sampler achieves a reward of 0.903 + 0.007 while running the target model with only steps yields a reward of 0.876 + 0.008.
This approach also has limitations. It is not directly ap- plicable to deterministic samplers, although noise can be added a principled way to such samplers to obtain a valid stochastic sampler, to which speculative sampling can then be applied (see e.g. Section 3.1). Moreover, similarly to Picard iteration techniques (Shih al., 2023; Chen al., 2024), it increases memory overhead due to the parallel calls to the sampler during the verification procedure.
In particular, while LLMs are memory-bound and there- fore heavily benefit from speculative decoding/sampling techniques that increase arithmetic intensity and reduce la- tency, this is not necessarily the case for diffusion models, which already benefit from parallelism. The applicability of parallel techniques for serving diffusion models, therefore, remains an active area of investigation.
9

---

Accelerated Diffusion Models via Speculative Sampling
Impact Statement
Chi, C.,, Xu, Z., Feng. S., Cousineau, E., Du, Y., Burchfiel, B., Tedrake, R., and Song. S. Diffusion policy: Visuomo- tor policy learning via action diffusion. The International Journal of Robotics Research, 2023.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Christen, J. A. and Fox, C. Markov chain Monte Carlo using an approximation. Journal of Computational and Graphical statistics, 14(4):795-810, 2005.
References
Albergo, M. S., Boffi, N. M., and Vanden-Eijnden, E. Stochastic interpolants: A unifying framework for flows and diffusions. arXiv preprint (XXi:2333308797, 2023.
Christopher, J. K., Bartoldson, B. R., Kailkhura, B., and Fioretto, F. Speculative diffusion decoding: Accelerating language generation through diffusion. arXiv preprint arXiv:2408.005666, 2024.
Anari, N., Chewi, S., and Vuong, T.-D. Fast parallel sam- pling under isoperimetry. In The Thirty Seventh Annual Conference Learning Theory, 2024.
Cui, T., Fox, C., and O' o'sullivan, M. Bayesian calibration of a large-scale geothermal reservoir model by new adaptive delayed acceptance Metropolis Hastings algorithm. Water Resources Research, 47(10), 2011.
Angelino, E., Kohler, E., Waterland, A., Seltzer, M., and Adams, P. Accelerating MCMC via parallel predictive prefetching. arXiv preprint 1eXX:x:1403.2220 2014.
De Bortoli, V., Hutchinson, M., Wirnsberger, P., and Doucet, A. Target score matching. arXiv preprint arXiv:2402.08667 2024.
Austin, J., Johnson, D. D., Ho. J., Tarlow, D., and Van Den Berg, R. Structured denoising diffusion models in
discrete state-spaces. In Advances in Neural Information Processing Systems, 2021.
Del Moral, P. Feynman- Kac Formulae: Genealogical and Interacting Purticle Approximations. Springer, 2004.
Berthelot, D., Autef, A., Lin, J., Yap, D. A., Zhai, S., Hu, S., Zheng, D., Talbott, W., and Gu, E. Tract: Denoising diffusion models with transitive closure time-disilllatin. arXiv preprint arXiv:2303.04244 04248, 2023.
Dieleman, S. The paradox of diffusion distillation, 2024. URL https::/ http:///anddrraraaae wwtp://///222//// paradox.. html.
Dockhorn, T., Vahdat, A., and Kreis, K. Genie: Higher- order denoising diffusion solvers. In Advances in Neural Information Processing Systems, 2022.
Bou-Rabee, N., Eberle, A., and Zimmer, R. Coupling and convergence for Hamiltonian Monte Carlo. The Annals of Applied Probability, 90K3):1009-1233 2020.
Doucet, A., De Freitas, N., and Gordon, N. J. Sequential Monte Carlo Methods in Practice. Information Science and Statistics. New York, NY: Springer, 2001.
Brockwell, Parallel Markov chain Monte Carlo simu- lation by pre-fetching. Journal of Computational and Graphical Statistics, 15(1):246-261) 2006.
Cai, T., Li, Y., Geng, Z., Peng. H., Lee, J. D., Chen, D., and Dao, T. Medusa: Simple L.LM inference acceleration framework with multiple decoding heads. In Interna- tional Conference Machine Learning, 2024.
Durmus, and Moulines, Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. Annals of Applied Probabiliry, 27(3):1551-1553 2017.
Esser, P., Rombach, R., and Ommer, B. Taming transformers for high-resolution image synthesis. In Proceedings of the IEEE/CVF conference on Computer Vision and Pattern Recognition, 2021.
Campbell, A., Benton, J., De Bortoli, V., Rainforth, T., continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 2022.
Deligiannidis, G., and Doucet,
Esser, P., Kulal, S., Blattmann, A., Entezari, R., Müller,
Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01313 2023.
J., Saini, H., Levi, Y., Lorenz, D., Sauer, A., Boesel, F,, Podell, D., Dockhorn, T., English, Z., Lacey, K., Good- win, A., Marek, Y., and Rombach, R. Scaling rectified flow transformers for high-resolution image synthesis. In International Conference on Machine Learning, 2024.
Chen, H., Ren, Y., Ying, L., and Rotskoff, G. M. Acceler- ating diffusion models with parallel sampling: Inference at sub-linear time complexity. In Advances in Neural Information Processing Systems, 2024.
Guth, F., Coste, S., De Bortoli, V., and Mallat, S. Wavelet score- based generative modeling, Advances in neural information processing systems, 2022.
10

---

Accelerated Diffusion Models via Speculative Sampling
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. GANs trained by two time-scale update rule converge to local Nash equilibrium. In Advances in Neural Information Processing Systems, 2017.
Li, T., Tian, Y., Li, H., Deng, M., and He, K. Autore- gressive image generation without vector quantization. In Advances in Neural Information Processing Systems, 2024b.
Higgins, L, Matthey, L., Pal, A., Burgess, C. P., Glorot, X., Botvinick, M. M., Mohamed, S., and Lerchner, A. beta- vae: Learning basic visual concepts with a constrained variational framework. In International Conference on Learning Representations, 2016.
Lindvall, Lectures on the Coupling Method. John Wiley & Sons, New York. 1992.
Liu, L., Ren, Y., Lin, Z., and Zhao, Z. Pseudo numerical methods for diffusion models on manifolds. In Interna- tional Conference on Learning Representations, 2022.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion prob- abilistic models. In Advances Neurul Information Processing Systems, 2020.
Liu, X., Zhang, X., Ma, J., Peng. J., and Liu, Q. Instaflow: One step is enough for high-quality diffusion-based text- to-image generation. In International Conference on Learning Representations, 2023.
Hsu, P. and Sturm, K.-T. Maximal coupling of Euclidean Brownian motions. Communications in Mathematics and Statistics, 1:93-104, 2013.
Lu, C., Zhou, Y., Bao, F, Chen, J., Li, C., and Zhu, J. Dpm-solver: A fast ODE solver for diffusion probabilis- tic model sampling in around 10 steps. In Advances in Neural Information Processing Systems, 2022.
Jacob, Lectures on Couplings and Monte Carlo. https://sitee http://siisess.lgllleeee ccomsitte///scccccoooooom/mmoeet wtazeejaccobmmceecturee 2021.
Luhman, E. and Luhman, Knowledge distillation in iterative generative models for improved sampling speed. arXiv preprint arXiv:2101.02.0 2021.
Karras, T., Aittala, M., Aila, T., and Laine, Elucidating the design space of diffusion-based generative models. In Advances in Neural Information Processing Systems, 2022.
Luo, W. A comprehensive survey on knowledge distillation diffusion models. arXiv preprint arXiv:2304.0422 042662, 2023.
Karras, T., Aittala, M., Kynkäänniemi, T., Lehtinen, J., Aila, T., and Laine, S. Guiding a diffusion model with bad version of itself. In Advances in Newral Information Processing Systems, 2024.
Ma, X., Fang, G., and Wang, X. Deepcache: Acceler- ating diffusion models for free. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, 2024.
Katzir, O., Patashnik, O., Cohen-Or, D., and Lischinski, D. Noise-free score distillation. In International Conference on Learning Representations, 2024.
Meng, C., Rombach, R., Gao, R., Kingma, D., Ermon, S., Ho, J., and Salimans, T. On distillation of guided diffu- sion models. In Proceedings ofe the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
Kim, D., Lai, C.-H., Liao, W.-H., Murata, N., Takida, Y., Uesaka, T., He, Y., Mitsufuji, Y., and Ermon, S. Consis- tency trajectory models: Learning probability flow ODE trajectory of diffusion. In International Conference Learning Representations, 2024.
Milchev, A., Heermann, D., and Binder, K. Finite-size scaling analysis of the & - 4 field theory the square lattice. Journal of Statistical Physics, 44:749-784, 1986.
Peherstorfer, B., Willcox, K., and Gunzburger, M. Survey of multifidelity methods in uncertainty propagation, in- ference, and optimization. SIAM Review, 60(3):550-591, 2018.
Kingma, D. P. and Welling, M. Auto-encoding variational Bayes. International Conference Learning Represen- lations, 2014.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Interna- tional Conference on Machine Learning, 2023.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEFF/CVF Con- ference on Computer Vision and Pattern Recognition. 2022.
Li, M., Cai, T., Cao, J., Zhang, Q. Cai, H., Bai, J., Jia, Y., Li, K., and Han, S. Distrifusion: Distributed parallel infer- ence for high-resolution diffusion models. Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024a.
Sabour, A., Fidler, S., and Kreis, K. Align your steps: Op- timizing sampling schedules in diffusion models. arXiv preprint arXiv:2404. 14507, 2024.

---

Accelerated Diffusion Models via Speculative Sampling
Salimans, T. and Ho, J. Progressive distillation for fast pling of diffusion models. In International Conference Learning Representations, 2022.
Sun, X., Ge, T., Wei, F., and Wang. H. Instantaneous gram- matical enror correction with shallow aggressive decoding. In Proceedings of the 59th Annual Meeting of the Associ- ation for Computational Linguisties and the 1 11th Interna- tional Joint Conference on Natural Language Processing (Volume 1: Long Papers), Association for Computational Linguistics, 2021.
Salimans, T., Goodfellow, I., Zaremba, W., Cheung, V., Rad- ford, A., and Chen, X. Improved techniques for training GANs. In Advances in Neural Information Processing Systems, 2016.
Sun, Z., Suresh, A. T., Ro, J. H., Beirami, A., Jain, H., and Yu, F. Spectr: Fast speculative decoding via optimal transport. In Advances in Neural Information Processing Systems, 2023.
Salimans, T., Mensink, T., Heek, J., and Hoogehoom, E. Multistep distillation of diffusion models via moment matching. In Advances in Neural Information Processing Systems, 2024.
Tang, Z., Tang, J., Luo, H., Wang, F,, and Chang, T.-H. Accelerating parallel sampling of diffusion models. In International Conference on Machine Learning, 2024.
Sauer, A., Lorenz, D.,, Blattmann, A., and Rombach, R. Ad- versarial diffusion distillation. In European Conference on Computer Vision, 2024.
Thorisson, H. Coupling, Stationarity, and Regeneration. Springer, New York, 2000.
Shen, R. and Lee, Y. T. The randomized midpoint method for log-concave sampling. In Advances in Neural Infor- mation Processing Systems, 2019.
Tong, V., Trung-Dung, H., Liu, A., Broeck, G. V. d., and Niepert, M. Learning to discretize denoising diffusion ODEs. arXiv preprint arXivv2405.15506, 2024.
Sherlock, C., Golightly, A., and Henderson, D. A. Adaptive, MCMC for targets with expensive likelihoods. Journal of Computational and Graphical Statistics, 26(2):434 444, 2017.
Vempala, S. and Wibisono, A. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, 2019.
Shih, A., Belkhale, S., Ermon, S., Sadigh, D., and Anari, N. Parallel sampling of diffusion models. In Advances in Neural Information Processing Systems, 2023.
Vincent, P. connection between score matching and de- noising autoencoders. Neural Computation, 23(7):1661: 1674, 2011.
Shoji, I. and Ozaki, T. Estimation for nonlinear stochastic differential equations by local linearization method. Stochastic Analysis and Applications, 16(4):733-752, 1998.
Wang, Z., Zhang, R., Ding, K., Yang, Q., Li, F., and Xiang, S. Continuous speculative decoding for autoregressive im- age generation. arXiv preprint arXiv:2411.11925, 2024.
Xia, H., Ge, T., Wang, P., Chen, S.-Q.. Wei, F., and Sui, Z. Speculative decoding: Exploiting speculative execu- tion for accelerating seq2seq generation. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 9905-3925, 2023.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International Conference on Machine Learning, 2015.
Song. J., Meng, C., and Ernon, S. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021.
Xia, H., Yang, Z., Dong, Q., Wang, P., Li, Y., Ge, T., Liu, T., Li, W., and Sui, Z. Unlocking efficiency in large language model inference: comprehensive survey of speculative decoding. In Findings of the Association for Computational Linguistics: ACL 2024, 2024.
Song, Y., Dhariwal, P., Chen, M., and Sutskever, I. Consis- tency models. In International Conference on Machine Learning, 2023.
Xiao, Z., Kreis, K., and Vahdat, A. Tackling the generative learning trilemma with denoising diffusion GANs. In International Conference on Learning Representations, 2022.
Spector, B. F. and Re, C. Accelerating LLM inference with staged speculative decoding. In Workshop on Efficient Systems for Foundation Models@ ICMI.2023, 2023.
Xu, Y., Zhao, Y., Xiao, Z., and Hou, T. Ufogen: You forward once large scale text-to-image generation via diffusion GANs. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, 2024.
Stern, M., Shazeer, N., and Uszkoreit, J. Blockwise parallel decoding for deep autoregressive models. In Advances in Neural Information Processing Systems, 2018
12

---

Accelerated Diffusion Models via Speculative Sampling
Yin, T., Gharbi, M., Zhang, R., Shechtman, E., Durand, F,, Freeman, W. T., and Park, T. One-step diffusion with distribution matching distillation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024.
Yu, L. and Dalalyan, A. Parallelized midpoint random- ization for Langevin Monte Carlo. arXiv preprint arXiv:2402.144333 2024.
Zhang, Q and Chen, Fast sampling of diffusion models with exponential integrator. In International Conference on Learning Representations. 2023.
Zhang, R., Isola, P., Efros, A. A., Shechtman, E., and Wang, O. The unreasonable effectiveness of deep features perceptual metric. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2018.
Zhou, H. and Sugiyama, M. Parallel simulation for sam- pling under isoperimetry and score-based diffusion mod- els. arXiv preprint 2rX1v:2412.07435, 2024.
13

---

Accelerated Diffusion Models via Speculative Sampling
Organization of the Supplementary Material
This supplementary material is organized as follows. Proofs of the main results are gathered Appendix A. Potential alternative drafting strategies are discussed in Appendix B. A detailed implementation of speculative sampling for diffusion models is presented in Appendix In Appendix D, we present various results on the first time rejection and how this could be efficiently approximated numerically. An extension of the maximal coupling strategy for Gaussians with different variances is proposed in Appendix E. In Appendix F, we investigate alternative acceptance criteria relying either the introduction of a temperature parameter or the use of the "typical acceptance criterion" of (Cai et al., 2024) introduced for LLMs. Appendix G presents an extension of speculative sampling to incorporate some spatial transform. In Appendix H, we establish lower bound on the expectation of the log-acceptance ratio. Experimental details are gathered in Appendix I. Finally, Appendix K details how the speculative sampling procedure proposed in this work can be used to accelerate simulation of Langevin diffusions sample from unnormalized target distributions and presents simulations this context.
A. Proofs of the Main Results
A.1. Proof of Proposition 2.1
The joint distribution of (X, generated by Algorithm 2 is
[(, x) = p()) (1 - a()))r())),
with (x) the Kronecker-delta symbol and a(ū) = min(1, (z)/((()) That is we first sample X ~ then set X = with probability a(X) and sample X ~ r otherwise. follows that the marginal distribution of is given by
X
f(x) Σ f(,,2) - + (1 Σ TEX
a()))(#))r r(x).
(12)
8E
We have
r(x) x max(0. - p(x))
=g(x) min(p(z).q(m))
=((z) a())p(x).
Therefore, we have that
g(x) (x))p(())
r(x) 1 1- 1- ExEx (())
Hence, by substituting the expression of r(x) in (12), we obtain f(x) g(x), that is X ~ q. Now by construction, we have that
P(X + X) =1 Σ p(x))(x)
#EX
Σ min(p(z).q(z))
xEX
= ||p 10-4lpp /TV,
as min(a,b) b) = 1 + - lalla-bb
(0-bb) bl) for any a, b. However, Lindvall's inequality (Lindvall, 1992) (also known as the coupling inequality) shows that any pair of random variables X, X satisfying marginally X and X q verify
ba-
lp g/vv < PPX + X).
(13)
Algorithm generates a joint distribution for which the inequality (13) becomes an equality; hence is optimal.
A.2. The need for adjusted rejection sampling
One could wonder if an algorithm where we sample from under rejection and not from the modified probability r(x) xc max(0, q(x)- - p(xr) would work. In particular, we could consider Algorithm
14

---

Accelerated Diffusion Models via Speculative Sampling
Algorithm 5 INCORRECT REJECTION (p. q. X)
Require: Proba. distributions ? and X ~
Sample ~ Unif(o, 1].
bool IU I min(1, ((X)LL)(()/p(X)))
if bool then
Set X = X. else
X ~ (-)(.). end
return (X, bool) where ~ q.
can easily be shown that Algorithm 5 does not output Y with distribution y as in this case the joint distribution of X, Y is
((t.))=p()(aa0)633 (1 (()))((x))
so the marginal distribution of X is given by
f(x) - a(x)(()) + (1- Ca())p())) g(x)) # ((x))
ZEX
In particular, the following example illustrates the problems with Algorithm 5. Consider p Uni and q Uni 1,). In that case, we have that bool Bcr(1/2) Henee, accept X half of the time in expectation. If we were sampling from q 1,, upon rejection then the output distribution (1) of X would be given by
3 Uni 1)) + Uni
x
This means that we sample too much on the set [0,1]. In order get X q(-) we need to sample more the which outside of the support of p. This is exactly the purpose r(-). Indeed, we have that r(x) ([2, Hence, using Algorithm 2 we get that
X ~ Unif (10, + Uni,((2,3))) 2
that is, X ~ q as required.
A.3. Proof of Proposition 3.1
We have y (mm"; Id). We check here that the algorithm also returns Y ~ (Nmm:; To show this, we leverage the fact that we can rewrite Y = m2 + 7 for some random variable whose distribution follows
f(3) = / 62+a(3) mi) min(1,
Ni2 + A; Id)
O,);0,Id) )
+ f (rd-22n (²) max 0.
A(2 + A. 0.0, Ozz Id)
N(:;
where we have used 1 min(1, = max(0, 1 - a) for 2 0. Hence to show the validity of the procedure, we need now to show that 7 IO,, f(2) = Id) We have
8 (2) min 1, N(2 + A;0,I,
N[ 0, Id)dz
(2;
/ (o+a(3) ( +110000)))
min(N(( -(0.0))
15

---

Accelerated Diffusion Models via Speculative Sampling
In addition, we have that
/ 61a 21 max (, W( + Id),
0d) (z; Id)dz
/ 0(1a- 1ee-2207T T) (3) max (z, - (/ 1:0,
max (I.V((ld 2ee )2;0,1d) -V 2ee ) 2c0
-; Id).
as (Id 2ee )2 implies that = = (Id 2ee ) and (ildd 2ee );;0, = (2; Id) because l( 2ee )&(l
|| Finally used the fact that .V(lI 2ee ) A; 0, Id) M/ A;0, Id)
[I(ld Zee ) Al1 = || | + ||(Id 2ee 2ee )all? +2 4A ce
= || + || 22 TA
= || A
as ce" AAT/|AA]2 Combining these results, we obtain that f(z) min(V(= A, (2) + ((x,0) - -V( A;0,ld)
= -, Id)).
We thus have proved that ~~ (0, Id), so Y ~ N(m², IId). To prove now that this coupling is maximal coupling, we compute P(Y * Y). Recall that Y Y if U < min(1, A:0.Id)/N((:0,1dk) so
PPY + Y) =1 / Ni 0,
straightforward to check that this indeed equal to
Pp <v| [IV(,,, Nu Qddd) || = =20(1AA\/2) 1,
where & is the cumulative distribution function of the standard normal random variable. Hence, it follows from Lindvall's inequality (Lindvall, 1992) that Algorithm 4 outputs maximal coupling.
Similarly to Appendix A.2, it can be easily shown that we cannot sample simply independently from g in the case we reject as it would output unconditionally a random variable Y whose distribution differs from
A.4. Optimality of reflection maximal coupling
In Appendix A.3 we have shown that the reflection coupling is maximal coupling. In what follows, we denote C(m², m9) the set of coupling, i.c., distributions on IRd x Rd with marginals (mm,, o²Id) and ((m=, We also denote by Hettection E (mmP, m9) the reflection coupling. Proposition 3.1 shows that
Llfetection E argmin m2) (
In fact, Hsu Sturm (2013, Theorem 4.2) show that
Teelecctio E argmin BB (0yy)~u(((11) YY1)),
for every non neg-nega,ive, strictly increasing and strictly concave function & with ((0) = Hence, the reflection coupling also naturally appears if one considers other cost functions than (i. 3) + 18zty-
B. Alternative drafting strategies for diffusion models
Medusa-like correction. To improve the frozen target as draft model (see (16)), we can introduce correction term to the frozen model. Our correction is inspired by the Medusa architecture (Cai et al., 2024). More precisely, we consider a smaleer correction model cl trained with the following loss
((0) (.' f. (b6)(z)) (z(x)) - (x,, x.) (x,, pa, (I,,,, 2,)dr,dæ,.
(14)
16

---

Accelerated Diffusion Models via Speculative Sampling
Here Ps,t can be any distribution with support on R Rd the minimizer for Ca (x,, vT) is then always (2,, b3 (xrz). However, in practice, one may choose Ps, (T,, 24) defined by the following procedure
X = Ce X + oz
X, = - - (o (2.
where Z, and Ze are independent Gaussian random variables with zero mean and identity covariance matrix where this joint distribution of X, and X, is induced by the diffusion
dX Ju + JudBu.
the correction model is expressive enough then the minimizer of (14) is given by (,, = (x(() - b9 (x,)) and in that case the draft model is equal to the target model.
We then have model p(yx Wrck-1) .N (yys m (ynck- 1), Tdd) with
(((n))))) V/ + 769, 2, (yn) + cn (yns wk))
TF E===v/99--
Hence, on a window of size L, we only need evaluate the target model once while the (cheap) correction model is evaluated L times. If ca, then recover the draft model proposed in (16). Note that similarly to the frozen model, can sample the draft states in parallel.
Combining draft models. Assume we have N draft models such that (1 (3x-1) N m - (Wnnk- 1), and let a (y)--) 2 0 such that Ei at (3k-1) = 1. We can define new draft distribution
(uixxuwlyx=- N (yys m (yk- 0 Id),
mix m
(yk-1)=
- (Uk-1)m (Ik-1)-
(15)
The distribution in (15) mixes together Np draft models by considering a convex combination of their means, Since is Gaussian, Section 3.3 applies and get that
P(Y + Yu|Y=-1) = (0 (e00o-"1lm""(1aaee. V 1,
The parameters, ag (Bn-1) can either be hyperparameters (constants) specified by the practitioner, or can be represented by a mapping af (yx: 0) with parameters 0. These parameters can be learned by minimizing the sum of average rejection probabilities Eya.
EK_ P(Y * V=))
Parallel sampling and speculative correction. We now show here how one can combine Picard iterations from ParaDiGMS (Shih et al., 2023) and speculative sampling by using the output of ParaDiGMMS as draft model. We start by recalling the Picard iterations from Shih al. (2023). Consider draft sequence initialized with some deterministic transformation of Y,, i.e. 8- n+lmm =FF2+1(Yn: (Y.)... (Y,)) where nı max(K, L). Then, we define the Picard iterations
TTT f-m-1 70% ("<TT))
mm Y...
where & E (n 11+1,... } and m (L...., M 1}. Here we use Picard iterations for the deterministic sampler, that ( see Equation (1). Hence, for any k E {n + 1, I,...,nLL there exists
is and (z) (x) + deterministic function 1 such that
TmT PTT (Yn).
Lastly, we consider a last Picard iteration
Y.M -
--M-- k-1 + 7b9 (9/M-L) + EV7990_,2 Zk.
where Z₃ NN, Id). Hence, we have
y P (V,)
PM-1
(FM-1((P)) + +e/Fotu-,2e
17

---

Accelerated Diffusson Models via Speculative Sampling
We consider the sequence Y:M n+lmng
draft sequence. In that case still have that Y.M n+imm p (Bn) with
PL II
"L II 1mmm1
p(ya 1one (n))
N(ni m (2
as required where
my (vnsk-11)) = F + 7,6%% (F
Ok = E
Efficient frozen draft strategy. We start by recalling the frozen draft strategy described in Section 3. In that case, we consider here very simple draft model where p(ykk Wick-1) = p(yl Wn, yk-1) with
me (Mrck) Us 7b,, (un), ok V-891-04
(16)
This draft model is similar to the target model, except that we replace 62, (vx) by bf, (Bn). Importantly, on window of size L, we only need to query the target model once in order to draw a draft sequence. In practice, a more efficient modification of this frozen draft strategy can be obtained we replace 6% (un) with 6% (7n). Note that if, in the previous window, all the samples have been accepted then 69, (yn) coincides with D2, (Wn). Otherwise they not. The main advantage of this procedure is that we can leverage the quantities computed on the previous window during the iterated speculative sampling procedure. Indeed, b2_ (Ur.) is always computed when doing speculative sampling perform the verification stage, see Algorithm 3. This drastically reduces the cost of the draft model since, we do not need to call any model to compute the proposals, since 6% (Jn) has already been computed at the previous verification stage. The only caveat to this method is that it requires to be initialized, i.e., we need to compute 6% (wo). In that case, we simply compute 62, (yo) (and therefore the cost of rumning the whole draft model is one function evaluation of the target model). Finally, another alternative strategy to use 6,,_,(n (Wn-1) in place of 82 (ūn) when Dn * yn.
the previous window, in order to
C. Detailed implementation of speculative sampling for diffusion models
We present in Algorithm 6 detailed implementation of speculative sampling for diffusion models, an algorithm combining Algorithm 3 and Algorithm 4.
D. Distribution of time to rejection
Consider the following process (Y&, Yx)xzo following the following distribution
[[ 30m) = p((00) (vo)
II p(u wo ((x Tu 10g. (vx) + (1 - or (y lux- T1))
where
as (1( 1kkk) min min(1, q(ux
p(un 1y
and
r(y 11 T6) ((ve-1. (ykk
corresponds to reflection maximal coupling for appropriate function f. This distribution deseribes the speculative sampling algorithm for diffusions (not describing the drafting process over an horizon of L but this is irrelevant). By construction, we have / I yo:n )doo.n = q(Vo.n. Starting from Y,- = Yo. we can look at the first time т, T 2 1, the draft state is rejected. This is equivalent to look at the first time that Yn f Yg- We have from direct calculations that
(P( - f p
ploo.s) II (.
Hence [P(r > k) is given by Feynman-Kaa Kac formula (Del Moral, 2004) so we could estimate numerically efficiently this quantity by running a particle filter (Del Moral, 2004; Doucet et al., 2001). A similar expression can be obtained for the distribution of Tn the n time the draft state is rejected starting from the last time one rejected a draft, p(ño) being replaced by -110,,))))))))
18

---

Accelerated Diffusion Models via Speculative Sampling
Algorithm Speculative Sampling for DDM
Require: Lookahead integer I., sequence length K, target model (see eq. (2)) and draft model (see eq. (3)). Sample Yo (O, Id) and set n = 0.
while n < do
Set Y, Y, and nz. = min(n + I., K).
for h + 1 nı do
Sample Y2 N(m (Yn. nik 1), o Il).
end for
In parallel, compute my (Yn): m n+1 (Yat1)........ m - (1).
for k = n + 1 n do
Set Ax-1 = (m) (Yrc m1) mm m (Vx-))))) and == A
Let - (Y&- m
(Yn:k-1))/
Sample U ~ Unif(0, 1).
bool = T[ S min(1,W(Z,, + 1.0)
if bool then
Set Y3 = Yg.
else
Set Y22 ml (Vk-1) + -=d1(Id 2ee T 1Zk
end if
return (Y,, bool).
if not (bool) then
Exit For Loop end if end for Set +-
end while return YR
19

---

Accelerated Diffusion Models via Speculative Sampling
1.0
0.9
0.8
0.4
0.3
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Figure Evolution of the rejection probability (y-axis) with the dimension d (z-axis) for σ 0.2 and 02 0.1
In the case where we have
+ p(yalu--1) (Nwi U4-1 70b((yx-11) (gk-1)),dd);, ?1d), ((mlly--1) = 10 76² (xx((x11)) 7id).
Under the simplifying assumption that [bb(xz) 62 M, we have
0n P(Yo = Yo) II P(Y 1,1i Ym-1)
II 24 (-V>) 6 (Y.-11111
$ (2 - -2
As we have 20(-x)= =1 V o
lim 0,.177 = 0. 7-0
E. Maximal coupling between Gaussian distributions with different covariance matrices
Algorithm 4 is restricted Gaussian random variables admitting the same covariance matrix. This implies that the draft and the target samplers introduce the same amount of noise each step. One wonder if the two samplers could have instead different noise levels. In the following examples, we show that, even if the means are equal, then the probability of rejection is extremely high as the dimension increases.
Indeed, consider two centered ddddddiine dimensional normals p(x) = (x;;; 0, Id and ((x) = (x; 0, IgId). We assume that 02 < 01. that case, we have that p(x) S ((x) if and only if || < R² with
R² (llog(o//03((1/33 1/0?)-1
Hence, in the ideal case where the acceptance probability given by ||p g//Tv, we get that
- E6 [[[, - E [= -E= Bl
/
where is x random variable with d degrees of freedom. Unfortunately this probability is extremely close d increases, see Figure 4. Therefore, the probability of coupling is very low in high dimensions.
F. Alternative verification strategies
In this section, we investigate different verification strategies for Algorithm 4. First, we introduce a temperature parameter in Appendix F. Then, in Appendix F.2, we adapt the rypical acceptance criterion of Stern et al. (2018); Cai et al. (2024) to our setting.
20

---

Accelerated Diffusion Models via Speculative Sampling
F.1. Influence of the temperature
Consider Algorithm 7, which is version of Algorithm 4 including an additional temperature parameter 0.
Algorithm 7 (Temperature) REJECTION (p, Y) for two Gaussians with same covariance
Require: Probability densities p(x) (x; o IIId). N2; Y p, temperature 0.
Set A (m² m and e A/||A||.
Let Z = (Y ma
Sample U 1].
bool I S
if bool then
Set Y Y
else
Set Y = m o(d Zee. JZ.
end if'
return bool).
Setting = 1, we recover Algorithm but for 7 > 1 we have larger probability of accepting the current proposal Y This higher acceptance rate, of course, is not without its drawbacks since we are no longer sampling from the correct distribution. In what follows, we analyze how the distribution shifted when tuning the temperature parameter т. To shorten notation, we use in the following proof the notation (-(()) = N(2; O, rId) and y şo for 7 We recall that Ca the set of continuous functions with compact support. For any f C₂ (IR),, using that for any æ R2, ||>|| || for
(Id Bee )ar, and > (Id -2ee )ar is involution, have
E[f(Y)] [ f(m² + oz)) min(1, (2)))
+ A s(m8 + +o2)(1 min + A/)p
/ f(me + (x
+ *sf
- [0mnfoo2))--mmm00024444444441110
Rn
1 + min (c)))))
J f(m² +zz) (2
+ S s(m² + oz))(2)dd
f f(m² + oz) (ii A));(( A)dz
- f(m² + min(min(11 ( 4)/9-(()))o(eddzz,
+ 1 f(m² + (z)(((
21

---

Accelerated Diffusion Models via Speculative Sampling
We have that 2 + A A. Hence, we get that
/ Jad f(m" + ((2) A))x(( A)dz
B[f(x]]
[ Rd f(mm+ + 4)/
+ J f(m² +o2)())2)
f(m² +
1 s(m2 oz)) min(,, ())p)
+ Ssu f(mm + +z2)p(z)dz
5(m² +02) ()/0(2),((0-2)))( -ttp:///iiii////////////e-----/- -/ll -)/()/(-----))))))))()) ()
B4
[ f(mm + +02) min(1 pz -o
f f(m² +zz)
Hence, we get that
Elf(Y)l = / f(m² a
(17)
where
a=(2)= min(1, A)/(+(=)))) + mincs//eepde-/////((------- (2))()((()))))))))()) ((==)\/<(2)))) A)/((2)).
Note that for = 1 we have that (=(=) = O. If we let T + too then we get that a=(=) = -1 5p= A {))((=) so ~ ~N(mm, Idld) from (17), i.c. we always accept the draft model. In Figure 5, we show the effect the temperature on the output distribution. The influence of the temperature in more realistic settings is studied in Appendix
Link with guidance. We first give the following result and subsequently explain its connections with (Karras et al., 2024).
Proposition F.1 (Link with guidance): Let (Ý, Y) be the output of Algorithm 7. We have that
B|y| = m + (1/0)C,(1All)mm - m²),
with A = (m² ma and C+(I < 0 if S 1 and C+(IAI)) O otherwise. In particular, we have that ([I = i = 1. In addition, C₁ (I] is explicit in the proof.
We can interpret this result as follows. For r = 1, we recover that the mean of Y is the mean of the target as expected as we have a maximal coupling in this case so Y follows the correct target distribution. For > 1, we increase the acceptance probability: this has intuitively the effect of moving the distribution of Y towards the distribution of Y Looking at the mean, we can interpret this effect guidance effect, where we push towards m² and away for m For 7 1, we pushing towards the target distribution guidance term, i..., pushing away from the draft model and towards the target model. This last setting is similar to (Karras et al., 2024), which consider an explicit guidance of a "good" model with "bad" model.
more than with
1. Looking the mean of Y. can interpret this effect as
Proof. Using (17), we have that
E| = / (m² + (z) + + (z))
J
m + m3 / (x())(2)) + za, (z)
22

---

Accelerated Diffusion Models via Speculative Sampling
First, we show that Sza a (z)dz 0. Indeed, using the change of variable + -- and - A ger
J (z)p(()) =
- mtll/////p---///////------e---e-
Rd
(
- - A)) A)dz
min (
min(s/3)jpt)//eee-///ooet/ll = O.
Hence, we have that
B [ (m" + +zz) a (z))) =
m2 + /
za, za. (2)d22) Rd
We going show that
Jec (z, (t) = 0,
where we recall that e A/||A|]. For any E Rd, we have that 2 + Σd-1 2e, eú where 2. (z, e) and 2e; (2, with fe, e dd-1 an orthonormal basis. Note in particular that for any E (l...., d 1), = We have that
20,(2)2(2)dz= = / / Rd
- (mii(//4)illl-00)///4----AA (l))))/)))d/
Rd
z -1=l:p===--///ppp mmin(
(/tn/// - A))dz
(;
Ra
(z A) A) (10
Ra
2
2
minl(p (2 (3)))
A / min(pr(2-A)ooee)))
(18)
JRd
Next, we look at z + min(p-(2 A)p(())/4,(3)) For any 2, let ze = 2 2ce. Note that (2,1, = We have
23

---

Accelerated Diffusion Models via Speculative Sampling
that
-min(pr(2e - (
1), ((Za))((Ee)))
min(fr(Ze - (1ll-//lllllllaa::::a/aaaaaadda = ((2()) ( -
((e))
Using this result, (18) and the fact that for any E (l....... d 13. (es, A) = 0, we get
(
za, (z)))())d) O.
Therefore, we get that
B = m (1/0)C+ - m3).
In the rest of the proof, we give an explicit expression for the parameter C+)) We first find 2 such that i (2e || (z)))((z)//p/(4) S (0(z), i.e., find such that log(se(Zze |||l)) I 1og(()-(2e))= i.e, 2e S || In particular, we have that
min(s, (ze - ((11))((()())/////))0)) (z), (((z))
|Aal/2
p(za)dZe / Pr(zo 1All)p(te)/
IAA1/22
(11 + / Pol 11
||A1/2
In addition, we have that
(r (All)p(())//9 = =f 1tte-A/////eep///////0000
Therefore, we get that
[ min( (eai://(e__llllllaa////eeclllad
(1 All/2) + exp (1 -|1 1 4)))
()-
(1 / + exp -
f)).
(19)
Similarly, have that
Ze (in (1000=10)00(2)//pttt)))a ((E)))
R
11a11/2
// Ze (4))
ze ZeplZz))2e
/AAI1/2
11A11/2
fre /|AI1/2
toc
Z0 (06(22)
exp||||| 7 -7)
zopllze ||
IIA11/2
+oc
2c)p(26)
exp|| -)
- (ze AJA|)=-1|A|1// ||A1//)ddz
||A1//2
+ +||1||
- (1 - ||Al/T)dze
|A11/2
/
= =<(IA|I
4)) - 11AAa//////////--000000000/11//0 1)).
expl| T)]p(E, - I1A
//1l//2
= =((AI] - ||||
(20)
24

---

Accelerated Diffusion Models via Speculative Sampling
Combining (19), (20) and (18), we get that
(e. / Rd
za, (2)dz)
(1 2))+ 2++(11A111)
(
2)) + +1A1@(()|1/2)
+ 11A4))ppp/AAP////1113711111111 2))
-- - +)](((((1))
+ 1111// (1 - -141 expl (IAA( -2))
Therefore, We have
C+(I = - T&T ( 1)) + [ (11l1122
+ (11111/) c 2 +) 2)).
can be checked that (+(I)))) 0f and C+(|++I) 2 otherwise. In particular, we have that C+
F.2. Typical acceptance in the Gaussian case
We adapt here the typical acceptance criterion introduced in (Cai et al., 2024) to our setting; i.e. we consider the following acceptance ratio
a min(1. max(g(x))x, (xx) exp (H)))/6)))
(21)
where H(g) is the differential entropy of i.e., H(g) = - Jax ((x) log ((z)dr. The hyperparameters k, > 0 are assumed to be fixed. We recall that g(x) (x; m", o I'Id). In that case we have that
(g)) = (1 log(2n) + +
Now, if we replace the acceptance criterion in Algorithm with (21) and, the sample is rejected, apply a deterministic orthogonal transformation 2 + the Gaussian noise obtain Y, we get that for any C²
B[f(Y) = | la(me + tzz) +o2) + (1 - a(m² +oz))f(m² 0z;
Hence, we get
E(S(Y) = / [a(m" + +zz) + +oz) + (1 a(m" + +zz)) (=)
(a(m² + +z2)f(m² +oz) + (1 a(m= + σ fm) +2))
[N(x - A;
(2; 0,l a(m² o2)f(m² oz) + (1 a(m" + fz))) + tzz) N(2;0,
[N(2 - 0; Id)
O2) a(m + toz) + (1 - a(m + oz)) f(m² + (z;
Therefore, we have
[[((Y)] = / smm8 + oz) (1+
N'2 W(= 112--;:00 1;0,
a(m + +zz) - a(m" + +oē) 0(2;0,1d)e
0,2;0,Id)
G. Projection and extension to operators
In this section, we show that we can introduce an acceptance criterion so that two random variables are maximally coupled latent space. This relaxes the criterion introduced Algorithm In partieular, it possible to reach higher acceptance
25

---

Accelerated Diffusion Models via Speculative Sampling
Probability Density Functions with Varying Temperatures
0.8
Target
Temp 1.00
0.7
Temp 2.00
Probability Density
0.6
Temp 3.00
Temp 4.00
0.5
Temp 5.00
Draft
0.4
0.3
0.2
0.1
0.0
-1
0
2
3
5
Y Value
Figure 5. Effect of the temperature on the distribution of Y. Draft model has mean 1.0 and standard deviation 0.5. Target model has mean 3.0 and standard deviation 0.5.
Algorithm 8 REJECTION (pA. 9A YA) for two Gaussians with same (full) covariance
Require: matrix A, PA (x) = N (zx Am3, o² AA Id), (a()) Nx Am?, Id), YA ~ PA- m9) and eΛ A
Set A (AA -1/2
Let ZA (AAT) - Amm))oo
Sample U 1n.
bool I(U A.,
bool then
Set YA = YA-
else
Set YA Am (AAA (12 - 22A
end
return (YA, bool).
26

---

Accelerated Diffusson Models via Speculative Sampling
rate than with Algorithm 4. Of course, there is price pay for this increased flexibility the variable Y does follow the target distribution ! anymore.
To start with, consider linear operator A E Rddd such that AA is invertible, i.e., A is surjective, In Algorithm 8, we show how to maximally couple two d dimeesnsional densities of the form (x;; Am?, of PAA)) and ((;; Am", o oAAAA)
Algorithm operates directly in the "latent" space, i.c., provides maximal coupling YA) where YA (Ame, AA Idd and YA ~ (Amm, o² AA Iid).
We now present Algorithm 9, which is a non-trivial rewriting of Algorithm 8 operating on the original (Y, YY and thus induces maximally coupled (Yx, YA). In what follows, denote At the Moore-Penross inverse of A defined by
At = A AAAAT)-
The validity of Algorithm 9 is based on the following lemma.
Lemma G.1 (Latent reflection): Let AAT be invertible. Let ÿ = m² + oZ with Z ~ Id),Td). Let Z = (AAT)-1/22)) Let eΛ = Aa/ AA/ where A = (AA 1-1/2 and = (m² - -m9)/o. We have that
Am3 + (AAT) (1de)ex)))) 2e =
m + +0
A - )
(22)
ATA
In addition, we have that
2 ( + A'AA] -N(AA=N((Z A.:00TT)/N((2.0..
(23)
Proof. First, have the following
A(m² m (m" m (AAT) -
= -AAT)) m(mp=m')(mm mmm (AA (AATT-1/27A
-m²)A
=
Hence, we have that
= (AAT) (AMTAAZ-AA
(24)
Next, we have that for any a E RRd
u AA = a AT Au= ])(AAT) 1
(25)
Hence, we have that Combining this result and (24), have
ATA = [I(AAT) 1/2 1/ 11A.13
A m2
oz -- 2 AAAA
} -2 ATTATA
A m -- 2T-22TAAA AATAZAZ ATAATA
4
A m [m
TAT 1 (6- 22-2 A A ATAZ)]
Am +AAA 1 -2AAT)
which concludes the proof of (22). Second, we have that where we have used (25). This concludes the proof of (23).
22) T AÍAA ATA 7T
(Z =( A -
=I(AAT)- -12 +
- + A | 12,
27

---

Accelerated Diffusion Models via Speculative Sampling
Algorithm 9 REJJECTION (p. Y) for two Gaussians with same (full) covariance
Require: Matrix A, p(æ) = "od), (2; m", oTd)), Y p. A = (m² m///
Sample U ~ On 1].
bool = - & min(1, expl(= (A + 22) T ATAA])]
if bool then
Set Y = Y
else
Set = m 222AAAA
ATAIAA
end if'
return (Y, bool).
The main advantage of Algorithm 9 compared to Algorithm 8 is that it only requires the knowledge of A and At and implicitly provide a maximal coupling between YA and Ya. Note that if A is invertible, then we have that A = A-1 and Algorithm becomes identical to Algorithm and thus returns a maximal coupling between Y and Y. However, Algorithm is also applicable when only AAT is invertible. In that case, we do not recover that Y y~ Nxx m o but the algorithm can still be applied and does induce maximally coupled YA).
In particular, given mapping and mapping such that (x)) = x for E Rd, non-linear approximate version of Algorithm 9. In particular, in Algorithm 10, f can be thought of as an encoder and g as a decoder. In the case where (x) = Ar, then A = -(f(A)) A AA. Note that by letting A = -/TT in Algorithm 10, we recover Algorithm 7.
define Algorithm 10, which is
Algorithm 10 REJECTION (p, q. Y) for two Gaussians with auto-encoders
Require: f(g) = N(1; mp, x² Iddd), ((x) (1; Ý p. A = Ammm² - /o. A = (o()(
Sample U ~ Un. 1J.
bool = IIU & exp] (A + 22) T [1)]]]
if bool then
Set Y
else
Set Y = m² to oz(z 2z
end
return (Y, bool).
H. Some Theoretical Results
In Appendix H.1, we establish Lemma 4.2 while we prove Theorem 4.3 in Appendix H.2.
H.1. Control of acceptance ratio
We now provide lower bound on the expectation of the logarithm of the acceptance ratio for speculative sampling. We have at step + 1 that the target density is 4( (Wm) (yn+ti; m?, (Jx). II and, for an independent target model,
the proposal density is p(yn+119m) = =N((n+11 m² (y)m),o where
m4, (v) y + 76 (v),
m (3) = y + 766 (v)
with
o Ii sp sp- (v).
bi_r, (v)
f1 f1-t. +
2 s1-,,, (v), 8i (v) -1--a
2
The acceptance ratio is then given by
N(Z + 1,
an
N(2 (1);0,Id)
28

---

Accelerated Diffusion Models via Speculative Sampling
for Z (d; where
|A,11 4 > -,. s8,,,1
So obtain that
log On - + 1, 1 1112
2
so that
B[log(an)lyn]) ||
Now using Jensen's inequality
- - (IIIA,,11)) 119] B[an] 2 exp[B[logaa.]]] exp
This proves the result.
H.2. Control of acceptance ratio under exact scores
We consider the following setting. Let (X)) for any i E {0, 1] be given by
ax; = fiXid + dd
X mb
where f: 10 and g: [0, [0, +x)) are functions introduced further, T8 and x) are distributions over Fd and (B))e((o11) are d-dimensional Brownian motions. In what follows, we define for any & [0. 1)
ft = 11(1111100
ot = =t/(111 t).
In that case, we have that for any E [0, 1] and i E 10
x = Xx + o.Z,
~~ 100
(26)
with a; and oe We assume that for any E {0,1). mo has density with respect to the Lebesgue measure denoted ph- In that case, for any t [0 and i 10, X; admits density with respect to the Lebesgue measure denoted pt. In this section, show that for any t (0, 1]
f V log) - (1) I C(t, ((: pt),
(27)
such that
1. lim C(t, Pd.Pb) pb)
2. D(pllp)) 0 implics that C(t, p8. pb) + 0, where D is measure of divergence between p8 and ph defined further.
In other words, item 1) shows that the Fisher score between di and pt gets smaller as gets larger expected as o p1. normal density. Item 2) shows that the Fisher score between pi and p is small if p8 and pi are close.
We will also establish in our main result, Theorem H.9, lower bound for the expectation of the logarithm of the acceptance ratio in our speculative sampling setting based on (27).
Time control. First, we provide an upper-bound on the Fisher score that goes to as t + 1. We begin with the following result.
29

---

Accelerated Diffusion Models via Speculative Sampling
Lemma H.1 (Convergence of Fisher score): Assume that JR+ (z)()) CO < too E {0, 1}. Then, have that for any & E (0, 1] and E {0,1}
J | (oggp(<)) - (og & - -1) af
where pı is the density of (0, Id) with respect to the Lebesgue measure. In addition, assume that Sa+ dz = C < +00, we have that for any t E (0, 1] and E {0.1)
[Vlogg((2.)
(x:))) s 3( -,, o,) +a,01 Gaî( Cij
s 12 df + Cg
Proof. Let E (0,1). 1}. First, using Tweedie's identity, see (Vincent, 2011) 1) for instance, we recall that for any E (0, 1), we have that for any 2e Rdd
V log p(,)) = f llog Poo(ploo))))) Poje (xoll
= =E[ -EI-21 2/a, X; st,,
where we recall that x: = Xi + oz see (26). Hence, using Jensen's inequality, we have that
V (ogg((())) v loger (xx))
|||| E X x
[F[I( az ox) 02 X ||
< ( oo )z 2 ز + af
where we have used that X and Z are independent. Finally, using E | 2| d, we obtained the first result. The second part of the proof is similar and left to the reader.
We recall that for any a 2 1 the Xa divergence between two densities over Rdd, p. is given by
(a(plg) / (1 p(z) ) g(z)dr. ((x))
If a = 2, we also have
Xa(plg) = p(x)² dr 1.
(28)
Rdd q(x)
In addition, we have the following useful result.
Lemma H.2 (Xa -dat processing inequality): For any a 2 1, t E [0, 1], (r(lp) s (a(l)bb))
Note that this data processing is fact valid for every f-divergence with f convex. Combining Lemma H.I and Lemma H.2, we have the following result.
Lemma H.3 (Convergence of modified Fisher score): Assume that Sge ((/l()) C₁ < +00 for E (0, Let C4 = max(Ca C)). Then, we have that for any E (0, 1]
f (Vlogp((z) log (x)))d < 4(1 + (2(( - - + o²c1/2)
where pı is the density of (0, Id) with respect to the Lebesgue measure.
30

---

Accelerated Diffusion Models via Speculative Sampling
Proof. For any E (0, 1), let A, Ja V (ogg)((<)) (oxp Using the Cauchy- inequality and (28), have that for any E (0,
V loggp (x:)) ( (((())
2
12
Pi (zze (are)dar)
Rd
P. (x,)
(x1) dra
(Vlogl V (o (r))
(1()))
gd
[VVlogp( ) (x.))dr + x2(1((p)))
We conclude upon combining Lemma H.I. Lemma H.2, the fact that for any a, 2 0, va+b s va vb and that max(v122 v < 4.
Finally, combining Lemma H.3 and Lemma H.1, we get the following result.
Proposition H.4 (Control of Fisher score (I)): Assume that SRa || = Ci < too for E 10,13. Let
C4 max(C4, C)). Then, we have that for any E (0,
JeL |V (Vlogg((a)))
(a:)) s 10(1 v2(v -0.-- + o2/)112)
Proof. For any & E (0, 1), we have that
V log - V Vlogr/ (2
Rd
$
Vloop v log (1) )zz
Rd
V Vloggl V (x:)) (x.)
We conclude upon combining Lemma H.l and Lemma H.3.
In particular, Proposition H.4 shows that lim,-1 Sg | logrl( v (x:)) (p) 0.
Measure control. We now provide control the Fisher score that depends on some divergence between the measures T and m.. We first recall useful result the score which can be found, for instance, in (De Bortoli et al., 2024).
Lemma H.5 (Target Score Identity): Assume that for any i E (0, 1), pà E (TRdd, IRd) and for any E [o, 1] and 24 Idd, Sa || log (oo)((r)))l (zolzz; ddzo < +00. Then, we have that for any e [0, t [0, 1) and xt Rdd
V Voogp/ 1 / Pl (xo )dz.
Next, show the following result.
Lemma H.6 (Posterior control): We have that for any 2, a even and ( 10,1)
[ Xa (x0 (o.
S (x.o (x.1() + xan (b)
with
3 Do,a 2 2( X2a (pbl)))))) + x2
31

---

Accelerated Diffusson Models via Speculative Sampling
Proof. First, have that for any 2, a even and & (0,
J&c Xx (P (20 ( (20) (2x)dæz = JRAXRA
(1 (1-
(ole() (xala)))))
(20, Ia drodd
-1 1x -
p
=
po. (20, 24 dxddd,
I 2--1
{ (1
1-palra) po(2a))
po(2o)doo
Ju
+ 20-1
{
(1
p. ((()))) p)
a Po,e (0,, (4 de)drodd. )
(P)(z))
Rdd
Rdd
2 (xo(pbl// pb)) + 2a-1
phlzo) Pi(za)
(1
(m()))
Po, in dxxdde.
0
(29)
Rd
Next, we note that for any B 2 1, 3 even and densities p.q
[ec
[(x) p(z)
9 p(x)dx 220 x=((lp))
Using this result and (29), have that
1 Xa (a(Ppj (x)
[ JRARRd
$ 2 1----xx xa + 2a-1
phlan) Po(a)))
(1
(axe) p((e))
( (1 droddz
2a-1
(fpe (1-
1/2
2 xa(xb1) + 2a-12
2 (1 (2a
Pe (((
<2- x. + 22a
2 + X2a
3
(p pblp 1/2
(/L (1
(((a)) (ma)
pl )x pi )dx
< x2 2 1/
X2
(p)lp)))
2 xa + 22 (1 X2. (10++
2 X4a (polp)) 1/4 + 220 2 |
< 2 2(1 X2a (p (2)) 1/2 (2 + ( pb) (p6118
where we used the data processing inequality. This concludes the proof.
Finally, for case of notation, we introduce for any E [0, 1]
FI(p!lp:) = f |Vloog V
We obtain the following result.
Proposition H.7 (Control of Fisher score (II)): Assume that for any i [0,1), pà C² CRdd, Rd) and for any e 1] and E Rd, [ga ||V ló (zu) llp (Zol 1z) < +oc. In addition. assume that for any i E {0.
fg. (Zoogá((z))) (F dr( D < +00. Then for any E [0, 1), we have
[ V (xx) Vlog (xx) ( (x.))) <
(FIcpll)))) + x1ele 22)/11)))1/8)
of
where D is explicit in the proof.
32

---

Accelerated Diffusson Models via Speculative Sampling
Proof. For any / E (0,1), let A, f24 TeaaIVVoogee (Vlg (1 any E (0,1)
Using Lemma H.5, we have that for
V log pog )dvoo | Di (xx
V log Poggr (0 ( (x /
A 0i Bd
Hence, for any t E (0, 1), A. = (A) + Az) with
A
v log ( )
V log 1og )dzo
pi (cr))
Rd
12d
43
log (ogg
(
Using Jensen's 's inequality, we have that for any E (0,1)
1 S JRd
IV [Vlorg((r)) V log
(30)
Second, using Jensen's 's inequality, the
inequality and Lemma H.6
A -
V Poog
(1-
(xul(e)) Poje (xol2z))
po,r (zo, 24 dx)do.
Rdd
1/2
(1 RRXXR (1-
1/2
(ool(e) (2otee)) )
pú. (200 (20. as dadgde
< 1/2 (Fs (Vlogr P((
1/2
(x16(1blp)) + x16(281pb)119)
Combining this result and (30) concludes the proof with D = 2(1 + D// max(D2,
Finally, combining Proposition H.4 and Proposition H.7, we get the following proposition.
Proposition H.8 (Control Fisher (III):: Assume that for any E {0, p C² Rd) and for any e 10,1] and Rd. Je ||V log (zo))llp ( (ro too. In addition, assume that for any i {0,1}, Sg. log pà (=o))l (11((((()))))) (z0) + +P (2o))do = DÅ < +o0. Assume that Sgs (l])) = C₁ < +o0 for E 10, Then, we have for any E 1)
[ | lVoogi - v (1)
C
( + a²; + (FI(p80p)) + xio(pble)) + x1o(e8 1b)
where C > 0 can be made explicit.
Control of acceptance ratio. We now provide lower bound on the expectation of the logarithm of the acceptance ratio in the speculative sampling framework. We consider discretization of the interval [0, 1] given by K N and t. = k/ K. We let 7 1/K. We consider the target model given for any {0, K - 1} by
Yia = Vi + f1-, Vt +
1+=² 2
oi V Vlogr pf (Yx) + - Zi
Yo ~ N(O,
where (Zf) iid.
(d) We now Ko (0, N - 11. N, k2 = min(N 1, + L - 1) and consider the draft model associated given for any l E (ku, kL} by
yd = ye + 7 f1 yd 1t 1+2
++''Vlogn
Vlogrt + V Zd
yd vt ~ ~O,
33

---

Accelerated Diffusion Models via Speculative Sampling
where kEN Lid. (00, Id).
The step kn + 1 is accepted if S min min(1,,V(Z2, + Id)) Id)) with
1 A ko 1== 7e(e+ =
19 V tkp (%% logrl-e, (1
So obtain
Bloog( (kk)] - A [1²].
Combining this result with the previous Proposition, obtain the following result.
Theorem H.9 (Control of log-acceptance ratio): Assume that for any i E {0,1}, pà E C* (R)) and for any [0, 1] and i, E Rd fo || log (=) (=)
toc. In addition. assume that for any i {0. 1}, pı (xo) )doo D < +00. Assume that Saa (l=]\/)mmb())) C² < +00
Sga V Po (p addition, assume that k ~ P1- then
foo for E {0, 1}. In
Ellog(ako))
8 (s (s+
199 min (Gt.
a + (FI(p[lpb) xio(vble)) + X1o xio (Po())))))/
where 80
tko and C 2 0 is explicit in the proof.
The final result is obtained by using Jensen's inequality, i.e, E[axo] 2 cxp/E]log(**,.].
Let us interpret Theorem H.9. We aim at maximizing log(aso) since high acceptance ratio yields lower computational cost of the speculative sampling method. We here give lower bound on its expectation. There are different factors that influence this bound:
7 > yields E(log(ax,)) ) 2 0. Hence small discretization step is associated with better acceptance of the method. However, emphasize that a small discretization step also gives a larger total number of steps. Hence the benefits of reducing the stepsize must be weighted by the additional computational requirement of having to run the speculative procedure for a larger number of iterations.
If -> pb (in Fisher and divergence) then Ellog( (ox,)) ) 2 0. This means that if during speculative sampling, the two models target similar distribution then we obtain a higher acceptance rate. This remark is verified empirically in and echoes similar findings in LLMs (Cai et al., 2024).
If g² (( - a3) + 0 as t + 1 then Ellog(aa,) (ax.)) )1 2 0. Hence, in that case for low values of Ko. i.e., at the beginning of the denoising process, the acceptance rate is high. This observation is also confirmed empirically and is specific to the diffusion model setting.
In our setting, we have
0. 1 - o0)2 +af) 26(1 - (1 + (1 + 1/t)3).
Hence lim,-1 S( 0,)² a - We showcase the A(t) gf((1 0.)2 + af) in Figure 6.
= 0.
Experimental details
In this section, we provide details about our experimental setup Appendix I.1. Our setting for the low dimensional Gaussian Mixture Models (GMMs) is described in Appendix I.2. Similarly, our setting for the image experiments given in Appendix L.3.
34

---

Accelerated Diffusion Models via Speculative Sampling
200
150
125
100
75
50
0.2
0.4
Figure 6. The value of A(t) as function of for 0z = 1 - and d. = t (bluc). The value of A(f) for oz = cos(( and a, (in(()/)) (orange).
L.. Experiment setting.
In our setting, consider the stochastic interpolant framework (Albergo et al., 2023) for greater flexibility. Namely, consider noising interpolant given by
X: = 0x o,X1,
Xo me, X Id),
(31)
where t ++ at is a non-increasing function and t + o, is a non-decreasing function so that a1 0, 01 1. The interpolation (31) can be associated with the following forward process
dX. fiX,dt + g.dB.,
(32)
where for any E (0.
f: 0g log(a:),
gi = 2010a)
The time-reversal of the noising process (32) is given by (Y (Yt)uEjo.1) which satisfies
dY. fh---YY, +f - Vlogo-
Yo
(33)
where is the density of X, with respect to the Lebesgue measure. In practice, we do not typically know and let Yo ~ N(0, If). For given hyperparameter 0, one can also consider
dY, { -f- + (1 + $² g6r logpi-.(Y.)) dtt Egg
(34)
which has the same marginals as (33). This can also be rewritten
dY. - -i (o )dl EgI dd.
(35)
where the so-called velocity V. is given by
(x(x) = ElO;a, + 8, X, = z].
Upon combining (34) and (35), we have that for any t (0, 1)
2
v (x) EX X, = 21/0;
= - (fæ - (x(x))
(36)
St
In particular, in order to estimate the score function, we only need to estimate the velocity and vice-versa. In practice, we consider the following loss function
Co = w,Elll,,,,,, + 0,0,X, (x))(
35

---

Accelerated Diffusson Models via Speculative Sampling
where w, > 0 is weighting function, see Esser et al. (2024) for some possible choices for wt- We denote se the score estimated from vo using (36). At sampling time, we consider the Fuler-Maruyama discretisation of (35). More precisely, we define some timesteps { with 0 = to < ti < < tN- = 1 and consider the following Markov chain
Yx+1 = Vi + 7h 10 pooffo.110
1 1e (Vr) + 2 - 00 (Yw)) + Theg Zko
(37)
where (Zx) is a sequence of independent and identically distributed Gaussian random variables with zero mean and identity covariance matrix and = f fg. When additional conditioning information is available, one can consider an additional guidance term and (37) is changed into
Yk+1 Yk + 78 ( (00,,1u () ò0e,1 (Yu, 0) + 1 2º
- ( ( + Vruegi Zk.
where vo,((,c) c) corresponds to a conditional model and vo,e(- 0) to an unconditional one.
I.2. Low dimensional experiments.
In our low-dimensional setting, we create a dataset by sampling from a mixture of Gaussians. The means are sampled uniformly and independently from [-2, 2jd, where d is the dimension. Each Gaussian component has a covariance matrix of the form I'Id, where the standard deviation o is also sampled uniformly and independently from [0.1, 0.2). We test across dimensions d {2, 4, 8, 16, 32} and numbers of components n E {1, 4, 8, 16).
The velocity of the diffusion model is parameterized with sequence of MLPs. For all MLP we use the GeLU activation function. The label, corresponding to the component of the mixture is encoded using a layer embedding layer with feature dimension 512. Similarly, the time information is encoded using sinusoidal embedding with feature dimension 512. This encoding is then processed with a MLP with output dimension 512. The time embedding and the label embedding are then concatenated into a conditioning embedding. The conditioning embedding and the input z₁ of the velocity network are then processed independently with MI.P layers with output dimension (64, 64, 128). The obtained embedding are then concatenated and processed with MLP layers with output dimension (128, 64, 64). Finally a last dense layer with output dimension d is added. We do not consider any normalisation layer. In the case of the training of an independent draft model, the three preprocessing MLP layers are replaced with one MLP layer with output dimension 4. Similarly, the three postprocessing MLP layers are replaced with one MLP layer with output dimension 4. For the sampling, we use 250 sampling steps. We refer to Appendix for additional results.
I.3. Image experiments
All FID and IS scores are evaluated with 50, 000 images.
The shape of the samples in the training dataset is (32 x 32 x 3). The batch size is set to 128. Images are rescaled between -1.0 and 1.0. We consider augmentation pipeline similar to the one of (Karras et al., 2022). The augmentation pipeline is applied with a global probability = 0.12. The rest of the augmentation pipeline is similar to the one used in (Karras et al., 2022). In particular, we consider flipping (both x and y axis), anisotropy transformations, non-integer rotation, scaling and non-integer translation.
CIFAR10.
For the model, we consider a U-net architecture with GeLU activations, levels with residual attention block applied on the second level. The channel multipliers are given by 2,, 2). The channel size is 256. We consider dropout rate of 0.2. The normalization layers are RMS normalization layers. For the attention layers consider 8 heads. The number of residual blocks is 2. For the skip connection, we add (and normalize) the current activation with the stored activation. The time is embedded using sinusoidal embedding with hidden dimension 256. We embed the 10 different classes and consider conditional models. We also condition the model on the augmentation vector. These two conditionings are added and the time embedding is added on top of this. The conditioning occurs through adaptive normalization layers. We train the model for 1M steps with the Adam optimizer and learning rate of 10-4 and EMA decay of 0.9999.
LSUN. We consider the same configuration as CIFARIO. However, the samples do not have label and we only consider the augmentation conditioning.
36

---

Accelerated Diffusson Models via Speculative Sampling
1.4. Latent CIFAR-10 experiments
In the first stage, as an auto-encoder, we use variational auto-encoder (VAE) (Kingma & Welling, 2014) with a smaller term on the KL-term as in 3-VAE (Higgins et al., 2016). The encoder and decoder represented by U-Net where in encoder, U-Net follows only the downsampling and middle bottleneck paths, while in decoder, U-Net follows middle bottleneck and upsampling paths, which is similar to what is used in (Rombach et al., 2022). We use 128 channels for the corresponding U-Nets without attention in downsampling/upsampiing but with attention in the middle (1 head) and with channel multipliers 21, 4, 4). We use SILU activation function. We also use RMSNorm for normalization as opposed to GroupNorm. We also employ perceptual LPSIS loss (Zhang et al., 2018) with coefficient as well as patch-based discriminator as in (Esser et al., 2021). The dimensionality of the latent space is (4, 32) which is times smaller than the original CIFAR-10 image dimensionality (32, 32, 3). We train the autoencoder for 500000 steps. We track the FID on the subset of 12800 images comparing clean images and the reconstructions de decoder (ecoer((nnodee(m1) smallest FID. The selected hyperparameters as well as their ranges are:
and select hyperparameters which achieve the
Number of discriminator filters = 32. Range [32, 64, 128).
Number of discriminator layers 6. Range [3. 6, 9).
Dropout rate for both encoder and decoder 0.0. Range [0, 0.1, 0.2,
3 parameter 1e 6. Range [1e 4, 5e 5, 1e 5, 5,5e 6, le
6,5e 7, le 7].
Generator loss coefficient 0.01. Range [0.001, 0.01, 0.1, 1.0].
Adversarial loss coefficient 0.001. Range [0.001, 0.01, 1.0
Batch size = 1024. Range [128, 256, 512, 1024]
For the second stage, we freeze the encoder and decoder and train a diffusion model on the encoded images (we take the means), similar (Rombach et al., 2022). We use the U-Net with 256 channels, (2, 2) channel multipliers with attention performed (False, True), with attention in the middle with 8 attention heads, RMSNorm, GeLU activation. We train latent diffusion for 160000 iterations with batch size 256, We track FID on the subset of 12800 to select the hyperparameters, The selected hyperparameters as well as their ranges are:
Prediction target- = Zg. Range rp or velocity
U-Net dropout rate = 0.0. Range 0,0.1, 0.2, 0.3].
Learning rate = le - 4. Range [1e - 3, le -0--4.. - 55 5]
Noise process type = cosine. Range linear, cosine, rectified flow
Once the models are trained, we employ the same sampling strategy as CIFAR- experiment.
L.5. PushT dataset.
We consider the PushT dataset. The task here is to push 7 shape onto a target shape on a two dimensional plane. The action dimension 2, the action horizon is 8. We keep an history of length 2 and consider a maximum 300 steps when unrolling the policy. We consider a prediction horizon of length 16. This means that the dimension of the target 16 2. And we condition on the last two previous states (dimension is 5). Hence the conditioning signal has shape (2 x 5). Once we have predicted 16 actions reward reaches one, i.e., the 7 shape is perfectly aligned.
execute of them. As specified before execute maximum of 300 steps stop if the
We train the model for LM steps with Adam and stepsize 10 We consider a one-dimensional U-net with time embedding. The architecture follows from (Chi et al., 2023).
At inference time, we rely on the DDPM sampler.
37

---

Accelerated Diffusson Models via Speculative Sampling
J. Additional results
We run similar experiments in latent space to showcase the flexibility of our method. We follow the approach described in (Rombach et al., 2022) we pre-train an autoencoder on the whole dataset and then train diffusion model on the latent-encoded dataset. We consider the latent space of shape (4 4 x 32) which is times smaller than the dimensionality (32 32 x 3) of CIFARIO. We refer Appendix 1.4 for architectural and training details. We report FID score computed on 50k training samples. Our results are reported in Table 4. We found that using latent diffusion on CIFAR-10 10 achieved better FID score when the target used only 30 sampling iterations. Nevertheless, we see that our speculative sampling method still provides 3-x speed-up (best is NFE) while maintaining similar to target model quality. We also considered using target model with only 10 NFEs and Table 4 suggests that it achieves considerably worse results. This highlights the strength of our approach.
Combining speculative sampling and parallel sampling. We report FID score and NFE for CIFAR-10 with a number of steps of 30. We vary the temperature parameter т, the churn parameter well the number of parallel iterations, (Shih et al., 2023; Tang et al., 2024). For each combination of hyperparameters we also consider window sizes 5, 10 and 20 and report the best run (in terms of FID).
The original speculative sampling procedure corresponds to po 0. The best FID number that can be achieved with this configuration is 2.23 with a NFE of 15.69. However, by combining our speculative sampling procedure with parallel sampling then we can reach a FID of 2.07 with a NFE of 15.42. This shows the benefits of combining our speculative sampling procedure with other acceleration methods. We report those results in Table
Combining speculative sampling and step distillation. We now compare approach with LD3 (Tong et al., 2024) and (Sabour et al., 2024). We compare the results on CIFAR-10 reported in LD3 (Tong al., 2024). Our best speculative sampling method outperformed both LD3 and AYS. We also included our best results obtained with uniform timesteps spacing and EDM timestep spacing (Karras et al., 2022). These results are based on the same model as "Best speculative". We sweep over = [1.0, .... 8.0] in the case of EDM timestep spacing. This improves the quality of the samples but they remain inferior in quality to the ones obtained with our best speculative model. We re-implemented LD3 (Tong et al., 2024) in our setting and used it to learn a timestep spacing. Our setting similar the one of (Tong al., 2024). Finally, we compare our approach with distilled generator trained on top of our best model. We focus Multistep Moment Matching Distillation (MMD) (Salimans al., 2024).
Configuration
FID
NFF
DPM Solver++ (naive reported)
2.37
20
DPM Solver++ (AYS (Sabour et al., 2024) - reported)
2.10
DPM Solver++ (LD3 (Tong et al.. 2024) reported)
2.36
20
Uniform timesteps
7.14
15
EDM timesteps
4.22
15
LD3 timesteps
3.49
15
MultiStep Moment Matching
2.76
15
Best speculative
2.07
15.4
Table Comparison model configurations, including our best speculative methods against several baselines. The top section shows reported results from prior work, while the bottom section details our experiments.
K. Accelerating Langevin Diffusions using Speculative Sampling
We detail in this appendix the application of speculative sampling to Langevin diffusions proposed in Section 5, Assume where we are interested in sampling from an unnormalized density π (Ix) on Rd, i.e.
cxp(- cxp(-E(x))
z f exp(( exp(-E(())drr,
x (z)
where the energy function E(x) can be evaluated pointwise, but each evaluation is computationally expensive, and is an intractable normalizing constant. We are interested here in accelerating MCMC sampling in the context where we have
38

---

Accelerated Diffusion Models via Speculative Sampling
Configuration
Draft
Target (30 steps)
Target (10 steps)
Speculative
FID
1S
FID
HID 4
HDD 1
1
0.01, r 0.5
80.92
5.39
2.67
11.09
39.48
7.42
2.66
11.13
18.53
0.01,
0.01, 2.0
80.92
5.59
2.67
11.09
39,48
7.42
2,66
11.14
17.09
0.25, 7 0.5
82.28
5.50
2.64
11.15
87.39
4.82
2.68
11.18
10.37
= 0,25, 7 1.0
82.28
5.50
11.15
87.39
4.82
2.60
11.23
9.36
0,25,
82.28
5.50
2.64
11.15
87.39
4.82
2.66
11.21
8.36
0.5. 0.5
83.27
5.42
2.51
11.08
118.78
3.81
2.56
11.11
9.35
0.5, 1.0 2
83.27
11.08
118.78
3.81
2,50
11.12
8,30
0.S.
118.78
2.52
11.07
1.0, 0.5
97.67
4.72
37.54
7.09
182.94
2.43
37.13
7.11
9.57
8 1.0, 1.0
97.67
4.72
37.54
7.09
182.94
2.43
37.85
7.07
8,36
1.0.
Table Latent diffussin on CIFAR-10 with window size = 15 for speculative sampling. For each column, we report the best result in bold.
Configuration
Draft
Target (500 steps)
Speculative
FID 4
FID 1
IS
FID
IS
NFET
0.005, r 0.25
5.76
1.93
4.66
2.02
4.69
2.01
305.30
8 0.005, 0.5
5.76
1.93
4,66
2.02
4.68
2.01
286.07
0.005,
5.76
1.93
4,66
2.02
4.70
263.56
0.005, 2.0
5.76
1.93
4.66
2.02
4.72
2.01
238.01
0.01, 7 = 0.25
5.76
1.93
4.66
2.02
4.65
2.01
257 96
F
0.01, 7 1.0
5.76
1.95
4.66
2,02
4.69
2,00
211.47
0.01, T 2.0
5.76
1.93
4.66
2.02
4.76
2.00
184.98
0,05, 7 0.25
5.9
4.66
2.01
4.48
2.02
136.63
0.05. 0.5
5.97
1.91
4.66
2.01
4.53
2,00
164.07
0.05, r 1.0
5.97
1.91
4.66
2.01
4.62
2.01
140.06
0.05. r 2.0
5.97
1.91
4.66
2.01
4.86
1.99
116.38
176.02
0.1.7 0.5
6.46
1.91
4.32
2,00
4.38
2,02
134.73
5 0.1,7 1.0
6.46
1.91
4.52
2.00
4.56
1.99
131.47
0.1.7
6.46
4.52
2.00
4.79
0.25, 0.25
10.11
1.96
4.13
1.96
3.94
172.65
= 0.26, 7 0.5
10.11
1.96
4.13
1.96
3.98
1.97
153.05
= 0.26. T 1.0
10.11
1.96
4.13
1.96
4.24
1.97
130.71
T
10.11
4.13
4.53
107.92
0.6, = 0.25
17.53
2.11
4.18
1.96
4.02
1.96
478.45
0.5, 0.5
17.53
2.11
4.18
1.96
4.02
1.95
160.68
0.5.
0.5. 2.0
17.53
2.11
4.18
1.96
4.51
1.93
116.33
Table LSUN with window
50, no last step function, 500 steps. For each column, we report the best result bold.
39

---

Accelerated Diffusion Models via Speculative Sampling
Configuration
Draft
Target (200 stops)
Specnlative
FID..,
IS
FID
IS
FIF.
IST
NFF.
0.001, 0.25
1.89
3,99
1.98
176.85
0.001. 0.5
10.56
1.89
3.99
1.99
1,98
173.49
0.001, 1.0
10.56
1,89
3.99
1.99
3.99
1.98
168.23
0.001, r 2,0
10.56
1.89
3.59
1.99
3.99
1.98
160.89
0.25
10.38
1.89
4,02
1.98
137.95
0.005. 0.5
10.58
1.89
4,02
1.56
3.99
1.96
131,55
0.003, 7 1.0
10.58
1.89
4.02
1.98
3.99
1.98
124.52
0.005, r
10.58
1.89
1.98
117.13
0.01, r 0.25
10.63
1.89
3,59
1,96
3.98
1.96
121.26
0.01, = 0.5
10.63
1.89
3.99
1.98
3.98
1.98
114.51
0,01,7 1.0
10.63
1.89
3.59
1.98
3.99
1.98
107.26
0.01,
10.63
1.89
3.99
1.98
4.01
1.98
99.20
0.05, 7 0.25
12.73
1.91
3.95
1.98
3.94
1.98
92.66
5
0.05, r 0.5
12.73
1.91
3.95
1.98
3.96
1.97
86.26
1.91
3.95
1.96
78.75
0.05, 2.0
12.75
1.91
3.95
1.58
4.14
1.95
70.04
5
0.1,7 = 0.25
18.56
1.99
3.92
1.99
3.89
1.97
87.74
0.1, 0.5
18.56
1.99
3.92
1.99
82.05
0.1. 1.0
18.56
1.99
3.92
1.99
3.97
1.98
74.87
0.1. 2.0
18.56
1.99
3.92
1.99
4.16
1.94
66.22
0.25. T 0.25
33.76
2.28
3.83
1.94
1.96
.0
0.25,
33.76
2.28
3.83
1.94
3.74
1.97
80.82
0,25, 1.0
33,76
2.28
3,83
1.94
3.94
1.95
74.27
5
0,25, r 2.0
33.76
2.28
3.83
1.94
4.12
1.94
66.01
49.82
4.09
1.95
0.5,
49.82
2.65
4,09
1.95
3.97
1.95
83 29
U.S. = 1.0
49.82
2.65
4,09
1.95
4.14
1.93
77.55
6
0.6, 2.0
49.82
2.65
4.09
1.96
69.81
1,0, 0.25
115.98
3.44
4.76
1.93
4.75
1.95
93.13
2 1.0, 0.5
115.98
3.44
4.76
1.93
4.73
1.97
90.88
c 1.0,
1.0
115.98
3.44
4.76
1.93
4.77
1.96
87.24
2.0
115.98
3.44
4.76
1.95
81.40
Table LSUN with window size 50, no last step function, 200 steps. For each column, we report the best result bold.
Configuration
Draft
Target FID
steps)
Specnlative
FID 1
IS
IS
FID
IS
NFE
0.001, 0.25
24.04
1,99
0.001, 0.5
24.04
1.99
3,81
1.95
3.79
1.95
90.57
0.001. 1.0
24.04
1.99
3.81
1.95
3.79
1.95
88.56
0.001. 2.0
24.04
1.9
3.81
1.95
3.79
1.95
46
0.005, 0.25
24.26
2.00
3.81
1.95
3.78
1.95
73.13
0.003, 0.5
24.26
2.00
3.81
1.95
3.77
1.95
70.13
0.005, r 1.0
24.26
2.00
3.81
1.95
3.77
1.95
66.67
0.005,
24.26
2.00
1.95
63.10
0.01. 0.25
25,05
2.01
3.80
1,95
3.37
1.54
65.75
0.01, = U.5
25.05
2.01
3.80
1.95
3.37
1.94
62.68
0.01,
25.05
3,80
1.94
59.39
0.01,
25.05
2.01
3.80
1.95
3.77
1.94
56.71
0.05, 7 0.25
48.62
2.27
3.75
1.96
3.75
1.94
52.44
0.05, r 0.5
48.62
2.27
3.75
1.96
3.76
1.93
50.07
2.27
3.75
1.93
47.57
0.06, = 2.0
48.62
2.27
3.75
1.96
3.85
1.93
44.52
0.1,7 0.25
69.55
2.53
3.74
1.95
3.78
1.94
49.65
0.1,
69.55
2.53
1.94
47.75
0.1. 1.0
69.55
2.53
3.74
1.95
3.79
1.93
45.51
= U.1.7 = 2.0
69.55
2.53
3.74
1.95
3.86
1.91
42.52
0.25, 5 0.25
97.47
3.17
3.85
1.93
48.11
0,25,
97.47
3.17
3.83
1.92
3.82
1.54
46.76
0.25, 1.0
97.47
3.17
3,85
1.92
3.81
1.93
44.92
0,25, 2.0
97.47
3.17
3.85
1.92
3.90
1.92
42.16
147.36
3.62
1.95
48,38
U.S. 0.5
147.36
3.62
4,08
1.97
4,06
1.96
47,43
0.5.T 1.0
147.36
3.62
4.08
1.97
4.14
1.95
46.02
0.5, 2.0
147.36
3.62
1.95
1.0, 0.25
231.66
2.74
5.76
2,02
5.72
2.00
50.08
1.0, 0.5
231.66
2.74
5.76
2.02
5.69
2.00
49.59
8 1.0, = 1.0
231.66
2.74
5.76
2.02
5.70
2.01
49.00
2.0
231.06
2.74
3.76
2.02
2.02
47.89
Table LSUN with window size 50, no last step functions, 100 steps. For each column, we report the best result bold.
40

---

Accelerated Diffusion Models via Speculative Sampling
Configuration
FID
NFE.
p 0,2
0.25, r
10
2.23
13.69
p=
0.23, 1.0
2,09
23,80
p=
5,4
0.25,
10
2,09
57.85
p= 0,5
0.5,T
1.0
2,77
17.06
P p=
0.5.T
23.42
P 5,8
0,5,1 1.0
2.75
57,80
p 0,2
=
0.25,
2.0
2.24
14,89
p=
1,e
0.25,7 2.0
2.09
21.12
0.25, 2.0
2,08
51.45
0,5
0.5, 2.0
2.74
16.47
P 1,c
=
0.5,T 2.0
2,77
20.62
p=
0.5.T 2.0
p=
0,25,
10.0
2.39
12.86
p
1,5
0.25, T 10.0
2.07
15.42
p=
6.6
0.26,
10.0
2.07
37.50
0.
10.0
2.73
14.49
1.
0.5.7
10.0
2.79
16.38
p= 5,6 0.3,7
10.0
2.79
40.25
Table Results on CIFAR-10 when combining speculative sampling and parallel sampling. The hyperparameter represents the number of parallel calls.
access to a computationally cheap proxy energy function E(x) R E(x) defining (xx) x exp(-B(x)). Access to such proxies is common many domains of computational science and engineering, see e.g. (Peherstorfer et al., 2018) for review.
In this context, popular modification of the Metropolis- M (MH) algorithm to sample from π leveraging energy proxy was proposed by Christen & Fox (2005). It is known in the literature as delayed acceptance MH (Cui et al., 201 I; Sherlock et al., 2017) or two-stage Markov chain Monte Carlo (Peherstorfer et al., 2018). We present here completely different approach to accelerate another popular MCMC algorithm, namely the Unadjusted Langevin algorithm (ULA).
The Langevin diffusion defined by
dx, VX,,) + V2dB,,
where (Bt) is standard multivariate Brownian motion. The limiting distribution of this diffusion is æ. Practically, discretize this diffusion to obtain the ULA algorithm, i.e.
X X >VE(X.) + W
(38)
for stepsize y > 0 and W lid. Id). Contrary to MH, this algorithm only samples from an approximation of due the line-discretization but explicit bounds on the bias incurred are available (Durmus & Moulines, 2017). The speculative sampling algorithm is directly applicable to accelerate the simulation of (38). In this case, (38) plays the role of the target model while
X = X - - ~V + 2
(39)
corresponds to the draft model. In this case, the general speculative sampling from Algorithm simplifies drastically and we obtain Algorithm 11. As cheap proxy, we can still use the frozen draft model strategy in this context, that is set [=(+++) = V E=x,) for k = 1, ..., n2 in (39). Again speculative sampling returns exact samples from ULA. This method can be thought of as novel pre-fetching technique to accelerate MCMC (Brockwell, 2006; Angelino et al., 2014).
We now demonstrate the efficiency of Algorithm 11. We consider the á model (Guth et al., 2022; Milchev et al., 1986)
where the energy function is given by
E(x)
8
Σ< (a. 22,² |(]|=1
Σ (o) 1)
on grid of shape (8, 8) and /3 100. Sampling from is complex this requires sampling so-called ordered states. In this context, the teacher model is the Langevin diffusion sampling E(x) with 100, 000 iterations and stepsize 10-3, while our speculative sampling algorithm uses the frozen prediction draft model and a window size of 20. We report the mean and the standard deviation of the energy over the last 500 simulated samples over 500 runs. The NEE is reduced by factor of 2.

---

Accelerated Diffusion Models via Speculative Sampling
Metrics
Mean energy
Standard deviation energy
NFE
Langevin sampling
62.27
13.32
100000
Speculative sampling
65.90
12.48
48564
Table Comparison of sampling metries for the 4 model.
Algorithm 11 Speculative Sampling for Unadjusted Langevin Diffusion
Require:
Lookahead integer L, sequence length K, stepsize 0, target distribution and proxy distribution ft Set Yo arbitrarily and set n O.
while < K do
Set Yn +- Yn and nı = min(n + L, K).
for = n + :: n2 do
Set V 8- - 7 + -2 for 7k-1 NV Id).
end for
In parallel, compute VE(Ýn), V 2+1) VE(L VE((n
for k + 1 nz do
Set A = v///2
- vB(Y--1)) and e A
Sample 0 ~ Unif(0, 1).
bool = T(U <
if bool then
Set Y/2 Yg.
else
Set Yv:- 17-1-7E(('r)) + /27(Id 2cc ) 7
-
end if
return
(Y,. bool).
not (bool) then
Exit For Loop
end if end for
Set +- k. end while
return Yo.k
42


Reviews:
[{"review_id": "v8FBbQXd6b", "reviewer": "Reviewer_E771", "summary": "This work introduces a speculative sampling method for efficient diffusion models using reflection maximal coupling. Instead of relying on a separate draft model, they propose an approach that generates drafts directly from the target model. A complexity analysis establishes a lower bound on acceptance ratios. The experiments show speed-ups in image generation and robotics policy generation tasks.\nThe rejection implementation proposed leverages the coupling between two Gaussian distribution with different means but identical variances applicable to diffusion models. \n\nA relevant problem statement.\n\nThe manuscript well written. Captions for the tables can be improved. \n\nSupplementary material Section C – Algorithm 7. The return statement on Line 980 is probably incorrect.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their positive assessment of our paper. \n\n> The approach assumes parallel evaluation allowing lower latency, but the method increases compute and memory requirements, which are also critical components that are not handled by the approach. \n\nOur approach indeed trades memory for latency. We believe this trade-off is advantageous for certain applications. For example, in applications requiring extremely low latency, increased memory consumption is often acceptable. Note that this fact is also emphasized in [1] “Currently, for large models like SD, ParaTAA requires the use of multiple GPUs to achieve considerable speedup in wall-clock time. Nonetheless, as advancements in GPU technology and parallel computing infrastructures evolve, we anticipate that the cost will be significantly lower”\n\n[1] Tang et al. (2024) – Accelerating Parallel Sampling of Diffusion Models\n\n> The evaluation is conducted using CIFAR10 and LSUN datasets. More thorough evaluation is needed using ImageNet-1k classes.\n\nWe have now evaluated our method on ImageNet (64x64x3) and show similar improvements in terms of NFE. With a baseline at 250 steps (corresponding to a FID/IS of 4.18/49.54), our method achieves a NFE of  95.38 corresponding to a halving of the NFE. The FID/IS score of the speculative sampling approach is 4.35/48.28 (which is of the same order as 4.18/49.54). We acknowledge that our baseline FID/IS is not state-of-the-art, but this was the only model we had the time to retrain by the rebuttal deadline. We are currently training another model in order to improve the base FID/IS score. \n\nThe parameters of the base sampler are given by $\\varepsilon = 0.25$ and the guidance value is set to $0.25$. In our speculative  sampling experiment we consider a temperature of $\\tau=1.0$ and a window size of $10$. \n\n> Need to compare with other approaches that allow efficient sampling of diffusion models. o “Fast Sampling of Diffusion Models via Operator Learning” o “Parallel Sampling of Diffusion Models” o “Accelerating Parallel Sampling of Diffusion Models”\n\nWe do not compare with [1] as this approach is very different from ours and does not yield state-of-the-art results. However, we have now compared with [2] and refer to the answer to Reviewer zMQr for more details. In short, our method outperforms [2] and, combining our speculative approach with [2], leads to improved results which also outperforms strong baselines such as [4,5]. However, we emphasize that our approach is not directly comparable to [2,3], since 1) these methods do not sample exactly from the original denoising diffusion models and 2) only converge in the infinite number of steps limit since they rely on the fixed point property of the SDE integrators.\n\n[1] Zheng et al. (2022) – Fast Sampling of Diffusion Models via Operator Learning\n\n[2] Shih et al. (2023) – Parallel Sampling of Diffusion Models\n\n[3] Tang et al. (2024) – Accelerating Parallel Sampling of Diffusion Models\n\n[4] Tong et al. (2024) – Learning to Discretize Denoising Diffusion ODEs\n\n[5] Sabour et al. (2024) – Align Your Steps: Optimizing Sampling Schedules in Diffusion Models\n\n\n> Supplementary material Section C – Algorithm 7. The return statement on Line 980 is probably incorrect.\n\nThanks, this is indeed a typo.\n\n> Versatility of the method\n\nTo showcase the applicability of our method beyond generative modeling, we demonstrate its  efficiency in the context of Monte Carlo sampling. We consider the $\\phi_4$ model [1,2] which defines $\\pi(x) \\propto \\exp[-U_\\beta(x)]$ for \n\n$$U_\\beta(x) = (\\beta/2) \\sum_{|i-j| = 1} (x_i - x_j)^2 + \\sum_{i} (x_i^2 - 1)^2,$$\n\non a grid of shape $(8,8)$ and $\\beta=100$. Sampling from $\\pi$ is complex as this requires sampling so-called ordered states. In this context, the teacher model is the Langevin diffusion sampling $\\pi(x)$ with $100,000$ iterations and stepsize $10^{-3}$ while our speculative sampling algorithm uses the frozen prediction draft model and a window size of $20$. The results are averaged over $500$ runs. The mean energy is the average of $U(x_i)$ computed on the $500$ samples $x_i$, while the standard deviation energy is the standard deviation of $U(x_i)$. \n\n | Metrics | Mean energy | Standard deviation energy | NFE | \n| --- | --- | --- |--- |  \n| Langevin sampling | 62.27 | 13.32 | 100000 | \n| Speculative sampling| 65.90 | 12.48 | 48564 | \n\n [1] Guth et al. (2022) – Wavelet Score-Based Generative Modeling\n\n[2] Milchev et al. (1986) – Finite-size scaling analysis of the $\\phi_4$ field theory on the square lattice", "claims_and_evidence": "The general claim of  parallel of parallel sampling and selection helps in the case parallel evaluation but with increased compute and memory.\n\nThe lower bound presented in Section 4.2, intuitively makes sense in terms of selected parameters.", "methods_and_evaluation_criteria": "-\tThe evaluation is conducted using CIFAR10 and LSUN datasets. More through evaluation is needed using ImageNet-1k classes.\n-\tThe approach assumes parallel evaluation allowing lower latency, but the method increases compute and memory requirements, which are also critical components that are not handled by the approach. \n-\tNeed to compare with other approaches that allow efficient sampling of diffusion models.\no\t“Fast Sampling of Diffusion Models via Operator Learning”\no\t“Parallel Sampling of Diffusion Models”\no\t“Accelerating Parallel Sampling of Diffusion Models”", "theoretical_claims": "See above sections.", "experimental_designs_or_analyses": "Check methods and evaluation criteria section.", "relation_to_broader_scientific_literature": "Good initial step for speculative sampling for diffusion models.", "essential_references_not_discussed": "check above sections.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "The manuscript well written. Captions for the tables can be improved. \n\nSupplementary material Section C – Algorithm 7. The return statement on Line 980 is probably incorrect.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None."}}, {"review_id": "hk8aQNj3ov", "reviewer": "Reviewer_zMQr", "summary": "The paper provides an efficient way to apply speculative decoding from literature of language models to diffusion models, which is challenging because diffusion models use the gaussian distribution instead of discrete distribution. They address this challenge via adjusted rejection sampling with reflection coupling. Experimental results show that speculative sampling actually accelerates sampling from diffusion models even without separate draft models.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their very positive assessment of our manuscript. \n\n> Overall, their claims are well-supported by theory and experiments. Thus I think the contributions of the paper are solid and beneficial to the community of both speculative decoding and diffusion models.\n\nWe appreciate that the reviewer recognizes the value of our work and its benefits for both the LLM and diffusion models communities. \n\n> How much does the proposed method accelerate inference of diffusion models when combined with other acceleration methods?\n\nBelow, we combine our speculative sampling method with parallel sampling [1]. \n\n| Configuration | FID |  NFE | \n| --- | --- | --- |  \n| $p=0$, $\\varepsilon=0.25$, $\\tau=1.0$ | 2.23 | 15.69 | \n| $p=1$, $\\varepsilon=0.25$, $\\tau=1.0$ | 2.09 | 23.80 | \n| $p=5$, $\\varepsilon=0.25$, $\\tau=1.0$ | 2.09 | 57.85 | \n| $p=0$, $\\varepsilon=0.5$, $\\tau=1.0$ | 2.77 | 17.06 | \n| $p=1$, $\\varepsilon=0.5$, $\\tau=1.0$ | 2.75 | 23.42 | \n| $p=5$, $\\varepsilon=0.5$, $\\tau=1.0$ | 2.75 | 57.80 | \n| $p=0$, $\\varepsilon=0.25$, $\\tau=2.0$ | 2.24 | 14.89 | \n| $p=1$, $\\varepsilon=0.25$, $\\tau=2.0$ | 2.09 | 21.12 | \n| $p=5$, $\\varepsilon=0.25$, $\\tau=2.0$ | 2.08  | 51.45 | \n| $p=0$, $\\varepsilon=0.5$, $\\tau=2.0$ | 2.74 | 16.47 | \n| $p=1$, $\\varepsilon=0.5$, $\\tau=2.0$ | 2.77 | 20.62 | \n| $p=5$, $\\varepsilon=0.5$, $\\tau=2.0$ | 2.77 | 50.40 | \n| $p=0$, $\\varepsilon=0.25$, $\\tau=10.0$ | 2.39 | 12.86 | \n| $p=1$, $\\varepsilon=0.25$, $\\tau=10.0$ | **2.07** | 15.42 | \n| $p=5$, $\\varepsilon=0.25$, $\\tau=10.0$ | 2.07 | 37.5 | \n| $p=0$, $\\varepsilon=0.5$, $\\tau=10.0$ | 2.73 | 14.49 | \n| $p=1$, $\\varepsilon=0.5$, $\\tau=10.0$ | 2.79 | 16.38 | \n| $p=5$, $\\varepsilon=0.5$, $\\tau=10.0$ | 2.79 | 40.25 | \n\n\nWe report FID score and NFE for CIFAR-10 with a number of steps of $30$. We vary the temperature parameter $\\tau$, the churn parameter $\\varepsilon$ as well as the number of parallel iterations, see [1,2]. For each combination of hyperparameters we also consider window sizes $5$, $10$ and $20$ and report the best run (in terms of FID). \n\nThe original speculative sampling procedure corresponds to $p=0$. The best FID number that can be achieved with this configuration is $2.23$ with a NFE of $15.69$. However, by combining our speculative sampling procedure with parallel sampling then we can reach a FID of $2.07$ with a NFE of $15.42$. \nThis shows the benefits of combining our speculative sampling procedure with other acceleration methods. We will report those results in the updated version of our manuscript.  \n\n[1] Shih et al. (2023) – Parallel Sampling of Diffusion Models\n\n[2] Tang et al. (2024) – Accelerating Parallel Sampling of Diffusion Models\n\n\n> Captions for the tables can be improved.\n\nWe are willing to improve the captions of our table if the reviewer has more feedback for us. \n\n> Versatility of the method\n\nWe have now included additional experiments regarding comparison with DPM++ solvers, see answer to Reviewer eBDt, as well as an experiment showcasing the efficiency of the method in a sampling context (i.e. a non generative modeling setting), see answer to Reviewer E771.", "claims_and_evidence": "- Claim 1: To extend speculative decoding to diffusion models, they propose an efficient rejection sampling using reflection maximal coupling.\n  - Evidence: Section 3.2-3.3 provide concise derivations.\n  - Evidence: Efficiency is measured by the number of function calling for the target model in Section 6.\n- Claim 2: They propose an efficient draft model constructed from the target model itself, by reusing the previous score from target models.\n  - Evidence: Figure 3 experimentally shows it is indeed more efficient than the independent draft models.\n  - Evidence: The actual speed-ups are also observed on realistic datasets like CIFAR10 and LSUN.\n- Claim 3: They provide a complexity analysis on the number of function evaluation, and also analyses for acceptance ratio for speculative sampling.\n  - Evidence: Proposition 4.1, Theorem 4.3.\n\nOverall, their claims are well-supported by theory and experiments. Thus I think the contributions of the paper are solid and beneficial to the community of both speculative decoding and diffusion models.", "methods_and_evaluation_criteria": "The proposed method makes sense. Evaluation protocols also follow the standard ones.", "theoretical_claims": "I checked all statements of the paper. I read some proofs given in Appendix, especially in relation to Proposition 4.1, Theorem 4.3.", "experimental_designs_or_analyses": "Experimental designs make sense.", "relation_to_broader_scientific_literature": "Speculative sampling has been widely used with language models, and it effectively accelerates the inference of large language models. The proposed method and drafting strategy provides such a powerful tool for diffusion models with a straightforward and efficient way, which opens up a new research direction for inference acceleration or diffusion models.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "See above discussions.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- How much does the proposed method accelerate inference of diffusion models when combined with other acceleration methods?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "frkWtAsakj", "reviewer": "Reviewer_eBDt", "summary": "This paper extends the method of speculative sampling, which has been used in the context of speeding up inference for autoregressive models, to diffusion models. Roughly, this is a method by which one uses a weaker \"draft\" model to propose sampling steps which are then accepted with some probability by a strong \"target\" model via rejection sampling. The rejection step can be interpreted as an optimal coupling between the two models; the naive way to implement this coupling in continuous domains fails to achieve meaningful savings, so the authors utilize a smarter optimal coupling that exploits the fact that the sampling steps of the two models are both Gaussian in distribution. In addition, they find that given a target model, instead of training a weaker draft model, it is preferable to simply take the draft model to be a coarser discretization of the target. With this, they find that speculative sampling can improve sampling efficiency over vanilla stochastic diffusion samplers (e.g. 2.45 in 100 NFEs -> 2.34 in 35 NFEs).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their insightful comments. \n\n> how to think about $g_t$ [...] for classical schedules. \n\nLet $A(t) = g_t^2 ((1/\\sigma_t - \\sigma_t)^2 + \\alpha_t^2)$ and consider a few schedules:\n\n* Rectified flow [1]: $\\alpha_t = 1-t$, $\\sigma_t = t$. We have that $A(t) = 2 t (1-t) (1 + (1 + 1/t)^2)$.\n* Cosine [2]: $\\alpha_t = \\cos(\\pi t /2)$, $\\sigma_t = \\sin(\\pi t /2)$. We have that $A(t) = \\frac{\\pi}{2}\\sin(\\pi t) (1 + \\mathrm{cotan}(\\tfrac{\\pi}{2} t))$.\n\nNote that $A(t) \\to 0$ as $t \\to 1$ and $A(t) \\to +\\infty$ as $t \\to 0$. Hence the acceptance is close to 1 around $t \\approx 1$ and worsens when $t \\to 0$. This is consistent with our empirical results. We will include a plot of $A(t)$ as a function of $t$ for those schedules.\n\n[1] Liu et al. (2022) – Flow Straight and Fast\n\n[2] Nichol and Dhariwal (2021) – Improved Denoising Diffusion Probabilistic Models\n\n> difficult to parse how useful Theorem 4.3 is.\n\nWe believe that Theorem 4.3 is useful because, although we do not expect our bound to be tight, it captures rigorously the impact of the various hyperparameters of the algorithm on the expected acceptance rate. In particular:\n* that decreasing the stepsize increases the acceptance rate at the cost of increasing the number of total steps.\n* The influence of the schedule (see above).\n* The existence of an optimal value for $\\varepsilon$ is also observed in practice, see our experimental section.\n\n>  needs more support is the sentence \"Our approach complements [other approaches for acceleration] and can be combined with...better integrators.\" [...] I would be more convinced about the proposed approach if, combined with one of these existing approaches, it gets a tangible improvement.\n\nWe have compared our approach with LD3 [1] and AYS[2]. In addition, to further substantiate our claim we have combined our acceleration method with parallel sampling [3] and observed benefits of the method, see the answer to Reviewer zMQr for more details. \nWe compare the results on CIFAR-10 as reported in LD3 [1]. Our best speculative sampling method outperformed both LD3 and AYS. \nWe also included our best results obtained with a uniform timesteps spacing and EDM timestep spacing [4]. These results are based on the same model as “Best speculative”. We sweep over $\\rho = [1.0, \\dots, 8.0]$ in the case of EDM timestep spacing. This improves the quality of the samples but they remain inferior in quality to the ones obtained with our best speculative model. We re-implemented LD3 [1] in our setting and used it to learn a timestep spacing. Our setting is similar to the one of [1]. Finally, we compare our approach with a distilled generator trained on top of our best model. We focus on Multistep Moment Matching Distillation (MMD) [5]. We sweep over several hyperparameters for MMD and report the best result. \n\n| Configuration | FID |  NFE | \n| - | - | - | \n| DPM Solver++ (naive – reported) | 2.37 | 20 | \n| DPM Solver++ (AYS [2] – reported) | 2.10 | 20 | \n| DPM Solver++ (LD3 [1] – reported) | 2.36 | 20 |\n| Uniform timesteps | 7.14 | 15 | \n| EDM timesteps | 4.22 | 15 | \n| LD3 timesteps | 3.49 | 15 |\n| MultiStep Moment Matching |  2.76 | 15 | \n| Best speculative | **2.07**  | 15.42 | \n\nWe will include those results in the revised version of our paper. We will also comment on LD3 [1] and AYS [2] in the related work section as these works are indeed complementary to ours. \n\nFinally we note that our method is not restricted to diffusion models. It can be applied to accelerate simulation to sample from unnormalized distributions. We have added an experiment on the $\\phi_4$ potential demonstrating the efficiency of the method, see the answer to Reviewer E771.\n\n[1] Tong et al. (2024) – Learning to Discretize Denoising Diffusion ODEs\n\n[2] Sabour et al. (2024) – Align Your Steps: Optimizing Sampling Schedules in Diffusion Models\n\n[3] Shih et al. (2023) – Parallel Sampling of Diffusion Models\n\n[4] Karras et al. (2022) – Elucidating the Design Space of Diffusion-Based Generative Models\n\n[5] Salimans et al. (2024) – Multistep Distillation of Diffusion Models via Moment Matching\n\n>  [is the] method actually orthogonal to other accelerations. This is tricky as many few-NFE methods are based on ODEs. [...] setup you could try where you could achieve comparable FID with existing acceleration baselines using [...]?\n\nIt is indeed correct that our approach does not apply to deterministic samplers, but we adapt common acceleration methods to the stochastic case. For example in the case of LD3 [1] we train LD3 in our setting by considering the noise added during the sampling to be frozen. Similarly, in [2] (see end of Section 3.1), the authors freeze the noise. Following those principles we are able to combine several acceleration techniques with our approach. \n\n[1] Sabour et al. (2024) – Align Your Steps: Optimizing Sampling Schedules in Diffusion Models\n\n[2] Shih et al. (2023) – Parallel Sampling of Diffusion Models", "claims_and_evidence": "The theoretical claims lower bounding the acceptance ratio under their rejection method are sound. While I appreciated the discussion under Theorem 4.3, it would be helpful to discuss further how to think about $g^2_t((1/\\sigma_t - \\sigma_t)^2 + \\alpha^2_t)$ as a function of $t$ when $t$ is bounded away from $1$, for classical schedules. In general, it is a bit difficult to parse how useful Theorem 4.3 is.\n\nThe main claim that needs more support is the sentence \"Our approach complements [other approaches for acceleration] and can be combined with...better integrators.\" This isn't implausible but needs experimental support. The improvement from 100 NFEs to 30 NFEs is not particularly striking in the context of the many works on acceleration, especially the ones that use minimal distillation (e.g. LD3 achieves FID of 2.27 on CIFAR using only 10 NFEs and also doesn't require heavy-duty distillation). I would be more convinced about the proposed approach if, combined with one of these existing approaches, it gets a tangible improvement.", "methods_and_evaluation_criteria": "It would be better if the authors conducted a more thorough empirical investigation. For instance, the image experiments are limited to improving over vanilla Karras et al.-style diffusion on CIFAR-10 and LSUN. The empirical results would be more compelling if the authors evaluated their method against other acceleration methods of comparable computational cost.", "theoretical_claims": "The most nontrivial theoretical result in the paper is the lower bound on the acceptance ratio in Theorem 4.3. I skimmed the proof of this in the supplement and the argument involves some standard manipulations with Fisher divergence and Tweedie's formula.", "experimental_designs_or_analyses": "I checked the soundness and validity of the image experiments as this is the domain with which I am most familiar. I did not find any issues but found them to be insufficiently comprehensive, see \"Methods And Evaluation Criteria\" above.", "relation_to_broader_scientific_literature": "There is a vast literature on diffusion generative modeling, with many recent works on acceleration of inference. This paper sits squarely within that broader literature, which is adequately overviewed in the Related Work section modulo a couple works (see Essential References Not Discusses below)", "essential_references_not_discussed": "As mentioned in the \"Claims and Evidence\" section above, the authors would have benefited from checking whether their method improves upon existing methods that get comparable or even better speedups, e.g. AYS (https://arxiv.org/pdf/2404.14507), LD3 (https://arxiv.org/abs/2405.15506), etc.", "other_strengths_and_weaknesses": "Strengths:\n- It is natural to ask for a diffusion analogue to the popular speculative sampling approach for LLMs, and prior to this work, it was not known how to obtain a suitable analogue. The reflection coupling trick used in this paper, while simple, is clever and gives a slick way to implement rejection sampling in this continuous context\n- The theoretical claims give nontrivial lower bounds on the acceptance probability\n- The experimental results provide preliminary evidence that their method is effective\n- The idea to use a coarse-graining of the target model as the draft model is interesting and arguably unique to the diffusions setting\n\nWeaknesses:\n- To reiterate, my main complaint is that the actual acceleration achieved by this method is not that impressive compared to existing acceleration methods. I would be more convinced if this method were actually complementary to those other methods as claimed, and I would be happy to raise my score if that is actually the case.\n- As the authors note, the method crucially relies on stochasticity in the sampling steps, so it does not apply to ODEs. This appears to be a crucial weakness as ODE-based samplers are generally much more NFE-efficient", "other_comments_or_suggestions": "See \"Questions for Authors\" below", "questions_for_authors": "As discussed above, one thing that would make me much more positive about this paper is whether the acceleration afforded by this method is actually orthogonal to other accelerations. This is tricky as many few-NFE methods are based on ODEs. Is there any setup you could try where you could achieve comparable FID with existing acceleration baselines using, say, 10 NFEs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "551WIVauNZ", "reviewer": "Reviewer_VXs6", "summary": "This paper proposed a fast sampling method for diffusion models, inspired by the idea of speculative decoding from LLMs. Using a more compact draft model to efficiently generate an image sequence and then verify the whole sequence in parallel with the original diffusion model, the sampling latency can be shortened. Besides leveraging an independent draft model, the authors reuse $b_t$ approximated at the window start, making the original target model itself a draft model. Theoretical analysis and empirical evaluation are provided to prove the effectiveness of the proposed sampling method.\n\n\n### Update after rebuttal\nI appreciate the feedback from the authors. Overall, I think it is a good paper. I would keep my rating and recommend it for acceptance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their positive assessment of our work. \n\n> This paper shares a similar idea to speculative decoding for LLMs [1], but to my knowledge, it is the first to apply this idea to diffusion model sampling. T-stitch [2] leverages the idea of using a smaller draft model for fast sampling, but from a totally different perspective. It didn't share the same theoretical foundation as speculative decoding.\n\nWe thank the reviewer for pointing us to [1]. While [1] also leverages two models, their approach differs from ours. Specifically, they employ a cheap model for early denoising stages and an expensive model for later stages. This strategy does not guarantee the same quality as the original superior model. In contrast, our method samples exactly from the superior model, utilizing the cheap model only for parallel verification, thus maintaining the desired quality. We will however include a discussion regarding this very related work in our updated version of the manuscript. \n\n[1] Pan et al. (2024) – T-Stitch: Accelerating Sampling in Pre-Trained Diffusion Models with Trajectory Stitching\n\n> Some experimental settings are not clearly described.\n\nBelow we answer the concerns of the reviewer. \n\n> What kind of sampler is used for 30-step sampling in Table 1? And what is the original total number of sampling steps of the target model?\n\nIn Table 1 (and all of our experiments), we used the stochastic sampler of flow matching models, see [1] for instance. An explicit form of the sampler is given in Equation (37), line 1843. In the revised version of the paper, we will highlight Equation (37) in the main paper. We emphasize that our method is compatible with other stochastic methods such as DDPM [2].\n\n[1] Albergo et al. (2023) – Stochastic Interpolants: A Unifying Framework for Flows and Diffusions\n\n[2] Ho et al. (2020) – Denoising Diffusion Probabilistic Models\n\n> The idea of applying speculative decoding to diffusion model sampling is interesting. However, since there are already many fast samplers like DPM-Solver [1] for diffusion models, what are the main advantages of speculative sampling over the other samplers? In this paper, there is no experiment comparing them.\n\nWe thank the reviewer for this insightful remark. We emphasize that our method is largely orthogonal to other acceleration techniques. In particular we now combine our approach with [1,2], see our detailed answer to Reviewer zMQr, which yields comparable NFE improvements (including against DPM-Solver++ [3]). Furthermore, our method's applicability extends beyond accelerating denoising diffusion models; it can also be used to accelerate the simulation of any diffusion equation with a computationally expensive drift, such as Langevin diffusion to sample from unnormalized target distributions, see our detailed answer to Reviewer E771. We have added experiments as well as an Appendix in the revised version demonstrating the efficiency of the methodology in this context. \n\n[1] Tong et al. (2024) – Learning to Discretize Denoising Diffusion ODEs\n\n[2] Shih et al. (2023) – Parallel Sampling of Diffusion Models\n\n[3] Lu et al. (2022) – DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models\n\n> In Table 1, is the draft model independent or frozen? If independent, how is NFE computed? Is it only dependent on the calls to the target model?\n\nTo clarify, we employed the frozen strategy for all Image Space and Robotics experiments reported in Table 1. The independent strategy was used exclusively in the low-dimensional setting to demonstrate the superior performance of the frozen draft approach. Consequently, in that specific case, only the target model was evaluated, and the NFE reported corresponds solely to that model. We will explicitly address this distinction in the revised manuscript.\n\n> Versatility of the method\n\nWe have now included additional experiments regarding comparison with DPM++ solvers, see answer to Reviewer eBDt, as well as an experiment showcasing the efficiency of the method in a sampling context (i.e. a non generative modeling setting), see answer to Reviewer E771.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper shares a similar idea to speculative decoding for LLMs [1], but to my knowledge, it is the first to apply this idea to diffusion model sampling. \n\nT-stitch [2] leverages the idea of using a smaller draft model for fast sampling, but from a totally different perspective. It didn't share the same theoretical foundation as speculative decoding. \n\n[1] Leviathan, Yaniv, Matan Kalman, and Yossi Matias. \"Fast inference from transformers via speculative decoding.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Pan, Zizheng, et al. \"T-stitch: Accelerating sampling in pre-trained diffusion models with trajectory stitching.\" arXiv preprint arXiv:2402.14167 (2024).", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "### Strengths: \n- The writing is clear. The theoretical analysis is solid.\n- The empirical evaluation is supportive.\n\n### Weaknesses:\n- Some experimental settings are not clearly described.", "other_comments_or_suggestions": "Please see questions for authors.", "questions_for_authors": "1. What kind of sampler is used for 30-step sampling in Table 1? And what is the original total number of sampling steps of the target model?\n\n2. The idea of applying speculative decoding to diffusion model sampling is interesting. However, since there are already many fast samplers like DPM-Solver [1] for diffusion models, what are the main advantages of speculative sampling over the other samplers? In this paper, there is no experiment comparing them.\n\n3. In Table 1, is the draft model independent or frozen? If independent, how is NFE computed? Is it only dependent on the calls to the target model? \n\n### Reference: \n[1] Lu, C., Zhou, Y., Bao, F., Chen, J., Li, C., & Zhu, J. (2022). Dpm-solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps. Advances in Neural Information Processing Systems, 35, 5775-5787.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes extending speculative sampling to diffusion models through a reflection-based coupling scheme. The reviewers agreed that adapting speculative sampling to continuous sampling in diffusion models is a valuable contribution, both conceptually and practically. In particular, they praised the clever application of reflection maximal coupling as well as the thorough theoretical analysis bounding the acceptance ratio. 

Some reviewer also suggested to refinie the technique and comparing it against additional fast-diffusion samplers. Some also highlighted trade-offs in memory usage and recommended exploring synergy with other acceleration methods (such as parallel sampling). Overall this is a nice contribution and the authors are encouraged to incorporate the reviewers suggestions for the final version, should the paper make the cut.
Decision: Accept (poster)