TL;DR
Existing discrete diffusion models rely on rigid, hand-crafted noise matrices (like uniform noise or absorbing [MASK] tokens), severely limiting their expressiveness. The Discrete Markov Bridge (DMB) introduces an alternating learning framework that pairs an adaptive, diagonalizable transition-rate matrix with a reverse score network. DMB provides theoretical accessibility guarantees, slashes the compute/memory costs of matrix exponentials, and sets a new state of the art on Text8 while matching continuous models on CIFAR-10.
What Problem Does This Paper Address?
Continuous diffusion models (and continuous normalizing flows) have revolutionized generative modeling in part because their noise schedules and prior transitions can be flexibly designed or learned. In contrast, discrete diffusion models—governed by Continuous-Time Discrete Markov Chains (CTDMCs)—remain constrained by hand-designed transition-rate matrices ($Q$).
Nearly all discrete diffusion models rely exclusively on two simple matrices:
- Uniform transitions: Randomly switching to any token with equal probability.
- Absorbing transitions: Gradually replacing tokens with an artificial
[MASK]token.
Arbitrary learnable matrices have historically been avoided because computing matrix exponentials ($\exp(Q)$) is computationally prohibitive, and storing dense transition matrices for high-dimensional discrete data requires $O(n^2 d)$ space (where $n$ is vocabulary size and $d$ is sequence length). As a result, discrete diffusion lacks the flexible latent-representation capabilities typical of variational inference.
Methods
DMB reformulates discrete generation as a bidirectional, two-stage variational process optimized via the continuous-time Evidence Lower Bound (ELBO):
- Matrix-Learning (Forward Process): Instead of fixing $Q$, DMB learns an adaptive rate transition matrix decomposed as $Q_\alpha = A H A^{-1}$.
- $A$ is a fixed permutation matrix that sorts states by marginal probability.
- $H$ is a structured upper-triangular matrix governed by only $n - 1$ learnable parameters $\alpha = \{a_1, \dots, a_{n-1}\}$.
- Crucially, $H$ is analytically diagonalizable into $U \Lambda_\alpha U^{-1}$, where $U$ is a constant all-ones upper-triangular matrix and $\Lambda_\alpha$ is diagonal. Consequently, $\exp(Q_\alpha) = (AU) \exp(\Lambda_\alpha) (AU)^{-1}$, reducing an expensive matrix exponential to an $O(n)$ element-wise diagonal exponential with $O(nd)$ parameter footprint.
- $Q_\alpha$ is trained to map the data distribution to an adapted latent distribution by minimizing a forward KL divergence term $J_Q$.
- Score-Learning (Reverse Process): A neural network $s_\theta(x_t, t)$ learns the probability ratios $\frac{p_t(y)}{p_t(x)}$ required to form the reverse CTDMC rate matrix via concrete score matching ($J_\text{score}$).
- Bidirectional Alternating Optimization: The algorithm alternates between updating the rate matrix parameters $\alpha$ and updating the neural denoiser $\theta$, with the reverse sampling step periodically estimating empirical data distributions to supervise forward matrix learning.
[Forward: Matrix-Learning Q_α]
Data Distribution (μ) ────────► Noise Prior (p_T)
▲ │
└──────── Reverse CTDMC ─────┘
[Backward: Score-Learning s_θ]
Datasets
The authors evaluate DMB on two standard generative benchmarks without introducing new datasets:
- Text8: Character-level language modeling benchmark ($n = 27$ tokens, sequence length $d = 256$).
- CIFAR-10: Image generation benchmark evaluated by quantizing images into discrete tokens using a VQ-VAE codebook.
Key Insights and Ideas
- Universal Accessibility with Minimal Parameters: The authors prove that any discrete distribution $p$ can transition to any other distribution $q$ through a single valid rate matrix ($p = q e^Q$) requiring only $n-1$ free parameters and a permutation matrix (Lemma 4.4 & Theorem 4.2).
- Bypassing the Matrix Exponential Bottleneck: By designing $H$ such that its eigenvectors are constant, parameter updates only affect the diagonal eigenvalues. Computing transition probabilities across time steps becomes practically as fast as uniform diffusion.
- No
[MASK]Token Needed: Absorbing-state models alter data vocabulary and often struggle with temporal/bidirectional dependencies. DMB achieves top-tier results working directly on the native vocabulary without special tokens. - Convergence Guarantees: The authors prove that under optimal subprocess steps, the alternating updates of Matrix-learning and Score-learning monotonically decrease the KL divergence $\lim_{k\to\infty} D_{KL}(\mu \parallel p_0^{(k)})$, formally establishing framework stability.
Key Results
- Text8 (Language Modeling): DMB achieves an Evidence Lower Bound / Bits-per-Character (BPC) of $\le 1.38$, outperforming:
- Mask-based models like SEDD Absorb ($\le 1.39$) and D3PM Absorb ($\le 1.45$).
- Mask-free discrete diffusion baselines by a large margin (SEDD Uniform at $\le 1.47$ and D3PM Uniform at $\le 1.61$).
- CIFAR-10 (Image Synthesis): Within a discrete VQ-VAE latent space, DMB achieves an Inception Score (IS) of 8.64 and Fréchet Inception Distance (FID) of 11.63.
- Outperforms discrete diffusion baselines (D3PM absorbing IS 6.78, uniform IS 5.99, Gauss+Logistic IS 8.56).
- Outperforms continuous image baselines including SNGAN (FID 21.7) and DDPM fixed isotropic (FID 13.51).
Limitations and Future Work
- Theoretical Assumptions: The convergence proof assumes that both sub-processes (score matching and matrix optimization) reach their global optimum at each epoch, which is not guaranteed with deep neural networks in practice.
- Vocabulary Scalability: While $O(nd)$ space complexity is a massive improvement over dense $O(n^2 d)$ matrices, scaling to large language model vocabularies (e.g., $n \ge 32{,}000$ subword tokens) may still present computational and memory challenges.
- Alternative Objectives: The current framework strictly targets the continuous-time ELBO; exploring other variational objectives or flow-matching formulations remains an open avenue.
Summary updated