{"id":"099dcb1d-2999-4b1a-ba5f-876a5bc93c93","arxiv_id":"2505.07016","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A hierarchical importance sampling scheme using Gács-Körner common information reduces the communication cost of multi-terminal remote function estimation over a broadcast channel.","lead":"This paper develops a way for one sender to help several receivers estimate statistics of a distribution using a broadcast message plus small per-receiver messages, leveraging correlated background knowledge. It shows that when the receivers' prior samples share a common part, the sender can transmit a single coarse sample to everyone and then refine privately, lowering communication cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Communication-cost reduction is not established by Lemma 2: χ^2 factor can make the hierarchical bound exceed the unicast cost.","rationale":"The paper's contribution is the claimed communication-cost reduction. The unique strength—paying the block divergence once—is an algebraic consequence of the chain rule, but the paper's formal cost expression in Lemma 2 includes a χ^2 factor that is not present in the standard scheme's cost and can be huge. This means the central claim is not proven by the provided analysis. The reader flagged the GK restriction as the weakest assumption; I find a more immediate technical gap: the order-notation argument omits the χ^2 factor. However, this is fixable with a tighter analysis or an explicit asymptotic statement, so the paper remains plausible and CONDITIONAL is appropriate.","tokens_in":10622,"tokens_out":26900,"duration_ms":241953,"concrete_test":"Take C∈{0,1} with p_C=(0.5,0.5), p_QC=(0.9,0.1), so D_KL(p_QC||p_C)≈0.531 bits and χ^2=0.64. Let the two decoders have identical conditional divergence d=D_KL(p_{Q|C}||p_{Y_i|C}) for both c. Standard cost per transmission is 2[D_KL(p_QC||p_C)+d]≈1.062+2d. Hierarchical bound from Lemma 2 is D_KL(p_QC||p_C)+(χ^2+1)·2d≈0.531+3.28d. Verify whether 0.531+3.28d < 1.062+2d; for d≥0.415 bits it fails. Compute the actual hierarchical cost (log2 n_c + E[log2 n_{i,c}]) for a finite n_c to see if the scheme still beats unicast. If the actual cost is lower but the Lemma 2 bound is not, the paper needs a tighter cost analysis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the broadcast-plus-unicast hierarchical scheme reduces communication cost by paying the block-level KL divergence once instead of once per decoder. The only formal support is Lemma 2's cost bound, which is O(D_KL(p_QC||p_C)) + (χ^2(p_C,p_QC)+1)/((n_c-1)/n_c) · E_{Q_C~p_QC}[Σ_i O(D_KL(p_{Q|C}||p_{Y_i|C}))]. Because χ^2(p_C,p_QC) can be exponentially large in D_KL(p_QC||p_C) (since E_p[p/q] ≥ exp(D_KL)), the multiplicative factor on the conditional terms can dominate the block-term saving. The informal comparison in Section IV ignores this factor and only notes that the block term appears once instead of twice. No theorem states that the hierarchical cost is ≤ the standard unicast cost; for a concrete distribution with D_KL(p_QC||p_C)=0.53 and conditional divergence d=1 bit, the Lemma 2 bound gives 3.81 bits vs 3.06 bits for the standard scheme, so the claimed reduction fails within the paper's own bound. The actual scheme likely does save the block term, but the paper's analysis does not demonstrate it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies a multi-terminal remote estimation problem in which an encoder with access to a target distribution p_Q helps N decoders estimate (possibly different) functionals over p_Q, while each decoder has access to a correlated prior p_{Y_i} through shared randomness. The authors refine the known minimal random coding (MRC) importance-sampling bound into a high-probability estimation-error guarantee (Proposition 1), then introduce a hierarchical sampling scheme that first samples a common block variable C via MRC and then refines the sample conditionally on C for each decoder. In the multi-terminal setting, the common block is chosen as the Gács-Körner common information of the correlated priors, so that the block-level index can be broadcast and only refinement indices are sent over unicast links. The paper claims that this reduces communication cost because the block-level KL divergence is paid once instead of once per decoder, and it provides bias, error, and cost bounds (Theorem 1, Corollaries 1--2, Lemma 2).","tokens_in":10854,"tokens_out":8222,"duration_ms":89508,"significance":"The hierarchical MRC construction and the use of Gács-Körner common information to coordinate a broadcast sampling step are original and clearly presented. The formal bias and estimation-error bounds, together with the edge-case recovery of Lemma 1, are useful sanity checks and the unicast bounds are of independent interest. If the communication-cost reduction were rigorously established, the scheme would be a meaningful advance for multi-terminal estimation with block-correlated priors. However, the central claimed advantage is not proven: Lemma 2 contains a chi-squared factor multiplying the conditional-divergence terms, and the informal comparison in Section IV ignores this factor. Moreover, the regime of non-zero Gács-Körner common information is acknowledged in Remark 2 to be rare in practice, which limits the scope of the result regardless of the technical gap.","major_comments":[{"comment":"The claimed communication-cost reduction is not established by the provided bounds. Lemma 2 upper-bounds the average hierarchical cost by O(D_KL(p_QC||p_C)) + ((chi^2(p_C,p_QC)+1)/((n_c-1)/n_c)) * E_{Q_C}[sum_i O(D_KL(p_{Q|C}||p_{Y_i|C}))], and Section IV then argues that the block-level divergence term is paid once rather than once per decoder. This ignores the multiplicative chi^2 factor on the conditional terms. Since chi^2(p_C,p_QC) can be exponentially large in D_KL(p_QC||p_C) (indeed chi^2+1 >= exp(D_KL) by Jensen's inequality), the second term can outweigh any saving from paying the block divergence once. No theorem states that the hierarchical cost is at most the standard unicast cost; the informal comparison in Section IV is therefore not sufficient for the abstract's claim that the scheme shows a reduction in communication cost. The authors should either provide a formal comparison with an explicit condition on chi^2 or a choice of n_c that keeps the factor bounded, or weaken the claim accordingly.","section":"Section IV, Lemma 2"},{"comment":"The comparison between hierarchical and standard schemes is made only at the level of O(.) expressions, without tracking the constants and the required sample sizes needed to achieve the same estimation-error guarantees. The standard scheme's cost also depends on the n_i required by Lemma 1 for a prescribed confidence level, and the hierarchical scheme's cost depends on n_c and n_{i,c} in a coupled way. To substantiate the statement in Section V that 'significant gains can be achieved', the authors should state a concrete theorem or a family of priors for which, with identical target bias and error parameters (epsilon, hat-epsilon_i, K), the hierarchical per-sample expected communication cost is provably smaller than the standard per-decoder MRC cost. Without such a statement, the cost-reduction claim remains a heuristic comparison of upper bounds.","section":"Section III-C and Section IV"}],"minor_comments":[{"comment":"The condition 'nc >= log(D_KL(p_QC||p_C)+t_c)' appears to be a typo: it should be 'nc >= exp(D_KL(p_QC||p_C)+t_c)', consistent with Theorem 1 and Lemma 1.","section":"Section III-B, Corollary 2"},{"comment":"The notation 'forall c,i in C' in the sentence 'When n_c >= exp(...) and forall c,i in C: n_{i,c} >= ...' is confusing: C is the alphabet of the common variable, while i indexes the decoders. It should be 'for all c in C and i in {1,2}'.","section":"Section IV"},{"comment":"The 'standard scheme' is described only informally as selecting an index from n_i samples for each decoder. For a rigorous comparison with the hierarchical scheme, the standard scheme should be stated with the same level of formality, including the exact number of samples n_i and the resulting per-transmission cost in bits.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The central claim of communication-cost reduction needs to be made rigorous before publication. The authors are transparent about the rarity of non-zero Gács-Körner common information, and this limitation should be reflected more strongly in the abstract and conclusion if the cost-reduction claim is not strengthened. The paper is likely to be a good fit for the journal once the comparison with the unicast baseline is turned into a formal statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing to know: the hierarchical sampling construction is real, and the bias/error analysis is careful, but the paper's central claim—that the broadcast scheme cuts communication cost by paying the block-level divergence once—is not supported by the paper's own Lemma 2. That lemma carries a chi-squared term multiplying the conditional divergence, and this factor can be exponentially large in the block divergence. So the formal bound can exceed the unicast baseline even when the block term is paid once. The stress-test example is concrete: with a block divergence of 0.53 bits and a conditional divergence of 1 bit, the Lemma 2 bound gives about 3.81 bits versus 3.06 for standard unicast. The actual scheme may still save the block term in practice, but the analysis does not demonstrate it.\n\nWhat is genuinely new: the two-stage MRC procedure—block-level sampling followed by conditional MRC—and its application to broadcast transmission using Gács-Körner common information. Theorem 1, Corollary 1, and Proposition 2 give bias, total-variation, and estimation-error bounds, and they degrade cleanly to Lemma 1 in the trivial and full-block partitions. Those point-to-point bounds are independently useful, and the broadcast-plus-unicast architecture is a natural and non-obvious extension of the MRC framework.\n\nWhere the soft spots are: the multi-terminal comparison in Section IV is informal and order-notation only. Lemma 2's chi-squared factor is not a small hidden constant; it can dominate the entire cost expression. The paper needs a formal finite-blocklength comparison, or at least a clear statement that the reduction is a heuristic advantage of the scheme rather than a proven property of the bound. The Gács-Körner restriction is real but acknowledged in Remark 2, and I would treat it as a scope limitation rather than a flaw. Minor issues: Corollary 2 has a typo (log instead of exp), and Proposition 2 appears to have an f^4 notation slip.\n\nWho this is for: people working on channel simulation, relative entropy coding, and remote estimation with side information. It gives a framework worth discussing, and the core idea deserves a serious referee. I would send it to review, but with the expectation of major revision: either prove the cost reduction or pull the claim back to what the bounds actually support.","headline":"The hierarchical sampling scheme is a genuine idea, but the paper's advertised communication-cost reduction is not actually established because Lemma 2's chi-squared factor can erase the block-level saving.","tokens_in":11372,"tokens_out":3863,"would_cite":false,"duration_ms":41331,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"When decoder priors share a nontrivial common variable, a two-stage broadcast/unicast sampling scheme pays the block-level divergence once and then refines per decoder.","keywords":["remote generation","importance sampling","minimal random coding","Gács-Körner common information","broadcast channel","multi-terminal estimation","hierarchical sampling","channel simulation"],"falsifier":"Simulate the two-stage scheme on a block-structured prior of the form $Y_1=(C,A)$, $Y_2=(C,B)$ with independent non-atomic $C,A,B$ and a target $p_Q$ for which $p_{QC}\\neq p_C$; compare the realized average bits per sample with $O(D_{KL}(p_{QC}\\|p_C))$ plus the summed conditional divergence term. If the broadcast stage does not save the block term across decoders, or if the estimation error exceeds the Theorem 1 bound at the stated confidence, the paper's central claim is contradicted.","tokens_in":10451,"feed_emoji":"📡","tokens_out":11815,"duration_ms":119987,"temperature":0.7,"pith_summary":"This paper tries to establish that correlation among decoders' prior samples can lower the communication cost of remote estimation when a broadcast link is available. The proposed mechanism splits sampling into two rounds: first, a block of the priors' shared common variable is chosen by minimal random coding and broadcast to all decoders; second, each decoder refines the selected block to its own prior using conditional importance sampling over a unicast link. When the priors have nonzero Gács-Körner common information, the KL divergence between target and prior over the common blocks is paid once per transmission rather than once per decoder. The paper supports this with bias, total-variation, and estimation-error upper bounds for the hierarchical scheme, and it leaves optimality open.","feed_headline":"Hierarchical sampling pays shared-block cost once, not per decoder","feed_subtitle":"A broadcast block plus unicast refinements saves bits when priors share a common variable.","key_machinery":"The load-bearing object is the two-stage (hierarchical) importance-sampling scheme built on the Gács-Körner common variable $C$, defined as the largest-entropy random variable that is a deterministic function of each decoder's prior, $C=g_1(Y_1)=g_2(Y_2)$. The first stage runs minimal random coding on the block variable $C$ with target $p_{QC}$ and prior $p_C$, producing one index $m_k$ that is broadcast to every decoder. The second stage runs conditional minimal random coding on each decoder's prior $p_{Y_i|C=c}$ with target $p_{Q|C=c}$, producing refinement indices $\\ell_{i,k}$ sent over unicast. The machinery that carries the cost argument is the KL chain-rule decomposition $D_{KL}(p_Q\\|p_{Y_i}) = D_{KL}(p_{QC}\\|p_C) + \\mathbb{E}_{Q_C}[D_{KL}(p_{Q|C}\\|p_{Y_i|C})]$, which shows the block term is common to all decoders while only the conditional term depends on $i$. Theorem 1 bounds the bias of the two-stage estimator in terms of tail probabilities of the log importance ratios, and Lemma 2 converts this into an average communication-complexity bound.","core_discovery":"The central discovery is a hierarchical sampling method for remote generation and estimation that exploits a common random variable shared by correlated priors. Given a nonzero Gács-Körner common information $C=g_1(Y_1)=g_2(Y_2)$, the encoder first draws $n_c$ samples from $p_C$, importance-samples one block index $m_k$ with respect to $p_{QC}$, and broadcasts $m_k$ to all decoders. Each decoder then draws $n_{i,c}$ samples from its conditional prior $p_{Y_i|C=c}$, importance-samples a refinement index $\\ell_{i,k}$ with respect to $p_{Q|C=c}$, and receives it over unicast. The average communication cost per sample is $O(D_{KL}(p_{QC}\\|p_C))$ for the broadcast stage plus $\\frac{\\chi^2(p_C,p_{QC})+1}{(n_c-1)/n_c}\\mathbb{E}_{Q_C}\\big[\\sum_i O(D_{KL}(p_{Q|C}\\|p_{Y_i|C}))\\big]$ for the refinement stage, so the block-level divergence is paid once instead of once per decoder. Theorem 1 and Proposition 2 give finite-sample upper bounds on the bias and estimation error, and Corollary 2 shows that when the function $f$ is constant on each block the sample complexity reduces to the block level.","pith_inferences":["Beyond the paper, one could approximate the scheme for continuous priors by coarsening the priors into blocks; the broadcast gain would then be limited by the fidelity of that coarsening, a tradeoff the paper does not quantify.","A natural extension is to interpret the two stages as successive refinement, with the broadcast block as a coarse description and the unicast step as per-decoder innovation, which may connect this scheme to rate-distortion formulations of remote estimation.","Because the paper deliberately omits improved index coding such as ordered random coding, replacing minimal random coding in both stages would likely preserve the once-per-block cost structure while shrinking the log-index terms in the communication cost."],"forward_implications":["If the priors have nonzero Gács-Körner common information, the two-stage scheme's average communication cost per sample is the block-level divergence plus the sum of per-decoder refinement divergences, so the shared part is paid once for all decoders.","The block-level term can be reduced by choosing a non-maximal common partition that minimizes the KL divergences with the target, and the encoder can transmit the corresponding partitioning functions once, with the overhead vanishing as the number of samples $K$ grows.","When the function $f$ is constant on each block of the partition, the point-to-point hierarchical scheme needs only block-level sample complexity, giving a tighter error bound than one-level minimal random coding.","The scheme extends to more than two decoders and to multiple hierarchy levels through generalized common information, with the savings amplified as the number of receivers grows.","The analysis provides finite-sample bias and estimation-error upper bounds, not just asymptotic rates, so the scheme comes with explicit sample counts for a target confidence level."],"supporting_citations":[{"why":"Supplies the importance-sampling sample-size and bias bounds that the paper turns into its Lemma 1 and Proposition 1.","marker":"[3]"},{"why":"Introduces minimal random coding, the single-decoder sampling procedure that the first stage of the hierarchical scheme reuses.","marker":"[4]"},{"why":"Defines Gács-Körner common information, the shared block variable whose broadcast use is the paper's central mechanism.","marker":"[18]"}],"fun_headline_variants":["Pay shared block cost once, then refine per decoder","One broadcast for common block, unicast for refinements","Hierarchical sampling: broadcast block, then refine per decoder","Common info in priors enables single broadcast step","Broadcast block sampling cuts per-decoder cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The scheme's advantage requires the joint prior $p_{Y_1,Y_2}$ to have nonzero Gács-Körner common information, meaning there is a nontrivial block variable $C$ that is a deterministic function of both observations; for typical continuous or smoothly correlated priors this $C$ is trivial and the broadcast stage carries no savings.","fun_headline_variants_meta":{"raw":{"variants":["Pay shared block cost once, then refine per decoder","One broadcast for common block, unicast for refinements","Hierarchical sampling: broadcast block, then refine per decoder","Common info in priors enables single broadcast step","Broadcast block sampling cuts per-decoder cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000724,"raw_usage":{"total_tokens":3314,"prompt_tokens":1081,"completion_tokens":2233,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":697,"completion_tokens_details":{"reasoning_tokens":2157}},"tokens_in":697,"tokens_out":2233,"duration_ms":17361,"temperature":1.0,"reasoning_tokens":2157,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:26:43.310464+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the two-stage scheme on a block-structured prior of the form $Y_1=(C,A)$, $Y_2=(C,B)$ with independent non-atomic $C,A,B$ and a target $p_Q$ for which $p_{QC}\\neq p_C$; compare the realized average bits per sample with $O(D_{KL}(p_{QC}\\|p_C))$ plus the summed conditional divergence term. If the broadcast stage does not save the block term across decoders, or if the estimation error exceeds the Theorem 1 bound at the stated confidence, the paper's central claim is contradicted.","supporting_citations":[{"cited_title":"The sample size required in importance sampling,","cited_arxiv_id":null,"evidence_quote":"Supplies the importance-sampling sample-size and bias bounds that the paper turns into its Lemma 1 and Proposition 1."},{"cited_title":"Minimal random code learning: Getting bits back from compressed model parameters,","cited_arxiv_id":null,"evidence_quote":"Introduces minimal random coding, the single-decoder sampling procedure that the first stage of the hierarchical scheme reuses."},{"cited_title":"Common information is far less than mutual information,","cited_arxiv_id":null,"evidence_quote":"Defines Gács-Körner common information, the shared block variable whose broadcast use is the paper's central mechanism."}],"review_version":1}