Articles

Vector indexes and retrieval: finding the nearest neighbours

A vector index buys speed by giving up exactness; knowing which one decides its limits.

Reading: 6 minAutomation & AI

Article cover: Vector indexes and retrieval: finding the nearest neighbours

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.

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

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.
Nodrius Field Kit — cover

Get the Nodrius Field Kit

Enter your email and we'll send you the complete Field Kit: eight technical resources in one download.

Your email address is sent to Nodrius and used to deliver the Field Kit to you by email. Marketing messages are separate and optional: the checkbox does not affect your download, and you are only added to our updates list if you tick it. Privacy Policy.

Privacy & cookies

This site does not use cookies, analytics or tracking, and it does not profile you. There is nothing technical to switch off, so Accept and Reject change nothing about how the site works: either choice lets you browse everything normally.

The only difference is what your browser remembers: two entries in local storage — your choice here, so this notice is not shown again, and a marker that the Field Kit offer has already been made — so the offer is presented once and not on every page. They contain no identifier, they are not shared with anyone, and the site sets no cookie for either.

What we do with your data
How your email address is used when you ask for a Resource, how long it is kept and which rights you have — in the Privacy Policy.
What the site stores in your browser
Two entries in local storage — your choice on this notice and whether the Field Kit offer has been shown — and no cookies, no session storage, no third-party content: in the Cookie Policy.