Exact Optimality Under Uncoded Placement (YMA 2018)

Four Years of Progress

The question left open by Maddah-Ali and Niesen in 2014 — is the MAN scheme optimal? — was partially answered by a sequence of works between 2014 and 2018. Chen, Fan, and Letaief improved the bound for small $M$ (2016); Ghasemi, Ramamoorthy (2017) and Wang, Lin, Sun (2018) attacked specific regimes. But the definitive answer came from Yu, Maddah-Ali, and Avestimehr in 2018: under the restriction of uncoded placement, the MAN scheme is exactly optimal for worst-case demands.

The proof is a beautiful demand-averaging argument that would not have been possible without the intervening four years of developing the right conceptual tools. We state the result here; the proof idea follows.

Definition:
Uncoded Placement

A caching scheme has uncoded placement if every bit of every file is either stored verbatim in some caches or not stored at all — no bit is modified or XORed with other bits during placement. Formally: each cache $\mathcal{Z}_{k}$ is a subset of $\{W_n(b) : n \in [N], b \in [F]\}$ , where $W_n(b)$ is the $b$ -th bit of $W_n$ .

Uncoded placement is the most natural and operationally simplest placement regime. The MAN scheme's placement is uncoded — each subfile $W_{n,\mathcal{S}}$ is a contiguous block of bits from $W_n$ . Under uncoded placement, the only coding happens in the delivery phase (via XOR).

Theorem: YMA '18 Exact Converse

Under uncoded placement, for all $K, N \geq 1$ , $M \in [0, N]$ , and worst-case demands, the optimal worst-case delivery rate is exactly $R_{\text{unc}}^*(M) \;=\; \mathrm{conv}\!\left\{\left(\frac{iN}{K},\, \frac{K-i}{i+1}\right) : i = 0, 1, \ldots, K\right\},$ the lower convex envelope of the MAN operating points. That is, the MAN scheme (with memory sharing for non-integer $t$ ) is exactly optimal under uncoded placement.

The proof has two sides:

Achievability: MAN attains this rate (Chapter 2).
Converse: For any uncoded placement, an information-theoretic averaging argument over a carefully chosen ensemble of demand vectors shows no scheme can achieve less. The key insight is to average over demand vectors of the same type (histogram of distinct file requests); symmetry then forces the rate to be at least the MAN rate.

Proof

Setup — demand types

A demand type is the histogram $(n_1, n_2, \ldots, n_N)$ where $n_i$ is the number of users requesting file $i$ . Equivalent demand vectors (same histogram) are related by permutations of $[K]$ .

Key averaging identity

For any uncoded placement and any demand type, the average rate over all permutations of $[K]$ equals the rate of the MAN scheme applied to that type. This uses the symmetry of uncoded placement under user permutation.

Rate lower bound

The worst-case rate is at least the MAN rate, because we cannot average below the max. Concretely, for any demand vector of the worst-case type (all distinct demands): the average rate over permutations equals the MAN rate, so some permutation yields rate at least the MAN rate.

Uncoded-placement achievability

MAN's placement is uncoded, so the MAN rate is achievable within the uncoded regime. Combined with the matching lower bound, the MAN rate equals the optimal rate under uncoded placement. $\blacksquare$

Key Takeaway

Under uncoded placement, coded caching is solved. The MAN scheme is provably optimal: no uncoded-placement scheme can achieve a lower worst-case rate. This is a complete information-theoretic characterization of the memory-load tradeoff in the uncoded regime.

Historical Note: The Path to the 2018 Converse

2014–2018

Between 2014 and 2018, many researchers attempted to close the MN gap. The breakthrough came from realizing that the converse bound could be tightened by exploiting a demand-averaging argument within the uncoded regime. Yu, Maddah-Ali, and Avestimehr (UC Berkeley, 2018) showed that any uncoded placement must, in expectation over a symmetric demand ensemble, yield a rate at least that of MAN. Combined with achievability, this closed the gap exactly.

The general problem (allowing coded placement) remains open. Known examples of coded placements that marginally beat MAN exist (Gómez- Vilardebó, Tian '18 for small $K$ ), but no systematic improvement has been found. Tian and Chen showed (2018) that under an additional symmetry restriction, coded placement cannot help either. Whether there is a coded-placement scheme with strictly better rate than MAN for general $(K, N, M)$ is perhaps the open question in coded caching.

⚠️Engineering Note

The Operational Meaning of 'Uncoded Placement'

Uncoded placement is not just an analytical convenience — it matches what real CDNs do. Edge caches in deployed systems store unmodified file fragments (typically HTTP byte ranges), not XOR combinations. Coded placement would require:

Encoding bits from multiple files before storage — a significant architectural change.
Decoding on reception, which introduces latency and complexity.
Careful key management if the coding is cryptographic.

For these reasons, the practical impact of the YMA '18 result is bigger than the theoretical impact. It says: the MAN scheme, which fits within today's CDN architecture, is already optimal under the most realistic placement restriction. Chasing a coded-placement improvement might yield a theoretical paper but is unlikely to change deployed systems.

Practical Constraints

•
Uncoded placement matches HTTP byte-range caching used by commercial CDNs
•
Coded placement would require encoder/decoder at every edge node
•
YMA '18 result closes the theory-practice gap for deployed systems

🎓CommIT Contribution(2018)

Exact Optimality of MAN — Context of the CommIT Program

Q. Yu, M. A. Maddah-Ali, A. S. Avestimehr, G. Caire — IEEE Transactions on Information Theory

The YMA '18 paper is jointly celebrated by the coded-caching community and is the touchstone for all subsequent converse work, including the CommIT program's wireless, D2D, and privacy extensions. The Caire group's papers in later chapters (Lampiris-Caire on multi-antenna CC, Wan-Caire on demand privacy) all invoke this result as the "shared- link tight bound" against which their wireless-extension gains are measured.

Operational reading. The result says: pick any uncoded placement, run any delivery, and you cannot beat MAN for worst-case demands. Subsequent work explores what happens when we relax one or more of these restrictions — non-uniform demand (Ch 13), decentralized placement (Ch 10), wireless channels (Ch 5), privacy constraints (Ch 12). In each case, YMA '18 is the baseline the extensions measure gains against.

coded-cachingconverseoptimalityView Paper →

Quick Check

The YMA '18 result says MAN is optimal:

For all placements (coded or uncoded).

For uncoded placement and worst-case demands.

For any placement but only under Zipf demands.

For uncoded placement, only when $K \leq N$ .

Correction: