Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis

## Abstract

Abstract Diffusion models have achieved great success in generating high-dimensional samples across various applications. While the theoretical guarantees for continuous-state diffusion models have been extensively studied, the convergence analysis of the discrete-state counterparts remains under-explored. In this paper, we study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space [ S ] d superscript delimited-[] 𝑆 𝑑 [S]^{d} [ italic_S ] start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT that utilizes score estimators at predefined time points. We derive convergence bounds for the Kullback-Leibler (KL) divergence and total variation (TV) distance between the generated sample distribution and the data distribution, considering both scenarios with and without early stopping under specific assumptions. Notably, our KL divergence bounds are nearly linear in dimension d 𝑑 d italic_d , aligning with state-of-the-art results for diffusion models. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function, which are essential for characterizing the discrete-time sampling process.

## 1 Introduction

Diffusion models (Sohl-Dickstein et al., ; Song and Ermon, ; Ho et al., ) have achieved great empirical success in various generative tasks including audio (Kong et al., ; Schneider, ), video (Ho et al., ; Yang et al., ), and image (Batzolis et al., ; Ho et al., ) generation, and have demonstrated potential across a wide range of domains like computer visions (Baranchuk et al., ; Whang et al., ), medical image reconstruction (Chung and Ye, ; Cao et al., ), and bioinformatics (Guo et al., , ). The main goal of diffusion models is to generate novel samples from an unknown and unstructured data distribution. In general, the framework of score-based diffusion models consists of two stochastic processes: a predefined forward noising process that gradually corrupts data into some easy-to-sample noise distribution (e.g., standard Gaussian), and a reverse generative process generating new samples that almost obeys the real data distribution from the pure noise by learning the logarithmic gradient of the forward marginal distributions known as the (Stein) score.

Previous works on diffusion models primarily focus on continuous state spaces, such as the Euclidean space $\mathbb{R}^{d}$. In this setting, as studied by Song et al. (), the forward process can be constructed as a continuous-time process characterized by a stochastic differential equation (SDE). The associated reverse process is also described by an SDE, which incorporates the drift and diffusion coefficients of the forward SDE along with the score function. Hence, an approximate reverse process can be constructed by estimating the score functions, which is the core principle of the score-based diffusion models. However, many problems require us to deal with discrete data, which arise in fields like text generation (Austin et al., ; Hoogeboom et al., ; Li et al., ; Zheng et al., ), protein design (Gruver et al., ; Campbell et al., ), and segmentation maps (Zbinden et al., ; Courdier et al., ). Therefore, modeling probability distributions and constructing diffusion processes in discrete space is of great importance.

To tackle the discrete data, analogous to the state-of-the-art Denoising Diffusion Probabilistic Models (DDPMs) (Ho et al., ) in continuous state space, Austin et al. () proposed structured discrete diffusion models in discrete time, which was referred to as Discrete Denoising Diffusion Probabilistic Models (D3PMs). Campbell et al. () first introduced a continuous-time framework for discrete diffusion models, in which the forward noising process is formulated as a CTMC. Similar to the continuous SDE setting, the reversal of a forward CTMC can be characterized by the forward rate matrix and the forward marginal probability ratios known as the discrete score function. Lou et al. () proposed methods for estimating the discrete score by minimizing discrete score matching objectives. Thus, we can refer to the discrete diffusion models by estimating the score function within the CTMC framework as the score-based discrete diffusion models. Interestingly, as studied in Benton et al. (), score-based continuous space SDE diffusion and discrete space CTMC diffusion can be regarded as a more general unity, which well illustrates the many similarities between discrete and continuous diffusion.

In light of the significant empirical advances, extensive theoretical works for understanding the efficiency and acceleration of score-based diffusion models in the SDE framework (Chen et al., ; Lee et al., ; Yang and Wibisono, ; Chen et al., ; Benton et al., ; Li et al., , ; Cheng et al., ; Li et al., ; Chen et al., , ; Gupta et al., ) have arisen. Nevertheless, the theoretical foundation remains largely absent for discrete diffusion models, both in discrete-time and continuous-time settings. The recent work Chen and Ying () first studied the theory of score-based discrete diffusion model. This paper proposed a sampling algorithm in the hypercube setting $\{0,1\}^{d}$ utilizing the uniformization technique of CTMC, proved its efficiency by deriving convergence bounds and sampling complexities, and applied the elementary properties of the discrete score function to promote the algorithm design. Motivated by these prior works, we focus on the theoretical analysis of the score-based discrete diffusion model within the CTMC framework, as it allows us to leverage the score error and properties as studied in continuous diffusion models. The discrete-time sampling algorithm and methodology in our paper are closely related to the previous works on the theory of continuous diffusion models (Chen et al., ; Benton et al., , ) and discrete diffusion models (Campbell et al., ; Chen and Ying, ).

### 1.1 Contributions

- 1.
Analogous to the state-of-the-art exponential integrator (Zhang and Chen, ; De Bortoli, ; Yang and Wibisono, ; Chen et al., ) within the SDE framework, which discretizes the true reversal SDE, we propose a discrete-time sampling algorithm for high-dimensional discrete diffusion tasks with theoretical guarantee within the CTMC framework. Under reasonable assumptions, we derive convergence bounds for scenarios with and without early stopping. When the data distribution is balanced, the bound without early stopping is tighter than the bound with early stopping. Our main KL divergence bounds for convergence comprise three components: score estimation error, discretization error, and the error due to insufficient mixing of the forward process, which correspond to the typical convergence bound of continuous diffusion models (Chen et al., , ; Yang and Wibisono, ; Benton et al., ).
- 2.
Technically, we use the Girsanov-based method to analyze the proposed discrete-time generative algorithm. We first explore theoretical properties of discrete score functions such as the movement bound to facilitate our analysis. The discretization error terms in our main bounds are novel in the literature on the score-based discrete diffusion models. Also, we first derive the exponential convergence of the forward process with uniform mixing in the general state space $[S]^{d}$. Our KL divergence bounds are nearly linear in the dimension $d$, matching the best result for continuous diffusion models (Benton et al., ) and discrete diffusion models (Chen and Ying, ).

### 1.2 Notations

We use lowercase letters to denote scalars and boldface lowercase letters to represent vectors. The $i$-th entry of a vector ${\mathbf{x}}$ is denoted by ${\mathbf{x}}^{i}$, or simply $x^{i}$ when the context is clear. We use ${\mathbf{x}}^{\backslash i}$ to refer to all dimensions of ${\mathbf{x}}$ except the $i$-th, and ${\mathbf{x}}^{\backslash i}\odot\hat{x}^{i}$ to denote a vector whose $i$-th dimension takes the value $\hat{x}^{i}$, while the other dimensions remain as ${\mathbf{x}}^{\backslash i}$. For a positive integer $n$, we denote $[n]$ as the set $\{1,2,\dots,n\}$, $\mathbf{1}_{n}\in\mathbb{R}^{n}$ as the column vector of ones, and $I_{n}\in\mathbb{R}^{n\times n}$ as the identity matrix. The notation ${\mathbf{e}}_{i}$ refers to a one-hot column vector with a $1$ in the $i$-th position. The Hamming distance between two vectors ${\mathbf{x}}$ and ${\mathbf{y}}$ is denoted by $\mathrm{Ham}({\mathbf{x}},{\mathbf{y}})=\sum_{i}\mathbf{1}\{x^{i}\neq y^{i}\}$. We use $\mathrm{Cat}({\mathbf{p}})$ to denote a categorical distribution over a one-hot column vector with probabilities given by the column vector ${\mathbf{p}}$. $\delta\{\cdot,\cdot\}$ denotes the Kronecker delta, and $\mathbf{1}\{\cdot\}$ is the indicator function. Additionally, we denote the generalized I-divergence (Amari, ) as $D_{I}({\mathbf{x}}\|{\mathbf{y}})=\sum_{i}(-x^{i}+y^{i}+x^{i}\log(x^{i}/y^{i}))$, which is the Bregman divergence with respect to the negative entropy function $I({\mathbf{x}})=\sum_{i}x^{i}\log x^{i}$.

## 2 Related Work

**Table 1: Comparison of convergence results for score-based discrete diffusion models with and without early stopping. The true reverse CTMC is discretized in our algorithm, leading to a step size $h$ in our bound. For early stopping, a terminal time of $T-\delta$ is used, where $q_{\delta}$ is a $\delta$-uniform perturbation of the data distribution, and $p_{T-\delta}$ is the law of output from the diffusion model after $K$ steps with $T-\delta=Kh$. Without early stopping, $q_{0}=p_{\rm{data}}$ is the data distribution, and $p_{T}$ is the law of output from the diffusion model with time horizon $T$ after $K$ iterations with $T=Kh$. ${\epsilon}$ is score error, $S$ is the size of discrete state space, $C_{1}$ depends on $S$ and $\delta$, and $C_{2}$ and $\kappa^{2}$ depend on the properties of data distribution. To keep comparison consistent, we present all bounds with ${\epsilon}$, though in Chen and Ying () the actual bound is ${\epsilon}T$ due to their time-averaged score error assumption.**
| Space | Time-discretized? | Early stopping? | Assumption | Convergence result | Reference |
| --- | --- | --- | --- | --- | --- |
| $\{0,1\}^{d}$ | No | Yes | continuous score error | $D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})\lesssim de^{-T}+{\epsilon}$ | (, ,<br>Theorem 6) |
| bounded score estimator |  |  |  |  |  |
| $[S]^{d}$ | Yes | Yes | discretized score error | $D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})\lesssim de^{-T}\log S+$ | Theorem 1 (This work) |
| $\delta^{-3}C_{1}S^{2}h^{3}d+C_{1}S^{2}h^{2}dT+C_{1}^{2}{\epsilon}$ |  |  |  |  |  |
| $\{0,1\}^{d}$ | No | No | continuous score error | $D_{\mathrm{KL}}(q_{0}\|p_{T})\lesssim de^{-T}+{\epsilon}$ | (, ,<br>Theorem 7) |
| bounded score estimator |  |  |  |  |  |
| bounded score of $p_{\rm{data}}$ |  |  |  |  |  |
| $[S]^{d}$ | Yes | No | discretized score error | $D_{\mathrm{KL}}(q_{0}\|p_{T})\lesssim de^{-T}\log S+$ | Theorem 2 (This work) |
| bounded score of $p_{\rm{data}}$ | $C_{2}S^{2}h^{2}\kappa^{2}T+C_{2}^{2}{\epsilon}$ |  |  |  |  |

Discrete Diffusion Model.
The diffusion model was first introduced by Sohl-Dickstein et al. (). Many previous works construct discrete diffusion processes as discrete-time Markov chain, and thus train and sample the model in discrete time (Austin et al., ; Chen et al., ). In particular, D3PM (Austin et al., ) and the Discrete Non-Markov Diffusion Model (DNDM) proposed by Chen et al. () serve as the discrete diffusion counterparts to DDPM (Ho et al., ) and Denoising Diffusion Implicit Model (DDIM) (Song et al., ) in continuous diffusion, respectively. These works offer various practical sampling algorithms but lack theoretical guarantees. Given the limitations and inflexibility of the discrete-time formulation, Campbell et al. () proposed a CTMC framework for discrete diffusion models, which offers much greater flexibility in defining the reverse sampling scheme. Due to the particular nature of the discrete space, this paper sensibly proposed to assume the factorization of the forward process for the high-dimension tasks which has been broadly adopted, and correspondingly established a tau-leaping method to simulate the continuous-time reverse process. Lou et al. () provided a practical sampling algorithm using Euler discretization and the discrete Tweedie’s theorem.

Inspiringly, the CTMC framework for discrete diffusion models makes estimating the discrete score function important for simulating the reverse process. Meng et al. () proposed a concrete score matching objective, but the $L^{2}$ distance there cannot fully capture the characteristics of the score and is thus unsatisfactory. Sun et al. () derived the score matching objective from the marginal probabilities of each dimension with maximum likelihood training.
Lou et al. () proposed score entropy losses by deriving the KL divergence path measure between the true and approximate reverse process, which are analogous to the score matching objectives in the continuous counterpart (Hyvärinen and Dayan, ; Vincent, ). Benton et al. () provided a unifying framework for these score matching objectives in both discrete and continuous spaces.

Convergence Analysis of Discrete Diffusion Model.
There is a lack of convergence analysis of discrete diffusion models in the existing literature. Campbell et al. () derived an error bound for the tau-leaping sampling algorithm with TV distance metric, under strong assumptions such as bounded forward probability ratios and $L^{\infty}$ error for the approximate rate matrix, since the forward process can be quite general. The error bound grows at least quadratically in the dimension $d$. Chen and Ying () first introduced a sampling algorithm for score-based discrete diffusion models that exactly simulates the reverse process through uniformization of CTMC in the hypercube setting with independent flips as forward process. They also provided corresponding convergence bounds and algorithm complexities that are nearly linear in the dimension $d$, matching the best result found in continuous diffusion models (Benton et al., ). The results of Chen and Ying () and ours are summarized in Table 1.

## 3 Backgrounds on Score-Based Discrete Diffusion Model

We will be handling discrete data $x_{0}\in{\mathcal{X}}=[N]$. A probability distribution on ${\mathcal{X}}$ can be represented by a probability mass column vector $p\in\mathbb{R}^{N}$, where the entries of $p$ are non-negative and sum to 1. Assume that $x_{0}\sim p_{\rm{data}}$ for some discrete data distribution $p_{\rm{data}}$. The forward noising process is defined as a CTMC on ${\mathcal{X}}$, evolving from $t=0$ to $t=T$, with a rate matrix (or generator matrix) $Q_{t}\in\mathbb{R}^{N\times N}$ and an initial distribution $q_{0}$. Rate matrix $Q_{t}$ defines the infinitesimal transition probability, for the continuous-time process between the two time points $t$ and $t+\Delta t$:

$$ $q_{t+\Delta t|t}(y|x)=\delta\{x,y\}+Q_{t}(x,y)\Delta t+o(\Delta t),$ (1) $$

where $Q_{t}(x,y)$ is the $(x,y)$ element of the rate matrix $Q_{t}$ and $q_{t+\Delta t|t}(y|x)$ denotes the infinitesimal transition probability of being in state $y$ at time $t+\Delta t$ given state $x$ at time $t$. From (1) we know

$$ $Q_{t}(x,y)\geq 0\quad\text{for}\ x\neq y,\quad Q_{t}(x,x)\leq 0,\quad\text{and }\quad Q_{t}(x,x)=-\sum_{y\neq x}Q_{t}(x,y).$ $$

Moreover, the forward marginal distribution $q_{t}$ satisfies Komolgorov forward equation (see, e.g., Campbell et al. (); Chewi ()):

$$ $\frac{\mathrm{d}q_{t}}{\mathrm{d}t}=Q_{t}^{\top}q_{t},\quad q_{0}=p_{\rm{data}}.$ (2) $$

Generally, $Q_{t}$ is chosen as a simple matrix such that the forward process mixes quickly towards noise distribution $p_{\mathrm{ref}}$ which is easy to sample. For example, if setting $\beta(t)$ as a time-dependent scalar, the uniform rate matrix $Q_{t}=\beta(t)(\mathbf{1}_{N}\mathbf{1}_{N}^{\top}-N\cdot I_{N})$ results in $p_{\mathrm{ref}}=\frac{1}{N}\mathbf{1}_{N}$, the uniform distribution on ${\mathcal{X}}$; $Q_{t}=\beta(t)(\mathbf{1}_{N}\cdot{\mathbf{e}}_{\mathrm{MASK}}^{\top}-I_{N})$ yields $p_{\mathrm{ref}}={\mathbf{e}}_{\mathrm{MASK}}$, the one-hot probability encoding of the MASK absorbing state (Austin et al., ; Campbell et al., ; Lou et al., ).

Notably, the forward process has an exact time reversal (Kelly, ; Campbell et al., ) which is also a CTMC with rate matrix $Q^{\leftarrow}_{t}$ given by

$$ $Q^{\leftarrow}_{t}(y,x)=Q_{t}(x,y)\frac{q_{t}(y)}{q_{t}(x)}\quad\text{for}\ x \neq y,\quad\text{and}\quad Q^{\leftarrow}_{t}(x,x)=-\sum_{y\neq x}Q^{ \leftarrow}_{t}(x,y).$ $$

Therefore, we know that the access to probability ratio $\frac{q_{t}(y)}{q_{t}(x)}$ is important to simulate the reversal. Specifically, the collective ratios $s_{t}(x):=\left(\frac{q_{t}(y)}{q_{t}(x)}\right)_{y\neq x}\in\mathbb{R}^{N-1}$ are known as the discrete score function (Meng et al., ), which generalizes the Stein score function $\nabla_{x}\log q_{t}(x)$ (Song and Ermon, ) in the continuous setting. As pointed out by previous works concerning score matching in discrete space (Lou et al., ; Benton et al., ),
we learn a discrete score estimator $\hat{s}_{t}$ to $s_{t}$ for $t\in[0,T]$ by minimizing the score entropy

$$ ${\mathcal{L}}_{\mathrm{SE}}(\hat{s})=\int_{0}^{T}\mathbb{E}_{x_{t}\sim q_{t}} \sum_{y\neq x_{t}}Q_{t}(y,x_{t})D_{I}(s_{t}(x_{t})_{y}\|\hat{s}_{t}(x_{t})_{y} )\,\mathrm{d}t.$ $$

Nota that the score entropy loss is characterized by the Bregman divergence, different from the $L^{2}$ distance loss in the continuous counterpart. We defer the details on the Bregman divergence to Appendix E. The score entropy is exactly the path measure KL divergence (Lou et al., ; Chen and Ying, ; Benton et al., ). Although the score entropy can not be directly estimated, there are equivalent objectives such as implicit score entropy and denoising score entropy (Lou et al., ; Benton et al., ) which can be optimized practically.

## 4 Problem Setting

In practice, the state space factorizes as ${\mathcal{X}}=[S]^{d}$, representing sequences ${\mathbf{x}}={\mathbf{x}}^{1:d}=x^{1}\cdots x^{d}$.

Forward Process.
The forward process $X=(X_{t})_{t\geq 0}$ is defined by a CTMC on ${\mathcal{X}}$ with rate matrix $Q_{t}$ starting from $X_{0}\sim q_{0}=p_{\rm{data}}$ which is the data distribution. Let $q_{t}:=\mathrm{Law}(X_{t})$, which follows the Kolmogorov forward equation (2). As a general $Q_{t}\in\mathbb{R}^{S^{d}\times S^{d}}$ would be of exponential size, we assume that the forward process can be factorized such that each dimension propagates independently with rate $Q_{t}^{\mathrm{tok}}\in\mathbb{R}^{S\times S}$. Namely, the forward transition kernel $q_{t|s}({\mathbf{x}}_{t}|{\mathbf{x}}_{s})={\mathbb{P}}(X_{t}={\mathbf{x}}_{t}
|X_{s}={\mathbf{x}}_{s})$ factorizes as $q_{t|s}({\mathbf{x}}_{t}|{\mathbf{x}}_{s})=\prod_{i=1}^{d}q_{t|s}^{i}(x_{t}^{i
}|x_{s}^{i})$, where $q_{t|s}^{i}(x_{t}^{i}|x_{s}^{i})={\mathbb{P}}(X_{t}^{i}=x_{t}^{i}|X_{s}^{i}=x_
{s}^{i})$ is the transition probability for the $i$-th dimensional CTMC $X^{i}:=(X_{t}^{i})_{t\geq 0}$ with forward rate $Q_{t}^{\mathrm{tok}}$. This is a common assumption in literature considering high dimension tasks in the CTMC setting (Campbell et al., ; Lou et al., ; Campbell et al., ; Chen and Ying, ). According to Campbell et al. (, Proposition 3), the non-zero off-diagonal entries of $Q_{t}$ are given by

$$ $Q_{t}({\mathbf{x}},{\mathbf{x}}^{\backslash i}\odot\hat{x}^{i})=Q_{t}(x^{1} \cdots x^{i}\cdots x^{d},x^{1}\cdots\hat{x}^{i}\cdots x^{d})=Q_{t}^{\mathrm{ tok}}(x^{i},\hat{x}^{i})$ $$

for ${\mathbf{x}}\in{\mathcal{X}}$ and $x^{i}\neq\hat{x}^{i}\in[S]$. We see that the non-zero off-diagonal entries of $Q_{t}$ can only occur between sequences with a Hamming distance of $1$, leading to a rather sparse structure. As for the perturbation of each dimension, we take the time-homogeneous uniform rate

$$ $Q_{t}^{\mathrm{tok}}\equiv Q^{\mathrm{tok}}=\frac{1}{S}\mathbf{1}_{S}\mathbf{1 }_{S}^{\top}-I_{S}.$ $$

This rate matrix is common in applications (Austin et al., ; Campbell et al., ; Lou et al., ; Campbell et al., ), and also analyzed by Chen and Ying () where $S=2$ is taken. Then $Q_{t}\equiv Q$ is of the form

$$ $Q({\mathbf{x}},{\mathbf{y}})=\begin{cases}\frac{1}{S},&\mathrm{Ham}({\mathbf{x }},{\mathbf{y}})=1,\\ (\frac{1}{S}-1)d,&{\mathbf{x}}={\mathbf{y}},\\ 0,&\text{otherwise}.\end{cases}$ $$

We can then obtain the expression of forward transition probabilities and marginals as stated in the following proposition, which shows the process converges to a uniform distribution over ${\mathcal{X}}=[S]^{d}$ which we denote $\pi^{d}$ as $t$ increases. The proof of Proposition 1 is deferred to Appendix A.1.

###### Proposition 1 .

Let $P^{i}_{s,t}\in\mathbb{R}^{S\times S}$ be the transition probability matrix of the $i$-th dimensional forward CTMC $X^{i}$ from time $s$ to time $t$, i.e., $P^{i}_{s,t}(x,y)=q^{i}_{t|s}(y|x)$ for all $x,y\in[S]$ and $i\in[d]$. Then for all $i\in[d]$, $P^{i}_{s,t}\equiv P^{0}_{s,t}$ where

$$ $P^{0}_{s,t}=\frac{1}{S}(1-e^{-(t-s)})\mathbf{1}_{S}\mathbf{1}_{S}^{\top}+e^{-( t-s)}I_{S}.$ $$

Let $P_{s,t}\in\mathbb{R}^{S^{d}\times S^{d}}$ be the transition probability matrix of the forward process from time $s$ to time $t$ for $t>s$, i.e., $P_{s,t}({\mathbf{x}},{\mathbf{y}})=q_{t|s}({\mathbf{y}}|{\mathbf{x}})$ for all ${\mathbf{x}},{\mathbf{y}}\in{\mathcal{X}}$, then

$$ $P_{s,t}=\left(P_{s,t}^{0}\right)^{\otimes d},$ $$

where $(\cdot)^{\otimes d}$ denotes performing the matrix Kronecker product $d$ times. In particular, the marginal distribution of the forward process at time $t$ can be expressed as

$$ $q_{t}=\left[\frac{1}{S}(1-e^{-t})\mathbf{1}_{S}\mathbf{1}_{S}^{\top}+e^{-t}I_{ S}\right]^{\otimes d}\cdot p_{\rm{data}},$ $$

and when $t\to+\infty$, $q_{t}$ approaches the uniform distribution $\pi^{d}$.

Reverse Process and Score Model. Suppose that we run the forward process until time $T>0$, ending at $q_{T}$. We can convert the noise back into samples if we reverse the forward CTMC dynamic $X$ in time. The reverse process $Y=(Y_{t})_{t\in[0,T]}$ can be achieved by a CTMC starting from $Y_{0}\sim q_{T}$. According to Campbell et al. (, Proposition 3), the reverse rate $Q^{\leftarrow}_{t}\in\mathbb{R}^{S^{d}\times S^{d}}$ is of the form

$$ $Q^{\leftarrow}_{t}({\mathbf{x}},\tilde{{\mathbf{x}}})=\sum_{i=1}^{d}Q_{T-t}^{ \mathrm{tok}}(\tilde{{\mathbf{x}}}^{i},{\mathbf{x}}^{i})\delta\{{\mathbf{x}}^{ \backslash i},\tilde{{\mathbf{x}}}^{\backslash i}\}\frac{q_{T-t}(\tilde{{ \mathbf{x}}})}{q_{T-t}({\mathbf{x}})}.$ (3) $$

From (3) we know that the non-zero off-diagonal entries of $Q^{\leftarrow}_{t}$ can only occur between sequences with a Hamming distance of $1$. Therefore, we care about the forward marginal ratios between these sequences, and denote the collective ratios as $s_{t}:{\mathcal{X}}\to\mathbb{R}^{d\times(S-1)}$ defined by

$$ $s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}:=\frac{q_{t}({\mathbf{x}}^{\backslash i} \odot\hat{x}^{i})}{q_{t}({\mathbf{x}})}\quad\text{for}\ {\mathbf{x}}\in{ \mathcal{X}},\ i\in[d],\ x^{i}\neq\hat{x}^{i}\in[S].$ $$

Then the sparse structure of $Q_{t}^{\leftarrow}$ can be expressed as

$$ $\displaystyle Q^{\leftarrow}_{t}({\mathbf{x}},{\mathbf{x}}^{\backslash i}\odot \hat{x}^{i})=Q_{T-t}^{\mathrm{tok}}(\hat{x}^{i},x^{i})s_{T-t}({\mathbf{x}})_{i ,\hat{x}^{i}}=\frac{1}{S}s_{T-t}({\mathbf{x}})_{i,\hat{x}^{i}}\quad\text{for} \ i\in[d],\ \hat{x}^{i}\neq x^{i}\in[S].$ $$

With rate $Q_{t}^{\leftarrow}$, it holds that $\mathrm{Law}(Y_{t})\stackrel{{\scriptstyle\text{a.s.}}}{{=}}\mathrm{Law}(X_{T-
t})=q_{T-t}$, and therefore $Y$ is the exact time reversal of the forward process $X$. The reverse marginal $q_{T-t}$ satisfies the Kolmogorov equation

$$ $\displaystyle\frac{\mathrm{d}q_{T-t}}{\mathrm{d}t}=Q^{\leftarrow}_{t}{}^{\top} q_{T-t}.$ (4) $$

However, in practice, we do not have access to $q_{T}$, the initial distribution of the reverse process, so we start the reverse process at the noise $\pi^{d}$, the target distribution of the forward process, and simulate it with score estimators. The score estimator $\hat{s}_{t}:{\mathcal{X}}\to\mathbb{R}^{d\times(S-1)}$ that estimates $s_{t}$ for $t\in[0,T]$ is learned by minimizing the score entropy loss

$$ $\displaystyle{\mathcal{L}}_{\mathrm{SE}}(\hat{s})={}$ $\displaystyle\int_{0}^{T}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}\sum_{i=1}^{d} \sum_{\hat{x}_{t}^{i}\neq x_{t}^{i}}Q_{t}({\mathbf{x}}_{t}^{\backslash i}\odot \hat{x}_{t}^{i},{\mathbf{x}}_{t})D_{I}(s_{t}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^ {i}}\|\hat{s}_{t}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}})\,\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\int_{0}^{T}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}D_{ I}(s_{t}({\mathbf{x}}_{t})\|\hat{s}_{t}({\mathbf{x}}_{t}))\,\mathrm{d}t.$ (5) $$

Algorithm. Since the reverse process is time-inhomogeneous, we can discretize the time to simulate it. Let $h>0$ be the step size, and $T$ be the time horizon. We consider applying early stopping with a terminal time of $T-\delta$, because the score function can blow up as $t\to 0$ for data distributions without full support on ${\mathcal{X}}$. As shown in Section 5, early stopping can be removed when $p_{\rm{data}}$ has full support on ${\mathcal{X}}$. The time horizon is set to $T=Kh+\delta$, where $\delta\geq 0$ is a small value and $K\in{\mathbb{N}}$ is assumed. Suppose we have access to the score estimators $\hat{s}_{T-kh}$ for $k=0,1\cdots,K-1$. We then construct a continuous-time sampling process $Z=(Z_{t})_{t\in[0,T-\delta]}$ starting from $Z_{0}\sim\pi^{d}$, and let $p_{t}:=\mathrm{Law}(Z_{t})$. For $t\in[kh,(k+1)h]$, by freezing the value of the rate matrix in the ODEs (4) at time $kh$ and replacing the true score with the score estimator, $(Z_{t})_{t\in[kh,(k+1)h]}$ is constructed as a time-homogeneous CTMC with rate matrix $\hat{Q}^{\leftarrow}_{kh}\in\mathbb{R}^{S^{d}\times S^{d}}$, where the non-zero off-diagonal entries of $\hat{Q}^{\leftarrow}_{kh}$ are given by

$$ $\hat{Q}^{\leftarrow}_{kh}({\mathbf{x}},{\mathbf{x}}^{\backslash i}\odot\hat{x} ^{i})=\frac{1}{S}\hat{s}_{T-kh}({\mathbf{x}})_{i,\hat{x}^{i}}\quad\text{for}\ i\in[d],\ x^{i}\neq\hat{x}^{i}\in[S].$ $$

Hence, in each step from time $kh$ to $(k+1)h$, the distribution follows the Komolgorov equation

$$ $\frac{\mathrm{d}}{\mathrm{d}t}p_{kh+t|kh}({\mathbf{x}}_{kh+t}|{\mathbf{x}}_{kh })=\hat{Q}^{\leftarrow}_{kh}{}^{\top}p_{kh+t|kh}({\mathbf{x}}_{kh+t}|{\mathbf{ x}}_{kh}),\ t\in[0,h].$ (6) $$

For $k=0,1\cdots,K-1$, theoretically we update the solution of the ODEs (6) as

$$ $\displaystyle{\mathbf{z}}_{k+1}\sim\mathrm{Cat}\left(\exp\left(h\hat{Q}^{ \leftarrow}_{hk}{}^{\top}\right)\cdot({\mathbf{e}}_{{\mathbf{z}}_{k}^{1}} \otimes\cdots\otimes{\mathbf{e}}_{{\mathbf{z}}_{k}^{d}})\right),\ {\mathbf{z}} _{0}\sim\pi^{d}.$ (7) $$

After $K$ iterations, we get a sample ${\mathbf{z}}_{K}$ with law $p_{T-\delta}$. Unlike the exponential integrator in the continuous setting, where the closed-form solution for the iteration formula of sampling random variables can be obtained by solving the linear discretized SDE within each time interval, the discrete setting requires deriving the categorical probability from the Kolmogorov equation and then sampling from this distribution. In practice for sampling, we can run (7) with a Poisson point process utilizing the uniformization of CTMC (Chen and Ying, ) instead of exactly calculating the matrix exponential $\exp(h\hat{Q}^{\leftarrow}_{hk}{}^{\top})$ which is intractable for reasonably sized $S$ and $d$. For completeness, We formalize the practical sampling procedure in Algorithm 1, presented in Appendix D.

###### Proposition 1 .

## 5 Main Results

Our main results are the convergence analyses for the theoretical iterative algorithm (7). We use an analogous Girsanov-based method in the continuous SDE settings (Chen et al., , ; Benton et al., ) by bounding the KL divergence between the path measures of the true reverse process and the sampling process.

The score estimation error measures the quality of the learned score estimator. Since we discretize the true reverse CTMC in our algorithm, we make the following score error assumption.

###### Assumption 1 (Score estimation error) .

The score estimator satisfies

$$ $\frac{1}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1)h+\delta}\mathbb{E}_{{ \mathbf{x}}_{t}\sim q_{t}}D_{I}(s_{(k+1)h+\delta}({\mathbf{x}}_{t})\|\hat{s}_{ (k+1)h+\delta}({\mathbf{x}}_{t}))\,\mathrm{d}t\leq{\epsilon}_{\mathrm{score}}.$ $$

Assumption 1, which we introduce for the first time, can be viewed as a time-discretization of the score entropy loss (5), establishing a discretized version of score error assumptions for our CTMC framework. This assumption is analogous to those widely used in diffusion models (Lee et al., ; Chen et al., , ; Li et al., , , ; Benton et al., ; Chen and Ying, ), but with two key distinctions. First, we use the Bregman distance instead of the $L^{2}$ distance, aligning with the discrete nature of the CTMC framework. Second, in contrast to Chen and Ying (), we only require a small average error over pre-defined discretization points, rather than a continuous error bound.

###### Theorem 1 .

Suppose Assumption 1 holds.
By choosing a small $\delta=\tilde{O}(S^{-\frac{2}{3}})>0$, the KL divergence between $q_{\delta}$ and $p_{T-\delta}$ is bounded by

$$ $D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})\lesssim de^{-T}\log S+\delta^{-3}C_{ 1}S^{2}h^{3}d+C_{1}S^{2}h^{2}dT+C_{1}^{2}{\epsilon}_{\mathrm{score}},$ (8) $$

where $C_{1}=\max\left\{1+\frac{S}{\delta},\max_{{\mathbf{x}}\in{\mathcal{X}},k\in\{0
,\cdots,K-1\}}\|\hat{s}_{(k+1)h+\delta}({\mathbf{x}})\|_{\infty}\right\}$, and the TV distance between $p_{\rm{data}}$ and $p_{T-\delta}$ is bounded by

$$ $D_{\mathrm{TV}}(p_{\rm{data}},p_{T-\delta})\lesssim\sqrt{de^{-T}\log S+\delta^ {-3}C_{1}S^{2}h^{3}d+C_{1}S^{2}h^{2}dT+C_{1}^{2}{\epsilon}_{\mathrm{score}}}+( 1-e^{-d\delta(S-1)/S}).$ (9) $$

The proof of Theorem 1 is deferred to Appendix A.3. We interpret the KL divergence bound (8) as follows. The first term $de^{-T}\log S$ arises from the initialization error of the algorithm. Recall that the true reverse process should begin from $q_{T}$, but the algorithm starts from the noise $\pi^{d}$. The second term $\delta^{-3}C_{1}S^{2}h^{3}d+C_{1}S^{2}h^{2}dT$ reflects the discretization error, which scales with the step size $h$ and is linear in $d$, vanishing as $h\to 0$. The third term $C_{1}^{2}{\epsilon}_{\mathrm{score}}$ corresponds to the score estimation error, which is non-vanishing. We remark that the appearance of the quantity $C_{1}$ in the bound (8), which is absent in the continuous SDE counterpart, stems from the lack of the triangle inequality for the Bregman divergence. Specifically, $C_{1}$ is the uniform bound of the involved score and score estimators. As discussed in Appendix 5, if applying the score clipping technique, we can ensure that $C_{1}\lesssim S/\delta$. The nearly linear dependence on $d$ of the KL bound (8) matches the best result for the continuous diffusion model (Benton et al., ).

The last term in (9) provides an upper bound on the TV distance between $p_{\rm{data}}$ and $q_{\delta}$. There is a trade-off involving $\delta$ in this bound: to reduce $D_{\mathrm{TV}}(p_{\rm{data}},q_{\delta})$, we opt for a rather small $\delta>0$, especially when $d$ is large. However, this causes the square root term to grow rapidly, at a rate of $\delta^{-2}$. As a result, the square root term dominates the bound, leading us to focus on the KL divergence bound (8) for a small $\delta$.

The data distribution characteristics are closely related to the properties of the score function when $t>0$ is small. We perform early stopping because the score of the data distribution can be positive infinity for some data points with a probability of zero. However, if the score of $p_{\rm{data}}$ is uniformly bounded, early stopping is no longer necessary.

###### Assumption 2 .

The data distribution $p_{\rm{data}}$ has full support on ${\mathcal{X}}$, and there exists a uniform $L>0$ depending on $S$ but not on $d$, such that for all ${\mathbf{x}}\in{\mathcal{X}},i\in[d]$ and $x^{i}\neq\hat{x}^{i}\in[S]$,

$$ $s_{0}({\mathbf{x}})_{i,\hat{x}^{i}}=\frac{p_{\rm{data}}({\mathbf{x}}^{ \backslash i}\odot\hat{x}^{i})}{p_{\rm{data}}({\mathbf{x}})}\leq L.$ $$

Assumption 2 is similar to Assumption 3 in Chen and Ying (), both aimed to remove early stopping. Our Assumption 2 is stronger since we assume that $L$ does not depend on $d$. Campbell et al. () also applied similar assumptions, as presented in Assumptions 1 and 2 in their paper. As they noted, the uniform boundness for the data distribution follows trivially from the strict positiveness of $p_{\rm{data}}$ if we allow $L$ to depend on $d$. We adopt the assumption from Campbell et al. (), which enables us to derive a bound that can be nearly linear in $d$, as stated in the following theorem.

###### Theorem 2 .

Suppose Assumptions 1 and 2 hold. Let $\delta=0$. Denote $p_{\rm{data}}^{i}\in\mathbb{R}^{S}$ as the marginal distribution of the $i$-th dimension of the data, and let $\kappa_{i}=\frac{(p_{\rm{data}}^{i})_{\mathrm{max}}}{(p_{\rm{data}}^{i})_{
\mathrm{min}}}$ for $i\in[d]$ and $\kappa^{2}=\sum_{i=1}^{d}\kappa_{i}^{2}$, then it holds that

$$ $\displaystyle D_{\mathrm{KL}}(p_{\rm{data}}\|p_{T})\lesssim de^{-T}\log S+C_{2 }\kappa^{2}S^{2}h^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}},$ (10) $$

where $C_{2}=\max\left\{L,\max_{{\mathbf{x}}\in{\mathcal{X}},k\in\{0,\cdots,K-1\}}\|
\hat{s}_{(k+1)h}({\mathbf{x}})\|_{\infty}\right\}$.

The proof of Theorem 2 is deferred to Appendix A.4. In the bound (10), the term $C_{2}\kappa^{2}S^{2}h^{2}T$ is the discretization error, where $\kappa^{2}$ and $C_{2}$ are related to the property of the data distribution. Specifically, $\kappa^{2}$ is characterized by the ratio of the largest to the smallest entry in the marginal data distribution, and a large value of $\kappa^{2}$ indicates that the probability values for certain data points are either very high or very low. $\kappa^{2}$ is nearly linear in $d$ and equals $d$ when $p_{\rm{data}}$ is a uniform distribution. When $p_{\rm{data}}$ is relatively balanced, meaning that the probabilities across data points are fairly similar, $\kappa^{2}/d$ and $C_{2}$ are reasonably small, and thus the bound (10) is tighter than (8) as it eliminates the term involving $\delta^{-4}$. The quantity $C_{2}$ arises similarly to $C_{1}$, and applying score clipping can make $C_{2}\lesssim L$ as shown in Appendix A.4, where $L$ is proven to be the uniform bound of the score along the forward process.

With the early stopping criterion, Theorem 1 leads to the following iteration complexity for the diffusion model.

###### Corollary 1 .

Suppose Assumption 1 holds. By choosing a small $\delta=\tilde{O}(S^{-2/3})>0$, then for any ${\epsilon}>0$, if choosing $T\asymp\log\left(\frac{d\log S}{{\epsilon}}\right)$ and $h\asymp\min\left\{\delta\left(\frac{{\epsilon}}{C_{1}S^{2}d}\right)^{1/3},
\left(\frac{{\epsilon}}{C_{1}S^{2}d}\right)^{1/2}\right\}$, then the discrete diffusion model requires at most $\tilde{O}\left(\max\left\{\frac{1}{\delta}\left(\frac{C_{1}S^{2}d}{{\epsilon}}
\right)^{1/3},\left(\frac{C_{1}S^{2}d}{{\epsilon}}\right)^{1/2}\right\}\right)$ steps to reach a distribution $p_{T-\delta}$ with $D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})=\tilde{O}({\epsilon}+C_{1}^{2}{
\epsilon}_{\mathrm{score}})$.

By Corollary 1, to have $D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})=\tilde{O}(\epsilon)$, it suffices to choose ${\epsilon}_{\mathrm{score}}=O({\epsilon}/C_{1}^{2})$. Without early stopping, Theorem 2 leads to the following iteration complexity.

###### Corollary 2 .

Suppose Assumptions 1 and 2 hold. Let $\delta=0$, then for any ${\epsilon}>0$, if choosing $T\asymp\log\left(\frac{d\log S}{{\epsilon}}\right)$ and $h\asymp\sqrt{\frac{{\epsilon}}{C_{2}S^{2}\kappa^{2}}}$, then the discrete diffusion model requires at most $\tilde{\Theta}\left(\sqrt{\frac{C_{2}S^{2}\kappa^{2}}{{\epsilon}}}\right)$ steps to reach a distribution $p_{T}$ with $D_{\mathrm{KL}}(p_{\rm{data}}\|p_{T})\leq\tilde{O}({\epsilon}+C_{2}^{2}{
\epsilon}_{\mathrm{score}})$.

By Corollary 2, to have $D_{\mathrm{KL}}(p_{\rm{data}}\|p_{T})=\tilde{O}({\epsilon})$, it suffices to have ${\epsilon}_{\mathrm{score}}=O({\epsilon}/C_{2}^{2})$.

Comparison with Chen and Ying ().
Both Chen and Ying () and our paper utilize a uniform rate matrix for its structural simplicity. Chen and Ying () applied the uniformization technique of CTMC to develop a sampling algorithm for discrete diffusion models, enabling the exact simulation of approximate reverse CTMC dynamics. In contrast, our algorithm discretizes the time to simulate the reverse process, introducing an additional discretization error term in our bound. As $h\to 0$, our sampling procedure covers the exact simulation, at which point our bound (8) degrades to the bound in terms of score error and the mixing of the forward noising process. See Table 1 for a comparison of the quantitative KL divergence bounds. However, because we discretize the approximate reverse dynamic rather than simulating it exactly, our method significantly reduces the number of function evaluations by only calling the neural network at discrete time steps $\{kh+\delta\}_{k\in[K]}$, resulting in a much faster sampling process. Moreover, we do not require additional assumptions on the score estimator, such as Assumption 2 in their paper. Furthermore, our convergence analysis is conducted in the more general $[S]^{d}$ setting, as opposed to the $\{0,1\}^{d}$ hypercube framework used in their work, making our state space setting and algorithm more broadly applicable.

###### Assumption 1 (Score estimation error) .

###### Theorem 1 .

###### Assumption 2 .

###### Theorem 2 .

###### Corollary 1 .

###### Corollary 2 .

## 6 Overview of Key Proof Techniques

We present key proof techniques for the main results given in Section 5, which characterize the discrete-time sampling process in the discrete diffusion model. Theorems 1 and 2 provide bounds for both the KL divergence and the TV distance. In this section, we focus on proving the KL bound (8), as the TV distance bound (9) follows from this KL bound via Pinsker’s inequality, plus the additional term $(1-e^{-d\delta(S-1)/S})$. The proof of the KL bound (10) follows similarly.

Let ${\mathbb{Q}}$ be the path measure of the reverse process $Y=(Y_{t})_{t\in[0,T]}$ starting from $Y_{0}\sim q_{T}$, and ${\mathbb{P}}^{\pi^{d}}$ be the path measure of the sampling process $Z=(Z_{t})_{t\in[0,T-\delta]}$ starting from $Z_{0}\sim\pi^{d}$. Recall that $q_{t}=\mathrm{Law}(Y_{T-t})$ and $p_{t}=\mathrm{Law}(Z_{t})$. Additionally, let the process $\tilde{Z}=(\tilde{Z}_{t})_{t\in[0,T-\delta]}$ be the same as $Z$ except for its initialization at $q_{T}$, and ${\mathbb{P}}^{q_{T}}$ be the path measure of $\tilde{Z}$. We visualize these three processes in Figure 1. Then by the data processing inequality and the chain rule of KL divergence, we have

$$ $\displaystyle D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})\leq D_{\mathrm{KL}}({ \mathbb{Q}}\|{\mathbb{P}}^{\pi^{d}})=D_{\mathrm{KL}}(q_{T}\|\pi^{d})+D_{ \mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}}).$ (11) $$

Therefore, it suffices to bound the two KL divergence terms in (11).

Figure: Figure 1: Illustration of the processes $Y$, $Z$ and $\tilde{Z}$. $Y$ is the true reverse process, $Z$ is the sampling process starting from the noise $\pi^{d}$, and $\tilde{Z}$ is the same as $Z$ except for the initialization. Both $Y$ and $\tilde{Z}$ start from $q_{T}$. The random variables (e.g., $Y_{t},Z_{t}$) are shown with their corresponding probability laws in parentheses (e.g., $q_{T-t},p_{t}$).
Refer to caption: x1.png

Forward Process with General $S$ States.
The term $D_{\mathrm{KL}}(q_{T}\|\pi^{d})$ represents the prior loss due to the initial distribution mismatch between $q_{T}$ and $\pi^{d}$. This can be bounded using the convergence properties of the forward process. Proposition 1 already shows that the forward process $q_{T}$ converges to $\pi^{d}$ as $T\rightarrow\infty$. We now characterize this convergence rate for general $S$ states.

###### Proposition 2 .

For the forward process marginal $q_{t}$ targeting the uniform distribution $\pi^{d}$, we have

$$ $\displaystyle D_{\mathrm{KL}}(q_{t}\|\pi^{d})\leq e^{-t}D_{\mathrm{KL}}(p_{\rm {data}}\|\pi^{d})\leq e^{-t}d\log S.$ $$

The proof of Proposition 2 is deferred to Appendix A.2. Proposition 2 demonstrates that the forward process converges exponentially to the uniform distribution $\pi^{d}$. Since $D_{\mathrm{KL}}(p_{\rm{data}}\|\pi^{d})$ can be upper bounded by $d\log S$, which is the maximum possible KL divergence between any discrete distribution and the uniform distribution over $S$ states in $d$ dimensions, this result holds irrespective of the complexity of the data distribution $p_{\rm{data}}$.

Girsanov-Based Method. The term $D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})$ is the discretization error that calculates the path measure KL divergence between the true reverse process and discretized reverse sampling process. We employ Girsanov’s theorem to explicitly express the discretization error as follows (detailed in Lemma 1 in Appendix)

$$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})=\frac{1}{S} \sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1)h+\delta}\mathbb{E}_{{\mathbf{x}}_{t} \sim q_{t}}D_{I}(s_{t}({\mathbf{x}}_{t})\|\hat{s}_{(k+1)h+\delta}({\mathbf{x}} _{t}))\,\mathrm{d}t,$ $$

where $D_{I}(s_{t}({\mathbf{x}}_{t})\|\hat{s}_{(k+1)h+\delta}({\mathbf{x}}_{t}))$ is the Bregman divergence characterizing the distance between $s_{t}$ and $\hat{s}_{(k+1)h+\delta}$, for $t\in[kh+\delta,(k+1)h+\delta]$. Since our Assumption 1 is made on the discrete points $kh+\delta,k=0,\cdots,K-1$, we further decompose the Bregman divergence into two parts:

$$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})\lesssim{}$ $\displaystyle\underbrace{\frac{C_{1}}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1 )h+\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}\|s_{t}({\mathbf{x}}_{t})-s_{ (k+1)h+\delta}({\mathbf{x}}_{t})\|_{2}^{2}\,\mathrm{d}t}_{\text{Score Movement}}$ $\displaystyle+\underbrace{\frac{C_{1}^{2}}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^ {(k+1)h+\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}D_{I}(s_{(k+1)h+\delta}( {\mathbf{x}}_{t})\|\hat{s}_{(k+1)h+\delta}({\mathbf{x}}_{t}))\,\mathrm{d}t}_{ \text{Score Error}},$ (12) $$

where the inequality holds due to the boundness of score and the property of Bregman divergence (detailed in Lemma 2 and Proposition 3 in Appendix). The score movement term in (12) represents the squared norm of the score difference $\|s_{t}({\mathbf{x}})-s_{(k+1)h+\delta}({\mathbf{x}})\|_{2}^{2}$ over the time interval $[kh+\delta,(k+1)h+\delta]$, and the score error term in (12) is naturally bounded by $C_{1}^{2}\epsilon_{\mathrm{score}}$ due to Assumption 1.

Score Movement Bound. We derive the score movement bound to quantify the change in the score function over time (detailed in Lemma 3 in Appendix). For all $k\in\{0,1,\cdots,K-1\}$, $t\in[kh+\delta,(k+1)h+\delta]$, and ${\mathbf{x}}_{t}\in{\mathcal{X}}$, we establish the following inequality:

$$ $\displaystyle\frac{1}{S}\|s_{t}({\mathbf{x}}_{t})-s_{(k+1)h+\delta}({\mathbf{x }}_{t})\|_{2}^{2}\lesssim\left[\frac{e^{-(kh+\delta)}}{(1-e^{-(kh+\delta)})^{2 }}+\frac{S}{e^{kh+\delta}-1}+1\right]^{2}dS^{2}h^{2},$ $$

which leads to the score movement term in (12) being bounded by $\delta^{-3}C_{1}dS^{2}h^{3}+C_{1}dS^{2}h^{2}T$ (detailed in Lemma 2 and the proof of Theorem 1 in Appendix), vanishing as $h$ approaches zero.

In summary, we established proof techniques for bounding (11). We demonstrated exponential convergence of the forward process to the uniform distribution, bounding the prior loss term. The Girsanov-based method was employed to analyze the discretization error, decomposing it into score movement and score error components. The derived score movement bound revealed dependencies on step size $h$, dimensionality $d$, and state space size $S$. Collectively, these techniques provide a final bound on $D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})$, offering a rigorous framework for analyzing discrete diffusion models under various parameter regimes.

###### Proposition 2 .

## 7 Conclusion and Future Work

We introduce a discrete-time sampling algorithm for the high-dimensional score-based discrete diffusion models within the CTMC framework and corresponding convergence analyses using a Girsanov-based method, similar to that in the continuous SDE setting. We study the properties of the discrete score function and incorporate them into our discretization error analysis. The convergence bounds for the sampling algorithm are nearly linear in the dimension $d$, both with and without early stopping. The bound without early stopping is related to the property of the data distribution.

The primary limitation of this work is that the discretization error in the convergence bounds of the proposed sampling algorithm becomes significant when $\delta$ is sufficiently small or when the data distribution contains extreme probability values. Hence, future work can be focused on developing refined techniques to treat the discretization error. Another important future direction will be developing accelerated algorithms with theoretical guarantees for score-based discrete diffusion models and applying our method to some more general rate matrices to obtain a tight convergence bound.

## Appendix A Main Proofs

### A.1 Proof of Proposition 1

Proof of Proposition 1.
Consider the Kolmogorov forward equation $\frac{\partial}{\partial t}P_{s,t}^{i}=P_{s,t}^{i}Q^{\mathrm{tok}}$, we obtain that $P_{s,t}^{i}=\exp\left((t-s)Q^{\mathrm{tok}}\right)$ for the CTMC $X^{i}$. Let $Q^{\mathrm{tok}}=P\Lambda P^{-1}$ be the eigendecomposition of $Q^{\mathrm{tok}}$ with

$$ $\begin{array}[]{cc}P=\begin{pmatrix}-1&-1&\cdots&-1&1\\ 1&0&\cdots&0&1\\ 0&1&\cdots&0&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&1\end{pmatrix},&P^{-1}=\displaystyle\frac{1}{S}\begin{pmatrix}-1& S-1&\cdots&-1&-1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ -1&-1&\cdots&S-1&-1\\ -1&-1&\cdots&-1&S-1\\ 1&1&\cdots&1&1\end{pmatrix}\end{array},$ $$

and $\Lambda=\operatorname{diag}\{-1,\cdots,-1,0\}$. Then it can be easily verified that

$$ $P_{s,t}^{0}=\exp\left((t-s)Q^{\mathrm{tok}}\right)=P\exp\left((t-s)\Lambda \right)P^{-1}=\frac{1}{S}\left[(1-e^{-(t-s)})\mathbf{1}\mathbf{1}^{\top}+Se^{- (t-s)}I_{S}\right].$ $$

Also, the Kolmogorov forward equation $\frac{\partial}{\partial t}P_{s,t}=P_{s,t}Q$ yields $P_{s,t}=\exp((t-s)Q)$. By utilizing the Kronecker-product structure of $Q$, we can write the rate

$$ $Q=\bigoplus_{k=1}^{d}Q^{\mathrm{tok}}=\sum_{k=1}^{d}I_{S}^{\otimes(k-1)} \otimes Q^{\mathrm{tok}}\otimes I_{S}^{\otimes(d-k)},$ $$

where $\oplus$ denotes the Kronecker sum. Then

$$ $\displaystyle P_{s,t}=\exp((t-s)Q)=\exp\left(\bigoplus_{k=1}^{d}(t-s)Q^{ \mathrm{tok}}\right)=\left(\exp\left((t-s)Q^{\mathrm{tok}}\right)\right)^{ \otimes d}=\left(P_{s,t}^{0}\right)^{\otimes d}.$ $$

Thus, by the Kolmogorov forward equation $\frac{\mathrm{d}}{\mathrm{d}t}q_{t}=Q^{\top}q_{t}$ we have

$$ $q_{t}=\exp(tQ)\cdot p_{\rm{data}}=\exp\left(tQ^{\mathrm{tok}}\right)^{\otimes d }\cdot p_{\rm{data}}=\left[\frac{1}{S}(1-e^{-t})\mathbf{1}_{S}\mathbf{1}_{S}^{ \top}+e^{-t}I_{S}\right]^{\otimes d}\cdot p_{\rm{data}}.$ $$

$\hfill\square$

### A.2 Proof of Proposition 2

Proof of Proposition 2.
For the first inequality, we prove that the forward CTMC with generator matrix $Q$ and stationary distribution $\pi^{d}$ satisfies a modified log-Sobolev inequality (MLSI) with constant $C_{\mathrm{LSI}}=2$:

$$ $\operatorname{Ent}_{\pi^{d}}[f]\leq\frac{C_{\mathrm{LSI}}}{2}{\mathcal{E}}(f, \log f)\quad\text{for all function}\ f:{\mathcal{X}}\to\mathbb{R}_{+},$ (13) $$

where the entropy is

$$ $\operatorname{Ent}_{\pi^{d}}[f]=\mathbb{E}_{\pi^{d}}[f\log f]-\mathbb{E}_{\pi^ {d}}[f]\log(\mathbb{E}_{\pi^{d}}[f])$ $$

for a function $f:{\mathcal{X}}\to\mathbb{R}_{+}$, and the associated Dirichlet form is

$$ $\displaystyle{\mathcal{E}}(f,g)={}$ $\displaystyle-\int_{{\mathcal{X}}}f({\mathbf{x}})\sum_{{\mathbf{y}}\in{ \mathcal{X}}}Q({\mathbf{x}},{\mathbf{y}})g({\mathbf{y}})\,\mathrm{d}\pi^{d}({ \mathbf{x}})$ $\displaystyle={}$ $\displaystyle\frac{1}{2}\sum_{{\mathbf{x}},{\mathbf{y}}\in{\mathcal{X}}}(f({ \mathbf{x}})-f({\mathbf{y}}))(g({\mathbf{x}})-g({\mathbf{y}}))Q({\mathbf{x}},{ \mathbf{y}})\pi^{d}({\mathbf{x}})$ $$

for two functions $f,g:{\mathcal{X}}\to\mathbb{R}$. With the sparse structure of $Q$, we can further write out that

$$ ${\mathcal{E}}(f,\log f)=\frac{1}{2S}\mathbb{E}_{{\mathbf{x}}\sim\pi^{d}}\sum_{ i=1}^{d}\sum_{\hat{x}^{i}=1}^{d}(f({\mathbf{x}})-f({\mathbf{x}}^{\backslash i} \odot\hat{x}^{i}))(\log f({\mathbf{x}})-\log f({\mathbf{x}}^{\backslash i} \odot\hat{x}^{i}))$ $$

for some function $f:{\mathcal{X}}\to\mathbb{R}_{+}$. We now use the subadditivity of entropy and tensorization property of log-Sobolev constants to prove (13), and we will see that it is sufficient to show that the CTMC on $[S]$ with generator matrix $Q^{\mathrm{tok}}$ and stationary distribution $\pi=\frac{1}{S}\mathbf{1}_{S}$ satisfies MLSI with constant $C_{\mathrm{LSI}}=2$. First, Boucheron et al. (, Theorem 4.10) implies the subadditivity of entropy that

$$ $\operatorname{Ent}_{\pi^{d}}[f]\leq\mathbb{E}_{{\mathbf{x}}^{\backslash i}\sim \pi^{\otimes(d-1)}}\sum_{i=1}^{d}\operatorname{Ent}_{\pi}^{(i)}[f],$ $$

where $\operatorname{Ent}_{\pi}^{(i)}[f]=\mathbb{E}_{x^{i}\sim\pi}[f\log f]-\mathbb{E
}_{x^{i}\sim\pi}[f]\log\mathbb{E}_{x^{i}\sim\pi}[f]$. Hence, it suffices to show that for all $i\in[d]$,

$$ $\operatorname{Ent}_{\pi}^{(i)}[f]\leq\frac{C_{\mathrm{LSI}}}{4}\mathbb{E}_{x^{ i}\sim\pi}\sum_{\hat{x}^{i}=1}^{S}(f({\mathbf{x}})-f({\mathbf{x}}^{\backslash i }\odot\hat{x}^{i}))(\log f({\mathbf{x}})-\log f({\mathbf{x}}^{\backslash i} \odot\hat{x}^{i})).$ (14) $$

Given any fixed realization of ${\mathbf{x}}^{\backslash i}$, $f({\mathbf{x}})$ can take $S$ different values with equal probability $\frac{1}{S}$, and we call these values $a_{1},\cdots,a_{S}>0$. Then the desired inequality (14) is of the form

$$ $\sum_{i=1}^{S}\frac{a_{i}}{S}\log a_{i}-\left(\sum_{i=1}^{S}\frac{a_{i}}{S} \right)\log\sum_{i=1}^{S}\frac{a_{i}}{S}\leq\frac{C_{\mathrm{LSI}}}{4S^{2}} \sum_{i,j=1}^{S}(a_{i}-a_{j})(\log a_{i}-\log a_{j}).$ $$

Thus, it remains to prove that this elementary inequality holds for all $a_{1},\cdots,a_{S}>0$, which can be easily verified by plugging $C_{\mathrm{LSI}}=2$ and the concavity of logarithmic function.

To conclude, the MLSI (13) implies the exponential mixing of the forward process in KL divergence (see, e.g., Bobkov and Tetali (, Theorem 2.4), Chewi (, Theorem 1.2.25)):

$$ $D_{\mathrm{KL}}(q_{t}\|\pi^{d})\leq\exp\left(-\frac{2t}{C_{\mathrm{LSI}}} \right)D_{\mathrm{KL}}(p_{\rm{data}}\|\pi^{d})=e^{-t}D_{\mathrm{KL}}(p_{\rm{ data}}\|\pi^{d}).$ $$

The second inequality is because

$$ $\displaystyle D_{\mathrm{KL}}(p_{\rm{data}}\|\pi^{d})=\sum_{{\mathbf{x}}\in{ \mathcal{X}}}p_{\rm{data}}({\mathbf{x}})\log\frac{p_{\rm{data}}({\mathbf{x}})} {S^{-d}}=\sum_{{\mathbf{x}}\in{\mathcal{X}}}p_{\rm{data}}({\mathbf{x}})\log p_ {\rm{data}}({\mathbf{x}})+d\log S\leq d\log S.$ $$

$\hfill\square$

### A.3 Proof of Theorem 1

To prove Theorem 1, we state the following lemmas. Their proofs are provided in Appendix B.

###### Lemma 1 .

The KL divergence between the true and approximate path measures of the reverse process both starting from $q_{T}$ is

$$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})=\sum_{k=0}^{ K-1}\int_{kh+\delta}^{(k+1)h+\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}} \sum_{i=1}^{d}\sum_{\hat{x}_{t}^{i}\neq x_{t}^{i}}Q_{t}^{\mathrm{tok}}(\hat{x} _{t}^{i},x_{t}^{i})D_{I}(s_{t}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}}\|\hat{s}_ {(k+1)h+\delta}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}})\,\mathrm{d}t.$ $$

Lemma 1 is the key lemma to our analysis, allowing us to explicitly express the path measure KL divergence.

###### Lemma 2 (Score bound) .

Let $\delta>0$. For all $t\in[\delta,T]$, ${\mathbf{x}}\in{\mathcal{X}}$, $i\in[d]$ and $\hat{x}^{i}\neq x^{i}$, we have

$$ $\displaystyle s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}\leq 1+\frac{S}{e^{t}-1}\leq 1 +\frac{S}{e^{\delta}-1}.$ $$

###### Lemma 3 (Score movement bound) .

For all $k\in\{0,1,\cdots,K-1\}$, $t\in[kh+\delta,(k+1)h+\delta]$, ${\mathbf{x}}\in{\mathcal{X}}$ and $\hat{x}^{i}\neq x^{i}\in[S]$, we have

$$ $\displaystyle|s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}-s_{(k+1)h+\delta}({\mathbf{x }})_{i,\hat{x}^{i}}|\lesssim\left[\frac{e^{-(kh+\delta)}}{(1-e^{-(kh+\delta)}) ^{2}}+\frac{S}{e^{kh+\delta}-1}+1\right]Sh.$ $$

Proof of Theorem 1.
Recall that ${\mathbb{Q}}$ is the path measure of the true reverse process $Y=(Y_{t})_{t\in[0,T]}$ starting from $Y_{0}\sim q_{T}$, and ${\mathbb{P}}^{\pi^{d}}$ is the path measure of the sampling process $Z=(Z_{t})_{t\in[0,T-\delta]}$ starting from $Z_{0}\sim\pi^{d}$. $Z$ is a CTMC with rate matrix $\hat{Q}^{\leftarrow}_{t}$, where the non-zero off-diagonal entries are defined by

$$ $\hat{Q}^{\leftarrow}_{t}({\mathbf{x}},{\mathbf{x}}^{\backslash i}\odot\hat{x}^ {i})=\frac{1}{S}\hat{s}_{T-[\frac{t}{h}]h}({\mathbf{x}})_{i,\hat{x}^{i}}\quad \text{for}\ \hat{x}^{i}\neq x^{i}.$ $$

Then $\tilde{Z}=(\tilde{Z}_{t})_{t\in[0,T-\delta]}$ is a CTMC with rate matrix $\hat{Q}^{\leftarrow}_{t}$ starting from $\tilde{Z}_{0}\sim q_{T}$ with path measure ${\mathbb{P}}^{q_{T}}$. By the data processing inequality, we have the estimate

$$ $\displaystyle D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})\leq{}D_{\mathrm{KL}}({ \mathbb{Q}}\|{\mathbb{P}}^{\pi^{d}})={}$ $\displaystyle\mathbb{E}_{Y\sim{\mathbb{Q}}}\log\left(\frac{\mathrm{d}{\mathbb{ Q}}}{\mathrm{d}{\mathbb{P}}^{q_{T}}}(Y)\frac{\mathrm{d}{\mathbb{P}}^{q_{T}}}{ \mathrm{d}{\mathbb{P}}^{\pi^{d}}}(Y)\right)$ $\displaystyle={}$ $\displaystyle\mathbb{E}_{Y\sim{\mathbb{Q}}}\log\left(\frac{\mathrm{d}{\mathbb{ Q}}}{\mathrm{d}{\mathbb{P}}^{q_{T}}}(Y)\frac{\mathrm{d}q_{T}}{\mathrm{d}\pi^{d }}(Y_{0})\right)$ $\displaystyle={}$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})+D_{\mathrm{ KL}}(q_{T}\|\pi^{d}),$ (15) $$

where the second to last equality holds since the only difference between the two path measures ${\mathbb{P}}^{q_{T}}$ and ${\mathbb{P}}^{\pi^{d}}$ is the initial distribution for a path $Y$. We respectively bound the two terms in (15). The second term is bounded by Proposition 2. We next combine Lemmas 1, 2, and 3, Assumption 1 and Proposition 3 to bound the first term in (15). By choosing

$$ $C_{1}=\max\left\{1+\frac{S}{e^{\delta}-1},\max_{{\mathbf{x}}\in{\mathcal{X}},k \in\{0,\cdots,K-1\}}\|\hat{s}_{(k+1)h+\delta}({\mathbf{x}})\|_{\infty}\right\},$ $$

we have

$$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1)h+\delta} \mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}D_{I}(s_{t}({\mathbf{x}}_{t})\|\hat{s}_ {(k+1)h+\delta}({\mathbf{x}}_{t}))\,\mathrm{d}t$ $\displaystyle\lesssim{}$ $\displaystyle\frac{C_{1}}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1)h+\delta} \mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}\|s_{t}({\mathbf{x}}_{t})-s_{(k+1)h+ \delta}({\mathbf{x}}_{t})\|_{2}^{2}\,\mathrm{d}t$ $\displaystyle+\frac{C_{1}^{2}}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1)h+ \delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}D_{I}(s_{(k+1)h+\delta}({\mathbf {x}}_{t})\|\hat{s}_{(k+1)h+\delta}({\mathbf{x}}_{t}))\,\mathrm{d}t$ $\displaystyle\lesssim{}$ $\displaystyle\frac{C_{1}}{S}\sum_{k=0}^{K-1}\left[\frac{e^{-(kh+\delta)}}{(1-e ^{-(kh+\delta)})^{2}}+\frac{S}{e^{kh+\delta}-1}+1\right]^{2}dS^{3}h^{3}+C_{1}^ {2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle C_{1}\sum_{k=0}^{K-1}\left[\frac{e^{-2(kh+\delta)}}{(1-e^{-(kh+ \delta)})^{4}}+\left(\frac{S}{e^{kh+\delta}-1}\right)^{2}+1\right]dS^{2}h^{3}+ C_{1}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle C_{1}dS^{2}h^{3}\int_{\delta}^{T}\left[\frac{e^{-2x}}{(1-e^{-x}) ^{4}}+\frac{S^{2}}{e^{x}-1}\right]\,\mathrm{d}x+C_{1}dS^{2}h^{2}T+C_{1}^{2}{ \epsilon}_{\mathrm{score}}$ $\displaystyle\leq{}$ $\displaystyle\left[(e^{\delta}-1)^{-3}+(\delta-\log(e^{\delta}-1))S^{2}\right] C_{1}dS^{2}h^{3}+C_{1}dS^{2}h^{2}T+C_{1}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\leq{}$ $\displaystyle\left[\delta^{-3}+\left(\delta+\log(1/\delta)\right)S^{2}\right]C _{1}dS^{2}h^{3}+C_{1}dS^{2}h^{2}T+C_{1}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle\delta^{-3}C_{1}dS^{2}h^{3}+C_{1}dS^{2}h^{2}T+C_{1}^{2}{\epsilon} _{\mathrm{score}}.$ (16) $$

The first equality follows from Lemma 1. The first inequality is a consequence of Lemma 2 and Proposition 3. Lemma 3 and Assumption 1 lead to the second inequality. The third inequality stems from $(a+b+c)^{2}\leq 3(a^{2}+b^{2}+c^{2})$. The second last inequality utilizes the fact that $e^{x}-1\geq x$. For the final inequality, we employ $\delta=\tilde{O}(S^{-\frac{2}{3}})$ and note that $\delta^{-3}+\log(1/\delta)S^{2}=O(\delta^{-3})$ as $\delta\to 0^{+}$. Lastly, combining (15), (16), and Proposition 2 yields the KL divergence bound (8).

As for the TV distance bound (9), it is a similar proof to that of Theorem 6(2) in Chen and Ying (). By the definition of TV distance and the uniformization of CTMC (Chen and Ying, , Proposition 1), we have

$$ $\displaystyle D_{\mathrm{TV}}(p_{\rm{data}},q_{\delta})$ $\displaystyle\leq\mathbb{P}(X_{0}\neq X_{\delta})$ $\displaystyle\leq\mathbb{P}(\text{'A Poisson$(d(S-1)\delta/S)$ random variable is non-zero'})$ (17) $\displaystyle=1-e^{-d(S-1)\delta/S}.$ $$

Then by the triangle inequality, Pinsker’s inequality and inequality (8), we have

$$ $\displaystyle D_{\mathrm{TV}}(p_{\rm{data}},p_{T-\delta})$ $\displaystyle\leq D_{\mathrm{TV}}(q_{\delta},p_{T-\delta})+D_{\mathrm{TV}}(p_{ \rm{data}},q_{\delta})$ $\displaystyle\leq\sqrt{\frac{1}{2}D_{\mathrm{KL}}(q_{\delta}\|p_{T-\delta})}+( 1-e^{-d(S-1)\delta/S})$ $\displaystyle\lesssim\sqrt{de^{-T}\log S+\delta^{-3}C_{1}S^{2}h^{3}d+C_{1}S^{2 }h^{2}dT+C_{1}^{2}{\epsilon}_{\mathrm{score}}}+(1-e^{-d(S-1)\delta/S}).$ $$

We conclude the proof of Theorem 1.
$\hfill\square$

###### Lemma 1 .

###### Lemma 2 (Score bound) .

###### Lemma 3 (Score movement bound) .

### A.4 Proof of Theorem 2

The proof of Theorem 2 is similar to that of Theorem 1. Note that the decomposition (15) and the equation for path measure KL divergence in Lemma 1 still hold for $\delta=0$. It suffices to bound the first term of (15). We need the following lemmas. Proofs of Lemmas 4 and 5 are provided in Appendix B.

###### Lemma 4 (Score bound) .

Suppose Assumption 2 holds. Let $\delta=0$. Then for all $t\in[0,T]$, ${\mathbf{x}}\in{\mathcal{X}}$, $i\in[d]$ and $\hat{x}^{i}\neq x^{i}\in[S]$, we have

$$ $\displaystyle s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}\leq L.$ $$

###### Lemma 5 (Score movement bound) .

Suppose Assumption 2 holds. Let $\delta=0$. Then for all $k\in\{0,1,\cdots,K-1\}$, $t\in[kh,(k+1)h]$, ${\mathbf{x}}\in{\mathcal{X}}$, $i\in[d]$, and $\hat{x}^{i}\neq x^{i}\in[S]$, we have

$$ $\displaystyle|s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}-s_{(k+1)h}({\mathbf{x}})_{i, \hat{x}^{i}}|\lesssim\left[\frac{1}{1-e^{-(k+1)h}}+S\right]\kappa_{i}h.$ $$

We then combine Lemmas 1, 4, and 5, Assumption 1 and Proposition 3 with $\delta=0$. By choosing

$$ $C_{2}=\max\left\{L,\max_{{\mathbf{x}}\in{\mathcal{X}},k\in\{0,\cdots,K-1\}}\| \hat{s}_{(k+1)h}({\mathbf{x}})\|_{\infty}\right\},$ $$

we have

$$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_{{\mathbf {x}}_{t}\sim q_{t}}D_{I}(s_{t}({\mathbf{x}}_{t})\|\hat{s}_{(k+1)h}({\mathbf{x} }_{t}))\,\mathrm{d}t$ $\displaystyle\lesssim{}$ $\displaystyle\frac{C_{2}}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_{{ \mathbf{x}}_{t}\sim q_{t}}\|s_{t}({\mathbf{x}}_{t})-s_{(k+1)h}({\mathbf{x}}_{t })\|_{2}^{2}\,\mathrm{d}t$ $\displaystyle+\frac{C_{2}^{2}}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_ {{\mathbf{x}}_{t}\sim q_{t}}D_{I}(s_{(k+1)h}({\mathbf{x}}_{t})\|\hat{s}_{(k+1) h}({\mathbf{x}}_{t}))\,\mathrm{d}t$ $\displaystyle\leq{}$ $\displaystyle\frac{C_{2}}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_{{ \mathbf{x}}_{t}\sim q_{t}}\sum_{i=1}^{d}\sum_{\hat{x}^{i}\neq x^{i}}|s_{t}({ \mathbf{x}}_{t})_{i,\hat{x}^{i}}-s_{(k+1)h}({\mathbf{x}}_{t})_{i,\hat{x}^{i}}| ^{2}\,\mathrm{d}t+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle\frac{C_{2}}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_{{ \mathbf{x}}_{t}\sim q_{t}}\sum_{i=1}^{d}\sum_{\hat{x}^{i}\neq x^{i}}\left[ \frac{1}{1-e^{-(k+1)h}}+S\right]^{2}\kappa_{i}^{2}h^{2}\,\mathrm{d}t+C_{2}^{2} {\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle C_{2}\sum_{k=0}^{K-1}\sum_{i=1}^{d}\left[\frac{1}{(1-e^{-(k+1)h} )^{2}}+S^{2}\right]\kappa_{i}^{2}h^{3}+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle={}$ $\displaystyle C_{2}\kappa^{2}\sum_{k=0}^{K-1}\frac{1}{(1-e^{-(k+1)h})^{2}}h^{3 }+C_{2}\kappa^{2}S^{2}h^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle C_{2}\kappa^{2}h^{3}\int_{h}^{T}\frac{1}{(1-e^{-x})^{2}}\, \mathrm{d}x+C_{2}\kappa^{2}S^{2}h^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\leq{}$ $\displaystyle C_{2}\kappa^{2}h^{3}\left[T-\log(e^{h}-1)+\frac{1}{e^{h}-1} \right]+C_{2}\kappa^{2}S^{2}h^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\overset{(i)}{\leq}{}$ $\displaystyle C_{2}\kappa^{2}h^{3}\left[T-\log h+\frac{1}{h}\right]+C_{2} \kappa^{2}S^{2}h^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle C_{2}\kappa^{2}h^{3}\left[T+\frac{1}{h}\right]+C_{2}\kappa^{2}S^ {2}h^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}}$ $\displaystyle\lesssim{}$ $\displaystyle C_{2}\kappa^{2}h^{2}T\left[h+S^{2}\right]+C_{2}^{2}{\epsilon}_{ \mathrm{score}}$ $\displaystyle\overset{(ii)}{\lesssim}{}$ $\displaystyle C_{2}\kappa^{2}h^{2}S^{2}T+C_{2}^{2}{\epsilon}_{\mathrm{score}}.$ (18) $$

The first equality follows from Lemma 1. Lemma 4 and Proposition 3 lead to the first inequality. Assumption 1 gives rise to the second inequality, while Lemma 5 yields the third. The fourth inequality stems from the fact that $(a+b)^{2}\leq 2(a^{2}+b^{2})$. Inequality $(i)$ is a consequence of $e^{x}-1\geq x$, and $(ii)$ results from the assumption that $h\leq S^{2}$.

Then Theorem 2 follows from (15), (18) and Proposition 2. $\hfill\square$

Discussion on $C_{1}$ and $C_{2}$.
Since we have access to uniform bounds for the true score functions from Lemmas 2 and 4, which depend on either $\delta$ and $S$, or $L$, we can apply score clipping during training to ensure that the learned score functions are reliable. Specifically, we enforce the following conditions:

$$ $\max_{{\mathbf{x}}\in{\mathcal{X}},\,k\in\{0,\dots,K-1\}}\|\hat{s}_{(k+1)h+ \delta}({\mathbf{x}})\|_{\infty}\leq\frac{3}{2}\left(1+\frac{S}{e^{\delta}-1} \right)\leq\frac{3S}{\delta},\ \text{for a small $\delta$.}$ $$

and

$$ $\max_{{\mathbf{x}}\in{\mathcal{X}},\,k\in\{0,\dots,K-1\}}\|\hat{s}_{(k+1)h}({ \mathbf{x}})\|_{\infty}\leq\frac{3}{2}L.$ $$

As a result, we can choose that $C_{1}=\frac{3S}{\delta}$ and $C_{2}=\frac{3}{2}L$.

###### Lemma 4 (Score bound) .

###### Lemma 5 (Score movement bound) .

## Appendix B Omitted Proofs in Appendix A

### B.1 Proof of Lemma 1

To prove Lemma 1, we need the following generalized Girsanov’s theorem and Dynkin’s formula, as stated below. For related definitions and details regarding the notations used in Theorem 3 and Lemma 6, we refer readers to the work of Benton et al. ().

###### Theorem 3 (Girsanov, (Benton et al., 2024b , Theorem 6) ) .

Let $\bar{Y}=(Y_{t},t)_{t\geq 0}$ and $\bar{Z}=(Z_{t},t)_{t\geq 0}$ be Feller processes on ${\mathcal{S}}$ with generators ${\mathcal{L}},{\mathcal{M}}$ and path measures $\bar{{\mathbb{Q}}},\bar{{\mathbb{P}}}$ respectively, such that $Y_{0}$ and $Z_{0}$ have the same law. Suppose that there exists a bounded, measurable function $\alpha:{\mathcal{S}}\to(0,+\infty)$ such that $\alpha^{-1}{\mathcal{L}}\alpha$ is bounded, and such that

$$ $\alpha{\mathcal{M}}f={\mathcal{L}}(f\alpha)-f{\mathcal{L}}\alpha$ (19) $$

for all proper functions $f$ (assume that all the involved functions are well-defined). Then we have

$$ $\frac{\mathrm{d}\bar{{\mathbb{P}}}}{\mathrm{d}\bar{{\mathbb{Q}}}}(\omega)= \frac{\alpha(\omega_{T},T)}{\alpha(\omega_{0},0)}\exp\left\{-\int_{0}^{T}\frac {{\mathcal{L}}\alpha(\omega_{s},s)}{\alpha(\omega_{s},s)}\,\mathrm{d}s\right\}.$ $$

###### Lemma 6 (Dynkin’s formula, (Dong, 2003 , Theorem 27.20) ) .

If $\bar{Y}=(Y_{t},t)_{t\geq 0}$ is a Feller process on ${\mathcal{S}}$ with generator ${\mathcal{L}}$ and $f$ is a proper function on ${\mathcal{S}}$ (assume that all the involved functions are well-defined), then

$$ $M_{t}^{f}=f(Y_{t},t)-f(Y_{0},0)-\int_{0}^{t}{\mathcal{L}}f(Y_{s},s)\,\mathrm{d}s$ $$

is a martingale with respect to the natural filtration of $\bar{Y}$.

Proof of Lemma 1.
Recall that $Y=(Y_{t})_{t\in[0,T]}$ is the true time reversal CTMC with generator $Q^{\leftarrow}_{t}$, and $Z=(Z_{t})_{t\in[0,T]}$ is the sampling CTMC with generator $\hat{Q}^{\leftarrow}_{t}$, both initiating from $q_{T}$; the rate matrices are of the forms

$$ $Q^{\leftarrow}_{t}({\mathbf{x}},{\mathbf{x}}^{\backslash i}\odot\hat{x}^{i})= \frac{1}{S}s_{T-t}({\mathbf{x}})_{i,\hat{x}^{i}}\quad\text{and}\quad\hat{Q}^{ \leftarrow}_{t}({\mathbf{x}},{\mathbf{x}}^{\backslash i}\odot\hat{x}^{i})= \frac{1}{S}\hat{s}_{T-[\frac{t}{h}]h}({\mathbf{x}})_{i,\hat{x}^{i}}\quad\text{ for}\ x^{i}\neq\hat{x}^{i}.$ $$

Since the processes $Y$ and $Z$ on ${\mathcal{X}}$ are time-inhomogeneous, motivated by Benton et al. (), we consider Feller processes $\bar{Y},\bar{Z}$ defined on the extended space ${\mathcal{S}}={\mathcal{X}}\times[0,+\infty)$ which are constructed by setting $Y_{t}=Y_{T}$ and $Z_{t}=Z_{T}$ for $t\geq T$ and letting $\bar{Y}=(Y_{t},t)_{t\geq 0}$ and $\bar{Z}=(Z_{t},t)_{t\geq 0}$, which are time-homogeneous. For more related details on the Feller process and stochastic analysis, we refer readers to the work of Benton et al. ().

We can now apply Theorem 3 with ${\mathcal{L}}=\partial_{t}+\hat{{\mathcal{L}}}$ and ${\mathcal{M}}=\partial_{t}+\hat{{\mathcal{M}}}$, where $\hat{{\mathcal{L}}}$ and $\hat{{\mathcal{M}}}$ are the generators of the CTMCs $Y$ and $Z$ respectively, the condition (19) has the form

$$ $\alpha\hat{{\mathcal{M}}}f=\hat{{\mathcal{L}}}(f\alpha)-f\hat{{\mathcal{L}}}\alpha,$ $$

and it follows that

$$ $\alpha({\mathbf{x}},t)\sum_{{\mathbf{z}}\in{\mathcal{X}}}\hat{Q}^{\leftarrow}_ {t}({\mathbf{x}},{\mathbf{z}})f({\mathbf{z}})=\sum_{{\mathbf{z}}\in{\mathcal{X }}}Q^{\leftarrow}_{t}({\mathbf{x}},{\mathbf{z}})\alpha({\mathbf{z}},t)f({ \mathbf{z}})-f({\mathbf{x}})\sum_{{\mathbf{z}}\in{\mathcal{X}}}Q^{\leftarrow}_ {t}({\mathbf{x}},{\mathbf{z}})\alpha({\mathbf{z}},t)$ $$

for all ${\mathbf{x}}\in{\mathcal{X}}$. By taking ${\mathbf{y}}={\mathbf{x}}^{\backslash i}\odot\hat{x}^{i}\ (\hat{x}^{i}\neq x^{
i})$ and $f({\mathbf{z}})=\mathbf{1}\{{\mathbf{z}}={\mathbf{y}}\}$, we have

$$ $\alpha({\mathbf{x}},t)\hat{s}_{T-[\frac{t}{h}]h}({\mathbf{x}})_{i,\hat{x}^{i}} =\alpha({\mathbf{y}},t)s_{T-t}({\mathbf{x}})_{i,\hat{x}^{i}}\quad\text{for all }\ i\in[d]\ \text{and}\ \hat{x}^{i}\neq x^{i}.$ $$

Thus, in order for (19) to hold, it is required that

$$ $s_{T-t}({\mathbf{x}})_{i,\hat{x}^{i}}=\frac{\alpha({\mathbf{x}},t)}{\alpha({ \mathbf{x}}^{\backslash i}\odot\hat{x}^{i},t)}\hat{s}_{T-[\frac{t}{h}]h}({ \mathbf{x}})_{i,\hat{x}^{i}}\quad\text{for all}\ i\in[d]\ \text{and}\ \hat{x}^ {i}\neq x^{i}.$ (20) $$

It also can be easily verified that this it is sufficient for (19) to hold
for a given $\alpha$. Let $\bar{{\mathbb{Q}}}$ and $\bar{{\mathbb{P}}}$ be the path measures of $\bar{Y}$ and $\bar{Z}$ respectively. Then with function $\alpha({\mathbf{x}},t)$ satisfying (20), Theorem 3 yields that

$$ $\frac{\mathrm{d}\bar{{\mathbb{P}}}}{\mathrm{d}\bar{{\mathbb{Q}}}}(Y)=\frac{ \alpha(Y_{T-\delta},T-\delta)}{\alpha(Y_{0},0)}\exp\left\{-\int_{0}^{T-\delta} \alpha(Y_{s},s)^{-1}{\mathcal{L}}\alpha(Y_{s},s)\,\mathrm{d}s\right\}.$ (21) $$

By taking $f=\log\alpha$ in Lemma 6, we know that

$$ $M_{t}^{f}:=\log\frac{\alpha(Y_{t},t)}{\alpha(Y_{0},0)}-\int_{0}^{t}{\mathcal{L }}\log\alpha(Y_{s},s)\,\mathrm{d}s$ $$

is a $\bar{{\mathbb{Q}}}$-martingale.
Then by taking logarithms in (21), it follows that

$$ $\displaystyle\log\frac{\mathrm{d}\bar{{\mathbb{P}}}}{\mathrm{d}\bar{{\mathbb{Q }}}}(Y)$ $\displaystyle={}$ $\displaystyle\int_{0}^{T-\delta}\left[{\mathcal{L}}\log\alpha(Y_{s},s)-\frac{{ \mathcal{L}}\alpha(Y_{s},s)}{\alpha(Y_{s},s)}\right]\mathrm{d}s+M_{T-\delta}^{f}$ $\displaystyle={}$ $\displaystyle\int_{0}^{T-\delta}\left[\left[\partial_{t}\log\alpha(Y_{s},s)+ \hat{{\mathcal{L}}}\log\alpha(Y_{s},s)\right]-\left[\frac{\partial_{t}\alpha(Y _{s},s)}{\alpha(Y_{s},s)}+\frac{\hat{{\mathcal{L}}}\alpha(Y_{s},s)}{\alpha(Y_{ s},s)}\right]\right]\mathrm{d}s+M_{T-\delta}^{f}$ $\displaystyle={}$ $\displaystyle\int_{0}^{T-\delta}\left[\hat{{\mathcal{L}}}\log\alpha(Y_{s},s)- \frac{\hat{{\mathcal{L}}}\alpha(Y_{s},s)}{\alpha(Y_{s},s)}\right]\mathrm{d}s+M _{T-\delta}^{f}.$ $$

Taking expectation above yields that

$$ $\displaystyle D_{\mathrm{KL}}({\mathbb{Q}}\|{\mathbb{P}}^{q_{T}})=D_{\mathrm{ KL}}(\bar{{\mathbb{Q}}}\|\bar{{\mathbb{P}}})=\mathbb{E}_{\bar{{\mathbb{Q}}}} \log\frac{\mathrm{d}\bar{{\mathbb{Q}}}}{\mathrm{d}\bar{{\mathbb{P}}}}$ $\displaystyle={}$ $\displaystyle\mathbb{E}_{\bar{{\mathbb{Q}}}}\int_{0}^{T-\delta}\left[\frac{ \hat{{\mathcal{L}}}\alpha(Y_{s},s)}{\alpha(Y_{s},s)}-\hat{{\mathcal{L}}}\log \alpha(Y_{s},s)\right]\mathrm{d}s+\mathbb{E}_{\bar{{\mathbb{Q}}}}M_{T-\delta}^ {f}$ $\displaystyle={}$ $\displaystyle\int_{0}^{T-\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{T-t}}\left [\frac{\hat{{\mathcal{L}}}\alpha({\mathbf{x}}_{t},t)}{\alpha({\mathbf{x}}_{t}, t)}-\hat{{\mathcal{L}}}\log\alpha({\mathbf{x}}_{t},t)\right]\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\int_{0}^{T-\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{T-t}}\left [\sum_{{\mathbf{y}}\in{\mathcal{X}}}\left\{Q^{\leftarrow}_{t}({\mathbf{x}}_{t} ,{\mathbf{y}})\frac{\alpha({\mathbf{y}},t)}{\alpha({\mathbf{x}}_{t},t)}-Q^{ \leftarrow}_{t}({\mathbf{x}}_{t},{\mathbf{y}})\log\frac{\alpha({\mathbf{y}},t) }{\alpha({\mathbf{x}}_{t},t)}\right\}\right]\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\int_{0}^{T-\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_{T-t}}\left [Q^{\leftarrow}_{t}({\mathbf{x}}_{t},{\mathbf{x}}_{t})+\sum_{{\mathbf{y}}\neq{ \mathbf{x}}_{t}}Q^{\leftarrow}_{t}({\mathbf{x}}_{t},{\mathbf{y}})\frac{\alpha( {\mathbf{y}},t)}{\alpha({\mathbf{x}}_{t},t)}+\sum_{{\mathbf{y}}\neq{\mathbf{x} }_{t}}Q^{\leftarrow}_{t}({\mathbf{x}}_{t},{\mathbf{y}})\log\frac{\alpha({ \mathbf{x}}_{t},t)}{\alpha({\mathbf{y}},t)}\right]\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\int_{0}^{T-\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_ {T-t}}\sum_{i=1}^{d}\sum_{\hat{x}_{t}^{i}\neq x_{t}^{i}}\Bigg{[}-s_{T-t}({ \mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}}+\hat{s}_{T-[\frac{t}{h}]h}({\mathbf{x}}_{ t})_{i,\hat{x}_{t}^{i}}$ $\displaystyle\hskip 170.71652pt+s_{T-t}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}} \log\frac{s_{T-t}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}}}{\hat{s}_{T-[\frac{t}{ h}]h}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}}}\Bigg{]}\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\int_{0}^{T-\delta}\mathbb{E}_{{\mathbf{x}}_{t}\sim q_ {T-t}}\sum_{i=1}^{d}\sum_{\hat{x}_{t}^{i}\neq x_{t}^{i}}D_{I}(s_{T-t}({\mathbf {x}}_{t})_{i,\hat{x}_{t}^{i}}\|\hat{s}_{T-[\frac{t}{h}]h}({\mathbf{x}}_{t})_{i ,\hat{x}_{t}^{i}})\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_{{\mathbf {x}}_{t}\sim q_{T-t}}\sum_{i=1}^{d}\sum_{\hat{x}_{t}^{i}\neq x_{t}^{i}}D_{I}(s _{T-t}({\mathbf{x}}_{t})_{i,\hat{x}_{t}^{i}}\|\hat{s}_{T-kh}({\mathbf{x}}_{t}) _{i,\hat{x}_{t}^{i}})\,\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\sum_{k=0}^{K-1}\int_{kh}^{(k+1)h}\mathbb{E}_{{\mathbf {x}}_{t}\sim q_{T-t}}D_{I}(s_{T-t}({\mathbf{x}}_{t})\|\hat{s}_{T-kh}({\mathbf{ x}}_{t}))\,\mathrm{d}t$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\sum_{k=0}^{K-1}\int_{kh+\delta}^{(k+1)h+\delta} \mathbb{E}_{{\mathbf{x}}_{t}\sim q_{t}}D_{I}(s_{t}({\mathbf{x}}_{t})\|\hat{s}_ {(k+1)h+\delta}({\mathbf{x}}_{t}))\,\mathrm{d}t,$ $$

where we used $\mathbb{E}_{\bar{{\mathbb{Q}}}}M_{T-\delta}^{f}=\mathbb{E}_{\bar{{\mathbb{Q}}}
}M_{0}^{f}=0$ since $\{M^{f}_{t}\}_{t\geq 0}$ is a $\bar{{\mathbb{Q}}}$-martingale. Thus we finish the proof of Lemma 1. $\hfill\square$

###### Theorem 3 (Girsanov, (Benton et al., 2024b , Theorem 6) ) .

###### Lemma 6 (Dynkin’s formula, (Dong, 2003 , Theorem 27.20) ) .

### B.2 Proof of Lemma 2

Proof o Lemma 2.
Note that for all $0\leq t^{\prime}\neq t$,

$$ $\displaystyle s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}=\frac{q_{t}({\mathbf{x}}^{ \backslash i}\odot\hat{x}^{i})}{q_{t}({\mathbf{x}})}={}$ $\displaystyle\frac{1}{q_{t}({\mathbf{x}})}\sum_{{\mathbf{x}}_{t^{\prime}}\in{ \mathcal{X}}}q_{t^{\prime}}({\mathbf{x}}_{t^{\prime}})q_{t|t^{\prime}}({ \mathbf{x}}^{\backslash i}\odot\hat{x}^{i}|{\mathbf{x}}_{t^{\prime}})$ $\displaystyle={}$ $\displaystyle\frac{1}{q_{t}({\mathbf{x}})}\sum_{{\mathbf{x}}_{t^{\prime}}\in{ \mathcal{X}}}q_{t^{\prime}}({\mathbf{x}}_{t^{\prime}})\prod_{k\neq i}q^{i}_{t| t^{\prime}}(x^{k}|x_{t^{\prime}}^{k})q^{i}_{t|t^{\prime}}(\hat{x}^{i}|x_{t^{ \prime}}^{i})$ $\displaystyle={}$ $\displaystyle\frac{1}{q_{t}({\mathbf{x}})}\sum_{{\mathbf{x}}_{t^{\prime}}\in{ \mathcal{X}}}q_{t^{\prime}}({\mathbf{x}}_{t^{\prime}})\prod_{k=1}^{d}q^{i}_{t| t^{\prime}}(x^{k}|x_{t^{\prime}}^{k})\frac{q^{i}_{t|t^{\prime}}(\hat{x}^{i}|x_ {t^{\prime}}^{i})}{q^{i}_{t|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}$ $\displaystyle={}$ $\displaystyle\sum_{{\mathbf{x}}_{t^{\prime}}\in{\mathcal{X}}}\frac{q_{t^{ \prime}}({\mathbf{x}}_{t^{\prime}})q_{t|t^{\prime}}({\mathbf{x}}|{\mathbf{x}}_ {t^{\prime}})}{q_{t}({\mathbf{x}})}\cdot\frac{q^{i}_{t|t^{\prime}}(\hat{x}^{i} |x_{t^{\prime}}^{i})}{q^{i}_{t|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}$ $\displaystyle={}$ $\displaystyle\mathbb{E}_{{\mathbf{x}}_{t^{\prime}}\sim q_{t^{\prime}|t}(\cdot| {\mathbf{x}})}\frac{q^{i}_{t|t^{\prime}}(\hat{x}^{i}|x_{t^{\prime}}^{i})}{q^{i }_{t|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}.$ (22) $$

In particular, by taking $t^{\prime}=0$ in (22), we have

$$ $\displaystyle s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}={}$ $\displaystyle\mathbb{E}_{{\mathbf{x}}_{0}\sim q_{0|t}(\cdot|{\mathbf{x}})} \frac{q^{i}_{t|0}(\hat{x}^{i}|x_{0}^{i})}{q^{i}_{t|0}(x^{i}|x_{0}^{i})}$ $\displaystyle={}$ $\displaystyle\mathbb{E}_{{\mathbf{x}}_{0}\sim q_{0|t}(\cdot|{\mathbf{x}})} \frac{1+e^{-t}(-1+S\cdot\delta\{\hat{x}^{i},x_{0}^{i}\})}{1+e^{-t}(-1+S\cdot \delta\{x^{i},x_{0}^{i}\})}\leq 1+\frac{S}{e^{t}-1}\leq 1+\frac{S}{e^{\delta}- 1}.$ (23) $$

$\hfill\square$

### B.3 Proof of Lemma 3

To prove Lemma 3, we need the following lemmas. Proofs of Lemmas 7, 8, and 9 are provided in Appendix C.

###### Lemma 7 .

Denote $q_{t}^{i}$ as the marginals of the $i$-th dimensional forward CTMC $X^{i}$, and the corresponding score function for $X^{i}$ as $s_{t}^{i}(x)_{y}=\frac{q_{t}^{i}(y)}{q_{t}^{i}(x)}$ for $x\neq y\in[S]$. Then for all $i\in[d]$, $k\in\{0,1,\cdots,K-1\}$, $t\in[kh+\delta,(k+1)h+\delta]$, and $x\neq y\in[S]$, we have

$$ $\displaystyle s_{t}^{i}(x)_{y}\leq 1+\frac{S}{e^{kh+\delta}-1},\quad\text{and} \quad\left|s_{t}^{i}(x)_{y}-s_{(k+1)h+\delta}^{i}(x)_{y}\right|\leq\frac{She^{ -(kh+\delta)}}{(1-e^{-(kh+\delta)})^{2}}.$ $$

###### Lemma 8 .

There exists some large enough $t^{\prime}$ such that for all $i\in[d]$, $k\in\{0,1,\cdots,K-1\}$, $t\in[kh+\delta,(k+1)h+\delta]$, $x\neq y\in[S]$, and $x_{t^{\prime}}\in[S]$, we have

$$ $\left|\frac{q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|y)}{q^{i}_{t^{\prime}|t}(x_{t^ {\prime}}|x)}-\frac{q^{i}_{t^{\prime}|(k+1)h+\delta}(x_{t^{\prime}}|y)}{q^{i}_ {t^{\prime}|(k+1)h+\delta}(x_{t^{\prime}}|x)}\right|\leq 8Sh,\quad\text{and} \quad\frac{q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|y)}{q^{i}_{t^{\prime}|t}(x_{t^{ \prime}}|x)}\leq 2.$ $$

###### Lemma 9 .

There exists some large enough $t^{\prime}$ such that for all $k\in\{0,1,\cdots,K-1\}$, $t\in[kh+\delta,(k+1)h+\delta]$ and ${\mathbf{x}}\in{\mathcal{X}}$, it holds that

$$ $2\cdot D_{\mathrm{TV}}(q_{t^{\prime}|t}(\cdot|{\mathbf{x}}),q_{t^{\prime}|(k+1 )h+\delta}(\cdot|{\mathbf{x}}))\leq h.$ $$

Proof of Lemma 3.
We can bound the high-dimensional score movement as follows:

$$ $\displaystyle|s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}-s_{(k+1)h+\delta}({\mathbf{x }})_{i,\hat{x}^{i}}|$ $\displaystyle={}$ $\displaystyle\left|\mathbb{E}_{{\mathbf{x}}_{t^{\prime}}\sim q_{t^{\prime}|t}( \cdot|{\mathbf{x}})}\frac{q^{i}_{t|t^{\prime}}(\hat{x}^{i}|x_{t^{\prime}}^{i}) }{q^{i}_{t|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}-\mathbb{E}_{{\mathbf{x}}_{t^ {\prime}}\sim q_{t^{\prime}|(k+1)h+\delta}(\cdot|{\mathbf{x}})}\frac{q^{i}_{(k +1)h+\delta|t^{\prime}}(\hat{x}^{i}|x_{t^{\prime}}^{i})}{q^{i}_{(k+1)h+\delta| t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}\right|$ $\displaystyle\leq{}$ $\displaystyle\mathbb{E}_{{\mathbf{x}}_{t^{\prime}}\sim q_{t^{\prime}|t}(\cdot| {\mathbf{x}})}\left|\frac{q^{i}_{t|t^{\prime}}(\hat{x}^{i}|x_{t^{\prime}}^{i}) }{q^{i}_{t|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}-\frac{q^{i}_{(k+1)h+\delta|t ^{\prime}}(\hat{x}^{i}|x_{t^{\prime}}^{i})}{q^{i}_{(k+1)h+\delta|t^{\prime}}(x ^{i}|x_{t^{\prime}}^{i})}\right|$ $\displaystyle+\left|\mathbb{E}_{{\mathbf{x}}_{t^{\prime}}\sim q_{t^{\prime}|t} (\cdot|{\mathbf{x}})}\frac{q^{i}_{(k+1)h+\delta|t^{\prime}}(\hat{x}^{i}|x_{t^{ \prime}}^{i})}{q^{i}_{(k+1)h+\delta|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}- \mathbb{E}_{{\mathbf{x}}_{t^{\prime}}\sim q_{t^{\prime}|(k+1)h+\delta}(\cdot|{ \mathbf{x}})}\frac{q^{i}_{(k+1)h+\delta|t^{\prime}}(\hat{x}^{i}|x_{t^{\prime}} ^{i})}{q^{i}_{(k+1)h+\delta|t^{\prime}}(x^{i}|x_{t^{\prime}}^{i})}\right|$ $\displaystyle\leq{}$ $\displaystyle\mathbb{E}_{{\mathbf{x}}_{t^{\prime}}\sim q_{t^{\prime}|t}(\cdot| {\mathbf{x}})}\left|s_{t}(x^{i})_{\hat{x}^{i}}\cdot\frac{q^{i}_{t^{\prime}|t}( x_{t^{\prime}}^{i}|\hat{x}^{i})}{q^{i}_{t^{\prime}|t}(x_{t^{\prime}}^{i}|x^{i} )}-s_{(k+1)h+\delta}(x^{i})_{\hat{x}^{i}}\cdot\frac{q^{i}_{t^{\prime}|(k+1)h+ \delta}(x_{t^{\prime}}^{i}|\hat{x}^{i})}{q^{i}_{t^{\prime}|(k+1)h+\delta}(x_{t ^{\prime}}^{i}|x^{i})}\right|$ $\displaystyle+\sup_{t,\hat{x}^{i},x_{t^{\prime}}^{i},x^{i}}\left\{\frac{q^{i}_ {t^{\prime}|t}(x_{t^{\prime}}^{i}|\hat{x}^{i})}{q^{i}_{t^{\prime}|t}(x_{t^{ \prime}}^{i}|x^{i})}\right\}\cdot 2D_{\mathrm{TV}}(q_{t^{\prime}|t}(\cdot|{ \mathbf{x}}),q_{t^{\prime}|(k+1)h+\delta}(\cdot|{\mathbf{x}})),$ (24) $$

where the first equality is by (22), the first inequality is due to the triangle inequality, and the last inequality is due to the Bayes’ rule.

Then by utilizing the inequality $|a_{1}a_{2}-b_{1}b_{2}|\leq|a_{1}-b_{1}|a_{2}+b_{1}|a_{2}-b_{2}|$ $(a_{1},a_{2},b_{1},b_{2}\geq 0)$ for the first term in (24), and then using Lemmas 7, 8, and 9, for some large enough $t^{\prime}$, we have that

$$ $\displaystyle|s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}-s_{(k+1)h+\delta}({\mathbf{x }})_{i,\hat{x}^{i}}|\leq{}$ $\displaystyle\left[\frac{2She^{-(kh+\delta)}}{(1-e^{-(kh+\delta)})^{2}}+(1+ \frac{S}{e^{kh+\delta}-1})8Sh\right]+2h$ $\displaystyle\lesssim{}$ $\displaystyle\left[\frac{e^{-(kh+\delta)}}{(1-e^{-(kh+\delta)})^{2}}+\frac{S}{ e^{kh+\delta}-1}+1\right]Sh.$ $$

$\hfill\square$

###### Lemma 7 .

###### Lemma 8 .

###### Lemma 9 .

### B.4 Proof of Lemma 4

Proof of Lemma 4.
This is a similar proof to that of Lemma 8 in Chen and Ying (). Define the kernel function

$$ $g_{\mathbf{w}}(t)=\frac{1}{S^{d}}\prod_{i=1}^{d}\left[1+e^{-t}(-1+S\cdot \mathbf{1}\{w^{i}\equiv 0\pmod{S}\})\right]\quad\text{for}\ {\mathbf{w}}\in{ \mathbb{Z}}^{d},\ t\geq 0.$ $$

By Proposition 1, we can express the transition probability of the forward process as

$$ $\displaystyle q_{t|s}({\mathbf{x}}_{t}|{\mathbf{x}}_{s})=\prod_{i=1}^{d}q_{t|s }^{i}(x_{t}^{i}|x_{s}^{i})=\prod_{i=1}^{d}P_{s,t}^{0}(x_{s}^{i},x_{t}^{i})$ $\displaystyle={}$ $\displaystyle\frac{1}{S^{d}}\prod_{i=1}^{d}\left[1+e^{-(t-s)}(-1+S\cdot\delta \{x_{t}^{i},x_{s}^{i}\})\right]\quad\text{for all $t>s\geq 0$}.$ $$

Then we have $q_{t|0}({\mathbf{y}}|{\mathbf{x}})=g_{{\mathbf{y}}-{\mathbf{x}}}(t)$ for $t>0$. Thus, it follows that for all $t\in(0,T]$, ${\mathbf{x}}\in{\mathcal{X}}$, $i\in[d]$ and $x^{i}\neq\hat{x}^{i}\in[S]$,

$$ $\displaystyle s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}$ $\displaystyle=\frac{q_{t}({\mathbf{x}}^{\backslash i}\odot\hat{x}^{i})}{q_{t}( {\mathbf{x}})}$ $\displaystyle=\frac{q_{t}({\mathbf{x}}+(\hat{x}^{i}-x^{i}){\mathbf{e}}_{i})}{q _{t}({\mathbf{x}})}$ $\displaystyle=\frac{\sum_{{\mathbf{y}}\in{\mathcal{X}}}q_{0}({\mathbf{y}})q_{t |0}({\mathbf{x}}+(\hat{x}^{i}-x^{i}){\mathbf{e}}_{i}|{\mathbf{y}})}{q_{t}({ \mathbf{x}})}$ $\displaystyle=\frac{\sum_{{\mathbf{y}}\in{\mathcal{X}}}q_{0}({\mathbf{y}})g_{{ \mathbf{x}}+(\hat{x}^{i}-x^{i}){\mathbf{e}}_{i}-{\mathbf{y}}}(t)}{q_{t}({ \mathbf{x}})}$ $\displaystyle=\frac{\sum_{{\mathbf{y}}\in{\mathcal{X}}}q_{0}({\mathbf{y}}+( \hat{x}^{i}-x^{i}){\mathbf{e}}_{i})g_{{\mathbf{x}}-{\mathbf{y}}}(t)}{q_{t}({ \mathbf{x}})}$ $\displaystyle=\sum_{{\mathbf{y}}\in{\mathcal{X}}}\frac{q_{0}({\mathbf{y}})q_{t |0}({\mathbf{x}}|{\mathbf{y}})}{q_{t}({\mathbf{x}})}\cdot\frac{q_{0}({\mathbf{ y}}+(\hat{x}^{i}-x^{i}){\mathbf{e}}_{i})}{q_{0}({\mathbf{y}})}$ $\displaystyle=\mathbb{E}_{{\mathbf{y}}\sim q_{0|t}(\cdot|{\mathbf{x}})}\frac{q _{0}({\mathbf{y}}+(\hat{x}^{i}-x^{i}){\mathbf{e}}_{i})}{q_{0}({\mathbf{y}})}$ $\displaystyle\leq L,$ $$

where the last inequality is by Assumption 2 and ${\mathbf{y}}+(\hat{x}^{i}-x^{i}){\mathbf{e}}_{i}$ should be understood in modulo $S$ sense. $\hfill\square$

### B.5 Proof of Lemma 5

###### Lemma 10 .

Suppose Assumption 2 holds. Let $\delta=0$, then for all $i\in[d]$, $k\in\{0,1,\cdots,K-1\}$, $t\in[kh,(k+1)h]$, and $x\neq y\in[S]$, we have

$$ $\displaystyle s_{t}^{i}(x)_{y}\leq\kappa_{i},\quad\text{and}\quad\left|s_{t}^{ i}(x)_{y}-s_{(k+1)h}^{i}(x)_{y}\right|\leq\kappa_{i}\cdot\frac{h}{1-e^{-(k+1)h }}.$ $$

The proof of Lemma 10 is provided in Appendix C.

Proof of Lemma 5.
Similar to the proof of Lemma 3, by utilizing the inequality $|a_{1}a_{2}-b_{1}b_{2}|\leq|a_{1}-b_{1}|a_{2}+b_{1}|a_{2}-b_{2}|(a_{1},a_{2},b
_{1},b_{2}\geq 0)$ for the first term in (24) and then combining Lemma 8, Lemma 9, and Lemma 10 with $\delta=0$, we obtain

$$ $\displaystyle|s_{t}({\mathbf{x}})_{i,\hat{x}^{i}}-s_{(k+1)h}({\mathbf{x}})_{i, \hat{x}^{i}}|\leq{}$ $\displaystyle\kappa_{i}\left[\frac{1}{1-e^{-(k+1)h}}h\cdot 2+8Sh\right]+2h$ $\displaystyle\lesssim{}$ $\displaystyle\left[\frac{1}{1-e^{-(k+1)h}}+S\right]\kappa_{i}h.$ $$

$\hfill\square$

###### Lemma 10 .

## Appendix C Omitted Proofs in Appendix B

### C.1 Proof of Lemma 7

Proof of Lemma 7.
Proposition 1 implies that

$$ $q_{t}^{i}=P_{0,t}^{i}\cdot p_{\rm{data}}^{i}=e^{-t}p_{\rm{data}}^{i}+(1-e^{-t} )\pi.$ $$

Thus, we have

$$ $\displaystyle s_{t}^{i}(x)_{y}=\frac{q_{t}^{i}(y)}{q_{t}^{i}(x)}=\frac{p_{\rm{ data}}^{i}(y)+(e^{t}-1)\frac{1}{S}}{p_{\rm{data}}^{i}(x)+(e^{t}-1)\frac{1}{S}},$ (25) $$

and

$$ $\displaystyle\left|s_{t}^{i}(x)_{y}-s^{i}_{(k+1)h+\delta}(x)_{y}\right|={}$ $\displaystyle\left|\frac{q_{t}^{i}(y)}{q_{t}^{i}(x)}-\frac{q^{i}_{(k+1)h+ \delta}(y)}{q^{i}_{(k+1)h+\delta}(x)}\right|$ $\displaystyle={}$ $\displaystyle\frac{(e^{(k+1)h+\delta}-e^{t})|p_{\rm{data}}^{i}(x)-p_{\rm{data} }^{i}(y)|}{(p_{\rm{data}}^{i}(x)+\frac{1}{S}(e^{(k+1)h+\delta}-1))(Sp_{\rm{ data}}^{i}(y)+(e^{t}-1))}.$ (26) $$

We can derive from (25) and (26) that if we retain the dependence on $\delta$, we obtain

$$ $\displaystyle s_{t}^{i}(x)_{y}\leq 1+\frac{S}{e^{t}-1}\leq 1+\frac{S}{e^{kh+ \delta}-1},$ $$

and

$$ $\displaystyle\left|s_{t}^{i}(x)_{y}-s^{i}_{(k+1)h+\delta}(x)_{y}\right|\leq{}$ $\displaystyle\frac{Se^{(k+1)h+\delta}(1-e^{-((k+1)h+\delta-t)})}{(e^{(k+1)h+ \delta}-1)(e^{t}-1)}$ $\displaystyle\leq{}$ $\displaystyle\frac{Sh}{(1-e^{-((k+1)h+\delta)})(e^{kh+\delta}-1)}$ $\displaystyle\leq{}$ $\displaystyle\frac{She^{-(kh+\delta)}}{(1-e^{-(kh+\delta)})^{2}}.$ $$

$\hfill\square$

### C.2 Proof of Lemma 8

Proof of Lemma 8.
First, we have

$$ $\displaystyle|q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|y)-q^{i}_{t^{\prime}|(k+1)h+ \delta}(x_{t^{\prime}}|y)|$ $\displaystyle={}$ $\displaystyle\frac{1}{S}\left|(-1+S\cdot\delta\{x_{t^{\prime}},y\})(e^{-(t^{ \prime}-t)}-e^{-(t^{\prime}-((k+1)h+\delta))})\right|$ $\displaystyle\leq{}$ $\displaystyle e^{-(t^{\prime}-((k+1)h+\delta))}(1-e^{-((k+1)h+\delta-t)})\leq h,$ $$

and

$$ $q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|x)=\frac{1}{S}(1+e^{-(t^{\prime}-t)}(-1+S \cdot\delta\{x,x_{t^{\prime}}\}))\geq\frac{1}{S}(1-e^{-(t^{\prime}-t)})\geq \frac{1}{\sqrt{2}S};$ $$

$$ $q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|x)\leq\frac{1}{S}(1+e^{-(t^{\prime}-t)}(S- 1))\leq\frac{2}{S}$ $$

for some large enough $t^{\prime}$ (for example, $t^{\prime}\geq T+2\log\frac{S}{2}$). Hence, we have the estimate

$$ $\displaystyle\left|\frac{q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|y)}{q^{i}_{t^{ \prime}|t}(x_{t^{\prime}}|x)}-\frac{q^{i}_{t^{\prime}|(k+1)h+\delta}(x_{t^{ \prime}}|y)}{q^{i}_{t^{\prime}|(k+1)h+\delta}(x_{t^{\prime}}|x)}\right|$ $\displaystyle={}$ $\displaystyle\left|\frac{q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|y)q^{i}_{t^{ \prime}|(k+1)h+\delta}(x_{t^{\prime}}|x)-q^{i}_{t^{\prime}|(k+1)h+\delta}(x_{t ^{\prime}}|y)q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|x)}{q^{i}_{t^{\prime}|t}(x_{t ^{\prime}}|x)q^{i}_{t^{\prime}|(k+1)h+\delta}(x_{t^{\prime}}|x)}\right|\leq \frac{2h\frac{2}{S}}{\frac{1}{2S^{2}}}=8Sh.$ $$

For the other statement, it holds that

$$ $\displaystyle\frac{q^{i}_{t^{\prime}|t}(x_{t^{\prime}}|y)}{q^{i}_{t^{\prime}|t }(x_{t^{\prime}}|x)}=\frac{1+e^{-(t^{\prime}-t)}(-1+S\cdot\delta\{x_{t^{\prime }},y\})}{1+e^{-(t^{\prime}-t)}(-1+S\cdot\delta\{x_{t^{\prime}},x\})}\leq 1+ \frac{S}{e^{t^{\prime}-t}-1}\leq 2$ $$

for some large $t^{\prime}$ (for example, $t^{\prime}\geq T+\log S$).
$\hfill\square$

### C.3 Proof of Lemma 9

Proof of Lemma 9.
By taking a large enough $t^{\prime}$ (for example, $t^{\prime}\geq T+d\log S+\log d$), we have

$$ $\displaystyle 2\cdot D_{\mathrm{TV}}(q_{t^{\prime}|t}(\cdot|{\mathbf{x}}),q_{t ^{\prime}|(k+1)h+\delta}(\cdot|{\mathbf{x}}))={}$ $\displaystyle\sum_{{\mathbf{x}}_{t^{\prime}}\in{\mathcal{X}}}|q_{t^{\prime}|t} ({\mathbf{x}}_{t^{\prime}}|{\mathbf{x}})-q_{t^{\prime}|(k+1)h+\delta}({\mathbf {x}}_{t^{\prime}}|{\mathbf{x}})|$ $\displaystyle={}$ $\displaystyle\sum_{{\mathbf{x}}_{t^{\prime}}\in{\mathcal{X}}}\left|\prod_{i=1} ^{d}q^{i}_{t^{\prime}|t}(x_{t^{\prime}}^{i}|x^{i})-\prod_{i=1}^{d}q^{i}_{t^{ \prime}|(k+1)h+\delta}(x_{t^{\prime}}^{i}|x^{i})\right|$ $\displaystyle\leq{}$ $\displaystyle(S^{d}de^{-(t^{\prime}-((k+1)h+\delta))})h\leq h,$ $$

where the second last inequality comes from the inequality

$$ $\left|\prod_{i=1}^{n}a_{i}-\prod_{i=1}^{n}b_{i}\right|\leq\sum_{k=1}^{n}\left| (a_{k}-b_{k})\prod_{i\neq k}\mathrm{mix}\{a_{i},b_{i}\}\right|$ $$

where $\mathrm{mix}\{a_{i},b_{i}\}$ denotes taking a value from $a_{i}$ and $b_{i}$.
$\hfill\square$

### C.4 Proof of Lemma 10

Proof of Lemma 10.
We retain the dependence on $p_{\rm{data}}^{i}$ in equations (25) and (26) with $\delta=0$, and derive that

$$ $\displaystyle s_{t}^{i}(x)_{y}\leq$ $\displaystyle\max\left\{\frac{(p_{\rm{data}}^{i})_{\mathrm{max}}}{(p_{\rm{data }}^{i})_{\mathrm{min}}},1\right\}=\kappa_{i},$ $$

and

$$ $\displaystyle\left|s_{t}^{i}(x)_{y}-s^{i}_{(k+1)h}(x)_{y}\right|\leq\frac{(p_{ \rm{data}}^{i})_{\mathrm{max}}}{(p_{\rm{data}}^{i})_{\mathrm{min}}}\cdot\frac{ h}{1-e^{-(k+1)h}}=\kappa_{i}\cdot\frac{h}{1-e^{-(k+1)h}}.$ $$

$\hfill\square$

## Appendix D Practical Algorithm

Inspired by Chen and Ying (, Algorithm 1), we provide a practical generative sampling algorithm in Algorithm 1. The uniformization of CTMC guarantees the algorithm (Chen and Ying, , Proposition 1). For convenience, we define $\hat{s}_{t}({\mathbf{x}})_{{\mathbf{x}}}:=\sum_{i=1}^{d}\sum_{\hat{x}^{i}\neq x
^{i}}\hat{s}_{t}({\mathbf{x}})_{i,\hat{x}^{i}}$ for $t\in[0,T]$, yielding that

$$ $\displaystyle\hat{Q}^{\leftarrow}_{t}({\mathbf{x}},{\mathbf{x}})=-\sum_{{ \mathbf{y}}\neq{\mathbf{x}}}\hat{Q}^{\leftarrow}_{t}({\mathbf{x}},{\mathbf{y}} )=-\sum_{i=1}^{d}\sum_{\hat{x}^{i}\neq x^{i}}\hat{Q}^{\leftarrow}_{t}({\mathbf {x}},{\mathbf{x}}^{\backslash i}\odot\hat{x}^{i})={}$ $\displaystyle-\frac{1}{S}\sum_{i=1}^{d}\sum_{\hat{x}^{i}\neq x^{i}}s_{T-t}({ \mathbf{x}})_{i,\hat{x}^{i}}$ $\displaystyle={}$ $\displaystyle-\frac{1}{S}\hat{s}_{T-[\frac{t}{h}]h}({\mathbf{x}})_{{\mathbf{x} }}.$ $$

Figure: Algorithm 1 Generative Reverse Process Simulation through Uniformization

Note that we run a Poisson point process to sample based on the transition probability matrix $\exp\left(h\hat{Q}^{\leftarrow}_{hk}\right)$ in each iteration. Running Algorithm 1 requires $M\sim\mathrm{Poisson}(\lambda)$ steps with $\lambda=\sum_{k=0}^{K-1}\lambda_{k}h=(\sum_{k=0}^{K-1}\max_{{\mathbf{x}}\in{
\mathcal{X}}}\{\hat{s}_{T-kh}({\mathbf{x}})_{{\mathbf{x}}}\})h$, which characterizes the sampling complexity.

Discussion on $\lambda$.
Since we know that $s_{T-kh}({\mathbf{x}})_{\mathbf{x}}\leq dS(1+\frac{S}{e^{T-kh}-1})$ for all $k\in\{0,1,\cdots,K-1\}$ and ${\mathbf{x}}\in{\mathcal{X}}$ from the score bound (23), we can apply score clipping to ensure that $\hat{s}_{T-kh}({\mathbf{x}})_{\mathbf{x}}\leq\frac{3}{2}dS(1+\frac{S}{e^{T-kh}
-1})$. Then we have

$$ $\displaystyle\lambda\lesssim{}$ $\displaystyle\sum_{k=0}^{K-1}dS\left(1+\frac{S}{e^{T-kh}-1}\right)h=dST+dS^{2} h\sum_{k=1}^{K}\frac{1}{e^{kh+\delta}-1}$ $\displaystyle\lesssim{}$ $\displaystyle dST+dS^{2}h\int_{h+\delta}^{T}\frac{1}{e^{x}-1}\,\mathrm{d}t \lesssim dS(T+Sh\log(1/(h+\delta))).$ $$

By choosing $T$ and $h$ in Corollary 1, we have

$$ $\displaystyle\lambda\lesssim{}$ $\displaystyle dS\left(\log\frac{d\log S}{{\epsilon}}+\min\left\{\delta\left( \frac{{\epsilon}}{C_{1}S^{2}d}\right)^{\frac{1}{3}},\left(\frac{{\epsilon}}{C_ {1}S^{2}d}\right)^{\frac{1}{2}}\right\}S\log(1/\delta)\right)$ $\displaystyle\leq{}$ $\displaystyle dS\log\frac{d\log S}{{\epsilon}}+\left(\frac{{\epsilon}}{C_{1}} \right)^{\frac{5}{12}}S^{\frac{7}{6}}d^{\frac{7}{12}}\delta^{\frac{1}{2}}\log( 1/\delta),$ (27) $$

where we used the inequality $\min\{a,b\}\leq\sqrt{ab}$ for $a,b\geq 0$; by choosing $T$ and $h$ in Corollary 2, we have

$$ $\displaystyle\lambda\lesssim dS\left(\log\frac{d\log S}{{\epsilon}}+Sh\log(1/h )\right)\lesssim dS\left(\log\frac{d\log S}{{\epsilon}}+\sqrt{\frac{{\epsilon} }{C_{2}\kappa^{2}}}\log\frac{C_{2}S^{2}\kappa^{2}}{{\epsilon}}\right),$ (28) $$

which depends on the property of data distribution. When score clipping is applied as discussed in Appendix 5, we can specify $C_{1}=\frac{3S}{\delta}$ and $C_{2}=\frac{3}{2}L$ and further obtain from (27) that

$$ $\displaystyle\lambda\lesssim dS\log\frac{d\log S}{{\epsilon}}+{\epsilon}^{ \frac{5}{12}}S^{\frac{19}{12}}d^{\frac{7}{12}}\delta^{\frac{1}{12}}\log(1/ \delta)\to dS\log\frac{d\log S}{{\epsilon}}\ (\delta\to 0^{+})$ (29) $$

with early stopping, and from (28) that

$$ $\displaystyle\lambda\lesssim dS\left(\log\frac{d\log S}{{\epsilon}}+\sqrt{ \frac{{\epsilon}}{L\kappa^{2}}}\log\frac{L\kappa^{2}S^{2}}{{\epsilon}}\right) \lesssim{}$ $\displaystyle dS\log\frac{d\log S}{{\epsilon}}+1+\sqrt{\frac{{\epsilon}}{L \kappa^{2}}}\log S$ (30) $$

without early stopping.
Note that the last term of (30) can be rather small for some large $L$ and $\kappa^{2}$, leading the first term to be the dominant term in the bound (30), which matches the bound (29) for the sampling complexity with a sufficient small $\delta>0$.

## Appendix E Bregman Divergence

###### Definition 1 (Bregman divergence) .

Let $\phi$ be a strictly convex function defined on a convex set ${\mathcal{S}}\subset\mathbb{R}^{n}$ and $\phi$ is differentiable. The Bregman divergence $D_{\phi}(x\|y):{\mathcal{S}}\times{\mathcal{S}}\to\mathbb{R}_{+}$ is defined as

$$ $D_{\phi}(x\|y)=\phi(x)-\phi(y)-\nabla\phi(y)^{\top}(x-y).$ $$

In particular, the generalized I-divergence

$$ $D_{I}({\mathbf{x}}\|{\mathbf{y}})=\sum_{i=1}^{n}\left[-x^{i}+y^{i}+x^{i}\log \frac{x^{i}}{y^{i}}\right]$ $$

is generated by the negative entropy function $I({\mathbf{x}})=\sum_{i=1}^{n}x^{i}\log x^{i}$. When restricted on the simplex, the generalized I-divergence becomes KL divergence.

The Bregman divergence does not satisfy the triangle inequality. However, for the negative entropy restricted to a closed interval contained in $(0,+\infty)$, we have the following proposition, which provides an analogous form of the triangle inequality.

###### Proposition 3 .

Let the negative entropy function $F({\mathbf{x}})=\sum_{i=1}^{n}x_{i}\log x_{i}$ defined on $[\frac{1}{C},C]^{n}\ (C>0)$. Then given an ${\epsilon}>0$, we have

- 1.
$D_{I}({\mathbf{x}}\|{\mathbf{y}})\lesssim{\epsilon}\Leftrightarrow\|{\mathbf{x
}}-{\mathbf{y}}\|_{2}^{2}\lesssim{\epsilon}.$
- 2.
$D_{I}({\mathbf{x}}\|{\mathbf{y}})\leq C\cdot\|{\mathbf{x}}-{\mathbf{z}}\|_{2}^
{2}+2C^{2}\cdot D_{I}({\mathbf{z}}\|{\mathbf{y}})$.

Proof of Proposition 3.

- 1.
"$\Rightarrow$"
Since $\nabla^{2}F({\mathbf{x}})=\operatorname{diag}\{\frac{1}{x_{1}},\cdots,\frac{1}
{x_{n}}\}\succeq\frac{1}{C}I_{n}$, $F({\mathbf{x}})$ is strongly-convex with constant $\frac{1}{C}>0$. Thus by the definition of strongly-convex function, we have
$\frac{1}{2C}\|{\mathbf{x}}-{\mathbf{y}}\|_{2}^{2}\leq D_{I}({\mathbf{x}}\|{
\mathbf{y}})\lesssim{\epsilon}.$
"$\Leftarrow$"
Since $\nabla^{2}F({\mathbf{x}})=\operatorname{diag}\{\frac{1}{x_{1}},\cdots,\frac{1}
{x_{n}}\}\preceq CI_{n}$, there exists some $t\in[0,1]$ such that
$\displaystyle D_{I}({\mathbf{x}}\|{\mathbf{y}})=\frac{1}{2}({\mathbf{x}}-{
\mathbf{y}})^{\top}\nabla^{2}F({\mathbf{y}}+t({\mathbf{x}}-{\mathbf{y}}))({
\mathbf{x}}-{\mathbf{y}})\leq\frac{C}{2}\|{\mathbf{x}}-{\mathbf{y}}\|_{2}^{2}
\lesssim{\epsilon}.$
- 2.
By the proof of 1., we have
$\displaystyle D_{I}({\mathbf{x}}\|{\mathbf{y}})\leq\frac{C}{2}\|{\mathbf{x}}-{
\mathbf{y}}\|_{2}^{2}\leq C\cdot(\|{\mathbf{x}}-{\mathbf{z}}\|_{2}^{2}+\|{
\mathbf{z}}-{\mathbf{y}}\|_{2}^{2})\leq C\cdot\|{\mathbf{x}}-{\mathbf{z}}\|_{2
}^{2}+2C^{2}\cdot D_{H}({\mathbf{z}}\|{\mathbf{y}}).$

$\hfill\square$

###### Definition 1 (Bregman divergence) .

###### Proposition 3 .

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 3
presentation: 2
questions: - *Equation on line 723*. Why is $Q$ equal to the Kronecker sum $Q^{tok}$?   
 - *line 296* Why is the reverse process time-inhomogeneous? 
 - *line 3 of the Algorithm*: How easy is it to find the maximum of the estimated score function? Is there any concavity assumption to make this problem solvable in theory/real-time? Is this assumption satisfied for practically relevant examples?
 - *line 361* Why is there a uniform upper bound on all the scores and their estimators? On line 371 the authors mention that the score function may be as large as infinity for some data points. This means, that when $\delta$ is small, this uniform upper bound $C_1$ becomes larger, thus, it is dependent on $\delta$. Can this dependence be quantified? 
 - *Equation (4)*. Why is this true? Is there a reference or a proof for this statement?
soundness: 3
strengths: The paper tackles an interesting theoretical problem. Theoretical analysis of diffusion models with finite state spaces with discrete time space is of great importance. The authors have made the effort to push further the existing methods for the current setting.
summary: The paper presents a discrete-time sampling method using score estimators at fixed points in a multidimensional state space. It provides bounds on how closely the sample matches the data distribution, with KL divergence bounds nearly linear in dimension, comparable to top diffusion models. The analysis uses a Girsanov-based approach to define key properties of the discrete score function for effective sampling.
weaknesses: The notation is confusing and important details are often omitted.  The assumptions seem to be rather stringent. The paper lacks mathematical clarity. See the below sections for details.
 
### Mathematical comments 
 
- *Proposition 1*. The formula for $q_t$ depends on the initial data distribution $p_{data}$. When $t \rightarrow \infty$, the term on the right side  $\frac{1}{S} \left(1 - e^{-t}\right) \mathbf{1}_S \mathbf{1}_S^\top + e^{-t} I_S \rightarrow \frac{1}{S} \mathbf{1}_S \mathbf{1}_S^\top$ . The latter is a fixed matrix and thus $q_t \rightarrow \frac{1}{S} \mathbf{1}_S \mathbf{1}_S^\top \cdot p_{data}$. This is not necessarily the uniform distribution. 
- *Proposition 1* What does approaching mean here? In what sense do you have the convergence?
-  *line 280* . The sentence `With rate $Q^{\leftarrow}_t$, it holds that...` is not clear. Is there a reference or proof for this statement? 
- *Assumption 2* It does not seem to be easy to verify this assumption. Is there a general class of distributions that are known to satisfy it?
- *Theorem 2* The number $\kappa_i$ is not always well-defined, as we deal with discrete distributions, where some of the probabilities may be equal to zero. 

#### typos
- *line 187* if setting β(t) as a time-dependent scala
- *line 206* Nota -> Note
- *line 323* For completeness, We -> For completeness, we

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. Have the authors considered adaptive step sizes as a way to minimize discretization error? If so, could author's share insights on how this might affect the overall convergence bound?
2. The paper proposes a CTMC-based discrete diffusion model, but certain continuous diffusion approaches are also adaptable to discrete data. Could the authors elaborate on specific scenarios or types of tasks where their CTMC-based model would be preferred over these alternative approaches?
3. Also see weaknesses part above
soundness: 4
strengths: Overrall I think this work is clear and studies a clean problem which is relevant to the theoretical understanding of diffusion models.. Theorems 1 and 2 derive rigorous convergence bounds for score-based discrete diffusion models using KL divergence (Theorem 1 with early stopping, Theorem 2 without early stopping). This provides a critical theoretical foundation for discrete diffusion modeling, aligning nearly linearly with the dimension $d$, a promising result compared to continuous models. And the use of a Girsanov-based approach to analyze the sampling algorithm in a discrete setting is particularly noteworthy (Sections 5 and 6). This method adapts well-established techniques from continuous diffusion models and is a creative application in the discrete domain, enabling a novel convergence analysis.
The work also proposes a time-discretized approach (Section 4 and Algorithm 1), which involves sampling at discrete time steps rather than simulating the continuous CTMC path. This approach allows for more efficient sampling, as it does not require continuous access to the reverse CTMC. Additionally, to ensure bounded score estimates, the authors introduce score clipping as a practical solution for handling extreme values (discussed in Section 5).
summary: The paper  examines theoretical aspects of score-based discrete diffusion models within a Continuous Time Markov Chain (CTMC) framework. The authors aim to address the underexplored convergence properties of these models, especially in discrete state spaces, compared to their continuous counterparts which have been widely studied. Key contributions of the paper include: 1. The authors propose a discrete-time sampling algorithm designed for high-dimensional discrete diffusion tasks. This algorithm leverages score estimators at specific time points to approximate the reverse process of the diffusion model. 2. They provide convergence bounds for the KL divergence and TV distance between the generated sample distribution and the target data distribution. The bounds are derived for cases both with and without early stopping, depending on assumptions about the data distribution's properties. 3.The convergence analysis is performed using a Girsanov-based method, which enables the authors to assess the score estimation error, discretization error, and mixing properties of the forward process. This method is adapted from techniques in continuous diffusion models and tailored to the discrete setting. 4. The paper establishes that their convergence bounds scale nearly linearly with the data dimension, aligning with the best results for continuous models. Additionally, they discuss practical considerations, such as the need for score clipping and early stopping under certain conditions to handle potential score function divergences. 5. The authors compare their method with prior approaches, particularly highlighting differences in sampling efficiency and the elimination of certain assumptions on score estimators, thus broadening the algorithm's applicability in discrete settings.
weaknesses: I don't see major weaknesses of this work, but I do have some comments:
1. Since the authors claim improved sampling efficiency (e.g., fewer function evaluations), would compare actual runtime or convergence speed with other discrete sampling methods (such as the uniformization technique in Chen & Ying) substantiate these claims?
2. Assumption 2 requires the data distribution to have full support and uniform bounds. This may restrict the model.
3. Although the work mentions similarities with continuous diffusion models, there is limited discussion on when to use their discrete CTMC approach versus discretized continuous models for discrete data. 
4. Generalizability to Other State Spaces: The works' algorithm assumes a general state space $[S]^d$, but would it be insightful to discuss how it might extend to more complex or structured discrete spaces, such as graph-based or hierarchical state spaces, which are common in discrete data applications?

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: Please see the weakness section.
soundness: 3
strengths: The paper provides a timely convergence analysis of the discrete diffusion models, which is important in understanding this new class of models (with applications to LMM). I checked most proofs, and they are scientifically correct.
summary: This paper provides the convergence rate of the discrete diffusion models introduced by Lou and Ermon. The authors consider the finite state space $S^d$, extending early analysis by Chen and Ying in the continuous time.
weaknesses: The weaknesses are:

(1) The main idea of proofs are very similar to Chen and Yin, with the key to the proof the representation given by Proposition 1. The differences are: (1) the paper extends the previous results from $\{0,1\}^d$ to $S^d$; (2) the paper considers the issue of discretization. I agree that (2) is important, while (1) seems to me incremental. 

(2) The authors made Assumption 2, which requires the ratio constant $L$ is independent of $d$. I am dubious on this assumption, since the main application of the discrete diffusion models is on the LLM. I would encourage the authors to provide a numerical analysis to show indeed this assumption is valid.

(3) Regarding early stopping: Chen and Yin considers early stopping since they are concerned with the continuous dynamics. It is known that the score matching has large errors near time $0$, and even the continuous dynamics may not be well-defined at $0$. Since the paper studies the discrete scheme, I wonder if there is a particular reason why the authors also consider early stopping. 

(4) Except the error for the initialization, which uses log-Sobolev inequality (more or less expected), the other ingredients in the proof are very similar to the existing approaches to the SDE-based diffusion models. Of course, the authors dealt with CDMC, which is slightly different.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: Can the authors provide more explanation comparing their result to the Chen and Ying result? 

Also, can they provide a comparison between their guarantees and the guarantees for continuous models? I am curious if they are analogous or what the fundamental differences are.
soundness: 4
strengths: The paper is well-written and represents a strong contribution to the generative model literature. The assumptions are weaker than those for existing algorithms. There is a strong case for accepting this paper due to its novel theoretical analysis of an important problem. The theoretical framework given may be useful in analyzing more general settings and motivating further algorithmic improvements.
summary: This work develops an algorithm for score-based diffusion models over a discrete state space. Their new algorithm relies on the uniformization of the CTMC developed by Chen and Ying and discretization in time. The main innovation of the work is theoretical. Using this new algorithm, the authors can derive bounds on the generated samples under less restrictive assumptions than in previous work. The main assumption is an approximate score function, where analogous to the results on continuous denoising diffusion models, the authors are able to develop a bound with early stopping. Under the further assumption of bounded scores for the data distribution, the authors show that early stopping is no longer needed and can derive bounds at $t=0$.
weaknesses: First, It is unclear how tight these bounds are. Can the authors compare these to bounds in the continuous setting? Second, I don’t understand everything in the table, and it would be better to flesh out the comparison with Chen and Ying. In particular, their assumptions are different, can you tell us what they are? Finally, there are no tests of the algorithm in practice. While the theoretical contribution is nice, it remains to be seen if it will have an impact on practice.

Meta-review: This paper offers a convergence analysis of score-based discrete diffusion model when the state space is $[S]^d$, generalizing the prior work of Chen and Ying that handles the case of $\{0,1\}^d$. The work leverages heavily the techniques from Chen and Ying, but also offers new ingredients to handle the generalization. Given the importance of discrete diffusion, the work provides a useful contribution to the theoretical understanding of such models.

Decision: Accept (Poster)