The second of three ideas behind modern ANN: replace full-precision vectors with small codes that are dozens of times smaller and still let you estimate distance.
Part 3 of Approximate Nearest Neighbors. Previous: Partition the Space.
Partitioning was the first trick: cut the space into regions so a query only scans a small fraction of the database. That gets you a lot, but it leaves a second problem untouched. The vectors themselves are enormous. Modern embedding models emit 768- or 1536-dimensional float32 vectors, and the inner loop of any nearest-neighbor search still has to read those vectors from memory and do arithmetic on them.
Compression attacks that inner loop. If you can replace a full 3 KB vector with a handful of bytes, three things happen at once. The database gets small enough to fit in RAM, sometimes in L2 cache. The distance kernel becomes cheaper because there is less data to pull through the ALU. And because the database is smaller, cache misses plummet. Compression is as much about speed as it is about storage.
Start with a back-of-envelope. A single 768-dimensional float32 vector is 768 × 4 = 3072 bytes, about 3 KB. A million of them is 3 GB. A hundred million is 300 GB. At that scale, the only question is which storage tier the database lives in, and each jump (L2 to RAM to SSD to network) costs an order of magnitude in latency.
The figure below shows how quickly compression changes your hardware constraints. Drag the slider to change the bit budget per dimension. The bar shrinks, and labels mark the thresholds where the database moves between memory tiers.
There are three families of compression we will look at. Scalar quantization reduces bits per dimension. Binary quantization takes that to the extreme. Product quantization throws out the one-bit-per-dimension constraint entirely and replaces subvectors with codebook indices. They trade off differently, and modern systems often combine them.
The simplest compression is also the oldest. Pick a per-dimension range, divide it into buckets, and store a bucket index instead of a float. Eight-bit scalar quantization uses 256 buckets per dimension and cuts storage by 4x compared to float32. Four-bit uses 16 buckets and cuts 8x. Two-bit is more aggressive still.
Scalar quantization preserves the shape of the vector space. Vectors that were close before are still close after, with small rounding errors. The cost is that every dimension still has to be touched during distance computation. You are paying "full" distance cost on compressed data, which is fine when the bottleneck is memory bandwidth and not arithmetic.
Use the slider below to watch what happens as the bit budget shrinks. Database points snap to a coarser and coarser grid. The k nearest neighbors by the compressed representation start to diverge from the true nearest neighbors computed on the full precision points.
Push scalar quantization to its limit and each dimension becomes a single bit: above or below the per-dimension median. A 768-dim vector becomes 96 bytes. Distance between two binary vectors is the Hamming distance, which is a bitwise XOR followed by a population count. On modern CPUs, that is one of the cheapest instructions available. A distance comparison that used to involve 768 multiplies and adds becomes a handful of 64-bit popcount instructions.
Binary quantization loses a lot of information. It works surprisingly well on well-trained embedding vectors, mostly because those vectors tend to be roughly isotropic after layer normalization, and the sign pattern of each dimension carries more signal than you would guess. It also fails gracefully: you can use it as a very fast first pass, then rerank survivors with a less aggressive scheme.
The most important compression technique for ANN is Product Quantization, usually called PQ. The insight is that you can beat scalar quantization's one-bit-per-dimension limit by correlating dimensions with each other.
Here is the recipe. Take the d-dimensional vector and split it into m chunks, each of size d/m. Treat each chunk as a point in (d/m)-dimensional space. Run k-means on the whole database restricted to that chunk, producing 256 centroids per chunk. Now every chunk of every vector can be replaced with the index of the nearest centroid, a single byte. The full vector becomes m bytes.
The combinatorial space is 256m possible codes, which for m = 16 is about 1038. You are not limited to 256 possibilities per vector. You are limited to 256 possibilities per subspace, and the subspaces combine freely.
The figure below is a small working example. An 8-dimensional vector is split into 4 subvectors of 2 dimensions each. Each subspace has a codebook of 16 centroids (visualized as a small 2D scatter). Drag the sliders at the top to change the vector and watch each subvector snap to its closest centroid, producing a 4-integer code.
Compression is only half the story. The other half is how you compare a query to the compressed database. You could decompress every database vector back to floats, but that would throw away the speedup. You could also compress the query and compare codes directly, but that loses query-side precision. PQ's contribution is a third option that is usually better than both.
The trick is called Asymmetric Distance Computation. When a query arrives, split it into the same m subvectors as the database uses. For each subspace, precompute the distance from the query's subvector to every one of the 256 centroids. That builds an m × 256 lookup table, computed once per query.
Now comparing the query to any database vector is almost free. Each database vector is m bytes, one centroid index per subspace. Look up m distances from the table and add them. m additions, and the total is the PQ estimate of the query-to-vector distance. No multiplies, no square roots, and the query stayed at full precision.
The name asymmetric is there because the query is not quantized. The database is coded, the query is floats. Symmetric distance (quantize both) is faster still (the table is precomputed once for the whole database) but gives worse accuracy. Asymmetric is the usual choice.
PQ distance is an estimate, not a measurement. It can be off by several percent on any single comparison, and the ordering of the top candidates can shuffle. The standard fix is reranking. Pull the top k×10 or top k×20 candidates by PQ distance, then recompute exact distance for only those candidates and return the top k.
The exact pass costs a few thousand full distance computations, which is tiny compared to the millions avoided by the PQ shortlist. Recall climbs back to near its full-precision value, and the total cost is dominated by the PQ scan rather than the exact rerank.
Partition and compression are complementary. Partition narrows the candidate set to one or a few cells. Compression makes scanning inside those cells fast. Put them together and you get IVF-PQ, the workhorse index behind FAISS, lancedb, and many other production systems.
A query arrives. IVF picks the nprobe closest cells. The query's PQ lookup table is computed. For each vector inside the selected cells, sum m table entries to get a PQ estimate. Take the top candidates, rerank with exact distance, and return the top k. The figure below traces that pipeline once on load, then loops.
The pattern generalizes. HNSW indexes use PQ on the bottom layer to avoid storing full vectors per node. DiskANN uses PQ-compressed vectors in RAM for scoring and the full vectors on SSD for reranking. The next article, on hardware-aware design, is about matching this structure to the memory tier your database actually lives in.