The Cache Ladder

“Add a cache” sounds like one engineering task. For a language-model system, it can mean at least four:

1. return the output stored for the same request;
2. return an output stored for a similar request;
3. recognize an identical token prefix and skip repeated prefill work;
4. retain the transformer's key-value state so later computation can resume from it.

The first two reuse an answer. The latter two reuse computation. Confusing them causes both disappointing savings and subtle correctness failures.

The right question is not “What hit rate can we get?” It is:

Which work can this system safely avoid, for how long, under which identity, model, data, policy, and side-effect boundaries?

That question turns caching from a speed trick into a controlled economic decision.

Four caches, four contracts

Cache	Key resembles	Value stored	Work avoided	Primary risk
Exact output	canonical request identity	final response and evidence	whole generation and tools, if included	incomplete key or stale answer
Semantic output	embedding plus filters	response from a similar request	whole generation	false equivalence
Prefix	token IDs and model identity	reusable prefix location or KV blocks	repeated prefill	incompatible prefix or eviction
KV	model-specific attention state	per-layer key and value tensors	recomputing prior tokens	memory, placement, version mismatch

An exact cache can sit at an API boundary. A semantic cache is a retrieval and policy system. Prefix reuse normally lives close to the serving scheduler. KV state lives inside or beside the inference runtime. Their owners, telemetry, invalidation triggers, and failure blast radii differ.

Start by writing the contract in one sentence:

For requests in scope S, artifact A may be reused when predicate P holds,
until invalidation event I, with fallback F and maximum consequence C.

If the predicate is merely “cosine similarity is above 0.9,” the contract is unfinished.

Exact output caching is equality after canonicalization

Suppose a documentation assistant receives the same public question repeatedly. A key might include:

hash(
  tenant_id,
  authorization_scope,
  normalized_question,
  retrieval_corpus_version,
  system_policy_version,
  model_and_sampling_policy,
  locale,
  tool_contract_version
)

This looks excessive until one omitted field changes the answer.

• Omit tenant_id, and one customer's private answer may cross into another tenant.
• Omit authorization_scope, and a previously privileged result may be exposed.
• Omit corpus_version, and a revoked policy may remain apparently current.
• Omit tool_contract_version, and an old action payload may no longer validate.
• Omit sampling policy, and the cache silently changes a stochastic product into a deterministic one.

Canonicalization should remove variation that truly does not affect meaning, such as harmless whitespace in a controlled input. It must preserve variation that changes policy or outcome. Do not sort a list if order is meaningful. Do not lowercase identifiers if the downstream system is case-sensitive.

An exact hit is not automatically fresh. Attach provenance and expiry to the value:

{
  "answer": "...",
  "evidence_ids": ["policy-17#section-4"],
  "created_at": "2026-07-15T09:00:00Z",
  "corpus_version": "kb-481",
  "policy_version": "support-v12",
  "model_route": "route-factual-v5",
  "expires_at": "2026-07-15T10:00:00Z"
}

Time-to-live is only one invalidation tool. Event-based invalidation is better when a changed document, permission, price, or account state has a known dependency. Keep a reverse index from source or policy version to affected entries when the domain justifies it.

Semantic caching asks a harder question than nearest-neighbor search

A semantic cache embeds a new query, retrieves similar historical queries, and may return a stored response. GPTCache describes this architecture with an embedding generator, similarity search, cache storage, and an evaluator that decides whether a candidate qualifies.

The engineering temptation is to interpret similarity as interchangeability. It is not.

Consider these query pairs:

Query A	Query B	Lexically close?	Safe to share?
“Reset my password”	“How do I reset my password?”	yes	often, for public instructions
“Can user 41 read invoice 7?”	“Can user 47 read invoice 7?”	yes	no
“Dose for a 70 kg adult?”	“Dose for a 7.0 kg infant?”	yes	no
“Price today in INR”	“Price yesterday in INR”	yes	not necessarily
“Cancel the draft order”	“Cancel the paid order”	yes	no

Embedding distance can underweight the one slot that controls the decision. MeanCache explicitly incorporates user context because context-free lookup can confuse personalized and standalone requests. That is a useful design direction, but no paper supplies a universal safe threshold for your domain.

A production semantic key usually needs both similarity and hard filters:

eligible(candidate) =
  same tenant
  and same authorization class
  and same intent class
  and same policy/data version
  and compatible entities and time scope
  and similarity >= threshold_for_this_intent

For actions, personalized decisions, changing facts, or high-loss answers, the sensible threshold may be “do not return cached output.” The semantic layer can still retrieve an earlier answer as context for a fresh model call. That converts a dangerous answer cache into a potentially useful memory system.

Prefix caching reuses work without reusing the answer

Transformer inference first processes the prompt during prefill. If many requests begin with the same long system instruction, tool schema, few-shot examples, or document prefix, recomputing those token states wastes work.

A prefix cache recognizes an identical token sequence and makes its precomputed state available to later requests. The later suffix is still processed, and output tokens are still generated. The model can therefore produce a fresh answer for each request.

SGLang introduced RadixAttention for automatic KV reuse across structured language-model programs. A radix tree represents shared token prefixes, while cache-aware scheduling can favor requests whose reusable state is resident. The paper's measured improvements belong to its tested programs and machines. The general mechanism is more important here: prompt structure becomes a serving optimization surface.

Two prompts that look identical to a human can tokenize differently because of whitespace, serialization order, chat templates, special tokens, or tokenizer version. Prefix identity should be checked on token IDs after final prompt construction, not on a casually normalized string.

Prompt design now has a measurable cost dimension. Stable content should appear before variable content when semantics allow it. Tool schemas should serialize deterministically. Frequently changing timestamps placed near the front can destroy reuse for everything after them.

This does not justify distorting a prompt that performs better. Measure verified outcome quality and prefix-hit economics together.

KV caching is state management inside inference

During autoregressive decoding, each new token attends to prior tokens. The runtime stores key and value tensors for earlier positions so it does not recompute the whole sequence at every step. This is the KV cache.

KV state grows with sequence length, number of layers, KV heads, head dimension, bytes per element, and active sequences. A simplified per-sequence estimate is:

KV bytes ≈ tokens * layers * 2 * KV_heads * head_dim * bytes_per_element

The factor two represents keys and values. Architectures and implementations differ, so use the actual model configuration and runtime allocator for planning.

PagedAttention applies virtual-memory ideas to KV-cache allocation. Blocks reduce waste caused by reserving contiguous memory for uncertain sequence lengths and can enable sharing. This is distinct from deciding that two questions deserve the same answer.

Reusable KV state is tightly coupled to its computation:

• model weights and revision;
• tokenizer and chat template;
• adapter or fine-tune identity;
• exact token IDs and positions;
• attention and positional-encoding configuration;
• numerical format and runtime compatibility.

Changing any of these may invalidate reuse. Treat a model rollout like a cache-version rollout.

MemServe, an author preprint, explores context caching across disaggregated serving through an elastic memory pool and locality-aware scheduling. It highlights the next systems problem: cached state has a location. A remote hit can lose to local recomputation if discovery, transfer, or contention costs exceed saved prefill.

Eviction decides which future work remains cheap

Cache capacity is finite, so admission and eviction form a prediction policy. Least-recently-used eviction is simple, but recency alone may retain a huge low-value prefix while evicting many small, frequently reused prefixes. A better score can include reuse probability, bytes occupied, recomputation time, transfer cost, tenant fairness, and expiry:

retention value
= expected future hits * avoided recomputation
  - bytes * memory opportunity cost
  - expected transfer and lookup cost
  - staleness risk

The score need not be sophisticated on day one. It must be observable. Record why an entry was admitted, evicted, or bypassed and how much work later misses recomputed.

Protect the state plane from cache pollution. One tenant, crawler, or agent that produces unique long prompts can evict useful shared prefixes. Apply per-tenant quotas or weighted fairness, reject entries larger than their plausible reuse value, and separate short-lived session state from durable common prefixes. For semantic caches, low-quality or adversarial inputs can also populate misleading candidates. Admit only verified responses with explicit provenance, not every model output.

Eviction changes queueing behavior. A burst can simultaneously raise arrivals and lower hit rate by displacing hot state, making each later request more expensive. Capacity tests should therefore begin from both warm and cold caches and should include churn, not only a steady collection of popular prompts.

Work the economics before celebrating hit rate

For cache layer i, a first-order expected value is:

net value_i =
  eligible_requests * hit_rate_i * avoided_cost_i
  - lookup_cost_i
  - storage_and_transfer_cost_i
  - invalidation_cost_i
  - expected_false_return_loss_i
  - expected_staleness_loss_i

Layers interact. An exact output hit prevents the request from reaching prefix reuse. A prefix hit changes only prefill cost, not tool or decode cost. Calculate a funnel rather than adding independent hit rates.

Take 100,000 illustrative requests at $0.0040 generation cost each. Exact output caching hits 18 percent. Among the remaining 82,000, prefix reuse hits 35 percent and avoids $0.0012 of prefill work. Among 53,300 later semantic-cache candidates, 12 percent return a stored output. Semantic lookup costs $0.00008 for each candidate. Cache operations cost $18 for the period.

Before incorrect returns, the arithmetic is attractive:

baseline generation              $400.00
exact savings                     $72.00
prefix savings                    $34.44
semantic generation savings       $25.58
semantic lookup                    -$4.26
cache operations                  -$18.00
subtotal savings                  $109.76

Now suppose 1.5 percent of 6,396 semantic hits are false returns. That is about 96 wrong reuses. At $2.00 expected loss each, false-return loss is $191.88. The cache loses about $82.12 overall.

At two cents of consequence per false return, the same system saves about $107.84. Neither scenario predicts your product. They prove that the consequence distribution, not hit rate alone, decides whether semantic output reuse belongs in the path.

The relevant denominator is cost per verified successful outcome, introduced in Cost per Successful Outcome. A cached response that is fast, cheap, and wrong is not goodput.

Invalidation is part of the data model

Write an invalidation table before implementation:

Change	Exact output	Semantic output	Prefix/KV
source document updated	invalidate dependents	invalidate or refilter	unaffected unless prompt changes
permission changed	invalidate subject/scope	invalidate subject/scope	computational state may remain safe only if no private cross-user reuse
model weights changed	policy choice, usually version	re-evaluate quality and version	invalidate
system prompt changed	invalidate	invalidate or version	invalidate changed prefix
price or live inventory changed	short TTL or event invalidation	usually bypass	reusable prompt prefix may remain valid
tool caused a side effect	never replay effect from answer cache	do not treat similarity as authorization	KV reuse does not replay the effect itself

For retrieval-grounded answers, store evidence identifiers and corpus versions with the cached value. For side-effecting workflows, separate planning text from the execution token. A cached plan can be revalidated; a cached “payment succeeded” must never stand in for a payment transaction.

A builder playbook

1. Instrument avoidable work before adding storage

Measure repeated exact requests, repeated token prefixes, prefill share of latency and cost, semantic clusters, and answer volatility. If prompts rarely share prefixes, a distributed KV pool is unlikely to be the first investment.

2. Start with the narrowest correctness domain

Good early candidates include immutable public explanations, deterministic transformations with versioned inputs, and long stable prompt prefixes. Poor candidates include authorization decisions, live balances, medical or legal conclusions, and irreversible actions.

3. Shadow semantic decisions

Run semantic lookup without serving its answer. Record candidate, similarity, filters, fresh answer, verified correctness, latency, and counterfactual savings. Label false returns by reason: entity mismatch, temporal mismatch, scope mismatch, intent mismatch, or stale evidence.

4. Calibrate by intent and consequence

One global threshold is rarely defensible. Build precision and coverage curves for each intent class. Optimize expected value under a minimum precision constraint, and include an abstain region.

5. Load-test the state plane

For prefix and KV reuse, replay real tokenized prompts. Measure hit rate, TTFT, goodput, memory occupancy, eviction, transfer time, scheduler locality, and recomputation. A theoretical hit that waits behind a congested transfer is not a product win.

6. Make every hit explainable

Emit a cache-decision span with:

layer, key_version, candidate_id, hard_filters,
similarity, threshold, age, provenance, bytes,
avoided_prefill_tokens, avoided_generation, disposition

This joins the request path from From Prompt to Proof to the capacity model in Capacity Is a Queue. Cache misses consume capacity. Cache hits consume state, policy, and trust.

The decision

Use exact output caching when equality can be fully defined and freshness can be enforced. Use semantic output caching only where domain-calibrated precision and consequence make answer reuse acceptable. Use prefix caching when repeated token prefixes make prefill material. Use KV caching and careful memory management whenever autoregressive inference runs at scale, while versioning the state as strictly as the model.

The best cache is not the one with the highest hit rate. It is the one whose reuse contract preserves verified outcomes while reducing the correct bottleneck.

References

• Efficient Memory Management for Large Language Model Serving with PagedAttention, Kwon et al., SOSP 2023. The primary systems paper for paged KV-cache memory management in vLLM.
• SGLang: Efficient Execution of Structured Language Model Programs, Zheng et al., NeurIPS 2024. Introduces RadixAttention and cache-aware execution for shared prompt structure.
• MemServe: Context Caching for Disaggregated LLM Serving with Elastic Memory Pool, Yao et al., 2024 preprint. Explores distributed context state, placement, and locality.
• GPTCache: An Open-Source Semantic Cache for LLM Applications, Zeng et al., NLP-OSS 2023. Describes the semantic lookup and evaluator architecture.
• MeanCache: User-Centric Semantic Caching for LLM Web Services, Gill et al., 2024 preprint. Adds contextual identity to semantic reuse and illustrates why query text alone is insufficient.

The calculations in this article are illustrative. Inputs and derivations are preserved in the accompanying claim ledger.