LeCaR (Learning Cache Replacement)

Goal

Adapt eviction behavior online by learning when recency-focused or frequency-focused decisions work better for the current workload.

Core Idea

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.

Core Data Structures (Typical)

• 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)

Complexity & Overhead

• Extra per-operation arithmetic for weight updates
• More metadata than single-policy designs
• Performance depends on stable, well-tuned feedback signals

Notes For CacheKit

• 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.

References

• Vietri et al. (2018): “Driving cache replacement with ML-based LeCaR”, NSDI 2018.
• Wikipedia (taxonomy context): https://en.wikipedia.org/wiki/Cache_replacement_policies