A floor on the bits

Every floor on this site so far has been a floor on time. Comparison sorting needs $\log_2(n!)$ comparisons; connectivity needs to read every edge; the floor moves when the question does and again when the values repeat. Five essays, one resource.

This is a floor on space, and it differs from the others in a way that matters more than the change of axis. The comparison-sorting floor is a bound nothing gets near — the best sorts sit a few per cent above it and the ordinary ones are off by factors that grow with $n$ — so it functions mostly as a proof of impossibility. This one is a bound that a structure people actually deploy sits 44% above, at every accuracy, for a reason with a name. That makes it a design target rather than a curiosity.

The argument, in full #

The bound is a counting argument and it is short enough to give completely, which is the standard this site holds a floor to.

Fix a universe of $U$ possible keys and a set $S$ of $n$ of them. A structure answering approximate membership must say yes to every element of $S$ — no false negatives — and may say yes to some elements outside $S$, subject to doing so for at most a fraction $\varepsilon$ of them.

Now look at what the structure’s memory contents determine. Whatever the bits say, they determine a set of keys the structure answers yes to — call it $A$. Correctness requires $S \subseteq A$, and the false-positive constraint requires $|A| \le n + \varepsilon(U - n)$, which for large $U$ is about $\varepsilon U$.

So each possible memory state accepts a set of size at most $\varepsilon U$, and every one of the $\binom{U}{n}$ possible sets $S$ must be covered by at least one state. One state can cover at most $\binom{\varepsilon U}{n}$ different sets — the subsets of size $n$ inside its accepted set. Therefore the number of distinct memory states needed is at least

$$\frac{\binom{U}{n}}{\binom{\varepsilon U}{n}} \approx \varepsilon^{-n}$$

and the number of bits is the logarithm of that:

$$m \ge n\log_2\frac{1}{\varepsilon}$$

The approximation in the middle is the usual one for $U \gg n$; the result is exact in the limit and close enough at any real universe size. The number is per element and it does not involve $U$ at all, which is the surprising part of the statement: the size of the universe drops out. Storing the keys exactly would cost $\log_2 U$ bits each and grow as the keys get wider; accepting an $\varepsilon$ of error costs $\log_2(1/\varepsilon)$ bits each regardless of how wide the keys are.

That is the whole reason approximate membership structures exist. At $\varepsilon = 1\%$ the floor is 6.64 bits per key whether the keys are 32-bit integers, 64-bit hashes or 200-byte URLs.

What the floor says at each rate #

Two shapes in this table are worth naming.

The floor is logarithmic in the rate. Each factor of ten in accuracy costs $\log_2 10 = 3.32$ more bits per element. That is a very good exchange rate and it is why filters are used at all: going from 1% to 0.1% error costs 3.3 bits per key, which on a million keys is 415 kilobytes. The alternative — being wrong ten times less often by holding the keys — costs whatever the keys cost.

The overhead is a constant. 1.4427 at every row, to five figures. A Bloom filter is not closer to optimal at loose rates or at tight ones; it is $1/\ln 2$ times the floor everywhere. That is checked rather than asserted — assertTheFilterFloorHolds requires the ratios across four rates to span less than 1.001, so a change that made the overhead drift would fail the build.

Where the 44% comes from #

The constant is not arbitrary and its derivation explains what a Bloom filter is doing wrong, in the specific sense of what a better structure would do differently.

At its optimal $k$, a Bloom filter’s table is exactly half full: the fill is $1 - e^{-kn/m}$ and substituting $k = (m/n)\ln 2$ gives $1 - e^{-\ln 2} = \tfrac12$. That is not a coincidence, it is what optimising $k$ does — the rate $f^k$ is minimised where the marginal cost of setting more bits balances the marginal benefit of requiring more of them to agree, and that point is $f = \tfrac12$.

A table that is half full of ones, with the ones in no particular pattern, holds exactly one bit of entropy per bit of storage. So the Bloom filter is at least using its bits at full information density — the waste is not there. The waste is that the information it stores is not only the membership information. A specific pattern of set bits records which keys were inserted and which of the $k$ hash slots each of them happened to land in, and the second part is noise the query does not need. The structure is spending bits on a record of its own arbitrary choices.

$1/\ln 2$ is how much of the storage that costs, and it is why the better constructions are all built the same way: store a fingerprint, not a footprint. A cuckoo filter or a quotient filter stores, per key, a short hash of the key in a slot chosen by another part of the same hash — so the bits record the key’s identity rather than the positions it happened to occupy. Those structures reach about 1.05 to 1.2 times the floor, and the extra machinery they need — displacement, a load factor below one, a bounded insertion loop — is what the 25% of space buys.

The same argument, twice #

It is worth putting this derivation beside the comparison-sorting one, because they are the same argument in different clothes and seeing that is worth more than either on its own.

Comparison sorting. A sort must be able to produce any of $n!$ orderings. Each comparison has two outcomes, so a decision tree of depth $d$ has at most $2^d$ leaves. To have $n!$ leaves it needs $d \ge \log_2(n!)$. The resource is comparisons and the counting is over outcomes the algorithm must distinguish.

Approximate membership. A filter must be able to represent any of $\binom{U}{n}$ sets. Each memory state accepts at most $\varepsilon U$ keys and so covers at most $\binom{\varepsilon U}{n}$ sets. To cover them all it needs $\varepsilon^{-n}$ states, hence $n\log_2(1/\varepsilon)$ bits. The resource is bits and the counting is over inputs the structure must distinguish.

Both are the same three-step shape: count the things that must come out differently, count how many the mechanism can separate per unit of resource, divide. That shape is what an information-theoretic bound is, and it is why it applies to algorithms nobody has written — it never mentions an algorithm, only what the answer has to distinguish.

The difference is what the resource is bought with. A comparison buys one bit of discrimination and an algorithm can waste it by asking a question whose answer it could have predicted. A bit of storage buys one bit of state and a structure wastes it by recording something the query does not ask about. Bloom filters waste in the second way, by 44%, and the previous section says exactly what they are recording that nobody needs.

The bound with numbers in it #

The derivation is cleaner with a concrete universe, and the numbers are small enough to check by hand.

Take a universe of one million possible keys and a set of ten thousand of them, with $\varepsilon = 1\%$. Then:

• There are $\binom{10^6}{10^4}$ possible sets, which is $2^{80{,}785}$.
• Each memory state accepts at most $1\% \times 10^6 = 10^4$ keys plus the $10^4$ real ones, and so covers at most $\binom{2\times 10^4}{10^4} = 2^{19{,}993}$ sets.
• The ratio needs at least $80{,}785 - 19{,}993 = \textbf{60{,}792 bits}$.
• Divided by the ten thousand keys: 6.08 bits per key.

The asymptotic formula says $\log_2 100 = 6.64$. The exact count comes out lower because the universe is only a hundred times the set, so being allowed to accept 1% of the universe is a large allowance relative to $n$ — the accepted set may be twice the size of $S$ rather than a negligible amount bigger. Widening the universe closes the gap:

So $n\log_2(1/\varepsilon)$ is the large-universe limit, and at a small universe the true floor is lower. In the extreme, if the universe is only twice the set size, a bitmap of $U$ bits answers exactly and costs 2 bits per key, well under the “floor” of 6.64 — because at that ratio the counting argument’s approximation has broken down entirely. The formula is a floor for the regime it is derived in, which is the one every real filter is in: keys drawn from 64-bit hashes or from URLs, where $U$ is astronomically larger than $n$ and the limit is reached to four figures.

The condition is not that the universe is large #

“$n\log_2(1/\varepsilon)$ is the large-universe limit” is the right reading of that table, and the condition it names is the wrong one. The universe being large is not what makes the limit accurate; what matters is the accepted set being large relative to $n$.

The correction is computable. Expanding the exact ratio $\binom{U}{n}/\binom{\varepsilon U}{n}$ to the next order gives a per-key floor of

$$\log_2\frac{1}{\varepsilon} \;-\; \frac{n}{2U\ln 2}\left(\frac{1}{\varepsilon} - 1\right),$$

and the subtracted term is exactly what the table measures. At $U = 10^7$ with $n = 10^4$ and $\varepsilon = 0.01$ it is 0.071 bits, giving 6.573 against the measured 6.573. At $U = 10^9$ it is 0.0007, giving 6.6433 against 6.643. Both to the digit.

Now read the correction’s shape. It is $n/(2U\ln 2)$ times $1/\varepsilon$, which is $n/(2\varepsilon U \ln 2)$ — a function of $n$ divided by $\varepsilon U$, the size of the accepted set. So the asymptotic floor is accurate exactly when $\varepsilon U \gg n$, and the universe’s size enters only through that product.

That is a considerably stronger demand than $U \gg n$ when the rate is tight. At $\varepsilon = 10^{-4}$ and a million keys, $\varepsilon U \ge 10n$ needs a universe of $10^{11}$; below that the true floor is measurably under $\log_2(1/\varepsilon)$ and a structure is permitted to be smaller than the quoted bound. The row of the table where the formula visibly fails is the one where $\varepsilon U$ equals $n$ exactly — a million-key universe at one per cent accepts ten thousand keys and holds ten thousand real ones, so the accepted set is barely twice $S$ and the counting argument’s slack has run out.

Two things follow.

The bound as usually quoted has an unstated hypothesis, and it is the one that fails first in the direction people care about. Tightening $\varepsilon$ is the standard way to make a filter better, and tightening it is what pushes the deployment out of the regime the floor was derived in. A design that reaches for $10^{-6}$ on a modest universe is not merely asking for a lot of bits; it may be asking for a bound that does not apply.

And the direction is the friendly one. The exact floor is always at or below the asymptotic one, so quoting $n\log_2(1/\varepsilon)$ never claims a structure is impossible when it is merely hard. It over-states the irreducible cost, by an amount that is negligible whenever $\varepsilon U$ is a few times $n$ and is a substantial fraction of a bit when it is not.

Which is the same lesson the floor moves when the question does draws about counting sort, arriving here as a continuous version of it: the problem’s parameters do not merely decide which floor applies, they decide by how much the standard one over-shoots. And it is the second time a filter allowed to be wrong’s arithmetic has turned out to hinge on $\varepsilon U$ rather than on $U$ — the first being that the fill, not the universe, is what the rate is a power of.

What kind of bound this is #

It is worth being precise about the logical status, because the site distinguishes carefully between what is proved and what is measured, and this essay’s two numbers have different statuses.

The floor is proved. The counting argument above is complete. It applies to every structure that answers approximate membership with one-sided error at rate $\varepsilon$, including ones nobody has written, and it does not depend on any model of computation beyond the structure having a finite memory whose contents determine its answers. Nothing measurable can refute it, and if a measurement ever appeared to, the conclusion would be that the measurement is wrong.

The 9.59 is measured. $\log_2(1/\varepsilon)/\ln 2$ is the space a Bloom filter needs at its optimal $k$ under the standard analysis, and the standard analysis contains approximations whose size has been measured and is a few per cent on random keys and 30% on structured ones. So the filled bar in the figure is a theorem and the outlined bar is a good estimate.

That last calculation is the one to keep, because it shows the floor being used as a measuring instrument rather than as a fact. Take any filter at all, measure its rate, compute $\log_2(1/\varepsilon)$, and divide into the space it actually occupies. The answer is how far above optimal that specific built object is, and it takes one measurement and one logarithm.

The same two lines, over three ranges #

The gap between the floor and the filter is $1/\ln 2 = 1.44$, a constant — and a constant is the kind of claim that is worth reading over more than one range.

The tight end is the half that matters to anybody sizing a filter for a cache or a router, and it is four orders of magnitude away from the plate above.

And three points spanning the whole of it are enough to read the constant off directly, which is the cheapest form the claim takes.

The floors field, now with two axes #

This is the fifth distinct floor on the site and the first on a resource other than time, so it is worth setting the collection side by side. The interesting comparison is not the bounds but how close anything gets to them.

Three of the four are nearly tight, which is the useful observation. A lower bound that nothing approaches is a statement about the problem; a lower bound that something approaches is a statement about the algorithm, and it converts “is this good?” from a comparison against other implementations into a comparison against what is possible.

Using the floor while sizing #

The bound has a practical use that is separate from its role as a proof, and it takes one line of arithmetic.

Whenever a filter is specified — 1% false positives on fifty million keys, say — the floor immediately gives the irreducible cost: $50 \times 10^6 \times 6.64 / 8 = 41.5$ megabytes. Any structure meeting that specification is at least that large, so if the budget is 30 megabytes the specification is impossible and no amount of implementation cleverness will rescue it. That is worth knowing in the first minute of a design rather than the last.

Then the Bloom number, 59.9 megabytes, says what the standard answer costs, and the ratio between them — 1.44 — is the entire space of improvement available from choosing a different structure. If 60 megabytes is affordable, the conversation is over and a Bloom filter is the right answer because it is the simplest. If 45 is affordable and 60 is not, the 1.44 is exactly the gap a cuckoo filter closes, and the extra complexity is now justified by a number rather than by a preference.

That is the general use of a tight lower bound, and it is the reason this one is more useful than the comparison-sorting floor despite being a weaker-sounding statement. Knowing that sorting cannot beat $\log_2(n!)$ rarely changes what anyone does, because the available sorts are already within a few per cent of it and the choice between them turns on other things entirely. Knowing that membership cannot beat $n\log_2(1/\varepsilon)$ decides, immediately, whether a proposed budget is feasible and how much a better structure could possibly buy.

What the bound does not cover #

Three exclusions, each of which is a real structure the bound does not constrain.

Two-sided error. The argument assumed no false negatives. A structure permitted to be wrong in both directions can be smaller — considerably so, since the accepted set no longer has to contain $S$ — and that is a different problem with a different floor.

Queries from a known distribution. The bound counts all $\binom{U}{n}$ sets as equally likely. If the queries are known to concentrate on a small part of the universe, a structure can be sized against that and the counting argument’s premise is gone. This is the same escape as counting sort’s: the floor holds for the problem as stated, and stating a narrower problem moves it.

Structures that can be rebuilt from the keys. A perfect-hash-plus-fingerprint arrangement sits essentially on the floor and needs the whole key set in advance to build the perfect hash. So the honest version of the comparison is “among structures supporting one-at-a-time insertion”, and within that class the 1.05× of the cuckoo and quotient filters is the number to beat.

None of those weakens the bound; each of them names a hypothesis it depends on, which is what a floor is made of. The one it does not depend on is the size of the universe, and that remains the surprising part: the price of approximate membership is set entirely by how often the answer is allowed to be wrong.