Split Gibbs Discrete Diffusion Posterior Sampling

1. Is SGDD limited to discrete diffusion models with uniform transition kernels? What prevents extension to more general kernels?

Yes, 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.

1. Clarifications on the claims about SMC-based methods.

Thanks 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.

Moreover, 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.

2. Equating number of functional evaluations.

We 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.

3. Missing details on monophonic music task.

Thanks 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.

[1] Li et al. Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding, 2024.

[2] Wu et al. Practical and asymptotically exact conditional sampling in diffusion models, 2024.

[3] Singhal et al. A general framework for inference-time scaling and steering of diffusion models, 2025.

1. Ambiguities in notations.

Yes, $\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.

2. Providing Fisher divergence and KL divergence in table 2.

Thanks 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:

3. Could you provide a link to the code?

Thanks for your interest! Please check our code in the supplementary file.

1. More comprehensive literature review of related methods in SMC and inference-time scaling.

We 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). To 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.

2. Justifications on our theoretical results.

We 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

• 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$.

Note 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].

Given 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

where 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

Note 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

\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. $$= - \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.$$

Note 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.

6. Applying advanced solvers to accelerate inference?

Thanks 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.

Reference:

[23] Li et al. Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding, 2024.

[24] Wu et al. Practical and asymptotically exact conditional sampling in diffusion models, 2024.

[25] Esser et al. "Taming Transformers for High-Resolution Image Synthesis." 2021.

The reviewer would like to thank the authors for their detailed response, which has addressed most of my concern. Therefore, I will raise my score from 2 to 3. However, please ensure that all revisions outlined in the rebuttal above (theory, literature review and extra experiments) are incorporated in the final version of the manuscript.