LFU — Page Replacement

Overview

What this concept solves

LFU — Least Frequently Used — bets on popularity instead of recency. Each page keeps a running count of how many times it's been referenced, and when something has to go, LFU evicts the page with the smallest count. The intuition: a page used many times is probably important and will be used again; a page used once was probably a fluke.

Where LRU asks 'when was this last used?', LFU asks 'how often has this been used?'. For workloads with a stable set of hot pages — a few popular items everyone keeps requesting — frequency is a strong, stable signal that resists being knocked out by one-off accesses.

But frequency has a famous blind spot: it has no sense of time. A page that was hammered early in the program builds a huge count and then clings to memory forever, even if it's never touched again — because its count stays high while newer, genuinely-useful pages can't catch up. This 'cache pollution' by stale-but-popular pages is LFU's defining weakness.

Mechanics

How it works

The rule, step by step

Page already resident? Hit. Increment its count by one.
Not in memory, free frame available? Load it with a starting count of 1.
Not in memory, all frames full? Evict the page with the smallest count. If several tie for the smallest, break the tie by least-recently-used (evict the one not touched for longest).

The stale-frequency problem

Imagine a page referenced 50 times during startup, then never again. Its count is 50. Meanwhile your current working set churns through pages that only ever reach counts of 2 or 3. Pure LFU will evict your live working set over and over while protecting the dead startup page, because 50 > 3. Frequency without decay measures all-time popularity, not current popularity. The prototype's Stale frequency preset shows this trap directly.

Real LFU implementations fix this with aging or decay: periodically halve all counts, or use a count that decays over time, so old popularity fades and recent popularity dominates. (This is the same insight that turned NFU into Aging.) Redis's LFU mode, for instance, uses a probabilistic counter with a decay term rather than a raw count. The bare LFU shown here omits decay so you can see exactly why it's needed.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › LFU

About this simulation

Each resident page keeps a reference count, shown as a number and a bar. Every access bumps the count; a fresh page starts at 1. On a fault with no free frame, the page with the smallest count is evicted — ties broken by least-recently-used. Try the Stale frequency preset to watch a once-popular page refuse to leave long after it's gone cold.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch counts protect a popular page

Load the Frequency wins preset and step through. The pages accessed repeatedly grow long bars (high counts) and survive, while pages touched once or twice get evicted first. On each eviction the decision card lists all counts sorted low-to-high and marks the smallest as the victim.

try 02

Fall into the stale-frequency trap

Run Stale frequency: one page is hammered early (its bar shoots up), then never used again, while later pages cycle through with low counts. Watch LFU repeatedly evict the live, low-count pages and protect the dead high-count one. This is the exact failure that motivates decaying the counts.

try 03

See the LRU tie-breaker kick in

Run Tie → LRU, where several pages share the same lowest count. When counts tie, LFU can't decide on frequency alone, so it evicts the least-recently-used among them. Read the decision card — it shows each tied page's 'last used' step and notes when the tie was broken by recency.

In practice

When to use it — and what you give up

When frequency is the right signal

Stable, skewed popularity — a small set of items accounts for most accesses and that set rarely changes (think a CDN serving a catalogue where a few assets dominate). Frequency captures this beautifully.
When recency misleads — workloads where a page used heavily but not just now is still the right thing to keep; LRU would wrongly evict it, LFU won't.
Always pair it with decay in production — raw LFU's stale-frequency trap makes some aging mechanism essentially mandatory for a long-running cache.
Avoid it for shifting working sets — if the hot set changes over time, undecayed counts anchor the cache to the past and starve the present.

Where you'll see it

Redis offers allkeys-lfu / volatile-lfu eviction with a built-in decay so old accesses fade. Hybrid policies like ARC, 2Q, and LFRU combine recency and frequency to get the best of both (see the Cache Eviction topic). Pure, undecayed LFU is mostly a teaching device and a building block — but the frequency signal it isolates is everywhere in modern caches.

Pros

Captures popularity — keeps a stable hot set even when single accesses churn around it.
Resists one-hit wonders — a page touched once can't displace a genuinely popular page.
Strong on skewed workloads — when a few items dominate access, frequency tracks them directly.
Simple core idea — one counter per page, evict the minimum.

Cons

No sense of time — stale-but-popular pages cling forever; the defining flaw.
Slow to adapt — a new hot page starts at 1 and takes many accesses to overtake an old high count.
Needs decay to be practical — usable long-running LFU requires aging the counts, adding complexity.
Tie-breaking and counter cost — ties need a secondary rule (often LRU), and exact min-count eviction wants a careful data structure (e.g. buckets by frequency).

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

lfu.ts

// LFU: evict the smallest reference count; ties broken by least-recently-used.
interface Slot { page: number; freq: number; lastUsed: number; }

class LFU {
  private frames: number;
  private resident: Slot[] = [];
  private clock = 0;          // logical time for the LRU tie-break
  faults = 0; hits = 0;

  constructor(frames: number) { this.frames = frames; }

  access(page: number): "hit" | "fault" {
    this.clock++;
    const slot = this.resident.find((s) => s.page === page);
    if (slot) { slot.freq++; slot.lastUsed = this.clock; this.hits++; return "hit"; }
    this.faults++;
    if (this.resident.length >= this.frames) {
      // smallest freq wins; tie -> smallest lastUsed (least recently used)
      let victim = this.resident[0];
      for (const s of this.resident) {
        if (s.freq < victim.freq ||
           (s.freq === victim.freq && s.lastUsed < victim.lastUsed)) victim = s;
      }
      this.resident = this.resident.filter((s) => s !== victim);
    }
    this.resident.push({ page, freq: 1, lastUsed: this.clock }); // new page: count 1
    return "fault";
  }
}

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Which page does LFU evict?

question 02 / 03

What is the stale-frequency problem in basic LFU?

question 03 / 03

How do practical LFU implementations avoid clinging to stale-but-popular pages?

0/3 answered