Scaling Coded Caching via Reduced Subpacketization

31 concepts17 papers4 proposals

Coded caching is a powerful technique designed to alleviate peak-hour internet traffic by trading cheap storage for expensive bandwidth. By proactively pushing content to users' local caches during off-peak hours, a central server can later broadcast a single, coded transmission that simultaneously satisfies multiple distinct user requests.

However, a major barrier prevents this elegant theory from working in the real world: subpacketization overhead. To achieve optimal network efficiency, files must be fragmented into smaller pieces (sub-packets) so that they can be mixed and matched via network coding operations (like XORs). In baseline centralized schemes, the number of required sub-packets scales exponentially with the number of users in the network. If a network has just a few dozen users, a single video file would need to be split into more pieces than there are atoms in the universe, making the scheme physically impossible to implement on finite file sizes.

To make coded caching scalable, researchers have developed structured mathematical frameworks that drastically reduce file fragmentation while preserving the benefits of coordinated content delivery.


The Intuition of Coded Caching and Its Combinatorial Explosion

To understand why files must be split, imagine a simple network with a single server and two users, User 1 and User 2. The server holds two files, $A$ and $B$. During the off-peak placement phase, the server populates the users' caches. If we split file $A$ into two halves ($A_1, A_2$) and file $B$ into two halves ($B_1, B_2$), we can store $A_1$ and $B_1$ in User 1's cache, and $A_2$ and $B_2$ in User 2's cache.

During the peak delivery phase, suppose User 1 requests file $B$ and User 2 requests file $A$.

  • User 1 already has $B_1$ and needs $B_2$.
  • User 2 already has $A_2$ and needs $A_1$.

Instead of sending $B_2$ and $A_1$ separately, the server broadcasts a single coded packet: $A_1 \oplus B_2$. User 1 uses its cached $A_1$ to decode $B_2$, while User 2 uses its cached $B_2$ to decode $A_1$. A single transmission satisfies both users simultaneously.

Placement Phase (Off-Peak):
User 1 Cache: [ A_1, B_1 ]
User 2 Cache: [ A_2, B_2 ]

Delivery Phase (Peak Requests: User 1 wants B, User 2 wants A):
Server Broadcasts: A_1 ⊕ B_2
User 1 Decodes: (A_1 ⊕ B_2) ⊕ A_1 = B_2  --> Gains full file B
User 2 Decodes: (A_1 ⊕ B_2) ⊕ B_2 = A_1  --> Gains full file A

This "multicast gain" scales with the number of users who share overlapping cache contents. However, as Gunduz et al. and Paschos et al. point out, the baseline scheme achieves this by considering every possible subset of users. If you have $K$ users, the file must be partitioned into a number of sub-packets that scales as $\binom{K}{t}$, where $t$ relates to the cache size.

As Ramamoorthy observes, this exponential growth creates an immediate hardware bottleneck. If a file is finite, splitting it into an exponential number of pieces means each sub-packet eventually becomes smaller than a single bit. As a result, theoretical models that assume infinite file sizes collapse when faced with real-world storage and processing constraints, a challenge highlighted by Deng et al..


Breaking the Exponential Barrier via Structured Placement

To bypass this combinatorial explosion, researchers must move away from considering all possible user subsets. Instead, they restrict the caching patterns so that sub-packets are shared only among specific, highly regular groups of users. This reduces the subpacketization level at the cost of a slight, controlled increase in the delivery rate.

Graph-Theoretic Layouts: Ruzsa-Szeméredi Graphs

One of the earliest breakthroughs in achieving linear scaling came from graph theory. Shanmugam 0001 et al. demonstrated that the relationship between sub-packets, user caches, and delivery requirements can be mapped to a combinatorial structure known as a Ruzsa-Szeméredi graph.

In this framework, the dense, overlapping cache allocations of the baseline scheme are replaced by a sparse graph structure where edges represent sub-packets and matchings correspond to conflict-free multicast transmissions. By leveraging these graphs, the authors constructed the first coded caching scheme where the subpacketization level scales linearly ($O(K)$) with the number of users, proving that massive file fragmentation is not an inherent requirement for coded delivery.

Coding Theory Layouts: Linear Block Codes

Another strategy leverages the algebraic properties of error-correcting codes. Ramamoorthy introduced a method that uses resolvable designs derived from linear block codes to structure the cache placement phase.

Instead of arbitrarily assigning file pieces to users, the sub-packets are mapped to coordinates within a linear block code. Because linear codes possess natural geometric structures (like parallel lines or hyperplanes in finite fields), the sub-packets naturally group together into predictable configurations. This algebraic alignment allows the system to achieve sub-exponential scaling, making the management overhead manageable for physical hardware.

Matrix Frameworks: Placement Delivery Arrays (PDAs)

To systematically analyze the trade-off between file fragmentation and delivery speed, researchers formalize the problem using a matrix structure called a Placement Delivery Array (PDA). A PDA acts as a blueprint: its rows represent users, its columns represent sub-packets, and its entries dictate both what goes into the cache and how the server should construct its XORed broadcasts.

To optimize these blueprints, Michel et al. proposed constructing PDAs using strong edge colorings of graphs. By treating the caching matrix as a graph coloring problem, they provided a mathematical recipe to minimize the column count (subpacketization level) while maximizing the size of the color classes (multicast opportunities).


Scaling to Complex and Wireless Topologies

The subpacketization bottleneck becomes even more acute when moving from idealized, wired shared links to complex, multi-hop, or wireless network architectures.

Multi-Antenna and Physical-Layer Wireless Caching

In wireless systems, the central server is a base station equipped with multiple antennas. Here, the challenge is two-fold: the system must handle both file fragmentation and wireless interference. Zhao et al. note that exponential subpacketization makes the joint optimization of beamforming vectors and delivery schedules mathematically intractable for large networks. To solve this, the authors decoupled the problem by limiting the number of coded messages each user must decode per time slot, drastically reducing the computational burden on user devices.

Furthermore, Shariatpanahi et al. and Gunduz et al. demonstrated that a naive translation of network-layer caching to the wireless domain performs poorly at realistic signal-to-noise ratios (SNR). They proposed hybrid schemes that combine messages in the finite field (network layer) before applying complex-field precoding (physical layer), helping to maintain caching gains without requiring extreme file fragmentation.

Multiaccess and Hierarchical Networks

In more intricate topologies, such as combination networks where a central server reaches users through an intermediate layer of cache-aided relays, the fragmentation problem compounds. As Huang et al. and Wan et al. demonstrate, extending standard single-hop caching methods to multiaccess scenarios causes an immediate exponential explosion in subpacketization.

[Central Server]
       |
   [Relays]  <-- Cache-aided intermediate layer
    /    \
[User 1] [User 2] <-- Multiaccess users connected to multiple relays

To combat this, the authors designed specialized multiaccess coded caching schemes that treat relay data as structured "side information" for the users. By coordinating the placement phase across both layers simultaneously, they successfully reclaimed multicast opportunities while avoiding the compounding fragmentation overhead that plagues simpler, uncoordinated extensions.

Finally, when the number of users vastly exceeds the number of available files, Amiri et al. showed that users can be clustered into groups with identical requests. This group-based approach bounds the subpacketization level by treating each cluster as a single macro-user, ensuring that the system remains stable and computationally efficient even as the participant population grows into the millions.

Key Foundational Work

Coded Caching with Low Subpacketization Levels (2016) — contributed 4 concept elements to this direction.
Coded Caching for a Large Number Of Users (2016) — contributed 2 concept elements to this direction.
Fundamental Limits of Coded Caching: Improved Delivery Rate-Cache Capacity Tradeoff (2017) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_subpacketization_overhead_0ec1d800,
  title = {subpacketization overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subpacketization-overhead/rdr_0ec1d8006b834c4abd21520fa71b50a9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_subpacketization_overhead_0ec1d800_v1,
  title = {subpacketization overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subpacketization-overhead/rdr_0ec1d8006b834c4abd21520fa71b50a9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake