Official Review · ICLR 2025

This paper proposes a reparameterization of the absorbing discrete diffusion, based upon the finding that the concrete score can be decomposed into a time-independent conditional probability of clean data, and a time dependent but data independent term. Therefore, this paper proposes a new network architecture, that removes the time dependency, and add softmax layers to project the output layer to the probability space. The authors argue that the removed time dependency can accelerate the sampling process by caching the network output before it changes. The total changes would be at most $d$ instead of $n$, and the total number of NFEs reduces to $n(1 - (1 - \frac{1}{n}))^l)$. The authors proposed a novel reparameterization of absorbing discrete diffusion, decoupled the time-independent and time-dependent part. This discovery allows for better understanding of discrete diffusions, and the previous reparameterization in SEDD. The proposed reparameterization allows for a simplified network architecture and efficient sampling. Moreover, the authors proposed the unification of absorbing diffusion with the any-order autoregressive model. First of all, the proposed algorithm are specified to absorbing discrete diffusion, and does not fit in the other widely used discrete diffusion model, multinomial diffusion. The authors did not discuss if or why not their methodology can not be applied to multinomial diffusion. There are existing works that have reduced the sampling complexity of discrete diffusions, including absorbing and multinomial diffusion, e.g., Chen et al. 2024 [1]. [1] also made use of the fact that during the reverse sampling process, computation is only required when tokens changes, thus reducing the computation from number of diffusion steps to number of tokens. Also [1] proposed a similar NFE estimation in Theorem D.1, which is the same as (3.4) in this paper. However, the authors did not discuss or mention the relationship with [1]. Also inspired from [1], the sampling complexity essentially does not comes from whether you have $t$ in your score network or not, but comes from times that you change tokens. Even for SEDD based discrete diffusion network, it is also possible to only calculate when change is required, and skip calculation when $x$ does no change. For example, if using [1] for sampling, does RADD still have any advantage over SEDD? [1] Fast Sampling via Discrete Non-Markov Diffusion Models. See weaknesses.