# Block Sparse Attention with Log-Linear Complexity

arXiv: https://arxiv.org/abs/2609.31093 · HTML: https://mlsanity.com/paper/2609.31093/

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [BoolQ: Exploring the Surprising Difficulty of Natural Yes/No Questions](https://mlsanity.com/paper/1905.10044/) (2019)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [The LAMBADA dataset: Word prediction requiring a broad discourse context](https://mlsanity.com/paper/1606.06031/) (2016)
- [DROP: A Reading Comprehension Benchmark Requiring Discrete Reasoning Over Paragraphs](https://mlsanity.com/paper/1903.00161/) (2019)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [Simple linear attention language models balance the recall-throughput tradeoff](https://mlsanity.com/paper/2402.18668/) (2024)
- [MoBA: Mixture of Block Attention for Long-Context LLMs](https://mlsanity.com/paper/2502.13189/) (2025)
- [XAttention: Block Sparse Attention with Antidiagonal Scoring](https://mlsanity.com/paper/2503.16428/) (2025)
- [SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs](https://mlsanity.com/paper/2410.13276/) (2024)
- [SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference](https://mlsanity.com/paper/2502.18137/) (2025)
- [SparQ Attention: Bandwidth-Efficient LLM Inference](https://mlsanity.com/paper/2312.04985/) (2023)
- [Just read twice: closing the recall gap for recurrent language models](https://mlsanity.com/paper/2407.05483/) (2024)
- [InfLLM-V2: Dense-Sparse Switchable Attention for Seamless Short-to-Long Adaptation](https://mlsanity.com/paper/2509.24663/) (2025)
- [IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reuse](https://mlsanity.com/paper/2603.12201/) (2026)
- [A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention](https://mlsanity.com/paper/2406.09827/) (2024)
- [Hierarchical Sparse Attention Done Right: Toward Infinite Context Modeling](https://mlsanity.com/paper/2607.02980/) (2026)
- [Trainable Log-linear Sparse Attention for Efficient Diffusion Transformers](https://mlsanity.com/paper/2512.16615/) (2025)

## 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.