Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on $\tau$-leaping-based samplers. We establish sharp convergence guarantees for attaining $\varepsilon$ accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that $\tau$-leaping achieves an iteration complexity of order $\tilde{O}(d/\varepsilon)$, with $d$ the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size $S$ and improving existing bounds by a factor of $d$; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified $\tau$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by $d \log S$ but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.

Consistency models, which were proposed to mitigate the high computational overhead during the sampling phase of diffusion models, facilitate single-step sampling while attaining state-of-the-art empirical performance. When integrated into the training phase, consistency models attempt to train a sequence of consistency functions capable of mapping any point at any time step of the diffusion process to its starting point. Despite the empirical success, a comprehensive theoretical understanding of consistency training remains elusive. This paper takes a first step towards establishing theoretical underpinnings for consistency models. We demonstrate that, in order to generate samples within $\varepsilon$ proximity to the target in distribution (measured by some Wasserstein metric), it suffices for the number of steps in consistency learning to exceed the order of $d^{5/2}/\varepsilon$, with $d$ the data dimension. Our theory offers rigorous insights into the validity and efficacy of consistency models, illuminating their utility in downstream inference tasks.

This paper presents new theoretical insights into how diffusion generative models adapt to low-dimensional structure in data distributions. We study two widely used samplers — the denoising diffusion probabilistic model (DDPM) and the denoising diffusion implicit model (DDIM) — and analyze their convergence behavior under the assumption of accurate score estimates. Our main result shows that both DDPM and DDIM require at most $O(k/\varepsilon)$ iterations (up to logarithmic factors) to generate samples that are $\varepsilon$-close to the target distribution in total variation distance, where $k$ captures an intrinsic low-dimensional structure of the distribution. Importantly, our theory holds without assuming smoothness or log-concavity. These results provide the first rigorous guarantees for the low-dimensional adaptation capability of DDIM-type samplers, and significantly improve upon prior TV-based convergence bounds for DDPM. Our analysis also highlights the role of discretization coefficients in exploiting low-dimensional structure, and establishes lower bounds that justify the optimality of commonly used parameter choices originally proposed by Ho et al. (2020); Song et al. (2020).

As one of the three main scenarios of 5G, massive machine-type communications (mMTC) is expected to play an essential role in the future. However, the limited battery of the machine-type communication devices (MTCDs) restricts the network performance. Unmanned aerial vehicles (UAVs) attract more attention recently in cellular networks. The collaboration between the UAV and MTCDs has been a crucial topic to enhance the network performance. In this paper, an adaptive and cost-efficient model is proposed to collect data from MTCDs in a large area assisted by the UAVs. We propose the strategies for higher energy efficiency of MTCDs and longer lifetime of the network based on the model. According to the strategies, we propose a Global Energy-efficient ant colony optimization (ACO) routing algorithm for UAV-assisted mMTC networks (GEAU) to reduce the energy consumption and prolong the lifetime of the networks. Furthermore, in order to reduce the complexity, we propose a practical algorithm with similar performances. Simulations are carried out and illustrate that the proposed algorithms have superior performances compared with existing works.