Deterministic Discrete Denoising
Hideyuki Suzuki, Hiroshi Yamashita · 2025
Read Deterministic Discrete Denoising by Hideyuki Suzuki, Hiroshi Yamashita (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20896.txt.
Introduction
Diffusion models make text and images by slowly removing noise, and the steps are usually random. Hideyuki Suzuki, Wataru Kurebayashi, and Hiroshi Yamashita make those steps fixed instead in a 2025 paper. Their method swaps the random reverse chain for a herding algorithm with mildly chaotic dynamics.
Herding drives the state changes in a set, repeatable way. The swap needs no new training and no smooth stand-ins for the discrete states. On text and image tasks, the authors report gains in both speed and sample quality. The method also improves diffusion-based answers to hard combinatorial problems. It is a small change to the sampling stage, offered as a direct replacement that many existing discrete diffusion models could adopt at once.
Catalog record
| CREATOR | Hideyuki Suzuki, Hiroshi Yamashita |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-20896
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deterministic Discrete Denoising Hideyuki Suzuki, Hiroshi Yamashita Abstract We propose a deterministic denoising algorithm for discrete-state diffusion models based on Markov chains. The generative reverse process is derandomized by introducing a variant of the herding algorithm with weakly chaotic dynamics, which induces deterministic discrete state transitions. Our approach is a direct replacement for the stochastic denoising process, requiring neither retraining nor continuous state embeddings. We demonstrate consistent improvements in both efficiency and sample quality on text and image generation tasks. Thus, this simple derandomization approach is expected to enhance the significance of discrete diffusion in generative modeling. Furthermore, our results reveal that deterministic reverse processes, well established in continuous diffusion, can also be effective in discrete state spaces. 1 Introduction Diffusion models have recently achieved remarkable success in generating realistic image and audio data. Their forward process progressively corrupts data with noise, and the models are trained to denoise by inverting the corruption process. Once trained, diffusion models can generate realistic samples from pure noise by iteratively applying the denoising procedure. For continuous data such as images and speech, the reverse denoising process is often implemented as a deterministic algorithm, which exhibits more directed dynamics and enables efficient generation with fewer denoising steps compared to stochastic denoising, as demonstrated by DDIM ( Song et al. 2021 ) . Diffusion models for discrete data are also an important research direction, since many data of interest are inherently discrete, including text, graphs, genomes, and chemical structures. In discrete-state diffusion models, the forward and reverse processes are typically formulated as probabilistic Markov chains on a discrete sample space ( Austin et al. 2021 ) . If the reverse denoising process could be made deterministic, improved performance would be expected, as in the case of continuous models. However, in discrete spaces, naive derandomization as a deterministic mapping aggregates discrete trajectories and reduces sample diversity, which is essential for generative modeling. One promising approach is to embed the discrete sample space into a continuous space and apply continuous diffusion models ( Hoogeboom et al. ; Chen et al. 2023 ; Sahoo et al. 2025 ) . The main advantage of this approach is that it allows the direct use of well-established techniques for continuous diffusion, including deterministic denoising. Nevertheless, denoising in the continuous space requires retraining the model. Moreover, it remains unclear whether discrete data must be embedded into a continuous space for derandomization. In this paper, we propose to directly derandomize the reverse denoising process on discrete sample spaces. The key idea is to introduce a variant of the herding algorithm ( Welling 2009 ; Welling & Chen 2010 ) , which associates auxiliary continuous weight variables with each discrete variable in the sample space. The reverse denoising updates of both discrete and continuous variables are deterministic, and randomness arises solely from their initial states. Since the proposed algorithm derandomizes the state transitions of Markov chains, it serves as a drop-in replacement for the stochastic reverse process without retraining discrete diffusion models. This relation is analogous to DDIM ( Song et al. 2021 ) , which generates samples deterministically using a model trained for DDPM ( Ho et al. 2020 ) . In our experiments on text and image generation, we demonstrate consistent improvements in both efficiency and sample quality. These results reveal that deterministic reverse processes, well established in continuous diffusion, can also be effective in discrete state spaces. In the evaluation, we adopt UDLM ( Schiff et al. 2025 ) , a state-of-the-art discrete-state generative model based on the uniform diffusion process. Our aim in this paper is not to propose a new discrete diffusion model, but to demonstrate how the herding-based algorithm improves the generative process of existing ones. We use the official training, sampling, and evaluation codes of UDLM, replacing only the reverse denoising procedure. This directly shows that our method works as a drop-in replacement without retraining. Moreover, the uniform diffusion process is particularly suitable for our approach, since its reverse process performs self-correction through successive Markov state transitions, making it a natural setting to examine whether derandomizing these transitions can improve efficiency and sample quality. In contrast, masked diffusion has been widely studied as a discrete diffusion model, but its reverse process allows each token to transition only once from the masked state and remain fixed thereafter, fundamentally limiting its dynamics. A related line of work is the deterministic reverse algorithm proposed in Chen et al. 2024 , which performs deterministic state transitions in discrete sample spaces. This approach is effective for masked diffusion, where the transition time is limited. Our work complements this result by showing that deterministic denoising is also beneficial for uniform diffusion models, where state transitions continue throughout the reverse process. Overall, we present a simple yet effective derandomization approach to directly enhance the generative process of existing discrete-state diffusion models, thus strengthening the significance of discrete diffusion in generative modeling. 2 Background 2.1 Discrete Diffusion Models We consider generative models for discrete data represented as a sequence of L categorical tokens. Each token takes one of K categories and is represented as a K -dimensional one-hot vector \bm{x}\in\mathcal{V} , where \mathcal{V}=\{(x_{1},x_{2},\dots,x_{K})^{\top}\in\{0,1\}^{K}\mid\sum_{k=1}^{K}x_{k}=1\} . A sequence of L tokens is denoted by \bm{x}^{(1:L)}=(\bm{x}^{(1)},\bm{x}^{(2)},\dots,\bm{x}^{(L)})\in\mathcal{V}^{L} . The forward noising process in the D3PM framework ( Austin et al. 2021 ) is formulated as a discrete-time Markov chain on \mathcal{V} , which gradually transforms the original data \bm{x}_{0} into noise \bm{x}_{T} . Given the Markov transition matrix Q_{t} at time t , the forward transition is defined as q(\bm{x}_{t}\mid\bm{x}_{t-1})=\mathrm{Cat}(\bm{x}_{t};Q_{t}\bm{x}_{t-1}), (1) where \mathrm{Cat}(\cdot;\bm{p}) denotes the categorical distribution with the probability vector \bm{p} . The Markov transition matrix Q_{t} is designed to gradually transform any categorical distribution into a stationary distribution as t increases. For the uniform noising process, it is given by Q_{t}=(1-\beta_{t})\bm{I}+\beta_{t}\frac{1}{K}\bm{1}\bm{1}^{\top}, (2) where \beta_{t}\in(0,1) is a noise schedule. For the absorbing noising process, it is defined as Q_{t}=(1-\beta_{t})\bm{I}+\beta_{t}\bm{x}_{\mathrm{mask}}\bm{1}^{\top}, (3) where \bm{x}_{\mathrm{mask}} is the one-hot vector representing the absorbing category. In both cases, the Markov transition matrix from time s to t , Q_{t}Q_{t-1}\dots Q_{s+1} , admits a closed-form expression for arbitrary s<t , which can be extended to non-integer times. This property is exploited to improve the efficiency of training and sampling ( Sahoo et al. 2024 ; Schiff et al. 2025 ) . The reverse denoising process is also formulated as a discrete-time Markov chain on \mathcal{V}^{L} . A neural network model parameterized by \theta is trained to predict \tilde{\bm{x}}^{(1:L)}_{0} , an estimate of the original data \bm{x}^{(1:L)}_{0} , from noisy data \bm{x}^{(1:L)}_{t} at time t . Training is performed by minimizing a variational upper bound (NELBO) on the negative log-likelihood ( Austin et al. 2021 ; Schiff et al. 2025 ) . The transition probability p_{\theta}(\bm{x}_{t-1}\mid\bm{x}^{(1:L)}_{t},t) of the reverse process is then computed from the predicted original data \tilde{\bm{x}}^{(1:L)}_{0} and the forward transition matrix Q_{t} . By iterating this Markov transition from pure noise \bm{x}^{(1:L)}_{T} sampled from the stationary distribution, the reverse process generates a sample \bm{x}^{(1:L)}_{0} . Namely, each denoising step reduces to sampling from the categorical distribution \mathrm{Cat}(\bm{x}_{t-1};\bm{p}_{t-1}) with probability vector \bm{p}_{t-1}=p_{\theta}(\bm{x}_{t-1}\mid\bm{x}^{(1:L)}_{t},t) . This is typically implemented as a probabilistic procedure using the Gumbel-max trick. However, sampling does not necessarily have to be