Cache admission: fill one premium slot without hindsight¶

A content delivery network (CDN) has one premium slot: an object pinned in memory at every edge location for the next 24 hours. Objects are published one at a time, each with a predicted hit count, and you must pin or skip each one as it arrives; once the slot is filled it stays filled until tomorrow. Pin too early and a weak object takes the slot; wait too long and you may end up with nothing better. This page shows a simple rule the library ships for this kind of one-shot choice, what it does on a sample day, and what you can and cannot promise about it. It is written for a CDN or edge-capacity owner and the engineers behind the admission service.

At a glance


Question	As objects are published one by one, which one gets the single premium slot?
Owner	Edge capacity; the admission service applies the rule per publish event.
Today's habit	Pin the first object published.
What this adds	`single_item_max_of_samples`: take yesterday's predicted hits at each of today's publish slots (one past sample per arrival), use the largest as the bar, skip every object below it, pin the first one at or above it.
Demo outcome	Bar 6.0. Today's habit pins an object worth 1.0 expected hits; the rule pins one worth 9.0. The best in hindsight was 12.0.
Kind of example	A helper, not a decision: there is no act/abstain verdict and no decision record.
Example id	`cache_admission` (`uv run grounded-decision examples cache_admission`)

For a review slide: "The bar rule pinned a 9-hit object where pin-first took a 1-hit one. On average over days it earns at least half of the best object in hindsight, if yesterday's slots are like today's; on any single day it can do worse, so we measure its share every day."

The question today¶

The slot is a premium tier, not the whole cache: one object served from memory everywhere, for a launch trailer, a software release or a breaking news page. The popularity model predicts hits for each object at the moment it is published. Two facts make the choice hard:

It is online. You see objects in publication order, and you do not know what will be published later today.
It is irrevocable. A skipped object goes to the ordinary disk tier and cannot be promoted later; a pinned object stays until tomorrow.

The ordinary multi-object cache, with eviction, is a different problem and not what this helper is for.

Where today's habit goes wrong¶

Today's sequence, in publication order, with predicted hits:

Order	Object	Predicted hits
0	`obj_0`	1.0
1	`obj_1`	1.5
2	`obj_2`	9.0
3	`obj_3`	2.0
4	`obj_4`	12.0

Pinning the first object fills the slot with obj_0, worth 1.0 expected hits. The 9.0 and 12.0 objects arrive later and never get a look. The opposite habit, waiting for "something big", has no stopping rule: on a quiet day it keeps waiting and pins nothing worthwhile.

What the library will and will not claim¶

The helper takes one past sample per arrival: yesterday's predicted hits at the same five publish slots, 2.0, 0.5, 6.0, 3.5 and 5.0. The bar is the largest of them, 6.0. It skips every object below the bar and pins the first object at or above it. If nothing reaches the bar, it pins the last object of the day, so a non-empty day always fills the slot. This is a threshold rule from the theory of prophet inequalities: results that compare an online rule with a "prophet" who sees the whole day in advance and always picks the best.

The library claims	The library does not claim
The rule is a single pass and never revisits a skipped object.	That it pins the best object of the day. In the demo it pins 9.0 and misses 12.0.
The result reports `factor_claimed = 0.5`: averaged over days, the rule earns at least half of what the prophet gets, when each slot's value is independent and non-negative and yesterday's value at a slot is drawn like today's (Rubinstein, Wang and Weinberg, 2020). The proof is in `compare/prophet.py`.	That half holds on any single day, or when yesterday is not like today (a launch day, a weekday against a weekend).
The result also reports `lean_factor`, a machine-checked bound for a more general setting, so it is visible.	That `lean_factor` is a usable promise. It is \(2^{-310} \approx 4.8 \times 10^{-94}\).

One-half is an average over days, and only for this bar

Not every day. With the same bar 6.0 and arrivals [6.5, 1.0, 1.0, 1.0, 50.0], the rule pins the 6.5 object: 13 % of that day's best. With arrivals [1.0, 2.0, 0.5, 3.0, 4.0], nothing reaches the bar and the rule pins the last object, 4.0.
Not for a simpler bar. A single scalar bar, such as yesterday's median of individual objects, carries no guarantee. The scalar-bar helper single_item_one_sample reports factor_claimed=None for that reason: with bar 4.0 and arrivals [4.0, 100.0] it pins the 4.0 object, 4 % of the best, and averaged over many days of 50 arrivals with exponentially distributed hits and the bar at the median of a single object it earns about 38 % of the prophet (0.376 by simulation with 20,000 days).

Each line was checked by calling the helpers directly.

The text report of the example prints guarantee: on average >= 1/2 of the offline-best hit count (one past sample per arrival) and SLO claimed: on average >= 1/2 of the offline best (not every day). That is the form in which one half may go into a service-level objective (SLO): an average over days, with the assumption stated.

In the wider literature: single-item prophet inequalities with a threshold achieve one half of the prophet in expectation, and one half is the best possible; the single-sample version used here recovers one half when the rule sees one sample from each arrival's distribution and sets the bar at the largest.
In this project's math catalog: a one-sample prophet inequality for the more general matroid setting (many slots under constraints), with a Lean-checked statement and factor \(2^{-310}\) (catalog result 111). It is true and far too small to promise anything. See one slot, no take-backs (prophet inequalities).

Data you provide¶

Input	Source	Refresh	Owner	Quality bar
Predicted hits per published object	Popularity model	Per publish event	Edge data science	Same units as the bar.
One past sample per arrival (`YESTERDAYS_EXPECTED_HITS`: 2.0, 0.5, 6.0, 3.5, 5.0; bar = the largest, 6.0)	Yesterday's predicted hits at the same publish slots	Nightly	Edge data science	One value per today's slot, drawn like today's. On a launch day or during an outage elsewhere, yesterday is a poor guide and the one-half guarantee does not apply.
Actual hits per pinned object, and the best object of the day	CDN logs	Daily	Edge capacity	Needed to measure the rule's realised share of the best (see Tuning and monitoring).

Worked example¶

From uv run grounded-decision examples cache_admission:

Order	Object	Predicted hits	Pin-first habit	Bar rule (bar 6.0)	Why
0	`obj_0`	1.0	pin	skip	below 6.0
1	`obj_1`	1.5	slot full	skip	below 6.0
2	`obj_2`	9.0	slot full	pin	first object at or above 6.0
3	`obj_3`	2.0	slot full	slot full	already pinned
4	`obj_4`	12.0	slot full	slot full	already pinned; the rule never waits

	Pinned	Predicted hits	Share of best in hindsight (12.0)
Pin-first habit	`obj_0`	1.0	8 %
Bar rule	`obj_2`	9.0	75 %
Prophet (hindsight)	`obj_4`	12.0	100 %

The helper's result dict is index=2, value=9.0, threshold_sample=6.0, factor_claimed=0.5, a guarantee sentence stating the assumptions, lean_factor≈4.79e-94, plus the catalog entry and a note.

What your service does with the result¶

Per publish event, evaluate the rule incrementally: if the slot is empty and the predicted hits are at or above the bar, pin the object. The helper takes a list for the demo; in production you apply the same comparison to each event as it arrives.
At the end of the day, if nothing has been pinned, the helper's fallback is the last object. Decide whether that is what you want; an empty slot may be better than a weak object.
Log every arrival with the bar, the predicted hits and the decision. There is no decision record on this path, so this log is your audit trail.
Promise in your SLO one half only as an average over days, with its assumption (yesterday's slots are drawn like today's), and back it with what you measure (below). Never promise the Lean factor.

Tuning and monitoring¶

The only input is the set of past samples. Choose it so each sample is drawn like its arrival, and check:

Each day, compute the realised share: actual hits of the pinned object divided by actual hits of the day's best object.
Plot the average share over weeks. If it stays below one half, the assumption behind the guarantee is failing: yesterday's slots are not like today's (pick samples from a comparable day, for example the same weekday last week).
Watch for days where nothing reaches the bar and the fallback pins the last object; many such days mean yesterday was unusually strong.

Limits and risks¶

One slot only. The helper does not handle several slots, sizes or eviction. For an ordinary cache, use your cache's own admission policy.
Predictions, not hits. The rule ranks objects by the popularity model's prediction. A wrong prediction pins the wrong object.
No corroboration. A high predicted value from a crawler or a bot looks the same as real demand. To hold a pin when the demand behind it is not corroborated, put a decision module after the rule; the live_cdn_peak desk shows that combination.
Synthetic data. The past samples and the five arrivals are constructed to show a skip, a pin and a missed better object.

Wiring it in¶

from grounded_decision.compare import single_item_max_of_samples

samples = predicted_hits_per_slot_yesterday()  # your function, nightly; one per slot
result = single_item_max_of_samples(predicted_hits_today, samples)
log_admission_choice(result)  # your function
if result["index"] is not None:
    pin_object(object_keys[result["index"]])  # your function

For a streaming service, compute the bar once a night (max(samples)), keep it and a "slot filled" flag in memory, and compare each arrival with the bar directly; the helper's logic is that one comparison. ARRIVING_OBJECTS, YESTERDAYS_EXPECTED_HITS and BAR_EXPECTED_HITS in src/grounded_decision/examples/cache_admission.py are the demo's inputs. All comparison helpers are described in Compare outcomes and features.

Run it yourself¶

uv run grounded-decision examples cache_admission
uv run grounded-decision examples cache_admission --json

The report prints the setup (yesterday's samples, the bar and the arrivals), an index of every arrival, then one block per arrival: what arrived (INPUT), what pin-first would do (NAIVE), the rule's comparison (DECISION), where the object went (OUTPUT) and what happens to the slot (NEXT). CACHE means pin, SKIP means disk tier, gone means the slot was already filled. How to read reports in general: Example library: reading a report.