E3.2 · LESSON 2 OF 6

Blocks and tables

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

THE IDEA

Blocks and a block table

Paged attention borrows an idea from operating-system memory: split the cache into small fixed-size blocks (say 16 tokens). A sequence gets blocks as it grows, wherever free ones are, and keeps a block table mapping its logical block 0, 1, 2… to physical block numbers. To find token i: logical block = i // 16, slot = i % 16, and the table gives the physical block.

token index20

logical block 0 → physical #7

abcdefghijklmnop

logical block 1 → physical #2

qrstuvwxyzABCDEF

logical block 2 → physical #5

GHIJKL

token 20: logical block 20 // 16 = 1, offset 20 % 16 = 4 table[1] = 2 → physical block #2, slot 4 The logical order comes from the table. The physical blocks (7, 2, 5) are not adjacent and not sorted.

Move the token index. The physical blocks 7, 2, 5 are scattered, but the sequence stays in order.

Predict first. Does physical block order determine token order?

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

Look up a token through a table, then write the lookup, a gather that follows the table, and token appending.

token index20

logical block 0 → physical #7

abcdefghijklmnop

logical block 1 → physical #2

qrstuvwxyzABCDEF

logical block 2 → physical #5

GHIJKL

blocks for 38 tokens physical block of token 20 slot inside it

To do: A sequence of 38 tokens, blocks of 16 tokens. How many blocks does it use?
To do: Its block table maps logical blocks 0, 1, 2 to physical blocks [7, 2, 5]. Token number 20 (counting from 0) lives in logical block 20 // 16 = 1. Which PHYSICAL block?
To do: At which slot inside that block (20 % 16)?

Part 2. Do it in code

blocks_needed(n_tokens, block): ceil(n_tokens / block).
locate(table, token_index, block): return (physical_block, offset) of the token at logical position token_index. IndexError (or ValueError) if the position is beyond the table.
gather(storage, table, n_tokens, block): storage maps a physical block number to a list of `block` slots. Return the first n_tokens tokens in LOGICAL order by following the table.
append_token(table, n_tokens, block, free_list): add one token. If the last block is full (or the table is empty), take the lowest free block number from free_list (remove it) and append it to the table. Return the updated (table, n_tokens + 1); raise MemoryError if no free block is available.

def blocks_needed(n_tokens, block):
    pass

def locate(table, token_index, block):
    pass

def gather(storage, table, n_tokens, block):
    pass

def append_token(table, n_tokens, block, free_list):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Does physical block order determine token order?

AYesBNo

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.