Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders
LFU was the strongest simple semantic-cache default, but answer validity mattered far more than eviction policy. Raw hit rates above 50% fell near 2% after quality adjustment.
Seven eviction policies were tested across three query corpora, three capacities, and two encoders. None beat LFU by more than **0.041 percentage points** in any of the 18 settings, while FIFO and streaming SISO trailed it by up to 8.67 and 8.55 points.
For an agent response cache, validate whether a matched answer can actually substitute for a new response before tuning replacement logic. Use LFU as the simple baseline, exact search for comparisons, and recalibrate thresholds for each encoder.
Seven eviction policies were tested across three query corpora, three capacities, and two encoders. None beat LFU by more than **0.041 percentage points** in any of the 18 settings, while FIFO and streaming SISO trailed it by up to 8.67 and 8.55 points. For an agent response cache, validate whether a matched answer can actually substitute for a new response before tuning replacement logic. Use LFU as the simple baseline, exact search for comparisons, and recalibrate thresholds for each encoder. At MiniLM’s median threshold, only **2.1–3.9%** of sampled hits were answer-substitutable. Raw hit rates of **51–60%** became quality-adjusted rates of **1.1–2.2%**, and thresholds did not transfer between embedding models.
This narrows the cache-engineering agenda established by the prior candidates: for response caches, semantic substitutability and encoder-specific threshold calibration matter far more than sophisticated eviction, with LFU an adequate baseline. It also distinguishes response reuse from prompt or token caching, where preserving history or incremental tokenization can improve serving without asserting that an old answer is valid for a new query.