Efficient Approximate Posterior Sampling with Annealed Langevin Monte Carlo
Authors: Advait Parulekar
Litu Rout
Karthikeyan Shanmugam
Sanjay Shakkottai
Venue: ICLR 2026 Poster (2026)
Keywords: Posterior Sampling
Sampling
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: Approximate Posterior Sampling is possible in polynomial time using annealed Langevin Monte Carlo.

Abstract: We study the problem of posterior sampling in the context of score based generative models. We have a trained score network for a prior $p(x)$, a measurement model $p(y|x)$, and are tasked with sampling from the posterior $p(x|y)$. Prior work has shown this to be intractable in KL (in the worst case) under well-accepted computational hardness assumptions. Despite this, popular algorithms for tasks such as image super-resolution, stylization, and reconstruction enjoy empirical success. Rather than establishing distributional assumptions or restricted settings under which exact posterior sampling is tractable, we view this as a more general "tilting" problem of biasing a distribution towards a measurement. Under minimal assumptions, we show that one can tractably sample from a distribution that is simultaneously close to the posterior of a noised prior in KL divergence and the true posterior in Fisher divergence. Intuitively, this combination ensures that the resulting sample is consistent with both the measurement and the prior. To the best of our knowledge these are the first formal results for (approximate) posterior sampling in polynomial time.

Published as a conference paper at ICLR 2026
EFFICIENT APPROXIMATE POSTERIOR SAMPLING WITH ANNEALED LANGEVIN MONTE CARLO
Advait Parulekar"
Litu Rout
Karthikeyan Shanmugam Google DeepMind
University of Texas at Austin
University of Texas at Austin
Sanjay Shakkottai
University of Texas Austin
ABSTRACT
We study the problem of posterior sampling in the context of score based gener- ative models. We have trained score network for prior p(z). measurement model p(y|ar), and are tasked with sampling from the posterior p(z yy. Prior work has shown this to be intractable in KL (in the worst case) under well-accepted computational hardness assumptions. Despite this, popular algorithms for tasks such as image super-resolution, stylization, and reconstruction enjoy empirical success, Rather than establishing distributional assumptions restricted settings under which exact posterior sampling is tractable, we view this as a more general "tilting" problem of biasing distribution towards measurement. Under minimal assumptions, we show that one can tractably sample from a distribution that is simultaneously close the posterior of noised prior in KL divergence and the true posterior in Fisher divergence. Intuitively, this combination ensures that the resulting sample is consistent with both the measurement and the prior. To the best of our knowledge these are the first formal results for (approximate) posterior sampling in polynomial time.
INTRODUCTION
Score-based generative models (Song & Ermon, 2020) including DALL-E (Ramesh et al., 2021), I), Stable Diffusion (Rombach et al., 2022), Imagen (Saharia et al., 2022), and Flux (Black Forest Labs, 2024), provide a powerful framework for sampling from complex data distributions. Given access to samples from a target distribution, these models learn family of smoothed score functions, i.e., vector fields that estimate the gradient of the log-density of the data corrupted with varying levels of noise. Intuitively, these score functions amount of noise to an image with less noise. Once such a family of score functions is learned, it can be used to iteratively denoise an image starting from pure noise and generate a sample from the data distribution.
be used to map an image corrupted with certain
The success of score-basee based generative models in capturing complex prior distributions has led to their widespread adoption in downstream tasks such as inpainting (Lugmayr et al., 2022). super- resolution (Kawar et al., 2022; Chung al., 2022; Song et al., 2023; Rout et al., 2023; 2024), MRI reconstruction (Song et al., 2022b), and stylization (Hertz et al., 2024; Rout et al., 2025b:a). In these tasks, we begin with a prior p specified to us through a large number of samples. We also have likelihood reward model denoted by R, that indicates preference at inference time, which is typically parameterized by a measurement y. The tasks is to obtain a sample from p that is consistent with Ry-
In many practical scenarios, such as those mentioned above, the measurement model is given by y A(x) + 17, where A is known measurement operator and n is noise. We seek sample from the prior such that RS A(x). This is often implemented by using R, = ||A(z)) y||² as a potential function and considering KL penalty. Formally, this is equivalent sampling from the
advai ww@.tttpt.tseeeememmee

---

Published as a conference paper at ICLR 2026
tilted distribution Muu which is defined as follows:
Po arg min R, (X)) + KL(vllp) = Ho x pe By
(Posterior Sampling)
This paper explores the extent to which score networks trained to model the prior p can be used for sampling the tilted distribution. We refer to this type of tilting Posterior Sampling. Indeed, if p is the prior, and e R₂ is a likelihood, then pe RR/ is the posterior given the measurement y. This setting differs from traditional conditional generation, where conditioning variables (e.g., measurements) are fed as input to the score network. In contrast, our focus is on a training-free setup: given a measurement y at inference time, we aim sample from p(xlyy) using only a score network trained on the unconditional prior p(z). While such networks are known to enable efficient sampling from p(z) (Chen et al., 2023), our goal in this paper is to understand their role in sampling from p(zly).
There has been growing interest in establishing provable guarantees for posterior sampling. In general, we cannot directly use the score based generative models, because we cannot efficiently compute the posterior smoothed scores from the prior smoothed scores. While empirically successful methods often perform well in practice and implicitly aim to solve the posterior sampling problem, provable polynomial-time guarantees remain elusive. In fact, many of the efficient algorithms proposed (Chung et al., 2022; Rout et al., 2023) can be proven to be biased. A formal counterpoint presented in Gupta et al. (2024), which showed that one could set up a posterior sampling problem to invert a (hypothesized) cryptographic oee function, establishing cryptographic hardness. Intuitively, this hardness stems from the fact that posterior sampling is a composite sampling problem that encourages consistency with both prior distribution as well as the measurement likelihood, which is difficult when the regions of highest likelihood have a small probability under the prior.
In light of this, recent work has focused on identifying sufficient conditions under which provable or asymptotically correct posterior sampling is possible, while avoiding such lower bounds (Bruna & Han, 2024; Xu & Chi, 2024). Instead, we take the view that exact posterior sampling might be a more difficult goal than we really need to achieve. In what sense can we tractably bias a sample from a prior towards likelihood?
Contributions. We introduce notion of posterior sampling that is possible in polynomial time, bypassing the hardness of sampling in KL. We develop guarantees with our method Annealed Langevin Monie Carlo (ALMC, Algorithm 1) in the general regime where the influences of the prior and the likelihood might be in conflict. We start with a sample that disregards the prior entirely - emphasizing only consistency with the likelihood. This sample is then annealed towards the true posterior by drawing its marginal closer to the posteriors of progressively denoised priors. Other than at polynomially low noise levels, we show that using ALMC we can efficiently transition from the posterior of a noised prior to a posterior of a slightly less noised prior. This efficiency is captured by bounds on how quickly these posteriors can change as vary the level of noising the priors (Lemmas B.2, C.6), as well as regularity conditions on the posteriors themselves, being as they were posteriors on priors that are regularized by annealing (Lemmas C.5, C.7). This brings us to the two main contributions of our work,
a. We show that an early-stopper Annealed Langevin Monte Carlo (ALMC) algorithm can track the posterior of a slightly noised prior in polynomial time in KL, and thus sample from a distribution close to the posterior for a noisy prior.
b. Although tracking the above path in KL beyond this point is generally intractable, we show that this early stopped distribution also has a low Fisher Divergence relative to the true posterior.
Our results require minimal assumptions (Assumptions 4.1) - that the prior should have Lipschitz score, be sub-Giau -ab-Gaass,nn, and that the measurement operator R, should be smooth and convex. Our motivation for this pair of results stems from the phenomenon of "mode collapse", shown in the context of "unannealed" Langevin Monte Carlo for convergence in Fl (Balasubramanian et al., 2022). Indeed, we show in Sections 2.1 and 4.1 1 that for a multimodal distribution (for example, mixture of Gaussians), Fisher Divergence alone suffices only to guarantee a type of local convergence, and cannot generally provide any guarantees on the corresponding mode weights (e.g., mixture weights). Our early stopped KL guarantee for the posterior of noised prior provides a notion of global correctness in density. Specifically, in the mixture-of- Giuussan setting, show that can
2

---

Published as a conference paper at ICLR 2026
explicitly avoid mode collapse (Section 4.1). Taken together, these results provide response the intractability of posterior sampling in KL.
Notation: We use po to denote a prior, Ry (or R.) to denote likelihood, and μi x poe ft to denote posterior. We use y to refer to a standard Gaussian. For time t, Pt denotes the Gaussian smoothed prior (or noised prior) with density pe(x:) e¹x pa **+***+; % where d is the ambient dimension (x: E IR.),, and * is the convolution operator. Similarly, we define (Ho){(2) = (o('x)) * (the noised true posterior) and Pr & p,e -It (the posterior of the noised prior). We have KL(a)]18) E, [log 9/8], TV(a, B) sup (a(A) B(A)) where the supremum is over all measurable sets A.
1.1 RELATED WORKS
Sampling: We refer the reader to Chewi (2023) for an exposition of works on sampling. There are strong connections between sampling and optimization, explored in various places including Wibisono (2018). Approximately, we can think of Langevin Monte Carlo (LMC) for sampling as corresponding Gradient Descent for optimization, and log-concave distribution correspond to convex functions. More recently, denoising diffusion models (Ho et al., 2020; Song et al., 2022a; Song & Ermon, 2020; Song et al., 2021) begin with noisy image and iteratively denoise to get sample. This is efficient, but requires a trained score network. Finally, the idea of running LMC towards changing target distribution is related works on annealing and tempering (Marinari & Parisi, 1992: Hajek & Sasaki, 1989). One can think of DDPM (Ho et al., 2020) as doing this using "heat" in different way by Gaussian convolution of the measures (adding heat to the particles).
This is a very active area of research, with a number of different approaches. Some methods try to estimate the posterior score Poogpi (r (z) directly (Chung et al., 2022; Rout et al., 2024; Song et al.. 2022b); we refer the reader to Daras et al. (2024) for more extensive treatment. The barrier for provable results with these methods is that getting the scores for the noisy posteriors exactly can be computationally intractable. Others use sequence of operations alternatingly aligning the iterate with the measurement and prior CCordero-Encinal et al., 2025; Xu Chi, 2024; Wu et al., 2024; Rout et al., 2025b). These are variants of "Split-Gibbs" sampling, which has a biased stationary distribution to which there are generally asymptotic convergence results, but no finite time, or even unbiased, guarantees. An exception is Wu et al. (2024), which gets "average" Fisher Divergence guarantee. There are also particle filtering methods (Chung et al., 2022; Dou & Song, 2024), which use Sequential Monte Carlo to estimate the posterior using a set of particles. Here the guarantees are in the limit as the number of particles grows to infinity. Indeed, formal guarantees appeared to be elusive, and result of Gupta et al. (2024) showed that posterior sampling is intractible in the worse case under the existence of a one way function. More recently Bruna & Han (2024) showed that posterior sampling can also be reduced to sampling from an ill-conditioned ising model, which is known to be impossible unless NP = RP.
Posterior Sampling:
Fisher Divergence bounds: In the classical (that is, without a trained score network) sampling literature, recently Balasubramanian et al. (2022); Wibisono (2025) proposed using Fisher Divergence to capture the phenomenon of metastability, which can be thought of as a type of approximate first. order convergence.
2 BACKGROUND
Gradient Flows: Consider a Markov process X, described by the SDE below. Let Pt denote the law of Xx, and let B, denote Wiener process. The measure Pt can be thought of as evolving according to vector field v, This flow can be expressed using the Fokker-Planck equation as shown to the right below.
= =x
(X()) dt V2dB + d:p:= (prv:) + Apt
(Fokker-Planck)
An absolutely continuous path +> Pt is generated by is if the Fokker-Planck equation satisfied. Also, for any absolutely continuous path, there is canonical "minimal" velocity field that generates it. We refer the reader to Ambrosio & Savaré (2007) for a detailed exposition.
Langevin Dynamies: Langevin Dynamies refers to the SDE
dx,- = V (log dt + v2dB + Oept = V (pe V log
Pt. π
(Langevin)
3

---

Published as a conference paper at ICLR 2026
It was noted in Jordan et al. (1998) that the law of the process is gradient flow for the KL diver- gence functional <L(-IIT) in the space of probability measures endowed with a Wasserstein metric. Convergence of Pt to is characterized by a Sog-lobolev inequality (LSI). Let Fl denote the Fisher divergence (defined below), then the LSI states
FI(p]T m) = B, V log L
pp (L(pITT) S
FI(]TTT)
(a -LSI)
While log-Sobolev inequalities are usually difficult to establish tightly, one can show that a measure whose negative log-density is az -tt-ooooyly convex satísfies aG-LSS (Bakry et al., 2014). If a measure satisfies log-Sobolev inequality, one show that Langevin Dynamics enjoys linear convergence in KL (Vempala& & Wibisono, 2022), specifically that
KL(pelI=) S <e-2ox" (L((l|
However, even for "simple" distributions like a mixture of two well-separated Gaussians, the LSI could have a very bad constant (in this case, exponentially small in the separation; see for instance Remark 3 in Chen et al. (2021)). This often prohibits the use of Langevin Monte Carlo.
Reversing the Flow: Modern score based generative models sample from prior distribution by training a neural network to learn the flow that would reverse the forward Gaussian Langevin flow. Langevin Dynamics for Gaussian is also called the Omnstein-Uhlenbee (OU) process
dX. = Xxdl + V2dB. = 3ep. V (p:(V log Pt + x))
(OU)
Sampling Xo To and running the above SDE for time l results in X, Mh. We note that me can explicitly be written as: Tz(x)= edd (o(''r) yy. From classical literature on reversing SDEs (Anderson, 1982), we know the following:
dX, -X,d + V2dB.
dxxt (Xt 2V log (x, di + V2dB.
(I)
forward process
roverse process
One can begin at Xx_ Ty and run the reverse process get X;- TT-1 until X; To- In fact, the random variables X, and Xi-, have the same law. The key to being able to implement this process is the use of the score V log Te. Due Tweedie's lemma (Robbins, 1956):
VI e- V log Te (2) = e x, E zole 'x + 1 Xt
7~7 (Tweedie)
These can be learned using simple variational characterization of least squares regression. Consider a family of models sa (0 t) parameterized by 8. We find
l" arg min Ex, ||= so(x oen. f)l2
From here, we can estimate the score V log as V log (x) ~ (2,1))))_
of
Annealed Langevin: Rather than using the reverse process specified above, one could use an "annealed" Langevin Dynamics. Unlike traditional Langevin where the drift of the SDE given by the score of a single density, here the density evolves over time follows:
dX, = V log Te (X,) + V2dB.
(Annealed Langevin)
Unlike the true reverse SDE, this annealed Langevin incurs bias that stems from the fact that never quite reaches ne by time L. The bias is characterized in Guo et al. (2024), Cordero-Encinar et al. (2025), where it shown to related the action of the path T; through the space of distributions. Specifically, for the path T. described above. the action is bounded in Cordero-Encine et al. (2025) by a quantity that is independent of any functional inequalities.
In fact?, any path t + n² with velocity field vi can be efficiently sampled from by starting with Xu ~ T and running X, (X,) - X, ~ T². However, for an arbitrary path t + Λ², it may not be easy to initialize X, ~ 2 or to compute the corresponding velocity field v,, Implementing the ODE also incurs a discretization bias.
'Theee is line of work analyzing the propagation of score matching errors into the sampling distribution (Chen et al., 2023; Lee et al., 2023). Because our interest in the posterior sampling problem, we will assume that we have the exact prior score.
We use superseript here to emphasize that n' need not he the marginal of OU process, like Re-
4

---

Published as a conference paper at ICLR 2026
Remark 2.1 (Action). We can think of the action of path as giving the run time of sampling along using annealed Langevin. Different paths connecting x0 and n/ coming from different fields ve give different actions. Some Ut lead to paths that are fast but difficult to compute, like the optimal transport path, or the constant speed geodesic connecting nO to π².. This path can be shown to have the least action over all paths, but implement this we would need to compute the optimal transport map. On the other hand, Annealed Langevin has a large action but could be easier to implement.
Discretization: Langevin Monte Carlo is an efficient discretization of Langevin Dynamics, where the drift is fixed over small intervals of time. Suppose we run our algorithm for time T, and suppose our discretization step size is 8. Let B, denote a Wiener Process. We have the following "interpolated" process
dx,-
V log ग (Xx6) dt + V2 dB,
I E [1:6, (k: + 1)6)
We can integrate this between kō and (k: + 1) to get
X(K+1J& = X&8 + ov log (Xas) + A 22 BES)
(LMC)
We refer to this as running LMC towards æ. Similarly, Annealed Langevin has the corresponding interpolation dxX,, = log (Xxss) dt + /2 dB, for t [R-5, (h + 1)6), which can be discretized as
X(K+1)8 = X&8 + V log T&a (Xa6) 6+ + 25 (B(x+1)8 BBs))
(Annealed LMC)
Remark 2.2 (Annealing). There are two notions of annealing in the context of sampling. The first is temperature annealing, where the diffusive term of the SDE (Langevin) is modified be /2/10g(244) (Geman& & Hwang, 1986). Second is Gaussian annealing, where the diffusive term is fixed, but the drift term of (Langevin) is modified by using the score of smoothed prior. Indeed, the continuous time variant of DDPM (Song & Ermon, 2020) is such an annealing and Algorithm is archetype of the latter type of annealing for posterior sampling.
2.1 LOCAL MIXING AND METASTABILITY
Recall the interpretation of Langevin Dynamics as gradient flow in the space of measures towards a minimum of the functional (L)) There is only one global minima corresponding to the correct distribution: (L(p 0 = p = w. If we view the relative Fisher information Fl(p, π a gradient norm in this analogy. one can ask whether we can quickly find first order approximately stationary point p satisfying Fl(p, л) < c. It is shown in Balasubramanian et al. (2022) that LD achieves FI T) < in polynomial time (d (é²) for the average iterate, that is + ʃ p,dt. We remark that this convergence is independent of LSI, but describes a weaker type of convergence as discussed below.
There is a sense in which Fl convergence ensures local mixing within "modes" of a distribution. Take two distributions 72. Let [B (x) (respectively, (2115 (x)) denote the distribution 71 conditioned on being within a ball of radius E around the point x. In Lemma D.1, we show that for small enough
Ex KL (TIIEE S =FI(11, 72)
(Pointwise LSI)
In other words, conditioned on being within a small radius of any point, the two distributions match in KL, on average?. In distribution with multiple separated modes, this means that conditioned on any specific mode, the sampler is accurate, even in KL. For intuition, consider distribution that has multiple modes (e.g., a mixture of Gaussians). The Fl convergence implies that if initialized close to one of the modes, LMC will converge quickly to sample "from this mode". Notably, however, in this setting, Fl convergence is not very sensitive to the weights of the modes because the Fl involves gradient operation on the log-density, which makes it insensitive to mode weights. Thus, this is too weak to ensure a global convergence. We further discuss this in Remark 4. in the context of posterior sampling.
'If the standard LSI: KL (L(7al/72) S Fl( 72) were to hold, that would be the "global" analog of this result. However, the setting of regions of low density in between high density regions that is typical of multimodal distributions precludes such an I.SI.
5

---

Published as a conference paper at ICLR 2026
Figure I: Hardness of posterior sampling: this instance, the prior is represented by the orange region, we measure a coordinate spec- ified by the red arrow. The posterior is repre- sented by the blue region.
Less noise
More noise
2.2 POSTERIOR SAMPLING
The discussion thus far has been about the classical sampling problem we want to sample from given log x or V log Tt. the posterior sampling problem, we also have likelihood R. and we would like to sample from μ me- =/= we -R, There is immediate way to use the prior smoothed scores to get the posterior smoothed scores. Many approaches to posterior sampling (Section 3 of Daras et al. (2024)) proceed by trying to estimate V (og()))). but none establish a formal guarantee.
In fact, the hardness sampling from a posterior has been established in recent works. Gupta al. (2024) describes instance in which sampling from the prior tractable yet sampling from a posterior derived from a noisy linear measurement is intractable under a cryptographic hardness assumption. Bruna & Han (2024) reduces the posterior sampling problem to an Ising model in which the prior is uniform distribution of the hypercube and shows hardness under standard computational hardness results. We will discuss this difficulty intuitively using the Figure
Consider the following instance. The prior consists of a number of modes (in Figure 1, there are four, one corresponding each of the vertical "bars"). The measurement is the vertical coordinate (one such measurement is represented by the red dotted line). In our case, the lefumost bar and the two to the right are consistent with the measurement, while the second from the left is not. However, we cannot use the scores V log x; from high noise levels to tell whether a specific mode is consistent. That is, high noise levels scores cannot distinguish between the true prior and prior with a different pattern of consistency, say one in which every mode is consistent. For distinguishing this, only the low noise level scores are useful, but usually by the time we are using the low noise level scores in an algorithm, have already committed to mode and cannot drift samples to other modes.
This suggests that we look at posterior sampling at two scales. At a local scale, the low noise level prior scores V log π, (combined with the gradients of the ligelhooss R(x))) contain enough information to sample correctly conditioned on any small neighborhood, and the locality of such a task ensures that this be achieved by SDE in polynomial time. The difficulty with sampling truly in KL is that these local guarantees cannot be accurately stitched together. We will see that the high noise level scores be used "warm-start" the local sampling described above.
ANNEALED LANGEVIN MONTE CARLO FOR POSTERIOR SAMPLING
Algorithm Annealed Langevin Monte Carlo
Input: 27 ~ 7, rate 1/ke, Warm Up period T, Warm Start period Twe. step size 6
Output:
Warm Start, sample Xxr pr Rs Hoo
2: for 1 to T do
3: Sample 17, 7/
4: =;= = - 8(2,-1 1 V((z+-)) + 28 m
5: end for
6: b Anncaling phase, track distributions { from Two +
7: TTw.k/68 22
8: for i i Tustt/ 00000oon to 0 do
9: Sample 7): ~ 7
10: 2;-1 = 2, + logpie vR(x,)) + 28 m
11: end for
We construct a path + #4 of posteriors, with μ4 x p.e R (that is, posteriors of noised priors). In Figure 3, this curve is represented by the blue curve between pr.,, and (ln- This path is absolutely

---

Published as a conference paper at ICLR 2026
continuous (see Lemma B.2) and thus generated by some velocity field v.. However, because do not know ut we cannot use this field to traverse the curve. Our results bound the action of this path to show that Annealed LMC tracks discretization of this continuous path. We denote sample at time by X,, and the associated distribution by Pt- There are two phases to our algorithm, as below.
Warm Start: We sample our initial point Xo from a standard Gaussian % and run LMC for target y R /Z for log _ iterates. Because R is convex, ye is strongly log-concave, so efficient convergence within in KL follows from prior work (Vempala & Wibisono, 2022). We can think of this warm start as biasing our samples towards the measurement. At this point, we have not aligned our samples at all with the prior.
Starting from PT... with Tw. x 2 log 1 we run Annealed LMC to track the distribu- tions je from Tws to O. We use parameter K to control the rate which we move along this path. Moving slowly results in better agreement between the law of the iterate and the corresponding target.
Annealing:
Hips
Figure Beginning y, we use LMC to sam- ple an initialization close to Moo We then run the Annealed LMC tracking μ4. The blue path represents the target distributions, first the Langevin path from y - Moo. followed by {Fr] from Meoo to μo (the true posterior). The orange curve indicates the laws of the iterates of LMC towards Vos in the first phase, and the laws of the iterates of Annealed LMC towards {ur} for the second phase.
or
Pipsk la
1TT Moii Pr
A note on the rate k: From Lemma 4.3 we can sample from close to uTT.. in KL for Two X log using LMC for target Mox Rather than running the annealing backward at the same rate as the forward OU process, we slow down' by a factor of k. Our iterates go from XTu + Xo. the annealing targets go from (Tr... - po in the continuous process, but in the discretized algorithm, the iterate X;-1 uses target M/5//c- The law of the iterates p; goes from PI.../6 to Po-
The pathology of L ++ ,4t It is illustrative to contrast the path L + f4, with the path / + Pt from a recent application of Annealed LMC for sampling from the prior (Cordero-Encinas et al., 2025). The path t + Pt can be followed efficiently because the curve P: is "continuous" in that the forward process is just an OU process with W W2(Pt, Pt+s) ~ 8, resulting in an action that can be bounded. However, even when Pt is close Pt+5 need not have 44 close 14+66 A simple example is that of Figure 3. We have a prior represented in orange, a noisy measurement represented by the red arrow, likelihood represented by the gray region, and a posterior represented by the blue shaded region. On the right side, the smaller mode is quite likely under the posterior. On the left side for a lower noise level, that mode has all but vanished from the posterior. This results in two distributions je and pr+4 such that ô is small, Pt is close to Pt+6 in Wasserstein, but μe is not close to P1+6- This "discontinuty"" the reason we cannot get KL bound for Po- However, the noising process introduces enough regularity that we can get bounds for the Wasserstein derivatives up until small t. Furthermore, the changes in the scores V log M++ A V log 14 are better behaved than changes in the oog-pobabillitess log M++ log μum This allows us to get guarantees in Fl rather than KL for 140-
Figure 3: "Discontinuity" of {pt]: The prior
consists of two vertical orange bars. We obtain a measurement, represented by the dotted line, of the vertical coordinate corrupted by some Gaus- sian noise. The log-likelihood is represented by the colored gradient, with dark representing regions of higher likelihood. Like the prior, the posterior represented in blue is bimodal, with one mode corresponding to each of the modes of the prior.
Less
"Thi inspired by similar rate parameter in (Wu et al., 2024).
7

---

Published as a conference paper at ICLR 2026
4 RESULTS
In this section, we will describe our main results. Most proofs have been deferred to the appendices, where the theorem statements contain the exact polynomial dependencies. Assumption 4.1. We make the following assumptions:
(i) The prior po is --suu--Gaussian with zero mean.
(ii) the score V loglooooos Po(x) is - Lipschitz.
(iii) The log-likelihood function Rax) smooth, convex, and bounded below by such that there exists F, ||-|| S D, R[(x) = 0, and V RI.
Remark 4.2. The first assumption is generally satisfied by natural distributions, for instance, by images where each pixel is bounded intensity. The second assumption is standard in the literature (Chen et al., 2023; Lee et al., 2023). The third assumption establishes a regularity for the likelihood. In the case of noisy linear measurements
Ax + on for 1J 7 Ri S ||A11//0
Warm Start: We begin by getting sample from (close to) the limiting distribution Poo = -ime Pt- We incur errors because we stop in finite time, and due to discretizations.
Lemma 4.3. Take = O 4 log KM<l))m)) and Tws = O (log 4) The Warm Start phase of Algorithm I results in a sample Xr satisfying KL(μT,... [aw((XT) S.
Proof Sketch. The Warm Start phase is LMC for the target Moxe Because is strongly log-concave, R is convex, ye- -R is strongly log-concave, so efficient sampling is possible. We can shift the guarantee MTw. because Poo = MT
Annealing Phase:
We can now begin our annealing towards the target distribution. If we traverse the annealed path je x pie -R the KL divergence between the law of the iterates Pix/6 and μ4 is
(LelllP)))))) E (L (PTT)))/)) + (J [|v.]]? dt/a).
where ey denotes the velocity field that generates the path {pe]. An important aspect of this phase is the rate 1/M which slows traversal of the path {Ne} allowing the iterates to better track the distribution.
Theorem 4.4. Suppose we run Warm Start phase with T = O (dx [og(x<((7)ll>>))) Tws = log kd, following which we run the Annealing Phase with 8 = K k/44, 1/4, This results in T = K. 7/16 satisfying
(L(pIllPTH/s) I poly(d,
Proof Sketch. Important technical tools we use are bounds on the magnitude of the derivatives O log O log jt (Lemmas C.5 and C.6). These, together with Lemma B.2, allow us bound the metric derivative (2(e)) = lim W2 mr)/A, A, where e is the drift implementing the path μe. The dominant term the KL distance comes from the action f ||v li dt.
Theorem 4.4 shows that we can track the annealed path up until t defined above for polynomial run time. Beyond that, Pt does not track P18/x closely. We now consider the Fisher Divergence.
Theorem 4.5. Suppose we run Warm Start phase with T = O (d ks log(s<L(>]llue))) Tame log kd, following which we run the Annealing Phase with 5 = x 1/4 This results in T = K 3/10 satisfying
Fl(pre48, Ho) S 0088112 (
Proof Sketch. Consider 0.p: V (pr V log pt). ). de Bruijn's 's identity states: Miosn
- -K 2 Fl ps8/K)
Since we are using annealed LMC, to telescope this as in the LMC analysis we also need to bound
KL KL(pisll (pi8l1148/=) KL((ss\||
prs (log 145/K log (((-188/x)-
8

---

Published as a conference paper at ICLR 2026
Because the initialization PIw. is sub-Gaussian, we can bound the drifts of our algorithm show that the resulting Pt is sub-Gaussian. Lemmas C.5 and C.6 again allow us to bound log Mi8/K log (1/1)88/s> which show grows at most polynomially. As consequence, we have
Task/á
(++1)6
(I( M48/N) di 2 (L l
From here, we finish using weak triangle inequality for Fl to get a guarantee against μoo
These results are driven by Lemmas C.5 and C.6, which effectively show that the posteriors 14r change in relatively mild way until some small t 0, allowing us anneal samples in polynomial time. Putting these together, we have the following conclusion, which states that there is an iterate close to the last iterate that satisfies simultaneous "global" KL guarantee posterior for a noised prior and a "local" FI guarantee to the true posterior.
IKL + FI] In algorithm 1, suppose we Warm Start phase with T O (d3x: log(x<L(<))lln Tw log rd, following which we run the Annealing Phase with 8 k3/4, then there S
( 9/20,, such that Prk/6 simultaneously satisfies
(L((IllPTr>))) - O(xx-1/2) which implies TV (V 14) S ~O(Vdx- dV
*
FI(PTT2ii no)= < Odkx V/e)
For this choice of K, the algorithm has run time (1x"²))
4.1 LOCAL AND GLOBAL GUARANTEES- IMPLICATIONS COROLLARY 4
It is possible to just get convergence in Fl,, indeed running LMC towards the posterior,
X;+1 X, + 8V log M4 (X,, + V2õe,
6~ NO, I),
results in polynomial convergence to f40 in Fl as in Balasubramanian et al. (2022). However, convergence in FI is susceptible to the phenomenon of "mode collapse", where for instance, in a multimodal distribution, the sampler significantly under-samples a specific mode depending on initialization. This particularly critical our setting one could interpret posterior sampling for multi-modal priors equivalent to conditionally sampling from a subset of modes that is consistent with a measurement. We will illustrate this below for mixture of two Gaussians, and show how Theorem 4.4 avoids this failure mode.
Let us define bimodal prior and likelihood:
Po / NO, + 2 w (1))
.2).
R(x)
- diag((O, 1])x|²
21
Let 1 17 77 and let Ag diag ([1, DJ) for any O. Then the posterior can be written
no = a Aw) + (1- ao) (AAW
A.
1
1 1 1+9
However, see in Lemma D.2 that even the distribution (with equal mode weights)
1 N (AAy
n/ = - N (0. Avy) Av, 2
X² ( So for > 15, X + co, Fl completely fails to discriminate the distribution with the correct mode weights of (ap, 1 an) from an incorrect distribution with equal weights (4/2, 1/2). Now consider noisy prior, and the corresponding posterior
satisfies FI(Ho, 1b) < e
2 1( 2 N
Ae
1 1).
aN (0, A,, + (1 a.) (e- AA,
with 0z
22 1
l1
9

---

Published as a conference paper at ICLR 2026
As saw previously, with the Fl guarantee alone, there is guarantee the weight a, which could range from 1/2 to exponentially close to 1. However the KL (which implies a TV) guarantee shows that the weights can themselves not be off by more ve. which means a2 = Ve.
We can now complete the discussion of Section 2.2. We saw in Section 2.1 that a Fl gurarantee can be be interpreted as type of "local" KL guarantee, and that these local guarantees cannot be stitched to get a KL guarantee. In a multimodal setting, such as this one, however, the weights of the modes themselves fall under the purview of the overall KL bound (Theorem 4.4), which sets them by solving a "simplified" posterior sampling problem.
Remark 4.6. Approximating the posterior of a noised prior is in some sense the best we can do tractably. Consider the lower bound instance of Gupta et al. (2024). In summary, they use way function f: (-1,1)d {-1,1} such that f(x:) = y is easy compute, but F They construct a posterior sampling problem, where the prior corresponds to a uniform distribution over {-1,1]" the measurement is a specific f(z) = y, and the posterior would correspond to distribution concentrated on the true inverse f (y)) Using the same measurement but noising the prior sufficiently results in distribution for that is uniform over {-1,1]d In other words, the posterior hr is concentrated on the true f (1) only for very small values of
difficult.
Figure 4: Our prior (shown on the left) consists of several vertical bars, two of which have gaps in them. The measurement model encourages the vertical coordinate to be -0.25, as indicated by the red horizontal line. The distribution of the sampler is depicted with kernel density plots for each of the resulting modes (shown to the right in red overlaid on top of the prior).
Remark 4.7. Consider a prior of several verticul "bars" in R2,, two of which huve gap in them in some range of the vertical coordinate (see Figure 4). Our measurement operator gives us only a noisy measurement of the vertical coordinate (the red dotted line, in this case at y -25). The two bars with gaps in them should be very unlikely under the true posterior. However, the posterior of a noised prior would not notice this gap for some time. The annealed Langevin algorithm we describe results in the sampler shown on the right. A kernel density estimate for each of the resulting modes is plotted red. Note that each of the modes is discovered, and as see from the marginals, the two modes that should have lower weight under the posterior do have a smaller weight.
5 CONCLUSION
We study the Annealed Langevin Monte Carlo algorithm to generate samples from an approximation the true posterior distribution. We show that this algorithm simultaneously satisfies two properties: when initialized with an efficient start"start", an iterate close to the final iterate is (i) close in KL with respect to the posterior with noisy prior, and (ii) close in Fl with respect to the true posterior. To the best of our knowledge, these constitute the first polynomial-ting results for a suitable notion of approximate posterior sampling.
We believe this type of guarantee is also possible with other popular posterior sampling frameworks like Split-Gibbs sampling, which can interpreted as a different discrete path through the space of distributions. Furthermore, there may be other paths {4r) } that allow us to sample from interpretable approximations to the true posterior (such as on that more closely aligns with DDPM, rather than Annealed Langevin); this is an interesting avenue for future work.
ACKNOWLEDGMENTS
This research has been supported by NSF Grants 2019844, 2505865 and 2112471, and the UT Austin Machine Learning Lab.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Luigi Ambrosio and Giuseppe Savaré. Chapter gradient flows of probability mea- sures. volume 3 of Handbook of Differential Equations: Evolutionary Equations, pp. 1-136. North-Holland, 2007. doi: http://c..og/uuunoosss3377777710 URL .tt. wtt.p//wwww..c..............aaaa
https: www.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures Mathematics ETH Zürich. Birkhäuser, Basel, 2. ed
edition, 2008. ISBN 378-3-7643-8722-88 OCLC: 254181287.
Brian D. O. Anderson. Reverse-time diffusion equation models. lic Processes and their Applications, 12:313-326,
Stochas- URL
1982.
3897405
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion operators. Grundlehren der mathematischen Wissenschaften, Vol. 348. Springer, January 2014.
URL https::tpp/.......... / /hal sci sccienceeeeee hotccc/991000099..0
Krishnakumar Balasubramanian, Sinho Chewi, Murat A. Erdogdu, Adil Salim, and Matthew Zhang. Towards a theory of non-log-concave sampling: First-order stationarity guarantees for langevin 05214.
monte carlo, 2022. URL htt
Black Forest Labs. Black forest labs, 2024. URL / ai/. Accessed: September 2024.
Valentin De Bortoli, Michael Hutchinson, Peter Wimsherger, and Arnaud Doucet. Target score matching, 2024. URL http:hts//aaxi....rrrreeeeeee http://awwii..rrraaa//....0....0 2402.. 08667.
Joan Bruna and Jiequn Han. Posterior sampling with denoising oracles via tilted transport, 2024.
URL httph:: org/ httg//bb/24477 00745.
Hong-Bin Chen, Sinho Chewi, and Jonathan Niles-Weed Dimension-free log-sobolev inequalities for mixture distributions, 2021. URL http::::///........oaabbb///////
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R. Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions, 2023. URL https: /arxxiv org/ abs 0tt//229..1111
Sinho Chewi. Log-concave sampling. Book draft available at https://chewisinho. github. io, 9:17-18, 2023.
Hyungjin Chung, Jeongsol Kim, Michael Mccann, Mare L. Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems, 2022. URL
https: fttps::/arrivv
Paula Cordero-Enninarr, O Deniz Akyildiz, and Andrew B Duncan. Non-asymptotic analysis of diffusion annealed langevin monte carlo for generative modelling. arXiv preprint arXiv:2502.09306, 2025.
Giannis Daras. Hyungjin Chung, Chieh-Hose Lai, Yuki Mitsufuji, Jong Chul Ye, Peyman Milanfar, Alexandros G Dimakis, and Mauricio Delbracio. A survey on diffusion models for inverse problems. arXiv preprint arXiv:2410.00000 2024.
Zehao Dou and Yang Song. Diffusion posterior sampling for linear inverse problem solving: filtering perspective. In The Twelfth International Conference Learning Representations, 2024.
Stuart Geman and Chii-Ruey Hwang. Diffusions for global optimization. SIAM Journal on Control and Optimization, 2435):1031-1043, 1986. doi: 10.1137/0324060.
Wei Guo, Molei Tao, and Yongxin Chen. Provable benefit of annealed langevin monte carlo for non-log-concave sampling. arXiv preprint (0l0:22207.13333 2024.

---

Published as a conference paper at ICLR 2026
Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun. Diffusion poste- rоor sampling is computationally intractable. Ruslan Salakhutdinov, Zico Kolter, Kather- ine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Pro- ceedings of the 41st International Conference on Machine Learning, volume 235 of Pro- ceedings of Machine Learning Research, pp. 17020-17059 PMLR, 21-27 Jul 2024. URL ht https: http://poceeeeiiggs/
weaeeediiinnmmm.......mmm. mlr press v2 p gu..
Bruce Hajek and Galen Sasaki. Simulated annealing to cool or not. Systems and Control Letters, 12(5):443 1989. ISSN 0167-6911. doi: http://cab.og///0000000666666111
URL https: http///wwwww..o www.nweiiiiceeerree...........ee httpss//www..cceeneeeeee....... com/ http:///ww..i..ee..eaaaeaaa////a
Amir Hertz, Andrey Voynov, Shlomi Fruchter, and Daniel Cohen-Or: Style aligned image generation via shared attention. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4775-4785, 2024.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models, 2020. URL
https: /ttp///axvvv.//. org/ abs/2006.
Richard Jordan, David Kinderlehrer, and Felix
Otto.
The variational for- Journal on Mathemati-
mulation of the fokker-planck equation.
SIAM
cal Analysis. 29(1):1-17, 1998.
doi: 10.113775006114199603333
URL
Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song. Denoising diffusion restoration models. Advances in Neural Information Processing Systems, 35:23593-23606, 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity, 2023. URL https: http://axxvv.rr../...... /twgg///////ee /206. 06227.
Andreas Lugmayr, Martin Danelljan, Andres Romero, Fisher Yu, Radu Timofte, and Luc Van Gool. Repaint: Inpainting using denoising diffusion probabilistic models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11461-11471, 2022.
E Marinari and G Parisi. Simulated tempering: A new monte carlo scheme. physics Letters (EPL), 19(6):551-458, July 1992. doi: 10. 1.12200295--00759999/0000 URL
Euro-
http://da doi. org/10..//.o wttrg/11.12999 1209 0295-5055 1 9/6 6/ 002.
Bernt Øksendal. Stochastic differential equations. Springer, 2003.
F. Otto and C. Villani. Generalization of inequality by talagrand and links with the logarithmic sobolev incquality. Journal of Functional Analysis, 173(2):361- 400. 2000. ISSN 0022-1236.
doi: https://bb..rr//1..0000/.aaaaa 33557 URL https: http://wwwwstt http///wwciieeeeeeeeeee.ee com/ http:///wwnceeeeteeee///////////
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp. 8821-8831. PMLR, 2021.
H. Robbins.
An empirical bayes approach to statistics. Berkeley Symp. Math. Statist. Probab. 1956, 1:157-163, 1956. nttps://cir.we ht///rrnni..e. hoo..a...pp/rraaa11722400000000
Proc. 3rd
URL
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Om- mer. High-resolution image synthesis with latent diffusion models, 2022. URL
https: https///axxvvvoor.ooo/
Litu Rout, Negin Raoof, Giannis Daras, Constantine Caramanis, Alexandros G Dimakis, and Sanjay Shakkottai. Solving inverse problems provably via posterior sampling with latent diffusion models. In Thirth-seventh Conference on Neural Information Processing Systems, 2023.
Litu Rout, Yujia Chen, Abhishek Kumar, Constantine Caramanis, Sanjay Shakkottai, and Shenn Chu. Beyond first-order tweedie: Solving inverse problems using latent diffusion. In JEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9472-9481, 2024.
12

---

Published as a conference paper at ICLR 2026
Litu Rout, Yujia Chen, Nataniel Ruiz, Constantine Caramanis, Sanjay Shakkottai, and Wen-Sheng Chu. Semantic image inversion and editing using rectified stochastic differential equations. The Thirteenth International Conference Learning Representations, 2025a.
Litu Rout, Yujia Chen, Nataniel Ruiz, Abhishek Kumar, Constantine Caramanis, Sanjay Shakkottai, and Wen-Sheng Chu. RB-modulation: Training-free personalization using stochastic optimal control. In The Thirteenth International Conference on Learning Representations, 2025b. URL
net. wow.m:idd-nnIIPCGG333 ott.pp/cwwwee..eeooooooooooooood
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al. Photorealistic text-to- -mmgee diffusion models with deep language understanding. arXiv preprint arXiv:2205.11487, 2022.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models, 2022a. URL https://arxise wwtp://rgg/bbbb///o///o
02502.
Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. Pseudoinverse-guuided diffusion models for inverse problems. In International Conference on Learning Representations, 2023.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution, 2020. URL https: //tp:i//aaaiia/aa/eaaeeeeeaiaala
http://///wwwww..oa//a////////// wttp:/wwww.rgg/b//////00 05600.
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben
Poole. Score-based generative modeling through stochastic differential equations, 2021. URL
https: / /ttpaaaxiivv/v.////iv wwwpsiiii.rrraaaaa 13456
Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medical imaging 08005.
with score-based generative models, 2022b. URL htt.:httts://rrxi..rrrr////
08005.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm:
Isoperimetry suffices, 2022. URL httttttt/axxi...ooot wttp./s//////////// 08568.
Andre Wibisono. Sampling optimization in the space of measures: The langevin dynamics composite optimization problem, 2018. URL htts:: https: http:///aaxxxxvx.aaaa..o 1tt.:/12220000000
Andre Wibisono. Mixing time of the proximal sampler in relative fisher information via strong data processing inequality, 2025. URL httpp:://axiv..org//aaaaaae
056.3.
Luhuan Wu, Brian L. Trippe, Christian A. Naesseth, David M. Blei, and John P. Cunningham. Practical and asymptotically exact conditional sampling in diffusion models, 2024. URL https::/aaxxe /ttp///rwi..orr/aaa////./..1
Xingyu Xu and Yuejie Chi. Provably robust score-based diffusion posterior sampling for plug-and- play image reconstruction, 2024. URL https: http://:///aawi.o////b/e////////
17042.
13

---

Published as a conference paper at ICLR 2026
A PRELIMINARIES
A.1 NOTATION AND OVERVIEW
Notation. The prior is denoted p. The log-likelihood, the measurement consistency, is denoted R. We denote by p: the distribution p passed through the OU channel, which is to say, if X, is an OU process with Xg having law p, then pr is the law of X₃. We l denote posteriors, so μa is the posterior Poc R/ /Z, and #r is P.c R. We use a to denote composition, so (f g) = f(g())
We C (24) to denote the space of all smooth functions on l with compact support, P2 to denote the set of measures on Rdd and (R))) to denote the set of measures that are absolutely continuous with respect to the Lebesgue measure.
Remark A.1 (Constants greater than one). For simplicity, we assume that each of the constants defined in Assumption 4. I is constant greater than one.
Overview. In Section A.2 review some identities that will be useful. In A.3 state some prior work with references. In Appendix B we discuss various aspects of the algorithm discussed in Section In Appendix C state and prove some bounds that are useful Appendix
A.2 PRELIMINARIES
Lemma A.2 (Identities). We have the following identities, under benign regularity conditions. These commonly used in the literature but repeated here for completeness
1. For f.g :0::2 Fd + R. we have V (f g) = (V ff) =g
2. For f :RR + RR Rd E. we have Vif * g) (Vf) gg
3. For : - R, have AS 9) (Af)* *g
4. For f:R. I. g R R. (fVg) V Vg fAg
5. For f : IR TR. /V log
VS
Proof. Follows from switching the order of the integrals and the derivatives. The principle is that convolution commutes with linear operators.
1.
V (f = =a, E
f(0- v))(v) dy oo - v)9(e)) dy = / Σ (0.f(z - u() (V f)*g
/ |
2.
v( V. [(x ( v)g()) dy V=
3. Follows from the above two:
A(f g) V V(f * g) V ((V)) * V (Vf)* (Af) *g
The remaining are common calculus manipulations.
Lemma A.3 (Gaussians). The following hold for Gaussians "/z (I)
1. VT
oZ 7oa
||||| 0
2. Ayaa
Yo2
3. A logg -
The above also follow from standard calculus rules.
14

---

Published as a conference paper at ICLR 2026
A.3 MISCELLENEOUS RESULTS
Lemma A.4 (Girsanov, (Oksendal, 2003)). Let Xo Po. Xo Po. and suppose
dX, (X,) dt + V2 dB. = dep: = -V (prv)) + Apt
(4)
dx x di + v2 dBt
> Depl -V (d/r)) Am
The KL divergence between pt and pe can be bounded as
KL(pelle)) & KL(polleb) + Exx.1 S [1x((x)) - o((,)]1
Lemma A.S (LMC convergence under Log-Concavity (Vempala Wibisono, 2022)). Let k E N, and let Pkh. denote the law of the k-th iterate of the Langevin Monte Carlo (LMC) algorithm with step size O. Assume that the target distribution x exp(-V) satisfies logarithmic Sobolev and for all
inequality with constant CLS((T) (T) I and that VV is B-Lipschitz. Then, for all h S 43 N N,
KL(UNA || (| exp(- KI x1 + 0 (
8ch
In particular, letting K = 3 a' for all E 10, and for step size x
e² Bud
we have
V VKL(UNA () S after N = 2d log KL [l]
iterations.
Lemma A.6 (HWI inequality (Otto & Villani, 2000)). Let E P2((R)) be a reference measure, and let p E (R))). We have
(L(Fllp) s W2( p) Fl(T, p)
Lemma A.7 (Talagrands transportation inequality (Chewi, 2023)), Let E P2(RR) be atrrongly concave. Then we have
(L(p)<>) 2 2 (p,
B PROOFS FOR ANNEALED LANGEVIN
In this section, we elaborate the proofs of section 3. Recall our general strategy for sampling. We
Pips
140
Pipga/o
WT Wol PT
Figure 5: (1.) We sample using LMC from Be R3 Poo. (2.) We run Annealed LMC along the path + Me.
begin by showing that the limiting distribution exists limy++00 Pt Moo-
Lemma B.I. Let μ4 P /Z. The sequence μ4 converges weakly 1loo Re-RRRRR R/2
15

---

Published as a conference paper at ICLR 2026
Proof. First note that if p Cg (R), then lim e"" p(c'x) ô in the sense of distributions, We need to show for every o Ce (R) that Ey Φ = - E,, Ø. We have
lim B lim I [((x) 11(x) pr(x) da
((())--
J -e- De de
lim _ (6())e R(w) (x) de
lim/+400 _ R(aa) pt (z) dr
I [lime x(z)e R( (r) de
flim e R( pc (x) dr
J [0(z)e R(x) (()) dx
Se {e-B(a) R(a))(()) dr
Eps Ø
The second equality holds long lime-soo I {R)((z) (ʃ elul 1)m (1) dy) dr + O. The third requires dominated convergence for pe (z)e (oo())e-Re))a ((x) and pe (x)e RR(x), The fourth requires lim moe Pt y. We will confirm these below in reverse order. First we have
lim Pe lim / p''(le(x-v))) (0000
2xy) dy
/
lim 10
u)mm- a (y)) dy
/
lim edd p(e w)))
lim n n- (1)) dy
/ 8(x - un(()) dy =7
S (1-e Mqjaz e R(x) R(x) (xx) pointwise, and [T- 2yya (())((())))))) dr = [I- 21ar7 e R(x) ((x) dr. Because e e R and @ are both square integrable, e- is integrable from Cauchy Schwartz, and we can use the dominated convergence theorem to show that
From C.4, we know P.e p RR()) ((x))
lim / (--B t
R(x) p.(x)(()) dr = lim c --1(x) (())(())) dr.
t0x
We can show similarly that
lim / (-(()) dr = lim e -R((s) dr. 8000
Finally, we have
/ c- (e) dr d==/
lim e -R(u)) dx= / / (R)()))(())) do > 0.
lim 1-00
60000
This distribution is log-concave, and we can show that LMC converges quickly to Pox. Let (X,) denote the law of X, when X, y and we run LMC towards Hooe for time T (Line 4 of Algorithm 1). We show that Pws Moo PT.. for sufficiently large Tw.... T' The standard results on LMC convergence are usually given terms of the KL divergence between the law of the iterate and the target distribution. To apply Girsanov's Theorem A.4 later in 4.4 need the KL divergence between the target and the law of the iterate.
Lemma 4.3. Take T O log KlTT and Tws O (log 2). The Warm Start phase of Algorithm I results in a sample XT satisfying KL(μr... (La(((x)) Sc.
Proof. We will do this in three steps. First, we will show that standard results in this setting bound (L(Law(X))]lls Then will bound KL (aassl/(a(()))) from KL(Law(Xr))lpa In
16

---

Published as a conference paper at ICLR 2026
general, cannot reverse the order of the arguments in KL divergence but under some conditions (log-concavity + lipschitzness of the scores + subgaussian target), and then show that (L [[))) is small.
Step Showing that (L) <E The drift term
v Mo Vlog(ne- (aeeeRR//--- - VR
satisfies
IV(--- v S vi Rt
and also || VRYII 2 d from convexity of R, so Poo is d dd-log-concaye From Lemma A.5 (which from Vempala & Wibisono (2022)), we that take 3 H. 1 Xt 6 [1-
and to get that at T = o ( log )U(+llu=)) iterations we have KL(Law(Tr)]IMa))) c
Step 2. Showing that (Ls(sllala(((rr <c
By Lemma A.6 we have
K Law((r)) W Moc) /Fl(uo Law(Xr)).
The Fisher divergence is bounded by dimension dependent constant
Fl( Law(Xr))
= E, V Mox uo
log log
< 2E V log Moo 1| + 2 V log Law(XT))
s poly(m (m, Ri L, d)
Overall we get [Law( XT)) S poly(m, R, (Law(La(
Note that Poo is at least 1 - strongly log log-concave, we have from Talagrands transportation inequality A.7
(L()))| - poly(m, R. 2) (L)()((Xr))
S poly(m, Ri E) (Laa:KLLLLLLLIlIlIl poly(m, R, 2)
Step 3. Showing that (L(PT... Law(Xr))
can now also show that (L (I,T,.)) ) is small
(atir.,)/La(Xr)) = Eprax log HTw. log Law(Xr)
Eprax log log Mmo + log Mox log (a)())))
KL (L [| + Bur,.. (log Hoo
log Law(Xr)
Ey (log Moo - log Law Law(X
1TTwe
Prx
Ep [(log poo log LaalLaa(XP)) (X+)) sup NI (x)
Moo (x)
KL Law (XT)) sup uT (x) 1oo (x)
(L(HHo|Laa((XT)) sup, Hog llg pool
We have from Lemma C.7
2Tw sup llog -log < e1---27w poly(m,&,9H.l
So if we set T.,s O(log {), we get (L(Law((T))lmm poly(m, H. 2)..
17

---

Published as a conference paper at ICLR 2026
A map from [0, P2( is absolutely contimuous if for all t,
W2(Me, (4+6)) 0C.
[i(t)
lim 5-0
Consider the continuity equation dm, - (TT Any choice of et results in curve t + we- but, conversely ++ Te is an absolutely continuous curve, there exists a choice of Ut, such that 0,54 V (TzUE) and ||v]]L22(=)) S (i(()). We refer the reader Chewi (2023) or Ambrosio et al. (2008) for a more elaborate exposition. In order to use Girsanov's ' Theorem to bound the KL distance for the drift between the target and the law of the iterate during annealed LMC, will need bound this derivative [a(t)).
Lemma B.2. The path + ar is an absolutely continuous curve. There exists velocity field or satisfying 0ep4: = - (pevt), and
de de-
|eelleated $ (1 ul-e-aypPolymmmmo
Proof. We have (M(,, u) inf( / XX - Y| dr. From duality we get the follow- ing equivalent characterization
fd v) Lip(f) s $1}
Wi(H = sup
(5)
To tie this W2, recall that for all subgaussssi μı, M, we have W2(n, v/ S v /mWi (ju, v). Without loss of generality
assume f 2 O, because for any constant in particular for inf f. we have f d du -v) = -f - c) d (μ v).
So we have
f dd v) Lip(S) $1}
W)
f dd - v) 10--inn |inf i d(u - v) =
= sup
{ / pd(u v) Lip(S) < 11,5 1,120
sup
Take any specific f. From Lip(f) I 1, we have f < ||=]|,, and from Lemma C.6 we have O log p4l 5 mp- E a,||=]]' for a, d poly(m, 2, R). Putting these together we have
e flä log S (1 (1-e- e e-2a-
a |=||
From Lemmas C.1 and C.3 we have E,,, 11 log uzl S From this, we have for all Lipschitz f
TI- poly R, L).
e 'dd
e'dd I f Idd dip - dpr+s = / f0r djp S (1- 2rzs
f( t+ô
poly poly(mm R. 2)6.
Since this is true for all f, this shows uniform convergence of J f dic+s to ʃ duc In particular, this means it is also true of the supremum
lim W2(ee pc+6) I Vm lim sup f f d (mr M2-6) sup f(O, In pelpt dr < c edd 8-+0
(1 e1-e-2 poly R., 2).
18

---

Published as a conference paper at ICLR 2026
Theorem 4.5. Suppose Warm Start phase with T O (d log (og(<cLL(yyll Tws log kd, following which we run the Annealing Phase with 5 \//4,, This results T 1--1/00 9/10 satisfying
FI(pr188, No) S (8/22/33/10
Proof. We use the following from Appendix C of Balasubramanian et al. (2022). We have that < log P48/n is & Lipshitz
1 r66+5
KL (L(pis+ollm<o;w) (KL(alll18))
2 2/10
FI(prs+0, (48/m) 2
and
(L(posll((11)))1) - (L(pssl(468/1)
Pi8
Pi8 Mib/rs
P48/N
Bprs log
Eps log
Epis log
1(i-1)6/kx
1(1-1)8/fm
Putting these together we have
i6++8
+ Eps log 148/xc
2 3
Fi(pt, 148/1) di 422 do2
M(i-135/K
We can telescope this:
(1(600011))))81 (Loollll1---115 + Epgs log
Mab/11
116-116/H
Tuokf8
Fi(pes Mb8/K) di 422
18
Tosk/ō
Eps log Pi8/a
KL(pTllAT-o) KL (l). +
M(i-1)6/xx
Twsn/8
(1+1)6
Fl(pe, Mi8/N) dt 42 d8T w
2 2
We need bound Σ Epis log
Midte
Because Pis is m subgaussian, we have
PG 1)8/>"
Σ Epss log
P15//
E Epu log
M46/x
1(i-1)6/m
M(--
118/K
Oe log di S Σ /
15
Σ
E Ees
Ep, 10, log dt
(3-1)8/K
(3-1)6
i8/k
de
(1-1)8/m (1 21-0-2e-aao0 polyymm 9,, R, 2) dt
de (Tuust//8888//
11 e 2(1 ( poly(m, 9, 2)
poly:/
so if (Tmsk/00)8// 1:
d poly(m, (m, R, R,
(L(PT(ITTT)) +
167 (8/k)1146 + 4I2 W
TweN/8
1 1i+1)6
Σ
Fl(pes (i8/k) dt
in
1= To
19

---

Published as a conference paper at ICLR 2026
In LD, each of the Fl are computed with respect to the target distribution, and average iterate guarantee can be derived using the convexity of in its first argument. In our case, the second argument is changing over the course of the integral, second argument to p4n- We have
need "triangle inequality" to change the
Fl(p:, No) = Ep, V log P: V log Holl
_ p. V log Pt log Mell 11 + pEp, V log uoll
PPt (e) + pI,p, V log - V log Pog
2Fl pa) + poly(m, 2m, d)t²
We will use the bound
(++1)6
(1+1)6
FI(e,, p18ja) dt 2 (Tusk/6)
min < 2/8 x/8==]
Fi M1bjk) dt
2 16
(= k//8
2 (Twsk/0)
min
min
Fl(pt, M1b/x)
ie (T( /88)
get that there exists T E [(Twsk/0) ((T))))((TTO0)))) such that
(I M18/k)
KL KL [TT.)) +
Tée T8a (8/x)/-4a
poly (m 28
ws
8(T wx k/0)a
From approximate triangle inequality for FI, have that there exists (())) 25(T [//8 such that
FI(pT, Mo) < (F 148/x) + dpoly(m, () (TTTs//8)200 288)208' /
Suppose the warm start phase is run such that KL Law S Cun (recall that this takes time poly(1/ews)).
dr
Fl(pr; po) S
Ews
+
85-585550 poly(m, Ri, 2) 2 1--a poly(m, 2, 2)
To n a
T5e 10
+ dpoly(m, 2) 220 x 2822222
we take x 8-4, we have
21-26a
Fl(pr, Mo) <
Ews
d
K T5cx
+
T2-aa
4-50
+ 122a k
h0-3 poly(m, Ri L)
To ur R
Bm-T
Finally, setting
17/20, we have
21 21-25a
FIpz/00 S
K 2a-1
twe
+ d
Tho
+
Tl-aa
1. ws
4-5m
+
T2 S0-b we
K
poly(m, R. 2)
dk 1/18
Ewe
9/z0n 1oopooow////0 1/16
T 17/20 x 13/16
17/4
For our choice T, T Two we have ews < Overall the bound is
FI(PT, Mo) S dT x - 1/16 poly(m, 2.
Theorem 4.4. Suppose we run Warm Start phase with T O (dx (x((x<(()l)))c))) Tw. = log kd, following which we run the Annealing Phase with 8 = K -/4, This results T k -/10 satisfying
KL KL(P=11PTx/6) I poly(d, 1/
20

---

Published as a conference paper at ICLR 2026
Proof. From Lemma 4.3 using T
O(dxxlo((H)) (oooo(kkK(()))))
know that
(L [|Law(Xxx.) (X..)) Σ 1 Because lim,- He is strongly log- log-concave, as shown 4.3 for large T Tus we can sample from PTw.. efficiently. From Lemma B.2 we have
J. Two
de 1o lorllintue dt S $ (1- poly(m, R. L) dt
2e 25 poly(m, R)
(1 E 22)8
From here, we adapt the discretization analysis of Guo et al. (2024), We will repeat some of it below highlight just the differences.
First note that V log inherits Lipschitzness from V log Pt and VR, following Lemma C.9:
V log (x) V (v()l - V log (x)
(v)) + VR(y) VR(=)]
S (1 + Le -f + R) yll
By the corollary of Girsanov's Theorem referenced above, Lemma A.4, we see that
1
Two
(L(eellpt)
4 J.
(nd) (V v (as - (x,11 dt
Time
(m | (X,,) V ( di + J. lee de
Twn
KL Law (XT....)))
Two
E(ue)lle( dt poly(R, (nc) ||Xe - -Xaol2 dt + {. Two
We bound X, - XRs by
I' (V In ae + (Xx) dt + /2(t - mmmml
[|x - Xxa 12 = E(m))ll
7~7
k5
$ f" E E(m)) V poll ( (xx))
dt + d8
k5
We can bound (p.)
V In 2
[(
V log 11112 1|
v B Voggt + V
E p4
V log + E,,, VRI2 s poly(m, 2,
Putting these together, we have
Tu. J. Be (lle di + do d poly, 2)
(L(lll)e)) S KL(UT,, (aarrr,//LaWWpppp + (1 + poly( 2)))
+T urs 2)
An important observation here is that because v itself a Wasserstein gradient, the quantity 1 Epp [xx))2 dt depends inversely the scale that we use for time. Suppose reparame- terize time to go from 0 to Twxk, rather than 0 to T. Let A denote the integral f.t E(uo)lvx dt. Consider the change of variable = si,, so s goes from 0 to kT. Of course, we have the change of variables ds = k dt. but also v. = fur. Then we have ptan E (X.. ds
f (lee))l dt. Over all, we have from lemma B.2
KL( S (L (Law(Xr..)) (1 + Spoly(9 2)) d8 do"poly(m, R. 2) + Poly(R, L) < (L |La (TT..) (1 + poly(m, R, 2))
f
Tw. E ((m)llu(XX.)I) dt
de
Twsk
(1 e--3-
+ 2 poly(m, (m, R. 2) + 8 (oly(R, L)
< KL [|aW(( + df + 6) poly (m, R)
0 (d022 + +6)
K/8
21

---

Published as a conference paper at ICLR 2026
We will take ips (Tws ( x- 114, Then have
KL (Lips Pisgre/8) I (L [Law(XT..)) +
10 + O(dx + + x+)
d
Finally setting, T' = d²x²² log (KL((rll Tws log rd, we have Eus = 1 x we have
and choosing a
17
20
KL (Pipsn)))))) S0(Pkx =
IKL + FI] In algorithm 1, suppose run Warm Start phase with T O (d (ogx:x)()(()))) Tws log sd, following which we run the Annealing Phase with 8 k²/a, then there S O s/18), such that Prw/á simultaneously satisfies
*KL(urlPpnN')) & O(dx 1/*), which implies TV 14) S <O(Vdr 1/2
. FFI(p Ho) S O(dk 1/10)
For this choice of k, the algorithm has run time O(k²/))
Proof. All that is left to prove is that the run time is polynomial in R. Note that we run the warm start phase for log (L() /c iterations. Because y and Poo are log-concave, get <L(Yil(>>)) LSI(H())FF(( Pco) Odd). The annealing phase lasts k/ (155/4) time, since Tws = d/og.
C MISCELLANEOUS BOUNDS
The role of this section is to establish bounds on various quantities. The main one is the global bound on |0g log lel for > which we use in couple of places.
We use bound the Wasserstein derivative of the annealed path in Lemma B.2, and this used with Girsanov's Theorem to bound the KL drift between the annealed L.MC and the targets Theorem 4.4.
We also use it to bound the log μ4, log Moo for large & (Lemma C.7), which is used to show that we can transfer Fl bounds from log μrg to log 2o in Theorems 4.3, 4.5.
We will begin with a statement about the sub- gaussiaanttt of posteriors from sub gaussgassssnnnn priors.
Lemma C.1. Let μ denote the probability distribution of a sub-gaussian random variable with sub-gaussian parameter a. Let R 2 denote smooth convex function with minima & satisfying R(F) = O and 42R = RI. Let v & pe -It deeoot the posterior, and let Y ~ D. Then we have
v is sub- sub-gaussian with purameter 30 + x
2. |B, < 3
3. E, 2 < 2 (o +122)2d 3
Proof. 1. Let X ~ μ. One of the characterizations of a co-sub-gaussia random variable is
decay of the tail probabilities Pr[XT >1 * Let Y u. We have
(()e R(m) [u(z)e- ((a)
-R(a)
Pr a > 1 =
M(a) dr ds.
22

---

m2 and Published as a conference paper at ICLR 2026
The partition function can be lower bounded
I Ju(a)e R(x) dx 2
/
u(x))e - R(a)) dx
||||| <2m+:
min e e-m(x) / [1el/<2m+s 1a(x) dr |m+
152 R(x) Pr[x- < 2m r] 2 /2
The tail can now be upper bounded as
Pr[y a > 1 J.
LAT p(z)e R(x)
I [u(aje R(x) dx ds
s 20 1.
p(z) ds
JT Tamms
2 Pr[X] t S 4e 2mm
Of course this bound is vacuous until 4 (m
m
1, which happens when
2(m 2/2) m - log
m + 1/2) log 4).
When t m² ((m + +/2) + log we have 2(m + r/2)
t²
m²
(2[[m++/2))000- Overall, this shows that v is a sub- sabbsaassiin distribution with pa- rameter m 2mm + / + 2) & 3m(m + +/22)/RR
2. From Donsker- Varadhan, we have E,,, X S KL(Ma ll..) + log ex, From sub uub-gaussianity we have log Ep, S m2 The KL can be bounded as (Lelellp.) = -B R - log Bppe-
I log Epp
R 0
= log / e px(x) dr
S llog
e-(( pc(x) dx
||al|sm
< log e Rim² (1 (1-2e-1)
2 Rm 2 - 39mm²
Here the last inequality follows because R(x) I m 2 in the region ||>|||
Prp, (X > m2) S 21 from sub- uub--aussianity.
3. For simplicity we will consider the zero-mean case, the general, full second moment will be the sum of the centered second moment and the square of the mean. We have Var(Y a) < (a++2)) for all a. Now consider an orthonormal basis {az). summing the above relation for each of them we have
Σ Var(Y ax) = Σ EY 03)² = E, E( ai)
= E, Σ (Y a3a (Y) = =E, M(
(Y (TaaaaTT)
= EVT Σ ano =E
Finally, if E, Y + 0, we write
E, | R, Y E, 2 + ||E, 2 99 + +z/2)²d + +
23

---

Published as a conference paper at ICLR 2026
Lemma C.2. Let Pa by m-subgaussion. The law the OU process pt is subgaussian with norm me + (1-6 22)).
We also need the following, about moments of subgaussian random variables.
Lemma C.3. Let v denote a m subbuassssia distribution. For any satisfying f(x) S E.= a,11z|11.
have
Exf(2) -
(2m))
Proof. Follows from standard results subgaussian random variables.
Lemma C.4. The density Pt is upper bounded by
1 (2 21))//2
S
Proof. We have
pr(x) / ple'y)m---- - y)dy s sup ( p(e (2T(1 - e 2-21))2/2
v
Note: Of course, the density can blow up at é = (that is, for unsmoothed distributions), but once we add heat the density is bounded.
Lemma C.5. Let pe denote the law of Xt, where Xo Po and X, satisfies OU. Then we have
2
| logorg E
a||/=||
(1 e 2-2r3
1=0
For a; - poly(m, Ri, 2).
Proof. We will directly compute ò log p
0, log Pt = 02 log P: = Oep:
Lemma A.2(5)
Pt (pr V log 2t)
V
Fokker-Plaie Planck
Pr Ps 7
Vp
v log
A log Pt
Lemma A.2(4)
Pt
A Alog" Pt
V log
V log
Lemma A.2(5)
7
Voggp: Vlog
Alog
V lo
γ
24

---

Published as a conference paper at ICLR 2026
We have
A log
Ps
logpr
A Alog = V.
VPt
Lemma A.3(3)
7
Vpell Apr.
=d
Lemma A.2(4)
Pi
d (poe') -
V logg p:l2
Lemma A.2(3, 5)
(poct) * 71--222
[(poe') - 1)
(I-e 2022 I-c 27 7 20( dy
1ill
= d+
V log
Lemma A.3(2)
[ 1---0-2 (1) dy
21 21 d+ [(ooe)( y) ---
|111 ( dy
|/ lo
c(pcet) wh (v) dy
(pon (=-19)
Note that o refers to composition. As a shorthand, we will write cr(v) [(peet (== y) 1- (2) dy
Note that Cz(()) can be interpreted as posterior. Let denote the isometry Tn (v) = x y. then we can interpret ف p et o Tr prior, and y a likelihood. this stage, the following identity about the gradient will be useful
Vpt
V Po
Lemma A.2(5)
Pt
(poc') * Vi-a-
Lemma A.2(2)
(poct) 1---22
(poct) I-e-x 1---22
Lemma A.3(1)
(poet) 8/110-2
['ple'xx - -1)) -- n---z (v) dy
pplee(x v)) (y) dy
2 /
y cv)(v) dy
(6)
We have
A log
+
V log Pe 1|2
V log
V Vlog
7
21
/
d
(1a1l2ca()) dy
V log Pt V log
e
e1-e-2tj
2t
|
y.
e 2 - d
Cu(yy) dy
[1 - 11-e-220p 2-227
1 1 c
c 2t
/ (1x - y/1² x. (v x) + e 2 11) cx( dy
2 d +
(1 e1-e
Lets consider the terms in the integral.
f | cv)) dy
$ (| - y11 + ||x - Ey ()) Eywes
ca (v) dy
/ [[By-c2()VV cc) dy ||x Eyne(1)811
We will now Lemma C.1 to bound these terms.
The first is just the variance the posterior c,. Note that in the application of the lemma, the prior is Pt el Tyx which has mean (since pt has zero mean) and subgaussian parameter me-t, and the
25

---

Published as a conference paper at ICLR 2026
likelihood is " 21, which has minima at y z, and Hessian bounded by 9 C.I (3) we have
I-e- 2t By Lemma
f |yy cz)) dy s 1 e-
9 21
||,/| )²d
3
m mme +
m 21
2
1-e
21
The second is controlled by Lemma C.I (2), since E Ex-oroetor
X = We have that
e 4t
| Ey 2II < 9m² 1
(1 e1-e-21j0
For readability we will assume d >>> 1. Then we have
/ || v11 (x) dy S (1 e 2122 9m2de de 21 (3m² + ||=x1²))
1
Similarly
/ || - (V) dy - (ʃ || (111z-1/Pcc000 (x) dy
1/2
1
$
21 3me
3'm ' (3m² + 1x-1))
So we have
Pt
log
logp:!?
V logg: V Vlog7
(1 e1---2t- 2122 / (110 - u112 - x (y - x) + e "yy x) co(y) dy
d
+
e 2t
1
e 2t
12m 12m2de -t (3m² + +||+|1²) + / e eeyy xc2 (v) dy
d
+
e-2
(1-e-21))
e
12m de - (3m² + 11x
e-
d
log 2
from Equation (6)
21.
(1-e-21j
c-2
12m2de-t (3m² + (|x]122)
2
(d + |x]||| + -1(+))²
e1---20
(1 - 2-)
We can write this as 10, logpel S कT- Ei 0i ||| for dpoly(m, 2,
Lemma C.6. We have |å log mel S (1- Σ ai||=|| for a, = dpoly(m,, R)..
Proof. We have
J p = = log 0,R - log / Pie
D R
0, log μt
0, log
O S
I pr logple
= 0, log S -re-- 0 logp:
S DIe-R
5 O, logp: + Ey, Or log S O logpt + 1E,, 10, log
< (1 2114
e
Σ a:||=/|
C.5, C.3.
1=0
For a, = dpoly E, R)
Lemma C.7. Let Pr x p.e For T we have
--
2
loggr((s (x) - log Mso (1))
S
2
a |||
[1 -e- e e-2773
1=0
Where a; poly(m, d)
26

---

Published as a conference paper at ICLR 2026
Proof.
logg jrt
log Mox =
O, log sh dl $
|0, log uel dl
100
e_
<
as |=]l|]]
(1
e
T
10
eT
e
2
a:||z||1
2-21
1=0
Lemma C.8. Let pr) = Prfe-ta vI e 21 = It. 11 ~ } be the posterior of the OU
process conditioned future iterate. We have
Vog (x V log Po()
Proof. Please see Proposition 2.1 of (Bortoli et al., 2024).
Lemma C.9. Let Xo Po with V Po being &- L-pisshitz for & >>> 1, and let Xt denote the OU process run for time t, with law X, ~ Pr. Then V log Pt. is LiLishiitz.
D Fl IS NOT SUFFICIENT
Lemma D.1. Take two distributions "n, 72. Let "/1]B,()) (2) (respectively, (2) (a)) denote the distribu- tion conditioned on being within a ball of radius around the point x. Then we have
Exam KL (7118,(2) S FFl((n, 72).
Proof. For y smooth around x, 7(y) x(x) + (y- x) (xx) + Olyy x=(2),
/ [SSAce 7(8) dy (1(x) 0(e2) (Bl(B, (z))
and
7(x)
7xx)
(I) (NEB,(e) (v) dy (7(x) + vol(B) vol(B.)
Let Val }a denote the gradient with respect to a evaluated then we also have
V. log ().(()()))
1=--- 12--- Vz log (2) 1a=a - -v log
7(V) dy 1z=z= V x2x),
(EB((*)
so we have:
Ex-y, KL (1
= Exxwy Ey 718. - log (X)
= Exayy By
[log (X) (X + (Y - X)) log (2) (X + (Y - XX)]
-Exon BY
[log 71] (X) log (218 + (Y (V log (x) V V 72 (x)) (X))
(V
= Ex By By (x))
[Y - T 1o - V log (x)
< eExam By BY
||| log (x) V log (x)
Ex_, (oloon
V 1og (X) cFl(m. 72)
27

---

Published as a conference paper at ICLR 2026
Lemma D.2. Let
Po = 2 N0, + z (a
.
R(xx
||diag (00 x])
2n
Let 77 1+ 7. and let A = diag( (11, []) for any D. Then the posterior can be written as
aol (Adw No)
[1] Av
= oo (0, A, (1
with ou
and the distribution
lte 149
1 = 2 NO, (0, A.)) + 1 IN (AAy 1 Avy Avr)
satisfies
FI(M, p2) S 2x 22
Proof. Take the marginals of No, H6 onto the two coordinates (denoted "x" and "y").
1 1
1b.2 = 2 2 1)+
Po,z av, (1-,))(A11)
Pu,y N 2
1 An
An
++1 .1)
No, ao ao) n1)
1 1+1
We have FI(p mo) S FI po,z)) FI po.v). We can apply Lemma D.3 each of these marginals seperately to get
Fl(H): po) S (1- (o)= 2// 2 ~x2
Lemma D.3. Consider two mixtures of scalar Gaussians
#1 = a,N((. + (1- (1- #2 = (1=
with > a1 > 1/2 We have
(1 a1) (2) 3
)
Flyn, U2)
0/00
az2)
Proof. For convenience, we write 71 O( n2 N(3,o). Note that Vog m = -%/a, Voog T2 (z--8/a. We upper bound the FI(H1, (2) follows (this follows the argu- ment in Balasubramanian al. (2022) very closely, just with modified parameters)
1
log /1/22
(n2 (a1
VTL + (1-a1) (1-a))VT)) - p1 (a2 (1 vT22)
11/222
(a2
a1)
VTz
T2 VTT)
11P2
(V log मे V logmi) ) = (a2 a1) R1722 3
=(a2 - -a1)
p0p22 a
28

---

Published as a conference paper at ICLR 2026
so we have
FI( (2) = E[(V log " /12)
8²
(a2 )
dip
14
82
m dr
(02 (1
8
01 (a2
)
(027) + (1 a2 a2) (T2) dr
(A1TT) + (1 an (T2)
01)2 88
1
2
1
t dx
< (02 01)
de
(1-a1)a2(1 - (v2)
Ja5%/a TT
(1 - 0r xx) o2)2
x2///2 T22
(a2 01)²
B
T dx
"1 dr
(1
(22 02
1588/2
1T
xx28/2
122
Finally
e
J
1/5%/2 1//= V2TO 228/2
e
1
932/8
2
Sz58/2
This also holds for the other term
Sa2%/2
zi. Overall we have FI(H1, u2) S (02-01) 12 9
82 //02
(1-01](1-02)
02
29

---

Published as a conference paper at ICLR 2026
E SYNTHETIC SIMULATIONS
We have include some synthetic simulations of our method below. We use three priors for illustration (Figure 6), mixture of gaussians with 5 components, in them (similar to the discussion in Remark 4.7), and a pair of "moons". We illustrate the posterior
of vertical bars, some of which have gaps
sampling algorithm with two choices of measurement models, y = Ax + v for = (0] 0
0 (Figure
7) and also simply y = x + 7y for 7 ~ (0, st (Figure 9). The sampler of Algorithm 1, with i 400 and Tws/ 200 total noising levels is shown in Figures 8 and 10.
Figure 6: Three priors used in our experiments. A Mixture-of- prior on the left, "Vertical Bars" prior in the center (similar to Remark 4.7), and a "moons" prior on the right.
Figure 7: Likelihood functions used to define the posterior. R(x) = 9 Axx where A = 0 !
Essentially these are "noisy projections", somewhat analogous to an inpainting problem (one coordi- nate is seen, the other is not).
Foos stuage 113300
Figure 8: Resulting sampler, with 400. Shown are hex-jointplots of 10000 samples each.
30

---

Published as a conference paper at ICLR 2026
Figure 9: Likelihood functions used to define the posterior, corresponding to a noisy gaussian measurement R(x) R||=
Figure 10: Resulting sampler, run with и: = 400, with 200 levels noising (so a total of 80000 iterations). Shown are hex-jointplots of 10000 samples each.
We see that each of the modes are discovered (avoiding the mode collapse phenomemon associated with FI).
Figure 11: Here we demonstrate the consequences changing the variance of the noise used the measurement (which is related Ri in 4.2). For large values of R, the gap in the second and fourth vertical bars is much less stark, but the mass dedicated to these bars does not vanish.
31


Reviews:
[{"review_id": "froeqDDak0", "reviewer": "Reviewer_VVro", "summary": "This paper tackles the problem of posterior sampling: given a pretrained diffusion model that allows you to sample from a prior p(x), and given a negative log-likelihood function R(x), how does one sample from p e^-R?\n\nDoing Langevin Monte Carlo directly on the posterior runs into well-known problems with sampling from multi-modal distributions. It's well-known that in this setting, LMC will have quick convergence in FI but can have arbitrarily slow convergence in KL (e.g. due to well-separated modes). \n\nThis paper's contribution is proposing an annealed Langevin sampling algorithm that has both guarantees in FI with respect to the true posterior as well as, more significantly, guarantees in the KL with respect to a tilted version of the noised prior. It does so by separating the sampling process into two phases: a first phase where you create a warm start by generating a sample from \\gamma e^{-R} (standard Gaussian tilted by R). And then finally, a phase where you do annealed Langevin sampling: at each time step, you change the distribution gradually from \\gamma e^{-R} to p e^{-R}. Using standard discretization and telegraphing techniques, you can bound the KL.", "questions": "Could the authors expand on the nature and role of \\tau? (The noise level of the prior which gets the KL guarantees.)\n\nHow crucial is the convexity assumption on R(x) for the analysis?\n\nAny insight on the empirical performance of this algorithm in simple toy model settings?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The presentation is clear and the overview of the background is well-done. They do a good job of stating clearly the main contribution of the paper (dual guarantees of FI and KL)\n\n* The approach is novel. It seems more normal to start with the prior and incorporate likelihood information (as with Bayesian updating), or to incorporate prior and likelihood information simultaneously (as with standard classifier-free guidance). But incorporating the likelihood information first and then incorporate the prior is different.\n\n* They managed to get a KL guarantee in a setting where KL guarantees have been elusive.", "weaknesses": "* Lack of empirical validiation. Specifically, they have a guarantee with respect to a noised version of the prior, but it's unclear how significant that noising is for degrading the quality of the sample (e.g. the perceptual quality in image diffusion models)\n\n* Related to the above, but while there are polynomial guarantees in d and 1/\\epsilon, the possiblity of large hidden constants could be relevant to applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vIvoaPOsaD", "reviewer": "Reviewer_nG4D", "summary": "The paper studies approximate posterior sampling using a pre-trained score model for the prior. The authors propose an algorithm based on Annealed Langevin Monte Carlo (ALMC) and analyze its convergence. The main contribution is a theoretical guarantee that the algorithm can, in polynomial time, produce samples from a distribution that is close to the posterior of a noised prior in KL divergence and close to the true posterior in Fisher Divergence. This result is presented as a way to circumvent the known computational hardness of exact posterior sampling.", "questions": "N/A", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The authors provide a detailed and mathematically rigorous analysis for approximate posterior sampling using a pre-trained score model.\n2. The paper does a good job of positioning itself relative to recent negative results (Gupta et al., 2024) and explaining the limitations of existing approaches.\n3. The problem of developing provable methods for posterior sampling with diffusion models is of high importance to the community.", "weaknesses": "1.  The paper makes no attempt to bridge the gap between its theoretical findings and practical applications. There are no experiments to illustrate the behavior of the algorithm or the meaning of the theoretical bounds. The claim that the method solves a practical problem is therefore not empirically supported.\n\n2. The practical relevance of the results is limited by strong assumptions. For example, the requirement that the log-likelihood `R(x)` be convex is a major restriction that excludes many inverse problems of practical interest (e.g. phase retrieval). The paper doesn't sufficiently discuss the implications of this assumption or how the guarantees might change without it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3ocUCQ2XaD", "reviewer": "Reviewer_aCxD", "summary": "This paper proposes a novel approximate posterior sampling framework for diffusion models, aimed at improving inference efficiency while preserving sample quality. The method reformulates the posterior inference as an optimization problem and derives an approximate sampler that leverages diffusion score information with reduced computational cost. Theoretical analysis supports the validity of the approximation, and experiments show strong empirical performance on benchmark datasets.", "questions": "NA. See the weaknesses above.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a well-written and technically sound paper with clear motivation, strong theoretical grounding, and solid empirical evidence. The methodology is both elegant and practical, providing a meaningful contribution to improving inference efficiency in diffusion models. The paper is well-organized and easy to follow, with a consistent logical flow from theoretical derivation to experimental validation.", "weaknesses": "I have only two minor concerns that do not undermine the overall quality of the paper. \n\n1. At line 159, the authors claim that two processes have the same joint distribution. However, this statement may not be strictly accurate: one process is a Markov process while the other is an 'inverse' Markov process, and although they share the same marginal distribution at each fixed time $t$, their joint distributions are not identical. This point should be clarified for mathematical precision.\n\n2. At line 235, two distinct notations for score functions are introduced without explicit definitions. Although the meaning becomes clear later in the text, it would improve readability and self-containment to define them formally when first introduced.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lVBwSlISJB", "reviewer": "Reviewer_qQ6U", "summary": "The paper introduces an algorithm for posterior sampling under oracle access to the score function of the prior distribution along the OU process. Their key insight is using annealed Langevin dynamics to represent the particle-level dynamics of the curve of measures $(\\mu_t \\propto p_t e^{-R_y})_{t \\in [0,1]},$ where $p_t$ is the annealed prior and $R$ is the likelihood, and a rate parameter $\\kappa$ is introduced to control the speed at which this path is traversed. Under fairly standard assumptions, they bound the Fisher information between the generated distribution and the true posterior, as well as the KL divergence between the generated distribution and a noisy version of the prior. They demonstrate in a specific example that, due to the KL divergence guarantee, their algorithm does not suffer from mode collapse issues that Fisher information guarantees are susceptible to, and they argue that sampling from a noisy posterior is the best that can be hoped for in the worst case.", "questions": "- I have some questions about the example in Section 4.1 involving the Gaussian mixture prior and linear inverse problem. When describing the failure of the Fisher information, you take $\\lambda \\rightarrow \\infty$, but when describing the ability of your algorithm to overcome mode collapse, you fix $\\lambda = 1/\\eta.$ Is this choice without loss of generality? Also, it seems that in this example, the posteriors $\\mu_t$ converge to $\\mu_0$ in KL divergence, which will not always be the case. In these more general cases, do you still expect your algorithm to overcome the mode collapse issue?\n- I don't quite understand precisely how you apply Girsanov to prove Theorem 4.4, could you clarify that in more detail? From the definition of annealed LD, I don't see where the velocity field $v_t$ shows up. I assumed that this followed from rewriting the continuity equation to include a diffusive term, but I am not completely sure. \n- In the proof of Lemma B.2, it seems the parameters $\\alpha$ and $\\beta$ are chosen sub-optimally (if I understand correctly, $\\alpha$ is the convexity parameter of the potential and $\\beta$ is the Lipschitz constant of the score). Since the likelihood is convex, can't you simply take $\\alpha = 1$? Also, it seems $\\beta$ can be taken to be $1 + R$ rather than $\\sqrt{d} + R$, since you only need an operator norm bound on the Hessian.\n\nOther questions/typos:\n- In Assumption 4.1, you have items i) and iii). Perhaps the first assumption is supposed to be broken into two parts, with the second being the Lipschitz score assumption?\n- In Step 3 of the proof of Lemma B.2, starting in the 4th equality, it seems that you drop the term $\\textrm{KL}(\\mu_{T_{ws}} \\parallel \\mu_{\\infty})$, but shouldn’t this term appear in the final bound? I don’t think it changes much for the final bound, since it only contributes a factor of $\\epsilon^2$ under your choice of $T_{ws}$.\n- In Step 3 of the proof of Lemma B.2, I think the 5th equality (taking the sup over $x$) should be an inequality.\n- In line 888, “We have $\\lim_{\\delta \\rightarrow 0} \\int f d(\\mu_t - \\mu_{t-\\delta}) =$...” I think you are missing a factor of $1/\\delta$. Also, here you should justify exchanging the limit and supremum.\n- In the proof of Lemma B.3, I think you should have $f \\leq f(0) + \\|x\\|$ instead of $f \\leq \\|x\\|$. Also, I don't understand the reduction to non-negative $f$, because the class of Lipschitz functions includes unbounded functions (so you cannot simply subtract off a constant). It doesn't even seem like you need $f$ to be positive in the proof.\n- In the proof of Theorem B.4, line 906, I think there is a typo in the integral $\\int_{i \\delta}^{i \\delta + \\delta} \\textrm{FI}(\\rho_{I\\delta + \\delta} \\parallel \\mu_{I\\delta + \\kappa})$ (what variable is being integrated?).\n- Typo at the top of page 19, $L^2$ should be a script 'L'.\n- On page 19, it seems like there is some text missing between the inequalities in lines 978 and 982, please fill those details in.\n- At the end of the proof of Theorem 4.5 on page 19, you have a bound on the Fisher information between the averaged $\\rho_t$ and $\\mu_0$. How do you translate this into a bound on a single iterate? You mention earlier about using convexity of the Fisher information in the first argument, but this gives you an inequality in the wrong direction.\n- In the proof of Theorem 4.4, starting at line 1008, I think $\\nabla \\mu_{k \\delta}$ is supposed to be $\\nabla \\log \\mu_{k \\delta}$.\n- On page 20, in the proof of Theorem 4.5, you eventually throw away the $O(\\delta)$ term in the bound, but shouldn't this term dominate the $O(d \\delta^2)$ term?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- To the best of my knowledge, this paper is the first to provably sample from the (approximate) posterior in polynomial time at this level of generality. The proof is interesting and a nice synthesis of different ideas.\n- The main text of the paper is well-written and the authors made a good effort to explain the high-level ideas of their algorithm.", "weaknesses": "- It is not clear whether the rate achieved is optimal (I would guess not), and the iteration complexity is not carefully tracked.\n- The proofs in the appendix have many typos/errors and many details are not completely filled in. This makes it difficult to assess the contribution.\n- Even though the primary contribution of the paper is the theory, I still would have liked to have seen a couple more experiments to demonstrate the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)