![\"\"](\"https:\/\/uplatz.com\/blog\/wp-content\/uploads\/2025\/10\/Architectures-of-Efficiency-A-Comprehensive-Analysis-of-KV-Cache-Optimization-for-Large-Language-Model-Inference-1024x576.jpg\")
<\/p>\n
bundle-course—cybersecurity–ethical-hacking-foundation By Uplatz<\/a><\/h3>\nThe Mechanism of Autoregressive Generation<\/b><\/h3>\n
Transformer-based LLMs generate text in an autoregressive, or sequential, manner. This process involves predicting the next token in a sequence based on all the tokens that have come before it.<\/span>1<\/span> The generation process is fundamentally iterative and can be divided into two distinct phases: the prefill phase and the decode (or generation) phase.<\/span>2<\/span><\/p>\nIn the <\/span>prefill phase<\/b>, the model processes the initial input prompt in its entirety. This operation is highly parallelizable, as the entire prompt sequence is known. The model computes the Query (Q), Key (K), and Value (V) vectors for every token in the prompt simultaneously. This phase leverages the massive parallelism of modern GPUs, performing large matrix-matrix multiplications to generate the probability distribution for the very first output token.<\/span>2<\/span> Concurrently, it computes and stores the K and V tensors for every token in the prompt, populating the initial state of the KV cache.<\/span><\/p>\nFollowing the prefill, the <\/span>decode phase<\/b> begins. The model generates one token at a time, appends it to the sequence of preceding tokens (the original prompt plus any previously generated tokens), and then uses this new, extended sequence as the input to predict the subsequent token.<\/span>5<\/span> This loop continues until a stopping condition is met, such as reaching a maximum sequence length or generating a designated end-of-sequence (EOS) token. The core of this process is the causal self-attention mechanism, which enforces the autoregressive property. Causal attention ensures that the prediction for a token at position $t$ can only depend on the information from tokens at positions $1$ to $t-1$, preventing the model from “looking ahead” into the future.<\/span>6<\/span> This sequential dependency is the defining characteristic of the decode phase and is the primary source of its performance challenges.<\/span><\/p>\n <\/p>\n
The Role of the KV Cache: From Quadratic to Linear Complexity<\/b><\/h3>\n
<\/p>\n
The naive implementation of the autoregressive decode phase is computationally prohibitive. At each step of generating a new token, the model would need to recompute the Key (K) and Value (V) tensors for every single preceding token in the sequence.<\/span>1<\/span> Since the sequence length grows with each generated token, the total number of computations grows quadratically with the sequence length, represented by a complexity of $O(N^2)$, where $N$ is the sequence length. For generating long sequences, this quadratic scaling makes inference untenably slow.<\/span>8<\/span><\/p>\nThe Key-Value (KV) cache is a simple yet profoundly effective optimization that addresses this computational redundancy. The core principle is to store, or “cache,” the K and V tensors in GPU memory as they are computed for each token.<\/span>7<\/span> During the generation of the next token, the model only needs to compute the Q vector for the newest token. It then performs the attention operation by comparing this new Q vector against the <\/span>entire history<\/span><\/i> of K and V vectors that have been progressively stored in the cache.<\/span>5<\/span> The newly computed K and V vectors for the current token are then appended to the cache for use in the next step.<\/span><\/p>\nBy eliminating the need to recompute K and V tensors for past tokens, the KV cache transforms the computational complexity of the decode phase from quadratic to linear, $O(N)$, with respect to the sequence length.<\/span>8<\/span> This optimization is fundamental to making real-time, interactive applications with LLMs feasible. The performance improvement is dramatic, with empirical measurements showing inference speedups of 4.5x to over 5x compared to generation without a KV cache.<\/span>1<\/span><\/p>\n <\/p>\n
The Memory Bottleneck: A Quantitative Analysis<\/b><\/h3>\n
<\/p>\n
While the KV cache is a crucial optimization for computation, it achieves this by trading compute for memory. This trade-off introduces a new and often more severe bottleneck: GPU memory consumption. The size of the KV cache grows linearly with both the sequence length and the number of requests being processed in a batch.<\/span>8<\/span> The total memory required for the cache can be calculated with the following formula <\/span>3<\/span>:<\/span><\/p>\n$$\\text{Cache Size} = 2 \\times n_{\\text{layers}} \\times n_{\\text{heads}} \\times d_{\\text{head}} \\times L_{\\text{seq}} \\times N_{\\text{batch}} \\times \\text{sizeof(datatype)}$$<\/span><\/p>\nWhere:<\/span><\/p>\n\n- The factor of 2 accounts for storing both Key and Value tensors.<\/span><\/li>\n
- $n_{\\text{layers}}$ is the number of decoder layers in the model.<\/span><\/li>\n
- $n_{\\text{heads}}$ is the number of attention heads per layer.<\/span><\/li>\n
- $d_{\\text{head}}$ is the dimension of each attention head’s K\/V vectors.<\/span><\/li>\n
- $L_{\\text{seq}}$ is the sequence length (prompt + generated tokens).<\/span><\/li>\n
- $N_{\\text{batch}}$ is the number of sequences in the batch.<\/span><\/li>\n
- $\\text{sizeof(datatype)}$ is the number of bytes per parameter (e.g., 2 for FP16\/BF16).<\/span><\/li>\n<\/ul>\n
Given the common identity that the model’s hidden dimension $d_{\\text{model}} = n_{\\text{heads}} \\times d_{\\text{head}}$, the formula can be simplified to <\/span>5<\/span>:<\/span><\/p>\n$$\\text{Cache Size} = 2 \\times n_{\\text{layers}} \\times d_{\\text{model}} \\times L_{\\text{seq}} \\times N_{\\text{batch}} \\times \\text{sizeof(datatype)}$$<\/span><\/p>\nThe scale of this memory consumption is staggering for modern LLMs. Consider a model like Llama3-70B, which has 80 layers and a hidden dimension of 8192.<\/span>11<\/span> For a single sequence with a context length of 4096 tokens using FP16 precision, the KV cache would require approximately:<\/span><\/p>\n$2 \\times 80 \\times 8192 \\times 4096 \\times 1 \\times 2 \\text{ bytes} \\approx 10.74 \\text{ GB}$<\/span><\/p>\nThis 10.7 GB of VRAM is required for just a single user request with a moderately long context. For applications involving very long contexts (e.g., 1 million tokens), the KV cache can grow to hundreds of gigabytes, far exceeding the memory required to store the model’s own weights and becoming the dominant memory consumer.<\/span>3<\/span> This immense memory footprint directly limits the maximum batch size and context length a system can support, thereby becoming the primary bottleneck for achieving high throughput and enabling long-context applications.<\/span>8<\/span><\/p>\nThe introduction of the KV cache fundamentally alters the performance characteristics of LLM inference. The prefill phase, characterized by large, parallel matrix-matrix multiplications, is typically <\/span>compute-bound<\/span><\/i>. Its performance is limited by the GPU’s raw floating-point operations per second (FLOPS). In contrast, the decode phase, which generates one token at a time, is dominated by matrix-vector operations (the new query vector against the large cached key matrix).<\/span>5<\/span> These operations have a low arithmetic intensity\u2014the ratio of arithmetic operations to memory operations is low. Consequently, the performance of the decode phase is not limited by the GPU’s computational power but rather by its memory bandwidth\u2014the speed at which it can read the entire, ever-growing KV cache from high-bandwidth memory (HBM) into the much faster on-chip SRAM for each and every generated token.<\/span>8<\/span> This critical distinction explains why the field of LLM inference optimization has become intensely focused on techniques that reduce the memory footprint and bandwidth consumption of the KV cache. An optimization that reduces the cache size directly translates to improved latency and higher potential throughput during the memory-bandwidth-bound decode phase.<\/span><\/p>\n <\/p>\n
Proactive Reduction: Architectural Modifications to the Attention Mechanism<\/b><\/h2>\n
<\/p>\n
Before exploring system-level optimizations that manage the KV cache post-creation, a crucial category of techniques involves modifying the Transformer architecture itself to generate a smaller cache from the outset. These are not post-hoc optimizations but fundamental design choices made during a model’s conception and training. The evolution from Multi-Head Attention (MHA) to Multi-Query Attention (MQA) and finally to Grouped-Query Attention (GQA) represents a maturing understanding of the attention mechanism’s inherent redundancies. This progression provides a principled way to prune these redundancies, trading a degree of representational capacity for significant gains in memory efficiency and inference speed.<\/span><\/p>\n <\/p>\n
Multi-Query Attention (MQA): The Radical Reduction<\/b><\/h3>\n
<\/p>\n
Standard Multi-Head Attention (MHA), as introduced in the original Transformer paper, is designed to allow the model to jointly attend to information from different representation subspaces at different positions.<\/span>18<\/span> In this design, each of the $H$ attention heads has its own independent set of weight matrices to project the input into Query, Key, and Value vectors. This means that for each layer, $H$ distinct sets of K and V vectors are generated and stored in the KV cache.<\/span><\/p>\nMulti-Query Attention (MQA) proposes a radical simplification of this paradigm. In MQA, all $H$ query heads share a <\/span>single<\/span><\/i> Key and Value head projection.<\/span>19<\/span> While each query head still has its own unique Q projection, allowing it to learn to focus on different aspects of the input, they all access the same, shared context as represented by the single K and V projection.<\/span><\/p>\nThe impact of this change on the KV cache is dramatic. Instead of storing $H$ sets of K\/V vectors per layer, the model only needs to store one. This reduces the size of the KV cache, and consequently the memory bandwidth required to read it during the decode phase, by a factor of $H$.<\/span>21<\/span> For a model with 96 attention heads, this represents a 96x reduction in the cache’s contribution from that layer. This substantial saving allows for much larger batch sizes or longer context windows on the same hardware. Models incorporating MQA, such as Falcon and older versions of PaLM, are typically trained with this architecture from the beginning.<\/span>21<\/span> It is also possible to adapt a pre-trained MHA model to use MQA through a process called “uptraining,” but this is computationally expensive, requiring approximately 5% of the original pre-training compute budget.<\/span>20<\/span><\/p>\n <\/p>\n
Grouped-Query Attention (GQA): The Balanced Compromise<\/b><\/h3>\n
<\/p>\n
While MQA offers maximal inference efficiency, its aggressive parameter sharing can come at a cost to model quality. The representational capacity of the attention layer is diminished, as the diversity of learned K\/V projections is lost. Empirical studies have shown that MQA can lead to a noticeable degradation in performance on downstream tasks compared to an equivalent MHA model.<\/span>20<\/span><\/p>\nGrouped-Query Attention (GQA) was introduced as an elegant solution to this trade-off, providing a tunable interpolation between the extremes of MHA and MQA.<\/span>19<\/span> In GQA, the $H$ query heads are divided into $G$ groups, where each group of $H\/G$ query heads shares a single Key and Value head projection.<\/span>25<\/span><\/p>\nThis formulation provides a spectrum of architectural choices:<\/span><\/p>\n\n- If the number of groups equals the number of query heads ($G=H$), each query head is in its own group, effectively making each head independent. This is identical to <\/span>MHA<\/b>.<\/span><\/li>\n
- If there is only one group ($G=1$), all query heads share a single K\/V head. This is identical to <\/span>MQA<\/b>.<\/span><\/li>\n<\/ul>\n
By choosing an intermediate number of groups (e.g., $1 < G < H$), model designers can finely tune the balance between memory efficiency and model quality.<\/span>19<\/span> GQA recognizes that complete independence of heads (MHA) is often wasteful and over-parameterized, while complete sharing (MQA) can be too restrictive. The introduction of groups provides a “knob” to control the degree of parameter sharing, allowing for a more optimal trade-off. Due to this favorable balance, GQA has become the de facto standard for high-performance LLMs, including Llama 3, Mixtral, and Gemini, as it captures most of the speed and memory benefits of MQA while maintaining quality that is nearly indistinguishable from MHA.<\/span>7<\/span><\/p>\n <\/p>\n
Performance vs. Quality Trade-offs<\/b><\/h3>\n
<\/p>\n
The decision to use MHA, GQA, or MQA involves a direct trade-off between the model’s representational power and its inference efficiency.<\/span><\/p>\n\n- The Cost of Sharing:<\/b> The core function of multiple heads in MHA is to allow the model to capture diverse linguistic patterns and relationships simultaneously.<\/span>18<\/span> One head might focus on syntactic dependencies, another on semantic relationships, and a third on co-reference. Forcing multiple query heads to share a single K\/V projection, as in MQA, constrains this ability and can reduce the model’s overall capacity to understand complex text.<\/span>22<\/span><\/li>\n
- Empirical Evidence:<\/b> Research has consistently demonstrated that GQA represents a Pareto improvement over the binary choice between MHA and MQA.<\/span>29<\/span> The original GQA paper showed that a T5 model uptrained with GQA using a moderate number of groups achieved quality nearly identical to the original MHA model, while being almost as fast as the MQA variant.<\/span>20<\/span> Conversely, the MQA variant showed a clear drop in quality. This suggests that much of the information encoded in the multiple K\/V projections of MHA is redundant, and GQA provides a structured way to eliminate this redundancy without harming performance.<\/span><\/li>\n
- Advanced Grouping Strategies:<\/b> The success of GQA has spurred further research into more intelligent grouping methods. Standard GQA typically groups adjacent query heads. However, recent work on Quality and Capacity-Aware Grouped Query Attention (QCQA) proposes using evolutionary algorithms to form non-uniform groups based on the observed behavior and similarity of query heads during training. This approach claims to achieve a significantly better accuracy-memory trade-off than standard GQA by grouping heads that are functionally similar, even if they are not adjacent in the architecture.<\/span>31<\/span><\/li>\n<\/ul>\n
This architectural evolution from MHA to GQA is not merely an inference optimization; it reflects a deeper understanding of the Transformer architecture itself. It suggests that the original MHA design was likely over-parameterized for many tasks. GQA offers a more parameter-efficient architecture that is cheaper to train and faster at inference. This foundational improvement has become a baseline assumption for nearly all subsequent system-level optimizations. Techniques like PagedAttention and quantization benefit immensely from GQA, as it provides a smaller, more manageable KV cache to work with from the very beginning.<\/span>32<\/span><\/p>\n <\/p>\n
The Memory Management Revolution: PagedAttention and Non-Contiguous Caching<\/b><\/h2>\n
<\/p>\n
While architectural modifications like GQA reduce the intrinsic size of the KV cache, they do not address the systemic inefficiencies of how that cache is managed in memory. The development of PagedAttention by the vLLM project represents a fundamental shift in the software architecture of LLM serving. By abandoning the rigid, contiguous memory model of traditional deep learning frameworks and adopting principles from classical operating systems, PagedAttention solves the critical problem of memory fragmentation, unlocking dramatic improvements in throughput and memory utilization.<\/span><\/p>\n <\/p>\n
The Fragmentation Problem in Contiguous Caching<\/b><\/h3>\n
<\/p>\n
LLM serving systems that predate vLLM, such as NVIDIA’s FasterTransformer and Orca, managed the KV cache by allocating a single, large, contiguous block of GPU memory for each incoming request.<\/span>33<\/span> This seemingly straightforward approach is plagued by severe inefficiencies due to the dynamic and unpredictable nature of text generation.<\/span><\/p>\n\n- Unpredictable Sequence Length:<\/b> A core challenge is that the final output length of any given request is unknown at the outset. To avoid costly memory reallocations during generation, systems were forced to be pessimistic and pre-allocate a memory block large enough to accommodate the maximum possible context length supported by the model (e.g., 2048, 4096, or even 32,000 tokens).<\/span>34<\/span><\/li>\n
- Internal Fragmentation:<\/b> In practice, most sequences are much shorter than the maximum possible length. If a system reserves memory for 32,000 tokens but a specific request only generates 1,000 tokens, the memory corresponding to the remaining 31,000 tokens is allocated but unused. This wasted space within an allocated block is known as <\/span>internal fragmentation<\/b>. This form of waste can be substantial, often consuming the majority of the allocated memory.<\/span>35<\/span><\/li>\n
- External Fragmentation:<\/b> As requests of varying sizes are processed and their memory is subsequently freed, the GPU’s memory space becomes a patchwork of used blocks and small, scattered, unusable free gaps. Even if the total amount of free memory is sufficient to handle a new request, the system may be unable to find a <\/span>contiguous<\/span><\/i> block large enough to satisfy the allocation. This is known as <\/span>external fragmentation<\/b>. It leads to a state where the system has ample free memory in total but cannot use it effectively.<\/span>35<\/span><\/li>\n<\/ul>\n
The combined effect of internal and external fragmentation is catastrophic for system efficiency. It leads to massive memory waste\u2014in some cases, up to 96% of the allocated KV cache memory is left unused.<\/span>38<\/span> This wasted memory severely constrains the number of requests that can be processed concurrently in a batch, crippling overall system throughput and leading to poor GPU utilization.<\/span>33<\/span><\/p>\n <\/p>\n
The PagedAttention Paradigm: A Virtual Memory Analogy<\/b><\/h3>\n
<\/p>\n
PagedAttention solves the fragmentation problem by drawing direct inspiration from the virtual memory and paging techniques that have been a cornerstone of modern operating systems for decades.<\/span>33<\/span> The central innovation is to decouple the <\/span>logical<\/span><\/i> organization of a sequence’s KV cache from its <\/span>physical<\/span><\/i> storage in GPU memory.<\/span><\/p>\nThe mechanism works as follows:<\/span><\/p>\n\n- Partitioning into Blocks (Pages):<\/b> Instead of a single monolithic block, the KV cache for each sequence is partitioned into multiple small, fixed-size blocks. These blocks are analogous to “pages” in an OS memory management system.<\/span>38<\/span><\/li>\n
- Non-Contiguous Physical Storage:<\/b> These physical blocks can be stored anywhere in the GPU’s memory; they are not required to be physically contiguous. This flexibility is key to eliminating external fragmentation.<\/span>35<\/span><\/li>\n
- The Block Table (Page Table):<\/b> For each sequence, the system maintains a data structure called a “block table,” which is analogous to an OS page table. This table serves as an indirection layer, mapping the logical indices of the tokens in a sequence to the physical memory addresses of the blocks where their corresponding K and V vectors are stored.<\/span>35<\/span><\/li>\n
- On-Demand Allocation:<\/b> As new tokens are generated during the decode phase, the memory manager allocates new blocks on demand, one at a time, and simply updates the block table to point to the new physical block. This “pay-as-you-go” model eliminates the need for large, pessimistic pre-allocations.<\/span>33<\/span><\/li>\n<\/ol>\n
This non-contiguous memory layout is incompatible with standard attention kernels, which assume that tensors are stored in a single, contiguous memory block. Therefore, a critical component of PagedAttention is the use of custom-written GPU kernels. These specialized kernels are designed to first read the block table for a given sequence, gather the scattered K and V vectors from their disparate physical locations, and then perform the attention computation.<\/span>36<\/span><\/p>\n <\/p>\n
Benefits of Paging<\/b><\/h3>\n
<\/p>\n
The adoption of a paged memory model provides a host of profound benefits that collectively redefine the performance ceiling for LLM serving.<\/span><\/p>\n\n- Near-Optimal Memory Utilization:<\/b> PagedAttention almost completely eliminates memory fragmentation. Since blocks are allocated on demand, internal fragmentation is confined to only the very last block of a sequence, resulting in an average memory waste of less than 4%.<\/span>33<\/span> External fragmentation is entirely eliminated because all blocks are of a uniform, interchangeable size.<\/span>33<\/span><\/li>\n
- Dramatically Higher Throughput:<\/b> The efficiency gains in memory utilization translate directly to higher throughput. By wasting significantly less memory per request, the system can accommodate much larger batch sizes, leading to better GPU utilization and a 2-4x increase in serving throughput compared to systems using contiguous allocation.<\/span>2<\/span><\/li>\n
- Efficient Memory Sharing with Copy-on-Write:<\/b> The block-based architecture enables highly efficient and granular memory sharing. This is particularly valuable for complex decoding strategies like parallel sampling or beam search, where multiple candidate sequences are generated from a common prompt. With PagedAttention, the block tables for all candidate sequences can simply point to the same set of physical blocks containing the KV cache for the shared prompt. As each sequence is extended with a new, unique token, only a new block needs to be allocated for that specific sequence. This is managed through a reference counting system and a <\/span>Copy-on-Write<\/b> mechanism, which ensures that shared blocks are not modified, and new blocks are created only when a sequence diverges. This avoids redundant storage and computation for the shared prefix, significantly reducing the memory overhead of these advanced sampling methods.<\/span>38<\/span><\/li>\n<\/ul>\n
<\/p>\n
Implementation Overheads and Alternatives (vAttention)<\/b><\/h3>\n
<\/p>\n
Despite its transformative benefits, the PagedAttention model introduces its own set of challenges, primarily related to software complexity and performance overhead.<\/span><\/p>\n\n- The Burden of Custom Kernels:<\/b> The reliance on custom GPU kernels is the most significant drawback. Writing, debugging, and optimizing high-performance CUDA code is a specialized and difficult task.<\/span>36<\/span> This creates a significant engineering burden and can lead to a lag in adopting new, highly optimized attention algorithms from the research community. For example, when a new algorithm like FlashAttention-3 is released, it cannot be used in a PagedAttention-based system until it has been manually ported to support the non-contiguous memory layout, a non-trivial undertaking.<\/span>42<\/span><\/li>\n
- Performance Overhead:<\/b> The additional logic required within the custom kernel to read the block table and de-reference pointers to gather scattered data introduces a performance overhead. Benchmarks have shown that paged attention kernels can be 10-40% slower than their vanilla, contiguous-memory counterparts for the same attention computation, due to this extra memory indirection.<\/span>
In the <\/span>prefill phase<\/b>, the model processes the initial input prompt in its entirety. This operation is highly parallelizable, as the entire prompt sequence is known. The model computes the Query (Q), Key (K), and Value (V) vectors for every token in the prompt simultaneously. This phase leverages the massive parallelism of modern GPUs, performing large matrix-matrix multiplications to generate the probability distribution for the very first output token.<\/span>2<\/span> Concurrently, it computes and stores the K and V tensors for every token in the prompt, populating the initial state of the KV cache.<\/span><\/p>\n Following the prefill, the <\/span>decode phase<\/b> begins. The model generates one token at a time, appends it to the sequence of preceding tokens (the original prompt plus any previously generated tokens), and then uses this new, extended sequence as the input to predict the subsequent token.<\/span>5<\/span> This loop continues until a stopping condition is met, such as reaching a maximum sequence length or generating a designated end-of-sequence (EOS) token. The core of this process is the causal self-attention mechanism, which enforces the autoregressive property. Causal attention ensures that the prediction for a token at position $t$ can only depend on the information from tokens at positions $1$ to $t-1$, preventing the model from “looking ahead” into the future.<\/span>6<\/span> This sequential dependency is the defining characteristic of the decode phase and is the primary source of its performance challenges.<\/span><\/p>\n <\/p>\n <\/p>\n The naive implementation of the autoregressive decode phase is computationally prohibitive. At each step of generating a new token, the model would need to recompute the Key (K) and Value (V) tensors for every single preceding token in the sequence.<\/span>1<\/span> Since the sequence length grows with each generated token, the total number of computations grows quadratically with the sequence length, represented by a complexity of $O(N^2)$, where $N$ is the sequence length. For generating long sequences, this quadratic scaling makes inference untenably slow.<\/span>8<\/span><\/p>\n The Key-Value (KV) cache is a simple yet profoundly effective optimization that addresses this computational redundancy. The core principle is to store, or “cache,” the K and V tensors in GPU memory as they are computed for each token.<\/span>7<\/span> During the generation of the next token, the model only needs to compute the Q vector for the newest token. It then performs the attention operation by comparing this new Q vector against the <\/span>entire history<\/span><\/i> of K and V vectors that have been progressively stored in the cache.<\/span>5<\/span> The newly computed K and V vectors for the current token are then appended to the cache for use in the next step.<\/span><\/p>\n By eliminating the need to recompute K and V tensors for past tokens, the KV cache transforms the computational complexity of the decode phase from quadratic to linear, $O(N)$, with respect to the sequence length.<\/span>8<\/span> This optimization is fundamental to making real-time, interactive applications with LLMs feasible. The performance improvement is dramatic, with empirical measurements showing inference speedups of 4.5x to over 5x compared to generation without a KV cache.<\/span>1<\/span><\/p>\n <\/p>\n <\/p>\n While the KV cache is a crucial optimization for computation, it achieves this by trading compute for memory. This trade-off introduces a new and often more severe bottleneck: GPU memory consumption. The size of the KV cache grows linearly with both the sequence length and the number of requests being processed in a batch.<\/span>8<\/span> The total memory required for the cache can be calculated with the following formula <\/span>3<\/span>:<\/span><\/p>\n $$\\text{Cache Size} = 2 \\times n_{\\text{layers}} \\times n_{\\text{heads}} \\times d_{\\text{head}} \\times L_{\\text{seq}} \\times N_{\\text{batch}} \\times \\text{sizeof(datatype)}$$<\/span><\/p>\n Where:<\/span><\/p>\n Given the common identity that the model’s hidden dimension $d_{\\text{model}} = n_{\\text{heads}} \\times d_{\\text{head}}$, the formula can be simplified to <\/span>5<\/span>:<\/span><\/p>\n $$\\text{Cache Size} = 2 \\times n_{\\text{layers}} \\times d_{\\text{model}} \\times L_{\\text{seq}} \\times N_{\\text{batch}} \\times \\text{sizeof(datatype)}$$<\/span><\/p>\n The scale of this memory consumption is staggering for modern LLMs. Consider a model like Llama3-70B, which has 80 layers and a hidden dimension of 8192.<\/span>11<\/span> For a single sequence with a context length of 4096 tokens using FP16 precision, the KV cache would require approximately:<\/span><\/p>\n $2 \\times 80 \\times 8192 \\times 4096 \\times 1 \\times 2 \\text{ bytes} \\approx 10.74 \\text{ GB}$<\/span><\/p>\n This 10.7 GB of VRAM is required for just a single user request with a moderately long context. For applications involving very long contexts (e.g., 1 million tokens), the KV cache can grow to hundreds of gigabytes, far exceeding the memory required to store the model’s own weights and becoming the dominant memory consumer.<\/span>3<\/span> This immense memory footprint directly limits the maximum batch size and context length a system can support, thereby becoming the primary bottleneck for achieving high throughput and enabling long-context applications.<\/span>8<\/span><\/p>\n The introduction of the KV cache fundamentally alters the performance characteristics of LLM inference. The prefill phase, characterized by large, parallel matrix-matrix multiplications, is typically <\/span>compute-bound<\/span><\/i>. Its performance is limited by the GPU’s raw floating-point operations per second (FLOPS). In contrast, the decode phase, which generates one token at a time, is dominated by matrix-vector operations (the new query vector against the large cached key matrix).<\/span>5<\/span> These operations have a low arithmetic intensity\u2014the ratio of arithmetic operations to memory operations is low. Consequently, the performance of the decode phase is not limited by the GPU’s computational power but rather by its memory bandwidth\u2014the speed at which it can read the entire, ever-growing KV cache from high-bandwidth memory (HBM) into the much faster on-chip SRAM for each and every generated token.<\/span>8<\/span> This critical distinction explains why the field of LLM inference optimization has become intensely focused on techniques that reduce the memory footprint and bandwidth consumption of the KV cache. An optimization that reduces the cache size directly translates to improved latency and higher potential throughput during the memory-bandwidth-bound decode phase.<\/span><\/p>\n <\/p>\n <\/p>\n Before exploring system-level optimizations that manage the KV cache post-creation, a crucial category of techniques involves modifying the Transformer architecture itself to generate a smaller cache from the outset. These are not post-hoc optimizations but fundamental design choices made during a model’s conception and training. The evolution from Multi-Head Attention (MHA) to Multi-Query Attention (MQA) and finally to Grouped-Query Attention (GQA) represents a maturing understanding of the attention mechanism’s inherent redundancies. This progression provides a principled way to prune these redundancies, trading a degree of representational capacity for significant gains in memory efficiency and inference speed.<\/span><\/p>\n <\/p>\n <\/p>\n Standard Multi-Head Attention (MHA), as introduced in the original Transformer paper, is designed to allow the model to jointly attend to information from different representation subspaces at different positions.<\/span>18<\/span> In this design, each of the $H$ attention heads has its own independent set of weight matrices to project the input into Query, Key, and Value vectors. This means that for each layer, $H$ distinct sets of K and V vectors are generated and stored in the KV cache.<\/span><\/p>\n Multi-Query Attention (MQA) proposes a radical simplification of this paradigm. In MQA, all $H$ query heads share a <\/span>single<\/span><\/i> Key and Value head projection.<\/span>19<\/span> While each query head still has its own unique Q projection, allowing it to learn to focus on different aspects of the input, they all access the same, shared context as represented by the single K and V projection.<\/span><\/p>\n The impact of this change on the KV cache is dramatic. Instead of storing $H$ sets of K\/V vectors per layer, the model only needs to store one. This reduces the size of the KV cache, and consequently the memory bandwidth required to read it during the decode phase, by a factor of $H$.<\/span>21<\/span> For a model with 96 attention heads, this represents a 96x reduction in the cache’s contribution from that layer. This substantial saving allows for much larger batch sizes or longer context windows on the same hardware. Models incorporating MQA, such as Falcon and older versions of PaLM, are typically trained with this architecture from the beginning.<\/span>21<\/span> It is also possible to adapt a pre-trained MHA model to use MQA through a process called “uptraining,” but this is computationally expensive, requiring approximately 5% of the original pre-training compute budget.<\/span>20<\/span><\/p>\n <\/p>\n <\/p>\n While MQA offers maximal inference efficiency, its aggressive parameter sharing can come at a cost to model quality. The representational capacity of the attention layer is diminished, as the diversity of learned K\/V projections is lost. Empirical studies have shown that MQA can lead to a noticeable degradation in performance on downstream tasks compared to an equivalent MHA model.<\/span>20<\/span><\/p>\n Grouped-Query Attention (GQA) was introduced as an elegant solution to this trade-off, providing a tunable interpolation between the extremes of MHA and MQA.<\/span>19<\/span> In GQA, the $H$ query heads are divided into $G$ groups, where each group of $H\/G$ query heads shares a single Key and Value head projection.<\/span>25<\/span><\/p>\n This formulation provides a spectrum of architectural choices:<\/span><\/p>\n By choosing an intermediate number of groups (e.g., $1 < G < H$), model designers can finely tune the balance between memory efficiency and model quality.<\/span>19<\/span> GQA recognizes that complete independence of heads (MHA) is often wasteful and over-parameterized, while complete sharing (MQA) can be too restrictive. The introduction of groups provides a “knob” to control the degree of parameter sharing, allowing for a more optimal trade-off. Due to this favorable balance, GQA has become the de facto standard for high-performance LLMs, including Llama 3, Mixtral, and Gemini, as it captures most of the speed and memory benefits of MQA while maintaining quality that is nearly indistinguishable from MHA.<\/span>7<\/span><\/p>\n <\/p>\n <\/p>\n The decision to use MHA, GQA, or MQA involves a direct trade-off between the model’s representational power and its inference efficiency.<\/span><\/p>\n This architectural evolution from MHA to GQA is not merely an inference optimization; it reflects a deeper understanding of the Transformer architecture itself. It suggests that the original MHA design was likely over-parameterized for many tasks. GQA offers a more parameter-efficient architecture that is cheaper to train and faster at inference. This foundational improvement has become a baseline assumption for nearly all subsequent system-level optimizations. Techniques like PagedAttention and quantization benefit immensely from GQA, as it provides a smaller, more manageable KV cache to work with from the very beginning.<\/span>32<\/span><\/p>\n <\/p>\n <\/p>\n While architectural modifications like GQA reduce the intrinsic size of the KV cache, they do not address the systemic inefficiencies of how that cache is managed in memory. The development of PagedAttention by the vLLM project represents a fundamental shift in the software architecture of LLM serving. By abandoning the rigid, contiguous memory model of traditional deep learning frameworks and adopting principles from classical operating systems, PagedAttention solves the critical problem of memory fragmentation, unlocking dramatic improvements in throughput and memory utilization.<\/span><\/p>\n <\/p>\n <\/p>\n LLM serving systems that predate vLLM, such as NVIDIA’s FasterTransformer and Orca, managed the KV cache by allocating a single, large, contiguous block of GPU memory for each incoming request.<\/span>33<\/span> This seemingly straightforward approach is plagued by severe inefficiencies due to the dynamic and unpredictable nature of text generation.<\/span><\/p>\n The combined effect of internal and external fragmentation is catastrophic for system efficiency. It leads to massive memory waste\u2014in some cases, up to 96% of the allocated KV cache memory is left unused.<\/span>38<\/span> This wasted memory severely constrains the number of requests that can be processed concurrently in a batch, crippling overall system throughput and leading to poor GPU utilization.<\/span>33<\/span><\/p>\n <\/p>\n <\/p>\n PagedAttention solves the fragmentation problem by drawing direct inspiration from the virtual memory and paging techniques that have been a cornerstone of modern operating systems for decades.<\/span>33<\/span> The central innovation is to decouple the <\/span>logical<\/span><\/i> organization of a sequence’s KV cache from its <\/span>physical<\/span><\/i> storage in GPU memory.<\/span><\/p>\n The mechanism works as follows:<\/span><\/p>\n This non-contiguous memory layout is incompatible with standard attention kernels, which assume that tensors are stored in a single, contiguous memory block. Therefore, a critical component of PagedAttention is the use of custom-written GPU kernels. These specialized kernels are designed to first read the block table for a given sequence, gather the scattered K and V vectors from their disparate physical locations, and then perform the attention computation.<\/span>36<\/span><\/p>\n <\/p>\n <\/p>\n The adoption of a paged memory model provides a host of profound benefits that collectively redefine the performance ceiling for LLM serving.<\/span><\/p>\n <\/p>\n <\/p>\n Despite its transformative benefits, the PagedAttention model introduces its own set of challenges, primarily related to software complexity and performance overhead.<\/span><\/p>\nThe Role of the KV Cache: From Quadratic to Linear Complexity<\/b><\/h3>\n
The Memory Bottleneck: A Quantitative Analysis<\/b><\/h3>\n
\n
Proactive Reduction: Architectural Modifications to the Attention Mechanism<\/b><\/h2>\n
Multi-Query Attention (MQA): The Radical Reduction<\/b><\/h3>\n
Grouped-Query Attention (GQA): The Balanced Compromise<\/b><\/h3>\n
\n
Performance vs. Quality Trade-offs<\/b><\/h3>\n
\n
The Memory Management Revolution: PagedAttention and Non-Contiguous Caching<\/b><\/h2>\n
The Fragmentation Problem in Contiguous Caching<\/b><\/h3>\n
\n
The PagedAttention Paradigm: A Virtual Memory Analogy<\/b><\/h3>\n
\n
Benefits of Paging<\/b><\/h3>\n
\n
Implementation Overheads and Alternatives (vAttention)<\/b><\/h3>\n
\n