Block Sparse Attention with Log-Linear Complexity
PISA cuts block selection from quadratic work to `O(N log N)` by routing through a coarse-to-fine key hierarchy.
The paper targets the selection step inside block sparse attention, where conventional methods still score all query-block pairs. Its pyramid Top-K scheme narrows candidates level by level using LogSumExp scoring over bounded sets. The authors say pooled key levels give `O(log N)` hierarchy depth and avoid materializing the full query-key score matrix with Triton kernels for training and inference. In their language-modeling tests, performance is comparable on commonsense reasoning and stronger on retrieval tasks versus the baseline. HF Daily Papers' note
The paper targets the selection step inside block sparse attention, where conventional methods still score all query-block pairs. Its pyramid Top-K scheme narrows candidates level by level using LogSumExp scoring over bounded sets. The authors say pooled key levels give `O(log N)` hierarchy depth and avoid materializing the full query-key score matrix with Triton kernels for training and inference. In their language-modeling tests, performance is comparable on commonsense reasoning and stronger on retrieval tasks versus the baseline. HF Daily Papers' note
score 5