KV-Cache Compression

The KV cache stores the key and value tensors of every past token so an autoregressive model does not recompute them each step. Its size grows linearly with context length, so at long context it — not the weights — dominates memory footprint and the memory-bandwidth cost of decoding. KV-cache compression (token dropping and low-bit quantization of the cache) attacks that footprint directly. The problem it has always had is fidelity: because each generated token attends over the compressed cache, small per-step errors compound, and compressed-KV decoding drifts away from full-cache decoding as generation proceeds — which is fine for chat but breaks exact-output tasks like code generation and tool calling (lossy methods lose 10–30 pp of function-call accuracy).

This is the first KV-cache source compiled in this KB — the lane was a named-but-empty thesis area (the KB held Speculative Decoding and Low-Bit Quantization but no KV-cache page), so this page opens it.

Compression is speculation (VeriCache)

VeriCache (Yao et al., arXiv:2605.17613, May 2026) makes lossy KV compression lossless with one structural move: treat compressed-KV decoding as a drafter and verify its tokens against the full KV cache in parallel. Draft tokens one at a time from the compressed KV sitting in GPU HBM (HBM-bandwidth-bound); verify a block of them against the full KV loaded from CPU/remote storage (interconnect + FLOPs bound); accept the tokens that match full-KV predictions, correct the first mismatch. Output is exact — identical to full-KV decoding, KL < 0.01 nats (attributed to hardware nondeterminism).

Two properties make verification nearly free. First, the drafter and verifier are the same model weights, differing only in KV fidelity — so the drafter is a faithful low-memory copy, not a separate small model, and acceptance is extraordinarily high: ~25–40 accepted tokens per verification round at 4× compression (vs 2–3 for typical small-model drafters). Second, cross-resource staggering interleaves different requests' draft and verify phases so the HBM path and the PCIe/network path stay saturated at once. A uniform compressor interface lets seven existing methods (token-dropping: KVzip, KVzap, ExpectedAttention, SnapKV; quantization: KIVI, KVQuant, RotateKV) drop in as drafters.

The KB-load-bearing reframing: VeriCache collapses "compress the cache" and "speculate then verify" into a single mechanism. That is the strong form of the "levers compound" pattern — not two optimizations stacked, but one optimization that is two levers at once. And it further stacks with small-model speculative decoding (EAGLE/MTP) as an orthogonal axis, reaching up to 4.35× ideal.

Eviction, not just compression (LaProx)

VeriCache keeps every token and makes a lossy view of the cache lossless. Eviction takes the opposite route — it permanently drops tokens to bound the cache — and its hard problem has always been which tokens to drop. LaProx (Mai & Kim, arXiv:2605.07234, May 2026) broadens this KB's KV-cache lane from compression into eviction with a different framing of that question.

Prior eviction methods score a token by local, head-wise attention weights — how much attention it received — and decide per head. LaProx argues that ignores value representations, the output projection, and inter-head interactions, and reformulates eviction as an output-aware, layer-wise matrix-multiplication approximation: it models the multiplicative interaction between attention maps and projected value states to estimate each token's actual contribution to the layer output. Building on that metric, it produces the first globally-comparable importance score, so tokens are selected model-wide rather than by local, per-head decisions.

The headline magnitude: LaProx maintains model performance at just 5% KV-cache retention — a ~20× cut — across 19 datasets (LongBench + Needle-In-A-Haystack), and reduces accuracy loss up to 2× vs prior SOTA under extreme compression, with minimal overhead. Where VeriCache is a lossless throughput mechanism, LaProx is a bounded-lossy footprint mechanism — the two attack the KV-memory wall from opposite ends (recover exact quality at full retention vs hold quality at 5% retention). Eviction is lossy by construction, so 5% is aggressive and task-dependent; the reported wins are on LongBench / NIAH families, not separately characterized for reasoning-heavy or agentic long-context workloads.

Key Claims

• Lossy KV-cache compression can be made bit-exact-lossless by drafting from the compressed cache and verifying against the full cache in parallel — Output identical to full-KV decoding (KL < 0.01 nats), 100% completion on long-generation tasks, where a lossy baseline (KVzip at 4× compression) shows ~14.4 nats KL on Llama-70B. Evidence: moderate (preprint, self-measured on the authors' hardware, no independent reproduction) (VeriCache)
• Throughput improves ~2.4–2.7× over full-KV decoding, up to ~4.3× composed — Long-context decoding: Llama-70B 2.73× (256 vs 102 tok/s), Mistral-24B 2.41×, Qwen-32B 1.92×; peak 4.26× (Qwen-32B) when composed with a traditional drafter; remote prefix caching gives 2.11× / 1.75× / 1.33×. Evidence: moderate (preprint, self-measured) (VeriCache)
• Same-model KV-fidelity drafting yields far higher acceptance than small-model drafting — ~25–40 accepted tokens/round vs 2–3, so verification amortizes across many more emitted tokens; ~0.8 acceptance rate at 4× compression, draft length 30. Evidence: moderate (VeriCache)
• Compression and speculation compose with small-model speculative decoding — With EAGLE/MTP, up to 4.35× ideal speedup (vs 3.50× VeriCache alone, 1.78× EAGLE alone) — orthogonal optimization dimensions. Evidence: moderate (VeriCache)
• KV-cache eviction can hold model quality at 5% retention when tokens are scored output-aware and globally — LaProx reformulates eviction as an output-aware, layer-wise matrix-multiplication approximation (modeling the attention-map × projected-value-state interaction, incl. inter-head effects) and assigns the first globally-comparable importance score for model-wide token selection. It maintains model performance at only 5% of the KV cache (~20× cut) across 19 datasets (LongBench + NIAH), outperforming prior eviction works across all tested configurations. Broadens the KB lane from compression into eviction. Evidence: moderate (preprint; abstract + reported metrics; LongBench/NIAH families, no independent reproduction) (LaProx, arXiv:2605.07234)
• Global, output-aware scoring cuts accuracy loss up to 2× under extreme compression — vs prior SOTA eviction baselines, with minimal overhead. The move is from local, head-wise attention-weight averaging (which ignores value representations and the output projection) to a single global scale — the correction that lets eviction survive aggressive retention cuts. Evidence: moderate (preprint; self-reported) (LaProx, arXiv:2605.07234)

Benchmarks & Data

Why this matters for the house thesis

VeriCache is a pure software / serving-layer change — no new weights, no new silicon — that recovers exact quality at multiples of throughput. It is a clean instance of the Inference & Token Economics cost decomposition (~103.7% of the price decline attributed to software/architecture, ~−0.9% to hardware): the gain comes entirely from how the cache and the interconnect are scheduled, on unchanged hardware. And by making compression be speculation it is the strongest single datapoint in this KB for the "efficiency levers compound" pattern — though see the conflict noted below, which bounds that pattern.

Open Questions

• VeriCache keeps the full KV on CPU/storage in addition to the compressed GPU copy — storage overhead rises. What is the crossover context length where that overhead outweighs the throughput win?
• Draft length is static per workload; adaptive per-request draft-length policies (for heterogeneous compressors) are unexplored.
• Existing compressors optimize serving accuracy, not acceptance-rate at long horizons — does a compressor designed for acceptance push the 25–40-token/round figure higher?
• Current scope assumes uniform bit-precision across layers/tokens and one compression method per deployment; the heterogeneous case (mixed precision, KV-reuse methods like CacheBlend) is not covered.
• Eviction (LaProx) vs lossless compression (VeriCache): the two coexist on this page but were not measured against or composed with each other. Does globally-scored eviction to 5% precede a VeriCache-style compress-and-verify step (evict first, then make the residual lossless), and what is the combined quality/throughput envelope? And does LaProx's global, output-aware score make a better VeriCache drafter than the local-attention compressors it currently wraps? Open.
• LaProx overhead and workload coverage: "minimal overhead" is stated but the exact score-computation cost vs simpler head-wise heuristics needs the full text, and the 5%-retention result is characterized on LongBench / NIAH — not on reasoning-heavy or agentic long-context workloads where token importance may be less concentrated. Open.
• The compound-vs-conflict boundary: VeriCache composes cleanly with EAGLE/MTP, but a separate line (arXiv:2505.22179, ingested + resolved 2026-07-24) shows speculative decoding and low-bit weight quantization interfere for tree drafts, fixed by converting tree → sequence drafts (2.78×). Where does KV-cache speculation sit relative to that interference — is it immune because drafter and verifier share weights, or does the same tree-vs-sequence tension recur? Still open.

Related Concepts

• Speculative Decoding — VeriCache is a speculative-decoding method whose drafter is a compressed KV cache rather than a small model; composes with small-model drafters
• Low-Bit Quantization — KV quantization is one of the compression families VeriCache wraps; the two lanes share the "trade fidelity for memory" question
• Inference & Token Economics — a software-only throughput multiplier on unchanged silicon; the mechanism behind the cost decomposition

Related Entities

None yet — VeriCache's author roster overlaps the LMCache / U. Chicago systems-for-LLM group, which is not a tracked entity in this KB.

Backlinks

Pages that reference this concept:

• Speculative Decoding
• Low-Bit Quantization
• Inference & Token Economics

Changelog

• 2026-07-23 — Created from VeriCache (arXiv:2605.17613), the first KV-cache source in this KB. Records the compression-as-drafter / full-KV-as-verifier mechanism, lossless output (KL < 0.01 nats), 2.4–2.7× (up to 4.35× composed) throughput, and ~25–40 accepted tokens/round. Represents "compression IS speculation" as the strong form of the levers-compound pattern, and flags the arXiv:2505.22179 spec-decoding × quantization conflict as the boundary on that pattern (evidence pending full read).
• 2026-07-24 — Broadened the lane from compression into eviction. Compiled LaProx (arXiv:2605.07234): added an "Eviction, not just compression" section, two Key Claims, and two benchmark rows — KV eviction reformulated as an output-aware, layer-wise matrix-multiplication approximation with the first globally-comparable token importance score; maintains performance at 5% KV-cache retention across 19 datasets (LongBench + NIAH), up to 2× accuracy-loss reduction vs prior SOTA under extreme compression. Added the source + a kv-cache-eviction tag to frontmatter and two eviction-specific open questions. Separately, updated the compound-vs-conflict open question: arXiv:2505.22179 is now ingested + resolved (tree → sequence, 2.78×), no longer "not yet ingested". All LaProx numbers preprint-grade (abstract + reported metrics).