Parallel Sampling of Diffusion Models
Authors: Andy Shih
Suneel Belkhale
Stefano Ermon
Dorsa Sadigh
Nima Anari
Venue: NeurIPS 2023 spotlight (2023)
Keywords: diffusion models
parallel sampling
TL;DR: We improve sampling speed of diffusion models by 2-4x using parallel computation

Abstract: Diffusion models are powerful generative models but suffer from slow sampling, often taking 1000 sequential denoising steps for one sample. As a result, considerable efforts have been directed toward reducing the number of denoising steps, but these methods hurt sample quality. Instead of reducing the number of denoising steps (trading quality for speed), in this paper we explore an orthogonal approach: can we run the denoising steps in parallel (trading compute for speed)? In spite of the sequential nature of the denoising steps, we show that surprisingly it is possible to parallelize sampling via Picard iterations, by guessing the solution of future denoising steps and iteratively refining until convergence. With this insight, we present ParaDiGMS, a novel method to accelerate the sampling of pretrained diffusion models by denoising multiple steps in parallel. ParaDiGMS is the first diffusion sampling method that enables trading compute for speed and is even compatible with existing fast sampling techniques such as DDIM and DPMSolver. Using ParaDiGMS, we improve sampling speed by 2-4x across a range of robotics and image generation models, giving state-of-the-art sampling speeds of 0.2s on 100-step DiffusionPolicy and 14.6s on 1000-step StableDiffusion-v2 with no measurable degradation of task reward, FID score, or CLIP score.

Parallel Sampling of Diffusion Models
Andy Shih, Suneel Belkhale, Stefano Ermon, Dorsa Sadigh, Nima Anari Computer Science, Stanford University
fandyshih, belkhale, ermon, dorsa, anari |cc.. stanford.
Abstract
Diffusion models are powerful generative models but suffer from slow sampling, often taking 1000 sequential denoising steps for one sample. As result, consider- able efforts have been directed toward reducing the number of denoising steps, but these methods hurt sample quality. Instead of reducing the number of denoising steps (trading quality for speed), in this paper we explore an orthogonal approach: can we run the denoising steps in parallel (trading compute for speed)? In spite of the sequential nature of the denoising steps, we show that surprisingly it is possible to parallelize sampling via Picard iterations, by guessing the solution of future denoising steps and iteratively refining until convergence. With this insight, we present ParaDiGMS, a novel method to accelerate the sampling pretrained difffusinn models by denoising multiple steps in parallel. ParaDiGMS is the first diffusion sampling method that enables trading compute for speed and is even compatible with existing fast sampling techniques such DDIM and DPM- Solver. Using ParaDiGMS, we improve sampling speed by 2-4x across a range robotics and image generation models, giving of of-te-of-the-arr the-art sampling speeds of 0.2s on 100-step DiffusionPolicy and 14.6s on 1000-step StableDiffusion-22 with measurable degradation of task reward, FID score, CL.P score.
Introduction
Diffusion models [28, 9, 32] have demonstrated powerful modeling capabilities for image genera- tion [34, 15, 24], molecular generation [38], robotic policies [12, 4]. and other applications. The main limitation of diffusion models, however, that sampling can be inconveniently slow. For example, the widely-used Denoising Diffusion Probabilistic Models (DDPMs) [9] can take 1000 denoising steps to generate one sample. In light of this, many works like DDIM [29] and DPMSolver [18] have proposed to improve sampling speed by reducing the number of denoising steps. Unfortunately. reducing the number of steps can come at the cost of sample quality.
We are interested accelerating sampling of pretrained diffusion models without sacrificing sample quality. We ask the following question: rather than trading quality for speed, can we instead trade compute for speed? That is, could we leverage additional (parallel) compute to perform the same number of denoising steps faster? At first, this proposal seems unlikely work, since denoising proceeds sequentially. Indeed, naïve parallelization can let us generate multiple samples at once (improve throughput), but generating a single sample with faster wall-clock time (improving latency) appears much more difficult.
We show that, surprisingly, it is possible improve the sample latency of diffusion models by computing denoising steps in parallel. Our method builds on the idea of Picard iterations to guess the full denoising trajectory and iteratively refine until convergence. Empirically, of iterations for convergence is much smaller than the number of steps. Therefore, by computing each iteration quickly via parallelization, we sample from the diffusion model much faster.
find that the number
Code for our paper can found at
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our method ParaDiGMS (Parallel Diffusion Generative Model Sampling) is the first general method that allows for the tradeoff between compute and sampling speed of pretrained diffusion models. Remarkably, ParaDiGMS is compatible with classifier- free guidance [10] and with prior fast sampling methods [29, 18] that reduce the number of denoising steps. In other words, we present an orthogonal solution that can form combinations with prior methods (which we call ParaDDPM, ParaDDIM, ParaDPMSSolvr)) to trade both compute and quality for speed.
We experiment with ParaDiGMS across large range of robotics and image generation models, including Robosuite Square, PushT, Robosuite Kitchen, StableDiffusion-22 and LSUN. Our method is strikingly consistent, providing an improvement across all tasks and all samplers (ParaDDPM, ParaDDIM. ParaDPMSolver) of around 2-4x speedup with no measurable decrease in quality on task reward, FID score, or CLIP score. For example, we improve the sample time of the 100-step action generation of DiffusionPolicy from 0.74s to 0.2s, and the 1000-step image generation of StableDifffssinn-22 on A 100 GPUs from 50.0s to 14.6s. Our improvements also extend to few-step image generation, showing speedups for as low as 50-step DDIM. By enabling these faster sampling speeds without quality degradation, ParaDiGMS can enhance exciting applications of diffusion models such as real-time execution of diffusion policies or interactive generation images.
Background
Diffusion models [28, 9] such as Denoising Diffusion Probabilistic Models (DDPM) were introduced as latent-variable models with a discrete-time forward diffusion process where g( is the data distribution, a is scalar function, with latent variables {æt : S T) defined as
g(
æo) = Maa /a(t)=o, (1 -)))))).
By setting (T") close to 0, ( converges to (0, I), allowing us to sample data zo by using a standard Gaussian prior and learned inference model p0 æz). The inference model pe is parameterized as a Gaussian with predicted mean and time- denendependent variance of, and can be used to sample data by sequential denoising. i.e., po(xx) I po xt),
po ( ax.) = N (1 14 (x:),
Many works [32, 18] alternatively formulate diffusion models Stochastic Differential Equation (SDE) by writing the forward diffusion process in the form
da, = (l) + g(()dure: 3g ~ ((xo),
with the standard Wiener process w;, where f and g are position-independent functions that can be appropriately chosen to match the transition distribution q(a; | æo) [18, 15]. These works use an important result from [2] that the reverse process of Eq. (2) takes on the form
dæ. (f(1)a, ()))) - log qe (a:) de g(t) dw or ((TT);
drift
where W; is the standard Wiener process in reverse time. This perspective allows us to treat the sampling process of DDPM as solving discretization of the SDE where the DDPM inference model Po can be used to compute an approximation po (I;-1 xx)- x; of the drift term in Eq. (3).
Since the focus of this paper is on sampling from a pretrained diffusion model, we can assume pe is given. For our purposes, we only need two observations about sampling from the reverse process in Eq. (3): we have access to an oracle that computes the drift at any given point, and the SDE has position-independent noise. We will use the latter observation in Section 3.
2.1 Reducing the number of denoising steps
DDPM typically uses a T = 1000 step discretization of the SDE. These denoising steps are computed sequentially and require a full pass through the neural network pa each step, so sampling can be extremely slow. As a result, popular works such as DDIM [29] and DPMSolver [18] have explored the possibility of reducing the number of denoising steps, which amounts to using a coarser discretization with the goal of trading sample quality for speed.

---

Empirically, directly reducing the number of steps of the stochastic sampling process of DDPM hurts sample quality significantly. Therefore many works [29, 32, 18] propose using an Ordinary Differential Equation (ODE) to make the sampling process more amenable to low-step methods. These works appeal to the probability flow ODE [20], a deterministic process with the property that the marginal distribution p(a;,) at each time matches that of the SDE, so in theory sampling from the probability flow ODE is equivalent to sampling from the SDE:
1 20 (t) log ())) dt, 2T I).
dæ.
f(()
drift 8
By sampling from the ODE instead of the SDE, works such as DDIM and DPMSolver (which have connections to numerical methods such Euler and Heun) can reduce the quality degradation of few-step sampling (e.g., 50 steps).
As summary, the current landscape of sampling from pretrained diffusion models comprised of full-step DDPM or accelerated sampling techniques such as DDIM and DPMSolver that trade quality for speed by reducing the number of denoising steps.
Notation We write [a, b] to denote the set {a, a + 1....,b) b} and [a, b) to denote the set {a, a + 1....,b b 1} for b > a. We write Fa:b to denote the set {a; : i [a, b)]. Since our focus is sampling, in the rest of the paper we denote time as increasing for the reverse process.
3 Parallel computation of denoising steps
Rather than investigating additional techniques for reducing the number of denoising steps, which can lead to quality degradation, we look towards other approaches for accelerating sampling. In particular, we investigate the idea of trading compute for speed: denoising steps in parallel? We clarify that our goal is not to improve sample throughput that can be done with naïve parallelization, producing multiple samples the same time. Our goal is to improve sample latency minimize the wall-clock time required for generating single sample by solving the denoising steps for single sample in parallel. Lowering sample latency without sacrificing quality can greatly improve the experience of using diffusion models, and enable more interactive and real-time generation applications.
accelerate sampling by taking
Parallelizing the denoising steps, however, seems challenging due to the sequential nature of existing sampling methods. The computation graph has chain structure (Fig. 1), it is difficult to propagate information quickly down the graph. To make headway, we present the method of Picard iteration, technique for solving ODEs through fixed-point iteration. An ODE is defined by drift function s(x t) with position and time arguments, and initial value zg. In the integral form, the value at time t can be written
3 = xo + L' s(Eu, u)du.
In other words, the value at time & must be the initial value plus the integral of the derivative along the path of the solution. This formula suggests a natural way of solving the ODE by starting with a guess of the solution {œf 0 < é < 1) at initial iteration & = O, and iteratively refining by updating the value at every time / until convergence:
x + 1
1/' s(a u)du.
(Picard Iteration)
x
Under mild conditions on such as continuity in time and Lipschitz continuity in position as in the well-known Picard-L.nndelff theorem, the iterates form a convergent sequence, and by the Banach fixed-point theorem, they converge to the unique solution of the ODE with initial value ap [ef. 5]. To perform Picard iterations numerically, we can write the discretized form of Eq. (4) with step size 1/T, fort E [0, T]:
1++
x
k +
Σ
s( s( i/T).
(5)
T
0=
3

---

2
22
T
x1
Ø2
TT
k+1
x++1
k++
k+1
a
322
Figure I: Computation graph of sequential sam- Figure 2: Computation graph of Picard iterations, pling by evaluating po (xr+1 (e)), from the per- which introduces skip dependencies. spective of reverse time.
Examining the iterative update rule in Eg. (5), we see that update at time f depends on all previous timesteps instead just the previous timestep 1. This amounts introducing skip dependencies in the computation graph (Fig. 2), which enables information to propagate quickly down the chain and accelerate sampling.
The key property of interest is that each Picard iteration can be parallelized by performing the expensive computations {s(a: ;) E [0, 7)} in parallel and then, with negligible cost, collecting their outputs into prefix sums. Given enough parallel processing power, the sampling time then scales with the number of iterations K until convergence, instead of the number of denoising steps T'.
The number iterations until convergence depends on the drift function s. More concretely, sequential evaluation be written as nested evaluation of functions _ h.(-.. h22 (æo))) on the initial value Ey where (x) = x + s(x, i/T)/T. If, for all timesteps, the drift at the true solution can be accurately obtained using the drift the current guess, then the parallel evaluation will converge in one step.
Proposition 1. (Proof in Appendix A)
s(a i/T) ((hh
vi Vist
x4+1
also easy to see that even in the worst case, exact convergence happens in K S T iterations since the first k points 2o.k must equal the sequential solution Th.. after k iterations. In practice, the number of iterations until (approximate) convergence is typically much smaller than T. leading to large empirical speedup.
The idea of Picard iterations is powerful because it enables the parallelization of denoising steps. Remarkably, Picard iterations are also fully compatible with prior methods for reducing the number of denoising steps. Recall that the drift approximated using Euler discretization as po(#+++ xx.) -r, but it can also be readily approximated using higher-order methods on po. In our experiments, we demonstrate the combination of the two axis of speedups to both reduce the number of denoising steps and compute the steps in parallel.
s(x,, t t/T"// can be written hx(3;)) - 2, and
3.1 Practical considerations
Implementing Picard iteration on diffusion models presents few practical challenges, the most important being that of GPU memory. Performing an iteration requires maintaining the entire array of points To.r over time, which can be prohibitively large to fit into GPU memory. To address this, we devise the technique window of size that can be chosen appropriately to satisfy memory constraints. Moreover, instead of iterating on Et:t+p until convergence of the full window before advancing to the next window, use sliding window approach to aggressively shift the window forward in time soon the starting timesteps in the window converge.
umini-)batching which performs Picard iteration only on points Ft:t+p inside
One other issue is the problem of extending Picard iteration to SDEs, since we rely on the determinism
of ODEs to converge to a fixed point. Fortunately, since the reverse SDE (Eq. (3)) has position- independent noise, we can sample the noise up-front and absorb these fixed noises into the drift of the (now deterministic) differential equation. Note that the resulting ODE is still Lipschitz continuous in position and continuous in time, guaranteeing the convergence of Picard iteration.

---

batch window
batch window
batch window
(a) Compute the drift of -it-p on a batch window of size p in parallel
(b) Update the values to ++1 ing the cumulative drift of points in the window
::t-p us-
(c) Determine how far to slide the window forward, based on the er- ror || - xx, 112
accelcrating an ODE solver by computing the drift at multiple timesteps in parallel. During iteration k, we process in parallel a batch window of size p spanning timesteps [t, + p). The new values at point 4t4j s++1 are updated based on the value æ at the left end
Figure 3: ParaDiGMS algorithm:
of the window plus the cumulative drift E D s(x; i/T) of points in the window. We then slide the window forward until the emror is greater than our tolerance, and repeat for the next iteration.
Finally, need choose stopping criterion for the fixed-point iteration, picking low tolerance avoid degradations of sample quality. A low enough tolerance ensures that the outcome of parallel sampling will be close the outcome of the sequential sampling process in total variation distance.
Proposition 2. (Proof in Appendix B) Assuming the iteration rule in Eq. (5) has linear convergence x rate with a factor 2 2, using the tolerance "| - =x 1|2 S 4e of 2T ensures that samples of aff are drawn from distribution with total variation distance at most from the DDPM model distribution of Eq. (1).
The above based on a worst-case analysis, and in our experiments, we find that using much more relaxed tolerance such as² 3 ||= 2
Poo7, with r 0.1 and D being the dimensionality of data, gives reliable speedups without any measurable degradation in sample quality.
In Algorithm we present the complete procedure of ParaDiGMS, incorporating sliding window over batch, up-front sampling of noise, and tolerance of Picard iterations (Fig. 3). The loop starting on Line 4 performs a sliding window over the batch of timesteps [t, f. + p) in each iteration. Line computes the drifts, which is the most compute-intensipg part of the algorithm, but can be efficiently parallelized. Line obtains their prefix sums in parallel to run the discretized Picard iteration update, and Lines 7-8 check the eтror values to determine how far forward we can shift the sliding window.
Algorithm 1: ParaDiGMS: parallel sampling via Picard iteration over sliding window
Input: Diffusson model pe with variances of, tolerance т, batch window size p, dimension D Output: A sample from Pa
t + 0,0
2 zi of
Vi Vi (0.7)
Up-front sampling of noise (for SDE) Sample initial condition from prior
3 ay I),
a + x Vie (t.p]
4 /
5
Deti + po pa( (ttt (+ a Vj (0,p)
If Compute drifts in parallel Discretized Picard iteration I/ Store error value for each timestep Slide forward until we reach tolerance // Initialize new points that the window now covers
x ++++1 zx E yi + Σ z, E (0.p)
k+1
emror + + [|]
k+1 - Vij [L,p)}
stride + min (1j :error, > >r3
8
k+l
k+1 Vj E [1, stride]
Fitpts - ættp
t + + stride,
k t k+
11
p + min(p,
12 return x
The ParaDiGMS algorithm is directly compatible with existing fast sequential sampling techniques such as DDIM and DPMSolver, by swapping out the Euler discretization in Lines 5-6 for other
Forr ODE methods (DDIM, DPMSolver) we still pick tolerance value relative to the noise variance of the corresponding SDE of DDPM.
5

---

solvers, such as higher-order methods like Heun. As we see in our experiments, the combination of reducing the number of steps and solving the steps in parallel leads to even faster sample generation.
4 Experiments
We experiment with our method ParaDiGMS on suite of robotic control tasks [4] including Square [41], PushT, Franka Kitchen [7], and high-dimensional image generation models including StableDiifusion-v2 [24] and LSUN Church and Bedroom [39]. We observe a consistent improvement of around 2-4x speedup relative to the sequential baselines without measurable degradation in sample quality as measured by task reward, FID score, or CLIP score.
4.1 Diffusion policy
Recently, a number of works have demonstrated the advantages of using diffusion models in robotic control tasks for flexible behavior synthesis or robust imitation learning on multimodal behavior [12, 4, 22, 36]. We follow the setup of DiffusionPolicy [4], which is imitation learning framework that models action sequences. More specifically, DiffusionPolicy first specifies a prediction horizon history
h and replanning horizon r. At each environment step 1, DiffusionPolicy conditions of observations and predicts a sequence of actions (*I.+*)- Then, the policy executes the first r actions (au++) of the prediction. Therefore, for an episode of length I. and scheduler with T steps, executing a full trajectory can take x L/r denoising steps over a dimension of |a] x h, which can be inconveniently slow.
We examine our method on the Robosuite Square, PushT, and Robosuite Kitchen tasks. Each environment
prediction horizon of 16, and replanning horizon 8. The Square task uses state- based observations with a maximum trajectory length of 400 and a position- -baee action space of dimensionality 7. This means the diffusion policy takes 50 samples per episode, with each sample being a series of denoising steps over a joint action sequence of dimension 112. The PushT task also uses state-based observations and has maximum trajectory length of 300 and action space of 2, which results in 38 samples with denoising steps over joint action sequence of dimension 32. Lastly, the Kitchen task uses vision-based observations and has maximum trajectory length of 1200 with an action space of 7, giving 150 samples per episode and denoising steps over a joint action sequence of dimensionality 112. For all three tasks, we use a convolution-based architecture.
The DDPM scheduler in DiffusionPolicy [4] uses 100 step discretization, and the DDIM/DPMSolver schedulers use 15 step discretization. For example, trajectory in the Kitchen task requires 1200/8 88 150 samples, which amounts to 150 x 100 = 15000 denoising steps over an action sequence of dimensionality 112 with the DDPM scheduler.
In Table 1, we present results on DDPM, DDIM, DPMSolver, and their parallel variants (ParaDDPM, ParaDDIM, ParaDPMSollver) when combined with ParaDiGMS. We plot the model evaluations (number of calls to the diffusion model po), the task reward, and the sampling speed reported in time per episode. Although parallelization increases the total number of necessary model evaluations, the sampling speed is more closely tied to the number of parallel iterations, which is much lower. We see that ParaDDPM gives speedup of 3.7x, ParaDDIM gives speedup of 1.6x, and ParaDPMSolver gives a speedup of 1.8x, without a decrease in task reward. Table 2 presents similar findings on the PushT task, where
speedups all three methods with up to 3.9x speedup ParaDDPM.
Table 1: Robosuite Square with ParaDiGMS using tolerance of 0.1 and batch window size of 20 on a single A40 GPU. Reward is computed using an average of 200 evaluation episodes, with sampling speed measured time generate 400/8 50 samples.
Sequential
ParaDiGMS
Robosuite Square
Model Evals
Time per Episode
Model Evals
Parallel Iters
Time per Episode
Reward
Reward
Speedup
DDPM
100
0.85 + 0.03
37.0s
392
25
0.85 + 0.03
10.0s
3.7x
DDIM
15
0.83
0.03
5.72s
47
7
0.85
0.03
3.58s
1.6x
DPMSolver
15
0.85
0.03
5.80s
41
0.83 0.03
3.28s
1.8x

---

Table 2: PushT task with ParaDiGMS using tolerance of r 0.1 and a batch window size of 20 on a single A40 GPU. Reward is computed using an average of 200 evaluation episodes, with sampling speed measured as time to generate [300/8] |8] = 38 samples.
Sequential
ParaDiGMS
Model Evals
Time per Episode
Model Evals
Parallel Iters
Time per Episode
PushT
Reward
Reward
Speedup
DDPM
100
0.81
0.03
32.3s
386
24
0.83 0.03
8.33s
3.9x
DDIM
15
0.78
0.03
4.22s
46
0.77 0.03
2.54s
1.7x
DPMSolver
15
0.79 0.03
4.22s
40
0.79 + 0.03
2.15s
2.0x
Table 3: FrankaKitchen with ParaDiGMS using tolerance of r 0.1 and a batch window size of 20 on a single A40 GPU. Reward is computed using an average of 200 evaluation episodes, with sampling speed measured time generate 1200/8 = 150 samples.
Sequential
ParaDiGMS
Franka Kitchen
Model Evals
Time per Episode
Model
Parallel
Time per Episode
Reward
Reward
Speedup
Evals
Iters
DDPM
100
0.85 + 0.03
112s
390
25
0.84 + 0.03
33.3s
3.4x
DDIM
15
0.80 + 0.03
16.9s
47
7
0.80 0.03
9.45s
1.8x
DPMSolver
15
0.79 0.03
17.4s
41
0.80 0.03
8.89s
2.0x
The final robotics task we study is FrankaKitchen, a harder task with predicted action sequences of dimension 112 and an episode length of 1200. In Table 3 we notice some decline performance when sampling with reduced number of steps using DDIM and DPMSolver. On the other hand, ParaDDPM is able to maintain high task reward. Similar to before, ParaDiGMS consistently achieves a speedup across all 3 sampling methods, giving speedup of 3.4x with ParaDDPM, 1.8x with ParaDDIM, and 2.0 2x with ParaDPMSolver. These improvements translate to a significant decrease in the time it takes to roll out an episode in the Kitchen task from 112s to 33.3s.
4.2 Diffusion image generation
Next, we apply parallel sampling to diffusion- based image generation models, both for latent-space and pixel-space models. For latent-space models, we test out StableDiifusion->22 [26, 24], which generates 768x768 images using a diffusion model on a 4x96x96 latent space. For pixel-space models, we study pretrained models on LSUN Church' /Bedroom" from Huggingface [9, 35], which run diffusion model directly over the 3x256x256 pixel space.
4.2.1 Latent-space diffuuson models
Even with the larger image models, there is no issue fitting batch window size of 20 single GPU for parallelization. However, the larger model requires more compute bandwidth, so the parallel efficiency quickly plateaus the batch window size increases, the single GPU becomes bottlenecked by floating phating-point operations per second (FL.OP).. Therefore, for image models, we leverage multiple GPUs increase FLOPS and improve the wall-clock sampling speed.
In Fig. we examine the net speedup ParaDDPM relative to DDPM on StableDiiffusion-22 using 1000-step diffusion on A100 GPUs. The net speedup is determined by the interplay between algorithm inefficiency and hardware efficiency. Algorithm inefficiency refers to the relative number of model evaluations of ParaDDPM compared to DDPM, which arises from the parallel algorithm taking multiple iterations until convergence. We see in Fig. 4e that as the batch window size grows, ParaDDPM can require 2-3x more model evaluations. On the other hand, hardware efficiency refers to the relative empirical speedup of performing a batch of model evaluations. For example, in Fig. 4e see that evaluating batch window size of 80 4 GPUs (20 per GPU) is roughly 5x faster than performing 80 model evaluations sequentially. In Fig. 4f, we divide the hardware efficiency by the
'nctpe://huggiiggaace co co.goooll//d/mm/occoccooo ema- http://pppw.mamccchhhhhhheeeheaa church-
'https:/hhuggingfacce co/ www.googgo//////ooooooooooooeeoo haleee/ddmmmmm- ema- www.emaaroomm-----0 256
7

---

(a) "a beautiful castle, (b) "a batter swings at (c) "several sail boats in the (d) "a grey suitcase sits in water at night"
matte painting"
pitch during a baseball game"
front of a couch"
Efficiency of ParaDDPM StableDiffusiin--2. A100
Net speedup of ParaDDPM on StableDiftusion-22 A100
3.0
hardware edfiieecc
2.5
algorithm mofficiione
1.5
normalized algorithm inefficiency
mote Tapas
Supes
Iopus
-H- Sgpus
1.0
Lagar Aagiu
nugal digee
3gpus
Pepex
-M-- Sypus
-a--
Pupus
-x- 4upus
-x--
Bupus
20
40
60
80
100
120
140
160
80
100
120
140
160
batch window
(c) Hardware efficiency overtakes algorithm ineffi- (f) Over 3x net wall-clock specdup for 1000-step ParaD- ciency as number of GPUs increase.
DPM
Figure 4: StableDiiffssion-22 generating text-conditioned 768x768 images by running ParaDDPM over 4x96x96 latent space for 1000 steps, on A100 GPUs. In Fig. 4e algorithm inefficiency in gray denotes the relative number of model evaluations required the parallel batch window size increases. The colored lines denote the hardware efficiency provided by the multi-GPUs. As the batch window size increases, the hardware efficiency overtakes the algorithm inefficiency. Fig. 4f we normalize the algorithm inefficiency to 1, to show the net wall-clock speedup of parallel sampling.
algorithm inefficiency to obtain the net relative speedup of ParaDDPM over DDPM. We observe over 3x speedup by using a batch window size of 80 spread across A100s. Finally, in Table 4 we verify that ParaDiGMS increases sampling speed for ParaDDPM, ParaDDIM, and ParaDPMSolver without degradation sample quality as measured by CLIP score [8] on ViT-g-14 [23, 11].
One important consideration is that the algorithm inefficiency is agnostic to the choice of GPU. Therefore, as the parallel efficiency of GPUs in the future improve for large batch window sizes, will see an even larger gap between hardware efficiency and algorithm inefficiency. With enough hardware efficiency, the wall-clock time of sampling will be limited only by the number of parallel iterations, leading to much larger net speedup. For example, observe that in Table the number of parallel iterations of ParaDDPM is 20x smaller than the number of sequential steps.
4.2.2 Pixel-space diffusion models
Next, we test out ParaDiGMS pretrained diffusion models on LSUN Church and Bedroom, which perform diffusion directly on 3x256x256 pixel space. In Fig. 5 in Appendix D, we plot the net speedup of 1000-step ParaDDPM by dividing the hardware efficiency by the algorithm inefficiency. We observe similar trend of over 3x speedup when using multiple GPUs. Finally, we verify in Table 5 that ParaDiGMS maintains the same sample quality as the baseline methods as measured by FID score on 5000 samples of LSUN Church
6DPMSolver is not yet integrated with the LSUN model in the Diffusers library, omit its comparison.

---

Table Evaluating CLIP score of ParaDiGMS on StableDiffusion-22 over 1000 random samples from the COC02017 captions dataset, with classifier guidance = 7.5. CLIP score is evaluated on ViT-g- 14, and sample speed is computed on A100 GPUs.
Sequential
ParaDiGMS
Stable Diffusion-v2
Model Evals
CLIP Score
Time per Sample
Tol.
Model Evals
Parallel Iters
CLIP Score
Time per Sample
Speedup
DDPM
1000
32.1
50.0s
lc-1
2504
50
32.1
14.6s
3.4x
DPMSolver
31.7
10.3s
le-1
422
15
31.7
2.6s
4.0x
DDIM
200
31.9
10.3s
le-1
432
15
31.9
2.6s
4.0x
DDIM
100
31.9
5.3s
5e-2
229
19
31.9
2.0s
2.7x
DDIM
50
31.9
2.6s
5e-2
91
17
31.9
1.1s
2.4x
DDIM
31.7
1.38
1c-2
93
17
31.7
1.0s
1.3x
We highlight that 500-step DDIM gives noticeably worse FID score than 1000-step DDPM, whereas using ParaDDPM allows to maintain the same sample quality as DDPM while accelerating sampling (to two times faster than 500-step DDIM). The ability to generate an image without quality degradation in 6.1s as opposed to 24.0s can significantly increase the viability of interactive image generation for many applications.
Table 5: Evaluating FID score (lower is better) ParaDiGMS on LSUN Church using 5000 samples. Sample speed is computed on A100 GPUs. We use tolerance 5e-1 for DDPM and le-3 for DDIM.
Sequential
ParaDiGMS
Model Evals
FID Score
Time per Sample
Model Evals
Parallel Iters
FID Score
Time Sample
LSUN Church
Speedup
DDPM
1000
12.8
24.0s
2583
45
12.9
6.1s
3.9x
DDIM
500
15.5
12.2s
1375
41
15.3
3.7s
3.3x
DDIM
100
15.1
2.5s
373
23
14.8
1.0s
2.5x
DDIM
50
15.3
1.2s
168
15.7
0.7s
1.7x
DDIM
25
15.6
0.6s
70
15
15.9
0.6s
1.0x
4.3
Related work
Apart from DDIM [29] and DPMSolver [18], there number of other fast sampling techniques for pretrained diffusion models [14, 17, 19, 40]. Most these techniques are based on higher-ond order ODE-solving and should also be compatible with parallelization using ParaDiGMS. Other lines of work focus on distilling few-step model [25, 21, 30] or learning a sampler [37], but these methods restrictive they require additional training.
Besides diffusion models, many works have studied accelerating the sampling of autoregressive models using various approaches such parallelization [33, 311, distillation [13], quantization [6], or rejection sampling [3, 16]. Of particular note is [31], which samples from autoregressive models by iterating system of equations until convergence. While these methods not immediately applicable to diffusion models due to the differences in computational structure and inference efficiency of autoregressive models, there may be potential for further investigation.
Parallelization techniques similar to Picard iteration have been explored theoretical works for sampling from log-concave [27] and determinantal distributions [1]. Our work is the first application of parallel sampling on diffusion models, enabling a new axis of trading compute for speed.
5 Conclusion
Limitations Since our parallelization procedure requires iterating until convergence, total number of model evaluations increases relative to sequential samplers. Therefore, our method is not suitable users with limited compute who wish maximize sample throughput. Nevertheless, sample latency is often the more important metric. Trading compute for speed with ParaDiGMS

---

makes sense for many practical applications such as generating images interactively, executing robotic or serving users who are insensitive to the cost of compute.
policies in
Our method is also an approximation to the sequential samplers since we iterate until the errors fall below tolerance. However, we find that using ParaDiGMMS with the reported tolerances results in no measurable degradations of sample quality in practice across range of tasks and metrics. In fact, on more difficult metries such FID score on LSUN Church, ParaDDPM gives both higher sample quality and faster sampling speed than 500-step DDIM.
Discussion We present ParaDiGMS, the first accelerated sampling technique for diffusion models that enables the trade of compute for speed. ParaDiGMS improves sampling speed by using the method of Picard iterations, which computes multiple denoising steps in parallel through iterative refinement. Remarkably, ParaDiGMS is compatible with existing sequential sampling techniques like DDIM and DPMSolver, opening up an orthogonal axis for optimizing the sampling speed of diffusion models. Our experiments demonstrate that ParaDiGMS gives around 2-4x speedup over existing sampling methods across range of robotics and image generation models, without sacrificing sample quality. As GPUs improve. the relative speedup of ParaDiGMS will also increase, paving an exciting avenue of trading compute for speed that will enhance diffusion models for many applications.
Acknowledgments
This research supported in part by NSF (#1651565, #2045354, #2125511), ARO (W911NF-21-1- 0125), ONR (N00014-23-1-2159, N00014-22-1-22993) CZ Biohub, HAI.
References
[1] Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu. Parallel discrete sampling via continuous walks. In STOC '23: 55th Annual ACM SIGACT Symposium Theory of Computing. ACM, 2023.
[2] Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326, 1982.
[3] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Bean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013118 2023.
[4] Cheng Chi, Siyuan Feng, Yilun Du, Zhenjia Xu, Eric Cousineau, Benjamin Burchfiel, and Shuran Song, Diffusion policy: Visuomotor policy learning via action diffusion. arXiv preprint 203.v:2303.04137, 2023.
[5] Earl A Coddington, Norman Levinson, and T Teichmann. Theory of ordinary differential èquations. Physics Today, 9()):18, 1956.
[6] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Llm. int8 O): 8-bit matrix multiplication for transformers at scale. arXiv preprint arXiv:2208.07333 2022.
[7] Abhishek Gupta, Vikash Kumar, Corey Lynch, Sergey Levine, and Karol Hausman. Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning. arXiv preprint
2019.
[8] Jack Hessel, Ari Holtzman, Maxwell Forbes, Ronan Le Bras, and Yejin Choi. Clipscore: A reference-free evaluation metric for image captioning. arXiv preprint 1040:2104.00718. 2021.
[9] Jonathan Ho. Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6855 2020.
[10] Jonathan Ho and Tim Salimans. Classifier-free diffusion guidance. arXiv:220..12598, 2022.
arXiv preprint
10

---

[11] Gabriel Ilharco, Mitchell Wortsman, Ross Wightman, Cade Gordon, Nicholas Carlini, Rohan Taori, Achal Dave, Vaishaal Shankar, Hongseok Namkoong, John Miller, Hannaneh Hajishirzi. Ali Farhadi, and Ludwig Schmidt. Openclip, July 2021.
[12] Michael Janner, Yilum Du, Joshua B. Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. In International Conference on Machine Learning, ICMI. 2022,
2022.
[13] Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. Tinybert: Distilling bert for natural language understanding. arXiv preprint arXiv: 1909. 10351, 2019.
[14) Alexia Jolicoeur-Martinea, Ke Li, Rémi Piché-Taillefee Tal Kachman, and loannis Mitliagkas. Gotta go fast when generating data with score-based models. arXiv preprint arXiv:2105. /4080, 2021.
[15] Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Advances neural information processing systems, 34:21696-21777, 2021.
[16] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. International Conference on Machine Learning, ICML, 2023, 2023.
[17] Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao. Pseudo numerical methods for diffusion models on manifolds. In The Tenth International Conference on Learning Representations, ICIR 2022, 2022.
[18] Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm-solver: fast ode solver for diffusion probabilistic model sampling in around 10 steps. arXiv preprint arXiv:2206.00 00927, 2022.
[19] Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm- solver++: Fast solver for guided sampling of diffusion probabilistic models. arXiv preprint vrXiv:221..0099 2022.
[20] Dimitra Maoutsa, Sebastian Reich, and Manfred Opper. Interacting particle solutions of mokker-plancee equations through gradient-log don-iesstty estimation. Entropy, 22(8):802, 2020.
[21] Chenlin Meng, Ruiqi Gao, Diederik Kingma, Stefano Ermon, Jonathan Ho, and Tim Salimans. On distillation of guided diffusion models. arXiv preprint arXiv:2210.031442 2022.
[22] Tim Pearce, Tabish Rashid, Anssi Kanervisto, Dave Bignell, Mingfei Sun, Raluca Georgescu, Sergio Valcarcel Macua, Shan Zheng Tan, Ida Momennejad, Katja Hofmann, et al. Imitating human behaviour with diffusion models, arXiv preprint 2rX1::2301.10677 2023.
[23] Alec Radford, Jong Wook Kim, Chris Hallacy, A. Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In ICML, 2021.
[24] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björ Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference Computer Vision and Patlern Recognition, pages 10684-10695, 2022.
[25] Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. arXiv preprint arXiv:2202.00511 2022.
[26] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade W Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa R Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmar- czyk, and Jenia Jitsev. LAION-5b: An open large-scale dataset for training next generation image-text models. In Thitty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
11

---

[27] Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log- log-concave sampling. Advances Neural Information Processing Systems, 32, 2019.
[28] Jascha Sehl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages
PMLR, 2015.
[29] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[30] Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever. Consistency models, arXiv preprint (eXiv:2303.0146) 2023.
[31] Yang Song, Chenlin Meng. Renjie Liao, and Stefano Ermon. Accelerating feedforward compu- tation via parallel nonlinear equation solving. In International Conference Machine Learning. pages 9791-9800 PMLR, 2021.
[32] Yang Song, Jascha Sohl-Dickttein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In 9th International Conference on Learning Representations, ICLR 2021, 2021.
[33] Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018.
[34] Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. Advances in Neural Information Processing Systems, 34:1 1287-11302, 2021.
[35] Patrick von Platen, Suraj Patil, Anton Lozhkov, Pedro Cuenca, Nathan Lambert, Kashif Rasul, Mishig Davaadorj, and Thomas Wolf. Diffusers: State-of-the-arr diffusion models. https: //github. cww/hugging..eeeecccoccoccc.oomo aaceaa////iiae diffuserss 2022.
[36] Hsiang-Chin Chun Wang, Shang-Fu Fu Chen, and Shao-Hus Sun. Diffusion model-augmented behav- ioral cloning. arXiv preprint arXiv:2302. 330.33333. 2023.
[37] Daniel Watson, William Chan, Jonathan Ho, and Mohammad Norouzi. Learning fast samplers for diffusion models by differentiating through sample quality. In International Conference on Learning Representations, 2022.
[38] Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geo- metric diffusion model for molecular conformation generation. arXiv preprint arXiv:2203.0290 029233, 2022.
[39] Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao. Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop. arXiv preprint mrXivv:506.03330
2015.
[40] Qinsheng Zhang, Molei Tao, and Yongxin Chen. gddim: Generalized denoising diffusion implicit models. 2023.
[41] Yuke Zhu, Josiah Wong, Ajay Mandlekar, Roberto Martún-Martnn Abhishek Joshi, Soroush Nasiriany, and Yifeng Zhu. robosuite: A modular simulation framework and benchmark for robot learning. In arXiv preprint arXiv:2009. 12293, 2020.
12

---

A Proof of exact convergence
Proof of Proposition I. Assume by induction that &+1 z;
x; Then
k+1 #+1
+
T i=0
T
saat -,)
T - s + T)
x
Σ
T
xtt
1
s(atiiT)
t
T
16 (1 +)
1
xt +
क + T s(xi ) ait1
B Total variation analysis
Proof of Proposition 2. A linear convergence rate with factor 2 2 ensures our error from the solution at given by sequential sampling each timestep is bounded by the chosen tolerance:
|| --;1=
2;
lim
|
lim
2 | x 111 s
1
| xz K 111
j=K+1
j=K+1
Then, for each timestep 1, since the inference model samples from a Gaussian with variance of, we bound the total variation distance:
drv(N(af, o(z))
(N ,ff
[ of
| 407
xFl1?
|
xt
K
12
407
T
Finally, we make use of the data processing inequality, that dry (f(), I (rv((,Q)) Q), so the total variation distance d, between the sample and model distribution after t timesteps does not increase when transformed by pa- Then by the triangle inequality, we get that de S di-1 + e/T. giving a total variation distance dr of at most Te Te/T for the final timestep T.
C Parallel Computation on Multiple GPUs
We experimented with two different approaches to implementing parallel computation on multiple GPUs PyTorch: 1) using torch. nn. DataParallel and 2) using torch. www multtppooessing DataParallel is very easy to implement, but performed more poorly than multiprocessing. For multiprocessing, we use a producer/consumer design where we spawn single producer process on GPU 0 to run the main loop in Algorithm 1, and N consumer processes (one for each of the N GPUs) run Line 5 of Algorithm 1 in parallel. Empirically, this worked better than dedicating the producer process with its own GPU and using only N consumer processes, since the producer process requires very little GPU resources.
13

---

D Additional experiments
D.1 LSUN Church and LSUN Bedroom
In Fig. we plot wallclock speedup of ParaDDPM as function of batch window size and number of GPUs LSUN Church and LSUN Bedroom. These experiments on LSUN show a similar trend as the experiments on StableDiffusion-22 in Fig. 4f.
Net speedup ParaDDPM on church,
Net speedup of ParaDDPM LSUN bedroom, A100
3.0
3.5
2.5
3.0
net speeclu
1.5
normalized
algorithm
1.5
normalized algorttium
mefficiency
1.0
mole: Lggas
unte
Squus
ine/ficiency
-X-- Igpas
-x- Sepus
2apus
-x--
Supus
2gpus
Japus 4apus
7opus
Agpus
Pypux
-X- Ocpus
20
40
120
140
160
20
40
60
80
100
120
140
160
batch window size
botch window size
(a) LSUN Church, close 3x net wall clock speedup with 1000-step ParaDDPM using DataParallel
(b) LSUN Bedroom, over 3x net wall clock speedup with 1000-step ParaDDPM using DataParallel
Figure 5: Unconditional generation of 256x256 images on diffusion models pretrained on the LSUN Church and Bedroom dataset, running ParaDDPM for 1000 steps on A100 GPUs. We plot the net speedup after dividing the hardware efficiency by the algorithm inefficiency the batch window size increases. Note that Table shows better speedups because for Table 5 we use a better parallel implementation with multiprocessing instead of DataParallel.
D.2 Ablation
In Table 6, we run ablation study on the tolerance parameter 7 for 200-step ParaDDIM. A lower tolerance means the algorithm takes more parallel iterations and attains better sample quality, whereas higher tolerance means the algorithm slides the batch window forward more aggressively leading to fewer iterations and faster sampling. We see Table that for 200-step ParaDDIM on StableDiffusion-v2. a good choice of 7 is le-1. Lower tolerance levels give less speedup without noticeable increase in CLIP score, and higher tolerance levels exhibit a drop CLIP score.
Table 6: Ablation on the effect of error tolerance sample quality and speed StableDiffusion-v2 Samples are generated using ParaDiGMS with 200-step DDIM. CLIP score is computed over 1000 samples. Sample speed is computed on A100 GPUs.
Parallel Iters
Time per Sample
StableDiffusion-v2
Steps
Tolerance
Speedup
Score
DDIM
200
sequential
200
31.9
10.3s
DDIM
200
5c-3
36
31.9
7.4s
1.4x
DDIM
200
1c-2
28
31.9
5.1s
2.0x
DDIM
200
5c-2
19
31.9
3.3s
3.1x
DDIM
200
le-1
15
31.9
2.6s
4.0x
DDIM
200
Se-1
13
31.5
2.1s
4.9x
DDIM
200
lc-0
12
31.5
1.9s
5.4x
14


Reviews:
[{"review_id": "xmvRGWvjFB", "reviewer": "Reviewer_gnmk", "summary": "Naive parallelization can let us generate multiple samples which improves throughput. However, the wall-clock time remains the same. To reduce the wall-clock time during diffusion model sampling, this paper proposes ParaDiGMS, a parallel sampling method of diffusion models based on Picard Iteration which improves latency. ParaDiGMS is compatible with classifier-free guidance and prior fast sampling methods. The experiment results show that ParaDiGMS can achieve a speedup without quality degradation.", "questions": "In the section on experiments of diffusion image generation, the authors test ParaDiGMS on the settings of 1000 NFEs for DDPM, 200/500 NFEs for DDIM, and 200 NFEs for DPMSolver. It is questionable whether ParaDiGMS can achieve a similar speedup in fewer NFEs(like around 50 NFEs) since fewer NFEs are commonly used in downstream applications and the state-of-the-art samplers can achieve comparable results in this setting.", "limitations": "The author addressed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors provide a theoretical guarantee and error analysis of the proposed method.\n\n2. The paper is motivated by the classical Picard Iteration which brings new ideas to the diffusion sampling community.\n\n3. The paper is easy to follow and overall well-written which helps the reviewer understand the content.\n\n4. The experiment results show that it achieves a speedup with no measurable decrease in quality.", "weaknesses": "The applicability of the proposed method is limited to certain situations. The total evaluations of ParaDiGMS are approximately twice that of the baseline method according to the experiments. Therefore, the proposed method may not be suitable for situations where maximizing sample throughput is a priority.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review.\n\n&nbsp;\n\n>  **may not be suitable for situations where maximizing sample throughput is a priority**\n\nPlease see the shared response on “Focus on latency”. Our work indeed focuses on improving sample latency.\n\n&nbsp;\n\n> **It is questionable whether ParaDiGMS can achieve a similar speedup in fewer NFEs**\n\nPlease see the shared response on “Speedup with few steps”. We present exciting developments where we implement custom multiprocessing for ParaDiGMS and are now able to see a 2.5x speedup on the most widely used setting of 50-step DDIM, and a 1.3x speedup even for 25-step DDIM.\n"}, {"review_id": "lO7stmIDBl", "reviewer": "Reviewer_PoCx", "summary": "The authors propose a technique to reduce the time taken to sample from a diffusion model at the expense of using more FLOPs. Roughly speaking, the authors parallelize sampling by \"guessing\" xt at numerous values of t simultaneously, then computing the score function for each of these values of xt in parallel, and then repeating to refine the estimate of each xt over multiple steps.", "questions": "See above.", "limitations": "The limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is clearly written. \n- The proposed method is novel.\n- The proposed method is practically useful in situations where having low latency is important (e.g. iterative human-in-the-loop image generation).\n- The experiments are thorough, showing speed-ups on a range of domains and even showing speedups when efficient samplers like DPMSolver are used.", "weaknesses": "Overall I am satisfied that this paper makes a tangible contribution. I have a couple of questions though about certain scenarios in which it is not immediately clear that this method is useful.\n- I would be interested to see the performance of the latent image generation when less steps are used. E.g. for Stable diffusion (https://github.com/CompVis/stable-diffusion), the given example command \"python scripts/txt2img.py --prompt \"a photograph of an astronaut riding a horse\" --plms \" produces good images in only 50 steps, which is much less than the 200 used in Section 4.2.1. Does the proposed method still provide a gain in this setting?\n- How does this method interact with other techniques to speed up sampling like progressive distillation (https://arxiv.org/abs/2202.00512)? I appreciate that one benefit of the proposed method is that it avoids the need to have any sort of \"distillation\" training phase, but can the proposed method provide additional advantages when used in combination with a \"progressively distilled\" model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review.\n\n&nbsp;\n\n> **less steps are used.**\n\nPlease see the shared response on “Speedup with few steps”. We present exciting developments where we implement custom multiprocessing for ParaDiGMS and are now able to see a 2.5x speedup on the most widely used setting of 50-step DDIM, and a 1.3x speedup even for 25-step DDIM.\n\n&nbsp;\n\n> **How does this method interact with progressive distillation**\n\nIn terms of compatibility, our method can be used in combination with progressive distillation. The distilled models are sampled using sequential denoising, which can similarly be parallelized using ParaDiGMS. Since the distilled models use even fewer steps (e.g. 4 or 8), achieving speedups with parallel sampling may be more challenging, but we believe it may be possible with future improvements.\n\nIn terms of differences, as you correctly point out progressive distillation requires retraining, whereas our method is an off-the-shelf sampling method that does not require any additional training. It is also important to note that distillation often leads to slightly worse sample quality, whereas our method is able to maintain the same sample quality.\n"}, {"review_id": "ksP9OBLShk", "reviewer": "Reviewer_veyN", "summary": "The paper proposes an approach for speeding up sampling of diffusion models using Picard iterations. Multiple time steps in the sample process are predicted in parallel, iteratively refining until converging. Rather than refining all time steps at once which would not be practical, a sliding window approach is used: points in the window are refined then the window is moved once the later time steps have converged. Experimentally this approach is tested on diffusion policy learning and image generation benchmarks, where it is shown to provide substantial speedup over sequential sampling methods, while achieving comparable sample quality.", "questions": "- In Algorithm 1 on line 9, new points are initialised from the latest point in the window. Would it make more sense to initialise the values based on the prediction of $x_0$?\n- What practically is the impact of using different tolerance values?", "limitations": "Limitations are well discussed in section 4.2.1 and section 5. It’s also worth noting that due to the extra compute, this approach will use more energy so has a negative environmental impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Using Picard iterations to speed up diffusion model sampling makes sense and is useful in many low latency scenarios such as image editing.\n- Showing that in the worst case, the approach will converge faster at least as fast as sequential sampling is nice (Lines 127-137). Similarly, providing tolerance bounds is useful (Lines 161-164).\n- A good set of experiments/ablations on a variety of benchmarks are provided. The approach is clearly shown to be faster than sequential approaches, while providing similar quality samples.\n- The approach is tested with multiple diffusion samplers, including the recent DPMSolver, showing that it can provide speedup even to already fast solvers. ", "weaknesses": "- It is mentioned that a more relaxed tolerance value can be used when determining convergence (line 166). It would be useful to see the effect of that value on sampling times/image quality.\n- Currently multiple GPUs are required to achieve net speedup on Stable Diffusion (Figure 4f).\n- The approach is only useful for reducing latency; if generating lots of samples, then sampling batches sequentially is more efficient. However, as mentioned in the strengths, there are many applications where this is useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review.\n\n&nbsp;\n\n> **It would be useful to see the effect of tolerance on sampling times/image quality. What practically is the impact of using different tolerance values?**\n\nThanks for the suggestion. Here are additional experiments on a sweep over tolerance values for 200-step DDIM. We can see that the sample quality starts to degrade at a tolerance of 5e-1. We can use a tolerance of 1e-1 to maintain the same quality (or 5e-2 to be safe), and still achieve a sizable speedup compared to the sequential baseline.\n\nStable Diffusion v2-0\n| tolerance | CLIP | time | Parallel Iters |\n|-----------|------|------|------------|\n| DDIM 200 steps|           |      |      |\n| sequential   | 31.9      | 10.3 | 200  |\n| 5e-3         | 31.9      | 7.4 (1.4x) | 36   |\n| 1e-2         | 31.9      | 5.1 (2.0x) | 28   |\n| 5e-2         | 31.9      | 4.9 (2.1x) | 21   |\n| 1e-1         | 31.9      | 3.8 (**2.7x**) | 16   |\n| 5e-1         | 31.5      | 2.1 (4.9x)  | 13   |\n| 1e-0         | 31.5      | 1.9 (5.4x) | 12   |\n\n&nbsp;\n\n> **Currently multiple GPUs are required to achieve net speedup on Stable Diffusion**\n\nYes, multiple GPUs provide enough parallel computation to achieve net speedup on Stable Diffusion.\n\n&nbsp;\n\n> **only useful for reducing latency**\n\nPlease see the shared response on “Focus on latency”. Our work indeed focuses on improving sample latency.\n\n&nbsp;\n\n> **New points are initialised from the latest point in the window. Would it make more sense to initialise the values based on the prediction of x_0?**\n\nThis is a great suggestion! We tried some initial explorations on improving the initialization by extrapolating the trajectory using the prediction of x_0, but have not noticed consistent improvements over the current choice of copy initialization. The new suggestion is sometimes better but sometimes worse, so it may require more tinkering. In general, we do agree that the choice of initialization is a promising direction for further improvements, since the current choice of copy initialization is likely suboptimal.\n"}, {"review_id": "gwxFzC4qsl", "reviewer": "Reviewer_RXY2", "summary": "Instead of reducing the number of denoising steps, the paper proposes to  parallelize diffsuion denoising sampling via Picard iterations, by guessing the solution of future denoising steps and iteratively refining until convergence, which trades compute for speed. The authors then present ParaDiGMS to accelerate the sampling of pretrained diffusion models by denoising multiple steps in parallel and verify its effectiveness.", "questions": "**Q1**:  Some notations may be a bit confusing, since the $x_T$ is always used to represent the initial noise of diffusion and the authors use $x_0$ to represent the initial point.\n\n**Q2**: For Algorithm 1, given the same denoising steps $T$, the proposed method is essentially similar to the existing techniques such as PNDM, DPMSolver. The existing high-order techniques should also cache the predicted score in previous time step, while the proposed method compute all the predicted score in a small window and use them for next selected window.\n\n**Q3**: The number of model evaluations: For all the tables, do you choose a different $T$ and use more parallel iterations compared to the baseline to match the sampling performance? If so, what is the value of $T$ ? If I am not wrong, $T = Model Eval / Para Iter$ ? The details are not clear. \n\n**Q4**: Following the prior question, how about setting a same $T$? Can parallel sampling improve the performance (e.g. FID)? This results could be important. If the performance remain the same, people can directly use a smaller denoising step $T$.\n\n**Q5**:  For image generation,  does $batch size = 80$ mean the author uses a batch window size of $80$?\n\n**Q6**: The evaluation results of image generation are not sufficient. How about the commonly-used FID for stable-diffusion? And more qualitative results should be shown and analysed.\n\n**Q7**: The algorithm seems not practical. As the authors said, this method may consume more resources. However, **Q4** is not clear. If the performance remain the same, more resources should be used to maximize sample throughput instead of parallel computing.\n\n**Q8**: Related works should discuss more parallelization techniques and the differences of between the proposed method and similar parallelization techniques.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The idea is interesting and may promote another way for accelerated sampling.\n- The procedure of Algorithm is clear.", "weaknesses": "In total, I think there are still many problems for the paper. Please refer to the questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review. However, we believe that there is a misunderstanding as to the nature of our proposed method. ParaDiGMS is the first parallel sampling method for diffusion models: computing multiple denoising steps at the same time. This is fundamentally different from existing higher-order solvers, which uses multiple past timesteps to compute a single denoising step.\n\nIt appears that Q2, Q3, Q4, Q7, Q8 stem from this misunderstanding. Please see the responses below.\n\n&nbsp;\n\n> **Q1: the authors use x_0 to represent the initial point**\n\nYes, we make a note of this on L91 of the submission. \n\n&nbsp;\n\n> **Q2: For Algorithm 1, given the same denoising steps T, the proposed method is essentially similar to the existing techniques such as PNDM, DPMSolver**\n\nNo, this is not the case. Our proposed method is fundamentally different from existing techniques such as PNDM, DPMSolver since our method denoises in parallel. In fact, since our method and existing techniques are addressing orthogonal issues, they can even be combined (e.g. ParaDiGMS + DPMSolver = ParaDPMSolver), as we demonstrate in our paper.\n\nTo elaborate, these existing higher-order methods use multiple previous timesteps to predict a single denoising step. However, they are still sequential in nature, predicting one denoising step at a time. In contrast, our method predicts multiple steps in parallel, where each step can either be predicted using just the previous step (e.g. ParaDDIM) or using higher-order solvers (e.g. ParaDPMSolver).\n\n&nbsp;\n\n> **Q3: do you choose a different T and use more parallel iterations compared to the baseline to match the sampling performance? If so, what is the value of T? If I am not wrong, T = ModelEval/ParaIter? The details are not clear.**\n\nNo, we use the same T when comparing sequential and parallel sampling. For example, for DDPM we use T=1000. The number of parallel iterations is lower than T because we are computing multiple steps in parallel. \n\nModelEval/ParaIter does not equal T, but is rather (approximately) the batch window size, i.e., the number of steps we compute in parallel. The relationship is not exact because the batch window gets truncated near the endpoints of the trajectory.\n\n&nbsp;\n\n> **Q4: how about setting a same T? Can parallel sampling improve the performance (e.g. FID)?**\n\nWe are already using the same T. We would not expect parallel sampling to improve performance since we are using the same T. The goal of our method is to improve sample latency.\n\n&nbsp;\n\n> **Q5: does batchsize=80 mean the author uses a batch window size of 80?**\n\nYes, batchsize refers to “batch window size”. We will update this.\n\n&nbsp;\n\n> **Q6: How about the commonly-used FID for stable-diffusion? And more qualitative results should be shown and analysed**\n\nFor stable-diffusion the commonly used metric is CLIP score since it is a text-to-image task. We show the CLIP score in Table 4 of our paper.\n\nFor other tasks such as unconditional generation with LSUN, we show FID score in Table 5 of our paper.\n\nWe show some qualitative results in Figure 4, where we see that the generated images are of high quality. We can include more image samples in the updated version of our paper.\n\n&nbsp;\n\n> **Q7: The algorithm seems not practical. As the authors said, this method may consume more resources. However, Q4 is not clear. If the performance remain the same, more resources should be used to maximize sample throughput instead of parallel computing.**\n\nIt is unclear why the reviewer believes the algorithm is not practical. Our results show a very concrete 2-4x speedup in sampling latency across a range of diffusion policy and diffusion image generation tasks. \n\nThe goal of our method is not to improve performance or sample throughput, but to improve sample latency. Our method requires more computation, but for many applications sample latency is critical and/or users are insensitive to the cost of compute. Please see the shared response on “Focus on latency” for more details.\n\n&nbsp;\n\n> **Q8: Related works should discuss more parallelization techniques and the differences of between the proposed method and similar parallelization techniques.**\n\nTo our knowledge, our work is the first parallelization technique for diffusion model sampling, so there are no other similar techniques to compare with.\n\n&nbsp;\n\nWe hope this addresses your concerns, and we are happy to answer any additional questions regarding our paper. Please consider updating your score in light of the initial review’s misunderstanding of our work.\n"}, {"review_id": "0kyzBUo1l3", "reviewer": "Reviewer_psnQ", "summary": "The paper introduces a new method for speeding up (reduced latency) sampling of diffusion models by sampling all time steps in parallel from some initialization and then iterating this procedure until convergence (Picard Iteration). Modifications are made for implementation efficiency such as a sliding window. The method is evaluated on control tasks and large scale image datasets with a consistent reduction in latency at the expense of increased compute being reported.", "questions": "In proposition 2, how realistic is the assumption of the convergence rate of the Picard iterations in the context of integrating the probability flow ODE from a trained diffusion model?\n\nThis has been investigated somewhat between the two experiments but what would you say is the interaction between the number of Picard iterations and the number of steps used to integrate the ODE. Do you believe there could be any relation where more steps could be helpful to reduce the number of total Picard iterations or are these completely orthogonal quantities?", "limitations": "The method is obviously more expensive than other diffusion models due to all steps being taken in parallel but this trade-off is well explained. Further, as explained above, the limits of when the method does not actually provide a speedup could have been better investigated.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is very good. The problem being tackled is highly significant and I think the approach will be widely used to easily achieve a reduction in latency when extra compute is available. The method is clearly presented with a nice bit of theoretical analysis. The experiments on practically releveant datasets clearly show the benefits of the method. I highly encourage acceptance.", "weaknesses": "I think it would have been nice to pick a suitably small problem and fully explore the compute/latency tradeoff by varying the window size. I appreciate the current experiment in Figure 4 which does nicely show this trade-off in this compute intensive regime however the picture is slightly obscured by the necessity of also considering GPU flop/s saturation (which is an important consideration in its own right I agree). I think a simpler experiment where you can vary the window size all the way up to the number of denoising steps would benefit the paper where we can see a potential 20x reduction in latency if DDPM is integrated with 1000 steps and the Picard iterations converge in around 50 steps.\n\nFor the experiments on StableDiffusion, it is not clear to what extent the method's benefits extend into the very low model evaluation regime. DPMSolver should be able to go to very few model evaluations and retain decent quality, in this regime, how does your method compare? It is ok if the model speedup is less in this case, but it would be good to know the extent to which the method can provide benefits.\n\nI think it would be good to stick with the terminology batch window size as you go through the experiments. When getting to section 4.2.1 it is a little confusing to start talking about batch sizes which may imply that you are generating entirely independent trajectories in parallel but I assume you still mean the batch containing the points in the window.\n\nEdit after rebuttal: I have read the author's response and my concerns have been addressed. I will keep my score of 8.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review.\n\n&nbsp;\n\n> **pick a suitably small problem and fully explore the compute/latency tradeoff by varying the window size… vary the window size all the way up to the number of denoising steps.**\n\nThank you for the suggestion. To better explore this tradeoff of varying window sizes, we use the Square task from Table 1 using a single GPU. This task uses a smaller diffusion model, so the effects of FLOPS saturation is less noticeable (but unfortunately still present for large window sizes). We see that the relative speedup increases up until a batch window size of 150, and then decreases as FLOPS saturation kicks in.\n\nSquare Task\n| batch window size | samples/sec | relative speedup | Parallel Iters |\n|-------------------|-------------|------------------|------------|\n| 1 (sequential) | 1.09              | 1x          | 1000             |\n| 50             | 9.07              | 8.3x        | 76               |\n| 100            | 11.11             | 10.2x       | 56               |\n| 150            | 12.02             | 11.0x       | 49               |\n| 200            | 11.84             | 10.9x       | 47               |\n| 300            | 11.40             | 10.4x       | 44               |\n| 500            | 9.64              | 8.9x        | 43               |\n| 1000           | 7.69              | 7.0x        | 43               |\n\n\nFor batch window size of 150, we see that (sequential steps) / (parallel iterations) = 1000 / 49, giving an over 20x theoretical speedup, which is similar to that of image models as well (L252 in the paper). Unlike image models, however, FLOPS saturation is less of an issue here, so we are able to get a 11x speedup when using a batch window size of 150. This highlights the fact that the relative speedup of ParaDiGMS can increase as the effect of FLOPS saturation diminishes with better hardware in the future.\n\n&nbsp;\n\n> **to what extent the method's benefits extend into the very low model evaluation regime? in this regime, how does your method compare?**\n\nPlease see the shared response on “Speedup with few steps”. We present exciting developments where we implement custom multiprocessing for ParaDiGMS and are now able to see a 2.5x speedup on the most widely used setting of 50-step DDIM, and a 1.3x speedup even for 25-step DDIM.\n\n&nbsp;\n\n> **the limits of when the method does not actually provide a speedup could have been better investigated**\n\nBased on the new experiments, we see a drop in speedup for 25-step DDIM (1.3x) when compared to the speedup for 50-step DDIM (2.5x). This suggests that 25-step DDIM is roughly the limits of the current method on large models such as stable diffusion. On smaller models such as diffusion policy, we achieve large speedups even for 15-step DDIM.\n\n&nbsp;\n\n> **stick with the terminology batch window size as you go through the experiments. When getting to section 4.2.1 it is a little confusing to start talking about batch sizes**\n\nThanks for the catch, we will be consistent in referring to it as the batch window size.\n\n&nbsp;\n\n> **In proposition 2, how realistic is the assumption of the convergence rate of the Picard iterations in the context of integrating the probability flow ODE from a trained diffusion model?**\n\nWe believe that this assumption is very realistic in the setting of diffusion models, and empirically seems to be satisfied in the experiments we tried. One way to see this is that the tolerance used in our experiments to attain equal sample quality is much looser than the necessary tolerance stated in proposition 2. This suggests that the convergence rate in practice is much faster than the convergence rate stated in the assumption.\n\n&nbsp;\n\n> **what would you say is the interaction between the number of Picard iterations and the number of steps used to integrate the ODE. Do you believe there could be any relation where more steps could be helpful to reduce the number of total Picard iterations or are these completely orthogonal quantities?**\n\nBased on our exploration, empirically more steps for integrating the ODE generally leads to more Picard iterations for convergence. That being said, we think it may be possible that more steps can help reduce the number of Picard iterations, since more steps means that each step involves an easier prediction, which may translate to faster convergence.\n"}]

Author rebuttal:
Thank you all for the helpful reviews. We are happy to hear that our contribution “brings new ideas to the diffusion sampling community”, is “practically useful”, and is “highly significant and…will be widely used”. We also appreciate that reviewers found the writing “easy to follow and overall well-written”, with a “good set of experiments/ablations on a variety of benchmarks”.

&nbsp;

First, we have some exciting developments regarding speedups for low-step sampling. **We optimized our implementation for multi-GPU inference, and are now able to sample 2.5x faster on 50-step DDIM on stable diffusion (details below)!** This is very exciting as 50-step DDIM is the most popular setting used for stable diffusion.

&nbsp;

Next, we discuss two common points raised by the reviewers.

1. **Speedup with few steps** \
\
First, we note that our method shows around 2x speedup even when using very few steps (15-step DDIM and 15-step DPMSolver) on the diffusion policy experiments. For diffusion policy, the models are smaller so a single GPU can handle parallel computation without much slowdown. \
\
Since stable diffusion is a larger model, the FLOPS saturation of the GPU plays a large role, so running with multiGPU is necessary. Our initial implementation using torch.DataParallel had a large overhead when using fewer steps, so we were unable to see any speedups for 50-step DDIM. Torch DistributedDataParallel also did not work since our use case is inference and not training. \
\
Recently, we implemented custom multiprocessing inference for ParaDiGMS, and we are able to see a substantial speedup (2.5x) for DDIM 50 steps! This is very exciting since, as the reviewers noted, 50-step inference is the most popular and the default setting for stable diffusion. \
\
As suggested by the reviewers, we run additional experiments to evaluate our algorithm on 100-step, 50-step, and 25-step DDIM for stable diffusion. \
\
We note that when using fewer steps, the tolerance level should be lowered to maintain the same sample quality. For 100-step DDIM, tolerance 5e-2 achieves the same sample quality with 2.7x speedup. For 50-step DDIM, tolerance 5e-2 achieves the same sample quality with 2.5x speedup. For 25-step DDIM, tolerance 1e-2 achieves the same sample quality with 1.3x speedup. \
\
Stable Diffusion v2-0
| Method          | time         | CLIP | Parallel Iters |
|-----------------|--------------|------|----------------|
| DDIM 100 steps  |              |      |                |
| sequential      | 5.34         | 31.9 | 100            |
| tolerance 5e-2  | 1.96 (**2.7x**)  | 31.9 | 19             |
| tolerance 1e-1  | 1.68 (3.1x)  | 31.6 | 17             |
| DDIM 50 steps   |              |      |                |
| sequential      | 2.62         | 31.9 | 50             |
| tolerance 5e-2  | 1.05 (**2.5x**)  | 31.9 | 17             |
| tolerance 1e-1  | 0.93 (2.8x)  | 31.3 | 15             |
| DDIM 25 steps   |              |      |                |
| sequential      | 1.31         | 31.7 | 25             |
| tolerance 1e-2  | 0.99 (**1.3x**)  | 31.7 | 17             |
| tolerance 5e-2  | 0.76 (1.7x)  | 31.4 | 13             |

 2. **Focus on latency**\
\
As stated in the paper, and noted by many reviewers, the goal of our method is to improve sample latency but not throughput. For many applications such as interactive generation or real-time policy execution, sample latency is much more critical. Moreover, many users are insensitive to the cost of compute during inference, since the GPU demands during inference are much lower than that during training. Finally, we note that the reviewers are in agreement with us that “there are many applications where [improving latency] is useful”. 


&nbsp;

We are extremely excited about the immediate benefits of ParaDiGMS – a 2.5x speedup on the default setting of stable diffusion. We are even more excited about the general potential of parallel sampling and the new avenue of research it unlocks for diffusion models. We fully agree with the reviewers on the significance of the idea that our paper introduces to the community, and are eager for future improvements on aspects such as discretization, batch window initialization, or multiprocessing optimization.



Meta-review: The reviewers' assessment of the paper is exceptionally positive. They commend the practicality and significance of using Picard iterations for swift diffusion model sampling, particularly in time-sensitive scenarios like image editing. The paper's strength lies in demonstrating both faster convergence and tolerance bounds, supported by a thorough experimentation process that establishes its efficiency and comparable sample quality. The reviewer acknowledges the approach's superiority over sequential methods, even for already efficient solvers like DPMSolver.
Decision: Accept (spotlight)