Approximate nearest neighbour search with an IVF index: interactive recall vs speed

Semantic search, recommendations and retrieval for LLMs all turn items into embedding vectors and look for the vectors nearest to a query. Comparing the query with every vector is exact but slow at millions of items, so vector databases use approximate nearest neighbour (ANN) indexes that look at a small part of the data and accept missing a few true neighbours. The IVF index, an inverted file of clusters, is the simplest of them.

The playground clusters 600 vectors, drawn in two dimensions, and searches for the 10 nearest to a query. Click to move the query, and change how many lists the index has and how many it probes.

How an IVF index works

Building the index runs k-means to find centroids and files every vector in the list of its nearest centroid. A query is compared with the centroids, then with the vectors in the nprobe nearest lists only. With 16 lists and one probe, a query in the middle of a cluster finds all 10 true neighbours after 64 comparisons instead of 600. A query near a border is the weak spot: its nearest neighbours lie partly in the next cell, and probing one list finds just 1 of 10. Probing 2 lists recovers all 10 for 77 comparisons.

• More probes raise recall and cost, roughly in proportion.
• More lists make each list smaller, so each probe is cheaper, but more queries sit near a border; pair more lists with more probes.
• Starting points from pgvector’s documentation: rows / 1,000 lists up to a million rows and the square root of the rows beyond that, with probes around the square root of the lists, then measure.

At scale the savings are large: 100 million vectors in 10,000 lists, probing 100, compares a query with 10,000 centroids and about a million vectors, 1% of the data.

IVF, HNSW and quantization

HNSW, a layered graph in which each vector links to its near neighbours, usually reaches higher recall at lower latency and handles inserts without retraining, at the cost of more memory and slower builds; it is the default in many vector databases. IVF builds fast and stays compact, and combined with product quantization, which compresses each vector to a few bytes, IVF-PQ is how billions of vectors fit in memory. Whatever the index, measure recall by comparing its results with exact search on a sample of real queries.

An IVF index in PostgreSQL with pgvector

CREATE EXTENSION vector;
CREATE TABLE docs (id bigserial PRIMARY KEY, body text, embedding vector(1536));

-- an IVF index: k-means runs when it is built, so build it after loading data
CREATE INDEX ON docs USING ivfflat (embedding vector_cosine_ops) WITH (lists = 1000);

SET ivfflat.probes = 32;          -- more probes: higher recall, slower queries
SELECT id, body FROM docs ORDER BY embedding <=> $1 LIMIT 10;

In a system design interview

When a design retrieves by meaning, say how and at what accuracy: “Documents are chunked and embedded, and the 20 million chunk vectors live in an IVF index with about 4,500 lists. We probe 64, which gave 95% recall@10 against exact search on a sample of logged queries, at about 20 ms. Filters such as tenant are applied inside the index scan, not after, so a small tenant still gets 10 results.” Expect the follow-ups: how the index is rebuilt as data drifts, HNSW versus IVF, and combining vector search with keyword search.

Read the guide to ANN indexes or vector search and RAG, compare the inverted index behind keyword search, or watch a strong candidate design an LLM inference service.

Questions people ask