VerKV enables attention with bounded approximation error while minimizing CPU-to-GPU transfers, and it is shown that PoissonComp outperforms state-of-the-art approaches to KV cache compression.
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 $(\epsilon, \delta)$ 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 $(\epsilon, \delta)$ 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.
As on-device large language model (LLM) applications like mobile agents become increasingly popular, long-context inference has become a key challenge. The key-value (KV) cache is the foundation of efficient autoregressive decoding, but its memory footprint grows rapidly with context length, often exceeding the memory...
Kun Wang, Jia-Ni Cao, Zhen-Jiang Li· Proceedings of the 32nd Annu...· 0 citations
KV cache compression is critical for large reasoning models, where most of the cost comes from long generated reasoning traces rather than the input prompt. These traces often contain redundant and low-utility tokens due to looping, self-verification, and corrections. However, such tokens may still receive high attenti...
P. Behnam, Elaheh Sobhani, Saad Amin et al.· 0 citations
Long-context capability has become essential for large language models (LLMs) to handle complex tasks, yet continuously expanding the context window does not remove the computational, storage, and information-selection pressures incurred at inference time. Existing work on prompt compression, KV-cache management, effic...
Long-context LLM inference is bottlenecked by GPU high-bandwidth memory (HBM), which the key–value (KV) cache rapidly exhausts. Existing designs compress, select, or offload KV entries, exposing trade-offs among HBM use, approximation error, and data movement. Our key insight is that locating the few tokens that domina...
Feng Yu, Hong-Shi Tan, Yao Chen et al.· Proceedings of the 2026 ACM...· 0 citations
This work proposes preserving shared prefixes and evicting the KV cache from the beginning of the remaining history while retaining the cached suffix and builds Penelope around this strategy by co-designing the eviction policy, KV recomputation, and unified GPU-CPU cache management.
Jia-Kun Fan, Han Meng, Yu-Xin Xia et al.· 1 citation
UlaCache is presented, a KV cache management system that provides unified logical addressing across GPU and CPU memory that reduces the overhead of KV replacement by parallelizing recency updates and eviction-candidate selection within a GPU memory pool shared across requests.