LFU Cache — Mathematical Foundations and Complexity Theory¶

Definition (LFU cache). An LFU cache of capacity k is a tuple
  C = (U, k, S, freq, rec)  where
    U          = universe of keys
    k in N      = capacity (max resident keys)
    S subset U  = resident set, |S| <= k
    freq: S -> N>0   = access count of each resident key
    rec:  S -> N      = recency stamp (last-access tick) of each resident key

On a request to key x (a get or put):
  - HIT  (x in S):  freq(x) <- freq(x) + 1;  rec(x) <- now
  - MISS (x not in S):
        if |S| = k:  evict v = argmin over S of (freq, rec)  [lexicographic]
        S <- S ∪ {x};  freq(x) <- 1;  rec(x) <- now

Eviction victim:
  v = argmin_{u in S} (freq(u), rec(u))          (ties: smaller rec = older)

(I1) Bucket partition.  The buckets {B_f : f >= 1, B_f != empty} partition S:
       every resident key is in exactly one bucket, namely B_{freq(key)}.

(I2) Per-bucket recency order.  Within each B_f, nodes are ordered
       front -> back by strictly decreasing rec. Hence back(B_f) is the
       least-recently-used key among those of frequency f.

(I3) minFreq correctness at eviction.  Immediately before any eviction,
       minFreq = f_min = min{ f : B_f != empty }.

get(x):
  1. look up x in keyMap                       -- 1 hash op
  2. if absent: return -1                       -- O(1)
  3. promote(node)                              -- see below
  4. return node.value                          -- O(1)

promote(node):
  f = node.freq
  remove node from B_f                          -- 4 pointer writes (DLL unlink)
  if B_f became empty:
      delete freqMap[f]                          -- 1 hash op
      if minFreq == f: minFreq = f + 1           -- O(1)
  node.freq = f + 1                              -- O(1)
  if freqMap[f+1] absent: create empty DLL       -- 1 hash op
  pushFront(B_{f+1}, node)                        -- 4 pointer writes

put(x, v):
  if capacity == 0: return                       -- O(1)
  if x in keyMap:                                 -- 1 hash op
      node.value = v; promote(node); return       -- O(1)
  if n == capacity:                               -- eviction
      victim = popBack(B_{minFreq})                -- DLL pop: 4 pointer writes
      delete keyMap[victim.key]                    -- 1 hash op
  create node(x,v,freq=1)                          -- O(1)
  keyMap[x] = node                                 -- 1 hash op
  pushFront(B_1, node)                             -- 4 pointer writes
  minFreq = 1                                      -- O(1)

Lemma (minFreq maintenance). Maintaining the rules
    (R1) on insert of a new key: set minFreq <- 1;
    (R2) on promote of a node from frequency f, if B_f becomes empty
         and minFreq == f: set minFreq <- f + 1;
preserves invariant (I3) — minFreq = f_min at every eviction point.

Proof.
  Evictions occur only inside put, immediately before an insert.
  Consider the value of minFreq just before such an eviction.

  Case A (the last structural change was an insert, R1).
    R1 set minFreq = 1, and that insert created a key with freq = 1,
    so B_1 != empty and f_min = 1 = minFreq. (I3) holds.

  Case B (the last change was a promote from f, R2 fired).
    The promoted node moved into B_{f+1}, so B_{f+1} != empty, and B_f
    became empty with minFreq updated to f+1. No bucket below f+1 became
    non-empty during a promote (promote only moves a node UP by one and
    creates no smaller bucket). Thus f_min = f+1 = minFreq. (I3) holds.

  Case C (a promote from f occurred but R2 did NOT fire).
    Then either B_f is still non-empty (f_min unchanged, minFreq unchanged,
    still = f_min), or minFreq != f (so emptying B_f does not affect the
    minimum). Either way minFreq still equals f_min.

  In all cases minFreq = f_min at the next eviction. By induction over the
  operation sequence, (I3) holds whenever an eviction reads minFreq. ∎

Independent Reference Model (IRM). Each request draws a key independently
from a fixed distribution p = (p_1, p_2, ..., p_m), where p_i = Pr[request = key i],
sum p_i = 1. Requests are i.i.d. (no temporal correlation).

A common instance is the Zipf distribution:
    p_i proportional to 1 / i^s,    rank i = 1..m,  skew s > 0.
Web, CDN, and DB workloads are empirically near-Zipfian with s in [0.6, 1.0].

Theorem (LFU is asymptotically optimal under the IRM).
Under the Independent Reference Model with a fixed distribution p, as the
number of requests t -> infinity, an (exact, non-decaying) LFU cache of
capacity k holds the top-k most probable keys with probability -> 1, and its
hit ratio converges to the optimal H* = sum_{i in top-k} p_i.

Proof sketch.
  Let N_i(t) = number of requests to key i in the first t requests.
  By the strong law of large numbers, N_i(t)/t -> p_i almost surely.
  Hence for any two keys i, j with p_i > p_j, there exists T such that for
  all t > T, N_i(t) > N_j(t) almost surely (their frequency ranks order by p).

  LFU evicts the resident key of smallest count. Once counts reflect the true
  ranking (t > T), any resident key outside the top-k has a smaller count than
  every top-k key, so it is the eviction target whenever a top-k key faults in.
  Thus the resident set converges to the top-k keys, achieving H*. ∎

Regime 1 — Stationary skewed (IRM/Zipf, fixed p):
    LFU -> H* (optimal).  LRU -> H_LRU < H*.    LFU strictly better.

Regime 2 — Non-stationary (p shifts at change-points):
    Exact LFU is anchored by stale counts; after a shift it can take
    Omega(accumulated old count) requests to evict a formerly-hot key.
    LRU adapts within O(k) requests of the shift.   LRU better.

Regime 3 — Looping / sequential scan over a working set larger than k:
    LRU suffers Belady-anomaly-free but pessimal behavior (every access a
    miss for loop length > k). LFU treats scan keys as freq-1 and protects
    a high-frequency hot subset.   LFU better (scan-resistant).

Definitions. For request sequence sigma, let f_A(sigma) = page faults of online
policy A, f_OPT(sigma) = faults of the offline optimum (Belady's MIN). A is
c-competitive if f_A(sigma) <= c * f_OPT(sigma) + b for all sigma.

Fact. Deterministic LRU and FIFO are k-competitive, and k is optimal for any
deterministic online paging policy (lower bound by the standard adversary).

Claim. Pure (non-decaying) LFU is NOT c-competitive for any constant c
independent of the sequence length; an adversary can force LFU into an
unbounded competitive ratio.

Adversary construction.
  Phase 1: request key A m times (m huge). Now freq(A) = m.
  Phase 2: with capacity k, repeatedly request a cyclic working set
           {B_1,...,B_k} that fits exactly if A is evicted. But A's count m
           dominates every B_j's growing count for the first ~m rounds, so LFU
           keeps A and thrashes one slot among the B_j's, faulting on nearly
           every Phase-2 request. OPT evicts A immediately and serves Phase 2
           with few faults. The ratio grows with m, unbounded. ∎

Setup. A key x receives F accesses during [0, t0], then zero accesses after t0.
With exact, non-decaying LFU, freq(x) = F + (init) for all time > t0.

Claim. x is evicted only after some other resident key accumulates count > F.
For a key y with arrival rate lambda_y (accesses/sec) after t0, y reaches count
F at expected time approximately F / lambda_y after t0.

Consequence. The "dead weight" duration D(x) during which the cold key x squats
a cache slot satisfies
    D(x) ≈ (F - c_y) / lambda_max
where lambda_max is the rate of the fastest-growing competitor and c_y its count
at t0. D(x) grows LINEARLY in the historical peak count F.

Aggregate method. Over any sequence of t operations on an LFU cache:
  - Each get/put performs O(1) hash ops and O(1) pointer rewires (shown above).
  - A bucket B_f is CREATED at most once per promotion or insert into it, and
    DESTROYED at most once when it empties. Each create/destroy is O(1).
  - The number of bucket creations <= number of promotions + inserts <= 2t.
  - Total work = O(t). Amortized per op = O(1).

Potential method. Define Phi(D) = (number of non-empty buckets) >= 0.
  - Insert: may create bucket 1 (Phi += 1); actual O(1); amortized O(1).
  - Promote from f: destroys B_f if it empties (Phi -= 1), creates B_{f+1} if new
    (Phi += 1). Net change in Phi in {-1, 0, +1}; actual O(1); amortized O(1).
  - Evict: removes a node, possibly destroys B_{minFreq} (Phi -= 1); amortized O(1).
  Since Phi >= 0 and Phi(D_0) = 0, sum of actual costs <= sum of amortized = O(t).

Capacity k = 2. Universe {A, B, C}. Sequence:
    A A A A   B C B C B C B C ...   (the BC loop repeats r times)

Phase 1 (A A A A): A enters (freq 1), promoted to freq 4. B not yet seen.
Phase 2 (B C B C ...):
  - First B: cache {A(4)}, room -> insert B(1). Cache {A(4), B(1)}.
  - First C: full. minFreq=1 bucket = {B}. Evict B. Insert C(1). Cache {A(4), C(1)}.
  - Next B: full. minFreq=1 bucket = {C}. Evict C. Insert B(1). Cache {A(4), B(1)}.
  - ... A (freq 4) is NEVER the minimum, so the second slot thrashes B<->C.
  Every Phase-2 request after the first is a MISS: 2r - 1 faults.

OFFLINE MIN on the same sequence:
  - Evict A right after Phase 1 (A is never requested again).
  - Keep {B, C} resident through the entire loop: 0 faults in the steady loop.
  Faults ≈ 3 (A, B, C compulsory) + 0 loop faults.

Ratio f_LFU / f_MIN ≈ (2r - 1 + const) / const  ->  unbounded as r -> infinity.

GreedyDual-Size-Frequency (GDSF). Each object x has a priority
    H(x) = clock + frequency(x) * cost(x) / size(x)
where `clock` is a running offset set to the H-value of the last evicted object
(an aging mechanism). Evict the object with minimum H(x). On access, recompute
H(x) with the incremented frequency. The `clock` term ages stale objects: an
object's H stays fixed while it is idle, so the global clock eventually surpasses
it, making it evictable — decay by another name.

Objective. GDSF approximately maximizes the cost hit ratio
    sum over hits of cost(x)
subject to sum of resident size(x) <= capacity (a fractional-knapsack flavor).
Plain frequency LFU is the special case cost = size = 1.

LFU-K / LRU-K (O'Neil et al.). Track the time of the K-th-most-recent access to
each key (the "backward K-distance"). Evict the key whose K-th-to-last reference
is oldest. K = 1 recovers LRU; larger K weights frequency more (a key must have
been accessed K times recently to be protected). LRU-2 is a celebrated DB buffer
policy: scan-resistant yet adaptive, because a single scan touch does not build
the required K-history.

LRFU (Least Recently/Frequently Used). Assign each key a Combined Recency and
Frequency value
    CRF(x) = sum over past accesses i of  (1/lambda)^{ (t_now - t_i) }   , lambda in [0,1]
a weighted sum where recent accesses count more (exponential recency decay).
  - lambda -> 0: weights collapse so only the most recent access matters -> LRU.
  - lambda -> 1: all accesses count equally -> LFU.
Evict the key with minimum CRF. The exponential weighting is, again, DECAY: it is
exactly the multiplicative forgetting of the earlier section applied per-access.

Model (multiplicative decay). Let counts be halved every tau seconds (or every
N accesses). A burst of F accesses at time t0 contributes, at time t0 + m*tau,
an effective count of approximately F / 2^m.

Forgetting time. The contribution of an old burst drops below the count of a key
with steady rate lambda after
    m such that F / 2^m < lambda * tau
    => m > log2( F / (lambda * tau) )
    => forgetting time ≈ tau * log2( F / (lambda * tau) ).

Morris counter. State c; estimate of true count n is X = 2^c - 1 (base-2 variant).
Increment rule: on each event, c <- c + 1 with probability 2^{-c}.

Unbiasedness.  E[X_n] = n   (exact in expectation; classic Morris result).

Variance.      Var[X_n] = n(n-1)/2.   So relative standard deviation
               sd(X_n)/n -> 1/sqrt(2) ≈ 0.707 for base 2.

Tunable base a > 1 (generalized Morris). Estimate X = (a^c - 1)/(a - 1).
               Var[X_n] = (a - 1)/2 * n(n-1).
               => relative error shrinks as a -> 1, at the cost of more bits.

Space. To count up to n, the counter c reaches ~ log_a n, needing
               O(log log n) bits  (vs log n bits for an exact counter).

Setup. A frequency sketch ~f estimates true frequency f using a Count-Min
sketch with w counters per row and d rows (hash functions), under reset-on-N
aging. Count-Min gives a ONE-SIDED error:
    ~f(x) >= f(x)   always (never underestimates), and
    Pr[ ~f(x) > f(x) + eps * N ] <= e^{-d}     when w >= e/eps,
where N is the total number of counted accesses in the current epoch.

Admission rule. Admit candidate cand over resident victim vic iff
    ~f(cand) >= ~f(vic).

Soundness (near-correct admission). Because Count-Min overestimates by at most
eps*N w.h.p., the admission decision agrees with the EXACT-frequency decision
whenever |f(cand) - f(vic)| > eps*N. Only near-ties (within the sketch's error
band) can be misjudged, and a misjudged near-tie costs at most the difference
in their true frequencies — negligible for eviction quality.

Space. d rows of w = e/eps counters of b bits each: O((e/eps) * d * b) bits TOTAL,
independent of the number of distinct keys. With 4-bit counters and small d,w
this is ~10 bits PER CACHE ENTRY — orders of magnitude below exact per-key counts.

Aging correctness (reset-on-N). Halving every counter after N additions bounds
the epoch's counted accesses, so the eps*N error term stays bounded and the
sketch reflects RECENT frequency. Effective memory is a soft window of ~N
accesses, fusing frequency with coarse recency — this is what makes TinyLFU
both frequency-aware (Regime 1) and adaptive to shift (Regime 2).