{"id":"dc3fc384-685d-4b58-9352-d91deb756103","arxiv_id":"1908.05198","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under Zipfian frequencies, Count-Min's expected error is Θ(k log(kn/B)/B), Count-Sketch gets its first nearly tight bounds, and learned Count-Sketch achieves Θ(1/B).","lead":"This paper gives tight mathematical bounds on the average error of Count-Min and Count-Sketch frequency estimators when data follows a Zipfian distribution, and it shows learned variants improve on them. It also finds that the number of hash functions should be a small constant, not the usual logarithmic choice, to minimize expected error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.4's Count-Sketch lower bound rests on an interval-occupancy arithmetic error; the corrected count gives only O(√log k/√k), too weak for the median argument, so the k>1 lower-bound claim is unproven as written.","rationale":"The Count-Min analysis (Theorem 3.1) and the one-row Count-Sketch analysis (Theorem 4.3) are internally consistent: the Bennett/Chernoff steps check out and the lower bound for CM depends only on standard concentration. The learned-CS upper bounds (Theorem 5.1, Corollary 5.2, Theorem 5.7) also follow from Jensen and second-moment estimates. The only place where a displayed calculation fails is the interval-occupancy count in Theorem 4.4. This is genuinely load-bearing because without a valid lower bound for k>1 standard Count-Sketch, the paper's advertised improvement of learned over standard CS for k>1 and the optimality of constant k for CS are not established. The reader's conditional verdict is appropriate: the defect is local and plausibly fixable (e.g., by a Littlewood–Offord argument on scaled coefficients), but as written the proof has a gap. I therefore leave the verdict unchanged. I do not see a reason to escalate to REJECT: the core Count-Min results and the k=1 CS results are supported, and the lower-bound gap is confined to one lemma in Section 4.2.","tokens_in":26054,"tokens_out":17823,"duration_ms":174487,"concrete_test":"Recompute the interval-occupancy count in Section 4.2 exactly: replace 'B log k/√k + 1' by 'B (log k)^{3/2}/√k + 1', then re-evaluate Eq. (6) and the subsequent Stirling estimate. If the anti-concentration bound becomes O(√(log k)/√k), the binomial tail at k/2 is k^{−Ω(1)}, so the theorem is not proven as written. To settle whether the claim is nonetheless true, independently re-derive an anti-concentration bound for S1 = ∑_{j∈J} ε_j/j using the Erdős–Littlewood–Offord lemma with coefficients scaled by B log k (so every |a_j| ≥ 1 and the target interval has scaled length √(log k)/√k ≤ 1); a successful derivation gives Pr[S1∈I] = O(1/√k) and restores the lower bound. Check whether this derivation goes through without additional assumptions; if it does not, the lower-bound row for k>1 Count-Sketch should be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4.4's lower bound (Section 4.2) is the load-bearing point: it is the only argument supporting the k>1 Count-Sketch lower bounds in Table 1, which in turn justify the claim that a constant k>1 minimizes expected error and that learned Count-Sketch beats standard Count-Sketch for k>1. The step in question bounds the probability that S lies in an interval of length 1/(B√(k log k)). The proof says the number of possible values of the last sampled item that can put S in this interval is at most (1/(B√(k log k)))·(B log k)^2 + 1 = B log k/√k + 1. The arithmetic is wrong: (B log k)^2/(B√(k log k)) = B (log k)^{3/2}/√k. With the correct value, the conditional bound Pr[S∈I | |J|=r] ≤ 3/√k becomes O(√(log k)/√k), and Eq. (6) yields Pr[S∈I] = O(√(log k)/√k). Substituting this into the Stirling step gives a binomial tail probability exp(−Ω(log k)) = k^{−Ω(1)} for the event that at least half of the k counters exceed the threshold, not Ω(1). The median argument therefore does not establish E[|f̃_i−s(i)f_i|] = Ω(1/(B√(k log k))) as written. Since no other proof of the k>1 Count-Sketch lower bound is supplied, the corresponding entry in Table 1 is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper analyzes the expected frequency-estimation error of Count-Min, Count-Sketch, and their learning-augmented variants under a Zipfian frequency distribution. The authors prove a tight bound of Θ(k log(kn/B)/B) for Count-Min with k rows and total B buckets, resolving a gap left by Hsu et al. (ICLR 2019). For Count-Sketch they provide the first such bounds: Θ(log B/B) for one row, and for odd k≥3 an upper bound O(√k/B) together with a claimed lower bound Ω(√k/(B log k)) after translating to the total-bucket formulation. They also analyze learned Count-Sketch with a perfect or noisy heavy-hitter oracle, and conclude that for minimizing expected error the number of hash rows should be a constant greater than 1, contrary to the common Θ(log n) choice. The paper includes experiments on synthetic Zipfian data that qualitatively support the main asymptotic statements.","tokens_in":26380,"tokens_out":17872,"duration_ms":175617,"significance":"If all bounds hold, this is a substantial contribution: the Count-Min bound is tight and short, the Count-Sketch analysis is the first for Zipfians, and the practical suggestion to use a small constant number of rows is actionable and well motivated. The proofs are self-contained and use standard concentration tools, and the experiments complement the asymptotics. However, the k>1 Count-Sketch lower bound, which is a load-bearing part of Table 1 and of the optimality claim for CS, rests on an arithmetic error that invalidates the proof as written. The CM upper/lower bounds and the k=1 CS bounds appear sound.","major_comments":[{"comment":"The displayed interval-occupancy count contains an arithmetic error. The proof states that an interval of length 1/(B√(k log k)) contains at most (1/(B√(k log k)))·(B log k)^2 + 1 = B log k/√k + 1 values from {1/j : j∈[B log k]}, but the correct product is B (log k)^{3/2}/√k. Consequently the bound Pr[S∈I | |J|=r] ≤ 3/√k is not obtained; the ratio is O(√(log k)/√k). Substituting this into Eq. (6) gives Pr[S∈I] = O(√(log k)/√k), so p0 = 1/2 − O(√(log k)/√k). The subsequent Stirling/binomial argument then yields only k^{−Ω(1)} for the probability that at least half of the k counters exceed the threshold, not the required Ω(1). Thus the lower bound E[|f̃_i − s(i)f_i|] = Ω(1/(B√(k log k))) is not established as written.","section":"Section 4.2, proof of Theorem 4.4 (lower bound)"},{"comment":"Because the proof of Theorem 4.4's lower bound fails, the k>1 Count-Sketch lower-bound entry Ω(k^{1/2}/(B log k)) in Table 1 is unsupported, and with it the claims that the CS bounds are nearly tight and that a constant number k>1 is optimal for expected CS error. These claims are central to the paper's advertised contributions. The authors should either repair the lower bound with a different anti-concentration argument (for example, one exploiting the variance scale Var[S]≈1/B^2) or state and prove a weaker lower bound that is actually established and adjust the conclusions accordingly.","section":"Table 1 and Section 4, downstream claims"}],"minor_comments":[{"comment":"The sentence 'Setting B1 = Bh = Θ(B) and B2 = B−B2 = Θ(B)' contains a typo; it should read B2 = B−B1 = Θ(B).","section":"Section 5.2, before Theorem 5.5"},{"comment":"The notation X^(ℓ) is used in the final paragraph of the lower-bound proof without being redefined in that context; the reader must infer it from the upper-bound part of the proof. Please define it explicitly.","section":"Section 4.2, lower-bound proof"},{"comment":"The interval I is described as centered at s_ℓ(i)f_i, but the anti-concentration step that yields p0 = 1/2 − O(1/√k) requires a bound on the probability that the noise lies in an interval centered at 0. The argument is insensitive to the center, so the proof can be repaired by rewording, but as written it is confusing.","section":"Section 4.2, lower-bound proof"},{"comment":"The choice N1 = [2B2]\\[B2] is transparent only when B1 = B2; since the theorem allows B2 ≥ B1, the proof should explicitly state why this choice captures the relevant non-heavy items and how the case B2 > B1 is handled.","section":"Theorem 5.5, proof"}],"recommendation":"major_revision","confidential_remarks":"The core difficulty is isolated to the k>1 Count-Sketch lower bound. The Count-Min bounds and the k=1 Count-Sketch bounds appear correct, and the paper is otherwise well written. I would encourage the authors to attempt a fix via a direct estimate of the characteristic function or a Berry-Esseen-type argument; such a repair would likely be publishable. I do not think rejection is warranted, but the current proof gap must be closed before the claims in Table 1 can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. Two things to know. First, the tight Count-Min bound and the Count-Sketch upper bounds are real results and worth knowing. Second, the k>1 Count-Sketch lower bound in Theorem 4.4 has an arithmetic error in the anti-concentration step, and as written that lower bound does not go through.\n\nThe Count-Min analysis is the strongest part. Theorem 3.1 gives E[|f_i - \\hat f_i|] = Theta(k log(kn/B)/B) for k>=2, and the proof is short and convincing. The heavy-head contribution is handled by a union bound plus Bennett, the tail by Bennett alone, and the constants are tracked. This resolves the open gap left by Hsu et al. and supports the practical advice that a constant k minimizes expected error. The k=1 Count-Sketch bound (Theorem 4.3) and the learned variants for k=1 (Theorems 5.1 and 5.7) also look right; the noisy-oracle interpolation is a nice touch. The paper is self-contained and does not lean on the authors' prior work beyond what it is improving.\n\nSoft spot: Theorem 4.4's lower bound. The proof bounds Pr[S in I] by counting how many values from {1/j : 1<=j<=B log k} can fall in an interval of length 1/(B sqrt(k log k)). The text says the count is at most B log k / sqrt(k) + 1. The arithmetic gives (B log k)^2 / (B sqrt(k log k)) = B (log k)^{3/2} / sqrt(k), a sqrt(log k) factor larger. With the corrected count the conditional probability becomes O(sqrt(log k)/sqrt(k)), and the final Stirling step gives only k^{-Omega(1)} for the median event, not Omega(1). So the claimed Omega(1/(B sqrt(k log k))) lower bound is not established as written. That is the only argument for the k>1 Count-Sketch lower bound in Table 1, so that entry is unsupported. The gap looks fixable—maybe a sharper anti-concentration estimate or a weaker but still meaningful lower bound—but it needs real work.\n\nBottom line: the paper deserves a serious referee. The wrong outcome would be a desk reject; the right outcome is a major revision that repairs or restates Theorem 4.4. The Count-Min results and the k=1 results are solid enough to cite even before that repair.","headline":"Tight Count-Min analysis and new Count-Sketch upper bounds are real contributions, but the k>1 Count-Sketch lower bound rests on a fixable arithmetic error that currently leaves that part of Table 1 unsupported.","tokens_in":26930,"tokens_out":2943,"would_cite":true,"duration_ms":28283,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes tight expected-error bounds for Count-Min and Count-Sketch under Zipfian frequencies, showing that learned variants improve by a factor $\\Theta(\\log n / \\log(n/B))$.","keywords":["Zipfian distribution","Count-Min","Count-Sketch","learned frequency estimation","streaming algorithms","expected error","heavy hitter oracle","randomized hashing"],"falsifier":"Recompute the count in Section 4.2: among $\\{1/j : 1 \\le j \\le B \\log k\\}$, how many values lie in an interval of length $1/(B\\sqrt{k \\log k})$? If the count is $\\Theta(B(\\log k)^{3/2}/\\sqrt{k})$ rather than the claimed $\\Theta(B \\log k/\\sqrt{k})$, then the anti-concentration probability in the proof is only $O(\\sqrt{\\log k}/\\sqrt{k})$, and the $\\Omega(\\sqrt{k}/(B \\log k))$ lower bound is not established by that argument. A direct simulation of Count-Sketch with $k = 3, 5, 7$ rows on Zipfian data can also compare empirical expected error against the claimed $\\Theta(\\sqrt{k}/B)$ upper and $\\Omega(\\sqrt{k}/(B \\log k))$ lower bounds.","tokens_in":25829,"feed_emoji":"📊","tokens_out":15706,"duration_ms":151021,"temperature":0.7,"pith_summary":"The paper establishes tight bounds for the expected error of Count-Min and Count-Sketch when frequencies follow Zipf's law, $f_i \\propto 1/i$, and items are queried roughly in proportion to their frequency. With $k$ hash rows and $B$ total buckets, Count-Min has expected error $\\Theta(k \\log(kn/B)/B)$ for $k \\ge 2$; Count-Sketch has expected error $\\Theta(\\log B/B)$ for $k = 1$ and, for odd $k \\ge 3$, an error between $\\Omega(\\sqrt{k}/(B \\log k))$ and $O(\\sqrt{k}/B)$. The paper also analyzes learned variants that set aside buckets for predicted heavy items, proving that learned Count-Sketch with a perfect heavy-hitter oracle attains $\\Theta(\\log(n/B)/(B \\log n))$ and degrades gracefully as the oracle's probability of misclassification grows. The practical conclusion, if the bounds hold, is that the customary $\\Theta(\\log n)$ hash rows are wasteful for expected error: a constant $k > 1$ (two for Count-Min, three for Count-Sketch) is asymptotically optimal, and learned sketches beat their classic counterparts by a factor of $\\Theta(\\log n / \\log(n/B))$.","feed_headline":"Constant rows beat log n rows in Zipfian frequency sketches","feed_subtitle":"Tight expected-error bounds for Count-Min and Count-Sketch also pin down the learned-sketch gain.","key_machinery":"The mechanism that carries the Count-Sketch results is the random counter $S = \\sum_{j=1}^n f_j \\eta_j \\sigma_j$, with $\\eta_j$ a Bernoulli indicating a hash collision with the queried item and $\\sigma_j$ an independent $\\pm 1$ sign; Count-Sketch's estimate is the median of $k$ independent copies of $S$. The paper's main technical contribution is an anti-concentration analysis of $S$ inside a small interval around zero: an upper bound on $\\Pr[S \\in I]$ for a short interval $I$ drives the Count-Sketch lower bound, while a lower bound of $\\Omega(tB)$ on $\\Pr[S \\in [-t,t]]$ for $t \\le 1/(2B)$ drives the upper bound through a binomial/median argument. For Count-Min, the carry is a head/tail split of the Zipfian frequencies: items in $[B]$ contribute $O(1/B)$ to the error once there are at least two rows, and the tail $[n]\\setminus[B]$ contributes $\\Theta(\\log(n/B)/B)$, with variance-based concentration inequalities giving the matching lower bound. The learned variants add a heavy-hitter oracle that removes the $B_h$ heaviest items from the hashed sketch, which is why their error is determined by the lighter tail and why a single row is then optimal.","core_discovery":"On the paper's own terms, the central discovery is that under a Zipfian frequency vector $f_i = 1/i$, the expected estimation error is controlled by a clean split between the heavy head of the distribution and its light tail. For Count-Min, the light tail contributes $\\Theta(\\log(n/B)/B)$ regardless of $k$, while the heavy head contributes $O(1/B)$ once $k \\ge 2$, yielding the tight bound $\\Theta(k \\log(kn/B)/B)$ when the $B$ total buckets are distributed over $k$ tables. For Count-Sketch, the paper studies the distribution of the counter $S = \\sum_{j \\ne i} f_j \\eta_j \\sigma_j$, where $\\eta_j$ indicates whether $j$ collides with the queried item and $\\sigma_j$ is a random sign; the median of $k$ independent copies of $S$ has expected deviation $\\Theta(\\log B/B)$ for $k = 1$ and, for odd $k \\ge 3$, lies between $\\Omega(\\sqrt{k}/(B \\log k))$ and $O(\\sqrt{k}/B)$. The learned-Count-Sketch analysis shows that a perfect heavy-hitter oracle, which gives dedicated buckets to the $B_h$ heaviest items, reduces the per-item error to $\\Theta(1/B)$ and the frequency-weighted error to $\\Theta(\\log(n/B)/(B \\log n))$; with an oracle that misclassifies each item with probability $\\delta$, the bound degrades smoothly and matches classic Count-Sketch when $\\delta = 1$, while retaining the idealized bound for $\\delta = O(1/\\log B)$. Together these results imply that a constant number of rows, rather than $\\Theta(\\log n)$, minimizes expected error under Zipfian data.","pith_inferences":["One could use the asymptotic formula to build a simple parameter rule: $k = 2$ for Count-Min and $k = 3$ for Count-Sketch on Zipf-like production workloads, switching to $\\Theta(\\log n)$ rows only when worst-case per-item guarantees (rather than expected error) are required.","The same head/tail split and anti-concentration approach should extend to other heavy-tailed distributions, such as Pareto or log-normal; verifying whether the $\\Theta(\\log n / \\log(n/B))$ learned gap persists would be a direct next experiment.","The noisy-oracle trade-off suggests an adaptive design the paper does not describe: estimate the oracle's error $\\delta$ online and disable the learned routing when $\\delta$ exceeds $O(1/\\log B)$, since the theoretical advantage over classic Count-Sketch then disappears.","The appendix's generalized-Zipf results for Count-Min (learning helps only when $\\alpha > 1$) point to a possible phase transition for learned Count-Sketch as well, which the paper leaves open."],"forward_implications":["With Zipfian frequencies and total budget $B$, Count-Min should be run with $k = 2$ (or another small constant): the expected error is $\\Theta(\\log(n/B)/B)$, whereas $k = \\Theta(\\log n)$ pushes it to roughly $\\Theta(\\log^2 n/B)$.","For Count-Sketch with odd $k$, $k = 3$ is asymptotically near-optimal, since the error is always $O(\\sqrt{k}/B)$ and never better than $\\Omega(\\sqrt{k}/(B \\log k))$ for $k \\ge 3$.","Learned Count-Sketch with one row and a perfect heavy-hitter oracle attains $\\Theta(\\log(n/B)/(B \\log n))$, which is the best of the variants analyzed and is a $\\Theta(\\log n / \\log(n/B))$ improvement over classic Count-Sketch.","The learned advantage is not brittle: it survives an oracle that misclassifies each item with probability up to $O(1/\\log B)$, and degrades to the classic sketch only as $\\delta$ approaches 1.","Because the per-item error bounds are proved uniformly, the same expected-error order applies under any query distribution, not just the frequency-proportional one assumed in the main text."],"supporting_citations":[{"why":"Defines the learning-augmented Count-Min/Count-Sketch framework, sets the Zipfian model, and supplies the previous non-tight Count-Min bounds and open problems this paper resolves.","marker":"[HIKV19]"},{"why":"Introduces Count-Min, the algorithm whose tight expected-error bound under Zipfians is the paper's first main result.","marker":"[CM05a]"},{"why":"Introduces Count-Sketch and the median-of-counters estimator analyzed in the new Count-Sketch bounds.","marker":"[CCFC02]"},{"why":"Supplies the anti-concentration lemma used to lower-bound the probability that a single Count-Sketch counter falls inside a small interval.","marker":"[MP14]"},{"why":"Bennett's inequality supplies the tail bounds used in the Count-Min lower bound and in bounding large deviations of Count-Sketch counters.","marker":"[Ben62]"},{"why":"The Chernoff bound controls the number of hash collisions in the Count-Sketch lower-bound argument.","marker":"[Che52]"},{"why":"Hoeffding's inequality shows that once individual counters escape a small interval, the median concentrates enough for the Count-Sketch upper bound.","marker":"[Hoe63]"},{"why":"The Littlewood-Offord lemma bounds the probability that a learned Count-Sketch counter lands in a short interval, giving the lower bound for $k \\ge 3$.","marker":"[LO39]"},{"why":"Erdős's strengthening of the Littlewood-Offord lemma is the version invoked in the learned Count-Sketch lower bound.","marker":"[Erd45]"}],"fun_headline_variants":["Tight error bounds for Count-Min and Count-Sketch under Zipfian","Constant rows minimize expected error in Zipfian frequency sketches","Learned sketches get first Zipfian error bounds, matching Count-Min","Why constant rows beat log n rows for expected sketch error","Zipfian analysis pins down optimal rows for Count-Min and Count-Sketch"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis assumes exact Zipfian frequencies $f_i \\propto 1/i$ and a query distribution aligned with them; separately, the Count-Sketch lower bound for $k > 1$ rests on a density count of the values $1/j$ inside an interval of length $1/(B\\sqrt{k \\log k})$, where the proof's displayed arithmetic appears to undercount by a $\\sqrt{\\log k}$ factor.","fun_headline_variants_meta":{"raw":{"variants":["Tight error bounds for Count-Min and Count-Sketch under Zipfian","Constant rows minimize expected error in Zipfian frequency sketches","Learned sketches get first Zipfian error bounds, matching Count-Min","Why constant rows beat log n rows for expected sketch error","Zipfian analysis pins down optimal rows for Count-Min and Count-Sketch"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000862,"raw_usage":{"total_tokens":3894,"prompt_tokens":1251,"completion_tokens":2643,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":867,"completion_tokens_details":{"reasoning_tokens":2546}},"tokens_in":867,"tokens_out":2643,"duration_ms":17337,"temperature":1.0,"reasoning_tokens":2546,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:23:54.229895+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the count in Section 4.2: among $\\{1/j : 1 \\le j \\le B \\log k\\}$, how many values lie in an interval of length $1/(B\\sqrt{k \\log k})$? If the count is $\\Theta(B(\\log k)^{3/2}/\\sqrt{k})$ rather than the claimed $\\Theta(B \\log k/\\sqrt{k})$, then the anti-concentration probability in the proof is only $O(\\sqrt{\\log k}/\\sqrt{k})$, and the $\\Omega(\\sqrt{k}/(B \\log k))$ lower bound is not established by that argument. A direct simulation of Count-Sketch with $k = 3, 5, 7$ rows on Zipfian data can also compare empirical expected error against the claimed $\\Theta(\\sqrt{k}/B)$ upper and $\\Omega(\\sqrt{k}/(B \\log k))$ lower bounds.","supporting_citations":[],"review_version":1}