LLM Inference Bottlenecks and KV Cache: Core Mechanisms and Mainstream Optimization Approaches

The speed bottleneck in LLM inference often lies not in the model weights themselves, but in the repeated computation introduced by the attention mechanism. This lesson starts from the computation process of self-attention and breaks down how KV Cache becomes the core memory mechanism for inference acceleration, along with the new challenges it brings and how different inference engines address them.

Self-Attention Computation: The Root of the Inference Bottleneck

During LLM inference, each generated token requires recomputing attention over the current sequence. Taking the input sequence "Aura" as an example, after processing the prompt and generating the next token, the model needs to recompute "Aura" and its subsequent tokens into Q, K, and V matrices. As the sequence keeps growing, the amount of repeated computation rises accordingly, memory and compute overhead expand sharply, and inference speed slows down noticeably.

The Q, K, and V matrices each have distinct roles: Q (Query) represents the token or phrase currently being processed; K (Key) is a set of representations of candidate tokens, used to compute relevance via dot product with Q; V (Value) carries the actual semantics of each candidate token. The attention scores determine which candidate tokens the current token should focus on, and then a weighted sum is performed over the highly relevant V's to obtain the contextual representation used to predict the next token.

It is precisely this mechanism of "recomputing the entire sequence at every step" that constitutes the main computational bottleneck during inference.

Matrix Origins and Dimensions of Q, K, V

In a Transformer, Q, K, and V are not the raw word embeddings themselves; they are obtained by multiplying the hidden representations of the input sequence by three learnable weight matrices $W_Q$, $W_K$, and $W_V$, respectively. If the hidden dimension is $d_{model}$, the number of attention heads is $h$, and the dimension per head is $d_k = d_{model}/h$, then for a sequence of length $L$, the sizes of Q, K, and V are all $L \times d_{model}$ (after multi-head concatenation). The attention scores are computed as $\text{softmax}(QK^T/\sqrt{d_k})V$, where the complexity of $QK^T$ is $O(L^2 d_k)$. This is the direct reason why computation grows quadratically as the sequence lengthens, and it is also the core contradiction that KV Cache aims to resolve.

KV Cache: The Core Mechanism of Trading Space for Time

The idea behind KV Cache is straightforward: cache the K and V that have already been computed and reuse them directly when generating subsequent tokens, avoiding redundant computation.

Specifically, the model first allocates a block of space for the KV Cache, computes and stores all K and V matrices during the input sequence stage. When generating a new token, it only needs to compute the K and V of the current token, concatenate them with the historical K and V in the cache for attention computation, and then append the new token's K and V to the cache. In this loop, the already-processed portion of the sequence does not need to be recomputed, significantly reducing memory and compute overhead.

Inference is typically divided into two stages: the prefill stage feeds the entire prompt into the model, saves the complete KV Cache, and generates the first new token; the decode stage generates subsequent tokens one by one, computing only the current token's K and V each time and using the KV cached during prefill for inference. This division sharply reduces computational complexity, improves memory utilization, and speeds up inference.

Differences in Computational Characteristics Between Prefill and Decode

The prefill stage processes the entire prompt at once, and all tokens can be computed in parallel, making it a compute-bound operation with high GPU utilization; the decode stage generates only one token at a time, and matrix multiplication degenerates into vector-by-matrix multiplication, making it a memory-bound operation whose performance is mainly limited by the bandwidth of reading model weights and KV Cache from memory rather than by floating-point compute. This difference explains why optimization in the decode stage often focuses on memory bandwidth and KV Cache layout, and also explains why quantizing the KV Cache (reducing the number of bytes read) can directly improve decode throughput.

The Cost of KV Cache: Memory Fragmentation and Duplicate Storage

KV Cache is not without cost. Since the final length of the sequence cannot be known in advance, the system must pre-allocate a sufficiently large contiguous space. As the sequence grows, this space keeps expanding and accounts for a considerable share of memory usage—in the course diagram, KV Cache occupies more than 30% of the space, competing with model weights, intermediate value caches, and other data for limited memory resources.

Space waste mainly comes from two aspects. Internal fragmentation: within the large pre-allocated block, the sequence ends early due to EOS before the space is fully used, and the remainder is wasted. External fragmentation: after allocating a large contiguous block, the remaining small, non-contiguous blocks are difficult for the next prompt to use, leaving memory idle.

Another issue is duplicate storage. In decoding algorithms such as parallel sampling and beam search, one prompt generates multiple output results, and each result requires storing the complete sequence of "prompt + result," causing the prompt to be stored repeatedly multiple times and further reducing memory utilization.

The Paged Mapping Principle of PagedAttention

PagedAttention divides the KV Cache into fixed-size blocks, each holding the K and V of several tokens. Logically contiguous sequences are mapped through a block table to physically non-contiguous memory blocks. In this way, when a new token arrives, only a new block needs to be appended, with no need to reserve a large contiguous space, and internal fragmentation is confined to the last partially filled block; different sequences can also point to the same physical block through the block table to achieve sharing, thereby eliminating duplicate storage of prompts during parallel sampling. The block table functions similarly to an operating system's page table, shifting memory allocation from "contiguous reservation" to "on-demand mapping."

Optimization Paths of Mainstream Inference Engines

Based on PagedAttention, vLLM draws on the memory paging idea of operating systems, managing physical memory in blocks and mapping only as much as is used, directly targeting the fragmentation problem. SGLang adopts RadixAttention, managing the KV cache with a tree-shaped data structure and enabling sharing and reuse through prefix matching to improve space utilization. LMDeploy combines quantization techniques, quantizing the KV Cache data type from float to int to compress its footprint at the cost of some precision.

The course's selection advice is to prioritize vLLM. It has the strongest generality, with support for mainstream models and hardware platforms far exceeding the other two, so most general inference needs require no architecture-specific modifications; its ecosystem is mature, integrating online/offline testing, single-kernel performance testing, profiler-based performance analysis, and quantization tools; and its community is active, responding quickly to support for new models. It performs in a balanced way across dimensions such as throughput, latency, and hardware compatibility, making it suitable for high-concurrency API services and general model inference scenarios.

From the computational bottleneck of the attention mechanism, to the cache reuse of KV Cache, to memory fragmentation and engine-level optimization, this chain forms the core thread for understanding LLM inference systems. Mastering KV Cache means mastering the starting point of inference performance optimization.