acceptodds
Under review as a conference paper at ICLR 2027

HATS: Efficient Threshold-based Sparse Attention via History-Guided Block Traversal

Abstract

Long-context decoding is bottlenecked by repeated access to an ever-growing KV cache. While sparse attention can skip insignificant KV blocks, inexpensive history-based selection is query-agnostic, whereas query-aware selection incurs additional computational overhead. An alternative is to make skip decisions during KV-block traversal, where a threshold determines whether to skip value-side computation right after computing a block's attention score. However, we observe that the achieved sparsity depends not only on the threshold but also on the traversal order: visiting low-scoring blocks before high-scoring ones can retain blocks that would otherwise be skipped, creating a traversal-induced sparsity gap. To close this gap, we propose HATS (History-guided Attention with Thresholded Skipping). HATS uses blocks that scored highly at the previous decoding step to guide traversal for the current token, thereby increasing the likelihood of visiting high-scoring blocks as early as possible. History only guides the order of block traversal, while value skipping remains determined by the newly computed current token score and a preset threshold. We prove that, for a given current token and fixed threshold, visiting the globally highest-scoring block first maximizes the attainable sparsity, thereby defining an oracle upper bound on sparsity over the set of all traversal orders. Experiments show that HATS closes 98.6–99.5% of the sparsity gap to the oracle, delivering a 1.98 speedup for the decode-attention kernel at 92.4% sparsity and a 1.26 decode-throughput speedup at 88.2% sparsity.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Sparse Attention, KV Cache, Efficient Inference

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_8fEKOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper improves threshold-based sparse decode attention by changing the traversal order of KV blocks. It uses previous-token block scores to prioritize likely high-scoring blocks, establishing a strong running maximum earlier. Skip decisions still use current-token scores. The paper analyzes the best traversal under a fixed skip rule and evaluates sparsity, task quality, attention-kernel performance, and decode throughput.

Critical strengths

S1. The paper clearly identifies how KV-block traversal order affects threshold-based skipping. The history-guided approach is simple and easy to understand.

S2. The fixed-score, fixed-threshold experiments help isolate the effect of traversal order. The paper also evaluates the tradeoff between task quality and sparsity.

Critical weaknesses

W1. The practical importance and incremental benefit over BLASST are insufficiently established. The motivation does not quantify the fraction of attention time and total decode time spent on traversal-induced extra value-side work over successive steps. The paper also lacks a direct performance comparison against BLASST at matched task quality, and the model-level throughput experiment omits BLASST. Headline speedups against Dense therefore do not isolate the benefit of the proposed traversal change.

W2. The throughput gain is not validated under a corresponding quality constraint. Quality experiments mainly use Qwen3-8B and Llama-3.1-8B, whereas throughput is measured on Qwen3-30B-A3B. No quality result is reported for that model at the corresponding sparsity setting. It is therefore unclear whether the reported throughput gain preserves task quality.

W3. Some quality comparisons use results taken from another paper; consistency of evaluation settings should be clarified. Table alignment and crowded half-width figures also need improvement.

Questions for authors

Q1. What fraction of attention time and total decode time is attributable to traversal-induced extra value-side work, and how much model-level throughput does HATS gain over BLASST at matched task quality?

Q2. What task quality does Qwen3-30B-A3B achieve at the 88.2% sparsity setting used for the reported throughput result?

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

This paper proposes HATS, which uses attention scores from the previous token to decide which KV blocks to visit first. By checking likely high-scoring blocks earlier, it can skip more computation on low-scoring blocks. The authors provide a theoretical analysis and GPU implementation, and show speedups over dense attention.

Critical strengths
  1. The main idea is simple and easy to understand.

  2. The ablation studies help explain why history-guided ordering works.

  3. The paper includes a GPU implementation and shows practical speedups over dense attention.

Critical weaknesses

I find the novelty somewhat overstated. BLASST already discusses visiting high-scoring blocks early to improve threshold-based skipping. HATS adds a useful history-guided ordering strategy, but the paper should distinguish this contribution more clearly from the existing insight.

The paper lacks an end-to-end comparison against BLASST at matched quality. Table 3(b) only reports throughput relative to Dense, and the model used there lacks corresponding quality results at high sparsity. This makes it difficult to assess the practical benefit of the proposed ordering strategy.

Questions for authors
  1. Why are different models used for quality and speed evaluations? This is confusing. Could you report both on the same model to show the quality–speed trade-off?
  2. Does the reported speedup include the cost of maintaining block scores and building the priority list?
Reviewer_wSqEOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The KV cache has become a major bottleneck for modern LLMs. When trying to skip V computation while traversing K, the traversal order determines the savings. HATS uses the locality between decoding steps to find the best traversal order and early-remove the impossible choices of V, which reaches near-optimal speedup.

Critical strengths
  • The paper demonstrates close to optimal speedup
Critical weaknesses
  • The Optimal itself is far from optimal: other methods like Quest can achieve much better speedup.
  • The speedup over baseline is minimal
Questions for authors

Thanks for submitting to ICLR, I have some concerns about the paper.

  1. “but require additional approximate scoring, sorting, or indexing.” Even then, they do not need to read the full K. However, HATS anyhow need to traverse the full K, where at least 50% of the data must be read. Even with an oracle, this still requires MUCH more reading than common query-aware sparsity methods and is very likely slower, especially for long contexts. The paper never compares the speed of HATS with Quest, which is a significant issue. Indeed, for a context length of 32K, even if Quest has a budget of 16K, it still loads less data than HATS!
  2. HATS does the full QK multiplication anyway; why not save the intermediate scores and perform a true top-k selection or a separate pass to find the items above the threshold, and then do the V part? That is a much easier solution and indeed, true optimal right?
  3. HATS’s speedup over BLASST is minimal (3.1%–10.2% at matched thresholds, according to Table 3(a)), despite the prominently reported 1.98× speedup over dense FlashAttention.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.