Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strengths:
* 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.
* 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.

Weaknesses:
* 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.
* I am unsure of the relevance of Section 3. How does this fit into the presentation in Section 4? See "Other Comments" below.

Other Comments:
* 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.
* Why were some of the models used retrained, instead doing testing using only fixed pretrained models?
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
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.
Also: what is an ELBO path?

On page 4, you write: "we can optimize a loss or reward function with respect to the timesteps themselves (after the DDPM is trained)." 
Can you explain again what this means?

Condition 1 on page 4: "The path starts at t = 0 and ends at t = 1." 
Is it not possible to both scale and translate the timescale? How restrictive is this really?

What is it about some regularization methods that makes your approach not work? Breaking the decomposability? 
Can the authors think of other regularization methods that break the approach?

My 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: The paper is very clearly written, and I enjoyed reading this paper.

The 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.

The 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.

Overall, 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.

## Figure 5

One 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.

The 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.

The 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].)

If 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.)

## Other remarks

Equation (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.

The 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.

The 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?

## Ethics statement

I 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.

## Minor points

- $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))$.
- Page 4: The abbreviation "i.e." is usually discouraged in academic writing.
- 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`.)
- 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?
- I don't think "BPD" (page 7) is defined.

## References

[1] Li. "torchsde" https://github.com/google-research/torchsde

[2] Kidger et al. "Efficient and Accurate Gradients for Neural SDEs" NeurIPS 2021 https://arxiv.org/abs/2105.13493

[3] Li et al. "Scalable Gradients for Stochastic Differential Equations" AISTATS 2020 https://arxiv.org/abs/2001.01328
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.
review_title: null

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