How to Benchmark Recall at K for ANN Indexes

The dashboard that usually starts this work is a RAG answer-quality eval that dropped two points after a migration from a flat index to HNSW, or after someone lowered ef_search to buy back p99. Nothing errored. The index quietly began returning the eighth-nearest chunk instead of the first for a slice of queries, and the only way to see that is to measure it. Here is how to benchmark recall at k for ANN indexes so the number you get is comparable to published curves and stable enough to gate a deploy on.

The metric that matters

Recall@k for an ANN index is the fraction of the true k nearest neighbours that the approximate search returns, averaged over a query set. The Faiss paper writes the general form as n-recall@k, the fraction of the n ground-truth nearest neighbours that appear in the first k results, and notes that at n = k = 1 the measure becomes “did the index return the single true nearest neighbour”, which it calls accuracy. For search and RAG workloads you want n = k, with k equal to the limit your application actually sends, usually 10, which is also the k on ann-benchmarks.com and in the NeurIPS’21 billion-scale challenge.

Set intersection of returned IDs against ground-truth IDs, the obvious implementation, breaks on ties: two vectors at identical distance are both correct answers, but an ID check penalises the index for picking the “wrong” one. The ANN-Benchmarks paper avoids this with a distance-threshold definition: count every returned point whose distance to the query is at most the distance of the k-th true neighbour, and divide by k. The same paper defines a (1 + ε)-approximate variant that also accepts points within a factor of that k-th distance. Use the distance-threshold form: it matches the intuitive definition when distances are distinct and stops false regressions when they are not, which is why the NeurIPS’21 ground-truth files ship distances alongside IDs.

Two more things need pinning down. Ground truth must come from exact search over the same vectors and the same metric. In Faiss that is IndexFlatL2 or IndexFlatIP, which the project documents as the only indexes that guarantee exact results and the baseline for the others. The pgvector README says the same thing operationally: monitor recall by comparing results from approximate search with exact search, which you get by disabling index scans inside a transaction. And the query set must be held-out real queries, not vectors sampled from the corpus. The hnswlib README recall example queries the index with the vectors it just inserted and checks that each returns its own ID; that is a smoke test, not a benchmark, because a stored vector is at distance zero from itself.

Recall alone is not the deliverable. Every knob that raises recall costs throughput, so the artefact is recall plotted against QPS or p99 across settings, and what you report is the Pareto frontier: in Faiss’s definition, the settings that are the fastest for a given accuracy, or equivalently the most accurate for a given time budget.

Wiring it up

The sweep below builds ground truth once with a flat index, then walks efSearch on an HNSW index, recording tie-safe recall@10 plus p50 and p99 per-query latency. In the HNSW paper, ef is the size of the dynamic candidate list kept during search, and efConstruction is its build-time counterpart that controls the recall of the greedy search procedure; the ef_search explainer covers the knob in depth. Faiss is pinned to one thread because ANN-Benchmarks runs its experiment loop on a single CPU in a single thread, enforced with cpusets. Production will use more cores; keep the single-thread run for comparability and a separate run at production concurrency for capacity planning.

import time
import numpy as np
import faiss

d, k = 768, 10
xb = np.load("corpus.npy").astype("float32")    # (N, d), L2-normalised
xq = np.load("queries.npy").astype("float32")   # (Q, d), held-out real queries

# 1. Ground truth: exact search, computed once and cached
flat = faiss.IndexFlatIP(d)
flat.add(xb)
gt_d, gt_i = flat.search(xq, k)
np.save("gt_d.npy", gt_d)

def recall_at_k(res_d, gt_d, k):
    # Distance-threshold recall (Aumueller et al.): a hit is any returned
    # point at least as close as the k-th true neighbour, so ties never
    # count against the index. Inner product: larger means closer.
    kth = gt_d[:, k - 1][:, None]
    return ((res_d >= kth).sum(axis=1) / k).mean()

# 2. Candidate index and the knob sweep
index = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)
index.hnsw.efConstruction = 200
index.add(xb)
faiss.omp_set_num_threads(1)

for ef in (16, 32, 64, 128, 256, 512):
    index.hnsw.efSearch = ef
    res_d = np.empty((len(xq), k), dtype="float32")
    lat = np.empty(len(xq))
    for j, q in enumerate(xq):
        t0 = time.perf_counter()
        D, _ = index.search(q[None, :], k)
        lat[j] = time.perf_counter() - t0
        res_d[j] = D[0]
    print(f"ef={ef:4d} recall@{k}={recall_at_k(res_d, gt_d, k):.4f} "
          f"p50={np.percentile(lat, 50) * 1e3:.2f}ms "
          f"p99={np.percentile(lat, 99) * 1e3:.2f}ms")

The same shape works for any engine with an exact path. In pgvector the ground-truth side is the README’s enable_indexscan = off pattern and the approximate side sets the knob per transaction, so a sweep is a loop over settings. hnsw.ef_search defaults to 40 and ivfflat.probes to 1; both trade speed for recall.

BEGIN;
SET LOCAL enable_indexscan = off;
SELECT id, embedding <=> $1 AS dist FROM chunks
ORDER BY embedding <=> $1 LIMIT 10;
COMMIT;

BEGIN;
SET LOCAL hnsw.ef_search = 100;
SELECT id, embedding <=> $1 AS dist FROM chunks
ORDER BY embedding <=> $1 LIMIT 10;
COMMIT;

Return the distance column on both sides so the client can do the threshold comparison. If you would rather not write the harness, the ann-benchmarks repository runs the whole loop in Docker with install.py, run.py and plot.py, accepts a private dataset converted to its HDF5 format, and reports its --batch mode separately from single queries.

What you’ll see

A healthy sweep is concave: recall rises steeply at low ef, reaches a knee, and each further doubling of ef buys a smaller increment while p99 keeps climbing with the candidate list. Weaviate’s benchmark page puts it as generally, as the recall improves, the throughput drops. For a sanity check on public data, the ANN-Benchmarks paper found that on GLOVE, over all recall values, HNSW is fastest, and that on SIFT every tested algorithm reaches close to perfect recall.

Three bad shapes are diagnostic. A plateau well below 1.0 no matter how high ef goes points at the graph rather than the search: M or efConstruction too low, vectors missing from the index, a metric mismatch between the ground-truth run and the index (cosine ground truth against an L2 index on unnormalised vectors is the classic), or a metadata filter pruning the candidate set; the low recall causes and fixes post walks that list. A flat 1.0 at every setting usually means the harness, not the index: the query set is the corpus, or the planner chose a sequential scan and never touched the HNSW index. And a fine curve alongside a bad application eval means the ANN layer is not your problem. Index recall measures agreement with exact search over the same embeddings; whether those embeddings put the relevant chunk in the top ten is a retrieval-quality question answered against labelled judgments, not a flat index.

Caveats

Vendor benchmark versus independent benchmark is the first thing to check on any published curve. ANN-Benchmarks and the NeurIPS’21 challenge are independent, academic-run efforts; the latter ranked entries by the sum of recall@10 improvements over the baseline at a target QPS across datasets, with the standard-hardware track set at 10,000 QPS on 32 vCPUs, written up in Simhadri et al.. Weaviate’s benchmark is a vendor benchmark: Recall@10 and Recall@100 on SIFT1M, a 1M-vector 1536-dimensional DBPedia OpenAI set and two larger text sets, on one n4-highmem-16 with 16 vCPUs and 128 GB, open source so you can rerun it. Qdrant’s is also a vendor benchmark, on 8-vCPU Azure VMs with every engine capped at 25 GB in Docker; its page states that results must be compared only at similar precision and concedes the authors are not experts in every engine tested. Treat both as reference shapes, not as numbers for your data.

Ground truth is expensive: exact search is a full scan per query, which is why ANN-Benchmarks ships the true top-100 per query in its dataset files. Compute yours once, cache it, and invalidate it when the corpus or embedding model changes. Recall is a mean of per-query fractions, so use a few thousand queries and keep the per-query distribution: a mean of 0.97 can hide a cluster of queries at 0.5.

Recall is a property of index plus data, not of the engine, and it drifts: inserts and deletes reshape an HNSW graph, and a build-time benchmark says nothing about the index six weeks later. Put index recall on a schedule next to your other production signals; the monitoring metrics taxonomy on SentryML maps where it sits relative to input and prediction drift.

Two harness details bite. If the flat and graph paths compute distances with different SIMD kernels, exact ties can differ in the last bits and the >= comparison will miscount them; a tolerance around float32 epsilon fixes it. And batch mode inflates QPS relative to single queries; single-query p99 is the number your latency SLO cares about.

Related across the network

• How to Benchmark AI Security Tools: A 2026 Methodology — ai-alert.org
• LLM Jailbreak Defenses: Why Static Filters Fail — aiattacks.dev
• LLM Guardrail Benchmarks: Build Your Own Eval Set — aidefense.dev
• AI Security Testing: A Method for LLM and Agent Systems — aisecbench.com
• How to Benchmark LLM Security: A Repeatable Method — aisecbench.com