How long context windows strain the KV cache

The long context kv cache problem isn’t theoretical — it’s the first thing that breaks when you push a model past 32K tokens in production. Every token you add to the context window allocates two new key vectors and two new value vectors per layer, per head, per request. At 128K context on a 70B model, a single request can consume 2-3 GB of GPU memory just for the cache. Multiply that by concurrent users and you hit OOM before you hit throughput limits.

The memory math nobody likes to calculate

Transformer attention computes attention(Q, K, V) = softmax(QK^T / √d)V. During generation, K and V for all previous tokens must be retained because each new token attends to the entire history. The cache grows linearly with sequence length.

For a model with L layers, H heads, head dimension d, and batch size B, the KV cache per token is:

cache_per_token = 2 * L * H * d * sizeof(dtype) * B

A concrete example: Llama-3-70B has 80 layers, 64 heads (grouped-query: 8 KV heads), head dimension 128. At FP16 (2 bytes):

cache_per_token = 2 * 80 * 8 * 128 * 2 = 327,680 bytes ≈ 320 KB per token

At 128K tokens: ~40 GB per request. That’s more than an H100 80GB can hold for a single user, before you even load model weights.

Real implementations use quantization (KV cache in FP8 or INT4), grouped-query attention (fewer KV heads), and paging. But the linear scaling remains. A 1M token context on the same architecture would need ~320 GB per request at FP16 — impossible without aggressive compression or offloading.

Where the memory actually goes

The KV cache isn’t one contiguous allocation. It’s a collection of per-layer tensors, each shaped [batch, seq_len, num_kv_heads, head_dim]. In PyTorch terms:

# Simplified Llama-3-70B cache structure per layer
past_key = torch.empty(batch, seq_len, 8, 128, dtype=torch.float16, device="cuda")
past_value = torch.empty(batch, seq_len, 8, 128, dtype=torch.float16, device="cuda")

With 80 layers, that’s 160 tensors per request. Fragmentation matters. CUDA’s allocator struggles with many medium-sized allocations, especially when sequence lengths vary across requests in a batch. This is why vLLM introduced PagedAttention — it manages KV cache in fixed-size blocks (typically 16 or 32 tokens) backed by a shared memory pool, reducing fragmentation and enabling prefix caching.

But paging adds indirection. Every attention kernel now needs to gather from non-contiguous blocks. The kernel overhead is small per token but compounds at long context. Benchmarks show 5-15% throughput degradation at 32K+ context compared to contiguous allocation, purely from gather/scatter overhead.

Prefill vs decode: different bottlenecks

During prefill, you compute attention over the entire prompt at once. The KV cache is written but not read back — yet. Memory bandwidth dominates. Writing 40 GB of cache for a 128K prefill takes ~200ms on an H100 (1.5 TB/s peak), but real kernels achieve 60-70% of peak. Prefill latency scales quadratically with sequence length due to the QK^T matmul, but cache write scales linearly.

During decode, you read the entire cache for every new token. A 128K context means reading 40 GB per generated token. At 10 tokens/sec, that’s 400 GB/s sustained read bandwidth — exceeding H100’s memory bandwidth. This is why decode throughput collapses at long context: you’re bandwidth-bound, not compute-bound.

The arithmetic intensity (FLOPs/byte) of attention drops as context grows. At short context, QK^T does enough work per byte loaded to saturate compute. At long context, the same Q vector dots against a massive K matrix — you’re streaming K and V from memory with minimal reuse.

Quantization: necessary but not sufficient

FP8 KV cache (E4M3 or E5M2) cuts memory in half with minimal quality loss. INT4 cuts it 4x but requires per-channel or per-token scaling factors, adding metadata overhead and decompression latency in the attention kernel.

# FP8 KV cache with per-tensor scale (simplified)
past_key_fp8 = torch.empty(..., dtype=torch.float8_e4m3fn)
past_value_fp8 = torch.empty(..., dtype=torch.float8_e4m3fn)
key_scale = torch.tensor([1.0], dtype=torch.float32)  # per-tensor or per-channel
value_scale = torch.tensor([1.0], dtype=torch.float32)

# In attention kernel: dequantize on the fly
k = past_key_fp8.to(torch.float16) * key_scale
v = past_value_fp8.to(torch.float16) * value_scale

The decompression happens inside the attention kernel, fused with the matmul. Modern kernels (FlashAttention-3, CUTLASS) support this natively. But quantization doesn’t change the fundamental bandwidth problem — you still read the same number of bytes from memory, just fewer of them. At 128K context with FP8, you’re reading 20 GB/token. Still bandwidth-bound.

Eviction and compression: the pragmatic escapes

Since you can’t fit infinite context in VRAM, production systems use three strategies:

1. Sliding window / local attention. Only retain the last W tokens in KV cache. Older tokens are evicted. Models like Mistral and Gemma use this natively (window=4096 or 8192). For general models, you can implement a sliding cache:

def append_kv_cache(past_key, past_value, new_key, new_value, window_size=8192):
    seq_len = past_key.shape[1]
    if seq_len >= window_size:
        # Drop oldest tokens
        past_key = past_key[:, -window_size+1:]
        past_value = past_value[:, -window_size+1:]
    return torch.cat([past_key, new_key], dim=1), torch.cat([past_value, new_value], dim=1)

Tradeoff: the model genuinely cannot attend to evicted tokens. Quality degrades for tasks requiring long-range retrieval. But memory becomes constant: O(window_size) instead of O(seq_len).

2. KV cache compression. Cluster similar keys, merge them, or use low-rank approximation. H2O, SnapKV, and Quest compress the cache by 2-4x with modest quality loss. The compression runs periodically (every 100-1000 tokens) on CPU or a separate GPU stream.

# Conceptual: compress cache by keeping only "important" tokens
def compress_kv_cache(key, value, keep_ratio=0.5):
    # Score tokens by attention weight magnitude or gradient
    scores = compute_importance_scores(key, value)
    keep_indices = torch.topk(scores, int(key.shape[1] * keep_ratio)).indices
    keep_indices, _ = torch.sort(keep_indices)
    return key[:, keep_indices], value[:, keep_indices]

Tradeoff: compression latency adds to prefill or runs async. If async, you risk using stale compressed cache. Quality loss is task-dependent — needle-in-haystack retrieval suffers first.

3. CPU/SSD offloading. Move cold cache to system RAM or NVMe. FlexGen and DeepSpeed-Inference do this. The attention kernel must fetch blocks on-demand, adding 10-100ms latency per fetch.

# Conceptual: tiered cache with async prefetch
class TieredKVCache:
    def __init__(self, gpu_capacity, cpu_capacity):
        self.gpu_cache = {}
        self.cpu_cache = {}
        self.gpu_capacity = gpu_capacity
    
    def get(self, layer_idx, token_indices):
        # Check GPU, fallback to CPU with async copy
        if layer_idx in self.gpu_cache:
            return self.gpu_cache[layer_idx][:, token_indices]
        else:
            # Trigger async copy from CPU to GPU
            self._prefetch(layer_idx, token_indices)
            return self.cpu_cache[layer_idx][:, token_indices]  # slow path

Tradeoff: unpredictable latency. Unsuitable for latency-sensitive serving. Works for batch/async workloads.

Prefix caching: the free lunch

If multiple requests share a common prefix (system prompt, few-shot examples, RAG context), you can reuse the KV cache for that prefix. vLLM and SGLang implement this with a prefix tree (trie) over token sequences.

# vLLM-style prefix cache lookup
class PrefixCache:
    def __init__(self):
        self.root = PrefixNode()
    
    def find_longest_prefix(self, tokens):
        node = self.root
        matched = []
        for token in tokens:
            if token in node.children:
                node = node.children[token]
                matched.append(token)
            else:
                break
        return matched, node.kv_cache_blocks if node.cached else None

This doesn’t reduce peak memory per request, but it dramatically reduces aggregate memory when many requests share context. A RAG system with a 50K token corpus shared across 100 concurrent users saves ~50 GB vs independent caches.

The catch: prefix caching requires exact token matches. Dynamic templating (timestamps, user IDs) breaks it. You must structure prompts so the static prefix is truly static.

Batch scheduling at long context

Continuous batching (iteration-level scheduling) becomes critical. At short context, you can pack many requests in a batch. At 128K context, each request consumes so much cache that batch size drops to 1-4. The scheduler must:

Prioritize prefill — new requests need cache allocation before they can decode
Evict stalled requests — if a request hits max tokens or times out, reclaim its cache blocks immediately
Defragment — when cache blocks are freed non-contiguously, the allocator must coalesce them for large prefill requests

# Scheduler policy sketch
def schedule_step(requests, cache_allocator):
    # 1. Reclaim from finished/evicted
    for req in requests:
        if req.finished or req.should_evict():
            cache_allocator.free(req.cache_blocks)
            req.cache_blocks = None
    
    # 2. Admit new prefill if space
    for req in pending_prefills:
        blocks_needed = estimate_blocks(req.prompt_tokens)
        if cache_allocator.can_allocate(blocks_needed):
            req.cache_blocks = cache_allocator.allocate(blocks_needed)
            running_prefills.append(req)
    
    # 3. Run decode for active requests
    decode_requests = [r for r in running if r.phase == "decode"]
    if decode_requests:
        run_decode_batch(decode_requests)

Without aggressive reclamation, long-context requests starve new traffic. This is why production serving stacks (vLLM, TGI, SGLang) tie cache lifetime to request lifecycle, not model lifetime.

The hardware reality check

H100 80GB: ~70 GB usable after model weights (70B at FP8 ≈ 70 GB). Fits one 128K request at FP8, maybe two at INT4. Zero headroom for batching.

H100 94GB (NVL): marginally better.

H200 141GB: fits two 128K FP8 requests with room for small batch decode.

Blackwell (B200 192GB): first GPU where 128K context at reasonable batch size (4-8) becomes viable without quantization tricks.

Until then, you’re choosing between: small batch + long context, or large batch + short context. You cannot have both on current hardware without compression or offloading.

What this means for system design

If you’re building a system that must handle long context:

Enforce a hard context limit per request tier. 8K for chat, 32K for RAG, 128K for document analysis — each on separate model instances or with strict quotas.
Implement prefix caching before you need it. Structure prompts so the cacheable prefix is maximal and stable.
Monitor cache memory separately from model memory. Alert on fragmentation ratio (free blocks / total free bytes). If it drops below 0.3, you’ll fail large prefill allocations.
Profile prefill vs decode latency at your target context lengths. Prefill scales quadratically; decode scales linearly in bandwidth. They need different capacity planning.
Test eviction policies on your actual workload. Sliding window loses retrieval; compression loses precision; offloading loses latency. Pick the failure mode your product can tolerate.

The decisive takeaway

Long context kv cache memory grows linearly with sequence length and dominates GPU memory at 32K+ tokens. No software trick eliminates this — quantization halves it, paging reduces fragmentation, prefix caching amortizes it across requests, but the fundamental scaling remains. On current hardware (H100-class), you cannot serve 128K context at meaningful batch sizes without accepting one of three tradeoffs: aggressive quantization (INT4), cache eviction/compression (quality loss), or CPU offloading (latency variance). Design your system around which tradeoff your product can survive, not around the hope that the next kernel optimization will make it free.