If you run a site search, a RAG assistant, or any internal tool built on embeddings, there is a failure mode that almost never gets diagnosed correctly: the retrieval layer silently skips documents that are genuinely among the closest matches to the query vector. Not ranked low — never scored at all.
The usual response is to blame the content. Someone rewrites the chunk, adds headings, restates the question in the first sentence. Sometimes that helps, because it changes the embedding. Often it doesn't, because the problem was never semantic. The index was approximate, and that document fell outside the part of the space the search actually visited.
What "approximate" means in an approximate nearest neighbor index
Exact nearest neighbor search compares the query vector against every stored vector. That is O(N) per query, which is fine for ten thousand chunks and unworkable for ten million. Every production vector store therefore uses an approximate index, and approximation is not a rounding error — it is a deliberate trade of recall for latency.
The three common families fail in different ways:
- Graph indexes (HNSW). Vectors become nodes in a navigable small-world graph. A query enters at a seed node and greedily walks toward closer neighbors, keeping a candidate list of size
ef_search. If the true nearest neighbor sits in a region the walk never reaches — because graph connectivity around it is poor, or becauseef_searchis small — it is simply not a candidate. Largeref_searchand higherM(edges per node) raise recall and raise latency and memory. - Inverted file indexes (IVF). The space is partitioned into
nlistclusters by centroid. A query probes only thenprobenearest clusters. Vectors that sit just across a cluster boundary from the query are invisible unlessnprobeis large enough to include their cell. Boundary losses are systematic, not random. - Quantization (PQ, SQ, binary). Vectors are compressed, so distances are computed on approximations. This rarely loses the top match outright but reorders near-ties constantly — which matters a lot when you pass the top 20 to a reranker and the real answer was number 23.
Most systems stack these: HNSW over PQ-compressed vectors, or IVF-PQ with a reranking pass over full-precision vectors. Each layer compounds the loss.
How to measure recall instead of assuming it
You cannot reason about this without a ground truth. The measurement is cheap because you only need a sample.
- Sample 200–1,000 real queries from your logs, weighted toward the ones that matter.
- For each, compute exact top-k by brute force over the full vector set. On a sample this is a single matrix multiply; it does not need to be fast.
- Run the same queries through your production index at the same k.
- Compute
recall@k = |ANN_topk ∩ exact_topk| / k.
import numpy as np
exact = (Q @ V.T).argsort(axis=1)[:, ::-1][:, :k] # cosine, normalized vectors
hits = [len(set(a) & set(e)) for a, e in zip(ann_results, exact)]
print("recall@%d = %.3f" % (k, np.mean(hits) / k))
Report recall at the k your pipeline actually consumes, not at k=1. If a cross-encoder reranks your top 50, recall@50 is the number that bounds your quality — the reranker cannot recover a document retrieval never surfaced. And report the distribution, not just the mean. A system averaging 0.95 recall with a tail of queries at 0.4 is a system with a broken query class you haven't identified yet.
| Index type | Main knob | What gets lost | Cost of fixing it |
|---|---|---|---|
| HNSW | ef_search, M | Nodes in poorly connected graph regions | Latency, index memory |
| IVF | nprobe, nlist | Vectors just across cluster boundaries | Latency, linear in nprobe |
| PQ / quantization | Code size, rerank depth | Correct ordering among near-ties | Memory, extra full-precision pass |
| Filtered search | Pre- vs post-filter | Everything outside the first k candidates | Depends on engine support |
Metadata filters are where recall actually dies
Add WHERE language = 'de' AND product_line = 'enterprise' to a vector query and the arithmetic changes completely.
With post-filtering, the engine retrieves k candidates by vector distance and then discards those failing the predicate. If the filter matches 1% of the corpus and you retrieved 50 candidates, you expect roughly zero survivors. You get a short or empty result set for a query that has hundreds of valid answers.
With naive pre-filtering on a graph index, the engine restricts the walk to matching nodes — but the graph was built over all vectors, so removing most nodes shreds connectivity and the traversal gets stranded in a local pocket. Good engines handle this by switching to brute force below a selectivity threshold, or by building per-partition indexes. Many do not, and few document the crossover point.
The practical consequence: measure recall per filter selectivity bucket. Unfiltered recall tells you nothing about recall on a 2%-selective facet, and the filtered queries are usually the high-intent ones.
Index maintenance quietly degrades what you measured last quarter
Two drift mechanisms that recall tests catch and nothing else does:
- Deletes as tombstones. Most graph indexes mark vectors deleted rather than removing them, because removal would break edges. Tombstones still consume candidate slots during traversal, so effective
ef_searchshrinks as churn accumulates. High-churn corpora need scheduled rebuilds. - Mixed embedding generations. Re-embedding with a new model is usually a backfill job. Until it completes, the index holds vectors from two models in the same space, and cross-model distances are meaningless. Partial backfills produce retrieval that is not merely worse but incoherent — and average recall against a single-model ground truth will look bizarre rather than simply low.
Why this looks like a content problem
When a chunk never appears in retrieved context, the symptom is an assistant that says it doesn't know, or a site search returning nothing for a question your documentation answers in full. That presents as a content gap. Teams respond by rewriting.
The diagnostic that separates the two causes takes an afternoon: run the failing query through exact brute-force search. If the missing chunk appears in the exact top-k and not in the production top-k, it is a retrieval configuration problem and no amount of rewriting will reliably fix it. If it is absent from the exact results too, then the embedding genuinely doesn't place that text near that query, and the content or chunking work is justified.
A note on scope: Google has not documented the ANN configuration behind its retrieval systems, and nobody outside should claim to know it. The reasonable inference is only that web-scale candidate generation is approximate by necessity, which means "semantically similar" and "actually retrieved" are different properties everywhere, not just in your stack. Treat that as a reason to be humble about similarity-based audits, not as a specific claim about Google's recall.
What to do
- Build a 200–1,000 query ground-truth set with brute-force exact search. Store it in version control; it is now a regression test.
- Measure recall@k at your pipeline's real k, and report the 10th percentile alongside the mean.
- Re-measure separately for filtered queries, bucketed by filter selectivity. Find your engine's pre-filter crossover point empirically.
- Tune
ef_searchornprobeupward until recall stops improving, then back off to your latency budget. Record both numbers so the trade is explicit rather than accidental. - Re-run the suite after every index rebuild, embedding model change, or chunking change — and after any significant delete volume.
- Before rewriting content that "doesn't get retrieved," check it against exact search first.