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. For ready-to-run matplotlib that renders exactly this frontier (and feeds on these numbers), see Lab VI4: Visualizing ANN.

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.

Coding Exercises

The lab gave you fragments — a ground-truth loop, a recall function, an ef_search sweep. These exercises weld them into a real, reusable harness and end at a self-contained benchmarking program. The deliverables are code that produces the frontier, not transcripts. Build on the Python the lab already uses; reach for C++/faiss where exact ground truth at scale demands it.

1. (warm-up) Test your recall function. Before trusting recall_at_k, write a pytest (or plain assert) suite that feeds it hand-built cases: perfect overlap → 1.0, zero overlap → 0.0, "8 of true top-10" → 0.8 (the lab's own self-check question), and a case where ANN returns more than k. A recall harness with a bug silently makes every downstream number fiction — so pin it first. This is the unit test the lab's discipline demands of measurement code itself.

2. (core) A standalone faiss ground-truth generator in C++ (or Python+faiss). The lab notes brute force is O(N) and says to compute ground truth offline with faiss IndexFlatL2 for large corpora. Implement it: a small program that loads a corpus + query set (e.g. the SIFT/.fvecs format), builds a faiss::IndexFlatL2, runs exact search for the query set, and writes a ground_truth.json your recall.py can consume. Doing this in C++ against the same faiss the plugin bundles (see lab-k1's jni/external/faiss) makes the oracle authoritative and fast. Verify it agrees with the in-OpenSearch knn_score oracle on a tiny corpus. The L2/inner-product distance it computes is exactly vector-math foundations made concrete.

3. (core) A parameterized recall/latency harness. Turn Steps 1–4 into one Python program bench.py that takes a config (engine, method, m, ef_construction, ef_search, quantization, oversample) and produces a full metric vector: builds/loads the index, warms it via POST /_plugins/_knn/warmup (assert via _plugins/_knn/stats that graph_memory_usage went non-zero before timing), runs the query set, computes recall@k against your ground truth, and records p50/p90/p99 latency and graph_memory_usage. One config in → one row out. The warmup-then-measure ordering is the methodology rule the lab puts a Warning on.

4. (core) The ef_search sweep as a frontier producer. Wrap bench.py in a sweep over ef_search ∈ {16, 32, 64, 100, 200, 400} on a fixed faiss/HNSW index (no reindex — it's a query-time param), writing one CSV row per value with recall@10 and p99. Assert the obvious monotonic shape (recall non-decreasing, latency non-decreasing as ef_search grows) and flag any row that violates it as a measurement error (probably un-warmed or noisy). This CSV is the exact input that feeds Lab VI4's plots — emit columns named so they drop straight in.

5. (core) Quantify the SIMD payoff. Build the plugin twice via lab-k1's AVX matrix (AVX512 on vs SIMD off), run the same bench.py config against each node, and tabulate the latency delta at fixed recall. Write up which metric SIMD moves (latency, not recall) and by how much on your CPU. This connects the benchmark frontier to the kernel-level work in native SIMD and faiss kernels — the distance-computation inner loop is where the SIMD speedup lives.

6. (advanced challenge) A reproducible frontier harness that emits Lab VI4's plot input. Compose everything into a single parameterized tool that takes a YAML/JSON matrix of configs (engine × quantization × ef_search), runs each with the full methodology (force-merge to 1 segment, replicas=0, shards=1, warmup, ≥3 repeats → median, variance noted), computes recall against your faiss ground truth, captures latency + graph memory, and writes a tidy CSV plus a Markdown frontier table identical in shape to the lab's Step-4 table. Crucially, emit the CSV in the exact schema Lab VI4: Visualizing ANN expects, so its matplotlib renders your frontier with no edits, and have the tool drop Pareto-dominated configs automatically. This is the capstone harness of project-06 in miniature: the reproducible, apples-to-apples evidence a maintainer needs to merge any vector-perf PR.

Issues to Practice On

Vector-perf work — benchmarking, recall regressions, quantization trades — is gated entirely on the kind of evidence this lab produces. The repo is opensearch-project/k-NN.

Labels drift — list and pick (gh label list --repo opensearch-project/k-NN). Anchor issues: #2595 (benchmarking effort) and the remote/GPU build RFCs #2293 / #2294.

Representative issue patterns. (1) "Recall dropped after change X / quantization is worse than expected" — reproduce against a fixed ground truth and query set, sweep ef_search and oversample_factor to find where recall recovers, and report the whole frontier (not a single point) in the issue. (2) "Benchmark X / standardize the methodology" — contribute a workload config or harness improvement that pins hardware/dataset/merge state, framed against #2595's methodology. Both are reviewer-friendly because they add measurement, the thing maintainers chronically need.

Planted-bug exercise. In your recall.py, change the set intersection to a union (| instead of &) — recall now reads ~1.0 on every config, the lab's "suspiciously 1.000" symptom. Run your Exercise 1 tests and watch them go red on the perfect-overlap and 8-of-10 cases. Fix it. Then plant a methodology bug instead: skip the warmup step in bench.py and observe the first measured query dominate p99; assert (via the stats check from Exercise 3) that warmup happened before timing, and watch that assertion catch the un-warmed run. The lesson the lab hammers: a benchmark with a measurement bug proves nothing — guard the harness with tests.

Etiquette. Claim the issue before working it, reproduce with a real ground truth first (another knn query is not an oracle), and every perf PR needs the methodology block, before/after numbers on a named workload, and — for code changes — a test, a CHANGELOG.md entry, and a DCO sign-off (git commit -s). See community interaction and the core performance discipline in Lab 9.2.

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.