DropKV: Decoupling Residual-Output Perturbation for Near-Optimal KV-Cache Eviction

Aozhong Zhang; Selcuk Gurses; Yanxia Deng; Naigang Wang; Chi-Chun Liu; Davis Wertheimer; Derrick Liu; Xin Li

cs.AIOct 15, 2026

DropKV: Decoupling Residual-Output Perturbation for Near-Optimal KV-Cache Eviction

Authors: Aozhong Zhang, Selcuk Gurses, Yanxia Deng, Naigang Wang, Chi-Chun Liu, Davis Wertheimer, Derrick Liu, Xin Li,

Organizations: University at Albany, SUNY · Northwestern University · IBM T. J. Watson Research Center

Abstract

Key-value (KV) cache management has become a critical bottleneck for scaling Large Language Models (LLMs) to long-context scenarios due to linear memory growth. While recent eviction methods have moved beyond simple attention-score heuristics to incorporate value representations, they typically face a fundamental trade-off: the underlying optimization for minimizing output perturbation is an NP-hard combinatorial problem, leading to mathematically suboptimal heuristics or implementations that are difficult to kernelize. In this work, we propose DropKV, a simple principled eviction framework based on Decoupled Residual-Output Perturbation. By decoupling the joint eviction decision into independent per-token scoring, DropKV circumvents combinatorial intractability and admits a provable constant-factor approximation guarantee under a cone condition that we empirically verify on three long-context LLMs. To ensure practical viability, we provide a high-performance implementation using fused Triton kernels that avoid materializing the full attention matrix, delivering a 19.8x scoring-kernel speedup that translates to up to a 9.9% matched-batch end-to-end prefill speedup. Extensive evaluations on the RULER and LongBench benchmarks demonstrate that DropKV consistently outperforms state-of-the-art baselines at equivalent cache budgets, achieving the lowest inference latency among eviction methods while also remaining faster than the dynamic cache baseline.

Figures & tables

Panel of Figure 1 — Figure 1: Cone condition: definition and empirical verification at $n{=}128\mathrm{K}$ on three long-context models. (a) Residuals $\bm{r}_{i}:=\bm{a}-\bm{v}_{i}$ inside a cone of half-angle $\arccos(c)$ about a single direction $\bm{u}$ , so no positive combination cancels to zero. (b) Layerwise prevalence of $c^{\star}>0$ across (head, query-position) triples, with binomial standard-error bands. (c) Distribution of $c^{\star}$ per model; mass to the right of the dotted line at $c^{\star}{=}0$ is the cone-holds region.

LLaMA-3.1-8B-Instruct
Method	Budget	N-S1	N-S2	N-S3	N-MK1	N-MK2	N-MQ	N-MV	VT	FWE	QA-1	QA-2	Avg.
Full KV	100%	100	99.2	99.6	97.6	88.2	98.7	95.85	84	61.93	64.17	44	84.84
SnapKV	5%	100	99	71.4	97.6	76.2	98.6	95.75	76.92	52.53	64.03	43.2	79.57
PyramidKV		100	99.4	62.4	97.4	74.2	98.6	94.7	78.36	54.86	63.9	45.6	79.04
StreamingLLM		4.4	4.2	4.8	5.6	5	5.05	5	4.9	73.4	37.48	37.4	17.02
KeyDiff		100	98.4	16.6	81.6	0	78.3	75.55	80.2	26.6	42.58	36.8	57.88

Table 1: RULER results at 128K sequence length and 5% KV-cache budget. On the Avg. column, the best result is bolded and the second-best is underlined; the DropKV row is shaded gray for emphasis.

Figure 2: Average accuracy on RULER. Top: 5% budget at varying sequence lengths. Bottom: varying cache budgets at $128\mathrm{K}$ sequence length. Our method consistently outperforms baselines and shows more graceful degradation at longer contexts.

	Single Doc. QA			Multi Doc. QA			Summarization			Synthetic		Fewshot Learning			Code
Method	NrtvQA	Qasper	MF-en	HotpotQA	2WikiMQA	Musique	GovReport	QMSum	MultiNews	PCount	PR-en	TREC	TriviaQA	SAMSum	Lcc	RB-P	Avg.
LLaMA-3.1-8B-Instruct
FullKV	30.51	45.59	56.34	58.22	50.02	31.75	34.3	25.33	26.76	9.5	100	73.5	92.29	43.96	64.77	55.7	49.91
SnapKV	30.34	31.51	54.45	56.95	47.34	29.8	22.64	24.62	16.03	9.5	100	39	92.03	42.18	58.82	54.97	44.39
PyramidKV	31.08	31.42	54.37	56.92	47.34	30.62	22.4	24.27	16.33	9.5	100	39.5	91.92	42.46	59.44	54.27	44.49
StreamingLLM	25.91	21.94	33.16	49.06	41.35	23.91	21.67	21.5	16.86	9.5	97	26.5	84.55	41.9	58.02	49.83	38.92

Table 2: LongBench results at 5% KV-cache budget.

LLaMA-3.1-8B-Instruct
Method	RULER			LongBench
Method	5%	10%	30%	5%	10%	30%
Full KV	91.35	91.35	91.35	49.91	49.91	49.91
CAKE	86.43	89.67	90.93	44.55	46.74	48.82
AdaKV	88.19	90.03	91.03	44.76	46.95	49.05
AnDPro	87.57	90.01	91.17	44.53	46.95	49.06

Table 3: Average scores on RULER (64K sequence length) and LongBench across different KV-cache budgets (

5\%,10\%,

and

30\%

). The best result is highlighted in bold.

Figure 3: DropKV scoring at

B{=}1

w{=}8

, and

5\%

budget. Left: Triton vs. PyTorch on scoring latency and peak scratch memory. At

n{=}128\mathrm{K}

Triton is

{\sim}20{\times}

faster with scratch flat at

{\sim}17

MB vs.

{\sim}9

GB. Right: Matched-batch prefill relative speedup percentage is positive in 8 of 9 cells; Qwen at

n{=}32\mathrm{K}

is essentially neutral (

-0.1\%

Method	End-to-End Latency (s) $\downarrow$					Time to First Token (s) $\downarrow$
Method	1	2	4	8	12	1	2	4	8	12
Dynamic	19.08	30.91	54.72	OOM	OOM	3.69	7.36	14.83	OOM	OOM
SnapKV	16.44	20.22	27.71	43.08	59.10	3.95	7.47	14.92	30.36	46.38
CriticalKV	16.72	21.10	29.55	46.36	64.75	4.24	8.27	16.68	33.62	51.96
AnDPro	17.79	23.06	33.22	53.91	76.25	5.31	10.30	20.45	41.00	63.43
DropKV	16.21	20.13	27.50	42.71	59.01	3.68	7.40	14.75	29.94	46.29

Table 4: End-to-End and Time to First Token latencies (in seconds) across batch sizes

B\in\{1,2,4,8,12\}

. All evaluations were conducted using the Mistral-7B-512K model with 32K sequence length.

\downarrow

indicates lower values are better. “OOM” denotes Out-of-Memory.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

LLaMA-3.1-8B-Instruct
Method	Budget	N-S1	N-S2	N-S3	N-MK1	N-MK2	N-MQ	N-MV	VT	FWE	QA-1	QA-2	Avg.
FullKV	100%	100	99.2	99.6	97.6	88.2	98.7	95.85	84	61.93	64.17	44	84.84
SnapKV	10%	100	99	90.8	97.4	78.2	98.45	96.4	78.92	56.47	63.23	43.8	82.06
PyramidKV		100	100	55.47	97.66	71.88	98.83	93.75	76.09	53.91	60.81	42.97	77.40
StreamingLLM		11.72	8.59	14.84	11.72	12.50	10.55	8.79	10.94	75.78	34.83	32.82	21.19
KeyDiff		100	100	57.03	94.53	1.56	95.51	94.92	78.44	45.31	43.68	35.16	67.83

Appendix

Table 5: RULER results at 128K sequence length, 10% and 30% KV-cache budgets. The best result is highlighted in gray, and the second-best is underlined.

LLaMA-3.1-8B-Instruct
Method	Budget	N-S1	N-S2	N-S3	N-MK1	N-MK2	N-MQ	N-MV	VT	FWE	QA-1	QA-2	Avg.
FullKV	100%	100	100	100	100	100	100	99.02	98.91	85.68	71.22	50	91.35
SnapKV	5%	100	99.40	84.6	99	94.4	99.5	98.7	96.24	74.87	69.9	49.2	87.80
PyramidKV		100	100.00	57.8	99.6	94.8	99.5	99.1	97.24	73.13	69.9	49.8	85.53
StreamingLLM		5.80	7.40	4.80	7.60	5.40	4.25	5.05	9.12	94.87	35.80	40.77	20.08
KeyDiff		100	99.40	42.40	89.80	1.40	87.35	90.55	95.20	54.53	38	45.85	67.68

Appendix

Table 6: RULER results at 64K sequence length and 5%, 10% and 30% KV-cache budget. The best result is highlighted in gray, and the second-best is underlined.

LLaMA-3.1-8B-Instruct
Method	Budget	N-S1	N-S2	N-S3	N-MK1	N-MK2	N-MQ	N-MV	VT	FWE	QA-1	QA-2	Avg.
Full KV	100%	100	100	100	100	100	99.61	98.24	99.84	95.57	71.03	53.91	92.56
SnapKV	5%	100	99.80	48.6	99.4	97.4	99.75	98.35	98.84	81.27	68.15	55.4	86.09
PyramidKV		100	99.80	29	100	97.4	99.75	98.2	99.24	82.6	68.85	55.6	84.59
StreamingLLM		5	6	4.40	5.40	6.20	5.15	5.15	8.96	92.80	43.20	42.68	20.45
KeyDiff		100	100	61.60	95	2.80	91.25	91.95	98.96	65.33	42	45.50	72.22

Appendix

Table 7: RULER results at 32K sequence length and 5%, 10% and 30% KV-cache budget. The best result is highlighted in gray, and the second-best is underlined.

LLaMA-3.1-8B-Instruct
Method	Budget	N-S1	N-S2	N-S3	N-MK1	N-MK2	N-MQ	N-MV	VT	FWE	QA-1	QA-2	Avg.
Full KV	100%	100	100	100	100	100	100	98.05	99.84	96.35	76.3	59.38	93.63
SnapKV	5%	100	100.00	19.92	100	98.44	99.9	97.56	99.06	91.28	71.62	58.59	85.12
PyramidKV		100	100.00	7.81	100	96.88	99.61	98.63	99.14	91.67	67.45	58.2	83.58
StreamingLLM		3.80	6.20	5	4.80	5.40	4	5.95	8.04	91.73	43.40	44.12	20.22
KeyDiff		100	100	49.60	93.60	3	89.15	89.20	98.88	83.67	44.80	45.25	72.47

Appendix

Table 8: RULER results at 16K sequence length and 5%, 10% and 30% KV-cache budget. The best result is highlighted in gray, and the second-best is underlined.

	Single Doc. QA			Multi Doc. QA			Summarization			Synthetic		Fewshot Learning			Code
Method	NrtvQA	Qasper	MF-en	HotpotQA	2WikiMQA	Musique	GovReport	QMSum	MultiNews	PCount	PR-en	TREC	TriviaQA	SAMSum	Lcc	RB-P	Avg.
LLaMA-3.1-8B-Instruct
FullKV	30.51	45.59	56.34	58.22	50.02	31.75	34.3	25.33	26.76	9.5	100	73.5	92.29	43.96	64.77	55.7	49.91
SnapKV	30.11	37.66	55.52	57.27	48.37	31.51	25.77	24.24	19.55	9.5	100	49.5	91.54	41.68	62.02	54.64	46.18
PyramidKV	30.33	38.03	55.11	57.17	48.65	31.26	25.28	24.73	19.79	9.25	100	43	91.68	42.04	61.98	54.61	45.81
StreamingLLM	27.82	24.8	33.13	50.57	42.3	24.17	24.06	21.69	19.06	9.5	92.5	42.5	87	41.32	61.45	51.98	40.87

Appendix

Table 9: LongBench results at 10% cache budget.

	Single Doc. QA			Multi Doc. QA			Summarization			Synthetic		Fewshot Learning			Code
Method	NrtvQA	Qasper	MF-en	HotpotQA	2WikiMQA	Musique	GovReport	QMSum	MultiNews	PCount	PR-en	TREC	TriviaQA	SAMSum	Lcc	RB-P	Avg.
LLaMA-3.1-8B-Instruct
FullKV	30.51	45.59	56.34	58.22	50.02	31.75	34.3	25.33	26.76	9.5	100	73.5	92.29	43.96	64.77	55.7	49.91
SnapKV	30.28	45.93	56.13	58.05	50.38	32.07	30.58	24.96	23.74	9.5	100	65.5	91.87	42.71	64.83	55.95	48.91
PyramidKV	30.58	44.36	55.8	57.98	49.83	31.7	30.06	24.99	23.53	9.5	100	62.5	91.88	43.42	64.37	55.68	48.51
StreamingLLM	28.33	31.55	37.18	54.34	48.13	26.98	28.64	22.44	23.25	9.5	83.5	59.5	91.54	43.42	63.18	54.13	44.10

Appendix

Table 10: Additional LongBench results at 30% budget. The best average result is highlighted in gray, and the second-best is underlined.

S. L.	Method	Budget	N-S1	N-S2	N-S3	N-MK1	N-MK2	N-MQ	N-MV	VT	FWE	QA-1	QA-2	Avg.
LLaMA-3.1-8B-Instruct
128k	Full KV	100%	100	99.2	99.6	97.6	88.2	98.7	95.85	84	61.93	64.17	44	84.84
	CriticalKV	5%	100	99	69.2	97.6	75.6	98.55	95.2	77.4	46.67	63.9	42.8	78.72
	AnDPro		100	99	68.4	97.4	78.4	98.75	96	76.52	54.53	63.76	43.4	79.65
	DropKV		100	98.8	89.6	97.6	86.2	98.25	96.9	77.32	49.73	64.17	43.4	82.00
	AdaDropKV		100	100	93.75	97.66	86.8	99.02	95.7	77.66	54.34	64.32	43.4	82.97

Appendix

Table 11: RULER results at 128K and 64K sequence length (S. L.) and 5%, 10% and 30% KV-cache budget. The best result is highlighted in gray, and the second-best is underlined.

		Single Doc. QA			Multi Doc. QA			Summarization			Synthetic		Fewshot Learning			Code
Method	Budget	NrtvQA	Qasper	MF-en	HotpotQA	2WikiMQA	Musique	GovReport	QMSum	MultiNews	PCount	PR-en	TREC	TriviaQA	SAMSum	Lcc	RB-P	Avg.
LLaMA-3.1-8B-Instruct
FullKV	100%	30.51	45.59	56.34	58.22	50.02	31.75	34.3	25.33	26.76	9.5	100	73.5	92.29	43.96	64.77	55.7	49.91
CAKE	5%	30.41	33.54	54.79	57.09	48.29	31.07	23.54	24.36	17.33	9.5	100	37	91.05	42.54	58.58	53.7	44.55
AdaKV		29.88	32.53	54.38	57.25	46.79	30.55	23.33	24.21	17.08	9.5	100	42	91.8	40.99	60.62	55.28	44.76
CriticalKV		30.03	31.07	54.55	57.33	47.15	30.09	23.16	23.92	18.46	9.5	100	41	92.03	42.14	59.25	54.54	44.64

Appendix

Table 12: LongBench results at 5%, 10% and 30% cache budget. The best result is highlighted in gray, and the second-best is underlined.

		Dynamic		DropKV-PyTorch		DropKV-Triton
Model	$n$	$B$	tok/s	$B$	tok/s	$B$	tok/s	$\times_{\mathrm{dyn}}$
Llama-3.1-8B	4k	38	395	56	2111	56	2066	$5.23$
	32k	4	50	7	260	6	223	$4.46$
	128k	1	12	1	38	1	38	$3.02$
Mistral-7B-512k	4k	56	411	88	2805	99	2938	$7.15$
	32k	7	55	11	413	12	452	$8.22$

Appendix

Table 13: Serving throughput at each method’s maximum batch at

5\%

budget on A100-80GB GPU.

B

is the largest batch that fits for the given

(n,\text{method})

; aggregate decode throughput is in tokens/s.

\times_{\mathrm{dyn}}

is Triton’s decode throughput divided by dynamic’s.

Method	Type	Per-token score	Direction	Reference
StreamingLLM [ 49 ]	H	$\mathds{1}[j\leq s]+\mathds{1}[j>n-w]$	keep large (mask)	§3.2
KeyDiff [ 37 ]	H	$-\,\mathrm{CosSim}\!\bigl(\bm{k}_{j},\,\mu(\bm{K})\bigr)$	keep large	Eq. 8
SnapKV [ 32 ]	H	$\mathrm{MaxPool1d}_{\kappa}\!\bigl(\sum_{t\in\mathcal{Q}}p_{j}^{(t)}\bigr)$	keep large	Eq. 2–3
PyramidKV [ 5 ]	H	SnapKV per-token; layer-asym. budget $k^{l}$	keep large	Eq. 1, 3
CAKE [ 38 ]	H	$\mathrm{Mean}(\bm{A}[-w{:},j])+\gamma\,\mathrm{Var}(\bm{A}[-w{:},j])$	keep large	Eq. 11
CriticalKV [ 13 ]	B	$(\bar{p}_{j}+\epsilon)\,\\|(\bm{V}\bm{W}_{O})_{j,:}\\|_{1}$	keep large	Alg. 1; Thm. 3.5

Appendix

Table 14: Per-token scoring expressions of the baselines in Table 1 . “Type” classifies the surrogate strategy: H: heuristic retention (no value-space modelling), B: explicit upper bound on

\|\Delta(\mathcal{J})\|_{1}

, R: convex (LASSO-style [ 44 ] ) relaxation of the combinatorial perturbation objective, E: exact singleton perturbation followed by per-token decoupling. “Direction” indicates whether the score is read as “keep large” (retention score) or “evict small” (eviction cost). Notation:

\bar{p}_{j}=\tfrac{1}{|\mathcal{Q}|}\sum_{t\in\mathcal{Q}}p_{j}^{(t)}

;

\mu(\bm{K})=\tfrac{1}{n}\sum_{i}\bm{k}_{i}

;

s

w

are the StreamingLLM sink and recent-window sizes;

\kappa

is the SnapKV pooling kernel size;

\gamma

is CAKE’s variance weight; and

k^{l}

is PyramidKV’s per-layer budget.

Model	triples	median $\varepsilon$	p95 $\varepsilon$	max $\varepsilon$	$\varepsilon\leq 0.005$
Llama-3.1-8B-Instruct	$32\mathrm{K}$	$3.1{\times}10^{-6}$	$1.1{\times}10^{-4}$	$0.146$	$97.89\%$
MegaBeam-Mistral-7B-512K	$32\mathrm{K}$	$2.6{\times}10^{-6}$	$9.7{\times}10^{-5}$	$0.222$	$97.19\%$
Qwen2.5-7B-Instruct-1M	$25{,}088$	$4.3{\times}10^{-6}$	$1.2{\times}10^{-4}$	$0.176$	$97.52\%$

Appendix

Table 15: Verification of Assumption 1 at

n=128\mathrm{K}

: distribution of

\varepsilon=\max_{j\in\mathcal{L}}p_{j}

across sampled triples.

Model	min	p05	p50	mean	p95	max
Llama-3.1-8B-Instruct	$-0.325$	$-0.148$	$\mathbf{+0.107}$	$+0.120$	$+0.389$	$+0.882$
MegaBeam-Mistral-7B-512K	$-0.334$	$-0.131$	$\mathbf{+0.094}$	$+0.110$	$+0.368$	$+0.849$
Qwen2.5-7B-Instruct-1M	$-0.567$	$-0.196$	$\mathbf{+0.074}$	$+0.088$	$+0.423$	$+0.845$

Appendix

Table 16: Cone constant

c^{\star}

distribution across sampled triples at

n=128\mathrm{K}

Model	$\tau=0.00$	$0.05$	$0.10$	$0.20$	$0.30$	$0.50$
Llama-3.1-8B-Instruct	$91.21\%$	$74.16\%$	$53.01\%$	$21.43\%$	$8.93\%$	$1.29\%$
MegaBeam-Mistral-7B-512K	$91.12\%$	$72.37\%$	$46.85\%$	$17.64\%$	$8.49\%$	$0.99\%$
Qwen2.5-7B-Instruct-1M	$76.45\%$	$57.29\%$	$42.99\%$	$22.50\%$	$12.33\%$	$2.14\%$

Appendix

Table 17: Fraction of sampled triples satisfying

c^{\star}>\tau

Model	finite	p50	p95	max
Llama-3.1-8B-Instruct	$89.13\%$	$10.42$	$122$	$8.2{\times}10^{4}$
MegaBeam-Mistral-7B-512K	$87.53\%$	$11.83$	$115$	$1.5{\times}10^{6}$
Qwen2.5-7B-Instruct-1M	$73.43\%$	$11.32$	$198$	$2.2{\times}10^{5}$

Appendix

Table 18: Empirical distribution of the conservative multiplicative factor in Theorem 1 , computed as

1/[c^{\star}(1-\varepsilon)(1-k\varepsilon)]

from the measured assumption constants. “finite” is the fraction of sampled triples with

c^{\star}>0

and

1-k\varepsilon>0

; p50/p95/max are computed over this finite subset.

$k=10$ (50% budget)
	Llama-3.1-8B		Mistral-7B-512K		Qwen2.5-7B-1M
Stratification	p50	p95	p50	p95	p50	p95
random	$1.000$	$1.095$	$1.000$	$1.107$	$1.000$	$1.107$
low-attention tail	$1.036$	$1.164$	$1.029$	$1.130$	$1.035$	$1.136$
near-threshold	$1.140$	$1.278$	$1.151$	$1.344$	$1.160$	$1.430$
rank-disagreement	$1.034$	$1.169$	$1.029$	$1.185$	$1.034$	$1.262$

Appendix

Table 19: Empirical approximation gap: DropKV proxy ratio

F(\hat{\mathcal{J}})/F(\mathcal{J}^{*})

n_{\mathrm{small}}{=}20

, broken down by stratification and

k

. Median (p50) and 95th percentile (p95) computed over

150

triples per (model, stratification,

k

) cell. Compare against the worst-case bound (median

10

–

12

) in Table 18 .

Panel of Figure 4 — Figure 4: Left: Strict Cone Condition (Assumption 2 ). Right: Approximate Cone Condition (Assumption 3 ): $\mathcal{L}_{\bm{u},c}=\{1,2,3,5\}$ and $p_{4}\|\bm{r}_{4}\|_{2}\leq\mu$ .

Metric	PyTorch scorer	Triton scorer
Runtime (ms)	3.63	0.23
Speedup	1.0 $\times$	15.7 $\times$
Kernels launched	34	8
HBM read (MB)	2,175	138
HBM write (MB)	1,545	5
Mem% of peak HBM	50.3	30.4

Appendix

Table 20: Nsight Compute full-call profiling at

n{=}16\mathrm{K}

. Both columns aggregate all launches inside the scoring call: time/bytes/ instructions are summed, percentage metrics are time-weighted, and register or shared-memory footprints are maxima over launches.

Kernel	Time ( $\mu$ s)	SM%	Mem%	Active warps	Ceiling	Main limiter
A: forward/LSE	69.82	22.7	49.0	11.6%	18.75%	Registers
B: score accumulation	63.52	39.6	54.0	22.6%	25.00%	SMEM
C: split-K merge	78.66	0.5	2.3	6.3%	43.75%	Reduction overhead

Appendix

Table 21: Per-kernel ncu measurements for the Triton scoring pipeline at

n{=}16\mathrm{K}

. SM% and Mem% are fractions of peak sustained SM issue and peak HBM bandwidth. Active warps is measured achieved occupancy; Ceiling is the resource-limited occupancy ceiling.

KV-Cache Eviction

Key-value (KV) cache eviction reduces language-model memory use by removing or compressing cached tokens while preserving useful context.

See all 99 papers

Reformulating KV Cache Eviction Problem for Long-Context LLM Inference
May 8, 2026Tho Mai, Joo-Young KimKV Caching Long-Context Language Model Inference
KAIST Daejeon, South Korea
ReST-KV: Robust KV Cache Eviction with Layer-wise Output Reconstruction and Spatial-Temporal Smoothing
May 9, 2026Yongqi An, Chang Lu, Kuan Zhu +5KV Caching Long-Context Language Model Inference
Foundation Model Research Center, Institute of Automation, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing, China · University of Electronic Science and Technology of China, Chengdu, China +2
DistillCache: KL-Guided Adaptive KV-Cache Eviction for Memory-Efficient LLM Inference
Aug 9, 2026Asaad AlthoubiKV Caching Long-Context Language Model Inference
Oklahoma State University Stillwater, OK USA

May 8, 2026J/K move · Enter open · S save

Reformulating KV Cache Eviction Problem for Long-Context LLM Inference

Tho Mai, Joo-Young Kim

KAIST Daejeon, South Korea

KV Caching Long-Context Language Model Inference KV-Cache Eviction KV-Cache Compression

Open paper AskPDF arXiv

Large language models (LLMs) support long-context inference but suffer from substantial memory and runtime overhead due to Key-Value (KV) Cache growth. Existing KV Cache eviction methods primarily rely on local attention weights, neglecting the influence of value representations, output projection, and inter-head interactions. In this work, we reformulate KV Cache eviction from a conventional head-wise, weight-averaging approach into an output-aware, layer-wise matrix multiplication approximation problem. We introduce LaProx, a novel eviction strategy that explicitly models the multiplicative interaction between attention maps and projected value states to accurately quantify token contributions while accounting for inter-head dependencies. Building on this metric, we propose the first unified eviction strategy that assigns globally comparable importance scores to tokens, enabling model-wide selection instead of local, head-wise decisions. Experimental results across 19 datasets on long-context benchmarks LongBench and Needle-In-A-Haystack demonstrate that our approach maintains model performance with only 5% of the KV cache and consistently outperforms prior works across all configurations. Notably, our method achieves up to 2

\times

accuracy loss reduction under extreme compression scenarios compared to existing state-of-the-art baselines with minimal overhead.

Abstract

KV-Cache Eviction

Explore similar work

Reformulating KV Cache Eviction Problem for Long-Context LLM Inference

ReST-KV: Robust KV Cache Eviction with Layer-wise Output Reconstruction and Spatial-Temporal Smoothing

DistillCache: KL-Guided Adaptive KV-Cache Eviction for Memory-Efficient LLM Inference