Ferkans — Interactive Telecom Tutor

Why We Need a Converse

The MAN scheme of Chapter 2 achieves rate $R_{\text{MAN}}(M) = K(1-M/N)/(1+KM/N)$ . But is this the best anyone can do? To answer that, we need a converse bound — a rate below which no scheme can go, regardless of how cleverly it is designed. This is the classical information-theoretic project: upper bound an operational quantity (rate) via information-theoretic quantities (entropies), then use entropy bounds to produce a scheme- independent lower bound on rate.

The cut-set converse of Maddah-Ali and Niesen is the first such bound for coded caching. It is not tight in general — MAN does strictly better than this bound predicts — but it establishes the structure of the answer and sets up the later exact-optimality result of YMA '18 under uncoded placement.

Theorem: Cut-Set Converse Bound

For the shared-link coded caching network with $K$ users, $N$ files, and per-user cache size $M$ , any scheme achieving worst-case rate $R$ satisfies $R^*(M) \;\geq\; \max_{s \in \{1, \ldots, \min(K, N)\}} \left( s - \frac{s M}{\lfloor N/s \rfloor} \right).$

The bound is a cut-set argument: pick $s$ users, consider the channel from the caches + delivery messages (over $\lfloor N/s \rfloor$ rounds) to the demanded files. The caches hold $sM F$ bits at most; the delivery messages hold $\lfloor N/s \rfloor R F$ bits. Together they must encode $\lfloor N/s \rfloor \cdot s \cdot F$ bits of file data (every file requested at least once). Rearranging gives the bound.

Proof

Fix a cut and a demand ensemble

Fix any $s \in \{1, \ldots, \min(K, N)\}$ . Consider $s$ users, say users $\{1, \ldots, s\}$ . We construct $\ell^* = \lfloor N/s \rfloor$ demand vectors $\mathbf{d}^{(1)}, \ldots, \mathbf{d}^{(\ell^*)}$ such that their union covers a set $\mathcal{F}$ of $s \ell^*$ distinct files: the $j$ -th user's demands are $d_j^{(\ell)} = (\ell - 1) s + j$ for $\ell = 1, \ldots, \ell^*$ .

Set up the information-theoretic constraint

For each $\ell$ , the $s$ users $\{1, \ldots, s\}$ must recover their demanded files from $\mathcal{Z}_{1}, \ldots, \mathcal{Z}_{s}$ plus the delivery message $X^{(\ell)}$ . By the data processing inequality and Fano's inequality, $\mathrm{H}\!\left(W_{d_1^{(\ell)}}, \ldots, W_{d_s^{(\ell)}} \,\Big|\, \mathcal{Z}_{1}, \ldots, \mathcal{Z}_{s}, X^{(\ell)}\right) = 0.$

Union over $\ell$

The $\ell^*$ delivery messages jointly determine all files in $\mathcal{F}$ given the $s$ caches. Concretely, $s \ell^* F \;=\; \mathrm{H}\!\left(\{W_n\}_{n \in \mathcal{F}}\right) \;\leq\; \mathrm{H}\!\left(\mathcal{Z}_{1}, \ldots, \mathcal{Z}_{s}, X^{(1)}, \ldots, X^{(\ell^*)}\right).$

Bound the joint entropy

By subadditivity and the cache capacity: $\mathrm{H}\!\left(\mathcal{Z}_{1}, \ldots, \mathcal{Z}_{s}\right) \;\leq\; s M F.$ Each delivery message has rate at most $R$ : $\mathrm{H}\!\left(X^{(1)}, \ldots, X^{(\ell^*)}\right) \;\leq\; \ell^* R F.$

Combine and solve

$s \ell^* F \;\leq\; s M F + \ell^* R F,KATEXPLACEHOLDER0ENDR \;\geq\; s - \frac{s M}{\ell^*} \;=\; s - \frac{sM}{\lfloor N/s \rfloor}.$ $Taking the max over$ s \in {1, \ldots, \min(K, N)} $gives the stated bound.$ \blacksquare$

Example: Cut-Set Bound for $K = 4$ , $N = 4$

Compute the cut-set lower bound for $K = 4$ , $N = 4$ , and all $M \in \{0, 1, 2, 3, 4\}$ .

Solution

Enumerate $s$

Candidates: $s \in \{1, 2, 3, 4\}$ .

Compute per-$s$ bounds

$s = 1$ : $\lfloor N/s \rfloor = 4$ . Bound: $R \geq 1 - M/4$ .
$s = 2$ : $\lfloor N/s \rfloor = 2$ . Bound: $R \geq 2 - M$ .
$s = 3$ : $\lfloor N/s \rfloor = 1$ . Bound: $R \geq 3 - 3M$ .
$s = 4$ : $\lfloor N/s \rfloor = 1$ . Bound: $R \geq 4 - 4M$ .

Take the max over $s$

At $M = 0$ : bounds are $1, 2, 3, 4$ . Max: $4$ (with $s = 4$ ). At $M = 1$ : bounds are $0.75, 1, 0, 0$ . Max: $1$ ( $s = 2$ ). At $M = 2$ : bounds are $0.5, 0, -3, -4$ . Max: $0.5$ ( $s = 1$ ). At $M = 3$ : $0.25, -1, \ldots$ Max: $0.25$ . At $M = 4$ : $0$ .

Compare with MAN

MAN at $K = N = 4$ : $t = KM/N = M$ . $R_{\text{MAN}}(t) = (K-t)/(t+1)$ . $M = 1$ : $R = 3/2 = 1.5$ . Cut-set: $1$ . Gap factor $1.5$ . $M = 2$ : $R = 2/3 \approx 0.667$ . Cut-set: $0.5$ . Gap factor $1.33$ . MAN exceeds the cut-set bound by a factor that depends on $M$ . The gap is real but bounded.

MAN Achievability vs. Cut-Set Converse

The memory-load plot with both the MAN upper bound (achievable) and the cut-set lower bound (converse). The green dotted curve is the tight YMA '18 converse under uncoded placement, which we prove in §3.3. Notice that at $K = N$ (symmetric), all three curves coincide; the gap is more visible at $K > N$ or $K < N$ .

Parameters

Number of users K10

Number of files N20

Key Takeaway

The cut-set bound sees the problem as a compressed-storage game. Each cut yields one constraint: the $s$ caches plus $\lfloor N/s \rfloor$ delivery messages must encode $s \lfloor N/s \rfloor$ files' worth of data. Maximizing over $s$ picks the tightest constraint. This is a classical cut-set argument — the same pattern that yields the max-flow min-cut bound in networks and the cut-set lower bound on broadcast channel capacity.

The Cut-Set Bound Is Loose — And That's Interesting

An honest assessment of the Maddah-Ali–Niesen 2014 result is: the achievable scheme and the converse bound both exist, but they do not coincide. The multiplicative gap between MAN achievability and cut-set converse is at most $\approx 12$ in general (MN 2014 showed this), and often as low as 2–3 in practice. Closing the gap was the main research question of coded caching from 2014 to 2018.

Yu, Maddah-Ali, and Avestimehr resolved it in 2018 under the restriction of uncoded placement: they proved the MAN scheme achieves rate exactly equal to the best converse under uncoded placement, closing the gap to 1. The case of general (possibly coded) placement remains open. This is our topic for §3.3 and §3.5.

The Cut-Set Converse Bound