- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors introduce PISA, a block sparse attention approach that first iteratively divides the sequence into a hierarchy of levels where blocks of tokens are split into groups at each level. The method then computer per-block scores at each level, from which the top scoring blocks at each level are selected and gradually refined into tokens that are used for a sparse attention computation. The method improves the asymptotic complexity relative to standard and other block sparse attention approaches, while demonstrating competitive behaviour on language modeling and passkey retrieval tasks.
Critical strengths
The approach is unique and sensible; in many cases, not all tokens are directly necessary and thus using sparse attention is sufficient to attain most of the performance of full attention. Building a hierarchy is a useful way to reduce computation by avoiding needing to score individual tokens first prior to computing the attention, which can be significantly more efficient.
Critical weaknesses
In terms of emprical results, there is some inconsistency that questions the significance of the improvements. For NIAH, much of the improvement (over NSA) appears to be driven by the multiquery at 4K result, which is signficantly better, but at the longer lengths of 8K and 16K this gap is significantly closed. Furthermore, the result at 8K is better than at 4K, which suggests perhaps more investigation is actually necessary before a conclusive statement can be made regarding actual imiprovements. On the standard language modeling tasks, results are also somewhat modest or inconclusive as well, with the primary improvement on the FDA containment task appearing to the main cause for the improved performance relative to NSA once again.
There is also a question of actual implementation efficiency. Part of how full attention is efficienty implemented in flash-attention (which I assume is the standard most individuals use) is by computing the attention matrix and its softmax normalization factor online without ever fully writing the intermediate matrix to HBM; part of this is based on the fact that memory loads and reads are expensive. When it comes to sparse attention, naively using a mask can lead to fragmented memory reads and accesses (particularly if the most fine segments are very small), which can reduce efficiency. Thus while asyptotic behavior might be better than variants such as NSA, much of the important details for actual improvements in speed would come from requiring some type of memory layout that minimizes this. The authors don't mention any particular details about implementation nor is there specific comparison about efficiency and the comparison to asymptotic speedups, thus this remains an open point that requires some consideration.
Questions for authors
Figure 1 would appear to suggest that at the -th level, the entirety of the selected blocks are used for attention. While this doesn't affect asymptotic complexity since one can choose and the block sizes accordingly, this does lead to the question of whether redundant or unnecessary tokens may be included in the attention computation. Depending on the other tokens, this could actually amplify a negative effect if these logits are scaled inappropriately relatively to the original attention. Is there a way to counteract this possibility, as this could become a realistic issue if hyperparameters are not tuned appropriately for the downstream tasks.
For figure 2, while it is relevant to compare against full attention, however it would be more informative to possibly compare against a synthetic task such as the more standard MQAR task where known key-value pairs of tokens can be drawn and retrieved. This might give a better sense of the potential efficiency vs. accuracy/recall tradeoff that might need to be considered.
9 comments
2. Memory access, implementation details, and practical efficiency.
Rather than applying a fragmented token mask or materializing an score matrix in HBM, PISA pairs FlashAttention-style online softmax over contiguous K and V tiles with SRAM-fused pyramid routing and query clustering, reaching a A100 selector speedup at 256K and +7.0%–32.8% faster 16K training than FlashAttention at .
- Coalesced K and V tiles shared across GQA query heads avoid fragmented reads and preserve FlashAttention-style online softmax. Routing never builds a dense mask in HBM or gathers scattered tokens; Section 3.3 outputs block indices per query and KV head shared across all GQA query heads. In both training and prefill as well as Triton decoding, kernels load contiguous slices from each KV head's buffers into SRAM and update FP32 running maxima, denominators, and numerators online, with gradients flowing through fixed selected blocks in Appendix B.
- Algorithm 1 combines a flat summary buffer, SRAM-fused coarse-to-fine traversal, and inverted leaf clustering to halve leaf HBM traffic:
- Summary layout: All mean-pooled key levels are packed into one contiguous buffer by level offsets rather than pointer trees or covariances.
- Stage 1 routing, : Each Triton program loads its GQA query group once into SRAM, scores bounded child summaries via Tensor-Core dot products and FP32 LSE, and runs an in-register bitonic top- sort on-chip without writing intermediate scores to HBM.
- Stage 2 leaf clustering, : Device-side atomic bucketing and prefix sums group queries sharing a leaf block into tiles of up to without host sync, loading each key tile once against a packed query tile to halve leaf HBM I/O in Equations 9 and 15 below.
- Single-token decoding, : Without cross-query key reuse during decoding, all levels fuse into one kernel launch to avoid reloading queries in Equation 17.
- Standalone A100 timings in Table 4 closely track versus scaling, crossing over BSA at
32Kand reaching at256K. Including pyramid construction and all routing stages at and , each context doubling from32Kto256Kmultiplies BSA latency by , , and , whereasPISA-Q4grows by only , , and and beats ungroupedPer-Queryrouting by to from64Konward.
| Context | Per-Query ms | Q1 ms | Q2 ms | Q4 ms | BSA ms | Q4 Speedup vs. BSA |
|---|---|---|---|---|---|---|
| 4K | 0.573 | 0.716 | 0.703 | 0.701 | 0.167 | |
| 8K | 1.028 | 1.176 | 0.909 | 0.865 | 0.463 | |
| 16K | 2.050 | 2.296 | 1.696 | 1.581 | 1.461 | |
| 32K | 4.243 | 4.685 | 3.429 | 3.185 | 5.099 | |
| 64K | 9.041 | 9.717 | 7.183 | 6.704 | 19.144 | |
| 128K | 18.813 | 20.467 | 15.467 | 14.452 | 76.682 | |
| 256K | 41.733 | 43.365 | 33.522 | 31.441 | 312.956 |
- End-to-end
16KA100 LLM training confirms practical speedups over FlashAttention and NSA while matching BSA's memory. Including pyramid build, routing, sparse attention, backward passes, and optimizer steps, PISA at trains+32.8%,+7.7%, and+7.0%faster than FlashAttention and+19.1%–33.6%faster than NSA; at before the32Kcrossover, PISA trains+11.8%–15.7%faster than NSA and12.1%–15.6%below BSA while matching BSA's peak memory within0.08 GiBand saving6.4–12.8 GiBover NSA.
| 16K CPT Budget | Method | 418M tok/s | 418M GiB | 1.47B tok/s | 1.47B GiB | 2.67B tok/s | 2.67B GiB |
|---|---|---|---|---|---|---|---|
| Dense baseline | Full FlashAttn | 21,430.6 | 45.02 | 9,268.8 | 23.91 | 6,164.8 | 36.47 |
| NSA | 21,295.4 | 58.06 | 8,178.3 | 30.28 | 5,537.2 | 45.63 | |
| PISA | 28,458.7 | 45.28 | 9,986.7 | 23.94 | 6,597.3 | 36.56 | |
| BSA | 22,483.5 | 45.86 | 8,659.6 | 24.36 | 5,850.1 | 37.17 | |
| NSA | 16,387.5 | 58.64 | 6,716.1 | 30.85 | 4,595.9 | 47.60 | |
| PISA | 18,968.4 | 45.88 | 7,574.0 | 24.44 | 5,139.4 | 37.16 |
3. Redundant tokens within selected blocks and logit scaling.
PISA uses LSE solely to select discrete block indices and never mixes compressed summaries or rescaled logits into final attention, preserving exact token-level softmax weights inside selected blocks and improving Cont-3 in 17/18 and WikiText perplexity in 18/18 training-free block-size and budget pairs without task-specific tuning.
- Equation 2 preserves exact logit scaling, token-level differentiation inside selected blocks, and stable softmax denominator anchors. Methods that mix compressed summary keys with raw keys in final attention can distort weights when multiplicity scaling is mismatched; by contrast, PISA uses routing LSE strictly to choose block indices . Once is selected, attention is computed solely over visible original keys and values under standard scaling and one unified online softmax below, so irrelevant accompanying tokens inside a selected block retain their own lower dot products rather than receiving block-averaged weights, while Appendix B unconditionally retains the first block as an attention sink alongside the previous and current local blocks to anchor the softmax denominator.
- Across 18 training-free and pairs on frozen
Qwen3-Base0.6Band1.7Bwith zero task-specific tuning, wider blocks do not degrade from accompanying tokens and PISA consistently outperforms BSA. Enlarging block size from32to64to128at fixed includes up to more tokens per block yet lowersWikiTextperplexity at every step and raises three-task containmentCont-3acrossSWDE,SQuAD-C, andFDAin almost every step, with only a0.10-point plateau at1.7B, . Overall, PISA beats BSA in17/18Cont-3settings and18/18perplexity settings, delivering+10.3to+14.8-point gains at or where flat mean pooling suffers severe dilution.
| 0.6B Cont-3 BSA % | 0.6B Cont-3 PISA % | 1.7B Cont-3 BSA % | 1.7B Cont-3 PISA % | 0.6B PPL BSA | 0.6B PPL PISA | 1.7B PPL BSA | 1.7B PPL PISA | ||
|---|---|---|---|---|---|---|---|---|---|
| 32 | 4 | 36.14 | 46.47 | 39.40 | 50.02 | 22.22 | 21.30 | 15.89 | 15.32 |
| 64 | 4 | 45.10 | 58.16 | 47.38 | 62.21 | 20.56 | 19.71 | 14.85 | 14.40 |
| 128 | 4 | 57.54 | 69.99 | 60.80 | 72.59 | 19.22 | 18.53 | 14.08 | 13.67 |
| 32 | 8 | 58.49 | 66.62 | 63.89 | 70.63 | 18.98 | 18.57 | 13.89 | 13.65 |
| 64 | 8 | 67.60 | 73.18 | 70.65 | 75.68 | 18.33 | 17.97 | 13.50 | 13.30 |
| 128 | 8 | 73.76 | 76.05 | 76.21 | 77.70 | 17.82 | 17.61 | 13.21 | 13.08 |
| 32 | 16 | 71.08 | 74.43 | 75.08 | 76.85 | 17.97 | 17.80 | 13.29 | 13.19 |
| 64 | 16 | 75.12 | 75.93 | 77.38 | 77.98 | 17.69 | 17.55 | 13.12 | 13.05 |
| 128 | 16 | 76.06 | 76.17 | 78.11 | 77.88 | 17.49 | 17.45 | 13.02 | 13.00 |
Thank you for reading our paper carefully and for asking how broadly our results hold and how we implement PISA on GPUs.
1. Are the gains mainly driven by FDA and the 4K multiquery result?
PISA's gains hold after removing
FDAfrom Table 2, across three frozenQwen3-Basemodel scales, and after excluding4K niah_multiqueryfrom2.67BRULER, where30Bcontinual pretraining yields a+5.63-point lead over NSA and a+9.47-point lead over BSA.FDAfrom Table 2 still leaves PISA ahead of NSA, HiLS, and BSA across all three model scales. The table below averages the remaining five containment benchmarksSWDE,SQuAD Completion,TriviaQA,Natural Questions, andDROPafter100B-token4Kpretraining.Qwen3-Basemodels at0.6B,1.7B, and4Bwith C=64 and K=8, training-free PISA improvesWikiTextperplexity,SWDE, andFDAover BSA at every scale. Meanwhile,Acc-8remains tied across all three models andSQuAD-Cstays within0.10–0.40points.4K niah_multiquery; excluding it across the remaining 19 family-by-length settings confirms your Table 3 observation at10BCPT while showing a+5.63-point lead over NSA and+9.47-point lead over BSA at30BCPT. Extending16Kcontinual pretraining from10Bto30Btokens at C=64 and K=32 allows2.67BPISA to converge cleanly and surpass both baselines by a wide margin even without4K niah_multiquery.4K multiquery, 19 settings1.47BRULER gains hold at both10Band30BCPT. Specifically, the non-monotonic4Kto8Kjump in Table 3 occurs in NSA from32.65%to50.10%, whereas PISA decreases smoothly from79.00%to48.50%to20.85%; across all four NIAH families and five lengths at1.47B, PISA also beats both BSA and NSA at10BCPT with60.87%versus54.93%and53.56%, and at30BCPT with62.10%versus58.30%and51.19%.