KV cache is the memory buffer storing previously computed key and value tensors during autoregressive LLM inference — avoiding redundant computation by caching intermediate results, but requiring significant GPU memory that scales with sequence length and batch size, making cache management critical for efficient serving.

What Is KV Cache?

• Definition: Cached key-value pairs from attention computation.
• Purpose: Avoid recomputing previous token representations each step.
• Growth: Linear with sequence length × layers × batch size.
• Challenge: Major memory bottleneck for long contexts and batching.

Why KV Cache Matters

• Efficiency: Without caching, cost would be O(n²) per token.
• Memory: Can exceed model weights for long sequences.
• Throughput: KV cache size limits batch size.
• Long Context: 100K+ contexts need cache optimization.
• Cost: Memory management directly impacts inference cost.

How KV Cache Works

Autoregressive Generation:

Without KV Cache (naive):
Step 1: Compute K,V for [token1]
Step 2: Recompute K,V for [token1, token2]
Step 3: Recompute K,V for [token1, token2, token3]
        ...each step recomputes everything!

With KV Cache:
Step 1: Compute K,V for [token1], cache it
Step 2: Compute K,V for [token2] only, append to cache
Step 3: Compute K,V for [token3] only, append to cache
        ...only compute new token each step

Memory Layout:

<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 760 470" width="100%" height="100%" style="background:#0F172A;font-family:-apple-system,BlinkMacSystemFont,'Segoe UI',Roboto,Helvetica,Arial,sans-serif;">
  <defs>
    <linearGradient id="cardGrad" x1="0%" y1="0%" x2="0%" y2="100%">
      <stop offset="0%" stop-color="#1E293B"/>
      <stop offset="100%" stop-color="#0F172A"/>
    </linearGradient>
  </defs>

  <!-- Title Banner -->
  <rect x="20" y="20" width="720" height="56" rx="14" fill="url(#cardGrad)" stroke="#334155" stroke-width="1"/>
  <text x="36" y="46" font-size="18" font-weight="800" fill="#F8FAFC">KV Cache Memory Architecture &amp; PagedAttention</text>
  <text x="36" y="64" font-size="12" font-weight="600" fill="#94A3B8">Transformer Memory Optimization · Key-Value State Reuse · Virtual Memory Block Management</text>

  <!-- Panel 1: Naive Memory Allocation vs KV Cache -->
  <rect x="20" y="90" width="350" height="350" rx="16" fill="url(#cardGrad)" stroke="#334155" stroke-width="1"/>
  <text x="40" y="118" font-size="14" font-weight="700" fill="#38BDF8">1. KV Cache Mechanism &amp; Savings</text>

  <!-- Without Cache (Recomputation) -->
  <rect x="40" y="140" width="310" height="70" rx="8" fill="#0F172A" stroke="#F43F5E" stroke-width="1"/>
  <text x="55" y="160" font-size="11" font-weight="800" fill="#F43F5E">Naive Generation (No KV Cache):</text>
  <text x="55" y="178" font-size="10" font-weight="600" fill="#CBD5E1">Recomputes Key &amp; Value tensors for ALL previous tokens at every step. Quadratic O(N²) Compute cost!</text>

  <!-- With Cache (Appends 1 token) -->
  <rect x="40" y="220" width="310" height="105" rx="8" fill="#1E293B" stroke="#0284C7" stroke-width="1.5"/>
  <text x="55" y="242" font-size="11" font-weight="800" fill="#38BDF8">With KV Cache (Cached Past Tokens):</text>
  <text x="55" y="262" font-size="10" font-weight="600" fill="#CBD5E1">Stores Key (K) &amp; Value (V) tensors in VRAM GPU memory.</text>
  <text x="55" y="280" font-size="10" font-weight="600" fill="#A78BFA">New Token: Computes only 1 new K, V vector &amp; appends to cache!</text>
  <text x="55" y="305" font-size="11" font-weight="800" fill="#F59E0B">Reduces Autoregressive Decoding from O(N²) to O(N)</text>

  <!-- Memory Sizing Footnote -->
  <rect x="40" y="335" width="310" height="90" rx="8" fill="#0F172A" stroke="#334155" stroke-width="1"/>
  <text x="55" y="355" font-size="11" font-weight="700" fill="#F8FAFC">KV Cache Memory Size Formula:</text>
  <text x="55" y="375" font-size="10" font-weight="600" fill="#38BDF8">Size = 2 × 2 (FP16) × n_layers × n_heads × d_head × seq_len</text>
  <text x="55" y="395" font-size="10" font-weight="600" fill="#CBD5E1">e.g., Llama-3 70B (8k seq): ~1.2 GB per sequence</text>

  <!-- Panel 2: PagedAttention & Fragmented Memory Management -->
  <rect x="390" y="90" width="350" height="350" rx="16" fill="url(#cardGrad)" stroke="#334155" stroke-width="1"/>
  <text x="410" y="118" font-size="14" font-weight="700" fill="#38BDF8">2. PagedAttention (vLLM Engine)</text>

  <!-- Virtual Memory Block Diagram -->
  <rect x="410" y="135" width="310" height="180" rx="10" fill="#0F172A" stroke="#334155" stroke-width="1"/>
  <text x="425" y="158" font-size="12" font-weight="800" fill="#38BDF8">Virtual Blocks to Physical Pages Map:</text>

  <!-- Sequence 1 Blocks -->
  <text x="425" y="182" font-size="10" font-weight="700" fill="#A78BFA">Seq 1 Logical Blocks:</text>
  <rect x="540" y="170" width="40" height="20" rx="4" fill="#6D28D9"/>
  <text x="560" y="184" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">L0</text>
  <rect x="585" y="170" width="40" height="20" rx="4" fill="#6D28D9"/>
  <text x="605" y="184" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">L1</text>
  <rect x="630" y="170" width="40" height="20" rx="4" fill="#6D28D9"/>
  <text x="650" y="184" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">L2</text>

  <!-- Mapping Arrow -->
  <line x1="565" y1="195" x2="565" y2="215" stroke="#94A3B8" stroke-width="1.5" stroke-dasharray="2,2"/>
  <line x1="605" y1="195" x2="645" y2="215" stroke="#94A3B8" stroke-width="1.5" stroke-dasharray="2,2"/>

  <!-- Physical Memory Pool -->
  <text x="425" y="232" font-size="10" font-weight="700" fill="#38BDF8">Non-contiguous GPU Pages:</text>
  <rect x="425" y="242" width="50" height="25" rx="4" fill="#0284C7"/>
  <text x="450" y="258" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">Page 7</text>

  <rect x="485" y="242" width="50" height="25" rx="4" fill="#0284C7"/>
  <text x="510" y="258" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">Page 2</text>

  <rect x="545" y="242" width="50" height="25" rx="4" fill="#0284C7"/>
  <text x="570" y="258" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">Page 19</text>

  <rect x="605" y="242" width="50" height="25" rx="4" fill="#0284C7"/>
  <text x="630" y="258" font-size="9" font-weight="800" fill="#F8FAFC" text-anchor="middle">Page 4</text>

  <text x="425" y="295" font-size="10" font-weight="700" fill="#F59E0B">Eliminates 96%+ Memory Fragmentation Waste!</text>

  <!-- PagedAttention Benefits Box -->
  <rect x="410" y="325" width="310" height="100" rx="10" fill="#1E293B" stroke="#475569" stroke-width="1"/>
  <text x="425" y="348" font-size="12" font-weight="800" fill="#38BDF8">Attention Variants for Memory Reduction:</text>
  <text x="425" y="370" font-size="11" font-weight="600" fill="#F8FAFC">• GQA (Grouped-Query Attention): 8x memory reduction</text>
  <text x="425" y="392" font-size="11" font-weight="600" fill="#CBD5E1">• MQA (Multi-Query Attention): Single KV head shared</text>
  <text x="425" y="412" font-size="10" font-weight="700" fill="#F59E0B">Enables 4x larger batch sizes &amp; higher throughput</text>
</svg>

Memory Calculation

KV Cache Size = 2 × L × H × S × B × dtype_size

Where:
- 2 = keys and values
- L = number of layers
- H = hidden dimension
- S = sequence length
- B = batch size
- dtype = FP16 (2 bytes) or FP8 (1 byte)

Example (Llama-70B, 4K context, batch=1, FP16):
= 2 × 80 layers × 8192 hidden × 4096 seq × 1 × 2 bytes
= 10.7 GB per sequence!

Batch of 8 = 86 GB just for KV cache

KV Cache Optimizations

PagedAttention (vLLM):

Traditional: Contiguous memory per sequence (fragmentation)
PagedAttention: Memory in fixed-size pages (like OS virtual memory)

Benefits:
- No fragmentation
- Share pages across requests (prefix caching)
- Dynamic allocation
- 2-4× higher throughput

Quantized KV Cache:

Store cache in INT8 or INT4 instead of FP16
Memory reduction: 2-4×
Quality impact: Minimal for most models

FP16: 16 bits/value
INT8: 8 bits/value (2× reduction)
INT4: 4 bits/value (4× reduction)

Grouped Query Attention (GQA):

Standard MHA: heads_k = heads_q = 32
GQA: heads_k = 8, heads_q = 32

KV cache 4× smaller with GQA
Most modern models use GQA

Multi-Query Attention (MQA):

MQA: heads_k = 1, heads_q = 32
Even smaller cache, some quality trade-off

Prefix Caching:

System prompt: "You are a helpful assistant..."
This is same across requests → compute once, share KV

First request: Compute full KV for system prompt
Later requests: Reuse cached system prompt KV
Savings: Skip prefill for common prompts

Memory Comparison

Optimization      | Memory | Implementation
------------------|--------|------------------
Baseline FP16     | 100%   | Standard
INT8 KV           | 50%    | Most frameworks
INT4 KV           | 25%    | Some frameworks
GQA (4 groups)    | 25%    | Model architecture
GQA + INT8        | 12.5%  | Combined
PagedAttention    | ~60-80%| vLLM (less fragmentation)

Sliding Window Attention

Instead of attending to full history:
- Only attend to last W tokens
- KV cache capped at W entries
- Used in Mistral (W=4096)

Trade-off: Bounded memory vs. long-range attention

KV cache management is the critical bottleneck in LLM inference — as context windows grow to 100K+ tokens and users expect real-time responses, efficient cache strategies determine whether serving is practical and affordable, making KV optimization essential infrastructure.