The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity

arXiv:2608.13520v1 Announce Type: cross Abstract: We study masking diffusion for discrete sampling and introduce a path-resolved measure of data geometry called the unmasking growth complexity ({extsf{UGC}xspace}). Its local increments directly control Kullback--Leibler (KL) discretization error, yielding a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes. In log-reveal-odds coordinates, this structure yields optimized single-block and multi-block schedules, and quantifies the gains from adapting computational effort to data geometry. Crucially, we show how {extsf{UGC}xspace} increments can be estimated from samples via KL increments along coupled reveal trajectories. This leads to certified-optimal samplers that achieve a prescribed KL error with high probability and iteration complexity within a constant factor of the corresponding oracle procedure. Collapsing the gc path yields the aggregate {extsf{UGC}xspace} mass, which connects to classical multivariate dependence measures and complexity measures from previous analyses of discrete diffusion. In the fine-partition limit, the squared integral of the square-root {extsf{UGC}xspace} density determines the sharp leading-order optimal Euler discretization error. Examples exhibit substantial dimension-dependent gains over coarse schedules, including widetilde{Omega}(sqrt{d}) improvements achievable with a constant number of adaptively placed blocks.

Related

• Denoising growth complexity: Data geometry and certified schedules for diffusion sampling
• Geometry-Correct Diffusion Posterior Sampling with Denoiser-Pullback Curvature Guidance and Manifold-Aligned Damping
• From Atoms to Entropy: Optimal Noise Allocation for Diffusion Training in the Convex Regime
• Simple Self-Conditioning Adaptation for Masked Diffusion Models

Source: arXiv cs.AI | 2026-08-14