PFDiff: Training-free Acceleration of Diffusion Models through the Gradient Guidance of Past and Future

We sincerely appreciate the reviewer's valuable suggestions.

W1: Previous gradient guided sampling and PFDiff's harm analysis.

A: Let's start with a possible misunderstanding. In PFDiff, previous gradients do not assist in guiding the sampling direction; rather, it is the future gradients that have a more significant guiding effect on the current state. Our primary motivation for replacing current gradients with past ones is their high similarity (see Fig. 2(a)), which reduces computational costs by skipping the current gradient computing. Regarding future gradients, we found that the optimal gradient guiding the current state exists at a future moment, not the current (Appendix B.2, lines 508-521, and response to reviewer sKuL W2). So using future gradients to approximate the optimal gradient offers better guidance for sampling the current state.

PFDiff does not harm image denoising. Since the denoising process involves solving discretized SDEs/ODEs, guiding current state sampling with the current gradient introduces unavoidable discretization errors, especially with fewer NFEs. PFDiff addresses this by using future gradients to approximate the optimal gradient, reducing discretization errors and accelerating sampling without harming quality.

W2: Many works investigate using previous gradients to improve sampling speed.

A: Using previous gradients alone (either entirely replacing or partially caching) to guide the current state's sampling is inefficient (see common response, Q3, Table C). The efficiency of the PFDiff comes from its information-efficient sampling update process, which involves the current state, past, and future gradients. PFDiff completes two updates with just one gradient computation (1 NFE), which is equivalent to achieving an update process of a second-order ODE solver with 2 NFE. so omitting either future or past gradients would significantly limit efficiency. PFDiff shows significant differences in improving sampling speed compared to many existing methods that utilize previous gradients.

Q1: Is there any memory overhead for saving the gradients?

A: The gradient saving of our PFDiff does not lead to memory overhead. This is because each update overwrites the previously saved gradients ( line 8 of Algorithm 1). Only one gradient needs to be stored at any given time, which is equivalent to the memory required to store one image.

Q2: More experiments on ImageNet 256, conditional and unconditional.

A: Yes, we added experiments on the ImageNet 256 as follows:

Unconditional, ImageNet 256, FID↓

Conditional (s=2.0), ImageNet 256, FID↓

As shown above, whether in conditional or unconditional experiments on the ImageNet 256 dataset, PFDiff consistently enhances the performance of DDIM. This further validates the effectiveness and wide applicability of PFDiff.

Q3: How about the comparison with DEIS sampler?

A: We added a comparison with the DEIS sampler on the CelebA 64x64 dataset, utilizing the default $t$AB3 version from the DEIS [1] codebase, and kept other experimental settings consistent with our PFDiff. The specific experimental results are as follows:

Unconditional, CelebA 64x64, FID↓

Like in the table, under conditions of fewer NFE, PFDiff outperforms DEIS. Particularly, at NFE=10, the PFDiff shows a faster convergence rate than DEIS. This further validates the efficiency and superiority of PFDiff under low NFE conditions. In the revised manuscript, we have incorporated the experimental results into Table 2 of the Appendix and Fig. 4(c).

Q4: Can the proposed method connect with distillation models?

A: It is non-trivial as PFDiff involves future gradients. However, theoretically, we can distill model information onto the temporal scales of PFDiff to achieve model distillation. E.g., using model distillation instead of learning optimal future gradients guided by hyperparameters $k$ and $l$ for updating PFDiff. This will be a focus of our future research.

Q5: More experimental metrics.

A: We added more experiments and compared them using recall, precision, and sFID metrics (ImageNet results added in Appendix D.7).

Unconditional, CIFAR10

As shown in the table, PFDiff consistently improved performance across all metrics, which shows the effectiveness of the PFDiff.

Thanks for the valuable comments, they help improve our paper.

W1: Flawed justification for future gradient.

A: Thanks for pointing out that the simplified description (lines 164-167) may have led to some misunderstanding. We now provided a more comprehensive explanation of the underlying logic (Approximation error analysis, please see W2 below).

• Firstly, the mean value theorem ensures the existence of an optimal point within an interval.
• Secondly, as analyzed in lines 508-515 and 519-521, the sampling trajectory of DPMs is not a simple linear relation (if it were a straight line, a larger sampling step size would not decrease the sampling quality), thus deducing that the optimal point would not be at the interval's endpoints. Therefore, sampling using the gradient at the current time point is not optimal.
• More importantly, we introduce hyperparameters $k$ and $l$ to approximate the optimal point through searching, as shown in Table 7. Even without precisely pinpointing the optimal point, adjusting these parameters has significantly improved the performance of PFDiff over the baseline. Therefore, our conclusion does not solely rely on theoretical derivation; both the mean value theorem and experimental results collectively support the viewpoint that using the gradient corresponding to future time points results in smaller discretization errors than using current gradients. We have made appropriate modifications to lines 164-167 and Appendix B.2 based on the above discussion.

W2: Approximation error analysis.

A: Great suggestion ! We have added the following error analysis into Appendix B.2:

Starting from Eq. (8):

$x_{t_i}=x_{t_{i-1}}+\int_{t_{i-1}}^{t_i} s(\epsilon_\theta(x_t,t),x_t,t) \mathrm{d}t.$

We define $s_{\theta }(x_{t}, t):=s(\epsilon_\theta(x_t,t),x_t,t)$, and further analyze the term that may cause errors, $\int_{t_{i-1}}^{t_i} s_{\theta }(x_{t}, t) \mathrm{d}t$. Applying Taylor's expansion at $t=r, r\in [t_{i-1},t_{i}]$, we derive:

$\int_{t_{i-1}}^{t_i} s_\theta\left(x_t, t\right) d t=\int_{t_{i-1}}^{t_i}\left[\sum_{n=0}^{\infty} \frac{s_\theta^{(n)}\left(x_{r}, r \right)}{n!}(t-r)^n+R_n(t)\right] dt \approx \frac{1}{(n+1)!} \sum_{n=0}^{\infty} s_\theta^{(n)}\left(x_{r}, r\right)\left[\left(t_i-r\right)^{n+1}-\left(t_{i-1}-r\right)^{n+1}\right].$

Furthermore, we analyze $r=t_{i-1}$ (i.e., the gradient corresponding to the current time point), and $r\in (t_{i-1},t_{i})$ (i.e., the gradient corresponding to the future time point). We compare the absolute values of the coefficients of the higher-order derivative terms corresponding to $r=t_{i-1}$ and $r\in (t_{i-1},t_{i})$, namely $|(t_i-t_{i-1})^n|$ and $| (t_{i}-r)^n -(t_{i-1}-r)^n |$, where $r \in (t_{i-1},t_{i})$, $n \ge 2$ and $| t_{i}-r |+ | t_{i-1}-r |= | t_i - t_{i-1} |$.

1. When $n$ is even, we can infer $\left | (t_{i}-r)^n -(t_{i-1}-r)^n \right |= |\ | t_{i}-r |^n - |t_{i-1}-r |^n |$. Furthermore, due to $| t_{i}-r | < | t_i - t_{i-1}|$ and $| t_{i-1}-r | < | t_i - t_{i-1} |$, we can infer that $|\ | t_{i}-r |^n - |t_{i-1}-r |^n | <\max(| t_i-r |^n, |t_{i-1}-r|^n)< | (t_i-t_{i-1})^n |$ holds.

2. When $n$ is odd, we can infer $|(t_{i}-r)^n -(t_{i-1}-r)^n|=| t_{i}-r | ^n + | t_{i-1}-r | ^n$, where $n\ge 3$. Let $a= | t_{i}-r |$, $b= | t_{i-1}-r |$ and $c=| t_i - t_{i-1}|$, we have $a,b,c>0$ and $c>a,b$. Next, using mathematical induction, we prove $a^n + b^n <c^n$, where $n\ge 3$ and $a+b=c$.

   • When $n=3$，$c^3 = (a+b)^3=a^3 + 3 a^2 b + 3 a b^2 + b^3 > a^3 + b^3$, hold.
   • When $n=k$ ($k\ge 3$, $k \in \mathbb{N}$), suppose $a\le b$, then $a^k + b^k < c^k$ hold. When $n=k+1$: $a^{k+1} +b^{k+1}=a\cdot a^k+b \cdot b^k\le b\cdot a^k+b \cdot b^k=b \cdot (a^k + b^k)<b \cdot c^k<c^{k+1}$. Overall, $a^n + b^n <c^n$ holds, thus $| t_{i}-r | ^n + | t_{i-1}-r | ^n < | t_i - t_{i-1} |^n$ holds.

In summary, we find $| (t_{i}-r)^n -(t_{i-1}-r)^n | < |(t_i-t_{i-1})^n|$, where $r\in (t_{i-1},t_{i})$. Firstly, this demonstrates that using the future time point $r$ gradient compared to the current time point $t_{i-1}$ gradient, the absolute values of the coefficients for higher-order derivative terms in the Taylor expansion are smaller. Secondly, as is well known, discretizing Eq. (8) neglects higher-order derivative terms, thereby introducing discretization errors. Finally, these suggest that neglecting higher-order terms has less impact when sampling with future gradients, further demonstrating that PFDiff's use of future gradient approximations in place of optimal gradients results in smaller sampling errors.

W3 and L1: Tuning hyperparameters k and l is both expensive and highly case-specific.

A: As in common response, Q1, searching for $k$ and $l$ does not necessitate extensive parameter tuning. Moreover, even without conducting a search and simply fixing $k=1$ and $l=1$, PFDiff still significantly enhances the baseline's sampling performance.

Q1: Two questions regarding the Mean Value Theorem.

A: Firstly, regarding lines 161-163, we cite from [1], which concludes that the sampling trajectories of DPMs' ODE solvers "almost" lie in a two-dimensional plane embedded in a high-dimensional space. This ensures the applicability of the mean value theorem in the context of ODE solutions for DPMs.

Secondly, we revised lines 163-164 and replaced "hold 'approximately' " with more explanation to avoid any misunderstandings. We intend to convey that: It is well known that the mean value theorem for real-valued functions does not hold in the case of vector-valued functions. However, given the previously mentioned conclusions, the unique geometric property where the sampling trajectories of DPMs' ODE solvers "almost" lie in a two-dimensional subspace ensures the applicability of the mean value theorem in the ODE solving process of DPMs.

[1] Zhenyu Zhou et al., Fast ode-based sampling for diffusion models in around 5 steps, CVPR 2024.

We sincerely appreciate the reviewer's valuable review of the manuscript and the recognition of our work of the work presented in the paper. Below are our responses to all questions. We kindly hope you could consider increasing the score if you are satisfied.

W1: The highly concise writing and complex notations might be a bit confusing.

A: Thanks to the reviewer for pointing this out this issue. As now clarified in the common response, Q2, and the one-page PDF attachment, we gave more explanation of the notations and, crucially, added flowcharts for the core iterative processes of the PFDiff algorithm. We hope this will help readers better understand our algorithm.

W2: There are fundamental mistakes in the writing.

A: We appreciate the reviewer for pointing out the potential misunderstanding. As now revised (originally in text in lines 117-119 ), “...The function $h$ represents the way in which different $p$-order ODE solvers handle the function $s$, and its specific form depends on the design of the solver. For example, in the DPM-Solver [21], an exponential integrator is used to transform $s$ into $h$ in order to eliminate linear terms. In the case of a first-order Euler-Maruyama solver [38], it serves as an identity mapping of $s$…”. We hope these modifications more accurately reflect our method and address your concerns about the potential misinterpretation.

W3: Experiments on EDM, the SOTA diffusion model on CIFAR-10 and ImageNet 64x64.

A: Based on the EDM pre-trained model, we conducted experiments on CIFAR10 and ImageNet 64x64 datasets, using PFDiff with and without DDIM, as shown in the tables below:

EDM, CIFAR10, FID$\downarrow$

EDM, ImageNet 64x64, FID$\downarrow$

As shown in the tables above, PFDiff continues to significantly improve the baseline performance of the EDM pre-trained model, further validating the effectiveness of our proposed PFDiff algorithm. We have incorporated the above experimental results into Table 4 of the revised version.

Q1: Are there any insights why PFDiff is more effective on first-order solvers (DDIM+PFDiff even outperforms high-order solvers)?

A: First order: The effectiveness mainly comes from the efficient utilization of information and a single iteration consists of two update processes. We have conducted a thorough analysis of the algorithmic update process of PFDiff. Initially, PFDiff utilizes past gradients to replace current gradients, updating to a future state; it then calculates future gradients based on this future state; finally, it employs these future gradients to replace the current gradients, completing an iterative update cycle. In this process, when using PFDiff+DDIM (a first-order ODE solver), the algorithm only requires one gradient computation (1 NFE) to complete two updates. This is equivalent to achieving an update process of a second-order ODE solver with 2 NFE. Therefore, under equivalent NFE conditions, PFDiff+DDIM even surpasses high-order ODE solvers. Furthermore, we have simulated the update process of PFDiff+DDIM in Fig. 2(b), discovering significant corrections to the trajectory of the first-order ODE solver by PFDiff, which substantially increases the sampling speed of the first-order ODE solver, even exceeding that of high-order ODE solvers.

However, as PFDiff introduces a small approximation bias when replacing gradients, a high-order ODE solver that calculates multiple gradients per iteration accumulates this bias. Therefore, the error accumulation when combining PFDiff with high-order ODE solvers can lead to instability under fewer NFE conditions, thereby impacting overall performance. This further illustrates that PFDiff is more suitable in conjunction with first-order ODE solvers, particularly under fewer NFE conditions.

We sincerely appreciate the reviewer's recognition of our work and valuable comments. Below are our responses to all questions. We kindly hope you could consider increasing the score if you are satisfied.

W1: The performance gap compared to training-based methods is still apparent.

A: Both training-based and training-free methods have their own application scenarios. While training-based acceleration algorithms can achieve one-step sampling, these methods often come with high training costs, especially when applied to large pre-trained models like Stable Diffusion. These substantial training costs of such methods significantly limit the broad applicability. In contrast, our proposed PFDiff algorithm achieves high-quality sampling under 10 NFE without any training requirement, making it a more attractive and practical solution.

W2: The mathematical notations are a bit hard to follow up.

A: We deeply appreciate the valuable comments from the reviewer. To more clearly demonstrate the specific execution process of the PFDiff algorithm in a single iteration, we have added a new schematic in the appendix (see one-page PDF attachment, Fig. 1). In the schematic, we explain the settings of the hyperparameters and the strategy for skipping timepoints. Additionally, for some of the more complex mathematical symbols, we have provided further explanations, for example:

• We have clarified the notation $x_{t_{i+1}} = \phi (Q, x_{t_{i}}, t_{i}, t_{i+1})$: This represents the update process from $t_{i}$ to $t_{i+1}$ for the current state $x_{t_{i}}$ using the ODE solver $\phi$, and leveraging the gradients $Q$ stored in buffer.

• Regarding Q \xleftarrow{\text{buffer}} \left ( \left \\{ \epsilon\_\theta(x \_{\hat{t}\ _{n}},\hat{t}\ _{n}) \right \\}\ _{n=0}^{p-1}, t\_{i+1}, t\_{i+2} \right ): This denotes the process of storing gradients calculated by a $p$-order ODE solver between the intervals $t\_{i+1}$ and $t\_{i+2}$ into the buffer as $Q$. The set of $p$ gradients, \left \\{ \epsilon\_\theta(x \_{\hat{t} \_{n}},\hat{t} \_{n}) \right \\} \_{n=0}^{p-1}, encompasses values calculated between the time points $\hat{t}\_{0} = t\_{i+1}$ and $\hat{t}\_{p} = t\_{i+2}$. Specifically, for a first-order ODE solver, this process simplifies to storing the gradient at the time point $t\_{i+1}$, $\epsilon\_\theta(x \_{t \_{i+1}},t\ _{i+1})$, into the buffer as $Q$.

We hope these modifications will help the reviewer and readers better understand our method.

W3: Regarding the issue of hyperparameter $k$, $l$ settings.

A: As now clarified in common response, Q1, our experimental results have shown some exciting outcomes; searching for $k$ and $l$ is not very time-consuming. Moreover, even without conducting a search and simply fixing $k=1$ and $l=1$, PFDiff still significantly enhances the baseline's sampling performance.

Q1: Does the faster sampling somehow come at the cost of reduced diversity?

A: Faster sampling does not reduce diversity. The FID is a comprehensive indicator of the diversity and quality of the algorithm, while Recall is a better measure of diversity [1]. We have supplemented our experiments on the CIFAR10 dataset with the Recall metric to analyze the impact of our method on diversity. As shown in the table below:

CIFAR10, Recall$\uparrow$ and FID$\downarrow$

As can be seen from the table above, compared to the original model with sufficient NFE, the diversity of PFDiff does not decrease, such as 59.85 (PFDiff) Recall$\uparrow$ with 10 NFE vs. 58.56 (DDIM) Recall with 1000 NFE. This demonstrates that the faster sampling of PFDiff does not come at the expense of reduced diversity.

[1] Kynkäänniemi T., et al. Improved precision and recall metric for assessing generative models, NeurIPS 2019.

We appreciate the reviewer's efforts and insightful comments on our work.

W1: The novelty question of PFDiff, and its distinctions from some prior important works, such as [R1] to [R5].

A: We have carefully checked all the five prior works mentioned by the reviewer, and we found they are significantly different from our work, which further proves the novelty of our PFDiff. Following we first highlight the uniqueness and efficiency of PFDiff, and then give a detailed analysis about the difference.

1. On the uniqueness and efficiency of PFDiff:

   • First, our novel future-gradient method is based on mean-value theorem, which is different from the Nesterov Acceleration [R5].
   • Second, NONE of the prior works explore and evaluate the importance of the combination of both past and future gradients for the sampling acceleration. By involving both past and future gradients, PFDiff completes two updates with just one gradient computation (1 NFE), which is equivalent to achieving an update process of a second-order ODE solver with 2 NFE. With our tailored update process that smoothly involves the current state, as well as past and future gradients, we achieve the new state-of-the-art performance for training-free acceleration. Ablation studies (in common response, Q3, Table C), also now added and demonstrated the effectiveness of each component.

2. Differences with [R1] to [R5]:

   • [R1] is a training-based accelerated sampling algorithm, which is fundamentally different from our TRAINING-FREE PFDiff. Additionally, [R1] constructs a new time-step sequence through training, which might implicitly utilize past information, but its motivation and implementation approach are significantly different from PFDiff.

   • [R2] does not "use all" (as in [R2] Section 3.1); its update process only depends on moments BEFORE the current state (no future gradients). Moreover, the specific update process in [R2] focuses on parallel sampling while ours focuses on reducing discretization error, which is also distinctly different.

   • [R3] is based on an SDE solver while our PFDiff is an ODE-based method. More importantly, [R3] optimizes sampling by estimating “first third-order” moments (training-based) of the reverse process while the PFDiff utilizes a totally different strategy as the acceleration is via the past and future gradients (TRAINING-FREE).

   • [R4] and [28] partially employ cached past gradients that are different from our past gradients, which will bring more time costs compared to direct replacement. Besides, they did not leverage future information. Our comparative experiments, detailed in the common response, Q3, Table C, show that incorporating future gradients with our PFDiff significantly improves sample quality and inference time compared to these methods.

   • [R5] theoretically demonstrated that Nesterov can speed up the sampling of Langevin dynamics. Though our future gradients share some similarities with Nesterov’s “foresight” update, our method has four significant differences: First. [R5] does not explicitly mention that their motivation comes from “future gradients”; it only implicitly includes them in their update process. Second, PFDiff's update procedure significantly differs from Nesterov’s approach as we employ a gradient replacement strategy instead of using momentum. Third, Based on the mean value theorem, we analyze that future gradients are more suitable for guiding the sampling of the current state, which is unrelated to the perspective of momentum in [R5]. Last, our experimental results (please see the common response, Q3, Table C) show that sampling guided solely by future gradients significantly differs in quality from PFDiff’s approach, which uses both past and future gradients for guidance.

Based on the above analysis, we cited all the papers and added comparisons with [R4] and [R5]. We can conclude that PFDiff significantly differs in methodology from [R1] to [R5], and the results further demonstrate the superiority of our method.

W2: Will PFDiff be parallelized for computation?

A: Potentially yes, future gradient makes this harder for PFDiff than other acceleration methods. But theoretically by using techniques like the Picard Iteration [R6], we can break the serial dependency of sampling and achieve parallelization; We will evaluate this in future work.

[R6] Shih A et al., Parallel sampling of diffusion models, NeurIPS 2023.

W3: Will 1 NFE of PFDiff take the same computation time as 1 NFE of other methods?

A: Yes, 1 NFE of PFDiff is precisely equivalent to 1 NFE of the other methods as the value of $\epsilon \_{\theta} (x\_{t_{i-(k-l+1)}}, t_{i-(k-l+1)})$ in Eq. (15) is directly retrieved from the buffer and does not require computation. Therefore, only 1 NFE computation is actually performed in Eq. (15). We added results regarding inference time, such as 1k samples, 15.79s (PFDiff) vs. 15.90s (DDIM) with 20 NFE, ( in common response, Q3, Table C) from which we can see that PFDiff does not introduce extra inference time.

W4: Regarding the question of confusion in notation and explanation.

A: Thanks for pointing out this. As now clarified in the common response, Q2, we have added more explanations of the notation and included a flowchart diagram of the PFDiff algorithm to demonstrate the update of one iteration in the PDF attachment.

[R1] M Xia et al., Towards More Accurate Diffusion Model Acceleration with A Timestep Tuner, CVPR 2024.

[R2] A Pokle et al., Deep Equilibrium Approaches to Diffusion Models, NeurIPS 2022.

[R3] H Guo et al., Gaussian Mixture Solvers for Diffusion Models, NeurIPS 2023.

[R4] F Wimbauer et al., Cache Me if You Can: Accelerating Diffusion Models through Block Caching, CVPR 2023.

[R5] R Li et al., Hessian-Free High-Resolution Nesterov Acceleration For Sampling, ICML 2022.