DUEL: Exact Likelihood for Masked Diffusion via Deterministic Unmasking

The position selection policy $\pi$ can be random or deterministic. Nearly all leading MDM sampling strategies use deterministic selection—a fixed rule that maps the current sequence state to a set of positions, with no randomness involved. This includes the sampling strategies used by most fast samplers and state-of-the-art MDMs (e.g. LLaDA).

We call such a rule an unmasking rule $F$. Given a partially-revealed sequence $\mathbf{z}$, the rule $F(\mathbf{z})$ returns a non-empty subset of masked positions to unmask:

$\emptyset \neq F(\mathbf{z}) \subseteq \mathcal{M}(\mathbf{z})$

Since the token probabilities $\mathbf{P} = \mathrm{softmax}(x_\theta(\mathbf{z}))$ are deterministic functions of $\mathbf{z}$, rules depending on $\mathbf{P}$ (like greedy confidence) are valid.

A DUEL sampler generates samples—but what distribution does it sample from? To make this explicit, we build on the any-order autoregressive model (AO-ARM) interpretation of MDMs. This formulation decomposes generation into position-selection and token-prediction steps, allowing us to write down the joint probability of generating a sequence via any ordered partition.

Ordered Partitions

To formalize the sequence of unmasking steps during generation, we introduce ordered partitions. An ordered partition $\sigma = (\sigma_1, \ldots, \sigma_T)$ is a tuple of non-empty subsets of $\{1, \ldots, L\}$ satisfying:

1. Pairwise disjoint: $\sigma_s \cap \sigma_t = \emptyset$ for all $s \neq t$
2. Exhaustive: $\sigma_1 \cup \cdots \cup \sigma_T = \{1, \ldots, L\}$

Each $\sigma_t$ records which positions are revealed at step $t$, and $T$ denotes the total number of steps.

Ordered partitions capture both sequential and parallel unmasking—a distinguishing feature of MDMs over ARMs:

• Sequential unmasking: Each $\sigma_t$ is a singleton ($|\sigma_t| = 1$), giving $T = L$ steps
• Parallel unmasking: Parts contain multiple positions, giving $T < L$ steps

We write $\mathbf{x}_{<\sigma_t}$ for the partial sequence where positions in $\sigma_1 \cup \cdots \cup \sigma_{t-1}$ are revealed and all others remain masked.

The Induced Distribution

The AO-ARM formulation decomposes generation into position-selection and token-prediction steps. The joint probability $p_\theta(\mathbf{x}, \sigma)$ measures the probability that sequence $\mathbf{x}$ was generated via a specific unmasking trajectory $\sigma$. To obtain the data likelihood, we marginalize (sum) over all possible ordered partitions:

$p_\theta(\mathbf{x}) = \sum_{\sigma} p_\theta(\mathbf{x}, \sigma)$

This defines the distribution induced by any unmasking policy $\pi$:

Standard MDM metrics fail to provide proper likelihood evaluation. The ELBO is a loose bound (not exact) computed under the wrong distribution (uniform, not test-time). Generative perplexity avoids both issues but introduces external model bias.

DUEL enables principled comparison of unmasking rules by fixing the denoiser $x_\theta$ and varying only the rule $F$. This comparison is impossible with the ELBO (which ignores the unmasking policy entirely) and unreliable with generative perplexity (which depends on a biased reference model).

Comparing Fast Samplers

Fast samplers differ in their unmasking rule $F$. Aggressive rules unmask many positions per step for speed; conservative rules unmask fewer for quality. DUEL enables principled comparison by measuring exact likelihood under the test-time distribution. Other metrics—the ELBO, generative perplexity, entropy, MAUVE—are unreliable: the ELBO ignores the unmasking policy, generative perplexity depends on a biased reference model, and entropy/MAUVE have other shortcomings.

DUEL perplexity by unmasking rule on OWT. Model: BD3-LM ($L'$=16). ELBO: $\leq$23.52.

*Adaptive NFE; thresholds chosen to match target step counts.

Why Other Metrics Fail

We compare DUEL perplexity against three sample-based metrics—generative perplexity, entropy, and MAUVE—and find each unreliable:

• Generative perplexity rankings are inconsistent across NFE budgets. Strikingly, left-to-right achieves the lowest generative perplexity at 128 NFE despite having the worst DUEL perplexity. The explanation: left-to-right produces low-entropy, repetitive text at low NFE, and autoregressive evaluators like GPT-2 reward such degenerate output with low perplexity. Generative perplexity also distorts magnitude, showing 30–40× degradation from 1024 to 128 NFE versus 6–11× under DUEL.
• Entropy confirms the degeneracy: left-to-right drops to ~4.2 bits at low NFE (repetitive text), while probability margin and greedy confidence maintain ~4.8–5.0 bits (diverse output). However, entropy alone cannot rank samplers—it measures diversity, not quality.
• MAUVE saturates near zero at low NFE for all rules, providing almost no discriminative signal. It is most useful for distinguishing high-quality regimes, not for comparing degraded generation.

Figure: Left: DUEL perplexity yields consistent rankings. Right: Generative perplexity rankings cross repeatedly.

Oracle Perplexity

Since different rules yield different likelihoods, we ask: what is the best possible perplexity achievable over all orderings? The oracle perplexity answers this by exhaustively searching all permutations and selecting the one that maximizes likelihood for each sequence. For BD3-LM ($L'=4$), we search all $4!=24$ permutations per block. This represents an upper bound on MDM performance—the best a model could achieve if it always chose the optimal unmasking order.