CertBlock: Certified Block Summaries for Budget-Constrained Long-Context Selection

Block-sparse attention serves a long context by committing a keep count per head and filling it with a selection rule, yet no step of that procedure bounds the attention mass the discarded blocks hold. Three challenges follow, each measured on 5 constructed workloads: an unobservable discarded mass, an unstable retained ordering as the workload is read, and incomparable per-head counts across differently concentrated heads. To address these challenges, we propose CertBlock, a block-sparse read-out that reports an upper bound on the mass it discards, comprising three components. Certified Block Summaries give every block a constant-size interval box and read from it an upper bound on the omitted softmax mass, carried as a certificate on the distance from dense attention. Certificate-Gated Selection admits and ranks blocks on that certified mass, a quantity that exists whether or not a block was selected. Global Budget Allocation spends one budget across heads and layers by the certified displacement each head incurs. The three components share one insight: the mass a truncated read-out omits can be bounded from a constant-size summary of each block, which turns the discarded portion into a computed term reported with every read-out. Because the rule computes its own certificate, a tolerance can refuse its selection. The certificate holds at all 1536 positions of each of two constructed workloads and at a sound rate of 1.000 on three held-out workloads under two attention geometries without retuning. At an identical committed block count, marginal allocation lowers the aggregated certified bound from 2.875 to 2.775 and from 4.921 to 4.852.