MPCache: MPC-Friendly KV Cache Eviction for Efficient Private LLM Inference
Authors: Wenxuan Zeng
Ye Dong
Jinjin Zhou
Jin Tan
Lei Wang
Tao Wei
Runsheng Wang
Meng Li
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Model
KV Cache Compression
Sparse Attention
Private Inference
Multi-party Computation
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Private large language model (LLM) inference based on secure multi-party computation (MPC) achieves formal data privacy protection but suffers from significant latency overhead, especially for long input sequences. While key-value (KV) cache eviction and sparse attention algorithms have been proposed for efficient LLM inference in plaintext, they are not designed for MPC and cannot benefit private LLM inference directly. In this paper, we propose an accurate and MPC-friendly KV cache eviction framework, dubbed MPCache, building on the observation that historical tokens in a long sequence may have different effects on the downstream decoding. Hence, MPCache combines a look-once static eviction algorithm to discard unimportant KV cache and a query-aware dynamic selection algorithm to activate only a small subset of KV cache for attention computation. MPCache further incorporates a series of optimizations for efficient dynamic KV cache selection, including MPC-friendly similarity approximation, hierarchical KV cache clustering, and cross-layer index-sharing strategy. Extensive experiments demonstrate that MPCache consistently outperforms prior-art KV cache eviction baselines across different generation tasks and achieves 1.8 ~ 2.01x and 3.39 ~ 8.37x decoding latency and communication reduction on different sequence lengths, respectively.

MPCACHE: MPC-Friendly KV Cache Eviction For Efficient Private LLM Inference
Wenxuan Zeng', Ye Dong", Jinjin Zhou², Jin Tan Lei Wang
Tao Wei Runsheng Wang', Meng Li
Peking University National University of Singapore 3 Ant Group zux. 2wx. andy@atu pww.uapppuueeeee en, meng. wog.l1@ppar wit.ku..ueuu...
Abstract
Private large language model (LLM) inference based on secure multi-party compu- tation (MPC) achieves formal data privacy protection but suffers from significant latency overhead, especially for long input sequences. While key-value (KV) cache eviction and sparse attention algorithms have been proposed for efficient L.LM inference in plaintext, they are not designed for MPC and cannot benefit private LLM inference directly. this paper, we propose an accurate and MPC-friendly KV cache eviction framework, dubbed MPCACHE, building on the observation that historical tokens in a long sequence may have different effects on the downstream decoding. Hence, MPCACHE combines a -ock-once static eviction algorithm to discard unimportant KV cache and query-aware dynamic selection algorithm activate only small subset of KV cache for attention computation. MPCACHE fur- ther incorporates a series of optimizations for efficient dynamic KV cache selection, including MPC-friendly similarity approximation, hierarchical KV cache cluster- ing. and cross-layer index-sharing strategy- Extensive experiments demonstrate that MPCACHE consistently outperforms prior-art KV cache eviction baselines across different generation tasks and achieves 1.8 2.01x and 3.39 8.37 x decoding latency and communication reduction different sequence lengths, respectively. The code can found here
Introduction
Large language models (LLMs) have recently demonstrated remarkable ability in a wide range of
applications such as document summarization 32 57 86), question answering 33 15 80 and dialogue systems 669
68). However, LLM- based machine learning as a service (MLaaS) on the cloud has raised serious privacy concerns the users are required to upload their prompts to the cloud, which may contain sensitive personal information. Mcanwhile, the service provider is unwilling to offload the trained model to the user to protect the proprictary model weights. In recent years, secure multi-party computation (MPC)-based LLM inference has become a prevailing and mainstream research trend to address privacy concerns [53] [9 25 60 62 94 48), which enables the users and the cloud to conduct the LLM inference jointly, but nothing else can be derived beyond the final inference results.
However, MPC-based L.LM inference illustrated in Figure Ta) faces serious efficiency challenges, especially for long sequences. We profile the decoding efficiency of GPT-2 with the Secretflow framework (55) using recent 2-party computation (2PC) (53) and 3-party computation (3PC) protocols [9] As can be observed in Figure b]) and (c), attention computation dominates the latency and communication for both 2PC and 3PC protocols. Moreover, Softmax accounts for the majority of the
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Aneetion
MLP
Lager
Siifarty Appeot.
Topuo Ronking
Token Gafteriig
(A) MPC Inference
(b) Breakdown Transformer
(e) Softmax with Seq. Lengths
(d) Challenge of KV Cache Eviction
+0uppul
Lak. 6) Comm. (MB)
MPC Protocals
N00
Laner
Sey, Longa
Fatra Cod
MPC Protocols
Laper
Protecols
[g)
Laper
64
06
206
40%
60%
50%
100%
10
20
60
70
6
16
Proportion
Comm. (MI3)
Inference Cost
Figure 1: (a) MPC-based LLM inference. (b) Breakdown of decoding latency and communication with a sequence length 512. Attention dominates the overhead for both 3PC and 2PC protocols. (c) The cost of Softmax scales with the sequence length rapidly. (d) Inference cost before and after KV cache eviction. Blocks in slash indicate the extra overhead introduced by eviction.
overall cost due its complex operators including max, exponential, and division, especially with an increasing sequence length.
To reduce the cost of private LLM inference, previous works focus on developing more efficient
MPC protocols [53]
19 60, BT] replacing non-linear activation functions with more MPC-friendly directly modifying the model architecture [62] However, they still incur sigmificant overhead or require expensive finetuning or re-training, and cannot be directly applied to LLMs. Another line of works leverages key-value (KV) cache eviction (sparse attention) reduce the number of tokens involved the attention computation [91] 22
operators 48
40
34
50
93
89 20 Although they have
demonstrated significant memory and computation reduction for plaintext LLM inference without the need of finetuning, they are not friendly to MPC. As shown in Figure dd),, directly applying the
dynamic KV cache eviction algorithm [ incurs even more communication and latency overhead over the baseline model since it introduces expensive operators in MPC, including top-k ranking, token gathering, etc, elaborated in Section Therefore, there is an urgent need for a training-free MPC-friendly algorithm designed for private LLM inference.
To overcome the heavy overhead of attention computation, make the following observations that motivate our MPCACHE: 1) LLM attention maps are overall sparse for long input prompts, motivating to perform static eviction and directly prune the KV cache of unimportant tokens; 2) LLM attention shows token-wise locality (49,, motivating us to build an efficient clustering algorithm for dynamic selection of the KV cache; 3) LLM attention of adjacent layers shows similar patterns, motivating us to share the KV cache selection for adjacent layers to further improve efficiency. Our contributions can be summarized as follows:
We observe the cost of MPC-based LLM inference mainly comes from attention computation and propose MPCACHE, an MPC-friendly KV cache evietion framework to reduce the LLM inference latency and communication.
We identify the challenges when applying KV cache eviction to MPC. To tackle the problems, MPCACHE combines look-once static eviction and query-aware dynamic selection with series of optimizations, including MPC-friendly similarity approximation, hierarchical KV cache clustering, and cross-layer index-sharing strategy.
With extensive experiments, we demonstrate the performance of MPCACHE consistently exceeds the prior-art KV cache eviction algorithms across different generation tasks and achieves up to 2.01x and 8.37x decoding latency and communication, respectively.
2 Problem Formulation and Background
2.1 Problem Formulation
Generative LLM inference can be divided into prefill and decoding stages (refer to Appendix A.3)
We formally describe the decoding process with KV cache eviction in Algorithm [ eviction policy, denoted as P, aims to minimize the attention computation by only preserving subset of tokens, which typically involves three steps: 1) P first computes the similarity between the query and key cache of previous tokens (line # I); 2) P then ranks the previous tokens based
The KV cache

---

Table 1: Qualitative comparison with prior works of attention optimization.
Representative
Work
Category
Token Similarity
Approximation
Top-é Ranking
Token Gathering
Layer-wise Optinization
MPC Emtieiecy
Performance
Model
Truining
Impractical
80
Approximation
Required
LLM
25 82 7M
Learning-hused
Required
Training
High
76 1H 02
Fixol-pailem
High
Accumulated
Usually
Token- Token wise
High
Dymamic
Tokeo wise Similarity
Token wise & Stap- wise
Low
High
MPCACHE (xurs)
Static Dynamii
Cluster Similarity
Hierarchical Clustering
Claster-wise & Step-wise
Choster-wie
Cross layer Index-sharing
High
High
on the similarity score and applies the top-k algorithm to determine the indices relevant tokens
(line # 2); 3) the KV cache is then retrieved based on the indices, denoted as token gathering (line #
3 followed by sparse attention computation with the selected KV cache (line # 4). To compute the similarity in line 1, existing works have used accumulated attention score of the historical tokens
55
9 93
78
89
or cosine similarity [47 [4].
KV cache eviction reduces the attention computation complexity from ((dd) (kdd) where T, d denote the sequence length and embedding dimension, respec- tively, and < T. However, it introduces! 1 sim Sim(q. K):
Algorithm 1: Formulation of KV cache eviction
Input : Query, key, and value cache q, K, V. :utput:Sparte attention output O
Similarity approx.
MPC-unfriendly operations, including sim-2 idx = topk(sim, k k));
Top-k ranking
ilarity approximation, top-k ranking, and a K', V K-gatherjip (axther(ixx,, V V.gather fidx]; token gathering, hindering its benefits in 4
Gathering
Softmax(q K'T /vd) V/; Sparse attention
MPC-based LLM inference. Hence, the return O. goal of this work can be summarized follows: "How can we design an MPCC-frienll KV cache eviction algorithm P to minimize MPC-based LLM inference overhead without sacrificing LLM performance?"
2.2 Background
KV cache eviction. There has been surge in improv- ing the efficiency of private LLM inference. Existing works focus the protocol optimization [60, 19 53
6 Head 20
Head
or replacing non-linear functions with MPC-friendly
ICC (Doamnicll Scleded
operators [40]
18] However, they either incur
[bunmisl
large overhead for long sequences or require expen- sive training. KV cache eviction has been widely explored for plaintext inference and can be mainly classified into 3 categories: 1) fixed-pattern algo- rithms like 76 33 always keep the tokens in the same position, e.g., initial and recent tokens across decod- ing steps. lacking flexibility for different LLMs and contexts; 2) static algorithmss like [9]] 42 22 discard
LEA Jakees
(Suiieall Exirted)
tokens based on the accumulated attention scores of historical tokens, which are efficient but suffers from large performance degradation when the compression ratio is high; 3) dynamic algorithms like 77 67 (29
Figure (Upper) token types in atten- tion maps where / means the token is se- lected and X means the token is not selected. (Lower) three types can be observed in atten- tion map with more tokens.
compute the similarity between the current query and key cache for every decoding step, which is more ac-
curate but requires repetitive token selection at each step. Recently, there are learning- beaniigg-based methods [75 which rely on the training process. Different from prior works in Table I MPCACHE is a training-free and hybrid method and equipped with MPC-friendly optimizations, simultaneously achieving high efficiency and performance. We leave a detailed review of existing works in Appendix A
We describe the procedure and protocol of token gathering in Appendix B.4

---

MPC and threat model. MPC [24 is a cryptographic technique recently developed to enable LLM inference while protecting the privacy of both data and model, as shown in ( an MPC framework, to protect a certain tensor, it is often split into multiple secret shares and distributed across different parties involved in the computation 53 19 56 31 We adopt an conest-but-curiote threat model and apply MPCACHE to both 2PC and 3PC protocols, which involve 2 parties and 3
parties in the computation, respectively. We refer interested readers to Appendix B where the threat model and underlying protocols are more clearly explained.
3 Motivations and Challenges
In this section, we discuss the key observations that motivate the design of MPCACHE.
Observation 1: the attention map of a long input sequence is usually sparse, and the KV cache of historical tokens demonstrates different impacts over the downstream decod- ing. We show the attention map of different heads and lay- of ALLMMA22-7B in Figure 2
Relattve Performaee (56)
1000
Full Cadie
Contibbuted (59)
100
Hoald Moce
Commonality Score
0
80
60
0:52
Longle
40
-20%
0.4
-00
Seg Longte
20
impurtaane
Congta
20
40
60
30
100
5 10 15 20 25
30
8
12
Statle Eviction Ratio
Layer Index
d'Ajjacett Layers
and leave visualizations of larger attention maps in Appendix C
Motivation
Motivation
(c) Cross-layer Commonality
Static Eviction
Dynamic Selection
From Figure 2 we can classity different tokens into categories: 1) important to all tokens (IA in red box): the attention scores re- main high for the entire column, e.g., Oth and 1st columns in Figure 2a)). indicating these tokens are important for the generation of all downstream tokens and hence, need to be always preserved: 2) un in-important to all tokens (UIA in blue box): the attention scores remain low for the entire column, e.g., 2nd and 3rd columns in Figure 2[a,, indicating these tokens can be discarded without impacting the downstream decoding; 3) important to certain tokens (IC orange box): the attention scores vary for different tokens, e-g., 4th and 5th columns in Figure [[ [), indicating these tokens impact a subset of downstream tokens, and hence, cannot be directly pruned.
Figure 3:
Motivating inspirations. (a) Statically evicting 60% tokens during the prefill stage still maintains the performance; (b) less than 20% tokens contribute decoding: (c) cross-layer commonality among different numbers of adjacent layers.
We verify the observations on LLaMA-2-7B with different input sequence lengths. As shown in Figure a),, almost 60% tokens can be statically evicted while preserving the LLM performance. While further pruning the remaining tokens starts to degrade the LLM performance. as shown in Figure 3b) in each decoding step. only less than 20% of the remaining tokens contribute to the decoding. The above observation motivates us to statically evict the KV cache of UIA tokens and dynamically select a subset of IC tokens at each decoding step.
Observation 2: dynamic KV cache selection incurs non-negli overhead in MPC. While dynamic KV cache selection is accurate and reduces the attention computation cost, it incurs non- negligible overhead due to MPC-unfriendly operations. In Figure dd), we show the extra overhead when 5% tokens are dynamically selected. The MPC-unfriendly operations mainly include:
Similarity computation (Algorithm I line # 1): cosine similarity is widely used, which requires computing the multiplication between the current query with the key cache of all previous tokens;
Top-k ranking (Algorithm line # 2): to compute the indices of relevant tokens, top-k is usually inevitable [91 22 93.. Unlike plaintext inference, top-k ranking in MPC involves
frequent comparison protocol, which incurs high latency and communication cost [3]
Token gathering (Algorithm I line # 3): after the top-k ranking, the KV cache of selected tokens is gathered based on the indices. Unlike plaintext inference, such gathering protocol in MPC is much more expensive since both KV cache and indices are ciphertexts. Therefore, each index is first converted to a one-hot vector and then
as described in Algorithm 2 multiplied with the KV cache, requiring repetitive MPC-unfriendly equal protocols.

---

Suiicaly Evieted
Dynamically Selected per
Dysamically
Alt--ogreeive Decoding Decoding Step
MPC-Ginnd Optiminaaionn
Evicted
Decoding Supp
MPC-friendly
Layer
Similarity Approx
Static Eviction
Dynamic Scleetien
Hicracchiall Cacho Clustering
Step (Prefitt)
Step (Desoding)
Crnes-layer Index
Query
VaylV Codae
Query Key/Value Cacae
Query Valae Cuche
Quer Key/Valne Caclte
Sharing Siralegy
Figure 4: Overview of our proposed MPCACHE.
Inspired by token-wise locality 49 95], our key insight to group the udjacent lokens into clusters, which can reduce the complexity of dynamic selection in proportion to the cluster size. However, this introduces extra questions on how to measure the similarity between a cluster and the current query, how to build the cluster, etc, which is discussed in Section 4.3
Observation 3: adjacent layers share similar top-k ranking of KV cache, providing an extra opportunity for efficiency optimization. Due to the residual, we hypothesize adjacent layers may share a similar top-k ranking of the KV cache. To verify the assumption, we define commonality score to measure the ratio of common top-k indices of adjacent layers as
L-m
1+m
R:T. Σ
n i=1
idx,[ k)
where idx;|: k] denotes the set of top-k indices for i-th layer, L is the number of layers, and counts the number of elements in set. As shown in Figure BJ)), adjacent layers demonstrate high similarity of top-k indices, which indicates the query tends to focus on the KV cache the similar tokens. The score reduces when increases, which motivates to share the indices of selected tokens among adjacent layers to trade off efficiency and performance.
MPCACHE: MPC-friendly LLM Inference
4.1 Overview of MPCACHE
Overall design. Driven by the observations, we propose an MPC-friendly KV cache eviction framework, dubbed MPCACHE as shown in Figure 4 It consists of two steps: look-once static eviction during the prefill stage to discard the UIA tokens (Section 4.2h; 2) query-aware dynamic selection during the decoding stage to select only a small subset of the remaining IC tokens for sparse attention (Section 4.3). A series of MPC-friendly optimizations are proposed to reduce the overhead of selection (Section and 4.4). The pseudocode is shown in Algorithm and the overall data flow
is shown in Appendix
Symbol definition. For clarity, summarize the symbols used in this paper. We define L as the number of layers, H as the number of attention heads, as the number of tokens, d as the embedding dimension, as the cluster size, and C' as the number of clusters.
4.2 Step 1: Look-once Static KV Cache Eviction
To prune the KV cache of UIA tokens as observed in Section 3 we use static eviction once during the prefill stage. To measure the token importance and identify UIA tokens, we compute the attention map and then, accumulate the attention scores for each token. Similar 42 93 we find it is sufficient to only sum up the scores of the last 20% tokens in the prompt compute the accumulated attention score. Then, we rank the accumulated attention scores to select the important tokens with the highest scores and discard the UIA tokens.
0.5
0.3
0.2
Last Tokeas
0.2
0.4
0.1
0.3
0.25
0.15
0.05
0.15
0.4
Σ
0.45
0.55
0.15
0.45
0.4
Protocol complexity analysis. Compared to the baseline computation of the prefill stage, static eviction only involves accumulating the attention scores, which are locally computed without any communication, and top-k ranking. Because the static eviction is performed only once, the
Statically Evicted
Figure 5: The illustration of static eviction.
5

---

Hond
Head
Determined
Kry Cuche
Preserved Cluster
3T4 MAMY
Approximated Similarity
Lovel.e
Similarity Distriuttoo
JW
Level
Key Clussers
Current Query Top-
(a) Hierarchical Clustering of Key Cache
(b) Dynamic Similarity Approximation
Figure 6: Hierarchical and dynamic KV cache clustering and selection procedure.
Table 2: The complexity analysis of token gathering protocol where ln
0.25T, 12 0.25C.
Width
Comparison
Lat.
Comm.
Example Lat.
Example Comm.
Baseline Protocol
log T log C
OIT log T)
O(ky log T)
4.780s
416.0MB 1.125MB
MPCACHE
log C)
Okg C))
0.065s
Improvement
log loge
Cllog
Tlog
Io T
RgC
73.5x
369.8x
cost can be amortized by the entire generation process, and hence, becomes negligible. Meanwhile, with UIA tokens pruned, the efficiency of the dynamic selection can be improved for all decoding steps and overall efficiency.
4.3 Step 2: MPC-friendly Dynamic KV Cache Selection
To reduce the overhead of dynamic token selection shown in Figure c). propose group the KV cache of adjacent tokens into clusters in Figure G(). The most important question is "how to aggregate the information of cluster and measure the cluster importance accurately and efficiently?"
MPC-friendly similarity approximation with clustering. A naive method for similarity approxi- mation is to compute the average of the key cache within a cluster and directly compute the cosine similarity with the average. However, as shown in Figure 7 the naive approach incurs large perfor- mance degradation. Our intuition is that the approximation should preserve the impact of important tokens as much as possible. Hence, we use the maximum dot product between the query and the key cache cluster. Specifically, given query q E gixd key cache cluster of tokens K. E gx the similarity can be designed as
d-1
Sim K.)
max q k max k
Σ q:k:
max qikı. KEK,
KEK,
We obtain the upper bound of similarity, and further have
q: maxkek, k; q: 2 0, qi minken, k; q; < 0.
max qik, = kek:
Define max and min where r.max = maXkek, k; and r-min minkek, k, Then, we have
d-1
Sim(q, K.) S
Σ max (q. max min). qirmin).
(2)
1=0
Protocol complexity analysis. During the decoding stage, r. and r.min of each cluster only need to be computed once. Hence, the computation cost can be amortized and become negligible. However, for each decoding step, we still need to compute O (T.Cd) multiplications, i.e., qariaxx and qarlin as well as (L.Cd) max operations in Equation 2 which still incur non-negligible overhead.
Linearization and reordering, To avoid the MPC-unfriendly max operation in Equation (2) we further propose to approximate the similarity as below:
Sim K.)
qar + (1 - a) q.r. min
1=0

---

where a E [0, 1] is a hyperparameter. As can be observed. when a 1, q is always selected while q.r," is always selected when a 0. After the linearization, there an opportunity to further reduce the multiplications by reordering the computation as
Σ a 7 + (1 (1- qar min ==0
Σ 1=0
qi (arquxx max + (1 (1)a)r, a)r.iin).
(3)
or and (1 armm are first added up without introducing extra communication, and the multipli-
cation with q; reduced by 2x. Compared with the maximum dot product in Figure 7 our method significantly reduces the cost while maintaining the performance. We empirically choose o = 0.6, and leave more discussions Appendix F33 and a theoretical analysis Appendix G
Protocol complexity analysis. MPCACHE reduces the number of max operations from (LCdd) to 0 and reduce the multiplication complexity by 2x. It is worth noting that clustering also benefits the token gathering protocol: 1) the number of equal protocol in one-hot vector conversion is reduced by log T
δ xx; 2) the bit width of one-hot vector is reduced by log x. Table 2 shows example of selecting top-25% tokens with T 1024, C 64, and the overhead is drastically reduced.
Hierarchical KV cache clustering. Another question is "how to build the KV cache cluster efficiently?" Since larger cluster sizes have higher efficiency at the cost of worse performance, we propose to trade off the selection overhead and performance. Inspired by hierarchical re- inforcement learning (77), we propose to cluster the KV cache of adjacent tokens with a hierarchical structure as shown in Figure that performs coarse- graise- (larger cluster size) to fine-grained (smaller cluster size) selection progressively. Generally, we divide the KV cache into n levels and progressively select the clusters level by level. At the fine-grained level, we only need to select from the remaining clusters, thereby reducing the selection complexity. Hicrarchical structure. including the cluster size and selection ratios at each level, can influence the performance-efficieng trfde-off. We discuss the trade-off in Section 5,4]and and setups in Appendix F.
111 Score (aa
Lin
92
Comparison among maxi- mum dot product (MP), average, and our method with different a's on TriviaQA.
Figure 7:
4.4 Cross-layer Index-sharing Strategy
Based on the observation that adjacent layers share sim- ilar top-k ranking of KV cache, we propose cross-layer index-sharing strategy that enables adjacent layers to share the same selected token indices to further reduce the cost of dynamic selection. Since two adjacent layers show the highest commonality score in Figure c), we choose
Commonality
0.75
0.5
Lo 1833
0.5
Layer & Layer
12
share the indices between two adjacent layers. In Figure ( we observe the first two layers have a low common- ality score while other layers have higher scores due to the residual, so we do not apply sharing to the first two layers. Cross-layer index-sharing effectively reduces the extra overhead introduced by dynamic selection. We discuss how the number of adjacent layers
Palroise Layer Index
Figure 8: Commonality score between two adjacent layers.
affects the trade-off in Section 5.4
4.5 Security Analysis of MPCACHE
MPCACHE is built upon established cryptographic building blocks from 2PC 53 and 3PC [19 that were already proven secure. Our introduced top-k protocol follows (31. Since our other optimizations do not introduce new protocols, but combine them to support efficient KV cache eviction, MPCACHE follows naturally from the security of these building blocks. MPCACHE assumes all parties are aware of the model architecture and number of pruned tokens, which consistent with 88 38). We argue that it does not compromise the client's 's data, nor does it enable the client to access the model's 'ss parameters. Also, the shared indices between layers are ciphertexts, which won't reveal any private information.
7

---

TrivaaA
PassageRetrieaal
HecputQA
Qugarre
NarrativeQ4
GevReport
AccuInES (%g
8 12
F1 11 (5)
P1 Score (%)
RONGGE La
F1
Cache Budget
KV Cache Budget
Cache Budget
Budgat
KV Cache Budget
Cacha Budget
Figure 9: Comparison with prior-art fixed-pattern and static eviction algorithms LongBench.
Table 3: Comparison with prior-art art dynamic KV cache eviction algorithms with different budgets.
IatLLM
LongCache
MPCACHE (ours)
Dataset
Cache Budget
Performance (%
Latency (6)
Performance (%)
Lateney (8)
Performance (%)
Latency (6).
Full
31.16
75.52
31.16
75.52
31.16
75.52
HotporQA
5%
28.20
51.64 (1.3 (1.30x)
24.31
89.46 (2.24x)
30.27
39.85
10%
(1.28x)
(2.30x)
Full
82.67
75.52
82.67
75.52
82.67
75.52
TriviaQA
5%
75.65
$1.64 (1.38x)
59.85
89.46 (2.59x)
75.61
37.37
10%
82.75
68.04 (1,34x))
60.56
123.1 (2.45x)
82.45
50.75
Full
17.02
75.52
17.02
75.52
17.02
75.52
NarQA
5%
12,80
47.74 (1.33 (1.32x)
14.65
86.42 (2,39k)
17.23
36.
10%
13.74
63.49 ( (8x)))
15.69
121.4 (2.45x)
17.35
49.46
Full
32,50
75.52
32.50
75.52
32.50
75.52
PassageR
5%
6,161
51.64 (1.15x)
21.42
89.46 (1.99))
19.75
44.82
10%
8.872
68 18.04 (1.16x)
24.92
123.1 (2.10x)
27.75
58.47
75.52
Qusper
64.52 (1.45x)
24.53
16%
23,90
72.84 (1.33x)
26.07
225.9 (4.12x)
21.95
51.77
(ax) means MPCACHE achieves ax efficiency improvemntt over the baselines.
Empirical Evaluation
5.1 Experimental Setups
Models, datasets, and baselines. Our experiments are conducted on LLaMA-22, LongChat-7B-
V1.5-32K, and LLaMA-3. -...A-3.11880 InSttuuttt on LongBench [2], XSUM (57), and srcdle-in-a-Haystaee
233. Refer to Appendix F.1 for details. We choose prior-art static and dynamic KV cache eviction
baselines, including H2O 91, StreamingLLM 776,, TOVA [58], SnapKV 42), InfLLM 77]. and
LongCache [47]
We leave the details of baselines to Appendix
Experimental setups. For performance evaluation, our ex- periments are conducted based on LongBench on an NVIDIA
Table 4: Evaluation XSUM task.
A 80GB GPU. For efficiency evaluation, we use Secretflow (SPU V0.9.1) (55 and follow the 3PC protocols of PUMA [19].
Budget
10%
5%
Model
7B:
138
13B1
The latency is evaluated under the LAN setup. We evaluate the efficiency using the architecture of GPT-2 and LLaMA-2. We
Pull Cache
MPCACHE (ours)
11.10
13:44
10.08
13.08
emphasize that the eviction ratio is determined based on the expected sequence length and the latency that can be tolerated by the server and the client in a realistic scenario. We explain the details of baselines, setups, and how to securely determine the
in Appendix F.I
5.2 Performance Evaluation
In Figure and Table we comprehensively compare MPCACHE with prior-art KV cache eviction methods on LongChat- 1B-VI.5-3225 and we make the following observations: comparison with fixed-pattern and static methods. MPCACHE consistently outperforms prior-art baselines across different datasets. MPCACHE shows decent scalability to different KV cache budgets. For example, on HotPotQA and NarrativeQA, MPCACHE achieves comparable performance as full cache, even only ~5% KV cache preserved; 2) comparison with dynamic methods. MPCACHE achieves comparable and even better performance compared with InfLLM and LongCache. On NarrativeQA,

---

KV Cadne
LonaCadhe-F 5%
Head Mensin
MPCacte-10%
M%C
Normalized
Normalizel
Comm (GB)
0.75
0.50
2.46
L0lc-
3.21x
592x
Seq.. Langtedi b-d12
Sey, Langthe512
Suy. Longhhi884
Seg. Langh=2044
Sey, Length-512
Seg. Langbed122
Seq. Lengh=1004
Seg. Longhh26645
Figure 10: Evaluation on per-token generation latency and communication compared with LongCache
head merging 622 and Vrke [8. Note that 5% and 10% mean the final KV cache budget.
MPCACHE achieves 1.32x and 2.39 latency reduction with higher F1 score compared with InfLLM and LongCache, respectively; 3) scalability. We combine static and dynamic methods on LLaMA-2-13B in Table 4 and LLaMA-3. 1.aMAA...1880 1-8B-Instruc in Table 5 demonstrating the superior performance of our method.
Table Extension to LLaMA-3.1 -.---.---B-----. -B-Instruct on LongBench with an average KV cache budget of 2048 and 1024. The best result is highlighted in bold and the second best in underline.
Budget
NarativeQA
Qusper
HoipotQA
2WikIMQA
MuSiQue
TREC
SAMSum
TriviaQA
QMSum
Pull Cache
30.21
45.51
55.53
46.71
31.35
72.50
43.85
91.74
25.20
99.50
54.94
Streamingl.LMM LM
27.40
30.77
49.23
44.66
24.31
67.50
42.49
90.95
21.67
87.00
37.5
2048
DuoAAtemiin
25.61
42.31
52.36
42.14
28.17
66.00
43.36
39.95
22.11
98.50
55.53
SnupkY
28.53
30.13
54.32
46.50
28.48
55.55
43.10
92.04
23.97
99.50
$3.91
28.00
45
68
44.05
MPCACHE
53.41
Full Cache
30.31
45.52
55.53
46.71
31,34
72.50
43. 86
91.74
25.20
99.50
54 $4.94
StreamingLLMM
26.64
27.48
47.3]
24.17
42.76
88.84
21.31
35.
1024
DuvAnentio
24.12
30.41
25.53
42.54
76.36
Snapky
27.24
90:12
23.10
Queest
15:45
23.93
70.00
21.04
99.00
MPCAFII:
29.47
46.20
55.38
46.55
31.14
69.50
43,02
91.84
24.77
99.50
52.70
5.3 Efficiency Evaluation
In Figure 10, we benchmark the decoding efficiency with different sequence lengths ranging from 512 to 2048 and a static eviction ratio of 70%. We compare MPCACHE with full KV cache, LongCache, head merging (62], and Vrk [8] with 3PC protocols. From the results, we make the following observations: 1) compared with full KV cache, MPCACHE achieves 1.59 2.01x. x, 1.46 ~ 1.97x, and 1.26 ~ 1.8x x latency reduction and 3.39 ~ 4.18x, 4.33 5.92x, and 5.51 ~ 8.37x communication reduction with different sequence lengths, respectively; 2) compared with LongCache which performs dynamic token-wiss selection, MPCACHE even achieves 3.85 and 19.47 x latency and communication reduction, respectively: 3) MPCACHE shows higher efficiency than Vrle due to our optimizations. We further discuss 2PC protocol [53 in Appendix F.3
5.4 Ablation Studies of MPCACHE
Effectiveness of different optimizations. In Figure we demonstrate the effectiveness of our proposed optimizations by adding them step by step LLaMA-2-7B with sequence length of 1024 and static eviction ratio of 70%. We make the following observations: 1) directly applying
Level 1 Coarse-grained
Fine-grained
Level 2
Score (%)
Comm. (MII)
s32(019)
s16(0.22)
29.5
163.5
<32(0.7)
<16/0 28)
30.1
144.0
Mede
ad2(0.5)
a16(0.40)
50.2
Sinbtrr Agose
s32(0.3)
#16(0.67)
CaCo
60%
20%
.64(0.0)
<16(0.22)
29.5
a64/0.7)
#16(0.28)
29.3
110.1
Twring
000
add(0.55
#16/0.00
29.1
104.9
60
60
128
100
300
1930
150
Hey
a64(0.33
a16(0.7))
29.0
69.12
Latency
Communication (XB8)
Performance
Table 6: Comparisons among different hier- archical structures.
Figure 11: Step-by-step ablation study.

---

BY Cache
StrouniggLLM (Bodaat-10%))
StromiingLLMM (Bodaad-50%%
Ctar (Boodact-3A%))
Otar (Boddao-54%)
LongChat Chahh-- 1.5-111..-88
Daptt Depth-Srment Mirent
3.
2-
0
Lengl
LLaMA-3, 1-1-------0 Instruct
Cache
StramingLLM (Bedpzrdd0)))
NinamisptLLM (Brd
(Bwllge-10%)
Oerx (Bedgan-88%)
Depth Peront
5 2.055 2.5
Figure 13: Needle-in-a -eeyst-n-a-Hayyttckk The x-axis denotes the length of the context ("haystack") and the y-axis indicates the position where the "needle" (a short prompt) is inserted within the context.
dynamic selection, e.g., LongCache private LLM inference does not provide the expected efficiency improvement and even increases both latency and communication; 2) after static eviction, latency and communication of dynamic selection reduced by 1.42x and 2.76x, respectively; 3) MPC-friendly optimizations, including clustering, linearization, reordering, and cross-layer index- sharing further reduce the overhead introduced by dynamic selection without sacrificing the model performance; 4) MPCACHE eventually achieves 1.9x x and 5.9 latency and communication reduction, respectively, and achieves high performance.
Effect of hierarchical structures. To trade off the model performance and dynamic selection overhead, evaluate dif- ferent hierarchical structures with a dynamic selection ratio of 20%. We choose different cluster sizes and selection ratios at different levels. From Table[]] we find that when 8 increases the coarse-grained selection ratio decreases, the overhead decreases while the performance exhibits a downward trend. Moreover, appropriate seare--raiiee selection may help im- prove the overall performance, e.g., the ratio changes from 90% 50% with 32;
30.0
28:65
Lafeney
Scoue
39.0
Fl (%)
27.5
36.0
35.0
H A.djaceet Layers
Figure 12: Effect of the number of adjacent layers.
Effect of the number of adjacent layers for cross-layer index- sharing. In response to Section 3 we evaluate the efficiency- performance trade-off of the number of adjacent layers on HotpotQA in Figure 12 As observed, when the number of adjacent layers increases, the latency is reduced while the performance degradation.
Benchmark on Needle-in-a- Haysstckk. We benchmark our similarity approximation algorithm on shown in Figure [3] MPCACHE demonstrates comparable performance with full KV cache and outstanding performance compared with StreamingLLM.
Beedle-in-a-Haystted
Additional results. We present the influence of a, discussion on 2PC protocol, comparison with average-baat based similarity in [ppendix(F]
Limitation and Conclusion
MPCACHE focuses on MPC inference, which still incurs non-negligible overhead compared to the plaintext counterpart. For certain tasks, such those requiring the model to recall information from tokens considered unimportant, static eviction may fall short, which a direction for future research.
In this work, we propose an MPC-friendly KV cache eviction framework named MPCACHE, that enables accurate and efficient private LLM inference. MPCACHE systematically combines static eviction and dynamic selection. To reduce the overhead of dynamic selection, we propose series of MPC-friendly optimizations, including efficient similarity approximation, hierarchical KV cache clustering, and cross-layer index-sharing. Extensive evaluations demonstrate that MPCACHE con- sistently outperforms prior-art KV cache eviction baselines across different generation tasks and significantly reduces both latency and communication.
10

---

Acknowledgements
This work was supported in part by NSFC under Grant 62495102, Grant 92464104, and Grant 62341407, in part by Beijing Municipal Science and Technology Program under Grant 2241100004224015, and in part by Ant Group through CCF-Ant Research Fund.
References
[1] 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:114-127, 2024.
[2] Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308 14508, 2023.
[3] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXi::2004.05/50, 2020.
[4] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piga: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 7432 0022-743,,00 2020.
[5] Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, al. Pyramidkv: Dynamic kv cache compression based pyramidal information funneling. arXiv preprint 2rXiv:2406.02065 2024.
[6] Chi-Chih Chang, Wei-Cheng Lin, Chien-Yo Yu Lin, Chong -an Chen, Yu-Fang Hu, Pei-Shuo Wang, Ning-Chi Huang, Luis Ceze, and Kai-Chiang Wu Palu. Compressing kv-eache with low-rank projection. arXiv preprint arXiv:2407.21 2024.
[7] Dake Chen, Yuke Zhang, Souvik Kundu, Chenghao Li, and Peter A Beerel. Rna-vit: Reduced- dimension approximate normalized attention vision transformers for latency efficient private inference. 2023 JEEE/ACM International Conference on Computer Aided Design (ICCAD), pages 1-9. IEBE, 2023.
[8] Renze Chen, Zhuofeng Wang, Beiquan Cao, Tong Wu, Size Zheng, Xiuhong Li, Xuechao Wei, Shengen Yan, Meng Li, and Yun Liang. Arkvale: Efficient generative Ilm inference with recallable key-value eviction. In The Thirty-eights Annual Conference on Neural Information Processing Systems, 2024.
[9] Tianyu Chen, Hangbo Bao, Shaohan Huang, Li Dong, Binxing Jiao. Daxin Jiang, Haoyi Zhou, Jianxin Li, and Furu Wei. The-x: Srivacy-preservve transformer inference with homomorphic encryption. arXiv preprint (tXXi:220000021666 2022.
[10] Yilong Chen, Guoxia Wang, Junyuan Shang, Shiyao Cui, Zhenyu Zhang, Tingwen Liu, Shuo- huan Wang. Yu Sun, Dianhai Yu, and Hua Wu. Nacl: A general and effective kv cache eviction framework for Iims at inference time. arXiv preprint arXiv:2408.0361 2024.
[11] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. Vicuna: An open-source chatbot impressing gpt-4 with 90%* * chatgpt quality, march 2023, URL https://mmyss org/blog/2023-03 30-vicuna, 3(5), 2023.
[12] Minsu Cho, Ameya Joshi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Selective network linearization for efficient private inference. In International Conference Machine Learning, pages 3947-3961. PMLR, 2022.
[13] Tri Dao. Flashattention-22 Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.0869/ 2023,

---

[14] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness, Advances in Neural Information Processing Systems, 35: 16344-16339,, 2022.
[15] Pradeep Dasigi, Kyle Lo, Iz Beltagy, Arman Cohan, Noah A Smith, and Matt Gardner. A dataset of information-sseeiing questions and answers anchored in research papers. arXiv preprini arXiv:2/05.03011, 2021.
[16] Aditya Desai, Shuo Yang, Alejandro Cuadron, Ana Klimovic, Matei Zaharia, Joseph Gon- zalez, and Ion Stoica. Hashattention: Semantic sparsity for faster inference. arXiv preprint arXiv:2412. 14468, 2024.
[17] Alessio Devoto, Yu Zhao, Simone Scardapane, and Pasquale Minervini. A simple and effective I norm-based strategy for kv cache compression. arXiv preprint arXiv:2406.11430, 2024.
[18] Naren Dhyani, Jianqiao Mo, Minsu Cho, Ameya Joshi, Siddharth Garg, Brandon Reagen, and Chinmay Hegde. Privit: Vision transformers for fast private inference. arXiv preprint arXiv:2310004004 2023.
[19] Ye Dong, Wen-jie Lu, Yancheng Zheng, Haoqi Wu, Derun Zhao, Jin Tan, Zhicong Huang, Cheng Hong, Tao Wei, and Wenguang Cheng. Puma: Secure inference of llama-7b in five minutes. arXiv preprini arXiv:2307. 125333, 2023.
[20] Qichen Fu, Minsik Cho, Thomas Merth, Sachin Mehta, Mohammad Rastegari, and Mahyar Najibi. Lazyllm: Dynamic token pruning for efficient long context Ilm inference, 2024.
[21] Yizhao Gao, Zhichen Zeng, Dayou Du, Shijie Cao, Hayden Kwok-Hay So, Ting Cao. Fan Yang, and Mao Yang. Seerattention: Learning intrinsic sparse attention in your llms. arXiv preprint vrXiv:2410.13276 2024.
[22] Suyu Ge, Yunan Zhang. Liyuan Liu, Minjia Zhang. Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for lims. arXiv preprint arXiv:2310.01801 2023.
[23] gkamradt. Limtest needle in a haystack pressure testing 1lms. http://LLMeetttteeeeeeeLeelaaaaa 2023.
https://github.com
[24] Oded Goldreich. Secure multi-party computation. Manuscript. Preliminary version, 78(110):-
108, 1998.
[25] Kanav Gupta, Neha Jawalkar, Ananta Mukherjee, Nishanth Chandran, Divya Gupta, Ashish Pan- war, and Rahul Sharma. Sigma: Secure gpt inference with function secret sharing. Cryptology ePrint Archive, 2023.
[26) 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. arXiv preprint arXiv:2308. 16137, 2023.
[27] Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private inference on transformers. Advances in neural information processing systems, 35:15718-15731 2022.
[28] Yefei He, Luoming Zhang, Weijia Wu, Jing Liu, Hong Zhou, and Bohan Zhuang. Zipeache: Accurate and efficient kv cache quantization with salient token identification. arXiv preprint arXiv:2405.14256. 2024.
[29] Coleman Hooper, Schoon Kim, Hiva Mohammadzadeh, Monishwaran Maheswaran, June Paik, Michael W Mahoney, Kurt Keutzer, and Amir Gholami. Squeezed attention: Accelerating long context length Ulm inference. arXiv preprint
2024.
[30] Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length Imm inference with kv cache quantization. arXiv preprint arXiv:2401. 2024.
12

---

[31] Xiaoyang Hou, Jian Liu, Jingyu Li, Yuhan Li, Wen-jie Lu, Cheng Hong, and Kui Ren. Ciphergpt: Secure two-party gpt inference. Cryptology ePrint Archive, 2023.
[32] Luyang Huang, Shuyang Cao, Nikolaus Parulian, Heng Ji, and Lu Wang. Efficient attentions for long document summarization. arXiv preprint arXiv:2104.02112 2021.
[33] Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir H Abdi, Dongsheng Li, Chin-Yer Lin, et al. Minference 1.0: Accelerating pre-filling for long-context Ilms via dynamic sparse attention. arXiv preprint arXiv:2407.024990 2024.
[34] William B Johnson, Joram Lindenstrauss, and Gideon Schechtman. Extensions of lipschitz maps into banach spaces. Israel Journal of Mathematics, 54(2):129-133 1986.
[35] Hao Kang, Qingru Zhang, Souvik Kundu, Geonhwa Jeong, Zaoxing Liu, Tushar Krishna, and Tuo Zhao. Gear: An efficient kv cache compression recipefor near-lossless generative inference of Ilm. arXiv preprint arXiv:2403.055. 403.05527, 2024.
[36] James T Klosowski, Martin Held, Joseph SB Mitchell, Henry Sowizral, and Karel Zikan. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE transactions on Visualization and Computer Graphics, 4(1):21-36, 1998.
[37] Tomáš Kočiský, Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gábor Melis, and Edward Grefenstette. The narrativeqa reading comprehension challenge. Transac- tions of the Association for Computational Linguistics, 6:317-328, 2018.
[38] Souvik Kundu, Shunlin Lu, Yuke Zhang, Jacqueline Liu, and Peter A Becrel. Learning to linearize deep neural networks for secure and efficient private inference. arXiv preprint 1.Xiv:2301.0925:5 2023.
[39] Woosuk Kwon, Zhuohan Li. Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and lon Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 61 1-626,62222 2023.
[40] Dacheng Li, Rulin Shao, Hongyi Wang, Han Guo, Eric P Xing, and Hao Zhang. Mpeformer: fast, performant and private transformer inference with mpe. arXiv preprint arXw::2211.01452. 2022.
[41] Fabing Li, Yuanhao Zhai, Shuangyu Cai, and Mingyu Gao. Seesaw: Compensating for nonlinear reduction with linear computations for private inference. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 29266-29277. PMLR, 21-27 Jul 2024.
[42] Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Lim knows what you are looking for before generation. arXiv preprint 24X1v:2404.1444 2024.
[43] Yehuda Lindell and Benny Pinkas. A proof of security of yao's protocol for two-party computa- tion. Journal of cryptology, 22:161-188 2009.
[44] Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chengruidong Zhang, Bailu Ding, Kai Zhang, et al. Retrievalattention: Accelerating long- context IIm inference via vector retrieval. arXiv preprint arXiv:2409. 10516, 2024.
[45] Guangda Liu, Chengwei Li, Jieru Zhao, Chenqi Zhang, and Minyi Guo. Clusterkv: Manipulating Ilm kv cache in semantic space for recallable compression. arXiv preprint arX2v:2412.03311, 2024.
[46] Minghui Liu, Tahseen Rabbani, Tony O'Halloran, Ananth Sankaralingam, Mary-Anne Hart- ley, Brian Gravelle, Furong Huang, Cornelia Fermüller, and Yiannis Aloimonos. Hashevict: pre-attention kv cache eviction strategy using locality-sensitive hashing. arXiv preprint 2rXiv:2412.16187,0 2024.
13

---

[47] Xiaoran Liu, Qipeng Guo, Yuerong Song, Zhigeng Liu, Kai Lv, Hang Yan, Linlin Li, Qun Liu, and Xipeng Qiu. Farewell to length extrapolation, training-free infinite context with finite attention scope. arXiv preprint arXiv:2407. 15176, 2024.
[48] Xuanqi Liu and Zhuotao Liu. Lims can understand encrypted prompt: Towards privacy- computing friendly transformers. arXiv preprint arXiv:2305. 18396, 2023.
[49] Yuhan Liu, Hanchen Li, Kuntai Du, Jiayi Yao, Yihua Cheng, Yuyang Huang, Shan Lu, Michael Maire, Henry Hoffmann, Ari Holtzman, al. Cachegen: Fast context loading for language model applications. arXiv preprint arXiv:2310.07220, 2023.
[50] 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 IIm kv cache compression at test time. Advances in Neural Information Processing Systems, 36, 2024.
[51] Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A tuning-free asymmetric 2bit quantization for kv cache. arXiv preprint S4Kiv:2202.0275555 2024.
[52] Tianpei Lu, Bingsheng Zhang, Xiaoyuan Zhang, and Kui Ren. A new PPML paradigm for quantized models. Cryptology ePrint Archive, Paper 2024/1 132, 2024.
[53] Wen-jie Lu, Zhicong Huang, Zhen Gu, Jingyu Li, Jian Liu, Cheng Hong, Kui Ren, Tao Wei, and WenGuang Chen. Bumblebee: Secure two-party inference framework for large transformers. Cryptology ePrint Archive, 2023.
[54] Jinglong Luo, Yehong Zhang, Zhuo Zhang, Jiaqi Zhang, Xin Mu, Hui Wang, Yue Yu, and Zenglin Xu. Secformer: Fast and accurate privacy-preeerving inference for transformer models via smpc. In Findings of the Association for Computational Linguistics ACL 2024, pages 13333- 13348, 2024.
[55] Junming Ma, Yancheng Zheng, Jun Feng, Derun Zhao, Haoqi Wu, Wenjing Fang, Jin Tan, Chaofan Yu, Benyu Zhang, and Lei Wang. SecretFlow-SPU: A performant and User-Friendly framework for Preacc-Preseviing machine learning. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). USENIX Association, July 2023.
[56] Payman Mohassel and Peter Rindal. Aby3: A mixed protocol framework for machine learning. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 35 12,552222 2018
[57] Shashi Narayan, Shay Cohen, and Mirella Lapata. Don't give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization. arXiv preprint arXiv: 1808. 08745, 2018
[58] Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers are multi-state mns. arXiv preprint arXiv:2401.06104, 2024.
[59] M Ott. fairseq: A fast, extensible toolkit for sequence modeling.
arXiv preprint
194.v:190..01038, 2019.
[60] Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. Bolt: Privacy- preserving, accurate and efficient inference for transformers. Cryptology ePrint Archive, 2023.
[61] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 188)99 2019.
[62] Deevashwer Rathee, Dacheng Li, lon Stoica, Hao Zhang, and Raluca Popa. Mpe-minimized secure Ilm inference. arXiv preprint arXiv:2408. 03561, 2024.
[63] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow2: Practical 2-party secure inference. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 325-342, 2020.
14

---

[64] Utkarsh Saxena, Gobinda Saha, Sakshi Choudhary, and Kaushik Roy. Eigen attention: Attention in low-rank space for kv cache compression. arXiv preprint 0rXiv:2408.05646, 2024.
[65] Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. arXiv preprint arXiv:2407.08608, 2024.
[66] Hanlin Tang. Yang Lin, Jing Lin, Qingsen Han, Shikuan Hong, Yiwu Yao, and Gongyi Wang. Razorattention: Efficient kv cache compression through retrieval heads. arXiv preprint arXiv:2407. 15891, 2024.
[67] Jiaming Tang. Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context IIm inference. arXiv preprint C1T:22406.1074 2024.
[68] Rohan Taori, Ishaan Gulrajani. Tianyi Zhang. Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Stanford alpaca: an instruction-folloinng llama model (2023). URL https://github. com//atsuu-lab//ttafooddd _alpacu, 2023.
[69] Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint wrXiv:2201.082333 2022.
[70] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint wwXii:2307.09288, 2023.
[71] Zhongwei Wan, Ziang Wu, Che Liu, Jinfa Huang, Zhihong Zhu, Peng Jin, Longyue Wang, and Li Yuan. Look-m: Look-once optimization in kv cache for efficient multimodal long-context inference. arXiv preprint arXiv:2406. 18139, 2024.
[72] Hanrui Wang, Zhekai Zhang, and Song Han. Spatten: Efficient sparse attention architecture with cascade token and head pruning. In 202/ IEEE International Symposium on Perf-PPefoemance Computer Architecture (HPCA), pages 97-110. IEEE, 2021.
[73] Zihao Wang and Shaoduo Gan. Squeezeattention: 2d management of kv-cache in Ilm inference via layer-wise optimal budget. arXiv preprint arXiv:2404.04799, 2024.
[74] Chaojun Xiao, Pengle Zhang, Xu Han, Guangxuan Xiao, Yankai Lin, Zhengyan Zhang, Zhiyuan Liu, Song Han, and Maosong Sun. Infllm: Unveiling the intrinsic capacity of Ilms for under- standing extremely long sequences with training-free free memory. arXiv preprini M.Xi::2402.04111 2024.
[75] Guangxuan Xiao, Jiaming Tang. Jingwei Zuo, Junxian Guo, Shang Yang, Haotian Tang, Yao Fu, and Song Han. Duoattention: Efficient lon-ccontext Ilm inference with retrieval and streaming heads. arXiv preprint ar wwX.x::2400108//11 2024.
[76] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2300. /7453, 2023.
[77] Zhiwei Xu, Yunpeng Bai, Bin Zhang, Dapeng Li, and Guoliang Fan. Haven: Hierarchical coop- erative multi-agent reinforcement learning with dual coordination mechanism. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 11735-11743, 2023.
[78] 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.1 11005.22550 12522, 2024.
[79] Shang Yang, Junxian Guo, Haotian Tang, Qinghao Hu, Guangxuan Xiao, Jiaming Tang, Yujun Lin, Zhijian Liu, Yao Lu, and Song Han. Lserve: Efficient long-sequence I1m serving with unified sparse attention. arXiv preprint a502v: 14866, 2025.
[80] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhut- dinov, and Christopher D Manning. Hotpotqa: dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv:1809.09600, 2018.
15

---

[81] Yao Yao, Zuchao Li. and Hai Zhao. Sirllm: Streaming infinite retentive 1lm. arXiv preprint arXiv:2405. 125288, 2024.
[82] Jingyang Yuan, Huazuo Gao, Damai Dai, Junyu Luo, Liang Zhao, Zhengyan Zhang, Zhenda Xie, YX Wei, Lean Wang. Zhiping Xiao, et al. Native sparse attention: Hardware- and natively trainable sparse attention. arXiv preprini arXiv:2502./ 1089, 2025.
[83] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santi- ago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 13:17233177297, 2020.
[84] Wenxuan Zeng, Meng Li, Wenjie Xiong, Tong Tong, Wen-jie Lu, Jin Tan, Runsheng Wang, and Ru Huang. Mpevit: Searching for accurate and efficient mpe-friendly vision transformer with heterogeneous attention. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 5052-5063, 2023.
[85] Rongzhi Zhang, Kuang Wang, Liyuan Liu, Shuohang Wang. Hao Cheng, Chao Zhang, and Yelong Shen. Lore: Low-rank compression for Ilms kv cache with a progressive compression strategy, arXiv preprint arXiv:2410.03111, 2024.
[86] Tianyi Zhang, Faisal Ladhak, Esin Durmus, Percy Liang, Kathleen McKeown, and Tatsunori B Hashimoto. Benchmarking large language models for news summarization. Transactions of the Association for Computational Linguistics, 12:39-57, 2024.
[87] Tianyi Zhang, Jonah Yi, Zhaozhuo Xu, and Anshumali Shrivastava. Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization. arXiv preprint vrXiv:2405.03917 2024.
[88] Yancheng Zhang, Mengxin Zheng, Yuzhang Shang, Xun Chen, and Qian Lou. Heprune: Fast private training of deep neural networks with encrypted data pruning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[89] Yichi Zhang, Bofei Gao, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, Wen Xiao, al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling, arXiv preprint arXiv:2406.0200 2024.
[90] Yuke Zhang, Dake Chen, Souvik Kundu, Chenghao Li, and Peter A Beerel. Sal-vit: Towards latency efficient private inference on vit using selective attention search with learnable softmax approximation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5116-5125, 2023.
[91] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024.
[92] Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang. Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficient 11m training by gradient low-rank projection. arXiv preprint arXiv:2403.03507 2024.
[93] Youpeng Zhao, Di Wu, and Jun Wang. Alisa: Accelerating large language model inference via sparsity-aware caching. arXiv preprint urXiv:2403. 2024.
[94] Fei Zheng, Chaochao Chen, Zhongxuan Han, and Xiaolin Zheng. Permllm: Private inference of large language models within 3 seconds under wan. arXiv preprint arXiv:2405.1877 2024.
[95] Lei Zhu, Xinjiang Wang, Zhanghan Ke, Wayne Zhang, and Rynson WH Lau. Biformer: Vision transformer with bi-level routing attention. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 16323-10333, 2023.
[96] Itamar Zimerman, Allon Adir, Ehud Aharoni, Matan Avitan, Moran Baruch, Nir Drucker, Jenny Lerner, Ramy Masalha, Reut Meiri, and Omri Soceanu. Power-softmax: Towards secure Imm inference over encrypted data. arXiv preprint 4rXir:2410.09457,, 2024,
16

---

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: Refer to the sections of Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Refer to the section of Limitation.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
17

---

Justification:
Refer to Appendix G
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Refer the section of Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
18

---

reproducible, they Answer: [Yes]
Justification:
Refer to the code here
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public/guides. http///odeeeaaaeiinnnneeeeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "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 to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/ //nips httpcc/cpplllgggiiueee
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. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is 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 describe the detailed setups and the determination of hyperparameters in Appendix F.1
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core 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, 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: [No]
Justification: We conduct experiments on multiple models and datasets, which require significant computational resources. In addition, we provide open access to the data and code, making it easy reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error 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.)
19

---

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.
It 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 of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Our compute resources can be found in the Appendix F.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms 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 circumstances 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: [NA]
Justification:
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.
20

---

The conference expects that many papers will be foundational research and not tied 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: /
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses 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: /
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or 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 (c.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 package should be provided. For popular datasets, paperswi thcode. com com/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.
21

---

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: /
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. Crowdsourcing 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: /
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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: /
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
22

---

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: [NA]
Justification: /
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.
23

---

A Detailed Background and Related Works
A.1 Private LLM Inference
Recently, private LLM inference has attracted an increasing amount of research attention. Iron [27] uses coefficient encoding to compute homomorphic encryption (HE)-based convolution layers efficiently and uses MPC to compute non-linear layers. PUMA [99 proposes a series of 3PC
protocols for both linear and non-linear functions to support private LLM inference, even under the
scale of LLaMA-7B. BumbleBee 53 proposes HE-based protocols that enable the multiplication of large matrices and efficient protocols for non-linear functions similar to PUMA. CipherGPT [3] uses subfield vector oblivious linear evaluation (sVOLE) to reduce the communication of MatMuls significantly. BOLT [60] proposes baby-step giant-step (BSGS) strategy that reduces the number of rotations on ciphertexts. SIGMA [25] achieves private GPT inference with function secret sharing (FSS) and accelerates the computation on GPUs. PermI.MM (94 proposes an efficient protocol for non-linear functions based on the random permutation. However, they mainly focus on protocol optimization, and still incur sigmificant overhead, especially on long sequences.
There are also works directly replacing expensive non-linear functions in Transformers, c.g., Softmax
and GeLU with MPC-friendly operations. For instance, MPCFormer 440] and Secformer [5 simplify
Softmax by replacing exponential with an MPC-friendly quadratic function. MPCVIT 84
replaces
exponential in Softmax with ReLU and selectively uses scaling attention using neural architecture
search (NAS). SiL-VIT (90) introduces external attention while PriViT [18] uses squaring function to replace Softmax. RNA-ViT 7 and Power-Softmax [96] use high-order polynomial approximation. 48] directly uniformly replaces GeL.U with ReL.U and replaces exponential in Softmax with ReI.U.
THE-X 9 approximates Softmax using an estimation model. Although these methods achieve high inference efficiency, they cannot avoid finetuning or re-training to preserve the model performance, making LLM development impractical. In conclusion, the above works still suffer from heavy overhead. Moreover, these works always handle full-length contexts during the LLM generation, incurring large latency and communication when handling long sequences. To solve this problem, our work aims compress the KV cache in attention without training. Our proposed method can also be applied to different protocol frameworks for efficiency improvement.
A.2
KV Cache Compression
When tackling the LLM generation tasks, especially in cong-context scenarios, the KV cache in the attention module becomes the most significant bottleneck due to the increasing sequence length. Therefore, how to effectively reduce the size of the KV cache is a high priority. System-leve optimizations such as FlashAttention [14], FlashAttention-2 [33,, FlashAttention-3 (65), and Page- dAttention [39 have been proposed to alleviate the problem. Meanwhile, many recent research efforts have been devoted to algorithm-level optimizations. For example, quantization methods 51 have been proposed to compress KV cache to 4 bits, low-rank decompo- project the KV cache into low-rank space. In this work, we follow FlashAttention 14 to save the GPU memory and focus on another research line of algorithm-level optimization called KV cache eviction, which is designed to reduce the number of tokens and enable sparse attention without extra training.
30
87
35
28
sition methods 64 6
9 85
KV cache eviction can be mainly categorized into 3 classes: 1) fixed Sxted-pattern algorithm: the position of important tokens is pre-defined before inference and remains consistent across decoding steps. However, this algorithm is not flexible for different LLMs and contexts 76
3 X3 2) static algo- rithm: tokens are statically discarded and cannot be recovered in the subsequent decoding steps. This algorithm is usually efficient but suffers from significant performance degradation when the compression ratio is high 50, 22 42, 89 78 93 10
71 33 58); 3) dynamic algorithm: tokens are dynamically selected across different decoding steps. This algorithm is much more flexible but
the dynamic selection usually involves more expensive operations 77 47 67 We quantitatively compare existing methods in Table [
Here, we introduce recent works of KV cache eviction. StreamingLLM 76 proposes to keep few initial tokens along with the recent tokens to recover the long-context performance. RazorAttention (66) theoretically analyzes the scope of effective attention vision for each head. Scissorhands (50). H2O (9T), ALISA [93), spttee [72,, SnapK [2] and LOOK-M [7I], and TOVA (58) use the accumulated attention score of the historical tokens to select small subset of KV cache. FastGen
24

---

and MInference 1.0 [39 propose to allocate different eviction policies for different heads based on the sparsity pattern of the prompt. PyramidKV 89), PyramidInfer [78], and Squeeze consider allocating different KV cache budgets for different layers. InfL.LM
22
73
74 and LongCache
47 propose to dynamically select tokens based on the relationship between the current query and the key cache of previous tokens. RetrievalAttennton [44] establishes connections from the query to its nearest keys and the decoding query can first search its nearest query and then obtain the most relevant key vectors. LazyLLM [20] introduces aux cache to enable selective KV cache eviction. Keyformer [ finds that the distribution after token pruning becomes uneven and proposes to smooth the distribution. Squeezed Attention [29] and ClusterKV [45] proposes to cluster KV cache based on the semantic information. HashAttention [16] and HashEvict [46] recently design hash functions to enable efficient KV cache eviction. To get rid of the dependency of similarity computation, L 81] uses token entropy while uses the 1.2-norm of the key cache to measure the token importance.
However, these works are not designed or optimized for MPC since they either statically discard tokens that cause significant performance degradation dynamically select tokens that introduce more complex and MPC-unfriendly operations. Recently, learning-based methods [75 21 have also emerged, which require training to automatically explore the sparsity patterns and thus, are not the focus this work.
A.3 Generative LLM Inference in Autoregressive-tyyle
The generative LLM inference procedure generally in an autoregressive style such as GPT-2 61 and LLaMA [70], and mainly consists of two stages: 1) the prefill (prompt) stage and 2) the decoding (generation) stage.
Prefill stage. The prefill stage serves the first step of generation. LLM takes prompt sequence as input and generates key-value (KV) caches for each layer. The attention can be computed as
prompt Softmax Qprompt K Vd) V prompt.
prompt/
(4)
where Qproapt E R xx denotes the query and Krroupt #xxxx V proupt E R Txxxx de- note the key and value cache, respectively. After the prefill stage, the KV cache is generated as Keacho <- Krrapp and V Vacce V prompt- KV cache retains previously computed key-value pairs, eliminating the need for costly re-computation of previous key and value vectors (59). Note that each layer is equipped with its unique KV cache and the generated KV cache the foundation for the dowmstreaming decoding stage.
Decoding stage. The decoding stage uses and updates the stored KV cache to generate new tokens step-by-step. First, the KV cache is updated by concatenating new E 11 x xd and v E lx
Keache + Keache |k], V Vacche + [V cachelllv].
(5)
where [-|1-] denotes tensor concatenation. Therefore, the attention can be computed as
Odec Softmax (qaec K <acke//
/d) V Vaache:
(6)
where qdec E R x denotes the current query. The attention output Odes E
ER Ixd xx is then sent to the
multi-layer perceptron (MLP) layer for the subsequent computation.
Explanation about the use of KV cache. Although previous works overlook the use of KV cache KV cache is already fundamental component for existing generative LLMs to guarantee the inference correctness. If we do not use KV cache, the model has to re-compute all the previous tokens at each decoding step, significantly increasing the overhead. Hence, we apply KV cache to private LLM inference by default, and our aim is to reduce the computation associated with KV cache size for better efficiency. We also show the generation efficiency without KV cache in Section 5 and
19 13 [2],
Appendix F
B
MPC Protocol Descriptions
B.1 Threat Model and Security
Consistent with previous works honest) security model in majostymajority 43 where parties follow the protocol specifications but
19,. MPCACHE adopts an honest-but-curious (a.k.a., semi-
25

---

may also try to learn more from the information than allowed. In our threat model, we assume all the parties are aware of the LLM architecture and number of pruned tokens, which consistent with HEPrune [88]. Seesaw [41], SENet [88] SNL [12], etc. We argue that this information does not compromise the client's data or inference results, nor does enable the client to access the model's parameters.
B.2
2PC Protocol
We follow the 2PC protocols proposed in BumbleBee [53] The protocols are built based on the 2-out-of-2 additive secret sharing (SS), where secret value x E 2 is shared by two random values To. 21 2 such that z Zo + 21 (mod 2¹), and party P; gets x; (denoted as [a:]). SS supports both addition and multiplication on the secret shares. Without special declaration, we compute in 64) which support arithmetic operations (e.g., + -, and ),, we refer to this type as arithmetic secrel sharing. Boolean secret sharing refers f = 1 where (+,-) and are replaced by bit-wise @ and A, respectively.
2 and omit (mod 2 for brevity. In the case of l > (e.g..
Addition. Ix + y] can be computed as (zo + yo, x1 + y1). where P. can compute its share locally. Multiplication. We write the multiplication of two shared values as [ayl = (Io - x (3o + +11) 2021 + 3130 where two cross terms Zol1; 21 can be computed using HE.
Tozo 319i
uses HE scheme that based on ring learning-withe with-error (RLWE). For more details about the 2PC protocol, please refer to [53 (5).
53
B.3
3PC Protocol
We follow the 3PC protocols proposed in PUMA 19)
The protocols are built based the 2-out-of-3
replicated secret sharing (RSS), where a secret value x E 2 is shared by three random values To, 31, 22 E 2 such that zo + I1 + x2 (mod 2¹), and party P. gets (1+1))))) (denoted as [x]].
Let (CI, C2, ca) be public constants, and ([=], [v]) be two secret-shared values. The secure addition and multiplication procedures are as follows:
Addition. [cı + C2y + es] can be computed as (Ci20 + C2to + Cs, C1 + C21/1, C1 + C282). where P. can compute its share locally. When (c1 1, C2 1, = 0), we get [x + y].
Multiplication. Parties follow steps: i) first, P; computes z; = s;yı + 1 + 2,/++ locally; ii) parties then perform re-sharing by letting P; sends = a; + z; P where og + 01 + 02
(P; can generate (4 using pseudorandom generators with negligible overhead as (56)) iii) finally, (1/6, 21), (z 2 (z2, +{)} form the 2-out-of-3 replicated secret shares of [xy]]
For more details about the 3PC protocol, please refer to 56 55
B.4 Token Gathering Protocol
Token gathering is used to retrieve tokens in the KV cache based the indices, which has the same functionality as frrch.gather(teen
indices) in PyTorch programming. We illustrate the overall
procedure in Figure 14
For brevity, in Algorithm we show the pipeline that retrieves one token from the key cache (we also omit the head dimension for simplification). The first step is converting ciphertext index [[id] into a ciphertext one-hot vector [o] E IR XX based on equal protocol II where denotes the number of tokens. Given a ciphertext key cache [K] E 7x where d denotes the embedding dimension, multiplying [o] with [K] (matrix-vector multiplication llMatVee) can generate an output with a dimension x d, which is the retrieved token. To extend the case to retrieve m tokens, concatenate one-hot vectors to form matrix [O] R=x and then multiply ]O] with [K] mmatrix-matrrn multiplication Ia to generate an output with a dimension m x d, which is the retrieved tokens.
Note that token gathering protocol is also used on the value cache, and indices are consistent with that of the key cache.
26

---

d
iis--0
6dom
6dsm2
Adr 73
Adrm3
ois-4
Indéx Tensor
Gathered Tensor
Step 1:
Key Tensor
One Conversion
Step 2: Multiply with Key (MatMul)
0
One-hot Vectors
Figure 14: Illustration of token gathering procedure where we give an example of retrieving tokens from 6 tokens.
Algorithm 2: Token gathering protocol Gaateer for retrieving one token
Input :A ciphertext key cache [K] E R and ciphertext index [id]]. Output: Key cache [K]' 1 with the selected token.
for [O, ..,.. T' do
L Parties jointly generate the one-hot vector as [[]]]] = Eqqua [[i]], i);
3 Parties jointly compute the retrieved key cache as [K| Mett Vecueee]] ([o], [K]]; return [K]
C Observation from Pattern Discovery of Large Attention Maps
is sufficient to use a few tokens within the observation window to distinguish the attention patterns
since the structure of attention maps is stable different decoding steps (50 78 22 42 In Figure 15
we visualize the large attention map with hundreds of tokens on the PIQA 4 dataset to further verify
observation in Section 3 As can be observed, there three types of tokens defined in Section 3
1) IA tokens in red blocks which usually appear as attention sinks mentioned in Streaming [76].
2) IC tokens in orange blocks; 3) UIA tokens in blue blocks; The pattern of attention maps motivates us to statically discard the UIA tokens which may have negligible impact on further generation, and dynamically select important tokens from IC tokens each decoding step for sparse attention computation.
D Pseudocode of MPCACHE Framework
We describe the overall flow of our MPCACHE in detail shown in Algorithm S
Layer
Layer
Layer
Observation Window
IA Token (Important
IC Token (Important
UIA Taken (Un-imporazz
Figure 15: Attention patterns across different layers on LLaMA-7B.
27

---

Algorithm 3: MPCACHE: KV cache eviction combining static and dynamic algorithm
Input Input sequence prompt; LLM model M; number of layers and attention heads L and H; dynamic selection ration 7) E 0, I]; three types of tokens IA, IC, and UTA (introduced in Scction cluster size s; decoding steps E.
Output: Attention oulput and evicted KV cache.
Step 1: Look-once static eviction during prefill stage
for
00.
....... 1]
Q Kt
V M(rroppt);
12/
then
ATTN (i)
sindow Soflmax (1 tem(prompt))) x ;. K(T);
(CAAA) static_ wew.eeeeicttttttee (1) vindoo);
else
IC,TAC + (TA,IC,U1AA)--))
Cross-layer index sharing (Section 4.4
K token token_gather (0) inder = (TA, IC)
V token gattnnggtttrrrtt (V() index (IA, IC)
10
Step 2: Query-aware dynamic selection during decoding stage
for E [0. .0.....
do for E 00, ... L- 1]db
13
14
if 1%2 = then
sim +- Sim(q (1)), K(te), celustrr_sste _szze 8); index topk(sim, k K(lee, size() n);
Follow Equation
17
else
index (t.e) (ndex
Cross-layer index sharing (Section
(1,e) + token_gather (tee), index index
19
Vlee) tathe_gatherr( v(be), index index (1)));;
20
21
(t.e) Softmax(q(1.)) K(leet/ /Va) v(l.e);
Sparse attention
return O, K, V.
100% Cache
LLM
100% Cache
Token Selector
10% KV
TXT
TXT
(a)
TEXT
TEST
Prefill Stage
Ieerative Decoding Stage
Inefficient
100% Cache
30% Cache
Token Selector
Efficient
TEXT TEX TDX
(b)
Prefill Stage (Static Eviction)
Iterative Decoding Stage
Figure 16: Paradigm comparison between (a) dynamic algorithm and (b) our proposed MP. CACHE combining static eviction and dynamic selection. MPCACHE discards unimportant tokens to reduce the decoding overhead (red texts mean the differences).
E Paradigm Comparison with Dynamic Algorithm
We compare the paradigm between dynamic algorithm and our MPCACHE as shown in Figure T6 Through performing static eviction during the prefill stage, we improve the efficiency of all decoding steps since the token selector (i.e., similarity approximation and top-k ranking) only needs to handle smaller number of tokens during the decoding stage (30% in this case).
28

---

F Supplemental Experiments
F.1 Supplemental Setups
Experimental environment. The model performance is evaluated with LongBench on an NVIDIA A100 80GB GPU in PyTorch. The latency is evaluated with Secretflow under the LAN setup 63 with 377MBps bandwidth and 0.3ms echo latency [63] on Intel(R) Xeon(R) Gold 5220R CPU @ 2.20GHz. To save GPU memory and avoid the aul-of-memory (OOM) error when processing long contexts, we leverage FlashAttention [4]] during the prefill stage. Since securely evaluating full-size 7B model in SPU exceeds our hardware resources, we set a smaller embedding dimension of 1024 in evaluation.
Datasets. In our experiments, we use XSUM 57 LongBench 2] and Beedle-in-a-Haysttar 23
LongBench is a benchmark for bilingual, multitask, and comprehensive assessment of long context understanding capabilities of large language models. We also use the XSUM [57 dataset which is used for the evaluation of abstractive single-document summarization systems. Needle-in-a-Haysttee is an evaluation method that randomly inserts key information into long texts to form prompts for LLMs. The test aims to detect whether models can extract such key information from extensive texts, thereby assessing the models' capabilities in processing and understanding long documents.
KV cache clustering configuration. For hierarchy, we in practice choose two-level hierarchical structure, i.e., n and when the final dynamic selection ratio a < 0.5, we drop 50% clusters at the 1st hierarchical level. For the XSUM dataset, we use a cluster size of 8 at the 1st hierarchical level and at the 2nd hierarchical level. For the long-context LongBench, we use larger clusters, i.e., 32 at the 1st hierarchical level and 16 at the 2nd hierarchical level.
Static eviction. During the static eviction, we compute the accumulated attention sum only using the last 20% tokens in the prompt. However, using 20% tokens still incurs CUDA out-of-memory (OOM) error when processing a long-context prompt (i.e., longer than 24k tokens). To solve this problem, we adaptively adjust the ratio to 10% tokens instead. We also notice that the choice of the ratio won't 't cause sigmificant performance fluctuations, so we omit the discussion in this paper.
How to securely determine the ayper-parameters e-g., eviction ratios in the realistic scenario? In practice, believe the static and dynamic eviction ratio should be determined based on two aspects: 1) the expected sequence length and 2) the latency that can be tolerated/afforded by the server and the client. Our framework proposes novel algorithm with configurable hyper-pane parameters to enable exploring the Pareto front of the LLM performance and efficiency. The framework has been validated across different benchmarks and different LLMs, which demonstrates its value and potential for practical use cases.
F.2 Detailed Descriptions about Baselines
follows fixed eviction pattern, i.e., keep the local tokens and initial tokens) across different decoding steps. H2O [91] and TOVA (58) statically prune the KV cache and these discarded tokens cannot be recovered at subsequent decoding steps. SnapKV 42 statically prunes the KV cache only during the prefill stage. InfLLM (74) employs block-level dynamic token selection
StreamingLLM 76
during the decoding stage. requires selecting several representative tokens within a block and computing the relevance score using these representative tokens. LongCache [47 uses the idea of cosine similarity between the query and key cache of previous tokens to select relevant tokens without static eviction and token clustering. Note that LongCache separates the positional embedding (PE) from the KV cache. Since our focus is on the dynamic selection metric in this work, we do not apply PE separation in LongCache.
F.3 Supplemental Ablation Studies
Effect of hyper-parameter a. To study how a impacts the similarity approximation, we select different at' different datasets as shown in F7 As can be observed, although the effects of different a do not occur in certain pattern, we can still discover some patterns related to the dataset from the trend in Figure [7 TriviaQA, the model may prefer larger a while it may prefer smaller on HotpotQA instead. Since a = 0.6 shows relatively better performance in these cases, we choose 0.6 by default in our experiments.
29

---

79.0
Dynamie Soleciin Ratio
TAYAON
PI Score (%)
78.0
40%
77.0
30%
31.0
HatporQA
30.5
2066
30.0
0.0
0.2
0.4
0.6
0.8
1.0
10'
ROUGE-2
Figure 17: The influence trend of sim- ilarity approximation with different values ranging from 0 to 1.
Comparison with average-basee similarity approxi- mation. MP means maximum dot product.
Figure 18:
Comparison with average-based similarity approximation. A straight- forward and efficient way to aggregate the information key cache cluster is the average. We compare our proposed method (a 0.6) with average-baad based similarity on the XSUM dataset with cluster size of 16 in Figure [8] Specifically, we perform dynamic selection with different ratios after 75% tokens are statically discarded. As can be observed, using average suffers from significant performance degradation under different ratios. With the compression ratio increasing, the degradation of the average-based method becomes more serious. An intuitive explanation is that using the average of cluster may make some important tokens averaged and ignored. In contrast, our approximation can effectively maintain the model performance. We theoretically analyze the similarity approximation algorithm Appendix
Full Cldas
LongCacte
MPCach:
*
F1 Scon:
Normalized
Normalized (MB)
Figure 19: Extension MPCACHE to 2PC pro- tocol.
Discussion on 2PC protocol. We evaluate the 2PC efficiency in Figure 19 It is observed that MPCACHE achieves 1.63x and 1.79x latency and communication reduction compared with the full cache, and 2.58 and 2.48x latency and communication reduction compared with LongCache. Since the multiplication communication in 2PC is larger than in 3PC, the cost of similarity approximation becomes higher. To solve this problem, we can leverage the random projection based on Johnson-Lindenstranne (JL) Lemma [4 reduce the dimensionality while preserving the token distance. We leave the research as our future work.
Static eviction ratio. We show the ablation study explain choice of static eviction ratio in Table 7 We choose the static eviction ratio that does not significantly affect the performance on the datasets, and different static eviction ratios influence the overall decoding performance.
G Theoretical Analysis of Similarity Approximation
given query q #x1xd key cache K E #x and value cache V Xxxxd the overall goal of KV cache eviction is to find an optimal policy P to minimize the gap between the attention outputs (here we omit V for simplification)
As mentioned in Section 2
Table 7: Model performance with different static eviction ratios HotpotQA.
D argmin Softmax(q K Softmax(q K'T)), )) (7)
Eviction Ratio (%)
Score
where K' is a subset of K selected by P. However, when grouping K into clusters for efficiency, the problem becomes challenging. We denote the key cache cluster as K. (cluster size is s), and our goal find way to accurately approximate the similarity between q
31.16
55
30.82
30.54
75
28.89
and the key cluster K.. This problem is equivalent to "how can we effectively aggregate the cluster
information obtain cluster representation and measure its importance?"
We assume there exists a function é that aggregates the key cluster K,, and we define the optimization problem
min
exp(q K-T) q (-o(K?))
(8)
30

---

Appooinniall
Transkomerr Datafow
Rasa Rate
Seeikely Iig
Eviction
Seircted
Attention
Weight +
Indleay
Effleiency Bottleneck
MPC Inforence
II Norsa
Bloute
Novm
MLP
Ourgut
T Ingut
Rdhonstract
Uoaaee
Ussuu
Figure 20: Overall secure inference data flow of MPCACHE during token generation.
Drawback of average-based clustering. As mentioned, the simplest way represent the cluster is the average and ((K (T) becomes -;= / /s. This happens be equivalent directly drop exp in Ejzo exp(q T))), introducing information loss. Infuitively, if there are tokens with low importance and tokens with high importance within one cluster, the overall importance will be averaged, leading the neglect of the crucial tokens.
Different from the average-based method, using the max dot product aims to protect the crucial tokens with large scores much as possible. This observation is aligned with [67].
MaxDotProduct q ((K) max q k. kEK.
In order to approximate maXkeK. q-k without accessing all the tokens in K., we utilize the bounding volume proposed by [36]. Our optimizations are described in Section 4.3
H
Overall Secure Inference Framework
Take 2PC as an example in Figure 20 we illustrate the secure inference framework following 53 where the server owns the proprietary LLM parameter and the client possesses private input data. During inference, the data is secretly shared between two parties. Linear layers are computed using the HE protocol, and non-linear layers require interactive protocols between the two parties based on oblivious transfer (OT) and HE. Figure 20 illustraaees the detailed data flow of MPCACHEE during the token generation.
31


Reviews:
[{"review_id": "2UVvdCNNKP", "reviewer": "Reviewer_AHwV", "summary": "The paper presents MPCache, a kKV cache eviction framework optimized for multi-party computation (MPC)-based private LLM inference. It combines static eviction during the prefill stage to prune unimportant tokens. Also, MPCache is incorporated with dynamic, query-aware cluster-based selection to further reduce the KV cache at each decoding step.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper introduces a hybrid static + dynamic KV eviction strategy tailored to MPC constraints\n2. This is a training-free model that can be directly applied on existing LLMs\n\nWeaknesses:\n1. Optimizations are largely heuristic and empirical, lacking formal approximation bounds or convergence analysis.\n2. Generally speaking, the experiment setup is not sufficient. For example, efficiency section $5.3$ Fig.10, only MHA models like Llama-2 are used, which gives a limited demonstration of how efficient MPCache is on SOTA models. \n3. In the section $4.4$, the authors missed a citation when discussing index sharing across adjacent layers. This finding has been extensively discussed in the paper: [https://arxiv.org/abs/2410.05076]{https://arxiv.org/abs/2410.05076}.", "was_revised": true, "final_justification": "My concern has been addressed. I have raised my score. Please include the updated experiments in the camera-ready version to ensure the effectiveness of the approach.", "rebuttal": "We sincerely thank Reviewer AHwV for your thoughtful feedback!\n\n---\n\n**Q1:** Optimizations are largely heuristic and empirical, lacking formal approximation bounds or convergence analysis.\n\n**A1:** Thank you for your insightful comment. For the **similarity approximation,** we have provided rigorous derivation in Eq. (1)-(2) and theoretical analysis in Appendix G, which demonstrate that MPCache better preserves the clusters with large $qK$ values, i.e., important tokens, and thus, achieves higher accuracy. This analysis is grounded in the concept of bounding volumes from computer graphics [1-4], which we adapt to formally analyze and approximate token importance under constrained KV cache budgets.\n\nFor other optimizations proposed by MPCache: \n\n- **Cross-layer index sharing** is motivated by inter-layer consistency patterns, as observed in Figures 3 and 8.\n- **Hierarchical clustering** utilizes the tree structure to effectively balance efficiency and accuracy. We provide the computational complexity analysis: let $T$ be the total token number, $c_1$ and $c_2$ be the cluster number at the 1st and 2nd level,  and $k$ be the preserved token number. Therefore, the complexity of full cache is $O(T)$, and hierarchical clustering only requires $O(c_1+c_2+k)$, where $c_1, c_2, k \\ll T$ in our experiments.\n\nIn conclusion, while some of our optimizations are not derived from formal theory, they are grounded in empirical observations which are **consistently verified across a wide range of datasets and models, leading to strong practical credibility.** We will incorporate more formal analysis in the revised version to further strengthen our work.\n\n---\n\n**Q2:** The experiment setup is not sufficient. In Figure 10, only MHA models like Llama-2 are used, which gives a limited demonstration of how efficient MPCache is on SOTA models.\n\n**A2:** Thank you for the suggestion. **MPCache is generally applicable to different model architectures like Grouped Query Attention (GQA)** used in recent SOTA models, e.g., Llama-3 and Qwen-3. GQA reduces KV storage and the number of linear projections (e.g., $XW^K$), but **the computation of attention—$\\text{Softmax}(qK^\\top)V$—remains the same as MHA**, since each query still attends to all keys and values within its group.\n\nSince our method is designed for MPC, **only computation reduction leads to lower communication and latency, whereas storage savings do not.** As a result, the benefits of MPCache naturally extend to both MHA and GQA. In the table below, we add results on Llama-3-8B with GQA at different sequence lengths. **The result shows significant latency and communication improvements, which is consistent with MHA.**\n\nWe will supplement our experimental setup and incorporate these results into the revised version.\n\n| **Sequence Length** | **512 (Lat. /Comm.)** | **1024 (Lat. /Comm.)** | **2048 (Lat. /Comm.)** |\n| --- | --- | --- | --- |\n| Full Cache | 50.1s / 0.98GB | 73.1s / 1.76GB | 108.2s / 3.46GB |\n| LongCache (5% Cache) | 56.5s / 0.97GB | 86.3s / 2.03GB | 154.9s / 4.94GB |\n| ArkVale (5% Cache) | 37.3s / 0.42GB | 55.6s / 0.54GB | 90.02s / 0.73GB |\n| MPCache (5% Cache) | 26.4s / 0.24GB | 38.9s / 0.30GB | 62.54s / 0.42GB |\n| **Improvement over Full Cache** | **1.89$\\times$ / 4.08$\\times$** | **1.87$\\times$ / 5.86$\\times$** | **1.73$\\times$ / 8.23$\\times$** |\n\n---\n\n**Q3:** The authors missed a citation.\n\n**A3:** Thank you for your kind suggestion! We will include the related paper in our revised version.\n\n---\n\n**Lastly, thanks so much for helping us improve this work through your valuable feedback. If you have any additional questions or anything you would like to discuss further, please feel free to let us know. If you find that we have addressed your concerns, please kindly consider re-evaluating our work. Thank you once again for your time and effort!**\n\n---\n\n**References:**\n\n[1] Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools, 1997.\n\n[2] Collision Detection Using Axis Aligned Bounding Boxes. Simulations, Serious Games and Their Applications. Springer Singapore, Singapore, 2014.\n\n[3] Bounding volume. Wikipedia, April 2024.\n\n[4] Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE transactions on Visualization and Computer Graphics 4.1 (1998)"}, {"review_id": "X9IGsSzgSr", "reviewer": "Reviewer_mW9c", "summary": "This work proposes a framework for properly integrating KV caching into MPC-based LLM inference to reduce inference costs. To do this, they use an MPC-friendly similarity approximation, hierarchical KV cache clustering, and a cross-layer index-sharing strategy to reduce the overhead of dynamic token selection. Their experimental results demonstrate strong performance and efficiency results compared to existing KV cache schemes.", "questions": "- Is obersvation 1 a general observation, not specific to the MPC setting?\n- Is this work the first to address optimization in MPC-based LLM inference with KV cache?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Tackles an important problem of revising the KV cache scheme to be more MPC-friendly\n- The writing style of the paper is great, with clear descriptions about the problem setup, motivational observations, and the proposed method\n- Lots of figures are utilized in the main text that help provide insight into important claims\n- The ideas proposed in the MPC-friendly dynamic KV cache selection section of the paper seem very interesting and innovative\n- Code is open-source and available for reproducibility \n- Experimental evaluations are comprehensive, on both performance and efficiency, with the proposed method comparable or outperforming existing static and dynamic KV cache methods\n\nWeaknesses:\nI have no major complaints about the work. I only have some minor complaints that may need to be addressed:\n- A legend is needed for Figure 1, as there are colors used in some of the graphs, and I do not know what they correspond to. \n- The descriptions for the figures and tables should be more comprehensive and self-contained. For example, for Figure 9 and Table 3, I do not know what models are being evaluated on and what performance metrics are being used. \n- For the tables, it would be visually easier to bold face the numbers that are best amongst the others\n- It would be insightful to include a non-KV cache baseline for both the performance and efficiency baselines", "was_revised": true, "final_justification": "After reading through the other reviewers' and rebuttals, I will still keep my score. The paper presentation is easy to follow, and the core ideas/contributions are interesting. Their rebuttal addressed many of the concerns raised by other reviewers and should be incorporated into their final version. Hence, I am generally supportive of the work.", "rebuttal": "We sincerely thank Reviewer mW9c for your appreciation of our work and thoughtful feedback!\n\n---\n\n**Q1:** Legend missing in Figure 1.\n\n**A1:** Thanks for pointing this out! In Figure 1, blue bar means attention, orange bar means MLP, green bar means LayerNorm, purple bar in slash means similarity approximation, yellow bar in slash means top-k ranking, and green bar in slash means token gathering. We have added the legend in our revised version.\n\n---\n\n**Q2:** The descriptions for the figures and tables should be more comprehensive.\n\n**A2:** Thanks for your kind advice! Figure 9 and Table 3 are evaluated on LongChat-7B-V1.5-32K on the LongBench [1] benchmark. We will carefully improve the descriptions for the figures and tables in our revised version.\n\n---\n\n**Q3:** For the tables, it would be visually easier to bold face the numbers that are best.\n\n**A3:** Thanks for your suggestion! We will improve the tables to make the results clearer.\n\n---\n\n**Q4:** It would be insightful to include a non-KV cache baseline for both the performance and efficiency baselines.\n\n**A4:** Thank your for your valuable advice! For performance, non-KV cache is consistent with the full cache, since the purpose of the KV cache is to reduce repeated computation (please refer to Appendix A.3 for details). \n\nFor efficiency, compared with using KV cache, non-KV cache baseline incurs hundreds of times latency, communication, and memory. Here, we provide an example: non-KV cache baseline requires more than 800GB of communication with a input sequence length of 2048. This comparison demonstrates that KV cache drastically reduces the overhead and further highlights the efficiency gains achieved by MPCache.\n\n| Method | Communication (GB) | Latency (s) |\n| --- | --- | --- |\n| Non-KV Cache Baseline | 829.4 | 18144 |\n| + KV Cache (Full Cache) | 3.460 | 111.4 |\n| + MPCache | 0.413 | 61.86 |\n\nWe promise to add comprehensive results of the non-KV cache baseline in our revised version.\n\n---\n\n**Q5:** Is observation 1 a general observation, not specific to the MPC setting?\n\n**A5:** Yes. Observation 1 focuses on the KV cache sparsity analysis and classification, which motivates us to combine static and dynamic KV cache compression for LLM efficiency improvement.\n\n---\n\n**Q6:** Is this work the first to address optimization in MPC-based LLM inference with KV cache?\n\n**A6:** Yes. This work is the first research to introduce KV cache for MPC-based LLM inference. Also, this is the first to study long-context inference in MPC. In this paper, to alleviate the heavy overhead introduced by long contexts (i.e., large KV cache size), we further propose a series of MPC-friendly optimizations for KV cache compression to improve the overall efficiency while preserving the accuracy.\n\n---\n\n**References:**\n\n[1] Bai, Yushi, et al. \"Longbench: A bilingual, multitask benchmark for long context understanding.\" arXiv preprint arXiv:2308.14508 (2023)."}, {"review_id": "gLi6wuguZv", "reviewer": "Reviewer_suRu", "summary": "This paper presents an MPC-friendly KV cache eviction framework. MPC is a cryptography scheme that allows multiple parties to work together on the computation with leaking the plaintext. However, some operations are not efficient in MPC in terms of computation latency and communication, such as comparison and non-linear operations. The existing KV cache eviction on plaintext computation is not efficient in MPC. This paper studies the KV cache eviction in the context of MPC. The proposed scheme combines static eviction and dynamic selection. It reduces the expensive max and similarity approximation operations needed, and also has optimizations like hierarchical clustering and cross-layer index-sharing strategy. The evaluation shows the proposed eviction outperforms the baseline KV cache eviction mechanism in both model performance and latency.", "questions": "* Please explain the color coding in Figure 1.\n\n* What is the implementation like in Figure 1(b) and (c)? Is KV cache used? If so, what KV cache eviction algorithm is used?\n\n* Is the latency in Table 3 per inference or for X number of queries? How the numbers are measured are not clearly stated in the paper not the evaluation.\n\n* Can you provide a further breakdown in \"model\" Figure 11? Earlier in the paper, you mentioned that softmax accounts for the majority of the cost. How about after your KV cache optimizations?\n\n* Can you provide insights on what the performance will be like if the networking has longer latency or bandwidth?", "limitations": "I agree with the authors that the proposed scheme is general. However, the resulting MPC is still slow for practical use. A discussion on MPC for decoder models can be added.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n+ (Significance and Originality) The first study on KV cache eviction in the MPC framework. This work will make the decoder models more feasible in MPC. I like the proposed schemes that reduce the number of max operations.\n+ (Quality) The proposed optimizations are derived from observations in detailed performance profiling. The paper is well-written and supported by solid experiments.\n\nWeaknesses\n- (Quality) The paper can provide more details on the performance improvement due to each of the optimizations. The current results do not give insights into the impact of each optimization.\n- (Quality) The evaluation metrics and how it is measured are not stated.\n- (Quality) The evaluation does not test under different network setups.\nIf the authors cannot evaluate the framework under different network settings, the computation and communication breakdown (i.e., percentage of time in communication vs. computation, or are they pipelined?) should be provided at least. \n\n- (Clarity) Some figures miss necessary legends. \n-- For example, Figure 1 did not mark what each color means in the breakdown. \n-- In Figure 1(d), the KV cache choice of the eviction baseline [47] can be biased. Table 3 shows that baseline [47] has worse latency performance than baseline InfLLM.\n\n-- It should also be stated clearly that F1 score is used as the model performance metric.", "was_revised": true, "final_justification": "Thanks for the response. My clarification questions are addressed. For practical use, the concerns remain, and I will keep my score. In general, I still support the paper.", "rebuttal": "We sincerely thank Reviewer suRu for your thoughtful feedback!\n\n---\n\n**Q1:** Provide more details on the performance improvement due to each of the optimizations.\n\n**A1:** Thanks for you advice! We here summarize  the impact of each optimization from the perspective of accuracy and efficiency.\n\n- Static eviction algorithm: unimportant KV cache is pruned based on the attention scores with negligible overhead. It does not affect the prefill stage and remain partial KV cache after the prefill stage to **improve the overall efficiency by ~60% without degrading accuracy.**\n- Dynamic selection algorithm: 1) similarity approximation optimization: a clustering-based optimization is proposed and it preserves the impact of important tokens within a cluster as much as possible. Hence, our selection method is **accurate and efficient (further improve overall efficiency by ~60%);** 2) linearization & reordering and hierarchical clustering optimizations: they aim to improve the efficiency of similarity approximation by removing MPC-expensive operators and progressive selection **(reduce KV cache selection overhead by ~80%) without significantly affecting accuracy;** 3) cross-layer index sharing optimization: due to the high similarity between adjacent layers as observed in Section 3, this optimization directly **reduces the overhead of KV cache selection by 50% without degrading accuracy.**\n\nIn conclusion, our optimizations are supported either by theoretical analysis or by empirical observations. These optimizations work together to improve the efficiency while preserving accuracy. **Experimental analysis can be found in our step-by-step ablation studies in Section 5.4.** We will add more discussions in our revised version.\n\n---\n\n**Q2:** The evaluation metrics and how it is measured are not stated.\n\n**A2:** Thanks for your suggestion! F1 score used in LLM generation task is calculated as the harmonic mean of precision and recall at the token level: F1=2$\\times$Precision$\\times$Recall/(Precision+Recall), where precision measures the proportion of tokens in the generated output that also appear in the answer, and recall measures the proportion of tokens in the answer that are correctly included in the generated output.\n\nIn this paper, we follow LongBench [11] to measure the metrics, and we will state the metric and measurement details clearer in our revised version.\n\n---\n\n**Q3:** The evaluation does not test under different network setups.\n\n**A3:** Thanks for your valuable advice! We provide the breakdown of computation vs. communication latency to better understand the protocols. We evaluate the 3PC protocol on Llama-2-7B to generate 1 token with a sequence lengths of 512, as shown in the table below:\n\n| Network | Total Lat. (s) | Comm. (GB) | Comm. Lat. (s) | Comput. Lat. (s) | **+ MPCache** |\n| --- | --- | --- | --- | --- | --- |\n| LAN | 51.2 | 1.01 | 2.679 (5.23%) | 48.521 (94.77%) | **25.5s (2.0$\\times$) / 0.24GB** |\n| WAN | 73.8 | 1.01 | 25.25 (34.2%) | 48.521 (65.8%) | **31.2s (2.3$\\times$) / 0.24GB** |\n\nAs observed, under different network setups, communication improvement remains unchanged. In contrast, latency improvement can vary depending the network setups. For WAN with lower bandwidth, the improvement can be slightly higher, i.e., 2.3x since KV cache eviction directly reduces the communication volume.\n\nWe will include more comprehensive experiments and analysis about the network setups in our revised version.\n\n---\n\n**Q4:** Some figures miss necessary legends and explain the color coding in Figure 1.\n\n**A4:** Thanks for pointing out our oversights! We have carefully revised the writing to make our paper clearer. In Figure 1, blue bar means attention, orange bar means MLP, green bar means LayerNorm, purple bar in slash means similarity approximation, yellow bar in slash means top-k ranking, and green bar in slash means token gathering.\n\n---\n\n**Q5:** Implementation like in Figure 1(b) and (c). Is KV cache used and what KV cache eviction algorithm is used?\n\n**A5:** Figure 1(b) uses the both 2PC and 3PC protocols on GPT-2 using the Secretflow framework. Figure 1(c) uses the 3PC protocol to evaluate Softmax. KV cache is used here to avoid redundant re-computation of KV cache (refer to Appendix A.3 for details). But in Figure 1(b) and (c), KV cache eviction algorithm is not used since they are profiled to analyze the efficiency bottleneck with full cache, which motivate us to compress the KV cache.\n\nWe will carefully improve our writing to make the paper clearer in our revised version.\n\n---\n\n**Q6:** Latency evaluation in Table 3.\n\n**A6:** The latency in Table 3 is measured by generating one token on Llama-2 given one input with a sequence length of 1024 tokens. We will clarify all the measurements in our revised version.\n\n---\n\n**Q7:** Provide a further breakdown in \"model\" Figure 11.\n\n**A7:** We show the model-level communication breakdown with a sequence length of 1024 in the table below. As observed, before optimization, Softmax dominates the total cost. After optimization, Softmax overhead becomes very small, leading to significant overall efficiency improvement. We will include these experiments in our revised version.\n\n| Method | Softmax (MB) | MLP (MB) | Others (MB) | Total (MB) |\n| --- | --- | --- | --- | --- |\n| Full Cache | 1242.7 | 184.32 | 436.66 | 1863.68 |\n| + MPCache | 68.19 | 184.32 | 23.97 | 276.48 |\n\n---\n\n**Q8:** The resulting MPC is still slow for practical use. A discussion on MPC for decoder models can be added.\n\n**A8:** Thanks for your valuable advice! We agree that MPC incurs more communication overhead and is still under research, but we believe MPC has strong potential. MPC has been used in practical applications such as healthcare [12] and finance [13]. In recent years, there is a significant amount of research on MPC inference for LLMs, which is more complex and expensive [1-10]. Through our optimizations, **MPCache achieves up to 2.01$\\times$ latency and 8.37$\\times$ communication reduction.**\n\nIn addition, MPCache is orthogonal to both protocol and hardware, and thus can be integrated with future advanced protocols and hardware to further enhance usability. For example, according to Piranha [14], GPU can accelerate MPC by 16-48$\\times$. Therefore, **we believe this research has important academic value and can promote the practical application of MPC.**\n\nIn our revised version, we will add more discussions and the limitation section regarding the MPC-based decoder models.\n\n---\n\n**References:**\n\n[1] Zhang, Yancheng, et al. \"CipherPrune: Efficient and Scalable Private Transformer Inference.\" ICLR 2025.\n\n[2] Lu, Wen-jie, et al. \"Bumblebee: Secure two-party inference framework for large transformers.\" NDSS 2025.\n\n[3] Li, Zhengyi, et al. \"Nimbus: Secure and Efficient Two-Party Inference for Transformers.\" NeurIPS 2024.\n\n[4] Pang, Qi, et al. \"Bolt: Privacy-preserving, accurate and efficient inference for transformers.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[5] Rathee, Deevashwer, et al. \"MPC-Minimized Secure LLM Inference.\" arXiv preprint arXiv:2408.03561 (2024).\n\n[6] Zheng, Fei, et al. \"PermLLM: Private Inference of Large Language Models within 3 Seconds under WAN.\" arXiv preprint arXiv:2405.18744 (2024).\n\n[7] Li, Dacheng, et al. \"Mpcformer: fast, performant and private transformer inference with mpc.\" ICLR. 2023.\n\n[8] Zeng, Wenxuan, et al. \"Mpcvit: Searching for accurate and efficient mpc-friendly vision transformer with heterogeneous attention.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023.\n\n[9] Hou, Xiaoyang, et al. \"Ciphergpt: Secure two-party gpt inference.\" Cryptology ePrint Archive (2023).\n\n[10] Dong, Ye, et al. \"Puma: Secure inference of llama-7b in five minutes.\" arXiv preprint arXiv:2307.12533 (2023).\n\n[11] Bai, Yushi, et al. \"Longbench: A bilingual, multitask benchmark for long context understanding.\" arXiv preprint arXiv:2308.14508 (2023).\n\n[12] Ahammed, Md Fahim, and Md Rasheduzzaman Labu. \"Privacy-preserving data sharing in healthcare: advances in secure multiparty computation.\" Journal of Medical and Health Studies 5.2 (2024): 37-47.\n\n[13] Salako, Ademola Oluwaseun, et al. \"Securing confidentiality in distributed ledger systems with secure multi-party computation for financial data protection.\" Journal of Engineering Research and Reports 27.3 (2025): 352-373.\n\n[14] Watson, Jean-Luc, Sameer Wagh, and Raluca Ada Popa. \"Piranha: A GPU platform for secure computation.\" 31st USENIX Security Symposium (USENIX Security 22). 2022."}, {"review_id": "2wgFIjbp9j", "reviewer": "Reviewer_kcBh", "summary": "The authors mainly address the high latency issue in securely performing KV cache eviction. To reduce the cost of similarity computation, they propose cache clustering, where similarity is calculated at the cluster level and refined progressively in a coarse-to-fine manner. To improve effectiveness, instead of using the mean of each cluster, they measure similarity using the maximum and minimum key values within the cluster. Additionally, they further enhance efficiency by exploiting the similarity of eviction patterns across adjacent layers, allowing similarity computation to be performed only on selected layers. Experiments conducted on various datasets and architectures demonstrate that the proposed method is both more efficient and effective compared to existing methods.", "questions": "* The reduction in communication cost is significant, but the corresponding latency acceleration appears to be relatively limited. Could the authors provide an analysis explaining this discrepancy?\n* Figures 7 and 8 appear after Figure 9 and are placed far from the text where Figure 7 is first mentioned. It would be better to relocate them closer to their first reference for improved readability.", "limitations": "The paper does not explicitly address its limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n* The authors propose a novel and efficient method using cache clustering.\n* They conduct extensive experiments to demonstrate the effectiveness of the proposed method.\n\n---\n\n###  Weaknesses\n* The proposed method appears to achieve approximately a 2× speedup in Figure 10. However, according to Figure 3(a), static eviction also shows no performance degradation up to 60%. Therefore, when compared to static eviction methods applied at a 60% rate, the proposed method might offer similar performance but little to no advantage in terms of speed improvement, since static eviction approaches are more efficient than dynamic eviction. Therefore, a comparison with static eviction at a 50–60% ratio in terms of both latency and performance is necessary.\n* Since the method requires additionally storing the minimum and maximum values for each cluster, it is expected to incur higher memory usage. In large models with long sequence lengths, this overhead could become significant. It would be helpful to include a comparison of memory consumption to assess this impact.\n* While the improvement in latency over existing methods is understandable, the reason for the performance improvement is not convincing at a high level. It would be helpful if the authors could provide a high-level analysis explaining why the proposed method outperforms the dynamic KV cache baseline in terms of effectiveness.", "was_revised": true, "final_justification": "While the latency improvement is somewhat limited, the method is novel and meaningful in that it reduces both latency and memory usage. Therefore, I have raised my score to 4: borderline accept.", "rebuttal": "We sincerely thank Reviewer kcBh for your thoughtful feedback!\n\n---\n\n**Q1:** Comparison with static eviction at a 50–60% ratio in terms of latency and performance.\n\n**A1:** Thank you for the insightful comment. First, we would like to clarify that the latency of Transformer consists of attention and MLP, and KV cache eviction only optimizes attention. **The 2$\\times$ latency reduction shown in Figure 10 represents an end-to-end result, and thus, it is not equivalent to 50% static eviction.** \n\nIn fact, achieving the **~2$\\times$ latency reduction requires compressing the KV cache to less than 10%**. As shown in the table below, **solely** **applying 60% static eviction leads to limited efficiency improvement (i.e., only 1.21$\\times$** **latency and 1.83$\\times$ communication** **reduction**), which is significantly lower than MPCache. Meanwhile, using only static eviction to reduce latency by ~2$\\times$ would result in substantial accuracy degradation (this can be also observed in SnapKV in Figure 9).\n\n| Method (Reserved KV Cache) | Latency (s) | Communication (GB) | Accuracy (%) |\n| --- | --- | --- | --- |\n| Full KV Cache (100%) | 75.52 | 1.82 | 26.54 |\n| Pure Static Eviction (40%) | 62.12 (1.21$\\times$) | 0.99 (1.83$\\times$) | 25.56 |\n| Pure Static Eviction (8%) | 40.32 (1.87$\\times$) | 0.36 (5.06$\\times$) | 16.80 **(Significant Drop)** |\n| MPCache (8%) | 44.39 (1.70$\\times$) | 0.41 (4.44$\\times$) | 23.86 |\n\nIn contrast, MPCache builds upon static eviction and further perform dynamic selection to identify the most important KV cache. This allows for **more aggressive compression, especially for communication cost (i.e., 1.7$\\times$ latency and 4.4$\\times$ communication reduction) while maintaining accuracy**, achieving significantly higher accuracy than using static eviction alone.\n\nWe will include these clarifications and the comparison results in our revised version.\n\n\n---\n\n**Q2:** This work requires additionally storing the min and max for each cluster, it is expected to incur higher memory usage.\n\n**A2:** Thanks for your thoughtful consideration. We would like to clarify that the memory usage introduced by storing min/max values is **negligible compared to the KV cache.** Specifically, KV cache has a dimension of $(H, T, D)$, where $H$, $T$, and $D$ are head number, token number, and hidden dimension per head, respectively. In contrast, min/max values are stored per cluster, resulting in a much smaller dimension of $(H, T/s, D)$, where $s$ denotes cluster size. It means min/max values require only $1/s$ memory compared to KV cache. In our experiments, the cluster size $s$ is very large, i.e., 32, resulting in only $1/32$ of the KV cache size.\n\nFor example, for a Llama-2-7B model and a sequence length of 16K, storing KV cache requires 7.8 GB, while storing min and max values requires only 250 MB of storage (in FP16 precision), which is ~3% of KV cache size.\n\nSince the **min/max value requires minimal storage, and communication and running time are the dominant bottleneck in current MPC protocols**, we prioritize communication and latency reduction in this work. We will add more explanations regarding the memory usage in our revised version.\n\n---\n\n**Q3:** The reason for the performance improvement is not convincing at a high level.\n\n**A3:** We analyze the effectiveness of MPCache at a high level as follows:\n\n- **Comparison with average-based clustering methods.** The widely adopted dynamic KV cache method is to represent each cluster using average of all tokens within it. However, this method suffers from the drawback of **averaging out the token importance,** making it difficult to retain highly informative tokens given a KV cache budget. In contrast, **MPCache is guided by the principle that similarity approximation should preserve the influence of important tokens within each cluster**. So, we build a novel similarity approximation method that utilizes the maximum dot product between the query and key clusters, rather than the average, to better approximate token importance. This intuition is empirically validated across different models and datasets, which shows that our design improves the selection of important tokens under a constrained KV cache budget.\n\n- **Comparison with non-clustering (token-wise) methods.** In long-context scenarios, prior studies has observed attention noise [1-3], where the dot product between the query and key becomes less reliable in reflecting token importance when the sequence is very long. Hence, compared to these token-wise similarity approximation methods, MPCache utilizes cluster-wise granularity to reduce the approximation complexity and **mitigate the attention noise** to some extent, enabling more robust and accurate token selection, especially for long sequences.\n\nIn conclusion, MPCache improves performance by using a novel similarity approximation that effectively preserves clusters with influential tokens, which is especially useful for long-context scenarios. We will clarify these motivations and high-level insights in the revised version.\n\n---\n\n**Q4:** The reduction in communication cost is significant, but the corresponding latency acceleration is relatively limited.\n\n**A4:** The primary reason for this discrepancy is that the **communication scales proportionally with the input dimension,** resulting in a significant decrease when the KV cache is compressed. In contrast, **latency is influenced by multiple factors,** including computation time, the number of communication rounds in MPC, and network setups such as bandwidth and transmission delay. These components **do not scale linearly with input size**, thereby limiting the overall latency reduction. \n\nFurthermore, as our current implementation runs on CPU, leveraging GPU to accelerate computation in future work could yield higher latency gains.\n\nWe will clarify these points and include this discussion in our revised version. \n\n---\n\n**Q5:** It would be better to relocate the figures closer to the first reference for improved readability.\n\n**A5:** Thanks for your kind advice! We will adjust the locations of figures and texts carefully in our revised version.\n\n---\n\n**Lastly, thanks so much for helping us improve this work through your valuable feedback. If you have any additional questions or anything you would like to discuss further, please feel free to let us know. If you find that we have addressed your concerns, please kindly consider re-evaluating our work. Thank you once again for your time and effort!**\n\n---\n\n**References:**\n\n[1] Ye, Tianzhu, et al. \"Differential transformer.\" arXiv preprint arXiv:2410.05258 (2024).\n\n[2] Adnan, Muhammad, et al. \"Keyformer: Kv cache reduction through key tokens selection for efficient generative inference.\" Proceedings of Machine Learning and Systems 6 (2024): 114-127.\n\n[3] Wang, Xue, et al. \"S3attention: Improving long sequence attention with smoothed skeleton sketching.\" IEEE Journal of Selected Topics in Signal Processing (2024)."}, {"review_id": "4wQC3GcTGt", "reviewer": "Reviewer_5USt", "summary": "The paper proposes MCPCache, a novel KV cache eviction strategy for use in LLM inference when performed via MPC. They thoroughly review and compare the state of the art and justify why their strategy works.", "questions": "Please address how the speed tradeoffs here fit into the limitations of the broader approach.", "limitations": "No, see above.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "It's a good paper, with a clear framework for why it is designed the way it is, and an explanation of how speed is improved via the KV eviction strategy.  \n\nStregths:\n- Clear explanation of why the strategy works\n- The extensive experiments demonstrate significant improvements over existing methods. MPCACHE achieves a reduction of up to 2.01x latency and 8.37x communication. \n\nWeaknesses:\n- No Explicit Limitations Section: The paper does not have a dedicated \"Limitations\" section, and the authors state in the checklist that the paper has no limitations. MPC fundamentally has limitations due to communication complexity and isn't widely used in AI deployments for that reason.\n-More generally, it's unclear with these speedups if anyone would be willing to accept the complexity of MPC inference.\n- Assumption of Architectural Knowledge: The security model assumes that all parties are aware of the model architecture and the number of pruned tokens. This is fine and aligns with past literature, but it forgoes significant privacy.", "was_revised": true, "final_justification": "The authors have vigorously and thoroughly responded to all the reviewer comments.\n\nWhile there are still challenges with the underlying pragmatic utility of this scope of research, they have argued for its novelty and soundness.\n\nI am happy to increase my review to an acceptable (from borderline acceptable) and retain my confidence.", "rebuttal": "We sincerely thank Reviewer 5USt for your thoughtful feedback!\n\n---\n\n**Q1:** No explicit limitations section and address how the speed tradeoffs fit into the limitations of the broader approach.\n\n**A1:** Thanks for your valuable advice! We agree that MPC incurs more communication overhead and is still under research, but we believe MPC has strong potential for these reasons: 1) In the era of LLM, the issue of data privacy becomes more severe, and there is a strong demand for LLM's privacy protection. For example, General Data Protection Regulation (GDPR) provides policy-level protections for LLM's data privacy; 2) MPC provides cryptographically-strong privacy protection for both data and parameters and is also independent of the hardware platforms; 3) In recent years, there is a significant amount of research on MPC inference, especially for LLMs [1-10].\n\nThrough our optimizations, **MPCache achieves up to 2.01$\\times$ latency and 8.37$\\times$ communication reduction.** In addition, MPCache is **orthogonal to both protocol and hardware,** and thus can be integrated with future advanced protocols and hardware to further enhance usability. For example, according to Piranha [11], GPU can accelerate MPC by 16-48$\\times$.\nTherefore, **we believe this research has important academic value and can promote the practical application of MPC.**\n\nIn our revised version, we will add the limitation section to elaborate the gap between private inference and the plaintext counterpart.\n\n---\n\n**Q2:** Assumption of architectural knowledge.\n\n**A2:** Thanks for your thoughtful consideration. Our threat model is consistent with previous studies that the model architecture and pruning ratio are public. We believe this is reasonable in real-world applications, where users typically know the model architecture and pruning ratio (or speedup) when using the service. For example, **Gemini [12] discloses the model architecture and optimizations while keeping model parameters private.**\n\nImportantly, our adopted threat model does not compromise the client's data, nor does it enable the client to access the model's parameters, which is **aligned with the security goal of MPC.**\n\n---\n\n**References:**\n\n[1] Zhang, Yancheng, et al. \"CipherPrune: Efficient and Scalable Private Transformer Inference.\" ICLR 2025.\n\n[2] Lu, Wen-jie, et al. \"Bumblebee: Secure two-party inference framework for large transformers.\" NDSS 2025.\n\n[3] Li, Zhengyi, et al. \"Nimbus: Secure and Efficient Two-Party Inference for Transformers.\" NeurIPS 2024.\n\n[4] Pang, Qi, et al. \"Bolt: Privacy-preserving, accurate and efficient inference for transformers.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[5] Rathee, Deevashwer, et al. \"MPC-Minimized Secure LLM Inference.\" arXiv preprint arXiv:2408.03561 (2024).\n\n[6] Zheng, Fei, et al. \"PermLLM: Private Inference of Large Language Models within 3 Seconds under WAN.\" arXiv preprint arXiv:2405.18744 (2024).\n\n[7] Li, Dacheng, et al. \"Mpcformer: fast, performant and private transformer inference with mpc.\" ICLR. 2023.\n\n[8] Zeng, Wenxuan, et al. \"Mpcvit: Searching for accurate and efficient mpc-friendly vision transformer with heterogeneous attention.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023.\n\n[9] Hou, Xiaoyang, et al. \"Ciphergpt: Secure two-party gpt inference.\" Cryptology ePrint Archive (2023).\n\n[10] Dong, Ye, et al. \"Puma: Secure inference of llama-7b in five minutes.\" arXiv preprint arXiv:2307.12533 (2023).\n\n[11] Watson, Jean-Luc, Sameer Wagh, and Raluca Ada Popa. \"Piranha: A GPU platform for secure computation.\" 31st USENIX Security Symposium (USENIX Security 22). 2022.\n\n[12] Comanici, Gheorghe, et al. \"Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities.\" arXiv preprint arXiv:2507.06261 (2025)."}]

Author rebuttal:

Meta-review: The paper introduces a framework called MPCache. It is designed to make private (in MPC sense) large language model (LLM) inference faster. While secure multi-party computation (MPC) protect user data, it is known to be slow. MPCache speeds up MPC by a novel approach to the key-value (KV) caching. It combines a static method to discard unimportant cache data and a dynamic method to select only a small, relevant subset of the cache for each step. 

Reviewers found the hybrid approach of MPCach to be a novel and important contribution, as it is the first to address KV cache eviction within the MPC framework. The method is also "training-free", meaning it can be applied directly to existing LLMs.  Initially, the reviewers raised several concerns. These included an insufficient experimental setup, such as a lack of newer models and tests under different network conditions. They also asked for more details on memory usage, clearer figures, and a better explanation of the performance gains. The authors' response addressed most of these points, leading several reviewers to raise their scores. There are still concerns about the practiacality of the approach, but overall the reviewers find the paper a step forward toward making MPC LLMs efficient. The authors should also include the new experiments and discussions in their revision.
Decision: Accept (poster)