# Smoothed Score Queries and the Complexity of Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 30 references that are in the map.
- First posted on arXiv 26 May 2026.

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024)
- [Instance-dependent Convergence Theory for Diffusion Models](https://mlsanity.com/paper/2410.13738/) (2024)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Optimal Convergence Analysis of DDPM for General Distributions](https://mlsanity.com/paper/2510.27562/) (2025)
- [High-accuracy sampling for diffusion models and log-concave distributions](https://mlsanity.com/paper/2602.01338/) (2026)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Sublinear iterations can suffice even for DDPMs](https://mlsanity.com/paper/2511.04844/) (2025)
- [Query Lower Bounds for Diffusion Sampling](https://mlsanity.com/paper/2604.10857/) (2026)

## Abstract (arXiv)

We study the query complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic (√kappa) dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query smoothed scores, namely gradients of the logarithms of the Gaussian-convolved densities. For a Gaussian target with precision matrix (Lambda), a smoothed-score query at noise level (τ) gives access to the resolvent ((Lambda+τ-1I)-1). Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with q=O!left(bigl(logkappa+log(e√ d/δrm TV)bigr)log(e√ d/δrm TV)right) smoothed-score queries for total variation error (δrm TV), improving the condition-number dependence from (√kappa) to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-score answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in (kappa); in particular, for fixed dimension and accuracy, the bit complexity is (O(log2kappa)). To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an (Omega(logkappa)) lower bound on the required gradient information. Together, these results identify smoothed scores as a provably more informative oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.