Skip to content

3. Vector search & indexes

Intermediate · 14 min read

Comparing a query with every vector is exact and simple — and fine up to a few hundred thousand vectors. Beyond that, vector databases use approximate nearest-neighbour (ANN) indexes: they look at only a small fraction of the vectors and accept that they will occasionally miss a true neighbour. This page builds that trade-off in NumPy.

Real embeddings are clustered by topic, and although they have hundreds of dimensions, the meaningful variation lives in far fewer directions. Simulate 20,000 such vectors — 50 topics in a 12-dimensional "meaning space", projected to 64 dimensions with a little noise:

import numpy as np

rng = np.random.default_rng(0)
N, D, TOPICS, LATENT = 20_000, 64, 50, 12

centres = rng.normal(size=(TOPICS, LATENT))
meaning = centres[rng.integers(0, TOPICS, N)] + rng.normal(scale=0.5, size=(N, LATENT))
X = meaning @ rng.normal(size=(LATENT, D)) + rng.normal(scale=0.3, size=(N, D))
X = (X / np.linalg.norm(X, axis=1, keepdims=True)).astype(np.float32)

queries = X[rng.choice(N, 200, replace=False)] + rng.normal(scale=0.05, size=(200, D)).astype(np.float32)
queries /= np.linalg.norm(queries, axis=1, keepdims=True)

def exact_topk(q, k=10):
    scores = X @ q
    top = np.argpartition(-scores, k)[:k]
    return top[np.argsort(-scores[top])]

truth = [set(exact_topk(q)) for q in queries]          # the right answers, to measure recall against
print(X.shape, X.dtype, f"{X.nbytes / 1e6:.1f} MB")
Output
(20000, 64) float32 5.1 MB

Exact search does N × D multiply-adds per query. At 10 million vectors of 1,536 dimensions that's 15 billion per query — too slow for an interactive app.

Recall@k measures how good an approximate index is: of the true top-10, how many did it return?

def recall(search_fn, k=10):
    return np.mean([len(set(search_fn(q, k)) & t) / k for q, t in zip(queries, truth)])

print("exact search recall:", recall(exact_topk))
Output
exact search recall: 1.0

3.2 IVF — search only the nearest clusters

IVF (inverted file index) clusters the vectors with k-means. At query time it finds the few cluster centroids closest to the query and searches only those clusters. nprobe = how many clusters to search.

def kmeans(data, k, iters=10, seed=0):
    r = np.random.default_rng(seed)
    c = data[r.choice(len(data), k, replace=False)].copy()
    for _ in range(iters):
        assign = np.argmax(data @ c.T, axis=1)                  # nearest centroid (cosine)
        for j in range(k):
            members = data[assign == j]
            if len(members):
                c[j] = members.mean(axis=0)
        c /= np.linalg.norm(c, axis=1, keepdims=True)
    return c, np.argmax(data @ c.T, axis=1)

N_LISTS = 100                                                    # rule of thumb: ~sqrt(N) to 4*sqrt(N)
centroids, assign = kmeans(X, N_LISTS)
lists = [np.where(assign == j)[0] for j in range(N_LISTS)]       # the "inverted lists"

def ivf_search(q, k=10, nprobe=4):
    probe = np.argsort(-(centroids @ q))[:nprobe]
    candidates = np.concatenate([lists[j] for j in probe])
    scores = X[candidates] @ q
    top = np.argsort(-scores)[:k]
    return candidates[top]

for nprobe in (1, 2, 4, 8, 16):
    scanned = np.mean([sum(len(lists[j]) for j in np.argsort(-(centroids @ q))[:nprobe]) for q in queries]) / N
    r = recall(lambda q, k: ivf_search(q, k, nprobe))
    print(f"nprobe={nprobe:2}  recall@10={r:.3f}  vectors scanned={scanned:.1%}")
Output
nprobe= 1  recall@10=0.820  vectors scanned=1.3%
nprobe= 2  recall@10=0.948  vectors scanned=2.2%
nprobe= 4  recall@10=0.990  vectors scanned=4.1%
nprobe= 8  recall@10=0.999  vectors scanned=8.1%
nprobe=16  recall@10=1.000  vectors scanned=16.0%

This is the core trade-off of every ANN index: scan a few percent of the data, get almost all of the right answers. Turning nprobe up buys recall with speed. Misses happen when a true neighbour sits in a cluster next to the query's cluster.

3.3 HNSW — a navigable graph

HNSW (Hierarchical Navigable Small World) is the most widely used ANN index (pgvector, Qdrant, Weaviate, Chroma, Pinecone, OpenSearch all offer it). It links every vector to a few dozen near neighbours, in several layers:

flowchart TB
    subgraph L2[Top layer: few nodes, long jumps]
      A2((A)) --- F2((F))
    end
    subgraph L1[Middle layer]
      A1((A)) --- C1((C)) --- F1((F)) --- H1((H))
    end
    subgraph L0[Bottom layer: every vector, short links]
      A0((A)) --- B0((B)) --- C0((C)) --- D0((D)) --- E0((E)) --- F0((F)) --- G0((G)) --- H0((H))
    end
    A2 -.-> A1 -.-> A0
    F2 -.-> F1 -.-> F0

Search starts at the top, greedily jumps to whichever neighbour is closest to the query, and drops a layer each time it can't get closer — like taking a flight, then a train, then walking. A simplified two-level version shows the idea: a small random sample stands in for the upper layers (it finds good entry points), then a beam search walks the bottom-layer neighbour graph:

import heapq

def build_knn_graph(data, m=16):
    graph = []
    for i in range(0, len(data), 2000):                         # in blocks, to limit memory
        sims = data[i:i + 2000] @ data.T
        graph.extend(np.argsort(-sims, axis=1)[:, 1:m + 1])     # m nearest neighbours (position 0 is itself)
    return np.array(graph)

GRAPH = build_knn_graph(X)
UPPER = np.random.default_rng(1).choice(N, 500, replace=False)  # stand-in for HNSW's upper layers

def graph_search(q, k=10, ef=64):
    sim = lambda i: float(X[i] @ q)
    entries = UPPER[np.argsort(-(X[UPPER] @ q))[:4]]            # "fly" to the right region
    visited = set(entries.tolist())
    to_explore = [(-sim(e), e) for e in entries]                # max-heap of nodes to expand
    best = [(sim(e), e) for e in entries]                       # min-heap of the ef best found so far
    heapq.heapify(to_explore); heapq.heapify(best)
    while to_explore:
        neg_s, node = heapq.heappop(to_explore)
        if len(best) >= ef and -neg_s < best[0][0]:
            break                                               # nothing left that could improve the results
        for nb in map(int, GRAPH[node]):                        # "walk" to neighbours
            if nb in visited:
                continue
            visited.add(nb)
            s = sim(nb)
            if len(best) < ef or s > best[0][0]:
                heapq.heappush(to_explore, (-s, nb))
                heapq.heappush(best, (s, nb))
                if len(best) > ef:
                    heapq.heappop(best)
    return [i for _, i in sorted(best, reverse=True)[:k]], len(visited)

for ef in (16, 32, 64, 128):
    results = [graph_search(q, ef=ef) for q in queries]
    r = np.mean([len(set(res) & t) / 10 for (res, _), t in zip(results, truth)])
    print(f"ef_search={ef:3}  recall@10={r:.3f}  vectors visited={np.mean([v for _, v in results]) / N:.1%}")
Output
ef_search= 16  recall@10=0.971  vectors visited=0.6%
ef_search= 32  recall@10=0.982  vectors visited=0.9%
ef_search= 64  recall@10=0.993  vectors visited=1.3%
ef_search=128  recall@10=0.995  vectors visited=1.8%

High recall while visiting only about 1% of the vectors, controlled by ef_search (how many candidates to keep while searching). Real HNSW builds its upper layers as proper graphs instead of a random sample, and typically gives the best recall per millisecond of any index.

HNSW parameter Effect of increasing it
M (links per node) better recall, more memory, slower builds
ef_construction better graph quality, slower builds
ef_search better recall, slower queries — tune this one at query time

HNSW's costs: the graph lives in memory, builds are slow for very large datasets, and deletes leave holes that need periodic rebuilding.

3.4 IVF vs HNSW vs exact

Exact (flat) IVF HNSW
Recall 100% tunable (nprobe) tunable (ef_search), usually higher at the same speed
Speed slow at scale fast fastest for most workloads
Memory vectors only vectors + centroids vectors + graph (more)
Build none k-means training slower, incremental
Good for < ~100k vectors, or re-scoring a short list very large collections, with compression (IVF-PQ) the default for most RAG workloads

3.5 Quantisation: smaller vectors

Storing vectors with fewer bits shrinks memory and speeds up distance maths:

def int8_quantise(v):
    scale = np.abs(v).max(axis=1, keepdims=True) / 127
    return np.round(v / scale).astype(np.int8), scale

X8, s8 = int8_quantise(X)
Xb = np.packbits(X > 0, axis=1)                         # binary: 1 bit per dimension (sign only)

def int8_search(q, k=10):
    scores = (X8.astype(np.float32) * s8) @ q
    return np.argsort(-scores)[:k]

def binary_search(q, k=10, rescore=0):
    qb = np.packbits(q > 0)
    hamming = np.unpackbits(Xb ^ qb, axis=1).sum(axis=1)  # count differing bits
    if not rescore:
        return np.argsort(hamming)[:k]
    shortlist = np.argsort(hamming)[:rescore]             # cheap first pass…
    return shortlist[np.argsort(-(X[shortlist] @ q))[:k]] # …then exact re-scoring of a short list

print(f"float32 {X.nbytes / 1e6:.2f} MB | int8 {X8.nbytes / 1e6:.2f} MB | binary {Xb.nbytes / 1e6:.2f} MB")
print("int8 recall@10:                  ", round(recall(int8_search), 3))
print("binary recall@10:                ", round(recall(binary_search), 3))
print("binary + re-score top 100 recall:", round(recall(lambda q, k: binary_search(q, k, rescore=100)), 3))
print("binary + re-score top 200 recall:", round(recall(lambda q, k: binary_search(q, k, rescore=200)), 3))
Output
float32 5.12 MB | int8 1.28 MB | binary 0.16 MB
int8 recall@10:                   0.977
binary recall@10:                 0.262
binary + re-score top 100 recall: 0.784
binary + re-score top 200 recall: 0.916
  • int8 (scalar quantisation): 4× smaller for a small recall loss — an easy win.
  • Binary: 32× smaller and very fast, but crude on its own; with re-scoring of a short list it recovers most of the recall. Works best with high-dimensional embeddings (1,024+), where the sign pattern carries more information.
  • Product quantisation (PQ) splits each vector into sub-vectors and replaces each with the ID of its nearest "codeword" — 8–64× compression, used with IVF (IVF-PQ) for billion-scale collections.

3.6 Tuning in practice

  1. Build an eval set of queries with exact top-k answers (from flat search, as above).
  2. Pick the target recall — 0.95–0.99 is typical for RAG; the reranker and LLM tolerate a missed 10th result.
  3. Increase ef_search / nprobe until you hit it; measure p95 latency at that setting.
  4. Re-check after large data changes — the right setting drifts as the collection grows.

Index recall is rarely your bottleneck

At 0.98 index recall, almost all retrieval failures in a RAG app come from chunking, the embedding model, or the query — not the ANN index. Measure end-to-end retrieval on real questions before tuning index parameters.

Interview questions

What is ANN search and why is it needed?

Approximate nearest-neighbour search finds most of the true nearest vectors while examining only a small fraction of the collection. Exact search is linear in collection size and too slow at millions of vectors; ANN indexes (HNSW, IVF) trade a small, tunable loss of recall for orders-of-magnitude speedups.

Explain HNSW.

A multi-layer proximity graph: each vector links to its nearest neighbours; upper layers are sparse for long jumps, the bottom layer has every vector. Search descends greedily from the top, keeping a candidate list of size ef_search. M and ef_construction control graph quality and memory; ef_search trades recall for latency.

IVF vs HNSW?

IVF clusters vectors and searches only the nearest clusters (nprobe); it's memory-efficient and pairs well with PQ compression for huge datasets. HNSW navigates a graph; it usually gives better recall per unit latency but uses more memory and is slower to build.

What is vector quantisation?

Storing vectors in fewer bits: int8 scalar quantisation (4×, minimal loss), binary (32×, needs re-scoring), product quantisation (8–64×, used with IVF). It cuts memory and speeds up distance computations; re-scoring a shortlist with full-precision vectors recovers accuracy.

Practice

  • Change N_LISTS to 25 and 400. How do recall and "vectors scanned" change at nprobe=4?
  • Re-score the top 200 instead of 100 in binary search. Where does recall level off?

Next: Vector databases — what a database adds on top of an index.