Learning Generation Orders for Masked Discrete Diffusion Models via Variational Inference David Fox, Sam Bowyer, Song Liu, Laurence Aitchison, Raul Santos-Rodriguez, Mengyue Yang Abstract Masked discrete diffusion models (MDMs) are a promising new approach to generative modelling, offering the ability for parallel token generation and therefore greater efficiency than autoregressive counterparts. However, achieving an optimal balance between parallel generation and sample quality remains an open problem. Current approaches primarily address this issue through fixed, heuristic parallel sampling methods. There exist some recent learning based approaches to this problem, but its formulation from the perspective of variational inference remains underexplored. In this work, we propose a variational inference framework for learning parallel generation orders for MDMs. As part of our method, we propose a parameterisation for the approximate posterior of generation orders which facilitates parallelism and efficient sampling during training. Using this method, we conduct preliminary experiments on the GSM8K dataset, where our method performs competitively against heuristic sampling strategies in the regime of highly parallel generation. For example, our method achieves 33.1% accuracy with an average of only only 4 generation steps, compared to 23.7-29.0% accuracy achieved by standard competitor methods in the same number of steps. We believe further experiments and analysis of the method will yield valuable insights into the problem of parallel generation with MDMs. 1 Introduction Discrete Diffusion Models (DDMs) 1 have recently emerged as a promising alternative to autoregressive generative models for various tasks such as text 13 , code 6 and biological sequence generation 14 , offering the ability to parallelise token generation for increased efficiency 4 and utilise bi-directional context during generation which has shown to be beneficial in certain tasks where a strict left-to-right dependency is not present in the data 10 . Masked Diffusion Models (MDMs) 1 in particular have established themselves as the most performant class of DDMs, due to their comparatively efficient paramaterisation and conceptually simple set-up 12 ; 11 , as well as their similarity with Autoregressive Models (ARMs), making it possible to initialise training from strong autoregressive baselines 16 . Despite the conceptual benefits and recent empirical progress of DDMs 9 , a consistent barrier to realising their full potential has been optimally balancing efficiency and sample quality by choosing generation orders which use parallelization without violating statistical dependence among token positions 5 . Current approaches attempt to overcome this issue by using heuristic sampling strategies, or by augmenting the generative model with a learned component which chooses token positions to unmask at each step. Heuristic approaches typically use model predicted logits to select tokens based on criteria such as top-k or top probability margin 7 . Learned approaches usually augment the generative model to include a component for selecting token indices which is then trained with a separate loss function 17 , or via reinforcement learning by formulating the generative model as a Markov Decision Process with a policy that chooses token positions to unmask 3 . While these methods have made progress toward achieving the optimal trade-off between generation efficiency and model output quality, we believe there is room for improvement. While heuristic approaches provide good performance at minimal cost, they are potentially too rigid and overly reliant on logit based model confidence estimates, which my be poorly calibrated for this purpose when trained using only binary cross-entropy. Of the learned approaches, the formulation of learned parallel generation orders within the variational inference framework remains underexplored. Hence, the goal of the present work is to investigate a variational inference framework for training an MDM which explicitly factorises the model into components for choosing which token positions to unmask, and which token value to sample given a position. We believe this formulation offers the following benefits which may lead to a method that allows training of an improved unmasking position model which scales to large datasets. Our main contributions are as follows: • We present a probabilistic formulation of a discrete diffusion generative model using variational inference, which explicitly factorises the model into components for choosing which token positions to unmask, and which token value to sample given a position. • We derive the associated ELBO objective, which leverages this model structure to decrease variance of the objective function through Rao-Blackwellisation. • We investigate the use of a paramaterised family of distributions for the approximate posterior generation order which is designed to allow efficient, low variance training. The remainder of this document is structured as follows: In section 2 we discuss necessary background information on masked DDMs, the issue of accurately sampling in parallel, and some current approaches to overcoming this issue. In section 3 we discuss our method, which is motivated by these concerns, and a plan for experiments to test it, which are reported in section 4 and discussed in section 5 . 2 Background 2.1 Masked Discrete Diffusion Models To construct an MDM 12 for a single dimension, we define a forward Markov process \{x_{t}\}_{t\in\left[0,1\right]} , taking values in a discrete set x_{t}\in\{1,\dots,m-1,m\} , where m represents a special ’mask’ token. Letting \mathbf{1} denote a vector of ones and \textbf{x}_{s} the one hot encoding of x_{s} , the forward process transition probabilities between times s