LLM Inference and KV Caching

Why It Matters

How it Works

The Mechanics of LLM Inference

When we interact with a Large Language Model (LLM), we typically provide a prompt and expect a generated response. Behind the scenes, the model does not generate the entire response at once. Instead, it performs "autoregressive generation." If you ask an LLM to complete the sentence "The cat sat on the...", the model calculates the probability of every word in its vocabulary being the next word. It selects one—say, "mat"—and then appends "mat" to the original prompt. The new sequence, "The cat sat on the mat," is then fed back into the model to predict the next word. This loop continues until the model generates an "end-of-sequence" (EOS) token.

The Bottleneck: Redundant Computation

In a standard Transformer, the self-attention mechanism requires calculating the relationship between every token in the current sequence. If your sequence is 100 tokens long, the model calculates the attention scores for all 100 tokens. When it generates the 101st token, a naive implementation would re-calculate the attention scores for the first 100 tokens all over again, plus the new one. As the sequence grows, this becomes incredibly slow. The computational cost of attention grows quadratically () with the length of the sequence. For long documents or complex reasoning tasks, this re-computation becomes the primary bottleneck for inference speed.

The KV Cache Solution

The KV Cache is a clever optimization that solves this redundancy. During the first pass (the prompt processing phase), the model computes the Key and Value tensors for every token in the input. Instead of discarding these after the first token is generated, we store them in a dedicated memory buffer—the KV Cache. When generating the next token, the model only needs to compute the Key and Value for the newly generated token. It then retrieves the cached Keys and Values for all previous tokens and concatenates them. This reduces the attention calculation to a simple lookup and append operation, effectively turning the problem into an process for the total generation, where each individual step is relative to the history.

Managing Memory Constraints

While the KV Cache significantly improves speed, it consumes a massive amount of VRAM. Each token's Key and Value vectors are stored as floating-point numbers. As the sequence length increases, the cache grows linearly. If you are serving 100 users simultaneously, each with their own KV cache, you can quickly run out of GPU memory. This is where modern techniques like PagedAttention (introduced in the vLLM library) become vital. By treating the KV cache like virtual memory in an OS, we can store these tensors in non-contiguous memory blocks, reducing fragmentation and allowing the system to handle significantly more concurrent requests than a naive implementation would permit.

Common Pitfalls

Sample Code

import torch
import torch.nn.functional as F

def simple_kv_attention(q, k_cache, v_cache, d_k):
    # q: (1, head_dim), k_cache: (seq_len, head_dim), v_cache: (seq_len, head_dim)
    # Compute attention scores for the new token against the history
    scores = torch.matmul(q, k_cache.transpose(-2, -1)) / (d_k ** 0.5)
    attn_weights = F.softmax(scores, dim=-1)
    
    # Compute the weighted sum of the cached values
    output = torch.matmul(attn_weights, v_cache)
    return output

# Mocking a scenario: 4 tokens already in cache, generating the 5th
d_k = 64
seq_len = 4
k_cache = torch.randn(seq_len, d_k)
v_cache = torch.randn(seq_len, d_k)
new_q = torch.randn(1, d_k)

# Resulting context vector for the new token
context = simple_kv_attention(new_q, k_cache, v_cache, d_k)
print(f"Context vector shape: {context.shape}")
# Output: Context vector shape: torch.Size([1, 64])

Key Terms

Related Concepts