{"id":"441a8494-b4eb-4cc5-8867-fc0010cb1e70","arxiv_id":"2502.05723","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A fine-grained per-key analysis lets bottom-k cardinality sketches answer many adaptive queries when each key appears in few of them, shifting the quadratic barrier from total query count to per-key participation.","lead":"The paper designs a version of the bottom-k MinHash cardinality sketch that stays accurate under far more adaptively chosen queries than previously possible, as long as no single data element appears in too many of the queries. This shifts the robustness bottleneck from the total number of queries to how often each key is reused, which is usually much smaller in real workloads.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's 'exponential number of adaptive queries' with per-key r=Θ~(k²) is not supported by Theorem 4.1: the stated k=O(α^{-2}√r log^{3/2}(n/β)) forces log n to be constant when r≈k², so the guaranteed regime is only subexponential.","rationale":"The reader's formal weakest_assumption was the full-independence condition on the priority vector, which is a real limitation of the ADA reduction and is acknowledged only in a footnote. However, the reader's rationale also flagged the query-count overclaim: Theorem 4.1 does not support 'exponential' queries when r=Θ(k²). I agree that this overclaim is the more load-bearing issue for the paper's central advertised message, because it concerns the internal consistency between the abstract/Section 1.3 and the formal theorem, rather than a standard modeling assumption shared by much of the sketching literature. The second concern I examined—the apparent 2Tnδ term in Lemma 3.1's proof—appears to be a fixable accounting issue (choosing δ proportional to β/(mn) restores the claimed bound without changing the asymptotics), so it is less load-bearing. The exponential overclaim is not a fatal flaw to the main technique: the per-key guarantee still yields subexponential total queries, which already breaks the quadratic barrier. Therefore the appropriate verdict remains CONDITIONAL, with the same required revisions as the reader identified: correct the informal query-count statement, fix the r=Ω~ typo, state the full-randomness assumption more prominently, and report experimental variance.","tokens_in":18448,"tokens_out":33091,"duration_ms":352787,"concrete_test":"Perform the parameter check: fix α=0.1, β=0.01, n=2^k, and r=k². Substitute into Theorem 4.1's bound k = O(α^{-2}√r log^{3/2}(n/β)): the right-hand side is approximately C·100·k·(k log 2)^{3/2} = 100C k^{5/2}, which exceeds k for every large k, so no constant C satisfies the theorem. Also, the theorem's condition r ≫ log(n/β) requires r ≥ Ω(k), while the inverted bound requires r ≤ O(α⁴/k), a contradiction. This algebraically settles that the exponential-query claim with r=Θ~(k²) is not supported by the formal theorem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline claim in the abstract and Section 1.3 is that the construction handles an exponential number of adaptive queries provided each key participates in r=O~(k²) queries. Theorem 4.1 states that the sketch size must satisfy k = O(α^{-2}√r log^{3/2}(n/β)). Substituting r = c k² α⁴ into this bound gives k = O(c^{1/2} k log^{3/2}(n/β)), which can hold only if log(n/β) is bounded by a constant depending on the hidden constant in the O. With n bounded by a constant, the per-key condition implies total queries t ≤ n r = O(k²), so the quadratic barrier is not actually surpassed in this advertised regime. If one instead wants t to be exponential in k, one needs log n = Ω(k); then the theorem's inequality forces r = O(k²α⁴/log³n) = O(α⁴/k), while the theorem itself requires r ≫ log(n/β) = Ω(k). These requirements are incompatible. Solving the constraints more generally gives log n = O(α√k) and t = exp(O(α√k))·poly(k), which is subexponential, not exponential. The formal contribution—shifting the barrier from total queries to per-key participation—survives, but the abstract's specific 'exponential queries with r=O~(k²)' claim is not a consequence of Theorem 4.1 and should be corrected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses adaptive adversarial queries to composable cardinality sketches, where prior work established a 'quadratic barrier': roughly t = O~(k^2) adaptive queries can be answered by a sketch of size k, and universal O~(k^2)-query attacks exist. The authors propose shifting the barrier to a per-key parameter r: if every key participates in at most r of the query sketches, then a bottom-k MinHash sketch of size k = O(alpha^{-2} sqrt(r) log^{3/2}(n/beta)) answers every query with (1 +/- alpha)-accuracy with probability 1 - beta. To obtain this, they reformulate the robustness wrapper of Hassidim et al. in terms of adaptive data analysis (ADA) with fine-grained per-key generalization guarantees (Section 3), using per-unit privacy charging (Cohen-Lyu) and a DP generalization bound (Dwork et al.; Bassily et al.). Two estimators are analyzed: a stateless basic estimator (Section 4, Theorem 4.1) and a tracking estimator that deactivates overexposed keys (Section 5, Theorem 5.1) with smooth degradation in the fraction of deactivated keys. Experiments on synthetic Uniform and Pareto query workloads report 12x-100x gains over the per-query baseline.","tokens_in":18778,"tokens_out":55172,"duration_ms":504448,"significance":"The per-key-participation formulation is a genuinely useful conceptual step: in realistic workloads where a few heavy-hitter keys dominate, the total query count t can vastly exceed k^2 while r stays moderate, and the paper provides the first composable-sketches result with this kind of data-dependent guarantee. The fine-grained ADA framework (Lemma 3.1, Corollary 3.3) is clean and reusable, and the reduction from robust estimation to linear threshold queries over a product-distributed priority vector is elegant; the proofs are unusually explicit (Lemma 4.2, Propositions 4.4-4.5, Appendices B and C), with each step checkable. The experimental protocol is simple and reproducible. However, the advertised headline claim of handling an exponential number of adaptive queries does not follow from Theorem 4.1 (see major comment 1), and the proof chain contains two repairable gaps (major comments 2 and 3). The per-key barrier-shift idea survives these corrections in a weaker, subexponential form and warrants publication after substantial revision.","major_comments":[{"comment":"The claim that the construction can handle an exponential number of adaptive queries provided each key participates in at most r = O~(k^2) queries is not a consequence of Theorem 4.1; in the advertised parameter regime it is actually inconsistent with the theorem. Substituting r = c k^2 alpha^4 into k = O(alpha^{-2} sqrt(r) log^{3/2}(n/beta)) forces log(n/beta) to be bounded by a constant, so n = O(1) and the total number of queries satisfies t <= n r = O(k^2): the quadratic barrier for total queries is not surpassed at all in this regime. If instead one aims for t exponential in k, which requires log n = Omega(k), the theorem forces r = O(alpha^4 k^2 / log^3(n/beta)) = O(alpha^4 / k), contradicting the theorem's own requirement r >> log(n/beta) = Omega(k). Maximizing t <= n r subject to both constraints yields log(n/beta) = O(alpha sqrt(k)) and t = exp(O(alpha sqrt(k))) * poly(k), i.e., subexponential in k. The formal per-key contribution survives in this weaker form, but the abstract and Section 1.3 overstate it; they should be corrected to state the subexponential tradeoff actually proved, or Theorem 4.1 should be strengthened to support the stated claim.","section":"Abstract and Section 1.3"},{"comment":"The proof of Lemma 3.1 drops the approximate-DP term from Theorem 2.2. With the stated choices delta = beta/n^2 and T = 2m/beta, the additive term 2Tn*delta equals 4m/n, which is not bounded by the claimed O(log(m/beta)/alpha) under the lemma's hypotheses; in the application of Section 4.3, m is taken to be poly(n), making 4m/n = poly(n), far beyond the O(alpha^{-1} sqrt(r) log^{3/2}(n/beta)) budget that the choice of k must absorb. The gap is locally repairable: choose delta = beta/(2mn), giving 2Tn*delta = 2, and note that log(1/delta) = O(log(n/beta)) because m = poly(n) in the application, so the privacy parameter epsilon = sqrt(r log(1/delta)) * epsilon_0 remains within the required bound after readjusting constants. As written, the chain Lemma 3.1 -> Corollary 3.3 -> Theorem 4.1 is incomplete, and the proof of Theorem 4.1 does not go through without this fix.","section":"Section 3, proof of Lemma 3.1"},{"comment":"The sentence 'Observe that for any query sketch S, there is at most one positive test in Algorithm 3. Therefore, per assumption (1) on the input, each index appears in at most r positive tests' does not follow from condition (1) as stated. Condition (1) bounds the number of sketches containing key i, but in the simulation by Algorithm 1 the charges are incurred by all keys i in V_j with rho_i < tau (the full-set predicate h_{V,tau}), and a key can satisfy this without belonging to the sketch whenever the termination threshold tau exceeds the k-th smallest priority of V_j. The missing argument is that, with probability 1 - O(beta), the final tau of each query lies below that k-th order statistic; this follows from T = (1 - alpha)k, the alpha*k/8 noise bound, and the grid spacing, just as the analogous claim is proved for the tracking estimator in Claim C.2 of Appendix C. Once that holds, all charged keys are sketch keys and each key is charged at most r times. Without such an argument, the claim holds only under the stronger set-participation condition that the paper notes as sufficient; the theorem, whose assumption (1) is stated in terms of sketch participation, needs either the missing proof or a restated assumption.","section":"Section 4.3, simulation argument"}],"minor_comments":[{"comment":"The formal analysis requires fully independent priorities, i.e., a product distribution over the priority vector rho, because the ADA generalization argument (Lemma 3.1 via Theorem 2.2) is stated for product distributions; the footnote's acknowledgment that implementations use pseudo-random hash maps means the robustness guarantee of Theorem 4.1 is not established for the practical hash families used in implementations, and the abstract's practical framing outruns the theorem. The parenthetical claim that O(log k) bits of representation are sufficient is also unclear (a bottom-k sketch stores k priorities, and the seed for the priority map appears to need Omega(log n) bits) and should be clarified or removed.","section":"Section 4.1, footnote 4"},{"comment":"The displayed formula for epsilon_0 is typeset incorrectly in both algorithms: 'epsilon_0 <- alpha/8 4 sqrt(r log(n/(beta/4)))' should presumably read epsilon_0 = (alpha/8)/(4 sqrt(r log(n/(beta/4)))), matching the invocation of Lemma 3.1 with parameters (alpha/8, beta/4).","section":"Algorithms 3 and 4"},{"comment":"The hypothesis states r >> log(n/beta), but the proof uses r >> log(1/delta); with the corrected delta = beta/(2mn) from major comment 2, the clean hypothesis becomes r >> log(mn/beta). Since m = poly(n) in the application, these differ only by constants, but the statement and the proof should be made consistent.","section":"Section 3, Lemma 3.1"},{"comment":"The reported 12x-100x gains are point estimates on synthetic data with no variance information; since the stopping rules (10% deactivated threshold, 50% stop) are stochastic, reporting standard errors over a small number of seeds would strengthen the empirical claim.","section":"Section 6"},{"comment":"Small typo: 'This standard estimator is know to optimally use' should read 'is known to'. Also, the term 'stateless estimator' in Section 1.3 is slightly misleading because the estimator runs a per-query while loop; the intended meaning is that no state persists across queries, and this could be stated explicitly.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The three issues above are independent and should all be addressed in a revision. The abstract's 'exponential queries' wording is the most visible; if it is corrected to the subexponential tradeoff actually proved (t = exp(O(alpha sqrt(k))) when queries spread over a sufficiently large universe), the paper's contribution remains solid and novel. The delta-choice gap in Lemma 3.1 is a genuine proof error but is local: one line fixes it with delta = beta/(2mn), and the paper's constants accommodate it. The charge-count gap in Section 4.3 needs either a short geometric argument or a restated assumption. The reader's conditional overall assessment is reasonable; my soundness reading is slightly lower than 7.0 as written because of the Lemma 3.1 proof issue, but after the fixes the result should be sound. No citation concerns: the reliance on Cohen and Lyu (2023a) for the per-unit charging privacy theorem is appropriate, as that is a prior peer-reviewed result used as a black box."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the formal claim in Theorem 4.1 is solid and a genuine step forward, but the abstract overstates it. The 'exponential number of adaptive queries' with r = O~(k^2) does not follow from the theorem; the correct regime is subexponential. That doesn't sink the paper, but the headline needs fixing.\n\nWhat's new: the reformulation of the robustness wrapper as fine-grained ADA with per-key generalization is a real conceptual contribution. The robust bottom-k estimator and its tracking variant are non-obvious, and the simulation argument through Algorithm 1 (the target-charging SVT) is clean. I checked the main proof: Lemma 4.2 correctly couples the sketch-based count to the full count, the accounting via Cohen & Lyu's per-unit privacy theorem checks out, and Propositions 4.4/4.5 deliver the (1±α) guarantee. The tracking analysis in Appendix C also looks right, with the same induction. Experiments show 12–100x gains; they are synthetic and lack variance bars, but the axes are sensible.\n\nSoft spots: (1) The abstract's exponential claim is not supported. The stress-test math is correct: plug r = Θ~(k^2 α^4) into k = O(α^{-2}√r log^{3/2}(n/β)) and you get log(n/β) = O(1), so n is constant and t ≤ n r = O(k^2). To get t exponential in k you'd need log n = Ω(k), which makes the theorem's inequality force r ≤ O(α^4/k), contradicting r ≫ log(n/β) = Ω(k). The achievable bound is t = exp(O(α√k))·poly(k). So the authors need to rewrite the abstract and Section 1.3 to claim subexponential, or exhibit a different parameter regime. (2) The full i.i.d. randomness assumption in footnote 4 is load-bearing. The ADA reduction needs a product distribution; a pseudorandom or k-wise independent hash family doesn't give you that. For an adversarial setting this is not cosmetic. It should be stated as a theorem condition, not a footnote. (3) Minor: the informal r = Ω~(k^2 α^4) direction is confusing; the theorem has r ≫ log(n/β), and the Ω~ should be spelled out carefully. Also, the experiments don't report variance, which makes the gain factors hard to interpret.\n\nVerdict: this deserves a serious referee. The core per-key participation result is a real shift from the quadratic barrier, the proofs are detailed and mostly self-contained, and the problems are corrigible. I would send it to review, with a strong expectation of revision.","headline":"The formal per-key participation result is real and worth refereeing, but the abstract's 'exponential queries' claim outruns Theorem 4.1; the headline needs correction before acceptance.","tokens_in":19325,"tokens_out":2831,"would_cite":true,"duration_ms":26913,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68W25","68P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims to break the quadratic barrier on adaptive queries for cardinality sketches, shifting the bound from total queries to per-key participation.","keywords":["adaptive queries","cardinality sketches","bottom-k MinHash","differential privacy","adaptive data analysis","per-key participation","quadratic barrier","robust estimation"],"falsifier":"Run RobustEst (or TRobustEst) with priorities generated by a 2-independent hash family instead of independent U[0,1] draws, and let an adaptive adversary issue queries that concentrate on a single key while keeping per-key participation at r ≈ 0.$002k^{2}$; if the estimator loses (1±α) accuracy at k = C $α^{{-2}}$√r $log^{{3/2}}$(n/β), the independence assumption is load-bearing. Alternatively, try to construct an adaptive sequence with each key in at most r queries that still drives the estimate off by more than α; the theorem predicts none exists.","tokens_in":18230,"feed_emoji":"","tokens_out":7047,"duration_ms":62137,"temperature":0.7,"pith_summary":"The paper claims to break the quadratic barrier on adaptive queries for cardinality sketches. Previous work showed that a sketch of size k fails after roughly $k^{2}$ adaptively chosen queries, no matter the estimator; this paper instead ties the guarantee to per-key participation, showing that a bottom-k MinHash sketch of size k = O($α^{{-2}}$√r $log^{{3/2}}$(n/β)) answers every query within a (1±α) factor with probability 1-β, provided each key appears in at most r query sketches. Since r can be far smaller than the total number of queries, this allows exponentially many queries when the workload spreads across keys. The paper also gives a tracking estimator that deactivates overused keys and degrades gracefully, and reports 12× to 100× gains in simulated workloads.","feed_headline":"Quadratic barrier broken for adaptive cardinality sketches","feed_subtitle":"New estimators stay (1±α)-accurate for exponentially many adaptive queries, as long as each key appears in few of them.","key_machinery":"The load-bearing object is the fine-grained SQ (statistical query) framework, which reduces robust sketching to adaptive data analysis. Concretely: the random priority vector ρ is the dataset from a product distribution; the query predicate is h_{V,τ}(i, ρ_i) = 1[i ∈ V ∧ ρ_i < τ], so the count over the dataset equals τ|V| in expectation; and the response algorithm is AboveThreshold with per-key 'charging' counters that deactivate a key after r positive queries (Algorithm 1). The analysis chains the privacy of that charging mechanism (Theorem 2.1) to the generalization property of differential privacy (Theorem 2.2), yielding error bounds in which the additive term is O($α^{{-1}}$√r $log^{{3/2}}$(mn/β)) plus α times the query's expectation (Corollary 3.3). Because this error depends on r rather than on total queries t, a bottom-k sketch of size k can be set proportional to √r and still answer an exponential number of adaptive queries.","core_discovery":"The central discovery is that robustness to adaptive queries can be guaranteed per key rather than per query. The authors reformulate the privacy-based robustness wrapper as an adaptive data analysis problem: the sketch's random priorities ρ = (ρ_1,...,ρ_n) are treated as a dataset drawn from a product distribution, and each query to the sketch becomes a linear threshold query h_{V,τ}(i, ρ_i) = 1[i ∈ V and ρ_i < τ]. Using the Sparse Vector Technique with individual per-key charging, they prove a fine-grained generalization bound in which the number of positive queries per key, r, controls the error. Instantiating this on the bottom-k MinHash sketch with the estimator RobustEst yields Theorem 4.1: for r ≫ log(n/β), sketch size k = O($α^{{-2}}$√r $log^{{3/2}}$(n/β)) answers all queries (1±α)-accurately with probability 1-β, provided each key participates in at most r queries. A second estimator, TRobustEst, tracks each key's participation, deactivates keys that exceed r, and retains accuracy as long as no query's sketch contains more than k/2 deactivated keys and the queries in question have at most αk/4 deactivated keys.","pith_inferences":["A practical deployment reading: workloads with per-user or per-key query limits can safely use far smaller sketches than the total-query bound would suggest; the guarantee degrades only when an adversary concentrates queries on the same keys.","If full i.i.d. randomness is truly required, implementations must avoid low-independence hash families; an engineering check is to compare failure rates of 2-independent hashing against a cryptographic hash on an adaptive adversary that targets one key at a time.","The per-key charging mechanism is essentially per-key privacy accounting; it could be imported into other interactive data structures, possibly replacing DP with other ADA algorithms where DP's constants are undesirable.","For heavy-tailed (Pareto) workloads, the tracking estimator is necessary; the experiments suggest 12×–40× gains, and the gap between uniform (100×) and skewed (12×) distributions indicates where per-key bounds bind."],"forward_implications":["Sketch size can be traded against robustness per key: k = O(α^{-2}√r log^{3/2}(n/β)), so reducing the allowed per-key participation r directly reduces the required sketch size.","An exponential number of total adaptive queries becomes safe whenever the query distribution spreads over keys so that each key appears in few query sets.","The tracking estimator allows a few heavy-hitter keys to exceed the per-key budget: those keys are deactivated, and estimates remain (1±α)-accurate as long as each query sketch has at most αk/4 deactivated keys and none has more than k/2.","The same fine-grained ADA reduction is a candidate template for other randomized composable sketches, including k-partition (PCSA) and capping statistics, as the authors conjecture."],"supporting_citations":[{"why":"Supplies the generic differential-privacy robustness wrapper that this paper reformulates into an adaptive-data-analysis reduction.","marker":"Hassidim et al. (2020)"},{"why":"Provides the per-key charging privacy bound (Theorem 2.1) that lets the analysis depend on per-key participation r rather than total queries.","marker":"Cohen & Lyu (2023a)"},{"why":"Establishes the generalization property of differential privacy used to bound sampling error for adaptively chosen predicates.","marker":"Dwork et al. (2015)"},{"why":"Co-source of the DP generalization theorem (Theorem 2.2) that converts privacy into accuracy for adaptive queries.","marker":"Bassily et al. (2021)"},{"why":"Gives the quadratic universal lower bound that defines the barrier the paper claims to shift to per-key participation.","marker":"Cohen et al. (2024)"},{"why":"Shows standard MinHash estimators fail to O~(k) adaptive queries, motivating the new robust estimators.","marker":"Ahmadian & Cohen (2024)"},{"why":"Provides the expectation bound used in the proof of the generalization theorem (Lemma B.1).","marker":"Kontorovich et al. (2022)"}],"fun_headline_variants":["Cardinality sketches now handle exponential adaptive queries","Sketch robustness shifts from total to per-element query barrier","Exponential adaptive queries possible with bounded per-key participation","Per-key charging lets sketches survive exponential adaptive queries","Quadratic barrier moves from total to per-key query count"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantees require the sketch priorities to be fully independent random draws from a product distribution, not merely k-wise independent or pseudorandom hashes; the privacy-generalization argument that controls adaptive queries collapses without that independence.","fun_headline_variants_meta":{"raw":{"variants":["Cardinality sketches now handle exponential adaptive queries","Sketch robustness shifts from total to per-element query barrier","Exponential adaptive queries possible with bounded per-key participation","Per-key charging lets sketches survive exponential adaptive queries","Quadratic barrier moves from total to per-key query count"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000435,"raw_usage":{"total_tokens":2220,"prompt_tokens":957,"completion_tokens":1263,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":1187}},"tokens_in":573,"tokens_out":1263,"duration_ms":11014,"temperature":1.0,"reasoning_tokens":1187,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T18:14:55.609702+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run RobustEst (or TRobustEst) with priorities generated by a 2-independent hash family instead of independent U[0,1] draws, and let an adaptive adversary issue queries that concentrate on a single key while keeping per-key participation at r ≈ 0.$002k^{2}$; if the estimator loses (1±α) accuracy at k = C $α^{{-2}}$√r $log^{{3/2}}$(n/β), the independence assumption is load-bearing. Alternatively, try to construct an adaptive sequence with each key in at most r queries that still drives the estimate off by more than α; the theorem predicts none exists.","supporting_citations":[{"cited_title":"Adversarially robust streaming algorithms via differential privacy","cited_arxiv_id":null,"evidence_quote":"Supplies the generic differential-privacy robustness wrapper that this paper reformulates into an adaptive-data-analysis reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the generalization property of differential privacy used to bound sampling error for adaptively chosen predicates."},{"cited_title":"D., Steinke, T., Stemmer, U., and Ullman, J","cited_arxiv_id":null,"evidence_quote":"Co-source of the DP generalization theorem (Theorem 2.2) that converts privacy into accuracy for adaptive queries."},{"cited_title":"One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches","cited_arxiv_id":"2411.06370","evidence_quote":"Gives the quadratic universal lower bound that defines the barrier the paper claims to shift to per-key participation."},{"cited_title":"Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs","cited_arxiv_id":"2405.17780","evidence_quote":"Shows standard MinHash estimators fail to O~(k) adaptive queries, motivating the new robust estimators."},{"cited_title":"Adaptive data analysis with correlated observations, 2022","cited_arxiv_id":null,"evidence_quote":"Provides the expectation bound used in the proof of the generalization theorem (Lemma B.1)."}],"review_version":1}