New COBS Attention Boosts LLM Long-Context Performance

Block sparse attention is a promising technique for improving the hardware efficiency of large language models (LLMs) by reducing the key-value (KV) cache read bottleneck. However, its adoption in leading open-weight LLMs has been limited, which often rely on dense attention or more fine-grained selection methods. This research analyzes DeepSeek's Native Sparse Attention (NSA) and identifies that the most critical and challenging aspect is block selection. The authors formalize this selection problem, reducing it to ranking blocks by their 'attention mass.' They demonstrate that if blocks with the largest attention mass are accurately retrieved, sparse attention can match the quality of dense attention. The core challenge lies in approximating this attention mass efficiently without reading all keys. To address this, the paper proposes COBS (Cumulant Order Block Sparse Attention), which builds upon NSA by incorporating a new selector that stores a compressed second-order statistic per block. On the 32k RULER long-context retrieval benchmark, COBS dramatically improved NSA's mean score from 0.2999 to 0.8195, nearing dense attention's 0.9040 and closing approximately 86% of the performance gap. Crucially, it achieved this while using only 1.21 times the KV cache read traffic of NSA and 15.15 times less than dense attention, all while preserving short-context behavior.