AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite-grid masked reverse sampler

Definition

For the finite masking chain with state space $S = (V \cup {m})^{L}$ and survival schedule $α_{0}, \dots, α_{N}$ , take probability vectors $h_{i, j} (z) \in Δ (V)$ for every position $i \in {1, \dots, L}$ , reverse step $j \in {1, \dots, N}$ , and current state $z \in S$ , where $Δ (V) = {p : V \to [0, 1] : \sum_{v \in V} p (v) = 1}$ . Initialize $Z_{N} = m^{L}$ . For $j = N, N - 1, \dots, 1$ , set $c_{j} = (α_{j - 1} - α_{j}) / (1 - α_{j})$ and update all positions from the same current state $z = Z_{j}$ as follows, independently across positions conditional on $z$ : if $z_{i} \neq m$ , set $Z_{j - 1, i} = z_{i}$ ; if $z_{i} = m$ and $c_{j} = 1$ , draw $Z_{j - 1, i}$ from $h_{i, j} (z)$ ; if $z_{i} = m$ and $c_{j} < 1$ , set $Z_{j - 1, i} = m$ when $U_{j, i}^{m a s k} \geq c_{j}$ , and otherwise draw the clean token from $h_{i, j} (z)$ using $U_{j, i}^{t o k e n}$ . The resulting one-coordinate row is $p_{i, j} (w ∣ z) = 1_{{w = z_{i}}}$ when $z_{i} \neq m$ , and, when $z_{i} = m$ , has mass $1 - c_{j}$ at $m$ and mass $c_{j} h_{i, j} (z) (v)$ at each $v \in V$ ; the sequence-state kernel is $P_{j} (z, z^{'}) = \prod_{i = 1}^{L} p_{i, j} (z_{i}^{'} ∣ z)$ . Return $Z_{0}$ after the finite loop. The mathematical random source is a finite product of mutually independent uniform $[0, 1]$ variables $U_{j, i}^{m a s k}, U_{j, i}^{t o k e n}$ , one pair for each step and position; an implementation seed is valid only insofar as its supplied random kernel has this law. For inverse-CDF token draws, fix any order $V = (v_{1}, \dots, v_{K})$ , choose the first $v_{k}$ whose cumulative mass strictly exceeds $U_{j, i}^{t o k e n}$ , and return $v_{K}$ if that draw equals $1$ . At $j = 1$ , $c_{1} = 1$ , so every remaining mask is unmasked.

Definition references

Finite masking diffusion chain: supplies the finite vocabulary, mask, length, grid, and survival schedule.

Measure kernel and probability kernel: a probability kernel is a family of probability-law rows with measurable evaluation functions; the finite $P_{j}$ above is a product of such rows.

Depends on

Finite masking diffusion chain

Used by

Negative expected finite masked-diffusion ELBO is weighted cross-entropy Corollary
A factorized reverse kernel fails for correlated tokens Counterexample
Finite masked-diffusion generative model Definition
Finite-grid masked sampler defines a normalized law Lemma
Forward path law is admissible for the finite masked model Lemma
Factorization and finite-endpoint warnings Remark
Masked-diffusion KL reduces to weighted cross-entropy Theorem

Dependency tree · two levels

2 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Subham Sekhar Sahoo et al., Simple and Effective Masked Diffusion Language Models, arXiv v1 (standard reference, not scraped)
Jacob Austin et al., Structured Denoising Diffusion Models in Discrete State-Spaces (standard reference, not scraped)