ESPL: Efficient Block Sparse Plus Low-Rank Attention

The quadratic $N \times N$ attention score matrix remains a central obstacle to extending Transformers to longer inputs. We propose ESPL, an efficient block-sparse plus low-rank approximation of attention. Rather than decomposing the learned projection matrices, ESPL approximates the attention operator induced after $Q, K, V$ are formed: a block-sparse branch captures selected high-similarity interactions exactly, while a low-rank branch summarizes diffuse global context. Because the two branches are normalized over supports with very different denominator mass, ESPL fuses them with a denominator-aware multiplier that rescales the block-sparse branch by its estimated attention mass relative to the low-rank branch. We further show that forcing the query's own block into the block-sparse support is not merely a retrieval heuristic: it gives the hybrid operator the same rank capacity as exact dense attention, $N$, for any low-rank budget, whereas a rank-limited branch alone provably cannot represent generic dense attention exactly. ESPL thus constructs block-sparse plus low-rank attention outputs without materializing the full score matrix, preserving both sharp token-level interactions and broad contextual mixing.