Vector indexes and retrieval: finding the nearest neighbours
A vector index buys speed by giving up exactness; knowing which one decides its limits.

A corpus of embeddings is a set of points in a space with thousands of dimensions. Comparing a query against all of them is a linear scan: honest, exact, and — at corpus scale — too slow. A vector index is the structure that replaces the scan with a search, and the trade it makes is the subject of this sheet: speed in exchange for exactness, with several different ways of spending that budget.
The family the indexes belong to
The structures used in practice are approximate nearest-neighbour search: they look for the vectors closest to the query without guaranteeing that they are the closest. The canonical graph approach is described as “a new approach for the approximate K-nearest neighbor search based on navigable small world” graphs organised into a hierarchy, a design whose purpose is efficient search with “logarithmic complexity scaling” — the property that makes retrieval on a large corpus affordable at all.
Two concrete index types, and how they differ
The relational vector extension used as the reference in these sheets documents two index types, and the difference between them is a good illustration of what an index decision actually trades:
- HNSW. “An HNSW index creates a multilayer graph. It has better query performance than IVFFlat (in terms of speed-recall tradeoff), but has slower build times and uses more memory.” The same documentation adds that such an index can be created before any data exists, because it has no training step of the kind the other type requires.
- IVFFlat. A partitioning approach whose structure depends on a training pass over a sample of the data, which is why it can be built faster and with less memory, and why its recall depends on how well that sample represented the corpus.
Neither is “better”. The decision is: how often does the corpus change (build cost), how much memory is available, and how much recall can be sacrificed for latency.
What the library scale looks like
At the scale where a single process is not enough, the reference library for similarity search is “a library for efficient similarity search and clustering of dense vectors” that “contains algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM”. Its documentation organises the choices around exactly the axes this sheet has been describing: exact versus approximate search, the compressed representations that trade quality for size, and — in its own list of considerations — “memory used per index vector”.
Recall is the parameter nobody measures
An approximate index has a quality setting: how hard it searches before returning its answer. The recall it achieves is a property of the index, the parameters and the data, and it is not visible from the outside. The consequence for a pipeline is uncomfortable:
- a query that returns nothing useful may be a retrieval failure (the right chunk was never indexed) or an index failure (the chunk is in the index and the search did not find it);
- the difference is only visible by measuring retrieval directly, which is why the evaluation sheets of this layer insist on a test set that includes queries whose answer is known to be present.
This is also why “we added a vector database and answers got better” is not evidence: the index is a performance component, and its effect on quality is measurable, not implied.
Filters change the shape of the search
A filter on the payload is not a post-processing step over the results: in the stores that implement it properly, filtering participates in the search, and its cost depends on whether the filtered fields are indexed — “for performant filtering, create payload indexes for the fields you plan to filter on. For best results, create payload indexes before ingesting data”. A highly selective filter can also make an approximate index less accurate, because fewer candidates survive the filter than the search assumed.
Where an index ends and retrieval begins
The index answers “which vectors are near this one”. Retrieval is the whole step: embedding the query, applying the filters, choosing how many candidates to take, and deciding what to do with them. The next sheet adds the second retrieval channel (lexical matching) and the sheet after it adds a reranking pass; the index is the component all of them sit on.
Level and prerequisites. L3 — integration level: the reader must be able to choose an index type for a corpus and to say what recall means in their deployment. No index is created, tuned or measured here. Prerequisites: the embeddings sheet of this layer (what is indexed) and the chunking sheet (what the vectors represent).
Where to go next
- Automation & AI — the macro-area this sheet belongs to.
- Applications — the node this sheet sits in.
References
- Malkov and Yashunin — Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — the approximate graph-search family and its logarithmic scaling.
- pgvector — README — the two index types, their trade-off in the project’s own words, and the filtering note.
- Faiss — README — the library scale, exact versus approximate indexes and the per-vector memory consideration.
- Qdrant — Filtering — payload indexes as the condition for performant filtering.