{"id":"e2b5cc1f-22dd-4c1f-9f7d-eea49159cad6","arxiv_id":"2506.16208","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Pyramid sampling selects a subset of symmetric-function histogram cells to reduce over-the-air computation constellation design complexity from exponential to a tunable lower order, trading accuracy for tractability.","lead":"This paper proposes pyramid sampling to cut the computational cost of designing digital modulations for over-the-air computation, replacing an exponential enumeration of input combinations with a tunable subset. It also shows that an extreme case recovers majority-vote aggregation with standard modulations and no signal overlap.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 1's Ωp is empty for p∤K, and its true cardinality C(K/p+q−1,q−1) differs from the printed C(K−p+q,q−1), so the headline O(q^{K−p+1}) complexity reduction and the trade-off analysis are unsupported.","rationale":"The reader's rejection is based on the same load-bearing weakness: the set Ωp in Definition 1 does not have the cardinality the paper claims, and for many parameter choices it is empty. This is not a cosmetic typo: the paper's abstract and Section I claim a complexity reduction from O(q^K) to O(q^{K−p+1}), and that scaling is derived directly from |Ωp|. The mismatch is numerically dramatic (36 vs. 11440 for K=16, q=8, p=8), and the p∤K case makes the optimization and δ(p) undefined. A corrected analysis would need to either restrict p to divisors of K or redefine Ωp so that it is nonempty for all p. In either case, the printed formula and the O(q^{K−p+1}) claim must be revised. I agree with the reader that the paper, as written, does not provide a sound basis for its headline complexity result. I also note, in fairness, that Proposition 3's no-overlap argument for the special case p=K is valid: if all nodes send the same symbol x(i), the sum is K x(i), and distinct symbols remain distinct when scaled by K. The majority-based scheme is therefore a meaningful special case, and the qualitative idea of pyramid sampling may be salvageable. But the central general claim about complexity reduction is unsupported, which justifies the rejection. The reader's weakest_assumption points at the same divisor issue and cardinality mismatch, so my assessment agrees with the reader's verdict.","tokens_in":18855,"tokens_out":9483,"duration_ms":113754,"concrete_test":"Enumerate Ωp directly for K=16, q=8, p=8: count vectors h∈{0,8,16}^8 with sum 16; the count is q + C(q,2) = 8 + 28 = 36. Compare this with C(K−p+q, q−1) = C(16,7) = 11440 and with the claimed O(q^{K−p+1}) = O(q^9). Then check p=3, K=16: the congruence 3∑ m_j = 16 has no solution, so Ω3 is empty; if the paper's definition leaves this case undefined, the optimization (4) has zero constraints and the trade-off analysis cannot be applied. Recomputing Figure 4 with either the corrected formula or the empty-set cases would settle whether the stated complexity scaling and Proposition 1 survive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central complexity claim rests on the cardinality of Ωp, but Definition 1 and the stated count are inconsistent. By (7), Ωp requires each histogram bin h_j to be a multiple of p and the total to be K. Writing h_j = p m_j gives p∑ m_j = K, so an integer solution exists iff p divides K. For K=3, q=4, p=2, Ωp is empty; then T_p = g|_Ωp is undefined, the optimization in (4) has no constraints, and δ(p), Figure 4, and the claimed p∈{1,…,K} generality are vacuous. When p does divide K, the true count is the stars-and-bars count with K/p units, |Ωp| = C(K/p + q − 1, q − 1), not the printed C(K−p+q, q−1). For K=16, q=8, p=8, the true count is C(2+8−1,7)=36, while the paper's formula gives C(16,7)=11440 and the headline O(q^{K−p+1})=O(q^9). Since δ(p)=log|Y_g^p|≤log|Ωp| feeds (14), Proposition 1's cost ratios, and the complexity–accuracy curves, the paper's central reduction from O(q^K) to O(q^{K−p+1}) is not established. The error may be conservative for fixed p, but the internal inconsistency means the method as defined is undefined for non-dividing p and the quantitative claims need correction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes pyramid sampling for digital over-the-air computation under symmetric aggregation. The idea is to constrain the constellation design to histograms whose bin counts are multiples of a sampling order p, thereby reducing the number of constraints in the max-min constellation design problem. The paper claims that this reduces encoder-design complexity from O(q^K) to O(q^{K-p+1}), introduces majority-based sampling (p=K) as a special case that uses only q consensus points, and supports the approach with simulations for sum, product, geometric-mean, and max functions. The central combinatorial statement underlying the complexity reduction is, however, incorrect.","tokens_in":19236,"tokens_out":10740,"duration_ms":119826,"significance":"If the complexity claim were correct, the framework would be valuable: it unifies several existing digital OAC schemes as special cases, permits standard modulation formats without overlap constraints in the p=K regime, and offers a principled complexity-accuracy trade-off. The paper is not fitting parameters to data; the analysis is analytical and the simulations are used to illustrate qualitative behavior. The majority-based sampling idea is intuitive and likely useful. However, the stated quantitative contribution depends on a false cardinality formula for the sampling set, so the headline complexity reduction and the general trade-off curves are not established as written.","major_comments":[{"comment":"The claimed cardinality |Ωp| = C(K-p+q, q-1) is false for the set defined in (7). Since every h_j must be a multiple of p, writing h_j = p m_j gives Σ_j m_j = K/p, so the set is empty unless p divides K, and when it is nonempty the count is C(K/p + q - 1, q - 1). For example, K=3, q=4, p=2 gives an empty set, not C(5,3)=10; for K=16, q=8, p=8 the printed formula gives C(16,7)=11440, whereas the true count is C(9,7)=36. Because Eq. (14), the complexity discussion, Figure 4, and the headline O(q^{K-p+1}) all rely on this count, the central reduction claim is unsupported and the method is undefined for non-dividing p.","section":"Definition 1, Eq. (7)"},{"comment":"The general complexity-accuracy trade-off is based on log|Ωp|. With the corrected cardinality, for p | K and fixed K while q grows, log|Ωp| ≈ (K/p) log q, not (K-p+1) log q. Thus δ(p)/δ(1) does not behave as suggested by the O(q^{K-p+1}) formula, and Figure 4 needs to be recomputed. The special p=K case used in Proposition 1 may survive, because |Ω_K| = q is correct, but the general pyramid-sampling complexity claim for intermediate p is not established.","section":"Eq. (14) and Figure 4"},{"comment":"The proof asserts that Ω_p ⊆ Ω_{p'} for every p' ≤ p, but this inclusion follows from the definition only when p' divides p. For instance, for p=3 and p'=2, the histogram (3,0,0) is in Ω_3 but not in Ω_2. Consequently, the statement that constraints satisfied for sampling order p automatically prevent overlaps for all lower orders p' ≤ p is not proved. The proposition needs a divisibility condition or a different nesting argument.","section":"Proposition 2, Eq. (19)"},{"comment":"The count |S^{(p)}_{i,j}| = C(K+q-1-p, q-1) does not match the definition in (20). Once p labelled coordinates are fixed to transition from i to j, each of the remaining K-p coordinates can take any of q values, giving q^{K-p} pairs, not a stars-and-bars count. For example, K=3, q=3, p=1 gives 9 pairs, not C(4,2)=6. The union over p therefore has size (q^K - 1)/(q - 1), not C(K+q-1, q), and the claimed 1/|S_{i,j}| constraint-reduction factor in Section III-A is incorrect.","section":"Lemma 1 and Eq. (32)"}],"minor_comments":[{"comment":"The legend in Figure 5 lists the scheme 'p=K, qK' twice, which makes the comparison difficult to read.","section":"Section IV, Figure 5"},{"comment":"Eq. (24c) contains 'gp0,2q = gp0,2q'; the intended relation is presumably gp0,2q = gp2,0q.","section":"Eq. (24)"},{"comment":"The sentence 'the cardinality of Ωp is p(K+q-1 q-1)' appears to have a formatting error, and the parenthetical 'where Ω1 indicates the whole input domain' should be phrased as 'for p=1, Ω1 = Ω'.","section":"After Eq. (7)"},{"comment":"The caption says q ∈ {4,32,64} while the text says q ∈ {4,32,64,128}; these should be reconciled.","section":"Figure 4 caption"},{"comment":"The notation 'qK' is used both for the product q·K and for q^K in Proposition 1, Figure 5, and Appendix B; using an explicit superscript would remove the ambiguity.","section":"Proposition 1 and Appendix B"},{"comment":"The authors correctly note that the computation-error comparison assumes an ideal channel; this limitation should be stated at the start of the experiment rather than only after the results, since the figure could otherwise be misread as an end-to-end OAC comparison.","section":"Section IV, Figure 5 discussion"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick read of 2506.16208. The headline complexity reduction does not hold as stated. Definition 1's Ωp requires every histogram bin to be a multiple of p and the bins to sum to K. That set is empty whenever p does not divide K, and when p does divide K its size is C(K/p+q−1, q−1), not the printed C(K−p+q, q−1). For K=16, q=8, p=8, the true count is 36, not 11440, so the O(q^{K−p+1}) scaling, the δ(p) curves in Figure 4, and the general statement of Proposition 1 are unsupported. Lemma 1 has a separate counting problem: the set S^{(p)}_{i,j} as defined—p indices changed i→j—has size C(K,p)q^{K−p}, not C(K+q−1−p, q−1). The balls-and-bins argument counts histograms of K−p balls, a different object.\n\nWhat is genuinely nice: the qualitative idea of sampling histograms at multiples of p is new, and it does unify OBDA, FSK voting, and balanced-numeral schemes as p=K special cases. The p=K case itself is correct and clean: the received sums are K·x_i, so they are distinct and overlap-free, and any standard modulation works. That part is solid. The simulations are thin but consistent for the p values tested (1,2,4,8 with K=16), all of which divide K, so the experiments do not expose the empty-set problem.\n\nThe fix is not deep: redefine Ωp so it is nonempty for all p (for instance, allow a remainder bin), correct the cardinality, recompute δ(p), and repair or drop Lemma 1. Until that is done, the central trade-off curves and complexity claims are not reliable. I would send this to a referee with combinatorics expertise as a major revision, not a desk reject, because the core idea is salvageable and the p=K majority scheme is useful. For my own work, I would not cite the complexity claim in its current form.","headline":"The advertised O(q^{K-p+1}) complexity reduction rests on a false cardinality count and a sampling set that is empty for many p, but the qualitative pyramid idea and the p=K majority scheme are salvageable.","tokens_in":19713,"tokens_out":6361,"would_cite":false,"duration_ms":67044,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Pyramid sampling reduces digital over-the-air computation encoder design from checking all $q^K$ superimposed symbol combinations to $\\mathcal{O}(q^{K-p+1})$ representative histograms, and at $p=K$ leaves only $q$ consensus points that…","keywords":["over-the-air computation","pyramid sampling","majority-based sampling","constellation design","digital modulation","symmetric aggregation","quantization","wireless edge computing"],"falsifier":"Set $K=3$, $q=4$, and $p=2$. The claimed cardinality formula gives $\\binom{3-2+4}{3}=10$ sampled histograms, but a valid histogram must have every bin count in $\\{0,2,4,\\ldots\\}$ and those counts must sum to $3$; no such histogram exists, so the actual sampled set is empty. Running the proposed complexity analysis on this example—where the formula's prediction and the actual count disagree—settles whether the central claim holds as stated.","tokens_in":18636,"feed_emoji":"📡","tokens_out":14088,"duration_ms":147052,"temperature":0.7,"pith_summary":"This paper argues that the main obstacle to scalable digital over-the-air computation—the need to design the modulation by comparing all $q^K$ possible superimposed symbol combinations—can be removed for symmetric aggregation functions. It introduces pyramid sampling: instead of every input histogram, the designer keeps only histograms whose bin counts are multiples of a sampling order $p$, cutting the number of constraints from $\\mathcal{O}(q^K)$ to $\\mathcal{O}(q^{K-p+1})$ at a controlled cost in function accuracy. At the extreme $p=K$, only the $q$ combinations where all nodes transmit the same symbol remain, so the received signals are $q$ scaled copies of one constellation point that cannot overlap; standard modulations such as QAM, PSK, and ASK then work without bespoke design. If the paper is right, large-scale wireless computation becomes computationally feasible, and earlier one-bit and balanced-vote aggregation schemes reappear as special cases of a single design rule.","feed_headline":"Pyramid sampling cuts over-the-air computation design cost","feed_subtitle":"A few consensus inputs suffice for accurate wireless computing at far lower design cost.","key_machinery":"The load-bearing object is the level-$p$ pyramid-sampling set $\\Omega_p$, the sub-lattice of input histograms whose bin counts are all multiples of $p$; histograms are the right domain because a symmetric function depends only on counts per quantization level. Sampling on this lattice is what turns an $\\mathcal{O}(q^K)$ constraint set into an $\\mathcal{O}(q^{K-p+1})$ one. Two supporting identities carry the counting: the balls-and-bins count $\\binom{K+q-1-p}{q-1}$ for each transition set, summed by the hockey-stick binomial identity into $\\binom{K+q-1}{q}$, and the structural fact that at $p=K$ each received sum is $K$ times a single constellation point, which makes overlap impossible.","core_discovery":"Pyramid sampling is defined on the histogram of the $K$ quantized inputs, which is legitimate because the aggregation function is symmetric and therefore depends only on how many nodes chose each of the $q$ quantization levels. The full histogram domain $\\Omega$ has $\\binom{K+q-1}{q-1}$ elements, growing as $\\mathcal{O}(q^K)$; the level-$p$ sub-domain $\\Omega_p$ allows only bin counts that are multiples of $p$ and has cardinality $\\binom{K-p+q}{q-1}=\\mathcal{O}(q^{K-p+1})$. Solving the Part I max–min constellation optimization over $\\Omega_p$ instead of $\\Omega$ yields a design whose retained points are separated according to the function values, and the paper proves that at $p=K$ the $q$ agreement histograms produce received sums $K x(i)$ that are distinct whenever the $q$ transmit points $x(i)$ are distinct, so destructive overlaps are impossible by construction. Its Proposition 1 formalizes the payoff: using modulation level $q^K$ at $p=K$ makes the normalized sampling error a factor $K/q^{K-1}$ of the exhaustive design's error with design-cost ratio $\\mathcal{O}(K/((q-1)\\log_q K))$, while using level $qK$ matches the exhaustive error exactly at cost ratio $\\mathcal{O}(1/(q-1))$. Simulations over sum, product, and max functions confirm that moderate $p$ reaches the quantization error floor with orders-of-magnitude fewer constraints.","pith_inferences":["Editorial inference — Because the argument only uses histogram symmetry and Lipschitz dependence, the same complexity–accuracy trade-off should extend to other symmetric aggregates such as medians, variance, and order statistics, which the paper does not simulate.","Editorial inference — The exact cardinality formula needs $p$ to divide $K$; a practical version of the scheme for network sizes where $K$ is not a multiple of $p$ would have to round counts to the nearest valid lattice or randomize the sampling, which the paper does not spell out.","Editorial inference — The $p=K$ receiver is effectively a vote over constellation indices, so the problem becomes a conventional point-to-point codebook design; this suggests layering standard channel codes or shaping schemes on top of the consensus constellation, a direction the paper only gestures at in its conclusion.","Editorial inference — A natural stress test is to replace pyramid sampling with a random subset of constraints of the same size; if random subsets match pyramid performance, the exact lattice structure is not what is buying the accuracy."],"forward_implications":["Moderate sampling orders preserve the large-scale geometry of the designed constellation: in the paper's product-function experiment with $K=16$, $q=8$, increasing $p$ from 1 to 8 cuts the constraint count from $\\mathcal{O}(q^{16})$ to $\\mathcal{O}(q^2)$ while only one pair of constellation points collides.","At $p=K$, any standard modulation format can be used without overlap, and the design problem reduces from an intractable $\\mathcal{O}(q^K)$-constraint optimization to a linear-in-$q$ problem; one-bit over-the-air aggregation and balanced-vote aggregation appear as special cases.","Proposition 1 implies that raising the modulation level at $p=K$ can either beat the accuracy of an exhaustive low-level design at comparable cost or match its accuracy at a fraction $\\mathcal{O}(1/(q-1))$ of the cost.","For the sum function, the optimal constellation is PAM for every sampling order, so sampling does not change the optimum for that function.","The end-to-end accuracy at high SNR is dominated by the quantization floor of the sampler, while at low SNR the modulation's minimum distance governs robustness, with rectangular QAM outperforming hexagonal and PAM in the simulations."],"supporting_citations":[{"why":"Formulates the noise-aware max–min constellation design problem that pyramid sampling is introduced to accelerate.","marker":"[9]"},{"why":"Supplies the margin-based no-overlap optimization in (4) and the exhaustive design baseline whose $\\mathcal{O}(q^K)$ complexity is the target of the reduction.","marker":"[10]"},{"why":"Justifies treating a symmetric function as a function of the input histogram, the domain on which pyramid sampling is defined.","marker":"[33]"},{"why":"Provides the balls-and-bins counting used for the number of superimposed constellation sums.","marker":"[38]"},{"why":"Supplies the identity that sums the binomial counts in Lemma 1 to obtain the size of the transition sets.","marker":"[39]"},{"why":"Identified as the $q=2$ special case of majority-based sampling, grounding the claim that prior schemes are special cases.","marker":"[14]"},{"why":"Identified as a special case of majority-based sampling for balanced numeral systems and averaging.","marker":"[34]"}],"fun_headline_variants":["Pyramid sampling slashes OAC design complexity","Subset sampling reduces OAC design cost","Pyramid trick scales over-the-air computation design","Fewer constraints, same accuracy for OAC","Sampling strategy shrinks OAC design from exponential to practical"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's complexity count silently assumes that the sampling order $p$ divides the number of nodes $K$; when $K$ is not a multiple of $p$, the sampled input set can be empty and the claimed speedup has no optimization to run on.","fun_headline_variants_meta":{"raw":{"variants":["Pyramid sampling slashes OAC design complexity","Subset sampling reduces OAC design cost","Pyramid trick scales over-the-air computation design","Fewer constraints, same accuracy for OAC","Sampling strategy shrinks OAC design from exponential to practical"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000353,"raw_usage":{"total_tokens":2023,"prompt_tokens":1146,"completion_tokens":877,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":762,"completion_tokens_details":{"reasoning_tokens":804}},"tokens_in":762,"tokens_out":877,"duration_ms":10325,"temperature":1.0,"reasoning_tokens":804,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T23:45:03.298524+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $K=3$, $q=4$, and $p=2$. The claimed cardinality formula gives $\\binom{3-2+4}{3}=10$ sampled histograms, but a valid histogram must have every bin count in $\\{0,2,4,\\ldots\\}$ and those counts must sum to $3$; no such histogram exists, so the actual sampled set is empty. Running the proposed complexity analysis on this example—where the formula's prediction and the actual count disagree—settles whether the central claim holds as stated.","supporting_citations":[{"cited_title":"On Designing Modulation for Over-the-Air Computation -- Part I: Noise-Aware Design","cited_arxiv_id":"2506.15950","evidence_quote":"Formulates the noise-aware max–min constellation design problem that pyramid sampling is introduced to accelerate."},{"cited_title":"Deep sets,","cited_arxiv_id":null,"evidence_quote":"Justifies treating a symmetric function as a function of the input histogram, the domain on which pyramid sampling is defined."},{"cited_title":"Mitzenmacher and E","cited_arxiv_id":null,"evidence_quote":"Provides the balls-and-bins counting used for the number of superimposed constellation sums."},{"cited_title":"Generalized hockey stick identities and N-dimensional blockwalking,","cited_arxiv_id":null,"evidence_quote":"Supplies the identity that sums the binomial counts in Lemma 1 to obtain the size of the transition sets."},{"cited_title":"Over-the-air computation based on balanced number systems for federated edge learning,","cited_arxiv_id":null,"evidence_quote":"Identified as a special case of majority-based sampling for balanced numeral systems and averaging."}],"review_version":1}