BELM: Bidirectional Explicit Linear Multi-step Sampler for Exact Inversion in Diffusion Models

Authors: fangyikang  wang
hubery  yin
yuejiang  dong
huminhao  zhu
chao  zhang
hanbin  zhao
hui  qian
chen  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 05:00:07

Abstract: The inversion of diffusion model sampling, which aims to find the corresponding initial noise of a sample, plays a critical role in various tasks.
Recently, several heuristic exact inversion samplers have been proposed to address the inexact inversion issue in a training-free manner. 
However, the theoretical properties of these heuristic samplers remain unknown and they often exhibit mediocre sampling quality.
In this paper, we introduce a generic formulation, \emph{Bidirectional Explicit Linear Multi-step} (BELM) samplers, of the exact inversion samplers, which includes all previously proposed heuristic exact inversion samplers as special cases.
The BELM formulation is derived from the variable-stepsize-variable-formula linear multi-step method via integrating a bidirectional explicit constraint. We highlight this bidirectional explicit constraint is the key of mathematically exact inversion.
We systematically investigate the Local Truncation Error (LTE) within the BELM framework and show that the existing heuristic designs of exact inversion samplers yield sub-optimal LTE.
Consequently, we propose the Optimal BELM (O-BELM) sampler through the LTE minimization approach.
We conduct additional analysis to substantiate the theoretical stability and global convergence property of the proposed optimal sampler.
Comprehensive experiments demonstrate our O-BELM sampler establishes the exact inversion property while achieving high-quality sampling.
Additional experiments in image editing and image interpolation highlight the extensive  potential of applying O-BELM in varying applications.

Main paper: 
 introduction: 
 The emerging diffusion models (DMs) [52, 20, 55, 56] , generating samples of data distribution from initial noise by learning a reverse diffusion process, have been proven to be an effective technique for modeling data distribution, especially in generating high-quality images [44, 10, 50, 46, 48, 21] . The diffusion process along with its sampling processes in DMs can be delineated as the forward and corresponding backward stochastic differential equations (SDE) [56, 1] . Furthermore, the sampling process can also be represented as a deterministic diffusion ordinary differential equation (ODE) [56, 53] , which is also called Probability Flow ODE (PF-ODE) in some papers. Notably, the backward SDE and diffusion ODE share the same marginal distribution [56] .The inversion of the diffusion sampling, which aims to elucidate the correspondences between samples and initial noise, plays a critical role in various tasks of DMs. The diffusion inversion has Figure 1 : Schematic description of DDIM (left) and BELM (right). DDIM uses x i and ε θ (x i , i) to calculate x i-1 based on a linear relation between x i , x i-1 and ε θ (x i , i) (represented by the blue line). However, DDIM inversion uses x i-1 and ε θ (x i-1 , i -1) to calculate x i based on a different linear relation represented by the red line. This mismatch leads to the inexact inversion of DDIM. In contrast, BELM seeks to establish a linear relation between x i-1 , x i , x i+1 and ε θ (x i , i) (represented by the green line). BELM and its inversion are derived from this unitary relation, which facilitates the exact inversion. Specifically, BELM uses the linear combination of x i , x i+1 and ε θ (x i , i) to calculate x i-1 , and the BELM inversion uses the linear combination of x i-1 , x i and ε θ (x i , i) to calculate x i+1 . The bidirectional explicit constraint means this linear relation does not include the derivatives at the bidirectional endpoint, that is, ε θ (x i-1 , i -1) and ε θ (x i+1 , i + 1).a variety of downstream applications, including image editing [18, 57] , image interpolation [53] , inpainting [7] , and super-resolution [67] . Several studies [31, 30, 7] have endeavored to tackle the inversion task within the context of SDE-based diffusion sampling. However, these works have not been able to achieve a mathematically exact inversion due to the inherent stochasticity of SDE.In contrast, the diffusion ODE naturally gives out a correspondence between samples and noise. The famous DDIM [53] and its inversion are formulated by considering a first-order explicit Euler discretization to the diffusion ODE. However, as noted in the work of [18] , the DDIM inversion introduces an inconsistency problem due to the schematic mismatch between DDIM and its inversion (see Figure 1 ). Encoding from x 0 to x T using DDIM inversion and then decoding using DDIM often leads to inexact reconstructions of the original samples (see Figure 4 ). To enable exact inversion, the work of null-text inversion [42] introduces intensive training for iterative optimization but still falls short of achieving a mathematically exact inversion.Recently, several heuristic exact inversion samplers have been proposed to address this inexact inversion issue in a training-free manner [63, 71] . These samplers enable the mathematically exact inversion without the need for additional training and are thus compatible with pre-trained models. Taking inspiration from affine coupling layers in normalizing flows [11, 12] , EDICT [63] intuitively introduces an auxiliary diffusion state and performs alternating mixture updates on the primal and auxiliary diffusion states. Later, BDIA [71] employs a symmetric bidirectional integration structure to achieve exact inversion intuitively. However, these heuristic exact inversion samplers often compromise the sampling quality due to their intuitive formula design. They may also introduce undesirable extra computational overhead or non-robust hyperparameters.In this paper, we develop a generic formula for the general exact inversion samplers, termed as Bidirectional Explicit Linear Multi-step (BELM) samplers. We demonstrate that all previously proposed heuristic exact inversion samplers are, in fact, special instances of BELM samplers. The concept of BELM originates from the observation of the mismatch between DDIM formula and its inversion formula. BELM is formulated by establishing an unifying relationship, from which both BELM and its inversion are derived. More specifically, the unifying relationship of BELM is constructed in a variable-stepsize-variable-formula (VSVF) linear multi-step manner, supplemented with an additional bidirectional explicit constraint to facilitate exact inversion.We systematically investigate the Local Truncation Error (LTE) within the BELM framework and show that the existing heuristic designs of exact inversion samplers yield sub-optimal LTE. Consequently, we employed a LTE minimization approach to design the formula of the optimal case within BELM, which we refer to as O-BELM. The formula for O-BELM dynamically adjusts in accordance with the timesteps, thereby ensuring minimized local error and consequently yielding the highest possible sampling accuracy. Furthermore, we demonstrate that O-BELM possesses the desirable property of zero-stability, which makes O-BELM robust to initial values. It also has the beneficial property of global convergence, which prevents O-BELM from diverging during sampling. To the best of our knowledge, O-BELM is the first theoretically guaranteed exact inversion diffusion sampler.We perform an image reconstruction experiment on the COCO dataset to validate that our O-BELM indeed achieves exact inversion, thereby enabling it to precisely recover complex image features. Furthermore, experiments involving both unconditional and conditional image generation demonstrate that O-BELM can ensure high sampling quality. Additional experiments in downstream tasks such as image editing and image interpolation highlight the extensive application potential of O-BELM. 
diffusion models and diffusion sdes: 
 Suppose that we have a d-dimensional random variable x(0) ∈ R d following an unknown target distribution q 0 (x 0 ). Diffusion Models (DMs) define a forward process {x(t)} t∈[0,T ] with T > 0 starting with x(0), such that the distribution of x(t) conditioned on x(0) satisfiesEQUATIONwhere α(•), σ(•) ∈ C([0, T ] , R + ) have bounded derivatives, and we denote them as α t and σ t for simplicity. The choice for α t and σ t is referred to as the noise schedule of a DM. According to [33, 29, 38] , with some assumption on α(•) and σ(•), the forward process can be modeled as a linear SDE which is also called Ornstein-Uhlenbeck process:EQUATIONwhereB t is the standard d-dimensional Brownian Motion (BM), f (t) = d log αt dt and g 2 (t) = dσ 2 t dt -2 d log αt dt σ 2 t .Under some regularity conditions, the above forward SDE (2) have a reverse SDE from time T to 0, which starts from x(t) [1] :EQUATION)where Bt is the reverse-time Brownian motion and q(x(t), t) is the single-time marginal distribution of the forward process. In practice, DMs [20, 56] use ε θ (x(t), t) to estimate -σ(t)∇ x(t) log q(x(t), t) and the parameter θ is optimized by the following objective:EQUATIONIt is noted that the reverse SDE (3) has an associated probability flow ODE (also called diffusion ODE), which is a deterministic process that shares the same single-time marginal distribution [56] :EQUATIONUpon substituting the f (t) and g(t) into Eq. ( 5), we obtain the following first-order form:EQUATIONThe famous DDIM sampler [53] can be obtained by applying the explicit Euler method to Eq. ( 6).EQUATIONThe inversion of DDIM is obtained by applying the explicit Euler method in the reverse of Eq. ( 6):EQUATIONIn practice, we observe an inconsistency issue with the DDIM inversion (8) . Consider a sample x 0 ; using DDIM inversion, we obtain the corresponding noise x T and then use DDIM to reconstruct a x * 0 . The reconstructed x * 0 would exhibit significant inconsistency with the original sample x 0 . Recently, two exact inversion samplers, EDICT and BDIA, have been heuristically proposed to address this inconsistency issue in a training-free manner.EDICT sampler Taking inspiration from affine coupling layers in normalizing flows [11, 12] , the recent work [63] proposed EDICT to enforce exact diffusion inversion. The basic idea lies in introducing an auxiliary diffusion state y t to be coupled with x t . Denoting a i = αi-1 αi and b i = σ i-1 -αi-1 αi σ i , the formulation of EDICT writes:EQUATIONwhere p ∈ (0, 1) is the mixing coefficient. The details of EDICT inversion defers to Appendix A.1.BDIA sampler BDIA sampler [71] utilizes a symmetric bidirectional integration structure to achieve exact inversion. BDIA reformulate the expression of DDIM (7) to bex DDIM i-1 = x DDIM i + ∆ i → i -1|x DDIM i and the expression of DDIM inversion (8) to be x DDIM i = x DDIM i-1 + ∆ i -1 → i|x DDIM i-1 . BDIA intuitively leverage -[(1 -γ)(x i+1 -x i ) + γ∆ (i → i + 1|x i )]to approximate the increment from x i+1 to x i and ∆ (i → i -1|x i ) as the increment from x i to x i-1 . Thus, the updating rule of BDIA writes:EQUATIONThe comprehensive formulation of BDIA and its inversion can be found in Appendix A.2.However, the theoretical properties of these heuristic samplers remain unknown and they often exhibit compromised sampling quality. To the best of our knowledge, there is no systematic approach to derive a diffusion sampler that simultaneously possesses the exact diffusion inversion property and maintains high sampling quality.3 The Generic Bidirectional Explicit Linear Multi-step (BELM) SamplersIn this section, we first model the diffusion sampling process as a well-posed initial value problem to facilitate subsequent analysis. By the rethinking of DDIM inversion, we propose the generic Bidirectional Explicit Linear Multi-step (BELM) samplers in a variable-stepsize-variable-formula (VSVF) manner. We further illustrate that EDICT and BDIA are, in fact, special instances of the BELM framework.The diffusion sampling problem as an IVP By denoting x(t) ≡ x(t) αt , σ(t) ≡ σt αt and εθ (x(t), σt ) ≡ ε θ (x(t), t), the deterministic sampling process of DMs (6) can be seen as an special reverse-time diffusion initial value problem (IVP) [58, p.310][3, p.3] :EQUATIONwhere x(T ) = x(T )/α T . A fundamental question before any further analysis is whether the given diffusion IVP (11) admits any solution and, if so, whether this solution is unique. Firstly, we need to establish some regularity assumptions on our diffusion sampling problem (6) . Assumption 1. ε θ (x,θ (x 1 , t) -ε θ (x 2 , t)∥ 2 ≤ L ε θ ∥x 1 -x 2 ∥ 2 .The Assumption 1 is a common assumption of the noise predictor ε θ (x, t) in the DMs literature [54] .Under the condition of Assumption 1, we can confirm the diffusion IVP ( 11) is well-posed by a direct application of the existence and uniqueness theorem in the IVP theory [3, p. 23] .Proposition 1. Under Assumption 1, there exists a unique solution to the diffusion IVP (11) .In this paper, x(•) denote the continuous solution, and x i denote numerical approximations.Rethinking on DDIM inversion As shown in Figure 1 , DDIM (7) and its inversion (8) are derived based on different linear relationships. We highlight that this mismatch results in the inexact inversion of DDIM. Building on this observation, a natural idea is to construct the DDIM inversion based on the same linear relationships as the DDIM to eliminate this mismatch. Regrettably, DDIM is constructed on a relationship between x i , x i-1 , and ε θ (x i , i) (utilizes x i , and ε θ (x i , i) to compute x i-1 ), which DDIM inversion cannot leverage to directly calculate x i , as ε θ (x i , i) is also unknown in the DDIM inversion case. This relation is explicit for DDIM but implicit for DDIM inversion. It should be noted that implicit equations must be solved using iterative methods such as Newton's method [58, p. 19] , which are time-consuming and can introduce numerical error in the context of DMs [23, 39] .To address this issue, we establish a new relationship between adjacent states and derivatives, which can be explicitly computed in both directions. Subsequently, we formulate both the sampler and its inversion based on this singular linear relationship to achieve exact inversion. This is the fundamental concept of BELM samplers.Bidirectional Explicit Linear Multi-step (BELM) samplers In an attempt to establish a linear relationship between x i , x i-1 , ε θ (x i , i), and ε θ (x i-1 , i -1) that can be explicitly computed bidirectionally, we must exclude both ε θ (x i , i) and ε θ (x i-1 , i -1). However, this exclusion results in a relationship that lacks sufficient information. Consequently, it becomes imperative to take more states into account. This prompts us to explore the concept of the linear multi-step (LM) method [3, p.111 ] as a means to derive a linear relationship between adjacent states and the derivatives of the diffusion IVP. However, the commonly used noise schedule of DMs would lead to a non-equidistant series of {σ i }, i = 1 . . . N . So, instead of the classical LM methods with fixed stepsize, we shall consider it in the variable-stepsize-variable-formula (VSVF) manner [8] , which use dynamic multistep formulae w.r.t. different stepsizes. Let t 0 < t 1 < . . . t N = t 0 + T be a grid in [t 0 , t 0 + T ], h i = σi -σi-1 , i = N . . . 1, h 0 = σ0 and h = max h i , the k-step VSVF LM methods w.r.t. Eq. ( 11) will calculate xi-1 at the points σi-1 with the following difference equation:EQUATIONwhere the coefficient of updates and stepsizes are all dependent on i. Throughout this paper, any reference to LM will, by default, imply VSVF LM unless explicitly stated otherwise. If b i,0 = 0 for all i in Eq. ( 12), the method is called explicit, since the formula can directly compute xi-1 . Clearly, the LM (12) have a reversed formula which is also a k-step LM as follows (assumeEQUATIONIf the reversed VSVFM is explicit, i.e. b i,k = 0 for all i, we call the origin LM (12) to be backward explicit. Now we can define a k-step LM to be bidirectional explicit when it is explicit as well as backward explicit. We call the LM samplers abide by the bidirectional explicit constraint as the Bidirectional Explicit Linear Multi-step (BELM) samplers, which have the general form:EQUATIONWe highlight this bidirectional explicit constraint is key to mathematically exact diffusion inversion:Proposition 2. Any BELM method (14) with a i,k ̸ = 0 has the exact inversion property. As an instance, setting k = 2 in Eq. ( 14) yields the 2-step BELM diffusion sampler:EQUATION)For detailed information on the 3-step BELM diffusion sampler, the general k-step case, and their optimal design, readers are referred to Appendix A.4 and A.5. In the main body of this paper, we will default mean 2-step case unless explicitly stated.BDIA and EDICT as special case of BELM We find that, although developed from heuristic ideas, both BDIA and EDICT are special cases within the BELM framework. That is, their exact inversion property is inherited from the fact that they are fundamentally instances of BELM samplers.Remark 1. EDICT (9) and BDIA (10) are both special cases within the BELM framework.The detailed mathematical derivation for Remark 1 can be found in Appendices A.7 and A.8. 
the optimal-belm (o-belm) sampler: 
 In this section, we systematically investigate the Local Truncation Error (LTE) within the BELM framework and show that the existing heuristic designs of exact inversion samplers yield sub-optimal LTE. Consequently, we introduce Optimal-BELM (O-BELM), which utilizes a more refined dynamic formula developed through the LTE minimization approach. Additional analysis is conducted to substantiate the theoretical stability and global convergence property of O-BELM.The Local Truncation Error (LTE) quantifies the error introduced in a step update. Specifically, it computes the difference between the numerical solution and its underlying true solution, assuming perfect knowledge of the true solution at the previous states.Definition 1. The LTE of BELM (15) on xi at each step i is defined as :EQUATION)Under Assumption 2 (details in Appendix A.3), we can utilize the Taylor expansion to investigate the LTE of BELM (15) as follows:Proposition 3. Under Assumption 2, the LTE of the BELM (15) gives general form as follows:EQUATION)where c i,1 = 1-a i,1 -a i,2 , c i,2 = -a i,1 h i -a i,2 (h i + h i+1 )-b i,1 h i , and c i,3 = - ai,1 2 h 2 i - ai,2 2 (h i + h i+1 ) 2 -b i,1 h 2 i .In the task of DMs, our primary concern is the LTE on x i-1 rather than xi-1 . We denote the LTE on x i as e i . It is clear that e i = α i-1 τ i . We investigate the LTE of existing samplers as follows:Corollary 1. Under Assumption 2, the LTE e i of DDIM sampler (7) is O α i-1 h i 2 ;TheLTE e i of BDIA sampler (10) is O α i-1 (h i + h i+1 ) 2 for any fixed γ ∈ [0, 1];The LTE e i of EDICT sampler (9) is O √ α i-1 h i for any constant p ∈ (0, 1).We then demonstrate that, through a meticulous design of formulae, we can achieve a higher order of LTE within the BELM framework compared to existing sub-optimal instances. Specifically, we utilize an LTE minimization approach, inspired by the design of renowned LM methods such as the Adams-Bashforth methods [2] or the Adams-Moulton methods [43, 40] .Proposition 4. Under Assumption 2, the LTE τ i of BELM diffusion sampler (15) can be accurate up to O (h i + h i+1 ) 3 when formulae are designed as a i,1 = h 2 i+1 -h 2 i h 2 i+1 ,a i,2 = h 2 i h 2 i+1 ,b i,1 = -hi+hi+1 hi+1 .When this is satisfied, obviously, the LTEe i on x i-1 is O α i-1 (h i + h i+1 ) 3 .Substituting the designed formulas into (15), we derive the Optimal-BELM (O-BELM) sampler:EQUATIONThe inversion of O-BELM diffusion sampler (18) writes:EQUATIONHere, we further demonstrate that the O-BELM not only surpasses in terms of local accuracy but also excels in stability and global convergence properties.As is clear from (15) , we need starting values before we can apply a method to the diffusion IVP. Of these, the initial one is given by the initial condition, but the others, have to be computed by other means, say, by using DDIM. At any rate, the starting values will contain numerical errors and it is crucial to ensure that perturbations of the initial values do not lead to an error explosion in the subsequent steps. This concept is encapsulated in numerical analysis as zero-stability.Definition 2. The LM ( 12) is said to be zero-stable if there exists a constant K such that, for any two sequences {x i } and {z i } that have been generated by the same formulae but different starting values xN , xN-1 , . . . , xN-k+1 and zN , zN-1 , . . . , zN-k+1 , respectively, we haveEQUATION)for all i, and as h tends to 0.We also want to ensure that a method will gradually converge to the underlying truth as the stepsizes decrease, a concept that aligns with the global convergence property.Definition 3. The LM (12) is globally convergent if for every solution x(t) of ( 11)EQUATIONwhen initial error We affirm that our O-BELM sampler possesses the nice zero-stable property as well as the global convergence property.N -1+k j=N (∥x j -x(t j )∥ + h i ∥ε θ (x j , σj ) -εθ (x(t j ), σj )∥) tends to zero.Proposition 5. The O-BELM sampler ( 18) is (a) zero-stable and (b) globally convergent. 
experiments: 
 In this section, we conduct experiments to verify that O-BELM achieves the exact inversion property while maintaining high-quality sampling ability. We further demonstrate the extensive potential of applying the O-BELM sampler in various applications, such as image editing and image interpolation (deferred to Appendix C.3). All the pre-trained models utilized are listed in Appendix C.5.We adopt the experimental setting from [63] to demonstrate the exact diffusion inversion property of O-BELM using 10k images in the MS-COCO-2014 validation set [35] . Given an image, inverted latents are calculated and used to reconstruct the image using SD-1.5. Mean-square error (MSE) is calculated on pixels normalized to [-1, 1] and averaged across 10k images. The autoencoder (AE) reconstruction error in the SD pipeline serves as a lower bound. From Table 2 , we observe that, regardless of the stepsize, O-BELM and its sub-optimal siblings BDIA and EDICT consistently achieve the lowest MSE, signifying their exact inversion at the latent level. In contrast, DDIM tends to suffer from inconsistency. More visual reconstruction examples can be found in Appendix C.1.In this section, we conduct an unconditional image generation task to validate the high-quality sampling ability of O-BELM. Utilizing a pre-trained model, we generate 50k artificial images over a specific number of steps and compute the corresponding Fréchet Inception Distance (FID) score with the real data. Specifically, Fréchet Inception Distance (FID) [19] calculates the Fréchet distance between the real data and the generated data. A lower FID implies more realistic generated data. Table 3 summarizes the computed FID scores for the CIFAR10 and CelebA-HQ datasets. It is evident that O-BELM consistently outperforms other exact inversion samplers in terms of sampling quality. This experimental result corroborates the error analysis presented in Table 1 . The parameters γ for BDIA and p for EDICT are determined through grid search. Details can be found in Appendix C.2.We further evaluate these samplers under conditional image generation tasks. We employ the StableDiffusion V1.5 and V2-base models to generate 30k images of resolution 512×512, based on text prompts from the COCO-14 validation set. All methods utilize the same seed and the same text prompts set. As evident from Table 4 , O-BELM also exhibits superior sampling quality in the context of conditional image generation. We ensure a fair comparison by selecting appropriate guidance weights and hyperparameters, details of which can be found in Appendix C.2. In this section, we present the results of the O-BELM sampler in an image editing task as shown in Figure 2 , and compare the editing effects of different samplers in Figure 3 . We demonstrate that the exact inversion property of O-BELM ensures the preservation of image features that we do not wish to edit. Furthermore, we illustrate how the high accuracy and stability properties of O-BELM contribute to the high quality of the edited image.We emphasis that the goal of experiments here is not going to use our O-BELM sampler alone to achieve commercial-grade level image editing. It's quite unfair for training-free exact sampler methods to compete with commercial-grade image editing pipelines involving domain-specific training [25, 68] , attention modification [18, 45] , testing-time finetuning [62, 24, 6] , complex control [73] , real-data inversion alignment [75] or input text refinement [47, 37, 32] . In fact, our O-BELM sampler is orthogonal to these image editing techniques, using a better exact inversion sampler like O-BELM in the commercial-grade image editing pipeline remains a promising future work.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The dataset utilized in this paper is publicly accessible on the internet. We have included codes, along with corresponding instructions, in the supplementary materials and intend to make them available on GitHub. However, our Stable Diffusion-related code is deeply intertwined with our proprietary business code, and we are currently working on decoupling the codebase. As soon as this process is complete, we will make them available on GitHub.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: We provide the details of our experiments in Appendix C. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusions: 
 We tackle the inexact inversion issue of DMs in a training-free manner. We introduce the generic Bidirectional Explicit Linear Multi-step (BELM) framework based on a linear multi-step observation, which encompasses existing heuristic exact inversion samplers as special cases. Furthermore, we devise a Local Truncation Error (LTE) minimization approach to construct the Optimal-BELM (O-BELM) within the BELM framework, which achieves a higher order of local error. We provide a theoretical guarantee of global stability and convergence for O-BELM and conduct various experiments to demonstrate that O-BELM not only accomplishes exact inversion but also maintains a high-quality sampling capability. Please refer to further discussion and limitations in appendix D.The code repository can be found at https://github.com/zituitui/BELM. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: This paper does not raise any issues related to statistical significance. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: We do provide sufficient information on the computer resources in Appendix D.3. 
 
 Appendix: A sequential inversion and rearrangement of EDICT (9) yields the EDICT inversion:EQUATIONA.2 Detail Formulation of BDIA BDIA sampler [71] utilizes bi-directional integration to achieve exact inversion, also introducing an additional hyperparameter. Reformulate the expression of DDIM (7) to beEQUATIONThe updating rule of BDIA write:x i-1 =x i+1 -[(1 -γ)(x i+1 -x i ) + γ∆ (i → i + 1|x i )] increment(xi+1→xi) + ∆ (i → i -1|x i ) increment(xi→xi-1),=x i+1 -(1 -γ)(x i+1 -x i ) -γ α i+1 α i -1 x i + σ i+1 - α i+1 α i σ i ε θ (x i , i) + α i-1 α i -1 x i + σ i-1 - α i-1 α i σ i ε θ (x i , i) =γx i+1 + α i-1 α i -γ α i+1 α i x i + σ i-1 - α i-1 α i σ i -γ σ i+1 - α i+1 α i σ i ε θ (x i , i).(24) By rearranging the BDIA (24) , the inversion of BDIA isEQUATIONContinuity Assumption Much of our Local Truncation Error (LTE) analysis such as Proposition 1 and 4, is built on the Taylor expansion, which requires that the noise predictor satisfies the necessary continuity conditions. Therefore, we establish the following continuity assumption:EQUATIONThis assumption can be met by selecting a differentiable activation design in the noise predictor U-Net [49] .Variable of IVP Here, we further wish to clarify that the notation εθ (x(t), σt ) ≡ ε θ (x(t), t) presented in Section 3 is well-defined. This is because there exists a bijective relationship between σt and t, and x(t) is simply a scaled version of x(t).In Assumption 1, we do not consider the singularity points at t = 0 and t = 1 because these points can lead to unusual performance of the noise predictor as discussed in [74] . In fact, our numerical method is minimally affected by these singularity points, thus making Assumption 1 reasonable.A.4 Detailed Formulation of 3-step BELM For 3-step BELM, we got five coefficients in the formulation:EQUATION)Follow the idea of Proposition 4, The local truncation error of the 3-step BELM diffusion sampler (27) τ i can be accurate up to the fifth order of step sizesτ i = O (h i + h i+1 + h i+2 )5 by setting coefficients as the following linear systemEQUATION) There is no linear dependence between any two equations in (28) . Through a calculation by hands or equation-solving tools like Matlab [27] , the linear system above yields the unique solution provided below, which can be verified by readers.EQUATIONA.5 Detailed Formulation of k-step BELMFor general k-step BELM, we got 2k -1 coefficients in the formulation:EQUATIONFollowing the derivation of 2-step case, we first applying the Taylor's expansion to xi-1+j and εθ (x i-1+j , σi-1+j ):EQUATIONThus, the optimal coefficient can be computed by:A (2k-1)×(2k-1)          a i,1. . .EQUATION)whereA = [A 1 | A 2 ],andEQUATIONEQUATIONConsistency The consistency property refers to the ability of the method to accurately represent the IVP equation it's trying to solve. More specifically, a method is said to be consistent if, as the step size approaches zero, the difference between the numerical method and the exact differential equation also approaches zero.EQUATIONA.7 BDIA as a Sub-Optimal Special Case of BELM the updating rule of BDIA write:x i-1 =γx i+1 + α i-1 α i -γ α i+1 α i x i + σ i-1 - α i-1 α i σ i -γ σ i+1 - α i+1 α i σ i ε θ (x i , i).(36) With the same alpha, scaled sigma and stepsize schedule as the BELM, the BDIA update (36) have an equivalent bidirectional explicit linear multi-step form with an easy rearrangement,EQUATIONwhereEQUATIONThus we find that BDIA is indeed a special case of our BELM framework.A.8 EDICT as a Sub-Optimal Special Case of BELMIn this section, we will demonstrate that a sequence of {x i }, {y i }, {y inter i }, and {x inter i }, where i ∈ [N . . . 1], generated by EDICT (9) , indeed corresponds to a sequence of z j , where j ∈ [4N . . . 1], produced by a special BELM. The EDICT updates as follows:                   x inter i = α i-1 α i x i + σ i-1 - α i-1 α i σ i ε θ (y i , i),EQUATIONtransferEQUATIONWe set alpha schedule to beEQUATIONThen we set sigma schedule to beEQUATIONThus the scaled sigma writesEQUATIONAnd the stepsize schedule will beEQUATIONWith easy substitution, the EDICT update (40) have an equivalent bidirectional explicit linear multi-step form:EQUATIONwhere the coefficients take the following piece-wise function form:EQUATIONDespite the formulation of ( 9) being subject to cyclic variations, the variable a j,2 consistently remains non-zero, thereby satisfying the conditions of the BELM framework. Consequently, EDICT can indeed be considered a special case within our BELM framework.In this section, we further explore the order of accuracy of DDIM, EDICT, BDIA, and our proposed O-BELM. Our findings indicate that O-BELM achieves the superior order of accuracy among these methods. Intuitively, the order of accuracy provides insight into which functional class of the IVP can be accurately approximated by a given method.Definition 5. The method ( 14) is said to have order of accuracy p if p is the largest positive integer such that there exist constants K and h * such that for all i,EQUATION)Proposition 6. The BELM diffusion sampler (15) is with second-order accuracy; The DDIM diffusion sampler (7) is with first-order accuracy; The EDICT diffusion sampler (9) is with zero-order accuracy; The BDIA diffusion sampler (10) is with first-order accuracy.Proof. This proposition can be directly inferred from the Definition 5, in conjunction with Proposition 1 and 4.Remark 2. Though the order of accuracy of BDIA is the same as DDIM to be 1, its step size in local error of BDIA is about twice that of DDIM. This theoretical result confirms the experimental observation that the sampling quality of BDIA sometimes is inferior to that of DDIM.We have also conducted an analysis of global stability and convergence for DDIM. It is apparent that the success of DDIM fundamentally stems from its nice theoretical property. Our O-BELM preserves these excellent theoretical properties of DDIM and maintains high-quality sampling performance.Proposition 7. The DDIM diffusion sampler ( 7) is (a) zero-stable and (b) globally convergent.To more effectively elucidate the implementation of O-BELM, we provide the pseudocode for O-BELM in Algorithm 1. Upon examination, it is apparent that the implementation of O-BELM requires little modifications compared to DDIM, thus facilitating its easy portability to pretrained models.Algorithm 1 O-BELM sampling process if i < N then 6:Calculate h i , a i,1 , a i,2 and b i,1 according to (53).7: Proof. We demonstrate the exact inversion property of BELM ( 14) by initially establishing that its local reconstruction error is zero. Assuming that we have already obtained {x i-1+j } k j=1 , we compute xi-1 in accordance with (14) , as follows:x i-1 = a i,1 x_list[-1] + a i,2 x_list[-2] + b i,1 h i ε θ (x_list[-1], i) 8: else 9: x i-1 = αi-1 αi x_list[-1] + σ i-1 -αi-1 αi σ i ε θ (x_list[-1], i).EQUATIONand we will use {x i-1+j } k-1 j=0 to reconstruct xi-1+k according to (13) , as follows:EQUATIONThe local reconstruction error, defined as the difference between xi-1+k and xi-1+k , can be calculated and is found to be zero. Furthermore, global exact inversion can be inferred from local exact inversion through the application of Mathematical Induction (MI).Proof. The Local Truncation Error (LTE) of the BELM diffusion sampler (15) can be computed by substituting x(t i ), x(t i+1 ), and εθ (x(t i ), σi ) in( 16) with their corresponding Taylor expansions at σi-1 as follows:EQUATIONProof. In the (17) of Proposition 3, we have three degrees of freedom: a i,1 , a i,2 , and b i,1 in the LTE of BELM (15) . Therefore, the highest order that τ i can achieve is three, under the condition that:EQUATIONwhose matrix form writesEQUATION)There is no linear dependence between any two equations in (51) . Through a straightforward calculation, the linear system above yields the unique solution provided below, which can be verified by readers. The LTE e i of DDIM sampler (7) isEQUATIONO α i-1 h i 2 .Proof. By applying the Taylor expansion and substitute into the DDIM formulation (7) , we can calculate the local error of DDIM on x i as following.e i =x(t i-1 ) - α i-1 α i x(t i ) -σ i-1 - α i-1 α i σ i εθ (x(t i ), σi ) =x(t i-1 ) - α i-1 α i α i x(t i-1 ) α i-1 + εθ (x(t i-1 ), σi-1 ) 1! (h i ) + O h i 2 -(-h i ) α i-1 (ε θ (x(t i-1 ), σi-1 ) + O (h i )) =O α i-1 h i 2 .(54)B.4.2 LTE of BDIA Proposition 9.The LTE e i of BDIA sampler (10) isO α i-1 (h i + h i+1 ) 2 for any fixed γ ∈ [0, 1].Proof. By applying the Taylor expansion and substitute into the BDIA formulation (10) , we can calculate the local error of BDIA on x i as following.EQUATION)For a fixed γ, the term εθ (x(t i-1 ), σi-1 ) cannot be eliminated for every i. This is due to the fact that the second-order term -γ 2 α i+1 h 2 i+1 + 3 2 α i-1 h 2 i is dynamic with respect to i. Consequently, the second-order local error will persist in the BDIA. To prove the Proposition 10, we need first establish an order estimate lemma:Lemma 1. The term √ α i - √ α i-1 have order O (h i )Proof. Recall that we define h i to be σi -σi-1 . In order to figure out the relation ofEQUATION)We then discover that d√ α = -1 2 σ2 + 1 -5 4 σdσ ∼ Cdσ. This implies that √ α i - √ α i-1 andσi -σi-1 are of the same order, which is h i .Proof. Since larger errors can absorb smaller ones, the 4l and 4l -2 terms in (46) introduce errors in the zeroth order of the Taylor expansion. This is where the main error occurs. Both of these updates introduce an error of√ αi- √ αi-1 √ αion xi , which means that the error onx i is √ α i √ α i - √ α i-1 .Therefore, according to Lemma 1, the error e i is of the order O √ α i h i .Remark 3. Please note that we have only established an error bound for EDICT based on the perspective of the linear multiplication method. There may be a tighter bound of EDICT on constants when viewed from the perspective of an interactive mixing system. which is non-increasing and strictly convex. Thus Assumption 3 can be achieved by choosing schedule of α i to be strictly convex w.r.t. i. Lemma 2. There exist a real constant C which is independent of α t and σ t , such that for every i, we have|a i,1 | ≤ C, |a i,2 | ≤ C and |b i,1 | ≤ C in (15).We will use an variable-stepsize-variable-formula analogy of the root condition of Dahlquist [9] to prove the zero-stability of (15). Theorem 1. [8, (3.10) ] Define the root matrix of a LM 12 at step i to be R i ,EQUATION)If all coefficients can be bounded and there exists a regular matrix H such that for all iEQUATIONthen the LM 12 is zero-stable.Finally, we start to give the proof of Proposition 5(a) under the Assumption 3.Proposition 11. The O-BELM diffusion sampler (18) is zero-stable.Proof. the root matrix of (15) writsEQUATION)The Assumption 3 can reach to σi+1 + σi-1 < 2σ i , thus h i+1 < h i < 0. Then we denote η = max ih 2 i h 2 i+1< 1, by setting H as followingEQUATION)then we can calculate thatEQUATIONwhere we can compute thatEQUATIONEQUATIONEQUATIONand obviouslyEQUATIONConsequently, we have the conclusion that for all i, the requirement ofH -1 R i H 1 ≤ 1 is satisfied.Thus due to Theorem 1, The BELM diffusion sampler ( 15) is zero-stable.Remark 4. Here, we present a very strong proof of Proposition 11 under Assumption 3, demonstrating that the iterative mapping of BELM constitutes a contraction mapping at each step i. However, it is important to note that in practical applications, even if Assumption 3 is not met at some step i, resulting in R i not being contractive sometimes, global stability may still be achieved.The proof for Proposition 7(a) writes:Proof. As DDIM can be seen as an explicit Euler method to the diffusion IVP, following the same reasoning of B.5, the root matrix of DDIM is R i = I. Obviously, DDIM is zero-stable.To analyse the global convergence property of a method, we first need to analyse the consistency property of a method. Please look up the definition of consistency in Appendix A.6. We first establish the consistency of DDIM and BELM by the following theorem.Theorem 2. [8, (2.5.1)] If a method have an order of accuracy 1 and all its coefficients is bounded by constant, then it is consistent.Lemma 3. The BELM diffusion sampler (15) is consistent.Proof. This lemma is a direct result of Lemma 2, Proposition 6 and Theorem 2.Lemma 4. The DDIM diffusion sampler (7) is consistent.Proof. In common choice of noise schedule, αi-1 αi and σ i-1 -αi-1 αi σ i is bounded. Thus this lemma is a direct result of Theorem 2.After we establish the consistency of DDIM and BELM, we can prove their global convergence by a famous sufficiency of conditions for convergence. In these image tasks, we only apply our 2-step O-BELM, as it has been demonstrated that higher-order numerical methods can lead to strong oscillations in stiff spaces such as images [58, p.343 ]. However, the application of higher-order O-BELM in other domains of Diffusion Models (DMs) continues to hold promise.For the sake of open accessibility, the dataset used in this paper is publicly available on the internet. We have included codes, accompanied by corresponding instructions, in the supplementary materials and plan to make them accessible on GitHub. However, our Stable Diffusion-related code is intricately interwoven with our proprietary business code, and we are in the process of decoupling the codebase. As soon as this task is completed, we will make the codes available on GitHub.Figure 4 presents the reconstruction results from several example images under 50 steps. It is evident that DDIM reconstructs images with non-negligible distortions compared to the original images, as marked by the red rectangle in Figure 4 . Our findings suggest that the exact inversion samplers (EDICT, BDIA, and O-BELM) indeed achieve exact inversion at the latent level, thereby achieving the lower bound of the reconstruction error of AE in latent diffusion models. Although the encoding and decoding processes of AE introduce some reconstruction error, these errors do not result in any detectable inconsistencies in the image as perceived by the human eye. It's also important to note that exact inversion requires the storage of two intermediates for precise reconstruction. This is feasible in downstream tasks such as image editing.We have also conducted an additional experiment to assess the reconstruction error in the latent space of O-BELM and other baseline methods as shown in Figure 5 . technique [22] which requires a guidance weight. For BDIA, we select a guidance weight of 4.0 and for EDICT, we choose 3.0, as recommended in their respective papers. For DDIM, we perform a grid search in the 20-step scenario, as shown in Table 8 , and determine the optimal guidance weight to be 5.5. This value is then fixed for other scenarios as well as for the O-BELM sampler. Examples of O-BELM We present unconditionally generated samples of O-BELM sampler in Figure 5 (a) (CIFAR10, 32×32) and Figure 5 (b) (CelebA-HQ, 256×256). Furthermore, we display text-guided generated samples in Figure 6 , utilizing the pretrained SD-1.5 model [48] (512×512) with captions from the COCO-14 dataset [35] . The guidance weight for our O-BELM has been set at 5.5 to align with the choice of DDIM.Image interpolation refers to the process of morphing between two images by interpolating between their corresponding latent vectors in the latent space, usually expecting to achieve a smooth transition between these images.The diffusion ODE (5) establishes a correspondence between latent noise and samples, which can also be perceived as a coding for the samples. Given that O-BELM can more effectively simulate the diffusion ODE while preserving the one-to-one relationship of the coding, we believe that the exact inversion of O-BELM can intrinsically provide a more rational correspondence. This, in turn, facilitates superior interpolation effects.We follow the experiment setting in [53] to generate interpolations on a line, which randomly sample two initial values x T from the standard Gaussian N (0, 1), interpolate them with spherical linear interpolation [51] , then use the BELM to obtain x 0 samples. The spherical linear interpolation x (α) T is calculated byEQUATIONT ,where θ = arccos The scheduler setting For these pre-trained diffusion models, we adopt the noise scheduler outlined in their respective configurations and apply it consistently across all our experiments. As our experiments do not involve the training or fine-tuning of diffusion models, there is no requirement to develop a new scheduler setting.Notice that, the intuitive exact inversion samplers achieve exact diffusion inversion at a cost of introducing an additional hyperparameter. comparing to DDIM, including both BDIA (10) (with additional hyperparameter γ) and EDICT (9) (with additional hyperparameter p). We point out that the need for additional hyperparameters would hinder the widespread application of the exact inversion samplers. The sampling quality of the previous exact inversion samplers is highly inrobust to the additional hyperparameter. EDICT recommend to choose p ∈ [0.9, 0.97] as EDICT would result in inconvergence when p ≤ 0.9.As depicted in Figure 10 , we observe that the use of different hyperparameters within the recommended interval could potentially result in divergence. In Table 6 and Table 7 , we note that the Frechet Inception Distance (FID) fluctuates significantly with respect to these unstable hyperparameters. Furthermore, the optimal hyperparameters vary across different datasets and steps.We would like to draw our readers' attention to the fact that the term Local Truncation Error (LTE) as used in this paper might differ from its usage in some other mathematical papers [58, p.317(12.24) ].Specifically, what is referred to as τ i /h i in this paper is often called LTE in other contexts, implying that their definition of LTE includes an additional division by a stepsize. However, in the context of variable-stepsize-variable-formula (VSVF), our definition proves to be more convenient and is more commonly adopted in papers dealing with VSVF [8, (2.1)].Time complexity Regarding the sampling task of diffusion models, the time cost bottleneck is the access to the noise network ε θ (x i , i). The number of accesses to ε θ (x i , i) is also referred to as NFE (the number of function evaluations). For the same value of N , we observed that O-BELM, DDIM, and BDIA all require an NFE equal to N for a single sampling chain. However, EDICT doubles this requirement to 2N .Experimentally, we've conducted additional tests to compare the average time cost of different methods across sampling, editing, and reconstruction tasks. The results show that O-BELM does not incur any additional computational overhead compared to DDIM across all these tasks. Detailed information about these experiments can be found in Table 9 .Memory complexity During the sampling process of diffusion models, typically the entire chain of the process is maintained. Both BDIA and O-BELM do not require additional memory beyond the previous sampling path. However, due to the auxiliary states, the memory requirements of EDICT need to be doubled.All experiments were conducted on a single V100 GPU and an Intel Xeon Platinum 8255C CPU. The sampling of 30k images using SD models under 100 steps took approximately 24 hours. The sampling of 50k images using a pre-trained CIFAR10 model under 100 steps took around 4 hours. Meanwhile, the sampling of 50k images using a pre-trained CelebA-HQ model under 100 steps required about 40 hours.We observe that the field of diffusion inversion is rapidly evolving. Recently, several works related to diffusion inversion have been proposed.For instance, the study by [26] suggests altering the prior distribution, as opposed to using Gaussian noise, for more convenient inversion. However, this approach requires training new models, rendering it incompatible with existing pretrained models. The research conducted by [72, 16] advocates for the training of a model-dependent bias corrector for precise inversion. Despite this, it fails to achieve mathematically exact inversion.The work of [39, 23] proposes the use of an implicit method in inversion to align with the sampling. However, this approach is time-consuming and residual optimization errors persist.And, the study by [34] suggests training a reverse one-step consistency model. However, its experimental performance also demonstrates reconstruction inconsistency.We understand that there are several techniques proposed to address the inexact inversion issue of DDIM within the context of classifier-free-text-guided image editing. These include NMG [5] , DirectingInv [28] , ProxEdit [17] , NPT [41] and NT [42] . We point out that the proposed O-BELM and these techniques should not be considered as comparative algorithms for following reasons.• These methods are orthogonal. O-BELM modifies the discretization formula to achieve exact inversion, while these techniques adjust the classifier-free-guidance mechanism. They address this problem from different directions. • They can be used together in the classifier-free-text-guided image editing. Take DirectingInv as an instance, its inversion is just DDIM inversion and its forward process encompasses two state-interacting DDIM forward processes with different prompts. We can substitute the DDIM inversion/forward in DirectingInv to be O-BELM inversion/forward and get O-BELM+DirectingInv. • Their working scenarios differ. The O-BELM is built on the general diffusion IVP, and can guarantee exact inversion and minimized error under all tasks based on diffusion ODE (PF-ODE). O-BELM can always converge to underlying IVP solution as demonstrated by Proposition 5. This means that the BELM framework is compatible with a wide variety of diffusion-based tasks, irrespective of the data type (images or words), the task type (editing or interpolation), the guidance method (unconditional, classifier-free, classifier-based, or adjoint ODE-based), or the network structure (whether it includes an attention layer or not). On the contrary, these techniques are developed specific for classifier-free-text-guided image editing task.The development of accurate and stable exact inversion diffusion sampling like O-BELM for DMs, as discussed in this paper, holds significant potential for several domains, including machine learning, healthcare, environmental modeling, and economics.However, while this research holds great potential for positive impacts, it is also important to consider potential negative societal impacts. The enhanced ability of an accurate and stable exact diffusion sampler could potentially be misused. For instance, it could be exploited to creating deepfakes, leading to misinformation. It may also raise privacy concerns, as more detailed and source data can be decoded from the intermediates using O-BELM. In healthcare, if not properly regulated, the use of synthetic patient data could lead to ethical issues. Therefore, it is crucial to ensure that the findings of this research are applied ethically and responsibly, with necessary safeguards in place to prevent misuse and protect privacy.This paper does not explore the integration of high-accuracy exact inversion samplers such as O-BELM with more powerful image editing pipelines. Additionally, the application of high-accuracy exact inversion samplers like O-BELM to tasks beyond image processing remains uninvestigated in this work. The concept of employing bidirectional explicit constraints to ensure exact inversion when applied to accelerated DM-solvers remains unexplored. There is also a lot of downstream tasks of DMs that a exact inversion samplers like O-BELM can apply [64, 61, 60, 4, 66, 13, 59, 70, 15, 14] .It will be also interesting to apply the exact inversion ODE sampler in variational inference [69, 65] or flow matching [36, 76] .• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 


Decision: The paper proposes BELM, a generic formulation of exact inversion samplers. This includes existing exact inversion samplers and the analysis of the LTE allows to optimize the method. The reviewers appreciated the novelty of the framework, the theoretical analysis of the LTE as well as the practical potential of BELM. The rebuttal clarified some concerns (difference with existing classifier-free-text-guided image editing works) and provided additional experiments which were appreciated by the reviewers.

All the reviewers recommend acceptance, and I concur with this evaluation.

Reviews: review: paper_summary: paper_summary: This manuscript introduces a generic formulation named ``Bidirectional Explicit Linear Multi-step'' (BELM) samplers for exact inversion of diffusion sampling. In contrast to DDIM Inversion, BELM inversion establishes the relationship between $x_{i-1}$, $x_i$, $x_{i+1}$, and $\epsilon_\theta(x_i, i)$. The authors prove that BELM is the generic version of EDICT and BDIA.
strength_weakness: strength_weakness: 1. How about the computation cost and latency of 2-step O-BELM compared with BDIA and EDICT?
2. Lack of more applications such as ControlNet-based Image Editing exemplars, and more failure cases is better for analyzing the limitation of BELM.
3. The local error of O-BELM seems higher than BDIA. Besides, for BDIA, $\gamma$ is tuned for different quality and effect, when $\gamma=1$, BDIA seems zero-stable and global convergence.
questions: questions: Please see the weakness part.
limitations: limitations: Yes.
paper_summary: paper_summary: The paper introduces the Bidirectional Explicit Linear Multi-step (BELM) sampler framework for exact inversion in diffusion models. The authors systematically investigate the Local Truncation Error (LTE) within the BELM framework and propose an optimal variant, O-BELM, which minimizes LTE for high sampling quality. Comprehensive experiments validate O-BELM's effectiveness in tasks like image reconstruction, editing, and interpolation.
strength_weakness: strength_weakness: 1.	As for downstream applications of diffusion inversion, style transfer [1] should also be included. I encourage the author could apply this method to some style transfer to show the robustness and effectiveness of this framework.
2.	Many punctuation marks at the end of the formulas are omitted by the authors. It is suggested to careful revise this article.
3.	The comparative analysis of qualitative and quantitative results is deficient. It is suggested that the authors provide detail comparative analysis and conclusion in experiment section.
questions: questions: See weakness.
limitations: limitations: This paper does not explore the integration of high-accuracy exact inversion samplers such as O-BELM with more powerful image editing pipelines. Additionally, the application of high-accuracy exact inversion samplers like O-BELM to tasks beyond image processing remains uninvestigated in this work.
paper_summary: paper_summary: This paper introduces a novel method for inverting real images into a diffusion model. It presents Bidirectional Explicit Linear Multi-step (BELM) samplers aimed at minimizing the mismatch in DDIM inversion.
strength_weakness: strength_weakness: 1. The paper lacks discussion and comparison with several related works such as NMG, EDICT, DirectingInv, ProEdit, ReNoise, and others. These works also aim to address the limitations of DDIM inversion through various proposed solutions. It is essential for the authors to provide a thorough discussion and comparative analysis with these existing methods.

2. The evaluation metrics used in the paper may not be sufficiently convincing. DirectingInv, for example, introduces several metrics specifically tailored for evaluating editing tasks, which are generally considered more reliable. Furthermore, DirectingInv also establishes a standard benchmark dataset for diffusion inversion tasks. It would be beneficial for the authors to conduct experiments using this benchmark dataset to ensure a comprehensive study and rigorous evaluation of their proposed method.

3. In terms of reconstruction performance compared to AE, EDICT, and BDIA, O-BELM does not demonstrate any improvement.
questions: questions: Please see in weakness
limitations: limitations: N/A
paper_summary: paper_summary: This paper introduces a systematic framework, referred to as BELM, that is designed for the specific task of exact inversion of diffusion sampling. This framework encompasses several existing intuitive exact inversion samplers as its special cases. Subsequently, the authors derive an optimal variant within this framework via local truncation error minimization, named O-BELM, and investigate its theoretical properties, including zero-stability and convergence. Experimental results demonstrate that O-BELM can achieve exact inversion and high-quality sampling. The authors further explore its potential applications in downstream computer vision tasks.
strength_weakness: strength_weakness: 1 There is a typographical error in the caption of Table 3. 
2 The information regarding the scheduler setting used in the experiments has not been included.
3 Some mathematical derivations in the paper are too succinct, making them difficult to follow. For instance, the transition from equation (30) to equation (31) is not straightforward as it involves a series of Taylor's expansions.
questions: questions: 1 This paper examines the zero-stable property of the O-BELM algorithm and baseline samplers. However, I've noticed that there are other stability properties, such as Absolute-stability or Butcher-stability, for ODE solvers. I'm interested in knowing how the samplers discussed in this paper fare in regards to these stability terms.
2 I'm curious to understand how adopting this new sampler might affect the marginal distribution of the diffusion models. Could you elaborate on the potential impacts this could have?
limitations: limitations: The authors have acknowledged the unexplored semi-linear structure as a limitation in the design of the BELM. 
Also, the effects of utilizing O-BELM in advanced image editing like P2P remain unexplored, which is a limitation of O-BELM as well.
Additionally, the impact of the paper is primarily confined to the sampling sub-area within the diffusion-based model community.

Comments: title: Dear Reviewer [eBdS], we are eager for your feedback
Concluding Response
Looking forward for further discussions.
Official Comment by Reviewer brf4
comment: Dear Reviewer [eBdS],

Since the discussion period will end in a few hours, we will be online waiting for your feedback on our rebuttal, which we believe has addressed your concerns. We would highly appreciate it if you could take into account our response when having discussions with AC and other reviewers.

Thank you so much for your time and efforts.  Sorry for our repetitive messages, but we're eager to your feedback.

Authors of Submission 2649
Dear Reviewers, AC, SAC, and PC,

We would like to begin by expressing our sincere gratitude for your engagement throughout the rebuttal process, which has significantly enhanced the quality of our paper.

In response to reviewers, we have revised the following contents in our manuscript:

- Typographical: The typographical errors in punctuation marks and captions have been corrected, as suggested by Reviewers [brf4] and [HZYw].

- Detailed Mathematical Derivation: A more comprehensive math derivation has been provided, as suggested by Reviewer [HZYw].

- Additional Experiments: In response to the advice of Reviewers [QGyL], [brf4], and [eBdS], we have incorporated further qualitative and quantitative comparative experiments in style-transfer, ControlNet-based image editing, and standard benchmark image editing to demonstrate the effectiveness of O-BELM.

- Clarification: We have incorporated comprehensive explanations for several elements, including time costs (Reviewer [QGyL]), BDIA performance (Reviewer [QGyL]), reconstruction error (Reviewer [eBdS]), and time scheduler (Reviewer [HZYw]).

We are immensely grateful for your feedback and suggestions for improving our manuscript. We kindly request your generous consideration of these points in the final evaluation of our paper.

Sincerely,

Authors of Submission 2649
Thanks for your valuable questions regarding our theory and for your generous appreciations to our work!
Thank you again for your times and efforts, your suggestions have been very helpful for us!
Thank you again for your patience and kindness, your suggestions on experiments have been very helpful!
After reading the careful response and other reviews, I will keep my score. Thank the authors for their response.
Dear Reviewer [eBdS],

Thank you again for your constructive feedback.

Our research is the first to construct a theoretical well-posed IVP modeling for the general inversion problem in diffusion sampling, as outlined in **Equation 11** and **Proposition 1**. Based on this IVP view, we have innovatively identified the Bidirectional Explicit condition, a sufficient prerequisite for achieving a mathematically precise inversion, as stated in **Proposition 2**. This condition does not merely reduce inversion error, but ensures exactness. Building on this condition, we have developed a generic formula for the general exact inversion samplers, which we have termed as Bidirectional Explicit Linear Multi-step (BELM) samplers, as detailed in **Equation 14**. These samplers incorporate several previous methods as special cases, as noted in **Remark 1**. We have conducted a thorough analysis of the Local Truncation Error (LTE) within the BELM framework, as described in **Proposition 3** and **Corollary 1**, and have proposed the optimal variants, O-BELM, as delineated in **Proposition 4**. We have also demonstrated that O-BELM possesses the advantageous property of zero-stability, as outlined in **Proposition 5**, which ensures its robustness to initial values. Additionally, O-BELM exhibits the beneficial characteristic of global convergence, also stated in **Proposition 5**, which prevents O-BELM from diverging during sampling. 

In regard to downstream tasks, we have taken your insightful advice into account and conducted experiments on the **standard image editing benchmark**, **PIE-Bench**. Additionally, during our interactions with Reviewer [QGyL] and Reviewer [brf4], we have conducted further experiments to provide support for the effectiveness and robustness of our methods. These additional tests include the **ControlNet-based editing task** and the **style transfer task**, further showcasing the effectiveness and robustness of our approach.


We sincerely hope to engage in further discussions with you. Thank you for your time and consideration!
Thank you for your rebuttal, my concern about experimental results has been well addressed. 

After reading the other comments and the corresponding rebuttal, I prefer to raise my score to accept.
Thank you for your detailed reply. It addresses most of my concerns.

I will keep my rating to weak accept.