When many users stream different videos at the same moment, a server can save bandwidth by having each user store pieces of many files in advance. It then broadcasts XOR combinations of pieces, and each user cancels out the parts it already holds. This technique, called coded caching, has two well-known problems. Its guarantees assume every file is equally likely to be requested, which real demand is not. It also requires cutting each file into a number of pieces (the "subpacketization") that grows combinatorially with the number of users. Schemes that do handle skewed demand group files into popularity tiers. They fix those tiers either by hand or by solving an optimization over popularity estimates. In practice those estimates are least reliable exactly where most files live: the long tail of rarely requested content.
We propose to borrow a tool from collider physics, where the same structural problem has a mature solution. Jet grooming removes soft, diffuse background radiation from a particle jet. It works by walking a clustering tree from the top down and discarding branches that carry too small a share of the momentum relative to their angular separation. Its key property is that the cleaned result is provably insensitive to uniform background noise. We map files to particles, request probability to momentum, and log-popularity distance to angle. A Soft-Drop-style rule applied to a popularity clustering tree then chooses how many cache tiers to create and which files share them. Every tier shares one common sub-packet size, so the server can XOR across tiers without zero-padding. The total subpacketization stays within a hard budget. Our central claim is narrow and falsifiable. On exact popularities, a groomed tiering should come close to the best tiering found by exhaustive optimization. When tail popularities are estimated from finite request logs, it should degrade measurably less than that optimum, just as recursive grooming is insensitive to pileup.
Background and Gap
Jet grooming supplies the method. Trimming (Krohn et al.) discards subjets below a fixed momentum fraction. Pruning (Altheimer et al.) vetoes soft, wide-angle merges. Soft Drop (Larkoski et al.) unwinds an angle-ordered tree. It keeps a branching only if the softer child's momentum fraction exceeds $z_{\text{cut}}(\Delta R/R_0)^\beta$, where $z_{\text{cut}}$ is a soft threshold, $\Delta R$ the angular separation of the two children, $R_0$ the jet radius, and $\beta$ a dial that sets how strongly the cut depends on angle. Soft Drop's appeal lies in what it guarantees: it removes a class of hard-to-control contributions, so its output can be calculated from first principles. Recursive Soft Drop (Dreyer et al.) continues into both retained branches. In the infinite-depth limit it gives a groomed jet with zero "catchment area", meaning it does not respond to uniform background at all. We reuse the tree-walking procedure, the form of the cut, and the recursion. We do not claim the physics carries over. What carries over is a design pattern: a local test that is cheap to compute and has analyzable error.
The caching literature motivates the problem and constrains the design.
Grouped coded caching (Niesen and Maddah-Ali) gives popular groups more memory but never codes across groups, which forfeits multicast gain. Cross-Level Coded Delivery (Özfatura and Gündüz) does code across three fixed tiers. However, its delivery optimization becomes intractable as the number of users $K$ grows. Strategy $\beta$ (Quinton, Sahraei, Gastpar) gives every file the same number of equal-sized pieces and expresses popularity through nested placement subsets. This avoids the zero-padding loss documented by Dong et al., but delivery is specified only for a small example. Optimization-based placement (Fundamental Structure of Optimal Cache Placement; Memory-Rate Tradeoff under Nonuniform Random Demands) characterizes the best placement given known popularities. None of these works asks how many tiers to use when popularities are noisy. None ties that choice to a subpacketization budget.
That budget is real. The canonical scheme needs $\binom{K}{t}$ pieces per file, where $t = KM/N$ for $N$ files and cache size $M$. This is about $10^{14}$ at $K=50$, as stressed by Ramamoorthy and Deng et al.. Low-subpacketization placements exist and serve as per-tier building blocks: Ruzsa–Szemerédi graphs (Shanmugam et al.), block-code designs (Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes), and placement delivery arrays (Michel and Wang). They assume uniform demand, however.
On the complexity side, delivery under arbitrary placement becomes an index coding problem. The best size-aware method, SACM (Asghari et al.), has a $(1+\log K)$ approximation guarantee but runs in time exponential in $K$. Joint placement problems are typically NP-hard (Golrezaei et al.; Dehghan et al.). This constrains us: any tier-selection method that calls a delivery solver inside its search loop will not scale.
Core Claim
Treat the file library as a "jet." Sort files by estimated popularity $\hat p_i$ and build a binary tree by repeatedly merging the adjacent groups closest in log-popularity; this is the analog of angle-only clustering. Then walk the tree from the root. At a node whose children have total request mass $P_1$ and $P_2$ and log-popularity separation $\Delta$, keep the split as two distinct cache tiers only if
$$\frac{\min(P_1,P_2)}{P_1+P_2} > z_{\text{cut}}\left(\frac{\Delta}{\Delta_0}\right)^{\beta},$$
where $\Delta_0$ is the full log-popularity range of the library. When a split fails, the lighter child is not discarded. Instead it is absorbed into a single fallback tier served by a uniform low-memory placement, and the walk continues into the heavier child. With recursion, a split that passes means the walk continues into both children. The walk also stops once adding another tier would push the common subpacketization past a budget $F_{\max}$.
All retained tiers share one piece size, following Strategy $\beta$, so the server can XOR across tiers without padding. Each tier's placement is drawn from a budget-respecting construction: the canonical scheme for small $K$, or a placement delivery array or block-code design for large $K$.
The rule has a structural property that motivates the robustness claim. Every rejected split routes at most a $z_{\text{cut}}$ fraction of its parent's mass to the fallback tier. Tail files therefore influence the tiering only through their aggregate mass, never through their individual ranks. Aggregate mass is precisely the quantity that a finite request log estimates well.
Research Program
The work has three parts.
The first part is analytical. We will prove an upper bound on the excess expected delivery rate of the groomed tiering relative to the best tiering of the same depth. We conjecture the bound scales as the tree depth times $z_{\text{cut}}$, because each rejected split misallocates at most that mass fraction. We will also prove a stability bound: a bounded perturbation of the tail popularities changes the groomed tiering only at nodes whose mass share lies within that perturbation of the threshold. This is our counterpart to Soft Drop's calculability and to the zero catchment area of Recursive Soft Drop.
The second part supplies the missing general delivery for a nested equal-piece placement with $L$ tiers. We will derive a closed-form delivery for the special case in which every tier uses the canonical placement with nested caching parameters. Arbitrary $K$ and $N$ are explicitly left open by Quinton et al. For other cases we will use SACM as a reference solver at small $K$.
The third part is a complexity accounting. Grooming costs $O(N\log N)$ time, essentially sorting plus one tree walk. Exact tier selection, by contrast, must evaluate a coupled delivery cost for each candidate partition.
Baselines
The naive reference point is the canonical uniform scheme of Maddah-Ali and Niesen, which ignores popularity. We pair it with plain uncoded caching of the most popular files that fit in memory. Together these show how much any popularity awareness is worth.
The structured competitors are grouped coded caching, CLCD with its three fixed tiers, and Strategy $\beta$ with hand-chosen tiers. All three run on identical libraries, memory sizes, user counts and subpacketization budgets. CLCD is restricted to the $K$ range where its optimization can be solved.
The strongest competitor is exhaustive optimal tiering. It searches every contiguous partition of the sorted library into at most $L$ tiers, subject to the same $F_{\max}$, and scores each candidate with the same delivery evaluator: our closed form where it applies, and SACM otherwise. It also receives the same popularity estimates. Because it is optimal on those estimates, it is the ceiling on clean data. We found no reported result on Lacuna for the expected delivery rate of any of these schemes under the specific Zipf settings we use, so all baseline numbers will be produced in our own harness rather than quoted.
The groomed method beats exhaustive tiering only if one of two things happens. It might match the exhaustive method within the analytical bound on clean popularities while running orders of magnitude faster. Or it might achieve lower true expected rate when both methods are fit on noisy estimates.
Three ablations isolate the ingredients. Setting $\beta=0$ turns the rule into a flat mass-fraction threshold, which tests whether the separation term matters. Stopping at the first passing split (plain rather than recursive grooming) tests whether the recursion matters. Dropping the shared piece size, so that tiers carry different subpacketizations, reintroduces padding and isolates Strategy $\beta$'s contribution.
Why not just…?
Why not just solve the tier partition by dynamic programming? Choosing contiguous groups over a sorted list is the classic setting for dynamic programming. If tiers were coded independently, as in grouped coded caching, the cost would separate across groups and dynamic programming would be exact and cheap. This is a real threat in that regime, and we will concede it there. Once coding crosses tiers, however, padding and shared transmissions couple the groups, so each evaluation requires a delivery computation. Even a perfect search then optimizes noisy tail estimates. The decisive experiment is the noisy-estimate comparison below. If the dynamic-programming or exhaustive optimum on estimated popularities matches grooming's true rate, the robustness claim fails. The contribution then shrinks to speed alone.
Why not just use a fixed popularity threshold, as CLCD and grouped caching do? A fixed threshold is the $\beta=0$, single-split special case of our rule, so the ablations measure this directly. Our hypothesis is that a fixed cut cannot adapt its number of tiers to the Zipf exponent and the memory size. That would cause it to over-split flat libraries and under-split steep ones.
Why not just smooth the popularity estimates, for example by fitting a Zipf exponent, and then optimize? Parametric smoothing does reduce tail noise. It fails when real demand departs from Zipf form. We will include fitted-Zipf-then-exhaustive as a further baseline and evaluate it on mixtures of two Zipf laws, where a single-exponent fit is misspecified.
Proposed Experiments
The file supplies no public request traces, so the evaluation uses synthetic demand. Libraries have $N$ from 100 to 10,000 files, with Zipf exponents from 0.4 to 1.4 and two-component Zipf mixtures. User counts $K$ run from 4 to 64. Memory ratios $M/N$ run from 0.05 to 0.5, and the subpacketization budget $F_{\max}$ ranges from $10^2$ to $10^6$. Popularity estimates come from request logs of length $n$, sampled from the true law, with $n$ swept from 10 to 1,000 times $N$.
The metrics are true expected delivery rate, measured in file units averaged over random demand vectors, the realized subpacketization, and the wall-clock time for tier selection.
The first decisive check is clean-data fidelity: the gap between groomed and exhaustive rates should fall within the derived depth-times-$z_{\text{cut}}$ bound across the sweep.
The second decisive check is robustness. With both methods fit on finite logs, we compare their true rates as $n$ shrinks. The proposal stands only if grooming's excess rate grows strictly more slowly than the excess rate of exhaustive optimization at small $n$. The stability bound predicts this gap concentrates in steep-tailed, small-memory settings.
The third check is scaling. At $K$ beyond the reach of SACM and CLCD, groomed tiering with placement-delivery-array tiers should still beat the uniform scheme within the same $F_{\max}$. This shows the method remains usable exactly where the complexity results rule out the competitors.
References
- Jet trimming
- Jet substructure at the Tevatron and LHC: new results, new tools, new benchmarks
- Soft drop
- Recursive Soft Drop
- Coded Caching With Nonuniform Demands
- Uncoded Caching and Cross-level Coded Delivery for Non-uniform File Popularity
- A Novel Centralized Strategy for Coded Caching with Non-uniform Demands
- Memory-Rate Tradeoff for Caching with Uncoded Placement under Nonuniform File Popularity
- Fundamental Structure of Optimal Cache Placement for Coded Caching With Nonuniform Demands
- Memory-Rate Tradeoff for Caching With Uncoded Placement Under Nonuniform Random Demands
- Coded Caching with Low Subpacketization Levels
- Decentralized Caching Under Nonuniform File Popularity and Size: Memory-Rate Tradeoff Characterization
- Coded Caching with Linear Subpacketization is Possible using Ruzsa-Szeméredi Graphs.
- Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes
- Placement Delivery Arrays From Combinations of Strong Edge Colorings
- An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching
- FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers.
- On the complexity of optimal routing and content caching in heterogeneous networks