Locality-Sensitive Hashing (LSH)

LSH provides a probabilistic guarantee, not a deterministic one. It is designed so that the probability of collision (hashing to the same bucket) is high for similar items and low for dissimilar ones. This is formalized by the LSH family condition: for a similarity function sim and parameters p1, p2 where p1 > p2, if sim(x, y) ≥ p1 then Pr[h(x) = h(y)] ≥ p1, and if sim(x, y) ≤ p2 then Pr[h(x) = h(y)] ≤ p2. The gap between p1 and p2 determines the quality of the hash family.

Basic LSH functions are amplified to sharpen the probability curve. This is done through two constructions:

• AND Construction (Concatenation): Combine k hash functions; vectors hash to the same bucket only if all k functions agree. This reduces false positives (dissimilar vectors colliding) but increases false negatives.
• OR Construction (Multiple Tables): Create L independent hash tables, each with its own AND-composed function. A query is searched in all L tables. This increases recall by reducing false negatives. Tuning k and L controls the trade-off between precision, recall, and query time.

The primary performance benefit of LSH is achieving sub-linear query time relative to the dataset size N. Instead of comparing the query to all N vectors (O(N) time), LSH only compares vectors within the same hash bucket(s). The expected query time is often O(N^ρ) where ρ is a parameter less than 1, dependent on the LSH family. For cosine similarity with SimHash, ρ ≈ 1/(1+cos(θ)) for angle θ. In practice, this enables searching billion-scale datasets with latency measured in milliseconds.

Different similarity/distance metrics require specific, mathematically derived hash functions:

• Cosine Similarity: SimHash (signed random projection) uses a random hyperplane. h(x) = sign(r · x) where r is a random Gaussian vector.
• Euclidean Distance (L2): p-stable LSH (e.g., E2LSH) uses distributions like Gaussian or Cauchy. h(x) = floor((r · x + b) / w), where b is a uniform random offset and w is a bucket width.
• Jaccard Similarity: MinHash represents sets as binary vectors. The hash of a set is the minimum element after a random permutation. Each family preserves the locality-sensitive property for its specific metric.

LSH manages a direct trade-off between memory footprint and retrieval accuracy (recall).

• Memory: Storing L hash tables increases memory usage linearly with L. Each table stores pointers to vectors.
• Accuracy: Higher L and careful tuning of k increase recall but also query time and memory. The failure probability (missing a true nearest neighbor) decays exponentially with L, but so does efficiency. This makes LSH suitable for scenarios where an approximate answer is acceptable, and resources are constrained. It is often paired with a multi-stage retrieval pipeline, where LSH is the fast, first-stage retriever.

LSH differs fundamentally from graph-based Approximate Nearest Neighbor (ANN) methods like HNSW.

• Indexing: LSH is data-independent in its basic form (random projections); hash functions are defined before seeing data. HNSW is data-dependent, constructing a graph that adapts to data distribution.
• Search Pattern: LSH performs hash lookups (O(1) bucket access). HNSW performs greedy graph traversal.
• Performance Profile: LSH often has faster index build time but may require more memory for multiple tables to achieve high recall. HNSW typically achieves higher recall at low latency for a given memory budget but has a slower build phase. LSH is often favored for extremely high-dimensional data or where the index must be frequently rebuilt.

Approximate Nearest Neighbor Search (ANN) is the overarching problem that LSH solves. It refers to algorithms designed to find vectors close to a query vector in high-dimensional space, trading perfect accuracy for orders-of-magnitude reductions in search latency and computational cost. This is fundamental to semantic search in RAG systems.

• Core Trade-off: Balances recall (accuracy) against query latency and memory usage.
• Algorithm Families: Includes hashing-based methods (LSH), graph-based methods (HNSW), and quantization-based methods (PQ, IVF).
• Use Case: Enables real-time retrieval from vector databases containing millions or billions of embeddings.

Hierarchical Navigable Small World (HNSW) is a graph-based ANN algorithm that represents a different architectural approach from LSH. It constructs a multi-layered graph where data points are nodes, and long-range connections enable fast, greedy traversal from entry points to nearest neighbors.

• Performance Profile: Often achieves higher recall at lower latency than LSH for in-memory indices but requires more memory to store the graph structure.
• Key Parameter: efSearch controls the size of the dynamic candidate list during search, governing the recall-latency trade-off.
• Contrast with LSH: HNSW is a deterministic graph traversal; LSH is a probabilistic hashing method. HNSW is typically used when memory is plentiful and latency is critical.

Product Quantization (PQ) is a vector compression technique crucial for billion-scale ANN. It reduces memory footprint and accelerates distance calculations, often used in conjunction with other methods like IVF.

• Mechanism: Splits a high-dimensional vector into subvectors, each quantized into a small set of centroids. A vector is represented by a short code of centroid IDs.
• Memory Efficiency: Can reduce storage by 16x to 32x, allowing massive indices to fit in RAM.
• Distance Approximation: Uses lookup tables for fast, approximate distance computations between a query and compressed vectors. It's a core component of the IVFPQ index.

An Inverted File Index (IVF) is a cluster-pruning index structure for ANN. It partitions the vector space into Voronoi cells using k-means clustering, creating an inverted index that maps centroids to lists of vectors.

• Search Process: For a query, find the nprobe nearest centroids, then search only the vectors in those corresponding cells.
• Key Parameter: nprobe directly controls the recall-latency trade-off. A higher nprobe searches more cells, increasing recall and latency.
• Hybrid Use: Rarely used alone; commonly combined with PQ for compression (IVFPQ) or as a coarse quantizer in multi-stage retrieval.

The recall-latency trade-off is the fundamental engineering compromise governing all ANN algorithms, including LSH. It states that achieving higher search accuracy (recall) necessitates more computational work, resulting in higher query latency.

• Definition: Recall measures the fraction of true nearest neighbors found by the approximate search. Latency is the time to return results.
• Algorithm Tuning: Managed via parameters like LSH's number of hash tables/bit length, IVF's nprobe, and HNSW's efSearch.
• System Design Impact: Drives architectural choices like multi-stage retrieval, where a fast ANN (high latency, moderate recall) is followed by a precise re-ranker (higher accuracy).