Locality-Sensitive Hashing (LSH)

Unlike cryptographic hashes where a single bit flip avalanches the output, LSH functions are designed to maximize collision probability for similar items. The core contract: Pr[h(x) = h(y)] = sim(x, y), where sim is a similarity function like cosine or Jaccard. Common families include random projection for cosine similarity and MinHash for Jaccard similarity. This property allows a cache to group semantically equivalent queries without exact matching.

A single LSH function is too coarse for production. Precision and recall are tuned through banding techniques:

• AND-amplification: Concatenating k hash functions into a single signature. All must match, increasing precision by reducing false positives.
• OR-amplification: Using L independent hash tables. A match in any table counts, increasing recall by reducing false negatives. The (k, L) parameter pair defines the sensitivity curve, creating a sharp drop-off in collision probability at the similarity threshold.

A brute-force nearest neighbor search over N vectors requires O(N) comparisons, which is prohibitive for billion-scale caches. LSH reduces this to O(N^ρ) where ρ < 1 is a function of the approximation factor. In practice, only a small fraction of the dataset—those hashed to the same buckets as the query—must be examined. This transforms semantic cache lookup from a linear scan to a constant-time hash table probe, critical for sub-millisecond inference retrieval.

For dense embedding vectors, the most common LSH family uses random hyperplanes. A random vector r is generated from a Gaussian distribution. The hash bit is sign(r · v): 1 if the vector lies on one side of the hyperplane, 0 otherwise. The probability that two vectors share the same bit equals 1 - θ/π, where θ is the angle between them. This directly preserves cosine similarity, the dominant metric for transformer-based embeddings in semantic caches.

Standard LSH queries only the exact bucket matching the query hash. Multi-probe LSH extends this by also checking neighboring buckets that are likely to contain similar items. It generates a sequence of hash perturbations, probing additional buckets in order of decreasing collision probability. This achieves the same recall as increasing L (more hash tables) but with significantly lower memory overhead, making it ideal for memory-constrained sovereign deployments where RAM is a premium resource.

Traditional LSH requires careful tuning of k and L parameters, which is brittle under shifting data distributions. LSH Forest eliminates this by organizing hash tables into a prefix tree structure. Queries descend the tree, dynamically adjusting the effective k based on bucket occupancy. If a bucket is too sparse, the algorithm ascends to a parent node with a shorter prefix. This adaptive granularity ensures consistent latency regardless of data density, crucial for production cache layers with unpredictable query patterns.

The core problem that Locality-Sensitive Hashing solves. Instead of performing an exact, brute-force comparison against every vector in a database—which is computationally prohibitive at scale—ANN algorithms trade a small, controllable amount of accuracy for massive gains in query speed. LSH achieves this by grouping similar vectors into the same hash buckets, limiting the search space to a tiny fraction of the total dataset.

A metric for comparing two strings of equal length by counting the number of positions where the corresponding symbols differ. In the context of LSH, algorithms like SimHash produce binary fingerprints. The similarity between two documents is then efficiently estimated by calculating the Hamming distance between their fingerprints, where a smaller distance indicates near-duplicate content.

A statistical measure of similarity between two sets, calculated as the size of the intersection divided by the size of the union. MinHash, a classic LSH family, is specifically designed to estimate the Jaccard similarity between two sets without comparing every element. This is fundamental for detecting near-duplicate documents in large text corpora.

The predominant metric in modern semantic search, measuring the cosine of the angle between two non-zero vectors. It captures orientation rather than magnitude, making it ideal for text embeddings. LSH families like Random Projection use hyperplanes to partition the vector space, preserving cosine similarity so that vectors with a small angle between them are hashed to the same bucket with high probability.

A phenomenon where data becomes increasingly sparse as the number of dimensions grows, causing traditional indexing methods like k-d trees to degrade to linear scan performance. LSH directly counters this curse by using hash functions that are deliberately insensitive to small perturbations, effectively reducing the dimensionality of the search problem by grouping points into low-resolution buckets.

The mathematical core of LSH. A well-designed LSH family guarantees that the probability of two items colliding in a bucket is high if they are similar, and low if they are dissimilar. This is formalized by parameters (R, cR, P1, P2), where the gap between P1 and P2 is amplified by concatenating multiple hash functions into a single table and using multiple independent hash tables to boost recall.