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

# Tangent Upper Bound on Evidence for Discrete Diffusion Language Models
Source: [https://arxiv.org/html/2605.24292](https://arxiv.org/html/2605.24292)
Arseny Ivanov1,2,3,Sergei Kholkin2,Vladislav Gromadskii2, Grigoriy Ksenofontov2,4,Ivan Oseledets1,2,Alexander Korotin2,1

###### 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 theTangent 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\.

††footnotetext:1AXXX, Russia;2Applied AI Institute, Moscow, Russia;3HSE University, Moscow, Russia\.4MIRAI, Russia\.
∗Correspondence to: Arseny Ivanov<a5r5s5e5n5y@gmail\.com\>, Alexander Korotin<iamalexkorotin@gmail\.com\>![Refer to caption](https://arxiv.org/html/2605.24292v1/x1.png)Figure 1:A tight tangent upper bound onlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)\.Our TUBE bounds the intractable marginal from above using a tractable surrogateψ\\psi, with equality atψ=pmodel\\psi=p\_\{\\mathrm\{model\}\}\.## 1Introduction

*Autoregressive models*\(ARMs\) remain a central paradigm in language modeling, supported by strong empirical scaling behavior in large\-scale settings\(Kaplan et al\.,[2020](https://arxiv.org/html/2605.24292#bib.bib18); Hoffmann et al\.,[2022](https://arxiv.org/html/2605.24292#bib.bib14)\)\. However, this efficiency arises from imposing a fixed autoregressive decomposition, which makes generation inherently order\-dependent\. At the same time, the best ordering typically depends on the domain and task, and learned or alternative orderings can outperform standard fixed choices in practice\(Li et al\.,[2021](https://arxiv.org/html/2605.24292#bib.bib24); Wang et al\.,[2025b](https://arxiv.org/html/2605.24292#bib.bib49)\)\. This has motivated a growing line of work on*any\-order autoregressive models*\(AO\-ARMs\)\(Uria et al\.,[2014](https://arxiv.org/html/2605.24292#bib.bib46); Shih et al\.,[2022](https://arxiv.org/html/2605.24292#bib.bib43)\)and related*masked diffusion models*\(MDMs\)\(Austin et al\.,[2021](https://arxiv.org/html/2605.24292#bib.bib3); Shi et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib42); Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37)\), which both replace a single fixed decomposition with a probabilistic family of generation orderings\.

Despite their different theoretical constructions, AO\-ARMs and MDMs both generalize beyond left\-to\-right order by repeatedly selecting token positions at random and filling in the corresponding values\. MDMs further extend this procedure by allowing multiple tokens to be generated in a single step, enabling faster inference\. Beyond these fully random ordering schemes, blockwise generation provides a mixed alternative\(Arriola et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib2)\), using a fixed autoregressive ordering over blocks and a random ordering within each block\. This retains block\-level autoregressive structure, enabling techniques such as KV caching\. Together, these features make AO\-ARMs and MDMs viable alternatives to strictly autoregressive generation\. More broadly, both have been applied beyond standard left\-to\-right language modeling to other discrete domains, including images\(Pang et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib32); Austin et al\.,[2021](https://arxiv.org/html/2605.24292#bib.bib3)\), graphs\(Kelvinius and Lindsten,[2024](https://arxiv.org/html/2605.24292#bib.bib20); Seo et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib40)\), molecular sequences\(Lee et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib23)\), and vector\-quantized image representations\(Gu et al\.,[2022](https://arxiv.org/html/2605.24292#bib.bib11)\)\. In language modeling, recent large\-scale MDMs have been shown to be competitive in the generation quality to ARMs\(Nie et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib28); Bie et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib4); Ye et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib50); Karimi Monsefi et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib19)\)\.

At the same time, principledevaluationof such models calls forlog\-likelihood, which remains the canonical measure of distributional fit\. While ARM enables exact log\-likelihood evaluation, for AO\-ARM and MDM, on the other hand, this quantity is typically intractable\. It is instead replaced by the*evidence lower bound*\(ELBO\), or related approximations\(Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37); Haxholli et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib12); Jeon et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib16)\)\. However, the ELBO does not indicate how much higher the true log\-likelihood may be\. As a result, ELBO\-based evaluation alone cannot reliably assess the likelihood of AO\-ARMs and MDMs, nor support rigorous comparison with ARM baselines\.

Recent work has made this issue increasingly explicit both for MDMs and for broader classes of latent\-variable models\. For MDMs, exact log\-likelihood evaluation is available only in special cases, such as deterministic unmasking\(Turok et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib45)\), while recent work has also proposed upper\-bound estimator\(Wang et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib47)\)\. In parallel, the variational\-inference literature has developed upper\-bound approaches for estimating log\-likelihood in general latent\-variable models\(Dieng et al\.,[2017](https://arxiv.org/html/2605.24292#bib.bib9); Struski et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib44)\)\. In practice, however, exact methods apply only in narrow fixed\-order settings, and upper\-bound estimators are hard to use reliably because they become biased when a nonlinear function is applied after Monte Carlo approximation\. This leaves open the problem of reliable finite\-sample log\-likelihood estimation for AO\-ARMs and MDMs, which we address in this paper\. Ourcontributionsare as follows:

- •Method\.We propose the*Tangent Upper Bound on Evidence*\(TUBE\), a variational pointwise upper bound on the log\-likelihood with a tractable surrogate and an unbiased Monte Carlo estimator \(§[3](https://arxiv.org/html/2605.24292#S3)\)\. Together with the ELBO, TUBE yields a two\-sided localization of the log\-likelihood\.
- •Analysis\.We evaluate pretrained block AO\-ARMs and MDMs and identify a clear empirical likelihood gap relative to standard ARM baselines \(§[5](https://arxiv.org/html/2605.24292#S5)\)\.

Notation\.We write𝒱=\{1,…,V\}L\\mathcal\{V\}\\\!=\\\!\\\{1,\\ldots,V\\\}^\{L\}for the space of length\-LLtoken sequences andx=\(x1,…,xL\)∈𝒱x\\\!=\\\!\(x^\{1\},\\ldots,x^\{L\}\)\\\!\\in\\\!\\mathcal\{V\}for a data sample\. We useppto denote distributions, with subscripts indicating the corresponding distribution when needed, e\.g\.,pmodelp\_\{\\mathrm\{model\}\}\. The generation ordering is denoted byπ\\pi\. By𝒮\\mathcal\{S\}we denote single\-token orderings, where each step reveals one position, and𝒢\\mathcal\{G\}denotes grouped orderings, where a step may reveal multiple positions\. For an index setπt\\pi\_\{t\}at stept∈\{1,…,T\}t\\in\\\{1,\\dots,T\\\},xπtx^\{\\pi\_\{t\}\}denotes the tokens ofxxat positions inπt\\pi\_\{t\}, andπ<t\\pi\_\{<t\}denotes the positions revealed before that step\.

## 2Background

In this section, we first recall ARMs, including their definition and training procedure \(§[2\.1](https://arxiv.org/html/2605.24292#S2.SS1)\)\. We then generalize this view to AO\-ARMs \(§[2\.2](https://arxiv.org/html/2605.24292#S2.SS2)\) and relate them to MDMs \(§[2\.3](https://arxiv.org/html/2605.24292#S2.SS3)\)\. Finally, we introduce block variants of the latter two \(§[2\.4](https://arxiv.org/html/2605.24292#S2.SS4)\) and discuss the challenges of likelihood evaluation \(§[2\.5](https://arxiv.org/html/2605.24292#S2.SS5)\)\.

### 2\.1Autoregressive models \(ARM\)

We consider the problem of generating a sequencex=\(x1,…,xL\)∈𝒱x=\(x^\{1\},\\dots,x^\{L\}\)\\in\\mathcal\{V\}of lengthLL, where eachxlx^\{l\}denotes a token\. ARMspARM​\(x\)p\_\{\\text\{ARM\}\}\(x\)model this sequence by generating one token at each stept∈\{1,…,L\}t\\in\\\{1,\\dots,L\\\}according to a fixed generation orderπ∈𝒮\\pi\\in\\mathcal\{S\}:

pARM​\(x\)=p​\(xπ1,…,xπL\)=p​\(xπ1\)​…​p​\(xπL\|xπL−1,…,xπ1\)=∏t=1Lp​\(xπt\|xπ<t\),p\_\{\\text\{ARM\}\}\(x\)=p\(x^\{\\pi\_\{1\}\},\\dots,x^\{\\pi\_\{L\}\}\)=p\(x^\{\\pi\_\{1\}\}\)\\dots p\(x^\{\\pi\_\{L\}\}\|x^\{\\pi\_\{L\-1\}\},\\dots,x^\{\\pi\_\{1\}\}\)=\\prod\_\{t=1\}^\{L\}p\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\),\(1\)whereπt\\pi\_\{t\}denotes the single position generated at steptt, so the full sequencexxis generated inLLsteps\.

For ARMs, log\-likelihood can be evaluated directly due to the fixed decomposition in \([1](https://arxiv.org/html/2605.24292#S2.E1)\):

log⁡pARM​\(x\)=∑t=1Llog⁡p​\(xπt\|xπ<t\)\.\\displaystyle\\log p\_\{\\text\{ARM\}\}\(x\)=\\sum\_\{t=1\}^\{L\}\\log p\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\)\.\(2\)Common choices ofπ\\piinclude left\-to\-right orderings for text\(Radford and Narasimhan,[2018](https://arxiv.org/html/2605.24292#bib.bib35)\)and raster\-scan orderings for images\(Chen et al\.,[2020](https://arxiv.org/html/2605.24292#bib.bib7)\)\. Fixed orderings make training and log\-likelihood evaluation tractable\. However, they force the model to generate variables in one prescribed order, even when other orders may be equally natural or more suitable for the data\.

![Refer to caption](https://arxiv.org/html/2605.24292v1/x2.png)Figure 2:AO\-ARM and MDM\.Both definepmodel​\(x\)p\_\{\\mathrm\{model\}\}\(x\)via a latent generation orderingπ\\pi\. AO\-ARM reveals one token per step \(π∈𝒮\\pi\\in\\mathcal\{S\}\)\. MDM allows zero, one, or many tokens per step \(π∈𝒢\\pi\\in\\mathcal\{G\}\)\.
### 2\.2Any\-order autoregressive models \(AO\-ARM\)

To reduce dependence on a fixed order, AO\-ARMs\(Uria et al\.,[2014](https://arxiv.org/html/2605.24292#bib.bib46); Shih et al\.,[2022](https://arxiv.org/html/2605.24292#bib.bib43)\)model the data distribution by averaging over autoregressive decompositions induced by different orderings:

pAO\-ARM​\(x\)=𝔼π∼p​\(π\)​\[p​\(x\|π\)\]=𝔼π∼p​\(π\)​\[∏t=1Lp​\(xπt\|xπ<t\)\],p\_\{\\text\{AO\-ARM\}\}\(x\)=\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[p\(x\|\\pi\)\\right\]=\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[\\prod\_\{t=1\}^\{L\}p\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\)\\right\],\(3\)wherep​\(π\)p\(\\pi\)is typically a uniform distribution over orderingsπ∈𝒮\\pi\\in\\mathcal\{S\}, and generation takesLLsteps\.

From this perspective, AO\-ARMs can be viewed as latent\-variable models in which the orderingπ\\piis latent, thereby increasing modeling flexibility\. Unfortunately, exact log\-likelihood computation is generally infeasible due to the large size of𝒮\\mathcal\{S\}\. One may therefore approximate the expectation in \([3](https://arxiv.org/html/2605.24292#S2.E3)\) using Monte Carlo, but placing this approximation inside the logarithm yields a biased estimator of the log\-likelihood\. Thus, in previous works\(Uria et al\.,[2014](https://arxiv.org/html/2605.24292#bib.bib46); Hoogeboom et al\.,[2022](https://arxiv.org/html/2605.24292#bib.bib15)\), log\-likelihood estimation is typically based on ELBO:

log⁡pAO\-ARM​\(x\)=log⁡𝔼π∼p​\(π\)​\[∏t=1Lp​\(xπt\|xπ<t\)\]≥𝔼π∼p​\(π\)​\[∑t=1Llog⁡p​\(xπt\|xπ<t\)\]\.\\log p\_\{\\text\{AO\-ARM\}\}\(x\)=\\log\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[\\prod\_\{t=1\}^\{L\}p\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\)\\right\]\\geq\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[\\sum\_\{t=1\}^\{L\}\\log p\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\)\\right\]\.\(4\)This latent\-order perspective also provides a natural bridge to discrete diffusion models\.

### 2\.3Masked diffusion models \(MDM\)

In MDMs\(Austin et al\.,[2021](https://arxiv.org/html/2605.24292#bib.bib3); Shi et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib42); Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37)\), the latent variable can be interpreted as an unmasking trajectory, or equivalently as a grouped ordering; see Figure[2](https://arxiv.org/html/2605.24292#S2.F2)\. We write an unmasking trajectory asπ=\(π1,…,πT\)∈𝒢\\pi=\(\\pi\_\{1\},\\dots,\\pi\_\{T\}\)\\in\\mathcal\{G\}, where𝒢\\mathcal\{G\}denotes the set of*grouped orderings*\. At each generation stept∈\{1,…,T\}t\\in\\\{1,\\dots,T\\\}, the setπt⊆\{1,…,L\}\\pi\_\{t\}\\subseteq\\\{1,\\dots,L\\\}contains the positions revealed at that step\. The setsπt\\pi\_\{t\}are pairwise disjoint, may be empty, and cover all positions, i\.e\.,⨆t=1Tπt=\{1,…,L\}\\bigsqcup\_\{t=1\}^\{T\}\\pi\_\{t\}=\\\{1,\\dots,L\\\}\. Thus, a step may reveal zero, one, or multiple positions, enabling parallel token generation\. To make such parallel updates tractable, the joint distribution over the revealed tokens is typically factorized over positions,p​\(xπt\|xπ<t,π\)=∏d∈πtp​\(xd\|xπ<t,π\)p\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\},\\pi\)=\\prod\_\{d\\in\\pi\_\{t\}\}p\(x^\{d\}\|x^\{\\pi\_\{<t\}\},\\pi\)\. With this parameterization, MDMs mirror AO\-ARMs by averaging over grouped generation orderings:

pMDM​\(x\)=𝔼π∼p​\(π\)​\[p​\(x\|π\)\]=𝔼π∼p​\(π\)​\[∏t=1T∏d∈πtp​\(xd\|xπ<t,π\)\],p\_\{\\mathrm\{MDM\}\}\(x\)=\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[p\(x\|\\pi\)\\right\]=\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[\\prod\_\{t=1\}^\{T\}\\prod\_\{d\\in\\pi\_\{t\}\}p\(x^\{d\}\|x^\{\\pi\_\{<t\}\},\\pi\)\\right\],\(5\)wherep​\(π\)p\(\\pi\)is the distribution over unmasking trajectories induced by the chosen masking process\. Generation proceeds inTTsteps, which may be smaller or larger thanLL\.

Notably, the grouped\-ordering view also clarifies the relation to AO\-ARMs in continuous time\. In models such as\(Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37)\), each position has a continuous generation timet∈\[0,T\]t\\in\[0,T\], so different positions are revealed at the same time with probability zero\. After sorting the reveal events and removing empty intervals, the trajectory reduces to single\-position groups\. As a result, generation proceeds in an AO\-ARM\-like manner, revealing one token at a time according to a random orderingπ∈𝒮\\pi\\in\\mathcal\{S\}induced by the masking process\.

Regarding log\-likelihood estimation, in continuous time one can use the standard MDM ELBO, e\.g\.,\(Ou et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib29), Eq\. 2\.6\), which is notably equivalent to the AO\-ARM ELBO in \([4](https://arxiv.org/html/2605.24292#S2.E4)\)\(Ou et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib29), Thm\. 2\)\. For discretized\-time MDMs, however, the relation to AO\-ARMs yields a similar ELBO, but over grouped trajectoriesπ∈𝒢\\pi\\in\\mathcal\{G\}:

log⁡pMDM​\(x\)=log⁡𝔼π∼p​\(π\)​\[∏t=1T∏d∈πtp​\(xd\|xπ<t,π\)\]≥𝔼π∼p​\(π\)​\[∑t=1T∑d∈πtlog⁡p​\(xd\|xπ<t,π\)\]\.\\log p\_\{\\mathrm\{MDM\}\}\(x\)\\\!=\\log\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\\!\\left\[\\prod\_\{t=1\}^\{T\}\\prod\_\{d\\in\\pi\_\{t\}\}\\\!p\(x^\{d\}\|x^\{\\pi\_\{<t\}\}\\\!,\\pi\)\\right\]\\\!\\geq\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\sum\_\{d\\in\\pi\_\{t\}\}\\log p\(x^\{d\}\|x^\{\\pi\_\{<t\}\}\\\!,\\pi\)\\right\]\\\!\.\(6\)

### 2\.4Block models \(BM\)

BMs\(Arriola et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib2)\)provide another way to combine the tractability of ARMs with the flexibility of AO\-ARMs and MDMs\. Rather than defining a single ordering over all positions, they split the sequence intoBBblocks of sizeL′L^\{\\prime\}, denoted by disjoint position setsℬ1,…,ℬB\\mathcal\{B\}\_\{1\},\\dots,\\mathcal\{B\}\_\{B\}with⨆b=1Bℬb=\{1,…,L\}\\bigsqcup\_\{b=1\}^\{B\}\\mathcal\{B\}\_\{b\}=\\\{1,\\dots,L\\\}\. This gives the following block\-level decomposition:

pBM​\(x\)=∏b=1Bp​\(xℬb\|xℬ<b\),where​p​\(xℬb\|xℬ<b\)​is parameterized as in\([3](https://arxiv.org/html/2605.24292#S2.E3)\)or\([5](https://arxiv.org/html/2605.24292#S2.E5)\)\.p\_\{\\mathrm\{BM\}\}\(x\)=\\prod\_\{b=1\}^\{B\}p\(x^\{\\mathcal\{B\}\_\{b\}\}\|x^\{\\mathcal\{B\}\_\{<b\}\}\),\\qquad\\text\{where \}p\(x^\{\\mathcal\{B\}\_\{b\}\}\|x^\{\\mathcal\{B\}\_\{<b\}\}\)\\text\{ is parameterized as in \}\\eqref\{eq:ao\_arm\}\\text\{ or \}\\eqref\{eq:mdm\}\.\(7\)As a result, the block factorization preserves the autoregressive structure needed for techniques such as KV caching, while the within\-block conditionals can still use random\-order or parallel generation\.

In both parameterizations, the decomposition in \([7](https://arxiv.org/html/2605.24292#S2.E7)\) is restricted to positions insideℬb\\mathcal\{B\}^\{b\}and conditioned on the previously generated blocksxℬ<bx^\{\\mathcal\{B\}\_\{<b\}\}\. Thus, log\-likelihood evaluation reduces to a sum of block conditional log\-likelihoods\. However, the AO\-ARM formulation in \([3](https://arxiv.org/html/2605.24292#S2.E3)\) and the MDM formulation in \([5](https://arxiv.org/html/2605.24292#S2.E5)\) still require averaging within each block over local orderingsπ∈𝒮\\pi\\in\\mathcal\{S\}or grouped orderingsπ∈𝒢\\pi\\in\\mathcal\{G\}, making exact evaluation intractable and requiring the ELBOs from \([4](https://arxiv.org/html/2605.24292#S2.E4)\) and \([6](https://arxiv.org/html/2605.24292#S2.E6)\), respectively\.

### 2\.5Likelihood evaluation challenges

Likelihood\-based comparison of ARMs, AO\-ARMs, and MDMs involves two separate choices: the trained modelpmodelp\_\{\\text\{model\}\}and the estimator used to evaluate its likelihood\. For the model, notably, a single network trained with either an AO\-ARM or MDM ELBO can be reused under different generation orderings\. This is possible because these formulations parameterize the same family of conditional distributions,pmodel​\(xd∣xπ<t,π<t\)p\_\{\\text\{model\}\}\(x^\{d\}\\mid x^\{\\pi\_\{<t\}\},\\pi\_\{<t\}\)ford∈πtd\\in\\pi\_\{t\}, with ARMs recovered as the fixed\-order special case\. Moreover, their training objectives have equivalent minimizers under the connection established by\(Ou et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib29)\)\. For estimator, on the other hand, the ELBO in \([4](https://arxiv.org/html/2605.24292#S2.E4)\) and \([6](https://arxiv.org/html/2605.24292#S2.E6)\) do not localize the true log\-likelihood of AO\-ARMs and MDMs, and therefore cannot support rigorous comparison with ARMs on their own\. We therefore introduce a complementary upper bound that, together with the ELBO, localizes the log\-likelihood of AO\-ARMs and MDMs\.

## 3Method

We construct our TUBE, a variational upper bound onlog⁡p​\(x\)\\log p\(x\)that, combined with ELBO, localizes the likelihood from both sides\. We first state the bound itself \(§[3\.1](https://arxiv.org/html/2605.24292#S3.SS1)\)\. Then take a look at its practical implementation for AO\-ARM and MDM models in \(§[3\.2](https://arxiv.org/html/2605.24292#S3.SS2)\)\.

### 3\.1Tangent Upper Bound on Evidence \(TUBE\)

Our method of constructing the upper bound onlog⁡p​\(x\)\\log p\(x\)rests on the concavity oflog⁡a\\log afunction inaaand the tangent majorization oflog⁡a\\log aby the taylor decomposition at pointbb:

log⁡a≤log⁡b\+a−bb,∀a,b\>0\.\\log a\\leq\\log b\+\\frac\{a\-b\}\{b\},\\quad\\forall\\,a,b\>0\.\(8\)The upper bound hasbbas the variational variable and allows us to construct a linear bound forlog⁡p​\(x\)\\log p\(x\)treating the upper bound at eacha=p​\(x\)a=p\(x\)separately\.

###### Definition 3\.1\(Tangent Upper Bound on Evidence\)\. Consider positive functionsp​\(x\)p\(x\)andψ​\(x\)\\psi\(x\), wherep​\(x\),ψ​\(x\)\>0p\(x\),\\psi\(x\)\>0for everyx∈𝒳x\\in\\mathcal\{X\}\. The following variational bound holds:log⁡p​\(x\)≤TUBEψ​\(x\):=log⁡ψ​\(x\)\+p​\(x\)−ψ​\(x\)ψ​\(x\),\\log p\(x\)\\;\\leq\\;\\mathrm\{TUBE\}\_\{\\psi\}\(x\)\\;:=\\;\\log\\psi\(x\)\\;\+\\;\\frac\{p\(x\)\-\\psi\(x\)\}\{\\psi\(x\)\},\(9\)where the functionψ​\(x\)\\psi\(x\)is a auxiliary function, and equality holds iffψ​\(x\)=p​\(x\)\\psi\(x\)=p\(x\)\.

This bound being based on the logarithm linearization allows for linearization ofp​\(x\)p\(x\)term, which in context of latent variable models of typep​\(x\)=𝔼π​\[p​\(x\|π\)\]p\(x\)=\\mathbb\{E\}\_\{\\pi\}\[p\(x\|\\pi\)\], see §[2](https://arxiv.org/html/2605.24292#S2), allows for unbiased Monte Carlo estimation of the bound, see §[3\.2](https://arxiv.org/html/2605.24292#S3.SS2)below\. The introduced functionψ​\(x\)\\psi\(x\), which we callsurrogate, can be any positive function and the tightness of TUBE depends on the closeness ofψ​\(x\)\\psi\(x\)top​\(x\)p\(x\)\.

Since TUBE is an upper bound, combining it with any lower bound, such as ELBO or its multi\-sample extensionELBOK\\mathrm\{ELBO\}\_\{K\}, yields a population two\-sided localization oflog⁡p​\(x\)\\log p\(x\)for anyψ\\psi:

Two\-sided localization of log\-likelihoodELBO​\(x\)≤log⁡p​\(x\)≤TUBEψ​\(x\)\.\\mathrm\{ELBO\}\(x\)\\;\\leq\\;\\log p\(x\)\\;\\leq\\;\\mathrm\{TUBE\}\_\{\\psi\}\(x\)\.\(10\)

### 3\.2TUBE estimation for AO\-ARM and MDM

Monte Carlo estimation\.While TUBE can applied to any latent variable modelp​\(x\)=𝔼z​\[p​\(x\|z\)\]p\(x\)=\\mathbb\{E\}\_\{z\}\[p\(x\|z\)\], such as VAEKingma and Welling \([2013](https://arxiv.org/html/2605.24292#bib.bib22)\)or DDPMHo et al\. \([2020](https://arxiv.org/html/2605.24292#bib.bib13)\), our work focuses on the application of TUBE for AO\-ARMHoogeboom et al\. \([2022](https://arxiv.org/html/2605.24292#bib.bib15)\)and MDMSahoo et al\. \([2024](https://arxiv.org/html/2605.24292#bib.bib37)\)models\. Let us consider the modelpmodel=𝔼π​\[pmodel​\(x\|π\)\]p\_\{\\rm model\}=\\mathbb\{E\}\_\{\\pi\}\[p\_\{\\rm model\}\(x\|\\pi\)\]and its Monte Carlo approximated likelihood, then we can finally construct anunbiased estimatorfor the TUBEψ:

TUBEψ,K^​\(x\):=log⁡ψ​\(x\)\+p^model,K​\(x\)−ψ​\(x\)ψ​\(x\),p^model,K​\(x\):=1K​∑k=1Kpmodel​\(x\|π\(k\)\),\\widehat\{\\mathrm\{TUBE\}\_\{\\psi,K\}\}\(x\)\\\!:=\\\!\\log\\psi\(x\)\+\\frac\{\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\-\\psi\(x\)\}\{\\psi\(x\)\},\\quad\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\):=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\rm model\}\(x\|\\pi^\{\(k\)\}\),\(11\)whereπ\(1\),…,π\(K\)​∼i\.i\.d\.​p​\(π\)\\pi^\{\(1\)\},\\dots,\\pi^\{\(K\)\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}p\(\\pi\)\. This straightforward possibility to construct the unbiased estimator is one of the core properties of our bound\. This is a contrast with other upper bounds like CUBODieng et al\. \([2017](https://arxiv.org/html/2605.24292#bib.bib9)\)or TVOMasrani et al\. \([2019](https://arxiv.org/html/2605.24292#bib.bib27)\)where the estimation is biased, see Table[1](https://arxiv.org/html/2605.24292#S4.T1)and discussion in §[4](https://arxiv.org/html/2605.24292#S4)\. In detail, for AO\-ARM case the Monte Carlop^model,K​\(x\)\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)takes the form:

p^model,K​\(x\)=1K​∑k=1K\[∏t=1Lpmodel​\(xπt\(k\)\|xπ<t\)\],π\(1\),…,π\(K\)​∼i\.i\.d\.​p​\(π\),π\(k\)∈𝒮\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\left\[\\prod\_\{t=1\}^\{L\}p\_\{\\rm model\}\(x^\{\\pi^\{\(k\)\}\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\)\\right\],\\quad\\pi^\{\(1\)\},\\dots,\\pi^\{\(K\)\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}p\(\\pi\),\\quad\\pi^\{\(k\)\}\\in\\mathcal\{S\}\(12\)and in the case of MDM withTTsteps:

p^model,K​\(x\)=1K​∑k=1K\[∏t=1T∏d∈πtpmodel​\(xd\|xπ<t,π\(k\)\)\],π\(1\),…,π\(K\)​∼i\.i\.d\.​p​\(π\),π\(k\)∈𝒢\.\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\left\[\\prod\_\{t=1\}^\{T\}\\prod\_\{d\\in\\pi\_\{t\}\}p\_\{\\rm model\}\(x^\{d\}\|x^\{\\pi\_\{<t\}\},\\pi^\{\(k\)\}\)\\right\],\\quad\\pi^\{\(1\)\},\\dots,\\pi^\{\(K\)\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}p\(\\pi\),\\pi^\{\(k\)\}\\in\\mathcal\{G\}\.\(13\)The Block Models extensions simply follows from \([7](https://arxiv.org/html/2605.24292#S2.E7)\)\.

Choice of surrogateψ\\psi\.Since the tightness of TUBE depends on the closeness of surrogateψ​\(x\)\\psi\(x\)to thep​\(x\)p\(x\), the choice of it is important\. Here we propose two versions of its construction\.

\(1\) Exact likelihood surrogate model\.One option is to take the model which has the similar density topmodel​\(x\)p\_\{\\rm model\}\(x\), but allows for fast and exact likelihood computation, e\.g\., ARM\. Sincepmodelp\_\{\\rm model\}is trained on datapdatap\_\{\\rm data\}, than it is natural to take ARM trained on the same data \(pARM≈pdata≈pmodelp\_\{\\rm ARM\}\\approx p\_\{\\rm data\}\\approx p\_\{\\rm model\}\):

ψA​R​M​\(x\)=pARM​\(x\)=∏t=1Lpψ​\(xπt\|xπ<t\)\.\\psi\_\{ARM\}\(x\)=p\_\{\\text\{ARM\}\}\(x\)=\\prod\_\{t=1\}^\{L\}p\_\{\\psi\}\(x^\{\\pi\_\{t\}\}\|x^\{\\pi\_\{<t\}\}\)\.\(14\)Furthermore, to bring the surrogateψA​R​M\\psi\_\{ARM\}model closer to thepmodelp\_\{\\rm model\}one may finetune theψA​R​M\\psi\_\{ARM\}using the synthetic data generated bypmodelp\_\{\\rm model\}, which can be done be regular likelihood maximization procedureRadford and Narasimhan \([2018](https://arxiv.org/html/2605.24292#bib.bib35)\)or more complex proceduresOuyang et al\. \([2022](https://arxiv.org/html/2605.24292#bib.bib30)\)\.

\(2\) Self\-surrogate\.Another option, is to suppose that conditional on arbitrary orderπ\\pilikelihoodpmodel​\(x\|π\)p\_\{\\rm model\}\(x\|\\pi\)is close to full model likelihood, i\.e\.,pmodel​\(x\|π\)≈pmodel​\(x\)p\_\{\\rm model\}\(x\|\\pi\)\\approx p\_\{\\rm model\}\(x\), which is in fact true at the model optimumOu et al\. \([2025](https://arxiv.org/html/2605.24292#bib.bib29)\)\. Furthermore, we can take several ordersπ\(m\)\\pi^\{\(m\)\}and averagepmodel​\(x\|π\(m\)\)p\_\{\\rm model\}\(x\|\\pi^\{\(m\)\}\)for them, which on practice should be even closer to thepmodel​\(x\)p\_\{\\rm model\}\(x\)\. We consider:

ψM​\(x\)=1M​∑m=1Mpmodel​\(x\|π^\(m\)\)\\psi\_\{M\}\(x\)=\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}p\_\{\\rm model\}\(x\|\\hat\{\\pi\}^\{\(m\)\}\)\(15\)whereπ^\(1\),…,π^\(M\)\\hat\{\\pi\}^\{\(1\)\},\\dots,\\hat\{\\pi\}^\{\(M\)\}are some chosen orders\. Note that bothp^model,K​\(x\)\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)andψM​\(x\)\\psi\_\{M\}\(x\)utilize ordersπ\(k\)\\pi^\{\(k\)\}andπ^\(m\)\\hat\{\\pi\}^\{\(m\)\}\. If one samples the orders forψM\\psi\_\{M\}at random, e\.g\., fromp​\(π\)p\(\\pi\), they should beindependentfrom orders forp^model,K​\(x\)\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)to avoid correlation bias inTUBEψ,K​\(x\)\\mathrm\{TUBE\}\_\{\\psi,K\}\(x\)\.

#### The computation of TUBE\.

The practical procedure for two\-sided likelihood localization consists of sampling latent variablesπ\(k\)\\pi^\{\(k\)\}, evaluating the target modelpmodel​\(x∣π\(k\)\)p\_\{\\rm model\}\(x\\mid\\pi^\{\(k\)\}\), computing the surrogateψ​\(x\)\\psi\(x\), and then evaluating \([11](https://arxiv.org/html/2605.24292#S3.E11)\)\. One can see thedetailed algorithmin Appendix[B\.1](https://arxiv.org/html/2605.24292#A2.SS1)\. The computational complexity is then determined by two components:\(1\)evaluation of the likelihood modelpmodelp\_\{\\rm model\}and\(2\)evaluation of the surrogateψ\\psi\. Estimating complexity ofp^model,K\\widehat\{p\}\_\{\\text\{model\},K\}scales linearly with the number of Monte Carlo samplesKK, i\.e\.,𝒪​\(K\)\\mathcal\{O\}\(K\), since it requiresKKevaluations of fullpmodel​\(x∣π\(k\)\)p\_\{\\rm model\}\(x\\mid\\pi^\{\(k\)\}\)\. The cost ofψ\\psidepends on its form: forψARM\\psi\_\{\\rm ARM\}, it is a single forward pass through the AR model, i\.e\.,𝒪​\(1\)\\mathcal\{O\}\(1\), while forψM​\(x\)\\psi\_\{M\}\(x\)the cost is similar top^model,K\\widehat\{p\}\_\{\\text\{model\},K\}and linear inMM, i\.e\.,𝒪​\(M\)\\mathcal\{O\}\(M\)\.

## 4Related work

External\-evaluator metrics\. A parallel line of work bypasseslog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)and scores samples under a separate pretrained reference model\.*Generative perplexity \(gen\-PPL\)*\(Lou et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib26); Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37)\)reports the perplexity of samples under GPT\-2 Large\. However, it can be lowered simply by reducing sample diversity\(Zheng et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib51)\), motivating the de facto practice of reporting it alongside sample entropy which complicated comparisons\.*MAUVE*\(Pillutla et al\.,[2021](https://arxiv.org/html/2605.24292#bib.bib33)\)replaces gen\-PPL’s token\-level scoring with an embedding\-space divergence and inherits the encoder’s coverage biases\.\(Pynadath et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib34)\)formalizes the perplexity\-entropy pairing via a KL decomposition and proposes a frontier\-based comparison, while\(Salimans et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib39)\)introduces a gradient\-based alternative to gen\-PPL that vanishes when samples match the training distribution\. All of these score the model’s samples through a chosen reference rather than evaluatinglog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)on real data, so they cannot be compared to ARM’s exact log\-likelihood on the same axis\.

#### Log\-likelihood approximation for MDMs\.

Evaluatinglog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)for a pretrained MDM is intractable, so most works report single\-sample ELBO\(Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37); Haxholli et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib12)\)or its multi\-sample tighteningELBOK, also known as I\-WAE\(Burda et al\.,[2016](https://arxiv.org/html/2605.24292#bib.bib5)\), see Table[1](https://arxiv.org/html/2605.24292#S4.T1)\. Two recent works go further: DUEL\(Turok et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib45)\)computeslog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)exactly, but only under deterministic unmasking, restricting the sampler family, while SPG\(Wang et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib47)\)introduces a sandwich estimate oflog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)between ELBO and Rényi upper bound\(Li and Turner,[2016](https://arxiv.org/html/2605.24292#bib.bib25)\)\.

#### Upper bound estimators on log\-likelihood\.

Here we highlight three established families of generic upper\-bound estimators onlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)for latent variable models that are applicable to MDMs and most related to our work:CUBOβ, TVOL, IS\-VG\-B, see Table[1](https://arxiv.org/html/2605.24292#S4.T1)and Appendix[C](https://arxiv.org/html/2605.24292#A3)forsummary\.

- •CUBOβ/ Rényi\(Li and Turner,[2016](https://arxiv.org/html/2605.24292#bib.bib25); Dieng et al\.,[2017](https://arxiv.org/html/2605.24292#bib.bib9); Wang et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib47)\)take the form1β​log⁡𝔼π​\[pmodel​\(x\|π\)β\]\\tfrac\{1\}\{\\beta\}\\log\\mathbb\{E\}\_\{\\pi\}\[p\_\{\\mathrm\{model\}\}\(x\|\\pi\)^\{\\beta\}\]forβ≥1\\beta\\\!\\geq\\\!1, an upper bound onlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\); exact atβ=1\\beta\\\!=\\\!1\. Its empirical estimator \(see Table[1](https://arxiv.org/html/2605.24292#S4.T1)\) applies an outerlog\\logto a Monte Carlo mean, so Jensen actsagainstthe upper bound at finiteKK, adding bias which may remove the upper bound guarantee for expectation\.
- •TVO\(Masrani et al\.,[2019](https://arxiv.org/html/2605.24292#bib.bib27)\)is a right Riemann sum of the thermodynamic identity along the geometric pathqβ​\(π\|x\)∝pmodel​\(x\|π\)βq\_\{\\beta\}\(\\pi\|x\)\\propto p\_\{\\mathrm\{model\}\}\(x\|\\pi\)^\{\\beta\}, discretized atΛ\\Lambdagrid pointsβλ=λ/Λ\\beta\_\{\\lambda\}=\\lambda/\\Lambda, with self\-normalized weights biased at finiteKKand an𝒪​\(1/Λ\)\\mathcal\{O\}\(1/\\Lambda\)discretization residual \(Table[1](https://arxiv.org/html/2605.24292#S4.T1), Appendix[C\.2](https://arxiv.org/html/2605.24292#A3.SS2)\)\.
- •IS\-VG\-B\(Struski et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib44)\)adds an independent log\-ratio correction toELBOs\\mathrm\{ELBO\}\_\{s\}governed by two hyperparameters \(np≥2n\_\{p\}\\geq 2pairs ofss\-sample MC estimators, total budgetK=2​s​npK=2\\,s\\,n\_\{p\}\)\. The bound is rigorous in the population, but the empirical estimator is biased and not bound\-preserving, since both log terms apply Jensen\-on\-log to MC averages \(see Table[1](https://arxiv.org/html/2605.24292#S4.T1)and Appendix[C\.3](https://arxiv.org/html/2605.24292#A3.SS3)\)\.

In comparison to all these bounds, our TUBE admits unbiased bound\-preserving estimator\.

Table 1:Estimators for various bounds on log\-likelihood for latent\-variable models\. We say that the empirical estimator isbound\-preservingif itsexpectationprovably preserves the bound direction\. Bound\-breaking terms are highlighted in red; our TUBE’s estimator is bound\-preserving\.Bound nameBound typeEmpirical estimatorBound\-preserving?ELBO\\mathrm\{ELBO\}Lowerlog⁡pmodel​\(x\|π\(1\)\)\\log p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(1\)\}\)✓ELBOK\\mathrm\{ELBO\}\_\{K\}Lowerlog⁡\(1K​∑k=1Kpmodel​\(x\|π\(k\)\)\)\\log\\\!\\left\(\\tfrac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)\\right\)✓CUBOβ≥1Upper1β​log⁡\(1K​∑k=1Kpmodel​\(x\|π\(k\)\)β\)\\tfrac\{1\}\{\\beta\}\\,\\hbox\{\\pagecolor\{badbg\}$\\displaystyle\\log$\}\\\!\\left\(\\tfrac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)^\{\\beta\}\\right\)✗TVOΛU\{\}^\{U\}\_\{\\Lambda\}Upper1Λ​∑λ=1Λ∑k=1Kw¯k\(βλ\)​log⁡pmodel​\(x\|π\(k\)\)\\tfrac\{1\}\{\\Lambda\}\\sum\_\{\\lambda=1\}^\{\\Lambda\}\\sum\_\{k=1\}^\{K\}\\hbox\{\\pagecolor\{badbg\}$\\displaystyle\\bar\{w\}\_\{k\}^\{\(\\beta\_\{\\lambda\}\)\}$\}\\,\\log p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)✗IS\-VG\-BUpper1np​∑j=1nplog⁡\(1s​∑i=1spmodel​\(x\|π\(j,i\)\)\)\+log⁡\(1np​∑j=1np∑i=1spmodel​\(x\|π~\(j,i\)\)∑i=1spmodel​\(x\|π\(j,i\)\)\)\\tfrac\{1\}\{n\_\{p\}\}\\sum\_\{j=1\}^\{n\_\{p\}\}\\hbox\{\\pagecolor\{badbg\}$\\displaystyle\\log$\}\\\!\\left\(\\tfrac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j,i\)\}\)\\right\)\+\\hbox\{\\pagecolor\{badbg\}$\\displaystyle\\log$\}\\\!\\left\(\\tfrac\{1\}\{n\_\{p\}\}\\sum\_\{j=1\}^\{n\_\{p\}\}\\dfrac\{\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\widetilde\{\\pi\}^\{\(j,i\)\}\)\}\{\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j,i\)\}\)\}\\right\)✗TUBE \(Ours\)Upperlog⁡ψ​\(x\)\+1K​∑k=1Kpmodel​\(x\|π\(k\)\)−ψ​\(x\)ψ​\(x\)\\log\\psi\(x\)\+\\hbox\{\\pagecolor\{goodbg\}$\\displaystyle\\dfrac\{\\tfrac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)\-\\psi\(x\)\}\{\\psi\(x\)\}$\}✓

## 5Experiments

We demonstrate our TUBE through two categories of experiments\. First, we show that TUBE is tight enough and helps to compare AO\-ARM/MDM with ARMs \(§[5\.1](https://arxiv.org/html/2605.24292#S5.SS1)\)\. Second, we ablate the tightness of TUBE with respect to the choice of surrogateψ\\psi\(§[5\.2](https://arxiv.org/html/2605.24292#S5.SS2)\)\. The code is available in the supplementary\.

All evaluations are done with BMs\(Arriola et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib2)\)at block sizesL′∈4,8,16L^\{\\prime\}\\in\{4,8,16\}on OWT and LM1B\(Gokaslan and Cohen,[2019](https://arxiv.org/html/2605.24292#bib.bib10); Chelba et al\.,[2014](https://arxiv.org/html/2605.24292#bib.bib6)\)\. Following standard practice for MDMs \(§[2\.3](https://arxiv.org/html/2605.24292#S2.SS3)\), we report results in terms of perplexityPPL=exp⁡\(−log⁡pmodel\)\\mathrm\{PPL\}=\\exp\(\-\\log p\_\{\\rm model\}\)rather than log\-likelihood directly\.In this form, upper bounds for log\-likelihood result in lower bounds for PPL, and vice\-versa, lower log\-likelihood bounds produce upper bounds for PPL\.For OWT, we use the available pretrained checkpoints\. For LM1B, we train the BM from scratch using the original code, since checkpoints are unavailable\. The conclusions are similar on both datasets, so we report only OWT results in the main text and deferLM1B resultsto Appendix[A](https://arxiv.org/html/2605.24292#A1)\.The experimental detailsprovided in Appendix[D](https://arxiv.org/html/2605.24292#A4)\.

### 5\.1Likelihood comparison

Table 2:Test perplexity \(↓\\downarrow\) on OWT\.We reportPPL=exp⁡\(−log⁡pmodel​\(x\)\)\\mathrm\{PPL\}=\\exp\(\-\\log p\_\{\\mathrm\{model\}\}\(x\)\)\. The±\\pmvalues denote standard deviations over1010random subsets of orderings, with all estimators in a row computed using the same total number of sampled orderings\. The reference column reportsELBOK\\mathrm\{ELBO\}\_\{K\}, which is exact forL′=4L^\{\\prime\}=4\(marked with⋆\) and Monte Carlo\-estimated forL′∈\{8,16\}L^\{\\prime\}\\in\\\{8,16\\\}\.Color coding:coral background marks biased estimators, and red text marks cells where the value exceedsELBOK\\mathrm\{ELBO\}\_\{K\}, violating the expected bound relation\.Biased upper estimators for log\-likelihoodOursReferencesGapL′L^\{\\prime\}RegimeCUBOβ=2TVOUIS\-VG\-BTUBEELBOKELBO\|TUBE−\-ARM\|Exact ARM baseline:17\.54PPL4NFE=1=197\.7897\.7897\.7897\.7897\.7897\.7897\.7897\.7897\.7897\.78−\-80\.2480\.24NFE=2=224\.34±0\.0124\.34\\pm 0\.0127\.68±0\.0127\.68\\pm 0\.0129\.11±0\.0329\.11\\pm 0\.03≥21\.55±0\.03\\geq 21\.55\\pm 0\.03≤27\.40\\leq 27\.40−\-4\.014\.01NFE=4=419\.78±0\.0119\.78\\pm 0\.0121\.89±0\.0121\.89\\pm 0\.0122\.52±0\.0122\.52\\pm 0\.01≥19\.16±0\.02\\geq 19\.16\\pm 0\.02≤21\.63\\leq 21\.63−\-1\.621\.62AO\-ARM17\.50±0\.0017\.50\\pm 0\.0018\.55±0\.0018\.55\\pm 0\.0018\.76±0\.0118\.76\\pm 0\.01≥17\.74±0\.01\\geq 17\.74\\pm 0\.01=18\.46⋆=18\.46^\{\\star\}≤21\.36±0\.21\\leq 21\.36\\pm 0\.210\.200\.208NFE=1=1221\.54221\.54221\.54221\.54221\.54221\.54221\.54221\.54221\.54221\.54−\-204\.00204\.00NFE=2=229\.04±0\.0129\.04\\pm 0\.0133\.41±0\.0233\.41\\pm 0\.0234\.95±0\.0334\.95\\pm 0\.03≥24\.32±0\.06\\geq 24\.32\\pm 0\.06≤32\.63\\leq 32\.63−\-6\.786\.78NFE=4=420\.90±0\.0120\.90\\pm 0\.0123\.54±0\.0123\.54\\pm 0\.0124\.15±0\.0124\.15\\pm 0\.01≥20\.23±0\.03\\geq 20\.23\\pm 0\.03≤23\.25\\leq 23\.25−\-2\.692\.69NFE=8=818\.85±0\.0118\.85\\pm 0\.0120\.83±0\.0120\.83\\pm 0\.0121\.17±0\.0121\.17\\pm 0\.01≥19\.15±0\.02\\geq 19\.15\\pm 0\.02≤20\.67\\leq 20\.67−\-1\.611\.61AO\-ARM17\.95±0\.0017\.95\\pm 0\.0019\.31±0\.0019\.31\\pm 0\.0019\.46±0\.0019\.46\\pm 0\.00≥18\.67±0\.01\\geq 18\.67\\pm 0\.01≤19\.24\\leq 19\.24≤22\.18±0\.58\\leq 22\.18\\pm 0\.581\.131\.1316NFE=1=1398\.63398\.63398\.63398\.63398\.63398\.63398\.63398\.63398\.63398\.63−\-381\.09381\.09NFE=2=235\.80±0\.0135\.80\\pm 0\.0139\.80±0\.0139\.80\\pm 0\.0141\.93±0\.0641\.93\\pm 0\.06≥22\.50±0\.15\\geq 22\.50\\pm 0\.15≤38\.43\\leq 38\.43−\-4\.964\.96NFE=4=422\.89±0\.0222\.89\\pm 0\.0225\.21±0\.0125\.21\\pm 0\.0125\.96±0\.0225\.96\\pm 0\.02≥19\.03±0\.08\\geq 19\.03\\pm 0\.08≤24\.75\\leq 24\.75−\-1\.491\.49NFE=8=819\.59±0\.0119\.59\\pm 0\.0121\.38±0\.0121\.38\\pm 0\.0121\.77±0\.0121\.77\\pm 0\.01≥18\.44±0\.04\\geq 18\.44\\pm 0\.04≤21\.14\\leq 21\.14−\-0\.900\.90NFE=16=1618\.44±0\.0118\.44\\pm 0\.0119\.98±0\.0019\.98\\pm 0\.0020\.26±0\.0120\.26\\pm 0\.01≥18\.22±0\.03\\geq 18\.22\\pm 0\.03≤19\.83\\leq 19\.83−\-0\.680\.68AO\-ARM18\.08±0\.0018\.08\\pm 0\.0019\.39±0\.0019\.39\\pm 0\.0019\.56±0\.0119\.56\\pm 0\.01≥18\.47±0\.01\\geq 18\.47\\pm 0\.01≤19\.30\\leq 19\.30≤22\.81±0\.61\\leq 22\.81\\pm 0\.610\.930\.93

Here we ask two questions: is the true log\-likelihood of AO\-ARM/MDM competitive with an ARM baseline, and are existing lower\-side estimators on log\-likelihood tight enough to settle the comparison? We address both by pairing ELBOKwith TUBE and benchmarking against prior estimators on a shared set of Monte Carlo samples\.

#### Setup\.

We compare TUBE againstCUBOβ=2\\mathrm\{CUBO\}\_\{\\beta=2\},TVOU\\mathrm\{TVO\}\_\{U\}, IS\-VG\-B, and also report ELBO andELBOK\\mathrm\{ELBO\}\_\{K\}\. The same pretrained BM is evaluated under two regimes: AO\-ARM \(π∈𝒮\\pi\\in\\mathcal\{S\}\) and MDM \(π∈𝒢\\pi\\in\\mathcal\{G\},NFE∈\{1,2,4,…\}\\mathrm\{NFE\}\\in\\\{1,2,4,\\dots\\\}\)\. ForL′=4L^\{\\prime\}=4in AO\-ARM we enumerate all4\!=244\!=24orderings, which gives theexactper\-block log\-likelihood and we report it instead ofELBOK\\mathrm\{ELBO\}\_\{K\}\. ForL′∈\{8,16\}L^\{\\prime\}\\in\\\{8,16\\\}this is intractable, so we sample6464and128128orderings respectively\. Then, split equally into two independent sets used forp^model,K\\widehat\{p\}\_\{\\mathrm\{model\},K\}andψM\\psi\_\{M\}, withELBOK\\mathrm\{ELBO\}\_\{K\}reported as a Monte Carlo estimate\.

#### Results\.

For MDMs, Table[2](https://arxiv.org/html/2605.24292#S5.T2)shows that TUBE is generally the tightest lower bound on PPL across all NFEs \(=T=Tin §[2\.3](https://arxiv.org/html/2605.24292#S2.SS3)\), compared with the competing estimators, withCUBOβ=2\\mathrm\{CUBO\}\_\{\\beta=2\}being the only exception\. However, we emphasize thatCUBOβ=2\\mathrm\{CUBO\}\_\{\\beta=2\}is not reliable, as discussed in the next paragraph\. When comparing MDMs with the ARM baseline, the gap in the rightmost column, decreases from about55to11PPL as NFE increases\. For AO\-ARMs, TUBE is the tightest estimator across the reported settings\. The conclusions are the clearest forL′=4L^\{\\prime\}=4, whereELBOK\\mathrm\{ELBO\}\_\{K\}is exact, so the likelihood gap between AO\-ARMs/MDMs and ARMs is localized without Monte Carlo ambiguity\.

Takeaway\.In every configuration the AO\-ARM/MDM PPL lies strictly above the ARM, so ARM is dominant in likelihood across all block sizes and generation regimes we consider\.

The other estimators behave differently\.TVOU\\mathrm\{TVO\}\_\{U\}and IS\-VG\-B sit*above*ELBOK\\mathrm\{ELBO\}\_\{K\}in every regime withNFE≥2\\mathrm\{NFE\}\\geq 2,so they fail to give a reliable bound\. This is structural: each applies a nonlinear function after Monte Carlo averaging, so the population bound does not transfer to its empirical estimator\. TUBE avoids this by being affine inp^model,K\\widehat\{p\}\_\{\\mathrm\{model\},K\}, so the bound from \([9](https://arxiv.org/html/2605.24292#S3.E9)\) transfers to the Monte Carlo estimator at everyK≥1K\\geq 1\.CUBOβ=2\\mathrm\{CUBO\}\_\{\\beta=2\}behaves differently fromTVOU\\mathrm\{TVO\}\_\{U\}and IS\-VG\-B: in our data it sits belowELBOK\\mathrm\{ELBO\}\_\{K\}in every row\. Nevertheless, this does not makeCUBOβ=2\\mathrm\{CUBO\}\_\{\\beta=2\}a valid upper bound: as discussed in §[4](https://arxiv.org/html/2605.24292#S4), its empirical estimator applieslog\\logto a Monte Carlo mean and is therefore biased downward\. Furthermore, the choice ofβ\\betacan substantiallychange the estimator biasand even lead to values exceedingELBOK\\mathrm\{ELBO\}\_\{K\}, see Appendix[C\.1](https://arxiv.org/html/2605.24292#A3.SS1)\. This makes CUBOunreliableas well\.

### 5\.2Surrogateψ\\psichoice and finite\-sample behavior

By \([9](https://arxiv.org/html/2605.24292#S3.E9)\), the tightness of TUBE depends on two factors: the number of orderings used to estimatep^model,K\\widehat\{p\}\_\{\\mathrm\{model\},K\}, and the surrogateψ\\psiused to construct the bound\. While the Monte Carlo error in estimatingpmodelp\_\{\\mathrm\{model\}\}decreases as1/K1/\\sqrt\{K\}, the role ofψ\\psiis less straightforward\. So we ask which construction from §[3\.2](https://arxiv.org/html/2605.24292#S3.SS2)closes gap betweenTUBEψ\\mathrm\{TUBE\}\_\{\\psi\}andlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)most effectively\.

![Refer to caption](https://arxiv.org/html/2605.24292v1/images/fig_ppl_vs_g_owt.png)

Figure 3:Test perplexity \(↓\\downarrow\) with differentψ\\psichoices on OWT\.We reportPPL=exp⁡\(−log⁡pmodel​\(x\)\)\\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 showsELBOK\\mathrm\{ELBO\}\_\{K\}\.#### Setup\.

Withp^model,K\\widehat\{p\}\_\{\\mathrm\{model\},K\}fixed, we compare four self\-surrogates: a single\-order surrogateψπ\\psi\_\{\\pi\}, the self\-surrogateψM\\psi\_\{M\}, an external ARM surrogateψARM\\psi\_\{\\mathrm\{ARM\}\}, and a variant of ARM fine\-tuned on samples generated by the BM \(Appendix[D](https://arxiv.org/html/2605.24292#A4)\)\. We vary the number of sampled orderingsMMon alog2\\log\_\{2\}grid up to the full ordering budget used in §[5\.1](https://arxiv.org/html/2605.24292#S5.SS1)\.

#### Results\.

Figure[3](https://arxiv.org/html/2605.24292#S5.F3)shows that the self\-surrogateψM\\psi\_\{M\}gets closest toELBOK\\mathrm\{ELBO\}\_\{K\}at every block size with increase ofMM\. The external ARM surrogateψARM\\psi\_\{\\mathrm\{ARM\}\}leaves a much wider gap, and fine\-tuning it on BM samples shifts the bound only marginally\. A single fixed orderψπ\\psi\_\{\\pi\}is looser still\. This matches the discussion of §[3\.2](https://arxiv.org/html/2605.24292#S3.SS2):ψM\\psi\_\{M\}averagespmodel​\(x\|π\)p\_\{\\mathrm\{model\}\}\(x\|\\pi\)over independent orderings drawn from the same model and therefore trackspmodel​\(x\)p\_\{\\mathrm\{model\}\}\(x\)pointwise better than an external density\.

## 6Potential impact and limitations

#### Limitations\.

Our empirical study is limited to BM\(Arriola et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib2)\)which is the dominant inference\-time paradigm of large\-scale MDMs such as LLaDA 2\.0\(Bie et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib4)\)and Mercury\(Khanna et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib21)\)\. However, applying TUBE to non\-block MDM may be challenging\. TUBE’s tightness requires the surrogateψ​\(x\)≈pmodel​\(x\)\\psi\(x\)\\approx p\_\{\\mathrm\{model\}\}\(x\)\. For non\-block MDM at typical sequence lengthsL∼102L\\sim 10^\{2\}to10310^\{3\},pmodel​\(x\)p\_\{\\mathrm\{model\}\}\(x\)is approximately product ofLLper\-token probabilities, vanishingly small in absolute scale\. Thus,ψ\\psibecomes hard to estimate reliably in practice\. In turn, BM decomposition \([7](https://arxiv.org/html/2605.24292#S2.E7)\) for moderate block size keeps computing log\-likelihood numerically feasible\.

#### Potential impact\.

The reliable two\-sided estimation oflog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)enables several downstream uses\. It tightens perplexity bounds for diffusion language models\(Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37); Arriola et al\.,[2025](https://arxiv.org/html/2605.24292#bib.bib2)\), supplies finite\-sample policy ratios for RL post\-training\(Christiano et al\.,[2017](https://arxiv.org/html/2605.24292#bib.bib8); Ouyang et al\.,[2022](https://arxiv.org/html/2605.24292#bib.bib30); Shao et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib41); Rafailov et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib36)\), and supports likelihood\-based evaluation in scientific generative modeling such as protein sequence design\(Alamdari et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib1); Wang et al\.,[2025a](https://arxiv.org/html/2605.24292#bib.bib48)\)\. Studying these directions using our TUBE is a promising avenue for the future work\.

## References

- Alamdari et al\. \[2023\]Sarah Alamdari, Nitya Thakkar, Rianne van den Berg, Alex X\. Lu, Nicolo Fusi, Ava P\. Amini, and Kevin K\. Yang\.Protein generation with evolutionary diffusion: sequence is all you need\.*bioRxiv*, 2023\.doi:10\.1101/2023\.09\.11\.556673\.
- Arriola et al\. \[2025\]Marianne Arriola, Aaron Gokaslan, Justin T\. Chiu, Zhihan Yang, Zhixuan Qi, Jiaqi Han, Subham Sekhar Sahoo, and Volodymyr Kuleshov\.Block diffusion: Interpolating between autoregressive and diffusion language models\.In*The Thirteenth International Conference on Learning Representations*, 2025\.
- Austin et al\. \[2021\]Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg\.Structured denoising diffusion models in discrete state\-spaces\.*Advances in neural information processing systems*, 34:17981–17993, 2021\.
- Bie et al\. \[2025\]Tiwei Bie, Maosong Cao, Kun Chen, Lun Du, Mingliang Gong, Zhuochen Gong, Yanmei Gu, Jiaqi Hu, Zenan Huang, Zhenzhong Lan, Chengxi Li, Chongxuan Li, Jianguo Li, Zehuan Li, Huabin Liu, Ling Liu, Guoshan Lu, Xiaocheng Lu, Yuxin Ma, Jianfeng Tan, Lanning Wei, Ji\-Rong Wen, Yipeng Xing, Xiaolu Zhang, Junbo Zhao, Da Zheng, Jun Zhou, Junlin Zhou, Zhanchao Zhou, Liwang Zhu, and Yihong Zhuang\.LLaDA2\.0: Scaling up diffusion language models to 100b\.*arXiv preprint arXiv:2512\.15745*, 2025\.
- Burda et al\. \[2016\]Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov\.Importance weighted autoencoders\.In*International Conference on Learning Representations \(ICLR\)*, 2016\.
- Chelba et al\. \[2014\]Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson\.One billion word benchmark for measuring progress in statistical language modeling, 2014\.URL[https://arxiv\.org/abs/1312\.3005](https://arxiv.org/abs/1312.3005)\.
- Chen et al\. \[2020\]Mark Chen, Alec Radford, Jeff Wu, Heewoo Jun, Prafulla Dhariwal, David Luan, and Ilya Sutskever\.Generative pretraining from pixels\.In*International Conference on Machine Learning*, 2020\.URL[https://api\.semanticscholar\.org/CorpusID:219781060](https://api.semanticscholar.org/CorpusID:219781060)\.
- Christiano et al\. \[2017\]Paul F\. Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei\.Deep reinforcement learning from human preferences\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2017\.
- Dieng et al\. \[2017\]Adji Bousso Dieng, Dustin Tran, Rajesh Ranganath, John Paisley, and David M\. Blei\.Variational inference viaχ\\chi\-upper bound minimization\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2017\.
- Gokaslan and Cohen \[2019\]Aaron Gokaslan and Vanya Cohen\.Openwebtext corpus\.[http://Skylion007\.github\.io/OpenWebTextCorpus](http://skylion007.github.io/OpenWebTextCorpus), 2019\.
- Gu et al\. \[2022\]Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo\.Vector quantized diffusion model for text\-to\-image synthesis\.In*Proceedings of the IEEE/CVF conference on computer vision and pattern recognition*, pages 10696–10706, 2022\.
- Haxholli et al\. \[2025\]Etrit Haxholli, Yeti Z\. Gurbuz, Oğul Can, and Eli Waxman\.Efficient perplexity bound and ratio matching in discrete diffusion language models\.In*The Thirteenth International Conference on Learning Representations*, 2025\.
- Ho et al\. \[2020\]Jonathan Ho, Ajay Jain, and Pieter Abbeel\.Denoising diffusion probabilistic models\.*Advances in Neural Information Processing Systems*, 33:6840–6851, 2020\.
- Hoffmann et al\. \[2022\]Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al\.Training compute\-optimal large language models\.In*Proceedings of the 36th International Conference on Neural Information Processing Systems*, pages 30016–30030, 2022\.
- Hoogeboom et al\. \[2022\]Emiel Hoogeboom, Alexey A\. Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans\.Autoregressive diffusion models\.In*The Tenth International Conference on Learning Representations \(ICLR\)*, 2022\.
- Jeon et al\. \[2025\]Moongyu Jeon, Sangwoo Shin, Dongjae Jeon, and Albert No\.Information\-theoretic discrete diffusion\.*arXiv preprint arXiv:2510\.24088*, 2025\.
- Ji and Shen \[2019\]Chunlin Ji and Haige Shen\.Stochastic variational inference via upper bound\.In*NeurIPS Workshop on Bayesian Deep Learning*, 2019\.arXiv:1912\.00650 – KL\-based EUBO; included for completeness, distinct from SPG’s Rényi\-based bound\.
- Kaplan et al\. \[2020\]Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei\.Scaling laws for neural language models\.*arXiv preprint arXiv:2001\.08361*, 2020\.
- Karimi Monsefi et al\. \[2026\]Amin Karimi Monsefi, Nikhil Bhendawade, Manuel Rafael Ciosici, Dominic Culver, Yizhe Zhang, and Irina Belousova\.FS\-DFM: Fast and accurate long text generation with few\-step diffusion language models\.In*The Fourteenth International Conference on Learning Representations*, 2026\.
- Kelvinius and Lindsten \[2024\]Filip Ekström Kelvinius and Fredrik Lindsten\.Discriminator guidance for autoregressive diffusion models\.In*International Conference on Artificial Intelligence and Statistics*, pages 3403–3411\. PMLR, 2024\.
- Khanna et al\. \[2025\]Samar Khanna, Siddhant Kharbanda, Shufan Li, Harshit Varma, Eric Wang, Sawyer Birnbaum, Ziyang Luo, Yanis Miraoui, Akash Palrecha, Stefano Ermon, Aditya Grover, and Volodymyr Kuleshov\.Mercury: Ultra\-fast language models based on diffusion\.*arXiv preprint arXiv:2506\.17298*, 2025\.
- Kingma and Welling \[2013\]Diederik P Kingma and Max Welling\.Auto\-encoding variational bayes\.*arXiv preprint arXiv:1312\.6114*, 2013\.
- Lee et al\. \[2025\]Seul Lee, Karsten Kreis, Srimukh Prasad Veccham, Meng Liu, Danny Reidenbach, Yuxing Peng, Saee Gopal Paliwal, Weili Nie, and Arash Vahdat\.Genmol: A drug discovery generalist with discrete diffusion\.In*Forty\-second International Conference on Machine Learning*, 2025\.URL[https://openreview\.net/forum?id=KM7pXWG1xj](https://openreview.net/forum?id=KM7pXWG1xj)\.
- Li et al\. \[2021\]Xuanlin Li, Brandon Trabucco, Dong Huk Park, Michael Luo, Sheng Shen, Trevor Darrell, and Yang Gao\.Discovering non\-monotonic autoregressive orderings with variational inference\.In*International Conference on Learning Representations*, 2021\.URL[https://openreview\.net/forum?id=jP1vTH3inC](https://openreview.net/forum?id=jP1vTH3inC)\.
- Li and Turner \[2016\]Yingzhen Li and Richard E\. Turner\.Rényi divergence variational inference\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2016\.
- Lou et al\. \[2024\]Aaron Lou, Chenlin Meng, and Stefano Ermon\.Discrete diffusion modeling by estimating the ratios of the data distribution\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235 of*Proceedings of Machine Learning Research*, 2024\.
- Masrani et al\. \[2019\]Vaden Masrani, Tuan Anh Le, and Frank Wood\.The thermodynamic variational objective\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2019\.
- Nie et al\. \[2025\]Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji\-Rong Wen, and Chongxuan Li\.Large language diffusion models\.*arXiv preprint arXiv:2502\.09992*, 2025\.
- Ou et al\. \[2025\]Jingyang Ou, Shen Nie, Kaiwen Xue, Fengqi Zhu, Jiacheng Sun, Zhenguo Li, and Chongxuan Li\.Your absorbing discrete diffusion secretly models the conditional distributions of clean data\.In*The Thirteenth International Conference on Learning Representations*, 2025\.
- Ouyang et al\. \[2022\]Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L\. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al\.Training language models to follow instructions with human feedback\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2022\.
- Owen \[2013\]Art B\. Owen\.*Monte Carlo theory, methods and examples*\.Stanford University, 2013\.
- Pang et al\. \[2025\]Ziqi Pang, Tianyuan Zhang, Fujun Luan, Yunze Man, Hao Tan, Kai Zhang, William T Freeman, and Yu\-Xiong Wang\.Randar: Decoder\-only autoregressive visual generation in random orders\.In*Proceedings of the Computer Vision and Pattern Recognition Conference*, pages 45–55, 2025\.
- Pillutla et al\. \[2021\]Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaid Harchaoui\.Mauve: Measuring the gap between neural text and human text using divergence frontiers\.In*Advances in Neural Information Processing Systems*, 2021\.
- Pynadath et al\. \[2026\]Patrick Pynadath, Jiaxin Shi, and Ruqi Zhang\.Generative frontiers: Why evaluation matters for diffusion language models\.*arXiv preprint arXiv:2604\.02718*, 2026\.
- Radford and Narasimhan \[2018\]Alec Radford and Karthik Narasimhan\.Improving language understanding by generative pre\-training\.2018\.URL[https://api\.semanticscholar\.org/CorpusID:49313245](https://api.semanticscholar.org/CorpusID:49313245)\.
- Rafailov et al\. \[2023\]Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D\. Manning, Stefano Ermon, and Chelsea Finn\.Direct preference optimization: Your language model is secretly a reward model\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2023\.
- Sahoo et al\. \[2024\]Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T\. Chiu, Alexander M\. Rush, and Volodymyr Kuleshov\.Simple and effective masked diffusion language models\.In*Advances in Neural Information Processing Systems*, volume 37, 2024\.
- Sahoo et al\. \[2025\]Subham Sekhar Sahoo, Zhihan Yang, Yash Akhauri, Johnna Liu, Deepansha Singh, Zhoujun Cheng, Zhengzhong Liu, Eric Xing, John Thickstun, and Arash Vahdat\.Esoteric language models\.*arXiv preprint arXiv:2506\.01928*, 2025\.
- Salimans et al\. \[2026\]Tim Salimans, Thomas Mensink, Jonathan Heek, and Emiel Hoogeboom\.Beyond single tokens: Distilling discrete diffusion models via discrete MMD\.*arXiv preprint arXiv:2603\.20155*, 2026\.
- Seo et al\. \[2025\]Hyunjin Seo, Taewon Kim, Sihyun Yu, and SungSoo Ahn\.Learning flexible forward trajectories for masked molecular diffusion\.*arXiv preprint arXiv:2505\.16790*, 2025\.
- Shao et al\. \[2024\]Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y\. K\. Li, Y\. Wu, and Daya Guo\.DeepSeekMath: Pushing the limits of mathematical reasoning in open language models\.*arXiv preprint arXiv:2402\.03300*, 2024\.
- Shi et al\. \[2024\]Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis Titsias\.Simplified and generalized masked diffusion for discrete data\.*Advances in neural information processing systems*, 37:103131–103167, 2024\.
- Shih et al\. \[2022\]Andy Shih, Dorsa Sadigh, and Stefano Ermon\.Training and inference on any\-order autoregressive models the right way\.*Advances in Neural Information Processing Systems*, 35:2762–2775, 2022\.
- Struski et al\. \[2023\]Łukasz Struski, Marcin Mazur, Paweł Batorski, Przemysław Spurek, and Jacek Tabor\.Bounding evidence and estimating log\-likelihood in VAE\.In*Proceedings of The 26th International Conference on Artificial Intelligence and Statistics*, volume 206 of*Proceedings of Machine Learning Research*, pages 675–693, 2023\.
- Turok et al\. \[2026\]Gilad Turok, Chris De Sa, and Volodymyr Kuleshov\.DUEL: Exact likelihood for masked diffusion via deterministic unmasking\.*arXiv preprint arXiv:2603\.01367*, 2026\.
- Uria et al\. \[2014\]Benigno Uria, Iain Murray, and Hugo Larochelle\.A deep and tractable density estimator\.In*International Conference on Machine Learning*, pages 467–475\. PMLR, 2014\.
- Wang et al\. \[2026\]Chenyu Wang, Paria Rashidinejad, DiJia Su, Song Jiang, Sid Wang, Siyan Zhao, Cai Zhou, Shannon Zejiang Shen, Feiyu Chen, Tommi Jaakkola, Yuandong Tian, and Bo Liu\.SPG: Sandwiched policy gradient for masked diffusion language models\.In*The Fourteenth International Conference on Learning Representations*, 2026\.Poster\.
- Wang et al\. \[2025a\]Xinyou Wang, Zaixiang Zheng, Fei Ye, Dongyu Xue, Shujian Huang, and Quanquan Gu\.DPLM\-2: A multimodal diffusion protein language model\.In*The Thirteenth International Conference on Learning Representations \(ICLR\)*, 2025a\.
- Wang et al\. \[2025b\]Zhe Wang, Jiaxin Shi, Nicolas Heess, Arthur Gretton, and Michalis Titsias\.Learning\-order autoregressive models with application to molecular graph generation\.In*Forty\-second International Conference on Machine Learning*, 2025b\.URL[https://openreview\.net/forum?id=EY6pXIDi3G](https://openreview.net/forum?id=EY6pXIDi3G)\.
- Ye et al\. \[2025\]Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and Lingpeng Kong\.Dream 7b: Diffusion large language models\.*arXiv preprint arXiv:2508\.15487*, 2025\.
- Zheng et al\. \[2025\]Kaiwen Zheng, Yongxin Chen, Hanzi Mao, Ming\-Yu Liu, Jun Zhu, and Qinsheng Zhang\.Masked diffusion models are secretly time\-agnostic masked models and exploit inaccurate categorical sampling\.In*The Thirteenth International Conference on Learning Representations \(ICLR\)*, 2025\.

## Appendix AExperiments on LM1B

This section reports the results of our TUBE evaluation on LM1B dataset \(Table[3](https://arxiv.org/html/2605.24292#A1.T3)and Figure[4](https://arxiv.org/html/2605.24292#A1.F4)\)\. The conclusions are analogous to those from the main paper obtained on OWT dataset\.

Table 3:Test perplexity \(↓\\downarrow\) on LM1B\.We reportPPL=exp⁡\(−log⁡pmodel​\(x\)\)\\mathrm\{PPL\}=\\exp\(\-\\log p\_\{\\mathrm\{model\}\}\(x\)\)\. The±\\pmvalues denote standard deviations over1010random subsets of orderings, with all estimators in a row computed using the same total number of sampled orderings\. The reference column reportsELBOK\\mathrm\{ELBO\}\_\{K\}, which is exact forL′=4L^\{\\prime\}=4\(marked with⋆\) and Monte Carlo\-estimated forL′∈\{8,16\}L^\{\\prime\}\\in\\\{8,16\\\}\.Color coding:coral background marks biased estimators, and red text marks cells where the value exceedsELBOK\\mathrm\{ELBO\}\_\{K\}, violating the expected bound relation\.Biased upper estimatorsOursReferencesGapL′L^\{\\prime\}RegimeCUBOβ=2TVOUIS\-VG\-BTUBEELBOKELBOTUBE−\-ARMExact ARM baseline:22\.4622\.46PPL4NFE=1=1137\.09137\.09137\.09137\.09137\.09137\.09137\.09137\.09137\.09137\.09−\-114\.62114\.62NFE=2=234\.67±0\.0134\.67\\pm 0\.0139\.45±0\.0139\.45\\pm 0\.0141\.40±0\.0441\.40\\pm 0\.04≥30\.87±0\.03\\geq 30\.87\\pm 0\.03≤39\.08\\leq 39\.08−\-8\.418\.41NFE=4=428\.05±0\.0128\.05\\pm 0\.0131\.01±0\.0131\.01\\pm 0\.0131\.85±0\.0231\.85\\pm 0\.02≥27\.34±0\.03\\geq 27\.34\\pm 0\.03≤30\.67\\leq 30\.67−\-4\.884\.88AO\-ARM25\.25±0\.0025\.25\\pm 0\.0026\.54±0\.0026\.54\\pm 0\.0026\.78±0\.0026\.78\\pm 0\.00≥25\.63±0\.01\\geq 25\.63\\pm 0\.01=26\.45⋆=26\.45^\{\\star\}≤28\.95±0\.38\\leq 28\.95\\pm 0\.383\.173\.178NFE=1=1299\.88299\.88299\.88299\.88299\.88299\.88299\.88299\.88299\.88299\.88−\-277\.42277\.42NFE=2=241\.45±0\.0241\.45\\pm 0\.0247\.68±0\.0247\.68\\pm 0\.0249\.73±0\.0349\.73\\pm 0\.03≥35\.24±0\.05\\geq 35\.24\\pm 0\.05≤46\.66\\leq 46\.66−\-12\.7712\.77NFE=4=429\.78±0\.0129\.78\\pm 0\.0133\.53±0\.0133\.53\\pm 0\.0134\.34±0\.0234\.34\\pm 0\.02≥29\.11±0\.04\\geq 29\.11\\pm 0\.04≤33\.14\\leq 33\.14−\-6\.656\.65NFE=8=826\.88±0\.0126\.88\\pm 0\.0129\.65±0\.0129\.65\\pm 0\.0130\.09±0\.0130\.09\\pm 0\.01≥27\.51±0\.02\\geq 27\.51\\pm 0\.02≤29\.44\\leq 29\.44−\-5\.055\.05AO\-ARM25\.14±0\.0025\.14\\pm 0\.0026\.90±0\.0026\.90\\pm 0\.0027\.09±0\.0127\.09\\pm 0\.01≥26\.15±0\.01\\geq 26\.15\\pm 0\.01≤26\.82\\leq 26\.82≤30\.32±0\.38\\leq 30\.32\\pm 0\.383\.693\.6916NFE=1=1546\.32546\.32546\.32546\.32546\.32546\.32546\.32546\.32546\.32546\.32−\-523\.86523\.86NFE=2=251\.26±0\.0351\.26\\pm 0\.0357\.02±0\.0357\.02\\pm 0\.0359\.97±0\.0359\.97\\pm 0\.03≥31\.99±0\.13\\geq 31\.99\\pm 0\.13≤55\.13\\leq 55\.13−\-9\.539\.53NFE=4=432\.81±0\.0232\.81\\pm 0\.0236\.15±0\.0236\.15\\pm 0\.0237\.18±0\.0237\.18\\pm 0\.02≥27\.39±0\.06\\geq 27\.39\\pm 0\.06≤35\.52\\leq 35\.52−\-4\.934\.93NFE=8=828\.00±0\.0128\.00\\pm 0\.0130\.54±0\.0130\.54\\pm 0\.0131\.07±0\.0131\.07\\pm 0\.01≥26\.60±0\.04\\geq 26\.60\\pm 0\.04≤30\.23\\leq 30\.23−\-4\.144\.14NFE=16=1626\.34±0\.0126\.34\\pm 0\.0128\.50±0\.0128\.50\\pm 0\.0128\.86±0\.0128\.86\\pm 0\.01≥26\.24±0\.02\\geq 26\.24\\pm 0\.02≤28\.30\\leq 28\.30−\-3\.783\.78AO\-ARM25\.14±0\.0025\.14\\pm 0\.0026\.88±0\.0026\.88\\pm 0\.0027\.09±0\.0127\.09\\pm 0\.01≥25\.82±0\.02\\geq 25\.82\\pm 0\.02≤26\.78\\leq 26\.78≤31\.03±0\.49\\leq 31\.03\\pm 0\.493\.363\.36

![Refer to caption](https://arxiv.org/html/2605.24292v1/images/fig_ppl_vs_g_lm1b.png)

Figure 4:Test perplexity \(↓\\downarrow\) with differentψ\\psichoices on LM1B\.We reportPPL=exp⁡\(−log⁡pmodel​\(x\)\)\\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 showsELBOK\\mathrm\{ELBO\}\_\{K\}\.
## Appendix BAdditional methodology

### B\.1TUBE Estimation Algorithm

Here we present the Algorithm[1](https://arxiv.org/html/2605.24292#alg1)for the two\-sided likelihood localization via our TUBEψ\([9](https://arxiv.org/html/2605.24292#S3.E9)\) and ELBOKestimateSahoo et al\. \[[2025](https://arxiv.org/html/2605.24292#bib.bib38)\]which originates from I\-WAE modelBurda et al\. \[[2016](https://arxiv.org/html/2605.24292#bib.bib5)\]\.

Algorithm 1TUBEψand ELBOK: two\-sided likelihood interval1:sample

xx, surrogate type

c∈\{ARM,self\}c\\in\\\{\\mathrm\{ARM\},\\mathrm\{self\}\\\}, sample budgets

K,M≥1K,M\\geq 1, model

pmodel\(⋅\|π\)p\_\{\\rm model\}\(\\cdot\|\\pi\), latent prior

p​\(π\)p\(\\pi\), optional ARM surrogate

pARMp\_\{\\rm ARM\}
2:Sample

π\(1\),…,π\(K\)​∼i\.i\.d\.​p​\(π\)\\pi^\{\(1\)\},\\dots,\\pi^\{\(K\)\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}p\(\\pi\)
3:

p^model,K​\(x\)←1K​∑k=1Kpmodel​\(x\|π\(k\)\)\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\\leftarrow\\dfrac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\rm model\}\(x\|\\pi^\{\(k\)\}\)
4:

TUBE^ψ,K​\(x\)←log⁡ψ​\(x\)\+p^model,K​\(x\)−ψ​\(x\)ψ​\(x\)\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)\\leftarrow\\log\\psi\(x\)\+\\dfrac\{\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\-\\psi\(x\)\}\{\\psi\(x\)\}
5:

ELBO^K​\(x\)←log⁡p^model,K​\(x\)\\widehat\{\\mathrm\{ELBO\}\}\_\{K\}\(x\)\\leftarrow\\log\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)
6:Return:LL interval

\[ELBO^K​\(x\),TUBE^ψ,K​\(x\)\]\[\\,\\widehat\{\\mathrm\{ELBO\}\}\_\{K\}\(x\),\\,\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)\\,\]

### B\.2Statistical properties

###### Proposition B\.1\(Unbiasednes and Variance of TUBE\)\.

Fixx∈𝒳x\\in\\mathcal\{X\}and assume thatψ​\(x\)\>0\\psi\(x\)\>0is deterministic\. Recap the Monte Carlo estimator ofTUBEψ​\(x\)\\mathrm\{TUBE\}\_\{\\psi\}\(x\):

TUBEψ,K^​\(x\):=log⁡ψ​\(x\)\+p^model,K​\(x\)−ψ​\(x\)ψ​\(x\),p^model,K​\(x\):=1K​∑k=1Kpmodel​\(x\|π\(k\)\),\\widehat\{\\mathrm\{TUBE\}\_\{\\psi,K\}\}\(x\)\\\!:=\\\!\\log\\psi\(x\)\+\\frac\{\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\-\\psi\(x\)\}\{\\psi\(x\)\},\\quad\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\):=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\rm model\}\(x\|\\pi^\{\(k\)\}\),\(16\)Then, for everyK≥1K\\geq 1andπ\(1\),…,π\(K\)\\pi^\{\(1\)\},\\ldots,\\pi^\{\(K\)\}which are i\.i\.d\.:

𝔼π\(1:K\)​\[TUBE^ψ,K​\(x\)\]=TUBEψ​\(x\),\\mathbb\{E\}\_\{\\pi^\{\(1:K\)\}\}\\\!\\left\[\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)\\right\]=\\mathrm\{TUBE\}\_\{\\psi\}\(x\),Moreover, ifVarπ∼p​\(π\)⁡\[pmodel​\(x∣π\)\]<∞\\operatorname\{Var\}\_\{\\pi\\sim p\(\\pi\)\}\[p\_\{\\mathrm\{model\}\}\(x\\mid\\pi\)\]<\\infty, then

Varπ\(1:K\)⁡\[TUBE^ψ,K​\(x\)\]=1K​ψ​\(x\)2​Varπ∼p​\(π\)⁡\[pmodel​\(x∣π\)\]\.\\operatorname\{Var\}\_\{\\pi^\{\(1:K\)\}\}\\\!\\left\[\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)\\right\]=\\frac\{1\}\{K\\,\\psi\(x\)^\{2\}\}\\operatorname\{Var\}\_\{\\pi\\sim p\(\\pi\)\}\\left\[p\_\{\\mathrm\{model\}\}\(x\\mid\\pi\)\\right\]\.

###### Proof\.

Sinceπ\(1\),…,π\(K\)\\pi^\{\(1\)\},\\ldots,\\pi^\{\(K\)\}are i\.i\.d\.,

𝔼π\(1:K\)​\[p^model,K​\(x\)\]=𝔼π∼p​\(π\)​\[pmodel​\(x∣π\)\]=pmodel​\(x\)\.\\mathbb\{E\}\_\{\\pi^\{\(1:K\)\}\}\[\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\]=\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\[p\_\{\\mathrm\{model\}\}\(x\\mid\\pi\)\]=p\_\{\\mathrm\{model\}\}\(x\)\.Therefore,

𝔼π\(1:K\)​\[TUBE^ψ,K​\(x\)\]=log⁡ψ​\(x\)\+𝔼​\[p^model,K​\(x\)\]−ψ​\(x\)ψ​\(x\)=log⁡ψ​\(x\)\+pmodel​\(x\)−ψ​\(x\)ψ​\(x\)=TUBEψ​\(x\)\.\\mathbb\{E\}\_\{\\pi^\{\(1:K\)\}\}\\\!\\left\[\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)\\right\]=\\log\\psi\(x\)\+\\frac\{\\mathbb\{E\}\[\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\]\-\\psi\(x\)\}\{\\psi\(x\)\}=\\log\\psi\(x\)\+\\frac\{p\_\{\\mathrm\{model\}\}\(x\)\-\\psi\(x\)\}\{\\psi\(x\)\}=\\mathrm\{TUBE\}\_\{\\psi\}\(x\)\.
For the variance, the only random term inTUBE^ψ,K​\(x\)\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)isp^model,K​\(x\)\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\), sinceψ​\(x\)\\psi\(x\)is fixed\. Hence:

Var⁡\[TUBE^ψ,K​\(x\)\]=1ψ​\(x\)2​Var⁡\[p^model,K​\(x\)\]\.\\operatorname\{Var\}\\left\[\\widehat\{\\mathrm\{TUBE\}\}\_\{\\psi,K\}\(x\)\\right\]=\\frac\{1\}\{\\psi\(x\)^\{2\}\}\\operatorname\{Var\}\\left\[\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\\right\]\.By independence of theKKsamples,

Var⁡\[p^model,K​\(x\)\]=Var⁡\[1K​∑k=1Kpmodel​\(x\|π\(k\)\)\]=1K​Varπ∼p​\(π\)⁡\[pmodel​\(x∣π\)\]\.\\operatorname\{Var\}\\left\[\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)\\right\]=\\operatorname\{Var\}\\left\[\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\rm model\}\(x\|\\pi^\{\(k\)\}\)\\right\]=\\frac\{1\}\{K\}\\operatorname\{Var\}\_\{\\pi\\sim p\(\\pi\)\}\[p\_\{\\mathrm\{model\}\}\(x\\mid\\pi\)\]\.∎

## Appendix CComparison of likelihood estimators

In this appendix we give the precise definitions of the upper\-bound estimators outlined in §[4](https://arxiv.org/html/2605.24292#S4)\(CUBOβ, TVOΛ, IS\-VG\-B\), derive their finite\-sample Monte Carlo forms, and identify the structural source of bias in each\. Throughout, we use the notation of §[3](https://arxiv.org/html/2605.24292#S3):π\\piis the latent generation structure \(an orderπ∈𝒮\\pi\\in\\mathcal\{S\}for AO\-ARM, a grouped orderingπ∈𝒢\\pi\\in\\mathcal\{G\}for MDM\),p​\(π\)p\(\\pi\)is a distribution on orders defined by the model, and the standardKK\-sample Monte Carlo estimatorp^model,K​\(x\)\\widehat\{p\}\_\{\\mathrm\{model\},K\}\(x\)is the one defined in \([11](https://arxiv.org/html/2605.24292#S3.E11)\)\. Each estimator below uses this single shared sample bank\.

### C\.1CUBO and the Rényi variational bound

Theχβ\\chi^\{\\beta\}\-divergence upper bound \(CUBO\) of\[Dieng et al\.,[2017](https://arxiv.org/html/2605.24292#bib.bib9)\]and the Rényi variational bound of\[Li and Turner,[2016](https://arxiv.org/html/2605.24292#bib.bib25)\]are two equivalent formulations of the same family of upper bounds onlog⁡pmodel​\(x\)\\log p\_\{\\text\{model\}\}\(x\)\. In our latent\-mixture form,

CUBOβ​\(x\)=1β​log⁡𝔼π∼p​\(π\)​\[pmodel​\(x\|π\)β\]≥log⁡pmodel​\(x\),β≥1,\\mathrm\{CUBO\}\_\{\\beta\}\(x\)\\;=\\;\\frac\{1\}\{\\beta\}\\log\\mathbb\{E\}\_\{\\pi\\sim p\(\\pi\)\}\\\!\\left\[p\_\{\\mathrm\{model\}\}\(x\|\\pi\)^\{\\beta\}\\right\]\\;\\geq\\;\\log p\_\{\\mathrm\{model\}\}\(x\),\\qquad\\beta\\geq 1,\(17\)with equality atβ=1\\beta=1and monotone non\-decreasing inβ\\beta\[Dieng et al\.,[2017](https://arxiv.org/html/2605.24292#bib.bib9)\]\.

#### Empirical Monte Carlo estimator\.

It can be practically estimated \(Table[1](https://arxiv.org/html/2605.24292#S4.T1)\) as

CUBO^β,K​\(x\)=1β​log⁡\(1K​∑k=1Kpmodel​\(x\|π\(k\)\)β\)\.\\widehat\{\\mathrm\{CUBO\}\}\_\{\\beta,K\}\(x\)\\;=\\;\\frac\{1\}\{\\beta\}\\log\\\!\\left\(\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)^\{\\beta\}\\right\)\.\(18\)

#### Source of bias\.

The estimator \([18](https://arxiv.org/html/2605.24292#A3.E18)\) is biased at finiteKK: by Jensen on the outerlog\\log,𝔼​\[CUBO^β,K\]≤CUBOβ\\mathbb\{E\}\[\\widehat\{\\mathrm\{CUBO\}\}\_\{\\beta,K\}\]\\leq\\mathrm\{CUBO\}\_\{\\beta\}\. The population guaranteelog⁡pmodel​\(x\)≤CUBOβ\\log p\_\{\\mathrm\{model\}\}\(x\)\\leq\\mathrm\{CUBO\}\_\{\\beta\}therefore does not transfer to the empirical estimator: the chainlog⁡pmodel​\(x\)≤𝔼​\[CUBO^β,K\]\\log p\_\{\\mathrm\{model\}\}\(x\)\\leq\\mathbb\{E\}\[\\widehat\{\\mathrm\{CUBO\}\}\_\{\\beta,K\}\]is no longer ensured, so the empirical expectation may fall belowlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)and void the upper bound\. Figure[5](https://arxiv.org/html/2605.24292#A3.F5)shows configurations of\(\|ℬ\|,β\)\(\|\\mathcal\{B\}\|,\\beta\)where this occurs in practice\. SPG\[Wang et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib47)\]observes this and notes that the linearizationlog⁡x≤x−1\\log x\\leq x\-1would restore the bound at the cost of looseness, motivating their tighter\-but\-biased choice\.

![Refer to caption](https://arxiv.org/html/2605.24292v1/images/app_cubo_heatmap.png)

Figure 5:CUBOβdiagnostic onL′∈\{4,8,16\}L^\{\\prime\}\\in\\\{4,8,16\\\}\.PPL of CUBOβas a function of the number of orderings and the Rényi exponentβ\\beta, on OWT \(left\) and LM1B \(right\)\. Gold borders mark cells exceedingELBOKfull\\mathrm\{ELBO\}\_\{K\}^\{\\mathrm\{full\}\}, where CUBO violates its nominal upper\-bound guarantee\. The only cell in the plane that is both valid and tight is\(number of orderings = 24,β=1\)\(\\text\{number of orderings = 24\},\\beta=1\), which coincides withELBOKfull\\mathrm\{ELBO\}\_\{K\}^\{\\mathrm\{full\}\}by construction; reducing number of orderings breaks the bound upward, increasingβ\\betapushes it past the truth downward\.
#### Connection to SPG\.

SPG’s “evidence upper bound” \(EUBO\)\[Wang et al\.,[2026](https://arxiv.org/html/2605.24292#bib.bib47)\]isCUBOβ\\mathrm\{CUBO\}\_\{\\beta\}specialized to the MDLM absorbing forward process\[Sahoo et al\.,[2024](https://arxiv.org/html/2605.24292#bib.bib37)\]: SPG’s Lemma 1 is \([17](https://arxiv.org/html/2605.24292#A3.E17)\) undern↔βn\\\!\\leftrightarrow\\\!\\beta, and Theorem 1 specializes it to the per\-token MDLM kernel\. This is distinct from the KL\-based EUBO of\[Ji and Shen,[2019](https://arxiv.org/html/2605.24292#bib.bib17)\], which requires posterior samples\.

### C\.2TVO: Thermodynamic\-integration Upper Bound

The TVO of\[Masrani et al\.,[2019](https://arxiv.org/html/2605.24292#bib.bib27)\]starts from the thermodynamic identity

log⁡pmodel​\(x\)=∫01𝔼π∼qβ\(⋅\|x\)​\[log⁡pmodel​\(x\|π\)\]​𝑑β,qβ​\(π\|x\)∝pmodel​\(x\|π\)β,\\log p\_\{\\mathrm\{model\}\}\(x\)\\;=\\;\\int\_\{0\}^\{1\}\\mathbb\{E\}\_\{\\pi\\sim q\_\{\\beta\}\(\\cdot\|x\)\}\\\!\\left\[\\log p\_\{\\mathrm\{model\}\}\(x\|\\pi\)\\right\]\\,d\\beta,\\qquad q\_\{\\beta\}\(\\pi\|x\)\\propto p\_\{\\mathrm\{model\}\}\(x\|\\pi\)^\{\\beta\},\(19\)whereqβq\_\{\\beta\}interpolates between the priorq0=p​\(π\)q\_\{0\}=p\(\\pi\)and the posteriorq1=pmodel​\(π\|x\)q\_\{1\}=p\_\{\\mathrm\{model\}\}\(\\pi\|x\)\. The integrand is monotone inβ\\beta\[Masrani et al\.,[2019](https://arxiv.org/html/2605.24292#bib.bib27)\], so the right Riemann sum on the equispaced gridβλ=λ/Λ\\beta\_\{\\lambda\}=\\lambda/\\Lambdaupper\-bounds the integral:

logpmodel\(x\)≤1Λ∑λ=1Λ𝔼π∼qβλ\(⋅\|x\)\[logpmodel\(x\|π\)\]=:TVOΛU\(x\)\.\\log p\_\{\\mathrm\{model\}\}\(x\)\\;\\leq\\;\\frac\{1\}\{\\Lambda\}\\sum\_\{\\lambda=1\}^\{\\Lambda\}\\mathbb\{E\}\_\{\\pi\\sim q\_\{\\beta\_\{\\lambda\}\}\(\\cdot\|x\)\}\\\!\\left\[\\log p\_\{\\mathrm\{model\}\}\(x\|\\pi\)\\right\]\\;=:\\;\\mathrm\{TVO\}^\{U\}\_\{\\Lambda\}\(x\)\.\(20\)
#### Empirical Monte Carlo estimator\.

Using the sameKKsampled orderings as in \([11](https://arxiv.org/html/2605.24292#S3.E11)\) with self\-normalized weightsw¯k\(β\)=pmodel​\(x\|π\(k\)\)β/∑jpmodel​\(x\|π\(j\)\)β\\bar\{w\}\_\{k\}^\{\(\\beta\)\}=p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)^\{\\beta\}\\,/\\,\\sum\_\{j\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j\)\}\)^\{\\beta\}, the empirical MC estimator \(Table[1](https://arxiv.org/html/2605.24292#S4.T1)\) is

TVO^Λ,KU​\(x\)=1Λ​∑λ=1Λ∑k=1Kw¯k\(βλ\)​log⁡pmodel​\(x\|π\(k\)\)\.\\widehat\{\\mathrm\{TVO\}\}^\{U\}\_\{\\Lambda,K\}\(x\)\\;=\\;\\frac\{1\}\{\\Lambda\}\\sum\_\{\\lambda=1\}^\{\\Lambda\}\\sum\_\{k=1\}^\{K\}\\bar\{w\}\_\{k\}^\{\(\\beta\_\{\\lambda\}\)\}\\,\\log p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(k\)\}\)\.\(21\)

#### Sources of bias\.

Two structural sources\.*\(i\)*Self\-normalized importance weightsw¯k\(β\)\\bar\{w\}\_\{k\}^\{\(\\beta\)\}have𝒪​\(1/K\)\\mathcal\{O\}\(1/K\)bias\[Owen,[2013](https://arxiv.org/html/2605.24292#bib.bib31)\]: asβ→1\\beta\\to 1the targetqβq\_\{\\beta\}concentrates on a vanishing subset of orderings while the proposal stays uniform, so weights at largeβ\\betacollapse onto a few outlier samples\. As a result,𝔼​\[TVO^Λ,KU\]≠TVOΛU\\mathbb\{E\}\[\\widehat\{\\mathrm\{TVO\}\}^\{U\}\_\{\\Lambda,K\}\]\\neq\\mathrm\{TVO\}^\{U\}\_\{\\Lambda\}at finiteKK, and the population upper\-bound guarantee no longer ensures𝔼​\[TVO^Λ,KU\]≥log⁡pmodel​\(x\)\\mathbb\{E\}\[\\widehat\{\\mathrm\{TVO\}\}^\{U\}\_\{\\Lambda,K\}\]\\geq\\log p\_\{\\mathrm\{model\}\}\(x\)\.*\(ii\)*The Riemann discretization adds an𝒪​\(1/Λ\)\\mathcal\{O\}\(1/\\Lambda\)residual that does not vanish at fixedΛ\\Lambda\.

### C\.3IS\-VG\-B: Importance Sampling Variational Gap Bound

IS\-VG\-B\[Struski et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib44)\]constructs an upper bound onlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)by adding a correction term to the \(lower\)ELBOs\\mathrm\{ELBO\}\_\{s\}bound\. The strategy is to pair a two\-point inequality with a tunable parameterCC, optimizeCCin closed form, and estimate the optimum using a second independent MC estimator drawn from the same distribution\.

The starting two\-point inequality is

log⁡𝔼​X≤𝔼​log⁡X−1\+C\+e−C​𝔼​\[Y/X\],\\log\\mathbb\{E\}X\\;\\leq\\;\\mathbb\{E\}\\log X\-1\+C\+e^\{\-C\}\\,\\mathbb\{E\}\[Y/X\],which holds for anyC∈ℝC\\in\\mathbb\{R\}which holds for anyC∈ℝC\\in\\mathbb\{R\}whenXXandYYare i\.i\.d\. positive random variables, with optimum atC⋆=log⁡𝔼​\[Y/X\]C^\{\\star\}=\\log\\mathbb\{E\}\[Y/X\]\[Struski et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib44), Theorem 4 and Corollary 4\]\. SubstitutingC⋆C^\{\\star\}collapses the right\-hand side to𝔼​log⁡X\+log⁡𝔼​\[Y/X\]\\mathbb\{E\}\\log X\+\\log\\mathbb\{E\}\[Y/X\]\. ReplacingXXby thess\-sample MC averageX¯s=1s​∑iXi\\bar\{X\}\_\{s\}=\\tfrac\{1\}\{s\}\\sum\_\{i\}X\_\{i\}preserves the bound at eachsssince𝔼​X¯s=𝔼​X\\mathbb\{E\}\\bar\{X\}\_\{s\}=\\mathbb\{E\}X, andlog⁡𝔼​\[Y¯s/X¯s\]→0\\log\\mathbb\{E\}\[\\bar\{Y\}\_\{s\}/\\bar\{X\}\_\{s\}\]\\to 0ass→∞s\\to\\inftyon bounded support\[Struski et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib44), Theorem 5\], so the bound becomes asymptotically tight\. Specializing to our setting withX≡pmodel​\(x\|π\)X\\equiv p\_\{\\mathrm\{model\}\}\(x\|\\pi\)and uniformp​\(π\)p\(\\pi\)gives

IS​\-​VG​\-​Bs​\(x\):=𝔼​\[log⁡p^model,s​\(x\)\]⏟=ELBOs\+log⁡𝔼​\[p~model,s​\(x\)p^model,s​\(x\)\]⏟correction term≥log⁡pmodel​\(x\),\\mathrm\{IS\\text\{\-\}VG\\text\{\-\}B\}\_\{s\}\(x\)\\;:=\\;\\underbrace\{\\mathbb\{E\}\\\!\\left\[\\log\\widehat\{p\}\_\{\\mathrm\{model\},s\}\(x\)\\right\]\}\_\{=\\;\\mathrm\{ELBO\}\_\{s\}\}\\;\+\\;\\underbrace\{\\log\\,\\mathbb\{E\}\\\!\\left\[\\frac\{\\widetilde\{p\}\_\{\\mathrm\{model\},s\}\(x\)\}\{\\widehat\{p\}\_\{\\mathrm\{model\},s\}\(x\)\}\\right\]\}\_\{\\text\{correction term\}\}\\;\\geq\\;\\log p\_\{\\mathrm\{model\}\}\(x\),\(22\)wherep^model,s\\widehat\{p\}\_\{\\mathrm\{model\},s\}andp~model,s\\widetilde\{p\}\_\{\\mathrm\{model\},s\}are independentss\-sample MC averages ofpmodel​\(x\|π\)p\_\{\\mathrm\{model\}\}\(x\|\\pi\)as in \([11](https://arxiv.org/html/2605.24292#S3.E11)\)\. The first term is theELBOs\\mathrm\{ELBO\}\_\{s\}*lower*bound at sample sizess, the correction is what flips the inequality into an*upper*bound\.

#### Empirical Monte Carlo estimator\.

The correction’s outer expectation is itself estimated by Monte Carlo overnpn\_\{p\}independent pairs ofss\-sample MC estimators \(total budgetK=2​s​npK=2\\,s\\,n\_\{p\}\)\. Expanding the per\-pair averagesp^model,s\(j\)​\(x\)=1s​∑i=1spmodel​\(x\|π\(j,i\)\)\\widehat\{p\}\_\{\\mathrm\{model\},s\}^\{\(j\)\}\(x\)=\\tfrac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j,i\)\}\)andp~model,s\(j\)​\(x\)=1s​∑i=1spmodel​\(x\|π~\(j,i\)\)\\widetilde\{p\}\_\{\\mathrm\{model\},s\}^\{\(j\)\}\(x\)=\\tfrac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\widetilde\{\\pi\}^\{\(j,i\)\}\)explicitly recovers the form shown in Table[1](https://arxiv.org/html/2605.24292#S4.T1):

IS​\-​VG​\-​B^s,np​\(x\)=1np​∑j=1nplog⁡\(1s​∑i=1spmodel​\(x\|π\(j,i\)\)\)\+log⁡\(1np​∑j=1np∑i=1spmodel​\(x\|π~\(j,i\)\)∑i=1spmodel​\(x\|π\(j,i\)\)\),\\widehat\{\\mathrm\{IS\\text\{\-\}VG\\text\{\-\}B\}\}\_\{s,n\_\{p\}\}\(x\)\\;=\\;\\frac\{1\}\{n\_\{p\}\}\\sum\_\{j=1\}^\{n\_\{p\}\}\\log\\\!\\left\(\\frac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j,i\)\}\)\\right\)\\;\+\\;\\log\\\!\\left\(\\frac\{1\}\{n\_\{p\}\}\\sum\_\{j=1\}^\{n\_\{p\}\}\\frac\{\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\widetilde\{\\pi\}^\{\(j,i\)\}\)\}\{\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j,i\)\}\)\}\\right\),\(23\)whereπ\(j,i\)\\pi^\{\(j,i\)\}andπ~\(j,i\)\\widetilde\{\\pi\}^\{\(j,i\)\}are theii\-th i\.i\.d\. samples of thejj\-th X\-side and Y\-side MC estimators, respectively, both drawn fromp​\(π\)p\(\\pi\)\. The first term averagesnpn\_\{p\}ELBOs\\mathrm\{ELBO\}\_\{s\}samples, the second averages the ratios*inside*the log to estimate the population correction\.

#### Source of bias\.

The first term in \([23](https://arxiv.org/html/2605.24292#A3.E23)\) is an MC estimate ofELBOs\\mathrm\{ELBO\}\_\{s\}, which by Jensen lies belowlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)at any finitess, this gap is part of the construction, since the correction is designed precisely to lift the bound back abovelog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)\. The second term is meant to do that lifting, but is itself alog\\logof a Monte Carlo mean: lettingr\(j\)=∑i=1spmodel​\(x\|π~\(j,i\)\)/∑i=1spmodel​\(x\|π\(j,i\)\)r^\{\(j\)\}=\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\widetilde\{\\pi\}^\{\(j,i\)\}\)\\,\\big/\\,\\sum\_\{i=1\}^\{s\}p\_\{\\mathrm\{model\}\}\(x\|\\pi^\{\(j,i\)\}\)denote the per\-pair ratio, Jensen gives𝔼​\[log⁡1np​∑jr\(j\)\]≤log⁡𝔼​\[r\]\\mathbb\{E\}\\\!\\left\[\\log\\tfrac\{1\}\{n\_\{p\}\}\\sum\_\{j\}r^\{\(j\)\}\\right\]\\leq\\log\\mathbb\{E\}\[r\], so the empirical correction underestimates the population value and the empirical IS\-VG\-B can fall belowlog⁡pmodel​\(x\)\\log p\_\{\\mathrm\{model\}\}\(x\)at finiteKK\.\[Struski et al\.,[2023](https://arxiv.org/html/2605.24292#bib.bib44)\]acknowledge this in their Limitations: the empirical estimator “results in nonrigorous bounds\.”

## Appendix DExperimental details

This appendix provides the experimental details for the results reported in the main paper: models and datasets \(§[D\.1](https://arxiv.org/html/2605.24292#A4.SS1)\), construction of the orders \(§[D\.2](https://arxiv.org/html/2605.24292#A4.SS2)\), estimator hyperparameters used in the main tables \(§[D\.3](https://arxiv.org/html/2605.24292#A4.SS3)\), and compute resources \(§[D\.4](https://arxiv.org/html/2605.24292#A4.SS4)\)\.

### D\.1Models and datasets

LM1B training details\.For LM1B, we follow the original BD3\-LM training procedure\. We first train an MDLM with the BD3\-LM repository’s default hyperparameters \(global batch size512512, learning rate3×10−43\\\!\\times\\\!10^\{\-4\},150,000150\{,\}000steps, sentence\-wrap data preprocessing\), and then fine\-tune it separately for each block sizeL′∈\{4,8,16\}L^\{\\prime\}\\in\\\{4,8,16\\\}to obtain the BD3\-LM checkpoints\. The ARM baseline is trained independently from scratch with the same architecture, tokenizer, and sequence length\. The synthetic\-finetuned ARMψARM​\-​FT\\psi\_\{\\mathrm\{ARM\\text\{\-\}FT\}\}used in Figure[3](https://arxiv.org/html/2605.24292#S5.F3)is a one\-off OWT experiment and is not available for LM1B, so the corresponding bar is missing from the LM1B panel of Figure[4](https://arxiv.org/html/2605.24292#A1.F4)\.

### D\.2Sampling orderings

For each block sizeL′L^\{\\prime\}, we precompute a fixed set ofMMlatent orderings per block, with each ordering specifying the unmasking sequence over theL′L^\{\\prime\}block positions\. The bank is constructed once per\(L′,dataset\)\(L^\{\\prime\},\\text\{dataset\}\)pair and shared across all estimators in the table\. Number of latent orderings and construction protocol are summarized in Table[4](https://arxiv.org/html/2605.24292#A4.T4)\.

Table 4:Latent orderings construction per block size\.L′L^\{\\prime\}ConstructionNumber of orderings44full enumeration of4\!4\!orederings242488random sampling64641616random sampling128128To cover the MDM regime, the same set of orderings is evaluated under the multi\-step parallel\-generation schedule withNFE∈\{1,2,4,…,L′\}\\mathrm\{NFE\}\\in\\\{1,2,4,\\dots,L^\{\\prime\}\\\}, whereNFE\\mathrm\{NFE\}is the number of forward passes through the MDM per block\. SmallerNFE\\mathrm\{NFE\}corresponds to coarser parallel denoising\. The validation\-set size used per evaluation is100100batches with the eval batch size of the BD3\-LM repo, giving roughly4×1054\\\!\\times\\\!10^\{5\}per\-block scores per ordering atL′=4L^\{\\prime\}=4\.

### D\.3Estimator hyperparameters

All estimators in Tables[2](https://arxiv.org/html/2605.24292#S5.T2)–[3](https://arxiv.org/html/2605.24292#A1.T3)share a common per\-row number of orderings depending onL′L^\{\\prime\}\. This number is split between the two halves used by TUBE, and the corresponding hyperparameters of CUBO, TVOU, and IS\-VG\-B are chosen so that all estimators draw orderings per row\. Table[5](https://arxiv.org/html/2605.24292#A4.T5)summarizes the configuration\.

Table 5:Estimator hyperparameters used in the main tables\.The per\-row number of orderings is fixed per block size so that estimators are compute\-comparable across rows\. ELBOKuses all available orderings deterministically\.EstimatorL′=4L^\{\\prime\}=4L′=8L^\{\\prime\}=8L′=16L^\{\\prime\}=16TUBE \(splitB/2\+B/2B/2\+B/2\)12\+1212\+1232\+3232\+3264\+6464\+64CUBOβ=2\(single MC set of sizeBB\)24246464128128TVOU\(Riemann partitionsΛ\\Lambda,K=BK=B\)Λ=200\\Lambda=200Λ=200\\Lambda=200Λ=200\\Lambda=200IS\-VG\-B \(np=2n\_\{\\mathrm\{p\}\}=2,k=B/4k=B/4\)2×62\\times 62×162\\times 162×322\\times 32ELBOK\(full bank, deterministic\)M=24M=24M=64M=64M=128M=128ELBO \(15 random\-seed runs\)15 seeds15 seeds15 seedsMC re\-seeds for±\\pmstd101010101010The heatmap in Appendix[C](https://arxiv.org/html/2605.24292#A3)sweeps wider hyperparameter rangesβ∈\{1\.0,1\.5,2\.0,3\.0,5\.0\}\\beta\\in\\\{1\.0,1\.5,2\.0,3\.0,5\.0\\\}for CUBO\. The±\\pmstandard deviations in the tables are computed across1010MC re\-seeds, each drawing a fresh per\-row subset of sizeBBfrom the bank\.

### D\.4Compute

All evaluations run on a single NVIDIA H200 140 GB GPU under PyTorch 2\.5\.1 / CUDA 12\.1\. Wall\-clock times for the OWT validation split with100100batches are summarized in Table[6](https://arxiv.org/html/2605.24292#A4.T6)\. LM1B times are within30%30\\%of OWT\. Total evaluation across both datasets and all three block sizes is roughly5050–6060GPU\-hours\.

Table 6:Wall\-clock per evaluation on a single H200 140 GB\(OWT/LM1B,100100batches, default eval batch size\)\.EvaluationL′=4L^\{\\prime\}=4L′=8L^\{\\prime\}=8L′=16L^\{\\prime\}=16ARM baseline \(per\-block AR\)1212m1212m1212mARM\-FT \(synth\-finetuned, OWT only\)1414m1414m1414mELBO \(1515seeds\)2828m3232m3838mOrdering bank \(M∈\{24,64,128\}M\\in\\\{24,64,128\\\}orderings\)3535m11h2525m22h5050mMulti\-step bank \(fullNFE\\mathrm\{NFE\}schedule\)4242m11h4040m33h3030m