Abstract
We study a discrete denoising diffusion framework that integrates a sample-efficient estimator of single-site conditionals with round-robin noising and denoising dynamics for generative modeling over discrete state spaces. Rather than approximating a discrete analog of a score function, our formulation treats single-site conditional probabilities as the fundamental objects that parameterize the reverse diffusion process. We employ a sample-efficient method known as Neural Interaction Screening Estimator (NeurISE) to estimate these conditionals in the diffusion dynamics. Controlled experiments on synthetic Ising models, MNIST, and scientific data sets produced by a D-Wave quantum annealer, synthetic Potts model and one-dimensional quantum systems demonstrate the proposed approach. On the binary data sets, these experiments demonstrate that the proposed approach outperforms popular existing methods including ratio-based approaches, achieving improved performance in total variation, cross-correlations, and kernel density estimation metrics.
Introduction
Generative diffusion models have achieved remarkable success in continuous domains such as image and video synthesis. However, extending these successes to discrete state spaces—where variables are binary or categorical—remains a significant challenge. In continuous spaces, diffusion models rely on the score function (the gradient of the log-density) to guide the reverse process. In discrete settings, gradients are not naturally defined, leading researchers to rely on continuous relaxations or complex variational lower bounds (VLB). These approaches often suffer from training instability, poor sample quality, or excessive data requirements to capture high-dimensional dependencies.
This work introduces a principled, sample-efficient discrete diffusion framework that respects the combinatorial structure of discrete data. By shifting the focus from global score estimation to local single-site conditional probabilities, we provide a more tractable and efficient path for generative modeling in discrete domains.
Methodology: Local Conditionals and NeurISE
The core innovation of this framework is the parameterization of the reverse diffusion process using single-site conditional probabilities. This approach simplifies the learning task by decomposing the global joint distribution into local components.
Round-Robin Noising
The model employs a "round-robin" noising scheme. Unlike standard diffusion where noise is added to all variables simultaneously, this scheme noises only one coordinate at a time in a fixed sequence. This structured approach allows the reverse process to be modeled as a sequence of local resampling steps.
NeurISE Estimator
To learn these local conditionals, we utilize the Neural Interaction Screening Estimator (NeurISE). NeurISE is specifically designed for sample-efficient learning in discrete graphical models by exploiting the "interaction screening" property. It focuses on how a single variable depends on its local neighborhood, avoiding the need to model the entire global distribution simultaneously. This locality makes the estimator highly robust even with limited training data.
Reverse Sampling
The generative process mirrors the forward noising: it visits each coordinate in reverse order and resamples its value based on the learned local conditionals. Theoretical analysis shows that under a "hard-noise" limit, this process collapses into a standard autoregressive model, bridging two major families of generative modeling.
Experimental Evaluation
We evaluated the proposed "NeurISE Diffusion" across several challenging benchmarks, including synthetic Ising (Edwards-Anderson) and Potts models, binarized MNIST, and high-dimensional data from a D-Wave quantum annealer.
As shown in the quantitative results, NeurISE Diffusion consistently outperforms baselines such as D3PM and SEDD. On the Ising model (L=25), our method exhibits a significantly sharper decay in Total Variation (TV) distance and cross-correlation error as the training set size increases. Furthermore, the training time for NeurISE remains stable and efficient, whereas methods like D3PM show a rapid increase in computational cost with larger datasets.
Qualitative results on binarized MNIST further validate the approach. NeurISE Diffusion generates clear, recognizable digits with fewer artifacts than D3PM or SEDD. In high-dimensional scientific applications, such as the 2,000-variable D-Wave dataset, NeurISE achieved an MMD of 0.016, vastly outperforming SEDD's 65.03, demonstrating its scalability and precision for complex physical systems.
Discussion and Future Work
A key insight of this work is that "local is better than global" for discrete diffusion. By parameterizing the reverse kernel through ratios of single-site conditionals, we simplify the learning objective. We also provide a new theoretical bound for Total Variation error, showing that generation error is a sum of mixing error, local kernel estimation error, and initial noise sampling error.
While the current round-robin scheme uses a fixed ordering, future work could explore random or learned orderings. Additionally, while the "canonical" reverse process was used here, investigating other non-local reverse kernels that might be even easier to learn remains a promising direction.
Summary updated