# An Imitation Learning Approach for Cache Replacement

arXiv: https://arxiv.org/abs/2006.16239 · HTML: https://mlsanity.com/paper/2006.16239/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 24 of 24)

- [Imitation Learning: Progress, Taxonomies and Challenges](https://mlsanity.com/paper/2106.12177/) (2021)
- [Ginex: SSD-enabled Billion-scale Graph Neural Network Training on a Single Machine via Provably Optimal In-memory Caching](https://mlsanity.com/paper/2208.09151/) (2022)
- [Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning](https://mlsanity.com/paper/2109.12021/) (2021)
- [SCALM: Towards Semantic Caching for Automated Chat Services with Large Language Models](https://mlsanity.com/paper/2406.00025/) (2024)
- [Robust Learning-Augmented Caching: An Experimental Study](https://mlsanity.com/paper/2106.14693/) (2021)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Sibyl: Adaptive and Extensible Data Placement in Hybrid Storage Systems Using Online Reinforcement Learning](https://mlsanity.com/paper/2205.07394/) (2022)
- [Giving Feedback on Interactive Student Programs with Meta-Exploration](https://mlsanity.com/paper/2211.08802/) (2022)
- [ArchAgent: Agentic AI-driven Computer Architecture Discovery](https://mlsanity.com/paper/2602.22425/) (2026)
- [A Learning-Based Caching Mechanism for Edge Content Delivery](https://mlsanity.com/paper/2402.02795/) (2024)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [Toward Robust and Efficient ML-Based GPU Caching for Modern Inference](https://mlsanity.com/paper/2509.20979/) (2025)
- [On a Foundation Model for Operating Systems](https://mlsanity.com/paper/2312.07813/) (2023)
- [Ranking-based Client Selection with Imitation Learning for Efficient Federated Learning](https://mlsanity.com/paper/2405.04122/) (2024)
- [IBCB: Efficient Inverse Batched Contextual Bandit for Behavioral Evolution History](https://mlsanity.com/paper/2403.16075/) (2024)
- [A Bring-Your-Own-Model Approach for ML-Driven Storage Placement in Warehouse-Scale Computers](https://mlsanity.com/paper/2501.05651/) (2025)
- [Harmonia: Enhancing Data Placement and Migration in Hybrid Storage Systems via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.20507/) (2025)
- [Athena: Synergizing Data Prefetching and Off-Chip Prediction via Online Reinforcement Learning](https://mlsanity.com/paper/2601.17615/) (2026)
- [Analyzing a Caching Model](https://mlsanity.com/paper/2112.06989/) (2021)
- [Machine Learning-Driven Intelligent Memory System Design: From On-Chip Caches to Storage](https://mlsanity.com/paper/2603.14583/) (2026)
- [SCION: Size-aware Policy Orchestration for Nonstationary Object Caches (Long Paper Version)](https://mlsanity.com/paper/2605.01055/) (2026)
- [Memory as a Wasting Asset: Pricing Flash Endurance for Embodied Agents, and the Limits of Doing So](https://mlsanity.com/paper/2606.18144/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

Program execution speed critically depends on increasing cache hits, as cache hits are orders of magnitude faster than misses. To increase cache hits, we focus on the problem of cache replacement: choosing which cache line to evict upon inserting a new line. This is challenging because it requires planning far ahead and currently there is no known practical solution. As a result, current replacement policies typically resort to heuristics designed for specific common access patterns, which fail on more diverse and complex access patterns. In contrast, we propose an imitation learning approach to automatically learn cache access patterns by leveraging Belady's, an oracle policy that computes the optimal eviction decision given the future cache accesses. While directly applying Belady's is infeasible since the future is unknown, we train a policy conditioned only on past accesses that accurately approximates Belady's even on diverse and complex access patterns, and call this approach Parrot. When evaluated on 13 of the most memory-intensive SPEC applications, Parrot increases cache miss rates by 20% over the current state of the art. In addition, on a large-scale web search benchmark, Parrot increases cache hit rates by 61% over a conventional LRU policy. We release a Gym environment to facilitate research in this area, as data is plentiful, and further advancements can have significant real-world impact.