XOR Filters: Cramming 234K Words Into 282 KB

The Problem: Word Validation at 42M ops/sec

When building Letter Snake — a word-chain game where every letter you collect must form a valid English word — I ran into a fundamental constraint: the word check had to be instant. Not "fast enough." Instant. Every keystroke triggers a validation, and any perceptible lag would break the game feel entirely.

The obvious approach is a Set<string> loaded from a dictionary file. Simple, fast, works. Until you look at the numbers: a raw 234,000-word text file weighs in around 2.4 MB. For a browser game, that's a non-starter cold-load cost.

What's an XOR Filter?

An XOR filter is a probabilistic data structure — like a Bloom filter, but better in almost every dimension. Instead of multiple hash functions writing to a single bit array, an XOR filter distributes fingerprints across a three-level structure that allows O(1) lookup with a theoretical false-positive rate you can tune at construction time.

The key insight: you only need to answer one question — "is this word in the set?" — and you can afford a tiny false-positive rate (~0.39%) for a word game. Nobody's going to notice the one-in-256 ghost word. What they will notice is a 2.4 MB download.

The Build Pipeline

The filter gets built once at library publish time via a Node.js script:

// Roughly: fingerprint each word, solve the XOR mapping
const filter = XorFilter.build(wordList, { bitsPerFingerprint: 8 });
fs.writeFileSync('filter.bin', filter.serialize());

The serialized binary lands at 282 KB — an 88% size reduction versus the raw text. At runtime, the filter deserializes in microseconds and every lookup runs three array reads + three XORs. That's it.

Benchmarks

On an M2 MacBook Pro:

• ~24 ns per lookup
• 42 million lookups/second
• 0.39% false-positive rate
• 282 KB total bundle cost
• Zero runtime dependencies

The library runs identically on Node.js, browsers, Deno, Bun, and Cloudflare Workers — because the only runtime primitive it needs is a typed array.

Lessons

The biggest surprise was how much the access pattern matters. XOR filters are read-heavy and write-once — which maps perfectly to a "ship a pre-built binary with your npm package" model. If you need to add words dynamically, you'd rebuild the filter. That constraint sounds limiting until you realize most dictionary-style use cases are exactly static.

The second lesson: probabilistic is fine when the failure mode is benign. A false positive in a word game means a player sneaks a non-word past the validator occasionally. In a financial system, that's catastrophic. Know your domain.

The library is on npm and fully open-source on GitHub if you want to dig into the implementation.