Cache Thrashing

Thrashing occurs when the working set—the collection of entries actively being accessed—is larger than the cache capacity. Every new request forces an eviction of an entry that will be needed again almost immediately. The cache hit ratio collapses toward 0%, yet the system incurs the full overhead of cache lookups, eviction processing, and reloading from the origin. This creates a negative net benefit: the cache makes the system slower than having no cache at all.

The primary trigger is a mismatch between cache size and access patterns. Key scenarios include:

• Rapid context switching between many distinct inference contexts that collectively exceed memory
• Highly random access patterns with low temporal locality, where entries are accessed once and never again
• Cache pollution from one-shot queries that displace frequently reused entries
• Memory pressure from the host system forcing the cache process to swap, compounding latency

A healthy cache experiences compulsory misses (first access) and capacity misses (working set near limit). Thrashing is distinct: it is a non-linear phase transition where the miss rate suddenly spikes as the working set crosses the capacity threshold. Unlike normal operation where increasing cache size improves hit rate, a thrashing cache may show zero improvement from small size increases until the working set fits entirely. The system exhibits high CPU utilization with low throughput—a classic thrashing signature.

Identify thrashing through these telemetry signals:

• Hit ratio drops below 20% and continues declining under steady load
• Eviction rate spikes dramatically while the cache size remains at maximum
• Average TTL of evicted entries drops to seconds or milliseconds—entries are evicted before they can be reused
• Origin load increases to near-direct-access levels despite the cache layer being present
• P99 latency increases due to the combined cost of cache miss + eviction + reload

Resolving thrashing requires structural changes:

• Increase cache memory to exceed the working set size, moving past the phase transition point
• Implement cache tiering with a larger, slower secondary cache to absorb the working set overflow
• Apply admission policies that reject caching for one-hit-wonder entries, preventing cache pollution
• Use probabilistic eviction like TinyLFU that estimates entry frequency to protect frequently accessed items
• Partition the cache by tenant or query type to isolate thrashing workloads from stable ones

In sovereign deployments with fixed, pre-provisioned hardware, thrashing is especially dangerous because elastic scaling is restricted. An air-gapped GPU cluster cannot burst to cloud resources. Mitigation must be proactive:

• Workload characterization before deployment to right-size cache allocations
• Circuit breakers that detect thrashing and temporarily bypass the cache to serve directly from the model, preserving throughput at the cost of latency
• Semantic cache compaction using Product Quantization to fit more embeddings in the same memory footprint

The deterministic algorithm that decides which entries to remove when a cache reaches its memory capacity. A poorly chosen policy is the primary cause of thrashing.

• LRU (Least Recently Used): Discards the oldest access; vulnerable to thrashing when working sets exceed cache size.
• LFU (Least Frequently Used): Tracks access frequency; resists one-hit-wonder pollution but adapts slowly.
• ARC (Adaptive Replacement Cache): Balances recency and frequency, self-tuning to resist sequential scan thrashing.
• TinyLFU: Uses a compact sketch to estimate frequency with minimal memory, ideal for high-throughput semantic caches.

The set of unique cache keys actively accessed within a given time window. Thrashing begins when the working set size sustainably exceeds the allocated cache capacity.

• Denning's Working Set Model: Defines the working set as pages referenced in the last Δ time units; directly applicable to cache key access patterns.
• HyperLogLog Sketching: A probabilistic data structure that estimates unique key cardinality with ~2% error using only ~1.5KB of memory.
• Miss Ratio Curves (MRC): Profiles how hit rate changes with cache size; identifies the cliff edge where thrashing begins.
• Monitoring the gap between working set size and cache capacity provides early warning before performance collapses.

A cascading failure where a popular cache entry expires, causing a flood of concurrent requests to simultaneously hit the origin model. While distinct from thrashing, stampedes can trigger thrashing-like symptoms by overwhelming the backend.

• External Recompute: Multiple clients independently detect expiration and each recompute the value.
• Probabilistic Early Expiration: Artificially expires hot keys early with a probability proportional to their popularity, allowing one request to refresh while others use stale data.
• XFetch Algorithm: Computes optimal recomputation time using delta * beta * log(rand()) where delta is time-to-recompute and beta controls the refresh window.
• Stampede-induced latency spikes can mimic thrashing in observability dashboards; distinguish by checking concurrent miss counts.

A stability pattern that automatically stops sending requests to a failing cache backend or model endpoint when error rates exceed a threshold. Prevents thrashing from cascading into total system failure.

• Closed State: Normal operation; requests flow to the backend.
• Open State: Requests immediately fail fast without touching the backend; a cooldown timer prevents retries.
• Half-Open State: A limited number of probe requests test if the backend has recovered before fully closing the circuit.
• In sovereign inference caches, circuit breakers protect GPU clusters from being overwhelmed when thrashing causes repeated cache misses against the origin model.

A multi-level storage strategy that places the hottest, most frequently accessed data in fast, expensive memory while demoting cooler data to slower, cheaper storage. Mitigates thrashing by expanding effective capacity without linear cost.

• L1 (Hot): In-memory cache (e.g., Redis, Memcached) with microsecond latency; holds the active working set.
• L2 (Warm): Local SSD-backed cache (e.g., NVMe) with sub-millisecond latency; holds the extended working set.
• L3 (Cold): Object storage or distributed cache with higher latency; holds long-tail entries.
• Promotes entries to L1 on access; demotes based on frequency decay. Prevents thrashing by absorbing working set overflow into lower tiers rather than evicting hot entries.

A resilience strategy where the system serves stale cached data or a static fallback response when the primary inference backend is unavailable. Essential for maintaining availability during thrashing-induced backend overload.

• Stale-While-Revalidate: Serve expired cache entry immediately while asynchronously refreshing in the background.
• Static Fallback: Return a pre-computed default response when no cache entry exists and the backend is unreachable.
• Soft TTL vs Hard TTL: Soft TTL triggers background refresh; hard TTL is the absolute expiration after which entries are never served.
• In sovereign deployments, graceful degradation ensures air-gapped systems remain operational even when model servers are under duress from thrashing workloads.