Block-Allocated PagedAttention Triton Kernel

Build the block table and the kernel that reads it, so multi-tenant batches never fragment GPU memory.

Part 1 of 5

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.

Why it matters

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.

01Block table

Maps a sequence's logical blocks to physical blocks in one shared pool. Blocks need not sit together.

02Free list

Holds unused physical blocks in a stack. Any free block serves any sequence, which removes external fragmentation.

03Reference count

Counts how many sequences share a block. A block returns to the free list at zero.

04Triton program

One instance of a kernel. The grid sets how many run, and the compiler vectorises each over a block of data.

Part 2 of 5

Question

What exactly you must answer, and what to settle before you start.

2.1Question

Interviewer

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 askAnswer
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.
Part 3 of 5

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.

  1. Keep a free list

    Free blocks sit in a stack, so allocation and release take O(1).

  2. Add one token

    Allocate only when the last block fills. A partly used block costs at most one block of waste per sequence.

  3. Fork with reference counts

    Fork copies the table and raises each block's count. No tensor data moves.

  4. 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.

  5. Release by count

    Release lowers each count and frees blocks that reach zero.

  6. 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.

paged-blocks.tsTypeScriptCopy
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}
61 linesUTF-8TypeScript
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.

paged_scores_kernel.pyPythonCopy
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)
20 linesUTF-8Python
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.

Part 4 of 5

Q&A

What interviewers ask next. Answer out loud, then open.

4.1Interview questions

Why return false instead of evicting inside addToken?
Eviction needs policy: arrival order, priority, tenant. Keeping that in the scheduler leaves the allocator simple and testable.
Why does a block table slow attention?
Each read adds an indirection, and scattered blocks hurt cache locality. Reading per block limits the cost.
How does beam search fit?
Beams fork and die constantly. Copy-on-write makes a fork nearly free, and only the diverging last block gets copied.
Part 5 of 5

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.