Vector Search: Nearest Neighbors at Scale
After this lesson, you will be able to:
- Compare two vectors with Euclidean distance and with cosine similarity, and say when the two rankings agree
- Explain why exact search costs O(n d) per query, and prove in words that no exact method can skip a point on arbitrary data
- Describe the curse of dimensionality in plain words, and show with a k-d tree why a tree index stops helping as d grows
- Build random-hyperplane hashing, a clustered (IVF) index and a navigable-graph search, each with a counter for distance computations
- Hand-trace a greedy graph walk, explain why it can get stuck, and say what the layers and the width ef of HNSW fix
- Measure recall against an exact baseline, read a recall versus speed table, and explain what quantization trades away
Before You Start
#The Nearest Neighbor Question
Nothing here is free. Every index trades three things against each other: recall, query speed, and the memory and build time it needs. The rest of the lesson shows how each method makes that trade, with a counter that counts distance computations so you can see the saving without a stopwatch.
#Distance and Cosine Similarity
Both cost O(d) for one pair, because each reads every number once. Try the next question before you read the code.
Take cat = (4, 3), kitten = (8, 6) and car = (1, 5). The kitten vector points the same way as cat but is twice as long. Which statement is true?
import math
def euclid(a, b):
"""Straight-line distance between two vectors. Cost: O(d) for d numbers each."""
return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))
def cosine(a, b):
"""Cosine similarity. 1 = same direction, 0 = right angle, -1 = opposite. Cost: O(d)."""
dot = sum(x * y for x, y in zip(a, b))
return dot / (math.sqrt(sum(x * x for x in a)) * math.sqrt(sum(y * y for y in b)))
cat, kitten, car = [4.0, 3.0], [8.0, 6.0], [1.0, 5.0]
for name, other in (("kitten", kitten), ("car", car)):
print("cat vs", name, " distance", round(euclid(cat, other), 3), " cosine", round(cosine(cat, other), 3))
# Output:
# cat vs kitten distance 5.0 cosine 1.0
# cat vs car distance 3.606 cosine 0.745The two measures can disagree, so the choice matters. Embedding models are usually trained with one of them in mind, and the model's documentation says which. Many models output vectors already scaled to length 1. For two such unit vectors the dot product is the cosine, and the squared Euclidean distance equals 2 minus 2 times the cosine. So on unit vectors the closest by distance is also the most similar by cosine, and the two rankings are identical.
That fact is useful: normalize once when you store the vectors, and then every query is a plain dot product.
#Exact Search and Its Cost
recall, and keeps the true answers as the ground truth for every later comparison.import random
def make_data(n, d, blobs, seed):
"""n points in d dimensions grouped into blobs, plus 30 queries drawn the same way."""
rng = random.Random(seed)
centers = [[rng.uniform(-1, 1) for _ in range(d)] for _ in range(blobs)]
def draw():
c = centers[rng.randrange(blobs)]
return [x + rng.gauss(0, 0.25) for x in c]
return [draw() for _ in range(n)], [draw() for _ in range(30)]
def exact_top(points, q, k):
"""Ids of the k nearest points, found by looking at every point. Time O(n d + n log n), extra space O(n)."""
return [i for _, i in sorted((euclid(q, p), i) for i, p in enumerate(points))[:k]]
def recall(found, truth):
"""Share of the true neighbors that the approximate answer also contains."""
return len(set(found) & set(truth)) / len(truth)
points, queries = make_data(1200, 16, 15, seed=11)
truth = [exact_top(points, q, 5) for q in queries]
print(len(points), "points,", len(queries), "queries")
print("true 5 nearest of query 0:", truth[0])
print("recall of a perfect answer:", recall(truth[0], truth[0]))
print("recall of a half-right answer:", recall(truth[0][:2] + [-1, -2, -3], truth[0]))
# Output:
# 1200 points, 30 queries
# true 5 nearest of query 0: [525, 308, 350, 575, 621]
# recall of a perfect answer: 1.0
# recall of a half-right answer: 0.4heapq.nsmallest does, costs O(n log k) instead. The extra space is O(n) for the scores, or O(k) with the heap. To feel the size: a million vectors of 768 numbers means 768,000,000 number operations for one query.There is also a floor, and it is worth seeing why. Suppose a method answers an exact query on arbitrary, unorganized data without looking at some point p. An adversary can then place the query right on top of p, where p is the unique nearest neighbor. The method never looked at p, so it is wrong. Therefore any exact method must read every point, which is Omega(n), unless the data has structure it can use.
So an index must either exploit structure in the data or accept some wrong answers. The first idea, a tree that exploits space, works well until the dimension grows. To see why it fails, first look at what high dimensions do to distances.
#The Curse of Dimensionality in Plain Words
def contrast(d, n=500, seed=1):
"""(farthest - nearest) / nearest for one random query among n random points in d dimensions."""
rng = random.Random(seed)
pts = [[rng.random() for _ in range(d)] for _ in range(n)]
q = [rng.random() for _ in range(d)]
dists = [euclid(q, p) for p in pts]
return (max(dists) - min(dists)) / min(dists)
for d in (2, 10, 100, 1000):
side = 0.1 ** (1 / d) # side of a box (a cube in d dimensions) that holds 10 percent of uniform points
print("d =", d, " spread:", round(contrast(d), 2), " box side for 10% of the points:", round(side, 3))
# Output:
# d = 2 spread: 30.02 box side for 10% of the points: 0.316
# d = 10 spread: 2.04 box side for 10% of the points: 0.794
# d = 100 spread: 0.37 box side for 10% of the points: 0.977
# d = 1000 spread: 0.12 box side for 10% of the points: 0.998In two dimensions the farthest point is about 30 times farther than the nearest. In 1,000 dimensions it is only 12 percent farther. Every point has become almost equally far away. The reason is simple. A distance adds up one squared difference per coordinate. With few coordinates, one lucky small difference can make a point stand out. With a thousand, the sum is an average of many random parts, and averages of many parts cluster near the middle.
The last column gives a second picture. To capture 10 percent of uniform points you need a box covering about 32 percent of each side in two dimensions, but 98 percent of each side in a hundred. A small box that holds a few neighbors simply does not exist.
One more view: cutting each axis once gives 2 to the power d cells. With d = 20 that is 1,048,576 cells, more than a million-point database can fill.
This is not the full story, and it is not a reason to give up. Real embeddings are not uniform noise. They lie near a lower-dimensional shape, with clusters and directions that matter more than others. That structure is what the index methods below use, and it is why they work on real data even when the raw dimension is large.
#k-d Trees and Why They Fail
Here is a small trace. The six points are (2,3), (5,4), (9,6), (4,7), (8,1) and (7,2). Splitting by x at the median makes (7,2) the root. Its left subtree holds (2,3), (5,4) and (4,7), and its right subtree holds (9,6) and (8,1). The query is (9,2).
- Visit the root (7,2). Distance 2. The query's x is 9, bigger than 7, so go right first.
- Visit (9,6). Distance 4, worse than 2. The query's y is 2, below 6, so go to its left child.
- Visit (8,1). Distance about 1.41, the new best.
- Come back to (9,6). Its wall is 4 away, more than 1.41, so skip its other side.
- Come back to the root. Its wall is 2 away, more than 1.41, so skip the entire left subtree.
Three distance computations out of six found the answer. Now the code, and a prediction before the numbers. We will build the tree for 2,000 uniform random points in 2, 6 and 12 dimensions and average the distance computations over 20 queries.
The k-d tree holds 2,000 uniform random points. How does the average number of distance computations per nearest-neighbor query change as the dimension goes from 2 to 6 to 12?
class Node:
def __init__(self, idx, axis, left, right):
self.idx, self.axis, self.left, self.right = idx, axis, left, right
def build_kd(points, idxs, depth=0):
"""Split on one axis at a time, at the median. Time O(n log² n) because of the sorts; space O(n)."""
if not idxs:
return None
axis = depth % len(points[0])
idxs = sorted(idxs, key=lambda i: points[i][axis])
mid = len(idxs) // 2
return Node(idxs[mid], axis,
build_kd(points, idxs[:mid], depth + 1),
build_kd(points, idxs[mid + 1:], depth + 1))
def kd_nearest(points, node, q, best, stats):
"""best is [distance, index]. stats[0] counts distance computations."""
if node is None:
return
d = euclid(q, points[node.idx])
stats[0] += 1
if d < best[0]:
best[0], best[1] = d, node.idx
gap = q[node.axis] - points[node.idx][node.axis]
near, far = (node.left, node.right) if gap < 0 else (node.right, node.left)
kd_nearest(points, near, q, best, stats)
if abs(gap) < best[0]: # the wall is closer than our best, so the far side may hold a winner
kd_nearest(points, far, q, best, stats)
tiny = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
tiny_root = build_kd(tiny, list(range(len(tiny))))
best, stats = [float("inf"), -1], [0]
kd_nearest(tiny, tiny_root, (9, 2), best, stats)
print("tiny tree: nearest is", tiny[best[1]], "after", stats[0], "of", len(tiny), "distance computations")
n = 2000
for d in (2, 6, 12):
rng = random.Random(3)
pts = [[rng.random() for _ in range(d)] for _ in range(n)]
root = build_kd(pts, list(range(n)))
total = 0
for _ in range(20):
q = [rng.random() for _ in range(d)]
best, stats = [float("inf"), -1], [0]
kd_nearest(pts, root, q, best, stats)
total += stats[0]
print("d =", d, " average distance computations:", total // 20, "of", n)
# Output:
# tiny tree: nearest is (8, 1) after 3 of 6 distance computations
# d = 2 average distance computations: 17 of 2000
# d = 6 average distance computations: 158 of 2000
# d = 12 average distance computations: 1848 of 2000abs(gap) < best[0] is the culprit. When all distances look alike, the best distance found is bigger than the gap to almost every wall, so almost every branch has to be visited.The costs, with their assumptions. Building by sorting at each level is O(n log² n) time, or O(n log n) with a linear-time median finder. The space is O(n). A query takes about O(log n) time when d is small and the data is spread evenly, and O(n) in the worst case.
A common rule of thumb says a k-d tree helps only when n is much larger than 2 to the power d.
#Locality-Sensitive Hashing: Random Hyperplanes
Two vectors at a small angle are rarely split by a random wall. For random walls, the chance that two vectors land on opposite sides is exactly their angle divided by pi. The next cell checks that on the cat and car vectors, then shows what many bits and many tables do.
cat, car = [4.0, 3.0], [1.0, 5.0]
rng = random.Random(0)
agree = 0
for _ in range(10000):
plane = [rng.gauss(0, 1), rng.gauss(0, 1)]
side_cat = plane[0] * cat[0] + plane[1] * cat[1] >= 0
side_car = plane[0] * car[0] + plane[1] * car[1] >= 0
agree += side_cat == side_car
angle = math.acos(cosine(cat, car))
print("planes that keep cat and car together:", round(agree / 10000, 2), " formula 1 - angle/pi:", round(1 - angle / math.pi, 2))
def same_bucket_chance(p, bits, tables):
"""p = chance that ONE random plane puts two vectors on the same side."""
one_table = p ** bits
return one_table, 1 - (1 - one_table) ** tables
for label, p in (("close pair", 0.9), ("far pair", 0.5)):
one, many = same_bucket_chance(p, bits=8, tables=12)
print(label, " one table:", round(one, 3), " twelve tables:", round(many, 3))
# Output:
# planes that keep cat and car together: 0.77 formula 1 - angle/pi: 0.77
# close pair one table: 0.43 twelve tables: 0.999
# far pair one table: 0.004 twelve tables: 0.046With 8 bits and 12 tables, a close pair (p = 0.9) shares a bucket almost surely, 0.999, while a far pair (p = 0.5) does so only 4.6 percent of the time. The curve is steep in the right place. Now the whole index, measured against the exact answers.
def make_planes(d, bits, rng):
return [[rng.gauss(0, 1) for _ in range(d)] for _ in range(bits)]
def signature(planes, v):
"""One bit per plane: which side of the plane v is on."""
return tuple(1 if sum(p * x for p, x in zip(plane, v)) >= 0 else 0 for plane in planes)
class LSH:
def __init__(self, points, bits, tables, seed):
rng = random.Random(seed)
self.points = points
self.planes = [make_planes(len(points[0]), bits, rng) for _ in range(tables)]
self.tables = []
for planes in self.planes:
table = {}
for i, p in enumerate(points):
table.setdefault(signature(planes, p), []).append(i)
self.tables.append(table)
def search(self, q, k):
"""Collect q's bucket from every table, then rank only those candidates exactly."""
cands = set()
for planes, table in zip(self.planes, self.tables):
cands.update(table.get(signature(planes, q), []))
ranked = sorted((euclid(q, self.points[i]), i) for i in cands)
return [i for _, i in ranked[:k]], len(cands)
for bits, tables in ((8, 1), (8, 4), (8, 12), (14, 12)):
lsh = LSH(points, bits, tables, seed=5)
r = s = 0
for q, t in zip(queries, truth):
got, scanned = lsh.search(q, 5)
r += recall(got, t)
s += scanned
print(bits, "bits,", tables, "tables: recall", round(r / len(queries), 2),
" candidates ranked", s // len(queries), "of", len(points))
# Output:
# 8 bits, 1 tables: recall 0.46 candidates ranked 36 of 1200
# 8 bits, 4 tables: recall 0.85 candidates ranked 80 of 1200
# 8 bits, 12 tables: recall 0.99 candidates ranked 153 of 1200
# 14 bits, 12 tables: recall 0.89 candidates ranked 55 of 1200One table of 8 bits ranks only 36 candidates but finds 46 percent of the true neighbors. Twelve tables find 99 percent, ranking 153 of 1,200 vectors. Look at the last row: 14 bits is stricter, the buckets are tiny, and recall falls to 0.89 even with 12 tables. More bits means fewer false matches and more misses. More tables does the opposite. You tune the pair against your data.
The costs. Building takes O(n L b d) time for L tables of b bits, and the tables need O(n L) space on top of the vectors. A query computes L signatures in O(L b d) and then ranks its candidates exactly, at O(d) each.
One assumption matters: the guarantee is about angles, so the method fits cosine similarity most directly. On real data, recall depends on how well the data fits, which is why you always measure it.
You raise the number of bits per signature from 8 to 14 and keep 12 tables. What do you expect, and what did the cell above show?
#Clustering First: The IVF Idea
nprobe lists. The rest of the database is never touched. It is the same trick as a library: you walk to the right aisle instead of reading every spine.def mean(vs):
return [sum(c) / len(vs) for c in zip(*vs)]
def kmeans(points, k, rounds, seed):
"""Pick k starting centers, then repeat: give each point to its nearest center, move each center to the mean."""
rng = random.Random(seed)
centers = [list(points[i]) for i in rng.sample(range(len(points)), k)]
for _ in range(rounds):
groups = [[] for _ in centers]
for i, p in enumerate(points):
groups[min(range(k), key=lambda c: euclid(p, centers[c]))].append(i)
centers = [mean([points[i] for i in g]) if g else centers[j] for j, g in enumerate(groups)]
return centers
class IVF:
def __init__(self, points, k, seed):
self.points = points
self.centers = kmeans(points, k, 5, seed)
self.lists = [[] for _ in self.centers]
for i, p in enumerate(points):
self.lists[min(range(k), key=lambda c: euclid(p, self.centers[c]))].append(i)
def search(self, q, k, nprobe):
"""Look inside only the nprobe lists whose center is closest to q. Returns (ids, distance computations)."""
order = sorted(range(len(self.centers)), key=lambda c: euclid(q, self.centers[c]))
work = len(self.centers)
ranked = []
for c in order[:nprobe]:
for i in self.lists[c]:
ranked.append((euclid(q, self.points[i]), i))
work += 1
ranked.sort()
return [i for _, i in ranked[:k]], work
ivf = IVF(points, 15, seed=2)
for nprobe in (1, 2, 4, 8):
r = w = 0
for q, t in zip(queries, truth):
got, work = ivf.search(q, 5, nprobe)
r += recall(got, t)
w += work
print("nprobe", nprobe, ": recall", round(r / len(queries), 2),
" distance computations", w // len(queries), "of", len(points))
# Output:
# nprobe 1 : recall 0.96 distance computations 109 of 1200
# nprobe 2 : recall 1.0 distance computations 181 of 1200
# nprobe 4 : recall 1.0 distance computations 356 of 1200
# nprobe 8 : recall 1.0 distance computations 719 of 1200nprobe exists.The costs. A query computes c distances to the centers, then scans about nprobe times n over c vectors. With balanced lists that is O((c + nprobe n / c) d) time. Choosing c near the square root of n balances the two terms, giving roughly O(d sqrt(n · nprobe)).
nprobe.#Navigable Graphs and HNSW
Here is a six-point graph. The points are A(0,0), B(3,0), C(6,1), D(4,4), E(8,4) and F(1,4). The links run A-B, A-F, B-C, B-D, D-E and D-F. The query is (7,3). To keep the arithmetic easy, the table uses squared distances. The square root never changes the order. The squared distances from the query are A 58, B 25, C 5, D 10, E 2 and F 37, so the true nearest is E.
A greedy walk starts at A, always moves to the neighbor closest to the query (7,3), and stops when no neighbor is closer than where it stands. Using the six points and links above, which node does it stop at?
The walk, step by step:
- At A (58) the neighbors are B (25) and F (37). Move to B. Three distances computed.
- At B (25) the neighbors are A, seen already, C (5) and D (10). Move to C. Five computed.
- At C (5) the only neighbor is B, which is worse. Stop. The answer is C, after five distance computations, and it is wrong.
ef best candidates found so far, and keep expanding the closest one not yet expanded. Stop when that candidate is worse than all ef you keep.With ef = 2, the walk keeps C and D, expands C (no news), expands D, finds E (2), and the answer becomes E after six computations. The code below runs both.
import heapq
def graph_search(points, graph, q, entry, ef, k):
"""Best-first walk over a graph. ef = how many candidates stay alive. Returns (top-k ids, distance computations)."""
d0 = euclid(q, points[entry])
work = 1
seen = {entry}
frontier = [(d0, entry)] # min-heap: the closest unexpanded node comes out first
best = [(-d0, entry)] # max-heap (negated): the ef best nodes found so far
while frontier:
d, u = heapq.heappop(frontier)
if len(best) >= ef and d > -best[0][0]:
break # the closest unexpanded node is worse than all ef we keep: stop
for v in graph[u]:
if v in seen:
continue
seen.add(v)
dv = euclid(q, points[v])
work += 1
if len(best) < ef or dv < -best[0][0]:
heapq.heappush(frontier, (dv, v))
heapq.heappush(best, (-dv, v))
if len(best) > ef:
heapq.heappop(best) # drop the worst of the kept candidates
top = sorted((-nd, i) for nd, i in best)[:k]
return [i for _, i in top], work
pts = {"A": (0, 0), "B": (3, 0), "C": (6, 1), "D": (4, 4), "E": (8, 4), "F": (1, 4)}
graph = {"A": ["B", "F"], "B": ["A", "C", "D"], "C": ["B"],
"D": ["B", "E", "F"], "E": ["D"], "F": ["A", "D"]}
query = (7, 3)
for ef in (1, 2, 3):
ids, work = graph_search(pts, graph, query, "A", ef, 1)
print("ef", ef, "->", ids, "after", work, "distance computations")
# Output:
# ef 1 -> ['C'] after 5 distance computations
# ef 2 -> ['E'] after 6 distance computations
# ef 3 -> ['E'] after 6 distance computationsfrontier heap gives the next candidate to expand, and the best heap holds the ef kept so far. It is a bounded version of Dijkstra's idea from the shortest paths lesson, with the distance to the query instead of the distance from the source.HNSW keeps a stack of graphs, like the express and local lines of a subway. The top layer holds a small random sample of the vectors with long links. The search walks greedily there, drops to the next layer at the point it reached, and continues down to the bottom layer, which holds everything. The cell below builds a toy version with one sparse layer and a few random long links.
Step through a query. The viewer is a two-dimensional picture with a random layout and a made-up assignment of nodes to layers, not real embeddings, so read it for the shape of the walk: a long hop on a sparse layer, then smaller hops on denser ones.
gpoints, gqueries = make_data(400, 12, 8, seed=4)
gtruth = [exact_top(gpoints, q, 5) for q in gqueries]
def build_graph(points, ids, m, far, seed):
"""Link every id to its m nearest others, plus `far` random long links, all two-way.
The long links are the small-world part. Brute-force build: time O(len(ids)² d)."""
rng = random.Random(seed)
graph = {i: [] for i in ids}
for i in ids:
near = sorted((euclid(points[i], points[j]), j) for j in ids if j != i)[:m]
for _, j in near:
if j not in graph[i]:
graph[i].append(j)
if i not in graph[j]:
graph[j].append(i)
for _ in range(far):
j = rng.choice(ids)
if j != i and j not in graph[i]:
graph[i].append(j)
graph[j].append(i)
return graph
base = build_graph(gpoints, list(range(len(gpoints))), 5, 1, 1)
top_ids = list(range(0, len(gpoints), 10)) # every 10th point also lives on a sparse top layer
top = build_graph(gpoints, top_ids, 4, 1, 2)
def two_layer(q, ef, k):
"""Greedy on the sparse layer picks an entry point, then the dense layer refines."""
(entry,), w1 = graph_search(gpoints, top, q, top_ids[0], 1, 1)
ids, w2 = graph_search(gpoints, base, q, entry, ef, k)
return ids, w1 + w2
runs = (("one layer, ef=1", lambda q: graph_search(gpoints, base, q, 0, 1, 5)),
("one layer, ef=10", lambda q: graph_search(gpoints, base, q, 0, 10, 5)),
("two layers, ef=10", lambda q: two_layer(q, 10, 5)),
("two layers, ef=30", lambda q: two_layer(q, 30, 5)))
for label, run in runs:
r = w = 0
for q, t in zip(gqueries, gtruth):
got, work = run(q)
r += recall(got, t)
w += work
print(label, ": recall", round(r / len(gqueries), 2),
" distance computations", w // len(gqueries), "of", len(gpoints))
# Output:
# one layer, ef=1 : recall 0.17 distance computations 41 of 400
# one layer, ef=10 : recall 0.97 distance computations 83 of 400
# two layers, ef=10 : recall 0.97 distance computations 87 of 400
# two layers, ef=30 : recall 1.0 distance computations 127 of 400Greedy alone (ef = 1) finds only 17 percent of the true neighbors, which is the stuck-walk problem at work. A beam of 10 gives 97 percent while computing 83 of 400 distances. On 400 points the second layer barely changes the cost. That is honest: layers pay off when n is in the millions and the hop count would otherwise be huge. With two layers and ef = 30, recall reaches 1.0 for 127 computations.
The costs, and what is not promised. Each hop reads at most M links, where M is the number of neighbors kept per node. So a query computes about M times the number of hops, times a small beam factor. On real data the hop count is reported to grow slowly, roughly like log n, but there is no worst-case proof. A chain graph with no shortcuts visits every node, and problem 5 below shows it.
The space is O(n M) for the links plus the vectors. Real implementations insert each point by searching the existing graph, so building costs about n searches. Our brute-force builder costs O(n² d), fine for a lesson and unusable at scale.
#Recall Versus Speed
nprobe for IVF, and ef for HNSW. Turn it up and recall and cost rise together. Here are the numbers from the runs above, on 1,200 or 400 vectors, so read the shape and not the sizes.| Method | Cheapest setting | Costlier setting |
|---|---|---|
| LSH (8 bits) | 1 table: recall 0.46, 36 ranked | 12 tables: recall 0.99, 153 ranked |
| IVF (15 lists) | nprobe 1: recall 0.96, 109 computed | nprobe 2: recall 1.0, 181 computed |
| HNSW toy (400 points) | ef 1: recall 0.17, 41 computed | ef 30: recall 1.0, 127 computed |
To choose a setting, measure. Keep a few hundred sample queries, compute their exact top-k once with the slow scan, and then for each setting record the recall and the number of distance computations. Pick the cheapest setting that meets the recall your application needs. Distance computations are a stand-in for speed. Real latency also depends on memory access, so confirm the winner with a clock before you ship.
Two honest warnings. Recall measures how well the index imitates exact search. It says nothing about whether exact search gives the answers your users want, which is a question about the embedding model. And recall averaged over queries can hide a bad group, such as rare queries far from every blob, so look at the worst queries too.
#Quantization: Smaller Vectors
The cell below uses a plain scalar version: split the value range into equal slots and keep only the slot number.
lo = min(min(p) for p in points)
hi = max(max(p) for p in points)
def quantize(v, levels):
"""Replace each number by the slot it falls in, 0 .. levels-1."""
step = (hi - lo) / levels
return [min(levels - 1, int((x - lo) / step)) for x in v]
def dequantize(code, levels):
"""Turn slot numbers back into approximate floats (the middle of each slot)."""
step = (hi - lo) / levels
return [lo + (c + 0.5) * step for c in code]
for levels in (4, 16, 256):
approx = [dequantize(quantize(p, levels), levels) for p in points]
r = r2 = 0
for q, t in zip(queries, truth):
ranked = sorted((euclid(q, a), i) for i, a in enumerate(approx))
r += recall([i for _, i in ranked[:5]], t)
short = [i for _, i in ranked[:20]] # keep 20 candidates, then re-rank them with the true vectors
final = sorted((euclid(q, points[i]), i) for i in short)[:5]
r2 += recall([i for _, i in final], t)
bits = levels.bit_length() - 1
print(levels, "levels,", bits, "bits per number,", 32 // bits, "x smaller than 32-bit floats: recall",
round(r / len(queries), 2), "| with re-rank", round(r2 / len(queries), 2))
# Output:
# 4 levels, 2 bits per number, 16 x smaller than 32-bit floats: recall 0.29 | with re-rank 0.75
# 16 levels, 4 bits per number, 8 x smaller than 32-bit floats: recall 0.72 | with re-rank 0.99
# 256 levels, 8 bits per number, 4 x smaller than 32-bit floats: recall 0.96 | with re-rank 1.0Compression does not change the O(n d) shape of a full scan, but it cuts the memory read per number, and memory traffic is often what limits a scan. It also lets a larger database fit in memory.
#Which Index?
Choose by size, by how much recall you need, and by how the data changes.
| Situation | Reasonable choice | Why |
|---|---|---|
| Thousands of vectors, or recall must be 100% | Exact scan | One pass is cheap, it is always right, and there is nothing to tune |
| Low dimension (below about 10), static data | k-d tree | Skips most points when the geometry is simple |
| Memory is tight, many vectors | IVF with compressed vectors, then re-rank | Few lists searched, small codes stored |
| Millions of vectors, high recall, fast queries | Graph index (HNSW) | Few distance computations per query, at the price of memory for links |
| Quick, simple, angle-based | Random-hyperplane LSH | Easy to build, but you tune bits and tables |
When not to build an index: when n is small enough that a scan answers inside your time limit, or when the data changes so fast that rebuilding costs more than it saves. An index also adds a second thing to get wrong, a recall number that can drift as the data grows, so only add one when the scan is truly too slow.
#Where This Shows Up
Retrieval-augmented generation looks up the stored passages nearest to a question's embedding and hands them to a language model. The step that finds them is a nearest-neighbor query, and vector databases exist mostly to run it fast. For example, graph indexes of the HNSW kind are offered by many vector databases and search libraries. Search engines can combine keyword matching with a vector query, and recommendation systems rank items by closeness to a user vector.
heapq.nsmallest is the small cousin of all this: it keeps a short list of the best so far while it scans. The habit to carry is the method. Set a baseline with the exact answer, then trade a measured amount of recall for speed.#Common Mistakes
#Try It: Five Problems
Work through the ladder in order. Problem 1 is the exact baseline with a counter. Problem 2 is cosine search, with a zero vector to survive. Problem 3 hashes with fixed planes and misses a neighbor on purpose. Problem 4 is the greedy walk, with a counter. Problem 5 is adversarial: find how wide the beam must be, including cases where no beam works and a chain where the walk visits every node.
Tests · Expected output, line by line. Line 1: ([0, 2], 5) ([0, 2, 4, 1, 3], 5) ([], 0), meaning ties go to the smaller id, k larger than n returns everything, and an empty database does zero work. Line 2: [0, 2, 4] [0, 2, 4, 3], where the zero vector is skipped and the long vector (10, 1) still ranks by direction. Line 3: ([0, 1], 0) ([], None) ([2, 3], 3), so an empty bucket returns None. Line 4: ('C', 7) ('E', 2), so the walk from A is stuck at C but the walk from E stays at E. Line 5: (2, 6) None (1, 3) (1, 200), where the trap needs ef 2, a broken graph has no answer, and the chain visits all 200 nodes even at ef 1.
#Recap
Vector search asks for the top-k stored vectors nearest to a query, by Euclidean distance or by cosine similarity. On unit vectors the two rank identically. Exact search costs O(n d) per query, and on unorganized data no exact method can skip a point.
In high dimensions distances bunch together, so a k-d tree can skip almost nothing. Approximate indexes accept lost recall for speed. Random-hyperplane hashing uses bits (AND) and tables (OR). IVF probes only the closest clusters. HNSW walks a layered neighbor graph with a beam of width ef, and can get stuck without one.
Quantization stores fewer bits per number, and re-ranking repairs the loss. Choose the setting by measuring recall against an exact baseline on queries kept out of the data.
A database holds n vectors of d numbers. A query asks for the exact nearest vector with a plain scan. What is the time cost, and why?
Key Takeaways
- Exact top-k search costs O(n d) per query, and on unorganized data no exact method can skip a point, so every index buys speed with recall
- Cosine and Euclidean rankings agree on unit vectors, so normalize once at storage time
- In high dimensions distances bunch together, which is why a k-d tree degrades from 17 touched points at d = 2 to 1,848 of 2,000 at d = 12
- Hashing uses bits as an AND and tables as an OR, IVF probes the nprobe closest clusters, and HNSW walks a layered graph with a beam of width ef
- Quantization stores fewer bits per number, and re-ranking a short list with full vectors repairs most of the loss
- Measure recall against an exact baseline on held-out queries, and pick the cheapest setting that meets your target