KVLink: Accelerating Large Language Models via Efficient KV Cache Reuse

1 Introduction

• Conventional LLM inference encodes the entire concatenated context for every query, redundantly re-encoding unchanged documents shared across queries.This raises prefilling costs for long contexts and prevents separately encoded segment representations from being reused.Source: §1 · p. 2
• KVLink precomputes each document’s KV states independently, then reuses and concatenates them at inference to avoid re-encoding shared context.It adjusts cached positional embeddings to match global positions and inserts trainable cross-segment tokens whose KV representations are computed at inference; the tokens attend to preceding tokens to restore self-attention across documents.Source: §1 · p. 2
• KVLink beats the best baseline by 6.6% on Natural Question and 7.3% on HotpotQA [11], while reducing time-to-first-token latency by up to 96% versus full encoding.Against the conventional full-encoding model, KVLink sacrifices only minimal performance; evaluations cover Llama-3.2-1B, Llama-3.2-3B, and Llama-3.1-8B.Source: §1 · p. 2
• KVLink combined with KV cache compression methods LLMLINGUA [12] and ANLLMS [13] consistently outperforms baseline approaches.The paper examines compression because storing precomputed KV caches can incur substantial storage overhead.Source: §1 · p. 2

2.1 Problem Formulation

• KVLink precomputes context-free KV caches for documents and concatenates retrieved caches for reuse, avoiding redundant encoding but losing cross-document dependencies that can degrade QA accuracy.Prior work reported up to a 35% relative accuracy decrease on question-answering tasks when each retrieved document was cached separately [7].Source: §2.1 · p. 3

2.2 KV Cache Positional Re-encoding

• KVLink stores KV states without RoPE rotations, then applies each token’s global-position rotation after concatenation to correct the mismatch between local and full-sequence positions.RoPE is still applied during segment encoding for local self-attention, but its positional transformations are excluded before saving the caches.Source: §2.2 · p. 3

2.3 Cross-Document Reconnection with Link Tokens

• Trainable link tokens reconnect documents: each attends to its document and preceding documents, while document tokens retain local causal attention; training jointly optimizes the model and tokens.At inference, KVLink concatenates precomputed caches and runs a forward pass only on the appended link tokens using the customized attention map.Source: §2.3 · p. 4

2.4 Compressed KV Cache Linking

• To reduce cache storage and loading overhead, KVLink combines with LLMLINGUA token dropping or chunk-based ANLLMS, whose anchor tokens attend within their chunk and to preceding anchors.The default chunk size is 100; training predicts tokens beyond the input chunks using only anchor tokens, then fine-tunes on QA datasets with KVLink.Source: §2.4 · pp. 4–5

3.1 Experiment Setup

• Experiments evaluate separately cached retrieval QA and summarization, TTFT, general capabilities, and QA with compressed caches.The QA suite includes NaturalQuestions, 2WikiMQA, TriviaQA, HotpotQA, and MuSiQue; summarization uses MultiNews and Samsum. Evaluation also covers reasoning and instruction-following benchmarks and compression rates of 50% and 75%.Source: §3.1 · pp. 5–6

3.2 Main Results

• KVLINK outperforms baselines on evaluation datasets, with up to 5% higher accuracy than BLOCKATTENTION on most QA tasks.The exceptions are 2WikiMQA and TriviaQA, whose training sets were included in the training mixture; on other evaluation datasets, KVLINK outperforms the baselines. It also approaches fine-tuned Llama performance under standard, fully concatenated-context decoding. Performance improves consistently as the number of link tokens increases.Source: Table 1 · p. 6, §3.2 · p. 7

3.3 Inference Efficiency Evaluation

• 85%–96% lower TTFT than standard decoding is achieved by KVLINK1 and KVLINK5, with a 96% reduction at 5,000 tokens.Measurements include loading precomputed caches from CPU to GPU, positional re-encoding, and encoding link tokens; the methods have lower TTFT across context sizes, and the gap widens as context length increases.Source: Figure 3 · p. 7, §3.3 · pp. 7–8

3.4 General Capability Preservation

• KVLINK maintains performance comparable to fine-tuned Llama across general-capability tasks, with drops from original models typically below 3% on affected benchmarks.The reported minor drops include ARC-Challenge and Winogrande; results across both model sizes are described as highly comparable to fine-tuned Llama.Source: §3.4 · p. 8

3.5 KVLINK with Cache Compression

• Adding link tokens consistently mitigates compression-related accuracy drops, while modified ANLLMS retains more information and outperforms LLMLINGUA across QA benchmarks.The comparison evaluates KVLINK with five link tokens against BLOCKATTENTION at 50% and 75% compression rates.Source: §3.5 · pp. 8–9, Table 3 · p. 9

3.6 Ablation Study

• KVLINK remains competitive across different training data mixtures, while task combinations and domain coverage can slightly affect downstream performance.The paper identifies balanced data selection as important and leaves comprehensive exploration of optimal data configurations for future work.Source: §3.6 · p. 9

Efficient inference for LLMs

• KVLink aims to reduce inference-time computation like pruning [35] [36] [37] [38], quantization [40] [41] [42] [43], and optimized decoding, and can combine cache reuse with eviction and KV-cache quantization for memory efficiency.The cited cache-memory approaches reduce footprint through eviction [56] [57] [58] or quantization [59] [42] [41] [60] [61] [62].Source: §4 · p. 9

KV cache reuse

• KV-cache reuse across queries often focuses on prefixes [51] [52]; PROMPTCACHE[9] supports discontinuous positions but ignores cross-chunk attention and requires Prompt Markup Language.The paper says these limitations reduce performance and flexibility across tasks.Source: §4 · p. 9
• CACHEBLEND selectively recomputes tokens with the largest value-state variance, but recomputing 10%–20% of tokens plus all first-layer tokens carries non-trivial cost.The passage also reports performance degradation.Source: §4 · p. 9
• BLOCKATTENTION[7] re-encodes caches without positional embeddings but lacks strategies to connect reused contexts; TurboRAG [54] adds two boundary tokens yet also reconnects caches ineffectively.The passage characterizes BLOCKATTENTION's performance as below ideal and says TurboRAG falls short similarly.Source: §4 · p. 9

Retrieve-augmented generation

• RAG commonly retrieves documents with dense retrievers or BM25 [22] [63], then concatenates text or integrates knowledge through cache-based LongMem [66] and noisy-context fine-tuning with RAFT [69].The passage also notes work on improving RAG with LLMs [67] [68].Source: §4 · pp. 9–10

5 Conclusion

• Precomputed KV caches for retrieved documents or context segments let the method avoid redundant computation across queries with overlapping contexts.The paper identifies refining the data mixture, optimizing fine-tuning, and exploring real-world deployment as future work; limitations and societal impact are discussed in the Appendix.Source: §5 · p. 10

• The checklist answers “Yes,” stating that KVLINK addresses performance degradation in cache reuse to accelerate LLM inference and that Section 3’s experiments verify the abstract and introduction’s claims.Source: NeurIPS Paper Checklist · p. 16

Limitations

• The paper reports that its limitations are discussed in Appendix A.9, but the supplied passages do not specify what those limitations are.The passage confirms the discussion exists without describing its content.Source: §2 · p. 16
• The paper has no theoretical results, so theoretical assumptions and proofs are not applicable.The paper’s checklist answer states that it does not include theoretical results.Source: §2 · p. 17
• The paper says reproduction details are in Section 3.1 and Appendix A.2, and that code, datasets, and KVLINK models will be released.Training and test details are also reported in those sections.Source: §2 · pp. 17–18
• Error bars are not reported because training is empirically stable and evaluation uses greedy decoding.The supplied passage gives these as the reasons for omitting error bars.Source: §2 · p. 18

A.1 Data Mixture

• TriviaQA and 2WikiMQA questions are paired with ten separately encoded Wikipedia passages retrieved using Contriever, with GPT-4-generated reference answers as supervision.The passages are retrieved for each question.Source: §A.1 · p. 23
• Earlier turns in instruction-following conversations are randomly converted into independently encoded KV caches, and the model learns to answer subsequent turns using those contexts.This setup is intended to teach integration of segmented contexts while maintaining instruction-following capability.Source: §A.1 · p. 23
• For XSum summarization, each document is split into consecutive segments encoded as separate KV caches, and the model is trained to generate the ground-truth summary.The task trains the model to aggregate information across independently encoded document chunks.Source: §A.1 · p. 23
• Standard TriviaQA and 2WikiMQA examples use whole, concatenated retrieved contexts to train generation of ground-truth answers and preserve existing QA capabilities.Source: §A.1 · p. 23
• Tulu 3 examples are included to preserve instruction-following ability, while a small amount of Fineweb pretraining data is included to preserve language-modeling capability.Source: §A.1 · p. 23
• Conversation training loss is computed only on the assistant’s final response; summarization uses 100-token segments, and all examples are truncated to 4096 tokens.Table 4 provides an overview of the training data.Source: §A.1 · p. 23

• Fine-tuning uses a mixed dataset from different sources to integrate disjoint context segments while preserving the LLM’s original capabilities.Source: §A.2 · p. 23
• Training uses randomly selected, GPT-4-generated system prompts tailored to SFT, QA, and summarization, and shuffles retrieved documents in QA data.Source: §A.2 · p. 23, Figure 5 · p. 24
• Reused contexts are marked with KV-START and KV-END, and each document’s link tokens depend on its index, following linkn-1 through linkn-K.For the n-th reused document, the tokens are linkn-1, linkn-2, ..., linkn-K when K link tokens are used.Source: §A.2 · pp. 23, 25
• QA accuracy counts a prediction as correct when any prediction substring exactly matches any gold answer, following [7] [21] [73] [74].Source: §A.2 · p. 25
• General capability preservation is evaluated with LM Evaluation Harness, using 8-shot GSM8K and 5-shot MMLU.Source: §A.2 · p. 25

A.3 More Implementation Details of Baselines

• BLOCKATTENTION separately encodes reused documents or segments and concatenates their caches without special tokens; data without reuse is processed as in KVLink.For PROMPTCACHE, the original implementation does not adjust position encodings, but evaluation gives reused contexts gold position information to maximize performance.Source: §A.3 · p. 25

A.4 Ablation Studies on Data Mixure

• Under KVLINK5, ablations indicate that cross-chunk reasoning tasks are essential for robust cache reuse and multiple cache-reuse data types improve generalization.The study compares No Summarization, No Multi-turn Conversation, and QA Only; the best training-data recipe for general cache reuse remains an open question.Source: §A.4 · p. 25

A.5 Impact of Answer Document Position

• Accuracy drops significantly when the correct answer document appears farther back in the context, supporting shuffled retrieved documents during QA training.The authors attribute the risk to relevance-ranked training data placing answer-containing documents near the front, which can teach the model to look there rather than reason across the context.Source: §A.5 · p. 25, Figure 6 · p. 26

A.6 Training of Modified ANLLM Compression

• Modified ANLLM compression is trained in continuous pre-training and QA-tuning stages.During pre-training, the former half is divided into 100-token segments; compression tokens attend to preceding compression tokens and original tokens in their segment, while latter-half tokens attend only to compression tokens. QA tuning adapts compression tokens for document compression and QA, with each document’s compression tokens unable to attend to one another.Source: §A.6 · pp. 25–27, Figure 7 · p. 26

A.7 Storage Demand of KV Cache Reuse

• KVLink can reduce storage use by combining with existing KV-cache compression methods, which the authors say can incur minimal performance loss when well designed.They also note that continued improvements in compression could further reduce storage demand.Source: §A.7 · p. 27
• For a 5,000-token input, KVLink cuts latency by 96% on an A100 80GB GPU.Under fixed GPU hours, it handles 25 times more requests than standard decoding; per million requests, it uses 9 GPU hours (16 USD) versus 246 GPU hours (440 USD).Source: §A.7 · p. 27
• Storage costs can be managed by caching high-hit-rate documents and placing infrequently accessed KV caches in cheaper storage such as SSDs.LRU or LFU can help select documents to cache, while frequently accessed caches can remain in faster CPU RAM.Source: §A.7 · p. 27

A.8 Comparison with TurboRAG

• Unlike TurboRAG’s offline, document-local boundary tokens, KVLink recomputes link-token caches at test time and trains them to reconnect separately encoded contexts.The authors report comparing the methods using replicated TurboRAG trained with the same data and setup, but the supplied passages do not state the Table 6 results.Source: §A.8 · p. 27, Table 6 · p. 27

A.9 Limitations

• KVLink still loses some performance after cache compression, and variable cache sizes complicate storage in vector databases.The authors identify larger-scale training and efficient organization of precomputed caches as possible ways to address these limitations.Source: §A.9 · p. 28

A.10 Societal Impact; A.11 License; A.12 LLM Usage

• The authors report using GPT-4 for proofreading, using datasets and software for their intended purposes, and finding no personal identifying or offensive content in their materials.They state that the training and evaluation data contain no private or sensitive information and that KV-cache reuse introduces no additional risks or bias; dataset licenses are listed across the materials.Source: §A.10 · p. 28, §A.11 · p. 28, §A.12 · p. 28