ReST-KV: Robust KV Cache Eviction with Layer-wise Output Reconstruction and Spatial-Temporal Smoothing
Authors: Yongqi An
Chang Lu
Kuan Zhu
Tao Yu
Chaoyang Zhao
Hong Wu
Ming Tang
Jinqiao Wang
Venue: ICLR 2026 Poster (2026)
Keywords: Long context
Efficient decoding
KV cache compression
Primary area: generative models
TL;DR: We propose ReST-KV, a novel KV cache eviction method that explicitly models attention redistribution and spatial-temporal dynamics, significantly improving LLM efficiency for long-sequence generation.

Abstract: Large language models (LLMs) face growing challenges in efficient generative inference due to the increasing memory demands of Key-Value (KV) caches, especially for long sequences.
Existing eviction methods typically retain KV pairs with high attention weights but overlook the impact of attention redistribution caused by token removal, as well as the spatial-temporal dynamics in KV selection.
In this paper, we propose ReST-KV, a robust KV eviction method that combines layer-wise output **Re**construction and **S**patial-**T**emporal smoothing to provide a more comprehensive perspective for the KV cache eviction task. 
Specifically, ReST-KV formulates KV cache eviction as an optimization problem that minimizes output discrepancies through efficient layer-wise reconstruction. By directly modeling how each token’s removal affects the model output, our method naturally captures attention redistribution effects, going beyond simplistic reliance on raw attention weights.
To further enhance robustness, we design exponential moving average smoothing to handle temporal variations and an adaptive window-based mechanism to capture spatial patterns.
Our method, ReST-KV, significantly advances performance on long-context benchmarks. It surpasses state-of-the-art baselines by 2.58\% on LongBench and 15.2\% on RULER. Additionally, ReST-KV consistently outperforms existing methods on Needle-in-a-Haystack and InfiniteBench, all while achieving a remarkable 10.61$\times$ reduction in decoding latency at 128k context length. The code is included in the supplementary material and is designed for easy reproduction.

Published as a conference paper at ICLR 2026
REST-KV: ROBUST KV CACHE EVICTION WITH LAYER-WISE OUTPUT RECONSTRUCTION AND SMOOTHING
Yonggi An Chang Lu", Kuan Zhu Tao Yu Chaoyang Zhao?.2, Hong Wu*, Ming Tang Jinqiao Wang1.2.1.5x
Foundation Model Research Center, Institute of Automation, Chinese Academy of Sciences, Beijing, China Schooo of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing, China UUniversity of Electronic Science and Technology of China, Chengdu, China "Wuhan AI Research, Wuhan, China 'Objecteye Inc., Beijing, China anênlpr aa.ac. cn, jqwangênlpr ia. ac. cn
ABSTRACT
Large language models (LLMs) face growing challenges in efficient generative in- ference due to the increasing memory demands of Key- Value (KV) caches, espe- cially for long sequences. Existing eviction methods typically retain KV pairs with high attention weights but overlook the impact of attention redistribution caused by token removal, as well as the paper, we propose ReST-KV, robust KV eviction method that combines layer- wise output Reconstruction and Spatial-Temporal smoothing provide more comprehensive perspective for the KV cache eviction task. Specifically, ReST-KV formulates KV cache eviction as an optimization problem that minimizes output discrepancies through efficient layer-wise reconstruction. By directly modeling how each tokens removal affects the model output, our method naturally captures attention redistribution effects, going beyond simplistic reliance raw attention weights. To further enhance robustness, we design exponential moving average smoothing to handle temporal variations and adaptive handow-based mecha- nism to capture spatial patterns. Our method, ReST-KV, significantly advances performance on long-context benchmarks. It surpasses state-of-the-ard baselines by 2.58% on LongBench and 15.2% on RULER. Additionally, ReST-KV consis- tently outperforms existing methods on Needle-in-a-HHaystack and InfiniteBench, all while achieving a remarkable 10.61 x reduction in decoding latency at 128k context length. The code is included in the supplementary material and de- signed for easy reproduction.
dynamics KV selection. In this
INTRODUCTION
Large language models (Acha) et all 2023% Anthropic 2023: Dubey all 2024: Mrs IraAA,, 2023) have significantly advanced natural language processing (NLP). These models have et all (0ZzR), multi-turn dialogues (Du et all (021), retrieval augmentation (Yan et all 2022), and code genera- tion (Roziere et all 2023). Recent models like GPT-4 (Achiam et all 2023), Claude 3.5 (Anthropic. 2023), and L (Dubey all 20244) have extended their context lengths beyond 128K tokens, allowing for long-context applications. However, as context length increases, the memory required to store KV cache grows rapidly, potentially reaching hundreds of gigabytes when handling longer sequences. Thus, optimizing KV cache during inference, without retraining, is crucial for improving both efficiency and scalability.
enabled breakthroughs in various tasks, such as document summarization
KV cache eviction, which identifies and removes less important KV pairs, is a promising approach to reduce memory consumption and enhance computational efficiency (Li eLetal all 20244). Current
methods typically rely on fixed attention patterns (Han all 2024; Ge et 212 or use statistical
"Corresponding Author

---

Published as a conference paper at ICLR 2026
weights
decention changes due to redistrabution
value sectors of renained neneved tokens
Previous wethod: 120, Snapsy, Pyrantdll
minimize
heST-KV (Our method]
minimize
Weightt
Figure I: Comparison between ReST-KV and existing methods. Unlike prior approaches that over- look attention redistribution, ReST-KV considers its impact to improve KV retention.
information from attention weights (Zhang et al. R002% Li all 2024h Careral 2024) to estimate the importance of KV pairs. However, as shown in Figure II, these approaches focus solely on retaining query-key pairs with high similarity scores, while ignoring the attention redistribution effects caused by removing certain pairs. This redistribution can alter the overall attention landscape, leading to suboptimal retention decisions and degraded performance, especially under tight cache constraints.
In this paper, we propose ReST-KV, a robust KV cache eviction method that accounts for the effects of attention redistribution and the spatial-temporal dynamics in KV selection. We revisit the KV cache eviction problem and reformulate it as preserving the attention output at each layer under fixed memory constraints. Specifically, we measure the reconstruction loss caused by removing each individual KV pair, and use it as an eviction indicator: the larger the loss, the more important the KV pair. This loss implicitly captures the impact of attention redistribution caused by the removal. Moreover, our empirical observations show that KV importance varies significantly across both time and space. To further improve robustness, we introduce two smoothing mechanisms: (1) an exponential moving average model temporal dynamics by emphasizing more recent KV pairs, and (2) an adaptive window-based spatial smoothing method, which adjusts for varying window sizes and offsets by estimating the spatial dynamics.
By evaluating on wide range of downstream tasks including LongBench, RULER, Needle-in-a- Haystack, and InfiniteBench, we demonstrate that ReST-KV consistently outperforms state-of-the- art baselines, especially under low cache budgets and demonstrates more robustness in multi-turn dialogue scenarios. We extensively evaluate ReST-KV challenging long-context benchmarks such as LongBench, RULER, Needle-in-a-Haystacc and InfiniteBench. Our results show it con- sistently surpasses state-of-the-art baselines, with particularly strong gains of 2.58% on LongBench and 15.2% on RULER. ReST-KV also exhibits greater robustness in multi-turn dialogue and effi- ciency under constrained cache budgets. For decoding, it achieves a 10.61 latency reduction 128k context length when integrated with FlashAttention-2. Importantly, ReST-KV is fully compat- ible with existing prefill sparse attention methods, leading 2.37x TTFT speedup. summary, we make the following contributions:
A novel formulation of KV eviction treating it as layer-wise output reconstruction, enabling new importance indicator that captures attention redistribution effects.
spatial-temporal smoothing mechanism combining exponential moving average and adap- tive windowing, significantly enhancing robustness in KV selection.
Extensive experiments show that ReST-KV outperforms state-of-the-ar baselines under low
cache budgets and reduces decoding latency by up 10x at 128k context length.
RELATED WORK
2.1
KV CACHE EVICTION
KV cache eviction, a prominent method for optimizing KV cache during inference without retrain- ing, alleviates memory and latency issues in long-context LLMs eL 2024z). Early eviction methods focused on specific attention patterns, such as StreamingLLM (Xtao.etal 20233) and LM- Infinite (Han et all 2024),, retain only the initial and local tokens. While more flexible approaches like FastGen (Ge et all (02%) and RazorAttention (Tang et al,, 2024) were developed, they still rely predefined patterns and risk ignoring important tokens. Subsequent studies introduced eviction
2

---

Published as a conference paper at ICLR 2026
(a) Layer-wise Output Reconstruction Indicator
(b) Spatial-Tempora Smoothing
MILA (Ky. Val
Multi-head
Altention
XIEA (s., (K Vired
Multi-head Attention
Kzis
of
Vyin
ofl-oo of
x
Peepera Spoething
EMA
[
MHA (x,, Ky, V.)) MHA (x,, Ki V1
AWS
Figure 2: Overview of ReST-KV. (a) Layer-wiss wise output reconstruction quantifies each KV pairs impact on output error as eviction indicator. (b) Two smoothing mechanisms enhance robustness: exponential moving average for temporal smoothing and adaptive window-base approach for spatial smoothing.
indicators to assess the importance of KV cache entries, often using attention weights. For instance, H2O (Zaag et all (оZE) uses cumulative attention weights, and SnapKV (Creta (0244) pools the average attention weight over the last window. In addition to indicator improvements, some research has explored non-uniform layer-wise and head-wise budget allocation strategies. Pyra- midKV (Cai et all, 2024) and PyramidInfer (Yang et all, (2024) allocate budget a pyramid fashion, while DynamicKV (Zhou el al 2022)), D2O (Wan el (0ZE)) and CAKE (Qin et al 2025) adap- tively allocate budget based on layer-specific information. AdaKV (Feng et al, 2024) adjusts the budget per head based on output & loss bounds. Our work focuses on the limitations of existing eviction indicators, which primarily rely on attention weights derived from query-key interactions and overlook the combined impact value vectors and spatial- tempoall dynamics. Furthermore, our approach is fully compatible with existing layer-wise and head-wise budget allocation strategies.
2.2 ATTENTION DYNAMICS
While attention is central to the success of Transformers, it also poses scalability challenges in long- context settings due to its quadratic complexity. Recent work has therefore investigated attention dynamicsppecifically, the spatiotemporal patterns and redistribution of attention weightsas means to enable more efficient inference.
Several studies reveal structured attention behaviors. MInference (Ding et all (12E)) discovers "vertical-slash" pattern, where attention gradually shifts across tokens over time, indicating evoly- ing token importance. FlexPrefill all, 2025) similarly identifies consistent attention trajec- tories during prefill. Keyformer (Adnan et all (024)) examines how KV eviction distorts attention distributions and proposes normalization to mitigate such shifts.
Distinct from the above methods, we reformulate KV cache eviction by explicitly modeling attention redistribution and spatiotemporal dynamics. Rather than relying solely on static attention weights, our approach captures temporal evolution and layer-wise shifts in attention, enabling more robust importance estimation and significantly improving performance under memory constraints.
3 METHODOLOGY
3.1 PRELIMINARY
LLMs typically decode text in an auto-regressive manner, which allows them to generate high- quality, contextually coherent text. However, this decoding process is computationally expensive, as it involves high degree of repetitive calculations, making it challenging to apply in real-time or large-scale scenarios.
KV cache, a widely recognized technique, reduces redundant computation by storing previously computed keys and values. In this section, we describe the attention computation under the KV cache framework, laying the foundation for our discussion on KV cache eviction. For clarity, we focus on single attention head and layer, omitting footnotes. At each decoding step t, the KV cache stores previously computed keys and values (K1a-1, Via-1) for X[1 t 1], enabling reuse future steps. For convenience, denote K KT-1 and V Via-1 VT-1- Consequently, the model

---

Published as a conference paper at ICLR 2026
requires only the current token x, to generate x rather than the full sequence X x Xe]- Formally, at step i, the query qr, key k,, and value V, are computed as:
q = x We, k, = x, WK. Ki V, = x, Wv.
(1)
where Wq. Wx K, Wv are the components of the Q V weight matrices corresponding single attention head. The currently computed k; and v, will be concatenated with the previously cached keys and values, and used in the attention computation for decoding step
Kr Concat (Kr-1, Vr Concat (Vr-1,
where K and VT are the entire sequences of keys and values at decoding step t. The attention output 2, for the token x, at step calculated as:
9qK4
2, = softmax
VT = A,VT.
vd
where A, represents the attention weights for the token x₃ and is used by existing methods to com- pute eviction indicators. da represents the dimension of the key vectors in the attention mechanism. Finally, the output of a single head in the multi-head attention can be expressed as:
MHA (xt, (Kr, VT)) - 2, Wo,
(4)
where Wo is the weight matrix of output projection corresponding to a single attention head.
3.2 LAYER-WER WISE RECONSTRUCTION INDICATOR
We reformulate KV cache eviction as preserving the attention output distribution each layer under fixed memory constraints, naturally capturing the effects of attention redistribution. We formalize this paradigm as layer-wise reconstruction, a framework that aligns with the transformer's 's inherent layer-wise computation flow. Specifically, for single layer, the subproblem is expressed as:
Definition 3.1. Given cache budget B for single layer, the task is to select series of important KV cache entries (Kr, VT) containing up to B elements from the total cache entries (Kr, V at step 4, with the goal of maximizing the retention the orignial MHA output. We use &2 distance to calculate reconstruction error, the objective for single attention head can be defined
|MH (xt, (Kr, Vz)) - MHA (xe, (Kr, Vzi)
argmin (r.Vy)
(5)
s.t.
(Kr, V.) S S,
where (Kr, Vr) is the number selected KV pairs.
To efficiently compute Eq E we adopt greedy selection strategy that retains the top-B KV pairs estimated to have the greatest impact on the attention output. Specifically, for the nith KV pair, its importance is measured by the increase in reconstruction error when removed, which based on the local linearity assumptions (Molchanoy al. 2016). The eviction indicator is defined as:
[m] MHHA(x (x,, (KT, VT))
MHA(X, (KTAnn VT.An))l2
(6)
where (Kr VTAA) represents the set of cache with the 7-th KV pair removed.
By introducing Eq. B and Eq. g for derivation, Eq. B can be simplified as follows:
A.[n] A-
I [n]
|MHA (xe, (Kr, Vr)) v.. Woll2
where [n[n]
[n] represents the attention weights of the query with respect to the key kn, and vx represents the n-th value in the value cache VT.
Traditional eviction indicators only considered A, (n), neglecting the effects of attention redistribu- tion. Eq. M demonstrates that the importance of KV pair depends on two mechanisms:
4

---

Published as a conference paper at ICLR 2026
Temporal
Spatial
Spatial
Figure 3: Visualization analysis of the spatial-temporal dynamics of the output reconstruction in- dicator. The left plot shows dynamic temporal variations in KV pair importance over steps, with the zoomed-in in view highlighting a KV pairs gradual decline in importance. The right plot reveals spatial shifts, where similar importance patterns emerge shifted positions.
Nonlinear Attention Reweighting: The first term A-A.p] acts as monotonic nonlinear
A.In]
amplifier in (0, 1). While preserving the conventional principle that higher attention weights Ar[n] indicate stronger retention priority, this transformation introduces curvature to better discriminate between high-competition KV pairs compared linear scaling prior methods. Redistribution Sensitivity: The second term ||MHA(-) v. Woll captures the redistribu- tion of attention after removing the n-th KV pair. It reflects how much the remaining KV pairs fail to compensate for the excluded value in reconstructing the MHA output. A smaller discrepancy indicates that attention can be effectively redistributed to preserve the output, thus signaling lower importance of the removed KV pair.
The additional analysis and the derivation of Eq. can be found in Appendix A and Eq. 211
3.3 SPATTAL-TEMPORAL SMOOTHING
To enhance the robustness of KV pair selection during the prefill stage, we analyze the spatial- temporal dynamics of the KV pairs' reconstruction error (Eq. M). From Figure we observe two key characteristics: (1) The importance of KV pairs exhibits dynamic temporal variations (i.e., the fluctuating patterns I [n), L m))...... [|]]] along the temporal dimension, and (2) simultaneously demonstrates dynamic spatial shifts where similar importance distributions emerge across shifted positions (e.g., I,
I N]. L [r1] exhibit analogous patterns).
Leveraging these observations, introduce novel smoothing mechanisms to enhance the bustness of KV pair selection, as illustrated Figure [(b).. These mechanisms address temporal variations and spatial shifts in KV pair importance, ensuring process. By applying these techniques, we aim to reduce short-term fluctuations and capture long- trends, ultimately improving the performance of the KV cache eviction.
stable and reliable selection
Exponential Moving Average Temporal Smoothing. Inspired by SnapKV (Lretal 2024h),
use a recent query window S., to assess the importance of KV pairs. To model temporal dynamics, apply exponential moving average (EMA) smoothing the importance of KV pairs, which signs higher weights to recent queries while dampening earlier fluctuations. To apply this smoothing over limited window of recent queries, we define the temporal smoothing
(..((Iss..axl))) if Sw, otherwise,
[m[n]
(
Ω
where [n(n] represents the eviction indicator with temporal smoothing. EMA(-) captures the tem- poral variation importance. We assign an arbitrarily large value to the most recent S., tokens ensure their preservation.
The exponential moving average E.M(()) is defined as:
aIg [r]] + (1 EM (r))),
EMA ( (m])
t1 < t2:
(9)
Ir [n],
elif t la
5

---

Published as a conference paper at ICLR 2026
where EMA(II, [xl) represents the exponential moving average of the reconstruction errors It [n]..... [n] computed over the steps from & to tz. a is the smoothing factor that controls the weight of the current reconstruction enror L, [n] relative to the previous error EMA [x]) in the update process.
Adaptive Window-Based Spatial Smoothing. To capture spatial shifts in KV importance over time, we split the observation window into two halves: Strer and S For each half, we compute the average index of the top-B important KV pairs:
D Proot B. Sw
Σ 1ES
aaggmax (I)):
(10)
where 2 is normalization factor. Stre"t denotes the first half of queries within the input window g. Sw. Drear is computed similarly for the second half of the queries. The difference AD D Drear
Droott reflects how KV importance shifts across positions. We use this signal to adaptively adjust both the window size and shift:
Drear Dfront
W. =
+1.
(11)
B
Druce Dror
if D Proot Drear > 0,
7sbift
Disce Dioir
+ if Dromt - Drar S 0,
(12)
where W, is the window size and "shiitt is the shift of the sliding window. ,3 is a scaling factor that determines the granularity of the sliding window's movement, controlling the size of the steps taken when calculating the window shift and size. [-] represents the floor function, which rounds a number down the nearest integer.
In summary, the final eviction indicator, which incorporates both layer-wise output reconstruction and spatial-temporal smoothing, is as follows:
/2/22/ Tainn [((k)
[W,/2]+Hu
[n
(13)
W
The selected (Kr, Vr) is the subset of the original KV pairs, defined as:
Kr Kr D...) Vr Vr. D. argmax (I,),
(14)
where D: denotes the indices of the top B KV pairs based on the eviction indicator I, The same operation is applied to each head and layer, and different KV pairs can be selected for different heads in each layer.
EXPERIMENTS
4.1 EXPERIMENTAL SETTINGS
Backbone LLMs. We evaluate ReST-KV on five open-source LLMs spanning two mainstream
attention architectures: (1) Multi-head attention, Alama2-Chat (oouwron all 2023) and Gemma- Instruct (Deam et all 2022); (2) Grouped-query attention, Instru- (Dubey et al. 2024),
Mistral--nstrrutt-00.3 (Jiang el all 2023), and Qwen2.5-Instruet (Team (025)).
Baseline Methods. We compare ReST-KV with five baselines: (1) Fixed Attention Patterns:
StreamingL.MM (Xıao et 2023); (2) Eviction Indicator: H2O (Zhang et all (023), TOVA (Oren
aL 2024), SnapKV (Lictal 20246) LaCache (Shi (025).. We also incorporate adaptive
budget strategies from PyramidKV (Car el all (024)) and AdaKV (Feng et all, 2022l) into our method show compatibility.
Evaluating Tasks. We evaluate ReST-KV three prominent benchmarks: (1) LongBench (Ba atlll 2023), which tests long-context understanding across 16 datasets spanning six categories; and (2) RULER (Hsieh etl 2024), challenging long-context benchmark consisting of categories and 13 complex tasks; (3) Needle-in-a-Haysttack (Liu all 20244)), designed to assess the ability of models retrieve key information from long sequences; (4) InfiniteBench (Zhang et alj 202Ah), includes 10 tasks designed to test various aspects of long-context processing. Detailed results are reported in Appendix

---

Published as a conference paper at ICLR 2026
Performance comparison across 16 datasets of LongBench. The best result is highlighted in bold, and the second-best is underlined. ReST-KV achieves the best performance in most cases.
Table I:
SingleDDeement Document QA
Multi- Document
QA
Summirizatioe
Few-shot I camning
Synthetic
Cadee
Method
NAvQQ
Qusper
MF-enn
HorporQA
ZWiKMQA
Miniiqee
GevRepont
QM5aa
MottNows
TRFC
TriviaQA
SAMSon
PCouni
Pio
RD
Aug.
Llama-3.1 1-8R-Insmer,
64r,
S.reaming...MMM
5.08
18.03
38.50
9.78
48.21
I220
12:23
5.12
15.12
11.51
10.14
6.23
17.23
19.51
16.79
39.15
81.51
36.12
8.12
12.12 51
47.12 29.1222555
TOVA
18.52
6.12
17.32
12.15
13.51
7.35
16.24
20:41
16.34
38.41 82.61
36 16
8.14
95.03
55
47.35 30
Snapky
19.90
5.78
18.38
13.51
14:42
8.52
17:35
20.45
17.33
41.00 85.37
37.63
5.93
91.08
55.09
48.88 51.45
ReST-KV
22.43
7.19
19.25
14.11
15.04
7,92
20.56
21,10
19:15
53,50
88.23
40.21
8.46
93.50
56,74
16.77 33.54
512/.
StreamingLLMM
19:15
6.23
23.31
41.86
H20
26.23
7.34
20:51
11,52
13.52
7.34
21.24
23:14
58.50
20.15
7.25
TOVA
27.34
9.34
22.45
12.25
14.51
8,42
24.23
22.15
22.25
58.50 89.51
40.51
8:24
93.14
62.23
55.61 35.59
Suppk
28.00
9.83
24,84
13.77
15,40
10.21
25
22.75
24.25
65.00 92.34
41 69
8.42
96.
64.30
57.28 57.47
RoST-KV
32.01
10.73
25.23
15.91
15.85
10.25
26.47
23.23
24.79
69.00 91.62 62
42..59
8.40
97.66
63.48 56.03 28.33
Pull
32.02
13.12
27/52
16.60
16.41
11.41
$4.39
235.41
26.89
73.30
91:65
-.3..0
77.38
'/7.73
58.89 59.96
Mistral-70
Instruct-vO.3..
Bus
20.37
24.62
38.87
17.68
19.84
39.50
36.72
5.50
49.77
H20
20.51
21.52
25.12
40.12
33.12
19.34
16:23
19:12
16.24
38.50 83.12
57.23
6.00
$5.50
50, 12 48.12 34.93
TOVA
22.51
22.24
37.25
41.12
54.10
19:52
17.21
19.23
16.27
38.50 85,
58.5 38:51
6.50
86.
50
04 48
56
Sunoky
19.30
23.62
78
43.26
14.72
21.33
17.99
20:93
17.086
38.50 86. 96
39.61
7,00
90.50
51.63 49.73 57.53
ReST-KV
25.65
26.58
42.71
46.11
36.43
24.34
19,50
21,65
18,90
51,50
87,88
41.54
4,00
90.50
52,39
50.75 40,05
Mistral-78--
Rusi
6122
SMraminng...MM.
24.19
25.97
30.14
31.90
23.22
43.75
6.00
35
I220
25.23
30:41
40.32
42.52
35.23
18.23
24.23
21.24
23.21
66.50 86.71
43.15
5.00
K2.52
13 58.
TOVA
25.23
32.52
46.24
45.23
36.23
20.32
24.53
22.53
23.64
66. 87.24
44:21
6.00
85.62
50
35 60
60.24 42.85
SmapKV
26.84
35.51
53.12
49.56
33.72
26.54
25.06
24.03
24.76
67,50 89.36
44.82
5.50
95.50
69.44
61.22 65.66
RVST-KY
25.60
35,86
53,37
19.13
38.70
27.94
36.05
24.37
25.09
73,50 89.66
46.27
5.50
98. 50
60.81 46.47
Fall
25.07
30.54
52768
40.37
59.00
28.35
$5.07
75:11
27.05
76.00 86:50
'47.3"
6.00
50
38
62.66
18.1
Liama2/7B-Chon Busa
Streaming..MMM 5.61
15:51
6.42
14.14
16.77
1.36
12.09
16.46
12.83
17.25 15.12
10.93
4.50
3.00
22.00
15.24
11.83
H20
4.46
12.14
8.85
12.11
13.34
2.36
13.06
16.63
16.89
19.50 20.69
10:45
2.70
3,00
26. 50
16.06 12:43
TOVA
8.26
14.34
12.64
13.52
13.25
3,53
11.64
16.67
13.35
36.00
22.64
32.72
2.00
4.00
36.15
32.53 20.20
SunpKV
10.83
16.38
17:53
22.81
23.24
5.06
13.12
18.38
14.17
34.50 09:45
33.43
5.50
7.00
30.99
36,04 22.96
LaCache
7,42
4.36
13.09
17.46
18.12
12.93
5.50
24.00
17.34 13.51
RoST-KV
12.72
24,09
5.55
5.50
1.lmmu2-88-CMe Busi
512
StraaingL
15.30
15,53
20.16
26.59
25.05
5.65
18:30
19.28
21.84
54.50
82.23
38.07
5.50
5,00
56.80
51.95 28.36
H20
9.68
8.67
6.86
10.85
8.71
1.31
20.04
18.72
24.91
18.00 17.09
18.90
3.73
2.30
20.87
14.87
12:85
TOVA
13.53
15.46
26,44
26.12
31.02
7.12
18.2 25
18.64
22.34
62.50 83.10
40.61
3.00
8.00
56,
51.53
50.24
SmpKV
16.22
19.57
32.32
31.87
24.97
9.66
20, 19
20.77
23.85
62.00 82.24
39.
6.00
10.5
50
59.49
56.06
32.18
RoST-KV
17.15
32.71
23.59
30
Implementation Details. We evaluate ReST-KV and all baselines under varying cache budgets (Bosal = nL, with n E [64, 1024)). where n denotes the number of KV pairs per layer across L layers. To ensure fairness, token eviction is performed only once during the prefilling phase. All methods, except TOVA, are implemented based on the codebase from (Cail 2023).. Experiments are run on NVIDIA A800 80GB GPUs Further details are provided Appendix B.
4.2 EVALUATIONS ON LONGBENCHI DATASET
Llama3, In8t-nstruu
Mistral-7E-Instruuttae
Llama--7-CCB
Soua 9p.1
Shatth NolCabk
Jeawiings
Cale
100
AdC
gb Cacha
Cache Stmw
Cache Sea
Figure 4: Average score across 16 datasets of LongBench under various cache budgets. ReST-KV outperforms the baseline across different models and settings.
We evaluate ReST-KV on 16 datasets from LongBench. As shown in Figure g. ReST-KV consis- tently outperforms all baselines across different cache budget settings, with especially strong gains under tight memory constraints. Unlike prior methods that rely solely on the rank of query-key key sim- ilarities, our approach accounts the impact of attention redistribution, ensuring that the most critical information is retained. Moreover, we verify the compatibility of ReST-KV with non-uniform bud-
7

---

Published as a conference paper at ICLR 2026
get strategies such as Py and AdaKV, with results presented in Appendix D. Compatibility with KV cache quantization techniques is also evaluated, as shown in Appendix II
Table 0 provides detailed comparison under two cache budgets: low (Brota 64L) and high (Bwal = 512L), with full results in Appendix DJI. ReST-KV consistently ranks among the top performers across tasks, achieving up 2.58% improvement under low budgets with the Mistral model. Notably, ReST-KV substantially outperforms the recent LaCache (Shret 2025) baseline, with a particularly large gap the tightest budget (Brerl - 64L, Llama2-7B: 25.54 vs. 13.51). These results highlight the effectiveness of our eviction indicator and spatio-temporal smoothing in enhancing KV selection robustness. Additional evaluations across different models and sizes further confirm this conclusion (Appendix D D D
4.3 EVALUATIONS ON RULER BENCHMARK
We evaluate ReST-KV on 11 tasks from the RULER benchmark using the Llama3.1-8 1-8B-Instruct model, with fixed cache budget of Buai 1024L applied across all methods. Table Z summarizes the average accuracy across varying context lengths, from 4k to 128k context length. Existing KV cache eviction methods suffer from substantial performance degradation increases, highlighting their limited robustness in long-context and complex retrieval scenarios. In contrast, ReST-KV consistently achieves strong results across all lengths, with an average accuracy improvement of 15.2% over prior methods. Notably, even at the I 18k context lengthwhere less than 1% of the original cache is retained, ReST-KV maintains effective retrieval capabilities. Detailed results for individual tasks are provided in Appendix E.
the context length
Table 2: Performance comparison on RULER bench- mark across different context lengths.
Table 3: Ablation results of ReST-KV.
Method
Avg. Acc
Method
4K
8K
16K
32K
64K
128K
Avg.
Attention weight Top-k
32.98
Full
99.34
98.83
98.55
94.89
89.85
79.32
93.46
Streaming
39.81
18.42 12.10
10.57
9.91
8.18
16.50
ReST-KV
35.86
SnapKV
83,60
75.54
71.12
66.95
57.47
47.99
67.11
ReST-KV w/o LOR
33.95 (-1.91)
PyramidKV
81.35
73.66
70.23
69.83
57.84
48.93
66.97
ReST-KV w/o EMA
34.02 (-1.84)
ReST-KV
94.01
86.66
84.12
81.87
78.65
68.28
82.27
ReST-KV w/o AWS
33.50 (-2.36)
4.4 VISUALIZATION ON
TEST
The needle-in-a-hayee -hyssttccahaakkk test (Liu ct all 20ZE) involves inserting key information at random po- sitions within long contexts and serves as a benchmark to assess the ability of LLMs to accu- rately retrieve critical information. To further demonstrate the effectiveness and adaptability of our method, we conducted experiments on the Misttrl-7B--nnstruut-... model with a cache budget Bucut 1024L. As shown in Figure 5L even under such a strict cache budget, ReST-KV maintains 98% of the model's performance, significantly outperforming other methods. This under- scores ReST-K KV's ability efficiently prioritize and retain the most relevant KV pairs. Additional visualization graphs can be found in Appendix E.
4.5 ABLATION STUDIES
We conduct ablation studies on LongBench to evaluate the contribution of each component in our KV cache management strategy: layer-wise output reconstruction (LOR) indicator, exponential moving average (EMA) temporal smoothing, and adaptive hindow-based spatial smoothing (AWS). We adopt the 1l-ma3.1-8BB -nsttructt model with cache budget of B 128L as the default configuration.
Table El systematically presents the results. The baseline using vanilla attention attention-weight-baeee weight-basse based top- selection yields only 32.98 accuracy, as it ignores attention redistribution and fails to capture the spatial-temporal dynamics of KV pairs. In contrast, our ReST-KV framework achieves 35.86 accuracy, representing a significant improvement.
To further understand the effectiveness of each module, ablate them individually:
8

---

Published as a conference paper at ICLR 2026
(a) FullKV
(b) StreamingLLM
Parra-734 morrr Avarspe 50.0
Mira haiittd-00 The Avenes Soree
(c) SnapKV
(d) ReST-KV
Figure 5: Performance comparison on the Needle in Haystack Test using -
v0.3 with Bual 1024L. Even with strict cache budget, ReST-KV retains 98% of the model's performance, outperforming other methods in retrieving critical information.
0.38
SinapKV
Peak Memory (CB)
RvST-KV
0.30
ReST.V
60
Full Cashe DOM (NAA)
Decading Lafency
0.30
Full Cache w. FlashAlmm (NAA)
0.20
0.15
an
0.10
0.06
4k
8k
16kK
32k
64k
128k
256k
0.00
4k
8k
16k
32k
64k
125k
258k
Context Length
Context Length
Figure 6: Peak memory usage and decoding latency on NVIDIA A800 80GB GPU. ReST-KV duces peak memory by 36.0% and achieves up to a 10x speedup at 128k context length compared to full cache.
Without the LOR indicator, the model misses attention redistribution effects, making harder to identify truly critical KV pairs. This is especially harmful under tight budgets like Biotal 128L, causing 1.91% drop in accuracy.
Without EMA temporal smoothing: The model lacks awareness of temporal changes in im- portance, making less capable of retaining KV pairs crucial for future queries. This results in 1.84% performance degradation.
Without AWS spatial smoothing: Without capturing spatial offset patterns (e.g., vertical-slash structures), the model tends to retain suboptimal KV pairs, causing a 2.36% accuracy drop.
Hyperparameter Sensitivity. Figure / shows the performance variation with respect to a (left) and B (right). Both hyperparameters exhibit stable accuracy across wide ranges, consistently out- performing the baselines. All experiments adopt a fixed setting of a 0.3 and B = 2000 without any per-model or per-task tuning.
Detailed ablation of each module can be found in Appendix G
4.6 EVALUATION OF MEMORY AND THROUGHPUT
To evaluate the effectiveness and efficiency of method in reducing memory consumption and enhancing LLM inference, we analyze peak memory usage and decoding latency on the Llama-3.1- 8B--nstt model implemented with F (Dad (()23).

---

Published as a conference paper at ICLR 2026
Llama3.1 1e1.-11----nnn 8B-Instruct
Llama3.1 1aa-3..--8----ss 88-Instruct
35.5
35.5
34.5
34.0
34.5
Mean
AvgPool
Smoothing Factor
Factor
Figure 7: Sensitivity analysis of the smoothing factor (left) and scaling factor 3 (right). The performance remains relatively stable across different settings of both hyperparameters, mostly out- performing the baseline.
Peak Memory Usage. As shown in Figure aa),, ReST-KV significantly reduces peak memory usage, performing comparably to other KV cache eviction methods. Compared to full cache, ReST- KV achieves approximately 36.0% reduction in peak memory usage at a context length of 128k.
Latency Analysis. As shown in Figure (bb), the decoding latency of the standard full cache method, even with FlashAttention-2, grows rapidly with input length. In contrast, ReST-KV main- tains high efficiency by using a fixed cache budget to limit the number of KV pairs. This approach overcomes the latency bottleneck for long sequences, achieving an approximate 10.61 speedup over the full cache method at 128K context length.
Furthermore, ReST-KV is compatible with prefill sparse attention approaches, yielding Time-To- First-Token (TTFT) speedup of up 3.42x. This efficiency is achieved because our method only requires computing attention outputs within a small query window, resulting a computational complexity comparable to that of SnapKV. For a detailed analysis, please see Appendix FI
Prefill Overhead. Although ReST-KV computes an output-aware eviction indicator, it operates only on small query window of size w < N, sharing the same OwwN D) dominant complexity as SnapKV. Table shows the absolute TTFT under the 128k setting. ReST-KV introduces only R=2% prefill overhead over SnapK V Vneligiible for long-context workloads where decoding dominates total latency.
Table 4: Prefill TTFT at 128k context length (Llama-3.1 3.1ma-3..--110 1-8t-Inntrrue). ReST-KV incurs only R/2%
additional latency over SnapK confirming negligible prefill overhead.
Method
TTFT (ms)
Full KV
28,230
SnapKV 28,500
ReST-KV
29,082 (43.0%
CONCLUSION
In this paper, we propose ReST-KV, a novel KV cache eviction method that reformulates eviction as a layer-wise output reconstruction task, effectively capturing attention redistribution effects be- yond conventional attention attention-weight weight heuristics. To enhance robustness, ReST-KV integrates spatial- temporal smoothing mechanism using exponential moving averages for temporal stability and adap- tive windowing for spatial awareness. Extensive evaluations on LongBench, Needle-in-a-Haye in-a-Hasstack,, and RULER demonstrate that ReST-KV consistently surpasses state-of-the-an methods under low memory budgets and significantly reduces decoding latencyachieving up to 10x speedups at 128k context lengths. Our method is model-agnostie and compatible with existing budget strategies, of- fering practical and principled solution for efficient long- cong-context generative inference. Future work will explore tighter integration with adaptive allocation strategies and extensions to multi molli- or structured memory scenarios.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint wrxiv:2303.08772 2023.
Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant J Nair, Ila Soloveychik, and Pu- rushotham Kamath. Keyformer: Kv cache reduction through key tokens selection for efficient generative inference. Proceedings of Machine Learning and Systems, 6:114-127, 2024.
Authropic. Claude 3: A next-generation language model, 2023. anthropic. com/ (55009990100000001111333080000 http://6800766611888877777777 pdf.. Accessed: 2025-01-21.
URL Card Baarrd_Caadde____eeee
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 2023.
Zefan Cai. Kvcache-factory, 2023. URL http:///ghttb.ooceeeaaaaaaaaaaar
Accessed: 2025-01-21.
Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, et al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. arXiv preprint arXiv:2406.0200 2024.
Tri Dao. Flashattentionn-:: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.0869) 2023.
Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang. Glm: General language model pretraining with autoregressive blank infilling. arXiv preprint arXiv:2103.10360. 2021.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint arXiv:247..21783 2024.
Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S Kevin Zhou. Ada-kv: Optimizing kv cache evic- tion by adaptive budget allocation for efficient Imm inference. arXiv preprint arXiv:2407.1 11550, 2024.
Suyu Ge. Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for llms. arXiv preprint arXiv:2310.01801, 2023.
Zhiyu Guo, Hidetaka Kamigaito, and Taro Watanabe. Attention score is not all you need for token importance indicator in kv cache reduction: Value also matters. arXiv preprint arXiv:2406. /2335, 2024.
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, 2024. URL https: //arxiv.org/abs//300. 16137,
Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh. Michael W Mahoney, Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length 1lm inference with kv cache quantization. Advances in Neural Information Processing Systems, 37:1270-1303, 2024.
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. Ruler: What's the real context size of your long-context language models? arXiv preprint 4rXiv:2404.0665. 2024.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310006822, 2023.

---

Published as a conference paper at ICLR 2026
Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir Abdi, Dongsheng Li, Chin- Yew Lin, et al. Minference 1.0: Accelerating pre-filling for long-context Iims via dynamic sparse attention. Advances in Neural Information Processing Systems, 37:52481-5251 2024.
Xunhao Lai, Jianqiao Lu, Yao Luo, Yiyuan Ma, and Xun Zhou. Flexprefll:: A context-aware sparse attention mechanism for efficient long-sequence inference. arXiv preprint arXiv:2502.20766. 2025.
Haoyang Li, Yiming Li, Anxin Tian, Tianhao Tang, Zhanchao Xu, Xuejia Chen, Nicole Hu, Wei Dong, Qing Li, and Lei Chen. survey on large language model acceleration based on kv cache management. arXiv preprint arXiv:2412. 19442, 2024a.
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 arXiv:2404. 14469, 2024b.
Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-173 2024a.
Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A tuning-frre asymmetric 2bit quantization for kv cache. arXiv preprint arXiv:2402.02750 2024b.
MistralAI. Mistral large 2407: A new milestone in open-source language models, 2023. URL 24077, Accessed: 2025-01-21.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:1611.06440, 2016.
Matanel Oren, Michael Hassid, Nir Yarden, Yossi Adi, and Roy Schwartz. Transformers are multi- state mas. arXiv preprint arXiv:2401.06/00 2024.
Ziran Qin, Yuchen Cao, Mingbao Lin, Wen Hu, Shixuan Fan, Ke Cheng, Weiyao Lin, and Jianguo Li. Cake: Cascading and adaptive kv cache eviction with layer preferences. arXiv preprint arXiv:2503.12491, 2025.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code. arXiv preprint ar arXiv:2308.1299 2023.
Dachuan Shi, Yonggan Fu, Xiangchi Yuan, Zhongzhi Yu, Haoran You, Sixu Li, Xin Dong, Jan Kautz, Pavlo Molchanov, et al. Lacache: Ladder-shaped kv caching for efficient long-context modeling of large language models. arXiv preprint arXiv:2507.1422 2025.
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 axXiv:2407.15891 2024.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.0822 2024.
Qwen Team. Qwen2. A party of foundation models. Qwen (Sept. 2024). url: htps://qwendm. github. io/blog/qwen2, 5, 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov. Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.09288. 2023.
Zhongwei Wan, Xinjian Wu, Yu Zhang, Yi Xin, Chaofan Tao, Zhihong Zhu, Xin Wang, Siqi Luo, Jing Xiong, and Mi Zhang. D2o: Dynamic discriminative operations for efficient generative inference of large language models. arXiv preprint arXiv:2406. 13035, 2024.
12

---

Published as a conference paper at ICLR 2026
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:3399.14553, 2023.
Dongjie Yang, XiaoDong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao, Pyramidinfer: Pyra- mid kv cache compression for high-throughput Ilm inference. arXiv preprint arXiv:2405.12553 2024.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Tianyi Zhang, Faisal Ladhak, Esin Durmus, Perey Liang, Kathleen McKeown, and Tatsunori B Hashimoto. Benchmarking large language models for news summarization. Transactions of the Association for Computational Linguistics, 12:39-57, 57, 2024a.
Xinrong Zhang, Yingfa Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Khai Hao, Xu Han, Zhen Leng Thai, Shuo Wang, Zhiyuan Liu, et al. inftybench: Extending long context evaluation beyond 100k tokens. In ACL (1), 2024b.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, al. H2o: Heavy-hitter oracle for efficient gen- erative inference of large language models. Advances Neural Information Processing Systems, 36:34661-34710, 2023.
Xiabin Zhou, Wenbin Wang, Minyan Zeng, Jiaxian Guo, Xuebo Liu, Li Shen, Min Zhang, and Liang Ding. Dynamickv: Task-aware adaptive kv cache compression for long context 1lms. arXiv preprint arXiv:2412.14838, 2024.
13

---

Published as a conference paper at ICLR 2026
A DERIVATION AND ANALYSIS OF THE OUTPUT RECONSTRUCTION INDICATOR
We define the eviction indicator [,[1] as the reconstruction error of the MHA output caused by removing the n-th KV pair. Specifically, the eviction indicator is given by:
L [r|] ||MHA (x,, (Kr, Vr)) MHA (x,, (Kragn Vrza))l22
(15)
where Ke, and V 4,An represent the set cache keys and values with the n-th KV pair removed.
Using Eq. B and Eq. A. we can expand Eq. D as follows:
I [n] V. Wo ALA Vr Woll2
(16)
where An represents the attention weights with the r-th KV pair removed, and VrA represents the values corresponding the remaining cache sets after the removal of the n-th KV pair.
Further, we expand the matrix computation into weighted sum form as:
L [n]
Σ Am[m|v Wo
Σ TAA
Am.mmm|vm Wo
(17)
where A, [m[m] and [m.mmm] represent the attention weights for the m-th query in the presence and absence of the n-th KV pair, respectively.
Compared to A [m]. AcAn [m]] is missing the component related to kn in the denominator. There- fore, the relationship between the two is given by:
A [m]
A Am [m]
(18)
1 A,
Substituting Eq.
I8 into Eq.
and performing step-by-step simplifications, we get:
A m
L
Ammm]ym Wo
Σ
Vm Wo
(19)
A₁
[
mfn
A [m
A [n]
Σ Am wo
Σ
Vm W
Vn Wo
(20)
AnIn]
- A,[n]
m
A1
A m [.]]
A Vn Wo
Σ
As[m|ym Wo
(21)
the tith KV pair removedd's 's loss
the increase other components after removing the rith KV pair
A in]
V. Σ Amimb Wo
(22)
1 A [n]
A, [n]
|MHH (x,, (KY, VT)) v, Woll
(23)
1 [,A]]]]
that the layer-wise output reconstruction indicator be divided into two parts. One part is the loss due to the removal of the n-th KV pair, and the other part is the increase in the contribution of the other components after removing the 7-th KV pair. Together, these two parts determine the importance of KV pair.
From Eq. 21
B MORE IMPLEMENTATION DETAILS
In this section, we provide additional details regarding the implementation of ReST-KV. Our method operates in two main phases: prompi prefilling and token decoding. During the prompt prefilling
14

---

Published as a conference paper at ICLR 2026
the eviction indicator. This formula integrates both the smoothing. According to Eq. I4 we select set of KV pairs based the cache budget from the prompt. Specifically, for the Exponen- tial Moving Average (EMA) Temporal Smoothing, the smoothing factor a is set to 0.3. In the case of the Adaptive
stage, employ Eq. TB from Section G
layer-wise output reconstruction indicator and
Handow-Based Spatial Smoothing, the sealing factor 3 is set to 2000. Following SnapKV et ((24b), we adopt a fixed observation window of size S. = 32 and kernel size = 5 for SnapKV, PyramidKV, V, and our proposed ReST-KV. To better capture important informa- tion, we set the kernel size to 21 on the RULER and InfiniteBench datasets. The Streaming method retains the first 4 tokens as an attention sink, ensuring efficient processing within the token flow. In the token decoding phase, we utilize the KV cache compressed during the prefilling stage, along with a newly updated KV cache, to perform decoding. Notably, no further compression applied during this phase. This prefill-only eviction strategy is adopted for consistency with existing methods such as SnapKV and PyramidKV, enabling a fair and controlled comparison. ReST-KV can be straightforwardly extended to decoding- eviction by periodically re-evaluating KV impor- tance every M generated tokens, which feasible since the required attention statistics are already available from the decoding pass.
C COMPATIBILITY WITH BUDGET ALLOCATION STRATEGIES
In this section, we evaluate the compatibility of our method with existing budget allocation strate- gies. Specifically, we choose PyramidKV (Cai et all (DEE)) representative of layer-wise budget allocation strategies and AdaKV (Feng et all 2022)) as a representative of head-wise budget al- location strategies. We compared the average accuracy results of the Llama2-7B-
model on the LongBench datasets under varying total cache budgets (ranging from 64L to 1024L). Our ex- periments demonstrate that, when combined with these strategies, our method achieves similar or slightly improved performance compared to SnapKV combined with the same strategies.
Table 5: Performance comparison of SnapKV and our method with Pyramid layer-wise budget allocation strategies across varying cache budgets.
Cache Budget B
Method
Avg. Acc
64L
128L
256L
512L
1024L
SnapKV
22.96
28.31
30.90
32.18
32.99
29.47
PyramidKV
24.67
29.58
31.04
32.32
32.95
30.11 (1 0.64%)
ReST-KV
25.54
29.99
31.51
32.38
32.97
30.48
ReST-KV w. Pyramid
26.88
30.47
31.74
32.48
33.05
30.93 (1 0.15%)
Table illustrates the results of applying Pyramid layer-wise budget allocation strategies to both SnapKV and our method, comparing the performance differences before and after the addition of the strategy. As shown, the accuracy improvements are modest but consistent across different cache budget sizes. For instance, our method combined with layer-wise budget allocation strategies achieves a 0.45% increase in average accuracy across different cache budgets.
Table 6: Performance comparison of SnapKV and our method with Ada head-wise budget allocation strategies across varying cache budgets.
Cache Budget P
Method
Avg. Acc
64L
128L
256L
512L
1024L
SnapKV
22.96
28.31
30.90
32.18
32.99
29,47
Ada- V
24.89
29.93
31.21
32.28
33.01
30.26 (1 0.79%)
ReST-KV
25.54
29.99
31.51
32.38
32.97
30.48
Ada-ReST-KV
27.35
31.27
31.84
32.51
33.02
31.20 (1 0.72%)
Table G presents the results of applying head-wise budget allocation strategies to both SnapKV and our method, comparing the performance differences before and after the addition of the strategy. The results show that our method combined with V achieves 0.72% increase in average accuracy
15

---

Published as a conference paper at ICLR 2026
Table 7: Performance comparison across 16 datasets of LongBench on Llama3.1-8B-Inste for cache budgets from 64L to 1024L. The best result is highlighted in bold, and the second-bes beood is underlined.
Single Document
Mutii Document QA
Summarization
Few Learning
Syuthetic
Code
Method
NitsQA
Queper
MF-en
HAsporAA
ZWiKIMQA
Masigan
GovReyon
QMSum
MolliNwss
TNBC
Triria44
SAMSSom
PCami
RD-P Arg.
Llama3.1
Bess
Fuil
32.02
27.52
23.41
26.89
73.00
7.18
97.73
58,89
1Jam3.11 1-88 88---nstrrct, Byaa
641.
StraamingLLM
7.65
5.08
14.14
10.93
12.64
6.86
16.57
19.95
16.30
38.50 83.13
34.65
9.75
96.28
54.16
48.21
29.61
H2O
12.23
5.12
15.12
11.51
10.14
6.21
17.23
19.51
16.79
39.15 81.51
36 12
8.12
95.
51
25
47.12 12.112232 29.52
TOVA
18.52
16.24
36.
8.14
55.21
19.90
5.76
37.63
ReST-KV
22.43
7.19
19.25
14.11
7.97
20.56
21.10
53.50 88.23
40.21
8.46
56.74
48.72
Liama3.
1-815- Iis--nntructt Buxx
1225
LM
16.07
5.34
14.82
11.01
12.38
6.61
17.99
19.06
18.69
40.50
85.57
58.24
9.30
94.11
58.97
31.70
HZO
14.00
5.45
16.62
12.83
10.87
6.94
17.29
20.88
16.96
40.27 82.15
37.61
9.11
96 13
52.
48.16
50.46
TOVA
21.63
5.11
18.70
14.31
14.44
9.46
19.22
22.97
17,50
40.76 84.40
39.21
11.24
96.67
58.25
32.87
20.95
7.29
ReST-KV
27.88
22.22
9.32
22.95
41.36
8.20
58.78
51.50
1Jam33.
1-88-Instruct, Baxa
2361.
StreamingL..M
16.03
5.50
14.95
10.38
12.25
7.01
20.38
19.48
20.63
46.00
87.49
41.02
9.57
90.53
61
51 52.11
H20
13.99
6.48
17.76
13.41
11.10
7.38
17.64
21.74
18.21
40.29 82.22
38:11
5.50
96.39
11.53
49.14 30.92
TOVA
34.05
11.17
21.30
17.61
17.50
12.84
21.93
26.16
20.58
43.69 87.20
42.52
14.21
99.26
60.92
51.65 35.79
SnaoKV
27.83
22.21
90.63
40.79
7.39
RuST-KV
29.14
23.61
1Jam33
1-88-Instruct Busa
5120
Straaming.L.M
19:15
6.47
15.02
10:94
12.58
6:23
23.06
20.05
23.31
57.50 87.20
41.00
10.25
90.74
62.39
53.61 33.84
H20
26.23
7.34
20.51
11.52
13.52
7.34
23.23
21.24
23.14
58.50 86.12
40.15
7:25
91:00 61.
54.12 34.53
TOVA
27.34
8.34
22.45
12.25
14.51
8.42
24.23
22.13
22.25
58.50 89.11
40.51
8.34
93.
62.23
55.61 35.59
SmpKV
28.02
9.83
24.84
13.77
15:40
25
22.73
24.25
65.00 92.34
41. 69
8.42
95.31
64.30
57.28 37.47
ReST-KV
32.01
42.59
8,40
1-SB- Instruct,, Busa
1024Z
StreamingL.MMMM
20.50
8.0K
15:72
11.61
12.39
6.71
25.76
20.18
25:44
63.50 88.84
42.61
10.03
55.88 36
H2O
27.63
8.84
21.98
12.99
15.91
8.23
23.96
23.22
24.20
59.79 86,
41. 5.52
9.07
93.01
67.55 59
08 36
TOVA
29.82
9.73
25.10
14,92
17.53
10.20
27.06
23.20
24.78
59.89 92.21
43.49
10.38
95.36
61.88 57.47 37
SunpKV
31.95
11.26
25.56
15.13
16.18
10.79
26.07
23.06
25.89
50 91.90
42.5
7.67
98.16
64.53
58,30 38.61
RoST-KV
31.83
26.51
28.20
70.50
42.70
8.02
38,94
across all cache budgets. These results highlight that our method compatible with existing budget allocation strategies.
D ADDITIONAL EXPERIMENTS ON LONGBENCH
In this section, provide comprehensive experimental results LongBench (Bai et al 2022))
benchmark focused on long-context understanding, with input lengths ranging from 1235 to 18409 tokens. We perform detailed performance evaluations for three base models with cache budgets ranging from 64L to 1024I: Llama2-7B-CUI (Touvron et all 2023), Llama33.1885 1-8B-IIstrucc (Dubey ctall 2024),, and Mistral-7B-Innsruut--00. (Jrag et arl 20233 (Appendix D.I.). To demonstrate the generality of ReST-KV, we also conduct experiments across different models and sizes. In Appendix D221 report additional experiments on the Swen2.5-7B-Instruuc (Team, 2023)) and
Gemma-7B IB-Istruct (Team et all (0224) model architectures, and in Appendix D.3. we present ex- periments on the Llama2- 100--13--hhha and Llama3-70B 70n-t-rr model sizes.
D.1 DETAILED PERFORMANCE ACROSS CACHE BUDGETS
Tables A and g present the detailed LongBench results of ReST-KV and comparative meth- ods applied to Llama3.1-80 Overall, the results demonstrate that, compared to other methods, ReST-KV consistently outper- forms all baselines across all tasks in LongBench when applied to the test models with cache bud- gets ranging from 64L to 1024L. This proves the effectiveness and wide applicability of RV in efficient long-context processing using KV caches in open-source L.MS across domains.
and Llama2-7B-Chat, respectively.
16

---

Published as a conference paper at ICLR 2026
Table Performance comparison across 16 datasets of LongBench on Bestral-7B-Instrutt--ee for cache budgets from 64L to 1024L. The best result is highlighted in bold, and the second- is underlined.
Single Document
Multi Document
Summarization
Few sbot
Synthetic
Code
Method
NmrQA
Qasper
Mi--nn
Hospor2A
TWKIMGA
Masique
GovRepurt
QMSam
MotiNews
TREC
TrioleAA
SAMSum
PCout
RB-P
Misrrl-78 In-mmaaet-
Full
52.88
35,07
Mismnl-BB- (osmml-7B-Issmut--00 Bus
647.
Streamingt L.M
20.37
20.56
24.82
38.87
32.47
17.68
15:48
19.84
15.81
10 50 82:
36.72
5.50
50.00
49.77
47.90
34.24
H20
20.51
21.52
25.12
40.12
33.12
18:34
16.23
19.12
16.24
38.50
83 1.12
37.23
0.00
$5.30
50.12
48.12 34.93
TOWA
22.51
22.24
17.25
41.12
34.10
19.52
17.31
19.25
16.27
38. 50
85. 12
38.51
6.50
56.10
51.04
48
36.55
SmpXV
19.39
23.62
38.66
13.25
34,72
21:33
17.59
20.93
17.06
38. 50
86 96
39.61
7.00
90.50
51.63
49.73 37.53
RoST-XV
19.80
52.39
Mlstall-HBBLostness-- Bus
StreamingL.M
21.39
22.05
26.73
37.25
32.81
17.61
16.76
19.69
17.98
45.50 64
40.49
5.50
50.00
55.01
52.12 36.03
H20
22.39
22.98
26.92
42.51
33.19
19:20
16.50
20:70
16.82
41.12
87.10
39.76
8.58
36.19
50.81
53.01 36.76
TOVA
22.48
28.78
48.21
47.58
34.26
21:56
21.67
21:75
21.68
42.23
K7 04
42.10
2.08
94.58
56.97
54.76 40.54
SnspKy
25.04
25.42
47.88
46.25
16,47
24.00
21.22
22.74
21.15
45.00
88.74
45.07
4.00
95.00
56.81
55.75 41.38
ReST-KV
26.58
29.60
49.23
47,45
37.18
25.16
22.44
22.43
21.77
69.00
85. 18
43.84
5.50
96.50
56.33 29
55.13 43,52
Mistral-7B- Mistal-7B-
2761.
Streaming
16.71
19.13
H2O
24.51
23.78
27.97
33:95
19:87
17:42
23.36
17.32
11.88
86.92
TOWA
28.17
29:93
51.01
46.25
36.55
26.65
22.96
22.31
21.24
$4.34
88
42.45
2.16
94.49
57.39
58.04
42.61
SnepkCy
26.88
11.22
$1.40
48.89
16,80
27.33
22.85
23,66
25.15
$7.00 89.01
43.60
5.00
96.50
58.64
58.21 43.79
RVST-KV
27.43
34.24
52.11
18.81
38.25
27:20
24.31
23.33
23.24
72.50
65.
44.61
5.50
96.50
58.41
59.21
45.27
Mistral-8--
5121.
StreamingLLM
24.19
25.97
30.14
10.75
31,90
17:35
22.18
20.30
25.22
65 50 96.95
43.75
6.00
$1.00
35
56.36
39.68
IE2
25.23
18:23
25.25
36.25
24.53
35.62
SmppKV
26.84
53.12
49.56
17.72
26.54
25.06
24.03
24.76
67 50
5.50
98.50
ReST-KV
28.60
35.86
53.37
40.15
38.70
27.94
26.85
24.37
25.09
73.50 89.66
46.27
5.50
98.50
50.13
(0)84
46.47
Mistral 7B
Instruct v0.3, Dhea:
1024Z
Stremming
24.81
27.98
31.09
42.93
12.65
18.03
24.57
20.74
25.42
68. 50 88.
45.37
5.50
$2.50
51.07
59.21
41,19
IEO
28.23
32.61
42.96
15,03
38.39
20.56
26.50
24.01
25.10
69.37 68. 19
45.60
8.11
83.81
62.79
59,90
43.84
TOWA
29.10
53.78
38.39
28.33
23.75
100.47
62.25
SnapXV
37.25
53.35
19.25
38.54
24.49
26.27
99.00
RoST-KV
29.20
37.72
52.56
50.50
38.89
38.69
28.03
24.71
26.76
74.00 39.41
5.50
59.00
61.66
D.2 ADDITIONAL EXPERIMENTS ON MORE MODEL ARCHITECTURES
To further validate the versatility of ReST-KV across different model architectures, we performed additional experiments on the Swen2.5-7B-Innsrrus and Gemma-7B-Instrur models. The experi- ments were conducted in two distinet memory configurations: low-memory setting (Buaal = 64L) and a high-memory setting (Broal performs baseline methods in both the low and high memory settings for the Qwen and Gemma architectures, similar to the results observed with the Llama and Mistral models. These findings further confirm the adaptability of ReST-KV across various model architectures, demonstrating its robust performance advantage regardless of the underlying design of the models.
512L). As shown in Table M. ReST-KV consistently out-
D.3 ADDITIONAL EXPERIMENTS ON LARGER- SCALE MODELS
To assess the scalability of ReST-KY on larger models, we conducted additional experiments on Llama2- 1amma2-13B-Chhe 13B-Chat and Llama3-70B- 708--IntrnIttt These experiments were performed under two dif- ferent memory configurations: a low-memory setting (Broral = 64L) and a high-memory setting (Breal 512L). As shown in Table IΣл, ReST-KV consistently outperforms baseline methods in both low and high memory settings for the Llama2-138 13B-Chat and Llama3-70B. 70B-atsrret models. These results further demonstrate the scalability and effectiveness of ReST-KV when applied to larger-scale models, highlighting its continued performance advantage regardless of the model size.
D.4 COMPARISON WITH LACACHE
We compare ReST-KV with LaCache (Shr 2023) on Llama2-7B BhCat under percentage-bee cache budgets (25% and 50%) across all 16 LongBench tasks. As shown in Tables [ and II3. ReST- KV consistently outperforms LaCache under both budget settings, with the advantage particularly
17

---

Published as a conference paper at ICLR 2026
Table 9: Performance comparison across 16 datasets of LongBench on Jlama2-7B-Chat for cache budgets from 64I to 1024. The best result is highlighted in bold, and the second- best is underlined.
Singk- Doeument QA
Multi- Document
Q4
Summarization
Few-shot Learing
Synthetic
Code
Mothod
Nnv
Quaper
Mi--on
HapprQA
2WikIMOA
Musupe
GovReport
QM
MoltiNiwrs
TREC
IrvingA
SAMSio
PCoun
PRe
Lou
RB.P
Arg.
Llama2 7B Chat. Bus
Fall
Full
18.39
20.11
35.67
31,25
25.50
10.14
25.68
20,93
26.27
64,00
83.38
40.99
5.50
10.00
60.81 55.27 53.37
Liuma2 2-7B-Chat
64L
StreamingLLMMM 5.61
1,36
15.12
4.50
H20
4.46
8.85
12.11
13.34
2.36
16.63
19.50
10.45
2.70
12.42
TOVA
8.26
14.34
12.64
13.52
13.25
3,53
11.64
16.67
13.35
36.00
72.64
32.72
2.00
4.00
36.15
32.53
20.20
SmpkV
10.83
16.38
17.53
22.81
23.24
5.06
13.12
18.38
14.17
34.50 69.45
33.43
5.50
7.09
39.99
36.00
04 22.96
RoST-KV
12.72
17.17
24,09
24.71
23,80
5.55
15.18
19.71
17.45
43.50
76.17
33:42
5.50
5.00
45.00
40.61
25.54
LIuma2-78BCCm Bysi
1285
Stremiing 8.45
5.17
13.99
30.61
5.00
39.55
H20
9.53
9.92
15.64
3,30
17:25
13:85
4.17
TOVA
12:26
14.66
25.72
26.08
21.21
6.90
15:28
18.30
17.51
42.44
80.12
35:25
5.05
5.93
52.48
19.17
27.00
Snapky
13:32
16.28
27.25
22.23
34.32
7,12
16.97
19.65
19.58
44.00 81.88
36.93
6.00
5,00
54,02
50.66 28.31
RoST-KV
15.55
17.78
27.34
27.72
24.02
8,93
17.88
20.13
20:92
60.00
82.48
37.35
6.00
9.50
53.45
50.24
29.99
L.uma2-7B-- Bl-Chhll, Busi
256.
StramingLLL.M
13.81
17.65
24.48
7,70
16.16
19.33
44.00
78.87
57.63
5.50
5.00
54.57
49.68
H20
10.11
13,70
3,78
19.29
19.13
23.36
4.755
TOVA
14.12
29.15
27.69
6.9
18.67
57.01
5.06
8.71
56.91
52.99 29.97
SmaKVV
15.45
17.57
29:64
29.53
21.91
3.69
18.78
20:48
22.15
57,50 83,76
38.25
6.00
10.50
57.75
53.59 30.90
ReST-KV
15:23
18.57
30.46
31,53
25.85
9.09
19.13
20.83
22.28
63.00
82:57
39.05
6.00
11.50
17
51,91
31.51
Hlama2-7B-Chhil Chat, Bu
512C.
StreamingL.MM
15.30
15.53
20.16
26.59
25.05
5.65
18.30
19.28
21.81
51,50 82.23
38.07
5.50
5.00
56.80
51,95 28.86
H20
6.86
1.31
20.04
18:72
3.75
14.87 12:85
TOVA
13:53
26.44
7.12
18:25
18.64
22.34
83.10
40.61
3.00
SmaXKV
16:22
19:57
32.32
31.82
21.97
9.66
20.19
20.77
23.85
62.00 82.24
39.11 18
6.00
10.50
59.49
56.06 32,18
ReST-KV
17.15
19.88
32.71
31.94
25.62
9.97
20.52
20.68
23.59
63.50 83.30
39 20
6.00
11.50
59.65
53.81
32.38
Llamu2
7B- Chal, Bust
1026L
StreamingLLM
15.12
15.12
17.35
22.21
26.76
21.43
6.52
21.15
19.16
21.67
61.00 82.16
39. 69
6.00
1.50
57.73 53.24 29.92
H20
8.96
9.57
1,80
22.43
19.14
18.50 15.59
36.61
4.43
29,96
15.34
TOVA
16.84
38.90
9.51
20.34
23.42
10.05
SmgoKV
17:41
35.92
10.09
22.06
20.43
63.50 82.27
40.55
6.80
10.50
56.05
ReST-KV
17.39
20.01
35.35
31.71
25.33
9.60
22.20 30
20.85
24.91
63.50 83.73
40.76
6.00
10.50
60:57
54,95 52.97
pronounced the 25% budget. These results complement the ixed-budge comparison in the main
text (Table II..
E ADDITIONAL EXPERIMENTS ON RULER BENCHMARK
In this section, we present detailed evaluation of ReST-KV the various subtasks of the RULER benchmark (Hsieh et all 2024).. RULER is specifically designed to assess the core capabilities of LLMs in long-context scenarios through a diverse suite of tasks.
The retrieval suite includes four variants of the needle-in-a-haastack (NIAH) testSingle-Needle (S- NIAH), Mul (MK-NIAH), Multi-Query (MQ-NIAH), and Multi-Value (MV-NIAH)to evalu- ate recall accuracy under diverse distractor settings and query formulations. Beyond retrieval, the Variable Tracking (VT) task measures multi-hop reasoning by requiring models resolve transitive variable references scattered throughout the input. Lastly, aggregation tasks such as Common Word Extraction (CWE) and Frequent Word Extraction (FWE) test a model's ability to compress and synthesize high-density signal distributed across long contexts. Tontex tasks collectively pose dis- tinct challenges for context retention, salience estimation, and compositional reasoning, providing a holistic benchmark for evaluating memory management strategies like ReST-KV.
We evaluate ReST-KV using the I.L.MA-3, -3.1 1-88--8nstttce model with a maximum context window of B = 1024L, across input lengths ranging from 4k to 128k tokens. The evaluation compares ReST- KV with several representative KV cache eviction baselines: Full KV cache (oracle), StreamingLLM
(Xiao et all 2023), SnapKV (Lietal 20245), and PyramidKV (Cal 2022))
As reported in Table I2, ReST-KV consistently achieves higher average accuracy than all alternative eviction strategies across all context lengths. For instance, at 4k tokens, ReST-KV achieves aver- age accuracy of 94.01% %, substantially outperforming SnapKV (83.60% and PyramidKV (85.21 %).. While all methods exhibit declining performance as the context length increases, ReST-KV main-
18

---

Published as a conference paper at ICLR 2026
Table 10: Performance comparison across 16 datasets of LongBench on Qwen2.5-7B- Instructt and Gemma-7B 7B-Instruct. The best result is highlighted in bold, and the second-best best is underlined.
Single Document QA
Muli: Documeat Q4
Summarization
Few sbot Learning
Synthetic
Code
Method
Nav
Quaper
Mi--nn
HoporQA
2WikIMOA
Musupe
GovReport
QMSam
MoltiNiwrs
TREC
TrvingA
SAMSio
PCount
PRC
Lou
RB.P
Arg.
Qwen2.5 5 7B Instruct Biaa
Fall
Full
3
10:75
24.24
10.23
9.30
6.97
32.54
17.84
22,46
71,50
89.32
46 16
4.35
98.83
93 68.2 36.15
Qwen2.5.74 1ann2.5-7---man 7u-mmtus Burai
StreamingL.MM
5,53
7.62
7:20
4.35
12.20
11,96
39.50
6.29
H20
1:00
3,46
17:22
6.57
6.33
4.33
14.50
11.67
10.29
37.38
76.86
7.76
TOVA
2.19
3.58
17.34
8.23
8.14
5.96
16.48
13.38
11.36
37.94 78.75
39.12
7.79
85.47
47.93
50.24
27.12
SmpkV
3.86
5.58
18.71
8,59
8.11
6.01
16.96
13.67
13:21
39.50 79.09
40.39
7.92
87.02
48.
10
$1.52 27.97
RoST-KV
3.27
6.09
18.95
9.57
8.79
6.03
18.77
14.99
15.19
50.50
79.07
41.22
4.73
93.00
48.47
50,03 29.33
Qwen2
1reen2.5778. Iissuust Busi
5122
Siremming
1.98
6.70
8.28
8.27
4.15
22.54
13.15
85.96
43.43
6.84
H20
6.46
21.50
9.05
8.50
6.00
15.25
43.52
2.00
31.96
TOVA
2.70
7.99
21.77
8.61
8.57
6.61
23:44
16.34
19,42
64.28 82.98
44.41
2.35
94.70
59.23
63.58 32.94
Smapky
3.57
8.90
22.88
10:34
9:52
6.74
24.73
12.58
19.56
64.50 83.49
45.08
4.52
96.67
59.93 (4.54 53,90
RoST-KV
3.59
9.46
23.66
10.91
9.76
7.24
25.65
17.76
20.25
67.50
86,73
44.92
3.83
98.08 69.14
63.56 34,56
Gemmmn 7B- Instrcsc Bhs
Filk
Pull
14.28
33.12
41,08
30,75
26.11
23.95
19.31
23.86
69,50
36
4.00
35.92
48.47 48.79
Gemma 7B Instruct, Busi
6.1.
SLreamingLLMM
11.31
16.51
22.96
21,87
23.25
10.18
12:47
16.80
12.74
38.50 70.94
29.79
2.50
20.50 44.67
48.75 25.24
H20
10.37
15.93
33.35
26.09
23.65
12:52
12.49
16.94
12.99
39.15 90.42
52.33 23:23
3:20
24.41 46.00
49.05 22
TOVA
10.53
16.58
33.81
27.05
24.56
12.66
13.76
17.19
13.76
39.68 80.6
32. 67.67
3.68
25.70
46 01 49. 94 27.96
SmnoKy
13.05
17.06
14.22
27.41
25.32
13.52
13.98
12.35
14.0%
40.50 81
32,90
3,83
26.00
46 34 49.95 28.43
RoST-KV
13.10
22,90
36.78
28.36
25.90
15.13
15.39
18.09
15.68
44,50 82.55
32.77
3.33
36.25
47.92
18.70 30,46
Gemman Ens-nns Bosi
5126
StramingL...M
11:58
20.26
26.09
24/06
17.49
17.01
20.12
60:50
37.45
1.83
52.64
IE20
12.70
29.01
38.6
28.71
25.10
14.19
17.53
17.20
20.09
60.94 80.75
35:24
3.15
02.00
47.44 19.01 32.14
TOVA
13.23
29.30
39.3 32
29.63
23.57
14.55
18.1
18.32
21.01
61.13 81 499
35
1.61
54. 46
39
50.00 52:74
SnapKV
13.26
29.43
29.80
30.24
26.01
14.82
18.30
18.86
21.23
62.00 $1.51
36.04
4.33
35.08
19.16 50.73 33.15
ReST-KV
13.70
30.33
42,08
30.13
26.06
14.37
18.82
18.60
22.35
69,00 81.72
37.55
4,33
35.21
48.67 19.48 33,90
Table 11: Performance comparison across 16 datasets of LongBench on Llama models from 13B to 70B. The best result is highlighted in bold, and the second-best is underlined.
Single Document QA
Multi- Document
QA
Summatication
Few-shot Leuring
Synthetic
Cude
Method
NnvQA
Qusper
MF-en
HosporQA
ZWIKIMOA
Masque
GovReport
QMmam
MotaiNews
TREE
TrviagA
SAAtiom
PCount
PRe
Lou
RB-P
Arg.
Llama2 33 Chas, Bara
Fall
Full
19.19
25.86
37.04
36.65
33,22
14.02
25.92
20.24
26.02
65.00
87,70
35
3.60
11.00
51.26
53,15 34.09
Liama2-138-CC 8uw.
644
Streamingt 6.96
7.49
0.98
2.17
3,00
H2O
14.00
18.17
21.78
30.62
28.77
9.93
14.58
19.17
17.97
35.00 80.11
28.97
3.87
6.50
37.50
30.11
TOVA
15:10
17.12
26.22
34.11
28.32
10.69
14.60
18.89
16.83
33.57
36.42
29.99
3.13
9.79
40.48
38.05
26
SnapKV
16:05
17.20
21.85
31.51
28.72
11.52
15.30
19.34
16.89
31,50 86.87
30.94
3.51
10.00
49.65
26.22 26.82
RoST-KV
14.97
20.02
32.61
35.27
29.15
10.21
17:21
19.12
18.39
42,00
85.35
30.57
3.54
12.00
40.01
41.41 28.27
Llums2: (0mmm2-13B-Ca0 1----33--hh....
Bes
5126
StreamingL.LM
14.50
20:27
18.27
85.96
33.02
1.05
H20
17.28
27.81
32.98
10.66
21.57
19.50
9.50
47.58
TOVA
16.95
21.97
33.18
35.51
31.11
13.94
20.33
19.74
22.94
62.33 85.54
35.06
2.94
10.57
49.60
49.80
31,97
SmmpkV
17.46
22.46
33.79
36.39
31.37
14.46
20.51
19.81
23.76
62.50
85.08
35388
3.55
11.50
50.12
50.08 32.45
ReST-KV
18.00
23.72
34,49
36.21
33,55
15.43
20.67
20.20
24.24
66.50 87.37
35.01
4.04
11.50
49.90
50,89 33.17
Lluma3
70B- Instruct, Basa Full
Full
27.75
46.48
29.68
$2.04
54.90
32.37
27.62
73,50
45.72
12.00
72.50
41.70
69.00
Llama3
70B Instruct, Busa
Streamingl
24.11
27.63
25.53
41.00
48.39
23.27
17.07
40.00 77,20
13.00
72.50
H2O
24.07
31.33
27.49
44.83
49.00
25.14
22.31
20.59
24.50
49.50 91.45
40
12.00
72.50
44.97
60.65
40.03
TOVA
24.53
30.45
27.56
45.29
49.64
25.93
22. 30
20.08
23.46
48.56 11.18
40.23
11:85
72.50
44.31
60.65
39
SusgkY
23.97
32.92
14.96
46.35
$2.90
26.05
18.3 33
21.55
19.98
43.00 88.85
41.18
12.00
72.50
44
61.63 40.04
RoST-KV
26.32
36.38
38.44
89.51
53,18
26.20
20.02
21.81
21.48
59.75 88.51
40.51
12.05
71.50
45.22
61.22
42,01
1Jame3-70R-- Insttttttt.. Pyxa
512/.
Streaming...M
24
31.23
44.91
25.91
23.08
19.76
62.50 14
13.00
66.04
120
27.56
12.91
36.19
50.10
19.87
25.98
28.82
21.67
27.05
72.00 91.88
44.57
12.00
72.00
42.65
67.87 44
TOVA
27.51
42.49
35.71
51.02
30.42
25.12
27.55
21.60
27.28
22.04 92.04
45.13
12.89
78.18
43.51
68.
44
SnapkV
22.67
44.58
48.00
$1.66
53.73
30.61
24.50
22.82
25.89
70.00 92.63
45. 14
12.00
72.50
44.59
69.20 55.99
RV
27.85
45.21
50.06
51.55
54.45
29.83
25.77
22.55
25.83
72.50 92.63
46.59
12.00
72.50
13.41
68.95 46.36
tains a clear and consistent margin over the baselines, demonstrating its robustness in extended- context scenarios.
19

---

Published as a conference paper at ICLR 2026
Table 12: LongBench comparison with LaCache Llama2-7B-Char at 25% cache budget.
Mathod
NavQA Qusper
Mi-m
HutprQQ
2WikiMQQA
Visiqe
GorRpt
QASium
MukiNews
TRPC
TriviQ44
SAMSum
Pfc
1ez
RB-P
PulKK
18,30
20111
35.07
31.25
25.50
10.14
25.58
20.91
26.37
64.00
$3.18
40.99
5.50
10.00
60.51
55.27
33.57
17.65
24.69
29.15
LaCocke
17.65
24.69
29.15
22.66
ReST-KY
19.00
34.44
31.51
25.16
Table 13: LongBench comparison with LaCache on Llama2-7B-Chen at 50% cache budget.
NnvQA Queper
HorporQA
2WKIIQQA
Musiqne
GovRec
Q/55um
MuhiNews
TriviaQA
SAMSun
20.11
31.25
SteamiingLLM
19.77
23.22
25.71
RoST-KY
A breakdown by task category reveals that ReST-KV performs particularly well retrieval tasks (S-NIAH, MQ-NIAH, MV-NIAH) and multi-hop reasoning (VT), often approaching the accuracy levels of the full KV cache. These results indicate that ReST-KV is effective preserving seman- tically salient tokens under constrained memory. More challenging tasks, such as MK-NIAH-3 and the CWE aggregation task with uniform word distributions, remain difficult across all methods. Nonetheless, ReST-KY continues to outperform other eviction baselines in these settings, suggesting stronger resilience to task complexity and noise.
F ADDITIONAL EXPERIMENTS ON NEEDLE-IN-A TEST
Mrtr:/35aammeee Score
14
(a) FullKV
(b) Streaming
(c) SnapKV
(d) ReST-KV
Figure& 8: Performance comparison the Needle in Haystack Test using Mistral-7B-Instruuttve with B = 128T.
In this section, we present additional experiments further evaluate the effectiveness of our method on the
Haystackk test. This benchmark assesses model's 's ability to retrieve critical infor- mation embedded within long contexts. While Section ! already provides results for Mistral-7B. Instruct-v0.3 with cache budget of B 1024L, we extend analysis by considering additional settings: (1) Mistral-7B. Inntt-utttt---... with reduced cache budget of = 128L, (2) Llama3. 1-8B- Instruct under both B 128L and B 1024L.
Figures S. g and Ia illustrate the performance comparison under these settings. We observe the following key insights:
20

---

Published as a conference paper at ICLR 2026
Table 14: Performance comparison of ReST-KV and baseline eviction strategies on the RULER benchmark across multiple context lengths (4k to 128k tokens). Results are reported as average accuracy (%) over subtasks. ReST-KV consistently outperforms other methods, particularly on retrieval and multi-hop reasoning tasks. The best result is highlighted in bold, and the second-best underlined.
Method
S NAIII
S-NIAH-2
S-NAAR-1
MK-NIAIL-1
MK-NIAIR-2
MK-NIAI--1
MO-MIH
MV-NIAH
CWE
PWE
1imno-3.1-88-irdmmn
T0244, lengthi-4k
100.0
100.0
SIreamingLLM
30.05
Snapky
99.6
Pyrmiidy
36.2
99.70
100.00
49,80
1-88--mmeeet Rigal
10247,
lenghh:8k
Pull
100.0
100.0
10000
100.0
99:80
99.80
10000
95.75
97.62
95.27
99.92
98.85
Strcamingt IM
11.
12.0
13,00
14.2
11.0
11
12.55
12:45
4.16
85.03
13.56
18.42
SnapKy
100.00
98.4
12.0
50.0
85.6
7.6
97.8
87-45
56.96
88.27
99.76
75.
PynmidKV
100.00
99.50
3.0
99, 20
87.80
5.2
98.05
88.25
60.24
$9.00
99.68
73 66
ReST-KV
100.00
100,00
45.60
100,000
99.200
19:60
100.00
95.80
51.16
91.53
99.76
96.66
L.unto-3 3. 3.1-88--------.. AlB-Insttmett Blg
10242, cnntest lengtii1..
Full
100.0
100.0
100.0
92.60
100.0
99.00
99.85 85
98.25
90.90
95.67
99.80
96.
LL
5.6
5.80
7.2
6.0
5.00
5.2
6.7
0.18
78.53
6.52
12.1
Snapky
100.00
97.8
3.8
88.95
Pynaiidy
100.00
08 00
3.4
17.0
85.5
70.25
ReST-KV
99.800
17.00
Dest
contCAL Jength-222
100.0
Streaming
3.00
2.45
SnupKy
100.00
07.20
5,20
90
$1.00
2.0
87.25
16.96
71.27
98.64
56.95
PyramidyV
100.00
2.8
59.2
1.8
96.
83.2
10.52
75.2
ReST-V
100.00
100,00
98.20
99.60
99.00
15:20
99.95
97.60
9.36
83.53
95.16
$1.87
Liuana- 3.1-XBB Anscruct, E5,
10/244, COstEAt lengttl-644k
Fall
100.0
100.0
99 30.80
99 80
90.20
94.00
99:75
98.95
7.56
90.60
98.3 08.32
89.85
SIramingULM
2.0
1.6
2.4
2.6
3.0
0.80
2.05
2.8
0.14
90.87
1.76
9.91
SnapkV
100.00
96.4
3,20
99.00
32.2
0.2
91.7
58.45
2.86
54.53
93.60
$7.47
Pyrmiddy
100.00
56.30
1.0
F92.0
36.00
0.2
22.10
58.25
1.66
55.87
94.56
$7.84
ReST-KV
100.00
100.00
90.80
100,00
96.80
15.60
98.95
97.30
1.3
21.62
92.68
78.65
Llama 3.1 Instruct,
102-L,
length-1200
Full
97.40
97.30
95.20
96.20
$3.00
63.20
95.85
94.95
0.06
64.35
80.08
79.32
StreamingL..M
2.4
0.811
1.95
2.35
SnapKV
PyrmiidK
57.33
Ulnaa scred bendhergg Soxceet.
130
50C
FullKV
(b) StreamingLLMM
(c) SnapKV
(d) ReST-KV
Figure 9: Performance comparison on the Needle in Haystack Test using I.lama3. 1-81--88---ee 8-I-trett with B 128T.
(B = 128L) retains 76 % of the original accuracy, outperform- ing SnapKV by 14% This demonstrates that our method maintains strong retrieval capa- bility even under severe cache constraints.
21

---

Published as a conference paper at ICLR 2026
6c
(a) FullKV
(b) Streaming
Unnae aod tcree tan scate1.0
(c) SnapKV
(d) ReST-KV
Figure 10: Performance comparison on the Needle in Haystack Test using Llama3, 1----BI-Btttt
with B 1024L.
Llama3. Inststruttt (B- 128T.) achieves 74% accuracy, surpassing SnapKV by 6%, indicating its robustness in preserving key-value pairs under limited cache budgets.
Llama3.1-8B-Instee (B 1024L) attains 100% accuracy, meaning it can match full KV cache performance while storing only 1/32 of the original tokens. This highlights the efficiency of our approach in long-context retrieval with minimal memory usage.
These results further validate the robustness and efficiency of method in selecting the most relevant KV pairs while minimizing memory overhead. Notably, even with a significantly reduced cache budget, our approach consistently outperforms prior methods, ensuring reliable long-context retrieval across different models and settings.
G ADDITIONAL EXPERIMENTS ON ABLATION STUDY
In this section, conduct additional ablation experiments rigorously analyze the effectiveness of core components in ReST-KV and assess its sensitivity to key hyper-parameters.
G.1 EFFICACY OF THE PROPOSED OUTPUT RECONSTRUCTION INDICATOR
To evaluate the proposed eviction indicator, we compare it with different types of eviction indicators under the same baseline, including random selection, attention weights, attention weights weighted by the values's norm (A,[n] |/,1122) similar to the VATP method (Guo et all 20244), and our output reconstruction. As shown Table TE. directly weighting attention weights by the values's norm does not effectively incorporate the values information. Our method significantly outperforms all baselines, indicating that the layer-wise output reconstruction perspective better assesses importance of KV cache.
G.2 EFFICACY OF THE PROPOSED SPATIAL-TEMPON SMOOTHING
To assess the effectiveness of the spatial-temporal smoothing mechanism, perform ablation study to examine the impact of different smoothing methods. As shown in the left part of Table IT. various temporal smoothing techniques, including Mean, Inv-EMA, and EMA, are tested. Notably, EMA smoothing achieves the best performance, surpassing other baselines, which demonstrates its effectiveness in capturing temporal variations by giving higher weights to recent KV pairs.
22

---

Published as a conference paper at ICLR 2026
Table 15: Ablation study on different types of information considered by the eviction indicator. Us- ing output reconstruction the eviction criterion achieves the best performance, surpassing methods based on attention weights or their combinations.
Information Considered by Eviction Indicator
Avg.
Random
6.83 0.20
Attention weights (SnapKV)
33.95
Attention weights and values (VATP) Output reconstruction (Eq. equation 77)
33.88
35.86
Table 16: Ablation study on the effect of different temporal and spatial smoothing methods in the eviction indicator. EMA refers our proposed exponential moving average temporal smoothing. while AWS represents our adaptive window- basee spatial smoothing.
Temporal Smoothing
Avg.
Spatial Smoothing
Avg.
None
35.22
None
33.50
Mean
34.02
Avgpool
35.69
Inv-EMA
31.25
Maxpool
35.59
EMA (Ours)
35.86
AWS (Ours)
35.86
addition, we evaluate the spatial smoothing methods, as detailed the right part of Table IG. Methods such as Avgpool, Maxpool, and adaptive window-based smoothing (AWS) are com- pared, with AWS achieving the highest average performance. This suggests that the adaptive window-based approach, significantly enhances the eviction indicators ability adjust for vary- ing window sizes and offsets, thereby improving the assessment of the importance of KV pairs in the spatial-temporal context.
G.3 HYPER-PARAMETER PARAMETER SENSITIVITY ANALYSIS
The sensitivity analysis of the temporal smoothing factor and spatial smoothing scaling factor 3 presented in Figure M in the main text (Section H.S)). Both hyperparameters exhibit stable perfor- mance across wide ranges, and all experiments adopt the fixed setting 0.3, 2000 without per-model or per-task tuning.
H ADDITIONAL EXPERIMENTS ON EFFICIENCY
In this section, investigate the integration of ReST-KV with prefill optimization techniquesex- emplified by Minference (Jing et all (122)) and FlexPrefill assess potential improvements in Time To First Token (TTFT). To this end, conduct additional experiments the RULER 128k benchmark using the LLaMA3. 1-88-I-n-- Instruct model, focusing on the efficiency of our proposed KV cache eviction method, particularly its impact on TTFT and decoding latency. Results are sum- marized in Table I
Table 17: Efficiency analysis on RULER 128k. All results are normalized the Full KV caching baseline.
Method
1 128k Avg. Acc.
TIFT
Decoding Latency
Full ReST-KV
79.32
1x
1x
68.28
0.97
10.61 x
ReST-KV+MInferet
53.71
2.99x
10.41x
ReST-KV44FlexPPeilll(
0.9)
67.16
3.42x
10.46x
ReST-KKV=FlexPreiill 0.95)
68.12
2.37x
10.54x
23

---

Published as a conference paper at ICLR 2026
39.0
LongBench Avg. Score
34.0
29.0
Full Cache (16 bit)
ReST-KV
26.5
KVQuant (2 bit)
24.0
KVQuant (4 bit)
KIVI bit)
21.5
KIVI (4 bit)
KVQuant (4 bit) ReST-KV
19.0
10
40
50
Compression Ratio (%)
Figure 11: Comparison of ReST-KV, KV cache quantization methods (KIVI and KVQuant), and their combination Llama3.1-8B --8---1----nnnrr using LongBench dataset.
Our method is a KV cache eviction strategy that achieves a substantial improvement in decoding latencyover 10x speedupwhile maintaining comparable TTFT (0.97CE) to full KV caching. Im- portantly, it maintains high level of accuracy (68.28%), demonstrating that our eviction strategy preserves model performance effectively even under long context scenarios.
Furthermore, our method is orthogonal and compatible with sparse prefilling techniques such as MInference (Jiang et al,, 20224) and FlexPrefill all 2025). When combined with these meth- ods, we observe additional gains in TTFT. For example, integrating FlexPrefil with 0.95 achieves 2.37CE TTFT speedup while retaining high decoding efficiency (10.54CE latency speedup) and competitive accuracy (68. 12%). This shows that our approach not only accelerates decoding but also enables efficient and flexible integration with other prefill optimization techniques.
I INTEGRATION WITH KV CACHE QUANTIZATION
In this section, we further investigate the interplay between ReST-KV and established KV cache quantization techniques, specifically KIVI (Lmu eLal (IZAD) and KVQuant (Hooper et al, 20za)). Our goal is to evaluate whether combining ReST-KVa KV eviction method that accounts for the effects of attention redistribution and the with quantization or even outperform aggressive quantization applied to full, non-evicted KV cache under similar overall compression ratios.
dynamies KV selection can synergize
To this end, we compare ReST-KV, both in isolation and combined with KIVI and KVQuant, against a baseline using full KV cache with various bit-width quantizations. Figure M visually summarizes the results.
In particular, even with a stringent total compression ratio of 6.25%, achieved by combining ReST- KV with moderate 4-bit quantization, ReST-KV retains high average accuracy. In contrast, applying more aggressive 2-bit KIVI or KVQuant directly to the full KV cache results in significantly lower accuracy.
These results suggest that eviction strategies which explicitly account for attention redistribution and effective pathway KV cache compression
spatial-temports token redundancy can provide than quantization- only approaches. The combination of ReST-KV and lightweight quantization thus offers practical and robust solution for efficient inference under tight memory constraints.
24

---

Published as a conference paper at ICLR 2026
J ADDITIONAL EXPERIMENTS ON INFINITEBENCH
In this section, we evaluate ReST-KV on the InfiniteBench benchmark (Zhang et all, 2024h) to fur- ther assess its long-context capabilities. InfiniteBench tests LLM performance on extremely long sequences through a diverse set of tasks. These tasks include realistic scenarios such as novel-based reasoning (summarization, QA, multiple-choice, using novels with key entity replacement), dia- logue understanding, and code debugging. Additionally, synthetic tests probe specific onn-ccontext abilities like retrieval, state preservation, and sequential processing.
Experiments are conducted on the Llama3.1 model. We compare ReST-KV against SnapKV (Li etall, 20245), as both are post-prefill KV eviction strategies. To ensure direct comparison their eviction effectiveness, both methods retain fixed KV cache budget of 1024 tokens post-eviction, regardless the initial input context length.
Table IS details the average performance across InfiniteBench subtasks. ReST-KV achieves no- tably higher overall average accuracy than SnapKV (e.g., 38.8% vs. 36.8%). This performance tasks Retriieve.asssey. Retrieve.Numbot
advantage is particularly evident in retrieval-focusee Retrieve.KV), where SnapKV can exhibit critical failures on some subtasks. ReST-KV also gen- erally demonstrates stronger results in question answering (En.QA, Zh.QA) and Math.Find. While SnapKV may be competitive on select tasks like En.Sum, the consistent and superior performance of ReST-KV across wider range of demanding retrieval and reasoning tasks contributes to its substan- tially higher overall average. These findings underscore the efficacy of ReST-KV's reconstruction- aware eviction strategy when applied the challenging long-context scenarios presented by In- finiteBench. Notably, the En.QA subset has an average input length of 192.6k tokens and the ZA.QA subset averages 2,068.6k tokens (Zhang et all (024b)) directly covering the 2256k regime that ex- tends well beyond the 128k setting of the main experiments. The consistent gains of ReST-KV across these observation window nor the EMA-based temporal smoothing introduces cumulative degradation at extreme context lengths.
multi-million token sequences confirm that neither the fixed
Table 18: Performance of different methods on InfiniteBench.
Methods
RetrPaskkey
Retr.Num
Retr.VV
Ena
En.Sum
En.MC
En.QA
Zh.QA
Math.Find
Debug
Avg.
ReST-KV
100.0
93.7
11.4
10.5
22.9
67.2
13.2
13.1
34,0
22.3
38.8
SnapKV
100.0
87.1
0.0
23.7
67.7
11.3
12.2
34.0
22.3
36.8
25


Reviews:
[{"review_id": "5iZNDJahRK", "reviewer": "Reviewer_uohW", "summary": "This paper proposes ReST-KV, a novel KV cache eviction method that reformulates token importance as a layer-wise output reconstruction problem, explicitly accounting for attention redistribution upon token removal. It further enhances robustness via spatial-temporal smoothing: exponential moving average (EMA) for temporal dynamics and an adaptive window mechanism for spatial shifts. Evaluated across LongBench, RULER, Needle-in-a-Haystack, and InfiniteBench, ReST-KV consistently outperforms SOTA methods—e.g., +2.58% on LongBench, +15.2% on RULER—and achieves a 10.61× decoding speedup at 128K context with minimal accuracy loss.", "questions": "* What is the prefill-time overhead of computing the reconstruction-based indicator compared to SnapKV or H2O?\n* Could the reconstruction loss be approximated more efficiently (e.g., via Jacobian or first-order Taylor expansion)?\n* How does ReST-KV perform in multi-turn dialogue where context evolves incrementally over many turns?\nIs the method compatible with sparse attention patterns (e.g., Longformer, BigBird) during prefill?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Principled formulation: The reconstruction-based importance metric (Eq. 7) is theoretically grounded and captures attention redistribution, a key limitation of prior attention-weight-only methods.\n* Strong empirical results: Consistent gains across diverse benchmarks, models (Llama2/3, Mistral, Qwen, Gemma), and cache budgets (64L–1024L).\n* Robust design: Spatial-temporal smoothing significantly improves stability, as validated by ablation (Table 3).\n* Practical impact: 10×+ speedup and 36% memory reduction enable real-world deployment of long-context LLMs.\nCompatibility: Integrates seamlessly with budget allocation (PyramidKV, AdaKV) and prefill acceleration (FlexPrefill).", "weaknesses": "* Computational overhead: Computing reconstruction error requires per-token MHA re-evaluation during prefill, which may slow down the prefill phase (though decoding benefits).\n* Hyperparameter tuning: EMA factor α and spatial scale β require tuning, though sensitivity analysis shows robustness.\n* Limited theoretical analysis: While empirically sound, formal guarantees on reconstruction error vs. downstream task performance are missing.\n* Focus on prefill-only eviction: No dynamic eviction during decoding, which may limit adaptability in streaming settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i9dZCLbJOz", "reviewer": "Reviewer_4XR7", "summary": "This paper introduces a KV cache eviction method ReST-KV for LLM inference to improve robustness and efficiency under limited cache budgets. The key idea is to reformulate the eviction process as a layer-wise output reconstruction problem, estimating token importance by measuring output discrepancies when a KV pair is removed. The method further incorporates spatial-temporal smoothing through EMA and adaptive windowing to stabilize token selection over time. Experiments show improvements in accuracy and latency over prior eviction baselines.", "questions": "please see weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors clearly articulate the practical motivation behind efficient KV cache management.\n\n- The proposed method is evaluated across multiple backbone models, and comprehensive ablation studies are conducted for each component.\n\n- I have reviewed and reproduced the code in Appendix; it is well-organized and easy to follow.", "weaknesses": "- Measuring token importance by reconstruction error is essentially equivalent to attention-weight reweighting already explored in H2O, which models the same relationship between attention redistribution and output sensitivity.\n\n- The EMA and adaptive window strategies are simple post-processing heuristics. Also, the authors do not include any hyperparameter sensitivity analysis.\n\n- The evaluation focuses on retrieval-oriented long-context benchmarks, without including instruction-following or multi-turn dialogue scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7tGS8sCrvL", "reviewer": "Reviewer_PCdR", "summary": "The paper proposes ReST-KV, a KV cache eviction method for efficient long-context LLM inference. It reformulates KV eviction as a layer-wise output reconstruction problem to capture attention redistribution effects and introduces spatial-temporal smoothing (EMA and adaptive windowing) to stabilize KV selection.", "questions": "- How can ReST-KV be made compatible with prefix cache reuse or shared KV pools in modern inference systems such as SGLang or vLLM?\n\n- What is the computational cost of evaluating Eq. (7) in real-time decoding, and how is it amortized?\n\n- How would the approach behave under multi-turn interactive scenarios where KV eviction and reuse interleave dynamically?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper correctly identifies the attention redistribution problem ignored by prior eviction methods and offers a principled reconstruction-based indicator.\n\n- Experiments are extensive, covering multiple long-context benchmarks and backbone models.", "weaknesses": "- Limited novelty: The layer-wise reconstruction objective largely follows standard Taylor-based pruning and reconstruction heuristics, and the smoothing mechanisms resemble temporal averaging used in previous cache compression work. Conceptually, the step from SnapKV to ReST-KV is incremental.\n\n- The approach is not compatible with prefix caching frameworks such as SGLang. Because ReST-KV relies on layer-wise recomputation and global reconstruction loss, it cannot be easily merged into multi-request serving or cross-session KV reuse. This seriously limits real-world deployment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "00bMH9Bj9i", "reviewer": "Reviewer_fJbv", "summary": "The authors argue that existing eviction methods, which primarily retain tokens based on high raw attention weights, are suboptimal. In light of the core flaw they identify is that these methods ignore the effect of attention redistribution, they propose ReST-KV, a novel KV cache eviction method that explicitly models attention redistribution and spatial-temporal dynamics, significantly improving LLM efficiency for long-sequence generation.", "questions": "see weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Reframing eviction as an output reconstruction problem rather than a key-query similarity problem is a more principled and robust approach.\n\n2. The experiments are thorough. The method is tested on multiple models om multiple benchmarks and under various cache budgets.\n\n3. Ablation study shows the effectiveness of the proposed method.", "weaknesses": "1. Does ReST-KV only evict tokens from the prompt during prefill? Or does it also evict tokens from the generated context during decoding?\n\n2. The autghors justifies that the greedy, one-token-at-a-time removal heuristic by citing local linearity assumptions.This is a very strong assumption, as the softmax operation is highly non-linear, and removing one token can cause drastic, non-local redistribution. While the greedy approach is pragmatic, its justification is weak. A brief discussion of why this approximation holds in practice would be beneficial.\n\n3. The Adaptive Window-Based Spatial Smoothing is complex and need more explanation. It computes the average index of the top-B tokens in two halves of a window to get a \"shift,\" which then defines a new window size ($W_s$) and shift ($\\gamma_{shift}$). This feels like an overly-engineered heuristic. A simple and intuitive explanation is needed here. And how sensitive is the model to the hyperparameter $\\beta$?\n\n4. authors may need to compare the most recent baseline[1]\n\nReferences:\n\n[1] LaCache: Ladder-Shaped KV Caching for Efficient Long-Context Modeling of Large Language Models, ICML'25", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CTStwMNyqu", "reviewer": "Reviewer_iKEa", "summary": "To address the limitations of existing KV cache eviction method, which overlook attention redistribution effects and spatial-temporal dynamics in token importance, this paper proposes ReST-KV, a robust eviction framework for long-context LLMs. ReST-KV reformulates eviction as a layer-wise output reconstruction optimization problem: it quantifies KV importance by the reconstruction loss caused by token removal and enhances robustness via two smoothing mechanisms. Experiments on 5 LLMs across 4 long-context benchmarks (LongBench, RULER, Needle-in-a-Haystack, InfiniteBench) show  accuracy improvement. It also integrates seamlessly with budget allocation (PyramidKV/AdaKV) and quantization (KIVI/KVQuant) techniques.", "questions": "1. How does ReST-KV perform at 256k/512k context lengths? It is better providing latency/accuracy data for 256k or longer context on benchmarks and analyze cumulative smoothing errors.\n2. What fraction of prefill time is spent computing the layer-wise reconstruction indicator? Can lightweight approximations (e.g., sampling 10% of tokens to estimate reconstruction loss) reduce overhead without accuracy degradation?\n3. ReST-KV is evaluated on autoregressive LLMs, does its design generalize to non-autoregressive (NAR) or diffusion-based LLMs (e.g., LLaDA)? NAR models have different attention dynamics, do the reconstruction indicator and spatial-temporal smoothing need modifications?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Unlike baselines (SnapKV/H2O) that rely solely on raw attention weights, ReST-KV’s eviction indicator is derived from MHA output reconstruction loss. This formulation explicitly models two critical effects: (1) Nonlinear attention reweighting amplifies high-competition KV pairs; (2) Redistribution sensitivity measures how well remaining tokens compensate for the removed KV pair. Ablation shows this indicator outperforms attention-weight-only methods.\n2.  Assigns higher weights to recent KV pairs mitigates short-term fluctuations in token importance. Ablation confirms it outperforms mean/inv-EMA smoothing by 1.84% accuracy.", "weaknesses": "1. ReST-KV is only tested up to 128k context. For 256k+ tokens, two issues arise: (1) The fixed observation window size may fail to capture long-range spatial dynamics (e.g., \"vertical-slash\" patterns spanning 1k+ tokens); (2) Cumulative errors in EMA smoothing could distort temporal importance estimation (older tokens are overly dampened). The paper does not report performance at 256k+ or adjust hyperparameters for extreme lengths.\n2.  Computing the layer-wise reconstruction indicator requires extra MHA forward passes for each token removal (theoretically O(L) per eviction step). For 128k context, this adds non-negligible prefill overhead, though the paper reports TTFT comparable to full cache (0.97×), it does not quantify the breakdown of reconstruction calculation time. This could become a bottleneck for low-latency applications (e.g., real-time dialogue).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)