Approximate Structured Diffusion for Sequence Labelling

A new method for sequence labelling uses diffusion models to train conditional random fields on entire label sequences, overcoming a long-standing limitation of traditional linear-chain CRFs that rely on narrow decision spans. Sequence labelling — the task of assigning a label to each token in a sentence — is a foundational problem in natural language processing [1]. The standard machine-learning formulation casts it as a linear-chain conditional random field parameterized by a neural network [2]. While effective, this setup assumes a finite decision span, typically label bigrams, which restricts expressivity and degrades performance when long-range dependencies matter [3]. Researchers now propose bridging structured prediction and discrete diffusion to address that constraint [4]. The core idea is to condition the CRF not only on the input sentence but also on a noisy version of the entire label sequence, allowing the model to consider unbounded label interactions while still enforcing preferences on adjacent labels [5]. Structured prediction problems are notoriously complex because interrelations among predicted variables make exact inference computationally infeasible, forcing practitioners to rely on approximations [6]. Decoding with diffusion models requires iterative sampling to refine predictions from random noise. Sampling directly from a CRF distribution is costly — its complexity scales linearly with input size — and the limited parallelizability of the Viterbi algorithm makes training too slow [5]. The linear space complexity of exact methods also burdens memory consumption during training [3]. To make the approach practical, the authors approximate the CRF distribution with a Mean-Field method, finding the closest factorized distribution [4]. In experiments on part-of-speech tagging, the combination of a diffusion model with a CRF denoiser — or its Mean-Field approximation — delivered a 16.5% error reduction compared to baselines [1]. The model also scaled better than traditional CRFs, with both the unigram diffusion variant and the structured denoiser achieving superior performance [5]. Training is performed by maximizing a lower bound on the likelihood, with the denoiser synchronized to the diffusion model at each timestep [5]. The authors state that code will be made publicly available upon acceptance [3].