Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Paged Attention › Measuring Fragmentation Reduction

Michael BrenndoerferJanuary 8, 20264 min read

Language AI HandbookAll chapters

Part 42 of 67Inference Optimization

Chapter 315Paged Attention › Measuring Fragmentation Reduction

Reading section 9 of 13 · Measuring Fragmentation Reduction · 4 minSection 9 of 13 · 4 min

Section 9 of 13 · 4 min read

Paged Attention › Measuring Fragmentation ReductionOne section · Sections in this chapter9 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Let's quantify the improvement PagedAttention provides over traditional allocation. This comparison is useful for understanding the magnitude of the problem that PagedAttention solves and for setting expectations about real-world throughput improvements.

The comparison is inherently unfair to traditional allocation because traditional allocation was never designed for dynamic request serving. It was designed for static, pre-known workloads. PagedAttention is specifically designed for the dynamic, variable-length nature of LLM inference. The numbers below reflect this design mismatch.

In[29]:

Code

import numpy as np


def compare_allocation_strategies(
    num_sequences: int = 50,
    max_seq_len: int = 2048,
    block_size: int = 16,
):
    """
    Compare traditional contiguous vs paged allocation.
    """
    # Generate realistic sequence lengths (biased toward shorter)
    actual_lengths = np.random.exponential(scale=300, size=num_sequences)
    actual_lengths = np.clip(actual_lengths, 50, max_seq_len).astype(int)

    results = {
        "traditional": {
            "peak_memory": 0,
            "avg_utilization": [],
            "fragmentation_events": 0,
        },
        "paged": {
            "peak_memory": 0,
            "avg_utilization": [],
            "fragmentation_events": 0,  # Should be 0
        },
    }

    # Traditional: pre-allocate max_seq_len for each
    trad_total_allocated = num_sequences * max_seq_len
    trad_total_used = sum(actual_lengths)
    results["traditional"]["max_seq_len"] = max_seq_len
    results["traditional"]["peak_memory"] = trad_total_allocated
    results["traditional"]["avg_utilization"] = (
        trad_total_used / trad_total_allocated
    )

    # Paged: allocate only what's needed (+ partial block overhead)
    paged_blocks_used = sum(
        (l + block_size - 1) // block_size for l in actual_lengths
    )
    paged_tokens_capacity = paged_blocks_used * block_size
    results["paged"]["peak_memory"] = paged_tokens_capacity
    results["paged"]["avg_utilization"] = (
        trad_total_used / paged_tokens_capacity
    )

    return results, actual_lengths


results, lengths = compare_allocation_strategies()

# Calculate improvement metrics
trad_peak = results["traditional"]["peak_memory"]
paged_peak = results["paged"]["peak_memory"]
memory_reduction = 1 - (paged_peak / trad_peak)
capacity_multiplier = 1 / (1 - memory_reduction)

Out[30]:

Console

Allocation Strategy Comparison
==================================================
Sequences: 50
Max sequence length: 2,048 tokens
Actual lengths: min=50, max=1051, avg=292

Traditional Contiguous Allocation:
  Peak memory: 102,400 token slots
  Actual data: 14,582 tokens
  Utilization: 14.2%

Paged Allocation:
  Peak memory: 14,976 token slots
  Actual data: 14,582 tokens
  Utilization: 97.4%

Memory reduction: 85.4%
Could serve 6.8x more sequences with same memory

In[31]:

Code

import matplotlib.pyplot as plt
import numpy as np

use_book_style()
plt.rcParams["figure.figsize"] = (6.0, 4.0)

plt.figure()
plt.hist(
    lengths,
    bins=30,
    edgecolor=PALETTE["ink"],
    alpha=0.7,
    color=theme_color("#3498db"),
)
plt.axvline(
    x=2048,
    color=theme_color("#e74c3c"),
    linestyle="--",
    linewidth=1,
    label="Max length (allocation)",
)
plt.axvline(
    x=np.mean(lengths),
    color=theme_color("#2ecc71"),
    linestyle="-",
    linewidth=1,
    label=f"Mean length ({np.mean(lengths):.0f})",
)
plt.xlabel("Sequence Length (tokens)")
plt.ylabel("Count")
plt.title("Actual Sequence Length Distribution")
plt.legend()
plt.show()

Out[31]:

Visualization

Histogram of sequence lengths showing exponential distribution with most sequences clustered at short lengths, well below the 2048-token maximum allocation line. — Histogram of sequence length distribution compared to maximum allocation capacity. Real-world sequences follow an exponential-like pattern, with most requests falling far below the 2,048-token limit (red dashed line), while the mean (green line) sits at only a fraction of maximum capacity. This mismatch between actual and allocated length is the root cause of traditional KV cache fragmentation.

In[32]:

Code

import matplotlib.pyplot as plt

use_book_style()
plt.rcParams["figure.figsize"] = (6.0, 4.0)

fig, ax = plt.subplots()
strategies = ["Traditional\n(Contiguous)", "Paged\n(vLLM)"]
utilizations = [
    results["traditional"]["avg_utilization"] * 100,
    results["paged"]["avg_utilization"] * 100,
]
colors = theme_color(["#e74c3c", "#2ecc71"])

bars = ax.bar(strategies, utilizations, color=colors, edgecolor=PALETTE["ink"])
ax.set_ylabel("Memory Utilization (%)")
ax.set_title("KV Cache Memory Utilization")
ax.set_ylim(0, 105)

# Add percentage labels
label_bars(ax, bars, labels=[f"{util:.1f}%" for util in utilizations])
polish_axes(ax)
plt.show()

Out[32]:

Visualization

Two-bar chart comparing low memory utilization for traditional contiguous allocation with near-complete utilization for paged allocation; exact percentages are printed above the bars. — Comparison of memory utilization for the same deterministic workload. Traditional allocation reserves the full maximum sequence length for every request, so only a small fraction is used. Paged allocation reserves only the blocks each request needs and therefore approaches complete utilization.

These results show the massive inefficiency of contiguous allocation. The exact values printed above come from the executed deterministic workload: paged allocation approaches full utilization while contiguous pre-allocation uses only a small fraction of its reserved capacity. The reported capacity multiplier shows how many more sequences the same memory could hold under this workload. It bears stressing that this improvement requires no changes to the model, no new hardware, and no change in the quality of the generated output. It is a pure systems optimization.