Block Allocation and Eviction Policies
What you'll learn: How inference engines intelligently allocate GPU memory blocks for KV cache and decide which blocks to evict when memory runs out.
The Memory Management Challenge
When serving LLMs with paged attention, your GPU memory is divided into fixed-size blocks that store key-value cache pages. But GPU memory is finite—you can't keep every sequence's KV blocks in VRAM forever. You need smart policies to decide:
- Where to allocate new blocks when a request arrives
- What to evict when GPU memory fills up
- When to swap back evicted blocks from CPU memory
Allocation Strategies
First-fit allocation scans for the first available free block—simple and fast. Best-fit finds the smallest sufficient space, reducing fragmentation. Most inference engines use a free list or bitmap to track available blocks in constant time.
When requests share prefixes (thanks to copy-on-write), allocation prioritizes blocks that can be shared, maximizing memory reuse.
Eviction Policies
When GPU memory is full, the engine must evict blocks to CPU RAM:
- LRU (Least Recently Used): Evict blocks not accessed recently—assumes past patterns predict future use
- Priority-based: Evict blocks from lower-priority requests first
- Prefix-aware: Avoid evicting shared prefix blocks that multiple sequences reference
Swapping Back on Demand
When computation needs an evicted block, the engine swaps it back from CPU to GPU asynchronously. Modern engines overlap this transfer with computation on other blocks to hide latency, similar to how operating systems handle virtual memory page faults.
Key Takeaway: Effective block allocation and eviction policies treat GPU memory like virtual memory—allocating intelligently, evicting strategically (often using LRU), and swapping on demand to maximize throughput while keeping latency predictable.