Research map / Image generation / Fast diffusion sampling
Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Scalable Discrete Diffusion Samplers (SDDS), with an RL/PPO-based reverse-KL training and a self-normalized NIS forward-KL training that avoid backprop through all diffusion steps, plus adaptations of SN-NIS and NMCMC for unbiased sampling with discrete diffusion models.
Problem
Diffusion samplers for discrete neural probabilistic optimization require backpropagation through the entire diffusion trajectory, so memory scales linearly with the number of steps; they also lack unbiased sampling methods because diffusion models only provide approximate likelihoods.
Approach
Reformulate the reverse-KL objective as an episodic RL problem optimized with PPO, and rewrite the forward-KL gradient with self-normalized neural importance sampling and Monte Carlo over diffusion steps, so that per-step mini-batching cuts memory; additionally adapt SN-NIS and NMCMC to diffusion path likelihoods for unbiased Ising sampling.
Key results
- On RB-large MIS, SDDS rKL w/ RL reaches 39.97 vs DiffUCO 39.44 and Gurobi 42.51 (time-limited), setting new neural state of the art on 6 of 7 UCO benchmarks.
- On the 24x24 Ising model at beta_c=0.4407, SDDS fKL w/ MC gives free energy -2.11209 vs optimal -2.11215, outperforming the AR reimplementation (-2.09344) and the reported AR baseline (-2.1128).
- Sampling 150 solutions instead of 30, SDDS fKL w/ MC and rKL w/ RL are best in 6 of 7 cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train with SDDS: rKL w/ RL instead of DiffUCO | GNN diffusion model · UCO test benchmarks, average solution quality | solution quality | Helped |
| Train with SDDS: fKL w/ MC instead of SDDS: rKL w/ RL | GNN diffusion model · UCO with 150 sampled solutions | best solution quality | Mixed |
| Use SDDS: fKL w/ MC instead of the AR reimplementation | U-Net diffusion model · 24×24 Ising grid, βc=0.4407 | free energy estimate: -2.09344 \pm 0.00063 -> -2.11209 \pm 0.00008 | Helped |
| Apply conditional expectation in the final diffusion step (ablation) | SDDS models · UCO test benchmarks | solution quality | No clear effect |
| Add per-step probability clipping for asymptotically unbiased sampling (ablation) | diffusion models · unbiased estimation | estimation performance | No clear effect |
Surprising findings
- The fKL-trained model performs worst on average solution quality with 30 samples but best when sampling 150 solutions, reflecting mass-covering behaviour.
- DiffUCO collapsed to predicting only +1 or -1 for every spin in the Ising setting, failing at unbiased sampling.
Limitations
- Fair-comparison and sampling bias: fKL-trained models have worse average solution quality with few samples.
- The rKL objective introduces new optimization hyperparameters (PPO parameters) requiring tuning.
- Asymptotic unbiasedness requires clipping probabilities, which was not found to improve results in practice.
Experimental setup
Datasets: RB graphs (MIS, MaxCl) Barabasi-Albert graphs (MDS, MaxCut) 2D Ising model 24x24 lattice
Benchmarks: RB-small MIS RB-large MIS BA-small MDS BA-large MDS RB-small MaxCl BA-small MaxCut BA-large MaxCut 2D Ising 24x24 free energy/internal energy/entropy
Metrics: average independent set size dominating set size clique size cut size free energy internal energy entropy effective sample size per sample
Baselines: DiffUCO LTFT Gurobi VAN AR (autoregressive NIS) DiffUCO: CE
Builds on: DiffUCO Variational Annealing Proximal Policy Optimization Self-Normalized Neural Importance Sampling Neural MCMC
Closest papers by meaning
- A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization (ICML 2024 · similarity 0.91)
- Improved off-policy training of diffusion samplers (NeurIPS 2024 · similarity 0.91)
- MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control (NeurIPS 2025 · similarity 0.90)
- Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms (NeurIPS 2025 · similarity 0.90)
- NETS: A Non-equilibrium Transport Sampler (ICML 2025 · similarity 0.90)
- On scalable and efficient training of diffusion samplers (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.