Accuracy-Latency Trade-offs in Vector Search: Recall@K, HNSW, IVF and PQ

There is no useful universal objective called "the fastest vector index" or "the most accurate ANN algorithm." Approximate nearest-neighbor systems trade accuracy against latency, throughput, memory and index-build cost. Improving one axis frequently makes another more expensive.

Start from an exact baseline

Before evaluating an approximate method, compute exact nearest neighbors on a manageable or sampled dataset. That baseline reveals how many target neighbors the ANN result recovers. Recall@K is a primary metric for this comparison.

If nine of the exact top ten neighbors appear in the ANN top ten, recall for that query is 0.9. Real evaluation requires many queries and a representative distribution; a few easy queries can make an index look better than it is.

HNSW: search width and memory

HNSW is graph based. Denser connectivity or broader exploration can improve recall while consuming more memory and query time. Query-time parameters such as efSearch are direct accuracy/latency controls.

Mean latency alone is insufficient because traversal work can vary across queries and data regions. P95/P99 should be reported as well.

IVF: candidate-set size

An inverted-file index assigns vectors to coarse centroids and searches only selected lists. Probing more lists can improve recall while increasing candidate count and memory-access cost. In FAISS, nprobe is a typical control for this trade-off.

A small nprobe can minimize latency but lose neighbors; a large value can approach exact-search cost. The useful operating point depends on dataset size, dimensionality and distribution.

Product Quantization and memory

Product Quantization represents vectors with compact codes, reducing memory and sometimes scan cost at the price of quantization error. For a large collection, fitting more candidates in memory can improve the system even while each vector is less precise.

PQ should therefore be evaluated with recall, query latency, training/build time and rebuild cost rather than index size alone.

System-level cost

Index search is only one component of end-to-end retrieval latency. Embedding generation, network transfer, metadata filtering, candidate materialization and reranking add their own cost. In a dense retrieval pipeline, an extremely fast ANN stage can still be followed by a cross-encoder that determines overall P99.

Metadata filters can also change the optimum index setting by shrinking the candidate space. A benchmark without production filters may therefore select the wrong operating point.

Evaluation matrix

A useful benchmark reports at least:

Recall@K
P50 / P95 / P99 query latency
queries per second
resident memory
index build time
index size
update/rebuild cost

Warm-cache and cold-cache conditions should be separated. Results from one machine may also change under different NUMA, storage or concurrency conditions.

A vector database should be selected from these requirements rather than from the algorithm name alone. HNSW, IVF and PQ are mechanisms; the correct system is the one that reaches the required recall inside the acceptable tail-latency and resource budget. FAISS index architecture provides the wider implementation context.