Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
Many applications require sampling from high-dimensional categorical distributions with local dependence, but discrete diffusion models lack end-to-end statistical guarantees. This paper introduces a pinning decomposition of the discrete score under uniform noising, showing that time dependence separates multiplicatively from target dependence for Markov random fields of order $d$. Building on this, the authors design a weight-sharing neural score learner and prove a sample-complexity rate of $\widetilde O_{\mathbb P}(S^d/n)$, replacing the ambient dimension $D$ with the interaction order $d$.
The paper is a strong theoretical contribution that rigorously connects score learning to sampling for discrete diffusions on structured domains. The pinning decomposition is novel, and the end-to-end $S^d/n$ rate is a clear improvement over the unstructured $S^D/n$ baseline. Nevertheless, the results are held back by several issues: the network width bound in Theorem 1 contains an exponential-in-$D$ term $(S+1)^{D-d-1}$; the theory is tightly restricted to uniform noising; and the minimax-optimality claim cites an unpublished Cho and Wu (2026) manuscript that cannot be independently verified. Experiments at $D\le 32$ and $d=2$ support the weight-sharing benefit but do not establish large-scale practicality.
The pinning decomposition in Proposition 1 is the centerpiece and is proved exactly: $g_t(\mathbf x)=\sum_{\mathsf m\subseteq[D]}\mu_t^{|\mathsf m|}\alpha_t^{D-|\mathsf m|}A_{\mathsf m}(\mathbf x_{\mathsf m})$, where the time weights are explicit and the target enters only through partial marginals. This explains why a single network can approximate the score uniformly over all noise levels. The authors' attribution of tau-leaping to Campbell et al. (2022) is accurate, as that work indeed introduced the continuous-time CTMC reverse process and leveraged tau-leaping for discrete denoising. Finally, the reduction of the effective parameter count to order $D^d S^d$ is a meaningful structural insight.
First, although the effective sparsity is polynomial, Theorem 1 allows network width to scale as $(S+1)^{D-d-1}$, which is exponential in the ambient dimension $D$. The weight-sharing map $\omega$ is argued to compress this, but the construction is predominantly existential and its practical realization in standard deep-learning frameworks is unclear. Second, the pinning decomposition is an artifact of uniform noising: coordinate-wise independent transitions with Binomial weights are essential, and there is no extension to masking, absorbing-state, or other non-uniform forward processes common in recent discrete-diffusion literature. Third, the minimax lower bound appealed to in the optimality claim comes from Cho and Wu (2026), a contemporaneous unpublished paper that readers cannot currently verify. These limitations significantly narrow the scope and immediate applicability of the guarantees.
Section 5 reports experiments on Potts chains, frustrated Ising ladders, and categorical trees with $d=2$ and $D$ up to $32$. The authors show that weight-sharing networks outperform fully connected ones in score risk and edge-pair total variation at $D=32$, and that a single trained score network works across inference grids, which aligns with the theory. However, the empirical validation is thin: no comparison against autoregressive baselines or other discrete diffusion variants is provided; only $d=2$ and modest dimensions are tested; and the bespoke combinatorial architecture of Section 4.2 is approximated by a simple convolutional network in practice, leaving a gap between the theoretical construction and the empirical instantiation.
The manuscript contains no statement about code or data release. Reproducing the exact experiments would require reimplementing the tau-leaping sampler (Algorithm 1) and, more critically, the weight-sharing architecture of Definition 2 with the combinatorial marginal-elimination layers described in Section 4.2. The paper defers hyperparameters to Appendix A, but the main text gives insufficient detail to reconstruct the weight-sharing map $\omega$ or the backward-induction elimination schedule from scratch. Because the construction is specific to order-$d$ MRFs and lacks a general software implementation, independent reproduction would demand substantial effort.
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 \emph{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 \emph{weight-sharing neural score learner} and combine it with $\tau$-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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.