Keep the Cost Down: A Review on Methods to Optimize LLM’s KV-Cache Consumption
Authors: Shi Luohe
Hongyi Zhang
Yao Yao
Zuchao Li
hai zhao
Venue: COLM (2024)
Keywords: efficient, KV-Cache, LLM, inference
TL;DR: A comprehensive review on KV-Cache compression, involving various methods in the training, deployment, and inference stages.

Abstract: Large Language Models (LLMs), epitomized by ChatGPT's release in late 2022, have revolutionized various industries with their advanced language comprehension. However, their efficiency is challenged by the Transformer architecture's struggle with handling long texts. KV-Cache has emerged as a pivotal solution to this issue, converting the time complexity of token generation from quadratic to linear, albeit with increased GPU memory overhead proportional to conversation length.  With the development of the LLM community and academia, various KV-Cache compression methods have been proposed. In this review, we dissect the various properties of KV-Cache and elaborate on various methods currently used to optimize the KV-Cache space usage of LLMs. These methods span the pre-training phase, deployment phase, and inference phase, and we summarize the commonalities and differences among these methods. Additionally, we list some metrics for evaluating the long-text capabilities of large language models, from both efficiency and capability perspectives. Our review thus sheds light on the evolving landscape of LLM optimization, offering insights into future advancements in this dynamic field.

Published as a conference paper at COLM 2024
Keep the Cost Down: A Review on Methods to Optimize LLM's KV Cache Consumption
Shi Luohe Zhang Hongyi National Engineering Research Center
Yao Yao
Department of Computer Science and Engineering,
for Multimedia Software, School of Computer Science, Wuhan University, Wuhan, 430072, P. R. China
Shanghai Jiao Tong University yaoyao27esjtu. wettu.edducc. en
(shiluohe, harryzhang ewhau @wh..edu. edu. cn
Li Zuchao"
Zhao Hai
National Engineering Research Center for Multimedia Software, School of Computer Science, Wuhan University, Wuhan, 430072, P. R. China zcli-charl weeccharlie@wee www.eeeeew.wuccrrrrr.
Department of Computer Science and Engineering, Shanghai Jiao Tong University zhaohai@cs sj tu. edu. cn
Abstract
Large Language Models (LLMs), epitomized by ChatGPT'ss release in late 2022, have revolutionized various industries with their advanced language comprehension. However, their efficiency is challenged by the Transformer architecture's s struggle with handling long texts. KV Cache has emerged pivotal solution to this issue, converting the time complexity of token generation from quadratic to linear, albeit with increased GPU memory overhead proportional to conversation length. With the development of the LLM community and academia, various KV Cache compression methods have been proposed. In this review, we dissect the various properties KV Cache and elaborate on various methods currently used to optimize the KV Cache space usage of LLMs. These methods span the pre-training phase, deployment phase, and inference phase, and we summarize the commonalities and differences among these methods. Additionally, we list some metrics for evaluating the long-text capabilities of large language models, from both efficiency and capability perspectives. Our review thus sheds light on the evolving landscape of LLM optimization, offering insights into future advancements in this dynamic field. Links to the papers mentioned this review can be found our Github Repo https: //gi thub. com/ wwwel--charll htwpii--chhreeee/eeeoeeeeee-eeee Leee///esoe--KCaachr
1 Introduction
Since the release of ChatGPT, Large Language Models (LLMs) are gradually having pro- found impact on people's s lives and are standing out in various fields (Wu et al., 2023; Roume- liotis & Tselikas, 2023b;a). These LLMs face a computational challenge: their Decoder-Only Transformer architecture has a quadratic time complexity when processing text sequences. During inference, the ruto-regressive decoding mechanism amplifies this issue, it repeats the process for each token generated. KV Cache, by storing the keys and values tensor in attention module generated by past tokens, can reduce the time complexity required to generate each token to linear, greatly improving inference efficiency. However, the use of KV Cache is not all advantageous. KV Cache will increase linearly with the length of
* *Corresponding author

---

Published as a conference paper at COLM 2024
the sequence, and the memory required will become larger and larger, especially for giant models like GPT-3 (Floridi & Chiriatti, 2020). Moreover, each individual dialogue needs to save its own KV Cache, and different dialogues can hardly reuse them, which will become bottleneck in the generation speed on modern inference hardware like GPU as they usually suffers from the low memory bandwidth comparing to their computing speed (Yu et al., 2022).
Recent months have seen emerging work on optimizing KV Cache, making it critical focus for enhancing LLMs' performance with longer contexts. This review presents various methods of KV Cache optimization, clarifying their interrelationships and comparing their core ideas. We discuss extensive methods to reduce memory space: before inference, the model itself can be compressed, or the architecture can be changed, completely abandoning attention with quadratic complexity; during inference, from the model input prompt level, to the embedding level, and then to the KV Cache level, compression can be performed. This paper primarily focuses on editing, modifying, and optimizing KV-Cache itself, with other methods briefly mentioned in Appendix C. These optimizations are considered the safest, most effective, and compatible approach known to date. A general preview can be found in Figure 1.
This review unfolds in chronological order of the LLMs, from the training phase, to the deployment phase, and finally to the post-training phase. In the training stage, we will introduce the KV Cache compression methods that can be used during model pre-training. These methods are usually the most effective, but they are not suitable for modifying existing models or scenarios with low computational budget. In the deployment stage, we will introduce the use of different frameworks to optimize the use of KV Cache. The methods in this section will not make a large number of modifications to KV Cache itself, but can significantly optimize its efficiency in the same environment. Finally, in the post-training stage, we will introduce a large number of on-time optimization methods for KV Cache, mainly including three methods: Eviction, Merging, and Quantization.
Additionally, we introduce metrics to assess LLMs' performance on long texts, which are vital for KV Cache optimization. These metrics are divided into efficiency and performance aspects. Efficiency measures include model generation speed and space occupancy improve- ment, while performance metrics evaluate the impact model capabilities, ensuring any capability loss remains acceptable.
In conclusion, this review chronologically introduces KV Cache optimization methods in LLMs, aiming to enhance model inference efficiency and context length. This review aims to summarize and analyze various LLM optimization methods from the perspective of KV-Cache, enabling the readers to better understand KV Cache optimization and build more effective, efficient, and sustainable LLMs.
2 Preliminary and Notations
Before introducing the KV Cache compression method, we must must rigorously define frequently occurring symbols to avoid ambiguity in the narrative. The core function of LLM is to transform a natural number sequence input into equal amount of multiple probability distributions LLM(() = LLM((1X2 Xn) P1P2... Pu- In this paper, we denote X as the input sequence of integers, named tokens, with the length n, composed by x; as the i-th token. Then LLM translates them into Pt. which is the probability of the next token corresponding to x,. the vocabulary, V. The size of the vocabulary is denoted as V = [V]. Naturally, we have X E V" x; V {0, 1,.,,, V V-1,, and p; RR The input X is translated from the natural language input PROMPT in tokenization, and usually pn is used to predict the next token with various sampling algorithms when auto-regression decoding.
a LLM, the entire set of possible values for x; constitutes
Within the LLM, I. Transformer Decoder blocks are sandwiched between the Embedding layer and linear layer (along with softmax). The Embedding layer translates every token
x; into d-dimensional vector h,) while the linear layer and softmax transform every
2

---

W w!),, paired with position embedding matrix R;, and w!!. In other words, H(O is mapped to ((1), K(),, and v(), Another matrix w!") is then used to map the output of the Published as a conference paper at COLM 2024
Word cache
Cache Cache
DOM
Token
Training
Deployment
Reintroduce
Embed k/)
for compression
Quar
Paged Attention for efficient memory usage
Grea-
K V
Decoder
LLM
GOA
Luntonn
4
(0)
Post-Training
Decoder
Block #0
k
quantisation for casy and steady compression
(1)
Decoder
Block #1
Cross-served server inferencing
Decoder Block...
Attention/ score
spectfic
Eviction with less information
loading aff-loading
Various fine grained methods
Figure 1: An overview of the main structure of KV Cache compression methods
d- d-dimensional vector ( into probability distribution p;. We denote as the layer count, and (f the hidden state of i-th token, after 1-th layer (here treat the embedding layer as the 0-th layer). At last, (1)) represents the matrix formed by concatenating h/" vectors.
Each Transformer Decoder Block consists of two parts: Self-Attention and Feed-Forward Network (FFN). Each part has its own residual connection and Normalization (Norm) operation. In this paper, we only focus on the Self-Attention part. In the Decoder Block,
(I) k!),, and of") using three trainable matrices each (n!)) is mapped to three new vectors 9:"
Self-Attention layer to the input (1) for single token, and ((()) for the entire sequence. The process is given by Formula 1.
(Q"). (Q")K())
K(O))
)) v()). w!!)
H softmax
mask
(1)
Vd
Modern LLMs utilize multi-head attention (MHA). The idea is to split q, k, and v into na smaller blocks, named heads, each with d, = d/n,, dimensions. For the j-th head of 1-th layer, we denote (Q, K, V. Wy, W₁, Wo, Wi k; ((i for the corresponding partition of these matrices or vectors. In MHA, Causal Mask mask(.) was used to prevent earlier tokens attend on later ones, by adding innf the upper right triangle of the pre-sof tmax attention matrix. This crucial property ensures that the K and V computed by preceding tokens will not be affected by subsequent tokens. Therefore, for each token newly added during k())
auto-regression decoding, only need to update previous K and V, as (<(),x())
and (v(),, vn v(1), and perform Formula 2. The K and V which we retained are called KV Cache.
ql "M""KK00"
k(.i)T dd
)) v(()) w!"))
1/ (1) Concatenate "y softmax mask
(2)
3

---

Published as a conference paper at COLM 2024
(1)
(0)
(1)
lo
io
(1.0)
(1.1)
(1.2)
(L33
(1.0)
(1.1)
(1.2)
(1.3)
(1.0)
(1.1)
(1.2)
(L3)
9:
9:
9:
qi
9:
qi
9i
41
4
9:
K (1.0
K
(..1
(1.2)
K (1.3)
K
(1.0
K (..)
K(L
(1,0)
11.13
(1.2)
(13)
(1.0)
(1:1)
(1.2)
(1.3)
(1.0)
(1.1)
(1.2)
(L3)
a
a
V/ (1.0)
(L.1)
((22
V(L3)
V(L0)
1/(00)
V(.1)
nio
(())
it
(())
MHA
MQA
GQA
Figure 2: The comparasion between MHA, MQA and GQA. To be note that the final linear
layer ( is not depicted here.
3 Training Stage Optimization
For LLMs that adopt the traditional Decoder-Only Transformer architecture, the most effective KV Cache compression method emerges during the pre-training phase. This is because, in this phase, the model possesses the greatest plasticity. The primary adjustment in this phase is to the model architecture, which, while still retaining the excellent properties of Attention, reduces the size of the generated Keys and Values vectors to quarter even less.
Shazeer (2019) proposed Multi-Query Attention (MQA) based on Multi-Head Attention (MHA). Shazeer claimed that even if we retain only one head for keys and values, we can still achieve satisfactory model performance. In this case, different query heads calculate attention scores with the same key head. Although there is only one head left for value, it will receive ni, different combination weights, resulting in пı combinations. Doing so can instantly optimize the KV Cache space usage to 1/n, of the original.
Reducing the number of keys and values heads from n1 to 1 is undoubtedly an aggressive strategy. Hence, Ainslie et al. (2023) proposed Grouped Query Attention (GQA), method that can better balance speed and performance. In GQA, query heads are divided into "g groups. Each group shares one key head, serving as the ng/Mg different combination weights for the corresponding value head. Ultimately, the KV Cache we need store will be reduced to /g, Compared to MHA and MQA, GQA introduces an adjustable parameter ng. When ng 1, we get MQA; when fgg nn, we get MHA. When ng is between and R/y efficiency and performance achieve more granular balance. Moreover, GQA can save substantial number of parameters within the Attention module, with the ratio of savings 1) 0.5 0.5 f1g/ n4.- comparison of MHA, MQA and GQA can be found at Figure 2. The current usage of GQA and MQA in open-source models can be found in Appendix A.
GQA reuses the KV Cache within layers, then the method proposed by Sun et al. (2024); Brandon et al. (2024); Goldstein et al. (2024) involves inter-layer KV Cache reuse. By sharing KV headers across layers, we can reduce the KV Cache size while maintaining model capacity. Specifically, the Brandon et al. (2024) method directly reuses these contents across layers, as CLA, whereas YOCO and GoldFinch in Sun al. (2024); Goldstein al. (2024) introduce more significant changes: they generate the all layers' KV Cache using linear models, like RetNet (Sun et al., 2023a) and RWKV (Peng et al., 2023a). However, it's essential to note that these methods do not optimize the memory bandwidth bottleneck of the KV Cache. Cross-layer reuse results in scattered access to the same KV Cache, and only meticulously crafted CUDA kernels can effectively reduce data exchanges between different cache levels, if such reduction is possible at all.
We can consider reuse form of low-rank compression, and complete low-rank com- pression should have even greater potential. The method proposed by DeepSeek-At et al. (2024), called Multi-Head Latent Attention (MLA), exemplifies this. MLA achieves KV
4

---

Published as a conference paper at COLM 2024
Cache decompression by utilizing additional dimension-expandiing matrix, rather than merely reusing the existing content. However, it's essential to note that this method still does not address the memory bandwidth bottleneck, as the cache still needs to be expanded into large KV vectors.
Yen et al. (2024) proposed new idea for the LLM architecture. CEPE, framework that combines the pre-trained LLM with an Encoder module that serves as context compressor.
In RAG scenario, the ultra-long context will greatly increase the need to store KV Cache. CEPE's additional Encoder compresses these reference texts, and then inputs them into the Decoder through cross-attention. The compressed text has shorter sequence length than before, so the KV Cache is saved. This method can use the pre-trained LLM, but the added decoder and cross-attention layer still require lot of extra training.
4 Dtploy-Stage Optimization
From the perspective of inference systems, KV Cache presents significant challenges in two key areas. First, during the continuous {K, kn - K and [V,u,] V operations, memory is repeatedly allocated and released, resulting in substantial fragmentation. Second, the inability batch-process KV Cache exacerbates severe memory bandwidth bottlenecks, leading to computational inefficiency. Addressing these two issues has become a central
concern for inference systems.
Kwon et al. (2023) introduced the Paged Attention mechanism and the vLLM framework. Paged Attention draws on the page memory mechanism widely used in CPU memory, and uses an additional mapping table to map the KV Cache that used to be stored continuously to discontinuous GPU memory. During inference, in order to generate the next token, it is necessary to call KV Cache for calculation, and this process can also be efficiently completed through set of custom CUDA kernels. The use of the Paged Attention mechanism results in almost no unused memory fragments and efficient inference.
Lin et al. (2024) further developed the idea of Paged Attention. Through the DistAttention it proposed and the DistKV-LLM built on it, KV Cache was able to achieve distributed deployment on multiple servers. This significantly improved the efficiency of providing LLM services using large-scale cloud servers.
Ye et al. (2024) aims to reuse KV Cache between different dialogues, achieving acceleration of the pre-fill stage and optimization of GPU memory occupancy. By establishing dictionary tree for all historical dialogues, and finding the longest common prefix in the dictionary tree when a new dialogue request is received and reusing the corresponding KV Cache for this part, the ChunkAttention
made the model avoid repeated calculation of some tokens in the pre-fill stage, speeding up the response speed of the deployment system. Moreover, Gao et al. (2024) extend this idea by introducing hierarchical system that utilizes multiple storage devices.
Jin et al. (2024) and Lee et al. (2024) offload KV Cache to CPU with speculation. The core idea is to offload the primary portion of the KV Cache to the CPU, retaining only critical components. During inference, by speculatively reloading small amount of KV Cache onto the GPU using the limited preserved information, we can save memory space on high-speed computational devices without compromising performance, all while avoiding extensive data exchanges.
He & Zhai (2024) introduces novel approach: by collaboratively utilizing the CPU for attention computations, we can enhance utilization efficiency, improve overall effective computational power, and accelerate inference speed.
Additionally, Qin et al. (2024) provides a comprehensive technical report from an enterprise perspective, optimizing the entire inference system.
5

---

Published as a conference paper at COLM 2024
5 Post-Training Optimizations
5.1 Eviction and Merging
Eviction methods are about the policies to discard unnecessary tokens. Two lines of ap- proaches exist: static policies, which are designed before inference and remains consistent across every inference request, and dynamic policies, which utilize the information gener- ated while inference to identify important tokens.
Static policies A straightforward approach for maintaining a fixed-size KV Cache is to retain recent tokens, known slide window attention (Beltagy et al., 2020). However, the model will collapse when sequence length exceeds cache size (Xiao et al., 2023). Recently, Xiao et al. (2023) and Han et al. (2024) proposed that initial tokens almost consistently receive high attention weights across layers and heads. As a result, keeping KV Cache of both initial and recent tokens can maintain model performance for long contexts.
Dynamic policies Policies based on attention weights have been widely explored by researchers, they believe that attention weights can provide insights into the importance of individual tokens. This can be leveraged in the design of dynamic strategies for eviction. Since it is impossible to predict which token will be necessary for future generation, the question arises whether it is possible to estimate the importance of a token based on history information.
Liu et al. (2023) empirically finds existence of Repetitive Attention Pattern. This pattern suggests that for two different tokens, there are similarities in what they are attending to and ignoring. So natural hypothesis is that only the tokens which are important in previous steps will be significant in the future.
This provides us with the possibilities to estimate future significance of a token based on history information of attention weights. Token Omission Via Attention (TOVA) (Oren et al., 2024) proposes a simple greedy method to discard useless tokens. While keeping a fixed-length of KV-Cahce, TOVA evicts at each decoding step the tokens with minimal attention weights layer-wise.
H2 Eviction Algorithm (Zhang et al., 2023) uses accumulative normalized attention scores to decide which token to stay and at the same time keeps the recent tokens since they may show strong correlations with current tokens.
PyramidInfer(Yang et al., 2024a) uses layer-wise approach with recent tokens occupying more weights. Apart from this, Yang et al. (2024a) believes that deeper layer contains more context redundancy, it defines decay ratio to shorten the length of KV Cache in deeper layers and thus forming a "pyramid".
However, while discarding unnecessary tokens seems have minor influence on the original inference process, Adnan et al. (2024) observes that when evicting more tokens during the inference process, the distribution normalized attention scores becomes uneven among the remaining ones. Therefore, Keyformer( (enfformr((Adaan et al., 2024) introduces additional methods to smooth the uneven distribution and approximate the original one when using full KV Cache.
FastGen (Ge et al., 2023) uses hybrid strategy to optimize token selection for discarding. In prompt encoding phase, it selects the best policy for each head in KV Cache, and then uses these policies to decide which token to discard in decoding process. The policies include: a) keeping special tokens, b) keeping punctuation tokens, c) keeping recent tokens and d) policies.
keeping tokens with attention-weight-bann
SparQ Attention (Ribar et al., 2023) tries different approach. Instead of reducing memory
capacity, it aims at reducing the amount of data transferred. It first uses the norm of 4/
to decide which k!") needs to be fetched, and approximate the attention scores based this subset of queries and keys. Then selects the top-K attention weights and fetch their corresponding Key-Value pair to calculate the output. To compensate the values that are

---

Published as a conference paper at COLM 2024
Traditional Policies
Static Policies
Dynamic Policies
Current Previous Token
Token
Attention
Local
Attention
(a) Dense
(b) Window Attention
(c) Initial Token
(e) Attention Based
The darker the color, the higher the token attention weight.
Attention
Attention
Figure 3: The comparison between different KV Cache policies
considered insignificant, keeps a running mean value vectors and interpolates between this running mean and the output of attention to approximate the original distribution.
Methods based on attention score also includes Corallo & Papotti (2024); rae Jo Shin (2024); Xu et al. (2024); Fu et al. (2024).
While attention scores provide ample information, they are incompatible with certain optimization methods, such Flash Attention (Shah et al., 2024). Therefore, investigating how to evict tokens without relying on attention scores is a novel research topic. Several approaches address this challenge. Tang et al. (2024) leverages the prior-known properties of attention heads to determine whether to evict. Yao et al. (2024) uses token entropy to decide whether remove tokens. Devoto al. (2024) relies on the L2 norm of keys determine token eviction. All these methods can be combined with Flash Attention. Notably, Devoto et al. (2024)'s 's approach demonstrates excellent granularity and controllability.
Merging, as relatively recent method, represents natural extension of Eviction, transition- ing from hardmax softmax. The current key challenges in this area include determining the merging region and selecting appropriate scheme for combining keys and values.
Nawrot al. (2024) proposed Dynamic Memory Compression (DMC), which use a single, after-trained dimension in key to determine whether to merge or not, and use attention score as the reference of merging. Wang et al. (2024) proposed the KVMerger, to merge KV by Gaussian weights and attention score.
Yu et al. (2024) proposed a novel approach merge KV Cache of each token across different attention head, with small amount of additional training, eventually turning an MHA model into a GQA model. Also requires additional training, Pang et al. (2024) proposed Anchor-LLM, which utilizes an innovative anchor-based self-attention, to help model learn how to merge KV Cache into a few token when training, achieving an outstanding performance.
Quantization
Another commonly utilized method for compressing Key-Value (KV) cache is through quantization. This approach effectively compresses data by mapping tensor values, origi- nally in full precision, to discrete levels and storing them at reduced precision. There are two primary categories of KV Cache quantization: Full quantization and KV Cache-only quantization. Full quantization involves compressing both the model weights and the KV Cache, thereby reducing the memory footprint of the entire model. On the other hand, KV Cache-only quantization specifically targets the KV Cache activations, selectively compress- ing them to conserve memory while leaving the model weights in their original state. This tailored approach can offer balance between model efficiency and performance.
KV Cache only quantization Hooper et al. (2024) further identified that Key matrices in language models often exhibit distinct outlier channels characterized by larger average magnitudes compared to others. To address this, They proposed KVQuant, method
7

---

Published as a conference paper at COLM 2024
to quantize Key and Value activations using distinct strategies. KVQuant's key features include: (1) Per-Channel and Per-Token Quantization, employing channel-based quantiza- tion for Keys and token-based for Values, effectively managing outlier distributions and mitigating distortion from Rotary Positional Embeddings (RoPE). (2) Sensitivity- Weighted Non-Uniform Datatypes, which enable more accurate activation distribution representation within layers. (3) Isolation of Outliers, minimizing skewness in quantization ranges to enhance quantization precision. (4) Normalization of Quantization Centroids, aligning
post-quantization distribution mean and standard deviation with pre-quantization values, beneficial in ultra low-bit quantization like 2-bit scenarios.
GSM8k
MMLU
BBH
HellaSwag
ARC- ARC-Challenge
WinoGiaande
WikiText2
PTB
C4
Model
Method
ACC
ppl
LLaMA2-7B
FP16 baseline
16.30
33.58
44,80
56.67
39.84
67.24
5.47
37.91
7.26
GEAR
15,20
33.01
44.45
WKVQuant
56.14
40.78
67.48
5.64
38.85
7.49
QAQ
76.30
LLMMA2-138
FP16 Baseline
30:34
40.79
59.69
45.56
69.69
4,88
50.93
6.72
GEAR
27.97
37.38
WKVQuant
58.98
43.94
68.75
5.00
52.36
6.89
QAQ
76.60
Table 1: Comparison of different quantization methods. Results are reported by Hooper et al. (2024), Dong et al. (2024b) and Dong et al. (2024b)
Dong et al. (2024a) introduces LESS (Low-rank Embedding Sidekick with Sparse policy), which integrates a constant-sized cache with eviction-based cache methods (Section 5). Inspired by recurrent networks, LESS utilizes a constant-sized low-rank cache by replacing the softmax with a separable similarity metric calculated by learnable row-wise functions. By doing so, LESS obtains the ability to accumulate history token information before they are discarded from KV Cache, allowing for continued access to previous information.
Yang al. (2024b) proposd Mixed-precision KV Cache (MiKV), reliable cache compression method that retains evicted KV pairs in reduced precision to preserve information and maintains important KV pairs in higher precision to ensure generation quality. MiKV employed Dynamic Outlier Awareness to dynamically balance the outliers manifested in the query and keys reduce quantization error. Dynamic Outlier Awareness multiplies and divides a channel balancer to the keys and queries to mitigate the impact of outliers.
Dong et al. (2024b) proposed the Quality Adaptive Quantization (QAQ). QAQ utilized separate quantization strategies for key caches and value caches, ensuring that the key cache, which is more sensitive, is quantized in way that less affects model performance. QAQ also uses an attention window to predict future attention scores based on the history of attention values. This ensures that the quantization does not overly compress tokens that may become more important in subsequent generation steps.
Kang et al. (2024) proposed GEAR (Generative Inference with Approximation Error Reduc- tion) which integrates three techniques: (1) Uniform quantization for the majority of entries. (2) Low-rank matrix approximation for quantization residuals. (3) Sparse matrix to handle errors from outlier entries.
Full quantization Sheng et al. (2023) proposed FlexGen which compresses both model weights and attention cache to 4 bits without significant accuracy loss.
Yue et al. (2024) took FlexGen a step further and proposed WKVQuant. For weight quanti- zation, WKVQuant ultize the OmniQuant (Shao et al., 2023). For KV Cache quantization, WKYQuant employs following three strategies: Past Only Quantization, Two-dimenssonal Quantization and Cross-block Reconstruction Regularization. Different from KVQuant (Hooper et al., 2024) which focus on calibrating for (er-channel(token) thresholds to ignore outlier, WKVQuant focuses on aligning and smoothing each channel and token.
8

---

Published as a conference paper at COLM 2024
6
Evaluation
In this section, we first introduce the datasets commonly used in KV Cache optimization, followed by a presentation of frequently used evaluation metrics.
6.1 Datasets
Long context benches Currently, there are several benchmarks that rely on extracting information from extremely long texts to answer questions. These benchmarks typically require models to read substantial reference document, often containing 4,000 to 20,000 tokens, and then respond to questions. In some cases, the longest texts may even approach 200,000 tokens. Typical examples are LongBench (Bai et al., 2023), ZeroSCROLLS (Shaham et al., 2023), L-Eval (An et al., 2023), BAMBOO (Dong et al., 2024c), XLèbench(Ni et al., 2024), InfiniteBench (Zhang et al., 2024b), and LooGLE (Li et al., 2023). However, these benchmarks face challenges related model-specific knowledge requirements, fixed text lengths that are difficult to adjust, and the uncontrollable and subjective nature of content generated by the models.
Key retrieval The other method for evaluating the ability of models handle extremely long texts involves directly extracting specified key from unrelated context. This approach simpler, more flexible, and more controllable. Importantly, it does not rely on the model's existing knowledge. Examples are Needle in Haystack (Kuratov et al., 2024), Passkey Retrieval (Mohtashami & Jaggi, 2023), and RULER (Hsieh et al., 2024). However, critics argue that this method is overly simplistic. Examples of these tasks can be found in Appendix Figure 4 and Figure 5.
Few-shot Testing In addition to datasets specifically designed for long texts, the length of traditional shorter test sets can be extended through a few-shot (Brown al., 2020) format or by simulating multi-turn dialogues, in order to test the model's capabilities with long texts. However, long-text tests based on few-shot, texts at greater distance only serve as reference and do not contain information that the model needs to extract or conditions for inference, so the reference value of the results is limited.
6.2 Evaluation Metric
Per Token GPU-Memory Usage For KV Cache, the most intuitive optimization indicator would be the memory space occupied by each token. The LLaMA2-7B model, as a typical example, theoretically occupies 0.5MB of memory for each KV Cache entry. Please note that when measuring this indicator rigorously, the fragment space generated by the token also be taken into account, that is, it is best to measure according to the actual memory occupancy, rather than a value calculated through a string of parameters.
Throughput and Latency Throughput and latency are important indicators for measuring the time efficiency of a model. Throughput, usually measured in tokens per second (token/st s), represents how many new tokens the model can generate per second. The higher the throughput, the better the model efficiency. In the Decoding phase, latency usually considered to be the time required to generate each new token, which is the reciprocal of the throughput, typically in milliseconds.
The Perplexity (PPL) is: for each token, the model calculates the natural logarithm likelihood value of the probability distribution predicted based on its previous tokens, takes the average, and then calculates the value as the exponent of e, mathematically given by Formula 3, where ANLL refers to the average natural logarithm likelihood.
Perplexity
1 ANLL
N
logp X1 (x,))_..x;)))),, x;-1), PPL ANLL
(3)
N
9

---

Published as a conference paper at COLM 2024
PPL can provide rough reference for the performance changes of the model. If PPL rises sharply, it usually means that the model's s ability has significantly decreased, such as completely losing language ability, etc.
Key Takeaways
This review, following the footsteps of prior work, takes a closer look into KV Cache optimization, uncovering its complexities and proposing strategies for its optimization. We f hope to propose some insights and suggested directions for future research that are not just reflections of current trends but also an invitation to explore the uncharted territory of LLMs.
Principles of KV Cache Optimization: At the core of optimizing KV Cache lies the principle of reducing memory consumption. This can be achieved by further compressing 'K' (Keys) or "V' (Values) in the KV pairs. Techniques to compress these components directly impact the efficiency of the models, especially in terms of memory usage and processing speed.
Trade-offs in Deletion vs. Compression: Whether to delete less important KV pairs to save memory or to compress the KV Cache without deletion remains an open question. While deletion might offer immediate memory relief, it could potentially compromise the model's performance. In contrast, better compression techniques strive to retain information integrity while reducing memory footprint.
Extremes in KV Cache Management: A more radical approach could involve storing the KV Cache externally, possibly different storage medium. This method would transform KV Cache management into a retrieval challenge, where the relevant KV pairs are fetched and reintegrated into the model as needed. While this could reduce memory usage on primary devices, it would introduce complexities in retrieval and integration processes.
These discussions point towards an evolving future where storage and retrieval technologies might become as crucial as the computational models themselves. Innovations in how KV Cache managed, stored, and accessed could open up new avenues for making LLMss more efficient and versatile.
Future Directions in Storage and Retrieval Technologies:
8 Conclusion
In this review, we highlighted the significance and the multifaceted nature of optimizing KV Cache in Large Language Models (LLMs). This review traversed through a variety of methods, from the training and deployment stages to post-training optimizations. Each method, whether it be the architectural changes in the pre-training phase, framework optimizations during deployment, or dynamic strategies like eviction and quantization in the post-training phase, offers unique insights into mitigating the challenges posed by the nature. Moreover, the exploration of different evaluation metrics for long-text performance underpins the importance of a balanced approach that considers both efficiency and model capabilities. As the field continues to evolve, it is clear that the optimization of KV Cache will remain a critical area of focus, offering a pathway towards more efficient and environmentally responsible use of LLMs.. We hope this review can be roadmap to guide learners venturing through this dynamic and rapidly progressing field.
KV Cache's memory-intensine
Acknowledgments
We sincerely appreciate the valuable feedback provided by all reviewers during the review process, as well as the efforts of the ethics area chairs and program area chairs. This work was supported by the National Natural Science Foundation of China (No. 62306216), the Natural Science Foundation of Hubei Province of China (No. 2023AFB816), the Fundamental Research Funds for the Central Universities (No. 2042023kf0133).
10

---

Published as a conference paper at COLM 2024
References
Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant J Nair, Ilya Soloveychik, and Purushotham Kamath. Keyformer: Kv cache reduction through key tokens selection for efficient generative inference. arXio preprint ar arXio:2403.0905- 2024.
Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi-head checkpoints. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 4895-4901, Singapore, December 2023, Association for Computational Linguistics. doi: 10.18653/v /vl 2023.emnlp-main.n 298. URL
org/ 2023. emnlp-maine mooommain... 298.
Chenxin An, Shansan Gong, Ming Zhong, Mukai Li, Jun Zhang, Lingpeng Kong, and Xipeng Qiu. L-eval: Instituting standardized evaluation for long context language models. CoRR, abs/ /307 11088, 2023. doi: 10.48550/ ARXIV.2307.1008. URL https://don org/10. 48550/arXiv.. 2307.11088.
Simran Arora, Sabri Byuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, Dylan Zinsley, James Zou, Atri Rudra, and Christopher Ré. Simple linear attention language models balance the recall-throughput tradeoff, 2024.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench: A bilingual, multitask benchmark for long context understanding. CoRR, abs abs/2208.14508, 2023. doi: 10.48550/ ARXIV 14508.
1044855/AAXXV.2308...
URL https: //tp:///oiiio. org/10..///.oo www50///5.i......
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document trans- former, 2020.
William Brandon, Mayank Mishra, Aniruddha Nrusimha, Rameswar Panda, and Jonathan Ragan-Kelley. Reducing transformer key-value cache size with cross-layer attention. CoRR, abs/ / 2ttp://455.19999 12981, 2024. doi: 10.48550/ ARXIV URL https://dot org/10. 48550/arXiv. 2405. 12981.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL http:s: neuries..... cc/pscer/pperrcc/ patees//pppr//2220 pdf.
Alexis Chevalier, Alexander Wettig, Anirudh Ajith, and Danqi Chen. Adapting language models to compress contexts. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 3829-3846, Singapore, December 2023. Association for Computational Linguistics. doi: URL https: //tp:///allaaaoogy/...o 2223. argg/223..mmnp-mmllll.. amnlp-main.
10.18653/v1 httt:////111222.m./mmaaaam 232.
Giulio Corallo and Paolo Papotti. Finch: Prompt-guided key-value cache compression, 2024.
URL httpps:/aaxxiv.or//aassss 0ttp:///22..00....... 00167.
DeepSeek-Al, Aixin Liu, Bei Feng, Bin Wang, Bingxuan Wang, Bo Liu, Chenggang Zhao, Chengqi Deng, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, Hao Zhang, Hanwei Xu, Hao Yang, Haowei Zhang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Li, Hui Qu, J. I.. Cai, Jian Liang, Jianzhong Guo, Jiaqi Ni, Jiashi Li, Jin Chen, Jingyang
11

---

Published as a conference paper at COLM 2024
Yuan, Junjie Qiu, Junxiao Song, Kai Dong, Kaige Gao, Kang Guan, Lean Wang, Lecong Zhang, Lei Xu, Leyi Xia, Liang Zhao, Liyue Zhang, Meng Li, Miaojun Wang, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Mingming Li, Ning Tian, Panpan Huang, Peiyi Wang, Peng Zhang, Qihao Zhu, Qinyu Chen, Qiushi Du, J. Chen, R. L. Jin, Ruiqi Ge, Ruizhe Pan, Runxin Xu, Ruyi Chen, S. Li, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shaoqing Wu, Shengfeng Ye, Shirong Ma, Shiyu Wang, Shuang Zhou, Shuiping Yu, Shunfeng Zhou, Size Zheng, Tao Wang, Tian Pei, Tian Yuan, Tianyu Sun, W. L. Xiao, Wangding Zeng, Wei An, Wen Liu, Wenfeng Liang, Wenjun Gao, Wentao Zhang, X. Q. Li, Xiangyue Jin, Xianzu Wang, Xiao Bi, Xiaodong Liu, Xiaohan Wang, Xiaojin Shen, Xiaokang Chen, Xiaosha Chen, Xiaotao Nie, and Xiaowen Sun. Deepseek-v2: A strong, economical, and efficient mixture-of-expent language model. CoRR, abs/ 2405.04434, 2024. doi: 10.48550/ ARXIV.2405.442. URL https: //doi. org/1.ggg100 48550/ arxiv. 2405. 04434.
Alessio Devoto, Yu Zhao, Simone Scardapane, and Pasquale Minervini. A simple and effective 1n norm-based strateg for KV cache compression. CoRR, abs//406.11430, 2024. doi: 11445500AAXXV.240..1111
URL https: //doi. http://ooooogg/////// org/10..////o 48550/ 2406. 11430. 11430.
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 LLM inference. CoRR, abs/2402.09399 2024a. doi: 10.48550/ ARXIV.4402009999 URL https://doi.org 1r 0400///22000////..222222222 2932.
Shichen Dong, Wen Cheng, liayu Qin, and Wei Wang. Qaq: Quality adaptive quantization for Iim kv cache. arXiv preprint ar Xio:2403.046443, 2024b.
Zican Dong, Tianyi Tang, Junyi Li, Wayne Xin Zhao, and Ji-Rong Wen. BAMBOO: A comprehensive benchmark for evaluating long text modeling capacities of large language models. In Nicoletta Calzolari, Min-Yen Kan, Veronique Hoste, Alessandro Lenci, Sakriani Sakti, and Nianwen Xue (eds.), Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pp. 2099, Torino, Italia, May 2024c. ELRA and ICCL. URL https: https:://aclanthoo.gg org/ 2024. 1rec-main. 188.
Luciano Floridi and Massimo Chiriatti. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 30:681-694, 2020.
Qichen Fu, Minsik Cho, Thomas Merth, Sachin Mehta, Mohammad Rastegari, and Mahyar Najibi. Lazyllm: Dynamic token pruning for efficient long context Ilm inference, 2024. URL https: /ttpss////xxvv///e org/ abs/ 220/. 14057.
Bin Gao, Zhuomin He, Puru Sharma, Qingxuan Kang, Djordje Jevdjic, Junbo Deng, Xingkun Yang, Zhou Yu, and Pengfei Zuo. Cost-efficient large language model serving for multi- turn conversations with cachedattention. In Saurabh Bagchi and Yiying Zhang (eds.), Proceedings of the 2024 USENIX Annual Technical Conference, USENIX ATC 2024, Santa Clara, CA, USA, July 10-12, 2024, pp. 111-126. USENIX Association, 2024. URL https: //www. www.ws.eei....ee.eee hwtp:///wooeeeeeeeeeaaaat/psaaaa balnggaaaabniioos-eeeeoeeeee bin-cost.
Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive KV cache compression for 1lms. CoRR, 2310.0000, 2023. doi: 10.48550/ 11.8555//ARXI.331111 ARXIV.2310.01801. URL https://doi: org/10. 48550/arXiv..311 01801.
Daniel Goldstein, Fares Obeid, Eric Alcaide, Guangyu Song, and Eugene Cheah. Goldfinch: High performance rwkv transformer hybrid with linear pre-fill and extreme kv-cache compression, 2024. URL https::/arxxi.orr//bbaee
12077.
Albert Gu and Tri Dao. Mamba: Linear-time sequeee modeling with selective state spaces, 2024. URL https: http://aaww..rrr/bb///...00/
Chi Han, Qifan Wang, Hao Peng, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. Lm-infinite: Zero-shot extreme length generalization for large language models, 2024.
12

---

Published as a conference paper at COLM 2024
Jiaao He and Jidong Zhai. Fastdecode: High-throughput gpu-efficient LLM serving using heterogeneous pipelines. CoRR, abs 1211111441,, 2024. doi: 10.48550/ AA00///AAAXX2222.1122222
URL h/dos://doi. org/10 48550/ 2403.
Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeht Michael W. Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length LLM inference with KV cache quantization. CoRR, 0/////1111.107/ 2024. doi: 10.48550/ ARXIV.2401.18079 URL https:://oi..rrr http:///oooor///.... http://oo...rr11...8888///////// 48550//axiv.....
2401 18079.
Cheng-Pingg Beeng-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? Xiv preprint ar Xio:2444.006654 2024.
Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. LLMLingua: Compressing prompts for accelerated inference of large language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, Pp. 13358 13376, Singapore, December 2023a. Association for Computational Linguistics. doi: 10.18653 (1186633v1/222 wtt.023..mmlpppppppp mainnmpmmai.825555 URL https://aclanthol..gg org/2023 mmnnp-mminn.. main.825.. 825.
Huiqiang Jiang, Qianhui Wu, Xufang Luo, Dongsheng Li, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. Longllmlingua: Accelerating and enhancing lims in long context scenarios via prompt compression. CoRR, abs/2310.06884 2023b. doi: 10.48550/ /A/1V:221222200099 URL httph:tt///:oiorr///// 488554/a55Xii 2310 2310.06839.
Hongye Jin, Xiaotian Han, Jingfeng Yang, Zhimeng Jiang, Zirui Liu, Chia-Yuan Chang, Huiyuan Chen, and Xia Hu. LLM maybe longlm: Self-extend LLM context window without tuning. CoRR, 2bs12400.1,3 2024. doi: 10.48550 AAAT//22XXX222111122222.2 URL
https://doi, 0rg/1.. 411.0.4855//// 240.1.....2......
Hao Kang, Qingru Zhang, Souvik Kundu, Geonhwa Jeong, Zaoxing Liu, Tushar Krishna, and Tuo Zhao. Gear: An efficient kv cache compression recipefor near-lossless generative inference of Ilm. ar preprint arXiv:2403.05527 2024.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5156-5165. PMLR, 13-18 Jul html.
2020. URL https: http://ppooeeeen..c/ec...oo
Yuri Kuratov, Aydar Bulatov, Petr Anokhin, Dmitry Sorokin, Artyom Y. Sorokin, and Mikhail Burtsev. In search of needles in 11m haystack: Recurrent memory finds URL
what iims miss. CoRR, abs/ 2400..0790, 2024. doi: https://doi org/10. 48550/arXin http:/avvvv.....1..2....
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 23, pp. 611-626, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400702297. doi: 10.145//600006.311316 URL https://doi. org/ /0. 1145/3600006 3613165.
Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. Infinigen: Efficient gen- erative inference of large language models with dynamic KV cache management. In Ada Gavrilovska and Douglas B. Terry (eds.), 18th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2024, Santa Clara, CA, USA, July 10-12, 2024, pp. 155-172. USENIX Association, 2024. URL https::/www.u.. wwwp///wwww..wiixoc///// org/ www.//eene/c///ee/eeeeeeeooeeeee presentation/les lleee..
Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. Loogle: Can long-context language models understand long contexts? CoRR, abs/ 2311..499,, 2023. doi: 10.48550/ ARXTV22311 1.499999.. 04999. URL httos:///oi.... org/10.g/e/// 48550/ ariiv. 2311.04939.
13

---

Published as a conference paper at COLM 2024
Bin Lin, Tao Peng, Chen Zhang, Minmin Sun, Lanbo Li, Hanyu Zhao, Wencong Xiao, Qi Xu, Xiafei Qiu, Shen Li, Zhigang Ji, Yong Li, and Wei Lin. Infinite-llm: Efficient LLM service for long context with distattention and distributed kvcache. CoRR, abs abs/2401.02665 2024. doi: 10.48550/ ARXIV22401 1.0669. URL https://dol .rrg//rr//// 48550/arXiv. 2401. .26669.
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the per- sistence of importance hypothesis for Ilm kv cache compression at test time. In A. Jh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Ad- vances in Neural Information Processing Systems, volume 36, Pp. 52342-52364. Curran Associates, Inc., 2023. URL https: httpps://ppooceeddigg....s neurips cc/paper www.fillll/ppee /tlles/paper2023// .df.
Amirkeivan Mohtashami and Martin Jaggi. Landmark attention: Random-access infinite context length for transformers. CoRR, a 2023. doi: 10.48550/ ARM/V.23RX 16300. URL https: /tt.//doi..oo wtt..rr......./rr.iii...... 2305. 16380.
Jesse Mu, Xiang Li, and Noah D. Goodman. Learning compress prompts with gist tokens. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL http://paperrr nips. wwps.cc/paper wwtppppp...llleeppeeeeeeeeeeeeee files/paper/ 2023/hash/3d7220 (altashh3d7776dcc7ff111 4aaad 54475445522268----- hateee222bo--bstttttt-ooooeree
html.
Piotr Nawrot, Adrian Lancucki, Marcin Chochowski, David Tarjan, and Edoardo M. Ponti. Dynamic memory compression: Retrofitting llms for accelerated inference. CoRR, abs/24403006636, 2024. doi: 10.48550/ 00085000/AXXV2243000066666 URL https://doi.ors org/10. 48550/arXiv. 2403. 09636.
Xuanfan Ni, Hengyi Cai, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, and Piji Li. XIabench: A benchmark for extremely long context understanding with long-range dependencies, 2024. URL https:
05446.
Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers are multi-state mns. Xiv preprint arXiv:2401.06104 2024.
Jianhui Pang, Fanghua Ye, Derek Wong, and Longyue Wang. Anchor-based large language models. CoRR, abs 2bbb//2440007666. 2024. doi: 10.48550/ ARXIV.2400.07616. URL https: //doi. www/orgg///.. 48550/ 2402. 27611
Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Bi- derman, Huanqi Cao, Xin Cheng, Michael Chung, Leon Derczynski, Xingjian Du, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Jiaju Lin, Krishna Sri Ip- sit Mantri, Ferdinand Mom, Atsushi Saito, Guangyu Song, Xiangru Tang, Johan Wind, Stanislaw Wozniak, Zhenyuan Zhang, Qinghua Zhou, Jian Zhu, and Rui-Jie reinventing rnns for the transformer era. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, Singapore, December 6-10, 2023, pp. 14048-14077. Association for Com- URL
Zhu. RWKV:
putational Linguistics, 2023a. doi: findings-emmlp.99 https::/doi.. http://dooooggg////// wtt../....//./////1....
188538816 /22233///222.... http://22......nneeee....
Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Jiaju Lin, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Krishna Sri Ipsit Mantri, Ferdinand Mom, Atsushi Saito, Guangyu Song, Xiangru Tang, Bolun Wang, Johan S. Wind, Stanislaw Wozniak, Ruichong Zhang, Zhenyuan Zhang, Qihang Zhao, Peng Zhou, Qinghua Zhou, Jian Zhu, and Rui-Jie Zhu. Rwkv: Reinventing mns for the transformer era, 2023b. URL https //txwaaaa.vv////////a//eae/aawa/ or org/abs// 2385. 13848.
14

---

Published as a conference paper at COLM 2024
Ruoyu Qin, Zheminn Li, Weiran He, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: kvcache-centric disaggregated architecture for Ilm serving, 2024. URL https::/arrtv..rg/abb////
00079.
Hyun rae Jo and Dongkun Shin. A2sf: Accumulative attention scoring with forgetting factor for token pruning in transformer decoder, 2024. URL https://arxiv. orggii..oorraeooooeoee.oo. /bss/
Luka Ribar, Ivan Chelombiev, Luke Hudlass-Galley, Charlie Blake, Carlo Luschi, and Douglas Orr. Sparq attention: Bandwidth-efficient LLM inference. CoRR, abs/2332.04988,, 2023. doi: 10.48550/ ARXTV URL https://dop org/10 48550/ 04985.
Konstantinos Roumeliotis and Nikolaos D. Tselikas. Chatgpt and open-ai models: A
preliminary review. Future Internet, 15(6), 2023a. ISSN 1999-5903, doi: 01330//f11500119.
URL https::t/// http://www/ppto www.mmdpi.coo com/ 1199995903115/////
Konstantinos Roumeliotis and Nikolaos D Tselikas. Chatgpt and open-ai models: A
preliminary review. Future Internet, 15(6):192, 2023b. doi: /ttss///oooorr/1.100077
$10439-023-03172--
Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision, 2024. URL https::/arxiv.orrt www.oogg//bb/a/eeeee/ 08608.
Uri Shaham, Maor Ivgi, Avia Efrat, Jonathan Berant, and Omer Levy. ZeroSCROLLS: A zero-shot benchmark for long text understanding. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguiitiic:: EMNIP 2023, pp. 7977-7989, Singapore, December 2023. Association for Computational Linguis- tics. doi: 10.18653 / 12/2/222.n2/mm 11223..idings-eee eaaess.mmllp..... URL https:://clanthhllogg www.ooggyoorg//g// org/ findings-emnlp. 536.
Wenqi Shao, Mengzhao Chen, Zhaoyang Zhang, Peng Xu, Lirui Zhao, Zhiqian Li, Kaipeng Zhang, Peng Gao, Yu Qiao, and Ping Luo. Omniquant: Ommidirectionally calibrated quantization for large language models. CoRR, abs/ 1301. 2023. doi: 10.48550/
ARXIV.2308.13137, ÜRL https: wrw.:i....r/ee.. 48550/ arxiv. 2308. 13137.
Noam Shazeer. Fast transformer decoding: One write-head is all you need. CoRR, 021550.
abs/1911.02150, 2019. URL
Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High-throughput generative inference of large language models with a single GPU. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. html.
PMLR, 2023. URL httpp:://proceeeeeee mariiinnsmmmr.r....m mwl...rrres///2//hheen22
Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language 2ww0200022222 2023a. doi: 10.48550/ AAX1///2/AAI2...00022111.11 URL https: models. CoRR, 48550/arXii 2307 08621. //doi. www.oo/.////..
Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor transformer for large language models, 2023b. URL https: /ttp://axvvvvve//ee www..os.///...oo..oo.......o.os. hts//b//2300 2307 2007./88222. 08621.
Yutao Sun, Li Dong, Yi Zhu, Shaohan Huang, Wenhui Wang, Shuming Ma, Quanlu Zhang, Jianyong Wang, and Furu Wei. You only cache once: Decoder-decoder architectures for language models. CoRR, abs/ 22//2/405505554 2024. doi:
URL
https://doi. org/10. 48550/ att//v..vvvvv////////aee/aaaaaee 2405. 05254..
15

---

Published as a conference paper at COLM 2024
Hanlin Tang, Yang Lin, Jing Lin, Qingsen Han, Shikuan Hong, Yiwu Yao, and Gongyi Wang. Razorattention: Efficient kv cache compression through retrieval heads, 2024. URL
https://arxiv. wttp///://////////// httess//arxll.orr////////.... 15891.
Madhusudan Verma. Revisiting linformer with a modified self-attention with linear com- plexity. CoRR, abss/2101.102777 2021. URL https://arxiv.oor/bbb//22
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self- attention with linear complexity. CoRR, 2etp//000004466,, 2020. URL http:/tts///rriii.orgg abs/2006.041 04768.
Zheng Wang, Boxiao Jin, Zhongzhi Yu, and Minjia Zhang. Model tells you where to merge: Adaptive kv cache merging for Ilms on long-context tasks, 2024. URL https: //arxiv.org/ /aa/abb//222/// .8454..
Tianyu Wu, Shizhu He, Jingping Liu, Siqi Sun, Kang Liu, Qing-Long Han, and Yang Tang. A brief overview of chatgpt: The history, status quo and potential future development. IEEE/CAA Journal of Automatica Sinica, 1025):112--1136, 2023. doi: 10.1109/JAS.200 123618.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient stream- ing language models with attention sinks, 2023.
Yuhui Xu, Zhanming Jie, Hanze Dong, Lei Wang, Xudong Lu, Aojun Zhou, Amrita Saha, Caiming Xiong, and Doyen Sahoo. Think: Thinner key cache by query-driven pruning, 2024. URL https: / //axxiv http.//w.rr//bb//2../2222
Dongjie Yang, Xiaodong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. Pyra- midinfer: Pyramid KV cache compression for tigh-throughput LLM inference. CoRR, abs/2400.125322, 2024a. doi: 0005500/AXXI..44552222222 URL 48550/arKiv. 2405. 12532.
June Yong Yang, Byeongwook Kim, Jeongin Bae, Beomseok Kwon, Gunho Park, Eunho Yang, Se Jung Kwon, and Dongsoo Lee. No token left behind: Reliable kv cache compression via importance-aware mixed precision quantization. arXiv preprint arXiv:2402.18096, 2024b.
Yao Yao, Zuchao Li, and Hai Zhao. Sirllm: Streaming infinite retentive LLM, 2024. URL https://don org/10 /0000000. 48550/ 38550/arXivv 2405. 2528.
Lu Ye, Ze Tao, Yong Huang, and Yang Li. Chunkattention: Efficient self-attention with prefix-aware KV cache and two-phase partition. CoRR, ab0.2.00.,, 2024. doi: 10. 48550/ARXIV.2402.15222
URL https://dol org/10.. 100..4445/////...24422.2 152222
Howard Yen, Tianyu Gao, and Danqi Chen. Long-context language modeling with parallel context encoding. CoRR, abs/ 0bbs/2240.116111 2024. doi:
URL
https://doi. org/10. 48550/ 2402. 16617.
Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for Transformer-Baat Based generative models. In 16th USENIX Symposium
Operating Systems Design and Implementattin (OSDI 22), pp. 521- 538, Carlsbad, July 2022. USENIX Association. ISBN 978-1-9391333-88-1 URL https: //www. usenix. org/ wttp://cccfccccccccoeoooooo osde /tt.eerrreeeeeeeeeeeeeeeeeeaaaaa
Hao Yu, Zelan Yang, Shen Li, Yong Li, and Jianxin Wu. Effectively compress KV heads for LLM. CoRR, abs/2406.07056. 2024. doi: 10.48550 AAt////RXXX22200006666666 URL https: //doi.org/11 48550/arXiv. 2406. 07056.
Yuxuan Yue, Zhihang Yuan, Haojie Duanmu, Sifan Zhou, Jianlong Wu, and Liqiang Nie. Wkvquant: Quantizing weight and key/ /aauee cache for large language models gains more. CoRR, awtpab//s.2a. 1202, 2024. doi: 10.48550/ ARXIV.2402.12063 URL https:
org/10. 48550/ /05500/aXXiv 2402. 12065.
16

---

Published as a conference paper at COLM 2024
Michael Zhang, Kush Bhatia, Hermann Kumbong, and Christopher Ré. The hedgehog & the porcupine: Expressive linear attentions with softmax mimicry. CoRR, /bbb/2400004447, 2024a. doi: (0.48550/ARXVV224022.. 04347.
URL nttps:://oil org/10 48550/arriiii 2402.
Xinrong Zhang, Yingfa Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Khai Hao, Xu Han, Zhen Leng Thai, Shuo Wang, Zhiyuan Liu, and Maosong Sun. oobench: Ex- tending long context evaluation beyond 100k tokens. CoRR, 22022..2723, 2024b. doi: 10.48550/ AROp://222XX12211333
URL htttps:///ol org/10. 48551.045/////iii 2402. 13718.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark W. Barrett, Zhangyang Wang, and Beidi Chen. H2O: heavy-hitter oracle for efficient generative inference of large language models. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL http: /ttpp//aapeeeee//aa/eeeeeeeeese/ nips. coos.cccppppe files/paper/ 557 (
-etrrrff--bbttrtrt Abstract- html.
A Popular Models With GQA
In table 2, we've showcased that how popular models applied GQA/MQA. For each metrics:
GQA: Indicates whether the model uses the GQA method.
MoE: Indicates whether the model is Mixture of Experts model. If yes, it's represented as "Total Experts (Activated Experts)". For example, Mixtral utilized out of 8 experts per token, it's showcased as 8(2).
PC: Total parameter count, including parameters from Attention, FFN, LayerNorm or RMSNorm, Embedding, and LM-Head.
LC: Number of layers in the model.
HD: Hidden layer dimension. Note that this dimension isn't necessarily the same as the gkv vectors dimension. For example, Gemma-7b uses a 3072x4096 matrix to map 3072-dimensional / to 4096-dimensional qkv.
2y and flg: Number of attention heads and average number per layer of KV heads. The "average" is necessary here due to the Deci-LM use different ng value across different layers.
SjıK and Skv: Embedding size (in bytes, 6float16 data type) and corresponding KV Cache increment per token.
F/A: Represents the ratio of parameters in the Feed-Forward Network (FFN) layer to those in the Attention layer. Notably, in models that do not use GQA, this value tends to be around 2. However, in models employing GQA, it typically increases to the range of 3.5 to 5. For MoE models, this is calculated by multiplying the F/A value of single expert with the activate experts counts.
R: Represents the ratio of the KV Cache size generated for each token to the size of the embedding vector. A higher ratio indicates that the information for this token has been expanded by a greater factor. Notably, when using the GQA method, this value is significantly lower compared to non-GQA methods, implying that the information produced relatively compressed.
B Dataset Examples
For Passkey-retrieeal and Haystack, one example is provided for each benchmark, which can be found in Figure 4 and Figure 5.
17

---

Published as a conference paper at COLM 2024
Model
GQA
MoE
PC
LC
HD
11
Mgg
SHS
SKV
F/A
R
Grokl
Yes
8(2)
314B
64
6144
48
12K
163K
6*2
13
DBRX
Yes
16(4)
132B
40
6144
48
12K
163K
2.06*4
13
Gemma
No
8.5B
28
3072
16
16
6K
468K
4.5
75
Gemma
Yes
2.5B
18
2048
8
4K
18K
9.6
4.5
DeciLM
Yes
7.0B
32
4096
32
2.1
8K
34K
4.93
4.2
DeciLM
Yes
5.7B
32
4096
8
1.6
8K
25K
3.84
3.1
Phi-2
No
2.8B
32
2560
32
32
5K
327K
3
64
Deepseek
No
66(8)
16.4B
28
2048
16
4K
229K
1+0.5%
56
Q.en1.5
Yes
72B
80
8192
64
16K
327K
4.7
20
1.e
No
61(5)
14.3B
24
2048
16
16
4K
197K
2+0.5*4
48
Qwnl1.5
No
14.2B
40
5120
40
10K
819K
2.01
80
Qwen1.5 1.5
No
7.7B
32
4096
32
32
8K
524K
2.01
64
Qwen1.5
No
1.8
24
2048
16
4K
197K
2.01
48
Yi
Yes
34B
60
7168
56
14K
245K
3.75
18
Yi
Yes
8.8B
48
4096
32
8K
98K
3.58
12
Yi
Yes
6.0B
32
4096
32
8K
65K
3.58
8
Mixtral
Yes
8(2)
47B
32
4096
32
8K
131K
4.2*2
16
Mistral
Yes
7.2B
32
4096
32
8K
131K
4.2
16
GLM2/3
Yes
6B
28
4096
32
8K
28K
4.72
3.5
LLaMA2
Yes
69B
80
8192
64
16K
327K
4.7
20
LLaMA2
No
13B
40
5120
40
40
10K
819K
2.02
80
LLaMA2
No
6.7B
32
4096
32
32
8K
524K
2.01
64
Table 2: The current state of popular open-source LLM using the GQA method, along with their approximate parameter counts.
There is an important info hidden inside lot of irrelevant text. Find it and memorize them. will quiz you about the important information there.
prefix filler
The grass is green. The sky is blue. The sun is yellow. Here we go. wo. There and back again. (repeat for N times)
The pass key is <PASS KEY> Remember PASS KEY the pass key.
suffix filler
The grass is green. The sky is blue. The sun is yellow. Here we There and back again. (repeat for M times)
What is the pass key? The pass key
Figure 4: Prompt format for passkey retrieval. (<PASS KEY> is a 5-digit number.)
18

---

Published as a conference paper at COLM 2024
Mary moved the bathroom. john went the hallway
Input Contoxt
Chronicles
moved Chroridles outide apan, layS ladon ga remeplar predecessors, story rans mppoyinng same milltary pized eqainst imperial
bethroom.Vall VaarroomiViliiii batrefeli commonly
tactical @-0 playing came developed Sega
Released anuary in] apan,
and
first game nation curing Second Europan
tollows Nameless
who pertorn secret operatons
Chronicles les Valkyria Chronicles
fan lation
compatible with game's excanded edition rokaased in Meli
tranchise divellamenn Vallera
ayStation
hallway, previous Valkytra
Chronicles tactical role - playing sake part in miss ons against enemy forces thruugh book @ like panels animated character portraits...
gamess,
game where players control milltary
Question
Where Mary?
Bathroom
Figure 5: Example for Needle in Haystack task. Facts are inserted in the sentences of irrelevant text
C Other Methods
In addition to the above methods, there are also some methods that modify the Attention mechanism to completely eliminate KV Cache. Furthermore, by directly compressing the prompt or the embedding, the length of KV Cache can also be reduced by decreasing the number of tokens.
C.1 Transforrans
Katharopoulos et al. (2020); Wang et al. (2020); Verma (2021) proposed a linear attention mechanism. By removing the sof tmax function and slightly adjusting Wigkoy/ the computa- tional complexity of the Attention part in the Transformer is transformed from quadratic to linear, thereby achieving an inference speed consistent with Recurrent Neural Networks (RNNs), and totally eliminate the KV Cache. Other popular Linear-Transformers, mainly RNN-like or SSM models, includes RetNet (Sun et al., 2023b), RWKV (Peng et al., 2023b), Mamba (Gu & Dao, 2024), etc.
Zhang et al. (2024a); Arora et al. (2024) are some improvements to linear attention. These include the use of naive Attention mechanisms close range, and the optimization of the performance of linear Transformers through Spiky and Monotonic Weights.
C.2 Prompt and Embedding Engineering
Chevalier et al. (2023) proposed to use summary vectors for compressing history informa- tion. It concatenates the summary vectors long segments and train the model to gather information from previous embedding.
Mu et al. (2023) applies a special attention mask. The gist token is inserted between instructions and inputs, acts as bridge for transferring instruction information to inputs and thus forcing gist token to compress information.
LLMLingua (Jiang et al., 2023a) uses a budget controller, an iterative token-level compression algorithm and a small model estimate which token important. LongLLLMinggu (Jiang et al., 2023b) further improves LLMLingua in long context scenarios.
19


Reviews:
[{"review_id": "5xe3lSUDUB", "reviewer": "Reviewer_uKZX", "summary": "This paper presents a review of KV-caching techniques for Decoder-only LLMs, describing methods and strategies pertaining to multiple steps along the life of a model, as well as briefly discussing evaluation metrics and proposing avenues for future work. Overall, the work is timely and necessary, and there will definitely be benefits for researchers new to this topic who choose to read it instead of (or before) diving into the growing literature.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1: The non-core sections are substantially weaker. There's a noticeable disconnect at the 5-6 section border\n\nThank you for your valuable feedback. The primary goal of Section 6 was to provide beginners with an understanding of the commonly used datasets and metrics for KV Cache optimization. In the next version of our paper, we will restructure the content by reducing and moving Section 6 to the appendix. Additionally, we will offer a more detailed discussion of the results table and integrate the content from Appendix C into the main body of the paper. We will also enhance the logical flow between sections.\n\n## W2&Q1: Does $p_i$ denote a distribution or a single probability\n\nAs stated in Section 2, $p_i \\in \\mathbb{R}^V$ denotes a distribution, not a single probability.\n\n## Q2: how do $𝑛_ℎ$ combination weights result in $𝑛_ℎ$ combinations?\n\nAs explained in section 3 in page 3, in MQA, all heads share the same Key and Value matrices, while each head retains its own set of Query parameters. Therefore, for $n_h$ heads, there are $n_h*1=n_h$ different QKV combinations.\n\n## Q3: In Section 3, what's the correct formula?\n\nWe apologize for the typo. The correct formula is:\n$$\n\\eta = \\frac 12 \\cdot \\left( 1 + \\frac{n_g}{n_h} \\right)\n$$\nwhere the weight of the queries and the output projection layer remains unchanged, but the Key and Value matrices are reduced to \\($\\frac{n_g}{n_h}$\\) of their original size.\n\n## W3 :Some illustrations is confusing and inconsistent\n\nThank you for your feedback. The purpose of Figure 1 is to provide a roadmap to help readers gain a clearer understanding of the overall structure of the paper. Our paper unfolds in a chronological order of LLM: (1) In the training stage, we introduce the KV Cache compression methods that can be used during model pre-training. These methods are usually the most effective, but are not suitable for modifying existing models with low computational power. (2) In the deployment stage, we discuss the use of different frameworks to optimize the use of KV Cache which do not require significant modifications to the KV Cache itself but can significantly enhance its efficiency. (3) In the post-training stage, we introduce a large number of on-time optimization methods for KV Cache.\n\nWe will improve the illustrations to provide more clarity and detailed explanations.\n\n## W4: Grammar\n\nWe will thoroughly optimize and proofread the presentation to address the grammatical errors.", "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": "* The topic is relevant and in need of a review.\n* The paper can be of use to both practitioners wondering which strategy to pursue in the model they're training and for newcomers who want to design the next shiny KV caching technique.\n* The method-focused core of the review (sections 3--5) is well-structured and well-balanced among the importance and \"meat\" in the various sub-sub-topics. The introduction is also good.", "reasons_to_reject": "* The non-core sections are substantially weaker. \"Evaluation\" (S.6) is mostly unnecessary and the space used for it could have been better spent on covering more methods, extending the descriptions for some, or integrating interesting bits from Appendices, mostly C. Not only is S6 describing at length well-known resources, it does not connect back to any of the methods described in the core sections, and the results table isn't referred to, let alone analyzed. This is followed by a \"take-aways\" section (S7) which does not follow comfortably from the preceding ones. Overall, there's a noticeable disconnect at the 5-6 section border.\n* Section 2 (Preliminaries and Notation(s)) is a good idea but not executed carefully enough (see below).\n* While some illustrations (Fig. 2,3) are useful and illustratory, Figure 1 is mostly confusing and inconsistent. It does not lend intuition of the topic or set expectations for the survey's contents.", "questions_to_authors": "### Questions\n* In S2, does $p_i$ denote a distribution, as suggested twice, or a single probability, as suggested once and inferred by convention?\n* In S3, how do $n_h$ combination weights result in $n_h$ combinations? It feels like an entire dimension is absent in the former.\n* In S3, setting $n_g$ to $n_h$ in the $\\eta$ equation results in 1.5, which cannot be true (it needs to be 1). What's the correct formula?\n\n### Required fixes\n* Please refrain from personifying models - \"understanding\" in line 4 of the intro should be changed. Especially since this is a didactic work which may be used in introductory classes.\n\n### Grammar and Suggestions\n* There are some foci of grammatical errors - four in the last three lines of the first intro paragraph, the caption for figure 2, \"utilize(s)\"in p.5, \"quer(y/ies)\" in p.6. The last sentence of the intro is not understandable.\n* Appendices A and B look useful, you should probably alert the reader to their existence in the main text.\n* The transpose notation in eq. (1) and (2) is not the standard \"top\" but a cross, please change.\n* Please don't call things \"horrible\" (top of S4). \"undesirable\" would be more suitable.\n* In p.5, *Static policies* paragraph, it seems like Xiao et al. and Han et al. *find* rather than *suggest* (unless they really only suggest, in which case somebody better run that analysis).\n* Last but not least. \"(the) KV cache\" is a noun phrase and shouldn't be hyphenated unless used as a modifier.", "extra_scores": {}}, {"review_id": "b8VBWaSINE", "reviewer": "Reviewer_q2wL", "summary": "This submission is a review of the compression methods of KV Cache. It organizes existing works in chronological order, including the training phase, deployment phase, and run-time phase with post-training compression. The training stage mainly involves some novel architecture designs, such as Multi-Query Attention (MQA), and Grouped-Query Attention (GQA). For the deployment-related techniques, this paper covers some system optimization like Paged Attention and DistKD-LLM. For the post-training optimization, several training-free methods are discussed, including Window Attention and Attention Sink. Besides, some pruning, and quantization methods are mentioned. Further, this paper summarises the datasets and evaluation metrics for the KV cache.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1: Lack of connections\n\nThank you for your suggestion. In fact, in Section 5.1, paragraph 5, we have discussed in detail how different works estimate the future significance of a specific token based on the historical information of attention weights, exploring their similarities and differences. This paper focuses on categorizing and summarizing different methods in detail. For eviction methods, we have decomposed them into two lines of approaches: static policies and dynamic policies, based on whether they use manual or dynamic methods to evict unnecessary tokens.\n\nWe will include the discussion of Attention Sink and Repetitive Attention Pattern in future versions and establish connections between different works within each category to enhance clarity and coherence. Besides, we will seek for more connections between methods. For example, methods like GQA and Eviction both focused on how to reduce the number of stored variables, making the information more condensed.\n\n## W2: The evaluation section falls short\nThank you for your suggestion. We have already listed the mainstream methods for testing ultra-long context capabilities in Section 6.1. Nevertheless, our current chapter layout indeed occupies too much space on common metrics that are less related to big KV Cache scenarios. In the next version, we will focus more on supplementing benches focused on long-text, since they are more relevant to evaluate the KV Cache compression. We will also add discussions on the current shortcomings of benches. The main content is an unresolved contradictions, that is, evaluation methods with long texts are often simple in form and task, due to the sparsity of critical information; evaluation methods that are complex in form and difficult in task are difficult to extend to sufficient lengths.\n\nMoreover, for methods mentioned in section 5, we provide a table describes the pros and cons of them.\n|Scenarios/Property|Quantization|Dynamic Eviction|Merging|Static Eviction|\n|-|-|-|-|-|\n|Short context|✓|✓|✓|✓|\n|Long context generation|✓|✓|✓|✓|\n|Long context retrieval|✓|✗|✓|✗|\n|Time efficiency|○|○|○|✓|\n|No extra training|✓|✓|○|✓|\n|Flash-Attn friendly|✓|○|✗|✓|\n|CPU friendly|✗|✓|✓|✓|\n|Needle-in-haystack|✓|✗|✓*|✗|\n\n✓ and ✗ refers to suitable or not. ○ refers to partially suitable or depends on the implementation. \\* means result reported by the paper. The ‘Merge’ in the table refers to a type of method that emerged in early April 2024, which merges different tokens' cache.", "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": "1. The review's structure is clear, covering multiple stages including pre-training, deployment, and run-time optimization, facilitating a comprehensive understanding.\n2. Both efficiency and model capacity, crucial aspects for KVCache, are thoroughly discussed, demonstrating a holistic approach to optimization.\n3. The paper provides four key takeaways for KV Cache optimization, Principles of KV-Cache Optimization, Trade-offs in Deletion vs. Compression, Extremes in KV-Cache Management and Future Directions in Storage and Retrieval Technologies. These insights offer valuable guidance for future research, highlighting important areas for further exploration and advancement.", "reasons_to_reject": "1. The primary reason for rejection is the lack of connections between different methods within the paper. While the taxonomy is structured around different stages, such as pre-training, deployment, and run-time optimization, there is a missed opportunity to highlight similarities and shared concepts among various methods. For instance, the Attention Sink and Repetitive Attention Pattern both emphasize the importance of focusing on specific tokens, yet this connection is not adequately explored or summarized in the review. As a review paper, it's crucial to provide a synthesis of such related ideas to enhance clarity and coherence.\n2. Despite claiming to introduce metrics for assessing LLMs' performance on long texts, the evaluation section falls short by only listing general and widely used metrics like memory usage, throughput, latency, and perplexity. The paper lacks a comprehensive assessment of different methods, failing to delve into specific metrics tailored to the nuances of long text processing. A more thorough evaluation framework is needed to effectively gauge the effectiveness of the reviewed methods and provide valuable insights for future research and development in this domain.", "questions_to_authors": "Please refer to the weaknesses. My main concern lies in the lack of in-depth analysis of similar methods.", "extra_scores": {}}, {"review_id": "U5m86GAlnL", "reviewer": "Reviewer_dhyD", "summary": "This paper provides a review of KV-cache optimization for LLMs. The reviews are grouped according to the stage when cache optimization is performed: training, deployment or post-training. Training-stage optimization mainly changes the model's architecture for efficient caching, deployment-stage optimization mainly studies better inference system, and post-training optimization mainly perform token eviction or quantization. Moreover, related datasets and evaluation metrics are also discussed.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1: This paper is mainly a literature review without empirical experiments exploring which methods are most effective in which scenarios\n\nThank you for your careful review. We would like to clarify that in the first paragraph of the second page, we divided the methods into pre-training, post-training, and deployment stages, and discussed the appropriate scenarios for each method.\nFor those with sufficient computational resources, methods like MQA and GQA are recommended. As listed in Appendix A, many organizations that can train a large language model (LLM) from scratch have successfully used GQA and MQA. For those with limited resources, methods in the post-training and deployment stages are more suitable.\nDuring the rebuttal period, we also created supplementary tables to help readers gain a deeper understanding of the different KV Cache optimization methods in next section.\n\n## W2: It would be nice to provide a table listing the advantages and disadvantages of different methods with suggestions on their best usage\n\nThank you for your suggestion. During the rebuttal period, we have added a supplementary table to compare different methods, highlighting their advantages and disadvantages along with suggestions for their best usage.\n\n| Scenarios / Property | Quantization | Dynamic Eviction | Merging |Static Eviction |\n|-|-|-|-|-|\n| Short context | ✓ | ✓ | ✓ | ✓ |\n| Long context generation | ✓ | ✓ | ✓ | ✓ |\n| Long context retrieval | ✓ | ✗ | ✓ | ✗ |\n| Time efficiency | ○ | ○ | ○ |  ✓ |\n| No extra training | ✓ | ✓ | ○ | ✓ |\n| Flash-Attn friendly | ✓ | ○ | ✗ | ✓ |\n| CPU friendly | ✗ | ✓ | ✓ | ✓ |\n| Needle-in-haystack | ✓ | ✗ | ✓* | ✗ |\n\n✓ and ✗ refers to suitable and not suitable. ○ refers to partially suitable or depends on the implementation. \\* refers to results reported within the paper. The ‘Merge’ in the table refers to a type of method that emerged in early April 2024, which merges the KV Cache of different tokens. This is a part that we added when we continued to maintain this work.\n\n## W3: Prompt compression techniques are quite related to this topic and related work should be discussed\n\nPlease refer to Appendix C where we have included a brief introduction of prompt, or embedding, compression techniques and related work. Besides, we will integrate the content from Appendix C into the main body of the paper for a more comprehensive discussion.", "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": "- Techniques on KV-cache compression are crucial for efficient deployment of LLMs.\n- A nice review is provided by this work, which may inspire more future research on this direction.\n- This work provides a good categorization of approaches on KV-cache compression, classified into training-stage, deployment-stage and post-training stage, which clearly describes how and when we can optimize the KV caches.", "reasons_to_reject": "- This paper is mainly a literature review without empirical experiments exploring which methods are most effective in which scenarios.\n- It would be nice to provide a table listing the advantages and disadvantages of different methods with suggestions on their best usage.\n- Prompt compression techniques are quite related to this topic and related work should be discussed.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nisnc13Eke", "reviewer": "Reviewer_mRjo", "summary": "This paper performs a literature review on optimizing KV-cache usage in LLMs. The paper is well written and ontology on classifying the current research and engineering effort is always welcome. While the topic is an important and active research area, I feel that the paper could have covered a rather deep review and discussion on the topic. The authors didn't discuss financial implications of different approaches while the title says 'Keep the Cost Down'.", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1: In depth discussion and review is missing since it is a survey paper. Work could be supplemented by experimental benchmarks\n\nThank you for your feedback. We have included an in-depth discussion review of the different methods explored in the Key Takeaways section. Besides, we have also provided our insightful perspective on this critical problem and pointed out promising potential future directions for the research.\n\nMoreover, we've conducted a needle-in-a-haystack test on the methods mentioned in the Post-Training Optimization section, as most of them did not test this in their paper. We also planned to add a section of the pros and cons of various methods in section 5. Results are as follows.\n\n| Scenarios / Property | Quantization | Dynamic Eviction | Merging |Static Eviction |\n|-|-|-|-|-|\n| Short context | ✓ | ✓ | ✓ | ✓ |\n| Long context generation | ✓ | ✓ | ✓ | ✓ |\n| Long context retrieval | ✓ | ✗ | ✓ | ✗ |\n| Time efficiency | ○ | ○ | ○ |  ✓ |\n| No extra training | ✓ | ✓ | ○ | ✓ |\n| Flash-Attn friendly | ✓ | ○ | ✗ | ✓ |\n| CPU friendly | ✗ | ✓ | ✓ | ✓ |\n| Needle-in-haystack | ✓ | ✗ | ✓* | ✗ |\n\n✓ and ✗ refers to suitable and not suitable. ○ refers to partially suitable or depends on the implementation. \\* refers to results reported within the paper. The ‘Merge’ in the table refers to a type of method that emerged in early April 2024, which merges the KV Cache of different tokens. This is a part that we added when we continued to maintain this work.\n\n## W2: The authors didn't discuss financial implications of different approaches while the title says 'Keep the Cost Down'\n\nThank you for suggesting another possible interpretation of our title. But here, our ‘cost’ is more inclined towards the consumption of performance, specifically in terms of memory, I/O bandwidth, and computational resources. While the KV Cache does indeed impact the financial cost of the model, the financial cost is also influenced by many factors unrelated to language models and subject to rapid changes. These are irrelevant to the issues we are concerned with, so we have not discussed this aspect.", "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": "The paper focuses important topic that is active and involving. Author attempt to cover approaches more broadly rather than depth.", "reasons_to_reject": "In depth, discussion and review is missing since it is a survey paper. Work could be supplemented by experimental benchmarks.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aybHeT34r6", "reviewer": "Reviewer_XM3o", "summary": "The manuscript presents an up-to-date overview of approaches for optimizing the KV-Cache, which is a method for speeding up, and reducing the memory load for LLMs.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1: The papers is in some places too condensed\n\nThank you for your careful review. Due to page limitations, we were unable to provide more detailed explanations in some sections. However, we plan to offer more extensive discussions and elaborations in the appendix in our future work. This will ensure that readers can access detailed information without compromising the overall structure and conciseness of the main paper.\n\n## Q1: Some acronyms are not explained: GQA (page 3), RAG (page 4), please consider explaining\n\nHere GQA refers to  Grouped-query Attention, and RAG refers to Retrieval-augmented Generation.\n\n## Q2&Q3: Typos and Presentation\n\nThank you for your suggestion. We will revise and optimize the expressions in the subsequent versions and conduct a more thorough proofreading to correct any typos.\n\n## Q4: Appendix A: \"Mixture of Experts model\" - please explain what is that\n\nIn the context of transformer models, a MoE(Mixture of Experts) consists of two main elements:\n\n- Sparse MoE layers are used instead of dense feed-forward network (FFN) layers. MoE layers have a certain number of “experts”, where each expert is a neural network. In practice, the experts are FFNs.\n- A gate network or router, that determines which tokens are sent to which expert.\nPlease refers to paper (<https://arxiv.org/pdf/2101.03961>) for more detailed explanations.\n\n## Q5: Appendix C 'Other methods' deserves to be a section in the body of the paper, and deserves more elaboration. If you get more pages for the paper, consider moving this section\n\nThank you for your invalueable suggestion. We will try to integrate the content from Appendix C into the main body of the paper for a more comprehensive discussion.\n\n## Q6：The following papers in the References section have no venue/publication data: Arora et al., Beltagy et al., Han et al. Please check completeness of the references\n\nWe will double check and revise these references in updated version.", "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": "A good and comprehensive overview to one of the most important technical aspects of modern LLMs. The introduction is reasonably detailed, and the review is well-structured. Also includes helpful diagrams. \nThis review can also be used for introducing new researchers to this topic.\n\nNotably, this is a very technical and complicated topic, and covering it within just 9 pages is a feat of compression (pun intended), but the authors also managed to include an evaluation section and neatly describe the logic of KV-Cache evaluations. Well done.", "reasons_to_reject": "The papers is in some places too condensed.", "questions_to_authors": "Some acronyms are not explained: GQA (page 3), RAG (page 4), please consider explaining.\n\nPage 4: \"but each time it only increases a little, which is a horrible property\" - the 'horrible' epithet is not helpful. The case is not 'horrible' but surely can be made more efficient. \n\nPage 7, a typo: \"obtains the ability to accumulates history\" -- should be 'accumulate'\n\nAppendix A: \"Mixture of Experts model\" - please explain what is that.\n\nAppendix C 'Other methods' deserves to be a section in the body of the paper, and deserves more elaboration. If you get more pages for the paper, consider moving this section. \n\nThe following papers in the References section have no venue/publication data: \nArora et al., Beltagy et al., Han et al. \nPlease check completeness of the references.", "extra_scores": {"ethics_concerns_details": "N/A"}}]

Author rebuttal:

Meta-review: The reviewers agree this paper is on a timely topic and seems to be very thorough, especially for a conference paper. The authors have promised to add some additional discussion and synthesize their different threads more closely, including adding a table to compare the methods in question. If they make these changes, the paper is clearly strong enough to accept.

[At least one review was discounted during the decision process due to quality]
Decision: Accept