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 input lengths. Existing efficient-attention methods usually reduce this bottleneck by either imposing sparsity, so that each query attends only to a small subset of keys, or by using low-rank / kernel sketches, so that global interactions are compressed into a lower-dimensional representation. We propose ESPL, an efficient block-sparse plus low-rank approximation of attention. ESPL does not decompose the learned projection or output matrices of the Transformer into sparse and low-rank factors. Instead, after dense projections produce $Q, K, V$, ESPL approximates the induced attention score operator itself: a block-sparse branch captures selected high-similarity interactions exactly, while a low-rank branch summarizes diffuse global interactions. Because the two branches are normalized over supports with very different denominator mass, ESPL introduces a denominator-aware fusion term that rescales the block-sparse branch according to 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 heuristic for retrieval recall: it supplies a perfect matching that gives the hybrid operator the same rank capacity as exact dense attention, $N$, for any low-rank budget, whereas a rank-limited branch used alone provably cannot represent generic dense attention exactly. This yields a practical framework for constructing block-sparse plus low-rank attention outputs without materializing the full quadratic score matrix, aiming to enable longer-context training while preserving both sharp token-level interactions and broad contextual mixing.