FINDING NEEDLES · CHAPTER 08
Dense retrieval turns search into “find the nearest points”. Measuring every point is exact and too slow. A vector index gives up a little accuracy to skip almost all of them.
Picture a star catalogue where each entry has been turned into a point. Ask for “stars like this one” and the answer is the points closest to your query point. That is the whole job of the previous chapter’s retriever, once the vectors exist.
The slow way measures the distance to every star. The fast ways first decide which stars are worth measuring. They can pick wrong, so they sometimes miss a true neighbour. That is why they are called approximate nearest neighbour (ANN) search.
A vector index is a guess about where to look. A good guess opens a small part of the catalogue and still finds most of the true neighbours. Every knob on a vector index trades how much you open against how many neighbours you miss.
A vector database wraps that index in the parts a service needs: ids, stored metadata (here, each star’s colour), inserts and deletes, and filters. This chapter is about the index and the filters, because that is where the trade-offs live.
Twelve stars, each a 2-D toy vector. Real embeddings have hundreds of dimensions; two let you draw the picture. The query sits at (4, 4). Distance is squared straight-line distance, which gives the same order as the real distance without a square root.
stars · ANN · tradeoff · filters
| Star | Vector | Colour | Distance² to (4, 4) |
|---|---|---|---|
| S4 | (4, 3) | blue | 1 |
| S12 | (5, 5) | blue | 2 |
| S8 | (6, 4) | red | 4 |
| S2 | (2, 3) | blue | 5 |
| S3 | (3, 1) | red | 10 |
| S1 | (1, 2) | blue | 13 |
| S9 | (4, 8) | red | 16 |
| S6 | (8, 3) | blue | 17 |
| S5 | (7, 1) | red | 18 |
| S11 | (7, 8) | red | 25 |
| S10 | (5, 9) | blue | 26 |
| S7 | (9, 2) | red | 29 |
The true top 3 are S4, S12, S8, at distances 1, 2 and 4. Finding them took 12 distance computations, one per star. That answer is the ground truth every faster method is graded against.
every one of the N stored vectors, times d numbers in each vector.
Twelve stars in two dimensions is 24 multiply-adds. A collection of 10 million vectors with 768 dimensions is 7,680,000,000 multiply-adds for one query. Hardware can do that, but not for thousands of queries a second on one machine. So you stop measuring everything.
An inverted file index (IVF) borrows the idea from chapter 1. There, a word pointed at a list of documents. Here, a centroid points at a list of vectors. Build time: pick a few centroids (k-means finds them in practice; here they are placed by hand) and file every star under its nearest centroid.
| List | Centroid | Stars filed here | Distance² from query to centroid |
|---|---|---|---|
| A | (2, 2) | S1, S2, S3, S4 | 8 |
| C | (5, 8) | S9, S10, S11, S12 | 17 |
| B | (8, 2) | S5, S6, S7, S8 | 20 |
Query time: measure the query against the centroids (8, 17 and 20), sort them, and open the nprobe closest lists. Only the stars in those lists get measured.
| nprobe | Lists opened | Work | Top 3 found | Recall@3 |
|---|---|---|---|---|
| 1 | A | 3 centroids + 4 stars = 7 distances | S4, S2, S3 | 1/3 |
| 2 | A, C | 3 + 8 = 11 distances | S4, S12, S2 | 2/3 |
| 3 | A, C, B | 3 + 12 = 15 distances | S4, S12, S8 | 3/3 |
of the k neighbours exact search would return, how many did the index return too.
S8 is the third-nearest star, but it lives in list B, and B’s centroid is the farthest of the three. A centroid is a summary of its list. A star on the edge of a list is badly summarised by it. That is the miss every ANN index has to live with.
Interactive · Open more lists
How many lists do you have to open before S8 shows up? Pink chips are returned, yellow chips were measured, plain chips were never opened.
At nprobe 3 the index costs 15 distances, more than the 12 of exact search. On twelve stars IVF is a loss. It pays off at scale. Take 10 million vectors in 1,000 lists of about 10,000 each, and open 10 lists. That is 1,000 centroid distances plus 100,000 vector distances: 101,000, or 1.01% of the 10 million an exact search measures. Real systems tune nprobe on held-out queries until recall@k is high enough.
Speed is half the problem. Memory is the other half. A 768-dimension float32 vector takes 3,072 bytes. Product quantization cuts the vector into 96 short pieces, learns a small codebook for each piece, and stores one byte per piece: the id of the nearest codebook entry. That is 96 bytes, 32 times smaller. Ten million vectors drop from 30.72 GB to 0.96 GB. Distances are then computed against the codebooks, so they are approximate too. IVF with product quantization on top is a common pairing for collections that do not fit in memory.
The other main family skips lists and builds a graph. Every star is linked to a few nearby stars. To search, start somewhere and keep hopping to whichever neighbour is closer to the query. Stop when no neighbour is closer. That is a greedy walk.
A walk on one flat graph takes many short hops to cross the sky. HNSW (hierarchical navigable small world) adds sparser layers on top, with long links between a few stars. The walk starts on the top layer, crosses the sky in a few long hops, then drops down a layer and continues with shorter links.
The path is S10 → S1 → S2 → S4. Along the way the walk measured 8 of the 12 stars. On twelve points that is a small saving. On millions, the layers let a walk cross the collection in a handful of long hops, so the number of hops grows roughly with the log of N rather than with N.
A real HNSW search does not keep only the single best star. It keeps a short candidate list (its size is the ef setting) and explores from all of them, which is how it returns a top k and recovers from dead ends. Each star’s link count (M) is set at build time. More links and a longer candidate list both raise recall and both cost time or memory.
Real queries come with conditions: this tenant, this date range, in stock. Here the condition is colour = red, and you want 3 results. Where you apply the filter changes the answer.
| Strategy | What it does | Red stars returned |
|---|---|---|
| Post-filter | Take the top 3, then drop the blue ones | S8 (1 of 3) |
| Oversample ×2 | Take the top 6, then filter | S8, S3 (2 of 3) |
| Oversample ×3 | Take the top 9, then filter | S8, S3, S9 |
| Pre-filter | Keep only red stars, then search them | S8, S3, S9 |
The true top 3 has two blue stars, so post-filtering leaves one result where you asked for three. Oversampling helps, but how much is enough depends on how rare the condition is: ×2 still came up short because S1 (blue) sits closer than S9 (red). Pre-filtering always returns the right answer, but it searches a subset the index was not built for. A strict filter can leave an IVF list nearly empty or cut a graph into islands the walk cannot cross. Vector databases differ most in how they handle this middle ground, for example by checking the filter during the graph walk.
"""Exact search, an IVF index, a two-layer graph walk, and filters.
Twelve stars from a toy catalogue, each one a 2-D vector.
Real systems use hundreds of dimensions and millions of points.
Distance is squared Euclidean: the same order as Euclidean, no square root.
"""
# Star id -> (x, y, colour). The colour is metadata, not part of the vector.
STARS = {
"S1": (1, 2, "blue"), "S2": (2, 3, "blue"), "S3": (3, 1, "red"),
"S4": (4, 3, "blue"), "S5": (7, 1, "red"), "S6": (8, 3, "blue"),
"S7": (9, 2, "red"), "S8": (6, 4, "red"), "S9": (4, 8, "red"),
"S10": (5, 9, "blue"), "S11": (7, 8, "red"), "S12": (5, 5, "blue"),
}
QUERY = (4, 4)
# IVF: three centroids, placed by hand where k-means would roughly put them.
CENTROIDS = {"A": (2, 2), "B": (8, 2), "C": (5, 8)}
# The graph, drawn by hand. Layer 1 is a sparse express layer.
LAYER1 = {"S1": ["S7", "S10"], "S7": ["S1", "S10"], "S10": ["S1", "S7"]}
LAYER0_EDGES = [
("S1", "S2"), ("S1", "S3"), ("S2", "S4"), ("S3", "S4"),
("S4", "S12"), ("S4", "S8"), ("S8", "S12"), ("S8", "S6"),
("S6", "S7"), ("S5", "S6"), ("S5", "S8"), ("S12", "S9"),
("S9", "S10"), ("S10", "S11"), ("S11", "S12"),
]
ENTRY = "S10"
def dist(a, b):
"""Squared straight-line distance between two 2-D points."""
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def point(star):
x, y, _ = STARS[star]
return (x, y)
def exact_knn(query, k, stars=None):
"""Score every star. Correct by definition, and the cost grows with N."""
stars = list(STARS) if stars is None else stars
ranked = sorted(stars, key=lambda s: (dist(query, point(s)), int(s[1:])))
return ranked[:k], len(stars)
def build_lists():
"""Each star joins the list of its nearest centroid."""
lists = {name: [] for name in CENTROIDS}
for star in STARS:
home = min(CENTROIDS, key=lambda c: dist(point(star), CENTROIDS[c]))
lists[home].append(star)
return lists
def ivf_search(query, k, nprobe):
"""Rank the centroids, open the nprobe closest lists, scan only those."""
lists = build_lists()
order = sorted(CENTROIDS, key=lambda c: dist(query, CENTROIDS[c]))
probed = order[:nprobe]
candidates = [s for c in probed for s in lists[c]]
found, scanned = exact_knn(query, k, candidates)
return found, probed, len(CENTROIDS) + scanned
def recall(found, truth):
"""Share of the true top-k that the approximate search returned."""
return len(set(found) & set(truth)) / len(truth)
def layer0():
graph = {star: [] for star in STARS}
for a, b in LAYER0_EDGES:
graph[a].append(b)
graph[b].append(a)
return graph
def greedy(graph, start, query, seen):
"""Hop to the closest neighbour while it beats the current star."""
here, path = start, [start]
seen.add(start)
while True:
seen.update(graph[here])
best = min(graph[here], key=lambda s: dist(query, point(s)))
if dist(query, point(best)) >= dist(query, point(here)):
return here, path
here = best
path.append(here)
def graph_search(query):
"""Walk the express layer, drop down, walk again. Count every distance."""
seen = set()
here, top_path = greedy(LAYER1, ENTRY, query, seen)
here, low_path = greedy(layer0(), here, query, seen)
return here, top_path + low_path[1:], len(seen)
def filtered(query, k, colour, strategy, oversample=2):
"""pre: filter, then search. post: search k, then filter. over: search k*oversample, then filter."""
if strategy == "pre":
keep = [s for s in STARS if STARS[s][2] == colour]
return exact_knn(query, k, keep)[0]
pool = k if strategy == "post" else k * oversample
hits = exact_knn(query, pool)[0]
return [s for s in hits if STARS[s][2] == colour][:k]
def scale(n=10_000_000, dim=768, nlist=1000, nprobe=10):
"""Exact multiply-adds per query, and vectors IVF touches with even lists."""
exact_ops = n * dim
ivf_vectors = nlist + nprobe * (n // nlist)
return exact_ops, ivf_vectors
def pq_bytes(dim=768, sub_vectors=96):
"""float32 storage versus one byte per sub-vector code."""
return dim * 4, sub_vectors
Reporting speed without recall. An index that opens one list is fast and wrong. Always measure recall@k against exact search on a sample of real queries, then tune nprobe or ef.
Filtering after the search and trusting the count. Post-filtering returned 1 star when you asked for 3. Check how many results came back, and oversample or pre-filter when the condition is rare.
Using an ANN index on a tiny collection. On 12 stars, IVF at full recall did 15 distances against exact search’s 12. Below a few tens of thousands of vectors, exact search is often fast enough and never misses.
Mixing the distance the model was trained for. If the encoder was trained with cosine or dot product, index with that. Squared distance gives the same order as cosine only when every vector has length 1.
Only list A is opened, because centroid A is closest to the query. S12 is filed under C and S8 under B, so they are never measured.
It measures the 3 centroids and then all 12 stars anyway. The centroid step only saves work when most lists stay closed.
Long hops. The walk crosses the sky in a few steps before it switches to short links, instead of crawling there one neighbour at a time.
Post-filtering. Oversample enough candidates before filtering, or pre-filter so the search only sees red stars.