Learning to Efficiently Sample from Diffusion Probabilistic Models
Authors: Daniel Watson
Jonathan Ho
Mohammad Norouzi
William Chan
Venue: ICLR 2022 Submitted (2022)

Abstract: Denoising Diffusion Probabilistic Models (DDPMs) have emerged as a powerful family of generative models that, yielding high-fidelity samples and competitive log-likelihoods across a range of domains, including image and speech synthesis. Key advantages of DDPMs include ease of training, in contrast to generative adversarial networks, and speed of generation, in contrast to autoregressive models. However, DDPMs typically require hundreds-to-thousands of steps to generate a high fidelity sample, making them prohibitively expensive for high dimensional problems. Fortunately, DDPMs allow trading generation speed for sample quality through adjusting the number of refinement steps during inference. Prior work has been successful in improving generation speed through handcrafting the time schedule through trial and error. In our work, we view the selection of the inference time schedules as an optimization problem, and introduce an exact dynamic programming algorithm that finds the log-likelihood-optimal discrete time schedules for any pre-trained DDPM. Our method exploits the fact that the evidence lower bound (ELBO) can be decomposed into separate KL divergence terms, and given any computation budget, we discover the time schedule that maximizes the training ELBO exactly. Our method is efficient, has no hyper-parameters of its own, and can be applied to any pre-trained DDPM with no retraining. We discover inference time schedules requiring as few as 32 refinement steps, while sacrificing less than 0.1 bits per dimension compared to the default 4,000 steps used on an ImageNet 64x64 model.

Under review as a conference paper at ICLR 2022
LEARNING TO EFFICIENTLY SAMPLE FROM DIFFUSION PROBABILISTIC MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Denoising Diffusion Probabilistic Models (DDPMs) have emerged powerful family of generative models that, yielding high-fidelity samples and competitive log-likelihoods across range of domains, including image and speech synthesis. Key advantages of DDPMs include ease of training, in contrast to generative adversarial networks, and speed of generation, contrast autoregressive models. However, DDPMs typically require hundreds-to-thousaadd of steps to generate a high fidelity sample, making them prohibitively expensive for high dimensional problems. Fortunately, DDPMs allow trading generation speed for sample quality through adjusting the number of refinement steps during inference. Prior work has been successful in improving generation speed through handcrafting the time schedule through trial and error. We instead view the selection of the inference time schedules as optimization problem, and show that, with a simple dynamic programming algorithm, one can find the nog-likelihoo--pptnne discrete time schedules for any pre-trained DDPM. Our method exploits the fact that the evidence lower bound (ELBO) can be decomposed into separate KL divergence terms, and given any computation budget, we discover the time schedule that maximizes the training ELBO exactly. Our method is efficient, has no hyper-parameters of its own, and can be applied to any pre-trained DDPM with no retraining. We discover inference time schedules requiring as few as 32 refinement steps, while sacrificing less than 0. bits per dimension compared to the default 4,000 steps used on an ImageNet 64x64 model.
INTRODUCTION
Denoising Diffusion Probabilistic Models (DDPMs) have emerged as a powerful class of generative
models (Sohl-Dickstein et al. 2015: Ho et al. 2020). DDPMs model the data distribution through an
iterative denoising process, and have been applied successfully to a variety of applications, including
unconditional image generation (Song & Ermon 2019 Ho et al. 2020 [Sng et al. 2021 Nichol &
Dhariwal 2021 shape generation (Cai et al. 2020), text-to-speech (Chen et al. [021 Kong et al.
2020) and single image super-resolution (Saharia al. 2021 Li al. 2021).
DDPMs are easy to train, featuring a simple denoising objective (Ho et al. 2020) with noise schedules that successfully transfer across different models and datasets. This contrasts Generative Adver- sarial Networks (GANs) (Goodfellow et al. 2014), which require an inner-outer loop optimization procedure that often entails instability and requires careful hyperparameter tuning. DDPMs also admit simple non- aotreutrrerrssvve inference process; this contrasts to autoregressive models with often prohibitive computational costs on high dimensional data. The DDPM inference process starts with samples from the corresponding prior noise distribution (e.g., standard Gaussian), and iteratively denoises the samples under the fixed noise schedule. However, DDPMs often need hundreds-to- thousands of denoising steps (each involving feedforward pass of large neural network) to achieve strong results. While this process is still much faster than autoregressive models, this is still often computationally prohibitive, especially when modeling high dimensional data.
There has been much recent work focused on improving the sampling speed of DDPMs. WaveGrad (Chen et al. (2021) introduced manually crafted schedule requiring only 6 refinement steps; however, this schedule seems to be only applicable to the vocoding task where there is very strong conditioning signal. Denoising Diffusion Implicit Models (DDIMs) (Song et al. 2020) accelerate sampling from

---

Under review as a conference paper at ICLR 2022
pre-trained DDPMs by relying on family of non-Markovian processes. They accelerate the generative process through taking multiple steps in the diffusion process. However, DDIMs sacrifice the ability compute log-iikllshoods Nichol & Dhariwal (202T) also explored the use of ancestral sampling with subsequence of the original denoising steps, trying both a uniform stride and other hand-crafted strides. (San-Roman al. (2021) improve few-step sampling further by training separate model after training a DDPM to estimate the level of noise, and modifying inference to dynamically adjust the noise schedule at every step to match the predicted noise level.
All these fast-sampling techniques rely on a key property of DDPMs - there is decoupling between the training and inference schedule. The training schedule need not be the same as the inference schedule. e.g., a diffusion model trained to use 1000 steps may actually use only 10 steps during inference. This decoupling characteristic typically not found other generative models. In past work, the choice of inference schedule was often considered hyperpameter selection problem, and often selected via intuition or extensive hyperparmeter exploration (Chen al. 2021). In this work, we view the choice of the timesteps of the inference schedule (which we just call an inference path) as an independent optimization problem, wherein we attempt to learn the best schedule. Our approach relies on the observation that we can solve this optimization problem with dynamic programming. Given a fixed budget of K refinement steps and pre-trained DDPM, we find the set of timesteps that maximizes the corresponding evidence lower bound (ELBO). As optimization objective, the ELBO has a key decomposability property: the total ELBO is the sum of individual KI. terms, and for any two inference paths, if the timesteps (s, t) contiguously occur both, they share common KL term, therefore admitting memoization (see Section 4.1 for a precise definition).
Our main contributions are the following:
We introduce a method that that finds the likelihood-opimall inference paths with a simple dynamic programming algorithm for all possible computation budgets K refinement steps. The algorithm searches over T > K timesteps, only requiring O(T) neural network forward passes. It only needs to be applied once to a pre-trained DDPM, does not require training or retraining DDPM, and is applicable to both time-discrete and time-continuous DDPMs.
We experiment with DDPM models from prior work. On both Lsimpee CIFARIO and Lhybrid ImageNet 64x64, we discover schedules which require only 32 refinement steps, yet sacrifice only 0.1 bits per dimension compared their original counterparts with 1,000 and 4,000 steps, respectively.
We show that our method can be applied to any decomposable set of objectives. In particular, optimizing a reweighted ELBO can favourably bias our algorithm towards solutions with better FID scores, as we find that optimizing the exact variational lower bound may lead to worse FID) scores, which is consistent with prior work on unconditional image generation.
BACKGROUND ON DENOISING DIFFUSION PROBABILISTIC MODELS
Denoising Diffusion Probabilistic Models (DDPMs) (Ho et al. 2020
Sohl-Dickstedi et al. 2015) defined in terms of a forward Markovian diffusion process g and a learned reverse process po- The forward diffusion process gradually adds Gaussian noise data point æn through T iterations,
( ma) II q(are #z-1),
q(=; x = .(xx; /o: x:;11, - o))
(2)
where the scalar parameters a1.r determine the variance of the noise added at each diffusion step. subject to 0 < < 1. The learned reverse process aims to model ((xo) by inverting the forward process, gradually removing noise from signal starting from pure Gaussian noise TT,
p(ær)
N(rr 0, T
(3)
Po (xo.T) ((ΦT) II,
| po pa(xx-11 x.))
(4)
Pe(0,-)) ax) N( Mo(are 1),
(5)
The parameters of the reverse process can be optimized by maximizing the following variational lower bound on the training set:
T -
E, ((0o) ) 2 E, (eopo -
DKL.
Lr(
(6)
2

---

Under review as a conference paper at ICLR 2022
where (x0)) DKL ( p(xx)) Nichol & Dhariwal (202)) have demonstrated that training DDPMs by maximizing the ELBO yields compentive log- likelihood scores on both CIFAR- 10 and ImageNet 64 x 64 achieving 2.94 and 3.53 bits per dimension respectively.
Two notable properties Gaussian diffusion process that help formulate DDPMs tractably and efficiently include:
q(<x mo) Na Ve 2o, (1 1)
where 7t III di
((x211 2o a..) N -V(( / (1 az) + var (1 - 1- (1 m-1) ar)
(8)
-++
7
Given the marginal distribution of 2t given Wo in 7 dently for different and perform SGD on a randomly chosen KL term in (6). Furthermore, given that the posterior distribution of # given æ and mn is Gaussian,
sample from the q(æ; æo) indepen-
compute each KI. term in (6) between two Gaussians closed form and avoid high variance Monte Carlo estimation.
3 LINKING DDPMS TO CONTINUOUS TIME AFFINE DIFFUSION PROCESSES
Before describing our approach to efficiently sampling from DDPMs, helpful to link DDPMs to continuous time affine diffusion processes, as it shows the compatibility of our approach to both time-discrete and time-continuous DDPMs (Song et al. 2021 Kingma et al. 2021). Let æo ~ ( denote a data point drawn from the empirical distribution of interest and let ((Z2/<0) denote stochastic process for E [0, 1] defined through an affine diffusion process through the following stochastic differential equation (SDE):
dx, = fsae + gude (t)dB;
where f Osde [0, 1] [0. 1] are integrable functions satisfying fado()) and Gsde (0) 0.
Following Särkkä & Solin (2019) (section 6.1,, we can compute the exact marginals g (x.) for
any s<1s I. We get:
(L (((t:u))g(u) ())
q(x; xx)) N xt (t,ts))a
(10)
where (t,,s) exp 1 fu)du. Since these integrals are difficult to work with, we instead propose (in parallel to Kingma et al. (202I) to define the marginals directly:
q( xo) N(xx f() g(t)²())
(11)
where f.g: [0.1] + j0, 1] are differentiable. monotonic functions satisfying f(0) = 1, f(1 = 0, (0) 0,1(1) = 1. Then, by implicit differentiation it follows that the corresponding diffusion is
dx, f(()) f(t)
(((gg()) f(t)
x,dt + /
2g(() g'(()
dB.
(12)
We provide a proof for Equation
12 in the appendix (A.1) To complete our formulation, let fts = f(t
f(a)
and It. = g(t - fi.g(s)² Then, it follows that for any 0 < <<t we have that g(xx v.s))
NV (ax: (1s
(13)
1
Looi I
g(x,, xc, x,, 20) .r xs
(Fsagisao + f, 220
(14)
We include proofs for [3) and [4p in the appendix (A.2). These equations show that we can perform inference with any ancestral sampling path (i.e., the timesteps can attain continuous values) by formulating the reverse process in terms of the posterior distribution as
Po (= xx.) (2x, xt, ae fo (a,, ())c)(z,,t)),,
(15)
justifying the compatibility of our main approach with time-continuous DDPMs. We note that this reverse process is also mathematically equivalent to reverse process based on time-discrete DDPM derived from a subsequence of the original timesteps as done by SSong et al. (2020); Nichol &
Dhariwal (2021). l). For the case of 0 in the reverse process, we follow the parametrization of Ho ct al. (2020) to obtain discretized log likelihoods and compare our log likelihoods fairly with prior work.
3

---

Under review as a conference paper at ICLR 2022
Algorithm Given matrix L [[++)x(T++) Algorithm 2: Fetch the shortest path of steps from the dynamic programming results implicitly returned by Algorithm 1.
of precomputed -(.,)) terms, find the likelihood-
optimal schedules for step budgets.
def vectorizees vectorized_dp_al Luudgges (
def fetch_shortest__
(D, K)
I 1en (L) -
optpath = I]
D np. full (I. shape, -1)
t =
C full (I. shape, ap.inf) CIO, 0]
for k in reversed (range (K)
optpath. optpath.appendd())
for k in range (1, I 1)
= D(k, t]
bpós = c[k 1, None] L
return optpath
C[k] np.amin (bpds, axis=-1) [[k] np.argmin (bpds, axis--1)
return C
LEARNING TO EFFICIENTLY SAMPLE FROM DDPMS
We now introduce our dynamic programming (DP) approach. general. after training DDPM, one can use different inference path than the one used during training. Additionally, one can optimize loss or reward function with respect to the timesteps themselves after the DDPM trained. this paper, we use the ELBO as our loss function, however we note that it is possible to directly optimize the timesteps with other objectives.
4.1 OPTIMIZING THE ELBO
In our work, we choose optimize ELBO as our objective. We rely on one key property of ELBOs. their decomposability. Before defining decomposability, we formally define K K-step inference path as a finite, monotonically inereasing sequence of timesteps = to < f < ... 1-x-1 < t'x Now, given S S [0, 1]. we define a family of lower bounds L of "ideal" objective Lideal be S-decomposable if:
1. There is a bijection from L to the set of all inference paths t with all timesteps in S, and 2. There exists a function S x S - [0, oo) such that, for all inference paths with all timesteps in S, Lideal 2 Σ -1
i=1 L(t,, + C (C' constant).
We now show that DDPM ELBOs are decomposable. As shown by Song et al. (2000) Nichol & Dhariwal (202T) and the equations in Section for any K and any K -tep inference path ł, there corresponding ELBO
TELBO
F.g DEL (g(20) Pon
Σ
(16)
where
L(1,)) 8) = - E.g log Po(xx, xx)) DKL (g(2) ( 20) (=)
8=
(17)
8 8> 0
Since all of these lower bounds of IE, log p(w)), conclude the family of DDPM evidence lower bounds is decomposable. Specifically, a DDPM trained on a set of timesteps S admits S- decomposable ELBOs. For DDPMs trained with continuous timesteps, trained on discrete timesteps, S is the set of those timesteps, as there is no guarantee that the behavior of the model won't pathological when give timesteps it has never seen during training. Now the question remains, given fixed budget K steps, what is the optimal inference path?
[0, 1]. For DDPMs
First, we observe that any two paths that share a (f,, s) transition will share a common L s) term. We exploit this property in our dynamic programming algorithm. When given grid S of plausible inference paths 0 = to < t1 < ... < ft-1 < tr = with 2 K, it is possible to efficiently find the ELBO-optimal K-step inference path contained in S by memoizing all the individual L s) ELBO terms for s, E (to...., )r) with s < t. We can then solve the canonical least-cost-par path problem on directed graph where
are nodes and the edge connecting them has cost T1(1,)).
4

---

Under review as a conference paper at ICLR 2022
4.2 DYNAMIC PROGRAMMING ALGORITHM
We now outline our methodology to solve the least-cost-paie path problem. Our solution is similar to Dijkstra's algorithm, but it differs to the classical least-cost-pthh problem where the latter typically used, as our problem has additional constraints: we restrict our search to paths of exactly K + nodes, and the start and end nodes are fixed.
Let C' and D be (K + 1) x (T 1) matrices. Clk, t] will be the total cost of the least-cost-path of length & from to 0. will be filled with the timesteps corresponding to such paths; i.e., Dik, will be the timestep immediately previous to / for the optimal k-step path (assuming / is also part of such path).
We initialize C 0] = 0 and all the other C[ to oo (the DIO, :] are irrelevant, but for ease of index notation we keep them in this section). Then, for each from to K, we iteratively set, for each f,
Clkc t| = min (Cīk 1, L(t, s))
D[k: t] arg min (C - 1 + L(t,s))
where [(I, 8) is the cost to transition from / (see Equation 17 For all we set L(l, 8) oo (e.g., we only move backwards in the diffusion process). This procedure captures the shortest path cost C' and the shortest path itself in D. We further observe that running the DP algorithm for each k from 1 to I (instead of K), we can extract the optimal paths for all possible budgets K. Algorithm 1 illustrates vectorized version of the procedure we have outlined in this section, while Algorithm shows how to explicitly extract the optimal paths from D.
4.3 EFFICIENT MEMOIZATION
A priori, our dynamic programming approach appears to be inefficient because it requires computing ( terms (recall, as we rely on all the L(t, s) terms which depend on a neural network forward pass). We however observe that a single forward pass of the DDPM can be used to compute all the L(L,)) terms. This holds true even in the case where the pre-trained DDPM learns the variances. For example, in Nichol & Dhariwal (021) instead of fixing them gt.- Stx9.
outlined in the previous section, the forward pass itself still only depends on and not 8, and the variance of pa (xs (x:)) obtained by interpolating the forward pass's 's output logits with exp( v log gi. + (1 v) log 9 Thus, computing the table of all the L(t, s) ELBO terms only requires (TT) forward passes.
Sto
Even stride
Even stride
Quadratic stride
Quadratic stride
(bits/dim)
DP stride
NLLL (bits(cllm)
DP stride
rehinement steps
rehhnnment stops
Figure 1: Negative log likelihoods (bits/dim) for Lybb CIFARIO (left) and Laybria ImageNet 64x64
(right) for strides discovered via dynamic programming v.s. even and quadratic strides.
5 EXPERIMENTS
We apply our method on wide variety of pre-trained DDPMs from prior work. This emphasizes the fact that our method is applicable to any pre-trained DDPM model. In particular, we rely the CIFARIO model checkpoints released by Nichol & Dhariwal (021) both their Laybad and Lub objectives. We also showcase results on CIFARIU (Knzhevsky et al. 2009) with the exact configuration used by Ho al. 2020). which denote as Tsimple: well Taybrid ImageNet 64x64 (Deng et al.
5

---

Under review as a conference paper at ICLR 2022
Table Negative log likelihoods (bits/dim) in the few-step regime across various DDPMs trained on CIFARIO, as well as Mfate-of-the-an unconditional generative models in the same dataset. The last column corresponds 1,000 steps for simple and 4,000 steps for all other models.
Model refinement steps
8
16
32
64
128
256
All
DistAug Transtormer (Jun
2020)
2.53
DDPM++ (deep. sub- VP) [Song et al. 2021
2.99
Lximple
Even stride
6.95
6.15
5.46
4.91
4.47
4.14
3.73
Quadratic stride
5.39
4.86
3.84
3.74
3.73
DP stride
4.59
3.99
3.79
3,74
3.73
3.72
Linh
Even stride
6.20
5,48
4.89
4.42
4.03
3.73
2.94
Quadratic stride
4.89
4.09
3.23
3.09
3.05
DP stride
4.20
3.41
3.17
3.08
3.05
3.04
Laghrid
Even stride
6.14
5.39
4.77
4.29
3.92
3.66
3.17
Quadratic stride
4.91
4.15
3.42
3.30
3.26
DP stride
4.33
3.62
3.39
3.30
3.27
3.26
Table Negative log likelihoods (bits/dim) in the few-step regime for DDPM model trained with Laybnd on ImageNet 64x64 (Nichol & Dhariwal, (021), as well state-of saate-of-the-aee the art unconditional generative models the same dataset. We underline that, with just steps, our DP stride achieves score of < 0.1 bits/dim higher than the same model with the original 4,000 step budget ("the authors report 3.57 bits/dim, but we trained the model for 3M rather than 1.5M steps).
Model refinement steps
16
32
64
128
256
4000
Routing Transformer (Roy et al. 2021
3,43
Ltbb (Nichol & Dhariwal 2021)
3,53
Liybrid
Even stride
6.07
5.38
4.82
4.39
4.08
3.87
3.55
Quadratic stride
4.83
4.14
3.65
3.58
3.56
DP stride
4.29
3.80
3.65
3.59
3.56
3.56
2009) following Nichol & Dhariwal (2021). training these last two models from scratch for 800K and 3M steps, respectively, but otherwise using the exact same confi configurations the authors.
In our experiments, we always search over a grid that includes all the timesteps used to train the model, i.c., (t/T: {I...,, T 1}}. For our CIFAR10 results, we computed the memoization tables with Monte Carlo estimates over the full training dataset, while on ImageNet 64x64 we limited the number of datapoints the Monte Carlo estimates 16,384 images on the training dataset.
For each pre-trained model, we compare the negative log likelihoods (estimated using the full heldout dataset) the strides discovered by our dynamic programming algorithm against even and quadratic strides, following Song et al. (2020). We find that our dynamic programming algorithm discovers strides resulting in much better log likelihoods than the hand-crafted strides used prior work, particularly in the few-step regime. We provide visualization of the log likelihood curves function of computation budget in Figure I for simple CIFARIO and Layorid ImageNet 64x64 (Deng ct al. 2009), a full list of the scores in the few-step regime in Table 1, and visualization of the discovered steps themselves in Figure 2.
5.1 COMPARISON WITH FID
further evaluate our discovered strides by reporting FID scores (Heusel et al. 2017) on 50,000 model samples against the same number of samples from the training dataset, as is standard in the literature. We find that, although our strides are yield much better log likelihoods, such optimization does not necessarily translate also improving the FID scores. Results included in Figure 3. This weakened correlation between log- likehoossods and FID is consistent with observations in prior work (Ho et al. 2020 Nichol & Dhariwal 2021

---

Under review as a conference paper at ICLR 2022
Even stride
100
(50,003 camples)
Quadratic
FID (50 0000000 samples!
DP stride
50
60
20
Quadratic stride
10
DP stride
16
32
64
128
236
512
1000
retinement steps
NLL (bitsidim)
Figure 2: FID scores for Liiple CIFARIO, as a function of computation budget (left) and negative log likelihood (right).
To remedy this issue, we show that despite our focus in this work being likelihood, we can significantly improve the FID scores discovered by our method simply by optimizing a reweighted ELBO. Recall that, as discussed in Section our proposed method is compatible with any decomposable objective. Moreover, prior work has shown that the choice of ELBOO weights has significant effect on sample quality (Ho et al. [220 Durkan & Song 2021). and that choosing weights corresponds to choosing an equally valid variational lower bound of the data for a DDIM (Song et al. 2020). Similarly to prior work in the VAE literature, we thus stumble upon open problem where different variational lower bounds compatible with the model (even with the same bits/dim) can lead to samples with different qualitative charachteristics (Alemi al. 2018). As focus is likelihood, research question of finding the weights ELBO that lead to most agreement with FID for future work, but nevertheless identify one such choice that favourably biases algorithm toward this front. Details about our construction weights and results are included in the appendix A.3)
leave this
5.2 MONTE CARLO ABLATION
To investigate the feasibility of our approach using minimal computation, we experimented with setting the number of Monte Carlo datapoints used to compute the dynamic programming table of negative log likelihood terms to 128 samples (i.e., easily fit into single batch of GPU memory). We find that, for CIFAR10, the difference log likelihoods is negligible, while on ImageNet 64x64 there is visible yet slight improvement in negative log likelihood when filling the table with more samples. We hypothesize that this due the higher diversity of ImageNet. Nevertheless, we highlight that procedure can be applied very quickly (i.c., with just T forward passes of neural network when using a single batch, as opposed a running average over batches), even for large models, significantly improve log their likelihoods in the few-step regime.
datapoints
50000 datapoints
16384 datapoints
(bits/dlm)
NLL (oits/clm)
32
230
refinement Steps
refinemment Steps
Figure 3: Negative log likelihoods (bits/dim) for Lximgle CIFAR10 and Layania ImageNet 64x64 for strides discovered via dynamic programming with log-likelihood term tables estimated with varying number of datapoints.
7

---

Under review as a conference paper at ICLR 2022
32 steps
64 steps
128 steps
256 steps
1.000 steps
Real samples
Figure 4: Non-cherrypicked Limple CIFARIO 10 samples for even (top), quadratic (middle), and DP
strides (bottom), for various computation budgets. For each step budget, the samples were produced with the same random vectors.
32 steps
64 steps
128 steps
256 steps
4,000 steps
Real samples
Figure 5: Non-cherrypicked Layhria ImageNet 64x64 samples for even (top), quadratic (middle), and DP strides (bottom), for various computation budgets. For each step budget, the samples were produced with the same random vectors.
RELATED WORK
DDPMs (Ho et al. 2020) have recently shown results that are competitive with GANs (Goodfellww al. 2014), and they can traced back to the work Sohi--issteiin et al. (2015) as restricted family of deep latent variable models. Dhariwal & Nichol 2021) have more recently shown that
DDPMs can outperform GANs in FID scores (Heusel et al.J (017). Song & Ermon (0019) have also linked DDPMs to denoising score matching (Vincent et al.) 2008 (010), which is crucial to the continuous- time formulation (Song et al.) 2021: Kingma et al. (022). More recent work on the few-step regime of DDPMs (Song al.] 2020 Chen et al. [2221] Nichol & Dhariwal 2021 SannRoman et al. 202T Kong & Ping [2021] Jolicoeur- Martinnn et al. 2021) has also guided our
research efforts. DDPMs also very closely related variational autoencoders (Kingma & Welling
8

---

Under review as a conference paper at ICLR 2022
1000
4000
512
2008
refineme steps
512
256
refinneme
128
61
1500 2500 2000 Discovered steps
4000
Discovered steps
Figure 6: Timesteps discovered via dynamic programming for simple CIFARIO (left) and Lyybeid ImageNet 64x46 (right) for various computation budgets. Each step (forward pass) is between two contiguous points. Our DP algorithm prefers allocates steps towards the end of the diffusion, agrecing with intuition from prior work where steps closer Zo important as they capture finer image details, but curiously, it may also allocate steps closer to æ1, possibly to better break modes early on in the diffusion process.
2013), where more recent work has shown that, with many stochastic layers, they can also attain competitive negative log likelihoods unconditional image generation (Child 2020). Also very closely related to DDPMs, there has also been work non-autooegreessiee modeling of text sequences that can be regarded as discrete-space DDPMs with forward process that masks or remove tokens (Lee et al. 2018 Gu al. 2019 Stern al. 2019 Chan al., 2020 Saharia al. 2020). The UNet architecture (Ronneberger et al. 2015) has been key to the recent success of DDPMs, and as shown by Ho al. (2020): Nichol & Dhariwal (202T), augmenting UNet with self-attention (Shaw et al.) 2018) in scales where attention is computationally feasible has helped bring DDPMs closer to the current state-of-the-art autoregressive generative models (Child et al.
2019
Jun et al. 2020
Roy
iet al. 2021
7 CONCLUSION AND DISCUSSION
By regarding the selection of the inference schedule as an optimization problem, we present a novel and efficient approach discover a likelihood-optimal inference schedule for pre-trained DDPM with simple dynamic programming algorithm. Our method need only be applied once to discover the schedule, and does not require re-training the DPPM. In the few-step regime, we discover schedules on Limple CIFAR 10 and Lhybria ImageNet 64x64 that require only 32 steps, yet sacrifice < 0.1 bits per dimension compared to state-of-the-arr DDPMs using mundreds-to-thousame approach only needs forward passes of the DDPM neural network to fill the dynamic programming table of (tt, s) terms, and we show that we can fill the dynamic programming table with just O(T) forward passes. Moreover, we can estimate the table using only 128 Monte Carlo samples, finding this to be sufficient even for datasets such as ImageNet with high diversity. Our method achieves strong likelihoods with very few refinement steps, outperforming prior work utilizing hand-crafted strides (Ho et al. 2020 Nichol & Dhariwal 2021).
refinement steps. Our
Despite very strong log-liieldhood results, we observe that maximizing the unweighted ELBO can actually lead to higher (worse) FID scores, and on ImageNet 64x64, a decrease in sample quality for the smallest budgets K E {32, 64]; this is consistent with findings in prior work (Ho et al. 2020 Nichol & Dhariwal 2021). Nevertheless, our method is compatible with any decomposable objective such as reweighted variational lower bounds, and we show that a simple choice of reweighted ELBO (or equivalently a choice of DDIM) can remedy this issue. Developing principled methods to choose variational lower bounds or other decomposable metrics that correlate best with image quality is thus an important direction for future research. Finally, we remark that likelihood optimization itself is useful for specific applications: as well as better compression, in domains such as non-autoregressive text generation where likelihood correlates much better with sample quality and where diffusion models are starting to make progress (Austin et al.) 202I), our method has the potential to improve sampling speed with far less cost in generation fidelity and without such adaptations.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We will fully open source our work and provide code pointers in the paper in the camera-ready version. Nevertheless, we provide pseudocode with a complete implementation of our proposed algorithm to maximize ease of reproducibility while we work on apen-sourcing our work (see Algorithms ?? and ?? Since we experiment with open-sourced datasets and pre-trained models that already have publicly available checkpoints, our work is fully reproducible. We additionally emphasize that our method has no hyperparameters of its own.
ETHICS STATEMENT
Innovations in generative models have the potential to enable harmful and unethical applications. In applications where no harm is intended, bias and other failure modes of generative models and datasets used to train them can also lead to issues with fairness, discrimination, and other forms of harm. While our work focused on making diffusion models more efficient, believe its public release will not cause any form of immediate harm, much more efficient generative models for images like GANs can still achieve high sample quality fraction of the speed of diffusion models.
REFERENCES
Alexander Alemi, Ben Poole, Ian Fischer, Joshua Dillon, Rif A Saurous, and Kevin Murphy. Fixing broken elbo. In International Conference on Machine Learning, pp. 159-168. PMLR, 2018.
Jacob Austin, Daniel Johnson, Jonathan Ho, Danny Tarlow, and Rianne van den Berg. Structured denoising diffusion models discrete state-spaces. arXiv preprint arXhv:2107.33006 2021.
Ruojin Cai, Guandao Yang. Hadar Averbuch-Elor, Zekun Hao. Serge Belongie, Noah Snavely, and Bharath Hariharan. Learning Gradient Fields for Shape Generation. ECCV, 2020.
William Chan, Chitwan Saharia, Geoffrey Hinton, Mohammad Norouzi, and Navdeep Jaitly, Imputer: Sequence Modelling via Imputation and Dynamic Programming. In ICML, 2020.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron J. Weiss, Mohammad Norouzi, and William Chan. WaveG- rad: Estimating Gradients for Waveform Generation. In ICLR, 2021.
Rewon Child. Very deep vaes generalize autoregressive models and can outperform them on images. arXiv preprint arXiv:201 10600 2020.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprinl arXiv: 0904/9044//// 10509, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Prafulla Dhariwal and Alex Nichol. Diffusion models beat gans on image synthesis. arXiv preprint arXiv:2105.05233. 2021.
Conor Durkan and Yang Song. On maximum likelihood training of score-based generative models. arXiv preprint
2021.
Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks, arXiv preprint arXiv: 1406 2, 2014.
Jiatao Gu, Changhan Wang, and Jake Zhao. Levenshtein Transformer. In NeurlPS, 2019.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Berhhard Nessler, and Sepp Hochreiter. Gans trained by a two time-seale update rule converge to a local nash equilibrium. arXiv preprint arXiv: /000:/770.088800 08500, 2017.
10

---

Under review as a conference paper at ICLR 2022
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising Diffusion Probabilistic Models. NeurIPS, 2020.
Alexia
Ke Li, Rémi Piché-Taillefee Tal Kachman, and Ioannis Mitliagkas. Gotta go fast when generating data with score-based models, 2021.
Heewoo Jun, Rewon Child, Mark Chen, John Schulman, Aditya Ramesh, Alec Radford, and Ilya Sutskever. Distribution Augmentation for Generative Modeling. ICML, 2020.
Diederik P Kingma and Max Welling. Auto-Encoding Variational Bayes. In ICLR, 2013.
Diederik P Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. arXiv preprint arXiv:2107.006:33 2021.
Zhifeng Kong and Wei Ping. On fast sampling of diffusion probabilistic models, 2021.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. WiffWave: A Versatile Diffusion Model for Audio Synthesis. arXiv preprint arXiv:2009.09761, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report, 2009.
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic autorerrsseee neural sequence modeling by iterative refinement. arXiv preprint arXiv: arXiv: /80.009010 2018.
Haoying Li, Yifan Yang. Meng Chang, Huajun Feng, Zhihai Xu, Qi Li, and Yueting Chen. SRDiff: Single Image Super- Resoluton with Diffusion Probabilistic Models. arXiv:2104.14951, 2021.
Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. arXiv preprint arXiv:2102.09672, 2021.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241. Springer. 2015.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68, 2021.
Chitwan Saharia, William Chan, Saurabh Saxena, and Mohammad Norouzi. Non-Autoregressive Machine Translation with Latent Alignments. EMNLP, 2020.
Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David Fleet, and Mohammad Norouzi. Image super-resolution via iterative refinement. arXiv preprint arXiv:2 104.07604 2021.
Robin San-Roman, Eliya Nachmani, and Lior Wolf. Noise estimation for generative diffusion models. arXiv preprint arXiv: 104.02600, 2021.
Simo Särkkä and Amo Solin. Applied stochastic differential equations, volume 10. Cambridge University Press, 2019.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. arXiv preprint arXiv:1803.0211 021555, 2018.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pp. 2256-2265. PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502. 2020.
Yang Song and Stefano Ermon. Generative Modeling by Estimating Gradients of the Data Distribution. NeurlPS, 2019.
11

---

Under review as a conference paper at ICLR 2022
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-Based Generative Modeling through Stochastic Differential Equations. JCLR, 2021.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit, Insertion Transformer: Flexible Sequence Generation via Insertion Operations. In ICML, 2019.
Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pp. 1096-1103, 2008.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and
Léon Bottou. Stacked denoising autoencoders: Learning useful representations in a deep network with local denoising criterion. Journal of machine learning research, 11(12), 2010.
12

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
A.1
PROOF FOR EQUATION
12
From Equation 10
we get by implicit differentiation that
f(t) (tt, 0) exp So Suae [use(u)ddu)
+1) exp (Lo [
dt Lo Saae (u)duu Smte
d
(() fade (1) f(1)
Similarly above and also using the fact that (11,,) 8)
19(t,0)
3*(x,0)
o(t)² '/' vitt, u)t,u))gno gude (u)² I.¹ f(1)
f(u)2 Inde (u) f()²² S/"
gotclu)² du f(u)2
=2g(t)g 21())(()) 8(12
f(t)2 5(1) J gulcl)) du 2S (1) Iste (t)2
f(u)
(tadet) (((o(t)g((t - faa (t)g((t))
A.2 PROOF FOR EQUATIONS 13 AND
From Equation 10 and (t, s)
(t.0)
it is immediate that fis is the mean of (x To show that
(s.0)
Li, is the variance of ((<,/=,), Equation 10 implies that
Var (ar[x,/20.,1
(t, u) (u)
1 st, 2) gade (u)
S vttt, u)2 gute gu)e (u) du
g(t)² 0)² Sr (ss u), 0)2 Inde (n)c((e))22 (2)
v1s u)²
(bs u)²
g(1)² 01,
(s, Iste (u) (u)
g(t)² (t, gss)
=(t)² faag())2
The mean of q(x, 20) is given by the Gaussian conjugate prior formula (where all the distributions are conditioned on ro). μ feS so we have a prior over μ given by
22 N (Saoro (a) la) + p/a00 W[Sooorra La
Pa Ia),
and likelihood with mean μ
Zt |z To Felæ, N(fists. P., 21lM,20 x (N..
Then it follows by the formula that wlare, 2o has variance
(Tr +
P2gz
faggng
Varjulue,
Pig.f0
Dis
PE 2
Fis
3
F20th
2
~Varfa, (2,, vo]
Varlul soo
92
f2c
ghs
figg
g
13

---

Under review as a conference paper at ICLR 2022
Table FID scores in the few-step regime across DDPMs trained on CIFARIO and ImageNet 64x64, compared to DDPM and DDIM(1 0) with different strides. The last column corresponds to 1,000 steps for CIAFRIO simple and 4,000 steps for ImageNet 64x64 Lnybrid The best results are highlighted in bold, and the second best are underlined.
Model # refinement steps
8
16
32
64
128
256
All
CIFARIO simple
Even stride (DDPM)
51.04
28.83
20.85
13.50
10.01
7.61
3.17
Quadratic stride (DDPM)
51.44
25.80
12.85
7.73
5.63
5.25
Even stride (DDIM)
26.96
15.88
11.12
8.40
6.61
5.50
Quadratic stride (DDIM)
19.24
9.49
6,16
5.09
4.70
4.57
DP stride
62.79
45.90
21.11
8.52
5.47
5.05
DP stride + MSE rewcighting
58.11
29.44
12.07
6.74
5.24
5.13
ImageNet 64x64 Lnyhrid
Even stride (DDPM)
72.76
37.25
21.83
16.66
14.99
14.72
3.19
Quadratic stride (DDPM)
223.6
73.10
38.69
22.45
16.99
15.37
Even stride (DDIM)
52.37
27.02
20.25
17.85
16.99
16.51
Quadratic stride (DDIM)
243.1
59.80
29.27
20.80
17.82
16.81
DP stride
184.0
124.0
71.15
40.45
23.87
17.62
DP stride MSE reweighting
146.4
85.42
48.10
28.88
20.45
17.10
and mean
1
fuo
2t
foogi.00
flag Hha
fuogis + flagoore Pd
gis
flagoo
gia.
fro
Pr To + feaPan
1
fis
Sangi mn Sea (es
+R[r, va]
Jtx
970
A.3 REWEIGHTED ELBO RESULTS
While the focus of work is likelihood, report FID scores for the sake of completeness, well as to show the adaptability of our method via reweighting to focus on sample quality, as mentioned in Section 5_
To choose a reweighting scheme for each L(t, s) term that takes into account both / and 8, Kingma
al. (02T) show that choosing discretized terms
[ w(w))NR'(u)d ||ا0 - de (Ee, 1)1
Lan (L, 8) =
(18)
ensures that the limit of infinite timesteps the continuous ELBO becomes E, fo (C))SNR'(()llaa) - to((,, dt (where SNR(t) 9io
fü and constant w(t) = 1
yields the unweighted ELBO).
While choosing w(l) SNR(t) (which is Liiple at the limit) did not work, we find that choosing SNR(()
w(() SN (which leads to a continuous objective of unweighted mean square errors and
(t, s) = (t 25-ss]ees s) Lo (x,, 1²) allows our algorithm to outperform DDPM FID scores and achieve similar scores DDIM (Song et al. 2020). We call this "MSE reweighting" and include FID scores in Table comparing to DDPM but also DDIM(1 0) which does not admit likelihood computation but has been shown to be one of the strongest FID baselines the few-step regime. The FID scores were estimated with 50,000 model and training data samples, as is standard in the literature.
14

---

Under review as a conference paper at ICLR 2022
A.4 NOTE ON SAMPLING STRATEGIES FOR FAIR COMPARISON
Finally, we discuss an alternative approach to that used in the figures of the paper for producing more qualitatively comparable samples. Given fixed budget K, Figures 4 and 5 are produced to generate "comparable" samples across different strides by fixing all the standard Gaussian vectors the sampling chain. However, another approach that allows to compare samples across different budgets is to fix single Brownian motion trajectory on all I" steps, and using discretizations (based on any stride) of this single random trajectory to generate the samples. We empirically find, however, that the former approach tends to produce much more similar images (see Figures 7 and 8 below). We suspect that the use of different strides (and hence different random directions from the fixed random trajectory) along with the very chaotic, non-linear behavior of DDPMs is the cause of this behavior.
32 steps
64 steps
steps
256 steps
1,000 steps
Real samples
Non-cherrypicked simple CIFARIO samples for even (top), quadratic (middle), and DP strides (bottom), for various computation budgets. All samples use the same random trajectory.
Figure 7:
32 steps
64 steps
128 steps
256 steps
4,000 steps
Real samples
Figure 8: Non-cherrypicked Layeni ImageNet 64x64 samples for even (top), quadratic (middle), and DP strides (bottom), for various computation budgets. All samples use the same random trajectory.
15


Reviews:
[{"review_id": "eCYeaACnE_3", "reviewer": "Reviewer_EgPP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Some things are introduced but never clearly explained. The most important one is you never explicitly say what *decomposable* means. I think most readers can figure it out, but only *after* reading the paper. You write a bit on page 2, but I would make it even more clear, as it is important for reading the rest.\nAlso: what is an ELBO path?\n\nOn page 4, you write: \"we can optimize a loss or reward function with respect to the timesteps themselves (after the DDPM is trained).\" \nCan you explain again what this means?\n\nCondition 1 on page 4: \"The path starts at t = 0 and ends at t = 1.\" \nIs it not possible to both scale and translate the timescale? How restrictive is this really?\n\nWhat is it about some regularization methods that makes your approach not work? Breaking the decomposability? \nCan the authors think of other regularization methods that break the approach?\n\nMy key concern: In *actual* compute time (say, seconds) how long does it take DP stride with 128 steps take compared to 128 Quadratic stride? To me it looks like 128 is enough for quadratic stride to catch up to your method, so how much is there to win by choosing your algorithm?", "summary_of_the_paper": "This paper presents a dynamic programming algorithm to sample from diffusion models. In short, they solve a Dijkstra-type problem on pretrained diffusions, and show good results even with coarse discretizations. ", "summary_of_the_review": "Overall, the paper gives a nice overview of the literature and present a new inference scheme in post-training scenarios. I have some remarks above that can make me reconsider my evaluation, and I hope for a nice discussion with the authors.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "A9Mx4ieSKrZ", "reviewer": "Reviewer_xjpp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strengths:\n* The dynamic programming problem identified by the authors is an elegant and efficient approach to address the sampling limitations of DDPMs. It is natural to frame the search for an optimal schedule as a Dynamic Programming problem, and the authors show this problem can be efficiently solved in linear rather than quadratic time.\n* The proposed method shows a significant improvement in model performance as measured by log likelihood compared to prior methods when applying a pre-trained DDPM over a greatly reduced set of time steps.\n\nWeaknesses:\n* The main weakness of this work is that the method appears to overfit the ELBO objective without improving (and potentially reducing) the visual quality of generated samples. In particular, the proposed method can significantly improve the log likelihood over few-step diffusion paths compared to prior techniques. However, the Dynamic Programming step schedules can actually decrease the quality of visual appearance, as measured by FID, compared to previous methods. Personally, I consider FID to be a much more reliable indicator of model quality than the log likelihood, due to its sensitivity to small changes, ability to detect mode coverage, and the fact that FID is model-agnostic, while log likelihood can only be applied to models with a tractable density or ELBO. The authors acknowledge this limitation and explore efficient schedules for maintaining low FID/high visual quality, but these results do not improve upon prior methods. Thus, while the authors achieve their intended goal of efficient and high log likelihoods via their new method, the outcome might not be particularly meaningful since it doesn't really improve model/sample quality.\n* I am unsure of the relevance of Section 3. How does this fit into the presentation in Section 4? See \"Other Comments\" below.\n\nOther Comments:\n* In Section 3, there is a claim that \"These equations show that we can perform inference with any ancestral sampling path (i.e., the timesteps can attain continuous values)\" but in Section 4, there is a claim that \"For time-continuous DDPMs, the choice of grid (i.e., the $t_1, \\dots,  t_{T −1})$ can be arbitrary. For models trained with discrete timesteps, the grid must be a subset of (or the full) original steps used during training.\" Why does the method not work for arbitrary continuous time steps if the model is trained with discrete time steps? The first claim makes it seems like that would be possible.\n* Why were some of the models used retrained, instead doing testing using only fixed pretrained models?", "summary_of_the_paper": "This work presents a method to efficiently sample from a pre-trained DDPM by solving a dynamic programming problem that can maximize the log likelihood of the data samples given a fixed computational budget. This is done by defining a least-cost path problem to select a reduced set of time steps among a full grid of potential time steps across different possible step budget sizes, where the ELBO is used as the cost function. The authors show that their method can identify DDPM schedules that can achieve significantly higher log likelihood (i.e. lower bits/dim) than prior DDPM schedules in the regime where about a hundred steps or fewer are used.", "summary_of_the_review": "Overall, I found the approach to efficient DDPM sampling employed by the authors to be sensible and reasonably novel. While their method can indeed effectively increase log likelihood for DDPM with a greatly reduced grid of time steps, this did not appear to translate to improved model quality in terms of actual generated samples. The final conclusion is therefore somewhat unsatisfying because an ideal DDPM schedule would be short and efficient, able to produce high log likelihoods, and able to produce low FID scores compared to other methods. Since this goal is not achieved, I recommend that the authors revisit their approach to identify if there is a way to more effectively incorporate sample quality (rather than log likelihood) in their DP algorithm.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8c5LTmQLPs5", "reviewer": "Reviewer_2CEn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The paper is very clearly written, and I enjoyed reading this paper.\n\nThe main attraction of this paper is the dramatic increase in computational efficiency -- the authors discuss one example in which 4000 steps in the SDE solver are replaced with merely 32 steps. [I will tend to refer to things as being steps of an SDE solver, even in the discrete case, since that's basically what's going on.] This is certainly a dramatic claim, as the high computational cost of DDPMs has so far been one of their major limiting factors.\n\nThe suggested technique seems to be mostly reasonable. Overall the dramatic reduction in steps feels \"too good to be true\" -- a sentiment that is largely borne out by Section 5.1, in which it is demonstrated that improving the ELBO does not necessarily imply improving the FID. As the authors note, it is multiple to derive multiple valid ELBOs, so this is a case in which optimising the ELBO need not imply actually improving the model.\n\nOverall, my take on this paper is that speed is improved, but it is hit-and-miss whether model performance is compromised whilst doing so. This is reflected in my middling-acceptance score. With some refinement I could see the techniques this paper proposes being of great utility.\n\n## Figure 5\n\nOne meaningful weakness in the presentation is Figure 5, in which I think different Brownian sample paths were used to generate each image. I do note that the text claims that the same random seed was used, but the variety -- both within each group-of-steps, and between each group-of-steps, means I am skeptical. My guess is that (a) different Brownian sample paths were used for each group of steps, and (b) within each group of steps, \"using the same random seed\" does not actually refer to using the same Brownian motion; rather it refers to using the same increments (each of which are rescaled by $\\alpha$, $\\sigma$ or $g$, depending on your notation). This is not at all the same thing as using the same Brownian motion.\n\nThe appropriate thing to do would be to use the same continuous-time Brownian motion sample for every single picture shown in Figure 5. Every time a point is queried (presumably nearly always at a point that it has not been queried at before, as different step schemes may place steps is very different places), then a Brownian bridge should be constructed between the two samples already observed either side of it.\n\nThe authors have not released code so I cannot see what library they are using themselves, but the above procedure may easily be done using the `BrownianInterval` of the `torchsde` library [1]. Make sure to use a single `BrownianInterval` object for the entirety of generating a figure (recreating a new one at any point would be a mistake, as it is deterministic only up to both its seed *and* the points it has already been queried at). (To give the appropriate references: the \"Brownian Interval\" was introduced in [2], as an improvement of the \"Virtual Brownian Tree\" of [3].)\n\nIf the above procedure is followed then I would expect the generated samples to much more closely resemble each in other, and in doing so be able to better understand the effect of increasing the number of steps. (Which is, after all, central to this paper.)\n\n## Other remarks\n\nEquation (16) is clearly central to the paper. However, it pretty much comes out of nowhere. (At least for the reader who doesn't hold all the mathematics of DDPMs in their head.) I think that a derivation would be a meaningful improvement to the paper.\n\nThe dynamic programming algorithm outlined in Section 4.2 feels essentially standard -- besides Dijkstra's algorithm, it also seems very reminiscent of dynamic time warping. I regard the main contribution of this paper as the identification that step locations can be chosen via DP; not the algorithm itself.\n\nThe entire paper is framed only in the context of inference. I speculate that it might also be useful in the context of training: minimising training costs, especially for expensive models such as these, is a topic of great importance. Perhaps the procedure suggested in this paper could be re-run every N training steps, for some N?\n\n## Ethics statement\n\nI would have thought that improving the computational efficiency of costly models would have some (perhaps small) positive impact on the pressing issue of climate change. It seems a bit perverse that this *positive* ethical impact is not discussed in the ethics statement.\n\n## Minor points\n\n- $D_{KL}$ never has brackets around its arguments -- e.g. it's just $D_{KL} p(x)q(x)$ rather than $D_{KL}(p(x), q(x))$ or $D_{KL}(p(x)||q(x))$.\n- Page 4: The abbreviation \"i.e.\" is usually discouraged in academic writing.\n- Algorithms 1 and 2: These are a weird a mix of pseudocode and Python. I think it would be preferred to pick just one. (Especially as they rely on behaviour specific to NumPy, such as indexing by `None`.)\n- I am not convinced how meaningful the discussion in Section 4.3 really is. It points out that $O(T)$ forward passes are required. As each forward pass takes $O(T)$ work then overall $O(T^2)$ work is required -- exactly as expected. What is new here?\n- I don't think \"BPD\" (page 7) is defined.\n\n## References\n\n[1] Li. \"torchsde\" https://github.com/google-research/torchsde\n\n[2] Kidger et al. \"Efficient and Accurate Gradients for Neural SDEs\" NeurIPS 2021 https://arxiv.org/abs/2105.13493\n\n[3] Li et al. \"Scalable Gradients for Stochastic Differential Equations\" AISTATS 2020 https://arxiv.org/abs/2001.01328", "summary_of_the_paper": "Samples are generated from DDPMs by solving an SDE (often in \"discrete time\", which is used to refer to specifically the Euler--Maruyama discretisation). This necessitates a choice for where to make numerical steps. Each choice of step locations has a corresponding ELBO. This paper demonstrates that (on a pretrained model) the optimal ELBO may be obtained via a dynamic programming algorithm for the location of the steps.", "summary_of_the_review": "Possibly with some refinement, the paper has the potential to be very good. As it stands it presents a dramatic speed improvement that may-or-may-not produce compromise the final model. Overall I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a dynamic programming strategy for faster approximate generation in denoising diffusion probabilistic models.

All reviewers appreciated the paper, but they are not overly excited. 

Two reviewers are focused on the log likelihood not being the objective for image quality. This AC does not really buy this argument. 

The method and story around are well-rounded and finished. So it is hard to think of any major modifications that will change the overall story a lot. One could therefore argue for acceptance as it stands. On the other hand this is difficult to argue for given the below acceptance level scores. 

So the final recommendation is reject with a strong encouragement to submit to the next conference. Updating the paper with preemptive arguments on why the ELBO and not FID is the right thing to consider.
Decision: Reject