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

arXiv: https://arxiv.org/abs/2603.20589 · HTML: https://mlsanity.com/paper/2603.20589/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 54 references that are in the map.
- First posted on arXiv 21 Mar 2026.

## Builds on (most cited first, 21 of 21)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Cascaded Diffusion Models for High Fidelity Image Generation](https://mlsanity.com/paper/2106.15282/) (2021)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Mixed-Type Tabular Data Synthesis with Score-based Diffusion in Latent Space](https://mlsanity.com/paper/2310.09656/) (2023)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Balancing Scalability and Uniformity in SAT Witness Generator](https://mlsanity.com/paper/1403.6246/) (2014)
- [Denoising Diffusion for Sampling SAT Solutions](https://mlsanity.com/paper/2212.00121/) (2022)
- [Computational bottlenecks for denoising diffusions](https://mlsanity.com/paper/2503.08028/) (2025)

## Built on by (most cited first, 3 of 3)

- [Thinking with Looped Flows](https://mlsanity.com/paper/2609.11801/) (2026)
- [The critical slowing down in training diffusion models](https://mlsanity.com/paper/2605.12597/) (2026)
- [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026)

## Abstract (arXiv)

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.