CS Paper Radar

Demystifying and Improving Lazy Promotion in Cache Eviction

Qinghan Chen, Muhammad Haekal Muhyidin Al-Araby, Ziyue Qiu, Zhuofan Chen, Rashmi Vinayak, Juncheng Yang

cs.DB ·submitted 2026-08-30 19:38 UTC · v1
top venuebenchmark

Abstract

Cache eviction algorithms play a critical role in the performance of modern data systems, yet their scalability is often limited by the high computational overhead associated with object promotions. Lazy Promotion techniques have emerged as relaxations of traditional Least-Recently-Used (LRU) methods, designed to alleviate lock contention and increase throughput. This work uses production traces from real-world systems to benchmark five Lazy Promotion strategies: Probabilistic-LRU, Batch-LRU, Delay-LRU, FIFO-reinsertion, and Random-LRU. We evaluate these techniques across miss ratio, scalability, promotion count, and a novel metric called promotion efficiency, which measures the number of hits per promotion. Our results reveal that Delay-LRU and FIFO-reinsertion significantly improve promotion efficiency, whereas Batch-LRU and Probabilistic-LRU struggle to reduce promotions without significantly increasing miss ratio. We further explore the impact of lazy promotion in advanced algorithms such as ARC and 2Q and make a similar observation. Moreover, we uncover substantial optimization potential, showing that most cache promotions are unnecessary when equipped with oracle knowledge. To further reduce promotions in LRU, we propose two novel enhancements-Delayed FIFO-reinsertion (D-FR) and Age-Guided Eviction (AGE)-that reduce promotions by 20-60% while achieving a similar or lower miss ratio.

Comment
14 pages, 13 figures, and 3 tables. Published in PVLDB 19(4); VLDB 2026 conference paper
Journal ref
Proceedings of the VLDB Endowment, 19(4): 549-562, 2025
DOI
10.14778/3785297.3785299

Closest papers

Nearest neighbours by meaning across the whole index.

When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse

cs.DC cs.LG ·2026-09-24 ·Yiyu Liu, Minlan Yu, Juncheng Yang
code/datahighly cited similarity 0.71
Abstract · 20 pages, 20 figures, 6 tables. Simulator: https://github.com/cacheMon/PrefixSim Traces: https://huggingface.co/datasets/harvardMadsys/2026_…

Long-running LLM applications and autonomous agents repeatedly send growing context, making prefix caching critical for reducing prefill cost. This raises a fundamental question: do decades of traditional cache-management techniques transfer directly to agentic and conversational LLM serving? We analyze production traces comprising over 20 billion processed tokens and evaluate 14 eviction algorithms across capacity-constrained HBM and large memory-pool settings. We find that simple Least Recently Used (LRU) is surprisingly robust, offering competitive performance against sophisticated traditional policies, though substantial headroom to Belady's optimum remains. The reason is structural: prefix reuse is dominated by the steady pacing of active sessions, making recency an unusually strong predictor for eviction. Nevertheless, prefix caching diverges from traditional workloads in ways that recency ignores, notably the prevalence of single-turn requests, extreme session footprint skew, and highly non-uniform miss costs because attention computation scales with token depth. To close the gap to optimality, we establish several design principles for prefix-cache management: keeping recency as the baseline while incorporating quick demotion to filter one-hit prompts, compute-aware eviction to prioritize expensive misses, and capacity-adaptive eviction granularity. Our traces and simulator are publicly available.

0.60

Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders

cs.DB cs.LG ·2026-08-20 ·Yash Kulkarni, Shubham Harkare, Arvind Yogesh Suresh Babu
similarity 0.66
Abstract · 11 pages, 9 figures

Semantic caches reuse an LLM response when the incoming query embedding lies near a cached query, but proposed eviction policies have rarely been compared under one protocol. Using CLEVER, we evaluate FIFO, LRU, LFU, ARC, GDSF, a single-pass streaming adaptation of SISO, and a semantic-redundancy policy across three ordered, deduplicated query corpora, three cache capacities, and two encoders. No evaluated policy improves on LFU by more than 0.041 percentage points in any of the eighteen settings. Replacement is not irrelevant: FIFO and streaming SISO trail LFU by as much as 8.67 and 8.55 points, respectively, at tight capacity. We explain the missing upside with a conditional packing result. Under exact lookup and insert-on-miss, a newly inserted entry cannot have a resident neighbor within the hit radius, so a geometry-aware eviction rule receives little new redundancy signal. A separate audit exposes a larger problem with the evaluated operating point. At MiniLM's median nearest-neighbor threshold, only 2.1-3.9% of sampled LMSYS and QQP hits are judged answer-substitutable, reducing raw hit rates of 51-60% to quality-adjusted rates of 1.1-2.2%. The cross-encoder study further shows that thresholds do not transfer between embedding models. LFU is the strongest simple default in this protocol; deployment decisions should first establish answer validity and then test sub-point policy differences with exact search.

0.20

Aker: Density-Aware Approximate Caching for Vector Search (Extended Version)

cs.DB ·2026-09-03 ·Sukjoon Oh, Minki Kang, Dohyun Kim, Baotong Lu, Jing Liu +3 more
top venue similarity 0.66
Abstract · Extended version of the paper published in Proceedings of the VLDB Endowment (PVLDB), Vol. 19, No. 10, pp. 2727-2740, 2026

Disk-based approximate nearest neighbor search (ANNS) incurs high I/O overhead due to frequent disk accesses during index traversal. Approximate caching, which reuses the results of past queries to serve future similar queries, offers a promising approach to bypass expensive disk searches. However, existing approaches suffer from two key limitations. First, their approximate hit predicates fail to simultaneously achieve high throughput and high accuracy, as they do not adapt to the varying local neighbor density in high-dimensional spaces. Second, they lack an effective refresh mechanism to maintain cache correctness under vector updates. We present Aker, an approximate cache for disk-based ANNS. Aker addresses these limitations through two core design choices. First, we introduce a per-query similarity threshold, where each cache entry maintains its own threshold that is dynamically adjusted based on observed cache hit patterns. This design enables Aker to adapt to neighborhood densities to preserve both efficiency and accuracy. Second, we propose del-consistency, a consistency model for ANNS caches that applies deletions eagerly and insertions lazily. Under this model, Aker implements a low-overhead refresh mechanism that bounds cache staleness and preserves high search accuracy. We integrate Aker into pgvector and evaluate it on representative workloads. Aker improves recall by up to 64 percentage points over prior solutions and increases QPS by up to 3.2x, while using 0.6x the memory of pgvector's shared buffers.

0.68

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

cs.DC ·2026-08-28 ·Haocheng Xia, William Nixon, Bintang Dwi Marthen, Pranav Bhandari, Juncheng Yang
top venue similarity 0.64
Abstract · 22 pages, accepted to OSDI '26

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.

0.54

A Simple Optimistic B-Skiplist Algorithm

cs.DS ·2026-10-27 ·Jianting Guo, Yicong Luo, Helen Xu
similarity 0.63
Abstract

We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC). OLC replaces the multi-cache-line RW lock with a compact, single-cache-line lock: readers validate a version number without writing to shared memory, avoiding cache invalidations and retrying only on a detected conflict. Although OLC was thought poorly suited to skiplists, where a single per-element lock may span structurally unrelated levels, the B-skiplist's blocked layout places each level (and associated lock) in its own node. We exploit the B-skiplist's upfront knowledge of promotion height with a hybrid top-down scheme that traverses upper levels optimistically and locks only from the promotion level down, so most inserts never dirty a cache line. On 128 threads, the proposed optimistic B-skiplist achieves $1.2-10\times$ higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves $0.8-4.3\times$ the throughput compared to high-performance optimistic B+-tree implementations based on RW locks and OLC. Finally, the optimistic B-skiplist achieves up to $13\times$ lower latency than concurrent skiplists and tree-based indices, and is within $1.6\times$ of the latency of the OLC-based B+-tree.

0.25

SR-Gadgets: Make Scan-Resistant Caching Practical

cs.PF ·2026-09-24 ·Yunjia Zheng, Juncheng Yang
hot direction similarity 0.63
Abstract

Block caches commonly serve scan-heavy I/O workloads, motivating extensive studies on scan-resistant eviction algorithms. Many of these algorithms adopt a multi-queue structure. However, they focus primarily on one-time scans and do not handle repeated scans well. Two important challenges from repeated scans are miss-ratio cliffs, where a small increase in cache size sharply reduces the miss ratio, and Belady's anomalies, where increasing the cache size increases the miss ratio. In this paper, we first develop two quantitative metrics to measure these behaviors. With these metrics, we find that LIRS is the only multi-queue algorithm that is scan-resistant (almost cliff- and anomaly-free). Contrary to conventional wisdom, we show that stack distance is not the secret sauce that makes LIRS scan-resistant. Instead, regulating the queues are the key to its scan resistance. Based on these insights, we design the \gadgetprefix Gadgets, easy-to-integrate augmentations that make existing algorithms scan-resistant without changing their eviction heuristics or queue structures. We implement the \gadgetprefix Gadgets in five algorithms: S3-FIFO, SIEVE, ARC, 2Q, and TinyLFU, and make them scan-resistant. Evaluated on 5,538 production traces, all augmented algorithms outperform their base versions, reducing miss ratios by up to 23.1% while consistently reducing cliffs and Belady's anomalies across the production traces.

0.31

Chiron: Cache Management Empowered by LLM Intelligence for AI Workloads

cs.DC cs.LG ·2026-11-04 ·Bohan Zhang, Renshu Ge, Tianze Wang, Chen Chen
similarity 0.63
Abstract · 18 pages, 16 figures

AI clusters keep data in remote object stores and rely on local caches to stop GPUs from waiting for data. A cache performs well only when its prefetching and eviction policies match the access pattern, yet these patterns differ across AI workloads and change between phases of one workflow. Existing methods either need code changes, which compromises user transparency, or use low-end heuristics, which cannot follow such changes. Large language models (LLMs) can infer access behavior without user hints, but direct LLM control of cache actions suffers from long reasoning delay, high token cost, and poor decision quality. We present Chiron, a cache system based on advisory switching control. An LLM asynchronously diagnoses the access pattern and recommends a policy. A deterministic harness gates this advice, executes expert-designed policies locally, and returns cache feedback for review. We implement Chiron atop JuiceFS and evaluate it on nine AI workloads. It reduces job completion time by 14.3-41.2% over the best baseline on popular AI workloads.

0.27

The KV Cache Working Set: Online Capacity Planning for LLM Inference Systems

cs.DC ·2026-09-23 ·Luchang Li, Shuaishuai Wang, Zhao Ruan, Dongfang Li, Bozhao Gong
code/data similarity 0.62
Abstract · 9 pages, 4 figures

Prefix caching is critical for efficient large language model (LLM) serving, particularly for agentic workloads that repeatedly invoke the model with a growing conversation and tool-use history. By reusing the key-value (KV) states of previously processed prefixes, prefix caching avoids redundant prefill computation. Its effectiveness, however, depends on retaining a sufficiently large set of KV cache states. Provisioning enough cache to preserve all historical KV states is prohibitively expensive and often unnecessary, whereas insufficient capacity can substantially degrade the cache hit rate. Determining the KV cache working set, defined as the minimum cache capacity required to achieve a target hit rate, is therefore essential for efficient cache provisioning and system design. We present KVSET, an online analyzer that estimates the KV cache working set of LLM serving workloads. KVSET uses the Mattson stack algorithm to efficiently estimate cache hit rates across a wide range of cache capacities. For each KV cache page, KVSET computes its LRU stack distance and compares it with the page number of each candidate capacity. This comparison determines whether the page would be a hit at each capacity without independently simulating every capacity configuration. KVSET therefore substantially reduces the computational and memory overhead of conventional capacity-by-capacity simulation and makes online working-set analysis practical. KVSET further determines the minimum cache capacity based on the maximum LRU depth among the prefix pages required to achieve the target hit rate. We validate KVSET using traces collected from production LLM workloads and show that its estimates closely match measurements from real cache deployments. The open-source implementation supports both online request processing and offline trace replay.

0.54