We thank the reviewer for the review, and are excited to hear that the reviewer finds the novel ideas presented to be very interesting, and that the experiments indeed demonstrate the efficacy of this approach! We respond to the concerns below:

Baselines

Please refer to the combined response to all reviewers. We thank the reviewer for bringing [2] to our attention; we were not aware of this very recent work (ICML 2024) at the time of writing this paper. However, their method uses completely different techniques (namely, formulating and solving a triangular system in a specialized way) to solve the same problem. We have discussed this work in the common response, and will make sure to include a detailed discussion in the final manuscript.

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

Thank you for highlighting the difference in notation between the papers. You are correct that the Eff. Serial Evaluations correspond to the Parallel Iters in [1] and Steps in [2], where all refer to the number of batched evaluations. We will be sure to clarify this notation in updates to the paper.

The reasons for the seemingly high number of Eff. Serial Iterations is twofold:

• Stricter convergence criteria for SRDS: We note that there is a considerable difference in the how the convergence criteria is calculated for ParaDiGMS and SRDS. ParaDiGMS using a per step tolerance proportional to the scheduler’s noise magnitude and aggressively (and irrecoverably) slides the sliding window if an early step has “converged”; this gives very loose guarantees of the final generated image. On the other hand, SRDS only directly considers differences in the final output representation to decide convergence. This strict/conservative threshold for our pixel diffusion results in Table 1 causes larger number of effective serial iteration. One can comfortably relax this threshold and still maintain good sample quality (as seen in the ablation study in Appendix C). Alternatively, as we show for StableDiffusion, one can instead limit the number of iterations and drastically reduce the Eff. Serial Evaluations (comparable to ParaDiGMS) with no measurable degradation in sample quality! In fact, even for pixel-based diffusion models, we can similarly limit the number of SRDS iterations to 1 or 2 without degradation in sample quality (Figure 7 in Appendix C).

• Batch size: As the reviewer hinted correctly, ParaDiGMS has a much higher needed batch size. Specifically, for a T step denoising process, ParaDiGMS needs to perform T model evaluations in parallel, while SRDS only requires $\sqrt{T}$ evaluations, which fits comfortably in GPU memory. To combat this using sliding windows, ParaDiGMS is able to arbitrarily increase the compute and create larger sliding windows (in exchange for reducing the number of serial iterations). It is worth noting that the comparison performed for the number of serial evaluations in the ParaDiGMS paper is on a system of 8 A100 80Gb GPUs whereas our experiments are performed on 4 A100 40Gb GPUs. To shed light on this difference in platforms, we also try to provide a more fair comparison in our experiments in the combined reviewer response, and we will add this clarification to the revised manuscript.

fixed-point iteration

Our rationale to include Proposition 1 in the manuscript, in a similar manner to Proposition 1 in [1] is to highlight the worst case behavior of the SRDS algorithm and provide the guarantee on convergence, despite the triviality. We will be sure to include the cross-references to the appropriate equations in [1] and [2], especially in the larger context of fixed-point iteration for n-order triangular systems.

different spirit in parallelization with [1][2] ... which one is better from the theoretical aspects

This is a great question! Indeed, SRDS has a different spirit of parallelization compared to [1] and [2]. We like to view it as a multigrid/multiresolution method where we solve for the trajectory at a low resolution and use parallel high-resolution solves to correct the trajectory. This is in contrast to [1] and [2] which have the flavor of more traditional fixed point iteration/updates. From a theoretical point of view, it is actually unclear which is fundamentally better. Even if SRDS might seem slightly superior empirically today, all three (SRDS [1] and [2]) are still the first works in this area of parallel sampling, and it is entirely possible that one of them possesses superior theoretical properties/guarantees that can be exploited. As we briefly discussed in the future work section of the paper, convergence guarantees/properties for parareal have been analyzed only in a handful of special cases such as heat equations, and it would be a very interesting future direction to see if the diffusion ODE admits better convergence guarantees for parareal (in line with what is observed empirically).

SDE sampler

Yes, as we mention in the paper, SRDS can indeed be readily applied to the SDE sampler. As seen in [1], we can just use the trick of pre-sampling the noise upfront, and the rest of the algorithm remains the same. Notably, it is even possible to ensure that the noise at the coarse and fine-time scales is aligned; however, this is not necessary due to the use of the predictor corrector updates in the parareal algorithm.

---

References:

• [1] Shih, Andy, et al. "Parallel sampling of diffusion models." Advances in Neural Information Processing Systems 36 (2023).
• [2] Tang, Zhiwei, et al. "Accelerating parallel sampling of diffusion models." Forty-first International Conference on Machine Learning. 2024.

We thank the reviewer for the review, and are happy to hear that the experimental results are convincing! We respond to the concerns below:

ParaDiGMs baseline

Please refer to the combined response to all reviewers, where we clearly demonstrate the superiority of SRDS over ParaDiGMS. For instance, SRDS is up to 38% faster than ParaDiGMS for DDIM on identical hardware even when using very generous convergence thresholds for ParaDiGMS.

Are the numbers intentionally matched in FID Score in Table 1 and CLIP Score in Table 2

Thanks for the question! Yes, the FID Score in Table 1 and CLIP Score in Table 2 are presented to show a tolerance/SRDS iterations so as to have no measurable degradation in sample quality. In the original version of the manuscript, we have included an ablation study for the number of SRDS iterations and the corresponding CLIP score in Figure 5; showcasing the capability of the model to achieve early convergence. For pixel space diffusion, we provide an ablation of tolerance threshold vs sample quality in Appendix C. We note that we use KID score instead of FID score due to computational budget constraints (KID is an unbiased estimator and requires much fewer samples than FID).

We thank the reviewer for the review, and appreciate that they recognize the practical applicability of our work! We respond to the concerns below:

ParaDiGMs baseline

Please refer to the combined response to all reviewers, where we clearly demonstrate the superiority of SRDS over ParaDiGMS. For instance, SRDS is up to 38% faster than ParaDiGMS for DDIM on identical hardware even when using very generous convergence thresholds for ParaDiGMS.

Comparison to existing solvers

We'd like to re-emphasize that SRDS provides an orthogonal improvement compared to the other lines of research on accelerating diffusion model sampling. In particular, while the main experiments (and writing) were focused on DDIM, SRDS is compatible with other solvers and they can be readily incorporated into SRDS to speed up diffusion sampling. We have empirically also evaluated that the SRDS method can be used with other solvers, such as DDPM (often requiring more steps than DDIM) and DPMSolver (often requiring fewer steps than DDIM). For both methods, SRDS maintains a speedup over the corresponding baseline serial implementation (~3.6x for 1000-step DDPM and ~1.5x for 25-step DPMSolver ). Please see the combined response for a greater discussion of this extension.

SRDS outperforms ParaDiGMs in terms of memory requirement

Apologies for the confusion. Yes, indeed ParaDiGMs has a higher memory requirement. Specifically, for a T step denoising process, ParaDiGMS needs to perform $T$ model evaluations in parallel with subsequent computations needing information about all previous evaluations, while SRDS only requires $\sqrt{T}$ parallel evaluations (which fits comfortably in GPU memory) and requires much lesser communication between GPUs. While the prohibitively large memory requirement can be combated with a sliding window method, the significantly larger communication overhead remains because at every step of Paradigms, an AllReduce over all devices must be performed in order to calculate updates to the sliding window. (For instance, even when ParaDiGMS reduces Eff. Serial Steps by 20x, the obtained speedup is only 3.4x). This is in contrast to the independent fine-solves in parareal that only need to transfer information for the coarse solve.

Below, we demonstrate how the minimal memory and communication overhead of SRDS shines through as we are able to achieve better device utilization as we increase the number of available GPUs. The following experiment was performed on 40GB A100s and used a generous 1e-2 threshold for ParaDiGMS.

In the table above, we can observe how SRDS has a significantly better time per sample than ParaDiGMS despite having a similar number of effective serial evaluations.

Pipelined SRDS

We compare SRDS and pipelined SRDS in the overall response to all reviewers. We hope this provides more context and strengthens the empirical evaluation!

Could the pipelined SRDS be easily deployed in practice?

Yes, the pipelined SRDS can be easily deployed in practice, though it does take minor adjustments to common diffusion modeling code in order to be efficiently implemented. For example, the StableDiffusion pipeline makes use of a scheduler that ahead-of-time sets the number of inference steps (as a class variable). Adjusting this parameter to be modified at runtime is required for pipelining. Additionally, a framework is required to coordinate computation and data transfers; our implementations make use of torch.multiprocessing and the queue organization to coordinate the launches of the different nodes.

While extracting close to optimal bonus speedup (2x) from pipelining might require considerable engineering effort, we implemented a suboptimal version of pipelined SRDS and already achieve substantial speedups compared to non-pipelined SRDS and more importantly baselines such as ParaDiGMS. Please refer to the combined response for quantitative results on the same.

Why the SRDS Iters shown in Table 1 are not integers?

In Table 1, for pixel-based diffusion, we used a very tight/conservative threshold on the convergence of the output in order to define early convergence. We then measure the average number of SRDS iterations required until convergence across 5000 samples, which ends up not necessarily being an integer. This contrasts from Table 2 (Stable Diffusion) which caps the number of iterations with no measurable degradation in sample quality. We will make this more clear in the revised manuscript text, as well as add an equivalent version of Table 1 that includes a capped number of iterations in order to obtain a fairer comparison to baselines (e.g. ParaDiGMS) and demonstrates much greater speedups without loss of sample quality. In fact, Figure 7 in Appendix C already provides support for the fact that even for pixel-based diffusion models, we can similarly limit the number of SRDS iterations to 1 or 2 without degradation in sample quality, while achieving much greater speedups than reported in Table 1.

Why the first and second rows of Figure 6 are almost the same?

The first and second rows of Figure 6 seek to highlight the early convergence of the SRDS algorithm to the output of sequential sampling. For a visualization of the ‘iterative refinement’ through rounds of parareal iterations, we direct the reviewer to Figure 1.

We thank the reviewer for the review and are glad to hear the reviewer’s agreement of the broad applicability of SRDS! We respond to the concerns below:

ParaDiGMs baseline

Please refer to the combined response to all reviewers, where we clearly demonstrate the superiority of SRDS over ParaDiGMS. For instance, SRDS is up to 38% faster than ParaDiGMS for DDIM on identical hardware even when using very generous convergence thresholds for ParaDiGMS. We hope that addition of these results, as well as the comparisons between different samplers, helps provide more context to the impact of SRDS in diffusion model sampling.

In the current SRDS pipeline, the intermediate results of the fine-grained solver are only used once. Do you have any thoughts on utilizing them in subsequent steps for better sample quality or faster convergence?

We appreciate the question about only using the intermediate results of the fine-grained solver once, as it highlights that there is a rich body of work in parallel-in-time integration methods that may also be applicable to parallelizing the sampling of diffusion models. In particular, the intermediate re-use idea appears similar to PITA [1]; however, the inversion required in the calculation of the projection matrix makes it more complicated and less amenable to the high-dimensional outputs common to diffusion models. There may be room for such methods in latent diffusion; though have not yet explored such an approach due to the complexity.

There may be more room for simpler ideas in diffusion sampling, as the approximation to the score function may be inaccurate and simple averaging in re-use may provide a better approximation of the true score. These have not been explored as the main goal of the paper was to ensure that parallelized sampling was finding the solution to the ODE defined by the network. This would certainly be an interesting future direction to explore theoretically and empirically as an extension to SRDS!

The meaning of the abbreviation "IVP" in line 1: of Algorithm.1 is unclear.

Thanks for pointing this out. We will update the manuscript to clarify that it refers to ‘Initial Value Problem’.

---

References:

• [1] C. Farhat and M. Chandesris, “Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications,” International Journal for Numerical Methods in Engineering, vol. 58, no. 9, 2003, doi: 10.1002/nme.860. [Online].

We thank the reviewer for the review, and appreciate that they find the paper well written and easy to follow! We respond to the remaining concerns below:

The authors argue on theoretical grounds that this approach can be combined with other approaches to reduce latency of diffusion models. This is fair, but they do not show any empirical results around it.

In order to empirically demonstrate that the SRDS method can be used in conjunction with other approaches to reduce the latency of diffusion model sampling, we have extended beyond the base DDIM solver primarily used in the paper. We tested SRDS both in conjunction with DDPM (which takes relatively more steps than DDIM) and DPMSolver (which can reduce the number of steps beyond DDIM). For both methods, SRDS maintains a speedup over the corresponding baseline serial implementation (~3.6x for 1000-step DDPM and ~2.9x for 200-step DPMSolver ). In this way, we show that SRDS for example could be combined with the improvement from DDPM → DDIM or DDIM → DPMSolver in order to orthogonally improve latencies. Please refer to the combined response to all reviewers for more details on the same.

The approach relies completely on leveraging parallel refinement and the actual number of model evaluations are much larger (often by a factor of 3x) which can limit the applicability in some cases.

Yes, indeed there is a tradeoff: as we note in the introduction section, SRDS provides speedups in sampling at the cost of potentially additional parallel compute. While this might limit applicability in some cases (such as compute-bound, batched inference workloads), we would like to emphasize that this tradeoff enables the diffusion models for many other use cases such as real-time image or music editing and trajectory planning in robotics. In fact, there is an increasing trend of diffusion models run locally where small enough models or strong enough hardware can support the batching described in this paper. In such scenarios, strict latency requirements may justify the tradeoff of additional compute vs wall-clock times. Moreover, in a number of cases, we have found that SRDS provides reasonable predictions within a single Parareal iteration; here, the total number of model evaluations is only slightly larger than the serial approach (increasing from $n$ to $n + 2\sqrt{n}$). Lastly, it is also worth noting that many users are often agnostic to inference time GPU compute costs as they are orders of magnitude lower than training compute costs anyway.

Yet one of their results (last on in Table 2) has speed up of 0.7x. Is this all due to GPU overhead?

No, while there is certainly some loss due to GPU overhead, the <1.0x speedup is primarily due to the lack of pipeline parallelism (meaning that coarse and fine solves are performed serially rather than in parallel). Note that the worst case sampling latency being no worse than sequential sampling only holds for the pipelined version. Without pipelining, in the worst case, the speed up is 0.5x, and the 0.7x speaks to the early termination/convergence of SRDS. Please refer to Figure 4 for an illustration that clarifies this.

Is is possible to present empirical results with pipeline parallelism? It seems like the authors expect 2x gains with it, but I assume it will require some computational overhead and based on the previous question, the degradation can be non-trivial.

Please refer to the combined response to all reviewers for a broad discussion. While achieving close to 2x bonus gains with pipeline parallelism requires considerable engineering effort, we implemented a somewhat suboptimal version of pipelined SRDS, and this already showcases significant speedups compared to both non-pipelined SRDS (~20% speedup) and more importantly baselines such as ParaDiGMS (up to 38% faster than ParaDiGMS for DDIM on identical hardware even when using very generous convergence thresholds for ParaDiGMS; even faster when using stricter thresholds). The less than optimal speedups stems from GPU and scheduling overhead.

While I understand the claim regarding this approach being orthogonal to other works reducing, showing some experiments around the same will make for a stronger paper.

We hope the discussion/experiments in the common response on readily incorporating other solvers such as DDPM and DPMSolver into SRDS helps make this a stronger paper and provides context to how SRDS can be used in conjunction with other improvements in diffusion modeling!