WorksComputer Science
Coarse Semantic Blocks for Efficient Training-Free Sparse Attention
Abstract
We introduce a training-free sparse attention method that builds a prompt-specific key index to accelerate both prefill and decoding. The method clusters the keys into large semantic blocks that group tokens from noncontiguous positions. Each query position selects blocks by scoring their centroids and attends to the original keys and values within them. Queries that select the same block are processed together, so prefill stays fast even though each query chooses its own blocks. Large blocks make centroid scoring and this grouped processing cheap, so each query can attend to more tokens in the same time. Larger blocks with a larger token budget can thus be both faster and more accurate on long-context tasks than smaller blocks with a smaller budget. We evaluate two hybrid LLMs, Qwen3.5-4B and 35B-A3B, on one NVIDIA H200. Including the cost of building and using the index, whole-model wall-clock speedups over dense attention are 2.3-2.4x for prefill and 1.7-2.0x for decoding at 512K tokens, and 2.9-3.0x for prefill at 1M. The 35B-A3B model stays close to dense attention on five RULER tasks through 1M, on LongBench-v2 overall, and on MRCR through 256K. The 4B model loses accuracy mainly on multi-key retrieval, yet outperforms dense Qwen3.5-2B, whose latency is similar at 512K, on all three benchmarks.
Introduction
Long contexts make attention expensive during both prefill and decoding. Sparse attention restricts each query to a subset of tokens, but it is faster only if choosing the tokens and preparing their keys and values costs less than the attention computation it saves. Methods with learned indexers, such as DSA [5], MSA [19], and QSA [32], train the indexer and the model so that a small token budget suffices. For training-free methods, estimating token importance separately for each query during prefill is costly, and irregular selections are difficult to execute efficiently on GPUs [28]. Existing methods therefore select contiguous blocks [37], whose tokens are often unrelated to one another, or share one selection across neighboring queries [15, 18, 16, 8]. Other methods cluster similar keys during dense prefill and use the resulting index only for decoding (Liu et al., 2025b; Zhu et al., 2026).
We show that, without training, a sparse prefill in which each query selects its own blocks can still run much faster than dense attention. Our method clusters the keys of each input prompt into large semantic blocks, groups of tokens with similar keys regardless of their positions in the sequence. Each query scores the cluster centroids and attends to the original keys and values of the blocks it selects. Unlike contiguous blocks, a semantic block gathers tokens that a query is likely to need together. We use the same index for both the prompt’s own prefill and decoding.
Scoring one centroid per block makes selection cheaper than scoring every key individually. During prefill, queries that select the same block are processed together for that block, as in the KV-outer execution of MoBA and MSA [25, 19]. This lets the GPU reuse KV data in on-chip memory across queries while preserving each query’s own block selection. Larger blocks make centroid scoring and block-wise attention cheaper but token selection less precise. The
Code: https://github.com/pfnet-research/semantic-block-sparse-attention/ time saved leaves room for a larger token budget, which can compensate for the coarser selection (§ 5.3).
We evaluate on hybrid models, which use full attention in only some layers and are increasingly common among top-tier LLMs ([27, 33, 11]). On Qwen3.5-4B and 35B-A3B, whole-model prefill is 2.3–2.4 faster and decoding 1.7–2.0 faster than dense attention at 512K tokens, and prefill is 2.9–3.0 faster at 1M, with index construction included and dense attention run on the same inference stack (Figure 1). The 35B-A3B model stays close to dense attention on five RULER tasks (Hsieh et al. [13]) through 1M, on LongBench-v2 (Bai et al. [3]) overall, and on MRCR (OpenAI [30]) through 256K. The 4B model, which loses accuracy mainly on the multi-key tasks in RULER, still outperforms dense Qwen3.5-2B, whose latency is similar at 512K (Table 1).
Figure 1. Prefill and decode latency on one H200 with a token budget of for a prompt of tokens. Whole-model latency is measured by wall clock, and full-attention layers (shaded) by GPU time. The rows are Qwen3.5-4B (top) and 35B-A3B (bottom). Dense (2B) is Qwen3.5-2B. Speedups are over dense attention (Table 13 and Table 31).
| RULER-5 | MRCR-8 | LongBench-v2 | Prefill (s) | |||||||
| 256K | 512K | 1M | 128K | 256K | 512K | ≤256K | >256K | all | 1M | |
| 35B-A3B, dense | 85.7 | 84.4 | 73.2 | 0.846 | 0.655 | 0.564 | 64.4 | 66.2 | 64.7 | 173.5 |
| 35B-A3B, ours | 84.5 | 84.2 | 73.9 | 0.844 | 0.668 | 0.504 | 63.1 | 64.7 | 63.3 | 57.4 |
| 4B, dense | 84.7 | 82.8 | 63.2 | 0.797 | 0.574 | 0.412 | 54.3 | 64.2 | 55.7 | 144.1 |
| 4B, ours | 82.7 | 81.8 | 55.2 | 0.788 | 0.561 | 0.399 | 53.9 | 57.7 | 54.5 | 49.3 |
| 2B, dense | 77.7 | 66.5 | 48.9 | 0.726 | 0.414 | 0.198 | 36.7 | 34.3 | 36.4 | 56.2 |
Table 1. Long-context performance at , with the upper bound of the length bin for MRCR-8 and of the length band for LongBench-v2, and whole-model prefill latency at 1M. MRCR-8 reports a match ratio, and the other quality scores are percentages. At 1M, the multi-value prompts of RULER-5 are about 647K tokens long (Appendix § 10.§ 3). Appendix § 13.§ 3 gives other budgets.
Related work
Many sparse attention methods first score individual tokens or blocks of consecutive tokens, then compute attention over the selected keys and values. DSA [5] and MSA (Lai et al. [19]) use learned indexers to score every visible token, with MSA pooling the resulting scores to select blocks. QSA reduces the number of candidates by pooling indexer keys into 4-token blocks before scoring (Qiu et al. [32]). NSA selects blocks by the attention that queries give to compressed block keys (Yuan et al. [45]). These systems train their selection together with the language model. DSA, MSA, and QSA perform well with selected-token budgets of 2,048.
Quest (Tang et al. [37]) and MoBA (Lu et al. [25]) select blocks of consecutive tokens using summaries of the model’s key cache. MoBA computes attention block by block, together for all queries that selected a block, as MSA also does (Lai et al. [19]). FlashMoBA speeds up this computation for small blocks (Xiao et al. [41]). Training-free prefill methods make selection cheaper with structured patterns and block-level estimates, as in Minference (Jiang et al. [15]). FlexPrefill’s query-aware pattern scores blocks using pooled queries and keys (Lai et al. [18]), while QuoK A uses representative queries to select a shared KV subset for a chunk (Jones et al. [16]). FlashPrefill and FlashPrefill V2 score mean-pooled key blocks for each tile of queries and keep the blocks above a threshold relative to the maximum score, the latter compensating the rest with their mean keys and values (Fan et al. [10]). Nawrot et al. [28] compare training-free methods using FLOPs for prefill and memory traffic for decoding rather than measured latency. They also note that fine-grained per-query selection during prefill is difficult to accelerate because importance estimation is costly and available kernels struggle with irregular sparsity.
Clustering groups tokens by key similarity rather than sequence position. Routing Transformer trains a model whose queries and keys are routed by spherical -means [34]. SAAP fits a key partition on a corpus and trains a query classifier to select clusters while keeping the language model frozen [26]. Squeezed Attention [12], ClusterKV [23], and Tactic (Zhu et al., 2026) use query–centroid scores without a learned classifier and attend to the selected original keys and values. Squeezed Attention indexes a reusable context offline, whereas ClusterKV and Tactic build prompt-specific clusters during dense prefill for subsequent sparse decoding. RetrievalAttention similarly searches a nearest-neighbor index of the keys during decoding [22]. Our method also builds its clusters for each prompt without training, but uses them for the prompt’s own prefill as well as its decoding. Its clusters are also much larger, 2,048 tokens in the main setting against tens of tokens in these methods, which makes centroid scoring and KV-outer attention cheap enough to afford a larger budget, with a separate selection for each query.
The inference-time methods above, which leave the language model unchanged, are evaluated in their own papers on Transformers in which every layer uses softmax attention Appendix § 16. UniPrefill, which skips token computation in attention and non-attention layers, measures several of the prefill methods on a linear-attention hybrid up to 128K tokens, where they speed up the time to first token by at most 1.11× [9]. Concurrent work on Qwen3.5 trains a selector and keeps the prefill dense [1]. When every layer uses softmax attention, most heads attend locally [39, 42], and turning 85% of them into sliding-window attention, with decode-time sparse token selection in the rest, loses little accuracy after a few hundred training steps [46]. In hybrids such as MiniMax-M1 [27] or Qwen3.5 [33], a quarter or fewer of the layers use full attention. These layers provide the model’s only exact access to distant tokens, so results on all-attention models do not show how much sparsity they can tolerate. They also account for only part of the model’s cost, so attention-layer speedups alone do not show the whole-model gain. We therefore report whole-model wall-clock latency and attention-layer GPU time separately, and break down the costs of indexing, selection, and attention execution.
Method
Our method groups prompt keys into semantic blocks, selects blocks for each query, and computes attention over the selected tokens (Figure 2). We choose the block size and token budget together to balance task accuracy and whole-model latency, including the cost of building and using the index. All model weights remain fixed, and no selector is trained.
Figure 2. Keys are clustered separately for each layer and KV head. The query heads that share a KV head score the centroids separately (), and the sum of their scores () selects the clusters. Each head attends to the original KV of the selected clusters, together with recent tokens , under a causal mask. Only positions at or before the query contribute to the attention sum.
We describe one full-attention layer and one KV head shared by a group of query heads under grouped-query attention (GQA) [2]. Let be the prompt length and the attention head dimension. We write for the key and value at position , and for the query at position in head . We omit layer and KV-head indices.
Building semantic blocks
Let and denote the keys and queries normalized to unit norm. For each prompt, layer, and KV head, we run spherical -means on a sample of the normalized keys to obtain unit-norm centroids . We assign each prompt key to its nearest centroid and define its block as
Each contains the positions of tokens assigned to cluster . We call these groups semantic blocks because they group similar keys regardless of their positions in the sequence. Figure 3 and Appendix J show tokens that the clustering places in the same block. A block can contain many different tokens. In the upper example, the members closest to the centroid are words about the environment from distant passages. In the lower example, they are the leading digits of different identifiers.
Figure 3. Examples of two clusters, with members of high and low cosine similarity to the centroid.
A target mean block size determines the cluster count approximately as (Appendix B gives the clustering details). Each layer and KV head has its own partition, and the members of a block are generally scattered across the prompt, so we store each block’s keys and values contiguously (Section 3.4).
Selecting blocks and computing attention
Prefill queries are processed in contiguous chunks. Each query attends to all causally visible tokens in its current chunk and selects clusters from the earlier history. During decoding, recent generated tokens are similarly included without selection. Let denote the positions included without selection for the query at position . The remaining visible positions in cluster are .
We compute softmax scores over centroids within each query head and sum them across the GQA group before selecting blocks. We also apply a size penalty to account for the number of tokens retrieved from each cluster,
We use temperature and size-penalty exponent . We select clusters in decreasing order of , taking all tokens in each until their total number reaches or exceeds the budget . Let be the clusters selected at position . The positions of the key–value pairs used for attention are
This selection is computed for each query position and shared by the query heads in its GQA group.
Attention is then computed over these positions using the model’s original queries, keys, and values1,
Setting recovers dense attention.
Prefill and decoding
During prefill, we build the index from the prompt keys at each layer and process the prompt queries in contiguous chunks. Each query attends to selected blocks from earlier chunks and to all causally visible tokens in its own chunk. For queries near the beginning of the prompt, the earlier history is short, so we avoid selection overhead by using dense attention over the whole visible prefix, setting (see Appendix § 9).
During decoding, each query uses the same index to select prompt blocks. In our main experiments, all generated tokens are included without selection in . For longer generations, older generated tokens can instead be added to the index, leaving only recent ones in (§ 5.5).
For simplicity, our main experiments run spherical -means on keys sampled from the whole prompt. Block selection for a prompt query can therefore depend on later prompt keys, although each query attends only to positions at or before it. This is possible because the whole prompt is given before generation starts, and every generated token still depends only on the tokens before it. Because the index is fitted to keys drawn from the whole prompt, prefill runs one layer at a time over the whole prompt, instead of passing chunks of the prompt through all layers as ordinary chunked prefill does (Appendices § 9.§ 4 and § 9.§ 5). Alternatively, running -means only on the first 64K keys and assigning each later key to its nearest centroid allows ordinary chunked prefill, with similar accuracy (§ 5.4 and Appendix § 9.§ 5).
Efficient execution
Efficient dense-attention kernels such as FlashAttention-3 (Shah et al. [35]) process neighboring queries together so that they can reuse each KV tile. In our method, however, neighboring queries can select different KV blocks. If they are still processed together, a block selected by one query may also be processed for queries that did not select it, reducing the savings from sparsity. We instead gather the queries that selected each KV block and compute their attention to that block together. MoBA and MSA use the same execution strategy for blocks of consecutive tokens (Lu et al. [25]; Lai et al. [19]).
For each prefill chunk and KV head, FlashAttention-3 processes a batch of KV blocks paired with their query groups. Attention within the current chunk uses causal FlashAttention-3. For each query, we combine the attention outputs using their softmax normalizers (Appendix § 9). Following MSA (Lai et al. [19]), we call this block-wise execution KV-outer. On Qwen3.5-4B at 512K, prefill with KV-outer is 2.6× faster than processing neighboring queries over their selected-block union (Appendix § 12.§ 4).
Although a block’s tokens may be scattered across the prompt, we store their KV contiguously in their original sequence order. For each prefill chunk, we can then read the KV of earlier tokens directly from the start of each block. We build this block-ordered cache once per layer and use it for both prefill and decoding. Without this layout, gathering the selected KV for every prefill chunk increases 512K prefill time by about 9% (Appendix § 12.§ 4).
During decoding, each step reads prompt KV from the selected blocks rather than the full prompt. This reduces the prompt tokens read per step from to roughly . Our vLLM implementation (Kwon et al. [17]) uses fused kernels to reduce the overhead of scoring and selecting blocks during decoding.
Each query scores centroids instead of the prompt’s keys. For a fixed prompt and token budget, smaller blocks give finer selection but require scoring more centroids and processing more blocks (Xiao et al. [41]). Larger blocks reduce this overhead, so we can increase the budget to compensate for coarser selection (§ 5.3). In our experiments, both and grow in proportion to , so prefill remains quadratic in prompt length, but with a smaller constant factor than dense attention. Appendix § 8 gives the cost of each step.
Experimental setup
Models and baselines. We evaluate Qwen3.5-4B and Qwen3.5-35B-A3B (Qwen Team [33]), replacing their full-attention layers (8 of 32 and 10 of 40) while keeping all weights fixed, and also apply the method to a hybrid of another family, Nemotron 3.5 Lightning [29]
(Appendix § 15.§ 2). Dense attention runs on the same vLLM build with chunked prefill, and dense Qwen3.5-2B serves as a smaller-model reference. As a controlled sparse baseline, we replace semantic blocks with positional blocks of consecutive tokens, each represented by its mean key. As in block-sparse prefill methods [15, 18, 8], neighboring queries can share one block selection to reduce its cost. It uses the same token budget, the same , and the same attention kernels as our method. This gives a controlled comparison with positional block selection and query sharing.
Benchmarks. We use RULER [13], eight-needle MRCR [30], and LongBench-v2 [3]. RULER-5 averages five RULER tasks, namely multi-key retrieval (MK-2 and MK-3), multi-value retrieval, common-word extraction, and HotpotQA. Most other tasks are too easy to separate the methods at 512K, and the 4B model’s average over all thirteen stays close to dense attention (Appendix § 11.§ 1). RULER and MRCR use about 100 examples per task and length, and LongBench-v2 uses the 470 of 503 examples that fit without truncation. RULER uses greedy decoding without thinking, while MRCR and LongBench-v2 use thinking with Qwen’s recommended sampling settings. We average our main results on all three benchmarks over three runs (Appendix § 10).
Settings. Both Qwen models use the same configuration, with target mean block size and budget for RULER and latency measurements. Most ablations use the 4B model. MRCR and LongBench-v2 have variable-length prompts, so we set budgets by length range. For MRCR, is one sixteenth of the bin’s upper length bound. For LongBench-v2, for prompts up to 256K and for longer prompts. The budget excludes the tokens attended without selection and may be exceeded by the last selected block. Beyond the native 256K context, dense and sparse runs both use factor-4 YaRN interpolation [31] without its attention scaling. This setting gave the best dense-attention accuracy in our tests (Appendix § 11.§ 2).
Results
Overall performance
We measure latency at batch size one on a single H200 in BF16, with FlashAttention-3 for prefill and full-step CUDA graphs for decoding in both methods, and report the median of three repetitions after warm-up (Appendix § 10). Prefill latency includes index construction, KV packing, selection, gathering, and merging. On Qwen3.5-4B and 35B-A3B, whole-model prefill is 2.3–2.4× faster and decoding 1.7–2.0× faster than with dense attention at 512K (Figure 1). The gains grow with context length, reaching 2.9–3.0× for prefill and 2.3–2.9× for decoding at 1M. The full-attention layers themselves prefill 3.9–4.3× faster at these lengths, and the whole-model speedup is lower because the other layers are unchanged (Table 13 and Table 31).
| Prompt | Prefill (s) | Decode (ms/token) | ||||||
| Whole model | Attention layers (8) | Whole model | Attention layers (8) | |||||
| Dense | Ours | Dense | Ours | Dense | Ours | Dense | Ours | |
| 128K | 4.18 | 3.11 | 1.92 | 0.84 | 4.87 | 4.07 | 1.29 | 0.34 |
| 256K | 12.37 | 7.06 | 7.75 | 2.34 | 6.14 | 4.16 | 2.41 | 0.43 |
| 512K | 40.69 | 17.39 | 31.81 | 8.18 | 8.69 | 4.41 | 5.00 | 0.66 |
| 1M | 144.08 | 49.30 | 125.47 | 29.79 | 13.93 | 4.84 | 10.51 | 1.03 |
| Reference, Qwen3.5-2B with dense attention, whole model | ||||||||
| 128K | 1.72 | – | – | – | 2.89 | – | – | – |
| 256K | 4.99 | – | – | – | 3.48 | – | – | – |
| 512K | 16.01 | – | – | – | 4.73 | – | – | – |
| 1M | 56.16 | – | – | – | 7.48 | – | – | – |
Table 13. Qwen3.5-4B latency on one H200. Whole-model columns are wall-clock measurements, the attention-layer columns profiler totals over the eight full-attention layers. The last rows are the dense reference model, Qwen3.5-2B.
| Prompt | Configuration | Whole model | Attention layers (10) | ||
| Prefill (s) | Decode (ms) | Prefill (s) | Decode (ms) | ||
| 128K | Dense | 4.75 | 5.72 | 2.41 | 0.92 |
| 128K | Ours | 3.31 | 4.91 | 0.96 | 0.30 |
| 256K | Dense | 14.77 | 6.64 | 9.58 | 1.56 |
| 256K | Ours | 7.76 | 4.98 | 2.69 | 0.37 |
| 512K | Dense | 49.19 | 8.68 | 39.25 | 2.98 |
| 512K | Ours | 20.73 | 5.15 | 9.68 | 0.54 |
| 1M | Dense | 173.49 | 12.87 | 156.24 | 6.14 |
| 1M | Ours | 57.42 | 5.71 | 36.38 | 0.84 |
| 512K | Ours, | 17.21 | 5.03 | – | – |
| 512K | Ours, | 15.21 | 4.96 | – | – |
Table 31. Qwen3.5-35B-A3B latency on one H200 at and , as Table 13. Whole-model columns are wall clock, the attention-layer columns profiler totals over the ten full-attention layers. The last rows halve and quarter the budget at 512K.
Figure 4 breaks down prefill time on Qwen3.5-4B at 512K. Our attention kernels run about 5× faster than dense attention. Index construction, selection, gathering, and merging together take about 1.8 s, of which fitting the centroids is a small part, compared with roughly 25 s saved in attention computation. The rest of the model is unchanged and takes about half of the sparse prefill time. use dense attention within query chunks and near the start of the prompt, so an budget does not give a attention speedup. We also tried switching from dense to sparse attention earlier in the prompt, but this did not speed up prefill. The extra selection, gathering, and merging offset the time saved on dense attention (Appendices § 12.§ 2 and § 12.§ 3).
Both models retain most of their dense-attention performance across the three benchmarks (Table 1). On the 35B-A3B model, RULER-5 remains close to dense attention through 1M. The 4B model loses more on multi-key retrieval, especially at 1M, while multi-value retrieval and HotpotQA remain close to dense attention across lengths (Appendix § 11.§ 1). MRCR-8 scores stay close to dense attention through 256K on both models and fall below it at 512K, more on the 35B-A3B model. Overall LongBench-v2 accuracy changes little on either model. A smaller dense model also reduces latency, but the sparse 4B model scores higher than dense Qwen3.5-2B on RULER-5 at every tested length, on MRCR-8, and on LongBench-v2, with similar prefill latency at 512K and lower latency at 1M (Table 1 and Appendix § 12). On Nemotron 3.5 Lightning, with its own clustering settings, multi-key accuracy falls further at , so we use . Whole-model prefill is then 1.5–2.0× faster than dense attention over prompts from 256K to 1M. At 512K, accuracy remains close to dense attention except on multi-key retrieval (Appendix § 15.§ 2).
Semantic blocks and per-query selection
We compare our method with positional block selection using the baseline in § 4. We vary the positional block size and the number of neighboring queries sharing a selection. For shared selection, we combine scores from all queries in the group to choose one set of blocks, following Fan et al. [8]. Sharing reduces cost but can miss blocks needed by individual queries. We tried averaging the queries before scoring, or taking the maximum query score for each block. Neither improved accuracy (Appendix § 13.§ 4).
Figure 5 compares these choices at the same token budget on multi-key retrieval, where the 4B model is most sensitive to sparsification. Large positional blocks are fast but retrieve poorly, and smaller ones improve accuracy at a higher execution cost, particularly with per-query selection. At , per-query positional selection is still less accurate than our method and more than slower to prefill. Sharing selections makes positional blocks faster, but the most accurate shared settings remain less accurate than our method and take 1.8–2.7× as long to prefill. On MK-2 the gap is wider, with every positional setting at least 25 points below our method. On Qwen3.5-35B-A3B, only one tested
Figure 5. MK-3 and MK-2 accuracy against prefill latency on Qwen3.5-4B at 512K, without and with an initial block of 1,024 positions. Numbers are the positional block size , and is the number of queries sharing one selection. Adding the initial block has little effect on prefill time (Appendix § 13.§ 4). We therefore reuse timings measured without it for per-query selection and shared semantic selection.
positional setting matches our MK-3 accuracy, but it takes 1.8 as long to prefill and scores 14 points lower on MK-2 (Appendix § 13.§ 4). As a reference point, we also ran FlashPrefill V2 with the SGLang implementation released with it, on the same prompts (Appendix § 13.§ 5). The two engines differ in implementation, but their dense attention runs at a similar speed and reaches a similar accuracy. We compare speedups relative to dense attention on each method’s own engine. Our method is more accurate at comparable speedups. Among the tested thresholds, FlashPrefill V2 reaches our MK-3 accuracy only with a 1.7 speedup, compared with 2.2 for ours.
We also test shared selection for semantic blocks, using groups of 64 neighboring queries as in MInference’s block-sparse pattern [15]. This sharply reduces MK-3 accuracy for only a small reduction in prefill time. Per-query selection of semantic blocks thus gives the best accuracy–latency trade-off among these configurations. At a fixed token budget, larger blocks mean fewer blocks per query, reducing the cost of gathering queries and merging outputs (§ 3.4). At 512K, each query scores 256 semantic centroids, compared with 16,384 block means for 32-token positional blocks.
We also test adding a fixed initial block of 1,024 positions, following the practice of including early prompt positions to retain attention sinks [40, 15]. This tends to improve both methods. Ours then matches the most accurate positional setting on MK-3 while prefilling 1.3 faster, and remains far more accurate on MK-2, also at the smaller budget (Figure 5, Table 23 and Appendix § 13.§ 4).
Table 23: Positional and semantic retrieval on Qwen3.5-4B at 512K, , MK-3 and MK-2 accuracy in percent with , without and with the fixed initial block of Appendix D.3. is positional block size and query sharing span. Min/max rows describe each positional block by its minimum and maximum keys, and their shared rows use the averaged query. Our per-token row is the mean over three clustering seeds. A dash denotes an unmeasured entry.
| Index | MK-3 (%), initial block Without | MK-3 (%), initial block With | MK-2 (%), initial block Without | MK-2 (%), initial block With | Prefill (s) | ||
| Positional, shared | 2,048 | 64 | 7 | 4 | – | – | 15.6 |
| 128 | 64 | 27 | 32 | – | – | 16.2 | |
| 32 | 64 | 51 | 64 | 24 | 24 | 18.4 | |
| 16 | 64 | 63 | 79 | 32 | 36 | 21.5 | |
| 8 | 64 | 77 | 92 | 51 | 53 | 27.5 | |
| 4 | 64 | 75 | 85 | – | – | 39.5 | |
| 32 | 32 | 64 | 78 | 35 | 38 | 19.1 | |
| 16 | 32 | 82 | 94 | 44 | 52 | 24.0 | |
| 8 | 32 | 84 | 93 | 58 | 64 | 32.9 | |
| 4 | 32 | 85 | 93 | 65 | 73 | 50.1 | |
| 32 | 16 | 78 | 85 | 51 | 54 | 23.8 | |
| Positional, per query | 2,048 | 1 | 10 | 9 | – | – | 16.1 |
| 128 | 1 | 49 | 51 | 34 | 37 | 33.1 | |
| 32 | 1 | 82 | 89 | 70 | 69 | 84.9 | |
| Min/max, shared | 2,048 | 64 | 6 | 6 | – | – | – |
| 32 | 64 | 24 | 21 | – | – | 18.7 | |
| 16 | 64 | 26 | 25 | – | – | – | |
| Min/max, per query | 32 | 1 | 44 | 44 | – | – | 87.7 |
| Ours, per query | – | 1 | 92.7 | 95.0 | 95.0 | 94.7 | 18.3 |
| Ours, shared | – | 64 | 26 | 21 | 11 | 18 | 16.4 |
| Dense | – | – | 96 | – | 99 | – | 40.7 |
Table 23.
Block size and token budget
On Qwen3.5-4B at 512K, smaller clusters are more accurate at small token budgets. As the budget grows, larger clusters reach similar accuracy while remaining faster (Figure 6; Appendix § 13.§ 2). Our main setting uses 2,048-token clusters at . We also analyze the attention mass retained by the selected tokens and test selection using dense-attention scores (Appendix § 14.§ 1).
Figure 6. Cluster size and token budget on MK-2 at 512K, Qwen3.5-4B. Larger clusters with a larger budget can improve both accuracy and latency over finer clusters with a smaller budget.
Figure 7 breaks down prefill GPU time by cluster size. At a fixed budget, reducing the cluster size from 2,048 to 512 tokens increases prefill GPU time by 41% on the 4B model. Most of the increase comes from attention over selected blocks, query gathering, and output merging. With 2,048-token clusters, attention over selected blocks reaches about 70% of the FLOP rate of dense FlashAttention-3 on the same GPU, compared with less than 40% with 512-token clusters. Kernels specialized for small blocks [41] could narrow this gap.
Figure 7. GPU time of one 512K prefill on Qwen3.5-4B by cluster size and token budget .
On Nemotron, smaller clusters give larger accuracy gains with a smaller runtime penalty. Reducing the cluster size from 2,048 to 512 tokens increases prefill GPU time by 27% (Figure 18). Clusters around 512 to 1,024 tokens work well on this model. Cluster size and token budget should therefore be chosen together for each model and its kernels.
Figure 18. GPU time of one 512K prefill on Nemotron 3.5 Lightning at by cluster size , drawn as Figure 7.
Prompt-specific clustering
Fitting centroids once on a shared corpus allows reuse across prompts, as in SAAP (Mazaré et al. [26]). We compare this approach with our prompt-specific fitting, keeping the selection rule unchanged (Table 2). Centroids fitted on a raw-text corpus lose almost all multi-key retrieval accuracy. Using RULER-5 evaluation prompts as the fitting corpus largely restores it, and fitting each prompt separately gives a further gain on MK-2 (Appendix § 13.§ 6).
| Centroids fitted on | MK-3 | MK-2 | Hotpot | CWE |
| Dense attention | 96.0 | 99.0 | 56.0 | 63.0 |
| Each prompt (ours) | 92.7 | 95.0 | 57.0 | 64.3 |
| Each prompt’s first 64K | 95.0 | 95.0 | 56.0 | 66.1 |
| A raw-text corpus | 1.0 | 12.0 | 51.0 | failed |
| RULER-5 examples | 91.0 | 90.0 | 55.0 | 64.6 |
Table 2. Centroid fitting data on Qwen3.5-4B at 512K ().
Fitting centroids on just the first 64K tokens of each prompt gives similar accuracy to using the whole prompt and allows ordinary chunked prefill with less memory (§ 3.3 and Appendix § 9.§ 5).
Decoding over long generations
In our main experiments, each decoding step attends to all generated tokens without selection. Decoding therefore slows as the output grows, which matters for the long reasoning traces in MRCR-8 and LongBench-v2 (blue in Figure 10; Appendix § 12.§ 5).
Figure 10. Decode latency of Qwen3.5-4B after a 512K prompt, index updates included.
We can instead add older generated tokens to the index by assigning them to the existing centroids without refitting. We update the index every 1,024 generated tokens and keep the newest 512 tokens outside it. Decode latency then stays nearly constant (orange in Figure 10), even over 64K generated tokens after a 1M-token prompt. LongBench-v2 accuracy changes little on either Qwen model (Appendices § 12.§ 5 and § 15.§ 1).
Limitations and future work
Our experiments use BF16 inference at batch size one on a single H200. Throughput under continuous batching and on other GPU architectures remains to be evaluated. The method retains the full prompt KV cache, so memory capacity still limits context length and batch size. Fitting centroids on the whole prompt raises peak memory above dense chunked prefill, but fitting them on the first 64K tokens allows chunked prefill with similar accuracy (Appendix § 9.§ 5). Our method can also be combined with other efficiency techniques, such as KV-cache quantization (Liu et al. [24]) and cache compression (Li et al. [21]), which reduce different costs.
Training the model for sparse attention, as in DSA (DeepSeek-AI [5]) and QSA (Qiu et al. [32]), may bring further gains. Our short distillation experiments did not consistently improve retrieval (Appendix § 14), but longer training on long-context task data may help preserve accuracy at smaller budgets.
Conclusion
We presented a simple but effective training-free sparse attention method that builds semantic blocks from each prompt and uses them for both prefill and decoding. Centroid scoring keeps selection cheap, while KV-outer execution makes prefill efficient with a separate selection for each query. This addresses the selection and execution costs discussed by Nawrot et al. [28]. The resulting savings allow a larger token budget and yield whole-model speedups on two hybrid LLMs.
Acknowledgments
We thank the National Institute of Information and Communications Technology (NICT) for the opportunity to conduct this research under our joint research framework.
Computational cost
We consider a layer with KV heads, each shared by a group of query heads, so it has query heads. The prompt has tokens, queries and keys have dimension , and each KV head has semantic blocks. Dense attention costs per generated token and over a prefill. Table 14 reports the measured GPU time of each stage.
| Dense | Ours | |
| Attention (8 attention layers) | 31.4 | 6.4 |
| selected blocks | 4.02 | |
| dense prefix | 2.02 | |
| current chunk | 0.34 | |
| Scoring, selection, index build (ours) | 0.0 | 0.3 |
| score the centroids and select | 0.24 | |
| -means fit | 0.02 | |
| index build | 0.02 | |
| Gather, merge and other overhead (ours) | 0.0 | 1.5 |
| gather and index operations | 0.72 | |
| merge of partial outputs | 0.38 | |
| masks, casts and copies | 0.38 | |
| Linear projections (all 32 layers) | 6.4 | 6.4 |
| Linear-attention layers (24 GDN) | 1.6 | 1.8 |
| Norms, activations, RoPE | 0.7 | 0.7 |
| Other | 0.1 | 0.0 |
| Total | 40.3 | 17.1 |
Table 14. GPU time in seconds for a 512K prefill on Qwen3.5-4B. The attention rows contain only FlashAttention-3 kernels, with scoring, selection, gathering, and merging reported separately. Totals come from profiling rather than the wall-clock medians in Table 13.
Building the index. The index is built once per layer and prompt. With a fixed number of -means iterations, fitting the centroids and assigning all prompt keys cost . Normalizing the keys and packing the KV into block order each cost . Appendix § 9 gives the clustering settings.
Scoring and selection. Scoring centroids in each query head costs per query position and over a prefill. Selection runs once per KV head and uses a fixed number of threshold-refinement passes, costing per position. Per-token indexers such as DSA [5] and MSA [19] instead score all visible tokens, so their scoring remains quadratic over a prefill even with a small attention budget.
Attention. For each KV head, attention at position costs , where is the set of positions read by that query (§ 3.2). Summing this cost over query positions and KV heads gives the full prefill cost. The set includes selected blocks and positions read without selection, such as the current chunk during prefill or generated tokens during decoding. Selecting whole blocks can exceed the budget , and the initial dense queries read their full visible prefix. Including all generated tokens makes decode cost grow with generation length.
Growth with prompt length. Our main configuration keeps the target mean block size fixed, so that , and uses . Prefill therefore remains quadratic in prompt length. More generally, prefill can become subquadratic if both and the average number of positions read per query grow sublinearly with .
Memory. The index stores centroid values and block assignments. Prompt KV is stored once, in block order. Appendix § 9.§ 5 reports peak memory, including temporary activations and kernel workspace.
Implementation details
Routing and clustering
Clustering and selection use the pre-RoPE queries and keys of each head, 256-dimensional vectors normalized as whole vectors. Each KV head has a separate prompt partition. For a target mean block size , the number of clusters is . Table 3 lists the resulting cluster counts at . At 128K, , so and the mean block size is 1,024, half the target. Centroids start from uniformly sampled keys and are refined for eight iterations on the sample in the table, with empty clusters re-seeded from it. All prompt keys are assigned after fitting.
| Prompt length | Clusters | Mean block size | Keys used to fit |
| 128K | 128 | 1,024 | 8,192 |
| 256K | 128 | 2,048 | 8,192 |
| 512K | 256 | 2,048 | 8,192 |
| 1M | 512 | 2,046 | 16,384 |
Table 3. Clustering per KV head at , at the four prompt lengths we report.
In the fit-budget sweep, the sample count ranges from 2,048 to all prompt keys and the iteration count from two to sixteen. MK-3 accuracy at 512K ranges from 90% to 96% over 100 items, while prefill latency varies by at most six percent.
For the PCA ablation, we fit a projection using about one million raw-corpus keys per layer and KV head, without subtracting their mean. We apply the same projection to queries and keys, then normalize each vector.
Selection and attention
The prefill selector uses 16 threshold-refinement steps to approximate the score-ordered budget selection in Equation (3). Its size penalty uses the visible block sizes of Equation (2), and blocks with no visible token are never selected. The selected clusters are represented by a bitmap per query and KV head. Counts and prefix sums convert this to cluster-major query lists and query-major merge slots, without materializing the full Boolean selection matrix or sorting partial outputs afterward. Within each block of this cache, tokens stay in position order, and every block starts at a page boundary. Each prefill chunk passes the exact count of preceding tokens in every cluster to FlashAttention-3, including a partially filled final page. The selected history is therefore entirely before the chunk, and only the separate current-chunk call needs a triangular causal mask. The GQA heads are folded into query rows for the history call.
Partial attention outputs are merged using their softmax normalizers. If region returns output and log-sum-exp , the combined output is with . The merge is computed in FP32 and cast back to BF16, giving attention over the selected positions up to floating-point rounding.
The decode backend of the latency runs uses five launches per sparse layer, namely suffix write, query normalization, fused scoring and selection, split attention, and output merge. Selection directly emits contiguous cluster ranges. The attention kernel reads selected prompt ranges and the tiles of the generated suffix in the same launch, then merges their softmax statistics. All live lengths are read on device and workspace is reused, avoiding per-step host reads and allocations. The RULER and MRCR-8 runs and the 4B model’s LongBench-v2 runs in Table 1 use a fused decode backend with more launches per layer, which selects the same clusters, under vLLM’s piecewise CUDA graphs.
Compilation and decode graphs
Measurements use TORCHINDUCTOR_DETERMINISTIC=1, with combo kernels and their benchmarking disabled. These settings reduce numerical differences between independent compilations. Prefill uses piecewise graphs where applicable. For the main decode latency results, both methods use vLLM’s FULL_DECODE_ONLY mode, which captures the whole decode step as one CUDA graph. Each sparse layer has a fixed-address arena containing prompt KV, centroids, posting lists, generated-token storage, and workspace. The graph is captured at engine warm-up and reused after the prompt’s index is copied into the arena. One-time graph capture is excluded from steady decode latency for both methods.
Prefill schedules
An index fitted on the whole prompt needs all of a layer’s prompt keys before that layer’s queries can be routed. The runtime therefore cannot use ordinary chunked prefill, which passes one token chunk through all layers before the next chunk. Instead, every layer processes the whole prompt before the next layer starts, in one of two ways (Figure 8). Single-pass prefill runs the whole prompt through the model as one forward pass, so every projection and feed-forward call processes all prompt positions at once and holds full-length activations. Sliced prefill loops over the layers itself instead of calling the model’s forward pass once, and processes each layer in slices of 32,768 positions. A full-attention layer makes two passes over the slices. The first projects the keys and values for all slices, then builds the index and packs the block-ordered KV cache. The second projects the queries and the output gate, performs attention, and writes the outputs. Linear-attention layers carry their recurrent and convolution states between slices, and feed-forward layers and normalization are sliced as well. Both schedules compute the same attention up to numerical differences, with selection and attention in 8,192-position query chunks inside each layer, and differ in peak memory (Table 5). Sliced prefill is required where single-pass prefill exceeds device memory, and Table 4 lists which schedule each measurement uses. The schedule is selected outside the compiled decode path, and elementwise operators are compiled separately for the sliced path.
| Quantity | Value |
| Replaced layers | Eight full-attention layers of 32 |
| Query / KV heads | 16 / 4, head dimension 256 |
| Routing | Pre-RoPE Q/K, whole-vector normalization, identity map |
| Target mean block size | , which sets the cluster count of Table 3 |
| Clustering | Eight iterations, sampled keys. The main RULER results average seeds 0–2, and other results use seed 0 unless stated otherwise (Appendix § 10.§ 4) |
| Score parameters | , |
| Length-controlled budget | for RULER and the main latency sweep |
| Query chunk | 8,192 positions |
| Dense prefix | A query chunk starting at position (four times the budget) or earlier attends to its whole prefix without selection |
| Attended without selection () | The visible part of the current chunk in prefill, every generated token in decoding |
| Numerics | BF16 attention, FP32 score aggregation and output merge |
| Short prompts | Sparse attention at every measured length, with the runtime’s dense fallback for short prompts switched off |
| Decode graph | The whole decode step captured as one CUDA graph in the latency runs, for dense and ours |
| Prefill schedule | Sliced (32,768-position slices) at 1M, for the task evaluations above 256K, and for the main RULER-5 evaluations at every length (Appendix § 9.§ 4). Single-pass for the latency sweep through 512K and the other task evaluations through 256K |
Table 4. Main Qwen3.5-4B runtime parameters. Benchmark-specific budgets are described in § 4.

Figure 8. The order of operations in one prefill, shown for a full-attention layer and its feed-forward block, where “all” is every prompt position. Linear-attention layers follow the same order without the index.
| Method | Length / schedule | Weights | KV cache etc. | Transient | Total |
| Dense (derived) | 512K / chunked | 8.35 | 16.00 | 1.58 | 25.93 |
| Ours (measured) | 512K / single-pass | 8.35 | 20.84 | 53.50 | 82.69 |
| Ours (measured) | 512K / sliced | 8.35 | 20.84 | 11.91 | 41.09 |
| Ours, prefix index (measured) | 512K / chunked | 8.35 | 20.86 | 6.43 | 35.64 |
| Dense (derived) | 1M / chunked | 8.35 | 31.97 | 1.58 | 41.90 |
| Ours (measured) | 1M / sliced | 8.35 | 39.65 | 22.37 | 70.37 |
| Ours, prefix index (measured) | 1M / chunked | 8.35 | 39.72 | 11.89 | 59.96 |
Table 5. Qwen3.5-4B memory on one H200, in GiB. Dense totals are derived request-sized estimates that exclude excess preallocated cache capacity, while sparse peaks are measured allocated memory, so dense and sparse rows are accounted differently.
Memory
In the memory and latency runs, prompt KV is stored only in the block-ordered cache, with space reserved for generated tokens and workspace. The 4B model’s single-pass RULER runs at 128K and 256K also write prompt KV to vLLM’s paged cache. Table 5 compares memory use with dense chunked prefill. For our method, “KV cache etc.” is the allocated memory remaining after prefill, excluding weights. “Transient” is the additional allocation at the peak.
The additional memory over dense chunked prefill has two sources. The sliced schedule of Appendix B holds the residual stream for the whole prompt and, until a layer’s index is built, that layer’s keys and values, which grow with prompt length. The KV-outer attention of Section 3.4 holds, for one query chunk and KV head at a time, the gathered queries and their partial outputs, which grow with the query chunk and the number of blocks its queries selected. The 512K latency runs use single-pass prefill, whose peak is listed separately and is set by the full-length feed-forward intermediates. Both methods fit on one H200 at every length measured. Sparsity does not reduce memory here, because the full prompt KV is kept.
The prefix-index rows fit centroids on the prompt’s first 64K tokens and assign later keys to them as they arrive. This allows ordinary chunked prefill with 8K-token chunks and no full-length activations. The remaining memory overhead comes from the output buffer and the attention kernels’ per-chunk buffers. This schedule is about a sixth slower than sliced prefill. The first-64K partition gives similar accuracy to the full-prompt partition on the four RULER tasks in Table 2. Running chunked prefill with this index gives 93.0 on MK-3 at 512K, compared with 95.0 for the first-64K row in Table 2. The reported results use the full-prompt index.
Measurement protocol
Latency
All headline latency measurements use one request on one H200 and BF16 weights. Both methods use FlashAttention-3 for prefill, and our decoding uses the fused backend of Appendix § 9. Each latency measurement uses one warm-up followed by three measured repetitions. Each request generates 64 tokens for prompts through 512K and 32 tokens at 1M. For each repetition, decode latency is the time between the first and last generated tokens divided by the number of tokens after the first. We report the median over the three repetitions. For the 4B model, our method is timed on two different prompts of each length through 512K and on one prompt at 1M. Dense attention is timed on two prompts at 512K and on one prompt at 128K, 256K, and 1M. Where there are two prompts, we report their mean. The 35B-A3B model is timed on one prompt at every length under the same protocol. Both decode paths use full-step CUDA graphs. We measure our method’s latency using single-pass prefill through 512K on the 4B model and through 256K on the 35B-A3B model, with sliced prefill at longer lengths. The dense baseline uses vLLM’s chunked prefill. Layer timings sum kernels attributed to the attention backend, with decode accounting over the final 32 generated steps. They are profiler totals, not whole-model wall-clock measurements.
Quality
RULER uses 100 cached prompts per task and length, shared by the two Qwen models, with greedy decoding and thinking disabled. On the 4B model, our main RULER-5 evaluations and all task evaluations above 256K use sliced prefill (Table 4). All sparse task evaluations of the 35B-A3B model use sliced prefill.
MRCR-8 uses revision f4c69fa (8 December 2025) and the model’s thinking sampling preset. We keep the official length-bin boundaries and assign prompts using their length in Qwen3.5 tokens after the chat template. The bins contain 100 items at 128K and 512K and 99 at 256K. The generation limit accommodates the longest answer and a 32,768-token thinking budget.
LongBench-v2 retains 470 items whose raw prompts fit within 983,040 tokens. Thinking is enabled, with at most 40,960 generated tokens. Sampling uses temperature 1.0, top- 0.95, top- 20, min- 0, and presence penalty 1.5.
The main MRCR-8 and LongBench-v2 results average three runs, each with its own sampling seed and, for our method, its own clustering seed. Budgets are defined in § 4.
Prompt lengths
The prompts come from lm_eval’s port of the RULER generator, with NVIDIA’s filling for common-word extraction beyond 128K, where the port’s word list runs out. The measured median RULER-5 prompt lengths are within five percent of nominal at 128K and two percent from 256K onward, except multi-value retrieval at 1M, whose generator runs out of material at about 647K tokens. Of the other tasks at 512K, frequent-word extraction is the one the generator sizes by words rather than tokens, and its prompts run from 418K to 505K tokens with a median of 476K. The budget follows the nominal length. SQuAD QA is not in RULER-5 because filling it repeats the answer paragraph, about two and a half times at 512K and five times at 1M, so raising the nominal length also changes how often the answer appears.
Clustering seeds and seeding
For both Qwen models, the main RULER-5 results average three clustering seeds with random initialization (Table 7 and Table 9). Appendix comparisons use seed 0 unless stated otherwise. When the main configuration is rerun alongside variants, we report its score from that run, which can differ across tables because the fitted partition changes. When it is included only as a reference, we use its three-seed mean.
| Prompt | MK-3 | MK-2 | MV | CWE | HotpotQA | RULER-5 |
| 128K | 100.0 (0.0) | 98.7 (1.5) | 99.8 (0.3) | 78.3 (0.5) | 57.3 (1.2) | 86.8 (0.3) |
| 256K | 97.7 (0.6) | 91.0 (2.0) | 99.3 (0.4) | 70.3 (1.4) | 55.0 (1.0) | 82.7 (0.1) |
| 512K | 92.7 (0.6) | 95.0 (1.0) | 100.0 (0.0) | 64.3 (0.9) | 57.0 (1.0) | 81.8 (0.5) |
| 1M | 28.3 (1.5) | 68.0 (2.0) | 100.0 (0.0) | 29.4 (1.2) | 50.0 (1.0) | 55.2 (0.8) |
Table 7. RULER results of our method in the main table, Qwen3.5-4B at and , 100 items per task and length. Each entry is the mean (sample s.d.) over three clustering seeds. RULER-5 is the mean over the five tasks, and its s.d. is computed over the three seeds’ five-task means.
Table 9: RULER-5 by task and length on the three models, in percent, on 100 examples per task at . For the Qwen models, the ours rows are means over three clustering seeds, and the 35B-A3B model also has multi-key rows at half and a quarter of the budget at 512K. Nemotron is measured at 512K with one seed, and its last row doubles the budget. Common-word extraction beyond 128K is on the filled prompts, and the 1M multi-value prompts are about 647K tokens long (Appendix § 10.§ 3).
| Prompt | Method | Multi-key-3 | Multi-key-2 | Multi-value | Common-word | HotpotQA | Mean | |
| Qwen3.5-4B | ||||||||
| 128K | 8,192 | Dense | 100.0 | 100.0 | 100.0 | 78.7 | 58.0 | 87.3 |
| Ours | 100.0 | 98.7 | 99.8 | 78.3 | 57.3 | 86.8 | ||
| 2B dense | 100.0 | 100.0 | 99.8 | 77.8 | 52.0 | 85.9 | ||
| 256K | 16,384 | Dense | 100.0 | 100.0 | 100.0 | 68.3 | 55.0 | 84.7 |
| Ours | 97.7 | 91.0 | 99.3 | 70.3 | 55.0 | 82.7 | ||
| 2B dense | 97.0 | 99.0 | 100.0 | 46.7 | 46.0 | 77.7 | ||
| 512K | 32,768 | Dense | 96.0 | 99.0 | 100.0 | 63.0 | 56.0 | 82.8 |
| Ours | 92.7 | 95.0 | 100.0 | 64.3 | 57.0 | 81.8 | ||
| 2B dense | 70.0 | 98.0 | 98.2 | 19.1 | 47.0 | 66.5 | ||
| 1M | 65,536 | Dense | 40.0 | 89.0 | 100.0 | 35.1 | 52.0 | 63.2 |
| Ours | 28.3 | 68.0 | 100.0 | 29.4 | 50.0 | 55.2 | ||
| 2B dense | 20.0 | 89.0 | 98.0 | 8.3 | 29.0 | 48.9 | ||
| Qwen3.5-35B-A3B | ||||||||
| 128K | 8,192 | Dense | 100.0 | 100.0 | 100.0 | 79.7 | 63.0 | 88.5 |
| Ours | 98.7 | 100.0 | 99.0 | 82.2 | 63.7 | 88.7 | ||
| 256K | 16,384 | Dense | 100.0 | 99.0 | 100.0 | 69.5 | 60.0 | 85.7 |
| Ours | 96.3 | 99.0 | 99.4 | 68.6 | 59.3 | 84.5 | ||
| 512K | 32,768 | Dense | 100.0 | 97.0 | 100.0 | 68.0 | 57.0 | 84.4 |
| Ours | 98.7 | 97.7 | 98.8 | 67.2 | 58.7 | 84.2 | ||
| 16,384 | Ours, | 80.0 | 96.0 | – | – | – | – | |
| 8,192 | Ours, | 25.0 | 68.0 | – | – | – | – | |
| 1M | 65,536 | Dense | 85.0 | 85.0 | 100.0 | 48.2 | 48.0 | 73.2 |
| Ours | 79.3 | 88.7 | 100.0 | 44.9 | 56.7 | 73.9 | ||
| Nemotron 3.5 Lightning | ||||||||
| 512K | 32,768 | Dense | 100.0 | 99.0 | 100.0 | 95.7 | 61.0 | 91.1 |
| Ours | 84.0 | 49.0 | 71.5 | 92.4 | 53.0 | 70.0 | ||
| 65,536 | Ours, | 90.0 | 81.0 | 95.5 | 95.1 | 56.0 | 83.5 |
Table 9.
Random initialization draws from a sample of 8,192 keys, and -means++ uses sampling on the same sample. Greedy farthest-point seeding uses 65,536 keys for Qwen seed 0 and 262,144 for seeds 1 and 2, and 1,024 keys per centroid on Nemotron. Neither alternative gives a consistent improvement (Table 6), so we retain random initialization.
| Model | Task | Length | Seeding | Mean (s.d.) |
| Qwen3.5-4B | MK-2 | 512K | random | 95.0 (1.0) |
| Qwen3.5-4B | MK-2 | 512K | farthest | 92.7 (1.5) |
| Qwen3.5-4B | MK-2 | 512K | -means++ | 91.7 (1.5) |
| Qwen3.5-4B | MK-3 | 512K | random | 92.7 (0.6) |
| Qwen3.5-4B | MK-3 | 512K | farthest | 94.3 (1.5) |
| Qwen3.5-4B | MK-3 | 512K | -means++ | 92.0 (3.6) |
| Nemotron 3.5 | MK-3 | 256K | random | 73 (1 seed) |
| Nemotron 3.5 | MK-3 | 256K | farthest | 86 (1 seed) |
| Nemotron 3.5 | MK-3 | 512K | random | 84 (1 seed) |
| Nemotron 3.5 | MK-3 | 512K | farthest | 80 (1 seed) |
Table 6. The clustering seed and the seeding procedure, with RULER multi-key accuracy in percent at and , 100 items per task and length.
Across three seeds on the same 512K items, MK-3 accuracy varies by one point and MK-2 by two, while up to 8% of the items in either task change between correct and incorrect.
Quality in detail
RULER results by task
On Qwen3.5-4B at 512K, our mean accuracy over all thirteen RULER tasks remains close to dense attention (Table 8). The largest losses occur on multi-key retrieval, where MK-2 identifies needles by words and MK-3 by UUIDs. Halving the budget to further reduces multi-key accuracy, with smaller drops on frequent-word extraction and the two QA tasks. Most tasks outside RULER-5 are near ceiling. RULER-5 focuses on the harder tasks and includes multi-value retrieval to check recovery of multiple answers.
Table 8: Every RULER task on Qwen3.5-4B at a nominal 512K, in percent, 100 items per task, except the last row, which halves it. Ours on the starred tasks and SQuAD is the mean over three clustering seeds, on the others one seed. The second row is the median length of each task’s prompts in thousands of tokens (Appendix C.3). S1–S3 are the single-needle tasks, MK-1 to MK-3 multi-key, MQ multi-query, MV multi-value, VT variable tracking, CWE and FWE common- and frequent-word extraction, SQuAD the QA task with its paragraphs repeated, and Hotpot HotpotQA. The starred tasks form RULER-5.
| S1 | S2 | S3 | MK-1 | MK-2* | MK-3* | MQ | MV* | VT | CWE* | FWE | SQuAD | Hotpot* | Mean | |
| Prompt (K tokens) | 524 | 524 | 524 | 524 | 524 | 523 | 524 | 524 | 524 | 523 | 476 | 523 | 517 | |
| Dense | 100.0 | 100.0 | 100.0 | 100.0 | 99.0 | 96.0 | 99.8 | 100.0 | 100.0 | 63.0 | 99.3 | 76.1 | 56.0 | 91.5 |
| Ours | 100.0 | 100.0 | 99.0 | 100.0 | 95.0 | 92.7 | 100.0 | 100.0 | 100.0 | 64.3 | 99.0 | 79.1 | 57.0 | 91.2 |
| Ours, | 100.0 | 100.0 | 99.0 | 99.0 | 76.7 | 82.7 | 99.5 | 99.5 | 100.0 | 63.2 | 93.7 | 74.3 | 52.0 | 87.7 |
Table 8.
The italic rows under the 4B model are the dense Qwen3.5-2B model on the same items, a reference for how much a smaller dense model loses. On Qwen3.5-4B, sparsification reduces accuracy most on the two multi-key tasks from 256K onward, especially MK-2 (Table 9). HotpotQA and common-word extraction remain close to dense attention through 512K. Both fall a few points below dense attention at 1M.
Positional scaling beyond the native context
YaRN changes position interpolation and attention scaling (Peng et al., [31]). We set YaRN’s attention factor to , with ( at ). The runtime multiplies the rotary cosine and sine tables by , which cancels the attention scaling while retaining interpolation. Table 10 compares these settings on matched 512K prompts on the 4B model. The 35B-A3B model uses the chosen setting without a sweep of its own. Unless stated otherwise, the interpolation factor is four.
Table 10: Qwen3.5-4B and Qwen3.5-2B under alternative context-extension settings at 512K, with multi-key and multi-value accuracy in percent, per task, one clustering seed. Unqualified YaRN rows use factor four, and interpolation-only cancels attention-temperature scaling.
| Configuration | MK-3 | MK-2 | MV |
| Dense, no extension | 56.0 | 91.0 | 98.8 |
| Dense, YaRN | 89.0 | 94.0 | 99.5 |
| Dense, YaRN | 74.0 | 95.0 | 100.0 |
| Dense, , interp only | 77.0 | 98.0 | 100.0 |
| Dense, interpolation only | 96.0 | 99.0 | 100.0 |
| Ours, no extension | 46.0 | 66.0 | 99.8 |
| Ours, YaRN | 83.0 | 81.0 | 99.0 |
| Ours, interpolation only | 94.0 | 93.0 | 100.0 |
| Qwen3.5-2B dense, YaRN | 44.0 | 87.0 | 95.8 |
| Qwen3.5-2B dense, interpolation only | 70.0 | 98.0 | 98.3 |
Table 10.
We chose the setting using dense attention’s five-task mean, with QA and common-word extraction evaluated on the port’s capped prompts (Appendix C.3). It also gives the best multi-key scores in Table 10. The bold dense row is the main table’s dense measurement, while the bold sparse row is an earlier single-seed run of the main configuration. Removing the extra attention scaling improves both dense and sparse attention on the 4B model. The dense Qwen3.5-2B reference also performs best with this setting and uses it throughout.
Our method with a fixed initial block
We test a fixed block of the first 1,024 prompt positions to retain attention sinks, as in other sparse attention methods (Xiao et al., [40]; Jiang et al., [15]). These positions are excluded from clustering, and every query includes the fixed block in both prefill and decoding. The block counts toward , leaving the remaining budget for clusters. All other settings follow the main configuration, which omits this block. Section 5.2 applies the same block to the positional baseline (Table 23).
Tables 11 and 12 compare our method with and without the initial block on the same items. On Qwen3.5-4B, the block recovers most of the 512K MK-3 loss, changes MK-2 little, and slightly improves RULER-5 across lengths. RULER changes are small on Qwen3.5-35B-A3B. On Nemotron 3.5 Lightning, it improves multi-value retrieval but lowers MK-2 accuracy. Aggregate LongBench-v2 accuracy rises slightly on both Qwen models. At 512K, MCRK-8 improves on the 4B model and declines on the 35B-A3B model.
All rows use except the Nemotron rows at . Common-word extraction beyond 128K is on the filled prompts (Appendix § 10.§ 3).
| Method | 128K | 256K | 512K | 1M | MK-3 | MK-2 | MV | CWE | HotpotQA |
| Qwen3.5-4B | |||||||||
| Dense | 87.3 | 84.7 | 82.8 | 63.2 | 96.0 | 99.0 | 100.0 | 63.0 | 56.0 |
| Ours | 86.8 | 82.7 | 81.8 | 55.2 | 92.7 | 95.0 | 100.0 | 64.3 | 57.0 |
| Ours with initial block | 87.0 | 83.6 | 82.5 | 56.6 | 95.0 | 94.7 | 99.2 | 66.2 | 57.3 |
| Qwen3.5-35B-A3B | |||||||||
| Dense | 88.5 | 85.7 | 84.4 | 73.2 | 100.0 | 97.0 | 100.0 | 68.0 | 57.0 |
| Ours | 88.7 | 84.5 | 84.2 | 73.9 | 98.7 | 97.7 | 98.8 | 67.2 | 58.7 |
| Ours with initial block | 88.6 | 84.5 | 84.0 | 74.5 | 99.3 | 98.0 | 98.1 | 66.5 | 58.3 |
| Nemotron 3.5 Lightning | |||||||||
| Dense | – | – | 91.1 | – | 100.0 | 99.0 | 100.0 | 95.7 | 61.0 |
| Ours | – | – | 70.0 | – | 84.0 | 49.0 | 71.5 | 92.4 | 53.0 |
| Ours with initial block | – | – | 74.7 | – | 81.0 | 42.0 | 99.0 | 96.5 | 55.0 |
| Ours, | – | – | 83.5 | – | 90.0 | 81.0 | 95.5 | 95.1 | 56.0 |
| Ours, , with initial block | – | – | 83.3 | – | 91.0 | 73.0 | 99.8 | 96.8 | 56.0 |
Table 11. RULER-5 by length and task at 512K, without and with the initial block, on Qwen3.5-4B, Qwen3.5-35B-A3B, and Nemotron 3.5 Lightning. Qwen rows average three clustering seeds.
Latency in detail
Latency by length
Figure 9 and Table 13 report prefill and decode latency for Qwen3.5-4B. Our method uses single-pass prefill through 512K and sliced prefill at 1M. The nominal 1M latency prompt contains 1,047,552 tokens. Appendix § 10 gives the measurement protocol.
Figure 9. Qwen3.5-4B latency on one H200 at . The columns show whole-model wall-clock latency (left) and GPU time over the eight full-attention layers (right). The rows show prefill (top) and decoding (bottom).
Appendix § 15 reports the corresponding results for Qwen3.5-35B-A3B (Figure 16) and Nemotron 3.5 Lightning (Figure 17).
Figure 16. Qwen3.5-35B-A3B latency on one H200 at . The columns show whole-model wall-clock latency (left) and GPU time over the ten full-attention layers (right). The rows show prefill (top) and decoding (bottom).
Figure 17. Nemotron 3.5 Lightning, latency against prompt length on one H200 at for three target mean block sizes , with the doubled budget at dashed. The left column is the whole model by wall clock and the right column the six full-attention layers by profiler accounting. The rows are prefill and decoding. The brackets are dense over ours at and , under the conditions of Table 35.
Prefill kernel breakdown
GPU kernels are grouped by the operator that launches them. At 512K, the first 17 of 64 query chunks use dense attention. The other chunks attend to selected blocks and the visible part of their own chunk.
Dense-prefix cutoff
The main configuration uses dense attention for a query chunk whose zero-based starting position satisfies , four times the token budget. We vary this cutoff to for while keeping the token budget and other settings fixed. Because the boundary is inclusive and selection is decided per chunk, is the cutoff for chunk starts rather than the exact number of densely processed queries.
Reducing the cutoff substantially lowers the dense-prefix attention time (Table 15). However, the affected queries now require block selection and grouped attention, increasing selected-block computation, query gathering, and output merging. At , these added costs largely offset the savings, leaving total prefill time nearly unchanged. At , total time increases. Neither smaller cutoff consistently improves the two retrieval scores, so we retain .
| Setting | Selected blocks | Dense prefix | Own chunk | Attention | Scoring | Gather, merge | Total | MK-3 | MK-2 |
| Dense attention | — | — | — | 31.44 | — | — | 40.30 | 96.0 | 99.0 |
| (ours) | 4.02 | 2.03 | 0.34 | 6.38 | 0.24 | 1.48 | 17.07 | 96.0 | 97.0 |
| 5.02 | 0.53 | 0.40 | 5.95 | 0.27 | 1.81 | 17.03 | 94.0 | 94.0 | |
| 5.65 | 0.16 | 0.43 | 6.24 | 0.29 | 2.10 | 17.64 | 93.0 | 93.0 |
Table 15. Effect of the dense-prefix cutoff on Qwen3.5-4B at 512K and . Timings are GPU seconds for one prefill, and accuracy is measured on 100 examples per task.
The dense reference is from Table 14. The quality comparisons use one clustering seed on the same examples, whereas the main RULER-5 results average three seeds.
Ablation of the kernel design
Table 16 compares three implementation choices from § 3.4 with simpler alternatives. All runs use one GPU and the 512K sliced prefill of Qwen3.5-4B at , with block selection and the rest of the runtime unchanged. In Q-outer execution, each tile of 32 queries reads the union of their selected blocks, with each query masked to its own selection. This takes more than twice as long as KV-outer execution and is slower than dense attention. Blocks are read again for every tile that selects them, and masked query–block pairs still incur computation. Gathering selected blocks from prompt-order KV for every query chunk adds about 9% to prefill time. The cluster-ordered cache avoids this repeated gathering. Replacing the fused selection kernel with a matrix product and a sort costs well under a second.
We also time the attention kernel on one chunk of the same prefill. With the same per-query selection, KV-outer execution using FlashAttention-3 takes about 21 ms, compared with 245 ms for FlexAttention (Dong et al., [7]) using a block mask. Most 128-by-128 blocks are partially selected, so FlexAttention processes nearly all of them.
Indexing older generated tokens
An optional flushing policy initially reads generated tokens exactly. When the unindexed suffix reaches tokens, the oldest are assigned to the existing centroids and added to the index without refitting. The newest remain outside the index. The cache buffers stay at fixed addresses, so the captured decode graph remains valid. Each point in Figure 10 averages the decode steps since the previous point, and all times include index updates.
| Execution | Prefill (s) | Decode (ms/token) |
| Dense attention | 40.69 | 9.27 |
| Ours: KV-outer over one cluster-ordered copy | 18.51 | 4.49 |
| Selected blocks gathered from prompt order every chunk | 20.24 | 4.45 |
| Same selection, Q-outer instead of KV-outer | 47.56 | 4.29 |
| Selection by a GEMM and a sort | 19.09 | 4.56 |
Table 16. Ablation of the kernel design on Qwen3.5-4B at 512K and , with the prefill and decode times of each execution.
With this policy the decode time stays nearly flat as the generation grows (Figure 10 and Table 17). Aggregate LongBench-v2 accuracy changes little with flushing (Table 18). We did not test reasoning traces as long as 64K tokens.
| 64 generated | 65,536 generated | |
| Dense | 15.39 | 16.06 |
| Ours | 4.81 | 7.85 |
| Ours, flushed every 8K () | 4.83 | 5.09 |
| Ours, flushed every 1K () | 4.82 | 4.82 |
Table 17. Qwen3.5-4B mean decode time over the full generation after a nominal 1M prompt, in milliseconds per token.
| Dense | Ours | Ours, flushed | |
| K (403 items) | 53.1 | 54.8 | 53.8 |
| K (67 items) | 65.7 | 61.2 | 58.2 |
| All (470) | 54.9 | 55.7 | 54.5 |
Table 18. Qwen3.5-4B LongBench-v2 accuracy (%) without and with flushing (, ), on the same items and sampling seed. The sparse columns are separate runs from Table 1’s.
Design choices on Qwen3.5-4B
The routing key
We compare routing representations while keeping attention computation unchanged. The main configuration uses unit-normalized pre-RoPE keys and queries, with spherical -means. We test using only the 192 non-rotary dimensions, since the model rotates 64 of its 256 key dimensions. We also test raw keys with Euclidean -means, using unnormalized cluster means and queries at the attention scale .
At 512K, both variants stay within about two points of our multi-key accuracy (Table 19). The non-rotary variant also matches our multi-key accuracy at 1M. Post-RoPE routing gives similar multi-key accuracy to pre-RoPE routing. PCA projections fitted to raw-corpus keys retain most of the multi-key accuracy at 128 and 32 dimensions. For timing, we use random projections of the same size. Reducing the dimension from 256 to 32 shortens the 512K prefill by about 5% and leaves decoding unchanged. These results support using the original keys for routing on Qwen3.5. On Nemotron, however, centering the keys prevents severe cluster imbalance (Table 34).
Table 19: The routing key on Qwen3.5-4B, with RULER multi-key and multi-value accuracy in percent at 512K, , , 100 items per entry. Our row, the post-RoPE row, and the multi-key entries of the non-rotary row are means over three clustering seeds, and all other entries use seed 0. A dash marks an entry that was not measured.
| Routing key | MK-3 | MK-2 | MV |
| Dense | 96.0 | 99.0 | 100.0 |
| Whole key, normalized, (ours) | 92.7 | 95.0 | 100.0 |
| Whole key after RoPE, normalized, | 93.0 | 94.0 | 100.0 |
| Non-rotary 192 dimensions, normalized, | 93.0 | 95.7 | 99.5 |
| Raw key, Euclidean -means, | 91.0 | 93.0 | 99.3 |
| Raw key, Euclidean -means, | 95.0 | 96.0 | 100.0 |
| PCA to 128 dimensions, normalized, | 94.0 | 91.0 | 100.0 |
| PCA to 32 dimensions, normalized, | 90.0 | 96.0 | 100.0 |
Table 19.
| Routing representation | MK-3 |
| Dense | 100 |
| Uncentered keys | 20 |
| Centered, 32 iterations, 128 samples per centroid | 100 |
| Whitened | 40 |
| Whitened, -means++ seeding, 32 iterations | 35 |
Table 34. Nemotron 3.5 Lightning, the 64K pilot behind the clustering settings, with MK-3 accuracy in percent on 20 items, . Centering subtracts the mean key before routing, whitening scales the centered keys by their covariance, and iterations and samples are the -means fit.
Token budget and block size at 512K
Table 20 lists the values plotted in Figure 6. It crosses four mean block sizes with four token budgets and scores each point on MK-2 over the same 100 items at 512K. The main setting’s accuracy is the three-seed mean of the main RULER table, and the other points are single runs of one code version. Each prefill time is the mean over two prompts. We use MK-2 rather than MK-3 here because its gap to dense attention is larger, so it separates the settings more clearly.
Table 20: The values behind Figure 6, Qwen3.5-4B at 512K.
| MK-2 (%) at | Prefill (s) at | |||||||
| 8K | 16K | 32K | 64K | 8K | 16K | 32K | 64K | |
| Dense | 99.0 | 40.69 | ||||||
| 4,096 | 32.0 | 62.0 | 90.0 | 100.0 | 12.66 | 14.05 | 16.78 | 23.47 |
| 2,048 | 40.0 | 75.0 | 95.0 | 99.0 | 13.40 | 14.98 | 17.86 | 24.30 |
| 1,024 | 56.0 | 87.0 | 97.0 | 100.0 | 15.30 | 17.31 | 20.42 | 26.14 |
| 512 | 73.0 | 86.0 | 97.0 | 99.0 | 18.97 | 22.21 | 25.59 | 30.05 |
Table 20.
At a fixed budget, finer blocks are slower. Their accuracy advantage is large at small budgets and narrows as the budget grows. The coarse partition with the main budget is both faster and more accurate than the fine partition with half that budget. Because selection takes whole clusters, their total size exceeds by 0.4–14% across the grid and 2.4% at the main setting, excluding tokens in . Accounting for this overshoot does not change the comparison.
Figure 11 extends the grid to MK-3 and MK-2 on all three models, with values for the Qwen models in Table 21 and for Nemotron in Table 36. Both Qwen models show the same pattern, with finer clusters ahead at small budgets and coarser clusters catching up as the budget grows. The main setting’s accuracy on each model is the three-seed mean of the main RULER table, and the other points are single runs. For the 35B-A3B model’s timings, gathering for KV-outer attention is split into two batches to fit in device memory.
Figure 11. Cluster size and token budget on MK-3 and MK-2 at 512K for Qwen3.5-4B, Qwen3.5-35B-A3B, and Nemotron 3.5 Lightning.
| MK-3 (%) at : 8K | 16K | 32K | 64K | MK-2 (%) at : 8K | 16K | 32K | 64K | Prefill (s) at : 8K | 16K | 32K | 64K | |
| Qwen3.5-4B | ||||||||||||
| Dense | 96.0 | 99.0 | 40.69 | |||||||||
| 4,096 | 31.0 | 76.0 | 91.0 | 94.0 | 32.0 | 62.0 | 90.0 | 100.0 | 12.66 | 14.05 | 16.78 | 23.47 |
| 2,048 | 58.0 | 88.0 | 92.7 | 97.0 | 40.0 | 75.0 | 95.0 | 99.0 | 13.40 | 14.98 | 17.86 | 24.30 |
| 1,024 | 81.0 | 87.0 | 94.0 | – | 56.0 | 87.0 | 97.0 | 100.0 | 15.30 | 17.31 | 20.42 | 26.14 |
| 512 | 82.0 | 88.0 | 92.0 | – | 73.0 | 86.0 | 97.0 | 99.0 | 18.97 | 22.21 | 25.59 | 30.05 |
| Qwen3.5-35B-A3B | ||||||||||||
| Dense | 100.0 | 97.0 | 49.19 | |||||||||
| 4,096 | 7.0 | 48.0 | 97.0 | – | 36.0 | 90.0 | 97.0 | – | 14.07 | 15.70 | 19.18 | – |
| 2,048 | 25.0 | 80.0 | 98.7 | – | 68.0 | 96.0 | 97.7 | – | 15.13 | 16.81 | 20.29 | – |
| 1,024 | 63.0 | 95.0 | – | – | 82.0 | 97.0 | – | – | 17.18 | 19.78 | – | – |
| 512 | 94.0 | 100.0 | – | – | 92.0 | 99.0 | 99.0 | – | 23.56 | 27.54 | 31.40 | – |
Table 21. The values behind Figure 11, Qwen3.5-4B and Qwen3.5-35B-A3B at 512K. A dash marks a point that was not measured.
| MK-3 (%) at , 8K | MK-3 (%) at , 16K | MK-3 (%) at , 32K | MK-3 (%) at , 64K | MK-2 (%) at , 8K | MK-2 (%) at , 16K | MK-2 (%) at , 32K | MK-2 (%) at , 64K | Prefill (s) at , 8K | Prefill (s) at , 16K | Prefill (s) at , 32K | Prefill (s) at , 64K | |
| Dense | 100.0 | 99.0 | 35.72 | |||||||||
| 4,096 | 3.0 | 19.0 | 60.0 | 89.0 | 6.0 | 14.0 | 32.0 | 62.0 | 11.30 | 12.46 | 14.80 | 19.96 |
| 2,048 | 11.0 | 35.0 | 84.0 | 90.0 | 7.0 | 20.0 | 49.0 | 81.0 | 11.98 | 13.26 | 15.72 | 20.75 |
| 1,024 | 25.0 | 65.0 | 87.0 | 94.0 | 17.0 | 33.0 | 72.0 | 91.0 | 12.95 | 14.55 | 17.21 | 22.24 |
| 512 | 56.0 | 79.0 | 93.0 | 97.0 | 34.0 | 62.0 | 83.0 | 95.0 | 14.81 | 16.83 | 20.09 | 25.09 |
| 256 | 81.0 | 86.0 | 93.0 | 99.0 | 62.0 | 78.0 | 92.0 | 98.0 | 19.86 | 22.60 | 26.64 | 31.29 |
| 128 | 82.0 | 89.0 | 97.0 | 100.0 | 68.0 | 87.0 | 96.0 | 96.0 | 30.10 | 34.25 | 40.17 | 44.82 |
Table 36. The values behind the bottom row of Figure 11, Nemotron 3.5 Lightning at 512K.
Figure 12 shows the corresponding profile for Qwen3.5-35B-A3B. The dense-prefix cutoff scales with the token budget. In the 4B experiment of Appendix E.3, reducing this cutoff did not improve prefill time.
Figure 12. GPU time of one 512K prefill on Qwen3.5-35B-A3B by cluster size and token budget , drawn as Figure 7.
Budget scaling across context lengths
Increasing the budget beyond gives little additional MK-3 accuracy while increasing latency (Table 22). Reducing the budget lowers latency at the cost of retrieval accuracy. Neither a fixed token count nor a fixed fraction predicts accuracy across lengths, because the dense model’s own retrieval performance also declines.
| Prompt | Dense | ||||
| 256K | 100 (12.4 s) | 97 (1.36×) | 97.7 (1.74×) | 88 (1.86×) | 42 (1.98×) |
| 512K | 96 (40.7 s) | 95 (1.62×) | 92.7 (2.25×) | 89 (2.68×) | 57 (2.98×) |
| 1M | 40 (144.1 s) | 32 (1.83×) | 28.3 (2.84×) | 24 (3.68×) | 18 (4.33×) |
Table 22. Qwen3.5-4B, MK-3 accuracy in percent () and prefill speedup at each length and budget. The column is the three-seed mean of the main table, and the other entries are single runs.
Figure 13 extends the comparison at 512K to MRCR-8 and LongBench-v2 on both Qwen models, over budgets from to . Because benchmark prompt lengths vary, we use the prefill time of a fixed-length RULER prompt as a common reference on the horizontal axis. For each budget, the reference prompt is 512K for MRCR-8 and 256K for LongBench-v2, the upper bound of the band containing most LongBench-v2 items. Filled markers are means over three runs, and hollow markers are single runs.
Figure 13. Quality against prefill time over token budgets from to on Qwen3.5-4B and Qwen3.5-35B-A3B.
MK-3 accuracy declines below , while MRCR-8 changes less. At , the MRCR-8 scores stay within the range of the three runs (Table 12). Increasing the budget to raises MRCR-8 above this range on the 4B model but not on the 35B-A3B model. On the 35B-A3B model, 512-token clusters match dense MK-3 accuracy at and come within six points at , but take longer to prefill than the main setting (Table 21). LongBench-v2 holds its accuracy down to and drops at .
| Method | 128K | 256K | 512K | ≤256K | >256K | all |
| Qwen3.5-4B | ||||||
| Dense | 0.797 (0.053) | 0.574 (0.010) | 0.412 (0.027) | 54.3 (1.1) | 64.2 (2.6) | 55.7 (0.7) |
| Ours | 0.788 (0.056) | 0.561 (0.029) | 0.399 (0.013) | 53.9 (1.0) | 57.7 (2.3) | 54.5 (0.6) |
| Ours with initial block | 0.783 (0.024) | 0.561 (0.068) | 0.415 (0.022) | 55.5 (0.9) | 57.2 (3.1) | 55.7 (0.4) |
| Qwen3.5-35B-A3B | ||||||
| Dense | 0.846 (0.012) | 0.655 (0.009) | 0.564 (0.056) | 64.4 (0.8) | 66.2 (2.3) | 64.7 (0.6) |
| Ours | 0.844 (0.016) | 0.668 (0.013) | 0.504 (0.063) | 63.1 (0.9) | 64.7 (0.9) | 63.3 (0.9) |
| Ours with initial block | 0.885 (0.019) | 0.655 (0.020) | 0.489 (0.021) | 64.7 (1.2) | 65.2 (4.3) | 64.8 (1.5) |
Table 12. MRCR-8 and LongBench-v2 of Qwen3.5-4B and Qwen3.5-35B-A3B without and with the initial block, the mean over three runs with the standard deviation across runs in parentheses.
Positional baselines
We form contiguous blocks of tokens and represent each block by its mean pre-RoPE key. Queries score these means without vector normalization at temperature , and head probabilities are summed within each GQA group before selecting the top blocks. With the positional baseline’s raw keys, unnormalized cluster means, and temperature , semantic blocks lose only a few points of accuracy (Table 19). They still outperform positional blocks, so normalization and temperature do not explain the gap. Both methods use the same token budget and dense-prefix, current-chunk, and generated-suffix policies. With per-query selection, positional blocks use the same KV-outer execution as semantic blocks (§ 3.4).
For shared selection, consecutive queries select blocks together using the tile score of FlashPrefill V2 [8]. Within each query head, we sum the exponentiated block scores across the queries and normalize over blocks. We then sum these probabilities within each GQA group and select the highest-scoring blocks to fill the budget. All queries attend to the selected blocks with their original query vectors and causal masks. Groups stay within a prefill chunk, and an incomplete final group is padded by repeating its last query. Both block layouts use this procedure, while decoding remains per-query. A Triton kernel computes group scores without storing individual query scores, and each group attends to its selected blocks in one FlashAttention call [15, 18].
FlashPrefill V2 shares one selection across 128 query rows. On the 4B model, these correspond to four query heads over 32 positions, within the sharing spans tested here [8]. Our comparisons vary block layout and query sharing at a fixed token budget; they do not reproduce the complete selection policies of MInference, FlexPrefill, QuoKA, or FlashPrefill. The released MInference and FlexPrefill kernels available for these experiments supported head dimensions up to 128, whereas Qwen3.5 uses 256. We found no public QuoKA code when we ran the comparisons. Appendix § 13.§ 5 compares directly with FlashPrefill V2.
At most settings, we also tested scoring blocks with the group’s mean query, as in MInference and FlexPrefill [15, 18]. We further tested the maximum score across queries and a sum over both queries and GQA heads as in FlashPrefill V2. Each gave accuracy similar to or lower than the summed exponentials. Table 23 lists all points in Figure 5, without and with the initial block.
On Qwen3.5-35B-A3B (Table 24), MK-3 is near its ceiling, and positional blocks of 8 tokens shared over 32 queries reach our accuracy, but their prefill takes 1.8× as long, as on the 4B model. Every faster positional setting is at least 6 points less accurate. On MK-2, the same setting is 14 points below our three-seed mean of 97.7%, and every other positional setting is lower still.
Table 24: Positional and semantic retrieval on Qwen3.5-35B-A3B at 512K, , without the initial block, MK-3 and MK-2 accuracy in percent with (ours on clustering seed 0) and 512K prefill time.
| Index | MK-3 (%) | MK-2 (%) | Prefill (s) | ||
| Positional, shared | 16 | 64 | 78 | 58 | 30.8 |
| 32 | 32 | 84 | 63 | 22.5 | |
| 16 | 32 | 93 | 66 | 27.4 | |
| 8 | 32 | 99 | 84 | 37.1 | |
| Positional, per query | 128 | 1 | 55 | 47 | 34.4 |
| Ours, per query | – | 1 | 99 | 97 | 20.4 |
| Dense | – | – | 100 | 97 | 49.2 |
Table 24.
In Table 23, the columns with the initial block add the fixed initial block of Appendix § 11.§ 3 to every row, which changes the prefill times by at most 5%.
Table 25 repeats the comparison at the smaller budget , where our accuracy falls further below dense attention. Our method stays faster than every positional setting we timed, and is more accurate on MK-2 with and without the initial block. With the block, the most accurate positional setting approaches our MK-3 accuracy but takes as long to prefill as our method at and as long as at . At this budget, halving our cluster size to recovers much of the MK-2 loss, as in the grid of Appendix § 13.§ 2.
Table 25: Positional and semantic retrieval on Qwen3.5-4B at 512K with the smaller budget , accuracy in percent with , without and with the fixed initial block, and 512K prefill time without it.
| Index | MK-3 (%), initial block Without | MK-3 (%), initial block With | MK-2 (%), initial block Without | MK-2 (%), initial block With | Prefill (s) | ||
| Positional, shared | 16 | 32 | 71 | 83 | 32 | 36 | 22.1 |
| 8 | 64 | 61 | 81 | 39 | 48 | 26.8 | |
| 8 | 32 | 72 | 88 | 49 | 60 | 32.0 | |
| 4 | 32 | 64 | 79 | 58 | 62 | 51.5 | |
| Positional, per query | 32 | 1 | 68 | 69 | 47 | 50 | – |
| Ours, per query, | – | 1 | 82.7 | 90.0 | 76.7 | 86.0 | 14.8 |
| Ours, per query, | – | 1 | 87.0 | 90.7 | 88.0 | 89.3 | 17.1 |
| Dense | – | – | 96 | – | 99 | – | 40.1 |
Table 25.
A Quest-inspired min/max descriptor does not improve the positional baseline in this pre-RoPE setting [37]. This comparison tests the descriptor, not Quest’s complete decoding method. Its shared rows and the temperature sweeps below score the group’s averaged query rather than the summed exponentials.
The min/max descriptor bounds the dot product with each block’s pre-RoPE keys. It is not an upper bound on the model’s post-RoPE attention logits. At with shared selection, increasing its scoring temperature from 16 to 64, 256, or 1,024 gives MK-3 scores of 19, 20, and 19 percent, respectively. The mean-key descriptor’s temperature, swept at the same point over 4, 16, 64, 256 and 1,024, gives 46, 51, 49, 44 and 41 percent, so the baseline’s default temperature, , is the best of the five, and none moves the baseline towards semantic blocks.
Comparison with FlashPrefill V2
FlashPrefill V2 is the only practical training-free sparse prefill method we found whose released kernels support the 256-dimensional heads of Qwen3.5 on H200 [8]. We run it with the SGLang implementation released with it, on Qwen3.5-4B with the same 512K prompts and YaRN setting as our tables. It uses the settings of the launch example in its repository, except that all eight full-attention layers are sparse, as in our method. We vary its threshold , which sets how many blocks it keeps. It always keeps the first blocks of the prompt as attention sinks. Both methods run in BF16. SGLang times are the median time to the first token over the 100 prompts, with prefill in chunks of 16,384 tokens, and our times are the prefill time of the latency prompt (Appendix C). FlashPrefill V2 is one run per threshold. Our points by budget are single runs timed in one session, as in Appendix F.2, and the point with the initial block is the mean over three clustering seeds.
Figure 14 and Table 26 report accuracy and latency on each engine. The dense baselines have similar latency and accuracy, but the engines and timing protocols differ. We therefore compare each method’s speedup over its own engine’s dense baseline. Our method is more accurate at comparable speedups on both tasks. Among the tested thresholds, FlashPrefill V2 reaches our MK-3 accuracy only with a 1.7× speedup, compared with 2.2× for our method at .
Figure 14. FlashPrefill V2 in SGLang and our method in vLLM on Qwen3.5-4B at 512K, against time on each engine (top) and against time relative to dense attention on the same engine (bottom). Labels are our budget and the threshold of FlashPrefill V2.
| Method | Engine | Accuracy (%) | Time at 512K (s) | ||
| MK-3 | MK-2 | MK-3 run | MK-2 run | ||
| Dense attention | vLLM | 96.0 | 99.0 | 40.18 | |
| Ours, | vLLM | 88.0 | 75.0 | 14.98 | |
| Ours, | vLLM | 93.0 | 94.0 | 17.86 | |
| Ours, | vLLM | 97.0 | 99.0 | 24.30 | |
| Ours, , initial block | vLLM | 95.0 | 94.7 | 18.69 | |
| Dense attention | SGLang | 97.0 | 99.0 | 43.25 | 43.70 |
| FlashPrefill V2, | SGLang | 25.0 | 39.0 | 13.09 | 13.42 |
| FlashPrefill V2, | SGLang | 49.0 | 49.0 | 14.03 | 15.08 |
| FlashPrefill V2, | SGLang | 81.0 | 59.0 | 16.23 | 17.15 |
| FlashPrefill V2, | SGLang | 88.0 | 79.0 | 20.82 | 24.09 |
| FlashPrefill V2, | SGLang | 94.0 | 84.0 | 25.37 | 29.83 |
Table 26. FlashPrefill V2 in SGLang and our method in vLLM on Qwen3.5-4B at 512K. Accuracy is on 100 prompts per task. Times are the prefill time of the latency prompt on vLLM and the median time to the first token over the 100 prompts on SGLang.
Centroids fitted on a corpus
Table 2 compares centroids fitted to each prompt with centroids fitted once and reused, with 256 centroids per layer and KV head. All rows keep the original query and key representations and the same selection rule, so this comparison does not include SAAP’s learned query classifier [26]. Per-prompt results average three clustering seeds, and the other rows are single runs. Raw-corpus centroids severely reduce multi-key accuracy and assign over half of the common-word prompt to one cluster, which the runtime rejects, so the table marks that task as failed. Fitting once to twenty RULER-5 examples per task recovers much of the loss. This fitting set includes evaluation examples, so the row diagnoses corpus mismatch rather than held-out generalization. The first-64K row fits each prompt’s centroids on its first 64K tokens and assigns every later key to them, as the prefix index of Appendix § 9.§ 5 does.
Sources of quality loss and training baselines
Attention mass missed by cluster scoring
Cluster selection can miss high-attention tokens because centroid scores misrank clusters or because whole clusters also contain low-attention tokens. We examine these effects by comparing centroid-based selection with dense-attention rankings, using the same partition.
We build the partition from the dense model’s keys and compare three selections for the dense model’s queries. The first applies our selection rule to the fitted clusters. The second sums the dense attention probabilities within each cluster and greedily selects whole clusters under the same budget, ranking by total mass or by mass per token and keeping the better of the two for each query and GQA group. The third selects the tokens that receive the most dense attention, without reading whole clusters. We call the last two dense-ranked clusters and dense-ranked tokens. Both need dense attention at inference time, so they serve only as references.
Coverage is the percentage of dense attention to the prompt retained by the selected tokens. Each query’s current chunk is always read exactly and does not count toward the budget. For generated queries, we count only attention to prompt tokens.
The analysis uses ten prompts per task at 512K, with the last 64 prompt positions and up to 32 generated tokens as queries, over the 4B model’s eight full-attention layers and four KV heads. The ten MK-3 prompts come from a separate set of 400 generated prompts rather than from the MK-3 items of our tables, and MRCR uses the first ten prompts of its 512K bin. The budgets are and of each prompt’s actual length. Dense probabilities are summed over a GQA group to rank tokens or clusters, and the retained mass is normalized by each query head’s attention on the prompt and averaged over heads, queries, layers, and prompts. Because heads can put different total attention on the prompt during generation, the ranking and the reported coverage are not exactly the same quantity. These queries emphasize retrieval near the end of the prompt and during generation, not the average prefill query.
At , dense-ranked tokens retain more attention mass than dense-ranked clusters on all three tasks (Figure 15). Cluster selections can exceed the budget by part of a cluster, but giving the token reference the same number of tokens changes its coverage by at most 0.3 points. Better cluster scores therefore recover only part of the mass lost when selection is restricted to whole clusters. Using our centroid scores with also gives higher coverage than dense-ranked clusters with on all three tasks (Table 27).
| Task | Our scores | Dense-ranked clusters | Dense-ranked tokens | |
| MK-2 | 77.4 | 80.8 | 90.4 | |
| MK-2 | 84.6 | 87.3 | 94.3 | |
| MK-3 | 76.9 | 80.5 | 91.9 | |
| MK-3 | 84.0 | 86.8 | 95.1 | |
| MRCR-8 | 86.3 | 88.2 | 94.2 | |
| MRCR-8 | 91.0 | 92.2 | 96.6 |
Table 27. Mean prompt-attention coverage on ten 512K examples per task, Qwen3.5-4B.
Figure 15. Prompt-attention coverage by full-attention layer at under our centroid scores, dense-ranked clusters, and dense-ranked tokens, on ten 512K examples per task, for Qwen3.5-4B (top, eight layers) and Qwen3.5-35B-A3B (bottom, ten). All curves use dense-model states.
We also replace the centroid scores inside the sparse runtime and measure RULER accuracy (Table 28). At every full-attention layer, we compute dense attention probabilities from the current queries and prompt keys in FP32, sum them within each cluster, and select clusters in that order under the runtime’s budget rule. The clustering, the regions read without selection, the attention computation, and the handling of generated tokens are unchanged. Queries and keys come from this sparse run, so the comparison includes the effect of earlier sparse layers on the model states. We use the first 50 prompts of each multi-key task at 512K, with clustering seed 0 for the dense-attention scores and the mean and standard deviation over three seeds for the centroid scores.
Table 28: Cluster scoring on Qwen3.5-4B at 512K, , . Accuracy (%) on 50 examples per task.
| Selection | MK-3 | MK-2 |
| Dense attention | 96.0 | 98.0 |
| Centroid scores | 93.3 (1.2) | 96.0 (0.0) |
| Dense attention mass | 94.0 | 98.0 |
Table 28.
Using dense-attention scores recovers dense accuracy on MK-2 but changes MK-3 little (Table 28). The effect of missing attention mass depends on which tokens are missed. A token carrying answer information matters more than one repeating information available elsewhere.
Learning the routing map
We test two simple training baselines. The first learns linear maps for selection while leaving the model weights and attention kernels unchanged. For each full-attention layer, we train a query map per query head and a key map per KV head, initialized to the identity. We also train the temperature and size penalty . The penalty is clamped to nonnegative values in the forward pass with a straight-through gradient, matching its use at inference time.
For each training document, we fit clusters on the mapped keys and sum the dense model’s attention probabilities within each cluster. The loss is the KL divergence from this cluster-mass distribution to the normalized selection scores in (2), with an L2 penalty keeping the maps near the identity. Cluster assignments are recomputed without gradients. The normalized means of the assigned mapped keys carry gradients to .
Training uses 25,684 raw-text documents of 65,536 tokens each, about 1.7B tokens, drawn from the PDF documents of the Dolma 3 Longmino mix [38]. We leave out the mix’s synthetic common-word extraction and rewriting tasks, which resemble RULER tasks. We train for 3,000 steps with eight data-parallel workers, a total batch size of eight documents, and learning rate . The objective is evaluated on eight held-out documents and largely plateaus after roughly half the run. For downstream evaluation, RULER scores are percentages averaged over three clustering seeds, with standard deviations in parentheses. MRCR-8 reports the mean match ratio over 100 examples.
Training reduces the held-out KL by about two thirds, but changes the attention mass retained by the selected clusters much less (Table 29). Much of the KL reduction accompanies a lower temperature, which sharpens the score distribution, while the size penalty reaches zero. The objective favors clusters receiving more total attention mass, which can reward large clusters and conflict with the runtime’s size penalty. Allowing a negative penalty reaches a similar objective.
Table 29: Learning query and key maps for clustering and selection on Qwen3.5-4B. The left columns report held-out KL loss, retained attention mass, and selection parameters. The right columns report long-context task performance.
| Configuration | Objective KL | Objective mass at | Rule | Rule | 512K MK-3 | 512K MK-2 | RULER-5 256K | RULER-5 512K | MRCR-8 512K |
| Dense attention | – | – | – | – | 96.0 | 99.0 | 84.7 | 82.8 | 0.381 |
| Identity map (ours) | 1.07 | 0.674 | 0.10 | 0.25 | 92.7 (0.6) | 95.0 (1.0) | 82.7 (0.1) | 81.8 (0.5) | 0.405 |
| Learned , , , | 0.31 | 0.695 | 0.036 | 0 | 91.0 (1.0) | 94.7 (0.6) | 83.1 (0.2) | 81.5 (0.4) | 0.402 |
Table 29.
The learned map gives similar aggregate RULER-5 and MRCR-8 scores to the identity map, but its 512K MK-3 accuracy is about two points lower. Earlier runs used a corpus 8.5 times smaller and a quarter to a third of the training steps, and tested an unconstrained penalty, the same map with the penalty clamped at evaluation, and a query-only map. None gave a consistent retrieval improvement.
Adapting the model to its sparse attention with LoRA
The second baseline adapts the model weights to the sparse attention. A copy of the model with rank-8 LoRA adapters [14] runs sparse attention and is trained to match the dense model’s next-token distribution by forward KL over the full vocabulary. One configuration adapts the query, key, and output projections of the eight full-attention layers. The other also adapts the MLP and Gated DeltaNet projections. The index and the selection are recomputed from the adapted model’s current keys and queries with the same code as at inference. Gradients pass through attention over the selected tokens, but not through the discrete selection.
Each run uses 300 steps with four documents per step, drawn from the corpus of the learned map above. The documents are 64K tokens long, and the loss is computed at every position. As an implementation check, the model with zero-initialized adapters reproduces the dense model when both use dense attention. For evaluation, adapters are merged into the weights and the sparse runtime is unchanged. Each task uses 100 examples and one clustering seed.
The held-out distillation objective falls substantially during training, but the task results do not improve (Table 30). At 512K, MK-2 stays close to the training-free configuration, while MK-3 and MRCR-8 are lower. These runs use raw text and documents shorter than the evaluation prompts. Other work on adapting models to sparse attention also trains on synthetic long-context tasks [46], which we do not test.
| Adapters | 128K MK-2 | 128K MK-3 | 512K MK-2 | 512K MK-3 | MRCR-8 |
| Dense | 100 | 100 | 99 | 96 | 0.381 |
| Ours, no training | 98 | 100 | 94 | 93 | 0.405 |
| Attention | 99 | 99 | 92 | 91 | 0.298 |
| +MLP+GDN | 100 | 99 | 95 | 90 | 0.291 |
Table 30. Adapting Qwen3.5-4B to sparse attention with LoRA trained on 64K documents. RULER multi-key scores are accuracy (%), and MRCR-8 reports a mean match ratio. All configurations use the same sparse runtime and token budget.
Other architectures
This section provides the full results for Qwen3.5-35B-A3B and Nemotron 3.5 Lightning.
Qwen3.5-35B-A3B
Qwen3.5-35B-A3B has 40 layers, including ten full-attention layers with 16 query heads, two KV heads, and head dimension 256. It uses 256 experts with eight active and shares the 4B model’s tokenizer. The sparse implementation uses the same query and key representations, clustering settings, and selection rule as the 4B model. All sparse quality measurements use sliced prefill. Latency measurements use it from 512K onward, where single-pass prefill exceeds device memory. The dense baseline uses chunked prefill.
Table 9 gives the task scores beside the 4B model’s. Figure 16 shows prefill and decode latency, with values in Table 31.
RULER-5 remains close to dense attention through 1M. Both multi-key tasks also remain close through 512K. At 1M, our method loses accuracy on MK-3 and common-word extraction but is above dense attention on MK-2 and HotpotQA. Halving or quartering the budget at 512K substantially reduces multi-key accuracy. The QA and common-word results of those runs used capped prompts and are not shown.
The 512K prefill profile in Figure 19 shows that the unchanged expert and Gated DeltaNet layers account for much of the remaining sparse prefill time. Because the sparse prefill is sliced at this length, these layers run in 32K slices, and the mixture-of-experts kernels are the largest part of the time not attributed to attention.
Figure 19. The 512K prefill profile of Qwen3.5-35B-A3B at (left) and of Nemotron 3.5 Lightning at (right), drawn as Figure 4, with GPU seconds by kernel group from one profiled prefill of each configuration. Nemotron uses different slicing schedules for non-attention layers in the dense and sparse runs.
Figure 4. GPU-time breakdown for a 512K prefill on Qwen3.5-4B. The upper panel shows whole-model GPU time, and the lower panel breaks down our attention-kernel time (Table 14). Times are profiler totals, not wall-clock latency.
For long generations, reading the entire generated suffix exactly increases decode cost. After a 512K prompt, the decode step grows from 4.9 ms per token at the start to 10.5 ms between 32K and 64K generated tokens, above dense attention’s 9.1 ms, while flushing keeps it near 5.1 ms. Flushing avoids this growth after both 512K and 1M prompts, with similar aggregate LongBench-v2 accuracy in the measured runs (Table 32 and Table 33).
| Configuration | 64 | 65,536 |
| Dense | 12.90 | 13.42 |
| Ours | 5.57 | 9.21 |
| Ours, flushed every 1K () | 5.55 | 5.49 |
| Ours, flushed every 8K () | 5.57 | 5.91 |
Table 32. Qwen3.5-35B-A3B, mean decode time after a 1M prompt in milliseconds per token, over 64 and over 65,536 generated tokens, , one H200.
| MRCR-8 | LongBench-v2 | |||||
| 128K | 256K | 512K | ≤256K | >256K | all | |
| Dense | 0.849 | 0.644 | 0.500 | 65.3 | 65.7 | 65.3 |
| Ours, | 0.835 | 0.596 | 0.463 | 64.3 | 65.7 | 64.5 |
| Ours, | 0.839 | 0.682 | 0.437 | 62.3 | 64.2 | 62.6 |
| Ours, , flushed | – | – | – | 63.0 | 71.6 | 64.3 |
Table 33. Qwen3.5-35B-A3B on MRCR-8 (mean match ratio) and LongBench-v2 (accuracy over the same 470 items), thinking on, at and at half of it. Flushing uses and (Appendix § 12.§ 5).
Table 33 compares the main budget with half that budget on MRCR-8 and LongBench-v2 in single runs. MRCR-8 at the main budget stays close to dense attention through 256K and falls below it at 512K. Halving the budget lowers MRCR-8 most at 256K. LongBench-v2 scores change less across the sparse configurations, and flushing changes aggregate accuracy by less than two percentage points.
The coverage analysis shows the same ordering as on the 4B model (Figure 15). Mean coverage is slightly lower on the 35B-A3B model even though its task-accuracy loss is smaller.
Nemotron 3.5 Lightning
Nemotron 3.5 Lightning 30B-A3B combines Mamba-2 and MoE layers with six full-attention layers, each with two KV heads and no rotary embedding. We replace these attention layers and retain the original model weights. We also slice non-attention layers to avoid an offset overflow in the Mamba-2 convolution kernel.
For routing, we center keys and use 32 clustering iterations with at least 128 sampled keys per centroid. These settings were selected on a 64K pilot and retained for longer evaluations (Table 34). Centering addresses a strong shared direction in the keys that otherwise leads to cluster collapse. It changes only routing representations, not the KV used for attention.
Figure 17 draws the latency columns of Table 35. Both decode paths use full-step graphs. The nominal 1M latency prompt is 1,028,096 tokens, while the 1M task evaluations use the 1,048,576-token RULER prompts.
| Prompt | Configuration | MK-3 (%) | Whole model: Prefill (s) | Whole model: Decode (ms) | Attention layers (6): Prefill (s) | Attention layers (6): Decode (ms) |
| 256K | Dense | 100 | 11.07 | 3.92 | 6.91 | 0.51 |
| 256K | Ours, | 73 | 6.15 | 3.39 | 1.94 | 0.17 |
| 256K | Ours, | 93 | 6.82 | 3.38 | 2.34 | 0.18 |
| 256K | Ours, | 98 | 7.68 | 3.42 | 3.07 | 0.22 |
| 256K | Ours, , | 96 | 7.59 | 3.44 | 3.15 | 0.22 |
| 512K | Dense | 100 | 35.72 | 4.44 | 28.32 | 0.88 |
| 512K | Ours, | 84 | 15.33 | 3.59 | 6.95 | 0.23 |
| 512K | Ours, | 87 | 17.30 | 3.54 | 8.47 | 0.27 |
| 512K | Ours, | 93 | 21.42 | 3.60 | 11.15 | 0.34 |
| 512K | Ours, , | 90 | 20.70 | 3.63 | 12.06 | 0.32 |
| 1M | Dense | 100 | 120.18 | 5.37 | 104.12 | 1.64 |
| 1M | Ours, | 70 | 41.09 | 3.65 | 24.54 | 0.35 |
| 1M | Ours, , | 85 | 61.62 | 3.87 | 44.74 | 0.51 |
Table 35. Nemotron 3.5 Lightning latency on one H200 and MK-3 accuracy in percent () by prompt length, at unless noted. The attention-layer columns are profiler totals over the six full-attention layers.
At and , prefill is 1.8× faster than dense attention at 256K and approaches three times as fast at 1M. The MK-3 loss is substantial at every length, however. Decode gains are smaller because the replaced attention layers account for less of the original decode step.
Figure 11 (bottom row) and Table 36 show the MK-3 and MK-2 grid at 512K, including and 128. Points below 30% accuracy are not drawn, and the ringed point is the main setting, and . For and 128, KV-outer gathering uses batches of 512 clusters to fit in device memory.
At a fixed budget, accuracy improves as cluster size decreases to 512 tokens. At similar prefill times, however, 512- or 1,024-token clusters with a larger budget are more accurate than 256- or 128-token clusters. Nemotron therefore benefits from finer clusters than the Qwen models. The main results keep , as on the Qwen models. At , changing to raises MK-2 accuracy by 10 points for about 7% more prefill time.
Figure 18 breaks down prefill time by cluster size. Smaller clusters mainly increase the time spent on attention over selected blocks, gathering, and merging, but the increase is smaller than on the Qwen models.
Table 9 reports all five RULER-5 tasks at 512K alongside the Qwen models. Unlike the Qwen models, Nemotron loses substantial accuracy on multi-value retrieval as well as multi-key retrieval. Doubling the budget recovers much of this loss while retaining prefill speedups of 1.5–2.0× from 256K to 1M (Table 35). The budget increase has a smaller effect on decode time.
Prior sparse-attention methods
Table 37 summarizes selected sparse-attention methods and their evaluations. Here, hybrid models combine full attention with linear-attention or state-space layers. SpotAttention keeps prefill dense and evaluates accuracy on hybrid Qwen3.5 models [1]. It reports decode throughput on Qwen3-8B. UniPrefill also evaluates several training-free prefill methods on hybrid models up to 128K tokens [9].
| Method | Learned components | Sparse phases | Hybrid model | Whole-model time |
| MInference [15] | None | Prefill | No | Yes |
| FlexPrefill [18] | None | Prefill | No | No |
| FlashPrefill / V2 [8 c] | None | Prefill | No | Yes |
| QuoKA [16] | None | Prefill, decode | No | Yes |
| Quest [37] | None | Decode | No | Yes |
| Squeezed [12] | None | Prefill, decode | No | No |
| ClusterKV [23] | None | Decode | No | Yes |
| Tactic (Zhu et al., 2026) | None | Decode | No | Yes |
| SAAP [26] | Query classifier | Decode | No | No |
| SpotAttention [1] | Indexer | Decode | Yes | Yes |
| RTPurbo [46] | Indexer and model | Prefill, decode | No | No |
| MoBA / FlashMoBA [25, 41] | Model | Prefill | No | No |
| DSA [5] | Indexer and model | Prefill, decode | No | Service cost |
| MSA [19] | Indexer and model | Prefill, decode | No | No |
| QSA [32] | Indexer and model | Prefill, decode | Yes | No |
| HISA [43] | Indexer and model | Prefill, decode | No | Yes |
| This work | None | Prefill, decode | Yes | Yes |
Table 37. Sparse-attention methods as their papers describe and evaluate them. The groups are training-free methods aimed mainly at prefill, training-free methods aimed mainly at decoding, and methods with learned components. Learned components are those trained for sparsity beyond the pretrained model. Whole-model time means that the paper times the whole model, such as end-to-end latency, time to first token, or time per output token, rather than only the attention layer or kernel. DSA reports token costs derived from deployed-service benchmarks.
ClusterKV and Tactic build a key index during dense prefill for subsequent decoding [23] (Zhu et al. 2026). Squeezed builds its index offline for a fixed context [12]. Our method builds an index within each request and uses it for the prompt’s own prefill. Our corpus-fitted centroids in § 5.4 are scored with the model’s queries, whereas SAAP learns a query classifier [26].
BLASST skips softmax and attention–value computation for low-scoring blocks [44]. Sketch&Walk combines sketched scores across layers to select blocks (Le et al., 2026). Kascade and IndexCache reuse token selections across layers [6, 4].
Examples of cluster members
Figure 3 shows one cluster from an MRCR prompt and one from an MK-3 prompt. Each highlighted span is a single member token, with surrounding text for context. Cosine similarity is measured between the normalized pre-RoPE key and its assigned centroid. Each cluster comes from a partition of 256 clusters fitted to the unmodified model’s keys. Layer, KV-head, and token-position indices are zero-based. The figure shows the three nearest and three farthest members of each cluster among the saved examples.
The MRCR cluster groups environmental vocabulary across several passages. Its lower-similarity members extend to medicine, history, and mathematics. For MK-3, the nearest members occur at the beginning of key identifiers, but lower-similarity members also include the beginning of a value identifier.
In two MK-3 and two MRCR prompts, about 70% of MK-3 clusters and 90% of MRCR clusters have no single token type accounting for more than half their members. These counts use all cluster members across eight layers and four KV heads per prompt.
Further clusters
Figure 20 shows five further clusters, using three members from each end of the saved cosine range. The first and third clusters use the same MRCR prompt as Figure 3, the second and fourth use separate MRCR and MK-3 prompts, and the fifth uses an MK-2 prompt.
Figure 20. Five additive clusters containing color vocabulary, tokens in a passage about color, pronouns, UUID digits, and adjectives in MK-2 keys. Positions are token indices, and highlights mark member tokens. Rows are sorted by key–centroid cosine similarity, with a gap between the two ends.
The first cluster groups occurrences of colors across descriptions, while its lower-similarity members extend to other words. The second includes punctuation and function words within a passage about color perception. The third groups pronouns and possessives across different topics. In the fourth, the nearest members are the digit 4 at the start of the third group of a key UUID. One lower-similarity member instead occurs in the second group. The fifth comes from an MK-2 prompt with lines such as “One of the special magic numbers for troubled-arena is: 8154823.” All ten saved nearest members of this cluster are negative adjectives in different keys, such as troubled, weary, abusive, disgusted, and ashamed. Its lowest-similarity members include other tokens of the same lines.
References
- [1]Huzama Ahmad and Se-Young Yun. SpotAttention: Plug-in block-sparse routing for pretrained long-context transformers. arXiv preprint arXiv:2606.22874, 2026.arxiv.org/abs/2606.22874
- [2]Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghvi. GQA: Training generalized multi-query transformer models from multi-head checkpoints. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
- [3]Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Yuxiao Dong, Jie Tang, Lei Hou, and Juanzi Li. LongBench v2: Towards deeper understanding and reasoning on realistic long-context multitasks. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, 2025.arxiv.org/abs/2412.15204
- [4]Yushi Bai, Qian Dong, Ting Jiang, Xin Lv, Zhengxiao Du, Aohan Zeng, Jie Tang, and Juanzi Li. IndexCache: Accelerating sparse attention via cross-layer index reuse. In Conference on Language Modeling, 2026. arXiv:2603.12201.arxiv.org/abs/2603.12201
- [5]DeepSeek-AI. DeepSeek-V3.2: Pushing the frontier of open large language models. arXiv preprint arXiv:2512.02556, 2025.arxiv.org/abs/2512.02556
- [6]Dhruv Deshmukh, Saurabh Goyal, Nipun Kwatra, and Ramachandran Ramjee. Kascade: A practical sparse attention method for long-context LLM inference. arXiv preprint arXiv:2512.16391, 2025.arxiv.org/abs/2512.16391
- [7]Juechu Dong, Boyuan Feng, Driss Guessous, Yanbo Liang, and Horace He. FlexAttention: A programming model for generating fused attention variants. In Proceedings of Machine Learning and Systems, volume 7, 2025. arXiv:2412.05496.
- [8]Qihang Fan, Huaibo Huang, Zhiying Wu, Bingning Wang, and Ran He. FlashPrefill V2: Block-sparse prefill attention for long-context LLM serving. arXiv preprint arXiv:2608.19758, 2026a.arxiv.org/abs/2608.19758
- [9]Qihang Fan, Huaibo Huang, Zhiying Wu, Bingning Wang, and Ran He. UniPrefill: Universal long-context prefill acceleration via block-wise dynamic sparsification. arXiv preprint arXiv:2605.06221, 2026b.arxiv.org/abs/2605.06221
- [10]Qihang Fan, Huaibo Huang, Zhiying Wu, Juqiu Wang, Bingning Wang, and Ran He. FlashPrefill: Instantaneous pattern discovery and thresholding for ultra-fast long-context prefilling. arXiv preprint arXiv:2603.06199, 2026c.arxiv.org/abs/2603.06199
- [11]Gemma Team. Gemma 4, 2026.
- [12]Coleman Richard Charles Hooper, Sehoon Kim, Hiva Mohammadzadeh, Monishwaran Maheswaran, Sebastian Zhao, June Paik, Michael W. Mahoney, Kurt Keutzer, and Amir Gholami. Squeezed attention: Accelerating long context length LLM inference. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, 2025.arxiv.org/abs/2411.09688
- [13]Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. RULER: What’s the real context size of your long-context language models? In Conference on Language Modeling, 2024.arxiv.org/abs/2404.06654
- [14]Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.arxiv.org/abs/2106.09685
- [15]Huijiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir H. Abdi, Dongsheng Li, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. MInference 1.0: Accelerating pre-filling for long-context LLMs via dynamic sparse attention. In Advances in Neural Information Processing Systems, 2024.arxiv.org/abs/2407.02490
- [16]Dalton Jones, Junyoung Park, Matthew Morse, Mingu Lee, Chris Lott, and M. Harper Langston. QuoKA: Query-oriented KV selection for efficient LLM prefill. In International Conference on Learning Representations, 2026.arxiv.org/abs/2602.08722
- [17]Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th ACM Symposium on Operating Systems Principles, 2023.arxiv.org/abs/2309.06180
- [18]Xunhao Lai, Jianqiao Lu, Yao Luo, Yiyuan Ma, and Xun Zhou. FlexPrefill: A context-aware sparse attention mechanism for efficient long-sequence inference. In International Conference on Learning Representations, 2025.arxiv.org/abs/2502.20766
- [19]Xunhao Lai, Weiqi Xu, Yufeng Yang, Qiaorui Chen, Yang Xu, Lunbin Zeng, Xiaolong Li, Haohai Sun, Haichao Zhu, Vito Zhang, Jinkai Hu, Jiayao Li, Rui Gao, Zekun Li, Songquan Zhu, Jingkai Zhou, and Pengyu Zhao. MiniMax Sparse Attention. arXiv preprint arXiv:2606.13392, 2026.arxiv.org/abs/2606.13392
- [21]Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. SnapKV: LLM knows what you are looking for before generation. In Advances in Neural Information Processing Systems, volume 37, 2024. arXiv:2404.14469.arxiv.org/abs/2404.14469
- [22]Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chengruigong Zhang, Bailu Ding, Kai Zhang, Chen Chen, Fan Yang, Yuqing Yang, and Lili Qiu. RetrievalAttention: Accelerating long-context LLM inference via vector retrieval. In Advances in Neural Information Processing Systems, volume 38, 2025a. arXiv:2409.10516.arxiv.org/abs/2409.10516
- [23]Guangda Liu, Chengwei Li, Jieru Zhao, Chenqi Zhang, and Minyi Guo. ClusterKV: Manipulating LLM KV cache in semantic space for recallable compression. In Proceedings of the 62nd ACM/IEEE Design Automation Conference, 2025b.arxiv.org/abs/2412.03213
- [24]Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. KIVI: A tuning-free asymmetric 2bit quantization for KV cache. In Proceedings of the 41st International Conference on Machine Learning, 2024.DOI
- [25]Enzhe Lu, Zhejun Jiang, Jingyuan Liu, Yulun Du, Tao Jiang, Chao Hong, Shaowei Liu, Weiran He, Enming Yuan, Yuxi Wang, Zhiqi Huang, Huan Yuan, Suting Xu, Xinran Xu, Guokun Lai, Yanru Chen, Huabin Zheng, Junjie Yan, Jianlin Su, Yuxin Wu, Yutao Zhang, Zhilin Yang, Xinyu Zhou, Mingxing Zhang, and JiezHong Qiu. MoBA: Mixture of block attention for long-context LLMs. In Advances in Neural Information Processing Systems, volume 38, 2025. arXiv:2502.13189.arxiv.org/abs/2502.13189
- [26]Pierre-Emmanuel Mazaré, Gergely Szilvasy, Maria Lomeli, Francisco Massa, Naila Murray, Hervé Jégou, and Matthijs Douze. Inference-time sparse attention with asymmetric indexing. arXiv preprint arXiv:2502.08246, 2025.arxiv.org/abs/2502.08246
- [27]MiniMax. MiniMax-M1: Scaling test-time compute efficiently with lightning attention. arXiv preprint arXiv:2506.13585, 2025.
- [28]Piotr Nawrot, Robert Li, Renjie Huang, Sebastian Ruder, Kelly Marchisio, and Edoardo M. Ponti. The sparse frontier: Sparse attention trade-offs in transformer LLMs. In Findings of the Association for Computational Linguistics: ACL 2026, 2026.arxiv.org/abs/2504.17768
- [29]NVIDIA. NVIDIA-Nemotron-3.5-Lightning-30B-A3B. https://huggingface.co/nvidia/NVIDIA-Nemotron-3.5-Lightning-30B-A3B-BF16, 2026.
- [30]OpenAI. OpenAI MRRC: Long context multiple needle in a haystack benchmark. Hugging Face dataset, https://huggingface.co/datasets/openai/mrc, 2025.
- [31]Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. YaRN: Efficient context window extension of large language models. In International Conference on Learning Representations, 2024.arxiv.org/abs/2309.00071
- [32]Zihan Qiu, Zekun Wang, Xiao Li, Yanpeng Li, Yang Xu, Yixuan Wang, Huaqing Zhang, Rui Men, Bochao Mao, Chengruidong Zhang, Fan Zhou, Hao Luo, Haofeng Huang, Haoran Lian, Haoyan Huang, Hongqing Chen, Jianwei Zhang, Jing Xu, Junjie Wang, Langshi Chen, Liangyu Wang, Linlang Jiang, Man Yuan, Minmin Sun, Peng Jin, Siqi Zhang, Siyu Wang, Xingzhang Ren, Yakai Wang, Yi Zhang, Yiming Dong, Yizhong Cao, Yubo Ma, Yunfei Mao, Bo Zheng, and Dayiheng Liu. On the design of Qwen3.8-Next architecture: Evaluation, efficiency, and training stability. arXiv preprint arXiv:2608.30320, 2026.arxiv.org/abs/2608.30320
- [33]Qwen Team. Qwen3.5. https://huggingface.co/collections/Qwen/qwen35, 2026.
- [34]Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9, 2021.
- [35]Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. FlashAttention-3: Fast and accurate attention with asynchrony and low-precision. In Advances in Neural Information Processing Systems, volume 37, 2024. arXiv:2407.08608.arxiv.org/abs/2407.08608
- [36]Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. RoFormer: Enhanced transformer with rotary position embedding. Neurocomputing, 568:127063, 2024.arxiv.org/abs/2104.09864
- [37]Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context LLM inference. In International Conference on Machine Learning, 2024.arxiv.org/abs/2406.10774
- [38]Team Olmo. Olmo 3. arXiv preprint arXiv:2512.13961, 2025.
- [39]Wenhao Wu, Yizhong Wang, Guangxuan Xiao, Hao Peng, and Yao Fu. Retrieval head mechanistically explains long-context factuality. In International Conference on Learning Representations, 2025. arXiv:2404.15574.arxiv.org/abs/2404.15574
- [40]Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, 2024.arxiv.org/abs/2309.17453
- [41]Guangxuan Xiao, Junxian Guo, Kasra Mazaheri, and Song Han. Optimizing mixture of block attention. arXiv preprint arXiv:2511.11571, 2025a.arxiv.org/abs/2511.11571
- [42]Guangxuan Xiao, Jiaming Tang, Jingwei Zuo, Junxian Guo, Shang Yang, Haotian Tang, Yao Fu, and Song Han. DuoAttention: Efficient long-context LLM inference with retrieval and streaming heads. In International Conference on Learning Representations, 2025b. arXiv:2410.10819.arxiv.org/abs/2410.10819
- [43]Yufei Xu, Fanxu Meng, Fan Jiang, Yuxuan Wang, Ruijie Zhou, Zhaohui Wang, Jiexi Wu, Zhixin Pan, Xiaojun Tang, Wenjie Pei, Tongxuan Liu, Di Yin, Xing Sun, and Muhan Zhang. HISA: Efficient hierarchical indexing for fine-grained sparse attention. In Conference on Language Modeling, 2026. arXiv:2603.28458.arxiv.org/abs/2603.28458
- [44]Jiayi Yuan, Cameron Shinn, Kai Xu, Jingze Cui, George Klimiashvili, Guangxuan Xiao, Perkz Zheng, Bo Li, Yixin Zhou, Zhouhai Ye, Weijie You, Tian Zheng, Dominic Brown, Pengbo Wang, Markus Hoehnerbach, Richard Cai, Julien Demouth, John D. Owens, Xia Hu, Song Han, Timmy Liu, and Huizi Mao. BLASST: Dynamic BLocked attention sparsity via softmax thresholding. In Proceedings of Machine Learning and Systems, volume 8, 2026.arxiv.org/abs/2512.12087
- [45]Jingyang Yuan, Huazuo Gao, Damai Dai, Junyu Luo, Liang Zhao, Zhengyan Zhang, Zhenda Xie, Y. X. Wei, Lean Wang, Zhiping Xiao, Yuqing Wang, Chong Ruan, Ming Zhang, Wenfeng Liang, and Wangding Zeng. Native sparse attention: Hardware-aligned and natively trainable sparse attention. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, 2025. arXiv:2502.11089.
- [46]Yanke Zhou, Yiduo Li, Hanlin Tang, Maohua Li, Kan Liu, Tao Lan, Lin Qu, Yuan Yao, and Xiaoxing Ma. Full attention strikes back: Transferring full attention into sparse within hundred training steps. arXiv preprint arXiv:2605.16928, 2026.arxiv.org/abs/2605.16928


















