Mathematical and Architectural Foundations#

Before looking at systems like vLLM, we must understand exactly why the Transformer architecture structurally demands a KV Cache, Start with the self-attention equation:

$Attention(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$

During the Prefill Phase (when the model processes our prompt of length $N$), all tokens are processed in parallel. We compute the Query ($Q$), Key ($K$), and Value ($V$) matrices for the entire sequence at once.

During the Decode Phase (generating token $t+1$), we only input the single newly generated token $t$ into the model. The query is a single vector $q_{t} \in \mathbb{R}^{1 \times d}$. However, to compute the attention weights for this new token, $q_{t}$ must be dotted with the Keys of all previous tokens ($K_{1:t}$). The resulting attention distribution must then scale the Values of all previous tokens ($V_{1:t}$).

If we do not cache $K_{1:t}$ and $V_{1:t}$, we have to recompute the $K$ and $V$ vectors for every single past token, at every single generation step. Without caching, the computational complexity of generating $M$ tokens for a sequence of length $N$ scales quadratically as $O((N+M)^2)$ in terms of FLOPs, because we are constantly re-running the entire past sequence through the projection layers.

What is FLOP?

In computing, a FLOP stands for Floating-Point Operation. It is a fundamental unit of measurement representing a single, basic arithmetic calculation - such as addition, subtraction, multiplication, or division—performed on “floating-point” numbers.

Unlike integers (whole numbers), floating-point numbers use a formulaic representation to track decimals and extremely large or small values (like $3.14159$ or $6.022 \times 10^{23}$). Because computing with decimals requires shifting exponents and aligning decimal points dynamically, a single floating-point operation is significantly more hardware-intensive than an integer operation.

FLOP vs. FLOPS

It is easy to confuse these two terms because they look almost identical, but they measure entirely different things:

• FLOP (Floating-Point Operation): This is a count of the total workload. It represents the absolute quantity of math operations required to run an algorithm or execute a model. For example, running a single forward pass of a 7-billion parameter language model might require a fixed budget of roughly 14 billion FLOPs per token.
• FLOPS (Floating-Point Operations Per Second): This is a rate of speed. It measures the raw performance and compute throughput of hardware. If a modern graphics processing unit is rated at 300 TeraFLOPS (TFLOPS), it means the chip is capable of performing 300 trillion floating-point calculations every single second.

In the context of deep learning and large language models, FLOP counts serve as the universal currency for measuring computational complexity. Because neural networks are fundamentally composed of massive matrix multiplications, we can mathematically project exactly how many physical calculations are needed to train or run a model based on its size. For instance, a widely used rule of thumb in deep learning is that computing a single forward pass through a model requires approximately $2P$ FLOPs per token, where $P$ represents the total number of active parameters in the model.By calculating the total FLOPs of an algorithm and comparing it to the physical FLOPS limit of our hardware, we can instantly determine the theoretical minimum time it will take to train a model or generate a response.

With caching, however, by storing $K_{1:t}$ and $V_{1:t}$ in memory, we only need to compute $q_t, k_t,$ and $v_t$ for the single new token. This drops the computational complexity per step to $O(1)$ relative to past tokens, turning the cumulative FLOP generation cost into a linear $O(M)$ relation.

The Hardware Bottleneck#

Once we understand the math, we must look at how this execution maps to GPU hardware. The primary bottleneck in LLM generation is not raw compute power (FLOPS), but memory bandwidth.

An algorithm’s execution on hardware is bound by either its compute limits or its memory bandwidth limits. This relationship is defined by Arithmetic Intensity:

$\text{Arithmetic Intensity} = \frac{\text{Operations (FLOPs)}}{\text{DRAM Access (Bytes)}}$

During the auto-regressive decode phase, the arithmetic intensity is extremely low. We load massive weight matrices and the growing KV Cache from High Bandwidth Memory (HBM) into the GPU’s fast SRAM just to perform a tiny matrix-vector multiplication for a single token.

Bridging to vLLM#

Traditional systems allocated a static, contiguous chunk of GPU memory for each request’s maximum possible sequence length. This led to massive waste:

• Fragmentation: Memory was pre-allocated but went unused if the prompt or response was short.
• Over-allocation: Memory was reserved for future tokens that hadn’t been generated yet.

vLLM’s primary innovation is PagedAttention, an algorithm inspired by how operating systems handle virtual memory. Instead of allocating contiguous blocks of memory for the KV Cache, PagedAttention breaks the cache into small, fixed-size blocks and manages them via a lookup table. This delivers a few immediate benefits:

• Near-Zero Waste: It reduces memory fragmentation to under 4%, freeing up massive amounts of GPU memory.
• Massive Throughput: Because memory is used efficiently, the system can batch way more concurrent requests together (Continuous Batching), drastically increasing throughput compared to traditional serving frameworks.
• Efficient Memory Sharing It allows requests that share the same prompt prefix (like system prompts or multi-turn conversations) to point to the exact same physical memory blocks, cutting down memory usage even further.

So, while frameworks like Megatron-LM or DeepSpeed handle the complexities of distributed training, vLLM steps in completely downstream. It takes a fully trained model and ensures we can serve it to as many users as possible, as fast as possible, without burning through unnecessary GPU memory.