CS Paper Radar

Hotplug Coded Caching: Uncoded versus Row-Wise Coded Placements

Daniela Tuninetti

cs.IT eess.SP ·submitted 2026-11-02 12:43 UTC · v1

Abstract

In the hotplug coded caching model, $K$ users fill their caches of size $M$ as a function of $N$ files, but only an unknown subset of $A\leq K$ users is active in the delivery phase. In all regimes where the optimal hotplug tradeoff is known, it depends only on $A$, not on $K$; whether this holds in general is open. We show that: (i) Under uncoded placement, YMA delivery with MAN placement, where offline users are assigned the demands of active users, is optimal. Hence, offline users cause a strict load penalty at intermediate memory sizes, while the MAN placement is optimal for every number of active users; (ii) Under row-wise placement (RWP), where each cache is a function of the user's own row of each file, every classical scheme can be embedded in a Reed-Solomon code. The resulting hotplug scheme has the tradeoff of the classical model with $A$ users, for every $A\leq K$: there is no load penalty, but the placement depends on $K$. We then derive a converse for RWP, which shows that: (a) for $2\leq N\leq A$, the scheme of Gomez-Vilardebo (GV) is RWP optimal for $AM\leq N/(N-1)$, which settles the RWP tradeoff for $N=2$; (b) YMA is RWP optimal at $AM=N$; and (c) for $N=A=3$, GV is RWP optimal for $M\leq 1$. Hence, the Reed-Solomon embeddings of these schemes are optimal among embedded RWP schemes.

Comment
Submitted to ICC 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Hotplug Coded Caching: Embedding the YMA and Interference Elimination Schemes via Reed--Muller Codes

cs.IT eess.SP ·2026-11-04 ·Daniela Tuninetti
similarity 0.87
Abstract · companion paper to arXiv:2611.03045

In the hotplug coded caching model, $K$ users fill their caches of size $M$ as a function of $N$ files, but only an unknown subset of $A<K$ users is active in the delivery phase. We recently showed that (i) under uncoded placement, offline users cause a strict load penalty at intermediate memory sizes, so that coded placement is needed; and (ii) for $AM\leq N$, every classical scheme with row-wise placement, including the scheme of Gomez-Vilardebo (GV), can be embedded in a Reed-Solomon code, which removes the penalty. In this note, we show that every point of the scheme of Yu, Maddah-Ali and Avestimehr (YMA) for a classical system with $A$ users is achievable in the hotplug model for every $K\geq A$. Each user is associated with a hyperplane and each file with a homogeneous polynomial; each user caches the restriction of the polynomial to its hyperplane, and the subfiles seen by the active users are the values of the polynomial at the points where their hyperplanes meet. This is a projective Reed-Muller code, which reduces to the Reed-Solomon code when each subfile is cached by one user. We then show, by an existence argument, that every classical scheme whose cache is a linear compression of the Maddah-Ali-Niesen cache and whose correctness holds for generic coefficients can also be embedded over a sufficiently large field; this includes the interference elimination (IE) schemes of Tian and Chen. These embeddings complement the Reed-Solomon one, which allows any row-wise placement and any delivery. Together with past work, our results show that every point attained by a GV, YMA or IE scheme ($N\leq A$ for IE), and every corner point of the linear tradeoff for $A=N=3$, is achievable in the hotplug model with a load that does not depend on $K$. Whether the optimal hotplug tradeoff depends only on $A$ remains open, but these results support a positive answer.

0.04

The Exact Optimal Delivery Scheme for the Cyclically $L$-Separated Placement in Multi-Access Coded Caching

cs.IT ·2026-11-16 ·Kai Wan, Huimei Wei, Minquan Cheng, Giuseppe Caire
similarity 0.69
Abstract

This paper investigates the $(K, L, M, N)$ multi-access coded caching (MACC) system introduced by Hachem et al. The system consists of a server storing $N$ equal-sized files, $K$ cache nodes, each with a storage capacity of $M$ files, and $K$ users, each accessing $L$ consecutive cache nodes in a cyclic wrap-around topology. The server transmits coded information to the users via an error-free capacitated broadcast channel, such that each user obtains its own requested file as a combination of the server transmission and the accessible caches' content. Our objective is to minimize the worst-case transmission load over all possible user demands. First, for the cyclically $L$-separated placement, we derive a new converse bound using the acyclic index coding bound. By carefully counting all valid cache supports, the proposed converse improves upon an existing bound for the same placement. We then develop a linear coded caching scheme based on a novel determinant-based interference alignment strategy, which achieves the new converse bound exactly. Exploiting the determinant structure of a random generating matrix (each of whose columns corresponds to one user), this scheme simultaneously aligns interference across all users into low-dimensional subspaces, while preserving the decodability of their desired packets. Furthermore, by averaging acyclic index coding bounds over cyclic user permutations, we derive a general converse bound applicable to arbitrary uncoded cache placements. By combining the proposed scheme with memory sharing, we demonstrate that the achievable transmission load is within a factor of two of the global bound under uncoded placement. Finally, theoretical and numerical comparisons demonstrate that the proposed scheme generally achieves a strictly lower load than existing schemes.

0.22

Heterogeneous Demand-Private Coded Caching: Exact Characterization for Two Users and Two Files

cs.IT ·2026-10-09 ·Tati V D N Eswar, Jithin Ravi
similarity 0.67
Abstract · 20pages

We consider the demand-private coded caching problem with heterogeneous file sizes and cache capacities, where each user must recover its requested file without learning any information about the demands of the other users. We first extend the virtual-user reduction technique to accommodate heterogeneous cache sizes, thereby enabling the construction of demand-private coded caching schemes from non-private schemes. Our main contribution is an exact characterization of the memory-rate trade-off for the fundamental setting of two users and two files with arbitrary file sizes and cache capacities. Specifically, we characterize the optimal trade-off through eight linear inequalities and establish achievability by constructing explicit coded caching schemes for the non-trivial corner points, followed by memory sharing. These constructions include novel asymmetric cache placement strategies tailored to heterogeneous file sizes and cache capacities. For the converse, we exploit the distributional equivalences induced by demand privacy to derive information-theoretic lower bounds that explicitly account for the underlying heterogeneity. Our results generalize the exact memory-rate trade-off characterization for the homogeneous demand-private coded caching setting with two users and two files, while quantifying the additional transmission cost imposed by demand privacy compared with the non-private heterogeneous setting.

0.15

Order-Optimal Coded Caching With File and Demand Privacy

cs.IT ·2026-10-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.66
Abstract · 14 pages, 2 figures, 1 table

We study coded caching with joint file and demand privacy: each user recovers its requested file while learning nothing about the remaining files and the other users' requests jointly. Let $N$ and $K$ be the numbers of files and users, and let $M$ and $R$ denote the cache memory and delivery rate, both normalized by the file size. For every $N,K\ge2$ and every feasible cache size, we give a scheme whose worst-case delivery rate is at most $9/2$ times the optimum. To reduce the memory used for file shares, the scheme secret-shares $N-1$ differences relative to a reference file. Cached masks supply the correction needed to recover the requested file from its difference. For each integer $t\in\{0,\ldots,K-1\}$, the scheme achieves $M=1+(N-1)t/(K-t)$ and $R=K/(t+1)$. To lower-bound the delivery rate, we compare the joint cache entropy of user groups under alternative demand vectors, using one fixed user's privacy constraint. Two choices of groups determine the optimal delivery rate up to constants at the scale $\min\{K,1+(N-1)/(M-1)\}$ for $M>1$. At $M=1$, the exact optimum is $K$. A complementary bound on joint broadcast entropy gives the minimum memory for unit delivery rate, $1+(N-1)(K-1)$, and the exact tradeoff on an interval ending at that memory. All schemes and bounds apply to repeated as well as distinct requests.

0.59

The Exact Memory-Rate Tradeoff for Three-User Secure Coded Caching

cs.IT ·2026-11-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.63
Abstract · 34 pages, 2 figures

We determine the exact zero-error memory-rate tradeoff for secure coded caching with three users and any number $N\ge2$ of independent files. Each user recovers its requested file, while its cache and the broadcast jointly reveal no information about the complete tuple of unrequested files. For $N\ge4$, two converse inequalities establish the optimality of the known achievable points and the memory-sharing segments between them. For $N=3$, two additional bounds identify a new corner at $(M,R)=(3/2,2)$, where memory and rate are measured in file units. An explicit linear code over $\mathbb{F}_3$ attains this corner and reduces the rate by one quarter of a file relative to memory sharing between the known points. The converse links the information held by cache pairs and triples to delivery under repeated and distinct requests. Its equality conditions guide the construction: users cancel the keys to recover their requested files, while uniform masking protects the complete tuple of unrequested files.

0.21

Cache-Aided Linear Function Computation

cs.IT ·2026-10-14 ·Xiaohong Cai, Ruze Zhang, Laigang Guo, Raymond W. Yeung
theory similarity 0.62
Abstract · 11 pages, 2 figures. A shorter version has been submitted to the 2027 IEEE Information Theory Workshop (ITW)

We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the $N$ sources stores its own independent file over a finite field and has an additional cache of normalized size $M$. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every $N\geq3$, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for $0\leq M\leq1/(2N-1)$ and $M\geq(N-1)/N$, establishing the optimal memory--rate tradeoff in these two ranges.

0.22

Which Eviction Policy Should an LLM Cache Use? A Systematic Study Across Workloads, Capacities, and Encoders

cs.DB cs.LG ·2026-08-20 ·Yash Kulkarni, Shubham Harkare, Arvind Yogesh Suresh Babu
similarity 0.60
Abstract · 11 pages, 9 figures

Semantic caches reuse an LLM response when the incoming query embedding lies near a cached query, but proposed eviction policies have rarely been compared under one protocol. Using CLEVER, we evaluate FIFO, LRU, LFU, ARC, GDSF, a single-pass streaming adaptation of SISO, and a semantic-redundancy policy across three ordered, deduplicated query corpora, three cache capacities, and two encoders. No evaluated policy improves on LFU by more than 0.041 percentage points in any of the eighteen settings. Replacement is not irrelevant: FIFO and streaming SISO trail LFU by as much as 8.67 and 8.55 points, respectively, at tight capacity. We explain the missing upside with a conditional packing result. Under exact lookup and insert-on-miss, a newly inserted entry cannot have a resident neighbor within the hit radius, so a geometry-aware eviction rule receives little new redundancy signal. A separate audit exposes a larger problem with the evaluated operating point. At MiniLM's median nearest-neighbor threshold, only 2.1-3.9% of sampled LMSYS and QQP hits are judged answer-substitutable, reducing raw hit rates of 51-60% to quality-adjusted rates of 1.1-2.2%. The cross-encoder study further shows that thresholds do not transfer between embedding models. LFU is the strongest simple default in this protocol; deployment decisions should first establish answer validity and then test sub-point policy differences with exact search.

0.20

Secure Multi-Access Coded Caching: A Lifting Approach

cs.IT ·2026-10-04 ·Han Fang, Qinyi Lu, Nan Liu, Wei Kang
theory similarity 0.59
Abstract · 48 pages, 2 figures. This paper was presented in part at the 2024 IEEE Information Theory Workshop(ITW)

We construct secure cyclic multi-access coded caching schemes by re-encoding the caches of a secure single-access scheme and reusing its multicast message unchanged. For a library of $N$ files, each of $K$ users reads $L<K$ consecutive shared caches and must recover its requested file while learning no information about the other files. Starting from a parent scheme with a cyclic representation of its cached symbols, the transformation lets each access window recover the corresponding parent-cache symbols and, conditioned on them, learn nothing about the remaining symbols. A deterministic Pascal-window encoder handles symbols whose consecutive appearances span at least $L$ users. A randomized complement-dual encoder handles shorter spans. Over a suitable finite field, these encoders attain the exact minimum per-block storage for every input length in the block-separable, parent-preserving class. Applying the transformation to two secure single-access schemes gives an achievable memory-rate family for $N,K\ge2$ and $1\le L<K$, including the exact rate-one cache size $(N-1)(K-1)/L$. Using converse bounds for arbitrary secure multi-access schemes, we prove approximation guarantees for the achievable family and give a proof of the exact $L=K-1$ tradeoff.

0.34