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

> VERKV combines Poisson sampling compression with a bounded shrinkage estimator and Bernstein certificates, achieving near-dense attention quality at 8-32x memory reduction via verified, minimal CPU-GPU KV fetching.

- **Source:** [arXiv](https://arxiv.org/abs/2611.11319)
- **Published:** 2026-11-14
- **Permalink:** https://picx.dev/p/3G6AwB
- **Whiteboard:** https://picx.dev/p/3G6AwB/image

## Summary

## 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)

| Method | Qwen3-4B Quality % | Qwen3.5-9B Quality % | Ministral-3-8B Quality % |
|--------|-------------------|---------------------|------------------------|
| Dense (resident) | 100 | 100 | 100 |
| KVzip 8× | 66.9 | 17.0 | 54.1 |
| KVzip 32× | 8.0 | 1.9 | 5.6 |
| Fast KVzip 8× | 65.0 | 16.8 | 64.3 |
| Fast KVzip 32× | 8.0 | 10.7 | 11.9 |
| **VERKV 8×** | **100.1** | **90.6** | **98.2** |
| **VERKV 16×** | **95.0** | **85.2** | **85.2** |
| **VERKV 32×** | **94.6** | **84.6** | **79.6** |

### 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)

---

_Markdown view of https://picx.dev/p/3G6AwB, served by PicX — AI-generated visual whiteboard summaries of research papers._