Skip to main content
← PROBLEMS / AI-SYSTEMS
An end-to-end domain learning journey

LLM KV-Cache Eviction
& PagedAttention.

You are designing the inference engine memory manager for a Llama-3-70B (GQA, 80 layers, 8 KV heads, head_dim=128, FP16) serving cluster running on 8x H100-80GB GPUs (TP=8). Under continuous batching with mixed workloads (512-token chat + 32k-token RAG prompts with shared system prefixes), naive contiguous KV allocation wastes 68% of GPU HBM and triggers OOM crashes at 40 concurrent requests. Design a PagedAttention block manager and KV cache eviction/preemption policy.
Start the journey5 stages
Loading diagram…
LLM KV-Cache Eviction & PagedAttention architecture sketch diagram
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

You are designing the inference engine memory manager for a Llama-3-70B (GQA, 80 layers, 8 KV heads, head_dim=128, FP16) serving cluster running on 8x H100-80GB GPUs (TP=8). Under continuous batching with mixed workloads (512-token chat + 32k-token RAG prompts with shared system prefixes), naive contiguous KV allocation wastes 68% of GPU HBM and triggers OOM crashes at 40 concurrent requests. Design a PagedAttention block manager and KV cache eviction/preemption policy.

From patterns to decisions.

You are designing the inference engine memory manager for a Llama-3-70B (GQA, 80 layers, 8 KV heads, head_dim=128, FP16) serving cluster running on 8x H100-80GB GPUs (TP=8). Under continuous batching with mixed workloads (512-token chat + 32k-token RAG prompts with shared system prefixes), naive contiguous KV allocation wastes 68% of GPU HBM and triggers OOM crashes at 40 concurrent requests. Design a PagedAttention block manager and KV cache eviction/preemption policy.

01
AI-SYSTEMS · STAGE 01L4 · FUNDAMENTALS

Each token requires 320 KB.

Each token requires 320 KB cluster-wide (40 KB/GPU under TP=8); reserving 32,768 tokens per request locks 10.48 GB even for a 200-token prompt.

ChoiceWhat it buysWhat it costs
Trade-off 1GQA (8 KV heads vs. 64 query heads) already cuts KV size by 8x compared to MHA, making PagedAttention even more impactful.

Step 1

Compute 2 * layers * kv_heads * head_dim * 2 bytes = 327,680 bytes/token.

Step 2

Multiply by max_seq_len = 32,768 -> 10.48 GB per request.

Step 3

Divide 460 GB available KV HBM by 10.48 GB -> 43 max requests.

Alternative 1

Quantize KV cache to FP8 (E4M3) to halve memory footprint per token to 160 KB.

Failure Mode 1

Internal fragmentation wastes up to 95% of reserved HBM on short chat prompts.

bytes_per_token = 2 * 80 * 8 * 128 * 2  # K+V, layers, kv_heads, head_dim, fp16
max_req_bytes = bytes_per_token * 32768
total_kv_hbm = 460 * (1024 ** 3)
print(f'Per token: {bytes_per_token/1024:.0f} KB, Max seq: {max_req_bytes/1e9:.2f} GB, Max batch: {total_kv_hbm // max_req_bytes}')
02
AI-SYSTEMS · STAGE 02L5 · APPLIED DESIGN

Maintain a free list, a.

Maintain a free list, a cached_blocks OrderedDict for ref_count == 0 blocks (LRU), and a Block table tracking ref_count.

ChoiceWhat it buysWhat it costs
Trade-off 1Using 64-bit hashes risks rare collisions; production engines (vLLM/SGLang) store the token tuple or 128-bit xxhash to verify exact match.

Step 1

Hash (parent_hash, tuple(token_ids)) to identify reusable 16-token prefix blocks.

On hit

if ref_count == 0, remove from eviction_lru and increment ref_count.

On alloc miss

pop from free_blocks or evict oldest entry from eviction_lru.

Alternative 1

Use a Radix Tree (SGLang RadixAttention) for variable-length prefix matching.

Failure Mode 1

Forgetting to remove old_hash from hash_to_id upon LRU eviction causes stale block corruption.

from collections import OrderedDict
from dataclasses import dataclass

@dataclass
class PhysicalBlock:
    block_id: int
    block_hash: int | None = None
    ref_count: int = 0

class PrefixBlockAllocator:
    def __init__(self, num_blocks: int):
        self.blocks = [PhysicalBlock(i) for i in range(num_blocks)]
        self.free_ids = list(range(num_blocks))
        self.hash_to_id: dict[int, int] = {}
        self.evict_lru: OrderedDict[int, int] = OrderedDict()

    def allocate(self, block_hash: int | None = None) -> PhysicalBlock | None:
        if block_hash is not None and block_hash in self.hash_to_id:
            bid = self.hash_to_id[block_hash]
            blk = self.blocks[bid]
            if blk.ref_count == 0:
                self.evict_lru.pop(bid, None)
            blk.ref_count += 1
            return blk
        if self.free_ids:
            bid = self.free_ids.pop()
        elif self.evict_lru:
            bid, _ = self.evict_lru.popitem(last=False)
            old_hash = self.blocks[bid].block_hash
            if old_hash is not None:
                self.hash_to_id.pop(old_hash, None)
        else:
            return None  # Trigger LIFO preemption
        blk = self.blocks[bid]
        blk.block_hash = block_hash
        blk.ref_count = 1
        if block_hash is not None:
            self.hash_to_id[block_hash] = bid
        return blk

    def free(self, bid: int) -> None:
        blk = self.blocks[bid]
        blk.ref_count -= 1
        if blk.ref_count == 0:
            if blk.block_hash is not None:
                self.evict_lru[bid] = blk.block_hash
            else:
                self.free_ids.append(bid)
03
AI-SYSTEMS · STAGE 03L6 · SCALE & TRADE-OFFS

Preempt LIFO (newest request) so.

Preempt LIFO (newest request) so older requests finish and release all their blocks; recompute short sequences and swap long sequences.

ChoiceWhat it buysWhat it costs
Trade-off 1Swapping consumes host pinned RAM and PCIe bandwidth.
Trade-off 2Recomputing consumes GPU tensor cores and delays other running decode steps.

Step 1

LIFO prevents starvation and maximizes request completion rate.

Step 2

Compare PCIe swap time (KV_bytes / 64 GB/s) against prefill compute time (2 * params * tokens / FLOPS).

Alternative 1

Chunked prefill to interleave recomputation with active decode tokens.

Failure Mode 1

Evicting the oldest sequence (LRU) wastes the most accumulated decode work and risks livelock.

def choose_preemption_mode(seq_len: int, kv_bytes_per_token_gpu: int = 40960) -> str:
    swap_ms = (seq_len * kv_bytes_per_token_gpu) / (64e9) * 1000
    # H100 TP=8 prefill ~ 12,000 tok/s for 70B FP16
    recompute_ms = (seq_len / 12000.0) * 1000
    return "SWAP" if swap_ms < recompute_ms and seq_len >= 1024 else "RECOMPUTE"
04
AI-SYSTEMS · STAGE 04L6 · SCALE & TRADE-OFFS

Implementation & Guardrails (4).

Enable Chunked Prefill (max_num_batched_tokens = 2048) and disaggregated prefill/decode pools.

ChoiceWhat it buysWhat it costs
Trade-off 1Chunked prefill slightly increases TTFT for 32k prompts in exchange for smooth <35 ms ITL for all concurrent decode users.

Step 1

Split 32k-token prefills into 2,048-token chunks piggybacked onto decode batches.

Step 2

Cap total batched tokens per iteration to bound step latency under 35 ms.

Alternative 1

Prefill-Decode disaggregation (Mooncake/DistServe) over RDMA InfiniBand.

Failure Mode 1

Running a single 32k prefill unchunked stalls all 500 decode streams for >2 seconds.

scheduler_config = {
    "enable_chunked_prefill": True,
    "max_num_batched_tokens": 2048,
    "max_num_seqs": 256,
    "watermark_blocks_ratio": 0.05,
}
05
AI-SYSTEMS · STAGE 05L7 · STAFF / PRINCIPAL

All 4 sequences share the.

All 4 sequences share the 256 prompt physical blocks (ref_count=4). Only the final partially-filled block is copied on first decode token divergence.

ChoiceWhat it buysWhat it costs
Trade-off 1Saves 75% of prompt KV memory (`3 * 163 MB` per request) at the cost of a single 1-block copy on divergence.

Step 1

Increment ref_count on all 256 prompt blocks to 4.

Step 2

When sequence 1 writes token 4097 into a shared tail block (ref_count > 1), allocate 1 new block, copy the existing tokens via cudaMemcpyAsync, and decrement old ref_count.

Alternative 1

Eagerly copy only the last partial block at fork time.

Failure Mode 1

Mutating a shared physical block in-place without checking ref_count > 1 corrupts sibling sequences.

def write_token_cow(seq_blocks: list[PhysicalBlock], allocator: PrefixBlockAllocator) -> PhysicalBlock:
    tail = seq_blocks[-1]
    if tail.ref_count > 1:
        new_blk = allocator.allocate(block_hash=None)
        # GPU kernel copies existing tokens from tail.block_id -> new_blk.block_id
        allocator.free(tail.block_id)
        seq_blocks[-1] = new_blk
        return new_blk
    return tail

Theory & Tips and Tricks

Practical heuristics & interview traps

  • 01Interview anchor: Partition KV caches into fixed-size 16-token physical blocks mapped via a block table, and handle memory pressure with prefix-aware LRU eviction, swap-to-CPU, or recomputation.
  • 02Trade-off tip: Swapping consumes host pinned RAM and PCIe bandwidth.
  • 03Trade-off tip: Recomputing consumes GPU tensor cores and delays other running decode steps.
  • 04Watch out for: Running a single 32k prefill unchunked stalls all 500 decode streams for >2 seconds.
Behavioral Progression · Llm Kv Cache Pagedattention

Llm Kv Cache Pagedattention — Normal → Load / Fault → Recovery

Send Request
1. Normal Request Ingress
Traffic: 1x baseline · Latency (p99): 4 ms
Process State
2. Core Execution & State Lookup
Traffic: 1x baseline · Latency (p99): 9 ms
Inject 10x Spike
3. Scale Spike / Failure Injection
Traffic: 10x burst · Latency (p99): 185 ms

Partition KV caches into fixed-size 16-token physical blocks mapped via a block table, and handle memory pressure with prefix-aware LRU eviction, swap-to-CPU, or recomputation.

Synthesis / One connected design

Putting LLM KV-Cache Eviction & PagedAttention Together

Partition KV caches into fixed-size 16-token physical blocks mapped via a block table, and handle memory pressure with prefix-aware LRU eviction, swap-to-CPU, or recomputation.

A candidate architecture, not a universal answer

Putting LLM KV-Cache Eviction & PagedAttention Together

Step 1
Step 2
Step 3
  1. Hash (parent_hash, tuple(token_ids)) to identify reusable 16-token prefix blocks.
  2. On hit: if ref_count == 0, remove from eviction_lru and increment ref_count.
  3. On alloc miss: pop from free_blocks or evict oldest entry from eviction_lru.
Enable Chunked Prefill (`max_num_batched_tokens = 2048`) and disaggregated prefill/decode pools.
Interview Readiness Check

Enable Chunked Prefill (max_num_batched_tokens = 2048) and disaggregated prefill/decode pools.

Walk through bottlenecks, back-of-the-envelope math, and failure recovery.

Practice / Explain the consequences

Make the trade-off yourself.

Practice Check

Test your understanding

Question 1 of 3

When is ACID Transaction Fundamentals the right default for a production team?

Key takeaway

LLM KV-Cache Eviction & PagedAttention

Partition KV caches into fixed-size 16-token physical blocks mapped via a block table, and handle memory pressure with prefix-aware LRU eviction, swap-to-CPU, or recomputation.