FFTSparse: Relative-Position Correlation Guided Sparse Attention for Long-Context Language Models

The quadratic computational complexity of attention during prefilling remains a primary bottleneck for the efficiency of long-context LLMS. While sparse attention methods mitigate this cost, existing dynamic approaches rely on computationally expensive $O(N^2)$ scoring, which undermines their practical efficiency gains. In this paper, we observe that long-context attention matrices frequently exhibit prominent diagonal stripe patterns, indicating that query-key pairs separated by specific relative distances yield consistently high correlation. Motivated by this, we propose FFTSparse, a hybrid block-sparse attention framework. By formulating the identification of these dominant attention lags as cross-correlation in the frequency domain via the Fast Fourier Transform (FFT), FFTSparse reduces the cost to identify the sparsity pattern of diagonal stripes to $O(N \log N)$. Additionally, we introduce a lightweight identification module that categorizes the patterns of attention heads and then applies tailored masking strategies accordingly. Extensive evaluations demonstrate that FFTSparse incurs a negligible mask construction overhead of merely 0.02\% relative to full attention. Furthermore, it maintains competitive downstream performance on long-context benchmarks while achieving up to a $7.4x$ prefilling speedup at a 128K sequence length, offering a highly efficient solution for long-context inference of LLMS.