XOR Filter, in depth: three-slot queries, hypergraph peeling, the 1.23 threshold, binary fuse successors and build-time failures

The problem a static filter solves

A membership filter sits in front of something expensive. Typical examples are a disk read for a key that may not exist, a network call to a shard that may not hold a record, or a URL check against a large blocklist. A filter may return a false positive, which costs one wasted expensive lookup. It must never return a false negative. The quality measure is bits per key at a given false-positive rate ε.

The information-theoretic floor is log₂(1/ε) bits per key. A Bloom filter needs about 1.44 log₂(1/ε): 44% above the floor. At ε = 1/256 that is 11.5 bits per key, and a query probes k bit positions, often in different cache lines. When the set is known in advance, you can do better. Examples are an SSTable written once, a nightly blocklist, a shipped dictionary or the key set of an immutable index segment. A static filter can spend effort at build time to get close to the floor, and an XOR filter lands at 1.23 times it.

How a query works

Hash the key once to 64 bits with a per-filter seed. From that hash derive three slot indexes h0, h1 and h2, one in each third of the array, and an f-bit fingerprint. The filter is an array B of f-bit values. Construction chooses B so that, for every key in the set,

fingerprint(x) == B[h0(x)] ^ B[h1(x)] ^ B[h2(x)]

A key that is not in the set gets an essentially random XOR of three slots, which matches its fingerprint with probability 2^-f. That is the whole query. One hash, three loads that can be issued in parallel, two XORs and a compare. There is no loop over k hash functions and no early exit to mispredict.

def locations(h, block):            # block = capacity // 3
    h0 = ((h & 0xFFFFFFFF) * block) >> 32               # multiply-shift instead of modulo
    h1 = ((rotl(h, 21) & 0xFFFFFFFF) * block) >> 32
    h2 = ((rotl(h, 42) & 0xFFFFFFFF) * block) >> 32
    return h0, h1 + block, h2 + 2 * block

def fingerprint(h, bits):
    return (h ^ (h >> 32)) & ((1 << bits) - 1)

def contains(f, key):
    h = mix(key ^ f.seed)                               # splitmix64 finaliser
    a, b, c = locations(h, f.block)
    return fingerprint(h, f.bits) == (f.B[a] ^ f.B[b] ^ f.B[c])

Construction: peeling a 3-hypergraph

Think of slots as vertices and each key as a hyperedge joining its three slots. Then consider a slot that only one key touches. Whatever values the other two slots of that key end up with, you can make that key's equation hold by setting the lone slot last. So remove the key, remember the pair (key, slot) on a stack, and decrement the counts of its three slots. That may create new lone slots. This is peeling. If peeling removes every key, assigning in reverse stack order satisfies every equation, because each key's private slot is written after all keys peeled later, and none of those touch it.

A neat trick keeps memory small. For each slot, store the count and the XOR of the indexes of keys touching it. When the count is 1, the XOR is the one remaining key, so there are no adjacency lists.

def build(keys, factor=1.23, bits=8, max_tries=100):
    n = len(keys)
    block = int(32 + factor * n) // 3
    cap = 3 * block
    for attempt in range(1, max_tries + 1):
        seed = mix(attempt)
        hs = [mix(k ^ seed) for k in keys]
        count, xmask = [0] * cap, [0] * cap
        for i, h in enumerate(hs):
            for s in locations(h, block):
                count[s] += 1
                xmask[s] ^= i                    # XOR of key indexes touching slot s
        stack, queue = [], [s for s in range(cap) if count[s] == 1]
        while queue:
            s = queue.pop()
            if count[s] != 1:
                continue                         # stale entry
            i = xmask[s]                         # the only key left on s
            stack.append((i, s))
            for t in locations(hs[i], block):
                count[t] -= 1
                xmask[t] ^= i
                if count[t] == 1:
                    queue.append(t)
        if len(stack) == n:                      # fully peeled
            B = [0] * cap
            for i, s in reversed(stack):
                a, b, c = locations(hs[i], block)
                B[s] = fingerprint(hs[i], bits) ^ B[a] ^ B[b] ^ B[c]   # B[s] is still 0
            return Filter(seed, block, B, bits)
    raise RuntimeError("peeling failed; duplicate keys?")

Worked example: 100,000 keys, measured

The code above was run on 100,000 distinct random 64-bit keys, with 8-bit and 16-bit fingerprints. One million random non-member keys were then queried. Every member returned true, as it must. Pure Python builds the 8-bit filter in 0.63 seconds on one core; a C build is far faster, but the shape is the same.

Two things stand out. The measured rate matches 2^-f closely, so you can size f directly from the target rate: f = ceil(log₂(1/ε)). And the saving over Bloom is a fixed ratio: 1.23 against 1.44, about 15% less memory at any accuracy, with three probes instead of k.

Why 1.23: the peeling threshold

Peeling succeeds with high probability only when there are enough spare slots. Random 3-uniform hypergraphs have a sharp threshold. Below about 1.222 slots per key, a 2-core (a cluster where every slot is shared) almost surely appears and peeling stalls. To show how sharp it is, the same code built 20 filters of 10,000 keys at each load factor, allowing exactly one attempt.

That cliff is why the constant is 1.23 plus a small additive slack of 32. The slack matters for tiny sets, where random fluctuation is relatively larger. At 100 keys the mean was 1.1 attempts and at 1,000 keys 1.16 (50 builds each, worst case 2). Expected construction time stays linear because each retry succeeds with constant probability. Never try to save memory by shaving the factor: at 1.21 the build never finishes.

Binary fuse filters

The 1.23 factor is a property of hypergraphs where every key picks three slots from anywhere. Graf and Lemire's follow-up, binary fuse filters (2022), keeps the same query but restricts each key's three slots to a small window of consecutive segments. These spatially coupled hypergraphs peel at much higher load. The authors report binary fuse filters within 13% of the storage lower bound, versus 23% for XOR filters. A four-wise variant gets within about 8% at some query cost. The authors also report construction more than twice as fast as XOR filters.

Two caveats come with that. The reported overheads are for large sets; small sets need proportionally more slack. And like XOR filters, binary fuse construction fails on duplicate keys. At least one library (the Rust xorf crate) documents that its binary fuse builders can fail to construct, almost always because of duplicate keys, so read your library's contract. For a new static filter, binary fuse is usually the better default. The plain XOR filter remains the clearest way to understand the family, and its construction is easier to reason about.

Choosing among static and dynamic filters

Whether to use an XOR filter is mostly about mutability, then about memory and probes.

Choose a dynamic structure when keys arrive continuously and you cannot afford periodic rebuilds. Choose a static one when the set is immutable by construction, for example per file, per segment or per release. That is common in LSM storage, where each file's filter is written once and dropped with the file. See Bloom filters, cuckoo filters and ribbon filters for the neighbours in this table.

Failure modes

• Duplicate keys. Two equal keys map to the same three slots, so every slot they share always has count of at least 2. Peeling can never remove them, and every retry fails. Adding one duplicate to 1,000 keys made all 20 attempts fail. Deduplicate before building, or let the builder sort and deduplicate.
• 64-bit hash collisions behave like duplicates. Two distinct keys with the same hash are indistinguishable. With a billion keys the chance of at least one 64-bit collision is about n²/2⁶⁵, roughly 2.7%. Builders that dedupe on the hash survive this. Builders that dedupe on the key, or don't dedupe at all, loop until max_tries.
• Seed not persisted. The seed is part of the filter. Serialize seed, block length, fingerprint width and the array together, with a format version. A reader that rederives the seed answers false negatives for every key.
• Hash drift across languages. If a Go writer and a Java reader hash the key bytes differently (string encoding, endianness, a different mixer), the filter returns false negatives, which is the one error a filter must never make. Pin the hash function in the file format and test cross-language.
• Build memory. The finished 8-bit filter costs 1.23 bytes per key. Construction holds a hash per key, a count and an index XOR per slot, and the stack. For the layout above that is on the order of 30 bytes per key, roughly 25 times the result. Partition very large sets and build per partition.

Operating XOR filters

In production the filter is an artifact, so treat it like one. Build it next to the data it summarizes, in the same job, from the same deduplicated key stream. Write it with a header (magic, version, seed, block length, fingerprint bits, key count) and a checksum. After building, verify it: query every key, or a large random sample, and fail the job on any false negative. Then estimate the false-positive rate on random keys and alert if it drifts above 2^-f by more than sampling noise, because drift usually means a hashing mismatch.

Shard big sets so builds parallelize and peak memory stays bounded. If you need a lower false-positive rate later, rebuild with a larger f. You cannot widen fingerprints in place. For distributing exact static maps rather than filters, the same peeling idea underlies several perfect hashing constructions, and Bloom variants cover the deletable and scalable cases a static filter cannot.

What to do next

1. Write down your set's mutability. If it changes between rebuilds, stop here and use a Bloom or cuckoo filter.
2. Pick f from the target rate: f = ceil(log₂(1/ε)). Use 8 bits for about 0.4% and 16 bits for about 0.0015%.
3. Use a maintained library with a binary fuse builder, and read what it does on construction failure.
4. Deduplicate keys (or their 64-bit hashes) before building, and cap retries with a clear error.
5. Persist seed, sizes and hash version with the array, and test reading the filter from every language that will query it.
6. Gate each build: zero false negatives on all keys, measured false-positive rate near 2^-f.
7. Measure end to end. The win is fewer wasted backend lookups per byte of RAM, so count those, not nanoseconds per query.