When Your Vector Database Gets Fat: How Compression Keeps Search Fast

Picture this: You've trained embeddings on 10 billion documents. Your vector search is starting to feel like waiting for dial-up. The index won't fit in RAM anymore, and every query digests into a painful disk grind.

This is the exact nightmare compression algorithms were built to solve — but they had to get remarkably clever about it. Because while you could just gzip your embeddings and call it a day, you'd be waiting hours for each search.

The Naïve Approach (And Why It Broke)

Early embedding stores treated vectors like JPEGs — compress once, decompress on query. This works fine for storage, but kills search dead. Every single distance calculation requires decompressing both vectors first. With millions of candidates to check per query, that's computational suicide.

The breakthrough came from realizing you don't need exact vectors to find nearest neighbors. You need them to be close enough to prune the search space correctly.

Product Quantization: The Workhorse

Product Quantization (PQ) is the hero of modern embedding compression. Here's how it sidesteps the decompression trap:

1. Slice every vector into equal-length subvectors (say, 8 chunks of 128 dimensions each)
2. Cluster each subspace independently using k-means, storing only 256 centroids per subspace
3. Replace each subvector with its nearest centroid ID (a single byte)

Now your 1024-dimensional float32 vector (4KB) becomes eight bytes. 500x compression — and you never need to decompress the original. Distance computations become table lookups against precomputed centroid distances.

The tradeoff? Accuracy drops. But with 256 centroids per subspace, you retain about 95-98% of recall@10 for most datasets. The search speed stays fast because every candidate's distance is computed from those tiny 8-byte codes.

ScaNN: When Google Needed Speed at Scale

Google's ScaNN (Scalable Nearest Neighbors) refined PQ further by noticing something counterintuitive: not all subspace divisions are equal. Some dimensions carry more discriminative power than others.

ScaNN uses anisotropic quantization — it allocates more centroids to subspaces with higher variance. This single change improved recall by 5-10% over vanilla PQ at the same compression ratio. The result powers Google's own large-scale retrieval systems.

Binary Quantization: The Radical Simplifier

For applications where recall can be slightly lower (semantic search, not DNA matching), Binary Quantization does something audacious:

• Take the median value of each dimension
• Set everything above it to 1, below to 0
• Your 1024-dimensional float vector becomes 1024 bits = 128 bytes

That's still 32x compression. But the real magic? Hamming distance (XOR + popcount) is 10-100x faster than Euclidean distance on modern CPUs because it uses dedicated vector instructions.

Facebook's Faiss library benchmarks show binary quantization achieving 90% of full-precision recall@10 with 40x speedup in throughput. Not bad for algorithms that literally throw away decimal places.

The Memory Hierarchy Trick

All these methods exploit a deeper principle: the faster the memory, the smaller the data.

• Full vectors live on slow disk (or cold storage)
• PQ codes sit in RAM for fast scanning
• Binary codes can even fit in L3 cache on large machines

When you query, you first scan the compressed representations (fast, cheap), then only fetch and re-rank the top-K candidates from the full vectors (slow, expensive). This two-phase approach keeps search speed high even as stores grow to billions of vectors.

Practical Guidelines

The sweet spot for production systems? PQ with 8-16 centroids per subspace, tuned via cross-validation on your actual query distribution.

The Future Isn't About Compression — It's About Structure

The next frontier isn't making embeddings smaller — it's making them smarter. Quantization-aware training lets you train embeddings that are born compressed, avoiding the accuracy loss entirely. Microsoft's Compresso model already shows 99.5% recall preservation with 8-bit quantization.

For now though, if your embedding store is ballooning and your search latency is creeping up, don't reach for more RAM. Reach for PQ. It's the difference between a database that crawls and one that stays snappy — even when your vector count hits a billion.