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

Large language models spend a significant amount of time recomputing key‑value (KV) tensors during the prefill stage, especially when serving many requests that share only parts of a prompt. Most existing caching approaches require the shared portion to sit at the very beginning of the input, which limits their usefulness when the overlap occurs elsewhere. KVBoost proposes a chunk‑level reuse strategy that decouples positional information from content, allowing cached KV blocks to be reused no matter where they appear in a new request.

What You Need to Know

KVBoost treats the KV cache as a collection of fixed‑size chunks, each accompanied by two hashes: a position hash that records where the chunk originally appeared in its source sequence, and a content hash that captures the actual token values inside the chunk. When a new request arrives, the system first looks up chunks by content hash to find candidates with identical or near‑identical token patterns, regardless of their original position. If a candidate’s position hash differs from the target location, KVBoost applies a lightweight deviation‑guided recomputation step that adjusts the attention scores to account for the shift, preventing the boundary errors that naive chunk stitching would introduce.

The approach works with any HuggingFace‑compatible decoder‑only model because it operates on the model’s internal KV tensors rather than requiring changes to the architecture. Exact matches reuse the cached KV directly; approximate matches (e.g., when a few tokens differ) trigger a bounded recomputation of only the affected keys and values, keeping the overhead low. Experiments on LLaMA‑2 and OPT families show up to a 2.3× reduction in prefill latency for workloads where prompt reuse is scattered across positions, while maintaining generation quality within 0.1 % perplexity of the baseline.

Why It Matters

Serving LLMs at scale is often limited by the time spent preparing the KV cache for each new query. When users ask variations of the same question, repeat instructions, or embed shared snippets (such as system prompts or retrieval‑augmented context) in different places, existing prefix‑caching schemes miss most of the opportunity for reuse. KVBoost removes the positional constraint, turning any recurring token span into a potential cache hit, which directly translates to lower latency and higher throughput without sacrificing model fidelity.

Beyond raw speed, the method reduces the amount of redundant computation performed on GPUs, which can lower energy consumption and make it easier to fit more concurrent requests onto a given hardware budget. For applications that rely on long contexts—such as code assistants, legal‑document summarizers, or multi‑turn chatbots—the ability to reuse cached KV chunks wherever they appear can be a practical way to keep response times interactive.

Key Details

• Chunk size is configurable; the paper evaluates 64‑token blocks as a sweet spot between granularity and overhead.
• Position hash uses a rolling polynomial hash over token IDs, enabling O(1) updates when sliding windows move.
• Content hash is a SHA‑256 of the chunk’s token IDs, providing collision‑resistant exact‑match detection.
• Deviation‑guided recomputation corrects attention scores by adding a positional offset term derived from the difference between source and target position hashes.
• Approximate matching employs a Hamming‑distance threshold on content hashes; mismatched tokens trigger recomputation of only the affected KV entries.
• Integration requires only a thin wrapper around the model’s forward pass; no changes to tokenization or generation loops are needed.

What’s Next

Future work could extend KVBoost to encoder‑decoder architectures, where cross‑attention layers also benefit from reusable KV caches. Additionally, learning‑based predictors for when to trust approximate matches versus falling back to full recomputation might further improve latency‑quality trade‑offs. As serving infrastructures evolve toward dynamic batching and speculative decoding, chunk‑level KV reuse like KVBoost offers a compatible, low‑overhead lever to make LLM inference more efficient.

📌 Source: Arxiv Ai