Locality-Sensitive Hashing and Vector Embeddings

Concept. An ordinary hash spreads similar inputs across different buckets. Locality-sensitive hashing maps similar vectors to the same bucket so a similarity query reads one bucket instead of scanning all vectors.

Intuition. Cut the space with a few random lines. Which side of each line a point falls on is one bit of its code. Two points close together land on the same side of almost every line, so they get the same code and the same bucket. Look only in that bucket.

The previous section already used approximation. A Bloom filter answers "is this item in the set?" approximately, accepting a few false positives in exchange for a large space saving. This page does the same for a harder question, "which items are nearest this one?", accepting a few missed matches in exchange for not scanning a billion vectors.

Locality Sensitive Hashing (LSH)

Every item is a vector in a high-dimensional space, an embedding of hundreds or thousands of numbers. A query is a vector too. "Find similar items" means one thing: of a million stored vectors, which sit nearest the query vector? Comparing the query against all million is O(N), too slow at scale, and an ordinary hash table cannot help: by design it scatters near-identical inputs to unrelated buckets.

Two near-identical cat vectors feed an ordinary hash and land in unrelated buckets, bucket 7 and bucket 3, far apart. A red bar: similar items, unrelated buckets, so 'find similar' would have to scan every bucket.

Figure 1. An ordinary hash spreads inputs across buckets. Two near-identical vectors (cat A and cat B) land in unrelated buckets, 7 and 3. The bucket index carries no information about distance, so a similarity query still scans every bucket. Locality-sensitive hashing groups near vectors instead.

Four items, each turned into a feature vector, then a k-bit LSH code, then a bucket. The two similar cats share code 1011 and the same bucket, while the dog and car land in different buckets. A query for items like the cat scans only that bucket.

Figure 2. Each item becomes a feature vector, an embedding, then a short LSH code, then a bucket. The two similar cats receive code 1011 and share a bucket, while the dog and car map to different buckets. A query for items like the cat reads that one bucket instead of comparing against every stored vector. Code bits come from random cuts of the space.

So flip the goal: build a hash that wants collisions, but only between vectors that are alike. Picture one straight line dropped across the space. Every point is on one side of it or the other. In a real embedding space of hundreds of dimensions that line becomes a hyperplane, but nothing else changes: one cut, one yes-or-no question, one bit. Two figures follow: the first computes the codes for four items, the second shows what a cut really is once you leave two dimensions.

A space crossed by three dashed cuts. Above a cut reads 0 and below reads 1, so three cuts give each item a three-bit code. The two cat photos both read 111 because no cut falls between them, and share a bucket. The dog reads 011 and the car reads 110, each differing from the cats on one cut. A table fills in above or below for every item as each cut lands.

Figure 3. Each cut asks one yes-or-no question: above the line is 0, below is 1, and the code assembles one bit at a time. The same four items as Figure 2. The two cats end on 111 because no cut fell between them, so they share a bucket; the dog differs on cut 1 and the car on cut 3, so each lands elsewhere. Nothing measures a distance, which is what turns a near-duplicate lookup into a hash-table lookup: cost O(N) becomes about O(N / 2k). Misses happen when a cut does fall between a close pair.

A cloud of 200 unit vectors in three dimensions holding the two near-duplicate cats and the unrelated dog. Planes through the origin arrive one at a time and orange marks every vector still on Cat 1's side of all of them. After the first plane the dog is still in Cat 1's bucket; the second separates it; Cat 2 stays throughout. The candidate set falls from 200 to 94, then 43, then 19. A ladder names the same object in each dimension: a line in two, a plane in three, a hyperplane in 256, always one dimension less than the space.

Figure 3b. A cut is always a flat one dimension below the space it cuts. In two dimensions that is a line, which is what Figure 3 drew; in three it is an ordinary plane, drawn here; in an embedding’s few hundred dimensions it is a hyperplane (harder to picture). Nothing else changes: above or below is still the only question. Watch what one cut is worth. After the first plane the dog is still in the cat’s bucket, because one cut halves the space and a coin flip put it on that side. The second ejects it, and the near-duplicate survives all three. Each plane roughly halves the candidates: 200, then 94, then 43, then 19.

Why it tracks similarity

A single cut separates two points only when it happens to fall between them. Two points sitting almost on top of each other leave almost no room for a cut to land between, so nearly every cut puts them on the same side and they keep the same code. Two points far apart leave a wide gap, so many cuts fall between them and flip a bit. The chance two items land in the same bucket therefore shrinks smoothly as they get farther apart. That is what locality-sensitive means: closeness survives the hash instead of being scrambled by it, which is exactly the opposite of an ordinary hash.

The knob: how many lines

More hyperplanes make purer buckets but split more true pairs, so k trades recall for selectivity. You pick k for the recall you need and union several independent tables to recover the pairs any single one drops.

What is Quantization?

LSH shrinks the search. Quantization shrinks the storage: replace each exact value with a small code for the bucket it falls in, so a vector that took kilobytes takes a handful of bytes. Keep just enough to preserve who is near whom.

Vector/Embedding Hashing

Every large system that searches embeddings runs some version of this: Faiss at Facebook, recommendations at Google and Spotify, semantic and code search at OpenAI. The same locality trick shows up beyond embeddings: perceptual image hashing (Microsoft PhotoDNA) collides near-duplicate images even after a resize or recolor, and DNA k-mer hashing groups similar genomic sequences for fast partitioning. All trade the exact answer for the scale. To see random projections and quantization in working code, open the Hashing Colab.

Once you stop demanding the exact answer, "find similar" and "store a billion vectors" both become cheap. The next two case studies show that in production, and Case Study 2.4 pushes it to its 2026 limit.