Basics
The whole idea first, then the terms the rest of this page uses.
1.1Whole idea
Attention needs every key of a sequence, but paged storage scatters them across memory. Two parts solve it: a block manager that owns memory, and a kernel that follows each sequence's block table while it computes scores.
Build the block table and the kernel that reads it, so multi-tenant batches never fragment GPU memory.
1.2Key concepts
One idea per card, in plain words.
Maps a sequence's logical blocks to physical blocks in one shared pool. Blocks need not sit together.
Holds unused physical blocks in a stack. Any free block serves any sequence, which removes external fragmentation.
Counts how many sequences share a block. A block returns to the free list at zero.
One instance of a kernel. The grid sets how many run, and the compiler vectorises each over a block of data.
Question
What exactly you must answer, and what to settle before you start.
2.1Question
Implement the memory manager behind PagedAttention: add a token, fork a sequence for parallel sampling, release a finished one. Then sketch the GPU kernel that computes attention scores through the block table.
2.2Clarify first
Each answer removes a guess.
| You ask | Answer |
|---|---|
| Block size? | 16 tokens by default. Make it a constructor argument. |
| What if memory runs out? | addToken returns false. The scheduler decides whom to preempt; the allocator never decides policy. |
| Threads? | The scheduler calls it from one thread, between steps. |
Detailed answer
How it works, and how to build or explain it.
3.1Step by step
The mechanism, in the order you would explain it.
- Keep a free list
Free blocks sit in a stack, so allocation and release take O(1).
- Add one token
Allocate only when the last block fills. A partly used block costs at most one block of waste per sequence.
- Fork with reference counts
Fork copies the table and raises each block's count. No tensor data moves.
- Copy on write
Before writing to a shared last block, take a new one. A real engine also copies the tensor contents; this code tracks ownership.
- Release by count
Release lowers each count and frees blocks that reach zero.
- Read through the table
The kernel runs one program per logical block, loads the physical id from the table, computes the pool offset and takes dot products with the query.
3.2Code
Working code for the core of it.
Managing the KV cache in blocks
A sequence's final length is unknown, so reserving contiguous memory wastes most of it. Blocks work like virtual memory pages.
1/** PagedAttention's memory manager: fixed-size blocks, one table per sequence, copy-on-write forks. */2export class BlockManager {3 private free: number[];4 private refs: number[];5 private blockTokens: number;6 private seqs = new Map<string, { blocks: number[]; tokens: number }>();7 8 constructor(totalBlocks: number, blockTokens = 16) {9 this.free = Array.from({ length: totalBlocks }, (_, i) => totalBlocks - 1 - i);10 this.refs = new Array<number>(totalBlocks).fill(0);11 this.blockTokens = blockTokens;12 }13 14 get freeBlocks(): number {15 return this.free.length;16 }17 18 table(seq: string): number[] {19 return [...(this.seqs.get(seq)?.blocks ?? [])];20 }21 22 /** Reserves room for one more token. False means no free block: the scheduler must preempt. */23 addToken(seq: string): boolean {24 const s = this.seqs.get(seq) ?? { blocks: [], tokens: 0 };25 this.seqs.set(seq, s);26 const lastIsFull = s.tokens % this.blockTokens === 0;27 if (lastIsFull) {28 const block = this.free.pop();29 if (block === undefined) return false;30 this.refs[block] = 1;31 s.blocks.push(block);32 } else {33 const last = s.blocks[s.blocks.length - 1];34 if (this.refs[last] > 1) {35 // A forked sequence shares this block: copy before writing.36 const copy = this.free.pop();37 if (copy === undefined) return false;38 this.refs[last]--;39 this.refs[copy] = 1;40 s.blocks[s.blocks.length - 1] = copy;41 }42 }43 s.tokens++;44 return true;45 }46 47 /** Parallel sampling or beam search: the child shares every block until it writes. */48 fork(parent: string, child: string): void {49 const p = this.seqs.get(parent);50 if (!p) throw new Error(`unknown sequence ${parent}`);51 p.blocks.forEach((b) => this.refs[b]++);52 this.seqs.set(child, { blocks: [...p.blocks], tokens: p.tokens });53 }54 55 release(seq: string): void {56 for (const b of this.seqs.get(seq)?.blocks ?? []) {57 if (--this.refs[b] === 0) this.free.push(b);58 }59 this.seqs.delete(seq);60 }61}s.tokens % this.blockTokens === 0- A new block is needed only when the last one is full, so waste is under one block per sequence.
return false- No free block. The scheduler must preempt something, which is why this returns a value rather than throwing.
this.refs[last] > 1- Copy on write: forked sequences share blocks until one of them writes.
--this.refs[b] === 0- A shared block returns to the free list only when its last user finishes.
Tested by npm run test:modules.
Attention over paged memory
A Triton kernel that follows the block table rather than assuming contiguous memory.
1import triton2import triton.language as tl3 4 5@triton.jit6def paged_scores(q_ptr, keys_ptr, table_ptr, scores_ptr,7 BLOCK_TOKENS: tl.constexpr, HEAD_DIM: tl.constexpr):8 logical = tl.program_id(0) # one program per logical block9 physical = tl.load(table_ptr + logical) # follow the block table10 11 dims = tl.arange(0, HEAD_DIM)12 toks = tl.arange(0, BLOCK_TOKENS)13 q = tl.load(q_ptr + dims) # [HEAD_DIM]14 15 # Keys live in one big pool: [physical block, token, dim].16 offs = physical * BLOCK_TOKENS * HEAD_DIM + toks[:, None] * HEAD_DIM + dims[None, :]17 k = tl.load(keys_ptr + offs) # [BLOCK_TOKENS, HEAD_DIM]18 19 scores = tl.sum(k * q[None, :], axis=1) # dot product per token20 tl.store(scores_ptr + logical * BLOCK_TOKENS + toks, scores)tl.load(table_ptr + logical)- The indirection that paging adds.
physical * BLOCK_TOKENS * HEAD_DIM- Turns a block number into an offset in the pool.
Syntax-checked. The GPU libraries it needs don't run in our tests.
Q&A
What interviewers ask next. Answer out loud, then open.
4.1Interview questions
Why return false instead of evicting inside addToken?
Why does a block table slow attention?
How does beam search fit?
Extra depth
Edge cases, counterpoints and what to read next.
5.1Edge cases and counterpoints
Includes the strongest argument against this approach.
Show detailsHide details
- Zero fragmentation, precisely
- External fragmentation disappears. Internal waste stays, bounded at one block per sequence.
- Tensor contents
- A production copy must duplicate keys and values for every layer and head before the next step writes.
- Next step
- Add a hash per block and this allocator becomes a prefix cache.