HATS: Efficient Threshold-based Sparse Attention via History-Guided Block Traversal

Long-context decoding is bottlenecked by repeated access to an ever-growing KV cache. While sparse attention can skip insignificant KV blocks, inexpensive history-based selection is query-agnostic, whereas query-aware selection incurs additional computational overhead. An alternative is to make skip decisions during KV-block traversal, where a threshold determines whether to skip value-side computation right after computing a block's attention score. However, we observe that the achieved sparsity depends not only on the threshold but also on the traversal order: visiting low-scoring blocks before high-scoring ones can retain blocks that would otherwise be skipped, creating a traversal-induced sparsity gap. To close this gap, we propose HATS (History-guided Attention with Thresholded Skipping). HATS uses blocks that scored highly at the previous decoding step to guide traversal for the current token, thereby increasing the likelihood of visiting high-scoring blocks as early as possible. History only guides the order of block traversal, while value skipping remains determined by the newly computed current token score and a preset threshold. We prove that, for a given current token and fixed threshold, visiting the globally highest-scoring block first maximizes the attainable sparsity, thereby defining an oracle upper bound on sparsity over the set of all traversal orders. Experiments show that HATS closes 98.6–99.5% of the sparsity gap to the oracle, delivering a 1.98$\times$ speedup for the decode-attention kernel at 92.4% sparsity and a 1.26$\times$ decode-throughput speedup at 88.2% sparsity.