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.
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.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | GQA (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}')
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.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Using 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)
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.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Swapping consumes host pinned RAM and PCIe bandwidth. | |
| Trade-off 2 | Recomputing 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"
Implementation & Guardrails (4).
Enable Chunked Prefill (max_num_batched_tokens = 2048) and disaggregated prefill/decode pools.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Chunked 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,
}
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.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Saves 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.
Llm Kv Cache Pagedattention — Normal → Load / Fault → Recovery
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.
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.
Putting LLM KV-Cache Eviction & PagedAttention Together
- Hash
(parent_hash, tuple(token_ids))to identify reusable 16-token prefix blocks. - On hit: if
ref_count == 0, remove fromeviction_lruand incrementref_count. - On alloc miss: pop from
free_blocksor evict oldest entry fromeviction_lru.
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.
Make the trade-off yourself.
Practice Check
Test your understanding
When is ACID Transaction Fundamentals the right default for a production team?
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.
