Negative Caching

Negative caching stores a sentinel value—a special object representing 'not found'—rather than simply omitting the key. This distinguishes between 'I looked and found nothing' and 'I haven't looked yet'. In LLM pipelines, this prevents repeated semantic searches for non-existent documents.

• Sentinel TTL: Typically shorter than positive cache TTLs (e.g., 60 seconds vs. 300 seconds) to allow for eventual data arrival
• Memory efficiency: A single sentinel object can represent millions of missing keys
• Example: A vector store returns null for an embedding query; the negative cache stores {query_hash: NOT_FOUND} to short-circuit identical future requests

Without negative caching, a popular query for a non-existent resource triggers a cache stampede: every concurrent request bypasses the empty cache and slams the origin database or model endpoint. Negative caching absorbs this pressure.

• Thundering herd mitigation: The first request discovers the absence and populates the negative entry; subsequent requests receive the cached 'empty' response
• Backend protection: Prevents denial-of-service conditions caused by repeated expensive lookups for invalid keys
• Real-world scenario: A user searches for a product SKU that doesn't exist; without negative caching, every search hits the inventory database

Negative caching is often implemented alongside Bloom filters—probabilistic data structures that can definitively say 'this key does not exist' with zero false negatives. Before querying the cache or backend, the system checks the Bloom filter.

• Zero false negatives: If the filter says 'absent,' the key is guaranteed absent—no need to query further
• Controlled false positives: The filter may occasionally say 'present' for an absent key (typically 1-3%), requiring a fallback lookup
• Memory footprint: A Bloom filter for 1 billion keys requires only ~1.7 GB with a 1% false positive rate

Beyond 'not found,' negative caching extends to transient error states. When an upstream model endpoint returns a 503 or timeout, caching that failure prevents cascading retries that compound the outage.

• Circuit breaker synergy: The cached error response allows the circuit breaker to fail fast without probing the degraded backend
• Graceful degradation: Serve a stale positive result or a cached 'temporarily unavailable' message instead of propagating raw errors
• TTL considerations: Error cache TTLs should be short (5-30 seconds) with exponential backoff on repeated failures

In air-gapped or geofenced environments, negative caching prevents wasteful cross-boundary lookups. If a document is confirmed absent from a local vector store, the negative cache ensures no request escapes the sovereign perimeter to check external sources.

• Data residency compliance: Negative entries confirm that data was not found locally, preventing unauthorized external queries
• Bandwidth conservation: In disconnected or low-bandwidth environments, eliminating redundant 'miss' lookups preserves scarce network resources
• Audit trail: Negative cache hits provide cryptographic proof that a lookup was performed and returned empty, supporting compliance reporting

Negative entries require distinct eviction policies from positive entries. A newly ingested document should immediately invalidate any negative cache entry for its key, while LRU eviction may prematurely discard critical 'not found' sentinels.

• Event-driven invalidation: Database write events trigger targeted removal of corresponding negative entries
• Shorter default TTLs: Negative entries typically expire faster (30-120 seconds) to balance protection against staleness
• Priority inversion risk: Under memory pressure, evicting negative entries can cause a sudden spike in backend load—consider pinned negative entries for high-traffic missing keys

A space-efficient probabilistic data structure used to test whether an element is a member of a set. In caching, it enables rapid key existence checks before performing expensive lookups.

• Guarantees no false negatives — if it says an item is absent, it definitely is
• Allows a controllable false positive rate
• Ideal for pre-filtering negative cache keys to avoid wasted disk I/O

The deterministic algorithm that decides which entries to remove when a cache reaches its memory capacity. It balances hit rate against resource constraints.

• LRU (Least Recently Used): Discards the oldest accessed item first
• LFU (Least Frequently Used): Removes items with the lowest access count
• TTL-based: Evicts entries after a fixed duration regardless of access patterns

Negative cache entries often use aggressive TTLs to prevent stale error states from persisting.

A cascading failure scenario where a popular cache entry expires, causing a flood of concurrent requests to simultaneously hit the origin model or database.

• Can overwhelm backend infrastructure within milliseconds
• Mitigated by probabilistic early recomputation or request coalescing
• Negative caching amplifies this risk — a single expired 'not found' entry can trigger a stampede of expensive validation lookups

A stability pattern that automatically stops sending requests to a failing cache backend or model endpoint, immediately failing fast to prevent cascading latency and resource exhaustion.

• Three states: Closed (normal), Open (failing fast), Half-Open (testing recovery)
• Prevents negative cache backends from being hammered during outages
• Essential for sovereign deployments where failover paths may be limited

A resilience strategy where the system serves stale cached data or a static fallback response when the primary inference backend is unavailable.

• Maintains basic functionality during partial outages
• Negative caches can serve cached error states while backends recover
• Critical for air-gapped environments where external fallback APIs are unreachable