Reproduce “An Imitation Learning Approach for Cache Replacement” on OpenResearch

About this paper

Evan Zheran Liu, Milad Hashemi, Kevin Swersky, Parthasarathy Ranganathan, Junwhan Ahn

PARROT, an end-to-end imitation learning framework, learns cache replacement policies by approximating Belady's optimal algorithm. This approach achieved 16% higher average raw cache hit rates than LRU on SPEC CPU2006 benchmarks and a 13.5% improvement on a Google Web Search benchmark, outperforming prior learning-based methods and demonstrating effective generalization.

Key insights

• An end-to-end imitation learning approach can effectively approximate Belady's optimal cache replacement policy, significantly closing the performance gap left by heuristic-based and hybrid learning methods.
• Integrating fine-grained supervision signals, such as reuse distances through a differentiable ranking loss and an auxiliary prediction task, is crucial for learning more robust and informative representations for eviction decisions.
• On-policy training with the DAgger algorithm is vital for addressing the distribution shift inherent in imitation learning for cache replacement, ensuring the learned policy performs well in real-world scenarios.

Summary by alphaXiv.