Discrete Markov Bridge

Hengli Li, Yuxuan Wang, Song-Chun Zhu, Ying Nian Wu, Zilong Zheng

Abstract

Discrete diffusion has recently emerged as a promising paradigm in discrete data modeling. However, existing methods typically rely on a fixed rate transition matrix during training, which not only limits the expressivity of latent representations—a fundamental strength of variational methods—but also constrains the overall design space. To address these limitations, we propose Discrete Markov Bridge (DMB), a novel framework specifically designed for discrete representation learning. Our approach is built upon two key components: Matrix Learning and Score Learning. We conduct a rigorous theoretical analysis, establishing formal performance guarantees for Matrix Learning and proving the convergence of the overall framework. Furthermore, we analyze the space complexity of our method, addressing practical constraints identified in prior studies. Extensive empirical evaluations validate the effectiveness of the proposed Discrete Markov Bridge, which achieves an Evidence Lower Bound (ELBO) of 1.38 on the Text8 dataset, outperforming established baselines. Moreover, the proposed model demonstrates competitive performance on the CIFAR-10 dataset, achieving results comparable to those obtained by image-specific generation approaches.

Introduction

Generative modeling has undergone a revolution with the advent of diffusion models. While continuous models (e.g., for image generation) enjoy significant flexibility, their discrete counterparts—used for text or categorical data—have historically been constrained by "hard-coded" transition rules. In discrete diffusion, transition matrices are used to corrupt data (e.g., swapping tokens or masking). However, the reliance on fixed-rate matrices (such as Uniform or Absorb matrices) limits the model's expressive capacity, effectively acting as a hard-coded encoder in a Variational Autoencoder (VAE) context. Furthermore, the computational complexity of calculating matrix exponentials ($O(n^3)$) has restricted researchers to simple, less expressive matrix designs.

Methodology: The Discrete Markov Bridge

The Discrete Markov Bridge (DMB) introduces a bidirectional two-stage learning framework that allows the model to learn its own transition paths, combining the strengths of VAEs with the power of diffusion.

Overview of the Discrete Markov Bridge framework showing the interaction between Matrix Learning and Score Learning.

1. Matrix Learning (The Forward Bridge)

Instead of a predefined noise schedule, DMB learns an adaptive transition rate matrix ($Q_\alpha$). To overcome the $O(n^3)$ complexity bottleneck, the authors utilize a specific matrix structure ($Q = AHA^{-1}$) where $H$ is a diagonal matrix. This ensures the matrix is always valid (rows sum to zero) and allows for efficient computation of matrix exponentials, enabling the model to learn the most efficient latent representations for the data.

2. Score Learning (The Backward Bridge)

Following the forward path learning, a neural network is trained to estimate the "concrete score" (probability ratios). This score is used to construct the inverse transition matrix, effectively learning to reverse the learned noise process and reconstruct the original data distribution. The entire "bridge" connects the data distribution to a learned latent distribution, optimized via the Evidence Lower Bound (ELBO).

Theoretical Foundations

The DMB framework is supported by formal proofs regarding:

  • Validity: Ensuring the process always results in a valid probability distribution.
  • Accessibility: Confirming the model can reach any target distribution within the discrete space.
  • Convergence: Providing mathematical guarantees that the learning process will stabilize.

Experimental Results

The effectiveness of DMB was evaluated on two distinct benchmarks representing different data modalities.

Text Modeling (Text8)

On the Text8 character-level language modeling dataset, DMB achieved an ELBO of 1.38 Bits Per Character (BPC). This result outperforms established non-autoregressive baselines, including SEDD (1.39–1.47) and D3PM (1.45–1.61), demonstrating the advantage of learned transition paths in discrete spaces.

Image Modeling (CIFAR-10)

To test versatility, DMB was applied to discrete image tokens generated by a VQ-VAE on the CIFAR-10 dataset. The model achieved an Inception Score (IS) of 8.64 and a Fréchet Inception Distance (FID) of 11.63. These metrics are competitive with DDPM, the standard for continuous diffusion, highlighting DMB's potential as a unified framework for cross-modal discrete data.

Conclusion and Future Work

Discrete Markov Bridge represents a significant step toward flexible discrete generative modeling by parameterizing the noise process itself. While the current framework achieves state-of-the-art results, future research may focus on relaxing independence assumptions for high-dimensional data and exploring optimization bounds beyond the ELBO to further enhance modeling of complex dependencies.

Summary updated

Abstract

Discrete diffusion has recently emerged as a promising paradigm in discrete data modeling. However, existing methods typically rely on a fixed rate transition matrix during training, which not only limits the expressiveness of latent representations, a fundamental strength of variational methods, but also constrains the overall design space. To address these limitations, we propose Discrete Markov Bridge, a novel framework specifically designed for discrete representation learning. Our approach is built upon two key components: Matrix Learning and Score Learning. We conduct a rigorous theoretical analysis, establishing formal performance guarantees for Matrix Learning and proving the convergence of the overall framework. Furthermore, we analyze the space complexity of our method, addressing practical constraints identified in prior studies. Extensive empirical evaluations validate the effectiveness of the proposed Discrete Markov Bridge, which achieves an Evidence Lower Bound (ELBO) of 1.38 on the Text8 dataset, outperforming established baselines. Moreover, the proposed model demonstrates competitive performance on the CIFAR-10 dataset, achieving results comparable to those obtained by image-specific generation approaches.
BibTeX
@misc{li2025discrete,
  author = {Hengli Li and Yuxuan Wang and Song-Chun Zhu and Ying Nian Wu and Zilong Zheng},
  title = {{Discrete Markov Bridge}},
  year = {2025},
  eprint = {2505.19752},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.19752},
}
Figure