This paper investigates the theoretical properties of discrete diffusion models, which are used to model intrinsically discrete data such as language and graphs. The authors introduce an algorithm that leverages uniformization to implement transitions on random time points, achieving exact sampling from any distribution on a hypercube. Under reasonable assumptions on the learning of the discrete score function, they derive Total Variation (TV) distance and KL divergence guarantees for sampling. The results align with state-of-the-art achievements for diffusion models in \(\mathbb{R}^d\) and highlight the advantages of discrete diffusion models over continuous-space frameworks. The proposed algorithm is efficient, requiring \(O(d\log(d/\epsilon))\) steps to achieve an \(\epsilon\)-error in KL divergence, with a nearly linear dependence on \(d\) and a logarithmic dependence on \(\epsilon\). This work provides the first theoretical analysis of discrete diffusion models, offering insights into their convergence properties and efficiency.This paper investigates the theoretical properties of discrete diffusion models, which are used to model intrinsically discrete data such as language and graphs. The authors introduce an algorithm that leverages uniformization to implement transitions on random time points, achieving exact sampling from any distribution on a hypercube. Under reasonable assumptions on the learning of the discrete score function, they derive Total Variation (TV) distance and KL divergence guarantees for sampling. The results align with state-of-the-art achievements for diffusion models in \(\mathbb{R}^d\) and highlight the advantages of discrete diffusion models over continuous-space frameworks. The proposed algorithm is efficient, requiring \(O(d\log(d/\epsilon))\) steps to achieve an \(\epsilon\)-error in KL divergence, with a nearly linear dependence on \(d\) and a logarithmic dependence on \(\epsilon\). This work provides the first theoretical analysis of discrete diffusion models, offering insights into their convergence properties and efficiency.