Every memory-tiering paper and every vendor deck reports a number of the same shape: this much slow-tier traffic was avoided, against this baseline policy, on these workloads. The question underneath it — given this trace and this fast-tier capacity, what is the least slow-tier traffic any placement policy could achieve? — has no standard instrument. So nobody computes it, and a gain of 30 % over LRU is reported without anyone knowing whether the ceiling was 32 % or 300 %.
The paper What Limits Memory Tiering? An Exact Oracle and the Workload-Intrinsic Floor on Slow-Tier Traffic builds that instrument, then tests what it implies. Three registered hypotheses about it are all refuted, and the reason they are all refuted turns out to be a structural result with a sharp practical consequence. I reproduced the package end to end before writing this; the numbers below come from its committed artefacts, and the demo is a script you can run on your own trace.
The construct, and what it costs to compute
Let phi*(c) be the minimum fraction of accesses that must reach the slow tier at fast-tier capacity c, minimized over all placement policies, with the full future known. It is a property of the trace's reuse structure and not of any policy, which is exactly what makes it usable as a ceiling.
It is also cheap and exact, because it is an offline paging optimum. The package certifies its optima three independent ways — a naive Belady emulation, an exhaustive cache-state search, and a lazy-heap implementation — and requires them to agree exactly, because a disagreement voids every later number:
- 200 random tiny traces: 0 disagreements between the naive and exhaustive routes
- 300 further tiny traces: 0 naive-vs-exhaustive, 0 heap-vs-exhaustive
- the naive and heap routes are identical at grid scale (
n = 4000, three capacities) - 624 (trace, capacity) pairs certified through a Mattson-style LRU-curve reconstruction: 0 disagreements
A control sits under it: a deliberately bad eviction policy must never come in below the optimum. It does not, over 200 cases — 0 violations.
On bounded working sets the optimum has a closed form, and this is the part you can use directly. For a trace of length N over a working set of W distinct items, at capacity c:
phi*(c) = ( (W - c)(N - W)/(W - 1) + W ) / N
Maximum absolute error against the exhaustive computation: 1.07e-4. So for the classic bounded-working-set shape you do not need a simulator at all — you can put a floor under your tiering claim with arithmetic.
First result: the deployed policy is not merely suboptimal, it is not even monotone
The intuitive picture is that more fast-tier capacity never hurts, and that the gap to the optimum shrinks as the tier grows. On a 42-cell grid over six trace families at three seeds per cell, the LRU gap to the optimum at h = 0.01 spans 5.99 % to 138.9 % and at h = 0.50 spans 0.0 % to 140.9 %. A 138.9 % gap means the policy moves 2.4× the traffic the floor requires; a 0.0 % gap means it is already optimal on that family. The sign of the effect is not a property of capacity, it is a property of the family.
The registered hypothesis was a two-limbed monotonicity claim. 0 of 6 families satisfy both limbs. Refuted, and the refutation is the useful part: there is no capacity at which you may assume your policy is near the floor.
Second result: the "capacity knee" is your policy's cliff, not the workload's
The knee — the capacity past which more fast tier buys little — is usually presented as a property of the workload. It is not. On cyclic working sets, LRU's relief from capacity strictly below the working-set size is exactly 0.000: adding capacity below W buys LRU nothing at all, on every one of those families. The oracle's relief on the same traces is 0.857 – 0.968.
Averaged over all seven families, the oracle's mean below-head relief is 0.896 and LRU's is 0.405. So roughly half of what the knee appears to say about the workload is a statement about LRU's eviction rule.
Third result: no profile statistic predicts the floor — and that is a theorem, not a fit failure
The obvious engineering response is to find a cheap predictor. The package tried eight candidates — the stack-distance quantiles sd_q50/q90/q99, the head-share statistics hs50/90/95/99, and the working-set size D — fitted on part of the data and held out on the rest, against a 5 % relative-error bar.
| capacity target | best candidate | held-out max relative error |
|---|---|---|
c_0.5 |
sd_q50 |
0.800 |
c_0.9 |
hs90 |
0.849 |
c_0.99 |
sd_q99 |
0.761 |
Every candidate misses the bar by more than 10×. The natural next move is to look for a better statistic. That move is unavailable, and the reason is the paper's structural result.
The result: the stack-distance profile does not determine the floor
Two traces can carry a byte-identical stack-distance multiset — hence, by Mattson's law, byte-identical LRU curves at every capacity — and still have offline optima that differ by 2×. Here is the pair, running:
from collections import Counter
A = [1, 2, 1, 2, 0, 1, 0, 2, 1] # the paper's matched pair (spike_v4.py: PAIR_A / PAIR_B)
B = [2, 0, 1, 0, 2, 0, 1, 0, 2]
def stack_distances(t):
"""sd[i] = number of DISTINCT items touched since t[i] was last seen (-1 on first touch).
LRU faults at capacity c exactly when sd[i] >= c."""
last, out = {}, []
for i, x in enumerate(t):
out.append(-1 if x not in last
else len({y for y in t[last[x] + 1:i] if y != x}))
last[x] = i
return out
def lru_faults(t, c):
return sum(1 for d in stack_distances(t) if d < 0 or d >= c)
def optimal_faults(t, c):
"""Belady's MIN over the known future -- the exact offline optimum."""
cache, faults, t = set(), 0, list(t)
for i, x in enumerate(t):
if x in cache:
continue
faults += 1
if len(cache) < c:
cache.add(x)
else:
nxt = {y: next((j for j in range(i + 1, len(t)) if t[j] == y), 10**9)
for y in cache}
cache.discard(max(nxt, key=nxt.get)); cache.add(x)
return faults
print(f"{'K':>4} {'n':>5} {'sd multiset identical':>22} {'LRU@c=2':>9} {'OPT@c=2':>9} {'ratio':>7}")
for K in (1, 10, 100):
a, b = A * K, B * K
same = Counter(stack_distances(a)) == Counter(stack_distances(b))
la, lb = lru_faults(a, 2), lru_faults(b, 2)
oa, ob = optimal_faults(a, 2), optimal_faults(b, 2)
print(f"{K:>4} {len(a):>5} {str(same):>22} {la:>4}/{lb:<4} {oa:>4}/{ob:<4} {ob/oa:>6.2f}x")
Output:
K n sd multiset identical LRU@c=2 OPT@c=2 ratio
1 9 True 6/6 4/6 1.50x
10 90 True 42/42 22/42 1.91x
100 900 True 402/402 202/402 1.99x
Read the middle rows together. At K = 10 both traces fault 42 times under LRU at capacity 2, and an LRU-curve simulator — the standard tool — will tell you they are the same workload with the same miss curve at every capacity. The floors are 22 and 42. On trace B, LRU is already optimal; on trace A it is 1.91× above a floor that is reachable.
Two honest qualifications, both of which sharpen rather than weaken it. First, the gap is capacity-specific: at c = 1, c = 3 and c = 4 the two traces' optima coincide, and only at c = 2 do they separate. So the question "what does the profile determine?" has to be asked per capacity, and the answer is "not the thing you are trying to predict". Second, it is not a hand-built freak: an exhaustive search over small traces found 184,275 traces collapsing into 28 stack-distance multisets, 13 of them (46.4 %) carrying more than one optimum. At the profile-class level on larger traces, 36 – 68 % of classes carry a spread exhaustively, and 1,791 of 2,510 (71 %) do at mid scale (n = 40, 60,000 draws), with a maximum ratio of 1.5.
And the effect does not decay with scale: the matched pair at K = 1000 (n = 9000) has phi_A = 0.2224 against phi_B = 0.4447, a stack-distance L1 distance of exactly 0.0, and a shared LRU curve that sits on the worse of the two.
What to do with this
- Put a floor under the number before you quote the gain. The floor is exact, it is an offline paging optimum, and on bounded working sets it is the closed form above. "We are 30 % better than LRU" means something quite different when the floor says the ceiling was 35 % than when it says 300 %.
- Do not look for a workload statistic to stand in for it. On this evidence the profile genuinely does not carry the quantity — it is not that a better statistic is waiting to be found. The stack-distance quantiles, which are the statistic anyone would reach for first, were among the candidates and were not the worst of them; the bar was missed by all eight.
- Check which capacity your claim lives at. The matched-pair gap exists at one capacity and vanishes at its neighbours. A claim stated for "the workload" without naming the capacity is not well defined.
-
Treat the knee as a policy property until you have shown otherwise. On cyclic sets LRU's sub-
Wrelief is exactly zero and the oracle's is 0.86–0.97, so a knee measured with LRU is mostly a measurement of LRU.
Reproducing it
cd papers/issue-120
bash reproduce.sh # full tier: recomputes all six artefacts, five figures, validates
# -> VALIDATE 41/41 / SELFTEST 7/7 plants caught / RESULT: PASS
Measured here at 94 s on CPython 3.13.9. The suite validates 41 claims tied to named sections, and it runs a control on itself: each check is re-run against a mutated copy of the artefact it reads, and all 7/7 plants are caught. A check that cannot fire is decoration, so this is the check on the checks. Two carriers are also cross-checked against their owners — the check count this README declares against the count the suite prints, and the Python build the manuscript names against the build the run log records — because both had drifted once and been returned by an editorial decision.
What it does not do: it rewrites the artefacts it owns (that is the point — it shows the stored artefacts are what the code produces), and the reference-layer re-verification re-fetches every identifier from arXiv and Crossref, so it needs network reachability and is not part of the run. The committed report is the record of the verification that was performed.
The paper, the instruments, the certified artefacts and the one-command reproduction are at github.com/argszero/silicon-science-cs, issue #120.
