The correction that makes it work

The registers hold what they hold. Splitting the hash gives $m$ of them, each holding the longest run of leading zeros among the keys that landed there, and turning those $m$ small integers into one estimate of the cardinality is a separate problem with more than one answer.

Two answers use exactly the same state, the same updates and the same hash, and differ only in an arithmetic performed at query time. One of them is 30% more accurate than the other, for nothing.

The arithmetic mean is the obvious one and it is the wrong one #

If register $j$ holds $M_j$, then $2^{M_j}$ is an estimate of how many distinct keys landed in that register, and $m \cdot 2^{\bar{M}}$ — with $\bar M$ the average register value, corrected by a constant — is an estimate of the total. That is LogLog, and it is the arithmetic that anybody writes down first.

Its problem is that the register values are logarithms and their average is a geometric mean of the underlying counts. A geometric mean is dominated by whichever register happened to see the longest run of zeros: one register at 20 where the rest are at 9 pulls the average up by more than a whole unit, which multiplies the estimate by more than two, and long runs of zeros are precisely the events the structure is built to notice.

So the estimator’s variance is driven by its own most extreme observation, which is the same defect one register had before there were $m$ of them. Averaging has reduced it and has not removed it.

The harmonic mean, on identical bits #

HyperLogLog’s answer is to average $2^{-M_j}$ instead and invert:

$$\hat{D} = \alpha_m \, \frac{m^2}{\sum_j 2^{-M_j}}.$$

A register with a large $M_j$ contributes a small term to that sum, so it can lower the denominator only so far — its influence is bounded above rather than unbounded. The estimator stops being at the mercy of its outlier and the variance falls.

The measurement, over forty runs at a thousand registers on fifty thousand distinct keys: 3.1% for the harmonic mean against 4.0% for the arithmetic one. A gain of 1.29 times, on the same registers, the same stream and the same seed — no extra bits, no extra hashes, no extra passes.

There is a way of reading the improvement that makes it feel less like a trick. The quantity being estimated is a count, and the registers hold logarithms of counts. Averaging in log space and then exponentiating estimates the geometric mean of the per-register counts; averaging the reciprocals estimates their harmonic mean; and it is a fact about extreme-value distributions that the harmonic mean is the better-behaved of the two when the underlying quantity is exponential in a maximum. The constant $\alpha_m$ is what puts the answer back on scale afterwards, and it is tabulated for small $m$ and given by $0.7213/(1 + 1.079/m)$ beyond.

At low cardinality the whole thing is wrong #

The derivation assumes each register has seen a good number of keys. When it has not, the estimator is not slightly imprecise — it is badly biased in a stated direction.

With a thousand registers and four hundred distinct keys, six hundred registers have seen nothing at all and hold zero. Each contributes $2^0 = 1$ to the sum in the denominator, which is the largest contribution any register can make, so the denominator is dominated by registers that have no information in them and the estimate comes out 137% high on average.

The repair is a different estimator #

The fix is not a correction factor. It is a switch: below a threshold, stop using the leading-zeros estimator and count the empty registers instead.

If $V$ registers out of $m$ are still zero, then each was missed by every one of $D$ keys, which happens with probability $(1 - 1/m)^D \approx e^{-D/m}$. So

$$\hat{D} = m \ln \frac{m}{V},$$

which is linear counting — an estimator that has nothing to do with leading zeros, treats each register as a single bit of a bitmap, and is at its best exactly where the other is at its worst.

The threshold in the published algorithm is $2.5m$: below that raw estimate, and provided some register is still empty, use linear counting. On the measurement above the bias falls from 137% to 0.3%, which is the difference between an unusable structure and a working one across two decades of cardinality.

Two things about this are worth naming because they generalise.

A structure’s specification includes its estimator, and the estimator can be piecewise. The HyperLogLog that gets deployed is two estimators and a threshold, and quoting $1.04/\sqrt m$ for it describes only one of the two pieces. This is the same shape as the library sorts in the practice field — the sort the library ships is a policy with thresholds rather than an algorithm — arriving in a place where the thresholds decide accuracy rather than speed.

The threshold is a number somebody chose. $2.5m$ is not derived; it is where the two estimators’ errors cross on the data the authors measured, and the later literature replaced it with an empirical bias table and then with a different estimator altogether. That is the field’s own admission that the constant matters, and the threshold is the algorithm is the thread this site already runs on that observation.

What a threshold does to a structure’s specification #

Switching estimators at $2.5m$ has a consequence that is easy to miss and is the reason the practice field exists on this site: the deployed structure has no single error law.

Below the threshold it is a linear counter, whose relative error goes as $\sqrt{(e^{D/m} - D/m - 1)}/D \cdot m$ — a different formula, with a different shape, that gets worse rather than better as the cardinality rises. Above it, $1.04/\sqrt m$. At the threshold the two are stitched together, and near the seam neither describes the behaviour well, which is why the published algorithm was later given an empirical bias table for exactly that region.

A structure whose accuracy is described by two formulas and a constant is a policy rather than an algorithm, in precisely the sense the sort the library ships means it. And it has the same consequence: a benchmark run entirely on one side of the threshold measures one of the two, and reports it as the structure’s accuracy.

The high end, and what the corrections cannot fix #

The original algorithm also carries a large-range correction, for cardinalities approaching the size of the hash space, and it is a different kind of repair.

With a 32-bit hash there are about four billion possible values, so once the cardinality reaches a few hundred million, distinct keys begin to share hashes and the structure cannot tell them apart. The correction — $-2^{32}\ln(1 - E/2^{32})$ — is a coupon-collector adjustment that undoes the expected number of collisions, and it works for a while and then stops meaning anything.

The real fix is a wider hash, and it is the reason production implementations use 64 bits and six-bit registers. It is worth being clear that this is not a subtlety of the estimator: it is the observation that a structure whose whole premise is that distinct keys look distinct stops working when they do not. No arithmetic performed on the registers can recover information that two keys destroyed by colliding.

What is being measured, and what is being assumed #

This essay’s central claim — that the harmonic mean is worth 30% — is a comparison, and comparisons are the easiest thing to arrange. Three things fix it.

The two estimators read the same object. Not two structures configured to be the same size: literally the same registers, populated by the same run, with the estimator swapped at query time. Any difference is therefore the arithmetic and cannot be anything else.

The comparison is over forty seeds, because a single run of either would be a draw from a distribution, and the quantity being compared is the width of two distributions.

And the direction is asserted rather than the magnitude. The gate requires the harmonic mean to be better and does not require it to be better by any particular amount, because the amount depends on $m$ and on the stream and a fixed number would be a tolerance rather than a claim.

What one run is worth, at four settings #

Every number above is one run, and a randomised estimator’s accuracy is a property of its distribution rather than of any run of it. The same sixty-seed sweep, four ways.

The cardinality is the second dial, and it is the one a deployment cannot choose. If the band moved with it the estimator would need re-sizing for every stream.

The last of the four changes the estimator rather than its setting, which is the comparison the whole page is for: two structures given exactly the same bits.

The register that is a Morris counter #

It is worth closing the loop with the first structure in this field, because the resemblance is exact rather than poetic.

A Morris counter increments with probability $2^{-c}$, so it advances when a coin comes up heads $c$ times in a row. A HyperLogLog register advances when a key’s hash begins with $c$ zeros. Both hold a small integer that is the logarithm of what is being counted; both are read by exponentiating; both have a relative error of order one on their own; and both are fixed by combining many of them.

The difference is where the randomness comes from, and it is the whole reason one counts events and the other counts distinct keys. Morris’s coin is fresh for every item, so a repeated item can advance the register again. A hash is a function of the key, so a repeated key cannot. That single change of source turns a counter into a set-size estimator, and it is the neatest illustration in this field of what these structures actually are — a statistic chosen in advance, and a rule for updating it that makes the statistic mean what it is supposed to mean.

What the essay claims and what it does not #

Two claims here are measurements and one is arithmetic, and separating them is worth a paragraph.

The harmonic mean is better on identical registers. A measurement, over forty seeds, with the estimator swapped at query time on the same object. The gate asserts the direction and not the magnitude.

The small-range correction removes a bias. A measurement, over thirty seeds at a cardinality well below the register count, comparing the corrected estimator’s mean signed error against the raw one’s. 137% against 0.3%.

$\alpha_m$ and the $2.5m$ threshold are quoted. Neither is derived here and neither is fitted; they are the published constants, used as published, and printed on the plates. Deriving $\alpha_m$ requires an integral over the limiting distribution of the registers, and refitting it against the streams measured here would produce a structure that agrees with itself and with nothing anybody else runs — which is the failure mode a site that fits its own constants has to be careful about.

That last point deserves a sentence more, because it is the one place where this site’s method and this structure’s design pull against each other. The habit here is to measure a constant rather than accept one. But a constant fitted to the data it is then evaluated on is not a measurement of anything: it will fit, the residual will be small, and the exercise will have established that a two-parameter family can be fitted with two parameters. So $\alpha_m$ is taken as published and the thing measured is whether the structure using it lands where the analysis says — which is a claim that can fail, and did not.

The zeros are informative twice #

The small-range switch rests on an observation that is worth pulling out on its own, because the same observation solves a second problem the essay has not mentioned.

At low cardinality most registers are zero. The switch uses that for accuracy — the number of zeros is a sufficient statistic for the cardinality, and reading it is a better estimator than exponentiating anything.

The same fact is available for space. A structure with a thousand registers of which six hundred hold zero is storing six hundred zeros at five bits each, which is three thousand bits of nothing. Keeping only the non-empty registers as (index, value) pairs costs about fifteen bits each and is smaller than the dense array until roughly a third of the registers are occupied.

So a structure that is going to spend its early life below the threshold can spend it in a sparse representation and convert to the dense one when the occupancy justifies it — which is exactly what the production variants do, and which is why a HyperLogLog counting a hundred distinct keys need not occupy the same bytes as one counting a hundred million.

The two uses of the zeros are the same fact read for two different resources, and they arrive at the same threshold from opposite directions: the estimator switches when there are too many zeros to exponentiate, and the representation switches when there are too few zeros to be worth compressing. That coincidence is not deep — both are governed by the occupancy $1 - e^{-D/m}$ — and it is a tidy illustration of this collection’s standing point that a structure has more than one axis and that the interesting design decisions move both.

Unbiased in the limit, and the limit is the register count #

There is a third correction in the published algorithm and the essay has treated it as a constant rather than as a repair. It is worth reclassifying.

$\alpha_m$ exists because the harmonic-mean estimator, without it, is biased: the expectation of $m^2 / \sum 2^{-M_j}$ is not the cardinality but a fixed multiple of it, and the multiple depends on $m$. The published $\alpha_m = 0.7213/(1 + 1.079/m)$ is that multiple, computed from an integral over the limiting distribution of the registers, and it is exact only as $m \to \infty$.

So the deployed structure is asymptotically unbiased in its register count, and slightly biased at any finite $m$ — with the bias largest where $m$ is smallest, which is the regime a memory-constrained deployment is in. The later empirical bias tables exist to correct exactly that residue, and they are tables rather than formulas because nobody found a closed form for it.

That gives the structure three corrections rather than two, and they are three different kinds of thing: a switch at low cardinality, which changes the estimator; a scale factor in the middle, which corrects a bias in the estimator that is used; and a coupon-collector adjustment at the top, which corrects for the hash rather than for the arithmetic. Only the first is usually described as a correction, and the essay above followed that convention until this paragraph.

The reason to separate them is that they fail in different ways. The switch fails by being applied at the wrong threshold, which is a tuning question. The scale factor fails by being computed for a different $m$ than the one in use, which is an implementation bug and a common one. The high-range adjustment fails by being asked to recover information that two colliding keys destroyed, which nothing can repair.

What was left alone #

The later literature has moved past both corrections. HyperLogLog++ replaced the small-range switch with an empirically tabulated bias correction and a sparse representation for low cardinalities; other work replaced the estimator entirely with a maximum-likelihood fit over the register histogram, removing the piecewise structure and the constants together.

None of that is implemented here, and the reason is the same one the coding field gave for leaving out context mixing: those variants differ in exactly the ways that decide a comparison between them, so running one of them against the version above and reporting a difference would be reporting a property of two implementations rather than of two designs. What is measured on this page is the original algorithm as published, and what is claimed is about that.

The direction is worth naming even so, because it says what the corrections are: scaffolding around an estimator that is right in the middle of its range and wrong at both ends. Every improvement since has been an attack on one of the two ends, and the harmonic mean in the middle has not been improved on.