Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems

• URL: http://arxiv.org/abs/2603.20589v1
• Date: Sat, 21 Mar 2026 01:16:57 GMT
• Title: Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems
• Abstract summary: Several groups have recently used random $k$-satisfiability ($k$-SAT) as a synthetic benchmark for new generative techniques.<n>We show that fundamental insights from the theory of random constraint satisfaction problems have observable implications on the behavior of generative techniques on such benchmarks.
• Score: 14.051523781282674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Generating data from discrete distributions is important for a number of application domains including text, tabular data, and genomic data. Several groups have recently used random $k$-satisfiability ($k$-SAT) as a synthetic benchmark for new generative techniques. In this paper, we show that fundamental insights from the theory of random constraint satisfaction problems have observable implications (sometime contradicting intuition) on the behavior of generative techniques on such benchmarks. More precisely, we study the problem of generating a uniformly random solution of a given (random) $k$-SAT or $k$-XORSAT formula. Among other findings, we observe that: $(i)$~Continuous diffusions outperform masked discrete diffusions; $(ii)$~Learned diffusions can match the theoretical `ideal' accuracy; $(iii)$~Smart ordering of the variables can significantly improve accuracy, although not following popular heuristics.

Related papers

• On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free [49.34727933066799]
  Masked discrete diffusion is a flexible paradigm for text generation in which tokens are corrupted by special mask symbols before being denoised.<n>We show that Euler samplers can achieve $epsilon$-accuracy in total variation (TV) with $tildeO(d2epsilon-3/2)$ discrete score evaluations.<n>We then propose a Mask-Aware Truncated Uniformization (MATU) approach that both removes bounded-score assumptions and preserves unbiased discrete score approximation.
  arXiv  Detail & Related papers  (2025-09-26T03:50:17Z)
• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  We describe an algorithm that satisfies local differential privacy, performs $tildeO(k3/2)$ non-adaptive queries to individuals.<n>We also introduce a new object we dub the Scheff'e graph, which captures structure of the differences between distributions in $Q$.
  arXiv  Detail & Related papers  (2025-09-19T17:41:15Z)
• Gaussian Universality for Diffusion Models [13.722991812691054]
  We show that the test error of a generalized linear model $f(mathbfW)$ trained for a classification task on the diffusion data matches the test error of $f(mathbfW)$ trained on the Gaussian Mixture.<n>We also show that for any $1$- Lipschitz scalar function $phi$, $phi(mathbfx)$ is close to $mathbbE phi(mathbfx)$ with high probability for $mathbfx$ sampled from the conditional diffusion model
  arXiv  Detail & Related papers  (2025-01-13T23:13:01Z)
• SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups [14.925722398371498]
  We introduce a novel discrete diffusion model that simplifies the task of learning a complicated distribution over $S_n$.<n>We provide empirical guidelines for selecting the diffusion length based on the theory of random walks on finite groups.<n>Our model achieves state-of-the-art or comparable performances on solving tasks including sorting 4-digit images, jigsaw puzzles, and traveling salesman problems.
  arXiv  Detail & Related papers  (2024-10-03T19:37:40Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
  conditional distributions is a central problem in machine learning.<n>We propose a new paradigm that integrates both paired and unpaired data.<n>We show that our approach can theoretically recover true conditional distributions with arbitrarily small error.
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  We establish a fast convergence theory for the denoising diffusion probabilistic model (DDPM) under minimal assumptions.<n>We show that the convergence rate improves to $O(k/T)$, where $k$ is the intrinsic dimension of the target data distribution.<n>This highlights the ability of DDPM to automatically adapt to unknown low-dimensional structures.
  arXiv  Detail & Related papers  (2024-09-27T17:59:10Z)
• Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
  This paper presents explicit non-asymptotic bounds on the forward diffusion error in total variation (TV)<n>We parametrise multi-modal data distributions in terms of the distance $R$ to their furthest modes and consider forward diffusions with additive and multiplicative noise.
  arXiv  Detail & Related papers  (2024-08-25T10:28:31Z)
• Doubly Robust Conditional Independence Testing with Generative Neural Networks [8.323172773256449]
  This article addresses the problem of testing the conditional independence of two generic random vectors $X$ and $Y$ given a third random vector $Z$. We propose a new non-parametric testing procedure that avoids explicitly estimating any conditional distributions.
  arXiv  Detail & Related papers  (2024-07-25T01:28:59Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Diffusion models as plug-and-play priors [98.16404662526101]
  We consider the problem of inferring high-dimensional data $mathbfx$ in a model that consists of a prior $p(mathbfx)$ and an auxiliary constraint $c(mathbfx,mathbfy)$. The structure of diffusion models allows us to perform approximate inference by iterating differentiation through the fixed denoising network enriched with different amounts of noise.
  arXiv  Detail & Related papers  (2022-06-17T21:11:36Z)
• Squared $\ell_2$ Norm as Consistency Loss for Leveraging Augmented Data to Learn Robust and Invariant Representations [76.85274970052762]
  Regularizing distance between embeddings/representations of original samples and augmented counterparts is a popular technique for improving robustness of neural networks. In this paper, we explore these various regularization choices, seeking to provide a general understanding of how we should regularize the embeddings. We show that the generic approach we identified (squared $ell$ regularized augmentation) outperforms several recent methods, which are each specially designed for one task.
  arXiv  Detail & Related papers  (2020-11-25T22:40:09Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.