{"id":"22bcedd3-d4ed-4800-952e-bea08bdcd3cb","arxiv_id":"1908.04810","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact occupancy-moment formulas give exact false-positive and efficiency expressions for Bloom filters, revealing that the standard m/n ln2 hash-count rule is a slight overestimate and that standard-filter peak efficiency falls as hash count rises.","lead":"This paper derives exact formulas for the moments of occupancy and committee distributions and uses them to compute exact false-positive rates for classic and standard Bloom filters. It reports that the usual m/n ln2 rule slightly overestimates the best number of hash functions and that standard Bloom filter peak efficiency is highest with a single hash function.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Efficiency theorems maximize over non-integer item counts, so the claimed global maximum is not a theorem about actual Bloom filters.","rationale":"The reader identifies the same load-bearing concern: Theorem 26 and Corollary 27 optimize over non-integer item counts without stating a continuous relaxation. I agree that this is the central rigor gap. The mathematical core is sound: for fixed total hash operations n, the inequality is an instance of Lyapunov's inequality on the occupancy fraction, and the resulting continuous maximum is plausible. But the paper presents the result as a statement about Bloom filters, which store whole items, so the literal claim of a unique maximum at a non-integer n is not established. The abstract additionally overstates the scope of the monotonicity claim: the standard-filter theorem concerns peak efficiency in the continuous relaxation, and the classic-filter analogue is only Conjecture 28. Because the concern is addressable by re-scoping the claims or proving an integer version, CONDITIONAL is the right verdict, and my read does not change it.","tokens_in":26210,"tokens_out":15702,"duration_ms":146243,"concrete_test":"For m=100, compute the exact efficiency εS(m,n,k) = (n/m) log2(1/fS(m,n,k)) using eq. (56) (or Theorem 22) for all integers n≥1 and 1≤k≤100, and find the integer-constrained maximum. Compare it with ε*S(100)=1/(100 log2(100/99))≈0.68966. Report whether the integer optimum is at (k=1,n=69) and whether any k≥2 with integer n achieves higher efficiency. Also repeat for m=3,4,10,1000 to see whether the gap between the continuous and integer optima is material. If the integer optimum is strictly below the continuous value, Corollary 27 needs re-scoping to a supremum, with an explicit integer-error bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central efficiency claim rests on Theorem 26 and Corollary 27, which assert that an m-bit standard Bloom filter has maximum efficiency ε*S = 1/(m log2(m/(m-1))) at k=1 and n=(log2(m/(m-1)))^(-1). But this n is not an integer for typical m, and the theorem's comparison εS(m,n/k,k) > εS(m,n/(k+1),k+1) evaluates efficiency at a fractional item count. The false-positive rate fS(m,n,k)=E[X_S^k]/m^k in eq. (53) is well-defined for real n provided nk is an integer, and εS(m,n/k,k) keeps the total number of ball placements equal to n, so the inequality itself is a correct statement about the continuous relaxation of the occupancy model. However, the paper never states that it is optimizing over a continuous relaxation. Consequently Corollary 27's 'uniquely obtained' maximum is not a literal statement about finite Bloom filters storing whole numbers of items; it is a supremum over non-integer n. The integer-constrained maximum may occur at a nearby integer (e.g., n=69 for m=100) with slightly lower efficiency, or conceivably at a different k. The abstract's 'efficiency is monotonic in the number of hash functions' is also broader than what is proved: Theorem 26 proves monotonicity of the continuous relaxation for standard filters, while the analogous classic-filter claim is explicitly labeled Conjecture 28. The Hölder/Lyapunov argument underlying Theorem 26 is sound; the gap is in the scoping of the claims to actual filters.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops exact moment formulas for classic occupancy, committee, and multivariate committee distributions, identifies these distributions as members of Berg's factorial series and Kemp's generalized hypergeometric factorial-moment families, and applies the moment machinery to Bloom filter analysis. It derives exact false-positive rate formulas for standard and classic Bloom filters, gives bounds and estimators, and analyzes filter efficiency. The headline claims are that the conventional approximation k ≈ (m/n) ln 2 overestimates the optimal number of hash functions, that standard Bloom filter efficiency is maximized with a single hash function, and that Bloom filter efficiency is monotonic in the number of hash functions.","tokens_in":26502,"tokens_out":7778,"duration_ms":79041,"significance":"If its scoping issues are resolved, the paper makes a solid contribution. The moment derivations in Sections 2 and 3 are internally consistent, reproduce known results, and provide genuinely useful formulas and bounds. The exact false-positive rate formulas for classic and standard Bloom filters, and the side-by-side comparison in Section 3, are valuable correctives to a literature that often conflates the two constructions. The efficiency analysis is thought-provoking: it suggests that the standard Bloom filter, under a continuous relaxation, is most efficient with one hash function, and that the classic filter can approach the information-theoretic efficiency limit. However, the central efficiency theorem is currently stated as a result about finite Bloom filters when it is, in fact, a result about a continuous relaxation; this must be fixed before the headline claims can be accepted.","major_comments":[{"comment":"The proof of Corollary 27 eliminates k > 1 using Theorem 26, but Theorem 26 compares configurations whose item counts n/k and n/(k+1) are, in general, non-integers, while an actual Bloom filter stores a whole number of items. The optimizer n = (log2(m/(m-1)))^(-1) in Corollary 27 is not an integer for typical m (for m = 100 it is approximately 68.97), so the asserted 'maximum efficiency of an m-bit standard Bloom filter' is actually a supremum over a continuous relaxation, not a maximum over finite Bloom filters. The integer-constrained maximizer is not identified, and the exact value 1/(m log2(m/(m-1))) is not attained by any real filter with an integer item count. The paper should either prove the integer version of the theorem or explicitly present the result as a continuous-relaxation supremum and revise the abstract and conclusions accordingly.","section":"Section 4.1.1, Theorem 26 and Corollary 27"},{"comment":"The claim that 'Bloom filter efficiency is monotonic in the number of hash functions' is broader than the results support. Theorem 26 proves monotonicity only for the continuous-relaxation comparison of configurations with item counts n/k and n/(k+1), not for fixed integer item counts in an actual filter. Moreover, for classic Bloom filters the analogous monotonicity statement is explicitly labeled Conjecture 28, so the unqualified monotonicity assertion in the abstract overstates what is derived. The abstract and the contribution bullets need to be qualified by filter type and by whether the claim concerns fixed n or peak efficiency, and the conjectural status of the classic-filter case should be acknowledged.","section":"Abstract and Section 1.2"}],"minor_comments":[{"comment":"The equality condition stated in the proof is incorrect: equality in the Lp-norm inequality requires the random variable to be constant almost surely, not uniformly distributed over [m]. This does not affect the strict inequality for n,m >= 2, but the sentence should be corrected.","section":"Section 4.1.1, proof of Theorem 26"},{"comment":"The displayed expression '2εk_S - εk+1_S' appears to be a typo; the subsequent argument establishes εk_S > εk+1_S via the logarithm of the ratio. Please correct the display to avoid confusing the strict inequality being proved.","section":"Section 4.1.1, display after (73)"},{"comment":"The caption states that the maximum efficiency ε*_S(100) = 0.69 occurs at n = 69, while Corollary 27 gives the non-integer optimizer n ≈ 68.97 and ε*_S ≈ 0.6897. The text should clarify that 69 is the nearest integer to the continuous maximizer and that the exact formula in Corollary 27 is not attained by an integer-item filter.","section":"Figure 9"},{"comment":"The bullet in Section 1.2 saying the efficiency of a classic Bloom filter 'decreases as the number of hash bits decrease' is confusingly worded; the intended statement appears to be that peak efficiency increases with k. Please rephrase and mark the monotonicity as conjectural, consistent with Conjecture 28.","section":"Section 4.1.2"},{"comment":"The word 'respectfully' should be 'respectively' in the statement of Corollary 30.","section":"Corollary 30"}],"recommendation":"major_revision","confidential_remarks":"The paper's distributional results are solid, but the abstract and the stated efficiency theorem oversell the result: the 'maximum efficiency' is a supremum over non-integer item counts, and the abstract's monotonicity claim includes a case that is left as a conjecture. These issues are fixable within the manuscript's scope by re-scoping the theorem and adjusting language, but they are load-bearing for the paper's main applied claim, so I recommend major revision rather than acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:1908.04810.\n\nThe distribution theory is the strongest part. Sections 2 and 3 give a clean treatment of multivariate committee distributions, connect them to Berg's factorial series and Kemp's generalized hypergeometric factorial moment families, and derive exact false-positive formulas for standard and classic Bloom filters, with proper credit to Bose et al. and Roberts. The inclusion-exclusion and Stirling-inversion derivations check out, and the historical note on the classic/standard conflation is actually useful.\n\nThe efficiency half is where the claims outrun the proofs. Theorem 26 compares εS(m,n/k,k) with εS(m,n/(k+1),k+1), i.e., filters with different item counts but the same total number of hash placements. The Hölder/Lyapunov argument is sound, but it is a statement about the efficiency function extended to real item counts. Corollary 27 then says the maximum efficiency of an m-bit standard filter is uniquely attained at n=(log2(m/(m-1)))^(-1), which is not an integer for any ordinary m. The paper never says it is optimizing a continuous relaxation, so the claimed maximum is a supremum over non-integer n, not a theorem about a finite filter storing a whole number of items. The integer-constrained maximum will be at a nearby integer with slightly lower efficiency; for m=100 the difference is in the third decimal, but the statement as written is not literally correct.\n\nThe abstract's monotonicity claim is also broader than what is proved. For standard filters, the continuous-relaxation argument gives monotonicity of peak efficiency, not of efficiency at fixed n. For classic filters, the analogous statement is labeled Conjecture 28, and Conjecture 24, about the conventional k* rule overestimating the optimal hash count, is likewise unproved. So the abstract overstates the derived results.\n\nThese are scoping problems, not fatal flaws in the math. The false-positive formulas and the distribution theory are solid and worth having. The efficiency results are likely true in the continuous sense and can probably be recovered for integers with careful handling. The paper ships no code or data, but as a theory paper it does not need any. The citation pattern is appropriate, including the single self-citation to the author's thesis.\n\nWho is this for? Readers interested in occupancy distributions and their moment structure, or in exact Bloom filter analysis, will get value. Bloom filter researchers should read the FPR half and treat the efficiency theorems with the relaxation caveat. I would send it to a serious referee, but with explicit instructions that the authors either re-scope Corollary 27 and the abstract to the integer setting or clearly define and justify the continuous relaxation. As it stands, the headline results are too strong.","headline":"Solid occupancy-moment paper with correct false-positive formulas, but the headline efficiency theorems are proven only for a continuous relaxation and one advertised monotonicity result is still a conjecture.","tokens_in":27010,"tokens_out":9942,"would_cite":false,"duration_ms":94115,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","68R05","94A24","33C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact occupancy moments show a standard Bloom filter peaks in efficiency with one hash function, not the customary many, and that the k≈(m/n)ln2 rule overshoots the optimum.","keywords":["classic occupancy problem","committee problem","Stevens-Craig distribution","factorial series distribution","generalized hypergeometric factorial moment distribution","Bloom filter","false-positive rate","filter efficiency"],"falsifier":"Take a small filter length such as $m=64$ or $m=100$, compute the exact standard-filter false-positive rate from the moment sum in Theorem 22 for every integer $n$ and $k$, and find the integer maximum of $\\varepsilon_S = -\\frac{n}{m}\\log_2 f_S$. If the maximum over integers occurs away from $k=1$ and the nearest integer to $(\\log_2 \\frac{m}{m-1})^{-1}$, or if $\\varepsilon_S(m,n/k,k) > \\varepsilon_S(m,n/(k+1),k+1)$ fails for some integer $m,n \\ge 2$, then the claimed global optimum depends on the unstated continuous relaxation.","tokens_in":25981,"feed_emoji":"🧮","tokens_out":13033,"duration_ms":114869,"temperature":0.7,"pith_summary":"Using exact moment formulas for occupancy distributions—the count of occupied urns when balls are cast in batches—the paper obtains exact expressions for the false-positive rate and efficiency of both classic and standard Bloom filters, probabilistic set-membership structures widely used in storage and network systems. It proves that a standard Bloom filter's peak efficiency decreases as the number of hash functions $k$ increases, so the most efficient configuration is $k=1$ storing $n = (\\log_2 \\frac{m}{m-1})^{-1}$ items, giving efficiency $\\varepsilon_S^* = (m \\log_2 \\frac{m}{m-1})^{-1}$. From these exact formulas it concludes that the familiar optimization rule $k \\approx \\frac{m}{n}\\ln 2$ overestimates the optimal hash count for small filters, producing extra hash work and a higher false-positive rate. The same machinery shows the classic Bloom filter approaches the information-theoretic efficiency limit of 1 as $m\\to\\infty$, while the standard variant approaches $\\ln 2$. The result makes exact small-filter optimization available in place of asymptotic approximation.","feed_headline":"Standard Bloom filters peak with one hash, not many","feed_subtitle":"Exact occupancy-moment formulas show the classic k≈(m/n)ln2 rule overshoots the optimal hash count.","key_machinery":"The engine is the family of committee-occupancy distributions—multivariate generalizations of the classic balls-into-urns occupancy count—together with their membership in the factorial series and generalized hypergeometric factorial moment families. The load-bearing identities are the moment formulas: $f_S = E[X_S^k]/m^k$ for the standard filter and $f_C = E[\\binom{X_C}{k}]/\\binom{m}{k}$ for the classic filter, expressed through finite differences and generalized hypergeometric functions (Theorems 4, 10, 13, and 22). These convert false-positive and efficiency calculations into computable moment evaluations even when the filter length $m$ is enormous, because the sums run over $k$ rather than $m$. The comparison of adjacent hash counts in Theorem 26 rests on the norm inequality $E[|X|^{k+1}]^{1/(k+1)} \\ge E[|X|^k]^{1/k}$ applied to the occupancy random variable.","core_discovery":"On its own terms, the paper's central claim is that exact occupancy moments answer Bloom filter efficiency. For a standard Bloom filter, the expected false-positive rate is $f_S(m,n,k)=E[X_S^k]/m^k$, where $X_S$ is the classic-occupancy count of 1-bits; for a classic Bloom filter it is $f_C(m,n,k)=E[\\binom{X_C}{k}]/\\binom{m}{k}$, a binomial moment. Substituting these into $\\varepsilon = -\\frac{n}{m}\\log_2 f$ and comparing $k$ with $k+1$ through a standard $L^p$ norm inequality yields the theorem $\\varepsilon_S(m,n/k,k) > \\varepsilon_S(m,n/(k+1),k+1)$ and its corollary that the standard filter's maximum efficiency is $\\varepsilon_S^* = [m \\log_2 \\frac{m}{m-1}]^{-1}$, attained at $k=1$ and $n=(\\log_2 \\frac{m}{m-1})^{-1}$ with false-positive rate $1/2$. For classic filters the paper proves in the limit that peak efficiency tends to 1 as $m\\to\\infty$ at $n=1$, $k=m/2$, while the standard filter tends to $\\ln 2 \\approx 0.693$; the monotone increase of classic-filter peak efficiency in $k$ is stated as Conjecture 28, not proven as a theorem. The exact formulas also make the common approximation $(1-e^{-nk/m})^k$ unnecessary for small-filter optimization.","pith_inferences":["If the one-hash optimum survives the integer-item-count restriction, standard-filter design reduces to choosing $m$ with $n \\approx m \\ln 2$ and using a single hash; the entire optimization over $k$ disappears in practice.","The exact moment analysis exposes a small-filter regime in which the standard Poisson approximation is systematically biased; a natural testable extension is to characterize, as a function of $m/n$, the smallest filter where the approximation's optimal $k$ first agrees with the exact optimum.","Because the committee distributions form factorial series and generalized hypergeometric factorial moment families, the same machinery likely supplies exact false-positive formulas for other occupancy-modeled membership filters, such as counting or partitioned Bloom filters, where asymptotic estimates are still the norm.","If Conjecture 28 is true, classic filters dominate standard filters in efficiency at every hash count, not just in the large-$m$ limit, which would make the standard construction harder to justify on efficiency grounds alone."],"forward_implications":["Standard Bloom filters should be configured with one hash function and about $m \\ln 2$ stored items for peak efficiency; at that configuration the false-positive rate per probe is $1/2$.","The common formula $k^* \\approx \\frac{m}{n}\\ln 2$ overshoots the exact optimal hash count for small filters; the paper's $m=1024$, $n=5$ example gives $k^*=142$ predicted versus $k_S^*=133$ and $k_C^*=124$ exact, so following the rule adds hash work and raises the false-positive rate.","Classic Bloom filters with one stored item and $k=m/2$ approach the information-theoretic efficiency ceiling of 1 as $m$ grows, while standard filters level off at $\\ln 2 \\approx 0.693$.","The exact formulas and recurrences in the paper let practitioners optimize small filters directly instead of relying on the Poisson approximation $(1-e^{-nk/m})^k$.","A classic filter holding one item can be losslessly compressed to $\\log_2 \\binom{m}{k}$ bits, preserving its false-positive rate and reaching efficiency 1 for every $k \\le m/2$."],"supporting_citations":[{"why":"It defines the classic Bloom filter and supplies the false-positive estimate that the paper shows is an upper bound, not the exact expected rate.","marker":"[4]"},{"why":"It introduces the standard Bloom filter and the approximation whose recommended k about (m/n)ln2 the paper argues overshoots.","marker":"[31]"},{"why":"It provides the exact sum formula for the standard filter's false-positive rate, which the paper rewrites as a short sum over k.","marker":"[6]"},{"why":"It gives the recurrences for the standard and classic false-positive rates and the first side-by-side false-positive comparison on which the efficiency analysis builds.","marker":"[22]"},{"why":"It defines filter efficiency as (n/m) log2(1/p) and establishes the universal upper bound between 0 and 1.","marker":"[58]"},{"why":"It introduces factorial series distributions and the capture-recapture moment estimators used for the committee union distribution.","marker":"[3]"},{"why":"It defines the generalized hypergeometric factorial moment family and the recurrence method applied to the committee intersection distribution.","marker":"[28]"}],"fun_headline_variants":["Bloom filter sweet spot is one hash function","Classic Bloom filter rule overshoots optimal hashes","One hash beats ln2 rule for Bloom filters","Standard Bloom filter optimum: k=1, not m/n ln2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The efficiency theorems optimize over non-integer item counts—Theorem 26 compares $n/k$ and $n/(k+1)$, and Corollary 27 sets $n = (\\log_2 \\frac{m}{m-1})^{-1}$—even though the occupancy random variable counts whole items, and the paper never states that it is using a continuous relaxation of item counts.","fun_headline_variants_meta":{"raw":{"variants":["Bloom filter sweet spot is one hash function","Classic Bloom filter rule overshoots optimal hashes","One hash beats ln2 rule for Bloom filters","Standard Bloom filter optimum: k=1, not m/n ln2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000755,"raw_usage":{"total_tokens":3370,"prompt_tokens":968,"completion_tokens":2402,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":584,"completion_tokens_details":{"reasoning_tokens":2346}},"tokens_in":584,"tokens_out":2402,"duration_ms":16662,"temperature":1.0,"reasoning_tokens":2346,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:34:11.364550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small filter length such as $m=64$ or $m=100$, compute the exact standard-filter false-positive rate from the moment sum in Theorem 22 for every integer $n$ and $k$, and find the integer maximum of $\\varepsilon_S = -\\frac{n}{m}\\log_2 f_S$. If the maximum over integers occurs away from $k=1$ and the nearest integer to $(\\log_2 \\frac{m}{m-1})^{-1}$, or if $\\varepsilon_S(m,n/k,k) > \\varepsilon_S(m,n/(k+1),k+1)$ fails for some integer $m,n \\ge 2$, then the claimed global optimum depends on the unstated continuous relaxation.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines the classic Bloom filter and supplies the false-positive estimate that the paper shows is an upper bound, not the exact expected rate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the standard Bloom filter and the approximation whose recommended k about (m/n)ln2 the paper argues overshoots."},{"cited_title":"and Tang, Y","cited_arxiv_id":null,"evidence_quote":"It provides the exact sum formula for the standard filter's false-positive rate, which the paper rewrites as a short sum over k."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It gives the recurrences for the standard and classic false-positive rates and the first side-by-side false-positive comparison on which the efficiency analysis builds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines filter efficiency as (n/m) log2(1/p) and establishes the universal upper bound between 0 and 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces factorial series distributions and the capture-recapture moment estimators used for the committee union distribution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines the generalized hypergeometric factorial moment family and the recurrence method applied to the committee intersection distribution."}],"review_version":1}