High-accuracy sampling for diffusion models and log-concave distributions

FORS: Achieving Exponential Precision in Diffusion Sampling Without Density Oracles

High-accuracy sampling for diffusion models and log-concave distributions

2026-02-01

Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin

Summary

Problem

Method

Results

Takeaways

Abstract

The paper introduces First-Order Rejection Sampling (FORS), a meta-algorithm that achieves $δ$ -error in diffusion model sampling using only polylog(1/δ) steps. By leveraging score estimates in $L_{2}$ and avoiding zeroth-order (density) evaluations, it establishes new SOTA complexity bounds of $i l d e O (d_{⋆} e x t p o l y l o g (1/ δ))$ under minimal assumptions.

TL;DR

A new meta-algorithm called First-Order Rejection Sampling (FORS) allows diffusion models to reach target accuracy $δ$ in $e x t p o l y l o g (1/ δ)$ steps. Unlike prior high-accuracy methods that needed log-density evaluations (zeroth-order), FORS works strictly with score estimates (first-order), theoretically upgrading diffusion models from polynomial to exponential convergence in precision.

The "Accuracy Floor" Problem

In the world of Generative AI, diffusion models are workhorses, but they have a hidden weakness: discretization error. Most samplers (DDPM, DDIM, Euler-Maruyama) treat the reverse process as a Stochastic Differential Equation (SDE). When you discretize time to speed up inference, you introduce a bias that scales poorly with the required precision.

To get a very accurate sample (small $δ$ ), you usually need a massive number of steps (e.g., $1/ δ^{2}$ ). While higher-order solvers exist, they still don't break the polynomial barrier. Scientists previously thought that to get $e x t p o l y l o g (1/ δ)$ accuracy, you had to evaluate the density function—a "zeroth-order" query that is practically impossible for complex models like Stable Diffusion.

Methodology: The Bernoulli Factory Meets Path Integrals

The authors solve this by reframing the sampling problem not as an SDE to be solved, but as a series of Gaussian Tilts to be sampled via rejection sampling.

1. The Physical Intuition

Rejection sampling usually requires knowing the ratio of two densities: $p (x) / q (x)$ . If we only have the score (the gradient $ab l a lo g p$ ), we don't know the absolute value of $p (x)$ . However, we can represent the log-density difference as a path integral: $f (x) = E_{y \sim e x t U ni f ([0, x])} [x f^{'} (y)]$ This means we can get an unbiased estimate of the log-density ratio using only the score.

2. The FORS Algorithm

The core of the paper is Algorithm 1, which uses a "Bernoulli Factory" technique. Instead of calculating the acceptance probability $α$ , it samples a random number of score evaluations to decide if a point is accepted. As long as the estimator is bounded within $[- B, B]$ , the algorithm is guaranteed to sample from the exact target distribution.

FORS Architecture Placeholder (Note: Algorithm 1 in the paper details the Poisson-sampled acceptance mechanism.)

Breaking the Dimension Barrier

One of the most impressive feats of this paper is its handling of high-dimensional data. Standard sampling often suffers from the "Curse of Dimensionality."

The authors show that the complexity scales with the intrinsic dimension $d_{⋆}$ , not the embedding dimension $d$ .

Low-Dimensional Manifolds: If your images lie on a 100-dimensional manifold inside a 1-million-pixel space, the complexity respects the 100, not the million.
Quantifiable Gains: They achieve a bound of $O (d_{⋆} lo g^{3} (1/ δ))$ , which is a massive leap over the previous best of $i l d e O (d / δ)$ .

Experimental Insights Placeholder (Note: Refer to Section 4.2 of the paper for the quantitative comparison against prior SOTA like Chen et al. and Li et al.)

Impact on Log-Concave Sampling

The paper doesn't just help Diffusion; it solves a long-standing problem in Log-Concave Sampling. By plugging FORS into the Proximal Sampler framework, they created the first high-accuracy sampler that only needs gradients. Previously, if you wanted high accuracy for a log-concave distribution, you had to use Metropolis-Hastings (requiring density) or accept a bias. FORS gives you the best of both worlds: high accuracy and gradient-only access.

Critical Analysis & Future Outlook

While this is a theoretical landmark, a few hurdles remain:

Strict Bounds: FORS requires the estimator to be bounded by a constant $B$ . In practice, score estimates can be noisy or outliers can occur, potentially leading to high rejection rates.
Effective Schedules: The "High-Accuracy" nature kicks in most effectively at very low $δ$ . For "good enough" image generation (high $δ$ ), traditional solvers might still be faster due to the overhead of the rejection steps.

Conclusion: This paper changes the "lower bound" conversation. It proves that the step-accuracy trade-off in diffusion models is not a fundamental law of nature, but a limitation of our current SDE-based algorithms. We are now entering the era of first-order high-accuracy sampling.

Find Similar Papers

Try Our Examples

Search for recent papers that apply rejection sampling or MCMC-based correction layers to accelerate the inference of pre-trained diffusion models.
Which paper first introduced the "Bernoulli Factory" for SDE simulation, and how does the FORS algorithm's use of path integrals specifically improve upon those earlier methods?
Investigate whether the "intrinsic dimension" (d_star) dependency introduced in this paper has been validated empirically in high-resolution image generation tasks where data lies on low-dimensional manifolds.

Contents

FORS: Achieving Exponential Precision in Diffusion Sampling Without Density Oracles

1. TL;DR

2. The "Accuracy Floor" Problem

3. Methodology: The Bernoulli Factory Meets Path Integrals

3.1. 1. The Physical Intuition

3.2. 2. The FORS Algorithm

4. Breaking the Dimension Barrier

5. Impact on Log-Concave Sampling

6. Critical Analysis & Future Outlook