Vector search and indexes

Nearest neighbours, again

A query embedding $\mathbf{q}$ and $N$ document vectors $\mathbf{d}_i \in \mathbb{R}^d$: find the $k$ largest $\mathbf{q}\cdot\mathbf{d}_i$. This is $k$-nearest neighbours (3.4 k-Nearest Neighbors) in embedding space. Exact (brute-force, "flat") search costs $Nd$ multiply-adds: for $N = 10^6$ and $d = 1{,}024$ that is about $10^9$ operations — roughly a millisecond on a GPU and tens of milliseconds on a CPU with a good BLAS library — and it is 100% accurate. Flat search is the right choice more often than people think: up to a few million vectors, or whenever recall must be perfect. Beyond that, memory bandwidth and latency force approximate nearest neighbour (ANN) search, which gives up a little recall for orders of magnitude in speed or memory.

Two families dominate: partition-based methods (IVF, with product quantization for compression) and graph-based methods (HNSW).

Inverted file index (IVF)

Run $k$-means (3.11 Clustering: k-means, GMMs/EM, DBSCAN and hierarchical) on the vectors with nlist centroids (typically between $\sqrt{N}$ and $4\sqrt{N}$). Each vector is stored in the list of its nearest centroid. At query time, compare $\mathbf{q}$ with the nlist centroids, pick the nprobe closest cells, and scan only the vectors in those cells:

With $N=10^6$, nlist $= 4{,}096$ and nprobe $= 32$: about $4{,}096\,d + 32 \cdot 244\,d \approx 12{,}000\,d$ instead of $10^6\,d$ — an 80× speed-up. Recall drops when the true neighbour sits in a cell you did not probe (common near cell boundaries); raising nprobe trades speed back for recall.

Product quantization: the memory math

IVF speeds up search but still stores full vectors. Product quantization (PQ) compresses them. Split each $d$-dimensional vector into $m$ sub-vectors of $d/m$ dimensions. For each sub-space learn a codebook of $256$ centroids with $k$-means. Encode a vector as $m$ centroid ids, one byte each:

For $d = 1{,}024$ and $m = 64$: 4,096 bytes become 64 bytes, a 64× reduction; a billion vectors fit in 64 GB instead of 4 TB. Distances are computed asymmetrically: for a query, precompute a table of $m \times 256$ distances between each query sub-vector and each centroid; the distance to any stored vector is then the sum of $m$ table lookups, with no multiplications per candidate. The price is quantization error, which lowers recall. IVF-PQ, with a final re-scoring of the top candidates using a few full-precision vectors, is how FAISS scales to billions of vectors on GPUs.

HNSW: a navigable graph

Hierarchical Navigable Small World graphs build a multi-layer proximity graph. Every vector is a node in the bottom layer, linked to about $M$ near neighbours (up to $2M$ at layer 0 in common implementations); a geometrically shrinking subset of nodes also appears in higher layers, which act like the express lanes of a skip list. Search starts at the top layer from an entry point, greedily hops to the neighbour closest to $\mathbf{q}$, drops down a layer when it cannot improve, and in the bottom layer runs a best-first search that keeps a candidate list of size efSearch. The number of hops grows like $\log N$ and each hop costs a handful of distance computations, so queries take well under a millisecond to a few milliseconds at millions of vectors, with recall above 95% when tuned.

Three knobs:

• M (links per node): higher means better recall and more memory — roughly $2M \times 4$ bytes of neighbour ids per vector at the base layer, on top of the vector itself. Typical values are 16–64.
• efConstruction: candidate-list size while building; higher gives a better graph and a slower build (hundreds is typical).
• efSearch (must be at least $k$): candidate-list size at query time; the live recall-versus-latency dial.

HNSW's weaknesses are memory (vectors and graph live in RAM, although PQ-compressed and disk-based variants exist) and slow, allocation-heavy builds; deletes are usually tombstones that require periodic rebuilds.

Choosing an index

Vector databases versus a table in Postgres

A vector database wraps an index with persistence, metadata filtering, hybrid (lexical plus dense) search, replication, multi-tenancy and an API. The options fall into three groups: libraries you embed in your process (FAISS, hnswlib, Annoy, usearch); extensions to databases you already run (pgvector for Postgres with HNSW and IVF-Flat indexes; OpenSearch and Elasticsearch with kNN next to BM25); and dedicated engines or managed services (Qdrant, Weaviate, Milvus, Chroma, Pinecone and others).

Honest guidance: below a few million vectors, a Postgres table with pgvector is usually enough and gives you transactions, joins with your real data and one backup story. Dedicated engines earn their complexity when you need tens of millions of vectors, high query rates, rich filtered search or multi-tenant isolation.

Filtering, hybrid search and updates

Metadata filters ("only documents this user may read, from 2025, in English") interact badly with ANN: post-filtering the top-$k$ can return nothing when the filter is selective, and pre-filtering destroys HNSW's graph connectivity. Engines solve this with filter-aware graph traversal, payload indexes, or by switching to flat search inside small filtered subsets — check how yours does it, because access-control filters are a security boundary (9.9 Production: latency, cost, caching, guardrails, security and privacy). Hybrid search keeps a BM25 index next to the vectors and fuses the results (9.5 Retrieval quality: hybrid search, reranking, query transforms and metrics). Updates: new documents are inserted (HNSW handles inserts well), changed documents are re-embedded, deleted documents are tombstoned and compacted; a change of embedding model means re-embedding everything, so record the model version with every vector.

Intuition. An ANN index is a map with highways. IVF draws districts and searches a few of them; PQ shrinks the map by rounding addresses; HNSW builds roads between neighbours and express lanes between regions.

Where this shows up later

• What goes into the index comes from chunking — 9.4 Chunking and ingestion; how you query it (hybrid, reranking) is 9.5 Retrieval quality: hybrid search, reranking, query transforms and metrics.
• Filtering by permissions is a production security control — 9.9 Production: latency, cost, caching, guardrails, security and privacy; the same indexes back agent memory — 10.4 Memory and context engineering.
• Vector search is k-NN (3.4 k-Nearest Neighbors) built on k-means (3.11 Clustering: k-means, GMMs/EM, DBSCAN and hierarchical) and the geometry of 1.1 Vectors, dot products and norms.