Approximate Structured Diffusion for Sequence Labelling

# Approximate Structured Diffusion for Sequence Labelling
Source: [https://arxiv.org/html/2606.18856](https://arxiv.org/html/2606.18856)
Nicolas Floquet, Joseph Le Roux, Nadi Tomeh Université Sorbonne Paris Nord, CNRS, Laboratoire d’Informatique de Paris Nord, LIPN, F\-93430 Villetaneuse, France \{floquet, leroux, tomeh\}@lipn\.fr

###### Abstract

Sequence labelling, a core task of Natural Language Processing \(NLP\), consists in assigning each token of an input sentence a label\. From a Machine Learning point of view, sequence labelling is often cast as a Linear\-Chain Conditional Random Field \(CRF\) parametrised by a neural network\. While this approach gives good empirical results, CRFs assume a finite decision span \(*e\.g*\.label bigrams\) which can limit their expressivity and hurt performance when long\-range dependencies are required\.

We show we can leverage diffusion to train a CRF conditioned on an entire label sequence, with the caveat that the condition is on a*noisy*version of labels\. We show experimentally that this method, in conjunction with approximate CRF inference, improves label accuracy with a16\.5%16\.5\\%error reduction for POS\-tagging\.111C ode will be made available publicly upon acceptation\.

\\todostyle

jlrcolor=red,shadow

Approximate Structured Diffusion for Sequence Labelling

Nicolas Floquet, Joseph Le Roux, Nadi TomehUniversité Sorbonne Paris Nord, CNRS,Laboratoire d’Informatique de Paris Nord,LIPN, F\-93430 Villetaneuse, France\{floquet, leroux, tomeh\}@lipn\.fr

## 1Introduction

Sequence labelling, a fundamental task in NLP, consists in assigning a tag to each token of an input sentence\. It is the foundation of a variety of NLP applications, such as POS tagging, named\-entity recognition or parsing\. Modern approaches to this task are based on CRFs parametrised by neural networksLaffertyet al\.\([2001](https://arxiv.org/html/2606.18856#bib.bib13)\); Zhenget al\.\([2015](https://arxiv.org/html/2606.18856#bib.bib14)\)\. While structured models such as CRFs consider interactions between labels, tractability impose some restrictions\. Thus many proposed models are limited to bigrams,*i\.e*\.correlations of adjacent labels\.

Recently, diffusion has been applied to language modelling to effectively condition generation on unbounded contextsHoogeboomet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib2)\); Austinet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib3)\); Sahooet al\.\([2024](https://arxiv.org/html/2606.18856#bib.bib15)\)\. In practice, these models train denoisers to predict*independently*each token from noisy versions of the clean output\.

In this work, we bridge these two concepts,*i\.e*\.structured prediction and discrete diffusion, for sequence labelling\. We define a CRF conditioning the predicted label sequence not only on the input sentence but also on a noisy label sequence\. This helps the model consider unbounded label interactions while remaining able to enforce preferences on predicted adjacent labels\. Decoding with diffusion models requires iterative sampling to refine predictions from random noise\. Since sampling CRF distributions is costly, with a complexity linear in the input size, we speed up decoding and training by approximating them with Mean\-Field\.

We evaluate on POS tagging and show that this model scales up better than baseline CRFs, with both the unigram diffusion model and the addition of either a CRF denoiser or its Mean\-Field approximation achieving superior performance\.

## 2Model

### 2\.1Standard Sequence Labelling Model

Given a sentence𝒔=s1​…​sn\\bm\{s\}=s\_\{1\}\\dots s\_\{n\}, withsis\_\{i\}theithi^\{\\text\{th\}\}word, labelling produces a sequence𝒚=y1​…​yn\\bm\{y\}=y\_\{1\}\\dots y\_\{n\}, withyi∈ℒy\_\{i\}\\in\\mathcal\{L\}the label forsis\_\{i\}\. More precisely, sequence labelling models define a parametrised probability distributionpθ​\(𝒚\|𝒔\)p\_\{\\theta\}\(\\bm\{y\}\|\\bm\{s\}\)so labelling amounts to returning the mode𝒚^=argmax𝒚pθ​\(𝒚\|𝒔\)\\widehat\{\\bm\{y\}\}=\\operatorname\*\{argmax\}\_\{\\bm\{y\}\}p\_\{\\theta\}\(\\bm\{y\}\|\\bm\{s\}\)and learning parametersθ\\thetais cast as Maximum Likelihood Estimation\. These distributions are usually written as energy modelspθ​\(𝒚\|𝒔\)∝exp⁡f​\(𝒙,𝒚;θ\)p\_\{\\theta\}\(\\bm\{y\}\|\\bm\{s\}\)\\propto\\exp f\(\\bm\{x\},\\bm\{y\};\\theta\), computed by a neural network implementingff,*i\.e*\.parametersθ\\thetaare the parameters offf\. The decomposition offfover sequences is crucial for efficiency\.

Unigram Modelssum unary potential over the sequencef​\(𝒔,𝒚;θ\)=∑i=1nf​\(𝒔,yi;θ\)f\(\\bm\{s\},\\bm\{y\};\\theta\)=\\sum\_\{i=1\}^\{n\}f\(\\bm\{s\},y\_\{i\};\\theta\)\. Typically this is implemented as a TransformerVaswaniet al\.\([2017](https://arxiv.org/html/2606.18856#bib.bib17)\)whose output vector at positioniifeeds a MLP computingfffor all labels at this position\. As a consequence of the decomposition offf,pθp\_\{\\theta\}is factorized,*i\.e*\.pθ​\(𝒚\|𝒔\)=∏i=1npθ​\(yi\|𝒔\)p\_\{\\theta\}\(\\bm\{y\}\|\\bm\{s\}\)=\\prod\_\{i=1\}^\{n\}p\_\{\\theta\}\(y\_\{i\}\|\\bm\{s\}\)\. Labelling and training are efficient but the independence between predictions impairs the expressivity required to model fine\-grained label interactions\.

Bigram Modelssum unary and binary222These models can be extended tonn\-ary potentials\.potentials over adjacent positions,f​\(𝒔,𝒚;θ\)=∑i=1nf1​\(𝒔,yi;θ\)\+∑i=1n−1f2​\(𝒔,yi,yi\+1;θ\)f\(\\bm\{s\},\\bm\{y\};\\theta\)=\\sum\_\{i=1\}^\{n\}f\_\{1\}\(\\bm\{s\},y\_\{i\};\\theta\)\+\\sum\_\{i=1\}^\{n\-1\}f\_\{2\}\(\\bm\{s\},y\_\{i\},y\_\{i\+1\};\\theta\)\. Transformer output are fed tof1f\_\{1\}as in the unigram case\. Forf2f\_\{2\}, we need to compute a transition matrix for all labelsyi,yi\+1y\_\{i\},y\_\{i\+1\}\. This can be either implemented as a position\-independent matrix, or as a MLP computing at each position the transition weights fed by a Transformer’s output\. Labelling and training can be performed in linear time w\.r\.t\.sentence’s length, as can be computed marginal probabilities, with ViterbiForney \([1973](https://arxiv.org/html/2606.18856#bib.bib12)\)and Forward/BackwardRabiner \([1989](https://arxiv.org/html/2606.18856#bib.bib11)\)algorithms\. Bigram CRFs are difficult to parallelise but approximations such as Mean\-FieldWanget al\.\([2020](https://arxiv.org/html/2606.18856#bib.bib6)\)or Mean\-RegularisationCorroet al\.\([2025](https://arxiv.org/html/2606.18856#bib.bib10)\)recover the position\-wise independent computation, and thus the efficiency, of unigram models\.

### 2\.2Discrete Diffusion Models for Labelling

We follow diffusion language modelsHoogeboomet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib2)\); Austinet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib3)\)to define labelling as generation of labels given words\.

Forward Diffusion\.A sequence of tags𝒚0\\bm\{y\}^\{0\}is altered by a forward diffusion processqqconsisting ofTTsteps𝐲1​…​𝐲T\\mathbf\{y\}^\{1\}\\dots\\mathbf\{y\}^\{T\}to eventually obtain a random sequence333All sequences of size\|𝒚0\|\|\\bm\{y\}^\{0\}\|are equiprobable𝒚T\\bm\{y\}^\{T\}\. Generating such sequences is a Markovian processq​\(𝐲1​…​𝐲T\|𝐲0\)=∏t=1Tqt​\(𝐲t\|𝐲t−1\)q\(\\mathbf\{y\}^\{1\}\\dots\\mathbf\{y\}^\{T\}\|\\mathbf\{y\}^\{0\}\)=\\prod\_\{t=1\}^\{T\}q\_\{t\}\(\\mathbf\{y\}^\{t\}\|\\mathbf\{y\}^\{t\-1\}\)with independent noise at each positionii:qt​\(𝒚t\|𝒚t−1\)=∏i=1nqt​\(yit\|yit−1\)q\_\{t\}\(\\bm\{y\}^\{t\}\|\\bm\{y\}^\{t\-1\}\)=\\prod\_\{i=1\}^\{n\}q\_\{t\}\(y\_\{i\}^\{t\}\|y\_\{i\}^\{t\-1\}\)\.

Noise distributions are parametrised by a corruption ratioβt\\beta\_\{t\}following a predefined schedule:444We only consider cosineHoogeboomet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib2)\)\.

qt​\(yit\+1\|yit\)=\{βt\+1−βt\|ℒ\|​if​yit\+1=yit1−βt\|ℒ\|​otherwiseq\_\{t\}\(y\_\{i\}^\{t\+1\}\|y\_\{i\}^\{t\}\)=\\begin\{cases\}\\beta\_\{t\}\+\\frac\{1\-\\beta\_\{t\}\}\{\|\\mathcal\{L\}\|\}\\text\{ if \}y\_\{i\}^\{t\+1\}=y\_\{i\}^\{t\}\\\\ \\frac\{1\-\\beta\_\{t\}\}\{\|\\mathcal\{L\}\|\}\\text\{ otherwise\}\\end\{cases\}The parameters of these conditional distributionsqt\(⋅\|⋅\)q\_\{t\}\(\\cdot\|\\cdot\)for timestepttcan be encoded as a matrixQtQ\_\{t\}\. We can also precompute consecutive applications ofttdiffusion stepsq0\|t​\(yit\|yi0\)=∑yit−1qt​\(yit\|yit−1\)​q0\|t−1​\(yit−1\|yi0\)q\_\{0\|t\}\(y\_\{i\}^\{t\}\|y\_\{i\}^\{0\}\)=\\sum\_\{y\_\{i\}^\{t\-1\}\}q\_\{t\}\(y\_\{i\}^\{t\}\|y\_\{i\}^\{t\-1\}\)q\_\{0\|t\-1\}\(y\_\{i\}^\{t\-1\}\|y\_\{i\}^\{0\}\)\.

Denoising\.Our model, followingHoogeboomet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib2)\); Austinet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib3)\)for language models, produces a parameterised distribution on label sequences from a random sequence by reversing the diffusion process\. With a slight abuse of notation we also denote this distribution aspθp\_\{\\theta\}\. This model can assign a probability to less and less noisy sequences, also a markovian process :pθ​\(𝐲0​𝐲1​…​𝐲T\|𝒔\)=p​\(𝐲T\)​∏i=tTpθ​\(𝐲t−1\|𝐲t,𝐬\)p\_\{\\theta\}\(\\mathbf\{y\}^\{0\}\\mathbf\{y\}^\{1\}\\dots\\mathbf\{y\}^\{T\}\|\\bm\{s\}\)=p\(\\mathbf\{y\}^\{T\}\)\\prod\_\{i=t\}^\{T\}p\_\{\\theta\}\(\\mathbf\{y\}^\{t\-1\}\|\\mathbf\{y\}^\{t\},\\mathbf\{s\}\), where the priorp​\(𝒚T\)p\(\\bm\{y\}^\{T\}\)is the uniform distribution\. We drop the condition on𝒔\\bm\{s\}in notations\.

Denoiserpθp\_\{\\theta\}is implemented by a neural network presented in §[2\.3](https://arxiv.org/html/2606.18856#S2.SS3)\. The same network is used for alltt: to add time information, we feed the neural network with a learned representation oftt\. We follow the widely adopted architecture ofHoet al\.\([2020](https://arxiv.org/html/2606.18856#bib.bib4)\)and describe a single denoising step fromttas full denoising followed by\(t−1\)\(t\-1\)forward steps:

pθ​\(𝒚t−1\|𝒚t\)\\displaystyle p\_\{\\theta\}\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\}\)=∑y0pθ​\(𝒚0\|𝒚t\)​q​\(𝒚t−1\|𝒚t,𝒚0\)\\displaystyle=\\sum\_\{y^\{0\}\}p\_\{\\theta\}\(\\bm\{y\}^\{0\}\|\\bm\{y\}^\{t\}\)q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\bm\{y\}^\{0\}\)=𝔼𝒚0∼pθ\(⋅\|𝒚t\)​\[q​\(𝒚t−1\|𝒚t,𝒚0\)\]\\displaystyle=\\mathbb\{E\}\_\{\\bm\{y\}^\{0\}\\sim p\_\{\\theta\}\(\\cdot\|\\bm\{y\}^\{t\}\)\}\\big\[q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\bm\{y\}^\{0\}\)\\big\]≈q​\(𝒚t−1\|𝒚t,𝒚0^\)\\displaystyle\\approx q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\widehat\{\\bm\{y\}^\{0\}\}\)with​𝒚0^=𝔼𝒚0∼pθ\(⋅\|𝒚t\)​\[𝒚0\]\.\\displaystyle\\text\{ with \}\\widehat\{\\bm\{y\}^\{0\}\}=\\mathbb\{E\}\_\{\\bm\{y\}^\{0\}\\sim p\_\{\\theta\}\(\\cdot\|\\bm\{y\}^\{t\}\)\}\[\\bm\{y\}^\{0\}\]\.
A denoising step can thus be modelled as sampling from\(i\)\(i\)the so\-called posterior distribution with\(i​i\)\(ii\)the clean sequence𝒚0\\bm\{y\}\_\{0\}replaced by an expected sequence𝒚0^\\widehat\{\\bm\{y\}^\{0\}\}\. In practice, addressing\(i\)\(i\)requires computing the posterior distribution, expressed with three tractable distributions, from Bayes’ theorem and Markovian assumption :

q​\(𝒚t−1\|𝒚t,𝒚0\)\\displaystyle q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\bm\{y\}^\{0\}\)=q​\(𝒚t−1,𝒚t\|𝒚0\)q​\(𝒚t\|𝒚0\)\\displaystyle=\\frac\{q\(\\bm\{y\}^\{t\-1\},\\bm\{y\}^\{t\}\|\\bm\{y\}^\{0\}\)\}\{q\(\\bm\{y\}^\{t\}\|\\bm\{y\}^\{0\}\)\}=q​\(𝒚t\|𝒚t−1,𝒚0\)​q​\(𝒚t−1\|𝒚0\)q​\(𝒚t\|𝒚0\)\\displaystyle=\\frac\{q\(\\bm\{y\}^\{t\}\|\\bm\{y\}^\{t\-1\},\\bm\{y\}^\{0\}\)q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{0\}\)\}\{q\(\\bm\{y\}^\{t\}\|\\bm\{y\}^\{0\}\)\}=qt​\(𝒚t\|𝒚t−1\)​q​\(𝒚t−1\|𝒚0\)q​\(𝒚t\|𝒚0\)\.\\displaystyle=\\frac\{q\_\{t\}\(\\bm\{y\}^\{t\}\|\\bm\{y\}^\{t\-1\}\)q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{0\}\)\}\{q\(\\bm\{y\}^\{t\}\|\\bm\{y\}^\{0\}\)\}\.
While explanations above indicated that denoising is performed step by step fromtttot−1t\-1, we can rewrite it to perform several steps at once, fromtttot−kt\-k\. This may impact the quality of the generated sequence since the denoiser is called less, and has thus less opportunities to rely on the input sequence\. In our experiments we use a*halving*strategy and go from stepttto step⌊t2⌋\\lfloor\\frac\{t\}\{2\}\\rfloor, starting with stepTTuntil we reach0, so the number of calls to the denoiser is logarithmic in the number of diffusion steps\.

Structured DenoisingWe can adapt the previous decoding method to the case where the denoiserpθp\_\{\\theta\}is implemented by a CRF\. Remember that the denoiser’s role is to generate𝒚0^=𝔼𝒚0∼pθ\(⋅\|𝒚t\)​\[𝒚0\]\\widehat\{\\bm\{y\}^\{0\}\}=\\mathbb\{E\}\_\{\\bm\{y\}^\{0\}\\sim p\_\{\\theta\}\(\\cdot\|\\bm\{y\}^\{t\}\)\}\[\\bm\{y\}^\{0\}\]the fractional counts of each variable, given by the marginals probabilities of labels\. For linear\-chain CRFs we can compute marginals inO​\(n\)O\(n\)time complexity, either by running the forward\-backward algorithmRabiner \([1989](https://arxiv.org/html/2606.18856#bib.bib11)\)or backpropagating through the log\-partitionEisner \([2016](https://arxiv.org/html/2606.18856#bib.bib16)\)\. Unfortunately, this approach is intractable in our context because of the limited parallelisability of the Viterbi algorithm or its variants\. Moreover the denoiser must be called multiple times at decoding and the linear space complexity of these methods also burdens training with memory consumption\.

Instead, we can approximate the CRF distribution with Mean RegularisationCorroet al\.\([2025](https://arxiv.org/html/2606.18856#bib.bib10)\)or find the closest factorised distribution with Mean\-FieldWanget al\.\([2020](https://arxiv.org/html/2606.18856#bib.bib6)\)\. We experiment with the latter and show we can exploit structures with diffusion models while remaining efficient\.

Trainingis performed by maximizing likelihood with the denoiser synced to the diffusion model at each timestep\. More precisely we optimise a variational lower bound of the log\-likelihood :

log⁡pθ​\(𝒚0\)=log​∑y1…yT∼q\(⋅\|y0\)pθ​\(𝒚0,𝒚1,…,𝒚T\)\\displaystyle\\log p\_\{\\theta\}\(\\bm\{y\}^\{0\}\)=\\log\\sum\_\{y^\{1\}\\dots y^\{T\}\\sim q\(\\cdot\|y^\{0\}\)\}p\_\{\\theta\}\(\\bm\{y\}^\{0\},\\bm\{y\}^\{1\},\\dots,\\bm\{y\}^\{T\}\)≥𝔼𝒚1∼q0\|1\(⋅∣𝒚0\)\[log⁡pθ​\(𝒚0∣𝒚1\)\]\\displaystyle\\geq\\operatorname\*\{\\mathbb\{E\}\}\_\{\\bm\{y\}^\{1\}\\sim q\_\{0\|1\}\(\\cdot\\mid\\bm\{y\}^\{0\}\)\}\\Big\[\\log p\_\{\\theta\}\(\\bm\{y\}^\{0\}\\mid\\bm\{y\}^\{1\}\)\\Big\]−∑t=2T𝔼𝒚t∼q0\|t\(⋅∣𝒚0\)\[DKL​\(q​\(𝒚t−1∣𝒚t,𝒚0\)\|\|pθ\(𝒚t−1∣𝒚t\)\)\]\\displaystyle\\quad\-\\sum\_\{t=2\}^\{T\}\\;\\operatorname\*\{\\mathbb\{E\}\}\_\{\\bm\{y\}^\{t\}\\sim q\_\{0\|t\}\(\\cdot\\mid\\bm\{y\}^\{0\}\)\}\\left\[\\,D\_\{\\mathrm\{KL\}\}\\\!\\vbox\{\\hbox\{$\\left\(\\begin\{array\}\[\]\{@\{\}l@\{\}\}q\(\\bm\{y\}^\{t\-1\}\\mid\\bm\{y\}^\{t\},\\bm\{y\}^\{0\}\)\\\\\[2\.58334pt\] \|\|\\;p\_\{\\theta\}\(\\bm\{y\}^\{t\-1\}\\mid\\bm\{y\}^\{t\}\)\\end\{array\}\\right\)$\}\}\\,\\right\]−DKL​\(q0\|T​\(𝒚T∣𝒚0\)∥p​\(𝒚T\)\),\\displaystyle\\quad\-D\_\{\\mathrm\{KL\}\}\\Big\(q\_\{0\|T\}\(\\bm\{y\}^\{T\}\\mid\\bm\{y\}^\{0\}\)\\,\\big\\\|\\,p\(\\bm\{y\}^\{T\}\)\\Big\),whereDK​LD\_\{KL\}is the Kullback\-Liebler divergence between the two distributions\. The last term can be ignored since, by definition, the two distributions are uniform and their divergence is thus zero\. We train our model by uniformly sampling attbetween 1 andTT, and then a sequence𝒚t∼q0\|t\(⋅\|𝒚0\)\\bm\{y\}^\{t\}\\sim q\_\{0\|t\}\(\\cdot\|\\bm\{y\}^\{0\}\), which simulatesttdiffusion steps\. Ift=1t=1, we only consider the first term; sit≥2t\\geq 2we only consider the mean in the second term based on thistt, which brings us back to optimizing a single KL divergence\.

We notice that once sampled𝒚t\\bm\{y\}^\{t\}, the first term is just a log\-likelihood\. For the second term, we get:

DK​L\[q\(𝒚t−1\|𝒚t,𝒚0\)\|\|pθ\(𝒚t−1\|𝒚t\)\]\\displaystyle D\_\{KL\}\[q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\bm\{y\}^\{0\}\)\|\|p\_\{\\theta\}\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\}\)\]=\\displaystyle=DK​L\[q\(𝒚t−1\|𝒚t,𝒚0\)\|\|q\(𝒚t−1\|𝒚t,𝒚0^\)\]\+C,\\displaystyle D\_\{KL\}\[q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\bm\{y\}^\{0\}\)\|\|q\(\\bm\{y\}^\{t\-1\}\|\\bm\{y\}^\{t\},\\widehat\{\\bm\{y\}^\{0\}\}\)\]\+C,*i\.e*\.we seek to match posteriors conditioned on respectively gold sequences and the denoised ones\.

Finally, we add the denoising lossAustinet al\.\([2021](https://arxiv.org/html/2606.18856#bib.bib3)\),*i\.e*\.the negative log\-likelihood given by the denoiser to training instances, as it helps training stability and convergence\.

### 2\.3Neural Architecture

The neural architecture depicted in Fig\.[1](https://arxiv.org/html/2606.18856#S2.F1)implements potential functions,fffor unigrams orf1,f2f\_\{1\},f\_\{2\}for bigrams, as defined in §[2\.1](https://arxiv.org/html/2606.18856#S2.SS1), which are then summed to define probability distributions\. All models start converting wordss1,…,sns\_\{1\},\\dots,s\_\{n\}to non\-contextual representations with a look\-up table and a charLSTM\(Lampleet al\.,[2016](https://arxiv.org/html/2606.18856#bib.bib5)\)\. These are contextualized with TransformersVaswaniet al\.\([2017](https://arxiv.org/html/2606.18856#bib.bib17)\)to obtain vectorse1,…,ene\_\{1\},\\dots,e\_\{n\}\. Alternatively, pretrained embeddings can be used\. The unigram model is parametrised bynnvectorslil\_\{i\}of\|ℒ\|\|\\mathcal\{L\}\|scores computed by a MLP fromeie\_\{i\}\. The bigram models adds\|ℒ\|×\|ℒ\|\|\\mathcal\{L\}\|\\times\|\\mathcal\{L\}\|scores which represent label transitions from one position to the next\. These are computed for each position by a MLP\.

Our diffusion models implement the denoiser with Diffusion Transformer blocks\(Peebles and Xie,[2022](https://arxiv.org/html/2606.18856#bib.bib18)\)\. It takes as input a sequence of label embeddings from a trainable look\-up table corresponding to noisy labels and, as context for normalization, the concatenation of the contextual word embeddings and a trainable embedding of the timestep\. After these blocks a final MLP converts position vectors to unigram, and possibly bigram, scores\.

Diffusion TransformerLabel EmbeddingsyiT∈ℒy^\{T\}\_\{i\}\\\!\\in\\\!\\mathcal\{L\}…\\ldots…\\ldots𝒚T=\\bm\{y\}^\{T\}=∼𝖢𝖺𝗍​\(𝟣\|ℒ\|\)\\sim\\mathsf\{Cat\(\\frac\{1\}\{\|\\mathcal\{L\}\|\}\)\}×N\\times N𝒛i∈ℝk\\bm\{z\}\_\{i\}\\\!\\in\\\!\\mathbb\{R\}^\{k\}…\\ldots…\\ldotsUnary MLPPairwise MLP𝒍i∈ℝ\|ℒ\|\\bm\{l\}\_\{i\}\\\!\\in\\\!\\mathbb\{R\}^\{\|\\mathcal\{L\}\|\}𝑩ii\+1∈ℝ\|ℒ\|×\|ℒ\|\\bm\{B\}\_\{i\}^\{i\+\\\!1\}\\\!\\in\\\!\\mathbb\{R\}^\{\|\\mathcal\{L\}\|\\\!\\times\\\!\|\\mathcal\{L\}\|\}…\\ldots…\\ldotsCRF: Mean\-Field Marginal Approxyi0^=𝔼pθ\(⋅\|𝒚t\)​\[yi0\]∈\[0,1\]\|ℒ\|\\widehat\{y^\{0\}\_\{i\}\}\\\!=\\mathbb\{E\}\_\{p\_\{\\theta\}\(\\cdot\|\\bm\{y\}^\{t\}\)\}\\left\[y^\{0\}\_\{i\}\\right\]\\\!\\in\[0,\\\!1\]^\{\|\\mathcal\{L\}\|\}…\\ldots…\\ldots𝒚t−1∼q\(⋅\|𝒚t,𝒚0^\)\\bm\{y\}^\{t\-1\}\\sim q\(\\cdot\|\\bm\{y\}^\{t\},\\widehat\{\\bm\{y\}^\{0\}\}\)Sample a label sequenceT\. Emb\.t∈\[T\]t\\in\[T\]𝝉∈ℝg\\bm\{\\tau\}\\\!\\in\\\!\\mathbb\{R\}^\{g\}t=T,…,1t=T,\\ldots,1…\\ldots𝒄i∈ℝd\\bm\{c\}\_\{i\}\\\!\\in\\\!\\mathbb\{R\}^\{d\}…\\ldotsTransformer Encoder×M\\times MCharLSTM \+ Word Embeddingssi∈𝒱s\_\{i\}\\\!\\in\\\!\\mathcal\{V\}…\\ldots…\\ldotsInput𝒔=\\bm\{s\}=𝑪∈ℝd×n\\bm\{C\}\\in\\mathbb\{R\}^\{d\\times n\}Unary MLPPairwise MLP𝒍i∈ℝ\|ℒ\|\\bm\{l\}\_\{i\}\\\!\\in\\\!\\mathbb\{R\}^\{\|\\mathcal\{L\}\|\}𝑩ii\+1∈ℝ\|ℒ\|×\|ℒ\|\\bm\{B\}\_\{i\}^\{i\+\\\!1\}\\\!\\in\\\!\\mathbb\{R\}^\{\|\\mathcal\{L\}\|\\\!\\times\\\!\|\\mathcal\{L\}\|\}…\\ldots…\\ldotsCRF: Viterbiyi∈ℒy\_\{i\}\\\!\\in\\\!\\mathcal\{L\}…\\ldots…\\ldots𝒚^=argmax𝒚Pθ​\(𝒚\|𝒔\)\\bm\{\\hat\{y\}\}=\\operatorname\*\{argmax\}\_\{\\bm\{y\}\}P\_\{\\theta\}\(\\bm\{y\}\|\\bm\{s\}\)Baseline

Figure 1:From word embeddings, instead of directly predicting distribution parameters \(baseline, left\) we use them with timesteps as context for a diffusion transformer fed with sequences of noisy label embeddings \(ours, right\)\.

## 3Experiments

DataWe experiment on 4 datasets from Universal Dependencies v2\.15\([29](https://arxiv.org/html/2606.18856#bib.bib1)\)namely EN\-EWT, DE\-GSD, FR\-GSD, NL\-LassySmall for English, German, French, and Dutch\. We use standard splits, evaluate accuracy with punctuation and average results over 8 random seeds\.

We compare the 3 baseline models, unigram, Mean\-Field and CRF with our diffusion models, the unstructured and structured models, Diffusion\-Uni and Diffusion\-MF respectively\. Additionally, we report the best POS taggging results fromCorroet al\.\([2025](https://arxiv.org/html/2606.18856#bib.bib10)\)\. The hyper\-parameter setups for each model are described in[G](https://arxiv.org/html/2606.18856#A7), while additional results, with a different encoder, features and a baseline for Diff\-CRF \(the non approximated structured diffusion model\) in[C](https://arxiv.org/html/2606.18856#A3), an ablation study in[D](https://arxiv.org/html/2606.18856#A4), and the models’ speeds in[F](https://arxiv.org/html/2606.18856#A6)\.

Table 1:Test results for UD 2\.15\.Our results in Table[1](https://arxiv.org/html/2606.18856#S3.T1)show that structured diffusion improves performances in nearly all datasets, and get an average16\.54%16\.54\\%error reduction between the best model without diffusion \(CRF\) and the model with structured diffusion \(Diffusion\-MF\)\. We find that the diffusion approach allows models to scale better with more parameters, surpassing the 3 baseline with an equal parameter count, this is shown in Table[D](https://arxiv.org/html/2606.18856#A4)in Appendix\. Moreover in this setting, while the main source of performance increase is the use of diffusion, we can see that the additional structure given by the CRF \(Diffusion\-MF\) improves performance over the simple diffusion process \(Diffusion\-Uni\)\.

## 4Related Work

Structured discrete diffusion\.Discrete diffusion either corrupts labels directly\(Hoogeboomet al\.,[2021](https://arxiv.org/html/2606.18856#bib.bib2); Austinet al\.,[2021](https://arxiv.org/html/2606.18856#bib.bib3)\)or relaxes tokens for Gaussian diffusion and discretise at decode time\(*e\.g*\.Hoet al\.,[2020](https://arxiv.org/html/2606.18856#bib.bib4); Liet al\.,[2022](https://arxiv.org/html/2606.18856#bib.bib26); Peebles and Xie,[2022](https://arxiv.org/html/2606.18856#bib.bib18)\); related variants use iterative masking\(Changet al\.,[2022](https://arxiv.org/html/2606.18856#bib.bib29)\), bit encodings\(Chenet al\.,[2022](https://arxiv.org/html/2606.18856#bib.bib27)\), or VQ codebooks\(Guet al\.,[2021](https://arxiv.org/html/2606.18856#bib.bib28)\)\. For*structured*NLP, diffusion has been applied to span\-level NER\(Shenet al\.,[2023](https://arxiv.org/html/2606.18856#bib.bib19)\), token\-level labelling via bit\-relaxed sequences\(Huanget al\.,[2023](https://arxiv.org/html/2606.18856#bib.bib20)\), and non\-autoregressive constrained generation\(Gonget al\.,[2022](https://arxiv.org/html/2606.18856#bib.bib30)\); continuous\-time categorical formulations connect to jump processes and score matching\(Sunet al\.,[2023](https://arxiv.org/html/2606.18856#bib.bib48)\)\. Adjacent works insert CRFs around diffusion,*e\.g*\.*continuous*CRF for latent diffusion\(Ranasingheet al\.,[2024](https://arxiv.org/html/2606.18856#bib.bib49)\)or diffusion\-enhanced BiLSTM\-CRF for NER\(Qiuet al\.,[2025](https://arxiv.org/html/2606.18856#bib.bib50)\)\. Unlike previous works, we use a*CRF denoiser inside the loop*, yielding \(i\) guaranteed normalization, \(ii\) global context via the evolving noisy sequence, and \(iii\) parallelizable mean\-field updates\.

Structured prediction with neural CRFs\.Neural CRF models remain strong for labelling\(Laffertyet al\.,[2001](https://arxiv.org/html/2606.18856#bib.bib13)\); differentiable inference via unrolled mean\-field \(CRF\-as\-RNN\) and parallel accelerations improve efficiency\(Zhenget al\.,[2015](https://arxiv.org/html/2606.18856#bib.bib14); Wanget al\.,[2020](https://arxiv.org/html/2606.18856#bib.bib6); Corroet al\.,[2025](https://arxiv.org/html/2606.18856#bib.bib10)\), alongside amortized perspectives\(Stoyanov and Eisner,[2011](https://arxiv.org/html/2606.18856#bib.bib32); Domke,[2012](https://arxiv.org/html/2606.18856#bib.bib33); Hersheyet al\.,[2014](https://arxiv.org/html/2606.18856#bib.bib34)\)and classical variational analyses\(Wainwright and Jordan,[2008](https://arxiv.org/html/2606.18856#bib.bib35); Yedidiaet al\.,[2005](https://arxiv.org/html/2606.18856#bib.bib36); Murphyet al\.,[1999](https://arxiv.org/html/2606.18856#bib.bib37)\)\. Rather than single\-shot CRF decoding, we perform*repeated, globally informed*CRF diffusion\-driven updates, reconciling long\-range evidence with local constraints beyond purely accelerated CRF decoders\(Wanget al\.,[2020](https://arxiv.org/html/2606.18856#bib.bib6); Corroet al\.,[2025](https://arxiv.org/html/2606.18856#bib.bib10)\)\. Our model is then closer to\(Jayasumanaet al\.,[2024](https://arxiv.org/html/2606.18856#bib.bib51)\)but with the CRF inside a diffusion denoiser instead of generative Transformers\.

## 5Conclusion

We presented a novel approach to sequence labelling, with application to POS tagging, based on structured prediction and discrete diffusion to better predict tag distributions\. Our model improves the tagging metric and increases parameter scaling, surpassing the baseline and performing even better as the number of parameters grows while keeping a manageable time complexity thanks to the Mean\-Field approximation of the CRF distribution\. Our approach could also be applied in other tagging tasks in NLP, such as NER, or word segmentation\.

## Limitations

We showed that the presented method can scale,*i\.e*\.the more parameters the better accuracy is, as opposed to prior methods which tend to overfit when the number of parameters grow\. However, this increase come at the expense of memory consumption and compute time\. In other words, our models require more energy to be run at their full potential\.

In order to improve parallelization, we resort to the parallel version of Mean\-Field for which convergence is not guaranteed\. Although we didn’t see pathological divergence in practice, we note that the method recently developed byCorroet al\.\([2025](https://arxiv.org/html/2606.18856#bib.bib10)\)could be used as a drop\-in replacement for parallel Mean\-Field with convergence guarantees\.TODO: Change if we need B\-CRF for NER or POS\-tagging\.

## Ethical Considerations

We believe that our work does not raise ethical concerns\. We present a novel architecture for sequence labelling based on diffusion and structured prediction and we test it on standard, publicly available data\.

We acknowledge the environmental impact of the energy cost of training neural models\.

## References

- Structured denoising diffusion models in discrete state\-spaces\.InAdvances in Neural Information Processing Systems,M\. Ranzato, A\. Beygelzimer, Y\. Dauphin, P\.S\. Liang, and J\. W\. Vaughan \(Eds\.\),Vol\.34,pp\. 17981–17993\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2021/file/958c530554f78bcd8e97125b70e6973d-Paper.pdf)Cited by:[§1](https://arxiv.org/html/2606.18856#S1.p2.1),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p16.1),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p4.4),[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- H\. Chang, H\. Zhang, L\. Jiang, C\. Liu, and W\. T\. Freeman \(2022\)MaskGIT: masked generative image transformer\.2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 11305–11315\.External Links:[Link](https://api.semanticscholar.org/CorpusID:246680316)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- T\. Chen, R\. Zhang, and G\. E\. Hinton \(2022\)Analog bits: generating discrete data using diffusion models with self\-conditioning\.ArXivabs/2208\.04202\.External Links:[Link](https://api.semanticscholar.org/CorpusID:251402961)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- C\. Corro, M\. Lacroix, and J\. L\. Roux \(2025\)Bregman conditional random fields: sequence labeling with parallelizable inference algorithms\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 29557–29574\.External Links:[Link](https://aclanthology.org/2025.acl-long.1430/),ISBN 979\-8\-89176\-251\-0Cited by:[§2\.1](https://arxiv.org/html/2606.18856#S2.SS1.p3.4),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p11.1),[Table 1](https://arxiv.org/html/2606.18856#S3.T1.2.p2.1.1.1.1.2.2.1),[§3](https://arxiv.org/html/2606.18856#S3.p2.1),[§4](https://arxiv.org/html/2606.18856#S4.p2.1),[Limitations](https://arxiv.org/html/2606.18856#Sx1.p2.1)\.
- J\. Domke \(2012\)Generic methods for optimization\-based modeling\.InProceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics,N\. D\. Lawrence and M\. Girolami \(Eds\.\),Proceedings of Machine Learning Research, Vol\.22,La Palma, Canary Islands,pp\. 318–326\.External Links:[Link](https://proceedings.mlr.press/v22/domke12.html)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- J\. Eisner \(2016\)Inside\-outside and forward\-backward algorithms are just backprop \(tutorial paper\)\.InProceedings of the Workshop on Structured Prediction for NLP,Austin, TX,pp\. 1–17\.External Links:[Link](https://www.aclweb.org/anthology/W16-5901),[Document](https://dx.doi.org/10.18653/v1/W16-5901)Cited by:[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p10.3)\.
- G\. D\. Forney \(1973\)The Viterbi algorithm\.Proceedings of the IEEE61\(3\),pp\. 268–278\.External Links:[Document](https://dx.doi.org/10.1109/PROC.1973.9030)Cited by:[§2\.1](https://arxiv.org/html/2606.18856#S2.SS1.p3.4)\.
- S\. Gong, M\. Li, J\. Feng, Z\. Wu, and L\. Kong \(2022\)DiffuSeq: sequence to sequence text generation with diffusion models\.ArXivabs/2210\.08933\.External Links:[Link](https://api.semanticscholar.org/CorpusID:252917661)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- S\. Gu, D\. Chen, J\. Bao, F\. Wen, B\. Zhang, D\. Chen, L\. Yuan, and B\. Guo \(2021\)Vector quantized diffusion model for text\-to\-image synthesis\.2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 10686–10696\.External Links:[Link](https://api.semanticscholar.org/CorpusID:244714856)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- J\. R\. Hershey, J\. L\. Roux, and F\. Weninger \(2014\)Deep unfolding: model\-based inspiration of novel deep architectures\.ArXivabs/1409\.2574\.External Links:[Link](https://arxiv.org/abs/1409.2574)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- J\. Ho, A\. Jain, and P\. Abbeel \(2020\)Denoising diffusion probabilistic models\.InAdvances in Neural Information Processing Systems,H\. Larochelle, M\. Ranzato, R\. Hadsell, M\.F\. Balcan, and H\. Lin \(Eds\.\),Vol\.33,pp\. 6840–6851\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2020/file/4c5bcfec8584af0d967f1ab10179ca4b-Paper.pdf)Cited by:[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p5.5),[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- E\. Hoogeboom, D\. Nielsen, P\. Jaini, P\. Forré, and M\. Welling \(2021\)Argmax flows and multinomial diffusion: learning categorical distributions\.InAdvances in Neural Information Processing Systems,M\. Ranzato, A\. Beygelzimer, Y\. Dauphin, P\.S\. Liang, and J\. W\. Vaughan \(Eds\.\),Vol\.34,pp\. 12454–12465\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2021/file/67d96d458abdef21792e6d8e590244e7-Paper.pdf)Cited by:[§1](https://arxiv.org/html/2606.18856#S1.p2.1),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p4.4),[§4](https://arxiv.org/html/2606.18856#S4.p1.1),[footnote 4](https://arxiv.org/html/2606.18856#footnote4)\.
- Z\. Huang, P\. Cao, J\. Zhao, and K\. Liu \(2023\)DiffusionSL: sequence labeling via tag diffusion process\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,Note:To appearExternal Links:[Link](https://arxiv.org/abs/2309.08006)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- S\. Jayasumana, D\. Glasner, S\. Ramalingam, A\. Veit, A\. Chakrabarti, and S\. Kumar \(2024\)MarkovGen: structured prediction for efficient text\-to\-image generation\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 9316–9325\.Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- J\. D\. Lafferty, A\. McCallum, and F\. C\. N\. Pereira \(2001\)Conditional random fields: probabilistic models for segmenting and labeling sequence data\.InProceedings of the Eighteenth International Conference on Machine Learning \(ICML 2001\), Williams College, Williamstown, MA, USA, June 28 \- July 1, 2001,C\. E\. Brodley and A\. P\. Danyluk \(Eds\.\),pp\. 282–289\.Cited by:[§1](https://arxiv.org/html/2606.18856#S1.p1.1),[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- G\. Lample, M\. Ballesteros, S\. Subramanian, K\. Kawakami, and C\. Dyer \(2016\)Neural architectures for named entity recognition\.InProceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,K\. Knight, A\. Nenkova, and O\. Rambow \(Eds\.\),San Diego, California,pp\. 260–270\.External Links:[Link](https://aclanthology.org/N16-1030/),[Document](https://dx.doi.org/10.18653/v1/N16-1030)Cited by:[§2\.3](https://arxiv.org/html/2606.18856#S2.SS3.p1.9)\.
- X\. L\. Li, J\. Thickstun, I\. Gulrajani, P\. Liang, and T\. Hashimoto \(2022\)Diffusion\-lm improves controllable text generation\.ArXivabs/2205\.14217\.External Links:[Link](https://api.semanticscholar.org/CorpusID:249192356)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- Y\. Liu, M\. Ott, N\. Goyal, J\. Du, M\. Joshi, D\. Chen, O\. Levy, M\. Lewis, L\. Zettlemoyer, and V\. Stoyanov \(2019\)RoBERTa: A robustly optimized BERT pretraining approach\.CoRRabs/1907\.11692\.External Links:[Link](http://arxiv.org/abs/1907.11692),1907\.11692Cited by:[Appendix C](https://arxiv.org/html/2606.18856#A3.p2.1)\.
- K\. P\. Murphy, Y\. Weiss, and M\. I\. Jordan \(1999\)Loopy belief propagation for approximate inference: an empirical study\.InProceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence,pp\. 467–475\.Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- W\. Peebles and S\. Xie \(2022\)Scalable diffusion models with transformers\.arXiv preprint arXiv:2212\.09748\.External Links:[Link](https://arxiv.org/abs/2212.09748)Cited by:[§2\.3](https://arxiv.org/html/2606.18856#S2.SS3.p2.1),[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- J\. Pennington, R\. Socher, and C\. D\. Manning \(2014\)GloVe: global vectors for word representation\.InEmpirical Methods in Natural Language Processing \(EMNLP\),pp\. 1532–1543\.External Links:[Link](http://www.aclweb.org/anthology/D14-1162)Cited by:[Appendix C](https://arxiv.org/html/2606.18856#A3.p1.1)\.
- Y\. Qiu, L\. Dong, W\. Zhang, H\. Xing, and J\. Huang \(2025\)A diffusion enhanced crf and bilstm framework for accurate entity recognition\.Scientific Reports15,pp\. 19670\.External Links:[Document](https://dx.doi.org/10.1038/s41598-025-04036-x)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- L\. R\. Rabiner \(1989\)A tutorial on hidden Markov models and selected applications in speech recognition\.Proceedings of the IEEE77\(2\),pp\. 257–285\.Cited by:[§2\.1](https://arxiv.org/html/2606.18856#S2.SS1.p3.4),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p10.3)\.
- K\. Ranasinghe, S\. Jayasumana, A\. Veit, A\. Chakrabarti, D\. Glasner, M\. S\. Ryoo, S\. Ramalingam, and S\. Kumar \(2024\)LatentCRF: continuous crf for efficient latent diffusion\.External Links:2412\.18596,[Link](https://arxiv.org/abs/2412.18596)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- S\. S\. Sahoo, M\. Arriola, A\. Gokaslan, E\. M\. Marroquin, A\. M\. Rush, Y\. Schiff, J\. T\. Chiu, and V\. Kuleshov \(2024\)Simple and effective masked diffusion language models\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=L4uaAR4ArM)Cited by:[§1](https://arxiv.org/html/2606.18856#S1.p2.1)\.
- Y\. Shen, K\. Song, X\. Tan, D\. Li, W\. Lu, and Y\. Zhuang \(2023\)DiffusionNER: boundary diffusion for named entity recognition\.InProceedings of the 61st Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 3875–3890\.External Links:[Link](https://aclanthology.org/2023.acl-long.214)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- V\. Stoyanov and J\. Eisner \(2011\)Learning cost\-aware, loss\-aware approximate inference policies for probabilistic graphical models\.InNIPS Workshop on Structured Prediction and Approximate Inference,Note:Workshop on Advances in Structured PredictionExternal Links:[Link](https://www.cs.jhu.edu/%CB%9Cjason/)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- H\. Sun, L\. Yu, B\. Dai, D\. Schuurmans, and H\. Dai \(2023\)Score\-based continuous\-time discrete diffusion models\.InThe Eleventh International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=BYWWwSY2G5s)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p1.1)\.
- \[29\]Universal dependencies 2\.15\.Cited by:[§3](https://arxiv.org/html/2606.18856#S3.p1.1)\.
- A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin \(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,I\. Guyon, U\. V\. Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett \(Eds\.\),Vol\.30\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf)Cited by:[§2\.1](https://arxiv.org/html/2606.18856#S2.SS1.p2.6),[§2\.3](https://arxiv.org/html/2606.18856#S2.SS3.p1.9)\.
- M\. J\. Wainwright and M\. I\. Jordan \(2008\)Graphical models, exponential families, and variational inference\.Foundations and Trends in Machine Learning1\(1–2\),pp\. 1–305\.External Links:[Document](https://dx.doi.org/10.1561/2200000001)Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- X\. Wang, Y\. Jiang, N\. Bach, T\. Wang, Z\. Huang, F\. Huang, and K\. Tu \(2020\)AIN: fast and accurate sequence labeling with approximate inference network\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),B\. Webber, T\. Cohn, Y\. He, and Y\. Liu \(Eds\.\),Online,pp\. 6019–6026\.External Links:[Link](https://aclanthology.org/2020.emnlp-main.485/),[Document](https://dx.doi.org/10.18653/v1/2020.emnlp-main.485)Cited by:[§2\.1](https://arxiv.org/html/2606.18856#S2.SS1.p3.4),[§2\.2](https://arxiv.org/html/2606.18856#S2.SS2.p11.1),[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- J\. S\. Yedidia, W\. T\. Freeman, and Y\. Weiss \(2005\)Constructing free\-energy approximations and generalized belief propagation algorithms\.IEEE Transactions on Information Theory51\(7\),pp\. 2282–2312\.Cited by:[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.
- S\. Zheng, S\. Jayasumana, B\. Romera\-Paredes, V\. Vineet, Z\. Su, D\. Du, C\. Huang, and P\. Torr \(2015\)Conditional random fields as recurrent neural networks\.InInternational Conference on Computer Vision \(ICCV\),Cited by:[§1](https://arxiv.org/html/2606.18856#S1.p1.1),[§4](https://arxiv.org/html/2606.18856#S4.p2.1)\.

## Appendix ANER results

Table 2:NER Results for CoNLL, \.
## Appendix BDecoding Algorithms

Algorithm[1](https://arxiv.org/html/2606.18856#alg1)describes the unbatched version of the decoding process with timesteps halved at each round\. It relies on five subroutines:

1. 1\.samplesamples independently at each position of the input sentence according to its input categorical distribution;
2. 2\.tag\-embedandtime\-embedembed discrete values \(resp\. POS labels and timesteps\) to their dense representations\. They are implemented as look\-up tables;
3. 3\.denoise\-marginalscalls the denoiser on the input sentencexxfrom a noisy predictiony~\\widetilde\{y\}and compute marginal distributions of all labels at each positions\. For unstructured diffusion or Mean\-Field, we simply return the softmaxed logits return by the neural network implementing the denoiser\. For structured diffusion we use the forward/backward algorithm\.
4. 4\.posteriorcomputes the posterior distribution from marginalsppbetween timestepsttandt′t^\{\\prime\}\.

The algorithms starts by sampling labels from the uniform distribution\. Then at each relevant timestep, it performs the following operations\. First the previously predicted labels, as well as the current timesteptt, are embedded\. Then the denoiser is called to predict a new sequence of marginal label distributions\. Finally, we use the posterior distribution to sample labels at timestept′=⌊t2⌋t^\{\\prime\}=\\left\\lfloor\\frac\{t\}\{2\}\\right\\rfloor\. These steps are repeated recursively for timestept′t^\{\\prime\}, until we reach timestep 1\.

1

Input:

x∈ℝN×Dx\\in\\mathbb\{R\}^\{N\\times D\}: Token embeddings

Output:

y^∈𝕃N\\widehat\{y\}\\in\\mathbb\{L\}^\{N\}: Predicted tags

2

3

t←1024t\\leftarrow 1024
4

yt←sample\(Cat\(1L𝟏N\)\)y\_\{t\}\\leftarrow\\text\{sample\(Cat\}\(\\frac\{1\}\{L\}\\bm\{1\}\_\{N\}\)\)
5while*t\>1t\>1*do

6

y~←tag\-embed​\(yt\)\\widetilde\{y\}\\leftarrow\\text\{tag\-embed\}\(y\_\{t\}\)
7

t~←time\-embed​\(t\)\\widetilde\{t\}\\leftarrow\\text\{time\-embed\}\(t\)
8

p←denoise\-marginals​\(x,y~,t~\)p\\leftarrow\\text\{denoise\-marginals\}\(x,\\widetilde\{y\},\\widetilde\{t\}\)
9

t′←⌊t2⌋t^\{\\prime\}\\leftarrow\\left\\lfloor\\frac\{t\}\{2\}\\right\\rfloor
10

yt←sample\(posterior\(t′,t,p\)\)y\_\{t\}\\leftarrow\\text\{sample\(posterior\}\(t^\{\\prime\},t,p\)\)
11

t←t′t\\leftarrow t^\{\\prime\}
12

13

y^←y1\\hat\{y\}\\leftarrow y\_\{1\}
14return

y^\\hat\{y\}

Algorithm 1Diffusion Decoding for Sequence Labelling
## Appendix CAdditional Results

In Table[3](https://arxiv.org/html/2606.18856#A3.T3), we report the results obtained using the GloVe pretrained embeddings\(Penningtonet al\.,[2014](https://arxiv.org/html/2606.18856#bib.bib53)\), which strengthen the validity of our approach, even when using more advanced pretrained features\.

Table 3:Comparison of the scores for all models using a transformer encoder, with or withoutGloVeembeddings in English using UD 2\.15 \(EN\-EWT\)\.In Tables[4](https://arxiv.org/html/2606.18856#A3.T4)and[5](https://arxiv.org/html/2606.18856#A3.T5), we compare the best baseline setups for the unigram, mean\-field and CRF taggers, to theLandXLversions of our models \(see[G](https://arxiv.org/html/2606.18856#A7)\) respectively using either a transformer as an encoder, or a pre\-trained multilingual transformer model, RoBerta\-Large\(Liuet al\.,[2019](https://arxiv.org/html/2606.18856#bib.bib52)\)\. Note that due to training time constraints, we only trained Diffusion\-CRF, our structured diffusion model which doesn’t use the mean\-field approximation using RoBerta\-Large as an encoder\. Model sizes are described in[G](https://arxiv.org/html/2606.18856#A7), while a global view of the scaling, or lack thereof for each model is presented in[D](https://arxiv.org/html/2606.18856#A4)\. The 2 tables show that both structured and unstructured diffusion work well, however, we acknowledge that the*bitter lesson*applies here, where with an the increased parameter count of theXLmodel, as well as with the enriched word embeddings with RoBerta\-Large, the unstructured model manages to catch up to Diff\-MF\.

Table 4:Results for UD 2\.15, average of 8 experiments using the best configurations for all 3 baseline models, and theLconfiguration for diffusion models\)\.Table 5:Results for UD 2\.15, average of 8 experiments using the best configurations for all 3 baseline models, and theXLconfiguration for diffusion models\)\.
## Appendix DAblation Studies

We find that the diffusion approach allows models to scale better with more parameters, surpassing the 3 baseline models when using a low parameter setup, but also getting increasingly better results as the parameter count increases, while the baseline models show no such improvements passed a very low ceiling after which performance actually decreases\. Given that the baseline models consist principally of an encoder and a scoring MLP, we only tested their scaling when using a transformer as an encoder, whereas with the diffusion models, the encoder’s size remains the same, but the parameters allotted to the diffusion and denoising processes vary, this is further explained in[G](https://arxiv.org/html/2606.18856#A7)\. The principal limit of our scaling, to our knowledge is the limited memory in the GPUs we used\.

ModelsModel sizeXSSMLXLTransformerUnigram91\.1791\.3691\.1690\.87N/AMF93\.1792\.9692\.7992\.63N/ACRF93\.8493\.5893\.5593\.47N/ADiffusion\-UniN/A94\.0494\.3394\.4794\.83Diffusion\-MFN/A94\.4594\.6794\.7294\.97RoBerta\-LargeUnigram98\.33N/AMF98\.20N/ACRF98\.22N/ADiffusion\-UniN/A98\.3798\.4098\.4298\.49Diffusion\-CRFN/AN/AN/A98\.4498\.40Diffusion\-MFN/A98\.4498\.4898\.4798\.49

Table 6:Dev scores with varying model sizes in English using UD 2\.15 \(EN\-EWT\)\.Another test we did was to use different mean\-field iterations, which led to increasing though diminishing gains until 10 iterations for the baseline mean\-field model, and 15 iterations for Diff\-MF\. The effect of different numbers of iterations on speed is shown in[F](https://arxiv.org/html/2606.18856#A6)\.

## Appendix EDiffusion Tuning

Table 7:Comparison of dev scores for the base and structured diffusion models with varying diffusion layer counts on UD2\.15 \(EN\-EWT\) using a transformer encoder and theExtra\-Largemodel size\.We tested different numbers of layers for the diffusion transformer and settled on 8, which yields high results in all tested datasets while having a memory footprint small enough to ensure that both the training and evaluation can be carried out with no errors\. As can be seen in[7](https://arxiv.org/html/2606.18856#A5.T7), the unstructured model keeps getting better results with added layers, and more parameters\.

## Appendix FTiming Experiments

In this section we notice in that a high number of mean\-field iterations as well as the diffusion itself both have a non negligible effect on speed in Table[8](https://arxiv.org/html/2606.18856#A6.T8), however it is worth noting that the slowest training speeds we obtained forDiff\-MFwere about equivalent with the speed of theCRFmodel\. Where our structured approach does slow down is in the evaluation, due to our decoding needing to perform the denoising process multiple times\.Diff\-CRFin particular is prohibitively slow, further validating our approximation approach with mean\-fields\. Similarly, our diffusion models do slow down considerably the more layers we use, as shown in[9](https://arxiv.org/html/2606.18856#A6.T9)\.

Table 8:Training and evaluation speeds with different numbers of mean\-field iterations on MF and Diff\-MF for UD 2\.15 \(EN\-EWT\)\.Table 9:Training and evaluation speeds for the base and structured diffusion models with varying diffusion layer counts for UD 2\.15 \(EN\-EWT\)\.\.ModelsModel sizeXSSMLXLTransformerUnigram1129999750640N/AMF738664552486N/ACRF361345313283N/ADiffusion\-UniN/A449455399287Diffusion\-MFN/A343344322242RoBerta\-LargeUnigram210N/AMF191N/ACRF152N/ADiffusion\-UniN/A156155155129Diffusion\-CRFN/AXX7166Diffusion\-MFN/A140140141119

Table 10:Training speeds with varying model sizes in English using UD 2\.15 \(EN\-EWT\)\.ModelsModel sizeXSSMLXLTransformerUnigram4258379831782711XMF3254303027402469XCRF574559550530XDiffusion\-UniX167167152175Diffusion\-MFX122131127136RoBerta\-LargeUnigram754N/AMF710N/ACRF358N/ADiffusion\-UniX142141142145Diffusion\-CRFXXX3840Diffusion\-MFX112113113118

Table 11:Evaluation speeds with varying model sizes in English using UD 2\.15 \(EN\-EWT\)\.
## Appendix GHyperparameters

We categorize our models into 5 different size configurations, based on the parameter count they have for the main baseline,XS,S,M,L,XL, corresponding to roughly 20, 40, 60, 80 and 650 million parameters respectively\. 20 million parameters are allotted to the transformer encoder, for the baseline models,unigram,mean\-field,CRF, the encoder is given more parameters to reach the bigger configurations, as the encoder is all these models have, save for a scoring MLP\. For the diffusion models, the encoder does not change in size, but we change the size of the diffusion transformer used, thus in theMconfiguration for example, the non diffusion models have 60 million parameters allocated to their encoder, while the diffusion models have 20 million for the encoder, and 40 million for the diffusion transformer\. We thus cannot have aXSdiffusion baseline, as it would have 0 parameters for the diffusion, and we also decided not to test out theXLbaselines for the non diffusion models, as none of them showed potential to perform any better than in the smaller baselines\. All models use no dropout for their scoring MLP\. Below is a few list of vector sizes, layer counts and the formula which gives the parameter count of the models\.