What is locality-sensitive hashing (LSH)?

Locality-sensitive hashing (LSH) is a family of hash functions designed so that similar vectors collide into the same buckets with high probability while dissimilar vectors rarely do – turning approximate nearest-neighbor search into a matter of hashing the query and scanning only the candidates that share its buckets.

How does LSH turn similarity into bucket collisions?

Ordinary cryptographic or table hashes scatter nearby inputs on purpose. An LSH family does the opposite for a chosen similarity: if two points are close under cosine, Jaccard, Euclidean distance, or another metric the family targets, the probability they receive the same hash value is high; if they are far, that probability drops. Classic constructions include random hyperplane hashes for angular similarity (each hash bit records which side of a random plane a vector lies on) and minhash-style sketches for set resemblance. At index time every vector is mapped through several hash functions – often grouped into bands – and inserted into the corresponding buckets of hash tables. At query time the same functions place the query into buckets; only the vectors found there become candidates for exact or refined distance computation. Amplification tricks (AND/OR combinations of hashes) trade the chance of missing a true neighbor against how many candidates you must score.

That candidate-generation story is a different ANN strategy from walking a proximity graph.

How does LSH-based search compare with HNSW graph search?

HNSW keeps explicit neighbor links and navigates them greedily with a beam; quality depends on graph connectivity and efSearch. LSH keeps no such walkable topology – only hash tables – so recall depends on whether true neighbors collided into the probed buckets. LSH can be attractive when you want a simple probabilistic guarantee tied to a similarity threshold, when updates are mostly appends into buckets, or when you already think in sketches and signatures. Graph methods such as HNSW have dominated many high-dimensional embedding benchmarks because they often deliver higher recall at a given latency once the graph is built, especially for dense neural embeddings. Vector databases such as Weaviate therefore default to graph indexing for large collections, while still describing hashing as one of the classic ANN families alongside trees, clustering, and compression. LSH remains useful as a conceptual baseline and as a component inside hybrid designs.

Those designs matter because raw LSH has well-known failure modes in modern embedding spaces.

Where does LSH struggle on high-dimensional embeddings?

As dimensionality grows, many metric spaces concentrate and pairwise distances look more alike, so it becomes harder for a fixed family to separate “near” from “far” with few bits. Tuning the number of tables, hash length, and probe count is delicate: too few probes miss neighbors; too many recreate a near-brute-force scan of huge buckets. Skewed data dumps popular regions into overflowing buckets while rare regions stay empty, hurting both latency and recall. Unlike HNSW’s continuous recall-latency curve via efSearch, LSH’s knobs are discrete and often require rebuilding tables when the similarity threshold changes. Filtering and multi-tenant isolation are also less natural when the primary structure is a global hash table rather than a traversable graph with per-object identity.

Knowing those limits helps you place LSH correctly in the ANN taxonomy rather than treating it as obsolete or universal.

When is locality-sensitive hashing still a reasonable choice?

Consider LSH when similarity is naturally Jaccard- or cosine-threshold shaped, when you need a compact sketch for first-stage candidate generation before a heavier reranker, or when engineering simplicity of hash tables beats maintaining a large in-memory graph. Prefer HNSW or other graph indexes when you need high recall at low latency on large dense-embedding collections with incremental inserts. Prefer inverted-file or cluster indexes when you want partition-based candidate reduction with coarse quantizers. Prefer tree methods mainly in lower-dimensional regimes where space partitioning stays meaningful. Always measure recall and candidate-set size on your data – LSH’s probabilities are only as good as the match between hash family and metric.

Locality-sensitive hashing finds approximate neighbors by hashing similar vectors into shared buckets and scoring only those collisions. From here, hashing-based ANN restates the family view, inverted file indexes and partition-based ANN cover the main clustering alternative, tree-based nearest-neighbor search opens the space-partitioning branch, and the taxonomy of ANN methods puts LSH beside graphs like HNSW so you can choose with eyes open.