Part I (§1–§4): the problem and the alternatives. What the window controls, why adaptation is hard, and what the original reactive climber already does well.
Part II (§5–§9): the controller. Each mechanism is introduced by the failure it prevents. Chapter 9 brings them together.
Part III (§10–§12): the evidence and the limits. Measurements, a diagnostic field guide, and a recap of the design.
Read one chapter at a time, or use Contents to jump. The expandable notes explain detailed decisions and their measured costs; you can follow the main explanation without opening them.
For a shorter first pass, read the cache layout (§1.2), the failure modes (§2.6), the controller map (§5), and the recap (§12).
A cache is a bet about the future. Recency and frequency offer two ways to make that bet, and real workloads need both. In W-TinyLFU, one number controls the balance: the admission window's share of capacity.
Recency policies (the LRU family) bet that whatever was touched most recently will be touched again soon. That is the right bet for drifting working sets: a user session, a batch job walking a table, a queue's write-then-read rhythm.
Frequency policies (the LFU family) bet on whatever was touched most often, which is the right bet for skewed popularity: hot products, hot keys, the Zipfian head that dominates most production traffic.
Each bet has a characteristic failure. A table scan can flush an LRU's working set; a shift in popularity can leave an LFU retaining formerly hot keys at the expense of new arrivals. Real workloads expose both weaknesses. A database page cache serves popular pages and scans; a CDN node serves viral objects and one-shot crawlers.
Neither philosophy is shipped pure; each carries a bias and pays to correct it. TinyLFU is frequency-biased, so W-TinyLFU puts a small LRU window in front of it to buy recency back. Merlin (OSDI '26) runs the correction the other way, buying frequency back for its 2Q lineage with an epoch popularity sketch and a ghost queue. Caffeine's correction is a single number, and choosing it is this document's subject.
So the question isn't "recency or frequency?" but "how much of each, right now?" W-TinyLFU makes that a physical quantity: a budget of C slots, split between a space that serves new arrivals and a space that guards the established core.
Caffeine's bounded cache splits capacity into two spaces with different admission rules:
The TinyLFU admission filter connects them. When the window overflows, its victim becomes a candidate for main and is admitted only if its popularity beats main's next victim. Popularity comes from a frequency sketch (a 4-bit count-min sketch, halved every 10·C accesses so reputations age). The filter is what stops scans: a once-seen key loses the popularity contest, flows through the window, and never touches main. The aging is what stops drift. Two details matter later: the filter admits a slightly-losing candidate with small probability (jitter that breaks pathological deadlocks), and the sketch is an estimate by design.
Movement is mechanical: new keys enter the window; window victims contest admission; admitted candidates enter probation; hits promote within main. An entry never moves between window and main on a hit. One number therefore controls the entire balance: the fraction of capacity that is window. At 1% the cache is nearly pure frequency; at 80% it is nearly LRU.
If the best fraction were roughly universal, a constant would do. It is not close. The chart below sweeps a fixed window across four real traces (no adaptation; every split is its own simulation): a looping scan wants no window at all and decays to nothing as one grows, corda is useless without a window and then plateaus, OLTP peaks in the middle, and the financial trace rises to a broad shelf. No point on the axis is good for everyone, and the spread between a trace's best and worst split runs from a few points to the entire hit rate.
Three consequences frame everything that follows.
That first consequence is the payoff for adapting at all. The reactive climber of §3 already collects most of it, so what this document adds is measured against that climber rather than against a static window.
Region sizing is not the only place adaptivity could live, and it is not a new place to put it. ARC (FAST '03) is the precedent: a recency list, a frequency list, and a boundary that moves toward whichever side its ghost lists say is starved. That is the same knob this document adapts, driven by a different signal (§4.4). The Middleware '18 paper on adaptive software cache management, which this design descends from, introduced the hill climber for W-TinyLFU and aimed it at two dials: the window size, and the frequency sketch's aging rate, where faster aging biases admission toward recency. Adapting the window was at least as good on every trace, so the sketch dial was dropped.
Later work mostly moved adaptation off allocation and onto a scoring constant or a global threshold. Cacheus (FAST '21) hill-climbs the learning rate behind LeCaR's expert weights, Hill-Cache (ICDE '24) the decay constant of an LRFU-style score, and Merlin (OSDI '26) adapts hotness and popularity thresholds. The pattern is structural. A constant or a threshold is an indirect dial, since its effect on the hit rate is mediated by the whole key population. Its response curve is workload-warped before the controller ever touches it, and it tends to need a correction of its own. Merlin carries a ghost queue because its thresholds misjudge hot and popular objects.
Caffeine largely gets the threshold question for free. TinyLFU admission compares two entries (the candidate against the incumbent victim) rather than testing either against a global score, so the admission bar self-adjusts to whatever the local contest is. What that leaves undecided is allocation: how much capacity each philosophy controls. That is a direct dial (move a boundary, capacity shifts), it is meaningful at every workload, and its units are the cache's own. So the region split is the knob, and everything else stays fixed policy.
The cache observes only the split it is currently using. Trying another split costs hits, and a later improvement might come from the workload rather than the move. These constraints make adaptation difficult even before we consider the shape of the optimum. The chapter ends with six failure modes that guide the design in Part II.
Call the objective HR(w): the hit rate as a function of the window fraction, workload and capacity held fixed. The phrase "hill climbing" suggests a smooth peak. What the sweeps actually find (§1.3 showed real examples; the appendix has more) reduces to four recurring shapes, and each one defeats a different kind of algorithm:
In optimization terms, this is a zeroth-order problem: the cache observes the objective's value, but not its slope. That value is noisy, the curve changes with the workload, and each move has a cost. The next four subsections explain these constraints.
An optimizer would like to evaluate HR(w) at several w and compare. The cache cannot: it runs one split, on live traffic, and observes only what that split earns. Everything else is a counterfactual.
Each sample provides four cheap counters: total hits, window hits, probation hits, and misses. These do not reveal the derivative dHR/dw, or how hit rate would change with window size. There is no paired trial at another split, and comparing samples taken at different times mixes the window's effect with changes in the workload (§2.4).
The classic answer is ghost state: ARC keeps metadata for recently evicted keys, so a "ghost hit" says you evicted this too soon, and each ghost list acts as a gravitational pull on the split, the hope being that opposing pulls settle at the right equilibrium. Caffeine rejects this family deliberately. The reason deserves precision.
A ghost hit answers "would this key have survived?", but pricing a resize needs "would this allocation earn more?", and those differ in both directions. The region might have needed to be far larger than the ghost implies before that key survived, with everything displaced from the other region silently charged against the move.
The benefit of growing a region is not uniform: it can be near zero until the region spans a reuse distance, then large (shape B above), so the marginal nudge a ghost hit justifies never crosses the gap. Sometimes the right decision is even to shrink a region and accept its losses because the other side pays better; per-key gravity has no way to say so. §4.4 adds the measured half of this argument.
So the constraint stands: every measurement is taken at the current operating point, and moving the operating point is the only way to learn about anywhere else. Exploration and exploitation share one live cache.
Three physical facts shape every design decision:
The natural goal signal is the sampled hit rate, differenced across samples: did the last move help? The difficulty is arithmetic. A window step's true effect is often under one percentage point, while the workload's own sample-to-sample swing is ±1–3pp on quiet traces and ±10–20pp on phase-structured ones. The difference measures the weather, not the move: a step gets credit when the workload happened to improve and blame when it soured. Here is what that does to a competent goal-metric climber (the reactive climber, which §3 introduces in full) on flat terrain, where the correct behavior is to stop:
Averaging isn't an exit either: suppressing ±15pp weather takes long averages, which means reacting slower than workloads change. The noise floor and the drift rate squeeze the usable bandwidth from both sides. The shipped design's answer (§5) is structural rather than statistical: find a signal in which the weather cancels, and reserve the goal metric for the few decisions nothing else can adjudicate, taken slowly and behind noise-cleared margins (§7, §8).
Classical feedback control regulates toward a known target; a thermostat knows the temperature it wants. Here nobody knows what hit rate the workload permits, so there is no hit-rate target to regulate toward. A PID loop built around an assumed target accumulates an error whose zero need not be attainable or desirable. Earlier designs tried this and produced the worst results measured on the benchmark (−32 to −98pp on flat terrain); anti-windup did not rescue them.
The task is instead extremum seeking: search for an unknown, moving optimum by making changes and observing their effects. Each change carries the cost described in §2.3. The density controller in §5 does use a balance target, but that target is derived from regional measurements, not from an assumed achievable hit rate.
The disqualification above applies to the goal metric. It does not apply to the density error of §5, and the distinction is the whole design. The controller of §5 commands a change in window size and the cache accumulates it, so the plant is a pure integrator and the proportional law of §5.3 is integral action with a setpoint, namely error = 0. There is no second integrator to wind up because the plant is the integrator.
So the PID result was not "integrators explode here". It integrated HR − target, an error whose zero was invented, through a plant that already integrates: a biased signal driving a double integrator winds to a rail and stays, and no anti-windup variant can repair a wrong zero. The density error's zero is a physical balance condition between two measured quantities, so it has a true zero by construction. The move that worked was not "avoid regulation" but put the integrator on a signal that has a true zero, which is also why §4.2's failure does not generalize to §5.
The rest of the design also has established control-theory names. They matter when judging whether a proposed change preserves the mechanism:
Together these make the shipped machine an event-triggered, non-dithering extremum seeker, and that too is derivable rather than stylistic. Classical extremum seeking adds a continuous dither and correlates the output with it, paying §2.3's motion cost on every sample (corda: every fixed window 33.3, an always-moving climber 22.8), so intermittent, revertible, adjudicated excitation strictly dominates it here.
Compressing the chapter: any adaptive-window design must answer six failure modes. Their names recur through the rest of the document.
| # | failure mode | the trap in one sentence | answered in |
|---|---|---|---|
| F-1 | Chasing weather | crediting window moves for the workload's own swings, so the window follows the noise (§2.4's chart) | §5: a within-sample signal in which weather cancels |
| F-2 | Churn at a flat optimum | terrain with nothing to find still charges full price for motion | §5: proportional control settles to a zero step |
| F-3 | Pinning while blind | a starved region produces no signal, and "no signal" read as "no value" holds an extreme forever | §6: starvation is declared, and triggers a real experiment |
| F-4 | Confident wrongness | the proxy's equilibrium is self-consistent, sighted, and wrong; no local evidence will dislodge it | §7: scheduled audits judged by the goal metric |
| F-5 | Amnesia | the controller walks away from a position it measured to be good, and nothing objects | §8: the anchor and the guard rail |
| F-6 | Polluted bookkeeping | events that are not capacity-earned usage leak into the counters and steer the sizing | §9.3: signal hygiene |
Two standing constraints ride along rather than being solvable. The lag limit: phases faster than the sampling cadence are invisible by construction, and the only goal there is to avoid catastrophe (§11). Run-to-run variance: on alternation-heavy workloads the outcome is basin-dependent, with identical runs landing ±8pp apart, which disciplines how this design is measured as much as how it behaves (§10.1).
Before the machine this document builds, Caffeine answered §2 with twenty lines of code, and for seven years that answer held. This chapter is that design on its own terms: what it is, why it works, the properties it turns out to have been providing silently, and where it breaks. It is not a museum piece. It still ships as the climber for caches up to 4096 entries (§9.1), it is the baseline every measurement in §10 is differenced against, and for a cache that wants adaptivity at minimal complexity it remains the design to copy.
The Middleware '18 paper (§1.4) posed the window question and answered it with the most direct instrument available: finite-difference hill climbing on the hit rate itself. Caffeine landed that climber in February 2019 and shipped it in v2.7.0, and it sized the window at every cache size until the density tier arrived. The whole law fits in a box:
Each constant is doing a job, and none of them was derived: they were found empirically against the stress test in §3.2. The period borrows the admission sketch's own aging sample, ten times capacity: long enough that a 1% window's hits are countable, short enough that a workload era contains several decisions.
The 6.25% seed is 1/16 of the range, floored at two entries so small caches can move at all; sixteen unreversed steps cross the whole range. The decay is the convergence the original implementation added when the raw Middleware climber kept oscillating around the best split. At 2% per sample the step halves in about 34 samples, annealing on an era's timescale rather than a trace's, since the restart re-arms it.
The five-point restart bar sits above per-sample weather on quiet traces (±1–3pp, §2.4) and far below a genuine era flip, which is measured in tens of points. Below 512 entries the same law runs gentler (grow-first, stretched period, slower decay) for §9.1's statistical reasons.
Two runs, both real. First, OLTP at 2048 entries, in the tier this law still owns. The trace is recency-heavy and wants a window that W-TinyLFU's static 1% default refuses it:
Second, the stress test the original implementation was tuned against, recreated with the law as it ships. A cache rarely serves one workload for life: the classic pre-cloud rhythm was interactive traffic through business hours and batch analytics overnight, and the same shift happens slowly as an application grows features that share its cache. The test compresses that into a splice of two bundled traces, a transactional vault workload for the day and an analytical loop for the night, so the optimal policy flips from LRU to MRU and back. At 513 entries the two regimes could hardly disagree more. Corda matches LRU only with the window wide open (a 1% window scores 0.6 against LRU's 33.3), while the loop rewards a closed one (a 1% window scores 45.1 where LRU scores 0.0):
This chart is the law's character in one image. It can be confused: the blips in the loop era are restarts kicked off by weather, each costing a sample or two before the walk re-converges, and the corda phases wander because at LRU parity every window ties. Its strength is that each move is checked against hit rate itself, and a large change restores a useful step size. In this test, those two rules let it recover after each transition.
The flips are deliberately more abrupt than typical production changes, making this a stress test of recovery. Merlin (OSDI '26) names this adaptation pattern as one its architecture cannot express. Every §4 family that swaps the goal metric for a proxy gives the property up somewhere, and §7 exists to buy it back.
Two of the law's load-bearing properties were discovered by the successor work, when removing them turned out to be expensive.
The reversal is the window floor. Nothing in the reactive law bounds the window from below except the cache's one-entry minimum; the 2% floor that protects the density tier (§5) does not exist here. It was never needed, because the reversal rule (the classic bold driver: keep stepping while the rate holds or improves, reverse the moment it drops) cannot sustain a run past a single worsening sample. Give the law more commitment (a noise band on the reversal, a longer period, a confidence gate) and the implicit floor silently goes with it. Measured, a banded reactive law walks corda's window to nearly zero, where TinyLFU refuses every new arrival against an established victim, and the hit rate falls 31.0 → 1.1. Any modification that lengthens a run must bring an explicit floor with it.
The restart is an era detector, and it re-arms magnitude only. Direction still comes from the comparison; what the restart buys is a step large enough to matter in the new regime, which is what both of Fig. 8's recoveries are made of. The same five-point constant survives into Part II's machine as its one definition of "the workload changed", read by a walk's crash bar (§6.4) and by the anchor's stand-down (§8.2).
The obvious repair for §3.5's magnitude problem is a band: reverse only on a drop that clears the noise, so runs survive jitter. Built four ways, it is dead everywhere. Real traces: +0.16pp mean over seven cells, never closing the gap to the shipped machine. Constructed families: five of six lose, by 10 to 26 points. A band buys commitment, and commitment without an adjudicator is a direction chosen by early noise that nothing can revoke. The reversal is the never-persistently-wrong property, and a band spends it. What a committed walk needs is a verdict on the evidence, which is §6's machinery.
The reactive climber is the baseline for §10's measurements. On the adversarial battery's 51 paired rows it is ahead of the shipped machine on 18; on 28, the machine's edge is under a point. On the real 205-cell corpus the machine wins significantly on 41 cells and loses on 9, everything else a tie, for a whole-corpus mean edge of +0.38pp.
Both directions are true at once: most workloads never needed the machine, and the ones that did, where a signal starves or an optimum sits across a plateau, needed it badly.
The reactive law's own real-trace losses have two shapes. Where frequency should own nearly everything, it hovers above the tiny optimal window and pays for the visit, occasionally landing under LRU. Where the optimum is far away at scale, it crawls (§3.5). On sharp frequency cliffs, meanwhile, it matches the static optimum that the density signal's bias gives away. One measurement hazard remains: on constructed traps its runs are bimodal, so a single-seed comparison reads near-parity and is wrong. Use three runs, or a seeded pair.
Three failure modes, all instances of §2.6's checklist, all measured. They are the agenda for the rest of the document.
For many caches, yes. This is the document's off-ramp. Below a few thousand entries it is not a compromise at all: it is what Caffeine runs today, because at those sizes a sample does not contain the information the density signal needs (§9.1). Above them it is still a pragmatic choice.
Twenty lines, one remembered rate, one signed step: a small implementation whose decisions follow directly from the hit-rate comparison. §3.5's prices are real, but they are collected mostly on adversarial constructions and at scales the tiering now assigns to the machine; on ordinary traffic this law is usually within a point of the best Caffeine can do (§3.4).
The larger controller spends additional complexity on the cases where this simple design falls short. For an implementation that stops here, two rules matter: measure any variant at three runs or more (§3.4), and if you extend the law's commitment, add the window floor its reversal was silently providing (§3.3). The following chapters explain the additional mechanisms and the evidence for their cost.
Most plausible answers to §2 were built and measured in this project's history. This chapter is the map: each family gets its idea, its virtue, and the measured way it breaks. The shipped controller is a composition of the survivors, so knowing why the others fail is what makes it legible.
The most direct answer to "no setpoint, no derivative" is finite-difference hill climbing on the hit rate itself: §3's incumbent, taking its place in the design space as family one. Its virtue is §3.2's: it judges moves by the actual objective, and the restart renews exploration when the workload changes. The shipped design keeps it in two roles: as the small tier's law (§9.1) and as the probe machine's walker (§6.3). Its three measured failures are §3.5's: it chases weather and churns on flat terrain (F-1/F-2, corda's 10.5pp), it cannot cross plateaus, and it learns one bit per sample. The last is the disqualifying price at density-tier scale: the magnitude of an imbalance is discarded, so a window that should move 30% of the range crawls there in decaying coin-flip steps:
Verdict: keep the goal metric where its statistics work, in small caches (§9.1) and in bounded, committed experiments that must cross plateaus deliberately (§6 re-uses this walker with its reversal rule retuned for that job).
PID and its relatives presume an error against a setpoint, and §2.5 explained why none exists. Tried anyway, in several dressings, the integrator is the part that fails: fed a proxy error with no true zero it winds the window to a rail and keeps it there. The measured best was lag; the measured worst was the largest regression in the benchmark's history. Regulation machinery answers a different problem.
If HR(w) were a parametric curve, a controller could fit it from a few probed points and jump to the argmax. Fig. 3 is the refutation: plateaus, cliffs, and steps are not quadratics, so a parabola fit invents a maximum wherever the noise leans. The family also pays §2.2 twice: measuring each fit point costs an excursion plus settling time, and the workload drifts out from under the fit while you collect them. Measured: unstable jumps, no configuration that beat the simple climbers.
ARC's ghost lists, and their scaled-up form (shadow-simulate alternative configurations, switch to the winner), are the only family that genuinely answers §2.2. Rejecting them was a considered decision, on three grounds. The §2.2 argument: a ghost hit prices a key, not an allocation, and allocation value is non-uniform, so per-key gravity neither crosses valleys nor authorizes profitable sacrifices. The cost: ghost metadata scales with capacity, charged to every deployment for the minority of moments adaptation binds. The measured record: the approach has not proven better. On a LIRS loop trace at small sizes the ghosts miss the cycle entirely and don't help; at larger sizes ARC improves only modestly on LRU. Ghost feedback can be a useful ingredient (Merlin uses ghosts to compensate its threshold adaptation), but as the load-bearing signal it buys little for its footprint, which makes the footprint hard to justify.
The shipped design's §6 machine is this family rebuilt without ghosts: instead of simulating the counterfactual in metadata, run it for real, briefly, under a budget, and undo it if it disappoints. Reality is the one simulator with no fidelity gap; its cost is bounded by discipline instead of memory.
Run both philosophies as "experts", score them, switch or blend. Scoring an unplayed arm needs ghosts (§4.4); A/B-ing in time inherits the weather (§2.4); and switching churns state (§2.3). Measured, the switching was driven by noise rather than merit. A late, subtler variant (blending a goal-metric nudge into steering continuously, gated by a confidence estimate) was built and instrumented carefully enough to deserve its own autopsy (§8.3). It fails for a reason that generalizes: continuous authority granted to a noisy judge is authority exercised by noise. The shipped design grants the goal metric authority only in discrete, committed, adjudicated doses.
Perhaps the split could be looked up: measure skew or reuse-distance shape, map to a window. Two measurements close the road. Online skew estimators showed no usable correlation with the optimal window across the corpus (recency demand is about the timing of reuse, not the popularity histogram), and near-zero skew readings actively mis-steered looping workloads. The project's standing rule came out of this: classify your signal, not the workload. Decide per sample whether each measurement is trustworthy, rather than which archetype the traffic resembles. The starvation bar (§6.1), the stillness clock (§7.3), and the noise-cleared margins (§8.1) are all signal classifiers.
The last family drops both the cross-time comparison and the counterfactual and asks a within-the-moment question: of the capacity I own right now, which region earns more per slot? If one region's slots out-earn the other's, capacity is worth more there. No memory, no model, no ghosts, and one decisive property, developed in §5: both regions are measured in the same sample, so the workload's phase affects both regions together, allowing that shared effect to cancel.
The limitations are just as important. The signal sees only residents (F-3 remains), and measures average rather than marginal value. Four attempts to measure marginal value directly each traded gains on some workloads for losses on others (§11.1). Density can also settle at a self-consistent but suboptimal split (F-4). Part II starts with density steering, then adds a mechanism for each limitation.
The steering heart of the design: compare what each region's slots earn within one sample, and move capacity toward the better earner. This chapter derives the signal, shows why the weather cancels out of it, sets its three constants, and then states plainly what it cannot do. The three things it cannot do are the next three chapters.
| condition | mechanism | judge |
|---|---|---|
| C ≤ 4096 | reactive climber (§3) | hit-rate direction |
| ordinary large-cache sample | density steering (§5) | regional hit density |
| small region is starved | probe walk (§6) | density against the frozen displaced edge |
| position has remained still | audit walk (§7) | hit rate against a frozen reference |
| sustained shortfall from a proven position | anchor veto (§8) | noise-cleared hit-rate margin |
A slot of capacity is worth the hits it produces, and within one sample each region's hits are counted directly. So each region has a hit density: hits per slot per sample.
dw = windowHits / windowSize dm = mainHits / (C − windowSize)
If the window's density is the higher one, its slots are out-earning main's and the split should shift toward the window. If main's is higher, the window should shrink. Equal densities mean rest. The steering error is the log of the ratio,
error = ln(dw / dm)
taken as a log so that the two directions are symmetric: "the window earns three times main" and "main earns three times the window" become +1.10 and −1.10 rather than 3.0 and 0.33. The sign says which way the split is out of balance and the magnitude says how far. Two integer counters implement it.
One caveat belongs here rather than later. Density is an average yield per slot, and the economic goal is to equalize marginal yields. The two are not the same, and §5.6 measures the bias the difference introduces.
This signal has the property that decides the design: the weather cancels out of it. Suppose a rough phase scales every region's earnings down by the same factor α, unrelated to the split:
error′ = ln(α·dw / (α·dm)) = ln(dw / dm) = error
The common factor cancels. Changes in the cacheable fraction of traffic can affect both regions together; comparing their densities within the same sample removes that shared effect. This is the advantage over §2.4's comparison across samples.
Cancellation is only first-order. A phase that shifts reuse between short and long distances changes the ratio, as it should: the preferred split may have changed too.
The same corda trace that defeated the reactive climber, under this controller:
step = sign(error) · min( 0.30·C, |error| · 0.03·C ) window = max(window + step, 0.02·C)
This is proportional control: move hard when far out of balance, barely at all near it. The reactive law needed a decay to converge and a restart to re-energize; here both come from the error's own magnitude. Three constants, three rationales:
Writing the error in shares makes its resting place explicit, taking logit(p) = ln(p/(1−p)) for the log-odds:
error = ln( (Hw/Cw) / (Hm/Cm) ) = logit(hitShare) − logit(capacityShare)
So error = 0 exactly when capacityShare = hitShare: each region holds capacity in proportion to what it earns. That equalizes average value, and the optimum equalizes marginals, H′w = H′m, the classical condition for partitioning a cache (Stone, Turek & Wolf 1992). The step is proportional to a log ratio, so it moves multiplicatively on the capacity simplex, which is what makes the gain scale-free.
The gap between the two conditions predicts §5.6's give-back, sign included. On a concave hit curve average ≥ marginal; write g = A − M, which widens as the curve saturates. At rest the averages are equal, so the marginals differ by gm − gw and the larger gap marks the over-allocated region. The window is an LRU serving tight reuse and saturates fastest, so the window is over-allocated. That is the typical measured 0.5–2.5pp given back on frequency-optimal traces, with larger witnesses recorded in §11, and closing it means steering on marginals. The machine already measures probation's, §6.4's frozen baseline, and uses it in the verdict; steering on marginals directly was built and measured, and §11.1 records the frontier that keeps the average form at the wheel.
The same lens explains shape B. A deceptive valley is a stretch where the hit curve is not concave, and there every first-order matching rule rests self-consistently inside the valley. F-4 is not a defect peculiar to this proxy but how local rules behave on non-convex terrain, and the textbook escape is the one §6 builds: large-amplitude committed excitation, since extremum-seeking stability is only local (Tan, Nešić & Mareels 2006). §6.3's escalating stride is that amplitude term.
Measured, the prediction holds and the escape does not. On P3 @152508 (Fig. 4b) the error crosses zero at a 1.4% window against an 80% peak, losing 3.59 points; on fiu_webmail @195466, 6.9% against 90%, losing 4.55. A unimodal control rests for 0.00, so the controller has arrived, in the wrong basin. §6's walk cannot help: it is gated on blindness, and these windows are not blind. P3's earns two orders of magnitude above §6.1's bar; it is a low-quality earner rather than a silent one, and the bar counts hits, not precision, so no corner is declared. §7's audit is inert on the class. §11.1 carries this as the limit's open half.
The formula divides by earnings, so a region that earned nothing needs a rule of its own, and this corner held two real defects. The obvious guard, a tiny ε in place of zero, is the wrong one. Against a starved region, ln(dw/ε) is an error of about twenty nats, the strongest command the controller can emit, and a handful of stray hits on the other side is enough to buy it. The repair gives the signal's two consumers different floors. For steering, a starved region's density is floored at an eighth of the starvation bar spread over the region, so "earned nothing" is priced low rather than infinitely low. The probe verdicts of §6 keep the ε form, because they only run behind a bar that guarantees real signal.
In an otherwise-dead sample (a pure scan phase), six stray window hits produced a +17.4-nat error and a full 30%-of-C step. A background trickle of 0.019% of requests, riding a victim's own scan phases, steered the window from 3% to 48% of the cache and cost the victim 8.3 points; at a 0.4% dose, 9.6 points. With the steering floor both doses measure flat.
One asymmetry survives deliberately: when main earns exactly nothing while the window earns anything, the error is enormous and the window balloons toward its structural maximum. That is a chosen prior: a region earning something takes everything donatable from a region earning literally nothing, and it is what rescues the cache when a scan has filled main with dead weight. Workloads that repeatedly black out main for a few samples pay ~1.2pp per episode for it, measured far above LRU throughout; the family built to trigger it on every other regime prices the prior at ~8pp against the static ceiling, and §11 carries that entry.
Each decision consumes a sample of 4·C requests. Shorter periods allow more decisions but produce noisier densities; at 2·C, verdict noise prevented measured escapes. Longer periods leave finite traces with too few decisions. Four capacities per decision is the measured compromise.
The period is also capped by the sketch's aging period, which counts entries rather than bytes, so a byte-weighted cache cannot inflate it by its mean entry size. Elapsed time depends on capacity and request rate: adaptation may take minutes or hours in production. Sampling is a by-product of maintenance, so these decisions add no work to the request path (§9.3).
With the virtues and debts on the table, each of the next three chapters pays one debt: starved-and-wrong gets the probe machine (§6), sighted-and-wrong gets the audit (§7), and "the controller optimizes a proxy" gets the anchor and guard rail (§8).
Where the density signal admits it cannot see, the climber runs a real experiment. It walks the window for a bounded time, judges the result against the alternative at its true price, and undoes everything unless the walk clearly won. The state machine below is the whole shape; the rest of the chapter takes each transition with the workload that breaks without it. The stakes are the design's first requirement: without this machine, pure density steering can park about 28 points below LRU on a constructible workload and never leave.
A region is starved when its hits in a sample fall below the bar,
max(4, requests/1024): one hit per thousand requests, floored for short
samples. The constant was calibrated, not guessed. Trapped regions measure about two
orders of magnitude below it, while floor-sized windows on frequency-bound traces earn
comfortably above it. The bar is a signal classifier in §4.6's sense. It asks "is this
measurement meaningful?", never "is this workload recency-ish?"
One fact shapes everything after. No threshold separates "starved because trapped" from "starved because the workload has no recency to offer". The two overlap on every resident-only statistic tried, per-entry reuse flags included; from inside the cache they look identical. That is why what follows runs experiments instead of computing a smarter predicate.
Starvation alone does not trigger a probe. The rule is the blind corner: probe only when the starved window is small. A window starved at a quarter of capacity or less probes upward; a sample in which both regions are dead probes away from the nearer wall, splitting at half. A large starved region needs no probe, because the other region's density already says what to do, and probing on its behalf is destructive. The scar behind that rule: a scan fills main, main earns nothing, and a naive rule concludes that the small, hard-working window should be raided mid-scan. An early variant lost double digits on corda to that logic.
A starved main beside a large window arms nothing either. At that wall the ratio can only point upward, so the window cannot move, stillness accrues by construction, and the audit of §7 owns the re-test. A probe once armed at that corner; it confirmed onto positions main could not price, and deleting it read as a gain or a tie on every cell where it had fired. Small-and-starved is the only corner where nobody can see and nothing else will look.
Inside the corner, control reverts to the goal metric. The walker is §3's climber, brought back for a bounded walk with its weaknesses patched for this job in three ways.
The machine remembers its launch point, and undo means returning there, step-capped with the remainder carried across samples. While a probe's aftermath cools down (the refractory), blind-corner samples hold still entirely. Falling through to a steering step during that hold was how the stray-hit trickle of §5.4 once bought its oversized steps.
A walk can end through a crash, a reversal back past its launch point, its budget, or adjudication (Fig. 14). A crash compares the current hit rate with the rate frozen at launch: how much has the walk lost overall? A reversal compares the current sample with the previous one: did the last stride hurt?
These comparisons measure different things, so their thresholds need different treatment. They share a threshold only where both are based on the same estimate of sample-to-sample scatter. Only adjudication can keep the new position.
Probe damage and a workload shift are indistinguishable at a single crash, so the retry price stays gentle (no backoff doubling) for one. A shift moves the rate once; a probe whose own damage crashes it does so on every attempt, so the second consecutive crash escalates on the walk's own ladder: audit crashes count on the audit layer's streak and rung, starvation crashes on the probe machine's, because on the shared form three exogenous pulses, paired with three lone audit crashes, drove the machine to the deepest rung and a 130-sample stand-down at the floor.
A starvation probe's bar is priced against the workload's own scatter: three measured deviations, floored at 5pp and capped at 15pp. Unpriced, weather aborted the walk that is a blind corner's only exit, and uncapped, all-blind workloads whose scatter is enormous let damaging walks roam; the cap keeps a real collapse aborting. The deviation is read live rather than frozen: the walk's own transient lifts the bar for as long as the walk is exposed to the weather.
An audit's walk keeps the absolute 5pp in depth (every depth pricing traded real-corpus basin cadence for constructed prizes), capped at 15% of the rate frozen at the arm. The cap exists because the threshold is a level test: a workload earning less than 5pp in total can never trip it, leaving a walk that halves the hit rate bounded by nothing but its budget (arc_S3). The cap binds only where the launch rate is under a third and is inert everywhere above it, so it narrows the bar where the absolute one is vacuous, the opposite of the pricings that died. The audit also prices persistence in time. A first audit crash aborts on its first below-bar sample, like a starvation probe. The retry of an equilibrium that already crashed one audit tolerates two below-bar samples, holding its committed direction at a decayed stride while the dip is adjudicated, and aborts on the third. Two samples of tolerance cross the terrain valley that a one-sample abort made an absorbing horizon (the moat family: the far bank is one stride past where the abort fired, at every rung), and they absorb one-sample pulses. A sustained collapse still aborts at 5pp, and a first abort stays cheap everywhere, since tolerance on every walk made short traces pay for longer failed excursions.
The cross-back rule exists because one noisy blip once converted an up-probe into an unterminated down-walk that ground the window to a single entry. A starvation probe's reversal shares its crash bar, both being priced from the same live scatter. An audit's reversal takes the same 15% of the larger of the frozen rate and the noise band, under the same absolute 5pp cap: a difference test must never be priced below the noise it has to survive, and a reversal through base is charged as a completed failure (it doubles the audit ladder and its wait), so a bar the noise can trip is expensive. Priced by the level alone it was: on the give-back sentinel that exposed it (shieldtrap) the bar measured a median 0.28 deviations, and one walk died to a 0.17-deviation sample at a 14.4% window that, held, confirms at 56.4%. The level is not a new constant: 15% of the three-deviation band is 0.45 deviations, with a measured cliff at 0.5, so do not re-derive it. The absolute cap is what keeps the noise term out of the widening family every dead audit-bar candidate died in (§11).
That verdict took five designs, and both of its choices are load-bearing. Why probation: follow a window-grow through §1.2's geometry: the quota comes out of protected, protected overflow demotes into probation, and probation expels its coldest tail. Probation's edge is what the grow displaces, so it is the true price. Why frozen: the walk contaminates its own evidence, since its demotions push warm entries into probation and enrich the live rate while the walk runs, so a live comparison becomes a veto that always says no.
Judging against main's average (the obvious simpler form) vetoes winning positions because the average is dominated by the protected core the grow never touches: a family of modest-reuse-band workloads sat 14–17 points below its achievable rate under that verdict, and three other trap families traded the same way. Judging against live probation was demonstrated to be absorbing on a construction with a protected-saturating hot core: the live variant pinned at the floor with zero confirmed probes ever (58.9) while the frozen baseline escapes (67.2). Freezing means the snapshot can be stale by walk's end; accepted, because every re-arm re-snapshots, so the error heals on the next attempt instead of compounding. Downward probes keep the plain average test (a window is one LRU; its edge is its average). "Neutral must fail" exists because an early version that kept no-better-no-worse positions let steering walk the window home and the probe re-fire, forever. The one priced trade: on a bistable low-hit-rate synthetic whose probation concentrates the reuse band, the frozen baseline vetoes an escape the sloppier average form occasionally confirmed by luck; no real-trace echo across the defended set, kept as a named sentinel.
In short, a walk ends by crash, reversal, budget, or verdict. The first three undo it. Only the verdict can keep it, and only against the price the walk actually displaced.
The subtlest mechanism resolves a real dilemma. When the window grows, its ledger fills with hits that are not evidence. Transferred hits come from probation entries that a grown boundary relabels as window entries, so their ordinary traffic now counts as the window's. Stray hits come from the extra slots incidentally catching re-touches the window deserves no credit for. Both grow with the window's size while their density stays low, so a deep walk manufactures its own earnings. Against a fixed adjudication trigger this cuts both ways. Where the small window is correct, strays trip the trigger early and the probe exits cheaply, which is right. Where the small window is a trap, the same early trigger fires one stride short of the reuse band, the verdict fails on stray-quality evidence, and the trap becomes absorbing. No single exit rule wins both cases; four rule families were measured onto this tradeoff.
Escalating commitment keeps early attempts cheap while giving repeated failures a way out. The first probe may stop at its first judgment opportunity.
A failed verdict deepens the retry rung: 16 → 32 → 64 samples, and incurs the corresponding refractory wait. A confirmation immediately reversed by steering also deepens the rung, without that wait. Crash endings follow §6.4's separate rule.
The deeper rungs require at least two, then ten, samples before adjudication can end the next walk. This commitment carries the probe beyond the stray-hit zone. It applies to confirmations as well as failures: an early confirmation on stray evidence would reset the ladder before the walk reached useful territory.
On the measured steady trap, this escalation produces an escape in about three rounds, roughly 100 samples. A workload whose floor is correct does not escalate far enough to pay the deep-walk price; its retries become rarer. Exempting confirmations from the minimum depth had a measurable cost: a long-trace escape fell from 53.3 to 38.7.
A confirm can be reversed because the two prices differ. The verdict compares the grown window with the probation it displaced; steering compares it with main's average, which the protected core dominates. When the window out-earns a thin probation edge but not the core, the verdict keeps the position and steering walks it home in the same sample. That round kept nothing, so the ladder counts it as a failure. Rewarded instead, the probe would repeat at the first rung and never commit a walk past a band that a first-round stride cannot reach.
One full episode, on a constructed reuse band behind a wide stray zone:
The probe machine is §4.4's family rebuilt without ghosts: it doesn't simulate the counterfactual, it briefly becomes it, on the real cache, where measurement has no fidelity gap. Every discipline above bounds the cost of that experiment: arm only where the incumbent signal has recused itself, walk under budget, judge against the frozen true price, undo everything short of a confirmed win, and pay for repeated failure with patience instead of damage. On workloads that never trap, the whole machine amounts to a few shallow walks per era, measured on the real corpus as a ~1pp premium on three cells and nothing elsewhere. The premium is small because the payout is rare and large.
The probe machine fires where the signal admits ignorance. The harder case is a signal that is sighted, settled, and wrong: every region earning above the bar, share-matching satisfied, and the cache resting on the wrong shelf of the terrain indefinitely. Since no resident-only statistic can detect this state, the design stops trying to detect and periodically tests: long-held positions get re-examined by the same walk machinery, judged by the goal metric.
The audit. An audit becomes due when the positional-stillness counter reaches its current wait, normally 32. At the next eligible decision, it starts the §6 walker toward the farther wall. Each sample adds one to the counter when the window differs from its previous sampled position by no more than 2% of capacity; a larger move subtracts one, down to zero (§7.3).
The first audit after a start or a resize is a cold-start calibration, due after only four still samples. It uses §6's strides and crash, reversal, and budget exits, with the audit's own thresholds from §6.4.
The audit keeps its own rung and crash streak, separate from the starvation probe's. Only a completed failure at the deepest rung doubles the wait between audits, up to 512 samples. A settled workload is therefore re-tested less often.
Both triggers drive the same walker, so the two are easiest to read side by side. The strides, the exits and the budget are shared; the arming, the pricing, the judge and the retry schedule are not:
| contract | starvation probe (§6) | audit (§7) |
|---|---|---|
| arms when | the starved region is the small one | the stillness counter reaches its wait: normally 32, or 4 after a (re)size; movement of at most 2% of C counts as still (§7.3) |
| direction | away from the wall the starved region is pinned against | toward the farther wall, alternating between audits; a park's first audit follows the walk that confirmed it while the claim stands |
| crash bar level, vs the rate frozen at the arm |
the live scatter, clamped to 5–15pp | 5pp, capped at 15% of the frozen rate |
| reversal bar first difference, vs the previous sample |
the same bar | 5pp, capped at 15% of the larger of the frozen rate and the scatter |
| crash tolerance | aborts on the first below-bar sample | the same, except a retry after a crash, which tolerates two and aborts on the third |
| judged by | density, once the watched region earns 4× the starvation bar: against probation's density frozen at the arm growing, against main's average shrinking | the goal metric, after a committed depth of five samples: four consecutive raw samples over the frozen reference plus the 1% margin, and at least one sample that beat the walk's own start |
| on a confirm | keep it, plant the anchor, reset the ladder (deepen it if steering reverses the position at once, and park if that reversed confirm came at the deepest commitment with the goal metric's confirmation); steering resumes | keep it, plant the anchor, and park, since density disagrees with the position by construction |
| on a failure | undo in full; the refractory doubles 16 → 32 → 64 and the next walk commits deeper (2 samples, then 10) at scaled strides (×2, ×4) | undo in full; the wait doubles toward 512 only on a completed failure at the deepest rung, and a crash never moves it |
Both are bounded at sixteen samples, and the two ladders are strictly separate: an audit's endings never deepen the probe machine's rung or streak, and a starvation confirm leaves the audit schedule untouched.
Direction. The walk alternates at interior positions. A park's first audit is the exception: it follows the walk that confirmed the park, while the park stands and the smoothed rate has held within a restart threshold since the confirm, because a confirm ends a walk on evidence of improvement rather than on its exhaustion. A direction with less than one stride of room is refused: a walk sent into a nearer wall clamps on its entry stride, stands still for the rest of its budget, and that information-free expiry would be priced as a failed experiment, doubling both the refractory ladder and the audit clock.
Why the calibration arms at four. A sighted false equilibrium pins from its first sample, and waiting the standard clock spends most of a short trace motionless while the reactive tier would have been exploring from sample one; the mixture trap's entire deficit against it was this prefix. Every later wait uses the standard clock, and the schedule belongs to the audit layer alone: a starvation probe's confirm leaves it untouched, because the landing that confirm validates is density's opinion, which is what an audit must not take on faith. (That confirm once reset the schedule to the standard wait, spending the calibration before the first audit ever ran and handing the §7.3 position jam a 32-sample bar that ordinary burstiness can keep breaking; the same cross-subsystem latch shape as the fresh-park shield's, §8.2.) The priced cost has two parts. One is an early misconfirm window on a steadily rising workload, since a trend clears any raw streak (regimeramp ~−1.3 once the walk-beats-start gate recovered part of it, bounded by the shield plus the next audit). The other is the calibration's exploration on short traces whose escape came from a starvation probe (mixture d025 ~−0.9, still above LRU with a steady state 3 points over). The prize on sighted traps is the whole prefix (mixture stock +18.7, to above the reactive arm).
Ordering. An audit may also arm from a blind-corner sample the probe machine would otherwise spend holding. The blind-corner gate outranks the goal-metric branches, which is right for the guard rail (it adjudicates a shortfall on the starved sample) and wrong for an audit (it adjudicates over the samples that follow). With the audit ordered beneath the gate, a corner that never cleared sat motionless through its whole refractory while the clock said the position was due.
Cadence. The audit's endings neither deepen the starvation machine's ladder (which sets that machine's stride and commitment), nor re-arm its refractory, nor inherit its escalation. An unconfirmed audit retries on its ladder's cadence; a crash, lone or streak-escalated, keeps the cadence at any rung, because deferring the retry is what an exogenous pulse train would want.
One question decides whether audits work: who judges the walk? The first implementation reused the probe's density verdict and failed in the most instructive way in this project. On a wide-window equilibrium the audit walked the window from 80% of the cache down to 20% with the hit rate rising the whole way, and density failed the walk at depth five. The failure was structural: the audited position is density's own attractor, every step away registers as imbalance, and so the signal being audited also decides the audit. A proxy cannot adjudicate the re-examination of its own opinion.
The audit verdict. Audits are judged by hit rate. Confirmation requires all three conditions:
The reference is the smoothed rate of the position the walk leaves, frozen when the audit starts. Freezing prevents the walk from changing its own benchmark. Without confirmation, the walk exhausts its budget and undoes its movement, unless a crash or reversal ends it earlier.
The anchor's claim serves a different decision: whether the guard rail should return to a previously proven position. Using that claim to judge an audit could demand a hit rate from a workload regime that has already ended.
The claim was the reference for as long as an anchor was planted. It re-syncs to the live rate only while the window stands on the anchor, so a claim planted before a regime shift that lands with the window elsewhere outlives the regime that earned it, and every audit armed away from the anchor was judged against it. On the constructed witness the audit walked from a 23% hit rate to a 53% wall, sat there for ten samples, and failed at budget against a claim of 58% (31.2 against a 54.1 ceiling at 128 samples). On a real cloud-physics trace a claim planted while the cache filled held the confirm off a genuine prize and the walk ran past it to the floor (44.1 → 46.1 with the reference it leaves). Measured against the rate it leaves, the witness reads 48.5, sixty of the sixty-eight battery rows are bit-identical at eight seeds, and the rest move by 0.2 or less, or by a redraw. The alternative, discarding the claim on a swing that lands with the window still, is dead: the terrain's own collapse at the position a retreat left the window on is a still swing too, and there the claim is the memory the rail recovers the prize with (see the anchor rules below).
The bar is deliberately not priced by the rate deviation the way the rail's is. The deviation is workload-scale while the effect an audit resolves is the window's 1–10pp marginal contribution, and a deviation-priced confirm measured inert on every real cell of a 32-trace corpus: bars of 4.3–62.4pp (median 20.7) against 1–10pp effects, the 1pp floor binding on none, with instrumented walks measuring real +5.4pp and +11pp gains and rejecting them. A consecutive run prices the bar by run-length statistics instead. That is a sensitivity gain of roughly 2–3×, not noise-independence: the walk offers about a dozen overlapping chances, so a neutral position under symmetric scatter still leaks confirms at a material rate, and the priced costs on trending openings are this exposure. But the streak needs the positional gain to clear only the per-sample noise trough rather than three deviations, and raw samples carry no smoothing lag, so a confirm lands at the position that earned it. The asymmetry with the rail is intentional, since a false confirm self-heals at the next audit while a false veto churns the anchor continuously.
Why the streak alone is not enough. The reference is an absolute rate, and it can be older and colder than the walk it judges. That is sharpest for the cold-start calibration audit: it arms while the cache is still filling, so the anchor still carries the rate earned cold, every post-warm-up sample clears it, and the streak completes on the warm-up ramp alone, confirming whichever position the walk had reached by then. On a stationary control whose optimum is a 1% window, the first audit confirmed a 32.6% window while the raw hit rate was falling, and the landing spot is structural rather than incidental (the floor plus five 6.25% strides, about a third of the cache; measured at 0.326, 0.327, 0.344 and 0.361 across four independent constructions). The repair is a necessary condition rather than a re-pricing: the walk must match or beat its own starting sample at least once (inclusive and margin-free: a saturating arming sample makes a strictly-greater bar unsatisfiable, which silently disabled later confirms on a cadence sentinel). Re-pricing was tried first and trades: lifting the streak's bar to the arming sample, or to the smoothed rate, costs 2.5pp on a noisy escape, because a streak against a noise-inflated bar is fragile while a one-shot "did this ever help" gate is not. The separation is wide rather than marginal: the escapes beat their starting sample by 11.7–33.7pp, while the cold-start misconfirm never beats it at all (−0.18pp).
Sighted false equilibrium. The whisper pin, the §7.1 shape built as a trap, converts from 9 points below LRU to 2 above it (55.5 → 66.8 against LRU's 64.6). The streak verdict buys the escape, and the cold-start calibration removes the pinned prefix.
Hit-rate weather. The escape survives rate modulation that defeated the earlier deviation-priced verdict. Under ±8pp of modulation the audit still reaches approximately LRU (65.2 at period 12, 64.5 at period 6) where the reactive climber reaches 59.4. A deeper dose crosses the audit's crash bar once, and §6.4's crash-streak tolerance repairs that to within half a point of LRU. The mixture family under the same modulation clears LRU on every seed (48.0 → 56.6 against 55.3), and the at-scale pins escape as far as each trace lets the ladder escalate.
Real corpus. On real traces the layer is neutral insurance on average (−0.03pp) and decisive on a few cells. On one cloud-physics cell (cp_w097 at 16k) the audits are worth 3.3 points, and the machine still finishes 3.2 behind the reactive climber there, because its confirms land at high windows, around 56% and 26%, rather than at the broad 5–15% static optimum. §11 separates that recovery from the steering bias it cannot repair.
Layer ablation. Across the 52-row constructed battery, removing the audit costs about 21 points for every one it returns (268 points lost over the 31 rows it helps, 13 regained over the 16 it hurts, worst single row 2.4). The gain is concentrated: without the audit, all eleven whisper, jam and pulse-train rows collapse to about 55.5, and the at-scale mixture pins collapse to 31–35. The rows it hurts are already far above LRU, and those losses are the duty-cycle price carried into §11.
Reading rule. Do not credit the bimodal-alternation battery mean to this layer. With N=8 and the arms rotated the audit is roughly inert there; the density tier produces the value on those rows.
The clock behind "32 still samples" carries a lesson from hostile review. The first clock counted calm: samples without a big rate swing and without a big commanded step. Both halves are the wrong observable. A periodic crash-scale rate swing that arrives faster than the wait, which bursty traffic can produce innocently, zeroes a calm-based clock forever and disables the layer built to catch confident wrongness. And "no large commanded step" confuses the controller's requests with the cache's state: a position held against discarded commands, which is what the guard rail produces, is a held equilibrium worth auditing. The repaired clock counts positional stillness only. Samples whose actual window stayed within the band accumulate, and rate events never touch the count. It is a band rather than a point because held equilibria orbit; the transfer geometry alone keeps the window wiggling.
A later hostile review taught the same lesson from the other side. Positional stillness with a hard reset is an observable an adversary can drive too. A count that zeroes on any move past the band never completes if the window can be made to move once per wait, and density commands such a move for a modest earnings imbalance, a factor of about two between the regions (eband/gain). A whisper construction that merely modulates the delivery of its trickle, with the same volume, the same optimum, and LRU and every static window unchanged, held the count at zero on 121 of 122 samples and pinned the climber 8.9 points below LRU, at the audit-free value. It still jammed with ±50% jitter on the burst timing, so this was not an alignment stunt.
So the repaired clock decays by one on a moving sample instead of resetting. A mostly still workload still accumulates toward its audit, while a window that moves on at least half its samples, real motion rather than a held orbit, never accumulates. That half-motion threshold is analytic rather than realizable. Measured 50% and 67% motion cadences fail to jam, because steering does not hold a clean partial alternation, and the decisive control is that the audit-free arm outscores the layer there, so the layer is inert rather than suppressed. That leaves motion on every sample, aligned to the grid, as the only starving cadence (§11). The decay of one per moving sample is what the recovery rests on. The burst cadences that recover do so because the calibration audit gets a foothold, parks, and the park's own stillness sustains the audit cycle.
After a confirmed probe that density keeps, the retry ladder resets so re-probing is cheap (phase alternation depends on it), unless the confirm only re-finds ground the ladder had already confirmed and lost, which deepens it instead. An audit inheriting that reset would re-arm within a sample or two, so the audit retry is floored at the initial refractory (16 samples). On the periodic-swing construction the defended value is 63.7 against an undisturbed control's 63.8, and disabling either the positional clock or the retry floor alone gives the broken 55.2 back.
The position jam had a companion of its own: the starvation confirm's schedule write (§7.2) had already raised the wait to 32 before the first audit could run, which is what made "break one run per wait" cheap: one super-band move per 32 samples, no alignment required. Each repair recovers a different cadence of the attack (the schedule fix alone recovers the jittered burst, the decay alone the period-2.5 burst) and only together do they close every unaligned variant (56.0 → 66.4/66.5 against a 66.9 dose-matched control). The residue is the sample-aligned every-sample jam, which no consecutive-run clock survives; §11 carries it as a limit with a known study direction, priced with the grid's other alignment exposures.
The controller optimizes a proxy, so something must remember what the goal metric has actually witnessed and refuse to stand anywhere measurably worse. That memory is one remembered position with one remembered claim, plus the discipline that bounds the claim. Most of this chapter is that discipline; each rule answers a specific measured failure.
Two failure shapes demand the memory. Share-matching's rest point moves with the traffic mix, so the controller can walk away from a better position that remains available (F-5). And a probe- or audit-won position can be quietly dismantled, since an audit's win is, by construction, a position density disagrees with. Measured concretely: a hot co-tenant occupying ~10% of main makes the walk home look density-balanced while the victim's rate falls.
The anchor records a proven window position and the smoothed hit rate earned there; that rate is its claim. The controller also tracks the current smoothed rate (≈5-sample memory) and its mean absolute deviation (MAD). The deviation starts wide, at 5pp, so a cold cache cannot veto early.
The guard rail returns the window to the anchor when the current position has earned measurably less. While away from the anchor, a smoothed rate below its claim by max(1pp, 3·MAD) for four consecutive samples triggers a return, using capped strides and a small budget. On arrival, the window parks.
The return also tests whether the claim is still valid. The claim is frozen when the return commits. At the end of the two-sample settle, a smoothed rate still a margin below that claim causes the controller to discard the anchor, release the hold, and re-seed its rate estimates. The rail supplies a return decision, rather than continuous steering.
One dynamic looks like a bug and is not: the margins widen just when the rate moves. A real step change feeds its |Δ| into the same deviation estimate that sets the margins, so for the first several samples after any step the rail and the ratchet hold fire, and they engage as the smoothing settles, typically after 5 to 10 samples. At the moment of a step, "the workload changed" and "the noise got louder" are the same observation. Acting before the two can be told apart is how §2.4's weather-chasers were built, and the scenario tests pin this lag on purpose.
Each rule below closes one way the memory could lie: a claim seeded on transient evidence, a claim that outlives its regime, a return that proves nothing, or a paid-for position quietly dismantled.
Re-sync runs only on-anchor, so without the re-seed the claim froze the moment steering left the anchor, and with the reference still ~80% composed of the ended regime no later audit could confirm at any position (the repro landed on its own audit-free value, 7.6 points below LRU). The deviation re-seeds wide (the cold-start seed again), so every margin it prices stays uncrossable until the new regime's own scatter has been measured. The gentler-looking alternative, aging the claim toward the live rate, is measured dead in both forms: symmetric aging lets the claim chase the rate upward so no position can ever clear it by the margin that moves the anchor (regimeramp −11.9), and one-sided aging disarms the rail. Discarding on a still swing fixes the stale-claim witness just as the audit's reference change does, and it costs the moat rows, the rail's own control. On the h4000 dose the undo's arrival lands the window inside a band of where it then stands and the collapse arrives one sample later; on h3000 the window sits still for fourteen samples while its hits erode and then break; both times the discarded claim was the position the rail vetoes home to (0.62 kept, 0.46 discarded; −0.7 to −1.9 on every seed with two or three boundaries of stillness required). Re-seeding the goal metric on a still swing while keeping the claim is worse still: the re-seeded deviation reads the shortfall as real and the rail vetoes into the dead anchor within four samples.
On workloads whose per-sample scatter reaches the restart threshold, the stand-down otherwise freed a just-validated position within ~5 samples and density re-ballooned off it (cp_w097's audits confirm real improvements at high windows and weather then loses the lower park). The bound matters in the other direction too: unconditional persistence converts the tracking controller into hold-and-retest where tracking is the cure (regimeramp −6.4, widepin −6.3, phases −4.1), while the bounded shield holds all three at their ship values.
In short, the anchor is planted only on evidence earned at rest or by a confirmed walk. It is re-synced while stood on, moved only on a cleared gain, discarded only by a crash at home, and defended by a veto whose return must re-earn the claim it acted on. What a swing, a blind corner, a shortfall, or a due audit does to each of these holds is tabulated mode by mode in §9.2.
If the goal metric deserves a veto, why not a vote? Blend a reactive step into density steering continuously, weighted by a confidence estimate, and let the two signals share the wheel. It would even dissolve a tier boundary. The blend was built and measured twice, once in the main line and once in a parallel instrumented study with pre-registered predictions, and it fails on three independent grounds that generalize beyond it.
These results explain the separation: density supplies ordinary steering, while hit rate guides bounded walks, judges audits, and triggers returns to the anchor.
This chapter is the maintainer's view: how size selects among three regimes, the full decision flow of one sample, where the numbers physically come from, and what the whole thing costs. Nothing new is designed here; it is the previous five chapters bolted together.
Everything in §5–§8 describes caches above 4096 entries. That controller is the density climber, named for its steering signal; in full, the goal-audited density climber, since density steers, probes rescue the blind corners, and the goal-metric layer audits what density cannot judge for itself. Below 4096 the reactive climber of §3 ships unchanged, and below 512 it runs with gentler tuning. Together they are the window climber, the one class that ships. The tiering follows from statistics rather than hedging. Adaptation quality depends on how many informative decisions a cache gets, and both the information in a sample and the price of a move change with C.
The shape of one decision, in priority order; the full annotated listing is in the fold:
every maintenance cycle, after eviction: // BLC.climb() → WindowClimber
if sampleRequests < period: return // period = min(4·C, sketchSample)
if C ≤ 4096: reactive climber // §3, §9.1
else:
crash stand-down on |ΔHR| ≥ 5pp // release holds (§8.2); a crash
// near the anchor discards the
// claim; own re-tests exempt
bookkeeping: smoothed rate · anchor // §8.1–§8.2
walk in flight → its endings // stride / crash / reverse /
// adjudicate (§6.4, §7.2)
undo or veto-return in flight → continue it
blind corner → hold, or arm a probe // §6
sustained shortfall vs anchor → veto // §8.1
audit due → arm an audit // §7.2
parked → hold
otherwise → the density step // §5, the default
stillness clock ticks; commit the step
every maintenance cycle, after eviction: // BLC.climb() → WindowClimber
if sampleRequests < period: return // period = min(4·C, sketchSample)
hitRate = hits / requests
if C ≤ 4096: reactive climber (§3, §9.1)
else:
bar = max(4, requests >> 10) // §6.1
error = ln(d_w / d_m) // ε form, for probe verdicts
span = requests / frozenRequests // §6.4: same length for both
verdict = probeDown
? error // down-probe: average test
: ln(d_w / (frozenProbation·span)) // up-probe: §6.4
if |ΔHR| ≥ 5pp and not (shielded or parkTest or returnTest):
// crash stand-down (§8.2); parkTest: the park's own audit walk;
// returnTest: its retreat, or a veto's return until re-tested
release any park or veto-return; discard the anchor only if
the crash landed within its band (far crash = the rail's own
evidence), and a discard re-seeds the smoothed rate + deviation
from the next sample (§8.2); the audit clock is untouched (§7.3);
a park stays shielded for one initial audit wait after its confirm
update smoothed rate + deviation // §8.1
update the anchor: seed at rest; re-sync on-anchor; ratchet on
margin-cleared improvement // §8.2
if probing: // §6.4 / §7.2 endings
crashBar = audit
? min(5pp, 0.15·launchRate) // level test vs the rate frozen at
: clamp(3·dev, 5pp, 15pp) // the arm; pricing the audit's
// depth trades basin cadence (§11)
reversalBar = audit
? min(5pp, 0.15·max(launchRate, 3·dev))
: crashBar // first-difference test vs the
// previous sample (§6.4)
crash (below launch by crashBar; an audit retry, auditCrashStreak ≥ 1,
tolerates 2 below-bar samples first, holding direction)
→ undo (capped); a 2nd consecutive crash escalates the walk's own
ladder (audit rung vs starvation rung, never each other's)
audit walk → goal-metric judge at depth ≥5 vs frozen reference;
confirm: keep + plant anchor + PARK (no parting steer);
budget out: undo, retry on the audit ladder's cadence (wait ×2 only
on a failed walk at the deepest audit rung; a crash, even
streak-escalated, keeps the cadence)
starvation walk → watched ≥ 4·bar at committed depth: density
verdict; confirm: keep + plant anchor + ladder reset (×2 instead if
steering reverses it at once; PARK when that reversed confirm is
audit-grade); else fail
budget out → undo, ladder ×2
else → rung-scaled bold-driver stride, reversing only on a
sample-to-sample drop past reversalBar
elif an undo remainder is pending: continue it (capped strides)
elif a veto return is in progress: stride toward the anchor
elif a return has landed on the anchor: settle, then re-test the
frozen claim; short → stand down + re-seed the rate references
elif blind corner (§6.2):
refractory remaining → still ≥ auditWait
? arm an audit (§7.2)
: tick down; HOLD
else → arm probe (freeze the probation baseline) + entry stride
elif sustained margin-cleared shortfall vs anchor → veto (§8.1)
elif still ≥ auditWait → arm an audit (§7.2)
elif parked → HOLD
else → density step on the floored steering error (§5.3–§5.4),
clamped and lifted at the 2% floor
stillness clock: window within the band accumulates toward the
next audit; movement decays it by one (§7.3)
commit the step as the pending adjustment; reset sample counters
The ordering encodes four priorities.
Three observers run before the router on every sample: the smoothed rate and its deviation update, the anchor re-syncs its claim if the window stands on it and may seed or ratchet on a settled sample, and a crash-scale swing stands the goal-metric layer down. After the router, the audit clock ticks on the window's actual position. The table reads the same priorities the other way round, by mode: what the machine does in each of its states when one of the four events arrives.
| mode | crash-scale swing |ΔHR| ≥ 5pp |
blind corner | sustained shortfall vs the anchor | audit clock due |
|---|---|---|---|---|
| steering (the default) | stand-down: any park or return is released; the claim is discarded, and the goal metric re-seeded, only if the window stands on the anchor. Steering continues | arms a probe, or holds if the refractory is still running | veto: a return toward the anchor begins, and the window is held there on arrival | arms an audit |
| blind-corner hold (refractory running) | the same stand-down; the hold continues | holds, counting the refractory down; the window moves only to lift off a sub-floor position | not judged: a starved sample cannot adjudicate a shortfall, and the streak neither grows nor resets | arms an audit; a due clock pre-empts the hold |
| walk in flight (probe or audit) | the walk continues; only its own crash bar can end it. A park the walk did not arm out of is released; a park whose own audit is walking is covered | ignored; a probe's verdict reads the starved region's earnings itself | frozen: the streak neither grows nor resets, and the anchor cannot move while a walk is in progress | waits for the walk to end; stillness decays while the window moves |
| retreat draining (a capped undo) | covered for the stride and the sample it lands on; a later swing stands the layer down as usual | waits for the retreat to complete | frozen, as during the walk | waits |
| veto return, striding home | ends the return and releases the hold; the claim is discarded only if the window already stands on the anchor | waits | already answering it | waits |
| veto return, landed and settling | covered until the retest has ruled: the landing's own swing is the return's doing | waits | the retest: after two settle samples, a claim the position cannot earn is stood down, and the goal metric re-seeded | waits |
| parked | releases the park and discards the claim, since the window stands on the anchor, unless the park is fresh (one initial audit wait after an audit's confirm) or its own audit is walking | arms a probe; the blind corner outranks the park | cannot fire: the window stands on the anchor | arms an audit out of the park; its first direction follows the walk that confirmed the park while the claim stands |
How a walk itself ends, and what each ending does to the ladders and the schedule, is the table in §7.2.2.
None of this touches the request path. A read records into a lossy striped ring
buffer (full stripes drop records, an intentional trade protecting read
scalability), and the buffer drains under the eviction lock during maintenance. Each
drained access reorders its entry and, for an entry with nonzero policy weight
outside a quiet completion (a hygiene rule below), feeds
recordHit(inWindow, inProbation), with the probation flag captured
before the access promotes the entry. Misses arrive via the lossless write buffer's
insert task. Read-buffer loss slightly undercounts hits uniformly across regions, so
the density ratio is unbiased by it.
After eviction and expiry in each maintenance cycle, climb() asks the
climber for a decision and applies the pending adjustment by moving region
boundaries, transferring at most 1,000 nodes per cycle with the remainder carried
over. All climber state is plain fields written only under the eviction lock: a
single-threaded state machine that happens to live in a concurrent cache. A user
resize (setMaximum) resets the climber wholesale, since every
reference it holds is denominated in a capacity that just changed.
The counters must also mean what they claim: hits earned by resident capacity, attributed to the region that earned them. The standing rule for any path that touches the access plumbing: decide, explicitly, whether an event is a usage or bookkeeping.
| leak | mechanism | measured damage | rule now enforced |
|---|---|---|---|
| async load completions counted as accesses | completing a future finalizes weight via the write path, which historically recorded a policy access: every async miss injected a synthetic, window-attributed hit plus a doubled admission frequency | −12.7 deterministic on a phase splice; −38.6 on a constructed cell | completions are quiet: weight and expiry finalize, no sketch increment, no climber counters |
refreshAfterWrite reload completions were loud |
the triggering read records its access and the reload's completion recorded another, double-counting all refresh-eligible traffic | 1000 reads → 2000 climber hits + 2000 sketch increments | automatic-refresh completions remap quietly; explicit refresh()
stays loud (deliberate action, no read-stream amplification) |
| zero-weight entries earned hits | an entry occupying no capacity (an in-flight async load, a zero-weight pin) contributes hits with nothing in the denominator | 200 pinned zero-weight entries captured the window: 57.9% time-averaged vs a 36.3% control | hits record only for entries with nonzero policy weight; misses still count (the demand is real, and weight arrives on completion) |
| resize-down left the sketch aging at the old scale | the aging period was only reassigned when the sketch's table grew, so shrinking 1M → 1K left it ~1000× too slow, freezing both admission aging and the climber's sample ceiling | adaptation effectively frozen after a large shrink | shrinks retrack the period while the table stays grow-only (reallocation would wipe the counts: an admission blackout until history rebuilds) |
One asymmetry follows and should not be "fixed": the climber's sampled hit rate is the rate over the entries it controls, which can sit below the user-visible rate (completions and zero-weight hits are real service, just not steering evidence). The two numbers answer different questions.
The controller keeps only fixed-size, per-cache state: no per-entry metadata, ghost structures, or auxiliary history. Access accounting is constant-time and decisions run on the existing maintenance path, so its time and space overhead are negligible relative to ordinary cache policy work and entry storage.
Five settings carry most of the controller's design load:
| setting | why it is load-bearing |
|---|---|
| starvation-bar shift | Trap earnings sit two orders below it; the whisper construction sits knife-edge above it by design (§6.1). |
| 2% floor and 2% stillness band | They have different meanings despite sharing a value: one preserves signal, while the other decides whether a position has held. |
| 4·C sample period | It is the three-way compromise developed in §5.5. |
| ladder schedule and commitment depths | They resolve §6.5's measured dilemma; they are not ordinary tuning parameters. |
| 15% audit-bar fraction | One fraction caps the crash abort against the frozen rate and prices the reversal against the larger of that rate and the noise band. It is derived from two shipped constants, equals 0.45 deviations, and sits just below the measured cliff at 0.5 (§6.4). |
Claims about an adaptive policy are only as good as the discipline behind their measurement, so this chapter opens with the method, then gives the results: real-trace corpus, weighted caches, and the constructed trap gallery with each family's defense.
The audit found four kinds of defect: a bar inside the row's own seeded spread (a coin flip), a bar set below LRU (it cannot fail for the reason the row exists), a recorded level that no longer reproduces (levels rot; margins do not), and a bar on a trace too short to converge (it prices warmup and reads as quality).
Every row is also checked for how many decisions its trace contains, since a ~50-sample trace holds at most one audit cycle, its whole-trace mean measures convergence speed, and quality is read from the final third. Trajectories are read in six blocks, because a thirds average renders oscillation as smooth drift.
| cell | decisions | density | reactive | static 1% | density − reactive |
|---|---|---|---|---|---|
| arc DS1 @1M | 10 | 11.99 | 14.01 | 14.77 | −2.02 |
| 32 | 14.28 | 14.77 | 17.24 | −0.49 | |
| 109 | 15.59 | 15.46 | 18.74 | +0.13 | |
| arc S3 @400k | 10 | 41.30 | 42.59 | 43.00 | −1.29 |
| 30 | 44.20 | 45.51 | 45.95 | −1.31 | |
| 102 | 44.83 | 46.82 | 47.00 | −1.99 |
Start with the failure an adaptive policy exists to avoid, which is doing worse than not adapting at all. On five real cells of the release battery the reactive climber lands below LRU, while the density climber holds at or above it on three and within a third of a point on the other two:
| cell | LRU | reactive | density |
|---|---|---|---|
| corda @8k | 33.33 | 30.96 (−2.4) | 33.00 |
| scarab recs @256k | 87.05 | 83.61 (−3.4) | 86.84 |
| systor17 LUN0 @1M | 5.45 | 4.53 (−0.9) | 5.92 |
| tencentPhoto @4M | 73.70 | 71.87 (−1.8) | 74.34 |
| google thesios c2 @4G | 23.96 | 22.62 (−1.3) | 24.07 |
The aggregate is quieter, and that is the actual shape of the result. From a 205-cell sweep (45 real traces across size ladders, N≥2): 41 significant wins (+117.7pp in total) against the reactive climber, 9 losses (−13.8pp), 155 ties. The wins are the recency-demand family the density signal was built for; the losses are §5.6's documented bias, each still far above LRU. Part of what a size sweep shows on a long-working-set trace is horizon rather than bias: at a 1M cache a 44M-request trace holds ten decisions, and §10.1's horizon table separates the two. Ties are the majority because the incumbent already sits at or near the static ceiling on most real traces, leaving nothing to win; the corpus checks that the record holds, and the trap gallery (§10.4) covers where it does not.
The shipped build was then re-verified on a fresh 28-cell run against current master (N=3, extended to N=8 wherever either arm's spread exceeded 0.5pp; the reactive arm is bimodal on several cells, up to ±2.6, so its single draws are not quotable); the significant movers, colored by direction:
| cell | density | reactive | Δ |
|---|---|---|---|
| cloudphysics w061 @64k | 38.33 | 34.16 | +4.17 |
| corda @8k | 33.00 | 30.96 | +2.04 |
| cloudphysics w097 @32k | 51.47 | 49.66 | +1.81 |
| umass F1 @32k | 37.39 | 35.66 | +1.73 |
| arc OLTP @8k | 60.77 | 59.51 | +1.26 |
| umass F1 @8k | 34.64 | 33.41 | +1.24 |
| arc P11 @64k | 44.51 | 43.54 | +0.97 |
| umass F2 @8k | 46.39 | 45.68 | +0.71 |
| umass F2 @32k | 68.22 | 67.71 | +0.51 |
| arc P5 @32k | 15.45 | 14.95 | +0.50 |
| msr proj0 @16k | 10.00 | 10.56 | −0.57 |
| arc P8 @64k | 48.67 | 49.33 | −0.66 |
| cloudphysics w097 @8k | 42.21 | 43.13 | −0.92 |
| arc P5 @64k | 25.17 | 26.39 | −1.22 |
| cloudphysics w097 @16k | 47.61 | 50.10 | −2.49 |
| …and 13 cells within ±0.5pp (the full table, ties included, is in the appendix) | |||
The modest average differences reflect how little room most traces leave for improvement. The terrain scan behind §2.1 found no interior optimum on any of its 22 real cells: the curves were flat from the floor or gently rising. On flat terrain, different climbers should tie. Where window size matters, the evidence distinguishes three benefits: avoiding below-LRU outcomes, retaining valuable objects in weighted caches, and reducing run-to-run variation.
The weighted view: where object identity and byte cost diverge, the density signal prices slots rather than requests, and the gap stops being small. metaCDN_rprn @4G trades −0.73pp in object hit rate for +10.69pp in byte hit rate (49.59 against 38.90), because the retained large objects are what the byte metric pays for.
Repeatability is the third distinction. On several cells, the reactive climber settles in different basins across runs of the same workload. Density narrows the resulting hit-rate spread. With N=20 per arm, the spreads were 3.8pp versus 0.2 on umass F1 @32k, 4.1 versus 0.2 on arc P5 @32k, and 2.5 versus 1.1 on arc P11 @64k, with reactive first in each pair.
The constructed battery (§10.4) shows larger separations, including 15–28 point escapes on the pin families. On real traffic, the case for the extra machinery rests on the three properties above.
The one row that deserves its paragraph is the last red one. cp_w097 at 16k is a density-family structural loss rather than a regression of the safety layers. On the current tree it reads 46.9 against the reactive climber's 50.1 and LRU's 41.7, and 43.6 with the audits disabled: the audits recover 3.3 points and keep the cell far above LRU, and they do not cure the steering objective.
The mechanism is average against marginal value. The density law asks whether the window's average hits per resident entry exceed main's, and on this trace that error stays positive from a 1% window through the reachable 80% cap, while the marginal error measured at the window's tail crosses near 22% and the static curve peaks broadly at 5–15%. The window has a valuable hot head and an exhausted tail, so matching whole-region averages keeps asking for more window after its boundary value is spent. Replaying the trace to two and four times its length leaves the loss where it is while the static ceiling rises as its cold fill amortizes, so this is not §10.1's short-horizon effect; the controller never settles, cycling through seed-dependent high-window walks and parks. The trace's own 3–7pp scatter, which widens the margins and releases parks, is a secondary cost on top of that wrong sign.
Holding the parks longer, following a productive confirm sooner, and re-arming the
clock on a shift were each measured and declined: every bounded form trades seeds
without touching the sign (§11). A repair needs richer marginal information, and
must first clear the slowswap counterexample that retired marginal
steering.
Behavior, not just endpoints:
Size-aware caches exercise every mechanism with a different denominator, and the zero-weight hygiene rule exists because of them. The weighted spot set (a mixed-size Zipf-plus-reuse-band family and a few-huge-entries family, ~200 objects of 25–100MB in 10GB, three seeds each):
| cell (weighted hit rate) | density | LRU | Δ |
|---|---|---|---|
| wmixture d010 · s7 / s11 / s13 | 79.45 / 79.80 / 79.47 | 75.25 / 75.67 / 75.21 | +4.2 / +4.1 / +4.3 |
| wfew (huge entries) · s7 / s11 / s13 | 68.96 / 73.01 / 69.25 | 62.14 / 66.51 / 62.37 | +6.8 / +6.5 / +6.9 |
Each constructed family is a plausible production shape distilled to one mechanism, maintained as a deterministic generator with a standing verification battery. The tour: what the workload is in production terms, which failure mode it triggers, and where the defense stands. Values are whole-trace hit rates at 8k entries unless noted, and on the ~47-sample instances a whole-trace mean prices convergence rather than quality (§10.1), so final-third figures are quoted where the two diverge.
| family | the workload, in production terms | failure mode | defense at the final build |
|---|---|---|---|
| mixture | popular content plus session-scoped re-reads at working-set distance | F-3: the re-read band is invisible to a floor window | escaped: 63.0 over LRU's 59.8 on every seed (long companion 63.6); the deeper bands and at-scale variants also converge above LRU: their whole-trace 50.8 / 58.5 is warmup, with final thirds +3.8 / +5.0 over LRU and long companions clearing LRU on every seed |
| whisper | the same shape plus a ~0.2% immediately-re-read trickle (heartbeats, token checks) that keeps the window "sighted" | F-4: no starvation is ever declared | audit repairs it past LRU: 66.8 vs 64.6 on every seed (was 55.5); the below-trickle control confirms via the probe path alone (66.8) |
| deadphase / rider | a hot set punctuated by one-shot scan bursts; the rider adds a timed 0.02–0.4% trickle | F-6/F-2: dead samples plus stray hits once bought maximum steps | at its ceiling (49.1 ≈ 49.7); rider dose-response flat where it formerly cost 8–10pp |
| demoflood | a protected-saturating hot core over a reachable reuse band | the live-baseline absorbing veto, constructively (§6.4) | 68.6 with confirmed probes (LRU 16.7); drift toward ~59-with-zero-confirms is the battery's tell for a broken freeze |
| trickle / bandtrap / straywall | reuse bands of varying width behind stray zones of varying depth: §6.5's dilemma swept across its parameter space | F-3 with adversarially placed evidence | trickle 70.7 (s7) / 72.5 (s11), warmup rows (+2.4 / +1.9 over LRU converged); straywall 55.1 attractor, the rung-scaled strides' win completed by the audit; bandtrap2 72.1, a genuine pin, 4.4 under LRU and constructed-only (§11) |
| widepin / phases | two jobs time-sharing one cache, alternating whole working sets | the lag limit plus basin lottery; partially structural | widepin's whole-trace 49.6 (seeded) is convergence cost: it ends at a 77.9% window against an 80% optimum, paying the deficit en route; phases d050 (57.2 at N=8, from 47.0 before this layer) is a genuine pin, −8 against LRU even converged; §11's measured residual |
| jam (rate / position) | periodic crash-scale hit-rate swings, or window-moving delivery bursts, from bursty co-tenant traffic | audit-clock suppression (§7.3) | closed twice: rate 63.7 vs an undisturbed 63.8; position 66.4/66.5 vs a dose-matched 66.9 control (was 56.1 = the audit-free pin, 8.9 under LRU); each repair pair verified by ablation; the sample-aligned every-sample variant remains a §11 limit, now with a clean reachability scan |
| co-tenant | a second hot tenant holding ~10% of main beside a false-equilibrium victim | F-5: rate-neutral dismantling of audit wins | anchor + park recover 57.4 → 59.6 of an undosed 64.1; the remainder is bounded audit duty |
| walk-interior dose (crashnoise / mixnoise) | a window-irrelevant hit-rate modulation whose amplitude crosses the walk's crash bar (the whisper and mixture bases) | weather aborting walks inside the machine's own noise floor | both sides answered: the probe bar's pricing healed the dosed mixture pin 51.6 → 60.7 (+5.6 over LRU, with battery, real corpus, and a fresh holdout tied), and the audit side, once −2.8 under LRU, closes to within a point (63.3 against 64.1) under the crash-streak tolerance and the reversal's noise floor (§6.4); the sub-point residual is §11's audit-bar entry |
| nullchurn / lowmix / scrambler / cadence set | degenerate and adversarial edges | various (§11) | nullchurn ≡ LRU (probing a dead equilibrium is free); lowmix and scrambler are accepted, documented sentinels; cadence cells within ±0.04 of record |
Read as a whole: every failure mode in §2.6 has a family that demonstrates it and a measured defense, and the whole battery reads against LRU and static-ceiling anchors, so "is the machine ever worse than doing nothing" is a table rather than an impression.
Across 52 rows the mean margin over LRU is +0.88, 21 rows sit within 2pp of the ceiling, and against the reactive climber the machine is better on 35 with a mean of +2.71. Nineteen rows read below LRU on a whole-trace mean, but most of that is convergence cost rather than steady-state quality: twelve of the fifteen short instances price warmup, and rows recorded 8pp below LRU are 3–4pp above it once converged. What survives the separation is small and named.
Three genuine pins survive (phases d050, bandtrap2, and the aligned jam), each constructed-only with a clean reachability scan (§11); eighteen of the nineteen below-LRU rows are below for the reactive climber too; and exactly one row is a density-introduced regression against doing nothing, the aligned jam.
What this design does not solve, on purpose, and how to read a misbehavior report against it.
Each limit has a measured example and a named mechanism. The labels distinguish an open fix direction, a priced trade whose refinement was built, measured, and declined, and a constructed-only failure not found in the scanned real corpus. Expand each item for its mechanism, measurements, and reachability checks.
Most of what the alternation families appear to pay is convergence rather than this limit: widepin, the battery's largest whole-trace deficit at −22 against LRU, converges to a 77.9% window against an 80% optimum and pays the whole deficit en route (final third −3.7). The genuine pin is phases d050, still 8 points under LRU converged: its cadence is locked to the sample grid (phases of 16·C against the 4·C period, so every phase is exactly four samples with boundaries on sample boundaries; hit-rate autocorrelation −0.56 at lag 4, stillness runs never past five samples), and it is constructed-only: the strongest real-cell autocorrelation is −0.38 at lag 11, a slow drift rather than a grid cadence, and the corpus's only short-lag negative is an order of magnitude under the trap. The alternative to a lag-free signal is accepting fixed-window behavior under detected thrash.
cp_w097 is the high-window face of the same identity error: the whole-window average error stays positive through 80% while the tail's marginal error crosses near 22%, and every block of the trace peaks within 5–15% with a plateau from about 2% to 25%. The controller does not settle there; it cycles through seed-dependent high-window walks and parks.
The open half, measured. Six of twenty-one swept cells hold a valley deeper than half a point between a 1% window and their optimum; four are real traces. On the two deepest the controller rests inside it: P3 @152508 at a 1.4% window against an 80% peak, 3.59 points lost, and fiu_webmail @195466 at 6.9% against 90%, 4.55 lost, while a unimodal control rests for 0.00. It is a rest-point error, not a convergence cost: on fiu_webmail the running controller sits 0.53 above the static value at its own rest point. §6's walk is gated on blindness and these windows earn far above the bar, and §7's audit is inert here (+0.054 points over twenty-two cells), so nothing in the machine escapes it. The marginal form would: it rests at 75.3% on fiu_webmail, 0.43 off the peak.
The presumed refinement, steering on marginal densities instead of averages, was built in four denominator forms and measured to a frontier. The signal is real (the full form at half gain earns +0.83pp mean over nine cells, with rest-point tracking 0.983 against ship's 0.950), but every denominator sits on one monotone frontier trading corpus prize against robustness on a slow whole-set handover whose heavy inflow fills probation with transients. The exchange rate is about 16pp there per 1pp of corpus, gain does not move the frontier, and the family's ceiling is 37.52 against that row's ≥40 bar. A trust-gated arm escapes the frontier (+0.69, tracking 1.000) and still fails the bar; its residue is recovery from a hole already dug, a parked window where steering is never consulted again, which nothing living in the steering law can fix. So the bias ships as a priced structural trade rather than an open refinement, and any successor is screened on rest-point tracking before it earns a battery.
The audits matter here: the cell reads 46.9 with them and 43.6 without. Their confirms land at high windows, around 56% and 26%, and weather later releases the lower park; that release is visible but is not the remainder. Holding the parks longer (up to a near-permanent bound), following a productive confirm sooner, and re-arming the clock on a shift were each measured: each trades seeds, the best of them a fraction of a point with several seeds losing, and none moves the steering sign. These are supervisory trade-offs, not a lower-variance reference waiting for the right retune. Reopen only with new marginal information.
The rate-weather class once had a complement: an audit's crash abort and bold-driver reversal shared one fixed 5pp bar, so once a workload's scatter crossed it, audits armed and died mid-walk instead of adjudicating: on fourteen real traces 76% of armed audits ended in the crash abort, and a window-irrelevant modulation killed the layer at a dose threshold. Both halves are now answered without re-opening the direction that stays closed. Widening the crash abort remains dead: pricing its depth, even capped and even with a fresh reference, heals every sentinel and then eliminates a real trace's good basin at the holdout (P8 −2.5, w097 −1.1), because the cheap early abort is what keeps audit duty low and basin-reaching cadence intact. What shipped instead attacks the two failure modes separately. The crash-streak retry tolerates two below-bar samples in time (§6.4), which healed the dose family's collapse to under a point below LRU. The reversal, a different statistic that never deserved the level's bar, is priced at the same fraction of the larger of the frozen rate and the scatter (§6.4), which returned the give-back sentinel's loss (+0.8/+1.8/+1.2 by seed) while 47 of 52 battery rows were bit-identical and the real corpus moved −0.02 mean. The sub-point residuals on the dose sentinels are the crash abort's remaining robustness price, and they are what staying out of the widening family costs.
The clock repairs (§7.3) widen the duty's reach: on regime-alternating and floor-optimal synthetics the audit layer's share of a run can grow from 6% to ~43% with nothing to confirm, costing one to two points that the (jammable) clock used to leave on the table, measured only on families already below LRU, with twelve real traces moving ±0.07. Part of that price turned out to be the reversal bar rather than the duty itself and came back with the exit split; what remains still reads as a net loss against the reactive arm on the give-back family, and it has no candidate: the one proposed (a bound on parked excursions) failed to reproduce under seeded pairs and was withdrawn. The gate's shieldtrap and saw rows pin the price.
The analytic boundary is motion on half the samples, but partial-motion cadences are not realizable (50% and 67% measured: audits arm, and the audit-free arm outscores the layer: steering cannot hold a clean partial alternation), so every-sample motion is the regime, and reaching it requires alignment an attacker cannot aim and a periodic workload lands only by luck, the same exposure class as the grid's trace-start offset. The cost is not a forgone increment: at N=8 seeded the controller scores 56.08 ±0.05 against the reactive climber's 65.37 ±0.20, a deterministic nine-point regression against the law this tier replaced. It is also below that cell's LRU of 64.9, where that law is above it, on a shape that law has no failure mode for. The dose-matched flat control runs the other way, and is the reason the finding is about the jam rather than the terrain: there the controller is 66.92 ±0.01 against the reactive arm's 64.61 ±10.71, so on the same traffic without the jam it is both better and deterministic where the reactive climber is a lottery. The reachability scan comes back 0 of 14 real cells: real traffic holds stillness runs of 9–128 samples with 1–15 audits armed per run against the jam's single-sample runs and zero; the nearest approach (corda) calibrates once on flat terrain, where low audit exposure costs nothing; and the adjacent cadences (half motion, jittered bursts, period 2.5) all pass, so the jam is a knife-edge rather than a basin. The known fix direction (stillness as a fraction over the interval, or against a low-passed position) keeps its warrant and stays deliberately unspent: it would redefine the clock the whole audit layer rests on, the clock that produced the last three severe findings, for a shape nothing real reaches.
A reuse band at one exact distance latches only inside a mid-range window band, where adjudication is density-inverted: the region that would earn the band is the one the steering signal shrinks, and the machine cannot re-test its way out, because steering's own motion keeps positional stillness below even the calibration wait (longest run two samples; zero audits ever arm). Constructed-only: across the same fourteen real cells, stillness runs 9–128 samples with the audit layer live on every one.
Priced by the family built to trigger it: alternating a regime that blacks main out entirely with one whose optimum is a 1% window costs ~8pp against both the static ceiling and the reactive arm: the window balloons to 80% of the cache within three samples of every blackout, while still sitting 26 points above LRU, which is the reading an LRU-only bar cannot see. Dose-response on repeated blackouts is ~1.2pp per episode. Not a defect to chase; the cell exists so any future reformulation of the ε-asymmetry has its price on record.
Six constructed failure shapes received additional reachability checks during release anchoring: the aligned jam (posjam), the density-inverted latch (bandtrap2), the grid-locked alternation (phases d050), the zero-main balloon (balloonflip), the moat terrain (whose valley §6.4's crash-streak tolerance now crosses), and the modulated-mixture dose instrument (mixmod). Each carries a named mechanism and a reachability scan against the same fourteen real cells, and all six are constructed-only.
The co-occurrences these traps need did not appear in the scanned real traffic. High scatter rides narrow terrain (every real cell whose scatter is three bars deep has under 3pp of terrain to lose, and every wide-terrain cell is quiet), cadences do not lock to the sample grid, and stillness starvation co-occurs with nothing worth finding. Where a real cell carries a signature or half of one, either the terrain is too flat for the exposure to cost anything (corda under two of the scans; the one full match, cp_w044, has half a point of terrain and banks +0.16 over LRU) or the scatter is window-informative, which is what the goal-metric layer exists to answer (arc_ConCat). The reachability checks found these six combinations only in deliberately constructed workloads.
| report | first hypothesis | how to check |
|---|---|---|
| "hit rate differs between two runs / versions on the same workload" | basin lottery on an alternation-heavy workload | N=8 both configurations; compare distributions, not draws: a regression shifts the mean, a lottery widens the spread |
| "frequency-heavy workload slightly worse than the old climber" | the density bias, typically 0.5–2.5pp and larger on its high-window face; confirm it is still above LRU | static-sweep the trace and read the trajectory: the classic give-back is an optimum ≤2% with the climber at 5–10%; the high-window face (cp_w097) peaks at 5–15% while the climber cycles much higher, the average sign still positive where the tail's marginal sign has turned |
| "window pinned small; a bigger static window scores much better; no probes" | a sighted false equilibrium the audit isn't repairing: check stillness (is something jittering the window?) and the margins (noisy texture) | trajectory capture: stillness counter, audit arms, verdict reasons per sample |
| "periodic dips at a regular cadence" | audit or probe excursions doing their duty, or the duty-cycle residual | duty should shrink as the ladder escalates; constant-rate dips forever means a confirm/undo cycle |
| "barely adapts at all" | sample starvation: 4·C per decision, so huge caches on short traces get few decisions | count completed samples; single digits means the trace is the limit |
| "weird behavior right after a maximum-size change" | wholesale climber reset plus throttled re-partition, transient by design | bounded by a few samples; persistence after that is real |
| "the rate visibly stepped, but the veto / anchor reacted late" | margin inflation on a step-change (§8.1) | expected lag ~5–10 samples; the anomaly is a reaction that never comes as the deviation decays |
The window climber combines density with hit rate. For large caches, density provides routine steering: compare the hits each region earns per slot within one sample, then move capacity toward the denser region. The proportional step becomes smaller as the densities approach balance.
That signal fails three ways, and each failure gets one machine:
Feed it only hits that resident capacity earned. Below the sizes where per-region statistics work, run the simple reactive climber instead. Every remaining constant has a measured reason behind it (§9.4).
That is the goal-audited density climber; with the reactive tier
beneath it, it ships as the window climber. Going deeper:
WindowClimber.java is the implementation, one plain
class whose comments cross-reference these chapters; the trap gallery regenerates
from deterministic generators bundled with the simulator; the appendix holds the
measurement charts. The W-TinyLFU and adaptive-TinyLFU papers supply the substrate
this design stands on.
The main contribution is robustness: retaining the reactive climber's strong results while recovering from failure modes that the public corpora rarely expose.
The archive: the full corpus table behind §10.2, the measured terrain sweeps behind §2.1, hit-rate-across-sizes charts for every workload in the corpus, and the complete corpus inventory with every family's disposition (A.4). Reference material; nothing here is needed to understand the design.
The re-run behind §10.2, every cell including the ties: the release re-verification of the shipped build against current master (N=3, extended to N=8 wherever either arm spread more than 0.5pp; means at the final N). The reactive arm is bimodal on umass F1 @32k, arc P11, and arc P5 (spreads up to ±2.6), so its single draws are not quotable. An earlier three-arm run tied a §5–§6 controller without the goal-metric layer to within noise on the corpus mean; cellwise the layer matters where its audits confirm (cp_w097@16k is 3.3 points better with it, §10.2). The raw per-rep data lives with the experiment ledger.
| cell | density | reactive | Δ |
|---|---|---|---|
| cp w061 65536 | 38.33 | 34.16 | +4.17 |
| corda lg 8192 | 33.00 | 30.96 | +2.04 |
| cp w097 32768 | 51.47 | 49.66 | +1.81 |
| umass F1 32768 | 37.39 | 35.66 | +1.73 |
| arc OLTP 8192 | 60.77 | 59.51 | +1.26 |
| umass F1 8192 | 34.64 | 33.41 | +1.24 |
| arc P11 65536 | 44.51 | 43.54 | +0.97 |
| umass F2 8192 | 46.39 | 45.68 | +0.71 |
| umass F2 32768 | 68.22 | 67.71 | +0.51 |
| arc P5 32768 | 15.45 | 14.95 | +0.50 |
| cp w038 8192 | 60.62 | 60.18 | +0.44 |
| cp w058 8192 | 53.16 | 53.00 | +0.17 |
| msr prxy0 16384 | 40.94 | 40.89 | +0.05 |
| msr proj0 65536 | 20.10 | 20.17 | −0.07 |
| arc DS1 262144 | 3.42 | 3.49 | −0.08 |
| msr mds0 8192 | 6.73 | 6.82 | −0.09 |
| msr mds0 16384 | 7.79 | 7.91 | −0.11 |
| msr proj3 262144 | 7.30 | 7.62 | −0.31 |
| cp w015 16384 | 58.56 | 58.88 | −0.32 |
| msr hm0 16384 | 11.83 | 12.21 | −0.38 |
| arc S3 65536 | 7.03 | 7.49 | −0.46 |
| cp w104 8192 | 22.16 | 22.62 | −0.46 |
| umass WS2 262144 | 0.63 | 1.09 | −0.46 |
| msr proj0 16384 | 10.00 | 10.56 | −0.57 |
| arc P8 65536 | 48.67 | 49.33 | −0.66 |
| cp w097 8192 | 42.21 | 43.13 | −0.92 |
| arc P5 65536 | 25.17 | 26.39 | −1.22 |
| cp w097 16384 | 47.61 | 50.10 | −2.49 |
Up to four lines per chart:
Optimal (Bélády, where tractable), LRU, the reactive climber,
and the density climber, across each trace's size ladder. The charts are grouped
by pattern; each title is marked by status as well as color:
✓ green = wins or ties everywhere on the ladder
≈ amber = mixed within tolerance (3pp)
! red = a beyond-tolerance loss exists (none in this corpus)
The sweep predates the §5 layer. The final design measures within noise of the density arm: −0.03pp mean over the §7.2 three-arm re-run. The release re-verification against current master provides a later check: 24 of the 28 A.1 cells reproduce within ±0.4pp. The changed cells are recorded in A.1; none is among the workloads charted here.
Only workloads where the two climbers measurably separate are charted; for every other trace the four lines overlap within noise across the whole ladder, and they are listed instead of plotted.
Within noise everywhere on their ladders: P3, P7, P13, S3, DS1, spc1likeread, MergeS.
Within noise everywhere on their ladders: fiu_casa, ◆ msr_hm0, ◆ msr_proj2, ◆ msr_mds1.
Within noise everywhere on their ladders: w99.
This inventory records every family in the local trace collection, including those that provide little information about adaptation and why. The tables report the release battery: density is the shipped build, reactive is the master climber it replaces, and the runs were interleaved. Raw data remains with the experiment ledger.
The frozen 12-cell merge holdout (four families never touched by any climber arm; LRU-only selection) was scored once, per its protocol: N=5, extended to N=8 where a spread exceeded 0.5pp; floor = max(reactive, LRU) − 3 per cell. Eleven of twelve pass.
| cell | density | reactive | Δ | LRU | verdict |
|---|---|---|---|---|---|
| wiki1190 @16k | 66.47 | 66.95 | −0.48 | 63.31 | pass |
| wiki1190 @256k | 79.80 | 79.84 | −0.03 | 77.72 | pass |
| wiki1190 @1M | 85.46 | 85.39 | +0.07 | 85.43 | pass |
| wiki1192 @64k | 72.62 | 72.91 | −0.29 | 69.19 | pass |
| wiki1192 @1M | 85.04 | 84.99 | +0.05 | 85.00 | pass |
| websearch3 @4M | 35.01 | 40.98 | −5.97 | 11.93 | fail, explained |
| websearch3 @16M | 86.34 | 86.33 | +0.01 | 86.35 | pass |
| msr proj4 @4M | 6.33 | 5.64 | +0.69 | 3.83 | pass |
| msr proj4 @16M | 13.48 | 13.80 | −0.32 | 5.52 | pass |
| tencentPhoto @256k | 51.05 | 51.76 | −0.71 | 47.09 | pass |
| tencentPhoto @1M | 64.60 | 64.81 | −0.21 | 62.61 | pass |
| tencentPhoto @4M | 74.34 | 71.87 | +2.48 | 73.70 | pass; reactive is below LRU |
The websearch3 @4M miss is the §2.1 floor-optimal shape at a ~7.8-sample budget: the static ceiling is 41.05 at a 1% window, which is the starting position, and the starvation probe reads the scan window's zero hit density as starvation and walks upward, because cold-start warmup masks the walk's crash bar (the bar compares against the rate frozen at arm time while compulsory misses fade), before crashing back and anchoring at the floor, whose final-sample rate is the ceiling's. One exploration cycle is ~75% of that trace's decisions. Played twice, the whole-trace rate rises to 40.58 and the walk does not repeat; a later audit re-test is bounded by its own crash bar. The give-back is the exploration trade that wins the two green rows on the same protocol.
First measurements on families new to the corpus (entry-denominated; N=3):
| cell | density | reactive | Δ | LRU |
|---|---|---|---|---|
| systor17 d09-LUN0 @1M | 5.92 | 4.53 | +1.40 | 5.45; reactive is below LRU |
| systor17 d09-LUN0 @256k | 3.52 | 3.63 | −0.11 | 3.13 |
| systor17 d09-LUN0 @64k | 2.48 | 2.43 | +0.05 | 2.53 |
| systor17 d09-LUN2 @1M | 5.10 | 4.64 | +0.45 | 4.31 |
| systor17 d09-LUN2 @256k | 2.96 | 2.91 | +0.05 | 2.88 |
| wiki1191a @16k | 65.91 | 66.73 | −0.82 | 63.09 |
| wiki1191a @256k | 79.49 | 79.37 | +0.11 | 77.61 |
| wiki1191a @1M | 84.32 | 84.32 | 0.00 | 84.33 (near-fit) |
| wiki1191b @16k | 66.41 | 67.13 | −0.71 | 63.47 |
| wiki1191b @256k | 79.98 | 79.88 | +0.10 | 78.21 |
| wiki1191b @1M | 84.68 | 84.67 | +0.01 | 84.68 (near-fit) |
| scarab recs @256k | 86.84 | 83.61 | +3.23 | 87.05; reactive gives back 1.4 to LRU |
| scarab prods @16k | 71.21 | 70.68 | +0.53 | 65.23 |
| scarab prods @256k | 92.58 | 92.13 | +0.45 | 93.11 |
| scarab recs @16k | 65.39 | 65.77 | −0.38 | 62.79 |
| cache2k orm-busy @4096 | 84.62 | 84.63 | −0.00 | 84.56 |
| cache2k orm-night @1024 | 67.02 | 66.90 | +0.12 | 67.36 |
| cache2k web07 @16k | 72.40 | 72.36 | +0.04 | 72.45 |
| cache2k web12 @16k | 85.61 | 85.61 | +0.00 | 85.61 |
| gradle build-cache @1024 | 78.75 | 79.04 | −0.29 | 79.91 |
Byte-weighted families (the readers declare weights; the object rate is the climber's own goal metric, the byte rate is the panel's; N=3):
| cell | obj density | obj reactive | Δ obj | Δ byte |
|---|---|---|---|---|
| ibm objectstore 000 @1G | 66.64 | 63.61 | +3.03 | |
| twitter52.000 @64M | 89.10 | 88.07 | +1.03 | +1.02 |
| cloudphysics w01 @1G | 15.19 | 14.22 | +0.97 | +0.75 |
| alibabaBlock @1G | 87.43 | 86.55 | +0.88 | +0.69 |
| metaCDN rprn @1G | 28.94 | 28.36 | +0.57 | +0.42 |
| cloudphysics w01 @256M | 12.27 | 11.91 | +0.37 | −0.59 |
| alibabaBlock @256M | 82.17 | 81.84 | +0.33 | −0.15 |
| metaStorage 1 @256M | 26.35 | 26.08 | +0.27 | +0.91 |
| wikitech @1G | 31.64 | 31.49 | +0.15 | +0.41 |
| wikitech @4G | 50.02 | 49.89 | +0.13 | +0.11 |
| tencentBlock @1G | 57.53 | 57.74 | −0.21 | −0.12 |
| metaStorage 1 @1G | 40.22 | 40.52 | −0.30 | −0.11 |
| ibm objectstore 000 @256M | 50.72 | 51.38 | −0.66 | |
| tencentBlock @256M | 38.24 | 38.97 | −0.73 | −3.58 |
| metaCDN rprn @4G | 31.55 | 32.28 | −0.73 | +10.69; density retains large objects |
| google thesios c2 @4G | 24.07 | 22.62 | +1.46 | +1.59; reactive is below LRU |
| google thesios c2 @16G | 26.30 | 25.01 | +1.30 | +1.46; reactive is below LRU |
| google thesios c1 @4G | 15.09 | 14.90 | +0.19 | +0.64 |
| google thesios c3 @4G | 16.56 | 16.71 | −0.15 | −0.24 |
| google thesios c2 @1G | 20.98 | 21.05 | −0.07 | +0.06 |
| outbrain sorted @4096 | 84.56 | 84.46 | +0.10 | (unweighted; LRU 80.44) |
| outbrain sorted @8192 | 89.58 | 89.67 | −0.09 | (unweighted; LRU 87.24) |
| family | disposition |
|---|---|
| arc (23 files) | A.1 / A.3 and the study corpora; P3, P4, P6, P7, MergeP @64k are frozen in an unspent study holdout |
| cloud_physics (16 files) | A.1 / A.3 corpus; w015 and w044 @16k frozen in an unspent study holdout |
| corda (2) | large: A.1 / A.3; small: the canonical cross-tier stress trace |
| umass storage (5) | Financial1/2 and WebSearch2 in A.1; WebSearch1/2/3 spent across holdouts; WebSearch3 scored the merge gate above |
| msr_cambridge (15) | A.1 / A.3 and holdouts; proj_4 scored the merge gate; hm_1 @64k frozen unspent |
| wikibench (4 shards) | 1190/1192: the merge gate; 1191a/b: first measured above. Unspent LRU-only rungs remain for a future freeze |
| libcachesim oracleGeneral (new set) | alibabaBlock, tencentBlock, metaStorage, MetaCDN_rprn, wikitech, cloudphysics w01: first measured above. metaKV_202401 measured saturated (LRU 88–95 across 1G–16G weight, no informative cell); twitter52 sample10 (8.1G) deferred, its family already covered |
| libcachesim classic (3) | tencentPhoto: the merge gate; metaCDN / metaKV: spent in earlier holdout rounds |
| google_cluster1-3 (Thesios) | Google's Thesios storage I/O traces: READ rows, the (file, offset) range as the object, requested bytes as its weight. In band at 1G–16G weight; measured above |
| twitter cluster52 (3 shards) | .050 in A.3; .100 spent in an earlier holdout; .000 first measured above (in band at 64M weight; ≥90 saturated above) |
| snia/ibm objectstore (3) | 000 measured above; 050 degenerate (~no reuse in Part0); 097 saturated (LRU 93.6 at 256M weight) |
| snia/systor17-01 (per day × LUN) | day-09 LUN0/LUN2 first measured above; other days and LUNs pristine |
| snia/k5cloud (14 volumes) | v0 and v25 frozen in the unspent stillness holdout; the other 12 degenerate |
| snia/exchange (98 shards) | four shards @256k frozen in the stillness holdout; the family is otherwise window-insensitive (ceiling − LRU ≤ 0.75pp) |
| cache2k (4) | in band at small and mid sizes, first measured above; orm-night and web12 @4096 are frozen in the unspent tier-boundary holdout |
| gradle build-cache (1) | high locality: in band only at 1024 (measured above); ≥4096 sits at 91+ |
| scarab (2) | not too small: in band across 4k–256k, measured above; recs @256k is the battery's largest entry-cell win |
| all-trc (37 files) | 10 plain LIRS streams (loop, multi1-3, cs, gli, ps, cpp, sprite, 2_pools), saturated in the gate and corpus; the other 27 (vortex, sor, gnuplot, … and their compositions) are the ClockPro authors' segmented program-trace container, N <seg> headers with I/O <id> <time> records, whose key mapping was lost with the format, so no reader parses them |
| outbrain | saturated: the page-views sample's document working set is ~60k, so it reads 99.4 from 65k entries even time-sorted (arrival order was not the cause); the two in-band cells at 4096/8192 measured above, both ties |
| address (6) | measured flat: every trace is size-insensitive at 512–16k (gzip 66.7 ±0.02pp across 32× size; twolf/gcc/swim ≥90 plateaus; mcf ~1 throughout), so nothing for any climber to tune |
| adaptSize (2) | measured tiny: usertrace-98 is 10,492 requests with zero evictions at 4096 (its .xz is the raw 1999 form the reader does not take; use the .tr); request.trace is 66,987 requests ≈ 4 density samples |