PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning-Augmented Heuristics: Simple, yet Smart, Robust and Interpretable Cache Eviction

Haocheng Xia, William Nixon, Bintang Dwi Marthen, Pranav Bhandari, Juncheng Yang

arXiv:2608.27975v1cs.DC

TL;DR

Existing smart caches can mismatch the miss-ratio objective and become unstable or costly, motivating a simpler adaptive approach. The paper introduces LAH, which learns cache-level parameters for static heuristics through separated data and control planes, and realizes it as S4-FIFO. Evaluated on 1,035 production traces, S4-FIFO achieves higher average miss-ratio reduction and stronger robustness than state-of-the-art algorithms while matching heuristic throughput.

  • Problem

    Existing smart caches can suffer objective mismatch, instability, and overhead, while static heuristics leave performance headroom on tail traces.

  • Method

    LAH uses a pre-trained model and cache-level features to configure a simple static heuristic through separate data and control planes; S4-FIFO applies this design to S3-FIFO.

  • Results

    S4-FIFO achieves higher average miss-ratio reduction and stronger robustness than state-of-the-art algorithms on 1,035 production traces while matching heuristic throughput.

  • Takeaways & Limitations

    Learning to configure expressive heuristics can preserve a simple data path while improving efficiency and robustness.

  • Takeaways & Limitations

    Extending LAH to other policies requires policy-specific feature engineering and is beyond this work’s scope.

Abstract

from arXiv · show

Caching is widely used across the system stack to improve performance and efficiency, with eviction algorithms at its core. Existing cache eviction policies fall into two broad categories: static heuristics (e.g., 2Q, S3-FIFO) and smart algorithms (e.g., ARC, LRB). Smart caches can adapt to workloads and have the potential to achieve higher efficiency and robustness than static heuristics. However, we find that existing smart caches suffer from objective mismatches and instability. We introduce Learning-Augmented Heuristics (LAH), a framework that learns the cache-level parameters of static heuristics. By decoupling the data and control planes, LAH supports simple, high-speed data reads and writes on the data plane, while performing occasional asynchronous learning on the control plane using cache-level features. We demonstrate the effectiveness of LAH through S4-FIFO, a Smart S3-FIFO cache eviction algorithm. We pre-train a single model on 4,140 production traces and embed it in S4-FIFO to learn optimal cache parameters. On 1,035 evaluation traces, S4-FIFO improves the mean efficiency by 26% compared to S3-FIFO and by 8% compared to 3L-Cache, the best state-of-the-art algorithm. S4-FIFO is also robust---increasing miss ratio over FIFO by 0.8% on the worst trace, whereas 3L-Cache increases FIFO's miss ratio by 8.8%. Finally, S4-FIFO's decisions are also interpretable: a language model can provide a rationale for why a particular configuration was chosen.

1 Introduction

Caching systems rely on eviction algorithms to retain objects under tight memory budgets, while smart caches seek workload adaptation but face objective mismatch, instability, and overhead. The paper introduces LAH and S4-FIFO to learn configurations for simple heuristics, targeting efficiency and robustness.

  • Motivation: Static heuristics remain widely used because they are simple, fast, and easy to deploy.Examples include LRU, 2Q, S3-FIFO, and SIEVE.
  • Motivation: Smart caches often learn per-object predictions on every miss using surrogate objectives instead of directly optimizing miss ratio.These designs can suffer objective mismatch, instability, metadata and inference overhead, and runtime complexity.
  • Motivation: S3-FIFO filters one-hit wonders and retains popular objects, yet its static configuration leaves substantial headroom on tail traces.Its mean and median performance is strong, but the analysis identifies weaker tail-trace behavior.
  • Gap: Periodic cache-level learning is an unexplored quadrant that can directly learn cache parameters to optimize miss ratio.The paper classifies algorithms by learning granularity and prediction frequency.
  • Approach: LAH separates a deterministic heuristic data plane from an asynchronous control plane that uses cache-level features to select configurations.A single model is pre-trained offline and reused for zero-shot prediction without per-deployment retraining.
  • Approach: S4-FIFO realizes LAH by exposing S3-FIFO control knobs and using a lightweight gradient-boosted model to choose among representative configurations.The model is trained on 4,140 production traces spanning block, key–value, and CDN caches.

2 Background and Motivations

Smart cache eviction algorithms adapt to workloads, but existing designs face objective mismatch, unpredictability, instability, delayed rewards, and substantial overheads. The paper identifies periodic cache-level learning as a gap and proposes configuring simple heuristics using global parameters aligned with miss-ratio reduction.

  • Smart Cache Eviction Algorithms: Static heuristics are valued for simplicity, high throughput, and easy implementation, while adaptive and learning-based policies aim to tailor eviction decisions to workloads.
  • Challenges of Smart Caches: Object-level learning can optimize proxy metrics such as reuse-distance loss without reducing cache misses, creating an objective mismatch with miss-ratio minimization.
  • Challenges of Smart Caches: Object-level metrics are workload-dependent and noisy, especially for one-hit wonders, making predictions sensitive and eviction decisions less robust and interpretable.
  • Learning-Augmented Heuristics: Cache-level learning improves interpretability because parameter changes correspond to operational actions such as resizing queues or adjusting expert weights.
  • Challenges of Smart Caches: Per-miss learning can chase fine-grained workload noise, suffer delayed and ambiguous rewards, and reduce throughput through repeated inference and per-object metadata.LRB adds over 200 bytes of features to each object.
  • Challenges of Smart Caches: Periodic object-level prediction can become stale as object usefulness changes, leading to lower efficiency when reused scores guide eviction.
  • Learning-Augmented Heuristics: The paper identifies periodic cache-level learning as an unexplored design-space quadrant that directly learns global parameters for miss-ratio reduction while avoiding unnecessary overfitting to noise.

3 Learning-Augmented Heuristics (LAH)

Learning-Augmented Heuristics separates deterministic cache data-path execution from asynchronous, infrequent control-plane learning that selects heuristic parameters from cache-level features. The framework targets efficiency, robustness, and interpretability while preserving lightweight cache operations.

  • Learning-Augmented Heuristics: LAH separates a deterministic, parameterized heuristic on the data plane from asynchronous control-plane learning that selects cache parameters.The control plane uses cache-level features and targets miss-ratio reduction without embedding complex learning logic in the critical path.
  • Learning-Augmented Heuristics: Asynchronous inference keeps the critical path for GET and PUT operations lightweight, supporting high throughput and low tail latency.The data-path logic remains simple and deterministic with minimal metadata overhead and fewer complex data structures.
  • Learning-Augmented Heuristics: LAH automatically optimizes configurations for different workloads by identifying golden configurations during cache warm-up and updating parameters accordingly.This provides workload-specific efficiency while retaining a simple static heuristic structure.
  • Learning-Augmented Heuristics: LAH uses aggregated cache metrics to map workload signals to a small set of heuristic parameters with clear operational meaning.This shared cache-centric representation makes configurations more interpretable than existing alternatives.
  • Learning-Augmented Heuristics: S4-FIFO transforms S3-FIFO into a learning-augmented heuristic by exposing and augmenting its internal parameters to a foundation model.S3-FIFO is used because it is simple, performant, and scalable.

4 S4-FIFO Design and Implementation

S4-FIFO augments S3-FIFO with tunable queue and promotion parameters, then uses cache-level features and asynchronous learning to select workload-specific configurations. Its design combines a deterministic O(1) data path with lightweight, infrequent model inference.

  • Heuristic augmentation: S4-FIFO adds a burst-aware parameter that virtually partitions S3-FIFO’s small queue into an additional FIFO region.This increases the heuristic’s flexibility without adding a fourth physical FIFO queue.
  • Parameter prediction: The offline-trained model makes a single asynchronous prediction after online feature collection, then S4-FIFO switches from default to predicted parameters.Feature collection and prediction occur after startup; queue resizing is lazy when a predicted configuration reduces a queue’s target size.
  • Parameters: S4-FIFO learns queue sizes, promotion thresholds, and a skip ratio to adapt filtering and promotion behavior to workload characteristics.The tunable parameters include small- and ghost-queue sizes, two promotion thresholds, and the skip ratio.
  • Learning objective: S4-FIFO models parameter selection as classification over a finite set of candidate configurations using workload features.The model learns P(y = c_j|x;φ) and predicts the configuration for an unseen workload.
  • Learning objective: A data-driven cost matrix captures asymmetric pairwise regret, normalized by FIFO’s miss ratio to anchor robustness across workloads.The cost matrix penalizes selecting configuration c_k when c_j is optimal, while FIFO normalization supports learning across traces with different cacheability.
  • Overhead analysis: All cache reads, writes, and evictions remain O(1), while asynchronous inference takes less than 2 ms and does not affect request serving.Feature collection uses mostly existing counters plus one O(1) histogram update; model inference costs O(T ·D).

5 Evaluation

The evaluation shows that S4-FIFO improves efficiency and robustness over static and learned baselines while retaining heuristic-level throughput and interpretable cache-level decisions.

  • Efficiency: S4-FIFO’s retrospective variant consistently outperforms its online variant, showing that predicted parameters improve efficiency while the observation window explains their performance gap.The retrospective variant applies predicted parameters to the entire trace, isolating learned-configuration quality from observation-window cost.
  • Efficiency: 26% higher miss ratio reduction than S3-FIFO and 8% higher reduction than 3L-Cache were achieved at the large cache size.At small cache sizes, S4-FIFO is slightly worse than 3L-Cache but remains substantially better than other state-of-the-art algorithms; 3L-Cache is 17.3× slower on average.
  • Robustness: 0.8% and 0.2% increases over FIFO were observed on S4-FIFO’s worst trace at large and small cache sizes, respectively.On the 10th-percentile trace, S4-FIFO instead reduces FIFO’s miss ratio by 4.2% and 3.6%.
  • Throughput: S4-FIFO sustains throughput comparable to conventional heuristics by extracting features outside the critical section and performing infrequent asynchronous inference.This avoids the critical-path inference and online-training costs typical of learned caches.
  • Why Learning Works: Learned parameters remain close to the best configuration across traces, whereas default parameters span substantially worse ranks.Queue hit-distribution histograms account for 75% of feature importance, making workload locality the strongest prediction signal.
  • Generalization: Prediction accuracy increases monotonically with more training traces, supporting the use of a single pre-trained model across workloads.The cited evaluation measures top-1, top-2, and top-3 accuracy.
  • Interpretability: 83% and 86% accuracy were achieved by LLMs distinguishing better configurations for small- and large-cache settings, respectively.The authors treat this as evidence that the feature and parameter spaces are semantically meaningful, not as proof of policy correctness.

6 Related Work

The related work spans machine-learning integrations that replace mechanisms, optimize policies, or tune external parameters, alongside cache-eviction algorithms targeting efficiency.

  • Optimizing Cache Efficiency: Cache-efficiency research includes static heuristics, per-miss cache-level adaptive algorithms, and object-level learning algorithms.The paper positions LAH as learning heuristic parameters while separating control and data-serving planes.
  • Machine Learning for Systems: Machine-learning systems research distinguishes structural replacement, policy optimization, and parameter tuning as three integration levels.Examples include learned indexes and bloom filters, reinforcement-learning-based admission, and tuning external knobs.

7 Conclusion

LAH keeps the cache data path simple while using a pre-trained model to configure semantic knobs. In S4-FIFO, this approach improves average efficiency and robustness while matching heuristic throughput, and supports interpretable decisions.

  • S4-FIFO uses a pre-trained model to configure a few semantic knobs while keeping the cache data path simple.
  • S4-FIFO achieves higher average miss-ratio reduction and stronger robustness than state-of-the-art algorithms while matching heuristic throughput.
  • Learning to configure expressive heuristics is presented as an effective and interpretable way to bring ML into core caching systems.

A.1 Pre-training Workflow

S4-FIFO uses an offline foundation-model workflow: collect cache-level features, label configurations by future miss ratio, train a classifier, and apply predicted parameters during serving.

  • S4-FIFO uses a foundation-model approach that pre-trains a model offline on a diverse corpus of traces.
  • Trace simulation & feature collection: Feature collection simulates S4-FIFO with default parameters, warms the cache to capacity, and exports monitored features every 20% of trace requests.
  • Oracle labeling: Exhaustive parameter-grid simulation labels each epoch with the lowest-miss-ratio configuration and computes regret for every candidate class.
  • Supervised training: A LightGBM gradient-boosted decision-tree classifier is trained on feature-label pairs using multi-class log-loss over diverse workloads.
  • Request Serving: After prediction, the system decodes new tuned parameters and applies them through S4-FIFO configuration interfaces.

A.2 Model Interpretability

S4-FIFO’s configuration choices can be explained from cache-level workload features. The examples connect one-hit ratios, cache pressure, burstiness, working-set size, and hit distributions to queue and promotion settings.

  • Workload 1: A high one-hit ratio and small cache ratio lead the model to choose a small small queue and low promotion threshold.These settings aggressively filter one-hit objects while promoting rare reusable objects quickly.
  • Workload 2: Burstiness and a large effective working set lead the model to expand the small queue, raise the promotion threshold, and increase skip behavior.The configuration absorbs bursts, limits burst pollution of the main queue, and ignores noisy early hits.

A.2.1 Feature-Label Reasoning Prompt

The feature-label reasoning prompt builds on S3-FIFO’s queue and ghost-history mechanisms and asks for explicit explanations linking workload features to each tunable parameter.

  • S3-FIFO background: S3-FIFO uses FIFO queues instead of complex recency or frequency structures, filtering one-hit objects through a small queue before longer-term storage in a main queue.
  • S3-FIFO background: A ghost queue stores metadata for recently evicted objects and can bypass probation when those objects reappear.
  • Tunable parameters: The prompt covers parameters controlling small-queue size, ghost-queue size, and promotion behavior through thresholds and related knobs.
  • Feature-label reasoning prompt: For each parameter, the requested response explains how features support the selected setting and ends with a concise feature-based takeaway.

A.2.2 Prompt for Pairwise Configuration-Selection Evaluation

The evaluation prompt asks a language model to select the more appropriate of two randomly labeled S4-FIFO configurations for measured workload features and briefly justify its choice. It provides context on S4-FIFO’s queues, tunable parameters, and workload-feature interpretation.

  • The model receives measured workload features and two candidate S4-FIFO configurations, then selects the more appropriate option and briefly justifies the decision.
  • S4-FIFO uses SMALL to filter one-hit wonders, MAIN for long-residency storage, and GHOST metadata to promote returning objects directly to MAIN.
  • The s_param knob controls the SMALL-queue fraction: lower values intensify filtering for scan-heavy workloads, while higher values retain more recently accessed objects.
  • Histogram interpretation links front-heavy distributions to short reuse distances and tail-heavy distributions to long reuse distances or queue churn; deeper GHOST hits may support a larger ghost queue.
  • Features include cache-scale, hit and miss statistics, queue-hit fractions, one-hit-wonder and unique-object ratios, and aggregated queue-depth histograms.
  • A and B are assigned randomly, so the model must evaluate both configurations on their merits rather than infer correctness from labels.

A.3 Artifact Appendix

The artifact provides implementations, training and analysis scripts, documentation, and containerized infrastructure for reproducing S4-FIFO’s miss-ratio and throughput evaluations. Its stated scope includes comparisons across supported production traces, although some traces are proprietary and unavailable publicly.

  • Contents: The artifact includes libCacheSim miss-ratio evaluation, CacheLib throughput integration, model-training and analysis scripts, Docker setup, and reproduction documentation.
  • Scope: Its validation scope covers comparing S4-FIFO with multiple cache-eviction baselines and reproducing parameter search, feature collection, model training, evaluation, and feature-importance analyses.
  • Evaluation data: The paper evaluates S4-FIFO on 5,175 production traces from 14 sources.
  • Contents: The repository organizes simulator and CacheLib implementations, analysis scripts, documentation, a Dockerfile, and a Makefile into separate components.
  • Hosting: The artifact is publicly hosted on GitHub, with the paper’s corresponding version identified by the osdi26 branch and a specific commit.
Loading 2608.27975v1…