Symptom

Your cache hit rate is 87%. Is that good?

Nobody can say. You try LFU instead of LRU and get 85%, then a hand-tuned hybrid and get 88%, and you have no idea whether the remaining 12% is a policy you have not tried yet or a hard floor imposed by the access pattern. So the tuning continues indefinitely, because there is no way to tell “we are done” from “we have not been clever enough”.

Then someone doubles the cache size and the hit rate goes to 94% — a bigger improvement than every policy experiment combined.

Both of those observations have a theory behind them. There is a policy that is provably optimal and impossible to implement, which tells you the floor. And there is a theorem saying that the gap between LRU and that floor closes as you add memory — which says the size knob is the real one, and that is not a coincidence.

Statement

Belady’s algorithm (MIN, OPT), 1966. On a cache of $k$ pages, evicting the page whose next use is furthest in the future minimises the total number of faults over any request sequence. No offline algorithm faults fewer times.

It is optimal and unimplementable, because it requires the future. Its use is as a yardstick: replay a production trace offline, run MIN, and you learn how many of your misses were policy and how many were unavoidable.

For online policies, competitive analysis gives a discouraging answer and then takes it back.

Sleator–Tarjan (1985). LRU is $k$-competitive on a cache of size $k$: for every sequence $\sigma$,

$$\text{LRU}_k(\sigma) \le k \cdot \text{OPT}_k(\sigma) + k$$

and no deterministic online paging algorithm is $c$-competitive for any $c < k$.

Resource augmentation (same paper). Give LRU a larger cache than OPT. With LRU holding $k$ pages and OPT holding $h \le k$,

$$\text{LRU}_k(\sigma) \le \frac{k}{k - h + 1}\,\text{OPT}_h(\sigma) + k$$

At $k = 2h$ the ratio is about $2$.

Randomization. The MARKING algorithm is $2H_k$-competitive, where $H_k \approx \ln k$, against an oblivious adversary, and $H_k$ is optimal.

Argument

Belady’s optimality, by exchange. Let OPT be any offline algorithm and MIN the furthest-in-future rule. Suppose they agree on the first $t$ evictions and differ at eviction $t+1$: MIN evicts $p$ (next used at time $f_p$, the furthest of any cached page) and OPT evicts $q \ne p$ (next used at $f_q \le f_p$).

Build OPT’ that matches MIN at step $t+1$, evicting $p$, and thereafter mimics OPT. The two caches now differ in exactly one page: OPT holds $p$ and lacks $q$; OPT’ holds $q$ and lacks $p$. Run forward. Every request both handle identically except requests to $p$ or $q$.

The request to $q$ arrives first, at $f_q$. OPT faults on it and must evict something; OPT’ has $q$ and does not fault. OPT’ is now one fault ahead, and can spend that credit later: at $f_p$, OPT’ faults on $p$ (which it evicted) while OPT does not. So over the interval, OPT’ faults no more than OPT — the fault at $f_p$ is paid for by the fault saved at $f_q$, and OPT’ can restore the identical cache state by evicting appropriately at $f_p$.

Repeating the exchange for each disagreement transforms any OPT into MIN without ever increasing the fault count. MIN is optimal, and the proof is the standard exchange argument: show any deviation can be swapped toward the greedy choice for free.

LRU is $k$-competitive. Partition $\sigma$ into phases: a phase is a maximal run containing requests to at most $k$ distinct pages, cut just before the request that would make it $k+1$.

Upper bound. Within a phase, LRU faults at most $k$ times. Reason: a phase touches at most $k$ distinct pages, and LRU never evicts a page that has been touched within the current phase while a page untouched in this phase remains — touched pages are the most recent. So each of the $k$ distinct pages costs at most one fault per phase.

Lower bound on OPT. Consider phase $i$ and the first request of phase $i+1$. Let $p$ be the page requested immediately before phase $i$ began. Phase $i$ contains $k$ distinct pages, and together with the first request of phase $i+1$ there are $k+1$ distinct pages requested in that window, at least $k$ of which differ from $p$. OPT holds $p$ at the start of phase $i$, so it must fault at least once per phase.

$k$ faults against at least $1$: ratio $k$. The bound is tight, as the adversary in the next paragraph shows.

Why no deterministic policy beats $k$. The adversary uses only $k+1$ distinct pages. Because the algorithm is deterministic, the adversary knows exactly which page is not in the cache, and requests that one. Every request is a fault. Over $n$ requests the algorithm faults $n$ times. OPT, seeing the whole sequence, applies Belady and faults at most once per $k$ requests, because after a fault it evicts the page not requested for the longest time and that page is untouched for at least $k-1$ subsequent requests. Ratio $k$. This applies to every deterministic policy — LRU, FIFO, LFU, CLOCK, and your hybrid — so the $k$-competitive bound is not a criticism of LRU specifically.

Resource augmentation, the step that makes the theory useful. The $k$-competitive result is correct and useless, because no real workload looks like that adversary and LRU is not, in practice, $k$ times worse than optimal. Sleator and Tarjan’s repair is to stop comparing at equal cache size.

With LRU at size $k$ and OPT at size $h \le k$, the phase argument changes: LRU still faults at most $k$ times per phase, but a phase now contains $k$ distinct pages while OPT has only $h$ slots, so OPT must fault at least $k - h + 1$ times per phase. The ratio becomes $\frac{k}{k-h+1}$.

Read the numbers. At $h = k$ it is $k$, the useless bound. At $k = 2h$ it is roughly $2$: LRU with twice the memory is within a factor of two of optimal with the original memory, for every sequence. At $k = 4h$ it is about $1.33$.

This is the theorem behind the symptom. Doubling the cache produced a bigger improvement than any policy change, and it was not luck: the theory says policy improvements are bounded and hard-won at fixed size, while size improvements are guaranteed. Buy memory before you tune eviction.

Randomization, briefly. MARKING keeps a mark bit per page. On a fault, if all pages are marked, clear all marks (new phase); then evict a page chosen uniformly at random from the unmarked ones and mark the requested page. The adversary cannot target the victim, and the expected number of faults per phase works out to $H_k = 1 + 1/2 + \cdots + 1/k \approx \ln k$ rather than $k$. For $k = 1000$ that is a competitive ratio near 15 rather than 1000 — randomization converts a linear ratio into a logarithmic one, and $H_k$ is a matching lower bound for randomized policies.

Belady’s anomaly, which belongs here because it is the exception. For FIFO, adding cache slots can increase the number of faults. The reference sequence 1,2,3,4,1,2,5,1,2,3,4,5 produces 9 faults with three frames and 10 with four.

The explanation is stack property. A policy is a stack algorithm if the set of pages held at size $k$ is always a subset of the set held at size $k+1$. LRU has it: the $k$ most recent are a subset of the $k+1$ most recent, always. So adding a frame to LRU can never hurt. FIFO does not have it, because insertion order and recency are unrelated, and a larger FIFO cache can retain a different — worse — set. Belady’s anomaly is a property of FIFO, not of caching, and it is another reason LRU-family policies are the default: their behaviour under resizing is monotone, which is what makes capacity planning meaningful at all.

CLOCK, the approximation of LRU that every real kernel actually runs, is a stack algorithm in its basic form, which is why the substitution is safe.

Forbids

Expecting a policy to close a gap that capacity is causing. If the working set does not fit, no eviction rule saves you. MIN on the trace tells you which regime you are in, and that measurement is cheap.

A deterministic policy with a worst-case ratio better than $k$. It does not exist. Any claim of a universally better eviction policy is a claim about typical workloads, not about the worst case.

Claiming a policy is optimal without offline comparison. “87%” means nothing without MIN’s number on the same trace. The single most valuable thing you can do to a cache is replay its trace through Belady, and it takes an afternoon.

Assuming more cache always helps, for FIFO. Belady’s anomaly is real, and FIFO-based caches must be measured across sizes rather than assumed monotone.

Does not forbid

It does not say LRU is 1000x worse than optimal on your workload, and this is the misreading that made a generation of engineers distrust competitive analysis. The $k$-competitive bound is attained only by a synthetic cyclic-scan adversary. On real traces LRU typically lands within a few percent of MIN. The bound is a worst-case guarantee, not a prediction, and reading it as a prediction is what the resource-augmentation result exists to correct.

It does not mean policy work is pointless. Since the worst case is the same for all deterministic policies, the differences are entirely in the typical case — and those differences are real and large. ARC, 2Q, LIRS, S3-FIFO, and TinyLFU all beat LRU substantially on real traces by detecting scans and frequency, and none of them contradicts a single line above, because they all still have worst-case ratio $k$.

It does not make Belady unimplementable in every setting. The future is sometimes known. A query planner executing a known join order knows its access sequence in advance, and compilers scheduling register spills have the same information; both apply furthest-in-future directly, and it is optimal there.

It does not apply unchanged to non-uniform costs. The whole analysis counts faults, assuming every miss costs the same. When misses have different costs — a CDN with variable object sizes, a memory hierarchy with different miss penalties — this is weighted caching, and Belady’s rule is no longer optimal. GDSF and the Landlord algorithm exist for that case.

It does not require a single level. Multi-level caches, inclusive or exclusive, are analysable with the same phase machinery, though the interactions are what make L1/L2/L3 policy design hard.

Boundary

  • Page granularity assumed. Uniform-size objects only. Variable-size caching changes the problem into something closer to knapsack.
  • Uniform miss cost assumed. See weighted caching above.
  • No prefetching. The model is demand paging. Prefetching changes the request sequence itself and is outside the analysis.
  • Adversary model matters. The $H_k$ randomized bound needs an oblivious adversary; against an adaptive one, randomization buys nothing.
  • Bypass changes the model. Real caches may decline to admit an item at all, which is an extra action the classical model does not have and which is precisely how scan-resistant policies get their advantage.

Two things to carry: run Belady on your trace to learn the floor, and resource augmentation says the memory knob has a guarantee that the policy knob does not.