Low Vector Search Recall: Causes and Fixes

“Search results got worse” is the most common complaint against a vector database and the least useful bug report, because at least eight distinct faults produce it. Some are configuration, some are data, and one of them is not a recall problem at all. Working through them in order costs less than guessing.

First, measure recall instead of describing it

Before changing a parameter, establish what the number is. Recall for approximate search has an unambiguous definition: take a sample of real queries, compute the true nearest neighbours by exhaustive comparison against the same collection, then measure what fraction of those the index returned at the same k. That is the methodology standard benchmarks use, and it is the only measurement that makes two configurations comparable.

Practical notes on doing it:

• Use production queries, not synthetic ones. Query distribution drives which part of the graph or which lists get touched.
• A few hundred to a few thousand queries is usually enough to see a change of a few percent.
• Compute ground truth against the same snapshot the index was built from. A collection that received writes in between will produce false misses.
• Record recall and latency together, always. A latency number without its recall is not evidence of anything.

Without this, every fix below is unverifiable, and the usual outcome is that someone raises a parameter, the numbers feel better, and the real fault is still there.

The search effort parameter is too low

This is the first thing to check and the most common single cause.

A graph index walks the structure keeping a candidate list, and the size of that list is a query-time parameter, commonly ef or ef_search. Larger list, higher recall, higher latency, no rebuild required. There is a hard constraint the reference implementation states directly: this value cannot be set lower than the number of neighbours requested. Ask for 50 results with a candidate list of 40 and the index cannot possibly do well, and the engine will not necessarily complain.

The same shape applies to inverted-file indexes with nprobe, the number of clusters a query examines. The default is often 1, which examines a single partition and misses any true neighbour that landed just across a boundary. Boundary effects are exactly where approximate search loses recall, so a default of 1 is a floor, not a recommendation.

Fix: sweep the parameter across a range, plot recall against latency, and pick the point that meets the requirement. This is a per-query setting in most engines, so expensive queries and cheap queries can be served from the same index at different settings.

The distance metric does not match the model

Cosine similarity, inner product and Euclidean distance are different functions and are not interchangeable. The correct one is whatever the embedding model was trained against.

Two variants of this fault:

• Wrong metric selected at index creation. Results still come back, ranked plausibly, and are subtly wrong for every query. There is no error to catch.
• Normalization applied inconsistently. Cosine on vectors that were never normalized, or inner product on vectors that were normalized only at index time, both produce rankings that look reasonable and score badly.

Fix: confirm the metric from the model documentation, confirm what the collection was created with, and confirm normalization happens in the same place for documents and queries. This one is worth checking early because it is cheap to check and expensive to miss.

Query-time embedding differs from index-time embedding

The index stores what the encoder produced when the data was ingested. If anything about that encoder changes, the query lands in a slightly different space and the neighbours are wrong even though the index is healthy.

Common causes: a model version bumped on one side only, a different pooling strategy, a truncation length that silently cuts long inputs, or an embedding family that expects an instruction prefix which differs between documents and queries. That last one produces a specific signature, plausible but consistently mediocre results, and it is easy to introduce when the ingest path and the query path live in different services.

Fix: embed one known document through the query path and compare the vector against what is stored for it. They should match closely. If they do not, the encoder configurations have diverged, and re-indexing is the only repair.

Filters are removing results the index already committed to

Filtered search is where recall degrades most sharply and least visibly.

If the engine applies the filter after retrieval, the index returns its top candidates and the filter deletes some, so a request for 10 can return 3. If the engine applies the filter during traversal, result counts hold up but the search is constrained: a graph walk restricted to a rare subset can spend its whole candidate budget among neighbours that do not qualify. Engines handle this differently, and some build additional structures specifically so that highly selective filters remain searchable rather than falling back to a scan.

Fix: find out which behaviour your engine implements, then check whether the filter is selective enough to be the problem. Selective filters are usually better served by narrowing the search space up front, through a payload index the engine can use, or by partitioning into separate collections when the filter is a stable, low-cardinality property such as tenant or language.

Quantization is on and rescoring is not

Compressed vectors are lossy by construction. The standard mitigation is to retrieve a larger candidate set using the compressed representation and re-rank those candidates against higher-precision copies.

If compression was enabled without oversampling and rescoring, recall drops by an amount that depends on how aggressive the compression is. Binary quantization without rescoring is the extreme case and can be dramatic.

Fix: enable rescoring, and raise the oversampling factor until recall recovers. If it does not recover, the compression level is wrong for the data. Vector database memory sizing covers what each compression level actually saves, which is the other half of that decision.

The index is stale, tombstoned, or not there

Several failures share the symptom of “it used to be better”.

• Deletes leave tombstones. Graph indexes typically mark elements deleted rather than removing them. Heavy churn accumulates dead entries that degrade traversal until a compaction or rebuild runs.
• The index was never built, or was built on an empty table. Cluster-based indexes learn their centroids from the data present at build time. Built before the data landed, they partition on nothing useful.
• Distribution drift. Centroids trained on last quarter’s corpus can be a poor fit for this quarter’s. Graph indexes degrade more gracefully here, but not infinitely.

Fix: check when the index was last built, whether a compaction has run since the last large delete, and whether the corpus has changed character since training. For cluster indexes, retraining is periodic maintenance, not an incident response.

Result counts collapse across shards or segments

Distributed and segmented engines run the approximate search once per shard or segment and merge the results. If each unit returns only k candidates and the merge takes the global top k, recall depends on how the true neighbours are spread across units. Many small segments make this worse; consolidating them is standard tuning advice in engines built on segmented storage.

Fix: check the per-unit fan-out setting, and check segment counts after bulk ingestion. This is the fault that only appears in production, because the development environment has one segment.

Recall is fine and relevance is still bad

The last case is the one no parameter fixes. If the index is returning the true nearest neighbours and users still call the results wrong, the retrieval layer is healthy and the problem is upstream: chunks too large to be about one thing, chunks too small to carry context, a model that does not represent the domain vocabulary, or a query that is a question when the corpus is statements.

This is worth separating early, because it is entirely possible to spend a week tuning ef on an index that was already at 99 percent recall. Measure first for exactly this reason.

Diagnostic order

1. Measure recall against exact search. Get a number.
2. Check the search effort parameter against k.
3. Verify metric and normalization on both paths.
4. Compare a query-path embedding against the stored one.
5. Re-run without filters to isolate filter effects.
6. Check quantization and rescoring settings.
7. Check index age, tombstones and segment count.
8. If recall is high, stop tuning the index and look at chunking and model fit.

For background on why these knobs exist, see vector search fundamentals, and for choosing the index in the first place, HNSW vs IVF: vector index tradeoffs compared.