LRU and its two failure modes

Why does LRU wipe the working set on a scan and score zero on a loop, while random replacement degrades smoothly?

LRU, and the correction it deserves

LRU (Least Recently Used) bets that the reference stream has temporal locality of a particular shape: that recency predicts imminence. On workloads with that shape the bet is close to optimal. It has two failure modes, and both are structural, not unlucky.

Failure 1: sequential flooding

A scan of a table larger than the pool touches every page exactly once. Under LRU each scanned page is the most recently used at the moment it arrives. So the scan evicts the entire working set to cache pages that it will never look at again. The hit rate afterwards is zero until the working set is read back in. This is not a rare pathology. It is what analytics workloads do all day. (This was Amara's 10:00 am scan.)

Failure 2: cyclic access, where LRU is not only bad but bimodal

Take a loop over n pages with a pool of c < n frames. When you reference page pᵢ, the pool holds the c most recent pages. But pᵢ was last referenced n steps ago, so it has been evicted. The hit rate is exactly zero for every c from 1 to n − 1, and then jumps to 100% at c = n. A cliff with nothing on it.

Worked trace. Pages 1–5 are read in a loop; the pool has 4 frames.

Reference	Pool before	Result	Evicts (LRU)
1, 2, 3, 4	(filling)	4 misses	—
5	{1,2,3,4}	miss	1
1	{2,3,4,5}	miss	2
2	{3,4,5,1}	miss	3
3	{4,5,1,2}	miss	4
4	{5,1,2,3}	miss	5

Every reference after the first four is a miss, forever, although 4 of the 5 pages would fit.

Random replacement degrades smoothly

Random replacement on the same loop behaves differently. A page survives each eviction with probability (1 − 1/c). Between two references to the same page there are about n(1 − h) misses (where h is the hit rate). So the steady-state hit rate is the fixed point of

RelationshipCyclic access: LRU against random replacement →

h = (1 - 1/ c)^{n (1 - h)} \approx e^{- n (1 - h) / c}

$n$: pages in the loop
$c$: frames in the pool
$h$: the steady-state hit rate (a fixed point)

random replacementLRU

Data table

Hit rate on a loop larger than the pool, by pool size
Pool ÷ loop c/n	series	Hit rate
0.1	random replacement	0
0.114	random replacement	0
0.128	random replacement	0
0.141	random replacement	0.001
0.155	random replacement	0.002
0.169	random replacement	0.003
0.182	random replacement	0.004
0.196	random replacement	0.006
0.21	random replacement	0.009
0.224	random replacement	0.012
0.237	random replacement	0.016
0.251	random replacement	0.02
0.265	random replacement	0.025
0.279	random replacement	0.031
0.292	random replacement	0.037
0.306	random replacement	0.044
0.32	random replacement	0.052
0.334	random replacement	0.06
0.347	random replacement	0.069
0.361	random replacement	0.078
0.375	random replacement	0.088
0.389	random replacement	0.098
0.402	random replacement	0.109
0.416	random replacement	0.121
0.43	random replacement	0.133
0.444	random replacement	0.146
0.458	random replacement	0.159
0.471	random replacement	0.173
0.485	random replacement	0.187
0.499	random replacement	0.202
0.512	random replacement	0.217
0.526	random replacement	0.233
0.54	random replacement	0.249
0.554	random replacement	0.265
0.568	random replacement	0.282
0.581	random replacement	0.3
0.595	random replacement	0.318
0.609	random replacement	0.336
0.622	random replacement	0.355
0.636	random replacement	0.374
0.65	random replacement	0.393
0.664	random replacement	0.413
0.677	random replacement	0.433
0.691	random replacement	0.454
0.705	random replacement	0.475
0.719	random replacement	0.496
0.732	random replacement	0.518
0.746	random replacement	0.54
0.76	random replacement	0.562
0.774	random replacement	0.585
0.787	random replacement	0.607
0.801	random replacement	0.631
0.815	random replacement	0.654
0.829	random replacement	0.678
0.842	random replacement	0.702
0.856	random replacement	0.727
0.87	random replacement	0.752
0.884	random replacement	0.777
0.897	random replacement	0.802
0.911	random replacement	0.828
0.925	random replacement	0.854
0.939	random replacement	0.88
0.952	random replacement	0.907
0.966	random replacement	0.933
0.98	random replacement	0.96
0.994	random replacement	0.985
1.01	random replacement	0.998
1.02	random replacement	1
1.03	random replacement	1
1.05	random replacement	1
1.06	random replacement	1
1.08	random replacement	1
1.09	random replacement	1
1.1	random replacement	1
1.12	random replacement	1
1.13	random replacement	1
1.15	random replacement	1
1.16	random replacement	1
1.17	random replacement	1
1.19	random replacement	1
1.2	random replacement	1
0.1	LRU	0
0.114	LRU	0
0.128	LRU	0
0.141	LRU	0
0.155	LRU	0
0.169	LRU	0
0.182	LRU	0
0.196	LRU	0
0.21	LRU	0
0.224	LRU	0
0.237	LRU	0
0.251	LRU	0
0.265	LRU	0
0.279	LRU	0
0.292	LRU	0
0.306	LRU	0
0.32	LRU	0
0.334	LRU	0
0.347	LRU	0
0.361	LRU	0
0.375	LRU	0
0.389	LRU	0
0.402	LRU	0
0.416	LRU	0
0.43	LRU	0
0.444	LRU	0
0.458	LRU	0
0.471	LRU	0
0.485	LRU	0
0.499	LRU	0
0.512	LRU	0
0.526	LRU	0
0.54	LRU	0
0.554	LRU	0
0.568	LRU	0
0.581	LRU	0
0.595	LRU	0
0.609	LRU	0
0.622	LRU	0
0.636	LRU	0
0.65	LRU	0
0.664	LRU	0
0.677	LRU	0
0.691	LRU	0
0.705	LRU	0
0.719	LRU	0
0.732	LRU	0
0.746	LRU	0
0.76	LRU	0
0.774	LRU	0
0.787	LRU	0
0.801	LRU	0
0.815	LRU	0
0.829	LRU	0
0.842	LRU	0
0.856	LRU	0
0.87	LRU	0
0.884	LRU	0
0.897	LRU	0
0.911	LRU	0
0.925	LRU	0
0.939	LRU	0
0.952	LRU	0
0.966	LRU	0
0.98	LRU	0
0.994	LRU	0
1.01	LRU	1
1.02	LRU	1
1.03	LRU	1
1.05	LRU	1
1.06	LRU	1
1.08	LRU	1
1.09	LRU	1
1.1	LRU	1
1.12	LRU	1
1.13	LRU	1
1.15	LRU	1
1.16	LRU	1
1.17	LRU	1
1.19	LRU	1
1.2	LRU	1

Principle: Randomization replaces coordination →

The shape matters more than the value: random is graceful where LRU is bimodal, and both are poor when c ≪ n.

The general statement to keep: LRU is not a conservative default. It is a bet on a specific access shape, and its failure is a cliff rather than a slope. This contrast between graceful and bimodal behaviour is the "variance matters more than the mean" idea in a new setting. You will meet the identical shape again in Degradation, where a spilling hash join behaves the same way for the same structural reason.

One-line compression: LRU turns a scan into a working-set wipe and a cycle into a zero, because "most recent" and "most useful" coincide only for one shape of workload.