How do I benchmark recall vs latency for vector indexes?

To benchmark recall vs. latency for a vector index, you want to measure:

1. How often the index returns the correct neighbors
2. How long each query takes
3. How these trade off as you change index/search parameters

Here’s a practical way to do it.

---

1) Define the benchmark task

Use a fixed dataset of vectors and a fixed set of query vectors.

You need:

• Corpus vectors: the database/index contents
• Query vectors: the test queries
• Ground truth neighbors: the exact nearest neighbors for each query, usually computed with brute force

Typical metric settings:

• k = number of nearest neighbors returned, e.g. k=10
• Distance metric: cosine, L2, or inner product — must match between ground truth and index

---

2) Build ground truth

For each query, compute exact top-k neighbors over the full corpus.

This is your “gold standard.”

Metrics commonly used:

• Recall@k = fraction of true top-k neighbors that appear in the approximate results
• Sometimes Recall@1 or Recall@10
• For reranking/search pipelines, you may use MRR, NDCG, etc., but recall@k is the standard for ANN indexes

Example:

• True top-10 neighbors for a query: {a,b,c,d,e,f,g,h,i,j}
• Returned neighbors: {a,b,x,d,e,y,z,h,i,m}
• Recall@10 = 6/10 = 0.6

---

3) Measure latency correctly

Measure query latency for the search call only, or separately measure:

• Index search latency
• End-to-end latency including preprocessing / network / serialization

For benchmarking indexes, usually focus on search latency.

Report:

• Average latency
• p50 / p95 / p99 latency
• Throughput if relevant: queries/sec

Important:

• Warm up the system before measuring
• Run enough queries to smooth variance
• Pin down CPU/GPU settings if possible
• Use the same batch size across tests, because batching changes latency a lot

---

4) Sweep index/search parameters

To get a recall-latency curve, vary the index’s search settings.

Examples:

• HNSW: vary efSearch
• IVF: vary nprobe
• FAISS PQ / Annoy / ScaNN: vary relevant search depth / candidate count
• DiskANN: vary beam width / search breadth

For each parameter setting:

1. Run the same query set
2. Compute recall@k
3. Measure latency
4. Plot recall vs. latency

This gives you a Pareto curve showing the best tradeoff.

---

5) Keep the benchmark fair

To make results comparable:

• Use the same corpus, query set, and distance metric
• Use the same k
• Use the same hardware
• Disable background tasks
• Run multiple trials
• Report mean and variance
• Ensure identical preprocessing/normalization

For cosine similarity, normalize vectors consistently before indexing and querying.

---

6) Use a standard benchmark harness if possible

Common tools:

• FAISS benchmark scripts
• ann-benchmarks: popular framework for ANN evaluation
• BigANN / DEEP / SIFT / GIST datasets for standard comparisons

ann-benchmarks is especially useful because it handles:

• Ground truth
• Multiple algorithms
• Parameter sweeps
• Recall-latency plots

---

7) Suggested evaluation procedure

A simple recipe:

1. Split data into:
   • Index vectors
   • Query vectors
2. Compute exact top-k neighbors with brute force
3. Build the vector index
4. For each search parameter value:
   • Warm up
   • Run all queries
   • Record per-query latency
   • Compute recall@k
5. Plot:
   • x-axis: latency (ms/query, often p95)
   • y-axis: recall@k

---

8) What to report

A good benchmark table might include:

• Dataset
• Metric (cosine / L2 / IP)
• k
• Index type and parameters
• Recall@k
• Mean latency
• p95 latency
• Memory footprint
• Build time, if relevant

Example:

Index	Param	Recall@10	Avg Latency (ms)	p95 (ms)
HNSW	ef=32	0.92	1.3	2.1
HNSW	ef=64	0.96	2.4	3.8
HNSW	ef=128	0.98	4.9	7.2

---

9) Common pitfalls

• No exact ground truth → recall numbers are meaningless
• Measuring cold-start latency only → results won’t reflect steady-state
• Changing batch sizes between runs → latency comparisons become unfair
• Different normalization / metric mismatch → incorrect evaluation
• Using only average latency → hides tail behavior

---

10) Minimal Python sketch

Conceptually:

# 1. Build ground truth exact neighbors
gt = exact_topk_search(corpus_vectors, query_vectors, k=10)

# 2. For each index/search parameter
for param in param_grid:
    index = build_index(corpus_vectors, param)

    warmup(index, query_vectors[:100])

    times = []
    recalls = []

    for q in query_vectors:
        start = time.perf_counter()
        results = index.search(q, k=10)
        times.append(time.perf_counter() - start)

        recalls.append(recall_at_k(results, gt[q], k=10))

    print(param, np.mean(recalls), np.mean(times), np.percentile(times, 95))

---

If you want, I can also give you:

• a FAISS-specific benchmarking script
• an ann-benchmarks setup
• or a Python template that computes recall@k and latency end-to-end.