Cache Eviction Policy

The most common eviction policy that discards the item with the oldest access timestamp first.

• Mechanism: Maintains a doubly-linked list; accessed items move to the head, eviction always targets the tail.
• Assumption: Data accessed recently will likely be accessed again soon (temporal locality).
• AI Context: Effective for repeated prompt prefixes in LLM serving, where system prompts and few-shot examples are reused across requests.
• Weakness: Suffers from cache pollution during large sequential scans, where one-time data flushes out frequently used entries.

Evicts the entry with the lowest access count, prioritizing items with sustained popularity over recent one-hit wonders.

• Mechanism: Each cache line maintains a frequency counter incremented on access; the minimum counter is evicted on overflow.
• AI Context: Ideal for embedding caches in RAG architectures where popular document chunks are queried repeatedly.
• Weakness: Cache pollution from formerly popular items that are no longer relevant; requires aging mechanisms like LFU with Dynamic Aging to decay old counters.

A deadline-driven policy where entries are automatically invalidated after a predefined expiration duration, regardless of access patterns.

• Mechanism: Each entry carries an absolute expiration timestamp; a background scavenger thread or lazy check on access removes stale items.
• AI Context: Critical for semantic cache implementations where factual data (e.g., stock prices, weather) has a known shelf-life and serving stale results is unacceptable.
• Implementation: Often combined with LRU as a hybrid policy—TTL handles temporal invalidation while LRU manages capacity pressure.

A simple queue-based policy that evicts entries strictly in the order they were inserted, ignoring all access patterns.

• Mechanism: Maintains a circular buffer or queue; the oldest inserted entry is always the eviction target.
• AI Context: Used in streaming inference pipelines where data is processed exactly once and temporal ordering matters, such as video frame analysis.
• Advantage: Extremely low computational overhead with no per-access metadata updates, making it suitable for high-throughput, low-latency GPU serving where cache management must not compete with inference.

A partitioned cache that splits entries into a probationary segment and a protected segment to prevent cache pollution from sequential scans.

• Mechanism: New entries land in probation; only on a second access are they promoted to the protected segment. Eviction always targets the probationary LRU.
• AI Context: Highly effective for KV-cache management in continuous batching inference servers, where new sequence prefixes must prove reuse value before displacing active generation contexts.
• Variant: Forms the basis of W-TinyLFU, used in high-performance Java caches like Caffeine.

A policy that assigns a retention score based on the computational expense of regenerating an item, not just its access recency or frequency.

• Mechanism: Each entry carries a recomputation cost (e.g., GPU milliseconds, token count); the eviction algorithm maximizes saved compute under capacity constraints.
• AI Context: Essential for speculative decoding caches and prompt compression caches, where regenerating a long, complex chain-of-thought trace is far more expensive than a simple embedding lookup.
• Formula: Eviction score = access_frequency × recomputation_cost / cache_size_consumed.