pagedattention vllm

**PagedAttention** is **the attention mechanism that manages KV cache using virtual memory techniques with fixed-size blocks (pages)** — eliminating memory fragmentation and enabling near-optimal memory utilization (90-95% vs 20-40% for naive allocation), allowing 2-4× larger batch sizes or longer contexts in LLM serving, forming the foundation of high-throughput inference systems like vLLM. **Memory Fragmentation Problem:** - **Naive Allocation**: pre-allocate contiguous memory for maximum sequence length; wastes memory for shorter sequences; example: allocate for 2048 tokens, use 100 tokens, waste 95% memory - **Fragmentation**: variable-length sequences create fragmentation; cannot pack sequences efficiently; memory utilization 20-40% typical; limits batch size and throughput - **Dynamic Growth**: sequences grow token-by-token during generation; hard to predict final length; over-allocation wastes memory; under-allocation requires reallocation - **Example**: 32 sequences, max length 2048, average length 200; naive allocation: 32×2048 = 65K tokens; actual usage: 32×200 = 6.4K tokens; 90% waste **PagedAttention Design:** - **Block-Based Storage**: divide KV cache into fixed-size blocks (pages); typical block size 16-64 tokens; allocate blocks on-demand as sequence grows - **Virtual Memory Mapping**: each sequence has virtual address space; maps to physical blocks; non-contiguous physical storage; transparent to attention computation - **Block Table**: maintain mapping from virtual blocks to physical blocks; similar to OS page table; enables efficient address translation - **On-Demand Allocation**: allocate blocks only when needed; deallocate when sequence completes; eliminates waste from over-allocation; achieves 90-95% utilization **Attention Computation:** - **Block-Wise Attention**: compute attention block-by-block; gather physical blocks for sequence; compute attention as if contiguous; mathematically equivalent to standard attention - **Address Translation**: translate virtual block IDs to physical block IDs; load physical blocks from memory; compute attention; store results - **Kernel Optimization**: custom CUDA kernels for block-wise attention; optimized memory access patterns; fused operations; achieves near-native performance - **Performance**: 5-10% overhead vs contiguous memory; acceptable trade-off for 2-4× memory efficiency; overhead decreases with larger blocks **Copy-on-Write Sharing:** - **Prefix Sharing**: sequences with common prefix (system prompt, few-shot examples) share physical blocks; only copy when sequences diverge - **Reference Counting**: track references to each block; deallocate when reference count reaches zero; enables safe sharing - **Divergence Handling**: when sequence modifies shared block, copy block before modification; update block table; other sequences unaffected - **Use Cases**: multi-turn conversations (share conversation history), beam search (share prefix), parallel sampling (share prompt); major memory savings **Memory Management:** - **Block Allocation**: maintain free list of available blocks; allocate from free list on-demand; deallocate to free list when sequence completes - **Eviction Policy**: when memory full, evict blocks from low-priority sequences; LRU or priority-based eviction; enables oversubscription - **Swapping**: swap blocks to CPU memory or disk; enables serving more sequences than GPU memory; trades latency for capacity - **Defragmentation**: not needed due to block-based design; major advantage over contiguous allocation; simplifies memory management **Performance Impact:** - **Memory Utilization**: 90-95% vs 20-40% for naive allocation; 2-4× improvement; directly enables larger batch sizes - **Batch Size**: 2-4× larger batches in same memory; improves throughput proportionally; critical for serving efficiency - **Throughput**: combined with continuous batching, achieves 10-20× throughput vs naive serving; major cost savings - **Latency**: minimal overhead (5-10%) from block-based access; acceptable for massive memory savings; user-imperceptible **Implementation Details:** - **Block Size Selection**: 16-64 tokens typical; smaller blocks reduce internal fragmentation but increase metadata overhead; 32 tokens balances trade-offs - **Metadata Overhead**: block table size = num_sequences × max_blocks_per_sequence × 4 bytes; typically <1% of total memory; negligible - **CUDA Kernels**: custom kernels for block-wise attention; optimized for coalesced memory access; fused operations; critical for performance - **Multi-GPU**: each GPU has independent block allocator; sequences can span GPUs with tensor parallelism; requires coordination **vLLM Integration:** - **Core Component**: PagedAttention is foundation of vLLM; enables high-throughput serving; production-tested at scale - **Continuous Batching**: PagedAttention enables efficient continuous batching; dynamic memory allocation critical for variable batch sizes - **Prefix Caching**: automatic prefix sharing; transparent to user; major performance improvement for repetitive prompts - **Monitoring**: vLLM provides memory utilization metrics; block allocation statistics; helps optimize configuration **Comparison with Alternatives:** - **vs Naive Allocation**: 2-4× better memory utilization; enables larger batches; major throughput improvement - **vs Reallocation**: no reallocation overhead; predictable performance; simpler implementation - **vs Compression**: orthogonal to compression; can combine PagedAttention with quantization; multiplicative benefits - **vs Offloading**: PagedAttention reduces need for offloading; but can combine for extreme oversubscription **Advanced Features:** - **Prefix Caching**: automatically cache and share common prefixes; reduces computation; improves throughput for repetitive prompts - **Sliding Window**: for models with sliding window attention (Mistral), only cache recent blocks; reduces memory; enables unbounded generation - **Multi-LoRA**: serve multiple LoRA adapters with shared base model KV cache; different adapters per sequence; enables multi-tenant serving - **Speculative Decoding**: PagedAttention compatible with speculative decoding; manage draft and target model caches efficiently **Use Cases:** - **High-Throughput Serving**: production API endpoints; chatbots; code completion; any high-request-rate application; 10-20× throughput improvement - **Long-Context Serving**: enables serving longer contexts by reducing memory waste; 2-4× longer contexts in same memory - **Multi-Tenant Serving**: efficient memory sharing across tenants; prefix caching for common prompts; cost-effective multi-tenancy - **Beam Search**: efficient memory management for multiple beams; prefix sharing reduces memory; enables larger beam widths **Best Practices:** - **Block Size**: use 32-64 tokens for most applications; smaller for memory-constrained scenarios; larger for simplicity - **Memory Reservation**: reserve 10-20% memory for incoming requests; prevents out-of-memory errors; maintains headroom - **Monitoring**: track block utilization, fragmentation, sharing efficiency; optimize based on metrics; critical for production - **Tuning**: adjust block size, reservation based on workload; profile and iterate; workload-dependent optimization PagedAttention is **the innovation that made high-throughput LLM serving practical** — by applying virtual memory techniques to KV cache management, it eliminates fragmentation and achieves near-optimal memory utilization, enabling the 10-20× throughput improvements that make large-scale LLM deployment economically viable.