ANN Recall and the HNSW Graph

Your vector index does not return the nearest chunks. It returns the chunks a greedy graph walk happened to reach before it ran out of budget, and when the closest chunk in your corpus is not one of them, nothing anywhere says so. The query succeeds. It returns ten rows. Four of them are the wrong four.

This is not a bug and it is not a tuning failure. It is what the letter A in ANN means. Approximate nearest neighbour search is the deal every production vector index makes: it will look at a small fraction of your vectors instead of all of them, and in exchange it gives up the guarantee that what it found is what you asked for. Recall — the fraction of the true k nearest chunks that actually came back — is the name of the part it gave up. At pgvector's shipped defaults that fraction is not 1.0, and there is no field in the response that tells you what it was.

The structure doing the walking is HNSW, Hierarchical Navigable Small World: a graph in which every chunk is a node linked to roughly its M nearest neighbours, stacked into layers so that the top layer is a sparse sketch of the whole corpus and the bottom layer holds everything. A search enters at one node in the top layer, walks downhill toward the query, drops a layer, walks downhill again, and finishes at the bottom with a candidate list of size ef. Two numbers decide everything: M, fixed when the index was built, and ef, chosen per query. pgvector calls the second one hnsw.ef_search and defaults it to 40. FAISS calls it efSearch and defaults it to 16.

Below is that graph, built for real from the algorithms in the HNSW paper over 300 synthetic vectors. Every number in it is measured, including the ground truth: the panel also computes the exact nearest neighbours by brute-force comparison against all 300, so recall is a real comparison and not an estimate. Start by dragging ef_search from 10 down to 1, and watch rows returned — not recall — first.

At ef_search = 1 the query asked for 10 rows and got 1. Not one relevant row out of ten — one row, total. The candidate list is the result set, so a database asked for LIMIT 10 hands back a single row and reports no error. This is documented behaviour, and it is the single most common way people first notice that their index is approximate. pgvector's own FAQ has an entry titled "Why are there less results for a query after adding an HNSW index?", and the answer is one sentence: "Results are limited by the size of the dynamic candidate list (hnsw.ef_search), which is 40 by default."

Now put ef_search back to 10 and read the hero number: 0.900. Nine of every ten chunks that should have come back did. The tenth did not, and the tenth is not a random tenth. Look at query 10 in the first panel: the chunk missing from its results is the single closest vector in the entire corpus — true rank 1, and the walk never visited it. The query returned ten rows, all plausible, all genuinely nearby, and the best one silently absent. Every stage after this point — fusion, a cross-encoder reranker, the prompt, the model — is operating on a candidate set that already lost the answer.

That is the whole lesson in one number, and it is why this page sits before the ranking ones rather than after them. A reranker reorders a list. It cannot conjure a row the index did not return.

Why the walk stops while the answer is still out there

The termination rule is three lines of the paper's algorithm 2, and it explains every recall number on this page. The search keeps two collections: C, the candidates it still intends to visit, and W, the best ef nodes it has found. On each step it takes the nearest candidate from C, and:

if distance(nearest candidate, q) > distance(furthest kept result, q)
    break — "all elements in W are evaluated"

So the walk halts as soon as the closest thing left to explore is worse than the worst thing already held. That is a sensible local rule and it is not a global one. It stops at a point where no neighbour of anything visited looks promising — which says nothing about the chunk sitting three hops away through a node the walk never had a reason to enter.

This gives recall loss exactly two causes, and the first panel labels every missing row with which one it was.

• Evicted. The walk found the chunk, put it in W, and later threw it out because W was full at ef and something closer arrived. Raising ef fixes this directly and cheaply. In the default configuration this is rare: drop ef to 4 and query 10 shows one evicted row against five that were never seen.
• Never visited. The chunk was never a neighbour of any node the walk touched, so it was never even measured. Raising ef fixes this only indirectly — a larger W keeps more mediocre candidates alive, each of which contributes its own neighbours, so the explored region grows. This is the dominant cause, and it is why recall improves so much more slowly than ef grows.

Watch the cost column while you do it. At ef = 10 the search compares the query against 79 of the 300 vectors. At ef = 20 recall reaches 0.992 and the count is 99. At ef = 64 recall is 1.000 and it is comparing against 204 of 300 — the index is now reading 68% of the corpus to avoid reading 100% of it. Perfect recall from an approximate index costs about as much as not having the index. That is the trade in its final form, and there is no setting that escapes it; there is only a place on the curve you have chosen, knowingly or otherwise.

One more structural fact worth having in mind. Open the layers readout: 264 of the 300 nodes exist only in layer 0, 34 reach layer 1, and 2 reach layer 2. That distribution is not tuned — it falls out of l = floor(-ln(unif(0,1)) · mL) with mL = 1/ln(8) = 0.481. FAISS implements the same thing in set_default_probas, called with levelMult = 1.0 / log(M), and allocates M * 2 neighbour slots in layer 0 against M above it. The whole search begins at whichever single node happened to draw the highest level. There is one entry point, and every query starts there.

Dimension is why your test corpus lied to you

Set embedding dimensions to 2 and leave everything else alone: recall is 1.000. Set it to 384 — the width of all-MiniLM-L6-v2, still the most common embedding model in tutorials — and the same graph, the same M, the same ef gives 0.800. Nothing about the algorithm changed. Nothing about the corpus size changed.

The nearest ÷ 100th distance readout is the reason, and it is computed from the brute-force ground truth on every render. It divides the distance from the query to its true nearest chunk by the distance to its 100th nearest. In 2 dimensions that ratio is 0.140: the best match is seven times closer than the hundredth, so "walk downhill" is a strong instruction and any greedy method finds it. In 384 dimensions the ratio is 0.948. The best chunk in the corpus and the hundredth-best are within 5% of each other in distance.

A greedy walk is a hill-climbing algorithm, and hill-climbing needs a hill. When the true top 100 form a nearly flat plateau, every step the walk takes is a coin flip between candidates that differ in the fourth decimal place, and the termination rule fires while the walk is standing on a slightly wrong part of the plateau. Run the dimension selector upward and watch the ratio climb — 0.140, 0.587, 0.771, 0.856, 0.893, 0.924, 0.948 — while recall falls across the same range from 1.000 to 0.800. The ratio is monotonic and the recall is not: it reads 0.875 at 64 dimensions and 0.900 at 128, because twelve queries against 300 chunks is a small sample and the wobble is real sampling noise. The trend is the finding, not any single pair of numbers. This is the concentration of distances in high dimensions, measured rather than asserted.

The practical consequence is unpleasant. You prototyped on 500 documents with a small model, saw the retriever behave, and shipped. The property that made it behave was not the corpus size. It was that your distances were still spread out. Nothing in your test suite changes when that stops being true.

Where the build-time fix helps, and where it does not. Switch how build time picks each node's links to simple. Recall falls from 0.90 to 0.61 on the clustered corpus, because taking a node's M closest neighbours as its links means a node inside a tight topic cluster spends every link on its own cluster and keeps none pointing anywhere else. The walk arrives in a cluster and cannot leave. The paper's algorithm 4 fixes this by refusing to link a candidate that is closer to an already-chosen neighbour than it is to the node itself, which forces the links to fan out in different directions; the paper reports the same effect, saying the heuristic "significantly increases performance at high recall and in case of highly clustered data". Now untick clustered corpus and switch between the two rules again: on uniform data the difference nearly vanishes. This is a repair for a specific pathology, not a general win — and your corpus, split by topic into chunks that were written by the same team about the same product, is the clustered case.

The filter is applied after the walk, not during it

Set WHERE clause matches to 10%. Rows returned drops from 10 to 2, and at 5% it drops to 1 — without ef changing at all, and without recall changing at all, because recall is measured before the predicate runs.

The reason is an ordering that most people assume runs the other way. The graph knows nothing about your tenant_id, your language column or your published = true flag. It walks by distance alone, produces its ef candidates, and only then does the database throw away the ones that fail the predicate. pgvector states the arithmetic explicitly: "filtering is applied after the index is scanned. If a condition matches 10% of rows, with HNSW and the default hnsw.ef_search of 40, only 4 rows will match on average."

Four rows. Not four bad rows out of forty — four rows, returned to an application that asked for the top 20 and will now answer from whatever it got. This is the failure mode behind every "it works in dev and returns almost nothing in the multi-tenant staging environment" report, and the smaller the tenant, the worse it gets.

The fix in pgvector 0.8.0 and later is hnsw.iterative_scan, which keeps scanning more of the index until it has enough rows that pass the filter, bounded by hnsw.max_scan_tuples. It has two modes, and the difference matters: strict_order returns rows in exact distance order, while relaxed_order allows them to come back slightly out of order and, in the README's own words, "provides better recall". If you are reranking afterwards, relaxed order costs you nothing you were going to keep anyway.

Checking it on your own system

Index recall is measurable in about fifteen minutes and almost nobody measures it. You do not need a labelled dataset, because the ground truth is free: it is your own database with the index turned off.

In Postgres, run the same query twice — once forcing the exact scan, once normally — and intersect the two id lists. pgvector documents the mechanism under Monitoring, and it is two settings:

BEGIN;
SET LOCAL enable_indexscan = off;  -- exact search, the ground truth
SELECT id FROM items ORDER BY embedding <=> $1 LIMIT 10;
COMMIT;

Do that for 100 real queries taken from your logs, then run the same 100 with the index enabled, and compute the mean overlap. That single number is your index recall, and it is the ceiling on every retrieval metric you report downstream. If it is 0.85, then your recall@10 cannot exceed 0.85 no matter how good your embedding model is, and 15% of the effort you are about to spend on chunking strategy and similarity thresholds is being spent on the wrong layer of the stack.

Then set the two parameters deliberately rather than by default:

• ef_search must be at least k, and that is a floor, not a recommendation. FAISS ships efSearch = 16. Asking a freshly constructed FAISS HNSW index for 20 neighbours without touching it is asking for something it structurally cannot give you.
• Raise ef_search per query, not globally. In Postgres it is SET LOCAL hnsw.ef_search = 100 inside the transaction, so a user-facing autocomplete can stay at 40 while the retrieval path that feeds an LLM runs at 200. They have different recall requirements and wildly different latency budgets.
• M is a rebuild. pgvector defaults to m = 16 and ef_construction = 64; the paper says "a reasonable range of M is from 5 to 48", with larger M better for high recall and high dimensional data, and memory use proportional to M. You cannot change it with a SET, so decide it against the dimensionality you actually have.
• Re-measure after bulk updates. pgvector issue #244 is titled "HNSW + dead tuples: recall loss/usability issues" — deleted rows still occupy graph nodes, so recall on a heavily churned table is not the recall you measured on the day you built it.

And when you report a retrieval number to anyone, say which one it is. "Our retriever gets 0.85" is three different claims: the fraction of true neighbours the graph returned, the fraction of answer-bearing chunks in the top k, and the fraction of questions the system answered correctly. They are measured against three different ground truths and they fail for unrelated reasons. This page is only about the first one, and it is the one that is invisible from the application.