Fundamental Limits of Uncoded Cache Placement

28 concepts23 papers3 proposals

In modern communication networks, network congestion peaks when many users simultaneously request different content. Coded caching is a powerful technique designed to mitigate these traffic spikes. It operates in two distinct phases:

  1. Placement Phase: Content is proactively pushed to users' local memories (caches) during off-peak hours.
  2. Delivery Phase: During peak hours, users request specific files, and the server broadcasts mathematically combined (coded) transmissions that simultaneously satisfy multiple distinct requests.

To understand why this works, imagine two users, User 1 and User 2, and a library of two files, $A$ and $B$. During the placement phase, User 1 caches the first half of both files ($A_1, B_1$), and User 2 caches the second half ($A_2, B_2$). If User 1 later requests file $B$ and User 2 requests file $A$, the server does not need to send $B_2$ and $A_1$ separately. Instead, it broadcasts a single coded message: $A_1 \oplus B_2$. User 1 uses its cached copy of $A_1$ to decode $B_2$, while User 2 uses its cached copy of $B_2$ to decode $A_1$. A single transmission satisfies both users, creating a multicast gain.

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  --> Combines with B_1 to get File B
User 2 decodes: (A_1 ⊕ B_2) ⊕ B_2 = A_1  --> Combines with A_2 to get File A

The efficiency of this system hinges entirely on how data is arranged during the placement phase. While it is theoretically possible to store complex mathematical combinations of files in the caches (coded placement), a vast body of literature focuses on the uncoded cache placement constraint. Under this constraint, caches are strictly restricted to storing raw, unmodified fragments of files.

The Practicality of the Uncoded Constraint

Restricting cache placement to raw file segments simplifies hardware implementation and data management. If a file in the central library is updated or deleted, an uncoded cache simply replaces or removes those specific bits. In contrast, coded placement requires re-encoding combinations across multiple files, creating massive computational and operational overhead.

However, this simplicity introduces a fundamental theoretical question: What is the minimum transmission rate we can achieve during the delivery phase if we are forced to use uncoded placement?

By enforcing uncoded placement, we fix the "side information" available to users as explicit pieces of files. The problem of minimizing the delivery phase network load then reduces to finding the optimal way to exploit this fixed side information.

Mapping Caching to Index Coding

To find the exact limits of uncoded cache placement, researchers map the delivery phase directly to the Index Coding problem. Index coding investigates the minimum number of transmissions required for a server to satisfy a set of receivers, where each receiver wants a specific message and already holds a subset of other messages as side information.

As shown by Kai Wan et al. in An Index Coding Approach to Caching with Uncoded Cache Placement, any uncoded cache placement scheme partitions the files into subfiles that map perfectly to an index coding problem during the delivery phase. By leveraging non-unique decoding techniques from index coding, Kai Wan et al. demonstrated in A Novel Index Coding Scheme and its Application to Coded Caching that one can derive tight converse bounds that define the absolute minimum transmission load for worst-case demand patterns.

Characterizing the Exact Rate-Memory Tradeoff

The foundational benchmark for coded caching is the Maddah-Ali and Niesen (MAN) scheme. In On the Optimality of Uncoded Cache Placement, Kai Wan et al. proved that the MAN scheme is exactly optimal under the uncoded placement constraint, provided that the number of unique files in the library ($N$) is at least as large as the number of users ($K$). In this regime, the raw fragments stored by the MAN scheme provide the perfect distribution of side information to maximize multicast gains.

However, when there are more users than files ($K > N$), users will inevitably request duplicate files. The standard MAN scheme does not fully exploit these overlapping requests, leaving a gap between the achievable transmission rate and the theoretical lower bound.

When Users > Files (e.g., User 1 and User 2 both request File A):
Standard MAN: May send separate coded pieces for each user's missing parts.
Leader-Based Strategy: Designates a "leader" for File A, eliminating redundant transmissions of the same subfiles across the network.

This gap was completely closed by Qian Yu et al. in The Exact Rate-Memory Tradeoff for Caching With Uncoded Prefetching. The authors introduced a leader-based delivery strategy. When multiple users request the same content, the scheme nominates a "leader" for that file and coordinates the multicast transmissions to eliminate redundant subfile delivery. This work established the mathematically exact upper and lower bounds for the rate-memory tradeoff under uncoded placement for any combination of users and files.

Extending to Real-World Topologies

While the exact tradeoff is well-understood for a single shared broadcast link, real-world networks introduce physical layer constraints, user preferences, and complex topologies. Researchers use the uncoded placement baseline to evaluate these complex environments:

  • Wireless Latency and Interference: In decentralized wireless networks, transmission bottlenecks occur due to interference. Avik Sengupta et al. in Cache Aided Wireless Networks: Tradeoffs between Storage and Latency characterized the optimal storage-latency tradeoff using a metric called Normalized Delivery Time (NDT), demonstrating how uncoded edge caching shifts the operational boundaries of interference management.
  • Correlated Content: Files in a network are rarely independent; they often share common information (e.g., different video resolutions or localized streams). In Centralized Caching and Delivery of Correlated Contents over Gaussian Broadcast Channels, Qianqian Yang et al. showed that combining uncoded cache placement with correlation-aware delivery strategies yields massive energy savings over Gaussian broadcast channels by avoiding the transmission of shared background data.
  • Asymmetric Demands and Profiles: Users exhibit different content preferences. Ciyuan Zhang et al. in Coded Caching With Heterogeneous User Profiles relaxed the assumption of uniform file popularity, optimizing uncoded prefetching to match heterogeneous user profiles while maintaining structured multicast opportunities during delivery.

By isolating the placement phase from complex cross-file encoding, the uncoded placement constraint provides a mathematically tractable yet highly practical framework. It allows researchers to derive exact information-theoretic bounds, proving that simple storage strategies can achieve near-optimal network performance when paired with sophisticated, coded delivery mechanisms.

Key Foundational Work

On the Optimality of Uncoded Cache Placement (2015) — contributed 2 concept elements to this direction.
Cache Aided Wireless Networks: Tradeoffs between Storage and Latency (2015) — contributed 1 concept elements to this direction.
FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers. (2013) — contributed 1 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_uncoded_placement_constraint_9f2234f4,
  title = {uncoded placement constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uncoded-placement-constraint/rdr_9f2234f4c93346a2aec4b191b02d539f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_uncoded_placement_constraint_9f2234f4_v1,
  title = {uncoded placement constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uncoded-placement-constraint/rdr_9f2234f4c93346a2aec4b191b02d539f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake