acceptodds
Desk rejected at ICLR 2027

Beyond Query Count: A Radial Budget for Sampling

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Efficient diffusion sampling requires reducing the number of denoising model evaluations used to generate a sample. When a sampler can request estimates at several neighboring noise levels together, counting requests alone leaves their total evaluation cost unresolved. We study this question in a discrete model where noise flips a prescribed number of binary coordinates and each query returns estimates for a contiguous band of noise levels. We introduce a radial information budget that accounts for the overlap between neighboring levels. The key geometric bound charges a band for its width plus one logarithmic term, avoiding a separate logarithmic charge for every returned estimate. We carry this bound through complete adaptive response histories. For each declared evaluation cap, we construct random targets and accurate denoising responses for which approximate sampling requires a worst case radial budget linear in dimension. At fixed denoising accuracy and moment order, the resulting evaluation lower bound is proportional to dimension divided by its logarithm, even with adaptive query points, band widths, and stopping times. In this model, grouping neighboring estimates into fewer requests does not remove the lower bound on their total number.

Primary area:
learning theory
Keywords:
Diffusion sampling, Query complexity, Adaptive queries, Information-theoretic lower bounds, Hamming geometry, Formal verification

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_D5QuOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies sample complexity when a denoising sample returns estimates at several neighboring noise levels in one request. To explore this question, the authors consider the DGP of a uniform distribution over nn iid. random sign vectors; the noising mechanism flips a pre-specified number of coordinates. The paper contributes a seemingly novel radial information budget that takes into account the overlap (in ranges of hidden codebook sizes over which a query can be informative) between neighboring noise levels. Lower bounds are computed that allow adaptive query points, band widths, and stopping times. One takeaway is that for fixed denoising accuracy, successful approximate sampling would require at least d/log⁡(d)d/\log(d) returned estimates in the worst case.

Critical strengths
  1. Interesting mathematical contribution. The main technical hurdle in the paper is perhaps the adaptive query setup. The authors address this by considering a null transcript generated using a target-independent denoiser, which is then coupled with the actual responses up to the first disagreement. I find the interaction of band-overlap geometry with this approach for adaptivity very interesting and clever.
Critical weaknesses
  1. Connection to diffusion sampling is not clear. The paper introduces a DGP whose noising mechanism is to flip a number of coordinates of a uniform vector over a random codebook. It is unclear how this connects to the common diffusions, e.g. Gaussian-noising diffusions and discrete diffusions. For instance, what kinds of high-level takeaways can we make for the usual diffusion settings with the same adaptive query setup?

  2. No matching upper bounds. For the particular setup of the paper, I wonder if the radial budget should approximately capture the overall sampling difficulty in this model. Specifically, if I were to sample effectively with prespecified ϵ\epsilon TV error, for instance, what would the radial budget have to be? Is it going to be the same asymptotic rate in dimension as the lower bound given in the paper?

I am leaning acceptance due to the paper's conceptual depth. On the other hand, I think that overall, although the paper is very mathematically interesting, its' obscure relationship (at least to me) with the broader literature diffusion sampling, even compared to e.g. Xun & Price et al. (2026) makes me a little unconfident in its' impact for the community.

Questions for authors

I have no further questions or concerns.

3 comments
AuthorsOpenReview ↗

Response to W1: Connection to binary diffusion and the broader takeaway

Thank you for recognizing the interaction between band geometry and adaptive queries, and for asking us to make the connection to standard diffusion clearer. We have added a precise mathematical connection to independent binary flips in Proposition I.1, together with a proof and an explicit description of the information supplied by each interface.

Suppose every coordinate flips independently with probability qq, and let KK be the number of flips. Conditional on K=kK=k, the flipped coordinates form a uniformly chosen subset of size kk. This is exactly the fixed energy channel in our paper. The standard posterior mean can therefore be expressed as a mixture of our shell means,

mS,qflip(x)=∑k=0dwk(S,x,q)mS,k(x)m^{\mathrm{flip}}_{S,q}(x)=\sum_{k=0}^{d}w_k(S,x,q)m_{S,k}(x)

wk(S,x,q)=NS,k(x)qk(1−q)d−k∑j=0dNS,j(x)qj(1−q)d−jw_k(S,x,q)=\frac{N_{S,k}(x)q^k(1-q)^{d-k}}{\sum_{j=0}^{d}N_{S,j}(x)q^j(1-q)^{d-j}}

Here NS,k(x)N_{S,k}(x) counts codeword occurrences in shell kk, including multiplicity. These are posterior weights after observing xx. The known binomial distribution of KK before observing xx does not generally supply them. Our oracle returns the shell means, without these occupancies or weights.

Appendix I gives a small exact example of this distinction. At x=(1,1)x=(1,1), a codebook containing two copies each of xx and −x-x, and a codebook containing all four binary vertices, return the same full shell list (x,0,−x)(x,0,-x). With q=1/4q=1/4, their bit flip posterior means are respectively (4/5)x(4/5)x and (1/2)x(1/2)x. Thus the list at one point does not determine the standard posterior at that point. The example isolates the information needed to combine shell means at the observed point.

We also checked the identity by two independent computations over all observations for 180 codebooks and four flip probabilities. The codebook is the statistical unit, with 20 codebooks in each dimension and size setting.

Diagnostic over 720 casesResult
Maximum coordinate residual using posterior weights3.55×10−153.55\times10^{-15}
Normalized RMSE using binomial prior weights0.02260.0226 to 0.47530.4753

The RMSE is weighted by the actual observation distribution and normalized by d\sqrt d. The proof establishes the identity, while these checks verify its implementation.

The broader takeaway is that access to several neighboring noise levels can contain overlapping information. Our result shows how to charge this overlap while allowing the next point, band width, and stopping decision to adapt to earlier answers. This distinguishes fewer requests from fewer returned denoising estimates. For standard diffusion, it motivates examining both the information returned across nearby levels and the weights used to combine it. Transferring the sampling lower bound to standard binary or Gaussian diffusion would additionally require a reduction matching the actual oracle access and accuracy assumptions. Section 6 and the new interface comparison in Appendix I now separate this transfer question from the exact binary channel identity. Thank you for helping us make the broader implication more precise.

AuthorsOpenReview ↗

Response to W2: Tightness, the radial budget, and prescribed sampling accuracy

Thank you for recognizing the radial budget as a potentially useful measure of sampling difficulty and for asking about a matching algorithm. Our results establish a necessary budget with a sharp geometric foundation. A matching sampling upper bound remains open. We have revised Section 6 to distinguish geometric tightness, necessary sampling resources, and the algorithmic sufficiency question.

Geometric tightness. Proposition 13 gives matching bounds when the radii lie in a fixed compact Hamming branch and each informative window has width of order H/dH/d:

=\Theta\!\left(\frac{b+H}{d}\right).$$ The windows describe hidden codebook rates at which a shell response can be informative. Neighboring windows overlap, so their union pays for the displacement across the band plus one common window width. This explains the additive dependence on $b$ and $H$. The matching estimate concerns the union diameter under these assumptions. **Meaning of the radial budget.** For a declared cap $R_\star$ on returned shell estimates, the radial charge is $$\mathcal B_\star=\sum_t(b_t+\Lambda_\star),\qquad \Lambda_\star=1+\log d+\log(1+R_\star)+p\log(1/\varepsilon).$$ Here $b_t$ is the band half width. This sum bounds the rate coverage charged to the queries, with neighboring estimates within each band accounted for through their union. The proof follows an entire null transcript independent of the target and couples it to actual responses. It therefore allows the point, band width, and stopping decision to depend on previous answers. This turns the geometric estimate into a necessary resource law for adaptive sampling. The budget also charges repeated coverage, so a query policy must choose how to turn its available budget into new information. Establishing that an optimal policy succeeds at the lower bound scale requires a sampler using the permitted responses and a guarantee for its complete output law conditional on each relevant fixed codebook. In particular, the sampler must reproduce the frequencies in the empirical target, including multiplicities. Finding one support point alone does not establish that sampling guarantee. **Budget for a prescribed TV accuracy.** The denoising error $\varepsilon$ and the desired sampling error $\tau$ are different parameters. The latter measures $$d_{\mathrm{TV}}\bigl(\mathcal L(\widehat X\mid S),\nu_S\bigr).$$ Theorem 2 first fixes $R_\star$ and constructs a hard distribution of targets and accurate response families before choosing the algorithm. Every adaptive algorithm satisfying both $R\le R_\star$ and $\mathcal B_\star\le c_{\mathrm{bud}}d$ on every possible transcript path has TV error at least $0.9$ on at least $0.9$ of these instances. Thus, for any $\tau<0.9$, achieving TV error at most $\tau$ on more than $0.1$ of these hard instances, while retaining the entry cap, requires some possible path with $\mathcal B_\star>c_{\mathrm{bud}}d$. This is a worst case path requirement. The corresponding necessary dimension scales are: | Resource | Necessary order under the respective hard distribution and cap conditions | | --- | --- | | Radial budget | $\Omega(d)$ | | Returned shell estimates | $\Omega(d/(\log d+p\log(1/\varepsilon)))$ | | Requests with fixed half width $b$ | $\Omega(d/(b+\Lambda_b))$ | Here $\Lambda_b=1+\log d+\log(1+b)+p\log(1/\varepsilon)$. The last row applies where Corollary 4 admits a positive integer query cap. The hard distribution is indexed by the declared cap in the corresponding theorem or corollary. At fixed $p$ and $\varepsilon$, the necessary estimate count is of order $d/\log d$. These bounds apply to every desired TV tolerance below $0.9$ under the stated success requirement. Whether the same dimension scales are sufficient, and how an achievable budget depends on $\tau$, remains the matching algorithmic question. The established contribution is the necessary radial resource law that survives fully adaptive access, supported by the sharp overlap geometry. Thank you for helping us articulate both the proved resource scales and the precise target for an upper bound.

Thank you for addressing my concerns. I will retain my score in favor of the mathematical content.

Reviewer_MGLLOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies sampling from a distribution on the binary hypercube using a denoising oracle. For a query point, the oracle returns approximate posterior means across a contiguous range of noise levels, where level kk means exactly kk coordinates have been flipped. Using Xun–Price’s proof framework, the paper establishes an Ω(d/log⁡d)\Omega(d/\log d) lower bound on the total number of denoising evaluations.

Critical strengths

The analysis looks sound, and this paper also offered the Lean proofs.

Critical weaknesses
  • This setting seems somewhat artificial, and I am unclear about its connection to discrete diffusion models or other models. Also, the theorem statement is hard to read, and the new oracle is not defined explicitly.

  • The technical contribution appears incremental, and the proof largely follows Xun and Price's proof framework.

  • The discussion of and comparisons with existing methods are insufficient.

Questions for authors

What practical sampling tasks or existing diffusion models does this setting capture? Is there any connection to standard discrete diffusion models, even in the binary case?

4 comments
AuthorsOpenReview ↗

Response to W1: Model connection, oracle definition, and theorem

Thank you for identifying these three points that needed a clearer presentation. The prepared revision now gives an exact connection to independent binary corruption, an explicit oracle definition in Section 2, and a plain language theorem summary in Section 3. Together, these explain the sampling task, the information available to the algorithm, and what the lower bound establishes.

The target is the empirical distribution of a hidden list of binary vectors, called a codebook. Our corruption channel chooses a codeword uniformly by its index and flips exactly kk uniformly selected coordinates. This channel has an exact connection to ordinary independent flips: conditioning independent flips on their total count gives precisely the same process. Proposition I.1 proves this identity for every nonempty codebook, including repeated vectors. Ordinary binary denoising then mixes the shell posterior means using probabilities conditioned on the observation. These weights depend on shell occupancies and are not determined by the binomial probabilities before observation. Appendix I proves this relationship and gives an example of the information missing from a mean list at one point. A transfer of the sampling lower bound to standard binary or Gaussian diffusion would require a further reduction respecting their access and accuracy conditions.

The boxed oracle definition specifies a query point xx in the binary cube, a center k0k_0, and a half width bb, with both integers between zero and dd. The response is an ordered list of approximate posterior means for radii from k0−bk_0-b to k0+bk_0+b, clipped to this valid range. Every entry uses the same chosen point xx, in increasing radius order. At radius kk, the exact mean averages compatible codeword indices, retaining multiplicity. For an empty shell, its defined value is (1−2k/d)x(1-2k/d)x. Returned entries may be dependent. The list does not separately provide occupancies, posterior mixing weights, or target samples.

An interior query with b=1b=1, for example, returns estimates at k0−1k_0-1, k0k_0, and k0+1k_0+1, all at xx. The algorithm then uses the response to choose its next point, center, width, or stopping decision. No future trajectory state is needed. Definition 1 states the accuracy assumption: for every fixed codebook and radius, the expected ppth power of the Euclidean error normalized by d\sqrt d is at most εp\varepsilon^p. The expectation uses that shell's forward channel and includes response randomness. This is an average over channel observations, rather than a guarantee at every point or conditional on an adaptive history.

The three resources distinguish a request from the amount it returns.

ResourceDefinition
QQNumber of oracle requests
RRTotal number of returned shell estimates
B⋆\mathcal B_\starSum of bt+Λ⋆b_t+\Lambda_\star over requests

Here Λ⋆=1+log⁡d+log⁡(1+R⋆)+plog⁡(1/ε)\Lambda_\star=1+\log d+\log(1+R_\star)+p\log(1/\varepsilon), where R⋆R_\star is a declared entry cap. These are information access costs.

Theorem 2 can now be read in this order. Fix p≥2p\ge2, ε∈(0,1/4)\varepsilon\in(0,1/4), and sufficiently large dimension. For each declared cap R⋆R_\star, the theorem supplies a distribution over targets and accurate response families. That distribution may depend on the cap, but is fixed before the horizon, state space, and algorithm. Every randomized adaptive algorithm whose possible histories all satisfy R≤R⋆R\le R_\star and B⋆≤cbudd\mathcal B_\star\le c_{\mathrm{bud}}d then has TV error at least 0.90.9 on at least 0.90.9 of those instances. This establishes existence of hard accurate responses. The output distribution is compared with the empirical target after fixing the codebook.

Equivalently, an algorithm respecting the entry cap and attaining TV error below 0.90.9 on more than 0.10.1 of these instances must exceed the stated radial budget on some possible history. Thus the necessary worst case radial budget has order at least dd. Corollary 3 gives a necessary entry cap of order at least d/log⁡dd/\log d at fixed pp and ε\varepsilon. The oracle error parameter and the TV error of the generated sample are distinct. The explanatory additions preserve the original theorem statements. A fresh build, axiom audit, and kernel replay of the supplied Lean development also passed. Thank you for prompting these additions, which place the model connection, complete interface, and theorem interpretation before the detailed proof.

AuthorsOpenReview ↗

Response to W2: The additional estimate for a contiguous band

Thank you for asking us to identify the technical contribution more precisely. The prepared revision now places the additional estimate directly beside the bound obtained by adding separate shell contributions. The distinction is geometric: nearby noise levels can expose many of the same candidate target rates, and the proof accounts for that overlap once across the whole band.

Our analysis builds on Xun and Price's framework of random codebooks, informative scale windows, a null execution, and coupling at the first differing response. Their framework already accommodates adaptive choices. Section 5 makes this attribution explicit and compares with arXiv version 2. The new step resolves how to charge an entire contiguous band, and it leads to a bound that depends explicitly on band width.

In our shell model, each radius has an informative window in the hidden codebook rate. Bounding each shell separately and adding the results charges O((b+1)Λ⋆)O((b+1)\Lambda_\star) candidate rates for a band of half width bb. The exact Hamming anchor relation instead encloses the neighboring windows in an interval whose length is the anchor span plus one window width. Under the stated localization conditions, this gives a charge of O(b+Λ⋆)O(b+\Lambda_\star). Here the hidden rate is log⁡n/d\log n/d for codebook size nn, and Λ⋆\Lambda_\star is the logarithmic term determined by dimension, the entry cap, and denoiser accuracy. Only one copy of this term remains for the whole call.

Section 4.2 now includes both formulas and a finite example. With dimension 4096, center 1024, and half width 22, the same 45 shell entries give the following counts on the specified candidate grid.

QuantityValue
Memberships added separately across shells2,277
Distinct candidate rates in their union121
Ratio of separate counts to union size18.82

The ratio quantifies the repeated coverage that the union estimate avoids. Appendix J supplies the full scan and its conditions.

The next step controls the complete response list along adaptive histories. The geometry bounds which hidden rates a band can expose, while the response disagreement argument accounts for all returned components under the entry cap. Together these give the radial budget in Theorem 2. For fixed width, Corollary 4 then separates the necessary request count from the necessary entry count. In the regime allowed by its cap condition, the entry lower bound becomes linear in dimension once the width reaches the logarithmic scale.

For our deterministic hard response family, a band can be serialized into individual shell queries. The additional result is the sharper accounting of their shared information, which yields the additive radial charge and the request versus entry tradeoff. Table 1 keeps the Gaussian and shell access and accuracy assumptions explicit, so the contribution is assessed within its stated model. Thank you for prompting us to make this mathematical contribution clearer.

AuthorsOpenReview ↗

Response to W3: A comparison organized by access, accuracy, and cost

Thank you for requesting a fuller comparison and discussion. We have revised Table 1 and Section 5 around three explicit questions: what information a query returns, what accuracy is assumed, and which resource the lower bound constrains. This organization makes the relation to the closest prior work more informative than a comparison of dimension rates alone.

For Xun and Price, the revised reference identifies arXiv version 2. We explicitly credit both adaptive query locations and adaptive noise levels. We also include their result for the number of distinct noise levels under a polynomial cap on total queries. This gives the prior work its full adaptive scope.

The main distinctions now appear together in the comparison.

AspectXun and Price, version 2Our setting
ResponseGaussian smoothed scoreList of shell posterior means
AccuracyScore error scaled by the noise levelNormalized error for each shell channel
ResourceTotal queries and distinct levels under a total capReturned entries and radial budget

The accompanying text states the prior accuracy condition and cap, and the table caption specifies the fixed parameters behind the displayed Gaussian rate. It also makes clear that the different channels and error criteria prevent interpreting our dimension rate as a strict improvement in the same model. The comparison instead identifies the question our band geometry resolves within the fixed energy setting.

Section 5 also places these results alongside lower bounds using stochastic gradient access and analyses of concrete samplers, including reverse stochastic differential equations, stochastic localization, higher order methods, and exponential integrators. These works help distinguish an access model lower bound from an upper bound for a particular sampling algorithm. Our comparison is organized around the information and error guarantees used by each analysis.

We have expanded the discussion in two complementary directions. Appendix I supplies an exact relationship to independent binary flips, including a proof of the posterior mixture identity and an example showing why the mixing weights cannot in general be inferred from one complete shell mean list at one point. Section 6 separately explains geometric tightness, the necessary sampling budget, and the open question of a matching sampler. This gives the reader a direct account of the geometric result, its sampling consequence, and the corresponding algorithmic question.

The new finite calculations complement this comparison by making the two central mechanisms inspectable: overlap among informative windows and the posterior weights connecting shell means to ordinary binary denoising. Thank you for suggesting a broader discussion. The prepared revision now brings the closest theorem, the exact binary channel relationship, and the band geometry into a single account of the contribution.

AuthorsOpenReview ↗

Response to the Question: What the model captures and its binary diffusion connection

Thank you for this direct question. The concrete sampling task captured by our theorem is to generate the empirical distribution of a hidden binary codebook using only approximate denoising means for specified flip counts. Its connection to ordinary independent binary corruption is exact after conditioning on the number of flips. The prepared revision now explains this connection in Appendix I and states the additional argument needed to connect it to an existing diffusion sampler.

To describe the task without diffusion terminology, imagine that a target distribution assigns equal probability to the indices of a list of binary vectors. Corrupting a target vector by flipping exactly kk randomly chosen coordinates defines a denoising problem. At an observed point xx, the exact answer is the mean of the codebook vectors compatible with that observation and flip count. Our band interface gives approximate answers to several neighboring values of kk at this same xx. The algorithm uses these lists to try to sample from the target distribution.

For standard independent flips, the total flip count is random. Conditional on that count, the corruption process is precisely the channel just described. Proposition I.1 proves this relationship for arbitrary nonempty codebooks. It also shows that the usual posterior mean combines shell means using probabilities conditioned on the observation. Those probabilities depend on shell occupancies, so the known binomial distribution of the flip count before observation is not enough to form the posterior mixture.

This distinction explains both the connection and the current application boundary. Our oracle exposes separate conditional means across a range of counts, whereas ordinary binary denoising exposes a mixture determined by the observation and the target. Appendix I gives two codebooks with the same complete shell mean list at one point but different ordinary posterior means there. This is a statement about the information returned at one point. Applying our sampling lower bound to a standard binary or Gaussian diffusion model requires an additional reduction, which is not established by this conditional channel identity.

The theoretical use of the model is to isolate how information overlaps across neighboring noise levels. A request can return many estimates while covering far fewer distinct candidate target rates than the sum of the separate shell counts suggests. The band geometry quantifies this difference, and the adaptive budget theorem turns it into separate necessary costs for requests and returned estimates. This gives a precise resource question even before assigning a runtime model to a particular neural network implementation.

The prepared revision supports this account with the explicit oracle definition, a Bayes proof of the binary connection, exhaustive checks of that identity over all observations in small dimensions, and a finite grid study of window overlap. Together, these provide a precise setting in which the effect of multiple neighboring estimates can be studied under adaptive access.

Thank you for asking us to separate these levels of applicability. Section 2 now gives the interface explicitly, Appendix I establishes the binary channel relationship, and Section 6 states that connecting this access model to a particular existing sampler requires an additional argument. This identifies both the task our theorem covers and the exact point of contact with standard binary corruption.

Reviewer_GNtGOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

Diffusion models sample by calling an expensive denoiser neural network many times. For this reason a natural goal, is to try to reduce the number of times we query it. Existing theoretical works have proved lower bounds on the number of calls needed to sample up to a given accuracy. This paper tries to consider a slightly different problem, what happens if we can query the score at multiple neighboring time steps at once, how many of these "band queries" can we perform? The paper proves for a particular problem several lower bounds on the number of requests and evaluations.

Critical strengths
  • From LLM queries and the lean reproducibility it seems like there is no doubts of the correcteness of the results
  • The paper reads well and it is easy to follow
Critical weaknesses
  • The biggest weakness of this work is that it is not clear why this question is important, or if there is ever any instance in which we could perform this kind of algorithm. The sequential nature in which we obtain a particular time step inmediately limits this possibility. In its current form, the paper answers a question that is not of practical or theoretical relevance
  • It is unclear if the lower bound is tight or close to tight, do the authors have any thoughts on this?
Questions for authors

See weaknesses

6 comments
AuthorsOpenReview ↗

Response to W1: Why band access is meaningful and compatible with sequential sampling

Thank you for raising both the significance of the resource question and the sequential dependence of sampling. Our question is whether obtaining denoiser estimates at neighboring noise levels together can reduce the total number of estimates required to sample. Counting requests alone cannot answer this question, because one request can return many estimates with overlapping information. The radial budget makes this overlap explicit and yields a lower bound that remains valid for fully adaptive samplers.

The interface is concrete and preserves sequential dependence. A query specifies an already known point xtx_t, a center radius ktk_t, and a band half width btb_t. It receives posterior mean estimates at those radii, all evaluated at xtx_t. For an interior radius and bt=1b_t=1, the response is

(m^S,kt−1(xt),m^S,kt(xt),m^S,kt+1(xt)).\left(\widehat m_{S,k_t-1}(x_t),\widehat m_{S,k_t}(x_t),\widehat m_{S,k_t+1}(x_t)\right).

Only after receiving this list does the sampler select its next point, radius, and width, or stop. No value at a future point is required before that point is chosen. Thus access across radii at the current point is compatible with sequential dependence between successive points. The proof permits each next query and the stopping decision to depend on the entire response history.

For a finite codebook, the exact means are obtained by averaging its codewords on the requested Hamming shells. Appendix C explicitly constructs the accurate response family used in the lower bound. For this deterministic family, a band response can also be obtained through separate shell queries while holding xtx_t fixed. Grouping them changes the number of requests, while every returned estimate is still counted. In the example above, one request returns three estimates and incurs radial charge 1+Λ⋆1+\Lambda_\star. Here Λ⋆\Lambda_\star is the logarithmic term determined by dimension, the declared entry cap, and denoiser accuracy. These are information and evaluation counts, rather than claims about elapsed runtime.

There is also an exact connection to binary denoising. Conditioning independent binary flips on their number gives our shell channel. Appendix I proves this identity and shows that ordinary denoising combines shell means using posterior occupancy weights. This makes the channel relationship explicit, while identifying the additional reduction needed to transfer a sampling lower bound to an ordinary diffusion interface.

The new geometric contribution explains why the distinction between requests and estimates matters. The hidden rate is the logarithm of the codebook size divided by dimension. For each shell, disagreement with a reference response independent of the codebook is localized to a rate window, up to a controlled failure probability. Under the stated localization conditions, adding the separate shell bounds charges O((b+1)Λ⋆)O((b+1)\Lambda_\star) candidate rates. Our bound on their union charges O(b+Λ⋆)O(b+\Lambda_\star) for the whole band. Neighboring windows overlap, so their union pays for the movement of the window centers plus one window width.

We computed this overlap directly on a finite realizable grid. A representative case has d=4096d=4096, p=2p=2, ε=0.1\varepsilon=0.1, R⋆=dR_\star=d, k0=1024k_0=1024, and b=22b=22.

Quantity for this single bandValue
Returned shell entries45
Sum of individual shell coverage counts2277
Distinct covered rate points121
Ratio of repeated to distinct counts18.82

This case respects the entry cap and lies below grid saturation. The 18.82 ratio measures the overcount from treating overlapping shell windows separately. The numerical appendix reports all 432 parameter combinations.

Theorem 2 turns this geometric control into a sampling obstruction for complete adaptive response histories. For each declared entry cap, the hard distribution is fixed before the algorithm. At fixed denoising accuracy and moment order, Corollary 3 requires Ω(d/log⁡d)\Omega(d/\log d) returned estimates on these hard instances. This is the theoretical contribution of measuring the information supplied by a band. We have made the interface, the sequential example, and this motivation explicit in the prepared revision. Thank you for helping us clarify their connection.

AuthorsOpenReview ↗

Response to W2: Tight overlap geometry and the sampling lower bound

Thank you for asking about tightness. The overlap geometry has matching upper and lower orders under the assumptions of Proposition 13. A matching sampling upper bound under the same oracle interface and accuracy criterion remains open. The prepared revision of Section 6 now distinguishes that established result from the necessary sampling budget and the remaining algorithmic question.

Proposition 13 concerns a band whose radii lie in a compact Hamming branch. If each informative window has width Θ(H/d)\Theta(H/d), it gives

=\Theta\left(\frac{b+H}{d}\right).$$ The two contributions are the displacement of the anchors and the width of one window. Theorem 5 supplies both upper and lower bounds on the anchor displacement within the branch. Thus the additive dependence on the band width and one window width has the correct order for this geometric diameter. This identifies the sharp scale of the geometric diameter used in the argument. Theorem 2 addresses a different object: the budget required to sample from the hard target and response distribution. For each declared shell cap $R_\star$, that distribution is fixed before the algorithm. If every possible transcript satisfies the entry cap and a radial budget at most $c_{\mathrm{bud}}d$, the conditional output has TV error at least $0.9$ on at least $0.9$ of the instances. Consequently, achieving TV below $0.9$ on more than $0.1$ of those instances requires a possible path exceeding that radial budget. At fixed $p$ and $\varepsilon$, Corollary 3 gives the necessary shell count $\Omega(d/\log d)$. A matching upper bound would need to construct such a policy using the permitted mean estimates and show that its output approximates the empirical target for a fixed codebook. The relevant guarantee concerns the probabilities assigned to the target codewords, including their multiplicities, so it requires control of the full output law. The requested sampling tolerance is also distinct from the denoising accuracy $\varepsilon$. Our theorem gives the stated obstruction for any desired TV tolerance below $0.9$, but does not characterize the optimal budget as a function of a general sampling tolerance. We have made these three levels explicit in the revised discussion: matching geometric diameter, a necessary sampling budget, and an open matching algorithmic bound. We appreciate this question because it helps identify precisely what the radial budget already characterizes and what remains to be understood.

Dear authors thanks for taking the time to answer my questions.

Our question is whether obtaining denoiser estimates at neighboring noise levels together can reduce the total number of estimates required to sample.

I believe this point is understood, however, there is still no explanation as to why this question is important either for practical or theoretical reasons, ideally practical. Until there is a good justification for this I will keep my score

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.