Hash tables to vector search and ANN

A hash table gives up a little exactness to buy near-constant lookup. Vector search makes the same bargain in a thousand dimensions - and that bargain is the engine under every RAG system.

In Hashing and hash tables you learned the great trick of hashing: instead of scanning a list to find a key, you compute where it lives. A hash function maps the key straight to a bucket, and lookup drops from $O(n)$ to $O(1)$ on average. The price is subtle but real - you give up the ordered, exact structure of an array and trust a scramble to land like things together. Now suppose your “keys” are not strings but embeddings: 1536-dimensional vectors, one per document chunk, and you want the closest one to a query vector out of ten million. Comparing the query to all ten million is the same $O(n)$ scan hashing was invented to kill. So we play the same card - a hash that sends nearby vectors to the same bucket - and search only that bucket. This lesson connects the two moves and builds the intuition for approximate nearest-neighbor (ANN) search.

Recall: a hash table is an exactness-for-speed trade

A hash table stores key-value pairs in an array of $m$ buckets. To insert or look up a key $k$, you compute a bucket index $h(k)=k\mathrm{mod}m$ (for integer keys) and jump straight there. No scanning. When two different keys land in the same bucket - a collision - you resolve it locally (chaining or probing), and as long as collisions stay rare the average cost is $O(1)$. What you surrendered to get that speed is the array's ordered, exact structure: a hash table has no notion of “next key” or “nearest key,” only “same bucket or not.” That is a perfect deal when your question is exact-match - “is this key present?” It is useless the moment your question becomes nearest - “which stored vector is most similar to this one?” - because an ordinary hash function is designed to destroy locality: it scatters similar inputs to unrelated buckets on purpose, so the table fills evenly.

Locality-sensitive hashing: keep the locality on purpose

Semantic search flips the requirement. We want similar inputs to collide. A locality-sensitive hash (LSH) is a family of hash functions engineered so that the probability two vectors share a bucket grows as they get closer. The classic construction for angle/cosine similarity is a random hyperplane: pick a random direction $\mathbf{r}$ and hash a vector by which side of that plane it falls on, $h(\mathbf{x})=\mathrm{sign}(\mathbf{r}\cdot \mathbf{x})$. Two vectors get the same sign bit exactly when the random plane does not slip between them - which is more likely the smaller the angle $\theta$ between them.

Hashing your query then narrows ten million candidates to the few dozen sharing its bucket - a sublinear shortlist you can afford to measure exactly. You have swapped a guarantee (the true nearest) for a probability (very likely the nearest, or close to it). That is approximate nearest-neighbor search. Drag the query below and watch the trade happen in real numbers.

From buckets to graphs: HNSW and the recall dial

Grid- and hyperplane-LSH have a weakness you just saw: a neighbor one cell over is invisible. Production vector databases (FAISS, Pgvector, Pinecone, Weaviate) more often reach for HNSW - a Hierarchical Navigable Small-World graph. Build a multi-layer graph where each vector links to its nearest neighbors, with sparse “express lanes” on the upper layers. To search, drop in at the top, greedily walk toward the query - always stepping to the neighbor that gets you closer - then descend a layer and repeat. Each query touches roughly $O(\log n)$ nodes instead of all $n$, and because the walk can cross the whole space in a few hops, it rarely gets stranded next to the wrong bucket. Same bargain as LSH, better geometry: give up the guarantee, keep almost all of the accuracy.

import numpy as np

# A signature = the sign bits of the vector against b random hyperplanes.
# Nearby vectors agree on most bits, so they land in the same bucket.
def signature(X, planes):          # X:(n,d) unit vectors, planes:(b,d)
    return (X @ planes.T) > 0       # (n,b) booleans -> a b-bit hash

planes = np.random.randn(16, d)     # 16 planes -> up to 2**16 buckets
buckets = {}
for i, sig in enumerate(signature(corpus, planes)):
    buckets.setdefault(sig.tobytes(), []).append(i)   # index by signature

# Query: hash it, then measure ONLY its bucket -- a shortlist, not millions.
key = signature(query[None], planes)[0].tobytes()
candidates = buckets.get(key, [])                    # sublinear shortlist
nearest = min(candidates, key=lambda i: np.linalg.norm(corpus[i] - query))

Check yourself