Paper deep dive
Lower Bounds for Parallel Diffusion Sampling
Yiwen Kou, Yimeng Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/8/2026, 7:49:52 AM
Summary
This paper establishes the first polynomial parallel-round lower bounds for diffusion sampling using approximate score functions. It proves that sampling smooth, near-isotropic Gaussian mixtures in dimension d requires at least \(\widetilde{\Omega}(d^{1/3})\) sequential rounds, and sampling from anisotropic axis-aligned boxes requires \(\Omega(d)\) rounds. These bounds hold for arbitrary randomized algorithms making polynomially many queries per round, demonstrating that significant sequential dependence is unavoidable even with parallel query capabilities.
Entities (7)
Relation Signals (5)
Score Function → isevaluatedby → Diffusion Sampling
confidence 96% · Standard diffusion samplers generate samples through repeated evaluations of a learned score function.
Diffusion Sampling → haslowerbound → Parallel Lower Bounds
confidence 95% · We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores.
Gaussian Mixtures → requiresroundcomplexity → \(\widetilde{\Omega}(d^{1/3})\)
confidence 93% · a \(\widetilde{\Omega}(d^{1/3})\)-round lower bound for sampling smooth, near-isotropic Gaussian mixtures
Anisotropic Boxes → requiresroundcomplexity → \(\Omega(d)\)
confidence 93% · an \(\Omega(d)\)-round lower bound for uniform sampling from anisotropic axis-aligned boxes
Parallel Lower Bounds → appliesto → Randomized Algorithms
confidence 90% · Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a $\widetilde{\Omega}(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $R^d$, and (2) an $\Omega(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.
Tags
Links
- Source: https://arxiv.org/abs/2610.09166v1
- Canonical: https://arxiv.org/abs/2610.09166v1
Trouble viewing inline? Open PDF directly →
Full Text
138,391 characters extracted from source content.
Expand or collapse full text
Lower Bounds for Parallel Diffusion Sampling Yiwen Kou †thanks: Email: evankou@ucla.edu, supported by NSF EnCORE: Institute for Emerging CORE Methods in Data Science Award #2217033 and NSF AF: Small Award #2425350 Affiliation: UCLA Yimeng Wang †thanks: Email: kobewang1359@ucla.edu, supported by NSF EnCORE: Institute for Emerging CORE Methods in Data Science Award #2217033 and NSF AF: Small Award #2425350 Affiliation: UCLA Abstract Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a Ω~(d1/3) (d^1/3)-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in ℝdR^d, and (2) an Ω(d) (d)-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level. October 6, 2026 Contents 1 Introduction 1.1 Main results 1.2 Related work 2 Preliminaries 3 Parallel lower bounds for near-isotropic targets 3.1 Only one additional block per round 3.2 An unseen block gives a TV gap 3.3 Why the exponent is 1/31/3 4 Linear parallel-round lower bounds for anisotropic boxes 5 Conclusion and future directions References A Deferred proofs from A.1 Parameters and near-isotropy A.2 Technical inputs from [51] A.3 Proof of A.4 Proof of A.5 Proof of A.6 Proof of B Deferred proofs from B.1 Public parameters and gates B.2 Proof of B.3 Proof of B.4 Proof of Lemma 4.4 1 Introduction Diffusion samplers generate samples by progressively removing noise through repeated evaluations of a learned denoising model [46, 22, 48, 47], with applications ranging from high-quality image synthesis to video generation [39, 23, 15, 41, 37, 35, 21, 6, 52, 45, 5, 18]. The central idea behind diffusion is to learn how to remove noise from data: during training, a neural network learns to denoise examples corrupted by varying amounts of noise. During generation, the learned model progressively transforms random noise into a new sample through a sequence of denoising steps [46, 22, 48, 47]. Beyond generating samples unconditionally, this framework supports generation guided by text descriptions or partially observed images [36, 41], allowing users to specify desired content, fill in missing image regions [34, 40], or enhance image resolution [42, 28]. This combination of sample quality and flexible conditioning makes diffusion models useful across a broad range of generative tasks [39]. A major practical challenge, however, is the cost of generation. Even after training is complete, producing a single sample with a standard diffusion sampler requires repeated evaluations of a neural network, making sampling computationally expensive. Faster sampling methods seek to reduce these evaluations while preserving sample quality [47, 31, 33, 53]. Moreover, standard implementations of denoising samplers such as DDPM [22] and DDIM [47] evaluate the denoising model sequentially, using each update to determine the input to the next evaluation. Hence, it is an important question in practice to reduce the number of sequential steps. Parallel diffusion sampling aims to shorten the generation of a single sample by evaluating several denoising proposals simultaneously. For example, a sampler can guess states at future noise levels, evaluate the model at those states in parallel, and use the answers to refine the proposed trajectory. Methods based on parallel iteration and speculation exploit this possibility to accelerate sampling [44, 49, 9, 24]. Such methods can trade additional model evaluations for fewer sequential rounds. The relevant resource is therefore how often the sampler must wait for one batch of answers before choosing the next. These developments raise a fundamental question: How many sequential rounds of interaction with a learned score model are necessary, even when each round allows polynomially many evaluations? To address this question, we must account for how score functions are obtained. In practice, the target distribution is typically known only through training data, so its exact scores at different noise levels are generally unavailable. Diffusion models instead learn score estimates from noise-corrupted samples using a squared-error denoising objective [48, 22]. This objective naturally motivates accuracy measured on average under the noisy data distribution. Therefore, we assume that learning has produced score estimates with small mean-squared error, and study the sequential rounds needed to sample using these estimates. Approximate scores satisfying distributional error guarantees support efficient sequential sampling. For targets with finite second moment and sufficiently accurate scores, existing results give nearly linear dependence on dimension for sampling suitably Gaussian-smoothed targets, with additional assumptions needed to transfer strong-metric guarantees to an unsmoothed target [4, 8]. Parallel algorithms can have polylogarithmic dimension dependence under quantitative regularity assumptions on the scores [9, 19, 54]. Speculative sampling also gives a O~(d) O( d) expected-round bound for Gaussian-smoothed bounded-support targets with exact denoising oracles [1]. Its inexact extension requires uniform pointwise accuracy. These results leave open the parallel complexity under the mean-square guarantee (1) alone. The closest diffusion lower bound, due to [51], establishes that Ω~(d) ( d) approximate-score queries can be necessary for constant total variation accuracy. This is a bound on the total number of queries. Their construction hides useful information in a narrow range of noise levels, requiring a search across possible scales. Those candidate scales can be queried simultaneously. A parallel-round lower bound therefore requires an additional obstruction: information learned in one round must be needed to choose informative queries in later rounds. We construct fixed approximate score oracles that enforce this dependence and obtain the first polynomial parallel-round lower bounds in this model. Oracle model. We formalize this discussion through an oracle model that abstracts away training and network architecture. For a target distribution π on ℝdR^d, let π(σ)=π∗(0,σ2Id)π^(σ)=π*N(0,σ^2I_d) denote its Gaussian smoothing and let sπ,σ=∇logπ(σ)s_π,σ=∇ π^(σ) be the corresponding score function. An algorithm may query any location x∈ℝdx ^d and any noise level σ>0σ>0. The oracle returns s^σ(x) s_σ(x), where the family s s is fixed before the interaction and satisfies X∼π(σ)[‖s^σ(X)−sπ,σ(X)‖22]≤εscore2σ2for every σ>0. _X π^(σ)\! [ \| s_σ(X)-s_π,σ(X) \|_2^2 ]≤ _score^2σ^2 every σ>0. (1) This mean-square guarantee reflects the distributional objectives used to learn scores. It controls error on noisy target samples while permitting larger errors in regions of small probability. In each adaptive round, the algorithm chooses a batch of queries before seeing any answers from that batch. Subsequent batches may depend on all previous answers. We allow polynomially many queries per round and unrestricted computation between rounds. The algorithm receives only the oracle answers and stated public information, and need not follow a prescribed diffusion trajectory. 1.1 Main results In this work, we establish the first parallel query-complexity lower bound for diffusion sampling. Both results below concern sampling the target itself to total variation error at most 1/101/10. They hold for arbitrary randomized algorithms making polynomially many queries per round, with arbitrary query locations and noise levels, and with inverse-polynomial score error in (1). Theorem 1.1 (Near-isotropic targets; consequence of Theorem 3.1). For all sufficiently large d, there is a family of smooth, near-isotropic Gaussian mixtures on ℝdR^d for which sampling requires Ω~(d1/3) (d^1/3) adaptive rounds. After a fixed public rescaling, these targets have mean of norm o(1)o(1) and covariance within o(1)o(1) of IdI_d in operator norm. Thus, poor covariance conditioning is unnecessary for polynomial parallel hardness. The targets are equal-weight Gaussian mixtures whose components share a constant-variance isotropic covariance. Parallel hardness. Our constructions arrange hidden information in an ordered sequence of blocks. Independent hard instances alone do not impose such an ordering: the exact score of a product distribution separates across blocks, allowing a single query to probe them all. We instead construct a fixed approximate oracle that reveals the hidden contribution of a later block only when the query passes consistency tests involving earlier blocks. A genuine noisy sample contains evidence of the hidden structure in each block and passes these tests with high probability. Controlling both these failure probabilities and the sizes of the suppressed contributions lets the oracle satisfy (1). At noise levels where later blocks still carry hidden information, a query chosen without the earlier hidden information is unlikely to pass the required tests. The main challenge is to preserve this obstruction across every noise level. We coordinate the blocks so that, at each level, either the first unknown block is difficult to pass, or the later blocks are sufficiently smoothed that their scores admit accurate uninformative responses. Consequently, a query cannot bypass an unknown earlier block and obtain hidden information from a later one, except with small probability. This dichotomy applies separately to every query, including queries at different noise levels in the same batch. A batch can reveal the current block, but using that information to choose new queries requires another round. An unexposed block then prevents the output distribution from approximating the target in total variation. The two constructions realize this mechanism with different geometric costs. For near-isotropic targets, we use independent random sets of Gaussian centers, or codebooks, building on [51]. Ordering their sizes lets us fit Θ~(d1/3) (d^1/3) successive barriers while preserving near-isotropy. For boxes, separated coordinate scales let each barrier occupy a single coordinate, yielding d barriers at the cost of substantial anisotropy. The sequential-exposure principle has antecedents in parallel matroid search [26] and sampling with counting oracles [3]. Our construction implements it through score approximations that remain accurate at every noise level. Section 3 and Section 4 give the detailed argument. A linear lower bound from anisotropy. While our first result shows that poor covariance conditioning is not necessary for parallel sampling hardness, anisotropy can provide an additional source of difficulty. Here anisotropy refers to widely different variances in different directions, measured by the condition number κ of the covariance matrix. Previous works such as [32, 25, 12] have demonstrated this hardness and ways to address it in various sampling settings. Our second construction uses a hierarchy of coordinate scales to strengthen the round lower bound to linear in dimension at the cost of anisotropy. Theorem 1.2 (Anisotropic boxes; consequence of Theorem 4.1). For all sufficiently large d, there is a family of full-dimensional, axis-aligned boxes K⊆B2(0,1)K B_2(0,1) for which sampling from Unif(K)Unif(K) requires Ω(d) (d) adaptive rounds. The box family has substantial anisotropy: its coordinate scales decrease geometrically. The candidate intervals are public, but their selected locations are hidden, and no interior point is supplied. This result shows how separated spatial scales can enforce a successive information barrier in every coordinate. For comparison, specializing the analysis of [8] to our Gaussian-mixture family gives a O~(d5/6) O(d^5/6) score-query upper bound under the same oracle guarantee, leaving a polynomial gap (Lemma 3.5). For our box family, a direct recovery algorithm uses O(d)O(d) rounds, matching the linear lower bound (Lemma 4.4). This matching upper bound relies on the known candidate-interval geometry. Remark. [1] obtained a O~(d) O( d) expected-round upper bound for parallel sampling Gaussian-smoothed versions of bounded-support distributions using a Gaussian denoising oracle. This oracle returns posterior means, which are related to smoothed scores by Tweedie’s identity. Their main result assumes exact oracle answers, and their extension to approximate answers requires a uniform pointwise bound on the denoiser error over all query locations and noise levels. Our accuracy assumption is distributional: at each noise level, we control the mean-square score error averaged over the true noisy target. This permits larger errors at query locations that have small probability under that distribution. This distinction is essential to our lower-bound mechanism as our fixed approximate oracles exploit this freedom to suppress hidden information at atypical query locations while remaining accurate on genuine noisy samples. Our lower-bound construction relies on the freedom permitted by the distributional guarantee (1), and does not establish a corresponding lower bound under the pointwise accuracy assumptions of [1]. 1.2 Related work Sequential diffusion sampling. Polynomial-complexity guarantees under mean-square score error were established by [10, 29], using early stopping to accommodate nonsmooth or singular targets. Subsequent work improved the dimension and accuracy dependence: [4] obtained a O~(d/δ2) O(d/δ^2) bound, [30] obtained O~(d/δ) O(d/δ), and [8] obtained O~(dpolylog(1/δ)) O(d\,polylog(1/δ)), with intrinsic-dimension refinements. Here δ denotes sampling accuracy, and the bounds require sufficiently accurate scores. For general targets, strong-metric guarantees apply to Gaussian-smoothed distributions. Guarantees for the original target require a weak metric or additional regularity. Parallel sampling algorithms. ParaDiGMS [44] uses Picard iteration to refine multiple denoising steps simultaneously. Theoretical diffusion guarantees [9, 19, 54] accommodate mean-square score error together with quantitative regularity assumptions. For example, the round complexity in [19] depends on Lipschitz bounds for both the true and estimated scores. Autospeculative methods [24] and speculative rejection sampling [1] provide another approach, with the exact-oracle and pointwise-error assumptions discussed above. Parallel Langevin methods also give favorable dimension dependence for smooth targets under strong log-concavity or log-Sobolev assumptions [43, 2]. These upper bounds depend on additional parameters beyond the mean-square score error in (1). Query and round lower bounds. Lower bounds for exact first-order sampling include sharp one-dimensional results [14] and condition-number-dependent bounds already for Gaussian targets [12]. Other work treats stochastic gradients [7], relative Fisher information accuracy [13], or non-log-concave targets with value-and-gradient access [20]. For convex bodies, [17] gives a linear sequential membership-query lower bound using boxes, and [50] proves an Ω(d2/(logd)9) (d^2/( d)^9) expected total-query lower bound for bodies satisfying B2(0,1)⊆K⊆B2(0,O(d3/2))B_2(0,1) K B_2(0,O(d^3/2)). These bounds count queries rather than adaptive rounds. In the counting-oracle model, [3] proves a Ω~(d1/3) (d^1/3) round lower bound using sequential exposure, following the parallel-search framework of [26, 27]. Its oracle differs from smoothed-score access. In diffusion, [51] supplies the total-query lower bound and codebook ingredients discussed above. Concurrent work [11] compares corruption processes, obtaining O~(d) O( d)-query sampling algorithms for random empirical measures on the Boolean hypercube with sufficiently accurate uniform or Gaussian diffusion scores, and a Ω~(d) (d) query lower bound for approximate masked diffusion. Our focus is the sequential dependence that persists when many score queries can be issued simultaneously. Organization. Section 2 introduces our notation and oracle model. Section 3 proves the parallel lower bound for near-isotropic Gaussian mixtures. Section 4 establishes the linear lower bound for anisotropic boxes. Parameter choices and detailed proofs appear in Appendix A and Appendix B. 2 Preliminaries Notation. Unless specified otherwise, all logarithms are natural. We write [n]=1,…,n[n]=\1,…,n\, let IdI_d denote the identity matrix, and use ∥⋅∥2\|·\|_2, ∥⋅∥op\|·\|_op, and ∥⋅∥F\|·\|_F for the Euclidean, operator, and Frobenius norms. The ball of radius r centered at the origin is B2(0,r)B_2(0,r). We write Unif(S)Unif(S) for the uniform law on a nonempty finite set, Unif(K)Unif(K) for normalized Lebesgue measure on a measurable set of positive finite volume, and ℒ(X)L(X) for the law of X. We identify a distribution with its density when one exists. For probability measures μ,νμ,ν, total variation distance is dTV(μ,ν)=supA|μ(A)−ν(A)|,d_TV(μ,ν)= _A|μ(A)-ν(A)|, where the supremum is over measurable sets. Any coupling (X,Y)(X,Y) of these measures satisfies dTV(μ,ν)≤[X≠Y]d_TV(μ,ν)≤ Pr\/[X≠ Y]. We use both facts: an event distinguishes a sampler’s output from the target, while a coupling transfers this distinction between two executions of an algorithm. Relative entropy is DKL(μ∥ν)=∫log(dμ/dν)dμD_KL(μ\|ν)= (dμ/dν)\,dμ when μ≪νμ ν, and +∞+∞ otherwise. Mutual information is MI(U;V)=DKL(ℒ(U,V)∥ℒ(U)⊗ℒ(V))MI(U;V)=D_KL(L(U,V)\|L(U) (V)). For a measurable vector field f, write ‖f‖L2(μ)2=X∼μ‖f(X)‖22\|f\|_L^2(μ)^2=E_X μ\|f(X)\|_2^2. For a distribution π with finite second moments, write Cov(π)Cov(π) for its covariance matrix. It is isotropic if its mean is zero and Cov(π)=IdCov(π)=I_d. We state near-isotropy through explicit bounds on the mean and the operator-norm deviation of the covariance from IdI_d, specifying any public scalar rescaling. For a positive definite matrix Σ , its condition number is κ(Σ)=λmax(Σ)/λmin(Σ)κ( )= _ ( )/ _ ( ). Gaussian smoothing and scores. For a target π on ℝdR^d and an additional noise level σ>0σ>0, define π(σ)=π∗(0,σ2Id),sπ,σ(x)=∇logπ(σ)(x).π^(σ)=π*N(0,σ^2I_d), s_π,σ(x)=∇ π^(σ)(x). Thus π(σ)π^(σ) is the law of Y+σZY+σ Z for independent Y∼πY π and Z∼(0,Id)Z (0,I_d). Gaussian convolution has a positive smooth density, so the score is defined at every query point. Smoothing preserves product structure, and the score of a product density is the concatenation of its factor scores. The posterior-mean identity explains what a score query reveals. For bounded Y∼νY ν, differentiating the Gaussian likelihood contributes the factor (Y−x)/σ2(Y-x)/σ^2, giving Tweedie’s formula [38, 16]: x+σ2sν,σ(x)=[Y∣Y+σZ=x].x+σ^2s_ν,σ(x)=E[Y Y+σ Z=x]. Here the posterior is defined by weighting ν by the Gaussian likelihood at x; the identity therefore holds at every point, not merely almost everywhere. For a target that already contains Gaussian noise, π=μ∗(0,γ2Id)π=μ*N(0,γ^2I_d) with γ>0γ>0, we also use total noise τ: πτ=μ∗(0,τ2Id),τ2=γ2+σ2,π(σ)=πτ. _τ=μ*N(0,τ^2I_d), τ^2=γ^2+σ^2, π^(σ)= _τ. The endpoint τ=γτ=γ describes the target itself. Actual queries have σ>0σ>0, hence τ>γτ>γ. Approximate oracles and parallel rounds. Fix εscore>0 _score>0. A legal score oracle for π is a fixed jointly measurable map s^:ℝd×(0,∞)→ℝd s:R^d×(0,∞) ^d satisfying X∼π(σ)‖s^σ(X)−sπ,σ(X)‖22≤εscore2σ2(σ>0).E_X π^(σ) \| s_σ(X)-s_π,σ(X) \|_2^2≤ _score^2σ^2 (σ>0). (2) The expectation is under the true noisy target. The oracle is fixed once the instance is chosen and remains unchanged throughout the interaction. No pointwise accuracy, spatial Lipschitz bound, or representation as another density’s score is required. An algorithm must succeed for every legal oracle for its target; a lower-bound construction may therefore assign one particular legal oracle to each target. An R-round algorithm submits at most P queries (x,σ)(x,σ) per round, choosing the entire batch before receiving any of its answers. Locations and noise levels may differ within a batch. Later batches depend on the preceding transcript and an independent random seed ω, which includes all algorithmic and output randomness. Apart from the stated public information, the algorithm receives only oracle answers. Computation between queries is unrestricted. For a fixed target-oracle pair (π,s^)(π, s), let Qπ,s^Q_π, s denote the output law, averaging over ω. Success means that dTV(Qπ,s^,π)d_TV(Q_π, s,π) is small: the target is π itself. In distributional lower bounds, the hard-instance law is chosen independently of the algorithm. Probability over instances is separate from the algorithmic randomness already averaged in Qπ,s^Q_π, s. Convention. Fix a polynomial query budget P=P(d)P=P(d) and an inverse-polynomial score accuracy εscore=εscore(d) _score= _score(d). Unless otherwise specified, for the rest of this paper, algorithms make at most P queries per round. The instance families and implicit constants may depend on these fixed bounds, which are chosen before the family is constructed. 3 Parallel lower bounds for near-isotropic targets In this section, we prove that a sampler using too few rounds produces a distribution far from its target in total variation. We focus on intuitions and high-level ideas with technical details deferred to Appendix A. The proof identifies an event that a genuine sample almost always satisfies, but the algorithm’s output rarely satisfies. The difference between these two probabilities gives the lower bound. Theorem 3.1 (Parallel lower bound for near-isotropic targets). For all sufficiently large d, there is a family of near-isotropic Gaussian-mixture targets πS _S, each equipped with an approximate oracle s s satisfying (1) such that every randomized sampler using O((d/logd)1/3)O ((d/ d)^1/3 ) rounds has an output law QπS,s^Q_ _S, s satisfying S[dTV(QπS,s^,πS)≥0.9]≥0.9. Pr\/_S[d_TV(Q_ _S, s,\, _S)≥ 0.9]≥ 0.9. Parallel hardness. Our starting point is the way [26, 3] use blocks to limit the information revealed in each round. The common aim is to force one round of queries to reveal information about only one additional block. More specifically, let d denote the ambient dimension. We divide d coordinates into B=(d)B= poly(d) blocks of dimension m=⌊d/B⌋m= d/B each. Within each block, we plant an instance that is hard for the query model. Crucially, the sizes of these planted hard instances must be placed on an increasing scale. The reason for this is to account for the power of the oracle: since the oracle can query at different noise levels, we want to make sure that regardless of the noise level σ, only one of the blocks sees this query as informative. It seems this simple idea already yields a parallel lower bound. However, there is a major obstruction: the score function factorizes. In particular, since the construction creates hard instances independently within each block, if we query the global score function at some noise level σ, we will obtain the score of each block at noise level σ. Hence, as long as we query the global score function at (d) poly(d) many noise levels, we would obtain information about all the blocks, making the whole argument fail. To fix this problem, one natural way is to create dependence between the instances across different blocks. While this may be a feasible approach, instance-dependence across different blocks makes the analysis significantly more difficult. Instead, we exploit the approximate L2L_2-guarantee (1). Concretely speaking, to establish a lower bound under (1), we do not need to concern ourselves too much with exact score functions. It suffices to construct an approximate oracle s s that satisfies (1) and prove parallel lower bounds with respect to s s. To this end, we construct an approximate oracle whose answer in block j+1j+1 also depends on a test of the point supplied in block j. The test checks whether this point looks like a noisy sample from block j’s hidden centers. When the test returns 00, block j+1j+1 receives a null score independent of its hidden centers. Thus, to obtain information about block j+1j+1, a query must supply a point in block j that opens the test. This special structure of s s allows us to prove the parallel lower bound. We now make this idea precise. Figure 1: One-block-at-a-time exposure in the prefix-gated construction. The increasing heights schematically represent the codebook sizes n1<⋯<nBn_1<·s<n_B. Here all coordinate blocks have the same dimension. Before round r, the progressive transcript depends only on the exposed prefix S1,…,Sr−1S_1,…,S_r-1 and the algorithm’s randomness. Even with polynomially many parallel queries, all locations and noise levels must be chosen before receiving any answer. With high probability, this batch can be answered using only SrS_r in addition to the exposed prefix, leaving Sr+1,…,SBS_r+1,…,S_B hidden. The dashed block indicates possible new dependence, not guaranteed recovery of SrS_r. Construction. Let B be the number of blocks and m=⌊d/B⌋m= d/B their dimension11 1 Any remaining coordinates use independent uniform signs plus Gaussian noise.. In block j, choose a random set SjS_j of cube vertices in −1,+1m\-1,+1\^m. Such a set is called a codebook. A target sample at total noise level τ≥γτ≥γ chooses one of its vertices uniformly and adds Gaussian noise: Xj=Yj+τZj,Yj∼Unif(Sj),Zj∼(0,Im). X_j=Y_j+τ Z_j, Y_j (S_j), Z_j (0,I_m). (3) The codebooks are independent across blocks. Each codebook is uniform among sets of its prescribed size, with these sizes increasing with block index j. One can show that the target distribution is near-isotropic with high probability after scaling. We include a detailed proof in Section A.1. Given this, we now specify the earlier-block tests, called gates, and show that the resulting answers satisfy the L2L_2 score-error guarantee (1) which is averaged over noisy target samples. For one noise level τ, let sjs_j be the true score in block j. Let s0s^0 be the null score of the full cube smoothed at the same noise level τ. 22 2 All blocks have dimension m and use the same full-cube reference distribution. Thus, at a fixed noise level τ, the null score is identical across blocks, and we omit the block index. By null score, we mean the score function of block j when the underlying SjS_j is −1,+1m\-1,+1\^m. Notice this null score is independent of the hidden codebook. Similar to [51], we choose the blockwise local answer bjb_j as follows: use s0s^0 when it is sufficiently accurate, and use sjs_j otherwise. Let ai(xi)∈[0,1]a_i(x_i)∈[0,1] be the gate for block i, with value one meaning that the query passes. Soon we will make this notion more precise. At the j-th block, the oracle returns s^j(x)=s0(xj)+(∏i<jai(xi))(bj(xj)−s0(xj)). s_j(x)=s^0(x_j)+ ( _i<ja_i(x_i) ) (b_j(x_j)-s^0(x_j) ). (4) On the d−Bmd-Bm padding coordinates, we use their exact public score. Notice that passing all earlier tests gives the local answer bjb_j, while a closed earlier gate (ai(xi)=0a_i(x_i)=0 for some i<ji<j) leaves the null score s0s_0. The first fact we need is that their combination satisfies the required accuracy guarantee. Lemma 3.2 (Accuracy of the gated oracle). For the target distribution constructed in (3) at τ=γτ=γ, the oracle in (4) satisfies (1) at every additional query noise level σ>0σ>0 with τ=γ2+σ2τ= γ^2+σ^2. Under the noisy target distribution, genuine samples usually pass the gates, so the oracle returns the accurate local answers bjb_j in later blocks. The error can be controlled by small probability of failed gates and blockwise L2L_2-accuracy guarantee developed in [51]. Section A.3 gives the detailed calculation. 3.1 Only one additional block per round Having established the oracle’s accuracy, we now show why a parallel batch can reveal information about at most one additional codebook. Fix a batch whose queries depend only on S1,…,Sr−1S_1,…,S_r-1 and an independent random seed. It suffices to show that, with high probability, every response in a block j>rj>r is the null score. Small window of informative noise levels. The oracle definition gives two ways this can happen: (1) the gate in block r is closed or (2) every later local answer already equals the null score. The first is likely when block r is sufficiently sparse at the queried noise level while the second is likely when all later blocks are sufficiently dense. We separate the codebook sizes so that every noise level falls into one of these two cases. To make this precise, we compare each codebook’s size with the information retained after smoothing as in [51]: κj=log|Sj|m⏟codebook rateandατ=MI(Y0,Y0+τZ)⏟information per coordinate. _j= |S_j|m_codebook rate _τ=MI(Y^0;Y^0+τ Z)_information per coordinate. (5) Here Y0∼Unif(±1)Y^0 (\± 1\) is a uniform sign, Z∼(0,1)Z (0,1) is independent, and τ≥γτ≥γ is the total Gaussian noise. The rates κj _j stay fixed as τ changes, while ατ _τ decreases. Crucially, this information level ατ _τ determines the transition. Let φτ _τ be the density of (0,τ2Im)N(0,τ^2I_m) and qτq_τ the density of the smoothed full cube. For a center y and observation x, the log-likelihood ratio ℓτ(y,x)=logφτ(x−y)qτ(x) _τ(y,x)= _τ(x-y)q_τ(x) measures the evidence for that center relative to the full cube. At a genuine noisy observation of y, this quantity concentrates around its mean [ℓτ(y,y+τZ)]E[ _τ(y,y+τ Z)], which is equal to mατm _τ. The gate tests whether some center supplies nearly this much evidence. Thus its threshold comes from a typical likelihood ratio while the noise level controls how much evidence a genuine sample retains. Now fix a query (x,τ)(x,τ) chosen independently of the hidden codebook SjS_j. To open the gate, this point must supply enough evidence for at least one of the codebook’s centers. First consider the cutoff mατm _τ, before allowing for concentration margins. Averaging exp(ℓτ(y,x)) ( _τ(y,x)) over a uniform cube vertex gives one, so Markov’s inequality bounds the probability that a random center meets this cutoff by exp(−mατ) (-m _τ). Taking a union bound over the |Sj|=exp(mκj)|S_j|= (m _j) centers gives Sj[∃y∈Sj:ℓτ(y,x)≥mατ] Pr\/_S_j\! [∃ y∈ S_j: _τ(y,x)≥ m _τ ] ≤|Sj|exp(−mατ)=exp(−m(ατ−κj)). ≤|S_j| (-m _τ)= (-m( _τ- _j)). When κj _j is sufficiently below ατ _τ, this probability is small: there are too few centers to compensate for how unlikely each individual match is. Thus an independently chosen query rarely opens the gate! With high probability, the gate is zero and the oracle returns null scores in all later blocks. This is the sparse-block hiding property. At the same time, a genuine sample usually passes because it was generated from a center already in the codebook. In the other direction, sufficiently many random centers average out after smoothing: when κj _j is above ατ _τ by a suitable margin, the null score is accurate with high probability. The rigorous estimates place two thresholds around the information level, κ−(τ)≤ατ≤κ+(τ),κ^-(τ)≤ _τ≤κ^+(τ), with a gap of order at most logd/m d/m, uniformly over the noise levels. Lemma A.10 gives the following guarantees for a random codebook: • If κj≤κ−(τ) _j≤κ^-(τ), a point chosen independently of the codebook rarely opens its gate. • If κj≥κ+(τ) _j≥κ^+(τ), its local response is identically the null score with high probability. We separate adjacent block rates κj,κj+1 _j,\, _j+1 by the width of the intermediate interval [κ−(τ),κ+(τ)][κ^-(τ),κ^+(τ)] of order logd/m d/m. This ensures that a block whose rate exceeds the sparse threshold is followed only by blocks above the dense threshold. Hardness for algorithms. Now, for the sake of analysis, suppose the first r−1r-1 codebooks have been exposed, with r<Br<B. Choose the next batch’s locations and noise levels using only these codebooks and an independent random seed. For each query at noise level τ, there are two cases: 1. If κr≤κ−(τ) _r≤κ^-(τ), the first unknown block is sparse. Its gate closes with high probability, suppressing every later block’s correction to the null score. 2. If κr>κ−(τ) _r>κ^-(τ), the gap to the next rate places κr+1 _r+1 above κ+(τ)κ^+(τ). Every later block is therefore dense, and their local responses are null scores with high probability. In either case, with high probability, every later block returns the null score. Block r may still reveal information about its own codebook, because its response in (4) is controlled only by earlier gates. A union bound over the queries shows that, with high probability, every answer beyond block r is a null score throughout the batch, including when queries use different noise levels. We express the result through a simulation. In round r, the simulation uses the first r codebooks and returns null scores in all later blocks. Consequently, after R rounds its output depends only on the first R codebooks. The following lemma says that this restricted simulation can reproduce the actual output with high probability. Lemma 3.3 (One new block per round). Let a sampler use R<BR<B rounds within the prescribed polynomial query budget. Its actual output Y and a simulated output Y~ Y can be generated together so that [Y≠Y~]≤0.001. Pr\/[Y≠ Y]≤ 0.001. The simulated output depends only on the algorithm’s random seed and S1,…,SRS_1,…,S_R. The probability averages over the independent codebooks and seed. The proof runs both interactions with the same random choices. As long as their answers agree, they select the same next batch. The first disagreement therefore occurs on a batch selected by the simulation, whose unused codebooks remain independent. Summing the small disagreement probabilities over all rounds gives the lemma. For a general and precise argument, see Lemma A.13. The useful conclusion is independence: Y~ Y is independent of SR+1S_R+1. This gives us a specific block in which to compare the output with a genuine sample. 3.2 An unseen block gives a TV gap We now turn the restriction on information revealed per round into a lower bound on sampling accuracy, using an unseen block to distinguish the sampler’s output from the target distribution. Fix a sampler using R rounds, where R<BR<B and B is the number of blocks. Lemma 3.3 shows that the simulated output is independent of the (R+1)(R+1)-st codebook SR+1S_R+1. We use the gate in this block at the target’s noise level to distinguish a genuine sample from the sampler’s output. A genuine sample was generated from that block’s codebook, so it usually passes while the simulated output is independent of the codebook, and therefore has little chance of passing. Let tτt_τ be the log-likelihood cutoff of the gate at total noise τ, chosen slightly below mατm _τ as in equation (34) in Section A.3. For a codebook S⊆±1mS \± 1\^m, define the target-level test: E(S)=x∈ℝm:maxy∈Sℓγ(y,x)≥tγ.E(S)= \x ^m: _y∈ S _γ(y,x)≥ t_γ \. Intuitively, E(S)E(S) consists of points close to a codebook center, where closeness is measured by the likelihood test above. The following lemma shows that genuine samples usually belong to E(S)E(S), whereas points chosen independently of the codebook S rarely do. Lemma 3.4 (Recognizing samples from a hidden block). Let n be one of the codebook sizes used in our construction. For every fixed n-element codebook S, a sample from its target block (3) at τ=γτ=γ belongs to E(S)E(S) with probability at least 0.9990.999. If S is uniform among the n-element subsets of ±1m\± 1\^m, then for every fixed x, S[x∈E(S)]≤0.001. Pr\/_S[x∈ E(S)]≤ 0.001. We bound these two probabilities in Lemma A.14. In Section A.1, we choose the parameters so that the error probabilities are at most 0.0010.001. Now we are ready to prove the total variation lower bound in our main theorem. Proof of Theorem 3.1. We first work with the unscaled targets and the independent codebook law. Fix a sampler using R<BR<B rounds, and write QSQ_S for its output law on instance S. For x∈ℝdx ^d, let xR+1∈ℝmx_R+1 ^m denote its coordinates in block R+1R+1. Define DS=x∈ℝd:xR+1∈E(SR+1).D_S=\x ^d:x_R+1∈ E(S_R+1)\. This event checks whether the output passes the target-level test in the first unseen block. By Lemma 3.4, πS(DS)≥0.999π^S(D_S)≥ 0.999 for every fixed instance S. Couple the actual output Y to the simulated output Y~ Y as in Lemma 3.3. Conditional on S1,…,SRS_1,…,S_R and the algorithm’s random seed, Y~R+1 Y_R+1 is fixed, while SR+1S_R+1 remains an independent random codebook. The second part of Lemma 3.4 therefore gives, after averaging, [Y~∈DS]≤0.001. Pr\/[ Y∈ D_S]≤ 0.001. Here the probability averages over the independent codebooks and the algorithm’s randomness. Consequently, S[QS(DS)] _S[Q_S(D_S)] =[Y∈DS] = Pr\/[Y∈ D_S] ≤[Y~∈DS]+[Y≠Y~] ≤ Pr\/[ Y∈ D_S]+ Pr\/[Y≠ Y] ≤0.002. ≤ 0.002. For every fixed S, total variation is at least the difference between the probabilities of DSD_S. Averaging gives S[dTV(QS,πS)]≥0.999⏟genuine sample−0.001⏟simulated output−0.001⏟simulation error=0.997.E_S\! [d_TV(Q_S,π^S) ]≥ 0.999_genuine sample- 0.001_simulated output- 0.001_simulation error=0.997. (6) Let G be the near-isotropy event from Lemma A.2. For sufficiently large d, (G)≥1/2 Pr\/(G)≥ 1/2, and on G the fixed public rescaling by (1+γ2)−1/2(1+γ^2)^-1/2 produces a near-isotropic target. Since 1−dTV(QS,πS)1-d_TV(Q_S,π^S) is nonnegative, the preceding bound implies S[1−dTV(QS,πS)|G]≤0.003(G)≤0.006.E_S\! [1-d_TV(Q_S,π^S)\, |\,G ]≤ 0.003 Pr\/(G)≤ 0.006. Markov’s inequality now gives S[dTV(QS,πS)<0.9|G]≤0.0060.1=0.06. Pr\/_S\! [d_TV(Q_S,π^S)<0.9\, |\,G ]≤ 0.0060.1=0.06. Hence S[dTV(QS,πS)≥0.9|G]≥0.94≥0.9. Pr\/_S\! [d_TV(Q_S,π^S)≥ 0.9\, |\,G ]≥ 0.94≥ 0.9. Choose the hard-instance distribution by conditioning the codebook law on G and applying the fixed public rescaling, together with the oracle transformation in Section A.1. This distribution is independent of the sampler and is supported on near-isotropic targets equipped with legal oracles. Any sampler for the rescaled targets induces a sampler for the original targets with the same query and round budgets. Since the invertible rescaling preserves total variation, the preceding probability bound proves the claimed guarantee. ∎ 3.3 Why the exponent is 1/31/3 The preceding argument gives a lower bound of B rounds, provided the codebook rates are sufficiently separated. We now choose the number of blocks so that this separation is compatible with the ambient dimension d, yielding the exponent 1/31/3. To achieve this, we want to choose as many blocks as the separation estimates κ−,κ+κ^-,κ^+ permit. Each increasing parameter has an available range of length proportional to m. In our construction, a block has at most 2m2^m possible centers, and the chosen logarithmic sizes occupy a fixed fraction of this range. Multiplying the rate margin logd/m d/m from Section 3.1 by m gives the logarithmic-size spacing mlogd m d. These are sufficient spacings for the proofs. The logarithmic factor makes the failure probabilities small enough for polynomially many queries. For our oracle, the constants also accommodate the prescribed inverse-polynomial accuracy. To fit B levels, the number of gaps times their spacing must fit inside the available range. Thus the choices satisfy B⏟number of levelsmlogd⏟spacing≲m⏟available range. B_number of levels m d_spacing m_available range. Equivalently, a block must have size m≳B2logdm B^2 d for this choice of spacing. Since B such blocks use d≍Bmd Bm coordinates, we obtain B3logd≲d.B^3 d d. This is the origin of the exponent 1/31/3. Lemma A.1 makes the choice with integer codebook sizes and obtains B=Θ((d/logd)1/3).B= ((d/ d)^1/3 ). Together with the total variation gap, this proves Theorem 3.1. For comparison, using the algorithm from [8], we can show that the same family admits a sampler using O~(d5/6) O(d^5/6) score queries under the same accuracy guarantee. Lemma 3.5 (Upper bound for the same target family). For all sufficiently large d, every target in the constructed family can be sampled to total variation error at most 1/101/10 using O~(d5/6) O(d^5/6) score queries, with one query per round, for every fixed leagl oracle. Section A.6 gives the complete error and query bounds. The main technical step is to verify the required regularity conditions for the denoiser. Using this, we can then prove this specialization of the sampling guarantee from [8]. 4 Linear parallel-round lower bounds for anisotropic boxes In this section, we prove an Ω(d) (d) parallel-round lower bound for uniform distributions over boxes and provide a matching upper bound. We focus on intuitions and high-level ideas with technical details deferred to Appendix B. Theorem 4.1 (Linear parallel lower bound). For sufficiently large d, there is a distribution over full-dimensional axis-aligned boxes Kθ⊂B2(0,1)K^θ⊂ B_2(0,1), with a fixed legal approximate oracle satisfying (1) for each πθ=Unif(Kθ)π^θ=Unif(K^θ), such that every randomized sampler using fewer than d rounds has output law QθQ^θ satisfying θ[dTV(Qθ,πθ)≥0.9]≥0.9. Pr\/_θ\! [d_TV(Q^θ,π^θ)≥ 0.9 ]≥ 0.9. Here, the instance distribution and oracle family are independent of the sampler. The probability is over the instance. The idea is similar to the construction in Section 3: we want to create a structure such that any randomized parallel algorithm can only unlock at most one block in a round. Since we allow anisotropy, it turns out we can simply use individual coordinates as our blocks. We now make this precise. Construction. Let M denote the number of candidate intervals in each coordinate. In coordinate i, let ai>0a_i>0 denote their location scale. We place M disjoint intervals Ii(1),…,Ii(M)I_i(1),…,I_i(M) in [ai,2ai][a_i,2a_i], with equally spaced centers and lengths much smaller than the gaps between them. The location scales and interval lengths decrease rapidly with i. We defer the parameter choices to Section B.1. Choose θ1,…,θd _1,…, _d independently and uniformly from [M][M], and set Kθ=∏i=1dIi(θi),πθ=Unif(Kθ).K^θ= _i=1^dI_i( _i), π^θ=Unif(K^θ). (7) All candidate intervals are available to the algorithms. Here only the labels are hidden, and no point inside the box is supplied. The parameters are chosen so that every box lies in the unit ball. The rapidly decreasing interval lengths give widely different coordinate variances, making the construction anisotropic. The approximate oracle. Fix an instance θ. For each coordinate j and noise level σ>0σ>0, let mj,σθj(z)m_j,σ _j(z) denote the posterior mean of U∼Unif(Ij(θj))U (I_j( _j)) given U+σZ=zU+σ Z=z, where Z∼N(0,1)Z N(0,1) is independent. The superscript θj _j records the selected interval in coordinate j. Since Gaussian smoothing preserves the product structure, the true score satisfies sj,σθ(x)=−xjσ2+mj,σθj(xj)σ2,mj,σθj(xj)∈Ij(θj)⊂[aj,2aj].s_j,σ^θ(x)=- x_jσ^2+ m_j,σ _j(x_j)σ^2, m_j,σ _j(x_j)∈ I_j( _j)⊂[a_j,2a_j]. (8) We use the public null score sσ0(z)=−z/σ2s_σ^0(z)=-z/σ^2 and gate only the posterior-mean correction mj,σθj(xj)/σ2m_j,σ _j(x_j)/σ^2. Let t1>⋯>td>0t_1>·s>t_d>0 denote the noise cutoffs: above tjt_j, the correction in coordinate j is small enough to discard within the score-error budget. For each coordinate i<di<d and candidate label k∈[M]k∈[M], we construct a gate gi,σk:ℝ→[0,1]g_i,σ^k:R→[0,1] that tests proximity to the interval Ii(k)I_i(k): • When σ≤ti+1σ≤ t_i+1, the gate equals one on a fixed neighborhood of Ii(k)I_i(k), decreases linearly with distance from the interval, and equals zero outside a slightly larger neighborhood. We choose these neighborhoods so that gi,σk(U+σZ)=1g_i,σ^k(U+σ Z)=1 with high probability for U∼Unif(Ii(k))U (I_i(k)) and independent Z∼N(0,1)Z N(0,1). At the same time, the larger neighborhoods are disjoint: for any fixed input z, at most one label k can satisfy gi,σk(z)>0g_i,σ^k(z)>0. Section B.1 specifies the neighborhoods and the probability bound. • When σ>ti+1σ>t_i+1, set gi,σk≡1g_i,σ^k≡ 1. At these noise levels, every later coordinate j>ij>i already satisfies σ>tjσ>t_j, so its correction is discarded and the gate is unnecessary. For the instance θ, we use the gate gi,σθig_i,σ _i corresponding to the selected interval Ii(θi)I_i( _i), and define s^j,σθ(x)=sσ0(xj)+σ≤tj(∏i<jgi,σθi(xi))mj,σθj(xj)σ2. s^θ_j,σ(x)=s^0_σ(x_j)+1_\σ≤ t_j\ ( _i<jg _i_i,σ(x_i) ) m _j_j,σ(x_j)σ^2. (9) Just as in the construction in Section 3, a closed earlier gate removes every later hidden correction. Notice this jointly measurable oracle is fixed once θ is chosen. We need the following fact regarding the accuracy of the constructed oracle. Figure 2: The anisotropic box construction. In coordinate i, the public candidate intervals lie in [ai,2ai][a_i,2a_i], and the shaded interval Ii(θi)I_i( _i) is selected by an independent uniform label θi _i. The target is uniform on their Cartesian product. Both the coordinate scales and the interval lengths decrease by a factor of q at each step. Only representative candidates are shown; scales are schematic. Lemma 4.2 (Accuracy of the gated oracle). For every instance θ, the oracle in (9) satisfies the score-error guarantee (2) at every noise level σ>0σ>0. We provide the complete proof in Section B.2. Additionally, we need the following simulation lemma to prove the lower bound. Lemma 4.3 (One new coordinate per round). Let a sampler use R<dR<d rounds. Its actual output Y can be coupled to an output Y~ Y depending only on the sampler’s random seed and θ1,…,θR _1,…, _R, such that [Y≠Y~]≤RPM. Pr\/[Y≠ Y]≤ RPM. The complete statement and proof appear in Section B.3. With these lemmas in hand, we are ready to prove Theorem 4.1. Proof of Theorem 4.1. The construction and Lemma 4.2 give the required targets and oracles. Fix a sampler using R<dR<d rounds and couple its output as in Lemma 4.3. Conditional on the first R labels and the seed, Y~R+1 Y_R+1 is fixed and θR+1 _R+1 remains uniform. Since the candidate intervals are disjoint, [Y~∈Kθ]≤[Y~R+1∈IR+1(θR+1)]≤1M. Pr\/[ Y∈ K^θ]≤ Pr\/[ Y_R+1∈ I_R+1( _R+1)]≤ 1M. The coupling therefore gives θ[Qθ(Kθ)]=[Y∈Kθ]≤RP+1M.E_θ[Q^θ(K^θ)]= Pr\/[Y∈ K^θ]≤ RP+1M. The choice of M in Section B.1 makes this at most 0.010.01 for every R<dR<d. By Markov’s inequality, Qθ(Kθ)≤0.1Q^θ(K^θ)≤ 0.1 with probability at least 0.90.9 over θ. For each such instance, πθ(Kθ)=1π^θ(K^θ)=1, and hence dTV(Qθ,πθ)≥πθ(Kθ)−Qθ(Kθ)≥0.9.d_TV(Q^θ,π^θ)≥π^θ(K^θ)-Q^θ(K^θ)≥ 0.9. This is the claimed probability bound. ∎ Finally, we prove a matching upper bound. In particular, we show that for the same parameter choice, the selected intervals can also be recovered one coordinate at a time. Lemma 4.4 (Upper bound for the same target family). For sufficiently large d, every target in the constructed family can be sampled to total variation error at most 1/101/10 using O(d)O(d) rounds and O(logd)O( d) queries per round, for every fixed legal oracle. The algorithm recovers the selected intervals one coordinate at a time, then samples uniformly from their product. The key observation here is that xi+σ2si,σθ(x)x_i+σ^2s^θ_i,σ(x) lies in the unknown interval. Thus, using the previously recovered intervals, we can construct randomized queries at noise comparable to our current uncertainty level. Taking the median of O(logd)O( d) approximate posterior means gives a more accurate center estimate. For our choice of parameters, O(1)O(1) refinements per coordinate suffice to identify the selected interval, giving O(d)O(d) rounds. We provide details of the algorithm and analysis in Section B.4. 5 Conclusion and future directions We establish polynomial lower bounds on the number of sequential rounds needed for diffusion sampling with approximate scores. For a fixed polynomial query budget per round, we prove a Ω~(d1/3) (d^1/3) lower bound for smooth, near-isotropic Gaussian mixtures and an Ω(d) (d) lower bound for anisotropic boxes. The latter matches an O(d)O(d)-round algorithm for our box family. Our constructions encode hidden information in an ordered sequence of blocks and use fixed approximate oracles whose informative responses about later blocks require knowledge of earlier ones. The mean-square error guarantee allows the oracles to suppress information on atypical queries while remaining accurate under the smoothed target distribution at every noise level. A progressive simulation argument shows that, with high probability, the answers to each batch of polynomially many queries can be simulated by exposing at most one additional block. We then show that leaving a block unrevealed prevents accurate sampling, yielding a lower bound proportional to the number of blocks. Our results suggest several directions for future work. 1. Tightening the near-isotropic bounds. For our near-isotropic Gaussian mixture family, a polynomial gap remains between the Ω~(d1/3) (d^1/3) lower bound and the O~(d5/6) O(d^5/6) upper bound obtained by specializing the analysis of [8]. Since this upper bound uses a sequential algorithm, exploiting parallel queries may reduce the number of rounds. On the lower bound side, can a sharper analysis or a modified construction improve the exponent? 2. Near-isotropic convex bodies. Our box construction gives a linear lower bound for uniform sampling from convex bodies, but its proof relies on strong anisotropy. Can polynomial round lower bounds also be established for uniform sampling from near-isotropic convex bodies using approximate score oracles? This would show that convexity and near-isotropy together do not suffice for efficient parallel sampling in this model. 3. Relating sequential and parallel lower bounds. The Ω~(d1/2) (d^1/2) sequential query lower bound of [51] raises the question of whether a comparable parallel round lower bound holds for near-isotropic targets. More generally, when can techniques for sequential query lower bounds be adapted to withstand polynomially many queries per round? The counting-oracle setting provides another context for studying this relationship [3, 1]. 4. Other oracle models. Do polynomial parallel lower bounds hold for exact score oracles, or for approximate scores satisfying uniform pointwise error guarantees at every noise level? More broadly, it would be interesting to determine the optimal round complexity of sampling from convex bodies using membership queries and from log-concave distributions using approximate first-order queries. How do these bounds depend on conditioning and oracle accuracy, and when can reductions from optimization to sampling transfer parallel lower bounds while preserving the relevant oracle guarantees and round complexity? Acknowledgments. We thank Raghu Meka for helpful discussions throughout the project. We also thank Sitan Chen and Liye Wang for valuable discussions and insights. AI Acknowledgment. The authors have engaged in ongoing discussions with ChatGPT since December 2025. The Ω~(d1/3) (d^1/3) construction was proposed by the authors, and ChatGPT assisted with formalizing and completing the proof. The box construction yielding the Ω(d) (d) lower bound arose during discussions of sampling from convex sets. ChatGPT also assisted with exploratory discussions of possible reductions from optimization to sampling. GPT-6 further assisted with revising the exposition. The authors take full responsibility for the results and presentation of this work. References [ABC+26] N. Anari, C. Baronio, C. Chen, A. Haqi, F. Koehler, A. Li, and T. Vuong (2026) Parallel sampling via autospeculation. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), p. 1168–1179. External Links: Document, Link Cited by: §1.1, §1.1, §1.2, §1, item 3. [ACV24a] N. Anari, S. Chewi, and T. Vuong (2024) Fast parallel sampling under isoperimetry. In Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 247, p. 161–185. External Links: Link Cited by: §1.2. [AGR24b] N. Anari, R. Gao, and A. Rubinstein (2024) Parallel sampling via counting. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), p. 537–548. External Links: Document, Link Cited by: §1.1, §1.2, §3, item 3. [BDD+24] J. Benton, V. De Bortoli, A. Doucet, and G. Deligiannidis (2024) Nearly d-linear convergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1.2, §1. [BRL+23] A. Blattmann, R. Rombach, H. Ling, T. Dockhorn, S. W. Kim, S. Fidler, and K. Kreis (2023) Align your latents: high-resolution video synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 22563–22575. External Links: Document, Link Cited by: §1. [BHE23] T. Brooks, A. Holynski, and A. A. Efros (2023) InstructPix2Pix: learning to follow image editing instructions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 18392–18402. External Links: Link Cited by: §1. [CBL22] N. S. Chatterji, P. L. Bartlett, and P. M. Long (2022) Oracle lower bounds for stochastic gradient sampling algorithms. Bernoulli 28 (2), p. 1074–1092. External Links: Document, Link Cited by: §1.2. [CCD+26] F. Chen, S. Chewi, C. Daskalakis, and A. Rakhlin (2026) High-accuracy sampling for diffusion models and log-concave distributions. In Proceedings of the International Conference on Machine Learning, External Links: Link Cited by: §A.6, §A.6, §A.6, §1.1, §1.2, §1, §3.3, §3.3, item 1. [CRY+24] H. Chen, Y. Ren, L. Ying, and G. M. Rotskoff (2024) Accelerating diffusion models with parallel sampling: inference at sub-linear time complexity. In Advances in Neural Information Processing Systems, Vol. 37, p. 133661–133709. External Links: Document, Link Cited by: §A.6, §1.2, §1, §1. [CCL+23] S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang (2023) Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, External Links: Link Cited by: §1.2. [CW26] S. Chen and L. Wang (2026) Parallelism, critical windows, and separations among diffusion language models. Note: arXiv:2609.20539 External Links: 2609.20539, Link Cited by: §1.2. [CdL+24] S. Chewi, J. de Dios Pont, J. Li, C. Lu, and S. Narayanan (2024) Query lower bounds for log-concave sampling. Journal of the ACM 71 (4), p. 29:1–29:42. External Links: Document, Link Cited by: §1.1, §1.2. [CGL+23] S. Chewi, P. Gerber, H. Lee, and C. Lu (2023) Fisher information lower bounds for sampling. In Proceedings of the 34th International Conference on Algorithmic Learning Theory, Proceedings of Machine Learning Research, Vol. 201, p. 375–410. External Links: Link Cited by: §1.2. [CGL+22] S. Chewi, P. R. Gerber, C. Lu, T. Le Gouic, and P. Rigollet (2022) The query complexity of sampling from strongly log-concave distributions in one dimension. In Proceedings of Thirty Fifth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 178, p. 2041–2059. External Links: Link Cited by: §1.2. [DN21] P. Dhariwal and A. Nichol (2021) Diffusion models beat GANs on image synthesis. In Advances in Neural Information Processing Systems, Vol. 34, p. 8780–8794. External Links: Link Cited by: §1. [EFR11] B. Efron (2011) Tweedie’s formula and selection bias. Journal of the American Statistical Association 106 (496), p. 1602–1614. External Links: Document, Link Cited by: §2. [GRV15] N. Goyal, L. Rademacher, and S. Vempala (2015) Query complexity of sampling and small geometric partitions. Combinatorics, Probability and Computing 24 (5), p. 733–753. External Links: Document, Link Cited by: §1.2. [GYR+24] Y. Guo, C. Yang, A. Rao, Z. Liang, Y. Wang, Y. Qiao, M. Agrawala, D. Lin, and B. Dai (2024) AnimateDiff: animate your personalized text-to-image diffusion models without specific tuning. In The Twelfth International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. [GCC25] S. Gupta, L. Cai, and S. Chen (2025) Faster diffusion sampling with randomized midpoints: sequential and parallel. In The Thirteenth International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1.2, §1. [HZ25] Y. He and C. Zhang (2025) On the query complexity of sampling from non-log-concave distributions (extended abstract). In Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 291, p. 2786–2787. External Links: Link, 2502.06200 Cited by: §1.2. [HMT+23] A. Hertz, R. Mokady, J. Tenenbaum, K. Aberman, Y. Pritch, and D. Cohen-Or (2023) Prompt-to-prompt image editing with cross-attention control. In The Eleventh International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. [HJA20] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, Vol. 33, p. 6840–6851. External Links: Link Cited by: §1, §1, §1, §1. [HSG+22] J. Ho, T. Salimans, A. Gritsenko, W. Chan, M. Norouzi, and D. J. Fleet (2022) Video diffusion models. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 35, p. 8633–8646. External Links: Document, Link Cited by: §1. [HDS+25] H. Hu, A. Das, D. Sadigh, and N. Anari (2025) Diffusion models are secretly exchangeable: parallelizing DDPMs via auto speculation. In Proceedings of the 42nd International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, Vol. 267, p. 24270–24289. External Links: Link Cited by: §1.2, §1. [JLL+26] H. Jia, A. Laddha, Y. T. Lee, and S. Vempala (2026) Reducing isotropy and volume to KLS: faster rounding and volume algorithms. Journal of the ACM 73 (2). External Links: Document, 2008.02146 Cited by: §1.1. [KUW85] R. M. Karp, E. Upfal, and A. Wigderson (1985) The complexity of parallel computation on matroids. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), p. 541–550. External Links: Document, Link Cited by: §1.1, §1.2, §3. [KUW88] R. M. Karp, E. Upfal, and A. Wigderson (1988) The complexity of parallel search. Journal of Computer and System Sciences 36 (2), p. 225–253. External Links: Document, Link Cited by: §1.2. [KEE+22] B. Kawar, M. Elad, S. Ermon, and J. Song (2022) Denoising diffusion restoration models. In Advances in Neural Information Processing Systems, Vol. 35, p. 23593–23606. External Links: Link Cited by: §1. [LLT23] H. Lee, J. Lu, and Y. Tan (2023) Convergence of score-based generative modeling for general data distributions. In Proceedings of the 34th International Conference on Algorithmic Learning Theory, Proceedings of Machine Learning Research, Vol. 201, p. 946–985. External Links: Link Cited by: §1.2. [LY25] G. Li and Y. Yan (2025) O(d/T)O(d/T) convergence theory for diffusion probabilistic models under minimal assumptions. Journal of Machine Learning Research 26 (292), p. 1–55. External Links: Link Cited by: §1.2. [LRL+22] L. Liu, Y. Ren, Z. Lin, and Z. Zhao (2022) Pseudo numerical methods for diffusion models on manifolds. In The Tenth International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. [LV06] L. Lovász and S. Vempala (2006) Hit-and-run from a corner. SIAM Journal on Computing 35 (4), p. 985–1005. External Links: Document, Link Cited by: §1.1. [LZB+22] C. Lu, Y. Zhou, F. Bao, J. Chen, C. Li, and J. Zhu (2022) DPM-Solver: a fast ODE solver for diffusion probabilistic model sampling in around 10 steps. In Advances in Neural Information Processing Systems, Vol. 35, p. 5775–5787. External Links: Document, Link Cited by: §1. [LDR+22] A. Lugmayr, M. Danelljan, A. Romero, F. Yu, R. Timofte, and L. Van Gool (2022) RePaint: inpainting using denoising diffusion probabilistic models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 11451–11461. External Links: Document, Link Cited by: §1. [MHS+22] C. Meng, Y. He, Y. Song, J. Song, J. Wu, J. Zhu, and S. Ermon (2022) SDEdit: guided image synthesis and editing with stochastic differential equations. In The Tenth International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. [NDR+22] A. Q. Nichol, P. Dhariwal, A. Ramesh, P. Shyam, P. Mishkin, B. McGrew, I. Sutskever, and M. Chen (2022) GLIDE: towards photorealistic image generation and editing with text-guided diffusion models. In Proceedings of the 39th International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, Vol. 162, p. 16784–16804. External Links: Link Cited by: §1. [PX23] W. Peebles and S. Xie (2023) Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), p. 4195–4205. External Links: Link Cited by: §1. [ROB56] H. Robbins (1956) An empirical Bayes approach to statistics. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, p. 157–163. Cited by: §2. [RBL+22] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer (2022) High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 10674–10685. External Links: Document, Link Cited by: §1, §1. [SCC+22a] C. Saharia, W. Chan, H. Chang, C. A. Lee, J. Ho, T. Salimans, D. J. Fleet, and M. Norouzi (2022) Palette: image-to-image diffusion models. In ACM SIGGRAPH 2022 Conference Proceedings, p. 1–10. External Links: Document, Link Cited by: §1. [SCS+22b] C. Saharia, W. Chan, S. Saxena, L. Li, J. Whang, E. L. Denton, K. Ghasemipour, R. Gontijo Lopes, B. Karagol Ayan, T. Salimans, J. Ho, D. J. Fleet, and M. Norouzi (2022) Photorealistic text-to-image diffusion models with deep language understanding. In Advances in Neural Information Processing Systems, Vol. 35, p. 36479–36494. External Links: Link Cited by: §1, §1. [SHC+23] C. Saharia, J. Ho, W. Chan, T. Salimans, D. J. Fleet, and M. Norouzi (2023) Image super-resolution via iterative refinement. IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (4), p. 4713–4726. External Links: Document, Link Cited by: §1. [SL19] R. Shen and Y. T. Lee (2019) The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems, Vol. 32, p. 2100–2111. External Links: Link Cited by: §1.2. [SBE+23] A. Shih, S. Belkhale, S. Ermon, D. Sadigh, and N. Anari (2023) Parallel sampling of diffusion models. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Document, Link Cited by: §1.2, §1. [SPH+23] U. Singer, A. Polyak, T. Hayes, X. Yin, J. An, S. Zhang, Q. Hu, H. Yang, O. Ashual, O. Gafni, D. Parikh, S. Gupta, and Y. Taigman (2023) Make-A-Video: text-to-video generation without text-video data. In The Eleventh International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. [SWM+15] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli (2015) Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, Vol. 37, p. 2256–2265. External Links: Link Cited by: §1, §1. [SME21] J. Song, C. Meng, and S. Ermon (2021) Denoising diffusion implicit models. In International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1, §1, §1. [SE19] Y. Song and S. Ermon (2019) Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, Vol. 32, p. 11918–11930. External Links: Link Cited by: §1, §1, §1. [TTL+24] Z. Tang, J. Tang, H. Luo, F. Wang, and T. Chang (2024) Accelerating parallel sampling of diffusion models. In Proceedings of the 41st International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, Vol. 235, p. 47800–47818. External Links: Link Cited by: §1. [VEM26] S. S. Vempala (2026) A nearly quadratic lower bound for linear optimization over convex bodies in the membership oracle model. Note: arXiv preprint arXiv:2609.30215 External Links: 2609.30215 Cited by: §1.2. [XP26] Z. Xun and E. Price (2026) Query lower bounds for diffusion sampling. In ICLR 2026 Workshop on Deep Generative Models in Machine Learning, External Links: Link Cited by: §A.2, §A.2, §A.2, §A.2, §A.2, Lemma A.3, Lemma A.5, Lemma A.6, §1.1, §1.2, §1, §3, §3, §3.1, item 3. [ZRA23] L. Zhang, A. Rao, and M. Agrawala (2023) Adding conditional control to text-to-image diffusion models. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), p. 3836–3847. External Links: Link Cited by: §1. [ZBR+23] W. Zhao, L. Bai, Y. Rao, J. Zhou, and J. Lu (2023) UniPC: a unified predictor-corrector framework for fast sampling of diffusion models. In Advances in Neural Information Processing Systems, Vol. 36, p. 49842–49869. External Links: Document, Link Cited by: §1. [ZS25] H. Zhou and M. Sugiyama (2025) Parallel simulation for log-concave sampling and score-based diffusion models. In Proceedings of the 42nd International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, Vol. 267, p. 79192–79225. External Links: Link Cited by: §1.2, §1. Appendix A Deferred proofs from Section 3 We now provide details of omitted proofs from Section 3. Shared notation and instance law. As in Section 3, d is the ambient dimension, B is the number of hidden blocks, and m=⌊d/B⌋m= d/B is their common dimension. Set dpad=d−Bmd_pad=d-Bm. The padding coordinates are independent uniform signs; when dpad=0d_pad=0, their law is the unit mass on the zero-dimensional space. For a nonempty codebook Sj⊆−1,+1mS_j \-1,+1\^m, write nj=|Sj|n_j=|S_j| and κj=(lognj)/m _j=( n_j)/m. For the full instance S=(S1,…,SB)S=(S_1,…,S_B) and any τ>0τ>0, define μS=(⨂j=1BUnif(Sj))⊗Unif(−1,+1dpad),πτS=μS∗(0,τ2Id).μ^S= ( _j=1^BUnif(S_j) ) (\-1,+1\^d_pad), π^S_τ=μ^S*N(0,τ^2I_d). (10) Fix a target smoothing parameter γ>0γ>0, and set πS=πγS,sτS=∇logπτS,(πS)(σ)=πγ2+σ2S.π^S=π^S_γ, s^S_τ=∇ π^S_τ, (π^S)^(σ)=π^S_ γ^2+σ^2. (11) Thus σ>0σ>0 is the additional query noise, while τ=γ2+σ2τ= γ^2+σ^2 is total noise. The target itself is at τ=γτ=γ. When a random instance is used, its codebooks are independent, and SjS_j is uniform among all njn_j-element subsets of the cube. All instance probabilities refer to this unconditioned product law unless conditioning is explicitly indicated. In particular, P denotes only the query budget, not a probability law. We use S for a single codebook in one-block statements and for a tuple in full-dimensional statements. All logarithms are natural. Polynomial bounds. We write P=(d)≥1P= poly(d)≥ 1 for a fixed public polynomial query budget and εscore=(d)−1 _score= poly(d)^-1 for a fixed inverse-polynomial score accuracy tending to zero. All such polynomial bounds are fixed before the instance family is chosen. Implicit constants may depend on them. An assumption ρ≥(d)−1ρ≥ poly(d)^-1 similarly fixes a polynomial lower bound on the failure tolerance. A.1 Parameters and near-isotropy We specify the public parameters and prove that the targets are near-isotropic. Fix γ>0γ>0, a score accuracy εscore=(d)−1 _score= poly(d)^-1, a query budget P=(d)P= poly(d), and (d)−1≤ρ≤1/10 poly(d)^-1≤ρ≤ 1/10. Constants may depend on these bounds, on γ, and on the fixed rate interval below, but not on the algorithm or sampled instance. As in Section 3, let αγ=MI(U,U+γZ) _γ=MI(U;U+γ Z), for independent U∼Unif(−1,+1)U (\-1,+1\) and Z∼(0,1)Z (0,1). Fix 0<κmin<κmax<αγ,c0=αγ−κmax2.0< _ < _ < _γ, c_0= _γ- _ 2. For any proposed dimensions 1≤B≤d1≤ B≤ d and max2,2γ≤m≤d \2, 2\,γ\≤ m≤ d, set δ=ρ2100Pd3,η=εscore8B,ζ(τ)=minρ2100,η2τ216m(τ≥γ).δ= ρ^2100Pd^3, η= _score8B, ζ(τ)= \ ρ^2100, η^2τ^216m \ (τ≥γ). (12) These are the hiding, local score-error, and gate-failure budgets. We collect their logarithms in a single quantity: H=1+log(16em2log(1+2m)δγ2η2)+log1ζ(γ).H=1+ \! ( 16em^2 (1+2^m)δγ^2η^2 )+ 1ζ(γ). (13) Uniformly over these dimensions, the logarithms of the reciprocal budgets are O(logd)O( d), and H=Θ(logd)H= ( d). Lemma A.1 (Public parameter choice). For all sufficiently large d, there are public integers B,n1,…,nBB,n_1,…,n_B such that, with m=⌊d/B⌋m= d/B , B=Θ((d/logd)1/3),m=Θ(d2/3(logd)1/3),H=Θ(logd).B= \! ((d/ d)^1/3 ), m= \! (d^2/3( d)^1/3 ), H= ( d). (14) Each njn_j is a power of two, the rates κj=(lognj)/m _j=( n_j)/m belong to [κmin,κmax][ _ , _ ], and κj+1−κj≥κmax−κmin2B(j<B). _j+1- _j≥ _ - _ 2B (j<B). (15) The constant factor in B can be chosen so that these gaps exceed any prescribed constant multiple of H/m+H/m H/m+H/m. The product has public cardinality Nd=2dpad∏jnj=exp(Θ(d))N_d=2^d_pad _jn_j= ( (d)). Furthermore, m≥max2,2γm≥ \2, 2\,γ\ and 1γ8log(1/ζ(γ))m≤c0,ζ(γ),e−c0m≤ρ2100,RPBδ≤ρ2100d(0≤R<B). gathered 1γ 8 (1/ζ(γ))m≤ c_0, ζ(γ),\ e^-c_0m≤ ρ^2100, RPBδ≤ ρ^2100d (0≤ R<B). gathered (16) All choices are independent of the algorithm and sampled codebooks. Proof. Choose B to be a sufficiently small constant multiple of (d/logd)1/3(d/ d)^1/3, rounded down, and set m=⌊d/B⌋m= d/B . This gives (14). Define nj=2⌈mlog2(κmin+j−1B(κmax−κmin))⌉.n_j=2 m 2 ( _ + j-1B( _ - _ ) ) . (17) Rounding changes each prescribed rate by less than log2/m 2/m. Consequently, for sufficiently large d, all rates lie in the fixed interval and κj+1−κj≥κmax−κminB−log2m≥κmax−κmin2B. _j+1- _j≥ _ - _ B- 2m≥ _ - _ 2B. Since H=O(logd)H=O( d) and m=Θ(d/B)m= (d/B), B(Hm+Hm)=O(B3logd+B2logd).B ( Hm+ Hm )=O\! ( B^3 dd+ B^2 dd ). The first term is as small as needed by the choice of the constant in B, while the second and B/mB/m tend to zero. This proves (15) and the claimed separation. In particular, the gaps can be made larger than the uniform transition width proved in Lemma A.11. Its implicit constant depends only on γ; the logarithmic budget is bounded uniformly before B is chosen. Moreover, logNd=dpadlog2+m∑j=1Bκj=Θ(d), N_d=d_pad 2+m _j=1^B _j= (d), (18) because Bm=d−O(B)Bm=d-O(B) and the rates stay in a fixed positive interval. Finally, H/m→0H/m→ 0 proves the first margin in (16), and m/logd→∞m/ d→∞ makes e−c0me^-c_0m smaller than the inverse-polynomial quantity ρ2/100ρ^2/100. The gate-failure bound is immediate from its definition. Since R,B≤dR,B≤ d, the hiding budget gives RPBδ≤d2Pδ=ρ2/(100d)RPBδ≤ d^2Pδ=ρ^2/(100d). ∎ Instance law and geometry. Choose the codebooks independently, with SjS_j uniform among the njn_j-element subsets of −1,+1m\-1,+1\^m. Use the center law and target from (10)–(11). Each target is an equal-weight mixture of exactly NdN_d distinct centers with common component covariance γ2Idγ^2I_d. Lemma A.2 (Near-isotropy). For the public parameters above, define G=S:∥πSX∥2≤d−10,∥Cov(πS)−(1+γ2)Id∥op≤d−10.G= \S:\|E_π^SX\|_2≤ d^-10, \|Cov(π^S)-(1+γ^2)I_d\|_op≤ d^-10 \. (19) Then S(Gc)≤exp(−Ω(m)) Pr\/_S(G^c)≤ (- (m)). More generally, for arbitrary prescribed codebook sizes and every t∈(0,1]t∈(0,1], the probability that either norm in (19) exceeds t is at most 4m2t−2∑jnj−14m^2t^-2 _jn_j^-1. Proof. Write vj=1nj∑y∈Sjy,Mj=1nj∑y∈Sjyy⊤,v=(v1,…,vB,0dpad).v_j= 1n_j _y∈ S_jy, M_j= 1n_j _y∈ S_jy , v=(v_1,…,v_B,0_d_pad). For any mean-zero, variance-one function f on the cube, sampling without replacement gives S(1n∑y∈Sf(y))2=2m−n(2m−1)≤1n.E_S ( 1n _y∈ Sf(y) )^2= 2^m-nn(2^m-1)≤ 1n. (20) Indeed, for a uniform ordered distinct pair, f(Y)f(Y′)=−1/(2m−1)Ef(Y)f(Y )=-1/(2^m-1). Apply this identity to yay_a and yayby_ay_b for a≠ba≠ b. The diagonal entries of MjM_j are one, so ZS:=‖v‖22+∑j‖Mj−Im‖F2,SZS≤m2∑j1nj.Z_S:=\|v\|_2^2+ _j\|M_j-I_m\|_F^2, _SZ_S≤ m^2 _j 1n_j. (21) For every fixed instance, πSX=v,Cov(πS)=diag(M1−v1v1⊤,…,MB−vBvB⊤,Idpad)+γ2Id.E_π^SX=v, (π^S)=diag(M_1-v_1v_1 ,…,M_B-v_Bv_B ,I_d_pad)+γ^2I_d. If ZS≤t2/4Z_S≤ t^2/4, then the mean has norm at most t/2t/2 and ‖Cov(πS)−(1+γ2)Id‖op≤ZS+ZS≤t/2+t2/4≤t.\|Cov(π^S)-(1+γ^2)I_d\|_op≤ Z_S+Z_S≤ t/2+t^2/4≤ t. Markov’s inequality therefore gives S[either norm exceeds t]≤4m2t2∑j1nj. Pr\/_S[either norm exceeds t]≤ 4m^2t^2 _j 1n_j. (22) For the chosen sizes, nj≥eκminmn_j≥ e _ m and Bm≤dBm≤ d. Taking t=d−10t=d^-10 yields S(Gc)≤4d21me−κminm=exp(−Ω(m)) Pr\/_S(G^c)≤ 4d^21me^- _ m= (- (m)). ∎ Public rescaling and the probability convention. Let c=(1+γ2)−1/2c=(1+γ^2)^-1/2 and π¯S=ℒ(cX) π^S=L(cX) for X∼πSX π^S. On G, its mean has norm at most d−10d^-10 and ‖Cov(π¯S)−Id‖op≤d−10\|Cov( π^S)-I_d\|_op≤ d^-10. Its NdN_d components have common covariance γ2(1+γ2)−1Idγ^2(1+γ^2)^-1I_d. Given a legal oracle s^S s^S in the additional-noise parameterization, define s¯^S(x,σ)=c−1s^S(x/c,σ/c). s^S(x,σ)=c^-1 s^S(x/c,σ/c). The true score has the same transformation. Thus X∼(π¯S)(σ)‖s¯^S(X,σ)−sπ¯S,σ(X)‖22≤c−2εscore2(σ/c)2=εscore2σ2.E_X ( π^S)^(σ)\| s^S(X,σ)-s_ π^S,σ(X)\|_2^2≤ c^-2 _score^2(σ/c)^2= _score^2σ^2. Each transformed query uses one original query. The invertible rescaling preserves total variation and the number of adaptive rounds. Below we work with πSπ^S and the unconditioned independent codebooks; conditioning on G and transferring the lower bound through this rescaling occur after the quantitative TV separation. A.2 Technical inputs from [51] In this subsection, we state variants of technical inputs from [51] we need for the proof. For the one-block estimates, let m≥1m≥ 1, Vm=−1,+1mV_m=\-1,+1\^m, and Um=Unif(Vm)U_m=Unif(V_m). For every nonempty S⊆VmS V_m and noise τ>0τ>0, set pτS=Unif(S)∗(0,τ2Im),qτ=Um∗(0,τ2Im),sτS=∇logpτS,sτ0=∇logqτ.p^S_τ=Unif(S)*N(0,τ^2I_m), q_τ=U_m*N(0,τ^2I_m), s^S_τ=∇ p^S_τ, s^0_τ=∇ q_τ. Thus sτ0s^0_τ is the null score from Section 3. Let φτ _τ be the density of (0,τ2Im)N(0,τ^2I_m), and let Y∼UmY U_m and Z∼(0,Im)Z (0,I_m) be independent. Define Lτ(y,x)=φτ(x−y)qτ(x),ℓτ(y,x)=logLτ(y,x),ατ=1mℓτ(Y,Y+τZ).L_τ(y,x)= _τ(x-y)q_τ(x), _τ(y,x)= L_τ(y,x), _τ= 1mE _τ(Y,Y+τ Z). By the product structure, ατ _τ equals MI(Y0,Y0+τZ0)MI(Y^0;Y^0+τ Z^0) for independent Y0∼Unif(−1,+1)Y^0 (\-1,+1\) and Z0∼(0,1)Z^0 (0,1), exactly as in (5). We write ‖f‖∞,2:=supx‖f(x)‖2\|f\|_∞,2:= _x\|f(x)\|_2 and Lip(f)Lip(f) for the global Euclidean Lipschitz constant. The mixture formula gives Y∼UmLτ(Y,x)=1,Lτ(y,x)≤2m,pτS(x)qτ(x)=1|S|∑y∈SLτ(y,x).E_Y U_mL_τ(Y,x)=1, L_τ(y,x)≤ 2^m, p^S_τ(x)q_τ(x)= 1|S| _y∈ SL_τ(y,x). (23) The numbered results below refer to arXiv:2604.10857v1 of [51]. We use its Gaussian-smoothing identities and KL–Fisher comparison. The without-replacement adaptation is proved here. Lemma A.3 (Posterior score bounds; [51], Proposition B.6). Let ν be supported on [−1,1]m[-1,1]^m, let Y∼νY ν, and let Z∼(0,Im)Z (0,I_m) be independent. For every τ>0τ>0, define sν,τ=∇log(ν∗(0,τ2Im))s_ν,τ=∇ (ν*N(0,τ^2I_m)). Then sν,τ(x) s_ν,τ(x) =[Y∣Y+τZ=x]−xτ2, = E[Y Y+τ Z=x]-xτ^2, (24) ∇sν,τ(x) ∇ s_ν,τ(x) =−Imτ2+Cov(Y∣Y+τZ=x)τ4. =- I_mτ^2+ Cov(Y Y+τ Z=x)τ^4. (25) Consequently, Lip(sν,τ) (s_ν,τ) ≤1τ2+mτ4,‖sτS−sτ0‖∞,2≤2mτ2, ≤ 1τ^2+ mτ^4, \|s^S_τ-s^0_τ\|_∞,2≤ 2 mτ^2, (26) ‖∇xℓτ(y,x)‖2 \| _x _τ(y,x)\|_2 ≤2mτ2(y∈Vm). ≤ 2 mτ^2 (y∈ V_m). (27) Justification of the specialization. The identities and score bounds are the specialization of [XP26], Proposition B.6(a)–(d), with support-radius parameter 11. Posterior means lie in [−1,1]m[-1,1]^m, and the posterior covariance has operator norm at most m. These facts give (26). Finally, ∇xℓτ(y,x)=τ−2(y−Y∼Um[Y∣Y+τZ=x]), _x _τ(y,x)=τ^-2 (y-E_Y U_m[Y Y+τ Z=x] ), which proves (27). ∎ Lemma A.4 (Information-density concentration and nearby noise). For every τ>0τ>0, the law of ℓτ(y,y+τZ) _τ(y,y+τ Z) is the same for all y∈Vmy∈ V_m, and its mean is mατm _τ. For either sign and every t≥0t≥ 0, Z[±(ℓτ(y,y+τZ)−mατ)≥t]≤exp(−τ2t28m). Pr\/_Z\! [± ( _τ(y,y+τ Z)-m _τ )≥ t ]≤ \! (- τ^2t^28m ). (28) For 0<u≤v0<u≤ v, 0≤αu−αv≤log(v/u).0≤ _u- _v≤ (v/u). (29) Proof. Sign symmetry of the cube and Gaussian noise makes the law independent of y. Equation (27) makes z↦ℓτ(y,y+τz)z _τ(y,y+τ z) a 2m/τ2 m/τ-Lipschitz function. Gaussian concentration gives (28). This is the Gaussian-Lipschitz argument used in [51], Proposition B.8(b); the stronger noise-uniform estimates there are not needed. For (29), couple Xu=Y+uZ1X_u=Y+uZ_1 and Xv=Xu+v2−u2Z2X_v=X_u+ v^2-u^2Z_2, with Y∼UmY U_m and independent standard Gaussians Z1,Z2Z_1,Z_2. Data processing gives αu≥αv _u≥ _v. Writing h for differential entropy, independence gives, for u<vu<v, h(Xv)≥h(Xv∣Z2)=h(Xu)h(X_v)≥ h(X_v Z_2)=h(X_u). Equality handles u=vu=v. Thus αu−αv=h(Xu)−h(Xv)+h(vZ1)−h(uZ1)m≤log(v/u). _u- _v= h(X_u)-h(X_v)+h(vZ_1)-h(uZ_1)m≤ (v/u). ∎ KL–Fisher comparison. For γ>0γ>0 and m≥max2,2γm≥ \2, 2\,γ\, define τ~=τ1−γ2m2,Fτ(S)=X∼pτS‖sτS(X)−sτ0(X)‖22. τ=τ 1- γ^2m^2, F_τ(S)=E_X p^S_τ\|s^S_τ(X)-s^0_τ(X)\|_2^2. Here Fτ(S)F_τ(S) is the squared error of the null score on the hidden smoothed distribution. These definitions apply at every positive noise level. Lemma A.5 (KL–Fisher comparison; [51], Proposition B.7(b)). For every nonempty S⊆VmS V_m and every τ≥γτ≥γ, Fτ(S)≤2em2γ2τ2DKL(pτ~S∥qτ~).F_τ(S)≤ 2em^2γ^2τ^2D_KL(p^S_ τ\|q_ τ). (30) Proof. For t>0t>0, put r+(t)=max0,supxλmax(∇2logqt(x))r_+(t)= \0, _x _ (∇^2 q_ t(x))\. The comparison in [51], Proposition B.7(b), gives Fτ(S)≤2(1−λ)τ2exp(2∫λτ2τ2r+(t)dt)DKL(pλτS∥qλτ),0<λ<1.F_τ(S)≤ 2(1-λ)τ^2 \! (2 _λτ^2^τ^2r_+(t)\,dt )D_KL(p^S_ λτ\|q_ λτ), 0<λ<1. (31) For the Boolean reference, ∇2logqt(x)=diagi∈[m](−1t+sech2(xi/t)t2)⪯1t2Im.∇^2 q_ t(x)=diag_i∈[m] (- 1t+ sech^2(x_i/t)t^2 ) 1t^2I_m. Taking λ=1−γ2/m2≥1/2λ=1-γ^2/m^2≥ 1/2 and using τ≥γτ≥γ gives 2∫λτ2τ2r+(t)t≤2(1−λ)λτ2≤4m2≤1.2 _λτ^2^τ^2r_+(t)\,dt≤ 2(1-λ)λτ^2≤ 4m^2≤ 1. Substitution proves the claim. The densities are finite Gaussian mixtures, so the comparison’s heat-flow hypotheses hold. Although τ~ τ may be below γ, the other analytic estimates hold at every positive noise level. ∎ Lemma A.6 (Without-replacement adaptation of [51], Lemma B.10). Let S be a uniformly random n-element subset of VmV_m, with 1≤n≤2m1≤ n≤ 2^m. For every τ>0τ>0 and u≥0u≥ 0, SDKL(pSτ∥qτ) _SD_KL(p^S_τ\|q_τ) ≤Y∼Um,Zlog(1+Lτ(Y,Y+τZ)n) _Y U_m,Z \! (1+ L_τ(Y,Y+τ Z)n ) (32) ≤e−u+log(1+2m)[ℓτ(Y,Y+τZ)≥logn−u]. ≤ e^-u+ (1+2^m) Pr\/[ _τ(Y,Y+τ Z)≥ n-u]. Proof. The source lemma samples codewords independently. For the required without-replacement version, put M=2mM=2^m and give S a uniform random ordering (Y1,…,Yn)(Y_1,…,Y_n). Let X=Y1+τZX=Y_1+τ Z, and put Li=Lτ(Yi,X)L_i=L_τ(Y_i,X). Exchangeability and (23) give SDKL(pτS∥qτ)=log(1n∑i=1nLi).E_SD_KL(p^S_τ\|q_τ)=E \! ( 1n _i=1^nL_i ). Conditional on (Y1,X)(Y_1,X), each YiY_i, i≥2i≥ 2, is uniform on the other M−1M-1 vertices. Since ∑yLτ(y,X)=M _yL_τ(y,X)=M, [Li∣Y1,X]=M−L1M−1.E[L_i Y_1,X]= M-L_1M-1. Conditional Jensen therefore yields SDKL(pτS∥qτ)≤log(L1+(n−1)(M−L1)/(M−1)n)≤log(1+L1/n).E_SD_KL(p^S_τ\|q_τ) \! ( L_1+(n-1)(M-L_1)/(M-1)n ) (1+L_1/n). For the last inequality, discard the nonpositive term −(n−1)L1/(M−1)-(n-1)L_1/(M-1) and use (n−1)M/(M−1)≤n(n-1)M/(M-1)≤ n. The marginal law of (Y1,X)(Y_1,X) is the planted law in the statement. Since L1≤ML_1≤ M, the logarithm is at most e−ue^-u on logL1<logn−u\ L_1< n-u\ and at most log(1+M) (1+M) on its complement. This proves the second inequality. No independence among the remaining codewords is used. ∎ A.3 Proof of Lemma 3.2 Lemma A.7 (Complete version of Lemma 3.2). Fix γ>0γ>0, 0<εscore≤10< _score≤ 1, 0<ρ≤1/100<ρ≤ 1/10, and integers 1≤B≤d1≤ B≤ d for which m=⌊d/B⌋≥max2,2γm= d/B ≥ \2, 2\,γ\. The codebooks S1,…,SBS_1,…,S_B may be any fixed nonempty subsets of −1,+1m\-1,+1\^m. Put η=εscore8B,ζ(τ)=minρ2100,η2τ216m(τ≥γ).η= _score8B, ζ(τ)= \ ρ^2100, η^2τ^216m \ (τ≥γ). (33) For every nonempty one-block codebook S, use the quantities of Section A.2 to define tτ=mατ−1τ8mlog1ζ(τ).t_τ=m _τ- 1τ 8m 1ζ(τ). (34) aτS(x)=min1,max0,1+maxy∈Sℓτ(y,x)−tτ.a^S_τ(x)= \1, \0,1+ _y∈ S _τ(y,x)-t_τ \ \. (35) bτS(x)=sτ0(x),Fτ(S)≤η2/(4τ2),sτS(x),Fτ(S)>η2/(4τ2).b^S_τ(x)= casess^0_τ(x),&F_τ(S)≤η^2/(4τ^2),\\ s^S_τ(x),&F_τ(S)>η^2/(4τ^2). cases (36) For the product instance, define, for j∈[B]j∈[B], s^j,τS(x)=sτ0(xj)+(∏i<jaτSi(xi))(bτSj(xj)−sτ0(xj)), s^S_j,τ(x)=s^0_τ(x_j)+ ( _i<ja^S_i_τ(x_i) ) (b^S_j_τ(x_j)-s^0_τ(x_j) ), (37) and use the exact score on the public padding coordinates. The empty product is one. The resulting field is fixed once S is chosen, and satisfies, for every τ≥γτ≥γ, X∼πτS‖s^τS(X)−sτS(X)‖22≤B(B+1)η28τ2≤εscore2256τ2.E_X π^S_τ\| s^S_τ(X)-s^S_τ(X)\|_2^2≤ B(B+1)η^28τ^2≤ _score^2256τ^2. (38) Consequently s^S(x,σ)=s^γ2+σ2S(x) s^S(x,σ)= s^S_ γ^2+σ^2(x) is a legal oracle for πSπ^S at score accuracy εscore _score. The distinction between the two branches of (36) is important. If a block uses the null score, its error is already small. Otherwise it uses the exact local score, and its only error comes from an earlier gate failing. We first establish the two bounds needed for this calculation. At a fixed total noise, the main text abbreviates sj=sτSjs_j=s^S_j_τ, s0=sτ0s^0=s^0_τ, aj=aτSja_j=a^S_j_τ, and bj=bτSjb_j=b^S_j_τ. Lemma A.8 (Fixed-instance local estimates). For every nonempty one-block codebook S and every τ≥γτ≥γ, pτS[aτS=1] p^S_τ[a^S_τ=1] ≥1−ζ(τ), ≥ 1-ζ(τ), (39) pτS‖bτS−sτS‖22 _p^S_τ\|b^S_τ-s^S_τ\|_2^2 ≤η24τ2,‖bτS−sτ0‖∞,2≤2mτ2. ≤ η^24τ^2, \|b^S_τ-s^0_τ\|_∞,2≤ 2 mτ^2. (40) Proof. Generate X=Y+τZX=Y+τ Z, with Y∼Unif(S)Y (S) and Z∼(0,Im)Z (0,I_m) independent. Conditional on Y=yY=y, Lemma A.4 and the choice of tτt_τ imply Z[ℓτ(y,y+τZ)<tτ]≤exp(−τ28m8mlog(1/ζ(τ))τ2)=ζ(τ). Pr\/_Z[ _τ(y,y+τ Z)<t_τ]≤ \! (- τ^28m 8m (1/ζ(τ))τ^2 )=ζ(τ). Since y∈Sy∈ S, on the complementary event the maximum in (35) is at least tτt_τ and the gate equals one. Averaging over the generating codeword proves (39). This argument is for every fixed S; no randomness of the codebook is required. If the first branch of (36) is selected, its squared error is Fτ(S)≤η2/(4τ2)F_τ(S)≤η^2/(4τ^2). In the second branch its error is zero. Also bτS−sτ0b^S_τ-s^0_τ is either zero or sτS−sτ0s^S_τ-s^0_τ, so Lemma A.3 gives the uniform size bound. Finite Gaussian-mixture densities are positive and smooth, and their scores are jointly continuous in (x,τ)(x,τ) for τ>0τ>0. The function ατ _τ is continuous by (29); ζ and tτt_τ are continuous as well. Hence the gates are jointly continuous. To verify the response switch, express Fτ(S)F_τ(S) using X=Y+τZX=Y+τ Z, where the law of (Y,Z)(Y,Z) does not depend on τ. On a compact interval [a,b]⊂(0,∞)[a,b]⊂(0,∞) its integrand is continuous and bounded by 4m/a44m/a^4, by Lemma A.3. Dominated convergence makes Fτ(S)F_τ(S) continuous. The switch need not be continuous in τ. ∎ Proof of Lemma A.7. Fix a full instance S and a total noise τ≥γτ≥γ. For X∼πτSX π^S_τ, the true score in block j is sτSj(Xj)s^S_j_τ(X_j), since smoothing preserves the product structure. The padding contributes no error. If bτSj≡sτ0b^S_j_τ≡ s^0_τ, the response in block j is always sτ0s^0_τ, regardless of the prefix gates. Its expected squared error is at most η2/(4τ2)η^2/(4τ^2). Otherwise bτSj≡sτSjb^S_j_τ≡ s^S_j_τ, and the error equals (1−∏i<jaτSi(Xi))(sτ0(Xj)−sτSj(Xj)). (1- _i<ja^S_i_τ(X_i) ) (s^0_τ(X_j)-s^S_j_τ(X_j) ). Its squared norm is at most 4m/τ44m/τ^4 and is zero when every preceding gate equals one. By (39) and a union bound, the probability that at least one of those gates fails is at most (j−1)ζ(τ)(j-1)ζ(τ). In either branch, the block’s expected squared error is bounded by η24τ2+4m(j−1)ζ(τ)τ4. η^24τ^2+ 4m(j-1)ζ(τ)τ^4. Summing over the orthogonal coordinate blocks gives ‖s^τS(X)−sτS(X)‖22 \| s^S_τ(X)-s^S_τ(X)\|_2^2 ≤Bη24τ2+2mB(B−1)ζ(τ)τ4 ≤ Bη^24τ^2+ 2mB(B-1)ζ(τ)τ^4 ≤B(B+1)η28τ2=B+1512Bεscore2τ2≤εscore2256τ2. ≤ B(B+1)η^28τ^2= B+1512B _score^2τ^2≤ _score^2256τ^2. Here the second inequality uses ζ(τ)≤η2τ2/(16m)ζ(τ)≤η^2τ^2/(16m) and the equality uses η=εscore/(8B)η= _score/(8B). Joint measurability follows from Lemma A.8 by finite products and sums, together with the exact padding score. All branches depend only on S and τ, never on the algorithm or its transcript. Finally, τ2=γ2+σ2≥σ2τ^2=γ^2+σ^2≥σ^2 converts (38) into the additional-noise guarantee (1). ∎ Lipschitzness of the oracle. For completeness, the explicit oracle is also spatially Lipschitz at each fixed noise level. This is not an assumption of our oracle model. The finite maximum and clipping in the gate preserve the bound in (27), so Lip(aτS)≤2mτ2,Lip(bτS)≤1τ2+mτ4.Lip(a^S_τ)≤ 2 mτ^2, (b^S_τ)≤ 1τ^2+ mτ^4. (41) To see the full-dimensional bound, put ri=‖xi−yi‖2r_i=\|x_i-y_i\|_2 and telescope the product of prefix gates. For factors in [0,1][0,1], |∏iui−∏ivi|≤∑i|ui−vi|| _iu_i- _iv_i|≤ _i|u_i-v_i|. At a fixed prefix-gate value the local field is a convex combination of sτ0s^0_τ and bτSjb^S_j_τ, so ‖s^j,τS(x)−s^j,τS(y)‖2≤(τ−2+mτ−4)rj+4mτ−4∑i<jri.\| s^S_j,τ(x)- s^S_j,τ(y)\|_2≤(τ^-2+mτ^-4)r_j+4mτ^-4 _i<jr_i. The strictly lower-triangular matrix of ones has operator norm at most B−1B-1. Since Bm≤dBm≤ d, including the exact padding gives Lip(s^τS)≤τ−2+4dτ−4Lip( s^S_τ)≤τ^-2+4dτ^-4. A.4 Proof of Lemma 3.3 Lemma A.9 (Complete version of Lemma 3.3). Use the dimensions, error budgets, and oracle of Lemma A.7. Fix 0<δ<1/40<δ<1/4, and define H by (13). Let S1,…,SBS_1,…,S_B be independent uniform codebooks of prescribed sizes. Suppose their adjacent rates are separated by a sufficiently large constant multiple of Hm+Hm. Hm+ Hm. (42) The required constant depends only on γ. Let P≥1P≥ 1 be an integer. For any randomized algorithm using at most P queries per round and 0≤R<B0≤ R<B rounds, let R,Y T_R,Y denote its actual transcript and output. There are coupled simulated variables ~R,Y~ T_R, Y satisfying [R≠~R]≤RPBδ,[Y≠Y~]≤RPBδ, Pr\/[ T_R≠ T_R]≤ RPBδ, Pr\/[Y≠ Y]≤ RPBδ, (43) such that the simulated transcript and output are functions only of the algorithm’s independent random seed and S1,…,SRS_1,…,S_R. Here the probabilities average over the independent codebooks and seed. The proof has two distinct parts. The codebook estimates show that one batch can be answered without any codebook after the first unknown one. The progressive coupling then turns this fixed-batch statement into an adaptive statement. The simulated oracle. For r∈[B]r∈[B], define s^j,τS,[r](x)=s^j,τS(x),j≤r,sτ0(xj),j>r, s^S,[r]_j,τ(x)= cases s^S_j,τ(x),&j≤ r,\\ s^0_τ(x_j),&j>r, cases (44) retaining the exact padding response. This truncation depends only on S1,…,SrS_1,…,S_r. It is used for analysis and need not be a legal oracle. The progressive interaction uses this r-truncated response in round r. All algorithmic and output randomness is included in a seed ω independent of S. Early stopping is padded with empty batches; a bounded-round algorithm promised only good instances can be extended arbitrarily to other transcripts with the same bound. Sparse hiding and dense null responses. For τ≥γτ≥γ, define the public thresholds κ−(τ)=tτ−log(1/δ)−1m,κ^-(τ)= t_τ- (1/δ)-1m, (45) κ+(τ)=ατ~+Hm+1τ~8Hm,τ~=1−γ2/m2τ.κ^+(τ)= _ τ+ Hm+ 1 τ 8Hm, τ= 1-γ^2/m^2\,τ. (46) These thresholds do not depend on n or on the realization of a codebook. The hypotheses on m,η,δm,η,δ ensure H>0H>0. Lemma A.10 (One-block hiding estimates). For each fixed τ≥γτ≥γ, let S be a uniformly random n-element subset of VmV_m, and write κ=(logn)/mκ=( n)/m. Then κ≤κ−(τ) κ≤κ^-(τ) ⟹supxS[aτS(x)>0]≤δ, \ \ _x Pr\/_S[a^S_τ(x)>0]≤δ, (47) κ≥κ+(τ) κ≥κ^+(τ) ⟹S[bτS≡sτ0]≥1−δ. \ \ Pr\/_S[b^S_τ≡ s^0_τ]≥ 1-δ. (48) The second event means equality as functions of x, not just equality at a particular query point. Proof. For sparse hiding, fix x. A positive gate requires some y∈Sy∈ S with ℓτ(y,x)>tτ−1 _τ(y,x)>t_τ-1. For a uniform cube vertex Y, (23) and Markov’s inequality imply Y[ℓτ(Y,x)>tτ−1]≤e1−tτYLτ(Y,x)=e1−tτ. Pr\/_Y[ _τ(Y,x)>t_τ-1]≤ e^1-t_τE_YL_τ(Y,x)=e^1-t_τ. Give S a uniform random ordering. Every codeword marginal is uniform on the cube, so a union bound, without independence of those codewords, gives S[aτS(x)>0]≤ne1−tτ=exp(mκ+1−tτ)≤δ. Pr\/_S[a^S_τ(x)>0]≤ ne^1-t_τ= (mκ+1-t_τ)≤δ. (49) This bound holds for every fixed x. For dense nullity, the rate assumption in (46) gives logn−H−mατ~≥8Hmτ~. n-H-m _ τ≥ 8Hm τ. Apply Lemma A.6 at noise τ~ τ with u=Hu=H. The tail in that lemma is at most e−He^-H by Lemma A.4. Because log(1+2m)≥1 (1+2^m)≥ 1, SDKL(pSτ~∥qτ~) _SD_KL(p^S_ τ\|q_ τ) ≤(1+log(1+2m))e−H ≤(1+ (1+2^m))e^-H ≤2log(1+2m)e−H≤δγ2η28em2. ≤ 2 (1+2^m)e^-H≤ δγ^2η^28em^2. Lemma A.5 now yields SFτ(S)≤2em2γ2τ2δγ2η28em2=δη24τ2.E_SF_τ(S)≤ 2em^2γ^2τ^2 δγ^2η^28em^2= δη^24τ^2. Markov’s inequality gives S[Fτ(S)>η2/(4τ2)]≤δ Pr\/_S[F_τ(S)>η^2/(4τ^2)]≤δ. On the complement, (36) selects the null score at every point. ∎ Lemma A.11 (Uniform transition width). For every τ≥γτ≥γ, κ−(τ)≤ατ≤κ+(τ),κ+(τ)−κ−(τ)=Oγ(Hm+Hm).κ^-(τ)≤ _τ≤κ^+(τ), κ^+(τ)-κ^-(τ)=O_γ\! ( Hm+ Hm ). (50) Proof. The first inequalities follow from tτ≤mατt_τ≤ m _τ and ατ~≥ατ _ τ≥ _τ. Since γ2/m2≤1/2γ^2/m^2≤ 1/2, the nearby-noise bound gives ατ~−ατ≤−12log(1−γ2/m2)≤γ2m2. _ τ- _τ≤- 12 (1-γ^2/m^2)≤ γ^2m^2. Using τ~≥γ/2 τ≥γ/ 2 and ζ(τ)≥ζ(γ)ζ(τ)≥ζ(γ), subtract the thresholds to obtain κ+(τ)−κ−(τ) κ^+(τ)-κ^-(τ) ≤γ2m2+H+log(1/δ)+1m ≤ γ^2m^2+ H+ (1/δ)+1m +2γ8Hm+1γ8log(1/ζ(γ))m. + 2γ 8Hm+ 1γ 8 (1/ζ(γ))m. The definition of H gives H≥1H≥ 1, H≥log(1/δ)H≥ (1/δ), and H≥log(1/ζ(γ))H≥ (1/ζ(γ)). Each term is therefore Oγ(H/m+H/m)O_γ( H/m+H/m), uniformly over the noise level. ∎ Lemma A.12 (One-batch indistinguishability). Suppose the rate separation in Lemma A.9 holds. Fix r∈[B]r∈[B], an exposed prefix S1,…,Sr−1S_1,…,S_r-1, and a seed ω. Any batch of at most P queries determined by this prefix and seed receives different responses from the full and r-truncated oracles with probability at most PBδPBδ, over the independent suffix Sr,…,SBS_r,…,S_B. Proof. For r=Br=B, the two oracles are identical. Otherwise fix a query (x,τ)(x,τ) from the batch. For a block j>rj>r, the response difference is (∏i<jaτSi(xi))(bτSj(xj)−sτ0(xj)). ( _i<ja^S_i_τ(x_i) ) (b^S_j_τ(x_j)-s^0_τ(x_j) ). If κr≤κ−(τ) _r≤κ^-(τ), any nonzero difference requires aτSr(xr)>0a^S_r_τ(x_r)>0, an event of probability at most δ by Lemma A.10. This single event controls the entire later suffix. If instead κr>κ−(τ) _r>κ^-(τ), then for every j>rj>r, κj≥κr+1>κr+(κ+(τ)−κ−(τ))>κ+(τ), _j≥ _r+1> _r+ (κ^+(τ)-κ^-(τ) )>κ^+(τ), where the rate separation dominates the width by Lemma A.11. Thus bτSj≡sτ0b^S_j_τ≡ s^0_τ except on an event of probability at most δ for each such j. In either case, a union bound bounds the probability of a different answer to this query by (B−r)δ(B-r)δ. Another union bound over the batch gives P(B−r)δ≤PBδP(B-r)δ≤ PBδ. The conditioning fixes both the locations and the noise levels of the batch, but leaves the suffix codebooks independent with their original laws. Hence the fixed-noise estimates above apply separately to each query. No event simultaneous over a continuum of noise levels, and no noise discretization, is needed. ∎ The general progressive coupling. The remaining argument uses no properties of scores or codebooks. We state it separately so that the box proof can invoke exactly the same lemma. Lemma A.13 (Progressive simulation). Let n,P≥1n,P≥ 1 be integers, let Θ=(Θ1,…,Θn) =( _1,…, _n) have independent finite-valued coordinates, and let ω be an independent seed containing all algorithmic and output randomness. Fix an oracle OΘO_ , truncated oracles OΘ[r]O^[r]_ for r∈[n]r∈[n], and δbatch≥0 _batch≥ 0. Assume that for every r∈[n]r∈[n]: 1. OΘ[r]O^[r]_ depends only on (Θ1,…,Θr)( _1,…, _r); 2. for every fixed prefix (Θ1,…,Θr−1)( _1,…, _r-1) in its support, seed, and batch of at most P queries determined by them, the full and truncated oracles disagree on the batch with probability at most δbatch _batch over the independent suffix. For every integer 0≤R≤n0≤ R≤ n and every algorithm using at most R rounds and P queries per round, couple its actual interaction to the progressive interaction that answers round r with OΘ[r]O^[r]_ . Their transcripts and outputs disagree with probability at most RδbatchR _batch. The progressive transcript and output depend only on (ω,Θ1,…,ΘR)(ω, _1,…, _R). Proof. Run the progressive interaction with OΘ[r]O^[r]_ in round r. Its transcript after that round depends only on (ω,Θ1,…,Θr)(ω, _1,…, _r), by induction. Thus its round-r batch is independent of the fresh suffix conditional on the prefix and seed. Let DrD_r be the event that the full and truncated oracles disagree on this progressive batch. The hypothesis, applied for each prefix and seed and then averaged, gives (Dr)≤δbatch Pr\/(D_r)≤ _batch. Couple the actual interaction using the same (Θ,ω)( ,ω). If the transcripts first disagree in round r, they chose the same batch in that round, so this first-disagreement event is contained in DrD_r. Their disagreement probability is at most ∑r=1R(Dr)≤Rδbatch _r=1^R Pr\/(D_r)≤ R _batch. The same seed determines the outputs, proving the output bound. For R=0R=0, the outputs can be identical. No estimate is conditioned on earlier agreement. Independence is used only in the progressive interaction, where prefix dependence holds identically. ∎ Proof of Lemma A.9. For any exposed prefix and seed, Lemma A.12 bounds the probability of a different answer to the next batch by PBδPBδ. Apply Lemma A.13 with Θj=Sj _j=S_j, n=Bn=B, OΘ=s^SO_ = s^S, OΘ[r]=s^S,[r]O^[r]_ = s^S,[r], and δbatch=PBδ _batch=PBδ. It gives (43) and the required prefix dependence. No conditioning on near-isotropy is used here. The public parameters in Lemma A.1 give RPBδ≤ρ2/(100d)RPBδ≤ρ^2/(100d); with ρ=1/10ρ=1/10, this is smaller than 0.0010.001, as required by Lemma 3.3. ∎ A.5 Proof of Lemma 3.4 Lemma A.14 (Complete version of Lemma 3.4). Use the one-block gate, cutoff, and budgets of Lemma A.7. Fix 0<κmax<αγ0< _ < _γ and put c0=(αγ−κmax)/2c_0=( _γ- _ )/2. Suppose 1γ8log(1/ζ(γ))m≤c0. 1γ 8 (1/ζ(γ))m≤ c_0. (51) For an integer 1≤n≤2m1≤ n≤ 2^m with (logn)/m≤κmax( n)/m≤ _ , and for each n-element codebook S⊆VmS V_m, define the target-level test E(S)=x∈ℝm:aγS(x)=1=x∈ℝm:maxy∈Sℓγ(y,x)≥tγ.E(S)=\x ^m:a^S_γ(x)=1\= \x ^m: _y∈ S _γ(y,x)≥ t_γ \. (52) Every fixed codebook satisfies pγS(E(S))≥1−ζ(γ).p^S_γ(E(S))≥ 1-ζ(γ). (53) If S is uniform among the n-element subsets of VmV_m, then supx∈ℝmS[x∈E(S)]≤ne−tγ≤e−c0m. _x ^m Pr\/_S[x∈ E(S)]≤ ne^-t_γ≤ e^-c_0m. (54) In particular, for any random V∈ℝmV ^m independent of this random codebook, [V∈E(S)]≤e−c0m Pr\/[V∈ E(S)]≤ e^-c_0m. Proof. The test is evaluated at total noise γ, because this is the unsmoothed target level in our notation. Equation (53) is exactly the gate-completeness estimate (39) at this noise level. For blindness, fix x∈ℝmx ^m. A uniform cube vertex Y obeys Y[ℓγ(Y,x)≥tγ]=Y[Lγ(Y,x)≥etγ]≤e−tγYLγ(Y,x)=e−tγ. Pr\/_Y[ _γ(Y,x)≥ t_γ]= Pr\/_Y[L_γ(Y,x)≥ e^t_γ]≤ e^-t_γE_YL_γ(Y,x)=e^-t_γ. A union bound over a uniform random ordering of S gives S[x∈E(S)]≤ne−tγ Pr\/_S[x∈ E(S)]≤ ne^-t_γ. The margins in (51) imply tγ≥m(αγ−c0)=m(κmax+c0),t_γ≥ m( _γ-c_0)=m( _ +c_0), so n≤emκmaxn≤ e^m _ yields the second inequality in (54). Finally, condition on the value of V and average the fixed-point bound. Independence ensures that conditioning on V does not change the uniform codebook law. ∎ For the public sizes chosen in Lemma A.1, the two failure bounds above are at most ρ2/100ρ^2/100. Taking ρ=1/10ρ=1/10 therefore gives the constants of Lemma 3.4, with slack. The restriction to the prescribed rates is necessary: this is not a claim about arbitrary subsets of the full cube. How the test gives the output separation. The following consequence records the quantitative form of the TV calculation in the proof of Theorem 3.1. It will be used only after the instance and algorithm have been fixed as specified. Lemma A.15 (An unseen block forces error). Suppose the independent product codebooks satisfy the hypotheses of Lemma A.9 and each rate is at most κmax _ . Assume (51). For an algorithm using R<BR<B rounds and at most P queries per round, let QSQ_S be its actual output law on instance S. Then SdTV(QS,πS)≥1−ζ(γ)−e−c0m−RPBδ.E_Sd_TV(Q_S,π^S)≥ 1-ζ(γ)-e^-c_0m-RPBδ. (55) Proof. For every fixed instance, define an event in the full sample space by DS=x∈ℝd:xR+1∈E(SR+1).D_S=\x ^d:x_R+1∈ E(S_R+1)\. The first bound in Lemma A.14 gives πS(DS)≥1−ζ(γ)π^S(D_S)≥ 1-ζ(γ). Couple the actual and simulated outputs Y,Y~Y, Y using Lemma A.9. The simulated output depends only on ω,S1,…,SRω,S_1,…,S_R and is therefore independent of SR+1S_R+1. Hence [Y~∈DS]=[Y~R+1∈E(SR+1)]≤e−c0m. Pr\/[ Y∈ D_S]= Pr\/[ Y_R+1∈ E(S_R+1)]≤ e^-c_0m. The coupling implies SQS(DS)=[Y∈DS]≤[Y~∈DS]+[Y≠Y~]≤e−c0m+RPBδ.E_SQ_S(D_S)= Pr\/[Y∈ D_S]≤ Pr\/[ Y∈ D_S]+ Pr\/[Y≠ Y]≤ e^-c_0m+RPBδ. For each fixed S, total variation is at least πS(DS)−QS(DS)π^S(D_S)-Q_S(D_S). Average this inequality over the independent instance law to obtain (55). The event DSD_S is selected for each instance before averaging. It need not be available to the algorithm. The randomness defining QSQ_S is already averaged within that output law; it is not an additional instance quantifier. ∎ A.6 Proof of Lemma 3.5 Lemma A.16 (Complete version of Lemma 3.5). Fix γ>0γ>0. For every sufficiently large d, there is a randomized sampler that, for every product target πSπ^S with the parameters of Lemma A.1 and every fixed legal oracle with accuracy εscore _score, uses at most Oγ(dm(logd)3)O_γ ( dm\,( d)^3 ) queries and has an output law Q satisfying dTV(Q,πS)=Oγ(d−1/2+εscorelogd).d_TV(Q,π^S)=O_γ\! (d^-1/2+ _score d ). (56) The query bound is a worst-case bound, and the algorithm may use one query per round. In particular, accuracy εscore=(d)−1 _score= poly(d)^-1 suffices for total variation error 1/101/10 using O~(d5/6) O(d^5/6) queries and adaptive rounds. The family-specific ingredient is the following bound for the true denoiser. After proving it, we give the full specialization of the [8] sampling guarantee used in the manuscript, including score error accumulation, removal of extra smoothing, and the worst-case query cutoff. No regularity of the given approximate oracle is assumed. Lemma A.17 (Regularity of the true denoiser). Let U∼μSU μ^S, let Z0,Z∼(0,Id)Z_0,Z (0,I_d) be independent of each other and of U, and put X0=U+γZ0X_0=U+γ Z_0. For σ>0σ>0, define Dσ(x)=[X0∣X0+σZ=x]D_σ(x)=E[X_0 X_0+σ Z=x] using the Gaussian posterior at every x. Then supσ>0,x∈ℝd‖∇Dσ(x)‖F≤d+dm4γ2. _σ>0,\ x ^d\|∇ D_σ(x)\|_F≤ d+ dm4γ^2. (57) Proof. Write τ2=γ2+σ2τ^2=γ^2+σ^2 and Σσ(x)=Cov(U∣X0+σZ=x) _σ(x)=Cov(U X_0+σ Z=x). Gaussian conditioning and differentiation of the posterior mean give ∇Dσ(x)=γ2τ2Id+σ2τ4Σσ(x).∇ D_σ(x)= γ^2τ^2I_d+ σ^2τ^4 _σ(x). (58) Indeed, conditionally on U=uU=u and X0+σZ=xX_0+σ Z=x, the mean of X0X_0 is (γ2x+σ2u)/τ2(γ^2x+σ^2u)/τ^2, while the derivative of the posterior mean of U is Σσ(x)/τ2 _σ(x)/τ^2. The posterior of U retains its product structure across the public blocks. Each hidden covariance block is positive semidefinite and has trace at most m, since its coordinates take values in −1,+1\-1,+1\. The padding coordinates remain independent, with posterior variances at most one. Consequently, trΣσ(x)≤d,‖Σσ(x)‖op≤m,‖Σσ(x)‖F2≤‖Σσ(x)‖optrΣσ(x)≤dm.tr _σ(x)≤ d, \| _σ(x)\|_op≤ m, \| _σ(x)\|_F^2≤\| _σ(x)\|_optr _σ(x)≤ dm. Now use γ2/τ2≤1γ^2/τ^2≤ 1 and σ2/(γ2+σ2)2≤1/(4γ2)σ^2/(γ^2+σ^2)^2≤ 1/(4γ^2) in (58). ∎ Proof of Lemma A.16. Write π=πSπ=π^S. The pointwise bound in Lemma A.17 verifies Assumptions 4.6 and 4.8 of [8], including the hypothesis under its auxiliary one-step distribution. We apply [9, Theorem 4.9] with data distribution π and additional Gaussian noise; these are precisely the scores available in the oracle model. Choose a step size h that is a sufficiently small constant multiple of 1/(dm(logd)2)1/( dm( d)^2), with the constant depending only on γ, and use the schedule σ12=γ2/d,σk+12=(1+h)σk2. _1^2=γ^2/d, _k+1^2=(1+h) _k^2. Let K be the first index with σK2≥(1+γ2)d2 _K^2≥(1+γ^2)d^2. Then K=Oγ(dm(logd)3),Kh=Oγ(logd).K=O_γ\! ( dm( d)^3 ), Kh=O_γ( d). (59) With internal tolerance d−10d^-10, this schedule meets the cited theorem’s step-size condition. If Q∗Q_* is the output law before query-budget truncation, the theorem gives DKL(π(σ1)∥Q∗)=O( D_KL(π^( _1)\|Q_*)=O ( DKL(π(σK)∥(0,σK2Id))+Kd−10 D_KL(π^( _K)\|N(0, _K^2I_d))+Kd^-10 (60) +h∑k=1Kσk2π(σk)∥s^(⋅,σk)−sπ,σk∥22). +h _k=1^K _k^2E_π^( _k)\| s(·, _k)-s_π, _k\|_2^2 ). Here s s is the given legal additional-noise oracle. For k<Kk<K, hσk2=σk+12−σk2h _k^2= _k+1^2- _k^2; the terminal summand is included only to simplify the error bound. The identity ‖X0‖22=(1+γ2)dE\|X_0\|_2^2=(1+γ^2)d holds for every instance. Convexity of relative entropy yields DKL(π(σK)∥(0,σK2Id))≤‖X0‖222σK2≤12d.D_KL(π^( _K)\|N(0, _K^2I_d))≤ E\|X_0\|_2^22 _K^2≤ 12d. Oracle legality and (59) bound the score-error sum by εscore2Kh=Oγ(εscore2logd). _score^2Kh=O_γ( _score^2 d). Also Kd−10=Oγ(d−9(logd)3)Kd^-10=O_γ(d^-9( d)^3). Thus (60) is at most Oγ(d−1+εscore2logd)O_γ(d^-1+ _score^2 d). To remove the additional smoothing, note that π and π(σ1)π^( _1) have the same centers and weights. Relative-entropy convexity applied to corresponding Gaussian components gives DKL(π∥π(σ1))≤d2(log(1+1/d)−1d+1)≤14d,D_KL(π\|π^( _1))≤ d2 ( (1+1/d)- 1d+1 )≤ 14d, using log(1+r)−r/(1+r)≤r2/2 (1+r)-r/(1+r)≤ r^2/2 for r≥0r≥ 0. Pinsker’s inequality and the triangle inequality give dTV(Q∗,π)=Oγ(d−1/2+εscorelogd).d_TV(Q_*,π)=O_γ(d^-1/2+ _score d). Finally, [8], Theorem 3.1, bounds the total number of rejection-sampling queries by O(K+logd)O(K+ d) with probability at least 1−d−21-d^-2. Stop after this deterministic budget and output an arbitrary point if it is exceeded. This changes the output law by at most d−2d^-2 and proves (56) with a worst-case query bound. Since m=Θ(d2/3(logd)1/3)m= (d^2/3( d)^1/3), the bound is O~(d5/6) O(d^5/6). The error tends to zero for εscore=(d)−1 _score= poly(d)^-1. The same upper bound transfers to the publicly rescaled targets by the invertible rescaling argument above. ∎ Appendix B Deferred proofs from Section 4 We give the public parameters and prove the three lemmas used for the box construction. The same parameter choice supports the lower bound and the recovery algorithm. Throughout, the ambient dimension is d, and σ>0σ>0 denotes additional Gaussian noise. B.1 Public parameters and gates Fix a polynomial query budget P=(d)P= poly(d) and an inverse-polynomial score accuracy εscore=(d)−1 _score= poly(d)^-1. These public bounds are fixed before choosing the instance family. Implicit constants may depend on these fixed bounds. For sufficiently large d, put M=⌈100(dP+1)⌉,q=100Mdεscore,ai=14q−(i−1),hi=ai100M,ti=4aiεscore(i∈[d]). gatheredM= 100(dP+1) , q= 100Md _score, a_i= 14q^-(i-1),\\ h_i= a_i100M, t_i= 4a_i _score (i∈[d]). gathered (61) Here q is the ratio between consecutive spatial scales, hih_i is the interval half-length, and tit_i is the noise cutoff. For k∈[M]k∈[M], define ci(k)=ai+(k−12)aiM,Ii(k)=[ci(k)−hi,ci(k)+hi].c_i(k)=a_i+ (k- 12 ) a_iM, I_i(k)=[c_i(k)-h_i,c_i(k)+h_i]. (62) Choose θ1,…,θd _1,…, _d independently and uniformly from [M][M], and let Kθ=∏i=1dIi(θi),πθ=Unif(Kθ).K^θ= _i=1^dI_i( _i), π^θ=Unif(K^θ). All parameters and candidate intervals are public; only the labels are hidden. For an interval I, write dist(z,I)=infu∈I|z−u|dist(z,I)= _u∈ I|z-u|. For i<di<d, set gi,σk≡1g_i,σ^k≡ 1 when σ>ti+1σ>t_i+1, and otherwise set gi,σk(z)=min1,max0,2−dist(z,Ii(k))10hi.g_i,σ^k(z)= \1, \0,2- dist(z,I_i(k))10h_i \ \. (63) Thus, at low noise, the gate is one within distance 10hi10h_i of its interval and zero at distance at least 20hi20h_i. Lemma B.1 (Geometry and gates). For the parameters above, every KθK^θ is full-dimensional and contained in B2(0,1)B_2(0,1). The intervals Ii(k)I_i(k) lie in [ai,2ai][a_i,2a_i], are pairwise disjoint, and have center spacing ai/M=100hia_i/M=100h_i. Moreover, for i<di<d: 1. If σ≤ti+1σ≤ t_i+1, the sets z:gi,σk(z)>0\z:g_i,σ^k(z)>0\ are pairwise disjoint over k∈[M]k∈[M]. 2. For independent Ui∼Unif(Ii(k))U_i (I_i(k)) and Zi∼N(0,1)Z_i N(0,1), at every σ>0σ>0, [gi,σk(Ui+σZi)<1]≤2exp(−50hi2σ2). Pr\/ [g_i,σ^k(U_i+σ Z_i)<1 ]≤ 2 (- 50h_i^2σ^2 ). (64) Proof. Since hi<ai/(2M)h_i<a_i/(2M), the interval endpoints lie strictly between aia_i and 2ai2a_i, and distinct intervals are disjoint. Their positive lengths give full dimension. Since q≥2q≥ 2, every x∈Kθx∈ K^θ satisfies ‖x‖22≤4∑i=1dai2≤14(1−q−2)≤13<1.\|x\|_2^2≤ 4 _i=1^da_i^2≤ 14(1-q^-2)≤ 13<1. At low noise, a positive gate requires |z−ci(k)|<21hi<50hi|z-c_i(k)|<21h_i<50h_i, which proves disjointness. If |σZi|≤10hi|σ Z_i|≤ 10h_i, then dist(Ui+σZi,Ii(k))≤10hidist(U_i+σ Z_i,I_i(k))≤ 10h_i, so the gate equals one. The Gaussian tail bound proves (64) for σ≤ti+1σ≤ t_i+1; for larger σ, the gate is identically one. ∎ In particular, 10hi/ti+1=5d/210h_i/t_i+1=5d/2, so at every σ≤ti+1σ≤ t_i+1 the gate for coordinate i has failure probability at most 2e−25d2/82e^-25d^2/8 on a genuine noisy sample. Also Cov(πθ)=diag(h12/3,…,hd2/3),κ(Cov(πθ))=q2(d−1).Cov(π^θ)=diag(h_1^2/3,…,h_d^2/3), κ (Cov(π^θ) )=q^2(d-1). The construction is therefore deliberately anisotropic. B.2 Proof of Lemma 4.2 For k∈[M]k∈[M], let mi,σk(z)m_i,σ^k(z) be the posterior mean of U∼Unif(Ii(k))U (I_i(k)) given U+σZ=zU+σ Z=z, where Z∼N(0,1)Z N(0,1) is independent. Equivalently, this is the mean obtained by weighting the uniform interval measure by its Gaussian likelihood at z. It is defined at every z, belongs to Ii(k)⊂[ai,2ai]I_i(k)⊂[a_i,2a_i], and is continuous in (z,σ)(z,σ) for σ>0σ>0. The true score is si,σθ(x)=−xiσ2+mi,σθi(xi)σ2.s_i,σ^θ(x)=- x_iσ^2+ m_i,σ _i(x_i)σ^2. Using the gates in (63), define the fixed oracle s^j,σθ(x)=−xjσ2+σ≤tj(∏i<jgi,σθi(xi))mj,σθj(xj)σ2. s_j,σ^θ(x)=- x_jσ^2+1_\σ≤ t_j\ ( _i<jg_i,σ _i(x_i) ) m_j,σ _j(x_j)σ^2. (65) The empty product is one. This is the oracle in equation (9) of the main text. Lemma B.2 (Complete version of Lemma 4.2). For every instance θ, the oracle (65) is jointly measurable, is fixed before interaction, and satisfies, for every σ>0σ>0, X∼(πθ)(σ)‖s^σθ(X)−sσθ(X)‖22≤εscore22σ2.E_X (π^θ)^(σ)\| s_σ^θ(X)-s_σ^θ(X)\|_2^2≤ _score^22σ^2. (66) In particular, it is legal at score accuracy εscore _score. Proof. Fix θ and σ. Call coordinate j active when σ≤tjσ≤ t_j. In an inactive coordinate, the squared error is at most 4aj2/σ44a_j^2/σ^4. In an active coordinate, the error vanishes if every preceding gate is one; otherwise its absolute value is at most 2aj/σ22a_j/σ^2. Lemma B.1 and a union bound therefore give ∥s^σθ(X)−sσθ(X)∥22≤4σ4∑j:tj<σaj2+8σ4∑j:σ≤tjaj2∑i<je−50hi2/σ2.E\| s_σ^θ(X)-s_σ^θ(X)\|_2^2≤ 4σ^4 _j:\,t_j<σa_j^2+ 8σ^4 _j:\,σ≤ t_ja_j^2 _i<je^-50h_i^2/σ^2. (67) For the first term, if an inactive coordinate exists, let j0j_0 be the first one. Since tj0=4aj0/εscore<σt_j_0=4a_j_0/ _score<σ, geometric summation yields 4σ4∑j≥j0aj2≤4aj02(1−q−2)σ4≤εscore24(1−q−2)σ2≤εscore23σ2. 4σ^4 _j≥ j_0a_j^2≤ 4a_j_0^2(1-q^-2)σ^4≤ _score^24(1-q^-2)σ^2≤ _score^23σ^2. (68) If all coordinates are active, this term is zero. For the gate term, interchange the sums and extend the sum over j: 8σ4∑j:σ≤tjaj2∑i<je−50hi2/σ2≤8(1−q−2)σ4∑i<dai+12e−50hi2/σ2. 8σ^4 _j:\,σ≤ t_ja_j^2 _i<je^-50h_i^2/σ^2≤ 8(1-q^-2)σ^4 _i<da_i+1^2e^-50h_i^2/σ^2. For every u>0u>0, ue−u≤e−1ue^-u≤ e^-1. Applying this with u=50hi2/σ2u=50h_i^2/σ^2 bounds the last display by 850e(1−q−2)σ2∑i<d(ai+1hi)2 850e(1-q^-2)σ^2 _i<d ( a_i+1h_i )^2 =4(d−1)εscore225e(1−q−2)d2σ2≤εscore210σ2. = 4(d-1) _score^225e(1-q^-2)d^2σ^2≤ _score^210σ^2. Here ai+1/hi=100M/q=εscore/da_i+1/h_i=100M/q= _score/d; the final bound follows from q≥2q≥ 2 and (d−1)/d2≤1/4(d-1)/d^2≤ 1/4. Together with (68), this proves (66). The calculation retains the dependence on σ and hence applies also as σ tends to zero. Finally, the posterior means are continuous and the gates and cutoff indicators are Borel measurable. Their finite products and sums define a jointly measurable oracle depending only on θ,x,σθ,x,σ. ∎ B.3 Proof of Lemma 4.3 The simulation exposes at most one additional label in each round. For r∈[d]r∈[d], define the truncated oracle s^j,σθ,[r](x)=s^j,σθ(x),j≤r,−xj/σ2,j>r. s_j,σ^θ,[r](x)= cases s_j,σ^θ(x),&j≤ r,\\ -x_j/σ^2,&j>r. cases (69) It depends only on θ1,…,θr _1,…, _r and need not itself be legal. The progressive interaction answers round r with s^θ,[r] s^θ,[r]. Lemma B.3 (Complete version of Lemma 4.3). Let a randomized algorithm make at most P queries per round for R<dR<d rounds. Couple its actual interaction with the progressive interaction using the same instance and random seed. Their transcripts, and hence their outputs Y,Y~Y, Y, disagree with probability at most RP/MRP/M. The progressive transcript and output depend only on (θ1,…,θR)( _1,…, _R) and the seed. The probability averages over the independent labels and seed. Proof. Include all algorithmic and output randomness in an independent seed ω. By induction, before round r the progressive transcript depends only on ω,θ1,…,θr−1ω, _1,…, _r-1. Fix these values. This fixes the next batch and leaves the remaining labels independent and uniform. Consider one query (x,σ)(x,σ) in that batch. The full and truncated oracles agree in coordinates j≤rj≤ r. If σ>tr+1σ>t_r+1, then every j>rj>r is inactive, so they agree there as well. If σ≤tr+1σ≤ t_r+1, any disagreement in a coordinate j>rj>r requires gr,σθr(xr)>0g_r,σ _r(x_r)>0. By Lemma B.1, this can hold for at most one label θr _r. Thus disagreement on this query has conditional probability at most 1/M1/M, and disagreement anywhere in the batch has conditional probability at most P/MP/M. This reasoning applies separately to each query, even when noise levels differ. Run both interactions with the same (θ,ω)(θ,ω). A first disagreement in round r must occur on the batch chosen by the progressive interaction: all preceding answers agree, so the actual algorithm chooses that same batch. A union bound over the R progressive batches gives probability at most RP/MRP/M of any disagreement. When all answers agree, the common seed produces the same output. This is also an application of the progressive-simulation lemma (Lemma A.13). ∎ Deduction of Theorem 4.1. Let QθQ^θ be the actual output law, with the algorithm’s randomness already averaged. Conditional on the first R labels and the seed, Y~R+1 Y_R+1 is fixed and θR+1 _R+1 is uniform. Disjointness of the candidate intervals gives [Y~∈Kθ]≤[Y~R+1∈IR+1(θR+1)]≤1M. Pr\/[ Y∈ K^θ]≤ Pr\/[ Y_R+1∈ I_R+1( _R+1)]≤ 1M. Consequently, Lemma B.3 and the choice of M imply θ[Qθ(Kθ)]=[Y∈Kθ]≤RP+1M≤1100.E_θ[Q^θ(K^θ)]= Pr\/[Y∈ K^θ]≤ RP+1M≤ 1100. (70) Markov’s inequality shows that Qθ(Kθ)≤1/10Q_θ(K^θ)≤ 1/10 for at least 9/109/10 of the instances. For each such instance, dTV(Qθ,πθ)≥πθ(Kθ)−Qθ(Kθ)≥910.d_TV(Q^θ,π^θ)≥π^θ(K^θ)-Q^θ(K^θ)≥ 910. Lemma B.2 supplies the fixed legal oracle for every instance, completing the claimed probability lower bound. B.4 Proof of Lemma 4.4 We now fix a target instance. The oracle in this subsection can be any fixed jointly measurable oracle satisfying the score-error guarantee; it need not be the oracle constructed in (65). Lemma B.4 (Complete version of Lemma 4.4). For all sufficiently large d, the family with parameters (61) admits a randomized algorithm which, for every instance θ and every fixed legal oracle of accuracy εscore _score, recovers all labels with probability at least 9/109/10 using O(d)O(d) rounds and O(logd)O( d) queries per round. It consequently samples πθπ^θ to total variation error at most 1/101/10 within the same query bounds. It suffices to recover one interval at a time. Once all labels are correct, we can draw a fresh exact uniform sample from their Cartesian product. The two facts below show how a batch of approximate-score queries refines the center estimate for the current interval. Lemma B.5 (Gaussian change of measure). Let U be a random vector in ℝnR^n, let σ>0σ>0, and let p be the density of U+σZU+σ Z for independent Z∼N(0,In)Z N(0,I_n). For v∈ℝnv ^n, let f be the density of N(v,σ2In)N(v,σ^2I_n). Then ∫ℝnf(x)2p(x)x≤exp(‖U−v‖22σ2). _R^n f(x)^2p(x)\,dx ( \|U-v\|_2^2σ^2 ). (71) Proof. Write ϕσ _σ for the centered Gaussian density, so p(x)=Uϕσ(x−U)p(x)=E_U _σ(x-U) and f(x)=ϕσ(x−v)f(x)= _σ(x-v). Convexity of z↦1/z 1/z, followed by Tonelli’s theorem, gives ∫f(x)2p(x)x≤U∫ϕσ(x−v)2ϕσ(x−U)x=Uexp(‖U−v‖22σ2). f(x)^2p(x)\,dx _U _σ(x-v)^2 _σ(x-U)\,dx=E_U ( \|U-v\|_2^2σ^2 ). The equality follows by completing the square. ∎ Lemma B.6 (One refinement). Suppose the labels θ1,…,θi−1 _1,…, _i-1 have been recovered, and let b∈ℝb and r≥hir≥ h_i satisfy |b−ci(θi)|≤r|b-c_i( _i)|≤ r. Set σ=4rσ=4r. For each of an odd number N of independent queries, draw Xj=Uj+σZj,Uj∼Unif(Ij(θj)),j<i,b+σZj,j=i,σZj,j>i,X_j= casesU_j+σ Z_j, U_j (I_j( _j)),&j<i,\\ b+σ Z_j,&j=i,\\ σ Z_j,&j>i, cases (72) with all draws independent and every Zj∼N(0,1)Z_j N(0,1). Query the oracle at (X,σ)(X,σ), form V=Xi+σ2s^i,σ(X)V=X_i+σ^2 s_i,σ(X), and let b′b be the median of the N values of V. Then [|b′−ci(θi)|>hi+64εscorer]≤2−N/2. Pr\/ [|b -c_i( _i)|>h_i+64 _scorer ]≤ 2^-N/2. (73) Proof. For sufficiently large d, q≥400Mq≥ 400M. Thus every U∈KθU∈ K^θ satisfies ∑j>iUj2≤4∑j>iaj2≤4ai2q2−1≤hi2. _j>iU_j^2≤ 4 _j>ia_j^2≤ 4a_i^2q^2-1≤ h_i^2. (74) Let f be the query density in (72), and let p be the density of the true noisy target (πθ)(σ)(π^θ)^(σ). Their prefix marginals agree exactly. On the suffix, the query distribution is the Gaussian centered at v=(b,0,…,0)v=(b,0,…,0), while the true distribution is the Gaussian smoothing of the unknown intervals. Every suffix point U obeys ‖U−v‖22≤(r+hi)2+hi2≤5r2.\|U-v\|_2^2≤(r+h_i)^2+h_i^2≤ 5r^2. The matching prefix factors cancel, so Lemma B.5 with σ=4rσ=4r gives ∫f(x)2p(x)x≤e5/16. f(x)^2p(x)\,dx≤ e^5/16. (75) Cauchy–Schwarz, legality, and (75) give X∼f|s^i,σ(X)−si,σθ(X)|≤e5/32εscoreσ.E_X f| s_i,σ(X)-s_i,σ^θ(X)|≤ e^5/32 _scoreσ. By Markov’s inequality, the score error exceeds 16εscore/σ16 _score/σ with query probability at most e5/32/16<1/8e^5/32/16<1/8. At every query point, the exact posterior mean xi+σ2si,σθ(x)x_i+σ^2s_i,σ^θ(x) belongs to Ii(θi)I_i( _i). Since σ=4rσ=4r, it follows that [|V−ci(θi)|>hi+64εscorer]<1/8. Pr\/ [|V-c_i( _i)|>h_i+64 _scorer ]<1/8. Because the oracle is fixed, the independently generated queries give independent values of V. If their median is outside the displayed interval, at least (N+1)/2(N+1)/2 of them are outside. A union bound over subsets gives probability at most 2N(1/8)N/2=2−N/22^N(1/8)^N/2=2^-N/2, proving (73). ∎ Proof of Lemma B.4. For sufficiently large d, 64εscore≤1/464 _score≤ 1/4. Choose an integer L=O(1)L=O(1) and an odd integer N=O(logd)N=O( d) such that (64εscore)L100M≤1,N≥2log2(10dL).(64 _score)^L100M≤ 1, N≥ 2 _2(10dL). (76) Such choices exist because M is polynomial and εscore _score is inverse-polynomial in d. Process coordinates i=1,…,di=1,…,d in order. Initialize b0=3ai/2b_0=3a_i/2 and r0=air_0=a_i. In refinement ℓ∈[L] ∈[L], apply Lemma B.6 with b=bℓ−1b=b_ -1 and r=rℓ−1r=r_ -1, and set the deterministic radius rℓ=hi+64εscorerℓ−1.r_ =h_i+64 _scorer_ -1. (77) After these L refinements, decode the label whose public center is nearest to bLb_L, breaking any ties by the smallest label. This specifies an algorithm on every possible history. The initial estimate satisfies |b0−ci(θi)|≤ai/2≤r0|b_0-c_i( _i)|≤ a_i/2≤ r_0, and every prescribed radius is at least hih_i. If all refinements so far succeed, their error guarantees give |bℓ−ci(θi)|≤rℓ|b_ -c_i( _i)|≤ r_ . Moreover, (76) implies (64εscore)Lai≤ai/(100M)=hi(64 _score)^La_i≤ a_i/(100M)=h_i, so rL=(64εscore)Lai+hi∑j=0L−1(64εscore)j≤hi+hi1−64εscore≤73hi<3hi.r_L=(64 _score)^La_i+h_i _j=0^L-1(64 _score)^j≤ h_i+ h_i1-64 _score≤ 73h_i<3h_i. Since distinct candidate centers are 100hi100h_i apart, successful refinements identify the correct label. Fix the target and oracle. Conditional on any history before the first failed refinement, all previously decoded labels are correct, the current center estimate lies within its prescribed radius, and the next batch uses fresh independent randomness. Lemma B.6 applies uniformly to every such history. The probability of at least one failed refinement is therefore at most dL 2−N/2≤1/10.dL\,2^-N/2≤ 1/10. On the complementary event every label is decoded correctly. Finally, use fresh independent randomness to sample uniformly from the decoded box. Couple this output to a uniform sample from the true box using the same final uniform coordinates. They agree whenever all decoded labels are correct, so their total variation distance is at most 1/101/10. Each refinement uses one round and N=O(logd)N=O( d) queries, for a total of dL=O(d)dL=O(d) rounds. ∎