mlsanityData to 7 Oct 2026

Diffusion Posterior Sampling is Computationally Intractable

arXiv 2402.12727 ↗First posted 20 Feb 2024cs.LG cs.AI math.STcited by 20

On the map: Diffusion models → Inverse problems and image restoration

Abstract (arXiv)

Diffusion models are a remarkably effective way of learning and sampling from a distribution p(x). In posterior sampling, one is also given a measurement model p(y mid x) and a measurement y, and would like to sample from p(x mid y). Posterior sampling is useful for tasks such as inpainting, super-resolution, and MRI reconstruction, so a number of recent works have given algorithms to heuristically approximate it; but none are known to converge to the correct distribution in polynomial time. In this paper we show that posterior sampling is computationally intractable: under the most basic assumption in cryptography -- that one-way functions exist -- there are instances for which every algorithm takes superpolynomial time, even though unconditional sampling is provably fast. We also show that the exponential-time rejection sampling algorithm is essentially optimal under the stronger plausible assumption that there are one-way functions that take exponential time to invert.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Placed in Inverse problems and image restoration, one of 14 directions in Diffusion models. Builds on 22 of its 30 references that are in the map. First posted on arXiv 20 Feb 2024.

Builds on

22 of 30 references.

Closest ancestors · 2

Same direction, newest first

  1. 2022Diffusion Posterior Sampling for General Noisy Inverse Problems29 Sep
  2. 2022Denoising Diffusion Restoration Models27 Jan

Other references · 20

  1. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  2. 2021High-Resolution Image Synthesis with Latent Diffusion Modelscited by 18,694
  3. 2020Denoising Diffusion Implicit Modelscited by 9,655
  4. 2021Diffusion Models Beat GANs on Image Synthesiscited by 8,185
  5. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  6. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,539
  7. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  8. 2023Stable Video Diffusion: Scaling Latent Video Diffusion Models to Large Datasetscited by 2,526
  9. 2022RePaint: Inpainting using Denoising Diffusion Probabilistic Modelscited by 1,419
  10. 2020DiffWave: A Versatile Diffusion Model for Audio Synthesiscited by 1,339
  11. 2020WaveGrad: Estimating Gradients for Waveform Generationcited by 620
  12. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
8 more
  1. 2021Robust Compressed Sensing MRI with Deep Generative Priorscited by 284
  2. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localizationcited by 230
  3. 2022Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problemcited by 229
  4. 2023Practical and Asymptotically Exact Conditional Sampling in Diffusion Modelscited by 218
  5. 2021SNIPS: Solving Noisy Inverse Problems Stochasticallycited by 191
  6. 2020Generative Modeling with Denoising Auto-Encoders and Langevin Samplingcited by 118
  7. 2021Fairness for Image Generation with Uncertain Sensitive Attributescited by 31
  8. 2022Finite-Sample Maximum Likelihood Estimation of Locationcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 7; 2026: 6.

20 papers.

Sort:

By area:

  1. 2024A Survey on Diffusion Models for Inverse Problemscited by 173
  2. 2024Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstructioncited by 73
  3. 2024What does guidance do? A fine-grained analysis in a simple settingcited by 45
  4. 2026Latent Forcing: Reordering the Diffusion Trajectory for Pixel-Space Image Generationcited by 33
  5. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
  6. 2024Posterior Sampling with Denoising Oracles via Tilted Transportcited by 12
  7. 2025InvFusion: Bridging Supervised and Zero-shot Diffusion for Inverse Problemscited by 9
  8. 2024Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplerscited by 6
  9. 2025ReGuidance: A Simple Diffusion Wrapper for Boosting Sample Quality on Hard Inverse Problemscited by 5
  10. 2026Steering diffusion models with quadratic rewards: a fine-grained analysiscited by 5
  11. 2026Provable diffusion-based posterior sampling for linear inverse problems via DDIMcited by 4
  12. 2025Efficient Approximate Posterior Sampling with Annealed Langevin Monte Carlocited by 3
8 more
  1. 2025Bigger Isn't Always Better: Towards a General Prior for Medical Image Reconstructioncited by 2
  2. 2025PAINT: Parallel-in-time Neural Twins for Dynamical System Reconstructioncited by 2
  3. 2026Trajectory Forcing: Structure-First Generation with Controllable Semantic Trajectoriescited by 2
  4. 2024Diffusion priors for Bayesian 3D reconstruction from incomplete measurementscited by 1
  5. 2025Diffusion Probabilistic Generative Models for Accelerated, in-NICU Permanent Magnet Neonatal MRIcited by 1
  6. 2025Exploiting the Exact Denoising Posterior Score in Training-Free Guidance of Diffusion Modelscited by 1
  7. 2026Diffusion-Based Posterior Sampling: A Feynman-Kac Analysis of Bias and Stabilitycited by 1
  8. 2026The tractability landscape of diffusion alignment: regularization, rewards, and computational primitivescited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics
  2. 2026Analyzing and Guiding Zero-Shot Posterior Sampling in Diffusion Models
  3. 2026Lower Bounds for Parallel Diffusion Sampling
  4. 2023Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models
  5. 2025Solving Diffusion Inverse Problems with Restart Posterior Sampling
  6. 2024Diffusion Posterior Proximal Sampling for Image Restoration
  7. 2025A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm
  8. 2026High-accuracy and dimension-free sampling with diffusions