When a cache miss arrives and the target set is full, hardware has microseconds — actually picoseconds — to pick a victim. The replacement policy is the algorithm that makes that choice, and it's implemented entirely in gates because software is far too slow to be in the loop.

The candidates:

• LRU (Least Recently Used): The textbook answer. For an N-way set, you need to track the relative age of every line. True LRU for 4 ways needs log2(4!) ≈ 5 bits per set and complex update logic. For 8 ways, it's 16 bits. By 16 ways, full LRU is prohibitively expensive in area and timing.
• Pseudo-LRU (Tree-PLRU): A binary tree of bits points "away" from the most recently used way. An N-way cache needs only N-1 bits. On access, you flip the bits along the path to the touched line. On eviction, you follow the tree from the root. It's not true LRU but it's close enough — and cheap.
• Random: An LFSR picks a way. Sounds dumb. Actually competitive on many workloads, because it never gets pathologically wrong on adversarial access patterns the way LRU does. ARM has shipped it.
• NRU (Not Recently Used): One "recently used" bit per line. On eviction, find a line with the bit clear. If none, clear all bits and try again. Dirt cheap.
• RRIP (Re-Reference Interval Prediction): 2 bits per line predicting how soon a line will be reused. New lines get inserted with "long re-reference" (high value) so streaming data doesn't pollute the cache. Intel has shipped variants of this for over a decade.

Concrete example: Intel's Skylake L3 is 16-way associative. True LRU would need 44 bits per set across millions of sets. Skylake uses a quad-age RRIP variant that needs only 32 bits per set and beats LRU on database and streaming workloads where LRU gets thrashed by large working sets.

Rule of thumb for hardware area: True LRU costs roughly N·log2(N) bits per set; Tree-PLRU costs N-1 bits; NRU and RRIP cost 1-2 bits per line. For anything beyond 4-way, designers almost never pick true LRU — the timing path through the age-comparison logic blows the clock budget.

The scan problem: LRU fails catastrophically on workloads that touch a working set larger than the cache once. Every line gets evicted right before it would be reused. RRIP fixes this by inserting new lines as "probably won't be reused," letting the existing hot lines survive a scan.