Large language models (LLMs) face significant constraints due to GPU memory limitations, primarily because each request necessitates a key-value (KV) cache for token data. Traditional memory allocation reserves a large block based on the maximum sequence length, resulting in substantial unused memory and limiting the number of concurrent requests. Paged Attention addresses this issue by segmenting the KV cache into smaller, flexible pages that are allocated as needed, akin to virtual memory systems. This method enables multiple requests with identical starting prompts to share memory until their outputs diverge, enhancing memory efficiency and throughput with minimal overhead.
In our exploration, we simulate a basic KV cache allocator and implement Paged Attention using a block table and Copy-on-Write (CoW) for prefix sharing. We analyze memory utilization across varying batch sizes, revealing that traditional methods can waste significant GPU resources. For instance, a naive approach might reserve 1024 MB per request but only utilize 250 MB, leading to considerable inefficiencies. In contrast, Paged Attention's design allows for dynamic memory allocation, significantly improving overall performance and resource utilization.