# Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 34 of its 83 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Placed in

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

## Builds on (most cited first, 30 of 34)

- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Dream 7B: Diffusion Large Language Models](https://mlsanity.com/paper/2508.15487/) (2025)
- [Mercury: Ultra-Fast Language Models Based on Diffusion](https://mlsanity.com/paper/2506.17298/) (2025)
- [Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens](https://mlsanity.com/paper/2401.17377/) (2024)
- [Generative Modeling with Denoising Auto-Encoders and Langevin Sampling](https://mlsanity.com/paper/2002.00107/) (2020)
- [Generalized Interpolating Discrete Diffusion](https://mlsanity.com/paper/2503.04482/) (2025)
- [Discrete Diffusion in Large Language and Multimodal Models: A Survey](https://mlsanity.com/paper/2506.13759/) (2025)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025)
- [Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis](https://mlsanity.com/paper/2410.02321/) (2024)
- [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025)
- [Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models](https://mlsanity.com/paper/2506.02318/) (2025)
- [Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees](https://mlsanity.com/paper/2509.16756/) (2025)
- [Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees](https://mlsanity.com/paper/2602.15008/) (2026)
- [Statistical Properties of Rectified Flow](https://mlsanity.com/paper/2511.03193/) (2025)
- [Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics](https://mlsanity.com/paper/2512.00580/) (2025)
- [Flow Matching is Adaptive to Manifold Structures](https://mlsanity.com/paper/2602.22486/) (2026)
- [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (2026)
- [The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity](https://mlsanity.com/paper/2608.13520/) (2026)
- [Nonparametric estimation of a factorizable density using diffusion models](https://mlsanity.com/paper/2501.01783/) (2025)
- [Lipschitz regularity in Flow Matching and Diffusion Models: sharp sampling rates and functional inequalities](https://mlsanity.com/paper/2604.06065/) (2026)
- [Denoising Diffusions with Optimal Transport: Localization, Curvature, and Multi-Scale Complexity](https://mlsanity.com/paper/2411.01629/) (2024)
- [Dimension-independent rates for structured neural density estimation](https://mlsanity.com/paper/2411.15095/) (2024)
- [Discrete State Diffusion Models: A Sample Complexity Perspective](https://mlsanity.com/paper/2510.10854/) (2025)
- [Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions](https://mlsanity.com/paper/2502.07939/) (2025)
- [No-Regret Generative Modeling via Parabolic Monge-Amp`ere PDE](https://mlsanity.com/paper/2504.09279/) (2025)
- [Provably adaptive sampling with uniform and remasking discrete diffusion models](https://mlsanity.com/paper/2608.23554/) (2026)

## Abstract (arXiv)

Many applications in statistics, economics, and physics require sampling from high-dimensional categorical distributions with local dependence structures. Examples include finite memory language models, Ising and Potts systems in statistical physics and protein folding, etc. In modern machine learning, discrete diffusions have emerged as a flexible approach for sampling such data, with strong empirical performance. Motivated by this, we develop learning methods with end-to-end sample complexity bounds for discrete diffusion with uniform noising under local dependence, which we model through low order Markov random fields (MRFs). Our main technical insight is a new pinning decomposition of the discrete score. It shows that unlike in continuous diffusions, the score decomposes into components where the dependence on time separates multiplicatively from the dependence on the target. Building on this decomposition, we propose a weight-sharing neural score learner and combine it with τ-leaping to obtain an end-to-end sampling procedure. Rather than treating score-learning error as a black-box input, as is common in existing sampling analyses, we study the score learning error from finite data and derive optimal sampling guarantees with explicit dependence on the vocabulary size, the interaction order of the MRF, and the sample size. Moreover, our strategy trains a single score network across uniform noise levels while leaving the sampling discretization to be chosen at inference-time. This allows the same trained model to trade accuracy for computational cost as inference-time budgets vary. Numerical experiments on Potts, Ising, and tree-structured models show that weight-sharing score networks outperform fully connected ones for sampling long sequences.