ArkVale: Efficient Generative LLM Inference with Recallable Key-Value Eviction
Authors: Renze Chen
Zhuofeng Wang
Beiquan Cao
Tong Wu
Size Zheng
Xiuhong Li
Xuechao Wei
Shengen Yan
Meng Li
Yun Liang
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Learning System
Large Language Model Inference
Key-Value Cache Eviction
Primary area: infrastructure
TL;DR: We propose a method to dynamically evict some KV cache tokens (pages) or recall evicted ones for different query tokens, reducing the memory usage of the KV cache and the latency of attention computation with few accuracy loss.

Abstract: Large Language Models (LLMs) are widely used in today's tasks of natural language processing. 
To support applications like multi-turn chats, document understanding, and content generation, models with long context lengths are growing in importance.
However, managing long contexts brings substantial challenges due to the expansion of key-value cache (KV cache). Longer KV cache requires larger memory, limiting the batch-size thus decreasing throughput. Also, computing attention over long KV cache incurs more memory access, hurting the end-to-end latency.
Prior works find that it is sufficient to use only the recent and high-impact tokens for attention computation, allowing the eviction of less vital tokens to shrink cache size.
Nonetheless, we observe a dynamic shift in token importance across different decoding steps. Tokens initially evicted might regain importance after certain decoding steps.
To address this, we propose ArkVale, a page-based KV cache manager that can recognize and recall currently important tokens evicted before. We asynchronously copy the filled page into external memory (e.g., CPU memory) as backup and summarize it into a much smaller digest by constructing the bounding-volume of its keys. Before attention computation, we measure all pages' importance based on their digests, recall the important ones, evict the unimportant ones, and select the top-ranked pages for attention computation. 
Experiment results show that ArkVale performs well on various long context tasks with negligible accuracy loss under 2k$\sim$4k cache budget and can improve decoding latency to $2.2\times$ and batching throughput to $4.6\times$ because it applies attention on only a small subset of pages and reduce per-sample memory usage of KV cache.

ARK Efficient Generative LLM Inference with Recallable Value Eviction
Renze Chen Peking University crzêpku, edu. cn
Zhuofeng Wang Peking University 22000128270stu pku. edu. en
Beiquan Cao Peking University 22000129880stu, pku. edu cn
Tong Wu
Size Zheng
Xiuhong Peking University
Peking University 22000132128stu, pku. edu. en
Peking University
zhengszēpku. edu cn
1 lixiuhong@pku. edu. cn
Xuechao Wei Peking University
Shengen Yan Infinigence-Al
Meng Li
Peking University meng 110pku. edu cn
xuechao.. wei0pku. edu. cn
yanshengen@gmail.com
Yun Liang" Peking University
er criclyun@pku.coo edu.
Abstract
Large Language Models (LLMs) widely used in today's tasks of natural lan- guage processing. To support applications like multi-turn chats, document under- standing, and content generation, models with long context lengths growing in importance. However, managing long contexts brings substantial challenges due to the expansion of key-value cache (KV cache). Longer KV cache requires larger memory, limiting the batch-size and thus decreasing throughput. Also, computing attention over long KV cache incurs more memory access, hurting the end-to-end latency. Prior works find that it is sufficient to use only the recent and high-impact tokens for attention computation, allowing the eviction of less vital tokens reduce memory footprint. Nonetheless, we observe a dynamic shift in token im- portance across different decoding steps. Tokens initially evicted might regain importance after certain decoding steps. To address this, we propose ARK VALE, a page-based KV cache manager that can recognize and recall important tokens evicted before. We asynchronously copy the filled page into external memory (e.g., CPU memory) as backup and summarizz/compress it into much smaller digest by constructing the bounding-volune of the keys in the KV-page. Before attention computation, we measure pages' importance based on their digests, recall the important ones, evict the unimportant ones, and select the top-ranked pages for attention computation. Experiment results show that ARKV VALE performs well various long context tasks with negligible accuracy loss under 2k~44 cache budget and can improve decoding latency up to 2.2x (1.7x in average) and batching throughput up to 4.6x (3.5x in average). Our code is now available at hattps://githin com/ pku- liang/ ArkVale
*Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

KV Cache Tokens
Generated
Evict
Decoding Step
X
(a) Keep all tokens
(b) Keep recent tokens
(c) Keep Important tokens
(d) Keep Recall Important tokens
Figure I: Comparison of different KV cache eviction works.
Introduction
Large Language Models (LLMs) are rapidly gaining universal presence, underpinning a myriad of natural language processing applications, including dialogue systems 2
52 16. document
summarization [2] [4], code completion [13 46), and question answering [31] The context length
supported by large models is also growing progressively to support more applications like multi-turn
chat [2] 52, [6] and text summarization [28
68 [22 This shift has seen an expansion from an initial range of up 16k, advancing steadily towards lengths of 32k (T. 128k 43 and even 2048k (21).
However, handling long contexts poses significant challenges. The key-value cache (KV cache) of LLMs scales with both the batch size and the length of historical context. For each token generated by an LLM, the query must attend to the entire set of context key-values. On one hand, longer KV caches occupy
memory spaces, limiting batch-size well as throughput. On the other hand, computing attention with long KV cache incurs more memory accesses, hurting the inference latency.
40 reveal sparsity in KV cache, which means that only subset of tokens in the KV cache significantly influence accuracy of attention computation. They propose two characteristics of token importance: locality and persistence. Locality implies that recent tokens tend to be important for current attention, while persistence suggests that tokens previously deemed important are likely to retain their importance over time. They devise algorithms to retain recent (Figure (b)) or vital tokens [58] 37 64
Previous works 58
64
37
23
(Figure | (b)) while evicting older less crucial ones reduce memory usage of KV cache and memory accesses of attention.
tokens 58 37 64
In this work, we delve deeper into the dynamism of token importance, observing that tokens previously deemed unimportant may regain importance over time and vice versa. Previous works ignore this and may risk permanently discarding the tokens that are vital later on, inadvertently decreasing model accuracy. To address these challenges, we propose A ARK VAL.F, inspired by vL..M (36] to organize tokens into pages for fine- mee-grained management of KV cache. Upon filling a KV-page, asynchronously copy it to CPU memory backup, and summarize/compres. it into much smaller digest by constructing a bounding- voouume the keys of the KV-page. Before each attention computation, dynamically estimate the importance of each page based their digests and current query, and selectively recall & evict some pages based on their importance scores (Figure (d)).
Our contribution can be summarized as follows:
We characterize the dynamism of the importance of tokens in the KV cache of LLM, and find that some unimportant tokens may regain importance over time.
We propose ARK VALE, KV cache manager which organize tokens into pages and dynami- cally evict & recall them based on their importance.
We propose a method based on bounding- volume to summarize the pages and estimate the importance of them with given query.
We evaluate ARK VALE against many state-of -ire--of-hhhhttat the-art art KV cache eviction works on various long- context benchmarks. Experimental results show ARK VALE performs well on all the long context tasks with negligible accuracy loss under cache budget of 2k~44 and speedup model decoding latency up to 2.2x x (1.7x in average) and batching throughput up to 4.6x (3.5x average) long context scenarios. Our code is now available at htttts:://ttthiia com pooomppuu---- liang/ ArkVale

---

2 Related Work
Many works have been proposed to extend context window of pre-trained models. One prevalent method is the integration of Rotary Position Embeddings (RoPE) [49]. Fine-tuning RoPE's scaling enables the Llama-2 model
[55] initially handling 4k tokens, be expanded to support 32k tokens in LongChat T and 128k tokens in Yarn-LJama-2
43 Recently, LongRoPE [21] pushes this boundary even further to accommodate up to 2048K tokens. However, as models become more capable of dealing with long context, they also face new challenges in terms of memory usage and inference efficiency. ARK VALE designed to address such issues.
Some training-ane -aaae aware (MQA) [47] and Group- Queur Attention (GQA) [7] aim to train LLMs with fewer attention heads in KV cache. Works like RWKV [22,, RetNet [50], and Mamba [25] propose Linear Attention/RNN to
methods have been proposed to handle these problems. Multi-Quen Query Attention
limit KV cache size. Sparse attention architectures [61 TO 56 17
33 [53 design special sparse pattern of attention during training to control the KV cache size during inference. But these works require much training effort for pre-training or fine-tuning while VALE is training-free method.
45
There are also some post-training methods, which evict tokens in KV cache to reduce memory usage and accelerate attention computation. StreamingLLM (58) and LM-Infinite [26] only keep initial tokens and recent tokens to maintain a fixed-size KV cache. Methods like H2O [64] Scissorhands (37]
and TOVA 44) keep important tokens in KV cache based on the historical current attention scores. categorizes tokens and employs a more nuanced approach for choosing which KV cache tokens to preserve. Keyformer [6] improves the eviction score function by leveraging the Gumbel distribution. Q-Hitter 633 combines V--cache quantization with K KV-cache eviction. These methods rely on historical data to dictate cache eviction and may risk discarding the tokens that are important in the future. Works like IceFormer (38, SparQ (5). ALISA (65, and Quest [51] use post-training sparse attention to alleviate such issue but they require all KV cache residing in memory and thus cannot control KV cache size to optimize memory usage. Many scheduling-
FastGen 23
methods [19 18 60 15 66
[4 36
48
32
27 67 are also employed to optimize memory efficiency
for LLMs or other DNNs, aiming to enhance memory usage and execution latency through proper computation partitioning and scheduling.
3 Background
3.1
Attention Computation and Generative Inference of LLM
The attention computation in a typical LLM involves mixing token-level information of queries Q E R and keys K E T Xd with values V E Rd where d is the hidden-dimension and Sy (skv) means the number of query (key/value) tokens. The attention computation can be formulated as: S = (Q. KT /Vd) E R P == sof softmaXSS) E R = (P. V) E Ra where P is often called "attention map/scores" and P., reflects the importance of key/value token j to query token i. Then, the generative inference process of L.LM mainly consists of two stages: the prefill/prompt stage and the decoding/generation stage. The prefill stage takes prompt sequence with length Sin as input and caches the keys & values computed by each layer of the LLM. The decoding stage uses and updates the KV cache to generate tokens step-by-step, where the current token depends on past tokens' keys & values stored in the KV cache. For the attention in prefill stage, Ske, while Sq and Ske topastttokens 1 in each decoding step.
Si Sq
3.2 Impact of Long Context
For decoding step with batch-size as number of transformer layers as I, history sequence length as s. sulden-dimension as h, and data type as float16, the KV cache requires 4bsh bytes memory accesses for each attention computation and occupies 4blsh bytes of memory in total. The latency & memory breakdown of a decoding step of model 7bb 3.5-32k [1] (1 = 32, h = 4096) with i = and & 29 210 211 212 213 214 225 shown in Figure 2 As the sequence length increases, accessing the KV cache incurs significant overhead, thereby impacting the end-to-end latency of inference. Besides, as the sequence length increases, the KV cache itself consumes more memory space; for instance, with just context length of 16k, batch size of 8 nearly saturates the
3

---

(in a Decoding Step)
Memory Usage (GB)
Relative Latency
4
Other Operations Attention
Parameters
KV Cache
3
100
50
0
0.5k
1k
2k
4k
8k
16k
32k
0.5k
1k
2k
4k
8k
16k
32k
Sequence Length
Sequence Length
(a) Inference lateney of attention and other operations.
(b) Memory usage cache and parameters.
Figure 2: Latency & memory breakdown of decoding step of Long SaanChht-7hhe ab-atv--vvlla 1..-32kk model with batch-size b = 8 and different history sequence-lengths & = 20, 2 211 212 213 214 215 2,16
80GB memory of A100 GPU. This not only hampers the use of larger batch sizes but also poses challenges for deploying models with more parameters.
4 Observation
4.1
Token-level Sparsity of KV Cache
To tackle the aforementioned issues, aim to exploit the sparsity of the KV cache. We collect data by running LongChat-7b-ve
[T] on LongBench [9]. Figure iillstaass the sparsity of the KV caches of different layers. We organize the tokens in KV cache into pages (with page-size=32), and rank the pages of each layer based on the highest attention scores of the tokens within each page for each decoding step. We observe that, in each layer except the initial one, less than 10 pages (320 tokens) contribute more than 99% scores in sum, achieving over 95% sparsity. Thus we can retain only subset KV tokens for attention.
(Ratio of Bottom-Rame -o---Ranke Ranked-Paneeee
10a
Number Top-Ranked-Page
Bettom Ranked- Pages
Top-Ranked- Pages that contrbbtt 99% scores in sum Top-Ranked Pages that contribute 90% scores in sum
0.8
that contribute 1% scores in sum
Sparsity
0.7
Ratio Bettom-Rarked that contribute 10% scores sum
0.4
0.3
6
9
10
15 Layer
16
17
18
19
20
24
25
26
27
28
29
ID
Figure 3: Token-level sparsity of KV cache. We organize the tokens in KV cache into pages (with page-size=32) and rank the pages of each layer based on the highest attention (softmax) scores of the tokens within each page.
4.2 Dynamism of Token Importance
Previous efforts leverage the sparsity of KV cache to control its size by retaining recent tokens while discarding older ones or selectively evicting less important tokens based on their historical attention scores, shown in Figure (b) (c). However, we find that the importance of tokens in the KV cache can dynamically change over time, as shown in Figure 44 For example, page 256 initially holds little importance but later becomes crucial, with its significant role (at position 12620) occurring nearly 4500 tokens after sequence position (at position 8192). Previous methods risk prematurely discarding such pages to save KV cache space. To address this, propose ARK VALE, shown

---

400
page 0-311)
Attention Score Ranking
page 2048-2079)
page 128 (taken 4096-4127)
page 256 (token 8192-8223)
260 (token 8320-8351)
200
300 (taken 9600-9631)
page 393 (token 12576-12607)
100
50
150
250
Decoding Step (Proptt-ength-12222
(a)
Number of attention
8
20.9
7.4
R
106.
040.7
10.2
3.4
2.2
that must participat
60.0
16.0
8.6
5.7
2.7
1.4
12
47.3
18.4
7.4
4.7
3.4
2.0
1.2
1.1
2.6
25.5
11.4
5.2
3.5
2.4
1.9
1.7
1.3
1.0
1.0
12
16
24
32
40
64
128
Cache capacity (number of pages)
(b)
Figure 4: (a) Dynamsim of token (page) importance (page-size=32). The sample is from GovRe-
port 28 (b) Number page-recalls (in average) needed during decoding step with page-size=32.
in Figure (d), method designed to recognize shifts in token importance and properly recall vital tokens as well as evict unimportant ones, therehy preventing substantial drops in accuracy.
Techniques of ARKVALL
5.1 System Design
Figure 5 showws the design of ARK VALE. Inspired by vLLM [36). ARKVALE arranges KV cache tokens into pages, enabling coarse- -ranneed management of tokens. As shown in Figure 5 (a), once page is filled, keys & values are asynchronously moved from GPU to external memory (CPU memory typically) for backup, with keys summarized into digest kept on the GPU (explained in 5.2.. Prior attention computation, ARKVALE gauges the importance of each page (whether cached or evicted), using the query and page digests (Figure[](b) detailed in $ $5.2). and subsequently ranks these pages (Figure (c) based on their importance scores. The top-k pages (governed by hyper-parameter k) must engage in attention computation (Figure 3 (e)). If any top-k pages were evicted before, they will be recalled from backup, and bottom-ranked pages in GPU will be evicted for exchange 5
Depending on the cache-size and the number of pages selected for attention, the overhead of page recall may be different. To validate the feasibility of our approach and ensure that recalls do not incur excessive overhead, we uniformly sample four instances from each dataset included in LongBench [9] and gather data from the inference process of LongChat-7b-v/ -aaa-atb-v..--322 1.55-2k [I to simulate eviction and recall scenarios. We configure the page-size p = 32 and vary both the cache capacity e (pages) and the attention size (the number of top-ranked pages selected for attention). The results, depicted Figure 4bb] reveal that as long as < min( 40, c/2), we can limit the number of recalls per decoding step under 10, amounting to a total of 5 MB of data transfer. This transfer takes merely hundreds of mieroseconds over contemporary CPU-GPU communication interfaces, which one two orders of magnitude faster than the end-to-end latency of each decoding step (usually few

---

Filled Page in GPU
Page Backup CPU
Async Copy
Keys Cache
Values
Keys Cache
Values Cache
(a) Backup and Summerize
Cache
Page Filled
Summarize
Keys Digest of the Page
PD
P2
P3
P4
P5
P6
P7
PB
P9
P10
P11
Query
(b) Estimating Page Importance Scores (Max Dot-product with Query)
Scores
80.5
74.5
(c) Ranking Pages based on Importance Scores
Ranks
To
1'1
12
Pages
PO
P11
P5
P3
P9
P7
P2
P4
P6
P10
P8
X
X
Participate
Recall
(d) Recall Evict Pages
Evict
PO
P11
P5
P3
P9
P7
P2
P4
P1
P6
P10
P8
Apply Paged-Attention
Page with both data in GPU & backup in CPU
Page with only backup CPU
Figure Design overview of ARK VALE
of milliseconds in long context scenarios NVIDIA A100 GPU). Thus, for page-size p and cache-capacity e (tokens), we set k = min(C, c/2)/p. where C' is a parameerssseterss (default C' 40 32 1280).
5.2 Page Summarization Importance Estimation
(1)
(2)
(9)
q
k (1)
(9)
(1)
(()
k
k
(4)
b(4)
k
b
Inge-Importance max q
k
q-- (2)
Page- Inppetaapreeceee max (
q k
2 (c 4) = q c
i=1
maxq q (
((2) 1 max + b (0)
i-1
(a) Bounding sounding-sphere need to record the center and the radius
(b) Bounding cuboid need to record the max-vector b(4) max (i) and the min-vector ( mine (t)
Figure 6: Summarize page keys {k()) into their bounding-volume (sphere/cuboid), We can estimate the max-dot-product between query q and keys (k(() Ji=1 using the bounding-volume.
For every filled page, maintain digest compression of it. The digest is much smaller than the page itself, and can be used to estimate the importance of each page regardless of whether the page has been evicted before attention computation. This estimation enables us rank pages to selectively recall or evict pages based on their importance.
[k(1] (k(1) E Rd), and query q E Rdd we measure its importance using the maximum dot product between the query and the (c..:/(q.2) K) maxke k q k. For two sets of keys, K, and K2, 7(q. Ki) > T(q. K2) implies that there's at least one token Ki with higher attention (softmax) scores compared to every token in K2.
Given a page with keys

---

It's evident that argmaxke K q must lie on a vertex of the convex hull of the point set K. Hence, we can upproximate [qq. K by constructing convex covering set of K. We leverage the concept of bounding-volume 3 34 to summarize the keys K of page. A bounding-volume for set of points closed region that completely contains all of them, which widely used in computer
graphics <4 29
12
Bounding-sphere. We can cover the keys K with sphere, needing to store only center с Rd and a radius r E IR as the digest. Given a query q E I2 we can estimate the importance [gq, K) leveraging с and r. Among the points k' on the surface of the sphere, those for which k' is parallel to yield the maximum dot product with q. Thus we have k' [ql leading to:
Iqq, K) maxq k = q. (c+
- q) c c q
(I)
kEK
Finding the minimal bounding sphere is complicated; hence, we employ an efficient approximation method: we take the center of the Axis-Aligned Bounding Box (AABB) 12 11 of K as our sphere center: 1/2 (minkex k + maxke k) (min and max are element-wise operations in this paper). For the radius r, three alternatives are considered:
An example is shown in Figure 6a
Tmax
max C k. KEK
Teenter
(min |c k + Tmax) 2 KE
Tmean
Σ KEK
|c
kl
(2)
K
where |..| means I.2-norm. Strictly speaking, only Tiax guarantees to enclose all points in K, but the latter two can avoid overestimating [(q, K) in practice, as shown in Figure 7 and discussed in $6.2
Bounding-cuboid. We can also cover the keys K directly using an Axis-Aligned Bounding Box (AABB) [12, [[]]. It needs store the max-vector b maXke k and min-vector b min milker k as the digest. Given a query vector q E IRd, we can estimate the importance / (qq K) of K with the boundaries of the box. This achieved by summing the maximum product by the boundary values and q across all dimensions:
d
[qq, K) = max q k ~ KEK
max q.k: = Σ max q.b. b.biiin) = max (q O max
min
KEK
Here, 1 E Rd denotes a vector of ones. and @ means wlement-wise multiplication. An example shown in Figure (b) Similar the bounding-sphers approach, we can employ different "radius vectors" to define cuboids with varying sizes:
max
max abs(c - k) penter keK
1 (min abs(c - k) + mmax)
mean
Σ keK
abs(c - k) (4)
2 kek
K
where abs(...) computes element-wise absolute values. For each r, we derive bmx and r, where с = 1 (minkek k + maxkex k) is the center of the AABB of K.
b min
Evaluation
6.1
Experimental Setup
and use datasets from LongBench 9 for We apply our method to LongChat-7b-v1.5-333 benchmarking: HotpotQA [59]. NarrativeQA (35.. Qasper [20]. GovReport (28). TriviaQA [30].
and Ressaaeeetrieval 19) along with the passkey-retrieval tasks. For comparison, we choose the state-of-the-art KV cache eviction methods including StreamingLLMM [58], H2O (64), and TOVA 40)
as baselines. As Figure 3 illustrates, the initial layers exhibit relatively low sparsity; hence, we do not apply ARK VALE and baselines the first two layers of model.
Our experiment platform comprises an Intel(R) Xeon(R) Gold 6348 CPU @ 2.60GHz and an NVIDIA A100 80GB PCle GPU. The software stack includes CUDA version 12.3, PyTorch [4] g version 2.3.0, and HuggingFace Transformers [57] version 4.40.0. We implement ARKVALE on top of
Huggingface Transformers, with CUTLASS (54), FlashInfer [60], and RAFT 44 for certain kemnlss.
7

---

1.0
Recall Accuracy
centroid
sphere-max
sphere-center
sphere-mean
cuboid-max
cuboid-center
cubold-mean
10
15
20
25
30
35
40
Top-k
Figure 7: Recall accuracy (the proportion of pages predicted to be among the top-k that indeed belong to the top-k) of different estimation methods. "Centroid" is the baseline which just uses the centroid of keys to estimate the max-dot-product with given query.
6.2 Estimation Accuracy
We begin by evaluating the accuracy of the page summarization & importance estimation methods discussed in $5.2 Using data from the LongBench [9] datasets employed in experiments, simulate each decoding step to collect both the actual page rankings and the estimated rankings derived using the digests. For varying values of k, we define recall accuracy as the proportion of overlap between the estimated top-k page set Eg and the true top-k page set Rs, that is: Ex n Rx R
Figure iillstrates the recall accuracy of different estimation techniques across various & values. The "centroid" method, which uses the centroid [4] (element-wise average of keys) of page keys as the digest and estimates page importance by directly taking the dot product of the query and the centroid, serves as a straightforward baseline. Other methods are the six introduced in $5. spheres with Tmux- Teenters and Tmean well cuboids with max center and mean As shown in Figure the centroid method cannot recall the top-4 pages with even 50% accuracy and achieves less than 5% accuracy in recalling the top-1 page, substantially undermining inference accuracy. Conversely, our six proposed methods guarantee at least 60% recall accuracy, with the standout cuboid-mean method ensuring 80% for other values. The cuboid-based
95% accuracy for top-1 recall and consistently methods generally outperform their sphere-basee counterparts due to more retained information (two vectors for cuboids versus one vector and scalar for spheres). Furthermore, the "mean" " variants tend to perform better than others, potentially because they provide a more balanced boundary estimation, avoiding overestimation of page importance.
6.3 LongBench Results
Next, evaluate the accuracy of ARK in general long-context tasks. We employ datasets from LongBench [9] as benchmarks, covering tasks such as multi-document QA with HotpotQA (59].
single-document QA with NarrativeQA (35), and Qasper [20), text summarization with GovRe- port (28). few-shot learning with TriviaQA [30], and synthetic tasks with PassageRetrieval [9]. The target model is LongChat-7b-v1.5-2 and the state-of-the-an KV cache eviction methods: StreamingLLM (58), H2O (64), and TOVA 40 We configure four cache budget settings: 4096, 2048, 1024, and 512. Notably, H2O and TOVA's original implementations require the full attention scores matrix to maintain states, preventing the use of optimizations like Atts-Ant [19 in prefill stage and causing Out-of-Memory (OOM) for many benchmark samples. To address this, we split each input into context and question/instruution sections and adopt two- sho-phase prefill: the first phase uses Flash-Attention [19] to handle the lengthy context without OOM (while also separately compute the last row of attention scores for H2O
M. Our comparison baselines include the original model

---

HotpatQA
NarrativeQA
Qasper
30-
Origin
18-
Origin
25-
Grigin
0
20
Arkoolo-32
ArkVale-16
0 16
ArkVale-16
AriVale-32
ArkVlle-16
ArkVale-32
StreamingLUM
14-
StreamingLLM
StreamingLUM
H20
TOVA
12-
H20
TOVA
15
H20
TOVA
512 1024
2048 Cache Budget
4096
512 1024
2040
4096
512 1024
2048
4096
Cache Budget
Cache Budget
GovReport
TrivagA
PassageRatrieval
30.0
30
Rougerl
25.0
27.5-
ArkVale-16 16
Drigin
70-
ArkVale-16
Origin
Accurscy
20
ArkVele-16
Crigin
AriVale-32
ArlVale-32
ArkVble-37
22.5
StreamingLUM
60-
StreamingLLM
StreamingLUM
H20
H2O
10-
H20
20.0
TOVA
50
TOVA
TOWA
512 1024
2048
4096
512 1024
2048
4096
512
1024
2048
4096
Cache Budget
Cache Budget
Cache Budget
Figure Evaluation on 6 long-context datasets in LongBench
9 with different cache budgets.
and TOVA's initial states update with little memory overhead), and the second phase uses brutal-force attention to process the shorter instruction, ensuring a complete score matrix for H2O and TOVA's states updates. This approach can also better demonstrate the long-range dependencies handling abilities of each method.
Figure 8 shows the results, where ARK VALE-16 and ARK represent ARK with page- sizes of 6 and 32, respectively. ARK VALE persistently surpasses baselines across datasets and cache budgets. It nearly equals Origin's 's performance with budgets over 2048, while other baselines show noticeable disparities when the budget dips below 2048 and even 4096. Specifically, ARK VALE achieves comparable results to Origin at budgets of 1024 for HotpotQA, 2048 for NarrativeQA and PassageRetrieval, 1024 for Qasper, and 512 for TriviaQA. Page-size differences have little impact in most test-cases: however, ARLVALE- 16 often outperforms ARK VALE-32 when budgets are tight, as it selects more pages under the same limited budget, enhancing the chances of hitting vital tokens.
6.4 Passkey Retrieval Results
Table I: Accuracy of passkey retrieval tasks
Context Length
10k
20k
30k
Cache Budget
512
1024
2048
4096
512
1024
2048
4096
512
1024
2048
4096
Streamingl LM (58
0%
5%
15%
40%
0%
0%
5%
20%
0%
0%
5%
10%
H2O [64]
5%
5%
5%
5%
20%
5%
5%
15%
TOVA H0
5%
10%
20%
40%
5%
5%
10%
20%
5%
5%
5%
15%
ARKVALE
100%
95 %
100% %
95%
95%
100%
100%
100%
100%
95%
95%
100 100%
We further examine the accuracy of ARKVALE under long-range dependency scenarios detail. We employ the passkey retrieval task (9) as our benchmark. We establish three context lengths for our tests: 10k, 20k, and 30k. For each context length, we generate 20 unique test cases, each with the passkey inserted at depths corresponding to 0%. 5%, .... up to 95% of the text's 's length. Following the setup in Section (6.3] we compare ARKVALI against StreamingLLM (58), H2O [64). and TOVA 40). Similarly, we adopt two-phase prefill for input texts to prevent OOM incidents of H2O and TOVA and more effectively evaluate each method's long-range dependencies handling.
The results are shown in Table Baselines, which permanently evict some tokens, risk discarding passkey-related information during inference, leading to accuracy falling short of 50% and declining further as the context length increases or the cache budget decreases. In contrast, VRLV examines the importance of evicted tokens (pages) and promptly recalls vital ones, thereby maintaining stable passkey retrieval accuracy above 95% across all tested context lengths and cache budgets.

---

6.5
Performance Results
Seq-len-100
Seq-len=200
Seq-len-30k
10k
5eg
30
40
Full
400
350
350
Alth
Relebive Throughout
300
300
25
Labency (mm))
20
40
Select Others
300
250
250
200
2:0
15
200
150
150
10-
20
100
100
100
50-
0.5k 14 2x 4x Full
0.5k 2x 4x Full
0.5k 14 2x Full Cache Budget
0.51kk 2x 4c Full Cache Budget
1.5 2x 4k Full Cache Budget
0.5 2k 4k Full Cache Budget
Cache Budget
Cache Budget
(a) Latency Breakdown (batch-size=4)
(b) Throughput Comparison
Figure 9: Decoding latency breakdown and achievable maximum throughput with page-size=32 and different seq-lens & cache budgets compared model with full KV cache.
We set up test-cases with lengths close to 10k, 20k, and 30k from GovReport 28 in LongBench and examined cache budgets of 512, 1024, 2048, and 4096. Figure TigurePajshows shows the results. Here, "Full" refers baseline without KV cache eviction, whereas "Estimate," "Select," and "Recall" denote the overhead for estimating page importance, choosing pages for computations and evictions, and recalling pages from CPU memory, respectively. ARK outperforms the baseline across all the tested text lengths, reaching up to 2.2x speedup (1.7x x in average). The main bottleneck of the baseline the full-attention, whose latency grows linearly with seq-len, whereas attention's 's latency is mainly governed by the fixed cache budget. Our extra latency overhead mostly arises from estimating importance, which grows linearly with the #pages seq-len page-size
inference latency with settings of a batch-size=4, page-size=32, and KV
Recalling, conversely, adds small overhead (especially when seq-len is large and cache-budget is small), consistent with the discussion in $5.1
We further compare the achievable maximum throughput in serving scenarios of ARK VALE versus the baseline under 40 GB memory limit for KV cache. Figure shows the results. Our throughput reaches up to 4.6x (3.5x in average) to that of baseline. This achievement not only due to the reduced inference latency but also to decreased per sample memory usage of the KV cache, enabling larger batch-size to enhance weight sharing to lessen the average latency of Linear computations per sample.
Limitation
The limitation of VRKV mainly lies on storing backup for each KV cache page in external memory (typically the CPU memory). Although the latency of data transfer for backup during decoding phase can be hided by asynchronous copy, the backup latency during prefilling phase is hard to completely overlapped. Also, the backups may occupy much CPU memory. When the CPU's memory capacity is insufficient, these backups may need to be offloaded to disk storage.
8 Conclusion
In this paper, we propose ARKVALE, a method designed for managing KV cache eviction and recall. It organizes KV cache tokens into pages, backs them up, and creates summaries, enabling the recognition of page importance to recall vital pages evicted before. Our method performs well on various long context tasks with few accuracy loss under cache budget of 2k-44 and speeds up decoding latency up to 2.2x and boosts decoding throughput up to 4.6x in long-contex, scenarios.
9 Acknowledgments
This work is supported part by the National Natural Science Foundation of China (No. T2325001) and Beijing Municipal Science and Technology Program (No.
10

---

References
[1] How Long Can Open-Source LLMs Truly Promise on Context Length? LMSYS Org.
[2] Introducing ChatGPT. https://openai.ccm//neee///ihhh
[3] Bounding volume. Wikipedia, April 2024.
[4] Centroid. Wikipedia, May 2024.
[5] SparQ Attention: Bandwidth-Effficiee LLM Inference. In ICLR Workshop ME-FoMo, April 2024.
[6] Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant J. Nair, llya Soloveychik, and Purushotham Kamath. Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference. In MLSys. arXiv, April 2024.
[7] Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints. In EMNLP, December 2023.
[8] Jason Ansel, Edward Yang. Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesen- sky, Bin Bao, Peter Bell, David Berard, Evgeni Burovski, Geeta Chauhan, Anjali Chourdia, Will Constable, Alban Desmaison, Zachary Vito,, Elias Ellison, Will Feng, Jiong Gong, Michael Gschwind, Brian Hirsh, Sherlock Huang, Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, C. K. Luk, Bert Maher, Yunjie Pan, Christian Puhrsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Shunting Zhang, Michael Suo, Phil Tillet, Xu Zhao, Eikan Wang, Keren Zhou, Richard Zou. Xiaodong Wang. Ajit Mathews, William Wen, Gregory Chanan, Peng Wu, and Soumith Chintala. PyTorch 2: Faster Machine Learning Through Dynamic Python Bytecode Transformation and Graph Compilation. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, volume 2 of ASPLOS '24, pages 929-947, New York, NY, USA, April 2024. Association for Computing Machinery.
[9] Yushi Bai, Xin Lv, Jiajie Zhang. Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding, August 2023.
[10] Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The Long- -occuentt Trans- former. 05510020000051500 December 2020.
[11] Gino Van Den Bergen. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools, 214):1-13, Jamuary 1997.
[12] panpan Cai, Chandrasekaran Indhumathi, Yiyu Cai, Jianmin Zheng, Yi Gong, Teng Sam Lim, and Peng Wong. Collision Detection Using Axis Aligned Bounding Boxes. In Yiyu Cai and Sui Lin Goei, editors, Simulations, Serious Games and Their Applications, pages 1-14. Springer Singapore. Singapore, 2014.
[13] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei. Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating Large Language Models Trained on Code, July 2021.
[14] Renze Chen, Zijian Ding, Size Zheng, Meng Li, and Yun Liang. MoteNN: Memory Optimization via Fine-grained Scheduling for Deep Neural Networks on Tiny Devices. In 2024 61 Design Automation Conference (DAC), 2024.
11

---

[15] Renze Chen, Zijian Ding, Size Zheng, Chengrui Zhang, Jingwen Leng, Xuanzhe Liu, and Yun Liang. Magis: Memory optimization via coordinated graph transformation and scheduling for dnn. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ASPLOS '24, page 607-621, New York, NY, USA, 2024. Association for Computing Machinery.
[16) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, and Joseph Gonzalez. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality. See htlps://vicuna. Imsys. org (accessed 14 April 2023), 2(3);6, 2023.
[17] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating Long Sequences with Sparse Transformers, April 2019.
[18] Tri Dao. FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning, July 2023.
[19] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré, FlashAttention: Fast and Memory-Efffcient Exact Attention with Iw-aweressss In NIPS. arXiv, June 2022.
[20] Pradeep Dasigi, Kyle Lo. Iz Beltagy, Arman Cohan, Noah A. Smith, and Matt Gardner. A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers, May 2021.
[21] Yiran Ding, Li Lyna Zhang, Chengruidong Zhang, Yuanyuan Xu, Ning Shang, Jiahang Xu, Fan Yang, and Mao Yang. LongRoPE: Extending LLM Context Window Beyond 2 Million Tokens, February 2024.
[22] Alexander R. Fabbri, Irene Li, Tianwei She, Suyi Li, and Dragomir R. Radev. Multi-News: A Large-Scale Multi-Docuumett Summarization Dataset and Abstractive Hierarchical Model, June 2019.
[23] Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs. In ICLR. arXiv, 2024.
[24] Tanya Goyal and Greg Durrett. Evaluating Factuality in Generation with Dependency-level Entailment, October 2020.
[25] Albert Gu and Tri Dao. Mamba: Linear-Time Sequence Modeling with Selective State Spaces, December 2023.
[26] Chi Han, Qifan Wang, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. LM-Infinite: Simple On-the-Fly Length Generalization for Large Language Models, November 2023.
[27] Ke Hong, Guohao Dai, Jiaming Xu, Qiuli Mao, Xiuhong Li, Jun Liu, Kangdi Chen, Hanyu Dong, and Yu Wang. FlashDecoding++: Faster Large Language Model Inference on GPÜs. arXiv preprint arXhv:2311.01282 2023.
[28] Luyang Huang, Shuyang Cao, Nikolaus Parulian, Heng Ji, and Lu Wang. Efficient Attentions for Long Document Summarization, April 2021.
[29] Pablo Jiménez, Federico Thomas, and Carme Torras. 3D collision detection: A survey, Comput- ers & Graphics, 25(2):269-285, 2001.
[30] Mandar Joshi, Funsol Choi, Daniel S. Weld, and Luke Zettlemoyer. TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprchension, May 2017.
[31] Ehsan Kamalloo, Nouha Dziri, Charles L. A. Clarke, and Davood Rafiei. Evaluating Open- Domain Question Answering in the Era of Large Language Models, July 2023.
[32] Marisa Kirisame, Steven Lyubomirsky, Altan Haan, Jennifer Brennan, Mike He, Jared Roesch, Tianqi Chen, and Zachary Tatlock. Dynamic Tensor Rematerialization. 2021.
[33] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The Efficient Transformer. In ICLR, September 2019.
12

---

[34] James T. Klosowski, Martin Held, Joseph SB Mitchell, Henry Sowizral, and Karel Zikan. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE transactions on Visualization and Computer Graphics, 4(1):21-36, 1998.
[35] Tomáš Kočiský, Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gá- bor Melis, and Edward Grefenstette. The NarrativeQA Reading Comprehension Challenge, December 2017.
[36] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient Memory Management for Large Language Model Serving with PagedAttention. In SOSP, SOSP '23, pages 611-626, New York, NY, USA, October 2023. Association for Computing Machinery.
[37] Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Seissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time. In NIPS, August 2023.
[38] Yuzhen Mao, Martin Ester, and Ke Li. IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs. In ICLR, October 2023.
[39] Amirkeivan Mohtashami and Martin Jaggi. Landmark Attention: Random-Access Infinite Context Length for Transformers. In Workshop on Efficient Systems for Foundation Models ICML2023, July 2023,
[40] Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers Multi-State RNNs, January 2024.
[41] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Veto,,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Pigh-Peeformance Deep Learning Library. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[42] Bo Peng. Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Krishna Sri Ipsit Mantri, Ferdinand Mom, Atsushi Saito, Xiangru Tang, Bolun Wang, Johan Wind, Stansilaw Wozniak, Ruichong Zhang, Zhenyuan Zhang, Qihang Zhao, Peng Zhou, Jian Zhu, and Rui-Jie Zhu. RWKV: Reinventing RNNs for the Transformer Era, May 2023.
[43] Bowen Peng, Jeffrey Quesnelle, Honglu Fan, and Enrico Shippole. YaRN: Efficient Context
Window Extension of Large Language Models. In ICLR, October 2023.
[44] Rapidsai. Rapidsai/raft: Raft contains fundamental widely-used algorithms and primitives for data science, graph and machine learning., 2022.
[45] Hongyu Ren, Hanjun Dai, Zihang Dai. Mengjiao Yang, Jure Leskovec, Dale Schuurmans, and Bo Dai. Combiner: Full Attention Transformer with Sparse Computation Cost. In NIPS, volume 34, pages 22470-22482. Curran Associates, Inc., 2021.
[46] Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi Jingyu Liu, Romain Sauvestre. Tal Remez, Jérémy Rapin, Artyom Kozhevmikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong. Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code Llama: Open Foundation Models for Code, January 2024.
[47] Noam Shazeer. Fast Transformer Decoding: One Write-Head is All You Need, November 2019.
[48] Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Re, lon Stoica, and Ce Zhang. FlexGen: High-TTrouuhhut Generative Inference of Large Language Models with Single GPU, ICML, 2023.
13

---

[49] Jianlin Su. Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. RoFormer: Enhanced Transformer with Rotary Position Embedding, November 2023.
[50] Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang. and Furu Wei. Retentive Network: A Successor to Transformer for Large Language Models, July 2023.
[51] Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference. In ICML, 2024-06-15.
[52] Rohan Taori, Ishaan Gulrajani. Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-folloving llama model, 2023.
[53] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da- Da-Cheng Juan. Sparse Sinkhorn Attention. In ICML, pages 0438-9447 PMLR, November 2020.
[54] Vijay Thakkar, Pradeep Ramani, Cris Cecka, Aniket Shivam, Honghao Lu, Ethan Yan, Jack Kosaian, Mark Hoemmen, Haicheng Wu, Andrew KeTr, Matt Nicely, Duane Merrill, Dustyn Blasig, Fengqi Qiao, Piotr Majcher, Paul Springer, Markus Hohnerbach, Jin Wang, and Manish Gupta. CUTLASS, January 2023.
[55] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajiwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini. Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiao- qing Ellen Tan, Binh Tang. Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open Foundation and Fine-Tuned Chat Models, July 2023.
[56] Hanrui Wang. Zhekai Zhang, and Song Han. SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning, In 2021 IEEE International Symposium High- Performance Computer Architecture (HPCA), pages 97-110, February 2021.
[57] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers:
oftte--f-theAAn
Natural Language Processing. In Qun Liu and David Schlangen, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38-45, Online, October 2020. Association for Computational Linguistics.
[58] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient Streaming Language Models with Attention Sinks. In ICLR. arXiv, September 2023.
[59] Zhilin Yang. Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdi- nov, and Christopher D. Manning. HotporQA: A Dataset for Diverse, Explainable Multi-hop Question Answering, September 2018
[60] Zihao Ye, Lequn Chen, Ruihang Lai, Yilong Zhao, Size Zheng, Junru Shao, Bohan Hou, Hongyi Jin, Yifei Zuo, Liangsheng Yin, Tianqi Chen, and Luis Ceze. Accelerating self-attentions for Ilm serving with flashinfer, February 2024.
[61] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big Bird:
Transformers for Longer Sequences. In NIPS, volume 33, pages 17283-17297. Curran Associates, Inc., 2020.
14

---

[62] Tianyi Zhang, Faisal Ladhak, Esin Durmus, Percy Liang, Kathleen McKeown, and Tatsunori B. Hashimoto. Benchmarking Large Language Models for News Summarization, January 2023.
[63] Zhenyu Zhang, Shiwei Liu, Runjin Chen, Bhavya Kailkhura, Beidi Chen, and Atlas Wang. Q-Hitter: A Better Token Oracle for Efficient LLM Inference via Saarse-Quantized KV Cache. 6:381-394, 2024-05-29.
[64] Zhenyu Zhang, Ying Sheng. Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song. Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen. H$ 2SO: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models. In NIPS, December 2023.
[65] Youpeng Zhao, Di Wu, and Jun Wang. ALISA: Accelerating Large Language Model Inference via Sparsity-Aware KV Caching. In ISCA. arXiv, 2024.
[66] Size Zheng, Renze Chen, Meng Li, Zihao Ye, Luis Ceze, and Yun Liang. vmeu: Coordinated memory management and kernel optimization for dnn inference on meus. In Gibbons, G. Pekhimenko, and C. De Sa, editors, Proceedings of Machine Learning and Systems, volume 6, pages 452-464, 2024.
[67] Size Zheng. Siyuan Chen, Peidi Song, Renze Chen, Xiuhong Li, Shengen Yan, Dahua Lin, Jingwen Leng, and Yun Liang. Chimera: An Analytical Optimizing Framework for Effective Compute-intensive Operators Fusion. In HPCA, pages 11 1113-112 1126, 2023.
[68] Ming Zhong, Da Yin, Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, and Dragomir Radev. QMSum: New Benchmark for Query-based Multi-domain Meeting Summarization, April 2021.
15

---

A Appendix supplemental material
Optionally include supplemental material (complete proofs, additional experiments and plots) in appendix. All such materials SHOULD be included in the main submission.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
17

---

Justification:
This paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The design of our method comprehensively discussed a5 the experi- ment setup is detailed in $6.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [No]
Justification: Due to some constraints, our code is currently not available for open access.
Nonetheless, design is thoroughly discussed in $5
Guidelines: For some reasons, we cannot open-source our code now.
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https /niiss.cc/pulli//guu guwdes/ddee/// Cot//ooodeeesiseeeeeeeeee wwwpobmmsssioooooooooooi for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experiment setup is outlined in $6.1 Additional details on specific settings are also provided for each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: In this paper's experiments, metrics for model performance (F1, Rouge-L, Accuracy) do not require error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
19

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiment environment is detailed in $6.1
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:pppr./.oooss.c.oo/o/////eea
Answer: [Yes]
Justification:
This paper does not entail ethical risks.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Due to space constraints, we don't delve into the broader impacts within the main text. In nutshell, our work positively contributes to the wider application of LLMs by reducing inference latency and memory usage while maintaining accuracy.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: In 6. we cite the methods we compare to and the datasets we use and specify versions of the software tools employed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt package should be provided. For popular datasets, paperswi thcode. cww/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "nueZnYPmp3", "reviewer": "Reviewer_PLAC", "summary": "The paper introduces ARKVALE, a novel page-based key-value (KV) cache management approach designed to optimize the performance of Large Language Models (LLMs) when dealing with long context lengths. As the demand for higher context lengths in tasks such as multi-turn chats and content generation increases, the management of extended key-value caches becomes crucial due to memory constraints and the impact on computation latency and throughput. ARKVALE addresses these challenges by dynamically managing the cache, selectively evicting less important tokens while recalling those that become relevant again at different decoding steps. This strategy leverages a mechanism that organizes tokens into pages and uses digests to estimate the importance of these pages. By summarizing pages into smaller, more manageable units, ARKVALE efficiently decides which pages to recall from external memory and which to evict, enabling focused attention computations on only the most relevant subsets of data.\n\nThe paper's experiments demonstrate that ARKVALE effectively handles various long-context tasks with minimal loss in accuracy, even under constrained cache sizes between 2K and 4K tokens. The results indicate significant improvements in model decoding latency and batching throughput, specifically up to 2.2x faster latency and 4.6x higher throughput. These enhancements are achieved by applying attention to a reduced subset of pages, thus decreasing the per-sample memory usage of the KV cache. This system not only improves the operational efficiency of LLMs but also maintains high accuracy levels, suggesting a scalable solution for managing extensive data in real-time language processing applications.", "questions": "Clarification on Model Choice: The paper primarily utilizes the LongChat-7b-v1.5-32k model for evaluating ARKVALE. Can the authors provide specific reasons for choosing this model over others? Additionally, how do the authors anticipate ARKVALE would perform with other, potentially larger or more recent LLM architectures?", "limitations": "The authors have not discussed the limitations of their work in the submission. It would be great to add sections discussing the limitations and societal impacts of ARKVALE.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: ARKVALE introduces a novel page-based system for KV cache management that dynamically adjusts which data is retained or discarded based on the evolving importance of tokens throughout the decoding process. This approach creatively combines ideas from memory management and attention mechanisms in LLMs, setting it apart from previous methods that often permanently discard tokens without the ability to recall them.\n\n**Quality**: The methods proposed are rigorously tested across various benchmarks and scenarios, demonstrating minimal loss in accuracy while substantially improving efficiency in terms of decoding latency and throughput. The experimental setup is thorough, using several datasets to ensure robustness and reproducibility of results.\n\n**Clarity**: The paper is well-organized, presenting complex ideas in a structured and understandable manner. The use of diagrams to illustrate the KV cache management process helps in demystifying the approach and makes the operational details of ARKVALE accessible to readers.\n\n**Significance**: ARKVALE's impact is multifaceted. For practical applications, it allows for the deployment of LLMs in environments where memory and latency are constraints, thus broadening their usability in real-world applications. Theoretically, it advances our understanding of efficient memory management in models requiring extensive context, potentially influencing future developments in LLM architectures and optimization techniques.", "weaknesses": "- Insufficient Model Evaluation:\nThe paper evaluates the proposed method using only the LongChat-7b-v1.5-32k model, which is relatively outdated in the current landscape. It does not demonstrate the method's generality and robustness across different model architectures (e.g., MoE, GQA) and scales (70B models).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Clarification on Model Choice: The paper primarily utilizes the LongChat-7b-v1.5-32k model for evaluating ARKVALE. Can the authors provide specific reasons for choosing this model over others? Additionally, how do the authors anticipate ARKVALE would perform with other, potentially larger or more recent LLM architectures?\n\nWe primarily choose the LongChat-7b-v1.5-32k model because it is a relatively state-of-the-art long-text extension of Llama2 at the time.\n\nWe conduct experiments on our method adapted to the relatively newer models\nMistral-7B and Llama-3-8B that utilize GQA. The results are shown in Global Response.\n\n---\n\n>The authors have not discussed the limitations of their work in the submission. It would be great to add sections discussing the limitations and societal impacts of ARKVALE.\n\nChiefly, the limitation of our method lies on storing a backup for each KV cache page in external memory (typically the CPU memory). On the one hand, although the latency of data transfer for backup can be hided by asynchronous copy, the energy consumption cannot be eliminated. On the other hand, it may occupy much CPU memory, potentially impacting the performance of other applications under some extreme conditions. Furthermore, when the CPU's memory capacity is insufficient, these backups may need to be offloaded to disk storage.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ggq2UPwcXq", "reviewer": "Reviewer_ntoN", "summary": "The paper proposed a method to minimize the risk of KV cache eviction by efficiently and soundly offloading some of them into external memory, which is realized by page organization, page digest, and digest ranking/scoring. The method gets much better performance in context retrieval tasks compared to other KV eviction methods.", "questions": "I'm wondering if there will be an open-sourced implementation/PR to vLLM?", "limitations": "It's desirable to see normal length tasks, e.g., GSM8K.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a reliable way to do KV cache eviction with minimal risk.\nThe system is sound and intuitive. It seems compatible with real world frameworks like vLLM.\nExperiments show good results.", "weaknesses": "It's not very clear if the dynamics of importance will change along the decoding in other tasks, so the observations may be limited.\nIt would be interesting to see how the page size affect the methods, as vLLM's default page size is 16. Is there any reason to scale to 32?\nWould the method still work when TP>1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It would be interesting to see how the page size affect the methods, as vLLM's default page size is 16. Is there any reason to scale to 32?\n\nWe briefly discuss the impact of different page-sizes on accuracy and latency in Global Response. A page-size of 32 is a compromise between these two aspects (though in fact, a page-size of 16 would also be perfectly acceptable).\n\n---\n\n>Would the method still work when TP>1?\n\nYes, ArkVale can be applied to distributed scenarios. But in the context of distributed inference for LLMs, it is common for different heads of a KV-cache to be distributed across various GPUs. Thus, head-wise page eviction and recall may be necessary.\n\n---\n\n>I'm wondering if there will be an open-sourced implementation/PR to vLLM?\n\nYes, we plan to introduce serving technologies such as continuous batching into ArkVale and adapt it to serving frameworks like vLLM and SGLang.\n\n---\n\n>It's desirable to see normal length tasks, e.g., GSM8K.\n\n\nWe evaluate our method on six normal length benchmarks using `lm-eval-harness`. The results are presented in the table below (with page-size=32):\n\n| Cache Budget        | \\|  | Full  | 4096  | 2048  | 1024  | 512   |\n| ------------------- | --- | ----- | ----- | ----- | ----- | ----- |\n| GSM8K (5-shot)      | \\|  | 0.092 | 0.092 | 0.092 | 0.086 | 0.078 |\n| HellaSwag (0-shot)  | \\|  | 0.544 | 0.544 | 0.544 | 0.544 | 0.544 |\n| WinoGrande (0-shot) | \\|  | 0.684 | 0.683 | 0.683 | 0.683 | 0.683 |\n| PIQA (0-shot)       | \\|  | 0.760 | 0.761 | 0.761 | 0.761 | 0.761 |\n| OpenBookQA (0-shot) | \\|  | 0.306 | 0.306 | 0.306 | 0.306 | 0.306 |\n| MathQA (0-shot)     | \\|  | 0.253 | 0.253 | 0.253 | 0.253 | 0.253 |\n\nThe data from the table indicates that, in most cases, ArkVale maintains comparable accuracy to the original model when the cache budget does not exceed 4096. This is likely because the context lengths for these tasks are not long enough, and they primarily test the model's fundamental capabilities rather than its contextual memory. However, in tasks like GSM8K, a notably small cache budget can lead to an obvious drop in accuracy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "prsow8QVvP", "reviewer": "Reviewer_8mmm", "summary": "ARKVALE presents a page-based key-value (KV) cache manager designed to address the challenges associated with long-context processing in large language models. The main contribution is its ability to recognize and recall important tokens that were previously evicted, thereby optimizing memory usage and improving throughput and latency without significant accuracy loss. The method involves asynchronously backing up filled pages in external memory and using bounding-volume techniques to summarize and estimate the importance of these pages for efficient recall and eviction. Experiments show strong performance in terms of both accuracy and efficiency.", "questions": "- What is the performance of ARKVALE on Mistral-7B-Instruct-v0.2 and LLaMA-3-8B-Instruct?\n- How does the performance (accuracy, latency/throughput) of ARKVALE compare to other methods [1, 2]?\n- What is the process for selecting the hyperparameters, and what their influence on performance?\n- Does the prefill phase use all tokens? For example, for the first token generated, is full attention used? Additionally, is this method compatible with FlashAttention/FlashDecoding?\n\n[1]  Infllm: Unveiling the intrinsic capacity of llms for understanding extremely long sequences with training-free memory\n\n[2] Snapkv: Llm knows what you are looking for before generation", "limitations": "See weaknesses and questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- ARKVALE empirically identifies the dynamism of token importance and proposes efficient token eviction and recall methods. This approach ensures good memory efficiency while maintaining accuracy.\n- The efficient system design and implementation improve decoding latency by up to 2.2x and batching throughput by up to 4.6x.\n- ARKVALE performs well across different tasks by comprehensive benchmarking, shows its ability in various long-context scenarios.", "weaknesses": "- The benchmark is only conducted on LongChat, lacking evaluations on different models such as Mistral and LLaMA-3.\n- There is a lack of comparison with other methods focusing on efficiency, and some other baselines like [1,2].\n- The paper lacks discussion and ablation studies on some hyper-parameters, such as top-k, page-size and the relationship between top-k, page-size and the cache budget.\n\n[1]  Infllm: Unveiling the intrinsic capacity of llms for understanding extremely long sequences with training-free memory\n\n[2] Snapkv: Llm knows what you are looking for before generation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">What is the performance of ARKVALE on Mistral-7B-Instruct-v0.2 and LLaMA-3-8B-Instruct?\n\nWe conduct experiments on our method adapted to Mistral-7B and Llama-3-8B, as detailed in Global Response.\n\n---\n\n>How does the performance (accuracy, latency/throughput) of ARKVALE compare to other methods\n\nIn the Global Response, we compare the accuracy and latency of ArkVale with other baselines.\n\n---\n\n>The paper lacks discussion and ablation studies on some hyper-parameters, such as top-k, page-size and the relationship between top-k, page-size and the cache budget.\n>What is the process for selecting the hyperparameters, and what their influence on performance?\n\nFor the cache-budget $c$ and page-size $p$, we empirically set the top-k to $\\min(40*32, c/2) / p$. In the Global Response, we discuss the impact of different cache-budgets and page-sizes on accuracy and latency.\n\n---\n\n>Does the prefill phase use all tokens? For example, for the first token generated, is full attention used? \n\nYes, currently we use the full kv-cache during the prefill phase. However, it is also feasible to perform eviction early in the prefill phase, although the impact on accuracy needs to be determined through experiments. We plan to explore this in future work.\n\n---\n\n>Additionally, is this method compatible with FlashAttention/FlashDecoding?\n\nYes, but it requires using the Paged version of FlashAttention/FlashDecoding, such as the kernels implemented in FlashInfer.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r2jTS79ffZ", "reviewer": "Reviewer_YdSG", "summary": "This paper proposes a paged-based KV cache manager that identifies and recalls important tokens for LLM inference, termed ArkVale. Results show that ArkVale achieves 2.2x latency and 4.6x throughput improvement on various long context tasks.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is easy to follow, with clear writing and presentation.\n2. Evaluation results are comprehensive.", "weaknesses": "1. How does the page size affect the memory consumption for the KV cache? Would smaller page size lead to potential fragmentation issues?\n2. In the related work section, it would be nice if the authors could the relationship between ArkVale and some concurrent works [1,2,3].\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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">How does the page size affect the memory consumption for the KV cache? Would smaller page size lead to potential fragmentation issues?\n\nWe allocate pages from a pre-allocated memory pool, and all pages have the same page-size, thus avoiding the issue of memory fragmentation. However, a smaller page-size results in an increased number of pages, leading to a greater number of page digests and consequently increased memory usage.\n\n---\n\n>In the related work section, it would be nice if the authors could the relationship between ArkVale and some concurrent works [1,2,3].\n\nKeyformer [1] are similar to works like H2O in that they use historical information to perform eviction on the KV-Cache, and they have improved the eviction score function by leveraging the Gumbel distribution. Q-Hitter [2] combines KV-cache quantization with KV-cache eviction. But neither of these works can dynamically assesses the importance of tokens. \n\nALISA [3] uses a post-training dynamic sparse attention approach, similar to SparQ, which dynamically evaluates the importance of each token in the KV-cache and selects a subset of tokens for attention calculation. However, this token-level approach is too granular and incurs significant additional overhead (requiring all KV-cache tokens to be involved in assessing importance), and it also poses challenges for memory management if it requires token-level eviction & recall. In contrast, our approach operates at the page-level for importance estimation, eviction, and recall, achieving a good balance between accuracy and performance overhead.\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": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## Adaption to other models 

We adapt ArkVale to both `MaziyarPanahi/Llama-3-8B-Instruct-64k` (with 64k context-length extended from Meta Llama-3-8B) and `mistralai/Mistral-7B-Instruct-v0.3` (with a 32k context-length) in hugginggface, and test them on the datasets used in our paper, with the results shown in the table below (with page-size=32): 

| Model            | \|  | Llama3     |           |        |           |           | \|  | Mistral    |           |           |        |       |
| ---------------- | --- | ---------- | --------- | ------ | --------- | --------- | --- | ---------- | --------- | --------- | ------ | ----- |
| *Cache Budget*   | \|  | ***Full*** | *4096*    | *2048* | *1024*    | *512*     | \|  | ***Full*** | *4096*    | *2048*    | *1024* | *512* |
| HotpotQA         | \|  | **42.94**  | **40.9**  | 38.01  | 37.39     | 32.54     | \|  | **49.37**  | 48.72     | **49.92** | 49.14  | 48.91 |
| NarrativeQA      | \|  | **16.77**  | 17.2      | 18.03  | 17.8      | **18.14** | \|  | **28.74**  | **28.61** | 25.87     | 25.34  | 23.59 |
| Qasper           | \|  | **11.0**   | **10.6**  | 10.03  | 9.5       | 8.71      | \|  | **41.58**  | **42.2**  | 41.44     | 39.24  | 36.9  |
| GovReport        | \|  | **28.91**  | **27.34** | 25.62  | 24.38     | 21.96     | \|  | **34.91**  | **32.84** | 31.59     | 29.69  | 25.85 |
| TriviaQA         | \|  | **89.91**  | 89.91     | 89.91  | **90.12** | 89.35     | \|  | **88.59**  | **88.94** | 88.94     | 89.38  | 88.7  |
| PassageRetrieval | \|  | **52.75**  | 59.75     | 61.25  | 62.0      | **64.91** | \|  | **98.0**   | **95.0**  | 94.5      | 90.5   | 82.0  |

From the data in the table, we can observe that in most cases, ArkVale can approach or even surpass the accuracy of the original model when the cache budget does not exceed 4096.

---
## Additional Baselines 

We add comparisons with two open-sourced concurrent works, SnapKV [1] and InfLLM [2]. SnapKV, similar to works like H2O and TOVA, evicts KV-cache based on historical token information, but it only performs eviction during the prefill phase, thereby reducing overhead in the decode phase. InfLLM is a context expansion work that employs block-level memory units, which share similarities with ArkVale's page-level eviction/recall method. However, it generalizes memory units using several representative tokens (defaulting to 4) and, like streaming-llm, it retains a fixed number of initial-tokens and recent-tokens, employing the same positional encoding for tokens outside the recent-tokens.

We test these two baselines on LongBench based on the experimental setup and evaluation method detailed in Section 6.3 of our paper. The experimental results are presented in *Figure 1 of the attached PDF*. SnapKV nearly outperforms all other baselines, yet it is still not better than ArkVale overall. We attribute this anomaly to our dynamic selection of important tokens. InfLLM, similar to ArkVale, inspects and recalls some important tokens, and additionally preserves initial-tokens and recent-tokens, thus performing comparably or even better than ArkVale on datasets such as Qasper, GovReport, and TriviaQA. However, since it apply the same positional encoding to all the tokens other than recent-tokens, its performance is unstable, as evidenced by its poor performance on NarrativeQA and PassageRetrieval. Furthermore, using representative tokens as page digest may not be good enough for page importance estimation.

*Figure 2 of the attached PDF* shows the average latency per decode step for ArkVale (page-size=32) and baselines under different sequence lengths in the passkey retrieval task. Due to the inconvenience of setting batch-size greater than 1 for some baselines, experiments were conducted with batch-size=1. In all cases, ArkVale achieves the shortest latency, which gradually increases with the increasing cache budget. H2O, TOVA, and StreamingLLM incur token eviction during every decode step, introducing additional overhead, whereas SnapKV only performs eviction during the prefill phase, resulting in better performance than the others. Although importance estimation and page recall may introduce some additional overhead to ArkVale, ArkVale is slightly faster than SnapKV, mainly due to its efficient paged memory management with page-attention. The poor performance of InfLLM is likely due to its suboptimal implementation of memory management and hand-crafted attention kernel.

[1] Infllm: Unveiling the intrinsic capacity of llms for understanding extremely long sequences with training-free memory

[2] Snapkv: Llm knows what you are looking for before generation

---
## Impact of Different Page-sizes

Generally speaking, the smaller the page-size, the more accurate the estimation of page importance, the higher the model's accuracy. However, a smaller page-size will also increase the number of pages for the same number of tokens, thereby increasing the space occupied by the page digest (1~2 token per page), and simultaneously increasing the latency overhead for page importance estimation. 

We test the impact of different cache-budgets and page-sizes on model accuracy and decode latency on LongChat-7b-v1.5-32k. We select PassageRetrieval as the benchmark. The results are presented in *Figure 3 of the attached PDF*. It can be observed that as the page-size decreases/cache-budget increases, both accuracy and latency gradually increase. Notably, the accuracy for page-size=8 is slightly worse than that for page-size=16, possibly due to the smaller page-size causing fewer adjacent tokens to be selected simultaneously, which impacts attention locality. Considering accuracy and latency & memory overhead, we typically set the page-size to 16 or 32.

Meta-review: This paper looks into the problem of KV cache compression for more memory-efficient LLM inference. Existing eviction-based KV cache compression methods permanently evict tokens which may later turn out to be important as generation moves forward. The paper introduces a method to offload a subset of tokens that are not important for the time being but can recall those tokens when needed if token importance changes dynamically. The paper also takes into account of page attention, which supports easy swap-in and swap-out of tokens to second memory during inference. Overall, the reviewers are positive to the paper. The main reasons for accepting the paper are: 
1) It seems to be novel to add the mechanism of dynamically retrieving tokens back from secondary memory based on the change of token importance. 
2) Promising empirical speedups.
3) Relatively comprehensive evaluation. 

There were some concerns from reviewers about the generalizability of the approach to other models and comparison with additional baselines. However, those were addressed via the rebuttal. The paper can be improved if it can incorporate the discussion of concurrent work, as suggested by reviewer YdSG.
Decision: Accept (poster)