Lab K6: Benchmark Recall and Latency

Background

Approximate nearest-neighbor search has a knob for every metric you care about, and they all trade against each other. Crank ef_search and recall climbs but latency rises. Switch to PQ or on_disk mode and memory plummets but recall drops until you add a rescore pass. There is no single number that describes a vector index — there is a frontier: recall@k on one axis, latency (or throughput, or memory) on the other, and a curve you move along by changing engine, method, quantization, and ef_search.

A vector-search PR that claims "faster" or "smaller" without plotting that frontier is a guess, and k-NN maintainers treat it the way OpenSearch core treats an unbenchmarked performance PR (see Lab 9.2: Analyze a Performance Regression): they do not merge "should be better," they merge "here is recall@10 vs p99 latency, before and after, on a named workload, reproducible." This lab teaches you to produce that evidence: measure recall@k against a brute-force ground truth, measure latency/throughput and memory, vary the index parameters, and tabulate the frontier — using OpenSearch Benchmark's vectorsearch workload and a small custom harness. The k-NN repo's own benchmarking effort is k-NN #2595; read it to see what numbers maintainers expect.

Note on terminology: the cluster manager (formerly master) is irrelevant to a single-node recall/latency measurement — vector search performance is a per-shard, per-segment property. Benchmark on a controlled single node first; only scale out once the single-node frontier is understood, or you will conflate ANN behavior with distribution effects.

Why This Lab Matters for Contributors

• Every quantization, engine, or algorithm change in k-NN is defined by its effect on the recall/latency/memory frontier. You cannot review — let alone author — such a PR without measuring it. Quantization and disk-ANN ends with exactly this instruction: never ship aggressive compression without measuring post-rescore recall against ground truth.
• Recall is meaningless without a ground truth. Learning to compute brute-force exact-kNN as the oracle is the foundation; everything else is comparison against it.
• Maintainers gate vector-perf PRs on reproducible, apples-to-apples numbers. A benchmark that changes two variables at once, or doesn't warm the cache, or measures a cold first query, proves nothing. This lab is about methodology discipline.
• The skills transfer directly to the capstone project-06: k-NN Benchmark Harness and to the general performance-regression workflow in Lab 9.2.

The metrics, defined precisely

Warning: Recall@k is computed against exact nearest neighbors, not against another approximate run. If your "ground truth" is itself approximate, every recall number is fiction. The ground truth is brute force — score_script / a flat (ivf with nlist=1, or an exact scan) index — and you compute it once per query set.

Prerequisites

• Quantization and disk-ANN read — you know the compression spectrum (byte / FP16 / PQ / BQ / on_disk) and that rescore recovers recall.
• Native integration and memory read — you know graph_memory_usage and the warmup API (you must warm before measuring latency, or you measure cold-load cost, not query cost).
• A running OpenSearch with k-NN, ideally on dedicated hardware (a laptop on battery is not a benchmark host).
• Python 3 (for the harness and recall computation), and OpenSearch Benchmark: pip install opensearch-benchmark.

opensearch-benchmark --version
opensearch-benchmark list workloads | grep -i vector   # confirms the vectorsearch workload is available

Step 1: Establish a ground truth (brute force)

Recall needs an oracle. For a fixed query set, compute the exact top-k with a brute-force scan, independent of any ANN index. The cleanest way inside OpenSearch is an exact script_score over the raw vectors (no HNSW graph involved).

# Index the corpus once into a field you can scan exactly. (For real runs use the
# vectorsearch workload's dataset; this shows the mechanism on a tiny corpus.)
curl -XPUT 'localhost:9200/gt' -H 'Content-Type: application/json' -d '
{ "settings": { "index.knn": true },
  "mappings": { "properties": { "v": { "type": "knn_vector", "dimension": 128,
    "method": { "name": "hnsw", "engine": "faiss", "space_type": "l2" } } } } }'

# For ONE query vector, get the EXACT top-k via knn_score (brute-force, no graph):
curl -s 'localhost:9200/gt/_search' -H 'Content-Type: application/json' -d '
{ "size": 10, "query": { "script_score": {
      "query": { "match_all": {} },
      "script": { "source": "knn_score", "lang": "knn",
        "params": { "field": "v", "query_value": [/* 128 floats */], "space_type": "l2" } } } } }'

The knn_score script computes the true distance for every document — that is exact kNN, your ground truth. Run it for each query in your query set and store the result-id lists. A small Python loop is cleaner for a real query set:

# ground_truth.py — exact top-k per query, the recall oracle.
import json, numpy as np
from opensearchpy import OpenSearch

client = OpenSearch("http://localhost:9200")
K = 10

def exact_topk(field, qvec, k=K, space="l2"):
    body = {"size": k, "query": {"script_score": {
        "query": {"match_all": {}},
        "script": {"source": "knn_score", "lang": "knn",
                   "params": {"field": field, "query_value": qvec, "space_type": space}}}}}
    hits = client.search(index="gt", body=body)["hits"]["hits"]
    return [h["_id"] for h in hits]

queries = json.load(open("queries.json"))             # list of query vectors
ground_truth = {i: exact_topk("v", q) for i, q in enumerate(queries)}
json.dump(ground_truth, open("ground_truth.json", "w"))

Note: Brute force is O(N) per query — fine for tens of thousands of vectors, slow for millions. For large corpora, compute ground truth once with a dedicated tool (faiss IndexFlatL2 offline, or the dataset's provided ground-truth file — ANN benchmark datasets like SIFT/GIST ship one). Never skip it; recall without an oracle is noise.

Step 2: The recall computation

Recall@k is set overlap between ANN results and ground truth, averaged over queries.

# recall.py — recall@k of an ANN run vs the ground truth.
import json

def recall_at_k(ann_results, ground_truth, k=10):
    total = 0.0
    for qid, gt_ids in ground_truth.items():
        gt_set = set(gt_ids[:k])
        ann_set = set(ann_results[qid][:k])
        total += len(gt_set & ann_set) / float(k)
    return total / len(ground_truth)

gt  = {int(k): v for k, v in json.load(open("ground_truth.json")).items()}
ann = {int(k): v for k, v in json.load(open("ann_results.json")).items()}
print(f"recall@10 = {recall_at_k(ann, gt, 10):.4f}")

A knn query produces the ANN results to compare:

curl -s 'localhost:9200/test/_search' -H 'Content-Type: application/json' -d '
{ "size": 10, "query": { "knn": { "v": { "vector": [/* 128 floats */], "k": 10 } } } }'

Step 3: Run the OpenSearch Benchmark vectorsearch workload

OSB automates ingest, query load, and latency/throughput collection against a real dataset. The vectorsearch workload is purpose-built for k-NN.

# Inspect the workload's parameters (engine, method, ef_*, dataset path, etc.):
opensearch-benchmark info --workload vectorsearch

# Run it against your node. workload-params override the index/query knobs you vary.
opensearch-benchmark execute-test \
  --target-hosts localhost:9200 \
  --pipeline benchmark-only \
  --workload vectorsearch \
  --workload-params '{
     "target_index_name": "test",
     "dimension": 128,
     "engine": "faiss",
     "method": "hnsw",
     "m": 16,
     "ef_construction": 128,
     "ef_search": 100,
     "k": 10
   }'

OSB reports service_time and latency percentiles, throughput, and error rate per task. Crucially, the vectorsearch workload computes recall for you when given a ground-truth file — so you can let OSB do Steps 1–2 on the standard datasets. Confirm the exact param names for your OSB version:

# The workload's params drift between OSB releases — read the real list:
opensearch-benchmark info --workload vectorsearch | grep -iE 'ef_search|recall|ground|engine|param'

Warning — warm before you measure. A faiss graph loads into native memory on the first query (see native memory). If you measure latency including that cold load, you are benchmarking disk I/O and deserialization, not query speed. Always POST /_plugins/_knn/warmup/<index> (or run a warmup task) before the measured phase, and force-merge to a stable segment count first so segment count isn't a hidden variable.

Step 4: Vary one knob at a time and tabulate the frontier

The discipline that makes a benchmark evidence rather than anecdote: change exactly one variable per row, hold everything else fixed, warm up each time, and record the full vector of metrics. Sweep ef_search first (it moves recall/latency without reindexing):

# Sweep ef_search on a fixed faiss/HNSW index. ef_search is a query-time param:
for ef in 16 32 64 100 200 400; do
  echo "=== ef_search=$ef ==="
  curl -s "localhost:9200/test/_search" -H 'Content-Type: application/json' -d "
  { \"size\": 10,
    \"query\": { \"knn\": { \"v\": { \"vector\": [/* query */], \"k\": 10,
       \"method_parameters\": { \"ef_search\": $ef } } } } }" \
    | python3 -c 'import sys,json; r=json.load(sys.stdin); print("took_ms", r["took"])'
done

Then sweep the index-time dimensions (engine, method, quantization) by building a fresh index per configuration. A complete frontier table looks like this:

(Numbers are illustrative shapes, not promises — the point is the trade pattern: quantization buys memory at a recall/latency cost, rescore claws recall back, higher ef_search buys recall with latency.) The lucene engine's vectors are on the JVM heap (mmap'd), so graph_memory_usage from the native stats API reads n/a — that contrast is itself a finding (see native integration).

# Capture graph memory per config from the native stats API (faiss/nmslib only):
curl -s 'localhost:9200/_plugins/_knn/stats?pretty' | grep -E 'graph_memory_usage'

Note: Plot recall@10 (y) against p99 latency (x) for each engine/quantization as a curve, sweeping ef_search along it. A configuration is strictly better only if its curve is up-and-to-the-left of another's. A single point proves nothing; the curve is the deliverable.

Step 5: A reproducible methodology (the checklist maintainers expect)

A benchmark is only evidence if someone else can reproduce it. Pin every variable:

HARDWARE:   instance type / CPU model / RAM / disk (NVMe vs network) — vector perf is CPU+memory bound
JVM:        -Xmx, JDK version (Panama SIMD needs a recent JDK; see ../../lucene/simd-and-the-vector-api.md)
DATASET:    name, N vectors, dimension, distribution (e.g. SIFT-1M, 128-d, L2)
QUERIES:    fixed query set (count, same set across all configs), provided ground truth
INDEX:      shards=1, replicas=0 (isolate ANN from distribution), force-merge to 1 segment
WARMUP:     POST _plugins/_knn/warmup BEFORE measured phase; discard first run
CONFIG:     engine, method, m, ef_construction, ef_search, quantization, oversample_factor, rescore
PROCEDURE:  one variable changed per run; N measured queries; report p50/p90/p99 + recall + mem
REPEAT:     ≥3 runs per config; report median; note variance

Warning: replicas=0 and shards=1 for the controlled run. Replicas mean a query can hit a different copy with a differently-built graph (HNSW construction is non-deterministic across merges), and multiple shards mean per-shard top-k merging — both add variance that has nothing to do with the ANN parameter you are studying. Add shards back only when you are explicitly measuring distribution.

Step 6: How maintainers gate vector-perf PRs

When you submit a change that touches the vector path, the reviewer wants the same evidence this lab produces. The bar (mirroring core perf review in Lab 9.2):

The benchmarking work tracked in k-NN #2595 exists precisely to standardize this so PRs are comparable across time. Read it before proposing a vector-perf change, and frame your numbers against its methodology.

Implementation Requirements / Deliverables

• A brute-force ground truth for a fixed query set (exact top-k per query), produced independently of any ANN index.
• A working recall@k computation (set overlap vs ground truth), with a pasted number.
• An OSB vectorsearch run (pasted summary) and/or a custom harness producing latency percentiles.
• A frontier table varying at least engine or quantization and ef_search, with recall + latency + graph memory per row.
• The reproducibility methodology block filled in with your actual hardware/dataset/config.
• Warmup performed before every measured phase (state how you verified it via stats).

Troubleshooting

Expected Output

A recall computation and a frontier slice, e.g.:

$ python3 recall.py
recall@10 = 0.9712     # faiss HNSW + PQ(m=64) + rescore, ef_search=100

$ # OSB summary excerpt
|   Metric |        Task | Value |  Unit |
| Min Throughput | knn-search |  812 | ops/s |
| 50th percentile latency | knn-search | 2.4 | ms |
| 99th percentile latency | knn-search | 8.8 | ms |
| Mean recall@10 | knn-search | 0.971 |   - |

The deliverable is not any single number — it is the table and the curve: a reader can see exactly what PQ+rescore costs in recall and latency to save 6× memory versus float32, and decide if that trade fits their constraint.

Stretch Goals

1. Plot the frontier. Produce a recall@10-vs-p99 scatter with one curve per engine/quantization, ef_search swept along each. Identify which configs are Pareto-dominated (strictly worse on both axes) and drop them.
2. Measure the rescore knob. Hold quantization fixed (say PQ) and sweep oversample_factor from 1x to 10x. Show recall rising and latency rising, and find the knee where more oversample stops buying recall.
3. Build vs serve. Time index-build/force-merge per config and tabulate it alongside query metrics — this is the cost the GPU/remote-build RFCs (#2293 / #2294) attack. Which configs are build-bound vs serve-bound?
4. Compare engines fairly. Put faiss-HNSW and lucene-HNSW on the same recall and compare latency and memory. The lucene engine's heap residency vs faiss's native memory is a real deployment trade — quantify it.
5. Take it to the capstone. Turn this into the reusable, parameterized harness of project-06: k-NN Benchmark Harness.

Validation / Self-check

1. Why is recall meaningless without a ground truth, and how do you compute an exact ground truth inside OpenSearch? Why can't another knn query serve as the oracle?
2. Define recall@k precisely as a set operation. If ANN returns 8 of the true top-10, what is recall@10?
3. Why must you warm up before measuring latency? What are you actually measuring if you don't, and how do you verify warmup happened?
4. Name three variables you must hold fixed to make two runs comparable, and explain what variance each one introduces if you let it move.
5. Why shards=1, replicas=0 for a controlled ANN benchmark? What does each setting isolate you from?
6. Walk a quantization PR's evidence: which three metrics must move in the reviewer's favor (or be shown not to regress) for it to merge? Give a concrete example of a "win" that is actually a loss.
7. Why is a single (recall, latency) point insufficient, and what is the curve that replaces it? When is one configuration strictly better than another?

When you can produce a ground truth, compute recall@k, sweep a parameter, and present the recall/latency/memory frontier with a reproducible methodology, you can both author and review vector-perf changes the way maintainers require. Close the loop with quantization and disk-ANN (the trades you just measured), Lab 9.2: Analyze a Performance Regression (the same discipline for core), and the capstone project-06: k-NN Benchmark Harness.