Approximate Nearest Neighbor (ANN)

ANN algorithms fundamentally exchange perfect recall for sub-linear query times. A brute-force k-NN scan of a billion vectors requires comparing the query against every single vector, yielding O(N) complexity. ANN structures like HNSW or IVF reduce this to O(log N) by organizing vectors into navigable graphs or clusters. The recall@k metric quantifies the tradeoff: a well-tuned ANN index typically achieves 95-99% recall while being 100-1000x faster than exact search. This is acceptable because downstream re-ranking stages can correct minor retrieval misses.

Inverted File (IVF) indexing partitions the vector space into clusters using k-means. During indexing, each vector is assigned to its nearest centroid. At query time, only the nprobe closest clusters are searched, dramatically reducing the candidate set. IVF is often paired with Product Quantization (PQ) for compression:

• Coarse Quantizer: The IVF centroids provide a first-pass filter
• PQ Codes: Residual vectors within each cluster are compressed using learned sub-vector codebooks This combination enables billion-scale indexes to fit in RAM, though recall depends heavily on nprobe tuning and cluster quality.

Tree-based methods recursively partition the vector space using random hyperplanes. Annoy (Approximate Nearest Neighbors Oh Yeah) builds a forest of binary trees where each split is a random projection. At query time, multiple trees are traversed and their candidate sets are unioned. While generally outperformed by graph methods for high-dimensional embeddings, tree-based indexes offer:

• Deterministic build time: No iterative training like k-means
• Disk-friendliness: Memory-mapped index files enable serving large indexes on constrained hardware
• Simplicity: Minimal hyperparameters compared to HNSW or IVF

Locality-Sensitive Hashing (LSH) uses hash functions designed so that similar vectors collide in the same bucket with high probability. By constructing multiple hash tables, query-time search reduces to examining only vectors that share a hash bucket with the query. LSH offers strong theoretical guarantees on recall bounds but has fallen out of favor for dense embeddings because:

• Hash quality degrades as dimensionality increases beyond ~100 dimensions
• Memory overhead from multiple hash tables can exceed graph-based methods
• Modern embeddings (768-1536 dims) perform better with graph or IVF approaches

Vector compression is critical for scaling ANN to production. Product Quantization (PQ) splits a d-dimensional vector into m sub-vectors, then quantizes each using a separate codebook learned via k-means. The original vector is stored as m byte-sized codes. Scalar Quantization (SQ) converts 32-bit floats to 8-bit integers per dimension. Binary Quantization thresholds dimensions to single bits. These techniques enable:

• In-memory billion-scale indexes on commodity hardware
• Fast distance approximation using lookup tables instead of full dot products
• Tradeoff control: More sub-vectors (higher m) yields better precision at the cost of more bytes per vector