Research map / Probabilistic and scientific modeling / Variational and generative sampling

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

NeurIPS 2026 · Probabilistic and scientific modeling › Variational and generative sampling · approach: Score-based generative modeling analysis · 0 citations (OpenAlex)

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.

Uses uniform solution sampling for random k-SAT/k-XORSAT as a principled benchmark for diffusion samplers, comparing continuous vs masked discrete diffusions with BP and learned local denoisers and testing smart variable orderings.

Problem

Benchmarks for generative models over discrete distributions (e.g., tabular/text) lack principled targets; random CSPs such as k-SAT and k-XORSAT offer a setting where theory predicts achievable accuracy, but it is unclear how diffusion samplers behave on them.

Approach

Applies insights from random CSP statistical physics (BP denoisers, cavity initialization, dynamical phase transition) to derive an ideal local denoiser and target accuracy, then compares learned NN denoisers against it; proposes reversed-leaf and reverse-degree variable orderings and a variable-dependent noise matrix W for continuous diffusions.

Key results

• Continuous diffusions systematically outperform masked discrete diffusions on 4-SAT and 4-XORSAT success rate, with BP and learned denoisers.
• Learned NN denoisers nearly match BP denoiser success rates, and the cavity-initialized BP is shown to be optimal among local denoisers in score-matching error.
• Reversed-leaf ordering lets discrete masked diffusion on XORSAT reach the dynamical phase transition alpha_d, versus the lower alpha_mask under random ordering.

Surprising findings

• Confidence-based (model-confidence) unmasking orderings give no gain over random ordering for XORSAT.
• Continuous diffusion outperforms masked discrete diffusion, contrary to the intuition that discrete diffusions suit discrete data.

Limitations

• Results focus on random CSPs with uniform solution targets, which may not transfer to real tabular, text or genomic data.
• Large formulas near or beyond the dynamical phase transition remain challenging; theory is non-rigorous for SAT at k=3,4.
• Gap between BP and NN denoisers is larger for XORSAT, which is harder to train.

Experimental setup

Datasets: random 4-SAT instances (planted and UniGen-sampled solutions) random 4-XORSAT instances (Gaussian elimination solutions)

Benchmarks: random 4-SAT random 4-XORSAT

Metrics: success rate KL divergence bound to uniform

Baselines: BP denoiser (uniform init) BP denoiser (cavity init) masked discrete diffusion with random ordering UniGen

Builds on: denoising diffusion probabilistic models masked discrete diffusion loopy belief propagation UniGen

Closest papers by meaning

• Constrained Discrete Diffusion (NeurIPS 2025 · similarity 0.89)
• Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models (ICLR 2024 · similarity 0.89)
• Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.89)
• Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms (NeurIPS 2025 · similarity 0.88)
• Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees (NeurIPS 2025 · similarity 0.87)
• Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.87)