Adapt eviction behavior online by learning when recency-focused or frequency-focused decisions work better for the current workload.
LeCaR treats eviction as a lightweight online-learning problem:
- Keep two experts (commonly LRU-like and LFU-like signals).
- Maintain weights for each expert based on recent regret/reward.
- On eviction pressure, pick victims according to the weighted mixture.
Under shifting workloads, weights move toward the better-performing strategy.
- Hash index
K -> EntryMeta - Recency structure (LRU list or clock-style metadata)
- Frequency counters (or compact approximate counters)
- Learning state (expert weights, step size, recent feedback)
- Extra per-operation arithmetic for weight updates
- More metadata than single-policy designs
- Performance depends on stable, well-tuned feedback signals
- Best viewed as a research/benchmark policy before production defaulting.
- Keep learning state compact and avoid floating-point work in hot loops if possible.
- Evaluate under non-stationary workloads with hotspot shifts.
- Vietri et al. (2018): “Driving cache replacement with ML-based LeCaR”, NSDI 2018.
- Wikipedia (taxonomy context): https://en.wikipedia.org/wiki/Cache_replacement_policies