PagedAttention: Block-wise Attention Computation

HardLLMs & GenAI

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; entry i is the physical block index of the sequence's logical block i. 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 beyond context_len hold 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