Certified Best-First Sparse Attention: Provable Early Termination via Admissible Block Bounds

Sparse attention makes long-context decoding affordable, but most methods silently discard KV blocks: they do not report how much attention mass was dropped. Fixed-budget selectors commit to a budget independently of the query, dynamic heuristics adapt but provide no bound, and probabilistic verifiers offer only high-probability guarantees at a fixed configuration budget. We recast sparse attention as best-first search with provable early termination. BNB-Attention reads KV blocks in decreasing order of an admissible upper bound on the attention scores inside each block, and stops once the unread blocks can contain at most an $\epsilon$ fraction of the attention mass accumulated so far. This yields a deterministic, per-query, per-head certificate bounding the output error relative to dense attention; in the worst case, the method falls back to dense attention. The practicality of the certificate hinges on bound tightness: on real activations, min/max and ball bounds are 22-24 nats loose, forcing near-dense visits, whereas per-block quantized bounds with explicit rounding radii are roughly $80\times$ tighter, making certified early termination viable. Across more than 19 million evaluations on seven checkpoints from four base model families, we observe zero certificate violations. At $\epsilon =10^{-2}$, BNB-Attention matches dense performance on RULER32K-HARD using only 3.1% KV density, remains within sampling noise of dense on AIME 2024 where certificate-free SnapKV collapses, and matches the strongest probabilistic verifier on its own LongBench protocol at roughly one-third the KV budget. It also achieves $\sim 2.7\times$ attention-kernel speedup over FlashAttention at 128K context under the quality-verified setting $\epsilon =10^{-2}$.