Caching › Cache Invalidation

Cache invalidation is famously described as one of the two hard problems in computer science, alongside naming things. In LLM systems, it is difficult because the relationship between a cached response and its continued validity is complex and often implicit.

A cached response was correct, or at least appropriate, when it was generated. It can become wrong for many reasons, and those reasons are not always visible from the cached response itself.

The underlying facts changed. If you cache the response "The current CEO of Company X is Alice Smith" and Alice Smith is replaced, the cached response is now factually wrong. External knowledge changes continuously and unpredictably. You cannot know in advance which cached responses depend on which facts.

The model changed. LLM providers update models regularly, sometimes changing behavior, safety policies, or output formatting conventions. A response cached under model version A may not be the response you would want from model version B. Model updates can change tone, verbosity, reasoning style, and safety thresholds in ways that make old cached responses look inconsistent with current behavior.

The context changed. A cached response that was appropriate for a certain user, time, or system state may not be appropriate when those conditions change. A system prompt updated to reflect a new product version should invalidate all cached responses that were generated under the old system prompt, because the instructions may now be different.

The user state changed. In personalized systems, a cached response tied to a user's preferences may become stale as the user's preferences evolve. A financial advisor bot that cached recommendations based on a user's risk tolerance should invalidate those recommendations if the user updates their risk profile.

These sources of staleness are fundamentally different from each other and require different invalidation strategies. There is no single mechanism that handles all of them correctly.

The simplest invalidation strategy is time-to-live (TTL): cached entries expire after a fixed duration. A TTL of 1 hour means no cached response is more than 1 hour old. This is easy to implement, requires no dependency tracking, and provides a clear guarantee to users about maximum response staleness.

The weakness of TTL-based invalidation is its bluntness. Stable information like mathematical definitions, historical facts, or fixed product descriptions could be cached indefinitely without staleness. Fast-changing information like stock prices, weather, or live event data should not be cached at all, or only for seconds. A fixed TTL either over-invalidates stable content (wasting cache capacity and adding unnecessary latency) or under-invalidates dynamic content (serving stale answers).

Tiered TTLs address this by assigning different expiration times to different content types. A system might use a 24-hour TTL for factual knowledge base responses, a 1-hour TTL for product information, and a 5-minute TTL for pricing or availability data. Implementing tiered TTLs requires your caching logic to know something about the content type of each response, either by tagging responses at generation time or by classifying them based on the query type.

The right TTL values are empirical. You should measure how quickly information in your domain changes, then set TTLs to be some fraction of that typical change interval. Setting a TTL based on intuition without measurement often results in either overly conservative (frequent re-computation) or overly aggressive (stale responses) caching behavior.

Event-based invalidation ties cache expiration to specific events rather than elapsed time. When the system prompt changes, all cached responses generated under the old system prompt are immediately invalidated. When a knowledge base is updated, all cached responses that might have drawn on the changed content are invalidated.

Event-based invalidation is more precise than TTL and avoids serving stale responses during the window between a change event and the next TTL expiration. If you deploy an updated system prompt at noon and your TTL is 1 hour, you could serve stale responses for up to an hour. With event-based invalidation, the old responses are invalidated at noon immediately.

But it requires the caching system to track dependencies: which cached responses were generated under which system prompt version, using which knowledge base version, and so on. This dependency graph can become complex. A response might have been generated under system prompt version 3, using knowledge base documents 17, 42, and 91. Updating document 42 should invalidate that cached response, but tracking this at response granularity requires recording which documents each response depended on at generation time.

Dependency tracking adds implementation complexity that many teams find difficult to justify. One practical simplification is cache versioning: include a cache version identifier in every cache key. When the system prompt or other shared state changes, increment the version. All previous cache entries automatically become unreachable because their keys no longer match, achieving a complete cache flush for the changed component without needing to track individual dependencies.

Version-key invalidation is essentially a full flush for the affected component. Every entry generated under the old version becomes unreachable at once, and the cache must rebuild from scratch for that component. This is clean and correct, but it sacrifices the warmth of all entries that were not affected by the change. If only 5% of your responses depended on the changed document, version flushing invalidates the other 95% unnecessarily.

When a change occurs, you have two options: invalidate only the entries likely affected by the change, or flush the entire cache and rebuild from scratch.

Full flush is simple and guaranteed correct. It is appropriate when the change is pervasive (such as a major model upgrade or a system-wide policy update) or when you cannot reason about which entries are affected. The cost is a cold cache immediately after the flush, with degraded hit rates until the cache warms up again. The warmup period can take hours or days depending on traffic volume, and during this period users experience full inference latency.

Partial invalidation is more efficient but requires careful reasoning about scope. If a specific FAQ article is updated, you might invalidate only the cached responses to questions about that article. This preserves cache warmth for unaffected queries. But if your invalidation logic is wrong and you miss some affected entries, you will serve stale responses for those queries, which is the failure mode you were trying to avoid by caching selectively.

The choice between full flush and partial invalidation should be governed by the expected scope of changes and your tolerance for serving stale responses. For infrequent, broad changes (model upgrades), full flush is safer. For frequent, narrow changes (individual document updates), partial invalidation pays off.

Semantic caches present an additional invalidation challenge that does not exist in exact-match caches. In an exact-match cache, you can invalidate a specific entry by its key. In a semantic cache, entries are matched by embedding similarity, not by a deterministic key. You cannot easily invalidate "all responses that might have discussed topic X" without searching the embedding space for entries near the topic's embedding.

This asymmetry creates a subtle problem. Suppose a company updates its product pricing policy. In an exact-match cache, you could search for entries whose keys contain the word "pricing" and remove them. In a semantic cache, you would need to embed a query like "product pricing policy", search for all cache entries with similarity above some threshold, and remove them. But this operation itself requires a similarity search that may be slow and may have recall errors: some relevant entries may not be found if their embeddings are below the search threshold.

One practical approach is to maintain a side index that maps semantic topics or document IDs to the cache entries that might depend on them. At cache store time, you classify the response by topic (automatically, using the LLM itself to tag the response) and add the entry ID to the topic's index. When a topic changes, you use the index to find and invalidate the relevant cache entries. Building and maintaining this index requires careful design but makes targeted invalidation tractable.

A simpler approach is to accept full flush as the invalidation strategy for semantic caches, while investing in fast cache warming to minimize the cold period. If your semantic cache can be warmed to 60% hit rate within 30 minutes of a flush (by replaying recent query logs), the cost of periodic full flushes may be acceptable.