Reuse, Evict, or Limit Earlier Context

In the previous lesson, you learned how PagedAttention eliminates fragmentation by dividing GPU VRAM into fixed-size physical blocks and mapping each request’s logical token positions to those blocks through a block table. A request now allocates only the blocks it needs, on demand.

That solved allocation. Now we face three new problems that appear when you serve real workloads at scale:

1. Redundant work — Many requests share the same beginning (system prompts, chat history, few-shot examples, or a shared document). Without intervention, each request recomputes the exact same prefill and stores the exact same KV blocks.

2. Memory pressure — Even with efficient paging, GPU VRAM is finite. When the free list is empty, new tokens cannot be placed anywhere. The system must decide: evict an existing request, swap its blocks to CPU RAM, or prune less-important tokens.

3. Unbounded growth — In a long conversation or document stream, the KV cache grows linearly with every new token. At some point, even a 128K or 1M context window is not enough — or the memory cost becomes prohibitive.

This lesson teaches three standard techniques that production engines (vLLM, SGLang, TensorRT-LLM, llama.cpp) use to handle these problems:

Technique	Problem It Solves	Core Mechanism
Prefix Caching (Automatic Prefix Reuse)	Redundant prefill + duplicate storage	Content-addressed physical blocks + reference counting + Copy-on-Write
Cache Eviction / Preemption	VRAM exhaustion	LRU request eviction, token-level pruning (Attention Sinks, Heavy Hitters), PCIe swapping to host RAM
Sliding-Window Attention	Unbounded per-request cache growth	Fixed rolling window W; each query attends only to the most recent W tokens

---

1. Prefix Caching: Automatic Prefix Reuse

1.1 Why Prefixes Repeat in Practice

Before defining the mechanism, look at where shared prefixes come from in real workloads:

Source	Typical Length	Example
System prompt	500–2,000 tokens	“You are a helpful assistant. Follow these guidelines…”
Multi-turn chat history	1,000–50,000+ tokens	Prior user/assistant turns in a long conversation
Few-shot examples	500–5,000 tokens	“Here are 10 examples of the task…”
Shared document / RAG context	2,000–100,000+ tokens	A PDF, codebase, or knowledge base prepended to every query

In a chat application serving hundreds of concurrent users, the same system prompt may be prepended to every single request. Without prefix caching, the engine recomputes the prefill for that system prompt on every request and allocates separate physical blocks for each copy — wasting both compute and memory.

1.2 How Prefix Caching Works with PagedAttention

PagedAttention gives us the building blocks: physical blocks are content-addressed immutable pages. Each block holds B_size tokens (typically 16 or 32). The KV data inside a physical block never changes once written — it is the exact key/value vectors produced by the model for those token positions.

This immutability enables automatic prefix reuse:

When Request B shares a prefix with Request A, the engine does NOT recompute prefill and does NOT allocate new GPU blocks. It simply points Request B’s block table entries to Request A’s existing physical blocks and increments their reference count.

Step-by-Step Mechanism

Request A arrives: "System prompt (1500 tokens) + User query A (100 tokens)"
→ Prefill computes 1600 tokens
→ Allocates physical blocks #100 through #200 (approx 100 blocks of 16 tokens)
→ Block table A = [100, 101, 102, ..., 199]
→ Reference count of each block = 1

Request B arrives: "System prompt (1500 tokens) + User query B (100 tokens)"
→ Engine detects: first 1500 tokens (94 blocks) match Request A exactly!
→ For logical blocks 0–93: block table B = [100, 101, ..., 193]  ← SAME physical blocks!
→ Reference count of blocks 100–193 increments to 2
→ Only logical blocks 94–99 (the unique 100 user tokens) need new prefill + new blocks
→ Block table B = [100, 101, ..., 193, 201, 202, ..., 206]

Key insight: Prefill latency for cached tokens drops to ZERO. The engine only computes the unique suffix.

1.3 Copy-on-Write (CoW) for Divergent Generation

What happens when Request B starts generating tokens and its sequence diverges from Request A?

Request A generates token 1601 → writes to Physical Block #200, slot 1
Request B generates token 1601 → wants to write to Physical Block #193, slot 15 (last slot)

But Physical Block #193 has ref_count = 2 (shared by A and B). If B writes to it, A’s cache would be corrupted!

Solution — Copy-on-Write:

1. Before writing to a physical block with ref_count > 1, the engine allocates a fresh physical block from the free list.
2. Copies the entire block’s contents to the new block.
3. Decrements the old block’s ref_count.
4. Updates Request B’s block table to point to the new block.
5. Request B now has exclusive ownership of the new block; Request A continues using the original.

This is exactly how OS virtual memory handles fork() — pages are shared until one process writes, then a private copy is made.

Result: Prefix caching is completely safe. Shared blocks are read-only. The moment a request needs to write, it gets its own private copy.

1.4 Reference Counting and Block Lifetime

Each physical block maintains a reference count (integer ≥ 0):

• ref_count = 0 → Block is free (in the global free list).
• ref_count = 1 → Block is owned by exactly one request; that request can write to it directly (no CoW needed).
• ref_count > 1 → Block is shared; writes trigger CoW.

When a request finishes (completes or is evicted), the engine walks its block table and decrements ref_count for every physical block. Any block whose count reaches 0 returns to the free list.

Practical note: vLLM and SGLang implement prefix caching by hashing the prompt token sequence (or the sequence of physical block IDs) and looking up matches in a prefix cache dictionary (typically an LRU cache of prefix → block sequence mappings). The lookup is O(prefix length) and happens before prefill starts.

---

2. Cache Eviction and Preemption: When Memory Fills Up

Even with PagedAttention and prefix caching, GPU VRAM is finite. The free list eventually empties. New incoming requests (or existing requests generating new tokens) need physical blocks, but none are available.

The engine must make space. This is cache eviction (also called preemption in scheduler terminology).

2.1 Request-Level Eviction Policies

The coarsest granularity: evict an entire request’s KV cache at once.

LRU (Least Recently Used) Eviction

• Track the last time each request was active (received a token or generated a token).
• When space is needed, pick the request with the oldest last_active_timestamp.
• Pros: Simple, fair, matches intuition that idle conversations are less likely to resume soon.
• Cons: Does not distinguish between a short idle request (cheap to recompute) and a long idle request (expensive to recompute).

Priority-Based Eviction

• Assign each request a priority (e.g., interactive chat > batch job > background summarization).
• Evict lowest-priority requests first.
• Pros: Protects latency-sensitive traffic.
• Cons: Requires explicit priority assignment; can starve low-priority work indefinitely.

Recomputation Cost

When a request is evicted, its prompt must be recomputed from scratch when (or if) the user resumes the conversation.

• Cost = prefill FLOPs for the full prompt length.
• For a 10K token prompt on a 7B model: ~140 TFLOPs → ~0.9 seconds at 150 TFLOPS.
• Key tradeoff: Eviction saves VRAM now but imposes a latency penalty later.

---

2.2 Swapping: Moving Blocks to CPU Host RAM (PCIe Offloading)

Instead of discarding evicted blocks, swap them to CPU host memory over PCIe. When the request resumes, swap them back.

How Swapping Works

1. Eviction decision: Scheduler selects victim request(s) based on LRU, priority, or recomputation cost.
2. Copy to host: Engine issues asynchronous PCIe DMA transfers to copy the victim’s physical blocks from GPU HBM → CPU RAM (pinned memory).
3. Free GPU blocks: Victim’s physical blocks return to GPU free list; block table entries are cleared or marked “swapped”.
4. Resume (swap-in): When request resumes, engine allocates new GPU blocks, copies data back (CPU RAM → GPU HBM), restores block table.
5. Continue decode: Request picks up exactly where it left off — no recomputation needed.

PCIe Bandwidth Reality Check

PCIe Generation	Lanes	Theoretical Peak	Realistic Sustained
Gen 3	x16	15.75 GB/s	~12 GB/s
Gen 4	x16	31.5 GB/s	~25 GB/s
Gen 5	x16	63 GB/s	~50 GB/s

Typical server (2024–2025): PCIe Gen4 x16 → ~25 GB/s sustained transfer.

Transfer time for a 1 GiB cache:

Time = 1 GiB / 25 GB/s = 0.04 s = 40 ms

Compare to recomputing 8,192 tokens (1 GiB at 128 KiB/token) on a 7B model at 150 TFLOPS:

FLOPs = 2 × 8,192 × 7×10⁹ = 114.7 TFLOPs
Time = 114.7 / 150 = 0.76 s = 760 ms

Swapping is ~19× faster than recomputation for this example. (See Exercise 3 for a detailed worked comparison.)

Swapping Overhead Considerations

• CPU RAM capacity: Must have enough host memory to hold swapped-out caches. A 32 GiB GPU cache pool may need 64–128 GiB host RAM for swap space.
• Pinning: Host buffers must be pinned (page-locked) for DMA; this reduces OS pageable memory.
• Asynchronous overlap: Engines overlap swap-out with decode of other requests; swap-in can be pipelined with prefill of the resumed request’s unique suffix.

---

2.3 Token-Level Eviction: Pruning and Compression (Within a Request)

Instead of evicting entire requests, remove individual tokens from a request’s KV cache to free a small number of blocks while keeping the request alive. This is cache pruning or cache compression.

Attention Sinks (StreamingLLM — Xiao et al., 2023)

Observation: In many decoder-only models, the first few tokens (typically 4) absorb a disproportionate amount of attention mass across all subsequent positions, regardless of their semantic content. These are called attention sinks.

Mechanism: Always keep the first N_sink tokens (e.g., 4) in the cache. When evicting, never remove these. Evict from the middle of the sequence (after the sinks, before the recent window).

Why it works: The sinks act as a “global accumulator” that stabilizes attention distributions. Removing them causes model collapse (perplexity explodes). Keeping just 4 tokens preserves most quality while freeing the middle.

Heavy Hitters (H2O — Zhang et al., 2023)

Observation: A small subset of tokens — recent tokens + tokens with high accumulated attention scores — contribute most to the model’s output quality.

Mechanism:

1. Maintain a running sum of attention weights each token receives across layers and heads.
2. Define a budget B (e.g., keep 2,000 tokens total).
3. Always keep the most recent R tokens (e.g., 512).
4. Fill the remaining B - R slots with the highest-scoring “heavy hitter” tokens from the middle.
5. Evict the rest.

Result: H2O can compress a 128K context to a few thousand tokens with minimal quality loss on long-context benchmarks.

Comparison: Request-Level vs Token-Level Eviction

Dimension	Request-Level Eviction	Token-Level Pruning (Sinks / Heavy Hitters)
Granularity	Entire request	Individual tokens within a request
Quality impact	Zero (exact restore via recompute or swap)	Small (approximate — some context lost)
VRAM freed per action	Large (entire cache)	Small (few blocks at a time)
Latency to resume	High (recompute prefill) or medium (swap-in)	Zero (request never paused)
Implementation complexity	Low (block table walk + free)	High (attention tracking, score maintenance)
Typical use case	Memory pressure, idle sessions	Continuous streaming, fixed cache budget

---

3. Sliding-Window Attention: Bounding Cache Growth

3.1 The Core Idea

Sliding-Window Attention (SWA) changes the attention pattern: each query position attends only to the most recent W tokens (the “window”), where W is a fixed hyperparameter (e.g., 4,096 or 8,192).

This is not an eviction policy — it is a model architecture choice. The model is trained with this attention pattern. At inference time, the KV cache physically cannot grow beyond W tokens per layer.

3.2 Mechanics: Circular Rolling Buffer

For each layer, the KV cache is a circular buffer of size W:

Window size W = 4,096 tokens
Layer KV buffer = array[W] of (Key, Value) per head

Token t arrives:
  slot = t mod W
  buffer[slot] = (K_t, V_t)   // overwrites token t-W

Visual trace (W = 8):

t=0:  [K0,V0]  _  _  _  _  _  _  _
t=1:  [K0,V0] [K1,V1] _  _  _  _  _  _
...
t=7:  [K0,V0] [K1,V1] [K2,V2] [K3,V3] [K4,V4] [K5,V5] [K6,V6] [K7,V7]  ← buffer full
t=8:  [K8,V8] [K1,V1] [K2,V2] [K3,V3] [K4,V4] [K5,V5] [K6,V6] [K7,V7]  ← K0 overwritten
t=9:  [K8,V8] [K9,V9] [K2,V2] [K3,V3] [K4,V4] [K5,V5] [K6,V6] [K7,V7]  ← K1 overwritten

Key property: Memory footprint is strictly constant after t ≥ W. No matter how long the conversation runs, the KV cache per layer never exceeds W tokens.

3.3 Information Flow Beyond the Window

If a token at position t only attends to t-W ... t-1, how does information from position t-2W reach position t?

Answer: Layer stacking. In a transformer with L layers, the receptive field grows by W per layer:

Layer	Receptive Field (tokens each query can “see”)
1	W
2	2W
3	3W
…	…
L	L × W

Example: Mistral 7B has L = 32, W = 4,096. At the final layer, each token can access information from 131,072 tokens back (32 × 4,096) — even though the per-layer cache is only 4,096 tokens!

This is why SWA models can handle very long contexts with small cache: information propagates vertically through layers, not horizontally within a layer.

3.4 SWA Memory Formula

Per-token KV cache memory (from Lesson 16):

bytes_per_token = 2 × L × H_kv × d_head × b

Where:

• L = number of layers
• H_kv = number of KV heads (for GQA; equals H_q for MHA)
• d_head = head dimension (e.g., 128)
• b = bytes per element (2 for FP16/BF16, 1 for INT8)

Total SWA cache memory (capped):

SWA_cache_bytes = W × bytes_per_token

Compare to full attention (unbounded growth):

Full_cache_bytes(T) = T × bytes_per_token  (grows linearly with T)

Critical distinction: SWA caps memory at W × bytes_per_token. Full attention grows without bound until context limit or OOM.

---

4. Three Hands-On Exercises with Checked Solutions

Notation used below:

• 1 KiB = 1,024 bytes
• 1 MiB = 1,024 KiB
• 1 GiB = 1,024 MiB
• FLOPs = floating-point operations (total count)
• FLOPS = floating-point operations per second (rate)

---

Exercise 1: Prefix Caching Latency & VRAM Savings

Scenario: A chat application serves 10 concurrent requests. All share the same system prompt.

Parameter	Value
Shared system prompt P_sys	1,500 tokens
Unique user query per request	100 tokens
Generated tokens per request	50 tokens
Model	7B parameters, FP16
Prefill compute density	14 TFLOPs per 1,000 tokens
GPU compute throughput	150 TFLOPS
KV cache per token	128 KiB

Part A: No Prefix Caching (Baseline)

Question 1A-1: Total prefill tokens across all 10 requests.

Solution:

Each request prefill = P_sys + unique_query = 1,500 + 100 = 1,600 tokens
10 requests × 1,600 tokens = 16,000 tokens

Question 1A-2: Total prefill compute time (ms).

Solution:

Total FLOPs = 16,000 tokens × 14 TFLOPs/1,000 tokens = 224 TFLOPs
Time = 224 TFLOPs / 150 TFLOPS = 1.4933 s = 1,493.3 ms

Question 1A-3: System prompt KV cache memory (GiB) — 10 separate copies.

Solution:

10 requests × 1,500 tokens × 128 KiB/token
= 1,920,000 KiB
= 1,875 MiB
= 1.831 GiB

Part B: With Prefix Caching

Question 1B-1: System prompt prefilled once. Time (ms).

Solution:

1,500 tokens × 14 TFLOPs/1,000 tokens = 21 TFLOPs
Time = 21 / 150 = 0.1400 s = 140.0 ms

Question 1B-2: Unique user queries (10 × 100 tokens). Time (ms).

Solution:

1,000 tokens × 14 TFLOPs/1,000 tokens = 14 TFLOPs
Time = 14 / 150 = 0.09333 s = 93.3 ms

Question 1B-3: Total prefill compute time with prefix caching (ms). Speedup factor.

Solution:

Total = 140.0 + 93.3 = 233.3 ms
Speedup = 1,493.3 / 233.3 = 6.40×

Question 1B-4: System prompt KV cache memory with prefix caching (GiB). Memory reduction factor.

Solution:

1 copy × 1,500 tokens × 128 KiB = 192,000 KiB = 187.5 MiB = 0.183 GiB
Reduction = 1.831 / 0.183 = 10.0×  (exactly 10×, matching the 10 requests)

Summary: Prefix caching gives 6.4× prefill latency reduction and 10× system-prompt memory reduction in this scenario.

---

Exercise 2: Sliding-Window Attention Memory Cap

Scenario: Mistral 7B configuration with sliding-window attention.

Parameter	Value
Layers L	32
KV heads H_kv	8 (GQA: 32 query heads, 8 KV heads)
Head dimension d_head	128
Precision b	2 bytes (FP16)
Sliding window W	4,096 tokens
Workload	Long-running stream generating T tokens

Question 2-1: Bytes per token for this model.

Solution:

bytes_per_token = 2 × L × H_kv × d_head × b
                = 2 × 32 × 8 × 128 × 2
                = 131,072 bytes
                = 128 KiB  (exactly)

Question 2-2: Full attention cache size at T = 32,768 (32K tokens). Express in GiB.

Solution:

Full cache = 32,768 tokens × 128 KiB/token
           = 4,194,304 KiB
           = 4,096 MiB
           = 4.0 GiB

Question 2-3: SWA cache size (capped at W = 4,096). Express in GiB.

Solution:

SWA cache = 4,096 tokens × 128 KiB/token
          = 524,288 KiB
          = 512 MiB
          = 0.5 GiB

Question 2-4: Memory saved at T = 32K. Percentage reduction.

Solution:

Saved = 4.0 - 0.5 = 3.5 GiB
Reduction = 3.5 / 4.0 = 87.5%

Question 2-5: At T = 131,072 (128K tokens). Full cache vs SWA cache. Reduction factor.

Solution:

Full cache = 131,072 × 128 KiB = 16,777,216 KiB = 16,384 MiB = 16.0 GiB
SWA cache  = 0.5 GiB (unchanged!)
Reduction factor = 16.0 / 0.5 = 32×
Memory saved = 15.5 GiB (96.875% reduction)

Key insight: SWA memory is constant after T > W. Full attention grows linearly. At 128K context, SWA uses 32× less memory.

---

Exercise 3: Preemption Decision — PCIe Swapping vs. Recomputation

Scenario: An idle request occupies 800 MiB of KV cache (6,400 tokens at 128 KiB/token). The scheduler must clear this space for an incoming request. Compare two strategies.

Hardware:

• PCIe Gen4 x16 sustained bandwidth: 25 GB/s
• GPU compute: 150 TFLOPS (FP16)
• Model: 7B parameters

Case 1: Swap to CPU RAM over PCIe

Question 3-1: Transfer time to swap 800 MiB out (GPU → CPU).

Solution:

800 MiB = 0.8 GiB = 0.8 × 1,024 MiB ≈ 819.2 MiB
In GB: 800 / 1,024 = 0.78125 GB
Time = 0.78125 GB / 25 GB/s = 0.03125 s = 31.25 ms ≈ 31.3 ms

(Using 800 MB / 25 GB/s = 0.8 / 25 = 0.032 s = 32.0 ms is also acceptable; the difference is MiB vs MB.)

Answer: ~32 ms

Case 2: Discard and Recompute from Scratch

Question 3-2: FLOPs to recompute 6,400 tokens on 7B model.

Solution:

FLOPs = 2 × tokens × parameters
      = 2 × 6,400 × 7×10⁹
      = 89.6 × 10¹²
      = 89.6 TFLOPs

Question 3-3: Recomputation time at 150 TFLOPS.

Solution:

Time = 89.6 TFLOPs / 150 TFLOPS = 0.5973 s = 597.3 ms

Comparison

Question 3-4: Which is faster, and by what factor?

Solution:

Swap time = 32.0 ms
Recompute time = 597.3 ms
Factor = 597.3 / 32.0 = 18.67× ≈ 18.7×

Conclusion: PCIe swapping is ~18.7× faster than recomputation for this workload.

Practical implication: Production engines (vLLM, TensorRT-LLM) prefer swapping for idle requests with large caches. Recomputation is only preferable when:

• The cache is very small (swap overhead dominates)
• Host RAM is exhausted
• PCIe bandwidth is saturated by other transfers
• The request is very unlikely to resume (speculative eviction)

---

5. Summary Reference Table

Dimension	Prefix Caching	Cache Eviction / Swapping	Sliding-Window Attention
Problem solved	Redundant prefill + duplicate storage	VRAM exhaustion	Unbounded per-request cache growth
Mechanism	Shared immutable physical blocks + ref counting + CoW	LRU/priority victim selection; PCIe DMA to host RAM; token pruning (sinks, heavy hitters)	Fixed attention window W; circular rolling buffer per layer
Granularity	Block-level (16–32 tokens)	Request-level or token-level	Per-layer, fixed W tokens
Memory effect	Reduces duplicate memory (shares prefix blocks)	Frees memory on demand (evicts or swaps)	Strictly caps memory at W × bytes_per_token
Latency effect	Zero prefill for cached prefix	Swap: ~30–100 ms; Recompute: ~100–1000+ ms; Prune: 0 ms (continuous)	No prefill change; decode unchanged
Quality impact	None (exact reuse)	Swap: None; Recompute: None; Prune: Small (approx.)	Model-dependent (trained with SWA)
When it applies	Any shared prefix (system prompt, chat history, RAG)	Free list empty; admission control; memory pressure	Model architecture choice (Mistral, Longformer, etc.)
Key tradeoff	CoW overhead on divergence; prefix cache lookup cost	Swap needs host RAM + PCIe; prune loses context	Cannot attend beyond W in a single layer (relies on depth)
Primary citation	Kwon et al. (2023) — vLLM Prefix Caching	Xiao et al. (2023) — StreamingLLM; Zhang et al. (2023) — H2O	Jiang et al. (2023) — Mistral 7B

---

6. Primary Source Citations

#	Citation	Link
1	Kwon et al. (2023), Efficient Memory Management for Large Language Model Serving with PagedAttention (vLLM, includes prefix caching)	arXiv:2309.06180
2	Jiang et al. (2023), Mistral 7B (Sliding-Window Attention, GQA)	arXiv:2310.06825
3	Xiao et al. (2023), StreamingLLM: Efficient Streaming Language Models with Attention Sinks	arXiv:2309.17453
4	Zhang et al. (2023), H2O: Heavy-Hitter Oracle for Efficient Generative Inference	arXiv:2306.13354
5	Dao et al. (2022), FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (tiling, not SWA but related)	arXiv:2205.14135

---

7. What Comes Next

• Next lesson: Use Less Memory: Quantization and Offloading — Now that we can reuse, evict, or bound the cache, learn how to shrink each cached value (FP16 → INT8 → INT4 → FP8) and move cache tiers between GPU, CPU, and NVMe.
• Previous lesson: Allocate the Cache: Blocks, Waste, and PagedAttention
• Track overview: Start Here: LLM Foundations