EPS Dashboard

Authors: Mohsen Dehghankar, Abolfazl Asudeh

Summary

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.

Relevance

Tangential — this is an inference optimization for attention, not about fine-tuning or persona installation. If I ever care about deploying models with persona-specific behaviors efficiently at inference time, fast sparse attention might matter, but it doesn't touch my current research on how behaviors are installed or represented.

Abstract

arXiv:2605.06763v1 Announce Type: new Abstract: Sparse attention improves LLM inference efficiency by selecting a subset of key-value entries, but at the cost of potential accuracy degradation. In particular, omitting critical KV entries can induce substantial errors in model outputs. Existing methods typically operate under fixed or adaptive token budgets and provide empirical robustness or partial theoretical guarantees, yet they do not ensure zero false negatives in decoding steps, particularly since the set of relevant tokens is both query- and step-dependent. Our empirical observations confirm that missing even one critical key can lead to sharp error spikes, especially in long reasoning tasks where the set of important tokens varies throughout decoding. This observation motivates the need for indexing methods that dynamically adapt to these variations across decoding steps while guaranteeing a full recall of the relevant keys above a certain threshold. We address this challenge by reformulating sparse attention as the halfspace range searching problem. However, existing range searching indices are not suitable for modern LLM inference due to their computational and implementation overheads. To overcome this, we introduce Louver, a novel index structure tailored for efficient KV cache retrieval. Louver (i) guarantees zero false negatives with respect to a specified threshold in both theory and practice, (ii) is lightweight to integrate into existing LLM pipelines, and (iii) incorporates hardware-aware optimizations for both CPU and GPU executions. Our experiments demonstrate that Louver outperforms prior sparse attention methods in both accuracy and runtime, and is faster than highly optimized dense attentions such as FlashAttention. These results highlight that recall guarantees are a critical and overlooked dimension of sparse attention, and open a new direction for building theoretically grounded, efficient KV cache indices.