Every cache eviction policy we've covered — LRU, LFU, TinyLFU, ARC — makes a smart decision about what to evict. Smart decisions require metadata: recency timestamps, frequency counters, ghost lists, sketches. That metadata costs memory and, more importantly, requires updates on every access. LRU moves an entry to the head of a linked list on every read. LFU increments counters. That's cache-line contention, atomic operations, and cache pollution just to decide what to throw away later.

Random Replacement (RR) skips all of it. When the cache is full and you need to evict, pick a random victim and throw it out. No timestamps. No counters. No linked lists. No locks on the read path.

Why this isn't as stupid as it sounds: for many real workloads with Zipfian access patterns, RR's hit rate is surprisingly close to LRU. Hot items dominate accesses, so probabilistically they survive random eviction — a hot item accessed 1000× is unlikely to be picked when there are 10000 entries and only one gets evicted per miss. Meanwhile, cold items don't get re-inserted, so they naturally get evicted eventually.

Real-world example: ARM Cortex-A CPUs use random replacement for L1 and L2 caches. Silicon area matters more than a fractional hit-rate improvement, and RR's hit rate is within 5% of LRU on typical workloads while requiring zero replacement-state bits per line. Intel switched some of their caches from pseudo-LRU to more complex policies only when the workload analysis justified the transistor budget. Memcached's slab allocator falls back to random-ish eviction within a slab class in some configurations for similar reasons.

Rule of thumb: if your cache is small (fits in L1/L2), high-contention (many concurrent readers), or your access pattern is heavily skewed (top 20% of keys get 80% of hits), the hit-rate gap between RR and LRU is typically under 10%. Multiply that by the CPU cycles saved on every read — no list pointer updates, no atomic recency writes — and RR often wins on throughput even when it loses slightly on hit rate.

When to avoid it: uniform access patterns (RR degrades to random), or when a single miss is catastrophically expensive (DB queries taking seconds). Then spend the metadata budget on LRU or W-TinyLFU.

The lesson generalizes beyond caches: metadata isn't free. Every "smart" decision has a bookkeeping cost paid on the hot path. Sometimes the dumb algorithm with zero overhead beats the smart one that pays overhead on every access to save overhead on rare evictions.