mlsanityData to 14 Oct 2026

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

arXiv 2603.20589 ↗First posted 21 Mar 2026cs.LGcited by 3

Not on the map. Why?

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.

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

21 of 54 references.

References · 21

  1. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  2. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 9,122
  3. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  4. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,585
  5. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,101
  6. 2021Improved Denoising Diffusion Probabilistic Modelscited by 3,761
  7. 2021Structured Denoising Diffusion Models in Discrete State-Spacescited by 1,719
  8. 2021Cascaded Diffusion Models for High Fidelity Image Generationcited by 1,163
  9. 2024Simplified and Generalized Masked Diffusion for Discrete Datacited by 626
  10. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 574
  11. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  12. 2023Mixed-Type Tabular Data Synthesis with Score-based Diffusion in Latent Spacecited by 186
9 more
  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  2. 2024Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planningcited by 135
  3. 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
  4. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
  5. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  6. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  7. 2014Balancing Scalability and Uniformity in SAT Witness Generatorcited by 5
  8. 2022Denoising Diffusion for Sampling SAT Solutionscited by 4
  9. 2025Computational bottlenecks for denoising diffusionscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Thinking with Looped Flowscited by 9
  2. 2026The critical slowing down in training diffusion modelscited by 1
  3. 2026Parallelism, critical windows, and separations among diffusion language modelscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025Error Bounds and Optimal Schedules for Masked Diffusions with Factorized Approximations
  2. 2025Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions
  3. 2026Why Gaussian Diffusion Models Fail on Discrete Data and How to Prevent It?
  4. 2025Debiasing Guidance for Discrete Diffusion with Sequential Monte Carlo
  5. 2026Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
  6. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models
  7. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
  8. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms