Prefix caching — when repeated prompts can skip most of prefill

Over the last few lessons, we have built a fairly complete picture of LLM inference.

We learned that prefill processes the prompt in parallel and builds the KV cache. We learned that decode generates tokens sequentially. We then looked at speculative decoding, quantization, and PagedAttention.

Today we can combine several of those ideas into an optimization that is conceptually simple but extremely important in real serving systems:

This is prefix caching.

The intuition is straightforward: if a Transformer has already processed a particular prefix, then the keys and values produced for that prefix can be reused by another request with the same prefix.

But the deeper lesson is more interesting.

Prefix caching turns the KV cache from merely temporary state for one request into a reusable computation cache across requests.

Start with a common system prompt¶

Imagine an application sends every request with a 4,000-token system prompt:

You are Acme Corp's support assistant.

Here are the support policies...
Here is the product catalog...
Here are examples of good responses...
[thousands more tokens]

Then each user contributes a short question.

Request A might be:

[4,000-token shared system prompt]

My package arrived damaged. What should I do?

Request B:

[4,000-token shared system prompt]

Can I change my shipping address?

Request C:

[4,000-token shared system prompt]

How long does a refund take?

Without prefix caching, the model performs prefill over the same 4,000 tokens three times.

Conceptually:

Request A:
shared 4000 tokens + user A
→ prefill

Request B:
shared 4000 tokens + user B
→ prefill

Request C:
shared 4000 tokens + user C
→ prefill

The shared work is duplicated.

Why the computation is reusable¶

Remember what causal attention means.

At position \(t\), a token can depend only on:

It cannot depend on future tokens.

Therefore the hidden state, key, and value computed for token 500 in a prefix depend only on tokens:

If two requests have exactly the same first 4,000 tokens, then — assuming the same model and inference configuration — the computation for those positions is the same.

So their KV tensors for the shared prefix are also the same:

and:

There is no reason to compute and store independent copies if the serving system can safely reuse them.

The book-prefix mental model¶

Imagine three students reading the same 100-page textbook chapter before answering different questions.

The naive system says:

Student A reads pages 1–100
Student B reads pages 1–100
Student C reads pages 1–100

Prefix caching says:

We already made detailed notes for pages 1–100. Give every student those notes and let each continue from there.

The cached KV state is not the original text.

It is closer to the Transformer's layer-by-layer working notes about that text.

The model still needs the logical prefix to exist in its context, but it does not need to recompute those notes.

What exactly is cached?¶

Suppose the model has:

Transformer layers.

For each cached token, we need the key and value tensors used by attention at every layer.

Conceptually:

token 1:
  layer 1 → K,V
  layer 2 → K,V
  ...
  layer L → K,V

token 2:
  layer 1 → K,V
  layer 2 → K,V
  ...
  layer L → K,V

...

So a prefix cache entry is potentially large.

This is not like caching a tiny HTTP response header.

We are caching substantial GPU-resident model state.

That means prefix caching has an economics problem:

The server must decide which prefixes are worth keeping.

A concrete example¶

Suppose a request contains:

prompt tokens.

The first:

tokens match a cached prefix.

Only the final:

tokens are new.

Without caching, prefill processes all:

tokens.

With a perfect prefix-cache hit, the server restores the KV state for the first 8,000 tokens and performs new prefill only for the remaining 2,000.

The fraction of prompt tokens whose prefill is skipped is:

So 80% of the prompt positions are already represented in cached state.

This does not necessarily mean an 80% reduction in wall-clock latency, because attention cost, cache lookup, memory movement, batching, and hardware utilization complicate the relationship.

But the amount of duplicated Transformer work can fall dramatically.

Why this matters more as prompts get longer¶

Consider a tiny prompt:

Translate "hello" to French.

Caching a five-token prefix is not very valuable.

Now consider an agent request containing:

system instructions
tool definitions
company policy
retrieved documents
conversation history
user message

The prompt may contain tens of thousands of tokens.

And much of the beginning may repeat across requests.

For example:

same system prompt
same tool schemas
same policy documents
same few-shot examples
different user question

As prompts become larger, repeated prefixes become expensive enough that caching them can materially change serving cost and latency.

Why the match must be a prefix¶

Suppose two prompts are:

A:
The cat sat on the mat because it was tired.

B:
The cat sat near the mat because it was tired.

They share many words.

But after:

The cat sat

they diverge.

Because causal Transformer states after the divergence depend on different preceding tokens, we cannot simply reuse the later state because the later text happens to become similar again.

The reusable portion is the longest exact prefix:

where LCP means longest common prefix.

Conceptually:

A: [ SAME SAME SAME ][ DIFFERENT ........ ]
B: [ SAME SAME SAME ][ DIFFERENT ........ ]
                       ↑
                 cache reuse stops

Once the histories differ, subsequent hidden states and KV entries belong to different computations.

Token identity matters, not textual appearance¶

There is another subtlety.

The cache operates on the model's token sequence.

So what must match is effectively:

Two pieces of text that look almost identical can tokenize differently because of whitespace, formatting, normalization, or templating.

For example, changing:

Tools:

to:

Tools: 

with an extra space may alter tokens downstream depending on the tokenizer.

Likewise, dynamically inserting timestamps or request IDs near the beginning of a prompt can destroy cache reuse for everything after them.

This leads to an important application-design principle:

if you want prefix caching to work well.

Prompt layout becomes a systems optimization¶

Imagine this prompt:

Current time: 2026-09-25 08:53:57

[4,000 tokens of static instructions]

User: ...

Every request gets a different timestamp at the beginning.

The cache sees:

request A:
[different token][static static static ...]

request B:
[different token][static static static ...]

The common prefix may end almost immediately.

Now reorder it:

[4,000 tokens of static instructions]

Current time: 2026-09-25 08:53:57

User: ...

Now many requests share the entire static prefix.

Nothing about the model changed.

Nothing about the GPU changed.

We merely reordered semantically compatible prompt components so the serving system can reuse more computation.

That is a striking example of application structure affecting hardware efficiency.

How do we find a cached prefix?¶

A server needs a way to identify previously computed token blocks.

A simple conceptual scheme hashes blocks of tokens.

Suppose blocks contain 16 tokens.

For a sequence:

we could form:

block 0 → tokens  1–16
block 1 → tokens 17–32
block 2 → tokens 33–48
block 3 → tokens 49–64

Each logical block can have a hash that depends on both its own tokens and the preceding prefix.

Conceptually:

and so on.

The chained structure matters because the same 16-token block appearing after a different history does not necessarily have reusable KV state.

The cache can map:

prefix hash
→ physical KV blocks

This starts to look much more like a storage system than a neural-network equation.

PagedAttention makes prefix caching natural¶

Yesterday we learned to represent KV memory as blocks:

logical block 0 → physical block 7
logical block 1 → physical block 2
logical block 2 → physical block 9

Now suppose Request A has already computed blocks 0–99.

Request B begins with exactly the same prefix.

Instead of copying those KV tensors, B can reference the same immutable physical blocks:

                    ┌→ Request A
cached KV blocks ───┤
                    └→ Request B

When the requests diverge, each gets new private blocks:

                    ┌→ A private suffix
shared prefix ──────┤
                    └→ B private suffix

This is why PagedAttention and prefix caching fit together so well.

Paging gives us a convenient unit of memory sharing.

Reference counting¶

If several requests share a physical KV block, the allocator cannot free it when the first request finishes.

It needs to know how many active owners remain.

Conceptually:

physical block 42

references:
Request A
Request B
Request C

refcount = 3

If A finishes:

refcount = 2

If B finishes:

refcount = 1

Only when the last owner releases it can the block become reclaimable — unless the server deliberately keeps it in the prefix cache for future requests.

This is classic memory-management machinery appearing inside an AI inference engine.

Cache eviction¶

GPU memory is finite.

Suppose the server has cached thousands of prefixes but now needs space for active requests.

Which cached blocks should it discard?

This is a cache-eviction problem.

A simple policy might resemble least recently used:

prefix A → used 2 ms ago
prefix B → used 4 s ago
prefix C → used 3 min ago
prefix D → used 1 hour ago

evict D first

But more sophisticated policies could consider:

prefix size
reuse frequency
cost to recompute
current memory pressure
tenant or workload priority

A 20,000-token prefix that is reused every second is much more valuable than a 200-token prefix seen once yesterday.

So a useful conceptual value metric is something like:

Real schedulers may not compute exactly this formula, but it captures the tradeoff.

Prefix caching does not eliminate decode work¶

Suppose a user asks for a 1,000-token answer.

Even if the entire prompt is cached, the model still must generate those output tokens autoregressively.

Prefix caching primarily attacks:

not:

This connects directly to Day 46.

A workload dominated by enormous repeated prompts and short answers may benefit dramatically.

A workload with tiny prompts and huge generations may benefit much less.

Again, "LLM latency" is not one workload.

Time to first token is the obvious beneficiary¶

Recall:

Prefill lies on the path to the first output token.

If most of a long prompt is already cached, the server can potentially reduce the work before generation begins.

So prefix caching can improve:

especially for long, repeated prefixes.

It can also reduce compute consumption, allowing the server to spend more capacity on other requests.

That may improve throughput indirectly.

Prefix caching versus semantic caching¶

These are easy to confuse.

Prefix caching says:

These exact initial tokens have already been processed, so reuse their internal KV state.

Semantic caching says something more like:

This new question resembles a previous question, so perhaps reuse the previous answer or result.

Those are fundamentally different.

Prefix caching is an exact computation-reuse optimization inside model inference.

It does not decide that two questions "mean the same thing."

It preserves normal model execution after the cached prefix.

Prefix caching versus RAG caching¶

Suppose retrieval repeatedly returns the same document.

You might cache the retrieval result itself.

That saves:

database / vector-search work

But if the document is still inserted into the prompt, the LLM must normally prefill those tokens.

Prefix caching can additionally save:

Transformer work over repeated prompt tokens

These layers can compose:

retrieval cache
→ avoid repeated retrieval

prefix cache
→ avoid repeated Transformer prefill

KV cache
→ avoid recomputing previous tokens during decode

Different caches eliminate different duplicated work.

A subtle limitation: cached KV state is model-specific¶

Suppose you update the model weights.

The old cached KV tensors were computed using:

from the old model.

They are not generally valid for the new model.

Likewise, changes to model configuration, adapters, or other computation-affecting state can invalidate reuse.

So the true cache key is conceptually richer than just:

It is closer to:

Caching is safe only when the computation being reused is actually identical.

Multi-tenant serving adds another complication¶

Imagine two customers happen to use identical prompt prefixes.

Technically, the resulting KV tensors might be reusable.

Operationally, a serving system must also consider isolation and privacy.

Cache metadata, timing behavior, or reuse policies should not accidentally create cross-tenant information leaks.

So production caching systems may partition caches by tenant, trust boundary, model instance, or other security context.

This is a broader systems lesson:

An optimization that is mathematically valid is not automatically operationally safe.

Prefix caching and agent workloads¶

Modern agents make prefix caching especially interesting.

An agent prompt might repeatedly contain:

system instructions
tool descriptions
tool schemas
behavioral policy
workspace context
conversation history
current observation

During a multi-step agent loop, much of the prefix can remain unchanged while only the newest observation and tool result are appended.

Conceptually:

step 1:
[ stable prefix ][ observation 1 ]

step 2:
[ stable prefix ][ observation 1 ][ action 1 ][ observation 2 ]

step 3:
[ stable prefix ][ observation 1 ][ action 1 ][ observation 2 ][ action 2 ]...

The system can potentially reuse substantial previously computed state rather than repeatedly prefilling the entire growing transcript.

This is one reason inference architecture becomes increasingly important as models move from single-turn chat toward long-running agents.

The deeper connection: computation can have locality too¶

We usually think of locality in memory terms.

Nearby addresses are likely to be reused.

But repeated prompts create computational locality.

Across requests, the server repeatedly encounters the same prefix:

That means the same expensive function:

is being evaluated again and again.

Caching replaces repeated evaluation with lookup:

This is the same fundamental idea behind many computer systems:

CPU cache
database cache
web cache
compiled-code cache
memoization

LLM prefix caching is memoization for part of a Transformer computation.

The key mental model¶

Think of prefill as constructing a road through the model.

Without caching, every request that starts in the same place rebuilds the same first 100 miles:

Request A:
build mile 1 → 100
then build its unique road

Request B:
build mile 1 → 100 again
then build its unique road

Prefix caching says:

shared road already exists
        ↓
Request A joins at mile 100 → builds suffix A
Request B joins at mile 100 → builds suffix B

The shared road is the cached KV state.

PagedAttention gives us blocks from which that road can be assembled and shared.

That gives us today's main principle:

And once the serving system recognizes that, long system prompts, tool definitions, repeated documents, and agent histories can become assets rather than pure overhead.

The broader lesson is one we have now seen repeatedly in LLM inference:

Performance improves when we stop treating every token, request, and tensor as completely new work and start identifying what can safely be reused.