E3.4 · LESSON 4 OF 6

Sharing prefixes

Allocate logical token blocks to physical KV-cache blocks and quantify internal waste and shared-prefix behavior.

THE IDEA

Sharing a common prefix

Many requests start with the same text, for example a long system prompt. Their cached keys and values for that prefix are identical, so full blocks of it can be stored once and referenced by every request. Each request owns the rest. Three 52-token requests that share a 32-token prefix need 2 + 3 × 2 = 8 blocks instead of 12.

identical prefix tokens32requests3own tokens each20

blocks of 16 tokens without sharing: 3 × ceil(52/16) = 12 blocks with sharing: 2 shared full block(s) + 2 + 2 + 2 own = 8 blocks (saved 4) Only FULL blocks of an identical prefix can be shared; the partly filled one differs by request.

Sharing is only safe when the cached state is genuinely identical: the same model and weights, the same token ids in that block, and the same positions. Text that merely looks the same in a different model is not the same cache.

Change the prefix length, the number of requests and their own text.

Predict first. Can unrelated models safely reuse a block only because the text looks identical?

Chapter context

Contiguous reservation can waste memory when sequence lengths differ or grow unpredictably. Paging separates a sequence's logical block order from the physical blocks storing its cache.

TRY IT YOURSELF

Part 1. Do it hands-on

Count blocks with and without sharing, then write the counting functions and the condition under which sharing is allowed.

identical prefix tokens32requests3own tokens each20

blocks without sharing (3 × 52 tokens) blocks with the 32-token prefix shared blocks saved

To do: Three requests each have 52 tokens (blocks of 16): a 32-token shared system prompt plus 20 tokens of their own. Without sharing, each needs ceil(52/16) = 4 blocks. Total blocks?
To do: With the shared prefix stored once (32 tokens = 2 full blocks) and each request holding its own remaining 20 tokens (2 blocks each), total blocks?
To do: Blocks saved by sharing?

Part 2. Do it in code

full_shared_blocks(prefix_len, block): the number of FULL blocks of an identical prefix that can be shared: prefix_len // block. (A partly filled last prefix block is followed by different tokens in each sequence, so it cannot be shared.)
blocks_without_sharing(totals, block): sum of blocks_needed(total) over the sequences.
blocks_with_sharing(prefix_len, totals, block): shared full blocks counted once plus each sequence's own blocks for its remaining tokens.
can_share(a, b): a and b are dicts with model, tokens (the token ids of the block) and start (position of the block). True only if all three are equal.

import math

def full_shared_blocks(prefix_len, block):
    pass

def blocks_without_sharing(totals, block):
    pass

def blocks_with_sharing(prefix_len, totals, block):
    pass

def can_share(a, b):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can unrelated models safely reuse a block only because the text looks identical?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For length T and block capacity P:

n_{blocks}=\lceil T/P\rceil,\quad slots=P\lceil T/P\rceil,\quad slack=slots-T.

Slack as a fraction of allocated slots is slack/slots. State the denominator when reporting waste percentages.

Worked example

A sequence has 33 tokens and blocks hold 16. It requires ceil(33/16)=3 blocks, allocating 48 token slots. Fifteen slots are unused, so internal slack is 15/48=31.25% of this allocation. It is not 31.25% of all GPU memory, and shared blocks change total ownership accounting.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import ceil,isclose
tokens,capacity=33,16
blocks=ceil(tokens/capacity)
slots=blocks*capacity
assert blocks == 3 and slots == 48
assert slots-tokens == 15
assert isclose((slots-tokens)/slots,.3125)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Paging improves allocation flexibility but does not make memory unlimited. Logical block order differs from physical layout. Internal slack and external fragmentation are different kinds of waste.