CS Paper Radar

Discrete Diffusion Playground: A 2D Benchmark for Discrete Generative Models

Justin Shao, Sihyun Park, David Ryan Koes, Maria Chikina

cs.LG ·submitted 2026-11-08 01:57 UTC · v1
top venuebenchmarkcode/data

Abstract

Discrete diffusion is a promising framework for categorical generative modeling, but current evaluation protocols often fail to reveal whether models have actually learned the target distribution. We introduce the Discrete Diffusion Playground, a diagnostic benchmark that converts known 2D continuous distributions into binary token sequences through an exact discretized bijection. This creates a rare setting in which models are trained on discrete sequences, but generated samples can be decoded back into 2D and compared directly against a known ground-truth distribution. The benchmark spans smooth Gaussian mixtures and tilted checkerboards with sharp boundaries, disconnected support, and coordinate-dependent structure, allowing it to expose failures that are invisible in standard proxy metrics. It supports exact grid divergences, Wasserstein distances, density visualizations, and nonparametric two-sample tests, providing both quantitative evaluation and interpretable failure diagnosis. Using this testbed, we show that masked diffusion models can learn meaningful adaptive reveal orders but remain less stable than autoregressive baselines on smooth targets and largely fail on tilted checkerboards, where autoregressive models preserve the target geometry. Control experiments with reversed and interleaved token orderings show that autoregressive performance is not explained by favorable bit order alone. The Playground provides a simple but stringent benchmark for stress-testing discrete generative models and for developing evaluation metrics that detect real distributional mismatch rather than proxy performance. Our code is available at https://github.com/shaojus/DiscreteDiffusionPlayground .

Comment
18 pages, 7 main figures, 2 tables. Accepted at NeurIPS 2026 (Evaluations and Datasets Track)

Closest papers

Nearest neighbours by meaning across the whole index.

Acquisition Function-Guided Generation for Bayesian Optimization over Discrete Spaces

cs.LG ·2026-10-16 ·Tommaso Ancilli, Thomas Wedenig, Henry Moss, Robert Peharz
code/data similarity 0.64
Abstract

Bayesian optimization (BO) over discrete spaces is challenging due to missing gradients and the sparsity of valid solutions. Latent-space BO sidesteps both issues by fitting a surrogate in the latent space of a generative model, which however substantially complicates the direct incorporation of domain knowledge that is naturally expressed in the original discrete space. In this work, we instead combine a pretrained generative model with a surrogate defined directly in data space, where inductive biases such as domain-specific kernels can be readily incorporated. Rather than maximizing the acquisition function over the discrete design space, our method samples candidates from the generative model under a distribution tilted by the acquisition function. To recover useful gradients for sampling, we embed this tilted distribution into a diffusion bridge that yields a smooth, posterior-averaged acquisition function. This leads to \emph{acquisition function guided generation} (AFGG), which we instantiate with a categorical diffusion model and an autoregressive normalizing flow. Across a broad suite of molecular benchmarks, the diffusion model variant performs on par with leading BO methods, while the flow model variant outperforms state-of-the-art methods in most cases and remains highly competitive otherwise. Our implementation is available at https://anonymous.4open.science/r/afgg.

0.24

Two-Stage Score Estimation for Group-Specific Diffusion Models

cs.LG stat.MLmath.ST ·2026-10-14 ·Huitao Yang, Oscar Hernan Madrid Padilla
theory similarity 0.64
Abstract

Generative modeling across related distributions raises a question: how can shared structure support accurate generation for a target distribution with limited observations? We develop a statistical framework for diffusion transfer that analyzes a shared pooled score together with a target-specific offset. Under Besov regularity of the pooled density and a stable hierarchical composition model for the offset, we derive convergence rates that separate the costs of learning these components and identify when a simpler offset yields a faster risk-bound rate than separate fitting. Under suitable boundary and regularity assumptions, we prove that the offset remains bounded and jointly regular as diffusion time approaches zero. These results allow the lower time cutoff to vanish polynomially and provide total-variation guarantees for diffusion models as density estimators. Synthetic simulations and image benchmarks provide a proof of concept for the framework.

0.19

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

cs.LG stat.ML ·2026-10-06 ·Dongsun Yoon, Saptarshi Chakraborty
similarity 0.64
Abstract

Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size $s_n(P_0)$, a sample-size-dependent measure of distributional complexity. Given $n$ independent and identically distributed (i.i.d.) samples from an unknown data distribution $P_0$ on $[K]^d$, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as $O(\sqrt{s_n(P_0)/n})$, while the expected Kullback--Leibler (KL) divergence is bounded by $O(\frac{1}{n}s_n(P_0)\log(eK^d/s_n(P_0))\log n)$. Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of $\log n$. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through $s_n(P_0)$, while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.

0.28

Escaping the Curse of Dimensionality in One-Step Flow-Based Generative Models

cs.LG math.ST ·2026-11-11 ·Konstantin Yakovlev
top venue similarity 0.64
Abstract · 52 pages; accepted at NeurIPS 2026

Flow and diffusion-based generative models achieve state-of-the-art quality, but require multiple forward passes at inference time, making them computationally costly. Consistency models overcome this by learning a flow map directly, enabling few-step generation and dramatically reducing the computation needed at test time. However, formal statistical guarantees for such one-step generators are scarce. Existing results either suffer from the curse of dimensionality or rely on impractical loss functions. We investigate whether one-step flow-based models can escape the curse of dimensionality under the assumption that the data distribution is generated by a low-dimensional surface perturbed with Gaussian noise. In this setup, we derive approximation and generalization error bounds for the flow map estimate that circumvent the curse of dimensionality. Our findings provide the first principled explanation for practical success of one-step flow-based generative models.

0.26

Simplex Relaxation for Discrete Diffusion

cs.CL ·2026-08-11 ·Jinya Sakurai, Patrick Pynadath, Satoshi Hayakawa, Jaehong Yoon, Xulei Yang +2 more
similarity 0.64
Abstract

Discrete diffusion models for categorical generation are defined by a corruption kernel, which determines the intermediate state space and the associated reverse prediction problem. Within this family, uniform diffusion has been extensively developed, with recent work connecting its categorical corruption process to continuous representations and dynamics. Motivated by this view, we ask whether uniform discrete diffusion can be augmented with an explicit continuous state while leaving its categorical corruption process unchanged. We introduce Simplax, an exact Dirichlet--categorical augmentation that couples each corrupted categorical state with an auxiliary simplex-valued variable while preserving the uniform diffusion process as its categorical marginal. This augmentation yields a tractable Rao--Blackwellized reverse-bridge objective and a stochastic reverse sampler, while retaining the corrupted categorical state as the denoiser input. Empirically, Simplax improves the generative perplexity--entropy tradeoff on unconditional OpenWebText generation. On Sudoku, a model trained exclusively on $30$-clue puzzles achieves the highest accuracy among the compared methods across all evaluated clue densities, including the minimum uniquely solvable $17$-clue regime, and also achieves the highest validity in unconditional generation.

0.39

Convergence of Denoising Diffusion Probabilistic Models: A Rényi Divergence Perspective

cs.IT ·2026-10-18 ·Wenliang Liu, Santiago Mazuelas, Guanding Yu, Renjie Liao, Lele Wang +1 more
similarity 0.63
Abstract

Denoising diffusion probabilistic models (DDPMs) have emerged as a powerful framework for generative modeling by transforming standard Gaussian inputs into outputs that approximate a target distribution. While DDPMs have been proved to converge in total variation, KL divergence, and Wasserstein distance, these discrepancy measures share a fundamental limitation of being insensitive to distributional mismatch in low-probability regions. To address this, we adopt the stronger Rényi divergence as the discrepancy measure. Leveraging a Girsanov-type change-of-measure argument, we establish the first Rényi characterization of DDPMs to the best of our knowledge, showing that the total error decomposes into a mixing error, a discretization error, and a score estimation error. We assume the target distribution is sub-Gaussian and characterize the score error via the cumulant generating function, relaxing both the log-Sobolev-inequality and $L^\infty$-score-error conditions used in prior Rényi divergence analyses of inexact Langevin Monte Carlo, a score-based sampling algorithm closely related to DDPM. Our results also establish an iteration complexity for achieving $ε$-accuracy in $α$-Rényi divergence that is asymptotically proportional to $α^3/ε$. Finally, by extending our analysis, we establish the first Rényi divergence convergence guarantee for critically damped DDPMs, a kinetic variant governed by critically damped Langevin dynamics. Similar to existing characterizations of critically damped DDPMs, this result shares the structural scaling of standard DDPMs, differing by at most a logarithmic factor in the mixing error exponent, and supports the conjecture that critically damped DDPMs do not yield a theoretical improvement.

0.21

Regularized Wasserstein Distance for Discrete Generative Modeling and Clustering Analysis

cs.CV cs.LG ·2026-10-31 ·Senmao Ye, Fei Liu, Dawei Zhang, Yuqian Zheng, Jun Zhang +1 more
code/data similarity 0.62
Abstract

In this paper, we formulate clustering analysis as discrete generative modeling. Specifically, when the generator is restricted to a finite candidate space, the generated samples naturally emerge as the most representative prototypes of the underlying data distribution. To model such a discrete candidate space, we employ a Discrete Distribution Network (DDN). However, DDN suffers from unstable training due to its hard nearest-neighbor selection. To stabilize training and encourage geometric consistency, we replace DDN's l2 loss between images with regularized Wasserstein distance between the empirical distributions of real and generated images. The resulting framework, termed Discrete Generative Clustering (DGC), offers four notable advantages: 1) the learned cluster centers are directly interpretable, as they are realistic synthetic samples; 2) the inference cost scales logarithmically with the number of clusters, i.e., O(log K), making the method scalable to extremely large K; 3) the regularized Wasserstein distance provides a smooth and well-behaved optimization objective that facilitates stable convergence, whereas DDN's l2 loss tends to converge to poor local optima; and 4) DGC replaces DDN's nearest-neighbor selection with random-neighbor selection, which avoids the density shift problem during multi-step forward. Extensive experiments on several benchmarks demonstrate the effectiveness and desirable properties of DGC. The code is publicly available at GitHub.

0.32

Intrinsic Gradient Barriers in Pushforward Deep Generative Models

cs.LG stat.MLmath.ST ·2026-10-25 ·Edric Tam, Qingyang Liu, Barbara Engelhardt, Ray Bai
similarity 0.62
Abstract · 45 pages, 9 figures

Broad classes of deep generative models (DGMs) operate by learning to map a simple source distribution, such as a standard Gaussian, to a complex high-dimensional target distribution. Despite their success, DGMs often empirically struggle to accurately represent distributions with heavy tails or well-separated modes. In this work, we show that these difficulties reflect intrinsic properties of the underlying transport problem rather than particular neural network architectures or training procedures. We establish quantitative lower bounds on the gradients and Jacobians of pushforward mappings that transport log-concave source distributions to such targets. For heavy-tailed target distributions, the required gradient magnitude grows as the target develops increasingly large moments. For multimodal target distributions, the low-probability regions between well-separated modes similarly force large gradients in the transport map. We discuss how such large derivatives relate to trade-offs between expressivity and numerical stability. Our results hold under substantially weaker regularity conditions than previous analyses and remain stable under perturbations of the target distribution. Finally, we show that these obstructions can be mitigated when the goal is approximation of a given density rather than generative modeling. Specifically, we propose simple classes of bijective reparametrizations that can alleviate the difficult geometric structure and reduce the gradient burden placed on the learned generative map. Numerical experiments support our theoretical analysis.

0.15