Sharp Lower Bounds for Parallel Log-Concave Sampling

Introduction

How much sequential computation is necessary to sample from a high-dimensional probability distribution? Many sampling algorithms generate a trajectory whose successive steps depend on earlier oracle responses. Parallel sampling algorithms seek to shorten this dependence by evaluating the target potential and its derivative(s) at many points simultaneously. For smooth strongly log-concave distributions, recent algorithms achieve polylogarithmic depth [2], and subsequently logarithmic depth [31], using polynomially many queries per round. This raises a converse question: can larger batches reduce the number of rounds further, or is logarithmic depth an intrinsic requirement of sampling?

We resolve this question for smooth strongly log-concave distributions with fixed condition number $\kappa\in(1,\infty)$. For any fixed $\delta\in(0,1)$, any parallel sampler achieving constant TV error using $\exp(d^{1-\delta})$ many queries per round requires $\Omega_{\kappa,\delta}(\log d)$ rounds in the worst case, matching the $O_{\kappa}(\log d)$ upper bound of [31]. The lower bound holds even when the mode is known, the potential is $C^\infty$, and each query returns all derivatives of the potential. We also characterize the tradeoff between the number of rounds and the number of queries per round for centered Gaussian targets. In this case, we identify an explicit threshold at which the necessary batch size falls from a positive power of the dimension to a constant.

Problem setting. We consider sampling from a probability distribution $\pi$ on $\mathbb{R}^d$ with density proportional to $e^{-V}$, given oracle access to the potential $V$ and its gradient. Our regularity assumptions are as follows:

We also assume that the mode of $\pi$ is known, both to provide a starting point for sampling algorithms and to separate the difficulty of sampling from that of minimizing $V$. By translating the target and adding a constant to $V$, we may impose the following normalization:

Assumptions 1.1 and 1.2 yield the standard setting of smooth strongly log-concave sampling. For a general treatment of log-concave sampling, see the textbook [10].

Parallel oracle model. In each round, an algorithm submits a batch of query points and receives the corresponding values of $(V,\nabla V)$. The batch may depend on the algorithm’s internal randomness and all responses from previous rounds, but its queries are chosen before any response from the current round is received. The algorithm then outputs a random point whose law must approximate $\pi$ in total variation (TV) distance, uniformly over the target class.

We call the number of rounds the depth and the maximum number of queries in any round the width. Computation between oracle calls is unrestricted: our lower bounds concern the information available to the sampler and apply to arbitrary randomized algorithms without requiring a particular dynamics, discretization, or particle representation.

Optimal depth for parallel log-concave sampling. Parallel simulation methods have substantially reduced the adaptive complexity of sampling [2, 31]. The following consequence of the parallel Picard method of Zhou and Sugiyama gives the upper bound relevant to our setting.¹

Our main result shows that the dimension dependence of this round bound is optimal, even if the algorithm is allowed a much larger polynomial query budget:

Remark 1.5. The constants $0.01$ and $0.99$ are illustrative and can be taken arbitrarily close to $0$ and $1$, respectively, at the cost of changing the hidden constants. Similarly, the condition number $\kappa$ can be taken arbitrarily close to $1$. The hard instances have $C^{\infty}$ potentials, and the same lower bound holds when each query returns the potential and all of its derivatives at the queried point.

Together, these results establish a worst-case round complexity of $\Theta_{\kappa}(\log d)$ for fixed-$\kappa$ log-concave sampling with polynomially many queries per round. This contrasts with Gaussian targets, which can be sampled exactly in one parallel round of $d$ gradient queries. Theorem 1.4 therefore yields a separation between log-concave and Gaussian sampling in round complexity, which complements the separation in total query complexity established concurrently by Zhou and Suzuki [33].

Theorems 1.3 and 1.4 also identify two regimes at the logarithmic round scale. If the sampler uses $T=\lceil c\log d\rceil$ rounds for a fixed $c\in(0,\infty)$, then:

• For any $c<\zeta(\kappa)$, Theorem 1.4 rules out sampling with $\operatorname{poly}(d)$ queries per round. Informally, this means that a successful sampler cannot improve on a brute force solution (e.g. discretizing $\mathbb{R}^{d}$ and reconstructing $V$), see Remark 4.6.

• If $c$ is sufficiently large, Theorem 1.3 provides a sampler using only $\mathcal{O}_{\kappa}(d\log d)$ queries per round. The sequence of interactions is long enough to allow a query-efficient algorithm.

Thus, allowing more rounds changes whether an efficient sampler exists. This raises a finer question: where does this transition occur, and how does the required number of queries decrease as the number of rounds approaches the transition? The width lower bound (4) suggests a stretched-exponential tradeoff between depth and width, but it is unknown if this is correct or how the true threshold for $c$ changes as $\kappa$ increases.

A sharp depth-width tradeoff for Gaussian sampling. We investigate this question in the Gaussian setting, where we can identify an explicit threshold and characterize the tradeoff leading up to it. As mentioned, centered Gaussians can be sampled using one round of width $d$; this is fully parallel but wasteful, and can be considered the brute force approach. Indeed, such targets can be sampled using $O_{\kappa}(\log d)$ rounds of width $1$ [8, 32].

Our second result determines how additional depth reduces the required width. To state it, normalize the spatial scale and define

Throughout, $\log$ denotes the natural logarithm, tildes in asymptotic notation suppress factors polylogarithmic in $d$.

Remark 1.7. The critical number of rounds is also $c_{\star}(\kappa)\log d$ in the regime where $(\kappa,d)$ grow jointly with $\kappa=d^{o(1)}$, see § 5.5. Note that $c_{\star}(\kappa) \sim\sqrt{\kappa}/8$ as $\kappa\to\infty$.

For each fixed $c \in(0,\infty)$, these bounds characterize the smallest worst-case width needed to achieve constant TV error. Below the threshold, the required width is

At or above the threshold, constant width suffices. Thus, the Gaussian result identifies both the depth threshold $c_{\star}(\kappa)\log d$ for constant-width sampling and the tradeoff leading up to it. Since the depth is logarithmic, this also marks a transition in total query complexity: below the threshold a positive power of $d$ is necessary, while above it $O(\log d)$ queries suffice.

Open questions. For general strongly log-concave targets, we have identified the logarithmic round scale at which polynomial width becomes possible. The Gaussian result suggests two finer questions about this transition.

The first concerns the location of the threshold and its dependence on $\kappa$. Taking $d \to\infty$ at each fixed $\kappa$ and then letting $\kappa\to\infty$, the coefficient $\zeta(\kappa)$ in our lower bound remains of constant order (see Corollary 4.5) while the coefficient obtained from the upper bound of [31 Corollary 4.3] grows as $\kappa\log\kappa$. Hence, it remains open whether ill-conditioning forces the coefficient of $\log d$ needed for polynomial-width sampling to grow with $\kappa$ and, if so, at what rate. For comparison, the Gaussian threshold for constant-width sampling has coefficient $c_\star(\kappa) \sim\sqrt{\kappa}/8$. From a practical perspective, closing this gap would help us identify whether ill-conditioning is better handled by increasing the width or depth of parallel samplers.

The second question concerns how the required width varies with the round budget $T = \lceil c \log d\rceil$. For fixed $0 < c < \zeta(\kappa)$ our width lower bound (4) is stretched-exponential with exponent decreasing linearly with $c$, but whether a sampler can attain this dependence remains open even at $\kappa= 2$ and constant TV error. At the other end of the tradeoff, Theorem 1.3 achieves logarithmic depth with near-linear width, while [24] achieves $d^{o(1)}$ total queries. It remains open whether $d^{o(1)}$ width suffices at logarithmic depth and, if not, how many rounds are necessary for subpolynomial width.

Related work

Parallel algorithms for sampling. Parallel sampling algorithms differ in what they evaluate simultaneously. Along a single Langevin trajectory, parallel variants of the randomized midpoint method evaluate the drift at several intermediate times in one batch [26, 30], while parallel Picard methods use the preceding trajectory estimate to update many time points in one round [2, 31]. ParaDiGMS applies the same idea to a diffusion model, evaluating a learned denoiser at several noise levels in parallel [25]. Rejection sampling also admits parallel implementations: one can test independent candidate paths in parallel [6, 7] or verify several proposed denoising steps in a batch [1]. In interacting particle methods, each round updates many particles using information shared across the current ensemble – examples include SVGD, LAWGD, the Radon-Wasserstein sampler, the ensemble Kalman sampler, and affine-invariant interacting Langevin dynamics [20, 11, 17, 15, 16].

Parallel complexity of log-concave sampling. For strongly log-concave targets with known mode, Zhou and Sugiyama [31 Corollary 4.3] give a sampler that achieves TV error $\varepsilon$ using

At fixed $\kappa$ and $\varepsilon$, this gives $\mathcal{O}(\log d)$ rounds with $\mathcal{O}(d\log d)$ queries per round. On the lower-bound side, Zhou, Wang, and Sugiyama [ZWS25] construct potentials that conceal a random partition of the coordinates and show that $\widetilde{\Omega}(d)$ rounds are necessary at exponentially small TV error. When $\varepsilon= \exp(-\Theta(d))$, this gives a lower bound of $\widetilde{\Omega}(\log(1/\varepsilon))$ rounds. Theorem 1.4 shows that even at constant TV error $\Omega_\kappa(\log d)$ rounds are necessary with polynomially many queries per round, which settles the dependence on $d$ at fixed $\kappa$ and $\varepsilon$. The optimal dependence on $\kappa$ and $\varepsilon$, as well as the width needed at logarithmic depth, remain open.

Total query complexity of log-concave sampling. Counting all queries across rounds gives a different picture already for Gaussian targets. Chewi et al. [8] use a block Krylov reduction to prove dimension-dependent query lower bounds for Gaussian sampling, which also apply to the larger strongly log-concave class. For centered Gaussians, the known upper bound is $\mathcal{O}(\min\{d,\sqrt{\kappa}\log(d/\varepsilon)\})$ matrix-vector queries, which the lower bound of Zhou and Suzuki [32] matches for $4 \leq\kappa\leq d^{2-\delta}$ and any fixed $\delta\in(0,2)$. The two terms correspond to different strategies for using precision matrix queries: querying $d$ basis vectors recovers it in one parallel round of width $d$, while polynomial approximation uses a sequence of repeated matrix-vector products at constant width. Theorem 1.6 characterizes the depth-width tradeoff and identifies the precise threshold for constant-width Gaussian sampling.

For general strongly log-concave targets at $\kappa= 2$ and constant TV error, OpenAI [24] gives a $d^{o(1)}$-query upper bound when the mode is known. Concurrently with the writing of this paper, Zhou and Suzuki [33] prove an $\exp(\Omega((\log d)^{1/3}))$ query lower bound even with a constant warm start. Their result separates Gaussian and strongly log-concave sampling in total query complexity, complementing the separation in round complexity given by Theorem 1.4.

Parallel complexity of diffusion sampling. In diffusion sampling, the oracle estimates the score of the Gaussian-smoothed target at a noise level chosen by the algorithm. Randomized midpoint and Picard methods achieve polylogarithmic round complexity under sufficiently small mean-square score error and suitable Lipschitz assumptions [14, 31]. However, mean-square accuracy alone permits large errors at query locations that are rare under the noisy target. In this oracle model, Xun and Price [29] prove a $\widetilde{\Omega}(\sqrt{d})$ lower bound on total score queries by showing that a sampler with a polynomial query budget must probe $\widetilde{\Omega}(\sqrt{d})$ distinct noise levels. Kou and Wang [19] obtain lower bounds on parallel rounds by concealing successive coordinate blocks, proving a $\widetilde{\Omega}(d^{1/3})$ bound for near-isotropic Gaussian mixtures and a tight $\Theta(d)$ bound for a family of anisotropic boxes. In our setting, the oracle answers every query exactly and so the potential itself must conceal the information needed in later rounds.