Research map / Learning theory and algorithms / Sample complexity
Diffusion Posterior Sampling is Computationally Intractable
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that posterior sampling from diffusion models under linear measurements is computationally intractable under one-way function assumptions, while showing rejection sampling is near-optimal under stronger assumptions.
Problem
Whether efficient, provably correct posterior sampling (e.g., for inpainting, super-resolution, MRI) is possible given only approximate smoothed scores of a diffusion model, rather than heuristic approximations that lack guarantees.
Approach
Constructs a well-modeled distribution (scores representable by a polynomial-size ReLU network) that encodes a one-way function's output in the phase of a discretized Gaussian, so any posterior sampler from linear noisy measurements would invert the one-way function; complemented by an upper bound showing rejection sampling takes (O(1)/(beta sqrt(delta)))^m time.
Key results
- Under the assumption that one-way functions exist, there is a 10-well-modeled distribution and linear measurement model for which (1/10,1/10)-posterior sampling requires superpolynomial time in d, while unconditional sampling is polynomial.
- If one-way functions requiring 2^{Omega(m)} time to invert exist, posterior sampling takes 2^{Omega(m)} time, and rejection sampling runs in 2^{O(m log log d)} poly(d) time, so it is near-optimal.
- Rejection sampling of the diffusion process is a (1/d^C, delta)-posterior sampler taking poly(d)(O(1)/(beta sqrt(delta)))^m time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use rejection sampling with unconditional diffusion samples for posterior sampling | Well-modeled distributions with linear measurements · Linear measurement model | runtime: \poly(d)(\frac{O(1)}{\beta\sqrt{\delta}})^m | Mixed |
| Require accurate posterior sampling for the constructed one-way-function distribution | Any posterior sampling algorithm · Constructed distribution, m > d^{0.01} | runtime: superpolynomial time in d | Hurt |
| Require accurate posterior sampling under the exponential-hardness assumption | Any posterior sampling algorithm · Constructed distribution, m ≤ O(d) | runtime: at least 2^{\Omega(m)} time | Hurt |
| Use the discretized reverse diffusion process for unconditional sampling | Well-modeled distributions · Unconditional sampling | runtime: \poly(d) time | Helped |
Surprising findings
- Posterior sampling is intractable even when the smoothed scores are well approximated by polynomial-size neural networks and unconditional sampling is provably fast.
Limitations
- Results are worst-case over distributions; the hard instance is an artificial, non-natural distribution derived from a one-way function.
- Relies on cryptographic assumptions (existence of one-way functions, or exponentially hard one-way functions) rather than unconditional proofs.
- Does not address whether natural image distributions or heuristic posterior samplers succeed in practice.
Experimental setup
Baselines: rejection sampling
Builds on: score-based generative modeling Langevin dynamics rejection sampling
Closest papers by meaning
- Analyzing and Guiding Zero-Shot Posterior Sampling in Diffusion Models (NeurIPS 2026 · similarity 0.88)
- Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics (NeurIPS 2025 · similarity 0.87)
- Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction (NeurIPS 2024 · similarity 0.87)
- Ambient Diffusion Posterior Sampling: Solving Inverse Problems with Diffusion Models Trained on Corrupted Data (ICLR 2025 · similarity 0.87)
- Adapt and Diffuse: Sample-adaptive Reconstruction via Latent Diffusion Models (ICML 2024 · similarity 0.87)
- Provable Posterior Sampling with Denoising Oracles via Tilted Transport (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.