Streaming Structured Inference with Flash-SemiCRF

Benjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen, H. Josh Jang · 2026

Read Streaming Structured Inference with Flash-SemiCRF by Benjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen, H. Josh Jang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18780.txt.

Introduction

Johnson and four colleagues present Flash-SemiCRF, a fused kernel for exact semi Markov conditional random field inference on large problems. Semi CRFs label segments of a sequence, not individual positions, but existing implementations must store an edge tensor that grows with length, segment length, and label count. Flash-SemiCRF replaces the stored tensor with prefix sum lookup, uses a streaming forward backward pass with checkpoint normalization, and controls drift with zero centered cumulative scores. Working memory stays sublinear while exact gradients are preserved.

Catalog record

CREATORBenjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen, H. Josh Jang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100828
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18780

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Streaming Structured Inference with Flash-SemiCRF Benjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen, H. Josh Jang Abstract 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 . keywords Semi-CRF · Structured prediction · Genomic segmentation · GPU inference · Triton † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. 1 Introduction Many sequence types are naturally segmented and prediction tasks need to go beyond per-position labels. Modern neural encoders learn rich cross-position dependencies, but their output layers remain per-position: the loss decomposes over individual positions, no constraint enforces that adjacent predictions form a valid segmentation, segment duration is never explicitly modeled, and there is no direct mechanism to obtain posterior marginals over segment boundaries or segment identities. Semi-Markov conditional random fields (semi-CRFs) Sarawagi and Cohen 2004 formalizes discriminative segment-level prediction by scoring variable-length segments via content, duration, and transition potentials. This factorization provides three structural properties that per-position classifiers lack, such as: every position belongs to exactly one labeled segment, explicit duration modeling that captures label-dependent length distributions, and segment-level posterior marginals that quantify uncertainty over boundaries rather than individual positions. The integration of CRFs as neural network output layers Lample et al. 2016 ; Ma and Hovy 2016 ; Kong et al. 2016 ; Ye and Ling 2018 demonstrated that structured inference and representation learning are complementary, with the CRF layer enforcing global coherence over the encoder’s learned representations. Rush Rush 2020 provided a general-purpose semi-CRF implementation ( pytorch-struct ), making the algorithm widely accessible as a training and inference layer but remaining bound by the edge tensor at scale. Semi-CRF inference requires materializing a dense edge tensor of size O(TKC^{2}) ( T positions, K maximum segment duration, C labels), dominating both time and memory. For NLP tasks with T in the tens to hundreds and small K , this cost is manageable. At genomic scales, modern CRF-based tools have primarily adopted the per-position linear ( K{=}1 ) case that avoids this edge tensor and the associated time and memory costs of a standard semi-CRF: Bonito Oxford Nanopore Technologies 2020 and Dorado Oxford Nanopore Technologies 2024 decode raw nanopore signal, and Tranquillyzer Semwal et al. 2025 annotates long-read RNA-seq, all at sequence lengths routinely exceeding 10^{5} . Earlier semi-CRF applications to gene prediction – CONRAD DeCaprio et al. 2007 and CRAIG Bernal et al. 2007 – relied on hand-crafted features and CPU-bound Viterbi decode rather than serving as differentiable layers under neural encoder training. Extending to the semi-Markov setting multiplies the per-position cost by K ; at genomic scales ( K\geq 10^{3} ), materializing the full edge tensor becomes infeasible on GPU long before the sequential sweep over T becomes the bottleneck. Recent work from Zaratiana et al. Zaratiana et al. 2023 addresses this problem through pruning. Their Filtered Semi-CRF uses a local span classifier to discard irrelevant segments before running structured inference on the reduced graph. This exploits the sparsity of named entities in text, where most spans are non-entities. In contrast, for dense segmentation problems where every position belongs to a labeled segment such as those in genomics, the sparsity assumption does not typically hold and the full semi-CRF graph must be traversed. FlashAttention Dao et al. 2022 demonstrated that for attention, the dominant cost is not arithmetic but memory access: by never materializing the n\times n attention matrix and instead recomputing blocks on-chip, it achieves large wall-clock speedups despite higher FLOP counts. We apply the same IO-aware principle to semi-CRF inference. The standard implementation pre-computes and stores the full O(TKC^{2}) edge tensor in HBM, then runs forward-backward over the stored result. At scale, this tensor dominates memory. We observe that when segment content scores decompose as sums over positions Sarawagi and Cohen 2004 , prefix sums reduce per-edge evaluation to O(1) , and the edge tensor need never be materialized. Each potential can instead be computed on-the-fly within a streaming dynamic programming (DP) kernel from an O(TC) cumulative score array. We present Flash-SemiCRF , a Triton-accelerated semi-CRF library built on this observation. The key ideas are: 1. On-the-fly edge computation. A prefix-sum decomposition of segment content scores enables O(1) -in-duration edge potential evaluation, reducing inference from memory-bound to compute-bound and dispensing with the O(TKC^{2}) edge tensor entirely. 2. Ring-buffer streaming. The forward-backward algorithm operates through K -slot and 2K -slot ring buffers for the forward and backward passes respectively, achieving O(KC) working memory independent of sequence length T . 3. Sublinear checkpointing. Gradient checkpointing at \sqrt{TK} intervals, following the recomputation paradigm of FlashAttention Dao et al. 2022 and the chunked scan of Mamba Gu and Dao 2024 , yields O(\sqrt{T/K}\cdot KC) checkpoint memory that grows sublinearly in T . 4. Globally-centered emissions. A sequence-level baseline subtraction simultaneously stabilizes prefix sums at large T and induces an adaptive, data-dependent duration prior that regularizes segmentation under label imbalance. We validate correctness through training convergence criteria, finite-difference gradient checks, and self-consistency between independent forward-backward implementations. We benchmark against pytorch-struct Rush 2020 and demonstrate that sparse or banded matrix representations are incompatible with semi-CRF inference due to the triangular, rather than diagonal, sparsity structure of the intermediate operators. We characterize the transition from memory-bound to compute-bound scaling as a function of T , K , and C . Flash-SemiCRF provides a structured decoding approach that can be applied to learned representations to produce segmentations that respect duration constraints and maintain segment-level coherence, properties that per-position classifiers typically discard. 2 Terminological clarification A linear CRF (or linear-chain CRF) is a model in which every segment has duration one (K=1), so inference reduces to the standard per-position Viterbi/forward–backward recurrence. A linear scan is an algorithm that implements the semi-CRF dynamic program by sweeping left-to-right over positions, as opposed to tree-structured (parallel-scan) alternatives. The two are orthogonal: a linear scan can execute semi-CRF inference at both K=1 and K\geq 1 , and a linear CRF can in principle be computed by any backend. Throughout this paper, “linear CRF” refers to the K=1 model, while “linear scan” refers to the sequential sweep algorithm. 3 Implementation

Read the complete text