Summary
This paper proposes a new method for parallelizing the sampling process of diffusion models, offering a novel way to trade compute for speed. In particular, it relies on the parareal iteration in this setting, where the main idea is to split the solving timesteps into multiple groups and then update them in parallel. To ensure that the output from these timestep groups matches the exact solution, parareal performs predictor-corrector steps after each group is updated. Experiments demonstrate the efficacy of applying parareal iteration in speeding up the sampling process.
Strengths
1. This paper demonstrates a very interesting direction by introducing the parareal iteration into diffusion models.
2. The experiments indeed demonstrate the efficacy of this approach.
Weaknesses
1. I think the author misses a rigorous discussion comparing the parareal algorithm with ParaDiGMS [1] and also completely ignores a more recent reference [2]. It is clear that all these works, including parareal, focus on parallelizing the sampling process via certain forms of fixed-point iteration, although the computing graphs of these algorithms differ. The only discussion in the current manuscript is that ParaDiGMS is highly memory-intensive and must use a sliding window. While this statement is certainly true, I believe it is not a disadvantage of ParaDiGMS and does not imply that ParaDiGMS is inferior to parareal. I do not see why using a sliding window should be considered a disadvantage.
2. As far as I can see, the Eff. Serial Evals in Table 1 and Table 2 should correspond to the Parallel Iters in [1] and Steps in [2], am I correct? Because Eff. Serial Evals essentially represent the number of batch evaluations on the models. If this is the case, based on the current numbers in Table 1, it seems quite inferior to the results in [1] and [2]. Of course, I understand that the batch size may be different in this work, but I still wish the author would provide a detailed discussion on this point.
3. Proposition 1 in the manuscript is somewhat trivial and exists in many existing works. Note that each refinement consists of $\sqrt n$ sequential evaluation, so the parareal will also require at most $\sqrt n \times \sqrt n=n$ sequential evaluation on the models to converge. I think the author should mention that this result is fundamentally equivalent to Proposition 1 in [1], and a more general result is found in Theorem 3.6 in [2]. The key point is that when performing fixed-point iteration for an $n$-order triangular system, it will certainly converge within $n$ steps, and this bound can not be further improved without extra assumption.
[1] Shih, Andy, et al. "Parallel sampling of diffusion models." Advances in Neural Information Processing Systems 36 (2024).
[2] Tang, Zhiwei, et al. "Accelerating parallel sampling of diffusion models." Forty-first International Conference on Machine Learning. 2024.
Questions
1. In my understanding, the technique in Parareal have a different spirit in parallelization with [1][2]. For example, consider that we wish to do n-step sampling with $\sqrt n$ batchsize. Given a initial sequence $[x_1,...,x_n]$, parareal first group them into $g_1=[x_1,...,x_{\sqrt n}],...,g_{\sqrt n}=[x_{n-\sqrt n},x_n]$. The parallelism is that to update $g_1$, ..., $g_n$ in parallel, while the update of each $g_i$ consists of $\sqrt n$ sequential solving. On the other hand, [1][2] consider update $[x_{i},...,x_{i+\sqrt n}]$ in parallel until convergence. It is not clear to me which one is better from the theoretical aspects, as they have the same worst-case convergence bound. I suspect that it should depends on the form of ODE and also the batchsize? I wonder if the authors could provide some thought and discussion on this point?
2. Do you think parareal can be applied to the SDE sampler as [1] and [2] did?
[1] Shih, Andy, et al. "Parallel sampling of diffusion models." Advances in Neural Information Processing Systems 36 (2024).
[2] Tang, Zhiwei, et al. "Accelerating parallel sampling of diffusion models." Forty-first International Conference on Machine Learning. 2024.
Limitations
See my comments on weaknesses and questions above. This work lacks a correct and thorough discussion comparing it to existing works.