Accurate KV Cache Eviction via Anchor Direction Projection for Efficient LLM Inference
Authors: Zijie Geng
Jie Wang
Ziqi Liu
Feng Ju
Yiming Li
Xing Li
Mingxuan Yuan
Jianye HAO
Defu Lian
Enhong Chen
Feng Wu
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
KV Cache Eviction
LLM Inference Acceleration
Primary area: deep_learning
TL;DR: We propose a projection-based scoring function in KV cache eviction for LLM acceleration.

Abstract: Key-Value (KV) cache eviction---which retains the KV pairs of the most important tokens while discarding less important ones---is a critical technique for optimizing both memory usage and inference latency in large language models (LLMs).
However, existing approaches often rely on simple heuristics---such as attention weights---to measure token importance, overlooking the spatial relationships between token value states in the vector space.
This often leads to suboptimal token selections and thus performance degradation.
To tackle this problem, we propose a novel method, namely **AnDPro** (**An**chor **D**irection **Pro**jection), which introduces a projection-based scoring function to more accurately measure token importance.
Specifically, AnDPro operates in the space of value vectors and leverages the projections of these vectors onto an *``Anchor Direction''*---the direction of the pre-eviction output---to measure token importance and guide more accurate token selection.
Experiments on $16$ datasets from the LongBench benchmark demonstrate that AnDPro can maintain $96.07\\%$ of the full cache accuracy using only $3.44\\%$ KV cache budget, reducing KV cache budget size by $46.0\\%$ without compromising quality compared to previous state-of-the-arts.

Accurate KV Cache Eviction via Anchor Direction Projection for Efficient LLM Inference
Zijie Geng', Jie Wang", Ziqi Liu', Feng Ju', Yiming Li², Xing Li², Mingxuan Yuan',
Jianye Hao Defu Lian', Enhong Chen', Yongdong Zhang', Feng Wu'
University of Science and Technology of China
Noah's 's Ark Lab, Huawei (zijiegeng, zigi ziqiliu, fengj jul @mail austc.edu... cn, jievangxdustc.edu
Tianjin University
Abstract
Key-Value (KV) cache evietion-which retains the KV pairs of the most important tokens while discarding less important ones-is critical technique for optimiz- ing both memory usage and inference latency in large language models (LLMs). However, existing approaches often rely on simple heuristics- such as attention weights-to measure token importance, overlooking the spatial relationships be- tween token value states in the vector space. This often leads suboptimal token selections and thus performance degradation. To tackle this problem, we propose a novel method, namely AnDPro (Anchor Direction Projection), which introduces projection-baser scoring function to more accurately measure token importance. Specifically, AnDPro operates in the space of value vectors and leverages the projections of these vectors onto "Anchor Direction" "-the direction of the pre-eviction output-to measure token importance and guide more accurate token selection. Experiments on 16 datasets from the LongBench benchmark demonstrate that AnDPro can maintain 96.07% of the full cache accuracy using only 3.44% KV cache budget, reducing KV cache budget size by 46.0% without compromising quality compared to previous ttate-of-the-arts.
Introduction
Large language models (LLMs) have revolutionized human society by reshaping the way process information [T3]]. Modern LLMs are primarily built upon the Transformer architecture, with self- attention as their core mechanism (6). However, the self-attention mechanism inherently involves quadratic computational complexity, which grows dramatically as the sequence length increases (7]. To address this bottleneck, the Key-Value (KV) cache mechanism has been introduced store and reuse intermediate results-i.e.. the KV pairs in the self-attention mechanism- reduce the computational complexity from quadratic linear [8) the demand for processing longer sequences grows, however, the KV cache size expands proportionally. leading to substantial increases in both GPU memory consumption and I/O latency Therefore, effective KV cache management is critical for practical LLM scaling and deployment.
Recent studies have revealed that LLM self-attention exhibits inherent sparsity, with only small subset of tokens making a substantial contribution to the model's output [10[12]. This insight has sparked the development of series of KV cache eviction strategies, which identify and retain the KV pairs of the most important tokens while discarding less important ones [3315). For instance, H2O 9 greedily eliminates KV pairs based on their cumulative attention weights during the generation phase. SnapKV [16] employs an observation window to generate queries and uses the obtained attention weights to measure the importance of prompt tokens during the prefilling phase. Ada-KV 177 further
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

refines this paradigm by jointly identifying important tokens across attention heads within each Transformer layer. By selectively removing less critical tokens, these approaches can effectively optimize both memory and time efficiency without significantly compromising the performance. The aforementioned approaches es- sentially rely on an importance -riterion-which we refer to as a "scoring function"- determine to- ken retention priority. Most of them use attention weights as the scoring function, assuming that tokens with higher attention weights should be re- tained preferentially. Although this assumption is intuitive, they overlook the spatial relationships between to- ken value states in the vector space, which play a critical role in how these states interact influence the model's output. This often leads to subop- timal token selection decisions and thus performance degradation. There- fore, effective KV cache management requires advancing beyond attention- only heuristics by developing scoring functions that explicitly account for the vector space geometry.
Auchor Direction
Pard (3.1
V.- (-1.)
0.45
Ri dutla 4g
(9. 10.30..9) 9)
Fane (-B 6
y (0.3,0.9
12 (0.-1)
0.3
Anchor direction projection
(b) Post-eviction output
Figure 1: eviction. (a) Consider three tokens with value states V1, U2 Vg and attention weights @1. d2, Ag. The pre-eviction output is denoted as y. Our approach computes the pro- jections of a,00 onto the "anchor direction" (i.e., the direction of y). (b) With a budget of 2, the attention-based eviction approach selects ti and U2 resulting in a post- eviction output Dattn and an error of lly-Jam 2l2 =1144. Our projection-based approach selects V1 and V3. resulting in a post-eviction output Zproj, with a smaller error of yy Uproj 12 =0.22.
A diagram of the projection-based KV cache
To tackle this problem, we propose a novel method, namely AnDPro (Anchor Direction Projection), which introduces a projection-based scoring function to more accurately measure token importance. Specifically, we formulate KV cache eviction as combinatorial optimization problem and then transform it into a sparse optimization formulation through mild relaxations. The theoretical and intuitive analysis of this problem motivates us to introduce an "anchor direction" in the vector space, i... the direction of the pre-eviction output. Intuitively, this anchor direction guides the retention of the most important semantic information, leading us to use the projections of token value states onto this direction to measure token importance (see Figure IT. Experiments on 16 datasets from the LongBench benchmark demonstrate that AnDPro maintains 96. 96.07% of the full cache accuracy using only 3.44% KV cache budget, reducing KV cache size by 46.0% without compromising model quality compared to previous state-of-the-arts.
2 Related Work
LLMs have been widely applied across various domains and tasks [88 19.. Among the numerous research directions related to LLMs, our work is most closely aligned with LLM inference accelera- tion 20 25) particularly in the areas of KV cache management, eviction, and budget allocation.
KV Cache Management plays a erucial role optimizing both memory and time efficiency in LLM inference. In a recent survey by Li et al. [3], KV cache management techniques are categorized into three levels: token-level, model-level, and system-level strategies. Our work is primarily related to token-level KV cache optimization, specifically KV cache eviction and KV cache budget allocation. Other token-level methods include KV cache merging (26 30), KV cache quantization 37]. and KV cache low-rank decomposition [18
KV Cache Eviction approaches selectively retain the most important KV pairs and discard the less critical ones. Some methods, such as StreamingLLLM [14), FastGen [11), and recent studies 20 21]. are designed based on certain patterns and fixed rules, such as the sliding windows, for KV cache
eviction. Other approaches, such as H2O 9 Scissorhands [10), and recent studies 42 43 22 44]. leverage attention scores as a criterion for selecting the most important KV pairs from the cache. V [16] introduces an observation window to generate queries, using accumulated attention scores to evaluate token importance in prefilling. Ada-KV [7 refines this framework by adaptively allocating the cache budget across attention heads based the attention scores. More recently,

---

CriticalKV 45 combines attention scores with the norm of value vectors as a better scoring function. Our work builds upon this line of research, and draws inspiration from SnapKV and Ada-KV.
KV Cache Budget Allocation focuses on allocating the budget across different components of the model, such layers and attention heads. Layer-wise allocation techniques include PyramidInfer [46 and DynamicKV
477 Head-wise budget allocation methods include Ada-KV [17]. HeadKV (88)
and DuoAttention [49] These methods are orthogonal our work, focus on retaining important
KV pairs for any layer- or head-level budget allocation. In this work, we implement our approach to achieve an adaptive budget allocation across attention heads.
3 Our Approach
In this section, we introduce our proposed method, AnDPro (Anchor Direction Projection). Sec- tion 3.1 begins by formalizing the KV cache eviction problem to provide a theoretical foundation for deeper analysis. In Section 3.2 we present a theoretical exploration of the optimization problem, which motivates the general form of projection-based scoring function. Section 3.3 further derives practical form of the scoring function through an intuitive analysis. Finally, in Section 3.4 we provide the implementation details of AnDPro. All the proofs can be found in Appendix
3.1 Problem Formulation
This section aims to answer the following question:
Q1: How to formulate the KV cache eviction problem in a manner that enables in-depth analysis on the design of an appropriate scoring functionfor KV cache eviction?
Our objective is to select a subset of tokens from the input prompt to retain, discarding the others, while approximating the original outputs accurately possible. In this section we consider one single attention head. Consider an input sequence X = " where n represents the context length, i.c., the number of tokens in the prompt.
D Let æ; E Ig denote the embedding vector of the thh token, where d denotes the embedding dimension. Let W W W Raxd be the parameter matrices for the query, key, and value projections, respectively. For the 2th token, its query qi key k; and value states v, given by:
q Wax, xi k = x, v. W. x,
Let be a query given from an observation window, which will be further detailed in Section 3.4 The pre-eviction output of the attention head is given by:
a,V, where a; Softmax(g q T k.). Isisn
Let S C. [n]] be the set of tokens selected to retain. The post-eviction output, i.c., the output derived when only retaining KV pairs corresponding to tokens i E S, then given by:
Σ 0;V;, where à; Softmax(q k:).
iES
Our objective is that the post-eviction output approximates the pre-eviction output as accurately as possible. It is intuitive to use the squared error as a metric to quantify the eviction loss:
L 9)
ll - 2
(4)
Additionally, we impose a sparsity constraint |S| S on the number of retained tokens. The following proposition provides more convenient expression of the post-eviction output to aid the further analysis.
Proposition 1.
Let S C [n] be the set of retained tokens, and define the indicator functioon
1,
i S,
21
0,
i s
'Throughout this paper, all vectors are presented as column vectors. We use the index i and its corresponding token z; interchangeably, given that ambiguity arises.
3

---

to represent whether the 1th token is retained. Then, the post-eviction outpit can be expressed as:
-==120 2;,,;
ÿ
(6)
Σi=1 2,0;
Based on Proposition
we can formulate the KV cache eviction problem as follows:
1 1= 2;0;0;
12
min =0 2
S.L. Σ
2 S k.
(PO-C)
1==1 2;0;
2
In the realm of sparse optimization, prevalent approach for dealing with the sparsity constraint to introduce an 4-normm regularization [50]. When dealing with binary variables, the 4 4-rom is equivalent to lo norm, which counts the number of non-zero elements. The regularized form of
Problem (PO-C) is then expressed as:
2
min (c(0,1)
Zj.
(PO-R)
2,01
Although Problem (PO-R) in a concise form, remains N'P-hard, making exact solution com- putationally infeasible. Given the context of LLM inference, where solution needs to be found within milliseconds, we seek identify high-quality solutions quickly and approximate the problem's optimal solution. To this end, we explore mild relaxations of (PO-R) to derive scoring function that can facilitate fast filtering for efficient KV cache eviction. Notice that directly relaxing the binary variables 2; in (PO-R) to continuous values would lead to problem degeneration and results in trivial solutions. Specifically, when 2; are relaxed, they can be scaled arbitrarily without affecting the first term in the objective function. If the values of 2; are scaled sufficiently small, the second term in the objective function will diminish to zero, yielding trivial solutions.
We introduce new variables and Bi, defined by and 8 _
4
240
(7)
Then, we obtain:
> -i=1 2,0,0%
n
3 V.
and Σ
B:a; = 1.
(8)
11
1= 2,00g
> Bia
i=1
Consequently, Problem PO-R can reformulated as:
min (0,1)))
y
3,a, D2
+ As L Big
2
im
1=1
(9)
s.t. 2
B,a = 1,
sB, = 24, i= 1,. n.
In this reformulation, As result, the regularization term would approach zero, and smaller values of s would always yield better objective function values. Moreover, if we impose lower bound s, the optimal solutions will always set take to this lower bound. Therefore, we fix 8 as a constant satisfying 0 < 8 < 1, and perform convex relaxation of the binary variables zę. This leads to the following optimization problem:
select an arbitrarily small which would lead to extremely small z;-
1 2
min 1
y
Bia
+ As
3
s.t.
B.a, 1.
(P1)
Through mild relaxations, we derive Problem (T). based on which we further work on the design of the scoring function in the subsequent sections.
A1:
Remark 1. We would like to re-emphasize that our goal is not to achieve exact solution to the original problem, which complex enough so that an exact solution intractable. Instead, we aim leverage this analysis provide insightful motivations for the design of scoring functions.

---

3.2 Projection-Basee Scoring Function: General Form
Although Problem PI) offers a concise formulation, solving it directly during the LLM inference process remains infeasible. Inspired by the "screening rules" in sparse optimization [51], we now investigate the design of a closed-form scoring function that can identify the active variables in Problem (PI). i.e., those with non-zero coefficients in the optimal solution. In this way, we can retain the active variables without explicitly solving the entire optimization problem. Thus, this section aims to answer the following question:
Q2: it possible to find a closed-form scoring function that identifies the active variables for Problem (PT) If so, what is the ideal mathematical form of such scoring function?
Let 3 denote an optimal solution to Problem P1 In this section, will show that under certain conditions, it is possible to determine that 3 0 for some E [n]. implying that the corresponding tokens can be removed from the cache. To further investigate the problem, introduce new set of variables, y Ei=1 B, We can then reformulate Problem Pl as:
min 3E(0.
| 2
+
As
3,
2
i=1
(P-Primal)
S.L. u = y
B,a,o,
Σ 3,0 =
We now derive the dual problem of (P-Primal), as presented in the following theorem. Theorem 1. The dual problem to Problem (P-Primal) is given by:
+ y c+ 1 Σ pr S):
sup
(P-Dual)
where 1y" E R2 and Ç E IR are dual variables, and pr <) A min (0, As ai (17 0; c))
(10)
Problem (P-Primal) is convex, and its constraints are affine. According Slater's condition [52], as long as (P-Primal) is feasible, strong duality holds. The reason why we care about (P-Dual) lies in the utilization of the optimal conditions, which can provide valuable insights into the optimal solution 3 Specifically, by applying the Karush-Kuhn- Kuhh-TTkkrr (KKT) optimal conditions, we can derive the following theorem:
Theorem 2. Let 3 be an optimal solution to Problem P-Primal and (11 5²) be an optimal
solution to Problem (P-Dual). Then we have:
a; (11 T 0; (*) < As
8 0,
(11)
a, (1 T U. (*) > As
8r =
The following corollary concludes this section.
Corollary 1. There exist 0 E R² and E R such that:
a a
(v,
0: 0 v. - b) < 1
3 = 0,
(1)
P2
(12)
a(0 0)
a: 0 0i b)
> 1 3
3: D
Corollary I reveals the existence of a scoring function of the form:
(a) Scoring function
(b) Projection
Figure 2: Illustration of the scoring function.
0. + (oTv
(13)
(a) The scoring function 8;, function of both 8; and a;, can distinguish between activate (green plots) and inactivate (red plots) samples. (b) The computation of 8; = a,(0 e; + b), which repre- sents the signed distance of v, to the hyperplane H. scaled by 0g-
As illustrated in Figure 2(a) this scoring func-
tion precisely identify the active and inacti- vate variables (PI). Tokens with low scores will be inactivate (PT). Therefore, these to- kens can be safely evicted from the cache.
A2: We can define scoring function in the form of Equation 13
5

---

Remark 2. In Theorem 2 we have shown that nf" and 5 correspond to the parameters O and b that we are interested in. However, is infeasible directly derive ni and Ç* without explicitly solving Problem (P-Dual). Therefore, we turn to an intuilive analysis on O and b to derive a more practical form the subsequent section.
3.3 Anchor Direction Projection: Practical Form
The theoretical analysis in Section 3.2 motivates to define scoring function in the form of Equation [3] Despite the thcoretical soundness, the determination of the parameters 0 and b remains challenging, because the dual variables 17" and are inaccessible before solving Problem P--Dual.. Therefore, this section aims to answer:
Q3: How can we determine generally good parameters A and b in practice?
We begin by analyzing special case when 0 0. In this case, the scoring function is simplified to 8; = a;b, where is a constant. Setting b = 1 gives us the most commonly used score, i.e., the attention weights. From this perspective, existing methods that relied solely on attention weights can be viewed as special instance of our framework.
For the more general case when 0 * O, without loss of generality, With this assumption, the equation H 0 x + b 0 represents a hyperplane in R", and 0 + b represents the signed distance (a distance metric that can assume negative values) of the point v; from H. The factor scales these signed distances. This computation is illustrated in Figure 2(b)
assume that |00| 1.
When applying this scoring function for top-k token selection, the tokens with relatively larger signed distances from H. scaled by a; are retained, while the other tokens are discarded. This procedure essentially preserves the projection of the output onto the direction of 0. We refer to the direction of 0 as an "anchor direction" ", as it acts as a reference to guide the selection of retained tokens. natural and intuitive way to set the direction of y as the anchor direction. This choice helps strengthen the semantic information along the direction of the pre-eviction output, ensuring that the most significant semantic features are preserved.
In this case, the proposed scoring function is defined as s; a T v. + b), where b acts as a bias term balance the relative importance of projections and attention weights. As b - oo, the scoring score. The results suggest that a
function gradually converges to the traditional attention- carefully chosen b leads to slight performance gain, while setting 0 also results in stable performance. Therefore, we set b = 0 and thus a.y in the main experiments. We conduct experiments on the choices of and in Section 4.5
A3: We can simply set 0 = y and = O.
3.4 Implementation Details
In this section, supplement some implementation details of AnDPro. Following SnapKV (16), retain an observation window W to accumulate attention weights from the last several prompt tokens, which generates queries hew. Specifically, We retain the tokens within this window as well as the first token. At each time step in the observation window, the attention for the 1th token and the corresponding pre-eviction output are computed as:
af Softmax k;) and y¹ alv..
(14)
1si5t
1=1
The scoring function for each token is then computed as:
Σ
a 2
(15)
tWW
tEW
We perform top-k selection across all attention heads within each layer, based on their scores. This allows for flexible budget allocation among heads, significantly enhancing generation quality. Additionally, we introduce a useful technique of merging tokens into chunks. Notice that both SnapKV and Ada-KV employ max/mean pooling operations, ensuring that adjacent tokens have similar scores. This leads to successive selection of tokens, significantly improving the performance.

---

Table I: Comparison based on Nistrral-BBIIsttructt--Z among 16 datasets from LongBench [53]. The results for H2O, Streaming, SnapKV, and Pyramid are from Feng et al. [17], and the results for
V and CriticalKV V are reproduced based on their papers [7 45 bold red, and the second best results in underlined blue.
We mark the best results in
Single. Doc. QA
Multi Doc. QA
Summarization
Few shodl earming
Synthetic
Code
NIvQA
Qumper
MF-n
HoqaaQA
2WikMM44
Musique
GovReport
@MSum
MultiNew
TRBC
TrivirA
SAMSum
Peamn
PRe
RB.P
Ave.
Score
Full Cache 26:63
32.99
49.34
42.77
27.35
18.77
32.87
24.24 27.10
71.00
86.23
42.96
2.75
86.98
55.33
52.87
42.51
Budget=123
128
120
21.19 21.66
38.60
30.63
20.65
12.19
20.65
22.42
21.81
39.00
82.52
40.68
2. 79.56
49.13
46.76
34.40
Streaming
16.61
14.74 31.40
28.05
21
12.08
18.44
18.91
19.26
43.50
74.22
29. 29.00
2.75 31.65
41.27
38.84
27.63
Snapky
19.17
21.40
42.93
36.76
22.4
15.86
19.16
21.84
21.55
47.50
84.15
40.24
2.30
26.26
50.69
47.13
35.09
Pyramid
20.16
21.77
43.55
36.78
23
14.39
19.53
22.03
21.47
51.00
84.62
40.24
2.79
70.77
50.57
46.53
35
Ada KV
21.79
23.03 47.07
38.70
22.85
15.92
19.94
25.05
21.84
63.00
85.36
40.01
3.20
72.13
51.36
49.29
37.41
CV
21.55
23.27
46.67
38.95
24.95
20.83
23.14
16
65.00
85.53
40.02
77.81
53.58
50.98
38 38.42
AnDr
25.14
47.33
39.79
23.99
17.34
20.40
23.45
67.50
85.59
40.62
76.94
53.77
51.55
38.96
Budget=256
11.07
23.09
77
Streaming
30.71
27.7
28.85
SnapKV
48.13
21.91
61.50
50.23
Pyranid
22
21.40
40.98
52.78
38
A
23.02
25.70
49.23
40.18
24.76
17.43
22.17
23.21
23.48
67.50
85.58
41.67
84.65
55.07
52. 17
39.93
CriticalVV
23.70
26.66
49.00
40.05
25.12
17.86
21.99
25.35
23:45
68.00
86. 19
42.07
2.92 85.8
53.81
50.42
40.03
AnDPro
25.71
28.17
49.31
40.04
25.81
18.68
21.66
23.64
23.63
70.30
86.39
42.60
2,86
85.62
55.74
52.87
30.84
Budget=512
120
21.72
26.03
44.81
32.33
23.16
14.86
23.65
84
24.70
42.00
85
22
41.57
3.40 86.45
53.04
49.68
37.22
Streaming
18.76
17.17
37.09
30.21
21 64
9.93
24.44
20.00
25.57
62.00
72. 36
29.95
2 48
18.
43.70
40. 13
29.60
SnapKV
24.60
27.81
48.98
39 46
25 20.255252
16.98
23
22.90 96
24.37
67.00
85 88
41.26
2.78
86.56
54.81
51.71
40.26
Pyramid
23.23
27.94
48.87
40.50
24.36
16.74
23.22
23.16
24.37
67.00
85.73
41.74
3.16
85.67
54.16
50.34
40.01
Ada-KV
23.88
29.05
48.79
40.44
25. 50
17.66
23.47
23.47
24.48
69.50
86.39
41.38
2.94
87 566
56.58
52.88
40.86
CriticalVV
23.83
28.67
19.13
40.18
26 18 18.19
23.52
23.57
24.28
70.00
86.39
42.16
2.82 87.55
56.51
52.64
40.98
AnDPro
41.34
27.01
23.76
25.01
2.83
57.46
53.61
Budget= 1024
H20
24.74
Streaming
41.75
32.40
22
26.50
67.00
2.88
16.57
39.76
SuapKV
25.47
29.57
25
19.01
23.89
26.21
69.50
$1.92
41.44
Pyramid
24.21
29.86
48.93
40.75
25.05
18.77
25.73
24.06
25.66
86.31
42.25
2.97
87.11
54.75
52.
41.07
AV
25.60
31.15
49.02
41.47
27.07
18.77
25.40
23.84
25.92
70.50
86.55
43.07
2.54 87.14
57.27
53.85
41.82
CriticalVV
26.03
31.50
48.39
41.73
27.10
18.84
25 30
24.10
25. 99
71.00
86.30
43.16
2. 66
87 23
56.69
53.20
41
AnDPro
25.78 32.54
49.35
42,20
26.94
18:63
25.33
24.01
26. 26.29
71.00
86,30
43,46
2
2.68
86.98
57.18
53.77
42.03
Inspired by this, we merge tokens into chunks, each containing a predefined number of tokens, to maintain semantic coherence. The chunk size is treated as a hyperparameter. The value state of a merged chunk is the weighted sum of the original tokens' values, and its attention score is the sum of the individual attention weights. The pseudocode of AnDPro is provided in Appendix I..
4 Experiments
"Fil Carde Stain
Full
Now. Secre
4.1 Experimental Setup
Pull Carle
Ful Cacae
SazghCV
Supp&V
V
Datasets We conduct comprehen- sive experiments to demonstrate the effectiveness of our approach on two commonly-used benchmarks, Longbench [53] and Needle-in-a- Haystack [54]. Specifically, Long- Bench is a long-sequence bench- mark containing 16 datasets covering multi-task domains. The Needle-in- a- Haystack dataset was specifically used to assess the context retrieval capabilities of different budget strategics, particularly in tasks involving long-context retrieval. More detailed information about these datasets are in Appendix B.2 Code is available at https: / thub.......... com/ wwtp//RAAaa--STT///I.. AnDDro
CrttiallV
Chriaali
Aniliho
AnDPno
155
730
519
1000
100
519
Bodgee
(a) Mistral-7B- -n-ssnttttttstt
(b) Llama-3.1 1--.e-...-----ttttete Instrrctt
Figure 3: Average scores on the LongBench dataset. The numbers annotated on the gray lines represent the proportion of budget saved by our method compared to the current SOTA to achieve the same accuracy.
Baselines We evaluate our approach using two open-source large language models: Mistral-7BB
Instruct-v0.2 (55) and 1.lam-3.11881 -88-- (56). We compare AnDPro against several strong baselines. These include representative prior works such as H2O [9. Streamingl 14, and
SnapKV (16), as well as latest SOTA methods, including Ada-KV 11 and CriticalKV 45
7

---

Avernge
Doya
HASI! Outer lough
Legh
(a) Full Cache
(b) Ada-KV
97.37
Dogth
Ceese12244 Courei Leugh
Casoe Lagh
(c) CriticalKy
(d) AnDPro
Figure 4: Results of Mistral-7b-Instruct--bb
the Needle-in-a- Haystack test. The x-axis represents the document's context length, and the y-axis indicates the depth of the needle insertion. Each square the heatmap demonstrates the correctness of retrieving proper sentence inserted in the context for a given context length and insertion depth. The Average Score is calculated by averaging the sum of score with different insert depth across various context lengths.
HyperParameters and Experimental Environment In our main experiments, evaluate the performance different methods across range of budget sizes, specifically setting budgets to B E {128, 256, 512, 1024) test their effectiveness under different memory constraints. All experiments are run on single A800 80G GPU. the main experiments, we set the observation window size to 32 and the chunk size 4. Our implementation is built upon the Ada-KV framework, and the hyperparameters are aligned with those used in the baseline. More details can be found in Appendix B.3 We will release our code the paper is accepted for publication.
4.2 Evaluations on LongBench Test
Table I presents the performance scores of various methods under different budget allocations for the Mistral model. Due to space limitations, results for the Llama model are provided in Appendix [.I Results on the Chinese datasets in LongBench are in Appendix C.2 Overall, AnDPro consistently delivers state-of- state-of-the-ar of-the-art (SOTA) performance across both models and range of budget configurations.
We further visualize the performance scores in Figure 3 Notably, for the Mistral model with budget of 256 (A: 256), AnDPro achieves average score of 40.84, which is 96.07% of the full cache accuracy, while utilizing only 3.44% (7455) of the total KV cache budget. In comparison, the previous SOTA method, CriticalKV, requires budget of 474 achieve similar performance. AnDPro achieves a 46.0% reduction in budget size compared with CriticalKV. Moreover, multiple datasets, such as MF-en, SAMSum, and Lcc, AnDPro achieves comparable or even better results compared with full cache.
4.3 Evaluations on Needle-i--a-Haystan Test
evaluate the long-context retrieval capability of different KV methods using the Needle-in-a- Haystack test. This test involves retrieving specific statement (the "needle") placed within a long context window (the "haystack"). In our experiment, we set the budget size to l = 128 and compare AnDPro against Ada-KV and CriticalKV, As shown in Figure 4 AnDPro significantly outperforms the baselines, achieving a score of 97.37, which is very close to the performance of the full cache. Additional results of other baselines in Appendix
4.4 Memory & Latency
We evaluate the computational efficiency of various KV eviction strategies by measuring the peak memory usage and decoding latency across different context lengths, ranging from 8K 256K.

---

We conduct the experiments on the Distral-7b-Instruct--e model with
fixed budget size k = 128. To mea- sure decoding latency, we use differ- ent methods to generate 1K tokens
Phat Meaaay Liee (08)
and compute the per-token decoding latency. The results are in Figure 5 The peak memory usage and decoding latency roughly the same for these eviction methods, significantly opti- mized compared with the full cache model. This demonstrates that AnD- Pro achieves similar memory and time efficiency with much better accuracy compared with previous SOTA eviction methods. Further analysis of the inference time composition of different methods is in Appendix C.44, demonstrating that the additional computation introduced by AnDPro-specifically the Update KV Phase-incurs negligible time overhead.
Seapity
60
64%
1280
150K
200K
Contect Lengra
(a) Peak memory usage
(b) Decoding latency
Figure Memory and latency different methods.
4.5 Analysis
isolate the impact of our contribution, i.e., the projection projection-based scoring function compared to attention based scores. We then analyze the effects of three design choices in algorithm: (1) merging tokens into chunks, (2) preserving the first token, and (3) cross-head budget allocation. The results confirm that the projection-based scoring function consistently outperforms its attention-based counterparts, and that each component contributes positively to performance in our framework.
Ablation Study We conduct ablation studies in Appendix C.5
We explore different choices of anchor direction 0 and the bias term The results are in Appendix C.6 demonstrating that our setting 0 y and 0 achieves a superior and robust performance.
Different Choices of 0 and b
Eviction Loss and Score Visualization We analyze the eviction loss between pre- and post- eviction outputs. Results in Appendix[C.] demonstrate that our method can effectively reduce this loss. Furthermore, we visualize the distribution of token scores Appendix C.8
Value Vector Analysis We investigate the role value vectors the eviction process. Using PCA, project value vectors and model outputs into two-dimensional space. The results are in Appendix C.9 We also provide statistical histograms of value vector magnitudes in Figure [5 in Appendix C.9 These results help understand the reason why projection-based score works intuitively.
We provide some case studies in Appendix C.10 showing that AnDPro can more accurately preserve important tokens compared to tateetion-based scoring functions.
Case Study
Longer context we evaluate performance on extremely long contexts ranging from 64k to 384k tokens. The results are in Appendix C.II] demonstrating that AnDPro achieves the best performance even on much longer contexts.
5 Conclusion
In this work, we model KV cache eviction as combinatorial optimization problem, and relaxes it to sparse optimization problem. Motivated by the theoretical and intuitive analysis, we proposes AnDPro (Anchor Direction Projection), which leverages projection-based scoring functions for more accurate KV cache eviction. Extensive experiments on LongBench and Weedle-in-a-Haystee benchmarks demonstrate the effectiveness of our approach.

---

Acknowledgements
The authors would like to thank all the anonymous reviewers for their insightful comments. This work was supported in part by National Key R&D Program of China under contract 20222D0119801, National Nature Science Foundations of China grants U23A20388 and 62021001.
References
[1] Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. A survey of large language models. arXiv preprint arXiv: 180..1823,, 2023.
[2] Muhammad Usman Hadi, Rizwan Qureshi, Abbas Shah, Muhammad Irfan, Anas Zafar, Muham- mad Bilal Shaikh, Naveed Akhtar, Jia Wu, Seyedali Mirjalili, al. A survey on large language models: Applications, challenges, limitations, and practical usage. Authorea Preprints, 2023.
[3] Shervin Minace, Tomas Mikolov, Narjes Nikzad, Mcysam Chenaghlu, Richard Socher, Xavier Amatriain, and Jianfeng Gao. Large language models: A survey, arXiv preprint arXiv:2402.06 06666 2024.
[4] Xize Liang. Chao Chen, Shuang Qiu, Jie Wang, Yue Wu, Zhihang Fu, Hanzhu Chen, Feng Wu, and Jieping Ye. ROPO: Robust preference optimization for large language models. In Forty- second International Conference on Machine Learning, 2025. URL
[5] Zehao Wang. Lin Yang. Jie Wang, Kehan Wang, Hanzhu Chen, Bin Wang, Jianye Hao, Defu Lian, Bin Li, and Enhong Chen. Logictree: Improving complex reasoning of LLMs via instantiated multi-step synthetic logical data. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
[6] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30(2017), 2017.
[7] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. ArXiv, abs/1904 (bs//9994.0059, 2019. BRLLihttps//ppp..sennniiii org/CorpusID 129944533
[8] Shi Luohe, Hongyi Zhang, Yao Yao, Zuchao Li, and hai zhao. Keep the cost down: A review on methods to optimize LLM's KV-ccche consumption. In First Conference on Language Modeling, 2024. httt:tttt///eereeeetet
net/ heot/foruuridd-88kjoggg5533
[9] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy- oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36:34661-3471 2023.
[10] Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidiss and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of impor- tance hypothesis for Ilm kv cache compression at test time. Advances in Neural Information Processing Systems, 36, 2024.
[11] Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang. Jiawei Han, and Jianfeng Gao. Model tells you what discard: Adaptive KV cache compression for LLMs. In The Twelfth International Conference on Learning Representatinss 2024. URL
wwweeeeiiiieeeeettureeeeee net/forum?
id=uNrFpDPMyo
[12] Mirko Farina, Usman Ahmad, Ahmad Taha, Hussein Younes, Yusuf Mesbah, Xiao Yu, and Witold Pedrycz. Sparsity in transformers: systematic literature review. Neurocomputing, page 127468, 2024.
10

---

[13] Haoyang Li, Yiming Li, Anxin Tian, Tianhao Tang, Zhanchao Xu, Xuejia Chen, Nicole Hu, Wei Dong, Qing Li, and Lei Chen. A survey on large language model acceleration based on kv cache management. arXiv preprint arXiv:2412.1 19442, 2024.
[14] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309.17453 2023.
[15] Qingyue Yang, Jie Wang, Xing Li, Zhihai Wang, Chen Chen, Lei Chen, Xianzhi Yu, Wulong Liu, Jianye Hao, Mingxuan Yuan, al. Attentionpredicto::: Temporal pattern matters for efficient I1m inference. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
[16] Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapky: Llm knows what you are looking for before generation. arXiv preprint arXiv:2404.14465 2024.
[17] Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S Kevin Zhou Ada-kv: Optimizing kv cache eviction by adaptive budget allocation for efficient I1m inference. arXiv preprint MrXiv:2407.11555 11500, 2024.
[18] Pengkun Wang, Zhe Zhao, HaiBin Wen, Fanfu Wang, Binwu Wang, Qingfu Zhang, and Yang Wang. Llm-autoda: Large language model-driven automatic data augmentation for long-tailed problems. Advances in Neural Information Processing Systems, 37:64915 2024.
[19] Haoyang Liu, Jie Wang, Yuyang Cai, Xiongwei Han, Yufei Kuang. and Hao Jianye. Optitree: Hierarchical thoughts generation with tree search for LLM optimization modeling. In The T'hirty-nintl Annual Conference on Neural Information Processing Systems, 2025.
[20] Chi Han, Qifan Wang, Hao Peng, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. Lm- infinite: Zero-shot extreme length generalization for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume I: Long Papers), pages 3991-4008, 2024.
[21] Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir H Abdi, Dongsheng Li, Chin-Yew Lin, et al. Minference 1.0: Accelerating pre-filling for long-context lims via dynamic sparse attention. arXiv preprint arXiv:2407. 02490, 2024.
[22] Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant Nair, Ilya Soloveychik, and Purushotham Kamath. Keyformer: Kv cache reduction through key tokens selection for efficient generative inference. Proceedings of Machine Learning and Systems, 6:1 14-127, 2024.
[23] 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 (xX.x:2335.13444 2023.
[24] Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint 194337711..19377 2024.
[25] Zhihai Wang, Jie Wang, Jilai Pan, Xilin Xia, Huiling Zhen, Mingxuan Yuan, Jianye Hao, and Feng Wu. Accelerating large language model reasoning via speculative search. In Forty-second International Conference on Machine Learning, 2025. URL https://openreviiai net/ forum?id=oq0t5BBXI
(26) Jang-Hyun Kim, Junyoung Yeom, Sangdoo Yun, and Hyun Oh Song. Compressed context memory for online language model interaction. In The Twelfth International Conference on Learning Representations, 2024. URL httpps:::///ot
[27] Zhongwei Wan, Xinjian Wu, Yu Zhang, Yi Xin, Chaofan Tao, Zhihong Zhu, Xin Wang, Siqi Luo, Jing Xiong, and Mi Zhang. D2o: Dynamic discriminative operations for efficient generative inference large language models. CoRR, abs/2406. 13035, 2024. URL httpss
//doi.org// 1000 48550/ arviv. 2406. 13035

---

[28] Akide Liu, Jing Liu, Zizheng Pan, Yefei He, Gholamreza Haffari, and Bohan Zhuang. Mini- cache: Kv cache compression in depth dimension for large language models. arXiv preprint arXiv:2405. 14366, 2024.
[29] Yifei Yang, Zouying Cao, Qiguang Chen, Libo Qin, Dongjie Yang, Hai Zhao, and Zhi Chen. Kysharer: Efficient inference via layer-wise dissimilar kv cache sharing. arXiv preprint arXiv:2410. 18517, 2024.
[30] Jian Yuan, Ziwei He, Haoli Bai, Jingwen Leng, and Bo Jiang. Weightedkv: Attention scores weighted key-value cache merging for large language models. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5, IEEE, 2025.
[31] Zhewei Yao, Reza Yazdani Aminabadi, Minjia Zhang, Xiaoxia Wu, Conglong Li, and Yuxiong He. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. Advances in Neural Information Processing Systems, 35:27 1822288,,,,, 2022.
[32] Hailin Zhang, Xiaodong Ji, Yilin Chen, Fangeheng Fu, Xupeng Miao, Xiaonan Nie, Weipeng Chen, and Bin Cui. Pqcache: Product ceatttiizatiin-aascee kvcache for long context IIm inference. CoRR, 2024.
[33] Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length Ilm inference with kv cache quantization. arXiv preprint arXiv:2401. 2024.
[34] Haojie Duanmu, Zhihang Yuan, Xiuhong Li, Jiangfei Duan, Xingcheng Zhang, and Dahua key and value cache quantization for large language models. arXiv
Lin. Skvq: Sliding window bodding-winddw preprint arXiv:2405.00. 19, 2024.
[35] Mengzhao Chen, Yi Liu, Jiahao Wang, Yi Bin, Wenqi Shao, and Ping Luo. Prefixquant: Static quantization beats dynamic through prefixed outliers in llms. arXiv preprint arXiv:2410.05265, 2024.
[36] Yujun Lin, Haotian Tang, Shang Yang, Zhekai Zhang, Guangxuan Xiao, Chuang Gan, and Song Han. Qserve: W4a8kv4 quantization and system co-design for efficient I1m serving. CoRR, abs/2405.04532, 2024. URL httpss://tt.o....//e org/ 10. 480500485///// 48550/arXiv
045322
[37] Haocheng Xi, Changhao Li, Jianfei Chen, and Jun Zhu. Training transformers with 4-bit integers. Advances in Neural Information Processing Systems, 146-49466-418,, 2023.
[38] Hao Yu, Zelan Yang, Shen Li, Yong Li, and Jianxin Wu. Effectively compress kv heads for 11m. arXiv preprini 2rXiv:2406.070556 2024.
[39] Hanshi Sun, Wi- Chang, Wenlei Bao, Size Zheng, Ningxin Zheng, Xin Liu, Harry Dong, Yuejie Chi, and Beidi Chen. Shadowkv: Kv cache in shadows for high-throughput long-context Ilm inference. arXiv preprint arXiv:2410.21465, 2024.
[40] Peiyu Liu, Ze-Feng Gao, Wayne Xin Zhao, Yipeng Ma. Tao Wang, and Ji-Rong Wen. Unlocking data-free low-bit quantization with matrix decomposition for kv cache compression. arXiv preprint arXiv:2405. /2591, 2024.
[41] Harry Dong, Xinyu Yang, Zhenyu Zhang, Zhangyang Wang, Yuejic Chi, and Beidi Chen. Get more with LESS: Synthesizing recurrence with KV cache compression for efficient LLM inference. In Forty-first International Conference on Machine Learning, 2024. URL https //openreview.
[42] Junqi Zhao, Zhijin Fang. Shu Li, Shaohui Yang. and Shichao He. Buzz: Bechive-structured sparse kv cache with segmented heavy hitters for efficient Imm inference. arXiv preprint 1.Xiv:2410.23079 2024.
[43] Yilong Chen, Guoxia Wang, Junyuan Shang, Shiyao Cui, Zhenyu Zhang, Tingwen Liu, Shuo- huan Wang, Yu Sun, Dianhii Yu, and Hua Wu. Nacl: A general and effective kv cache eviction framework for Imm inference time. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7913-7926, 2024.
12

---

[44] Insu Han, Michael Kapralov, Ekaterina Kochetkova, Kshiteej Sheth, and Amir Zandich. Bal- ancekv: Kv cache compression through discrepancy theory. arXiv preprint arXiv:2502.07861, 2025.
[45] Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S Kevin Zhou. Identify critical KV cache in LLM inference from am output perturbation perspective, 2025. URL /tRppsttt///ppeererii
net//orrun2dd1IIDDGG
[46] Dongjie Yang, XiaoDong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. Pyramid- infer: Pyramid kv cache compression for high-throughput Ilm inference. arXiv preprint arXiv:2405. /2532, 2024.
[47] Xiabin Zhou, Wenbin Wang, Minyan Zeng, Jiaxian Guo, Xuebo Liu, Li Shen, Min Zhang, and Liang Ding. Dynamickv: Task-aware adaptive kv cache compression for long context llms. arXiv preprint arXiv:2412.14838, 2024.
[48] Yu Fu, Zefan Cai, Abedelkadir Asi, Wayne Xiong, Yue Dong, and Wen Xiao. Not all heads matter: A head-level kv cache compression method with integrated retrieval and reasoning. arXiv preprint arXiv:2410. 19258, 2024.
[49] Guangxuan Xiao, Jiaming Tang, Jingwei Zuo, Junxian Guo, Shang Yang, Haotian Tang, Yao Fu, and Song Han. Duoattention: Efficient long-context Ilm inference with retrieval and streaming heads. arXiv preprint ar arXiv:2410. 10819, 2024.
[50] Jonas Ranstam and Jonathan A Cook. Lasso regression. Journal of British Surgery, 105(10): 1348-1348, 2018
[51] Jie Wang, Jiayu Zhou, Peter Wonka, and Jieping Ye. Lasso screening rules via dual polytope projection. Advances in neural information processing systems, 26, 2013.
[52] Stephen Boyd. Convex optimization. Cambridge UP, 2004.
[53] Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023.
[54] Greg Kamradt. Needle in haystack-pressure testing llms. Github Repository, page 28, 2023.
[55] Albert Q Jiang. Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint 110.022310 2023.
[56] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXi: 2024.
13

---

A Proofs
Proposition 1. Let S [m]] be the set of retained tokens, and define the indicator function
1, iES S, 0. i S
24
(5)
represent whether the 8th token is retained. Then, the post-eviction output can be expressed as:
Σ 7 Σ Ei=1 2;0g
1= 2,0,0
ÿ
(6)
Proof. We have
exp(qn k;)
Softmax In k;)u; EES
jES exp(1, k;)) V;
iE8
iES
exp R.)
(16)
vist expla. kx) V
ii= 2i00;2i
explg, k2)
Dim1 1 2,04
2g
expl C. ks)
Theorem 1. The dual problem to Problem P-Primaly is given by:
1 Σ p)(n.C).
sup n.
ml| 17 y c+
(P-Dual)
where 17"h 12 and Ç R are dual variables, and
pe(n, - min (0, As - as (1 v; 6))
(10)
Proof. Recall that Problem P-Primal takes the form of:
n
min 11"
||
2 + As
3
i=1
n2 s.t. u y
3,a,0
Σ Bia =1
t=1
By introducing the new variables n E R and ( E R, we get its Lagragian:
3,r. u w) + ( Bla (Eaa--1 (17)
T1
L(B, u. n. = 2 |ull2 2 + As
B: + nT
i=1
The primal variables are E [0, f and R".
The dual function g(n, () is then:
g () inf I.(3, u. n7.
8.u
=n y inf 1
12 3aam 12 + < > Brak (18)
|//1/2
17
+
inf
As
3
21
=n T + inf
|lul22
17
+
inf
Bs (As ai (n v; ())
2
3. [0.
It is easy to derive that
1
inf
1ul2 17 TTu
= - ||m11
(19)
4
2
14

---

with the optimal solution u = and
inf 8g (As - as (n (n= (3)- ()) A 1
min (0, As as (nJo: 8s ())
(20)
8
with the optimal solutions
0,
As - (n T - 5) > 0,
1
E
0,
As (1) T () = 0,
(21)
As - a4 (n T v. - 5) < 0.
Therefore, we have:
1
g(n - 1|llll +
5+
min (0, (0,A-o0 -
(n'nv, - -())
(22)
Combining the above, we get the dual problem:
g(n.C) = 1mmll +n y -+ Σ min (0, As as (n 0s <))
sup n.C
(23)
Theorem 2. Let 3 be optimal solution to Problem solution to Problem (P-Dual). Then we have:
P-Primal) and (ni ,5* be optimal
a; (1) T 0, -C)
< As
7
3r = 0,
(11)
a, (n " U; -3) As
B
Proof. By the strong duality, it is easy show that (17' (*) is geometric multiplier. Therefore, from the optimal condition, we have
(3 u²) E inf L(3, u, n (C))
(24)
We then complete the proof according Equation 21
Corollary 1. There exist O E IR." and b E R such that:
0 + b) <
8r = 0,
(12)
a; 0 T U; + b)
> 1
3
Proof. We can take
0 2 r/
6
(25)
As
As
where 17" and 5* are the optimal solution to Problem P-Dual
This completes the proof.
15

---

B
Implementation Details
B.1 Algorithm
simplified pseudocode AnDPro is provided Algorithm T We omit some unimportant details (such as preserving the first token) for simplicity.
Algorithm AnDPro Algorithm in One Layer
Require: A set H of all heads, A set W of the observation window, Number of tokens L outside the observation window, Queries "hEMH Keys {ke (E(L, Values {ul (of"hee H.(L)) Chunk size C, Budget size B for each head
Ensure:
Retained KV cache { ThE
a h Softmax:ee111 (q"it
1:
2: cut
hEH,rEW.ie(L/CC* E jEChunkk ay hi o
3: 0 IeEL,EE..eLLL/O!* Σj jEChunk,
Act
het
4: W + observation window chunks
5: nd IEH.IEN Eie(L/o U2
6: 8, heH.rew.ee(t//o (y 6
7: a |NEHAELLL/O)+ Enery 8i
htt
8: 8 + CoNCANnEH.iLLLLq((6]
9: 1S* + (o |H x B)
10: Shh Ineht 1th UW
return [S"
B.2 Datasets
Longbench is comprehensive benchmark that consists of 16 datasets and serves robust evaluation tool due to its wide variety of prompts with different domains, types, and lengths. It designed for long-sequence tasks spanning multiple domains, including single-document QA, multi-document QA, summarization, few-shot learning, synthetic tasks, and code generation. T provides detailed information of the 16 datasets in LongBench. These datasets have average input lengths ranging from 1, 235 to 18, 409 tokens, with an average token length of 7, 425. For our evaluation, we followed the recommended evaluation procedures for each dataset, with scores ranging from 0 to 100.
Table 2: Details of 16 datasets from the LongBench benchmark.
Task NarrativeQA
Task Type
Eval Metric
Avg Len
Language
Sample Num
Single-Doe. QA
Fl
18,409
EN
200
Qasper
Single-Doc. QA
F1
3,619
EN
200
MultiFicldQA-en
Single-Doc. QA
F1
4,559
EN
150
HotpotQA
Multi-Doc. QA
F1
9,151
EN
200
2WikiMulúhopQA
Multi-Doc. QA
FI
4,887
EN
200
MuSiQue
Multi-Doc. QA
F1
11,214
EN
200
GovReport
Summarization
Rouge-L
8,734
EN
200
QMSum
Summarization
Rouge-L
10,614
EN
200
MultiNews
Summarization
Rouge-L
2,113
EN
200
TREC
Few-shot Learning
Accuracy
5,177
EN
200
TriviaQA
Few-shot Learning
Fl
8,209
EN
200
SAMSum
Few-shot Learning
Rouge-L
6,258
EN
200
PassageCount
Synthetic
Accuracy
11,141
EN
200
PassageRetrieval-en
Synthetic
Accuracy
9,289
EN
200
LCC
Code Edit
Sim
1,235
Python/C#/lava
500
RepoBench-P
Code Edit
Sim
4,206
Python/Java
500
16

---

B.3 Code and Hyperparameter
Our code framework is adapted from AV specifically leveraging its concise and user- friendly custom classes to facilitate more efficient and convenient budget filtering and allocation. The primary updates include cross-head filtering strategy. We employ max pooling with kernel size of 7 and set the size of observation window to 32. The code is released at wttttts:/// thub. com/ MIRALab- DSTCCLLM-- AnDoro
17

---

C Additional Results
C.1
Main results of Llama LongBench
Table shows shows the scores of different methods based on the Llama model in 16 datasets. Overall, the results are consistent with those of Mistral, and AnDPro also leads to improved quality after cache eviction.
Table 3: Comparison based on Llama-3. 10ama-3.1-98 1------nnsttuctt among 16 datasets from LongBench. We run all the baselines to derive the results based on their released code. We mark the best results in bold red, and we mark the second best results in underlined blue.
Single-Doc. QA
Mult-Doc. QA
Summarization
New-shotL.ammigg
Synthetic
Code
NovQ4
Qasper
MF
HarooQA
2WikiMQA
Musique
GoeRepon
QMSum
MohnNews
TREC
Trivioo4
SAMSum
PCounl
RB.P
Ave.
Score
Foll Cache
51.80
Budgel
SnapKy
25.54
50.99
57.17
27.88
20.77
21.05
90 46
40.76
99.50
56.88
46 46.50
43.21
PyramidKV
27.83
32.98 51.45
56.72
44.67
30.54
89
21.67
63.00
90:45
40.06
8.00
100.
55.37
43.79
44.46
AV
25.06
34.50
52.27
56.29
47.57
29.06
11.17
23.
21.51
62.00
40.84
8.00
99.50
58.45
48.72
45.03
CriticalVV
26.56
35.71
52.90
27.21
47.53
29.57
21.77
64
21.79
63.50
91.44
41.62
7.75
100.00
59.09
49.32
45.59
AnDPru
26.66
38.22
54.34
57.47
47.57
29.42
22.09
23.67
21
67.00
92.35
40.90
7.70
100.00
59.15
50.06
36.13
SnapkV
26.92 38.19
52.62
57.03
46.75
29.63
23.07
21.92
22.82
58.50
91.83
40.81
7.75
99.50
59.95
48.63
45.50
PyramidVV
28.46
39.36
54.30
56.77
45.50
22.91
Ada
69.00
CV
70.00
92.75
100.00
AnDPro
27.28
42.09
54.72
$7.98
47.52
31.98
23.57
27
23.58
72.00
92.54
41.55
7.67
100.00
62.57
51.77
47.57
BudgS
SnapKy
28.40
41.52
55.40
$7.66
47.48
30.95
24.92
24 46 24.54
68.50
92 33
41.98
7.33
99.50
61.25
50.39
47.29
PyramidVV
29.15
43.04
55.55
57.71
47.67
31.27
26.05
04.08
24.54
70.50
92.67
41 .2
7.33
100.00
59.96
47.51
47.41
Ada-KV
26.92
42.68
55.20
57.47
48.06
31.27
24.95
24 17
24.40
71.00
92.14
42.35
7.33
100.00
62.26
50.62
47.55
CriliallV
26.75
43.75
55.45
25
48
32.03
2. 96
24 44 24.50
72.50
92.14
41.92
7.12
100.00
62.25
$1.17
47.83
AnDPro
28.03
44.25
55.61
59.29
48.30
24,86
24.55
24.83
73.00
91.97
42.08
100.00
62.68
52.12
48.12
Budget=1024
Snapky
PyramidKV
44.57
56.14
48
3199
20
23
26.00
70.50
92.41
42.46
100.00
49.12
Ada
28.52
46.01
55.72
57.85
48.10
32,02
26.98
24.72
72.00
91.97
42.55
100,00
61.98
51.52
48.30
CriticalyV
28.15
46
56.00
57.99
48 47 32.68
37 20
69
25.74
72.50
91.97
42.33
6.92
100.00
61.79
51.36
48.37
AnDPro
29.40
46,83
56.72
58.01
48.68
32.64
26.69
24.96
25.92
73.00
91.97
43.55
7.38
100.00
62.4
52.39
48.79
C.2 Results on the Chinese Datasets in LongBench
Table the scores of different methods based on the Llama model on 5 Chinese datasets fron LongBench. Although Llama model don support Chinese language, AnDPro leads improved quality after cache eviction.
Table 4: Comparison based on Llama-3. 3.1.......111 1-8B-Instruch on Chinese datasets from LongBench. The results demonstrate that AnDPro still achieves the best overall performance on Chinese datasets.
MF-zh
dureader
vesum
Isht
PRe-zh
Avg.
Full Cache
58.69
33.78
17.32
46.00
97.67
50.69
Budget=128
CriticalKV
42.57
24.32
12.51
29.50
93.75
40.53
Ada-KV
52.32
24.33
12.15
25.75
97.25
42.36
AnDPro
55,40
24.77
13.04
39.50
97.15
46.09
Budget=256
CriticalKV
48.12
24.74
13.52
24.00
94.00
40.88
Ada-KV
54.86
24.88
13.40
23.52
98.00
42.93
AnDPro
56.84
25.71
13.92
42.50
98,50
47.49
Budget=512
CriticalKV
55.51
26.21
14.47
29.25
79.66
41.02
Ada-KV
57.83
25.75
14.82
22.50
97.67
43.71
AnDPro
57.99
27.63
14.65
45.00
98,50
48.75
Budget=1024
CriticalKV
57.07
27.40
15.47
23.00
91.50
42,89
Ada-KV
58.54
27.19
15.47
22.00
98.00
44.24
AnDPro
58.57
29.07
15.85
45.50
98.17
49.43
18

---

C.3 Results of Needle-in-a-Hayttach test
Figure presents the Weedle-in-a-Haystaee (NIAH) scores across all methods. AnDPro significantly outperforms all baselines, achieving a high score of 97.37, which is very close to the performance of the full cache.
Avarue Seme to
Aveapo & ano 53 37
(a) Full Cache
(b) StreamingLLM
06.06
Octial
Outina Leath
(c) H2O
(d) PyramidKV
Average Score: 18
Average Scure: 81 30
Deeth Pooue
Shaghh
CALIII Outent Lough
Oueknt Loegh
SnapKV
(f) Ada-KV
Averge Seore: 92775
Average Scor:: 07 37
Dosth EER8EE888
(g) CriticalKV
(h) AnDPro
Figure 6: Results of Mistral-7b-Instrrut-t... on the Bredle-in-a-Haystee test. The x-axis represents the document's context length, and the y-axis indicates the depth the needle insertion. Each square in the heatmap demonstrates the correctness of retrieving proper sentence inserted in the context for a given context length and insertion depth. The Average Score is calculated by averaging the sum of score with different insert depth across various context lengths.
C.4 Runtime Analysis
We visualize The detailed comparison of time consumption different phases in the infer- ence process in Figure 7 The results demonstrate that the additional computation introduced by negligible time overhead.
AnDPro AnDPro-speciffcally the Update KV
(a) Context Length 64000
(b) Context Length 128000
Figure 7:
The detailed comparison of time consumption across different phases in the inference process under varying input lengths. The figure demonstrates the time costs of three key phases when processing input sequences of 64,000 and 128,000 tokens with output length of 1,000 tokens.
To provide more detailed quantitative breakdown, the specific runtime measurements are presented below (unit: scconds/iillscconds))
19

---

Table 5: Runtime analysis of different methods on sequences of length 64K and 128K.
64K
Prefilling (8)
KV update (s) Layer-wise KV update (ms)
Full
9.45
SnapKy
9.50
0.10
3.05
Ada-KV
9.88
0..43
13.28
AnDPro
10.04
0.58
18.13
128K
Prefilling (8)
KV update (S) Layer- wise K update (ms)
Full
28.78
SnapKV
29.00
0.11
3,42
Ada-KV
29.47
0.59
18.31
AnDPro
29.78
0.88
27.41
Although AnDPro introduces slightly higher update latency compared to SnapK and AdaK V, the additional overhead negligible relative to the total prefilling time.
We further conduct experiments using the Haystack (NIAH) benchmark. We measure the decoding latency (in seconds) for output length of IK under various input lengths (from 8K to 256K tokens) with budget size of 128. The results are in T
model on the Needle-in-a-
Table 6: AnDPro maintains comparable runtime efficiency AdaKV and remains close to SnapK V
across all input lengths.
Input Length
8K
16K
32K
64K
128K
256K
SnapK
35.10
34.72
37.15
40.49
39.40
53.69
AdaKV
39.22
38.99
39.64
43.39
44.23
55.30
AnDPro
39.23
38.67
40.44
42.98
44.20
55.51
C,5
Ablation Study
C.5.1 Ablation Study on inojection-Base Scoring Function
We conduct comprehensive ablation studies to isolate the effectiveness of the projection-base scoring function- which is the core contribution of this paper-and distinguish from the other components in our method. Specifically, scoring function (ProjScore) with the attention-ban based scoring function (AttnScore) with different combinations of other components. Specifically, consider five experimental groups A A-E:
conduct 5 sets of experiments to compare the mojection-basee
A: CrossHead + Chunk + FirstToken with ProjScore vs. AttenScore
Chunk + FirstToken with ProjScore vs. Pooling FirstToken with AttenScore
C: CrossHead + FirstToken with ProjScore vs. AttenScore
D: CrossHead Chunk with ProjScore CrossHead + Pooling with AttenScore
E: Isolated ProjScore vs. AttenScore comparison
We conduct these ablation studies on three datasets from the Single-Document QA task with the Mistral model. The results are in Table 7 and visualized in Figure The results demonstrate that the projection-based scoring function consistently outperforms the attention- scoring function, across all different configurations of other components.
We further validate this conclusion on two other based models Qwen and Llama. Table and Table show that AnDPro has good performance on other models, confirming both its effectiveness and robustness.
C.5.2 Ablation Study on Other Adopted Techniques
We further conduct ablation studies to investigate the contributions of three different components our algorithm: (1) merging tokens into chunks, (2) preserving the first token, and (3) cross-head budget allocation. The results are in Figure It visually compares the performance improvements contributed by each component to the project-based method, demonstrating that all components are indispensable for achieving the final higf-performance results.
20

---

Table 7: Ablation results of Distral--b-Instructt on LongBench (single QA Doc). The com- parisons demonstrate that ProjScore consistently outperforms AttnScore actoss different settings of adopted techniques, isolating the novel contribution of AnDPro.
Budget
Nrtvqa
Qasper
MF-en
Avg.
Nrtvqa
Qasper
MF-en
Avg.
CrossHead + Chunk + ForstToken + ProjScore
CrossHead + Chunk + Token +AtienScore
128
24.84
25.14
47.33
32.44
22.19
23.67
48.33
31.40
A
256
25.71
28.17
49.31
34.40
23.85
28.12
49.29
33.75
512
24.87
30.99
49.58
35.15
25.25
30.21
48.94
34.80
1024
25.87
32.54
49.35
35.92
25.94
32.45
49.02
35.80
Chunk + Fokes +ProjScore
Pooling
FirstToken
AttenScore
128
20.25
20.92
46.89
29.35
19.17
21.40
42.93
27.83
B
256
22.81
25.25
48.30
32.12
22.37
23.74
48.13
31.41
512
24.72
27.61
49.38
33.90
24.60
27.81
48.98
33.80
1024
26.09
30.75
49.20
35.35
25.47
29.57
49.33
34.79
Cross
Poken 4 PProSScore
CrossHeud
Token #AttenScore
128
22.78
24.98
47.39
31.72
21.12
21.16
38.46
26.91
C
256
24.32
27.41
48.49
33.41
21.50
23.50
40.38
28.46
512
25.64
29.03
49.09
34.59
23,93
24.67
43.08
30.56
1024
26.30
30.90
49.08
35.43
24.94
27.82
46.60
33.12
CrossHedd Chunk
+ProjSoore
CrossHead Pooling +AtinScore
128
24.90
24.47
48.57
32.65
21.64
23.77
46.48
30.63
D
256
24.92
28.25
49.21
34.13
23.29
26.32
48.99
32.87
512
26.18
30.20
49.41
35.26
24.73
28.59
48.84
34.05
1024
26.14
31.57
49.60
35.77
25.60
31.27
48.49
35.12
ProjScore
AttoScore
128
20.27
22.02
43.67
28.65
21.50
20.85
39.11
27.15
E
256
22.33
24.95
48.51
31.93
22.48
22.65
43.64
29.59
512
24.91
26.80
49.01
33.57
23.07
25.91
44.84
31.27
1024
25.20
30.02
49.25
34.82
25.02
29.48
47.25
33.92
Group A-Progoon Group A-AlteaSexee
Group B. ProfScore Group B.Minnooo
Grong C-ProoSoore Croup C-AtierSeee
Group D.Prs Group D-AlteBBoree
Group 55 ProfStore
Group S-AticaNone
35
Bodget
Figure 8: Ablation results of Mistrral7D--nsstrut---1. on LongBench (single QA Doc). The comparisons demonstrate that ProjScore consistently outperforms AttnScore across different settings of adopted techniques, isolating the novel contribution of AnDPro.
Our discoveries are as follows. (1) To achieve a better semantic succession, we merge a certain number of adjacent tokens one chunk. We test different chunk sizes C {1, 4, 16) on the three datasets from the Single-Doe Doc. QA task. The experiments are conducted on Mistral-7b-IIntmee v0.2. Results are in Figure IO As hyperparameter directly related to contextual semanties, we found that when the budget is small, smaller chunks will lead to better performance, and vice versa. In the main experiments, we set the chunk size to 4. (2) Following SnapKV and Ada-KV, we retain the first token by default. Results show that this leads to very slight performance gain. (3) We follow Ada-KV to allocate budget across all heads within each layer according their scores. The results show that this operator is critical to the overall performance gain. The integration of the
21

---

Table 8: Ablation results of Qwen2-7B-Instruct on LongBench (single QA Doc). The comparisons
demonstrate that ProjScore consistently outperforms AtinScore across different settings of adopted techniques, isolating the novel contribution of AnDPro.
Budget
Nrtvqa
Qasper
MF-en
Avg.
Nrtvqa
Qasper
MF-en
Avg.
CrossHead + Chunk + ForstToken + ProiScore
CrossHead + Chunk + First Token +AtienScore
128
23.95
35.67
44.72
34.78
21.69
35.07
45.74
34.17
A
256
22.52
39.90
46.20
36.21
24.25
39.16
46.87
36.76
512
21.52
43.93
46.74
37.40
22.96
43.32
46.02
37.43
1024
22.07
44.95
46.69
37.90
23.44
44.38
47.37
38.40
Chunk + FirstToken
+ProjScore
Pooling
FirstToken
AAttenScore
128
20.49
33.72
42.26
32.16
20.43
31.45
42.80
31.56
B
256
21.25
37.88
43.43
34.19
22.28
36.70
43.95
34.31
512
23.88
40.25
46.89
37.01
22.80
41.12
44.38
36.10
1024
23.40
42.24
46.51
37.38
24.58
43.55
46.95
38.36
ProjScorre
CrossHeud
FirsiToken
#AttenScore
128
21.84
35.04
44.64
33.84
17.07
32.11
39.11
29.43
C
256
22.30
38.72
44.31
35.11
23.36
36.89
43.24
34.50
512
25.02
43.50
47.55
38.69
22.43
40.82
42.02
35.09
1024
23.93
43.18
46.78
37.96
23.19
40.62
46.28
36.70
CrossHead Chunk
+ProjSoore
CrossHead Pooling +AtinScore
128
22.16
34.32
47.45
34.64
20.54
32.82
40.26
31.21
D
256
25.12
39.42
45.01
36.52
22.86
35.62
43.93
34.14
512
24.30
42.95
46.68
37.98
23.44
41.50
44.64
36.53
1024
24.56
45.52
45.71
38.60
23.75
42.82
47.91
38.16
ProjScore
AttuScore
128
21.32
33.44
41.42
32.06
19.40
30.84
34.30
28.18
E
256
21.67
36.45
45.76
34.63
21.34
31.67
38.96
30.66
512
24.02
41.40
44.30
36.57
21.68
34.55
39.60
31.94
1024
23.37
43.13
47.61
38.04
23.31
39.16
42.60
35.02
Avg. Score
34
Full Cache
AnoPro w/o Chunk
AnDPro FT
30
AnDPro w/o Cross head
AnDPro
Budget
Figure 9: Ablation Study on the adopted techniques.
aforementioned techniques results in the high performance of AnDPro. Notably, AnDPro outperforms full cache with a budget size & 2048.
22

---

Table Ablation results of Metta-Laama-3.-----nnnisst on LongBench (single QA Doc). The
comparisons demonstrate that ProjScore consistently outperforms AttnScore across different settings of adopted techniques, isolating the novel contribution of AnDPro.
Budget
Nrtvga
Qasper
MF--n
Avg.
Nrtvqa
Qasper
MF-en
Avg.
CrossHead
Chunk
FirscToken
ProjScore
CrossHend
Chunk
Foket AAttenSoore
128
26.66
38.22
54.54
39.81
27.19
38.01
53.13
39,44
A
256
27.28
42.09
54.72
41.36
26.36
41.94
54.77
41.02
512
28.03
44.25
55.61
42.63
29.12
44.86
54.86
42.95
1024
29.40
46.83
56.72
44.32
28.14
46.77
55.81
43.57
Chunk
+ First Loken +ProjScore
Pooling
First Token
AftenScore
128
24.87
32.33
52.51
36.57
25.54
31.40
50.99
35.98
B
256
27.04
38.52
54.21
39.92
26.92
38.19
52.62
39.24
512
27.24
42.18
54.25
41.22
28.40
41.52
55.40
41.77
1024
28.57
45.80
54.89
43.09
28.32
45.37
56.81
43.50
+ProjScore
+AttenScore
128
28.51
38.05
52.92
39.83
26.78
34.67
52.32
37.92
C
256
26.72
41.48
55.23
41.14
27.05
40.23
54.29
40.52
512
29.79
43.50
55.11
42.80
28.96
43.11
54.61
42.23
1024
31.48
45.54
56.75
44.59
29.98
46.06
55.32
43.79
CrossHead Chunk +ProjSoore
CrossHead + Pooling +AttnScore
128
30.13
37.46
54.01
40.53
25.06
34.50
52.27
37.28
256
29.70
42.56
55.59
42.62
27.04
39.24
54.41
40.23
512
31.08
44.48
55.62
43.73
26.92
42.68
55.20
41.60
1024
31.11
46.05
56.39
44.52
28.52
46.01
55.72
43.42
ProjScore
AttnScore
128
25.19
32.36
51.41
36.32
28.10
28.56
42.69
33.12
E
256
26.07
37.74
52.05
38.62
29.56
31.00
44.19
34.92
512
28.51
41.88
55.28
41.89
28.91
36.00
51.55
38.82
1024
27.75
45.54
56.22
43.17
29.51
40.70
54.31
41.51
310 0000
Cherk
Rollge
Figure 10: Comparison of experimental results with different chunk sizes on Single-Doc. QA
23

---

C.6 Different Choices of and b
Recall that our projection-based scoring function is defined in the form 8; a3 V; + 6). In this section, we investigate the effect of different choices of 0 and b. We conduct these experiments using QA task with the Mistral model.
Mistral-7B Distral-7B-Instructyyy Instruct-v2..00 on the datasets from the Single-Documen
To investigate the effect of the anchor direction 0, parameterize the anchor direction 8 with a temperature coefficient a. This generalization corresponds exactly
Σ a.U; where a; = Softmax(q" k; k;/a)) several cases: corresponds to the average all value vectors; an a - corresponds to the value vector with the highest attention weight. The results are in Table T0 demonstrating that setting the anchor direction as 0 y achieves robust performance.
proposed anchor direction 0
Σx= a,u, where à Table 10: Results of different choices of the anchor direction 0
Softmax(q k./a) with a temperature coefficient a. The used model is Mistral-7B-IIstruuttve and the dataset is LongBench (single QA Doc). The results demonstrate that setting the anchor direction as 0 y achieves robust performance.
Nrtvqa
Qasper
Mi--n
Avg.
Nrtvqa
Qasper Ml--n
Avg.
Budget=128
Budget=256
= (highest attention)
15.79
14.67
26.22
18.89
16.01
15.05
28.52
19.86
a 0.5
23.10
25.68
47.69
32.16
23.15
27.12
48.82
33.03
0 (0 3)
24.84
25.14
47.33
32.44
25.71
28.17
49.31
34.40
a 1.5
22.81
23.47
47.99
31.42
24.62
28.08
48.35
33.68
a = OC (average)
15.83
15.75
27.96
19.85
16.62
16.06
28.96
20.55
Budget=512
Budget=1024
(highest attention)
16.24
14.56
29.83
20.21
16.96
15.57
34.68
22.40
0.5
24.87
29.80
49.33
34.67
25.89
30.57
48.93
35.13
0
3)
24.87
30.99
49.58
35.15
25.87
32.54
49.35
35.92
1.5
25.13
30.34
48.14
34.54
25.81
31.57
49.64
35.67
00 (average)
16.81
17.62
33.50
22.64
17.11
21.56
38.68
25.78
We then investigate the impact of b, and the results are in Figure 11 We find that though careful is enough to derive a stable set = 0 in our main experiments, without the need for labor-intensive
choice of 6 promise lead to better results, simply setting performance. Therefore, hyperparameter tuning. Moreover, when b approaches infinity (e.g., 1000), the scoring function converges to attention-based based ones, and the performance approaches the performance of Ada-KV.
32.5
32.0
Scores
31.5
Ada-KV
AnDPro
31.0
Ada-KV Score 30.63
-10
-0.
-0.01
-1 06
040
denda...........................
De
03
0.01
100
Figure 11: Different choices of
24

---

C.7 Eviction Losses and Cosine Similarity
Figure 12 illustrates the eviction loss and cosine similarity derived from methods under different budget allocations, with the eviction loss quantified - The results show that AnDPro consistently yields lower eviction loss, and larger cosine similarity, which can some extend explain the high performance of AnDPro.
Lowe (Adl=())) Augs 0.55
Loses (Ani)Poo) Arg. 0.29
0.6
0.2
100
1225
150
175
200
Promus Stappo
1.0
Suallartty
0.7
Costne Sumtlority (Ada KV) Arg: 0.94
Coomee Simibbrity (Anl)Pro) Avg: 0.95
50
75
100
126
190
175
200
Pronge Sample
(a) Budget=128
0.7
KVV Arg:
0.6
Low (Anl3Pro) Aug:
0.3
25.
60
75
100
125
150
175
200
Proope Sample
1.00
Sinilrtty
Simillaitt (Aibe-V)) Ang.
Cooine Similacty (AaDDPro)
0.75
50
150
175
Promup Sample
(b) Budget=256
Figure 12: Comparison of eviction loss and cosine similarity. Experiments are conducted using 200 samples from the Qasper dataset.
25

---

C.8 Token Visualization
Figure 13 illustrates the distribution of our defined scoring functions across various layers (using Mistral7B BaedllBB-iiittttt instruct-v0.2 on a sample from the Qasper Dataset), demonstrating that the distribution exhibits a sparsity feature like that of attention weights.
Lower
Loper
Lear 18
Lawer 24
Figure 13: Visualization of Token Scores for Different Layers.
26

---

C.9 Value Vectors Visualization & Magnitude Histogram
We conduct two experiments intuitively explain why projection- based methods outperform attention-basse approaches. First, we provide the PCA visualization of value vectors in Figure [4 reveals that projection methods preserve geometrically critical tokens along the original output direction, minimizing post-eviction semantic drift. In contrast, attention-based selection disrupts the latent spatial distribution, causing divergent outputs. Second, complementary analysis in Figure [5] demonstrates significant variance of the vector vector magnitude. This indicates that the value vectors contain rich semantic information, which ignored in attention-bai baaiid approaches. This further underscores the necessity of projection-based strategies.
(a) Layer 4 Head 0
(b) Layer 8 Head 0
(c) Layer 9 Head 0
(d) Layer 11 Head
(c) Layer 12 Head
(f) Layer 14 Head
Layer 22 Head
(h) Layer 25 Head 0
Figure 14: The visualization of token value vectors and outputs of different approaches using PCA dimensionality reduction. We use an easy case with 23 tokens. Each dot represents token value vector, with color intensity (red hues) indicating attention scores. Tokens selected by different methods are highlighted by colored outer rings. Arrow vectors depict output directions. We visualize the results from the Head 0 across several layers. The results demonstrate that the projection based approach can achieve smaller distances between the pre- can post-eviction outputs by maintaining the semantical directions of the original outputs.
(a) Layer 0
(b) Layer
(c) Layer 16
(d) Layer 24
Figure 15: The distribution of the value vector magnitudes from several different layers in a test example. This reveals the significant variability and underscores the important semantic information captured by projection but overlooked by pure attention methods.
27

---

C.10
Case Study
We conduct case study on some simple test cases. We calculate the total scores of each token in the prefilling Phase based on the AnDPro and attention weights. Some results are presented in Figure T6 These token-level scores are scaled to the range of and sorted in descending order. Specifically, higher score indicates that the token is considered more important.
By observing the key tokens marked in red (identified by humans), AnDPro places better emphasis on the key tokens compared to the attention-based approach, thereby intuitively demonstrating the effectiveness of method.
AnDPro Mode
Attection Mode
seatoreed
alternioo( wenther acotyynned afternoanss) Whes
ifternoom/l
afeenionnal
shige
thas by
0.0
0.2
0.4
0.0
0.8
1.0
0.0
0.2
0.0
0.0
0.8
1.0
Stores
Scores
Prompt 1: There will be scattered showers this afternoon, clearing up by evening. What's 's the weather this afternoon?
AnDPM Modl
Attention Mode
Why Vere
Way changed The
poak the
rules b)
implemented sratiic by
trallic
homns
city
0.8
0.6
Stares
Scores
Prompt 2: The city implemented new traflic rules to reduce congestion during peak hours. Why were the traffic rules changed?
AnDPro Mode
Arsention Mode
wertie mainteeatcc tegin(b) deaited
547
mainte mepoeee toculaciy
bis
jo
die romming still
regalial there
Will
be
Scures
Scares
Prompt The train is delayed due to maintenance work, there still be buses running regularly. How the train service?
Figure 16: Case study. We visualize the importance orders given by different approaches, AnDPro, and attention-based approach. Red tokens are key tokens identified by humans.
28

---

C.11
Long Context
We have conducted additional experiments very long sequences using the Needle-in-a-Haystad benchmark, extending the test sequence length from the original 32K tokens up to 384K tokens. Specifically, the 1arma-..--8B-Instiii size of 128. Results are in Figure 17
model (pretrain context length 128K) under budget
The results demonstrate that AnDPro consistently achieves superior performance even long sequences. Notably, when sequence length exceeds 256K tokens, Full cache fails due to memory constraints, while AnDPro remains effective. Although all methods fail beyond 512K tokens, AnDPro maintains top performance within feasible length ranges.
Score
Scor 38 64
Usntect Lenglt
Contoct Langtt
(a) FullKV Score: 71
(b) Ada-KV Senee 48-4
Chedric Lonesh
Conker Lengh
(c) CriticalKV
(d) AnDPro
on the Needle-in saddle-in----e --yas-aa test with extremely long sequences (up to 384K). The x-axis represents the document's 's context length, and the y-axis indicates the depth of the needle insertion. Each square in the heatmap demonstrates the correctness of retrieving a proper sentence inserted in the context for given context length and insertion depth. The Average Score is calculated by averaging the sum of score with different insert depth across various context lengths. Gray squares indicate out-of-memon errors due to excessive context length.
Figure 17: Results of
C.12 Large-Sized LLMs
To evaluate the generalization and applicability of AnDPro on larger models, we conduct addi- tional experiments using the Owen2.5-32B-Inun Instructt model the LongBench single-document QA benchmark. The results are in Table II
Table 11: Results of Qwenn2.5-33B-Instrrue the LongBench single-document QA benchmark.
Budget= 128
Budget= 256
Budget= 512
Budget= 1024
Ada-KV
34.66
38.02
41.57
43.82
AnDPro
38.63
40.91
43.62
45.81
C.13 Long Decoding Tasks
To further demonstrate the broader applicability of our method, we conduct additional experiments on long decoding tasks, particularly in LLM reasoning settings. For better comparison with the baselines, we additionally implemented the decoding versions of AnDPro and SnapKV, V, while Ada- KV does not have decoding version. Specifically, evaluated our approach on the AIME24 dataset using DeepSeek-B -R --issiil-QWen..
Table 12 reports the reasoning performance (accuracy, %) under different KV cache budget settings. Table reports the throughput (tokens/s) and maximum supported batch size (OOM threshold) during 10K-token generation.
29

---

Table 12:
Performance (aceuracy. %) of different methods on the AIME24 dataset under KV cache budget settings (2K and 4K).
Budget= 2K
Budget= 4K
SnapKV AnDPro 60.00
50.00
53.33
63.33
Table 13:
Throughput (tokens/s) and maximum supported batch size (before out-of-memory occurs)
for different methods during 10K-token generation single GPU with 80GB of VRAM.
Generation Length Max Batch Size (OOM Threshold)
Throughput (token/s)
Full SnapKV
10K
28
181.09
10K
80
415.48
AnDPro
10K
80
413.15
D Limitation and Broader Impact
Limitation We have limited this work to the setting of uniform budget allocation across layers. remains to be investigated how to perform fine-grained budget allocation between layers, building upon existing studies that have demonstrated the varying importance of different layers.
Broader Impact Our methodology pioneers novel paradigm for KV Cache Compression by
incorporating directional characteristics value vectors (beyond attention weight exclusivity), which we believe will catalyze transformative breakthroughs in this field. Crucially, the proposed technique achieves substantial inference accelcration with only marginal performance degradation, establishing its deployment potential for edge computing scenarios and long-context sequence processing.
30

---

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: Our main contribution is to propose AnDPro, which is clearly described in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Appendix D
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
The proofs of all theorems can be found in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide necessary details to reproduce the results. We release our code at https://gi thub..b.aa. com wtt./oom///////. SELIRALLb-UUTCLLLAN AnDPro
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification: We use open-source, datasets and will release our code once the paper is accepted for publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https /mips..cc/pullc//uuui guwdes/ddee/eee Coc//ooodeeessseeeeeee hwtpibbmsssiioooooooiooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We follow the standard benchmarks and provide necessary details for all experiemnts.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We follow previous relevant works in the field to report experimental statistical information.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
33

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the information in Appendix 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in this paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have included broader impacts in Appendix D
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
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)?
Question:
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators or original owners of assets used in the paper are properly credited. The license and terms of use properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
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 paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
36

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: We have provided a detailed description of the use of LLMs in our method.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
37


Reviews:
[{"review_id": "NoeSAy4fgg", "reviewer": "Reviewer_Z3QZ", "summary": "This paper aims to design an improved scoring policy for KV cache eviction that leverages error in the output to identify the optimal KV cache set to retain. Their approach is complementary to existing KV cache compression strategies. They first present theoretical analysis for the assignment problem, demonstrating how an ideal method would select the optimal set to minimize the degradation in the output vector. They then propose a computationally efficient method that projects value vectors weighted by attention score onto anchor direction (the original unperturbed output) to better estimate token importance. Their approach leads to a reduction in accuracy degradation relative to existing KV cache approaches, without adding substantial noticeable inference efficiency overheads.", "questions": "- Is there any guarantee on how close the solution obtained through projection is to the optimal solution from the initial problem (P0-C or P1)?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- They present a novel strategy based on minimizing output degradation which leverages strong theoretical foundations to identify the optimal key set to retain.\n- They present a computationally efficient method for identifying the optimal key set to retain based on projecting the attention score-weighted value vectors onto an anchor direction (the original output vector). \n- They outperform a range of strong baseline methods (as evaluated on LongBench + Passkey Retrieval)\n- Their approach has low overhead for the Update KV phase, as highlighted in Appendix C.4.\n\nWeaknesses:\n- Their method is only applicable to compressing the prefill KV cache for generation. It is unclear whether the update step is fast enough to run online during generation.\n- They evaluate their method only on short decoding tasks (e.g. LongBench). Some analysis of performance on longer decoding tasks (e.g. LLM reasoning) would be useful for understanding the broader applicability of their method.\n- The KV cache merging method (which is similar to pooling) is not well justified - the ablations in C.5 are hard to follow. Some explanation of this approach (or empirical evaluation) would be helpful to support this, including a comparison between chunking and pooling methods as well as intuitive explanation for why this is helpful and superior to pooling.", "was_revised": true, "final_justification": "The author's response has addressed my main concerns around long generation tasks and the benefits of their chunking method. I will maintain my score of 4 as an overall positive assessment of the work.", "rebuttal": "Dear Reviewer Z3QZ,\n\nThank you for your insightful comments. We sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you consider raising your score.\n\n**Weakness 1 & 2. Online Eviction and Long Decoding Tasks.**\n\n> Their method is only applicable to compressing the prefill KV cache for generation. It is unclear whether the update step is fast enough to run online during generation.\n>\n> They evaluate their method only on short decoding tasks (e.g. LongBench). Some analysis of performance on longer decoding tasks (e.g. LLM reasoning) would be useful for understanding the broader applicability of their method.\n\n- Thank you for your valuable suggestions. We have **extended our approach to the decoding phase** and conducted additional experiments in the **reasoning scenario** that involves **long decoding**.  The details are as follows:\n\n  - **Online KV cache update mechanism.** We implemented an update mechanism specifically for the decoding stage, where the KV cache is dynamically compressed during token generation. Specifically, after every predefined number of decoding steps, we re-apply **AnDPro** to ensure that the size of the KV cache remains constant at the predefined budget size.\n\n  - **Long decoding reasoning task.**  Our method was originally designed for retrieval-oriented scenarios. To further demonstrate its broader applicability, we have conducted additional experiments under LLM reasoning settings.\n\n- We conduct experiments on the AIME24 dataset using the **DeepSeek-R1-Distill-Qwen-14B**. We report the  performance in **Table 1**, and the throughput and max batch size in **Table 2**. \n\n  Table 1: Performance (accuracy, %) of different methods on the AIME24 dataset under two KV cache budget settings (2K and 4K). The performance of the **full cache** method is **66.66**. Higher values indicate better reasoning performance. For a budget of 2k, the **KV cache update interval** is 1k, and for a budget of 4k, the **update interval** is 2k.\n\n  | **method** | **budget=2k** | **budget=4k** |\n  | ---------- | ------------- | ------------- |\n  | Snapkv     | 50.00         | 53.33         |\n  | Andpro     | 60.00         | 63.33         |\n\n  Table 2: Throughput (tokens/s) and maximum supported batch size (before out-of-memory occurs) for different methods during 10K-token generation. Larger batch size and higher throughput indicate better decoding efficiency.\n\n  | Method     | Generation Length | Max Batch Size (OOM Threshold) | Throughput (token/s) |\n  | ---------- | ----------------- | ------------------------------ | -------------------- |\n  | Full cache | 10k               | 28                             | 181.09               |\n  | SnapKV     | 10k               | 80                             | 415.48               |\n  | Andpro     | 10k               | 80                             | 413.15               |\n\n  The results indicate that **our method maintains strong performance and efficiency** even in reasoning-intensive long decoding scenarios.\n\n**Weakness 3.** **KV** **cache merging method.**\n\n> The KV cache merging method (which is similar to pooling) is not well justified - the ablations in C.5 are hard to follow. Some explanation of this approach (or empirical evaluation) would be helpful to support this, including a comparison between chunking and pooling methods as well as intuitive explanation for why this is helpful and superior to pooling.\n\nThank you for your valuable comments. In response, we provide the following clarifications and additional experimental analyses:\n\n- **Pooling** **Method as a Baseline** The pooling method was introduced as a baseline to encourage **similarity in attention scores among adjacent tokens**, thereby achieving a chunking-like effect during token selection. To illustrate the impact of pooling on token continuity, we conducted additional experiments using the SnapKV framework on the LongBench-Qasper dataset. We quantified the improvement in token continuity by measuring the **average continuity length**, computed as the total number of retained tokens (excluding the window size) divided by the number of separated token segments. The results are shown in Table 3.\n\n  Table 3:  Average consecutive length and task performance under different pooling kernel sizes, a larger pooling kernel size **increases the average consecutive length**.\n\n  | Pooling kernel             | 3     | 5     | 7     | 9     | 11    |\n  | -------------------------- | ----- | ----- | ----- | ----- | ----- |\n  | Average consecutive length | 6.17  | 8.99  | 11.33 | 13.29 | 15.04 |\n  | Result                     | 29.04 | 30.17 | 30.63 | 29.95 | 31.03 |\n\n- **Chunking Method with Attention–Value Guidance**\n\n  - Beyond pooling, we designed a **chunking method** based on our theoretical insights:\n  - The **anchor direction** is influenced not only by attention but also by **value vectors**, and considering only attention-based semantic consistency is insufficient.\n  - Directly pooling high-dimensional value vectors may lead to loss of directional information.\n  - Therefore, we propose a **chunk operation** that combines attention with value inner products. Specifically, token vectors within each chunk are aggregated by summation, leveraging the fact that adjacent tokens often exhibit strong semantic consistency in the value space. This design **preserves both the importance of attention and the directional information of value vectors**, while also reducing the computational cost of token selection.\n\n- To further analyze the impact of chunking on token continuity, we performed experiments under the AnDPro framework, where attention was already processed with the pooling method. The results are presented in Table 4:\n\n  Table 4:  Average consecutive length and task performance under different Chunk size, a larger chunk size **increases the average consecutive length**.\n\n  | Chunk size                 | 1     | 2     | 4     | 8     | 16    |\n  | -------------------------- | ----- | ----- | ----- | ----- | ----- |\n  | Average consecutive length | 5.99  | 10.25 | 15.39 | 23.37 | 36.13 |\n  | Result                     | 31.72 | 32.69 | 32.44 | 31.93 | 30.93 |\n\n**Question 1. Theoretical guarantee.**\n\n> Is there any guarantee on how close the solution obtained through projection is to the optimal solution from the initial problem (P0-C or P1)?\n\nThank you for your thoughtful question regarding the theoretical guarantee. Due to the **NP-hardness** of the combinatorial problem, we adopt a **heuristic projection-based scoring function**. While we do not provide a formal error bound at this stage, we **formulate KV cache eviction as an optimization problem**, grounded in convex analysis, which enables principled theoretical reasoning and future extensions. We will **investigate tighter theoretical guarantees** in future work.\n\n**Question 2. Presentation of Figure 5.**\n\n> For Figure 5, the decoding latency is hard to assess due to the large latency of the full KV cache baseline. It would be helpful to add a separate visualization comparing different eviction methods with the baseline KV runtime removed to better visualize the discrepancies between different methods.\n\nThank you for your valuable suggestion. We address your concerns as follows:\n\n- **Improved visualization.** In the revised version, we will add an additional visualization where the runtime of the full KV cache baseline is removed. This will allow for a clearer comparison among different eviction methods without being overshadowed by the large latency of the full KV baseline.\n\n- **Additional experiments.** We conducted further experiments using the **Mistral-7B-Instruct-v0.2** model on the **Needle-in-a-Haystack (NIAH)** benchmark. We measure the **decoding latency** (in seconds) was measured for an output length of 1K under various input lengths (8K–256K tokens) with a budget size of 128. The results are as follows:\n\n  Table5:  AnDPro maintains **comparable runtime efficiency** to AdaKV and remains close to SnapKV across all input lengths.\n\n  | input length | 8K    | 16K   | 32K   | 64K   | 128K  | 256K  |\n  | ------------ | ----- | ----- | ----- | ----- | ----- | ----- |\n  | SnapKV       | 35.10 | 34.72 | 37.15 | 40.49 | 39.40 | 53.69 |\n  | AdaKV        | 39.22 | 38.99 | 39.64 | 43.39 | 44.23 | 55.30 |\n  | AnDPro       | 39.23 | 38.67 | 40.44 | 42.98 | 44.20 | 55.51 |\n\n- **Efficiency analysis.** Despite incorporating a projection-based scoring function, **AnDPro exhibits runtime comparable to AdaKV** and only slightly slower than SnapKV. These results demonstrate that the additional computations introduced by AnDPro do not significantly affect overall decoding efficiency.\n\n- **Future optimizations.** We plan to introduce **engineering optimizations**, including:\n\n  - Parallelizing scoring computations with the prefilling operations, and\n\n  - Implementing optimized **CUDA** **kernels** for cross-head budget allocation.\n\n  These optimizations are expected to further reduce, or even eliminate, the minor additional overhead observed."}, {"review_id": "07pWVp6wqD", "reviewer": "Reviewer_iGUk", "summary": "The paper introduces AnDPro (Anchor Direction Projection), a novel method for improving Key-Value (KV) cache eviction in Large Language Models (LLMs). By proposing a projection-based scoring function, AnDPro aims to accurately measure token importance in the context of KV cache management, thus optimizing memory usage and inference latency. The authors argue that traditional methods relying on attention weights overlook spatial relationships between token value states in vector space, leading to suboptimal token selections. Through extensive experiments on 16 datasets from the LongBench benchmark, AnDPro demonstrates its effectiveness by maintaining high accuracy with significantly reduced KV cache budgets compared to state-of-the-art techniques.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths:\n1) AnDPro introduces an anchor direction projection technique that considers the spatial relationships within vector spaces, providing a more nuanced way to evaluate token importance beyond simple heuristics like attention weights, which is Innovative.\n2) The paper offers a thorough theoretical analysis, including derivations and propositions, which underpin the design of the proposed scoring function.\n\n### Weaknesses:\n1) The idea of considering value states in the vector space is excellent. However, given that random vectors in high-dimensional spaces are almost orthogonal, and the vector space of value states is a very high-dimensional space, have you observed whether the value state vectors are orthogonal? If they are nearly orthogonal, then the illustration in Figure 1 could be misleading because the anchor direction would almost be dominated by attention weights, thereby reducing the accuracy gains obtained by the proposed method. If they are not orthogonal, please provide experimental results.\n2) In the implementation, is the anchor direction updated during each forward pass of the LLM, and what is the associated computational overhead? Clarification is needed on whether the anchor direction is recalculated or updated during each forward pass of the LLM. The computational cost associated with this update should also be quantified to understand its impact on overall efficiency.\n3) Could the compressed KV cache mislead the anchor direction compared to its uncompressed state? If this is the case, then the practical effectiveness of AnDPro might deviate from the theoretical derivation presented in Section 3. \n4) Experiments were only conducted on Mistral-7B-Instruct-v0.2, which is insufficient to demonstrate that the method can generalize to other series of models or models of different sizes. Additionally, conducting evaluations in more scenarios (e.g., mathematical reasoning) to evaluate the impact of AnDPro would be beneficial.", "was_revised": true, "final_justification": "My recommendation is between borderline accept and accept.\n\nThe authors provided a strong rebuttal that resolved most of my key concerns.\n\nResolved: The new data on value vector non-orthogonality and the clarifications on computational overhead were convincing. The expanded evaluation on new models and a reasoning task has significantly strengthened the paper. I weigh these resolutions heavily.\n\nRemaining: The main weakness, now minor, is that the evaluation could still be more comprehensive. While much improved, results across a wider variety of benchmarks would make the claims more definitive.", "rebuttal": "Dear Reviewer iGUk,\n\nThank you for your insightful comments. We sincerely hope that our rebuttal could properly address your concerns.\n\n**Weakness 1. Orthogonality of value vectors.**\n\n> Given that random vectors in high-dimensional spaces are almost orthogonal, and the vector space of value states is a very high-dimensional space, have you observed whether the value state vectors are orthogonal?\n\nThank you for your suggestion. We highlight our key finding upfront: the value state vectors are not random and nearly orthogonal. Instead, they exhibit correlations. The details are as follows: \n\n- **Value state vectors are not nearly orthogonal---Cosine Similarity Analysis.** We computed the pairwise cosine similarity of 128-dimensional value state vectors extracted from multiple tokens, using the formula:\n$$\\text{cos\\\\_sim}(\\mathbf{v}_i, \\mathbf{v}_j) = \\frac{\\mathbf{v}_i \\cdot \\mathbf{v}_j}{\\|\\mathbf{v}_i\\| \\|\\mathbf{v}_j\\|}.$$\nThe results are in the follow table:\n\n   **Table 1:** Pairwise cosine similarity of 128-dimensional value state vectors extracted from five consecutive tokens (T0–T4). Higher similarity is observed between adjacent tokens (e.g., T1–T2, T2–T3).\n\n   | | T0 | T1 | T2 | T3 | T4 |\n   |-|-|-|-|-|-|\n   | T0 | 1 | | | | |\n   | T1 | -0.25 | 1| | | |\n   | T2 | -0.18 | 0.91 | 1  | | |\n   | T3 | -0.22 | 0.72 | 0.91 | 1 | |\n   | T4 | 0.06  | 0.48 | 0.67 | 0.82 | 1 |\n   \n   The results show that adjacent tokens exhibit relatively **high** **cosine similarity**, and the overall distribution significantly deviates from zero mean. This indicates that these vectors are not completely random and orthogonal but possess certain correlations and structural properties.\n\n- **Presence of low-dimensional semantic structure---PCA Cumulative Explained Variance** To further assess the structural properties of value vectors, we performed Principal Component Analysis (PCA) on the token value vectors. \n  \n  **Table 2:** Explained variance and cumulative variance of the top 10 principal components obtained by performing PCA on 128-dimensional token value vectors.\n   | PC| Explained Variance (%) | Cumulative Variance (%) |\n   |-|-|-|\n   | PC1  | 10.17 | 10.17 |\n   | PC2  | 10.05| 20.22 |\n   | PC3  | 6.46 | 26.67 |\n   | PC4  | 6.37 | 33.04 |\n   | PC5  | 4.19 | 37.23|\n   | PC6  | 4.13 | 41.36|\n   | PC7  | 4.09 | 45.45|\n   | PC8  | 3.89 | 49.35 |\n   | PC9  | 3.89 | 53.24|\n   | PC10 | 2.59 | 55.83|\n\n   The top 10 principal components (**approximately 20% of dimensions**) explain **over 55.8%** of the total variance. This demonstrates that value state vectors **exhibit pronounced low-dimensional linear correlations and encode semantic information**, rather than behaving as purely high-dimensional random noise.\n\n3. **AnDPro fully exploits these correlations.** Based on these findings, our method uses anchor projection to fully exploit the subtle yet **important correlations** in the value vectors. By integrating this with attention weight information, it achieves more accurate and robust information representation. Detailed theoretical analysis and supporting experimental evidence have been added in **Appendix C.6.**\n\n4. **Clarification of Figure 1.** In Figure 1, we illustrate the representation of tensors in a high-dimensional space.  Our method exploits the **subtle correlations present in the value vectors**, leveraging anchor projection to enhance the accuracy and robustness of information representation.\n\n**Weakness 2. Updated during forward pass.**\n\n> In the implementation, is the anchor direction updated during each forward pass of the LLM, and what is the associated computational overhead? \n\nThank you for your question. First, we would like to clarify that our method **by default** performs the anchor direction update **only once during the prefilling stage**, as it is primarily designed to handle long input scenarios efficiently. \n\nHowever, it can also be optionally applied **during the decoding stage** at specified steps to further maintain efficient memory utilization when necessary.\n\n- **Computational overhead.** As analyzed in **Figure 7 (Appendix C.4)**, we measured the additional time cost introduced by our approach. The measured runtime values are as follows (unit: seconds/milliseconds):\n\n   **Table 3:** Runtime analysis of different methods during prefilling on sequences of length 64K and 128K. Although AnDPro introduces slightly higher update latency compared to SnapKV and Ada-KV, the additional overhead is negligible relative to the total prefilling time.\n\n   | 64K    | Prefilling (s) | KV update (s) | Layer-wise KV update (ms) |\n   |-|-|-|-|\n   | Full| 9.45| - | - |\n   | SnapKV | 9.50 | 0.10 | 3.05 |\n   | Ada-KV  | 9.88 | 0.43 | 13.28 |\n   | AnDPro | 10.04 | 0.58 | 18.13 |\n\n   | 128K   | Prefilling (s) | KV update (s) | Layer-wise KV update (ms) |\n   |-|-|-|-|\n   | Full   | 28.78  | - | - |\n   | SnapKV | 29.00| 0.11| 3.42|\n   | Ada-KV  | 29.47 | 0.59 | 18.31 |\n   | AnDPro | 29.78 | 0.88 | 27.41 |\n\n   The results show that the additional computation introduced by the anchor direction update is **minimal and does not impact the overall decoding efficiency**.\n\n- **Performance and efficiency on decoding.** To further demonstrate the broader applicability of our method, we conducted additional experiments on **long decoding tasks**, particularly in **LLM reasoning** settings. For a better comparison with the baselines, we additionally implemented the decoding versions of AnDPro and SnapKV, while Ada-KV does not have a decoding version. Specifically, we evaluated our approach on the **AIME24** dataset using **DeepSeek-R1-Distill-Qwen-14B**.\n\n   - **Table 4** reports the **reasoning performance (accuracy, %)** under different KV cache budget settings.\n   - **Table 5** reports the **throughput (tokens/s)** and **maximum supported batch size** (OOM threshold) during 10K-token generation.\n\n   **Table 4.**  Performance (accuracy, %) of different methods on the AIME24 dataset under two KV cache budget settings (2K and 4K). The performance of the **full cache** method is **66.66**. Higher values indicate better reasoning performance. For a budget of 2k, the **KV cache update interval** is 1k, and for a budget of 4k, the **update interval** is 2k.\n\n   | **Method** | **Budget = 2K** | **Budget = 4K** |\n   | ---------- | --------------- | --------------- |\n   | SnapKV     | 50.00           | 53.33           |\n   | AnDPro     | **60.00**       | **63.33**       |\n\n   **Table 5.** Throughput (tokens/s) and maximum supported batch size (before out-of-memory occurs) for different methods during 10K-token generation on a single GPU with 80GB of VRAM. Larger batch size and higher throughput indicate better decoding efficiency.\n\n   | Method | Generation Length | Max Batch Size (OOM Threshold) | Throughput (tokens/s) |\n   | - | -| -| -|\n   | Full | 10K | 28 | 181.09 |\n   | SnapKV     | 10K | 80 | 415.48 |\n   | AnDPro     | 10K | 80 | 413.15 |\n\n   The results show that **AnDPro maintains strong reasoning performance under constrained budgets** and achieves **decoding efficiency comparable to SnapKV**.\n\n**Weakness 3. Anchor direction.**\n\n> Could the compressed KV cache mislead the anchor direction compared to its uncompressed state?\n\n- **Compute once**: During the **prefilling stage**, we first compute the anchor direction using the **uncompressed** value states and attention weights.\n\n- **Retain largest projections**: Tokens with the largest projections along this anchor direction are then selected, and only these tokens’ KV entries are retained.\n\n- **Fixed anchor direction**: After this one-time compression, the **anchor direction remains fixed** and is not updated during the decoding stage. The subsequent decoding process uses the compressed KV cache solely for efficient inference.\n\nBecause the anchor direction is derived from the **full, uncompressed KV cache**, the compression step does not introduce any bias or deviation from the theoretical derivation presented in Section 3.\n\n**Weakness 4. Experiments on more models with different sizes and more scenarios.**\n\n> Experiments were only conducted on Mistral-7B-Instruct-v0.2, which is insufficient to demonstrate that the method can generalize to other series of models or models of different sizes. Additionally, conducting evaluations in more scenarios (e.g., mathematical reasoning) to evaluate the impact of AnDPro would be beneficial.\n\nThank you for your suggestions. We have supplemented our experiments with additional results based on the LLaMA and Qwen model families, which are among the current mainstream architectures. The results demonstrate that AnDPro generalizes well across different model architectures.\n\nFurthermore, to comprehensively address your concerns, we conducted two additional sets of experiments:\n\n- **Different model scales.** We extended the evaluation to larger models by testing on Qwen2.5-32B-Instruct using the LongBench single-document QA benchmark. The results show that AnDPro maintains excellent performance at larger model scales.\n\n   **Table 6:** Performance on LongBench single-document QA benchmark using Qwen2.5-32B-Instruct. Results show that AnDPro consistently outperforms Ada-KV across different budget sizes.\n\n   | Method| Budget=128   | Budget=256   | Budget=512   | Budget=1024  |\n   |-|-|-|-|-|\n   | Ada-KV  | 34.66 | 38.02 | 41.57 | 43.82 |\n   | AnDPro | 38.63 | 40.91 | 43.62 | 45.81 |\n\n- **Reasoning scenarios.** We evaluated performance on reasoning tasks using reasoning models. Considering the longer outputs in such tasks, we optimized our implementation to perform online updates during decoding with a budget of 2K tokens and a step size of 1K tokens. The experiments in **Table 4** indicate that AnDPro also exhibits significant advantages in long-form reasoning scenarios such as mathematical reasoning.\n\nWe sincerely appreciate your thoughtful and insightful comments and kindly ask you to consider these updates during your further review."}, {"review_id": "9XqYFWl6T5", "reviewer": "Reviewer_PCLe", "summary": "This paper proposes AnDPro (Anchor Direction Projection), a new method for KV cache eviction in large language models (LLMs). Traditional methods often rely on attention weights to determine token importance, but these heuristics ignore the geometric structure of value vectors, potentially leading to suboptimal eviction decisions. AnDPro introduces a projection-based scoring function that measures the importance of each token by projecting its value vector onto an “anchor direction”—the direction of the pre-eviction output. The paper formulates the eviction process as an integer optimization problem and derives a relaxed convex formulation to inspire the design of the scoring function. Experimental results on two models (Mistral-7B and LLaMA3-8B) and across 16 tasks in LongBench and the Needle-in-a-Haystack benchmark demonstrate that AnDPro achieves superior accuracy and efficiency, maintaining over 96% of full-cache performance using only 3.44% of the cache.", "questions": "1. Can this method be extended to decoding phase? As it mainly focuses on the prefilling stage.\n2. What is the computational overhead of computing projections and scores per token? While the authors claim negligible latency, quantitative timing comparisons of the Update KV phase across methods would support the claim.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The authors model KV cache eviction as a constrained combinatorial optimization problem (P0-C), then relax it to a sparse convex problem (P1). This provides a mathematically grounded approach to derive a new scoring function based on the vector space geometry of the value states, rather than relying on attention weights alone.\n2. The authors evaluate AnDPro on two strong LLMs across diverse tasks and memory budgets, demonstrating consistent improvement over prior methods including SnapKV, Pyramid, Ada-KV, and CriticalKV. Notably, it achieves SOTA performance even at low memory budgets.\n3. They also provided a comprehensive analysis in the appendix.\n\nWeakness:\n1. The gap between the original non-convex objective (P0-C) and the relaxed convex form (P1) is not analyzed. Specifically, there is no theoretical or empirical discussion of how close the solution to P1 is to the true solution of P0-C.\n2. The reference of some methods, e.g. PyramidKV are missing.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer PCLe,\n\nThank you for your insightful comments. We sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you consider raising your score.\n\n**Weakness 1. Theoretical analysis.**\n\n> The gap between the original non-convex objective (P0-C) and the relaxed convex form (P1) is not analyzed. Specifically, there is no theoretical or empirical discussion of how close the solution to P1 is to the true solution of P0-C.\n\n- Our analysis follows a structured derivation path:\n  1. The transformation from **(P0-C) to (P0-R)** is a standard technique in traditional convex optimization, and when the penalty parameter $\\lambda$ is sufficiently large, the two formulations are **equivalent** in terms of support recovery.\n  2. The reformulation from **(P0-R) to Eq. (9)** is an **exact transformation**.\n  3. The relaxation from **Eq. (9) to (P1)** is a common and principled convex relaxation strategy that preserves the sparse structure and makes further analysis possible.\n- While the final relaxation (P1) does not always yield an exact solution to (P0-C), such a **relaxation is necessary** due to the **NP-hardness** of the original problem. Performing a precise theoretical gap analysis between (P1) and (P0-C) is thus **nontrivial** and remains an open challenge.\n- Importantly, our use of this relaxation serves as a **theoretical foundation** for deriving a **heuristic scoring function**, which is the core of our projection-based method. While we do not directly solve (P1), experiments show that the resulting heuristic performs **strongly in practice**, with low eviction loss and robust empirical results (Appendix C.7).\n\n**Weakness 2. Miss reference.**\n\n> The reference of some methods, e.g. PyramidKV are missing.\n\nThank you for pointing out the missing references. We will add the missing references, such as **PyramidKV**, to the **Related Work** section and ensure they are cited at their first mention in the revised manuscript.\n\n**Question 1. Extension to decoding phase.**\n\n> Can this method be extended to decoding phase? As it mainly focuses on the prefilling stage.\n\nThank you for your valuable question. While our method was originally designed for the **prefilling** stage, we have **explored its extension to the decoding phase**. For a better comparison with the baselines, we additionally implemented the decoding versions of AnDPro and SnapKV, while Ada-KV does not have a decoding version.\n\nWe conduct experiments on the AIME24 dataset using the **DeepSeek-R1-Distill-Qwen-14B**. We report the  performance in **Table 1**. \n\nTable 1: Performance (accuracy, %) of different methods on the AIME24 dataset under two KV cache budget settings (2K and 4K). The performance of the **full cache** method is **66.66**. Higher values indicate better reasoning performance. For a budget of 2k, the **KV cache update interval** is 1k, and for a budget of 4k, the **update interval** is 2k.\n\n| **Method** | **Budget=2k** | **Budget=4k** |\n| ---------- | ------------- | ------------- |\n| Snapkv     | 50.00         | 53.33         |\n| Andpro     | 60.00         | 63.33         |\n\nThe results show that **AnDPro maintains high inference accuracy** despite the additional computations introduced during decoding.\n\n**Question 2. Computational overhead.**\n\n> What is the computational overhead of computing projections and scores per token? While the authors claim negligible latency, quantitative timing comparisons of the Update KV phase across methods would support the claim.\n\nThank you for raising the question regarding the computational overhead of per-token projection and scoring. To ensure decoding efficiency, our method does **not** perform eviction at every decoding step. Instead, **the update is executed only once during the prefilling stage**, which significantly reduces runtime overhead.\n\nAs analyzed in **Figure 7 (Appendix C.4)**, we measured the additional time cost introduced by our approach. The measured runtime values are as follows (unit: seconds/milliseconds):\n\nTable 2: Runtime analysis of different methods during prefilling on sequences of length **64K** and **128K**. Although AnDPro introduces slightly higher update latency compared to SnapKV and AdaKV, the additional overhead is **negligible relative to the total prefilling time**.\n\n| 64K    | Prefilling (s) | KV update (s) | Layer-wise KV update (ms) |\n| ------ | -------------- | ------------- | ------------------------- |\n| Full   | 9.45           | --            | --                        |\n| SnapKV | 9.50           | 0.10          | 3.05                      |\n| AdaKV  | 9.88           | 0.43          | 13.28                     |\n| AnDPro | 10.04          | 0.58          | 18.13                     |\n\n| 128K   | Prefilling (s) | KV update (s) | Layer-wise KV update (ms) |\n| ------ | -------------- | ------------- | ------------------------- |\n| Full   | 28.78          | --            | --                        |\n| SnapKV | 29.00          | 0.11          | 3.42                      |\n| AdaKV  | 29.47          | 0.59          | 18.31                     |\n| AnDPro | 29.78          | 0.88          | 27.41                     |\n\nThe results confirm that the additional computation introduced by the anchor direction update is **minimal and does not impact the overall decoding efficiency**. These findings are also discussed in the revised manuscript, where we clarify that our method maintains runtime performance comparable to existing baselines."}, {"review_id": "DpQgRWIrMG", "reviewer": "Reviewer_qyz2", "summary": "This paper proposes AnDPro, a novel KV cache eviction method for efficient LLM inference. Unlike prior approaches that rely solely on attention weights to measure token importance, AnDPro leverages the geometric relationships between token value vectors in the embedding space. It introduces a projection-based scoring function, where token importance is quantified by projecting value vectors onto an anchor direction. Evaluated on 16 LongBench datasets, AnDPro achieves 96.07% of full-cache accuracy using only 3.44% of the KV cache budget.", "questions": "Q1: What would AnDPro perform on larger-sized LLMs (e.g., 32B, 70B)?\nQ2: What is the specific computational overhead of AnDPro? How does AnDPro’s overhead compare to the overhead of existing methods?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S1: The theoretical analysis is novel and solid.\n\nS2: The experimental comparison is comprehensive.\n\nS3: The writing of this paper is easy to follow.\n\nW1: The evaluation is only conducted on relatively small-sized LLMs.\n\nW2: The specific computational overhead of AnDPro is not provided.", "was_revised": true, "final_justification": "Thanks for the author's rebuttal, and I maintain the original positive rating.", "rebuttal": "Dear Reviewer qyz2,\n\nThank you for your insightful comments. We sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you consider raising your score.\n\n**W1 & Q1: Large-sized LLMs.**\n\n> W1: The evaluation is only conducted on relatively small-sized LLMs.\n>\n> Q1: What would AnDPro perform on larger-sized LLMs (e.g., 32B, 70B)? \n\nThank you for your interest in the scalability of our approach. To evaluate the **generalization and applicability** of AnDPro on larger models, we conducted additional experiments using the **Qwen2.5-32B-Instruct** model on the **LongBench single-document QA** benchmark.\n\n| Method | Budget=128 | Budget=256 | Budget=512 | Budget=1024 |\n| ------ | ---------- | ---------- | ---------- | ----------- |\n| Ada-KV | 34.66      | 38.02      | 41.57      | 43.82       |\n| AnDPro | 38.63      | 40.91      | 43.62      | 45.81       |\n\nThe results in the table above clearly indicate that across all tested average per-layer per-head computational budgets (from 128 to 1024), **AnDPro** consistently outperforms **Ada-KV**. This demonstrates that our method successfully generalizes to **larger-scale models** while maintaining its superior performance.\n\nWe will include the **detailed results and analysis** in the final version of the paper. \n\n**W2 & Q2. Computational overhead.**\n\n> W2: The specific computational overhead of AnDPro is not provided.\n>\n> Q2: What is the specific computational overhead of AnDPro? How does AnDPro’s overhead compare to the overhead of existing methods?\n\nThank you for your detailed question. To ensure decoding efficiency, our method does **not** perform eviction at every decoding step. Instead, **the update is executed only once during the prefilling stage**, which significantly reduces runtime overhead.\n\nAs analyzed in **Figure 7 (Appendix C.4)**, we evaluated the runtime overhead of our method. To provide a more detailed quantitative breakdown, the specific runtime measurements are presented below (unit: seconds/milliseconds):\n\n| Input Length 64K | Prefilling (s) | KV update (s) | Layer-wise KV update (ms) |\n| ---------------- | -------------- | ------------- | ------------------------- |\n| Full             | 9.45           | --            | --                        |\n| SnapKV           | 9.50           | 0.10          | 3.05                      |\n| Ada-KV            | 9.88           | 0.43          | 13.28                     |\n| AnDPro           | 10.04          | 0.58          | 18.13                     |\n\n| Input Length 128K | Prefilling (s) | KV update (s) | Layer-wise KV update (ms) |\n| ----------------- | -------------- | ------------- | ------------------------- |\n| Full              | 28.78          | --            | --                        |\n| SnapKV            | 29.00          | 0.11          | 3.42                      |\n| Ada-KV             | 29.47          | 0.59          | 18.31                     |\n| AnDPro            | 29.78          | 0.88          | 27.41                     |\n\nThe results show that while **AnDPro's KV update stage** takes slightly longer than **SnapKV** and **Ada-KV**, this overhead is **negligible** when compared to the total **Prefilling** time. Therefore, the results quantitatively confirm that the additional computation from our method is **minimal and does not impact the overall decoding efficiency**."}, {"review_id": "rIh2agqoxM", "reviewer": "Reviewer_AuWV", "summary": "This paper proposes AnDPro (Anchor Direction Projection), a novel KV cache eviction strategy for large language models that goes beyond traditional attention-weight-based heuristics by incorporating geometric information from value vectors. It defines token importance via a projection-based scoring function, $\\( s_i = a_i \\cdot y^\\top v_i \\)$, where $\\( y \\)$ is the pre-eviction output direction. This approach is derived from a sparse optimization formulation and efficiently implemented with support for cross-head cache budgeting. Experiments on LongBench and Needle-in-a-Haystack benchmarks show that AnDPro outperforms prior methods, achieving 96.07% of full-cache accuracy using only 3.44% of the cache, reducing memory by up to 46% without quality loss.", "questions": "1. How is y computed in Section 3.4? Is it computed with KV cache in the local window and what is the window size? Do you compute y before each step of generation?\n2. Do different attention heads select the same tokens to keep? Or they can choose to preserve different tokens?\n3. Will the evicted token be permanently deleted from the KV cache? Or they can still be selected and attended to at future generation steps?\n4. What is the chunk size in Section 3.4?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "[Strengths]\n1. The paper proposes a novel projection-based token importance score  $\\( s_i = a_i \\cdot y^\\top v_i \\)$​, incorporating value vector geometry beyond attention weights.\n2. The paper provides comprehensive theoretical analysis/proof and intuitive explanation for the proposed method.\n3. The authors evaluate the proposed method across different accuracy benchmarks with a wide range of LLMs, demonstrating the effectiveness of their optimizations, achieving 96.07% of full-cache accuracy using only 3.44% of the cache, reducing memory by up to 46% without quality loss.\n\n\n[Weaknesses]\n1. The discussion of implementation details should be improved.", "was_revised": true, "final_justification": "My questions have been well resolved by the authors' rebuttal. And I will keep my original recommendation.", "rebuttal": "Dear Reviewer AuWV,\n\nThank you for your insightful comments. We sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you consider raising your score.\n\n**Weakness 1：The discussion of implementation details should be improved.**\n\nWe respond to the questions regarding implementation details as follows, and we will provide a more detailed description in the revised manuscript. Please let us know if you have any further questions.\n\n**Question 1. How is $y$ computed?**\n\n> How is $y$ computed in Section 3.4? Is it computed with KV cache in the local window and what is the window size? Do you compute $y$ before each step of generation?\n\nWe clarify the calculation process as follows:\n\n- **Definition of $y$:** The vector y is an attention output calculated as the **weighted sum** of all **value vectors ($v_i$)**, using the corresponding **attention scores ($a_i$) as weights**.\n- **Use of Local Window:** In the local window computation, we calculate the vector y by performing an attention operation between the **queries**  from the **window** and the **full KV cache** that covers all historical information. The local observation window size used in our experiments is **32**.\n- **Timing of Computation:** Our method **computes and applies y only once during the prefilling stage**, i.e., immediately after the context is filled. During the subsequent **decoding** phase, the model directly uses the **pre-selected important tokens** without recomputing $y$ at each generation step.\n\nSince y is derived exclusively from the **uncompressed KV cache** within a fixed local window during prefilling, and remains fixed during decoding, its computation does not incur additional per-step cost in the generation process.\n\n**Question 2: Do different attention heads select the same tokens to keep**\n\n> Do different attention heads select the same tokens to keep? Or they can choose to preserve different tokens?\n\nThank you for raising this detailed question.\n\n During the pre-filling stage, each attention head **independently** selects important tokens based on its own computed attention scores. We employ an anchor projection method to process all heads in parallel, allowing each head to adaptively choose **different numbers and positions of tokens** according to its specific function and attention patterns.\n\nThis design enables each head to fully leverage its distinct role rather than being constrained by a unified selection strategy, thereby enhancing the model’s ability to capture critical information and improving overall reasoning efficiency.\n\n**Question 3.**\n\n> Will the evicted token be permanently deleted from the KV cache? Or they can still be selected and attended to at future generation steps?\n\n- **Permanent Eviction**\n  -  To maintain a minimal memory footprint, we exclusively retain the **Key-Value** pairs for the tokens that are selected. This means that any token evicted from the **KV cache is permanently discarded** and cannot be accessed or attended to in any subsequent generation steps.\n  -  Our experimental results validate this strategy, demonstrating that by keeping only about **3.44%** of the original KV cache, we can still preserve approximately **96%** of the model's generation performance. This highlights our method's ability to achieve significant cache compression with negligible impact on quality.\n\n> What is the chunk size in Section 3.4?\n\n- **About Chunk Size**\n  -  The primary motivation for our chunking operation is to preserve **local semantic continuity**. By grouping adjacent tokens, which are typically semantically related, we ensure that our selection mechanism evaluates local contextual information as **a coherent unit** rather than as isolated tokens. It is also worth noting that because our method incorporates information from the **value states**, merely applying **pooling techniques** to the attention scores (as in methods like **SnapKV**) is insufficient for effectively enhancing the continuity of the selected tokens. **To address this, we designed a chunk operation that combines attention and value inner products, specifically by summing the weighted vectors corresponding to tokens within a chunk.** This approach effectively overcomes the aforementioned limitation.\n  -  In our experiments, we set the chunk **size to 4**. **Appendix C.5.2** presents the impact of different chunk sizes on the experimental results."}]

Author rebuttal:

Meta-review: This paper introduces AnDPro, a projection-based scoring function for KV cache eviction in LLMs. The method is novel and mathematically grounded, going beyond attention-weight heuristics by leveraging value vector geometry. Extensive experiments on LongBench, Needle-in-a-Haystack, and reasoning tasks demonstrate strong and consistent improvements over SnapKV, Ada-KV, and other baselines, with minimal overhead. The authors also provided thorough rebuttals with larger-scale evaluations, runtime analyses, and detailed clarifications on orthogonality, anchor computation, and chunking. While some theoretical gaps remain (e.g., relaxation analysis), the contribution is technically solid and impactful. I recommend acceptance.
Decision: Accept (poster)