Approximate Structured Diffusion for Sequence Labelling

Nicolas Floquet; Joseph Le Roux; Nadi Tomeh

cs.CLJun 17, 2026

Approximate Structured Diffusion for Sequence Labelling

Authors: Nicolas Floquet, Joseph Le Roux, Nadi Tomeh

Organizations: Université Sorbonne Paris Nord, CNRS, Laboratoire d’Informatique de Paris Nord, LIPN, F-93430 Villetaneuse, France

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 (eg 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 a 16.5% error reduction for POS-tagging.

Explore similar work

Streaming Structured Inference with Flash-SemiCRF
Apr 20, 2026Benjamin K. Johnson, Thomas Goralski, Ayush Semwal +2Hidden Markov Models Flash
Dynamic Chunking for Diffusion Language Models
May 15, 2026Yichen Zhu, Xiaoming Shi, Peng Zhao +3Diffusion Language Models Chunk
DIRECT: Direct Decoding for Efficient and Aligned Sequence Labeling with Large Language Models
Jul 29, 2026Yilei Wang, Jiaxin Gan, Kexuan Zhang +3Sequence Modeling Direct Preference Optimization

Apr 20, 2026 · cs.LGJ/K move · Enter open · S save

Streaming Structured Inference with Flash-SemiCRF

Benjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen+1

Department of Epigenetics, Van Andel Institute, 333 Bostwick Ave. NE, Grand Rapids, 49503, MI, USA. · Department of Cell Biology, Van Andel Institute, 333 Bostwick Ave. NE, Grand Rapids, 49503, MI, USA.

Semi-Markov Conditional Random Fields (semi-CRFs) assign labels to segments of a sequence rather than to individual positions, enabling exact inference over segment-level features and principled uncertainty estimates at their boundaries. However, existing implementations must materialize a large edge potential tensor whose size grows with sequence length, maximum segment length, and label count, becoming prohibitive for speech-scale state spaces and intractable at genomic scales where sequences can exceed 100,000 positions. This memory bottleneck has limited the adoption of exact segment-level inference for long sequences and large label sets. We identify that the core inefficiency is materializing edge potentials that can instead be evaluated on-the-fly from a compact prefix-sum array, and make several improvements. First, replacing the stored edge tensor with prefix-sum lookup reduces the memory footprint by a factor proportional to the product of segment length and label count. Second, a streaming forward-backward pass with checkpoint-boundary normalization keeps working memory sublinear in sequence length while preserving exact gradients. Third, zero-centered cumulative scores control numerical drift and induce an adaptive duration prior under label imbalance. We integrate these ideas into Flash-SemiCRF, a fused Triton kernel that enables exact semi-CRF inference on previously intractable problem sizes. Available at https://github.com/biobenkj/flash-semicrf.

Hidden Markov Models Flash

Open paper Ask about it PDF

Abstract

Explore similar work

Streaming Structured Inference with Flash-SemiCRF

Dynamic Chunking for Diffusion Language Models

DIRECT: Direct Decoding for Efficient and Aligned Sequence Labeling with Large Language Models