Split Gibbs Discrete Diffusion Posterior Sampling
Authors: Wenda Chu
Zihui Wu
Yifan Chen
Yang Song
Yisong Yue
Venue: NeurIPS 2025 poster ()
Keywords: discrete diffusion model
posterior sampling
inverse problem
Primary area: probabilistic_methods

Abstract: We study the problem of posterior sampling in discrete-state spaces using discrete diffusion models. While posterior sampling methods for continuous diffusion models have achieved remarkable progress, analogous methods for discrete diffusion models remain challenging. In this work, we introduce a principled plug-and-play discrete diffusion posterior sampling algorithm based on split Gibbs sampling, which we call SGDD. Our algorithm enables reward-guided generation and solving inverse problems in discrete-state spaces. We demonstrate the convergence of SGDD to the target posterior distribution and verify this through controlled experiments on synthetic benchmarks. Our method enjoys state-of-the-art posterior sampling performance on a range of benchmarks for discrete data, including DNA sequence design, discrete image inverse problems, and music infilling, achieving more than 30% improved performance compared to existing baselines.

Split Gibbs Discrete Diffusion Posterior Sampling
Wenda Chu'
Zihui Wu'
Yifan Chen
Yang Song²
Yisong Yue *OpenAl
'California Institute of Technology
New York University
Abstract
We study the problem of posterior sampling in discrete-state spaces using discrete diffussin models. While posterior sampling methods for continuous diffusion mod- els have achieved remarkable progress, analogous methods for discrete diffusion models remain challenging. In this work, we introduce a principled plug-and and and-play discrete diffusion posterior sampling algorithm based on split Gibbs sampling, which we call SGDD. Our algorithm enables seward-guided generation and solv- ing inverse problems in discrete-state spaces. We demonstrate the convergence of SGDD to the target posterior distribution and verify this through controlled experiments on synthetic benchmarks. Our method enjoys state-of-the-art posterior sampling performance on a range of benchmarks for discrete data, including DNA sequence design, discrete image inverse problems, and music infilling, achieving more than 30% improved performance compared to existing baselines.
Introduction
We study the problem of posterior sampling in finite spaces with discrete diffusion models. Given pretrained discrete diffusion model [35, 1, 4, 29] that models the prior distribution p(x), our goal is to sample from the posterior p(x(y) in a plug-and-play fashion, where represents a guiding signal of interest. This setting encompasses both solving inverse problems (e.g., if y is an incomplete measurement of x), and conditional or guided generation (e.g., sampling from p(x) exp (x according a reward function r(-)).
Existing works on diffusion posterior sampling [7, 37, 30, 51] primarily focus on continuous diffusion models operating in the Euclidean space for These methods have achieved remarkable success in applications including natural image restorations [24, 7, 57], medical imaging [20, 42, 6]. and various scientific inverse problems [14, 51, 55J. However, posterior sampling with discrete diffusion models in discrete-state spaces remains a challenging problem, mainly due to not having well-defined gradients of the likelihood function p(y) x). Initial work address this gap for discrete diffusion models relies on approximating value functions (similar to reinforcement learning) for derivative-free sampling [27], which can be difficult tune for good performance. particularly when the guidance y is complicated.
In this paper, we develop rigorous plug-and-play method based on the principle of split Gibbs sampling [47], which we refer to as SGDD. Our method addresses the posterior sampling problem p(xly) by introducing an auxiliary variable along with regularization potential function D(x, 2; to relax the original problem. The relaxed formulation enables efficient sampling via Gibbs sampling, which alternates between likelihood sampling step and prior sampling step using a pretrained discrete diffusion model. As regularization increases, both variables x and z converge to the target posterior distribution. Our method generalizes split Gibbs samplers with &g regularizers any potential functions with certain limiting conditions, making it compatible with discrete diffusion models by carefully designing the potential function. We provide rigorous stationary guarantee on the convergence of SGDD, with error bounds that account for imperfect score function and discretization errors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

We validate SGDD on diverse inverse problems and swward-guiedd generation problems that involve discrete data. We demonstrate that SGDD converges the true posterior distribution on synthetic data, that SGDD solves discrete inverse problems accurately and efficiently on discretized image data and monophonic music data, and that SGDD excels reward- saradddgddedddddee sampling on guided DNA generation. Our method demonstrates strong sampling quality in all experiments. For instance, we achieve a 42% higher median activity in enhancer DNA design, an 8.36 dB improvement of PSNR values in solving the XOR inverse problem MNIST, and over 2x smaller Hellinger distance in music infilling, compared to existing methods.
Preliminaries
2.1 Discrete Diffusion Models
Diffusion models [39, 40, 18, 41, 22, 23] generate data x E X' by reversing predefined forward process. When X' E I is a Euclidean space, the forward process is typically defined to be stochastic differential equation [22]: dx, = (2 where w, is standard Wiener process and {or) is predefined noise schedule. This diffusion process is reversible once the score function s(x,, t) == Vx, log p( σ4) is learned. Starting from XT ~ NN, I). we generate data following the reverse SDE:
dx. = 26 vx, log p(x;; + 22
(1)
Recent works on discrete diffusion models [35, 1, 4, 29] extend score-based generative methods from modeling continuous distributions in Euclidean spaces categorical distributions in discrete-state spaces. Specifically, when the data distribution lies in finite support X' {1...., N). one can evolve a family of categorical distributions Pt over X' following a continuous-time Markov chain over the discrete elements.
Eep: '.
where Po = Pdata and Q NNXN are diffusion matrices with simple stationary distribution. To reverse this continuous-time Markov chain, it suffices to learn the concrete score s(x; t) (x())) (x( &xx, as the reverse process is given by ôspr-1 QiPr-t
with of (xx) Q [wli and Q.
[i.
-xx Q.a0).
(x;) T-t
For sequential data x E XP, there are N states in total. Instead of constructing an exponentially large diffusion matrix, we use sparse matrix Qf" that perturbs tokens independently in each dimension [29].
Example: uniform kernel. An example of such diffusion matrices is
Q = QuQuuuiiorm o, (11 /N -)),
I),
where is predefined noise schedule with on 0 and oT Fmax. This uniform kernel transfers any distribution to uniform distribution as o + xc. Moreover,
Pt exp (f' Po exp(o,C Saloo,,uuitonng uniiform)m po -(6-0 (6-0 (1-e-0t) 11T
Po-
(5)
When x E D is sequence of length D, we have (x Xo) x gd(xxxx)) d(.,.) is the Hamming distance between two sequences, and Br N 1 11-e-my
xo) (1 31) D- x(x) where
2.2 Diffusion Posterior Sampling Methods
Diffusion posterior sampling is class of methods that draw samples from p(xly) oc p(x)p(y|x) using a diffusion model trained on the prior p(x). This technique has been applied two settings with slightly different formulations: solving inverse problems and reward guided generation.
The goal of inverse problems to reconstruct the underlying data Xo from its measurements, which are modeled as y G(x)) n, where G' is the forward model, and n denotes the measurement noise. this case, the likelihood function given by p(y|x Pa Pn G(x)), where Pa denotes the noise distribution.

---

Guidance-based methods [7, 38, 37, 24, 49, 55] perform posterior sampling by adding additional likelihood score term Xx, loy xx)) to the score function in Eq. (1), and modifies the reverse SDE The intractable likelihood {mh I
SGDD Overview
No
TJmax
Annealing
mk 0
Measurement y
z (k)
Inpointing
3
(k)
4
Likelihood step: z
(x x (7.))) (++1) T(x, z z (k);; mik
Ground Truth Xo
Prior step:
Figure 1: An illustration of our method on inpainting discretized MNIST. Our method implements the Split Gibbs sampler, which alternates between likelihood sampling steps and prior sampling steps. Likelihood sampling steps enforce data consistency with regard to measurement y. while prior sampling steps involve denoising uniform noise from (*) by pretrained discrete diffusion model starting from noise level 7)s- Two variables converge a sample from the posterior distribution as the noise level reduces to zero.
On the other hand, reward-guidee guided generation [38, 19, 32] focuses on generating samples that achieve higher rewards according to given reward function r(-). Here, the likelihood is modeled as p(y[x) or exp(3r(x)), where 3 0 a parameter that controls the strength reward weighting.
Existing diffusion posterior sampling methods leverage (continuous) diffusion models as plug- and-play priors and modify Eq. (1) to generate samples from the posterior distribution p(x(y) x p(x)p(y(x)) These methods can be broadly classified into four categories [9, 56].
as: dx,- o xx,, log X₁; o,) Xx, log p(y v22
score term is approximated with various assumptions. However, these methods cannot be directly applied to discrete posterior sampling problems, where logp(y) p(y)))()))))))))())()) is defined only on a finite support and thus does not have such gradient information.
Sequential Monte Carlo (SMC) methods sample batches of particles iteratively from series of distributions, which converge to the posterior distribution the limit. This class of methods [45, 12, 26, 50, 33, 34, 5] exploits the sequential diffusion sampling process sample from the posterior distribution. Similar ideas have been applied in Li et al. [27] for swward-guided generation using discrete diffusion models, which rely approximating soft value function at each iteration.
Variational methods [30, 14] solve inverse problems by approximating the posterior distribution with parameterized distribution do and optimizing its Kullback-Leible (KL) divergence with respect to the posterior. However, how to extend these methods to discrete diffusion models remains largely unexplored.
Variable splitting methods [51, 54. 57, 36, 52] decompose posterior sampling into two simpler alternating steps. A representative of this category is the split Gibbs sampler (see Section 3), where the variable x; split into two random variables that both eventually converge the posterior distribution. These methods are primarily designed for continuous diffusion models with Gaussian kernels, leveraging Langevin dynamics or optimization Euclidean space as subroutines. Murata et al. [31] extends this category to VQ-diffusion models in the discrete latent space using the Gumbel- softmax reparameterization trick. However, this approach is limited to discrete latent spaces with an underlying continuous embedding due to its reliance on softmax dequantization. In this work, we generalize the split Gibbs sampler to posterior sampling in categorical data by further exploiting the unique properties of discrete diffusion models.
3

---

3 Method
3.1 Split Gibbs for plug-and-play posterior sampling
Suppose we observe y from a likelihood function p(y|x) xx] and assume that x satisfies prior distribu- tion pxx). Our goal is sample from the posterior distribution:
p(xly) oc p(yxx)p(x) = exp(-f(x;y) - -xx)),
(6)
log pxx). The challenge in sampling from this distribution arises from the interplay between the prior distribution, modeled by diffusion model, and the likelihood function.
where y) - ((ylp))))) and g(x)
The Split Gibbs sampler (SGS) relaxes this sampling problem by introducing an auxiliary variable z, allowing sampling from augmented distribution:
i xx z: oc exp(-f(z:)) g(x) (()),
where D(x, z; 1)) measures the distance between and z, and r7 0 is parameter that controls the strength of regularization. While prior works [8, 51, 52] consider D(x, 2; |x=2| the potential function can be generalized any continuous function D, such that D(x, z: 11) as n 0 for any x # z. As shown in Appendix A.3, this ensures that both marginal distributions.
2n
(x: n) := π (x, z; 1)d and n (z: = T(x, z: n))xx
converges to the posterior distribution p(xly). The decoupling of the prior and likelihood in Eq. (7) enables split Gibbs sampling, which alternates between two steps:
Likelihood sampling step:
z (k) x(x= = x()), 2; ,;n) oc exp(-f(z:y) - (k), 22n)), ,
(8)
2. Prior sampling step:
T(X z ( x exp(-9(x) - D(x, z (*)
(9)
key feature of split Gibbs sampling that it does not rely on knowing gradients of the guidance term y), which is highly desirable in our setting with discrete data. In this way, split Gibbs is arguably the most natural and simplest framework for developing principled posterior sampling algorithms for discrete diffusion models.
Prior work has studied split Gibbs posterior sampling for continuous diffusion models [8. 51, 52].
These methods specify the regularization potential D(x, 1;) |x-zii which transforms Eq. (9) into a Gaussian denoising problem solvable by diffusion model. A key challenge, which we tackle, developing a performant approach for the discrete diffusion setting that is easy to implement, and enjoys rigorous guarantees (i.e., sampling from the correct posterior distribution).
3.2 Prior Step with Discrete Diffusion Models
Suppose p(x) is discrete-state distribution over D modeled by diffusion process. We consider discrete diffusion model with uniform transition kernel 8. / 11" - I. To connect split Gibbs sampling to discrete diffusion models, we specify the potential function D(x, 2) as:
1 + (N 1) (N - 1)(1-e-1)
D(x, z; n) == d(x, z) log
(10)
where d(x, z) denotes the Hamming distance between x and z. When 77 - 0 the regularization potential D(x, z: 1)) goes to infinity unless d(x, distributions to p(xly). Given Eq. (10), the prior step from Eq. (9) can be written as
0, ensuring the convergence of marginal
n [xx z (k)) 0c (x() (B/(1 B1) ((2(1)
x (++1)
(11)

---

Algorithm Split Gibbs Discrete Diffusion Posterior Sampling (SGDD)
Require: Concrete score model 8p, measurement y, noise schedule } K-1 Initialize X E X for k O....,K' 1 do Likelihood step following Eq. (13): ((4) ~ T(( = x(h), 2; mp))
Prior step following Eq. (11): (k++1) Txx, 2 = 2(m);
end for Return (K)
where 3 = N-1 1 9). On the other hand, the distribution of clean data Xo conditioned on x, is
given by:
p(x0 x4) 0c (xxx))p(xx(2x) x (x(x)) ( (1 (1- P-
(12)
where 8, = - - "1). Thus, sampling from Eq. (11) 1) is equivalent to unconditional generation
from p(x)|x+) when / Bt. i... 1) os Therefore, we can solve the prior sampling problem by simulating partial discrete diffusion sampler starting from oe = 77 and X; (kk).
3.3 Likelihood Sampling Step
With the potential function D(x, z; 7) specified in Section 3.2, at iteration k the likelihood sampling step from Eq. (8) can be written as:
z (k) T(x = x n: x exp (- -f((zy) - d(x, z) log
1 (N 1)e
(13)
(N 1) e-")
Since the unnormalized probability density function of 7 (*) r)) is accessible, can efficiently sample from Eq. (13) using Markov Chain Monte Carlo methods.
3.4 Overall Algorithm
We now summarize the complete SGDD algorithm. Like in Wu et al. [51], our algorithm alternates between likelihood steps and prior steps while employing an annealing schedule {m²). which starts at a large and gradually decays to ÿк - 0. This annealing scheme accelerates the mixing time of the Markov chain, which we further provide some theoretical intuition in Appendix B.I; and ensures the convergence of π (x; and π <2; 7)) to p(xly)
- O. We present the complete pseudocode of our method in Algorithm and further explain the choice of the noise schedule Appendix B.
3.5 Convergence of Split Gibbs Diffusion Posterior Sampling
We provide theoretical guarantees on the convergence of SGDD. For two probability measures in finite X. we consider the Kullback-Leite (KL) divergence and the relative Fisher information (a. k.a. Fisher divergence), respectively, as (where we define J p//r)
([(x)) s(x.) [xx) log f(x,) Σ ((x:) X2,X,EX''
KL(μTT) Ex- [ln (x)]. FlQ(H(TT
f(x.)
Both divergences are nonnegative and equal to zero if and only Ju = v. when Q is irreducible. Fisher information has been widely used to analyze the convergence of sampling algorithms in continuous spaces due to its inherent connection to KL divergence [2, 43, 51]. In the continuous case, quadratic form FI(u][=T Ey V log /r However, it
the Fisher information can be written does not have an analogous form in finite spaces, which poses additional challenges to the analysis of SGDD. To address this challenge, we adopt a generalized definition of Fisher information [3, 17] and analyze the convergence of SGDD to the stationary distribution using a more general technique that encompasses both continuous and discrete settings.
define a distribution 14, over that evolves according to likelihood steps and prior steps alterna- tively. We assume each likelihood step is implemented with the Metropolis- Hastinns algorithm, and that each prior step solved by the Fuler method with an approximated score function. We compare ie to the continuous-timg stationary distribution ne, which alternates between n. and z²
5

---

Theorem 1. Consider running K iterations of SGDD with fixed qj > 0 and an estimated concrete score so(x; t), and suppose that each prior step is solved by an H step Euler method. Let t* with o(t*) Define and st as stationary and non sontstatiy distributions. Over K iterations of SGDD, the average relative Fisher information between μt and ne has
K (++1)((++1) K
1
2KL (KL(Tol)Po) Kt
4Mc
2M
Fl (Te (4)
(14)
cH
+1)-1
average Fisher divergence in the k-th prior step
convergence by O(1/K)
score error
discretization evoor
where
sel-)t) -(-tt)
<E 1, and L, M, are positive constants defined in Appendix A.
We include the proof in Appendix A. Theorem states that the average Fisher divergence of the non-stationary process to the stationary process in all prior steps converges at the rate of O K), up to constant error term. This result extends our theoretical understanding of diffusion posterior sampling by generalizing the analysis [43, 51] on SDEs to general Markov processes using the free-energy-rate wwwee--nnnnnna-rllleeeo Seative-Fisher-iiee existing analyses for continuous diffusion models, our analysis accounts not only for the imperfect score function but also for the discretization error in solving CTMCs as well.
(FIR) inequality [16]. Morcover, compared to
Unlike some previous methods [27, 50] that rely on assumptions of surrogate value functions and an infinite number of particles, SGDD does not rely on such approximations and eventually converges to the posterior distribution with robustness score approximation and discretization error. Consequently, SGDD can be viewed as natural and principled approach for posterior sampling using discrete diffusion models, leading to empirical benefits as we demonstrate Section 4.
Experiments
We conduct experiments to demonstrate the effectiveness of our algorithm on various posterior sampling tasks in discrete-state spaces, including discrete inverse problems and conditional generation guided by a reward function.
4.1 Experimental Setup
We evaluate our method across multiple domains, including synthetic data, DNA sequences, discrete image prior, and monophonic music, as listed in Table 1. We define the likelihood function for all inverse problems p(y[x) xx) exp([)|G(xx) ylloay, while the likelihood functions for reward guiding tasks are p(y x) oc exp(Br(xx).
Pretrained models. For synthetic data, we use closed-form concrete score function. For real datasets, we train a SEDD [29] model with the uniform transition kernel (details in Appendix C).
Baselines. We compare our methods to existing approaches for discrete diffusion posterior sampling: DPS [7], SVDD-PM [27], and SMC [50]. The original version of DPS relies on gradient back- propagation through both the likelihood function and the pretrained diffusion model, making unsuitable for discrete-domain posterior sampling. In our experiments, we consider its discrete analogy by replacing the gradient with a guidance rate matrix. SVDD-PM is originally designed to sample from a reward-guit -arddd distribution p" (x) p(x) exp(3r(x)). but is also adaptable to solving inverse problems. More implementation details are elaborated in Appendix C.2.
SGDD implementation details. We implement method with total of K iterations. In each prior sampling step, we simulate the reverse continuous-tin Markov chain with H 20 steps. Additional details on hyperparameter choices are provided in Appendix C.3.
Table 1: A summary of posterior sampling tasks considered in our experiments.
Domain
Synthetic
DNA enhancers
Images
Monophonic music
Task type
Inverse problem 50
Reward guidance 200
Inverse problem 2 2024
Inverse problem 259
Dimensionality

---

Table 2: Quantitative evaluation of posterior sampling on synthetic dataset for sequence lengths of D 2, 5 and 10. The Hellinger distance and total variation are computed between the empirical distribution 10k samples and the true posterior distribution on the first two dimensions.
D=
D =
D = 10
Hellinger
Hellinger
TV
Hellinger : TV 1
SVDD-PM (M 20)
0.297
0.320
0.413
0.458
0.455
0.503
SVDD-PM (M 100)
0.275
0.292
0.401
0.445
0.448
0.494
SMC DPS
0.238
0.248
0.353
0.391
0.412
0.460
0.182
0.176
0.345
0.383
0.410
0l.453
SGDD
0.149
0.125
0.214
0.222
0.334
0.365
4.2 Controlled Study using Synthetic Data
To evaluate the accuracy of SGDD in posterior sampling. we first conduct case study on synthetic task where the true posterior distribution accessible. Let E X follow a prior distribution p(x), obtained by discretizing Gaussian distribution ((,0 (T)) over an D-dimensional grid. We define a forward model by G(x) [[((x) I where f(x) maps x to R.D.
We draw 10k independent samples with each algorithm and compute the frequency map for the first two dimensions of x. We measure the Hellinger distance and total variation distance between the empirical distribution and the ground truth posterior distribution. As shown in Table 2, our method achieves substantially more accurate posterior sampling compared to baseline methods. We include visualization of the generated samples in Appendix D.3 (Fig. 8) by projecting samples onto the first two dimensions and computing their heatmaps. When the number of dimensions small, e.g.. D 2, all methods approximate the true posterior distribution well. However, as the dimensionality increases, DPS, SMC, and SVDD-PM struggle capture the posterior and tend to degenerate the prior distribution. While SGDD consistently outperforms baseline methods in terms of Hellinger distance and total variation distance, it also shows slight deviation from the posterior distribution as the dimensionality increases.
4.3 Guided DNAS Generation
We evaluate our method for generating regulatory DNA sequences that drive gene expression in specific cell types, which is an important task for cell and gene therapy and commonly studied in the literature [27, 44, 48].
We train a discrete diffusion model [29] on publicly available dataset from Gosai et al. [15] that consists of 700k DNA sequences. The expression driven by each sequence in human cell lines is measured by massively parallel reporter assays (MPRAs). Following Wang et al. [48], we split the dataset into two subsets and train surrogate reward oracles to predict the activity level in the HepG2 cell line. We use the oracle trained on the training set, r(-). guide our diffusion model, and evaluate its performance using the other one trained on the test dataset. The likelihood function is therefore defined as p(y|x) x exp(Br(x))
Evaluation metries. We evaluate the quality of generated samples using the following metrics:
Predicted activity (Pred-Activity). We evaluate the activity level of generated sequences using the oracle trained on the test dataset. This corresponds to the reward function that we aim to optimize.
Binary classification on chromatin accessibility (ATAC-Acc). Following [48], we use binary classifier trained on chromatin accessibility data in the HepG2 cell line. As active enhancers should have accessible chromatin, ATAC-Acc can be used to validate the generated sequences.
bog-likelihodd. We estimate the log- ligelioiddooo of the generated samples using the ELBO of pretrained masked diffusion model [48]. This regulates the generated samples to stay close to the prior distribution of natural DNA sequences.
We include more baseline methods that require additional training for this task, including dis- crete diffusion fine-tuning method, DRAKES [48], classifier guidance (CG) for discrete diffusion models [32], and twisted diffusion sampler (TDS) [50] which uses CG as the proposal function for sequential Monte Carlo sampling. We further include a Feynman- Kac diffusion sampler [33] with MAX potential function well.
Results. We generate 640 DNA samples using different algorithms and compute the median and average Pred-Activity of the generated sequences. As shown in Table 3, method achieves the
7

---

Table 3: Quantitative results for guided DNA (enhancers) sampling. We generate 640 independent samples with different algorithms according to the reward reward-shaped posterior distribution. We report the mean and median of the enhancer's ' activity computed by the surrogate reward.
Pred-Actio Pred-Activity
Pred-Activity (average) 1
ATAC
log-likelihood (average)
(median)
Acc % t
SVDD-PM
5.11
1.08
49.9
-241
SMC
4.15
3.99
39.9
-259
CG
2.90
2.761
-265
TDS
4.64
4.62+1.09
45.3
-257+9
FK-MAX
4.90
4.79
47.1
-243_
DRAKES w/o KL
6.44
6.28
82.5
-281+6
DRAKES w/ KL
5.61
5.24
92.5
-26449
SGDD (3 = 30)
8.82
8.69 11.12
91.7
-246
SGDD (5 = 50)
9.14
8.96-1.17
93.0
-26 -261229
Samples
7
f
9
Nearrnaar
f
4
1
Figure 2: Generating DNA sequences involves trade-ofl's between targeted objectives and consis- tency with the prior distribution. SGDD plotted in blue and darker colors mean higher 3.
Figure Diversified samples when the measurement is sparse. Samples are generated by SGDD when solving an MNIST inpainting task.
highest Pred-Activity (reward values) compared to existing basclines, including 42% higher median reward compared to the previous state-of-the-ar method.
Moreover, SGDD samples from the posterior distribution, p(x) (xp()r(x))/Z, the guidance strength 3 controls the strength of guidance imposed in the sampling algorithm. We instantiate SGDD with 3 ranging from 3 to 100 and calculate the Pred-Activity and Log-likelihood of the generated samples. We plot the distribution of the samples' Pred-Activity with various Fig. In general, using larger 3 results in higher Pred-Activity (reward), the expense of a lower likelihood as the target distribution deviates further from the prior distribution.
4.4 Discrete Image Inverse Problems
Setup. We evaluate on a discretized image domain. Specifically, we convert the MNIST dataset [25] binary strings by discretizing the images, and train discrete diffusion prior on 60k training data. As examples of linear and nonlinear forward models on binary strings, we consider AND and XOR operators. We randomly pick DD pairs of positions (ip:Ip) over (1...., D). and compute:
A [xx, Xip lp=1....., Gxon(x) [x,, + xj, 1p=11.....
(15)
These logical operators are challenging to approximate using surrogate functions to guide sampling.
Evaluation metries. We use 1k binary images from the test set of MNIST and calculate the peak signal-to-noise ratio (PSNR) of the reconstructed image. Furthermore, we train a simple convolutional neural network on MNIST
surrogate and report the classifier accuracy of the generated samples.
Results. As shown in Table 4, SGDD outperforms baseline methods by a large margin in both XOR and AND tasks. We present the samples generated by SGDD for the XOR task in Appendix D.2. The reconstructed samples are visually consistent with the underlying ground truth signal, which explains the high class accuracy of method shown in Table 4.
Sample diversity. Furthermore, we demonstrate that SGDD generates diversified samples when the measurement y is sparse. For example, when digit is masked with large box, shown
8

---

Table 4: Quantitative results for XOR and AND problems on discretized MNIST. We report the
mean and standard deviation of PSNR and class accuracy across 1 generated samples. SGDD demon- strates superior performance both tasks.
XOR
AND
PSNR 1
Accuracy (%) 1
PSNR 1
Accuracy (%) 1
SVDD-PM (M 20)
11.81 22.64
51.4
10.0441.49
33.7
SMC
1..0
27.8
10.25
24.4
DPS
9.04 1121
30.0
8.67 8.67 10.91
24.5
SGDD
20.17 13.47
91.2
17.25 13.82
79.4
Table Quantitative evaluation of infilling monophonic music sequences.
40%
60%
Hellinger
Outliers
Hellinger L
Outliers
SVDD-PM
0.165 12119
0.112
0.529 0.137
0.114
SMC
0..12
0.152
0.552=0.131
0.164
SGDD
0.126+0.099
0.003 00.002
0.244 40.164
0.060+0.13s
in Fig. 3, the measurement lacks sufficient information to fully recover the original digit. In this scenario, SGDD generate samples from multiple plausible modes, including digits 1,4,7 and 9. This highlights the ability of our method to produce diverse samples from the posterior distribution while preserving consistency with the measurement.
Higher dimensional images. To demonstrate the scalability of SGDD, we further evaluate SGDD on a digeessai dataset, FFH 256 [21] Appendix D.I, where we solve the super-resolution task by operating in the discrete latent space of pretrained vector-quantized diffusion model.
4.5 Monophonic Music
We conduct experiments on monophonic songs from the Lakh pianoroll dataset [11]. Following the preprocessing steps in [4], we obtain monophonic musical sequences of length D 256 and vocabulary size N = 129. The ordering of musical notes is scrambled to destroy any ordinal structure. Therefore, the likelihood function for this task is p(y) x)) x exp(-I|((x) y) lo oy). This to norm makes this inverse problem ill ill-posed, in stark contrast to most reward-guide
generation tasks, where the reward functions are much smoother. We evaluate our method on an inpainting task, where the forward model G(-) randomly masks y = 40%, 60% of the notes. As in Campbell et al. [4], we use the Hellinger distance of histograms and the proportion of outlier notes as metrics evaluate our method. We run experiments 100 samples in the test set and report the quantitative results Table 5. SGDD successfully completes monophonic music sequences style more consistent with the given conditions, achieving 2x reduction in Hellinger distance compared to SVDD-PM.
4.6 More Ablation Studies
We conduct more ablation studies
method to investigate how specific design choices may affect its performance. We discuss the effectiveness of using an annealing noise schedule y/ over fixed noise 7/І- 1) Appendix B.1, including empirical discovery and theoretical justification. We include runtime analysis of SGDD in Appendix B.2, showing the tradeoff between sample quality and computing budgets regarding NFEs. Finally, we highlight the value of using an informative discrete diffusion prior in solving inverse problems by comparing SGDD to MCMC methods without a prior (Appendix B.3).
5 Conclusion
We introduce SGDD, a principled discrete diffusion posterior sampling algorithm based on the split Gibbs sampler, extending plug-and-play diffusion methods from Euclidean spaces discrete- state spaces. Our algorithm alternates between prior and likelihood sampling steps with decreasing regularization level Π7- By carefully designing the regularization potential function, we establish a connection between prior sampling steps and discrete diffusion samplers, integrating discrete diffusion models into the split Gibbs sampling framework. We prove the convergence of SGDD to the targeted distribution. We evaluate our method on diverse tasks from various domains, including solving inverse problems and sequence generation guided by reward functions, where it significantly outperforms existing basclines.

---

Acknowledgments
This research supported in part by gifts from OpenAI, Two Sigma, and Cisco. Z.W. is supported by the Amazon Al4Science fellowship. W.C. is supported by the Kortschak Scholars Fellowship.
References
[1] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17999 2021.
[2] Krishnakumar Balasubramaniaan, Sinho Chewi, Murat A. Erdogdu, Adil Salim, and Matthew Zhang. Towards a theory of non-log-concave sampling: First-order stationarity guarantees for langevin monte carlo, 2022. URL httppppe//arrra...ooo////////// 05214.
[3] Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19:289-336, 2006.
[4] Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 35:28266-2822 2022.
[5] Haoxuan Chen, Yinuo Ren, Martin Renqiang Min, Lexing Ying, and Zachary Izzo. Solving in- verse problems via diffusion-based priors: An approximation-fiee ensemble sampling approach, 2025. URL https arxivv org/ h/t///b//25000 03979.
[6] Hyungjin Chung and Jong Chul Ye. Score-based diffusion models for accelerated mri. Medical Image Analysis, page 102479, 2022.
[7] Hyungjin Chung, Jeongsol Kim, Michael Thompson Mccann, Mare Louis Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems. In The Eleventh Inter- national Conference on Learning Representations, 2023. URL forum? Drrrmmidd-DDDDGGATTO.
net/
[8] Florentin Coeurdoux, Nicolas Dobigeon, and Pierre Chainais. Plug-and-play split gibbs sampler: embedding deep generative priors bayesian inference. arXiv preprint arXiv:2304. 134, 2023.
[9] Giannis Daras, Hyungjin Chung, Chich-Hsin Lai, Yuki Mitsufuji, Jong Chul Ye, Peyman Milanfar, Alexandros G. Dimakis, and Mauricio Delbracio. A survey on diffusion models for inverse problems, 2024. URL https:///arat org/ abs /2400 00083.
[10] Persi Diaconis and Laurent Saloff-Coste. Logarithmic sobolev inequalities for finite markov chains. The Annals of Applied Probability, 6(3):695-750, 1996.
[11] Hao-We Wen Dong, Wen-Yt Yi Hsiao, Li-Chia Yang, and Yi-Hsuan Yang. Musegan: Multi-track sequential generative adversarial networks for symbolic music generation and accompaniment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
[12] Zehao Dou and Yang Song. Diffusion posterior sampling for linear inverse problem solving: filtering perspective. In The Twelfth International Conference on Learning Representations, 2024. URL
[13] Patrick Esser, Robin Rombach, and Björn Ommer. Taming transformers for high-resolution image synthesis, 2021. URL https: / http///xxivv... org/ httgg/bs/22012/ 09841.
[14] Berthy T. Feng, Jamie Smith, Michael Rubinstein, Huiwen Chang, Katherine L. Bouman, and William T. Freeman. Score-based diffusion models as principled priors for inverse imaging. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 10520- 10531, October 2023.
[15] Sager J Gosai, Rodrigo I Castro, Natalia Fuentes, John C Butts, Susan Kales, Ramil R Noche, Kousuke Mouri, Pardis Sabeti, Steven K Reilly, and Ryan Tewhey. Machine-quided design of synthetic cell type-specific cis-regulatory elements. bioRxiv, 2023.
10

---

[16] Bastian Hilder, Mark Peletier, Mikola Schlottke, Guido Schneider, and Upanshu Sharma. An fir inequality for markov jump processes on discrete state spaces. 2017.
[17] Bastian Hilder, Mark A. Peletier, Upanshu Sharma, and Oliver Tse. An inequality con- necting entropy distance, fisher information and large deviations. Stochastic Processes and their Applications. 130(5):259-2260 2020. ISSN 0304-4149. doi: https://ooi.rr// 10.1016|jspa.2011.00.0111 URL httpp:://watt www.sseiieeeeeeecc..mm.r ps1//$0804449199006887
[18] Jonathan Ho. Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6840-6851, Curran Associates, Inc., 2020. URL, / www..nnuripc.mm cttpsccrccpp....eeeeeeee paper httpppppprr_eeeeee faaessffllsspppppeeeeeeee / /pppr//2222/fflle pdf.
[19] Yujia Huang, Adishree Ghatare, Yuanzhe Liu, Ziniu Hu, Qinsheng Zhang, Chandramouli S Sastry, Siddharth Gururani, Sageev Oore, and Yisong Yue. Symbolic music generation with non-differentiable rule guided diffusion. arXiv preprint arXiv:2402. 14285, 2024.
[20] Ajil Jalal. Marius Arvinte, Giannis Daras, Eric Price, Alexandros Dimakis, and Jon Tamir. Robust compressed sensing mri with deep generative priors. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14938-14954, Curran Associates, Inc., 2021. URL http:thtttp/:/proeeeeeiiee 728044996.0666117711000446666444
neurips.co. wwwrrps.cc/pppe..... wwtpcppppeeeaeeeeeeeeeeee files wttee/ffeessppaeeeeeeeee /ppper/2222///lle/ Paper. .df.
[21] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture adversarial networks. In Proceedings of the IÉEE/CVF conference on computer vision and pattern recognition, pages 4401-4410, 2019.
for generative
[22] Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-based generative models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https:
https::/openrevieee net/ wtt.://oomm...-KKPPTP0O....
[23] Tero Karras, Miika Aittala, Jaakko Lehtinen, Janne Hellsten. Timo Aila, and Samuli Laine. Analyzing and improving the training dynamics of diffusion models, 2024.
[24] Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song. Denoising diffusion restoration models. In Advances Neural Information Processing Systems, 2022.
[25] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 ((:21)):2782233 2324,, 1998.
[26] Cheuk Kit Lee, Paul Jeha, Jes Frellsen, Pietro Lio, Michael Samuel Albergo, and Francisco Vargas. Debiasing guidance for discrete diffusion with sequential monte carlo. arXiv preprint 2rXiv:2502.06079 2025.
[27] Xiner Li. Yulai Zhao, Chenyu Wang. Gabriele Scalia, Gokcen Eraslan, Surag Nair. Tommaso Biancalani, Shuiwang Ji, Aviv Regev, Sergey Levine, and Masatoshi Uchara. Derivative-free guidance continuous and discrete diffusion models with soft value-based decoding, 2024.
URL https: arxiv. org/ abs//////a /200 08252.
[28] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL https://openrevien wtwpreerrrriiieeeeeefrrrrro wwt.ffrunn
id-Bkg6Ricqy7.
[29] Aaron Lou, Chenlin Meng. and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Forty-first International Conference on Machine Learning, 2024. URL https::/
[30] Morteza Mardani, Jiaming Song, Jan Kautz, and Arash Vahdat. variational perspective on solving inverse problems with diffusion models. arXiv preprint 04350,330 2023.
11

---

[31] Naoki Murata, Chich-Hsin Lai, Yuhta Takida, Toshimitsu Uesaka, Bac Nguyen, Stefano Ermon, and Yuki Mitsufuji. G2d2: Gradient-guided discrete diffusion for image inverse problem solving, 2024. htI.tttp::/arre
ha//bb//244 14710.
[32] Hunter Nisonoff, Junhao Xiong. Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete state-space diffusion and flow models, 2024. URL https:///axxi:: org/ abs/2406. 01572.
[33] Raghay Singhal, Zachary Horvitz, Ryan Techan, Mengye Ren, Zhou Yu, Kathleen McKeown, and Rajesh Ranganath. A general framework for inference-time scaling and steering of diffusion models, 2025. URL https: http///axvvvvv. wwwrxii..oogggeee wtwpv/v.rrraaa////151/1 06848.
[34] Marta Skreta, Tara Akhound-Sadegh, Viktor Ohanesian, Roberto Bondesan, Alán Aspuru- Guzik, Arnaud Doucet, Rob Brekelmans, Alexander Tong, and Kirill Neklyudov. Feynman- kac correctors in diffusion: Annealing, guidance, and product of experts. arXiv preprint (rXiv:2503.02819, 2025.
[35] Jascha
Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256-2265. PMLR, 2015.
[36] Bowen Song. Soo Min Kwon, Zecheng Zhang. Xinyu Hu, Qing Qu, and Liyue Shen. Solving inverse problems with latent diffusion models via hard data consistency. In The Twelfth International Conference on Learning Representations, 2024. URL htttps///ppereviies net/foruum1d=-jhhaRRee id ddw.orrununidjaadRRuuuuu OOdRRQUNN.
[37] Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. "seudoinverse-guidee diffusion models for inverse problems. In International Conference on Learning Representations, 2023. URL https::/
[38] Jiaming Song, Qinsheng Zhang, Hongxu Yin, Morteza Mardani, Ming- Yu Liu, Jan Kautz, Yongxin Chen, and Arash Vahdat. Loss-guided diffusion models for plug-and-play controllable generation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 32483- 32498. PMLR, 23-29 html.
29 Jul 2023. URL https: //tp:///eppo/ggsss.e mlr. wwwpppressvveee wvtpe//v22////2 song23k.
[39] Yang Song and Stefano Ermon. Generative modeling by estimating gradients the data distribution. In Neural Information Processing Systems, 2019. URL https://api. semanticscholar. Drgg/CorpuIDD 196470877
[40] Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances in neural information processing systems, 33:12438-11 -12488, 2020.
[41] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021. URL https::/ h/tp:s:///ppereveee..
[42] Yang Song. Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medi- cal imaging with score-based generative models. In International Conference Learning Representations, 2022. URL
[43] Yu Sun, Zihui Wu, Yifan Chen, Berthy T. Feng, and Katherine L. Bouman. Provable probabilistic imaging using score-based generative priors, 2024. URL attps://arxixs: wtwpiii.or//bbb/31110 10835.
[44] Ibrahim Taskiran, Katina I Spanier, Hannah Dickmänken, Niklas Kempynck, Alexandra Pančfková, Eren Can Ekşi, Gert Hulselmans, Joy N Ismail, Koen Theunis, Roel Vandepoel, et al. cell-tyee-directe design of synthetic enhancers. Nature, 626(7997) 2024.
12

---

[45] Brian L Trippe, Jason Yim. Doug Tischer, Tamara Broderick, David Baker, Regina Barzilay, and Tommi Jaakkola. Diffusion probabilisticc modeling of protein backbones in 3d for the motif-scaffolding problem. arXiv preprint arXiv:2206.041 2022.
[46] Maxime Vono, Nicolas Dobigeon, and Pierre Chainais. Split-and-augmenter gibbs sam- ver-application to large-scale inference problems. IEEE Transactions on Signal Processing, 67(6):1648-1661. March 2019. ISSN 1941-0476. doi: 2011099/9222192299485335 URL
http://dx.co /tt.//xx.oooi..ooooooooooo.oo..d org/ 10. 1109/TSPPPPPPPP 2019. 2894825.
[47] Maxime Vono, Nicolas Dobigeon, and Pierre Chainais. Split-and-augmented gibbs sam- pler-application to large-scale inference problems. IEEE Transactions Signal Processing, 6766)164811661, 2019.
[48] Chenyu Wang, Masatoshi Uehara, Yichun He, Amy Wang, Avantika Lal, Tommi Jaakkola, Sergey Levine, Aviv Regev, Hanchen, and Tommaso Biancalani. Fine-tuning discrete diffusion models via reward optimization with applications to DNA and protein design. In The Thirteenth International Conference on Learning Representations, 2025. URL net/forumiidee id=G328Dixt4W
[49] Yinhuai Wang, Jiwen Yu, and Jian Zhang. Zero-shot image restoration using denoising diffusion null-space model. In The Eleventh International Conference on Learning Representations, 2023. URL
net/ Foromoiddmmiiiiii eQghtNTQ.
[50] Luhuan Wu, Brian L. Trippe, Christian A. Naesseth, David M. Blei, and John P. Cunningham. Practical and asymptotically exact conditional sampling in diffusion models, 2024. URL https://arxix:
org/ abtp///..//..... 17775.
[51] Zihui Wu, Yu Sun, Yifan Chen, Bingliang Zhang, Yisong Yue, and Katherine L Bouman. Principled probabilistic imaging using diffusion models as plug-and-play priors. arXiv preprint arXiv:2405.18788 18782, 2024.
[52] Xingyu Xu and Yuejie Chi. Provably robust score-based diffusion posterior sampling for plug- and-play image reconstruction. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024. URL https:: wwtpiiiwweeeeeeeeeeeeeeeeeeeeeee wwt.:eeetoooooee peee/fooumm/ Siwuummddd-S-aaa.... Y4u1.
[53] Horn-- Tzer Yau. Relative entropy and hydrodynamics of Hanzburg-landart models. Letters in Mathematical Physics, 22(1):63-80) 1991.
[54] Bingliang Zhang, Wenda Chu, Julius Berner, Chenlin Meng, Anima Anandkumar, and Yang Song. Improving diffusion inverse problem solving with decoupled noise annealing, 2024. URL https://arxiv
org/ abs/2407 01521.
[55] Hongkai Zheng, Wenda Chu, Austin Wang, Nikola Kovachki, Ricardo Baptista, and Yisong Yue. Ensemble kalman diffusion guidance: A derivative-free method for inverse problems, 2024.
URL. htttps://aratt org/ hargg/ab//00n 0abb//200..20 20175.
[56] Hongkai Zheng, Wenda Chu, Bingliang Zhang, Zihui Wu, Austin Wang, Berthy Feng, Caifeng Zou, Yu Sun, Nikola Borislavov Kovachki, Zachary E Ross, Katherine Bouman, and Yisong Yue. Inversebench: Benchmarking plug-and sang--ndd-llyy diffuusion models for scientific inverse problems. In Submitted to The Thirteenth International Conference Learning Representations, 2024. URL http://www...eeoooom///d///////. :ot.mmim-i-33PPII under review.
[57] Yuanzhi Zhu, Kai Zhang, Jingyun Liang, Jiezhang Cao, Bihan Wen, Radu Timofte, and Lue Van Gool. Denoising diffusion models for plug-and-play image restoration. In IEEE Conference on Computer Vision and Pattern Recognition Workshops (NTIRE), 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction include the motivation and brief description method. The experimental results highlighted are also accurate.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
imitations of our work are discussed in Appendix E.I.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

We list out the assumptions required for our main theorem in Appendix A, and provide complete proof.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All experimental results of our method are reproducible. All datasets, models, and hyperparameters are stated in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Data are all open- domann and the code is accessible in Supplementary files.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
mublic//uides/CodeSttee sos.oddeessmmsssioooooooiorc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.coo ctspps.ccpuulicc//ee http:/uullcggguddeee guides/ /CodeSubmi ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The details of our experiments are listed in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report the standard deviation experimental results tables.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer:
[Yes]
Justification: We include details of computational resources and runtime analyses in Ap- pendix B.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: pettss//nnett //terr//s.....e/eeeeeeeeee hcc/public/Etiicsuiieeee
Answer: [Yes]
Justification: This research does not include human subjects. All datasets used are safe, open domain data.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: We include discussion potential positive and negative broader impacts in Appendix E.2.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not involve any sensitive data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The creators of any codes, data, models used in the paper properly credited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code for the paper is provided with instructions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We only used LLMs for editing and grammar checks.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //teer/is....eee /cc//ooneereccc///225/////1/ for what should or should be described.
20

---

A Theory
Notations. We consider linear stochastic process whose forward Kolmogorov equation can be written as ē, QT with boundary condition Tt=0 = To. where Te ~ P(2)). For the simplicity of notation, we let Q: to generate reverse contimuus--tim Markov chain, which means Q! s(x;: 7 - xxx Q and time ł flows with the sampling algorithm, which means To is uniform distribution and Wy the data distribution.
For two probability mass functions j and æ,, we discuss their KL divergence,
(L(HI|=) == Exー log 1 (x)
(16)
We define the relative Fisher information between 1 and π as
((x)) (f(x))- - f(x,) f(x, log f(x;) f(xi) f p/T.
(l)(m)))
Σ X;,zER
(17)
Note that when Q is irreducible, the relative Fisher information Flq(ul > 0, and Flo(ul = 0 and only if μ
In continuous state spaces, the relative Fisher information criterion has been used to derive general first-order guarantees for non-log-concaye sampling [2]. This line of analysis has been adapted to provide theoretical insights for posterior sampling methods using diffusion models [43, 51]. The formula in Eq. (17) represents discrete state space analogue of Fisher information. We refer interested readers to [3, 10, 17] for more discussions on this topic and the relation between KI. and Fisher information in the discrete state space. Our analysis in this paper adapts these techniques and provides general first-order guarantees for posterior sampling with discrete diffusion models.
Time interpolation of SGDD. SGDD alternates between likelihood steps and prior steps. Let 1* > 0 such that 0₁+ 1/. We define ()t) the distributions at time / of the stationary process, and (1x] as the distributions of the non-stationary process.
In time intervals T [k(t* + 1)+1, (k+ 1)(* + +)]. The stationary distribution is initialized with * (x) = Th (x). We run prior step /l, with the learned concrete score function for H steps, while क evolves continuous time with the true concrete score
function.
In time intervals T E [k(t* + 1), k(t* + 1) + 1]. we run a Mctropolis-Hasee Hastings sampling algorithm on both π, and [++-
Assumptions. Our analysis relies on the following assumptions:
Concrete score is well estimated:
(e(s)))=(st)
<E< 1.
s(.3))
8
Smoothness of score function in (r144A)--a s(())) x(st)
10 L At.
Strong irreducibiliyy Q.
|.: > 0 for i # j.
(iii)
(iv) Bounded probability ratio: sup, log Mx(x) x.(x]
11x & B.
(v)
The entry-wise absolute of the reverse-time transition matrix is bounded: sup, |||Qulli M.
A.1 Lemmas
Lemma (Data processing inequality of Metropolis Hasting). Running Metropolis Hasting on two distributions тV and [rr does not increase their KL divergence, ie.,
KL( AL(TT(p*--n +1) +1)l|Px()++))) > 11
(18)
Lemma 2 (Free-energy-ratte -unctionaa-relltive rewativ--Fisher-nnfeeeeeeee Fisher-information (FIR) inequality (from Theorem 6.2.3. in [16])). Consider two continuous time Markov chains: θe.T, QITe and θeple Q.n.. Suppose Assumption (iv) holds, then there exists a constant e > O, such that
2 1 Fla. (TellP.) ) + Lg. (TT, Q,Te), (.KL(T)lM)) & -
(19)
c
21

---

where ((Te)) 2 O is the Lagrangian defined as
L sup (Eco(())
(p,
T((xx)) XiiXeeX
Σ
exp((((3)) ((xx))
(20)
Proof Sketch. This lemma follows from Theorem 6.2.3. in Hilder et al. [16]. For completeness, we provide sketch of the proof here.
By a direct calculation of derivatives, we have
(.KL(T))))))) 2, Σ Te (xx) log
(x())
Σ (xxT(()))
log
Te (x:)
Tx(x.) Me(xi)
@epl((xs)
14(x;)
pe [x(x,,
= Σ
Q
|iتا Te (xx)
log
(x;))
Tx(xx;)
(x,)
Me(x))
X
Σ
Ql
|i.il (e(x))
Te(x))
log
(xx:)
Te (x(x))
E
(x))) log Tx(x))
(xx(
Per
(x:)
pe(xs)
ee (x:))
X.
X.
Σx. Qfi:ol and the definition in Eq. (17), we have the equality
Using the fact that
TTe (x,) log (x;)
(x,) Me(xx) Me(xi)
(xx))
Σ Q
[65l Me(x))
= (Tellpe))
X.
Using the relation ट... QUTr. this leads to
@.LL(Te))))) = - FlQ., (Tellee)) - (log Tt 1 (Q: - m
(21)
Mr
einor term
This formula is similar to Lemma in Yau [53].
We define
Lq. Lq (TT,, O(Te) = sup ((o.) Pe) Oi vEC,(X)
?= cP]
sup CeTe - QiTT. Tt Te'(e (e-0Q% - k) vEC,(X)
(22)
denoted as H(
By the variational characterization of the Lagrangian, for any continuous, bounded y
(9, d, - QiT) & f O(m)) H()..
(23)
If we choose log a. it is easy to verify that
the inequality above gives bound to the emro term in Eq. (21). Moreover,
(T,, log Tt = Flq. (m 1/e).
(24)
In fact, when the space X' is continuous, choosing ((x) = log Ii (x) exactly recovers Lemma A.4 in [51]. However, as pointed out in [16], it is necessary to consider a rescaled Alog Ia with X E (0, 1) to derive bound in finite space X. Fortunately, according to Lemma 6.2.2. in [16]. for any &p E Co(X) with 11 < B, there exists positive constant = c(B) e (0, 1), such that
X²
M M((,,)))
H( ())
(25)
Plugging in Alog We in Eq. (23), we have
(Alog Pt
0. Q & Lo (T ((Tee) + Hl > log Tt
(26)
ft
X2
(Ti, H(T,, log "t) pt
(27)
22

---

Combine this with Eq. (21),
a,KL(m lme) (Telu)) L (me,) + - H(ee, log mh)
Me
-- - - Fl (mel14) + X f (Te, C(Ts)
(28)
Finally, choosing = _ (0, 1) recovers the statement of Lemma 2.
Lemma 3. When the learned score function Se satisfies Assumption (i) and (v),
(q, Q114) Mc.
(29)
Proof. By definition,
Lo (Pe: Qu4))= = sup pECo(2t) xxxxee
Σ
Q( p(x,) - (bx
Σ (( (p(xx) x(xx)) (xx)) (x(x))) -
sup ssu (ECo(d) xxxxEXX
(1 Q=Quuu ffror any u)
sup Σ (((x)Q((..) (2),(x)) x
- )
+ Σ (x) Q!
Q [. 25j
(21 = (((x;) ,o(x,))
[
Σ x;
(((x)
sup
Q [ia]] 2ij
E
+
Σ (xx
EijRR
(30)
where the inequality due to swapping sup and summation, and that pt (x)
for i * j.
Consider the function g(2) = - = When u > 0, this function is maximized when - log u.
Using Q Qu
[.a]]
sup
Q Zij - E - = (u 1) log & Iu - 1 1 c.
(31)
for < 1. Combining with Eq. (30), we have
La (pr, Q.1) & e1 & < elI[eelli & e.M.
(32)
Additional Notes on Lemma 3.
With slightly different derivation, assumptions (i) and (v) can potentially be replaced by the following assumption that links directly to the score entropy loss defined in Definition 3.1 of Lou et al. [29].
Alternative assumption.
(i) Score function is well estimated, i.e., the score entropy loss for distributions on the stationary process is bounded:
Ex SE (x;; = E Ex,- NT
Σ K
(0((x;;)))
fw [i-sl [i5l s(xx;t)xx & ESE.
s(xxit)x,
X, Ax:
for any E [0, 1], where K(a) a log Lemma 4. When the learned score function sa satisfies Assumption (i'),
Lg, (Ti, QiTe) ESE.
(33)
23

---

Proof.
Q 5.4
L. (T QuTT))
sup Σ
Te Q
2zg) -
Σ (x
-Q.
[
(2) x
Σ
7x(x,) ل!:.01
s(x;;t) t)
log
sx,;t)
Σ
Te(xx)
Σ !Q
[ Q!6.1))
so (x;;tt
so (x;;t)
X, xx
%1
j+1
(34)
Σ
Te (x. Q(
3i log s(x;tt)
Tee (x()) Σ Xi
E(Q! -Q(b.l)
s0(x;; ())
#x,
Jti
( fullt.s1 800 (xo(xs: Drs, log s(x,it)
Σ
s(x;;)) + so(xi:))
(x;;t)))
K 80(xi;)) Σ
Q. fiwlswll (xx $ <SE.
(35)
s(x;;t)
X xjxx;
where Eq. (34) comes from the previous Lemma 3.
A.2 Proof of Theorem
Proof. Consider discretizing prior step [0, [*] uniformly into H intervals, [hd, (h + 1)6]. for O..... H 1, where 8 = t* /H. H. In the h-th interval,
Cefle Qiopc.
(36)
Applying Lemma on fh and me the h-th interval,
2 (.LL(T))))) < F1 (Tell + Exxisx Can (Te, Q.7e).
(37)
= After integrating both sides by t and rearranging, (for simplicity of notation, we denote k(t* + 1) + the starting time of the k-th prior step)
+
111+-11++
Flo, (pell &
22( + fq. (Mee Prithsse)) de
k((0 +1(0
4 (
2 (KL(prezhollT (L tT
CQi Qixthote)dt.
c J44n
(38)
Taking summation over h,
+1)
(1el(T) & (D - /K//////ooo
+1+++1)++
H m 4
h= Jh+
(39)
Since -o(stts)=s(11))) s(-2)
11:0 c Ls. According to Lemma and 5 1* t²/H,
Tx (b++61)
5 4 S -M Ls)ds = 4M ct
L1*2
- LQq Q +noHtddd &
+
(40)
Tathō
11
2H12
Thus,
((++1))(0-1) JA(141)++1
4M
L1=2
Fle. & Hia
(et
2H
24

---

Finally, taking summation over k = O,.... K 1, and applying Lemma for each likelihood step,
(k+ (++1)(t++1)
(ual(T))Te) & 2KL((Ol|=O)) + 4M (eKt*
LKt#
k( +1)+1
2H
Dividing by Kt both sides,
1
(k+1)(**+3) +1)
2KL(Pal|
4Me
2M Lt*
Flo, (HellT)
(41)
K
+(++11+11
K1*
cH
A.3 Potential function of split Gibbs samplers
As defined in Eq. (7), split Gibbs samplers draws samples from the augmented distribution
π x, z: 17) exp(-f(z:y) g(x) D(x, z)))
The key requirement of split Gibbs samplers is that the potential function D(x, z) satisfies
lim D(x, z; 17) 00, Vx * z. n
(42)
Or more precisely,
exp( - D(x 2;1))
lim --
exxp(-D(xx, 1)) 6x(2).
(43)
Therefore,
lim n (x: lim f plxxp(ylla)epp(-D(xxx exp(- D(p n))
exp(
n 0-
n p-0-
p(x)p(xll))(xx z)d= = =xx)==(())xxxxx
(44)
Also, the similar derivation holds for n 7²(2; 17). This result has also been shown [46]. Combining this with Theorem 1, SGDD is guaranteed to sample from the true posterior distribution when 1J goes to zero.
25

---

B Ablation studies
12-
20
MNIST
15
14
13
P34R
13
13
Anneal
0-0.01
21
0=0.5
g=0.001 000
g=0.1
150 MF1 1020 2033
4003
Roundds
Figure 4: Convergence speed of different noise schedules. We compare our noise annealing scheduler (nx 1/ (orange) fixed noise sched- ules of various noise levels on the MNIST AND task. y-axis the PSNR of variables (k) with respect to the ground truth. Our noise sched- ule converges faster than schedulers with fixed noises.
Figure 5: Sampling quality vs. computing bud- get. The æ-axis indicates the number of function evaluations of the discrete diffusion, while the y-axis shows the PSNR metric. Experiments are done with 10 discretized MNIST samples on XOR and AND tasks.
B.1 Effectiveness of the annealing noise schedule.
We investigate how the choice of noise schedule {mo)-_ affects the performance of SGDD, In our
main experiments, we geometric noise schedule from [29], defined rJs-
Vmin 1/max
k/K 1-k/K We
argue that annealing noise schedule (m)))= that gradually decays Mmin allows SGDD to converge faster and more accurately to the posterior distribution.
To validate this hypothesis, conduct an ablation study on the MNIST AND task. We run our method for K 50 iterations and compare the annealing noise schedule with fixed noise schedules different noise levels, ranging from 10-3 0.5. We then compute the PSNR between x()) and the true underlying signal.
As shown in Fig. 4, running SGDD with the annealing noise schedule achieves the highest PSNR and also the fastest convergence speed. Moreover, when 1) is large, SGDD converges quickly to a poor solution, whereas when 7) is small, converges slowly an accurate solution. This finding aligns with our intuition that SGDD is most accurate with 7) - 0, while sampling with >> regularizes and simplifies the sampling problem.
This trade-off between convergence speed and accuracy results in a non-monotonic relationship between PSNR and fixed noise levels: PSNR first increases and then decreases with Therefore, using an annealing noise schedule helps provide both fast initial convergence and accurate posterior sampling 7/, approaches 0.
Theoretical insights. Since Eq. (44) holds when 7j - 0, a natural question is why we cannot fix small 1 to begin with.
The answer this question is contained in Theorem 1. When fixing small 7,, we also fix small t* as (tt*) = Then the transition matrix Q, (r e [0, will be ill-posed, in the sense that o!!i] is either very large or very close to O. In this case, the relative Fisher information Flq. (ur mT) becomes poor criterion of measuring the divergence between μ4 and π.. To see this, we note that the spectral gap (Q+) has
((2))
min - ReX(Q=) > Ne, X=
(45)
where N |2 if Q that
0 for all i j. By the logarithmic Sobolev inequality [3], we have
minn (
Flg- (M-
KL(H+11TT,)
(46)
26

---

Ignoring the errors in the score function and discretization, the KL divergence converges linearly, i...
KL( mT) ) & exp
min Q. KL(PoolTo). Jo (F)
(47)
When ? is large, S0 min Qf is considerably large, because the probability ratio (x( is being smoothed by the uniform transition kernel, which makes Qf large. However, discussed above, So | dr can be very close to when 7)s is small, which makes the convergence slow.
B.2 Time efficiency.
We run SGDD with different configurations evaluate its performance under different computing budgets. We control the number of iterations, K, and the number of unconditional sampling steps T in each prior sampling step, so the number function evaluations (NFH) of the discrete diffusion model is KT. We evaluate SGDD with NFEs ranging from 100 to 2k. The detailed configuration is specified in Table 6.
We present plot in Fig. 5 showing the tradeoff between sample quality and computing budgets in terms of NFEs. SGDD is able to generate high-quality samples with reasonable budget comparable to unconditional generation. Note that we calculate the NFEs for SVDD and SMC with the number of Monte Carlo samples mc and the number of Euler steps H 1, while some results in our experiments are done with larger me and H for better performance. We report both the number of total NFEs and the number of sequential NFEs that decide the cost of the algorithm when fully parallelized.
Table 6: Configurations of SGDD and baseline methods. For DPS and SVDD-PM. we calculate both the total NFE and the sequential NFE. The numbers are collected from the MNIST XOR task as an example. The runtime amortized on a batch size of 10 samples with one NVIDIA A100 GPU.
Configuration
# Iterations
Prior sampling steps
NFE (total/scqueettial
Runtime (sec/sample)
DPS
100
102400/100
820
SVDD-PM (M 20)
2560/128
SMC (M 20)
5120/256
SGDD-50
25
2
50
SGDD-100
25
4
100
6
SGDD-200
40
5
200
SGDD-400
40
10
400
10
SGDD-1k
50
20
1000
13
SGDD-2k
100
20
2000
20
B.3 Comparison to sampling without prior.
We evaluate the value of discrete diffusion priors in solving discrete inverse problems by comparing method to the Metropolis-Hastimee algorithm without diffusion prior. We pick the AND problem on discretized MNIST as an example, in which we choose 7D random pairs of pixels and compute their AND values measurement y. Fig. 6 shows the reconstructed samples of SGDD and direct MCMC sampling under different levels of measurement sparsity. As demonstrated the figure, the discrete diffusion model complements the missing information when the measurement is sparse (e.g.,
2, 4, 8), underscoring the importance of discrete diffusion priors in SGDD for solving discrete inverse problems.
27

---

y=2
4
SGDO
PSMR-11 5
PMNB-1 17.40
PS 90
PS40-8000
PSMR-600 0
4
PSNR=5.95
ISNR-7.80
PSNR-11.00
PSNR-17.36
PSNR-43.54
Figure 6: Comparison of SGDD and direct sampling without data prior. The PSNR values computed with 10 test samples. SGDD replenishes the missing information when the measurement is sparse.
C Experimental details
C.1 Pretrained Models
learn prior distributions for each dataset using SEDD [29] discrete diffusion models. use the SEDD small architecture with around 90M parameters for all experiments, and the models are trained with A [28] with batch size 32 and a learning rate of 3 10 10-4.
C.2 Baseline Methods
C.2.1 DPS
DPS [7] is designed to solve general inverse problems with pretrained (continuous) diffusion model. performs posterior sampling from pl p(x(y) by modifying the reverse SDE
dx, 2 Vx, log (og + / 20
(48)
20, (V o() Xx logp(y|x;))t 22
(49)
To estimate the intractable guidance term Vx, p(yp(( dt. DPS proposes to approximate it with p(y[x,)= E[x, xx.).. The guidance term is thus approximated
Vx, log ply((() 2 - |G [G(Do(x,, o.)) yy
(50)
20
where D9 is one-step denoiser using the pretrained diffusion model, and the measurement is assumed to be y G(x) + n with n o2)
However, DPS is not directly applicable to inverse problems in discrete-state spaces since propagating gradients through G and Dg Eq. (50) is impossible. Therefore, we consider the counterpart of DPS in discrete spaces. We modify the continuous-time Markov chain of the discrete diffusion model by
dpt = Pr dt
(51)
which
Q (b2) PT- (x-)(x (x-)(x;) PT ( (...) Pr-+(y|x)
(52)
(x-((x,y)) pr-((x,) ply((y)x,)
pr-c(y(x;)
Similar ideas are applied to classifier guidance for discrete diffusion models [32], where the matrix Pr x,) (yix, li, is called guidance rate matrix. We compute R at colummn by enumerating
RV
every neighboring x, and calculating pe(ylx.) for each x;. The discrete version of DPS can be summarized by
px()
dpt Q, R. Pr
(53)
dt
28

---

However, the discrete version of DPS is very time-consuming especially when the vocabulary size is large, for enumerates (NV 1) x number of neighboring when computing R We find it slow for binary MNIST (N 2) and DNA generation tasks (N 4) but unaffordable for monophonic music generation (N 129).
C.2.2 SVDD
SVDD [27] aims to sample from the distribution (²o) ac p(xo) exp(Br(xo)), which is equivalent the regularized MDP problem:
pd (xo) = arg max max Ex - -L((=l/)/
(54)
They calculate the soft value function as
vx(x)) )= = log Ex pxpp
(55)
and propose to sample from the optimal policy
p ((+1) o Pr (x x(+1) exp(3er(x)))
(56)
In time step t, SVDD samples batch of M particles from the unconditional distribution (e(x|xxx+3)) and conduct importance sampling according to (xp())(x)))
Although [27] is initially designed for guided diffusion generation; it also applies to solving inverse problems by carefully choosing reward functions. We consider r(x) = -IG(x) ([(x))yyloo yllo/ay and / 1, so that it samples from the posterior distribution p(xly). As recommended in [27]. we choose 3 oc
(a in their notation) in practice, so the importance sampling reduces to finding the particle with the maximal value in each iteration. We use WVDD-PM. training- free method provided by [27] in our experiments. It approximates the value function by ve(x;) = 7 r(xo(x))). where &o(x;) is an approximation of [xo [xe] In practice, find that approximating Ro by Monte Carlo sampling with a few-step Euler sampler achieves slightly better results. We use 3 Monte Carlo samples to estimate 2e (x²) in experiments.
C.2.3 SMC
Sequential Monte Carlo (SMC) methods evolve multiple particles to approximate a series of distribu- tions, eventually converging to the target distribution. Specifically, in experiments, implement the SMC method to sample from p(x:ly) for = T, 1...,0, O, using the unconditional discrete diffusion sampler p(x,) x the proposal function.
We maintain batch M = 20 particles (xlm)). At time I, we sample x! x!mll ~ p(x, (x(])) by the pretrained discrete diffusion model and estimate the likelihood p(y) (!m)) x. p(xx mm) p(y) (xxo)
by Monte Carlo sampling. We then resample the particles (x(")) according to their weights wf [m]] [
p(y|x!"" [m) //((y)
practice, we find that we have carefully tune hyperparameter 3, where we otherwise the resampling step can easily degenerate to arg max or uniform random sampling.
(m))//())/ppp [m]]
C.3 Hyperparameters
k/K 1-k/K with Mainn 10-4 and Muax 20. We We annealing noise schedule of 77 Mmin 7/max run SGDD for K iterations. In each likelihood sampling step, we run Metropolis-Hasting for T steps, while in each prior sampling step, we run few-step Euler discrete diffusion sampler with H steps. The hyperparameters used for each experiment are listed in Table 7. We also include the dimension of data spaces X' for each experiment in Table 7, where |
N.
29

---

Table 7: Hyperparameters used in each experiment.
Synthetic
DNA design
MNIST XOR
MNIST AND
Music infilling
Metropolis- Hastings T
10
200
2000
5000
5000
SGDD iterations K
10
50
50
100
100
Fuler sampler H
20
20
20
20
20
Sequence length D)
2/5/10
200
1024
1024
256
Vocab size N
50
129
D Additional Experimental Results
D.1 Solving image restoration problems in discrete latent space.
To demonstrate the performance of SGDD on higher-dimensional datasets, we conduct an additional experiment on FFHQ 256 with vector-quantized diffusion model. Specifically, use pretrained VQVAE model from [13] and train a discrete diffusion model the discrete latent space. We test algorithm the super-resolle super-resolution task (x4) using 100 images from the test dataset. While existing methods fail to solve this high-dimensional task with a complicated forward model that includes latent space decoder (the cost of DPS is unaffordable), our method is able to reconstruct the underlying images with high PSNR values.
While the latent codes of VQVAE lie in discrete-state space, they are embedded in an underlying Euclidean space, which makes this problem different from solving inverse problems in categorical distributions without ordinal information. A potential way to speed up and boost the performance of SGDD solving image restoration problems with VQ-diffusion is to replace the Metropolis- Hastings in discrete latent codes with Langevin dynamics in the continuous embedding space of latent codes. We leave the exploration this idea as future direction.
Table 8: Quantitative results for the super- resolution (x4) task on FFHQ 256 dataset.
Table 9: Class-conditioned generation MNIST dataset.
PSNR 1
LPIPS 1
MSID
Accuracy
SVDD-PM
12.08 25.85 10.39
0.594
SMC
39.13
45.0
SGDD
0.288 200039
SGDD
14.59
98.5
D.2 More results for inverse problems discretized image.
Qualitative results. Here we present the visualization of the reconstructed samples of MNIST from their XOR measurements.
Ground Truth
Ours
SVDD
O
O
O
O
7
8
/ /
1
/
f
1
2
2
2
2.
2
2
2
2
2
3
/
3
3
$
3
3
3
3
5
4 _
4
4
9
4
4
4
4
4
4
4
4
5
5
5
5
5
6
4
3
6
6
&
6
6
6
6
2
5
7
7
7
7
7 7
7
?
/
4
7
&
8
8
S
&
8 8
6
8
2
9
9
9
7
9
9
7
9
9
7
8
Figure 7: Sampling results of the XOR task on the discretized MNIST dataset. SGDD faithfully recovers the structural information of the ground truth signal.
30

---

Approximate distribution divergence on class-conditioned generation. Since classifier on MNIST data can also be viewed forward model, SGDD can also be directly applied to sample digit-conditioned samples. Moreover, while the posterior distribution for general inverse problem inaccessible, we can approximate the posterior distribution of class-conditioned generation by digit-specific prior distribution.
Specifically, define the posterior distribution as proportional to p(x)p((3(((((x), y)), where é is the cross-entropy loss between the predicted class probability and target class label y. We let the dataset as the approximated true posterior distribution. We train another classifier with a different random seed evaluate the generated samples. To measure the divergence of the generated samples from the posterior distribution, we extract the features of MNIST before the last layer of CNN classification network, and compute the multi-scale intrinsic distance (MSID) score.
y 0 to guide diffusion models to generate digits and extract all digits
Experimental results in Table show that SGDD effectively samples from the true posterior distribu- tion, achieves low MSID score and high class accuracy of 98.5%.
D.3 More experimental results on the synthetic dataset
DPS
Hellnger 0 182
Hellnger
Mellagen:033
Prior
SVDD-PM (M 100)
helinggr
Posterior
Ours
Figure 8: Empirical distributions of various sampling algorithms on the synthetic dataset. Heatmaps drawn with 10k samples for sequence lengths of D 5 and 10. We project the sequences to the first two dimensions for case of visualization.
31

---

E Discussions
E.1
Limitations and future directions
Our method is built on discrete diffusion models with a uniform transition matrix. It is unclear how our method can be applied to other types of discrete diffusion models, such as masked diffusion models. Moreover, our method calls the forward model (for inverse problems) or the reward function multiple times while running computational overhead when the forward model or reward function is complicated. We leave these issues as possible future extensions.
Serropoli--Hasting in likelihood steps, which potentially increases the
E.2 Boarder Impacts
We anticipate that SGDD offers a clean and principled framework for posterior sampling using discrete diffusion models. SGDD tackles these problems by leveraging discrete diffusion model as a general denoiser in the finite space, which models the prior distribution with rich data. However, we note that it could be the case that SGDD will generate biased samples, if the discrete diffusion model is itself trained on biased data. Therefore, caution should be exercised when using SGDD in certain sensitive scenarios.
32


Reviews:
[{"review_id": "XS0pQ7SdeD", "reviewer": "Reviewer_am6s", "summary": "This paper proposed Split Gibbs Discrete Diffusion (SGDD) for posterior sampling in discrete-state spaces, which generalizes the methodology proposed in [1,2,3] that applies continuous diffusion models to posterior sampling problems in continuous-state spaces to discrete distributions. Similar to the procedure developed in [1,2,3], the method consists of two alternative steps. One step is the likelihood sampling step, which is performed via standard Markov Chain Monte Carlo (MCMC) method. The other step is the prior sampling step, which is performed by running a discrete diffusion model. Both theoretical analysis of the proposed algorithm and empirical experiments on a wide range of tasks like DNA design, discrete image inverse problems and music infilling are included to justify the effectiveness of the proposed method.", "questions": "Regarding the theoretical part presented in the manuscript, would it be possible for the authors to comment on the relation between the relative Fisher information FI defined here with the score entropy loss proposed in [21]? It seems to the reviewer that the two forms are akin and highly related. Instead of adopting the stronger assumption on the error between the true score function and the learnt score function with respect to the $l_{\\infty}$ norm, the reviewer thinks that it is probably better to assume an upper bound on the training loss directly, just as what has been done in [13]. Moreover, it seems that the most crucial part in the theoretical results derived here is essentially bounding the KL divergence between two continuous-time markov chains (CTMCs) $\\frac{\\partial}{\\partial t}\\mu_t = Q_t \\mu_t$ and $\\frac{\\partial}{\\partial t}\\widehat{\\mu}_t = \\widehat{Q}_t \\widehat{\\mu}_t$ via the discrepancy between $Q_t$ and $\\widehat{Q}_t$, which highly relates to the Girsanov Theorem for CTMCs (See for instance Theorem III.5.34 in the book [11] or Theorem 3.3 in [13] for the case of discrete diffusion models). Hence, the authors might consider citing these related work and briefly comment on the relation between all different derivations. \n\nIn addition, to the best of the reviewer's knowledge, recent work on solving inverse problems via continuous diffusion models have also adopted advanced solvers like [19] to speed up the inference process. Would it be possible for the authors to comment on whether it would be possible for SGDD to be accelerated via more efficient inference methods (for discrete diffusion models) like distillation [22] or high-order solvers [16]?", "limitations": "The reviewer is satisfied with the limitations that the authors briefly discussed at the end of the manuscript. For instance, the authors mentioned that currently the methodology can only be used for discrete diffusion models with uniform transition matrix. Hence, one of the future directions is to investigate whether the methodology can be generalized to other forms of discrete diffusion models like the masked discrete diffusion model with absorbing transition matrix. However, this is indeed an important issue as masked discrete diffusion models (akin to autoregressive models) are more widely adopted nowadays in other tasks. \n\nOverall, the reviewer acknowledges that the authors address an important problem and offer meaningful contributions. However, the manuscript’s quality (presentation, literature review, experiments and theoretical analysis) probably requires further improvement before being considered for publication at a top-tier machine learning venue.\n\nReferences:\n\n[1] Wu, Z., Sun, Y., Chen, Y., Zhang, B., Yue, Y., & Bouman, K. (2024). Principled probabilistic imaging using diffusion models as plug-and-play priors. Advances in Neural Information Processing Systems (NeurIPS), 37, 118389-118427.\n\n[2] Xu, X., & Chi, Y. (2024). Provably robust score-based diffusion posterior sampling for plug-and-play image reconstruction. Advances in Neural Information Processing Systems (NeurIPS), 37.\n\n[3] Coeurdoux, F., Dobigeon, N., & Chainais, P. (2024). Plug-and-play split Gibbs sampler: embedding deep generative priors in Bayesian inference. IEEE Transactions on Image Processing.\n\n[4] Singhal, R., Horvitz, Z., Teehan, R., Ren, M., Yu, Z., McKeown, K., & Ranganath, R. (2025). A general framework for inference-time scaling and steering of diffusion models. arXiv preprint arXiv:2501.06848.\n\n[5] Chen, H., Ren, Y., Min, M. R., Ying, L., & Izzo, Z. (2025). Solving inverse problems via diffusion-based priors: An approximation-free ensemble sampling approach. arXiv preprint arXiv:2506.03979.\n\n[6] Skreta, M., Akhound-Sadegh, T., Ohanesian, V., Bondesan, R., Aspuru-Guzik, A., Doucet, A., ... & Neklyudov, K. (2025). Feynman-kac correctors in diffusion: Annealing, guidance, and product of experts. arXiv preprint arXiv:2503.02819.\n\n[7] Trippe, B. L., Yim, J., Tischer, D., Baker, D., Broderick, T., Barzilay, R., & Jaakkola, T. (2022). Diffusion probabilistic modeling of protein backbones in 3d for the motif-scaffolding problem. In The Eleventh International Conference on Learning Representations (ICLR), 2023.\n\n[8] Kim, S., M. Kim, and D. Park (2025). Test-time alignment of diffusion models without reward over-optimization. In The Thirteenth International Conference on Learning Representations (ICLR), 2025.\n\n[9] Yoon, T., Min, Y., Yeo, K., & Sung, M. (2025). $\\Psi $-Sampler: Initial Particle Sampling for SMC-Based Inference-Time Reward Alignment in Score Models. arXiv preprint arXiv:2506.01320.\n\n[10] Uehara, M., Zhao, Y., Wang, C., Li, X., Regev, A., Levine, S., & Biancalani, T. (2025). Inference-Time Alignment in Diffusion Models with Reward-Guided Generation: Tutorial and Review. arXiv preprint arXiv:2501.09685.\n\n[11] Jacod, J., & Shiryaev, A. (2013). Limit theorems for stochastic processes (Vol. 288). Springer Science & Business Media.\n\n[12] Chen, H., & Ying, L. (2024). Convergence analysis of discrete diffusion model: Exact implementation through uniformization. arXiv preprint arXiv:2402.08095.\n\n[13] Ren, Y., Chen, H., Rotskoff, G. M., and Ying, L. How discrete and continuous diffusion meet: Comprehensive analysis of discrete diffusion models via a stochastic integral framework. In The Thirteenth International Conference on Learning Representations (ICLR), 2025\n\n[14] Zhang, Z., Chen, Z., & Gu, Q. (2024). Convergence of score-based discrete diffusion models: A discrete-time analysis. In The Thirteenth International Conference on Learning Representations (ICLR), 2025\n\n[15] Liang, Y., Huang, R., Lai, L., Shroff, N., & Liang, Y. (2025). Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models. arXiv preprint arXiv:2506.02318.\n\n[16] Ren, Y., Chen, H., Zhu, Y., Guo, W., Chen, Y., Rotskoff, G. M., Tao, M., and Ying, L. Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms. arXiv preprint arXiv:2502.00234, 2025a\n\n[17] Murata, N., Lai, C. H., Takida, Y., Uesaka, T., Nguyen, B., Ermon, S., & Mitsufuji, Y. (2024). G2D2: Gradient-guided Discrete Diffusion for image inverse problem solving. arXiv preprint arXiv:2410.14710.\n\n[18] Karras, T., Laine, S., & Aila, T. (2019). A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 4401-4410).\n\n[19] Deng, J., Dong, W., Socher, R., Li, L. J., Li, K., & Fei-Fei, L. (2009, June). Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 248-255).\n\n[20] Karras, T., Aittala, M., Aila, T., & Laine, S. (2022). Elucidating the design space of diffusion-based generative models. Advances in Neural Information Processing Systems (NeurIPS), 35, 26565-26577.\n\n[21] Lou, A., Meng, C., & Ermon, S. (2023). Discrete diffusion modeling by estimating the ratios of the data distribution. International Conference on Machine Learning (ICML), PMLR, 2024.\n\n[22] Zhu, Y., Wang, X., Lathuilière, S., & Kalogeiton, V. (2025). Di $\\mathtt {[M]} $ O: Distilling Masked Diffusion Models into One-step Generator. arXiv preprint arXiv:2503.15457.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Pros: This paper studies an important problem (posterior sampling) for the setting of discrete diffusion models, which can be potentially generalized to other problems like inference-time scaling or inference-time alignment. Both theoretical analysis and multiple experiments (along with a wide range of baseline methods) are provided to justify how effective the proposed method is. Moreover, the authors included Python code for the reviewers to test on. \n\nCons: One of the concerns that the reviewer has is that a few work seem to be missing in the literature review. For instance, for diffusion posterior sampling methods based on the sequential monte carlo (SMC) approach, a lot of recent and concurrent work like [4,5,6,7,8,9,10] probably need to be cited and discussed briefly (Though some of them might have focused on different problem settings like inference-time scaling). Similar issues also exist for other classes of work like guidance-based diffusion posterior sampling and theoretical analysis of discrete diffusion models. Hence, the authors are encouraged to perform a more thorough review of related methods developed in these subfields. \n\nFurthermore, for the theoretical analysis part, the reviewer thinks the assumptions given in Appendix A might be a bit too strong, as they essentially assume that the score function can be ideally learnt with respect to the $l_{\\infty}$ norm. Compared to other existing work on the theoretical analysis of discrete diffusion models like [12,13,14,15,16], the assumptions might be too strong. The reviewer will elaborate on such issue in the \"Questions\" section below. \n\nMoreover, for imaging inverse problems considered in this manuscript, the authors only tested on the MNIST dataset. In contrast, related work like [1,2,17] have tested on large-scale image datasets like FFHQ [18] and ImageNet [19]. The authors are encouraged to test the proposed methodology on these large-scale datasets to justify the effectiveness of the proposed method.  \n\nAdditionally, several issues and typos also exist regarding the presentation of this paper. For instance, the term $dt$ is missing for almost all integrals of the relative Fisher information appearing in the manuscript (Examples include line 181-182, line 567-570). Also, definition of $\\mu_t$ and $\\pi_t$ included in line 174-177 seems to be a bit ambiguous. The authors may consider including a similar picture like Figure 3 in [1] to better illustrate the relation between these two processes (or maybe simply referring to Figure 3 in [1]).", "was_revised": true, "final_justification": "After reviewing the authors' rebuttal, the reviewer is satisfied with nearly all of their responses, which range from literature review, theoretical analysis and large-scale experiments. However, the reviewer still has a few concerns for the methodology and theoretical analysis presented in the paper. \n\nFor the methodology, the reviewer thinks that its novelty is a bit limited as it seems to be a simple generalization of existing work [1,2] (in the References above) from the continuous domain to the discrete domain. For the theoretical analysis, the reviewer finds it to be a bit limited, as it assume a fixed eta parameter,  which is not the case in practical applications.\n\nBased on the two points as well as all question raised in the review above, the reviewer is recommending \"Borderline Reject\" by raising the score from 2 to 3.", "rebuttal": "> 1. More comprehensive literature review of related methods in SMC and inference-time scaling.\n\nWe thank the reviewer for helping us improve the related work section. The reviewer mentioned several papers [4-10] that apply SMC methods to the inference-time sampling/scaling of diffusion models. While we implement SVDD [23] and SMC/TDS [24] as two canonical baselines from the class of SMC algorithms, we will cite and discuss all these recent advancements in the paragraph of Sequential Monte Carlo in Section 2.2. Specifically, SMC/TDS [24] can be viewed as a special case of the general FK diffusion sampling framework [4], with the potential function $G\\_t$ defined as the difference of value function between two sampling steps, and the proposal function defined as diffusion sampling (vanilla/with classifier guidance).\nTo provide a more complete evaluation of SMC-based methods, we further include a FK diffusion sampler [4] with MAX potential function (i.e. the best value along the sampling history), which is found to be slightly more effective in [4]. We use $M=20$ particles for all SMC-based experiments. As we see in the results below, while FK-MAX is slightly better than TDS, our SGDD approach performs significantly better than both SMC-based methods.\n\n| DNA | Pred-Activity (median) | ATAC Acc | Log-likelihood | \n| --  | --| -- | -- |\n| TDS [24] | 4.64 | 45.3% | -257|\n| FK-MAX [4] | 4.90 | 47.1% | -243 |\n| SGDD | 9.14 | 93.0% | -261|\n\n| MNIST-XOR | PSNR | Accuracy |\n| -- | -- | -- |\n| SMC | 10.05 | 27.8% |\n| FK-MAX [4] | 11.20 | 34.7% |\n| SGDD | 20.17 | 91.2% | \n\n> 2. Justifications on our theoretical results. \n\nWe appreciate the constructive feedback on our theoretical results. We will make sure to cite the references on the recent theoretical advancement of discrete diffusion models[12-16] in the revised version. Motivated by the reviewer's comment, we improved our assumption by substituting assumptions (i) and (v) with a direct assumption on the score entropy. Specifically, we assume that\n- Score function is well estimated (i.e., the score entropy loss for any distribution is bounded): for any path of distributions $(p\\_t)\\_{t\\in [0,1]}$, it holds that $$\\mathbb{E}\\_{\\mathbf x\\_i\\sim p\\_t} \\mathsf{SE}\\_{\\mathbf Q\\_t^{\\mathsf{fw}}}(\\mathbf x\\_i; \\theta,t) := \\mathbb E\\_{\\mathbf x\\_i\\sim p\\_t} \\left[\\sum\\_{\\mathbf x\\_j\\neq \\mathbf x\\_i} K\\left(\\frac{s\\_\\theta(\\mathbf{x}\\_i,t)\\_{\\mathbf{x}\\_j}}{s(\\mathbf{x}\\_i,t)\\_{\\mathbf x\\_j}}\\right) \\mathbf Q\\_t^{\\mathsf{fw}\\ [i,j]}s(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}\\right] \\leq \\epsilon,$$where $K(a) := a - 1 - \\log a$.\n\nNote that here $p\\_t$ is arbitrary and may be different from the path on which the DM was trained on. This is in fact expected and highlights the difference between analyzing the generative process of discrete DMs versus analyzing the process of using discrete DMs for solving inverse problems. The ideal process in the generative process of discrete DMs is the same as the process for training (only time going in different directions). In contrast, when using discrete DMs as priors for solving inverse problems, they conduct inference on arbitrary distributions that may be different from the training distributions, which is a generalization gap that requires stronger condition on the DMs for convergence. In fact, the existing works on SMC assume exact score in the posterior sampling task [10,24].\n\nGiven this assumption, we can improve Lemma 3 by directly bounding the Lagrangian term with the score entropy loss. Specifically, we have from Lemma 3 in Appendix A.1 that\n$$\n\\mathcal{L}\\_{\\mathbf{Q}\\_t}(\\mu\\_t, \\tilde{\\mathbf{Q}}\\_t \\mu\\_t) = \\sup\\_{\\varphi\\in \\mathcal{C}\\_b(\\mathcal{X})}\\sum\\_{\\mathbf{x}\\_i\\neq \\mathbf{x}\\_j} \\left[\\mu\\_t(\\mathbf{x}\\_i) \\mathbf{Q}\\_t^{[j,i]} \\left(-\\frac{\\tilde{\\mathbf{Q}}\\_t^{[j,i]}}{\\mathbf{Q}\\_t^{[j,i]}} z\\_{ij} - e^{-z\\_{ij}}\\right) \\right] + \\sum\\_{\\mathbf{x}\\_i} \\mu\\_t(\\mathbf{x}\\_i) (\\tilde{\\mathbf{Q}}\\_t^{[i,i]}-\\mathbf{Q}\\_t^{[i,i]})\n$$\nwhere we use the fact that $\\mathbf 1^T\\tilde{\\mathbf{Q}}\\_t \\mathbf{u} = 0$ for any $\\mathbf{u}$ and $z\\_{ij} := \\varphi(\\mathbf{x}\\_i) - \\varphi(\\mathbf{x}\\_j)$. Consider the function $g(z) = -uz - e^{-z}$. When $u \\geq 0$, this function is maximized at $z = -\\log u$. So, $-uz - e^{-z} \\leq u\\log u - u \\leq u\\log u$. Setting $u = \\tilde{\\mathbf{Q}}\\_t^{[j,i]}/\\mathbf{Q}\\_t^{[j,i]} = \\frac{s\\_\\theta(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}}{s(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}}$, we have that\n$$\n\\mathcal{L}\\_{\\mathbf{Q}\\_t} (\\mu\\_t, \\tilde{\\mathbf{Q}}\\_t\\mu\\_t) \\leq \\sum\\_{\\mathbf{x}\\_i \\neq \\mathbf{x}\\_j} \\left[\\mu\\_t(\\mathbf{x}\\_i) \\mathbf{Q}\\_t^{[j,i]} \\frac{s\\_\\theta(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}}{s(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}} \\log \\frac{s\\_\\theta(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}}{s(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}}\\right] - \\sum\\_{\\mathbf{x}\\_i} \\mu\\_t(\\mathbf{x}\\_i) \\sum\\_{j\\neq i} (\\tilde{\\mathbf{Q}}\\_t^{[j,i]} - \\mathbf{Q}\\_t^{[j,i]}) $$\n$$= \\mathbb{E}\\_{\\mathbf{x}\\_i\\sim \\mu\\_t} \\sum\\_{\\mathbf{x}\\_j\\neq \\mathbf{x}\\_i} \\left[ K\\left(\\frac{s(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}}{s\\_\\theta(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j}} \\right) \\mathbf{Q}\\_t^{\\mathsf{fw}\\ [i,j]} s\\_\\theta(\\mathbf{x}\\_i, t)\\_{\\mathbf{x}\\_j} \\right].\n$$\nNote that the last line is the SE of $s$ with respect to $s\\_\\theta$. Therefore, by swapping $\\mu\\_t$ with $\\pi\\_t$ and $\\mathbf{Q}\\_t$ with $\\tilde{\\mathbf{Q}}\\_t$, we have\n$$\n\\mathcal{L}\\_{\\tilde{\\mathbf{Q}}\\_t} (\\pi\\_t, \\mathbf{Q}\\_t\\pi\\_t) \\leq \\mathbb{E}\\_{\\mathbf{x}\\_i\\sim \\pi\\_t} \\mathsf{SE}\\_{\\mathbf{Q}\\_t^{\\mathsf{fw}}}(\\mathbf{x}\\_i; \\theta,t) \\leq \\epsilon.\n$$ Therefore, we can obtain an new version of Theorem 1 that incorporates the SE loss by swapping $\\mu\\_t$ and $\\pi\\_t$. We will update the theoretical part accordingly.\n\nRegarding the question on the similarity between FI and score entropy, both of them are built off of Bregman divergence. However, we would like to emphasize that they have different goals: the relative FI in our context is a convergence metric that measures the discrepance between intermediate distributions $\\mu\\_t$ and $\\pi\\_t$, while the SE objective measures the difference between the discrete score function and the target score function.\n\n> 3. Limited imaging inverse problems.\n\nWe only included binary MNIST data with binary string operations as an example of imaging inverse problem, because the primary goal of this paper is to design diffusion posterior sampling methods for categorical data distributions, while images are inherently continuous and are not the main focus of this paper. \nTo demonstrate the scalability of SGDD, we conduct an additional experiment on FFHQ 256 with a vector quantized diffusion model. Specifically, we use a pretrained VQVAE model from [25] and train a discrete diffusion model in the discrete latent space. We test our algorithm on super resolution task (x4). While SVDD fails to solve this high-dimensional task with a complicated forward model that includes a latent space decoder, SGDD is able to reconstruct the underlying images with metrics comparable to the results of the algorithms using continuous diffusion models. \n\n| Super-resolution (x4)| PSNR ($\\uparrow$)| LPIPS ($\\downarrow$)|\n| --- | --- | --- |\n| SGDD|  $26.13\\_{\\pm 1.69}$ | $0.278\\_{\\pm 0.033}$ |\n| SVDD   | $12.08\\_{\\pm 0.39}$ | $0.594\\_{\\pm 0.061}$ |\n\n> 4. Typos and ambiguities in notations.\n\nThank the reviewer for pointing out! We will correct the typos and add an illustration of $\\pi\\_t$ and $\\mu\\_t$ in the final version.\n\n> 5. Relation with the Girsanov's Theorem for CTMCs.\n\nWe thank the reviewers for providing the references, which we will cite in the revised manuscript. Prompted by the reviewer's suggestion, we verified that invoking the Girsanov's Theorem will lead to the same result. Specifically, using the chain rule for relative entropy and Girsanov's Theorem leads to the following:\n\n$$\n\\mathsf{KL}(\\mu\\_T||\\pi\\_T) - \\mathsf{KL}(\\mu\\_0||\\pi\\_0) = \\int\\_0^T \\sum\\_{\\mathbf{x}\\_i\\neq \\mathbf{x}\\_j \\in \\mathcal{X}} K\\left(\\frac{\\mathbf{Q}\\_t^{[j,i]}}{\\tilde{\\mathbf{Q}}\\_t^{[j,i]}}\\right)\\tilde{\\mathbf{Q}}\\_t^{[j,i]}\\mu\\_t(\\mathbf{x}\\_i)\\mathrm{d}t - \\int\\_0^T \\sum\\_{\\mathbf{x}\\_i\\neq \\mathbf{x}\\_j \\in \\mathcal{X}} K\\left(\\frac{\\mathbf{Q}\\_t^{[i,j]}\\frac{\\pi\\_t(\\mathbf{x}\\_j)}{\\pi\\_t(\\mathbf{x}\\_i)}}{\\tilde{\\mathbf{Q}}\\_t^{[i,j]}\\frac{\\mu\\_t(\\mathbf{x}\\_j)}{\\mu\\_t(\\mathbf{x}\\_i)}}\\right)\\tilde{\\mathbf{Q}}\\_t^{[i,j]}\\mu\\_t(\\mathbf{x}\\_j)\\mathrm{d}t. $$\n$$= - \\int\\_0^T \\mathsf{FI}\\_{\\mathbf{Q}\\_t}(\\mu\\_t||\\pi\\_t)\\mathrm{d}t  - \\int\\_0^T \\sum\\_{\\mathbf{x}\\_i, \\mathbf{x}\\_j \\in \\mathcal{X}} \\log \\left(\\frac{\\mu\\_t(\\mathbf{x}\\_i)}{\\pi\\_t(\\mathbf{x}\\_i)}\\right)\\left(\\mathbf{Q}\\_t^{[i,j]} - \\tilde{\\mathbf{Q}}\\_t^{[i,j]}\\right)\\mu\\_t(\\mathbf{x}\\_j)\\mathrm{d}t.$$\n\nNote that taking the time derivative of both sides exactly leads to (21) in Lemma 2. Our calculation is given by a direct calculation of the time derivative of KL divergence along the two Markov processes. We will comment on the derivation using the Girsanov's theorem in the revised manuscript.\n\n> 6. Applying advanced solvers to accelerate inference?\n\nThanks for the suggestion. SGDD naturally supports the use of more advanced solvers such as [16], as it is agnostic to the choice of discrete diffusion samplers. While we are not able to find the implementation of [16] at this time, we believe using such advanced solvers will further speedup SGDD and we leave this as a possible future extension.\n\nReference:\n\n[23] Li et al.  Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding, 2024.\n\n[24] Wu et al. Practical and asymptotically exact conditional sampling in diffusion models, 2024.\n\n[25] Esser et al. \"Taming Transformers for High-Resolution Image Synthesis.\" 2021."}, {"review_id": "YUJxg6Z44L", "reviewer": "Reviewer_f55Z", "summary": "This paper presents a new diffusion model sampling technique that can be used on discrete target distributions. \nThey augment the space by introducing an auxiliary random variable, $z$, that appears in a \"regularization potential\" term, $D(.)$, controlling the divergence of the intermediate distributions from the target. The augmented posterior is approximated by Gibbs sampling and via updating the original and auxiliary RVs, $x$ and $z$, iteratively. In this context this technique is called \"Split Gibbs\" sampling and is already applied to continuous settings. To apply Split Gibbs sampling to the discrete setting, the current work specifies a new potential function which leads to the new techque, namely Split Gibbs Discrete Diffusion sampling (SGDD). The convergence of the proposed algorithm is proved w.r.t. the Fisher divergecne.\nSGDD is compared with multiple algorithms for discrete diffusion posterior sampling across multiple domains. The reported results show that on these models, SGDD outperforms the existing baselines.", "questions": "1. In the theorem, the convergence is w.r.t. the Fisher divergence, but in Table 2, the performance is measured w.r.t. Hellinger distance. Could you also report the Fisher divergence as well as the KL divergence from the target? \n\n2. Could you provide a link to the code?", "limitations": "This is a theoretical work with no direct social impact.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper is well-written; the preliminaries and related work are sufficiently discussed; the SGDD algorithm is explained clearly and compared against several relevant state-of-the-art algorithms on various models.  \n\nWeaknesses: \nMinor comments on the notation:\n1. In lines 68-70 and 140, I assume $\\mathbf{11}^T$?  represents an $N \\times N$ matrix of ones? This notation is a bit confusing and should be clarified.  \n2. Define $\\dot{\\sigma}_t$, (I suppose it denotes $d \\sigma_t /dt$).\n\nPlease also see the Section \"Questions\" below.", "was_revised": false, "final_justification": "", "rebuttal": "> 1. Ambiguities in notations.\n\nYes, $\\mathbf{1}\\mathbf{1}^T$ means a matrix of all ones, and $\\dot \\sigma\\_t$ is defined as $\\mathrm d\\sigma\\_t/\\mathrm dt$. We will clarify these notations in the revised version.\n\n> 2. Providing Fisher divergence and KL divergence in table 2.\n\nThanks for the suggestion. The relative Fisher divergence is considered for the purpose of theoretical analysis. It is hard to evaluate relative Fisher divergence, because it is defined with respective to the rate matrix $\\mathbf Q\\_t$. However, we provide the KL divergence for the experiments on synthetic data:\n\n| KL divergence | D=2 | D=5 | D=10 |\n| -------- | -------- | -------- | --- |\n| SVDD-PM (M=20) |  0.374 | 0.826 | 1.087 |\n| SMC (TDS) | 0.158 | 0.567 | 0.909 |\n| DPS  | 0.117 | 0.586 | 0.836 |\n| SGDD | 0.072 | 0.204 | 0.560 |\n\n> 3. Could you provide a link to the code?\n\nThanks for your interest! Please check our code in the supplementary file."}, {"review_id": "XGiiI8xZAy", "reviewer": "Reviewer_z3tY", "summary": "The paper proposes an adaptation of the PnPDM split Gibbs sampler ([1]) to sampling from conditional distributions that use a discrete diffusion generative models as priors. To do so, it proposes using a different coupling potential for the two variables of the split Gibbs that makes the prior step of the Gibbs sampler be the equivalent of the backward part of the generative model, much like the standard gaussian coupling potential does for the continuous split Gibbs sampler in [1]. It then states a theoretical results for fixed $eta$ law of the Gibbs sampler, that is heavily inspired by the theoretical result of [1]. It then proceeds to a numerical verification of the proposed algorithm in several benchmarks.", "questions": "See weaknesses for the questions that I had, manly on the numerics part. If some of the writing is improved and details to the numerics are added I am willing to increase my grade.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper proposes an interesting way of adapting PnPDM to the discrete diffusion case. The approach is sound and the adaptation of the coupling potential is appropriate. The results about the split Gibbs are described in a detailed and precise fashion. \n\nWeaknesses:\n1. The claims in the paper concerning SMC-based methods are highly biased. Namely, lines 190-192. SMC guarantees hold for finite number of particles and I do not see why the guarantees from theorem 1 are inherently better than SMC. Furthermore, the role of the potential functions on SMC can be equated to the choices of $eta$ in the split Gibbs mechanism. Furthermore, most SMC guarantees regard the target posterior distribution and not a $eta$-version as in theorem 1. Therefore, this claim, while not at all necessary to the paper, which could justify their sampler by other merits of the sampler in itself, lead to a biased presentation of the current literature in the topic, which is not acceptable, specially in a prestigious venue as NeurIPS.\n\n2. Numerics pt1: Do the authors try to equate the NFE for all the samplers in table 2 and all section 4? This is on of the only ways of establishing \"fair\" comparison between different samplers, so one would expect so. But, as far as I'm concerned, even in the appendix I cannot find the number of particles used in the SMC approach (except for table 6, which is a different type of experiment).\n\n3. Numerics pt2: Several other small details are missing in the numerics, namely what is exactly the function $G$ in the Monophonic Music problem.", "was_revised": true, "final_justification": "The authors properly addressed my concerns and promised to add more details of the experimental section to the revised version. Therefore, I am inclined to suggest accepting the paper.", "rebuttal": "> 1. Clarifications on the claims about SMC-based methods.\n\nThanks for pointing this out. The claims made in lines 190-192 were only targeting the baseline methods SVDD [1] and TDS [2]. SVDD estimates a value function of noisy samples during diffusion sampling, and the guarantees of TDS hold only when the number of particles goes to infinity. However, the reviewer is right that these claims are not true for SMC-based methods in general. We apologize for causing these confusions, and we will correct this claim in our revised version.\n\nMoreover, we further include a more recent SMC-based method from Feynman-Kac (FK) steering [3], with MAX potential function (i.e. the best value along the sampling history). We use $M=20$ particles for all SMC-based experiments. Following this experiment, we will also include a more comprehensive literiture review in Section 2.2 to discuss recent advancements of SMC-based methods. As we see in the results below, while FK-MAX performs slightly better than TDS, our SGDD method significantly outperforms both SMC-based methods.\n\n| DNA | Pred-Activity (median) | ATAC Acc | Log-likelihood | \n| --  | --| -- | -- |\n| TDS [2] | 4.64 | 45.3% | -257|\n| FK-MAX [3] | 4.90 | 47.1% | -243 |\n| SGDD | 9.14 | 93.0% | -261|\n\n| MNIST-XOR | PSNR | Accuracy |\n| -- | -- | -- |\n| SMC | 10.05 | 27.8% |\n| FK-MAX [3] | 11.20 | 34.7% |\n| SGDD | 20.17 | 91.2% | \n\n> 2. Equating number of functional evaluations.\n\nWe use the same configurations (number of particles $M=20$ and NFEs) for SMC and SVDD in all experiments, as shown in Table 6 of Appendix B, resulting in 5120 NFEs for SMC methods. The configurations for SGDD is described in Table 7, with NFEs ($=H\\cdot K$) ranging from 200 to 2000, consistently lower than the NFEs used by baseline methods. While the the functional evaluations of SMC-based methods can be parallelized, we compute and compare the runtime of each method (in Table 6) on MNIST-XOR as an example. \n\n> 3. Missing details on monophonic music task. \n\nThanks for pointing this out! The forward model $G$ is an operator that randomly masks $\\gamma = 40\\\\%$ or $60\\\\%$ of the notes. We will make this clear in our revision.\n\n[1] Li et al.  Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding, 2024.\n\n[2] Wu et al. Practical and asymptotically exact conditional sampling in diffusion models, 2024.\n\n[3] Singhal et al. A general framework for inference-time scaling and steering of diffusion models, 2025."}, {"review_id": "vx9kttfpOw", "reviewer": "Reviewer_1thq", "summary": "- Method for sampling from posterior distribution $p(x|y)$ and reward tilted distribution.\n    - Introduce an auxiliary variable $z$ and an augmented distribution $\\pi$\n    - Both marginal of $\\pi$ converge to the posterior distribution.\n    - Sampling is done by alternating a likelihood sampling step and a prior sampling step.\n- They adapt prior work  to discrete diffusion.\n- Prove the convergence of their method\n- Substantial experiments across challenging tasks", "questions": "See weakness", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- The paper is well written and easy to follow. \nFigure 1 illustrates the method well and helps understanding the paper.\n- The method does not require gradients w.r.t the likelihood.\n- The experiments are substantial, challenging and showcases the performance of the method.\n- The theory is convincing and presented clearly.\n- It appears the method does not need any additional training.\n- The insights regarding noise schedule selection for sampling are valuable and well-explained.\n\n### Weaknesses\n\n- The framework appears designed specifically for uniform transition kernels. Could the authors clarify this limitation? If confirmed, what prevents extension to more general kernels? While absorbing kernels have inherent limitations, they currently represent the state-of-the-art, and demonstrating compatibility would significantly strengthen the work. Additionally, recent literature explores more promising kernels beyond masked processes, and generalization to these newer approaches would enhance the method's broader applicability.\n\n#### Theoretical concerns\n\nI have not read the proof in details but from what I have seen I do not see any theoretical concerns.", "was_revised": true, "final_justification": "I believe this work offers an interesting method with solid experiments to sample from discrete models. It is experimentally and theoretically strong and deserves in my opinion to be accepted.", "rebuttal": "> 1. Is SGDD limited to discrete diffusion models with uniform transition kernels? What prevents extension to more general kernels? \n\nYes, SGDD only considers discrete diffusion models with uniform transition kernel. Recall that we design a potential function $D$ in Equation (10) to make Equation (9) equivalent to a partial prior sampling from discrete diffusion models. The primary challenge of extending SGDD to other types of discrete diffusion model is to find another potential function that relates Equation (9) to prior sampling. However, masked diffusion models requires operating on an additional [MASK] token, on which the likelihood function is not defined, making this extension a nontrivial task. Nonetheless, we believe it is still possible if we carefully specify the likelihood function on sequences with [MASK] tokens as well, but we will leave this as an interesting future exploration."}]

Author rebuttal:

Meta-review: The paper proposes a posterior sampling algorithm based on split Gibbs sampling for discrete diffusion models. It establishes theoretical convergence guarantees and provides experiments demonstrating the effectiveness of the proposed approach. During the discussion phase, the authors also clarified the reviewers’ questions. Overall, this is a solid contribution that will likely be of broad interest to the NeurIPS community. I therefore recommend acceptance of the paper.
Decision: Accept (poster)