Q2HardPart Q · AI Infra Hardware & Memory Scheduling
Contiguous KV Memory Defragmentation vs PagedAttention
Simulate greedy contiguous memory compaction overhead to understand why PagedAttention's non-contiguous paging eliminates external fragmentation.
⏱️ Time:
O(N log N)💾 Space:
O(N)🎯 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
def compact_contiguous_kv_slabs(blocks: list[tuple[int, int]], total_slots: int) -> dict:
# Compact fragmented allocated ranges [(start, length), ...] toward slot 0 via minimal relocate moves
sorted_blocks = sorted(blocks, key=lambda x: x[0])
moves = []
cursor = 0
for start, length in sorted_blocks:
if start != cursor:
moves.append((start, cursor, length))
cursor += length
largest_contiguous_free =
return {"moves": moves, "used_slots": cursor, "largest_free_contiguous": largest_contiguous_free}
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: What tiny waste still exists under PagedAttention?
Q2: Why not set KV block_size = 1 token to make internal waste zero?
💡
Core Mental Anchor / Mnemonic
Compaction pays copy stalls for contiguous regions; paging eliminates external fragmentation cleanly
📐 Mathematical Derivation & Core Formula
$$\text{FragRatio} = \frac{\sum_{\text{free}} b_j - \max_{\text{free}} b_j}{\text{TotalFree}}$$
Contiguous buffers suffer external fragmentation as variable-length sequences finish out of order, requiring stalling
cudaMemcpy compaction to recover one contiguous block. Paged virtual-to-physical block tables tolerate scattered physical frames with zero external fragmentation.🔄 Tensor Dimensions & Shape Flow
allocated spans [(start, len)] -> ordered relocation moves + largest contiguous free block
🛡️ Numerical Stability & Pitfalls Checklist
- Sort blocks ascending by start offset before compacting leftward so copies never overwrite unread spans
- Quantify relocation bytes moved to prove why paging beats stop-the-world compaction
- Keep block sizes near 16–32 tokens to balance internal waste against coalesced HBM loads
💻 Reference Code Implementation
def compact_contiguous_kv_slabs(blocks: list[tuple[int, int]], total_slots: int) -> dict:
# Compact fragmented allocated ranges [(start, length), ...] toward slot 0 via minimal relocate moves
sorted_blocks = sorted(blocks, key=lambda x: x[0])
moves = []
cursor = 0
for start, length in sorted_blocks:
if start != cursor:
moves.append((start, cursor, length))
cursor += length
largest_contiguous_free = total_slots - cursor
return {"moves": moves, "used_slots": cursor, "largest_free_contiguous": largest_contiguous_free}🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
res = compact_contiguous_kv_slabs([(2, 3), (7, 2), (12, 4)], total_slots=20)
assert res['used_slots'] == 9 and res['largest_free_contiguous'] == 11
assert len(res['moves']) == 3 and res['moves'][0] == (2, 0, 3)
print('Q2 PASS')🎯 Core Follow-up Inquiries & Reference Answers
Q1:What tiny waste still exists under PagedAttention?
Only internal fragmentation inside the single trailing block per request (on average half of one block, under 4% of VRAM).
Q2:Why not set KV block_size = 1 token to make internal waste zero?
Tiny 1-token blocks blow up Page Table indirection overhead and break coalesced warp memory loads inside FlashDecoding kernels.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.