EPIC: Efficient Position-Independent Caching for Serving Large Language Models
Authors: Junhao Hu
Wenrui Huang
Weidong Wang
Haoyi Wang
tiancheng hu
zhang qin
Hao Feng
Xusheng Chen
Yizhou Shan
Tao Xie
Venue: ICML 2025 poster (2025)
Keywords: Machine Learning System
Context Caching
KV Cache
Sparsity
Primary area: deep_learning->attention_mechanisms

Abstract: Large Language Models (LLMs) show great capabilities in a wide range of applications, but serving them efficiently becomes increasingly challenging as requests (prompts) become more complex. Context caching improves serving performance by reusing Key-Value (KV) vectors, the intermediate representations of tokens that are repeated across requests. However, existing context caching requires exact prefix matches across requests, limiting reuse cases in settings such as few-shot learning and retrieval-augmented generation, where immutable content (e.g., documents) remains unchanged across requests but is preceded by varying prefixes. Position-Independent
Caching (PIC) addresses this issue by enabling modular reuse of the KV vectors regardless of prefixes. We formalize PIC and advance prior work by introducing EPIC, a serving system incorporating our new LegoLink algorithm, which mitigates the inappropriate “attention sink” effect at every document beginning, to maintain accuracy with minimal computation. Experiments show that EPIC achieves up to 8× improvements in Time-To-First-Token (TTFT) and 7× throughput gains over existing systems, with negligible or no accuracy loss.

EPIC: Efficient Position-Independent Caching for Serving Large Language Models
Junhao Hut
Wenrui Huang?
Weidong Wang?
Haoyi Wang's
Tiancheng Hu² Tao Xie
Qin Zhang?
Hao Feng?
Xusheng Chen
Yizhou Shan
Abstract
Static Sparsity
Liama Instruct
Naive
FR
0.25
Large Language Models (LLMs) show great capa- bilities in a wide range of applications, but serv- ing them efficiently becomes increasingly chal- lenging requests (prompts) become more com- plex. Context caching improves serving perfor- mance by reusing Key- Value (KV) vectors, the intermediate representations of tokens that are re- peated across requests. However, existing context caching requires exact prefix matches across re- quests, limiting reuse cases in settings such as few-shot learning and retrieval-augmented gener- ation, where immutable content (e.g., documents) remains unchanged across requests but is pre- ceded by varying prefixes. Position-Indeeendent Caching (PIC) addresses this issue by enabling modular reuse of the KV vectors regardless of pre- fixes. We formalize PIC and advance prior work by introducing EPIC, a serving system incorporat- ing our new LegoLink algorithm, which mitigates the inappropriate "attention sink" effect at every document beginning, to maintain accuracy with minimal computation. Experiments show that EPIC achieves up to 8x improvements in Time- To-First- Token (TTFT) and 7x throughput gains over existing systems, with negligible or no accu- racy loss.
Recomputaiinn
HotpotOA
0.15
Cachutlere
Nake
legel ivee
CachsBland
Logetare-3
0.05
CacheBlend
Cachefloond
0.00
Dynamic Sparsity
TTFT
Figure I. Left: Design space of iesiiionindeeeedeent context caching. Right: The x-axis shows the computation overhead or TIFT, while y-axis shows accuracy. Different shades of the same color indicate variants of the same algorithm.
chatbots, education, and medicine (Zhou et al., 2024). Users interact with LLMs by submitting requests, or prompts that consist of text-like tokens. As LLMs' capabilities continue to grow, their usage has shifted from simple dialogues to more complex tasks, such as multi-document question swering, few-shot learning, and tool use. These tasks typi- cally involve long prompts comprising relatively immutable token chunks (compared to mutable user instructions) such as system messages, few-shot examples, and documents. Notably, such immutable chunks are frequently repeated across requests.
Context Caching' (CC) is emerging approach that reuses Key-Value (KV) vectors, the intermediate representations of repeated tokens in previous requests to reduce computation, and is generally categorized into two types. First, prefix- based CC matches current request against previous ones to reuse the KV vectors of the longest common prefix. Al- though prefix-based CC remains the dominant approach in existing systems (kim; gem, b; Zheng et al., 2024; Kwon et al., 2023), it requires exact prefix matches across requests, limiting reuse cases in settings such as few-shot learning and Retrieval-Augmented Generation (RAG), where immutable chunks (e.g.. documents) remain unchanged across requests but are preceded by varying prefixes. Second, Position- Independent Caching (PIC) (Figure (b)) extends prefix-
1. Introduction
Large Language Models (LLMs) are fundamental to various emerging applications such question answering,
Thhis work completed during his internship Huawei Cloud. 'sCS, Peking University; Key Lab HCST (PKU), MOE, China 'School of Computer Science, Nanjing University, Nanjing, China HHaaei Cloud, Shanghai, China Key Lab of HCST (PKU), MOE; SCS, Peking University. China. Correspon- dence Tao Xie <taoxie @ pku.edu.en>>, Yizhou Shan <shany- izhou huawei.com>.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Also referred to as prompt caching.

---

EPIC: Efficient Position-Independed Caching for Serving Large Language Models
based CC, enabling modular reuse of the KV vectors of immutable tokens, regardless of their prefixes (Yao al., 2025). Although PIC significantly increases reuse opportu- nities (Figure 6), it deviates from standard attention mech- anisms, resulting in potential accuracy degradation; thus, ensuring accurate recovery becomes its main challenge.
EPIC against the state-of-the-art CacheBlend (Yao al., 2025) system, across six tasks with distinct characteris- tics and three model architectures with diverse training recipes. Compared to CacheBlend, EPIC achieves up to a 3x improvement in TTFT with accuracy losses limited to within 7% (Figure 1) when serving single requests. Fur- thermore, EPIC provides up to an 8x reduction in TTFT and 7x increase in throughput when serving multiple requests under varying rates. The code is available at: individual immutable chunks to the LLM to generate and store their respective KV vectors. Second, the link step re- trieves and concatenates cached KV vectors and recomputes a subset of KV vectors to maintain accuracy.
To tackle the challenge of PIC, we formalize its usage within two-step framework analogous to compilation and link- ing (Figure 2). First, the compile step involves submitting
In summary, this paper makes three major contributions:
We formalize the PIC usage into a two-step framework, within which we consolidate existing literature and highlight potential directions for future research.
To the best of our knowledge, CacheBlend (Yao al., 2025) the first work that fits into our PIC framework (Figure 1), and has two major limitations. First, the time and resource complexity of the recomputation in the link step are the same as the original attention mechanism-O(A3)) where N is the number of tokens in the given prompt. Figure shows that, although CacheBlend-15 15 dynamically selects 15% of tokens for recomputation, for very long prompts, common in many applications today, this ) complexity remains slow and prone to out-of-memory (OOM) errors (Figure 9). Second, CacheBlend relies on dynamic attention sparsity, which incurs heavy runtime overhead in addition to the O(N2 2 recomputation. Figure 10 shows that the runtime overhead of CacheBlend takes around 16.3% to 63.56% of Time- To- Forss---Tokkn (TTFT).
We provide a detailed analysis of existing algorithms, based on which we propose new LegoLink algorithm, which reduces up to 3x TTFT while keeping accuracy losses limited to within 7%, compared to the state-of- the-art CacheBlend system.
We implement the EPIC serving system by incorporat- ing OpenAl-compatible context caching APIs, a KV store, and LegoLink. EPIC reduces up to 8x TTFT and increases up to 7x throughput when serving multiple requests under varying rates.
To overcome the limitations of CacheBlend, we develop Caching), a serving
2. Background and Motivation
EPIC (Efficient Position-Independee system that incorporates our simple but effective algorithm named LegoLink with two characteristics. First, LegoLink reduces recomputation complexity to O(kN) ~ O(N), where k < N and increases with the number of immutable chunks instead of N. As described in Section 5, & could potentially become zero. Second, LegoLink relies on static attention sparsity, which selects the tokens to recompute beforehand, further improving performance. The static to- ken selection is based on our key insight: the initial tokens of each immutable chunk disproportionately absorb atten- tion, impeding subsequent tokens from attending to relevant context-a phenomenon known as "attention sink" (Xiao et al., 2024). LegoLink recomputes & (k < 32) initial tokens of each chunk (except the first chunk), allowing these tokens to recognize their non-initial positions and crippling their attention-sink ability.
This section provides a primer on transformers, context caching, and its variant, Position-Independent Caching (PIC), along with a review of an existing PIC algorithm.
2.1. Autoregressive Generation and KV Cache
The generation process of Large Language Models (LLMs) consists of two distinct stages: the prefill stage and the decode stage. In the prefill stage, the model processes a sequence of prompt tokens all at once. It computes the Key (K) and Value (V) vectors for all prompt tokens, stores these vectors in the KV cache, and generates the first output token to initiate the decode stage. The time required to gener- ate the first token is referred to as the Time-To-First- (TTFT). The prefill stage is primarily compute-bounde as it involves processing multiple tokens in parallel. In the decode stage, the model iteratively processes each newly generated token. It computes the KV vectors for the new token, appends these vectors to the KV cache, and generates the next token. This process repeats until specified stop- ping criterion is met. Unlike the prefill stage, the decode stage is memory- bound as it computes little compared to the amount of memory access.
We implement the EPIC serving system with the LegoLink algorithm based on one of the most widely used infer- ence frameworks, vLLM (Kwon et al., 2023). We evaluate
Anoohher related approach called PromptCache (Gim et al., 2024) is not of the PIC type.
2

---

EPIC: Efficient Position-Independed Caching for Serving Large Language Models
Source files
Compiler
PIC (Code)
Dynamic-Inked lib
sical position-independent code² that be executed at any memory address (Hu et al., 2023), enables modular reuse of the KV vectors of immutable tokens (Yao al., 2025), regardless of their prefix (Figure 2). PIC significantly in- creases reuse opportunities (Figure 6), but it deviates from standard attention mechanisms, resulting in potential accu- racy degradation; thus, ensuring accurate recovery becomes its main challenge.
D11 D11 D11
101 101 101
D11 101
User source file
Compiler Linker
Execulable
Position-ndependent Code
Immutable tokens
LLM
PIC (Cache)
KV cache
We formalize PIC usage within two-step framework. First, the compile step involves submitting individual immutable chunks to the LLM to generate and store their respective KV vectors. In this step, each chunk is encoded with po- sition IDs starting from zero, and the LLM performs only the prefill stage- aage-ggenaating KV vectors without any pre- fix or further token generation. This process is analogous to compiling C source files into position-indeppndenr re- locatable code. The resulting KV vectors are stored in a cache, conceptually similar to packaging object code into a dynamically linked library. Second, the link step retrieves and concatenates cached KV vectors and recomputes a sub- set of KV vectors to mitigate accuracy degradation due to deviations from the standard attention mechanism. This recomputation involves both cached tokens and uncached tokens, such as user instruction/query tokens, which are computed for the first time*. This process is analogous to linking dynamically linked libraries with source code to produce an executable.
KV
:8:]
Link
Mutable
LLM KVLink
Prefil-stage KV
(b) Position-Independent Cache
Figure 2. An analogy hetween position-independent code and position-independent cache.
2.2. Context Caching
LLMs' usage has shifted from simple dialogues to more complex tasks, such as multi-document question answer- ing, few-shot learning, and tool use. These tasks typically involve long prompts comprising relatively immutable to- ken chunks (compared to mutable user instructions/queries) such as system messages, few-shot examples, and docu- ments. Notably, such immutable chunks are frequently re- peated across requests. Context Caching (CC), also referred to as prompt caching, is an emerging approach that reuses the KV vectors of repeated tokens in previous requests (Hu al., 2024a; Zheng al., 2024; Liu al., 2024; Kwon et al., 2023), speeding up the prefill stage and reducing TTFT. Context caching can be categorized into two types: prefix-based caching and Positional- Positional-Indeeendenn Independent Caching (PIC).
2.3. Existing Algorithms for PIC
CacheBlend (Yao et al., 2025) is the first PIC algorithm focusing on the link step. but two simpler algorithms also deserve attention, although they are too rudimentary to be classified as proper algorithms. First, Naive reuses cached KV vectors directly in the link step, without any recom- putation (Figure 4, first row below the dashed line). This algorithm incurs zero linking overhead but leads to sub- stantial accuracy degradation (Figure 6) due to violations of the attention mechanism-the PIC challenge. Second, Fully Recompute (FR) recomputes all KV vectors in the link step (Figure 4, second row below the dashed line). This algorithm preserves the standard attention mechanism and achieves the highest accuracy, but it eliminates the efficiency benefits of caching, resulting in the highest linking overhead (Figure 6).
Prefix-based caching, implemented in nearly all existing context caching systems (Kwon al., 2023; Zheng al., 2024; Gim et al., 2024), matches the current request against previous
reuse the KV vectors of the longest com- mon prefix. This approach, however, requires exact prefix match, as each token's 's KV vector depends on all preceding tokens and their absolute position IDs in the prompt. Con- sequently, even minor differences in the prefix invalidate the KV vectors of otherwise immutable chunks, requiring full recomputation. This constraint significantly limits reuse opportunities (Ime; Yao et al., 2025), especially in scenarios such as multi-document question answering or Retrieval- Augmented Generation (RAG), where immutable chunks (c.g., documents) remain unchanged across requests but are preceded by varying prefixes.
To strike a balance between accuracy and linking overhead, CacheBlend (Yao et al., 2025) works as follows. First, retrieves the needed KV vectors and concatenates them to obtain KV _oldd. Second, it recomputes all KV vectors in the first layer of the LLM, generating KV_new_L. Third,
"Strictly speaking, uncached tokens are not recomputed, but for simplicity, we use "recomputation" to refer to both cases.
Position-Independers Caching (PIC), inspired by the clas-
3

---

EPIC: Efficient Position-Independee Caching for Serving Large Language Models
Immutable chunks
User
EPIC system
KVCompile le returns a unique cache ID, which users can later reference to enable KV reuse. Second, in the link step, @ users submit requests containing mutable tokens (e.g.. new instructions/ ing an extended chat completion API. The Schedules er component handles these requests by initiating a KVLink prefill. KVLink retrieves the relevant KV vectors from KVCache using the provided cache IDs, concatenates them, recomputes subset of KV vectors ensure correctness, and proceeds to the decode stage for subsequent token gen- eration. The final response is then returned to users. At the core of KVLink is the LegoLink algorithm, which we detail in Section 4.
generate_context. www.totttnncctteeeeeeee cache
compltoonl
along with cache IDs (if any), us-
Chunks of Immutable Tokens
Cache IDs +
Cache IDs
Mutable Tokens
Response
KVCompile
Scheduler
Prefill Stage
Decode Stage
Standard Prefill
KVLink Prefill
Discussion of implicit vs. explicit caching. Many existing systems (Kwon al., 2023; Zheng et al., 2024; Hu et al., 2024a) adopt an implicit eaching paradigm, where the sys- tem automatically manages cache generation, storage, and reuse through internal mechanisms such as hash tables or radix trees. In contrast, EPIC adopts an explicit caching paradigm, where users manage cache generation and reuse via explicit APIs that expose cache IDs. This paradigm, also used by systems such as Google Gemini and Moon- cake (kim; gem, b), reduces indexing overhead and provides greater user control over cache management pariienullaa beneficial in RAG scenarios.
Indexing (e.g. Cache Tree, or, Hash)
KVCache
SAAA 1.
Figure 3. The architecture of EPIC serving system.
compares the attention maps produced by KV old 1 and KV _,nnew_l, selecting the 15% of tokens that exhibit the most discrepancy. Fourth, it recomputes only these 15% of tokens in all subsequent layers'. Only 15% of tokens are necessary because attention exhibits sparsity tokens significantly influence attention computation.
small subset of
4. Algorithm Design
However, CacheBlend has two limitations, First, the time and resource complexities of the recomputation in the link step are the same as the original attention mechanism- O(N"), where N is the number of tokens in the prompt. Figure shows that, although CacheBlend-15 dynami- cally selects 15% of tokens for recomputation, for very long prompts, common in many applications today, this ((15%N22) complexity remains slow and prone to out-of- memory (OOM) errors (Figure 9). Second, CacheBlend re- lies on dynamic attention tors in the first layer; this recomputation incurs heavy run- time overhead in addition the O(N2) recomputation. Fig- 10 shows that the runtime overhead of CacheBlend takes around 16.3% 3% to 63.56% of Momn-TTo-Frrst. Token (TTFT).
In this section, we analyze existing algorithms and propose new algorithm Legollink based on the analysis results.
4.1. Analysis of Existing Algorithms
We analyze the attention map of Naive, FR, and CacheBlend algorithms (Section 2), shown in the bottom right of Fig- ure 4. First, in the Naive's 's attention map, most attention scores concentrate the initial tokens of each chunk, ev- ident from the four bright vertical lines along the x-axis. This pattern arises because EPIC independently compiles each chunk with position IDs starting from zero. As a result, the initial tokens disproportionately absorb attention-a phenomenon known as "attention sink" (Xiao et al., 2024) which prevents subsequent tokens from attending to the answer "Chrysan Company," located at the end of the third chunk (Chunk 1). Second, in the FR's ss attention map, the initial tokens of each chunk release part of their attention to more relevant positions, including "Chrysan Company". However, they still retain relatively strong attention scores partly because they are special begin-of-sentence tokens, such "
" in Llama models. Third, in the CacheBlend's attention map, the pattern closely resembles that of FR, re- flecting its design goal of approximating FR's attention map. Further analysis of CacheBlend's selected 15% of tokens shows that initial tokens of each chunk are frequently in-
all KV vec-
3. System Overview
To support PIC, we develop EPIC (Efficient Position- Independent Caching), a serving system whose workflow aligns with the PIC framework described in Section 2 and consists of two main steps (Figure 3). First, in the com- pile step, 1 users submit immutable chunks via the context caching API. The KVCompil le component processes each chunk using a standard prefill pass to generate KV vectors, which are then stored the KVCache. For each chunk,
'The recomputation rate might decrease deeper layers.

---

EPIC: Efficient Position-Independeee Caching for Serving Large Language Models
Chunk
Chunk
Query
All people living in the Thenum District work in the Chrysan Company.
Which company does Derek wark in? Answer within 5 words and do not...
Derek is a single man living in the Thenum District.
the question based on the given passages.
KV1
KV2
KV
KVCompile
KVLink
KV3
KV
KV
Query
Nalve
KV 3
KV 2
KV
Query
1.Derek
Recompute no takens
Fully Recompute
0
16
27
42
59
(FR)
KV 3
KV 2
KV
Query
Chrysan Company
Recompute all lokens
0
16
27
42
59
CacheBlend
Kv
KV
Query
Chrysan Company
Recompute 15% tokens to numerically approach FR
0
16
27
42
59
LegaLink
KV
KV
KV
Query
Chrysan Company
Recompute inilial tokens chunk
16
27
42
59
Figure 4. Comparison of PIC Algorithms. The area above the dashed line corresponds to the compile step, while the area below corresponds the link step. KVLink recomputes subset of tokens, highlighted dark colors. Four algorithms include Naive, Fully Recompute (FR), CacheBlend, and LegoLink. The bottom right visualizes attention maps (layer 5, head 5 of Llama 3.1 8B) for four decoded tokens. The x-axis marks the position ID the first token of cach chunk. To highlight the differences between attention maps, we normalize the QK" results to the [0, 1| range using min-max scaling instead of Softmax.
cluded, reinforcing the importance of recomputing these tokens to improve accuracy.
- unselected tokens correct positions, forming Kezp and Veup (both with shape (N)d)). Fourth, we compute the attention matrix A (with shape (k', N)) by multiplying Q (with shape (k', d)) with KT (with shape (d, N)), allow- ing the k'' tokens to attend to all N tokens:
4.2. The LegoLink Algorithm
Based the preceding analysis, we propose LegoLink, which recomputes each chunk's first l tokens (except the first chunk), thus linking chunks like Lego pieces. By re- computing these initial tokens, LegoLink enables them to recognize their non-initial status, thereby mitigating their tendency to dominate attention and redirecting attention to relevant positions, as shown in LegoLink's 's attention map in Figure 4. Evaluation results in Section 5 demonstrate that LegoLink consistently preserves accuracy across wide range of datasets and models. See LegoLink's s details in the next paragraph.
A= = softmax (QK? cmp MASK)
(I)
where MASK assures that the k' tokens attend to only tokens before them. Finally, we multiply A (with shape (K', N)) with Veep (with shape (N, d)) to obtain the output (or in- put to the next layer, with shape (k', d)): O = AV Wo. where Wo a matrix with shape (d, d).
In addition preserving accuracy and simple de- sign/implementation, LegoLink offers two key advantages over CacheBlend. First, Legolinnk reduces recomputation complexity to O(kN) creases with the number of immutable chunks instead of N. As described in Section 5, & could potentially become zero. Second, LegoLink relies on static attention sparsity, which selects each chunk's first & tokens to recompute beforehand, further improving performance.
Assuming that we have selected k (I: tokens from each chunk plus the user query) tokens from a total of N (prompt length) tokens, we recompute them as follows. First, we obtain the embedding matrix E (with shape (k,d) of the K' tokens, where d is the hidden size. Second, at layer we compute the new K, Q and V matrices (each with shape (K', d)) for these I tokens: Q = EWq. K = EWK, V = EWv, where Wo. WK. and Wy are model param- eters with shape (d, d) Third, we expand the K and v matrices by incorporating the cached KV vectors of the
O(N), where k << N and in-
5. Evaluation
We begin by describing the experimental setup, including implementation details, datasets, models, evaluation metrics, and software/hardware environment. We then present four key evaluation results.
For notation simplicity, represents all possible hidden di- mension sizes, which may be further divided into the number of heads and head dimensions.
5

---

EPIC: Efficient Position-Indepenne Caching for Serving Large Language Models
ZWIKIMQA
SAMSum MultiNews
HotpotQA
Models. We evaluate EPIC and LegoLink using three state- of-the-art open-source LLMss: Mistral 7B Instruct (Jiang et al., 2023), Llama 3.1 8B Instruct (Dubey et al., 2024), and Yi Coder 9B Chat (Young et al., 2024). These models represent diverse architectures and training recipes. Rather than employing quantized versions of larger models, we select smaller models to accommodate our limited GPU resources. Additionally, we do not choose models fine- tuned for the six specific task types, as the number of such models is extensive. While our chosen general-purpose base models may exhibit lower absolute accuracy on these tasks, the relative accuracy drop compared to the base model is sufficient to demonstrate the effectiveness of EPIC and LegoLink.
MusiQue
Needle
(a) Prompt length distribution
(b) Answer length d distribution
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
5000
10000
15000
0
200
400
600 800
Prompt length (tokens)
length (tokens)
Figure 5. Prefill and decode length distribution.
5.1. Experiment Setup
Baselines. We compare LegoLink with the other three recomputation algorithms in Figure 4: FR, Naive, and CacheBlend (Yao et al., 2025). Additionally, we evaluate different variants of CacheBlend, denoted as CacheBlend-r, where represents the ratio of tokens recomputed. Simi- larly, we evaluate different variants of LegoLink, denoted as Legol.ink-k, where k refers to each chunk's s first & tokens.
Implementation. We implement EPIC based on vLLM
0.4.1 (Kwon et al., 2023), with 2K lines of code in Python. We incorporate the four PIC algorithms presented in Fig- ure 4. We port CacheBlend from their public repository".
Dataset. Following CacneBlend, we evaluate on four LongBench datasets (Bai et al., 2024): 2WikiMQA (multi- document question answering), MuSiQue (multi-document question answering), SAMSum (few-shot instruction follow- ing), and MultiNews (multi-document summarization). We also include HorporQA (multi -outt-d question answer- ing) from LongBench, which identifies the two supporting documents containing the answer, enabling fine-graing fine-grained analysis. To evaluate long-contex: retrieval, we include the Needle in a Haystack dataset (LLM), which tests the model's s ability to locate and retrieve a single inserted fact from unrelated documents of varying lengths. All datasets contain 200 test cases, with the distribution of prompt (pre- fill) lengths and answer (decode) lengths shown in Figure Immutable tokens constitute approximately 95%-99% of the prompt, while mutable tokens are fewer than 50.
Environment. We run experiments on single NVIDIA A100 server with one A100-80GB GPU available. The server has 128-core Intel(R) Xeon(R) Platinum 8358P CPU@2.60GHz with 2 hyperthreading and 1TB DRAM. We use Ubuntu 20.04 with Linux kernel 5.17.7 and CUDA 12.6.
5.2. Workloads
We construct the following two kinds of workflows out of the six datasets.
Synchronous workload. To evaluate the accuracy- trade-off without interference from concurrent requests, we process test cases sequentially, ensuring that each completes before the next begins. First, for each test case, we compile all immutable chunks to obtain their corresponding cache IDs. For the LengBench dataset (excluding SAMSum), we treat each document as a chunk. For SAMSum and Needle- Haystaay,, we split all immutable tokens into 512-token chunks. Second, we send a request containing the cache IDs of cached chunks along with the query to obtain the response.
Metrics. We use the following three metries to evaluate per- formance and model accuracy. First, Time-To To-First-Tie Firss-TTkenn (TTFT) (Kwon et al., 2023) (lower is better) is used to evalu- ate all datasets. This metric measures the prefill-stage time: the time from when users send a request to when users re- ceive the first token; this time could be reduced by using con- text caching. Second, Fl score (Bai et al., 2024) (higher is better) is used to evaluate 2 2WikiMQA, MuSiQue, HotporQA, and needle in a haystack. This metric measures the simi- larity between I.LMM' output and the ground-truth answer based on their common words. Third, Rough-L score (Lin, 2004) (higher is better) is used to evaluate SAMSum and MultiNews. This metric measures the similarity between LLMs' output and the ground-truth answer by calculating the length of their longest common subsequence.
Asynchronous workload. To evaluate the latency and throughput of EPIC under varying request rates (requests per second), we simulate a PIC scenario as follows.. First, we select d test cases from 2 2WikiMQA to simulate d active users. As the number of users increases, larger portion of the GPU HBM is allocated to their position-independn
cache.
SPIC is relatively new approach and lacks publicly available traces or request arrival patterns. We try our hest to mitigate potential hias in constructing this asynchronous workload.
http:://gtthh..cco//oollaayallal Accessed in Sep 2024.
6

---

EPIC: Efficient Resition-Independee Caching for Serving Large Language Models
Cacheöiend-15
Cacheblerd-1
Legetine-
hatre
Cacheälend 10
Logzüink-22
Legolnnc4
Cachetlerd-cc
CacheSlend-5
Legotinbsle
Legoline22
Mistral 78 Instruct
Laaa 3.1 BB Instruct
Y Coder 98 Chat
0
16
26
40
56
6.6.
0.c
Reedle
F1 soor
Figure 7. Attention map of LegoLink-O using the example in Fig- ure 4.
6.2
00
0.2
0.4
0.000
0.2
9.4
0.00
9.2
0..4
HolpotD4
Fi v/0rr
0.3
0.5
0.3
LegoLink variants (a series of gradient blue stars) establish a new Pareto frontier, outperforming CacheBlend variants (a series of gradient orange rectangles) in most cases. Second, LegoLink-2 is sufficient to limit accuracy drops within 0 7% and reduces up to 300% TTFT, compared to the default CacheBlend- 15 configuration. On the contrary, CacheBlend- CacheBlend-5, which recomputes a similar number of tokens most LegoLink variants (except on SAMSum), ex- hibits significant accuracy degradation- up to 80% worse than FR. Third, increasing the number of recomputed tokens in LegoLink yields diminishing accuracy gains. Recomput- ing only a small number of initial tokens suffices to restore most of the accuracy, whereas CacheBlend requires substan- tially more recomputation for marginal benefits.
0.2
0.2
0.2
0.3
0.1
0000
100
0.5
1/3
1.0
0.20
0.00
0.00
Rouqe-L acore
3.00
0.20
3.04
0.32
0.02
0.02
0.4
0.2
5.
0.2
0.2
0.00
0.0
0.1
6.2
Rouged scone
5AMtumm
2.
0.2-
6.3
0.1
0000
0.5
1.0
0.5
1.0
9.8
2.5
10
0.20
0.26
0.20
MUSiQUs
5c0re)
In addition, we also have three unusual observations that warrant further explanation. First, all algorithms, including FR, CacheBlend, and LegoLink, exhibit low accuracy in the Yi Coder model due to its poor handling of document understanding. This observation suggests that, to ensure that PIC algorithms perform optimally, robust models well suited to the task are required. Second, all approaches us- ing all models perform poorly on the MultiNews dataset. This phenomenon can be attributed to the inherent diffi- culty of summarizing long documents with small models. Third, CacheBlend and LegoLink exhibit similar TTFT in the MultiNews and SAMSum datasets. Each document in these datasets is relatively short (around one hundred to- kens), making the number of tokens recomputed (k tokens in LegoLink-k) equivalent to the ratio of tokens recomputed (r% in CacheBlend-r).
9.30
0.30
3.05
0.05
0.05
2.08
0.5
1.0
1/5
0.00 0
0'5
3.0
335
0.00
63
1/0
155
2WARMDA
F1 score
0.2
6.2
0.2
0.3-
0/3
0.4
0.6
6.80
0.2
2.4
0.6
/
Figure 6. Accuracy vs. TTFT. Each point indicates the average TTFT and accuracy for running synchronous workloads of one dataset (row) on one model (column) using one specific algorithm (each legend label). The in Legol.ink-k denotes the numher of re- computed initial tokens for each chunk, while the in CacheBlend- r represents the ratio of all recomputed tokens. The black star represents LegoLink-00 0, zero-linking algorithm.
5.4. Algorithm Analysis
This portion is defined as the Context Cache Ratio (CCR). Second, each user compiles all immutable chunks in the test case once and then repeatedly sends the same request (con- taining cache IDs of cached chunks along with the query) at constant rate over 40-second period. Although each user resends identical requests, this setup effectively simulates user having different queries over the same document set, with all other context caching mechanisms, such as prefix caching, disabled. Third, we simulate request arrival times by sampling from a Poisson distribution.
To further understand LegoLink, we introduce LegoLink- O, a variant that shifts all linking overhead to the compile step and comprises two different PIC steps. First, EPIC prepends four dummy tokens (e.g.. begin-offsentence to- kens) to each immutable chunk during compilation, then discards their corresponding KV vectors. This removal elim- inates "attention sink" tokens in advance, preventing them from interfering with subsequent attention computations. Second, in the link step. LegoLink-O skips recomputation entirely, incurring zero runtime overhead.
5.3. Accuracy-Latency Trade-off of LegoLink
Using the synchronous workload, we draw two key insights from the results in Figure 6 and Figure 7. First, LegoLink-O, despite its minimal link-time cost, Legolink-O preserves
Using the synchronous workload described earlier, we draw three key insights from the results in Figure 6. First,
7

---

EPIC: Efficient Position-Independe Caching for Serving Large Language Models
Logotink-t8 #00R-11%
Logotink ROOR-TES
CochcB and 4CCR-445
Logobink-16 SCCR---S 32%
Logolink 16, 1DGR-92%
Cachett wnd-tt NCCN-e5%%
6
FR
LogoLink:18: FCCR-55
Legobinb-1o #ccre-ens
Cochelllee- #CCR-12%
Cachedlane-15 #CONN-11%
Cache end 8CCR-78N
CachwiBees--15 WCCR+
5
CacheBlend-15
LegoLink-16
0.8
Through (taneres)
2-
1-
10000 20000 30000 40000 50000 Context length (#r tokens)
0.
2.5 5.0
Requeet rate (negts)
7.5
10.0
12.5
2.5
Request rate (mpls)
5.0
7.5
10.0
12.5
Figure 9, TTFT vs. context length FR, CacheBlend- 15, and LegoLink-16 16, using a fixed chunk size of 512 tokens. For FR, we do not compile context cache to display its full quadratic time complexity trend, as it would otherwise run out of memory earlier than CacheBlend- 15 and Legoo.ink-16.
Figure& 8. Latency and throughput comparison of Legol.ink-16 16 and CacheBlend-15 under asynchronous workloads with varying re- quest rates and context cache ratios (CCR). Each data point rep- resents the average and standard deviation from five experiments. LegoLink- 16 is shown using solid lines, while CacheBlend- 15 is represented with dashed lines. Two algorithms with same CCR are shown in the same color.
observe three key trends. First, LegoLink-16 achieves up to an 8x reduction in TTFT compared to CacheBlend-15. Sec- ond, as the Context Cache Ratio (CCR) increases, LegoLink- 16 remains stable 7TFT, whereas CacheBlend-15 fluctu- ates around 0.5 seconds. This stability likely results from LegoLink- 16 generating fewer intermediate results; higher CCR reduces available memory for intermediate computa- tion, but LegoLink-16 16 incurs less recomputation overhead than Cache Third, TTFT plateaus as request rate increases, rather than growing exponentially. This plateau reflects vLLM's scheduling policy, which limits the number of concurrent rumning requests based on available memory. If we included the TTFT of all waiting (queued) requests, the average TIFT would approach infinity.
accuracy remarkably well. Second, the "attention sink" phe- nomenon disappears in the middle (Figure 7), reinforcing the importance of mitigating chunk-initial tokens' influence on subsequent attention computations. On the other hand, the previously raised concern in CacheBlend regarding lim- ited cross-attention across chunks proves less impactful in practice. Query and decoded tokens can still attend to all ear- lier chunks, enabling effective aggregation of cross-chunk information.
Discussion of lengthy outputs in sparsity algorithms. LegoLink variants occasionally show reduced accuracy on cases such as (MultiNews, Llama 3.1) and (Needle, Yi). However, this drop stems not from incorrect answers but from unnecessarily lengthy outputs. For the example in Fig- ure 4, LegoLink-O correctly begins with "Chrysan Company" but continues with unrelated content such "and that Derek is living in ...," which lowers F1 or ROUGE-L scores. We observe similar behaviors in other sparsity-basee algorithms such as StreamingLLM (Xiao et al., 2024), H2O (Zhang et al., 2023), and Quest (Tang et al., 2024). Such behavior latency
Regarding throughput versus request rates (right of Fig- ure 8), we observe two notable facts. First, LegoLink- 16 achieves a throughput that is up to 7x higher than CacheBlend-15, as it recomputes fewer tokens, allowing more requests (about 7x) to be processed simultaneously. Second, CCR increases, LegoLink-16's throughput con- tinues to improve until the CCR reaches threshold (approx- imately 30%), beyond which further increases in CCR lead to a reverse effect because requests start to severely interfere with each other. In contrast, CacheBlend- 15's throughput remains constant as it becomes incapable of handling addi- tional requests.
undermines the primary goals of and resource usage. We leave a more detailed investigation of this behavior to future work.
5.6. EPIC's Performance on Long Context
5.5. Latency and Throughput of EPIC
We send requests of varying context lengths with a fixed chunk size (512 tokens) synchronously to EPIC, yield- ing two observations from the results (Figure 9). First, context length increases, the TTFT of both FR and CacheBlend-15 grows quadratically, while Legolink- 16 ex- hibits nearly linear growth. This difference arises because FR and CacheBlend-1 15 have time and resource complexities of O(N2), while LegoLink- 16 operates with a complexity of OkN),, where & represents the number of recomputed
We employ the artificial asynchronous workloads on LegoLink-16 (16 is the block size of vLLM and mod- erate number of tokens to recompute) and CacheBlend-15, presenting results in Figure& 8. Notably, the numbers in this section should be interpreted cautiously when considering real-world scenarios.
Regarding TTFT versus request rates (left of Figure 8), we
8

---

EPIC: Efficient Cosition-IInepeenn Caching for Serving Large Language Models
tokens (k < N). Second, LegoLink-16 supports a longer context length compared CacheBlend-155 Specifically, CacheBlend-15 encounters an out-of-memory (OOM) error at approximately 35,000 tokens, while LegoLink-16 16 avoids OOM until the context length reaches 50,000 tokens. This difference is due to CacheBlend- 15's need to recompute more tokens and generate additional intermediate results, leading to higher GPU memory usage.
2023), Quest (Tang et al., 2024), Vrk (Chen al., 2024), RaaS (Hu al., 2025a)) determines important tokens runtime. Second, static sparsity (e.g.. Longformer (Beltagy et al., 2020), StreamingLLM (Xiao et al., 2024)) relies on predefined sparse patterns. CacheBlend leverages dynamic sparsity while Legoliink leverages static sparsity to enable efficient linking.
Retrieval- -uggeeee-- Generation (RAG), RAG (Li et al., 2022; Jin et al., 2024; Gao et al., 2023; Jeong et al., 2024; Ram et al., 2023; Mao et al., 2021) enhances LLMs' capa- bilities by integrating external knowledge to improve factu- ality and relevance. For example, at the application level, Adaptive- RAA (Jeong et al., 2024) dynamically selects re- trieval and generation strategies based on query complexity. At the system level, RAGCache (Jin et al., 2024) reduces lateney by caching and reusing intermediate states from retrieved documents. PIC has strong potential in RAG sce- narios, where reusing documents' KV cache across requests can yield significant performance gains.
6. Related Work
This work formalizes Position-Independent Context Caching (PIC) and advances the state of the art in this emerging area. Below, we outline the broader design space relevant to our work.
LLM-serving optimizations. Numerous systems have recently emerged to improve LLM serving efficiency. vLLM (Kwon et al., 2023) introduces Paged/Attention to achieve high throughput, while SGLang (Zheng et al., 2024) provides both a domain-specific frontend language and an optimized backend runtime. DeepFlow (Hu et al., 2025b) in- tegrates the advantages of existing research work into a sys- tem running on Ascend accelerators Huawei Cloud. In ad- dition to full systems, rescarchers have proposed scheduling techniques such as disaggregated prefill and decode (Zhong et al., 2024: Hu et al., b024a;b; Patel et al., 2024), contin- uous batching (Yu et al., 2022), and multi-LoRA integra- tion (Sheng et al., 2024; Li et al., 2024). Storage-related opti- mizations such as KV-cache-centrie inference systems (Qin al., 2025; Hu al., 2024a) also contribute to this space.
7. Conclusion
In this paper, we have formalized the Positional- Independent-Cachh (PIC) framework. Within this frame- work, we have proposed EPIC, a system that incorporates the LegoLink algorithm to address key limitations of ex- isting approaches. By leveraging static attention sparsity, LegoLink significantly reduces recomputation complexity in the link step while maintaining accuracy. Extensive eval- uation across six datasets and three LLM models has shown that EPIC achieves significant improvements in 7TFT and throughput compared to existing systems, with minimal or accuracy loss.
Context Caching (CC). Two primary types of context caching have emerged. First, prefix-based CC emerged in late 2023, represented by Pensieve (Yu et al., 2025), CacheGen (Liu et al., 2024), and SGLang (Zheng et al., 2024). Recently, vendors such as Kimi (kim) and Gem- ini (gem, b) have begun offering explicit CC APIs Sec- ond, PIC emerged in mid-2024 and CacheBlend (Yao al., 2025) represents the first attempt tackle the PIC challenge, although it does not formally define the challenge. Prompt- Cache (Gim et al., 2024) aims to support PIC, but its reuse remains position-dependee
Acknowledgments
This work was partially supported by National Natural Sci- ence Foundation of China under Grant No. 92464301. We would also like thank the anonymous reviewers for their insightful comments and suggestions, which helped improve the quality of this paper.
In this paper, we formally de- fine PIC and advance the state of the art by introducing LegoLink, a low-overhead or even zero-overhead linking algorithm.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Sparsity. Sparsity plays crucial role in improving long- context inference and falls into two types: dynamic and static. First, dynamic sparsity (e.g., H2O (Zhang et al.,

---

EPIC: Efficient Position- Pesition-Indeeendent Caching for Serving Large Language Models
References
Gim, I., Chen, G., Lee, S., Sarda, N., Khandelwal, A., and Zhong, L.. Prompt cache: Modular attention reuse for low-latency inference. In Proceedings of the Seventh Annual Conference on Machine Learning and Systems, pp. 325-338, 2024.
Needle In A Haystack.
httpa://github. com/
Gemini. httppp:://gmmmi..ggogss...c.///
Gemini context caching. http::::at..tootttaattts dev/
Hu, C., Huang, H., Hu, J., Xu, J., Chen, X., Xie, T., Wang, C., Wang, S., Bao, Y.. Sun, N., and Shan, Y. MemServe: Context caching for disaggregated LLM serving with elastic memory pool. CoRR, 2024a.
gemini-apa httpa//aaap./bboo/aaaacagg/a//// b.
Kimi context caching. https://platform
Hu, C., Huang, H., Xu, L.,, Chen, X., Xu, J., Chen, S., Feng, H., Wang, C., Wang, S., Bao, Y., Sun, N., and Shan, Y. Inference without interference: Disaggregate LLM inference for mixed downstream workloads. CoRR, 2024b.
LMCache. attps://githun wwt.c//c////ce../e
Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z Du, Z., Liu, X., Zeng, A., Hou, L., Dong, Y., Tang. J., and Li, LongBench: A bilingual, multitask bench- mark for long context understanding. In Proceedings of the Sixty-Second Annual Meeting of the Association for Computational Linguistics, pp. 31 19-333, 2024.
Hu, J., Wang, C., Huang, H., Luo, H., Jin, Y., Deng, Y., and Xie, T. Predicting compilation resources for adap- tive build in an industrial setting. In Proceedings of the high--E IEEE/ACM International Conference on Au- tomated Software Engineering, pp. 1813-1813, 2023.
Beltagy, I., Peters, M. E., and Cohan, A. Longformer: The long long-document transformer. CORR, 2020.
Chen, R., Wang, Z., Cao, B., Wu, T., Zheng, S., Li, X., Wei, X., Yan, S., Li, M., and Liang, Y. Arkeale: Efficient gen- erative LLM inference with recallable key-value eviction. In P Proceedings of the Advances in Neural Information Processing Systems, pp. 10...11..111 113134-113155, 2024.
Hu, J., Huang, W., Wang, W., Li, Z., Hu, T., Liu, Z., Chen, X., Xie, T., and Shan, Y. Efficient long- long-decoding in- ference with reasoning- aware attention sparsity. CoRR, 2025a.
Hu, J., Xu, J., Liu, Z., He, Y., Chen, Y., Xu, H., Liu, J., Zhang, B., Wan, S., Dan, G., Dong, Z., Ren, Z., Meng, J., He, C., Liu, C., Xie, T., Lin, D., Zhang, Q. Yu, Y., Feng, H., Chen, X., and Shan, Y. DeepFlow: Serverless large language model serving at scale. CORR, 2025b.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., Goyal, A., Hartshorn, A., Yang, A., Mitra, A., Sravanku- mar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A., Rodriguez, A., Gregerson, A., Spataru, A., Rozière, B., Biron, B., Tang, B., Chern, B., Caucheteux, C., Nayak, C., Bi, C., Marra, C., McConnell, C.,, Keller, C., Touret, C. Wu, C., Wong. C., Ferrer, C. C., Nikolaidis, C., Al- lonsius, D., Song, D., Pintz, D., Livshits, D., Esiobu, D., Choudhary, D., Mahajan, D., Garcia-Olano, D., Perino, D., Hupkes, D., Lakomkin, E., AlBadawy, E.,, Lobanova, E., Dinan, E., Smith, E. M., Radenovic, F., Zhang, F., Synnaeve, G., Lee, G., Anderson, G. L., Nail, G., Mialon, G., Pang. G., Cucurell, G., Nguyen, H., Korevaar, H., Xu, H., Touvron, H., Zarov, I., Ibarra, I. A., Kloumann, I. M., Misra, I., Evtimov, I., Copet, J., Lee, J., Geffert, J.. Vranes, J.. Park, J., Mahadeokar, J., Shah, J., van der Linde, J., Billock, J., Hong, J., Lee, J., Fu, J., Chi, J., Huang. J., Liu, J., Wang, J., Yu, J., Bitton, J., Spisak, J., Park, J., Rocca, J., Johnstun, J., Saxe, J., Jia, J., Alwala, K. V., Upasani, K., Plawiak, K., Li, K., Heatield, K., Stone, K., and et al. The Llama 3 herd of models. CoRR, 2024.
Jeong, S., Back, J., Cho, S., Hwang, S. J., and Park, J. Adaptive-RAGe Learning to adapt setrieval-augmente large language models through question complexity. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 7036-70565 2024.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., de Las Casas, D., Bressand, F,, Lengyel, G., Lample, G., Saulnier, L., Lavaud, L. R., Lachaux, M., Stock, P., Scao, T. L.,, Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E. Mistral 7b. CoRR, 2023.
Jin, C., Zhang, Z., Jiang, X., Liu, F,, Liu, X., Liu, X., and Jin, X. RAGCache: Efficient knowledge caching for retrieval-augmeenedd generation. CoRR, 2024.
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, Efficient memory management for large language model serving with PagedAttention. In Proceedings of the Twenty-Ninth Symposium Operating Systems Principles, pp. 611- 626, 2023.
Gao, Y., Xiong, Y., Gao, X., Jia, K., Pan, J., Bi, Y., Dai, Y., Sun, J., Guo, Q., Wang, M., and Wang, H. Retrieval- augmented generation for large language models: A sur- vey. CoRR, 2023.
10

---

EPIC: Efficient Position- Pesition-Independet Caching for Serving Large Language Models
Li, H., Su, Y., Cai, D., Wang, Y., and Liu, L. A survey on retrieval-augmented text generation. CoRR, 2022.
First International Conference on Machine Learning, pp. 47901-47911 2024.
Li, S., Lu, H., Wu, T., Yu, M., Weng, Q. Chen, X., Shan, Y., Yuan, B., and Wang. W. CaraServe: CPU-assisted and rank-aware LoRA serving for generative LLM inference. CoRR, 2024.
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Effi- cient streaming language models with attention sinks. In Proceedings of the Twelfth International Conference on Learning Representations, 2024.
Lin, C.-Y. Rouge: A package for automatic evaluation of summaries. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pp. 74-81, 2004.
Yao, J., Li, H., Liu, Y., Ray, S., Cheng, Y., Zhang, Q., Du, K., Lu, S., and Jiang, J. CacheBlend: Fast large language model serving for RAG with cached knowledge fusion. In Proceedings of the Twentieth European Conference on Computer Systems, pp. 94-109, 2025.
Liu, Y., Li, H., Cheng, Y., Ray, S., Huang, Y., Zhang, Q.. Du, K., Yao, J., Lu, S., Ananthanarayanan, G., Maire, M., Hoffmann, H., Holtzman, A., and Jiang, J. Cachegen: KV cache compression and streaming for fast large language model serving. In Proceedings of the ACM SIGCOMM 2024 Conference, pp. 38-56, 2024.
Young, A., Chen, B., Li, C., Huang, C., Zhang, G., Zhang, G., Li. H., Zhu, J., Chen, J., Chang. J., Yu, K., Liu, P., Liu, Q.. Yue, S., Yang, S., Yang, S., Yu, T., Xie, W., Huang, W., Hu, X., Ren, X., Niu, X., Nie, P., Xu, Y., Liu, Y., Wang, Y., Cai, Y., Gu, Z., Liu, Z., and Dai, Z. Yi: Open foundation models by OL.AI CoRR, 2024.
Mao, Y., He, P., Liu, X., Shen, Y., Gao, J., Han, J., and Chen, W. Generation Geeneratio--augmented retrieval for open-domain question answering. In Proceedings of the Fifty-Ninth Annual Meeting of the Association for Computational Lin- guistics and the Fleventh International Joint Conference on Natural Language Processing, pp. 4089-4100, 2021.
Yu, G., Jeong, J. S., Kim, G., Kim, S., and Chun, B. Orca: A distributed serving system for transformer-baa erative models. In Proceedings of the Sixteenth USENIX Symposium on Operating Systems Design and Implemen- lation, pp. 521-538, 2022.
gen-
Patel, P., Choukse, E., Zhang, C., Shah, A., Goiri, f., Maleki, S., and Bianchini, R. Splitwise: Efficient generative LLM inference using phase splitting. In Proceedings of the Fifty-First Annual International Symposium on Computer Architecture, pp. 118-132, 2024.
Yu, L.,, Lin, J., and Li, J. Stateful large language model serving with Pensieve. In Proceedings of the Twentieth European Conference on Computer Systems, pp. 144 158, 2025.
Zhang, Z., Sheng, Y., Zhou, T., Chen, T., Zheng, L.., Cai, R., Song, Z., Tian, Y., Ré, C., Barrett, C. W., Wang. Z., and Chen, B. H2O: heavy-hitter oracle for efficient generative inference of large language models. In Proceedings of the Advances in Neural Information Processing Systems, pp. 34661-34710, 2023.
Qin, R., Li, Z.,, He, W., Cui, J., Ren, F., Zhang, M., Wu, Y., Zheng, W., and Xu, X. Mooncake: Trading more storage for less computation A KVCache-centire architecture for serving LLM chatbot. In Proceedings of the Twenty-Thrd USENIX Conference on File and Storage Technologies, pp. 155-170, 2025.
Zheng, L., Yin, L.,, Xie, Z., Sun, C., Huang, J., Yu, C. H., Cao, S., Kozyrakis, C., Stoica, Gonzalez, J. E., Barrett, C. W., and Sheng, Y. SGLangg Efficient execution of structured language model programs. In Proceedings of the Advances in Neural Information Processing Systems, pp. 62557-62583, 2024.
Ram, O., Levine, Y., Dalmedigos, I., Muhlgay, D., Shashua, A. Leyton-Brown, K., and Shoham, Y. In-context -ugmented language models. Transactions of the Association for Computational Linguistics, pp. 1316 1331, 2023.
Sheng, Y., Cao, S., Li, D., Hooper, C., Lee, N., Yang, S., Chou, C., Zhu, B., Zheng, L., Keutzer, K., Gonzalez, J., and Stoica, I. SLoRA: Scalable serving of thousands of lora adapters. In Proceedings of the Seventh Annual Conference on Machine Learning and Systems, pp. 296 311, 2024.
Zhong, Y., Liu, S., Chen, J., Hu, J., Zhu, Y., Liu, X., Jin, X., and Zhang, H. DistServe: Disaggregating prefill and decoding for goodput-optimizei LLM serving. In Proceedings of the Eighteenth Symposium on Operating Systems Design and Implementation, pp. 193-210, 2024.
Zhou, Z., Ning, X., Hong. K., Fu, T., Xu, J., Li, S., Lou, Y., Wang, I.,, Yuan, 7., Li, X., Yan, S., Dai, G., Zhang, X., Dong, Y., and Wang, Y. A survey on efficient inference for large language models. CoRR, 2024.
Tang, J., Zhao, Y., Zhu, K., Xiao, G., Kasikci, B., and Han, S. QUEST: query-aware sparsity for efficient long- context LLM inference. In Proceedings of the Forty-

---

EPIC: Efficient Position-Independee Caching for Serving Large Language Models
Mistral Instruct
Liama Instruct
Coder 98 Chat
Figure 10 presents the average time-to-fisstttoken (TTFT)
15
across 200 requests, with breakdown of computational costs. The second transformer layer-where 15% of tokens for recomputation are dynamically sellected-conrriin 16.37% - 63.56% of the total 7TFT. This finding under- scores the substantial overhead introduced by dynamic spar- sity CacheBlend. In contrast, static sparsity, which pre- defines the recomputed tokens, significantly reduces this overhead, detailed in Section 4.
Ims
12-
Runtime overhead
32.33%
10.
Runtima averhead
32.31%
overfead
6b-
HotpolcA mis
30-
Runtime overhead 58.40%
30-
Runtime averhead
Runtimm overfead
13
20-
51.96%
10
20
30
10
20
30
20
40
B. Implementation Details
Multihewss
Runtime overhead 20.05%
Runtime overhead 17.68%
Runtime overhead 16.37%
We implement KVCache" based vLLM'ss original mem- ory management and prefix caching subsystem with the following changes. First, we add cache-ID--bssed indexing mechanism using the sequence group ID as the cache ID, Second, since the original vLLM manages historical KV cache residing in HBM only, we extend it to include DRAM and local filesyste,, akin to Mooncake (Qin al., 2025). Third, we modify the scheduler retain block tables and memory for PIC compile requests. Fourth, also imple- ment helper APIs that allow users to manage the lifecycle of KV cache, such as reachhe (cache-id).
SAMSum time: ms
Runtime overhead
49.49%
20.
Runtime avarhead 42.31%
Runtiime overhead 44.11%
12-
10-
10
10
20
30
10
20
32
20
40
MusiQuue mm
Runtime overhead 63.56%
everheed
overhead
58.791 79%
20-
20
We implement KVCompile as a standalone module that handles CC APIs that are similar those in Kimi (kim) and Gemini (gem, a). KVCompils le forwards a request to Regular Prefill with maximum generation token set to O.
10
0
19
20
25
20
20
2WNOMOO
15
40.67%
averhead
10
Runtime averhead
10
Runtimm overhead 35.68%
We implement KVLink as parallel module of the Regular Prefill. First, we adapt the model archi- tecture to support masked attention across tokens scattered in different positions. Second, we modify the attention backends handle data placement, movement, and the computational steps required by PIC algorithms, to ensure efficient recomputation.
10
15
20
LD
Layer
Layer
Figure 10. TTFT breakdown of CacheBlend-15.
A. Runtime Overhead of CacheBlend
We evaluate the runtime overhead of CacheBlend us- ing the synchronous workloads described in Section 5.
As building a highly efficient KVCache is not the core focus of this paper, we build a minimal working system.
12


Reviews:
[{"review_id": "oKnUK1iX03", "reviewer": "Reviewer_DTWU", "summary": "This paper introduces PICI, an efficient position-independent context caching system for serving large language models. The system pre-computes the KV caches of unchanged contents and splits them into blocks. The incorporated method, LegoLink, leverages the static attention sparsity of each block,  eliminating the influence of the attention sink phenomenon in each chunk to minimize recomputation for accuracy recovery when using position-independent context caching. \n\nComprehensive experiments validate the effectiveness and efficiency of the proposed method, providing additional insight into efficient LLM.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We address the review questions below.\n\n> More details (overall workflow, cache hit def, too-large cache) of PICI system in the main text instead of the appendix.\n\nDue to page limits, we prioritized the attention sink effect in PIC and our simple yet effective algorithm, placing system details in the appendix. However, we acknowledge this omission and will move system details back to the main text. Below is a summary (from the appendix) related to review questions.\n\nPICI workflow: 1) Users cache frequently used documents via generate_cache API, receiving a cache_id. 2) Users pass queries and cache_ids to PICI in any order (position-independent), and PICI retrieves the cache with minimal overhead (simple cache_id → cache address mapping) and finishes linking as described in the paper. \n\nPICI design philosophy (similar to Gemini): users (or a RAG system) explicitly control caching. 1) Users decide what doc (big or small, frequently used or not) is worth caching and for how long at known costs (xx $/token/hour). For now, PICI never actively deletes users’ PIC cache (more in the next paragraph). 2) Users explicitly pass cache_id to define cache hits. 3) For now, the PIC cache resides in GPU memory (no swap in/out).\n\nIn contrast, systems like vLLM and SGLang use implicit caching, where cache hits rely on token prefix-matching and swap in/out mechanisms are used for memory management. Future work will explore integrating explicit PIC caching with implicit prefix-based caching and optimizing their placement in the memory hierarchy.\n\n\n> Pre-computing and saving the KV caches for long documents requires larger storage than string.\n\nYes, it is always a hard trade-off between memory efficiency and computational savings. However, in the PICI design philosophy, users retain the flexibility to enable or disable caching based on their specific needs. Given their deeper understanding of application semantics and intent, users are often better positioned than the system itself to make optimal PIC caching decisions. This flexibility helps prevent unnecessary memory consumption by avoiding the storage of large, unused caches.\n\n> Missing citations in Section 2.2.\n\nWe will correct the citation problems in Section 2.2, making them as complete as in the Related Work section.\n\n> Line 220: O=AVW_O, should be O=AV_{exp}W_O?\n\nYes.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and/or evaluation criteria (e.g., benchmark datasets) make sense.\n\nMore details of the proposed PICI system should be introduced in the main paper instead of in the appendix.", "theoretical_claims": "n/a", "experimental_designs_or_analyses": "I have checked the soundness/validity of any experimental designs or analyses.", "relation_to_broader_scientific_literature": "This paper's motivation is related to the KVLink algorithm, e.g., CacheBlend, and its idea is related to the KV cache eviction method, e.g., StreamingLLM, H2O.", "essential_references_not_discussed": "See Other Strengths And Weaknesses.", "other_strengths_and_weaknesses": "Strengths:\n1. This paper is well-written and easy to follow. \n2. The motivation of this paper is clear. Position-Independent Context Caching is practical in real world application.\n3. Using a static attention sparsity that determines the tokens to recompute is both effective and efficient. \n4. Comprehensive experiments show the effectiveness of LegoLink, and give some interesting insight (e.g., Section 4.4) into the PIC area.\n\nWeaknesses:\n1. In the proposed PICI, how to retrieve the KV cache from a KV cache set remains exploration. The authors treat the implementation of PICI system as their contribution, but the details of PICI are in the appendix.\n2. Pre-computing and saving the KV caches for long documents requires larger storage than string.\n3. Missing related work in the Position-Independent Caching (PIC) of Section 2.2; only a Wikipedia website is cited. \n4. Line 220:  O=AVW_O, should be O=AV_{exp}W_O ?", "other_comments_or_suggestions": "See Other Strengths And Weaknesses", "questions_for_authors": "See Other Strengths And Weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LSBPYbV6kM", "reviewer": "Reviewer_RzKY", "summary": "The authors propose a system of context caching which can store pre-computed key value stores for multiple documents. The proper caches are then retrieved given a user query. The key insight is that only a fixed number of initial tokens needs to be recomputed in order to avoid shifting the attention score distribution due to the sink token phenomena.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We address the review questions below.\n\n> More details (overall workflow, cache hit def, indexing, cache swap in/out, too-large cache) of PICI system in the main text instead of the appendix.\n\nDue to page limits, we prioritized the attention sink effect in PIC and our simple yet effective algorithm, placing system details in the appendix. However, we acknowledge this omission and will move system details back to the main text. Below is a summary (from the appendix) related to review questions.\n\nPICI workflow: 1) Users cache frequently used documents via generate_cache API, receiving a cache_id. 2) Users pass queries and cache_ids to PICI in any order (position-independent), and PICI retrieves the cache with minimal overhead (simple cache_id → cache address mapping) and finishes linking as described in the paper. \n\nPICI design philosophy (similar to Gemini): users (or a RAG system) explicitly control caching. 1) Users decide what doc (big or small, frequently used or not) is worth caching and for how long at known costs (xx $/token/hour). PICI never actively deletes users’ PIC cache (more in the next paragraph). 2) Users explicitly pass cache_id to define cache hits. 3) PIC cache resides in GPU memory (no swap in/out).\n\nIn contrast, systems like vLLM and SGLang use implicit caching, where cache hits rely on token prefix-matching and swap in/out for memory management. Future work will explore integrating explicit PIC caching with implicit prefix-based caching and optimizing their placement in the memory hierarchy.\n\n> Rough-L score --> Rouge-L\n\nYes, thank you for pointing this out. We will fix it.\n\n> I assume that position encodings (PE) for the model are re-used by the chunks of the encoded prefix documents such that the whole process is permutation invariant?\n\nYes. PICI prefills a doc, whose first token is given position 0, to generate their KV cache. Then PICI uses the cache directly without modifying PE. On the contrary, new queries receive position IDs based on their real positions.", "claims_and_evidence": "The claims are supported by evidence.", "methods_and_evaluation_criteria": "The evaluation is sufficient for the problem setting.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The design of the experiments is sound.", "relation_to_broader_scientific_literature": "The contributions of this paper build on recent works which highlighted the appearance of sink tokens in transformers.", "essential_references_not_discussed": "The cited references are sufficient.", "other_strengths_and_weaknesses": "# Weaknesses\n\n- The pitfalls of prefix based caching are mentioned multiple times in the work, such as L138C1. But doesn't the presented algorithm suffer from the same limitation in that it is \"limited to cases with exact prefix matches across requests?\" \n  - From what I can see, there must be a query to a database which has precomputed KV values, and your method proposes minimally recomputing the retrieved tokens, but it does nothing to address the above limitation, correct?", "other_comments_or_suggestions": "L227C2: Rough-L score --> Rouge-L\n\nI would suggest adding more details of the overall algorithm for cache retrieval to the appendix, as I am left with many questions regarding how this is done after fully reading the work.", "questions_for_authors": "- In the current setup, what is the algorithm which decides a cache hit?\n- How does the current setup decide what to evict from the HBM cache in the GPU?\n- Are the caches only stored on GPU, or are they offloaded to CPU memory or hard disk space as well?\n- I assume that position encodings for the model are re-used by the chunks of the encoded prefix documents such that the whole process is permutation invariant?\n\n\n## Post rebuttal\n\nThanks for your responses to my review. I have decided to maintain my current score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XUCIQeu0XH", "reviewer": "Reviewer_i5ZR", "summary": "The paper introduces a context caching method with limited recomputation called LegoLink. Prior work either fully recomputes KV caches for new inference calls (e.g. full re-encoding) or uses dynamic recomputation to recompute a fraction of total cached values (i.e. CacheBlend). To further reduce cost, LegoLink has a static set of values to recompute when reusing cache (primarily the first few tokens in each block, i.e. the attention sink). The authors demonstrate that this decreases time to first token and maintains strong performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We address the review questions below.\n\n> Missing related work.\n\nThank you for pointing this out. We will include a subsection discussing RAG applications and their connection to context caching. This addition will clarify PICI's positioning without modifying its intended scope.\n\n> AGI. \n\nWe acknowledge that \"AGI\" is controversial and requires a precise definition when discussing it, especially in academic contexts. We will revise the first paragraph.\n\n> Needle in a Haystack\n\nInitially, we evaluated PICI on the same four datasets as CacheBlend (WikimQA, SAMSum, MultiNews, and Musique). To further demonstrate LegoLink’s generalizability, we selected the Needle in a Haystack dataset based on its popularity rather than ease of evaluation or improved results. We acknowledge its limitations as a synthetic task where the \"needle\" is highly distinct from the context. In the revised version, we will clarify our rationale for this dataset selection (popularity instead of methodological suitability) and include passage retrieval results from LongBench, where we expect similar findings.\n\n> Storyline and contribution. \n\nThe revised story (or the original story we plan to tell) should go as follows: 1) We are the first to formally define the PIC problem and decompose its solution into a four-step framework: document chunking, cache generation, retrieval, and linking. This structured approach establishes a diverse solution space (contribution 1). 2) CacheBlend, the first PIC work, fits in our framework and mainly designs the linking step, while LegoLink enhances its efficiency (contribution 2). 3) LegoLink-0 further improves performance by mainly designing the cache generation step, thereby simplifying the linking step (contribution 3). \n\nThis framework establishes a diverse solution space for future research. The key consideration is the distribution of computational costs across different steps. Allocating cost to the chunking or cache generation step resembles a compile-time expense—incurred once but benefiting all subsequent queries. Conversely, placing cost in the retrieval or linking step resembles link-time expense—introducing runtime overhead but allowing for more adaptive and potentially more accurate solutions. In the appendix, we call on future research to find more efficient and accurate solutions utilizing our framework.\n\nThe above details are currently in the appendix and will be integrated into the main text.\n\n> Text clarity.\n\nWe appreciate the feedback and will improve clarity on terms like \"token,\" O-notation, \"base\" model, and figure positions.\n\n> Still strong attention on chunk boundaries (Figure 3) \n\n1) Experiments show that the first token retains relatively strong attention absorption due to being a begin-of-sentence token (\"
\" in LLaMA). This insight motivates LegoLink-0, where we discard \"
\" tokens (and dummy tokens which are also \"
\" tokens), except for the first chunk. \n2) In the softmax map, we could still observe that recomputation reduces boundary attention, but attention-score differences on mid-content are harder to observe. We will add a softmax map for cross-comparison.", "claims_and_evidence": "I think the claims are generally supported by the evidence.\n\nA nitpick: I think the framing in the very first paragraph-- that LLMs have advanced the progress of AGI-- is not generally agreed and doesn't add much to the paper. This did not factor into my review scores, but personally I don't think it adds anything to use the term AGI here when it is still a contested idea.", "methods_and_evaluation_criteria": "Generally yes, I think measuring time-to-first-token is reasonable for a method focused on improving efficiency in the prefill stage. The model sizes and choice of models seems reasonable. \n\nThe authors substitute Needle in a Haystack for multi-doc retrieval (in line 260), saying that it is a more suitable benchmark for retrieval. I disagree-- I think this is actually generally a worse test of capabilities, as it is a much more synthetic task where the needle will be very distinct from the context. I don't think this really has an impact on the paper's claims, but I would consider revising the comment about suitability to be a comment about ease of evaluation or setup, or adding further justification for why you truly believe this is more suitable for assessing retrieval.", "theoretical_claims": "No-- no theoretical claims.", "experimental_designs_or_analyses": "I looked at the main experimental setup, comparing LegoLink to CacheBlend variants and full recomputation on performance and efficiency. I think the setup seems reasonable and well-documented.", "relation_to_broader_scientific_literature": "The paper brings attention to an interesting area of active study-- position-independent caching for efficient model serving-- and proposes a new method in this space. LegoLink has the advantage of being very simple conceptually and much faster than the prior state of the art (CacheBlend); the LegoLink-0 setting is also an interesting alternative to recomputation. I think these methods have the potential for adoption because of their low impact on performance, improvement on efficiency, and ease of integration into existing setups (strengthened by the implementation of the method to integrate with vllm workflows).", "essential_references_not_discussed": "I think more careful discussion is warranted around the idea of caching context. Line 293 says that context caching was introduced in late June 2024, but this is only the time that Gemini started supporting this feature. The related work on page 8 actually does a much better job of tracing the line of work here from caching KV values for a single inference example, to prefix caching, to modular/position-independent caching. I think this is still missing some prior works that talked about PIC in terms of individual applications, including for [RAG](https://arxiv.org/abs/2410.07590) and [long-context ICL](https://arxiv.org/abs/2405.00200); both feature encoding in local-position-only/global-position-agnostic blocks and then potentially retrieving blocks to reuse.", "other_strengths_and_weaknesses": "I've addressed strengths elsewhere in the review; I think my main concern not mentioned elsewhere is with the clarity of the framing. The paper starts as if it is fully introducing a new task of PIC and introduces a (to my knowledge) new view of PIC as analogous to the way code is pre-compiled. However, the paper then acknowledges that this problem has been studied before and instead begins framing itself as an improvement on an existing method (using LegoLink). Then, near the end, LegoLink-0 is introduced as a way to sidestep the need to do linking altogether. I think it's a good paper with a reasonable contribution, but it seems that the paper is not quite sure what story it is telling, and a revision of the narrative of the work would greatly enhance its readability and impact.", "other_comments_or_suggestions": "I would not describe tokens as \"text-based words\" (in line 26)-- I think something like \"small units of text\" is more accurate. \n\nThe notation introduced in line 69 for the computational complexity of CacheBlend is strange and makes it a bit hard to follow. Generally we exclude constant factors in big-O notation, but here I understand you are trying to distinguish complexity between full recomputation, your method, and CacheBlend; I think writing CacheBlend as $O([0.15N]N)$ and yours as $O(kN)$ would make it clearer that your contribution is reducing the \"15% of $N$\" recomputation to a static $k$. In general I think that section could use an additional pass for clarity of text.\n\nDescribing the models in 4.1.3 as \"base\" because they are not finetuned for these tasks is a bit confusing-- generally, I think of \"base\" as a distinction between instruct-tuned and non-instruct models, and you are using instruction-tuned models here. \n\nFigures are not always placed on the page where they are primarily referred to.", "questions_for_authors": "Q1. In Figure 3, the full recomputation setting still shows stronger attention at the \"chunk boundaries\"-- is this solely because the chunks are separate documents? If you use the regular softmax instead of your min-max scaling, is this a really noticable difference? (In general a fan of using softmax instead of min-max for this figure, or at least including the softmax version in the appendix.)\n\nQ2. Do you consider your main contribution to be the framing of the PICI problem (using the metaphor of software linkage), the presentation of LegoLink as an improvement on CacheBlend, or the proposal of LegoLink-0 as a 0-linking alternative?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nEjRCvdG9t", "reviewer": "Reviewer_4Fru", "summary": "Existing work accelerates LLM workload by reusing the KV cache of a text chunk when it is the prefix of the request. Existing work break the \"prefix\" limitation by dynamically finding and computing the attention for a subset of tokens. This work further accelerate existing work by only performing recomputation on a subset of tokens. Experimental results show that this work can reduce TTFT by upto 8x.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We address the questions and confusion below. \n\n> Key assumptions — attention sink.\n\nThe attention sink phenomenon is well-studied in attention sparsity research. For example, StreamingLLM [1] and DuoAttention [3] discover that only a few useful tokens receive some attention score, while the remaining useless attention score (summing to 1.0) is absorbed by the first few tokens (called sink tokens). If the sink tokens are numerous, they overshadow meaningful ones. In addition, Minference [4] describes this phenomenon as a ^-shape pattern, while more recently LightTransformer identifies lazy layers dominated by attention sink heads. \n\nBesides, a key clarification is that too many sink tokens are actually bad rather than representing important information for each chunk.\n\nRelevant related work is provided below to clarify the phenomenon of attention sink further. We hope this addresses your concern.\n\n[1] G. Xiao, Y. Tian, B. Chen, S. Han, and M. Lewis, “Efficient streaming\nlanguage models with attention sinks,” in The Twelfth International\nConference on Learning Representations, ICLR 2024, Vienna, Austria,\nMay 7-11, 2024. OpenReview.net, 2024.\n\n[2] J. Tang, Y. Zhao, K. Zhu, G. Xiao, B. Kasikci, and S. Han, “QUEST:\nquery-aware sparsity for efficient long-context LLM inference,” in Forty-\nfirst International Conference on Machine Learning, ICML 2024, Vienna,\nAustria, July 21-27, 2024. OpenReview.net, 2024.\n\n[3] G. Xiao, J. Tang, J. Zuo, J. Guo, S. Yang, H. Tang, Y. Fu, and S. Han,\n“Duoattention: Efficient long-context LLM inference with retrieval and\nstreaming heads,” in The Twelfth International Conference on Learning\nRepresentations, ICLR 2024, Vienna, Austria, May 7-11, 2024. Open-\nReview.net, 2025.\n\n[4] H. Jiang, Y. Li, C. Zhang, Q. Wu, X. Luo, S. Ahn, Z. Han, A. Abdi,\nD. Li, C. Lin, Y. Yang, and L. Qiu, “Minference 1.0: Accelerating pre-\nfilling for long-context llms via dynamic sparse attention,” in Advances in\nNeural Information Processing Systems 38: Annual Conference on Neural\nInformation Processing Systems 2024, NeurIPS 2024, Vancouver, BC,\nCanada, December 10 - 15, 2024, A. Globersons, L. Mackey, D. Belgrave,\nA. Fan, U. Paquet, J. M. Tomczak, and C. Zhang, Eds., 2024.\n\n[5] R. Chen, Z. Wang, B. Cao, T. Wu, S. Zheng, X. Li, X. Wei, S. Yan,\nM. Li, and Y. Liang, “Arkvale: Efficient generative LLM inference with\nrecallable key-value eviction,” in Advances in Neural Information Pro-\ncessing Systems 38: Annual Conference on Neural Information Processing\nSystems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15,\n2024, A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M.\nTomczak, and C. Zhang, Eds., 2024.\n\n\n> Positional embedding (PE)\n\nPICI prefills a doc, whose first token is given position 0, to generate their KV cache. Then PICI uses the cache directly without modifying PE. On the contrary, new queries receive position IDs based on their real positions. \n\nAgain, too many tokens with PE 0 at the beginning of each chunk absorb excess attention without contributing useful information. \n\nWe will add this detail in future versions.\n\n> Sliding window\n\nWe disabled the optional sliding window for the Mistral model.\n\n> Large chunk size\n\nCurrently, we chunk large documents into mid-sized segments (e.g., 512 tokens). We will add an analysis of the trade-off between chunking and processing long documents as a whole in future versions. \n\n> Source of improvement: from better token selection, or static token selection?\n\nLegoLink’s improvement comes from static token selection, specifically, the first few tokens of each chunk (except for the first chunk). These tokens are preselected for recomputation, offline before execution. \n\nThe recomputation gives these \"first few tokens\" actual position IDs, makes them realize they are not the \"first few\" tokens anymore (they are in the middle now), and stops them from being sink tokens and absorbing too much attention.", "claims_and_evidence": "The key assumption of this paper is attention sink, meaning that the first token in each text chunk will \"absorb\" the most attention. This assumption is not well-supported with empirical evidences (since this is the key assumption and it is not very well-known, I would expect some empirical evidences to prove that this is correct) and rationales.", "methods_and_evaluation_criteria": "The datasets (5 datasets from LongBench) and evaluation metrics (TTFT, Accuracy) are pretty standard and make sense.", "theoretical_claims": "There is no formal proof involved in the paper.", "experimental_designs_or_analyses": "The evaluation involves 3 models (mistral, Llama 3.1 and Yi). I am not familiar with Yi, but mistral and Llama 3.1 all contains sliding window layers. Not sure how the authors handle sliding window layer.\n\nNot sure whether the proposed method work well when the chunk size is large. But since 512 is a typical chunk size in RAG application I would say evaluating it is just a better-to-have.", "relation_to_broader_scientific_literature": "This paper can be hugely beneficial to RAG applications, which is one of the key for a lot of modern LLM applications (e.g. search results summary, code generation, etc) and will benefit the broad audience.", "essential_references_not_discussed": "Necessary references are included.", "other_strengths_and_weaknesses": "Strengths:\n* Super fast and easy to implement in real production\nWeaknesses:\n* Cannot smoothly trade-off between full recomputation and no recomputation given a fixed chunk size.\n* The key assumptions (attention sink) need more empirical backup and more rationales.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Thanks for submitting to ICML. The problem that this paper tackles is definitely important and the proposed approach is pretty effective.\n\nMy major confusion is about the attention sink assumption. Would be really nice if there are more empirical evidences or rationales. This assumption sounds to me that the cross-attention is mainly contributed by the first token in the text chunk, which seems to imply that other tokens don't really matter in terms of understanding the meaning of the text chunk.\n\nSeveral questions regarding the technical detail: how do you handle positional encoding and how do you handle sliding window layers?\n\nRegarding the evaluation: I would like to have some ablation study --- is your improvement mainly come from better token selection, or from static token selection scheme?\n\nA side question: will your solution remain effective when the text chunk size is large (say tens of thousands of tokens, e.g. a research paper).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents PICI, a serving system for LLM that overcomes the constraints of traditional prefix-based context caching by enabling position-independent caching (PIC). At its core, PICI features LegoLink, a simple yet effective linking algorithm that exploits static attention sparsity and eliminates the influence of the attention sink phenomenon in each chunk. It minimizes recomputation for accuracy recovery when using PIC.

The reviewers generally appreciate the contributions of this work, and the authors have adequately addressed the questions and concerns during the rebuttal. One major concern relates to the assumption of the "attention sink" phenomenon, which has been previously noted and studied (e.g., in Streaming LLM). The authors are encouraged to provide additional context and a more detailed explanation of this concept to enhance the paper’s clarity and readability.
Decision: Accept (poster)