Coded caching lets a server fill users' local memories with pieces of files during quiet hours. Later it broadcasts mixtures of pieces (typically XORs) that several users can each unscramble at once using what they already hold. The catch is subpacketization, meaning how many pieces each file must be cut into. The classical scheme needs a number of pieces that grows exponentially in the number of users, roughly $4.8\times 10^{14}$ pieces per file for 64 users at a quarter-file cache. A line of combinatorial work cuts this to practical sizes. Every one of those schemes, however, keeps a rigid decoding rule: each broadcast must be cleanly decodable on its own, so every listener must already cache every piece in the mixture except the one it wants. This proposal asks what happens if that rule is dropped.
The idea we want to import is non-unique decoding, borrowed from multi-user information theory. A receiver does not need to identify an interfering message; it only needs its own message to be the same across every explanation of what it heard. In a linear, finite-field setting this has a concrete and cheap form. A user may hear several broadcasts that each contain an uncached interfering piece. If those unknown pieces line up in a small subspace across the broadcasts, the user can eliminate them by combining equations and never learn what they were. Our claim is that this cross-broadcast alignment can lower the delivery load at a fixed, small number of pieces. If it can, the trade-off curve between pieces and load that current constructions trace is an artifact of one-shot decoding, not a limit of the placement.
Core Claim
Fix a cache placement with $F$ pieces per file and $K$ users, as given by any placement delivery array. A placement delivery array (PDA) is a table whose rows are pieces, whose columns are users, and whose integer entries name the broadcast slot in which a user receives a piece it lacks. Delivery under such a table is "one-shot": each piece is recovered from exactly one broadcast. Now allow delivery to be any linear code over a finite field. For user $k$, write the received symbols, after removing cached content, as $y_k = A_k x_k + B_k z_k$. Here $x_k$ are the pieces user $k$ wants, $z_k$ are the uncached pieces it does not want, and $A_k, B_k$ are the coefficient matrices restricted to those pieces. User $k$ can decode, without ever resolving $z_k$, exactly when
$$\mathrm{rank}\,[A_k \;\; B_k] - \mathrm{rank}\,B_k = \dim x_k .$$
This rank condition is the linear counterpart of simultaneous non-unique decoding. Checking it at the receiver costs one Gaussian elimination on a matrix whose size is the number of broadcasts by the number of pieces. There is no list search over candidate messages.
The delivery load is $R = T/F$, the number of broadcast slots $T$ normalized by file length in pieces. One-shot delivery is the special case where every $B_k$ restricted to a single broadcast is zero. The central question is whether the optimum of this rank-constrained problem, which we call aligned delivery, falls strictly below the one-shot optimum at the same small $F$. In particular, we ask whether it falls below the fixed-$F$ lower bound of Coded Caching for MISO Systems with Linear Subpacketization. That bound is proved only for uncoded placement with one-shot delivery, so it does not bind aligned delivery.
There are two possible outcomes, and both matter. A strict gap would mean that low-subpacketization designs have been discarding rate because of the decoding rule. A proof that aligned delivery collapses to one-shot for whole PDA families, such as the Partition PDA, would extend the optimality claims of Cheng et al. from one-shot to all linear delivery. That extension would also be new.
Positioning Against Prior Work
The closest work is A Novel Index Coding Scheme and its Application to Coded Caching. It treats coded-caching delivery as an index coding problem, meaning broadcast to receivers that hold side information. It shows that combining distributed source coding with non-unique decoding beats composite coding: 1/3 versus 0.2987 on a 6-user example. It also shows that the classical delivery is optimal under uncoded placement. That optimality holds only for the classical placement and in the limit of infinitely divisible files. At that placement there is nothing for alignment to gain. We move the same receiver principle to placements with small $F$, where the question is open, and we make it finite-field and finite-length.
The composite coding bounds of On the Capacity Region for Index Coding supply the information-theoretic yardstick for small instances. The gain those bounds capture comes from flat coding with non-unique decoding.
The low-subpacketization constructions motivate the problem and supply the placements we test. These are strong-edge-coloring PDAs (Placement Delivery Arrays from Combinations of Strong Edge Colorings), resolvable designs from linear block codes (Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes), and Ruzsa-Szemerédi graph schemes with $F=K$ but load $K^\delta$ (Coded caching with linear subpacketization is possible using Ruzsa-Szeméredi graphs). All of them pair their placement with one-shot XOR delivery.
Finite-length delivery work, Novel Delivery Schemes for Decentralized Coded Caching in the Finite File Size Regime, constrains the design. Its AHgLC algorithm already uses random linear combinations. Decoding there stays local and unique, and its stronger MHCD algorithm costs $O(2^{2K})$. That cost sets the bar for practical complexity.
Research Program
The first part is computational. For small parameter sets we will compute the exact minimum load under three regimes on the same placement and worst-case demand: one-shot delivery, aligned linear delivery over GF(2) and GF(q), and an information-theoretic lower bound. For aligned delivery, the minimum number of broadcasts equals a minrank-type quantity of the index coding instance that the placement and demand induce. It can be solved exactly for small sizes by integer and SAT search, and bounded above by greedy alignment heuristics for larger ones. For the lower bound we use the polymatroid and composite-coding machinery that is exact at very small sizes, plus maximum-acyclic-subgraph style bounds.
The second part is structural. Any strict gap we find comes with an explicit aligned delivery, and we will extract the pattern behind it. Our working hypothesis is that gains appear when a placement leaves a user with interfering pieces that recur across several of its broadcasts. A one-shot table cannot exploit that recurrence; an aligned code can make it cancel. We will formalize this as an aligned PDA, a table that relaxes the PDA condition so that a user may share a slot with an uncached interferer, provided the interferers it sees span few dimensions across its slots. We will then build families by modifying the cycle-graph strong-edge-coloring products of Michel and Wang.
The third part is analytic. Either we prove a lower bound for aligned delivery that matches one-shot for the Partition PDA, or we exhibit a family where the ratio of aligned to one-shot load diverges with $K$. The second outcome is the regime where Ruzsa-Szemerédi schemes lose a $K^\delta$ factor.
Baselines
The naive reference point is uncoded unicast at the same placement. The server sends every missing piece separately, which gives load $K(1-M/N)$ in the centralized case. Any scheme must beat it by a wide margin. It is computed exactly, so fairness is automatic.
The strongest existing competitor is one-shot PDA delivery on the identical placement. This means Partition PDAs at the configurations Cheng et al. prove tight, $(K=4,F=6)$ and $(K=6,F=8)$, and strong-edge-coloring PDAs from Placement Delivery Arrays from Combinations of Strong Edge Colorings. The latter report load 16 at $K=784$ with $F=5{,}215$, against a baseline load of 39.5 and $F\approx 2.6\times10^6$. It is the strongest competitor because it is provably optimal within one-shot delivery at those small sizes. The file gives no numeric load value for the $(4,6)$ and $(6,8)$ cases ("no reported result found on Lacuna" for the load itself), so we recompute one-shot optima exactly by exhaustive search. Fairness is enforced by holding placement, $F$, demand vector (worst case over all demands), and field size identical across regimes. The only variable is the delivery code. Beating it means a strictly smaller integer number of broadcasts on the same placement. At larger sizes it means a lower load at equal or smaller $F$ than the published PDA point; for $K=784$, that is below 16 at $F\le 5{,}215$.
For finite-length decentralized delivery the competitor is MHCD. It reports load 2.20, against AHgLC's 2.27 and earlier schemes' 3.49, at $N=4$, $K=8$, $M=1$, $F=400$ bits. We run aligned delivery on the same random placements, using the same number of Monte Carlo draws, and report both load and decoding time. Beating it means a lower average load, or an equal load at polynomial rather than $O(2^{2K})$ cost.
For the information-theoretic ceiling we use the non-unique scheme of Wan et al. on their 6-user instance, with symmetric rate 1/3. This tests whether linear alignment loses anything relative to random-codebook non-unique decoding.
The key ablation is random linear delivery with the same number of broadcasts and generic coefficients but no alignment design, decoded by Gaussian elimination. It isolates whether the gain comes from designed alignment or simply from allowing multi-shot linear mixing.
Why not just…?
Why not just build better PDAs? Combinatorial constructions have delivered large gains: Michel and Wang cut $F$ from 101,147 to 3,003 at $K=182$, and Tang and Ramamoorthy cut it from $4.8\times10^{14}$ to $1.07\times10^6$. Better tables remain the most likely way to move the frontier. Within one-shot delivery, though, Cheng et al. already prove the Partition PDA optimal at $q=2$, so at those parameters no better table can exist. Only a change in the decoding rule can help there. The exact computation at $(4,6)$ and $(6,8)$ settles this directly. If aligned delivery ties one-shot there and on the edge-coloring families, the skeptic is right, and we report the tie as an optimality theorem for linear delivery.
Why not just use random linear network coding? This is the real threat, because random combinations already avoid the one-shot rule. The ablation above answers it. If generic random combinations with $T$ broadcasts already satisfy the rank condition for all users wherever designed alignment does, then there is no structural contribution. The result would be "multi-shot suffices," and that is still a finding about the Cheng et al. bound. We expect designed alignment to need fewer broadcasts, because random codes over small fields fail the rank condition with non-negligible probability at small $F$. That expectation is exactly what the experiment checks.
Why not just accept slightly larger $F$ with classical-style delivery? We will plot load against $F$ for every scheme on shared axes. Aligned delivery matters only if it shifts the frontier, giving lower load at equal $F$. Matching some other scheme at a different $F$ does not count.
Why not worry that receiver complexity kills it? The concern raised for general non-unique decoding, as in On the Compound Broadcast Channel: Multiple Description Coding and Interference Decoding, involves list search over codebooks. Linear alignment needs one elimination on a matrix whose dimensions are the number of broadcasts by $F$. We will report measured decode time against MHCD's $O(2^{2K})$ cost.
Proposed Experiments
The first decisive check is exact computation at $(K=4,F=6)$ and $(K=6,F=8)$. It asks whether aligned linear delivery uses fewer broadcasts than the proven one-shot optimum. A yes refutes the generality of the fixed-$F$ bound; a no across all placements of that size motivates the extension theorem.
Second, we apply heuristic aligned delivery to strong-edge-coloring PDAs at $K=182$ and $K=784$, to test whether load 16 at $F=5{,}215$ can be lowered.
Third, we run the Wan et al. 6-user instance to check whether linear alignment reaches 1/3. Falling short would quantify what finite-field linearity costs relative to random-coding non-unique decoding.
Fourth, we run decentralized placement at $F=400$ bits against MHCD's 2.20. Here we also test whether alignment removes the zero-padding cost, since pieces of unequal length can be aligned rather than padded.
Finally, we take small Ruzsa-Szemerédi-style constructions with $F=K$ and track how the ratio of aligned to one-shot load grows with $K$. This is the regime where any asymptotic gain would show itself first.
References
- Coded Caching for MISO Systems with Linear Subpacketization
- A novel index coding scheme and its application to coded caching
- On the capacity region for index coding
- Placement Delivery Arrays From Combinations of Strong Edge Colorings
- Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes
- Coded Caching with Linear Subpacketization is Possible using Ruzsa-Szeméredi Graphs.
- Novel delivery schemes for decentralized coded caching in the finite file size regime
- On the Compound Broadcast Channel: Multiple Description Coding and Interference Decoding