Sparser Block-Sparse Attention via Token Permutation
Scaling the context length of large language models (LLMs) offers significant
benefits but is computationally expensive. This expense stems primarily from
the self-attention mechanism, whose O(N^2) complexity with respect to
sequence length presents a major bottleneck for both memory and latency.
Fortunately, the attention matrix is often sparse, particularly for long
sequences, suggesting an opportunity for optimization. Block-sparse attention
has emerged as a promising solution that partitions sequences into blocks and
skips computation for a subset of these blocks. However, the effectiveness of
this method is highly dependent on the underlying attention patterns, which can
lead to sub-optimal block-level sparsity. For instance, important key tokens
for queries within a single block may be scattered across numerous other
blocks, leading to computational redundancy. In this work, we propose Permuted
Block-Sparse Attention (PBS-Attn), a plug-and-play method that
leverages the permutation properties of attention to increase block-level
sparsity and enhance the computational efficiency of LLM prefilling. We conduct
comprehensive experiments on challenging real-world long-context datasets,
demonstrating that PBS-Attn consistently outperforms existing block-sparse
attention methods in model accuracy and closely matches the full attention
baseline. Powered by our custom permuted-FlashAttention kernels, PBS-Attn
achieves an end-to-end speedup of up to 2.75times in long-context
prefilling, confirming its practical viability. Code available at
https://github.com/xinghaow99/pbs-attn
68fee8b16cdff8b857f471b2
Xinghao Wang
claimed_verified
2026-02-11T11:21:50.855Z
6191f22d08a57f265f7f5266
/avatars/215164e7b6d025a3c32555ff541cdd62.svg
XinghaoWang
Singhoo
user
Singhoo
68fee8b16cdff8b857f471b3
Pengyu Wang
68fee8b16cdff8b857f471b4
Dong Zhang
68fee8b16cdff8b857f471b5
Chenkun Tan
68fee8b16cdff8b857f471b6
Shaojun Zhou
68fee8b16cdff8b857f471b7
Zhaoxiang Liu
68fee8b16cdff8b857f471b8
Shiguo Lian
68fee8b16cdff8b857f471b9
Fangxu Liu
68fee8b16cdff8b857f471ba
Kai Song
68fee8b16cdff8b857f471bb
Xipeng Qiu
Sparser Block-Sparse Attention via Token Permutation
Scaling the context length of large language models (LLMs) offers significant
benefits but is computationally expensive. This expense stems primarily from
the self-attention mechanism, whose O(N^2) complexity with respect to
sequence length presents a major bottleneck for both memory and latency.
Fortunately, the attention matrix is often sparse, particularly for long
sequences, suggesting an opportunity for optimization. Block-sparse attention
has emerged as a promising solution that partitions sequences into blocks and
skips computation for a subset of these blocks. However, the effectiveness of
this method is highly dependent on the underlying attention patterns, which can
lead to sub-optimal block-level sparsity. For instance, important key tokens
for queries within a single block may be scattered across numerous other
blocks, leading to computational redundancy. In this work, we propose Permuted
Block-Sparse Attention (PBS-Attn), a plug-and-play method that
leverages the permutation properties of attention to increase block-level
sparsity and enhance the computational efficiency of LLM prefilling. We conduct
comprehensive experiments on challenging real-world long-context datasets,
demonstrating that PBS-Attn consistently outperforms existing block-sparse
attention methods in model accuracy and closely matches the full attention
baseline. Powered by our custom permuted-FlashAttention kernels, PBS-Attn
achieves an end-to-end speedup of up to 2.75times in long-context
prefilling, confirming its practical viability. Code available at
https://github.com/xinghaow99/pbs-attn
Permuted Block-Sparse Attention improves computational efficiency in large language models by enhancing block-level sparsity in the self-attention mechanism, achieving significant speedups without compromising accuracy.
self-attention mechanism block-sparse attention Permuted Block-Sparse Attention PBS-Attn permuted-FlashAttention kernels