Overview

An eviction policy decides which resident entry a cache removes when a new entry is admitted beyond capacity. Four policies cover almost every replay-and-measure task:

Policy	Data structure	On hit	On admit	Eviction choice
LRU	OrderedDict	Move to tail	Append at tail	Pop head
LFU	{key: freq} + insertion order	freq[k] += 1	freq[k] = 1	Min freq, tiebreak by insertion order
FIFO	OrderedDict	Nothing	Append at tail	Pop head
S3FIFO	Three FIFO queues + freq[k]	freq[k] = min(freq+1, cap)	Admit to small; ghost-hit admits to main	Second-chance on main; small drains to main/ghost

Each has subtleties that trip naive implementations.

LRU

Use an OrderedDict where the tail is the most-recently-accessed key. On hit, move_to_end. On miss + insert, append; pop from head if over capacity.

Most common bug: forgetting to update recency on a hit. Without the refresh, LRU degenerates to FIFO — hit rate drops substantially on any workload with recency structure.

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self._d = OrderedDict()

    def contains(self, k): return k in self._d

    def access(self, k):
        if k in self._d:
            self._d.move_to_end(k)
        else:
            self._d[k] = None
            if len(self._d) > self.capacity:
                self._d.popitem(last=False)

LFU

Keep freq: dict[key, int] and a tie-breaker — an insertion counter is simplest and deterministic. On hit, increment freq[k]. On miss at capacity, evict min(freq) with ties broken by insertion order (oldest first).

Typical bugs:

• No tie-breaker. min(freq.items(), key=lambda x: x[1])[0] has implementation-defined behaviour across interpreters and distributions. Always include a secondary key.
• Frequency pollution. A block that was hot once and then went cold can linger forever because its freq is permanently above newcomers. Production systems add aging (periodic decay of freq) or combine with a recency signal (W-TinyLFU). Pure LFU is correct for the task as specified but fragile in practice.

FIFO

One queue, insertion order, no hit-time update. Useful as a lower-bound baseline.

Do NOT call it "LRU without hit update" — conceptually different even when implementations overlap. Hit on a FIFO cache is still a hit for accounting; the block just does not change rank.

S3FIFO

A modern FIFO-family policy (Yang et al., SOSP 2023) that matches or beats LRU on typical web and LLM workloads with a fraction of the bookkeeping cost — which is why recent production systems (Twitter, Google) have been switching to it. The full algorithm — three queues, saturating frequency counter, second-chance eviction on the main queue — is implemented in the prefix-cache-replay skill. Consult that skill if your task uses S3FIFO.

Workload implications

• Strong recency → LRU wins slightly.
• Stable hot set with long tail (Zipf) → LFU or S3FIFO.
• Nearly uniform random → all converge toward capacity / working_set hit rate.
• Prefix-shared LLM workloads are mixed — shared prefixes are both recent and frequent, so LRU/LFU/S3FIFO typically sit within a few percent of each other at the same capacity, but they differ in which blocks remain resident at end-of-trace, and their miss-handling costs diverge. Measure, don't assume.

Comparing hit rates on a trace

Replay the same trace through each policy at identical capacity, record total_hit_tokens / total_prompt_tokens and the final resident set. Do not compare hit rate alone — also compare:

• Final residency — how many unique blocks are resident at the end. Under S3FIFO this is often strictly less than capacity because ghost entries absorb the admission pressure.
• Per-request hit-token distribution — two policies can have similar overall hit rate but very different per-request variance.
• Admission effort — under policies with ghost structures, the bookkeeping cost per access is non-trivial.

Common mistakes

• Reusing an LRU implementation when the task specifies S3FIFO (or vice versa). The final hit rate and residency will both differ; no partial credit for "close enough".
• Making ghost count as resident, or treating a ghost hit as a hit for token accounting.
• Forgetting to saturate freq — unbounded counters turn the main-queue second-chance loop into a spin.
• Under LFU, using Python min(d.items(), key=d.get) without an explicit insertion-order tiebreaker.
• Misordering admission and residency check. Always check h ∈ cache BEFORE applying the admission side effects of the current request, otherwise every request self-hits.
• Final cache size off by small constants because you forgot to exclude ghost or you forgot to subtract the S-cap vs M-cap split.