# Diffusion Posterior Sampling is Computationally Intractable

arXiv: https://arxiv.org/abs/2402.12727 · HTML: https://mlsanity.com/paper/2402.12727/

## Key facts

- Cited by 20 papers in the map (data through 14 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.

## Placed in

- Diffusion models / [Inverse problems and image restoration](https://mlsanity.com/diffusion/inverse-problems-and-image-restoration/)

## Builds on (most cited first, 22 of 22)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Stable Video Diffusion: Scaling Latent Video Diffusion Models to Large Datasets](https://mlsanity.com/paper/2311.15127/) (2023)
- [RePaint: Inpainting using Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2201.09865/) (2022)
- [Diffusion Posterior Sampling for General Noisy Inverse Problems](https://mlsanity.com/paper/2209.14687/) (2022)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [Denoising Diffusion Restoration Models](https://mlsanity.com/paper/2201.11793/) (2022)
- [WaveGrad: Estimating Gradients for Waveform Generation](https://mlsanity.com/paper/2009.00713/) (2020)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problem](https://mlsanity.com/paper/2206.04119/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Practical and Asymptotically Exact Conditional Sampling in Diffusion Models](https://mlsanity.com/paper/2306.17775/) (2023)
- [SNIPS: Solving Noisy Inverse Problems Stochastically](https://mlsanity.com/paper/2105.14951/) (2021)
- [Generative Modeling with Denoising Auto-Encoders and Langevin Sampling](https://mlsanity.com/paper/2002.00107/) (2020)
- [Fairness for Image Generation with Uncertain Sensitive Attributes](https://mlsanity.com/paper/2106.12182/) (2021)
- [Finite-Sample Maximum Likelihood Estimation of Location](https://mlsanity.com/paper/2206.02348/) (2022)

## Built on by (most cited first, 20 of 20)

- [A Survey on Diffusion Models for Inverse Problems](https://mlsanity.com/paper/2410.00083/) (2024)
- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [What does guidance do? A fine-grained analysis in a simple setting](https://mlsanity.com/paper/2409.13074/) (2024)
- [Latent Forcing: Reordering the Diffusion Trajectory for Pixel-Space Image Generation](https://mlsanity.com/paper/2602.11401/) (2026)
- [Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel](https://mlsanity.com/paper/2406.00924/) (2024)
- [Posterior Sampling with Denoising Oracles via Tilted Transport](https://mlsanity.com/paper/2407.00745/) (2024)
- [InvFusion: Bridging Supervised and Zero-shot Diffusion for Inverse Problems](https://mlsanity.com/paper/2504.01689/) (2025)
- [Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers](https://mlsanity.com/paper/2410.13746/) (2024)
- [ReGuidance: A Simple Diffusion Wrapper for Boosting Sample Quality on Hard Inverse Problems](https://mlsanity.com/paper/2506.10955/) (2025)
- [Steering diffusion models with quadratic rewards: a fine-grained analysis](https://mlsanity.com/paper/2602.16570/) (2026)
- [Provable diffusion-based posterior sampling for linear inverse problems via DDIM](https://mlsanity.com/paper/2607.19333/) (2026)
- [Efficient Approximate Posterior Sampling with Annealed Langevin Monte Carlo](https://mlsanity.com/paper/2508.07631/) (2025)
- [Bigger Isn't Always Better: Towards a General Prior for Medical Image Reconstruction](https://mlsanity.com/paper/2501.07376/) (2025)
- [Exploiting the Exact Denoising Posterior Score in Training-Free Guidance of Diffusion Models](https://mlsanity.com/paper/2506.13614/) (2025)
- [PAINT: Parallel-in-time Neural Twins for Dynamical System Reconstruction](https://mlsanity.com/paper/2510.16004/) (2025)
- [Diffusion-Based Posterior Sampling: A Feynman-Kac Analysis of Bias and Stability](https://mlsanity.com/paper/2605.06538/) (2026)
- [The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives](https://mlsanity.com/paper/2605.11361/) (2026)
- [Trajectory Forcing: Structure-First Generation with Controllable Semantic Trajectories](https://mlsanity.com/paper/2606.22527/) (2026)
- [Diffusion priors for Bayesian 3D reconstruction from incomplete measurements](https://mlsanity.com/paper/2412.14897/) (2024)
- [Diffusion Probabilistic Generative Models for Accelerated, in-NICU Permanent Magnet Neonatal MRI](https://mlsanity.com/paper/2505.15984/) (2025)

## 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.