KVLink: Accelerating Large Language Models via Efficient KV Cache Reuse
Authors: Jingbo Yang
Bairu Hou
Wei Wei
Yujia Bao
Shiyu Chang
Venue: NeurIPS 2025 poster ()
Keywords: LLM
Retrieval-Augmented Generation
Efficiency
Primary area: deep_learning

Abstract: We describe KVLink, an approach for efficient key-value (KV) cache reuse in large language models (LLMs). In many LLM applications, different inputs can share overlapping context, such as the same retrieved document appearing in multiple queries. However, the LLMs still need to encode the entire context for each query, leading to redundant computation. In this paper, we investigate a new strategy to eliminate such inefficiency, where the KV cache of each document is precomputed independently. During inference, the KV caches of retrieved documents are concatenated, allowing the model to reuse cached representations instead of recomputing them. To mitigate the performance degradation when using KV caches computed independently for each document, KVLink introduces two key techniques: adjusting positional embeddings of the KV cache at inference to match the global position after concatenation, and using trainable special tokens to restore self-attention across independently encoded documents. Experiments across 7 datasets demonstrate that KVLink improves question answering accuracy by an average of 4% over state-of-the-art methods. Furthermore, by leveraging precomputed KV caches, our approach reduces time-to-first-token by up to 96% compared to standard LLM inference, making it a scalable and efficient solution for context reuse. Additionally, KVLink can be combined with KV cache compression to further save cache loading and storage overhead while outperforming the baselines.

KVLINK: Accelerating Large Language Models via Efficient KV Cache Reuse
Jingbo Yang" Department of Computer Science
Bairu Hou"
Department of Computer Science
UC Santa Barbara jigbbouusb..o edu
UC Santa Barbara bairu@ucsb.. edu
Wei Wei Center for Advanced Al Accenture
Yujia Bao Center for Advanced AI Accenture
wei. wei Caccenture.....oooo com
yujia. wujiaabao@@ccenturre.cc com
Shiyu Chang
Department of Computer Science
UC Santa Barbara chang878ucab.
Abstract
We describe KVLINK, an approach for efficient key-value (KV) cache reuse in large language models (LLMs). In many LLM applications, different inputs can share overlapping context, such as the same retrieved document appearing multiple queries. However, the LLMs still need to encode the entire context for each query, leading to redundant computation. In this paper, we investigate a new strategy to eliminate such inefficiency, where the KV cache of each document is precomputed independently. During inference, the KV caches retrieved docu- ments are concatenated, allowing the model to reuse cached representations instead of recomputing them. To mitigate the performance degradation when using KV caches computed independently for each document, KVLINK introduces two key techniques: adjusting positional embeddings of the KV cache at inference to match the global position after concatenation, and using trainable special tokens to restore self-attention across independently encoded documents. Experiments across 7 datasets demonstrate that K VVLINK improves question answering accuracy by average of 4% over state-of-the art methods. Furthermore, by leveraging precom- puted KV caches, approach reduces tonetto-fist--e toksn by up to 96% compared to standard L.LM inference, making a scalable and efficient solution for context reuse. Additionally, K KVLINK can be combined with KV cache compression further save cache loading and storage overhead while outperforming the baselines. Code is available at //tts/ub//tut....t// www/UCSB- CAA-GB---P--hhaaee NWW-NLLL--ChaKK-K- BhanngKVVLikk
Introduction
Large language models have demonstrated impressive capabilities across broad array of applica- tions many of which involve processing contexts naturally divided into multiple segments. For example, in retrieval- -augenel- generation (RAG) [13], each retrieved document forms a distinct
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

context chunk, while in multi-agen conversation scenarios 51, outputs from different agents serve as separate segments. However, conventional architectures require LLMs to encode the entire con- catenated context as single unit before generating a response. This approach incurs high prefilling costs for long contexts and prevents the model from separately encoding and reusing precomputed representations (i.e., key-value states) for each segment. Consider RAG: for every query, the LLM encodes a large collection of retrieved documents. When different queries share common documents, the model redundantly re-encodes these identical texts, even though their content remains unchanged.
This inefficiency motivates us to explore an alternative strategy. Instead of re-encoding the entire concatenated context for every query, we propose precomputing the key-value (KV) states for each document or text segment independently. then reusing these precomputed states during inference. By encoding each segment (e.g., each retrieved document) separately and concatenating their KV states as needed, we can eliminate redundant computations and significantly improve efficiency. However, naively encoding each document independently and concatenating their KV caches during inference can lead to performance degradation due to train-test discrepancies. Prior work 6 has reported up to 35% relative decrease in accuracy QA tasks, which results from the discrepancy of position embeddings and missing cross attention between retrieved documents. To overcome this challenge, we introduce KVLINK, an approach designed to bridge the gap between separately encoded segments and restore self-attention across documents. K KVLINK introduces two key enhancements: KV cache positional re-encoding. We adjust positional embeddings during inference to ensure that the stored KV caches align correctly with the positions required for a given query. @ Trainable cross- segment special tokens. To effectively "link" independently encoded segments, KVLINK appends small set of trainable tokens between each segment's precomputed KV states before concatenation. The KV representations for these tokens are computed during inference. While the documents independently encoded into KV cache, the link tokens can attend to all the preceding tokens, which helps restore self-altention across segments while introducing only minimal computational overhead.
We validate the effectiveness and efficiency of our method through comprehensive experiments across diverse question-anse answering and text sum- marization datasets. We evaluate three back- bone LLMs with different model scales, in- cluding Llama-3. 2-1B, Llama-3.. 2-3BB, and L1ama-3. 1-BB, showing that our approach consistently outperforms state-of-the-art base- lines 6 99. For example, KVLINK surpasses the best baseline by 6.6% Natural Ques- tion 100 and 7.3% on HotporQA [II] Even compared to the upper-bound model (i.e., LLM using conventional full encoding for inference), our method sacrifices only minimal performance while reducing the tine-to-first-ooee latency by up to 96% by efficiently reusing precomputed KV caches.
Standard RV Cache Encodiing
borb
KV cache
Doca
Doog
LEA
Doc.
Docg
Retrieked docusents
Dec,
Our Setting
Doca
Docp
Docg
Doce
Reuse
Doce
Doog
Doch
Separately encoded KV cache
Standard approach (top) encodes the KV cache of each document conditioned on preced- ing tokens, resulting in redundant and nonreusable KV cache encoding for shared documents (e.g.. Doc,). In contrast, our setting (bottom) encodes documents separately, allowing KV cache reuse across queries.
Figure I:
Additionally, we investigate the integration of KVLINK with KV cache compression tech- niques, as storing precomputed KV caches can incur substantial storage overhead. By incorpo- rating methods such as LLMLINGUA [12] and ANLLMS [3), KVLINK consistently outperforms
baseline approaches. These results demonstrate its strong potential for practical, large-scale deploy- ment.
2 Methodology
2.1 Problem Formulation
We aim to address the problem of reusing the key-value (KV) cache LLMS without having to repeatedly encode the same context segments. In many applications, the same documents or context

---

segments appear across different inference queries, yet current LLM pipelines redundantly re-encode these segments every time.
Consider the problem of retrieval augmented generation as an example, where the input question is denoted as q and we retrieve N documents for each question. These documents concatenated with the query, forming the complete LLM input.
In the standard LLM inference pipeline, the entire input is passed into the LLM as a single contiguous sequence, As shown in the top portion of Figure [ the resulting KV cache for each document is entangled with its preceding documents. Consequently, even if Doc, has already been encoded into KV cache when processing qı, the resulting KV cache cannot be directly reused when processing q2 because it was conditioned the preceding documents in 91-
To address this, we consider a scenario where the KV cache for every document in the knowledge base is pre-computed in a context-free manner, as illustrated in the bottom of Figure [ Specifically, for each document in the knowledge base, we feed only that document's 's tokens into the L.LM and record the resulting KV cache. At inference time, after we retrieve set of documents for given query, we concatenate their pre-computed KV caches. This design allows us to reuse the same cache for overlapping documents across different queries, thereby eliminating redundant computations.
However, the above approach often yields noticeable performance degradation. as LLMs are typically trained on fully concatenated sequences and each token attends to the preceding context. When we instead encode each document in a context-free manner, the model loses cross-document dependencies. Previous work also empirically demonstrates up to 35% relative decrease in accuracy in question- answering tasks when each retrieved document is encoded into KV cache separately 77. Our method aims to enable the LLM to produce high-quality outputs when the KV cache of each document is pre-computed independently by introducing two key components, 1 KV cache positional re-encoding and @ cross-document reconnection with link tokens.
2.2 KV Cache Positional Re-encoding
The first issue with separately encoding documents is the position mismatch during inference. Modern LLMs typically use Rotary Positional Encoding (RoPE) [14), where each token is assigned distinct positional embedding based on its position in the full sequence. However, when documents are encoded independently, tokens are indexed within their own document, ignoring their actual position in the full concatenated input. Take Figure ass an example. Since we pre-compute the KV cache for each document separately, the second token in Doc, is assigned position index 2 when computing its KV cache. However, when we concatenate Doc; with Doc, during inference (e.g., when processing query qı), the actual position of that token should be [Doc,] + where |occa| is the length of the first document. Since the KV cache of Doc, was precomputed without awareness of this global position shift, the LLM applies incorrect positional embeddings, leading to erroncous attention computations.
To address this, we decouple the key-value states from the positional embeddings when storing them. We still apply rotary position encoding tokens when encoding each segment for local self- att--tttennin. However, we exclude those positional transformations before saving the segment KV caches.
More specifically, we denote the hidden state of a token at position i at a particular transformer layer as a; E I.d where d the hidden dimension. The key vector is computed as R2 Wrar; and the value vector is computed as W..., Here W W(K..) E Ied represents the weight matrices that project the hidden states into the key and value spaces, and R; [-1, 1] is the position-dependent rotation matrix used in RoPE. Because RoPE directly encodes positional information via these rotations, the KV cache can be stored without positional embeddings, i.e., W W(k,e) At inference time, the kay-value states of all documents are concatenated, and we apply the global rotary embedding for the KV states of each token appropriate to its location in the full sequence. This operation only introduces negligible time, ensuring the efficiency of our method. This is also consistent with previous methods 6 R) which adjust the position encoding of separately encoded KV cache during inference.
2.3 Cross-Document Reconnection with Link Tokens
When documents are encoded and cached independently, tokens in later documents can no longer attend to those in earlier ones. This creates gap between our inference scheme and standard LLM training and can potentially limit the model performance. To mitigate this issue, we design
3

---

Position 1
2
3
Inference attention map
Doc,
teneeded
mas ked
linkl
link2
D0C
link3
1ink2
Doc.
User
1ikk3
DoCa
DoCb
Doc:
1ink1 link2 1ink3 User
attended
masked
Figure 2: Left: the attention map for all tokens. The link1 token attends only to the tokens in Doca; link2 attends to the tokens in Doc, and Doc, and link2; and link3 attends to the tokens in all reused contexts and other link tokens. Right: the attention map for three link tokens and the first user input token during inference. These two attention maps are identical.
novel mechanism restore the self-attention connection across segments while preserving the computational efficiency of KV cache reuse. Specifically, KVLINK introduces a set of trainable "link tokens". For every document with length L, we append K (e.g., K 5) link tokens:
c= (C1 .........0... CL, Clinkl Clinks)
where CI....,Cp Cr are the tokens within the original document. customized attention map ensures that the link tokens of each document can attend to (i) all tokens (including the link tokens) in the preceding documents and (ii) tokens within the current document. These tokens serve as an interface between segments, allowing the model to reconstruct dependencies that would otherwise be lost due to independent encoding.
Figure 2 iillustrates this mechanism, where one link token document (K = 1) is append (token 3, 6, and 8). The tokens within document can only maintain local causal attention, meaning they can only attend to earlier tokens within the same document. Each link token can attend to all preceding tokens. Therefore, different documents are implicitly connected through these link tokens during inference. For example, token 6 (the link token of document 2) attends to the first two documents and token (the link token of document 3) attends to token 6, thus mixing the information across all retrieved documents. After the retrieved documents, the question and user tokens follow standard causal self-attention. During training, we fine-tune the LLM with this attention mechanism, jointly optimizing both the model and the newly introduced link tokens.
Figure 2 illustrates our inference strategy, which avoids recomputing KV caches for retrieved documents. In practice, we first load and concatenate the precomputed KV caches for all retrieved documents. Since these caches were precomputed, they do need to re-encoded. We then append only the newly introduced link tokens (tokens 3, 6, and 8, corresponding to the three documents) to the end of the reordered sequence. A forward pass is performed on these tokens using the customized attention map, ensuring that their attention behavior matches the training phase.
2.4 Compressed KV Cache Linking
Although reusing pre-computed KV caches can greatly accelerate inference, it may introduce con- siderable overhead in storing these caches a database and loading them onto the GPU. This overhead presents major challenge for integrating cache reuse into real-world RAG deployments. For example, a 1.000-token document stored as UTF-8 text occupies only about 5KB, whereas the corresponding Llama3-8B KV cache requires roughly 131 To address this issue, we further explore combining our method with KV cache compression techniques. Specifically, we consider following choices: 1 L.L.LINGUA 12] which compresses documents by token dropping: and e ANILMMS [33, which fine-tunes the L.M to compress each sentence the document into anchor token with special attention masks.

---

When using ANLLMS, we empirically observe a significant drop in LLM performance on question- answering benchmarks. To address this, we introduce the following modifications aimed improving effectiveness. First, instead of compressing each sentence into single anchor token and storing its KV cache, we divide each document into multiple consecutive chunks of fixed length and compress each chunk into multiple anchor tokens. Second, we modify the attention masks so that each anchor token attends only to tokens within its own chunk and to preceding anchor tokens. More specifically, let represent a training example from the pretraining dataset, consisting of sequence of tokens. We split the first N tokens into N/s chunks of fixed size s:
x (m) = 1((=1))+t+..... Enst n2 = I,.,,,, N,
where s denotes the chunk size. In our experiments, we set 100 by default. We then append several anchor tokens to each chunk. The LLM is trained to perform next-token prediction on the remaining tokens beyond position N,, which are restricted to attend only to the anchor tokens. This setup encourages the model to compress the input into a small number of anchor tokens, allowing us to store only the KV cache of those tokens and thereby significantly reduce storage overhead. Also, by increasing the number of anchor tokens, we can better maintain the model performance given compressed KV cache. To apply this method, we first pretrain the LLM using this objective on pretraining data. We then fine-tune the model on QA datasets using KVLINK. Additional implementation details are provided in Appendix AA6
3 Experiments
3.1 Experiment Setup
Comparison baselines. We evaluate our method against three existing approaches: 1 PROMPT- CACHE (9) which directly reuses the precomputed KV cache of each retrieved document or context segment for model inference. Since the original PROMPTCACHE does not handle positional encoding mismatches, we enhance it by applying our positional re-encoding method (Section 2.2p to ensure the stored KV cache aligns correctly with the concatenated input. @ CACHEBLEND 6 which concate- nates the precomputed KV caches of retrieved documents and then recomputes the KV cache for a small number of selected tokens within the retrieved documents. Following the original implementa- tion, we set the recomputation ratio to 18%. @ ALTECAATTENTION [Z). which explicitly trains the model to handle separately encoded KV caches by fine-tuning on QA tasks where retrieved documents are encoded independently. For all baselines and our method, we use Llama-3.2 2-1 2-11 B- B-Instruct and [15 as the backbone models. Since BltckAtttntton and our method require
Llama-3.2-33 1.-ma-3.--3B-Instruue fine-tuning, we ensure fair comparison by using the same data mixture and training hyperparameters for both. Further implementation details for each baseline are provided in Appendix A.3
Implementation. We adopt Llama-3.22 3.2ma 3. I-Intrruc,, -lamm--3.2-3B 10-3B-Instucct and Llama-3. 3.1-8B
Instruct as the backbone models, fine-tuning them for 6,000 steps using global batch size of 64 across 8xH100 GPUs We construct the training dataset by mixing the training sets of 2WikiMQA [16], TriviaQA [7],, pretraining data from FineWeb [18], and TÜLU 19]. Further details on data preprocessing, dataset mixture, and training configurations For our method, we train three versions, each appending 0, 1, or link tokens to every document or context segment, denoted as KVLINKO, KVLINKI, and KVLINK5, respectively.
provided in Appendix A. and A.2
Evaluation configurations. We evaluate the effectiveness of our method in three dimensions: 1 performance with separately encoded KV cache, @ the inference efficiency, @ the general capabil- ity preservation (e.g., math reasoning and instruction forliionnooowwingggg. ability), and + performance with compressed KV cache.
To evaluate the model performance when using separately encoded documents or context segments, we focus on serrival--augmenter question answering tasks including Naturalquestions [10]. 2WikiMQA [16). TriviaQA [17], HotpotQA [ and MuSiQue 20). For Naturalquestions ons, we adopt the evaluation protocol from Liu et al. [21] where the LLM is given question along with set of 10 retrieved documents. The document that contains the correct answer is systematically placed at each of the 10 possible positions across separate evaluation runs. The final accuracy is reported as the average over these 10 evaluations. For 2WikiMQA, HotpotQA, and MuSiQue, we utilize the originally provided retrieved documents for evaluation. For TriviaQA retrieve 10 documents
5

---

Table 1: Performance comparison between KVLINK and other methods. The best results high- lighted bold. KVLINKO, KVLINKI, KVLINK5 refer to using 0, and link tokens respectively.
NQ
2WikiMQA
TriviaQA
HotpotQA
MuSiQue
MultiNews
Samsum
Llama-3.2-1B
Original Llama
44.6%
61.8%
61.6%
49.3%
13.8% 19.9%
0.197 0.193
0.301
Finetuned Upperbound
46.9%
71.9%
68.7%
56.5%
0.291
PROMPTCACHE
18.6%
19.5%
34.9%
20.5%
0.179
CACHEBLEND
25.7%
31.0%
52.0%
28.7%
3.7%
0.126
0.074
BLOCKATTENTION
39.0%
64.3%
64.6%
48.3%
14.3%
0.193
0.247
KVLINK
40.8%
62.2%
63.6%
48.1%
13.5%
0.193
0.256
KVLINK
43.8%
64.9%
65.7%
52.9%
16.0%
0.194
0.257
KVLINK
45.0%
66.0%
66.3%
55.6% %
19.2%
0,196
0.256
Llama-3.2-3B
Original Llama
69.4%
60.4%
72.6%
69.3%
34.8%
0.200
0.328
Finetuned Upperbound
69.7%
74.1%
76.2%
74.3%
41.5%
0.199
0.352
PROMPTCACHE
24.7%
27.8%
55.7%
24.6%
2.2%
0.203
0.224
CACHEBLEND
42.6%
47.6%
64.0%
32.7%
5.5%
0.191
0.146
BLOCKATTENTION
58.8%
70.3%
72.9%
64.3%
28.3%
0.204
0.317
KVLINK
62.1%
70.0%
73.3%
65. 9%
28.8%
0,203
0.316
KVLINK
64.0%
70.9%
73.6%
68.8%
32.5%
0.203
0.318
KVLINK
64.4%
71.2%
73.7% %
69.5% %
35.8% %
0.204
0.320
1lama-3.188
Original Llama
71.3%
77.2%
76. 2%
77.6%
49.1%
0,204
0.348
Finetuned Upperbound
75.1%
78.5%
77.9%
78.2%
46.5%
0.166
0.353
PROMPTCACHE
28.9%
42.2%
62.6%
36.5%
6.7%
0.203
0.329
CACHEBLEND
55.2%
45.9%
68.8%
40.8%
6.0%
0,207
0.320
BLOCKATTENTIOS
70.8%
73.6%
76.6%
72.2%
38.7%
0,166
0.342
KVLINK
71.0%
73.3%
76.4%
72.7%
39.9%
0.163
0.342
KVLINK
72.4%
74.7%
76.6%
73.6%
38.9%
0.340
KVLINK
72.5%
73.8%
76.6%
73.8%
40.8%
0.168
0.345
using Contriever 22 following the setting in BLOCKATTENTION, In all cases, documents are encoded separately into KV cache.
Additionally, following CLCHEBLEND, we evaluate on two text summarization datasets including MultiNews (33 and Samsum 24 The LLM is given several in-context examples per instance, each separately encoded into KV cache. We report the RougeL score (25) as the metric. Notably, our evaluation datasets cover all those used by our baselines, BLOCKATTENTION and CACHEBLEND, ensuring a comprehensive and fair comparison.
To measure inference efficiency, evaluate -oeett--fiitt (TTFT) under different document lengths. Specifically, we fix the number retrieved documents at 10 and vary document lengths from 100 500 tokens, leading to total context lengths ranging from 1,000 to 5,000 tokens. Given pre-computed KV caches stored in CPU memory, we compare the TTFT our method to standard LLM inference, which fully re-encodes all contexts for each query.
To ensure our method does not degrade the model's original capabilities, we evaluate it on range of reasoning and instruction-folloiinn benchmarks, including IFEval (26), GSM8K (27). MMLU (28), Mec-Challenge [29], ARC-Easy [29). PiqA [30], Sciq [3I], Winogrande [32), and
HellaSwar B3 We report the accuracy each dataset. For IFEval, report both strict prompt-
level accuracy (IFEval-P) and instruction- accuracy (IFEval-I), More details of the evaluation configuration available in Appendix A.2
Finally, to further reduce cache-storage and loading overhead, and thereby make cache reuse practical, we evaluate reuse with compressed KV caches. We report QA accuracy under various compression methods and assess the effectiveness of KVLINK when operating on compressed caches. The only difference from the first experiment is that we compressed, rather than original, KV cache.

---

3.2
Main Results
We first evaluate the effectiveness of our method when using separately encoded KV caches. For all QA tasks, each retrieved document is encoded into the KV cache independentl. In summarization tasks, each in-context example is also encoded separately. following the same setup as our basclines. The evaluation results are presented Table
To provide a more comprehensive understanding, we also include the performance of the original Llama models and their fine-tuned versions trained on the same data mixture other methods. Im- portantly, these reference models are evaluated in the standard setting, where the retrieved documents in-context examples are concatenated and encoded being separately encoded into KV cache. This serves as an upper bound for performance, helping contextualize improvements.
single contiguous sequence, rather than
We highlight the key observations below. First, KVLINK consistently outperforms all baselines across all datasets, demonstrating its strong effectiveness. In most QA tasks, our approach surpasses the best baseline, BLOCKATTENTION with up to 5% higher accuracy. The only exceptions are the 2WikiMQA and TriviaQA datasets, whose training On all other evaluation datasets, our method consistently outperforms the baselines, demonstrating superior aut-of-domain generalization performance. For other baselines, the gap more significant. The performance gap is even larger when compared to other baselines. Notably, our method not only outperforms the original Llama models without fine-tuning but also achieves accuracy close fine-tuned Llama, which is evaluated with a fully concatenated context.
included in training data mixture.
Second, the link tokens appended to each document effectively bridge separately encoded documents, restoring inter-document connections. Since one of the key differences between our method and baselines is the of link tokens for cross-document reconnection, the observed performance improvements further validate the effectiveness our design. With negligible computational cost, these link tokens significantly enhance performance. Compared to PLOCCATTENTION, which also fine-tunes the model on QA tasks with separately encoded documents, our method demonstrates the necessity of link tokens. Without them, BL.CK ATTENTION performs worse than our approach despite using the same training data.
Finally, observe consistent performance gain the number of link tokens increases, reinforcing their positive impact.
3.3 Inference Efficiency Evaluation
key objective of KVLINK is to reduce the computational overhead incurred by repeatedly encoding long contexts. To demonstrate these efficiency gains, we measure the Time-to-First-Toke (TTFT) when reusing the precomputed KV cache for ten documents of varying lengths. For a realistic assessment, include the overhead of loading the precomputed KV caches onto the GPU. Each measurement is averaged over 100 runs, with an initial warm-up trials to eliminate memory allocation overhead, following the setup in
Figure compares our methods, KVLINKI and KVLINK5, against standard decoding, which en- codes the entire context for each query. The key observations are as follows. First, reusing the precomputed KV cache significantly improves LLM inference efficiency. To leverage the pre- computed KV cache, we perform three main operations: (1) loading KV caches from CPU to GPU, (2) applying new positional encoding, and (3) encoding the link tokens for each document. All these operations introduce only negligible latency, reducing TTFT by 85%- 96% compared to standard decoding.
Standar Decoding KVLinkS
FIFI (eeond)
86
8.
10*300
Length (token)
Figure Inference speed comparison with ten reused contexts of varying lengths. Both KVLINK and KVLINK5 show considerably lower Time-to-Firse -o-Fiist-Tooen (TTFT) than standard decoding as context size grows.
Second, across all context sizes, both KVLINKI and V consistently achieve substan- tially lower TTFT relative to standard decod-
7

---

Table 2: Performance comparison between KVLINK, original Llama, and finetuned Llama under standard decoding. WG refers to WinoGrande, and HS refers to HellaSwag.
GSM8K
MMLU
IFEval-I
IFEval-P
ARC-E
ARC-C
PIQA
SeiQ
WG
HS
1lama-3.2-BB
Original Llama
44.9
46.1
65.9
35.8
74.3
93.9
59.5
Finetuned Llama
39.7
43.2
64.0
50.8
68.5
35.0
74.6
94.1
59.7
45.2
KVLINK
41.1
42.0
63.2
67.2
33.5
74.1
93.5
57.5
43.7
KVLINK
41.2
42.2
64.4
51.2
67.2
33.4
73.8
93.5
57.5
43.7
KVI.NKK 5
41.0
42.3
64.3
51.4
67.0
33.4
73.8
93.6
57.6
43.6
Llama-3.2-3B
Original Llama
77.2
60.5
82.2
75.6
74.2
43.7
75.7
95.2
67.4
52.2
Finetuned Llama
70.0
60.5
78.4
69.9
72.3
40.3
76.2
96.0
66.8
51.6
KVLINK 0
70.2
60.7
79.4
70.8
40.4
76.0
95.5
65.7
51.4
KVLINK I
70.8
60.9
79.4
70.4
72.3
40.0
76.0
95.6
65.5
51.4
KVLINK 5
70.5
60.9
79.4
70.4
72.6
40.0
76.0
95.6
65.5
51.4
1lama-3.1-a
Original Llama
85.1
68.0
85.1
78.7
81.9
51.7
79.8
96.7
73.7
Finetuned Llama
75.4
64.3
82.7
75.6
80.9
48.3
80.3
96.3
72.9
58.6
KVLINK 0
75.2
64.8
82.8
75.8
82.1
50.8
80.0
96.8
72.5
58.9
KVLINK I
75.5
64.0
82.4
75.4
82.2
51.1
80.7
96.8
72.8
59.0
KVL.NK 5
75.7
64.0
83.0
76.2
81.5
50.4
80.3
96.6
72.4
59.1
ing. As the reused context length increases, the TTFT gap further widens, highlighting the scalability of our approach. Notably, when the context length reaches 5,000 tokens, KVLINK decreases inference latency by 96%. These results confirm that K KVLIKK effectively mitigates the computational cost of large-scale context encoding and is well-suited for scenarios requiring fast response times.
3.4 General Capability Preservation
While our primary objective is to enable efficient cache reuse, we also verify whether these modifications maintain the model's general reasoning and instruction-followigg capabilities. Table presents the results for three model variants: Llama-3.2-1 IB, Llama-3.2-3B and Llama-3. 1-8B. We compare the original models, their fine-tuned counterparts, and our method with different numbers of link tokens (K (VINIO,, KVLINKI, and KVLINK5).
Our key findings are as follows. First, KVLINK maintains competitive performance across all tasks, with only marginal differences from the fine-tuned models. This confirms that KVLINK successfully preserves the model's general capabilities. Across both model sizes, the results of KVLINK are highly comparable the fine-tuned Llama, demonstrating that our method does not significantly degrade the model's general capabilities despite restructuring context encoding.
Second, while there minor drops in certain benchmarks (e.g., ARC-C and Winogrande) compared to the original models, these differences remain within a reasonable range, typically less than 3%. We expect that performance could be further improved by refining the data mixture and incorporating additional data on reasoning and instruction-followii tasks, which we leave for future work.
3.5 KVLINK with Cache Compression
In this section, we further evaluate the effectiveness of our method when combined with KV cache compression techniques, which help reduce the overhead storing and loading precomputed KV caches. For both compression methods described in Section 2.4 we experiment with 50% and 75% compression rates. We fine-tune the Lllam-3.22-1 model using our method and the baseline models on compressed KV caches using the training sets of 2WikiMQA and TriviaQA. Additional training details are provided in Appendix A.6 We compare our method with link tokens to the best-performing baseline, BLOCKATTENTION under KV cache compression on QA tasks.

---

Table 3: Evaluation of K VLINK under different compression regimes. We report the QA accuracy when using compressed cache. The value to the left of the slash (/) corresponds to 75% compression rate and the value to the right corresponds to 50% compression.
NQ 75% / 50%
2WiKIMQA 75% / 50%
TriviaQA 75% / 50%
HotpotQA 75% 50%
MuSiQue 75% / 50%
BLOCKATTENTIO
33.9/37.8
47.3/ 58.2
60.1 64.8
36.1 /4.1
7.1/11.1 6.5/11.5
Prompt Compression
KVLINK
45.5/41.6
47.8/ / 58.2
61.07 65.7
37.3/ 46.6
BLOCKATTENTION
37.5/40.5
68.4 70.0
67.0/ 68.8
51.1 54.3
14.0 16.7
Our Method
KVLINK
40.9/43.0
69.9 69.4
68.2 69.3
52.4 55.4
14.8/ /1..3
The evaluation results are shown in Table 3] We highlight the following findings. First, compared to LLMLINGUA, the modified ANLLMS compression retains substantially more information, resulting in consistently stronger performance across all QA benchmarks. Second, adding link tokens consis- tently mitigates the accuracy drop introduced by compression, restoring the model performance when using both KV cache compression techniques.
3.6 Ablation Study
We also perform ablation studies examining the robustness of our method against different data mixtures. Due to space constraints, the detailed results are provided in Appendix A..4 Our key observation that our method can still achieve competitive performance given different data mix- tures. Also, we find that specific combinations of tasks and domain coverage can slightly influence downstream performance, indicating the importance of balanced data selection. While our initial findings offer insight into more effective training mixtures, we make a comprehensive exploration of optimal data configurations for future work.
Related Work
Efficient inference for LLMs. As model sizes grow, serving LLMs efficiently becomes increasingly challenging. Previous work has tackled this via model pruning 385, quantization [39 and
optimized decoding algorithms such as non-autoregressive decoding (45, speculative decoding [46]-
48), or early-exiting [4]]50] Like these approaches, our method also aims to enhance LLM inference efficiency by reducing inference-tine time computation.
KV cache reuse. Recent work has explored reusing precomputed KV caches across multiple queries, often focusing on prefix-only reuse [51553 A few methods extend reuse to arbitrary positions, aiming for greater efficiency. PROMPTCACHE allows KV cache reuse with discontinuous position IDs but ignores cross-chunk attention, causing performance drops. It also relies Prompt Markup Language, limiting flexibility across tasks. CACHEBLEND reduces positional mismatches by selectively recomputing caches for tokens with the largest value-state variance; however, it suffers from performance degradation and the non-trivial cost of recomputing 10%-20% of tokens (plus all tokens at the first layer). BLOCKATTENTION 7 removes positional embeddings by re-encoding KV caches and directly fine-tunes on attentittnnioon data, but lacks strategies to better connect reused contexts refine data processing, leaving performance below ideal levels. TurboRAG [54] introduces two special tokens to mark the boundaries of reused caches. However, it still falls short in effectively reconnecting reused caches, similar to ATTECTOT A detailed discussion is provided in Appendix A.8
KV compression. While our method focuses accelerating inference by reusing KV caches, complementary line work aims to reduce memory overhead through cache eviction and quantization. For instance, (55158] introduces eviction policy that significantly lowers the memory footprint investigate quantizing KV caches to minimize storage requirements with only minor performance loss. Notably, our approach can be seamlessly integrated with these state-of-the-ar eviction and quantization strategies, thereby addressing both speed and memory efficiency.
during generation, while [59 42 39
60 62
Retrieve-augmented generation. Retrieval-augmented generation (RAG) is widely used to enhance the generation capabilities of language models by retrieving supporting documents. Retrievers such

---

as dense retrievers or BM25 22 63 64 are typically employed to find the most relevant documents for a given user query or context. addition to simply concatenating the retrieved text with the input [65] there are also other methods for integrating the retrieved knowledge into the models. For instance, LongMem [66] encodes documents into caches and uses a trained side net to incorporate these knowledge caches into the context for long-context tasks. With the advances of L.MS across
various NLP tasks, certain studies have focused on improving RAG with LLM 167 68). Some
research also explores how to enhance the robustness of LLMs when processing retrieved knowledge. For example, RAFT [69] provides a fine-tuning strategy that strengthens LLMs against noisy contexts in domain-specifer RAG.
5 Conclusion
In this paper, we introduced method improve LLM efficiency by reusing pre-computed KV caches. With precomputed KV caches for retrieved documents or context segments, our method can avoid redundant computation for overlapping contexts across different queries. In the future, we will refine our data mixture and investigate optimal fine-tuning strategies to further enhance performance. Additionally, we plan to explore real- world deployment scenarios to maximize the inference efficiency of L.Mss. The limitation and societal impact sections are included in the Appendix.
Acknowledgments
The work of Jingho Yang, Bairu Hou and Shiyu Chang was partially supported by National Science Foundation (NSF) Grant IIS 133-233,5,,, NSF Grant 220722,,, and NSF Grant IIS 2302730.. The computing resources used in this work were partially supported by the Accelerate Foundation Models Research program of Microsoft.
References
[1] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. eetrieval-augmenn generation for large language models: A survey. arXiv preprint arXiv:2312. 10997, 2023.
[2] Xiaohua Wang, Zhenghua Wang. Xuan Gao, Feiran Zhang, Yixin Wu, Zhibo Xu, Tianyuan Shi, Zhengyuan Wang, Shizheng Li, Qi Qian, al. Searching for best practices in retrieval- augmented generation. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 17716-17736, 2024.
[3] Zhuowan Li, Cheng Li, Mingyang Zhang, Qiaozhu Mei, and Michael Bendersky. Retrieval augmented generation or long-contex: Ilms? a comprehensive study and hybrid approach. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track, pages 881, 2024.
[4] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. Autogen: Enabling next-gen Ilm applications via multi-agent conversation framework. arXiv preprint arXiv:2308.08155 2023.
[5] Zijun Liu, Yanzhe Zhang, Peng L., Yang Liu, and Diyi Yang. A dynamic 11m- in-ppoeeeed agent network for task-oriented agent collaboration. First Conference on Language Modeling, 2024.
[6] Jiayi Yao, Hanchen Li, Yuhan Liu, Siddhant Ray, Yihua Cheng, Qizheng Zhang, Kuntai Du, Shan Lu, and Junchen Jiang. Cacheblend: Fast large language model serving with cached knowledge fusion. arXiv preprint arXiv:2405.16444, 2024.
[7] East Sun, Yan Wang, and Lan Tian. Block-attention for efficient rag. arXiv preprint 253355240..15355, 2024.
[8] Zhisong Zhang, Yan Wang, Xinting Huang, Tianqing Fang, Hongming Zhang, Chenlong Deng, Shuaiyi Li, and Dong Yu. Attention entropy is key factor: An analysis of parallel context en- coding with full-attention-basee pre-trained language models. arXiv preprint arXiv:2412. 16545 2024.
10

---

[9] In Gim, Guojun Chen, Seung-seor seob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems, 6:325-338, 2024.
[10] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: benchmark for question answering research. Transactions of the Association for Computational Linguisties, 7:453 366334662222 2019.
[11] Zhilin Yang, Peng Qi. Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhut- dinov, and Christopher D Manning. Hotpoiqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint wiXiv:/809.000
2018.
[12] Zhuoshi Pan, Qianhui Wu, Huiqiang Jiang, Menglin Xia, Xufang Luo, Jue Zhang, Qingwei Lin, Victor Rühle, Yuging Yang, Chin- Yew Lin, al. LImlingua-22 Data distillation for efficient and faithful task-agnostic prompt compression. arXiv preprint arXiv:2403.12990 2024.
[13] Jianhui Pang, Fanghua Ye, Derek Wong, Xin He, Wanshun Chen, and Longyue Wang. Anchor- based large language models. In Findings of the Association for Computational Linguistics ACL 2024, pages 4958-4976, 2024.
[14] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 1676127, 2024.
[15] Meta AI. and
Llama and vision: devices, 11 ama 3- 2- wow.emttt222--issio-e--e----e-ee www.--eeddde-ooleeeeieeeeeeeeeee
Bringing
next-gen ai to edge
mobile
2024.
URL
https://ai.mett meta. com/blog/
Accessed: 2024-11-
10.
[16] Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th International Conference on Computational Linguistics, pages 6609-6625 2020.
[17] Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
pages 1601-1611. 1,1611122 2017.
[18] Guilherme Penedo, Hynek Kydlíček, Loubna Ben allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro Von Werra, and Thomas Wolf. The fineweb datasets: Decanting the web for the finest text data at scale. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024.
[19] Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. T ulu 3: Pushing frontiers in open language model post- post-traiiing. arXiv preprint 2rXiv:2411.15122 2024.
[20] Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Musique: Multihop questions via sinle-hop question composition. Transactions of the Association for Computational Linguistics, 10:539-554 554, 2022.
[21] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-173, 2024.
[22] Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. Unsupervised dense information retrieval with contrastive learning. arXiv preprint arXiv:2112.091188 2021.
[23] Alexander R Fabbri, Irene Li, Tianwei She, Suyi Li, and Dragomir R Radev. Multi-news: A large-scale multi-document summarization dataset and abstractive hierarchical model. arXiv preprint arXiv: 01749, 2019.

---

[24] Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer. Samsum cor- pus: A aaman-annotated dialogue dataset for abstractive summarization. arXiv: 122377, 2019.
arXiv preprint
[25] Chin-Yew Lin. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pages 74-81, 2004.
[26] Jeffrey Zhou, Tianjian Lu. Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. Instruction foolloing evaluation for large language models. arXiv preprint wrXiv:2311.07911 2023.
[27] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14/68, 2021.
[28] Dan Hendrycks. Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXiv preprint arXiv:2009.048 03300, 2020.
[29] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint (003vv080000055577 2018.
[30] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piqa: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages 1432-7439 2020.
[31] Johannes Welbl, Nelson F Liu, and Matt Gardner. Crowdsourcing multiple choice science questions. arXiv preprint arXiv: 06209, 2017.
[32] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge scale. Communications of the ACM, 64(9):99-106, 2021.
[33] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv:1905.077 2019.
[34] Guangxuan Xiao, Jiaming Tang. Jingwei Zuo, Junxian Guo, Shang Yang. Haotian Tang, Yao Fu, and Song Han. Duoattention: Efficient long-context Ilm inference with retrieval and streaming heads. arXiv preprint wxXiv:2410.00//1 2024.
[35] Xin Men, Mingyu Xu, Qingyu Zhang, Bingning Wang, Hongyu Lin, Yaojie Lu, Xianpei Han, and Weipeng Chen. Shortgpt: Layers in large language models are more redundant than you expect. arXiv preprint 2rXiv:24033.3883 2024.
[36] Sharath Turuvekere Sreenivas, Saurav Muralidharan, Raviraj Joshi, Marein Chochowski, Mostofa Patwary, Mohammad Shoeybi, Bryan Catanzaro, Jan Kautz, and Pavlo Molchanov. Llm pruning and distillation practice: The minitron approach. arXiv preprint arXiv:2408.11796 2024.
[37] Mengzhou Xia, Tianyu Gao, Zhiyuan Zeng, and Danqi Chen. Sheared lama: Accelerating language model pre-training via structured pruning. In The Twelfih International Conference on Learning Representations, 2024.
[38] Bairu Hou, Qibin Chen, Jianyu Wang, Guoli Yin, Chong Wang, Nan Du, Ruoming Pang, Shiyu Chang, and Tao Lei. instractionffolloiin pruning for large language models. Forty-second International Conference on Machine Learning. 2025.
[39] Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. Awq: Activation-aware weight quantization for on-device IIm compression and acceleration. Proceedings of Machine Learning and Systems, 6:87-100, 2024.
12

---

[40] Mart van Baalen, Andrey Kuzmin, Markus Nagel. Peter Couperus, Cedric Bastoul, Eric Mahurin, Tijmen Blankevoort, and Paul Whatmough. Gptvq: The blessing of dimensionality for Ilm quantization. arXiv preprint arXiv:2402. 15319, 2024.
[41] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gpiq; Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210. 173233, 2022.
[42] Guangxuan Xiao, Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models. In International Conference on Machine Learning, pages 38087-38099. PMLR, 2023.
[43] Zhewei Yao, Reza Yazdani Aminabadi, Minjia Zhang, Xiaoxia Wu, Conglong Li, and Yuxiong He. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. Advances in Neural Information Processing Systems, 35:27168-27115 2022.
[44] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Gpt3. int8 (): 8-bit matrix multiplication for transformers scale. Advances in Neural Information Processing Systems, 18:30318-30332 2022.
[45] Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Riccardo Marin, and Emanuele Rodolà. Accelerating transformer inference for translation via parallel decoding. arXiv preprint WrXiv:2305.10422 2023.
[46] Schoon Kim, Karttikeya Mangalam, Suhong Moon, Jitendra Malik, Michael W Mahoney, Amir Gholami, and Kurt Keutzer. Speculative decoding with big little decoder. Advances in Neural Information Processing Systems, 36, 2024.
[47] Mostafa Elhoushi, Akshat Shrivastava, Diana Liskovich, Basil Hosmer, Bram Wasti, Liangzhen Lai, Anas Mahmoud, Bilge Acun, Saurabh Agarwal, Ahmed Roman, et al. Layer skip: Enabling early exit inference and self-speculative decoding. arXiv preprint arXiv:2404. 16700..661..... 2024.
[48] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, al. Specinfer: Accelerating generative large language model serving with tree-based speculative inference and verification. arXiv preprint arXiv:2305.0978) 2023.
[49] Xuanli He, Iman Keivanloo, Yi Xu, Xiang He, Belinda Zeng, Santosh Rajagopalan, and Trishul Chilimbi. Magic pyramid: Accelerating inference with early exiting and token pruning. arXiv preprint arXiv:2111.000 000300, 2021.
[50] Jun Kong, Jin Wang. Liang-Chih Yu, and Xuejie Zhang. Accelerating inference for pretrained language models by unified multi-perspective early exiting. In Proceedings of the 29th Interna- tional Conference on Computational Linguistics, pages 4677-4686, 2022.
[51] Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Xin Liu, Xuanzhe Liu, and Xin Jin. Ragcache: Efficient knowledge caching for sttreval-auugmetee generation. arXiv preprint arXiv:2404.1244 12457, 2024.
[52] Shu Liu, Asim Biswal, Audrey Cheng, Xiangxi Mo, Shiyi Cao, Joseph E Gonzalez, Ion Stoica, and Matei Zaharia. Optimizing Ilm queries in relational workloads. arXiv preprint arXiv:2403.0553 055.2 2024.
[53] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody_ Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Efficiently programming large language models using sglang. 2023.
[54] Songshuo Lu, Hua Wang, Yutian Rong. Zhi Chen, and Yaohua Tang. Turborag: Accelcrating retrieval-augmented generation with precomputed kv caches for chunked text. arXiv preprint arXiv:2400.07590. 2024.
[55] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024.
13

---

[56] Matanel Oren, Michael Hassid, Nir Yarden, Yossi Adi, and Roy Schwartz. Transformers are multi-state mns. arXiv preprint arXiv:2401.06104 2024.
[57] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309. 17453, 2023.
[58] Suyu Ge. Yunan Zhang. Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for llms. arXiv preprint arXhv:2310.01801, 2023.
[59] Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A tuning-free asymmetric 2bit quantization for kv cache. arXiv preprint 2402:2402.002500 2024.
[60] Sehoon Kim, Coleman Hooper, Amir Gholami, Zhen Dong, Xiuyu Li, Sheng Shen, Michael W Mahoney, and Kurt Keutzer. Squeezellm: manse-andspprse quantization. arXiv preprint arXiv:2306.0777 07629, 2023.
[61] Yilong Zhao, Chien- Yu Lin, Kan Zhu, Zihao Ye, Lequn Chen, Size Zheng, Luis Ceze, Arvind Krishnamurthy, Tianqi Chen, and Baris Kasikci. Atom: Low-bit quantization for efficient and accurate IIm serving. Proceedings of Machine Learning and Systems, 6:196-209, 2024.
[62] Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High-throughput generative inference of large language models with single gpu. In International Conference on Machine Learning, pages 31094-31116, 166. PMLR, 2023.
[63] Jinhyuk Lee, Mujeen Sung, Jaewoo Kang, and Danqi Chen. Learning dense representations of phrases at scale. arXiv preprint arXiv:2012./2624 2020.
[64] Stephen Robertson, Hugo Zaragoza, et al. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends@ Information Retrieval, 3(4):333-389 2009.
[65] Gautier Izacard and Edouard Grave. Leveraging passage retrieval with generative models for open domain question answering. arXiv preprint arXiv:2007.01282 2020.
[66] Weizhi Wang, Li Dong, Hao Cheng, Xiaodong Liu, Xifeng Yan, Jianfeng Gao, and Furu
Wei. Augmenting language models with long-term memory. Advances in Neural Information Processing Systems, 36:74530-74543, 2023.
[67] Florin Cuconasu, Giovanni Trappolini, Federico Siciliano, Simone Filice, Cesare Campagnano, Yoelle Maarek, Nicola Tonellotto, and Fabrizio Silvestri. The power of noise: Redefining retrieval for rag systems. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 719-729, 2024.
[68] Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. Self-rag: Learn- ing to retrieve, generate, and critique through self-reflection. In The Twelfth International Conference on Learning Representations, 2023.
[69] Tianjun Zhang, Shishir G Patil, Naman Jain, Sheng Shen, Matei Zaharia, Ion Stoica, and Joseph Gonzalez. Raft: Adapting language model to domain specific rag. In First Conference on Language Modeling, 2024.
[70] Zhilin Wang, Yi Dong, Olivier Delalleau, Jiaqi Zeng, Gerald Shen, Daniel Egert, Jimmy J Zhang, Makesh Narsimhan Sreedhar, and Oleksii Kuchaiev. Helpsteer2: Open-source dataset for training top-performing reward models. arXiv preprini arXiv:2406.088 240.0773.... 2024.
[71] Shashi Narayan, Shay B Cohen, and Mirella Lapata. Don't 't give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1797-1807, 2018.
[72] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint a0X1v:2303300874.220 2023.
14

---

[73] Nikhil Kandpal, Haikang Deng, Adam Roberts, Eric Wallace, and Colin Raffel. Large language models struggle learn long-tail knowledge. In International Conference on Machine Learning. pages 15696-15701 PMLR, 2023.
[74] Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Ha- jishirzi. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories. arXiv preprint arXiv:2212.10571. 2022.
[75] Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac"h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. A framework for few-shot language model evaluation, 07 2024. URL https://zenodo. org records/ 12608602
15

---

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 contribution of the paper is to propose KVLINK for addressing performance degradation problem in cache reuse, thus accelerating LLM inference. The main claims made in the abstract and introduction is also verified by experimental results in Section 3
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitation is discussed in the Appendix A.9
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best 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.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
16

---

Answer:
[NA]
Justification:
The 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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 details of reproducing the proposed method and the experiment results are included in Section 3.1 and Appendix AA.2] We will also release the code, datasets, and
KVLINK models used in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a specific model and empirical evaluation, it may be necessary to either make it 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 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, other means that appropriate to the research performed.
also be provided via detailed
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 to reproduce that algorithm.
(b) the contribution is primarily new 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 reprodueibility may be tricky in some cases, in which authors are welcome to describe 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., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
17

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The code and data will be provided in supplemental material. There will be detailed instructions about setting up environment, data processing and reproducing the results.
Justification:
Guidelines:
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" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//abps.cc/pullic/uuiide
swssssssiinyyyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
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 details for training and test are included in Section 3.1 and Appendix A.2
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, 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: Error bars not reported because empirically the training process is stable and greedy decoding is used in the evaluation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

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.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. 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 show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error 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 or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiment computer resources used are reported in the Section 3.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount 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 ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt////nuripppp http://rrrppp.pcppeee/ee///e/eee http://bblcc/tticcccccieeeeeeeee
Answer: [Yes]
Justification: The research conducted in the paper conform with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
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 (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The socictal impacts discussed in the Appendix A.I0
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

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), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not introduce any additional risk of LLM misuse.
Guidelines:
The answer NA means that the paper poses 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 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 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: The creators owners of assets used are well credited and the corresponding licenses are included in Appendix A.
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 or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.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.
20

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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.
If this information 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: The 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components. LLMs are only used for editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
22

---

Table 4: Overview of tasks, datasets, and sample counts with and without context reuse.
Separately Encoded KV Cache
Standard Decoding
Task
Retrieval-aug- QA
Multi-turn conv.
Summaarizatio
Retrieval-aug- QA
SFT
Pre-training
TrivisQA, 2WikMMAA
DasingAntean
TriviaQA, 2WikMMAA
sft
Fineweh
Percentage
10%
25%
5% 17,345
10%
3056
205
Total of Samples
20,000
92,700
20,000
732,100
10,000,000
A Appendix
A.1 Data Mixture
We fine-tuned our model using a mixture of different datasets.
Setrieval-augmentee QA. Since RAG is the most directly relevant task, we first consider fine- tuning the model on QA tasks with retrieved documents that are separately encoded to ensure it can produce high-quality responses under this setting. More specifically, we sample questions from TriviaQA [17] and 2WikiMQA [T6]. For each question, we retrieve ten relevant Wikipedia passages using Contriever [22]. each encoded separately. To obtain high-quality supervision, we prompt GPT-4 to generate reference answers, which serve the ground truth for training.
70 contain multi-turn conversations between the user and the assistant, which provides natural way to train the model on disjointed contexts. We randomly convert earlier conversation turns into independently encoded KV caches, and the LLM is then trained to produce the appropriate responses in subsequent turns. This ensures the model to learn integrate segmented contexts while maintaining its instruction-following capability.
Multi-turn conversation. Many existing instruction-followii datasets
Summarization. Summarization serves as another useful setting where the model must aggregate information from independently encoded document chunks to generate a coherent summary. We adopt the XSum (7l) dataset. Each document is randomly split into multiple consecutive segments, and each segment is independently encoded into KV cache. The model is trained to generate the ground-truth summary, ensuring it learns to integrate information across separate segments.
Additionally, better preserve the model's original capabilities, we also include standard version of TriviaQA and 2WikiMQA, where the retrieved documents are encoded as a whole rather than separately. In this setting, the model is trained generate the ground-truth answer conditioned on the fully concatenated context. Lastly, we incorporate the T"ULU 3 dataset [19 to preserve the instruction-followin ability and small portion of pre-training data from Fineweb [8 preserve the language modeling capability.
Table Provides overview of the data used in training. For the multi-turn conversation data, each prior user-asses asssisaattt conversation is independently encoded as a reused context, and we compute the training loss only the assistant's 's final response. In the summarization task, split the source document into 100-token segments, each serving as a reused context. All training examples are truncated maximum length of 4096 tokens.
A.2 Implementation Details
Training. we propose fine-tuning the LLM with mixed dataset drawn from different sources, enabling the model to integrate disjoint context segments while preserving its original capabilities.
Figure 5 iillustrates the system prompts use for each task category during training. These prompts are generated by GPT-4 (72), and are randomly picked during training. Additionally, for the QA training data, we also shuffle the retrieved reused documents in the context A.5
Figure demonstrates how each data sample is processed when the context is reused KVLINK. Particularly, we also include two special tokens, KV-START and KV-END to specify the boundaries of the reused contexts. For each reused document or context segment, the link tokens are dependent on the index of the document in all the reused documents, which means, in different prompts, for
23

---

Multi-ture Conversation
<SYS> You are an AI assistant. </SYS> <KV_ ST_RT
<USER> Write an email about </USER>
<ASSITANT> Here is the email about </ASSISTANT> <link1 <link1_2> <USER> The subject
not good enough </USER>
<ASSITANT> Here is a revised version_ </ASSISTANT> <link2_1> <link2_2> <KV_END> END> <USER> You also need to modify </USER>
<ASSITANT> </ASSISTANT>
surrleve-augmenterr QA
Summarization
<USER> <KV START>
<USER> <KV IKV_START>
Document [1] (Title:
The Nobel Prizes are five separate
<link1_1> 1> <link1_2g _2
<link1_1> <link1_2>
Document [2] (Title:
prizes awarded to those who conferred
<link2 <link2 2>
<link2 <link2_2>
<KV_ WND>
END>
Question: </USER>
Summarize the above passage. </USER>
Figure 4: Data Preprocess for Context Reuse.
SFT
"You AI assistant. Provide helpful, accurate, and clear answers, when uncertain, explain your reasoning request clarification."
"You Al assistant. Focus achieving the user's goal in each interaction. Use concise informative explanations."
"You are Al assistant. Speak clearly and stay consistent with priar statements. If you need more information, politely
it."
"You are AI assistant. Provide truthful, well-sourced information whenever possible. Acknowledge any Linitations and speculation if
"You are an AI assistant. Use the provided documents answer the user's question. If the information is insufficient, acknowledge the or request clarification."
"You are an AI assistant. Always ground your answers the retrieved documents and not add unsupported details. If the documents lack sufficient information, indicate that."
"You are an AI assistant, Rely sotely on the given documents for evidence when answering questions. When necessary, cite paraphrase the document content accurately."
"You are AI assistant. Base your replies on the retrieved documents, ensuring completeness and correctness. Ask for more details if the documents do nat cover the question fully."
Summarization
"You are an assistant. Read the provided text and produce a concise summary. Capture the nain points without unnecessary detail."
"You are an assistant. Sumarize the essential ideas from the given text. Avoid einor detaits and focus critical insights."
"You are an assistant, Provide brief, high-level overview of the text. Ensure clarity and coherence, prioritizing key thenes."
"You are an assistant, Sumarize the text clearly and logically. Organize the wein ideas in caherent sequence."
Figure 5: System Prompts Used for Training. We employ tailored system prompts for three primary task types-SPr SFT, QA, and Summarization reflecting different objectives and guiding the model's responses accordingly.
24

---

the n-th reused document, its link tokens are always linkn-1 1, linkn-22 ... linkn- K, if K link tokens are used.
Evaluation.
For QA evaluation with separately encoded KV cache, we adopt the accuracy as the
evaluation metrie, following 21 7 74), which considers the prediction correct if any sub-string of the prediction exactly matches any gold answer.
For the evaluation of general capability preservation, we use LM Evaluation Harness 75 We few-shot examples for GSM8K and KMLU(8-shot for GSM8K and 5-shot for MMLU).
A.3 More Implementation Details of Baselines
For BLOCKÄTTENTION, we process the training data with context reuse in 4 by separately encoding each reused document context segment and concatenating the caches directly without inserting any special tokens in between. For the data with no context reuse, the data processing is the same as KVLINK.
For PROMPTCACHE, in its original implementation, the position encoding is not adjusted when reused in the new prompt. It uses discontinuous position information between reused caches, which not accurate. We maximize the performance PROMPTCACHE by giving the reused contexts with gold position information during evaluation.
A.4 Ablation Studies Data Mixure
Table 5: Performance on different training data mixture.
ZWibd
TritaQA
HlotpoRQA
MuSiQue
Samsum
GSM8K
MMLU
IFEval-P
ARC-E:
ARC-C
PSQA
SeQ
KVLinks
45,0
06.0
66.3
55.6
19.2
0.256
41.0
42.3
04.3
51.4
67.0
33.4
73.8
93.6
No Summorization
26.5
06.6
67.2
56.6
18.5
0.240
40.6
45.2
01.5
49.8
67.6
34.6
73.7
94.6
No Multi-tora Cony.
48.2
68.7
67.
56.2
17.8
0.262
40.
44.2
63.5
31.7
68.0
33.1
73.9
94.7
QA only
48.9
69.3
68.4
58.3
17.3
0.242
435
45.2
63.9
528
64.9
34.7
72.9
90.5
We experiment with various data mixtures under the KVLINK5 setting, each omitting a distinct subset from our original training mix (see Appendix (A.I). Specifically, No Summarization, No Multi-turn Conversation, and QA Only (see Table For the first two, retain the same relative proportions among the remaining tasks and train for 6,000 steps, while QA Only is trained for two epochs to prevent overfitting. Our results show that tasks requiring cross-chunk reasoning
explore three configurations:
essential for robust cache reuse. Moreover, incorporating multiple types of cache-reuse reuse data improves generalization. However, the optimal recipe of training data for fully equipping LLMs with general cache-reuse capabilities remains an open question, which we leave to future work.
A.5 Impact of Answer Document Position
Empirically, we have observed that directly constructing the QA training data using Contriever 22 retrieved relevant documents is not ideal because the retriever typically places the answer-containing document near the front based on the relevance score. As a result, the fine-tuned model "learns" to find answers the beginning of the context rather than reasoning across the entire reused context.
To validate our statement, we fine-tune the Llama-3.2-3B base model on the same training data without shuffling as BLOCKATTENTIO and evaluate under the (2I] setup. In (2I), the test set for NaturalQuestions also built with Contriever-retrieeed contexts but places the document containing the correct answer varying positions. As shown in Figure 6 the model's performance drops significantly whenever the ground-truth document is located further back the context.
A.6 Training of Modified ANLLM Compression
Our training of modified ANLLM compression contains two stages: continuous pre-training and QA tuning.
25

---

70
65
60
Accurac
55
50
45
40
4 Answer
8
9
10
Document Index
Figure 6: Impact of Answer Document Position on Accuracy. The accuracy substantially decreases when the correct document is located farther from the start, indicating the necessity of shuffling the retrieved documents in the QA training data.
L CE
Continuous pre-training
segment1 (0:100)
segment2 (100:200)
segment3 (200:300)
link
link
fCE
QA Tuning
Doc1 (0:100)
Doc1 (100:180)
Doc2 (0:90)
Question
Answer
attention
compression
tokens
Figure 7: The attention during training compression tokens.
Continuous pre-training. This stage involves training the compression tokens to capture informa- tion from longer preceding sequence. As shown in Figure 7 given it into two halves. We compress the former half and calculate the cross-entropy loss on the latter half. During compression, we segment the former half into multiple text segments based on fixed token length of 100 tokens. After each segment, we append several compression tokens. These compression tokens attend to all the preceding compression tokens and the original tokens in their segment, which distinguishes our approach from ANLLMM. The original tokens in each segment maintain local attention, and the tokens in the latter half cannot attend these original tokens, but only to the compression tokens.
sample, first divide
26

---

QA tuning. The goal of QA tuning is to adapt the compression tokens to compress the document and further train the model perform QA tasks based on the compressed information. The attention mechanism during QA tuning is similar to that in continuous pre-training. The only difference is that the compression tokens of each document cannot attend one another.
A.7 Storage Demand of KV Cache Reuse
Storing KV caches comes with a higher cost than storing the original text. Below, we discuss the trade-off between storage and efficiency and how can be managed.
First, combining KVLinnk with existing KV cache compression methods helps reduce storage usage. In Section 2.4 we presents two such approaches, demonstrating that well-designed compression strategy causes minimal performance loss. Ongoing improvements in compression can further reduce the storage demand.
Second, GPU usage cost is typically higher than storage cost. As shown in our experiments, when running Llama3.1-88 model on A100 80GB GPU, KVLink can cut latency by 96% for 5000-token input. Under fixed GPU hours, this allows KVLink to handle 25 times more requests than standard decoding. For every million of these requests, KVLink takes 9 GPU hours (16 USD), while standard decoding uses 246 GPU hours (440 USD), based on the current rate (1.79 USD/hour for A 100 80GB). On the other hand, storage remains inexpensive. For example, Amazon S3's standard plan charges just 0.023 USD per GB each month.
Finally, we can lower storage cost through system-level solutions. Two design strategies can be used:
Cache only bigh-hit-rate documents. Strategies like LRU or LFU can help identify which docu- ments to keep in cache. Others can be stored in plain text as usual.
@ We can tiered KV cache storage to further save storage cost. For example, although a 1,000- token document stored as UTF-8 text occupies about 5KB, whereas its Llama3-8B KV cache requires roughly 131MB. We put this cache in cheaper storage if it is seldom used. In general, low-access caches should be saved on cheaper storage like SSDs, while important ones stay in faster memory like CPU RAM.
A.8 Comparison with TurboRAG
Another baseline for KV cache reuse is TurboRAG 54 we include its discussion here as it is similar to another baseline in our experiments, BlockAttention 77., where the reused caches directly concatenated. More specifically, 1 TurboRAG introduces two extra tokens: prepending <doc_start> the document and appending <doc croo__ed>__> to the document. Similar Block Sttenttteniinn, TurboRAG computes and stores the KV cache of the document and the two tokens with local self-attention. That means the two tokens are precomputed offline as part of the document and only maintain local attention within the document to mark the document boundaries. @ Therefore, these two tokens are mainly used indicate the boundaries of documents. In contrast, our method introduces link tokens and recomputes their KV cache at testing time to reconnect the separately encoded documents. During the training phase, we also introduce the link tokens and train them with the objective of connecting the separately computed contexts, which brings better performance compared to TurboRAG and Block
We also conduct experiments to empirically compare KVLink to TurboRAG, We replicate TurboRAG and train using the same training data and training setup as our method. Result is shown in Table
NQ
2WiKIMQA
TriviaQA
HotpotQA
Musique
avg.
Llama-3.2-1B
KVLINK5
45.0
66.0
66.3
55.6
19.2
50.4
TurboRAG
43.4
65.5
64.8
51.8
15.2
48.1
1lama-3,2-3B
KVLINK5
64.4
71.2
73.7
69.5
35.8
62.9
TurboRAG
62.9
69.5
72.9
65.6
31.4
60.5
Table 6: Comparison of KVLink5 and TurboRAG across QA datasets.
27

---

A.9 Limitations
Although our approach achieves state-of-the-an performance while improving the inference efficiency, it still has several limitations, Although KVLINK can restore performance with compressed cache, there is still some performance degradation after compression. One possible solution is to conduct larger scale training for better compression and linking. Second, the size of KV cache varies a lot, because partially based on the document length. Therefore, it will be hard to store these cache in the vector database. Efficiently organizing and storing the pre-computed KV cache remains challenge for large-scale deployment.
A.10 Societal Impact
In this paper, our primary goal is to improve LLM efficiency by reusing KV caches. Our method designed to improve both inference efficiency and also maintain the model performance on downstream tasks. The training data used in this paper is well-known and widely used in other projects, and we verify its quality and safety to ensure that no private or sensitive information included in the training or evaluation process. Also, The KV cache reuse approach proposed in this paper does not introduce additional risks or bias in LLMs. While we acknowledge that any LLM can have bias or potential misuse, the likelihood of risk misuse of our proposed technique is considerably reduced.
A.11 License
Various datasets are included for training and evaluation, and their licenses are listed below: The IFEval, NaturalQuestions, 2WikiMQA. TriviaQA, HotpotQA dataset is released under the Apache License 2.0. HumanEval, MMLU, GSM8K, HellaSwag, WinoGrande, XSum and LM-Evaluation- Harness are under the MIT License. The ARC dataset is provided under the Creative Commons Attribution Share Alike 4.0 license, and SciQ is under the Creative Commons Attribution Non- Commercial 3.0 license. The Dating dataset under the license Creative Commons Attribution 4.0. The MuSiQue dataset is under the Creative Commons Attribution 4.0 International license. The Samsum dataset is under the Creative Commons Attribution Non Commercial No Derivatives 4.0 license. The MultiNews dataset is under a legal agreement with LILY LAB. PiQA licensed under the Academic Free License v. 3.0. The Tulu3-sft- are under the Open Data Commons License Attribution family license. All datasets and software packages in this study are used strictly for their intended purpose- numpos--nmmely, training and evaluating LLMs. We confirm that personal identifying information offensive content appears in materials.
and fineweb datasets
A.12 LLM Usage
We employed GPT-4 to assist with proofreading and improving clarity throughout the text. Neverthe- less, the research concepts, analysis, and original writing remain fully authored by us.
28


Reviews:
[{"review_id": "QQGsZwGDie", "reviewer": "Reviewer_534y", "summary": "The paper introduces KVLINK, a method for accelerating large language models (LLMs) by enabling efficient key-value (KV) cache reuse across queries with overlapping context segments, such as in retrieval-augmented generation (RAG) scenarios. Traditional LLMs redundantly re-encode identical context segments for each query, leading to significant computational inefficiency. KVLINK addresses this by precomputing the KV cache for each document independently and then concatenating these caches at inference time, allowing for direct reuse.", "questions": "1. How does KVLINK perform in scenarios where the overlap between context segments across queries is low? Is there a break-even point where the overhead of precomputing and managing caches outweighs the benefits?\n\n2. Is there any degradation in model performance for tasks that require strong cross-document reasoning? Given, often times it's not possible to know ahead of time, what use case the query+documents are for.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "[+] KV cache positional re-encoding, and trainable cross-segment special (link) tokens as techniques to overcome the performance degradation of independently encoded KV caches. \n\n[+] Significant Efficiency Gains: KVLINK achieves up to 96% reduction in time-to-first-token latency by reusing precomputed KV caches, making it highly scalable for applications with overlapping contexts\n\n[-] The KVLINK technique works under the assumption of the existance of the `c_{linki}` tokens. However, section 3.1 only mentions \" fine-tuning them for 6,000 steps using a global batch size of 64 across 8×H100 GPUs\". Does this mean that `c_{linki}` is just a special set of markers and NOT special token (OR) there is an additional mid-training phase where the tokens are baked in?", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer 534y for the valuable recognition of our work and insightful questions. Your comments have been a great help in improving and improving our work. Below is a detailed response to the key points you raised.\n\n**Q1:** **Are link tokens just a special set of markers and NOT special tokens (OR) there is an additional mid-training phase where the tokens are baked in?**\n\n**A1:** Thank you for your question. These link tokens are indeed special tokens, designed to restore the cross attention between the documents at test time. Please find our explanations below.\n\n- First, we highlight that the hidden representations of these link tokens are recomputed at inference time using standard self-attention. Instead of treating them as markers to separate each document and saving their KV cache together with the documents, the KV cache of these tokens is recomputed to restore the cross attention between documents. We do not have a separate mid-training phase for link tokens. Instead, the embeddings of link tokens and all other tokens are trained together during the fine-tuning stage. Through this stage, the link tokens learn to compensate for the missing cross-attention between the separately computed KV caches.\n\n- Second, we empirically verify whether the link tokens act as special tokens and not just as markers to separate documents. We conduct another experiment where we insert two special tokens, doc_start and doc_end, as markers to indicate the boundaries of each reused document. Unlike link tokens, these two tokens are precomputed offline with the document and only maintain local attention inside the document. This method uses the same training process and computation as our method. Below is our experimental result:\n\n| Task            | NQ   | 2WikiMQA | TriviaQA | HotpotQA | Musique |\n| --------------- | ---- | -------- | -------- | -------- | ------- |\n| **Llama3.2-1B** |      |          |          |          |         |\n| KVLink5         | 45.0 | 66.0     | 66.3     | 55.6     | 19.2    |\n| Markers         | 43.4 | 65.5     | 64.8     | 51.8     | 15.2    |\n| **Llama3.2-3B** |      |          |          |          |         |\n| KVLink5         | 64.4 | 71.2     | 73.7     | 69.5     | 35.8    |\n| Markers         | 62.9 | 69.5     | 72.9     | 65.6     | 31.4    |\n\nWe observe a consistent performance improvement with link tokens. This performance gap shows the necessity of using link tokens to restore cross attention.\n\n**Q2:** **How does KVLINK perform in scenarios where the overlap between context segments across queries is low? Is there a break-even point where the overhead of precomputing and managing caches outweighs the benefits?**\n\n**A2:** Thank you for this insightful question! We agree that KVLink speeds up pre-filling by reusing the cache across different queries, but when the overlap between the queries becomes low, the cost of managing the cache may outweigh the benefits it brings. One extreme example is when all queries retrieve different documents.\n\nHowever, we believe that the overhead in this case can be reduced in two ways:\n\n- **Tier-based caching system.** We believe the cache management cost can be further optimized through system-level design. Specifically,\n\n  - Some documents are frequently retrieved, while others are rarely reused. So it is more storage-efficient to store only the cache of documents with high hit rates. Here, strategies like Least Recently Used (LRU) or Least Frequently Used (LFU) can be applied.\n\n  - It is helpful to offload less-used caches to cheaper storage tiers and reserve fast memory for the most important ones. In practice, we can set up a hierarchical cache across different hardware: keep the most-used KV caches in GPU VRAM (for fastest reuse), move moderately-used caches to CPU RAM, and store rarely-used caches on SSD or disk.\n\n- **On-the-fly KV computation.** Instead of precomputing caches for all documents offline in advance, we can compute the cache for a document only when it is retrieved. This way, only documents that have been retrieved before are cached, which avoids overhead from managing rarely used documents. This strategy can also be combined with the tier-based caching system above as an engineering solution when deploying the RAG system.\n\nWe also want to highlight that the benefit of KVLink is to save GPU cost by serving more requests with the same GPU hours, and GPU cost is usually much higher than the storage cost of the cache.\n\n**Q3:** **Is there any degradation in model performance for tasks that require strong cross-document reasoning?**\n\n**A3:** Many of our experiment tasks already require strong cross-document reasoning. In particular, 2WikiMultiHopQA, HotpotQA, MuSiQue, and TriviaQA all require the model to combine knowledge from multiple documents to produce the correct answer. Although the absolute accuracy on MuSiQue is lower because it is a harder task, we observed that for all of these tasks, our KVLink method gives a consistent performance improvement over all the baseline methods."}, {"review_id": "DEZTf3nobD", "reviewer": "Reviewer_94Ka", "summary": "In RAG, data is retrieved then processed by the network during prefil. This work extends something like prefil cache-ing to the RAG system as a whole, where instead of retrieving text data, network KV cache is retrieved (note given retrieved docs can have different ordering, a special attention mask must be used in training).\n\nThis paper introduces a method already introduced in https://arxiv.org/abs/2410.07590. (they even intro special tokens to act as what this work calls \"links\").\nIts a really good idea; just already exists. Not novel :(", "questions": "please cite: https://arxiv.org/abs/2410.07590\nPLEASE rewrite your paper comparing to TurboRAG and resubmit. please please please. I would 100% accept if it was redone that way.\n\nwhat is the size of your vector store vs the baseline where just text is stored (storing text much cheaper than storing kv-caches)", "limitations": "not novel\nkv-caches are larger than text. this will blow up the size of your vector store.\n\nI'd also be good to talk about storage vs compute economics and cache coherence", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 1, "strengths_and_weaknesses": "Strengths:\n- really good idea\n- The potential efficiency gains are f-in cracked (i'm like 80% sure the big labs do a version of this; the big labs already to disag prefil-decode; might as well stick a cache in-between the prefil and decode GPUs...)\n\nWeaknesses:\n- Not novel; missing tubrorag as related work\n- Scalability and Practical Deployment Issues\n  - Missing analysis of storage overhead costs vs. computational savings trade-offs\n    - KV caches are massive compared to text\n  - No analysis of cache management strategies for large document collections\n  - No cost analysis of storage infrastructure requirements\n- I'm not you test performance vs long context well (ie number of retrieved docs vs performance)", "was_revised": true, "final_justification": "They're including discussions on how their work improves over TurboRAG.", "rebuttal": "We sincerely thank Reviewer 94Ka for the valuable recognition of our work and insightful questions. Your comments have been a great help in improving and improving our work. Below is a detailed response to the key points you raised.\n\n**Q1:** **Missing TurboRAG as related work.**\n\n**A1:** Thank you for pointing out this important work. We will include the discussion of TurboRAG in our experiments and related work section in the final manuscript. We would like to compare our method with TurboRAG as below.\n\n- First, we want to clarify that our key contribution, the link token mechanism, is different from TurboRAG. Instead, TurboRAG is very similar to our baseline, BlockAttention, where the reused caches are directly concatenated. More specifically,\n\n  - TurboRAG introduces two extra tokens: prepending doc_start to the document and appending doc_end to the document. Similar to BlockAttention, TurboRAG computes and stores the KV cache of the document and the two tokens with local self-attention. That means the two tokens are precomputed offline as part of the document and only maintain local attention within the document to mark the document boundaries.\n\n  - Therefore, these two tokens are mainly used to indicate the boundaries of documents. In contrast, our method introduces link tokens and recomputes their KV cache at testing time to reconnect the separately encoded documents.\n\n  - During the training phase, we also introduce the link tokens and train them with the objective of connecting the separately computed contexts, which brings better performance compared to TurboRAG and BlockAttention.\n\n- Second, we also conduct experiments to empirically compare our method to TurboRAG. We replicate TurboRAG and train it using the same training data and training setup as our method. Below is the result:\n\n| Task            | NQ   | 2WikiMQA | TriviaQA | HotpotQA | Musique | avg. |\n| --------------- | ---- | -------- | -------- | -------- | ------- | ---- |\n| **Llama3.2-1B** |      |          |          |          |         |      |\n| KVLink5         | 45.0 | 66.0     | 66.3     | 55.6     | 19.2    | 50.4 |\n| TurboRAG        | 43.4 | 65.5     | 64.8     | 51.8     | 15.2    | 48.1 |\n| **Llama3.2-3B** |      |          |          |          |         |      |\n| KVLink5         | 64.4 | 71.2     | 73.7     | 69.5     | 35.8    | 62.9 |\n| TurboRAG        | 62.9 | 69.5     | 72.9     | 65.6     | 31.4    | 60.5 |\n\nWe observe a consistent performance improvement of KVLink over all tasks, which shows the importance of our link tokens in restoring cross attention.\n\n**Q2:** **Scalability issue of storing pre-computed KV cache.**\n\n**A2:** We appreciate your thoughtful feedback. We agree that storing KV caches comes with a higher cost than storing the original text. Below, we discuss the trade-off between storage and efficiency and how it can be managed.\n\n- First, combining KVLink with existing KV cache compression methods helps reduce storage usage. Our paper presents two such approaches, demonstrating that a well-designed compression strategy causes minimal performance loss. Ongoing improvements in compression can further reduce the storage demand.\n\n- Second, GPU usage cost is typically higher than storage cost. As shown in our experiments, when running a Llama3.1-8B model on an A100 80GB GPU, KVLink can cut latency by 96% for a 5000-token input. Under fixed GPU hours, this allows KVLink to handle 25 times more requests than standard decoding. For every million of these requests, KVLink takes 9 GPU hours (16 USD), while standard decoding uses 246 GPU hours (440 USD), based on the current rate (1.79 USD/hour for A100 80GB). On the other hand, storage remains inexpensive. For example, Amazon S3’s standard plan charges just 0.023 USD per GB each month.\n\n- Finally, we can lower storage cost through system-level solutions. Two design strategies can be used:\n\n  - Cache only high-hit-rate documents. Strategies like LRU or LFU can help identify which documents to keep in cache. Others can be stored in plain text as usual.\n\n  - We can use tiered KV cache storage to further save storage cost. For example, although a 1,000-token document stored as UTF-8 text occupies about 5KB, whereas its Llama3-8B KV cache requires roughly 131MB. We can put this cache in cheaper storage if it is seldom used. In general, low-access caches should be saved on cheaper storage like SSDs, while important ones stay in faster memory like CPU RAM.\n\nIn conclusion, our paper focuses on accelerating LLM inference. We leave the challenge of designing an optimal system that balances performance and storage for future work.\n\n**Q3:** **The performance of the proposed method with different numbers of retrieved documents.**\n\n**A3:** We agree that it is crucial to test the generalizability of KVLink under different numbers of retrieved documents. To address your concern, we evaluate the performance of our method and the best baseline, BlockAttention, on the NaturalQuestions benchmark by varying the number of retrieved documents. The experiment results are as below.\n\n| Num of Docs     | 3    | 4    | 5    | 6    | 7    | 8    | 9    | avg. |\n| --------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |\n| **Llama3.2-1B** |      |      |      |      |      |      |      |      |\n| KVLink5         | 65.6 | 62.0 | 60.8 | 54.0 | 51.4 | 49.6 | 46.4 | 55.7 |\n| BlockAttention  | 58.8 | 60.6 | 56.8 | 44.0 | 43.8 | 39.4 | 37.0 | 48.6 |\n| **Llama3.2-3B** |      |      |      |      |      |      |      |      |\n| KVLink5         | 80.0 | 74.6 | 72.6 | 72.6 | 70.2 | 68.2 | 66.8 | 72.1 |\n| BlockAttention  | 73.8 | 75.4 | 74.0 | 69.2 | 64.0 | 64.0 | 60.8 | 68.7 |\n\nHere we can observe that for almost all the numbers of retrieved documents, the KVLink model outperforms the BlockAttention model with up to 10% performance gain. This result indicates that KVLink can generalize to different numbers of retrieved documents. We will add this experiment in our final manuscript."}, {"review_id": "maRQPnLCQa", "reviewer": "Reviewer_vcib", "summary": "The paper proposes a method called KVLink to reuse precomputed KV caches in order to alleviate the burden of recomputing the KV cache for each retrieved document. Since simple KV cache concatenation leads to significant performance degradation, the authors propose trainable “link” tokens that can aggregate information and reconstruct the interconnection between documents. These link tokens attend to both other link tokens and to their assigned documents. From an implementation perspective, pre-RoPE is employed so that the positional indices of the KV cache can be adjusted properly. Compared to existing cache-reuse methods, the proposed approach achieves superior QA performance and summarization accuracy. Furthermore, KVLink demonstrates a significant speedup in time-to-first-token (TTFT).", "questions": "* During training, “link” tokens take positional indices between documents; is this policy maintained at inference time, too? In other words, do link tokens possess non-consecutive positional indices in the implementation?\n* In TTFT experiments (Section 3.3), on which model and GPU were the experiments conducted, and how does TTFT vary with model size?\n* In Table 1, it would be helpful to indicate which methods require fine-tuning (BlockAttention, KVLink) and which do not, for clarity.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths** \n\n* The concept of using link tokens is clear. It seems that parallelism can be maintained at inference time simply by adjusting the attention map properly.\n* Experiments are well-designed and detailed. The authors put an effort into fair comparisons with related work (Sections A.3, A.4). The paper evaluates KVLink across multiple tasks, including summarization. Analyses also include the GPU loading time of the KV cache in the TTFT measurements.\n\n**Weaknesses**\n\n* The most significant issue, which the authors also discuss, is that storing the entire KV cache demands an overwhelmingly large storage footprint. Even with speed gains, the jump from 5 KB to 131 MB (lines 157–158) is not practical. Although methods such as AnLLM have been explored, the manuscript does not specify how much space is saved versus how much performance is lost. In my opinion, even 5KB to 1MB is too much.\n* While extending into the domain of RAG and KV compression is meaningful, the methodology appears similar to AnLMM. KVLink seems to expand from chunk-level to document-level granularity. The manuscript should discuss these differences in detail or provide specific improvements focused on the application (e.g., RAG).\n* The on-the-fly adjustment of RoPE positions is already well known as “pre-RoPE”, in KV cache compression and quantization papers. In this perspective, the novelty of position re-embedding (rotation) is somewhat weak.", "was_revised": true, "final_justification": "Most of my concerns have been addressed. Based on the discussions and other reviews, it seems that this work has clear advantages, novel points, and potential practical issues. I wish the revised version to include a discussion about pre-RoPE, practical limitations, and approaches to mitigate such challenges.", "rebuttal": "We sincerely thank Reviewer vcib for the valuable recognition of our work and insightful questions. Your comments have been a great help in improving and improving our work. Below is a detailed response to the key points you raised.\n\n**Q1:** **Storing the entire KV cache demands an overwhelmingly large storage footprint.**\n\n**A1:** Thank you for highlighting this important concern. We acknowledge that KV cache storage is more expensive than storing plain text. Below, we address this trade-off between storage and efficiency, along with possible ways to reduce the cost.\n\n- First, storage overhead can be minimized by combining KVLink with existing KV cache compression methods. In our paper, we study two such strategies and show that with proper compression design, the performance drop is minimal. These compression methods can be further refined to lower the storage burden.\n\n- Second, the cost of GPU usage outweighs that of storage. In our experiments, serving a Llama3.1-8B model on an A100 80GB GPU, using KVLink for prefilling a 5000-token context reduces latency by around 96%. This means that for such requests, KVLink enables 25 times more requests to be served using the same GPU time compared to standard decoding. For one million such requests, KVLink requires roughly 9 GPU hours (costing 16 USD), while standard decoding needs about 246 GPU hours (440 USD), based on the current price (1.79 USD/hour for A100 80GB). Meanwhile, storage costs remain low. For instance, Amazon S3 standard tier charges about 0.023 USD per GB per month.\n\n- Lastly, storage can be further optimized at the system level. Two strategies are applicable:\n\n  \n\n  - Store KV cache only for documents with high access frequency. Techniques like Least Recently Used (LRU) or Least Frequently Used (LFU) can help choose which documents to cache. Infrequently used documents can be stored as plain text.\n\n    \n\n  - Use a hierarchical storage system for KV cache. Caches accessed less often can be offloaded to lower-cost storage like SSDs, while high-priority caches can be kept in fast memory such as CPU RAM.\n\n    \n\nIn a nutshell, this work focuses on improving LLM inference speed. Designing a complete system to optimize the efficiency–storage trade-off is an important direction for our future work.\n\n**Q2:** **While extending into the domain of RAG and KV compression is meaningful, the methodology appears similar to AnLLM.**\n\n**A2:** Thank you for the question. Here we want to highlight the differences between our compression method and the AnLLM method from three dimensions:\n\n- We include the KV compression technique to help reduce the storage overhead of pre-computed KV cache. To this extent, we explore different strategies to compress the KV cache, including prompt compression [1], our method, and AnLLM. However, we empirically found that AnLLM does not give good performance after compression. Please find the experiment results below using AnLLM for compression. The AnLLM model here is first trained with the pre-training data as described in the AnLLM paper, and then supervised fine-tuned using QA tasks for 2 epochs, the same as our method.\n\n| Task              | NQ   | 2WikiMQA | TriviaQA | HotpotQA | Musique |\n| ----------------- | ---- | -------- | -------- | -------- | ------- |\n| AnLLM (5 anchors) | 31.3 | 36.1     | 52.6     | 20.9     | 2.6     |\n| Our method (50%)  | 43.0 | 69.9     | 69.3     | 55.4     | 17.3    |\n| Our method (75%)  | 40.9 | 69.4     | 68.2     | 52.4     | 14.8    |\n\nThe sub-optimal performance of AnLLM motivates us to make a few modifications to it. We acknowledge that our method is directly built upon AnLLM with slight changes to improve performance. We also mention this in the main paper (lines 160–164).\n\n- Second, the main difference between our revised compression method and the original AnLLM is the attention mechanism. In AnLLM, the compressed tokens (i.e., the anchor tokens) in the previous chunk can be attended by the following raw tokens and anchor tokens. However, in our method, to follow the cache reuse setting where each chunk is encoded separately, the compressed tokens can only be attended by the link tokens and query tokens, which follow the standard self-attention. We empirically find this attention mechanism more suitable for our application setting.\n\n- Third, as you have mentioned, the intended use cases of the two methods are also different. AnLLM focuses on dynamically dropping the generated tokens with compression during the decoding phase for long context tasks, instead of pre-computing and compressing the KV cache for reuse. In contrast, our method compresses the document in the context into a reusable KV cache for efficient prefilling.\n\n[1] Pan, Zhuoshi, et al. \"LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression.\" ACL (Findings). 2024.\n\n**Q3:** **The on-the-fly adjustment of RoPE positions is well known as “pre-RoPE”, in KV cache compression and quantization papers.**\n\n**A3:** Thank you for pointing this out. We acknowledge there are multiple ways of restoring the cache position information, and we want to highlight that our key contribution in this paper is proposing the link tokens for restoring the cross attention between the reused context. As discussed in the related work section, current KV reuse works also handle the position information using similar methods. For example, BlockAttention removes the position information inside the caches by rotating the key cache with a negative angle. Nevertheless, we will definitely discuss and credit the pre-RoPE techniques in our final manuscript.\n\n**Q4:** **During training, “link” tokens take positional indices between documents; is this policy maintained at inference time, too? In other words, do link tokens possess non-consecutive positional indices in the implementation?**\n\n**A4:** The use of “link” tokens is the same for both training and inference time, where the positional indices of the “link” tokens are consecutive, ranging from the position of the last token in the preceding document to the position of the first token in the next following document.\n\n**Q5:** **In TTFT experiments (Section 3.3), on which model and GPU were the experiments conducted, and how does TTFT vary with model size?**\n\n**A5:** In TTFT experiments, the Llama3.1-8B-instruct model is used with an A100 80GB GPU. As the model size increases, the reduction in TTFT latency will also increase given the same length of context and same device. This is because larger models take more time to prefill the contexts, whereas loading a larger KV to GPU memory adds only a small extra time cost. We will include this information in our final manuscript.\n\n**Q6:** **In Table 1, it would be helpful to indicate which methods require fine-tuning (BlockAttention, KVLink) and which do not, for clarity.**\n\n**A6:** Thank you for pointing this out. We will include this information in Table 1 in our final manuscript. Specifically, for the KV reuse methods, BlockAttention and KVLink require training, while PromptCache and CacheBlend are training-free methods."}, {"review_id": "7StioKO4N9", "reviewer": "Reviewer_5Ajo", "summary": "This paper introduces KVLink, an approach designed to reusing KV caches across docs. The problem KVLink aims to solve is due to inherent inefficiency in many LLM applications, particularly those involving RAG, where different inputs often share overlapping context. Standard LLM inference requires re-encoding the entire concatenated context for each query, leading to redundant computations.\nKVLINK addresses this by precomputing the KV cache of each doc segment independently. During inference, these precomputed KV caches are concatenated, allowing the model to reuse cached representations instead of recomputing them. To counteract the performance degradation  that typically arises from independently computed KV caches. KVLink introduces positional re-encoding and trainable cross-segment link tokens.\nThe experiments validated KVLINK's effectiveness across seven datasets. Using 5 link tokens, it improved QA accuracy by 4%. Additionally, it significantly reduced TTFT", "questions": "Questions have been proposed in weakness.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength\n1. The problem of redundant computation due to repeated encoding of shared contexts in LLMs is a genuinely interesting and critical challenge. \n2. This paper introduces the KVLINK approach with positional re-encoding and trainable link tokens tackle the KV cache reuse in multi docs scenarios. The trainable link tokens are an elegant solution for restoring cross-document attention.\n3. The experiments demonstrate the effectiveness of KVLINK across diverse datasets and model scales (Llama-3.2-1B, Llama-3.2-3B, and Llama-3.1-8B). While link tokens provided improvement in smaller models.\n\n### Weakness\nOverall, this paper addresses the recomputation problem by introducing link tokens to capture relationships between documents to some extent. However, it still has the following weaknesses:\n1. Storing documents as KV Cache remains too costly at present.\n2. Based on the results shown in the paper, most of the experimental improvements are observed in 1B and 3B models, with only marginal gains for the 8B model. Can larger models (30B/70B) be evaluated to demonstrate the general applicability of link tokens?\n3. In the experiments presented in the paper, many experimental designs for certain task types, such as the NQ task, do not fully demonstrate the effectiveness of link tokens.", "was_revised": true, "final_justification": "4:  Borderline accept\n\nRemain unresolved:  The impact of link tokens on large models (More than 7B) appears to be limited.\n\nSolved: Clarify the applicable scenarios of KVLink, and adopt a hierarchical memory design to store the KV cache in RAG systems.", "rebuttal": "We sincerely thank Reviewer 5Ajo for the valuable recognition of our work and insightful questions. Your comments have been a great help in improving and improving our work. Below is a detailed response to the key points you raised.\n\n**Q1:** **Storing documents as KV Cache remains too costly at present.**\n\n**A1:** Thank you for raising this important point. We agree that storing the KV cache is more costly than storing the text. We would like to discuss this trade-off between storage overhead and efficiency, as well as the strategies to reduce the cost, as outlined below.\n\n- First, we can reduce storage overhead by combining KVLink with existing KV cache compression techniques. In our paper, we explore two different strategies and show that the performance loss is minimal with a well-designed compression scheme. We believe the compression method can be further improved to reduce the storage cost.\n- Second, GPU cost is more significant than storage cost. As shown in our experiment, serving a Llama3.1-8B model on one A100 80GB GPU, prefilling a 5000-token context with KVLink can reduce latency by about 96%. Therefore, for requests of this length, KVLink can serve 25 times more requests than standard decoding using the same amount of GPU time. For one million such requests, KVLink uses about 9 GPU hours for prefilling, which costs around 16 USD, while standard decoding takes about 246 GPU hours, costing around 440 USD (based on the current market price of ~1.79 USD/hour for an A100 80GB GPU). Meanwhile, storage is much cheaper than GPU resources. For example, on cloud storage like Amazon S3 standard tier, storing 1 GB per month costs about 0.023 USD.\n\n- Finally, we can reduce storage cost through system-level design. Specifically, two strategies can be used:\n\n  - Store the KV cache only for documents with high hit rates. Strategies like Least Recently Used (LRU) or Least Frequently Used (LFU) can help decide which documents to keep in KV cache. For less frequently used documents, we can store them as plain text.\n\n  - Use hierarchical KV cache storage. Less frequently accessed caches can be stored on cheaper storage (e.g., SSD), while more critical ones can be kept in faster memory (e.g., CPU RAM).\n\n    \n\nIn summary, our work focuses on speeding up LLM inference. We leave the full system design that balances efficiency and storage cost as future work.\n\n**Q2:** **Based on the results shown in the paper, most of the experimental improvements are observed in 1B and 3B models, with only marginal gains for the 8B model. Can larger models (30B/70B) be evaluated to demonstrate the general applicability of link tokens?**\n\n**A2:** Thank you for the question. Firstly, we observed that when using the larger models, it is harder to achieve further performance improvements because these models already have high absolute performance, leaving less room for gains compared to smaller models. We agree that it is important to show that the improvements hold across different model sizes. To address the concern, we have trained the KVLink5 model and our strongest baseline, BlockAttention, using Qwen-2.5-32B-instruct as the base model. The result is given below.\n\n| Task           | NQ   | 2WikiMQA | HotpotQA | TriviaQA | Musique |\n| -------------- | ---- | -------- | -------- | -------- | ------- |\n| BlockAttention | 71.7 | 94.2     | 75.3     | 84.6     | 45.3    |\n| KVLink5        | 74.4 | 95.9     | 76.9     | 84.5     | 46.6    |\n\nWe highlight that our method also outperforms the best baseline, BlockAttention, on the 32B model with a 1.3%–2.7% absolute improvement. The only exception is the TriviaQA dataset. We believe the reason is that the training set of TriviaQA is used to train both methods, so their performance on in-distribution data becomes similar. These improvement numbers are consistent with the results on 1B and 3B models, showing that our method works well across different model sizes.\n\n**Q3:** **In the experiments presented in the paper, many experimental designs for certain task types, such as the NQ task, do not fully demonstrate the effectiveness of link tokens.**\n\n**A3:** The tasks that we tested in the paper for the first experiment are QA and summarization tasks. The three reasons that we are testing these tasks are:\n\n1.  The prefill-heavy nature of these tasks. These tasks usually have much longer context and short model response, which makes them suitable to benefit from KVLink through reusing context cache.\n2. To provide a comprehensive evaluation and comparison, these tasks are all the tasks tested by our baselines.\n3. The multi-hop reasoning QA tasks rely more on cross attention across documents, and QA is a task that has strong demand in real-world applications."}]

Author rebuttal:

Meta-review: The paper presents KVLink, a novel approach for efficient KV cache reuse in large language models, particularly benefiting applications like Retrieval-Augmented Generation. Strengths include substantial efficiency gains, with up to 96% time-to-first-token reduction, and the effective, elegant solution of trainable link tokens for cross-document attention. KVLink also achieves state-of-the-art accuracy on QA tasks and is supported by well-designed experiments across diverse model scales, including evaluation on a 32B model.

Key weaknesses included concerns about the storage overhead of KV caches, initial lack of direct comparison with related methods like TurboRAG and AnLLM, and questions regarding its general applicability to very large models.

The paper is recommended for acceptance due to its significant efficiency improvements and the novel, effective link token mechanism that addresses a critical challenge in LLM inference.

During the rebuttal period, reviewers (534y, 94Ka, vcib, 5Ajo) raised concerns about storage overhead, which authors addressed by proposing compression, hierarchical storage, and emphasizing the higher cost of GPU usage over storage. Missing comparisons with TurboRAG and AnLLM were resolved by authors providing empirical results and clarifying fundamental differences in their link token mechanism. The nature of link tokens was clarified as special tokens recomputed at inference to restore cross-attention, empirically demonstrating their necessity. Authors also provided additional experiments showing consistent performance across varying numbers of documents and on a 32B model. Reviewer 5Ajo, while acknowledging addressed concerns, noted the perceived limited impact on large models in their final comment, though authors did show consistent gains on 32B. These discussions significantly strengthened the paper's claims and justifications.
Decision: Accept (poster)