💻 computer science

VeriCache: Turning Lossy KV Cache into Lossless LLM Inference

VeriCache is an inference framework that achieves lossless LLM output identical to full-KV-cache decoding while significantly boosting throughput by using compressed KV caches to draft tokens and verifying them against the full cache, which is kept out of GPU memory and swapped in only when necessary.

Original authors: Jiayi Yao, Samuel Shen, Kuntai Du, Shaoting Feng, Dongjoo Seo, Rui Zhang, Yuyang Huang, Yuhan Liu, Shan Lu, Junchen Jiang

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jiayi Yao, Samuel Shen, Kuntai Du, Shaoting Feng, Dongjoo Seo, Rui Zhang, Yuyang Huang, Yuhan Liu, Shan Lu, Junchen Jiang

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

The Big Problem: The "Memory Overload"

Imagine a super-smart AI assistant (a Large Language Model) that needs to remember a massive amount of information to answer your questions. This information is stored in a special "scratchpad" called the KV Cache.

As conversations get longer (like writing a whole book or analyzing a huge codebase), this scratchpad gets so big that it doesn't fit in the AI's fast, expensive memory (GPU).

The Old Solution: To make it fit, engineers started "compressing" the scratchpad. They threw away some details or simplified the numbers (like summarizing a 100-page report into a 10-page one).
The Catch: This compression is lossy. It's like trying to drive a car using a blurry map. For short trips, it's fine. But for long trips (like writing code or calling tools), the AI starts making small mistakes. These mistakes pile up, and eventually, the AI might write code that crashes or gives the wrong answer, even if the words look correct.

The New Solution: VeriCache

The researchers built VeriCache, a system that lets you use the "blurry map" (compressed cache) for speed, but checks the "real map" (full cache) to make sure you don't get lost.

Think of it like a Fast Draftsman and a Strict Editor.

How It Works (The Analogy)

The Draftsman (Compressed Cache):
The AI uses the small, fast, compressed memory to quickly write a bunch of sentences (tokens) at once. This is super fast because the memory is small and fits easily on the computer.
- Analogy: A speed-writing student who guesses the next few words based on a quick summary.
The Strict Editor (Full Cache):
Before the student's work is sent to you, a "Strict Editor" checks it. The Editor has access to the entire original, perfect memory (which is too big to keep on the desk all the time, so it's kept in a filing cabinet across the room).
- The Trick: The Editor only pulls the heavy filing cabinet onto the desk when they need to check a batch of words.
The "Staggered" Dance (The Secret Sauce):
Here is where VeriCache gets clever. Usually, if you have to stop and fetch a heavy file, everything stops.
- VeriCache's Move: While the Editor is walking to the filing cabinet to get the heavy file, the Student keeps writing!
- Because fetching the file (moving data from storage to memory) and writing the next sentence (using the GPU) use different "roads" in the computer, they can happen at the same time without bumping into each other.
- By the time the Editor returns with the file, the Student has already written a whole new paragraph. The Editor checks the previous paragraph, fixes any mistakes, and approves the rest.

Why This is a Big Deal

Lossless Speed: Previous methods forced you to choose: Fast but wrong (compressed) OR Slow but perfect (full). VeriCache gives you Fast AND perfect. The final output is identical to what you would get if you used the slow, full memory the whole time.
No More "Silent Failures": In tasks like coding or giving specific commands, a tiny mistake is a disaster. VeriCache catches these mistakes before they reach you.
Works with Anything: It doesn't care how the memory was compressed. Whether they threw away words or simplified numbers, VeriCache can use that compressed version as the "Draftsman" and verify it against the "Full" version.

The Results

In their tests, VeriCache was able to generate text up to 4 times faster than using the full, slow memory, while producing exactly the same correct results.

In short: VeriCache lets the AI run on a fast, lightweight track, but puts up safety rails that check the heavy, perfect track in the background, ensuring the AI never falls off the edge.

Technical Summary: VeriCache

Problem Statement

The rapid expansion of Large Language Model (LLM) context lengths (exceeding one million tokens) has created a severe bottleneck in inference serving due to the size of the Key-Value (KV) cache. This bottleneck manifests in two ways:

Within-request overhead: Decoding steps require reading the entire KV cache from GPU High Bandwidth Memory (HBM), creating a memory bandwidth bottleneck that scales linearly with context length. Large caches also reduce the batch size that fits in GPU memory.
Cross-request overhead: Reusing precomputed KV caches for shared prefixes (e.g., system prompts) requires transferring large data volumes from storage or across networks, often dominating request latency.

To address this, numerous KV cache compression methods (token dropping and quantization) have been proposed. However, these methods are inherently lossy. While they may preserve token-level metrics (e.g., perplexity, F1 score) for short outputs, they introduce a systematic bias in the next-token distribution. As generation proceeds, this bias accumulates, causing the output to diverge significantly from the full-KV baseline. This leads to "catastrophic failures" in applications requiring strict functional correctness, such as code generation (syntax errors) and tool calling (incorrect arguments), rendering traditional compression unsuitable for these critical tasks.

Methodology: VeriCache

VeriCache is an inference framework designed to achieve the throughput benefits of KV cache compression while guaranteeing lossless outputs identical to full-KV decoding. It repurposes lossy compression methods as a speculative execution layer rather than a direct serving mechanism.

Core Algorithm

VeriCache operates in a draft-then-verify loop:

Drafting: The model generates a sequence of candidate tokens ( $x$ ) using the compressed KV cache ( $KV_{comp}$ ). This step is fast and memory-efficient.
Verification: The system performs a single forward pass using the full KV cache ( $KV_{full}$ ) to verify the drafted tokens in parallel.
Acceptance: Tokens are accepted up to the first mismatch. If all drafted tokens match the full-KV prediction, an additional "bonus" token is accepted. The process repeats from the last accepted token.

Key System Innovations

To prevent the verification overhead from negating the throughput gains of compression, VeriCache introduces two critical system-level designs:

1. Cross-Resource Staggering (P1)
Traditional speculative decoding often runs in lock-step (all draft, then all verify), causing resource contention. VeriCache exploits the fact that drafting and verification have complementary resource bottlenecks:

Drafting is GPU HBM-bandwidth bound (reading compressed KV and weights).
Verification is Interconnect-bandwidth bound (loading full KV from CPU/Storage) and compute-bound.
Mechanism: The runtime scheduler staggers requests so that while some requests are drafting (using HBM), others are verifying (loading full KV over PCIe/Network). This allows the system to overlap data transfer with computation, keeping both the interconnect and GPU HBM utilized without stalling.

2. Extended Verification Period via High Acceptance Rates (P2)
Unlike traditional speculative decoding which uses a smaller, different model as a drafter (leading to rapid distribution divergence and short acceptance lengths), VeriCache uses the same target model with compressed KV.

Because the model weights and dominant attention patterns are preserved, the compressed KV drafter maintains a high acceptance rate even for long draft lengths (e.g., 25–40 tokens per round vs. 2–3 for small-model drafters).
This high acceptance rate amortizes the cost of the expensive full-KV verification, allowing the system to verify less frequently while maintaining correctness.

Architecture Support

VeriCache supports two primary deployment scenarios:

Long-Context Decoding: The compressed KV resides in GPU HBM, while the full KV is stored on CPU memory. Verification involves loading the full KV from CPU to GPU over the PCIe link.
Remote Prefix Caching: The compressed KV is streamed over a slow network link to a remote GPU for drafting. The full KV is loaded over a fast local link to a local GPU for verification. This decouples the slow storage transfer from the remote GPU's compute.

The framework exposes a uniform compressor interface, allowing it to integrate with various existing token-dropping and quantization methods (e.g., KVzip, KIVI, SnapKV) without modifying the scheduling or verification logic.

Key Contributions

Lossless Inference with Compression: VeriCache is the first framework to enable lossless LLM inference using inherently lossy KV compression techniques, ensuring output identity with full-KV decoding.
System Design for Verification Overhead: It introduces cross-resource staggering and extended verification periods to hide the latency of loading full KV caches, solving the throughput degradation typically associated with speculative verification.
Unified Interface: It provides a generic interface that supports a broad family of compression methods (both token dropping and quantization), unlike prior systems that hard-wire specific compressors.
Dual-Scenario Support: It addresses both long-context decoding (HBM bottleneck) and remote prefix caching (network/storage bottleneck).

Experimental Results

Evaluated on models including Mistral-24B, Qwen-32B, and Llama-70B across various workloads (code generation, tool calling, math reasoning):

Throughput: VeriCache achieves up to 4× higher throughput than full-KV inference in long-context decoding and up to 2× in remote prefix caching.
Correctness: It produces outputs identical to full-KV inference (under greedy decoding), whereas lossy baselines suffer significant drops in functional accuracy (e.g., code syntax validity drops to near zero with 4× compression in baselines).
Quality-Throughput Tradeoff: While lossy baselines force a tradeoff where higher compression leads to lower quality, VeriCache maintains full quality while operating at the throughput levels of compressed inference.
Composition: VeriCache can be composed with traditional speculative decoding (e.g., EAGLE), achieving up to 4.35× ideal speedup by attacking orthogonal bottlenecks (batch size via compression, token speed via small-model drafting).

Significance

The paper argues that the current dichotomy—choosing between high-throughput lossy compression (risking functional failure) or low-throughput full-KV inference—is unnecessary. VeriCache demonstrates that compression should not replace exact computation but rather accelerate it. By leveraging the high acceptance rates of same-model compressed drafting and sophisticated resource staggering, VeriCache enables the deployment of long-context LLMs in critical applications (coding, agentic workflows) without sacrificing the functional correctness required for these tasks.