Discrete Markov Probabilistic Models: An Improved Discrete Score-Based Framework with sharp convergence bounds under minimal assumptions

We thank the reviewer for their thoughtful remarks and the opportunity to clarify the significance of our theoretical results. Our primary aim is to establish convergence guarantees for discrete generative models, analogous to those in continuous diffusion. This led us to a discrete score function with two key formulations (Propositions 1.1 and 1.2), from which our methodology naturally follows—culminating in strong convergence results, arguably our chief contribution.

As emphasized in our paper, there is a notable lack of results concerning discrete diffusion models. The closest related work, which improves upon ours in several respects (as detailed in our response to Reviewer fUbX), has only recently been accepted to ICLR [1].

While we include experiments to illustrate the method’s potential, we agree with the reviewer that they should be viewed as preliminary—particularly for large-scale or high-dimensional data. We will revise the paper’s conclusion to emphasize that these findings are intended to motivate and guide future empirical studies, not to be a conclusive benchmark.

[1] Ren et al, ICLR 2025

[no] widely recognized large-scale binary datasets...

We emphasize the hypercube setting’s relevance. First, many real-world large-scale datasets use binary data (e.g., millions of presence/absence edges in amazon products or research papers see [2]), enabling applications like link repair, synthetic-data generation for privacy, or also molecule design. Second, any discrete dataset can be binarized (e.g., 8-bit pixel encoding), and recent developments such as Differentiable Logic Gates Networks [3] show how bit-based methods can excel with neural networks, with the right engineering. We belive our framework provides a strong foundation for bit-based generative models.

[2] Hu et al. 2020, Open Graph Benchmark, Neurips

[3] Petersen et al. 2022, Neurips

[...] particular case of discrete state space CTMCs...

Our method indeed fits within the class of discrete-state CTMCs. Its novelty stems from exploiting the hypercube in a more specialized way than the general framework in [4]. We can introduce efficient optimization strategies, mirroring approaches like MDLM with the SUBS parameterization or MD4, which leverage the structure of the absorbing kernel.

Like SEDD [5], we parameterize a ratio of density $\mu_t(y) / \mu_t(x)$ rather than a reverse density $p_{0 |t}$, which is easier since it is a general value rather than a proper distribution. Furthermore, our objective function is expressed in continuous time, contrary to the loss in [4] which must be extended from discrete time and approximated.

Contrary to SEDD, our backward process is characterized by a conditional expectation we exploit in a regression problem using an ${L}_2$ loss term. The discrete denoiser structure is also exploit with a cross-entropy loss term. In contrast, SEDD only derives our entropic regularization loss term (see [eq. (10), 5] and our eq. (16)).

[4] Campbell et al. 2022, Neurips

[5] Lou et al. 2024, ICML

the paper lacks insufficient hyperparameters testing...

We first underline the symmetric choice of $T_f$ and $\lambda$, because of time reparameterization. Consider a time-dependent rate $\lambda_t$, with $Q_t = \lambda_t Q$, then $P_t^{\lambda} = \exp(Q\int_0^t \lambda_s ds) = P_{\int_0^t \lambda_s ds}$. In practice, we fix $\lambda = 1$ and vary $T_f$, leaving more sophisticated noise schedules to future work.

We did an initial grid search for $\lambda, T_f$, validating $T_f = 3$. We thought the results in Figure 1 were convincing. As suggested, we will include an expanded search on MNIST together with various plots in the camera-ready version, like convergence speed to uniform distribution (e.g., on MNIST, we can see the sliced Wasserstein distance between $p_{\text{uniform}}$ and $p_t$ plateau after $t \approx 2.5$).

The FID metric...

The reviewer makes a fair point, but we note that FID has been successfully used for MNIST (e.g., [6]) and is reliable in our experiments. In addition to FID we report our $F_1^{dc}$ metric, see Appendix D.3. It relies on local geometry to evaluate generative quality/diversity. We remain open to other metrics as recommended, we are confident we will still observe improvements.

[6] Xu et al. 2023, Normalizing flow neural networks by JKO scheme, Neurips

Beneficial to compare with [...] SEDD uniform

We train SEDD Uniform with the same settings as the other models. In response to concerns about FID, we report the $F_1^{dc}$ metric. Again, we see clear improvements:

Table 1: $F_1^{\text{dc}}\uparrow$ for different methods

We hope that the previous discussion has satisfied the reviewer. If this is the case, we kindly ask them to consider raising their score, if they feel it is appropriate.

We thank the reviewer for their very positive feedback, and for finding our paper an interesting contribution to discrete diffusion models from both theoretical and methodological perspectives.

I wonder if the DMPM can be generalized to systems where each particle has more than two potential states. Can you modify the Poission clock to design a proper forward process? And can the backward process and convergence result be derived with similar approaches in this paper?

We thank the reviewer for the opportunity to address this question.

First, it is entirely possible to stay within the hypercube setting for any discrete data by using binary encoding. For instance, colored images can be encoded in 8-bits RGB pixels. Then each image is encoded in {$0, 1$}$^{3 \times 8 \times 64 \times 64}$, if using images of size $64 \times 64$, for instance. The same approach can be adopted for particles with more than two possible states.

Second, we believe it should be possible to extend our study to state-spaces like {$0, \cdots, N$}$^d$, defining the uniform random walk with unit increment as the noising process, and that the backward process and convergence results would be derived very similarly.

However, we emphasize that our paper's philosophy is to stay within the binary hypercube, and benefit from various optimizations enabled by such a setting, both theoretically and methodologically. For instance, this yields our regression objective, with the ${L}_2$ loss term (eq. 15), and our discrete denoiser structure, leading to the cross-entropy loss term (eq. 17).

Assumption 2.2 seems a bit too restrictive [...]. Is this assumption technical or essential to the proof of the convergence?

We thank the reviewer for the opportunity to clarify this point. We wish to reassure them as we relax Assumption 2.2 soon after introducing it.

Initially, it is used in Theorem 2.3 to derive our simplest convergence bound, which involves computing a Fisher divergence. However, we subsequently employ an early-stopping argument (as detailed from Theorem 2.5 onward) to circumvent its necessity in practice.

This mirrors what happens in continuous diffusion models, where the data may lie on a lower-dimensional manifold without admitting a density against the Lebesgue measure in the full ambient space. There, too, the same line of arguments involving early stopping are used.

In practice, the learned model can still assign zero probability to impossible states. For example, on MNIST, we observe that the learned model faithfully recreates handwritten digits, and it is safe to assume that it assigns negligible or zero probability to meaningless states (such as a completely white image). Hence, the assumption does not pose a practical limitation either.

We hope we have successfully addressed the reviewer's questions, and we would like to thank them again for their positive feedback.

We thank the reviewer for their comments, which will help improve the presentation of our contributions. We hope that we have addressed all of their questions in the responses below. Given their positive feedback—particularly their appreciation of the "very impressive" theoretical contributions—we would kindly ask the reviewer to consider raising their score, if they feel it is appropriate.

I wanted to know whether the breakthrough [...] briefly outline Appendix F (Proof of Theoretical Results)

We thank the reviewer for their remark, which will help us clarify the key contributions of our paper. To this end, we provide a brief sketch of the proof for Theorem 2.3, which we will expand upon and include in the revised version of the paper.

The first step in the proof is to decompose the relative entropy
between the backward process and our generative algorithm into three terms:

$$\mathrm{KL}(\overleftarrow{P} \| P^*) \leq \mathrm{KL}(\mu_{T_f} \| \gamma^d) + II + III.$$

• The first term on the right-hand side arises from the fact that the generative process does not start from the marginal at time $T_f$, but rather from the stationary distribution $\gamma^d$. Using standard arguments for the convergence of random walks on $\lbrace 0,1\rbrace^d$, this term is exponentially small in $T_f$.

• The second term $II$ corresponds to the score approximation error. By Assumption 2.1, we can bound it by $T_f \varepsilon$.

• The third term, $III$, corresponds to the time discretization error of the generative process. It is given by

$$\sum_k \mathbb{E} [ \int_{[t_k, t_{k+1}]} \sum_{\ell} u^*_{t_k}(\ell) \cdot h(u^*_{t}(\ell)/u^*_{t_k}(\ell)) dt ],$$

where $u_t^*(\ell) = 1 - s_t^{\ell}(\overleftarrow{X}_{t})$, and $(\overleftarrow{X}_t)_t$ denotes the time-reversed process.

To bound this term, we rely critically on Proposition F.11, which serves as the main technical tool in our analysis. Specifically, the proposition shows that:

1. The process $(\sum_{\ell} u^*_t( \ell) )_t$ is a martingale, and
2. The process $(\sum_{\ell} h(u^*_t(\ell)))_t$ is a submartingale.

Thanks to these two properties, along with Assumption 2.2 and an application of Jensen’s inequality, we are able to bound the third term $III$.

does the fact that we have made a stronger assumption on the state transition matrix than before contribute to this concise argument?

The reviewer is correct in noting that the arguments we developed—and summarized in our previous response—crucially rely on using the random walk on {$0,1$}$^d$ as the noising process. Nevertheless, we view our work as a foundational step toward extending the framework to broader classes of discrete generative models.

In fact, as part of our future work, we aim to formalize our reasoning in a more general setting that could encompass a wide family of discrete models, including masked diffusion processes.

My main concern [...] is a much stronger situation than the assumptions made in previous papers.[...]

We thank the reviewer for this comment, which helps to clarify the implications of our work.

First, as this appears to be the reviewer’s most critical concern, we acknowledge that—unlike most previous works—both the state space and the noising process we consider are fixed. These choices are indeed crucial for establishing our theoretical results (as detailed further above) under minimal assumptions on the data distribution. We will emphasize on this point in the revised version of the paper.

However, we would like to make two points in response. First, although working on the hypercube may initially appear restrictive, we note that any discrete space can, in principle, be embedded into the hypercube via binary encoding. This means that our algorithm can, in theory, be applied to any discrete data structures.

Second, we view the theoretical analysis presented in this paper as a first important step to demonstrate that convergence guarantees for a general class of discrete score-based generative models can be achieved under minimal assumptions on the data distribution. As we emphasized in our first response, we are confident that the techniques developed here have the potential to extend to other discrete structures as well. However, since the exact scope of this generalization is not yet fully understood, we refrain from making definitive claims at this stage.

In particular, the description of the paper's position in relation to the latest methods [...] is limited to high-level, abstract explanations.

We will follow the reviewer’s suggestion and, in particular, include a comparison table in the camera-ready version of our paper. We also plan to add a detailed discussion of the assumptions made in previous works—specifically those concerning the data distribution, as well as the density and score of the noising process—which our approach is able to relax.

We thank the reviewer for their positive feedback, especially regarding the strength of our theoretical contributions. Due to space constraints, we address only the most critical concerns, but we welcome further discussion if any important points remain unaddressed.

Additional large-scale experiments or high-dimensional evaluations are necessary [...]

We acknowledge that our experiments are limited, and we agree that more extensive large-scale and high-dimensional evaluations are necessary to fully support the use of uniform noising kernels in comparison to masked ones. Nevertheless, as the reviewer noted, the core contributions of our paper are theoretical.

Our main objective is to derive convergence guarantees for discrete generative models that match those known for continuous diffusion models. As emphasized in our paper, there is a notable lack of results concerning discrete diffusion models. The closest related work, upon which ours significantly improves (as detailed in our response to Rev. fUbX), has only recently been accepted to ICLR [1].

In pursuing our goal, we obtained a representation of the score as a conditional expectation (Prop 1.1 and 1.2), which is the foundation of our methodology.

While limited, we believe our numerical experiments add value by showing the practical potential of our approach. That said, we agree that strong conclusions should not be drawn from these preliminary results, especially in large-scale or high-dimensional scenarios. To address this, we will revise the conclusion to clarify that our findings are meant to motivate future empirical work rather than provide definitive evidence.

[1] Ren et al, ICLR 2025

Lines 99-103 [...] The notion of conditional expectation of [...] is the key contribution in prior works, such as D3PM or MDLM).

From our understanding, prior works—including those mentioned by the reviewer— aim to estimate the generator associated with the backward dynamics of the backward process relying on estimating the conditional distributions $p_{0|t}$ of $X_0$ given $X_t$ for $t \in [0,T_f]$.

In contrast, we first demonstrate that estimating the generator of the time-reversed process is equivalent to estimating the discrete score function introduced. Second, we show that (1) this score function can be expressed as a conditional expectation, and (2) it is associated with a discrete denoising structure.

Therefore estimating the backward generator reduces to solving either a regression or a classification problem—tasks that are often more tractable than learning full conditional distributions. While prior work seeks to model an entire conditional distribution, we focus on estimate a function that solves a regression or classification task.

We regret any confusion caused by the original formulation and will revise the paper to include this discussion in order to clarify our claims.

Theorem 2 in [2] [...] Isn’t there a tight characterization of this error?

The third term $\epsilon T_f$ has the same meaning and significance of the corresponding term in Theorem 2 of [2], appearing as such. Indeed, it accounts for the score approximation error that we do not investigate in our submission similarly to [2].

[2] Chen et al, ICLR 22

The transition probabilities [...] can be seen in [...] (Chapter 2, Liggett)...

As stated in the paper, these computations are well known, and we thank the referee for pointing out the reference in Liggett’s book, which we will include in the revised version. As the referee suggests, we will emphasize this point more clearly early in the paper.

The regression loss used in Equation (15) is quite similar to the DFM loss...

First, we would like to emphasize the following points based on our understanding:

• (1) The SUBS parameterization is applicable only to absorbing kernels;
• (2) The approach in [3] focuses on estimating conditional probabilities $p_{s|t}$, which is fundamentally different from our methodology, as previously discussed.

Concerning the DFM loss, we were not able to find a similar result as ours in [4]. It seems to us they use a flow matching construction with a conditional rate matrix built ad-hoc (Section 3.2). This seems fundamentally different from the way we derive our reverse process (see (4)).

[3] Sahoo S. et al, 2024, Neurips [4] Campbell et al 2022, Neurips

What is the relation between Assumption 2.2 and the irreducibility property of CTMC?

Ass. 2.2 only states that $\mu^\star$ has full support and does not impose any conditions on the CTMC considered in our analysis.

Table 1: DMPM (flip) seems inconsistent

We thank the reviewer for spotting this, indeed we loaded the wrong model checkpoint for the evaluation run at 500 steps, here is the result of a new run:

Table 1: FID$\downarrow$ and F$_1^{dc}\uparrow$ for DMPM methods at 500 reverse steps.