Randomized Cache Eviction for Unpredictable Workloads

20 concepts14 papers

Traditional caching strategies like Least Recently Used (LRU) or Least Frequently Used (LFU) operate on a fundamental assumption: the past predicts the future. If a data block was accessed recently, it will likely be accessed again soon. This deterministic heuristic works beautifully for standard workloads with strong temporal locality.

However, when systems face highly concurrent environments, non-linear data access patterns, or adversarial inputs designed to exploit predictable patterns, deterministic strategies suffer from catastrophic thrashing. Instead of building increasingly complex deterministic models to predict the future, a powerful alternative is to embrace uncertainty through randomized and stochastic cache replacement. By introducing controlled randomness into the eviction process, systems can break worst-case performance traps, preserve a more diverse historical sample of data, and drastically reduce the computational overhead of maintaining global cache states.

Defeating Adversarial Exploitation and Worst-Case Inputs

Why does determinism fail? Consider a cache of size $N$ managed by LRU, facing a cyclic request pattern of $N+1$ unique items. Every single request results in a cache miss, yielding a 0% hit rate. This is a classic example of a predictable blind spot. As noted by Persiano et al. (2015), deterministic eviction policies are highly vulnerable to adversarial input patterns that consistently trigger worst-case performance.

Randomization solves this by "smoothly" averaging decision boundaries. Algorithms like Follow-the-Perturbed-Leader (FTPL) inject noise into the decision-making process to obscure the cache's state from adversarial exploitation. As demonstrated by Bhattacharjee et al. (2020), this randomization prevents adversarial exploitation and maintains high hit rates even against non-stationary request patterns designed to force frequent evictions. Similarly, Ben Mazziane et al. (2023) show that introducing sampling noise prevents a cache from over-fitting to immediate history, allowing it to bypass the pitfalls of deterministic heuristics under repeating sequences.

This robustness is highly practical in modern high-throughput systems. For instance, in multi-LLM serving systems, Wu et al. (2026) introduced a randomized marking strategy (RLT) for Key-Value (KV) caching. By maintaining a set of recently accessed tokens and evicting an unmarked token uniformly at random, the system achieves theoretical robustness against adversarial query sequences that cause standard LRU policies to fail. In online learning contexts, Cavallanti et al. (2007) proved that a "Randomized Budget Perceptron"—which simply throws out a random old data point when memory is full—is theoretically optimal for tracking changing targets because randomness ensures the model does not develop predictable blind spots over time.

Preserving Temporal Diversity in Non-Linear Workloads

Deterministic heuristics like LRU assume strict temporal linearity: newer is always better. But what happens when a workload lacks historical repetition or exhibits non-linear behavior?

In specialized platforms like Highway Structural Health Monitoring, user queries for high-frequency sensor data are highly unpredictable. Qi et al. (2025) found that simple random replacement strategies actually outperform LRU in these environments. Because the data access patterns lack meaningful temporal locality, standard heuristics fail; a random strategy is more effective at maintaining a useful cache for overlapping data requests.

A similar phenomenon occurs in Peer-to-Peer (P2P) traffic tracking. P2P applications frequently request older data chunks non-linearly. Ye et al. (2009) demonstrated that random replacement strategies outperform FIFO or LRU because random eviction is far more likely to preserve a diverse temporal range of data blocks in memory, which is critical for identifying applications uploading older content.

When workloads feature a very high ratio of accessed pages, traditional locality-based policies break down. In tiered memory systems, Heo et al. (2020) leverage a random migration policy for precisely these scenarios, recognizing that they are fundamentally ill-suited for LRU or LFU. To prevent a system from getting locked into rigid historical patterns during sudden spikes in irregular content requests, Ye et al. (2007) proposed using a temperature-dependent probability function inspired by simulated annealing. This stochastic approach prevents the cache from converging on suboptimal local strategies and maintains system robustness during irregular traffic bursts.

Eliminating Coordination Overhead via Random Sampling

Beyond robustness, stochastic eviction offers massive computational advantages. In high-concurrency or distributed environments, maintaining a globally ordered list (such as an exact LRU queue) requires heavy synchronization, locking, or expensive network round-trips.

Instead of exhaustively searching for the absolute lowest-priority item to evict, systems can use random sampling as an approximation. As shown in Hyperbolic Caching by Blankstein et al. (2017), randomly sampling a small subset of items from the cache and evicting the lowest-priority item within that sample provides a highly effective approximation of global eviction policies while drastically reducing computational complexity.

This sampling-based approximation scales exceptionally well to distributed memory architectures. In the Ditto system, Shen et al. (2023) utilize client-centric random sampling of a small number of objects to identify eviction candidates. This mechanism completely bypasses the need to maintain a globally ordered list, eliminating coordination overhead and allowing system performance to scale linearly with the number of active clients while still achieving high hit rates.

Balancing Randomness and Structure

While randomness provides robustness and efficiency, it must be applied carefully. Completely blind randomness can sometimes destroy valuable structural shortcuts. For example, Ooi et al. (1999) observed that using pure random eviction for auxiliary database index structures can inadvertently remove frequently accessed shortcuts, increasing the frequency of expensive full-tree traversals.

Therefore, the most effective stochastic caching systems often combine probabilistic logic with structural constraints. In streaming multi-armed bandit problems with low-memory environments, Zhang et al. (2025) utilize a stochastic head-to-head eviction mechanism that compares an incoming item against a single randomly selected item currently in memory, discarding the loser. This allows continuous stream processing without large memory buffers. In probabilistic sampling frameworks, Pfeffer (2007) employs a specific probability to decide whether to reuse a cached result or perform a full re-computation, ensuring a continuous influx of fresh, independent data points to prevent the sampler from getting trapped in a biased state.

Key Foundational Work

An evolution-based cache scheme for scalable mobile data access (2007) — contributed 2 concept elements to this direction.
Sampling with Memoization (2007) — contributed 1 concept elements to this direction.
Tracking the best hyperplane with a simple budget Perceptron (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_cache_replacement_d0222d52,
  title = {stochastic cache replacement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-cache-replacement/rdr_d0222d52b39244789f3956917a102609},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_stochastic_cache_replacement_d0222d52_v1,
  title = {stochastic cache replacement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-cache-replacement/rdr_d0222d52b39244789f3956917a102609/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake