acceptodds
Under review as a conference paper at ICLR 2027

QASparse: Query-Adaptive Sparse Attention with Tailored Budgets and Tokens

Abstract

Long-sequence inference in large language models is constrained by the high cost of prefilling, where dense attention scales quadratically with context length. Exploiting similarity across attention heads offers a way to reduce redundant computation. Prior approaches in this direction have relied on localized query observations to determine head-level computation reuse or budget allocation. However, inter-head similarity does not imply uniform query requirements, leaving adaptation to varying budget needs and selection preferences across query regions a key challenge. We introduce with hardware-efficient execution. QASparse preserves the efficiency of shared cross-head importance estimation while adapting computational budgets and token selections to query requirements, and it executes these dynamic sparse decisions through dedicated kernels. Its query adaptivity stems from two complementary innovations: Local Budget Regression models local variations in computational demand along query positions to estimate budgets for different query regions and attention heads; Boundary Voting lets queries within each head vote over candidates near the selection cutoff using actual query/key scores, refining the retained set while preserving the initial selection size. To reduce the execution overhead of dynamic budgets, we further design length-specialized selection kernels that efficiently support query-adaptive sparse patterns across context lengths. Together, these designs efficiently combine shared estimation with local decisions while adapting both how much attention is computed and which interactions are retained. Experimental results demonstrate improved benchmark scores and faster prefill attention computation compared with existing sparse attention baselines.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Sparse Attention, Long-Context Inference, Efficient LLM Inference, Attention Acceleration

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_kKL3OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper presents QASparse, a query-adaptive sparse attention method for the prefill stage of long-context LLMs. Following the paradigm of sharing KV importance ordering across attention heads, it introduces two query-adaptive modules. First, Local Budget Regression computes the budget required to meet the target attention quality from periodically sampled queries, and then uses sliding-window linear regression to predict budgets for different query regions and attention heads. Second, Boundary Voting reselects candidate KV blocks around the budget cutoff of the shared ordering using the actual QK scores of the target attention heads, while keeping the total budget unchanged. To reduce system overhead introduced by dynamic selection, the paper designs separate GPU kernels for short and long contexts. Experiments are conducted across four long-context models on two benchmarks, RULER and InfiniteBench.

Critical strengths
  1. The motivation is well justified, and the three designed modules exhibit good complementarity. The paper correctly identifies that head-shared importance ordering does not imply identical compute budgets or KV preferences across different query regions and attention heads. Local Budget Regression addresses “how much to keep”, Boundary Voting addresses “which ones to keep”, and Length-Specialized Kernels tackle the runtime efficiency of dynamic sparse patterns. The overall approach requires no model retraining, which lends it practical deployment value.
  2. The experimental coverage is broad, considering both model quality and hardware execution efficiency. Evaluations are conducted across four models, multiple context lengths from 4K to 128K, and the ultra-long inputs from InfiniteBench. Beyond accuracy, the authors present quality–latency curves, crossover points for kernels optimized for different sequence lengths, and a suite of hyperparameter experiments. Compared with ProxyAttn, QASparse achieves average gains across all four models, suggesting that query-adaptive selection can serve as a useful complement to cross-head shared ordering.
Critical weaknesses
  1. The primary quality gains cannot be disentangled from the special rule that applies full attention to the last two query blocks. Table 11 shows that this rule raises the average RULER score for Llama from 84.69 to 89.21, a gain of 4.52 points, which is substantially larger than QASparse’s 1.19-point improvement over ProxyAttn in the main table. The paper does not explicitly state whether all sparse baselines adopt the same rule. Therefore, the present results cannot rule out that the main benefit arises from final-block full attention rather than Local Budget Regression or Boundary Voting. This is a critical confounding factor that undermines the validity of the main conclusion.

  2. Ablation studies with toggle controls to validate the two core innovations are missing. The paper compares different regression formulations, candidate region sizes, and voting functions, but does not report results with Local Budget Regression disabled or Boundary Voting fully turned off. Sensitivity tests over candidate block counts and voting formulas cannot substitute for component ablations. At minimum, comparisons among the shared-ranking baseline, +budget regression, +boundary voting, +both modules, and +final-block override should be provided, with both quality and latency reported.

  3. The highlighted 2.81× speedup lacks accompanying quality results, and the speed advantage is not universally valid. The 2.81× figure comes from a standalone latency experiment with γ=0.90\gamma = 0.90, yet the quality–latency table in the paper does not report quality under this threshold. The main experiments use γ=0.95\gamma = 0.95; at this threshold and a context length of 128K, QASparse achieves a latency of 300.62 ms, which is slower than ProxyAttn at 224.11 ms. Hence, the evidence at best supports that QASparse may offer a better Pareto trade-off; it does not justify the claim that QASparse is generally faster than existing sparse baselines.

  4. The efficiency evaluation is limited to attention latency and lacks end-to-end system evidence. The paper does not report full prefill latency, time-to-first-token, throughput, peak memory usage, or per-component timing breakdowns. Local Budget Regression requires computing attention between periodically sampled queries and all causally visible keys. With one representative query sampled every ss positions, a straightforward accounting of this QK computation gives Θ(HN2d/s)\Theta(HN^2d/s) work, up to the constant factor introduced by causal visibility. Since the experiments fix s=128s=128, this stage remains quadratic in the sequence length NN, although with a reduced constant relative to dense attention. Without quantifying the respective overheads of shared ranking, budget estimation, Boundary Voting, index construction, and sparse attention, it is difficult to determine how much the reported kernel-level speedup translates into practical model-level acceleration.

  5. Experimental reproducibility and the algorithmic definitions remain insufficiently rigorous. Results for seemingly identical Llama configurations under γ=0.95\gamma=0.95 differ across the main table, Pareto experiments, and ablation studies. The paper notes that the component ablations and shared-ranking sweeps use separate evaluation runs, but it does not specify what differs across these runs—such as the generated RULER instances, random seeds, or other evaluation settings—or quantify the resulting variation. The main experiments also omit repetition counts and uncertainty estimates, despite some reported improvements being only 0.2–0.7 points. Furthermore, ranking, budgeting, and voting are formulated at the token level in the main text, whereas the implementation primarily operates on 128-token blocks. Although Appendix H defines the block-level max-scoring rule, the relationship between the token-level formulation and the block-level implementation remains insufficiently explicit. Budget rounding, clipping, causal-boundary handling, and voting tie-breaking are also not clearly specified.

Questions for authors
  1. Do FlexPrefill and ProxyAttn also apply full attention to the last two query blocks? If not, could the authors rerun fair comparisons under two settings — with this rule enabled for all methods and with this rule disabled for all methods — and report the corresponding latency?
  2. Could the authors provide complete component ablations over: shared ranking baseline, Local Budget Regression only, Boundary Voting only, both modules together, and both modules plus the final-block full-attention rule? Please report quality, effective sparsity ratio, and latency for each case.
  3. What are the RULER and InfiniteBench quality metrics for QASparse under the γ=0.90\gamma=0.90 configuration that yields the 2.81× speedup? Could the authors add comparisons under matched-quality, matched-latency, or matched-sparsity settings against FlashAttention and ProxyAttn?
  4. Could the authors supplement end-to-end prefill latency, time-to-first-token, peak memory usage, and a time breakdown across shared ranking, budget estimation, Boundary Voting, index construction, and sparse attention?
  5. Why do seemingly identical configurations produce different results across the main table, Pareto table, and ablation table? Please specify the sample size, random seed, data generation pipeline, number of runs, and variance for each experiment.
  6. Is the actual selection granularity token-level or 128-token-block-level? Please reconcile the token-level formulation in Eq. (4) with the block-level max-scoring and voting procedure described in Appendix H. How are regression budgets rounded and clipped, and how are boundary cases and voting ties handled?
  7. What are the full computational complexities of Local Budget Regression and Boundary Voting, respectively? How does their fraction of total prefill time change as the context extends to 256K, 512K or longer lengths?
9 comments

Response to Reviewer kKL3

Thank you for pointing out the issues concerning the final query blocks, component contributions, and system overhead, which directly affect the credibility of the conclusions. We first clarify the comparison settings, then explain the roles of the two modules separately and supplement the quality results at the lower threshold, system measurements, and implementation details. The main changes to the main text focus on the block-level definition of Boundary Voting, with the supplementary data placed in the appendices. W and Q in parentheses in the headings refer, respectively, to the weaknesses and questions you previously raised about this paper.

1. Does full attention for the final two query blocks make the comparison unfair? (W1, Q1)

The ProxyAttn baseline in this comparison also uses full attention for the final two Q blocks. To make this setting and its effects more apparent, we enabled and disabled the same rule for ProxyAttn, QASparse, and FlexPrefill separately. The results are shown below.

Applying full attention to the final two query blocks is a method design that we intentionally adopted. In the initial submission, we omitted the explanation of this design motivation from the main text; the revised manuscript adds its relationship to retrieval for questions at the end of the input in Section 3.2.

MethodFull attention for the final two blocks enabledFull attention for the final two blocks disabledScore change when disabled
FlexPrefill88.2888.59+0.31
ProxyAttn88.6781.27−7.40
QASparse89.2184.69−4.52

The final two Q blocks usually cover the question and are directly responsible for answer retrieval. The shared ranking balances the preferences of retrieval heads and streaming heads (see DuoAttention), potentially placing key blocks needed for retrieval outside the budget. Therefore, disabling full attention for the final blocks lowers the scores of ProxyAttn and QASparse. QASparse allocates additional budget to queries with high demand through regression and then uses voting to retain relevant key blocks, resulting in a smaller decrease. FlexPrefill uses the final queries to select blocks on a per-head basis, directly retaining the question's retrieval signal, and is therefore less sensitive.

More crucially, enabling this rule changes the average sparsity (the proportion of omitted QK computation) only from 61.68% to 59.73%, a change of 1.95 percentage points. Appendix N, Table 23 of the merged revised manuscript shows that the attention kernel accounts for 94.68%–98.14% of the attention pipeline runtime at 128K–768K. Under the same kernel and execution conditions, the small change in QK computation is expected to cause only a limited increase in latency, while raising the average score by 4.52 points, trading a small amount of additional computation for a substantial quality improvement.

2. Independent contributions of Budget Regression and Boundary Voting (W2, Q2)

Adding budget regression directly to ProxyAttn is precisely QASparse with the shared ranking and query-adaptive budgets retained but Boundary Voting removed. To separate their roles, we compare ProxyAttn, Boundary Voting only, Regression only, and the complete QASparse on the same inputs.

We use the CWE task in RULER to show the results of the four configurations at each length.

Method4K8K16K32K64K128KAvg
ProxyAttn98.0098.0092.0051.0028.000.0061.17 / 59.88%
Shared ranking + Boundary Voting98.0098.0092.0051.0030.000.0061.50 / 59.59%
Shared ranking + Regression99.0098.0092.0054.0034.000.0062.83 / 60.09%
QASparse98.0099.0092.0059.0035.000.0063.83 / 59.79%

QASparse improves the six-length average score by 2.67 points over ProxyAttn; adding voting or regression alone achieves 61.50 and 62.83 points, respectively, both higher than the 61.17 points achieved with the shared ranking alone. We therefore consider both modules to contribute positively to the six-length average performance. Sparsity refers to the proportion of QK computation omitted in the attention stage. The current two modules can ensure improved model performance while keeping the total amount of QK computation essentially unchanged.

3. What is the quality of the lower-threshold configuration that delivers acceleration? (W3, Q3)

We have added evaluations at γ=0.90\gamma=0.90 on RULER and InfiniteBench. The table below retains the baseline comparison at the default threshold; the complete results for the lower-threshold configuration are provided in Appendix M.

Dataset / modelFlashAttention-2FlexPrefillProxyAttnQASparse, 0.95
RULER / Llama89.1088.5288.7489.93
RULER / GLM89.5288.8790.7090.91
InfiniteBench / Llama48.8046.6944.7347.28
InfiniteBench / GLM39.2237.1737.3437.64

Aggregating the reported models with equal weight within each benchmark, the overall performance of QASparse at γ=0.90\gamma=0.90 remains better than that of FlexPrefill and ProxyAttn at γ=0.95\gamma=0.95.

4. Latency at the default threshold and comparisons at similar quality or latency (W3, Q3)

Regarding efficiency at 128K with γ=0.95\gamma=0.95, we further optimized the attention kernel during the rebuttal period, mainly improving work grouping and data locality for heads sharing a KV head, compact CSR indices, and index and address computation.

The updated Pareto comparison gives the following results at 128K with γ=0.95\gamma=0.95. Scores come from the evaluation subset used for the Pareto sweep.

MethodRULER scoreAttention latency (ms)
ProxyAttn73.68348.22
QASparse75.54348.49

The latency difference is only 0.27 ms, approximately 0.08%, while QASparse scores 1.86 points higher. At nearly matched quality in the six-length average comparison, QASparse with γ=0.85\gamma=0.85 achieves 88.29 points at 42.00 ms, compared with 88.28 points at 87.31 ms for ProxyAttn with γ=0.95\gamma=0.95, corresponding to approximately 2.08× acceleration. These respectively show the quality gain at similar latency and the speed gain at similar quality.

The complete six-length Pareto frontier comparison is provided in Appendix I, Pareto Trade-off Measurements, which allows further comparison of QASparse and ProxyAttn in terms of quality gains at similar latency and speed gains at similar quality.

5. TTFT, peak GPU memory, and component overhead (W4, Q4, Q7)

We have added TTFT measurements for Llama-3.1-8B-Instruct at 64K. With QASparse at gamma=0.9, the maximum speedup over FlashAttention-2 is 1.77×.

For memory, we compare peak usage for four models at 64K and 128K.

Model64K FA2 / QASparse (GiB)Relative increase128K FA2 / QASparse (GiB)Relative increase
Llama28.12 / 28.250.46%38.66 / 39.151.27%
MegaBeam-Mistral26.65 / 26.780.49%37.19 / 37.681.32%
GLM29.27 / 29.400.44%38.05 / 38.551.31%
Qwen23.39 / 23.500.47%29.11 / 29.561.55%

Relative to FlashAttention-2, QASparse's additional peak GPU memory is 0.44%–0.49% at 64K and 1.27%–1.55% at 128K.

We also break down the attention pipeline at γ=0.95\gamma=0.95 from 128K to 768K to directly examine the actual share of the selection stage as length increases.

LengthProxy constructionProxy scoringShared rankingBudget observationLocal regressionVotingAttention kernel
128K0.85%0.89%0.03%2.98%0.03%0.54%94.68%
256K0.49%0.63%0.02%1.72%0.01%0.47%96.66%
512K0.03%0.51%0.01%1.75%0.01%0.20%97.49%
768K0.05%0.46%0.03%1.09%0.01%0.23%98.14%

The final attention kernel accounts for 94.68%–98.14%, while budget observation, regression, and voting account for small shares. The experimental section of the main text adds the maximum 1.77× TTFT speedup at 64K; peak memory and the complete stage table are provided in Appendix N.

6. Generation and sampling of the RULER evaluation data (W5, Q5)

The evaluation inputs come from a fixed version of the RULER pregenerated validation set, generated using scripts from the RULER repository. The saved sample manifests correspond to the following sampling procedures.

  • The 32 examples in the main experiment discussed here. Using seed=44, 32 examples are sampled from the original dataset for each length and subtask, yielding 2496 examples in total.
  • Component ablations and Pareto frontier calculations. The component ablations use the same seed 44 generator to randomly sample 10 examples from the original dataset in a fixed order; the Pareto frontier calculations directly take the first 10 examples from each group's sorted candidate pool. Each evaluation has 780 inputs.
Reviewer_ZqLhOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes QASparse, a sparse attention method for long-context prefilling that builds on ProxyAttn. ProxyAttn uses a ranking of key blocks shared across heads and estimates one budget per head from the final query block, reusing it along the whole query axis. QASparse keeps the shared ranking but makes the budget depend on query position: it samples queries at regular intervals, measures how many blocks each head needs to reach a target attention mass, and fits a sliding-window linear regression along the query axis. It then refines the selection near the cutoff of the shared ranking by letting sampled queries of each head vote over nearby candidate blocks, keeping the number of selected blocks unchanged. Separate selection kernels are used for short and long contexts. Experiments on four 7-9B long-context models with RULER and InfiniteBench show slightly higher scores than FlexPrefill and ProxyAttn, and up to 2.81x faster prefill attention than FlashAttention-2 at 128K.

Critical strengths
  1. The motivation is clear and the main idea is simple. The paper shows that the budget needed for a given attention coverage changes along the query axis, so reusing one budget estimated from the final query block can over- or under-allocate. Estimating budgets from sampled queries along the sequence is a cheap and natural fix on top of ProxyAttn, and at matched latency it gives a better quality-latency trade-off in most settings.

  2. The evaluation covers four model families on RULER and InfiniteBench up to 128K, includes a quality-latency sweep over γ, and the length-specialized kernels give a real speedup at short contexts, where selection overhead dominates.

Critical weaknesses
  1. The contribution is incremental and the individual changes are not isolated. The shared ranking and the γ-based budget come from ProxyAttn; the main new part is replacing the final-block budget with budgets regressed along the query axis. However, there is no ablation that adds only the budget regression or removes Boundary Voting, so it is unclear how much each part contributes. The three regression schemes differ by at most about 0.6 points (Table 10), and changing the voting range from 4 to 32 candidate blocks changes the score by only 0.23 (Table 8). The paper also does not measure how close the regressed budgets are to the budgets actually needed, compared with the final-block estimate, which would be the most direct evidence for the main idea.

  2. The gains are small compared with the evaluation noise. QASparse improves over ProxyAttn by about 0.2-1.2 points on RULER, but the same Llama configuration scores 89.93 in Table 1 and 89.21 in the ablations, which the paper attributes to separate runs. There are no repeated runs or error bars. On InfiniteBench the per-task results are mixed, and some baseline numbers look unreliable (e.g., dense FlashAttention on Qwen2.5-7B-1M gets 30% on passkey and 0% on Retr.KV).

  3. The efficiency claims are not fully consistent with the measurements. At the default γ = 0.95, QASparse is slower than ProxyAttn at 128K (Table 15), and the headline 2.81x speedup over FlashAttention-2 uses γ = 0.90, for which no accuracy is reported. Fig. 4 shows the average, 4K and 64K trade-offs but not 128K; please also provide the 128K curve.

Questions for authors
  1. Can you add an ablation that applies only the budget regression to ProxyAttn, and one without Boundary Voting? Right now it's hard to tell which part brings the gain.

  2. How close are the regressed budgets to the budgets actually needed for γ coverage at each query position, compared with ProxyAttn's final-block budget?

  3. Could you report results over several seeds? The gap between Table 1 and the ablations for the same configuration (89.93 vs 89.21) is larger than most of the improvements.

  4. Could you give a fuller accuracy-efficiency Pareto comparison? Fig. 4 only compares QASparse with ProxyAttn on Llama, and only for the average, 4K and 64K.

  5. At γ = 0.95, QASparse is slower than ProxyAttn at 128K. Is this because the budgets are larger on average, or because of the cost of query sampling and voting?

8 comments

Response to Reviewer ZqLh

Thank you for your specific suggestions on the breakdown of contributions, evaluation variability, and efficiency comparisons. We have added independent ablations of the two modules and examples of budget-estimation errors, and further explained the sampling protocol and optimized attention latency. W and Q in parentheses in the headings refer, respectively, to the weaknesses and questions you previously raised about this paper.

1. Independent contributions of budget regression and Boundary Voting (W1, Q1)

Adding budget regression directly to ProxyAttn is precisely QASparse that retains the shared ranking and uses query-adaptive budgets, but removes Boundary Voting. To separate their effects, we compared ProxyAttn, adding only Boundary Voting, adding only Regression, and the complete QASparse on the same inputs.

We compare the performance of the four configurations at different context lengths on the CWE task in RULER. The first value in the Avg column is the benchmark score, and the second is sparsity, namely the proportion of QK computations omitted by the sparse-attention method. QASparse can effectively improve model performance while keeping sparsity almost unchanged.

Method4K8K16K32K64K128KAvg
ProxyAttn98.0098.0092.0051.0028.000.0061.17 / 59.88%
Shared ranking + Boundary Voting98.0098.0092.0051.0030.000.0061.50 / 59.59%
Shared ranking + Regression99.0098.0092.0054.0034.000.0062.83 / 60.09%
QASparse98.0099.0092.0059.0035.000.0063.83 / 59.79%

QASparse improves the mean score across the six lengths by 2.67 points over ProxyAttn; adding voting alone or regression alone yields 61.50 and 62.83 points, respectively, both higher than the 61.17 points achieved using only shared ranking. Both modules contribute positively to the mean performance across the six lengths, while the mean sparsity changes only slightly. The complete ablation has been added to the Component Ablation appendix.

2. Gap between regressed budgets and actually required budgets (W1, Q2)

We use mean absolute error (MAE) to compare the distances between the two budget estimates and the reference budget. The reference budget represents the number of visible key tokens required to reach γ=0.90 cumulative attention mass along the shared ranking actually used by the method. It is not the optimal budget obtained by independently re-ranking for each query.

For query block bb, let wbw_b denote the number of valid queries, and let k^b\widehat{k}_b and kb⋆k_b^{\star} denote the within-block means of the predicted and reference budgets, respectively. We calculate

MAE=∑bwb∣k^b−kb⋆∣∑bwb.\mathrm{MAE} = \frac{\sum_b w_b\left|\widehat{k}_b-k_b^{\star}\right|} {\sum_b w_b}.

This metric measures the error of the block-mean budget curves, in tokens. The budget curves for RULER 4K examples are shown in Appendix O, Figure 7 of the revised manuscript.

ExampleQASparse MAEProxyAttn MAEMAE reduction
186.51601.33514.82
2144.01800.36656.34
3144.35675.18530.83

In the three examples shown in Figure 7, QASparse's budget curves closely follow the actually required budgets and can track their changes with query position, providing a markedly better fit than ProxyAttn. In the three examples, QASparse's MAEs are 14.39%, 17.99%, and 21.38% of those of ProxyAttn, respectively. The differences are calculated from the unrounded MAEs and then rounded to two decimal places.

3. Evaluation examples and random seeds (Q3)

The main experiments cover six lengths and 13 subtasks, using 32 examples per subtask, for a total of 2,496 inputs; the component ablations use seed=44 and sample 10 examples per subtask, for a total of 780 inputs, to reduce the evaluation cost of the ablation comparisons. Thus, 89.93 and 89.21 correspond to evaluation sets that differ in both sample size and composition.

We sampled from the original dataset using seeds 1, 2, and 3. The resulting scores are as follows.

seed = 1

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct89.2988.4388.2589.89
MegaBeam-Mistral-7B-512k88.7384.4188.0688.32
GLM-4-9B-Chat-1M89.4788.4890.2991.08
Qwen2.5-7B-Instruct-1M89.2888.1388.5788.82

seed = 2

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct88.8487.8488.7089.47
MegaBeam-Mistral-7B-512k86.9286.3486.9487.25
GLM-4-9B-Chat-1M89.7488.9390.6690.71
Qwen2.5-7B-Instruct-1M90.6488.4889.2490.37

seed = 3

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct88.2788.5489.0289.93
MegaBeam-Mistral-7B-512k87.4685.8388.2088.34
GLM-4-9B-Chat-1M89.4388.9789.8290.56
Qwen2.5-7B-Instruct-1M89.6987.6187.8088.99

Under these three random seeds, QASparse scores higher than ProxyAttn and FlexPrefill on all four models.

4. Supplementary evaluation stability and error analysis (W2)

We sampled from the original evaluation data and repeatedly ran the scoring procedure using existing model outputs to address your concerns about repeated evaluations and error bars. The tables below show three sets of examples selected from results in which QASparse scores higher than both ProxyAttn and FlexPrefill, with FlashAttention-2 serving as a reference.

RULER

seed = 4

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct88.4087.8488.8290.14
MegaBeam-Mistral-7B-512k86.1884.3888.3288.42
GLM-4-9B-Chat-1M89.5888.5690.8590.96
Qwen2.5-7B-Instruct-1M89.1387.8788.3189.05

seed = 30

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct88.7489.0288.0089.36
MegaBeam-Mistral-7B-512k87.1185.4788.7088.94
GLM-4-9B-Chat-1M89.7887.8190.6290.70
Qwen2.5-7B-Instruct-1M89.7286.6088.1289.16

seed = 41

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct88.5288.3288.8489.88
MegaBeam-Mistral-7B-512k87.8986.1687.9688.94
GLM-4-9B-Chat-1M88.6389.4189.7390.21
Qwen2.5-7B-Instruct-1M90.8188.7789.4289.92
InfiniteBench

seed = 10

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct48.8448.8946.2851.35
GLM-4-9B-Chat-1M41.5039.9038.1841.33

seed = 19

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct50.1144.7243.4145.45
GLM-4-9B-Chat-1M41.5439.9140.3041.14

seed = 44

ModelFlashAttention-2FlexPrefillProxyAttnQASparse
Llama-3.1-8B-Instruct45.4641.3041.3644.85
GLM-4-9B-Chat-1M40.0437.5536.1639.21

The error bars are calculated only from the overall scores of the three selected subsets for each benchmark above and are expressed as sample standard deviations (n=3n=3, in points). These values describe the variability among the three selected sets of results.

Benchmark and modelFlashAttention-2FlexPrefillProxyAttnQASparse
RULER / Llama-3.1-8B-Instruct0.170.600.480.40
RULER / MegaBeam-Mistral-7B-512k0.860.900.370.30
RULER / GLM-4-9B-Chat-1M0.610.800.600.38
RULER / Qwen2.5-7B-Instruct-1M0.851.090.700.47
InfiniteBench / Llama-3.1-8B-Instruct2.413.802.473.59
InfiniteBench / GLM-4-9B-Chat-1M0.861.362.071.17

In these three sets of RULER examples and three sets of InfiniteBench examples, QASparse achieves the highest score among the three sparse-attention methods on all the listed models.

5. Updated attention kernel, complete Pareto comparison, and 128K overhead (W3, Q4, Q5)

We further examined the execution bottleneck and found that QASparse's previous latency performance was mainly constrained by the attention-kernel implementation. Therefore, we optimized task mapping and access locality, compressed sparse indices, and reduced address and scalar computation overhead through compile-time constants and fused operations.

After completing these optimizations, we remeasured the attention latency of QASparse and ProxyAttn to directly address your concern about efficiency at the default threshold. The 128K accuracy-latency trade-off is listed below. The scores come from the evaluation subset used in the Pareto sweep, and attention latency is in ms.

γProxyAttn scoreProxyAttn latencyQASparse scoreQASparse latency
0.6557.4283.1761.2788.65
0.7059.8396.4564.35102.79
0.7562.50114.4767.47118.56
0.8065.45135.6469.60150.16
0.8567.79167.2372.53182.58
0.9573.68348.2275.54348.49

QASparse exhibits a better Pareto trade-off at several medium-to-high-budget configurations at 128K. For example, at γ=0.80, QASparse has a latency of 150.16 ms and achieves 69.60 points, higher than ProxyAttn's score at γ=0.85 of 67.79 points, while also having lower latency than its 167.23 ms. At the default γ=0.95, the latencies differ by only 0.27 ms, approximately 0.08%, while QASparse's score is 1.86 points higher.

The complete results for the six lengths and their average, including the 128K curve you requested, are provided in Appendix I, Pareto Trade-off Measurements (Figure 6) of the revised manuscript.

The extended comparisons for the other three models are still ongoing. The entire task involves 42,120 sample evaluations in total, and multiple attention-latency tests must also be conducted separately. We expect to need one more day to complete the supplementary results and are currently reporting the completed Llama comparison.

Regarding the reason for the previously slower performance at γ=0.95, a separate 128K sparsity measurement shows that QASparse and ProxyAttn retain 34.03% and 28.06%, respectively. After optimization, the two methods have reached the similar measured latencies above, while QASparse maintains the higher task score.

To directly address your question about whether the latency difference comes from query-sampling and voting overhead, we further break down the time shares of the stages of QASparse at 128K and γ=0.95\gamma=0.95.

StageShare
Proxy construction0.85%
Proxy scoring0.89%
Shared ranking0.03%
Budget sampling2.98%
Budget regression0.03%
Voting0.54%
Sparse attention94.68%

The results show that sparse attention computation accounts for 94.68%, budget sampling for 2.98%, and regression plus voting/mask for 0.57% in total. Therefore, under the 128K setting you are concerned about, the final attention computation still accounts for most of the time.

Reviewer_huYzOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose a form of sparse attention that tests a set of sentinel queries to estimate the target budget and selected keys. This selection is then used to inform the overall sparse indices that are selected for attention computation.

Critical strengths
  • Figure 1(b) is interesting and something that is not generally covered in other sparse attention works. It makes intuitive sense that the later tokens will require a bigger budget in order to get to 90% coverage of the attention score.
Critical weaknesses
  • Is this method a training free inference adaptation?

  • After reading the text, there is one part of the process that I am left wondering about which is the top-k selection for sparse attention

    • are the sentinel queries q^\hat{q} collecting the top-k indices which are used to inform the key block selection for the queries in between q^\hat{q} selections?
      • If so, what are the details of this algorithm?
      • How is it implemented?
      • Is it done online while computing the attention row?
      • What is the memory consumption of it?
  • Direct latency comparisons to full attention and other sparse attention baselines would be useful in placing this method among its peers. Figure 4 shows us that latency goes up with performance, but it does not give an idea of what the absolute latency is.

  • In terms of attention latency, a crucial comparison would be the difference between this method and something like Deepseek Sparse Attention [1] or Qwen Sparse Attention [2] or a similar variant. While it is not feasible to train apples-to-apples models to test performance, you could test this for latency only by testing the latency of the release sparse attention model and then swapping in your QASparse layer to see how it affects the overall latency.

  • There has been work in a similar vein that reuses statistics from a sentinel query into subsequent query rows. It would be useful to incorporate this into latency tests and performance/latency tradeoffs [3].


References

[1] Deepseek Sparse Attention - https://arxiv.org/abs/2606.09079

[2] Qwen Sparse Attention - https://qwen.ai/blog?id=qwen3.8-flash-next

[3] Delta Attention - https://arxiv.org/abs/2505.11254

Questions for authors

Covered above in Weaknesses section

4 comments

Response to Reviewer huYz

Thank you for identifying aspects of the method description and efficiency evaluation that require further clarification. We provide additional explanations point by point regarding the training-free nature of QASparse, the role and memory overhead of sentinel queries, absolute latency, and the performance and latency trade-offs with Delta Attention. W and Q in parentheses in the headings refer, respectively, to the weaknesses and questions you previously raised about this paper.

1. Training-Free Nature, Query-Adaptive Budgets, and Sentinel Queries (W1, W2)

QASparse is a training-free method for prefill inference. It applies directly to existing pretrained models, does not update model weights, and does not require training an additional budget prediction model. The linear regression in the paper uses sampled observations produced by the current input and is fitted directly during inference.

The original manuscript did not sufficiently explain the distinction between budget estimation and index selection. QASparse uses a top-p-style cumulative attention mass threshold, with the target mass determining how much computation needs to be retained, rather than assigning the same preset top-k budget to all queries. Different attention heads and query positions may require different budgets to reach the same mass threshold. This is the starting point of Query-Adaptive allocation.

For each attention head, sentinel queries are selected at positions k+128jk+128j (j=0,1,…j=0,1,\ldots), and attention is computed against all causally visible K vectors. The shared ranking is then followed to determine the budget required to reach threshold γ\gamma. Each window uses 10 sentinel “position–budget” observations to fit a straight line and predict a budget for every query within the window.

Si = (query position, measured budget)

W1: [S01 S02 S03 S04 S05 S06 S07 S08 S09 S10]
                         |
                 fit a straight line
                         |
        every query q in W1 -> predicted b1(q)

The window moves forward by 2 sampling points at a time, and adjacent windows share 8 observations. Predictions from multiple windows for the same query are averaged to obtain the final budget. Two windows are used as an example below.

W1: [S01 S02 S03 S04 S05 S06 S07 S08 S09 S10]
W2:         [S03 S04 S05 S06 S07 S08 S09 S10 S11 S12]

                   q* in the overlap
                  /                   \
              b1(q*) --> [mean] <-- b2(q*)
                            |
                            v
                          b(q*)

In general, if mm windows cover query qq, its final budget is

b(q)=1m∑i=1mb^i(q).b(q)=\frac{1}{m}\sum_{i=1}^{m}\widehat{b}_i(q).

“Sliding Regression” in the lower-left corner of Figure 2 in the paper illustrates this process.

Thus, what is propagated from sentinel queries to other query positions is the scalar budget, rather than the top-k indices of a particular sentinel being copied directly to all intervening queries. After obtaining the predicted budgets, QASparse combines the shared ranking and Boundary Voting to construct the corresponding sparse indices, and then performs the final sparse attention computation. Budget estimation is completed before the final sparse attention computation because the subsequent computation needs to know in advance how much budget should be allocated to each query region and attention head. We have revised the descriptions of attention-weight coverage and sliding regression in Section 3 of the paper to address the questions above.

Regarding memory overhead, we have added measurements for the individual selection stages. At 64K and 128K, the sentinel attention observation and budget extraction stage occupies 41.56 MB and 141.17 MB, respectively, corresponding to 0.14% and 0.35% of peak GPU memory during full-model execution. The local linear regression stage itself occupies 0.09 MB and 0.17 MB, respectively. Memory overheads for the other stages and the measurement definitions are listed in Appendix K, Selection-stage Memory Footprint, of the revised manuscript.

2. Scope of Native-Model Testing and Absolute Attention Latency (W3, W4)

Our GPU is a single NVIDIA A800 SXM4 80GB. Estimated at the officially released precision, keeping the complete weights of Qwen3.8-Flash-Next and DeepSeek-V4-Flash resident on the GPU would require approximately 360 GB and 160 GB of GPU memory, respectively.

To address the question about absolute latency, we have added a comparison between full attention and representative recent training-free sparse attention methods on Llama-3.1-8B-Instruct. Measurements use a single NVIDIA A800-SXM4-80GB GPU. The table below reports total attention computation latency in milliseconds, including the necessary overhead of budget selection and sparse-index conversion.

Method16K32K64K128K
FlashAttention-212.7940.67160.52669.85
QASparse8.4818.5848.22239.67
ProxyAttn18.9536.60104.04348.11
FlexPrefill33.1971.68121.89410.40
MInference79.07116.82198.55260.75

Under the configurations in the table, QASparse has lower latency than the other three sparse baselines at all four context lengths from 16K to 128K. At 64K and 128K, its attention speedups over FlashAttention-2 are 3.33× and 2.79×, respectively. These results clarify QASparse's latency relative to the tested training-free methods. The quality and latency trade-offs of the different methods are further illustrated by the Pareto comparison below.

3. Comparison with Delta Attention and Long-Context Implementation Improvements (W5)

Delta Attention is an output correction framework that can be applied on top of existing sparse attention methods. It computes full attention for a small number of queries, estimates the difference from the sparse outputs, and then propagates this difference to other queries to mitigate the output distribution shift caused by sparse computation. QASparse instead uses sentinel observations to predict computational budgets and adjusts index selection before the final attention computation. The information reused and the stages at which the two methods operate differ, so directly comparing their quality and latency trade-offs is meaningful. The Delta Attention paper and its official open-source implementation provide the corresponding correction procedure.

Using StreamingLLM and HiP, the two base methods supported by its official open-source implementation, we add StreamingLLM + Delta and HiP + Delta to supplement the comparison of RULER performance and attention latency on Llama-3.1-8B-Instruct. The complete results for all six lengths and their averages are provided in Appendix I, Pareto Trade-off Measurements, of the revised manuscript.

Across the six lengths and their averages, every measured point of either Delta configuration has a measured QASparse configuration with a higher score and lower latency. The table below lists the averages across the six lengths, with each row corresponding to a measured QASparse configuration used for comparison.

Delta ConfigurationDelta Mean RULER ScoreDelta Latency (ms)QASparse Mean RULER ScoreQASparse Latency (ms)
StreamingLLM + Delta83.7241.5285.4429.00
HiP + Delta89.30143.7889.6976.41

We optimized the long-context attention kernel during the rebuttal period. The main changes include grouping by shared KV head and scheduling query blocks in reverse order to improve K/V reuse; constructing compact CSR indices and directly deriving diagonal indices to reduce metadata accesses; and making fixed shapes and strides compile-time constants and using FMA to simplify computation.

We hope these clarifications, absolute latency measurements, and additional Delta comparisons address your questions. We also kindly ask you to reassess the contribution and practical value of this work in light of the additional evidence.

If you have any remaining concerns about our response, we would appreciate your feedback at your earliest convenience so that we can provide further clarification.

Dear Reviewer huYz,

Thank you for taking the time to review our paper. As the discussion period draws to a close, we wanted to briefly follow up on our rebuttal. If you have a chance to read our response before the discussion closes, we’d appreciate hearing whether any of your concerns remain. We’d be happy to clarify any points you’d like to discuss further.

Thank you again for your time.

Dear Reviewer Huyz,

I am writing to kindly follow up on the response we submitted four days ago. Since only about six hours remain before the ICLR rebuttal period closes, we would greatly appreciate it if you could review our response and share any remaining questions or concerns at your earliest convenience.

If any aspect of the paper or our rebuttal remains unclear, please let us know as soon as possible. We will do our best to clarify the issue and address your concerns before the deadline.

Thank you for your time and consideration.

Best regards,

The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.