VerKV keeps just 3.13% of the KV cache on GPU: it bounds attention error first, then fetches only what it needs

VerKV lets long-context inference keep only a small fraction of the KV cache on the GPU while holding the gap between its attention output and full computation within an estimable range, instead of losing quality guarantees as compression rises, as query-agnostic compression does. Earlier query-agnostic KV compression keeps a fixed number of tokens by importance score during prefill and offers no guarantee on attention approximation error for future queries; at matched GPU memory, Fast KVzip and KVzip retain only 1.9% to 11.9% of dense quality with 3.13% of the cache resident. Across three models and two long-context benchmarks at 32K and 128K, VerKV retains 100.1%, 90.6% and 98.2% of dense quality on Qwen3-4B, Qwen3.5-9B and Ministral-3-8B at 12.5% GPU-resident cache, 95.0%, 85.2% and 85.2% at 6.25%, and 94.6%, 84.6% and 79.6% at 3.13%.

Each decode step first decides whether the GPU-resident sample alone meets the error tolerance, avoiding CPU access entirely when it does, and otherwise fetches the minimum set of additional KV entries. Full offloading moves the entire cache from host to GPU at every decode step, while pure compression never fetches, paying in latency and in accuracy respectively. KVFetch avoids the CPU KV cache entirely for about 20% to 25% of queries; on Qwen3-4B it reads about 4.8% of the KV cache per forward pass, and across the three models the range is 4.7% to 19.4%; loosening the tolerance raises the share of queries with no CPU access to 65% to 67%.

The GPU-resident sample comes from Poisson sampling whose inclusion probabilities derive from importance scores of an existing compression method, so a Bernstein bound can combine bias, variance and single-token influence into a relative error bound. Deterministic top-k selection yields only a point estimate, giving no way to judge how large the approximation error is or whether extra entries are needed. With exact attention weights the empirical failure rate stays below the target failure probability, and per-decision error falls within tolerance for most decisions; in a vLLM implementation, VerKV reaches the decode throughput of offloaded dense attention while keeping only 3.13% of the KV cache resident on the GPU.

The evaluation covers three instruction-tuned models, Qwen3-4B, Qwen3.5-9B and Ministral-3-8B, two benchmarks, RULER and LOFT, context lengths of 32K and 128K, and GPU-resident cache fractions of 12.5%, 6.25% and 3.13%; speed is measured with a vLLM implementation on one NVIDIA H100 GPU serving one request at a time.

The error certificate is derived under a fixed query, an exact sketch and Poisson sampling; the 2-bit sketch exceeds the target failure probability at strict tolerances because sketch error is not accounted for in the certificate. Quality with an approximate sketch degrades as context grows, while a perfect sketch still recovers dense quality.