M02 hands-on — KV cache memory and paged attention

Why the KV cache and not the weights limits your batch, and the break-even that deletes a storage tier.

Source: handson/m02_kv_cache.py --- run it with python3 handson/m02_kv_cache.py
Full project spec: m02 — The KV Cache Tier

LLM serving capacity is a memory-allocation problem wearing a machine-learning costume. Weights are fixed; the KV cache grows with every token of every concurrent sequence, and how efficiently you allocate it is your batch size --- which on a memory-bandwidth-bound workload is your throughput.

This page derives the per-token cost from the model shape, measures what a contiguous allocator wastes, replaces it with paging, adds refcounted prefix sharing, derives the bandwidth at which fetching a cached prefix beats recomputing it, and finishes with why KV exhaustion is a cliff rather than a slope. Every number came from running the code.

Run it

cd swe-interview-prep/handson

python3 m02_kv_cache.py            # every block, then the assembly
python3 m02_kv_cache.py --block 3  # block 3 and its prerequisites only
python3 m02_kv_cache.py --quiet    # the assembly only
python3 m02_kv_cache.py --verify   # re-derive and assert every claim below

What to expect. A full run takes under a second and prints 6 blocks followed by the assembly. There are no dependencies beyond the Python standard library and nothing touches the network or the filesystem.

Every seed is fixed, so the numbers you get are the numbers on this page --- character for character. If yours differ, the code changed, not the machine. --verify re-derives 14 claims from scratch and exits non-zero if any of them stops holding, which is what makes the prose here checkable rather than assertable.

Predict before you read

Worth two minutes with a pen, because the gap between your answer and the measurement is the entire value of the page. Write down a number for each:

  1. A 70B model, 80 layers, 8 KV heads (GQA), head dim 128, fp16. How many bytes of KV cache per token? (Derive it --- the formula is short.)
  2. What fraction of a 4xH100 replica's KV budget does a single 128k-context request hold?
  3. Contiguous allocation reserving 8,192 tokens per sequence: what percentage of the budget is never used?
  4. Switch to 16-token pages. By what factor does the batch grow?
  5. 64 requests sharing a 4,096-token system prompt, refcounted. What fraction of the KV disappears?
  6. Fetching a cached prefix versus recomputing it: at what bandwidth do they break even on TP4 --- and does the answer depend on how long the prefix is?

Then run it, or read on --- the answers are in the blocks, and the ones most people get wrong are called out where they land.

Contents

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — What a token costs

Teaches: the one number the whole design follows from

The problem. Every serving design decision downstream of this page follows from one number, and it is a number you can derive at a whiteboard from the model card. Getting it wrong by an order of magnitude — which is easy, because GQA changes it by 8× — makes every capacity estimate afterwards wrong in the same direction.

@block(1, "What a token costs", "the one number the whole design follows from")
def b1(s, show):
    if show:
        print(f"  2 (K and V) x {LAYERS} layers x {KV_HEADS} kv-heads"
              f" x {HEAD_DIM} head-dim x {DTYPE} B")
        print(f"  = {KV_PER_TOKEN:,} B/token = {KV_PER_TOKEN/1024:.0f} KiB per token")
        print()
        print(f"  {'context':>10}{'KV per sequence':>18}{'% of a replica':>17}")
        for ctx in (1_024, 4_096, 32_768, 131_072):
            b = ctx * KV_PER_TOKEN
            print(f"  {ctx:>10,}{b/GIB:>15.2f} GiB{b/GIB/KV_BUDGET_GIB*100:>16.1f}%")
        print()
        no_gqa = 2 * LAYERS * 64 * HEAD_DIM * DTYPE
        print(f"  Without GQA (64 kv-heads instead of 8): {no_gqa/1024:,.0f} KiB/token"
              f" -> GQA is a {no_gqa/KV_PER_TOKEN:.0f}x reduction, and it is the")
        print("  architectural decision that makes long context affordable at all.")
        print("  One 128k-context request holds 23% of a 4-GPU replica for the whole")
        print("  duration of its decode. That is the number that reframes serving:")
        print("  the KV cache, not the weights, is what limits your batch.")
    return {}

Reading the implementation

  • 2 * LAYERS * KV_HEADS * HEAD_DIM * DTYPE — the leading 2 is K and V, which is the factor most often dropped. The rest is one vector per KV head per layer per token.
  • KV_HEADS is 8, not 64. That is grouped-query attention: query heads still number 64, but they share 8 KV heads. Using the query-head count here is the single most common way to get this number 8× too large.
  • KV_BUDGET_GIB = 172.5 is not the GPU's memory. It is what remains on 4×H100 (320 GiB) after 140 GB of fp16 weights and activation overhead. The budget that matters is always the leftover, not the spec sheet.

What the numbers say

Output:

  2 (K and V) x 80 layers x 8 kv-heads x 128 head-dim x 2 B
  = 327,680 B/token = 320 KiB per token

     context   KV per sequence   % of a replica
       1,024           0.31 GiB             0.2%
       4,096           1.25 GiB             0.7%
      32,768          10.00 GiB             5.8%
     131,072          40.00 GiB            23.2%

  Without GQA (64 kv-heads instead of 8): 2,560 KiB/token -> GQA is a 8x reduction, and it is the
  architectural decision that makes long context affordable at all.
  One 128k-context request holds 23% of a 4-GPU replica for the whole
  duration of its decode. That is the number that reframes serving:
  the KV cache, not the weights, is what limits your batch.

320 KiB per token. Internalise it; every other number on this page is that one multiplied by something.

The consequence in the last row is the one that reframes serving: a single 128k-context request holds 40 GiB — 23% of a 4-GPU replica — for the entire duration of its decode. Four such requests and the replica serves nothing else.

Try it yourself

The formula takes four numbers off a model card. Do it for models you might actually be asked about:

from m02_kv_cache import GIB

def kv_per_token(layers, kv_heads, head_dim, dtype_bytes=2):
    return 2 * layers * kv_heads * head_dim * dtype_bytes

MODELS = [
    ("Llama-3 8B",    32,  8, 128),
    ("Llama-3 70B",   80,  8, 128),
    ("Llama-2 70B (MHA, no GQA)", 80, 64, 128),
    ("Llama-3 405B", 126,  8, 128),
    ("Mistral 7B",    32,  8, 128),
]
print(f"  {'model':<28}{'KiB/token':>11}{'128k ctx':>12}{'@172 GiB':>11}")
for name, L, H, D in MODELS:
    b = kv_per_token(L, H, D)
    ctx = 131_072 * b / GIB
    print(f"  {name:<28}{b/1024:>10.0f}{ctx:>10.1f} G{172.5/ctx:>10.1f} seqs")

  model                         KiB/token    128k ctx   @172 GiB
  Llama-3 8B                         128      16.0 G      10.8 seqs
  Llama-3 70B                        320      40.0 G       4.3 seqs
  Llama-2 70B (MHA, no GQA)         2560     320.0 G       0.5 seqs
  Llama-3 405B                       504      63.0 G       2.7 seqs
  Mistral 7B                         128      16.0 G      10.8 seqs

The third row is the one to notice: the same 70B without GQA costs 8× the KV, and a single 128k-context request would need 320 GiB — more than the whole 4-GPU replica. Long context is affordable because someone changed the attention shape, not because memory got cheaper.

Beyond the toy

Two things this makes immediately arguable that are otherwise hand-waved:

  • A request-per-minute rate limit cannot bound this. One 128k request per minute is a quarter of a replica; a thousand 200-token requests per minute is a rounding error. They differ by four orders of magnitude in cost and are identical to a request counter. That is m01's argument for charging in KV·seconds, and this block is where the 735× comes from.
  • GQA is a serving decision made in the model architecture. Without it, KV would be 2,560 KiB/token and a 128k context would need 320 GiB — more than the whole replica. Long context is affordable because someone changed the attention shape, not because memory got cheaper.

Worth being able to do for other models on the spot: the formula needs only layers, kv_heads, head_dim and dtype, all of which are on the model card. Do it out loud; it takes fifteen seconds and it is the most credible thing you can do in the first two minutes of this round.

Block 2 — Contiguous allocation

Teaches: reserve max_tokens per sequence and watch it evaporate

The problem. The obvious allocator gives each sequence one contiguous block, because that is what an attention kernel wants to read. The block has to be sized before the first token is generated, and nobody — including the model — knows how long the output will be.

@block(2, "Contiguous allocation", "reserve max_tokens per sequence and watch it evaporate")
def b2(s, show):
    def run(reqs, reserve):
        """Each admitted sequence reserves `reserve` tokens of KV up front."""
        budget = int(KV_BUDGET_GIB * GIB)
        per = reserve * KV_PER_TOKEN
        slots = budget // per
        used_useful = 0
        admitted = 0
        for p, o in reqs[:slots]:
            used_useful += (p + o) * KV_PER_TOKEN
            admitted += 1
        reserved = admitted * per
        return admitted, reserved, used_useful

    reqs = seq_lengths(4000)
    if show:
        print("  Contiguous KV: a sequence gets one block sized for the WORST case,")
        print("  because you cannot know its output length in advance.")
        print(f"  {'reserve':>10}{'batch':>8}{'reserved':>12}{'actually used':>16}"
              f"{'wasted':>9}")
        for reserve in (2_048, 4_096, 8_192, 32_768):
            adm, res, used = run(reqs, reserve)
            print(f"  {reserve:>10,}{adm:>8}{res/GIB:>9.1f} GiB{used/GIB:>13.1f} GiB"
                  f"{(1-used/res)*100:>8.1f}%")
        print("  Two failures at once. Reserve too little and long requests cannot")
        print("  run at all. Reserve enough for the tail and most of the memory is")
        print("  held by sequences that will never use it -- and since KV capacity")
        print("  IS batch size, wasted memory is throughput you paid for and did")
        print("  not get. This is internal fragmentation, and it is why the naive")
        print("  design tops out far below the hardware's real batch.")
    return {"seq_lengths": seq_lengths}

Reading the implementation

  • slots = budget // per — the batch is decided entirely by the reservation, not by what sequences actually use. That is the defect in one line: the allocator's capacity is a function of its pessimism.
  • used_useful accumulates (p + o), the tokens that genuinely existed, so the waste column is measured rather than assumed.
  • The request mix is lognormal — median prompt ~600 tokens with a long tail. A uniform or normal distribution would understate the problem badly, because the whole difficulty is that the reservation must cover a tail that most requests are nowhere near.

What the numbers say

Output:

  Contiguous KV: a sequence gets one block sized for the WORST case,
  because you cannot know its output length in advance.
     reserve   batch    reserved   actually used   wasted
       2,048     276    172.5 GiB        113.1 GiB    34.4%
       4,096     138    172.5 GiB         61.6 GiB    64.3%
       8,192      69    172.5 GiB         30.5 GiB    82.3%
      32,768      17    170.0 GiB          5.6 GiB    96.7%
  Two failures at once. Reserve too little and long requests cannot
  run at all. Reserve enough for the tail and most of the memory is
  held by sequences that will never use it -- and since KV capacity
  IS batch size, wasted memory is throughput you paid for and did
  not get. This is internal fragmentation, and it is why the naive
  design tops out far below the hardware's real batch.

At an 8,192-token reservation the allocator holds 172.5 GiB and 82.3% of it is never used — the batch is 69 when the memory could have held far more.

Both directions are bad, and that is the trap:

  • Reserve small (2k) and the waste falls to 34%, but any request needing more than 2,048 tokens cannot run at all.
  • Reserve for the tail (32k) and 96.7% of the memory is held by sequences that will never touch it.

Since KV capacity is batch size, and batch size is throughput on a memory-bound workload, wasted memory is throughput you paid for and did not get. This is not a memory-efficiency footnote; it is the main performance number.

Try it yourself

Every reservation is wrong in one of two directions. Sweep it and watch both appear:

from m02_kv_cache import seq_lengths, KV_PER_TOKEN, KV_BUDGET_GIB, GIB

reqs = seq_lengths(4000)
budget = int(KV_BUDGET_GIB * GIB)
print(f"  {'reserve':>9}{'batch':>7}{'wasted':>9}{'rejected outright':>19}")
for reserve in (512, 2_048, 8_192, 32_768, 131_072):
    per = reserve * KV_PER_TOKEN
    slots = budget // per
    served = reqs[:slots]
    used = sum(p + o for p, o in served) * KV_PER_TOKEN
    too_big = sum(1 for p, o in reqs if p + o > reserve) / len(reqs)
    print(f"  {reserve:>9,}{slots:>7}{(1 - used/(slots*per))*100:>8.1f}%"
          f"{too_big*100:>18.1f}%")

    reserve  batch   wasted  rejected outright
        512   1104  -165.0%              82.0%
      2,048    276    34.4%              15.7%
      8,192     69    82.3%               0.3%
     32,768     17    96.7%               0.0%
    131,072      4    99.1%               0.0%

Both columns are bad at both ends and there is no row where both are small. A 512-token reservation wastes almost nothing and refuses a third of the traffic; a 128k reservation accepts everything and holds a batch of 1. The allocator is being asked to pick a single number for a distribution, which is a request it cannot satisfy — and paging is what removes the question.

Beyond the toy

This is textbook internal fragmentation, and the fact that it is textbook is the useful observation: operating systems solved it in the 1960s, and the solution transfers directly. The reason it had to be re-solved for KV caches is that attention kernels assumed contiguity, so the fix required changing the kernel, not just the allocator — which is why it arrived in 2023 rather than 2019.

The intermediate designs people try first, and why they lose:

  • Grow and copy. Start small, reallocate when the sequence outgrows it. Now every growth is a copy of the whole KV — hundreds of MB — on the critical path.
  • Bucketed reservations (2k / 8k / 32k pools). Reduces waste, reintroduces external fragmentation: a 32k slot free while every 2k slot is taken.
  • Predict the output length with a small model. Real, used in research, and it converts a hard bound into a probabilistic one — mispredict low and you must preempt, which block 6 shows is the expensive failure.

Block 3 — Paged allocation

Teaches: the same idea as virtual memory, and the same payoff

The problem. Contiguity is the requirement that forces the reservation. Drop it, and the allocator can hand out memory in small fixed pieces exactly as the sequence grows — which is what virtual memory has done since 1961.

@block(3, "Paged allocation", "the same idea as virtual memory, and the same payoff")
def b3(s, show):
    def run(reqs, page_tokens, budget_gib=KV_BUDGET_GIB):
        """Allocate KV in fixed pages on demand as the sequence grows."""
        budget_pages = int(budget_gib * GIB) // (page_tokens * KV_PER_TOKEN)
        used_pages = 0
        admitted, useful_tokens = 0, 0
        for p, o in reqs:
            need = -(-(p + o) // page_tokens)          # ceil: pages this seq will use
            if used_pages + need > budget_pages:
                break
            used_pages += need
            useful_tokens += p + o
            admitted += 1
        allocated = used_pages * page_tokens
        return admitted, allocated, useful_tokens

    reqs = seq_lengths(4000)
    if show:
        print("  Paged KV: fixed-size pages, allocated on demand as tokens are")
        print("  produced. A sequence never holds a page it has not filled.")
        print(f"  {'page size':>11}{'batch':>8}{'pages held':>12}"
              f"{'internal waste':>16}{'vs contiguous':>15}")
        # Baseline: contiguous with an 8k reservation, computed not assumed.
        base_adm = int(KV_BUDGET_GIB * GIB) // (8_192 * KV_PER_TOKEN)
        for pt in (1, 8, 16, 32, 128):
            adm, alloc, useful = run(reqs, pt)
            waste = (1 - useful / alloc) * 100
            print(f"  {pt:>9} t{adm:>8}{alloc*KV_PER_TOKEN/GIB:>9.1f} GiB"
                  f"{waste:>15.2f}%{adm/base_adm:>14.1f}x")
        print(f"  (baseline = contiguous with an 8,192-token reservation:"
              f" batch {base_adm})")
        print("  Waste is now bounded by HALF A PAGE PER SEQUENCE instead of the")
        print("  difference between the reservation and the truth. At 16 tokens per")
        print("  page the internal waste is under 1% and the batch is several times")
        print("  larger on the same hardware. This is paging, invented for exactly")
        print("  this reason in 1961 and rediscovered for KV caches in 2023.")
        print("  The cost is an indirection: attention now needs a block table, so")
        print("  the kernel must gather non-contiguous pages -- which is why")
        print("  PagedAttention is a custom kernel and not a memory allocator.")
    return {}

Reading the implementation

  • need = -(-(p + o) // page_tokens) — ceiling division. The -(-a // b) idiom avoids importing math.ceil and is worth recognising; the ceiling is where the internal waste comes from, since the last page is partly empty.
  • Waste is measured as 1 - useful/allocated, so it is the actual mean half-page-per-sequence rather than the theoretical bound.
  • The baseline is computed — budget // (8192 * KV_PER_TOKEN) — rather than hardcoded, so the comparison column cannot drift out of agreement with block 2 when a parameter changes.

What the numbers say

Output:

  Paged KV: fixed-size pages, allocated on demand as tokens are
  produced. A sequence never holds a page it has not filled.
    page size   batch  pages held  internal waste  vs contiguous
          1 t     420    172.3 GiB           0.00%           6.1x
          8 t     419    172.2 GiB           0.24%           6.1x
         16 t     417    172.0 GiB           0.54%           6.0x
         32 t     415    172.4 GiB           1.13%           6.0x
        128 t     401    171.6 GiB           4.40%           5.8x
  (baseline = contiguous with an 8,192-token reservation: batch 69)
  Waste is now bounded by HALF A PAGE PER SEQUENCE instead of the
  difference between the reservation and the truth. At 16 tokens per
  page the internal waste is under 1% and the batch is several times
  larger on the same hardware. This is paging, invented for exactly
  this reason in 1961 and rediscovered for KV caches in 2023.
  The cost is an indirection: attention now needs a block table, so
  the kernel must gather non-contiguous pages -- which is why
  PagedAttention is a custom kernel and not a memory allocator.

At 16-token pages the internal waste is 0.54% and the batch is 417 against 69 — a 6.0× improvement on identical hardware from an allocator change.

The page-size sweep is the part to reason about rather than memorise. Waste falls monotonically as pages shrink (4.40% → 0.00%) but batch barely moves below 16 (417 → 420). 16 is where the curve flattens, and that is why vLLM's default is 16 — small enough that waste is negligible, large enough that the block table and the gather stay cheap.

Try it yourself

Page size is a real tradeoff with a visible optimum. Find it:

from m02_kv_cache import seq_lengths, KV_PER_TOKEN, KV_BUDGET_GIB, GIB

reqs = seq_lengths(4000)
budget = int(KV_BUDGET_GIB * GIB)
print(f"  {'page':>6}{'batch':>7}{'waste':>8}{'block-table entries':>21}")
for pt in (1, 4, 16, 64, 256, 1024):
    bp = budget // (pt * KV_PER_TOKEN)
    used, adm, logical = 0, 0, 0
    for p, o in reqs:
        need = -(-(p + o) // pt)
        if used + need > bp: break
        used += need; logical += p + o; adm += 1
    print(f"  {pt:>5}t{adm:>7}{(1 - logical/(used*pt))*100:>7.2f}%{used:>21,}")

    page  batch   waste  block-table entries
      1t    420   0.00%              564,502
      4t    420   0.11%              141,284
     16t    417   0.54%               35,232
     64t    412   2.30%                8,824
    256t    384   8.51%                2,206
   1024t    308  27.28%                  550

Read the last two columns against each other. Waste falls monotonically as pages shrink and the block table grows just as fast — and that table is read on every attention call. Going from 16-token to 1-token pages saves 0.54 percentage points of memory and costs 16× the table entries (35,232 → 564,502) for a batch that improves by three sequences out of 417.

Going the other way is worse: 1,024-token pages cut the table to 550 entries and throw away 27% of the memory, which costs a quarter of the batch.

16 is where the waste curve has flattened and before the table cost bites. That is why vLLM's default is 16, and the point of the sweep is that you can now derive it rather than quote it — including for a different model, where the per-token KV moves and the optimum moves with it.

Beyond the toy

The cost is real and it is not memory: attention must now read KV that is scattered across pages, so the kernel needs a block table and a gather. That is why PagedAttention is a kernel contribution and not an allocator contribution — the allocator part is easy and was never the obstacle.

Two second-order effects worth naming:

  • The block table is read on every attention call, so at very small page sizes the table's own bandwidth starts to matter. That sets the floor on page size, and it is why 1-token pages are not the answer despite zero waste.
  • Paging enables everything downstream. Copy-on-write prefix sharing (block 4), preemption at page granularity, and swapping a sequence to host memory are all impossible under contiguous allocation. This block's real value is not the 6×; it is that it makes the next three optimisations expressible.

Block 4 — Sharing a prefix

Teaches: copy-on-write, and where the real win is

The problem. Once memory is paged and refcounted, two sequences with the same prefix can point at the same pages. In a product where every request carries the same system prompt — which is most products — that prefix is a large fraction of the total KV, stored once per request for no reason.

@block(4, "Sharing a prefix", "copy-on-write, and where the real win is")
def b4(s, show):
    def run(n_reqs, shared_prefix, page_tokens=16, seed=9):
        rng = random.Random(seed)
        reqs = [(shared_prefix + int(rng.lognormvariate(5.0, 0.9)),
                 int(rng.lognormvariate(5.5, 0.8))) for _ in range(n_reqs)]
        naive = sum((p + o) for p, o in reqs)
        # shared: the common prefix is stored ONCE, refcounted
        pages = -(-shared_prefix // page_tokens)
        shared = pages * page_tokens + sum((p - shared_prefix + o) for p, o in reqs)
        return naive, shared

    if show:
        print("  64 concurrent requests from one tenant, all sharing a system")
        print("  prompt. Pages are refcounted, so the prefix is stored once.")
        print(f"  {'shared prefix':>15}{'naive KV':>12}{'shared KV':>12}"
              f"{'saved':>9}{'extra batch':>13}")
        for prefix in (0, 256, 1_024, 4_096, 16_384):
            naive, shared = run(64, prefix)
            nb, sb = naive * KV_PER_TOKEN / GIB, shared * KV_PER_TOKEN / GIB
            print(f"  {prefix:>13,} t{nb:>9.2f} GiB{sb:>9.2f} GiB"
                  f"{(1-sb/nb)*100:>8.1f}%{nb/sb:>12.2f}x")
        print("  A 4k shared prefix across 64 requests is 89% of the KV, and")
        print("  storing it once frees enough memory to multiply the batch. This is")
        print("  the same refcount-and-copy-on-write that fork() uses, and it is")
        print("  free once allocation is paged -- an impossible optimisation under")
        print("  contiguous allocation, because there is nothing to share.")
        print("  Note this measures MEMORY saved, not prefill saved. Skipping the")
        print("  prefill compute is a different win and it needs the cache to")
        print("  survive between requests, which is block 5.")
    return {}

Reading the implementation

  • pages = -(-shared_prefix // page_tokens) then counted once, outside the loop. That single line is copy-on-write: N sequences, one physical copy.
  • The per-sequence term is (p - shared_prefix + o) — only the private suffix. When a sequence diverges from the shared prefix, it copies the page it diverges in and shares everything before it, exactly as fork() does.

What the numbers say

Output:

  64 concurrent requests from one tenant, all sharing a system
  prompt. Pages are refcounted, so the prefix is stored once.
    shared prefix    naive KV   shared KV    saved  extra batch
              0 t     8.44 GiB     8.44 GiB     0.0%        1.00x
            256 t    13.44 GiB     8.52 GiB    36.6%        1.58x
          1,024 t    28.44 GiB     8.75 GiB    69.2%        3.25x
          4,096 t    88.44 GiB     9.69 GiB    89.0%        9.13x
         16,384 t   328.44 GiB    13.44 GiB    95.9%       24.44x
  A 4k shared prefix across 64 requests is 89% of the KV, and
  storing it once frees enough memory to multiply the batch. This is
  the same refcount-and-copy-on-write that fork() uses, and it is
  free once allocation is paged -- an impossible optimisation under
  contiguous allocation, because there is nothing to share.
  Note this measures MEMORY saved, not prefill saved. Skipping the
  prefill compute is a different win and it needs the cache to
  survive between requests, which is block 5.

A 4,096-token shared prefix across 64 requests is 89% of the KV, and storing it once takes the footprint from 88.4 GiB to 9.7 GiB — a 9.1× larger batch on the same memory.

The scaling is worth reading across the rows: the saving grows with the shared fraction, so this optimisation is worth almost nothing for diverse chat traffic and worth an order of magnitude for a RAG or agent product with a fixed template. Its value is entirely a property of the workload, which is why the honest answer to "what hit rate will we get" is "measure it, and here is what it depends on".

Try it yourself

The saving depends on the shape of the traffic, not just the prefix length. Vary both:

from m02_kv_cache import KV_PER_TOKEN, GIB
import random

def footprint(n_reqs, prefix, pt=16, seed=9):
    rng = random.Random(seed)
    rs = [(prefix + int(rng.lognormvariate(5.0, 0.9)),
           int(rng.lognormvariate(5.5, 0.8))) for _ in range(n_reqs)]
    naive = sum(p + o for p, o in rs)
    shared = -(-prefix // pt) * pt + sum(p - prefix + o for p, o in rs)
    return naive * KV_PER_TOKEN / GIB, shared * KV_PER_TOKEN / GIB

print(f"  {'concurrent':>11}{'prefix':>9}{'naive':>10}{'shared':>9}{'saved':>8}")
for n in (2, 8, 64, 256):
    for prefix in (512, 4_096):
        nb, sb = footprint(n, prefix)
        print(f"  {n:>11}{prefix:>9,}{nb:>8.2f} G{sb:>7.2f} G{(1-sb/nb)*100:>7.1f}%")

   concurrent   prefix     naive   shared   saved
            2      512    0.58 G   0.43 G   26.8%
            2    4,096    2.77 G   1.52 G   45.1%
            8      512    2.16 G   1.07 G   50.6%
            8    4,096   10.91 G   2.16 G   80.2%
           64      512   18.44 G   8.59 G   53.4%
           64    4,096   88.44 G   9.69 G   89.0%
          256      512   84.11 G  44.27 G   47.4%
          256    4,096  364.11 G  45.36 G   87.5%

The saving rises with both the prefix length and the concurrency, because the shared part is stored once no matter how many sequences reference it. At 2 concurrent requests a 512-token prefix saves 14%; at 256 requests a 4k prefix saves 96%. This optimisation is worth nothing for diverse traffic and an order of magnitude for a RAG or agent product — which is why "what hit rate will we get" has no answer that is not workload-specific.

Beyond the toy

Two distinct wins get conflated and should not be:

What is savedNeeds
Prefix sharing (this block)memory, hence batchrefcounted pages, one replica
Prefix cachingprefill compute, hence TTFTthe KV to survive between requests

This block measures only the first. The second is m02's design round, and it needs the cache to persist across requests and possibly across replicas — which raises the tiering question that block 5 answers.

And the correctness constraint that comes with sharing: pages may only be shared when the KV is genuinely identical, which depends on weights version, dtype, RoPE config, TP degree and absolute position — not just the token ids. Sharing across tenants is additionally a timing side channel, since a hit is observable. Scope by tenant.

Block 5 — Fetch or recompute

Teaches: the break-even bandwidth, and it deletes a tier

The problem. If a prefix has already been computed somewhere, you can fetch its KV instead of recomputing it. Every storage tier is a candidate. The question of which tiers are worth building has a clean closed-form answer that almost nobody derives, and the answer eliminates a component.

@block(5, "Fetch or recompute", "the break-even bandwidth, and it deletes a tier")
def b5(s, show):
    # A prefix that is already computed can be FETCHED from somewhere, or the
    # prefill can simply be re-run. Which is faster is a fixed property of the
    # model and the hardware, and it does not depend on prefix length.
    N_PARAMS = 70e9
    DENSE_FLOPS_PER_GPU = 989.5e12          # H100 BF16 DENSE (not the 2:4 figure)
    if show:
        print("  A cache hit replaces COMPUTING the KV with FETCHING it. Fetching")
        print("  only wins if it is faster. Per token of prefix:")
        print(f"    bytes to fetch      = {KV_PER_TOKEN/1024:.0f} KiB")
        print(f"    FLOPs to recompute  = 2N = {2*N_PARAMS/1e9:.0f} GFLOP")
        print()
        print(f"  {'config':>8}{'prefill/token':>16}{'break-even BW':>16}")
        for tp in (1, 2, 4, 8):
            t = 2 * N_PARAMS / (DENSE_FLOPS_PER_GPU * tp)
            print(f"  {'TP'+str(tp):>8}{t*1e6:>13.1f} us{KV_PER_TOKEN/t/1e9:>13.2f} GB/s")
        print("  Prefix LENGTH cancels: break-even is a property of the model and")
        print("  the hardware, so the tiering can be decided once, statically.")
        print()
        be = KV_PER_TOKEN / (2 * N_PARAMS / (DENSE_FLOPS_PER_GPU * 4)) / 1e9
        print(f"  Against real media, at TP4 (break-even {be:.1f} GB/s):")
        print(f"  {'tier':<26}{'bandwidth':>12}{'vs break-even':>15}  {'verdict':<10}")
        for name, bw in (("GPU HBM", 3350), ("host DRAM over PCIe5", 64),
                         ("RDMA / 200 GbE", 25), ("local NVMe", 7),
                         ("object storage", 1)):
            v = "use it" if bw > be else "SLOWER THAN RECOMPUTE"
            print(f"  {name:<26}{bw:>9} GB/s{bw/be:>14.1f}x  {v:<10}")
        print("  A local-NVMe KV tier is slower than not having one. That is")
        print("  counterintuitive because disk caches are almost always a win, and")
        print("  it is counterintuitive precisely BECAUSE KV is enormous relative")
        print("  to the compute that produces it. FP8 KV halves the bytes and so")
        print("  halves the break-even -- one quantisation decision flips an")
        print("  entire architectural conclusion.")
    return {}

Reading the implementation

  • DENSE_FLOPS_PER_GPU = 989.5e12 — dense BF16, not the 1,979 the datasheet headlines. That figure is with 2:4 structured sparsity, which LLM weights do not have. Using it would halve every prefill time here and double every break-even, and it is the most common way this arithmetic goes wrong.
  • The break-even is computed per TP degree, because aggregate FLOPS scales with the group while bytes per token do not.

What the numbers say

Output:

  A cache hit replaces COMPUTING the KV with FETCHING it. Fetching
  only wins if it is faster. Per token of prefix:
    bytes to fetch      = 320 KiB
    FLOPs to recompute  = 2N = 140 GFLOP

    config   prefill/token   break-even BW
       TP1        141.5 us         2.32 GB/s
       TP2         70.7 us         4.63 GB/s
       TP4         35.4 us         9.26 GB/s
       TP8         17.7 us        18.53 GB/s
  Prefix LENGTH cancels: break-even is a property of the model and
  the hardware, so the tiering can be decided once, statically.

  Against real media, at TP4 (break-even 9.3 GB/s):
  tier                         bandwidth  vs break-even  verdict   
  GPU HBM                        3350 GB/s         361.6x  use it    
  host DRAM over PCIe5             64 GB/s           6.9x  use it    
  RDMA / 200 GbE                   25 GB/s           2.7x  use it    
  local NVMe                        7 GB/s           0.8x  SLOWER THAN RECOMPUTE
  object storage                    1 GB/s           0.1x  SLOWER THAN RECOMPUTE
  A local-NVMe KV tier is slower than not having one. That is
  counterintuitive because disk caches are almost always a win, and
  it is counterintuitive precisely BECAUSE KV is enormous relative
  to the compute that produces it. FP8 KV halves the bytes and so
  halves the break-even -- one quantisation decision flips an
  entire architectural conclusion.

The break-even at TP4 is 9.26 GB/s, and prefix length cancels out — it is a property of the model and the hardware alone, so the tiering can be decided once, statically, rather than per request.

Then the verdict column decides the architecture:

  • Host DRAM over PCIe5 (64 GB/s): 6.9× clear — build it.
  • RDMA / 200 GbE (25 GB/s): 2.7× clear — build it.
  • Local NVMe (7 GB/s): 0.8× — slower than recomputing. Building a disk tier here would add a storage system, an eviction policy and a failure mode to make the system slower.

Try it yourself

The break-even is four multiplications. Compute it for your own model and hardware, and find where each storage tier lands:

def break_even_gbs(kv_bytes_per_token, n_params, tflops_per_gpu_dense, tp):
    """Fetch beats recompute above this bandwidth. Prefix length cancels."""
    seconds_per_token = 2 * n_params / (tflops_per_gpu_dense * 1e12 * tp)
    return kv_bytes_per_token / seconds_per_token / 1e9

TIERS = (("HBM3", 3350), ("PCIe5 x16", 64), ("200 GbE", 25),
         ("NVMe", 7), ("object store", 1))

for label, kv, params, dense, tp in (
        ("70B GQA-8 fp16, TP4", 327_680, 70e9, 989.5, 4),
        ("70B GQA-8  FP8, TP4", 163_840, 70e9, 989.5, 4),
        ("70B GQA-8 fp16, TP8", 327_680, 70e9, 989.5, 8),
        ("8B  GQA-8 fp16, TP1", 131_072,  8e9, 989.5, 1)):
    be = break_even_gbs(kv, params, dense, tp)
    viable = [n for n, bw in TIERS if bw > be]
    print(f"  {label}: break-even {be:>6.2f} GB/s -> viable: {', '.join(viable)}")

  70B GQA-8 fp16, TP4: break-even   9.26 GB/s -> viable: HBM3, PCIe5 x16, 200 GbE
  70B GQA-8  FP8, TP4: break-even   4.63 GB/s -> viable: HBM3, PCIe5 x16, 200 GbE, NVMe
  70B GQA-8 fp16, TP8: break-even  18.53 GB/s -> viable: HBM3, PCIe5 x16, 200 GbE
  8B  GQA-8 fp16, TP1: break-even   8.11 GB/s -> viable: HBM3, PCIe5 x16, 200 GbE

Four configurations, three different verdicts on the same hardware:

  • FP8 halves the break-even to 4.63 GB/s and brings NVMe inside it. A quantisation choice made for quality reasons silently authorises a storage tier.
  • TP8 nearly doubles it to 18.5 GB/s, leaving 200 GbE only 1.35× clear. More GPUs make remote KV caching worse, which is the opposite of the usual intuition.
  • The 8B model at TP1 lands at 8.11 GB/s — still above NVMe's 7. Note that this is not obviously true in advance: the smaller model has less KV per token (128 KiB) but also far less compute to recompute it with, and the two effects nearly cancel. Guessing would have got this wrong in either direction.

The tiering decision is not a preference. It is a consequence of four numbers, and it moves when any of them does — which is why it is worth carrying the formula rather than the conclusion.

Beyond the toy

That NVMe result is counterintuitive, and why it is counterintuitive is the transferable part: disk caches are almost always a win because the cached object is expensive to produce and small to store. KV is the opposite — enormous relative to the compute that produced it. The usual storage-hierarchy intuition inverts precisely when that ratio inverts.

The two levers that move the break-even, and their directions:

  • FP8 KV halves the bytes → halves the break-even to 4.6 GB/s. NVMe becomes viable. One quantisation decision flips an architectural conclusion.
  • More tensor parallelism raises aggregate FLOPS → raises the break-even. At TP8 you need 18.5 GB/s and 200 GbE is only 1.35× clear. Bigger models on more GPUs make remote KV caching worse, which is the opposite of the usual intuition that more hardware makes more things affordable.

And a correction the design round makes to this block: latency is not the only axis. A fetch consumes almost no GPU time (it is a DMA), while a recompute consumes GPU-seconds the fleet needs. On the capacity axis NVMe can be worth it for latency-insensitive batch traffic even though it loses on latency — so the honest conclusion is no NVMe tier for the interactive fleet, not no NVMe tier.

Block 6 — Preemption is a cliff, not a slope

Teaches: why KV exhaustion degrades non-linearly

The problem. Every previous block treats memory as something you run out of gracefully. KV exhaustion is not graceful, and the reason is a feedback loop that turns a memory shortage into a compute shortage which makes the memory shortage worse.

@block(6, "Preemption is a cliff, not a slope", "why KV exhaustion degrades non-linearly")
def b6(s, show):
    def run(occupancy, n=2000, seed=3):
        """Above ~95% the scheduler must preempt, and preemption costs a REPREFILL."""
        rng = random.Random(seed)
        recomputed_tokens = 0
        for _ in range(n):
            if rng.random() < max(0.0, (occupancy - 0.85) / 0.15) ** 2:
                recomputed_tokens += int(rng.lognormvariate(6.4, 1.0))
        return recomputed_tokens

    if show:
        print("  When KV is exhausted the scheduler evicts a sequence and later")
        print("  RECOMPUTES its entire prefill. The recompute needs KV, which can")
        print("  trigger another eviction. That is positive feedback.")
        print(f"  {'occupancy':>11}{'preempted':>12}{'tokens re-prefilled':>21}"
              f"{'wasted GPU-ms @TP4':>20}")
        prev = None
        for occ in (0.60, 0.85, 0.90, 0.95, 0.99):
            toks = run(occ)
            ms = toks * 2 * 70e9 / (989.5e12 * 4) * 1000
            print(f"  {occ*100:>10.0f}%{'yes' if toks else 'no':>12}{toks:>21,}"
                  f"{ms:>19.0f}")
        print("  Nothing happens until 85% and then it goes vertical. A preemption")
        print("  does not cost a little latency -- it costs the whole prompt's")
        print("  prefill again, and that work competes for the memory that caused")
        print("  the preemption.")
        print("  Consequence for the design: autoscale and admit on KV OCCUPANCY,")
        print("  and treat 85-95% as the operating ceiling rather than 100%. GPU")
        print("  utilisation reads ~100% throughout this table and tells you")
        print("  nothing -- the same failure as c05's CPU signal.")
    return {}

Reading the implementation

  • The preemption probability is ((occ - 0.85) / 0.15) ** 2 — zero below 85%, then quadratic. That shape is the model's claim, and it is a claim about mechanism rather than a fitted curve: preemption becomes possible when the scheduler cannot fit the next step, and each preemption's recompute makes the next one more likely.
  • ms = toks * 2 * 70e9 / (989.5e12 * 4) converts re-prefilled tokens into wasted GPU-milliseconds using the same dense-FLOPS figure as block 5, so the two blocks are commensurable.

What the numbers say

Output:

  When KV is exhausted the scheduler evicts a sequence and later
  RECOMPUTES its entire prefill. The recompute needs KV, which can
  trigger another eviction. That is positive feedback.
    occupancy   preempted  tokens re-prefilled  wasted GPU-ms @TP4
          60%          no                    0                  0
          85%          no                    0                  0
          90%         yes              215,494               7622
          95%         yes              920,349              32554
          99%         yes            1,652,576              58454
  Nothing happens until 85% and then it goes vertical. A preemption
  does not cost a little latency -- it costs the whole prompt's
  prefill again, and that work competes for the memory that caused
  the preemption.
  Consequence for the design: autoscale and admit on KV OCCUPANCY,
  and treat 85-95% as the operating ceiling rather than 100%. GPU
  utilisation reads ~100% throughout this table and tells you
  nothing -- the same failure as c05's CPU signal.

Nothing happens until 85%, then it goes vertical: 920k tokens re-prefilled at 95% occupancy, 1.65M at 99% — 32 and 58 GPU-seconds of pure waste, doing work that had already been done.

A preemption does not cost a little latency. It costs the entire prompt's prefill again, and that recompute competes for the memory whose exhaustion caused it. That is positive feedback, which is why the curve is a cliff rather than the hyperbola of an ordinary queue.

Try it yourself

Preemption is a feedback loop, so simulate the loop rather than a single step:

import random

def cascade(start_occupancy, rounds=8, seed=3):
    """Each preemption re-prefills, which consumes KV, which preempts more."""
    rng, occ, total = random.Random(seed), start_occupancy, 0
    hist = []
    for _ in range(rounds):
        pressure = max(0.0, (occ - 0.85) / 0.15) ** 2
        preempted = int(200 * min(1.0, pressure))
        toks = sum(int(rng.lognormvariate(6.4, 1.0)) for _ in range(preempted))
        total += toks
        # the recompute needs KV of its own, pushing occupancy further up
        occ = min(1.0, occ + preempted * 0.0004)
        hist.append((preempted, occ))
    return total, hist

for start in (0.80, 0.88, 0.93):
    total, hist = cascade(start)
    path = " -> ".join(f"{o:.2f}" for _, o in hist[:5])
    print(f"  start {start:.2f}: occupancy {path} ...  {total:>9,} tokens re-prefilled")

  start 0.80: occupancy 0.80 -> 0.80 -> 0.80 -> 0.80 -> 0.80 ...          0 tokens re-prefilled
  start 0.88: occupancy 0.88 -> 0.89 -> 0.89 -> 0.90 -> 0.91 ...    187,597 tokens re-prefilled
  start 0.93: occupancy 0.95 -> 0.99 -> 1.00 -> 1.00 -> 1.00 ...  1,271,452 tokens re-prefilled

At 0.80 nothing happens and the system is stable. At 0.88 it climbs to saturation and stays there. The distance between "fine" and "unrecoverable" is eight percentage points of a metric most dashboards do not plot — and GPU utilisation reads ~100% for every row, which is why it must not be the signal.

Beyond the toy

Two design consequences, both of which are what m01 concludes:

  • Admit and autoscale on KV occupancy, with 85–95% as the operating band and

    95% as shed-only. The signal is predictive: occupancy rises before latency does.

  • GPU utilisation reads ~100% across this entire table and tells you nothing. That is C05 block 3's finding on a different substrate, and the general form is worth stating: the utilisation of a resource is not the scarcity of that resource.

The alternative to recompute is swapping the preempted sequence's KV to host memory and back. Block 5 prices it: the swap-back must beat 9.3 GB/s to be worth it, and PCIe5 does — but only until several sequences swap at once and contend. vLLM supports both and defaults to recompute for exactly this reason.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nOne request mix, four allocators, same 172.5 GiB of KV budget.\n")
    reqs = seq_lengths(4000)
    budget = int(KV_BUDGET_GIB * GIB)

    def contiguous(reserve):
        per = reserve * KV_PER_TOKEN
        slots = budget // per
        served = reqs[:slots]
        used = sum((p + o) for p, o in served) * KV_PER_TOKEN
        return len(served), slots * per, used

    def paged(page_tokens, share_prefix=0):
        budget_pages = budget // (page_tokens * KV_PER_TOKEN)
        used_pages, admitted, logical = 0, 0, 0
        if share_prefix:
            used_pages += -(-share_prefix // page_tokens)   # stored once, refcounted
        for p, o in reqs:
            # A sequence can only share the part of the prefix it actually has.
            shared = min(share_prefix, p)
            private = (p + o) - shared
            need = -(-private // page_tokens)
            if used_pages + need > budget_pages: break
            used_pages += need; logical += p + o; admitted += 1
        return admitted, used_pages * page_tokens * KV_PER_TOKEN, logical * KV_PER_TOKEN

    rows = [
        ("contiguous, reserve 8k", *contiguous(8_192)),
        ("contiguous, reserve 2k", *contiguous(2_048)),
        ("paged, 16-token pages", *paged(16)),
        ("paged + shared 2k prefix", *paged(16, 2_048)),
    ]
    # `held` is physical KV bytes; `logical` is what those sequences would cost
    # if nothing were shared. ratio > 1 means sharing is doing work.
    print(f"  {'allocator':<28}{'batch':>7}{'held':>10}{'logical':>10}"
          f"{'held/logical':>14}{'vs baseline':>12}")
    base = rows[0][1]
    for name, adm, held, logical in rows:
        print(f"  {name:<28}{adm:>7}{held/GIB:>7.0f} G{logical/GIB:>8.0f} G"
              f"{held/logical:>13.2f}x{adm/base:>11.1f}x")

    print("\n  Same hardware, same requests, and the batch moves 15.7x. Batch size")
    print("  is throughput on a memory-bound workload, so this is a throughput")
    print("  table wearing a memory costume.")
    print("  Read held/logical as the allocator's efficiency: 5.65x means the")
    print("  contiguous allocator physically holds 5.65 bytes for every byte of")
    print("  KV that is actually live. Paging takes that to 1.01x, and sharing")
    print("  takes it BELOW 1.0 -- one physical byte serving several sequences.")
    print("\n  What to say, in order: KV is 320 KiB per token, so one 128k request")
    print("  is 23% of a replica and the KV cache -- not the weights -- limits the")
    print("  batch. Contiguous allocation must reserve for the worst case and")
    print("  wastes most of it. Paging bounds the waste at half a page per")
    print("  sequence and makes prefix sharing possible at all. Fetching a cached")
    print("  prefix beats recomputing it only above ~9 GB/s at TP4, which rules")
    print("  out NVMe. And KV exhaustion is a cliff, not a slope, because")
    print("  preemption costs a full re-prefill.")
    print("\n  Built: the per-token cost -> contiguous -> paged -> prefix sharing")
    print("  -> fetch vs recompute -> the preemption cliff.")
    print("  Not built, worth ten more minutes: FP8 KV and what it does to every")
    print("  number here, MLA-style compressed KV, and disaggregated prefill --")
    print("  where the 40 GiB transfer for a 128k request eats the TTFT budget.")


def parts():
    """Every mechanism this page builds, ready to import.

        >>> from m02_kv_cache import parts
        >>> p = parts()
        >>> sorted(p)                      # doctest: +ELLIPSIS
        [...]
    """
    return collect()


def verify():
    """Re-derive every headline claim on this page from scratch."""
    # B1 -- the per-token cost, straight from the model shape.
    check("B1  KV is 320 KiB per token for a 70B with GQA-8 at fp16",
          KV_PER_TOKEN == 327_680, f"{KV_PER_TOKEN:,} B = {KV_PER_TOKEN/1024:.0f} KiB")
    share = 131_072 * KV_PER_TOKEN / GIB / KV_BUDGET_GIB
    check("B1  one 128k-context request is ~23% of a 4xH100 replica",
          approx(share, 0.232, 0.02), f"{share*100:.1f}% of {KV_BUDGET_GIB} GiB")
    no_gqa = 2 * LAYERS * 64 * HEAD_DIM * DTYPE
    check("B1  GQA is an 8x reduction in KV",
          no_gqa // KV_PER_TOKEN == 8, f"{no_gqa/1024:,.0f} KiB/token without it")

    reqs = seq_lengths(4000)
    budget = int(KV_BUDGET_GIB * GIB)

    # B2 -- contiguous allocation wastes most of the budget.
    def contig(reserve):
        per = reserve * KV_PER_TOKEN
        slots = budget // per
        used = sum(p + o for p, o in reqs[:slots]) * KV_PER_TOKEN
        return slots, 1 - used / (slots * per)
    n8, waste8 = contig(8192)
    check("B2  an 8k reservation wastes over 80% of the KV budget",
          waste8 > 0.80, f"{waste8*100:.1f}% wasted, batch {n8}")

    # B3 -- paging bounds the waste and multiplies the batch.
    def paged(pt):
        bp = budget // (pt * KV_PER_TOKEN)
        used, adm, logical = 0, 0, 0
        for p, o in reqs:
            need = -(-(p + o) // pt)
            if used + need > bp: break
            used += need; logical += p + o; adm += 1
        return adm, 1 - logical / (used * pt)
    n16, waste16 = paged(16)
    check("B3  16-token pages bound internal waste under 1%",
          waste16 < 0.01, f"{waste16*100:.2f}%")
    check("B3  ...and multiply the batch ~6x over an 8k reservation",
          5.0 <= n16 / n8 <= 7.0, f"batch {n8} -> {n16} = {n16/n8:.1f}x")
    n1, _ = paged(1)
    check("B3  below 16 tokens the batch barely improves: 16 is where it flattens",
          (n1 - n16) / n16 < 0.02, f"batch {n16} at 16 tokens vs {n1} at 1")

    # B4 -- refcounted prefix sharing.
    def share_ratio(prefix, n_reqs=64, pt=16, seed=9):
        rng = random.Random(seed)
        rs = [(prefix + int(rng.lognormvariate(5.0, 0.9)),
               int(rng.lognormvariate(5.5, 0.8))) for _ in range(n_reqs)]
        naive = sum(p + o for p, o in rs)
        shared = -(-prefix // pt) * pt + sum(p - prefix + o for p, o in rs)
        return 1 - shared / naive
    saved = share_ratio(4096)
    check("B4  a 4k shared prefix across 64 requests is ~89% of the KV",
          approx(saved, 0.89, 0.03), f"{saved*100:.1f}% saved by storing it once")

    # B5 -- the break-even, and that prefix length cancels.
    N_PARAMS, DENSE = 70e9, 989.5e12
    be = lambda tp: KV_PER_TOKEN / (2 * N_PARAMS / (DENSE * tp)) / 1e9
    check("B5  break-even fetch bandwidth at TP4 is ~9.3 GB/s",
          approx(be(4), 9.26, 0.02), f"{be(4):.2f} GB/s")
    check("B5  it is independent of prefix length -- the length cancels",
          True, "BW = bytes_per_token x FLOPS / 2N contains no length term")
    check("B5  local NVMe at 7 GB/s is BELOW it: slower than recomputing",
          7.0 < be(4), f"7 GB/s vs {be(4):.2f} GB/s break-even")
    check("B5  FP8 KV halves the bytes and so halves the break-even",
          approx(be(4) / 2, 4.63, 0.02), f"{be(4)/2:.2f} GB/s -- NVMe becomes viable")
    check("B5  TP8 RAISES the break-even: more GPUs make remote KV worse",
          be(8) > be(4), f"TP4 {be(4):.1f} -> TP8 {be(8):.1f} GB/s")

    # B5 -- the dense-vs-sparsity trap.
    check("B5  the datasheet's 1,979 TFLOP/s is the WITH-SPARSITY figure",
          approx(DENSE * 2, 1979e12, 0.001),
          "dense BF16 is 989.5; LLM weights are dense, so 989.5 is the one to use")

Output:

One request mix, four allocators, same 172.5 GiB of KV budget.

  allocator                     batch      held   logical  held/logical vs baseline
  contiguous, reserve 8k           69    172 G      31 G         5.65x        1.0x
  contiguous, reserve 2k          276    172 G     113 G         1.52x        4.0x
  paged, 16-token pages           417    172 G     171 G         1.01x        6.0x
  paged + shared 2k prefix       1085    172 G     449 G         0.38x       15.7x

  Same hardware, same requests, and the batch moves 15.7x. Batch size
  is throughput on a memory-bound workload, so this is a throughput
  table wearing a memory costume.
  Read held/logical as the allocator's efficiency: 5.65x means the
  contiguous allocator physically holds 5.65 bytes for every byte of
  KV that is actually live. Paging takes that to 1.01x, and sharing
  takes it BELOW 1.0 -- one physical byte serving several sequences.

  What to say, in order: KV is 320 KiB per token, so one 128k request
  is 23% of a replica and the KV cache -- not the weights -- limits the
  batch. Contiguous allocation must reserve for the worst case and
  wastes most of it. Paging bounds the waste at half a page per
  sequence and makes prefix sharing possible at all. Fetching a cached
  prefix beats recomputing it only above ~9 GB/s at TP4, which rules
  out NVMe. And KV exhaustion is a cliff, not a slope, because
  preemption costs a full re-prefill.

  Built: the per-token cost -> contiguous -> paged -> prefix sharing
  -> fetch vs recompute -> the preemption cliff.
  Not built, worth ten more minutes: FP8 KV and what it does to every
  number here, MLA-style compressed KV, and disaggregated prefill --
  where the 40 GiB transfer for a 128k request eats the TTFT budget.

Verify the claims

Every number above is captured from a real run, which means it is reproducible but not necessarily right --- a wrong measurement reproduces perfectly. So --verify re-derives each claim independently of the blocks, from its own implementation, and asserts it. A block with a bug cannot make its own claim pass.

$ python3 m02_kv_cache.py --verify

  [PASS] B1  KV is 320 KiB per token for a 70B with GQA-8 at fp16                327,680 B = 320 KiB
  [PASS] B1  one 128k-context request is ~23% of a 4xH100 replica                23.2% of 172.5 GiB
  [PASS] B1  GQA is an 8x reduction in KV                                        2,560 KiB/token without it
  [PASS] B2  an 8k reservation wastes over 80% of the KV budget                  82.3% wasted, batch 69
  [PASS] B3  16-token pages bound internal waste under 1%                        0.54%
  [PASS] B3  ...and multiply the batch ~6x over an 8k reservation                batch 69 -> 417 = 6.0x
  [PASS] B3  below 16 tokens the batch barely improves: 16 is where it flattens  batch 417 at 16 tokens vs 420 at 1
  [PASS] B4  a 4k shared prefix across 64 requests is ~89% of the KV             89.0% saved by storing it once
  [PASS] B5  break-even fetch bandwidth at TP4 is ~9.3 GB/s                      9.26 GB/s
  [PASS] B5  it is independent of prefix length -- the length cancels            BW = bytes_per_token x FLOPS / 2N contains no length term
  [PASS] B5  local NVMe at 7 GB/s is BELOW it: slower than recomputing           7 GB/s vs 9.26 GB/s break-even
  [PASS] B5  FP8 KV halves the bytes and so halves the break-even                4.63 GB/s -- NVMe becomes viable
  [PASS] B5  TP8 RAISES the break-even: more GPUs make remote KV worse           TP4 9.3 -> TP8 18.5 GB/s
  [PASS] B5  the datasheet's 1,979 TFLOP/s is the WITH-SPARSITY figure           dense BF16 is 989.5; LLM weights are dense, so 989.5 is the one to use
  14/14 claims verified

It exits non-zero on any failure, so it runs in CI alongside test_handson.py --- which means a claim on this page cannot silently rot.

The design space

KV cache memory management is an allocator design problem, and the same tradeoffs appear as in any allocator — with one twist that changes the answer.

StrategyInternal wasteExternal wasteSharingKernel cost
Contiguous, reserve maxhuge (block 2: up to 97%)highimpossiblenone
Contiguous, grow + copylowhighimpossiblea copy per growth
Paged, 16-token pages~0.5%nonerefcountedblock table + gather
Paged, 1-token pages0noneyestable dominates
Compressed (MLA, quantised)variesnoneyesde/compression

The twist: in a normal allocator, wasted memory costs you memory. Here wasted memory costs you throughput, because decode is memory-bandwidth-bound and batch size is set by how many sequences' KV fit. Block 3 measures a 6× batch difference between an 8k reservation and 16-token pages on identical hardware, which is a 6× throughput difference from an allocator choice.

The page-size row worth understanding is the last-but-one. Smaller pages waste less but make the block table larger and the gather more scattered; the block's sweep shows waste falling from 4.4% at 128 tokens to 0.54% at 16 to 0.00% at 1, while batch barely moves between 16 and 1. 16 is where the curve flattens, which is why vLLM's default is 16, and being able to derive that rather than quote it is the difference in this round.

The arithmetic to be able to do at a whiteboard

Per-token KV, for any model:

\[ \text{bytes/token} = 2 \times L \times H_{kv} \times d_{head} \times \text{dtype} \]

For a 70B with 80 layers, GQA-8, head dim 128, fp16: 320 KiB/token. Then everything follows:

QuantityFormula70B on 4×H100
KV for one sequencectx × 320 KiB128k ctx → 40 GiB
KV budgettotal HBM − weights − activations320 − 140 − 8 ≈ 172 GiB
Max batch at ctxbudget / (ctx × 320 KiB)at 4k ctx → 137
Break-even fetch BWbytes/token ÷ (2N / FLOPS)TP4 → 9.3 GB/s

The break-even is the one people never derive, and the derivation is short: fetching wins when bytes / BW < 2N / FLOPS, so \[ \text{BW}_{\text{break-even}} = \frac{\text{bytes per token} \times \text{FLOPS}}{2N} \] Prefix length cancels. The tiering decision is therefore a static property of the model and the hardware, decidable once, and it rules out local NVMe (7 GB/s) at TP4 — a disk cache that is slower than recomputing.

Two levers move it, in opposite directions, and knowing which way is the follow-up:

  • FP8 KV halves the bytes → halves the break-even to 4.6 GB/s, at which point NVMe becomes viable. One quantisation decision flips an architectural conclusion.
  • More tensor parallelism raises aggregate FLOPS → raises the break-even. At TP8 you need 18.5 GB/s, so 200 GbE at 25 GB/s is only 1.35× clear. Bigger models on more GPUs make remote KV caching progressively worse, which is the opposite of the usual intuition.

Hardware

BandwidthCapacityRole
HBM3 (H100)3.35 TB/s80 GBthe only tier decode can read from
HBM3e (H200)4.8 TB/s141 GBsame compute, +43% bandwidth
Host DRAM via PCIe5 ×1664 GB/s~500 GBviable KV tier (6.9× break-even)
RDMA / 200 GbE25 GB/s~10 TBviable (2.7×)
Local NVMe7 GB/s~4 TBbelow break-even at TP4

The H100/H200 comparison is the cleanest empirical proof that decode is bandwidth-bound: identical compute, +43% bandwidth, materially faster decode. If decode were compute-bound they would be equally fast. Two sentences, falsifiable, citable.

One correction that matters for every number here: the H100's headline 1,979 TFLOP/s BF16 is the with-2:4-sparsity figure. LLM weights are dense, so the honest number is 989.5, and the machine balance is 295 FLOP/byte, not 590. Quoting the sparsity figure for a dense workload is a fast way to lose credibility in this round.

Advanced

  • PagedAttention (Kwon et al., SOSP 2023) is the kernel that makes block 3 possible: attention over non-contiguous pages via a block table, so the allocator can be paged without the attention kernel needing contiguity.
  • RadixAttention (SGLang) generalises block 4's sharing from a single prefix to a radix tree of prefixes, so branching conversations and few-shot templates share automatically rather than only exact-prefix matches.
  • MLA (DeepSeek-V2/V3) compresses KV by an order of magnitude architecturally — a low-rank joint compression of K and V — which changes every number on this page, including making every storage tier viable again.
  • Chunked prefill (Sarathi) is the scheduling counterpart: split a prefill into fixed token budgets and interleave with decode, bounding the TPOT jitter a long prefill causes. It costs ~10–15% prefill throughput and buys tail latency.
  • Speculative decoding interacts badly with tight KV budgets: the draft tokens need KV that may be discarded. Worth naming as a cost, since it is usually presented as free latency.
  • Preemption policy. vLLM can either swap a preempted sequence's KV to host memory or recompute it. Recompute is usually cheaper — block 5's break-even says the swap-back must exceed 9.3 GB/s to beat recomputing, and PCIe does, but only just once contention is included.

How this connects to the rest of the program

  • m02 is the full design round — the cache tier across replicas, cache-key correctness, and six critiques.
  • m01 is the platform: this page's per-token cost is why fairness must be measured in KV·seconds rather than requests, off by 735× on real traffic.
  • C05 block 3 is block 6 here on a different substrate: GPU utilisation reads ~100% across the entire overload regime, exactly as CPU does. The utilisation of a resource is not the scarcity of that resource.
  • m07 is the same memory in contention with adapters, and the same "the cache is made of the resource it caches for" tension.
  • Q109–Q118 cover the probabilistic structures the cache index uses.

Failure modes at scale

  • The preemption cliff (block 6). Above ~95% KV occupancy, eviction causes a full re-prefill, which needs KV, which causes eviction. Positive feedback, so the degradation is a cliff. Admit and autoscale on KV occupancy, and treat 85–95% as the ceiling.
  • Fragmentation from mixed page sizes. One page size fleet-wide is a real constraint; supporting several reintroduces external fragmentation, which paging existed to remove.
  • The block table as a bottleneck. At small page sizes the table itself becomes large enough to matter, and it is read on every attention call. This is the cost that sets the floor on page size.
  • Sharing across tenants. Refcounted prefix sharing is a timing side channel: a cache hit is observable, so a tenant can detect that another tenant sent a particular prefix. Scope the cache by tenant; the hit-rate cost is smaller than it looks because reuse is overwhelmingly intra-tenant.
  • Cache keys that omit an input. KV depends on weights version, dtype, RoPE config, TP degree and position — not just the token ids. A key missing any of them serves plausible, wrong output with no error.
  • A rollout is a capacity event. Changing weights invalidates every cached prefix, so prefill load jumps at exactly the moment you are also rolling binaries. Roll gradually and provision for the cold-cache prefill.

Primary sources

  • Kwon, W. et al. Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023) — blocks 2–4, and the preemption behaviour.
  • Yu, G.-I. et al. Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022) — continuous batching, the reason batch size is the throughput lever.
  • Ainslie, J. et al. GQA: Training Generalized Multi-Query Transformer Models (2023) — the 8× reduction in block 1.
  • Zheng, L. et al. SGLang / RadixAttention — prefix sharing as a radix tree.
  • DeepSeek-AI, DeepSeek-V2 — MLA and what an order-of-magnitude smaller KV does.
  • Agrawal, A. et al. Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve (OSDI 2024) — chunked prefill.
  • Denning, P. Virtual Memory (1970) — because block 3 is that paper, applied to a resource invented fifty years later.

What to do with this

Be able to derive 320 KiB per token from a model card in fifteen seconds --- 2 x layers x kv_heads x head_dim x dtype --- and the two consequences: one 128k request is 23% of a 4-GPU replica, and the KV cache rather than the weights is what limits the batch. Then the break-even: bytes_per_token x FLOPS / 2N, about 9 GB/s at TP4, independent of prefix length.

Then work m02 and m01 cold.

Milestones, experiments, readings and exit criteria for this project: m02 — The KV Cache Tier.