06. Inference: The KV Cache Problem — Why Memory Is the New Compute

The Problem

If you've ever managed memory in any production system — malloc fragmentation in a long-running process, buffer pool sizing in a database, page cache pressure on a Linux box — you already have the intuition for this problem.

Here's what happens when an LLM generates text:

For every token in the conversation (both the input you provided and every token the model generates), the model computes a "key" vector and a "value" vector at every layer. These get stored. The model needs ALL of them to generate the next token — it's attending over the entire history.

For a 70B model like Llama 2 70B with a 4K context window:

• Each token stores key + value vectors across 80 layers, each 128 dimensions wide, in BF16

• That's ~640 KB per token, per request

• At 4K tokens: ~2.5 GB per request

• At 128K tokens (modern context windows): ~80 GB per request

An H100 has 80 GB of HBM. Model weights for 70B take ~140 GB (usually sharded across 2+ GPUs). What's left for KV cache determines how many users you can serve concurrently. It's literally: "how many conversations can fit in memory at once?"

This is why KV cache is the #1 constraint in LLM serving economics. Not FLOPs. Not model size. How many concurrent requests can your memory hold.

Why This Is Like — and Unlike — Traditional Caching

If you've built caching layers (Redis, Memcached, CDN caches, CPU caches), the KV cache will feel familiar:

What's similar:

• It's a hot data structure that needs to be close to compute (low latency access)

• It grows with workload (more concurrent requests = more cache)

• Eviction policies matter (what do you drop when memory is full?)

• Tiered placement matters (fast/expensive tier vs slow/cheap tier)

What's fundamentally different:

1. You can't just re-fetch on a cache miss. In Redis, a cache miss means you hit the database — slower but correct. In LLM serving, "evicting" a KV cache entry means that token's representation is gone. You either recompute it (expensive — re-run the entire prefill) or accept degraded quality. There's no "backing store" you can cheaply read from. The cache IS the state.

2. Every entry is accessed on every step. Traditional caches have hot/cold data with power-law access patterns. KV cache? The attention mechanism reads ALL entries on every single token generation. There's no locality in the traditional sense — though there IS recency bias (recent tokens get higher attention weights on average).

3. The working set grows monotonically during a request. In a database buffer pool, pages come and go. KV cache only grows — every new generated token adds to it. It never shrinks until the request completes. This makes capacity planning per-request, not per-time-window.

4. Fragmentation is catastrophic. In malloc, 20% fragmentation is annoying. In GPU HBM, 60% fragmentation means you're serving 2.5x fewer users than you could. At $2-4/GPU-hour, that fragmentation is burning money every second.

The Tech Transformation

Era 1: Static Pre-allocation (pre-2023) — "Reserve for worst case"

The naive approach: when a request starts, allocate a contiguous buffer sized to the maximum sequence length. If your model supports 4K context, reserve 2.5 GB per request regardless of whether the actual conversation is 50 tokens or 4,000.

Result: 60-80% of KV cache memory wasted. Internal fragmentation from over-reservation, external fragmentation from contiguous allocation leaving unusable gaps.

If you've seen this pattern before — it's pre-allocated connection buffers in older web servers, or fixed-size slab allocation with poor size-class matching. Same class of problem.

Era 2: PagedAttention (2023) — "Virtual memory for GPU"

vLLM's insight: this is literally the problem that OS virtual memory solved in the 1960s. The solution is the same — paging.

How it works:

• Split KV cache into fixed-size blocks (default: 16 tokens per block)

• Each request gets a block table (= page table) mapping logical positions to physical memory blocks

• Blocks are allocated on demand as tokens are generated — not reserved upfront

• Blocks can be non-contiguous in physical memory — scattered across HBM

• Shared prefixes use Copy-on-Write — multiple requests reading the same system prompt share physical blocks until one diverges

Results:

• Memory waste: 60-80% → < 4% (only the last partially-filled block per request)

• Throughput vs prior systems: 2-4x (because you can fit 2-4x more concurrent requests)

• Memory sharing (beam search/parallel sampling): up to 55% reduction via CoW

This was the iPhone moment for LLM serving. vLLM went from research paper to industry standard in months. Nearly every production serving system now uses some form of paged KV cache.

But PagedAttention has limits:

• The blocks are still full-precision. No compression.

• All pages are treated equally — no notion of "hot" vs "cold" data.

• The non-contiguous memory layout adds pointer-chasing overhead to attention kernels.

• It doesn't solve the fundamental problem: KV cache still grows linearly with context. At 128K-1M tokens, even perfectly managed cache doesn't fit in HBM.

Era 3: Compression — "Store less per token" (2024-2026)

If you can't fit all the KV cache in HBM at full precision, compress it.

Layer-wise mixed precision (KVTuner, 2025):

Not all layers are equally sensitive to quantization. KVTuner's insight: search the Pareto frontier of quality vs. memory, giving each layer exactly the precision it needs.

• Sensitive layers: 4-bit

• Insensitive layers: 2-3 bit

• Keys need more precision than values (keys determine where to attend; values determine what to read — getting "where" wrong is worse)

• Average across all layers: 3.25 bits — down from 16 bits (BF16). That's a ~5x compression with "nearly lossless" quality.

If you've worked with tiered storage where hot data gets SSDs and cold data gets spinning disk — this is the same principle applied to precision. Each layer gets the "tier" of precision it actually needs.

Transform coding (KVTC, ICLR 2026):

Goes beyond simple quantization. Apply PCA decorrelation to remove redundancy across the feature dimensions, then adaptively quantize, then entropy-code. 20-40x compression. This is image/video compression thinking (DCT, entropy coding) applied to attention states.

Reversible eviction (KVReviver, 2025):

Instead of permanently evicting tokens, store a compressed "sketch" (like a Bloom filter or Count-Min sketch from streaming algorithms). When the evicted token turns out to be important later, reconstruct it from the sketch. 10% of original memory, zero accuracy loss at 2K context.

Channel pruning (SparK, AAAI 2026):

Instead of dropping entire tokens (rows), prune feature dimensions (columns). Remove 80% of channels from unimportant KV entries, dynamically restore them during attention. Orthogonal to token eviction — you can do both.

The compression landscape is converging: multiple techniques stacking together (quantize + prune + evict + sketch), each attacking a different axis of redundancy. Same evolution as video codecs — each generation adds another layer of exploitation.

Era 4: Tiered Placement — "Not all tokens deserve HBM" (2025-2026)

Even with compression, 1M-token contexts strain GPU HBM. The answer: multi-tier memory hierarchy with intelligent placement.

TTKV: Temporal-Tiered KV Cache (2026):

Maps the problem onto human memory — recent events in short-term memory (fast, small), older events in long-term memory (slow, large):

• HBM tier: Recent tokens, full precision, immediate access

• DRAM tier (host CPU): Older tokens, reduced precision, accessed via PCIe with block-wise streaming

• Placement policy: Purely temporal — more recent tokens stay hot. Block-wise streaming overlaps data transfer with attention computation so you don't stall.

Result: 5.94x reduction in cross-tier traffic, 76% latency reduction, 2x throughput on 128K-context tasks.

This is the same tiered-storage playbook from databases (buffer pool → shared storage → cold archive) and CPU caches (L1 → L2 → L3 → DRAM → SSD). The insight isn't novel — what's novel is that we needed it at all. Two years ago, KV caches fit in HBM. Now they don't.

SpeCache (2025):

Full KV cache lives on CPU. A low-bit quantized copy lives on GPU and is used to speculate which tokens will be important on the next step. Only the predicted-important tokens get fetched at full precision from CPU.

It's branch prediction for attention — use a cheap approximation to guess what you'll need, prefetch it, and you're right often enough that the average latency stays low.

RetroInfer (VLDB 2026):

For truly massive contexts (120K-1M tokens), builds a "wave index" data structure over KV cache stored on CPU. Retrieves only the tokens that matter for the current attention computation — sparse retrieval instead of full scan. 4.4x throughput at 120K tokens, 12.2x at 1M.

If you've worked with columnar databases (Parquet, ClickHouse) where query execution skips irrelevant row groups using statistics — this is that pattern for attention.

Era 5: Context-Independent Caching — "Cache the document, not the conversation" (2026)

Here's a subtle problem that all the above doesn't solve:

You cache the KV states for a document (say, a 50K-token PDF). Then a different user asks a question about the same document. Can you reuse the cached KV states?

No — because KV states are context-dependent. The attention pattern for token 5000 in the document depends on what came before it in the full input (system prompt, prior conversation turns). Different surrounding context = different KV states = cached values are stale.

The standard fix: recompute the prefill for the shared document in every new conversation. Expensive.

KV Packet (2026) solves this differently:

• Treat cached documents as immutable "packets" — frozen KV states that never get recomputed

• Wrap each packet in a lightweight trainable adapter (soft tokens) trained via self-supervised distillation

• The adapter bridges the context discontinuity — it learns to adjust the attention patterns to account for the new surrounding context

Zero recomputation. The adapters are tiny (a few trainable tokens per packet boundary). The cached document stays frozen across all users and conversations.

This is conceptually similar to how CDNs serve the same static asset to different clients, with edge logic (adapters) handling per-client variations (headers, compression negotiation) without re-fetching from origin.

Era 6: Disaggregated KV Cache — "Cache as a distributed service" (2025-2026)

Once KV cache becomes too large for one GPU's HBM, and too important to just evict, the natural conclusion: make it a shared, networked resource rather than per-GPU local state.

Mooncake (Moonshot AI / Kimi, 2024-2025):

KV cache becomes a first-class distributed resource. Idle CPU/DRAM/SSD across the cluster forms a distributed cache pool. Prefill nodes compute KV states and push them to the cache. Decode nodes pull from the cache on demand. 525% throughput increase in simulation, 75% more requests in production.

TraCT (2025):

Uses CXL (Compute Express Link) shared memory as a rack-scale KV cache tier. GPUs read/write KV states directly via CXL, bypassing network stacks entirely. 9.8x TTFT reduction.

AIBrix (2025):

Cloud-native distributed KV cache with prefix-aware routing. The router knows which nodes already have which prefixes cached and routes requests accordingly. 50% throughput increase, 70% latency reduction.

The trajectory here is unmistakable: KV cache is evolving from "per-request GPU-local state" to "shared, tiered, networked infrastructure." The same evolution that databases went through (local files → shared disk → distributed storage → tiered caching layers) is happening for KV cache in 2-3 years instead of 20.

The Big Picture: Why This Matters

The KV cache problem is where infra engineers should feel most at home in AI Infra. Every pattern here — virtual memory, tiered storage, compression codecs, distributed caching, eviction policies, prefetching, copy-on-write — is a well-understood concept that's being re-applied to a new substrate (GPU HBM instead of system RAM, attention access patterns instead of filesystem access).

The differences are:

• The "database" (model) reads the ENTIRE cache on every operation (attention over all tokens)

• The working set only grows (never shrinks during a request)

• Latency tolerance is microseconds, not milliseconds (GPU kernels stall on HBM reads)

• The "key" is position in a sequence, not a hash — locality is temporal, not spatial

But the playbook is transferable. If you've built distributed caches, tiered storage, or memory management systems — you already know 70% of what's needed. The other 30% is understanding attention access patterns well enough to make good eviction/placement decisions.

What's Still Unsolved

Optimal eviction under attention. Traditional LRU/LFU don't work because attention patterns are model-dependent and query-dependent. A token that's "cold" for 500 steps might suddenly be critical. We don't have a good general eviction policy that works across models, tasks, and context lengths.

Semantic vs. temporal locality. TTKV bets on temporal (recent = hot). RetroInfer bets on content-based retrieval. SpeCache bets on speculative prediction. Nobody's unified these into a single coherent policy. The right answer is probably "it depends on the workload" — but we don't have the monitoring/profiling tools to know which workload you have.

Cross-request sharing without quality loss. KV Packet shows adapters can bridge context shifts, but the adapters need training per-document. Fully dynamic, zero-overhead cross-request KV sharing with guaranteed quality is still open.

The scheduling-memory co-design problem. The batch scheduler decides which requests run. The memory manager decides which KV blocks to evict. These two systems interact (evicting cache forces recomputation, which delays the schedule) but are optimized separately in every system I've seen. Joint optimization is an open problem.

References

1. Efficient Memory Management for LLM Serving with PagedAttention (Kwon et al., 2023) — https://arxiv.org/abs/2309.06180

2. vAttention: Dynamic Memory Management for Serving DNN Models (2024/2025) — https://arxiv.org/abs/2405.04437

3. KV Packet: Recomputation-Free Context-Independent KV Caching (Chen et al., 2026) — https://arxiv.org/abs/2604.13226

4. TTKV: Temporal-Tiered KV Cache for Long-Context Inference (2026) — https://arxiv.org/abs/2604.19769

5. KVTuner: Layer-Wise Mixed-Precision KV Cache Quantization (Li et al., 2025) — https://arxiv.org/abs/2502.04420

6. KVTC: KV Cache Compression with Transform Coding (ICLR 2026) — https://arxiv.org/abs/2511.01815

7. KVReviver: Reversible Eviction via Sketch Algorithms (2025) — https://arxiv.org/abs/2512.17917

8. SpeCache: Speculative KV Cache Prefetching (2025) — https://arxiv.org/abs/2503.16163

9. RetroInfer: Vector Storage Engine for KV Retrieval (VLDB 2026) — https://arxiv.org/abs/2505.02922

10. Mooncake: KVCache-Centric Disaggregated Architecture (Moonshot AI, 2024) — https://arxiv.org/abs/2407.00079

11. TraCT: CXL Shared Memory KV Cache (2025) — https://arxiv.org/abs/2512.18194

12. AIBrix: Cloud-Native Distributed KV Cache (2025) — https://arxiv.org/abs/2504.03648

13. DMS: Dynamic Memory Sparsification (NeurIPS 2025) — https://arxiv.org/abs/2506.05345