{"id":"d8a8b921-f67f-41c0-9248-3af5467e9817","arxiv_id":"2505.18919","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Fair-Count-Min partitions Count-Min columns among groups, allocating columns by group size for one hash row and by a binomial-minimum equation for multiple rows, aiming to equalize expected approximation factors.","lead":"The paper introduces Fair-Count-Min, a Count-Min sketch variant that gives each element group its own columns so items from different groups never collide, and claims this equalizes expected relative estimation error across groups. It matters because Count-Min is a standard streaming counter whose additive error hits rare items hardest, so a low-overhead fairness fix would be broadly useful.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"For d>1, Equation (8) equalizes expected minimum bucket size E[Y], not expected approximation factor E[alpha]; a toy counterexample shows the two diverge, so the central fairness theorem is unsupported and false as stated.","rationale":"The reader's weakest assumption is precisely the gap I identify: shifting from E[Y] to E[alpha] in the d>1 proof. The d=1 analysis is correct, and the negative price-of-fairness result for one row is a useful contribution. But the abstract and introduction promise a general FCM sketch with equal expected approximation factors across groups, and the d>1 guarantee is the only support for that claim. Section 3.2 explicitly calls the equalization of minimum bucket size a simplification, yet never proves that this simplification preserves equality of E[alpha]; Section 4 computes w_l from Eq. (8), and Section 6.8 validates that same quantity, so the entire pipeline optimizes the wrong objective if the simplification fails. A tiny counterexample with equal group sizes makes Eq. (8) trivially satisfied while E[alpha] differs substantially across groups, so the claimed theorem is not merely missing a technical lemma; it is false in a simple setting. The empirical sections may show small unfairness on particular datasets, but they do not test this counterexample and cannot replace a universal theoretical claim. Because the central theoretical contribution is invalid for d>1, the REJECT verdict is appropriate.","tokens_in":24629,"tokens_out":6975,"duration_ms":67843,"concrete_test":"Run an exact or Monte Carlo test: n_l=n_h=4, w=4, d=2, which gives w_l=w_h=2 and satisfies Eq. (8) with equality. Set frequencies l = {1,1,1,1000} and h = {100,100,100,100}. For random hash functions mapping each group's 4 elements uniformly into its 2 buckets per row, compute E[alpha_l] and E[alpha_h] over all elements and many hash realizations. The prediction is alpha_h = 0.5 for every h element; alpha_l for light elements is 1/(1000 + small) whenever the heavy element shares either of the two row buckets, which happens with probability 3/4. If the measured |E[alpha_l] - E[alpha_h]| is more than 0.1, Eq. (8) does not imply fairness. This single small instance decisively tests whether equalizing E[Y] is sufficient for equal expected approximation factors.","verdict_should_be":"REJECT","load_bearing_attack":"The paper's central claim for d>1 rests on the Section 3.2 simplification: 'equalizing the expected number of element types hashed into the minimum-size bucket' is treated as equivalent to equal expected approximation factors. This is not proven and is in fact false. For d=1 the argument uses an exact cancellation: for a bucket containing frequencies f_1,...,f_k, sum_j f_j / C = 1, so E[alpha_l] collapses to w_l/n_l (Eq. 4). For d>1 the estimate is min_i C_i(e), and taking the minimum destroys that cancellation; alpha(e)=f(e)/min_i C_i(e) depends on the full joint distribution of frequencies in the d buckets, not only on the number of element types. Equation (8) equalizes E[Y] where Y is the minimum of d binomial counts of bucket sizes. But E[alpha] is not a function of E[Y]. Concretely, let n_l=n_h=4, w_l=w_h=2, d=2, so Eq. (8) is satisfied trivially. Let group l have frequencies {1,1,1,1000} and group h have frequencies {100,100,100,100}. For h, every element has alpha = 100/200 = 0.5 in every realization. For l, a light element has alpha near 0.001 when it collides with the 1000-frequency element in at least one of the two rows (probability 3/4); the mean alpha over l is well below 0.5. Thus E[alpha_l] != E[alpha_h] although Eq. (8) holds. The theorem 'FCM is fair' for d>1 is therefore not established and fails in this setting. Section 4's allocation algorithm and Section 6.8's validation target Equation (8), so they do not rescue the fairness guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Fair-Count-Min (FCM), a Count-Min variant that partitions the sketch columns among element groups and uses group-aware semi-uniform hashing so that elements from different groups never collide. It claims that, with a suitable choice of per-group column counts w_l, FCM guarantees equal expected approximation factors E[α] across groups (Definition 2) without increasing the memory or time of a standard Count-Min sketch. For d=1, the paper derives w_l = (n_l/n)w through an exact cancellation. For d>1, it replaces the fairness target by Equation (8), which equalizes the expected minimum bucket cardinality E[Y], and then develops binary-search algorithms for w_l, a price-of-fairness analysis, and experiments on real and synthetic datasets.","tokens_in":24975,"tokens_out":6755,"duration_ms":61531,"significance":"The d=1 analysis is correct, and the accompanying price-of-fairness calculation for d=1 is a clean, parameter-free derivation against a standard Count-Min baseline. The paper also provides reproducible code and extensive experiments. However, the central advertised contribution—the d>1 fairness guarantee—is not derived. The manuscript explicitly substitutes a different quantity, E[Y], for the quantity in Definition 2, E[α], and the two are not equivalent: E[α] depends on the joint distribution of frequencies across the d rows, while E[Y] depends only on bucket cardinalities. Since the general-d fairness guarantee is the main result of the paper, the central claim fails as stated.","major_comments":[{"comment":"The derivation changes the target from Definition 2, which requires equal E[α], to equality of E[Y], the expected minimum number of element types in a bucket. The text says, \"we simplify our analysis by equalizing the expected number of element types hashed into the minimum-size bucket.\" This is not a simplification of the same object: for d>1, α(e)=f(e)/min_i C_i(e), where C_i(e) is the total frequency in the bucket of e in row i, so E[α] depends on the frequency distribution and on the joint behavior of the d rows, not only on bucket cardinalities. Equality of E[Y] does not imply equality of E[α]. Concretely, take n_l=n_h=4, w_l=w_h=2, d=2, so Equation (8) holds by symmetry. Let group l have frequencies {1,1,1,1000} and group h have frequencies {100,100,100,100}. In every realization each h element has α≈0.5, while an l element has α near 0.001 when it shares a bucket with the 1000-frequency element in at least one of the two rows, which occurs with probability 3/4. Hence E[α_l] and E[α_h] differ even though Equation (8) is satisfied. The abstract's and Section 1's claim that FCM is provably fair is therefore not established for d>1 and is false as stated.","section":"Section 3.2, Equation (8)"},{"comment":"The allocation algorithms in Section 4 binary-search for w_l that solves Equation (8), and the validation experiment in Section 6.8 compares the Monte Carlo allocation to the value from Equation (8). Since Equation (8) equalizes E[Y] rather than E[α], these components do not produce or validate a sketch that satisfies Definition 2. The Monte Carlo experiment even reports that the computed w_l is independent of the frequency distribution, which is consistent with the fact that the target is a bucket-cardinality quantity, not an approximation-factor quantity. The unfairness experiments in Section 6.5 measure E[α_l]−E[α_h] and show near-zero values for FCM on the tested instances, but those are empirical observations on particular datasets and frequency distributions; they cannot rescue the general theorem, and the toy counterexample in the previous comment shows that the approach does not provide a worst-case or distribution-free guarantee.","section":"Sections 4 and 6.8"},{"comment":"Theorem 1 is proved only for d=1, yet the abstract and the contribution list state without qualification that FCM \"theoretically proves that FCM is fair, i.e., it ensures an equal expected approximation factor across groups.\" The only formal result in the paper is the d=1 case; the d>1 case is asserted through the Section 3.2 simplification, which, as noted, targets a different quantity. This mismatch is not merely presentational: it obscures the absence of a proof for the general case. If the intended contribution is restricted to d=1, the paper must say so explicitly; if the intended contribution includes d>1, a proof connecting Equation (8) to Definition 2 is required.","section":"Section 3.1, Theorem 1, and the contributions list"}],"minor_comments":[{"comment":"The text states \"we cannot directly compute PoF = L_CM - L_FCM,\" but Equation (12) defines PoF = L_FCM - L_CM; the signs in the two places are inconsistent.","section":"Section 5.2"},{"comment":"The definition of multi-group unfairness says \"the difference between the maximum and minimum mean approximation factors across all groups,\" but the displayed expression is min - max; the order should be max - min.","section":"Section 6.5"},{"comment":"The caption ends with \"d=5 2,\" which appears to be a typographical artifact; it should be simply \"d=5.\"","section":"Figure 15 caption"},{"comment":"The claim that FCM is \"the first frequency estimation sketch with provable multiplicative error guarantees\" is not supported by the cited literature and is stronger than what is proved; the guarantee is equality of expected approximation factors, not a bounded multiplicative error guarantee in the usual sense.","section":"Section 1"}],"recommendation":"reject","confidential_remarks":"The stress-test counterexample in the reader's report is valid and reflects a genuine, load-bearing gap: the d>1 fairness guarantee is the core advertised result, and the proposed mechanism of equalizing E[Y] cannot be patched locally because Definition 2 requires frequency-dependent behavior that Equation (8) does not capture. A d=1-only version would be a substantially smaller paper, and even then the stated contribution would need to be re-scoped. I have no concerns about attribution or novelty, and the d=1 analysis is a solid piece of work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the d=1 part is genuinely good, and the rest of the paper's headline claim is unsupported. The proof for d>1 equalizes the expected minimum bucket size (Equation 8), but Definition 2 requires equal expected approximation factors. Those are different quantities, and the paper's own Section 3.2 calls the move a simplification without ever justifying it. A toy example with n_l=n_h=4, w_l=w_h=2, d=2 shows Equation (8) holds while the groups' expected approximation factors differ substantially. So the theorem FCM is fair for d>1 is false as stated, unless the missing link between E[Y] and E[alpha] is supplied. What is actually new and correct: the group-fairness definition for frequency estimation, the column-partitioning construction with group-aware semi-uniform hashing, and the d=1 proportional allocation rule w_l = (n_l/n)w. That d=1 derivation is clean and parameter-free. The negative price-of-fairness result for d=1 under random hashing is a nice, counterintuitive observation and is proven correctly. The bucket-allocation algorithm and its near-linear time analysis are reasonable, and the experiments do show that FCM empirically maintains near-zero unfairness in the settings tested. The soft spots are proportional to the claim. The abstract and contributions say theoretically prove and provable multiplicative error guarantees, which overstates what is delivered for d>1. Table 1 shows that for d=5, FCM's total additive error can be 30-47% higher than CM in some settings—that is not minimal additional error in any ordinary sense. Experiments also report means over five runs without error bars, and Figure 25 validates Equation (8), not Definition 2. The citation pattern is fine; the self-citation to the authors' Fairhash is relevant and not a problem. Who gets value: someone working on fairness in data structures will want the d=1 result and the empirical surface, but they should not cite this as a proof for d>1. I'd send it to peer review, not desk reject, because the flaw is specific and fixable: either prove a bound on the expected approximation factor directly, or honestly reframe FCM as a heuristic with empirical support. The current version should not be accepted as-is.","headline":"The d=1 analysis is correct and worth keeping, but the paper's central d>1 fairness theorem is not proven—it equalizes the wrong quantity.","tokens_in":715,"tokens_out":903,"would_cite":false,"duration_ms":45019,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fair-Count-Min, a sketch for streaming frequency estimation, claims to guarantee equal expected approximation factors across element groups while using the same memory and time as Count-Min.","keywords":["frequency estimation","Count-Min sketch","group fairness","approximation factor","streaming data","semi-uniform hashing","price of fairness","column partitioning"],"falsifier":"Compute, for a synthetic stream with two frequency groups and $d>1$, the $w_l$ solving Equation 8, then directly measure the empirical mean approximation factor $\\hat\\alpha_l$ and $\\hat\\alpha_h$. If the means differ by more than sampling noise while the expected minimum bucket sizes are equal, the fairness claim for $d>1$ is falsified.","tokens_in":24383,"feed_emoji":"⚖️","tokens_out":5257,"duration_ms":47427,"temperature":0.7,"pith_summary":"The paper introduces Fair-Count-Min (FCM), a frequency-estimation sketch meant to fix a fairness gap in the classic Count-Min (CM) sketch: CM's additive error hits low-frequency elements proportionally harder than popular ones. FCM partitions the sketch's columns among element groups with group-aware semi-uniform hashing, so elements from different groups never collide. The central claim is that by choosing each group's column count according to an equation that equalizes the expected minimum bucket size across groups, FCM ensures equal expected approximation factors (true frequency over estimated frequency) for every group. The paper also analyzes the price of fairness, proving it is negative for a single hash row and experimentally small for more rows, and gives near-linear-time algorithms for computing the column allocation. If correct, FCM would deliver group-fair multiplicative error guarantees at the same memory and time cost as standard CM.","feed_headline":"Sketch equalizes overcounting across element groups","feed_subtitle":"Fair-Count-Min matches Count-Min's speed and memory while promising equal expected error ratios per group.","key_machinery":"The central mechanism is column partitioning with group-aware semi-uniform hashing: each element group is confined to its own contiguous block of columns, so collisions only occur within a group. The load-bearing identity is the formula for the expected minimum bucket size across $d$ independent rows, $E[Y]=\\sum_{x\\ge1}\\Pr(X\\ge x)^d$ where $X$ is the number of element types hashed into a bucket, and the fairness condition for $d>1$ is obtained by equating this quantity across groups (Equation 8). For $d=1$, the identity reduces to the closed form $E[\\alpha_l]=w_l/n_l$, which yields the proportional-allocation rule $w_l = (n_l/n)w$.","core_discovery":"The paper claims that fairness in frequency-estimation sketches can be achieved by eliminating inter-group collisions rather than by inflating the sketch. For one hash function, allocating each group a number of columns proportional to its share of element types makes the expected approximation factor equal to $w_l/n_l = w/n$ for every group, and hence identical across groups. For $d>1$ hash rows, the paper derives the expected minimum bucket size $E[Y]$ for a group as $\\sum_{x=1}^{n_l} \\Pr(X\\ge x)^d$ with $X\\sim \\mathrm{Bin}(n_l, 1/w_l)$, and claims that solving the equality of these quantities between groups (Equation 8) yields a column allocation that makes the expected approximation factors equal. The paper further states that FCM is the first sketch with provable multiplicative (rather than additive) error guarantees, that the price of fairness is negative for $d=1$ under random hashing and zero under uniform hashing, and that experiments confirm fairness with negligible additional error.","pith_inferences":["The equivalence between equal expected minimum bucket size and equal expected approximation factor is assumed rather than proven for $d>1$; a direct derivation of $E[\\alpha]$ in terms of bucket-size distributions would settle whether the column allocation from Equation 8 actually equalizes the target quantity.","The Monte Carlo validation in the paper only checks that the column allocation matches the theoretical $w_l$ values, not that the resulting approximation factors are equal; an experiment reporting per-group empirical $E[\\alpha]$ for the solved $w_l$ would be a direct test of the fairness guarantee.","FCM's guarantee is about expectations; worst-case or high-probability fairness bounds for individual elements could be a natural next step if the expectation-level claim holds.","Because the grouping is arbitrary, the same construction could be used to enforce fairness across any protected attribute, with the price of fairness then depending on how unevenly element types are distributed across groups."],"forward_implications":["If FCM works as claimed, frequency-estimation sketches can report multiplicative error guarantees instead of additive ones, making estimates for rare items as trustworthy as those for common items.","The same memory and time complexity as Count-Min means fairness comes without a performance penalty in construction or query cost.","A negative price of fairness for one-row sketches means separating groups can improve total additive error by reducing bucket-size variance.","The column-allocation equation offers exact and approximate near-linear-time algorithms for arbitrary numbers of groups.","The technique applies to any grouping strategy, including demographic attributes and frequency-based partitions, not just binary splits."],"supporting_citations":[{"why":"Defines the Count-Min sketch and its additive error guarantees, the baseline FCM must match.","marker":"[26, 27]"},{"why":"Supplies the expected additive error calculation used for the price-of-fairness analysis.","marker":"[28]"},{"why":"Provides the identity $E[Y]=\\sum_{x\\ge1} P(Y\\ge x)$ used to derive the expected minimum bucket size.","marker":"[38]"},{"why":"Introduces the price-of-fairness concept used to quantify FCM's cost relative to CM.","marker":"[14]"},{"why":"Gives the occupancy/balls-into-bins background explaining why random hashing creates bucket-size variance and why FCM's negative price of fairness for $d=1$ is plausible.","marker":"[57]"}],"fun_headline_variants":["Fair sketch: equal error per group, less overcount","Column allocation equalizes group error ratios","Eliminate inter-group collisions for fair counts","First provable multiplicative error guarantee in sketches","Fair-Count-Min: zero extra memory, fair approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes, for multiple hash rows, that making the average smallest bucket size the same for every group also makes the average ratio of true to estimated frequency the same, but does not prove that the two are connected.","fun_headline_variants_meta":{"raw":{"variants":["Fair sketch: equal error per group, less overcount","Column allocation equalizes group error ratios","Eliminate inter-group collisions for fair counts","First provable multiplicative error guarantee in sketches","Fair-Count-Min: zero extra memory, fair approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1328,"prompt_tokens":880,"completion_tokens":448,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":496,"completion_tokens_details":{"reasoning_tokens":375}},"tokens_in":496,"tokens_out":448,"duration_ms":4071,"temperature":1.0,"reasoning_tokens":375,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:24:05.561878+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for a synthetic stream with two frequency groups and $d>1$, the $w_l$ solving Equation 8, then directly measure the empirical mean approximation factor $\\hat\\alpha_l$ and $\\hat\\alpha_h$. If the means differ by more than sampling noise while the expected minimum bucket sizes are equal, the fairness claim for $d>1$ is falsified.","supporting_citations":[{"cited_title":"2020.Small summaries for big data","cited_arxiv_id":null,"evidence_quote":"Supplies the expected additive error calculation used for the price-of-fairness analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the occupancy/balls-into-bins background explaining why random hashing creates bucket-size variance and why FCM's negative price of fairness for $d=1$ is plausible."}],"review_version":1}