KeyDiff: Key Similarity-Based KV Cache Eviction for Long-Context LLM Inference in Resource-Constrained Environments
Authors: Junyoung Park
Dalton Jones
Matthew J Morse
Raghavv Goel
Mingu Lee
Christopher Lott
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
LLM
Key-Value Cache
KV Cache
KV Cache Eviction
Token Eviction
Efficient LLM Inference
Primary area: deep_learning

Abstract: We demonstrate that geometrically distinctive keys during LLM inference tend to have high attention scores. Based on the phenomenon we propose KeyDiff, a training-free KV cache eviction method based solely on key similarity. Unlike other KV cache eviction methods, KeyDiff can process arbitrarily long prompts within strict resource constraints and efficiently generate responses.
We provide a theoretical basis for KeyDiff by relating key diversity with attention scores. These results imply  KeyDiff can efficiently identify the most important tokens to retain. Notably KeyDiff does not rely on attention scores, allowing the use of optimized attention mechanisms like FlashAttention. Under a strict memory allowance, we demonstrate the effectiveness of KeyDiff for the Llama and Qwen model families by observing a performance gap of less than 0.04\% with 8K cache budget (~23\% KV cache reduction) from the non-evicting baseline on LongBench for Llama 3.1-8B and Llama 3.2-3B. We also observe near baseline performance for Deepseek-R1-Distill-Llama-8B on the Math500 reasoning benchmark and decrease end-to-end inference latency by up to 30\% compared to the other token-eviction methods.

KEYDIFF: Key Similarity-Based KV Cache Eviction for Long-Context LLM Inference in Resource-Constrained Environments
Junyoung Park
Dalton Jones
Matthew J Morse Chris Loft
Raghavy Goel
Mingu Lee
Qualcomm AI Research
(junpark, dalaik daltjons one, wttettttoeetttssooooaoooooooorre m mingul, clot] oou.eroattttti..all.lcc.......ma qualcomm. com
Abstract
We demonstrate that geometrically distinctive keys during LLM inference tend to have high attention scores. Based on the phenomenon we propose KIFD training-frree KV cache eviction method based solely on key similarity. Unlike other KV cache eviction methods, KEYDIFF can process arbitrarily long prompts within strict resource constraints and efficiently generate responses. We provide a theoretical basis for KEYDIFF by relating key diversity with attention scores. These results imply KEYDIFF efficiently identify the most important tokens to retain. Notably KRYDIFF does not rely on attention scores, allowing the use of optimized attention mechanisms like FlashAttention. Under strict memory allowance, we demonstrate the effectiveness of KEYDIFF for the Llama and Qwen model families by observing a performance gap of less than 0.04% with 8K cache budget (~~ 23% KV cache reduction) from the non-evicting baseline on LongBench for Llama 3.B and Llama 3.2-3B. We also observe near baseline performance for Deepseek- - RRI-Distil--Llama-B on the Math500 reasoning benchmark and decrease end-to-end inference latency by up 30% compared the other coken-eviction methods.
Introduction
Key- Value (KV) caching is a standard technique to accelerate large language model (LLM) inference that reuses key and value states (KVs) from previously processed tokens, enabling efficient autoregres- sive generation. This is crucial for long-context applications such as document summarization, code generation, question answering [7, 25, 31, 10], retrieval augmented generation [19] and reasoning [34, 17, 41]. However, the memory footprint of the stored KV cache grows linearly with input length, environments.
which becomes bottleneck in memory-constraiie
This challenge is particularly acute for LLM inference on edge device, where compute, memory, and power resources are limited [3, 22, 32, 36]. While KV cache eviction policies have been proposed to bound memory overhead by removing unimportant KVs (often measured by attention scores) [35, 24, 43], they typically process the entire prompt at once and violate memory constraints during intermediate computation.
To enforce strict memory bounds throughout the prompt prefill and token generation inference phases, we adopt block-wise inference strategy: the input prompt is divided into smaller blocks which are processed sequentially by the model, similar to [18, 1, 37]. After processing each block, we evict some of the cached KVs by according to an eviction policy that scores each KV, as illustrated in Figure 1. Unlike previous approaches that apply eviction after processing the entire prompt, this
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

V
Q
A
Attontion
Attemtion
Attention
Enweddoing
Top-K
Top-K
Top-K
Valus
Cochred KV
Figure 1: An example of block prompt processing with KV cache eviction. The input prompt having length of 7 is segmented by three blocks, and transformer layer in LLM processes each block by (1) computing key-value states from inputs, (2) computing attention, (3) computing the eviction score, and (4) performing eviction based on the eviction score to satisfy the memory constraints (e.g., at most 4 tokens can reside in the cache). After each block processing, the KV cache is updated and passed the next round of block processing, satisfying imposed memory constraints on the KV cache.
strategy satisfies memory constraints throughout the full inference process. However, we observe degradation in accuracy when applying existing eviction methods in this setting (Table 1).
We hypothesize that the performance drop stems from mismatch in design: methods assume access to mull-prompt attention, where key importance is computed over the entire input. During block prompt processing, however, attention is computed using only the current block's tokens without access to future blocks. As a result, attention scores based on a limited context often fail to reflect token's true importance across the full prompt.
existing eviction
To this end, we observe that keys with lower average pairwise cosine similarity tend receive higher attention scores across variety of inputs. This suggests that key diversity serves as strong proxy for global token importance, even without access to future tokens. This insight enables an attention-free approach to cache eviction that is based on the geometry of the cached keys.
Motivated by these observations, we propose KEYDIFF, an attention-free cache eviction method that removes redundancy among cached keys, operates effectively during block-wise wise inference, and avoids excessive memory overhead. Our contributions are summarized follows:
Insight. We observe that lower pairwise cosine similarity among keys correlates with higher attention scores, suggesting its utility as a proxy for token importance. (Section 3.1)
Method. We introduce KEY DIFF, an eviction strategy that selects keys based on their similarity to other cached entries without relying on attention scores future tokens. (Section 3.2)
Theory. Through our analysis of key and query geometry we provide a theoretical understanding how/why KEYDIFF works. We also show that KEYDIFF solves an optimal subset selection problem that maximizes key diversity. (Section 3.3)
Performance. KEYDIFF achieves S 1.5% and I 0.04% accuracy drop on LongBench with 6K and 8K cache budgets, respectively, outperforming srate-of-the-as eviction methods across Llama and Qwen models (Section 4.2), and near non-evicting baseline performance for Deepseek-R1. Distill-Llama-8B on the Math-500 reasoning benchmark. (Section 4.3)
Efficiency. We observe up to 30% end-to-end inference latency reduction using KEYDIFF compared to existing KV cache eviction methods. (Section 4.5)
2 Background
2.1 Transformers
The Transformer architecture [33] processes input data using a sequence of transformer blocks. A
transformer block f takes sequence X (æ) x2, .TT Txxx as input and applies the causal self-attention operator Attention followed by a feed-forward network FF with optional gating [28] produce the output X'
(x', 2'y........ ....,,,.....
247 .,,
Txd,
X' f(X) FF (AAttenntinn(X),
(I)

---

The causal Attention operator projects each input token with matrices Wg. We, W. E Rdxd into
key, query, and value matrices (K XW k- Q XWo. V XWr, respectively) then applies the following relation produce the attention output 2:
Oatta Softmax (QK*
T |Va+ M) V AV
(2)
where Oattn E Rxxd and the causal attention mask M is an upper triangular matrix with nonzero values of -00.
2.2 KV Caching
When the Attention operator processes a new token 21+1, it must also recompute the prior KV states for tokens 2o. æT. This can be avoided by storing previously computed KVs in KV cache
C = (K, V) for later reuse and append the new KV corresponding 27+1 to the cache. We can apply Equation (2) an existing KV cache C' as follows:
attn OT
Softmax (qr+i|K [Kr+1] //a + M) [V]lt++]:
where KT+1, QT UT are the key, query, and value states of IT+I, and [X] [X|]=++]] represents the concatenation of øT-1 to existing tensor X along the time dimension, M is the causal attention mask accounting for both the KV cache and ø1+1-
KV caching dramatically reduces the latency of Attention by only computing kT+1. 4T+1, DT+1 for each token 4T++ 1 and reusing the KVs in However, the size of the KV cache increases linearly with the number of processed tokens and dominates the memory footprint in long-context applications [39].
2.3 KV Cache Eviction Methods
To limit the memory footprint of the KV cache, we fix cache budget N, which is the maximum number of tokens to be stored the cache. a new KV is added to cache and the updated cache size is greater than N, we must evict KVs from the cache until the cache budget is met. The eviction policy NN (C) evicts subset of KVs from C' and returns a new cache C' containing at most N KVs:
C ([K] [V]le
C' (C)
Attention-Based Eviction Policies Attention-bass eviction policies n use aggregated attention values to rank each KVs' relative importance and keep the N highest scoring KVs. For given attention weight aggregation function d, the eviction policy "N performs the following steps:
S topk( (p))
(5)
K" gather(K,K) S),
V = gather(V,S))
where topk(æ, NN) returns the indices of N N-largest values of and gather(X, S) gathers columns indexed by S.
Attention-based eviction methods prioritize KV pairs with higher attention scores to past tokens.
This is problematic when applying block prompt processing: all input tokens are not simultaneously accessible within Attention, only those in the current block and cache. This result in an incorrect eviction decision. Additionally, attention- eviction often requires explicitly materializing A, which can be resource intensive. We discuss the attention-based eviction policies further in Section 5.
2.4 KV Caching in Desource-Constrainee Environments
Existing eviction policies like Zhang et al. [43], Oren et al. [24] focus on processing the entire input prompt at once: KVs are computed for each token in the prompt and stored in cache C, then the eviction policy n is applied to reduce the number of tokens in C' to N, before token generation.
"The multi-head extension and output projections omitted for brevity.

---

Conatre Simfartty Hiedd
Attention Weight (aayer
Oveine Simbbrity Hlad
Alteation (Layee liww
22
0.000 0000000
layindac
layiddas
(a) Layer and Head
(b) Layer 11 and Head
Cosine similarity the keys and attention weights. Measured from Llama 3.2-3B- Instruct and the first sample from the NarrativeQA dataset in LongBench. Truncated to the first 64 tokens for visualization.
Figure 2:
However, the intermediate cache C. before eviction will grow to the size of the input prompt. This can often exceed model's 's allocated memory limit when deploying long context applications resource constrained environments.
As demonstrated in efficient LLM inference frameworks [1. 14, 18, 36], one solution is to apply n
more frequently by segmenting X into non-overlapping blocks X = X1, Xm-il, where
X, Bi -B B is the block size, and = [T/B], and iteratively updating the cache by exploiting causality, applying Equation (4) in a block-wise fashion:
C. - ([K,- [I il, [V; 1
(6)
C - xC,),, C. C,
C₁ Co = 0,
where KBIB((+1)-1 and UBs:B(++1)-1 are the keys and values selected from X; respectively, and C, = (K,, Vi) is the KV cache after processing the first prompt blocks. As in Equation (4), we concatenate the B new KVs to the current cache, apply an and update the cache in Equation (6).
We refer to this as block prompt processing. Its main advantage the ability to control of the compute and memory overhead of KV cache management by adjusting the block size B and cache budget N. Note that, in a decoder-based architecture, applying block prompt processing to with = T yields the same result as processing all of X at once and choosing B 1 corresponds to the token generation phase of LLM evaluation.
Lttention-Basee Token Eviction Challenges Despite its advantages, block prompt processing introduces a challenge for KV cache eviction: eviction decisions in block X, impact the cache used by Xi+1. causing eviction errors to compound over time. When the model processes X,, attention- based eviction methods retain KVs with high attention weights derived from Xo...., rather than all of X, which may prematurely evict KVs with high weights in upcoming blocks.
3 Method
We demonstrate negative correlation between attention scores and the cosine similarity among keys (Section 3.1) and leverage this observation to develop KEYDIT (Section 3.2). followed by a thcoreti- cal justification of KEYDIFF (Section 3.3) and preliminary evidence of its efficacy (Appendix C.2).
3.1 Correlation of Attention Scores and Key Dissimilarity
To address the shortcomings of attention-based KV cache eviction in Section 2.4, we develop an alternative attention-fret free scoring metric that retains significant KVs across blocks while being resource efficient. We recall the "attention sink" phenomenon: LLMs often assign high attention weight to the first few tokens, regardless of the input [35, 29]; these highly weighted tokens are called sink tokens. However, the index of the sink tokens can vary across heads and layers and reside deeper in the sequence than the first few tokens. This observation motivates the following hypothesis: high attention scores can be determined by the intrinsic properties of the keys rather than by any particular combination of keys and queries.
Correlation of Key Similarity and Attention Scores We evaluate our hypothesis by inspecting the cosine similarities between keys computed inside attention block. We visualize the pairwise

---

cosine similarities between keys along with the attention weights in two particular heads and layers in Figure 2. We observe that keys with lower cosine similarity with other keys exhibit higher relative attention scores regardless of the choice of query, such as the 4th and 15th keys in Figure 2a, or the 1st key in Figure 2b. Pairwise cosine similarity keys is solely function of the keys in the cache, which are independent of input queries; the surprising aspect of Figure is the negative correlation with attention weights. These distinctive keys essentially recover the attention sink phenomenon [35].
3.2 KEYDIFF
Based on the observation in Section 3.1, we propose KEYDIFF, which evicts tokens from the KV cache based on key similarity. If the cache C. has intermediate size n and budget N where n >> N, KayDur is defined as:
N
S = Cosk(-CosSimm(A CosSimosSmmm
K' S)
V = (athor(V,S)
where K E Roxd and V Ra are the cached keys and values, CosSim(K) E R=xx is the pairwise cosine similarity matrix of keys in K with CosSim( (K) = T |Ry vector of ones.
k;
and 1 E R" is a
Efficient Variant of KEYDIFF Unlike attention- based eviction policies. KEYDIFF does not require access to the attention weights A, facilitating opti- mized attention kernels that do not materialize A such FlashAttention [8]. However, computing the
2
5
Negative Simtinity
Anchior
pairwise cosine similarities runs in O(r²) time. For- tunately, we can compute the score of each token in Equation (7) in (n) as follows:
Kay-Vatue
Anchor
Top-K
topk(= (Coos-CCoo((())))) k)),
(8)
Scord
Ratained Thlown
2
We refer to n (R) the anchor vector. We show this formu- lation retains the same KVs of Equation (7) under mild condition. (see Appendix C.2). Our exper- imentation has shown that the anchor vector μ ((K) can be replaced with μ(() without losing accuracy (see Table 15). We evaluate the efficient KEYDIFF described in Figure 3 using unnormalized keys & in all subsequent sections. Figures 5 and to 10 visu- alize the keys retained and evicted by sink attention
where v(K) - + Σm & and k; by [
Figure 3: An overview of KEYDIFF. (1) KEYDIFF first computes the anchor vector by taking the average of the keys in the KV cache, (2) computes the cosine similarity be- tween the keys and the anchor resulting in eviction scores whose color intensities indi- cate the score values, and (3) retains the KV pairs with the lowest similarities.
[35], TOVA [24] and KEYDIFF via PCA. KEYDIFF retains more varied keys. full complexity and FLOP analysis can be found in Appendices B and B.I
KEYDIFF with Sliding Window In tasks such as reasoning and coding, where the most recent tokens are often important, of the cache budget for a sliding window [6]. which we call KEYDIFF with sliding window. This extension introduces no complexity memory overhead and we observe better results on certain tasks than vanilla KEYDIFF (Table 14 and Appendix E).
augment KEYDIFF and its efficient variant use percentage
3.3 Why KEYDIFF Works: A Theoretical Perspective
To solidify the theoretical foundation of KEYDIFF and show that KEY ultimately selects keys most aligned with queries, we prove the following two results. We first validate the relationship between cosine similarity and attention scores observed in Figure 2 by bounding the attention score of a new incoming key Ee in terms cosine similarity with a fixed query q:
Lemma 3.1. Suppose that for a fixed query token g, there is a set of key tokens (his) )im such that || M, V i. Without loss of generality suppose ||q|| 1 and assume k* is key not in {ki )
5

---

alu
Uli
(a) Sink Attention
(b) TOVA
(c) KRYDIFF
(d) Retained keys only
Figure 5: (a, b, and c) PCA Visualizations in two dimensions of a key cache managed with Sink, TOVA, and KEYDIFF. Retained tokens are blue, while evicted tokens are orange. Keys are taken from layer 5 and head 3 of Llama3.2-31 2--nnnnntttt and generated using the Narrative dataset. (d) PCA visualization of the retained keys for each KV cache eviction method.
with | 1
< M that has attention weight w > 0. Then, for 1t - oc,
logg11 w) 1 CosSim(k",,
2M
We then establish relationship between the cosine similarities of k. q, and the mean of prior keys k Theorem 3.2. Consider tokens k", as above, and the average of the keys tokens k. Suppose CosSim(k' .9) = 3g 0 and CosSim(k, q) Ogy < 0. Then
CosSim(k, k*) = + 3g - 0.5a 2 0.5,3 g"
(9)
By combining Lemma 3.1 and Theorem 3.2, we establish a relationship between the attention weight w and the KEYDIFF score CosSim(k, k*).
Query Key PCA Plat (Layer0 Head0)
As CosSim(K, (k, q) decreases and CosSim k*,4) q) in- creases (along with the attention weight w), then CosSim k, k*) tends to 11: this means KEYDIFF se- lects distinet keys most aligned with q. We visualize this in Figure 4 with PCA embedding of keys and queries from a single head of I.lama 3.2 3B, high- lighting the relationship between top scoring keys via KRYDIFF, the anchor vector and queries. Simi- lar trends are found from the other layers and heads as shown in Figure 11. The proof's of Lemma 3.1 and Theorem 3.2 are in Appendix C.3, along with empirical motivation for the chosen assumptions.
2nd principle componentt
2999
5.0
2.5
0.0
SA
-2.
Query
55.0
KeyDiff Average key
-7.5
Key
-20
10
10
1st principle
Figure 4: PCA embedding of keys and queries from Llama 3.2 3B
Experiments
In this section, we empirically demonstrate the effectiveness of KEYDIFF, We begin with a description of competing,
eviction methods, followed by detailed description of the evaluation setup, then present our experimental results. Our findings can be summarized as follows:
Beedle-In-a-Haystackk KEYDIFF outperforms competing eviction policies on the Needle-In- In-A- Haystack benchmark (Section 4.1).
LongBench. KEYDIFF outperforms competing eviction policies with block size B = 128 on LongBench, achieving an 1.5% accuracy drop with a 6K cache budget (~33% compression rate) and < .04% with 8k cache budget (~23% compression rate) with ---ma--.---B-Insttiie and Llama-3.2-3B -nnstuttt (Section 4.2).
Reasoning. KEYDIFF performs competitively the Math-500 reasoning benchmark with other eviction methods using the DeepSeek-RR -ieekk-R--issilll---- -i-ttiill--wen---7 7 and Llama-8B, and shows near eviction- Distill-Llama-SB.
free baseline performance when augmented with sliding window (Section 4.3) for DeepSeek-RI-
A blation Study. We perform ablation study on the main parameters of KEYDIFF and show that utilizing negative cosine similarity as the eviction criteria and the mean of cached keys as the anchor vector performs best. (Section 4.4).

---

(a) TOVA
(b) SnapKV
(c) KEFDIFF
Figure 6: Accuracy across document length and needle depth for needle in a haystack test. Cache
size is 6K with B 128.
Efficiency. We compare the end-to-end inference latency KEYDIFF, [20] and [24] and observe 30% latency improvement with KEYDIFF (Section 4.5).
Experimental Setup We apply several cache eviction methods to several decoder-only transformer-
based language models, including Llama 3.1-8B-Instruue [10]. Llama 3. 3.2-3B-Instruct [10], and Qwen 2.5-3B7BB-Instuul [38]. We evaluate these models using H2O [43], TOVA [24], SnapK V [20], and StreamingL.LM [35], (or "sink attention") cache eviction policies, along with the eviction-free model as a baseline. We simulate resource constrained environment by processing prompts and generating responses using Equation (6), with block size of B 128 for prompt processing and B 1 for token generation using greedy decoding for all experiments. We denote the cache budgets of 2048, 4096, 6144 and 8192 2K, 4K, 6K and 8K, respectively.
4.1 Needle In a Haystack
To compare the impact of various cache eviction policies fact retrieval, conduct the "Needle In a Haystack" test [21, 16]. This test embeds specific information ("needle") at different points within body of unrelated text ("haystack"); finding and retaining the needle is challenging for eviction policies, which can't know what information must be retained during block prompt processing. The results shown in Figure 6 and Figure 19, where Instruct across different document lengths (x-axis) and needle depths (y-axis) with a cache size of 6K. KEY DIFF performs similarly to TOVA, SnapKV and sink attention for shorter documents and outperforms all three methods as the document length increases.
show the recall accuracy of Llama3.2-31
4.2 LongBench
LongBench [4] a bilingual, multi-task benchmark suite for LLMs, providing a comprehensive stress test for long prompt inputs. LongBench is useful for evaluating cache eviction methods in resource constrained environments with fixed memory budget: 51% % of prompts are longer than the largest KV cache size of 8K. For cache budgets of 6k and 8k tokens, prompts LongBench compressed by 33% and 23% respectively on average, (see Appendix F.3 for more detail.)
Table 1 summarizes the evaluation results of Llama 3. 1.1--B--lae Instruct and Llama 3.2-3B- InI-trctt the English subset of LongBench with 2K, 4K, 6K, and 8K cache budgets using various eviction policies with block prompt processing enabled with B = 128. As shown in Table 1, DIFF outperforms other eviction strategies across most tasks, even demonstrating better performance with smaller cache budgets. KEYDIFF shows significant improvement which tests whether long-term dependencies within a long prompt can be correctly recognized [4], while achieving near full-context model performance even with the smallest budget. Adding sliding window to KEYDIFF improves coding task performance (Table 14). We observed similar trends in the full LongBench task suite shown in Table 11 and in the additional results in Appendix F.
the PassageRetrieval-en (PR-en) dataset,
KEYDIFF exhibits similar or better performance compared to competing methods. Notably, the attention-base based methods (e.g., H2O, TOVA, and SnapKV) show significant performance improve- ments over the B = 128 case. This result supports our hypothesis: an eviction scheme robust to changes in the scope of comparison among tokens is essential in memory constrained environments where token-wise attention weight can't be fully materialized.
We present the full evaluation results in Table and more complete compar- isons LongBench in Appendix F, such as: standard prompt processing with single large block
Additional Results
7

---

Table I: Llama-3.1-8B/33--9B- Instrruutt LongBench results with B = 128 (Higher is better). We highlight the best and second best methods within a given budget with bold and underline. We omit Chinese dataset results and other model results due space limit. The full evaluation results are in Table 11. f: A subset of samples (183/200) were evaluated due to OOM errors.
Stagk
Mall Dac.
Fowshed Leansng
Sysietic
Gooe
GooRopert
Liaaa81144 1-00
30.05
36.12
57.33
47.31
34,36
25.32
27:02
12.00
43.57
8.33
09.30
$1.06
$1,34
25
1:34
31.15
25.33
16.11
26:15
9.75
3.17
3.70
16:78
64:00
13.39
7.63
1.25
3.50
40.15
12:14
16:59
1741
24.93
8.53
48.90
6640
11
11:35
36.31
(2.08
58.36
0.25
16.03
20.51
13:85
44.50
47.31
43.04
46.99
23.55
15.75
11.35
26.43
66530
69.05
13.43
5.25
62.3
59.74
56.25
39.30
12.57
$1.20
65.56
56,45
14:77
13:37
21.17
26.35
(2.59
90.73
42.74
18.00
02.68
52.48
37:52
TOVA
23.00
04.55
16.70
33.56
10.05
23:15
06.96
61.90
60.56
27
310
63.53
01.00
53.00
34.56
45.75
54.93
54.53
09.30
35.40
$3.44
34.76
27.00
71.00
91.11
1.229
6:25
57.00
61.09
51.79
47.59
SaA
23:41
13.04
03:01
46.13
90.56
11:01
41.33 34
14.00
$1.88
22.19
21:47
26.81
10/00
12.00
01.55
$3.30
43
52.33
18
17.17
06.81
91.55
19:01
$3.00
3.35
02.18
46:43
51.33
SegeEV
31.79
34.10
44.33
45-57
30.44
33.12
18:19
65.41
30.55
34.33
32.19
$2.43
23.68
25.33
36.55
27.03
67.51
11.30
90.96
93.25
17:14
0.58
5:17
5.25
09.00
01:14
61.32
52.15
51.30
25:64
41.75
$0.99
51.59
06.47
22.84
15.00
33.86
36.36
66.30
85.00
18:26
3.17
96.00
5617
56.43
44.3
Kay/lue
65
23:00
46.35
05.10
56.90
09.95
11.53
13.40
36.98
36.98
73.00
$0.00
1.100
5.27
09.3 53
61.00
(0.33
48.51
33:57
27.81
12.30
43.11
533
31.76
40.25
91.99
50.09
36.44
$3.19
24.31
25.31
12.90
60.11
62:48
3181
96.50
56.22
96.33
1.63
19:96
11.30
19.00
19.55
2:85
0.78
1.55
15.97
41:00
11.95
0.93
8:50
0.50
16:71
13:91
14:55
2.92
34.49
25.98
3.44
22.75
$3.00
10:33
22.34
98.56
$3.55
0.50
1340
54.55
0.55
59.90
13.00
38.00
20.41
21.46
13.00
15.35
24.97
1000
64.50
$2.19
2.00
24.50
55.00
50.99
33.46
12:41
15.96
10.35
13.06
76.15
19:31
25.04
56.90
10:15
3.40
11
65.91
63.6
11.57
23:2
15.55
-2.47
44.12
38.42
13:22
25:36
21.36
24.55
62.30
13.00
41.50
3.00
23.33
25.72
56.55
35.24
31 06
1047
49.3
18:00
41.41
13.05
$1.60
25:85
06331
69/00
$5.25
19
3.50
71.00
45.77
47.47
4131
19.66
16.61
36.33
13.99
36.64
1335
36.32
26.19
24.00
11.81
1816
61:1
2.50
05.53
16-18
6341
17.56
47.00
35:15
41.91
16:15
42.34
$1.60
23.00
25.30
17.00
$4.36
12:07
3.50
16.90
SkpRVV
0R
1935
3335
16:65
45.48
74.5
49:30
00.08
37.98
50.38
10:04
26.79
$1.27
2575
25.01
25.99
02.50
60:00
$5.95
$5.35
41:47
40:15
4.00
2.50
02.50
85.00
55.0
55.76
57.93
2135
.1.00
16:5
05.11
16:09
35.11
13.99
16
31.45
25.0
60/
17:00
110
00.53
1111
KayBine
68
33.00
0048
91.1
43.0
5183
3.999
23.53
25.00
71.00
6000
17.00
3m
05.00
05.06
45.31
23.41
30.39
49.33
43.99
28.09
33.78
23.00
23.07
12.00
90.17
42.60
3.30
06.30
55383
58.63
(i.e. B = x) in Table 10; eviction method performance with Qwen 2.5-3 in Table 12;
performance behavior with block sizes B = [64, 256] in Table 13; and performance on KEYDIFF combined with sliding window described in Section 3.2. We also compare against the L2-norm minimizing eviction method of [9] in Table 11.
4.3 Math-500 Reasoning Benchmark
Reasoning is important long- mong-contettee task for LLMs. Unlike other long-context cases, reasoning typically involves a relatively short prompt followed by a long generation, which presents unique challenges for token eviction methods. To evaluate the effectiveness of token eviction methods, we apply KRYDIFF and SnapK V to the
and Llama-8B distilled models the Math-500 reasoning benchmark [13]. Surprisingly, we
[12], and assess their performance found that Llama equipped with KEYDIFF and a moderate KV cache budget performs comparably to, or slightly better than, the eviction free baseline, while also outperforming SnapKV. We kindly refer the reader to Appendix E for additional details on the reasoning task evaluation.
4.4 Ablation Study
We evaluate the design choices of KBYDIFF, including the similarity metries and the choice of the anchor vector, and validate the efficacy of KEYDIFF. We provide a full description of the test setup in Appendix G and summarize the findings here:
KEYDIFF anchor choice does not greatly impact benchmark accuracies (See Table 15).
KEYDIFF using cosine similarity as the distance metric outperforms other metrics (See Table 16)
4.5 Latency and Complexity
Additionally, in order to demonstrate that KRYDIFF decreases end-to-end inference latency, we measured time to first token for the Llama 3.2 3B instruct model using different block prompt
8

---

Block Sice
Block Stze:
Block 258
7
3ey TriA Snaplly
0.5 SeayiCy
StapkY
1177 CAP CAA
65-
40
Cache
Cocee
Crche Badge:
Figure 7: Time-to-fistt-okkn (TTFT) for Llama 3.2-3B using Flash Attention with different eviction strategies with block prompt processing sizes 64, 128, and 256.
processing sizes and cache strategies. These results are visualized in Figures 7 and 17. Since KEYDIFF does not require attention weight materialization, FlashAttention [8] can be used, resulting in up to 30% lower latency than TOVA and SnapKV. We compare the complexity of KEY with competitors in Appendix B and perform complete FLOP count in Appendix B.I.
5 Related Work
Sparse Attention LLMs often exhibit high attention sparsity, where small subset of keys receives
significant proportion of attention scores. This characteristic allows sparse approximation techniques
to reduce the computational cost of attention. Similar to PagedAttention [18]. Tang et al. [30]
estimates the importance of a page (a contiguous set of keys) to a given query, whereas Rehg [26]
further refined the budgets in per-head manner. On the contrary, sample-based based methods [44, 27] attempt to approximate token importance by inspecting the attention scores from the last few queries certain query channel dimensions. Despite their effectiveness in reducing computational costs, these methods do not address the memory overhead of the KV cache, which typically retains all KVs.
KV Cache Compression Different approaches compress the KV cache include architecture modification such as GQA [2]. which shares a KV cache across a small number of heads. Other techniques to compress the KV cache include quantization such as [15, 23, 42] in which the authors use various techniques to take advantage of existing patterns to efficiently quantize and compress the KV cache. More related to our work [40] uses scoring mechanism determine the precision the quantization for different tokens.
Token Eviction Methods Unlike the sparse attention and KV cache compression methods, eviction methods evict KVs from the cache reduce the size of the KV cache. As discussed in Section 2.3, the majority of the token eviction methods employ their own rules to decide the importance of the tokens by manipulating the attention score A. For example, by appropriately choosing the aggregation functions Φ(A) (A) of Equation (4), we can obtain existing attention-basse eviction methods as discussed in Appendix A. Attention-based eviction may be a better choice when the entire prompt is being processed at once, as the eviction can be done by assessing the importance of all tokens simultaneously. However, computing the full attention score of long prompts could be prohibitively expensive in resource-constrained environments.
6 Conclusion
Inspired by our observation that distinctive keys tend to have high attention scores, we propose KEYDIFF, training-free KV cache eviction method based on key similarity that enables large language models to operate in memory and compute constrained environments. We justify KEYDIFF by showing that it minimizes the pairwise cosine similarity among keys the KV cache, maximizing the aforementioned diversity. KEYDIFF significantly outperforms state-of of-te-of-the-art KV cache eviction methods under similar memory constraints, with only a 1.5% and 0.04% accuracy drop from the non-evicting baseline while achieving 33% and 23% KV cache memory reduction on LongBench. Similar to other token eviction methods, KEYDIFF is primarily designed and evaluated for the GQA attention mechanism used in models such Llama and Qwen. In future work, we plan to extend KRYDIFF for seamless integration with other attention variants, such as Multi-Head Latent Attention [12].

---

References
[1] Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ramachandran Ramjee. Sarathi: Efficient IIm inference by piggybacking decodes with chunked prefills. arXiv preprint arXiv:2308. 16369, 2023.
[2] Joshua Ainslie, James Lee- Thorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. arXiv preprint arXiv:2305. 13245, 2023.
[3] Keivan Alizadeh, Iman Mirzadeh, Dmitry Belenko, Karen Khatamifard, Minsik Cho, Carlo C Del Mundo, Mohammad Rastegari, and Mehrdad Farajtabar. Llm in a flash: Efficient large language model inference with limited memory. arXiv preprint arXiv:2312. /114, 2023.
[4] Yushi Bai, Xin Lv. Jiajie Zhang, Hongchang Lyu. Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. LongBench: A bilingual, multitask benchmark for long context understanding. In Lun-Wei Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 3119-3137 3137, Bangkok, Thailand, 172.
August 2024. Association for Computational Linguistics. doi: URL htattppss/aclllnhoooogggg /rt////.....1111oogoo.... aal-lclg..1.2
[5] Federico Barbero, Álvaro Arroyo, Xiangming Gu, Christos Perivolaropoulos, Michael Bronstein, Razvan Pascanu, et al. Why do Iims attend to the first token? arXiv preprint arXiv:2504.02732, 2025.
[6] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-documen transformer. arXiv preprint arXiv:2004.055/55 2020.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[8] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344 16359, 2022.
[9] Alessio Devoto, Yu Zhao, Simone Scardapane, and Pasquale Minervini. A simple and effective 1 2 norm-based strategy for kv cache compression. arXiv preprint arXiv:2406. 1430, 2024.
[10] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle. Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783 2024.
(11) Nathan Godey, Éric de la Clergerie, and Benoît Sagot. Anisotropy is inherent to self-attention in transformers. arXiv preprint arXiv:2401. 2024.
[12] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Iims via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.
[13] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2 103.038744 2021.
[14] Connor Holmes, Masahiro Tanaka, Michael Wyatt, Ammar Ahmad Awan, Jeff Rasley, Samyam Rajbhandari, Reza Yazdani Aminabadi, Heyang Qin, Arash Bakhtiari, Lev Kurilenko, et al. Deepspeed High-throughput text generation for llms via mii and deepspeed-inffrrecee. arXiv preprint arXiv:2401.0867,, 2024.
[15] Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length Imm inference with kv cache quantization. arXiv preprint arXiv:2401.18079 2024.
10

---

[16] G. Kamradt. Needle in haystack pressure testing llms. GitHub repository, 2023, URL https://gi thubbb. com/ oeeeaa//LLLLLeeeteeeeeeeeeeeoee
[17] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199-22213. 2022.
[18] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 61 626, 2023.
[19] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems, 33:9459-9474, 2020.
[20] Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation. arXiv preprint arXiv:2404.14466 2024.
[21] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-173, 2024.
[22] Zechun Liu, Changsheng Zhao, Forrest landola, Chen Lai, Yuandong Tian, Igor Fedorov, Yunyang Xiong, Ernic Chang, Yangyang Shi, Raghuraman Krishnamoorthi, et al. Mobilellm: Optimizing sub-billion parameter language models for on-device use cases. arXiv preprint 20w:22402.1490. 2024.
[23] Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A tuning-free asymmetric 2bit quantization for kv cache. arXiv preprint 200202240..027500 2024.
[24] Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers are multi-state mns. arXiv preprini urXiv:2401.06104 2024.
[25] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21(140):1-66 1-,7, 2020.
[26] Isaac Rehg. Kv-compress: Paged kv-cache compression with variable compression rates per attention head. arXiv preprint arXiv:2410.00166 2024.
[27] Luka Ribar, Ivan Chelombiev, Luke Hudlass-Gall Galley, Charlie Blake, Carlo Luschi, and Douglas Orr. Sparq attention: Bandwidth-effiiient I1m inference. In Forty-first International Conference on Machine Learning.
[28] Noam Shazcer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202. 2020.
[29] Mingjie Sun, Xinlei Chen, J Zico Kolter, and Zhuang Liu. Massive activations in large language models. arXiv preprint 24X. 2024.
[30] Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context I1m inference. arXiv preprint 4rX1v:2006.10774 2024.
[31] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint 23Xi::2307.09288 2023.
[32] Mart van Baalen, Andrey Kuzmin, Markus Nagel, Peter Couperus, Cedric Bastoul, Eric Mahurin, Tijmen Blankevoort, and Paul Whatmough. Gptvq: The blessing of dimensionality for Imm quantization. arXiv preprint arXiv:2402.15311 2024.

---

[33] A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[34] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. 2022.
Advances in neural information processing systems,
[35] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, 2024.
[36] Daliang Xu, Hao Zhang, Liming Yang, Ruiqi Liu, Gang Huang, Mengwei Xu, and Xuanzhe Liu. Empowering 1000 tokens/second on-device IIm prefilling with mllm-npu. arXiv preprint arXiv:2407.05888, 2024.
[37] Yuhui Xu, Zhanming Jie, Hanze Dong, Lei Wang, Xudong Lu, Aojun Zhou, Amrita Saha, Caiming Xiong, and Doyen Sahoo. Think: Thinner key cache by query-drived pruning. arXiv preprint WrXiv:240.220016 2024.
[38] An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li. Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei. Huan Lin, Jialong Tang, Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, Jianxin Yang, Jin Xu, Jingren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang, Mei Li, Mingfeng Xue, Na Ni, Pei Zhang, Peng Wang. Ru Peng, Rui Men, Ruize Gao, Runji Lin. Shijie Wang, Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wenbin Ge, Xiaodong Deng, Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Xuejing Liu, Yang Fan, Yang Yao, Yichang Zhang, Yu Wan, Yunfei Chu, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, Zhifang Guo, and Zhihao Fan. Qwen2 technical report, 2024. URL https:/ /tts:///axxivv org/ abs/ /200. 10671.
[39] Dongjie Yang, XiaoDong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. Pyramid- infer: Pyramid kv cache compression for high-throughput 1lm inference. arXiv preprint arXiv:2405. / /2532, 2024.
[40] June Yong Yang, Byeongwook Kim, Jeongin Bae, Beomseok Kwon, Gunho Park, Eunho Yang, Se Jung Kwon, and Dongsoo Lee. No token left behind: Reliable kv cache compression via importance-awiin aware mixed precision quantization. arXiv preprint arXiv:2402.18096 2024.
[41] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
[42] Tianyi Zhang, Jonah Yi, Zhaozhuo Xu, and Anshumali Shrivastava. Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization. arXiv preprint arXiv:2405.03917 2024.
[43] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024.
[44] Qianchao Zhu, Jiangfei Duan, Chang Chen, Siran Liu, Xiuhong Li, Guanyu Feng, Xin Lv, Huanqi Cao, Xiao Chuanfu, Xingcheng Zhang, et al. Sampleattention: Near-lossless accelera- tion of long context Ilm inference with adaptive structured sparse attention. CoRR, 2024.
12

---

KEYDIFF Supplementary Material
A Extended Related Work
A.1 Attention-based eviction methods
In this section, we provide a unified framework to understand prominent attention based eviction methods. As mentioned in Equation (5), we can specify attention- -based eviction methods under the unified framework with proper selection of the aggregation function ((A) follows:
TOVA [24]: TOVA (A) = A 1,5
H2O [43]: H20 (A) Aprev A A
SnapKV [35]] &f SnapkV (A) = (AT1) * K, where K is a vector of and l is the kernel size of average smoothing.
B Runtime and Memory Complexity
We analyze the runtime and memory complexity for the prominent KV cache eviction algorithms in Table 2. For given block size B and cache budget N, KEYDIFF requires ON B) runtime and memory. The same holds true for TOVA, since it only requires computing the bottom row of A. Sink attention retains the first tokens the input sequence, followed by a sliding window of size I., resulting in O(k + L) O(N) memory and runtime, since k + T. equals the chosen cache budget. SnapKV V computes attention over sliding window of size against N + keys from the incoming block and the key cache, the memory and runtime complexity is O((N B).). H2O accumulates attention weights over all tokens, and computes the attention over the current block, so will require O(N B B²) memory overhead and runtime. We summarize these details in Table 2
Table 2: Runtime and memory complexity of token eviction methods.
Runtime Complexity
Memory Complexity
KEYDIFF
O(N B)
O(N B)
TOVA
O(N + B)
O(N + +B)
H2O
O(NB + B2)
O(N + 132)
SnapKV
O((N + +B)L)
O((N + B)L)
Sink
O(N)
O(1)
B.1
FLOP count of KeyDiff
The bulk of the computation in KeyDiff (neglecting the 'topk' operator) is the following two expres- sions:
μu K
Rs
Ziz1
= (osSim((((K). ky)
p
i 1,...,
We will count the total number of additions, multiplications, square roots and divisions required by KeyDiff separately, since division and square root implementation are hardware-dependen,, then
13

---

assign weights to each operation at the end for final count. Norms are assumed to be 2-norms. We count the FLOPs required for each operation as follows:
||ki|| Vi; ky: since h; E IR: d multiplications, d - additions, one square root. Repeating for each i, this contributes nd multiplications, vid - additions, and n square roots.
A; naively, d divisions, but can be rewritten as one division and d multiplications. Repeating for each i, this contributes nd multiplications and n divisions.
E Ci for I one division, (n 1)d additions.
Combining the above, we can compute the anchor vector using 2nd multiplications, 2nd - 71 additions, square roots and
divisions.
To compute the cosine similarity score, we have from above that (KK) kk requires nd multiplications and n(d additions. Also from above, have that computing I| [)] requires multiplications, d - additions and one square root. We reuse the computation of ||k from the previous step and compute ||As|IIla(RR K|] in multiplications and max( (Iss p [I],, e) with more additions (assuming boolean comparison equals addition in cost). We can then divide through to compute
max( kell I.e) with n divisions. Therefore, computing the cosine similarity between the anchor and each key requires nd + + multiplications, nd + d - additions, n + 1 divisions and one square root.
k(R)
Adding everything up. KeyDiff requires:
1. 3nd n multiplications,
2. 3rd
additions,
3. 2n + 2 divisions,
4. n + square roots,
If, based x86 instruction tables, declare additions and square roots cost FLOP (i.e. be computed in one cycle), multiplications cost three FLOPs, division is roughly 47 FLOPs, we arrive at final FLOP count of:
3 3nd + d + n) + (3nd 1) 47 47 (2n + + (n + 1) (12d + 97) 3d 94. (A.1)
This is linear in the number of keys n with a small constant, relative to the quadratic complexity of the attention operator.
C KEYDIFF: A Theoretical Perspective
C.1 Additional PCA Visualizations
In order to demonstrate the phenomena in Figure 11 persists across all heads and layers, have included several more visualizations as seen in Figure 8, Figure 9, and Figure 10.
Bmal
(a) Sink Attention
(b) TOVA
(c) KEYDIFF
(d) Retained keys only
Figure 8: (a, b, and c) PCA Visualizations in two dimensions of a key cache managed with Sink, TOVA, and KEYDIFF. Retained tokens are blue, while evicted tokens are orange. Keys taken from layer 27 and head Llama3.2-3B-Insttree and generated using the NarrativeQA dataset. (d)
PCA visualization of the retained keys for each KV cache eviction method
14

---

(a) Sink Attention
(b) TOVA
(c) KEYDIFF
(d) Retained keys only
Figure 9: Keys taken from layer 20 and head of Llama3.2 2-33-Insttucc
(a) Sink Attention
(b) TOVA
KEYDIFF
(d) Retained keys only
Figure 10: Keys taken from layer 8 and head of Llama3.2 3.2--BBInnstruct
Quarry Hoar1)
Key oet (Layer Hrodd))
Query (layeri2 Pealt)
(Layerss
Qure
Qpny be on
say
oty
(a) Layer O Head I
(b) Layer 10 Head
(c) Layer 20 Head
(d) Layer 25 Head
Figure 11: PCA plots of Query and Keys from LJama-3.2-3B-Instie
C.2 Derivation of KEYDIFF from an Optimization Perspective
To leverage the observation in Section 3.1, we minimize the sum of pairwise cosine similarities of each key retained in the cache. This can be formulated constrained optimization problem with the keys K E Faxd whose element is k; and budget N smaller than n:
k kg
minimize S
ΣΣ JES
||4
(A.2)
subject to
SC .1,....,), S = N
This is a combinatorial optimization problem, which is difficult to solve efficiently, particularly during inference. However, relax Equation (A.2) to produce more tractable approximation to the original problem. First, we rewrite Equation (A.2) by normalizing keys k; such that i; ||A. resulting in:
ΣΣ iES JES
k
ky
Rs
E Np(Ks))
jES
where u(Ks) N Σ ky is the empirical mean of normalized keys in S. This objective requires
JES
recomputing pa Ks) for each candidate subset S. The sub-sampled mean tends to converge to the mean over the entire set, the problem can be further relaxed by replacing μ(Ks) with μ(()
15

---

after Ei= hy Dropping N from the objective (since it doesn' 't affect the solution) yields:
minimize
Σ h;
S
iES
(A.3)
subject to
$ (1 n.) n), -
The optimal solution Equation (A.3) can be found by sorting tokens using their cosine similarity with p K) and selecting the smallest N, leading to the algorithm described Equation (8).
Key Cache Diversity and KEYDIFF To empirically verify KEYDIFF's ability to retain diverse keys, we apply PCA the keys computed in an attention block of Llama evaluating a long context prompt. We visualize the distribution of retained and evicted keys by applying sink attention [35], TOVA [24], and KEYDIFF as eviction policies Figure 11. Visual observation reveals the tokens retained by sink attention and TOVA tend to tightly cluster together while DIFF's retained tokens are more evenly distributed. This observation generalizes across heads and layers, shown in Appendix C.I.
We also visualize the log determinant of the Gram matrix of the key cache (g(det(KK")) generated using different eviction policies in Figure 12. This quantity corresponds to the volume of space spanned by the keys in The distribution volumes for KEYDIFF attains higher values, indicating that the retained keys are more distinctive than TOVA and sink, corroborating the results of Figure 11. Details of how these plots were generated are discussed in Appendix F.1.
KeyDAdf
Deneity
Sask
JOVA
8.1
6.00
340
30.
966
973 200
506
1000
1016
log Volume
Distribution of log (det (KK")) from the Qasper dataset in LongBench. Larger values mean more of the key space spanned by the key cache. KEFFIFF retains keys that span a greater volume of the ambient space than TOVA or sink attention.
Figure 12:
C.3 Attention Sinks and Approximate Collinearity
Key Cosine Simllritty with Mean
Query Cosine nesine Similantt with Meen
0.75
050
0.50
025
10
0.25
14
0.0
1.4
0.25
1.0
-359
20
-050
24
24
-0.5
31
12
30
21
23
Heed
(a) Keys
(b) Queries
Figure 13: Cosine similarity between keys and their mean (left) and queries and their mean (right)
across heads and layers
To better understand why there exists a negative correlation between cosine similarity between keys and attention scores, we look to recent research that seeks to the importance attention sinks in decoder-based LLMs. The authors in [5] show that attention sinks emerge from training decoder- based I.I.ss since they can denoise the model and prevent rank collapse by limiting over mixing in attention heads. Moreover, attention patterns in decoder based models demonstrate that most
16

---

Cosine Similarity between Key and Query Means
0
2
6
8
0.3
12
-0.4
14
-0.5
18
20
-066
22
-0.7
26
3
7
9
11
13
15
17
19
21
23
Head
Figure 14: Cosine similarity of mean key and mean query for each head and layer.
attention logits are quite small (and almost always negative) for most keys and queries. This allows the attention sink have high attention activation, preventing over mixing in addition allowing the heads to specialize and selectively identify important tokens.
At the same time, the results in [11] suggest that hidden states, keys and queries all approximately collinear in the sense that CosSim Z,, xy) > O. In geometric terms, this means that most key tokens and query tokens lie in the same direction in Euclidean space. Our demonstrate that this is the case for both keys and queries. Our experiments show that most keys and queries lie within small angular distance from the mean key and query. More than this, see that across all heads, the mean key and mean query have negative cosine similarity Figure 14. Moreover, seen in Figure 15, we find that the norms of keys and queries are tightly clustered around a relatively fixed value. This means that variations in the norm of key and query tokens have less impact on the magnitude of attention scores than their direction. These three observations indicate that most keys and queries combine to create uniformly small attention logits, and that larger attention weights are constructed by projecting keys closer the direction of the mean query. This appears to be the fundamental mechanism through which over mixing is prevented: if most attention activations are very small, each head can increase the activations of a small number of keys across most queries selectively projecting them to be more aligned with the distribution of queries. This hypothesis is further supported by fact that sink tokens themselves often have small norm, which results in an approximate no-op in the attention head as in [5], however in this case, the only way for a key corresponding to sink token to have high attention scores it is as parallel as possible to the set of query tokens.
in Figure 13 results,
Norms
2
35
10
8
25
12
16
18
15
15
22
76
Figure 15: Distribution of I norms for keys and queries across heads and layers.
17

---

Cosine Similarity between Top Scoring Key and Query Mean
0.7
0.6
Layer
14
16
0.4
0.3
22
0.2
24
26
3
5
9
11
13
15
17
19
21
23
Head
Figure 16: Cosine similarity between highest KEYDIFF scoring key token with mean query.
To verify the above hypothesis, we show Figure 16 that keys which have maximum angular difference from the mean key are aligned with the mean query, resulting very large attention weights. This demonstrates how LLMs exploit the geometry of the hidden states and projections to limit over mixing, selectively identify important tokens.
To summarize, we have for all attention heads decoder based transformer models:
The majority of keys and queries are approximately collinear with their mean.
Mean keys and mean queries have negative cosine similarity across all heads.
Most keys and queries have a similar L2 norm.
Decoder based attention heads can selectively increase attention weights for a fixed key by aligning it with the mean query.
Key token importance can hence be measured by the angular distance between key and the mean key.
can show mathematically with some reasonable assumptions based on above observations that key tokens with persistently high attention scores must be geometrically aligned with queries.
Theorem C.1. Suppose that for fixed query token q, there is set of key tokens {k. such that | M, V i. Without loss of generality suppose ||gll = 1, the scaling parameter 1 and assume k* key not in {ki 1=1 with [k
1/ < M that has atlention weight 0:
exp(k* Tg) 1 exp(k*T 4) Σ exp(k{
Then
log( n n+1
- (1 - w)
S CosSim(k., .9)
2M
18

---

Proof. To show this we have that
exp(k* 9)
exp(k 9) Σ (xpp ()
exp(k=Tog ②)
Σ exp(ki R 4) exp(A* 9)
exp(k: 9) = w) w) eepp(=" 2)
Note that M Rg I M and hence
(-p(-M) S (1 - w) exp(k T 4)
W
1=1
un enpe - (1 w) exp(k 9)
exp( (MM exp(k* 9)
w
M - log(1 - w) v MCosSim( ,k", ,9) log( (w))
log(wn)
M log(1 w)
CosSim(k",,
M
exp(k" 1
log(
n2) - - -log(1 w)
exp(k- T ()+ E exp(k:T P
CosSim
M
expik" T g) log(
(x++ jexp( M) n2) M - llog(1 w)
CosSim (k",
M
MCCosSimk*,, .q) + log( n
2M - -log(1 - w)
n+1
CosSim (k", .9)
M
log( n+1
2M
log(1 w)
< 2CosSim(k",, g)
M
log( n
-llog11 (1 - w)
n+1
1 CosSim(k",0
2M
Taking the limit as n produces Lemma 3.1
The above proof demonstrates that as long as the norms of the keys are bounded, order for an attention head to be able to freely allocate w attention weight given key k*, the cosine similarity between and q must be high, therefore K* and q must be approximately collinear.
Using this result, we can also show that as long as the cosine similarity between k and is high, while the cosine similarity between and q low, CosSim(k* k) small. Note that, since empirical results demonstrate that most keys have high cosine similarity with their mean k key with high importance, approximately collinear to q. will also have low cosine similarity k. Generally, this also suggests that key tokens with low cosine similarity to le have greater importance.
In order show this, need the following auxiliary result.
Lemma C.2. Suppose {21:...,aa) is an orthonormal busis of T and E R Define CosSim(z,, y). Then Σ a =
19

---

Proof. Note that 0;
|
v m4
T&lll
If expand in the basis (011,.,, Fn)
|
that
y
Σ
1/
|
|yl
0g
i=
2
71 But we have
But then, we know that since
1, then
Σ 0
Σ a;T; 1=1
Ttll
2
n
n2
aa azTzz)
(asan, 0,344)
1=1
proving the result.
Theorem C.3. Consider tokens k.,,, 9. ke as above where is the average of the keys tokens. Suppose
CosSim(k' k* .9) =Bg > 0 and CosSim(k, ag O. Then CosSim k, k*) I 1 + 0g 2 3.
Proof. Consider the cosine similarity of k and k*:
k- T K
CosSim(ks, || ||||
expand in an orthonormal basis which contains {q. ri, 1 such that
n-1 Σ
= ||a|||
agg +
ag7i
where a; CosSim(k,, rz). Additionally, define 3, CosSim(k* rx) and note that by the definition of an orthonormal basis and the cosine similarity operation, using the result from Lemma C.2 we
n-1
n-1
have that o + Σ a = and that 32
+
Σ B = 1. Now we have that
T
| +
Σ
|kllarr
k. To
||
|+=1|
||||||
||
111/|11
1-
=0
|
1=1
a-1
= 0g
Σ
04
< <ag9
Σ
|as11,3
1=1
20

---

Table 3: Spearman correlation (p) between negative key cosine similarity and attention scores for each transformer layer of Llama-3.2-3B I.nsuututttt
Layer
2
4
5
7
0.9332
0.9496
0,9517
0,9484
0.9587
Layer
9.
10
11
12
13
14
0,9578
0.9534
0.9570
0.9628
0,9554
0,9658
0.9578
Layer
15
16
17
18
19
20
21
0.9477
0.9538
0.9280
0.9373
0,9528
0,9340
0.9311
Layer
22
23
24
Mcan +: Std
0.9140
0.9060
0.8950
0.94 + 0.02
Applying Young's inequality obtain
n-1 0 B2
I Sa
0
(1 - 0 + 2 (1 (8)
2
1 32
=
1 + 4,
2
4
2
-
2 4
Note that on the domain a, E [-) B, E {0, the function 1 a, - - is bounded above by and decreasing to - as a + -1. Hence, the smaller CosSim K, q) = ag is, the smaller CosSim k*) must be.
C.4 Correlation Analysis
We report the Spearman rank correlation between key cosine similarity and attention scores for each layer of the Llama-3.2-3B- --n-tuuuttttt model. Correlations are averaged over randomly sampled LongBench-Musiquee prompts. From Table we observe a consistently high correlation (p 0.94 on average) across all layers, indicating that geometrically distinctive keys (i.e., those with low pairwise cosine similarity) are strongly aligned with tokens receiving higher attention scores. This empirical evidence supports our theoretical claim in Section 3.3 that key diversity serves as reliable proxy for token importance.
D TTFT Analysis
We have measured end-to-end inference latency (measured as time to first token (TTFT)) for Llama 3.2-3B via the standard Huggingface API when the model is using eager attention and Flash Attention as in Figure block sizes and KV cache budgets. KeyDiff outperforms TOVA and SnapKV with FlashAttention as well as with eager attention for large cache budgets. We can see inference latency with KeyDiff is independent of block size when using FlashAttention because of KeyDiff's linear complexity and its lack of required materialized attention weights.
and Figure 7. Tests are performed on NVIDIA A100 80GB GPUs. We test various
E Math-500 reasoning benchmark
In order to measure effectiveness of different caching methods on reasoning tasks, we tested several different model using various caching algorithms on the Math 500 reasoning benchmark. Specifically, we test KEYDIFF with sliding window whose window size 20% of the KV cache budget, and SnapKV on the DeepScck-PP PrepSeck-RI-Disiieee RI-Distill--Lamaa 8BB and DeepSeck- DDistill-Qwen----
21

---

(Transformers v4.49, NVIDIA A100, Euger Dileal16, 11K Prompt leng Prompt Processing)
Prompt Block Stee 64
Promy: Block Stze 128
Prontgt Block Siee 256
65-
Eestien
Keytan
30VA
10
Seapey
-- teeghY
Casphy
1.5
T177 00
-.0
KV
Figure 17: TTFT for eager attention with different cache eviction strategies using block size 64, 128, 256 for block prompt processing.
models. We randomly sample 5 responses with TopP- 0.95, Temperature 0.95 with the 4096, 6144, and 32,786 max generation lengths. The reported scores are the average of accuracies over the random samples.
Table summarizes the Math-500 evaluation results for Llama-8B, As shown in the table, token eviction methods generally perform well even with KV cache budgets that are strictly smaller than the maximum generation length. Surprisingly, we found that KEYDIFF slightly outperforms baseline methods in certain configurations (e.g.. KEYDIFF with 2K budget for 4K generation length, and KEYDIFF with a 4K budget for 8K generation length).
To further analyze the effectiveness of token eviction, we measure accuracy in cases where the context length of the baseline method (i.e., prompt length + generation length) exceeds the available KV cache budget. As shown in Table 5, for samples where eviction is actively triggered, KEYDIFF continues to outperform the token eviction baseline (SnapKV), and often achieves accuracy close to or slightly better than the non-evicting baseline.
We also conducted similar evaluation on SeepSeek-R1-Dsstll--e performance degradation for token eviction methods compared to full KV cache baselines (See Tables 6 and 7.) However, KEYDIFF still demonstrates comparable performance SnapK overall. This discrepancy may stem from architectural differences that Llama uses a lower GQA [2] ratio than Qwen, which results more information compression in the KV cache. We hypothesize that models with more compression like Qwen are more sensitive to eviction since each evicted token contains more information in Qwen than Llama by design.
and observed slight
F
Additional discussion for LongBench
F.1 Empirical Motivation for KEYDIFF Setup
To generate Figure 11, we used the first sample from the test split of the narrativeqa task in LongBench to prefill the KV cache of Mamma.22-3B-nn. maximum size 4096 while the sample was much longer, requiring KV eviction. We applied PCA to the key cache and repeated the process for sink attention, TOVA and KEYDIFF.
with a block size of B 128. The KV cache had
To construct Figure 12, we sample 100 prompts from the Qasper dataset LongBench [4], compute the log determinant of K KT of the keys in the KV caches of each head and layer of Illaa 3.2-3B- Instruct using cache budget of 2048 and block size of = 128, and plot the distribution in Figure 12. We show this key distribution for sink attention, TOVA and KEYDIFF.
F.2 Experiment Setup
In this subsection, we provide the experimental setup for KEYDIFF and the baselines for the Long- Bench experiments. The LongBench evaluation is conducted using the default parameters of the LongBench evaluator with predefined prompt templates. Tests are performed on NVIDIA 1 80GB GPUs.
22

---

Table 4: Math 500 results Deepsee--Rt-Llmma-BB distilled model (Higher is better). We highlight the methods showing the best performance within given budget with boldface.
Method
Max Gen. Length
Budget
Flex Match
Exact Match
Avg. Gen. Length
Full
4K
N/A
0.711
0.537
2769
1024
0.695
0.531
2753
KeyDiff'
4K
2048
0.720
0.546
2740
1024
0.689
0,529
2759
SnapKV
4K
2048
0.714
0,544
2757
Full
8K
N/A
0.840
0.628
3812
2048
0.819
0.617
3888
KeyDiff
8K
4096
0.844
0.634
3805
2048
0.805
0.610
3898
SnapKV
8K
4096
0.828
0.627
3898
Full
32K
N/A
0.898
0.668
6869
2048
0.883
0.662
7678
KeyDiff
32K
4096
0.894
0.668
7312
8192
0.894
0.667
7096
2048
0,849
0.641
7509
SnapKV
32K
4096
0.884
0.661
7218
8192
0.893
0.665
7005
For TOVA, H2O, and SnapKV. the set of attention weights computed from a single key cache due to grouped query attention [2] is aggregated by taking the average over the attention weights. Additionally, only for SnapKV, we apply average smoothing to the attention score with a kernel size of and keep the most recent 32 tokens in the cache, following the suggestion of the original paper. For Sink, we used the first four tokens as the attention sink, following the suggestion the original paper.
F33 Longbench dataset statisties
In this section, we provide the length statisties of the Longhench Benchmark and in-depth analysis of compression ratios for the given KV cache budgets, such as 2K, 4K, 6K, and 8K.
Prompt lengths We measure the number of tokens in the samples using LLama tokenizer [31]. As shown in Figure 18, LongBench exhibits variability in sample length from the datasets.
roxtt aroum
(0l153 en
0 2004
0.0000
0002
0.000
0500
Feer Shot
Symthelic
Code Completion
3.00000
partago cuut
0.000
0744
tria
0004
pas veteeal
possapt www.etlttttt.......oo...........
a.0000
spoberch
ase00
1005e z000 l030s canon socce 63033
Tahan Here s0o0s calon Viace Mele
19030 zrece creen $15te move
Langt
Figure 18: Histograms of sample lengths measured by number of tokens
Compression ratio The majority of other KV cache eviction studies assume an unconstrained memory footprint. Before they compress the cache by applying an eviction policy, they first set target compression ratio and evict the appropriate number of KV pairs to satisfy the compression ratio [43, 24, 20]. On the other hand, we fix the KV cache size and ensure the number cached tokens less than equal to the predefined cache size. Due to these differences,, it is less straightforward to
23

---

Table 5: Math 500 results DeepSeck-RI-LLama-BB distilled model (Higher is better). We highlight the methods showing the best performance within given budget with boldface.
Max Gen. Length
4K
Max Gen. Length 8K
Num Tokens
IK (497/500 samples)
Num Tokens 2K (353/500 samples)
Budget
Flex
Exact
Budget
Flex
Exact
Full
N/A
0.709
0.534
Full
N/A
0.783
0.584
DifD
1024
0.693
0.528
KeyDiff
2048
0.756
0.570
SnapKV
1024
0.687
0.526
SnapKV
2048
0.736
0.560
Num Tokens
2K
(240/500 samples)
Num Tokens > 4K
(195/500 samples)
Full
N/A
0.604
0.449
Full
N/A
0.650
0.455
DifDiff
2048
0.618
0.463
KeyDiff
4096
0.662
0.470
SnapKV
2048
0.610
0.458
SnapKV
4096
0.637
0.453
Max Gen. Length 32K
Num Tokens > 2K (353/500 samples)
Budget
Flex
Exact
Full
N/A
0.783
0.584
KeyDiff
2048
0.756
0.570
SnapKV
2048
0.736
0.560
Num Tokens > 4K
(195/500 samples)
Full
N/A
0.650
0.455
KeyDiff
4096
0.662
0.470
SnapKV
4096
0.637
0.453
Num Tokens > 8K
(162/500 samples)
Full
N/A
0.793
0.550
KeyDiff
8192
0.786
0.545
SnapKV
8192
0.782
0.541
set appropriate KV cache budgets to satisfy the target compression ratios. Instead, we provide the average compression ratio, which defined as:
N Σ
Average Compression Ratio
L.
where N is the KV cache budget, and L; is the length of the i-th prompt (sample). We replace the summand with 1 whenever N 2 T.,, as compression doesn't occur in that setting.
As summarized in Table 9, 2K cache budgets have 0.31 average compression ratio, which indicates 69% of input prompts are compressed. Our largest cache budget, 8K, exhibits 0.77 average compression ratio.
F,4 Additional Results
G Ablation study
Selecting the Anchor Vector We have mainly evaluated KEYDIFF using the method described in Equation (7). Scores to determine eviction are measured via cosine similarity with an anchor vector
which can be computed in several ways. We run LongBench Llama3.2 3.B-BB- Instruct with eviction
Insssuuuttt
24

---

Table 6: Math 500 results DeepSeek-RRI-Qwen-T5 distilled model (Higher is better). We highlight the methods showing the best performance within given budget with boldface.
Method
Max Gen. Length
Budget
Flex Match
Exact Match
Avg. Gen. Length
Full
4K
N/A
0.764
0.579
2630
1024
0.666
0.512
2692
KeyDiff'
4K
2048
0.749
0.570
2629
1024
0.692
0,533
2655
SnapKV
4K
2048
0.749
0,566
2637
Full
N/A
0.877
0.658
3287
2048
0.811
0.613
3348
KeyDiff
8K
4096
0.867
0.647
3208
2048
0.812
0.612
3328
SnapKV
8K
4096
0.868
0.647
3214
Full
32K
N/A
0.923
0.682
4051
2048
0.811
0.613
4322
KeyDiff
32K
4096
0.897
0.647
3800
8192
0.891
0.663
3741
2048
0.812
0.612
4279
SnapKV
32K
4096
0.868
0,647
3828
8192
0.891
0.662
3808
00-
22.0
28
Accomny
1000
1860
1222
1007
2014
Home
Figure 19: Needle in Haystack results for Sink Attention [35]
policies using the following anchor choices: pairwise cosine similarity from Equation (7), denoted Pairwise; KEYDIFF, using the mean of all normalized keys as an anchor, and using the median of keys an anchor, denoted Median. Table 15 summarizes the average LongBench accuracy for the different methods to Llama I.ntsttInstruuc. KEYDIFF shows similar average scores to Pairwise. Additionally, KEYDIFF and Median show similar scores, demonstrating that KEYDIFF is robust to the selection of the anchor design.
Selecting the Similarity Metric We use cosine similarity as the scoring metric for eviction in KEYDIFF based on our discussion Section 2.2. This could be replaced with other metrics like the dot product Fuclidean distance. We evaluate KEYDIFF variants using dot product and Fuclidean distance as the similarity metric, denoted DotProd and Euclidean respectively, and report the results in Table 16. KEYDIFF and DotProd show similar performance for 6K and 8K budgets. However, KEYDIFF outperforms DotProd for smaller cache sizes. This implies that considering both the direction and the magnitude of the keys to compute similarity are important for identifying the tokens to evict. On the other hand, Euclidean shows a significant performance drop relative to KEY DIFF.
G.1 Needle in a Haystack results for Sink attention
25

---

Table 7: Math 500 results DeepSeek-RR--ween-BB distilled model (Higher is better). We highlight the methods showing the best performance within given budget with boldface.
Max Gen. Length 4K
Max Gen. Length 8K
Num Tokens IK (497/500 samples)
Num Tokens 2K (317/500 samples)
Budget
Flex
Exact
Budget
Flex
Exact
Full
N/A
0.762
0.578
Full
N/A
0.816
0.603
DifD
1024
0.664
0.511
KeyDiff
2048
0.713
0.533
SnapKV
1024
0.690
0.532
SnapKV
2048
0.718
0.533
Num Tokens
2K
(328/500 samples)
Num Tokens > 4K
(179/500 samples)
Full
N/A
0.650
0.478
Full
N/A
0.626
0.441
KifDiff
2048
0.628
0.464
KeyDiff
4096
0.611
0.419
SnapKV
2048
0.629
0.459
SnapKV
4096
0.615
0.422
Max Gen. Length 32K
Num Tokens > 2K (360/500 samples)
Budget
Flex
Exact
Full
N/A
0.889
0.642
KeyDiff
2048
0.713
0.533
SnapKV
2048
0.718
0.533
Num Tokens (141/500 samples)
4K
Full
N/A
0.787
0.524
KeyDiff
4096
0.611
0.419
SnapKV
4096
0.615
0.422
Num Tokens > 8K
(53/500 samples)
Full
N/A
0.550
0.275
KeyDiff
8192
0.392
0.222
SnapKV
8192
0.381
0.215
2K
2K <
L 4K
4K
< L
<
6K
6K
L
8K
8K
Total
NarrativeQA
8
192
200
Qasper
1
77
83
25
14
200
MultifidelitQA-
9
31
21
32
57
150
MultifidelityAA QA-Zh
14
33
37
200
HotPoiQQ
12
12
171
200
2wikimqu
54
53
200
masique
0
3
197
200
dureader
16
184
200
gov report
200
qmsum
0
17
15
167
200
multi news
99
200
vesum
4
20
18
32
126
200
frec
43
39
73
200
triviagu
21
139
200
samsum
6
29
34
17
114
200
Isht
8
189
200
passage count
0
13
184
200
pussago-retrievl--Er
0
0
200
200
passag--cctieval-ZN
160
10
170
loc
80
86
21
4
9
200
repobench-p
113
200
Table 8: Distribution of sample length measured by Llama2 tokenizer
26

---

2K
4K
6K
8K
NarrativeQA
0.10
0.20
0.30
0.40
Qasper
0.47
0.82
0.96
0.98
MultifidelityAA-Ii
0.40
0.66
0.82
0.93
Mult
0.49
0.78
0.91
0.98
HotPorQA
0.19
0.37
0.52
0.66
2wikimqa
0.36
0.65
0.85
0.92
musique
0.13
0.27
0.40
0.53
dureader
0.17
0.34
0.52
0.68
gov report
0.28
0.52
0.70
0.81
qmsum
0.18
0.36
0.52
0.66
multi news
0.81
0.96
0.98
0.53
vesum
0.27
0.49
0.65
0.68
trec
0.38
0.66
0.84
0.94
triviaqa
0.26
0.46
0.60
0.72
samsum
0.32
0.55
0.71
0.82
Isht
0.13
0.27
0.39
0.52
passage count
0.15
0.31
0.46
0.60
passage-retrieval En
0.16
0.33
0.49
0.66
passage-retrieval-Z] Zh
0.37
0.74
0.99
1.00
lec
0.78
0.95
0.98
0.99
repobench-p
0.27
0.52
0.67
0.78
average
0.31
0.53
0.67
0.77
Table 9: Compression ratio of prompts w.r.t. various KV cache budgets
H Additional Experiments and Analyses
To further substantiate the empirical findings presented in Sections and 4, we provide extended set of experiments and complementary analyses. These additional studies examine the correlation between key geometry and attention, evaluate retrieval-critical and reasoning scenarios, and measure the efficiency of KEYDIFF under constrained hardware settings. Together, they offer broader view of the method's robustness, efficiency, and general applicability across diverse inference conditions.
H.1 Retrieval-Critical Evaluation: Phonebook Lookup
We evaluate KEYDIFF on a retrieval-critical setting using the Phonebook Lookup task, where model retrieves phone number corresponding a queried name from long list of entries. Accuracy averaged across five random phonebooks of varying lengths. As shown in Table 17, KEYDIFF maintains high retrieval accuracy for shorter contexts and degrades more gracefully than attention- based baselines as context length increases.
H.2 RULER Benchmark Validation
To assess the generalizability of KIFDIFF across diverse architectures, we reference the results reported by the community-maintaneed KVPress RULER benchmark. KEYDIFF consistently achieves competitive or superior leaderboard scores compared to methods such as TOVA, SnapKV, QFilter, and Knorm on both Llama-3.2-3B and Qwen-3-8B backbones, demonstrating its robustness and transferability.
H.3 Needle-in-a-Haasttee Recall Saturation
We further analyze the recall behavior of KEYDIFF under varying context lengths in the Needle-in-d Haystack benchmark. Table 18 reports the recall difference between KEYDIFF and full-cache baseline as function of depth and context length. As shown in Table 18, KEYDIFF achieves near- parity recall with the full-cache baseline up 30k tokens, confirming its stability under long-context compression.
27

---

H.4 On-Device Latency Evaluation
We further evaluate the runtime characteristics DEYDIFF on a mobile-class device by measuring the latency required to compute key-eviction scores an Android platform. All methods are tested on recent Samsung smartphone under identical FP16 inference precision, and the results are normalized by the latency of KEYDIFF with cache budget of 512 VVs.
As shown in Table 19, KEYDIFF performs par with competing methods for small cache sizes and achieves substantially lower scoring latency as the cache size increases, demonstrating both scalability and minimal overhead edge hardware. Minor runtime fluctuations can be attributed to kernel-level optimizations and proprietary hardware characteristics.
28

---

Table 10: Resource unrestricted LongBench Results (Higher is better). All methods processes the input prompt in parallel (i.e., block size = oo) and make an eviction decision with all token information in the input. The token eviction is made every step of generation if the budget exceeds. We highlight the methods showing the best performance within a given budget with boldface. We omit A from evaluation due higher chance of OOM errors.
Avg.
50.72
26.33
4066
46.67
48.30
49.25
09.32
49.96
3508
38.09
39-1
40.57
48.5
8917
47.8
49007
69.2
49.1
17.12
2424
32.56
37.29
41,20
42.40
42.33
42.70
3008
38.00
40.57
4045
42,46
42.56
43,07
RD-P
51.34
16.44
45.17
51.31
52.19
53.33
54.50
59M1
5981
54.07
55.35
51.92
52.05
54.00
45.65
50:49
53.30
53.60
56.5
17.58
29
39,8
65.83
55.68
56.22
57.58
56.85
53M1
53.61
5400
55.35
48.23
55.55
36.28
36,80
Code
Lce
61.6
42.58
55.96
00.25
69.82
61.5
0199
62.
61.96
57.9
57
57.13
60.56
0213
61.66
59.26
0055
01.2
61.9
4016
$1.49
54.28
55.35
56
36.30
56.77
57.8
57.4
57.15
55.21
55.79
5585
56.20
FR-sh
99.00
31.05
07.50
99.00
96 16.58
09.00
09.00
1800
22.0
2100
20.50
8700
98.50
9900
98.00
9592
07.67
95.00
99.00
0.50
725
1900
2000
18550
1850
2000
2000
1800
22
2250
20.50
17.50
2100
2050
2000
Syntheic
PR-
99
99.50
100.00
100.30
100.00
100.00
100.00
36.00
48.00
53
1700
70,00
98.55
98
100.00
100.00
100.00
100.00
100.00
100.00
1.52
13.71
63.00
81.91
95
85.50
94.97
95
36,00
49.00
57.00
70.00
80.00
95855
92.42
96.45
POum
M.33
16
16
13.73
9:4
13.06
14.22
13.50
250
2.50
3.00
5.556
1092
11.38
13.20
11.80
481
4.95
4.76
4.01
5.88
4.5
5.7
2.50
2.50
4.00
495
5.21
5.00
LSTT
45,50
12.20
16:07
13.53
28 89
20.79
30.43
21.25
24.25
26 26
27.75
26.53
28.5 57
33.36
31.82
31.82
33.33
27.27
16.00
13.70
12.86
15.07
24.00
24.32
21.25 25
24755
22.75
20.55
18
22.22
25.55
Fowsbot Learing
SAMSum
43.57
10.39
40.05
45.29
44.39
44.82
41.32
41.94
42.27
39.74
45.00
43.51
43.87
44.02
12:23
21.7
20:45
35.08
42.97
42.23
47.59
40:99
41.32
41.34
42.27
42.28
42.55
43.18
42.52
TAviiQA
91.61
5.88
65 83
7W-42
86.91
91.53
91 44
91 16
50000
00
90 77
90.77
89.68
90.46
92.27
50.13
90.34
41.36
11
72.81
53.55
89.47
89.73
89.07
89 40
90.00
50.55 52
90.77
98.77
88.31
98
90. 59
59.08
90
TREC
23,00
46 19
67.7 71
71.00 11000
72.08
72.65 25
67.50
21.50
22
72
20.8
22
71.96
22.00
7300
23.55
72.59
43.00
01
41.50
70
50
70 50
71.50
2250
72.50
67.50
71.50
22.50
20.50
71.50
72.50
22
50
VC5mm
17:28
4.44
12.39
1646
17.40
17.34
16.30
16.0
1634
17.37
17.45
18
17
1751
17
16
1635
1744
17.5
3.05
5.77
7.24
10.55
15
1587
1615
16.00
16
17337
17.45
14.47
15:00
16.32
16000
MohiNews
Summartzam t22000
27.02
17.42
26.55
27.18
26 81
27. 18
27.23
24.00
25 12
25
25.5 26
27.34
27.24
26.95
27.12
21.29
27.20
25.21
16.14
23.10
24.44
24.7
24
25.8
25 30
24. 98
25.02
25.2
25.0 10
38
25 34
25.31
50m
25.52
4.73
7.54
17.39
24.37
25.56
25.21
21.41
21.89
22 38
22.61
25
25.71
25
25.2
26.02
25.87
24.90
411
9:26
13
17.06
27
23.88
24
21
21
22.30
22
23.91
24.15
24
24.27
Gov Repoon
34,96
3.70
25.80
30.54
13.33
34.35
26.08
29:28
30.54
31.35
32.09
34,99
35.28
28.97
55.17
34.42
34.81
33.09
1.43
6.99
13.52
23.65
28.71
31.09
32.91
33.34
26.06
29.25
31.35
29.13
31.63
52.80
33.31
DiRRouler
35.04
5.55
15:63
26.55
20:99
26.54
17:00
17.71
2035
52.35
34,83
53
36.31
2604
35.01
10:40
12:25
15.57
20.79
27.80
31.66
36.28
36.74
18
17.50
20.35
35.47
35.93
36.00
37.08
Maskgge
32.25
0.00
10.00
13.58
1667
15:28
15222
2251
22.32
23.75
25.00
15.28
14
13.58
12:99
26.04
9.88
17884
11.61
M.74
14:81
1944
15
2007
22.51
25.25
20
18.78
15.26
17.70
Mulii Doce US4
ZWAMMO4
47.8 FM
29.49
48.81
48.26
49 06
50.26
58.46
00.57
42.57
42 5M
50.17
69
51.51
47.56
49.97
50.00
50.51
23.51
27 46
36
39
42
43.12
03
36.66
40 07
42.38
42.04
41 88
41.71
42.07
MF-24 ah Hopurrq
57.33
43.50 56
52.07
$3.09
59 16
00:72
55.00
45-77
69.07
50.05
49.15 13
51.54
89.08
57.18
57.40
59.04
59:70
57.48
26
35.29
42.34
46.1 13
24.25
52.67
52.91
45.57
45.07
490
48.23
51.58
51.28
53.52
99.6 06
25. 95
39
47.08
55.7 72
55.00 07
50.80 82
59.31 31
50
34.75
46.58
$3
54
56.15
58.5
98.2 79
53665
57.52
59.19
59
53.80
18.08
35.46
46.08
$2.90
54.09
38
96
34.75
46.58
54.77
51.15
55
55
56.16
Stngle Doc. QA
MF--en
56.12 12
32.73
47:74
51.12
55447
56.21
51.26
3374
11.15
4374
44.38
52.53
55333
5388
5467
54.99
24.23
33
44.38
41.33
52
49.70
33.74
41.35
48.74
44.58
49.58
51.38
21544
5033
Qhaper
47.00
22.75
00.40
45
45:33
44.37
46-45
65
38:57
4941
40.53
4500
46.72
4:55
4600
4581
46.55
20.1
32.58
38.61
00.33
2X 38,22
00.57
80
35.33
38.57
40.41
40.53
38.55
40.55
40.54
40
Llamal.1 MB
2K
SK
2K
4x
6k
4K
6%
8K
2K
4X
6K
SK
2K
4X
6K
2K
4K
6K
SK
6K
8K
2K
4K
6K
8K
4X
6K
SK
120
TOWA
Siak
SnapXV
KEYDUFF
1120
TOWA
Siak
KEYDIF
29

---

Table 11: Full 10imm-3.---B/33---B-Iini-- LongBench Results with B 128 (Higher is better). We highlight the methods showing the best performance within a given budget with boldface.
:: A subset of camples Were svaluatee due to OOM errors (783/200 samples are dealuatedd (alled)
AVg.
49774
15.25
2438
13.55
38.00
4112
48.1
4523
3375
1976
43.9
44.9
18:55
46.5
48.05
17
4014
45.17
476)
45.0
48.14
49.15
49.55
40.71
13.00
2035
26:33
31.5
20
34.5
3771
199)
2034
338
36-22
38.25
3085
1074
10
41
22.23
20.13
36
35.09
J0.3%
41.85
42.40
600
$1.04
12.08
21.48
29.53
36.26
5340
52.20
51.90
59.54
53.54
56.24
5648
51.55
52.16
51411
3565.
15.28
43.14
45.28
3942
45.00
49:00
50:90
56.52
13.1
22:8
53.20
19,00
52.6
56.6
57.58
5747
5223
52.1
54.1
5663
55.11
50.8
5782
57.29
36.32
40.0
4708
50.73
42,01
59.44
54.30
55,05
Cole
Lee
61.66
40.5
5488
58.00
59,70
61/2
6150
6.00
0425
6212
0222
6218
6239
0121
61.8
6148
52:00
59,2
6008
62.06
59.1
6000
61
61.48
56.22
3971
51.23
565
55.00
5551
5572
855
3377
366
5648
56.5
5600
56.2
55.0
55.00
3577
45.0
55
5682
5618
5555
55,00
55.85
PR.
99.00
4.00
31.55
98.57
32.00
1460
98662
98.57
3250
7130
08:00
520
0.7
996
9868
20.5
00050
9800
09000
06.5
07.50
98.67
21,50
0.0
6.25
19:00
21.50
6:50
13.0
31.00
2150
16.00
19.50
30
9:00
22.30
20130
21.00
5.0
11.00
18.50
20.50
1240
19.50
21.50
3150
Senteeti
Pk
99.50
5.68
28.50
02:50
1800
45.50
62700
8700
2550
38500
5250
16.00
23300
10500
9800
100
1755
5000
1500
8200
96000
9000
99.50
96.00
0.50
7.50
1300
2650
11:50
2350
40.30
7100
35500
4700
62.50
32500
62:30
85000
9400
750
40.00
60.50
8850
9500
56500
PCouu
6.58
2:25
4.00
5.2
0.00
3.00
435
6.5
240
360
300
355
400
535
500
340
450
555
725
31
5,0
3.00
0.50
1.50
0.0
2.00
2550
3.0
400
2.5
120
290
350
3:30
3.50
250
4000
5.00
240
250
1.50
140
230
140
350
LSHT
45.50
14.50
19-50
19:50
18.55
23.55
2900
33.25
22.25
2925
55.75
21.25
250
27
55.55
20
27000
32.50
39.00
42.25
46:00
54.00
11.35
15.50
1525
17.00
16.25
18.5
21
19:50
21-55
23550
38.25
1625
1825
15.5
2200
12.50
1900
21.50
23
50
38.5
3075
Fewsbot Lerring
43.37
7.42
17.41
33
4254
43.27
43.00
43.2
42.31
42.30
45
435
43.54
28.55
37.50
40.51
4.33
20.36
43.84
4200
9.3
20.53
27.32
32
40.45
41.50
42.50
4133
4201
42.5
40.5
4005
41
4.99
23
5516
39
2000
41
4200
42
lnve@q
91
20.5 36
47665
90.71
91.36
91891
9111
89-46
91:33
91.23
91.29
02.38
91.78
59.94
79-41
86.89
89.26
8502
92.28
21,97
53.23
64.30
87.81
88
8000
8808
88
89.36
58 13
89
8905
911
5099
2866
84.90
85.24
87.00
5000
TRDC
73:00
46.00
55.00
59:50
50
61 30
08.50
03
00
70
72000
72
50
50
71 50
7250
65 00
99
7010
71 1:50
00:50
70
22:50
72.50
41000
55.00
61 50
7000
56.50
63 50550
66 00:50
00
01
71.50
73000
59
65.50
60 00
7000
48.00
63.00
00
70.00
0000
06.50
1100
7200
VCStmm
17:26
3.07
6J13
9396
16.3
16.75
1691
17.53
15.54
16.25
17:05
76.9
16.15
16
37.57
11003
13.44
15.12
15.8
14.11
17.13
16.41
311
4281
6.66
9.12
15:47
16.00
16.37
16
16.50
35.97
16.24
1631
10.24
701
14.25
15.50
1526
15.88
15
MalliNoo
Summuniation
27.00
16.78
26005
25
25.96
27:00
27:00
26.02
26.78
26.87
26
26.77
2708
27
26.09
26.95
26.34
2658
26.76
27.01
25.21
15.97
22.77
24:25
24.57
25.04
2156
35:11
25
2506
25.1
35:30
21.97
25.01
25.00
25.17
34.30
2506
15
25.01
25.06
25.19
25.17
QM8mm
25.33
2.70
5.55
11:35
11
22133
24
24.76
31
21577
22
23
21005
22
23.53
3605
14996
22.27
2465
2089
2338
2500
25112
24.30
1.55
6.30
10
13.28
10:23
21.36
2217
22:85
30
21.35
22
10.03
21:11
22.73
25.46
12.45
21-47
22
21-45
33
23333
2500
34.95
06
2.07
18:75
38-87
30.95
52.35
33:64
26.55
31.08
2248
53 10
29.00
22.99
33-43
33.65
64
29.30
52.65
33.8
2002
52.30
33.44
34 17
33.09
0.7%
5:44
10.51
17.30
26.15 15
24 36
30.50
31.64
30.03
31.64
27.03
20.29
31.27
31.05
15.36
2899
16
28.05
31
22.99
32.75
Dutooseer
35.64
5.90
16.08
22.50
27.08
5115
16.18
16.34
17:55
19.54
2214
27-46
32.06
17.33
21
52.
5409
32.57
34.54
36.34
6.07
10
13 96
16:35
9.2
17.26
24.28
31.00
9.86
11.10
14.76
9.65
16.88
25.32
310-00
1417
22.02
31.29
33
20
32.45
3664
34.30
Masiiqu
0.25
8.73
2366
14.7
20.56
2507
26.00
12.99
19.00
21.00
16.53
24.7
27.82
5.99
18:44
25.63
30
22.04
31.52
30.88
20.04
2.88
7:55
15
21 16
13008
18:22
20.45
23.05
15.91
16
11.54
16.64
26 38
24.9
744
12:11
12400
22.22
13.9
21
2600
20,09
Molss Doc. Q4
2WIaMQQ
21.55
16
44.54
47.8
40.00
25.50
41.30
65.73
12
46.5
4844
48.75
32.25
05.55
47.00
47.75
46.47
00
40.29
19 56
28.0%
55 53
40.41
30.05
38
47
0.
56
10
24
30,05
37.98
40.15
41 65
25 76
40.7
35.41
48 30
22
45.55
330 db Bugpotq
0.33
26.11
40
48.26
5500
51.5
3864
4404
473
53.12
50000
33.25
5022
5255
S0.4
51.59
515
96.87
30.69
18.02
24-49
65
58,09
6112
4:97
06.13
45
57.27
46:20
49
40.5
29.47
39.89
43.15
29
66.00
8014
51.24
403
20
3165
46.34
56.14
1696
5116
55-45
57.55
3232
4616
55.77
29
55.7
57665
5720
47.52
5357
56.77
51.88
9655
29.16
50.04
5.2
39:25
17
60
31
6530
5208
5517
4168
89
59:57
29
45:55
51
55.24
3064
4585
24
4747
5956
55
5002
56
25.33
36.00
4788
5359
5453
20224
50
4720
53.30
41.70
5153
5506
5502
50.90
55448
20.00
33:23
59
43.30
52.44
42447
45
36222
37.95
11596
31.48
39
44.00
48
51.5
27
47.0
4544
45155
50L1
50
Single Doc. QA
Qusper
47:00
21.15
17.36
4635
4508
46.28
24277
4501
47.00
30222
4537
46.55
3663
4308
45633
45:70
41.75
40335
46:77
40:23
19.06
31.94
3681
9966
30.14
3653
4067
3861
00229
40002
31.57
9022
3965
4000
30.39
4855
40.54
36.65
40/00
0068
Narmiive QA
05
1.74
+117
12.57
22.08
24.99
26.96
21.83
23.3
25
24.79
14
25
8.6
15:38
21:25
25
26.64
35.52
25.
1,3
290
996
17.14
20032
20122
21.08
10
19:33
2011
17.38
30255
20.3
29
747
12.00
1300
15722
10:20
22.34
22
22.41
2X
4K
6K
80%
7X
<K
0%
8K
26
2X
-6
2
3K
68
8K
2X
4K
6%
88
2K
-8
6K
8K
2
OK
46
0%
8%
2K
AK
6K
80
2X
4K
6K
8K
Linus .08
Key (
19 19]
H20
TUVA
Sink
StapRV
Liannd
H20
TOVA
Sink
SippKV
KEYDIF
30

---

Table 12: Full Qwen-2.5-7B/3B--nnttee LongBench Results with B 128 (Higher is better).
We highlight the best and second best methods within a given budget with bold and underline.
Ang
36.4
11
22-35
25.15
2007
30A8
9:54
31.79
2343
26
3:76
31.5
32.35
38.6
2375
M90
11-35
21.55
2659
2008
37.3
2003
3011
201
3665
28.00
2935
2015
M600
31.55
3056
22:4
R0-P
61.04
18:2
41.5
5615
56.59
0057
51.30
5500
5642
0036
0.50
3305
4222
5240
47.55
34.44
900
4840
1678
4230
1766
0032
3049
4038
47.00
4782
2435
3924
Code
5TM
15.00
3560
5599
5669
1768
57.5
2011
5523
5580
5632
57.6
5313
57.48
5191
22.66
49.55
N061
51.00
3132
48.7
3176
6532
39
5625
513
46
4030
66799
1.50
54.51
55.66
3645
43:33
5516
2130
6405
7121
71.71
5915
5519
3437
34
5811
306
1228
455
8055
2014
20
51
2132
1046
2045
Syntheik
05
0000
0.41
15.73
0.9
15.00
21.24
20.5
7.50
18.00
46.22
33
18
240
9.00
11
600
95
3.75
1355
14
24.00
15
35
13
2008
403
4.22
0A6
245
187
270
1000
2.24
3.0
414
241
531
4.58
355
5,00
0:25
111
250
3300
400
1.00
5:0
5.20
355
00-02
16:40
15.75
31-41
22.23
27
01
29
55.25
23
34.36
30,00
15
16
5625
17.25
2125
22
29.30
900
34,50
28
25,00
25.55
20
24.00
Jowbbr Leariigg
TeiiQQA SAM5im
41.75
10A0
20.57
41.55
42.71
42:90
44.10
41.47
44.15
41.13
15.00
43,00
32.22
10:25
45.96
3458
30
41:90
4300
62.5
43.11
42.77
43.32
45.55
44.40
27.43
52/24
00.05
28:11
29-16
82.67
8142
75.36
00.30
81.00
83555
01-78
0550
$3.00
20290
85.05
21.87
56.10
08-00
8026
56.77
0851
26.00
2637
04
41
6302
65.50
59.00
56.00
58.50
01
62.00
04.30
04.50
65:00
6000
61200
$2.00
36100
67.50
58.00
00
51.00
3800
60.50
50.0
63.00
05.50
65
65.50
$7.50
65000
07.50
15-26
3.44
15.25
15.81
14.35
15:48
15-45
1500
15:35
11.73
11:11
M4-55
932
16.55
15
1300
83
12
59566
83.75
00-53
1130
27.57
15:00
22.61
22.63
22.73
22:41
25
22.79
24.66
22.91
02
22
22.71
22:20
22.76
24.99
16:00
24-88
2598
24344
26
24
2692
24
24.59
36.1
24.00
24.11
24-00
24.55
Summar
19:91
6.41
14
17.02
17 64
10.05
17.00
18.02
14:72
19.49
10
26
36.09
18-00
20-42
23.94
690
19
16.40
1:40
22:27
23:00
19
45
30
38
21.14
25
25
24
23.57
16 56
22:08
23.0
34:35
1.52
20:70
27.41 47
29:21
10-40
31:23
27.75
50.23
31:47
52.56
31.00
$1:99
17.09
2391
5.0
1100
500-1
2883
20-2
3102
25 20
30008
00-98
31.51
29.04
30.34
31.33
17355
2364
DoResser
30.50
602
0:30
16.10
14:45
21.15
25.20
10:00
10.57
11:00
17.20
25
22-45
23.59
2238
12.55
8465
1555
2111
22.26
11:30
11.48
53.55
17.59
2114
26.11
20.54
24.9
2701
3692
7.95
6.21
5.20
8.85
11.20
3.97
4.99
5:90
0.24
874
10.53
571
9:29
18.05
2.70
4.00
5:1
2.74
4.63
632
935
9.00
10.53
13:63
351
7.56
1595
Abbit Doo. QA
ZWI4MMQA
10
11:06
04:05
51
13:37
11:24
05.44
0.38
11:21
12:11
12 16
F2 40
11h
11
39-45
2-14
15.55
17754
12
13:00
16
22
15:27
10000
15 90
18.19
13.12
10
24
HepoorAA
100
6:35
11:45
00
18:00
90
8:58
0.09
11 23
17 -6
18:22
1943
11
37 26
6.34
16
29
29.58
23
63
15.30
14
24.31
14
22 49
5:03
18.06
25/05
14:87
11:23
1.99
11:55
1411
14:8
1248
1465
1474
55552
1116
14
F296
14
99
MM
22
28
20UT
2402
22
29 49
26.5
28
20
15
2364
2000
12:42
25.04
25.29
21044
2701
19.66
2346
25
2360
33445
2423
12248
50
23
5040
12
55
56
35.0
22
3157
3552
Siggl Doc. QA
Quipet
16:44
15.5
14:03
17303
15.51
15555
18.08
17218
F640
1615
16.55
1531
PAWS
15
22.49
014
1862
90
1553
2055
15
1820
23.27
2009
2058
10.50
18
Nammioo
15:75
2:30
3:54
6,10
5.40
12.53
15.77
7.08
7.28
7.32
5.22
15.00
7.42
15:16
13:42
1.40
552
616
11:00
12
13,2
9:11
11:46
15:00
10:30
14.00
96
12.76
3.99
9.39
10
Queen 5-118
48C
7X
48%
7X
08
8X
2K
4K
Qwent 1-98
4K
2K
48%
FX
8%
8X
2%
46
TOWA
Slak
SnapKV
KoyDur
TOWA
SIKk
SnapWV
KINDBY
31

---

Table 13: Blama-3.2-3B-Instrud LongBench Results with prompt block size B E [64, 256)
(Higher is better). We highlight the best and second best methods within a given budget with bold
and underline.
Ang
42.11
2510
30.30
7027
3435
1764
20:30
3381
1001
3804
1936
4004
3479
42.5
56-52 40.11
2037
27.54
11:0
1471
123T 1930
3333
1604
2827
1674
1920
31.2
35.2
40.3
42.55
56.52
1308
29.26
5230
56.88
3805
5291
52.1
5547
5644
51.00
$1.30
57.54
40,0
3009
2424
12455
1935
53422
3891
5624
57.90
3196
3358
2603
5645
5240
57.36
41.00
55.0
Onde
56.22
300
53.4
56.22
55.00
5514
2815
55.45
56.45
5535
5002
5621
3515
55%
53.44
5441
3439
15.44
56-2
34500
5524
359K
3835
3585
3505
3605
3505
5000
5321
5599
5407
3579
3001
20.50
0125
17.50
1950
000
15.00
18.00
1950
8.50
1650
1900
20.50
1550
10.00
1250
1850
1955
20.00
1900
31
14000
21
K50
17.00
2000
2000
1900
3600
21.00
1350
1900
2100
Synthelic
96.90
1.50
00.90
24.00
47.00
1900
3500
(7.50
61.50
5050
85.00
05.00
6350
1900
96.95
95.50
15.00
1100
1500
28.00
1900
3500
4700
02.50
66.00
05.00
93.50
65.00
01.0
95.0
3.00
0.50
0.30
1.0
3.50
1.30
2,50
350
3.50
3.50
630
4.00
1.00
3/00
2:00
220
3500
1.00
1.50
1.50
5.00
3.0
400
1000
54,00
11:50
16,00
15:30
17.50
21.00
1900
21.25
25:50
25:25
1855
2136
2425
212
3400
14.10
17235
16.25
1822
1850
21.35
21.10
3:25
1055
25,55
25.55
36.00
SAMSim
Powshot Learting
42.58
9.78
41
41.9
47-48
41.04
41.88
4209
40:20
41.06
41:44
3655
42-35
42-58
9.89
25.30
1055
4040
41555
41.7
4007
41.9
42.47
4131
42.12
57.77
4.70
50.11
14002
00.37
57.45
59-48
36000
56.33
58206
59:26
59000
50000
53220
13/9
90.1
2382
67
5923
88-0
50
59
59
00.90
90.17
56.30
88-22
56.34
72.50
70.50
64.00
02.50
06:00
66.00
69000
13
72:00
60
77.00
55.00
00000
22.50
67
77000
62000
63500
00000
60000
73.50
11000
72.50
7000
73.50
53.50
65.50
72.50
16
2:49
9:26
15.00
16:09
16:5
36.04
96555
M039
M8S5
13455
15:55
16-9
3-2
850
16
6940
15
1635
5655
1655
25
14
55
MinoNess
Summor mo00oattttoo
23.21
21.70
23009
25.08
25.23
25.20
25.01
2500
53099
25.00
25
35.2
2458
25-00
25.54
16.29
22
23:48
25.04
25.00
55000
25.77
25.45
25.41
2502
25
21. 10
1:30
12 12:90
16 76
26
10 25
30.23
21 PM
22 2.
21.5
22
23 33.52
21.09
23.52
22.03
24 50
1.70
6:20
19.00
21 17
19
28.00
22 24
16
22 17
22 20
21.50
2255
Covitopon
00
37.97
26 15
28.22
10:42
70
29.59
10.51
31.50
29.00
50.00
52.8
28.34
13.41
59,99
17.78
26 12
28
90:71
31-47
26 70
29 29
31.22
27.12
11:78
31.95
30
53.5
Daltestor
16:24
6:08
17.82
10:50
12.44
2524
9.53
10.30
10
15008
1694
2158
$1340
1242
14
96.44
1387
1804
1700
2420
9.00
5:50
1112
1408
1681
2380
51.99
29.54
3107
Mili thee QA
Mhsioee
20.84 8-1
0.72
55,08
12
1866
1978
24.52
1330
12.88
14:20
16:37
16-25
21556
1357
21-45
26-94
15.46
10:76
14
1741
21-2
15 50
1307
14
17
50.31
2474
15
2200
2W06MQA
+2.29
1644
35.35
2825
24.97
37.63
25.43
3533
3901
4:24
37.34
48.03
4.23
3423
#258
41.0
42.29
24.34
86.1
1021
12.18
2500
4202
25.01
35.17
1950
41.10
38.58
10:24
4.47
33.22
4026
455
HepporQA
$9.59
12.38
3921
36.48
44.3
33.76
4146
95.00
4722
4339
452
5059
8325
98
4553
11
4151
46
47.52
506
4924
45
5364
5050
55.84
52.58
32117
44.54
3331
17.42
4161
55008
460
5280
5450
41.09
5119
55
1606
5214
1224
46
35
4150
W22
55.25
5250
54.77
4661
3294
5545
50.00
16.6
57.6
45.04
5108
42.16
46.16
2661
3331
5510
4321
835
4350
4525
5009
1124
11
312
425
26
37
36
42
4005
010
4720
4657
5025
Sagll Dac. QA
Quier
40.23
18:3
31.22
5000
5922
2991
5257
6001
5539
560
0055
4110
2
4125
1919
3509
25700
4046
2018
33
61
40.19
5934
6015
4005
37.30
4148
Nemalie
23:95 1/
1:40
17 24
19 59
21
15.60 08
19.35
19 16
20 40
20.00
39.54
44
22 Wh
23.9%
140
5:0
9000
18-46 46
28 56
28-71
15 48
37
35
17.04
52.00
20.25
18.99
21:00
22
6K
SX
2X
ex
8K
2X
42
6x
8%
6%
8X
2%
aK
8K
62
822
28
45%
65
2X
6%
9%
02
82
2X
4K
8X
9- 61
TOVA
SUk
SuyjKV
KeyDer
18 10-99 206
TOVA
SDK
SnoREV
KLYDoY
32

---

Table 14: KEYDIFF Recent tokens
LongBench Results with B = 128 (Higher is better). We highlight the methods showing the best performance within a given budget with boldface. X% indicates X% of KV cache budget is reserved to keep the recent tokens, while the remaining cache budget is managed by KEYDINS algorithm. t: A subset of samples were evaluated due to 00M errors (183/200 samples are evaluated
40.74
33:78
39-76
4691
30.45
48:66
16.65
48/15
45.79
48:36
5010
40.33
4551
20.14
4036
4806
J0-44
96.5 42:1
3024
3085
36:23
4120
M:73
4036
4128
4237
40.35
4136
42,40
35,0
40:38
42.40
51,94
50.34
38.44
56.63
51.85
5130
2216
48.00
52.8
5298
51.38
50.57
50,4
WA2
3500
4070
9063
5591
36588
57.29
5131
3635
5118
9612
5077
36.45
4001
2014
3645
Onie
61.00
64.95
02:12
18:33
02.15
62.37
6:44
03
62.00
0536
02.5
02.56
63.0
02 22.99
62
5017
0090
61-00
01.88
56.2
8635
35.90
56.31
23.44
55.77
51.8
51.14
5030
57.00
5714
57.05
5413
35.55
55.55
iWosh
99.00
22.50
71:00
59.00
51.37
0668
59:00
28.00
95.5
5258
50000
50200
50.00
00000
9625
5200
5200
20.50
650
19.50
20.50
900
22
21.00
15.0
20.00
30
20.50
30
20.50
12.00
19:0
Synthetk
99:50
23:50
38.50
12:50
51.50
89800
5800
08.50
6000
59
99.59
9000
980
3000
2200
96.50
19:00
4700
62
12.50
62550
30
93.00
9600
58000
57200
60.50
14.00
09
99
95
5,55
2.00
4.00
5:17
2:25
4.25
511
4:33
5:49
4:0
533
1.56
3.17
421
3:00
220
5.00
830
230
300
2300
130
3.00
2.0
5:0
3.00
300
500
45.50
22.25
29225
57,00
21.75
25
2700
4400
4200
5200
4000
13.00
4050
4000
4225
4250
1400
19200
10.25
1825
24
2500
26.30
28
1700
2025
2448
22000
5053
SAMSum
bewshor Leaning
43.57
43 20
43-29
01
48,75
40.56
41.14
43-58
45
53.0
-5 11700
20
54
5w 28
13
43-10
42.58
46 19
41-11
12.55
06
30
40 05
41-42
36
41
41.00
31 43
41 01999
37
41-41
TmiQQA
91.61
89 46
01 15:25
91
08. 84
96/08
835 10-00
86
32.2
02772
12:09
50
85-92
55555
40 11
09
86 13
35
20.7
38.00
87.25
58
39:57
89.57
24
00
73000
66.00
7120
72.00
01.00
82-50
21.50
72:10
64500
F1.00
725
62510
5150
7250
66.00
2000
750
72-50
71200
7300
2000
6550
MA0
5000
07500
21.30
73:50
21-00
7250
40.00
66.00
VCNcm
17.24
15:44
17.05
16.16
1955
1024
17:37
15:38
1851
1059
F2
1721
1022
1920
16
15.98
15.9
1674
1451
1553
1581
1575
16
1608
13.50
15288
MuliNeoss
Stmmtaritation
27.02
20.02
28 26
26
26.77
26
2740
26.
20.00
21.00
56
28 16
24
25.21
15
25.06
25
24
25
25
24
2500
24
25.25
24
25.30
25.0
25
25.32
20.21
21:57
25
21.08
12:08
23.55
23.28
23.57
34.55
72
23 26
2305
22
24 70
19
19
22
22 60
23.57
10
23.77
21.20
23.52
25
2344
23,00
CavReppont
34.00
29.51
20.33
12.19
52-42
20.41
11.00
33115
39.65
2012
32
55.09
26-24
22401
29.9
51.12
1100
22000
11 17
33,02
26
31 14
35.64
16:18
16.54
17-55
16.37
22
27-48
32:66
30
34.33
13.04
20/00
94
92.30
33
26.24
M.34
110
16
12
26
22
32
14
34
34.00
34
28
12.46
22.25
22
19,09
16.53
25.5
24.27
25.34
9948
2503
5354
2629
255
5357
2144
24
26
11
160
1:
1644
2634
15
20
20
25
19.54
25
24.52
13.99
21A8
25.09
Mill Doc. QA
SWAIMQQ
47.80
29.90
1:339
55.42
46.31
89.41
48.75
44.77
42.01
47:54
48.54
4551
14
46-41
40.50
42.9
23-27
4254
1015
37.95
46.1
34.81
41.02
47.5
44.00
4264
47.44
43.04
35.41
40.30
45.55
57.31
24.64
44:04
45.10
48.00
52.12
40.44
11:77
55.41
57.24
57.02
59.10
51559
54.55
56.90
59.09
27:27
46.20
40.00
44
47.39
50
51.52
41.91
4099
51
46.09
2014
4900
Mi-hh
59.000
32282
16.15
55.77
38.39
M027
55.27
50.1
17-30
5752
5965
585
120
5118
508
55
22
5357
200
4730
40
5253
1221
5521
5200
350
5521
47.07
5451
35
Stight Dic.. QA
56.12
20.32
1910
57
43
50.44
506
5558
5565
525
565
2009
5009
26
1M
1:
26
44
450
40.36
4006
50
5002
45
15
Quipar
47.00
34.77
41001
37.22
44
4557
40.99
50.24
48.65
00
40.5
2309
4029
2000
17
2222
55
4000
3556
4255
4574
4058
3665
2000
Nimalio
21
22344
23:53
21:81
34.70
24
27.36
37:45
50:55
12.17
11:35
26.04
28
20.00
23
16:45
19:45
20.15
17
19:55
20.00
19900
21.07
11.56
23.05
27.45
23.82
18.29
22.34
5%
6X
XX
<X
65
RK
2X
88
2K
8K
2k
45
8K
2X
A8
2X
46
08
8K
8K
5K
4K
Llanna. 138
Lirmdd 10
SuugCV
DotDlit 10%
Token
KorBift+ 20% Tokea
KEYDUR
S
bit 10%
Ream Tolons
bot 2015
Tolons
Kie
Rooss
33

---

Table 15: Anchor vector ablation study. Average of Full Longbench results for Llama 3.2-3B- Instruct. KEYDIFF results match Table 11. (Higher is better)
DEF
35.09
40.28
41.88
42.40
Pairwise
35.24
40.61
41.87
42.45
Median
35.43
40.67
41.89
42.26
Table 16: Distance metric ablation study. Average of Full Longbench results of Llama 3.2-3B- Instruct. KEYDIFF results match Table 11. (Higher is better)
KEYDIFF 35.09
40.28
41,88
42.40
DotProd
30.14
38.01
41.09
42.23
Euclidean
13.68
21.06
25.91
29.53
Table 17: Accuracy (%) on the Phonebook Lookup task using budget.
with 6k cache
Method
100
478
856
1233
1611
1989
2367
2744
3122
3500
1.0
KeyDiff TOVA
1.0
1.0
1.0
0.6
0.4
0.2
0.0
0.0
0.2
0.2
1.0
0.2
0.0
0.0
Table 18: Recall difference (KEYDIFF-Full) on NIAH benchmark for -lama-3.2-33
Depth
1000
4222
7444
10667
13889
17111
20333
23556
26778
30000
-0.06
0.06
11.0
0.10
-0.04
-0.44
0.30
0.28
-0.18
0.26
0.28
0,10
-0.08
22.0
0.04
-0.12
0.00
0.32
0.30
-0.18
0.16
0.28
0.14
00.4
33.0
0.02
0.06
-0.00
0.34
0.08
-0.16
0.26
0.26
0.20
-0.16
44.0
-0.06
-0.08
-0.16
0.30
0.26
-0.12
0.24
0.22
-0.10
0.04
67.0
0.02
0.02
0.14
0.36
0.28
-0.26
0.24
0.16
0.04
0.08
78.0
-0.10
0.26
89.0
0.02
0.08
0.06
0.30
0.26
-032
0.30
0.22
0,06
0012
100.0
0.00
0.06
0.26
0.00
0.06
0.02
0.00
0.044
0.14
0.04
Table 19; Relative latency of key scoring Android device (normalized by KEYDIFF at 512 KVs).
Lower better.
Method
512
1024
2048
.0966
8192
SnapKV
1.92
2.46
4.50
8.94
11.42
TOVA
1,02
0.94
1.25
1.95
3.06
KeyDiff
1.00
1.07
1.37
H2O
1.10
0.99
1.52
2.32
4.23
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made in the abstract are corroborated by both our theoretical
justification Section 3.3, experiments Section 4 and auxiliary results and discussion.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: In Section we discuss the fact that KEYDIFF is only tested on decoder based models featuring GQA and would like to extend it in the future to models with different designs such MLA.
3. Theory Assumptions and Proofs
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Question:
Answer: [Yes]
Justification: Proofs of all results are discussed briefly in their statement in Section 3.3 and rigorously proved in Appendix C.3.
4. Experimental Result Reproducibility
Question: If the contribution is a dataset or model, what steps did you take make your results reproducible verifiable? Depending on the contribution, reproducibility can be uccomplished in various ways. For example, if the contribution architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the case large language model), release of model checkpoint, or other means that are appropriate to your research.
novel
Answer: [NA]
Justification:
The paper releases neither a dataset or model, though the cache agement algorithm can be easily implemented using the description from the paper.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: Code is not provided as it is proprietary. However the algorithm may be readily implemented and results replicated using the description in the paper.
6. Experimental Setting/Details
If you ran experiments, did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? The full details can provided with the code, but the important details should be in the main paper, and information about how hyperparameters were selected should appear either in the paper or supplementary materials.
Question:
35

---

Answer: [Yes]
Justification: All hyperparameters selected for the benchmarks run to evaluate KEYDIFF are specified Section and Appendices and F.2. Hyperparameters to recreate figures are given in figure descriptions.
selectee
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
The only experiment using stochasticity Figure 7 and Figure 17 reports error bars and statistical significance. The Math500 results as well discuss the use of sampling and stochasticity in generating responses. Aside from this, the remaining results deterministic.
Justification:
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In all relevant cases, particularly experiments on TTFT Figure 17 and Figure 7, we mention the GPUs and compute resources used.
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wuip...ccopiiiie//hhhhoe
Question:
Answer: [Yes]
Justification: The research proposes a new cache management algorithm based on the geometry of the attention mechanism in decoder-based LLMs. It does not involve human subjects or obviously ethically sensitive applications, and it conforms the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This research foundational in nature and is not tied to particular applications or deployments. As such we do not see any direct path to negative applications of our work.
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)??
Answer: [NA]
The paper proposes a new cache eviction algorithm. Neither the models used, data cache eviction algorithm appear to pose high risk for abuse necessitating relcase safeguards beyond standard practices.
Justification:
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
36

---

Answer: [Yes]
Justification: Creators for datasets//enchmarks LongBench and Math500 are properly credited with citations. Open source models from the Ilaaaa and Qwen model classes are used to test KEYDIFF are properly cited as are their deepseek distill r1 variants.
13. Assets
Question: you are releasing new assets, did you document them and provide these details alongside the assets? Researchers should communicate the details of the dataset or the model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
Answer: [NA]
Justification: The research does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: If you used crowdsourcing or conducted research with human subjects, did you include the full text of instructions given participants and sereenshots, if applicable, as well as details about compensation (if any)? Including this information in the supplemental material is fine, but if the main contribution of your paper involves human subjects, then we strongly encourage you to include as much detail as possible in the main paper. According to the NeurIPS Code of Ethics, you must pay workers involved in data collection, curation, or other labor at least the minimum wage in your country.
Answer: [NA]
Justification: The research does not involve crowdsourcing experiments or research with human subjects.
15. IRB Approvals
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research does not involve human subjects, therefore IRB approval is not applicable.
Declaration LLM usage
Does the paper describe the usage of LLMss if it is an important, original, non-standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does impact the methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The research does not include any input from an LLM. In particular the core methodology and research is original to the authors.
37


Reviews:
[{"review_id": "qwpA84PQjl", "reviewer": "Reviewer_6KAK", "summary": "Long-context inference has become increasingly common. Due to resource constraints, the prefill must be chunked into small segments, which requires sparse attention algorithms to make decisions without access to the full context. This paper proposes a KV cache eviction policy based on the cosine similarity of Key vectors. By identifying Key vectors that significantly deviate from the mean, KeyDiff effectively retains important tokens. Evaluation shows that KeyDiff achieves high accuracy while also improving performance.", "questions": "Thanks for submitting to NeurIPS. This paper claims that key similarity can determine which keys are important, which is simple yet effective. I enjoyed reading the paper and would advocate for it if the proposed solution is widely applicable. I appreciate the effort to provide an intuitive explanation in the appendix. However, I kindly ask the authors to provide some additional evidence to further strengthen the argument:\n\n1. **Correlation Analysis**  \n   I would like to see the correlation between Key vector cosine similarity and attention scores. I understand that figures cannot be submitted during the rebuttal, so a table showing cosine similarity and attention scores sampled from request prompts would be helpful. Please include the Spearman rank correlation between cosine similarity and attention scores.\n\n2. **Partial Cache Attention Scores**  \n   What percentage of the total attention score is retained when only a subset of the KV cache (e.g., 4K tokens) is used compared to full attention?\n\n3. **Performance on Retrieval-Critical Tasks**  \n   I would like to see the performance of KeyDiff on tasks that require retrieving all keys to get the correct answer — for example, the Counting Star dataset. Due to time constraints, evaluating one model (e.g., LLaMA3.1 8B) is sufficient.\n\n4. **RULER Benchmark**  \n   Could you include results on the RULER benchmark, which is considered more challenging than LongBench?\n\n5. **NIAH Recall Saturation**  \n   For the NIAH dataset, while the token budget is 6K, none of the policies achieve 100% recall even when the token limit is 1000 or 4222. Is this due to model limitations? What about larger models?\n\n6. **PCA Analysis Interpretation**  \n   The paper shows multiple PCA analysis figures. While it is true that KeyDiff selects tokens more uniformly, it is unclear why this leads to better performance. Could you elaborate on how to interpret these graphs?\n\n7. **Key Vector Norm Variations**  \n   While the paper claims that Key vectors have similar norms, the beginning-of-text token tends to be an outlier with a smaller norm. Does KeyDiff account for this?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- Detailed evaluation across different models and datasets.\n- The proposed method is easy to implement and introduces limited overhead.\n- KeyDiff supports chunked prefill and GQA.\n\n## Weaknesses\n- More evidence is needed to demonstrate the correlation between Key cosine similarity and the attention score.", "was_revised": true, "final_justification": "I do believe the keys on the border are more important than the keys inside, especially given the strong correlation. However, only keeping the border still sounds not that robust. The results on complex task are not fully given and the cumulative attention score is still missing. Thus, I would like to keep the score.", "rebuttal": "Thank you for your thoughtful and considered feedback. We have replied to each of your comments below.\n\nRegarding the correlation between negative key cosine similarity and attention scores: below we report the Spearman rank correlation for each layer of the Llama 3.2 3B Instruct model, averaged over each head. We averaged the correlations over several randomly selected samples from the musique task of LongBench. We observe high correlation across layers, validating our primary claim. We can also infer from this correlation that a large percentage of attention scores will be retained if we evict KVs according to key cosine similarity. We can include this table in the final version of the paper, along with similar data for other models.\n\n|     Layer Index      |   1    |   2    |   3    |   4    |   5    |   6    |   7    |   8    |   9    |   10  |   11   |   12   |   13   |   14   |   15   |   16   |   17  |   18   |   19   |   20  |   21   |   22  |   23   |   24   |   25   |   26   |   27   |   28   |\n| -------------------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ----- | ------ | ------ | ------ | ------ | ------ | ------ | ----- | ------ | ------ | ----- | ------ | ----- | ------ | ------ | ------ | ------ | ------ | ------ |\n| Spearman Correlation | 0.8997 | 0.9561 | 0.9332 | 0.9496 | 0.9517 | 0.9484 | 0.9587 | 0.9578 | 0.9534 | 0.957 | 0.9628 | 0.9554 | 0.9658 | 0.9578 | 0.9477 | 0.9538 | 0.928 | 0.9373 | 0.9328 | 0.934 | 0.9311 | 0.914 | 0.9265 | 0.9284 | 0.9258 | 0.9394 | 0.9419 | 0.9448 |\n\nRegarding retrieval-critical benchmarks: while we were unable to implement the Counting Star benchmark during the rebuttal window, we have initial results on the Phonebook Lookup task, which requires exact recall of a phone number corresponding to a target name [1] from list of names and numbers. We report results averaged over five random phonebook queries with KeyDiff and TOVA using a 6k cache budget. We see that KeyDiff generally outperforms TOVA, but still lags behind the baseline once it begins evicting KVs from the cache.\n\n| Method/Phonebook Length | 100 | 478 | 856 | 1233 | 1611 | 1989 | 2367 | 2744 | 3122 | 3500 |\n| ----------------------- | --- | --- | --- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |\n|          Dense          | 1.0 | 1.0 | 1.0 | 0.8  | 1.0  | 0.8  | 0.6  | 0.6  | 0.8  | 0.6  |\n|         Keydiff         | 1.0 | 1.0 | 1.0 | 0.6  | 0.4  | 0.2  | 0.0  | 0.0  | 0.2  | 0.2  |\n|           TOVA          | 1.0 | 1.0 | 1.0 | 0.4  | 0.2  | 0.0  | 0.0  | 0.0  | 0.0  | 0.0  |\n\nRegarding evaluation on the RULER benchmark: while we don't have our own results comparing KeyDiff with competing baselines on the RULER benchmark, we would like to highlight that NVIDIA's KVPress package on GitHub (and the corresponding kvpress-leaderboard on Huggingface) has recently adopted KeyDiff. KVPress demonstrates KeyDiff's competitive performance on RULER and thus provides independent, third-party validation of our method. **Note that we are not affiliated with NVIDIA or KVPress in any way.**\n\nAccording to their evaluation -- including RULER as a subset -- KeyDiff achieves higher leaderboard scores than other eviction methods such as TOVA, SnapKV, QFilter, and Knorm, with a clear margin for Llama-3.1-8B-instruct and Qwen3-8B. Although KVPress benchmarking is done without applying the proposed block prompt processing (BPP), KeyDiff still outperforms competing methods. According to our results, KeyDiff performs best under the memory-constrained BPP setup; therefore, we expect a greater performance gap in KeyDiff's favor when the methods are evaluated with BPP enabled. \n\nWe also want to note that KeyDiff appears ranked fourth in the plot of KVPress. However, the methods ranked above KeyDiff are meta-heuristic approaches (e.g., DuoAttention, AdaKV, or SnapKV with Compressed Question) built upon an underlying score-based eviction scheme. KeyDiff is fully compatible with these meta-heuristics. Consequently, as a base scoring method, KeyDiff remains a strong KV cache eviction method.\n\nRegarding the NIAH recall saturation: we have noted this behavior as well and also attribute it to intrinsic model limitations. We will add a baseline NIAH heatmap without cache eviction to validate this in the final version. We have not yet experimented with larger models, but anticipate the NIAH scores to improve. Below, we show the difference in NIAH scores between the eviction-free baseline and KeyDiff with a KV cache of 6k (averaged over fifty samples), i.e., $$ NIAH_{\\mathrm{KeyDiff}} - NIAH_{\\mathrm{Full}}.$$ We can see that KeyDiff performs similarly to the eviction-free baseline for context lengths 1000 and 4222 and is roughly on par with the baseline at longer contexts. \n\n| Depth / Context Length |  1000 |  4222 |  7444 | 10667 | 13889 | 17111 | 20333 | 23556 | 26778 | 30000 |\n| ---------------------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |\n|          0.0           |  0.02 | -0.06 | -0.06 |  0.2  |  0.16 | -0.16 |  0.18 |  0.2  |  0.06 |  0.04 |\n|          11.0          |  0.1  | -0.04 | -0.04 |  0.3  |  0.28 | -0.18 |  0.26 |  0.28 |  0.1  | -0.08 |\n|          22.0          |  0.04 | -0.12 |  0.0  |  0.32 |  0.3  | -0.18 |  0.16 |  0.28 |  0.14 | -0.04 |\n|          33.0          |  0.02 |  0.06 |  -0.2 |  0.34 |  0.08 | -0.16 |  0.26 |  0.26 |  0.2  | -0.16 |\n|          44.0          | -0.06 | -0.08 | -0.16 |  0.3  |  0.26 | -0.12 |  0.24 |  0.22 |  -0.1 |  0.04 |\n|          56.0          | -0.06 |  0.0  | -0.24 |  0.26 |  0.26 |  -0.2 |  0.18 |  0.14 |  0.04 | -0.02 |\n|          67.0          |  0.02 |  0.02 | -0.14 |  0.36 |  0.28 | -0.26 |  0.24 |  0.16 |  0.04 | -0.08 |\n|          78.0          |  -0.1 |  0.08 | -0.26 |  0.26 |  0.3  | -0.26 |  0.2  |  0.3  |  0.02 | -0.04 |\n|          89.0          |  0.02 |  0.08 | -0.06 |  0.3  |  0.26 | -0.32 |  0.3  |  0.22 |  0.06 | -0.12 |\n|         100.0          |  0.0  | -0.06 | -0.26 |  0.0  | -0.06 | -0.02 |  0.0  | -0.04 |  0.14 | -0.04 |\n\nRegarding PCA analysis interpretation: The full KeyDiff scoring criteria (without an anchor, labeled \"Pairwise\" in the ablation study) is the sum of negative cosine similarity among keys. In order for a key to score highly, it must have a very low cosine similarity with all other keys in the KV cache. This occurs when keys are more uniformly distributed in key space rather than tightly clustered in a single region. This means that a set of more uniformly distributed keys will lead to higher KeyDiff scores and ultimately higher attention, as validated by the correlation analysis above. The PCA plots are an effort to demonstrate that the keys retained by KeyDiff are more uniformly distributed than competing approaches, while evicted keys remain similarly uniform (i.e., not introducing bias).\n\nRegarding the relation between key and beginning-of-sequence (BOS) token norms: This is a great point with a slightly nuanced answer. The BOS or sink token indeed has a smaller norm than other keys, due to its role in computing an approximate no-op in each attention head to avoid overmixing. We discuss this phenomenon in more detail in Section C.3. The smaller norm affects the inequality of Lemma 3.1, tightening the gap between cosine similarity with attention. However, the BOS token is typically not aligned with the majority of keys. Figure 16 shows that the key that is least similar to the key mean (which is typically the sink/BOS token) tends to have a high cosine similarity with the query mean. KeyDiff will always select this token due to its geometric irregularity, despite it having a lower norm than the remaining keys. This can also be seen in Figure 4, where the key with the highest KeyDiff score (the BOS token) can be seen as an outlier.\n    \n[1] Jelassi, Samy, et al. \"Repeat after me: Transformers are better than state space models at copying.\" arXiv preprint arXiv:2402.01032 (2024)."}, {"review_id": "WNRcRRgGJM", "reviewer": "Reviewer_P2EX", "summary": "The authors propose a training-free KV-cache eviction policy that scores tokens purely by how geometrically distinctive their keys are (low mean cosine similarity to other cached keys), which shows advantages in the chunk-prefill setting.\n\nThis observation that distinctive keys tend to attract high attention regardless of the current query lets KeyDiff reduce peak memory of prefilling with higher accuracy, which is critical for serving/edge deployments where the peak memory of a full-prompt prefill would exceed RAM budgets.", "questions": "- How does KeyDiff perform on RULER or similarly harder long-context datasets?\n- The authors mention extending KeyDiff to MLA. In MLA, all heads share the same low-rank token embedding E, with different Keys computed through different K projections. Dropping a token means discarding E and thus removing that token’s keys from every head, even if it is distinctive for only some heads. How will your method handle this head-coupling constraint?\n- The authors' “distinct keys ⇒ high future attention” assumption is intriguing, but will it hold on tasks where most tokens are already mutually dissimilar? When there are many key scores as “distinct,” KeyDiff may have no reliable ranking signal and could evict truly important tokens. Have you evaluated such scenarios, and how does the method safeguard against this failure mode?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n- Well-motivated setting: Chunk prefill under a hard KV budget is important in both serving and memory-constrained on-device LLMs inference.\n- Simple but novel insight: Linking low pairwise cosine similarity to high long-range importance is intuitive yet, to my knowledge, new and is backed by both visualization and a neat geometric bound.\n\n**Weaknesses:**\n- NIAH still lags the no-evict baseline: Figure 6 shows recall tapering for deeper needles; although KeyDiff beats other evictors, it is still materially below full-cache accuracy for long docs.\n- Missing harder retrieval tasks: The paper lacks harder benchmarks, such as RULER stress very rare tokens, which raises the concern about whether the property always holds.", "was_revised": true, "final_justification": "The paper proposes a simple but novel insight: distinctive keys (with low cos similarities) tend to attract high attention regardless of the current query, which is useful for chunked prefilling. \nI appreciate the author’s comprehensive reply. All of my concerns have been addressed. I will raise my score to 4 (Borderline accept).", "rebuttal": "Thank you for your helpful feedback. We have responded to each of your comments below.\n\nRegarding NIAH performance of KeyDiff: Thank you for your helpful comment; it prompted us to revisit the NIAH results. We re-ran our tests over more trials (increasing from the average of five random NIAH trials to fifty) to smooth out any noise in the tests. KeyDiff performs significantly better, and we plan to update the final paper with these results.\n    \nTo summarize our findings here: below, we show the difference in NIAH scores between the eviction-free baseline and KeyDiff with a KV cache of 6k (averaged over fifty samples), i.e., $$ NIAH_{\\mathrm{KeyDiff}} - NIAH_{\\mathrm{Full}}.$$ KeyDiff performs similarly to the eviction-free baseline for context lengths 1000 and 4222, where no eviction occurs, and performs roughly on par with the baseline at longer contexts. A key takeaway from this table is that the eviction-free baseline also cannot solve NIAH problems with 100% accuracy, so matching the model's NIAH performance is the best any eviction method can hope to achieve.\n\n| Depth / Context Length |  1000 |  4222 |  7444 | 10667 | 13889 | 17111 | 20333 | 23556 | 26778 | 30000 |\n| ---------------------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |\n|          0.0           |  0.02 | -0.06 | -0.06 |  0.2  |  0.16 | -0.16 |  0.18 |  0.2  |  0.06 |  0.04 |\n|          11.0          |  0.1  | -0.04 | -0.04 |  0.3  |  0.28 | -0.18 |  0.26 |  0.28 |  0.1  | -0.08 |\n|          22.0          |  0.04 | -0.12 |  0.0  |  0.32 |  0.3  | -0.18 |  0.16 |  0.28 |  0.14 | -0.04 |\n|          33.0          |  0.02 |  0.06 |  -0.2 |  0.34 |  0.08 | -0.16 |  0.26 |  0.26 |  0.2  | -0.16 |\n|          44.0          | -0.06 | -0.08 | -0.16 |  0.3  |  0.26 | -0.12 |  0.24 |  0.22 |  -0.1 |  0.04 |\n|          56.0          | -0.06 |  0.0  | -0.24 |  0.26 |  0.26 |  -0.2 |  0.18 |  0.14 |  0.04 | -0.02 |\n|          67.0          |  0.02 |  0.02 | -0.14 |  0.36 |  0.28 | -0.26 |  0.24 |  0.16 |  0.04 | -0.08 |\n|          78.0          |  -0.1 |  0.08 | -0.26 |  0.26 |  0.3  | -0.26 |  0.2  |  0.3  |  0.02 | -0.04 |\n|          89.0          |  0.02 |  0.08 | -0.06 |  0.3  |  0.26 | -0.32 |  0.3  |  0.22 |  0.06 | -0.12 |\n|         100.0          |  0.0  | -0.06 | -0.26 |  0.0  | -0.06 | -0.02 |  0.0  | -0.04 |  0.14 | -0.04 | \n    \n    \nRegarding evaluation on the RULER benchmark: while we don't have our own results comparing KeyDiff with competing baselines on the RULER benchmark, we would like to highlight that NVIDIA's KVPress package on GitHub (and the corresponding kvpress-leaderboard on Huggingface) has recently adopted KeyDiff. KVPress demonstrates KeyDiff's competitive performance on RULER and thus provides independent, third-party validation of our method. **Note that we are not affiliated with NVIDIA or KVPress in any way.**\n\nAccording to their evaluation -- including RULER as a subset -- KeyDiff achieves higher leaderboard scores than other eviction methods such as TOVA, SnapKV, QFilter, and Knorm, with a clear margin for Llama-3.1-8B-instruct and Qwen3-8B. Although KVPress benchmarking is done without applying the proposed block prompt processing (BPP), KeyDiff still outperforms competing methods. According to our results, KeyDiff performs best under the memory-constrained BPP setup; therefore, we expect a greater performance gap in KeyDiff's favor when the methods are evaluated with BPP enabled.\n\nWe also want to note that KeyDiff appears ranked fourth in the plot of KVPress. However, the methods ranked above KeyDiff are meta-heuristic approaches (e.g., DuoAttention, AdaKV, or SnapKV with Compressed Question) built upon an underlying score-based eviction scheme. KeyDiff is fully compatible with these meta-heuristics. Consequently, as a base scoring method, KeyDiff remains a strong KV cache eviction method.\n\nRegarding the extension of KeyDiff to MLA: we believe that, with the exception of the first decoder layer, the geometric observations underpinning KeyDiff are intrinsic to each layer's token embeddings, since $W_K$ is just a linear projection. The challenge is how to analyze the RoPE operator, since it is clear that RoPE introduces necessary some temporal bias while allowing keys to cluster together on a per-head basis. Evicting token embeddings per-layer without performance degradation is the main challenge of future work.\n    \nRegarding adversarial evaluation: we would like to emphasize that KeyDiff operates on keys directly rather than tokens, i.e., after we have applied the RoPE and the learned projection $W_k$ to the input to a decoder block. This, of course, makes it tricky to construct an input prompt that will cause KeyDiff to fail: as one might infer from Figure 4, the keys and queries tend to cluster together regardless of the input prompt. \n    Lemma 3.1 shows that attention scores are bounded by a function of the corresponding cosine similarity values, assuming a bounded key norm. If one can construct an input prompt that forces certain keys to have a massive norm relative to those already in the cache, KeyDiff will likely evict incorrect keys. However, we are not aware of a reliable method to construct such a prompt across all heads and layers."}, {"review_id": "zCOCCzElkT", "reviewer": "Reviewer_oNVT", "summary": "To address the challenges of the existing attention-based KV cache eviction methods, this work proposes a KV cache evictino method based solely on key similarity, named KeyDiff. The proposed KeyDiff method minimizes the pairwise cosine similarity among keys, thereby maximizing the diversity of the compressed KV cache. Extensive experiments validate that KeyDiff achieves significant superiority in both algorithm accuracy and inference effectiveness.", "questions": "See above.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The motivation of this work is demonstrated clearly and is easy to follow.\n2. The experiments are rich, which demonstrate the effectiveness and efficiency of the proposed method.\n\nWeaknesses:\n1. The complete evaluation result combining different KV eviction methods with the 'sliding window' strategy is lacking. The KeyDiff with 'sliding window' can achieve better performance in reasoning and code tasks, while the effects of other methods (TOVA, Sink, SnapKV) combined with 'slicing window' are unclear. \n2. The discussion on the ‘Attention-Based Token Eviction Challenges’ in Section 2.4 is more like a general challenge associated with block-wise processing strategies. How does replacing attention with cosine similarity specifically address this challenge?\n3. The referencing of experimental figures and tables is poorly organized, compromising the article's coherence and readability.", "was_revised": true, "final_justification": "In the rebuttal phase, the author has further clarified my remaining questions, particularly regarding paper formatting and the superiority of the cosine similarity-based eviation scheme. It is suggested that the author supplement the experimental results planned in the reply in the final version. I will maintain my rating 'Borderline accept'.", "rebuttal": "Thank you for your helpful comments. We have replied to each of them below.\n\nRegarding a more comprehensive analysis of the hybrid attention + sliding window eviction strategy: we do not have a comprehensive analysis of each strategy on LongBench at this time, but we can include such results in the final version of the paper. Attention-based eviction methods tend to have an implicit recency bias [2], which gives them an advantage compared to KeyDiff, which strictly looks at key similarity and ignores temporality. We can also state this motivation for adding the sliding window more clearly in the main text of the final version.\n\nRegarding replacing attention-based eviction with cosine similarity-based eviction: Attention-based eviction is limited by the number of tokens present in current block when evicting: it cannot know future attention scores based solely on the current block. By using cosine similarity instead, we have an eviction criteria that is independent of future tokens (i.e. key similarity) while remaining strongly correlated with future attention scores. We describe in Section 3.1 more precisely how we address the challenge presented in Section 2.4.\n\nRegarding the paper organization, we will do our best to reorganize the paper layout for the final submission to reduce the number of forward references and disreuptions to the reading flow.\n\n[2] Oren, Matanel, et al. \"Transformers are multi-state rnns.\" arXiv preprint arXiv:2401.06104 (2024)."}, {"review_id": "J62t6t63U3", "reviewer": "Reviewer_vjtt", "summary": "This paper proposes KEYDIFF, a training-free policy for evicting KV-cache entries when running large language models under limited memory and resource budgets. The key insight is that keys that are geometrically distinct—those with low cosine similarity to the rest of the cache—tend to receive higher attention weights, so preferentially retaining these keys preserves model performance. Algorithmically, the method computes the mean of all current keys as an anchor, scores each key by its negative cosine similarity to this anchor, and keeps the top-N least-similar keys, yielding an efficient O(N) procedure. Extensive experiments demonstrate that KEYDIFF outperforms existing baselines in both latency and memory consumption while maintaining accuracy.", "questions": "1. For the anchor update schedule, do you recompute the anchor after each eviction? What is the incremental overhead?\n\n2. What will KEYDIFF perform if we use quantized key? Does cosine similarity remain reliable?\n\n3. In chat mode, how does sliding-window KEYDIFF choose the window size?\n\n4. Could KEYDIFF combine with RAG? In this case, the cache contains both prompt and retrieved chunks.\n\n5. How does KEYDIFF perform on mobile device, since it is a resource contained environment.", "limitations": "1. Only decoder-only models are tested.\n2. Benchmarks assume ample GPU bandwidth; edge-class DRAM and cache is not tested\n3. KEYDIFF ranks keys on a per-layer basis but not per head; if one head relies on a subset of highly self-similar keys, those keys might be evicted.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The idea is novel. Requires only cosine distance; independent of attention implementation, so it can work with FlashAttention.\n2. Clear proof on the insight.\n3. Benchmarks cover essential aspects,\n4. Linear time solution; easy to apply\n\nWeakness:\n1. Limited architecture coverage; no evidence to show its effectiveness on MoE and encoder-decoder.\n2. Need to test on resource constrained environment.\n3. Need to show the anchor sensitivity at low budget.", "was_revised": true, "final_justification": "The rebuttal addresses part of my concerns; however, some experiments are difficult to conduct within the short timeframe, so I will retain my score.", "rebuttal": "Thank you for your insightful feedback. We have responded to each of your comments below:\n\nRegarding the incremental overhead of anchor updating: a naive approach would simply recompute the anchor from the current KV cache each pass through the model. As you suggest, an incremental approach is also possible. If we chose the key mean as the anchor, we recieve a single new key $K_c$ and we evict a single key $K_e$, we can rescale the new and evicted keys then add and subtract them appropriately:\n$$ K_A^{'} = K_A + \\frac{K_c}{N} - \\frac{K_e}{N} $$A similar relation holds during block prompt processing. This means the incremental anchor update complexity is proportional to the number of new keys plus the number of evicted keys.\n\nRegarding KeyDiff performance with quantized keys: preliminary internal analysis does show that cosine similarity remains reliable in downstream benchmarks. However, we do not have a comprehensive analysis of quantized eviction performance at this time.\n\nRegarding the sliding window size appropriate for chat mode: our goal was to address the lack of recency bias in KeyDiff that is present in attention-based methods and show that the sliding window corrects for this. We believe the optimal window size would be application-dependent and likely needs domain-specific experimentation and benchmarking to determine the correct window size.\n\nRegarding RAG integration: yes, KeyDiff can work with RAG. Prompt and RAG tokens could be naively combined and processed as a single long input prompt. KeyDiff could potentially be amended to retain prompt tokens and only evict RAG tokens to improve instruction-following.\n\nRegarding on-device performance: we were unable to properly benchmark a full LLM inference pipeline comparable to the existing NVIDIA GPU TTFT measurements during the rebuttal window. However, we anticipate that performance will behave   similarly, assuming the each KV cache eviction scheme does not introduce additional overhead on-device. To measure key scoring overhead on an edge device, we present relative latency on a recent Samsung Android device to compute the eviction scores of KeyDiff, TOVA, SnapKV and H2O, relative to the KeyDiff scoring latency with a cache budget of 512 KVs. Slight runtime variations can be attributed to kernel optimizations and proprietary hardware specifications.\n| Method | 512 | 1024 | 2048 | 4096 | 8192 |\n| ------ | --- | ---- | ---- | ---- | ---- |\n| snapkv | 1.92 | 2.46 | 4.50 | 8.94 | 11.42 |\n| tova | 1.02 | 0.94 | 1.25 | 1.95 | 3.06 |\n| keydiff | 1.00 | 1.03 | 1.01 | 1.07 | 1.37 |\n| h2o | 1.10 | 0.99 | 1.52 | 2.32 | 4.23 |\n\nWe can see that KeyDiff matches competing methods at small cache sizes and outperforms them at larger cache sizes by a wide margin.\n\nRegarding per-layer vs. per-head eviction: KeyDiff does in fact rank and evict keys on a per-head basis. This allows KeyDiff to attain excellent benchmark performance."}]

Author rebuttal:

Meta-review: This paper proposes KeyDiff, a training-free KV cache eviction method for LLM inference. Its core claim is that geometrically distinctive keys correlate with high attention scores, enabling efficient retention of important tokens for long-context LLMs under resource constraints. 
Strengths include its novelty, simplicity, low overhead, and compatibility with FlashAttention. It provides a strong theoretical basis and extensive evaluations.

Weaknesses noted were the need for more direct correlation evidence between key similarity and attention scores, and performance lagging baselines on some extreme retrieval tasks like Phonebook Lookup for very long contexts. Limited architecture coverage was also mentioned.

I recommend accepting this paper. Its novel insight into KV cache optimization offers a highly efficient and training-free solution. The authors' rebuttal provided compelling Spearman correlation data, cited independent RULER benchmark validation by KVPress, and presented on-device latency results, effectively addressing most major concerns. Reviewers acknowledged the comprehensive responses, largely expressing satisfaction.
Decision: Accept (poster)