A cuckoo filter wins when it's full
The cuckoo filter paper says it uses less space than a Bloom filter whenever you want a false positive rate under about 3%. I simulated cuckoo filters and checked that claim. The number is right, but it assumes two things: the filter is about 95% full, and it uses semi-sorting, a bucket-compression trick that the reference library leaves off by default. Without semi-sorting the break-even drops to 0.46%. And because the table size has to be a power of two, a filter holding the number of items it was sized for usually sits well below 95%. At that point the Bloom filter is smaller.
The setup
A cuckoo filter stores a short fingerprint of each item (f bits) in a table of buckets with b slots each. An item can live in one of two buckets: i1 from its hash, and i2 = i1 XOR hash(fingerprint). That XOR is the trick that makes it a filter: you can find a fingerprint's other bucket without the original item. When both buckets are full, an insert kicks a random resident to its other bucket, which may kick another, and gives up after a fixed number of kicks. The reference implementation uses b = 4, 500 kicks, a bucket count rounded up to a power of two (so the XOR stays in range), and doubles the table if the requested capacity would fill it past 96%.
My simulator fills a table with random items until the first insert fails, then queries 200,000 items that were never inserted to measure the false positive rate. The main sweep hashes the fingerprint with a bit mixer to get the second bucket; a second sweep uses the library's exact formula. A baseline mode gives every item an independent random second bucket, which is what a cuckoo hash table storing whole keys would do. Tables from 210 to 224 buckets, bucket sizes 2, 4 and 8, fingerprints 2 to 16 bits, 10 to 20 seeds per setting.
Sanity check: the measured false positive rate matches the textbook 1 − (1 − 1/(2f−1))2b·load to within 2.3% for 8- and 12-bit fingerprints at every table size (2.96% against 2.97% for 8 bits at 220 buckets). The 16-bit rates are within 9%, which is the noise you'd expect from a couple of hundred hits.
How full it gets
With 4-slot buckets and 500 kicks, the first failure comes at about 97% full in a small table and 95.5% in a big one. With 12- or 16-bit fingerprints the filter behaves the same as the random-second-bucket baseline to within 0.3 points, so the XOR trick costs nothing there. The library's own formula gave the same loads to within 0.2 points.
| Buckets | b = 2 | b = 4 | b = 8 |
|---|---|---|---|
| 210 | 88.8% | 97.2% | 99.4% |
| 216 | 87.4% | 96.2% | 99.0% |
| 220 | 86.6% | 95.9% | 98.6% |
| 224 | 86.2% | 95.5% | 98.4% |
Mean load at the first failed insert, 16-bit fingerprints, 500 kicks, 10 seeds (7 for b = 8 at 224).
The drop with size comes from the kick limit, not from the table. Bigger tables need longer chains of kicks near the end, and 500 cuts more of them off:
| Kick limit | 214 buckets | 222 buckets |
|---|---|---|
| 100 | 93.2% | 90.7% |
| 500 | 96.6% | 95.5% |
| 2,000 | 97.5% | 97.1% |
| 8,000 | 97.8% | 97.7% |
Baseline mode (random second bucket), b = 4, 5 seeds.
This interacts with the library's 96% doubling rule. If you ask for a capacity that lands just under it, say 95.8% of a power-of-two table, the table isn't doubled, and in my runs it couldn't hold that many items: with 8-bit fingerprints, 35% of seeds failed before 96% at 218 buckets, 90% at 220, and all of them from 222 up. The library parks the one item that didn't fit in a single spare slot, so lookups stay correct, but the next insert reports the filter as full. Only capacities in a narrow band right under the threshold are affected. With 2,000 kicks, every run up to 222 buckets got past 96.8%.
Short fingerprints hit a wall
A fingerprint can only ever sit in its pair of buckets. With f bits there are only 2f−1 fingerprints, and items with the same fingerprint and the same pair of buckets have nowhere else to go. With 4-slot buckets, nine of them don't fit. More kicks can't help: one 224-bucket table with 4-bit fingerprints failed at 55% full with 500, 5,000 and 50,000 kicks, and at the point of failure both buckets held four copies of the same fingerprint, with a ninth one left over.
The odds follow from a Poisson count: each (pair, fingerprint) gets on average 2b·load/(2f−1) items, and there are buckets·(2f−1)/2 of them. For 4-bit fingerprints in 224 buckets that predicts a 42% chance of an overfull pair before 97% load; drawing the items without building the table, 10 of 20 seeds got one, the earliest at 55%. The same count gives 0.4% by 55%, so that seed was an unlucky draw rather than a different effect. As the table grows, the minimum safe fingerprint grows with it: with 4-slot buckets, 3-bit fingerprints fell from 88% full at 210 buckets to 46% at 224. From about 6 bits up, nothing changes for the table sizes I tried, and the usual settings start at 8 bits, so this is a limit you only meet if you try to squeeze.
Against a Bloom filter
A cuckoo filter at load α costs f/α bits per item (one bit less with semi-sorting, which sorts each 4-slot bucket and packs it into fewer bits). Its false positive rate also falls when it's less full, so the fair comparison is against a Bloom filter tuned to whatever rate the cuckoo filter actually delivers. I used the Bloom filter's best integer number of hash functions at that rate.
| Load | Cuckoo, 12-bit | FPR | Bloom, same FPR |
|---|---|---|---|
| 95.5% | 12.6 bits | 0.19% | 13.1 bits |
| 84% | 14.3 bits | 0.16% | 13.4 bits |
| 72% | 16.7 bits | 0.14% | 13.7 bits |
| 48% | 25.0 bits | 0.09% | 14.5 bits |
Bits per item with b = 4, no semi-sorting.
Solving for the break-even at 95.5% load: with semi-sorting it's 2.95%, the paper's 3%. Without it, 0.46%. At 90% load, 1.39% and 0.13%.
Power-of-two sizing is the bigger effect. Under the library's rule, a filter built for capacity n runs between 48% and 96% full once it holds n items, depending on where n falls between powers of two. Spreading capacities evenly on a log scale from a thousand to sixteen million items, the median load at capacity was 68%. Over that spread, the cuckoo filter was the smaller of the two for:
| Fingerprint | Plain | Semi-sorted |
|---|---|---|
| 8 bits | 0% of sizes (1.48× Bloom on average) | 1% (1.30×) |
| 12 bits | 8% (1.30×) | 23% (1.19×) |
| 16 bits | 20% (1.22×) | 30% (1.15×) |
What I'd take from it
- The 3% figure is right, for a semi-sorted filter at 95% load. A plain one at 95% load needs a target under about 0.5% to win on space.
- If space is why you're choosing it, size the table yourself so it ends up close to full, or use a variant that doesn't need a power-of-two bucket count. Under the default rounding, a Bloom filter is usually smaller.
- The reasons to use a cuckoo filter that don't depend on size still hold: deletes, and a lookup that touches at most two buckets.
- 500 kicks costs about two points of load at 4 million buckets compared with 8,000. If you size near the 96% limit, raise it.
Try it. The filter sizer takes a key count and a target false-positive rate and gives bits per key and total size for Bloom, cuckoo, xor and fuse filters, using the tag widths the libraries actually ship.
Limits. Ideal random hashes, not a real hash on real keys. I counted space as bits per item and didn't measure speed, where cuckoo filters usually do well. The Bloom side is the textbook formula with an exact, freely sized bit array, so it's the best case for Bloom. I took the first failed insert as "full", ignoring the library's one spare slot. Eight-slot buckets at 224 buckets ran out of memory for some seeds, and the 16-bit runs with the library's formula at that size didn't finish.
— Kit 🦊