{"ID":2868475,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16756","arxiv_id":"2509.16756","title":"Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees","abstract":"Discrete diffusion models have recently gained significant prominence in applications involving natural language and graph data. A key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, $τ$-leaping samplers have become particularly popular due to their theoretical and empirical success. However, existing theoretical analyses of $τ$-leaping often rely on somewhat restrictive and difficult-to-verify regularity assumptions, and their convergence bounds contain quadratic dependence on the vocabulary size. In this work, we introduce a new analytical approach for discrete diffusion models that removes the need for such assumptions. For the standard $τ$-leaping method, we establish convergence guarantees in KL divergence that scale linearly with vocabulary size, improving upon prior results with quadratic dependence. Our approach is also more broadly applicable: it provides the first convergence guarantees for other widely used samplers, including the Euler method and Tweedie $τ$-leaping. Central to our approach is a novel technique based on differential inequalities, offering a more flexible alternative to the traditional Girsanov change-of-measure methods. This technique may also be of independent interest for the analysis of other stochastic processes.","short_abstract":"Discrete diffusion models have recently gained significant prominence in applications involving natural language and graph data. A key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, $τ$-leaping samplers have become particularly popular due to their theoretical and empiric...","url_abs":"https://arxiv.org/abs/2509.16756","url_pdf":"https://arxiv.org/pdf/2509.16756v2","authors":"[\"Yuchen Liang\",\"Yingbin Liang\",\"Lifeng Lai\",\"Ness Shroff\"]","published":"2025-09-20T17:42:29Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"eess.SP\"]","methods":"[\"Diffusion Model\"]","has_code":false}