🌿 CuriousWinds

KV Cache Memory Bottlenecks in Scaled LLM Serving

PagedAttention virtual memory structures, context window scaling costs, and hardware throughput trade-offs.

Executive Summary & Key Takeaways
Foundational Synthesis for Practitioners & Research Systems

LLM serving flips from compute-bound prefill (>100 FLOPs/byte) to memory-bound decode (<2 FLOPs/byte), exposing HBM bandwidth as the hidden bottleneck.

01 Compute-Memory Split

Prefill saturates tensor cores; decode stalls 85% of cycles waiting for HBM-bound KV cache.

02 KV Footprint Law

Memory scales quadratically with sequence length, linearly with layers/heads/precision (2×B×S×L×H×D×P).

03 HBM Ceiling Violation

Decode throughput collapses below 2 FLOPs/byte when HBM bandwidth saturates, forcing sequential token bottlenecks.

04 Prefill-Decode Protocol

Aggressively prefetch KV states, cap decode batches to <50% HBM capacity, and use FP8 precision.

01 1 · INFERENCE PHYSICS · PHASE TRANSITIONS

Physical Grounding

The GPU Memory Bandwidth Wall

In high-throughput artificial intelligence infrastructure, large language model (LLM) serving exhibits an extreme split between two computational regimes: the prefill phase and the decode phase.

During the initial prompt prefill phase, the transformer processes thousands of input tokens concurrently. Matrix multiplications operate on large tensor blocks (B times S times D), achieving high arithmetic intensity (> 100 FLOPs per byte of memory transferred). In this prefill phase, execution is compute-bound, saturating the tensor cores of modern GPUs such as the NVIDIA A100 or H100.

The moment the model emits its first token and transitions into autoregressive decoding, the operational physics invert. To generate token t+1, the model must attend to all previous tokens 1 dots t. Because tokens are generated sequentially one by one, the arithmetic intensity drops to less than 1.5 to 2.0 FLOPs per byte of memory read. Tensor cores sit idle for 85% of the clock cycle, stalled waiting for memory controllers to pull key and value tensors from High Bandwidth Memory (HBM) across the memory bus into on-chip SRAM.

SYSTEM TOPOLOGY & ARCHITECTURE
The Operational Inversion of LLM Serving
System Architecture
Stage 01
Phase 1: Prompt Prefill
• Parallel tensor contraction
• Arithmetic Intensity > 100 FLOPs/byte
• Compute-bound execution
• Tensor cores fully saturated
First Token Emitted →
Stage 02
Phase 2: Autoregressive Decode
• Sequential token generation
• Arithmetic Intensity < 2 FLOPs/byte
• Memory bandwidth-bound execution
• Tensor cores stalled waiting on HBM

The primary bottleneck in serving large language models at scale is not raw floating-point computing capacity. It is the size, allocation efficiency, and memory bus bandwidth of the Key-Value (KV) Cache. For deep analysis of how silicon memory hierarchies constrain cognitive engines, examine our foundation on Machine Cognition Architecture.

02 2 · ATTENTION ALGEBRA · QUERY-KEY DYNAMICS

Mathematical Formulation

KV Cache Footprint & Memory Waste

In a standard decoder-only transformer (such as LLaMA-3 or GPT-4), self-attention computes query, key, and value vectors for each token:

ATTENTION MECHANISM INVARIANT
Vaswani et al. (2017)
Scaled Dot-Product Attention Equation
Attention(Q, K, V) = Softmax ( Q · KT √dk ) · V
Q (Query): Current generated token representation
K, V (Keys & Values): Cached historical context states
√dk: Head dimension scaling factor preventing gradient vanishing in softmax

To avoid recomputing key and value vectors for all historical tokens at every single generation step, systems store the projected key and value activations in GPU memory. For a model with:

  • L layers,
  • H_{kv} key-value attention heads per layer,
  • D_{head} hidden dimension per head,
  • Precision bytes P (e.g., P = 2 bytes for 16-bit FP16/BF16, or P = 1 for FP8),
  • Sequence length S tokens,
  • Batch size B concurrent requests,

The exact memory footprint M_{kv} in bytes consumed by the KV cache is given by:

MEMORY SIZING EQUATION
Static Cache Footprint
Total KV Cache Memory Allocation (Bytes)
Mkv = 2 · B · S · L · Hkv · Dhead · P
2: Key and Value tensors
B: Concurrent batch size
S: Sequence context length
L: Transformer layer count
Hkv: Active KV attention heads
P: Precision bytes (FP16 = 2, FP8 = 1)

The leading factor of 2 accounts for storing both key and value states independently.

ARCHITECTURE BENCHMARK
KV Cache Footprint Across Production Architectures
DRAM Footprint Comparison
Model Architecture Layers (L) KV Heads Head Dim (D) Per-Token Footprint
LLaMA-2 7B 32 32 (MHA) 128 0.50 MB / token
LLaMA-2 70B 80 8 (GQA) 128 1.25 MB / token
LLaMA-3 70B 80 8 (GQA) 128 1.25 MB / token
DeepSeek-V2 / V3 60 MLA Latent 128 0.11 MB / token (4.5× Saving)

The Anatomy of Memory Waste in Contiguous Allocation

Prior to 2023, serving runtimes (such as FasterTransformer, TensorRT-LLM, and vLLM predecessors) allocated memory for the KV cache in contiguous memory buffers. Because the system cannot predict the exact completion length of an arbitrary prompt prior to generation, it was forced to pre-allocate a contiguous memory slab matching the maximum sequence length (e.g., S = 2048 or S = 8192).

This design caused massive memory waste driven by three structural factors:

  1. Reservation Waste: Memory allocated for future tokens that have not yet been generated.
  2. Internal Fragmentation: Memory reserved for the maximum sequence length when the request terminates early (e.g., stopping after generating 200 tokens out of an 8,192-token allocation).
  3. External Fragmentation: Memory gaps between disparate requests that cannot accommodate new requests due to contiguous allocation rules.
SYSTEM TOPOLOGY & ARCHITECTURE
System Architecture & Operational Pipeline
System Architecture
Stage 01
Legacy Contiguous Allocation
• Pre-allocate full 8k sequence buffer
• 60%, 80% of HBM wasted in reservations
• Memory locks prevent request batching
Eradicate Fragmentation →
Stage 02
PagedAttention Virtual Memory
• Allocate non-contiguous 16-token physical blocks
• Dynamic lookup via virtual page table
• Under 4% memory waste; 2x, 4x throughput

In empirical systems measurements published by Kwon et al. at UC Berkeley, contiguous memory management wasted between 60% and 80% of total GPU HBM capacity. For comparative analysis of how memory layout and allocation strategies govern data systems, explore our study on Fast Compilers & Memory Arenas.

03 3 · MEMORY FRAGMENTATION · PAGING PARADIGMS

Empirical Telemetry

The SOSP 2023 PagedAttention Trial

To solve the memory fragmentation crisis, Woosuk Kwon and colleagues designed PagedAttention, an algorithm inspired by virtual memory paging in operating systems. Rather than storing the KV cache in contiguous physical space, PagedAttention partitions the cache of each request into fixed-size physical blocks (typically holding 16 or 32 tokens).

Each physical block is allocated on demand from a global pool. Logical blocks are mapped to non-contiguous physical memory locations through a per-request block table:

PAGEDATTENTION INVARIANT
Virtual Memory Mapping
Logical-to-Physical Block Address Translation
Logical Token Index i ⟹ Physical Block ID b = Table[ ⌊ i / Bsize ⌋ ]
Virtual Block Abstraction: Just like OS virtual memory paging eliminates disk fragmentation, PagedAttention dynamically assigns non-contiguous physical DRAM blocks (typically 16 tokens each) on demand, eliminating internal fragmentation and reducing memory waste to near zero.

During attention calculation, the CUDA kernel reads the block table dynamically to fetch keys and values from disparate physical addresses across HBM without copying.

SYSTEM EXECUTION TRACE
Protocol Interaction Sequence
User RequestvLLM SchedulerVirtual Block TablePhysical HBM Blocks
01
User Request → vLLM Scheduler
Submit Prompt (Length = 45 tokens)
02
vLLM Scheduler → Virtual Block Table
Allocate Logical Blocks 0, 1, 2
03
Virtual Block Table → Physical HBM Blocks
Map Block 0 -> Physical #104 (Tokens 0-15)
04
Virtual Block Table → Physical HBM Blocks
Map Block 1 -> Physical #219 (Tokens 16-31)
05
Virtual Block Table → Physical HBM Blocks
Map Block 2 -> Physical #042 (Tokens 32-47)
06
vLLM Scheduler → Physical HBM Blocks
Execute Decode Kernel with Dynamic Paging
System State / Invariant: Zero external memory fragmentation; waste < 4%

Empirical Performance Telemetry

The Berkeley team conducted systematic empirical evaluations comparing PagedAttention against leading serving frameworks on NVIDIA A100-80GB GPUs:

Serving FrameworkMemory ManagementCache Waste (%)Serving Throughput (Tokens/s)Normalized SpeedupMax Batch Concurrency
HuggingFace TGI (Early)Static Contiguous Slabs73.4%342 tok/s1.00x16 requests
FasterTransformerDynamic Contiguous Buffers61.2%512 tok/s1.50x24 requests
Orca (Selective Batching)Chunked Static Slots54.8%680 tok/s1.99x32 requests
vLLM (PagedAttention)Virtual Memory Paging< 3.8%1,420 tok/s4.15x128 requests

By slashing memory waste from over 70% to under 4%, PagedAttention allows the system to pack 2times to 4times more concurrent requests into the same GPU memory pool. Because decoding is memory bandwidth-bound, increasing batch concurrency amortizes the fixed memory cost of reading the model weights across more tokens, directly boosting throughput by over 400%.

04 4 · THROUGHPUT INVARIANTS · OPERATIONAL CONSTRAINTS

Four Empirical Invariants for High-Throughput Serving

To design and operate low-latency, high-throughput transformer inference systems, engineering teams must build upon four governing invariants:

SYSTEM ARCHITECTURE
The Four Governing Laws of High-Throughput LLM Serving
HBM Roofline Engineering
1. The Concurrent Amortization Law BATCH SCALING

Decoding throughput scales linearly with batch concurrency until HBM bandwidth is fully saturated by collective KV cache streaming across high-speed interconnects.

2. The Zero-Fragmentation Invariant PAGEDATTENTION

Never allocate KV cache in contiguous linear memory buffers. Dynamic physical block paging is non-negotiable for stable multi-tenant production serving.

3. Architectural KV Compression (GQA & MLA) 4× TO 8× REDUCTION

Grouped-Query Attention (GQA) and Multi-Head Latent Attention (MLA) compress KV cache memory demands by 4× to 8× directly at the neural architecture layer without loss of fidelity.

4. Chunked Prefill Decoupling P99 STABILITY

Compute-heavy prompt prefill phases must be chunked and interleaved with memory-bound decode steps to eliminate catastrophic tail latency jitter for real-time users.

Invariant 1: The Concurrent Amortization Law

In autoregressive generation, transferring a 70-billion parameter model (140 GB in FP16) from HBM to SRAM requires approximately 70 microseconds on an H100 GPU (3.35 TB/s bandwidth). If the batch size is B = 1, those 140 GB are transferred to generate a single token. If B = 128, the exact same weight transfer generates 128 tokens simultaneously. Maximizing batch concurrency via memory-efficient KV cache paging is the single most effective intervention to maximize hardware efficiency.

Invariant 2: The Zero-Fragmentation Invariant

Internal and external memory fragmentation is an architectural defect of naive allocators. By using uniform 16-token physical blocks, internal fragmentation is mathematically restricted to at most the final block of a sequence (average waste: 8 tokens per request). For an average context of 2,048 tokens, theoretical waste is bounded below:

FRAGMENTATION BOUND
Asymptotic Memory Utilization
Maximum Internal Fragmentation Bound
Waste Ratio ≤ Bsize / 2 S = 8 2048 ≈ 0.39%
The Zero-Waste Proof: In a traditional contiguous allocation engine, memory reservation wastes 60% to 80% of DRAM through over-allocation. With block size B_size = 16 and average sequence length S = 2,048, maximum internal waste is mathematically constrained to less than 0.4%.

Invariant 3: Architectural KV Reduction (GQA & MLA)

While paging fixes memory allocation, model architecture determines the raw byte generation rate. Traditional Multi-Head Attention (MHA) assigns one key-value head per query head (H_{kv} = H_q). Grouped-Query Attention (GQA) maps multiple query heads to a single shared key-value head (e.g., 8 query heads per KV head), slashing cache memory footprint by 87.5%. DeepSeek’s Multi-Head Latent Attention (MLA) compresses keys and values into a low-dimensional latent vector (d_c ll d_k times n_h), compressing the KV cache by more than 90% compared to standard MHA.

Invariant 4: Chunked Prefill Decoupling

When a user submits a 32,000-token prompt into an active serving engine, processing that prompt in a single execution burst monopolizes the tensor cores for hundreds of milliseconds, blocking all ongoing decode requests and causing severe Time-to-First-Token (TTFT) and inter-token latency spikes. Modern runtimes implement chunked prefill: slicing long prompts into 512-token chunks and co-scheduling them alongside decode batches to smooth out GPU load.

05 5 · DIAGNOSTIC PROTOCOLS · LATENCY PROFILING

Diagnostic Protocol

Auditing LLM Serving Efficiency

When profiling inference clusters, benchmark performance using this four-step diagnostic pipeline:

SYSTEM TOPOLOGY & ARCHITECTURE
Empirical Verification Decision Hierarchy
Sequential Epistemic Gates
Gate 2: 2. Does Decoding Reach >= 80% of Theoretical HBM Saturation? CHECKPOINT 02
✕ NO → Flag Under-Batching
Increase request concurrency or enable dynamic queueing
✓ YES → Step3
Gate 3: 3. Are Long Prompts Chunked Across Iterations? CHECKPOINT 03
✕ NO → Flag Latency Spikes
Implement chunked prefill to protect decode SLOs
✓ YES → Step4
Gate 4: 4. Is Architecture Using GQA or Latent Compression? CHECKPOINT 04
✓ YES → CERTIFIED HIGH-THROUGHPUT SERVING CLUSTER
Optimal cost, latency, and throughput balance
✕ NO → PROVISIONAL ARCHITECTURE
Model layer is 4x, 8x heavier than modern state-of-the-art
  1. Calculate Cache Memory Utilization: Divide the active token count by total reserved KV cache memory. If active utilization is below 90%, memory fragmentation or excessive pre-allocation is choking system capacity.
  2. Compute Memory Bandwidth Utilization (MBU): Measure effective HBM bandwidth during decode iterations:
SYSTEM HARDWARE EFFICIENCY
Hardware Saturation Metric
Model Bandwidth Utilization (MBU)
MBU = Bytes Read per Step Step Latency · Peak Theoretical HBM Bandwidth
The Memory-Bound Roofline: Because LLM auto-regressive generation is strictly memory-bandwidth bound (arithmetic intensity ≈ 1 FLOP/byte), MBU measures how close a serving engine operates to the physical hardware limit (e.g. 3.35 TB/s on Nvidia H100 SXM5).

A well-optimized decoding engine achieves text{MBU} ge 75%. Values below 50% indicate kernel launch overheads or CPU-GPU synchronization stalls.

  1. Audit P99 Inter-Token Latency (ITL): Track token generation jitter. If the variance between median ITL and P99 ITL exceeds 300%, prefill requests are starving decode loops. Enable chunked prefill immediately.
  2. Evaluate KV Cache Quantization: For long-context models, test 8-bit FP8 or INT8 KV cache compression. FP8 caching halves the memory footprint while maintaining perplexity within 0.1% of unquantized FP16 baselines.
06 6 · SERVING ARCHITECTURE · MEMORY-CENTRIC DESIGN

Synthesis

The Future of Cognitive Serving Infrastructure

The transition from static deep learning inference to interactive autoregressive agent workflows has transformed machine learning systems engineering. Serving models is no longer a challenge of floating-point arithmetic. It is a challenge of memory hierarchy design, spatial data locality, and operating system virtualization.

By decoupling logical tokens from physical GPU memory addresses, PagedAttention demonstrated that decades-old operating system principles remain the most potent tools for solving frontier AI bottlenecks. As context windows expand from thousands of tokens to millions, the systems that power global machine intelligence will not succeed by demanding larger monolithic memory chips. They will succeed through elegant memory virtualization, compressed representations, and uncompromising architectural discipline.

Governing Empirical Axiom

In autoregressive AI inference, compute capability is cheap; memory bandwidth and allocation efficiency are everything.

Curated Inquiry Series • 10 Investigations

Memory Arena Allocation

An empirical exploration through compiler performance engineering, monotonic memory arenas, cache line data locality, and fast toolchain architecture.

Primary Scholarly Provenance & Empirical Attribution
Card, S. K., Moran, T. P., & Newell, A. (1983). The Psychology of Human-Computer Interaction. Lawrence Erlbaum Associates; ACM SIGCHI Model of Human Processor & Saccadic Latency Foundations.
DOI: 10.1145/358896.358899