KV caching and prompt caching: how LLMs achieve lightning-fast inference

When interacting with Large Language Models (LLMs), you may have noticed that generating responses over long documents can feel sluggish or prohibitively expensive.

Why does this happen, and how do modern inference engines (such as vLLM, TensorRT-LLM, and API providers like Anthropic and OpenAI) optimize autoregressive decoding?

The secret lies in two interconnected techniques: KV Caching and Prompt Caching (Prefix Caching).

NAIVE ATTENTION (Recompute past tokens every step):
Step 1: Compute Token 1
Step 2: Recompute Token 1 ➔ Compute Token 2
Step 3: Recompute Token 1 & 2 ➔ Compute Token 3
Complexity: O(N²) quadratic matrix operations

KV CACHED ATTENTION (Compute once, read from GPU VRAM):
Prefill: Compute K & V tensors for prompt ➔ Store in VRAM
Step 1: Compute Q_1 ➔ Multiply with Cached K, V ➔ Output Token 1
Step 2: Compute Q_2 ➔ Multiply with Cached K, V ➔ Output Token 2
Complexity: O(1) per token generation step

---

1. The Quadratic Attention Problem

In standard Transformer self-attention, the attention mechanism is computed as:

Attention(Q, K, V) = softmax((Q * K^T) / sqrt(d_k)) * V

During autoregressive generation, each newly generated token must attend to all previous tokens in the sequence. Without caching:

• Generating token N requires re-running matrix multiplications across all previous tokens 1 through N-1.
• Generating a sequence of length N results in quadratic O(N²) computational complexity.

---

2. How KV Caching Works

During the Prefill Phase, the model processes the entire user prompt at once. It computes the Query (Q), Key (K), and Value (V) vectors for all prompt tokens.

Because the past tokens never change during generation, their Key and Value vectors remain static.

The Decoding Optimization:

1. Store all calculated K and V tensors across every attention layer in GPU high-bandwidth memory (HBM).
2. When predicting the next token, compute only the Query vector (Q_new) for the current single token.
3. Compute attention by querying Q_new against the stored K_cached and V_cached vectors.
4. Append the new token’s K and V vectors to the cache.

This transforms the decoding phase from O(N²) down to O(N) total operations.

---

3. Prompt Caching (Cross-Request Prefix Caching)

While KV caching speeds up token generation within a single request, Prompt Caching (or Prefix Caching) extends this concept across multiple distinct HTTP requests:

Request 1 (User A): [System Prompt (5,000 tokens)] + [Question A]
                     ▲ (Computed & Saved to KV Cache)

Request 2 (User B): [System Prompt (5,000 tokens)] + [Question B]
                     ▲ (Cache Hit! Skip 5,000 tokens of prefill calculation)

Benefits of Prompt Caching:

• 80% Latency Reduction (Time-to-First-Token): The inference server skips the heavy prefill compute phase and begins streaming tokens immediately.
• Up to 90% Cost Discount: Major LLM providers (Anthropic Claude, OpenAI GPT-4o, DeepSeek) charge up to 90% less for cached input tokens.

---

4. Production Architectural Best Practices

1. Static System Instructions First: Always place long, immutable text (system instructions, tool definitions, documentation) at the start of your prompt. Dynamic content (user query, timestamps) should always go at the very end to prevent cache invalidation.
2. PagedAttention & Memory Virtualization: Standard KV caches suffer from memory fragmentation. Use modern serving frameworks like vLLM that implement PagedAttention (inspired by OS virtual memory pages) to dynamically allocate non-contiguous GPU memory blocks.
3. Chunked Prefill: For extreme context lengths (128k+ tokens), combine KV caching with chunked prefill to prevent large prompt spikes from starving active decoding batches.