Locality-sensitive hashing and the amplification trick

Locality-sensitive hashing is the one family of approximate nearest neighbour methods that comes with a real proof. It is also the family you are probably not using. Both facts are instructive, and the central construction — amplifying an unreliable test into a reliable one by combining copies of it — is worth knowing on its own, because variants of it turn up throughout the field.

The naive approach

Hash tables give constant-time exact lookup. The obvious thing to want is a hash table for similarity: hash the query, read the bucket, done, no scan at all.

Try it with an ordinary hash function. Two nearly identical vectors, differing in one component by a rounding error, hash to unrelated buckets.

How it fails, and why it’s the wrong kind of failure: a cryptographic or general-purpose hash is designed to destroy the relationship between input similarity and output similarity. Avalanche behaviour — one bit of input flipping half the output bits — is the goal. That is exactly the property we need to invert. We don’t want a hash that scatters; we want a hash that collides on purpose, specifically for inputs that are close.

The idea: a hash that leaks distance

Design the hash so that the probability of two points colliding is a decreasing function of the distance between them.

For vectors compared by angle, the construction is beautifully simple. Pick a random direction r. Hash a vector to a single bit: which side of the plane through the origin perpendicular to r does it fall on?

h(v) = 1 if (v · r) ≥ 0 else 0        # r drawn once, at random, uniformly over directions

Geometrically: you are slicing the space with a randomly oriented plane through the origin, and asking which side each point is on. Two vectors end up on opposite sides only if the plane happens to pass between them. The chance of that is proportional to the angle between them: a random plane separates two vectors with probability θ / π, where θ is the angle. So

P[h(a) = h(b)]  =  1 − θ(a, b) / π

That is the whole locality-sensitive property, and it is exact rather than heuristic. Identical directions collide with probability 1. Perpendicular vectors collide with probability 1/2. Opposite vectors never collide. The hash has one bit of output and it carries genuine information about angle.

Note the connection worth carrying: this is the same operation as binary quantization — record the sign of a projection, discard everything else. Binary quantization uses the coordinate axes as its projection directions and keeps d bits; hyperplane LSH uses random directions and keeps as many bits as you choose. Both are turning geometry into bit patterns whose Hamming distance approximates angle.

The problem with one bit, and the fix

A single bit is far too weak. Half the collection collides with your query by chance, and you have eliminated 50% of the work in exchange for building an index. The signal is real but drowned in noise.

The repair is the interesting part, and it is a two-stage construction with a name for each stage.

AND-amplification: concatenate k hashes into a signature. Draw k independent random directions and use all k bits as the bucket key. Two points now land in the same bucket only if they agree on every bit. Since the hashes are independent, the collision probability is raised to the k-th power:

P[signature match] = p^k       where p = 1 − θ/π

Raising a number below 1 to a power pushes it towards zero — but it pushes small numbers down far harder than large ones. With k = 16, a pair at p = 0.95 still collides about 44% of the time, while a pair at p = 0.6 collides about 0.1% of the time. The gap between “near” and “far” has been sharpened enormously. The cost is that we now also miss more than half of the genuinely near pairs.

OR-amplification: build L independent tables. Repeat the whole thing L times with fresh random directions, and take the union of the buckets the query lands in. A pair is retrieved if it matches in any table:

P[found in at least one table] = 1 − (1 − p^k)^L

Now the low probabilities get rescued. With k = 16 and L = 20, our p = 0.95 pair is found with probability around 1 − (1 − 0.44)²⁰, which is essentially certain, while the p = 0.6 pair remains very unlikely to surface.

Together, AND then OR turns a soft, gradual relationship between distance and collision probability into a steep S-curve: near pairs almost always retrieved, far pairs almost never. k controls where the threshold sits, L controls how sharp the transition is and how much it costs.

build(vectors, k, L):
    for t in 1..L:
        R[t] ← k random directions
        for v in vectors:
            table[t][ signature(v, R[t]) ] ← append v

search(query, k, L):
    candidates ← ∅
    for t in 1..L:
        candidates ← candidates ∪ table[t][ signature(query, R[t]) ]
    return exact rescoring of candidates

Note the last line. LSH does not return an answer; it returns a candidate set, which you then score exactly. This is the same coarse-then-exact pattern that composite indexes generalise, and LSH is where it was first made rigorous.

What it gives up, and what it uniquely provides

The guarantee is the selling point. Because the randomness lives in the hash functions rather than in the data, the analysis holds for any dataset. You can state, before seeing the data, that for a chosen distance ratio and failure probability, this many tables of this many bits suffice. No other mainstream family offers that; graph and cluster indexes offer no guarantee at all.

The cost is that data-independence. The bound is a worst-case bound, and worst-case behaviour is what you are paying to defend against. L tables means L copies of the posting structure, and a convincing failure probability wants L in the tens. Real embeddings are highly structured — clustered, on a low-dimensional surface — and a method that ignores that structure by design cannot exploit it. Graph and cluster indexes exploit it aggressively and win by a wide margin on real collections, at the price of having nothing to promise in advance.

Tuning is coupled and unforgiving. k and L interact: raising k sharpens the threshold but demands a larger L to avoid misses, and the right pair depends on the distance scale you care about — which is a property of your data, so the data-independence of the guarantee does not extend to the parameters. And there is no runtime knob equivalent to search breadth. Both parameters are baked into the tables, so moving along the recall-latency curve means rebuilding, which is a real disadvantage compared to a family where recall is a query-time argument.

Bucket occupancy is uneven. In a clustered collection, some signatures attract enormous numbers of points and most are empty. Query cost becomes the size of whichever buckets you happened to hit, which is neither uniform nor predictable, and a dense bucket can degenerate into a partial scan.

Where the idea still earns its place

LSH as a primary index is rare now. The construction survives in several forms worth recognising.

Deduplication and near-duplicate detection. When the question is “is anything within this small distance”, rather than “what are the ten nearest things”, LSH is a natural fit — that threshold question is exactly what the S-curve is shaped for. This is the setting where LSH-derived methods remain standard, and the shingle-and-minhash family for set similarity is the same amplification argument over a different base hash.

Binary sketches as a first stage. Random-projection sign bits make an excellent cheap filter in front of an exact rescoring pass: compact, and comparable with a couple of instructions. Used this way it isn’t a hash table at all, just a compressed representation with a distance you can trust approximately — which is precisely what a quantization scheme is.

Sharding and routing. A locality-sensitive signature is a way to assign vectors to machines such that similar vectors land together, so a query touches few shards. The signature is doing partitioning work rather than search work.

As the reference point for what “approximate” can mean. This is the reason to understand it even if you never deploy it. LSH is the family where the approximation is derived, so it shows you what a guarantee costs — and by contrast, exactly what the heuristic families are buying with the guarantee they declined to make.