Streaming Structured Inference with Flash-SemiCRF

Flash-SemiCRF makes exact semi-Markov CRF inference tractable at genomic scale (T > 10⁵) by avoiding the O(TKC²) edge tensor - where T is sequence length, K is maximum segment duration, and C is the number of labels - and taking a streaming approach. Three ideas drive the implementation: (1) prefix-sum decomposition enables O(1)-per-edge evaluation from an O(TC) cumulative score array, so the full edge tensor is never stored; (2) ring-buffer streaming keeps forward-backward working memory at O(KC), independent of sequence length; and (3) sublinear gradient checkpointing at √(TK) intervals preserves exact gradients. A globally-centered emission baseline simultaneously controls numerical drift and induces an adaptive, data-dependent duration prior that regularizes segmentation under label imbalance. The system is implemented as a fused Triton kernel. On TIMIT phoneme segmentation, Flash-SemiCRF achieves a 25x training speedup and 178x inference speedup over pytorch-struct's linear scan, the only existing exact backend capable of running K=30 without OOM. We further prove that banded and block-sparse matrix formats cannot exploit the bounded segment length K in tree-structured formulations, as fill-in under composition drives intermediates to near-dense within O(log(T/K)) tree levels.