# Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 41 of its 75 references that are in the map.
- First posted on arXiv 12 Feb 2025.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 41)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [On the Variance of the Adaptive Learning Rate and Beyond](https://mlsanity.com/paper/1908.03265/) (2019)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Torsional Diffusion for Molecular Conformer Generation](https://mlsanity.com/paper/2206.01729/) (2022)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Path Integral Sampler: a stochastic control approach for sampling](https://mlsanity.com/paper/2111.15141/) (2021)
- [Neural Importance Sampling](https://mlsanity.com/paper/1808.03856/) (2018)
- [Denoising Diffusion Samplers](https://mlsanity.com/paper/2302.13834/) (2023)
- [An optimal control perspective on diffusion-based generative modeling](https://mlsanity.com/paper/2211.01364/) (2022)
- [GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training](https://mlsanity.com/paper/2009.03294/) (2020)
- [Iterated Denoising Energy Matching for Sampling from Boltzmann Densities](https://mlsanity.com/paper/2402.06121/) (2024)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Improved sampling via learned diffusions](https://mlsanity.com/paper/2307.01198/) (2023)
- [Equivariant flow-based sampling for lattice gauge theory](https://mlsanity.com/paper/2003.06413/) (2020)
- [Solving Statistical Mechanics Using Variational Autoregressive Networks](https://mlsanity.com/paper/1809.10606/) (2018)
- [Deep autoregressive models for the efficient variational simulation of many-body quantum systems](https://mlsanity.com/paper/1902.04057/) (2019)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Limitations of Autoregressive Models and Their Alternatives](https://mlsanity.com/paper/2010.11939/) (2020)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)

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

- [LEAPS: A discrete neural sampler via locally equivariant networks](https://mlsanity.com/paper/2502.10843/) (2025)
- [Trust Region Constrained Measure Transport in Path Space for Stochastic Optimal Control and Inference](https://mlsanity.com/paper/2508.12511/) (2025)
- [MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control](https://mlsanity.com/paper/2508.10684/) (2025)
- [Proximal Diffusion Neural Sampler](https://mlsanity.com/paper/2510.03824/) (2025)
- [Discrete Neural Flow Samplers with Locally Equivariant Transformer](https://mlsanity.com/paper/2505.17741/) (2025)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Discrete Feynman-Kac Correctors](https://mlsanity.com/paper/2601.10403/) (2026)
- [Bridge Matching Sampler: Scalable Sampling via Generalized Fixed-Point Diffusion Matching](https://mlsanity.com/paper/2603.00530/) (2026)
- [Rethinking Losses for Diffusion Bridge Samplers](https://mlsanity.com/paper/2506.10982/) (2025)
- [Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization](https://mlsanity.com/paper/2510.19544/) (2025)
- [Discrete Adjoint Schr"odinger Bridge Sampler](https://mlsanity.com/paper/2602.08243/) (2026)
- [IsingFormer: Augmenting Parallel Tempering With Learned Proposals](https://mlsanity.com/paper/2509.23043/) (2025)
- [Sampling from Energy distributions with Target Concrete Score Identity](https://mlsanity.com/paper/2510.23106/) (2025)
- [Diffusion-Augmented Markov Decision Processes for Maximum Entropy Reinforcement Learning](https://mlsanity.com/paper/2512.02019/) (2025)
- [Importance Weighted Score Matching for Diffusion Samplers with Enhanced Mode Coverage](https://mlsanity.com/paper/2505.19431/) (2025)
- [Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spaces](https://mlsanity.com/paper/2602.05961/) (2026)
- [Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching](https://mlsanity.com/paper/2605.30920/) (2026)
- [Diffusion-based learning framework for Constrained Nonconvex Optimization with Weighted Bootstrapped Refinement](https://mlsanity.com/paper/2502.10330/) (2025)
- [The critical slowing down in training diffusion models](https://mlsanity.com/paper/2605.12597/) (2026)
- [Boltzmann Reinforcement Learning for Noise resilience in Analog Ising Machines](https://mlsanity.com/paper/2602.09162/) (2026)
- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)
- [LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers](https://mlsanity.com/paper/2605.29005/) (2026)
- [Mode Collapse Is Cheap to Detect: A Ground-Truth-Free Pre-Flight Check for Neural Samplers](https://mlsanity.com/paper/2609.26272/) (2026)
- [Discrete Diffusion Models via Evolving Variational Autoregressive Networks](https://mlsanity.com/paper/2609.27306/) (2026)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)
- [Iterative Exact Discrete Guidance for Energy-Based Sampling](https://mlsanity.com/paper/2609.37043/) (2026)
- [Parallel Tempering for Diffusion-Based Combinatorial Optimization](https://mlsanity.com/paper/2609.37323/) (2026)
- [Fixed-point neural samplers on discrete spaces](https://mlsanity.com/paper/2610.01739/) (2026)
- [Probabilistic Algorithms for Ising Machines from Optimization to Generative AI](https://mlsanity.com/paper/2610.03972/) (2026)

## Abstract (arXiv)

Learning to sample from complex unnormalized distributions over discrete domains emerged as a promising research direction with applications in statistical physics, variational inference, and combinatorial optimization. Recent work has demonstrated the potential of diffusion models in this domain. However, existing methods face limitations in memory scaling and thus the number of attainable diffusion steps since they require backpropagation through the entire generative process. To overcome these limitations we introduce two novel training methods for discrete diffusion samplers, one grounded in the policy gradient theorem and the other one leveraging Self-Normalized Neural Importance Sampling (SN-NIS). These methods yield memory-efficient training and achieve state-of-the-art results in unsupervised combinatorial optimization. Numerous scientific applications additionally require the ability of unbiased sampling. We introduce adaptations of SN-NIS and Neural Markov Chain Monte Carlo that enable for the first time the application of discrete diffusion models to this problem. We validate our methods on Ising model benchmarks and find that they outperform popular autoregressive approaches. Our work opens new avenues for applying diffusion models to a wide range of scientific applications in discrete domains that were hitherto restricted to exact likelihood models.