PagedAttention: Block-wise Attention Computation
Problem statement
In large-scale inference for autoregressive models the key-value (KV) cache consumes a lot of memory, and pre-allocating a contiguous region per sequence up to the maximum length wastes much of it. Borrowing from virtual memory in operating systems, the KV cache can instead be managed in fixed-size blocks (pages) that need not be contiguous in physical memory.
Implement paged_attention(query, key_cache, value_cache, block_table, context_len), scaled dot-product attention where keys and values live in a paged layout.
query: array of shape(num_heads, head_dim), the query for a single token.key_cache: array of shape(num_physical_blocks, block_size, num_heads, head_dim), the physical pool of key blocks.value_cache: same shape, the physical pool of value blocks.block_table: list of ints; entryiis the physical block index of the sequence's logical blocki. Only the first $\lceil \text{context\_len} / \text{block\_size} \rceil$ entries are used.context_len: total number of valid KV tokens. The last logical block may be only partially filled; slots beyondcontext_lenhold garbage and must be ignored.
Reconstruct the keys and values by reading physical blocks in logical order, handle the partially filled last block, then compute scaled dot-product attention independently per head with scale $1/\sqrt{\text{head\_dim}}$ and a numerically stable softmax.
Return the output as an array of shape (num_heads, head_dim), rounded to 4 decimal places.
Example
Input:
query = [[1.0, 0.0]] # 1 head, head_dim = 2
# key_cache shape (2, 2, 1, 2):
# physical block 0: slot 0 = [1, 0], slot 1 = [1, 0]
# physical block 1: slot 0 = [1, 0], slot 1 = [0, 0] (unused)
# value_cache shape (2, 2, 1, 2):
# physical block 0: slot 0 = [1, 0], slot 1 = [0, 1]
# physical block 1: slot 0 = [0.5, 0.5], slot 1 = [0, 0] (unused)
block_table = [0, 1]; context_len = 3
Output:
[[0.5, 0.5]]
Reasoning: logical block 0 is physical block 0 (tokens 0 and 1), and logical block 1 is physical block 1, where only token 2 is valid because context_len = 3. All three keys are [1, 0], so the weights are uniform at $1/3$ and the output is $\frac{1}{3}([1, 0] + [0, 1] + [0.5, 0.5]) = [0.5, 0.5]$.
Show hint
How can a page-table style lookup turn the scattered physical blocks back into one ordered sequence of keys and values?
Relevant roles: LLM Engineer, ML Engineer, MLOps Engineer, AI Engineer and AI Architect.
Related free problems
- Tiled Attention Against the SRAM BudgetML CodingMedium