E3.3 · LESSON 3 OF 6

Internal fragmentation

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

THE IDEA

Internal fragmentation: the half-empty last block

A sequence rarely fills its last block exactly. A 33-token sequence in blocks of 16 needs ceil(33/16) = 3 blocks, which is 48 slots; 15 of them are empty. That slack is 15/48 = 31.25% of this allocation, not 31.25% of all GPU memory. On average the slack is about (block size − 1) / 2 slots per sequence.

tokens33block size16

33 tokens → 3 blocks × 16 = 48 slots slack = 15 slots = 31.25% of this allocation (orange) expected slack for random lengths ≈ (b − 1)/2 = 7.5 slots per sequence

Smaller blocks waste less per sequence but need more table entries and more bookkeeping. Paging cannot remove slack for arbitrary lengths; it makes it small and bounded. The percentage is of this allocation, not of all GPU memory.

Blue = tokens, orange = slack. Try a block size of 8 or 64.

Predict first. Can paging eliminate all internal slack for arbitrary sequence lengths?

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

Compute slack by hand, then write the functions and find the best block size for a set of lengths.

tokens33block size16

33 tokens → 3 blocks × 16 = 48 slots slack = 15 slots = 31.25% of this allocation (orange) expected slack for random lengths ≈ (b − 1)/2 = 7.5 slots per sequence

slack, 33 tokens, block 16 as a percent slack with blocks of 8

To do: 33 tokens in blocks of 16 need 3 blocks = 48 slots. Unused slots (slack)?
To do: Slack as a percentage of this allocation (2 decimals)?
To do: With blocks of 8 tokens instead, the slack for 33 tokens?

Part 2. Do it in code

allocated_slots(n_tokens, block): blocks_needed · block.
slack(n_tokens, block): allocated − used.
slack_fraction(n_tokens, block): slack / allocated (0 for an empty sequence).
average_slack(block): the mean slack over sequence lengths 1 … block (every possible last-block fill), computed by brute force.
total_slack(lengths, block): slack summed over several sequences.
best_block_size(lengths, candidates): the candidate with the least total slack (the smallest on ties).

import math

def allocated_slots(n_tokens, block):
    pass

def slack(n_tokens, block):
    pass

def slack_fraction(n_tokens, block):
    pass

def average_slack(block):
    pass

def total_slack(lengths, block):
    pass

def best_block_size(lengths, candidates):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Can paging eliminate all internal slack for arbitrary sequence lengths?

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.