Project 6: A k-NN Recall/Latency Benchmark Harness

Every claim about vector search is a lie until it has a recall number attached. "Faster" is meaningless if recall dropped. "Smaller" is meaningless if latency tripled. "Better quantization" is three numbers — recall@k, latency, and memory — measured together, on a fixed dataset, against a known ground truth, reproducibly. The single most common reason a k-NN performance PR stalls is that the author brought one number (latency) and the maintainer asked for the other two.

This project builds the thing that makes every other k-NN project credible: a reproducible benchmark harness that, given an engine/quantization configuration, reports recall@k and p50/p99 query latency and native-memory footprint, against a ground truth it computes itself. It is the "Medium" project in the portfolio to build and one of the most mergeable, because a clean, documented harness is exactly the tooling the k-NN team and every future contributor wants.

Note: Read Quantization and Disk-ANN and do the benchmark lab before you start. This brief assumes you know what recall@k means, what a space_type is, what on_disk mode and compression_level do, and how to read GET /_plugins/_knn/stats. It builds the lab's one-off measurement into a harness — repeatable, configurable, and trustworthy.

This project is also the prerequisite tool for the recall claims in Project 1. If you are doing both, build this first.

Problem & motivation

Benchmarking ANN is uniquely easy to get wrong, and the wrong way looks fine:

• Recall needs a ground truth, and the ground truth is the expensive part. Recall@k is "of the true k nearest neighbours, how many did the approximate search return?" The true k nearest neighbours come from an exact (brute-force / flat) search over the same vectors with the same space_type. People skip this and report latency alone — or, worse, compute "recall" against an approximate baseline, which measures nothing.
• The three numbers trade off against each other and must be reported together. A configuration is a point on a recall/latency/memory surface. Reporting one axis hides the trade. ef_search alone moves recall and latency in opposite directions; quantization moves memory and recall together. A harness that cannot report all three at one configuration is not a benchmark.
• "Reproducible" is the whole game and is rarely achieved. Different dataset, different query set, different ef_construction, a warmup that was or wasn't run, a circuit breaker that tripped mid-run, a single-shard vs multi-shard index, JIT not warmed — any of these silently changes the numbers. A result without the full configuration captured is folklore, not data.
• The k-NN team explicitly wants better benchmarking. Comparing engines, quantization modes, and the in-flight GPU/remote-index-build work requires a trustworthy harness. This is open tooling the project asks for.

This project builds the harness so that "I made k-NN faster" becomes a table anyone can regenerate.

Real-world grounding

The grounding issue is the k-NN benchmarking work itself — the project's own statement that it needs reproducible recall/latency/memory comparison across engines and quantization modes:

• Benchmarking the vector engine — k-NN #2595: https://github.com/opensearch-project/k-NN/issues/2595

This sits next to the GPU / remote-index-build RFCs whose claims a harness like this exists to validate — those features are entirely about recall/latency/memory trade-offs and cannot be evaluated without exactly this tool:

• [RFC] Boosting OpenSearch vector-engine performance using GPUs — k-NN #2293: https://github.com/opensearch-project/k-NN/issues/2293
• [RFC] Remote vector index build — k-NN #2294: https://github.com/opensearch-project/k-NN/issues/2294

Citation discipline: the benchmarking effort spawns sub-issues fast. Before you scope, search is:issue is:open label:Benchmarks and is:issue is:open recall OR latency benchmark in opensearch-project/k-NN, and check whether OpenSearch Benchmark already has a vector workload you should extend rather than reinvent (search its repo for vectorsearch / bigann). Link the current issue in your design note; #2595 is the anchor.

Subsystems you'll touch

This project is more integration and tooling than core-Java surgery — which is exactly why it is mergeable and a great first "I shipped infrastructure" contribution. You will touch:

Deep dives that cover the surrounding ground: k-NN query path · native JNI and memory · quantization and disk-ANN · the benchmark lab (the one-off this project generalizes) · the perf-regression lab (the discipline of before/after measurement, applied here to recall as well as latency).

Phased plan

The discipline of this project is that Phase 1 is a single-configuration harness that already produces a correct, reproducible three-number result. Everything after is sweeping that over more configurations and hardening it for others to run.

Phase 0 — Establish ground truth and the recall definition (1 day)

Before any benchmark, you must be able to compute the exact k nearest neighbours for a dataset, in the same space_type the index uses. Pick a standard, license-clean dataset with a fixed query split (a SIFT/GIST-style ANN dataset, or the dataset the OSB vectorsearch workload already uses — prefer the latter so your numbers are comparable to the project's).

# A "flat" / exact index = an HNSW field is the wrong oracle. Use brute force.
# Option A (recommended): index the SAME vectors with an exact method (flat) or compute exact
# neighbours offline in NumPy and store them as the ground-truth file.
python3 - <<'PY'
import numpy as np
base = np.load("base.npy")      # (N, dim) corpus
queries = np.load("query.npy")  # (Q, dim) query set
# L2 ground truth (mirror your space_type EXACTLY — l2 here):
d = ((queries[:, None, :] - base[None, :, :])**2).sum(-1)   # (Q, N), do it in blocks for big N
gt = np.argsort(d, axis=1)[:, :100]                          # top-100 true neighbours per query
np.save("groundtruth.npy", gt)
PY

Warning: the ground truth MUST use the same distance as the index space_type. Compute L2 ground truth for an l2 index, cosine for cosinesimil, inner-product for innerproduct. A mismatched oracle silently makes every recall number wrong. This is the single most common benchmark-harness bug — assert the space match in your harness config.

Write capstone-work/recall-definition.md: the exact recall@k formula you use, the dataset, the query split, the space_type, and how you computed ground truth. This is the document that makes your numbers auditable.

Phase 1 — A single-configuration, three-number harness (the scoped, mergeable core)

Build a harness that takes ONE configuration and emits recall@k, p50/p99 latency, and native-memory MB — reproducibly. Prefer extending the OSB vectorsearch workload over a bespoke script, so it plugs into tooling the project already runs.

# Driver outline (OSB or a thin Python wrapper around the REST API):
# 1. PUT the index with the configured knn_vector mapping
curl -s -X PUT localhost:9200/bench -H 'Content-Type: application/json' -d '{
  "settings": { "index.knn": true, "index.number_of_shards": 1 },
  "mappings": { "properties": { "v": {
    "type": "knn_vector", "dimension": 128, "space_type": "l2",
    "method": { "name": "hnsw", "engine": "faiss",
                "parameters": { "m": 16, "ef_construction": 256 } }
  }}}
}'
# 2. _bulk index the corpus (batched), then force-merge to a stable segment count
curl -s -X POST localhost:9200/bench/_forcemerge?max_num_segments=1
# 3. WARM UP native memory so the first query isn't penalized
curl -s -X POST localhost:9200/_plugins/_knn/warmup/bench
# 4. record native memory BEFORE timing
curl -s localhost:9200/_plugins/_knn/stats?pretty
# 5. run the fixed query set, capturing per-query ids and latency
# 6. compute recall@k against groundtruth.npy; report p50/p99 latency; report native MB delta

The harness must capture the full configuration in its output so the run is reproducible:

{
  "config": { "engine": "faiss", "method": "hnsw", "m": 16, "ef_construction": 256,
              "ef_search": 100, "space_type": "l2", "mode": "in_memory",
              "compression_level": "1x", "dimension": 128, "shards": 1,
              "dataset": "sift-1m", "k": 10, "queries": 10000, "warmup": true },
  "result": { "recall_at_10": 0.987, "p50_ms": 1.8, "p99_ms": 4.1,
              "native_mem_mb": 612, "index_build_s": 73 }
}

Why this is the right Phase 1: a single-configuration harness that captures the full config and emits all three numbers correctly is already the thing the project needs. It is the unit the sweep in Phase 2 repeats. Get one row provably right — including ground-truth correctness — before you generate a hundred.

Validate Phase 1 by proving recall is correct at the extremes:

sanity check          expected            why
exact / flat method   recall@10 == 1.000  brute force must score perfect against its own ground truth
ef_search very high   recall@10 -> 1.000   HNSW with huge ef_search approaches exact
ef_search very low    recall@10 low        and latency low — the trade is visible

If your "exact" configuration does not score recall 1.000 against your ground truth, your ground truth or your recall computation is wrong. Fix that before anything else. This self-check is the single most important gate in the whole project.

Phase 2 — Sweep the configuration space

Now make the harness parametric: run the matrix and produce one row per configuration, so trade-offs are visible.

engine  method  quant   ef_search  recall@10  p50_ms  p99_ms  native_mb  build_s
faiss   hnsw    1x        64         0.962      1.4     3.0      612        73
faiss   hnsw    1x        128        0.987      1.9     4.1      612        73
faiss   hnsw    on_disk8x 128        0.94x      2.x     x.x       8x         7x
lucene  hnsw    1x        128        0.98x      x.x     x.x       (heap)     x

The deliverable is not the numbers (those are dataset-specific) — it is the recall/latency Pareto curve the harness can draw for any engine/quant combination, reproducibly, from a config file.

Phase 3 — Make it reproducible by someone who is not you

This is what separates a script from a harness. Pin everything:

• A single config file drives a full run; the output embeds the config (as above).
• The dataset is fetched/verified by checksum; the ground truth is regenerated or checksum-verified.
• The harness records the k-NN/OpenSearch version, JDK, engine native-lib version, and shard count.
• A --dry-run validates the config (space match, dataset present, ground-truth present) before spending an hour indexing.
• A README a stranger can follow to regenerate any row of your table.

Test the reproducibility claim literally: run the same config twice and assert recall is identical and latency is within a stated tolerance band. If two runs disagree on recall, something is nondeterministic that should not be (different query order? a circuit breaker tripping?) — find it.

Phase 4 — Wire it into CI-shaped, regression-catching form

The highest-value version of this harness catches a regression: a code change that drops recall or raises latency. Add a "compare two runs" mode that diffs a current run against a stored baseline and flags any recall drop beyond tolerance or latency rise beyond tolerance — the ANN analogue of the perf-regression lab.

$ harness compare --baseline baseline.json --candidate run.json
config: faiss/hnsw/on_disk8x/ef=128
  recall@10:  0.943 -> 0.911   REGRESSION (drop 0.032 > tolerance 0.01)   FAIL
  p50_ms:     2.1  -> 2.0      ok

That is the artifact a maintainer dreams about: a harness that turns "did this PR quietly hurt recall?" from a guess into a gate.

Deliverables

• capstone-work/recall-definition.md — the recall@k formula, dataset, query split, space_type, ground-truth method
• capstone-work/design.md — extend-OSB vs bespoke decision, the config schema, what you measure and why
• Phase 1: a single-config harness emitting recall@k + p50/p99 + native MB, with the exact/ef_search sanity checks passing
• Phase 2: a parametric sweep producing a recall/latency Pareto table across engines and quantization
• Phase 3: a fully reproducible run (config-driven, checksummed dataset+ground truth, version-stamped output) + README
• (Phase 4) a compare mode that flags recall/latency regressions beyond tolerance
• capstone-work/validation.md — the commands, dataset checksums, versions, and a same-config-twice reproducibility check
• An upstreaming decision: a PR to the OSB vectorsearch workload / k-NN benchmarking, or a written proposal under #2595
• A 500–1000 word write-up: the trade-off surface, the ground-truth-correctness story, the reproducibility argument

Difficulty & time

The reason this is "Medium" and not "Easy" is that a benchmark that looks fine but has a wrong ground truth is worse than no benchmark — it produces confident, wrong numbers. The engineering is modest; the measurement discipline is the whole grade.

Stretch goals

• Add a filtered k-NN axis: recall/latency with a restrictive filter (the lucene engine's filtered path vs faiss), since filtering changes the recall story materially.
• Add a memory-pressure scenario: index past the native-memory circuit-breaker limit and report how recall/latency degrade when graphs are evicted and reloaded.
• Plot the Pareto curves automatically (a tiny matplotlib step) so a PR can paste a figure, not just a table.
• Validate one claim from the GPU RFC (#2293) or remote-index-build RFC (#2294) if you have access to the relevant build — the harness exists precisely to check those claims.
• Contribute the harness output format as a shared schema so multiple contributors' numbers are directly comparable.

Evaluation

Self-grade against the 100-point rubric. For this project the Testing dimension dominates — this is a testing/measurement project:

A finished, reproducible harness at 90+ is mergeable tooling and the instrument that makes every other vector PR — including Project 1 — credible.

How to turn this into a real contribution

1. Extend, don't reinvent. Check the OSB vectorsearch workload first. If recall@k or a custom param source already exists there, your contribution is "add the missing axis / fix the ground-truth handling," which is far more mergeable than a parallel harness.
2. Comment before you build. On #2595, state which datasets, which axes, and which output schema you propose. The team has opinions about what "the" benchmark should measure — get them first.
3. Lead with the correctness gate. The reviewer's first question is "how do I trust your recall number?" Your README's first section is the exact-config recall-1.000 proof and the ground-truth method. Earn trust before showing tables.
4. Pin everything. A benchmark PR that cannot be regenerated is not mergeable. Dataset checksum, versions, config-in-output, same-config-twice reproducibility — these are the contribution.
5. DCO applies. k-NN and OSB are GitHub-native: git commit -s, follow each repo's contributor guide. OSB workloads have their own structure — read an existing workload's layout before adding.

A trustworthy harness is the rare contribution that makes everyone else's work better. That is why "Medium difficulty, high mergeability" is not a contradiction here — it is the point.