- Rating
- 3(+1)
- Confidence
- 1(−1)
- Informativeness
- 2
- Presentation
- 2(−1)
- Soundness
- 2
Read review
Paper summary
The paper proposes ART, a run-time early termination mechanism inside FlashAttention decoding kernels. The kernel monitors a 32-element probe of the partial attention output and stops traversing KV blocks once scale and direction changes stay below thresholds for consecutive blocks. ART composes with full KV, StreamingLLM, SnapKV, and PyramidKV, using recency or importance order for traversal. On LongBench it reports about 10% lower TPOT with small score drops. On RULER NIAH, recency-first ART loses about 20 points at 32K. In vLLM serving, it gains 3.7% throughput.
Critical strengths
ART is training free and implemented at the kernel level. It is composable with existing KV policies, has measured detector overhead, and is integrated into vLLM.
Critical weaknesses
- Stability of the visited prefix cannot reveal unseen evidence, so the stopping rule is unreliable when important tokens appear late in the traversal. The RULER results confirm the risk: accuracy at 32K falls from 99.34% to 78.65% on Qwen3-8B. Figure 4 also contradicts the premise of early convergence, since the relative error stays near 0.6 until about 20% of the cache is loaded and reaches zero only at the end.
- The theoretical bound adds little. Assumption 1 requires the remaining blocks to carry decaying mass, which is essentially the condition that makes early termination safe. ART does not verify the assumption at run time, and the resulting harmonic sum bound is elementary.
- The efficiency gains are modest, and a key baseline is missing. TPOT improves by about 10% on LongBench, and end-to-end vLLM throughput by only 3.7%. There is no comparison against fixed truncation, such as a recency window or a top-k budget, at the same average number of visited blocks, so it remains unclear whether the adaptive criterion outperforms a static budget. The thresholds are also absolute values without normalization across layers or models.
Questions for authors
- At matched average KV blocks visited, how does ART compare with a fixed recency window or a fixed SnapKV budget?
- How often does Assumption 1 hold empirically along recency and importance traversals?
- Do the fixed thresholds and transfer across models and layers without retuning?
- What fraction of KV blocks is skipped on average, and how does that fraction vary with context length beyond 32K?
6 comments
Response to Reviewer jZ9T
Q2: Empirical validity of the key mass bound. To evaluate the empirical relevance of Assumption 1, we conducted additional experiments using Qwen3-8B on LongBench with a retention ratio of . Specifically, we examined whether the normalized attention-mass bound , where , holds across the unvisited KV blocks following ART termination. Across all evaluated layers and attention heads, the block-level violation rate was 1.84% for recency-based StreamingLLM + ART and 0.07% for importance-based SnapKV + ART. Furthermore, for SnapKV + ART, 95.47% of evaluated traversals exhibited no violations among their unvisited blocks.
These results provide empirical support for the harmonic mass-decay behavior underlying our logarithmic error analysis, particularly under importance-based traversal. Although individual blocks may deviate from the assumed decay rate, the low observed violation rates suggest that the normalized mass bound is representative of the evaluated traversal patterns. Importantly, these measurements verify the specific mass inequality used in Lemma 1 rather than all the stronger sufficient conditions of Assumption 1.
The theoretical analysis remains a conditional characterization of truncation error, while the new mass-bound measurements and the task-level evaluations provide empirical evidence for its relevance and delineate the traversal-dependent limitations.
We have added these block-level and traversal-level results to Appendix A (p. 16, lines 810–816), together with the evaluation setting and an explicit distinction between the tested mass inequality and the stronger sufficient conditions in Assumption 1.
W3 / Q1 / Q4: KV traversal and fixed-budget comparisons.
On Llama-3.1-70B-Instruct using LongBench, Full KV + ART skips 20.93% of candidate KV blocks overal. For contexts above 32K tokens, it skips 25.24%, using the same default thresholds and patience. Thus, the longer-context subset leaves a larger fraction of the traversal unvisited under the same settings. We count 64-token logical computation blocks across actual decoding steps, all layers, and all query heads, excluding prefill and the first output token.
Full KV + ART and StreamingLLM provide a recency-based comparison between output-dependent stopping and a fixed recent-window budget. Full KV + ART traverses the cache in recency-first order and dynamically determines where to stop, whereas StreamingLLM uses a fixed recent window with attention-sink preservation.
On Llama-3.1-70B-Instruct using LongBench, Full KV + ART has a measured aggregate KV-block visit rate of 79.07%, close to the fixed 80% retention budget of StreamingLLM (0.8). At these approximately matched budgets, Full KV + ART achieves a LongBench score of 47.48, compared with 42.31 for StreamingLLM—a 5.17-point improvement—while providing slightly higher TPOT speedup.
The measured visitation rate establishes the approximate KV-budget match, while the similar TPOT speedups show comparable realized decoding cost, including ART's monitoring overhead. Thus, this comparison directly addresses the fixed-recency-window alternative in Q1 and demonstrates a quality advantage for output-dependent stopping over the evaluated fixed window at a comparable average KV budget. “Full KV” specifies the candidate cache available to ART, not that all blocks are actually processed.
The observed 79.07% visit rate is close to 80%, motivating comparison with the existing fixed configurations for the same 70B model. Table 1 reports their quality and decoding performance on LongBench:
| Method | LongBench score | TPOT speedup |
|---|---|---|
| Full KV + ART | 47.48 | 1.15× |
| StreamingLLM (0.8) | 42.31 | 1.13× |
| SnapKV (0.8) | 46.49 | 1.08× |
| PyramidKV (0.8) | 44.10 | 1.12× |
All speedups are relative to the same full-KV baseline. ART achieves higher LongBench quality and lower measured decoding latency than each listed fixed-budget configuration. These quality–latency comparisons complement the direct traversal measurements on LongBench.
ART inherits SnapKV’s importance ranking, and fixed SnapKV budgets select prefixes of that same ranking. On Mistral-7B in Table 1, SnapKV (0.8) + ART scores 43.12, versus 31.17 for fixed SnapKV (0.2), with both reporting 1.17× TPOT speedup. This is an 11.95-point quality advantage at the same reported decoding speed, using the same importance order.
The TPOT measurements include ART’s monitoring and traversal costs. The 3.70% serving-throughput improvement is measured end-to-end, where ART accelerates the decode-attention component of the larger serving workload. Our Q3 response addresses the shared default thresholds and the sensitivity results in Appendix H.
We have added the block-count measurements and counting protocol to Appendix I (p. 23, lines 1194–1197) and made the fixed-budget comparisons explicit in Section 4.2 (pp. 6–7).
Response to Reviewer jZ9T
Q3: Shared thresholds and sensitivity.
Our main evaluations use the same defaults across the evaluated models and layers, without model-specific or layer-specific retuning:
These settings are shared across Mistral-7B, Qwen3-8B, and Llama-3.1-8B/70B. The scale criterion uses a fixed raw L2 threshold, while the direction criterion uses cosine distance.
To further characterize parameter sensitivity, we added experiments on Llama-3.1-70B-Instruct using LongBench with Full KV + ART. We vary one parameter at a time, keeping the other two at their defaults. The Full KV baseline without ART scores 48.25 and serves as the 1.00× reference for all kernel speedups below, using the same model, benchmark, and otherwise identical evaluation settings. These speedups measure attention-kernel acceleration, not the decoding TPOT speedups reported in Table 1.
Scale threshold , with and :
| Scale threshold | LongBench score | Kernel speedup |
|---|---|---|
| 47.86 | 1.04× | |
| 47.54 | 1.07× | |
| 47.48 | 1.25× | |
| 45.38 | 1.84× | |
| 43.24 | 1.91× |
Direction threshold , with and :
| Direction threshold | LongBench score | Kernel speedup |
|---|---|---|
| 48.14 | 1.03× | |
| 47.59 | 1.14× | |
| 47.48 | 1.25× | |
| 46.05 | 1.26× | |
| 45.06 | 1.26× |
Patience , with and :
| Patience | LongBench score | Kernel speedup |
|---|---|---|
| 1 | 41.60 | 1.59× |
| 2 | 43.25 | 1.50× |
| 5 | 47.48 | 1.25× |
| 10 | 47.94 | 1.03× |
These results clarify the trade-offs achieved by the shared defaults:
- Scale: tightening from to improves the score by only 0.06 points, while reducing kernel speedup from 1.25× to 1.07×. Relaxing it to increases speedup to 1.84× but reduces the score by 2.10 points.
- Direction: relaxing beyond provides little additional acceleration, from 1.25× to 1.26×, while reducing the score by 1.43–2.42 points.
- Patience: reducing to 1 or 2 lowers the score by 5.88 or 4.23 points. Increasing it to 10 improves the score by 0.46 points but reduces kernel speedup to 1.03×.
The cross-model evaluations demonstrate that the same defaults can be used across the tested models and layers without retuning. The additional 70B sensitivity study shows how each parameter affects quality and attention-kernel efficiency, supporting the shared defaults as a balanced operating point among the tested settings. We have added these 70B results and the one-parameter-at-a-time evaluation protocol to Appendix H.2 and Table 12 (pp. 22–23), explicitly distinguishing attention-kernel speedup from decoding TPOT speedup.
Response to Reviewer jZ9T
We thank the reviewer for the questions and for recognizing ART's kernel implementation and composability.
W1: Traversal order and Interpretation of Figure 4.
Traversal dependence and RULER. ART adds output-dependent stopping to the candidate KV set and traversal order supplied by the base policy. Stability of a visited prefix does not certify unseen evidence; Section 4.3 uses RULER NIAH specifically to examine this limitation in distant retrieval. The 99.34% to 78.65% accuracy change at 32K concerns Qwen3-8B with recency-first ART over full KV. This exposes a genuine failure mode: important evidence can appear after a stable prefix under the chosen traversal.
Table 2 also evaluates importance-based compositions. At 32K, adding ART to SnapKV increases TPOT speedup from 1.18× to 1.36× on Qwen3-8B, with accuracy changing from 99.37% to 95.68%. On Llama-3.1-8B, speedup increases from 1.18× to 1.34×, with accuracy changing from 99.26% to 97.09%. All speedups are relative to the same model’s full-KV baseline. These results demonstrate additional acceleration with substantially smaller retrieval losses under the evaluated importance-based compositions, while retaining a quality–efficiency trade-off. ART complements the base policy’s selection and prioritization rather than replacing them.
Interpretation of Figure 4. Figure 4 illustrates approximation error as coverage increases, rather than directly validating ART’s stopping criterion. Figure 4 plots the relative L2 discrepancy between attention over an expanding recent-KV window and full attention; it does not plot ART’s stopping statistics. ART instead monitors changes between consecutive partial attention outputs through the probe’s L2 change, cosine distance, and patience rule. A plateau in distance to a fixed reference does not imply that consecutive output vectors are unchanged: the vector can change while remaining at a similar distance from the reference. Likewise, zero discrepancy at full coverage is expected by construction; ART does not require exact agreement with full attention before stopping.
We have clarified this distinction in Sections 3.1–3.2 and the caption of Figure 4 (p. 4, lines 173–192).
W2: Explanation of Assumption 1.
Assumption 1 is intended to characterize a mathematically meaningful reference regime, rather than assert that attention mass always decays uniformly in practice. Consider the elementary setting in which each KV block contributes the same unnormalized attention mass ℓ. The cumulative normalization then grows linearly, Aj=jℓ, while each additional block contributes a normalized mass of ℓj/Aj=1/j. Under bounded residual update magnitudes, the cumulative truncation-error upper bound therefore scales as $\sum_{j=t^{\ast}+1}^{T} \frac{1}{j} \leq \log(T/t^{\ast})$$. The analysis establishes a generalized logarithmic characterization of cumulative attention-output error, showing how the harmonic decay arising from attention normalization translates into a bound on the residual error.
Assumption 1 extends this uniform reference case by permitting nonuniform block masses under sufficient conditions that ensure their normalized contributions remain bounded by μ/j. Crucially, this assumption does not directly impose small output error. Disproportionately large attention mass assigned to later blocks may violate Assumption 1, while unusually large value-dependent changes may increase Δ. Thus, the logarithmic bound characterizes the natural accumulation of error under mass-regulated traversal, while violations of this regime fall outside the guarantee provided by this logarithmic bound.