--- title: The Cache Ladder slug: the-cache-ladder canonical_url: https://blog.openfactoryai.com/the-cache-ladder published_at: 2026-07-14T20:44:00.289665+00:00 author: OpenFactoryAI tags: LLM caching, semantic cache, prefix cache, KV cache, inference optimization tldr: An LLM cache can reuse a final answer, a semantically similar answer, a token prefix, or the transformer's computed key-value state. These are not interchangeable. Each avoids different work and carries a different correctness boundary, so optimize expected outcome cost, not hit rate. In high-consequence workflows, one false semantic hit can erase thousands of cheap inference savings. key_takeaways: - Name the artifact being reused before selecting a cache. - Exact output caching is safest only when every decision-relevant input is in the key. - Semantic similarity is a retrieval signal, not proof that an old answer is valid. - Prefix and KV caching save prefill computation without freezing the generated answer. - Measure net value after lookup, memory, invalidation, staleness, and false-return costs. --- “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. ::figure{template=layers caption="The cache ladder reuses progressively lower-level artifacts" items="Exact output :: same key, same stored answer | Semantic output :: similar query, stored answer | Token prefix :: identical token sequence | KV state :: computed attention state | Fresh inference :: no reusable work"} ## 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: ```text 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: ```text 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. ::figure{template=flow caption="An exact-cache key must cover every answer-changing boundary" items="Request :: raw input | Canonicalize :: harmless variation only | Add identity :: tenant and authorization | Add versions :: data, policy, tools, model | Hash :: stable cache key | Reuse or infer :: audited decision"} An exact hit is not automatically fresh. Attach provenance and expiry to the value: ```json { "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](https://aclanthology.org/2023.nlposs-1.24/) 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](https://doi.org/10.48550/arXiv.2403.02694) 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: ```text 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](https://papers.nips.cc/paper_files/paper/2024/file/724be4472168f31ba1c9ac630f15dec8-Paper-Conference.pdf) 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. ::figure{template=branch caption="Shared token prefixes branch into fresh request-specific suffixes" items="System policy + tools :: cached tokens | Shared examples :: cached tokens | User A :: fresh suffix | Answer A :: fresh decode | User B :: fresh suffix | Answer B :: fresh decode | User C :: prefix changed, miss"} 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: ```text 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](https://doi.org/10.1145/3600006.3613165) 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](https://arxiv.org/abs/2406.17565), 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. ::figure{template=compare caption="A cache hit is useful only when avoided work exceeds reuse overhead" items="Local KV hit :: lookup + no transfer + saved prefill | Remote KV hit :: lookup + network transfer + saved prefill | Recompute :: local prefill + no cache dependency | Output hit :: lookup + policy check + no generation"} ## 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: ```text 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: ```text 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: ```text 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. ::figure{template=waterfall caption="Illustrative savings disappear when false semantic hits are costly" items="Baseline spend :: 400 | Exact savings :: -72 | Prefix savings :: -34.44 | Semantic savings :: -25.58 | Lookup + ops :: 22.26 | False-return loss :: 191.88 | Cached total :: 482.12"} The relevant denominator is cost per verified successful outcome, introduced in [Cost per Successful Outcome](/cost-per-verified-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: ```text 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](/from-prompt-to-proof) to the capacity model in [Capacity Is a Queue](/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](https://doi.org/10.1145/3600006.3613165), 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](https://papers.nips.cc/paper_files/paper/2024/file/724be4472168f31ba1c9ac630f15dec8-Paper-Conference.pdf), 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](https://arxiv.org/abs/2406.17565), Yao et al., 2024 preprint. Explores distributed context state, placement, and locality. - [GPTCache: An Open-Source Semantic Cache for LLM Applications](https://aclanthology.org/2023.nlposs-1.24/), Zeng et al., NLP-OSS 2023. Describes the semantic lookup and evaluator architecture. - [MeanCache: User-Centric Semantic Caching for LLM Web Services](https://doi.org/10.48550/arXiv.2403.02694), 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. ## FAQ ### What are the four main types of LLM cache? An exact output cache returns a stored answer for an equal canonical request. A semantic output cache returns an answer for a similar request. A prefix cache recognizes shared token prefixes to avoid repeated prefill. A KV cache stores transformer attention state so prior tokens are not recomputed. ### Is semantic caching safe for LLM applications? Only within a measured domain where hard identity, authorization, entity, version, and time filters accompany similarity, and where false-return consequences are acceptable. Similar embeddings do not prove that two queries deserve the same answer. ### What is the difference between prefix caching and semantic caching? Prefix caching requires identical token prefixes and reuses model computation while generating a fresh answer. Semantic caching searches for a meaning-near query and may reuse its final answer, which creates a larger correctness risk. ### When must an LLM KV cache be invalidated? Invalidate or segregate it when model weights, adapters, tokenizer, chat template, token sequence, positional behavior, attention configuration, or incompatible runtime representation changes. The safe identity depends on the actual engine. ### How should cache savings be calculated? Price the work each hit actually avoids, then subtract lookup, storage, transfer, invalidation, staleness, and expected false-return loss. Apply layers as a funnel because an earlier output hit prevents later cache opportunities. ### Can an LLM cache replay a tool action? It should not. Cache planning or explanatory artifacts separately from authorization and execution. Every side effect needs fresh validation, idempotency controls, and a real transaction result. ## Test yourself ### 1. Which cache normally produces a fresh decoded answer after a hit? - [ ] Exact output cache - [ ] Semantic output cache - [x] Prefix or KV cache - [ ] Browser cache **Explanation:** Prefix and KV reuse avoids prior computation while the request-specific suffix and answer still run. ### 2. Why is cosine similarity alone an incomplete semantic-cache policy? - [ ] It is always too slow - [x] It does not establish identity, authorization, time scope, or answer equivalence - [ ] It cannot compare text - [ ] It makes exact keys longer **Explanation:** Decision-relevant differences can remain even when embeddings are close. ### 3. Which change most clearly invalidates reusable KV state? - [ ] A dashboard color change - [x] A model-weight revision - [ ] A new cache metric - [ ] A lower network price **Explanation:** KV tensors are computed from the model and token sequence, so a weight revision changes their identity. ### 4. Why can a high semantic hit rate lose money? - [ ] Hits always generate more tokens - [x] False-return loss and lookup costs can exceed avoided inference - [ ] KV memory becomes free - [ ] Exact caching stops working **Explanation:** Expected value includes correctness consequences and operating costs, not just generation savings. ### 5. What is the safest first step for a semantic output cache? - [ ] Serve every nearest neighbor - [ ] Use one threshold for all intents - [x] Run shadow lookups and compare candidates with fresh verified answers - [ ] Remove tenant filters **Explanation:** Shadow evaluation estimates precision, coverage, savings, and failure classes without exposing users to false hits.