Verify Before You Fetch: Reliable KV Cache Compression for LLM Inference

Devanshu Jha, Gaurav Kumar, Agniva Chowdhury, Kumar Krishna Agrawal, Aditya DesaiarXiv 2026 · arXiv

TL;DR

VerKV is a hybrid KV cache management framework that provides formal $(\epsilon, \delta)$ error guarantees for attention approximation in long-context LLMs. By combining a novel stochastic sampling method (PoissonComp) with a query-aware verification and retrieval algorithm (KVFetch), it achieves near-dense model quality while reducing GPU memory usage by up to 32x and significantly cutting down on slow CPU-to-GPU data transfers.

What Problem Does This Paper Address?

As Large Language Models (LLMs) move toward processing massive contexts—think long-lived agents or multi-document analysis—the "KV cache" (the memory used to store keys and values for every token) becomes a massive bottleneck. For a 128K context, this cache can easily exceed the high-bandwidth memory (HBM) of even the most powerful GPUs.

The standard solution is offloading: moving the cache to CPU memory. However, the PCIe link between the CPU and GPU is relatively slow. Fetching the entire cache for every new token generated creates a massive latency penalty. On the other hand, existing compression methods (like evicting "unimportant" tokens) are often heuristic and brittle; they might throw away a token that is crucial for a specific future query, leading to significant quality drops with no way to detect or fix the error during inference.

Methods

The authors introduce VerKV, which treats KV cache management as a "verify before you fetch" problem. It consists of two main stages:

  1. PoissonComp (Prefill Stage): Instead of using a deterministic "top-k" approach to decide which tokens to keep on the GPU, VerKV uses a novel stochastic sampling procedure. It assigns importance scores to tokens and uses them to parameterize Poisson sampling. This creates a set of "pivotal" tokens that stay on the GPU. Crucially, because this is a random sample, it allows the system to statistically estimate the approximation error later.
  2. KVFetch (Inference Stage): The GPU also stores a "sketch"—a highly compressed (e.g., 2-bit) representation of the entire KV cache. When a new query arrives, the KVFetch algorithm uses the pivotal tokens and the sketch to calculate a "certificate" of the relative error.
  3. If the estimated error is within a user-defined tolerance $(\epsilon, \delta)$, the model proceeds using only the GPU-resident tokens, avoiding the CPU entirely.
  4. If the error is too high, the algorithm identifies the specific "missing" tokens that would most effectively reduce the error and fetches only those from the CPU.
Figure 1. Overview of VERKV. The GPU holds query-agnostic pivotal tokens (deterministic and stochastic) and a sparse attention indexer (sketch), while the full KV cache resides in CPU memory. An error-estimation module uses the pivotal tokens and sketch to decide whether the approximation already meets a user tolerance (ϵ, δ); if not, a query-aware fetch recovers additional tokens from the host so that the final attention is guaranteed to have error (ϵ, δ).

Datasets

The researchers evaluated VerKV across three different model families (Qwen3-4B, Qwen3.5-9B, and Ministral-3-8B) using two major long-context benchmarks:

  • RULER: A benchmark designed to test "real" context size through tasks like multi-key needle retrieval and common-word extraction.
  • LOFT: A benchmark focused on retrieval-augmented generation (RAG) tasks like HotpotQA and MuSiQue. Tests were conducted at both 32K and 128K context lengths.

Key Insights and Ideas

  • Stochasticity as a Tool for Reliability: The shift from deterministic eviction to Poisson sampling is the "aha" moment. By introducing controlled randomness, the authors can apply concentration inequalities (like Bernstein’s inequality) to provide a mathematical guarantee that the attention output is accurate.
  • The "Certificate" of Accuracy: VerKV doesn't just guess; it computes a formal bound on the error. This allows engineers to set a "reliability knob" ($\epsilon$). If you need high precision, you set a low $\epsilon$, and the system fetches more from the CPU; if you value speed, you can relax the bound.
  • Adaptive Retrieval: The paper shows that for many queries, a tiny fraction of the cache is sufficient. VerKV's ability to fetch only 2–23% of the cache per token (see Figure 4/Table 1) proves that full offloading is often overkill.
  • Sketching the Future: Even a naive 2-bit sketch significantly helps in identifying which tokens to fetch. The authors show that with a "perfect" sketch, they could theoretically match dense performance even at 32x compression.

Key Results

VerKV demonstrates a superior Pareto frontier between memory, speed, and quality compared to state-of-the-art methods like KVzip.

  • Quality: On average, VerKV retains 96% of dense quality at 8x compression and 86% at 32x compression. In contrast, deterministic methods like Fast KVzip often collapse to 2–12% quality at these extreme compression rates.
  • Efficiency: It reduces the GPU memory footprint by 8–32x.
  • Throughput: When implemented in vLLM, VerKV achieved 1.6x the decoding throughput of standard dense offloading. It achieves this by transferring 47x less data from host memory.
  • Fetch Rates: At default settings, VerKV avoids CPU fetches entirely for about 20–25% of queries and only reads a small fraction of the cache for the rest.
Figure 3. Quality vs. compression rate. Average quality of different compression setups across the RULER and LOFT benchmarks at context lengths of 32K and 128K for three models. We observe that (1) POISSONCOMP(C=KVzip) consistently outperforms KVzip, and (2) VERKV(C=KVzip, A=2-bit sketch) = POISSONCOMP(C=KVzip) + KVFETCH improves upon POISSONCOMP under all settings. (3) Relative to dense attention, quality is better preserved at shorter context lengths for a given compression rate, for the Qwen family compared to Ministral, and on RULER compared to LOFT. In particular, VERKV recovers near-dense quality on RULER-32K across all three models. Our algorithm currently uses a naive 2-bit sketch to bootstrap its estimates; improving sketch accuracy is a promising direction for further quality gains as can be seen with VERKV(C=KVzip, A=perfect sketch) which matches Dense in nearly every setting. Host traffic for these runs is reported per generated token in Table 1 and per forward pass in Table 2.

Limitations and Future Work

  • Sketch Approximation Error: The current error certificate assumes the sketch is perfect. In practice, 2-bit sketches have their own errors, which can lead to the system underestimating the true error at very tight tolerances. Future work could involve "sketch-aware" certificates.
  • Kernel Overhead: The "decide" phase (calculating the certificate and choosing what to fetch) introduces some computational overhead. While VerKV is faster than full offloading, optimizing these kernels is necessary to compete with resident (non-offloaded) attention.
  • Batching Challenges: Currently, the throughput gains from batching are limited because the decision-making kernel is memory-intensive. Scaling this to high-throughput production environments remains an open engineering challenge.

Summary updated

Abstract

Long-context applications, long-lived agents, and multi-agent systems require large language models (LLMs) to process and retain extensive information. In these settings, the KV cache can exceed GPU high-bandwidth memory (HBM) capacity, necessitating offloading to host memory, where CPU-to-GPU transfers can dominate inference latency. While KV cache compression can reduce data movement, query-agnostic compression that guarantees accurate attention for arbitrary queries is extremely challenging, if not impossible. We introduce VerKV, a hybrid approach that provides $(ε, δ)$ guarantees for approximating attention on any given query. VerKV maintains a compact set of query-agnostic pivotal tokens on the GPU, together with a token-level sketch of the full KV cache, while retaining the complete cache in CPU memory. We introduce a novel stochastic sampling procedure, PoissonComp, to select the pivotal tokens. At inference time, our proposed KVFetch algorithm uses the pivotal tokens and the sketch to estimate the relative error of the resulting attention computation. If the estimate satisfies a user-specified $(ε, δ)$ tolerance, inference proceeds without accessing host memory. Otherwise, VerKV performs query-aware retrieval to fetch additional tokens from the CPU, refining the attention computation to meet the required tolerance. Thus, VerKV enables attention with bounded approximation error while minimizing CPU-to-GPU transfers. We show that PoissonComp outperforms state-of-the-art approaches to KV cache compression. Combined with KVFetch, it achieves near-dense performance (90-100% of dense quality at 32K context length, averaged over RULER and LOFT), using Qwen3-4B, Qwen3.5-9B and Ministral-3-8B, while reducing the GPU memory footprint by 8-32x and keeping CPU-to-GPU memory fetches within 2-23% of the cache per generated token, depending on the model.
BibTeX
@misc{jha2026verify,
  author = {Devanshu Jha and Gaurav Kumar and Agniva Chowdhury and Kumar Krishna Agrawal and Aditya Desai},
  title = {{Verify Before You Fetch: Reliable KV Cache Compression for LLM Inference}},
  year = {2026},
  eprint = {2611.11319},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11319},
}
Figure