Discrete diffusion for categorical MRFs: a pinning decomposition and weight-sharing score learner yield end-to-end sample complexity bounds

It introduces a pinning decomposition of the discrete score, showing that unlike continuous diffusions, the discrete score decomposes into components where the dependence on time separates multiplicatively from the dependence on the target. Prior sampling analyses of discrete diffusion lacked an explicit structural characterization of the score; this decomposition supplies a structural basis for subsequent learning and sampling error analysis. The abstract presents this as the main technical insight, a theoretical construction; proof details are not provided in the abstract.

Building on the decomposition, it proposes a weight-sharing neural score learner and combines it with tau-leaping to obtain an end-to-end sampling procedure. Unlike common sampling analyses that treat score-learning error as a black-box input, this procedure places learning and sampling within a unified framework. The abstract states the method composition and combination, but gives no network sizes, training details, or hyperparameter settings.

It studies score learning error from finite data and derives optimal sampling guarantees with explicit dependence on vocabulary size, MRF interaction order, and sample size. It moves sample complexity from black-box assumptions toward explicit dependence on concrete problem parameters. The abstract claims optimal sampling guarantees but lists no specific rates, constants, or theorem numbers.

A single score network is trained across uniform noise levels while sampling discretization is chosen at inference time, letting the same trained model trade accuracy for computational cost as budgets vary; on Potts, Ising, and tree-structured models, weight-sharing score networks outperform fully connected ones for sampling long sequences. Decoupling training from inference lets one model adapt to different inference budgets, and numerical experiments support the advantage in long-sequence settings. Numerical experiments cover three model families; the abstract reports no specific metrics, sequence lengths, or statistical significance.

The results target categorical distributions with local dependence characterized by low-order Markov random fields, using discrete diffusion with uniform noising and tau-leaping sampling. They apply to settings in statistics, economics, and physics that require sampling from high-dimensional categorical distributions, such as finite-memory language models, Ising and Potts systems, and protein folding. The training strategy lets a single score network choose sampling discretization at inference time according to computational budget, making it directly relevant to engineering practice that reuses one model under varying inference costs.

The abstract does not give the specific rate form, constant factors, or theorem conditions of the sample complexity, nor does it report experimental metrics, sequence lengths, or comparison settings, so the tightness of the guarantees and the magnitude of the empirical advantage cannot be judged from the abstract. Proof details of the pinning decomposition, the concrete architecture of the weight-sharing network, and how tau-leaping step selection affects the guarantees remain to be confirmed in the full text.