What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Belady's Bound: Optimal Replacement, the Static Bound and the Capacity Price of LRU”?
Answer: Chapter 3 takes Belady's optimal replacement as a lower bound on misses and the static top C as an upper bound on hits, and finds that LRU needs 4.48 times the slots for not knowing popularity.
Scope of the numbers: Under Zipf requests the hit ratio of a least-recently-used (LRU) cache grows slowly with capacity: with illustrative parameters, a hundred-and-twenty-eight-fold increase in capacity raises the hit ratio only 6.80 times. Chapter 4 derives the optimal capacity from slope and cost, 4187 slots or 0.2094 of the catalogue under illustrative parameters, with a flat cost curve around the optimum.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 4.48
| LRU slots needed to match a static top-C cache, N = 20000 | ||||
| a | C | static hit | LRU slots | multiplier |
| 0.8 | 125 | 0.2737 | 559.5 | 4.48 |
| 0.8 | 500 | 0.4055 | 1527.2 | 3.05 |
| 0.8 | 2000 | 0.5795 | 4055.3 | 2.03 |
| 0.8 | 8000 | 0.8092 | 10490.9 | 1.31 |
| 1.0 | 125 | 0.5161 | 428.7 | 3.43 |
| 1.0 | 500 | 0.6481 | 1333.7 | 2.67 |
| 1.0 | 2000 | 0.7803 | 3898.1 | 1.95 |
| 1.0 | 8000 | 0.9126 | 10540.1 | 1.32 |
Show the full program
# Chapter 3. p32: the capacity price LRU pays for not knowing popularity.
# Model: a static cache that knows p keeps the C most popular keys and
# hits with the head share H(C). For the same H, the Che approximation
# says how many LRU slots are needed: bisect on T until the Che hit
# ratio equals H, then read the slots as the occupancy at that T. The
# ratio of the two capacities is LRU's multiplier. N = 20000 keys and
# the Zipf exponents are illustrative.
import math
N = 20000
def zipf(n, a):
w = [1.0 / (i ** a) for i in range(1, n + 1)]
s = math.fsum(w)
return [x / s for x in w]
def occupancy(p, t):
return math.fsum(-math.expm1(-x * t) for x in p)
def che_hit(p, t):
return math.fsum(x * -math.expm1(-x * t) for x in p)
def slots_for_hit(p, h, tol=1e-9):
lo, hi = 0.0, 1.0
while che_hit(p, hi) < h:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if che_hit(p, mid) < h:
lo = mid
else:
hi = mid
return occupancy(p, 0.5 * (lo + hi))
if __name__ == "__main__":
print("LRU slots needed to match a static top-C cache, N = {}"
.format(N))
print(" a C static hit LRU slots multiplier")
for a in (0.8, 1.0):
p = zipf(N, a)
for c in (125, 500, 2000, 8000):
h = math.fsum(p[:c])
s = slots_for_hit(p, h)
print(" {:.1f} {:5d} {:.4f} {:8.1f} {:6.2f}"
.format(a, c, h, s, s / c))Single source and citation
Fan, Y. (2026). Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts (Version 1.0.0), Chapter 3: Belady's Bound: Optimal Replacement, the Static Bound and the Capacity Price of LRU. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-327 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026327,
author = {Fan, Yafu},
title = {Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Doubling Illusion: Hit-Ratio Curves under Zipf Requests
- Chapter 2 · The Characteristic Time: Solving the Che Approximation by Bisection, and How Accurate It Is
- Chapter 4 · Marginal Returns: the Slope of the Capacity Curve and the Cost-Optimal Boundary
- Chapter 5 · Non-Stationary Requests: Popularity Drift, Frozen Lists and Cold Starts
- Chapter 6 · Partitions and Tiers: the Same Slots, Arranged Differently
- Chapter 7 · Eastern and Western Classics: the Nine-Year Reserve of the Royal Regulations and Belady's Optimal Replacement
- Chapter 8 · Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache