mlsanityData to 7 Oct 2026

Denoising Diffusion for Sampling SAT Solutions

arXiv 2212.00121 ↗First posted 30 Nov 2022cs.AI cs.LGcited by 4

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Generating diverse solutions to the Boolean Satisfiability Problem (SAT) is a hard computational problem with practical applications for testing and functional verification of software and hardware designs. We explore the way to generate such solutions using Denoising Diffusion coupled with a Graph Neural Network to implement the denoising function. We find that the obtained accuracy is similar to the currently best purely neural method and the produced SAT solutions are highly diverse, even if the system is trained with non-random solutions from a standard solver.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 24 of its 30 references that are in the map. First posted on arXiv 30 Nov 2022.

Builds on

24 of 30 references.

Closest ancestors · 5

Same direction, newest first

  1. 2022Diffusion Models: A Comprehensive Survey of Methods and Applications2 Sep
  2. 2021High-Resolution Image Synthesis with Latent Diffusion Models20 Dec
  3. 2021Structured Denoising Diffusion Models in Discrete State-Spaces7 Jul
  4. 2021Score-based Generative Modeling in Latent Space10 Jun
  5. 2021Cascaded Diffusion Models for High Fidelity Image Generation30 May

Other references · 19

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  2. 2020DiffWave: A Versatile Diffusion Model for Audio Synthesiscited by 1,339
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  4. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 566
  5. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  6. 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 282
  7. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  8. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 263
  9. 2021Autoregressive Diffusion Modelscited by 208
  10. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  11. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  12. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
7 more
  1. 2021Symbolic Music Generation with Diffusion Modelscited by 152
  2. 2019Guiding High-Performance SAT Solvers with Unsat-Core Predictionscited by 61
  3. 2021Goal-Aware Neural SAT Solvercited by 27
  4. 2019PDP: A General Neural Framework for Learning Constraint Satisfaction Solverscited by 14
  5. 2020Enhancing SAT solvers with glue variable predictionscited by 11
  6. 2022Unsupervised Training for Neural TSP Solvercited by 9
  7. 2014Balancing Scalability and Uniformity in SAT Witness Generatorcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 2.

4 papers.

  1. 2024Understanding GNNs for Boolean Satisfiability through Approximation Algorithmscited by 3
  2. 2026Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problemscited by 3
  3. 2026Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problemscited by 1
  4. 2025A Geometric Perspective on the Difficulties of Learning GNN-based SAT Solverscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Neural Approaches to SAT Solving: Design Choices and Interpretability
  2. 2026Diffusion as a Training Curriculum for Timestep-Free Iterative Reasoning
  3. 2025Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs
  4. 2026Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization
  5. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
  6. 2025A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem
  7. 2023Accelerating Diffusion-based Combinatorial Optimization Solvers by Progressive Distillation
  8. 2026Learning How to Cube