I5Medium★ LLM Serving Essential · vLLM CorePart I · Inference, Decoding & Quantization

PagedAttention KV Block Allocator & Mapping

⚡Flashcard Drill➔

Allocate non-contiguous fixed-size KV physical blocks on demand via block tables to eliminate external fragmentation.

⏱️ Time: O(新增 Token / block_size)
💾 Space: O(SeqCount * MaxBlocksPerSeq) 块表映射开销,内部碎片 < block_size / 序列
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
class PagedKVCacheAllocator:
"""PagedAttention fixed-size physical KV block allocator with virtual-to-physical mapping."""
def __init__(self, num_blocks: int, block_size: int):
self.block_size = block_size
self.free_blocks =
self.block_tables = {} # seq_id -> list of physical block ids
self.seq_lens = {} # seq_id -> active token count
def allocate_tokens(self, seq_id: str, num_new_tokens: int) -> list:
cur_len = self.seq_lens.get(seq_id, 0)
table = self.block_tables.setdefault(seq_id, [])
new_total = cur_len + num_new_tokens
needed_blocks =
while len(table) < needed_blocks:
if not self.free_blocks:
raise MemoryError("Out of physical KV cache blocks")
table.append(self.free_blocks.pop())
self.seq_lens[seq_id] = new_total
return list(table)
def free_sequence(self, seq_id: str) -> None:
table = self.block_tables.pop(seq_id, [])
self.seq_lens.pop(seq_id, None)
# Return physical blocks to free pool
self.free_blocks.extend(reversed(table))
def internal_waste_tokens(self) -> int:
waste = 0
for seq_id, table in self.block_tables.items():
waste += len(table) * self.block_size - self.seq_lens[seq_id]
return waste
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How does PagedAttention share prefix KV memory across parallel branches (n > 1 or Beam Search)?
Next: Continuous Batching Iteration-Level Scheduler →
💡

Core Mental Anchor / Mnemonic

Split logical KV into size-B pages, map to non-contiguous physical blocks, bound waste < B per request.

📐 Mathematical Derivation & Core Formula

PhysicalAddr(t)=BlockTable[⌊t/B⌋]⋅B+(t mod B)\text{PhysicalAddr}(t) = \mathrm{BlockTable}\left[\lfloor t / B \rfloor\right] \cdot B + (t \bmod B)
### Virtual-to-Physical Paging & Fragmentation Bound
Pre-allocating contiguous max-sequence buffers wastes large memory regions before tokens are generated and fragments free memory.
PagedAttention splits KV sequences into fixed blocks of BB tokens mapped via a per-request block_table:
PhysicalAddr(t)=BlockTable[⌊t/B⌋]⋅B+(t mod B)\text{PhysicalAddr}(t) = \mathrm{BlockTable}\left[\lfloor t / B \rfloor\right] \cdot B + (t \bmod B)
Non-contiguous blocks eliminate external fragmentation, and internal waste is strictly bounded under BB tokens per active sequence.

🔄 Tensor Dimensions & Shape Flow

seq_id + new_tokens -> needed_blocks = ceil(total / B) -> pop from free_blocks -> append to block_table[seq_id]

🛡️ Numerical Stability & Pitfalls Checklist

  • Check free block availability before committing partial pops so failed allocations never leak blocks.
  • Track reference counts on shared prefix blocks so Copy-on-Write triggers only when sequences diverge.

💻 Reference Code Implementation

class PagedKVCacheAllocator:
    """PagedAttention fixed-size physical KV block allocator with virtual-to-physical mapping."""
    def __init__(self, num_blocks: int, block_size: int):
        self.block_size = block_size
        self.free_blocks = list(range(num_blocks - 1, -1, -1))
        self.block_tables = {}  # seq_id -> list of physical block ids
        self.seq_lens = {}      # seq_id -> active token count

    def allocate_tokens(self, seq_id: str, num_new_tokens: int) -> list:
        cur_len = self.seq_lens.get(seq_id, 0)
        table = self.block_tables.setdefault(seq_id, [])
        new_total = cur_len + num_new_tokens
        needed_blocks = (new_total + self.block_size - 1) // self.block_size
        while len(table) < needed_blocks:
            if not self.free_blocks:
                raise MemoryError("Out of physical KV cache blocks")
            table.append(self.free_blocks.pop())
        self.seq_lens[seq_id] = new_total
        return list(table)

    def free_sequence(self, seq_id: str) -> None:
        table = self.block_tables.pop(seq_id, [])
        self.seq_lens.pop(seq_id, None)
        # Return physical blocks to free pool
        self.free_blocks.extend(reversed(table))

    def internal_waste_tokens(self) -> int:
        waste = 0
        for seq_id, table in self.block_tables.items():
            waste += len(table) * self.block_size - self.seq_lens[seq_id]
        return waste

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

alloc = PagedKVCacheAllocator(num_blocks=6, block_size=4)
t1 = alloc.allocate_tokens("req1", 5)  # needs ceil(5/4) = 2 blocks
t2 = alloc.allocate_tokens("req2", 4)  # needs 1 block
assert len(t1) == 2 and len(t2) == 1
assert len(alloc.free_blocks) == 3
# Internal waste bounded strictly by < block_size per sequence
assert alloc.internal_waste_tokens() == 3
alloc.free_sequence("req1")
assert len(alloc.free_blocks) == 5
print("✓ PagedAttention block allocator assertion passed")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:How does PagedAttention share prefix KV memory across parallel branches (n > 1 or Beam Search)?
Branches point their logical block tables to the same physical blocks with reference counts > 1; Copy-on-Write duplicates a block only when a branch writes a diverging token into a shared partially filled block.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Beam Search Decoding with Length PenaltyBack to Part I & All 105Next: Continuous Batching Iteration-Level Scheduler →