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

Oct 20, 2026

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

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.

Rodrigo Casado Noguerales, Dimitri von Rütte, Bernhard Schölkopf +2

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

Diffusion Models Diffusion-Based Planning Masked Diffusion Models

Ask PDF

Aug 11, 2026

Simplex Relaxation for Discrete Diffusion

Discrete diffusion models for categorical generation are defined by a corruption kernel, which determines the intermediate state space and the associated reverse prediction problem. Within this family, uniform diffusion has been extensively developed, with recent work connecting its categorical corruption process to continuous representations and dynamics. Motivated by this view, we ask whether uniform discrete diffusion can be augmented with an explicit continuous state while leaving its categorical corruption process unchanged. We introduce Simplax, an exact Dirichlet--categorical augmentation that couples each corrupted categorical state with an auxiliary simplex-valued variable while preserving the uniform diffusion process as its categorical marginal. This augmentation yields a tractable Rao--Blackwellized reverse-bridge objective and a stochastic reverse sampler, while retaining the corrupted categorical state as the denoiser input. Empirically, Simplax improves the generative perplexity--entropy tradeoff on unconditional OpenWebText generation. On Sudoku, a model trained exclusively on

30

-clue puzzles achieves the highest accuracy among the compared methods across all evaluated clue densities, including the minimum uniquely solvable

17

-clue regime, and also achieves the highest validity in unconditional generation.

Jinya Sakurai, Patrick Pynadath, Satoshi Hayakawa +4

1NTU Singapore · 2The University of Tokyo · Institute for Advanced Intelligence and Computing (IAIC), A*STAR +2

Diffusion Sampling Diffusion Language Models Diffusion Models

Ask PDF

Oct 15, 2026

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

Discrete diffusion models have become a powerful framework for modeling complex discrete distributions across a range of applications. While theoretical convergence guarantees depend on consistency between the target and training distributions, such a case rarely holds in practice, making score mismatch a central challenge in discrete diffusion sampling. This is particularly relevant to zero-shot conditional generation, where a model trained on the unconditional distribution is directly reused at inference time to sample from a conditional target distribution. In this paper, we provide the first theoretical analysis for score-mismatched discrete diffusion models and derive a general KL divergence upper bound that clearly identifies the additional bias caused by such a mismatch. Our analysis covers partial-observation constraints, including text infilling, sentence completion, and more general coordinatewise set constraints. Specifically, we analyze the classical Conditional SEDD sampler and show that it can incur a bias term that scales with the dimension, vocabulary size, and compatibility. Based on this analysis, we propose a Randomized Hard Clamping (RHC) sampler for coordinatewise set constraints. We show that the assignment probabilities can be expressed exactly by the unconditional scores with absorbing rate. Finally, numerical and real-data experiments demonstrate the effectiveness of the proposed RHC sampler.

Renxiang Huang, Yuchen Liang, Yingbin Liang +2

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

Diffusion Models Diffusion Sampling Conditional Diffusion Models Conditional Generation Constrained Generative Modeling Score Matching

Ask PDF

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