Locality-Sensitive Hashing (LSH)
LSH hashes vectors so close ones land in the same bucket. You check one bucket instead of the whole collection, and accept a small chance of missing.
Why Does This Exist?
You have turned a million passages into embeddings and a question arrives. The honest way to answer "what is closest?" is to score the query against every stored vector. If is your collection size and is the number of values in each vector, one query costs on the order of operations. Double the collection and you double the work per query. You will not feel that at ten thousand vectors. You will feel it at millions of vectors with milliseconds to answer.
Locality-sensitive hashing (LSH) breaks that link. It hashes every vector ahead of time so that close vectors land in the same bucket, and each query checks only its own bucket. The price is a small chance of missing the true nearest match, which makes LSH one member of the approximate nearest neighbor search family. The graph based rival lives in HNSW, the compression first rival in IVF and product quantization, and the production system around any of them in vector databases.
This page covers the hashing member: random cuts for cosine similarity, how short signatures become tables, and how you tune them. The one idea you need first is the yardstick LSH preserves. Two embeddings are close when the angle between them is small, and similarity metrics spells out why cosine cares about that angle and ignores vector length. With that in place, the trick below will click.
Think of It Like This
A post office with rough sorting rules
Imagine a post office that sorts parcels with three yes or no questions: heavy or light, big or small, local or far. Each parcel gets a three bit code from its answers, like heavy, small, local, and lands in the bin for that code. A new parcel arrives, you answer the same three questions, walk straight to its bin, and compare it only with the parcels there. Similar parcels mostly share a bin, so you skip the rest of the building.
Each question is one hyperplane, each bin is one bucket, and walking to the bin is the query. That is the whole mapping.
Where it stops: the post office designed its questions, and a parcel never lands in the wrong bin. LSH draws its questions at random, so a cut sometimes falls between two close vectors and two far vectors sometimes share a bin. The post office never misses by design. LSH misses by design, and you buy the misses back with more tables.
How It Actually Works
An LSH family is a set of hash functions where the collision probability falls as the distance grows: close inputs collide often, far inputs rarely. For cosine similarity the standard family cuts space with random hyperplanes, and the rest of this page is that construction plus the two knobs that tune it.
One random cut
Draw a vector whose entries come from a standard normal distribution. Here is the random cut direction, is any data vector, and the dot product measures which side of the cut falls on. The hash keeps only the sign:
Take two vectors and with angle between them, measured in radians so a half turn is . A random cut separates them exactly when its direction falls in the wedge between them, which happens with probability . So they agree with probability:
Close vectors rarely have a cut land between them. Orthogonal vectors agree half the time. Opposite vectors never agree.
From one bit to a signature
One bit is too coarse, so you stack independent cuts, where is the number of bits in a signature. All bits must agree for two vectors to share a bucket, and independence multiplies the probabilities: a pair that agrees per bit with probability shares the full signature with probability . Longer means smaller buckets and fewer false friends, but also more near misses.
Then you repeat the whole thing times, where is the number of independent tables. A pair is found if it collides in at least one table, so with per table probability the chance of being found, called the recall, is:
That is the trade. Raising sharpens each table and costs recall; raising buys recall back and costs memory. A cheaper patch for boundary misses is multi probe: flip one or two bits of the query signature and check those neighbouring buckets too.
Worked example
Take and , a unit vector sitting degrees above . The angle is , so each random bit agrees with probability . With bits the full signatures match with probability .
Now draw three concrete cuts: , , . Dotting each vector against each cut and keeping the sign:
- : ; ; , giving the signature .
- : ; ; , giving .
Two of three bits agree, but the signatures differ, so this table misses. That is being the unlucky cut in the diagram: it falls in the degree wedge between the pair. With independent tables the miss chance per table is , all four miss with probability about , and recall is . Four small tables turn a coin flip table into a near sure thing.
For contrast, a pair at degrees agrees per bit with probability and shares all three bits with probability . Far pairs still collide sometimes. That background rate is what large pushes down.
Two sibling families work the same trick for other yardsticks. Sets under Jaccard similarity use MinHash, covered in the MinHash definition, and Euclidean distance uses a quantized projection variant. The assumption underneath is always the same: the family must match the distance you actually rank by. Cut space with cosine cuts while your reranker scores Euclidean distance, and the buckets preserve the wrong geometry.
Use LSH when the collection is big enough that a full scan hurts and a small miss rate is affordable, then rerank the bucket exactly. Skip it when the collection fits a brute force scan or a miss is unacceptable. Exact answers need exact search.
Code
This snippet replays the worked example with plain Python: three cuts, two vectors, one signature each. No libraries, so you can paste it anywhere.
Vector = list[float]
def dot(u: Vector, v: Vector) -> float: return sum(x * y for x, y in zip(u, v))
def signature(vec: Vector, planes: list[Vector]) -> list[int]: return [1 if dot(vec, w) >= 0 else 0 for w in planes]
a: Vector = [1.0, 0.0]b: Vector = [0.866, 0.5]planes: list[Vector] = [[0.5, -0.2], [-0.3, 0.8], [1.0, 1.0]]
print(signature(a, planes)) # -> [1, 0, 1]print(signature(b, planes)) # -> [1, 1, 1]Same pair as above: two of three bits agree, so this table misses and the remaining tables do the catching. Change to and both signatures become , which shows the luck of the draw in one line.
Watch Out For
Long signatures that return empty buckets
You raise to shrink noisy buckets and queries start coming back empty. Recall craters, not gradually but all at once, because each added bit multiplies the miss rate. The symptom is unmistakable: the bucket lookup succeeds and finds nobody home.
Shorten before you add tables, then add tables until a labelled sample of true pairs collides at your target recall. If memory is the wall, probe neighbouring buckets by flipping one bit of the query signature instead of building another full table.
Expecting exact answers from a probabilistic index
LSH sometimes misses the true nearest neighbour, by construction, so an eval that demands the exact top result flakes from run to run as the random tables change. People usually blame the embeddings. The embeddings are fine; the index made a bargain and the eval ignored it.
Treat LSH as a shortlister: pull candidates from the bucket, then score those candidates exactly and keep the best. When the collection is small enough to scan, or a miss breaks the product, run exact search or a high recall graph index instead.
The Quick Version
- LSH hashes vectors so similar ones share a bucket, turning a full scan into one bucket lookup plus an exact rerank.
- One random hyperplane gives matching bits with probability , where is the angle between the vectors.
- Stacking bits sharpens each table as ; stacking tables lifts recall as .
- A degree pair shares a bit with probability about and a bit signature with probability about , rising to about recall over four tables.
- Tune and against measured recall on your own pairs, because the right values depend on your data and not on defaults.
- Use it for big collections where a small miss rate is affordable; skip it where a miss is unacceptable or a scan is already cheap.