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
| CREATOR | Benjamin K. Johnson, Thomas Goralski, Ayush Semwal, Hui Shen, H. Josh Jang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100828 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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