PagedAttention: Finding a Token's Block
Intermediate
The problem, from first principles
PagedAttention keeps a block table per sequence, mapping logical block numbers to physical memory blocks. Attention kernels use this table to find each cached token, so the blocks need not be contiguous in memory.
From theory to code
Implement block_table_lookup(block_table, token_idx, block_size), returning the physical block and offset of a token.
Constraints
- Logical block is
token_idx // block_size.
Hints
Hint 1
Divide the token index by the block size to get the logical block, look it up in the table, and take the remainder as the offset.
Keywords
research-paperssystemsservingkv-cache
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.