Coded caching lets a server send one broadcast packet that several users decode at once. Each user pre-stores pieces of files, and the server sends the bitwise XOR of pieces that different users want. Each recipient cancels the parts it already holds. The catch is subpacketization: the number of pieces each file must be cut into. In the original scheme it is a binomial coefficient, and at 64 users with a quarter of the library cached it is about $4.8\times10^{14}$ (Ramamoorthy 2018). Practical schemes therefore need explicit combinatorial structures that keep the coding gain while cutting files into few pieces.
This note proposes building those structures as graph lifts. A graph lift (a covering graph) replaces every vertex of a small seed graph by $L$ copies and every edge by a matching between copies, chosen by permutations. Lifts are usually used to destroy short cycles and so to fool local algorithms. We argue that, applied to coded caching, high girth is provably the wrong target, but the lift operation itself is exactly right. Whether an XOR is decodable is a local property, and lifts preserve local structure. So a small seed design can be blown up to hundreds of users for free, and the permutations can be searched to remove only the cycles that block XOR packets from being merged, while keeping the cycles that carry the multicast gain.
Core Claim
The structure being lifted comes from Michel & Wang. They show that a placement delivery array (the table saying which user caches which piece and which pieces are XORed together) is the same object as a strong edge coloring of a bipartite "miss graph". In that graph, piece $j$ is joined to user $u$ when $u$ does not cache $j$. Each color is an induced matching, a set of disjoint edges with no edges between them, and each color is sent as one XOR. Two miss-edges $(j,u)$ and $(j',u')$ conflict exactly when they share a vertex or one of the cross pairs $(j,u')$, $(j',u)$ is also a miss. Conflicts are therefore paths of at most three edges, and 4-cycles are double conflicts.
The research file suggests lifting these graphs to high girth, but a counting argument rules this out. If the miss graph has no 4-cycle, no two users share two missed pieces. Counting pairs of missed pieces gives $K\binom{(1-\mu)F}{2}\le\binom{F}{2}$, where $K$ is the number of users, $F$ the subpacketization and $\mu=M/N$ the cached fraction. This forces $1-\mu\lesssim 1/\sqrt{K}$: users must cache almost everything.
Raising girth in the complementary "hit graph", where piece and user are joined when the user does cache the piece, fails too. An XOR serving $s+1$ users needs the hit graph to contain $K_{s+1,s+1}$ minus a perfect matching. That subgraph is a 6-cycle at $s+1=3$ and contains 4-cycles for $s+1\ge4$. Girth 8 in the hit graph therefore caps the multicast gain at 2.
This sets coded caching apart from settings where girth is a resource. In compressed sensing, girth 6 doubles recovery thresholds (Khajehnejad et al.). In hardness proofs, girth hides global structure from LP relaxations (Arora et al.) and from distributed algorithms (Coupette et al.). In coded caching, some short cycles are the coding gain.
What survives is the locality property those hardness proofs exploit. An induced matching of the seed lifts to an induced matching of the cover, because any cross-edge in the cover projects to a cross-edge in the seed or to a second copy of a seed edge, and lifts of a single edge are matchings. Hence every strong edge coloring of the seed lifts with no extra decodability check.
To keep the cached fraction fixed, the seed must be a multigraph, a "protograph" in LDPC terms. Seed entry $m_{ju}$ becomes $m_{ju}$ cyclic shifts $S_{ju}\subset\mathbb{Z}_L$, so that piece copy $j^a$ is joined to user copy $u^b$ iff $b-a\in S_{ju}$. A lifted edge of type $(j,u,s)$ at offset $a$ and one of type $(j',u',s')$ at offset $c$ can share an XOR iff their vertices are distinct and
$$c+s'-a\notin S_{ju'}\quad\text{and}\quad a+s-c\notin S_{j'u}.$$
Every conflict thus depends only on the difference $c-a$. Translation-invariant delivery "patterns" then cover the cover graph, giving $K=LK_b$, $F=LF_b$ and
$$R=\frac{P}{F_b},$$
where $K_b$ and $F_b$ are the seed's user and piece counts and $P$ is the number of patterns. The rate does not depend on $L$, while the user count grows linearly in $L$.
The claim is that searching the shift sets on a small seed reaches better rate–subpacketization points at moderate $K$ (64 to about 800) than graph products, linear-code designs, or user clustering. The search space is the seed, not the full graph.
Relation to Prior Work
Three lines of work supply structures for low subpacketization. Shanmugam, Tulino and Dimakis map caching to induced matchings in Ruzsa–Szemerédi graphs and get $F=K$ with rate $K^\delta$. They state the construction only pays off at astronomically large $K$. Ramamoorthy 2016 and 2018 (Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes) build resolvable designs from single-parity-check and linear block codes. They reach $F=q^{k-1}$ with rate $q-1$, but are tied to $M/N=1/q$ and are still exponential in $K$. Michel & Wang supply our formalism and combine small arrays by tensor and strong products. Products copy the seed's conflict structure into every coordinate and cannot selectively undo it.
A lift is a different operation. The disjoint union of $L$ seed copies is the identity-permutation lift, which is exactly user clustering. Nontrivial permutations are the only new ingredient, which makes the key ablation clean.
Linear-code designs already carry a $\mathbb{Z}_q$ symmetry, so they can be read as particular algebraic covers. We relax them to free shift search at arbitrary $\mu$.
From the lift literature we reuse one principle: covers preserve radius-limited views. Coupette et al. use it adversarially, and Arora et al. use it to blind local LP constraints. We use it constructively, because decodability is a radius-one condition.
Research Program
The theory has three results. The first is the obstruction lemma above, extended to a tradeoff between girth, memory and multicast gain for both graphs. The second is a lifting lemma with multiplicities, which states the difference conditions on shift sets under which a seed pattern stays an induced matching in the cover. The third is a reduction: minimum-pattern covers of the cover are colorings of a "voltage" conflict graph on the seed edges labelled by $\mathbb{Z}_L$ differences. That turns design into a finite search whose size depends on the seed and on $L$, never on $K$.
Two lower bounds certify how close designs come. The first is $P\ge\sum m_{ju}/s_{\max}$, where $s_{\max}$ is the largest decodable pattern. The second is the uncoded-placement rate of the original scheme of Maddah-Ali and Niesen, $R_{MN}=K(1-\mu)/(1+K\mu)$, used as the reference curve.
The algorithmic work is a shift optimizer. It does local search with exact incremental conflict counting, modeled on protograph-LDPC shift design, but its objective is pattern count rather than girth. We pair it with exact integer programming on seeds small enough to certify optimality. Seeds come from small optimal arrays, from blocks of the original scheme, and from Ramamoorthy designs. All code and generated arrays will be released, because the file finds no public benchmark implementation for these schemes.
Baselines
The naive reference is uncoded delivery with memory sharing, rate $K(1-\mu)$ at $F=1$. Ramamoorthy 2016 shows memory sharing loses badly on rate. Any lifted design that does not beat this curve is a failure.
The original scheme of Maddah-Ali and Niesen gives the rate floor at enormous $F$; for example $R\approx2.82$ at $K=64,\ \mu=1/4$ with $F\approx4.8\times10^{14}$. We report every design's rate gap to it.
The strongest structured competitors are graph products and linear-code designs. For Michel & Wang, the file reports $F=5{,}215$ packets and delivery rate $16$ at $K=784$, against roughly 2.6 million packets and rate $39.5$ for the comparison scheme. It also reports $F=3{,}003$ against $101{,}147$ at $K=182$. The file does not report memory ratios for these points, so we will rebuild their constructions and recompute $\mu$ before comparing. For Ramamoorthy 2018, the file reports $F=1.07\times10^6$ at $K=64,\ \mu=0.25$; no reported rate for that point was found on Lacuna, so we will compute it from the construction.
Fairness is enforced by evaluation design. We match $K$ and $\mu$ exactly and plot full $(F,R)$ frontiers rather than single points. Every searched design gets the same CPU budget as the strongest heuristic baseline, measured in wall-clock core-hours.
The ablation that isolates the proposal's key ingredient is an identity versus random versus optimized comparison on the same seed. The identity lift equals clustering. Random shifts are the "just use a random cover" option. Optimized shifts are the proposal. A further heuristic baseline is a random bipartite miss graph at the same density, colored greedily.
The attention-network array designer of Deng et al. will be run if code can be obtained; no reported result was found on Lacuna for it at our settings.
Beating the strongest baseline has a concrete meaning. At $K=784$ and Michel–Wang's recomputed $\mu$, we need a rate below 16 at $F\le5{,}215$, or rate 16 at clearly smaller $F$. At $K=64,\ \mu=1/4$, we need $F$ well below $1.07\times10^6$ at equal or lower rate.
Why not just…?
Why not just lift to high girth, as the graph-lift literature does? The counting arguments in the Core Claim settle this before any experiment. A 4-cycle-free miss graph forces $1-\mu\lesssim1/\sqrt{K}$. Hit-graph girth 8 caps the multicast gain at 2. We will still include a maximum-girth lift as a baseline, to show empirically that its rate collapses toward uncoded delivery.
Why not just cluster users and run the original scheme in each cluster? This is the most serious threat. Clustering gives $R=K(1-\mu)/(1+K_0\mu)$ with only $\binom{K_0}{K_0\mu}$ pieces for clusters of size $K_0$, and for a fixed piece budget it is strong. The file's claim that clustering cannot match graph products is not backed by a reported number. Because clustering is exactly the identity lift, the ablation measures directly what nontrivial permutations add. If optimized shifts do not move the frontier beyond identity lifts at matched $F$, the proposal's central claim is false, and we will report it.
Why not just search for arrays directly with greedy coloring or a neural designer? Direct search must handle a conflict graph on $K\cdot F$ edges, and strong edge coloring is hard in general. It also offers no certificate that a large instance is decodable. The lift moves the search onto the seed and gives decodability by the lifting lemma. The random-graph greedy baseline and, where available, the neural designer test whether the reduction actually buys better designs, not just faster ones.
Proposed Experiments
The test grid covers $K\in\{64,182,784\}$ and $\mu\in\{1/8,1/4,1/2\}$, plus Michel–Wang's recomputed points. For each grid point and lift degree $L\in\{2,\dots,64\}$, we report $F$, rate, gap to $R_{MN}$, gap to the pattern lower bound, and search time.
The first decisive check is the identity-versus-optimized ablation at matched $(K,\mu,F)$; it determines whether lifting is anything more than clustering. The second is the head-to-head at $K=784$ against $F=5{,}215,\ R=16$. The third is a seed-size study at fixed $K$, trading seed size against $L$. It tests the prediction from $R=P/F_b$ that rate is set by the seed while user count scales freely. If shift optimization reliably reaches the pattern lower bound on small seeds, this would also give the first explicit moderate-scale counterpart to the Ruzsa–Szemerédi existence result.
References
- Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes
- Placement Delivery Arrays From Combinations of Strong Edge Colorings
- Reconstruction guarantee analysis of binary measurement matrices based on girth
- Proving Integrality Gaps without Knowing the Linear Program
- A Breezing Proof of the KMW Bound
- Coded Caching with Linear Subpacketization is Possible using Ruzsa-Szeméredi Graphs.
- Coded Caching with Low Subpacketization Levels
- Fundamental Limits of Caching
- Placement Delivery Array Design via Attention-Based Deep Neural Network