mlsanityData to 7 Oct 2026

Block Sparse Attention with Log-Linear Complexity

arXiv 2609.31093 ↗First posted 25 Sep 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Scaling language models to long contexts is limited by the quadratic cost of self-attention. Block sparse attention offers an efficient alternative, but selecting the retained blocks remains a bottleneck. Conventional block selection requires scoring all query-block pairs and therefore remains quadratic in sequence length. To address this issue, we propose PISA, a block-sparse attention mechanism that employs a pyramid Top-K selection strategy. The main idea is to gradually narrow down the candidates across different levels, making it more efficient to find the most relevant keys. Specifically, we construct a coarse-to-fine hierarchy of keys and perform selection from the coarsest level. At each level, LogSumExp scoring is applied to a bounded candidate set to select candidates for the next finer level, continuing until the finest level is reached. Through pooling, we construct O(log N) levels of keys, yielding an overall complexity of O(Nlog N), where N denotes the sequence length. We develop hardware-aware Triton kernels for both training and inference, fusing hierarchical routing and LogSumExp scoring without materializing the query-key score matrix. We further evaluate our method on language modeling tasks. Compared with the baseline, our method achieves comparable performance on benchmarks such as commonsense reasoning while delivering better results on retrieval tasks.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 34 of its 41 references that are in the map. First posted on arXiv 25 Sep 2026.

Builds on

34 of 41 references.

References · 34

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,710
  3. 2019HellaSwag: Can a Machine Really Finish Your Sentence?cited by 4,018
  4. 2020Longformer: The Long-Document Transformercited by 3,362
  5. 2016Pointer Sentinel Mixture Modelscited by 2,992
  6. 2017TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehensioncited by 2,895
  7. 2019PIQA: Reasoning about Physical Commonsense in Natural Languagecited by 2,818
  8. 2019BoolQ: Exploring the Surprising Difficulty of Natural Yes/No Questionscited by 2,140
  9. 2018Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answeringcited by 2,114
  10. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  11. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  12. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,311
22 more
  1. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,270
  2. 2016The LAMBADA dataset: Word prediction requiring a broad discourse contextcited by 960
  3. 2019DROP: A Reading Comprehension Benchmark Requiring Discrete Reasoning Over Paragraphscited by 883
  4. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 487
  5. 2025Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attentioncited by 391
  6. 2024MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attentioncited by 375
  7. 2024Simple linear attention language models balance the recall-throughput tradeoffcited by 197
  8. 2025MoBA: Mixture of Block Attention for Long-Context LLMscited by 188
  9. 2025XAttention: Block Sparse Attention with Antidiagonal Scoringcited by 131
  10. 2024SeerAttention: Learning Intrinsic Sparse Attention in Your LLMscited by 121
  11. 2023SparQ Attention: Bandwidth-Efficient LLM Inferencecited by 119
  12. 2025SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inferencecited by 113
  13. 2024Just read twice: closing the recall gap for recurrent language modelscited by 55
  14. 2025InfLLM-V2: Dense-Sparse Switchable Attention for Seamless Short-to-Long Adaptationcited by 31
  15. 2026IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reusecited by 27
  16. 2024A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attentioncited by 12
  17. 2026Hierarchical Sparse Attention Done Right: Toward Infinite Context Modelingcited by 8
  18. 2025Trainable Log-linear Sparse Attention for Efficient Diffusion Transformerscited by 6
  19. 2026Double-P: Hierarchical Top-P Sparse Attention for Long-Context LLMscited by 5
  20. 2026Simplified Sparse Attention via Gist Tokenscited by 4
  21. 2026DashAttention: Differentiable and Adaptive Sparse Hierarchical Attentioncited by 3
  22. 2026LongCat Sparse Attention: Taming the Lightning via Streaming-aware Hierarchical Cross-Layer Indexingcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026COBS: Cumulant Order Block Sparse Attention
  2. 2026AB-Sparse: Sparse Attention with Adaptive Block Size for Accurate and Efficient Long-Context Inference
  3. 2026CompactAttention: Accelerating Chunked Prefill with Block-Union KV Selection
  4. 2026LoSA: Locality Aware Sparse Attention for Block-Wise Diffusion Language Models
  5. 2024Loki: Low-rank Keys for Efficient Sparse Attention
  6. 2025Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving
  7. 2025Rectified Sparse Attention
  8. 2025Mixture of Sparse Attention: Content-Based Learnable Sparse Attention via Expert-Choice Routing