$\text{D}_{2}\text{O}$: Dynamic Discriminative Operations for Efficient Long-Context Inference of Large Language Models
Authors: Zhongwei Wan
Xinjian Wu
Yu Zhang
Yi Xin
Chaofan Tao
Zhihong Zhu
Xin Wang
Siqi Luo
Jing Xiong
Longyue Wang
Mi Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Efficient inference of LLMs
Long context
Primary area: foundation or frontier models, including LLMs
TL;DR: A novel method that utilizes two-level discriminative strategies to optimize KV cache size without fine-tuning, while preserving essential context

Abstract: Efficient generative inference in Large Language Models (LLMs) is impeded by the growing memory demands of Key-Value (KV) cache, especially for longer sequences. Traditional KV Cache eviction strategies, which discard less critical KV-pairs based on attention scores, often degrade generation quality, leading to issues such as context loss or hallucinations. To address this, we introduce **D**ynamic **D**iscriminative **O**perations ($\mathbf{D_2 O}$), a novel method that optimizes KV cache size dynamically and discriminatively at two levels without fine-tuning, while preserving essential context. At **layer-level**, by observing the varying densities of attention weights between shallow and deep layers, we dynamically determine which layers should avoid excessive eviction via our proposed ***dynamic allocation strategy*** to minimize information loss. At **token-level**, for the eviction strategy in each layer, $\mathbf{D_2 O}$ innovatively incorporates a ***compensation mechanism*** that maintains a similarity threshold to re-discriminate the importance of currently discarded tokens, determining whether they should be recalled and merged with similar tokens. Extensive experiments on various benchmarks and LLM architectures have shown that $\mathbf{D_2 O}$ not only achieves significant memory savings and enhances inference throughput by more than 3$\times$ but also maintains high-quality long-text generation.

Published as a conference paper at ICLR 2025
D20: DYNAMIC DISCRIMINATIVE OPERATIONS FOR EFFICIENT LANGUAGE MODELS
INFERENCE OF LARGE
Zhongwei - Xinjian Wust
Yu Zhang
Xin Chaofan Tao
Zhihong Zhu Xin Wang Siqi Luo"
Jing Xiong'
Longyue Wang"
Mi Zhang' Tongji University
'The Ohio State University
Universityy of Chinese Academy of Sciences
"Nanjing University 'The University of Hong Kong
PPkingg University
Alibaba International Digital Commerce
htips://githas: www.moom MLSys- Lab/ddo
ABSTRACT
Generative inference in Large Language Models (LLMs) is impeded by the growing memory demands of Key-Value (KV) cache, especially for longer sequences. Traditional KV cache eviction strategies, which discard less critical KV pairs based on attention scores, often degrade generation quality, leading to issues such as context loss or hallucinations. In this work, we introduce Dynamic Discriminative Operations (D, a KV cache compression method that optimizes KV cache size dynamically and discriminatively at two levels without fine-tuning, while preserving essential context. At layer level, D₃O leverages the varying densities of attention weights between shallow and deep layers dynamically determine which layers should avoid excessive eviction via a novel dynamic allocation strategy minimize information loss. At token level, D2O incorporates compensation mechanism that maintains a similarity threshold to re-discriminate the importance of currently discarded tokens, determining whether they should be recalled and merged with similar tokens. We conduct experiments on various benchmarks and L.M architectures. Our results show that D2O not only achieves significant memory savings and enhances inference throughput by more than 3 but also maintains high-quality long-text generation.
INTRODUCTION
Large Language Models (LLMs) (Achiam et al.
2023 Touvron al. 2023 Meta 2024 Jiang et al.
2023 Wan et al., 2023) excel in tasks requiring long contexts such dialog systems (Chiang ct al.
2023). >. document summarization (Zhang et al. 2023), question answering (Kamalloo et al. 2023). and code completion (Roziere al. 2023). Such long contexts demand significant amount of Key- Value (KV) cache. For instance, a model with 30 billion parameters, processing inputs of 1024 tokens batch size of 128, requires up to 180 GB KV cache (Zhang et al. 2024c). Such bottleneck underscores the critical need for KV cache optimization.
To minimize memory demands of KV cache, let al. (0236) IZhang et al., 2024c Liu et al.] 2023 Ren & Zhu [024) /Zhang et al., Ge et al. 2023). where the key to identify a subset of K Vs be evicted from the cache. However, existing methods all suffer from both layer-level and token-level information loss. Specifically, at layer level, existing methods equally treat all the layers and indiscriminately evict KV pairs at each layer. However, not all the layers exhibit the same patterns. Figure [ visualizes the attention weights on the GSMSK dataset (Cobbe et al., 2021a). As shown, the shallower layers (layer and 1) display densely interconnected attention maps, while the deeper layers (layer 30 and 31) exhibit a staircase sparse pattern, where attention is localized to specific context segments, with only a few tokens in each segment receiving substantial attention. This observation aligns with findings from (Zhao et al. 2024a] b), indicating that while shallower layers primarily engage with syntactic structures through global attention, deeper layers target task-related semantic knowledge with localized attention. Consequently, applying the same eviction strategy indiscriminately across all the layers may compromise important information in long contexts. At token level, shown in
effective method is KV cache eviction (iiao)
Project leader. 'quual contribution.

---

Published as a conference paper at ICLR 2025
0.0010
0.0006
0.0004
0.0002
(a) layer 0
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
-.0000
Figure I: Attention map density comparisons of shallow layers (layer 0, 1) and deep layers (layer 16, 30, 31) of LLaMA-2-7B on the GSM8K dataset. We use the mean value of heads for each layer.
Figure 2 (a), existing methods enable models to operate within a constrained KV cache budget by either directly dropping KV pairs (e.g.. StreamingLLM (Xiao et al. 2023b)) selectively removing them based on specific eviction strategies, such as using cumulative attention scores (c.g., H2O (Zhang
et al.) 2024ch) mean attention scores (e.g., RoCo (Ren & Zhul 2024).. However, the irreversible nature of eviction and the difficulty in accurately predicting which KV pairs are essential for future text generation can lead to information loss, causing hallucinations, contextual inconsistencies (Yang)
et al. 2024b), and challenges in maintaining long-context integrity (Bai et al. 2024).
In this paper, we introduce Dynamic Discriminative Operations (D2O), a KV cache compression method that tackles the two fundamental issues of existing methods. The key idea of D2O is to incorporate dynamic discrimina- tive operations at both layer level and token level. Specif- ically, at layer level, based on the findings in Figure [ unlike existing methods that indiscriminately evict KV pairs, O2O proposes dynamic allocation strategy using inverse variance softmax, adjusting the KV cache bud-
Eviction
Others
Attention Score Ranking
Permanent Discard
EMA Threshold
Ours
get for each layer based on the density metric of the at-
tention weights. At token level, given the uncertainties about how discarded tokens might affect future outputs, D2O introduces an effective compensation mechanism by maintaining an exponential moving average (EMA) threshold that assesses the degree of similarity between previously discarded and retained tokens, allowing D₂O to dynamically decide whether a currently discarded token should be recalled and merged with a similar token retained in the current KV cache according to the current EMA threshold in order to compensate the information loss of KV cache eviction, as shown in Figure
Similarity Merging Discard
Current KV Cache
(b)
Figure Existing methods (a) vs. D2O (b) at token level.
(b). Through these operations at layer level and token level, D₂O maintains the KV cache at a consistent size while being able to preserve valuable information from evicted tokens, enabling LLMs to handle the generation of extended texts with improved memory efficiency and high-throughput inference while minimizing the loss of contextual information.
We evaluate D2O and compare it with state-of- the-art art KV cache compression methods: StreamingLLM (Xiao et al, 2023b), H₂O (Zhang et al. 2024c). RoCo (Ren & Zhu 2024), pyra- midK V Cai et al. (2024b), and CaM (Zhang et a..). To demonstrate the generability of D2O, we conduct our evaluation using four models from three different LLM families (Llama, Falcon, and Mistral) and diverse tasks involving math and commonsense reasoning, long-context QA, summariza- tion, and code completion, drawn from LM-Eval (Gao al. 2021). LongBench (Bai al. (023).
Long-contex: fact retrieval (Kamradt 2023), and language modeling [Rae et al. 2019) benchmarks. We highlight five of our findings:
(1) Under the same reduced KV cache budgets, D2O consistently achieves superior perfor- mance on reasoning tasks compared state-of-the the baselines.
(2) For long-context tasks, D2O outperforms state-of-the-at baselines on LongBench with minimal accuracy degradation.
(3) D2O also outperforms state-of-the-ard baselines on the Needle In A Haystack task, demonstrating superior long-context fact retrieval capabilities.
(4) Even with a limited KV cache, D₂O is able to effectively leverage long- distance depen- dencies in language modeling, achieving superior performance compared to state-of-the-ar baselines.
(5) Lastly, D₂O enables larger batch sizes and is able to achieve up to 3,04 times higher throughput than the original model in our experimental setup.
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
Non- -rainaiiee KV Cache Compression. Majority of existing non-trainable KV cache compression methods reduce KV caches by focusing on evicting less crucial KVs. For example, Mistral-7B (Jiang
et al.) 2023). StreamingI.IMM (Xiao al. 2023b) and SirLLMMs (Yao al., 2024 focus tokens crucial for near-eeuuence generation. H2 (Zhang et al., 2024c). Scissorhands (Liu et al. 2023)
and RoCo (Ren & Zhu, 2024) maintain a small set of influential tokens based on attention scores.
FlexGen (Ge et al. 2023) adopts importance policies based on attention scores for KV eviction, while
SnapKV (Li et al. 2024) uses a recent window strategy to compress KV cache for long prompts.
PyramidKV (Cai et al. (2024b) and PyramidInfer (Yang et al. (202a)) propose the layer-wise KVs eviction strategies. NaCL (Chen et al. (2024) combines proxy-tokens and random eviction to keep robustness of LLMs. However, these methods can significantly lose context from evicted KVs.
Trainable KV Cache Compression, Some methods attempt to adapt LLMs to learn KV cache compression by training on selected datasets. For example, LESS (Dong et al. 2024) learns the residuals between the original and approximated attention outputs from a sparse policy applied during training. DMC (Nawrot al. 2024) pre-trains on original data to learn parameters that control compression across various heads and layers in the KV cache. However, training on selected datasets poses challenges in adapting these methods to diverse downstream tasks due to limited generalizability. Unlike these approaches, D,O employs a plug-and-play method that requires no additional training, offering broader applicability without the need for dataset-specific tuning.
Token Merging. Token merging (Bolya et al. 2022: Shi et al. 2023) consolidates tokens into fewer, more meaningful units while preserving information integrity. This approach has emerged as a preferred alternative to token pruning for reducing the token count. Methods such as ToMe (Bolya)
ct al. 2022). TPS (Wei et al. 2023), MG-VIT (Zhang et al.] 2024b), and PPT (Wu et al. 2023) ) have applied token merging and pruning techniques for visual representation. However, these approaches mainly focus on merging the hidden states and are primarily designed for visual classification tasks. Recently, CaM (Zhang et al.) proposes use Bernoulli process generate mask for value state merging on the KV cache during long-text generation. It still employs a uniform merging strategy across all layers, disregarding variations in attention density between layers. D₂O addresses the above issues by performing merging directly on the KV cache with a dynamic layer-level KV cache allocation and a dynamic merging strategy based on an EMA threshold. This prevents excessive information loss during KV cache compression in long-text generation tasks and improves efficiency for autoregressive tasks LLMs.
PRELIMINARY: GENERATIVE INFERENCE WITH KV CACHE
Standard generative inference of an LLM includes two stages: prompt encoding and token generation.
Prompt Encoding. In the prompt encoding stage, a prompt sequence is utilized to generate a KV cache for each Transformer layer within an LLM. Consider an input prompt tensor X E R T.smauye x D. where Lpramp represents the length of the prompt and D denotes the hidden dimension of the model. For simplicity, the indices for heads and layers are omitted. The key and value tensors are derived as:
K = XWK. K. V XWV.
(1)
where WK, Wv E DxD represents the weights for the key and value layers, respectively. Once K and V are computed, they are stored in the KV cache facilitate the token generation process (Otl et al. 2019 Wolf et al. 2020).
Token Generation. In the token generation stage, KV cache is both utilized and updated to se- quentially produce tokens. For each time step i, only the keys and values for the new token x; are computed whereas those for x<i are retrieved from the cache. Then the cache updated and the output of newly generated token is as:
K == K. kl. V
(2)
Xx,out Softmax (q.K") /VD V. x
where We E DxD is the weight matrix of the query layer. The linear expansion of KV cache with each new token significantly increases memory usage and latency, particularly for longer prompts, underscoring the importance of compressing the KV cache.
3

---

Published as a conference paper at ICLR 2025
Layer Cache Size Allocation
00
6,45
Prompt Encoding
Column
Dynamic Affecation
Bum
Stralogy
Generation
Jayr
Coche
Calculate F!
Layer Cache Size Allocation
Cache Siee Each Layer
Leoa
Token Eviction
Dynamic Token Merging
Generating Token 1001:
EMA Threshols
Dynamic Taken Merging
Nearest Neighbor
Weighted Merging
Matching
Aftertion Soore Ranbiing
Atterion
cied Tocks
Recent Token
CHASgEETIaTiO mucchoonive
Figure 3: Overview of D2O. For the layer cache size allocation at the layer level, D₂O addresses the issue of inconsistent attention density across higher and lower layers by incorporating dynamic cache each layer. The size of the cache determined by the variance metric attention and dynamic allocation strategy. token level, D2O addresses long-context information loss by incorporating a combination of token eviction scheme and dynamic token merging technique (where compensation mechanism is located).
4 D2O
Figure 3 provides an overview of D2O. For simplicity, each layer in the figure is depicted with single attention head. The dynamic layer-level and token-level discriminative operations proposed by D₂O are explained Section 4.1 and Section 4.2 respectively in details.
4.1 DYNAMIC LAYER-LEVEL DISCRIMINATIVE OPERATION
Employing a uniform layer- layer-wise wise size, such as those proposed in H₂O (Zhang et al. 2024c) and StreamingL (Xiao et al., 2023b), across layers could potentially compromise model perfor- mance. To address this, we propose using specific metric, Ft, to evaluate the attention density of each layer I:
Lapong
Fd Var
Σ A5 1=0
A/ = Softmax (OEK)) /VD)
where A denotes the attention score of prompt encoding in each layer, and Q K/ E R.. > We sum the elements of each column in A to establish the initial state of the cumulative attention sequence. The attention density for each layer is then quantified by the variance of this sequence, denser attention weights correspond to smaller variances. This relationship is illustrated in Figure 4 We observe consistent phenomenon across models on the GSM8K dataset: the variance of attention scores is lower in the shallow layers (e.g., 0, 1, 2) and middle layers (e.g., 13. 14), indicating that the attention weights are dense, as also shown in Figure I This density makes it difficult to distinguish which tokens should be discarded. In deeper layers, the variance increases and the attention weights display a sparser pattern.
800
Llama 78
700
Llama2
Score Variance
600
Llama
500
400
300
200
100
0
10
15
20
25
30
Layer
Figure 4: Variances attention score across different layers for various models.
Dynamic Allocation Strategy. Leveraging this consisteney, we propose
dynamic allocation
strategy using inverse variance softmax to adjust the KV cache size each layer: layers with higher variance Ft are allocated smaller cache size, while shallower layers with lower variance receive larger cache allocation. Specifically, for given compression ratio the cache size for each layer Sj, calculated as:
exp(-F!) L.P. p.
S = 0i where Σ exp(-F!)
(5)
where P represents the compression ratio of the cache size, and S is the original cache size, which is equal Lprempt in the prompt encoding stage. and L denotes the number of model layers. We adopt a softmax-like function to dynamically distribute cache proportions aq The derivation details and theoretical analysis can be found in Appendix and Appendix A.9 respectively.
4

---

Published as a conference paper at ICLR 2025
4.2 DYNAMIC TOKEN-LEVER LEVEL DISCRIMINATIVE OPERATION
After the layer-level discriminative operation, to compensate for the loss of long-context information, introduce critical strategies in the token-level discriminative operation: token eviction and dynamic token merging strategies. Specifically, while D2O is compatible with any token eviction technique, we propose an eviction strategy based on accumulative attention (Zhang al., 2024c) to dynamically prune KV cache in generation tasks. For token merging, we introduce a new strategy that utilizes a similarity threshold based on exponential moving average (EMA) to dynamically determine whether to merge discarded tokens back into the preserved KV cache through weighted merging.
4.2.1 TOKEN EVICTION
The core concept of token eviction involves dynamically updating the KV cache by leveraging cumulative attention scores. This process systematically excludes the least essential KV pairs to maintain the compressed cache size S; for each layer, thereby preserving only the most valuable tokens for efficient inference. A recent study (Xiao et al., 2023b) suggests that retaining crucial attention sink tokens within the most recent KV cache window enhances the stability of attention score distributions across extended texts. Unlike traditional accumulation- bassd approaches such as H₂O (Zhang al. 2024c), our strategy improves performance by maintaining attention sink tokens from the initial 7 tokens of the input and integrating them within a recent window of size M. The attention score is formulated follows:
Eepeaupe Ei=o
[.] q. (q.KT/VD)
if token i <= Irponpt otherwise, token generation
AttnScore
(6)
Softmax
/VD)
Laann :p
After obtaining the current cumulative attention scores, we retain the most recent window of size M and include 7 attention sink tokens. We then select the top N tokens with the highest scores from the remaining KV cache to finalize the eviction process. The procedure is defined as follows:
K. [[| TT:). K[ : K[ I] V== T. VI. V[- :.:
(7)
and I Top (AttnScore(TT MM,.
(8)
where x (,, N) selects the top N important tokens with indices / in AttnScore, (K., Va repre- sents the preserved KV cache after eviction, and S = T + N M denotes the current cache size.
4.2.2 DYNAMIC TOKEN MERGING
Directly discarding the eviction tokens context. To mitigate information loss, we propose dynamic token merging approach that retrieves tokens still containing potential value at minimal computational cost and integrates these selected tokens with similar reserved tokens. Considering the alignment properties of KV pairs, we compute the similarity matrix only on the key tokens and share both the similarity metric and weighted merging weights with the value tokens. We outline this approach in three key steps: nearest-neighbor matching, EMA threshold judgment, and weighted merging.
may compromise the integrity of the long
Nearest Neighbor Matching. We utilize many-to-one nearest-neighbor matching algorithm (Dang et al. 2021) to compute the similarity matrix U between K, and K.. We then identify the most similar tokens from K2 as candidates for merging. Specifically, let 1 and 1e denote the indices, and L and I represent the lengths of tokens in K. and K2, respectively. Each element ua in U represents the interaction between tokens for matching, where E and j E Io, We then determine the closest token knerrest in K, for each evicted token k, The formulas are as follows:
k, k k
nearest
Argmax (ua,), where u.jj jer=
|
Here, we adopt cosine similarity, where || denotes the norm. Since the similarity matrix U E I.''xx x is derived directly from input prompts and E R during token generation, it introduces no additional parameters and ensures computational efficiency.
5

---

Published as a conference paper at ICLR 2025
EMA Threshold. After calculating similarities and identifying candidate tokens K, K.earest directly applying average weighted fusion to token pairs could lead to feature dispersion (Liang et al., (022). Additionally, as depicted in Figure [I attention patterss in higher layers exhibit staircase- like structure, indicating a focus on local window information. Moreover, since only a few critical tokens exist outside these local windows, indiscriminately merging all candidate tokens introduce redundant information or noise, ultimately affecting inference accuracy. Inspired by the exponential moving average (EMA) (Hunter 1986 Busbridge et al. 2023) used in time-series tasks-which prioritizes more recent data and enhances sensitivity to data changes -we propose an EMA threshold for token-level operations. Our approach emphasizes the importance of recent similarity between current evicted tokens and preserved tokens while smoothing historical similarity information between previously evicted and preserved tokens. Specifically, the influence of past token similarity thresholds diminishes exponentially over time, assigning greater weight to more recent thresholds. The EMA threshold is formulated as:
E 2 Max (U.(i,))) MMMx + (1-3) T--1 T--1 otherwise, > 0 for token generation, U, E IR
if fft= = 0 for prompt encoding <= Teprompt U, E RL
7
(10)
The initial threshold is set the average of the highest similarity values between evicted tokens and the conserved set, as computed from the similarity matrix U, at each forward step t. The smoothing constant 3 regulates the balance between the current similarity matrix U, and the previous similarity threshold Tz-1, with higher values of 3 increasing sensitivity to changes in current similarity. If the maximum similarity of a given evicted token is lower than Tj. it is permanently discarded. Otherwise, a weighted merging strategy is applied.
Weighted Merging. Lastly, for a conserved token, evicted tokens with higher similarity should be assigned greater weights. Therefore, we use weighted merging instead of averaged merging, this approach mitigates potential errors arising from imperfect token scoring. The weighted merging formulas are defined as:
kej Werker + Σ Warke Vej Woreey + Σ Waiees
(11)
K.rEK.
VoV...
where w, and w. represent the weights assigned to each preserved and evicted key-value pair, respectively. We adopt a similarity-based weighting strategy, inspired by Graph Attention Networks (GAT) (Veličković et al. 2017). The weight calculation is as follows:
Exnck,
Woj Σk.ek. exp(u:y m. +
Wei Ex.ek, exp(u.) mij +
(12)
where maj E M represents the mask matrix of U. xf K. is the most similar token to x; E K.. then m:j = 1; otherwise, m,, = 0. The fusion weights Wej and wes are determined by the mask values m.jj and similarities u, Specifically, Wes represents the weight for each evicted token kes, while Wey corresponds to the weight of the preserved token itself. Each conserved token k-j retains the highest fusion weight, as its self-similarity equals one. Therefore, preserved tokens remain unchanged, as the most similar tokens are not modified, whereas evicted tokens are integrated into their most similar counterparts, replacing the originals.
5 EXPERIMENTS AND ANALYSIS
5.1 EXPERIMENTAL SETUP
Models. We evaluate D2O using four models: Llama-2 (Touvron et al. 2023 Llama-3 (Meta 2024 Falcon (Almazrouei et al. 2023), and Mistral (Jiang et 2023). For 1lama-2, we employ model sizes ranging from 7B to 13B. For Llama-3, we use the 8B model. Notably, both Llama-2 and Mistral utilize multi-head attention, whereas Falcon employs multi-query attention (Shazeer) 2019), , and Llama-3 adopts grouped-query attention (Ainslie et al. 2023). We implement D₂O using the Hugging Face Transformers codebase (Wolf et al. 2019).
Tasks. We evaluate D₂O using datasets with both standard and extended context lengths. For standard contexts, we utilize generation tasks from LM-Eval (Gao et al.) (202I), assessing model per- formance across commonsense and math reasoning on CoQA (Exact Match (EM) Accuracy) (Reddy

---

Published as a conference paper at ICLR 2025
Cache
Secuningux
Liam-a
CoQA Liama: 2:78
CoQA Liama-2-138
CoQA Lama:3388
55-
50
10% 87% 100%
100%
62%
10%
100%
Suiget
Sudpet
Budget
Sudget
GSMBK Liama-700
GSMBK Liama-2-70
GSMBK Liama Lbmm-2-130
GSMBK Uame-3300
14-
12
30
20-
10
20%
4255
50%
55%
100%
20%
42%
60%
50%
102%
27%
40%
65%
50%
100%
20%
40%
50%
85%
100%
Carthe Sasgett
Carhe Sudpet
RY Carte Budget
Carhe Basget
ACC
32
25
33
22
2056
4295
50%
90%
100%
20%
40%
60%
50%
102%
20%
40%
92%
50%
100%
20%
40%
60%
92%
100%
007
Cachee Budget
KV Ceche Sudpet
K2/
Cache Budget
V0V Cachee Subget
Figure 5: Performance of D₂O and other methods LLama backbones on reasoning datasets including CoQA, GSM8K, and TruthfulQA.
et al. 2019), TruthfulQA (BLEU score) (Lin et al. 2022). and GSM8K (Fxact Match (EM) Accu- racy) Cobbe al. (202Tb). For long-context tasks, we apply LongBench (Bai et al. 2023), which particularly suited for evaluating the effects of compressed KV cache. This involves tasks from subgroups such as Single-Document QA. Multi Dilti-DDecumntt QA, Summarization, Synthetic, and Code Completion. Additionally, Haystack test (Briakou et al. 2023). challenging the model to retrieve a specific sentence within a large document. We also validate our method's long sequence modeling ability using PG-19 (Rae et al. 2019). More details are illustrated in Appendix A.I
assess DzO's capabilityy in long-context retrieval with the Needle-in-at
Implementation. In principal experiment, select the 3 value for EMA threshold merging from the range 0.5 ~ 0.9. The hyperparameter experiment in Appendix A.3 shows that 8 = 0.7 achieves optimal performance. Additionally, the number of top N important tokens and the recent token M are typically set as N = 3 1, with N M T ag S. The overall KV cache compression ratio p varies across different settings, including values such as 0.2, 0.4, and 0.8. All experiments were conducted on NVIDIA A100 80GB GPUs. Further details on implementation and the determination of hyperparameters are provided in Appendix A.I and Appendix A.3 respectively.
5.2 COMPARATIVE ANALYSIS UNDER DIFFERENT KV CACHE COMPRESSION RATIOS
In Figure 5 benchmark DyO GSM8K. CoQA, and TruthfulQA datasets. We compare models equipped with full KV cache against those utilizing our D2O compression technique over several Llama models: Llama-1-7B, Llama-2-7B. Llama-2-133 and the latest Llama-3-8B. The ratio represents the proportion of the overall compressed KV cache budget relative to the prompt length Lppompe- Results indicate that D,O consistently outperforms all other KV compression methods across all configurations. Notably, D,O significantly enhances performance, particularly under reduced budgets conditions. This performance highlights D,O's ability to retain erucial context, compensating for the severe loss of information inherent in eviction-basee methods and preventing the degradation of LLMS' reasoning capabilities, particularly for Llama-3-8B on the GSM8K and CoQA datasets. Intriguingly, on the TruthfulQA dataset, DzO even surpasses the full KV cache model across four Llama backbone settings and most of the budget ratios, demonstrating that D,O's unified eviction and dynamic merging strategies can prune irrelevant tokens from LLMs' input text, preserving essential context and then enhancing reasoning accuracy.
7

---

Published as a conference paper at ICLR 2025
Table 1: Performance evaluation D2O on various models LongBench benchmarks. For each baseline. except for the full model, we retain 20% of Lpromg (p 0.2, S = Lipoops)) as the preserved KV cache size and highlight the best method.
Single-Docunnn Diccmment
QA
Multi- Nutti-DeeummttOo Q4
Summarication
Summarization
Synthetic
Codee
Methods
NevQA
Queer
MlF-a
2WiLMMA
Musiqu
GevRoppn
QM5um
MuloNeww
TREE
SAMSum
PCunnt
PRS
V,66
RB--
Full Modell
1.03
3.82
7.62
1.75
1.78
1.25
3.77
2.48
6.04
5.00
5.27
2.75
0.49
0.41
9.98
7,33
Balee-71
Local Window
2,50
4.50
1.26
1.31
1.79
0.61
2.31
4.67
7.25
SteaningLLMM
0.32
2:51
4.55
1.36
1.04
0.54
1,80
0.53
4.54
4.67
6.53
1.68
1.601
0.36
9.67
7.16
Hg0
4.01
5:65
1.66
1.70
0.50
2.61
0.61
4.36
4.33
0.0
6.72
RoCo
0.38
3.82
5.33
1.31
1.61
0.38
2.25
0.53
3.88
4.35
7.42
1.88
0.49
0.22
9.78
6.75
CaM
0.58
3.50
5.77
1.79
1.65
0.65
2.65
0.59
4.13
4.57
7.38
2.41
0.66
0.23
10.35
6.85
DyO
4.27
6.50
1.73
2,86
3001
3,32
4.75
5.32
7.33
Metral-788
Full Midel
76.28
79.8
49.4
41.77
26.53
19:35
24.46
26.28
65.67
16
41:11
4.43
90.5
56.91
49:00
Local Window
16.25
15.72
29.25
27.83
19:35
12,90
21.64
15.71
15.45
33.65
20.54
15.57
2.35
41.25
25.50
26.50
StraminnLLL
16.22
17.98
50.52
30.28
H,0
22.45
23.52
42.78
33.56
23.45
15.58
28.45
18.58
20.22
56.72
75.52
$1.88
3.45
78.55
52.88
93.25
RoCa
19:55
21:22
38.55
03.54
83
19.9%
13:58
25.22
15:32
16.85
52.45
76,23
30,50
75.58
09.54
53.75
CaM
03:40
42.54
$1.81
23.02
28.
18:09
10:82
56.25
75.28
31.62
78.70
16.85
DyO
24.54
25.72
45.07
34.84
24.92
17.29
29.70
21.90
24.06
62.99
$4.02
58,03
4.18
96.26
55.17
46.15
Ulma-2-71
Fall Midel
15002
8.92
31 1.39
9.13
10.2
3:71
19:45
21 77
1.42
61.00
89. RI
90/73
2.49
4.94
67.995
15:14
Locad Window
6.56
2.3
8.88
7.29
1.25
0.06
2.07
0.25
17.67
5.85
13.81
StromingLLM
10.31
5.62
19.78
5.65
8.75
2:49
1.29
19.3 06.56
1.32
$2.67
8% 96
57.13
0.59
6.10
64.76
50.49
820
7.15
20:45
R66
9.93
9.96
0.40
59.67
88.46
7.25
$3.40
RoCo
12.22
6.58
18:45
7.76
7.95
3.52
8.85
19.56
0.55
57.65
K5.54
36.14
2.55
4.84
61.99
50.55
CaM
11.31
6.34
18:05
K.06
8.44
3.91
9.35
19.40
1.46
$7.83
85.19
36.61
3.38
4.98
61.71
40.94
DyO
7.58
21.45
9.26
10.58
4.06
16.18
21.37
1.41
59.82
59.70
7.09
53,82
Full Model
12.91
9.37
19.65
11.19
10.84
5.59
19.39
21.37
4.74
63.35
$7.37
42.3
4.67
7.92
67.36
54.62
Local Window
3.77
5.17
2.78
13.83
11.76
3.95
0..14
1.48
0.32
17.67
7.54
3.65
0.67
3.89
15.44
13:64
StreamingLLM
5.70
11.62
14.06
10.20
4.51
2.25
17.91
0.39
52.00
85.25
37.64
5.00
46.34
15.52
6.53
15.10
10.74
10.74
5.28
12.13
20.48
0.29
60.33
85.73
42.23
3.25
9.52
64.99
51.31
RuCo
4.51
14.05
10.22
9.88
4.95
9:54
19.55
1.07
55.56
$4.78
6.02
51.95
CaM
11.17
5.59
13.98
10.64
10:72
4.81
9.80
20.59
2.01
$6.04
85.07
39.20
3.61
5.27
63.36
52.11
D,O
14,66
8,89
16.39
10.83
12.41
5.88
16.13
21.16
3.36
62.57
M5.15
42,75
6.87
9:83
67.19
52.81
Full Model
14:25
12:89
22.45
12:17
0.96
23:25
4.02
71.00
90,10
42.05
12.51
61.26
Local Window
1.8
4.54
4,10
5.11
6.91
2.81
0.56
10:35
0.02
33.5
25.67
10.55
5.69
2.00
33.80
21.85
Stroamingl IM
10.47
9.96
13:32
9.64
11.05
5.53
19.99
20.53
3.13
62.67
90:05
41.30
5.44
14.05
70:44
57.91
11.05
17.72
11.23
6:38
21.29
21:38
3.38
66.63
58.29
RoCh
10:77
10.58
16.54
9.98
8.95
9:52
20.78
20.15
2,80
63.98
86.26
$8.59
5:55
10.05
68.78
$6.65
CaM
11,02
16.34
10.47
8.85
9.45
21.23
20:75
2.57
66.10
67.21
38.69
10,40
59.51
DVO
14.33
12.66
19.93
11.92
12.79
9.88
24.86
23:42
3.95
69.72
90.99
42,36
6.61
14.67
72.43
60.00
5.3 ACCURACY COMPARISON ON LONG-CONTEXT TASKS
LongBench Results. We evaluate D on five models using LongBench, as shown in Table [ including Falcon-7B. Mistral- 7B, Llama-2-7BB Jlama-2-13B, and Llama-3-8B. To assess the performance of D2O and various baselines under high compres- sion conditions, we set the default KV cache budget ratio to demonstrates that D2O effectively manages KV cache compression with minimal impact on accuracy and successfully captures key information in lengthy texts com- pared the full model. In particular, the local window method suffers from severe performance degradation due to significant context loss. Furthermore, we compare D2O with other recent eviction- based baselines to further demonstrate its capability to retain key information. The results show that D20 significantly outperforms other eviction- based methods, such as StreamingLLM (Xiao) et al. 2023a). O (Zhang et al. 2024c), RoCo (Ren & Zhu| (024)), and CaM (Zhang et al.), es- pecially ly on the Llama-3-88 backbone. In addition to the experiments involving 7B, 8B, and 13B models presented in Table [ conducted additional experiments with the Code-Llama-34p model, experimeeeeeeeee
Table 2: LongBench code perfor-
mance on 34B model.
Code-LLama-34B
Lec
RB-P
Full
75.52
65.46
= 0.2. Table I
Local
37.38
21.49
StreamLLM
63.42
55.27
H₂O
68.85
61.02
RoCo
67.21
59.21
CaM
69.21
58.71
D2O
75.28
64.77
as shown in Table 2 We evaluated the 34B model on the LongBench code task type. The results indicate that O outperforms other evietion-based baselines and closely matches the performance of the full KV cache model. This demonstrates that D2O effectively generalizes to larger LLM scales, validating its scalability and robustness across different model sizes.
Long-Conters Fact Retrieval Task. To validate D2O's retrieval capabilities in long contexts after compressing the KV cache, we employ the Needle In Haystack task (Kamradi 2023). designed to retrieve specific "needles" from extensive documents. We adopt the evaluation set- tings from the Retrieval Head study, using Llama-2-7B-8 as the backbone of the experiment.
8

---

Published as a conference paper at ICLR 2025
Table 3: Needle-in a- results.
For fair comparison, the KV cache budget was set to 4096 and 8192, and both D,O and the baseline models were tested on contexts with maximum lengths of 50k and 100k. The average accuracy is reported in Table 3 D20 not only outperforms other eviction-based based methods but also exhibits the smallest drop in performance accuracy when compared to the full model even without the assistance of well-designed re- triever, especially when the cache budget is 8192.
Methods
I=50k
1==10k
I=50k
T==00k
Full Model
97.88
94.46
97.88
94.46
4096
8192
LLreamingL.MM
58.64
47.93
62.84
51.34
H₂O
79.84
69.81
82.32
72.34
SnapKV
83.55
76.22
86.63
80.42
CaM
82.66
78.22
87.59
78.88
D,O
91.27
87.74
94.48
91.88
These results underscore D2O's robust long-context retrieval capabilities, even with a compressed KV cache.
LogpPI, Llama-3-85
Long Sequence Modeling Perplexity. We sample data from PG-19 (Rae et al. 2019) to evaluate long-sequence language modeling perplexity. To ensure a fair compari- son, set the KV cache capacity to 2048. Figure 6 de- picts the cumulative average negative log- likelihood (NLL) function of context length. D20 enables LLMS pro- cess long sequences more effectively, achieving superior performance (lower perplexity) compared other eviction- based compression methods. These results demonstrate that O can effectively leverage long-distance depen- dencies in language modeling, even with a limited KV cache.
2.3
2.2
1.6
StreamingLLM
2.1
2.0
50000
6000p
1.9
1.0
1.7
0k
8k
16k
24k
32k
40k
48k
56k
65k
Length
Figure 6: Long sequence modeling PPL.
Table 4: Comparison of cache allocation strategies.
5.4 DYNAMIC ALLOCATION POLICY ANALYSIS
Method
CoQA
TREC
To evaluate the impact of our proposed dynamic allocation policy at the layer level, we conduct an experiment comparing various designs for the cache allocation factor at, where each design influences how the cache is distributed across layers based their attention variance F.. We consider several settings: (1) Inverse Variance
Exponential Decay
48.26
57.46
Uniform Allocation
55.30
65.10
Reciprocal of Variance
58.10
68.00
Inverse Variance Softmax (Ours)
59.25
69.72
exp(- F.)
Softmax (Ours): ag = EE exp(-FF) F.) L. p. which allocates smaller cache sizes to layers with higher
L. where the cache allocation is inversely variance; (2) Reciprocal of Variance: 0q E FT.
proportional to the attention variance; (3) Exponential Decay Allocation: ot e where cache allocated in an exponentially decreasing manner based on the variance. (4) Uniform Allocation: a p. where all layers assigned equal cache sizes. As shown in Table the comparison of these settings demonstrates the effectiveness of our proposed approach in efficiently distributing cache based on variance, leading superior performance in key metrics.
5.5 THROUGHPUT ANALYSIS
Table 5: Throughput comparison of full model and D20. 32 (256) means the max hatch size is 32 with 256 cache budget
We demonstrate that reducing the KV cache with D₂O significantly en- hances real-world throughput, as illus- trated in Table All experiments are conducted using the Llama-3-8B ar- chitecture on an A100-80G GPU with- out CPU offloading. The KV cache budget is set equal to the length of the prompts to maintain the contextual in- tegrity of the input prompts. We observe that D2O reduces memory usage, enabling larger batch sizes and higher throughput. Specifically, text length increases, DzO's throughput advantage over the full model also grows. For example, throughput improves from 2.34x x at the 256+1024 setting to 3.04x at the 2048+8192 setting, demonstrating D,O''s efficiency in processing longer texts. Moreover, the table above also shows that our method achieves throughput comparable to H₂O for long sequence inference, with throughput 3.0-3.1 times that of the Full Model. This validates the GPU memory
Prompt+Gen
256+1024
512-2048
10244-096
2048+8192
Max Batch Size
Full Model H2O
8 32 (256)
16 (512)
(1024)
(204))
D,O
32 (256)
16 (512)
(1024)
4 (2048)
Throughpot: tokens
Full Model
374.79
198.94
96.95
43.44
H&O
919.77 (2.45x)
511.75 (2.57x)
281.36 (2,90x)
134.66 (3.10x)
D&O
878.62 (2.34x)
495.50 (2.49k)
272.28 (2.80x)
132.45 (3.04x)

---

Published as a conference paper at ICLR 2025
efficiency of our merging strategy in increasing throughput compared the full cache size. While merging strategy incurs some computational overhead compared to HzO's s eviction- based strategy, the benefits are clear in long text generation and inference tasks. As demonstrated in Table (Longbench Results) and Appendix A. (Multi-turn Conversations) in the main text, D2O significantly reduces information loss due eviction, enhancing inference accuracy. Furthermore, additional details computational cost analysis are provided in Appendix A.5
5.6 ABLATION ANALYSIS
In this section, conduct series of experiments to investigate the importance of each component and parameter setting in our proposed method. Unless otherwise specified, Llama-3-8B is used as the default model under the cache budget 20%.
Ablation Study of Each Component. To
Table 6: Performance of each component.
demonstrate the effectiveness of each compo- nent, we have included a table comparing the Full Model, H2O, D2O, and its key compo- nents in Table 6 We evaluated these mod- els on four datasets from Longbench: Single- Document QA (MF-en), (2WikiMQA). Summarization (GovReport), and Synthetic (PRe). As shown in the following table, the removal of any component of D2O results in performance degradation. When two components are removed (leaving only the weighted merging), the performance loss is even greater, but still better than the H2O method, which is purely eviction- based. These results demonstrate that each component of D2O effectively mitigates the information loss associated with eviction-basee KV optimization.
MF-en
2WikiMQA
GovReport
Full Model
22.45
12.17
30.8
12.51
11.25
D,O
19.93
12.79
24.36
14.67
Layer Operation
18.89
11.67
22.45
13.44
wao EMA-Theshold
19.23
11.88
22,85
13.23
QA
W.o. Both
17.85
11.58
21.87
11.98
Table 7: Feature choice.
Table Performance comparison with different merge policy.
Table 9: Ratio impact.
Feature
CoQA
TREC
Methods
CoQA
TREC
Methods
CoQA
TREC
K
59.25
69.72
1:1
56.52
66.45
V
53.88
64.34
Average
56.58
67.12
1:3
55.43
65.41
KN
53.54
62.76
Weighted average
59.25
69.72
3:1
59.25
69.72
Token Similarity Metric. We examine various choices for token similarity metrics based keys, values, or both, to determine which tokens should be merged. As shown in Table attention keys (KC) exhibit significantly higher performance than attention values ())). We also observe a notable decrease in performance when using independent metrics for the key-value (AC/V) cache, which we attribute to the disruption the corresponding relationships between key-value pairs within the cache.
Merge Policy. After determining which tokens to merge, we explore the merging policy in our pro- posed method. Specifically, we compare the performance of average merging and weighted merging. The results in Table & indicate that the weighted merging policy achieves superior performance.
Balaneing Important Token Size (N) and Recent Size (M). We also investigate the impact of different important token sizes and recent size ratios on performance, given fixed budget. This ratio determines the emphasis placed on influential tokens from historical contexts (larger ratio) versus tokens from recent contexts (smaller ratio). The results in Table 9 suggest that important tokens reflecting global information have a greater impact on performance.
CONCLUSION
In this paper, we propose Dynamic Discriminative Operations (D:0) that can effectively address the challenges of KV cache management in LLMs by dynamically merging tokens to maintain essential contextual information without requiring fine-tuning. By leveraging the varying densities of attention features across layers, D₂O minimizes information loss during eviction and significantly reduces both computational and memory demands. Our experiments confirm that D2O not only preserves the quality of generation in long-text scenarios but also achieves optimal balance between KV- cache compression and performance. Future research could explore integrating D,O with additional compression methods like quantization, distillation, and efficient attention architectures.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, 1lge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et Gpt-4 technical report. arXiv preprint (tt.::30330087744 2023.
Joshua Ainslie, James I Lee-Thorp. Thorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. arXiv preprint arXiv:2305.1322// 2023.
Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojo- caru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, et al. The falcon series of open language models. arXiv preprint arXiv:2311.16667, 2023.
Robert B Ash. Information theory. Courier Corporation, 2012.
Ge Bai, Jie Liu, Xingyuan Bu, Yancheng He, Jiaheng Liu, Zhanhui Zhou, Zhuoran Lin, Wenbo Su, Tiezheng Ge. Bo Zheng, and Wanli Ouyang. Mt-bench-101: fine-grained benchmark for evaluating large language models in multi multi-turrn dialogues. CoRR, (bs/2400..1472,, 2024.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: bilingual, multitask benchmark for long context understanding. arXiv preprint urXiv:2308. 14508, 2023.
Daniel Bolya, Cheng- Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman. Token merging: Your vit but faster. arXiv preprint arXiv:2210.094611, 2022.
Eleftheria Briakou, Colin Cherry, and George Foster. Searching for needles in a haystack: On the role of incidental bilingualism in palm's 's translation capability. arXiv preprint arXiv:2305./0260 2023.
Dan Busbridge, Jason Ramapuram, Pierre Ablin, Tatiana Likhomanenko, Eeshan Gunesh Dhekane, Xavier Suau Cuadros, and Russell Webb. How to scale your EMA. In NeurlPS, 2023.
Ruisi Cai, Yuandong Tian, Zhangyang Wang, and Beidi Chen. Lococo: Dropping in convolutions for long context compression. arXiv preprint urXiv:2406.053// 05317, 2024a.
Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. arXiv preprint arXiv:2406.0206 2024b.
Yilong Chen, Guoxia Wang, Junyuan Shang. Shiyao Cui, Zhenyu Zhang, Tingwen Liu, Shuohuan Wang, Yu Sun, Dianhai Yu, and Hua Wu. Nacl: A general and effective kv cache eviction framework for llms at inference time. arXiv preprint arXiv:2408.0338 03675, 2024.
Wei-L.in Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wa, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. Vieuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, march 2023. URL https://lmsys. 1tg/blog2023300333-vvccmm (5), 2023.
Karl Cobbe, Vincet Kosaraju, Mohammad Bavarian, Mark Chen, Hcewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. CoRR, abs/2110. 14168, 2021a.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reñcchrr Nakano, al. Training verifiers solve math word problems. arXiv preprint arXiv:2110. 1414666,,,, 2021b.
Zhiyuan Dang, Cheng Deng, Xu Yang, Kun Wei, and Heng Huang. Nearest neighbor matching for deep clustering. In Proceedings of the IEFE/CVE conference on computer vision and pattern recognition, pp. 13693-13702, 2021.
Harry Dong, Xinyu Yang, Zhenyu Zhang, Zhangyang Wang, Yuejie Chi, and Beidi Chen. Get more with less: Synthesizing recurrence with kv cache compression for efficient Ilm inference. arXiv preprint arXiv:2402.09399 09398 2024.
11

---

Published as a conference paper at ICLR 2025
Leo Gao, Jonathan Tow, Stella Biderman. Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Kyle McDonell, Niklas Muennighoff, et al. framework for few-shot language model evaluation. Version vO. 0.1. Sept, pp. 8. 2021.
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.01800 (0000,0801,00 2023.
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 arXiv:2404.06644 2024.
Stuart Hunter. The exponentially weighted moving average. Journal of Quality Technology. 18: 203-210, 1986. 1tgp://_nno.nnu.iiirrrr/p/.ee.e.
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:2310.0682) 2023.
Ehsan Kamalloo, Nouha Dziri, Charles LA Clarke, and Davood Rafeii. Evaluating open-domain question answering the era of large language models. arXiv preprint arXivv2305.06984 2023.
G Kamradt. Needle in haystack-pressure testing llms, 2023.
Yuhong Li, Yinghing Huang, Bowen Yang, Bharat Venkitesh, Acyr F. Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before gener- ation. 2024. URL httt:::s::// / www.:esssseattnccccc.oeoeeeoeaee
owg/Corpus ID: 269303316
Youwei Liang Chongjian Ge, Zhan Tong, Yibing Song, Juc Wang, and Pengtao Xic. Not all patches are what you need: Expediting vision transformers via token reorganizations. ArXiv, abs/2202.07800, 2022. 246867285
Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. In ACL (I), pp. 3214-3252. Association for Computational Linguistics, 2022.
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for LLM KV cache compression at time. In NeurlPS, 2023.
Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu, Kivi: A tuning-free asymmetric 2bit quantization for kv cache. arXiv preprint arXiv:2402.02750. 2024.
Meta. Introducing meta Ilama 3: The most capable openly available Ilm to date, 2024. URL https://ai. meta. com/ blog/ meta-llama-aaa
Piotr Nawrot, Adrian Lańcucki, Marein Chochowski, David Tarjan, and Edoardo M Ponti. Dynamic memory compression: Retrofitting llms for accelerated inference. arXiv preprint 06X.v22403.09636, 2024.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: fast, extensible toolkit for sequence modeling. arXiv preprint arXiv:1904.01038 2019.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap. Compressive transformers for longerange sequence modelling, arXiv preprint arX1v:1911.05507, 2019.
Siva Reddy, Danqi Chen, and Christopher D. Manning. Coqa: A conversational question answering challenge. Trans. Assoc. Comput. Linguistics, 7:249-266 2019.
Siyu Ren and Kenny Q Zhu. On the efficacy of eviction policy for key-value constrained generative language model inference. CoRR, abs/2402.06262,, 2024.
12

---

Published as a conference paper at ICLR 2025
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. Code llama: Open foundation models for code. arXiv preprint arXh::2388 2023.
Noam Shazeer. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:191 1911,09 2019.
Dachuan Shi, Chaofan Tao, Anyi Rao, Zhendong Yang, Chun Yuan, and Jiaqi Wang. Crossget: Cross-guided ensemble of tokens for accelerating vision-language transformers. arXiv preprint 1rX11:2305.17455 2023.
Alan Jay Smith. Cache memories. ACM Computing Surveys (CSUR), 14(3):473-533 1982.
MTCAJ Thomas and Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307. 092888, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1rXiv:1710.10900 2017.
Zhongwei Wan, Xin Wang, Che Liu, Samiul Alam, Yu Zheng. Zhongnan Qu, Shen Yan, Yi Zhu, Quanlu Zhang, Mosharaf Chowdhury, et al. Efficient large language models: A survey, arXiv preprint 23..:2332.008633 1, 2023.
Siyuan Wei, Tianzhu Ye, Shen Zhang, Yao Tang, and Jiajun Liang. Joint token pruning and squeezing towards more aggressive compression of vision transformers. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2092-2101, 2023.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's transformers: State-of-the-art natural language processing. arXiv preprint arXiv:1910.037711 2019.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Transformers: State-of-the-ard natural language processing. In Proceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations, pp. 38 45, 2020.
Xinjian Wu, Fanhu Zeng, Xiudong Wang, Yunhe Wang, and Xinghao Chen. Ppt: Token pruning and pooling for efficient vision transformers. arXiv preprint arXiv:2310.01812. 2023.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. CoRR, 10d//309..1445, 2023a.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309. 17453, 2023b.
Dongjie Yang, XiaoDong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. Pyramidinfer: Pyramid kv cache compression for high-throughput Ilm inference. arXiv preprint arXiv:2405. /2532, 2024a.
June Yong Yang, Byeongwook Kim, Jeongin Bac, Beomseok Kwon, Gunho Park, Eunho Yang, Se Jung Kwon, and Dongsoo Lee. No token left behind: Reliable KV cache compression via importance-awarn mixed precision quantization. CoRR, Abs/2402.18096 2024b.
Yao Yao. Zuchao Li, and Hai Zhao. Sirllm: Streaming infinite retentive 1lm. arXiv preprint arXiv:2405. 12528. 2024.
Tianyi Zhang, Faisal Ladhak, Esin Durmus, Percy Liang, Kathleen R. McKeown, and Tatsunori B. Hashimoto. Benchmarking large language models for news summarization. CoRR, abs/2301.13848, 2023.
13

---

Published as a conference paper at ICLR 2025
Xinrong Zhang, Yingfa Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Hao, Xu Han, Zhen Thai, Shuo Wang, Zhiyuan Liu, et al. Extending long context evaluation beyond 100k tokens. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume
I: Long Papers), pp. 15262-15277, 2024a.
Yu Zhang, Yepeng Liu, Duoqian Miao, Qi Zhang, Yiwei Shi, and Liang Hu. Mg-vit: A multi- granularity method for compact and efficient vision transformers. Advances in Neural Information Processing Systems, 36, 2024b.
Yuxin Zhang, Yuxuan Du, Gen Luo, Yunshan Zhong, Zhenyu Zhang, Shiwei Liu, and Rongrong Ji. Cam: Cache merging for memory-efficient Ilms inference. Forty-furst International Conference Machine Learning.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024c.
Haiyan Zhao, Hanjie Chen, Fan Yang, Ninghao Liu, Huiqi Deng, Hengyi Cai, Shuaiqiang Wang, Dawei Yin, and Mengman Du. Explainability for large language models: A survey. ACM Transactions Intelligent Systems and Technology, 15(2):1-38, 2024a.
Haiyan Zhao, Fan Yang. Bo Shen, Himabindu Lakkaraju, and Mengnan Du. Towards uncovering how large language model works: An explainability perspective. 2024b. URL https://api
semanticscooles ott.://o......ooooooooraaaa//0a.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging lud- with mt-bench and chatbot arena. Advances Neural Information Processing Systems, 36, 2024.
14

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 MORE SETTING DETAILS
In all our experiments, used model weights downloaded from Huggingface follows: for all Llama architectures, the Llama-1-7B model employed the 'huggylaama/lama-71 checkpoinc Llama-2-7B used the -at--laammaaaaa--------ff versionn L.lama-2-13B utilized metta-lama/Lllmma- In the Mistral
2- 2-13b-hf and for the latest Llama-3-8B, we used architecture, the 'mistrala/MMistral-BBBnsss -B-nst-ttt-tt checkpoint was employed. For Falcon architecture, 'tiuae/faalco-775 (
was used. Additionally, for the evaluation metrics of the various sub-tasks such as "narrativeqa. "qasper," "multifielqq, en, and "hotpotqa" within the LongBench benchmark, please refer to the official benchmark repository!
A.2 DERIVATION OF CACHE ALLOCATION FACTOR OI)
In this section, we provide the derivation for the cache allocation factor og, which dynamically adjusts the KV cache size based on the variance of attention scores in each layer.
We begin by noting that the total cache size across all layers is constrained by the original fixed cache size for each layer and the compression ratio p. The total cache size after compression is given by:
Σ 1=1
S.S.L.
(13)
where is the cache size allocated to layer I, L is the total number of layers, and p represents the compression ratio. To allocate cache dynamically, we introduce which governs the proportion of the total cache assigned to each layer. The cache size for layer I is therefore:
S S
(14)
and aj must satisfy the constraint:
Σ 1=1
ai = L L.p
(15)
To ensure layers with higher variance F. receive smaller cache sizes, we propose an inverse rela- tionship between ag and EN A softmax-like function is adopted to distribute cache proportions as follows:
exp(
0: ΣL cxP L.P
(16)
This formulation ensures that layers with higher attention variance are allocated less cache, while those with lower variance receive more. The normalization factor Σ exp(-PP) guarantees that the total allocation across all layers satisfies EL= L.p. Thus, the above formulas concludes the derivation the dynamic cache allocation factor, where on is inversely proportional the attention variance of each layer.
A.3 MORE DETAILS OF HYPER-PARAMENS PARAMETERS DETERMINATION
Our hyper-parameters are designed to be both generalizable and robust across all tasks in the paper. We select hyper-parameters by first conducting parammer searches on specific long-text datasets from Longbench (e.g., TREC) and reasoning datasets from LM-Eval (c.g., COQA), as detailed in Section 5.6 (Ablation Study) of our paper. We then the best-performing parameters for global
https://huggingfacc.co/ugggg co/.uggyllama//laaaaa-aa
"ntpss//hugggngffacccoooeee wwtp://we..o.//aeeeeeeeeeee Lamaa/laam-22
"hcrss//hugggnngffcc.oo// wwtmetaa- co/meta-llammlLaanne
"batss//huggingffccccoomeee wwt.wtaacoa/////// Saatma/MMta-aalaa---
"https//hugginnffacc.o
hhtps://githubbb..
15

---

Published as a conference paper at ICLR 2025
experiments. For token-level hyper- paper-parameters such as 3, we conducted searches within the range of 0.5-0.9 (0.5, 0.6, 0.7, 0.8, 0.9}. For (important tokens) and M (recent tokens), we tested ratios [3:1, 1:1, 1:2, 1:3].
In addition to the TREC and COQA datasets used in the main text, we have conducted additional hyper- parameter ablation studies the GSM8K (mathematical reasoning) and TruthfulQA (commonsense reasoning) datasets, as shown in Table [T] and [1] We found that the ratio of N:M =3:1 yielded the best performance across most datasets, stated in Section 5.1 of of our paper. For the EMA threshold parameter Beta, we observed that a value around 0.7 produced optimal results in most datasets, and we set the default Beta 0.7.
N:M
COQA
GSM8K
TruthfulQA
8
COQA
GSMSK
TruthfulQA
3:1
57.92
41.24
44.92
0.5
56.35
40.04
44.13
2:1
57.68
39.95
41.49
0.6
57.12
41.02
44,92
1:1
56.87
37.26
26.72
0.7
57.92
41.24
43.1
1:2
54.90
36.32
36.47
0.8
57.18
40.18
42.4
1:3
54.58
36.79
34.52
0.9
56.92
39.89
38.8
Table 10: N:M Comparison
Table 11: Beta Comparison
A.4
GENERATED SAMPLES OF MULTI-TURN CONVERSATIONS
To validate our D2O method's s ability to preserve critical context information and generate correct and fluent responses in multi-turn dialogues, we employed the MT-bench dataset (Zheng et al. 2024). This dataset consists of 3.3K expert-level pairwise human preferences for responses generated by six models, including GPT-4 and LLaMA-13B, in response to 80 multi-turn questions. It is specifically designed to assess the performance of language models in producing contextually appropriate conversations. To ensure a fair experimental comparison, we followed the settings (Xiao et al.) [2033]] Zhang et al., (024c) of using KV cache budget of 2048 tokens. For D₂O and HzO, we set the quantity of the top important tokens at 48 and recent tokens M at 2000.
Notably, due to the extremely long texts in streaming multi-turn dialogues, the full model will encounter out-of-memory issue. Therefore, we primarily compare D₂O with H₂O (Zhang et al. 2024c) and StreamingLLM (Xiao et al. 2023b). As illustrated in Figure g we randomly sample outputs according to the running order of the MT bench dialogue data, with samples I and appearing in the earlier dialogue data and samples 3 and 4 in the latter part. From the outputs, we observe that during the early stages of multi-turn conversations, both D2O and two other eviction-based KV cache compression methods effectively captured the context and yielded accurate responses. However, after the second sample, H2O and StreamingL_LMM start to produce irrelevant content, losing conversational coherence. This deterioration underscores a significant loss of contextual information and a decline in future generation performance, illustrating the drawbacks of methods that directly drop the middle KV cache, such as StreamingLLMM, or employ eviction strategies based on attention scores, like H Meanwhile, we observe that Full Cache encounters out-of-memory error when processing the third sample. It highlights the critical necessity of optimizing KV cache to retain complete contextual information during multi-turn dialogues with ultra-long texts. This experiment demonstrates the efficacy of our two-level discriminative operations for context retention.
A.5 COMPUTATIONAL COST ANALYSIS
To better understand the time overhead associated with prompt encoding and token generation after implementing token-level discriminative operations. we compared the time costs of prompt encoding to the total inference time. Our results, as illustrated in Table 12 show that the prompt encoding process, which utilizes token evietion and dynamic token merging operations, constitutes only a small fraction of the total time. Moreover, the length of generation tokens increases, this proportion continues to decrease to 0.224%, indicating that the token merging operation is both efficient and less time-consuming.
Additionally. we compare the computational overhead of our method (D20) with evietion-based method (H₂O) in Table [3] we observe that the inference time for D₂O is not significantly different from that of H₂O. This indicates that the token similarity calculation and the merging strategy are lightweight and do not affect the overall inference efficiency.
16

---

Published as a conference paper at ICLR 2025
Sample
Sample 2
USER Edit th following pangaagli to conrec asy grananniaa ancos She duart remeeber whene her porea, is stmbe the hets say kishes are
of Eiglish tnreberr todee with correriny should skodis insoiic &, and reaeanl sida seftaal and palided veniro ma koi is Englics Your objective is use elopere and apphericated experations, while proce sing original mecniigg Focus soidh on srprocenaaa My
USER Press
calancinn moellngg und languaae. Reuardlzo the lanauge
then oskel looking slath sey, "Whut" aeass, "Old foord ket
and,
ccreections 2088600057 AYP
Fall Cache
Full Cache
ASSISTANT: Yes, Siee (idi" rreeembor where hor pume was, sn flocealy was the cas it kachen tanke tteeah
Thes hearm siked Did you find
ASSISTANT: The test is Chisese Here the rofieel and polisted immbatic: anme theneer, bek losure sut rears nutious for cndare Dis logging searhoss
D2O
D20
ASSIS FANT You like dieek nemoreher whene
paree, thought
ASSISTANT: The peorided los is wee's requed is wiitee Chincws, Hov Explisk inmolttion leat "Clesace ane not snouah to casst snd's
caa, lut wark aad Slae uded in lelp ker find and suplicd with "Mtayhe ifi kitchen soblets Ste dran hor me and then he asted agais. TTi yoe
thei abdoniial discorffet. "aljiota progsoes discsmoon cosld "adpurs vangitaaze oeveral
OF counect Herz's the revised puraapapio with requested connctione She rihii rememberr whim hir purso wark on think it's the sir hir lila an iissa the kindaa table. bet lecs act sure Juad than thes saked asc to help Rid due esys. yeu'* And requant wath, "Mayhe, her I'm noe sire Li
E
abdoniical
"adtaats
X
sarglasest meeil,, deperalnn on the rndellyng cause "aljuss sunglesses" Its slmn penaiii that the saneet may expenence "acjeen sangleoe" incrrvemmnni in thei abdoniral discontoor, Tadjuts sanglasees degonding offectie
StreamingLIMM
StreamingI..MM
Sla-dsäri rensanber elaaz lan pare was se thangls was lae oas le saii on inchen shile saatt are. Thy acced
ASSSTANT Sam, 1hd happs to help! Horkk the cormated paragaahe
ASSES EANT Cattanly Engliss trandaase, will hage help rafor and erhonce your tee. The planee provited, "208 4-66 A6 RR: cas susokand to Beglish
and Lear
will respodall "Malho.lon lad surc!
"wiatt
"Te ball gradailly wideas nove bercarated, thesuke people puspleskkuss
Sample
Sample
Alps
agrccltue
USER: Doviile linckes piteipho evakaling seganane ando wiiting
Womars harope' Lat
Full Cache
Full Cache
Out Of Memory
Out Of Memory
D2O
procppi
ASSISTANT Alpu aas Milie Rival lave aad ripo bepuca antinneer and "gi
Cluite arpanazt shalddie dan and cup undemtand with cuch casty sardd aeppessily
fendowaps reflameed counc steers The likin Rinee has bocn merapomaanc goace and peopls desat deceeaarpar plam bine hoce agrice oprin Baregia
Bikonau la aquanes
adouant tapip davaty
Invlenee The erginee dould ho reperted by enitened red aotlideg ficts serteees and
5. Suuppay The aquaaee dloak cenained will od aqua auaa and will atte rafoorng theee pereoplcs you can cnhlate irpaneet defemmne whethers petcannc
H2O
ASSISTANT AA "adbari smpituer" patcea's pregrest evold alse to in ther ahke Gouundio faliel englowess in and saild peonod axdlusor" lo als thur the peicee may cpprrate tu aagilaec" intervenaai wengeet
11,0
polaed proposis?
Arymiii miring "aljes placeeee It's posaille pablet ecuciaze fad oug e
Siteenall sevvel polce''s and medernaal chowerisn renk pensi isacve
X
dusendet "adj siglisi What
Streaming
(INST)] [INST)s (ISST) (INST) in (NST] aa (INST) (INST] in
(INSTj (NST) in (INST]
X
StreamingLLM
ASSISTANT + a 99 0000000000000 00000000
Figure 7: Overall caption for the two images.
Figure 8: A comparative visualization of text generation by the DzO, H2O, StreamingLLMs. and Full Cache methods is presented, with samples to collected sequentially according to the multiple rounds of dialogue from the MT Bench dataset. All three methods were tested on the 2-b-hhh--- model. The correct responses have been highlighted.
17

---

Published as a conference paper at ICLR 2025
We also included additional experiments comparing latency across different model sizes, specifically Meta-Llama-33881 Llama-2-13B. Mode-Llama-34B, and 3aata-Llmm---70B under varying sequence lengths for encoding/prompt encoding. For these tests, used single A100 80G GPU for the 8B and 13B models, two GPUs for the 34B model, and four GPUs for the 70B model. As shown in the results in Table 14 inference time scales with both sequence length and model size, with larger models experiencing increased latency due to computational complexity and communication overhead, even with fixed-size KV cache optimization.
Furthermore, to assess inference time and generation quality during long-generation tasks, we conducted additional tests on the longbook sum eng dataset from InfiniteBench (Zhang al.) 2024a). which has an average output length of 1.1K tokens. Due to computational constraints, we tested the first 20 samples using the -Jama-3.1-8B-Insteee representative baselines, including the eviction-based method (H2O), layer-wise KV cache reduction (PyramidKV) V), and value token merge (CaM). The experiment was conducted using four A A100 GPUs with 80GB, As shown in Table 15 DzO achieved the best performance, with total inference time between HgO and PyramidKY and minimal latency differences.
(128K) model, comparing D2O with
For Table 16 of the Needle-in-a-haystack experiment, using four-A 100 80GB setup, our inference speed falls between SnapKV and CaM, while achieving the best performance among the methods.
Table 12: Inference time cost analysis of Llama 3-8B. The overall generation duration is calculated from the beginning of the decoding process the conclusion of the generation sequence. Prompt encoding time spans from the initial prompt input the completion of token eviction and dynamic token merging by DgO. The KV cache budget established at 256 tokens with a ratio of N set at 1:3.
Prompt Len Decoding Len
Overall Generation Duration (s)
Prompt Encoding Duration (8)
Decoding Time Per Token (s)
Prompt Encoding/Overall (%)
256+512 512+1024
29.454
0.235
0.057
0.798%
58.528
0.246
0.057
0.420%
1024+2048
121.191
0.328
0..559
0.271 (6:
2048+-1096
232.398
0.520
0.057
0,224%
Table 13: Computational overhcad comparison (Cache size 256, Reported by LLama 3-8B).
Prompt Len
Overall Generation Duration (6)
Prompt Encoding Duration (S)
Decoding Time Per Token (s)
Prompt Encoding/Overalll (%)
Decoding Len
H₂O
512+1024
52.253
0.214
0.051
0.410%
2048+4099
214.425
0.315
0.523
0.153%
DyO
512+1024
58.475
0.245 0.518
0.057
0.419% 0.223%
2048+4096
232.225
0.057
Table 14: Computational overhead analysis by model size and context length.
Overall Gemeration Duration (s)
Prompt Len + Decoding Len
34B
70B
256+512
29.454
53.02
147.27
279.81
512+1024
58.528
105.35
292.64
556.02
1024+2048
121.191
218.14
585.36
1151.31
2048+4006
232.398
418.32
998.79
2015.78
A.6 EXTENDED ANALYSIS OF LONGBENCH EXPERIMENT
This experiment mainly validate the capability of our D₂O to handle longer text data under low KV cache budget, we selected several representative tasks from the LongBench. including single-document QA (e.g., MultifieldQA), multi-document QA (such HotpotQA and 2wikimQA),
18

---

Published as a conference paper at ICLR 2025
Table 15: Lookbook sum eng 1.1-ma-..1-8B--- Instruutt / (20% KV Cache)
- 1-8-rrnstttctt (128K)
Rouge_ Lsum (fl)
Inference time (min)
Full
36.87
259.64
HgO
28.12
190.91
PyramidKV
31.92
206.06
CaM
33.82
181.51
D2O
35.48
201.27
Table 16: Needle in-- -n---ii------s- -aystaac results with inference time.
Methods
1==00k
1==00k
1.=50k
I=100k
Full Model
97.88 (93.6 min)
94.46 (175.4 min)
97.88 (93.6 min)
94.46 (175.4 min)
8192
StreamingLLM
58.64 53, 49 min
47.93 100.23 min
62.84 / 64.17 min
51.34/ 110.92 min
H₂O
79.84/ 69.33 min
69.81 125.93 min
82.32 82.32/75.11 75.117
72.34/ 138.88 min
SnapKV
83.55 78.00
76,22 146.17 min
86.63 86.82
80.42/ / 154.34 min
CaM
82.66 / 66.73 73 min
78.22 116.24 min
87.59 / 75.12 min
78.88 / 129.80 min
D₂O
91.27 71.53 87.74 129.85 min
94.48 79.37 min
91.88 142.22 min
summarization (GovReport, TREC, and SAMSum), and code completion (Lee RB-P). We specifically chose datasets exceeding 8k in length and only retained 20% KV cache budget. As shown in Table 17 D2O still demonstrates significant advantages even on datasets larger than 8k. Specifically, within the Llama-2-78 architecture, D2O outperforms the best baseline by 5.94 and 7.23 points in two summarization tasks, GovReport and TREC, respectively. This robustly validates the effectiveness of D2O's dynamic layer and token-level strategies, which effectively compress extended textual information under a low KV cache budget.
A.7 VISUALIZATION OF LONG CONTEXT FACT RETRIEVAL TASK
We visualized the Weedle-in-at -at-----ayttckk (Kmmradt 2023) test performance comparison of the full model, H2O, and our D2O method to show the effectiveness of our dynamic token merging strategy for long-context information retrieval. As illustrated in Figure 9 we observed that the eviction-based method H2O, which relics on attention scores to prune the KV cache, loses significant contextual information, especially when the retricval task reaches maximum length of 100k. In contrast, D2O method, which employs a dynamic token merging strategy, effectively preserves the information of evicted tokens and mitigates the impact of KV cache compression long-context retrieval.
A.8 VISUALIZATION ATTENTION WEIGHTS ACROSS VARIOUS DATASETS
In Figure 10 we visualize the attention weight results of the prompts across various layers of models such as Llama-1-27 1-7B and Llama-3-8B on reasoning datasets like GSM8K (Cobbe et al., (0211) and COQA (Reddy et al. 2019). Consistent with the observations noted in Section of the main text, similar pattern exists across different models and datasets, wherein the lower layers of the models exhibit higher density than the higher layers. Thus, this strongly corroborates our motivation for the layer-level discriminative operation, which employs different eviction ratio strategies for layers with varying densities of attention weights.
A.9 THEORETICAL ANALYSIS OF THE DYNAMIC ALLOCATION STRATEGY
In this section, we provide a detailed theoretical analysis demonstrating why the proposed dynamic KV cache allocation strategy is superior to using a uniform compression ratio p across all layers during the inference phase of LLMs. Our proof is grounded in information theory (Ash) 2012) and considers the multi-head attention mechanism inherent in Transformer-bast models.
A.9.1 PROBLEM FORMULATION
Consider an LLM with layers, where each layer contains H attention heads. During inference, each layer maintains its own key-value (KV) cache with limited size due to resource constraints.
19

---

Published as a conference paper at ICLR 2025
Table 17: Performance evaluation of D₂O across various models using range benchmarks from LongBench at 8k settings.
Model
MultifieldQA
HotpotQA
2wikimQA
GovReport
TREC
SAMSum
Loc
RB-P
Model
15.97
66.4
Local Window
0.00
0.17
0.00
0.38
0.00
0.00
4.70
4.69
Llama-2-7B
LM
15.05
6.68
5.77
6.72
52.67
41.39
62. 17
46.82
H₂O
15.06
8.53
7.00
7.31
52.67
42.44
61.66
30.70
RoCo
12.56
6.23
6.65
5.38
48.80
40.78
61.55
49.54
CaM
5.61
61.46
D,O
16.58
9.89
8.68
14.07
60.00
44.75
65.88
54.31
1.53
1.36
1.68
6.76
7.33
1.79
2.31
Full Model
22.48
73.00
73.81
Local Window
2.84
3.81
6.08
0.59
35.00
10.18
37.20
22.26
StreamingI.IMM
71.99
Llama-3-8B
H₂O
15.50
10.54
9,30
20.57
70.00
42.23
71.54
50.40
RoCo
14.23
10.11
8.88
18.56
66.89
40.12
69.98
51.12
CaM
14.04
10.57
8.78
18.97
67.29
40.00
70.04
50.98
D&O
18.57
12,50
10.43
22.72
71.96
44.64
73.95
54.57
3.07
2.15
1.96
20.
400
560
260
700
76.0
1000
1000
For
(a) 50k long-context fact retrieval of Full model.
(b) 100k long-context fact retrieval of Full model.
11.0
110
100
1913
Arre
(c) 50k long-context fact retrieval HgO method.
(d) 100k long ong-cootext fact retrieval HgO method.
20.0
u00
Sean Len:
50k long- congecontext fact retrieval of DzO.
(f) 100k long-context fact retrieval of D.O.
Figure 9: Visualization comparisons of congectntet fact retrieval tasks for several methods.
The total cache size is constrained by:
1 H
sh = Swatl p. H.
(17)
20

---

Published as a conference paper at ICLR 2025
0.0010
0.0008
0.0006
0.0004
0.0002
(a) layer 0
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
0.0000
(a) Attention weight visualization for Llama-1-76 on GSM8K datasct.
0.0010
0.0008
0.0006
0.0004
0.0002
(a) layer
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
0.0000
(h) Attention weight visualization for Jlmm--17b on COQA dataset.
0.0010
0.0008
0.0006
0.0004
0.0002
(a) layer
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
0.0000
(c) Attention weight visualization Llama-2-7b on GSM8K dataset.
0.0010
0.0008
0.0006
0.0002
(a) layer
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
(d) Attention weight visualization for Llama-2-7b on COQA dataset.
0.0010
D.0008
0.0006
0.0004
0.0002
(a) layer
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
0.0000
(e) Attention weight visualization for Llama-3-8B on GSM8K dataset.
0.0010
0.0008
D.0006
0.0002
(a) layer
(b) layer 1
(c) layer 16
(d) layer 30
(e) layer 31
(f) Attention weight visualization Llama-3-80 on COQA dataset.
Figure 10: Attention weight visualization across various models and datasets.
where St denotes the cache size allocated to the h-th attention head in the 1-th layer, S is the original cache size per head, and p the compression ratio. Our goal is maximize the model's output
21

---

Published as a conference paper at ICLR 2025
quality during inference by optimally allocating the limited cache resources among different layers and attention heads.
A.9.2 ATTENTION VARIANCE AND INFORMATION ENTROPY
Attention Weights as Probability Distributions. For each attention head in layer I, the attention weight matrix A E Lpromptx Leponye is computed as:
Q P
KLA
A 4 Softmax
(18)
where Qp/-h and KLAA the dimensionality. The attention weights can viewed as probability distributions over tokens:
A are the query and key matrices for the prompt encoding, respectively, and D is
exp(e!")) E cx)(
L.b Ps
(19)
where of is the attention score for token
Calculating Attention Variance and Information Entropy. The attention variance for head h in layer is:
FlAh = Var (s!. and s/th
A 1, [.,:]
(20)
t=0
where gith is the cumulative attention sequence obtained by summinn the columns of Ab". The information entropy for the attention distribution
H = Σ pt logg."
(21)
Typically, a lower attention variance Fí.h indicates a more uniform distribution (higher entropy H!'),, implying that information is more evenly distributed across tokens.
A.9.3 INFORMATION RETENTION AND CACHE SIZE
The information retained by attention head h in layer depends on its cache size S and information entropy H
74h = S(S H(A),,
(22)
where f is monotonically increasing function, indicating that larger cache size leads to higher information retention. The marginal information gain for head in layer is:
a7T
A
(23)
ash
During the inference phase, the attention weight distributions (and thus the information entropy H (/hh are determined by the model's parameters and input data, not by the cache size 5/. Therefore, H is treated as a constant and does not appear in 1.h because it does not depend on St.
A.9.4 OPTIMIZATION OBJECTIVE
Our objective is to maximize the total information retention Q under the cache size constraint:
H
r(S) H,),,, s.t.
Swottl-
(24)
St
h=1
1=
h=1
To maximize Q under the constraint, we use the Lagrange multiplier method from optimization theory. By introducing the Lagrange multiplier μ,, we construct the Lagrangian function:
L
H
L
H
L
Σ
sh
Swatl
(25)
h=1
1=1
h=l
22

---

Published as a conference paper at ICLR 2025
To find the optimal cache allocation that maximizes Q, under the constraint, take the partial derivative of the Lagrangian with respect to each S and set to zero:
dc
1 O.
(26)
as
This yields the condition:
01 μ, Vl,h.
(27)
as
This equation indicates that, the optimal allocation, the marginal information gain for each attention head equals the Lagrange multiplier In other words, we achieve the maximum total information retention Q when the marginal information gains are balanced across all attention heads.
Optimal Allocation of Cache Size. Under the constraint of limited total resources, if the marginal information gain of a particular attention head 11 is greater than Je, increasing its cache size will enhance the total information retention Q. Conversely, if the marginal information gain of an attention head 7 is less than μ4, reducing its cache size and reallocating those resources to attention heads with higher marginal information gain will increase Q.
A.9.5 DYNAMIC ALLOCATION STRATEGY.
Cache Size Allocation Based Attention Variance. We propose allocating cache sizes inversely proportional to the attention variances:
exp(- FL.h) E 1= exp(-
S
Swotl: where
of
(28)
This strategy ensures that attention heads with lower variance (higher entropy) receive more cache, adhering to the principle of allocating more resources to where the marginal information gain is higher. The total cache size for layer / with the layer-level allocation proportion are:
H
H
S
=
St and 0g =
(29)
4=1
1=1
Limitations of Uniform Compression. Under a uniform compression ratio each attention head receives the same cache size:
= S.
(30)
However, due to varying attention variances and entropies across different heads and layers, the marginal information gains 7 are unequal. This imbalance leads to suboptimal total information retention compared to the dynamic allocation strategy.
A.9.6 THEORETICAL PROOF OF SUPERIORITY
Total Information Retention Comparison.
Dynamic Allocation Strategy, The total information retention is:
1
H
I.
Qdynamic
ΣΣ
Lh dynamic
S dydynamic .1hhh.
(31)
1=1
[=1
Uniform Compression Strategy. The total information retention is:
I. H
L h (p-ss,HH EE
Q Quniform
ΣΣ
plhh uniform
(32)
1=1 1=1
Since the dynamic allocation strategy balances the marginal information gains across all attention heads, it maximizes the total information retention Qdynamic- In contrast, the uniform compression
23

---

Published as a conference paper at ICLR 2025
strategy cannot balance the marginal gains due to the diversity in H resulting in Quiitoem dynamic- Next, we give a numerical example.
Numerical Example. Since Il is monotonically increasing function, assume the information retention function of cache memory (Smith) 1982 Thomas & Joy 2006) is:
7l.h H (1 (1-exp) (-xs²²))
(33)
where & positive constant. The marginal information gain is:
A 74th Ol.h H eexp
(34)
ast
Set the marginal gains equal:
kxp (-ks)) = HL. k exp (-kstt) p.
(35)
Solving for S yields:
St
In
M Hlink
(36)
h
The total cache size constraint is:
1 Σ
S
Spatl-
(37)
1=1 h=1
By iteratively solving for μ. we obtain the optimal cache sizes S Comparison of Total Information Retention.
Dynamic Allocation. The total information retention is:
H (1 exp (-his ))
dynaamic
(38)
1=1
Uniform Compression. The total information retention is:
H H (1 ex-exp (-kpS)).
Q uuiiform
(39)
Since S S.h.dnamicc is adjusted based on H it follows that Qdynamic Qunifoem- By considering the attention variances and information entropies of individual attention heads, the dynamic KV cache allocation strategy effectively balances the marginal information gains, leading to maximal total information retention during inference. This theoretical analysis demonstrates that the dynamic allocation strategy outperforms the uniform compression strategy, as it optimally utilizes limited cache resources to enhance model output quality.
A. COMPARISON OF D₂O WITH OTHER NEW BASELINES
Table 18: Comparison of D₂O with other new methods in LongBench (20% KV cache).
Model
Qasper
QMSum
MultiNews
TREC
TriviaQA
SAMSum
Lec
RB-P
Full Cache
29.8
24.44
26.28
66.67
86.16
41.11
56.91
49.09
SnapKY
23.32
20.18
23.97
60.62
82.46
36.99
$2.68
45.53
PyrmiidKV
23,80
20.60
24.22
59.44
82,90
35.31
53.52
42.11
PyramidInfor
23.38
19. 80
21.23
58.35
78.24
35.18
52.35
41.88
SirLLMs
21.48
23.12
78.57
31.72
53.42
LoCoco
22.55
19.42
24,80
58.71
75.32
35.85
$4.15
41.58
D.O
25.72
21.90
24.06
62.99
84.02
38.03
55.17
46.15
We also conducted additional comparisons with more contemporary baselines: token eviction ap- proaches such as SnapKV (Liet 2024) and SirLLLM Yao et al. 2024). well as token compression
24

---

Published as a conference paper at ICLR 2025
techniques like LoCoco (Cai et al. 2024a). and layer-wise KV cache compression methods like PyramidKV V (Cai et al. 2024b) and PyramidInfer (Yang et al. 2024a). These experiments were performed on the LongBench dataset using the Mistral-7B model and followed the setting from Liu et al. 2024).
As shown in the Table 18 D2O consistently outperforms these baseline methods across most datasets. This demonstrates that D,O's combination of dynamic token-level merging and dynamic layer- wise cache allocation effectively preserves context and delivers robust performance in long-context scenarios.
A.11 D2O PERFORMANCE IN 100K+ LONG CONTEXTS
To validate the capability of D2O in handling ultra-long contexts, also conducted additional evaluations on datasets with longer contexts, including InfiniteBench (Zhang et al. 2024a) and RULER (Hsieh al. 2024). both featuring instances exceeding 100K tokens. To ensure a fair comparison, we utilized the - --B-tnstttctt (128K) model and benchmarked D2O against representative baselines, such HzO (based on eviction). PyramidKV (layer-wise reduction of KV cache) and CaM (mergency of value tokens). All experiments were performed on four A 1100 GPUs with 80GB memory.
The results, provided in the tables T9 and 20 demonstrate that D20 consistently outperforms these baselines across both InfiniteBench and RULER. These findings highlight D2O's ability to effectively preserve context and maintain strong performance in extreme long-context scenarios, further validating its robustness.
Table 19: Comparison of D₂O with other baselines in InfiniteBench (20% KV cache).
Model
R.PK
R.Num
R.KV
Choice
QA
Math.F
Code.Debug
Cache
100
99.52
28.66
62.15
25.78
35.86
26.94
0
62.15
63.84
18.85
51.42
16.13
27.65
19.35
Llama-31-8BB-nstte (128K)
PyramidKV
65.25
73.88
19.82
52.91
19.36
28.19
24.08
CaM
76.95
78.55
23.99
51.03
20.72
32.07
23.59
D2O
86.75
91.35
25.88
54.35
24.84
33.85
25.54
Table 20: Comparison of DyO with other baselines in Ruler (20% KV cache).
Model
4K
8K
16K
32K
64K
128K
Full Cache
95.5
93.8
91.6
87.4
84.7
77.0
H₂O
90.5
88.2
85.7
83.2
77.8
72.5
-lama-3.1-8B-Isttree (128K)
PyramidKV
89.5
88
86.2
82.1
79.1
71.7
CaM
91.6
86.6
85.4
81.8
79.6
72.6
D2O
92.1
89.7
86.2
83.7
80.6
74.7
A.12 COMPARISON OF D2O USING OTHER LONGBENCH SETTING
To validate the effectiveness of O under other LongBench settings (Cai 2024b), we conducted additional experiments, including using LLaMA-3-8B-Instee backbones, and conducted experiments under two KV cache scenarios (KV size 64 and 2048). For D2O, the total compressed KV cache size was configured as 64 L or 2048xL, where L is the number of layers. For comparison, results of SnapK V Li al. (024). StreamingI_LMM Xiao et al. (2023a). H₂O /Zhang al. (2024c), and PyramidK V /Zang et al. (2024c) were taken directly from the PyramidK Cai et al. (2024b) paper. The evaluation for D was conducted using the BrramidKV-rrovider LongBench settings. The results demonstrate that under extreme compression settings (KV size 64), D2O outperforms all baselines, highlighting the effectiveness of D,O's combination of layer-level dynamic KV cache allocation and token-level dynamic merging. With higher KV sizes (KV size 2048), D2O still achieves better performance than baselines on most datasets, confirming the importance of our two-level operation approach.
and Mistral - -B-Innstruc models as
25

---

Published as a conference paper at ICLR 2025
Table 21: Performance evaluation of D2O on various models in LongBench benchmarks following other sctting (Cai ct al. 2024b).
Dengte-
Multi Nutti-Decument QA4
Summarization
Summorization
Syuthetic
Code
Methods
SirQA
Quepei
Mif-cm
HelpoQA
TWiLIMAA
Missigss
GesReport
QMSum
MalliNews
TRRC.
TriviQA
SAMSum
PCrson
RB--F
StupKV
28.35
15.56
20.05
16.41
38.50
LM
17.46
8.68
22.25
35.37
31.51
15.97
13.46
20.06
14.64
38,00
72.33
29.10
5.42
69.50
46.14
45.09
H20
20.00
11.34
27.03
37.25
30.01
17.94
18.29
21.40
19.43
38.40
$4.70
$7.76
5.65
69.33
53.44
50.15
PysamiXVV
21.13
D20
22.50
15.30
33.45
39.18
30.12
17,50
21.15
23.10
22.15
60.12
$9.50
39,00
5.80
08.58
$4.50
47,00
M. Eilt-rrtrrrttt (KV size
2846)
SuppYY
25.86
29.55
41.10
44.99
35.90
21.51
25:96
23.40
26.46
73.50
90.55
41.66
5.17
69.25
56.65
49.94
Stroml M. 21.11
25.78
38.13
40.12
50.01
16.86
33.14
22.64
76.48
70.00
83.12
31.75
5.74
68.50
49.94
45.58
PyramicKV
25.40
29.71
40.25
44.76
35.32
21.98
23.30
23.30
26.19
73.00
90..5
42.34
5.22
09.25
59.76
51.18
Model 26.90
33.07
49.20
27.33
24.21
26.99
71.00
36.98
56,96
Mistral- Tl-Enttruct (KV sizu =:
SmpRV
16.94
17.17
39.51
36.87
22.26
15.18
14.75
20.35
21.45
37.50
$4.16
37.28
4.50
61.13
42.40
59.44
1120
18.19
19:04
37.40
30.18
22,22
13.77
16.60
21.52
21.98
37.00
$1.00
38.62
5.00
66:05
43.54
40.46
ParamkKV
D20
22.50
21.38
41.26
38.15
23,50
16,20
23.54
22.50
22,00
55.00
$2.50
38.00
2.32
67.00
47.53
41.81
Mistral-7--nsstree (KV
2048)
Snup&Y
Stnsenl.1M
20.31
26.64
45.72
35:25
24.31
12.30
27.47
21.57
24.51
66.50
71.05
31.19
5.00
22.56
43.38
57.08
25.76
26.60
PyramicKV
25.53
32.21
48.97
42.26
27.50
19.36
23.95
23.97
26.73
71.00
36.25
42.94
4.50
37.90
53.12
47.21
D20
26.18
33,12
43.88
43.50
27.38
19.45
33.20
24.55
26.88
71.58
36.12
43,30
5.35
87.21
57.10
5475
26


Reviews:
[{"review_id": "F6jvblQplj", "reviewer": "Reviewer_JAQq", "summary": "This paper presents Dynamic Discriminative Operations D2O, an efficient generation method in large language models. D2O uses layer-level to dynamically adjust cache usage and token-level strategies to merge discarded tokens. D2O achieves significant memory savings and improves throughput without sacrificing generation quality, as demonstrated in various benchmarks and LLM architectures.", "questions": "- As the generation length increases, if a certain KV Cache budget is maintained, the effect of token merging is expected to weaken. Are there any experiments on this?\n- The performance testing in the paper separates the benchmarks from the throughput tests. In the LongBench, the prompts are usually long while the outputs are short, so the methods presented in this paper may not save much time on such tasks. Are there more suitable benchmarks where the generated text is longer, allowing for simultaneous evaluation of generation speed and performance?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- D2O takes into account the phenomenon of varying attention score densities across different layers in LLMs, dynamically allocating KV cache budgets for each layer. Additionally, for important discarded tokens, D2O uses a weighted merging approach to retain their information, mitigating information loss during token eviction.\n- Compared to various KV cache compression methods, D2O demonstrates consistent superiority across a wide range of benchmarks and different models. With a comparable improvement in throughput, D2O achieves significant performance gains in task execution.\n- This paper provides extensive ablation analysis, validating the effectiveness of each component within D2O.", "weaknesses": "- The Introduction states that \"existing methods equally treat all the layers and indiscriminately evict KV pairs at each layer.\" However, some prior work has already considered allocating different KV cache budgets across layers, such as PyramidInfer[1] and PyramidKV[2]. The allocation method in D2O should be compared with those in previous works.\n- The use of mathematical symbols is confusing. For example, the F representing variance in line 207 is a scalar and should not be in bold, as well as u_ij in line 261.\n- The experiment setup is not clear enough. For example, in Section 5.3, the maximum length setting for the LongBench test is mentioned.\n\n[1] PyramidInfer: Pyramid KV Cache Compression for High-throughput LLM Inference (Yang et, al.)\n\n[2] PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling (Cai et, al.)", "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": "EsbVJQDd2S", "reviewer": "Reviewer_LdwY", "summary": "This paper proposes D2O, a method for efficient LLM inference through dynamic KV cache optimization. The key contributions include: (1) layer-wise cache allocation based on attention density patterns, and (2) a token-level strategy combining eviction with dynamic merging using EMA threshold. The method achieves 3x throughput improvement while maintaining generation quality across various tasks.", "questions": "-How does the computational overhead of D2O scale with increasing sequence lengths and model sizes?\n\n-What are the trade-offs between the compression ratio and the quality of the generated output?\n\n-How does D2O handle extreme cases, such as sequences longer than 100k tokens?\n\n-Why is the exponential function chosen for the allocation strategy? Have other functions been considered?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "-The paper brings up a major snag in putting LLMs into action, especially the memory requirements of the KV cache during making inferences. This is a crucial issue for real-world applications.\n\n-The authors have conducted extensive experiments across multiple LLM architectures  and tasks, providing a broad evaluation of the method's effectiveness.\n\n -D2O shows notable improvements in throughput and memory efficiency, achieving up to 3x higher throughput while preserving generation quality, which are important metrics for the deployment of LLMs.", "weaknesses": "-The core ideas (layer-wise allocation and token merging) are largely combinations of existing techniques. The EMA threshold mechanism is straightforward and lacks theoretical justification.The dynamic allocation strategy is similar to existing attention-based pruning methods\n\n-There is insufficient analysis. There is no ablation study on the impact of different attention patterns across layers. There is also limited discussion on why the 3:1 ratio for N:M works best. \n\n-Regarding experimental concerns, the comparison with baselines is not entirely fair as some methods (like H2O) are designed for different scenarios. There is no discussion on the trade-off between computational overhead and memory savings.", "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": "MnTu60dqAO", "reviewer": "Reviewer_VHpa", "summary": "This paper focuses on token eviction for large language models and introduces a dynamic allocation strategy at the layer level and a compensation mechanism at the token level.", "questions": "Please refer to Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed token eviction mechanisms at both the layer level and token level are well-reasoned and contribute to performance improvements in the models.\n2. The effectiveness of the proposed methods is validated across multiple model backbones and long-context benchmarks.", "weaknesses": "1. The experimental comparisons are not comprehensive enough. The authors should compare their method with recent token eviction approaches, such as SnapKV and SirLLM. Additionally, comparisons with token compression techniques like LoCoco would be beneficial.\n2. It is suggested that the authors evaluate the performance of their method on benchmarks with longer contexts, such as InfiniteBench and RULER, which consist of instances up to 128K tokens.", "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": "Dr7jgT1wfU", "reviewer": "Reviewer_FB7s", "summary": "This paper explores methods for saving the KV cache during inference of large language models. Specifically, the authors investigate ignoring less important tokens in the context during decoding and find that, to prevent excessive performance degradation, the number of tokens discarded should vary across different layers. Additionally, they explore a token compensation mechanism to mitigate the information loss caused by discarding tokens. Experiments demonstrate that their approach accelerates the model while maintaining performance.", "questions": "* In formula (5), $S_\\ell$ is the cache size for each layer. However, when calculating $\\alpha_\\ell$, the number of model layers $L$ is multiplied again. Is this a typographical error?\n* In formula (6), I cannot understand the calculation of AttnScore during token generation.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* The motivation is clear and saving the KV cache of LLMs during inference is significant.\n* This paper deeply investigates the difference in token eviction across layers and explores a reasonable token compensation mechanism.\n* The experiments are relatively extensive.", "weaknesses": "* Some judgments are inaccurate. As noted in lines 181-182: \"Employing a uniform eviction strategy such as the ones proposed in H2O...\". However, to my knowledge, H2O also adopts a layer-wise token eviction strategy, as evidenced in its open-source code [1].\n* The baselines are limited. Exploring the issue of token eviction ratios across different layers is highly meaningful. However, to my knowledge, some relatively classic works in this area, such as PyramidKV [2], were not considered by the authors.\n* Some experimental results are quite unusual. In detail,\n  * Logically, discarding some tokens would lead to information loss. However, some results in Figure 5 of the paper indicate that, after discarding certain tokens, the performance improves significantly compared to the original model (for instance, on the TruthfulQA task). Is this reasonable?\n  * The evaluation results on Longbench differ significantly from those in some previous studies. For example, The results in line 423 of the paper differ by more than **10** points from those in Table 1 of PyramidKV [2] and SnapKV [3]. I believe the authors need to carefully review and revise their findings to provide more reliable results.\n\n[1] https://github.com/FMInference/H2O/blob/main/h2o_hf/utils_real_drop/modify_llama.py#L357\n\n[2] Zhang, Yichi, et al. \"PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling.\" arXiv preprint arXiv:2406.02069 (2024).\n\n[3] Li, Yuhong, et al. \"Snapkv: Llm knows what you are looking for before generation.\" arXiv preprint arXiv:2404.14469 (2024).", "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": "nreyTRC1aE", "reviewer": "Reviewer_aSVX", "summary": "This paper introduces Dynamic Discriminative Operations (D₂O), a method to optimize KV cache management in large language models. At the layer level, D₂O allocates cache sizes dynamically based on attention variance. At the token level, it merges similar tokens and prunes less important ones, preserving essential contextual information. This approach reduces memory usage while improving efficiency and accuracy in long-text generation and inference tasks, outperforming existing cache compression techniques.", "questions": "1. For the Dynamic Allocation Strategy, could it result in a single layer's computational load exceeding that of processing all tokens in a layer? How would this be handled in such cases?\n2. In the Dynamic Allocation Strategy, how do you ensure that the computational load is uniform across samples within a batch? Could there be scenarios where some samples in the same batch have significantly higher or lower computational loads, thus reducing inference efficiency? Can this strategy be integrated with existing inference acceleration methods like vLLM?\n3. In the Dynamic Allocation Strategy, is there any physical rationale behind the decision to allocate fewer KV caches to layers with high attention score variance?\n4. Could the method be compared to a smaller full-size model with similar inference time costs?\n5. In Table 9 and Figure 5, D₂O performs better than the full model in some tasks. Could you explain and analyze the reasons for this outcome?\n6. In Section A.4, could you provide results for the full model in the multi-turn dialogue examples for comparison?\nWhat are the inference costs in Table 3 for identical batch sizes?\n7. Missing citation: https://arxiv.org/pdf/2408.03675 . This paper also focuses on optimizing token eviction methods which introduces a random eviction strategy that retains more token information.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method outperforms traditional eviction-based approaches, significantly reducing performance loss in sparse long-text inference.\n2. Extensive experimental analysis on hyperparameter selection, various models, and datasets strongly validates the method's effectiveness.\n3. The method demonstrates excellent generalizability, as it can be applied to a wide range of existed pretrained models without requiring additional post-training or fine-tuning.", "weaknesses": "The innovation and novelty of the proposed method are somewhat limited compared to existing sparse attention pre-trained models or eviction-based inference approaches. For instance, the concept of token merging has been discussed in several prior works, such as https://openreview.net/pdf?id=LCTmppB165 and https://arxiv.org/html/2407.08454v1. Additionally, the idea of dynamically allocating different computational loads to different layers has also been explored in other works, such as https://arxiv.org/pdf/2404.02258.", "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)