Paper at a glance

Why VLM attention is not like LLM attention

Prior KV-cache-compression work (StreamingLLM, H2O, PyramidKV, …) was designed for text-only LLMs and simply evicts “unimportant” cache tokens based on attention scores. The authors show this transfers poorly to VLMs because VLM attention has a structurally different shape: there is a sharp modality boundary between visual tokens and the language tokens that follow them.

Figure 1 (reproduced above from the paper). Darker red = higher attention score. Both matrices show that the tokens that matter during decoding are largely the same ones that mattered during prefill — which is why KV cache compression is possible at all. The key difference in panel (b) is the clear modality boundary along the query dimension: language tokens attend strongly to the language tokens that come right after the image (the “post-vision” tokens), not diffusely across all preceding visual tokens. This single observation motivates the entire method.

Because prior methods are modality-unaware, they conflate attention mass coming from visual tokens with attention mass coming from language tokens, which — as the paper demonstrates empirically in its accuracy benchmarks (Section 6.2) — leads to suboptimal token eviction decisions for VLMs.

Two more empirical observations that shape the method

1. Attention sparsity varies a lot across layers. Measured sparsity ranges from 70% to 99% across transformer layers, with the first couple of layers noticeably denser than the rest. Prior work allocates the same cache budget to every layer (H2O, Keyformer) or a fixed monotonically-decreasing schedule (PyramidKV, PyramidInfer) — both of which under-fit this per-layer variation.
2. Sparsity also differs between visual and language tokens, and depends on the specific prompt, so a fixed, prompt-independent budget schedule can’t be optimal — the budget really needs to be computed per prompt, at inference time.

Contributions, restated

1. A characterization of VLM attention sparsity across the prefill and decoding phases, showing it’s structurally different from LLM attention.
2. Layer-adaptive, sparsity-aware KV cache budget allocation — how much cache each layer gets is computed dynamically from that layer’s own measured sparsity, not from a fixed schedule.
3. A modality-aware token scoring policy (“Accumulated Post-vision Attention”) that uses language-to-vision attention as a robust signal for which tokens (visual and language) are worth keeping.

VLM inference: prefill and decoding

Let a VLM prompt be a sequence of m tokens (mixing visual and language tokens after the visual encoder + projection layer have turned image patches into “soft prompt” embeddings): \(\{x_1, \dots, x_m\}\).

Prefill phase. All m tokens are processed in parallel to compute \(P_\theta(x_{m+1} \mid x_1, \dots, x_m)\) — the probability distribution for the first generated token. While doing this, the model caches the per-layer key and value vectors \(\{k_1^{(l)}, \dots, k_m^{(l)}\}\) and \(\{v_1^{(l)}, \dots, v_m^{(l)}\}\) for every transformer layer \(l\), so they don’t need to be recomputed later.

Decoding phase. At step \(i\), the model consumes token \(x_{m+i}\) and computes \(P_\theta(x_{m+i+1} \mid x_1, \dots, x_{m+i})\). This produces new key/value vectors \(k_{m+i}^{(l)}\), \(v_{m+i}^{(l)}\) per layer, which get appended to the running cache. As context length grows (many images, video, or long generations), the KV cache can exceed the size of the model’s own parameters, making memory capacity and bandwidth — not compute — the bottleneck.

KV cache compression: two independent design axes

The paper frames KV cache compression as having exactly two design dimensions, and this framing is the backbone of the whole method:

1. Budget allocation — how many cache slots does each layer get?
   • Naïve baseline: equal budget per layer (used by StreamingLLM, H2O).
   • PyramidKV / PyramidInfer: a fixed, monotonically decreasing budget with depth (more budget to shallow layers, less to deep ones), motivated by the empirical finding that evicting cache at different layers hurts accuracy by different amounts.
2. Token scoring policy — which tokens within a layer’s budget get kept?
   • Formally: given n cached tokens at layer l indexed by \(S = \{0, \dots, n\}\), a scoring policy is a function \(\psi: S \to \mathbb{R}^n\). Given a budget \(k \in [1, n)\), the tokens kept are the top-k scorers: \[S_\psi := \{i_1, i_2, \dots, i_k : \psi(S)_{i_j} \ge \psi(S)_{x \in [n]\setminus\{i_1,\dots,i_k\}}\}\]
   • StreamingLLM keeps only the earliest (“attention sink”) tokens plus the most recent ones.
   • H2O uses accumulated attention scores (summed over the query dimension) to keep “heavy hitter” tokens.

The paper’s unifying insight: KV cache compression only works because transformer attention is sparse in the first place — so both budget allocation and token scoring should be driven by measured sparsity, not fixed heuristics. That idea is developed in the next section.

Measuring attention sparsity

To measure sparsity cheaply (it needs to run at inference time, not just for offline analysis), the paper defines a fast relative-threshold filter instead of using top-k/top-p truncation (which would require sorting):

\[ \text{ThresholdFilter}(A, p)_{ij} = \begin{cases} A_{ij} & \text{if } A_{ij} \ge p \cdot \max_j(A_{ij}) \\ 0 & \text{otherwise} \end{cases} \qquad (1) \]

with \(p \in (0,1)\) heuristically set to 1% (small enough that the filtered-out scores barely affect the layer’s output). ThresholdFilter is asymptotically faster than top-p/top-k truncation because it doesn’t require sorting the attention distribution.

Given the filtered matrix, per-layer sparsity \(\gamma^{(l)} \in [0,1]\) is the fraction of zero entries in the lower-triangular (causal) portion of the attention matrix:

\[ \gamma^{(l)} := \frac{\sum_{i \ge j} \mathbb{1}[\text{ThresholdFilter}(A^{(l)}, p)_{ij} = 0]}{|\{A_{ij}^{(l)} : i \ge j\}|} \qquad (2) \]

Figure 2 (reproduced from the paper). Each box is one transformer layer’s sparsity distribution (across attention heads and sampled prompts).

Findings from this experiment:

• Sparsity ranges from about 70% to 99% across layers — this is not uniform, contradicting the equal-budget assumption used by H2O/Keyformer.
• The first two layers are noticeably less sparse (denser, more “important” in the sense of needing more cache) than the rest, and a few middle layers are also denser than their neighbors — this non-monotonic pattern contradicts the monotonically decreasing schedule used by PyramidKV/PyramidInfer.
• The decoding-phase sparsity curve (b) closely tracks the prefill-phase curve (a), except the 2nd layer becomes much sparser during decoding. The Pearson correlation coefficient between the prefill and decoding sparsity curves (averaged across layers) is 0.695 — high enough that the authors conclude prefill-phase sparsity can be used to predict how much cache a layer will need during decoding.

This last point is the linchpin of the method: you can measure sparsity once, cheaply, right after prefill, and use it to decide the decoding-phase cache budget — no need to observe decoding attention at all (which wouldn’t be available yet anyway).

Measuring cache hit rate and the “post-vision” hypothesis

Going back to the modality boundary observed in Figure 1(b), the authors hypothesize that scoring cache tokens by their attention from the post-vision language tokens (rather than from the whole prompt) will more faithfully identify which tokens the model actually needs during decoding.

To test this rigorously, they define an oracle-relative metric.

Since \(A_{m+1}\) is only known after decoding starts — and the entire point of compression is to shrink the cache before decoding — multiple prefill-time approximations \(\psi\) have been proposed:

τ is the count of language tokens that follow the vision tokens in the prompt — so Accumulated Post-vision Attention is a dynamic, prompt-dependent sliding window, where the window size is exactly the length of the post-vision language prompt, instead of a fixed, hand-tuned w.

Why does plain Accumulated Attention do worse? Summing over the entire query dimension unavoidably gives high scores to early tokens simply because more queries have had the chance to attend to them — a length bias. A sliding window helps, but a fixed window size is a blunt instrument: it can be too large or too small depending on how long the post-vision prompt happens to be for a given input. Post-vision Attention sidesteps this by letting the “window” be exactly the post-vision language span, which is exactly where the modality boundary in Figure 1(b) shows the useful signal concentrating.

Sparsity-aware KV cache budget allocation

Two steps happen once, right after prefill:

1. Apply ThresholdFilter (with \(p = 1\%\)) to the Post-vision Attention scores \(A'\) and compute layer-wise sparsity \(\gamma'^{(l)}\) (same recipe as Eq. 1–2, but restricted to the post-vision query rows).
2. Given a global target cache budget \(\alpha\) (a hyperparameter — e.g. \(\alpha = 10\%\) means “keep 10% of the KV cache overall”), distribute that budget across layers in proportion to each layer’s density (i.e. \(1 - \gamma'^{(l)}\)): sparser layers get less cache, denser layers get more.

Input:  query and key Q, K ∈ R^(L×H×m×d), number of layers L,
        number of heads H, length of post-vision prompt τ,
        cache budget α.
Output: layer-wise budget β

procedure ComputeSparsity(Q, K):
    Q' ← Q[m-τ:m]
    A' ← softmax(Q' Kᵀ / √d)
    γ' ← Σ_{i+m-τ≥j} 1[ThresholdFilter(A', p)_ij = 0]
         ─────────────────────────────────────────────
                    |{A'_ij : i+m-τ ≥ j}|
    return γ'

procedure SkewedCacheBudgetAllocation(Q, K, α, L, H):
    Γ[L][H] ← 0
    for l = 1 → L:
        for h = 1 → H:
            Γ[l][h] ← ComputeSparsity(Q_h^(l), K_h^(l))
    γ' ← Γ.mean(axis=1)                 # average over heads
    Z  ← Σ_l (1 − γ'^(l))
    β[L] ← 0
    for l = 1 → L:
        β^(l) ← clip( (1 − γ'^(l)) / Z · αL ,  0.01,  1 )
    return β

The same logic, as a flowchart:

flowchart TD
    START(["Input: Q, K ∈ ℝ^(L×H×m×d)<br/>layers L, heads H, post-vision length τ, budget α"]) --> OUTER{"for layer l = 1…L"}
    OUTER --> INNER{"for head h = 1…H"}
    INNER --> CS["ComputeSparsity(Qₕ⁽ˡ⁾, Kₕ⁽ˡ⁾):<br/>Q′ = Q[m−τ:m]<br/>A′ = softmax(Q′Kᵀ/√d)<br/>γ′ = fraction of ThresholdFilter(A′,p) = 0<br/>in the post-vision causal region"]
    CS --> INNER
    INNER -->|all heads done| OUTER
    OUTER -->|all layers done| AGG["γ′⁽ˡ⁾ = mean over heads<br/>Z = Σₗ (1 − γ′⁽ˡ⁾)"]
    AGG --> ALLOC["for layer l = 1…L:<br/>β⁽ˡ⁾ = clip( (1−γ′⁽ˡ⁾)/Z · αL , 0.01, 1 )"]
    ALLOC --> RET(["Return per-layer budget β"])

Key contrast with PyramidKV: PyramidKV uses one fixed monotonically-decreasing budget schedule for every prompt. VL-Cache’s \(\beta^{(l)}\) is recomputed per prompt from that prompt’s own measured sparsity pattern — so a document-heavy prompt and a short-caption prompt get different per-layer allocations, instead of being forced into the same static shape. Note the allocation is only computed once, immediately after prefill, so its cost is amortized over the (potentially many) subsequent decoding steps.

Modality-aware token scoring policy

Once each layer knows its budget \(k^{(l)}\) (the token count implied by \(\beta^{(l)}\)), VL-Cache still needs to decide which \(k^{(l)}\) tokens to keep. It reuses the same Post-vision Attention matrix \(A'\) (Accumulated Post-vision Attention from Section 4.2) as the scoring function.

Two advantages are argued for reusing Post-vision Attention here, rather than the full attention matrix used by prior work (e.g. H2O):

1. Efficiency. Computing layer-wise sparsity/scores from Post-vision Attention costs \(O(\tau m)\) instead of \(O(m^2)\) for the full attention matrix — because \(\tau \ll m\) for realistic vision-language prompts (the post-vision instruction/question is typically much shorter than the full prompt, which is dominated by visual tokens).
2. Better token preservation. As shown empirically in Figure 3 (Section 4.2), Post-vision Attention achieves a higher CacheHitRate than plain Accumulated Attention or a fixed sliding window, i.e. it more reliably keeps the tokens that the model will actually attend to during decoding.

The narrative tying it together: plain Accumulated Attention over-weights early tokens (length bias); a fixed sliding window helps but its size is a poorly-chosen constant across very different prompts; Post-vision Attention is a prompt-adaptive sliding window whose size is derived from the prompt’s own structure (the post-vision span), which is exactly where the paper’s Figure 1(b) modality-boundary observation says the useful signal lives.

Setup

• Hardware: AWS EC2 P4 instance, 8× A100 40GB GPUs.
• Tasks (via lmms-eval): Coco-Caption (metric: CIDEr — captioning / world knowledge), DocVQA (metric: ANLS — document OCR/QA), MathVista (metric: ACC — visual math reasoning).
• Baselines: full KV cache, StreamingLLM, H2O, PyramidKV — all configured with default settings, budget scaled proportionally to prompt length, and recent-token window fixed at 10% of the budget for a fair comparison.

Accuracy evaluation

Figure 5 (reproduced from the paper). Accuracy vs. KV cache budget (1–100% of prompt length), for both LLaVA backbones across all three datasets. The dashed grey line marks full-cache accuracy.

Speed benchmark

Latency is measured as raw GPU kernel time (via PyTorch Profiler) using synthetic prompts of increasing length (1K → 128K tokens) and batch sizes (1 → 64), following the benchmarking methodology of vLLM’s PagedAttention paper (Kwon et al., 2023). The baseline uses HuggingFace’s default implementation with FlashAttention-v2; VL-Cache uses custom Triton kernels (detailed in Section 8.3) for the attention-statistics pass. Speedup is always baseline latency / VL-Cache latency.

How to read these numbers:

• Prefill is barely affected (speedup ≈ 0.96–0.99, i.e. essentially neutral, occasionally a hair slower) — this is expected, since the extra attention-statistics computation is small and happens only once per request; Appendix A.4 shows it’s just 1–6% overhead on top of prefill latency, shrinking further as prompts get longer.
• Decoding speedup grows with prompt length, reaching 7.08× at 128K tokens/batch 1 — because that’s exactly where a smaller KV cache saves the most HBM traffic per decoding step.
• End-to-end speedup is bounded above by decoding speedup, since prefill is unaffected. At 128K tokens/batch 1, decoding is 7.08× faster, but prefill still eats 53% of total latency, so the blended end-to-end number comes out to only 1.66×. As the number of output tokens generated grows, end-to-end speedup asymptotically approaches the decoding speedup — meaning VL-Cache is most valuable for long-output tasks: captioning, video description, chain-of-thought multi-modal reasoning, etc.
• Because batch size in this setup is capped by peak prefill memory, not KV cache size, compression here doesn’t directly raise the maximum batch size — the authors note that continuous batching / chunked prefill (future work) would let KV-cache size become the binding constraint, at which point VL-Cache’s memory savings would translate into higher concurrency too.
• Figure 6 shows the practical payoff for a server operator: at any given target latency, VL-Cache serves noticeably higher throughput than the full-cache baseline, and vice versa — for the same throughput target, requests see lower latency.

A.1 — Vision-language prompt template construction

The point of this figure is subtle but important for why VL-Cache’s Post-vision Attention signal is robust: standard VLM prompt-template conventions (used across LLaVA, Gemini, GPT-4o, Qwen-VL, Claude, etc.) mean that regardless of whether the image appears before or after the user’s text in the raw conversation, the templated prompt fed to the model always places a language-based instruction or question in the post-vision position. That’s what makes “the last τ tokens after the vision block” a reliable, prompt-independent way to locate the useful signal — it doesn’t require knowing anything about how the user phrased their input.

The underlying process, generalized as a flow:

flowchart TB
    IMG["Input image"] --> VE["Visual encoder<br/>(e.g. CLIP ViT-L/14-336)"]
    VE --> PROJ["Projection layer (MLP)"]
    PROJ --> IMGEMB["&lt;image&gt; embedding<br/>(soft prompt tokens)"]
    USERTXT["User instruction / question<br/>(may precede or follow the<br/>image in the raw conversation)"]
    SYS["System / conversation<br/>prompt template"]
    IMGEMB --> COMBINE["Templated prompt:<br/>system + &lt;image&gt; + instruction"]
    USERTXT --> COMBINE
    SYS --> COMBINE
    COMBINE --> POSTVISION["Post-vision language span (length τ)<br/>always right after &lt;image&gt;,<br/>regardless of original ordering"]
    POSTVISION --> LM["Language model"]
    LM --> OUT["Generated response"]

A.2 — Extended related work

A.3 — Efficient implementation (Triton kernels)

To find low-attention tokens during prefill without blowing the latency/memory budget, VL-Cache needs two statistics computed from the (potentially huge) attention score matrix:

1. The average attention score per token in the key dimension (used for token scoring).
2. The count of attention scores below p% of the row maximum, in the query dimension (used for the sparsity ratio, per Eq. 1–2).

The catch: modern fused-attention kernels like FlashAttention and PagedAttention deliberately never materialize the full attention score matrix in HBM (that’s exactly what makes them fast). So VL-Cache needs a new, similarly memory-efficient kernel that computes these two statistics without ever writing the full attention matrix back to HBM. The design constraints, verbatim from the paper:

1. The attention mask is not written to HBM.
2. The \(QK^T\) product is not written to HBM.
3. The attention scores are not written to HBM.
4. Similarly-parallelized elementwise operations (e.g. division, addition) are fused to avoid intermediate tensors in HBM.

Their first attempt — torch.compile with the Triton backend — satisfied constraints (1), (3), and (4), but not (2): it could not automatically discover the fused matmul+softmax trick that FlashAttention uses (partitioning work along the Q dimension, keeping one Q tile resident in SRAM, and streaming K/V tiles through it while running an online softmax). So they hand-wrote the fused kernel in Triton.

The wrinkle for the second statistic (average attention per token in the K dimension) is that it requires reducing over the query dimension — the opposite axis from what the fused matmul+softmax kernel already partitions over. That forces a second kernel, partitioned over K instead of Q, which has to recompute softmax (since the scores were never stored) — but it can reuse the row-wise max/sum tensors the first kernel already computed and stored (both only \(O(Q)\) in size, so cheap to keep in HBM).

flowchart TD
    IN["Q, K in HBM"] --> K1["Kernel 1 — Softmax + row-wise stats<br/>(reduction over K dim, Q-dim partitioned, online softmax)<br/>• pre-exp max over K (numerical stability)<br/>• post-exp sum over K (softmax normalizer)"]
    K1 -->|"pre-exp max, post-exp sum<br/>(both O(Q), written to HBM)"| K2["Kernel 2 — Softmax + column-wise stats<br/>(reduction over Q dim, K-dim partitioned;<br/>re-derives softmax from Kernel 1's stats)<br/>• post-softmax sum over Q → avg. attention/token<br/>• count of scores below p·max over Q → sparse count"]
    K2 -->|"partial sparse-count per thread block"| K3["Kernel 3 — Sum reduction<br/>of partial sparse counts"]
    K3 --> OUT["Attention statistics:<br/>avg. attention score / token (scoring)<br/>+ per-layer sparsity ratio (budget allocation)"]

The authors report that each of their two hand-written Triton kernels has roughly the same latency as a FlashAttention kernel — evidence that the 3-kernel partitioning is close to optimal for this problem. Given that overhead, they note the practical need to keep the number of query tokens used for statistics small (their benchmark uses only the last 50 tokens of the prompt).

A.4 — Detailed speed benchmark results

Measured with PyTorch Profiler (summing GPU-kernel latencies only, excluding CPU-side overhead not attributable to the method). Blank cells indicate the inference server ran out of GPU memory during prefill at that batch size / prompt length combination.

Prefill overhead — cumulative latency (ms) of computing attention statistics (50 query tokens), eviction scores for all prompt tokens, and copying the post-eviction (90%-compressed) KV cache into contiguous memory:

Prefill speedup — ratio \(\frac{\text{prefill}}{\text{prefill} + \text{overhead}}\) (i.e. how much prefill latency the statistics overhead “costs”; values below 1.0 indicate overhead, never more than 6%, and it shrinks as prompts get longer):

Decoding speedup — ratio of decoding latency with a full KV cache vs. decoding latency with a 10%-of-prompt-length KV cache:

End-to-end speedup — ratio of full-cache baseline latency to VL-Cache latency, where VL-Cache latency includes prefill + overhead + 99 decoding passes (100 output tokens total):

A.5 — Measuring attention to visual vs. language tokens

Beyond raw sparsity, the authors quantify how much of a layer’s attention “budget” goes to visual tokens vs. language tokens, using two complementary metrics.

Contribution measures each modality’s share of the filtered (sparsified) attention mass. Let \(T\) be the current sequence length, \(t\) the index of the first decoded token, and \(A^{(l)} \in \mathbb{R}^{T \times T}\) the attention matrix at layer \(l\) for one head:

\[ \text{Contribution}^{(l)}_{mod} := \frac{1}{T - t + 1} \sum_{i \ge t} \frac{\sum_{j \in J_{mod}} \text{ThresholdFilter}(A^{(l)}, p)_{ij}}{\sum_{j \in J_{all}} \text{ThresholdFilter}(A^{(l)}, p)_{ij}} \qquad (3) \]

where \(J_{mod}\) and \(J_{all}\) index one specific modality (vision or language) and all modalities respectively.

Coverage instead measures each modality’s share of the tokens that survive a hard top-k cache-eviction cutoff (rather than share of raw attention mass):

\[ \text{Coverage}^{(l)}_{mod} := \frac{1}{T - t + 1} \sum_{i \ge t} \frac{\sum_{j \in J_{mod}} \text{TopK}(A^{(l)}, k)_{ij}}{\sum_{j \in J_{all}} \text{TopK}(A^{(l)}, k)_{ij}} \qquad (4) \]

\[ \text{TopK}(A, k)_{ij} = \mathbb{1}\!\left[A_{ij} \in \{A_i^{(r-k+1)}, A_i^{(r-k+2)}, \dots, A_i^{(r)}\}\right] \qquad (5) \]

Here \(k := \lfloor \alpha \cdot T \rfloor\), \(r\) is the number of columns of \(A\), and \(A_i^{(n)}\) denotes the \(n\)-th order statistic (rank) of row \(i\) — i.e. \(\text{TopK}\) is an indicator for “this score is among the top-k in its row.”

Why this matters for the method: because the vision/language attention split itself varies by layer (heavy vision in layer 1, heavy language from layer 3 onward, with a middle-layer bump in visual importance), the optimal per-layer budget plausibly also depends on the ratio of visual to language tokens in a given prompt. Static, pyramid-style schedules can’t adapt to that; VL-Cache’s per-prompt, per-layer, sparsity-derived allocation can.