💬 NLP

ART: Attention Run-time Termination for Efficient Large Language Model Decoding

This paper introduces ART, a lightweight run-time mechanism that terminates KV cache accesses when accumulated attention outputs become negligible, thereby improving large language model decoding throughput by 20% without compromising accuracy.

Original authors: Chen Qiu, Guozhong Li, Panos Kalnis

Published 2026-06-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Chen Qiu, Guozhong Li, Panos Kalnis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a complex puzzle, and you have a massive box of reference cards (the KV Cache) that contain all the clues you've gathered so far. In a Large Language Model (LLM), every time the AI wants to write the next word, it has to look through these cards to find the most relevant ones.

The problem is that as the conversation gets longer, the box of cards gets huge. The AI has to physically walk to the shelf, grab a card, read it, and put it back. If the box is too big, the AI spends more time walking than thinking, which slows everything down.

The Old Way: Guessing Who Matters

Previously, researchers tried to speed this up by looking at the "title" of each card (the Key). They would guess, "Oh, this title looks important, so I'll read the whole card. That title looks boring, so I'll skip it."

But the paper points out a flaw in this logic: The title doesn't always tell the whole story. Sometimes a card with a boring title has a very important message inside (the Value). By skipping it based on the title alone, the AI might miss a crucial clue.

The New Solution: ART (Attention Run-time Termination)

The authors propose a new method called ART. Instead of guessing which cards to read before starting, ART lets the AI start reading the cards one by one and stops as soon as it has enough information.

Here is how it works, using a simple analogy:

The "Taste-Test" Analogy
Imagine you are cooking a soup and adding ingredients one by one to see how the flavor changes.

The Old Way: You have a recipe that says, "Add exactly 10 ingredients." Even if the soup tastes perfect after 3 ingredients, you keep adding the rest because the recipe says so.
The ART Way: You taste the soup after every single ingredient.
- You add the first few (the most important ones).
- You taste it.
- You add the next one. You taste it again.
- The Magic Moment: If you add an ingredient and the taste doesn't change at all (or changes so little you can't notice), you stop. You don't bother adding the remaining 5 ingredients because they won't make the soup any better.

How ART Does This Technically

In the computer world, the "soup" is the Attention Output (the final result the AI is calculating).

Monitoring: As the AI processes blocks of data, it constantly checks the "flavor" of the result.
Two Checks: It checks two things:
1. Size: Did the result get significantly bigger or smaller?
2. Direction: Did the result shift to a completely different meaning?
The "Patience" Rule: Sometimes the flavor might wiggle a tiny bit just by chance. ART has a "patience" setting. It waits to see if the flavor stabilizes for a few steps in a row. If it stays steady, ART says, "Okay, we're done," and stops fetching the rest of the cards.

Why This is a Big Deal

It's Smart: Unlike the old methods that only looked at the "titles" (Keys), ART looks at the actual "message" (Values). It knows when the information is truly finished.
It's Safe: It doesn't delete cards permanently. It just decides, "We don't need to read the rest of this specific batch right now."
It Works with Everything: You can use ART alongside other speed-up tricks. It's like adding a "stop-early" button to a car that already has a turbo engine.
The Results: The paper tested this on long conversations and found that:
- The AI gets the answers just as accurately as before (almost no loss in quality).
- It generates text 20% faster when handling many requests at once, because it stops wasting time reading cards that don't change the answer.

Summary

ART is like a smart librarian who realizes that once you've read the first few chapters of a book, you already know the ending. Instead of forcing you to read the last 50 pages, the librarian says, "You're good, you can stop here," saving you time and energy without missing the point of the story.

Technical Summary: ART (Attention Run-time Termination)

1. Problem Statement

Long-context decoding in Large Language Models (LLMs) is currently bottlenecked by memory bandwidth constraints required to fetch extensive Key-Value (KV) caches. As sequence lengths increase, the latency and memory usage grow linearly because each new query attends to an expanding set of cached keys ( $K$ ) and values ( $V$ ).

Existing solutions primarily rely on key-centric pruning, where tokens are selected or evicted based on attention scores or heuristic importance estimators derived from query-key similarity. However, the authors identify a fundamental limitation in this approach:

Misalignment of Importance: Attention scores do not always correlate with a token's true influence on the model output. As illustrated in Figure 1 of the paper, tokens with low attention weights can still possess high functional impact due to the magnitude of their value vectors.
Overhead of Value-Aware Methods: Recent attempts to incorporate value information into KV management often require auxiliary predictors, pre-computation, or offline analysis, which introduce prohibitive overheads during inference.

The core challenge addressed is: Can the joint effect of keys and values be accounted for at run-time with negligible additional cost to determine when further attention computation is redundant?

2. Methodology: Attention Run-time Termination (ART)

ART is a lightweight, run-time mechanism designed to terminate attention computation early once the accumulated output stabilizes, thereby skipping the processing of remaining KV blocks.

2.1. Core Insight

Modern FlashAttention-style kernels compute attention in a streaming, tile-wise manner, incrementally accumulating outputs as KV blocks are processed. This execution model exposes intermediate attention states at negligible cost. The authors observe that the attention output often converges (stabilizes) before all KV blocks in the sequence have been traversed.

2.2. Stability-Based Termination Criterion

Unlike static pruning rules, ART is output-aware. It monitors the evolution of the partial attention output $O^{(t)}$ as additional KV blocks are incorporated. To avoid the high cost of computing full-vector norms, ART utilizes a lightweight probe vector $x^{(t)}$ extracted from the register fragment of the leading thread in a thread block (leveraging the swizzled Matrix Multiply-Accumulate layout).

Convergence is determined by monitoring two geometric dimensions of the probe vector's evolution:

Magnitude Variation ( $d^{(t)}_{scale}$ ): The L2-norm difference between the current and previous probe vectors.
Directional Change ( $d^{(t)}_{direction}$ ): The cosine similarity deviation between the current and previous vectors.

Termination is triggered only when both metrics fall below predefined thresholds ( $\tau$ and $\phi$ ) simultaneously. This decoupled design is crucial because a unified metric cannot reliably balance sensitivity to directional shifts against benign scale variations.

2.3. Patience Mechanism

To prevent premature termination due to transient fluctuations, ART employs a patience parameter ( $p$ ). The system requires the stability criteria to be met for $p$ consecutive KV blocks before triggering early termination. This filters out noise while incurring negligible latency.

2.4. Integration and Correctness

Orthogonality: ART does not replace existing KV cache management methods (e.g., StreamingLLM, SnapKV, PyramidKV) but acts as an orthogonal control layer. It can be seamlessly integrated by reordering the traversal sequence of KV blocks (e.g., "recency-first" or "importance-first").
Correctness Guarantees:
- Permutation Invariance: Reordering KV blocks does not introduce approximation errors due to the permutation-invariant nature of attention and the numerical properties of online softmax.
- Attention Sinks: To preserve numerical stability, ART enforces the mandatory evaluation of the first KV block (Block 0), which often serves as an attention sink, before any early termination can occur.
- Positional Encodings: Since positional encoding and masking are applied prior to accumulation, Rotary Positional Embeddings (RoPE) and causal masking remain strictly preserved.

3. Key Contributions

ART Mechanism: The proposal of a lightweight, run-time mechanism that dynamically determines whether further KV cache blocks need processing by monitoring the convergence of intermediate attention outputs.
Stability Criterion: The design of a dual-component termination criterion (scale and direction) that captures the joint influence of keys and values without expensive pre-computation.
Composability and Efficiency: Demonstration that ART integrates seamlessly with existing KV cache strategies, achieving significant speedups (20% higher throughput in large batch sizes) with negligible accuracy loss.

4. Experimental Results

The authors evaluated ART on the LongBench benchmark using Mistral-7B-Instruct-v0.3 and Llama-3.1-70B-Instruct on NVIDIA A100 GPUs.

Accuracy: When applied to full KV caching, ART retained 99.2% of the original LongBench score. When combined with pruning methods (StreamingLLM, SnapKV, PyramidKV), the accuracy degradation was marginal (often < 1%), demonstrating that ART effectively preserves critical KV blocks.
Throughput: ART achieved a 20% increase in generation throughput compared to state-of-the-art baselines in large batch sizes. The gains were most pronounced as batch size increased, due to the reduction in memory bandwidth contention caused by skipping redundant KV block fetches.
Latency: Time Per Output Token (TPOT) was significantly reduced across all tested configurations.
Overhead: An ablation study confirmed that the computational overhead of the ART detector itself is negligible (approx. 1.3% increase in kernel runtime when early termination is disabled).
Ablation: Removing the scale or direction components, or the patience mechanism, resulted in either severe accuracy degradation or increased false-positive termination rates, validating the necessity of all design choices.

5. Significance and Claims

The paper positions ART as a general and practical building block for efficient long-context LLM decoding. Its primary significance lies in:

Shifting the Paradigm: Moving from static, key-only pruning to dynamic, output-aware termination that accounts for the joint contribution of keys and values.
System-Level Efficiency: Providing a "plug-and-play" acceleration module that reduces memory traffic and compute redundancy at the kernel level without requiring changes to model architecture or offline training.
Resource Optimization: By eliminating redundant attention computation, ART has the potential to lower the cost and energy footprint of deploying large-scale language models, improving their accessibility.

The authors maintain a modest stance, acknowledging that effectiveness may vary across hardware platforms and usage scenarios, and emphasizing that ART is a system-level optimization rather than a guarantee for all application domains.