Prism: Spectral-Aware Block-Sparse Attention

Block-sparse attention is promising for accelerating long-context LLM pre-filling, yet identifying relevant blocks efficiently remains a bottleneck. Existing methods typically employ coarse-grained attention as a proxy for block importance estimation, but often resort to expensive token-level searching or scoring, resulting in significant selection overhead. In this work, we trace the inaccuracy of standard coarse-grained attention via mean pooling to a theoretical root cause: the interaction between mean pooling and Rotary Positional Embeddings (RoPE). We prove that mean pooling acts as a low-pass filter that induces destructive interference in high-frequency dimensions, effectively creating a "blind spot" for local positional information (e.g., slash patterns). To address this, we introduce Prism, a training-free spectral-aware approach that decomposes block selection into high-frequency and low-frequency branches. By applying energy-based temperature calibration, Prism restores the attenuated positional signals directly from pooled representations, enabling block importance estimation using purely block-level operations, thereby improving efficiency. Extensive evaluations confirm that Prism maintains accuracy parity with full attention while delivering up to $\mathbf{5.1\times}$ speedup. Code available at https://github.com/xinghaow99/prism.

LLMs can process long documents, code, and videos, but standard attention becomes very slow as inputs grow. Sparse attention speeds this up by looking at only the most relevant blocks, but choosing those blocks efficiently is difficult. We identify an important caveat in a common shortcut: when tokens are averaged after RoPE positional encoding, mean pooling can act like a low-pass filter, washing out fine-grained local position information. This explains why prior block-selection methods often need expensive token-level corrections. To address this, we propose Prism, which separates broad semantic signals from local positional signals and restores their balance through online calibration without extra hyperparameters. Prism requires no model training and uses only efficient block-level operations. Across long-document, retrieval, and video tasks, Prism preserves nearly the same quality as full attention while making long-context processing much faster, with up to 5.1× speedup.