acceptodds
Under review as a conference paper at ICLR 2027

Block Sparse Attention with Log-Linear Complexity

Abstract

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- 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 levels of keys, yielding an overall complexity of , where 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Efficient Attention, Long-Context Modeling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_sC3rOpenReview ↗
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 O(log⁡N)O(\log N) 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 KK 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 N×NN \times N 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 (L−1)(L-1)-th level, the entirety of the selected blocks are used for attention. While this doesn't affect asymptotic complexity since one can choose KK 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

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 FDA from Table 2, across three frozen Qwen3-Base model scales, and after excluding 4K niah_multiquery from 2.67B RULER, where 30B continual pretraining yields a +5.63-point lead over NSA and a +9.47-point lead over BSA.

  • Removing FDA from Table 2 still leaves PISA ahead of NSA, HiLS, and BSA across all three model scales. The table below averages the remaining five containment benchmarks SWDE, SQuAD Completion, TriviaQA, Natural Questions, and DROP after 100B-token 4K pretraining.
Scale in Table 2, 4K PTNSA Excl. FDA % ↑\uparrowHiLS Excl. FDA % ↑\uparrowBSA Excl. FDA % ↑\uparrowPISA Excl. FDA % ↑\uparrow
418M36.7338.3038.3039.16
1.47B44.8245.2445.2745.95
2.67B48.0347.2647.9048.62
  • On frozen Qwen3-Base models at 0.6B, 1.7B, and 4B with C=64C=64 and K=8K=8, training-free PISA improves WikiText perplexity, SWDE, and FDA over BSA at every scale. Meanwhile, Acc-8 remains tied across all three models and SQuAD-C stays within 0.10–0.40 points.
Qwen3-BaseMethodWikiText PPL ↓\downarrowAcc-8 % ↑\uparrowSWDE % ↑\uparrowSQuAD-C % ↑\uparrowFDA % ↑\uparrow
0.6BFull17.4454.3084.6156.2386.93
0.6BBSA18.3354.1678.1356.9767.70
0.6BPISA17.9754.1683.4456.6079.49
1.7BFull13.0061.4589.4759.7985.75
1.7BBSA13.5061.3685.0659.8267.06
1.7BPISA13.3061.3688.3059.4279.31
4BFull10.7965.8791.9059.7287.75
4BBSA11.1865.7588.5759.6271.51
4BPISA11.0265.7591.3659.5282.03
  • Thank you for pointing out 4K niah_multiquery; excluding it across the remaining 19 family-by-length settings confirms your Table 3 observation at 10B CPT while showing a +5.63-point lead over NSA and +9.47-point lead over BSA at 30B CPT. Extending 16K continual pretraining from 10B to 30B tokens at C=64C=64 and K=32K=32 allows 2.67B PISA to converge cleanly and surpass both baselines by a wide margin even without 4K niah_multiquery.
2.67B CPT Budget at C=64,K=32C=64, K=32, Excl. 4K multiquery, 19 settingsBSA %NSA %PISA %vs. BSAvs. NSA
10B CPT, Table 354.3762.5761.95+7.58+7.58−0.62-0.62
Extended 30B CPT54.9358.7764.40+9.47+9.47+5.63+5.63
  • In Table 3, PISA's accuracy decreases monotonically with length, and its 1.47B RULER gains hold at both 10B and 30B CPT. Specifically, the non-monotonic 4K to 8K jump in Table 3 occurs in NSA from 32.65% to 50.10%, whereas PISA decreases smoothly from 79.00% to 48.50% to 20.85%; across all four NIAH families and five lengths at 1.47B, PISA also beats both BSA and NSA at 10B CPT with 60.87% versus 54.93% and 53.56%, and at 30B CPT with 62.10% versus 58.30% and 51.19%.

2. Memory access, implementation details, and practical efficiency.

Rather than applying a fragmented token mask or materializing an N×NN \times N score matrix in HBM, PISA pairs FlashAttention-style online softmax over contiguous C=64C=64 K and V tiles with SRAM-fused pyramid routing and Qtile=4Q_{\text{tile}} = 4 query clustering, reaching a 9.95×9.95\times A100 selector speedup at 256K and +7.0%–32.8% faster 16K training than FlashAttention at K=8K=8.

  • Coalesced C=64C=64 K and V tiles shared across GQA query heads avoid fragmented reads and preserve FlashAttention-style online softmax. Routing never builds a dense N×NN \times N mask in HBM or gathers scattered tokens; Section 3.3 outputs KK block indices per query and KV head shared across all GQ=16G_Q = 16 GQA query heads. In both training and prefill as well as Triton decoding, kernels load contiguous 64×d64 \times d slices from each KV head's N×dN \times d 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 Qtile=4Q_{\text{tile}} = 4 leaf clustering to halve leaf HBM traffic:
    • Summary layout: All L=O(log⁡N)L = O(\log N) mean-pooled key levels are packed into one contiguous O(Nd/C)O(Nd/C) buffer by level offsets rather than pointer trees or O(d2)O(d^2) covariances.
    • Stage 1 routing, ℓ=L→2\ell = L \to 2: Each Triton program loads its GQ×dG_Q \times d 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-KK sort on-chip without writing intermediate scores to HBM.
    • Stage 2 leaf clustering, ℓ=1\ell = 1: Device-side atomic bucketing and prefix sums group queries sharing a leaf block into tiles of up to Qtile=4Q_{\text{tile}} = 4 without host sync, loading each d×64d \times 64 key tile once against a packed 64×d64 \times d query tile to halve leaf HBM I/O in Equations 9 and 15 below.
    • Single-token decoding, ℓ=L→1\ell = L \to 1: Without cross-query key reuse during decoding, all levels fuse into one kernel launch to avoid reloading queries in Equation 17.

[(QtileGQ)×d]×[d×C]→(QtileGQ)×C,GQ+C/Qtile=16+64/4=32<64=C.[(Q_{\text{tile}} G_Q) \times d] \times [d \times C] \to (Q_{\text{tile}} G_Q) \times C, \qquad G_Q + C / Q_{\text{tile}} = 16 + 64 / 4 = 32 < 64 = C.

  • Standalone A100 timings in Table 4 closely track O(Nlog⁡N)O(N \log N) versus O(N2)O(N^2) scaling, crossing over BSA at 32K and reaching 9.95×9.95\times at 256K. Including pyramid construction and all routing stages at C=64C=64 and K=8K=8, each context doubling from 32K to 256K multiplies BSA latency by 3.75×3.75\times, 4.01×4.01\times, and 4.08×4.08\times, whereas PISA-Q4 grows by only 2.11×2.11\times, 2.16×2.16\times, and 2.18×2.18\times and beats ungrouped Per-Query routing by 1.30×1.30\times to 1.35×1.35\times from 64K onward.
ContextPer-Query msQ1 msQ2 msQ4 msBSA msQ4 Speedup vs. BSA
4K0.5730.7160.7030.7010.1670.24×0.24\times
8K1.0281.1760.9090.8650.4630.54×0.54\times
16K2.0502.2961.6961.5811.4610.92×0.92\times
32K4.2434.6853.4293.1855.0991.60×1.60\times
64K9.0419.7177.1836.70419.1442.86×2.86\times
128K18.81320.46715.46714.45276.6825.31×5.31\times
256K41.73343.36533.52231.441312.9569.95×9.95\times
  • End-to-end 16K A100 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 K=8K=8 trains +32.8%, +7.7%, and +7.0% faster than FlashAttention and +19.1%–33.6% faster than NSA; at K=32K=32 before the 32K crossover, PISA trains +11.8%–15.7% faster than NSA and 12.1%–15.6% below BSA while matching BSA's peak memory within 0.08 GiB and saving 6.4–12.8 GiB over NSA.
16K CPT BudgetMethod418M tok/s418M GiB1.47B tok/s1.47B GiB2.67B tok/s2.67B GiB
Dense baselineFull FlashAttn21,430.645.029,268.823.916,164.836.47
C=64,K=8C=64, K=8NSA21,295.458.068,178.330.285,537.245.63
C=64,K=8C=64, K=8PISA28,458.745.289,986.723.946,597.336.56
C=64,K=32C=64, K=32BSA22,483.545.868,659.624.365,850.137.17
C=64,K=32C=64, K=32NSA16,387.558.646,716.130.854,595.947.60
C=64,K=32C=64, K=32PISA18,968.445.887,574.024.445,139.437.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 1/d1/\sqrt{d} 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 1/d1/\sqrt{d} 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 It=It(1)\mathcal{I}_t = \mathcal{I}_t^{(1)}. Once Tt\mathcal{T}_t is selected, attention is computed solely over visible original keys and values under standard 1/d1/\sqrt{d} 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.

ot=∑j∈Tt,j≤texp⁡(qt⊤kj/d)vj/(∑j∈Tt,j≤texp⁡(qt⊤kj/d)).o_t = \sum _ {j \in \mathcal{T} _ t, j \le t} \exp(q_t^\top k_j / \sqrt{d}) v_j \Big/ \Big(\sum _ {j \in \mathcal{T} _ t, j \le t} \exp(q_t^\top k_j / \sqrt{d})\Big).

  • Across 18 training-free C∈{32,64,128}C \in \{32, 64, 128\} and K∈{4,8,16}K \in \{4, 8, 16\} pairs on frozen Qwen3-Base 0.6B and 1.7B with zero task-specific tuning, wider blocks do not degrade from accompanying tokens and PISA consistently outperforms BSA. Enlarging block size CC from 32 to 64 to 128 at fixed KK includes up to 4×4\times more tokens per block yet lowers WikiText perplexity at every step and raises three-task containment Cont-3 across SWDE, SQuAD-C, and FDA in almost every step, with only a 0.10-point plateau at 1.7B, K=16K=16. Overall, PISA beats BSA in 17/18 Cont-3 settings and 18/18 perplexity settings, delivering +10.3 to +14.8-point gains at C=128C=128 or K=4K=4 where flat mean pooling suffers severe dilution.
CCKK0.6B Cont-3 BSA % ↑\uparrow0.6B Cont-3 PISA % ↑\uparrow1.7B Cont-3 BSA % ↑\uparrow1.7B Cont-3 PISA % ↑\uparrow0.6B PPL BSA ↓\downarrow0.6B PPL PISA ↓\downarrow1.7B PPL BSA ↓\downarrow1.7B PPL PISA ↓\downarrow
32436.1446.4739.4050.0222.2221.3015.8915.32
64445.1058.1647.3862.2120.5619.7114.8514.40
128457.5469.9960.8072.5919.2218.5314.0813.67
32858.4966.6263.8970.6318.9818.5713.8913.65
64867.6073.1870.6575.6818.3317.9713.5013.30
128873.7676.0576.2177.7017.8217.6113.2113.08
321671.0874.4375.0876.8517.9717.8013.2913.19
641675.1275.9377.3877.9817.6917.5513.1213.05
1281676.0676.1778.1177.8817.4917.4513.0213.00
Reviewer_TieBOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper proposes PISA, a block-sparse attention mechanism that replaces exhaustive block scoring with coarse-to-fine selection over a mean-pooled key hierarchy. It uses LogSumExp (LSE) over child summaries at intermediate levels and over original keys at the leaf level, then computes attention using the original keys and values in the selected blocks. With a fixed block budget, block size, branching factor, and model dimensions, selection costs O(N log N) for prefill and amortized O(log N) per decoding step. The implementation combines fused intermediate routing with leaf-key reuse across queries during prefill. Evaluation includes models up to 2.67B parameters trained on 100B tokens, 16K continued pretraining and retrieval evaluation, and selector latency measurements up to 256K. Results show broadly comparable language-modeling performance, improved retrieval over BSA in several settings, and faster long-sequence block selection.

Critical strengths
  1. For a fixed query head, raw-key LSE ranks visible blocks exactly by their full-attention probability mass. This gives block scoring a direct relationship to the quantity that sparse attention aims to preserve and addresses the dilution of salient matches by mean pooling. The intermediate-level analysis carefully states its limitations, and the shared-Q/K diagnostic in Table 7 supports the empirical value of the scoring choice. I regard this scoring perspective as the main contribution. But coarse-to-fine pyramid search itself is not new.

  2. The paper evaluates multiple model scales with matched training settings. The language-modeling results suggest that hierarchical routing can preserve competitive quality, while the long-sequence selector timings demonstrate the expected scaling advantage over exhaustive block selection.

Critical weaknesses
  1. Figure 3 and Table 4 measure summary construction and selection, explicitly excluding attention over the selected blocks. Appendix B specifies tensor shapes and timing methodology but does not identify the GPU. There is no complete-attention comparison against a hardware-appropriate FlashAttention implementation, measured peak-memory breakdown, or batch/concurrency sweep. The O((N/C)d) summary-cache bound does not establish actual memory overhead or its effect on feasible concurrency. Consequently, the reported selector speedup does not yet establish the speedup of a complete attention layer or the throughput attainable under a fixed GPU memory budget. This matters because practical long-context efficiency is a central motivation of the work.

  2. Table 3 reports four RULER NIAH families, but not variable tracking, common/frequent word extraction, or the RULER SQuAD/HotpotQA tasks. The separate SQuAD Completion evaluation does not substitute for the RULER QA setting. Tasks involving distributed aggregation and multiple supporting facts would be particularly informative for a method that prunes whole regions at intermediate levels. Long-output reasoning is also untested: the containment evaluations generate at most 48 tokens, so they do not establish whether sparse routing preserves final-answer quality over extended autoregressive generation. The existing results also warrant a qualified interpretation: at 16K, PISA trails NSA on all four reported families, and Table 6 reports lower containment averages than BSA after continued pretraining. In addition, model quality is evaluated only through 16K, whereas the strongest selector speedups occur at substantially longer lengths and use a different block budget. These limitations do not negate the reported gains, but they leave the breadth of the quality-efficiency tradeoff uncertain.

Questions for authors
  1. Which GPU was used for Table 4? Could you provide a representative complete-attention comparison against a hardware-appropriate FlashAttention implementation, including pyramid construction, routing, and selected attention in PISA's timing? Please distinguish prefill, forward/backward training, and KV-cached decoding where measured, and include a configuration matching the model-quality experiments. The current selector-only comparison should remain separate because full attention has no corresponding selection stage.

  2. What is the measured peak GPU memory of PISA relative to BSA and optimized full attention, separating persistent KV/pyramid storage from routing workspace? For a representative long-context workload, how do feasible concurrency and aggregate throughput change under the same GPU memory budget? A modest batch/concurrency sweep, with latency reported alongside throughput, would help establish whether the single-batch advantage survives higher utilization.

  3. Could you provide a small representative extension of the existing RULER evaluation, for example, one of CWE/FWE and QA-Hotpot, using the existing checkpoints and matched block budgets? These would test distributed aggregation and multi-document evidence use. How should the retrieval claim be scoped in light of the 16K comparison with NSA and the post-CPT containment results in Table 6?

  4. Could you provide long-output reasoning evaluations using standardized lm-evaluation-harness task configurations such as gpqa_diamond_cot_n_shot and aime? The purpose is to test whether changes in attention affect final-answer quality as generation proceeds and errors may accumulate, which the current retrieval and short-output evaluations do not address. The full-attention baseline should have nontrivial performance for the comparison to be informative; if these tasks are too difficult for the current checkpoints, please provide a suitable alternative long-output reasoning task and explain the choice.

6 comments

Thank you for your detailed questions about system performance and how we evaluated PISA.

1. GPU identification and complete-attention efficiency.

All Table 4 benchmarks were measured on NVIDIA A100 GPUs and reach a 9.95×9.95\times selector speedup over BSA at 256K, while complete end-to-end 16K LLM training on A100 outperforms FlashAttention by +7.0%–32.8% at K=8K=8 and NSA by +11.8%–15.7% at K=32K=32.

  • On NVIDIA A100, standalone prefill selector latency crosses over flat BSA at 32K and scales to a 9.95×9.95\times speedup at 256K. Kept separate from full attention as requested, the Table 4 timings below include mean-pyramid construction and all routing levels at C=64C=64 and K=8K=8 from 4K to 256K, where Q1, Q2, and Q4 denote the leaf query-grouping tile sizes in Appendix B.
ContextPer-Query msQ1 msQ2 msQ4 msBSA msQ4 vs. BSA
4K0.5730.7160.7030.7010.1670.24×0.24\times
8K1.0281.1760.9090.8650.4630.54×0.54\times
16K2.0502.2961.6961.5811.4610.92×0.92\times
32K4.2434.6853.4293.1855.0991.60×1.60\times
64K9.0419.7177.1836.70419.1442.86×2.86\times
128K18.81320.46715.46714.45276.6825.31×5.31\times
256K41.73343.36533.52231.441312.9569.95×9.95\times
  • Complete forward-and-backward LLM training throughput on NVIDIA A100 exceeds FlashAttention at 16K when K=8K=8 and at 1.47B when K=16K=16, and beats NSA across every configuration. Measured under the exact model configurations of our 4K pretraining and 16K continual pretraining quality experiments, the tokens/s figures below include pyramid construction, routing, selected sparse attention, backward passes, and optimizer updates, with 1.47B at K=16K=16 also reaching 9,645.4 tok/s versus 9,268.8 tok/s for FlashAttention. Under 16K and K=32K=32 prior to the 32K routing crossover, PISA trains 11.8%–15.7% faster than NSA and 12.1%–15.6% below flat BSA, trading a modest short-context routing cost for +7.81 to +9.16 RULER points at 2.67B.
Regime & BudgetMethod418M tok/s1.47B tok/s2.67B tok/s
4K PTFull FlashAttn44,913.716,732.810,119.2
4K PT, C=64,K=8C=64, K=8BSA43,092.415,655.39,182.5
4K PT, C=64,K=8C=64, K=8NSA32,399.812,706.88,120.2
4K PT, C=64,K=8C=64, K=8PISA38,152.414,295.78,884.3
16K CPTFull FlashAttn21,430.69,268.86,164.8
16K CPT, C=64,K=8C=64, K=8NSA21,295.48,178.35,537.2
16K CPT, C=64,K=8C=64, K=8PISA28,458.79,986.76,597.3
16K CPT, C=64,K=32C=64, K=32BSA22,483.58,659.65,850.1
16K CPT, C=64,K=32C=64, K=32NSA16,387.56,716.14,595.9
16K CPT, C=64,K=32C=64, K=32PISA18,968.47,574.05,139.4
  • Distinguishing prefill, training, and KV-cached decoding clarifies both our measured scope and why long-context selector speedups carry over to complete attention. Our benchmarks directly measure standalone prefill routing in Table 4 and complete forward-and-backward training above, whereas KV-cached decoding is not separately benchmarked end-to-end. Structurally, once KK leaf blocks are selected, PISA and BSA execute the exact same sparse-attention kernel in both prefill and decoding, and during decoding Section 3.3 updates only the current leaf mean and its O(log⁡N)O(\log N) ancestor path before launching one single-stage fused routing kernel.

2. Peak memory, KV/pyramid storage, workspace, and concurrency.

PISA adds only +0.78% persistent summary storage over BSA at 1.56% of raw KV for C=64C=64, avoids dense score-matrix workspaces, and matches BSA's peak A100 GPU memory within 0.08 GiB at 16K while staying 20.8%–21.9% below NSA.

  • Separating persistent storage from routing workspace shows that both components add negligible memory overhead. Under equal head dimension dd and precision, a binary pyramid stores ≈2Nd/C\approx 2Nd/C persistent summary elements per KV head alongside the shared 2Nd2Nd raw K and V cache without duplicating raw KV. Meanwhile, for transient routing workspace, Section 3.3 never materializes a dense N×(N/C)N \times (N/C) score matrix: Stage 1 keeps intermediate candidates in on-chip SRAM and writes at most gKgK leaf candidates per query and KV head to HBM before Stage 2 selects the final KK block indices, bounding routing workspace at O(NK)O(NK) per KV head.
Persistent Cache Component per KV HeadFull AttentionBSAPISA
Raw K & V cache2Nd2Nd2Nd2Nd2Nd2Nd
Key-summary cache00Nd/CNd/C≈2Nd/C\approx 2Nd/C
Summary overhead vs. raw KV, C=64C=640%0\%≈0.78%\approx 0.78\%≈1.56%\approx 1.56\%
  • Measured NVIDIA A100 peak training memory matches BSA across every configuration and saves 6.0–12.8 GiB, or 18.9%–22.5%, relative to NSA. The figures below include persistent parameters, optimizer states, activations, routing indices, LSE workspaces, and allocator buffers under matched micro-batch sizes at each model scale.
Regime & BudgetMethod418M GiB1.47B GiB2.67B GiB
4K PTFull FlashAttn24.0325.0935.98
4K PT, C=64,K=8C=64, K=8BSA23.9225.0536.19
4K PT, C=64,K=8C=64, K=8NSA30.8630.3244.61
4K PT, C=64,K=8C=64, K=8PISA23.9224.3336.19
16K CPTFull FlashAttn45.0223.9136.47
16K CPT, C=64,K=8C=64, K=8NSA58.0630.2845.63
16K CPT, C=64,K=8C=64, K=8PISA45.2823.9436.56
16K CPT, C=64,K=32C=64, K=32BSA45.8624.3637.17
16K CPT, C=64,K=32C=64, K=32NSA58.6430.8547.60
16K CPT, C=64,K=32C=64, K=32PISA45.8824.4437.16
  • Although our end-to-end systems runs used fixed per-GPU micro-batches rather than serving concurrency sweeps, the memory breakdown above directly bounds feasible batch capacity. Because PISA adds only +0.78% persistent per-request cache over BSA with bounded O(NK)O(NK) routing workspace and matches BSA's measured GPU memory across all scales while saving 6.0–12.8 GiB over NSA, PISA preserves virtually the same per-GPU batch capacity and concurrency headroom as BSA while supporting substantially higher concurrency than NSA under a fixed GPU memory budget.

3. Retrieval performance and tasks beyond top-KK block selection.

PISA consistently improves localized and multi-key retrieval across block budgets, extended continual pretraining, and frozen routing, while we explicitly scope top-KK block selection to salient evidence retrieval rather than uniform whole-sequence counting such as CWE and FWE.

  • Across block budgets and extended 30B-token continual pretraining, PISA consistently leads both BSA and NSA on RULER multi-needle retrieval. Averaged over all four NIAH families across five context lengths below, PISA outperforms both baselines at every budget KK on 1.47B. Although NSA led on the 16K slice of 2.67B after brief 10B continual pretraining in Table 3 despite PISA already leading overall, extending continual pretraining to 30B tokens widens PISA's 2.67B lead over both baselines and overtakes both on 16K niah_multiquery at 23.70% versus 19.85% for NSA and 17.60% for BSA.
Trained 16K RULER Setting, C=64C=64BSA %NSA %PISA %vs. BSAvs. NSA
1.47B, 10B CPT, K=8K=839.3442.9843.56+4.22+0.58
1.47B, 10B CPT, K=16K=1649.1749.5253.21+4.04+3.69
1.47B, 10B CPT, K=32K=3254.9353.5660.87+5.94+7.31
1.47B, Extended 30B CPT, K=32K=3258.3051.1962.10+3.80+10.91
2.67B, 10B CPT, K=32K=32, Table 354.9961.0762.80+7.81+1.73
2.67B, Extended 30B CPT, K=32K=3255.5956.4764.75+9.16+8.28
  • Table 6's containment dip reflects short-prompt FDA variance under brief continual pretraining, whereas longer training and frozen routing both confirm PISA's extraction advantage. In Table 6, PISA already surpasses BSA on SQuAD Completion across larger scales, with its lower average driven mainly by short-prompt FDA; under our full-scale 2.67B continual-pretraining recipe, PISA reaches 69.81% three-task containment and edges past Full Attention at 69.12%. Likewise, when isolating block selection from training dynamics on frozen checkpoints, PISA consistently improves both exact block recall in Table 7 and three-task containment over flat BSA across every Qwen3-Base scale.
  • Mechanistically, our retrieval claims are scoped to localized and multi-needle salient evidence rather than uniform whole-sequence counting. Any hard top-KK selector attends to only KC≪NKC \ll N tokens and drops unselected blocks by design, so it cannot tally uniform token frequencies across the entire prompt as required by CWE and FWE. While CWE, FWE, variable tracking, and QA-Hotpot were not included in our evaluation suite, PISA directly targets and improves multi-fact retrieval over localized salient blocks across niah_multikey, niah_multiquery, and niah_multivalue, and we will state this scope clearly in the revision.
Reviewer_jusEOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PISA, a trainable block-sparse attention mechanism that replaces exhaustive block scoring with hierarchical coarse-to-fine selection. It constructs a mean-pooled key pyramid, retains a bounded number of candidates at each level using LogSumExp scores, and computes attention over the original keys and values in the selected leaf blocks. With fixed selection parameters, the method achieves (O(N logN)) prefill complexity and amortized (O(logN)) selection during decoding.

Critical strengths
  1. The paper addresses the quadratic cost of exhaustive block selection, an important bottleneck in block-sparse attention. Its hierarchical search reduces selection complexity to (O(N logN)) under fixed selection parameters.
  2. The implementation accounts for the different execution patterns of prefill and decoding. Fused hierarchical routing reduces intermediate memory traffic, and query grouping enables leaf-key reuse during prefill. The benchmarks demonstrate substantial routing speedups over BSA at long sequence lengths.
  3. The experiments cover three model scales with matched backbone and training settings, evaluating language modeling, downstream tasks, retrieval, and selection quality. The PISA-1 and PISA-2 ablations provide useful evidence about the contribution of LSE scoring.
Critical weaknesses
  1. Hierarchical pruning is irreversible: important leaf blocks cannot be recovered once their ancestors are discarded. As context length grows, the hierarchy deepens and coarse summaries cover larger regions, but the paper does not sufficiently evaluate the resulting risk of missing relevant tokens.
  2. Long-context quality evaluation is limited to four RULER retrieval families up to 16K, while routing speedups emerge at 32K–256K. Quality results at these longer lengths and broader long-document tasks are needed to establish the claimed quality–efficiency tradeoff.
  3. The efficiency results measure block selection rather than end-to-end model performance. Prefill, decoding, and training benchmarks should include sparse attention and the overhead of maintaining the additional summary cache under realistic model configurations.
  4. The efficiency evaluation reports selector latency without establishing end-to-end benefits or memory costs. Maintaining the full pyramid approximately doubles the number of cached summary vectors relative to single-level BSA, while retaining the original KV cache. The paper should report actual memory overhead and end-to-end prefill, decoding, and training performance.
Questions for authors

See weaknesses.

12 comments

Thank you for your thoughtful review and constructive questions.

1. Important leaves may be lost through irreversible hierarchical pruning.

Every sparse attention method faces potential key omissions under a finite budget, yet PISA applies sparsity only to keys while keeping queries token-wise, and empirically outperforms both flat BSA and O(N2)O(N^2) NSA while running faster and using less memory than NSA.

  • Sparsity in PISA operates exclusively on candidate keys KK, whereas queries QQ are never pooled or pruned. As detailed in Section 3.2, every token retains its full hidden representation and issues its own unpooled token-wise query qtq_t while always attending to local forced blocks. Moreover, hierarchical pruning is query-specific and non-destructive to the KV cache: skipping an ancestor key region for one query qtq_t never evicts those keys from the sequence, so they remain fully accessible to other queries, KV heads, and deeper layers.
  • Replacing flat mean pooling with hierarchical LSE mitigates coarse-level dilution while preserving O(Nlog⁡N)O(N \log N) complexity. Scoring all N/CN/C leaves with exact raw-key LSE in a flat selector would touch all NN keys per query and revert to O(N2d)O(N^2 d) Full Attention, whereas narrowing candidates to at most gKgK blocks per level lets PISA evaluate exact raw-key LSE at the leaves in O(N)O(N) work. At intermediate levels, Equation 21 bounds normalized child-mean LSE between PISA-1 mean pooling and exact raw-key block LSE using only O(d)O(d) summaries, and max⁡jmj≤LSE⁡(m)≤max⁡jmj+log⁡g\max_j m_j \le \operatorname{LSE}(m) \le \max_j m_j + \log g prevents low-scoring sibling regions from averaging away a salient child block as the hierarchy deepens.
  • Across frozen-Q/K diagnostics and trained LLMs, PISA consistently outperforms flat BSA and surpasses O(N2)O(N^2) NSA at higher efficiency. On identical frozen Full-Attention Q and K tensors at C=64C=64 and K=8K=8 in Table 7 below, progressive summary enrichment steadily reduces leaf omissions over flat BSA. Likewise, in trained LLMs across Tables 2 and 3 as well as Points 2 and 3 below, PISA consistently beats flat BSA on containment and 16K RULER retrieval, and outperforms O(N2)O(N^2) NSA while achieving higher training throughput and substantially lower peak GPU memory across every scale.
SelectorRecall@8 % ↑\uparrowCaptured Mass % ↑\uparrowAttention Mass Ratio % ↑\uparrow
BSA, flat mean85.9185.6798.42
PISA-1, pyramid mean84.7585.5098.22
PISA-2, pyramid 2nd-order88.2486.1399.02
PISA, pyramid LSE90.9586.4799.46
  • We further ran training-free experiments on pretrained Qwen3-Base models from 0.6B to 4B, confirming consistent gains over flat BSA without updating any weights. Applying each selector directly to frozen Qwen3-Base checkpoints at C=64C=64 and K=8K=8, three-task containment averaged over SWDE, SQuAD-C, and FDA reproduces the exact ordering PISA-1<BSA<PISA-2<PISA\text{PISA-1} < \text{BSA} < \text{PISA-2} < \text{PISA} across all three model scales.
Frozen BackboneBSA %PISA-1 %PISA-2 %PISA %
Qwen3-0.6B67.6067.4071.9273.18
Qwen3-1.7B70.6570.2274.7675.68
Qwen3-4B73.2372.7276.8177.64

2. Broader long-document tasks and the gap between quality and timing lengths.

Across multi-scale 10B to 30B 16K CPT on RULER, training-free Qwen3-Base from 0.6B to 4B, and aligned 2.67B scaling over ~300B + ~30B tokens, PISA outperforms BSA and NSA and closely matches Full Attention while attending to at most 12.5% of context tokens.

  • Extending 16K CPT from 10B to 30B tokens widens PISA's RULER advantage over both BSA and NSA at 2.67B, reaching 64.75%. Evaluated at C=64C=64 and K=32K=32 across four NIAH families and five context lengths from 1K to 16K, PISA also achieves lower 30B CPT training loss than BSA across all three model scales.
CPT Stage at 16K, C=64,K=32C=64, K=32ScaleFull %BSA %NSA %PISA %vs. BSAvs. NSA
10B CPT1.47B72.9554.9353.5660.87+5.94+7.31
10B CPT, Table 32.67B66.2454.9961.0762.80+7.81+1.73
Extended 30B CPT1.47B73.6358.3051.1962.10+3.80+10.91
Extended 30B CPT2.67B70.7855.5956.4764.75+9.16+8.28
  • On frozen Qwen3-Base models at 0.6B, 1.7B, and 4B with C=64C=64 and K=8K=8, training-free PISA improves WikiText perplexity, SWDE, and FDA over BSA across all three scales. In the table below, Acc-8 denotes the 8-task multiple-choice average.
Qwen3-BaseMethodWikiText PPL ↓\downarrowAcc-8 % ↑\uparrowSWDE % ↑\uparrowSQuAD-C % ↑\uparrowFDA % ↑\uparrow
0.6BFull17.4454.3084.6156.2386.93
0.6BBSA18.3354.1678.1356.9767.70
0.6BPISA17.9754.1683.4456.6079.49
1.7BFull13.0061.4589.4759.7985.75
1.7BBSA13.5061.3685.0659.8267.06
1.7BPISA13.3061.3688.3059.4279.31
4BFull10.7965.8791.9059.7287.75
4BBSA11.1865.7588.5759.6271.51
4BPISA11.0265.7591.3659.5282.03
  • Under an aligned 2.67B scaling recipe with ~300B pretraining tokens at 4K and ~30B CPT tokens at 16K, PISA beats 100% Full Attention on both-stage loss, 16K perplexity, and 16K Cont-3. Attending to at most 12.5% of context tokens with K=8K=8 at 4K and K=32K=32 at 16K, PISA trades only 1.54 points on Acc-8 at 16K.
Stage at 2.67BMethodLoss ↓\downarrowWikiText ↓\downarrowLAMBADA ↓\downarrowAcc-8 %SWDE %SQuAD-C %FDA %Cont-3 %
~300B / 4KFull2.136212.66678.463860.7078.2247.4579.2268.30
~300B / 4KPISA, K=8K=82.132912.74458.463360.2280.4746.5174.6867.22
+~30B / 16KFull1.589210.80786.329059.9479.9351.0176.4169.12
+~30B / 16KPISA, K=32K=321.587610.73076.263958.4083.2650.1376.0469.81
  • Evaluating RULER beyond 16K is not meaningful without longer continual pretraining, which was beyond our compute budget. Training multiple sparse and dense variants from scratch across three model scales up to 300B pretraining tokens plus 16K CPT already exhausted our available compute resources, preventing continual pretraining at 32K–256K. Because our checkpoints are only trained up to 16K context, running RULER at longer lengths would reflect out-of-window positional extrapolation collapse across all models rather than differences in sparse block selection. Meanwhile, as shown in Point 3, PISA already outperforms FlashAttention at K=8K=8 and NSA at both K=8K=8 and K=32K=32 in end-to-end 16K training efficiency.

3. Complete-system performance and additional cache cost. (Response to Weaknesses 3 & 4)

On NVIDIA A100, PISA adds only +0.78% persistent summary storage over BSA at 1.56% of raw KV for C=64C=64, matches BSA's peak GPU memory while saving over 20% memory relative to NSA at 16K, trains faster than FlashAttention at 16K with K=8K=8, and reaches a 9.95×9.95\times selector speedup at 256K.

  • Complete NVIDIA A100 end-to-end LLM training beats FlashAttention at 16K with K=8K=8 and beats NSA across every configuration while matching BSA's memory footprint. The table below includes pyramid construction, routing, selected sparse attention, backward passes, optimizer steps, and workspace buffers under matched micro-batch sizes at each model scale. Even at 16K with K=32K=32 prior to the 32K routing crossover, PISA trains 11.8%–15.7% faster than NSA while trading only a modest short-context routing gap behind flat BSA for substantial RULER gains.
Regime & BudgetMethod418M tok/s418M GiB1.47B tok/s1.47B GiB2.67B tok/s2.67B GiB
4K PTFull FlashAttn44,913.724.0316,732.825.0910,119.235.98
4K PT, C=64,K=8C=64, K=8BSA43,092.423.9215,655.325.059,182.536.19
4K PT, C=64,K=8C=64, K=8NSA32,399.830.8612,706.830.328,120.244.61
4K PT, C=64,K=8C=64, K=8PISA38,152.423.9214,295.724.338,884.336.19
16K CPTFull FlashAttn21,430.645.029,268.823.916,164.836.47
16K CPT, C=64,K=8C=64, K=8NSA21,295.458.068,178.330.285,537.245.63
16K CPT, C=64,K=8C=64, K=8PISA28,458.745.289,986.723.946,597.336.56
16K CPT, C=64,K=32C=64, K=32BSA22,483.545.868,659.624.365,850.137.17
16K CPT, C=64,K=32C=64, K=32NSA16,387.558.646,716.130.854,595.947.60
16K CPT, C=64,K=32C=64, K=32PISA18,968.445.887,574.024.445,139.437.16
  • Once KK leaf blocks are selected, PISA and BSA execute the exact same sparse-attention kernel in both prefill and decoding, while Table 4 includes pyramid maintenance and all routing levels. During prefill, Table 4 benchmarks full pyramid construction plus hierarchical routing, where PISA-Q4 overtakes BSA from 32K onward and reaches a 9.95×9.95\times speedup at 256K with 31.44 ms versus 312.96 ms; during decoding, Section 3.3 updates only the current leaf mean and its O(log⁡N)O(\log N) ancestor path without rebuilding past summaries before running the same selected-block attention.
  • Doubling key summaries from N/CN/C to ≈2N/C\approx 2N/C adds negligible memory because the shared 2Nd2Nd raw KV cache is never duplicated. At C=64C=64, the entire summary pyramid equals only 1.56% of raw KV storage, adding just +0.78% over flat BSA, so measured peak GPU memory in the table above matches BSA across every scale while saving 6.0–12.8 GiB relative to NSA.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Additional Results and Clarifications

Dear Area Chair and Reviewers,

We sincerely thank the reviewers and Area Chair for their time and constructive feedback. For ease of reference, we summarize the main conclusions from the additional experiments and clarifications provided across our rebuttal and follow-up responses:

  • Hierarchical pruning fidelity and training-free generalization [Reviewers jusE, TieB, sC3r]. Directly comparing PISA against an exact O(N2d)O(N^2 d) flat-LSE oracle on frozen Qwen3 models confirms that hierarchical pruning incurs minimal block loss across 4K to 32K contexts, substantially outperforming flat mean-pooled BSA in oracle block recall, attention-output approximation error, and 32K needle-in-a-haystack retrieval. In training-free evaluations across frozen Qwen3-Base models (0.6B to 4B) and block-size/budget grids, PISA consistently improves perplexity and extraction accuracy over BSA while reducing routing complexity from O(N2)O(N^2) to O(Nlog⁡N)O(N \log N).
  • End-to-end training and inference efficiency [Reviewers jusE, TieB, sC3r]. Full-model NVIDIA A100 benchmarks confirm that PISA's log-linear routing translates into practical system speedups with negligible memory overhead: at 64K context, CUDA-Graph prefill is up to 4.81×4.81\times faster than Full Attention and 1.56×1.56\times faster than BSA, with comparable KV-cached decode latency and virtually identical peak memory. Across complete 418M to 2.67B training runs, PISA trains faster than FlashAttention at moderate budgets and consistently outperforms NSA in both throughput and peak memory (saving roughly 20% GPU memory).
  • Extended scaling, longer contexts, and budget trade-offs [Reviewers jusE, TieB, sC3r]. Extending 16K continual pretraining to 30B tokens further widens PISA's RULER retrieval advantage over both BSA and NSA, including when excluding the 4K multi-query slice. Additional 300B+30B scaling at 2.67B and 64K ProLong continual pretraining confirm that PISA matches or surpasses Full Attention on language modeling and extraction while matching NSA's long-range retrieval at much higher training throughput and lower memory; budget sweeps further show that half-budget PISA surpasses double-budget NSA on multi-query retrieval.
  • Short-context preservation, non-CPT verification, and significance [Reviewer sC3r]. Auditing checkpoints before and after 16K continual pretraining confirms that short-context retrieval and standard language-modeling benchmarks consistently improve rather than degrade under our document-boundary masking and conservative learning-rate schedule. PISA's gains also hold without any continual pretraining (across all 4K pretraining scales, with or without FDA, and on frozen Qwen3-Base), and our closed-form RULER standard-error analysis together with consistent wins across three independent model scales confirms that the observed gains far exceed evaluation noise.

Detailed tables and derivations are provided in our reviewer-specific responses and follow-ups. We remain available to clarify any remaining questions. Thank you very much again for your time and thoughtful engagement.

Best regards,

The Authors of Submission 38207

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.