The authors reframe sparse attention (selecting only a subset of key-value cache entries during LLM decoding) as a "halfspace range searching" problem from computational geometry, and build a new index called Louver that guarantees zero false negatives—every key above a threshold is retrieved—while being fast and lightweight. Louver is designed to handle the fact that the set of important tokens changes at every decoding step and for every query, which existing sparse attention methods don't guarantee.
Main takeaways:
- Sparse attention methods trade accuracy for speed, but missing even one critical key can cause sharp errors, especially in long reasoning tasks.
- The authors formulate KV cache retrieval as halfspace range searching, where you want all keys whose attention score exceeds a threshold.
- Louver is a new index structure that guarantees perfect recall (no false negatives) above a threshold, is easy to integrate into existing LLM pipelines, and has CPU/GPU-aware optimizations.
- Experiments show Louver is more accurate than prior sparse attention methods, faster than both sparse baselines and dense FlashAttention in many settings.