Summary (Overview)

• VERKV is a hybrid KV cache management framework that combines query-agnostic compression with query-specific verification and adaptive retrieval, providing (ε, δ) approximation guarantees for attention computation while minimizing CPU-to-GPU transfers.
• The framework introduces POISSONCOMP, a novel stochastic sampling procedure for KV cache compression that outperforms deterministic top-k eviction methods (KVzip, Fast KVzip) across all settings.
• KVFETCH, the verification and fetching algorithm, uses a bounded shrinkage estimator and Bernstein certificates to decide when GPU-resident tokens suffice and which additional tokens to fetch from CPU memory when needed.
• VERKV achieves 90–100% of dense quality at 32K context (averaged over RULER and LOFT benchmarks) while reducing GPU memory footprint by 8–32× and keeping CPU-to-GPU fetches within 2–23% of the cache per generated token.
• In a vLLM implementation, VERKV achieves 1.6× the decode throughput of offloaded dense attention at near-dense quality, keeping only 6.25% of the KV cache resident on the GPU.

Introduction and Theoretical Foundation

Background and Motivation

Long-context applications, long-lived agents, and multi-agent systems require LLMs to process extensive information. The KV cache scales linearly with sequence length, often exceeding GPU high-bandwidth memory (HBM) capacity. This necessitates offloading to host memory, where CPU-to-GPU transfers can dominate inference latency.

Limitations of Existing Approaches

The paper categorizes existing KV cache management into three approaches, each with distinct trade-offs:

1. KV compaction (Cassano & Rush, 2026; OpenAI, 2026; Anthropic, 2026): Compresses context in the text domain via summarization, but incurs substantial computational overhead and offers no guarantees about preserving query-relevant information.

2. KV offloading (Sheng et al., 2023; Lee et al., 2024b): Preserves the full cache in host memory but introduces significant CPU-to-GPU data movement at every decoding step.

3. KV compression (Zhang et al., 2023; Liu et al., 2023; Li et al., 2024; Kim et al., 2025; 2026): Reduces cache footprint in the embedding space but remains largely heuristic with no formal guarantees on attention approximation error.

Theoretical Foundation

The paper builds on the definition of verified computation from Desai et al. (2026):

Definition 1 ((ϵ, δ)-verified-X): For any computation $\mathcal{X}: \mathbb{R}^{d_1} \to \mathbb{R}^{d_2}$, an algorithm X′ is (ϵ, δ)-verified-X if for any $x \in \mathbb{R}^{d_1}$:

$$\operatorname{Pr}\left(\frac{\|\mathcal{X}'(x) - \mathcal{X}(x)\|_2}{\|\mathcal{X}(x)\|_2} > \epsilon\right) < \delta. \tag{2}$$

VERKV focuses on verifying the numerator ($\mathcal{N}$) and denominator ($D$) of the attention computation, which can be combined to obtain an (ϵ, δ)-verified SDPA algorithm.

Methodology

POISSONCOMP: Stochastic KV Cache Compression

POISSONCOMP uses importance scores from an existing KV compression algorithm C to parameterize Poisson sampling. Given a budget of η tokens:

Inclusion probabilities:

$$r_i = \min\{1, c\tau_i\}, \tag{3}$$

where $c$ is chosen such that $\sum_i \min(1, c\tau_i) = \eta n$ and $\tau_i \in [0,1]$ are normalized importance scores.

Tokens are partitioned into:

• H: tokens retained with probability 1 (including sink and local tokens)
• L: tokens with $0 < r_i < 1$

A Poisson sample is drawn:

$$S = \{i \in L: Z_i = 1\}, \qquad Z_i \sim \mathrm{Bernoulli}(r_i),$$

with all $Z_i$ independent.

Bounded Shrinkage Estimator

Definition 2: Given query q, sets H and L with inclusion probabilities r for L:

$$\hat{D} = \sum_{i \in H} w_i + \sum_{i \in L} Z_i \lambda_i \frac{w_i}{r_i}, \tag{5}$$

where $Z_i \sim \mathrm{Bernoulli}(r_i)$, $\lambda_i = \mathrm{clip}_{[r_i,1]}\left(\frac{\beta r_i}{w_i(1-r_i)}\right)$ with $\mathrm{clip}_{[r_i,1]}(x) = \min\{1, \max\{r_i, x\}\}$ and $\beta = \sum_{i \in L} w_i(1-\lambda_i)$.

Theorem 1: The bounded shrinkage estimator uniquely minimizes the Mean Square Error:

$$\mathrm{MSE}_{\hat{D}}(\lambda) = \left(\sum_{i \in L} w_i(1-\lambda_i)\right)^2 + \sum_{i \in L} \lambda_i^2 w_i^2 \frac{1-r_i}{r_i}. \tag{6}$$

Bernstein Certificate

Lemma 1: For $0 < \delta < 1$, the estimator $\hat{D}$ satisfies $|\hat{D} - D|/D \leq \hat{\varepsilon}(L)$ with probability at least $1 - \delta$, where:

$$\hat{\varepsilon}(L) = \frac{\beta(L) + \frac{b(L)l_\delta}{3} + \sqrt{\left(\frac{b(L)l_\delta}{3}\right)^2 + 2V(L)l_\delta}}{D}, \tag{7}$$

with $l_\delta = \log(2/\delta)$, $\beta(L) = \sum_{i \in L}(w_i - \lambda_i w_i)$, $V(L) = \sum_{i \in L}\left(\lambda_i^2 w_i^2 \frac{1-r_i}{r_i}\right)$, and $b(L) = \max_{i \in L}\left(\frac{\lambda_i w_i}{r_i}\max(r_i, 1-r_i)\right)$.

KVFETCH: Verification and Adaptive Fetching

At each decode step, KVFETCH:

1. Computes estimated weights $\hat{w}_i$ using the sketch
2. Determines if $\hat{\varepsilon}(L) < \epsilon$ (no fetch needed)
3. If fetching is needed, orders tokens by importance score: $$g_i = \hat{\varepsilon}(L) - \hat{\varepsilon}(L \setminus \{i\}), \tag{9}$$
4. Finds the minimal k such that $\hat{\varepsilon}(L_g[k:]) < \epsilon$: $$k^\star = \min\left\{k \in \{0, \dots, |L|\}: \hat{\varepsilon}(L_g[k:]) < \epsilon\right\} \tag{10}$$
5. Fetches tokens $L \setminus L'$ from CPU, where $L' = L_g[k^\star:]$

Theorem 2: Under the fixed-query, exact-sketch, and Poisson sampling assumptions, the returned estimator satisfies:

$$\operatorname{Pr}\left(\frac{|\hat{D} - D|}{D} > \epsilon\right) \leq \delta.$$

Empirical Validation / Results

Experimental Setup

• Models: Qwen3-4B-Instruct-2507, Qwen3.5-9B, Ministral-3-8B-Instruct-2512 (all BF16)
• Benchmarks: RULER (MK3, MV, CWE, QA1 tasks) and LOFT (NQ, HotpotQA, MuSiQue, QAMPARI, QUEST) at 32K and 128K context
• Compression rates: 8×, 16×, 32× (GPU-resident cache fraction)
• Default parameters: $\varepsilon_0 = 0.05$, $\delta = 0.1$, 128-token shortlist per KV head

Quality Results (Table 1)

Host Traffic Results (Table 2)

At default $\varepsilon_0 = 0.05$ on Qwen3-4B (RULER-32K, 16×):

• 75.3% of decode decisions fetch at least one token
• Each fetching decision retrieves only 4.1% of the context
• Overall KV read is 10.8% of the full cache

Key findings:

• KVFETCH completely avoids CPU access for 20–25% of queries at $\varepsilon_0 = 0.05$
• Setting $\varepsilon_0 = 0.3$ avoids CPU access for 65–67% of queries
• Traffic scales with tolerance: falls ~43× from $\varepsilon_0 = 0.01$ to 0.3
• Ministral-3-8B requires ~3× more fetching than Qwen3-4B

Error Bound Guarantee (Figure 5)

• With perfect sketch: empirical failure rate always under 0.7%, well below δ = 10%
• With 2-bit sketch: stays within δ only at $\varepsilon_0 = 0.3$; sketch error, not the certificate, limits adherence
• Without fetching: 11–87% of decisions violate the error tolerance

System Performance (vLLM Implementation)

• 1.6× decode speedup over Dense (offload) at $\varepsilon_0 = 0.05$
• Speedups reach 3.1× at $\varepsilon_0 = 0.5$
• Transfers 47× less data from host memory than full offloading
• Quality: 86.7 vs. 88.0 for Dense (Qwen3-4B, RULER-32K, 16×)

Theoretical and Practical Implications

Theoretical Contributions

1. Formal guarantees for hybrid KV cache management: VERKV is the first framework to provide (ε, δ) approximation guarantees for attention in a hybrid GPU/CPU setting, combining the efficiency of compression with the reliability of verification.

2. Bounded shrinkage estimator: The paper introduces a novel estimator that optimally trades bias for variance, with a closed-form MSE minimization (Theorem 1) and a Bernstein-based certificate (Lemma 1).

3. Pareto improvement in compression: POISSONCOMP alone outperforms deterministic top-k eviction methods, demonstrating that stochastic sampling with importance-based inclusion probabilities is superior to hard thresholding.

4. Theoretical limits of query-agnostic compression: The results formally demonstrate why fetching is essential—no query-agnostic compression can guarantee quality for arbitrary queries at high compression rates.

Practical Implications

1. Controllable quality-traffic tradeoff: The (ε, δ) parameters provide users with explicit control over the balance between inference quality and host memory traffic.

2. Model-aware adaptation: The verification mechanism automatically adapts to model-specific attention patterns (e.g., Ministral requires 3× more fetching than Qwen models).

3. Practical deployment: The vLLM implementation demonstrates real-world viability, with meaningful throughput gains over full offloading at near-dense quality.

4. Sketch quality as a bottleneck: The results identify sketch accuracy as the primary limitation, suggesting that improving sparse attention indexers is a high-value research direction.

Conclusion

VERKV addresses the fundamental challenge of KV cache management for long-context LLM inference by combining query-agnostic compression with query-specific verification and adaptive retrieval. The framework provides formal (ε, δ) approximation guarantees while minimizing CPU-to-GPU transfers, achieving near-dense quality at compression rates where existing methods collapse.

Key takeaways:

• POISSONCOMP provides a Pareto improvement over deterministic KV compression methods
• KVFETCH enables verified attention with minimal data movement
• VERKV achieves 90–100% of dense quality at 32K context with 8–32× memory reduction
• The framework offers controllable tradeoffs between quality, memory, and latency

Future directions identified by the authors include:

• More accurate sketches to close the gap between approximate and perfect sketch performance
• Certificates that explicitly incorporate sketch error into the bound
• Optimizing the verification kernel overhead (currently 36.6 ms/token at $\varepsilon_0 = 0.5$ vs. 5.8 ms for Dense resident)