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

1AXXX   2Applied AI Institute   3HSE University   4MIRAI
Accepted at ICML 2026 (SPIGM & FoGen Workshops)
TUBE method: latent orders, intractable likelihood, and the tangent upper bound

Overview of TUBE. Left: the log-likelihood of masked / any-order diffusion models is intractable, because it marginalizes over all latent generation orders $\pi$. Right: the Tangent Upper Bound on Evidence (TUBE) is a tractable, unbiasedly-estimable upper bound that, together with the ELBO, two-sidedly localizes the true log-likelihood, $\;\mathrm{ELBO}(x)\le \log p(x)\le \mathrm{TUBE}_\psi(x)$.

Abstract

Log-likelihood is a standard metric for evaluating generative models. Unfortunately, in contrast to autoregressive models (ARMs), discrete diffusion models generally do not admit exact computation of this quantity. Existing evaluations, therefore, rely on the evidence lower bound (ELBO), leaving unclear how much higher the true value may be. We address this by introducing the Tangent Upper Bound on Evidence (TUBE), a variational upper bound on log-likelihood that admits an unbiased Monte Carlo estimator. Our TUBE extends across latent-variable models, including masked diffusion models (MDMs), any-order ARMs (AO-ARMs), and block variants of both. Applied to block MDMs and block AO-ARMs, TUBE reveals our key empirical finding that these models lie strictly below the exact ARM baseline, showing that ARMs still dominate in likelihood.

A Unified View via Latent Generation Orders

Masked diffusion and any-order autoregressive models build a sequence by progressively unmasking its positions. The order in which positions are filled is itself a latent variable: the same sentence can be produced by many different generation orders, and the model likelihood averages over all of them. This is precisely why the likelihood is intractable — unlike a left-to-right autoregressive model, there is no single order to read it off from.

This latent-order view unifies models that look different on the surface. An any-order ARM commits one token per step, whereas a multi-token (block) diffusion model can commit several tokens at once — or none — per step. Both are simply different distributions over generation orders under one framework, which is exactly the setting our bound is designed to evaluate.

Latent generation orders: any-order ARM vs multi-token MDM unmasking tokens step by step
Two models under one lens. At each denoising step the newly generated token(s) light up: an any-order ARM (left) reveals one token per step, a multi-token MDM (right) reveals a block of tokens per step. Both realize the same sequence through a latent generation order.

Method: A Tangent Upper Bound

Our method of constructing an upper bound on $\log p(x)$ rests on the concavity of $\log a$ as a function of $a$, and on the tangent majorization of $\log a$ by its first-order Taylor expansion at a point $b$, namely $\;\log a \le \log b + \frac{a-b}{b}\;$ for all $a,b>0$. Instantiating this at $a=p(x)$ and a tractable surrogate $b=\psi(x)$ yields the Tangent Upper Bound on Evidence (TUBE):

$\displaystyle \log p(x) \;\le\; \mathrm{TUBE}_\psi(x) \;:=\; \log\psi(x) + \frac{p(x)-\psi(x)}{\psi(x)}$

with equality iff $\psi(x)=p(x)$.

Two-sided localization of log-likelihood

TUBE is linear in the model likelihood, so it admits an unbiased Monte-Carlo estimator that preserves the bound. Together with the ELBO, it brackets the true log-likelihood from both sides:

$\displaystyle \mathrm{ELBO}(x) \;\le\; \log p(x) \;\le\; \mathrm{TUBE}_\psi(x)$

Results

We evaluate pretrained block-diffusion models (block AO-ARMs and block MDMs) at block sizes $L'\in\{4,8,16\}$. On both OWT and LM1B, in every configuration the AO-ARM / MDM perplexity lies strictly above the exact ARM baseline — ARMs still dominate in likelihood across all block sizes and generation regimes. The gap to ARM shrinks as the number of function evaluations (NFE) grows. Among upper estimators, TUBE is the only bound-preserving one: TVO and IS-VG-B sit above $\mathrm{ELBO}_K$ once NFE $\ge$ 2, and CUBO's bias makes it unreliable as well.

Table 1. Test perplexity ($\downarrow$) on OWT. $\mathrm{PPL}=\exp(-\log p_{\mathrm{model}}(x))$. Exact ARM baseline: 17.54 PPL. Std over 10 ordering subsets omitted for clarity; Gap $=\mathrm{TUBE}-\mathrm{ARM}>0$ — the diffusion-LM PPL stays strictly above the ARM baseline.
$L'$Regime Biased upper estimators Ours References Gap
CUBO$_{\beta=2}$TVO$_U$IS-VG-B TUBE $\mathrm{ELBO}_K$
4NFE=197.7897.7897.7897.7897.7880.24
NFE=224.3427.6829.11≥21.55≤27.404.01
NFE=419.7821.8922.52≥19.16≤21.631.62
AO-ARM17.5018.5518.76≥17.7418.46*0.20
8NFE=1221.54221.54221.54221.54221.54204.00
NFE=229.0433.4134.95≥24.32≤32.636.78
NFE=420.9023.5424.15≥20.23≤23.252.69
NFE=818.8520.8321.17≥19.15≤20.671.61
AO-ARM17.9519.3119.46≥18.67≤19.241.13
16NFE=1398.63398.63398.63398.63398.63381.09
NFE=235.8039.8041.93≥22.50≤38.434.96
NFE=422.8925.2125.96≥19.03≤24.751.49
NFE=819.5921.3821.77≥18.44≤21.140.90
NFE=1618.4419.9820.26≥18.22≤19.830.68
AO-ARM18.0819.3919.56≥18.47≤19.300.93
Test perplexity with different psi choices on OWT
Test perplexity ($\downarrow$) with different $\psi$ choices on OWT. We report $\mathrm{PPL}=\exp(-\log p_{\mathrm{model}}(x))$. The bar plot reports standard deviations over 10 repeated ordering samples with different random seeds. The dotted gold reference line shows $\mathrm{ELBO}_K$.
Per-block per-token NLL on LM1B
Per-block per-token NLL on LM1B. ARM (dark gray), per-block ELBO (light gray), and TUBE (blue dashed) versus block index $b$, for $L'\in\{4,8,16\}$. Insets zoom on the first four blocks. The ordering $\mathrm{ARM}\le\mathrm{TUBE}_{\psi_{B,K}}\le\mathrm{ELBO}$ holds at every block.

Comparison of Likelihood Estimators

We call an empirical estimator bound-preserving if its expectation provably preserves the bound direction. Prior upper-bound estimators (CUBO, TVO, IS-VG-B) apply a nonlinear $\log$ or self-normalized weights to a Monte-Carlo mean, so by Jensen’s inequality their finite-sample expectation can break the bound (terms in red). TUBE is linear in the model likelihood, so its Monte-Carlo estimator stays bound-preserving.

Table 2. Estimators for various bounds on log-likelihood for latent-variable models. Bound-breaking terms are highlighted in red; TUBE’s estimator is bound-preserving.
BoundTypeEmpirical estimatorBound-preserving?
ELBOLower$\log p_{\mathrm{model}}(x\mid\pi^{(1)})$✓
$\mathrm{ELBO}_K$Lower$\log\!\left(\tfrac1K\sum_{k=1}^K p_{\mathrm{model}}(x\mid\pi^{(k)})\right)$✓
$\mathrm{CUBO}_{\beta\ge1}$Upper$\tfrac1\beta\,{\color{#C0392B}{\log}}\!\left(\tfrac1K\sum_{k=1}^K p_{\mathrm{model}}(x\mid\pi^{(k)})^{\beta}\right)$✗
$\mathrm{TVO}_\Lambda^{U}$Upper$\tfrac1\Lambda\sum_{\lambda=1}^\Lambda\sum_{k=1}^K {\color{#C0392B}{\bar w_k^{(\beta_\lambda)}}}\,\log p_{\mathrm{model}}(x\mid\pi^{(k)})$✗
IS-VG-BUpper$\tfrac1{n_p}\sum_{j=1}^{n_p}{\color{#C0392B}{\log}}\!\left(\tfrac1s\sum_{i=1}^s p_{\mathrm{model}}(x\mid\pi^{(j,i)})\right)+{\color{#C0392B}{\log}}\!\left(\tfrac1{n_p}\sum_j \frac{\sum_i p_{\mathrm{model}}(x\mid\tilde\pi^{(j,i)})}{\sum_i p_{\mathrm{model}}(x\mid\pi^{(j,i)})}\right)$✗
TUBE (Ours)Upper$\log\psi(x)+\dfrac{\tfrac1K\sum_{k=1}^K p_{\mathrm{model}}(x\mid\pi^{(k)})-\psi(x)}{\psi(x)}$✓

Where prior estimators break the bound

Empirically, each biased estimator violates its nominal upper bound across a large region of its hyperparameters: red-bordered cells mark configurations whose value exceeds $\mathrm{ELBO}_K$ and therefore break the bound. TUBE has no such region — it is bound-preserving by construction.

CUBO$_\beta$ diagnostic on OWT

CUBO$_\beta$
orderings $\times$ Rényi $\beta$

TVO diagnostic on OWT

TVO
orderings $\times$ partitions

IS-VG-B diagnostic on OWT

IS-VG-B
orderings $\times$ pairs

Baseline diagnostics on OWT ($L'\in\{4,8,16\}$, top to bottom). Red-bordered cells exceed $\mathrm{ELBO}_K$ and break the upper bound; the valid region shrinks as orderings decrease or the estimator’s hyperparameter grows. TUBE has no violating region.

BibTeX

@article{ivanov2026tube,
  title   = {TUBE: Tangent Upper Bound on Evidence for Discrete Diffusion Language Models},
  author  = {Ivanov, Arseny and Kholkin, Sergei and Gromadskii, Vladislav and
             Ksenofontov, Grigoriy and Oseledets, Ivan and Korotin, Alexander},
  journal = {arXiv preprint arXiv:2605.24292},
  year    = {2026}
}