# Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions

arXiv: https://arxiv.org/abs/2502.07939 · HTML: https://mlsanity.com/paper/2502.07939/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 11 Feb 2025.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 14 of 14)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Consistency Models](https://mlsanity.com/paper/2303.01469/) (2023)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [WaveGrad: Estimating Gradients for Waveform Generation](https://mlsanity.com/paper/2009.00713/) (2020)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning](https://mlsanity.com/paper/2208.04202/) (2022)
- [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024)
- [Continuous diffusion for categorical data](https://mlsanity.com/paper/2211.15089/) (2022)
- [Generator Matching: Generative modeling with arbitrary Markov processes](https://mlsanity.com/paper/2410.20587/) (2024)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Categorical SDEs with Simplex Diffusion](https://mlsanity.com/paper/2210.14784/) (2022)
- [Sampling Binary Data by Denoising through Score Functions](https://mlsanity.com/paper/2502.00557/) (2025)

## Built on by (most cited first, 4 of 4)

- [Wasserstein Convergence of Critically Damped Langevin Diffusions](https://mlsanity.com/paper/2511.02419/) (2025)
- [Parallelism, critical windows, and separations among diffusion language models](https://mlsanity.com/paper/2609.20539/) (2026)
- [Sample complexity bounds for categorical Markov random fields via Discrete Diffusions](https://mlsanity.com/paper/2610.02128/) (2026)
- [Bernoulli Flow Models: Self-Consistent Generative Modeling for Binary Data](https://mlsanity.com/paper/2610.11362/) (2026)

## Abstract (arXiv)

This paper introduces Discrete Markov Probabilistic Models (DMPMs), a novel discrete diffusion algorithm for discrete data generation. The algorithm operates in discrete bit space, where the noising process is a continuous-time Markov chain that flips labels uniformly at random. The time-reversal process, like the forward noise process, is a jump process with its intensity governed by a discrete analogue of the classical score function. Crucially, this intensity is proven to be the conditional expectation of a function of the forward process, underlining theoretical alignment with score-based generative models. We establish convergence bounds for the algorithm under minimal assumptions, ensuring robustness and efficiency, which we demonstrate through experiments on low-dimensional Bernoulli-distributed datasets and high-dimensional binary MNIST data. The results highlight competitive performance in generating discrete structures compared to the state-of-the-art. This work bridges theoretical foundations and practical applications, advancing the development of effective and theoretically grounded discrete generative modeling.