Technical Summary: TUBE: Tangent Upper Bound on Evidence for Discrete Diffusion Language Models

Problem Statement

Log-likelihood is the canonical metric for evaluating the distributional fit of generative models. While Autoregressive Models (ARMs) allow for exact log-likelihood computation due to their fixed decomposition, Discrete Diffusion Models (specifically Masked Diffusion Models, MDMs) and Any-Order Autoregressive Models (AO-ARMs) generally do not. These models define the data distribution by averaging over a latent space of generation orderings (or unmasking trajectories), rendering the marginal likelihood intractable.

Consequently, evaluation for these models relies on the Evidence Lower Bound (ELBO). However, the ELBO provides only a lower bound, leaving the magnitude of the gap between the bound and the true log-likelihood unknown. This ambiguity prevents rigorous comparison between ARMs and diffusion-based models, as it is unclear if the observed performance gap is due to the model architecture or merely the looseness of the ELBO approximation. Existing upper-bound estimators (e.g., CUBO, TVO, IS-VG-B) often suffer from bias when applied to finite-sample Monte Carlo estimates, failing to guarantee a true upper bound in practice.

Methodology: Tangent Upper Bound on Evidence (TUBE)

The authors propose the Tangent Upper Bound on Evidence (TUBE), a variational upper bound on log-likelihood that admits an unbiased Monte Carlo estimator.

Theoretical Foundation

The method relies on the concavity of the logarithm function. Using the tangent line approximation at a point $b$, the inequality $\log a \leq \log b + \frac{a-b}{b}$ holds for all $a, b > 0$.
By treating the true likelihood $p(x)$ as $a$ and a tractable surrogate function $\psi(x)$ as $b$, the authors derive the bound:
$$\log p(x) \leq \text{TUBE}_\psi(x) := \log \psi(x) + \frac{p(x) - \psi(x)}{\psi(x)}$$
Equality holds if and only if $\psi(x) = p(x)$.

Unbiased Estimation

A critical contribution of TUBE is its linearity with respect to the likelihood term $p(x)$. For latent variable models where $p(x) = \mathbb{E}_\pi[p(x|\pi)]$, the term $p(x)$ appears linearly in the TUBE formula. This allows for the construction of an unbiased Monte Carlo estimator:
$$\widehat{\text{TUBE}}_{\psi, K}(x) = \log \psi(x) + \frac{\hat{p}_{\text{model}, K}(x) - \psi(x)}{\psi(x)}$$
where $\hat{p}_{\text{model}, K}(x)$ is the standard Monte Carlo average of $K$ samples of $p(x|\pi)$. Unlike other upper bounds (e.g., CUBO) where a non-linear function (like $\log$) is applied to the Monte Carlo mean (introducing Jensen's inequality bias), TUBE's affine structure preserves the bound direction in expectation.

Surrogate Construction ($\psi$)

The tightness of the bound depends on the proximity of the surrogate $\psi(x)$ to the true $p(x)$. The paper proposes two strategies:

1. Exact Likelihood Surrogate: Using an ARM trained on the same data (or fine-tuned on synthetic data from the diffusion model) as $\psi$.
2. Self-Surrogate: Averaging the conditional likelihoods $p(x|\pi)$ over multiple random orderings $\pi$. This leverages the fact that at the model optimum, the conditional likelihood is close to the full marginal likelihood.

Two-Sided Localization

By combining the standard ELBO (lower bound) with TUBE (upper bound), the method provides a two-sided localization of the true log-likelihood:
$$\text{ELBO}(x) \leq \log p(x) \leq \text{TUBE}_\psi(x)$$

Key Contributions

1. Methodological Innovation: Introduction of TUBE, a variational upper bound that is the first to admit an unbiased, bound-preserving Monte Carlo estimator for discrete diffusion and any-order autoregressive models.
2. Empirical Analysis: Application of TUBE to pretrained Block AO-ARMs and Block MDMs to rigorously evaluate their likelihoods against ARM baselines.
3. Resolution of Evaluation Ambiguity: The ability to localize the true log-likelihood, moving beyond the uncertainty of the ELBO gap.

Experimental Results

The authors evaluated the method on Block Models (BMs) with block sizes $L' \in \{4, 8, 16\}$ on the OpenWebText (OWT) and LM1B datasets.

• Tightness: TUBE consistently provided the tightest upper bound on Perplexity (PPL) compared to competing estimators (CUBO, TVO, IS-VG-B). Notably, CUBO and other biased estimators occasionally violated the expected bound relations (e.g., producing values lower than the ELBO), whereas TUBE maintained the bound.
• Likelihood Gap: The experiments revealed a clear empirical likelihood gap. Across all block sizes and generation regimes (varying Number of Function Evaluations, NFE), the true log-likelihood of AO-ARMs and MDMs was found to be strictly lower than that of standard ARM baselines.
  • For example, on OWT with block size $L'=4$, the exact ARM baseline achieved a PPL of 17.54, while the AO-ARM/MDM models achieved PPLs strictly higher (worse), with the gap narrowing but remaining positive as NFE increased.
• Surrogate Performance: The "Self-Surrogate" ($\psi_M$), which averages over multiple orderings, was found to be the most effective construction for closing the gap between the TUBE estimate and the true likelihood, outperforming external ARM surrogates.

Significance and Claims

The paper claims that TUBE resolves a fundamental evaluation bottleneck in discrete diffusion modeling. By providing a reliable upper bound, it demonstrates that despite the flexibility of random ordering and parallel generation in MDMs and AO-ARMs, ARMs still dominate in terms of likelihood for the models and datasets tested.

The authors emphasize that this finding is robust because it is derived from a two-sided localization that eliminates the uncertainty inherent in ELBO-only evaluations. The work suggests that while diffusion models offer advantages in inference speed and generation quality, they currently lag behind ARMs in distributional fit as measured by log-likelihood. The paper concludes that reliable two-sided estimation enables more rigorous downstream applications, such as policy ratio estimation for Reinforcement Learning and scientific generative modeling, without the ambiguity of biased bounds.