- 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
- 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.
- 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
-
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.
-
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.
-
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 , yet the quality–latency table in the paper does not report quality under this threshold. The main experiments use ; 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.
-
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 positions, a straightforward accounting of this QK computation gives work, up to the constant factor introduced by causal visibility. Since the experiments fix , this stage remains quadratic in the sequence length , 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.
-
Experimental reproducibility and the algorithmic definitions remain insufficiently rigorous. Results for seemingly identical Llama configurations under 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
- 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?
- 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.
- What are the RULER and InfiniteBench quality metrics for QASparse under the 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?
- 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?
- 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.
- 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?
- 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
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.
| Method | 4K | 8K | 16K | 32K | 64K | 128K | Avg |
|---|---|---|---|---|---|---|---|
| ProxyAttn | 98.00 | 98.00 | 92.00 | 51.00 | 28.00 | 0.00 | 61.17 / 59.88% |
| Shared ranking + Boundary Voting | 98.00 | 98.00 | 92.00 | 51.00 | 30.00 | 0.00 | 61.50 / 59.59% |
| Shared ranking + Regression | 99.00 | 98.00 | 92.00 | 54.00 | 34.00 | 0.00 | 62.83 / 60.09% |
| QASparse | 98.00 | 99.00 | 92.00 | 59.00 | 35.00 | 0.00 | 63.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 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 / model | FlashAttention-2 | FlexPrefill | ProxyAttn | QASparse, 0.95 |
|---|---|---|---|---|
| RULER / Llama | 89.10 | 88.52 | 88.74 | 89.93 |
| RULER / GLM | 89.52 | 88.87 | 90.70 | 90.91 |
| InfiniteBench / Llama | 48.80 | 46.69 | 44.73 | 47.28 |
| InfiniteBench / GLM | 39.22 | 37.17 | 37.34 | 37.64 |
Aggregating the reported models with equal weight within each benchmark, the overall performance of QASparse at remains better than that of FlexPrefill and ProxyAttn at .
4. Latency at the default threshold and comparisons at similar quality or latency (W3, Q3)
Regarding efficiency at 128K with , 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 . Scores come from the evaluation subset used for the Pareto sweep.
| Method | RULER score | Attention latency (ms) |
|---|---|---|
| ProxyAttn | 73.68 | 348.22 |
| QASparse | 75.54 | 348.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 achieves 88.29 points at 42.00 ms, compared with 88.28 points at 87.31 ms for ProxyAttn with , 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.
| Model | 64K FA2 / QASparse (GiB) | Relative increase | 128K FA2 / QASparse (GiB) | Relative increase |
|---|---|---|---|---|
| Llama | 28.12 / 28.25 | 0.46% | 38.66 / 39.15 | 1.27% |
| MegaBeam-Mistral | 26.65 / 26.78 | 0.49% | 37.19 / 37.68 | 1.32% |
| GLM | 29.27 / 29.40 | 0.44% | 38.05 / 38.55 | 1.31% |
| Qwen | 23.39 / 23.50 | 0.47% | 29.11 / 29.56 | 1.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 from 128K to 768K to directly examine the actual share of the selection stage as length increases.
| Length | Proxy construction | Proxy scoring | Shared ranking | Budget observation | Local regression | Voting | Attention kernel |
|---|---|---|---|---|---|---|---|
| 128K | 0.85% | 0.89% | 0.03% | 2.98% | 0.03% | 0.54% | 94.68% |
| 256K | 0.49% | 0.63% | 0.02% | 1.72% | 0.01% | 0.47% | 96.66% |
| 512K | 0.03% | 0.51% | 0.01% | 1.75% | 0.01% | 0.20% | 97.49% |
| 768K | 0.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.
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.
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.