Research map / Probabilistic and scientific modeling / Variational and generative sampling
Discrete Markov Probabilistic Models: An Improved Discrete Score-Based Framework with sharp convergence bounds under minimal assumptions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Discrete Markov Probabilistic Models (DMPM), a score-based CTMC bit-flip diffusion for discrete data with a denoiser parameterization, and proves KL convergence bounds under minimal assumptions, evaluated on Bernoulli sawtooth data and binarized MNIST.
Problem
Discrete generative modeling via diffusion lacks theoretically sound, stable, and efficient formulations with convergence guarantees; prior discrete diffusion theory relies on strong assumptions.
Approach
A forward bit-flip CTMC on the hypercube whose time-reversal has a discrete score expressed as a conditional expectation of a function of the forward process; this yields an L2 regression and a denoiser reparameterization with cross-entropy loss, plus denoise-renoise and flip-schedule samplers.
Key results
- On binarized MNIST, DMPM denoise-renoise reaches FID 2.89 at 200 steps versus MD4 4.48 and DFM 16.26 at the same step count (DFM 7.34 at 500 steps).
- With linear flip-schedule, DMPM achieves FID 4.77 using only 25 network calls (reported in text).
- On the sawtooth Bernoulli data for d=4 to 16, DMPM achieves lower SWD than MD4 and DFM at every dimension (e.g., 2.342e-3 vs 4.045e-3 for MD4 at d=12).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DMPM denoise-renoise instead of MD4 | DMPM · Binarized MNIST, 200 reverse steps | FID: 4.48 -> 2.89 | Helped |
| Use DMPM denoise-renoise instead of MD4 | DMPM · Binarized MNIST, 200 reverse steps | Fdc1: 0.83 -> 1.00 | Helped |
| Use DMPM denoise-renoise instead of DFM | DMPM · Binarized MNIST, 200 reverse steps | FID: 16.26 -> 2.89 | Helped |
| Use DMPM instead of MD4 or DFM | Discrete Bernoulli data · Sawtooth Bernoulli, d=4, d=8, d=12, d=16 | SWD | Helped |
| Use a linear rather than constant flip-schedule (ablation) | DMPM flip-schedule sampler · Binarized MNIST | FID | Helped |
| Scale losses by 1/wt (ablation) | DMPM training objective · Binarized MNIST | FID | Helped |
| Combine the denoiser L2, entropy, and cross-entropy losses (ablation) | DMPM training objective · Binarized MNIST | FID | Helped |
| Increase the reverse-step count for the flip-schedule sampler (ablation) | DMPM flips · Binarized MNIST | FID: 16.30, 9.98, 11.07, 9.07, 7.80, 10.84 | Mixed |
| Increase the reverse-step count for the denoise-renoise sampler (ablation) | DMPM denoise-renoise · Binarized MNIST | FID: 78.20, 20.94, 8.62, 3.98, 2.89, 4.36 | Mixed |
Surprising findings
- Flip-schedule DMPM FID is non-monotone in reverse steps (e.g., 9.07 at 100 steps, 7.80 at 200, 10.84 at 500), and DFM's standard results depend strongly on step count.
Limitations
- Convergence bounds rely on an entropic score-approximation assumption (Assumption 2.1) and, for the tight rate, on data with full support (Assumption 2.2).
- Experiments limited to low-dimensional synthetic Bernoulli data and binarized MNIST.
- Time-dependent rate extension left to future work.
Experimental setup
Datasets: synthetic sawtooth Bernoulli data binarized MNIST
Benchmarks: binarized MNIST synthetic sawtooth Bernoulli
Metrics: FID F_1^dc (density-coverage harmonic mean) sliced Wasserstein distance
Baselines: MD4 DFM (discrete flow matching)
Builds on: discrete diffusion (Sohl-Dickstein et al., 2015) Multinomial diffusion / D3PM-style discrete diffusion Gillespie algorithm Conforti et al. 2025 relative Fisher information bounds
Closest papers by meaning
- Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Time (NeurIPS 2024 · similarity 0.88)
- Piecewise deterministic generative models (NeurIPS 2024 · similarity 0.88)
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.86)
- Unlocking Guidance for Discrete State-Space Diffusion and Flow Models (ICLR 2025 · similarity 0.86)
- Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models (ICLR 2024 · similarity 0.86)
- Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.