ANN recall (efSearch, nprobe)
The share of the true nearest neighbours an ANN index actually returns. Measured against exact search, not human relevance labels.
An Approximate nearest neighbour (ANN) index is approximate, so it sometimes misses vectors that are truly the closest. ANN recall@k measures how many of the true top-k (found by slow exact search) the index returned. If exact search finds 10 neighbours and the index returns 9 of them, ANN recall@10 is 0.9. This is different from Recall@k in RAG evaluation, which asks whether relevant documents were found.
Checking a fast cashier against a careful one: of the ten items the careful cashier rang up, how many did the fast one also scan?
Quoting a vendor benchmark's '99% recall' as your system's recall. It was measured on SIFT/GloVe-style datasets without filters at a specific ef. Your recall with filters, your dimensions and your data distribution can be 20+ points lower.
ANN recall@k = |ANN top-k ∩ exact top-k| / k, averaged over a query sample. It isolates index error from model error: end-to-end retrieval recall ≤ (model's exact-search recall) and ANN loss compounds on top of it. Measure with 1,000+ real queries (not random vectors — real queries cluster), run exact search with FAISS IndexFlatIP or a sequential scan (SET enable_indexscan = off in pgvector). Plot recall vs latency (QPS) for the knob you can turn: ef_search (HNSW), nprobe (IVF (inverted file index)), oversampling (Scalar & binary quantization). Recall varies by segment: small tenants under filters, new data after drift, and dense clusters (near-duplicates) often score 10–30 points below the average. ANN-Benchmarks (Aumüller et al.) standardised the recall–QPS frontier as the way to compare indexes; vendor benchmarks without the recall level are meaningless.
Nightly job: 1,000–2,000 sampled production queries, exact top-k via brute force, recall@10 reported overall and per segment (tenant size bucket, filter vs no filter, data age). Index-build CI fails below 0.95 recall@10.
Contract-clause search, 8M × 1024-d in Qdrant. 2,000 sampled production queries. Overall recall@10 0.97 at ef=128. Segmented: tenants with < 10k clauses under a tenant filter: 0.62; clauses added in the last 7 days: 0.91. Raising ef to 256 for filtered queries and creating a tenant_id payload index (so Qdrant builds filter-aware links) brings small tenants to 0.96 at +1.8 ms.
Separate the two recalls: "I report index recall vs exact search and retrieval recall vs labels separately, so I know whether to tune ef_search or change the model." Then talk segments: the average hides filtered small tenants. Expect: how often do you measure? Nightly on a sample plus as a gate on every index rebuild.
Numbers worth knowing
- Typical production target
- recall@10 ≥ 0.95with a reranker and fusion downstream
- Filtered small-segment gap
- 10–40 points below averageHNSW, filters selecting < 1% of vectors, no filter-aware index
- Audit sample
- 1,000 queries → about ±1 pt (95% CI)mean recall@10 ≈ 0.95; use 1,000 per segment you report
How to decide
| When | Do this |
|---|---|
| Exact search finds the answer but ANN doesn't | Tune ef_search/nprobe/oversampling — not the model. |
| Exact search also misses | The model or chunking is the problem; ANN tuning won't help. |
| Filtered segment recall < 0.9 | Payload/filter index, partition the tenant, or pre-filter with exact search for small segments. |
Cost maths
Measurement cost: 1,000 queries × exact scan of 10M × 768-d ≈ 7.7 TFLOP → ~2–3 minutes on 16 CPU cores, seconds on one GPU. Trivial compared with the cost of shipping an index at 0.7 recall.
Operating it
- Any segment's recall@10 < 0.9 — fix that segment before tuning the average
- Recall drops > 2 points week-over-week without config change — drift or tombstone build-up; rebuild
- Raising ef/nprobe no longer improves recall — rebuild with higher M or retrain IVF
- Recall@10 vs exact, per segment (filter, tenant size, data age) — alert below 0.9 for any segment
- Rows returned < k — alert above 1% of queries
- Deleted/tombstoned fraction of the index — alert above 20%
When it goes wrong
Enterprise tenants on a shared document-search platform said search 'forgets' recent uploads.
Recall audit segmented by document age: documents < 48 h old had recall@10 of 0.58.
New documents were written to a small mutable segment searched with brute force only up to a size threshold; above it, an unoptimised HNSW segment with heavy deletes served them.
Tuned the optimizer to build indexes on new segments sooner, triggered compaction after bulk deletes, and added data-age as a recall segment on the dashboard.
Related terms
Where it shows up
Sources
- ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms — Aumüller, Bernhardsson & Faithfull, 2018paper
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — Malkov & Yashunin, 2016paper
- ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data — Patel et al., 2024paper
Check yourself
Three questions. Every option is explained once you answer.