CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Authors: Haoyun Jiang
Haolin li
jianwei zhang
Fei Huang
Qiang Hu
Minmin Sun
Shuai Xiao
Yong Li
Junyang Lin
Jiangchao Yao
Venue: ICML 2025 poster (2025)
Keywords: Large Lauguage Models
Acceleration
Long context
Primary area: deep_learning->large_language_models
TL;DR: We propose a simple method to reduce memory usage and decoding latency while maintaining performance in long-context LLM inference.

Abstract: Large language models (LLMs) have demonstrated strong capabilities in handling long-context tasks, but processing such long contexts remains challenging due to the substantial memory requirements and inference latency. In this work, we discover that certain attention heads exhibit sequential consistency in their attention patterns, which can be persistently identified using a coefficient-of-variation-based algorithm. Inspired by this observation, we propose CateKV, a hybrid KV cache method that retains only critical token information for consistent heads, thereby reducing KV cache size and computational overhead, while preserving the majority of KV pairs in adaptive heads to ensure high accuracy. We show the unique characteristics of our algorithm and its extension with existing acceleration methods. Comprehensive evaluations on long-context benchmarks show that, while maintaining accuracy comparable to full attention, CateKV reduces memory usage by up to $2.72\times$ and accelerates decoding by $2.18\times$ in single-sample inputs, and boosts throughput by $3.96\times$ in batch scenarios.

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Haoyun Jiang" 12
Haolin Li
Jianwei Zhang² Fei Huang? Qiang Hu' Junyang Lin Jiangchao Yao!
Minmin Sun
Shuai Xiao
Yong Li
Abstract
heads
Low accuracy
For consistent heads
Low
Pre-filling
Pre-filling
memory
Large language models (LLMs) have demon- strated strong capabilities in handling long- context tasks, but processing such long contexts remains challenging due to the substantial mem- ory requirements and inference latency. this work, we discover that certain attention heads ex- hibit sequential consistency in their attention pat- terns, which be persistently identified using a coefficient-of-vee ser--vvrrtionbaasee algorithm. Inspired by this observation, propose Ca a hy- brid KV cache method that retains only critical token information for consistent heads, thereby reducing KV cache size and computational over- head, while preserving the majority KV pairs in adaptive heads ensure high accuracy. We show the unique characteristics of our algorithm and its extension with existing acceleration meth- ods. Comprehensive evaluations on long-context benchmarks show that, while maintaining accu- racy comparable to full attention, V reduces memory usage by up to 2.72x and accelerates decoding by 2.18x in single-sample inputs, and boosts throughput by 3.96x in batch scenarios.
02
666
0.1
0.2
Decoding
KV pairs
Only retain orticca KV
Decoding
Query KV Eviction Algorithm
KV cache
(a)
Decoding
For all heads
memory
High
adaptive heads
High accuracy
Pre- -inliilling
Query
Retain most pairs
Query
(b) KV Retrieval Algorilum
Decoding
Context window
Observation window
KV cache
Query
Evicted KV pairs
KV peirs sitention
(c)
Figure 1: Comparison of KV eviction, KV retrieval, and our method. CateK employs hybrid KV cache method to reduce memory usage while maintaining high accuracy.
standing (Bairi et al., 2024; Jimenez et al., 2023). However, context lengths grow, the autoregressive nature of the mainstream LLM paradigm often leads to increased compu- tational costs, memory consumption, and thus the runtime, since we have to store and retrieve all key-value (K V) caches. For example, using the Llama-3-8B-mn S-n----nntcttte666 (Gradient, 2024b) model with FlashAttention, extending the context from 1K to 1M tokens increases inference latency by over 3000 times (Jiang et al., 2024). Therefore, accelerating LLM inference in long contexts is both essential and imperative.
1. Introduction
With rapid development of large language models (LLMs),
many generalist models support context windows of 128K
tokens or more (Achiam et al., 2023; Dubey et al., 2024;
Bai et al., 2023a; GLM et al., 2024b; Team et al., 2023;
Existing methods for inference acceleration of LLMs under long contexts can be categorized into two types: KV cache eviction and KV cache retrieval strategies. KV eviction strategies reduce the size the KV cache by systematically discarding KV pairs based on predefined policies (Xiao et al., 2023; Zhang et al., 2023; Li al., 2024; Cai et al., 2024). However, this usually suffers from significant accu- racy loss, as the removal of essential information without comprehensive contextual understanding adversely affects task performance. contrast, KV retrieval methods main- tain accuracy by preserving all KV pairs in the cache and
Abdin et al., 2024), enabling to effectively perform tasks like long-document question answering (Caciularu et al., 2023; Wang al., 2024), information retrieval (Zhang et al., 2024a; Zhu et al., 2023), and repository-level code under-
'CMIC, Shanghai Jiao Tong University Allibaba Group # Fudan University. Correspondence to: Jiangchao Yao <sunarker@ wwweerr@@@juuuu...c sjtu.edu.en>. Shuai Xiao <shuai.xsh ish& com..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

CateKV: On Sequential Consistency for Long-Conters LLM Inference Acceleration
selectively retrieving relevant tokens during the decoding stage, thereby ensuring that crucial information is omit- ted (Tang et al., 2024b; Sun et al., 2024). Nevertheless, KV retrieval does not mitigate high memory usage, lim- iting scalable batch sizes and thus the throughput under long contexts. Furthermore, certain approaches (Jiang et al., 2024; Xiao et al., 2024b; Tang et al., 2024a) recognize the heterogeneous sparsity patterns across different attention heads within the model and configure the heads with distinct sparsification strategies during inference. While they show initial promise in accuracy and efficiency, they do not fully utilize the interplay between the pre-filling and decoding phases to facilitate further optimization.
We identify that general sequential consistency exhibits in certain attention heads and dynamic activation in others, dividing the attention heads into consistent and adaptive heads, which naturally constructs the basic for decoding acceleration with pre-filling experience.
We propose CateK V, a hybrid KV cache acceleration algorithm leveraging sequential consistency. Employ- ing a coefficient-of-variatee -abaed score, CateKV can precisely classify attention heads into two categories, enabling efficient KV cache eviction while closely ap- proximating the performance of full attention.
Extensive evaluations on popular benchmarks demon- strate that CateKV reduces memory usage and decod- ing latency by 2.72x and 2.18x for single inputs, in- creases throughput by 3.96 in batch scenarios, while maintaining performance comparable to full attention. Further acceleration can be achieved by integrating our plug-and aad---nd--ply method with other approaches.
Different from previous methods, we explore leveraging the experience in pre-filling stage to promote the decoding stage. Specifically, our intuition is inspired by interesting observation: certain attention heads exhibit sequentially consistent attention patterns, spanning across the pre-filling and decoding stages, while some attention heads exhibit rich activation dynamics during the whole process, as shown in Figure 2. Besides, this phenomenon, reflecting the special head working mechanism, frequently existed in different LLMs and their different layers. This indicates that if we can capture those modes at the pre-filling stage, can leverage the sequential consistency to only maintain a subset of crucial tokens for certain heads, which achieves both a reduction of the KV cache and the speedup of attention computation during the decoding stage for LLM inference acceleration.
2. Related Work
2.1. KV Cache Eviction Algorithm
To save the significant time and space overhead as the in- put length increases, various approaches explore evicting tokens to reduce both memory usage and computational cost. StreamingL.MM (Xiao et al., 2023) introduces the phe- nomenon of "attention sink" and supports longer sequence by retaining only the KV pairs of attention sinks and recent tokens. H2O (Zhang et al., 2023) employs a low-cost evic- tion strategy to maintain a fixed-size KV cache containing hiiter, based on the sum of historical attention scores. SnapKV V (Li et al., 2024) uses the last tokens in the prompt during the prefilling stage to select critical tokens for gener- ation in the decoding stage. PyramidKV (Cai et al., 2024), PyramidInfer (Yang et al., 2024), and LazyLLM (Fu et al., 2024a) leverage attention distribution across layers to dy- namically adjust cache size, making cache allocation more efficient. Other methods like MagicPig (Chen et al., 2024), Q-Hitter (Zhang et al., 2024b), ALISA (Zhao et al., 2024) and, which combine KV cache eviction with quantization, hashing algorithms, or sparse windows, can also improve inference efficiency. However, these methods induce non- negligible performance degradation, they potentially evict certain tokens that are crucial for future generation.
Based on the above analysis, we propose CateKV, a sim- ple, effective, and plug-and-play method designed to en- hance LLM inference efficiency by leveraging sequential consistency. C uses an observation window during the pre-filling stage to identify critical tokens and employs a cefffiiientoo--vvrrattoo---
score to classify attention heads into consistent and adaptive types, based on a ref- erence dataset. In consistent heads, CateKV retains only small proportion of critical KV pairs, while in adaptive heads, it retains most, selecting tokens based on their impor- tance derived from attention weights in the pre-filling stage, as shown in Figure/ 1. By such an effective routing manner guided by sequential consistency, our method maintains the performance merit of LLM inference and simultancously enjoys the acceleration gain. Our method is orthogonal to and combinable with many existing acceleration approaches, and we conducted extensive experiments on widely used benchmarks including RULER (Hsich et al., 2024), Long- bench (Bai et al., 2023b), and NIAH (Kamradt, 2024), using models such as LLaMA-3-88 -----------n--tttttt--e- 1048K (Gradient, 2024a), GLM-4-9B- 1M (GLM et al., 2024a), 1LaMA-3.1- 8B (Meta AI, 2024) and Yi-9B-200K (AI et al., 2024) to demonstrate the effectiveness. In nutshell, our contribu- tions are summarized as follows:
2.2. KV Cache Retrieval Algorithm
Unlike KV cache eviction algorithms, KV cache retrieval algorithms retain a complete KV cache and dynamically retrieve important KV pairs to reduce inference latency. Fol- lowing PageAttention (Kwon et al., 2023), Quest (Tang et al., 2024b) divides tokens into pages and devises an approximate attention score to retrieve the most relevant
2

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
pages for the current decoding steps. InfLLM (Xiao al., 2024a) adopts strategy similar to Quest, offlodding most of the cache to the CPU to support longer prompts. Shad- owKV (Sun et al., 2024) enhances the storage efficiency of Quest by storing only low-rank key caches and offloading value caches, allowing inference with large batch sizes and context lengths. Others like SparQ (Ribar et al., 2023), In- finiGen (Lee al., 2024), and Loki (Singhania et al., 2024), accelerate the selection of top-k critical tokens by reducing the dimension. KV cache retrieval methods maintain per- formance by preserving the entire KV cache but inevitably incur increased inference latency and storage costs.
Layer 20 Head?
Tre-Ring
(a)
Consistent head
Exprdd 30
Lever Moud
Layer 20 veead 30
2.3. Head-wise Attention Classification
Another line of work classifies attention heads into distinct sparse patterns. MInference (Jiang et al., 2024) divides the attention into A-shape, Vertical-Slash, and Block-Sparse patterns, achieving acceleration during the pre-filling stage. RazorAttention (Tang et al., 2024a) and DuoAAttention (Xiao al., 2024b) split heads into retrieval heads and streaming heads to determine whether to implement full attention or an attention mechanism similar to LLre (Xiao et al., 2023). Methods like A (Feng et al., 2024) and HeadKV (Fu et al., 2024b) achieve more fine- the-grai clas- sification by allocating different budgets to each attention head. These methods focus on the features within individ- ual heads or their variations, but overlook the patterns of attention heads across the prefilling and decoding stages.
(b) Adaptive head
Figure 2: Visualization of attention weight heatmaps for consistent heads and adaptive heads in the LongChat-7B model using a randomly selected text segment. In these figures, the vertical axis represents the attention of the head across different queries, with the first 20 rows corresponding to the last 20 queries during the pre-filling stage, while the subsequent rows depict the attention weights across consecutive decoding steps. These two types of heads exist in various layers and other popular models (Appendix A).
Consistent heads are attention heads that exhibit stable attention patterns of sequential consistency, focusing on a limited set of tokens across all decoding steps.
3. Method
3.1. Sequential Consistency of Attention Heads
Adaptive heads are attention heads characterized by variable attention distributions across decoding steps, which do not exhibit stable patterns and require a larger attention space for flexible token interactions.
In this paragraph, we present an interesting observation about the attention patterns across the pre-filling and de- coding stages. To illustrate this, we randomly selected text segment from Wikitext (Merity et al., 2016) as input for the LongChat- (Li et al., 2023) model, examining how attention weights evolve throughout the generation pro- cess. Figure 2 illustrates the attention heatmaps during the pre-filling and decoding stages for two types of attention heads. We observe that for certain attention heads, attention concentrated on a few critical tokens, which show clear consistency across both the pre-filling and decoding stages. This consistency allows us to identify critical tokens during the pre-filling stage, which can then guide the decoding process and help reduce computational costs. In contrast, other attention heads exhibit attention distributions that vary significantly across decoding steps, maintaining a broader attention scope without focusing on specific tokens at each step. For these heads, it is crucial to retain most of the KV pairs to ensure accurate predictions. For clarity, we provide the further claims for these two types of attention heads:
3.2. How to Identify Consistent and Adaptive Heads?
Observation matrix As can be seen in Figure 2, the atten- tion weights of the last query tokens the pre-filling stage effectively reflect the attention patterns. To save the com- putational cost, we set an observation window that contains the last query tokens of the input to identify head types and critical tokens. Additionally, since initial and recent tokens are typically important but do not influence the classification process, we temporarily exclude them during the identifi- cation phase. Formally, let Linits Lice and Lobs respectively denote the lengths of the initial tokens, recent tokens, and the observation window. Then, consider head within a sample at the pre-filling stage, where the input includes the query Q, key K, and value V E Rx with n representing the input length and d representing the head dimension in the attention mechanism. We define the observation matrix
3

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Oyerlsp Rate Classification Results Across Different Samples
Uama-3-00
Algorithm 1 CateKV in individual Head
Input: Q,K, V E Rnxd q R1xd head type H, obser- vation window size Lobs selected chunk budget b, chunk size es, retention ratio r7 Pre-filling Stage:
Layers
# Calculating loken criticality
A = softmax(Q2) (Q( bogs K- Lotee) / /d)
C Σ Lobe Ai,
i==
# Divide C into chunks and take maximun
Cehask BlockMax cs)
Sample
Hoads
(a)
(b)
# Cache keys and values based on indices of top-k elements if H = consistent head then
Figure 3: (a) High similarity of classification results across samples. We calculate the overlap rate between the classifi- cation results of 200 randomly selected WikiText samples and the overall classification result with r = 0.3. All sam- ples exhibit an overlap rate exceeding 80% with the overall result. (b) Frequency of adaptive head identification for Llama-3B model in reference dataset with 0.3. The frequency distribution is highly concentrated, enabling the determination of fixed head type based on these results.
i arglopk (Cetunk b)
eache,, cache, = Cache(K, K, V, Vikko Loba))
else
iu = Cnrgtop(Cstuntss n7))
caches, cache, = Cache(K, (K, V, iks Lobs)
end if
Decoding Stage:
# Retrieval keys and values from cache if H consistent head then
k, e caches, cache,
else
k Retrival(g, caches, eache.) # all or query-aware
A within the observation window, as follows:
end if
(Q--Lenii))) KTrni Tmact
(Ql- (qltia
oulput Attention(q, k)
= softmax
Vd
Now, obtain the score based the coefficient of variation for an attention head of sample as follows:
where A E IR (( bun) In the following, we will identify consistent heads based on the characteristics of A.
E
score (n Lnee Tmmi)
Coefficient of Variation (CV) Score Empirically, consis- tent heads exhibit two primary features in their observation matrices: a high degree of similarity among different rows and a small subset of columns that is sufficient to recall most of the attention weights. Inspired by this aspect, we score to measure the concentration and similarity of attention within obser- vation matrices A. Since the coefficient of variation (Abdi, 2010) is highly sensitive to the magnitude of values, we first binarize the observation matrix with a percentile-based threshold & and a scaling factor a.
(4)
1²(C)
where n(C) (n- Lun) E, C. is the mean. With the above equations,
compute score for each head under sample. Then, for specific LLM, we can obtain score matrix S E x for all heads, where 7 and h represent the number of layers in the model and the number of heads in a layer, respectively. For a statistic head identification rule, let r denote the proportion of adaptive heads, and ((r) represents the percentile threshold based on We can use the threshold to control the token eviction ratio. Then, we distinguish the head types of specific sample follows
propose
B = I (kk a)) E Rhaxx(nn ((nxxx(n-Lee Liui)
(2)
consistent head, if St, > T(r) adaptive head, if St, - [(r)
where is the indicator function, and ((k, a) Quantile, (4) x a represents the k-th percentile element the matrix A, scaled by a factor of a. Then after binariza- tion, we derive frequency vector C' quantify the number of times each token that is identified critical, reflecting the similarity and concentration of attention weights:
=
Head,
(5)
Enterence-Basell Static Identification Although head identification can be performed dynamically for each sam- plc, it is actually expensive for memory management along with the change of samples at the pre-filling stage. There- fore, is better to determine a fixed head type for the model, which can be directly used for inference. Surprisingly, we
Ligts
C
Bi, B (n--ne Traa)

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
1
Attention Weight Recall
Vf E F, Phead
B[f]
Σ
fn 2Rx(F)
N
0.-
==1
2lo ae
6.-
+
2 1 8.
(6)
2NV
Consistent pattern
where RN (P) ) is the conditional Rademacher average.
Streaming pattern
Top-k
Let P1 and Ps denote the probabilities of correctly classified consistent heads and adaptive heads, respectively, while Pi and P2 represent the probabilities of misclassified consistent heads and adaptive heads, respectively. It is assumed that Pi + P2 = Phend and P1 + P2 = 1 - Phead The probability in the above lemma can then be decomposed through a fine-grained analysis as follows.
Quest
Normalized Head Index (Descending)
Figure 4: Attention weight recall curves for four methods. The curves show the attention recall for each attention head, calculated on four patterns: consistent, streaming, quest, and top-k, on 128k-length example. The attention recall values are obtained by the mean of all decoding steps and sorted in descending order for all heads. The sparse budget is set to 2048, and the chunk size 8. The results indicate that the consistent pattern outperforms the streaming pattern in terms of overall attention recall, and approaches the performance of the quest pattern that requires additional computation.
Let 7) and 172 denote the retention ratios for consistent heads and adaptive heads, respectively, while 'ii and 1/2 represent their corresponding optimal retention ratios. Define the retention accuracy for different cases Fi 1/ [m, > n/l + 7, 1 [yH > nf'l) by comparing the retention budgets with the optimal budgets. Additionally, assume that the hypothesis asserting the query attention score provides the best description in order with probability x. Then, the token retention accuracy satisfies:
Theorem 1:
observe that the same head does exhibit similar attention patterns across different samples, and the identification sults based CV scores are highly consistent. This inspires us use reference dataset to calculate the frequency of each head being identified as the consistent head, and then derive the final model-wise identification result based on the adaptive head ratio r, as shown in Figure 3, which comes the final form of our method (termed as CateKV), After determining the type of each head, we retain only the most important KV pairs for consistent heads, while for adaptive heads, we preserve a majority based on the predefined re- tention ratio Specifically, we select the top-k KV pairs in chunks, enabling seamless integration with retrieval-bare methods. For the GQA model, the observation matrix A is computed as the mean of A of the heads group. The CateKV acceleration for LLMs shown in Algorithm
P Puoken > Pri,1 + r2,2 + r2,1 + P2)
2 (mmin((2,1 [min(r1,1,
1in(121,7112) Phead)
Remark From the above theorem, three critical factors influence the worst-case token retention accuracy (i.e., the lower bound):
X: The effectiveness of identifying an efficient measure to characterize token correlation by the score order, with as high probability of correctness as possible.
Budget control: The ability to appropriately set the re- tention budget in order to maximize gains by reducing the majority of tokens when heads are correctly clas- sified, while simultaneously mitigating the negative impact when heads are misclassified.
3.3. Theory Analysis
In this part, we present an analysis of the theoretical bound on the eviction performance of CateKV.
The accuracy of the CV-based method clas- sifying the head type during token reduction, which directly impacts the overall performance.
Pread:
Lemma 1: Let G represent the hypothesis class derived from the CV-based function, F denote the real-valued func- tion class induced by the binary cross-entropy loss applied to G, and let N denote the sample size of the reference- based dataset. Then, with probability at least 5, the following Rademacher complexity bound holds:
3.4. Further Discussion of CateKV
To show the distinction and effectiveness of attention pat- terns discovered from the sequential consistency, Figure
5

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Table I: Performance (%) of different models and various methods on RULER evaluated at length of 128K. The 'Cache' in the table refers to the retained KV cache size. CateKV outperforms other methods and comparable with full attention.
Methods
Cache
N-S1
N-S2
N-S3
N-MKI N-MK2
N-MK3
FWE
N- N-MQ N-MV
QA-1
QA-2
VT
Avg.
1amma-3-8B-JM IMM
100%
100.00
100.00
100.00
98.96
98.96
41.67
71.88
98.69
96.35
73.96
50,00
78.75
84.10
Streamingl
41% %
51.04
51.04
51.04
40.63
35.42
22.92
75.69
45.31
39.58
78.13
45.83
31.46
47.34
SuapKY
41%
100.00
100.00
100.00
98.96
98.96
30.21
71.53
98.44
97.13
73,95
51.04
79.17
83.28
PyramidKV
41%
100,00
100.00
100.00
98.96
98.96
37.50
71.53
98.44
96.61
71.87
50.00
79.38
83.60
Duoattention
41%
100.00
100.00
100.00
98.96
97.92
39.58
76.74
94.27
90.36
69.79
51.04
86.46
83.76
CateKV
41%
100.00
100.00
100.00
98.96
97.92
41.67
71.88
98.44
96.88
73.96
50.00
85.63
84.61
Phi-3-Mini- 128K
100%
96.88
90.63
95.83
83.33
65.63
37.50
87.15
72.14
66.67
63.54
39.58
65.83
72.06
Streaming
41%
47.91
45.83
44.79
38.54
30.21
25.00
84.38
36.49
34.90
64.58
38.54
4.38
41.29
SnapKy
41%
96.88
90.63
80.21
82.29
56.25
11,46
82.99
61.72
53,91
62.50
38.54
63.54
65.08
PyramidKV
41%
96.88
90.63
84.38
83.33
57.29
13.54
78.47
66.15
59.64
62.50
39.58
62.29
66.22
CateKV
41%
96.88
90.63
95.83
83.33
65.63
38.54
80.21
70.31
65.63
63.54
39.58
70.21
71.69
Llama-3. 3.B
100%
100,00
100.00
98.96
98.96
90.63
63.54
71.53
98.96
95.31
81.25
46.88
68.54
84.55
StreamingLLM
41%
51.04
51.04
51.04
39.58
34.38
40.63
71.18
44.27
39.84
85.42
40.63
28.33
48.11
SnapKy
41%
100.00
100.00
98.96
98.96
89.58
46.88
69.10
98,96
94.01
81.25
46.88
68.96
82.80
PyramidKV
41%
100.00
100.00
98.96
98.96
90.63
56,25
65.28
98.96
95.31
80.21
46.88
65.42
83.07
Duoattention
41%
100.00
100.00
98.96
97.92
88.54
59.38
74.31
97.92
91.41
81.25
46.88
78.54
84.59
CateKV
41%
100.00
100.00
98.96
98.96
88.54
61.46
71.88
98.96
94.27
81.25
46.88
74.79
84.66
Yi-98-200K
100%
100.00
100.00
98.96
85,42
63.54
18.75
89.24
66.41
32.55
45.83
38.54
35.00
64.52
StreamingL.M
41%
47.92
52.08
50.00
39.58
37.50
7.29
90.28
33.33
14.84
44.79
36.46
18.13
39.35
SnapKV
41%
100.00
100.00
95.83
85.41
43.75
3.13
83.33
66.41
33.33
46.88
40.63
38.96
61.47
PyramidKV
41%
100.00
100.00
91.67
86.46
50.00
2.08
73.61
68.75
34.64
43.75
37.50
41.46
60.83
CateKV
41%
100.00
100.00
100.00
84.38
70.83
18.75
92.01
62.24
34.64
43.75
37.50
45.00
65.76
compares attention weight recall for our consistent pattern, streaming pattern (Xiao et al., 2023), Quest pattern (Tang et al., 2024b), and the upper-bound bound top-k pattern under the same sparse budget. As can be seen, all methods exhibit a gap compared the upper bound, indicating some informa- tion loss with current sparse attention approaches. There- fore, retaining most KV pairs for certain heads is important for maintaining accuracy. On the other hand, the attention recall of the consistent pattern closely approximates that of the Quest pattern, applying the consistent pattern to heads with sequential consistency can help KV retrieval methods reduce memory usage and the cost of selecting critical to- kens. Related works (Tang al., 2024a; Xiao et al., 2024b) classify attention heads into Retrieval Hcads and Streaming Heads, which is similar to our method. However, from an attention recall perspective, the streaming pattern is only effective for a small fraction of heads, otherwise deviating significantly from full attention. This highlights that the consistent pattern achieves a higher compression rate than the streaming pattern. We will discuss the comparison and integration with these methods in the experimental section.
et al., 2024) and Qwen2.5-7B (Bai et al., 2023a). The per- formance of CateKV was assessed on three challenging benchmarks: RULER (Hsieh et al., 2024), LongBench (Bai et al., 2023b), and Needle in a Haystack (NIAH) (Kamradt, 2024). We built a reference set for head identification of CateKV by emulating Variable Tracking task from RULER, which is very distinct from the test set. The experiments were carried out on single NVIDIA A100-80G GPU.
Baselines We compare CateKV with eviction -baeed al- gorithms Streaming (Xiao et al., 2023), SnapKV (Li et al., 2024), PyramidKV (Cai et al., 2024), retrieval-based algorithms Quest (Tang et al., 2024b) and ShadowKV (Sun et al., 2024), and the head-wise classification algorithm Duoattention (Xiao al., 2024b). In our experiments, all approaches maintained an exact pre-filling stage and utilized sparse attention during the decoding stage. We also do not perform memory optimization like ShadowKV in the accu- racy comparison. For fairness, when comparing with the KV eviction methods and head classification methods, we maintain the same KV cache size, while comparing with KV retrieval methods, we integrate them under adaptive heads to ensure equivalent computational budget. Given that Duoattention only provides attention patterns for Llama3 and Llama3. in the models used in our study, the com- parison is restricted to these two models. When baselines require a chunk size, we all set it to 8 to maintain consis- tency. Further experimental details are in the Appendix B.I.
4. Experiments
4.1. Setup
LLM and Benchmark We employed five widely used
LLMs in long-context scenarios: (LMMA-3-BB-Insttun 1048K (Gradient, 2024a), Phi-3-Mini- -28K (Abdin al.,
2024), L-ama-3.1-8B (Meta AI, 2024), Yi-9B-200K (AI
6

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Table 2: Performance (%) of different models and various methods on LongBench. We present the average score of all 21 tasks. The "Budget" refers to the computational budget.
Needle in A Haystack Liama-3-8-1M w/ CateKV
100
08
Please refer to the Appendix B.3 for detailed data.
Death Percent
33
0.
64
Model
[. ama-3
Phi-3 | Llama--. 3.1
Yi Qwen2.5
56
0.4
Methods
Cache
Budget
Average Performance
Full
100%
100%
31.27
34.00
33.68
33.02
30.03
02
+CateKV
42%
42%
31.48
33.73
33.70
32.83
29.92
Quest
+CateKV
100%
42%
3%
3%
31.03
30.90
33.11
33.29
33,20
33.38
32.79
32.82
29.33
29.30
20k
2lok
3008
4400
$1.k
7206
0.0
ShadowKV KV
100%
3%
30.77
32.53
33.03
32.41
28.57
+CateKV
42%
3%
30.94
32.45
32.96
32.21
28.51
Context Length
Figure 5: Needle In A Haystack from 20K to 1M in Llama3
4.2. Effectiveness Evaluation
4.2.1. RESULTS ON RULER
Table 3: Performance of CateKV combined with Duoatten- tion and MInference on the RULER benchmark. The results are tested on the Llama-3-8B-a model.
In this experiment, we test 12 synthetic tasks under the context of 128K, with each task including 96 samples. To ensure fair comparison with other baseline methods, we focus here on the task- setting. The results are shown in Table 1. Specifically, in CateKV we set the adaptive head ratio r to 0.4, the retention ratio 17 to 1.0 and allocate a sparse budget for consistent heads at 2048 (1.56%), retain- ing approximately 41% of the KV cache size. Experimental results demonstrate that our method outperforms baselines and is comparable to full attention, despite evicting over half of the KV pairs. Besides, CateKV exhibits outstanding per- formance in complex tasks such as multi-document QA and variable tracking while maintaining high accuracy in other tasks. Due to the space limitation, we place results of more context lengths and combination with other setrevall-based methods in Appendix B.2.
Methods
8K
16K
32K
64K
128K
256K
Avg.
Ducattention
78.32
77.93
66.27
60.37
68.46
Dumateention w/ CatcKVV
89.93
91.08
89.96
86.44
84.57
81.59
87.26
MInference
91.33
92.28
84.57
MInference w/ CateKV
91.32
92.13
89.71
85.90
85.14
82.27
87.74
computational cost by more than half. Additional NIAH test results other models are available in the Appendix B.4.
4.2.4. CATEKV Vs. DUOATTENTION
Duoattention (Xiao et al., 2024b) classifies attention heads into retrieval heads and streaming heads, similar to our approach. For a comprehensive comparison, we evalu- ate CateKV against DuoAttention across varying ratios of adaptive/retrieval heads, ranging from 0.1 1.0. Figure 7 shows that Duoattention's accuracy notably declines when the proportion of retrieval heads falls below 0.3. In contrast, CateKV sustains performance close to full attention even when the ratio of adaptive heads decreases to 0.1. This dis- crepancy arises from the fundamental difference attention patterns between our consistent head and their streaming head. The consistent head in CateKV captures similarity across different queries, whereas the streaming head pri- marily focuses on the coverage of initial and recent tokens, This essential difference enables our method to complement DuoAAttentio, mitigating its performance degradation at low full attention head ratios. To validate this, we conducted experiments presented Table 3. Specifically, we set the retrieval head ratio in DuoAAtention 0.3, with the remain- ing 0.7 as streaming heads. In contrast, "Duoattention w/ Ca replaces part of the streaming heads with consis- tent heads, resulting in 0.2 consistent head ratio and a 0.5 streaming head ratio. The results demonstrate that in- corporating CateKV significantly improves DuoAttention'ss performance at low full attention head ratios, further vali- dating the effectiveness of our consistency pattern.
4.2.2. RESULTS ON LONGBENCH
I LongBench (Bai et al., 2023b) is a comprehensive long- context benchmark including 6 main categories and 21 di- verse tasks. Following ShadowKV (Sun et al., 2024), we test samples with lengths exceeding 4096 tokens. In CateK V, we set the adaptive ratio r and retention ratio 1) to 0.4 and 1.0 respectively. The budget for consistent heads is set to 512. As shown in Table 2, CateKV enables reduction in KV cache size to 42% across five LLMS while maintain- ing an accuracy decline of no more than 0.3% on average. Furthermore, when integrated with KV retrieval methods like Quest (Tang et al., 2024b) and ShadowKV (Sun et al., 2024), CateKV facilitates a reduction in memory usage with only a minimal impact accuracy, not exceeding a 0.2% decrease, under the same computational budget.
4.2.3. RESULTS ON NEEDLE IN A HAYSTACK
As shown in Figure 5, on the Needle In A Haystack dataset, CateKV demonstrates its robust ability to accurately identify and extract relevant information from long contexts, rang- ing from 20K to 1M tokens, while reducing memory and
7

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Llama-3-88-11 (GQA 40%)
Llama-3-8B-1M (GQA 40%)
140
Full Attention
140
Attention
120
CatekV
80
CateKV
(Memrr (GB)
100
Latency (ms)
60-
40
60
28
19
40
24
28
65
32
36
10141
10145
40
23 1.8
30
21
24
45
27
30
10
36
00
1
39
101
12
100K
200K
300K
400K
500K
600K
700K
BOOK
900K
1000K
100K
200K
300K
400K
500K
600K
700K 800K 900K 2000K
Context Length
Context Length
Figure 6: Comparison of decoding efficiency between CateKV and full attention. As the context length increases, both the memory usage (a) and decoding latency (b) increase linearly, but CateKV exhibits smaller slope compared to full attention. OOM indicates that the GPU memory limit (80G) is exceeded; corresponding data is obtained by extrapolation.
4.2.5. EFFICIENT FRE-FILLING METHODS INTEGRATION
RULEN-128K Parformancs, 3-4ma-3-48-11
Aug
CateKV is designed to accelerate the decoding stage and can naturally integrate with prefilling acceleration methods. We also combined V with the efficient prefilling accel- eration method, MInference (Jiang et al., 2024), and tested it on RULER with contexts ranging from 8K to 256K. As shown Table 3, combining CateKV with MInference does not lead to performance degradation and even a slight per- formance improvement has been observed. This shows that sequential consistency within the heads is unaffected by the pre-filling inference patterns, highlighting the robustness of our method. Moreover, the additional acceleration of the prefilling stage further improves the overall inference speed.
70
Accwacy
60
50
40
(128K)
(128/
Dusattentonn
30
Dupatiantion
CahekV
Catelt
20
0.9
0.8 06
0.5 0.4 0.3 0.1
0.9 0.7
0.4
0.1
AdeptivsRetrieevl Head Rabio
Adaotiva/ Rettiiva/Rotiivva Hoad Radio
Figure 7: Comparison of accuracy between our method and DuoAttention across different full attention head ratios.
4.3.2. BATCH-SAMPLE INFERENCE
Batch-sample inference is more common scenario in real-world applications. By evicting a portion of the KV pairs, CateKV supports larger batch sizes, thereby increas- ing throughput. To evaluate CateKV's efficiency in batch- sample scenarios, we set each sample length to 40K and in- put them in batches, comparing throughput at the maximum batch size for both full attention and CV The compar- ative results across three models are presented in Table 4, With the generic settings, gains of up to 2.38x in batch size and 2.25x in throughput were achieved. Additionally, through further KV cache compression while maintaining accuracy, both batch size and throughput in the Llama-3 model were boosted to 4.33x and 3.96x, respectively.
4.3. Efficiency Evaluation
To validate the efficiency of CateKV, we tested it under both single-sample and batch-sample inference scenarios.
1.3.1. SAMPLE INFERENCE
To evaluate the efficiency of CateKV during sagpe inference, we selected three models with different num- bers of KV heads: Llama-3, Phi-3, and Yi. We compared CateKV full attention on these models by measuring mem- ory usage and decoding latency at the same input length. We observed that memory and latency reductions increase as the context length grows (detailed in the Figure 6). To demon- strate optimal performance, we selected the maximum input length that can be handled by full attention on a single A100 GPU. As shown in Table 4, under the generic settings of r 0.4 and 77 = 1.0, the Phi-3 model achieved reductions of 2.11x in memory and 1.79x in latency by using CateKV. By balancing efficiency and accuracy, CateKV further re- duced memory usage by 2.72x and decoding latency by 2. 1818 on Ilama-3, with accuracy decline on RULERR-12K and Longbench tasks under 0.25%.
4.4. Ablation Study
The ablation studies focus on three key aspects of CateKV (1) ratio of adaptive heads, (2) retention ratio in the adaptive head, and (3) sparse KV cache budget in the consistent head. All experiments conducted the RULER-128K datasets using the Llama-3-8B-IM model.
4.4. 1. RATIO OF ADAPTIVE HEADS
The ratio of adaptive heads r a crucial hyperparameter bal- ancing accuracy and inference speed. As shown in Figure 7, the relationship between r and model performance does
8

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Table 4: Efficiency comparison between CateKV and Full Attention on a single A100 GPU. In the single-sample inference task, we utilized texts of lengths 500K, 180K, and 650K as inputs for the following three models. For the inference task, the sample length was set at 40K, and the maximum feasible batch size was used for each method evaluated.
Accuracy (Avg)
Single-sample inference
Batch-sample inference
Model
RUTER-122K
Langhench
Memory
Latency
Batchsize
Throughput
Llama-3-8B-J1n (8 KV heads)
84,10 (0.00)
31.27 (0.00)
77.72 (1.00x)
54.28 (1.00x)
12 (1.00x)
229.37 (1.00x)
CateKV (r 0.4. 1) 1.0)
84.61 (+0.51)
31.48 (+0.21)
41.02 (1.89x)
32.75 (1.66x)
28 (2.33x)
511.46 (2.23x)
CateKV (r 0.3, 17 0.7)
83.85 (-0.25)
31.21 (-0.06)
28.59 (2.72x)
24.86 (2.18x)
52 (4.33x)
909.69 (3.96x)
Phi-3-Mimi-128K (32 KV heads)
72.06 (0.00)
34,00 (0.00)
75.11 (1.00x)
55.51 (1.00x)
4 (1.00x)
78.53 (1.00x)
CateKV (r 0..4 17 1.0)
71.69 (-0.37)
33.73 (-0.27)
35.58 (2.11x)
31,06 (1.79x)
10 (2.50%)
167.11 (2.13 (2.13x)
CateKV (r 0.3, 17 1.0)
71.48 (-0.58)
33.66 (-0.33)
29.02 (2.59x)
27.81 (2.00x)
14 (3.50x)
221.29 (2.82x)
V--9B-20K (4 KV heads)
64,52 (0.00)
33,02 (0.00)
77.65 (1.00x)
56,30 (1.00x)
16 (1.00x)
292.55 (1.00x)
CateKV (r 0) 1.0)
65.76 (+1.24)
32.83 (-0.19)
41.61 (1.87x))
36.05 (1.56x)
38 (2.38x)
659.02 (2.25
CateKV (r 0.3. 0.8)
65.75 (+1.23)
32.78 (-0.24)
31.58 (2.46x)
29.96 (1.88x)
60 (3.75%)
980.86 (3.35x)
35
85
80
80
84
Memory Usage
82
30
84
60
60
Accuracy
Latency
Accuracy
80
83
40-
-40
78
20
Full
20
76
Ours
1.0 0.9 0.8 0.7
0.6
0.5
0.4
0.3
0.2
0.1
1.0 0.9
D.8
0.3 Retention Rotio
0.7
0.6
D.5
0.4
0.7
0.1
81
2000
4000
6000
8000
Adaptive Head Ratio
Sparse Budget
(a)
(b)
(c)
Figure 8: (a) The effect of adaptive head ratio on memory and decoding latency is approximately linear. (b) Impact of retention ratio accuracy in RULER-128K 128K and decoding latency for 500K length input. (c) Minimal effect of sparse budget in consistent heads on accuracy.
not exhibit a perfect inverse correlation. Rather, the per- formance remains relatively stable with decreasing r until reaching a critical threshold (==0.2), beyond which signifi- cant degradation occurs due to excessive reliance on critical tokens during the prefilling stage. In terms of efficiency, as shown in Figure 8(a), both memory usage and decoding latency decrease almost linearly with decreasing r.
tings of r = 0.4 and n = 1.0, even when the sparse budget in the consistent head is reduced to approximately 0.78% (1024), CateKV still maintains comparable performance to full attention in terms of average accuracy. This indicates that, during inference, the consistent head only requires minimal portion of the cache to perform its function, while the acquisition of global information relies primarily on adaptive heads, which retain the majority of KV pairs dur- ing the decoding stage. Since the sparse budget for the consistent head a small fraction of the total cache, its im- pact on memory usage and inference latency is negligible.
4.4.2. RETENTION RATIO IN ADAPTIVE HEAD
In adaptive heads, there is still a subset of tokens that are always not important. This enables a reduction in the pro- portion of the KV cache retained within adaptive heads. Figure 8(b) illustrates the impact of changes in the retention ratio 7) accuracy and latency. When 1) exceeds a certain threshold (s00.),, the model maintains or even surpasses the performance achieved with the full KV cache. How- ever, dropping below this threshold results in a significant performance decline, indicating that adaptive heads heavily depend on the majority of the KV cache. Additionally, a de- crease in 17 leads to a linear reduction in latency. In practical applications, it is essential to adjust both and 17 to balance accuracy and memory consumption.
5. Conclusion
We propose CateKV, a novel hybrid KV cache method that leverages sequential consistency to improve LLM inference efficiency in long-context tasks. By using a coefficient-of- variation-based algorithm, CateKV classifies attention heads into consistent and adaptive types. It selectively retains crit- ical KV pairs in consistent heads and most pairs in adaptive heads, reducing memory usage and decoding latency while maintaining performance. Additionally, it can be easily integrated with other acceleration methods for further en- hancement. Extensive evaluations demonstrate that CateKV achieves significant efficiency gains, including up to 2.72x reduction in memory usage, 2.18x acceleration in decoding, and a 3.96 x throughput increase in batch scenarios.
4.4.3. SPARSE BUDGET IN CONSISTENT HEAD
As illustrated in Figure 8(c), CateKV demonstrates strong robustness across different sparse budgets. Under the set-

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Acknowledgments
Repository-Level coding using Ilss and planning. Pro- ceedings of the ACM on Software Engineering, 1(FSE): 675-698, 2024.
This work is supported by National Natural Science Founda- tion of China (No.62301188) (88), STCSM (No.22D22229005), 111 plan (No. BP0719010).
Caciularu, A., Peters, M. E., Goldberger, J., Dagan, I., and Cohan, A. Peek across: Improving multi-document modeling via cross-document question-answerigg arXiv preprint arXiv:2305. 2023.
Impact Statement
The primary objective of our research is to develop inference acceleration methods for large language models, aiming to advance their efficiency and scalability. We explicitly state that any depictions of violence in the datasets are wholly fictional and are utilized exclusively for academic research purposes. This work does not reflect, support, justify any real-world violent actions. Additionally, this research was carried out independently, with no external funding or conflicts of interest influencing its outcomes. The study strictly follows ethical guidelines, taking into account es- sential factors such as discrimination, bias, fairness, privacy, security, and legal adherence, while maintaining the utmost integrity in the research process.
Cai, Z., Zhang, Y., Gao, B., Liu, Y., Liu, T., Lu, K., Xiong, W. Dong, Y., Chang, B., Hu, J., et al. Pyramidkv: Dy- namic kv cache compression based on pyramidal informa- tion funneling, arXiv preprint arXiv:2406 02069, 2024.
Chen, 7.., Sadhukhan, R., Ye, 7., Zhou, Y., Zhang, J., Nolte, N., Tian, Y., Douze, M., Bottou, L., Jia, Z., et al. Mag- icpig: Lsh sampling for efficient Ilm generation. arXiv preprint arXiv:2410. 2024.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., al. The llama 3 herd of models. arXiv preprint 2407 2024.
References
Feng, Y., Lv, J., Cao, Y., Xie, X., and Zhou, S. K. Ada- kv: Optimizing kv cache eviction by adaptive budget allocation for efficient 11m inference. arXiv preprint 1rXiv:2407111555 2024.
Abdi, H. Coefficient of variation. Encyclopedia of research design, 1(5):169-171, 2010.
Abdin, M., Aneja, J., Awadalla, H., Awadallah, A., Awan, A. A., Bach, N., Bahree, A., Bakhtiari, A.. Bao, J., Behl, H., et al. Phi-3 technical report: A highly capable lan- guage model locally on your phone. arXiv preprint arXiv:2404. 14219, 2024.
Fu, Q. Cho, M., Merth, T., Mehta, S., Rastegari, M., and Najibi, M. Lazyllm: Dynamic token pruning for efficient long context Ilm inference. arXiv preprint arXiv: wwX.v:207..1400 2024a.
Fu, Y., Cai, Z., Asi, A., Xiong, W., Dong, Y., and Xiao, W. Not all heads matter: A head-level kv cache compression method with integrated retrieval and reasoning. arXiv preprint arXiv:2410. O./ 1..09920 19258, 2024b.
Achiam, J., Adler, S., Agarwal, S., Ahmad, I.., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., al. Gpt-4 technical report. arXiv preprint arXiv:2303. 08774, 2023.
GLM, T., Zeng, A., Xu, B., Wang, B., Zhang, C., Yin, D., Rojas, D., Feng, G., Zhao, H., Lai, H., Yu, H., Wang, H., Sun, J., Zhang, J., Cheng, J.,, Gui, J., Tang, J., Zhang, J.. Li, J., Zhao, L., Wu, L.., Zhong, L., Liu, M., Huang, M., Zhang, P., Zheng, Q., Lu, R., Duan, S., Zhang, S., Cao. S., Yang, S., Tam, W. I.., Zhao, W., Liu, X., Xia, X., Zhang, X., Gu, X., Lv, X., Liu, X., Liu, X., Yang. X., Song, X., Zhang, X., An, Y., Xu, Y., Niu, Y., Yang, Y., Li, Y., Bai, Y., Dong, Y., Qi, Z., Wang, Z., Yang, Z., Du, Z., Hou, Z. and Wang, Z. Chatglm: A family of large language models from glm-130b to glm-4 all tools, 2024a.
:,, Young, A., Chen, B., Li, C., Huang, C., Zhang, G., Zhang, G., Li, H., Zhu, J., Chen, J., Chang, J., Yu, K., Liu, P., Liu, Q., Yue, S., Yang, S., Yang, S., Yu, T., Xie, W., Huang, W., Hu, X., Ren, X., Niu, X., Nic, P., Xu, Y., Liu, Y., Wang. Y., Cai, Y., Gu, Z., Liu, Z., and Dai, Z. Yi: Open foundation models by 01. ai. 2024.
Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X., Fan, Y., Ge, W., Han, Y., Huang, F, et al. Qwen technical report. arXiv preprint 2309v:2309. 16609, 2023a.
GLM, T., Zeng, A., Xu, B., Wang, B., Zhang, C., Yin, D., Zhang, D.,, Rojas, D., Feng. G., Zhao, H., et al. Chatgim: A family of large language models from glm-1306 to glm-4 all tools. arXiv preprint arXiv:2406. 12793, 2024b. Gradient.
Bai, Y., Lv. X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou, L., et al. Longbench: A bilingual, multitask benchmark for long context under- standing. arXiv preprint arXiv:2308. 14508, 2023b.
gradient 1048k, 2024a.
Bairi, R., Sonwane, A., Kanade, A., Iyer, A., Parthasarathy, S., Rajamani, S., Ashok, B., and Shet, S. Codeplan:
URL htttps://hggiiggace..oo 4iama-3- 3- 8B Instrrttt-rrriieenteee
10

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Gradient.
Llama-3-8b-instruet gradient 262k, 2024b. URL www.:ttts://hhggiiig htt.aaaacc.e./ggg.eeaaaaaia//// gradientadiin//// Llama-3 3 8-8B- -nB-nrttt -atorructt26kk..
Singhania, P., Singh, S., He, S., Feizi, S., and Bhatele, A.
Loki: Low-rank keys for efficient sparse attention. arXiv preprint arXiv:2406.02544 2024.
Hsieh, C.-P., Sun, S., Kriman, S., Acharya, S., Rekesh, D., Jia, F., Zhang, Y., and Ginsburg, B. Ruler: What's the real context size of your long-context language models? arXiv preprint arXiv:2404.06654. 2024.
Sun, H., Chang, L.-W., Bao, W., Zheng. S., Zheng, N., Liu, X., Dong, H., Chi, Y., and Chen, B. Shadowkv: Kv cache in shadows for high-throughput long-context Ilm inference. arXiv preprint urXiv:2410.11460 2024.
Jiang, H., Li, Y., Zhang, C., Wu, Q., Luo, X., Ahn, S., Han, Z., Abdi, H., Li, D., Lin, C.-Y., et al. Minference 1.0: Accelerating pre-filling for long-context Ilms via dynamic sparse attention. arXiv preprint
Tang, H., Lin, Y., Lin, J., Han, Q., Hong, S., Yao, Y., and Wang, G. Razorattention: Efficient kv cache compression through retrieval heads, arXiv preprint arXiv:2407.1589) 2024a.
2024.
Jimenez, C. E., Yang, J., Wettig, A., Yao, S., Pei, K., Press, O., and Narasimhan, Swe-hench: Can language mod- els resolve real-world github issues? arXiv preprint arXiv:2310.06770 2023.
Tang. J., Zhao, Y., Zhu, K., Xiao, G., Kasikei, B., and Han, S. Quest: Query-aware sparsity for efficient long-context Ilm inference. arXiv preprint arXiv:2406. 10774, 2024b.
Team, G., Amil, R., Borgeaud, S., Alayrae, J.-B., Yu, Sori- cut, R., Schalkwyk, J., Dai, A. M., Hauth, A., Millican, K., et al. Gemini: family of highly capable multimodal models. arXiv preprint arXiv:2312.1180; 2023.
Kamradt, G. Needle in a haystack pressure testing Ilms, 2024.
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. Proceedings of the 29th Sym- posium on Operating Systems Principles, pp. 611-626, 2023.
Wang, M., Chen, L.., Cheng, F., Liao, S., Zhang, X., Wu, B., Yu, H., Xu, N., Zhang, L., Luo, R., et al. Leave no document behind: Benchmarking long-context Ilms with extended multi-doc qa. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 5627-5646, 2024.
Lee, W. Lee, J., Seo, J., and Sim, J. [InfiniGen]:: Effi- cient generative inference of large language models with dynamic [KV} cache management. In 18th USENIX Symposium Operating Systems Design and Implemen- tation (OSDI 24), pp. 155-172,70 2024.
Xiao, C.,, Zhang, P., Han, X., Xiao, G., Lin, Y., Zhang, Z., Liu, Z., and Sun, M. Infilm: Training-free long- context extrapolation for llms with efficient context memory. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Li, D., Shao, R., Xie, A. Sheng, Y., Zheng, L., Gon- zalez, E., Stoica, I., Ma, X., and Zhang, H. How long can open-source Ilms truly promise context length?, June 2023. URL https: happs://mmsysss hwllmss...orooo blog/2023 06-006666 29-21990000 2onngggc
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Ef- ficient streaming language models with attention sinks. arXiv preprint arXiv:2309.1 17453, 2023.
Li, Y., Huang, Y., Yang. B., Venkitesh, B., Locatelli, A., Ye. H., Cai, T., Lewis, P., and Chen, D. Snapkv: Lim knows what you are looking for before generation. arXiv preprint arXiv:2404.1 14469, 2024.
Xiao, G., Tang, J., Zuo, J., Guo, J., Yang, S., Tang, H., Fu, Y., and Han, S. Duoattention: Efficient cont-context I1m inference with retrieval and streaming heads. arXiv preprint 2xXiv:2410.18811 2024b.
Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. arXiv preprint arXiv: 060..600947444 2016.
Yang, D., Han, X., Gao, Y., Hu, Y., Zhang, S., and Zhao, H. Pyramidinfer: Pyramid kv cache compres- sion for high-throughput IIm inference. arXiv preprint arXiv: 2:Xiv:2405.110 12532, 2024.
Meta AL. Introducing Llama 3.1, 2024. URL https: //ai .ett. com/booooo//ooooooo bl molog/metta almaaama33 3- Ac- cessed: 2024-08-21.
Zhang, X., Chen, Y., Hu, S., Xu, Z., Chen, J., Hao, M., Han, X., Thai, Z.,, Wang. S., Liu, Z., et al. bench: Extending long context evaluation beyond 100k tokens. In Proceed- ings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 15262-15277, 2024a.
Ribar, L., Chelombiev, I., Hudlass-Galley, L., Blake, C., Luschi, C., and Orr, D. Sparq attention: Bandwidth- efficient Ilm inference. arXiv preprint arXiv:2312.04985, 2023.

---

VateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Zhang, Z., Sheng, Y., Zhou, T., Chen, T., Zheng, L.,, Cai, R., Song, Z.,, Tian, Y., Ré, C.,, Barrett, C., al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36:34661-34710 2023.
Zhang, Z.,, Liu, S., Chen, R., Kailkhura, B., Chen, B., and Wang, A. Q-hitter: A better token oracle for efficient Ilm inference via sparse-quantized kv cache. Proceedings of Machine Learning and Systems, 6:381-394, 2024b.
Zhao, Y., Wu, D., and Wang, Alisa: Accelerating large language model inference via sparsity-aware kv caching. In 2024 ACM/IEEE 5 st Annual International Symposium on Computer Architecture (ISCA), pp. 1005-1017. IEEE, 2024.
Zhu, Y., Yuan, H., Wang, S., Liu, J., Liu, W., Deng, C., Chen, H., Liu, 7.,, Dou, Z., and Wen, J.-R. Large language models for information retrieval: A survey, arXiv preprint S01:::2308.00100,, 2023.
12

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
A. Further Observations
We expanded our exploration of sequential consistency to a wider selection of models, primarily focusing on the popular models mentioned in the main text: Llama-3-8B- 8B-IM (Gradient, 2024a), Llama-3.1-88 (Meta AI, 2024). Phi-3-128K (Abdin al., 2024), and Yi-9B-200K (AI al., 2024). In Figure 9, visualized the attention weights heatmap for these four models, illustrating the presence of both consistent and adaptive heads across various layers. This visualization supports the generality of our observations. Consistent with the setup described in the main text, the heatmap in the figure comprises attention weights associated with the last 20 query tokens during the pre-filling stage and all query tokens during the decoding stage, employing causal mask. And the samples are randomly excerpted from the WikiText-2 (Merity et al., 2016) dataset.
B. Experiment Details
B.1. Implementation Details of Experiments
During the identification stage of CateKV, employed observation window and temporarily excluded initial tokens and recent tokens from the context window. We set Labss to 64, while Linit and Lyee were defined as 1/32 and 1/128 of the sparse budget, respectively. We constructed the reference dataset based on the Variable Tracking task from the RULER Benchmark, which comprises 100 samples, each with a length of 128K, distinct from the test set. The sparse budget was set at 2048. According to the performance on the reference dataset, we selected the most appropriate percentile threshold I and scaling factor a for each model. For the percentile threshold k, Llama3 and Llama3. were set at 0.996 and 0.984, respectively, while other models were set 0.99, For the scaling factor a, Llama3. and Yi were set at 0.8, while other models were assigned value of 1.0.
For the baseline methods, we configured the observation windows of SnapKV (Li et al., 2024) and PyramidKV (Cai et al., 2024) to 32 and set the 3 in PyramidKV to 20. For Streaming (Xiao et al., 2023), the initial tokens were set to 128. Regarding Duoattention( (Xiao et al., 2024b), we conducted experiments using the attention patterns provided by their code available on GitHub.
B.2. Additional Results on RULER
B.2.1. PERFORMANCE OF DIFFERENT CONTEXT LENGTHS ON RULER
We also conducted evaluations on various context lengths within the RULER benchmark. The Table presents the performance of CateKV on tasks with context lengths from 8K to 256K. CateKV is comparable to full attention in terms of all lengths and average results and even shows slight improvements in performance at certain lengths when 0.4 and n 1.0.
Table 5: Performance of different context lengths on RULER
Methods
8K
16K
32K
64K
128K
256K
Avg.
Llama-3-8B-IM
91.47
92.87
90.31
86.44
84.10
79.79
87.50
CateKV
91.28
92.11
90.37
86.86
84.61
81.53
87.79
P2i-
92.02
91.42
91.24
87.89
72.06
86.93
CateKV
92.68
92.54
92.04
88.78
71.69
87.55
Llama-3.1 -31BBBB
94.78
94.95
94.61
93.02
84.55
92.38
CateKV
94.66
94.68
94.58
93.03
84.66
92.32
Yi-9B-200K
87.54
82.33
72.06
69.19
64.52
75.13
CateKV
87.17
81.68
71.85
69.25
65.76
75.14
B.2.2. COMBINE WITH KV RETRIEVAL METHODS
We combine CateKV with Quest (Tang et al., 2024b) and ShadowKV (Sun et al., 2024) and compare their performance with the baseline under the same computational budget at a length of 128K. The results are shown in Table CateKV helps
13

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Table 6: Performance (%) of CateKV combined with KV retrieval methods. 'Budget' refers to the computational budget for sparse attention. CateKV can reduce memory. CateKV can help KV retrieval methods reduce memory usage to 41 % while maintaining accuracy.
Methods
Budget
N-S1
N-S2
N-S3
N-MK1
N-MK2 N-MK3
FWE
N-MQ
N-MV QA-1
QA-2
VT Avg.
1amm--3-B-IMM
100%
100.00
100.00
100.00
98.96
98.96
41.67
71.88
98.69
96.35
73.96
50.00
78.75 84.10
SnapKV
1.6%
100.00
100.00
14.58
98.96
96.88
0.00
61.11
98.44
96.88
68.75
48.96 79.38
72.00
Py
1.6%
100.00
100.00
10.42
98.96
96.88
0.00
56.60
98.18
95.58
70.83
48.96
80,42 71.40
Quest
1.6%
100.00
100.00
100.00
98.96
97.92
19.79
58.33
98.96
96.61
72.91 52.08
80.20 81.31
CuuekV+Quest
1.6%
100.00
100.00
100.00
97.92
97.92
19.79
58.33
98.96
94.27
73.96
51.04
82.29 81.21
ShadowKV
1.6%
100.00
100.00
100.00
97.92
93.75
21.88
75.69
98.96
96.09
72.92
50.00
78.96 82.18
1.6%
100.00
100.00
100.00
97.92
89.58
21.88
75.35
98.70
94.79
71.88
51.04
81.25
81.86
Phi-3-Mini-128K
100%
96.88
90.63
95.83
83.33
65.63
37.50
87.15
72.14
66.67
63.54
39.58
65.83 72.06
SnapKV
1.6%
98.21
38.54
1.04
42.71
11,46
0.00
60.76
8.59
2.60
62.50
38.54 60.63 35.47
PyramidKV
1.6%
97.92
39.58
0.00
46.88
11.46
0,00
56.94
10.16
2.08
59.38
39.58 60.42 35.37
Quest
1.6%
96.88
92.71
96.88
80.21
57.29
20.83
57.29
69.53
63.02
64.58
39.58 63.75 66.88
+uuet
1.6%
96.88
92.71
96.88
80.21
57.29
18.75
55.56
68.75
64.32
64.58
39.58 62.50 66.50
ShadowKV
1.6%
95.83
88.54
90.63
80.21
54.17
21.88
77.43
63.28
51.28
62.50
38.54
63.75 65.71
CatekV+Shadowk
1.6%
97.92
87.50
92.70
77.08
55,20
18.75
74.31
64.06
55.99
62.50
38.54
65.83 65.87
Llama-3, 1-88B
100%
100.00
100.00
98.96
98.96
90.63
63.54
71.53
98.96
95.31
81.25
46.88
68.54 84.55
SnapKV
1.6%
100.00
100.00
41.67
98.96
79.17
0.00
59.72
97.14
91.67
81.25
44.79
62.92 71.44
PyramidKV
1.6%
100.00
100.00
33.33
98.96
81.25
1.04
56.25
95.83
93.48
81.25
45.83
65.00 71.02
Quest
1.6%
100.00
100.00
100.00
98.96
78.13
4.17
59.03
98.70
94.01
80.21
50.00
68.96 77.68
V+tesv+
1.6%
100.00
100.00
100.00
98.96
78.13
3.13
62.15
97.92
90.63
82.29
47.92 66.88 77.33
ShadowKV
1.6%
100.00
100.00
98.96
98.96
77.08
13.54
70.49
98.18
90.36
81.25
48.96
64.17 78.50
CateKV+Shadow VV
1.6%
100.00
100.00
100.00
98.96
73.96
13.54
65.97
98.44
90.89
80.21
50.00
67.08 78.25
Yi-9B-200K
100%
100.00
100.00
98.96
85,42
63.54
18.75
89.24
66.41
32.55
45.83
38.54
35.00 64.52
SnapKV
1.6%
100.00
93.75
5.21
80.21
6,25
0.00
75.69
54.95
18.23
40.63
36.46
52.92 47.02
PyramidKV
1.6%
100.00
94.79
4.17
79.17
5.21
0,00
85.76
55.73
15.63
41.67
33.33
51.45 47.24
Quest
1.6%
100.00
97.92
98.96
85.42
64.58
4.17
67.01
66.14
38.39
42.71
36.46
48.33 62.51
CateK Queest
1.6%
100.00
100.00
98.96
85.42
70.83
5.21
66.67
63.28
37.24
40.63
37.50
50.21 62.99
ShadowKV
1.6%
100.00
100.00
97.92
87.50
60.42
2.08
75.35
59.64
34.11
43.75
37.50
54.79 62.76
CatcK WShadwwSa
1.6%
100.00
100.00 97.92
84.38
58.33
2.08
82.29
59.38
33.85
43.75
36.46
47.29 62.14
reduce the memory usage of Quest and ShadowKV and significantly outperforms KV Eviction methods in terms of accuracy with the same computational load.
B.3. Full Longbench Results
We present the complete experimental results for the Longbench in Table 7. We integrate CateKV with both the Full Attention and KV retrieval methods, Quest(Tang et al., 2024b) and ShadowKV (Sun et al., 2024), and evaluate its performance on all 21 tasks in Longhench. The results showed that this integration did not lead to any significant drop per-task accuracy, and the average accuracy even outperformed the original methods, despite retaining only 42% of the KV cache size. For around half of the tasks, the combination of CateKV with the original methods leads slight improvement in performance.
B.4. Additional Results in Needle In Hystack
Figure B.4 displays the performance of the Llama3. Phi-3-Mini- 128K, and Yi-9B-200K models on the 'Needle In A Haystack' task. Compared to full attention, CateKV shows varied performance across different context windows and needle depths, but maintains overall comparable performance. This suggests that CateKV does not significantly affect the models' capacity to access and retrieve long-context semantic information.
B.5. Additional Results on Larger Models
We evaluated the performance of CateKV on larger models, setting the context length according to the maximum supported by each model-128k for Qwen2.5-32B and Yi-34B-200K, and 16k for Phi-4-14B. As shown in Table 8, CateKV scales effectively, achieving near full-attention accuracy on the 30B and 14B models, outperforming baseline methods such as SnapKV and PV.
14

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Table Full LongBench results with Llama-3-8B-IM.
Metrics
Full
CateKV
Quest
CateKV+Quest
ShadowKV
CateKV+ShadowYY
Average
31.27
31.48
30.90
31.03
30.77
30.94
NarrativeQA
18.61
18.64
19.54
17.93
18.43
17.74
Qasper
25.83
27.00
27.00
26.20
25.39
26.38
MuluFieldQAAen
48.06
48.17
45.80
45.72
45.59
46.63
MultiFieldQA-zh
33.76
33.68
34.23
33.37
34.23
33.65
HotpotQA
36.35
36.44
35.79
36.84
38.00
37.64
2 WikiMuutihopOA
25.17
24.61
25.48
24.07
24.92
25,98
MuSiQue
21.08
20.41
20.18
19.56
20.70
20.22
DuReader
30.98
28.62
29.23
27.36
29.82
27.91
GovReport
23.38
23.45
23.96
23.53
22.35
22.85
QMSum
25.45
24.74
24.59
24.66
24.67
24.29
MultiNews
22.63
21.42
23.30
21.10
23.53
21.10
VCSUM
14.19
13.90
14.21
13.93
13.86
13,86
TREC
39.00
41.83
39.11
39.49
37.69
39.49
TriviaQA
16.81
16.91
16.67
16.73
17.08
16,91
SAMSum
26.46
26.59
26.66
25.16
26.02
25.61
LSHT
31.58
32.00
24.75
33.25
29.68
29.96
PassageCount
1.00
1.00
1.00
1.00
1.00
1.00
PussageRetrieval-en
81.00
80.50
74.50
80.50
80.00
80.50
Pu
43.73
43.61
42.85
42.50
39.39
38.98
LCC
48.31
50.08
51.30
51.45
49.06
50.69
RepoBench-P
43.21
47.58
48.73
48.27
43.84
48.45
Table 8: Perforrance (%) of CateKV on larger models
Methods
Cache
N-S1
N-S2
N-S3
N-MKI N-MK2
N-MK3
FWE
N-MQ
N-MV
QA-1
QA-2
VT
Avg.
Owen2.5-32B
100%
100.00
87.50
97.92
70.83
15.63
7.29
90.28
87.24
85.16
51.04
41.67
85.41
68.33
SnapKV
41%
100.00
88.54
51.04
69.79
12.50
2.08
88.54
76.82
76.82
51.04
41.67
85.83
62.06
PyramidKV
41%
100.00
87.50
46.88
66.67
8.33
L.04
84.02
66.93
67.71
48.96
41.67
84.79
58.71
CateKV
41%
100.00
86.46
95.83
71.88
14.58
6.25
89.58
86.88
86.28
50.00
43.75
86.67
68.18
Y1-44B200K
100%
100.00
100.00
100.00
92.71
70,83
47.92
86.11
97.14
92.45
68.75
47.92
88.05
82.66
SnapKV
41%
100.00
97.92
80.21
90.62
22.92
17.71
81.25
91.15
72.14
67.71
47.92
86.25
71.32
PyramidKV
41%
100.00
100.00
68.75
91.67
26.04
12.50
82.99
91.15
79.43
69.79
47.92
86.46
71.39
CateKV
41%
100.00
100.00
100.00
92.71
73.96
47.92
85.12
97.14
91.15
67.71
46.88
87.08
82.47
Phi-4-14B
100%
100.00
97.92
100.00
100.00
97.92
100.00
98.96
98.96
99.22
80.21
67.71
100.00
95.08
SnapKV
43%
100.00
100.00
100.00
93.75
3.13
99.31
97.66
99.22
82.29
66.67
100.00
79.11
PyramidKV
43%
100.00
100.00
3.13
100.00
94.79
5.21
98.96
98.44
98.44
80.21
67.71
100.00
78.91
CateKV
43%
100.00
98.96
100.00
97.92
98.96
100.00
99.31
98.44
99.48
78.13
67.71
99.79
94.89
15

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Consistent Head
Adaptive Head
Layer Head
Layer Head
Layer 5 Head
Layer Head
Pro Filling
Decoding
hrce
Rien
(a)
Llama-3-8B-IM
Consistent Head
Adaptive Head
Layer Head
Layer 23 Head
Layer 5 Head 2
Layer 14 Head
Pro filling
Decoding
(b) Llama-3.1-8B
Consistent Head
Adaptive Head
Layer Head
Layer 28 Head
Layer Head 14
Layer 26 Head 28
Pro: filling
Decodingg
Then
100
Indiic
(c) Phi-3-Mini-128K
Consistent Head
Adaptive Head
Layer Head
Layer 24 Head
Layer 5 Head
Layer 27 Head
Pro- filling
Decoding
60
(d) Yi-9B-200K
Figure 9: Sequential consistency in Llama-3-8B-Ine IM, Llama-3.1-88 Phi-3-Mini- Mini--iini- and Yi-9B-200K
16

---

CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration
Needle in Haystack Llama-3.1 3-8-88 Instruct
Needle in Haystack Uama-3.1 3.1-88 Instruct w/ Cate
11
Deplh Percent
Depth
0.2
02
254
20k
proee
0.0
2000
0.0
Context Length
Context Length
(a) Llama-3 3.1-88 11-8--Iune Instructt
(b) Llama-3, 3.1-8B Instruct w/ CateKV
Haystack Phi-3-mini-11 12ktinitk-in
Needle Haystack 128k instruct w/CatekV
Depth Percent (%)
Depth Percent
0.6
0.6
48
44
0.4
04
0.
02
28c
2255.
11
Length
Length
(c) Phi- Phi-3-mint 128k-instruct
(d) Phi-3-mint miiin--18k-iiie instructt -aniitrtttn w/ CateKV
Haystack
Haystack w/CateVV
Depth Percent (18)
22-
Depth Percent
0.6
0.6
0.4
044
0.2
02
100
100
N0
20c
Book
Look
2200
Port
2000
Boo
120r
2000
Context Length
Length
Yi-9B-200k
Yi-9B-200k w/ CateKV
Figure 10: NIAH Results Llama-3. Meta AI, 2024), wiw--mmiiii--iiinne- (Abdin et al., 2024) and Yi-9B-200k (AI et al., 2024)
17


Reviews:
[{"review_id": "IhjENfNYKB", "reviewer": "Reviewer_3ByN", "summary": "CateKV introduces a hybrid KV cache optimization method that improves long-context LLM inference efficiency by leveraging sequential consistency in attention heads. The key insight is that certain attention heads exhibit stable attention patterns across both pre-filling and decoding stages, while others remain highly dynamic. Based on this observation, CateKV: (1) Classifies attention heads into two types:\nConsistent heads: Retain only a subset of KV pairs based on pre-filling attention patterns. Adaptive heads: Retain most KV pairs to ensure flexible attention computation. (2) Uses a coefficient-of-variation (CV)-based scoring algorithm to differentiate between consistent and adaptive heads. (3) Applies selective KV retention, where consistent heads store a minimal set of critical tokens, while adaptive heads retain most of their KV pairs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank the reviewer for your valuable time and constructive feedback. Below, we provide our responses point-by-point.\n\n> Experiments: Latency breakdown\n\nWe very appreciate the reviewer's constructive suggestion, and follow the advice to present a fine-grained latency analysis ([here](https://anonymous.4open.science/r/CateKV-rebuttal-1A3F/latency_breakdown.jpg)) for your reference.\n\n>Missing References\n\nThank you for your recommendation. We will carefully include MagicPIG and references suggested by other reviewers in the discussions of the submission.\n\n>W1: Assumption that ... may lead to inconsistencies.\n\nGiven a certain long-context input, we conjecture that the functionality of each head can be well characterized, even for the head where the focus may change. Informally, it resembles the functionality of human brain regions, which are categorized to play different roles. This pattern stability is well supported by empirical findings in DuoAttention, our cross-model consistency ([here](https://anonymous.4open.science/r/CateKV-rebuttal-1A3F/cross_model.jpg)) and cross-task stability analysis ([here](https://anonymous.4open.science/r/CateKV-rebuttal-1A3F/cross_task.jpg)), which we believe is inherently related to the working mechanism of LLMs. Regarding the implication of this phenomenon, we would like to give a plausible explanation: during inference, LLMs rely on both\n\n- Heads that dynamically adapt to task-specific information, i.e., adaptive heads. For retrieval tasks with dynamic focus shifts, adaptive heads retaining more KV cache specifically handle such varying information.\n\n- Heads that consistently attend to globally important tokens, i.e., consistent heads. Figure in this [link](https://anonymous.4open.science/r/CateKV-rebuttal-1A3F/Similar_focus.jpg) demonstrates that the positions focused on by consistent heads exhibit strong similarity, indicating that some tokens are crucial for the model's understanding globally.\n\n>W2: Fixed Ratio of Adaptive vs. Consistent Heads.\n\nFirst, the reason that we chose a fixed ratio here is that we focus on the task-agnostic scenario where previous works primarily considered. This ensures a fair comparison with the baselines under the same settings.\n\nSecond, CateKV can easily adapt to task-aware scenarios by setting task-adaptive head ratios. The table in this [link](https://anonymous.4open.science/r/CateKV-rebuttal-1A3F/task_aware.jpg) exhibits different adaptive head ratios for tasks on RULER-128K (LLaMA-3.1-8B), where adjusting the ratio per task allows for lower ratios without sacrificing accuracy. \n\nWe will add a more detailed discussion in the revised submission.\n\n>W3: No Explicit Theoretical ... retention accuracy.\n\nTo address the concern, we present the following theoretical analysis of CateKV.\n\n**Lemma 1:** Let $G$ denote our CV-based function hypothesis, $F$ denote the real-value class defined by the binary cross-entropy loss composite on $G$, and $N$ denote the sample number of the reference dataset. Then, with the probability $\\delta$, we have the Rademacher complexity bound,\n\n$\\forall f\\in F,  P_{\\text{head}}\\left(\\mathbb{E}[f]-\\frac{1}{N}\\sum_{n=1}^Nf_n \\leq 2\\mathcal{R}_N(F)+\\sqrt{\\frac{2\\log{\\frac{2}{\\delta}}}{N}}\\right)\\geq 1-\\delta$,\n\nwhere $\\mathcal{R}_N(F)$ is the conditional Rademacher average. \n\nLet $P_1$, $P_2$ denote respectively the probabilities of correctly classified consistent heads and adaptive heads, and $\\bar{P}\\_1$, $\\bar{P}\\_2$ denote respectively the probabilities of misclassified consistent heads and adaptive heads, where we have $P\\_1+P\\_2=P\\_{\\text{head}}$ and $\\bar{P}\\_1+\\bar{P}\\_2=1-P\\_{\\text{head}}$. Then, we can decompose the probability in the above lemma with fine-grained analysis as follows.\n\n**Theorem 1:** Let $\\eta_1$, $\\eta_2$ denote respectively the retention ratios of consistent heads and adaptive heads, and $\\eta_1^*$, $\\eta_2^*$ denote their optimal retention ratios correspondingly. Define the retion accuracy of different cases $r_{i,j}=\\eta_i^*\\mathbb{1}[\\eta_j > \\eta_i^*]+\\eta_j(1-\\mathbb{1}[\\eta_j > \\eta_i^*])$ by comparsing the retention budgets with the optimal budgets, and the hypothesis that the query attention score is the best description in order holds with the probability $\\lambda$. Then, the token retention accuracy has the following inequalities,\n\n$P\\_{\\text{token}} = \\lambda(r_{1,1}P\\_1 + r\\_{2,2}P\\_2 + r\\_{2,1}\\bar{P}\\_1 + r\\_{1,2}\\bar{P}\\_2)\\geq \\lambda \\left(\\min(r\\_{2,1}, r\\_{1,2}) + \\left[\\min(r\\_{1,1}, r\\_{2,2})-\\min(r\\_{2,1}, r\\_{1,2})\\right]P\\_{\\text{head}}\\right)$\n\nIn this theorem, three factors, i.e., $\\lambda$, budge control part and head identification accuracy $P_{\\text{head}}$ make critical effect about the worst-tken retention accuracy in CateKV, which are actually also verified in the submission (like Figures 3, 4, 7 and Tables 2, 3). Due to space limitation, we will give more details and remarks on this theorem in the reviewer-author discussion phase.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No theory in this paper.", "experimental_designs_or_analyses": "The experiments are well-structured but could be strengthened with:\n- Latency breakdown.", "relation_to_broader_scientific_literature": "- Head-Level KV Compression Methods\n- Hybrid KV Retention Approaches", "essential_references_not_discussed": "[1] MagicPIG: LSH Sampling for Efficient LLM Generation", "other_strengths_and_weaknesses": "Strengths\n- Novel Sequential Consistency-Based KV Management. Unlike prior work that heuristically prunes KV caches (SnapKV, StreamingLLM) or dynamically retrieves KV pairs (Quest, ShadowKV), CateKV exploits consistent attention patterns across layers.\n\nWeaknesses\n- Assumption That Pre-Filling Attention Patterns Remain Consistent During Decoding. CateKV relies on the assumption that stable attention patterns persist, but certain adaptive behaviors in retrieval tasks (e.g., dynamically changing focus) may lead to inconsistencies.\n- Fixed Ratio of Adaptive vs. Consistent Heads. The paper fixes the adaptive head ratio (r = 0.4) without dynamically adjusting it based on task or context length, which may be suboptimal in some settings.\n- No Explicit Theoretical Bound on Eviction Performance. The CV-based classification method is empirically justified but lacks a formal guarantee on its worst-case token retention accuracy.", "other_comments_or_suggestions": "See Strengths And Weaknesses", "questions_for_authors": "Thank you to the authors for their latest response. Although the underlying assumptions do not fully convince me, I will raise my score to a 3, considering that similar work has been accepted at top conferences.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ziik9qKwmW", "reviewer": "Reviewer_cc5K", "summary": "This paper studies the long-context inference acceleration of LLMs through sequential consistency patterns. By observation of distinguishing activation of attention heads, the authors classified them into consistent heads and adaptive heads, which can be used to promote the decoding acceleration. Different from previous methods that considered the acceleration of prefilling stages or decoding stages independently, the proposed method discovers the sequential consistency estimated at the prefilling stages efficiently help the decoding both in memory and computation speedup. Extensive experiments show the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We appreciate the supportive comments and the comprehensive evaluation of our method. In the following, we provide our responses point-by-point.\n\n> Weakness 1: About setting the best threshold\n\nWe select the threshold based on a fixed ratio of consistent-to-adaptive heads, as while CV scores vary significantly across inputs, the proportion of heads exhibiting consistent patterns remains remarkably stable within the model architecture.\n\nIn task-agnostic scenarios, determining the optimal threshold or adaptive head ratio for each sample is challenging. One potential approach is to incorporate attention weight recall as an additional criterion in the head classification process. If the attention weight recall exceeds a threshold (denoted as $t$), these heads can also adopt the consistent pattern.\n\nAs shown in the table below (LLaMA-3-8B,$r=0.4$,$t=0.98$), this recall-threshold method enables input-adaptive ratio adjustment while maintaining performance (Avg 84.32% vs 84.61% CateKV). However, the marginal gains suggest this approach may not be universally optimal. We will further explore dynamic threshold adjustment methods in future work.\n\n|Methods|N-S1|N-S2|N-S3|N-MK1|N-MK2|N-MK3|FWE|N-MQ|N-MV|QA-1|QA-2|VT|Avg|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|CateKV ($r=0.4$)|100.00|100.00|100.00|98.96|97.92|41.67|71.88|98.44|96.88|73.96|50.00|85.63|84.61|\n|CateKV+recall threshold|100.00|100.00|100.00|98.96|97.92|42.71|71.88|98.18|96.35|71.87|50.00|83.96|84.32|\n|Average adaptive head ratio|34.38%|37.13%|37.16%|37.13%|38.67%|36.72%|35.54%|37.23%|37.20%|37.25%|37.89%|32.03%|36.53%|\n\nFor task-aware scenarios, please refer to our response to Reviewer 3ByN'Weakness 2, where we discuss dynamic ratio selection in task-aware contexts.\n\n> Weakness 2: About the meaning of Topk curve.\n\nFigure 4 compares different methods' ability to approximate the ground-truth top-k attention weights during decoding. The top-k curve represents the upper bound of achievable recall, as it directly uses the actual highest attention weights (which are unknown in advance during real inference).\n\nThis does not imply top-k is universally \"better,\" but rather that it serves as the theoretical optimum. The key advantage of CateKV/Quest is that they avoid computing full attention, making them practical for real-world deployment.\n\n>Weakness 3 and Question: Comparison Between CateKV and DuoAttention\n\n1. Differences between CateKV and DuoAttention: From a conceptual perspective, consistent heads emphasize the overall similarity of attention across different sequences, while Streaming Heads prioritize whether initial and recent tokens cover most of the attention. Thus, in terms of token selection, streaming heads only focus on the initial and recent tokens for attention, whereas consistent heads have a broader search space. To further illustrate this, we randomly selected 100 samples from WikiText and performed inference using LLama3-8B. Our analysis shows that approximately 72% of the tokens selected by consistent heads do not belong to the initial or recent tokens, demonstrating greater flexibility compared to streaming heads.\n\n2. Analysis of the rapid drop: From the perspective of attention recall, the number of streaming heads within a model is inherently limited. As shown in Figure 4, a larger proportion of heads recall less than 0.8 of the attention weights under the streaming pattern. An overreliance on the streaming pattern results in significant information loss, which explains the rapid drop in the performance of DuoAttention when the ratio is below 0.4. In contrast, even with an aggressive increase in the proportion of consistent heads, the consistent pattern effectively preserves critical tokens, including those that capture global information from prior attention. These retained tokens enhance the robustness of CateKV, making it more effective than DuoAttention.\n\n> Suggestion: Using Soft Attention Weight Matrix for Method Design\n\nUtilizing a soft attention weight matrix is an intuitive approach. However, we believe that the values in the soft attention weight matrix reflect the importance of individual tokens, whereas the binarized observation matrix used in CateKV more effectively captures the relative importance of tokens. Since sparse attention methods aim to identify the top-k important positions, sequence similarity should be evaluated by the alignment of their top-k attention indices, which reflects a relative relationship. Additionally, the values of attention weights fluctuate with the query, and attention sinks in some heads complicate the use of a soft attention matrix for classification.\n\nWe also conducted an experiment where we removed the binarization step from the identification process (a soft version). When $r = 0.5$, on the RULER-128K niah-multikey3 task, the performance dropped by 14.58 points (from 63.54 to 48.96) compared to full attention on LLama-3.1-8B.", "claims_and_evidence": "The claims presented in the submission are well-supported by both intuitive understanding and empirical evidence. The authors provided the empirical statistics regarding the sequential consistency in the main part and appendix. The results demonstrated the substantial effectiveness of the proposed methods.", "methods_and_evaluation_criteria": "The authors designed a proper method to distinguish consistent heads and adaptive heads, and on that basis, the efficiency in KV cache reduction and compute speedup has been gained. The evaluation follows the common bench, which covers different dimensions including the context length, different backbones and performance against the acceleration.", "theoretical_claims": "Not Applicable.", "experimental_designs_or_analyses": "I have checked experimental parts and their analysis including the complementary results in the appendix. The experimental results are sound and adequately demonstrate the effectiveness of the proposed CateKV. The results demonstrate the consistent acceleration benefit and the gain when combined with the conventional acceleration methods.", "relation_to_broader_scientific_literature": "LLM inference acceleration is tightly related to many areas in the recent AI communities, since it is a trend to integrate LLM to enhance the performance of many tasks. Since it is always time-intensive when the input or the output of LLMs is very long, it is very demanding to explore the inference acceleration of LLMs, which is critical to many AI applications in the era of foundation models.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths\n- The proposed method captures the essential patterns during the inference of LLMs, where the evidence of the sparse computation inherent in the transformers can be estimated along with the sequential consistency. The design is natural and simple yet effective.\n- The experiments and evaluations are comprehensive, covering a broad range of LLM inference benchmarks. The experimental results demonstrate the effectiveness of CateKV. Besides, the experiments combined with the previous acceleration methods demonstrate the orthogonality of CateKV. \n- The paper is well-written, clearly structured, and easy to follow.\n\nWeakness:\n- It is unclear how to set the threshold to distinguish consistent heads and adaptive heads. Do we need some searching-based strategy to find the best threshold or some other ways?\n- For figure 4, it seems that CateKV has the similar trend with Quest, which both are not good than Top-k. What does this mean? Is it means that the Top-k strategy is actually a good way to find the sparse compute structure? Please claim this details. \n- In Figure 6, why DuoAttention has a so rapid drop in performance at the ratio of 0.4. Please provided more analysis and claimed that why CateKV could maintain the effectiveness.", "other_comments_or_suggestions": "- It is better to add more discussion about why not choose a soft attention weight matrix to design the method. Intuitively, this can be more precise and flexible. The authors could add more discussion in terms of this point.", "questions_for_authors": "- What is the difference between CateKV and DuoAttention? Can you provide more qualitative comparison between the selected tokens of CateKV and those of DuoAttention. Such an result can be more convincing to reflect the novelty of CateKV.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ho9nHehPV6", "reviewer": "Reviewer_5Grq", "summary": "This paper proposes a novel KV cache algorithm that calculates the coefficient-of-variation of attention tokens at each layer. Specifically, it identifies consistent head and adaptive head where most of the KV cache can be reduced from the consistent head. In experiments, author demonstrate the effectiveness of the method on multiple long-context evaluation datasets. The performance is superior against existing KV-cache methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank the reviewer for your valuable time and constructive feedback. In the following, we provide our responses point-by-point.\n\n> Claims: About the design of observation window\n\nHere, we provide a more detailed explanation regarding the design of the observation window:\n\n1. **The observation window helps avoid quadratic memory and computational costs**. In the pre-filling stage, the full attention matrix has size $n \\times n$ (where $n$ is the context length). Analyzing the full attention matrix directly increases the computational complexity from $O(n)$ to $O(n^2)$, posing challenges in memory and computation, especially for long inputs. Using the full attention matrix for head classification led to an out-of-memory (OOM) error on a single A100 GPU for inputs larger than 8k tokens\n\n2. **The attention within the observation window is more representative**. Due to the causal mask, the last query tokens capture global information similar to what is needed during decoding. Including intermediate query tokens may cause erroneous guidance, as these tokens have partial information. The table below shows that increasing the observation window size from 64 to 4k with $r = 0.4$ results in negative performance gains.\n\n|Methods|N-S1|N-S2|N-S3|N-MK1|N-MK2|N-MK3|FWE|N-MQ|N-MV|QA-1|QA-2|VT|Avg|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|CateKV ($L_{obs}=64$)|100.00|100.00|100.00|98.96|97.92|41.67|71.88|98.44|96.88|73.96|50.00|85.63|84.61|\n|CateKV ($L_{obs}=4000$)|100.00|100.00|98.96|97.92|97.92|19.79|66.67|99.21|97.92|70.83|48.96|76.25|81.20|\n\nWe will enrich our explanation and add the above analysis in the submission to well justify our choice. Thank you very much for pointing out the insufficiency of this claim.\n\n> Q1: Applicability of CateKV to traditional LLM Eval tasks and the role of long-context\n\nWe follow the research line of LLMs under long-context inference, which causes a significant bottleneck in memory consumption and computation latency. Regarding its practical value, some examples, like the RAG (retrieval-augmented generation) applications, long-document understanding, multi-turn interaction, etc., easily make the LLMs face long-context inference scenarios. In this case, it is critical to accelerate LLM inference to avoid the vanilla catastrophic response speed (it can be minute-level for A100 with 80G memory under 100k-long context). \n\nNaturally, the existing long-context acceleration methods, including CateKV, are applicable to traditional short-context LLM evaluation datasets. We tested the performance of CateKV and baseline methods on MMLU and MMLU-Pro, with all methods retaining approximately 25% of the KV cache and utilizing a one-shot prompting approach. The results in the table below show that CateKV still maintains performance comparable to full attention. It is worth noting that in short-context scenarios, attention to recent tokens is more likely to retain complete contextual information, allowing simpler methods (such as StreamingLLM) to maintain much of the performance.\n\n|Methods|MMLU|MMLU-Pro|\n|-|-|-|\n|Llama3-8B|59.70|30.71|\n|StreamingLLM|58.98|30.04|\n|SnapKV|59.60|30.43|\n|PyramidKV|59.60|30.43|\n|CateKV|59.60|30.71|\n\n> Essential Reference: \n[1] Model tells you what to discard: Adaptive kv cache compression for llms\n\nThank you for the recommendation and we will incorporate the discussion of FastGen [1] in Section 2.2. For the comparison, we need to clarify that in our practice, FastGen easily incurs OOM when going beyond 8K. This is mainly because of the usage of the complete attention matrix during its pre-filling stage. We will add more explanations in the updated version.\n\n> Q2: How is the method generalize without reference dataset ?\n\nWhile CateKV uses a reference dataset to achieve static identification, the method proposed in Section 3.2 actually can perform without a reference dataset, yielding the dynamic identification. In the following table, we show that the dynamic identification method exhibits similar performance as the reference-based static identification method, both comparable to or surpassing full attention, highlighting the generalizability of CateKV. \n\n| Method | RULER-128K(Llama3) | Longbench(Llama3) | RULER-128K(Llama-3.1) | Longbench(Llama-3.1) |\n|-|-|-|-|-|\n| Full | 84.10 | 31.27 | 84.55 | 33.68 |\n| Dynamic ($r=0.4$) | 84.17 | 31.14 | 84.63 | 33.43 | \n| Static ($r=0.4$)| 84.61 | 31.48 | 84.66 | 33.70 |\n| Dynamic ($r=0.3$) | 83.49 | 30.61 | 81.59 | 32.89 | \n| Static ($r=0.3$) | 83.84 | 31.08 | 82.14 | 33.38 | \n\nHowever, the following drawbacks arise without a reference dataset:\n\n- At the pre-filling stage, the extra sample-wise computation needed for head identification increases computational overhead.\n- The need for a complete observation matrix in the pre-filling stage to assist classification prevents integration with sparsification-based pre-filling acceleration methods.\n\nWe will include the above analysis in the submission to improve the clarity.", "claims_and_evidence": "In section 3.2, the author claims \"To save the computational cost, we set an observation window that contains the last query tokens of the input to identify head types and critical tokens. \" while I don't think it's fully justified.", "methods_and_evaluation_criteria": "Yes, except one point\n1. Why the method cannot be applied to traiditional LLM eval dataset? What does long-context matter here?", "theoretical_claims": "This paper does not include theoretical claims.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "It can be used to accelerate the industry LLM serving.", "essential_references_not_discussed": "I am wondering why [1] is not discussed nor compared in the paper.\n\n[1] Model tells you what to discard: Adaptive kv cache compression for llms, ICLR 23'", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is easy to follow with good demonstrations and examples.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can you apply CateKV on traditional LLM Eval tasks? \n\n2. How is the method generalize without reference dataset ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qyl6Gk1eRJ", "reviewer": "Reviewer_Tg7K", "summary": "This paper proposes CateKV, which improves the inference efficiency by adaptively evicting and retrieving KV cache based on sequential consistency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank the reviewer for your valuable time and constructive feedback. In the following, we provide our responses to each question.\n\n> Weaknesses 1: The main concern I have with this paper is the issues of scalability. In the paper, the largest model being evaluated is 9B. It would be better if the authors could provide results on larger models (30B/70B).\n\nWe have tried our best to expand experiments on three larger models (30B&14B) in the following. Due to limited resources, we are unable to finish experiments on 70B models during this rebuttal period, but promise to include the results of 70B models in the final version. \n\n|Methods|Cache|N-S1|N-S2|N-S3|N-MK1|N-MK2|N-MK3|FWE|N-MQ|N-MV|QA-1|QA-2|VT|Avg|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|**Qwen2.5-32B**|100%|100.00|87.50|97.92|70.83|15.63|7.29|90.28|87.24|85.16|51.04|41.67|85.41|68.33|\n|SnapKV|41%|100.00|88.54|51.04|69.79|12.50|2.08|88.54|76.82|76.82|51.04|41.67|85.83|62.06|\n|PyramidKV|41%|100.00|87.50|46.88|66.67|8.33|1.04|84.02|66.93|67.71|48.96|41.67|84.79|58.71|\n|CateKV|41%|100.00|86.46|95.83|71.88|14.58|6.25|89.58|86.88|86.28|50.00|43.75|86.67|68.18| \t \t \t \n|**Yi-34B-200K**|100%|100.00|100.00|100.00|92.71|70.83|47.92|86.11|97.14|92.45|68.75|47.92|88.05|82.66|\n|SnapKV|41%|100.00|97.92|80.21|90.62|22.92|17.71|81.25|91.15|72.14|67.71|47.92|86.25|71.32|\n|PyramidKV|41%|100.00|100.00|68.75|91.67|26.04|12.50|82.99|91.15|79.43|69.79|47.92|86.46|71.39|\n|CateKV|41%|100.00|100.00|100.00|92.71|73.96|47.92|85.12|97.14|91.15|67.71|46.88|87.08|82.47| \t \t \n|**Phi-4-14B**|100%|100.00|97.92|100.00|100.00|97.92|100.00|98.96|98.96|99.22|80.21|67.71|100.00|95.08|\t \t \t \t \t \n|SnapKV|43%|100.00|100.00|7.29|100.00|93.75|3.13|99.31|97.66|99.22|82.29|66.67|100.00|79.11|\n|PyramidKV|43%|100.00|100.00|3.13|100.00|94.79|5.21|98.96|98.44|98.44|80.21|67.71|100.00|78.91|\n|CateKV|43%|100.00|98.96|100.00|97.92|98.96|100.00|99.31|98.44|99.48|78.13|67.71|99.79|94.89|\n\nThe context length was set based on the maximum length supported by the model, with 128k for Qwen2.5-32B, Yi-34B-200K, and 16K for Phi-4-14B. The results in the above table demonstrate that CateKV scales effectively, delivering near-full-attention accuracy for 30B and 14B models, surpassing baseline methods such as SnapKV and PyramidKV.\n\n> Weaknesses 2: Some references [1-3] are missing in the related work for KV cache optimization.\n\nThank you very much for recommending these references, and we will carefully incorporate the discussions of these papers in §2.1 (KV Cache Eviction Algorithm), which is initially summarized as follows:\n    \nKeyformer proposes a score-based KV cache eviction algorithm that selectively retains only 'key' tokens with high attention weights, reducing cache size and memory bandwidth. Q-Hitter introduces a hybrid KV cache eviction criterion combining token importance (Heavy Hitters) and quantization-friendliness, enabling aggressive sparsification and low-bit quantization. ALISA designs a token-prioritization-based KV cache eviction algorithm using Sparse Window Attention (SWA) to dynamically reduce memory footprint, coupled with system-level optimizations for efficient caching-recomputation trade-offs. While these KV cache eviction methods demonstrate computational efficiency, they inherently incur information loss due to the reduction of attention across all heads or the quantization of data precision. In contrast, CateKV preserves the complete KV cache for adaptive heads, maintaining critical contextual information while still achieving efficiency through selective eviction in consistent heads.\n\n[1] Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference, MLSys 2024.\n\n[2] Q-Hitter: A Better Token Oracle for Efficient LLM Inference via Sparse-Quantized KV Cache, MLSys 2024.\n\n[3] ALISA: Accelerating Large Language Model Inference via Sparsity-Aware KV Caching, ISCA 2024.", "claims_and_evidence": "Please see **Other Strengths And Weaknesses**", "methods_and_evaluation_criteria": "Please see **Other Strengths And Weaknesses**", "theoretical_claims": "Please see **Other Strengths And Weaknesses**", "experimental_designs_or_analyses": "Please see **Other Strengths And Weaknesses**", "relation_to_broader_scientific_literature": "Please see **Other Strengths And Weaknesses**", "essential_references_not_discussed": "Please see **Other Strengths And Weaknesses**", "other_strengths_and_weaknesses": "**Strengths**:\n\n1. The paper is easy to follow, with clear writing and presentation.\n2. The evaluation results are good and comprehensive.\n\n**Weaknesses**:\n\n1. The main concern I have with this paper is the issues of scalability. In the paper, the largest model being evaluated is 9B. It would be better if the authors could provide results on larger models (30B/70B).\n\n2. Some references [1-3] are missing in the related work for KV cache optimization.\n\n\n[1] Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference, MLSys 2024.\n\n[2] Q-Hitter: A Better Token Oracle for Efficient LLM Inference via Sparse-Quantized KV Cache, MLSys 2024.\n\n[3] ALISA: Accelerating Large Language Model Inference via Sparsity-Aware KV Caching, ISCA 2024.", "other_comments_or_suggestions": "Please see **Other Strengths And Weaknesses**", "questions_for_authors": "Please see **Other Strengths And Weaknesses**", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces CateKV, a hybrid KV cache optimization method designed to enhance the efficiency of inference in large language models (LLMs) processing long-context tasks. CateKV leverages the insight that certain attention heads demonstrate stable attention patterns, allowing selective retention of key-value (KV) pairs to significantly reduce memory and computational overhead. The reviewers agree that the method presented is novel and well-motivated, distinguishing itself from prior approaches by systematically exploiting sequential consistency in attention heads. 

However, reviewers identified several concerns that authors have mostly addressed in the rebuttal:
+ The reliance on the assumption of persistent attention patterns during decoding potentially limits the method’s applicability in tasks with dynamic retrieval behaviors. The authors provided additional analyses demonstrating cross-model and cross-task stability, partially mitigating this concern.
+ The fixed ratio of adaptive vs. consistent heads could be suboptimal across various tasks and contexts. The authors provided task-aware analyses to suggest potential adaptations for different scenarios, though dynamic ratio adjustments were not originally explored.
+ A theoretical analysis and bound on retention accuracy were initially lacking. In response, authors presented a theoretical Rademacher complexity bound to justify their empirical findings.

The authors did a very good job addressing reviewers' concerns, and reviewers were also quite responsible during the rebuttal period. Overall, the work is considered a solid contribution to ICML, given its practical significance and promising empirical validation. Therefore, I'm recommending acceptance of this work.
Decision: Accept (poster)