acceptodds
Under review as a conference paper at ICLR 2027

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 index construction and data movement, whole-model wall-clock speedups over dense attention are 2.3–2.4× for prefill and 1.7–2.0× for decoding at 512K tokens, and 2.9–3.0× for prefill at 1M. On five RULER tasks and LongBench-v2, the 35B-A3B model stays close to dense attention through 512K, 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
language models, Transformer, sparse attention, long context

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_fHmqOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces a training-free sparse attention approach for accelerating prefill and decoding in long-context LLM inference. It focuses on two challenges in training-free sparse attention: efficiently identifying relevant tokens for individual queries and executing irregular sparse attention patterns without excessive selection and memory-access overhead. The evaluation covers Qwen3.5-4B and Qwen3.5-35B-A3B, with experiments revealing superiority in inference latency and accuracy across long-context settings.

Critical strengths
  1. The problem is timely and the basic insight proposed makes sense.

  2. The solution is reasonable. The paper combines prompt-specific semantic clustering, per-query block selection, and KV-outer execution to accelerate both prefill and decoding without additional training. Previous clustering-based approaches have largely focused on decoding, whereas this method also uses the constructed semantic index during prefill. Coarse semantic blocks reduce the cost of block selection, and KV-outer execution improves KV reuse while allowing individual queries to select different blocks. The ablation results in Section 5.2 demonstrate the benefits of this design. At 512K context length, the proposed method achieves a better accuracy-latency trade-off than the evaluated positional-block baselines, particularly on multi-key retrieval tasks. Section 3.4 also reports a 2.6× speedup from KV-outer execution compared with processing neighboring queries over the union of their selected blocks on Qwen3.5-4B. The ability to combine query-specific selection with efficient execution is an important practical contribution, as irregular attention patterns often limit the performance gains of training-free sparse attention.

  3. The evaluation reports whole-model wall-clock latency and accounts for index construction and sparse attention overhead, making the measured performance improvements more representative of actual inference costs than attention-kernel results alone. On a single H200 GPU, the method achieves 2.3–2.4× prefill speedups and 1.7–2.0× decoding speedups at 512K tokens, with prefill speedups reaching 2.9–3.0× at 1M tokens. Accuracy evaluations on RULER, MRCR, and LongBench-v2 show that Qwen3.5-35B-A3B generally remains close to dense attention across several tested settings. The ablations in Section 5.3 further examine the relationship between block size and token budget. They show that larger blocks can reduce selection and execution overhead enough to accommodate a higher token budget, resulting in a better accuracy-latency trade-off than finer blocks in certain configurations. The reported whole-model improvements, together with the analysis of block granularity and token budget, provide evidence for the practical value of the approach in long-context inference.

Critical weaknesses
  • It is hard to judge the novelty of this paper. Each of the solution components seems plain. The authors did not clearly summarize the design challenges, potential design space and key insights in each part.

  • The baselines are highly insufficient. The experimental comparisons primarily involve dense attention and controlled positional-block baselines. These baselines help assess the effects of semantic clustering and query-specific block selection, but they do not reproduce the complete selection and execution strategies of existing methods such as FlexPrefill, FlashPrefill V2, and QuoKA. Appendix F.4 examines several alternative query-group scoring strategies and explains the implementation constraints that prevent direct comparisons with some prior methods. While these experiments provide useful evidence for the proposed design choices, they leave uncertainty about how the method compares with established training-free approaches under equivalent conditions. Since improving the accuracy-latency trade-off is a central objective of this work, the absence of direct comparisons makes it harder to establish the magnitude of its advantage over existing methods. This limits the assessment of its relative contribution, despite the improvements demonstrated by the controlled ablations.

  • The main latency measurements are obtained with batch size one on a single H200 GPU, without evaluating throughput under concurrent requests or continuous batching. This limitation matters because the proposed method involves query-specific block selection, KV reorganization, and additional indexing operations, whose costs may affect throughput and memory efficiency differently when multiple requests are served together. The full-prompt clustering approach also requires layer-wise prefill and incurs higher peak memory usage than dense chunked prefill. The paper acknowledges these constraints in Section 6 and investigates a prefix-index variant that supports conventional chunked prefill with lower memory overhead, as described in Section 5.4 and Appendix B.5. Although the appendix reports memory measurements and the additional latency of this alternative, its performance under concurrent workloads remains untested. As a result, the reported single-request speedups establish the method's potential for long-context inference, but provide limited evidence of its throughput and resource efficiency in practical serving settings.

Questions for authors

See the weakness above.

Reviewer_7Dt7OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a training-free sparse attention method that clusters prompt keys into large semantic blocks and uses query-specific block selection during both prefill and decoding. KV-outer execution groups queries by their selected blocks to improve efficiency. Experiments on hybrid LLMs show substantial whole-model speedups, although accuracy preservation varies across models and tasks.

Critical strengths
  1. The paper identifies a useful trade-off: larger blocks reduce execution overhead and can support larger token budgets, improving both accuracy and latency.
  2. The execution ablations are convincing. With the same selection, KV-outer substantially outperforms Q-outer, showing why the sparse pattern translates into actual speedups.
  3. Whole-model latency includes index construction and selection costs. The evaluations also cover retrieval, reasoning, and long generations.
Critical weaknesses
  1. Comparisons mainly use controlled positional-block baselines rather than complete implementations of prior methods. This makes the advantage over existing approaches difficult to assess, especially given the shared ideas with earlier clustering methods and MoBA.
  2. Accuracy losses can be substantial. At 512K, the 4B model’s MK-2 accuracy drops from 97.0% to 82.3%, while the 35B model’s MRCR-8 score drops from 0.525 to 0.459.
  3. The speed gains come with considerable additional memory usage. The fastest 4B configuration at 512K uses 82.69 GiB, compared with a dense estimate of 25.93 GiB, although the accounting differs.
  4. Experiments use one H200 at batch size one. The preferred block size also depends on the model and kernels, so broader deployment benefits remain unclear.
Questions for authors
  1. Could you compare against a complete clustering-based baseline under matched settings, including index construction costs?
  2. Does the advantage of coarse blocks persist with kernels optimized for smaller blocks?
  3. What speedups remain under comparable memory budgets and with multiple concurrent requests?
  4. Could you report paired confidence intervals for the quality differences, particularly on MRCR-8 and LongBench-v2?
Reviewer_XTHnOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a training-free sparse attention method that clusters keys into coarse semantic blocks. Each query selects blocks using centroid scores and attends to the original keys and values within them. Queries selecting the same block are processed together to improve KV reuse. The same index supports both sparse prefill and decoding. The paper studies the trade-off between block size, token budget, accuracy, and execution cost.

Critical strengths
  1. The method supports both prefill and decoding without additional model training.
  2. The paper reports whole-model latency improvements with index construction and other overheads included.
  3. The ablation studies examine block size, token budget, query sharing, clustering data, and execution choices. The runtime breakdown helps explain why coarser blocks can be more efficient.
Critical weaknesses
  1. No comparison with existing sparse-attention methods. The main comparisons are against dense attention and a controlled positional-block baseline. These experiments do not show its accuracy-efficiency advantage over prior work.
  2. The advantage of coarse blocks may depend substantially on the kernel implementation. Smaller blocks have much lower hardware utilization in the reported implementation. Without comparisons using kernels optimized for smaller blocks, it is unclear how generally the conclusion about coarse blocks holds.
  3. The full 13-task RULER benchmark is evaluated only on the 4B model at 512K, while cross-model and cross-length results mainly use five tasks. Systematic quality and latency results below 128K are also missing, leaving performance and acceleration at less lengthy contexts unclear.
Questions for authors

please see weakness section.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.