PaperlayerView exact revision on arXiv

Source-linked AI summary

Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation

Shubham Agarwal, Sai Sundaresan, Subrata Mitra, Debabrata Mahapatra, Archit Gupta, Rounak Sharma, Nirmal Joshua Kapu, Tong Yu, Shiv Saini

arXiv:2502.15734v1cs.DCcs.AIcs.CLcs.LGcs.OS

TL;DR

RAG repeatedly processes retrieved chunks, but prefix caching is limited when questions change which chunks appear and in what order. Cache-Craft manages reusable chunk-caches and selectively recomputes KV values to preserve output quality. It reduces GPU computation costs versus prefix caching and improves throughput and response latency in continuous batching.

  • Problem

    RAG prefix caching has limited reuse as the retrieved chunks and their order vary, while caching ordered chunk tuples becomes less reusable and can require prohibitive memory.

    Source: §2.4 · pp. 3–4

  • Method

    Cache-Craft identifies reusable chunk-caches, selectively recomputes KV values to fix them across contexts, and manages caches to prioritize likely reuse.

    Source: §1 · p. 2, §3.2 · p. 6

  • Results

    51% lower GPU computation costs than prefix-caching; under continuous batching, throughput improved 1.6× and latency fell 2.1× for LLaMA-3-8B and 2× for LLaMA-3-70B.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Cache-Craft provides speedups without compromising quality on real production workloads and popular RAG datasets.

    Source: §8 · p. 13

    Prefix-cache reuse density drops as ordered chunk-tuple length increases, and the combinatorial number of possible tuples makes its memory footprint prohibitive.

    Source: §2.4 · pp. 3–4

Abstract

from arXiv · show

Retrieval-Augmented Generation (RAG) is often used with Large Language Models (LLMs) to infuse domain knowledge or user-specific information. In RAG, given a user query, a retriever extracts chunks of relevant text from a knowledge base. These chunks are sent to an LLM as part of the input prompt. Typically, any given chunk is repeatedly retrieved across user questions. However, currently, for every question, attention-layers in LLMs fully compute the key values (KVs) repeatedly for the input chunks, as state-of-the-art methods cannot reuse KV-caches when chunks appear at arbitrary locations with arbitrary contexts. Naive reuse leads to output quality degradation. This leads to potentially redundant computations on expensive GPUs and increases latency. In this work, we propose Cache-Craft, a system for managing and reusing precomputed KVs corresponding to the text chunks (we call chunk-caches) in RAG-based systems. We present how to identify chunk-caches that are reusable, how to efficiently perform a small fraction of recomputation to fix the cache to maintain output quality, and how to efficiently store and evict chunk-caches in the hardware for maximizing reuse while masking any overheads. With real production workloads as well as synthetic datasets, we show that Cache-Craft reduces redundant computation by 51% over SOTA prefix-caching and 75% over full recomputation. Additionally, with continuous batching on a real production workload, we get a 1.6X speed up in throughput and a 2X reduction in end-to-end response latency over prefix-caching while maintaining quality, for both the LLaMA-3-8B and LLaMA-3-70B models.

1 Introduction

Cache-Craft targets redundant RAG prefill computation: retrieved chunks are repeatedly processed, while prefix caching often misses because questions change chunk sets and ordering. It reuses chunk-level KV caches with selective recomputation and cache management; evaluations report lower GPU costs and faster continuous-batching service than prefix caching.

1 Introduction

  • Long RAG inputs make prefill a bottleneck: it grows quadratically with input-context length and accounts for up to 77% of Sys-X inference time.For LLaMA-3-70B on four A100-80GB GPUs, prefill reached 76 seconds for 32k-token sequences at batch size 8; production prefill can exceed 100 seconds.Source: §1 · p. 1
  • In Sys-X, 75% of retrieved chunks for a query were reprocessed, totaling over 12B tokens in a month.The paper estimates processing those tokens would require 9,600 GPU hours on LLaMA-3-70B using eight A100 GPUs, costing approximately $50k.Source: §1 · p. 1
  • Prefix caching applies to only 8% of production requests and 18% of prefill tokens; arbitrary cache reuse also risks quality loss and must avoid memory-transfer overheads.Small question variations can change retrieved chunks and their ordering, while GPU memory must also hold model parameters and growing decode KV caches.Source: §1 · pp. 1–2
  • Cache-Craft reuses chunk-caches across altered prefixes, selectively recomputes contextualized tokens, and prioritizes chunks by reuse potential and expected workload frequency.The system manages cache loading and storage to mask overheads while reducing GPU computation and time-to-first-token latency.Source: §1 · p. 2
  • 51% lower GPU computation costs than prefix-caching; with continuous batching, throughput rose 1.6× for both models, while response latency fell 2.1× (LLaMA-3-8B) and 2× (LLaMA-3-70B).With 30% of tokens recomputed, the system maintained 90% of the base ROUGE F1 score on average.Source: §1 · p. 2
  • The implementation integrates Cache-Craft into vLLM, and the paper evaluates it on production workloads and six other datasets, with a human-evaluation study and sensitivity studies.The implementation incorporates FlashAttention and PagedAttention optimizations.Source: §1 · p. 2

2 Background and Motivation

RAG prefill dominates measured computation and latency, while repeated chunk retrieval offers opportunities for reuse. But ordered-prefix scarcity and context-dependent KV values make reliable reuse difficult.

2.1 Preliminaries of LLM

  • LLM prefill computes prompt hidden states and KV pairs, while decode reuses cached KVs; prefix caching instead reuses previously computed context matching an input prefix.The paper describes transformer hidden states as progressively contextualized embeddings across layers.Source: §2.1 · pp. 2–3

2.2 Prefill Dominates Decode in RAG

  • For the three analyzed systems, prompts average 30k prefill tokens versus 600 decode tokens, and retrieved chunks contribute 60%–98% of Sys-X prompt tokens.The token imbalance is attributed to the extra retrieved chunks beyond the user’s question.Source: §2.2 · p. 3
  • For Sys-X, Sys-Y, and LMSys, prefill accounts for 55.4%, 76%, and 22% of total time and 19.3x, 46x, and 4.4x decode operations, respectively.Across the three systems, the analysis finds that prefill typically dominates both token computation and total latency.Source: §2.2 · p. 3

2.3 Evidences of Chunk-Reuse

  • The top 5% of chunks are accessed by 60% of requests in Sys-X and MuSiQue and 40% in 2wikiMQA; 94% of Sys-X chunk reuse is across users.In Sys-X, reuse within a session is 55% and across sessions is 67%.Source: §2.3 · p. 3

2.4 Why Cache-Reuse is non-trivial?

  • Prefix-cache reuse requires the same ordered k-tuple of chunks, but individual chunks are retrieved repeatedly and could have higher hit rates when reused at any position.The paper defines reuse density as the number of ordered k-tuples observed in previous requests and reports that it drops significantly as k increases.Source: §2.4 · pp. 3–4
  • At k=5, prefix-cache reuse density falls as low as 5, and caching enough ordered tuples for high reuse makes the memory footprint prohibitive.The observed 5-tuple hit-rate distribution is low and does not follow a power law.Source: §2.4 · pp. 3–4
  • Chunk contextualization changes with prefix chunks, while chunk ordering affects it through causal attention and positional embeddings.A chunk may have stored KV-caches from different requests and positions; the contextualization grows with more prefix chunks.Source: §2.4 · p. 4
  • Naively reusing all five chunks from five distinct past requests produces a 50% drop in F1 score.For most Sys-X and 2wikiMQA requests, the five retrieved chunks appeared across three past requests; finding all five in one past request was uncommon.Source: §2.4 · p. 4

3 Cache-Craft Design

This section describes Cache-Craft’s offline and online management of reusable RAG chunk-caches, including metadata, cached-version selection, targeted recomputation, and cache lookup, storage, and loading. It also presents layer-wise preloading to eliminate prefill wait time, motivated by production requests concentrating on a stable subset of chunks that can fit in GPU memory.

3.1 Determining Cache Reusability

  • Cache-Craft’s reusability measures combine prefix overlap with an order penalty based on normalized Kendall’s Tau, then assess how much a chunk’s KV depends on its prefix versus its own tokens.A high Cache Context Impact (CCI) signals stronger outside-context influence and lower reuse potential unless the prefix context matches closely.Source: §3.1 · pp. 5–6

3.2 Fixing Chunk-Cache via Recomputation

  • Cache fixing recomputes only the KV values needed to make a reused cache mimic uncached output, with Cache Fix Overhead (CFO) estimating the required token fraction.The scaling parameter α is selected on validation data to balance recomputation against a desired F1 score; the system targets the top ⌈CFO(C_i) · |C_i|⌉ tokens by inter-attention.Source: §3.2 · p. 6, §3.2.1 · p. 6

3.2.2 Adaptive Early Recomputation Termination.

  • About 55% fewer tokens are recomputed while maintaining similar output quality by stopping recomputation for unfocused chunks once question attention identifies focused chunks.For approximately 80% of LLaMA-3-8B queries, focused chunks can be detected between layers 10 and 15.Source: §3.2.2 · p. 6

3.3 Cache Variants: Retrieval and Eviction

  • Cache-Craft stores multiple variants per chunk, selects the variant with the lowest CFO, and evicts caches with the lowest frequency-reuse score when storage is full.Its N and M capacity choices depend on cache popularity and reusability, the RAG setting, hardware memory and interconnects, and LLM deployment configuration.Source: §3.3 · p. 7

3.4 Chunk-Cache Reuse Pipeline

  • The reuse pipeline plans cache retrieval or computation per chunk, overlaps layer-wise cache loading with prefill and KV recomputation, and applies updated rotary positions to merged cached and new KVs.When loading exceeds prefill time, it preloads multiple layers to minimize execution gaps; in the given five-layer example, preloading three layers eliminates gaps at a prefill-to-load ratio of 1:2.Source: §3.4.1 · p. 7, §3.4.2 · p. 7, §3.4.3 · p. 8

3.5 Hierarchical Chunk-Cache Management

  • Cache-Craft tiers caches across GPU HBM, CPU memory, and SSD, asynchronously preloading them while requests wait and falling back to prefill from scratch when a cache is not ready.For five Sys-X RAG chunk-caches, loading takes 0.03s from CPU or 0.59s from SSD, while typical queue wait is 0.32s and can mask loading delay under higher loads.Source: §3.5 · p. 8
  • Layer-wise preloading of chunk-caches into GPU memory is intended to eliminate wait time during prefill execution.Source: Figure 19 · p. 8
  • Over 1 month in Sys-X, 85% of requests hit 13.5% of chunks; by 3 months, 85% still accessed just 14.8% of chunks.Chunk accesses rose from 20.6% to 24% over that period.Source: §3.5 · p. 8
  • Sys-X’s stable, highly reused chunks total 119 GB for LLaMA-3-70B, fitting within the 135 GB free GPU memory budget.The budget corresponds to LLaMA-3-70B hosted on 4 A100-80GB GPUs with Tensor-Parallelism; the design aims to handle future chunk-cache growth.Source: §3.5 · p. 8

4 Implementation

Cache-Craft combines chunk-granular cache storage, runtime positional-embedding adjustment, and selective prefill recomputation to reuse chunk-caches across requests.

4 Implementation

  • Independent per-chunk hashes map chunks to 16-token memory blocks, with tiered address pointers and padding for variable chunk sizes.The hash table allows direct chunk access without dependence on prior context.Source: §4 · p. 8
  • For batch requests sharing chunk positions, RPE is applied before attention and removed after decoding; differing positions integrate RPE into attention.Source: §4 · pp. 8–9
  • Selective recomputation uses a modified Triton flash-attention kernel for selected cached-chunk tokens and new question tokens, then injects corrected KVs for decoding.After decoding, the updated cache is asynchronously swapped with the original to prevent cache corruption.Source: §4 · p. 9

5 Evaluation

The evaluation tests Cache-Craft across production and benchmark RAG workloads, comparing quality, computation, and serving performance against cache-reuse and context-compression baselines. Results show improved quality-efficiency trade-offs and faster serving under the reported conditions.

5.1 Experimental Set up

  • Cache-Craft is evaluated on LLaMA-3 8B and 70B; an exact-prefix cache offers perfect accuracy but low reuse potential, while Set-Cache provides higher reuse with lower accuracy.Source: §5.1.1 · p. 9, §5.1.4 · p. 9

5.2.1 Evaluation of Recomputation Strategy

  • With LLaMA-3-8B, 20% and 30% recomputation improve multi-hop ROUGE by 30% and 42%, while higher recomputation brings results within 1–5% of Full-Recomp across datasets.The reported improvement trend also holds across single-hop QA and summarization, with approximately 20–35% improvements for both model sizes.Source: Figure 20 · p. 10, §5.2.1 · p. 10
  • Contextualized recomputation beats random and high-attention token selection; short-QA and True/False ROUGE reaches 0.87 versus 0.59 for Full-Cache.Prefix-Cache computes 80–95% of tokens regularly, while Set-Cache saves 15–35% but has lower ROUGE from incorrect contextualization.Source: Figure 21 · p. 10, §5.2.1 · p. 10

5.2.2 Comparison with Prompt Compression Techniques

  • At 30% recomputation, Cache-Craft scores around 0.9 ROUGE-F1 versus 0.4 for Lingua2 and 0.5 for MapReduce; Sys-X scores are 0.87 versus 0.56 and 0.61, respectively.In the user study, Cache-Craft received 71% on 2wikiMQA and 79% on SQuAD, versus 30% and 53% for Full-Cache.Source: Table 1 · p. 10, §5.2.2 · p. 10, Table 2 · p. 10

5.3 Performance Evaluation in Deployment

  • With 30% recomputation, continuous batching yields 1.6× throughput speedup and 2.1× lower response latency for LLaMA-3-8B, and 1.6× and 2×, respectively, for LLaMA-3-70B.The reported setting maintains 90% of base ROUGE F1 on average; layer-wise preloading also reduces SSD loading overhead to 0.12s.Source: Figure 22 · p. 11, §5.3.1 · p. 11, §5.3.2 · p. 11

5.4 Controlled Evaluations for TTFT

  • On Sys-X, Cache-Craft achieves about 2.5× TTFT speedup over Prefix Cache on LLaMA-3 8B, recomputing 39% of tokens while retaining 90% of original quality; it also cuts 99th-percentile TTFT 3× and average token computation 51% versus Prefix-Cache.On average, only 18% exact prefix match occurs for Sys-X requests.Source: §5.4 · pp. 11–12
  • At batch size 4 and 8,192 tokens, Cache-Craft reduces TTFT by 1.6× versus Full-Recomp for LLaMA-3-8B and 2.3× for LLaMA-3-70B.For LLaMA-3-8B at 16k tokens, it is 1.7× faster than Full-Recomp and outperforms the other tested baselines across sequence lengths.Source: Figure 23 · p. 12, §5.4.2 · p. 12

6 Ablations and Discussions

The ablations examine positional and causal corrections, recomputation choices, and context-size effects. They also connect chunk-cache reuse to RAG workload characteristics and serving latency.

Design Components in Cache-Craft

  • Removing β raises recomputation to 54% without improving quality, disabling focus chunking raises it to 70% with minimal gains, and random selection without CCI yields 0.73 ROUGE.The reported Full-Cache baseline with fixed RPE scores 0.665.Source: §6 · p. 12, Figure 26 · p. 13
  • Quality rises from 0.825 at α=0.5 to 0.953 at α=3, with diminishing returns as recomputation increases.The intermediate scores are 0.896 at α=1 and 0.94 at α=2.Source: §6 · p. 12, Figure 26 · p. 13

Context Size (Number of Chunks vs. Chunk Size)

  • With larger chunks, ROUGE-F1 rises and stabilizes around 0.92; with more chunks it reaches about 0.91 before slightly declining after saturation.Disabling focused-chunk filtering keeps quality stable, indicating the decline is attributed to errors from that selection mechanism.Source: §6 · p. 12, Figure 27 · p. 13

Approximation (Position vs. Causal)

  • With 30% recomputation, Cache-Craft scores 0.896 ROUGE versus 0.665 for Full-Cache; fixing causality alone scores 0.22, while fixing neither position nor causality scores 0.15.The comparison shows the reported benefit of combining correct positional encoding with selective recomputation.Source: Table 3 · p. 13, §6 · p. 13

Why caching chunks is acceptable in practice?

  • For large Sys-X chunks over 883 tokens, intra-attention averages 2.18× inter-attention, and only 23% of chunks are highly contextualized; Cache-Craft gets 0.87 ROUGE with 20% recomputation.The user study reports 78.9% acceptance for Cache-Craft versus 83.7% for exact-computation vLLM.Source: §6 · p. 13
  • At high load, TTFT reaches 35s for LLaMA-3-70B on four A100 GPUs, and its share of overall response latency increases with system load.Cache-Craft stores chunks independently, allowing reuse in different combinations and higher cache hit rates than prefix caching.Source: §6 · p. 13

7 Related Works

The related-work discussion situates Cache-Craft among serving, context-compression, KV-cache, and approximation techniques, distinguishing its RAG-oriented chunk-cache reuse from prior approaches.

LLM Serving Efficiency

  • LLM-serving work covers SLOs, memory optimization, parallelism and batching, and KV-computation improvements using model sparsity.The cited work groups include [14, 15, 31, 67],, [34, 79, 81], and.Source: §7 · p. 13

Context Compression and KV Cache Reduction

  • Context-reduction approaches compress prompts or drop tokens, while most KV-reuse methods assume prefix matches, which the paper characterizes as impractical for RAG systems.Prompt Cache supports reuse at different positions but is described as struggling with positional encoding and cross-attention accuracy.Source: §7 · p. 13

KV Cache Quantization and Management

  • The paper describes Cache-Craft as enabling KV-cache reuse for RAG without compromising quality, and says quantization and KV-cache management techniques can complement it.The discussion also places controlled KV-cache approximation alongside approximation methods in other systems domains.Source: §7 · p. 13

8 Conclusion

The conclusion presents Cache-Craft as a chunk-cache management system for RAG and reports that it provides speedups without compromising quality across production workloads and popular RAG datasets.

Conclusion

  • Cache-Craft manages precomputed states corresponding to knowledge-base chunks for RAG.The conclusion describes the system as efficiently managing those states.Source: §8 · p. 13
  • The paper reports in-depth analyses of production workloads that identify opportunities for chunk-cache reuse and technical challenges.Source: §8 · p. 13
  • The conclusion attributes its reported speed-up without quality compromise to reusable-chunk identification, selective recomputation, and cache-management policies.The stated scope includes real production workloads and popular RAG datasets.Source: §8 · p. 13

Related papers

Loading 2502.15734v1…