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

Alankrita Bhatt; Mukur Gupta; Germain Kolossov; Andrea Montanari

cs.LGMar 21, 2026

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

Authors: Alankrita Bhatt, Mukur Gupta, Germain Kolossov, Andrea Montanari

Organizations: Granica Computing Inc. – granica.ai · Stanford University

Abstract

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.

Figures & tables

Figure 1: 4-SAT (

N=300

) Left: The learned NN denoiser (solid) matches the BP denoiser (dashed), and continuous diffusion (blue) outperforms discrete diffusion (red) for both denoisers at locality radius

r=3

. Right: Smart variable ordering improves discrete diffusion with

r=100

BP denoiser. We compare random ordering with reverse-degree and dynamic reverse-degree orderings. We report success rate (probability of producing a satisfying assignment) versus clause density

\alpha

, averaged over 500 random formulas. Shaded regions: 95% confidence interval. Vertical line: dynamical phase transition

\alpha_{\mbox{\tiny\rm d}}(k=4)\approx 9.38

Figure 2: 4-XORSAT (

N=100

): learned NN denoiser (solid lines) vs. BP denoiser (dashed lines). Success rate as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions. Each panel corresponds to a different locality radius for the denoisers

r\in\{2,3,6,9\}

. Success rates are computed over 500 random formulas. The vertical line corresponds to the dynamical phase transitoion at

\alpha_{\mbox{\tiny\rm d}}(k=4)\approx 0.77228

Panel of Figure 3 — Figure 3: 4-SAT. Two left panels: Effect of BP message initialization in discrete diffusion. We compare zero, warm-start, and cavity-based initializations for $N=300$ using a BP denoiser with radius $r=1$ ( left ) and $r=2$ ( right ). Two right panels: Effect of variable ordering in discrete diffusion with a BP denoiser. We compare random, reverse min-degree, and dynamic reverse min-degree orderings for $N=500$ ( left ) and $N=1000$ ( right ) with $r=100$ . Each panel reports success rate versus clause density $\alpha$ , averaged over 500 random formulas; the vertical line marks the dynamical phase transition $\alpha_{\mbox{\tiny\rm d}}(k=4)\approx 9.38$ .

Figure 4:

k

-XORSAT (

N=300

): reversed-leaf (red) vs reversed-degree (black) vs random (blue) decoding ordering. Success rate as a function of clause density

\alpha

for

k\in\{4,\dots,8\}

obtained using discrete diffusion with BP denoiser with

r=300

. The two vertical lines are the theoretical thresholds for random (

\alpha_{\mbox{\tiny\rm mask}}

) and optimal (

\alpha_{\mbox{\tiny\rm d}}

) decoding ordering at every value of

k

. Success rates are computed over 500 random formulas.

Figure 5: 4-XORSAT (

N=300

): reversed-leaf (red) vs random (blue) ordering in continuous diffusion. Success rate as a function of clause density

\alpha

obtained using

{\boldsymbol{W}}

in Eq. ( 2.2 ), with a BP and NN denoiser. The vertical line indicates the theoretical dynamical phase-transition threshold.

Figure 6: 4-SAT (

\alpha=2,r=3

) : Distribution of probabilities of sampled solutions using BP and NN (trained on either planted on UniGen formulas) discrete diffusion samplers. The verticle line corresponds to

\phi(\alpha)=\log(2)+\alpha\log(1-2^{-k})

. Averaged over 3 different formulas and 100 simulations per formula.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: Neural network denoiser architecture for $r\geq 2$ , with target variable $i$ . $(a)$ illustrates the overall architecture, assuming for simplicity that $\partial i=\{1,2,\dotsc,|\partial i|\}$ . $(b)$ illustrates the detailed architecture of the $\mathrm{ClauseEmbedder}$ component (assuming again for simplicity that $i_{a}(1)=i$ ) which creates a radius $r$ representation for the clause $a$ w.r.t. variable $i$ , by performing a message passing-like update that utilizes the radius $r-1$ representation of each variable present in the clause.

Figure 8: 4-SAT (

N=100

) : Comparison of training SAT learned NN denoiser with planted formulas and solutions generated with UniGen. Success rate as a function of clause density

\alpha

on random 4-SAT instances with

r=2

( left ) and

r=3

( right ). Success rates are computed over 100 random formulas.

Figure 9: 4-XORSAT (

N=100

): Comparison of learned NN denoisers trained on biased solutions, unbiased solutions, and a mixed curriculum that begins with biased solutions and then transitions to unbiased solutions. Success rate as a function of clause density

\alpha

on random 4-XORSAT instances with

r=2

( left ) and

r=3

( right ). Success rates are computed over 100 random formulas.

Figure 10: 4-SAT (

N=100

) : Comparison of diffusion timesteps (

L

) for continuous diffusion with a local BP denoiser. Success rate as a function of clause density

\alpha

on 100 random instances, evaluated with

r=3

$k$	$\alpha_{\mathrm{mask}}$	$\alpha_{\mathrm{diff}}$	$\alpha_{\mbox{\tiny\rm d}}$
3	0.666667	0.736	0.818469
4	0.562500	0.632	0.772280
5	0.474074	0.531	0.701780
6	0.406901	0.511	0.637081
7	0.355474	0.396	0.581775
8	0.315203	0.384	0.534997

Appendix

Table 1: Threshold values for

k

-XORSAT.

Figure 11: 4-NAE-SAT (

N=100

) : Success rate as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions using BP denoiser. Each panel corresponds to a different locality radius for the denoisers

r\in\{2,3,6,9\}

, success rates are computed over 500 random formulas. The error bars are 95% Wilson confidence intervals.

Figure 12: 4-Hypergraph-Bicoloring (

N=100

) : Success rate as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions using BP denoiser. Each panel corresponds to the optimal performance obtained with a locality radius less or equal than

r\in\{2,3,6,9\}

(in this case we observed strong non-monotone behavior in

r

). Success rates are computed over 500 random formulas. The error bars are 95% Wilson confidence intervals.

Figure 13: 4-SAT (

N=100

): learned NN denoiser (solid lines) vs. BP denoiser (dashed lines). Success rate (probability of generating actual solutions) as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions. Each panel corresponds to a different locality radius for the denoisers

r\in\{2,3,6,9\}

. Success rates are computed over 500 random formulas. The vertical line marks the dynamical phase transition

\alpha_{\mbox{\tiny\rm d}}(k=4)\approx 9.38

Figure 14: 4-SAT (

N=300

) : learned NN denoiser (solid lines) vs. BP denoiser (dashed lines). Success rate as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions. Each panel corresponds to a denoiser

r\in\{2,3,6,9\}

, success rates are computed over 500 random formulas. The vertical line marks the dynamic phase transition threshold

\alpha_{\mbox{\tiny\rm d}}\approx 9.38

for

k=4

Figure 15: 4-SAT (

N=900

) : learned NN denoiser (solid lines) vs. BP denoiser (dashed lines). Success rate as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions. Each panel corresponds to a different locality radius for the denoisers

r\in\{2,3\}

, success rates are computed over 500 random formulas. The vertical line marks the dynamic phase transition threshold

\alpha_{s}\approx 9.38

for

k=4

. The error bars are 95% Wilson confidence intervals.

Figure 16: 4-SAT (

N=5000

) : learned NN denoiser (solid lines) vs. BP denoiser (dashed lines). Success rate as a function of clause density

\alpha

for continuous (blue) and discrete (red) diffusions. Each panel corresponds to a different locality radius for the denoisers

r\in\{2,3\}

, success rates are computed over 500 random formulas. The vertical line marks the dynamic phase transition threshold

\alpha_{s}\approx 9.38

for

k=4

. The error bars are 95% Wilson confidence intervals.

Figure 17: 4-XORSAT (

N=100

) : reversed-leaf (red) vs random (blue) decoding ordering. Success rate as a function of clause density

\alpha

obtained using discrete diffusion with learned NN denoiser. Each panel corresponds to a denoiser

r\in\{2,3\}

, success rates are computed over 500 random formulas. The two vertical lines are the theoretical thresholds for random (

\alpha_{\mbox{\tiny\rm mask}}

) and optimal (

\alpha_{\mbox{\tiny\rm d}}

) decoding ordering.

Figure 18:

k

-XORSAT (

n=1000

) : reverse-leaf (red) vs random (blue) decoding ordering. Success rate as a function of clause density

\alpha

for

k\in\{4,\dots,8\}

obtained using discrete diffusion with BP denoiser. The two vertical lines are the theoretical thresholds for random (

\alpha_{\mbox{\tiny\rm mask}}

) and optimal (

\alpha_{\mbox{\tiny\rm d}}

) decoding ordering at every value of

k

Diffusion Sampling

Diffusion sampling studies how to turn a trained diffusion model into high-quality samples efficiently and reliably.

See all 265 papers

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks
Oct 20, 2026Rodrigo Casado Noguerales, Dimitri von Rütte, Bernhard Schölkopf +2Diffusion Models Diffusion-Based Planning
ETH Zurich · Max Planck Institute for Intelligent Systems · ELLIS Institute Tübingen
Simplex Relaxation for Discrete Diffusion
Aug 11, 2026Jinya Sakurai, Patrick Pynadath, Satoshi Hayakawa +4Diffusion Sampling Diffusion Language Models
1NTU Singapore · 2The University of Tokyo · Institute for Advanced Intelligence and Computing (IAIC), A*STAR +2
Score Mismatch and Set-Constrained Sampling in Zero-Shot Conditional Discrete Diffusion
Oct 15, 2026Renxiang Huang, Yuchen Liang, Yingbin Liang +2Diffusion Models Diffusion Sampling
Department of Electrical and Computer Engineering, University of California, Davis, Davis, CA, 95616, USA · Luddy School of Informatics, Computing, and Engineering, Indiana University Indianapolis, Indianapolis, IN, 46202, USA · Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH, 43210, USA

Oct 20, 2026J/K move · Enter open · S save

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks

Rodrigo Casado Noguerales, Dimitri von Rütte, Bernhard Schölkopf, Thomas Hofmann+1

ETH Zurich · Max Planck Institute for Intelligent Systems · ELLIS Institute Tübingen

Diffusion Models Diffusion-Based Planning Masked Diffusion Models

Open paper AskPDF arXiv

Discrete diffusion models iteratively denoise a noisy sequence of categorical data such as text, enabling any-order generation with self-correction and in-filling capabilities. This makes them promising candidates for reasoning, planning, and constrained-generation tasks like coding and math. Yet masked and uniform diffusion erase a token's identity in a single corruption event, so their noisy states cannot explicitly represent partially resolved uncertainty in which several alternatives remain plausible. We close this gap with Binary Discrete Diffusion, a family of continuous-time discrete-diffusion processes whose noisy state is a set of candidate tokens per position, represented as a binary membership vector. Binary diffusion changes candidate sets through additions and removals, allowing information to be lost and recovered gradually while the diffusion state itself represents partial uncertainty. On Sudoku-Extreme, Boxoban, and graph coloring, the symmetric formulation of binary diffusion consistently outperforms strong, well-tuned masked and uniform baselines under matched architectures and controlled training, sampling, and tuning budgets, with its largest gains on the hardest instances, while remaining competitive on language modeling (Text8, TinyStories, OpenWebText). These results support candidate sets as an effective intermediate representation for iterative reasoning and show that the corruption kernel can materially change the computation learned by the reverse model.

Abstract

Diffusion Sampling

Explore similar work

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks

Simplex Relaxation for Discrete Diffusion

Score Mismatch and Set-Constrained Sampling in Zero-Shot Conditional Discrete Diffusion