Superposing Coded-Caching Slots: When Low Subpacketization Creates Side Information for Interference Cancellation

Coded caching lets one broadcast serve several users at once. Each user stores pieces of popular files ahead of time, and the server later sends XOR combinations of pieces that every recipient can unscramble using what it already holds. The catch is subpacketization: to get the full benefit, each file must be cut into a number of pieces that grows combinatorially with the number of users. Practical designs therefore cut files into far fewer pieces and accept a higher delivery load. A separate line of work, cache-enabled interference cancellation, uses stored content at the physical layer. If a receiver already holds the data behind an interfering signal, it can rebuild that signal and subtract it from what it received. It then decodes its own message as if the interferer were absent. This trick lets power-domain non-orthogonal multiple access (NOMA), where several messages are sent at once at different power levels, escape its usual strict decoding orders.

This note proposes to connect the two. Low-subpacketization designs make users' caches overlap more than the classical scheme does, and that overlap is exactly the side information a receiver needs to cancel a superposed coded multicast. So the cost of reducing subpacketization may be partly paid back at the physical layer. Two delivery slots can be transmitted on top of each other at different powers. Users in one slot strip out the other slot's signal from their caches, and users in the other slot remove it by ordinary successive decoding. The question is whether this recovers the load lost to small subpacketization under realistic fading and imperfect channel knowledge.

Core Claim

A coded-caching scheme can be described by a placement delivery array (PDA). This is a table whose rows are file pieces and whose columns are users. A star marks a piece the user caches. An integer label marks which delivery slot carries the piece that user needs (Placement Delivery Arrays from Combinations of Strong Edge Colorings, Coded Caching for MISO Systems with Linear Subpacketization).

Call slot $b$ cache-cancellable for a set of users $A$ if every user in $A$ has a star in every row that slot $b$ draws from. Such users can rebuild the XOR sent in slot $b$ and subtract it. Superposing $b$ on top of a slot $a$ intended for $A$ then costs $A$'s users only the residual left by imperfect cancellation.

The first observation is a simple structural fact. The classical Maddah-Ali–Niesen placement has no cache-cancellable pairs at all. In that scheme, a slot for user group $G$ carries pieces indexed by $G\setminus\{k\}$. A user outside $G$ can never belong to any of those index sets, so it never holds the required pieces. Low-subpacketization constructions behave differently. Partition PDAs, designs built from linear block codes, and Ruzsa–Szemerédi graph placements (Coded Caching Schemes With Reduced Subpacketization From Linear Block Codes, Coded caching with linear subpacketization is possible using Ruzsa-Szeméredi graphs) reach small subpacketization $F$ by making caches overlap more. That overlap can create cancellable pairs.

The hypothesis is that, at finite signal-to-noise ratio (SNR) with heterogeneous fading, superposing such pairs closes much of the delivery-time gap between low-$F$ designs and the classical scheme. In some regimes it may reverse the gap. The reason is that superposition also frees each group's rate from the weakest user in the other group, a constraint that XOR merging cannot avoid.

For a superposed pair, let $A$ be the group that cancels slot $b$ from cache and $B$ the group that decodes slot $a$ by successive interference cancellation. Let $h_u$ be user $u$'s channel gain, $p_a$ and $p_b$ the layer powers with $p_a+p_b=P$, and $\epsilon$ the fraction of a cancelled signal left behind by channel estimation error. The slot must deliver piece size $S$ to both groups within duration $T$:

$$ T=\max\!\left(\frac{S}{\min_{u\in A}\log\!\left(1+\frac{h_u p_a}{1+\epsilon h_u p_b}\right)},\ \frac{S}{\min_{u\in B}\log(1+h_u p_b)}\right), $$

subject to $B$'s users being able to decode layer $a$ first, treating layer $b$ as noise. The baseline is time-sharing, which spends $S/\min_{u\in A}\log(1+h_uP)+S/\min_{u\in B}\log(1+h_uP)$ on the same two slots. Concavity of the logarithm is what lets superposition beat time-sharing at finite SNR. The $\epsilon$ term is what can erase that advantage.

Relation to Prior Work

Three groups of papers frame the proposal.

The cache-aided NOMA papers supply the physical-layer mechanism. Cache-Aided Non-Orthogonal Multiple Access: The Two-User Case shows that cached side information lets even the weak user cancel the strong user's signal. It derives closed-form power and rate splits and reports at least 30% shorter delivery time and 18.6 versus 12.0 bps/Hz throughput. Power Allocation in Cache-Aided NOMA Systems: Optimization and Deep Reinforcement Learning Approaches extends this to many users by pairing them on orthogonal subchannels or by a learned policy. All of these use uncoded prefix-style caching. The surveys (A Survey on Applications of Cache-Aided NOMA, A Survey on Cache-Aided NOMA for 6G Networks) name two gaps: the lack of combinatorial file-splitting frameworks, and the assumption of perfect cancellation. This proposal reuses the closed-form two-layer power split. It applies the split to pairs of coded multicast slots rather than to pairs of individual users, and it models imperfect cancellation explicitly through $\epsilon$.

The subpacketization papers supply the placements and constrain the expectations. Coded Caching for MISO Systems with Linear Subpacketization proves a lower bound on load at fixed $F$ and shows Partition PDAs meet it, assuming an error-free shared link or underloaded beamforming. Since that bound already rules out load gains from rearranging slots on an ideal shared link, any gain here must come from finite-SNR power-domain effects. The proposal does not claim to break the bound. The claim is that delivery time on a fading channel is a different objective, and on that objective cache overlap is an asset rather than only a cost.

The closest existing combination is Multi-Antenna Coded Content Delivery with Caching: A Low-Complexity Solution. That paper caps how many coded messages each user must decode and uses beamforming to null interference. It reports about 8.5 dB transmit-power savings for 5 users and 6 antennas. It requires at least as many antennas as interfering streams and uses no receiver-side cache cancellation. This proposal targets single-antenna and overloaded settings where that nulling is impossible. It also keeps a decode-count metric comparable to theirs. Cache-Aided Combination Networks with Interference also uses caches against interference, through interference alignment at edge nodes. It works with continuous MDS splits and high-SNR degrees of freedom, so it never faces finite $F$.

Research Program

The work has four parts.

The first is combinatorial. For each PDA family in the file, compute the directed "cancellability graph": nodes are delivery slots, and an edge $b\to a$ exists when every user in slot $a$ caches all constituents of slot $b$. The analysis then counts these edges as a function of $F$, the number of users $K$, and the cache fraction. For the classical scheme the count is provably zero. For Partition PDAs and block-code designs, the aim is closed-form or exact computational counts. The same analysis includes the trivial low-$F$ scheme in which clusters of users hold identical caches.

The second part is the delivery algorithm. Placement is fixed, but which group is stronger changes with each fading realization. Given a realization, each candidate pair is oriented, and its time saving over time-sharing is computed from the closed-form two-layer split. The pairing is then chosen by maximum-weight matching on the cancellability graph, which runs in polynomial time. Three-layer superposition is an extension, kept only if pairs prove insufficient.

The third part is robustness analysis. The analysis derives the largest $\epsilon$ at which a pair still beats time-sharing. It also examines whether the low power typically assigned to the cancelled layer keeps the residual small. If so, that would explain why cache-based cancellation is more robust than decoding-based cancellation.

The fourth part is design. If existing low-$F$ families turn out to have few cancellable edges, the project will build a search, for example over strong-edge-coloring constructions, for PDAs that maximize cancellable edges at a given $F$ while staying within a small factor of the fixed-$F$ load bound of Cheng et al.

Baselines

The naive reference point is the classical Maddah-Ali–Niesen XOR delivery, time-shared slot by slot. Each slot is sent at full power at the rate of its weakest user. It is evaluated wherever its subpacketization is feasible for the file size, and also at the same low-$F$ PDAs with plain time-sharing. Beating this reference means lower average normalized delivery time, the total delivery time divided by file size, at equal transmit power.

The strongest existing physical-layer competitor is the divide-and-conquer cache-aided NOMA of Power Allocation in Cache-Aided NOMA Systems: Optimization and Deep Reinforcement Learning Approaches, combined with the closed-form two-user splits of Cache-Aided Non-Orthogonal Multiple Access: The Two-User Case. It is strong because it already captures power-domain and cache-cancellation gains with uncoded caching and no subpacketization burden. Its reported reference number is a throughput of 18.6 bps/Hz versus 12.0 bps/Hz for baselines, with at least 30% shorter delivery time, in the two-user case. No reported result was found on Lacuna for the deep reinforcement learning variant's numbers. This baseline will be run with the same cache memory, the same Zipf request statistics, the same 3GPP Urban Macro non-line-of-sight path loss with Rayleigh fading, and an equal power-split search grid. Beating it means lower delivery time at $K\ge 6$, where coded multicast gain should begin to matter.

The best low-subpacketization scheme is the Partition PDA of Coded Caching for MISO Systems with Linear Subpacketization. It runs at the paper's tightness instances ($K=4, F=6$ and $K=6, F=8$) and at larger sizes, with time-shared rate adaptation. For the overloaded multi-antenna case, the message-limited beamforming of Zhao et al. is the reference, with its reported 8.5 dB gain treated as context only, because it was obtained in the underloaded regime.

The key ablation keeps everything in the proposal but forbids cache cancellation. Pairs are superposed, and users can remove the other layer only by successive decoding, never from cache. This isolates whether the caches, rather than ordinary NOMA superposition, produce the gain.

Why not just…?

Why not just pair users two at a time and run cache-aided NOMA on orthogonal subchannels? This is the main practical threat, because it is simple and already reported to work. Its cost is that it forgoes coded multicast entirely: each transmission serves at most two users. Its own authors note that it gives up spectral efficiency relative to full-bandwidth sharing (Power Allocation in Cache-Aided NOMA Systems: Optimization and Deep Reinforcement Learning Approaches). The experiments sweep $K$ and the cache fraction to find where, if anywhere, superposed coded slots overtake it. If they never do at practical sizes, that is a publishable negative result about coded caching on fading channels.

Why not just superpose multicast slots with ordinary successive decoding and skip cache cancellation? This is exactly the key ablation. One argument suggests it could capture most of the gain: when the strong group's layer gets little power, the weak group loses little by treating it as noise. Cache cancellation should matter most when the two groups have similar channel gains. In that regime, decoding-only superposition gives little benefit and XOR merging is unavailable because cancellation is one-sided. The proposal will report the gain split by channel-gain ratio. If the cache-free version matches across the board, the core claim fails.

Why not just merge the cancellable slots into one larger XOR? Merging requires cancellability in both directions. Even then, a single XOR is limited by the weakest user across both groups. Optimal fixed-$F$ PDAs are presumably already merged as far as possible. The only remaining opportunities are one-directional, and those cannot be expressed as XORs. The simulation includes greedy merging as a baseline to confirm this.

Why not just use beamforming? With enough antennas, zero-forcing removes the need for any of this (Multi-Antenna Coded Content Delivery with Caching: A Low-Complexity Solution). The proposal is therefore aimed only at single-antenna and overloaded regimes, and it reports results by antenna count to show where beamforming alone stops sufficing.

Proposed Experiments

No empirical radio-frequency datasets exist in the file, so all evaluation is Monte Carlo simulation. The setup uses 3GPP Urban Macro non-line-of-sight path loss, Rayleigh block fading, users placed by Poisson processes as in NOMA Assisted Wireless Caching: Strategies and Performance Analysis, and Zipf requests. File sizes are finite and fixed, so schemes with infeasibly large $F$ are penalized honestly rather than idealized. The metrics are normalized delivery time, the number of decodes per user (comparable to Zhao et al.'s per-user message cap), and robustness to the cancellation-residual parameter $\epsilon$.

There are three decisive checks. The first is combinatorial: the cancellability counts for the low-$F$ families must be nonzero and must grow as $F$ shrinks. If they are near zero, the program shifts to the design part. The second is the main comparison: at matched $F$, cancellation-aided superposition must beat both the time-shared PDA and the cache-free superposition ablation, and there must be some $(K, F, \text{SNR})$ point where low-$F$ delivery with superposition beats classical XOR delivery that is feasible at that file size. The third is robustness: the gain must survive $\epsilon$ values consistent with realistic channel estimation error, and the break-even $\epsilon$ will be reported directly.