VeriCache: Turning Lossy KV Cache into Lossless LLM Inference

Review date: 2026-05-30 Review author: Zhongzhu Zhou Paper reviewed: VeriCache: Turning Lossy KV Cache into Lossless LLM Inference Paper authors: Jiayi Yao, Samuel Shen, Kuntai Du, Shaoting Feng, Dongjoo Seo, Rui Zhang, Yuyang Huang, Yuhan Liu, Shan Lu, Junchen Jiang arXiv: 2605.17613 Venue/Status: arXiv preprint, May 2026

Short Answer

VeriCache is an LLM serving framework that takes any lossy KV cache compression method — token dropping, quantization, or any combination — and turns it into a lossless inference path that still preserves most of the compression’s throughput gain. Conceptually, the compressed KV cache plays the role of a fast drafter and the full KV cache plays the role of a verifier in a speculative-decoding-style loop, but because the drafter and verifier share the same model weights and only differ in their KV cache content, the acceptance rate is extremely high (25–40 tokens per round, vs. 2–3 for traditional small-model drafters). A custom runtime scheduler hides the cost of swapping the full KV from CPU to GPU behind drafting work for other requests in the batch, so the framework reaches up to $4\times$ higher throughput than full-KV inference with bit-identical outputs (under greedy decoding).

Prerequisites

Before diving into VeriCache it helps to have a working mental model of four building blocks. None of them is new in this paper, but the paper’s contribution sits exactly at their intersection, so it is worth getting the foundations right.

Transformer attention and the KV cache

Modern decoder-only Transformers process input through stacked self-attention layers. At each layer, every token attends to every previous token. The operation that dominates inference cost is, at a high level,

$$\text{Attention}(Q, K, V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_h}}\right) V,$$

where $Q, K, V \in \mathbb{R}^{n \times d_h}$ are query, key, and value matrices over the sequence of length $n$ with per-head dimension $d_h$. During autoregressive decoding, the prefix’s $K$ and $V$ never change, so caching them avoids recomputing the projections at every step. This cache — the KV cache — is the structure VeriCache compresses, swaps, and verifies.

The KV cache’s size scales linearly with context length $n$, number of layers $L$, number of heads $h$, and head dimension $d_h$:

$$\text{KV size} = 2 \cdot n \cdot L \cdot h \cdot d_h \cdot b,$$

where $b$ is the bytes per element (e.g., $2$ for FP16). For Llama-3.1-8B with $L=32$, $h=8$ (GQA), $d_h=128$, and 100K context, the KV cache is on the order of $13$ GB — bigger than the model weights themselves.

KV cache as a serving bottleneck

The KV cache hits inference in three ways:

1. HBM bandwidth. Every decode step reads the entire KV cache from HBM into on-chip SRAM. On an H100 with $3$ TB/s HBM, a $60$ GB KV cache costs $\sim 20$ ms just for the memory transfer — before any compute.
2. HBM capacity. Large KV caches reduce the batch size that fits on a GPU, hurting per-GPU throughput.
3. Cross-request transfer. When KV caches are reused across requests (e.g., a shared system prompt), they must move from storage or another GPU to the serving GPU; over a $1.2$ GB/s remote link, a $15$ GB cache takes $\sim 12$ s.

KV cache compression: lossy by construction

Two main families address these bottlenecks:

• Token dropping keeps only a subset of the $n$ token positions per layer/head. Examples: KVzip, SnapKV, KVzap, H2O, StreamingLLM, DuoAttention.
• KV quantization reduces the bits per element. Examples: KIVI (2-bit), KVQuant (per-channel), KVTuner, TurboQuant, CacheGen.

Both deliver $2\text{-}5\times$ compression. Both are lossy: the compressed KV is a different tensor, and attention computed against it produces a different next-token distribution. The error compounds with output length.

Speculative decoding

Speculative decoding (Leviathan et al., 2023; Chen et al., 2023) accelerates autoregressive inference using a small fast drafter and a large slow verifier. The drafter proposes $x$ tokens; the verifier runs one forward pass over those $x$ positions in parallel and accepts the longest prefix whose drafted token matches the verifier’s prediction. The throughput gain comes from amortizing the verifier’s expensive forward pass over multiple accepted tokens. Critically, the output distribution is provably identical to the verifier-only one (under greedy decoding, exactly; under sampling, via rejection sampling).

VeriCache’s entire conceptual move is to map this drafter/verifier dichotomy onto compressed/full KV cache: same model, two different caches, same lossless guarantee.

GPU memory hierarchy

GPU compute happens against HBM (e.g., $80$ GB at $3$ TB/s on an H100). Below HBM sits CPU DRAM, accessible only via the PCIe interconnect ($\sim 64$ GB/s on PCIe Gen5 ×16). Below that sits SSD/network storage. The bandwidth ratio between HBM and the interconnect — call it $\rho = \text{BW}_\text{hbm} / \text{BW}_\text{inter}$ — typically falls between $10$ (GH200 NVLink-C2C) and $60$ (H100 NVL with PCIe). This ratio drives a lot of VeriCache’s scheduling decisions.

Motivation and Problem Setup

The accuracy–efficiency dichotomy

KV cache compression methods are evaluated on token-level metrics: F1, ROUGE, perplexity, cosine similarity. These metrics tolerate small drift in token identity. They are reasonable proxies for summarization or open-ended Q&A. They are terrible proxies for any task with a strict syntactic or semantic structure: code generation, tool calls, JSON output, shell commands.

The paper’s Figure 2 makes this visceral: asked to implement a feature over a $\sim 280$K-character codebase, full-KV Qwen-32B produces correct code, while the same model with KVzip $4\times$ compression generates code that starts correctly but rapidly drifts off-distribution after $\sim 200$ lines. The F1 score stays above $75\%$. The code does not compile.

Per-step bias accumulates exponentially

The paper formalizes why this happens. At each decode step $t$, compression introduces a per-step KL divergence between the full distribution $p_\text{full}$ and the lossy distribution $p_\text{lossy}$:

$$\text{KL}_t = \sum_x p_\text{full}(x_t \mid x_{<t}) \log \frac{p_\text{full}(x_t \mid x_{<t})}{p_\text{lossy}(x_t \mid x_{<t})}.$$

By the chain rule of KL divergence, the sequence-level divergence over $T$ tokens is

$$\text{KL}_{1:T} = \text{KL}\!\left(p_\text{full}(x_{1:T}) \,\Vert\, p_\text{lossy}(x_{1:T})\right) = \sum_{t=1}^T \mathbb{E}_{x_{<t} \sim p_\text{full}}\!\left[\text{KL}_t\right].$$

If $\text{KL}_t \geq \varepsilon > 0$ for all $t$, then $\text{KL}_{1:T} \geq \varepsilon T$ grows linearly in $T$. But $\text{KL}_{1:T}$ equals $\mathbb{E}_{x \sim p_\text{full}} \log(p_\text{full}/p_\text{lossy})$, which means the log-likelihood ratio has mean $\geq \varepsilon T$, and so the likelihood ratio $p_\text{full}/p_\text{lossy}$ is of order $e^{\varepsilon T}$ — exponential in output length.

To put numbers on it: KVzip $4\times$ accumulates only $\sim 0.023$ nats per step. The lossy model assigns the full-KV token $e^{-0.023} \approx 98\%$ of its full-KV probability — barely distinguishable per step. After $T = 250$ steps, cumulative KL hits $\sim 6$ nats, so the lossy model emits the full-KV output with probability only $e^{-6} \approx 2.5 \times 10^{-3}$. A $\sim 2\%$ per-step gap amplifies into a $400\times$ mismatch over a few hundred tokens. The paper’s Figure 4 confirms this experimentally.

The research question

This sets up the paper’s central question:

Can we exploit the throughput benefits of KV cache compression without affecting LLM output?

The answer the paper proposes is yes — by treating compression as a speculative drafter rather than a final-output approximator.

VeriCache Framework Design

High-level architecture

VeriCache sits between the request frontend and the GPU workers. It maintains two KV cache copies per long-context request: the compressed $\text{KV}_\text{comp}$ in GPU HBM (drives drafting) and the full $\text{KV}_\text{full}$ in CPU DRAM or remote storage (drives verification). For remote prefix caching, the picture shifts: the compressed cache streams over the slow remote link to a remote drafter GPU, while a local verifier GPU has fast-link access to full KV in storage.

flowchart LR
    R[Incoming Request] --> Adm[Admit: schedule next verify]
    Adm --> Draft[Draft x tokens with KV_comp on GPU HBM]
    Draft --> Verify{Verify window<br/>scheduled?}
    Verify -- yes --> Load[Async load KV_full<br/>CPU --> GPU]
    Load --> Forward[Forward pass over x drafted positions<br/>with KV_full]
    Forward --> Accept[Accept longest matching prefix + bonus correction]
    Accept --> Adm
    Verify -- no --> Draft
    Accept --> Out[Emit accepted tokens]

The figure makes one important detail explicit: at any given iteration, only $\sim B/x$ of the $B$ concurrent requests are verifying. The other $\sim B \cdot (1 - 1/x)$ are drafting. The runtime’s job is to place each request’s verify iteration so that the interconnect, HBM, and GPU compute never simultaneously saturate.

Two settings, one mechanism

VeriCache deploys in two scenarios:

flowchart TB
    subgraph LC[Setting 1: Long-Context Decoding]
        LCG[Single GPU] -- KV_comp resident --> LCG
        LCC[CPU DRAM] -- "PCIe (~64 GB/s)" --> LCG
        LCG -- "verify reload of KV_full" --> LCC
    end
    subgraph RP[Setting 2: Remote Prefix Caching]
        Store[KV Store / Storage Node + Local GPU]
        Remote[Remote GPU Pool]
        Store -- "slow link (~1.2 GB/s) carries KV_comp" --> Remote
        Store -- "fast link (~40 GB/s) carries KV_full" --> Store
        Remote -- "drafted tokens" --> Store
        Store -- "verify forward pass on local GPU" --> Remote
    end

The mechanism — draft with compressed, verify with full, schedule across resources — is identical. Only the bandwidth budget and physical placement differ.

The two design principles

VeriCache’s success rests on two principles, each addressing a distinct system-level worry:

P1: Cross-resource staggering. Drafting bottlenecks on HBM bandwidth; verifying bottlenecks on interconnect bandwidth (transfer) plus GPU compute (forward pass). These are complementary. If we stagger requests’ verify iterations across the batch — so that every iteration has both drafters (using HBM) and verifiers (using interconnect + compute) — total resource utilization rises dramatically.

P2: High acceptance rate amortizes verification. Because the drafter is the same model with merely a compressed KV cache, the drafted distribution closely tracks the verified distribution. Empirically, $25\text{-}40$ tokens are accepted per verification round — vs. $2\text{-}3$ for a typical small-model drafter. This means verification fires rarely, and each round captures a long run of accepted tokens.

Together, P1 hides the cost of each verify, and P2 minimizes how often verifies happen. The paper shows that without P1, lock-step verification stalls the interconnect; without P2, even a perfectly staggered schedule can’t amortize the verify cost.

Draft–Verify Pipeline

Step-by-step prose

For greedy decoding (the paper extends to sampling via standard rejection sampling), the per-request loop is:

1. The drafter holds the compressed cache $\text{KV}_\text{comp}$ in GPU HBM.
2. The drafter advances autoregressively for $x$ steps, generating candidate tokens $t_1, t_2, \dots, t_x$. Each $t_i = \arg\max_t p_\text{lossy}(t \mid \text{prompt}, t_1, \dots, t_{i-1})$, computed against the compressed cache.
3. At scheduled verify iteration $i + x$, the full cache $\text{KV}_\text{full}$ is already loaded into HBM (the load was kicked off $S_r$ windows earlier; see runtime).
4. The verifier runs one forward pass over the $x$ drafted positions in parallel, conditioned on $\text{KV}_\text{full}$ and the partial sequence $t_1, \dots, t_{k-1}$ at each position $k$. This yields $x + 1$ predictions: $t_1^*, t_2^*, \dots, t_x^*$ (the full-KV next-token prediction at each drafted slot) plus one bonus $t_{x+1}^*$.
5. Walk the drafted sequence: find the first position $j$ where $t_j \ne t_j^*$. Accept $t_1, \dots, t_{j-1}$ as the verified prefix, plus the verifier’s correction $t_j^*$. Discard $t_{j+1}, \dots, t_x$.
6. If no mismatch is found (all $x$ tokens were correct), accept all $x$ plus the bonus $t_{x+1}^*$ — net gain of $x + 1$ tokens for one verify.
7. Drafting resumes from the position immediately after the last accepted token; the runtime calls $\text{Admit}(r)$ to schedule the next verify.

Numbered pseudocode

Algorithm: VeriCache per-request draft-verify cycle
Inputs: prompt P, model weights M, compression knob c
Outputs: accepted token stream

  1: KV_comp <- Compressor.compress(prefill(P), ratio=c)
  2: KV_full <- prefill(P)              # kept on CPU/storage
  3: position <- |P|
  4: while not EOS do
  5:     // ---- Draft phase ----
  6:     for k = 1 .. x do
  7:         logits <- forward_one_token(M, KV_comp, position + k - 1)
  8:         t_k <- argmax(logits)
  9:         append (k_k, v_k) to KV_comp at position + k - 1
 10:     end for
 11:     // ---- Async swap ----
 12:     // started S_r windows earlier; assume KV_full now resident on GPU
 13:     // ---- Verify phase ----
 14:     logits_1..x+1 <- forward_parallel(M, KV_full, [t_1, ..., t_x])
 15:     for k = 1 .. x do
 16:         t_k_star <- argmax(logits_k)
 17:         if t_k != t_k_star then
 18:             accept t_1..t_{k-1}, t_k_star
 19:             position <- position + k       # advanced by k tokens
 20:             rollback KV_comp to position    # discard rejected appends
 21:             goto next cycle
 22:         end if
 23:     end for
 24:     // All x matched: bonus
 25:     t_bonus <- argmax(logits_{x+1})
 26:     accept t_1..t_x, t_bonus
 27:     position <- position + x + 1
 28:     append KV_full deltas for t_1..t_x into KV_full      # so next verify sees them
 29:     Compressor.update(...)                                # let online compressor refresh
 30:     evict KV_full from GPU; schedule next verify
 31: end while

Line-by-line explanation

• Lines 1–3 prefill once and produce both caches. The compressed cache is the only one resident on the GPU between iterations; the full cache lives on CPU.
• Lines 5–10 are the draft loop. Each step is a single-token forward — sequential, vector-matrix bound, dominated by reading $M + \text{KV}_\text{comp}$ from HBM.
• Line 12 captures the central scheduling trick: the full-KV transfer was scheduled to finish before verify begins. It overlaps with the draft work on other requests in the batch (cross-resource staggering).
• Line 14 is the cheap part. One parallel forward pass over $x$ positions costs roughly the same wall-clock time as a single decode step (because the compute is parallelizable across the $x$ positions and the KV read is amortized).
• Lines 15–22 check for the first divergence. The instant it appears, we abandon the rest of the drafted sequence. This is exactly the speculative-decoding accept rule.
• Lines 24–27 handle the lucky “all matched” case. The bonus prediction at position $x+1$ is free because the verifier’s forward pass already computed it.
• Line 28 is subtle but important: after a verify, the full cache must absorb the newly accepted tokens. The compressed cache also needs to incorporate them; how depends on the compressor (online vs. offline; see §6 of the paper).
• Line 30 evicts $\text{KV}_\text{full}$ from GPU HBM — the full cache is only ever transiently resident during a verify window.

Why the same model means high acceptance

The most important intuitive property to internalize is that VeriCache’s drafter and verifier are the same model. They differ only in the KV cache content. Traditional speculative decoding uses a small auxiliary model whose distribution diverges quickly from the target’s — typical acceptance lengths are $2\text{-}3$ tokens. VeriCache’s drafter shares all weights and most of the attention pattern with the verifier, so the dominant attention heads and the dominant token rankings line up. The result: $25\text{-}40$ accepted tokens per round. This is the fundamental algorithmic reason VeriCache works.

KV Swap Scheduling

The core engineering challenge is hiding the cost of moving $\text{KV}_\text{full}$ from CPU (or storage) to GPU. The naïve lock-step approach is catastrophic; the paper’s Figure 6 visualizes it.

Lock-step (bad) vs. staggered (good)

sequenceDiagram
    participant ICN as Interconnect
    participant GPU as GPU
    participant HBM as HBM BW
    Note over ICN,HBM: (a) Lock-step — both requests verify at iter i+2
    GPU->>HBM: draft r1 (iter i)
    GPU->>HBM: draft r2 (iter i)
    ICN->>GPU: load KV_full(r1) (iter i+1)
    ICN->>GPU: load KV_full(r2) (iter i+1)
    Note over ICN,GPU: PCIe serialized; r1 waits in HBM idle
    GPU->>HBM: stall (waiting on r2 transfer)
    GPU->>HBM: verify r1 + r2 (iter i+2)
    Note over ICN,HBM: (b) Staggered — r1 at i+1, r2 at i+2
    ICN->>GPU: load KV_full(r1) (overlap with iter i draft)
    GPU->>HBM: draft r2 (iter i)
    GPU->>HBM: verify r1 (iter i+1); draft r2 (iter i+1)
    ICN->>GPU: load KV_full(r2) (overlap with iter i+1)
    GPU->>HBM: verify r2 (iter i+2); draft next requests

In the lock-step picture, both requests’ verifies collide at the same iteration. The PCIe link is serialized, so $\text{KV}_\text{full}(r_1)$ arrives first and then sits in HBM idle waiting for $\text{KV}_\text{full}(r_2)$ to arrive. HBM is doubly occupied; the GPU stalls. In the staggered picture, the same total work happens but it’s spread across iterations, so every iteration uses the interconnect for one request’s transfer, HBM for another’s drafting, and compute for a third’s verify.

Concrete numbers from the paper

Consider Mistral-24B on an RTX PRO 6000 (PCIe Gen5 ×16, $64$ GB/s), $B=10$ requests, $\text{KV}_\text{comp} = 1$ GB, $\text{KV}_\text{full} = 4$ GB per request, draft length $x = 30$:

• One full-KV transfer over PCIe: $4 \text{ GB} / 64 \text{ GB/s} \approx 62.5 \text{ ms}$ (the paper rounds to $\sim 80$ ms including overheads).
• One draft-only iteration reads $M + B \cdot \text{KV}_\text{comp}$ from HBM: $\sim 35$ ms.
• One mixed draft+verify iteration adds one $\text{KV}_\text{full}$ to the HBM read: $\sim 37$ ms.
• Staggered: $10$ verifies spread one every $3$ draft iterations. Each $\sim 80$ ms PCIe transfer overlaps with concurrent draft work. Peak HBM stays at $M + B \cdot \text{KV}_\text{comp} + 1 \cdot \text{KV}_\text{full} = 64$ GB.
• Lock-step: batches all $10$ verifies at iteration $30$, serializing $40$ GB on the PCIe link ($\sim 800$ ms of transfer time, $\sim 20\times$ the iteration window). Peaks HBM at $M + B \cdot \text{KV}_\text{full} = 90$ GB.

The staggered schedule wins by an order of magnitude in transfer overhead and avoids a $1.4\times$ HBM blowup.

Theoretical Analysis

Why we need a model at all

Before diving into the formulas, it is worth saying why we want them. VeriCache’s throughput depends on three knobs: the compression ratio $c$, the draft length $x$, and the batch size $B$. It also depends on six hardware constants: HBM bandwidth, PCIe bandwidth, fast remote-storage bandwidth, slow remote-storage bandwidth, GPU FLOPs, and the model weight size $M$. A practitioner deploying VeriCache on a new GPU SKU or with a new model needs a way to predict whether the speedup will be $1.5\times$ or $4\times$ before running expensive experiments. The throughput model in this section is the answer.

Throughput model for long-context decoding

The paper’s Eq. (3) gives the iteration-time bound for the staggered schedule:

$$T_\text{iter} = \max\!\underbrace{\left(\frac{M + B \cdot \text{KV}_\text{full} \cdot (c + 1/x)}{\text{BW}_\text{hbm}}\right)}_{T_\text{gpu}},\ \underbrace{\frac{B \cdot \text{KV}_\text{full}}{x \cdot \text{BW}_\text{inter}}}_{T_\text{xfer}}.$$

Let me unpack each term:

• The numerator inside $T_\text{gpu}$ has two pieces. $M$ is model weights read once per iteration. $B \cdot \text{KV}_\text{full} \cdot c$ is the compressed-KV bandwidth used by all $B$ drafting requests in this iteration ($c$ is the compression ratio so $\text{KV}_\text{comp} = c \cdot \text{KV}_\text{full}$). The extra $1/x$ factor accounts for the one verify-in-flight that contributes its full $\text{KV}_\text{full}$ to HBM reads — but only $1/x$ of the time on average, since verifies fire once per $x$ iterations.
• $T_\text{xfer}$ is the PCIe load time amortized across $x$ draft iterations: in steady state we need to transfer one $\text{KV}_\text{full}$ for every $x$ draft iterations per request, and there are $B$ requests, so the aggregate transfer rate must hit $B \cdot \text{KV}_\text{full} / x$ bytes per iteration.
• The iteration time is the max of the two because the staggered pipeline runs them in parallel; whichever is slower determines the iteration step.

Step-by-step derivation of T_iter

Start from a single iteration of the staggered schedule and ask: what work happens, and what resources does it consume?

Step 1: Count token-equivalent compute. Per iteration we have $B$ drafting requests (each producing one new token) and roughly $B/x$ verifying requests (each verifying $x$ tokens in parallel). Total token-forward-passes per iteration: $B + (B/x) \cdot x = 2B$.

Step 2: Compute HBM traffic. Each token forward must read the model weights $M$ and the relevant KV cache. For drafters, the KV cache is compressed: each of the $B$ requests contributes $\text{KV}_\text{comp} = c \cdot \text{KV}_\text{full}$ of HBM read. For verifiers, the KV cache is full: each of the $B/x$ verifying requests contributes $\text{KV}_\text{full}$, which after amortizing across the iteration window becomes $(B/x) \cdot \text{KV}_\text{full}$ effective bytes per iteration. Plus the model weights $M$ are read once. Total HBM bytes per iteration:

$$\text{HBM}_\text{iter} = M + B \cdot c \cdot \text{KV}_\text{full} + (B/x) \cdot \text{KV}_\text{full} = M + B \cdot \text{KV}_\text{full} \cdot \left(c + \frac{1}{x}\right).$$

Step 3: GPU-side iteration time. Dividing by HBM bandwidth gives $T_\text{gpu}$, the time HBM transfer needs.

Step 4: Compute interconnect traffic. Each verify needs one $\text{KV}_\text{full}$ transferred from CPU to GPU. With $B$ requests each verifying once every $x$ iterations, the per-iteration aggregate is $(B/x) \cdot \text{KV}_\text{full}$ bytes. Dividing by $\text{BW}_\text{inter}$ gives $T_\text{xfer}$.

Step 5: Take the max. Because staggering runs HBM and interconnect work in parallel, the binding iteration time is whichever takes longer. Hence Eq. (3).

When does each term dominate?

Setting $T_\text{gpu} = T_\text{xfer}$ and solving for the critical compression ratio:

$$c^* = \frac{1}{\rho} - \frac{1}{x} - \frac{M}{B \cdot \text{KV}_\text{full}},$$

where $\rho = \text{BW}_\text{hbm} / \text{BW}_\text{inter}$. If the actual compression $c < c^*$, HBM is the bottleneck and shrinking the compressed cache further helps. If $c > c^*$, the PCIe link is the bottleneck and pushing the draft length $x$ longer (so verifies fire less often) is what helps.

For typical values — $\rho = 50$ (H100 + PCIe Gen5), $M / (B \cdot \text{KV}_\text{full}) \approx 0.1$, $x = 30$ — we get $c^* \approx 1/50 - 1/30 - 0.1 < 0$, which means in the realistic regime, GPU compute is the limit and the system actually saturates HBM. The compressed cache size dominates the achievable throughput.

Acceptance rate model

Let $\gamma(x, c)$ be the acceptance rate (fraction of drafted tokens accepted per verify round) as a function of draft length $x$ and compression $c$. In steady state, the effective tokens per iteration is

$$\eta = 1 + \gamma(x, c) \cdot \frac{x}{x + 1},$$

where the $+1$ in the denominator is the verify iteration itself. Throughput in tokens per second is then $\eta / T_\text{iter}$.

The paper’s Figure 8 shows that for KVzip at $4\times$ compaction, $\gamma$ stays above $0.8$ even at $x = 30$, peaks of acceptance length near $19\text{-}23$ tokens. Compared to traditional speculative decoders where $\gamma \approx 0.5\text{-}0.7$ and effective acceptance length is $\sim 2\text{-}3$, VeriCache’s acceptance length is an order of magnitude longer.

Why the acceptance rate stays high

The paper’s argument has two parts:

1. Model preservation. The model weights are identical. All FFN computations, all attention parameters, all positional embeddings — unchanged. Only the KV tensor that attention reads is approximate.
2. Dominant attention preservation. Both token-dropping (which keeps the highest-attention positions) and quantization (which keeps all positions at lower precision) preserve the dominant attention pattern. The top-1 token is usually the same whether you compute attention against $\text{KV}_\text{comp}$ or $\text{KV}_\text{full}$.

The result is a high “small-deviation regime”: per-step KL is small, and the argmax (relevant for greedy decoding) almost always agrees.

Remote prefix caching throughput model

For setting 2, the per-request time is (Eq. 4 in the paper):

$$T_\text{req} = \underbrace{\frac{c \cdot \text{KV}_\text{full}}{\text{BW}_l}}_\text{startup} + \underbrace{\frac{K}{x \cdot \gamma(x, c)} \cdot T_\text{cycle}}_{\text{\# draft–verify cycles}},$$

where $T_\text{cycle} = \max(x \cdot T_\text{decode},\ \text{KV}_\text{full}/\text{BW}_h + T_\text{fwd}(x))$. The max captures the draft–load overlap, and $T_\text{fwd}(x)$ — the verify forward pass — sits on the critical path because the next $x$ drafts depend on which of the previous $x$ were accepted. Startup is $\sim 1/c\times$ faster than the full-KV baseline (which would transfer $\text{KV}_\text{full}$ over the slow link), and the high $\gamma$ minimizes draft–verify cycles needed for $K$ output tokens.

Worked example: predicting Mistral-24B’s speedup

Let’s plug in numbers for Mistral-24B on RTX PRO 6000 ($96$ GB HBM, PCIe Gen5 ×16 at $64$ GB/s):

• $M \approx 48$ GB (24B params at FP16).
• $\text{BW}_\text{hbm} \approx 1.6$ TB/s (RTX PRO 6000 is HBM3 with bandwidth lower than H100).
• $\text{BW}_\text{inter} = 64$ GB/s.
• $\rho \approx 25$.
• Assume context $50$K tokens, so $\text{KV}_\text{full} \approx 5$ GB per request.
• Compression $c = 0.2$, draft length $x = 25$, batch $B = 6$.

HBM bytes per iteration:

$$\text{HBM}_\text{iter} = 48 + 6 \cdot 5 \cdot (0.2 + 1/25) = 48 + 7.2 = 55.2 \text{ GB}.$$

$T_\text{gpu} \approx 55.2 / 1600 \approx 35$ ms. PCIe traffic per iteration: $(6/25) \cdot 5 = 1.2$ GB; $T_\text{xfer} \approx 1.2 / 64 \approx 19$ ms. So $T_\text{iter} \approx 35$ ms, GPU-bound. Effective tokens per iteration: $1 + 0.85 \cdot 25/26 \approx 1.82$. Throughput: $\sim 1.82 / 0.035 \approx 52$ tok/s. Multiplied by batch $B = 6$ that’s $\sim 312$ tok/s — in the ballpark of the paper’s reported $317$ tok/s for Mistral-24B Pipeline 1. The model matches reality within $\sim 5\%$ on the headline number.

Worked example: predicting Qwen-32B’s $4\times$ ceiling

Repeat with Qwen-32B ($M \approx 64$ GB, otherwise same hardware):

$$\text{HBM}_\text{iter} = 64 + 6 \cdot 5 \cdot 0.24 = 71.2 \text{ GB}.$$

But $96 - 64 = 32$ GB of HBM are left for KV. At $\text{KV}_\text{comp} = 1$ GB per request, only $B \le 30$ requests can fit purely on $\text{KV}_\text{comp}$ — but in practice we want headroom for transient $\text{KV}_\text{full}$ during verifies. Setting $B = 6$ as before keeps us within $48$ GB of resident KV. $T_\text{gpu} \approx 71.2 / 1600 = 44$ ms. Effective tokens per iter: $\sim 1.82$, giving per-GPU throughput $\sim 41$ tok/s × $B = 6$ = $\sim 246$ tok/s. Reported by the paper: $188$ tok/s. Close, but the model overshoots — probably because we’re ignoring the verify forward pass overhead on critical path. Good enough for back-of-envelope.

The point of the worked examples: a practitioner can predict whether VeriCache will deliver substantial speedup on their workload before committing to deployment.

A note on the model’s simplifications

Eq. (3) hides several second-order effects:

1. GPU FLOPs are not modeled as a separate ring. The paper argues compute is smoothed by cross-resource staggering (verifies are spread evenly across iterations); empirically this seems right but on smaller models with cheap MLP layers it might not hold.
2. Verify forward pass is not on critical path in the model — but in remote prefix caching (Eq. 4) it explicitly is. The long-context model assumes that as long as the GPU is busy with draft work for other requests, the verify forward pass for request $r$ runs in parallel.
3. The KV append cost (Line 28 of the pseudocode — writing accepted tokens’ KV into both $\text{KV}_\text{comp}$ and $\text{KV}_\text{full}$) is ignored. For online compressors, this is a real cost; for offline compressors, it’s negligible.

These are pragmatic simplifications. They don’t change the qualitative picture but they do explain why the model overpredicts speedup by $5\text{-}20\%$ in some configurations.

Compression Method Integration

VeriCache exposes a small Compressor interface that any token-dropping or quantization method can implement. The interface decouples the scheduler from the compressor’s internals.

class CompressedKV:
    dropped_indices: list[Tensor]  # per-layer positions dropped
    bit_scheme:      int           # bits per element

class Compressor:
    scenario: Literal["long-context", "remote-prefix"]
    mode:     Literal["offline", "online"]
    def compress(full_kv, ratio) -> CompressedKV: ...
    def decompress(compressed, layer_idx=None,
                   page_table=None): ...
    def update(layer_idx, q, k, v, hidden,
               req_offsets) -> list[Tensor]: ...

Offline vs. online compression

• Offline. Compression runs once before serving (or on idle compute) and the runtime serves directly from the resulting cache. KVzip is the canonical example: it scores token importance via a one-shot context-reconstruction loss at prefill, then evicts low-importance pairs.
• Online. Compression runs inline during decode. After each layer’s forward pass, the runtime calls update(layer, q, k, v, hidden, req_offsets) and the compressor returns a new set of indices to drop or new quantization parameters. KVzap is the example here — a per-token MLP scores hidden states and decides what to evict on the fly.

Pass-through paging

The interface is intentionally pass-through: the runtime hands the compressor the physical-layout metadata (page table, request offsets in the batched tensor) and lets the compressor gather, dequantize, or write pages itself. The cost — compressor authors must understand the runtime’s paged layout — buys the runtime out of a virtualization layer. KIVI’s fused dequant-attention already operates on pages directly, so this is a small ask.

Seven compressors, one runtime

The paper instantiates the interface for seven methods spanning both families: KVzip, KVzap, ExpectedAttention, SnapKV (token dropping); KIVI, KVQuant, RotateKV (quantization). Adding a new method requires no scheduler changes. By contrast, prior speculative-with-compressed-KV systems (MagicDec, QuantSpec, SparseSpec) hard-wire a single compressor.

Scope and current limitations

The interface assumes:

1. Heads within a layer may drop different positions but the same count (count varies only across layers).
2. The system runs one mode at a time; token dropping and quantization don’t mix across concurrent requests.
3. bit_scheme is uniform across tokens and layers.
4. The compression method is fixed at deployment.

Each of these is a “future-work extension” rather than a fundamental limit.

Composition with Speculative Decoding

VeriCache’s drafter (compressed KV) and traditional speculative decoding’s drafter (small model) attack orthogonal bottlenecks:

flowchart LR
    subgraph Bottlenecks
        A[Per-Request KV Size]
        B[Per-Token Compute]
    end
    VC[VeriCache: shrinks KV --> larger batch] --> A
    SD[Speculative Decoding: amortizes compute over multiple tokens] --> B
    Composed["VeriCache + Eagle: hits both bottlenecks"] --> A
    Composed --> B

VeriCache shrinks the per-request KV footprint, which enlarges the achievable batch size. A traditional drafter (Eagle, MTP) accelerates the per-token compute for whatever sequence ends up running. Combining them is a tree: the small-model drafter proposes; VeriCache verifies its output against the compressed KV cache; periodically, the compressed-KV draft is itself verified against the full KV cache.

The paper’s Figure 10 quantifies the payoff: on Qwen-32B, VeriCache alone reaches $3.50\times$ ideal speedup; Eagle alone reaches $1.78\times$; VeriCache + Eagle reaches $4.35\times$.

The composition is clean because Eagle’s verify uses whatever KV cache is current — which happens to be the compressed one between VeriCache’s verify rounds. As long as the compressed cache produces tokens close enough to the full-KV distribution (the same property that makes VeriCache work), Eagle’s drafter remains useful within each VeriCache cycle.

Runtime Algorithm Deep Dive

The Compressor interface tells you how compressors plug in; the runtime tells you when each request drafts vs. verifies. The runtime is where the rubber meets the road.

Resource model

The runtime maintains a sliding window of $W$ future iterations, indexed $i \in [0, W)$, and tracks two reserve rings:

• BW ring (interconnect): $T[i]$ holds the interconnect time reserved for transfers landing in window $i$. The link is serialized — one transfer at a time, with each transfer taking size/bandwidth seconds — so the constraint is $T[i] \le T_\text{iter}$ for all $i$.
• HBM ring (GPU memory): $B[i]$ holds the in-flight KV cache occupying HBM during window $i$, including KV streaming for upcoming verifies. Together with persistent residency: $M + \text{KV}_\text{resident} + B[i] \le \text{HBM}$ for all $i$, where $\text{KV}_\text{resident}$ counts every KV cache kept on the GPU between iterations.

For request $r$ with $\text{KV}_\text{full}^{(r)}$, the reload’s iteration-equivalent duration is $\ell_r = \text{KV}_\text{full}^{(r)} / (\text{BW} \cdot T_\text{iter})$, spanning $S_r = \max(1, \lceil \ell_r \rceil)$ windows on both rings.

GPU compute is intentionally not modeled as a third ring — staggering spreads verifies evenly across iterations, so compute load is smoothed rather than bursting.

Admit pseudocode (Algorithm 1 in the paper, annotated)

Algorithm: Admit(r)
Inputs:  request r (just arrived or just finished a verify)
Globals: BW ring T[], HBM ring B[], lookahead window W,
         target draft length x

  1: ell_r <- KV_full^(r) / (BW * T_iter)
  2: S_r <- max(1, ceil(ell_r))
  3: anchor <- clamp(x, S_r, W - 1)
  4: candidates <- [anchor, anchor +/- 1, anchor +/- 2, ...]
                   clamped to [S_r, W - 1]
  5: for d in candidates:
  6:     span_r <- [d - S_r + 1, d]
  7:     if BW-ring-fits(span_r) and HBM-ring-fits(span_r):
  8:         reserve r on span_r
  9:         d_r <- d
 10:         mode[r] <- Speculative
 11:         return
 12: return r to waiting queue

Line-by-line explanation

• Line 1–2: Compute how many windows the full-KV reload will occupy.
• Line 3: Start the search at the ideal draft length $x$, but clamp it so the verify lands inside the lookahead window and after enough windows to fit the reload.
• Line 4: Build a “fan-out” candidate list — try $x$, then $x \pm 1$, $x \pm 2$, … — to gracefully degrade when the ideal slot is full.
• Line 5–11: Walk candidates in proximity-to-$x$ order. The first one that satisfies both ring constraints wins.
• Line 12: If nothing fits, push the request back to the queue and try again next tick.

The crucial design choice: searching outward from $x$ rather than starting from $0$. This minimizes the deviation from the ideal draft length, preserving acceptance rate at the cost of a few extra ring lookups.

Execution loop

At each iteration $t$:

1. Kick off verify reloads. For each speculating request whose reserved span has its first window at iteration $t$, start the asynchronous full-KV-cache reload on the link feeding the verifying GPU.
2. Draft and verify. Drafters run the next iteration’s forward pass; concurrently, verifiers complete their forward pass for any request scheduled at the current iteration. For each completed verify, re-invoke Admit(r) with the updated state — either continuing speculation with the next verify iteration scheduled, or returning $r$ to the waiting queue.
3. Advance. Slide the lookahead window one iteration forward.

Per-setting specialization

Long-context decoding. Drafting and verification share the same GPU; the interconnect is the CPU↔GPU PCIe link. The BW ring tracks this link, and the HBM ring tracks the same GPU’s HBM. The compressed cache stays on GPU for drafting; each verify reloads the full KV cache from CPU.

Remote prefix caching. Two GPU pools share a storage node: a small local pool on a fast link $\text{BW}_h$, and a larger remote pool on a slow link $\text{BW}_l \ll \text{BW}_h$. Remote-pool requests speculate: the remote GPU drafts using the compressed KV streamed over $\text{BW}_l$, while a local GPU concurrently loads the full KV over $\text{BW}_h$ for an upcoming verify and runs the verify forward pass. Because VeriCache issues each load ahead of its verify deadline, drafting, loading, and verifying all pipeline together. All links and pool HBMs get their own BW/HBM rings.

Experiments and Results

Hardware and models

• Mistral-24B and Qwen-32B on a single NVIDIA RTX PRO 6000 ($96$ GB).
• Llama-70B on $2\times$ H100 NVL ($94$ GB each, TP=2).
• CPU–GPU: PCIe 5.0 ×16 ($64$ GB/s).
• Local node to KV store: $40$ GB/s. Remote nodes: $1.2$ GB/s.

Pipelines and datasets

• Pipeline 1 (long-context decoding): context KV precomputed in CPU memory or storage, compressed offline or online, single serving instance.
• Pipeline 2 (remote prefix caching): KV reused across requests over the slow remote link, with one local instance and four remote instances.
• Datasets: LMCache-trace (KL-divergence from Full KV), ComplexFuncBench (function-call exact match), PISanitizer (prompt-injection defense), LongGenBench (per-prompt constraint satisfaction), GSM8K-Long (chained math).

Headline throughput numbers

VeriCache’s headline configuration uses KVzip ($c = 0.2$, $x = 25$) on Pipeline 1 and KIVI (4-bit, $x = 40$) on Pipeline 2. From Figure 11:

Model	Pipeline	Full KV	VeriCache	Speedup
Mistral-24B	Long-Context	$\sim 102$ tok/s	$\sim 256$ tok/s	$2.51\times$
Qwen-32B	Long-Context	$\sim 44$ tok/s	$\sim 188$ tok/s	$4.27\times$
Llama-70B	Long-Context	$\sim 102$ tok/s	$\sim 256$ tok/s	$2.51\times$
Llama-70B	Remote Prefix	$\sim 240$ tok/s	$\sim 485$ tok/s	$2.02\times$

On long-context decoding, VeriCache delivers $1.92\text{-}2.73\times$ over Full KV; composed with a traditional drafter, the peak hits $4.26\times$ on Qwen-32B. On remote prefix caching (where drafter-based methods don’t apply), VeriCache alone gives $1.33\text{-}2.11\times$.

Hardware sweeps

Figure 13 sweeps two hardware axes:

• KV-cache budget (Pipeline 1): varying Qwen-8B → Qwen-32B (larger weights = less HBM for KV). As budget shrinks from $0.74$ to $0.2$ of HBM, VeriCache’s speedup grows from $1.61\times$ to $2.71\times$. Full-KV’s batch collapses faster than VeriCache’s. SparseSpec drops from $1.82\times$ to $1.02\times$ because it must keep full KV resident on the drafter.
• HBM-to-interconnect ratio $\rho$: as $\rho$ falls from $60$ (H100 NVL) to $10$ (GH200), VeriCache’s speedup rises from $1.92\times$ to $3.01\times$. Faster interconnect means each full-KV reload is cheap, so verifies fire more often without stalling drafts.

For Pipeline 2, sweeps over $G_R/G_L$ (remote/local GPU count ratio) and $T_\text{init\_remote}/T_\text{decode}$ show a sweet spot at $G_R/G_L = 4$ where local and remote pools match throughput.

Quality–throughput frontier

Figure 14 plots negative KL divergence vs. throughput. VeriCache’s KL stays under $0.01$ nats (within hardware nondeterminism, per Thinking Machines Lab’s “Defeating Nondeterminism in LLM Inference”). Lossy baselines accumulate tens of nats. On Llama-70B Pipeline 1 at compression $0.5$, KVzip accumulates $\sim 14.4$ nats per request — the lossy model emits Full KV’s exact output with probability only $e^{-14.4} \approx 5 \times 10^{-7}$.

Application-level quality

Figure 16 shows function-call accuracy on ComplexFuncBench: VeriCache reaches at least $59\%$ of the fastest KVzip configuration’s throughput at Full KV accuracy, while KVzip drops up to $\sim 30$ accuracy points at the same throughput and collapses to $\sim 31\%$ of Full KV’s accuracy on Llama-70B even at the most conservative compression ratio.

Figure 17 (LongGenBench completion + GSM8K-Long accuracy on Qwen-32B): VeriCache preserves $100\%$ completion at $339$ tok/s and $90\%$ accuracy at $385$ tok/s. KVzip drops $\sim 10$ points at the same speed.

Across compression methods

Figure 15 adds four more baselines on Mistral-24B (ExpectedAttention, SnapKV, KVQuant, RotateKV). Across all, VeriCache’s KL stays within $0.01$ nats while running $1.4\text{-}1.9\times$ faster than Full KV; the baselines all trace the same quality–throughput frontier as the KVzip/KIVI headlines.

Latency vs. throughput tradeoff

Figure 12 of the paper plots end-to-end request latency against request rate for both pipelines. The key observation: at low request rates, VeriCache and Full KV have similar per-request latency (drafting work is parallelized but each request’s wall-clock is dominated by its own decode loop). As request rate climbs, Full KV’s latency explodes — the queueing backlog grows quadratically — while VeriCache stays flat much longer because its smaller per-request HBM footprint allows larger batches.

For Mistral-24B, Full KV saturates near $0.2$ req/s; VeriCache holds through $0.6$ req/s. The $3\times$ rate improvement at the same latency target is consistent with the throughput speedup.

The composition with traditional drafters extends the curve further: VeriCache + Trad. Drafter delivers another $\sim 1.3\times$ on top of VeriCache alone in the long-context regime, but adds variance because the small drafter’s acceptance rate fluctuates more than VeriCache’s.

Sensitivity to draft length

Figure 8 shows the acceptance rate stays above $0.8$ across draft lengths $5$ to $30$ at $4\times$ compaction. The ideal speedup peaks at $x \approx 15$ and degrades gently as $x$ grows further (because each rejected token wastes more drafting work) or shrinks below $\sim 10$ (because verifies fire too often).

This shape — broad peak with graceful degradation — is exactly what you want operationally. A static choice of $x = 25$ (the paper’s headline) sits comfortably on the plateau; small mistuning costs at most $10\text{-}15\%$ of throughput.

Why VeriCache + Eagle beats either alone

Figure 10 quantifies the composition: VeriCache alone $3.50\times$, Eagle alone $1.78\times$, VeriCache + Eagle $4.35\times$. The two mechanisms target orthogonal bottlenecks:

• VeriCache shrinks per-request KV in HBM → enables larger batch → linear throughput gain in batch size.
• Eagle drafts multiple tokens per target-model forward pass → reduces target-model invocations per accepted token → constant-factor reduction in compute time per token.

Multiplying the gains (with the small drafter sustaining ~3 accepted tokens per Eagle round inside VeriCache’s compressed cache) gets you to the observed $4.35\times$.

Workload-specific quality findings

Beyond the headline KL-divergence numbers, the application-level results show how lossy methods break in production-style settings:

• PISanitizer (prompt injection defense): KVzip drops defense success rate from $\sim 95\%$ (full KV) to $\sim 60\%$ at $4\times$ compaction. VeriCache preserves the full-KV $95\%$ at higher throughput.
• ComplexFuncBench (function calling): KVzip drops function-call accuracy from $\sim 80\%$ to $\sim 50\%$ at $2\times$ compaction; VeriCache preserves $80\%$ at $59\%$ of KVzip’s throughput.
• GSM8K-Long (chained math): A single wrong digit propagates and ruins the chain. Lossy methods drop $\sim 10$ accuracy points; VeriCache preserves the baseline.

These all reinforce the paper’s core motivating claim: for structured-output tasks, lossy KV cache compression is categorically the wrong tradeoff.

Comparison with Prior Work

Side-by-side architecture comparison

flowchart TB
    subgraph Full[Full KV inference]
        F1[KV_full on GPU] --> F2[Sequential decode, full attention]
    end
    subgraph Lossy[Lossy KV inference: KVzip, KIVI, ...]
        L1[KV_comp on GPU] --> L2[Sequential decode, sparse/quantized attention]
        L2 --> L3[Output drifts from full-KV distribution]
    end
    subgraph SpecDec[Traditional Speculative Decoding: Eagle, MTP]
        S1[Full KV on GPU] --> S2[Small drafter produces x tokens]
        S2 --> S3[Big verifier checks all x in one pass]
        S3 --> S4[Accept longest match: avg 2-3 tokens]
    end
    subgraph MagicSparse[MagicDec / SparseSpec / QuantSpec]
        M1[Full KV on GPU] --> M2[Sparse / Quantized KV used by drafter]
        M2 --> M3[Verifier uses Full KV; full KV still pinned]
    end
    subgraph VC[VeriCache]
        V1[KV_comp on GPU; KV_full on CPU/storage] --> V2[Same model drafts on KV_comp]
        V2 --> V3[Same model verifies on KV_full, async swap]
        V3 --> V4[Accept 25-40 tokens per round]
    end

The architectural diff is sharp: VeriCache is the only one of the speculative-with-compressed-KV family that does not pin $\text{KV}_\text{full}$ on the drafting GPU.

Detailed comparison table

System	Drafter	KV layout	Lossless?	Composes with traditional SD?	Multiple compressors?	Remote prefix?
Full KV	n/a	KV_full on GPU	Yes	n/a	n/a	n/a
KVzip / KIVI / KVzap	n/a	KV_comp on GPU	No	n/a	n/a	n/a
Eagle / MTP	Small model	KV_full on GPU	Yes	n/a	n/a	No
MagicDec	Small model	KV_full pinned + sparse KV	Yes	No	Hard-wired	No
QuantSpec	Self (quantized)	KV_full pinned + quantized KV	Yes	No	Hard-wired	No
SparseSpec	Self (sparse)	KV_full pinned + sparse KV	Yes	No	Hard-wired	No
VeriCache	Self (compressed)	KV_comp on GPU; KV_full on CPU/remote	Yes	Yes	7 + uniform iface	Yes

VeriCache is the first system in the bottom three rows to (a) actually shrink HBM usage to the compressed KV size, (b) expose a generic compressor interface, and (c) handle remote prefix caching.

Why prior work cannot match

MagicDec, QuantSpec, and SparseSpec all keep $\text{KV}_\text{full}$ pinned in GPU memory. They use the compressed cache only for drafting; verification happens with the resident full cache. The architectural consequence: they cannot realize compression’s batch-size benefit (HBM is still saturated by $\text{KV}_\text{full}$) and they cannot deploy to remote prefix caching at all (where the slow link is the bottleneck and resident full KV is impossible). VeriCache flips this — full KV is transient on the GPU, present only during the verify window of a single request.

Implementation notes worth absorbing

The paper buries a few practical implementation details that matter for reproducing the results:

vLLM scheduler hooks. VeriCache subclasses vLLM’s AsyncScheduler. The hook runs Admit against the BW and HBM rings on every scheduler tick. The async reload is kicked off $S_r$ windows ahead of its deadline; the bytes move via LMCache’s move(src_tier, dst_tier, kv_pointer).

Page table tricks. vLLM stores KV in fixed-size pages. VeriCache extends the page allocator to support two coexisting “kinds” of pages per request: compressed-resident (always allocated) and full-transient (allocated at verify reload, freed after verify). The allocator’s free list distinguishes them so that transient frees don’t fragment the resident pool.

Compressor.update calling convention. For online compressors, after each layer’s forward pass, vLLM calls Compressor.update(layer, q, k, v, hidden, req_offsets) on the batched tensors. The compressor slices the batch via req_offsets, scores per request, and returns a per-request (num_heads, new_drops) tensor. The runtime appends to dropped_indices[layer] and trims the (layer, head) page allocation.

Rejection sampling for non-greedy. The paper’s algorithmic description targets greedy decoding. For sampling with temperature, the standard rejection-sampling trick (Leviathan et al. 2023; Chen et al. 2023) applies unchanged: the drafter samples $t_i \sim p_\text{lossy}$; the verifier computes $p_\text{full}(t_i)$ and accepts with probability $\min(1, p_\text{full}(t_i) / p_\text{lossy}(t_i))$. When rejected, sample from the residual distribution. This preserves exactly the full-KV sampling distribution.

Limitations and Boundary Conditions

The paper is unusually explicit about its constraints.

Memory overhead

VeriCache keeps both caches — compressed in GPU HBM, full in CPU DRAM (or storage). The CPU memory pressure is real. On a $100$K-context Llama-70B run, $\text{KV}_\text{full}$ is $\sim 13$ GB per request; a $B = 10$ batch needs $130$ GB of CPU DRAM. This is cheap by GPU standards but not free, and it pushes deployments toward CPU-rich nodes. For remote prefix caching, the full cache is already on storage so this overhead is zero — VeriCache aligns naturally with that deployment.

Static draft length

The current implementation picks a single draft length $x$ per workload (e.g., $x = 25$ for KVzip on Pipeline 1, $x = 40$ for KIVI on Pipeline 2). A per-request adaptive policy — driven by early accept/reject outcomes — would handle heterogeneous compressors and contexts more gracefully. The paper flags this as future work.

Drafter-specific compression

Existing compressors (KVzip, KIVI, etc.) were optimized for direct serving — minimizing output quality loss when you use the compressed cache as the final output. A compressor designed instead to maximize acceptance length at large draft horizons — a different objective — could push VeriCache’s throughput further. This is a clean follow-up research direction.

Where speculative-style verification breaks down

The paper hints at but does not deeply explore: scenarios where the per-token KL is not small. If a compressor is aggressive enough that the per-step argmax often differs between $p_\text{full}$ and $p_\text{lossy}$, acceptance lengths collapse and VeriCache reduces to full-KV serving + overhead. The published evaluations use moderate compression ($c = 0.2\text{-}0.5$); much more aggressive compression may break the assumption.

Verification beyond compression

Other lossy KV techniques besides compression — for instance, CacheBlend’s reuse of precomputed KV across non-prefix chunks — also produce outputs that diverge from full-KV decoding. The paper raises whether a draft-then-verify approach could help there but does not investigate.

Boundary in remote prefix caching

The benefit fades when $T_\text{init\_remote} / T_\text{decode}$ exceeds $\sim 5$ — beyond that, decode time dominates the request lifecycle and the streaming-quantized-KV trick stops paying off. Similarly, the speedup converges back to $1\times$ when $G_R/G_L$ drifts far from the sweet spot of $4$.

Boundary diagram

flowchart TB
    Start[Workload profile] --> Q1{Per-token output<br/>strict?}
    Q1 -- yes --> Q2{Long context<br/>or shared prefix?}
    Q1 -- no --> Plain[Use lossy KV directly]
    Q2 -- long context --> Q3{HBM-bound<br/>at full KV?}
    Q2 -- shared prefix --> Q4{Slow remote link<br/>dominates?}
    Q3 -- yes --> Use1[VeriCache long-context]
    Q3 -- no --> Q5{Compute-bound?}
    Q4 -- yes --> Use2[VeriCache remote prefix]
    Q4 -- no --> Plain2[Pure caching, no compression]
    Q5 -- yes --> SD[Use Eagle/MTP alone]
    Q5 -- no --> Use3[VeriCache + Eagle composed]

The decision tree captures where VeriCache pays off vs. where simpler approaches suffice. If your output isn’t structured (open-ended Q&A, summarization), lossy KV is fine. If you’re compute-bound and have plenty of HBM, traditional speculative decoding alone is enough. VeriCache wins when you’re simultaneously memory-bound and need exact outputs — which is exactly the agentic / coding / tool-use regime that’s growing fastest.

Critical Assessment: Weaknesses & Improvements

The sections above summarize what VeriCache demonstrates well. This section reads the paper against the grain: where the evaluation is weaker than the headline numbers suggest, what the authors understate, and what a stronger version of the work would need.

Weaknesses and flaws in the evaluation

The lossless guarantee is validated only under greedy decoding, and the paper’s own numbers are all greedy. Section “Verification of lossless guarantee” defines “identical” as bit-identical under greedy decoding up to hardware nondeterminism (KL below $0.01$ nats). But every headline throughput number in Figures 11–17 is also collected under greedy decoding. Sampling with temperature $>0$ is mentioned only as “the standard rejection-sampling trick applies unchanged” — a one-sentence claim with zero supporting measurements. Since most production agentic/coding workloads do sample with $T > 0$ for diversity, and since rejection sampling under temperature systematically produces lower acceptance rates than greedy argmax matching (a rejected sample forces a full residual re-sample, unlike a simple mismatch check), the paper’s entire evidence base does not actually cover the regime most of its target audience will deploy in. The $25$-$40$-token acceptance-length claim could look very different at $T=0.7$.

No ablation isolates cross-resource staggering from high acceptance rate. The paper’s two design principles (P1: staggered scheduling, P2: same-model high acceptance) are presented as separately necessary, and the reviewer’s own summary above repeats this framing. But Figures 11–17 only report the fully-staggered VeriCache system versus Full KV and versus prior lossy/lossy-drafter baselines — there is no reported configuration that disables staggering (e.g., forces lock-step verification) while keeping the compressed-KV drafter, which is the one experiment that would isolate P1’s contribution quantitatively. Readers are asked to take the $\sim 20\times$ PCIe-blowup claim (Figure 6, restated in this review’s “KV Swap Scheduling” section) on the authors’ word rather than see it as a controlled ablation row in a results table.

The reported speedups conflate three different comparison baselines without a clearly labeled apples-to-apples control. “VeriCache reaches up to $4\times$” (Qwen-32B, long-context) is compared against Full KV; “VeriCache + Eagle reaches $4.35\times$” is compared against Full KV without Eagle; and the remote-prefix $1.33$-$2.11\times$ is compared against a Full-KV-over-slow-link baseline that itself is a strawman (nobody would actually serve remote prefixes without any compression in production). None of the tables report VeriCache against the strongest already-existing alternative for each regime — e.g., for long-context decoding, how does VeriCache compare against simply running the lossy compressor directly (accepting the quality hit) at the same throughput point, rather than against uncompressed Full KV? The paper’s own Figure 14 (quality–throughput frontier) contains the data to make this comparison directly, but the headline numbers in the abstract and results tables use the less informative Full-KV baseline throughout.

Memory-overhead accounting is asserted, not measured end-to-end. The paper states $130$GB of CPU DRAM is needed for a $B=10$ batch at $100$K context on Llama-70B, but there is no reported experiment showing VeriCache actually running at that batch size with that DRAM budget under realistic PCIe contention from other system traffic (OS, other tenants, page-cache eviction). The 8K-LoC implementation note and the DRAM-sizing arithmetic are both back-of-envelope; nothing in the results section demonstrates VeriCache holding up under DRAM pressure close to the stated requirement.

Limitations the authors understate or omit

The compression ratios tested are all “moderate” ($c = 0.2$-$0.5$), and the paper explicitly flags but never tests the aggressive-compression regime where the whole mechanism should break down. This review’s own “Where speculative-style verification breaks down” section already surfaces this from the paper’s text, but it’s worth stating plainly: the paper never reports a single data point at, say, $c = 0.05$ or $c = 0.1$ to show where the acceptance-length collapse actually starts. Given that the entire value proposition (a) requires the compressor to still produce a distribution close enough to Full KV for high acceptance, and (b) is strongest precisely when compression is most aggressive (more HBM saved), the absence of any boundary-finding experiment leaves the paper’s real operating envelope undefined. A practitioner cannot tell from the paper whether $c=0.1$ still works great or silently degrades into “VeriCache = Full KV + overhead.”

The remote-prefix-caching sweet spot ($G_R/G_L = 4$) is presented as a finding but is really a property of the specific bandwidth ratios used in the testbed ($1.2$ GB/s remote vs. $40$ GB/s local). The paper does not report how this ratio shifts as $\text{BW}_l/\text{BW}_h$ changes, even though it derives (and this review restates) a throughput model that could predict exactly that. Presenting "$4$" as if it were a general design target, rather than deriving the general formula for the optimal $G_R/G_L$ as a function of the bandwidth ratio, understates how testbed-specific this number is.

Online-compressor overhead is acknowledged but never separately measured. The Reproducibility section (echoed above) explicitly lists “cost of online compression’s per-layer hook” as something the paper does not include, noting KVzap’s MLP scoring “is cheap but not free.” This is a real omission: every headline number that uses an online compressor (as opposed to offline KVzip/KIVI) is implicitly crediting VeriCache with throughput that should be partially debited to the per-layer scoring hook, and the paper gives no way to tell how much.

Concrete improvement suggestions

1. Add a sampling-mode (T>0) results table, mirroring Figures 11 and 16 but for $T \in \{0.3, 0.7, 1.0\}$, reporting acceptance length and throughput under the standard rejection-sampling correction. Without this, the paper’s applicability to the dominant production decoding mode (sampled, not greedy) is unverified.
2. Run a staggering-disabled ablation: keep the same compressed-KV drafter and verifier, but force lock-step verification (all in-flight requests verify on the same iteration) and report the resulting PCIe stall time and throughput directly, rather than only asserting the effect via a schematic diagram.
3. Add a same-throughput quality comparison against the raw lossy compressor, using Figure 14’s own data: at the throughput VeriCache achieves at a given $(c,x)$, what accuracy would KVzip/KIVI alone achieve if you tuned their compression ratio down to match VeriCache’s speed, rather than comparing against Full KV only?
4. Locate the aggressive-compression failure boundary experimentally. Sweep $c$ down to $0.05$-$0.1$ and report acceptance length and effective throughput at each point, so readers can see the actual cliff rather than inferring its existence from the small-KL argument.
5. Derive and report the general $G_R/G_L^*$ formula as a function of $\text{BW}_l/\text{BW}_h$ and $T_\text{init\_remote}/T_\text{decode}$, instead of presenting "$4$" as a fixed recommendation — the paper already has the throughput model (Eq. 4) needed to derive this in closed form.

Reproducibility Notes

The paper notes VeriCache is implemented in $\sim 8$K LoC of Python and C++ on top of:

• vLLM as the serving engine. VeriCache subclasses AsyncScheduler and manages its own GPU KV allocations so compressed and transient reload caches can coexist under admission control.
• LMCache as the persistent KV cache storage and transfer layer. VeriCache uses lookup/lookup_compressed to fetch KV pointers and move for cross-tier transfers (CPU↔GPU, storage↔GPU).

Per-layer attention activations route through a vLLM forward hook to Compressor.update for online compressors; offline compressors run before serving (or on idle compute) and apply when the context’s KV is reused.

What is needed to reproduce

To reproduce the headline numbers a reader needs:

1. The vLLM + LMCache codebase at the matching commit, plus the VeriCache patch (the paper does not yet provide a public repo URL — likely available with the camera-ready).
2. Access to the models (Mistral-24B-Instruct-2501, Qwen-32B, Qwen3-Coder-30B, Llama-70B-Instruct). All are public.
3. Hardware: RTX PRO 6000 or H100 NVL ×2. Most academics have $1\times$ H100 access; the Qwen-32B / Mistral-24B numbers should be reproducible on that.
4. The LMCache agentic trace dataset (Hugging Face: sammshen/lmcache-agentic-traces) plus the public benchmarks: ComplexFuncBench, PISanitizer, LongGenBench, GSM8K-Long, SWE-bench Lite.

Verification of lossless guarantee

The paper defines “identical” as identical under greedy decoding except for randomness from hardware nondeterminism. Concretely: KL divergence below $0.01$ nats. This is a meaningful claim and easy to spot-check by running VeriCache vs. Full KV on a long prompt with temperature=0 and diff-ing token IDs.

The hardware nondeterminism caveat is real (FP16 accumulation order on different SMs can change low-bit results); the paper cites Thinking Machines Lab’s recent blog on defeating it as the reference treatment.

What the paper does not include

• Full ablations isolating the contribution of cross-resource staggering vs. high acceptance rate. The authors argue both are needed; an ablation that disables staggering would quantify it.
• Sensitivity to draft length beyond the headline configuration. Figure 8 shows the curve at $4\times$ compaction; other compression ratios are less explored.
• Cost of online compression’s per-layer hook. KVzap’s MLP scoring is cheap but not free; the paper does not separate it from the verify cost.

Suggested replication checklist

If you want to validate VeriCache yourself, here’s a minimum checklist:

1. Sanity check the KL claim. Run any pure-compressed-KV serving (KVzip or KIVI) and a Full-KV baseline on a $\sim 100$-token output. Measure per-token argmax overlap. Confirm KL drifts up linearly with output length.
2. Sanity check the acceptance rate. Reproduce the drafter on compressed KV and measure how many tokens match the full-KV argmax in a single window. Expect $20+$ at $4\times$ compaction.
3. Sanity check the throughput model. Plug your hardware constants into Eq. (3) and predict $T_\text{iter}$. Compare against a single-iteration benchmark.
4. End-to-end run. Once 1–3 line up, run the full VeriCache integration on a small workload (e.g., 50 LMCache-trace samples) and confirm KL stays below $0.01$ nats.

Tooling gaps

A reproducer will want, but the paper doesn’t yet provide:

• A reference Compressor implementation in a public repo.
• Step-by-step instructions for building the staggered scheduler on top of vLLM’s AsyncScheduler.
• A benchmark harness that automates the four-step replication checklist above.

These are the kinds of artifacts that typically appear in the camera-ready or in a follow-on open-source release. As of the arXiv version, replication is plausible but not turnkey.

My Take

VeriCache is one of those papers where the central trick — “the same model on different caches is a great drafter/verifier pair” — is obvious in retrospect but nobody had used it productively before. The lossy-vs-lossless dichotomy in KV cache compression has been a real, painful tradeoff for anyone deploying LLM inference at scale, and the paper kills it cleanly. The functional-correctness collapse on code generation and tool calls (Figure 2 in the paper) is exactly the failure mode I have personally seen in production agentic workloads where someone enabled aggressive token dropping to fit more requests on a node and then started getting silently broken outputs.

What makes the framework genuinely useful — as opposed to merely clever — is the runtime engineering. The lock-step vs. staggered diagram (Figure 6 in the paper) makes the case crisply: a naïve implementation would spike PCIe transfer time to $\sim 20\times$ the iteration window, completely erasing compression’s throughput gain. The cross-resource staggering scheduler is what turns the algorithmic idea into a real speedup. I particularly liked the explicit BW-ring and HBM-ring resource model — it’s the kind of detail that papers often hide, and exposing it makes the system easy to reason about and easy to port to new hardware.

The remote-prefix-caching extension is the part I would have liked to see more of. It is the deployment scenario that most modern LLM services actually hit (shared system prompts, long agentic histories, document RAG), and the existing speculative-with-compressed-KV literature ignores it entirely. The $1.33\text{-}2.11\times$ remote-prefix speedup is more modest than the long-context decoding $4\times$, but it’s $2\times$ on a setting where prior work delivers $1\times$, which is the more important comparison.

The composition with Eagle ($4.35\times$ vs. $3.50\times$ alone) is a nice consistency check that the two acceleration mechanisms are orthogonal. It also implies that VeriCache is not the last word in LLM inference acceleration — there is still per-token compute headroom, and traditional speculative decoding still buys you something on top.

What I would want to see next:

1. Adaptive draft length. A bandit-style scheduler that tunes $x$ per request based on observed acceptance length. The paper flags this; I’d expect a $1.1\text{-}1.3\times$ additional speedup on heterogeneous workloads.
2. Compressor co-design. A compressor that maximizes long-horizon acceptance rather than direct-output quality. The objective is well-defined: maximize $\Pr[\arg\max p_\text{lossy}(\cdot \mid t_{1:k}) = \arg\max p_\text{full}(\cdot \mid t_{1:k})]$ for $k$ up to several tens of tokens.
3. Cross-request reuse of verifies. If two requests in the same batch share a prefix and produce overlapping drafts, in principle a single verify forward pass could check both. This adds combinatorial complexity but could amortize verifies across the batch.
4. Boundary with very aggressive compression. What happens at $c = 0.1$? $c = 0.05$? At some point per-step KL crosses a threshold where acceptance collapses; characterizing that threshold per-model would be useful.
5. Sampling-mode results. The paper covers sampling via standard rejection sampling but the headline numbers are greedy. For agentic workloads with temperature $> 0$, the acceptance rate inevitably drops; quantifying by how much would close an important gap.

The methodological clarity of the paper is also worth calling out. The motivation section (the KL chain-rule argument, the F1-vs-functional-accuracy distinction, the code-generation example) lands harder than most KV-cache papers because it makes the failure mode concrete rather than abstract. The throughput model in Eq. (3) and the per-request model in Eq. (4) are simple enough to plug into a spreadsheet and predict what your own hardware will deliver before you write a line of code. This is the kind of paper that anyone working on LLM serving systems should read end-to-end at least once.

A small critique: the paper doesn’t reconcile its $4\times$ claim with the fact that the ideal speedup from KV-cache compression alone (without the verification correctness guarantee) is already in the $3\text{-}5\times$ range for typical compressors. The framing implies VeriCache is “free correctness on top of lossy compression’s speedup,” but a fair reading of the numbers is that VeriCache approaches but does not quite match what a pure lossy method delivers on the same hardware. That’s still a clear win — you get nearly all the speedup and the correctness guarantee — but the comparison should be explicit.

Where I’d push the design further

A few directions I would explore as immediate extensions, beyond the limitations the paper itself flags:

1. Cross-layer compression mixing. The interface restricts mixing modes (token dropping vs. quantization) across requests, but within a single request one could use different compression at different layers — quantize the first 8 layers heavily, drop tokens in the middle layers, keep last 4 dense. Layer sensitivity to compression varies enormously; a mixed-mode policy could push acceptance higher.
2. Hierarchical verification. Instead of one verify against full KV per round, do two: first against medium-compression KV (cheap), then full KV only on mismatch. This is analogous to multi-level caching and could amortize even further.
3. Speculative prefill. VeriCache focuses on decode, but prefill of long contexts also has compressed-vs-full tradeoffs. A draft-then-verify approach for prefill (with KV computed incrementally and verified once at the end) might apply.
4. Cross-GPU verify sharing in a tensor-parallel deployment. When the model is sharded across GPUs (TP=2 for Llama-70B), the verify forward pass requires all-reduce. Coordinating staggered verifies across TP groups is non-trivial; the paper’s evaluation handles it but the runtime details are thin.

A note on the broader research direction

VeriCache is part of a wider arc in LLM serving research: using approximate methods as drafters in exact-output frameworks. The pattern repeats in:

• Speculative decoding (small model = approximate drafter; large model = exact verifier).
• Cascaded serving (small cheap model first; route hard examples to large model).
• Sparse attention with verification (approximate attention pattern; verify with full attention).

The unifying principle is: “approximate” doesn’t have to mean “lossy at the output level” if you have a verification path. The paper makes this principle concrete for KV cache compression and demonstrates it at production-relevant scale.

I expect more of these “approximation as drafter” frameworks across LLM serving in the next year. Candidates worth watching: approximate MoE routing as drafter for exact routing; approximate KV reuse (CacheBlend-style) as drafter for exact prefill; approximate retrieval as drafter for exact RAG.

Overall, this is the kind of paper I expect to see widely deployed quickly. The implementation is built on existing open-source serving stacks (vLLM, LMCache); the interface is small enough that integrating new compressors is straightforward; and the deployment story applies to two of the most common production scenarios. I would not be surprised to see a production version of this in major LLM serving frameworks within a year.