When a video is stored as a coarse base layer plus refinement layers, every edge cache must decide how much of its memory goes to each layer. The theory of coded caching shows the right answer flips with memory size. Coded caching means that caches are filled ahead of time so that later broadcasts can be XOR combinations serving several users at once. With little memory, one ordering of layers wins; with more memory, the opposite ordering wins. What the theory cannot yet say, for more than two users, is where the flip happens or how wide the uncertain zone around it is. Current work offers achievable schemes, which are upper bounds on the load a cache must receive, and loose cut-set lower bounds. The gap between them is too wide to settle the question.
This note proposes to answer the question by exclusion rather than by optimization. Experimental particle physics works this way. When a telescope sees no signal, it rules out every region of model parameter space that would have produced one, and it stays honest about unknown astrophysical quantities by profiling over them as nuisance parameters. We carry that logic into caching. For each memory size, we prove which allocations across layers cannot come close to the best known delivery load under any delivery scheme. We then make that exclusion robust to demand popularity that is only estimated from data. The output is an exclusion envelope in the plane of memory against the fraction of memory given to the base layer. It has two uses. It brackets the regime-inversion threshold with a certificate, and it tells a system designer which allocations are provably wasteful for every demand distribution consistent with observed traces.
Core Claim
The claim is that restricting the lower bound to a slice of allocation space makes it tight enough to exclude large regions, even where the global lower bound is loose. Two restrictions make this possible. First, placement is uncoded, meaning caches hold only raw file pieces. Second, the placement has a given layer split. Under both restrictions, delivery becomes an index-coding problem with fixed side information. Index coding is the problem of broadcasting to receivers that already hold some of the messages.
Write $\alpha \in [0,1]$ for the fraction of each cache devoted to base layers. Write $R^{\mathrm{lb}}(M,\alpha)$ for the best lower bound on worst-case delivery load over all uncoded placements with that split. Write $R^{\mathrm{ach}}(M)$ for the best achievable load from any known scheme at memory $M$. An allocation is excluded at slack $\epsilon$ when
$$R^{\mathrm{lb}}(M,\alpha) > (1+\epsilon)\,R^{\mathrm{ach}}(M).$$
Excluded points are provably at least $\epsilon$ worse than a known scheme, whatever delivery is used. The unexcluded region is the envelope. If it is narrow, it localizes the ordering inversion.
When file popularity $\theta$ is unknown, we compute the envelope for every $\theta$ inside a data-driven confidence set. We exclude a point only if it is excluded throughout that set. This is the profile-over-nuisance construction used for J-factor uncertainty in dwarf-galaxy searches, where the J-factor is the integrated dark matter density that sets the expected signal.
Where This Sits in Prior Work
Three papers supply the phenomenon and motivate the gap.
Centralized Coded Caching for Heterogeneous Lossy Requests studies Gaussian sources split into successive refinement layers under uncoded placement. It compares two policies. Ordered Cache Allocation (OCA) fills caches with base layers first. Proportional Cache Allocation (PCA) splits memory in proportion to layer sizes. The paper proves optimality for two users and two files, finds that PCA dominates beyond very small caches, and leaves a gap to the cut-set bound for larger systems.
Memory-rate trade-off for caching and delivery of correlated sources shows the same inversion for correlated files. Correlated files are split, following the Gray-Wyner source-coding construction, into a shared "common" description and file-specific "private" descriptions. Private descriptions are cached first at low memory and common ones at high memory. Optimality is again proven for two users, with a residual gap at intermediate memory when there are more users.
Coded Caching With Heterogeneous User Profiles finds an analogous shift for user classes, from content popular across classes to content specific to each class, without matching lower bounds.
All three establish that ordering matters. None of them certifies which orderings can be ruled out at a given memory size, and that certificate is our target.
Two papers supply the method.
An Index Coding Approach to Caching with Uncoded Cache Placement turns uncoded placement into index coding. It derives lower bounds from acyclic subgraphs of the side-information graph, combined by eliminating variables from a system of linear inequalities. We reuse that bound. The difference is that we keep the layer split as a fixed constraint instead of optimizing it away, and we solve the resulting inequalities as a linear program rather than by closed-form elimination.
The Exact Rate-Memory Tradeoff for Caching With Uncoded Prefetching gives both the exact uncoded tradeoff for single-layer files and a leader-based delivery scheme. In that scheme, one user per requested file is designated the leader and transmissions are designed for leaders only. We use it inside the achievable benchmark $R^{\mathrm{ach}}$.
One tension in prior work matters here. PCA gets its multicast opportunities by making all users symmetric. Yu et al., by contrast, show that asymmetric leader-based delivery is necessary when users outnumber files. It is therefore unknown whether the PCA-versus-OCA picture survives once duplicate layer requests are handled by leaders. Our envelope is computed against the leader-aware benchmark, so it answers that question directly.
The third direction supplies the statistical template rather than any caching content. Combined search in dwarf spheroidal galaxies for branon dark matter annihilation signatures with the MAGIC telescopes combines four targets in a joint likelihood. It treats J-factors as nuisance parameters and reports 95% confidence-level exclusions in mass–cross-section space. Cuoco et al. builds exclusions that stay valid across halo-shape assumptions.
We borrow two ideas from these searches. One is combining independent "targets", here user classes or trace segments, into one likelihood for the popularity nuisance. The other is reporting exclusion that holds across the nuisance range rather than at a single point estimate. To our knowledge, no caching paper in the file reports statistically qualified exclusion of any kind.
Research Program
The first component is the allocation-restricted lower bound. For a layered library with $N$ files, $L$ layers and $K$ users, we enumerate symmetric uncoded placements. A placement is described by the fraction of each layer stored at each subset size, subject to the memory budget and the split $\alpha$. For each demand type we write the acyclic index-coding inequalities of Wan et al. A demand type, in the sense of Yu et al., is a request pattern up to relabeling of users and files; for layered content it includes how many users ask for each quality level. Minimizing the worst-case sum over placement variables at fixed $\alpha$ gives $R^{\mathrm{lb}}(M,\alpha)$.
Symmetrizing over users with equal cache size and equal quality requests keeps the linear program polynomial in $K$ for fixed $L$. This is the step that makes $K=10$ to $30$ feasible. Heterogeneous cache sizes, as in the $M_k = 0.2kM$ setting of Yang and Gündüz, break some of this symmetry, and we handle them by symmetrizing within cache-size groups.
The second component is the achievable side. $R^{\mathrm{ach}}(M)$ is the lower envelope, over memory sharing, of OCA, PCA, the Gray-Wyner multiple-request scheme where it applies, and a layered leader-based scheme we build by running Yu et al.'s delivery separately on each refinement layer's request pattern.
The third component is robust exclusion under estimated popularity. From user–video interactions, we fit a Zipf-type popularity model per user class. We form a joint profile likelihood across classes, the analogue of the multi-dwarf combination, and take its 95% confidence region for $\theta$. A point $(M,\alpha)$ is excluded only if the exclusion inequality holds at every $\theta$ in that region. Average-load versions of both bounds replace worst-case ones here, since popularity only matters on average.
The fourth component is analysis. We report how the envelope's width scales with $K$. We report whether the inversion threshold moves once leader-based delivery is included, which resolves the tension between PCA's symmetry and leader-based asymmetry. We also check that the envelope reproduces the five known regimes of the two-user, two-file case.
Baselines
The do-nothing reference is the plain cut-set bound of Yang and Gündüz used as $R^{\mathrm{lb}}$, with no allocation restriction and no index-coding structure. It will exclude almost nothing. Any nonempty exclusion region we obtain beyond it measures what the method adds. It is run on exactly the same systems and memory grid.
The strongest existing achievable methods are PCA and OCA from Centralized Coded Caching for Heterogeneous Lossy Requests, and the leader-based scheme of The Exact Rate-Memory Tradeoff for Caching With Uncoded Prefetching. They are strongest because they are the schemes whose relative ordering the inversion question is about. For single-layer files, Yu et al. report a peak rate of 12.67 against 14.12 for earlier methods at $N=K=30$ with limited cache. We will reproduce that figure as a correctness check of our leader-based implementation before layering it. For the Gaussian $K=N=10$ heterogeneous benchmark, Lacuna gives no numerical rate points; the file reports only the $M_k=0.2kM$ scaling and regime classifications. We will therefore regenerate PCA and OCA curves from the paper's definitions.
Beating the baselines here does not mean a lower achievable rate. It means certifying, on the same grid, that one of OCA's or PCA's splits is excluded at some memory. It also means bracketing the switch point more narrowly than the gap between the baselines' own curves and the cut-set bound would allow.
The key ablation removes the allocation restriction. Computing the index-coding bound optimized over all $\alpha$ gives a single number per $M$ that excludes no allocation. That isolates the effect of conditioning on the split. A second ablation replaces the likelihood confidence set with the point estimate of popularity. It is scored by how often point-estimate exclusions are violated on held-out demand, which shows whether the nuisance treatment is necessary.
For the trace-level setting, the reference system is NCTM: A Novel Coded Transmission Mechanism for Short Video Deliveries. NCTM reports network-load reductions of 3.02%–14.75% and a 23.01% peak-traffic reduction versus CDN-supported schemes on MAWI and FCC18 traces. We use it as the practical operating point: we check whether its implied allocation lies inside or outside our envelope.
Why not just…?
Why not just grid-search the known schemes over $\alpha$ and pick the best? This is the reviewer's most natural alternative, and it is cheap. It tells you which of the existing schemes wins. It cannot tell you whether an untried delivery scheme would reverse the ordering, and that is exactly the open question left by the gaps in Yang and Gündüz and in Hassanzadeh et al. We treat the grid search as the achievable half of our construction, not a competitor.
The real threat is different. If the restricted lower bound turns out as loose as the cut-set bound, the envelope will be nearly the whole plane and the grid search is all one can say. The unrestricted-bound ablation and the envelope-width-versus-$K$ curve will show this directly. If exclusion vanishes beyond $K\approx 4$, we will report that and restrict the claim to small systems.
Why not just use the cut-set bound per allocation? Cut-set bounds ignore which specific pieces each user holds, and that information is where uncoded placement's structure lives. Wan et al. obtain bounds tighter than cut-set precisely by exploiting side-information graphs. The do-nothing baseline measures this gap exactly.
Why not just do minimax over the whole popularity simplex instead of a likelihood confidence set? Worst-case popularity is almost always uniform-like and discards what traces reveal. It is a legitimate conservative option, and we run it. We expect the confidence-set exclusion to be strictly larger while retaining coverage on held-out data. If minimax excludes nearly as much, the astrophysics-style nuisance treatment is unnecessary and we will say so.
Why not just bootstrap the empirical optimum? Bootstrapping gives uncertainty about which known scheme is best under sampling noise. It gives no certificate against unknown schemes. It is complementary, and we report it alongside.
Proposed Experiments
The first testbed is the Gaussian successive-refinement model of Yang and Gündüz with two and three layers. We use $K=N=2$ to check that the envelope reproduces the five exact regimes, and then $K=N=10$ with homogeneous caches and with $M_k=0.2kM$.
The second testbed is the doubly symmetric binary source from Hassanzadeh et al., using the common/private split as the "layers". It is known to be exact at $K=2$, with a gap within half the conditional entropy for $K>2$ at intermediate memory. Here we ask how much of that intermediate region our envelope excludes. The three-component discrete source provides a third-file check.
The empirical testbed is the KuaiRec small matrix, with 1,411 users, 3,327 items and 99.6% density, from KuaiRec. Its dense watch-time data let us define quality-layer demand: a user watching past a duration threshold requests refinement layers. User-feature clusters serve as the combined "targets" in the popularity likelihood. MAWI and FCC18 traces are used only to place NCTM's operating point.
Metrics are three. The first is the excluded area fraction of the $(M,\alpha)$ plane. The second is the width of the certified interval around the inversion threshold. The third is empirical coverage: across held-out time windows of KuaiRec, the fraction of excluded allocations that are in fact beaten by $(1+\epsilon)$ under realized demand. Nominal is at least 95%, mirroring an injection-and-recovery test in dwarf-galaxy searches.
Four decisive checks determine whether the idea works. First, the envelope must match the known exact regimes at $K=N=2$, or the bound construction is wrong. Second, at $K=10$ the certified inversion interval must be narrower than the interval allowed by the cut-set baseline. Third, including leader-based delivery either moves the PCA/OCA switch point or provably does not, which settles the symmetry-versus-leader tension. Fourth, confidence-set exclusions on KuaiRec must keep nominal coverage while point-estimate exclusions do not. Failing the second check would mean the approach does not scale and should be scoped down. Failing the fourth would mean the nuisance machinery borrowed from astroparticle searches adds nothing here.
References
- Centralized coded caching for heterogeneous lossy requests
- Memory-rate trade-off for caching and delivery of correlated sources
- Coded Caching With Heterogeneous User Profiles
- An Index Coding Approach to Caching with Uncoded Cache Placement
- The exact rate-memory tradeoff for caching with uncoded prefetching
- Combined search in dwarf spheroidal galaxies for branon dark matter annihilation signatures with the MAGIC telescopes
- Constraining heavy dark matter with cosmic-ray antiprotons
- NCTM: A Novel Coded Transmission Mechanism for Short Video Deliveries
- KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems