# Streaming Structured Inference with Flash-SemiCRF

arXiv: https://arxiv.org/abs/2604.18780 · HTML: https://mlsanity.com/paper/2604.18780/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 20 Apr 2026.

## Builds on (most cited first, 10 of 10)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [Neural Architectures for Named Entity Recognition](https://mlsanity.com/paper/1603.01360/) (2016)
- [End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF](https://mlsanity.com/paper/1603.01354/) (2016)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Segmental Recurrent Neural Networks](https://mlsanity.com/paper/1511.06018/) (2015)
- [Hybrid semi-Markov CRF for Neural Sequence Labeling](https://mlsanity.com/paper/1805.03838/) (2018)
- [Filtered Semi-Markov CRF](https://mlsanity.com/paper/2311.18028/) (2023)
- [Segment Boundary Detection via Class Entropy Measurements in Connectionist Phoneme Recognition](https://mlsanity.com/paper/2401.05717/) (2024)

## Abstract (arXiv)

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.