Vector databases
Finding the nearest neighbour among millions of vectors without comparing them all: HNSW, IVF, and the trade-off between recall and latency.
The idea
An embedding turns text into a point in space. Similar texts sit close together. A vector database is the filing cabinet for that: it answers "which ten points are closest to this one?" in milliseconds instead of minutes.
What it is good for
- Making your own documents searchable without exact keywords.
- Finding similar cases, articles or images.
- The basis for RAG, that is answers grounded in your own sources.
- Detecting duplicates.
The methods
| Method | Build | Search | Memory | Used for |
|---|---|---|---|---|
| Exact (flat) | none | O(n·d) | vectors | up to ~100,000 |
| IVF | clustering | O(n/k · d) | vectors plus centroids | millions, fast build |
| HNSW | graph | O(log n) | vectors plus edges, high | Best latency |
| IVF-PQ | clustering plus compression | fast | heavily reduced | Very large collections |
# Without a dedicated database: pgvector in Postgres
# CREATE EXTENSION vector;
# CREATE TABLE doc (id bigserial, text text, e vector(768));
# CREATE INDEX ON doc USING hnsw (e vector_cosine_ops)
# WITH (m = 16, ef_construction = 64);
#
# SELECT id, text, 1 - (e <=> $1) AS similarity
# FROM doc ORDER BY e <=> $1 LIMIT 10;
#
# <=> is the cosine distance. The index engages only when the ORDER BY
# uses the same operator as the index definition.- Normalise vectors before insertion when searching by cosine.
- Treat the
ef_searchparameter as the dial between recall and latency. - Measure recall against an exact search on a sample rather than estimating it.
- Filter metadata inside the search, not afterwards; otherwise too few results come back.
The trade-off
Typical measurements for HNSW on a million 768-dimensional vectors:
ef_search | Recall@10 | Latency per query |
|---|---|---|
| 16 | 0.84 | 0.4 ms |
| 64 | 0.96 | 1.1 ms |
| 128 | 0.985 | 2.0 ms |
| 512 | 0.999 | 7.5 ms |
| exact | 1.000 | ~380 ms |
The last row shows the gain: a factor of 190 for 1.5 percent of hits lost.
Memory, worked through
For n = 10⁷, d = 768, b = 4, M = 16: vectors 30.7 GB, graph 2.6 GB,
together about 33 GB. In float16 it would be 18 GB; with product quantisation
to 96 bytes per vector only 3.6 GB, at a recall around 0.9.
Hybrid search
Pure vector search fails on proper nouns, case numbers and figures. The usual answer is combining it with BM25 and fusing the results:
The advantage over a weighted sum of scores: ranks are comparable across the two methods, raw scores are not. In evaluations the combination regularly improves recall@10 over pure vector search by 5 to 15 points. See RAG in depth.
Deletion and data subject rights
An erasure request under Art. 17 GDPR reaches the index too. Two points are awkward in practice:
- A vector marked deleted stays in the graph until the index is rebuilt. A rebuild cycle therefore belongs in the record of processing activities.
- An embedding partially reconstructs its source text. It is therefore pseudonymised data, not anonymised.
Related courses and sources
Efficient Estimation of Word Representations
The paper that first established words as vectors with computable meaning. The origin of all embeddings.
The origin of all embeddings; short and still illuminating.
LangChain documentation
Building blocks for retrieval, tool calls and agents. Useful as a catalogue of the patterns, even if you end up building without the framework.
Useful as a catalogue of patterns, even if you end up building without the framework.