Block Sparse Attention with Log-Linear Complexity
Summary
The paper proposes PISA, a block sparse attention mechanism using a pyramid Top-K selection strategy to achieve O(N log N) complexity, enhancing efficiency for long-context language models with comparable performance on benchmarks and better results on retrieval tasks.
View Cached Full Text
Cached at: 09/28/26, 04:02 AM
Paper page - Block Sparse Attention with Log-Linear Complexity
Source: https://huggingface.co/papers/2609.31093
Abstract
Scalinglanguagemodelstolongcontextsislimitedbythequadraticcostofself-attention.Blocksparseattentionoffersanefficientalternative,butselectingtheretainedblocksremainsabottleneck.Conventionalblockselectionrequiresscoringallquery-blockpairsandthereforeremainsquadraticinsequencelength.Toaddressthisissue,weproposePISA,ablock-sparseattentionmechanismthatemploysapyramidTop-Kselectionstrategy.Themainideaistograduallynarrowdownthecandidatesacrossdifferentlevels,makingitmoreefficienttofindthemostrelevantkeys.Specifically,weconstructacoarse-to-finehierarchyofkeysandperformselectionfromthecoarsestlevel.Ateachlevel,LogSumExpscoringisappliedtoaboundedcandidatesettoselectcandidatesforthenextfinerlevel,continuinguntilthefinestlevelisreached.Throughpooling,weconstructO(logN)levelsofkeys,yieldinganoverallcomplexityofO(NlogN),whereNdenotesthesequencelength.Wedevelophardware-awareTritonkernelsforbothtrainingandinference,fusinghierarchicalroutingandLogSumExpscoringwithoutmaterializingthequery-keyscorematrix.Wefurtherevaluateourmethodonlanguagemodelingtasks.Comparedwiththebaseline,ourmethodachievescomparableperformanceonbenchmarkssuchascommonsensereasoningwhiledeliveringbetterresultsonretrievaltasks.
View arXiv pageView PDFAdd to collection
Models citing this paper0
No model linking this paper
Cite arxiv.org/abs/2609.31093 in a model README.md to link it from this page.
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2609.31093 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2609.31093 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
Hierarchical Sparse Attention Done Right: Toward Infinite Context Modeling
Introduces HiLS Attention, a chunk-wise sparse attention mechanism for LLMs that learns chunk selection end-to-end via LM loss, achieving performance comparable to full attention while enabling ultra-long-context extrapolation and faster inference.
RIS-Kernel: A Model-Agnostic Architecture for Long-Context LLM Inference via Sparse Attention
RIS-Kernel introduces a model-agnostic sparse attention architecture (RIS) that reduces self-attention complexity from O(N^2) to O(N log N) for long-context LLM inference, enabling operation on commodity CPU hardware without GPU acceleration.
MiniMax Sparse Attention
MiniMax Sparse Attention introduces a blockwise sparse attention mechanism that achieves significant speedups for ultra-long-context LLMs, reducing per-token attention compute by 28.4x at 1M context with wall-clock speedups of 14.2x for prefill and 7.6x for decoding on H800 GPUs. The method is accompanied by an open-source inference kernel and a publicly released multimodal model.
MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference
The paper introduces MISA, a method that applies a mixture-of-experts approach to the indexer heads in sparse attention mechanisms, significantly reducing computational costs for long-context LLM inference while maintaining performance.
COBS: Cumulant Order Block Sparse Attention
COBS introduces a cumulant-order block sparse attention method that improves block selection by using compressed second-order statistics, achieving near-dense attention accuracy on long-context benchmarks while significantly reducing KV cache read traffic.