Approximate Nearest Neighbor (ANN)

ANN algorithms achieve search times that grow slower than linearly with the dataset size, typically O(log N) or O(1). This is the defining characteristic that makes them viable for billion-scale vector databases.

• Exact k-NN requires O(N * D) time, comparing the query against every vector.
• Graph-based methods like HNSW navigate a sparse graph structure, visiting only a tiny fraction of nodes.
• Hash-based methods like LSH achieve O(1) lookups by confining search to a single hash bucket.
• This complexity reduction is what enables real-time semantic search over massive corpora.

ANN algorithms deliberately sacrifice a small, configurable amount of recall to gain massive speed improvements. This is not a bug but a design parameter tuned via hyperparameters.

• Recall@K measures the fraction of true nearest neighbors found, typically targeting 95-99%.
• Parameters like ef_search in HNSW or nprobe in IVF directly control the accuracy-speed balance.
• In practice, a 99% recall with 100x speedup is often more valuable than perfect accuracy.
• The semantic noise from embedding models typically dwarfs the error introduced by ANN approximation.

ANN algorithms trade memory for speed by building auxiliary index structures that guide the search. The memory footprint varies dramatically by algorithm class.

• Graph-based indices (HNSW) store neighbor links, adding significant memory overhead proportional to the graph degree.
• Quantization-based methods (IVF-PQ) compress vectors, reducing memory but adding computational overhead for distance approximation.
• Hash-based indices (LSH) store multiple hash tables, with memory scaling with the number of hash functions.
• Disk-backed variants like DiskANN extend graph methods to SSD storage for datasets exceeding RAM capacity.

ANN algorithms differ in the type of correctness guarantees they provide, ranging from strict probabilistic bounds to empirical consistency.

• Locality-Sensitive Hashing (LSH) provides formal probabilistic guarantees: the probability of finding the true nearest neighbor is bounded by the hash collision probability.
• Graph-based methods like HNSW offer no formal guarantees but demonstrate empirically consistent high recall across diverse datasets.
• Tree-based methods (KD-trees, Annoy) provide deterministic results for a given index but degrade severely in high dimensions due to the curse of dimensionality.
• Production systems typically favor empirically validated graph methods over theoretically bounded but practically slower LSH.

ANN algorithm performance degrades as vector dimensionality increases, a manifestation of the curse of dimensionality. Different algorithms exhibit varying degrees of resilience.

• Beyond ~100 dimensions, exact tree-based spatial partitioning (KD-trees) becomes no better than brute force.
• Graph-based methods remain effective up to ~1000-2000 dimensions, which covers most modern embedding models.
• Quantization techniques like Product Quantization (PQ) compress dimensions into sub-vectors, enabling search in very high-dimensional spaces at the cost of some accuracy.
• Matryoshka embeddings allow dynamic dimensionality reduction, letting practitioners truncate vectors to the sweet spot where their chosen ANN algorithm performs optimally.

ANN algorithms achieve significantly higher throughput when processing queries in batches rather than one-at-a-time, due to hardware-level parallelism and memory locality.

• GPU-accelerated libraries like FAISS exploit SIMD parallelism, processing hundreds of queries simultaneously.
• Batching amortizes the cost of loading index structures from memory, reducing per-query latency.
• Continuous batching in serving systems dynamically accumulates queries into optimal batch sizes.
• This characteristic makes ANN particularly well-suited for high-throughput retrieval pipelines in RAG architectures where multiple queries may fire concurrently.

The fundamental distance metric that quantifies the semantic relationship between two vectors by measuring the cosine of the angle between them. Unlike Euclidean distance, cosine similarity is magnitude-invariant, meaning it focuses purely on directional alignment in the embedding space. This property makes it the default choice for comparing text embeddings where document length should not influence similarity scores. The metric ranges from -1 (completely opposite) to 1 (identical direction), with 0 indicating orthogonality.

Hierarchical Navigable Small World is the dominant graph-based ANN algorithm that builds a multi-layered proximity graph. The top layers contain long-range "highway" edges for rapid coarse navigation, while bottom layers capture fine-grained local neighborhoods. This structure achieves logarithmic time complexity O(log N) during search by greedily traversing through layers. HNSW offers an exceptional speed-accuracy tradeoff and is the default index in many vector databases, though it consumes more memory than quantization-based approaches.

A vector compression technique that decomposes the original high-dimensional space into a Cartesian product of lower-dimensional subspaces and quantizes each independently. This dramatically reduces the memory footprint of vector indices—often by 10-30x—enabling billion-scale datasets to fit in RAM. The tradeoff is a slight degradation in recall compared to uncompressed search. PQ is commonly paired with Inverted File (IVF) indexes to first narrow the search scope before applying compressed distance calculations.

An algorithmic technique that hashes similar input items into the same buckets with high probability, enabling sub-linear time approximate search. LSH uses random projection functions designed so that the collision probability increases with vector similarity. While historically foundational, LSH has been largely superseded by graph-based methods like HNSW for most embedding search workloads due to superior recall-efficiency curves. It remains relevant for specific use cases requiring strict theoretical guarantees.

A retrieval strategy that combines the precision of sparse keyword search (BM25) with the semantic understanding of dense vector search (ANN). Results from both pipelines are merged using Reciprocal Rank Fusion (RRF), an unsupervised algorithm that consolidates ranked lists without requiring score calibration. Hybrid search solves the "out-of-domain" problem where pure vector search misses exact keyword matches for rare terms, entity names, or product codes that embedding models may not capture well.

A two-stage retrieval architecture that addresses the accuracy-efficiency tradeoff inherent in ANN search. Stage one uses a fast bi-encoder to retrieve a candidate set of 100-1000 documents via approximate search. Stage two applies a slower, more accurate cross-encoder that processes the query and document jointly through full attention, enabling nuanced relevance assessment. This pipeline achieves near-exhaustive search quality while maintaining production latency requirements.