HyperLogLog for probabilists

Lucas Gerin (MODAL'X)

HyperLogLog for probabilists

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that HyperLogLog's raw estimate has exponential upper and lower tail bounds that hold non-asymptotically for every dataset size and every number of registers, under the Random Oracle model.

desk verdict First non-asymptotic exponential tail bounds for the discrete HyperLogLog estimator, with an elementary and checkable proof; the paper is honest about its variant and assumptions. read the letter →

arxiv 2607.22063 v1 pith:6D7DCUTF submitted 2026-07-24 cs.DS math.PR

Lucas Gerin (MODAL'X) This is my paper

classification cs.DSmath.PR MSC 68W2060E15

keywords HyperLogcardinalityestimationstreamingalgorithmsdeviationinequalitiesconcentrationofmeasureRandomOraclemodelstochasticaveragingMinCount

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that HyperLogLog, the classic streaming algorithm for counting distinct elements, has exponential concentration of its raw estimator around the true count N. Under the standard Random Oracle model (hashed values behave like truly random uniforms), the probability of underestimating by a factor μ decays like exp(-m J(μ)), and overestimating by a factor λ decays like exp(-m J(λ/2)) plus an explicit correction, where m is the number of registers and J is an explicit rate function. The bounds are non-asymptotic: they hold for every N and every m, with no hidden constants. The proof is deliberately elementary, using only the Chernoff method, a stochastic comparison of register minima to exponentials, and a concavity argument to handle dependence between registers. Because the estimates are explicit, they immediately give one-sided confidence intervals for the true cardinality.

What carries the argument

The central object is the random vector (Y_1,...,Y_m) of minima of hashed values falling in each register, which represents Z_N via y/2 ≤ 2^{-ρ(y)} ≤ y. The right tail is carried by a comparison lemma: (Y_1,...,Y_m) is smaller in the upper-orthant order than (m/N)(E_1,...,E_m) for i.i.d. exponentials, so the Laplace transform of the sum is bounded by that of a Gamma variable. The left tail is carried by a conditional bound E[e^{-λY_j}|A_j=k] ≤ (k+e^{-λ}(λ-1))/(k+λ-1), whose logarithm is concave in k, allowing a Jensen step over the multinomial occupation counts. The rate function J(x)=1/x-1+log x is what falls out of optimizing the Chernoff exponent.

What would settle it

For m=2 and N=2, compute exactly the distribution of m²Z_N under i.i.d. uniform inputs by enumerating all register assignments, and check whether P(m²Z_N ≤ μN) ≤ exp(-mJ(μ)) for all μ≤1 and whether P(m²Z_N ≥ λN) ≤ exp(-mJ(λ/2)+δ(m,N,2/λ)) for all λ≥2; any violation for a single pair would refute Theorem 4. Since the theorem is conditional, an alternative practical falsifier is to exhibit a deterministic hash function and a dataset where the deduplicated hash values deviate from uniformity strongly enough that simulated tail frequencies exceed the bound.

Watch

Extended reading notes

Core claim

The central result is Theorem 4: for the HyperLogLog estimator built from m=2^b registers, the probability that m²Z_N falls below μN is at most exp(-mJ(μ)) for μ≤1, and the probability it exceeds λN is at most exp(-mJ(λ/2)+δ(m,N,2/λ)) for λ≥2, where J(x)=1/x-1+log x and δ is explicit and bounded by (c+e^{-2})m²/N. The proof shows the register minima Y_j are stochastically dominated by m/N times exponentials in the upper-orthant order, which transfers a Laplace-transform bound despite the dependence; the left tail uses a log-concavity of a bound on the conditional Laplace transform. This is the first non-asymptotic deviation inequality for the discrete HyperLogLog output, with explicit correc

Load-bearing premise

The load-bearing premise is that the hash function's outputs are statistically indistinguishable from genuine i.i.d. uniform random variables, and that the modified algorithm with registers initialized to 1 (whose equivalence to the standard version is only asymptotic in N ≫ m log m) is the one being analyzed.

Editorial extensions

If this is right

With m registers, failure probabilities decay exponentially in m, so doubling m approximately squares the tail bound; this is the first non-asymptotic quantitative form of the stochastic-averaging intuition.
The left-tail bound yields a non-asymptotic one-sided confidence interval for the true cardinality: with probability at least 1-ε, N ≤ (1+2√(log(1/ε)/m)) m² Z_N.
The raw estimator m²Z_N, without debiasing, is already a valid order-of-magnitude estimator even in extreme cases m=1 or m=2 where the debiasing constants of the classical analysis are undefined or infinite.
The same Proposition 8 gives exponential deviation inequalities for the MinCount algorithm (case k=1), with a right-tail bound that holds for all λ≥1 rather than only λ≥2.
For fixed m and N, the right-tail bound implies that the estimator has finite p-th moments for all p<m, a fact not available from the asymptotic variance analysis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The author suggests the method may transfer to other stochastic-averaging sketches; a concrete next step would be to find a log-concave bound on the conditional Laplace transform for order-statistics estimators with k>1, which would extend these bounds to the better-performing MinCount variants.
The explicit correction δ(m,N,c) ≈ c m²/N reveals a sharp threshold: the right-tail bound becomes useful only when N is comparable to or larger than m²; for tiny N the bound is vacuous, so practical deployments should still handle the small-N regime separately.
Because the bounds have no built-in slack for hash imperfections, applying them in a real system requires measuring hash quality (e.g., via collision or uniformity tests); the Random Oracle idealization is the only place where a practical failure could slip in.
The one-sided confidence interval maps directly to network-anomaly detection: an unexpectedly large m²Z_N triggers an alert with a certified false-positive rate, which is exactly the kind of guarantee operators need in high-volume settings.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is simple: this is the first non-asymptotic exponential deviation bound for the discrete HyperLogLog estimator, and the proof is clean enough to be worth your time. Gerin replaces the poissonization/Mellin machinery of the original paper with a Chernoff argument on register minima, and it works. I traced the chain from the multinomial representation through the upper-orthant comparison to the Laplace-transform domination and the concavity step; the algebra is consistent and the constants are explicit. The rate function J is the right one, and the δ correction term is honest.

What is genuinely new: Theorem 4 gives left-tail P(m²Z_N ≤ μN) ≤ exp(−mJ(μ)) for all μ ≤ 1, and a right-tail version for λ ≥ 2 with an explicit correction. That is strictly more than the expectation/variance analysis in Flajolet et al. and the heuristic remark in the LogLog paper. The proof is elementary and self-contained, which makes it useful for teaching and for adapting to other stochastic-averaging sketches. The MinCount application is a nice bonus.

Soft spots, in proportion. The theorem is proved for Algorithm 1 with registers initialized to 1, not the 0/−∞ initialization of the original paper. The author discloses this and notes the asymptotic regime N ≫ m log m is unchanged, but the non-asymptotic statement is literally about the modified algorithm. If a practitioner wants the bound for the exact HLL variant in Redis/BigQuery, that step is a bridge they need to cross. The Random Oracle hypothesis is stated up front and is the field-standard idealization; it carries no error term for real hash functions. The right-tail bound only kicks in for λ ≥ 2 and carries a correction term — the author says plainly why, and that is fine. Minor issues: the simulation numbers in §1.2 are informal and not backed by code or data, but they are not load-bearing; the 'mean-value inequality' misspeak in §3.2 is cosmetic.

I disagree with no part of the reader's assessment. The paper is honest, the proof is reproducible on paper, and the limitations are disclosed. It is not a massive breakthrough, but it is a solid, clean result that fills a real gap.

Who is it for? Researchers in streaming algorithms and probabilistic analysis; also anyone teaching HLL who wants a proof that doesn't depend on Mellin transforms. It deserves peer review — it is short but the theorem is useful, the proof is checkable, and the writing is clear. I would send it to a serious referee.

Referee Report

0 major / 4 minor

Summary. The paper revisits the analysis of the HyperLogLog cardinality estimation algorithm under the Random Oracle model and proves fully explicit, non-asymptotic exponential deviation bounds for the raw estimator m^2 Z_N. The main result (Theorem 4) states a left-tail bound P(m^2 Z_N ≤ μN) ≤ exp(-mJ(μ)) for μ ≤ 1, and a right-tail bound P(m^2 Z_N ≥ λN) ≤ exp(-mJ(λ/2)+δ(m,N,2/λ)) for λ ≥ 2, where J(x)=1/x-1+log x and δ(m,N,c) ≤ (c+e^{-2})m^2/N is explicit. The proof proceeds by representing the registers as minima of multinomial allocations, proving an upper-orthant comparison with exponential variables (Lemma 9), deriving Laplace-transform bounds via a concavity argument (Lemma 10), and applying Chernoff-type optimizations (Proposition 8). An application to the MinCount algorithm is also given.

Significance. This is the first non-asymptotic, fully explicit exponential concentration result for the discrete HyperLogLog estimator, with no fitted constants. The proof is elementary and self-contained, relying on standard tools (multinomial allocation, stochastic orders, Chernoff bounds, Jensen). The bounds have immediate applications to one-sided confidence intervals and to the analysis of MinCount. The stochastic-averaging comparison in Lemma 9 and the concavity trick in Lemma 10 are elegant and potentially adaptable to other streaming algorithms. If correct, the paper fills a notable gap between the classical asymptotic bias/variance analysis of Flajolet et al. and the empirical observation that HyperLogLog has exponentially decaying tails.

minor comments (4)

[Theorem 4, Section 1.2] The right-tail statement is for all λ≥2, but the proof applies Proposition 8 with c=2/λ, which requires c<1. For λ=2 the bound is vacuous because δ(m,N,1)>0 makes the right-hand side exceed 1; please add a sentence covering this edge case or change the statement to λ>2 and note λ=2 separately.
[Throughout] The method is repeatedly spelled 'Chernov' (e.g., Section 2, Section 3.1, Section 3.2). The standard name is 'Chernoff' (Chernoff bound). Please correct.
[Algorithm 1 and Remark 1] The central theorem concerns the variant of Algorithm 1 with registers initialized to R[j]=1, which differs from the original HyperLogLog initialization (0 or −∞). While this is disclosed in Remark 1, the abstract and introduction refer simply to 'HyperLogLog'. Consider adding a qualifier in Theorem 4 or the introduction to avoid any misattribution of the non-asymptotic claim to the original initialization.
[Proof of Proposition 8, Eq. (14)] The bound δ(m,N,c) ≤ (c+e^{-2})m^2/N is correct, but the derivation can be made clearer by explicitly setting x = (N/m)(1/c-1), so that the second term equals (m^2/N)·x e^{-x-1}. This would help readers see that the inequality xe^{-x-1}≤e^{-2} applies directly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the concentration theorem is derived from scratch under a stated Random Oracle idealization, with no fitted constants and no load-bearing self-citation chain.

full rationale

The derivation chain is self-contained. Proposition 6 gives an exact distributional representation of Algorithm 1's Z_N under Hypothesis R-O; it is a modeling step, not a circular one. Lemma 9 proves the upper-orthant comparison by direct calculation from the multinomial counts, and Lemma 10 is a direct conditional Laplace estimate. Proposition 8 applies the Chernoff method together with the standard comparison theorem [21, Th.6.G.1], an external textbook result, and the final Theorem 4 follows by algebraic manipulation of the two-sided bound 1/(sum Y) <= Z_N <= 2/(sum Y). The rate function J and the correction delta are fully explicit; no parameter is fitted to data or to the target tail event, and no equation reduces to its own input by construction. The only self-citation, [3] (Chassaing-Gerin), appears in the optional MinCount section as background for an estimator form and is not needed for the main inequalities; even if removed, Proposition 8 would still imply Proposition 11. The register-initialization modification is disclosed in Remark 1 and the theorem is explicitly stated for that version of Algorithm 1, so this is a scoped condition rather than a hidden circular redefinition. The Random Oracle hypothesis is an explicit external idealization, inherited from the literature, and the theorem is conditional on it; that is an assumption, not a circular reuse of the conclusion.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The derivation is self-contained: no fitted constants, no hidden inputs beyond the Random Oracle model inherited from [10] and standard probabilistic machinery (Chernoff, Jensen, stochastic-order comparison [21, Th.6.G.1]). The only paper-specific choice is the register-initialization variant, which the author discloses and argues is asymptotically harmless for N ≫ m log m. α_m and β_m from [10] appear only in the motivational comparison of §1.2, not in the proofs.

assumptions (4)

domain assumption Random Oracle hypothesis: deduplicated hash values are i.i.d. Uniform(0,1)
Stated as Hypothesis R-O, §1.1 p.3, assumed 'as in [10]'. All bounds in Theorem 4 and Proposition 11 are conditional on it; real finite hash functions only approximate it.
standard math Upper-orthant order implies Laplace-transform comparison for products of increasing functions ([21, Th.6.G.1])
Invoked in the right-tail proof of Proposition 8, §3.1, to transfer the domination (Y_1,...,Y_m) ≼ m/N·(E_1,...,E_m) to exponential moments; cited to Shaked-Shanthikumar [21].
standard math Chernoff / exponential-moment bounding and Jensen's inequality for concave f_λ
Used throughout §3; the concavity of f_λ (f''_λ < 0 for λ > 1) is the load-bearing step in the left-tail inequality of §3.2.
ad hoc to paper Register-initialization variant R[j] ← 1
Algorithm 1, Line 4. Differs from [10]'s R ← 0 or −∞; justified by asymptotic insensitivity for N ≫ m log m. Theorem 4's non-asymptotic statement applies to this variant.

how reviews work

0 comments

Cite this review

Pith. "Pith review of HyperLogLog for probabilists." pith.science (2026). https://pith.science/paper/6D7DCUTF

@misc{pith2026260722063,
  author       = {Pith},
  title        = {Pith review of: HyperLogLog for probabilists},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6D7DCUTF}},
  note         = {Machine review of arXiv:2607.22063}
}

read the original abstract

HyperLogLog is a now classic probabilistic algorithm that provides an approximation of the number of distinct elements in a massive dataset, using only one pass over the data. In the original article, Flajolet, Fusy, Gandouet, Meunier (2007) provided a sharp analysis of the expectation and variance of the output, using explicit formulas analyzed using poissonization and Mellin transform. In this short article, we revisit the analysis of HyperLogLog with a more probabilistic viewpoint. This allows us to establish exponential deviation inequalities for the HyperLogLog estimator. The methods are elementary, but the estimates are non-asymptotic and totally explicit.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 2 linked inside Pith

[1]

The space complexity of approximating the frequency moments

Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 20--29, 1996

1996
[2]

Brands, F.W

J.J.A.M. Brands, F.W. Steutel, and R.J.G. Wilms. On the number of maxima in a discrete sample. Statistics & Probability Letters , 20(3):209--217, 1994

1994
[3]

Efficient estimation of the cardinality of large data sets

Philippe Chassaing and Lucas Gerin. Efficient estimation of the cardinality of large data sets. In Proceedings of 4th Colloquium on Mathematics and Computer Science (DMTCS Proceedings vol.AG) , pages 419--422, 2006

2006
[4]

A statistical analysis of probabilistic counting algorithms

Peter Clifford and Ioana A Cosma. A statistical analysis of probabilistic counting algorithms. Scandinavian Journal of Statistics , 39(1):1--14, 2012

2012
[5]

Loglog counting of large cardinalities

Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities. In European Symposium on Algorithms , pages 605--617. Springer, 2003

2003
[6]

Algorithms

Jeff Erickson. Algorithms . 2023. Director's cut (available at https://jeffe.cs.illinois.edu/teaching/algorithms/)

2023
[7]

New cardinality estimation algorithms for hyperloglog sketches

Otmar Ertl. New cardinality estimation algorithms for hyperloglog sketches. 2017. arXiv:1702.01284

arXiv 2017
[8]

Counting by coin tossings

Philippe Flajolet. Counting by coin tossings. In Annual Asian Computing Science Conference , pages 1--12. Springer, 2004

2004

Show all 23 references

[9]

Probabilistic counting algorithms for data base applications

Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences , 31(2):182--209, 1985

1985
[10]

Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm

Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science , DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA ...

2007
[11]

Order statistics and estimating cardinalities of massive data sets

Fr \'e d \'e ric Giroire. Order statistics and estimating cardinalities of massive data sets. Discrete Applied Mathematics , 157(2):406--427, 2009

2009
[12]

Cardinality estimation: An experimental survey

Hazar Harmouch and Felix Naumann. Cardinality estimation: An experimental survey. Proceedings of the VLDB Endowment , 11(4):499--512, 2017

2017
[13]

Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm

Stefan Heule, Marc Nunkesser, and Alexander Hall. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In Proceedings of the 16th International Conference on Extending Database Technology , pages 683--692, 2013

2013
[14]

Tight lower bounds for the distinct elements problem

Piotr Indyk and David Woodruff. Tight lower bounds for the distinct elements problem. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. , pages 283--288. IEEE, 2003

2003
[15]

An optimal algorithm for the distinct elements problem

Daniel M Kane, Jelani Nelson, and David P Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages 41--52, 2010

2010
[16]

Cardinality estimation using G umbel distribution

Aleksander ukasiewicz and Przemys aw Uzna \'n ski. Cardinality estimation using G umbel distribution. In 30th Annual European Symposium on Algorithms (ESA 2022) , pages 76:1--76:13, 2022

2022
[17]

An optimal cardinality estimation algorithm based on order statistics and its full analysis

J \'e r \'e mie Lumbroso. An optimal cardinality estimation algorithm based on order statistics and its full analysis. Discrete Mathematics & Theoretical Computer Science , DMTCS Proceedings vol. AM, 2010 Conference on Analysis of Algorithms (AofA 10), 2010

2010
[18]

The story of H yperloglog: How F lajolet processed streams with coin flips

J \'e r \'e mie Lumbroso. The story of H yperloglog: How F lajolet processed streams with coin flips. 2018. arXiv:1805.00612

2018 arXiv
[19]

Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis

Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge U niversity P ress, 2017

2017
[20]

Information theoretic limits of cardinality estimation: F isher meets S hannon

Seth Pettie and Dingyu Wang. Information theoretic limits of cardinality estimation: F isher meets S hannon. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 556--569, 2021

2021
[21]

Shaked and J.G

M. Shaked and J.G. Shanthikumar. Stochastic Orders . Springer Series in Statistics. Springer New York, 2007

2007
[22]

Big Q uery documentation: H yperloglog++ functions

BigQuery . Big Q uery documentation: H yperloglog++ functions. https://docs.cloud.google.com/bigquery/docs/reference/standard-sql/hll_functions (Accessed: 2026-06-03)

2026
[23]

Redis documentation: H yperloglog

Redis . Redis documentation: H yperloglog. https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/ (Accessed: 2026-06-03)

2026

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

The space complexity of approximating the frequency moments

Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 20--29, 1996

1996

[2] [2]

Brands, F.W

J.J.A.M. Brands, F.W. Steutel, and R.J.G. Wilms. On the number of maxima in a discrete sample. Statistics & Probability Letters , 20(3):209--217, 1994

1994

[3] [3]

Efficient estimation of the cardinality of large data sets

Philippe Chassaing and Lucas Gerin. Efficient estimation of the cardinality of large data sets. In Proceedings of 4th Colloquium on Mathematics and Computer Science (DMTCS Proceedings vol.AG) , pages 419--422, 2006

2006

[4] [4]

A statistical analysis of probabilistic counting algorithms

Peter Clifford and Ioana A Cosma. A statistical analysis of probabilistic counting algorithms. Scandinavian Journal of Statistics , 39(1):1--14, 2012

2012

[5] [5]

Loglog counting of large cardinalities

Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities. In European Symposium on Algorithms , pages 605--617. Springer, 2003

2003

[6] [6]

Algorithms

Jeff Erickson. Algorithms . 2023. Director's cut (available at https://jeffe.cs.illinois.edu/teaching/algorithms/)

2023

[7] [7]

New cardinality estimation algorithms for hyperloglog sketches

Otmar Ertl. New cardinality estimation algorithms for hyperloglog sketches. 2017. arXiv:1702.01284

arXiv 2017

[8] [8]

Counting by coin tossings

Philippe Flajolet. Counting by coin tossings. In Annual Asian Computing Science Conference , pages 1--12. Springer, 2004

2004