Recall@K

Recall@K = |Retrieved True Neighbors ∩ Top-K Results| / |All True Neighbors|

• K is the number of results returned to the user or downstream system
• True Neighbors are the ground-truth results from an exact brute-force search
• A score of 1.0 means perfect recall—all true neighbors were found
• A score of 0.8 at K=10 means 2 out of 10 true neighbors were missed

Approximate Nearest Neighbor algorithms trade accuracy for speed. Recall@K quantifies this tradeoff directly.

• Without Recall@K, you cannot objectively compare HNSW vs. IVF vs. DiskANN
• A 10x speedup is worthless if Recall@10 drops from 0.99 to 0.65
• Production systems typically target Recall@10 > 0.95 for semantic search
• The metric exposes regression bugs when re-indexing or tuning hyperparameters

The fundamental engineering tension in vector search:

• Higher recall requires searching more graph edges or Voronoi cells
• Lower latency requires aggressive pruning and smaller search scopes
• Typical tuning parameters that affect this balance:
  • ef_search in HNSW: larger values increase recall but slow search
  • nprobe in IVF: more probes increase recall linearly with compute
• Plotting a recall-latency curve is standard practice for index selection

Recall@K is highly sensitive to the choice of K:

• Recall@1: Measures whether the single most relevant item was found. Critical for question-answering systems.
• Recall@10: Standard benchmark for search result pages. Balances precision and recall.
• Recall@100: Used for re-ranking pipelines where a coarse filter feeds a precise downstream model.
• Recall@1000: Relevant for exhaustive retrieval tasks like e-discovery or deduplication.

Always report Recall@K at multiple K values to fully characterize an index.

Computing Recall@K requires exact nearest neighbors as ground truth:

• Run brute-force k-NN search over the entire dataset using the same distance metric
• For billion-scale datasets, this is computationally prohibitive
• Sampling strategies: evaluate recall on a representative query subset
• Approximate ground truth: use a highly-accurate but slow ANN config (e.g., HNSW with very high ef_search) as a proxy
• Mismatched distance metrics between ground truth and ANN index invalidate the measurement

Avoid these errors when measuring Recall@K:

• Ignoring tied distances: vectors at identical distances can cause non-deterministic ordering, inflating or deflating recall
• Measuring on training queries: always use a held-out query set to avoid overfitting
• Single K reporting: Recall@10 alone hides poor Recall@1 performance
• Ignoring filtered ANN: recall with metadata filters is a distinct, harder problem requiring separate measurement
• Confusing Recall@K with Precision@K: recall measures completeness; precision measures relevance ratio