Beyond Query Count: A Radial Budget for Sampling

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.