💻 computer science

CachePrune: Privacy-Aware and Fine-Grained KV Cache Sharing for Efficient LLM Inference

CachePrune is a privacy-aware mechanism for Large Language Model inference that enables fine-grained, token-level sharing of Key-Value cache entries to eliminate side-channel leakage while significantly improving cache hit rates and reducing time-to-first-token compared to existing coarse-grained or sharing-disabled approaches.

Original authors: Guanlong Wu, Zhaohan li, Yao Zhang, Zheng Zhang, Jianyu Niu, Ye Wu, Yinqian Zhang

Published 2026-05-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Guanlong Wu, Zhaohan li, Yao Zhang, Zheng Zhang, Jianyu Niu, Ye Wu, Yinqian Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, super-smart library (the Large Language Model or LLM) that helps people write stories, answer questions, and solve problems. To work fast, this library keeps a "scratchpad" (called the KV Cache) of everything it has already read and thought about. If two people ask similar questions, the library can skip re-reading the common parts and just look at its scratchpad, saving a huge amount of time and energy.

However, there's a problem: Privacy.

The Problem: The "Echo" in the Library

If the library lets everyone share the same scratchpad, a sneaky thief (an adversary) could try to guess what you wrote.

How? The thief asks the library a question. If the library answers super fast, it means the library recognized part of the question from your previous request and reused its scratchpad.
The Risk: By timing how fast the library answers different questions, the thief can figure out exactly which words you used, even if they weren't supposed to see them.

The Old Fix: To stop this, the library's managers decided to stop sharing the scratchpad entirely between different people. It's safe, but it's slow and wasteful because the library has to re-read everything from scratch every time.

The New Solution: CachePrune

The authors of this paper built a new system called CachePrune. Think of it as a smart librarian with a red marker.

Instead of throwing away the whole shared scratchpad just because one person wrote a secret, the librarian does something much smarter:

The Red Marker (Privacy Detection): The librarian scans your request and puts a red "DO NOT SHARE" sticker on any sensitive words (like your name, credit card number, or private secrets).
The Scissors (Fine-Grained Cutting): The librarian cuts the request into tiny pieces.
- The pieces with red stickers are thrown into a private bin (they are never shared).
- The pieces without stickers (like "Hello," "Please write a story about," or "The weather is") are kept in the shared scratchpad.
The Puzzle Solver (Smart Retrieval): When a new person comes in, the librarian doesn't just look for big, pre-cut blocks of text. They look for exact matches of the safe, sticker-free pieces, no matter where they appear in the sentence.

Why This is a Big Deal (The Analogy)

Imagine you are baking a cake with a friend.

The Old Way (All-or-Nothing): If you whisper a secret to your friend while baking, the whole kitchen is considered "contaminated." You can't share the recipe or the tools with anyone else ever again. You have to buy new tools and start over.
The CachePrune Way: You wear a special apron. You whisper your secret, and the apron catches it. The rest of the kitchen (the flour, the eggs, the mixing bowl) is perfectly clean. You can share the clean tools with the next baker immediately. You save time, but your secret stays safe.

How It Works Under the Hood

The paper explains two tricky technical challenges they solved to make this possible:

Finding the Safe Pieces: It's hard to know exactly which parts of a sentence can be reused without messing up the meaning. The system uses a mathematical trick (called a "summed-area table") to quickly scan the sentence and find the longest, safest chunks that don't rely on the secret words.
Finding the Pieces Fast: Since the safe chunks can be any length (not just fixed blocks), finding them is like searching for a needle in a haystack. The system uses a "rolling hash" (like a sliding window) to scan through requests incredibly fast, checking for matches in milliseconds.

The Results

The authors tested this system on a real library (using the vLLM software) with three different types of tasks (answering questions, reading stories, and summarizing meetings). Here is what they found:

Privacy: The "thief" could not guess any of the secret words. The "Direct Recovery" rate was 0%. Even guessing the meaning from the context was very difficult (less than 7% success).
Speed: Because they could share the safe parts, the system was 4.5 times faster at starting to answer a question compared to the old "no-sharing" method.
Quality: The answers were just as good as if the system had read everything from scratch.
Efficiency: Even without any privacy rules, this new "cutting" method was 44% better at reusing work than previous methods that only used fixed-size blocks.

Summary

CachePrune is a system that lets AI servers share their "memory" to work faster, but it acts like a smart filter. It automatically hides sensitive information before sharing, allowing the safe parts to be reused instantly. This breaks the old rule that you had to choose between speed and privacy; now, you can have both.

Technical Summary: CachePrune

Problem Statement

Large Language Models (LLMs) rely on Key-Value (KV) caching to accelerate inference, and modern serving systems often share KV caches across different users to reduce redundant computation and memory usage. However, unrestricted cross-user sharing introduces significant side-channel vulnerabilities. Adversaries can probe the system with specific token sequences; if the system reuses cached KV entries (detected via reduced latency or scheduling priority), the adversary can infer the presence of those tokens in a victim's prompt, potentially reconstructing sensitive inputs.

Current defenses typically disable cross-user sharing entirely to prevent leakage. This "all-or-nothing" approach is overly coarse-grained. In practice, user prompts contain substantial privacy-irrelevant content (e.g., system instructions, public templates, or retrieved passages in RAG pipelines), where sensitive tokens (like PII) often constitute a tiny fraction of the total input (e.g., ~2.3% of user input). Disabling all sharing sacrifices significant efficiency gains. Furthermore, existing fine-grained sharing mechanisms (e.g., CacheBlend, CacheCraft) operate at fixed chunk levels (e.g., 512 tokens). If a single sensitive token falls within a chunk, the entire chunk must be discarded, leading to substantial loss of reusable content.

Methodology: CachePrune

The authors propose CachePrune, a privacy-aware KV cache sharing mechanism that enables fine-grained, token-level reuse of non-sensitive KV entries. The system is designed to break the trade-off between privacy and efficiency by selectively sharing only privacy-irrelevant segments.

System Architecture

CachePrune integrates five core components on top of existing frameworks like vLLM:

Sensitivity Detector: A pluggable interface (supporting user-defined rules, regex, or classifiers like Presidio) that identifies sensitive tokens in a prompt and generates a binary sensitivity mask.
KV Annotator: Post-inference, this module analyzes the attention score matrix to derive reusable segments from the non-sensitive tokens. It identifies "self-contextualized" segments where intra-attention exceeds inter-attention.
KV Retriever: Before generating a response, this module searches the KV Pool for segments matching the incoming request's non-sensitive tokens using a rolling-hash-based algorithm.
LLM Engine: Completes the inference by computing missing KV entries and recomputing specific tokens within reused segments to maintain generation quality.
KV Pool: Stores and indexes reusable KV segments, managing their lifecycle and eviction.

Key Algorithmic Solutions

The system addresses two primary challenges:

1. Efficiently Deriving Reusable KV Segments (Challenge 1)

Problem: Determining reusability at the token level requires evaluating attention dependencies for arbitrary substrings. A naive approach checking all substrings against the attention matrix results in $O(n^4)$ complexity, which is prohibitive.
Solution: CachePrune employs a summed-area table (integral image) algorithm on the attention score matrix. This allows the system to compute intra- and inter-attention sums for any candidate substring in $O(1)$ time after an $O(n^2)$ preprocessing step. This reduces the overall complexity of finding optimal reusable segments to $O(n^2)$ .
Recomputation Strategy: Within a reusable segment, tokens with high inter-attention (dependence on outside context) are marked for recomputation to preserve output quality.

2. Efficiently Retrieving Variable-Length Segments (Challenge 2)

Problem: Unlike fixed-size chunks, token-level sharing produces variable-length segments. Direct hash lookups fail because a single-token shift breaks alignment, making retrieval a substring containment problem with $O(n \times m)$ complexity for naive search.
Solution: The system uses a rolling-hash-based retrieval algorithm.
- Prefix Filtering: It precomputes hashes for the first 128 tokens of cached segments. Incoming requests are scanned with a sliding window to find potential matches in $O(n)$ time.
- Full Verification: Candidates undergo a fast prefix-hash check followed by a cryptographic hash (SHA-256) verification to ensure correctness without token-by-token comparison.

Key Contributions

First Practical Fine-Grained Sharing System: CachePrune is the first system to enable selective KV cache sharing at the token level, effectively breaking the privacy-efficiency trade-off by reusing non-sensitive entries while blocking sensitive ones.
Algorithmic Innovations: The paper introduces an adaptive algorithm using summed-area tables for efficient segment derivation and a rolling-hash mechanism for variable-length retrieval, overcoming the limitations of fixed-chunk approaches.
Comprehensive Evaluation: The authors implement CachePrune on vLLM and evaluate it across three datasets (QASPER, NarrativeQA, QMSum) and multiple models (Mistral-7B, Qwen2.5).

Results

The evaluation demonstrates that CachePrune achieves significant efficiency gains without compromising privacy or generation quality:

Privacy:
- Direct Leakage: Tokens marked as sensitive cannot be recovered via reuse-based side channels (0% exact recovery rate).
- Contextual Leakage: Inference of sensitive content from non-sensitive tokens remains limited (2.2% exact and 6.4% semantic recovery under SOTA attacks).
- Imperfect Detection: The system is robust to detection errors; false negatives increase direct leakage, while false positives conservatively reduce contextual leakage.
Efficiency:
- TTFT Reduction: CachePrune reduces Time-to-First-Token (TTFT) by up to 4.5x compared to non-sharing baselines.
- Hit Rates: It achieves up to 94.57% KV cache reuse.
- Fine-Grained Advantage: Even without privacy constraints, CachePrune's token-level sharing improves cache hit rates by 44% compared to state-of-the-art fixed-chunk methods (CacheCraft, CacheBlend, EPIC).
Quality: Generation quality (measured by F1-score and ROUGE-L) remains comparable to full recomputation, with negligible deviation.

Significance and Claims

The paper claims that CachePrune provides a practical foundation for secure LLM serving in multi-tenant environments. By moving beyond fixed-size chunking, it maximizes the reuse potential of privacy-irrelevant content (such as system prompts and public data) while strictly isolating sensitive user inputs. The authors emphasize that their approach does not require new privacy detection mechanisms but rather integrates with existing ones to provide a unified interface for secure, high-performance inference. The work highlights that fine-grained KV management is not only feasible but essential for balancing the competing demands of privacy and efficiency in modern LLM infrastructure.