REMARC: Reduction-Modeled Adaptive Replacement Cache

REMARC: A Compositional Framework for Cache Eviction PoliciesAbstract: We present REMARC (Reduction-Modeled Adaptive Replacement Cache), a compositional framework for cache eviction policies. The framework expresses any cache policy as a composition E = P (A₁,. . . , Aₙ), where atoms (Aᵢ) extract access signals (recency, frequency, inter-arrival period, confidence) and projections (P) map atom values to eviction decisions. We classify projections into six families---Score, Gate, Modulate, Factor, Step, and Augment---and evaluate 23 policy variants across five workloads (Zipfian, ScanResistant, Temporal, Looping, Uniform) using a deterministic trace-driven simulator (PolicyBench). Key contributions: (1) ARC is proven as a strict subset of the framework---setting the augmentation demotion threshold to minimum reproduces ARC exactly. (2) Page-level eviction imposes a structural ~24. 5% Zipfian hit-rate ceiling, resolved only by per-key eviction with quota structure. (3) AUG-ADAPT, a self-tuning variant combining heap-based eviction with ARC's adaptive replacement via a feedback controller (population coefficient-of-variation feedforward + prediction-regret feedback), achieves 99. 33% hit rate on adversarial looping workloads while matching ARC on Zipfian, ScanResistant, and Temporal workloads (zero evictions on looping). (4) The delivery--quota tension---where accurate eviction selection corrupts ARC's self-tuning---is resolved by the controller's conservative LRU default with workload-driven heap activation. (5) Three hash structure strategies are evaluated, demonstrating that throughput is a data-structure problem, not an algorithmic one. The paper presents 30 findings, including a critical ghost-list management invariant (doEvict must DROP, not ghost-move, evicted keys), the frozen-state problem for lazy decay, and evidence-based timestamp demotion. All variants use compile-time template instantiation with no virtual dispatch.