Block-sparse attention's real bottleneck was selection, not computation

The quadratic cost of self-attention is well understood, and block-sparse attention has long been the obvious fix. The catch is that picking which blocks to keep has itself been quadratic — you still have to score every query against every block to know which ones matter. PISA breaks that loop.

The mechanism is a pyramid. Keys are pooled into a hierarchy of O(log N) levels, from coarsest to finest. Selection starts at the top: a bounded candidate set is scored with LogSumExp at the coarsest level, the survivors pass down to the next finer level, and the process repeats until you reach full resolution. Because each level operates on a bounded candidate set rather than the full sequence, the total work across all levels comes out to O(N log N) — not O(N²). That's the core contribution: making block selection itself sub-quadratic, not just attention computation.

The implementation is built around hardware-aware Triton kernels that fuse the hierarchical routing and LogSumExp scoring together, avoiding materializing the full query-key score matrix at any point. That matters in practice: a theoretically cheaper algorithm that still blows out memory bandwidth is only half a solution. The kernels cover both training and inference paths.

On benchmarks, PISA matches the dense baseline on commonsense reasoning and edges ahead on retrieval tasks. Retrieval is the harder test for sparse attention — it requires the model to locate specific information across a long context, which is exactly where coarse block selection tends to fail by discarding the relevant window. The pyramid strategy's coarse-to-fine narrowing is structurally well-suited to that problem: the coarsest level can identify the rough neighborhood, and finer levels zero in.

The empirical picture reported is deliberately narrow: the paper compares against a baseline on commonsense reasoning and retrieval benchmarks, but the magnitude of gains, the specific sequence lengths tested, and wall-clock or memory comparisons against other sparse methods are not detailed in what is available. Whether the Triton kernels actually close the gap with optimized dense attention on realistic hardware remains the open question for practitioners.

The architectural insight is nonetheless clean. The bottleneck in block-sparse attention has always been selection cost, and addressing it with a logarithmic hierarchy rather than a learned or heuristic shortcut is a principled move — one that becomes more valuable precisely at the sequence lengths where quadratic attention is genuinely prohibitive.