🤖 AI

KVBoost: Chunk-Level Key-Value Cache Reuse with Deviation-Guided Recomputation for Efficient Large Language Model Inference

KVBoost is a chunk-level Key-Value cache reuse system that employs a dual-hash keying scheme and deviation-guided recomputation strategies to enable efficient, position-agnostic inference acceleration for large language models, achieving significant latency reductions without compromising accuracy.

Original authors: Srihari Unnikrishnan

Published 2026-08-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Srihari Unnikrishnan

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

Large language models, the powerful computer programs that can write stories, solve problems, and answer questions, rely on a specific way of processing information to understand context. When these models read a prompt, they do not just look at the current word; they build a mental map of everything that came before it to understand how the pieces fit together. This map, known as a key-value cache, is essential for the model to function correctly, but creating it is computationally expensive. Every time a user sends a request, the model traditionally has to rebuild this entire map from scratch, even if the request contains text it has seen before. In many real-world situations, such as when a user asks multiple questions about the same document or when a system uses a standard introduction for every conversation, this repeated rebuilding is a massive waste of time and energy. The central challenge for engineers has been how to save this work without losing the accuracy of the model's answers.

A researcher named Srihari Unnikrishnan has developed a system called KVBoost to solve this specific problem. The system is designed to recognize and reuse parts of the mental map that the model has already created, but it does so in a way that is much more flexible than previous methods. Older systems could only save work if the repeated text appeared at the very beginning of a request. If the shared text was buried in the middle of a long paragraph or appeared after a unique question, the system would ignore it and start over. KVBoost changes this by breaking the text into small, manageable chunks. It treats each chunk like a distinct piece of a puzzle that can be stored and retrieved independently, regardless of where it sits in the overall sentence structure. This allows the system to skip the heavy lifting of re-creating the mental map for any chunk of text that has been seen before, even if it appears in a completely different order or context.

However, simply pasting together pre-made pieces of a mental map creates a new problem. When two chunks are joined, the model might lose the subtle connections between the end of one chunk and the start of the next, leading to errors in how it understands the flow of the story. To fix this, the system employs a clever repair strategy. It identifies the specific points where the chunks meet and recalculates only the most critical parts of the connection, rather than re-doing the entire calculation. This approach is guided by a method that measures how much the model's understanding deviates from what it should be, allowing it to focus its effort only where it is truly needed. The result is a system that can stitch together a complete, accurate understanding of a prompt using mostly pre-computed pieces, with only a tiny fraction of the work required to fix the seams.

The effectiveness of this system was tested using a model with three billion parameters on a standard graphics card, processing a thousand different examples of a bug-localization task where a computer must find errors in code. In these tests, the new system was able to produce the first word of its answer nearly four and a half times faster than the traditional method of starting from scratch. When compared to the best existing method for saving work, which only works for text at the very start of a prompt, KVBoost was sixteen percent faster on average. Crucially, this speed did not come at the cost of quality; the system maintained an accuracy rate of ninety-nine point two percent, which was statistically indistinguishable from the slower, full-recomputation method. The system also proved capable of handling long contexts efficiently, with the speed advantage growing as the length of the text increased, reaching nearly five times faster for very long inputs.

Beyond just speed, the system is designed to be practical for real-world use. It includes features that allow it to store these pre-computed chunks on a computer's hard drive if the memory is full, ensuring that the cache remains useful even when dealing with massive amounts of data. It also uses a technique to compress the stored information, reducing the space it takes up without sacrificing the quality of the answers. The research confirms that by decoupling the content of the text from its position, it is possible to achieve significant efficiency gains in how these models operate. The findings suggest that the rigid requirement for shared text to be at the beginning of a prompt is no longer necessary, opening the door for much faster and more efficient interactions with artificial intelligence in scenarios where shared information appears anywhere within a conversation.

Technical Summary: KVBoost: Chunk-Level KV Cache Reuse with Deviation-Guided Recomputation

1. Problem Statement

Transformer-based Large Language Models (LLMs) incur significant latency during the prefill phase (processing the full prompt before decoding) because Key-Value (KV) tensors must be recomputed for every token. While existing systems like vLLM and SGLang utilize prefix caching to reuse KV tensors for shared leading prefixes, this approach fails in realistic deployment scenarios where shared content (e.g., system prompts, retrieved documents, few-shot examples) appears at arbitrary positions within a prompt rather than strictly at the beginning.

When shared text is interleaved with unique request-specific content, prefix caching yields no benefit, forcing the model to waste compute resources recomputing identical KV tensors. Furthermore, simple chunk-level reuse introduces two critical technical challenges:

Seam Errors: When independently cached chunks are concatenated, tokens at the boundaries lack cross-chunk attention context, leading to attention score inaccuracies.
RoPE Position Collision: Rotary Positional Embeddings (RoPE) bake absolute position rotations into KV tensors. Reusing a chunk cached at position $0$ for position $1000$ without correction results in invalid attention scores.

2. Methodology: KVBoost System

KVBoost is a chunk-level KV cache reuse system designed for HuggingFace-compatible decoder models. It operates as a seven-phase pipeline: tokenization/chunking, cache lookup, prompt assembly, seam repair, forward pass, cache population, and decoding.

2.1 Dual-Hash Keying Scheme

To resolve the RoPE collision problem and enable reuse regardless of position, KVBoost assigns each chunk two hash identifiers:

Prefix Hash (Positional + Contextual): Computed as a rolling hash of the chunk's token IDs and the previous chunk's prefix hash. This ensures exact matches only occur when both content and preceding context are identical, allowing for direct reuse of RoPE-rotated keys.
Content Hash (Position-Independent): Computed solely from the chunk's token IDs. This enables approximate matches for identical content appearing at different positions. Matches via this hash are flagged for mandatory repair because the cached RoPE rotations are incorrect for the new position.

2.2 Seam Repair Strategies

To correct the attention boundary errors (seam errors) arising from stitching independent chunks, KVBoost implements two strategies:

SelectiveRecompute: A spatial strategy that re-encodes a fixed window of tokens (default 16) immediately preceding and including each chunk seam. This restores local cross-chunk attention.
CacheBlendRecompute: A deviation-guided strategy inspired by CacheBlend [9]. It performs a "probe pass" using the assembled (stale) KV cache to measure the cosine deviation of each token's KV tensor against what a full-context pass would produce. It then selectively recomputes only the top $\rho$ (e.g., 15%) of tokens with the highest deviation. This strategy is mandatory for all content-hash (approximate) matches to correct systematic RoPE errors.

2.3 System Enhancements

Adaptive Chunking: Supports fixed, semantic (sentence/paragraph boundaries), and document-level chunking. It includes an adaptive boundary splitting mechanism that nudges chunk boundaries to the nearest punctuation token within a window to improve linguistic coherence.
KV Quantization: Implements asymmetric KIVI-style quantization (int8/int4), applying per-channel quantization to keys and per-token quantization to values to reduce memory footprint.
Memory Management: Utilizes an importance-weighted LRU eviction policy, scoring chunks by the $\ell_2$ norm of their KV tensors. It also features an optional disk-tier overflow cache using memory-mapped files for cold storage.
Attention Sink & Overlap: Injects attention-sink tokens and overlap tokens during cache population to improve boundary token fidelity.

3. Key Contributions

The paper outlines eight primary contributions:

A dual-hash keying scheme separating positional and content identity, enabling both exact and approximate reuse.
Two seam-repair strategies: fixed-window SelectiveRecompute and deviation-guided CacheBlendRecompute.
An importance-weighted LRU eviction policy using per-chunk KV tensor norms.
Implementation of asymmetric KIVI-style quantization (int8/int4) for cached chunks.
Adaptive chunk boundary splitting to align with natural linguistic seams.
Overlap and attention-sink token injection to enhance boundary fidelity.
A two-tier storage architecture combining in-memory hot storage with optional disk overflow.
A complete, open-source implementation compatible with any RoPE-based HuggingFace model without model surgery.

4. Experimental Results

The system was evaluated on Qwen/Qwen2.5-3B using a 1,000-sample bug-localization benchmark involving shared code contexts and multiple-choice questions.

Latency (TTFT): KVBoost achieved a 4.49× mean speedup in Time-to-First-Token (TTFT) compared to full recomputation (142.4 ms vs. 639.1 ms). It was 16% faster than vLLM prefix caching (142.4 ms vs. 165.5 ms). The speedup over vLLM was most pronounced in short contexts (1.53× in the 0–500 token bucket) where shared content often appears non-lexically.
Output Quality: KVBoost maintained 99.2% exact-match accuracy, comparable to the baseline (99.1%) and vLLM (99.1%). This confirms that the seam repair pipeline introduces no detectable quality regression.
Cache Reuse: While vLLM achieved a slightly higher mean reuse ratio (39.5% vs. 36.4%), this is because KVBoost operates at the chunk level and requires at least one chunk boundary to align for a cache hit, whereas vLLM's prefix caching can match at arbitrary token granularity. Despite the lower mean reuse ratio, KVBoost achieves lower overall TTFT by avoiding PagedAttention per-page overhead and utilizing aggressive seam-repair strategies.
Memory: Peak GPU memory usage was nearly identical to the baseline (a marginal 0.24% reduction), as the primary benefit is skipping recomputation rather than reducing peak allocation.

5. Significance and Claims

The paper claims that KVBoost provides a production-ready, memory-bounded inference acceleration layer that extends the benefits of KV caching to the broad class of prompts encountered in real-world deployments, where shared content is rarely confined to a leading prefix.

The core insight is that the position of content within a prompt should not determine its reusability. By decoupling content identity from positional identity via dual hashing and providing principled repair mechanisms (specifically CacheBlendRecompute) for the resulting boundary artifacts, KVBoost overcomes the limitations of prefix caching. The system is designed to integrate seamlessly with existing RoPE-based models without requiring architectural changes ("model surgery"), making it a practical solution for reducing prefill latency in RAG systems, multi-turn conversations, and batched document processing.