Skip to main content

KV-Cache: The Hidden Tax

At 128K context, the cache alone exceeds the model weights, leaving room for only a handful of users.

node
intermediate
Discover that KV-cache memory, not model weights or compute, determines how many users a GPU can serve concurrently. Sweep batch size and context length to find the real OOM boundary.

The Question

Llama-3.1-8B is deployed on an 80 GiB (85.9 GB) NVIDIA H100 or NVIDIA A100. The model weights take 16.06 GB (15.0 GiB), leaving 69.8 GB (65.0 GiB) free. Can that GPU serve dozens of users concurrently?

Not if they have long contexts. Every active user requires a KV-cache that grows linearly with sequence length. At 128K context, a single user’s GQA KV-cache takes 17.18 GB (16 GiB), exceeding the model weights and capping concurrency at 4 users (or 1 user at 68.7 GB / 64 GiB without GQA). This tutorial shows where the real memory wall lies and how to push it back.

NotePrerequisites

Complete Tutorial 1: The Memory Wall and Tutorial 2: Two Phases, One Request. This tutorial assumes familiarity with memory-bound vs. compute-bound regimes and the two-phase LLM serving model.

NoteLearning Objectives
  • Calculate the KV-cache size for any model, sequence length, and batch size
  • Identify the OOM boundary where KV-cache exhausts GPU memory
  • Explain why context length, not model size, is the binding memory constraint in serving
  • Compare static batching vs. paged attention for maximizing concurrent users
TipBackground: The KV-Cache

During LLM decoding, every attention layer stores Key and Value matrices for all tokens generated so far. In data-structure terms, this is memoization applied to the attention mechanism: store computed results instead of recomputing them. The names come from a database-style lookup: the Query is what is searched for, the Key is what it is matched against, and the Value is what is retrieved. Without this cache, the model would need to recompute attention over the entire context at every step, at quadratic cost. The KV-cache trades memory for compute:

Factor Effect on KV-Cache
More layers Linear growth (one K + one V per layer)
Longer context Linear growth (one entry per token)
More users (batch) Linear growth (independent cache per user)
Lower precision Proportional reduction (INT8 = half of FP16)

The formula is KV-cache = 2 x layers x kv_heads x head_dim x seq_len x batch x bytes_per_element (or 2 * 2 * layers * kv_heads * head_dim bytes per token in FP16). At short contexts this is negligible. At long contexts it dominates everything.

Note on GQA (Grouped Query Attention): Modern architectures like Llama-3 use GQA, where kv_heads < num_heads. Llama-3.1-8B has 32 layers and 32 attention heads (head dimension 128), yet only 8 KV-heads, reducing the FP16 KV-cache by 4× compared to standard multi-head attention (MHA): from 524,288 bytes (512 KiB) per token under MHA down to \(2 \times 2 \times 32 \times 8 \times 128 = 131\,072\;\text{bytes}\) (128 KiB) per token under GQA. Using num_heads instead of kv_heads in the formula is a common source of 4× overestimates.

1. Setup

import mlsysim
from mlsysim.solvers import ServingModel

2. Single-User Baseline: Where the Memory Goes

The starting point is a single user at a modest 2K context, which shows how memory breaks down:

from mlsysim.solvers import ServingModel

model = mlsysim.Models.Language.Llama3_8B
hardware = mlsysim.Hardware.Cloud.H100
solver = ServingModel()

# Single user, 2K context — the easy case
r = solver.solve(model=model, hardware=hardware, seq_len=2048, batch_size=1, precision="fp16")

from mlsysim.show import table, info

info("Memory Breakdown",
     Model_weights=r.model_weights_size,
     KV_cache_1_user=r.kv_cache_size,
     Total_memory=r.total_memory_required,
     Memory_utilization=f"{r.memory_utilization:.1%}",
     KV_as_pct_of_total=f"{(r.kv_cache_size / r.total_memory_required).magnitude * 100:.1f}%")
── Memory Breakdown ────────────────────────
Model weights:       16.06 GB
KV cache 1 user:     0.268 GB
Total memory:        16.33 GB
Memory utilization:  19.0%
KV as pct of total:  1.6%

At 2K context with one user, the KV-cache is 0.268 GB (1.6% of total memory), a small fraction of the 16.06 GB model weights (and at 4K context it is 0.537 GB, or 0.50 GiB). This is why many engineers assume memory pressure comes from model size, an assumption the next two sweeps overturn.

3. Batch Size Sweep: The Concurrency Wall

Adding users changes the picture. Each concurrent user needs its own KV-cache, so HBM occupancy climbs with batch size:

rows = []
for batch in [1, 4, 8, 16, 32, 64, 128]:
    r = solver.solve(
        model=model, hardware=hardware,
        seq_len=2048, batch_size=batch, precision="fp16"
    )
    rows.append([batch, r.kv_cache_size, r.total_memory_required,
                 f"{r.memory_utilization:.1%}", "OK" if r.feasible else "OOM"])

table(["Batch", "KV-Cache", "Total", "Util", "Feasible"], rows)
Batch  KV-Cache     Total   Util  Feasible
──────────────────────────────────────────
1      0.268 GB  16.33 GB  19.0%        OK
4       1.07 GB  17.13 GB  19.9%        OK
8       2.15 GB  18.21 GB  21.2%        OK
16      4.29 GB  20.35 GB  23.7%        OK
32      8.59 GB  24.65 GB  28.7%        OK
64     17.18 GB  33.24 GB  38.7%        OK
128    34.36 GB  50.42 GB  58.7%        OK

At 2K context, up to 260 concurrent users fit on an 80 GiB (85.9 GB) A100 or H100 (and up to 130 users at 4K context). The KV-cache per user is small enough that batch size scales comfortably. The picture changes sharply, however, once the context grows.

4. Context Length Sweep: The Real Memory Wall

Fix batch size at 8 users and sweep context length from 512 tokens to 128K. This sweep exposes the hidden tax:

rows = []
for ctx in [512, 2048, 4096, 8192, 16384, 32768, 65536, 131072]:
    r = solver.solve(
        model=model, hardware=hardware,
        seq_len=ctx, batch_size=8, precision="fp16"
    )
    rows.append([ctx, r.kv_cache_size, r.model_weights_size,
                 r.total_memory_required, f"{r.memory_utilization:.1%}",
                 "OK" if r.feasible else "OOM"])

table(["Context", "KV-Cache", "Weights", "Total", "Util", "Status"], rows)
Context  KV-Cache   Weights     Total    Util  Status
─────────────────────────────────────────────────────
512      0.537 GB  16.06 GB  16.60 GB   19.3%      OK
2048      2.15 GB  16.06 GB  18.21 GB   21.2%      OK
4096      4.29 GB  16.06 GB  20.35 GB   23.7%      OK
8192      8.59 GB  16.06 GB  24.65 GB   28.7%      OK
16384    17.18 GB  16.06 GB  33.24 GB   38.7%      OK
32768    34.36 GB  16.06 GB  50.42 GB   58.7%      OK
65536    68.72 GB  16.06 GB  84.78 GB   98.7%      OK
131072   137.4 GB  16.06 GB  153.5 GB  178.7%     OOM
ImportantKey Insight

KV-cache grows linearly with sequence length and batch size. It is the hidden memory consumer that determines the maximum number of concurrent users: not model size, not compute, but cache state. At 2K context, the cache is 0.268 GB per user; at 4K context, 0.537 GB (0.50 GiB). At 128K context, a single user’s cache is 17.18 GB (16 GiB), exceeding the 16.06 GB model weights. The same 80 GiB (85.9 GB) GPU that serves 260 users at 2K context (130 at 4K) can serve at most 4 users at 128K context with 4× GQA (and 1 user under standard MHA). The “context length” on the model card is not a feature but a memory bill.

The extreme case is a single user at 128K:

# Single user at 128K context — the extreme case
r_long = solver.solve(
    model=model, hardware=hardware,
    seq_len=131072, batch_size=1, precision="fp16"
)

info("Single User @ 128K Context",
     Context="131,072 tokens (128K)",
     Model_weights=r_long.model_weights_size,
     KV_cache=r_long.kv_cache_size,
     Total=r_long.total_memory_required,
     Feasible=str(r_long.feasible),
     KV_as_pct_of_total=f"{(r_long.kv_cache_size / r_long.total_memory_required).magnitude * 100:.0f}%")
── Single User @ 128K Context ──────────────
Context:             131,072 tokens (128K)
Model weights:       16.06 GB
KV cache:            17.18 GB
Total:               33.24 GB
Feasible:            True
KV as pct of total:  52%

5. Paged Attention: Pushing Back the Wall

The KV-cache fills memory fast, and at long contexts a GPU runs out of memory with only a handful of users. Buying more memory is not the only option, because the allocation strategy itself wastes space. Most sequences do not use the maximum context length, yet static batching reserves memory for the worst case.

Static batching allocates contiguous memory for the maximum sequence length, wasting space on incomplete sequences. PagedAttention (from vLLM) allocates KV-cache in small, fixed-size pages, in the same way an operating system uses virtual memory paging to avoid physical memory fragmentation. Much as the OS maps virtual pages to physical frames on demand, PagedAttention maps KV-cache blocks to GPU memory on demand, eliminating fragmentation and fitting more concurrent requests.

An experiment tests the claim with two allocators competing for the same memory budget. The worst-case context is fixed at 8K tokens, but request lengths are drawn from a long-tailed distribution in which most requests are far shorter than the worst case, the workload for which static allocation wastes the most memory.

Set up the KV math. Reuse the model and GPU from the Silicon Zoo and compute the cache cost of a single token:

import random
from mlsysim import Q_
from mlsysim.show import table

model = mlsysim.Models.Language.Llama3_8B
hardware = mlsysim.Hardware.Cloud.H100

# KV cache bytes per token (FP16): 2 (K+V) x layers x kv_heads x head_dim x 2 bytes
head_dim = model.hidden_dim // model.heads
bytes_per_token = 2 * model.layers * model.kv_heads * head_dim * 2
max_seq = 8192  # worst-case context length we must support
kv_budget = hardware.memory.capacity - model.size_in_bytes()  # HBM left after weights
budget_tokens = int(kv_budget.to("byte").magnitude // bytes_per_token)

The two allocators. Static contiguous reserves a full max_seq slot per request, whether the request needs it or not. Paged hands out fixed-size blocks on demand, so a request pays only for the blocks it fills:

def paged_blocks(tokens, page):
    """Whole blocks needed for `tokens` tokens (ceiling division)."""
    return -(-tokens // page)


def sample_lengths(seed, n, mean=2048, cap=max_seq):
    """n request lengths from a long-tailed distribution (avg well below the cap)."""
    rng = random.Random(seed)
    return [max(1, min(cap, int(rng.expovariate(1 / mean)))) for _ in range(n)]


class StaticAllocator:
    """Static contiguous KV: every request reserves a full max_seq slot up front."""

    def __init__(self, budget_tokens, max_seq):
        self.budget = budget_tokens
        self.max_seq = max_seq
        self.reserved = 0
        self.used_tokens = 0
        self.admitted = []

    def admit(self, tokens):
        if self.reserved + self.max_seq <= self.budget:
            self.reserved += self.max_seq
            self.used_tokens += tokens
            self.admitted.append(tokens)
            return True
        return False


class PagedAllocator:
    """Paged KV: fixed-size blocks handed out on demand from a free-block pool."""

    def __init__(self, budget_tokens, page):
        self.page = page
        self.free_blocks = budget_tokens // page
        self.used_tokens = 0
        self.admitted = []

    def admit(self, tokens):
        need = paged_blocks(tokens, self.page)
        if need <= self.free_blocks:
            self.free_blocks -= need
            self.used_tokens += tokens
            self.admitted.append(tokens)
            return True
        return False

Same memory budget, two strategies. Feed both allocators the same stream of requests in arrival order until the next request no longer fits, and watch where the memory goes:

def fill(alloc, lengths):
    """Admit requests in arrival order; stop at the first one that does not fit."""
    for t in lengths:
        if not alloc.admit(t):
            break
    return alloc


lens = sample_lengths(seed=42, n=10_000)

static = fill(StaticAllocator(budget_tokens, max_seq), lens)
paged16 = fill(PagedAllocator(budget_tokens, 16), lens)
paged64 = fill(PagedAllocator(budget_tokens, 64), lens)
paged256 = fill(PagedAllocator(budget_tokens, 256), lens)


def kv_tokens(alloc):
    if isinstance(alloc, StaticAllocator):
        return alloc.reserved
    return sum(paged_blocks(t, alloc.page) * alloc.page for t in alloc.admitted)


def internal_frag_pct(alloc):
    return 1 - alloc.used_tokens / kv_tokens(alloc)


def decode_throughput(alloc):
    # Memory-bound decode (Tutorial 2): weights + used KV streamed once per token
    step_bytes = model.size_in_bytes().magnitude + alloc.used_tokens * bytes_per_token
    step_sec = step_bytes / hardware.memory.bandwidth.to("byte/s").magnitude
    return len(alloc.admitted) / step_sec


rows = []
for label, alloc in [(f"Static (reserve {max_seq // 1024}K)", static), ("Paged (16 tok)", paged16),
                     ("Paged (64 tok)", paged64), ("Paged (256 tok)", paged256)]:
    rows.append([label, len(alloc.admitted),
                 f"{Q_(kv_tokens(alloc) * bytes_per_token, 'byte').to('GiB'):~.1f}",
                 f"{internal_frag_pct(alloc):.1%}",
                 f"{decode_throughput(alloc):,.0f} t/s"])

table(["System", "Max Users", "KV Allocated", "Int Frag", "Throughput"], rows)
System               Max Users  KV Allocated  Int Frag  Throughput
──────────────────────────────────────────────────────────────────
Static (reserve 8K)         65      65.0 GiB     77.8%   6,894 t/s
Paged (16 tok)             259      64.8 GiB      0.4%  10,162 t/s
Paged (64 tok)             255      64.4 GiB      1.5%  10,152 t/s
Paged (256 tok)            245      64.8 GiB      6.0%  10,075 t/s
ImportantKey Insight

The same 65 GiB KV budget serves 65 users at 77.8% internal fragmentation with static reservation, or 259 users at 0.4% with 16-token pages. Static pays for the worst case (8K) on every request even though the average request is ~4× shorter; paged pays for what is used. The extra concurrency buys 1.47× decode throughput under the memory-bound model from Tutorial 2.

The second kind of waste: external fragmentation. The static allocator above never suffers from this, because every freed slot is a full max_seq and fits any request. That is the trade it makes, paying in internal waste instead. A contiguous allocator that hands out exact sizes avoids the reservation waste but fragments under churn: requests finish out of order, leaving holes too small for the next long request. Paged allocation never fragments this way. Any free block works, so external fragmentation is ~0:

class FirstFitAllocator:
    """Contiguous exact-size allocation: variable-size chunks, first-fit, holes merge on free."""

    def __init__(self, budget_tokens):
        self.budget = budget_tokens
        self.holes = [(0, budget_tokens)]
        self.allocated = {}
        self._next_id = 0

    def admit(self, tokens):
        for i, (s, sz) in enumerate(self.holes):
            if sz >= tokens:
                self.holes.pop(i)
                if sz > tokens:
                    self.holes.insert(i, (s + tokens, sz - tokens))
                self.allocated[self._next_id] = (s, tokens)
                self._next_id += 1
                return True
        return False

    def free(self, rid):
        s, sz = self.allocated.pop(rid)
        self.holes.append((s, sz))
        self.holes.sort()
        merged = []
        for s, sz in self.holes:
            if merged and merged[-1][0] + merged[-1][1] == s:
                merged[-1] = (merged[-1][0], merged[-1][1] + sz)
            else:
                merged.append((s, sz))
        self.holes = merged

    def external_frag_pct(self):
        free = sum(sz for _, sz in self.holes)
        largest = max((sz for _, sz in self.holes), default=0)
        return 0.0 if free == 0 else 1 - largest / free


class PagedPool:
    def __init__(self, budget_tokens, page):
        self.page = page
        self.free_blocks = budget_tokens // page
        self.admitted = []

    def admit(self, tokens):
        need = paged_blocks(tokens, self.page)
        if need <= self.free_blocks:
            self.free_blocks -= need
            self.admitted.append(tokens)
            return True
        return False

    def free(self, tokens):
        self.free_blocks += paged_blocks(tokens, self.page)


rng = random.Random(777)
first_fit = FirstFitAllocator(budget_tokens)
paged = PagedPool(budget_tokens, 16)

# Fill both pools in arrival order until each is full, then complete every other
# request (finish out of order — the churn that fragments contiguous memory).
# Both pools admit a prefix of the same wave, so index i is the same request in each.
wave = [rng.randint(256, max_seq) for _ in range(400)]
fill(first_fit, wave)
fill(paged, wave)

n_done = min(len(first_fit.allocated), len(paged.admitted))
for i in range(0, n_done, 2):
    first_fit.free(i)
    paged.free(paged.admitted[i])

# A fresh wave of worst-case requests arrives — who can still admit them?
new_reqs = [max_seq] * 10
ff_adm = sum(first_fit.admit(t) for t in new_reqs)
pg_adm = sum(paged.admit(t) for t in new_reqs)
free_ff = int(sum(sz for _, sz in first_fit.holes))
table(["System", "External Frag", "Free Tokens", f"New {max_seq // 1024}K Req. Admitted"],
      [["Contiguous (first-fit)", f"{first_fit.external_frag_pct():.1%}", free_ff, f"{ff_adm}/10"],
       ["Paged (16 tok)", "~0%", int(paged.free_blocks * 16), f"{pg_adm}/10"]])
System                  External Frag  Free Tokens  New 8K Req. Admitted
────────────────────────────────────────────────────────────────────────
Contiguous (first-fit)          97.1%       268270                  1/10
Paged (16 tok)                    ~0%       194080                 10/10

Page size: the fragmentation knob. Page size trades waste against bookkeeping. Small pages leave a smaller unused tail on each sequence; large pages mean fewer block-table entries per sequence but waste more. Sweep the page size and watch both:

rows = []
by_page = {}
for page in [8, 16, 64, 256, 1024]:
    a = fill(PagedAllocator(budget_tokens, page), lens)
    by_page[page] = a
    n = len(a.admitted)
    blocks_per_req = sum(paged_blocks(t, page) for t in a.admitted) / n
    rows.append([page, n, f"{internal_frag_pct(a):.1%}", f"{blocks_per_req:.1f}",
                 paged_blocks(max_seq, page), f"{kv_tokens(a) / budget_tokens:.1%}"])

table(["Page Size", "Max Users", "Int Frag", "Avg Blocks/Req",
       f"Blocks/{max_seq // 1024}K Seq", "Pool Used"], rows)
Page Size  Max Users  Int Frag  Avg Blocks/Req  Blocks/8K Seq  Pool Used
────────────────────────────────────────────────────────────────────────
8                259      0.2%           255.7           1024      99.4%
16               259      0.4%           128.1            512      99.6%
64               255      1.5%            32.3            128      99.0%
256              245      6.0%             8.5             32      99.6%
1024             209     22.0%             2.5              8      99.2%

16-token pages (vLLM’s default) sit at the sweet spot: 0.4% waste, with about 128 blocks for an average request and 512 for a full 8K sequence. Going to 1024-token pages shrinks the block table 64-fold (8 entries for a full 8K sequence) but burns 22.0% of the cache as slack and serves 50 fewer users, the wrong trade for long-tail workloads.

The third trick: sharing. Because blocks are first-class, sequences can share them. Eight requests that begin with the same 1K-token system prompt (or eight beam-search branches that fork from one prefix) can point at the same blocks via reference counts (copy-on-write) instead of storing the prefix eight times:

prefix, gen, n_req = 1024, 512, 8

rows = []
static_kv = n_req * max_seq
no_share = n_req * paged_blocks(prefix + gen, 16) * 16
shared = paged_blocks(prefix, 16) * 16 + n_req * paged_blocks(gen, 16) * 16
for label, kv in [("Static (reserve max)", static_kv),
                  ("Paged, no sharing", no_share),
                  ("Paged + shared prefix", shared)]:
    rows.append([label, f"{Q_(kv * bytes_per_token, 'byte').to('MiB'):~.1f}",
                 f"{kv / static_kv:.1%}"])

table(["Scheme", "KV Allocated", "vs Static"], rows)
Scheme                 KV Allocated  vs Static
──────────────────────────────────────────────
Static (reserve max)     8192.0 MiB     100.0%
Paged, no sharing        1536.0 MiB      18.8%
Paged + shared prefix     640.0 MiB       7.8%

Sharing the prefix cuts peak KV from 1536 MiB to 640 MiB, a 58% saving that grows with the number of concurrent requests sharing the prompt. Production systems call this prefix caching; it is why shared system prompts and few-shot examples are cheap to serve.

Paged attention therefore attacks the memory wall from three directions at once: it eliminates reservation waste (77.8% → 0.4% internal fragmentation), survives churn with ~0 external fragmentation, and shares common prefixes across requests. This is why vLLM and TensorRT-LLM default to paged KV-cache management in production.

Next Steps

  • Quantization: Not a Free Lunch: Learn when reducing precision shrinks the KV-cache effectively vs. when it does not help
  • Two Phases, One Request: Revisit the prefill/decode split with the cache pressure in view
  • Where to Invest: Use sensitivity analysis to quantify whether more memory or more bandwidth helps more
  • Silicon Zoo: Compare HBM capacity across H100, H200, MI300X, and see which GPUs tolerate long context
Back to top