Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics

Thank you for the thorough review of our submission. We appreciate your feedback, though we believe the assessment overlooks the core contributions of our work. This is a theory paper, and we hope it can be assessed based on the theoretical questions it addresses, the insights it provides, and the theorems it proves. We respectfully ask you to reconsider your evaluation based on these criteria.

Below, we respond to your specific concerns.

Novelty

We’re glad you found the theoretical results novel. You expressed concern that the methods we used to obtain these results are too similar to existing approaches, which you feel significantly reduces the novelty of our work. We strongly disagree with this view.

Our goal is to find a posterior sampling method that is provably robust. In this context, simplicity is a strength. Demonstrating that a relatively simple method (annealed Langevin dynamics) satisfies strong theoretical guarantees makes the result more meaningful, not less. In fact, if we could prove that even vanilla Langevin dynamics is a robust posterior sampling algorithm, that would be an even better result! Except that such a statement is false, as we show in Appendix F, so we need to use annealing.

I fail to see a meaningful difference between the proposed work and [2].

We find this comment puzzling. Paper [2] doesn’t provide any robustness theorem, or any theoretical analysis of annealing, or guidance on choosing a schedule. We also want to clarify that our proposed algorithm is quite different from [2] in design and purpose.

Specifically, [2] uses the same observation $y$ at all times, and just anneals down the measurement variance $\sigma_t$. In contrast, our method simulates a measurement process by also adding variance to $y$, so that at stage $t$ the measurement $y_t$ being considered is drawn according to the annealed variance $\sigma_t$. Our version ensures that on average, the marginal distribution of the intermediate samples $x_t \sim p(x \mid y_t)$ matches the original marginal $p(x)$; this is a key property to be able to bound the error in each stage. We do not believe the algorithm in [2] could achieve our Theorem 1.1 for any annealing schedule.

What also sets our work apart is that we don’t just use annealed Langevin dynamics — we analyze why and when it works, and offer a principled annealing schedule based on this analysis. That goes beyond what previous works have offered, which typically rely on heuristics or hand-tuned parameters.

To sum up, the fact that annealed Langevin dynamics has had empirical success only strengthens the impact of our results. We

• identify failure modes of existing approaches,
• introduce an alternative annealing design that circumvents those issues, and
• provide formal theoretical guarantees.

However, the authors suggest that they are the first to propose this approach.

Where do we suggest this? We never intended to suggest that "annealed Langevin dynamics" is a new idea, it's a pretty natural one. We do believe that we are the first to prove a theorem about any version of annealed Langevin dynamics for posterior sampling. Furthermore, our version of annealing does not appear in prior work.

Novelty of Techniques

You acknowledged the novelty of our theoretical results, but we also want to highlight the novelty of our proof techniques. Our paper is the first to introduce the idea of “controlling the expectation of intermediate distributions” in posterior sampling (see Section 3 for a detailed discussion). We also provide a complete proof framework for formalizing this idea, as laid out in the appendix and in the proof organization paragraph on page 9.

Taken together, we are confident that our work is both theoretically significant and methodologically novel.

Related Literature

We really appreciate your suggestion on including more related papers. We were mostly focusing on papers that have theoretical guarantees, but we will cite and discuss more related works in the final version of the paper.

Experiments

Look, this is a theory paper and should be judged as such. We view the experimental section as "better than nothing": it demonstrates that the algorithm can be implemented and perform OK, but not much more. We don't discuss our experiments until the last page of our paper.

Plenty of theory papers at NeurIPS have no experiments at all; please judge our paper as if it didn't have them, rather than rejecting 55 pages of theory over 1 page of unconvincing experiments. Turning theoretical ideas into SOTA systems that beat all baselines is a substantial effort in itself and goes beyond the intended scope of this paper.

Formatting suggestions

We appreciate your formatting and clarity suggestions. We’ll boldface vectors/matrices and tighten Figure 5 in the final version of the paper.

We hope this clarifies the novelty and significance of our work. We’d be grateful if you could reconsider your evaluation in light of these points.

Thank you for your review. We address your comments and questions below:

$L^4$ bound requirement

Our requirement of $L^4$-accurate scores for posterior sampling is significantly weaker than the MGF bound required for log-concave sampling in general; [1] shows that score approximations that are $L^p$-accurate are insufficient for Langevin convergence for any $1 \le p < \infty$.

We admit that $L^4$-closeness is still a strong requirement -- we suspect that even $L^2$ accurate scores are sufficient for provable sampling using our algorithm, and hope to address this in future work.

On page 6 you use the estimator for the conditional score as $\widehat s_y(x) = \widehat s(x) + A^T (y - Ax)/\eta^2$. It is fairly known, that is approximation is quite rough. Why do not use other approximation, e.g. DPS? Does the proof only work for your approximation?

We are confused by this comment -- if $s(x)$ is known exactly, $s_y(x) = s(x) + A^T (y - Ax)/\eta^2$ is precisely the true conditional score. Thus, our approximation $\widehat s_y(x)$ is the natural one given only approximate scores $\widehat s(x)$.

In contrast, DPS attempts to replace the scores of the smoothed conditional distributions with a lossy approximation. We only work with the unsmoothed conditional distribution, which is the one that Langevin uses.

Is Theorem 1.2 limited to Gaussian noise or can it be extended to other noise types (e.g. Poisson, mixed Gaussian-Poisson)?

This is a great question -- our analysis certainly gives a natural starting point for analyzing other noise types, but doing so may require modifying the annealing schedule and is beyond the scope of this paper.

2-competitive with optimal in any metric

This means that if the best possible reconstruction algorithm achieves error $\varepsilon$ with probability $1-\delta$ in any metric, posterior sampling has error at most $2 \varepsilon$ with probability $1-2\delta$.

Why do you express Theorem 1.1 and Theorem 1.2 as existence results

Sure, we're happy to restate them more explicitly. The original phrasing follows a common convention in theory papers, where the focus is on the properties and guarantees rather than the specifics of the algorithm itself — to the extent that many such papers don’t even present the algorithm in full.

Looking at Section 3.3 (page 8) and Algorithm 1 it seems that you are not using the local log-concave condition

Algorithm $1$ is for Theorem 1.1, the global log-concave case -- Algorithm $3$ in Appendix $E.2$ handles the locally log-concave setting, and makes use of the initial estimate $x_0$.

Figure 3

In our experiments, we use the step size as a proxy for controlling the time spent running the algorithm. So, as we decrease step size, so that the time spent is decreased, we expect the sample obtained to be farther from the target conditional distribution, and closer to the starting sample $x_0$. Thus, we expect the sample to be farther from the ground truth, as we see.

[1] Convergence in kl and rényi divergence of the unadjusted langevin algorithm using estimated score. Kaylee Yingxi Yang and Andre Wibisono. NeurIPS 2022 Workshop on Score-Based Methods, 2022.

Thank you for taking the time to look over our previous response and for sending these follow-up questions. We address each point below.

Reference to Algorithm 3

Thank you for pointing this out. In the revised version, we will state Algorithms 2 and 3 more explicitly. Both are applications of Algorithm 1 to modified distributions that incorporate the auxiliary measurement $x_0$.

The key idea behind applying Algorithm 1 in the local log-concavity setting is simple: once we start from the auxiliary measurement $x_0$ in the local log-concave region, we can apply Algorithm 1 directly. With high probability, the trajectory stays within this region, which ensures the algorithm remains effective. This approach underlies each of the results, as summarized below:

* Standard arguments show that this leads to a competitive compressed sensing algorithm, as detailed in Corollary 1.3.

We will include explicit references and brief descriptions of Algorithm 2 and Algorithm 3 in the revised version to improve clarity.

Relationship between step size and time spent

Thanks also for raising this point. The “time” we refer to is the theoretical time variable in the continuous time Langevin dynamics rather than the computational time of the program. In our experiments, we simulate a Langevin process:

and discretize it using a fixed number of steps $M$ and step size $h$. This results in a total simulation time of $T = M \cdot h$. Since $M$ is fixed, decreasing $h$ directly reduces $T$, which means the sample has evolved less from its initialization. This is what we mean by “less time spent” — it reflects how far the sample has progressed in distribution, not the actual runtime of the program.

Thank you for your thorough review and positive evaluation. Below we address each of your comments point by point.

The general diffusion community has got rid of log concave assumption several years ago.

You're right that unconditional diffusion models can work with very flexible distributions, thanks to access to smoothed scores. Posterior sampling, however, is more difficult: you cannot quickly compute the smoothed score of the posterior from the smoothed scores of the prior. As shown in [1], once we lose access to smoothed scores and have to work with unsmoothed ones, no polynomial-time algorithm exists for sampling from a general non-log-concave posterior. That’s why in the literature on unsmoothed-score samplers, log-concavity remains a common assumption. In fact, the hardness example in [1] is itself a Gaussian mixture, so replacing the prior by a mixture of Gaussians would not avoid the same barrier.

It is possible that Algorithm 1 works only locally.

We agree, and that’s exactly what we formalize in Theorem 1.2: When the prior isn't globally log-concave, as long as it's log-concave in a local region around the target, our algorithm can still do posterior sampling — once it's localized to that region.

The line 7 in Algorithm 1 should really be $X_1 \sim \hat p (x \mid y)$.

Algorithm 1 is designed for priors that are globally log‑concave, so sampling $X_{1}$ from $p(x)$ is sufficient. For priors that are only locally log‑concave, Algorithm 2 in Appendix E.2 replace the global prior by its localized counterpart -- just as you suggest.

The approach proposed is sufficient but might not necessary. It is possible to generate good sample with very large score error, and the theoretical result of DPS might be improved without limiting score error.

You're absolutely right that DPS sometimes produces high-quality samples even with large score error, especially if it's implicitly maximizing the posterior. But in this work, our goal is sampling from the correct posterior — not just generating plausible outputs. Maximizing the posterior may give sharp samples, but they’re biased, even in simple settings like a mixture of two Gaussians.

I am wondering if Algorithm 1 will work without init from DPS, on real world images such as FFHQ.

The experiment in Section 4 falls under the locally log‑concave setting, where an initializer inside the correct region is required. DPS supplies such an initializer, but a simpler choice like the pseudoinverse $A^{\dagger} y$ is also possible, albeit with weaker performance. For a truly globally log‑concave prior, Algorithm 1 would not need any special initialization.

[1]: Diffusion Posterior Sampling is Computationally Intractable. Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun. ICML 2024

Thank you for your review. We respond to your comments and questions below:

The paper is only theoretical—there’s no actual algorithm or method that someone can implement.

This comment, as well as the related one in the limitations section, perplexes us -- we have implemented the algorithm and shown improvements over the existing DPS method; see the Experiments section for details.

It doesn’t cover more general situations, like non-log-concave priors or nonlinear measurements.

Our analysis does cover non-log-concave priors as long as they are locally log-concave as we describe on page 2 -- see Theorem 1.2 for the formal statement. For general non-log-concave priors, it is impossible to design a polynomial time posterior sampler, as [1] shows.

We thank you for asking about nonlinear measurements -- in general, unless the posterior density is log-concave, our analysis does not apply; for nonlinear measurements, log-concavity is not guaranteed. If this posterior is log-concave, our analysis gives a natural starting point for this setting, but a complete analysis is beyond the scope of this paper.

It doesn’t mention or cite recent work on how Langevin methods behave.

We have provided a comparison with existing works in the Langevin literature on page 5 -- to reiterate, when the score function is known exactly and the distribution is strongly log-concave, the Unadjusted Langevin Algorithm is known to converge rapidly [2]. If an approximation to the score is known satisfying a strong MGF condition, [3] showed that Langevin converges, but fails to converge if the score approximation is only $L^p$-accurate for any $1 \le p < \infty$. Our analysis shows that for posterior sampling, an annealed version of Langevin converges even if the score approximation is only $L^4$-accurate.

Is it possible to test or check in practice whether the $L^4$ error bound holds for learned score models?

This is a great question -- in practice we see that our method does improve upon DPS as noted above, which suggests that either the scores are being learned in $L^4$, or that our method continues to work even for $L^2$ accurate estimates.

Can the authors give a simple example where their result applies and shows the improvement clearly?

One simple example is the Poisson distribution -- since it is a log-concave distribution, our algorithm is guaranteed to converge. In contrast, DPS suffers error depending on the Jensen gap, which is non-zero for this distribution.

Note that standard Langevin fails to converge even for the Gaussian distribution, while our annealed version converges -- see Appendix F for a discussion.

[1] Diffusion Posterior Sampling is Computationally Intractable. Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun. ICML 2024

[2] Theoretical guarantees for approximate sampling from smooth and log-concave densities. Arnak S Dalalyan. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2017.

[3] Convergence in kl and rényi divergence of the unadjusted langevin algorithm using estimated score. Kaylee Yingxi Yang and Andre Wibisono. NeurIPS 2022 Workshop on Score-Based Methods, 2022.