{"id":"5ccba0fc-9bfd-4db6-b1c6-fbd2ec446b20","arxiv_id":"1908.04036","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A superposition-coding scheme with per-layer rates achieves near-optimal, within-factor-4 delivery time for cache-aided SISO broadcast with uneven-capacity users, and full-capacity delay remains achievable when each user's capacity exceeds a closed-form threshold.","lead":"This paper designs a layered superposition-coding delivery scheme for cache-aided wireless broadcast where users have different channel speeds, and proves it is within a factor of 4 of the optimal delivery time. It shows that the full-capacity delay of coded caching can be preserved even when many users have weaker channels, as long as their speeds stay above a simple per-user threshold.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 omits the K-Kγ-th power layer, leaving the XOR X_{K-Kγ,...,K} undelivered; the achievability proof of Theorem 1 fails as written, though a one-line fix restores it.","rationale":"The central factor-4 claim appears mathematically sound in substance, but the manuscript's own Algorithm 1 does not prove the achievability half of Theorem 1 because of the loop bound in Section IV-B. This is the most load-bearing concrete defect I can identify: it invalidates the proof as written, yet it is localized and easy to repair. The reader's weakest_assumption targets the converse, but a cut argument restricting any feasible K-user schedule to the first w users should justify Eq. (26); the paper should state it explicitly, but I do not see a counterexample to the lower bound. Other elements, including Appendix A's binomial bound and the wγ≥1 ratio bound, check out, and the corollary follows from Eq. (8). Because the flaw is in the presented algorithm rather than in the theorem's statement, a conditional accept with a required revision is the right outcome; no change to the Reader's verdict is needed.","tokens_in":9629,"tokens_out":29263,"duration_ms":316920,"concrete_test":"Simulate Algorithm 1 exactly as written for K=3, γ=1/3, ε<1, α=(ε,ε,1). The loop runs only over k=1; the layer-k=2 XOR X_{2,3}=W_{2,{3}}⊕W_{3,{2}} is never sent, so user 2's file lacks subfile W_{2,{3}} and user 3 lacks W_{3,{2}}. Then rerun with the loop bound changed to K-Kγ=2 (β_2=ε); both layers finish in T=1/ε and every user's file is complete, confirming the off-by-one is the only obstruction to achievability.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV-B, Algorithm 1 Step 3 restricts power layers to k∈[K-Kγ-1], and Eq. (24) takes the max over the same range. But the XORs defined in Eq. (15) exist for every min user k∈[1,K-Kγ]; the final layer k=K-Kγ contains the single XOR X_{K-Kγ,...,K}=⊕_{k=K-Kγ}^K W_{d_k, {K-Kγ,...,K}\\{k}}. This message carries one requested subfile for each of users K-Kγ,...,K, so without it those users' files are incomplete. Hence the algorithm as written does not achieve the delay in Theorem 1; the theorem's achievability proof is not valid as stated. This is a concrete off-by-one error, not a conceptual one: extending the loop to K-Kγ and defining β_k via Eq. (19) for k=K-Kγ keeps every per-layer delay equal to the right side of Eq. (25), so the claimed T_sc is still achievable after the fix. The converse cut flagged by the Reader appears repairable by a standard subset argument, so I do not regard it as the primary blocker.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a K-user cache-aided SISO broadcast channel in which the receivers have generally different normalized capacities alpha_k, ordered from weakest to strongest. It proposes a superposition-coding delivery scheme that transmits coded-caching XOR messages in power layers indexed by the weakest user in the message's user subset. The main result, Theorem 1, claims that the worst-case delivery time T_sc(K,gamma,alpha) = max_w (1/alpha_w) [C(K,Kgamma+1)-C(K-w,Kgamma+1)]/C(K,Kgamma) is achievable and is within a multiplicative factor of 4 of the optimal delivery time. A corollary gives per-user capacity thresholds under which the full-capacity Maddah-Ali-Niesen delay is still achievable. The achievability proof is via Algorithm 1, and the converse uses an augmented-system argument that invokes a lower bound from [36].","tokens_in":9850,"tokens_out":19027,"duration_ms":208332,"significance":"If the theorem is correct, the paper provides a crisp constant-factor characterization of coded caching over uneven-capacity broadcast channels and shows that the worst-user bottleneck does not destroy the multicast gain beyond a factor of 4. The proposed scheme is explicit, the achievable delay is a closed-form expression with no fitted parameters, and the converse relies on an external lower bound rather than on circular reasoning. The paper also gives a falsifiable quantitative prediction (the threshold condition of Corollary 1). However, the achievability proof as written omits one power layer, and the converse's subset lower bound is asserted rather than proved; both are repairable, but they currently prevent the theorem from being fully established.","major_comments":[{"comment":"The algorithm defines power layers only for k in [K-Kgamma-1], and Eq. (24) takes the delay maximum over the same range. However, the XORs defined in Eq. (15) exist for every k in [1,K-Kgamma], and the final layer k=K-Kgamma contains the single XOR X_{K-Kgamma,...,K} = \\oplus_{k=K-Kgamma}^K W_{d_k,{K-Kgamma,...,K}\\{k}}. Each user in {K-Kgamma,...,K} needs one subfile from this XOR, so the procedure as written does not deliver all requested data and does not achieve the delay claimed in Theorem 1. This is a concrete off-by-one error rather than a conceptual one: extending the layer index to k=K-Kgamma and using Eq. (19) for that layer keeps the per-layer delay equal to the right-hand side of Eq. (25), since |X_{K-Kgamma}|=1. Please correct Algorithm 1, the statement that the scheme uses 'K-Kgamma-1 power layers' in Section IV-B, and the range in Eq. (24).","section":"Section IV-B, Algorithm 1, Eq. (24)"},{"comment":"The converse lower-bounds the augmented-system delay by (1/alpha_w) * (1/2) * w(1-gamma)/(1+w*gamma), citing [36] for 'a system with w cache-aided users.' The augmented system, however, has K users, and the extra K-w users have caches and receive transmissions. It is not immediate that the w-user lower bound of [36] applies to the first w users of this larger network; the extra users could interact with the multicast structure, and the paper gives no cut argument. Since this lower bound is the basis for the factor-4 gap, the proof of Theorem 1 is incomplete at this point. Please add a lemma that justifies the subset lower bound, or state precisely which result in [36] yields it and why the presence of the extra users does not invalidate it.","section":"Section V, Eq. (26)"}],"minor_comments":[{"comment":"The pseudo-code is hard to parse: Step 3 defines beta_k inside a loop and is immediately followed by another loop 'for all k in [K-Kgamma-1]' containing Steps 4-7. Please rewrite it to separate the precomputation of the power exponents and rates from the transmission loop, and clarify that in each time slot one XOR from each non-empty layer is transmitted simultaneously.","section":"Section IV-B, Algorithm 1"},{"comment":"The symbol 'T_e' in Eq. (28) appears to be a typo for 'T_aug' (or possibly 'T^*'), and the two-line fraction in Eq. (26) is difficult to read; please clean up the notation.","section":"Section V, Eq. (28)"},{"comment":"The expression '|X_k|(K Kgamma) * 1/r_k' is notationally confusing: the delay should be |X_k| / C(K,Kgamma) * 1/r_k, because each XOR has size 1/C(K,Kgamma) of a file. Please make the division explicit.","section":"Section IV-D, Eq. (24)"},{"comment":"The word 'Sterling' should be 'Stirling'. The approximate formula used in the proof is informal, but the exact threshold expression in Eq. (10) is what matters, so this is only a presentation issue.","section":"Corollary 1 proof"},{"comment":"There is a small typo in the opening sentence: 'T*(k,gamma,alpha)' should be 'T*(K,gamma,alpha)'. Also, the scalar alpha_w and the capacity vector alpha are both denoted by alpha in Eq. (26); please disambiguate them.","section":"Section V"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the main theorem is right: a factor-4 order-optimal worst-case delivery time for cache-aided SISO BC with uneven capacities, via a superposition scheme that transmits XORs in layers indexed by the weakest user in each subset. Second, the paper as written has a concrete off-by-one: Algorithm 1 runs power layers only up to K−Kγ−1, but XORs exist up to min-user index K−Kγ. The final layer is a single XOR X_{K−Kγ,...,K}, and without it those users do not get all their data. The achievability proof of Theorem 1 therefore fails as stated. It is a one-line fix: extend the loop and the β recursion to K−Kγ; the per-layer delay is unchanged by the same cancellation that makes all other layers equal. I checked the algebra in Eqs. (24)-(25) and the gap proof in Section V; both are consistent once that layer is included.\n\nWhat is genuinely new: the previous topological result [14] handled a binary case; this generalizes to arbitrary K and capacity levels, and the factor-4 converse is new. The threshold corollary (full-capacity delay achievable if α_k ≥ 1−e^{−kγ}) is a nice by-product and follows from the theorem plus Stirling, no curve fitting.\n\nSoft spots, in order of seriousness. (1) The off-by-one above. It is real, but it is exactly the kind of bug that survives a first submission and gets fixed in revision; the conceptual scheme stands. (2) The converse uses the factor-2 lower bound of [36] on a w-user network, applied to an augmented K-user system where the first w users have capacity α_w and the rest unit. The paper handwaves the cut argument. On reading, the missing step is a standard subset argument: ignore the extra K−w users and treat the first w as a standalone w-user network with rate α_w; their caches give no additional leverage, so the [36] bound applies. That should be written down, but I do not believe it collapses. (3) Minor: the threshold is presented with the approximation sign; the exact binomial expression is what is proved, and the exponential is asymptotic. That is fine, but it should be labeled.\n\nThe citation pattern is fair; self-citations are to prior work by the same group on the topological case, which is the actual starting point, so no concern.\n\nWho is this for: people working on coded caching for wireless broadcast. Not a broad-field paper, but it settles a natural open question within a constant factor. I would send it to a serious referee. If I were the editor, I'd ask for a revision that fixes Algorithm 1 and spells out the subset argument.","headline":"Factor-4 order-optimal result for uneven-capacity coded caching is correct in substance, but Algorithm 1 has an off-by-one that omits the final layer and must be fixed.","tokens_in":10391,"tokens_out":3923,"would_cite":true,"duration_ms":37496,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A superposition-coding scheme achieves the optimal worst-case delivery time of cache-aided multicasting within a factor of 4 when receiver channel capacities are uneven.","keywords":["coded caching","wireless caching","broadcast channel","superposition coding","worst-user bottleneck","uneven channel capacities","delivery time","multicast gain"],"falsifier":"Run the proposed scheme and a brute-force-optimal schedule on a small instance such as $K=4$, $\\gamma=1/4$, $\\alpha=(\\epsilon,1,1,1)$; if the optimal worst-case delivery time falls below $T_{\\mathrm{sc}}/4$, the factor-4 gap claim is false, and if the augmented-system lower bound is violated, the converse step is unsound.","tokens_in":9425,"feed_emoji":"📡","tokens_out":8447,"duration_ms":79979,"temperature":0.7,"pith_summary":"This paper asks whether the multicast gains of coded caching survive when receivers have unequal channel capacities. It answers yes: a superposition-coding scheme delivers all requested files within a factor of 4 of the optimal worst-case delivery time for any number of users, any cache fraction, and any capacity vector. The scheme's key move is to identify a bottleneck user that need not be the weakest user, then transmit XOR messages assigned to each power layer at the rate of that layer's weakest participant while stronger messages ride in higher layers. A corollary shows that the ideal all-unit-capacity delay remains achievable even when many users have degraded channels, provided each user $k$'s capacity stays above about $1-e^{-k\\gamma}$. The result matters because the worst-user bottleneck was thought to halve or worse the coded-caching gain; this paper argues the gain can be preserved up to a constant factor.","feed_headline":"Coded caching keeps its multicast gain when channels differ","feed_subtitle":"A power-layered delivery scheme stays within a factor of 4 of the optimal time, and often matches the ideal full-capacity delay.","key_machinery":"The load-bearing object is the superposition-coding layer structure built from the XOR multicast messages of the standard placement scheme. Each message $X_\\sigma$ is assigned to power layer $k$ if the weakest user in $\\sigma$ is user $k$; layer $k$ then contains $\\binom{K-k}{K\\gamma}$ messages. The algorithm picks a bottleneck user $w$ maximizing $\\left(\\binom{K}{K\\gamma+1}-\\binom{K-w}{K\\gamma+1}\\right)/\\alpha_w$, sets every layer's rate proportional to $\\alpha_w$, and allocates powers $P^{-\\beta_k}$ so that each user decodes its own higher layers by successive interference cancellation while treating lower layers as noise. This reduces the uneven-capacity problem to a single scalar bottleneck parameter $w$ and yields the closed-form delay. The converse hinges on a cut lower bound for a $w$-user cache network applied to the augmented system.","core_discovery":"On its own terms, the paper's discovery is a tight constant-factor characterization of the optimal worst-case delivery time in the $K$-user SISO broadcast channel with cache fraction $\\gamma$ and ordered capacities $\\alpha_1 \\leq \\cdots \\leq \\alpha_K$. Theorem 1 states that the delay $T_{\\mathrm{sc}} = \\max_w \\left\\{ \\frac{1}{\\alpha_w} \\cdot \\frac{\\binom{K}{K\\gamma+1} - \\binom{K-w}{K\\gamma+1}}{\\binom{K}{K\\gamma}} \\right\\}$ is achievable and lies within a factor of 4 of the optimum $T^*$. The achievability scheme partitions the $\\binom{K}{K\\gamma+1}$ multicast XOR messages into layers according to their weakest user and superposes them, with power and rate chosen so that each user decodes its own layers and treats lower layers as noise. The converse augments the system by raising the first $w$ users' capacities to $\\alpha_w$ and the rest to 1, then applies a known factor-2 lower bound for $w$-user cache networks to conclude no scheme can do much better. A direct corollary is that the baseline delay $K(1-\\gamma)/(1+K\\gamma)$ is preserved when $\\alpha_k \\geq 1 - \\binom{K-k}{K\\gamma+1}/\\binom{K}{K\\gamma+1} \\approx 1-e^{-k\\gamma}$ for every $k$.","pith_inferences":["A sharp experimental check would measure the delay onset against the predicted threshold $1-e^{-k\\gamma}$ in a small three- or four-user testbed; the formula is precise enough to accept or reject.","The converse's cut lower bound is the most likely place for improvement; if stronger users' caches can help weaker users decode, the true multiplicative gap may be below 4, and exact small-$K$ computations could reveal it.","The same layer-superposition idea could be ported to multi-antenna or erasure broadcast channels, where each user's 'capacity' becomes a decoding probability rather than a fixed rate and the bottleneck user becomes a random index."],"forward_implications":["If Theorem 1 is right, uneven channel capacities cost at most a constant factor of 4, so cache-aided multicast remains usable in wireless broadcast settings with heterogeneous links.","The threshold $\\alpha_k \\gtrsim 1-e^{-k\\gamma}$ means the full unit-capacity delay is achievable even when many users have weaker channels, and smaller caches make the system more tolerant of unevenness.","The bottleneck user $w$ defined by the argmax, not the weakest user, governs delivery time, so channel improvements should be targeted at users near $w$.","Because the scheme reuses the baseline cache placement unchanged, it can be layered onto existing coded-caching deployments without changing the prefetching phase."],"supporting_citations":[{"why":"Supplies the baseline cache placement, the XOR multicast message structure, and the unit-capacity delay $K(1-\\gamma)/(1+K\\gamma)$ that the new scheme extends.","marker":"[1]"},{"why":"Defines the naive worst-user delivery time and the earlier practice of transmitting each XOR at the rate of its weakest user, the baseline the paper improves on.","marker":"[13]"},{"why":"Introduces the two-level superposition approach for a binary topological special case that this paper generalizes to arbitrary ordered capacities.","marker":"[14]"},{"why":"Presents a closely related superposition-coded caching scheme for Gaussian broadcast channels, giving context for the power-layer design.","marker":"[30]"},{"why":"Provides the generalized-degrees-of-freedom normalization that lets each user's capacity be represented by a scalar $\\alpha_k\\in[0,1]$.","marker":"[31]"},{"why":"Supplies the factor-2 lower bound on $w$-user cache-network delivery time that the converse applies to the augmented system.","marker":"[36]"}],"fun_headline_variants":["Caching wins even when users have uneven channels","Uneven channel speeds still allow near-optimal caching","Power-layered caching beats the worst-user limit","Factor-4 optimal caching for users with mixed rates","Caching with unequal channels: near-optimal delay"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The converse assumes that adding extra stronger users with caches cannot reduce the time needed to serve the weak users below the known lower bound for a $w$-user system.","fun_headline_variants_meta":{"raw":{"variants":["Caching wins even when users have uneven channels","Uneven channel speeds still allow near-optimal caching","Power-layered caching beats the worst-user limit","Factor-4 optimal caching for users with mixed rates","Caching with unequal channels: near-optimal delay"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000516,"raw_usage":{"total_tokens":2550,"prompt_tokens":1040,"completion_tokens":1510,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":1436}},"tokens_in":656,"tokens_out":1510,"duration_ms":12394,"temperature":1.0,"reasoning_tokens":1436,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:55:28.389339+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed scheme and a brute-force-optimal schedule on a small instance such as $K=4$, $\\gamma=1/4$, $\\alpha=(\\epsilon,1,1,1)$; if the optimal worst-case delivery time falls below $T_{\\mathrm{sc}}/4$, the factor-4 gap claim is false, and if the augmented-system lower bound is violated, the converse step is unsound.","supporting_citations":[{"cited_title":"Fundamental limits of caching,","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline cache placement, the XOR multicast message structure, and the unit-capacity delay $K(1-\\gamma)/(1+K\\gamma)$ that the new scheme extends."},{"cited_title":"On the coded caching based wireless video transmission scheme,","cited_arxiv_id":null,"evidence_quote":"Defines the naive worst-user delivery time and the earlier practice of transmitting each XOR at the rate of its weakest user, the baseline the paper improves on."},{"cited_title":"Wireless coded caching: A topological perspec- tive,","cited_arxiv_id":null,"evidence_quote":"Introduces the two-level superposition approach for a binary topological special case that this paper generalizes to arbitrary ordered capacities."},{"cited_title":"Caching and coded delivery over gaussian broadcast channels for energy efficiency,","cited_arxiv_id":null,"evidence_quote":"Presents a closely related superposition-coded caching scheme for Gaussian broadcast channels, giving context for the power-layer design."},{"cited_title":"Generalized Degrees of Freedom of the symmetric Gaussian K user Interference Channel,","cited_arxiv_id":null,"evidence_quote":"Provides the generalized-degrees-of-freedom normalization that lets each user's capacity be represented by a scalar $\\alpha_k\\in[0,1]$."},{"cited_title":"Characterizing the rate-memory tradeoff in cache networks within a factor of 2,","cited_arxiv_id":null,"evidence_quote":"Supplies the factor-2 lower bound on $w$-user cache-network delivery time that the converse applies to the augmented system."}],"review_version":1}