Lab L3: Build an HNSW Graph from Scratch

Background

You have read how HNSW works — layers, greedy search, the M/efConstruction/efSearch knobs — and how the SIMD kernel makes each distance fast. Now you will build it: a standalone Java program that indexes float vectors into a Lucene index using Lucene99HnswVectorsFormat, runs a KnnFloatVectorQuery, and measures recall@k against a brute-force exact scan. Then you will sweep M, efConstruction, and efSearch and tabulate how recall and latency move — turning the abstract trade-off table from the chapter into numbers you produced.

This is the lab that makes ANN concrete. "Approximate" stops being a word and becomes a measured recall of 0.94 that you can push to 0.99 by raising efSearch at a latency cost you can read off a table. At the end you map every knob to its OpenSearch k-NN equivalent so you can tune a real knn_vector field with intuition instead of guesswork.

Note: This uses the Lucene HNSW classes directly — exactly what OpenSearch's k-NN lucene engine wraps. The recall/latency behavior you measure here is the behavior of a lucene-engine knn_vector field; only the configuration surface differs. See k-NN algorithms.

Why This Lab Matters for Contributors

Recall@k vs latency vs memory is the vector-search trade-off. Measuring it yourself builds the intuition every k-NN issue, benchmark, and tuning question depends on.
You will see directly why M/efConstruction are index-time (graph-baked) and efSearch is query-time — because you change one and must rebuild, the other you change per query.
Writing the brute-force baseline teaches you what "ground truth" means for ANN evaluation — the thing every benchmark (k-NN #2595, ann-benchmarks) compares against.
The exact configuration you set on Lucene99HnswVectorsFormat is what k-NN's lucene engine sets under the hood; this lab demystifies that engine.

Prerequisites

Lab L1 (build/inspect an index) and the HNSW chapter.

JDK 21; the lucene-core jar from your apache/lucene checkout:

CORE=$(find /path/to/apache/lucene -name "lucene-core-*.jar" | grep -v sources | head -1)
echo "$CORE"

Run everything with --add-modules jdk.incubator.vector so distance scoring is SIMD-accelerated.

Step-by-Step Tasks

Step 1: The plan

flowchart LR
    Gen["generate N random vectors (dim d)"] --> Index["index into Lucene<br/>Lucene99HnswVectorsFormat(M, efConstruction)"]
    Gen --> Brute["brute-force exact top-k<br/>(ground truth)"]
    Index --> Query["KnnFloatVectorQuery(k, efSearch)"]
    Query --> Compare["recall@k = overlap / k"]
    Brute --> Compare
    Compare --> Sweep["sweep M / efConstruction / efSearch -> table"]

You need four pieces: a vector generator, an HNSW indexer with tunable M/efConstruction, a brute-force scorer for ground truth, and a recall+latency harness that sweeps parameters.

Step 2: Configure the HNSW vector format with `M` and `efConstruction`

To set M and efConstruction you supply a custom codec whose knnVectorsFormat() returns a Lucene99HnswVectorsFormat(maxConn, beamWidth) — the same FilterCodec pattern from Lab L2:

import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.FilterCodec;
import org.apache.lucene.codecs.KnnVectorsFormat;
import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;

/** A codec that pins the HNSW build parameters M (maxConn) and efConstruction (beamWidth). */
public class HnswCodec extends FilterCodec {
    private final KnnVectorsFormat vectorsFormat;

    public HnswCodec(int m, int efConstruction) {
        super("HnswLab", Codec.getDefault());
        // maxConn == M, beamWidth == efConstruction. These are baked into the graph at index time.
        this.vectorsFormat = new Lucene99HnswVectorsFormat(m, efConstruction);
    }

    @Override
    public KnnVectorsFormat knnVectorsFormat() {
        return vectorsFormat;
    }
}

Note: Lucene99HnswVectorsFormat(maxConn, beamWidth) is the full-precision (float32) HNSW format. To experiment with quantization, swap in Lucene99HnswScalarQuantizedVectorsFormat (int8) or a Lucene104HnswScalarQuantizedVectorsFormat (1/2/4/7/8-bit) and watch recall and .vec size change — a great stretch goal that mirrors OpenSearch's quantization modes.

Step 3: Index vectors, with `M`/`efConstruction` fixed at build time

import org.apache.lucene.document.Document;
import org.apache.lucene.document.KnnFloatVectorField;
import org.apache.lucene.document.StoredField;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;

import java.nio.file.Paths;
import java.util.Random;

public class HnswLab {

    static final int N = 20_000;     // corpus size
    static final int DIM = 64;       // dimensions (small for speed; try 768 for realism)
    static final int K = 10;         // top-k

    /** Deterministic random vectors so runs are comparable. */
    static float[][] randomVectors(int n, int dim, long seed) {
        Random r = new Random(seed);
        float[][] vs = new float[n][dim];
        for (int i = 0; i < n; i++)
            for (int d = 0; d < dim; d++)
                vs[i][d] = r.nextFloat() * 2 - 1;   // [-1, 1)
        return vs;
    }

    static Directory buildIndex(float[][] vectors, int m, int efConstruction) throws Exception {
        Directory dir = FSDirectory.open(Paths.get("hnsw-index-" + m + "-" + efConstruction));
        IndexWriterConfig cfg = new IndexWriterConfig();
        cfg.setCodec(new HnswCodec(m, efConstruction));      // <-- M & efConstruction here
        try (IndexWriter w = new IndexWriter(dir, cfg)) {
            for (int i = 0; i < vectors.length; i++) {
                Document doc = new Document();
                doc.add(new StoredField("id", i));
                doc.add(new KnnFloatVectorField("vec", vectors[i], VectorSimilarityFunction.EUCLIDEAN));
                w.addDocument(doc);
            }
            // One segment => one graph => clean, comparable measurements.
            w.forceMerge(1);
        }
        return dir;
    }
    // ... continued below
}

Step 4: Brute-force ground truth

The recall denominator is the true top-k from an exact scan. Compute it once per query:

    /** Exact top-k by squared Euclidean distance. Returns the k nearest doc ids (the original index). */
    static int[] bruteForceTopK(float[][] vectors, float[] query, int k) {
        // Max-heap of size k keyed by distance (largest distance on top, so we can evict).
        java.util.PriorityQueue<int[]> heap =
            new java.util.PriorityQueue<>((a, b) -> Integer.compare(b[1], a[1])); // [id, scaledDist]
        // Use a parallel array of doubles for precise distance, ids for tie-break.
        double[] bestDist = new double[k];
        int[] bestId = new int[k];
        java.util.Arrays.fill(bestDist, Double.MAX_VALUE);
        java.util.Arrays.fill(bestId, -1);
        for (int i = 0; i < vectors.length; i++) {
            double dist = 0;
            float[] v = vectors[i];
            for (int d = 0; d < query.length; d++) {
                double diff = v[d] - query[d];
                dist += diff * diff;
            }
            // Insert into the running top-k (worst slot is index of max).
            int worst = 0;
            for (int j = 1; j < k; j++) if (bestDist[j] > bestDist[worst]) worst = j;
            if (dist < bestDist[worst]) { bestDist[worst] = dist; bestId[worst] = i; }
        }
        return bestId;
    }

Step 5: ANN query with `efSearch` and recall measurement

KnnFloatVectorQuery's third arg is k. To raise the search beam (efSearch) beyond k, request a larger candidate set and keep the top k — Lucene's collector expands the beam to satisfy the requested count, so querying for efSearch candidates and trimming to k is the practical lever from the reader API:

import org.apache.lucene.document.Document;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.KnnFloatVectorQuery;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.store.Directory;

    /** Run an ANN query; return the doc ids of the top-k (mapped via the stored "id"). */
    static int[] annTopK(IndexSearcher searcher, DirectoryReader reader,
                         float[] query, int k, int efSearch) throws Exception {
        // Request efSearch candidates (>= k) to widen the beam, then keep the best k.
        KnnFloatVectorQuery q = new KnnFloatVectorQuery("vec", query, Math.max(k, efSearch));
        TopDocs td = searcher.search(q, Math.max(k, efSearch));
        int[] ids = new int[Math.min(k, td.scoreDocs.length)];
        org.apache.lucene.index.StoredFields sf = reader.storedFields();
        for (int i = 0; i < ids.length; i++) {
            Document d = sf.document(td.scoreDocs[i].doc);
            ids[i] = d.getField("id").numericValue().intValue();
        }
        return ids;
    }

    /** recall@k = |annTopK ∩ trueTopK| / k. */
    static double recall(int[] ann, int[] truth) {
        java.util.Set<Integer> t = new java.util.HashSet<>();
        for (int id : truth) if (id >= 0) t.add(id);
        int hit = 0;
        for (int id : ann) if (t.contains(id)) hit++;
        return (double) hit / t.size();
    }

Step 6: The sweep harness — `main`

Tie it together: build one index per (M, efConstruction), then for a set of query vectors measure recall and average latency across efSearch values:

    public static void main(String[] args) throws Exception {
        float[][] corpus = randomVectors(N, DIM, 1L);
        float[][] queries = randomVectors(200, DIM, 999L);    // disjoint seed = held-out queries

        // Ground truth once (independent of HNSW params).
        int[][] truth = new int[queries.length][];
        for (int qi = 0; qi < queries.length; qi++) truth[qi] = bruteForceTopK(corpus, queries[qi], K);

        int[] Ms          = { 8, 16, 32 };
        int[] efConstrs   = { 64, 128 };
        int[] efSearches  = { 10, 50, 100, 200 };

        System.out.printf("%-4s %-6s %-6s %-9s %-12s%n", "M", "efC", "efS", "recall@" + K, "avg_us/query");
        for (int m : Ms) {
            for (int efc : efConstrs) {
                Directory dir = buildIndex(corpus, m, efc);                 // index-time params
                try (DirectoryReader reader = DirectoryReader.open(dir)) {
                    IndexSearcher searcher = new IndexSearcher(reader);
                    for (int efs : efSearches) {                            // query-time param
                        double recallSum = 0; long nanos = 0;
                        for (int qi = 0; qi < queries.length; qi++) {
                            long t0 = System.nanoTime();
                            int[] ann = annTopK(searcher, reader, queries[qi], K, efs);
                            nanos += System.nanoTime() - t0;
                            recallSum += recall(ann, truth[qi]);
                        }
                        System.out.printf("%-4d %-6d %-6d %-9.4f %-12.1f%n",
                            m, efc, efs, recallSum / queries.length, (nanos / 1000.0) / queries.length);
                    }
                }
            }
        }
    }
}

Compile and run (all the source in one dir):

javac -cp "$CORE" HnswCodec.java HnswLab.java
java  -cp "$CORE:." --add-modules jdk.incubator.vector -Xmx2g HnswLab

Step 7: Read the table

You will get something shaped like this (your exact numbers vary by machine and seed):

M    efC    efS    recall@10 avg_us/query
8    64     10     0.8120    41.3
8    64     50     0.9460    88.7
8    64     100    0.9710    142.5
8    64     200    0.9850    240.1
16   128    10     0.8740    55.0
16   128    50     0.9760    121.2
16   128    100    0.9900    188.6
16   128    200    0.9960    310.4
32   128    100    0.9950    250.9
32   128    200    0.9985    402.7

Read it like an engineer:

efSearch ↑ → recall ↑ and latency ↑, at fixed graph. The cheapest recall lever; it is query-time, so tune it per query.
M ↑ / efConstruction ↑ → higher recall ceiling and a better-connected graph, but slower indexing (you will notice the build step take longer) and more memory (bigger .vex). These are baked in — to change them you rebuilt the index.
There are diminishing returns: going efSearch 100→200 buys little recall for ~1.7× the latency. The art is finding the knee.
Confirm efSearch raises recall monotonically at fixed M/efConstruction.
Confirm a larger M/efConstruction raises the recall ceiling and slows the build.

Inspect .vec/.vex sizes across M (Lab L1 technique) — .vex grows with M:

for d in hnsw-index-*; do echo "$d:"; find "$d" -name '*.vex' -exec ls -la {} \; ; done

Step 8: Map every knob to OpenSearch k-NN (lucene engine)

The whole point: these are the same parameters a real knn_vector field exposes.

This lab (Lucene)	OpenSearch k-NN (lucene engine)	When set
`Lucene99HnswVectorsFormat(m, …)` → `M`	`method.parameters.m`	Index time (mapping)
`Lucene99HnswVectorsFormat(…, beamWidth)` → `efConstruction`	`method.parameters.ef_construction`	Index time (mapping)
`KnnFloatVectorQuery` beam → `efSearch`	`method.parameters.ef_search` (index/query setting)	Query time
`VectorSimilarityFunction.EUCLIDEAN`	`space_type: l2`	Index time
`KnnFloatVectorField`	`knn_vector` with `engine: lucene`	Index time
recall@k vs brute force	what k-NN benchmarks (#2595) measure	—

The equivalent OpenSearch mapping:

PUT /vectors
{
  "settings": { "index.knn": true },
  "mappings": { "properties": { "vec": {
    "type": "knn_vector", "dimension": 64, "space_type": "l2",
    "method": { "name": "hnsw", "engine": "lucene",
                "parameters": { "m": 16, "ef_construction": 128, "ef_search": 100 } }
  }}}
}

Your table is the recall/latency curve that index would exhibit. Deepen the algorithm comparison (HNSW vs IVF vs PQ, and why faiss adds IVF) in k-NN algorithms, and benchmark a real cluster in Lab K6.

Implementation Requirements / Deliverables

HnswCodec pinning M/efConstruction via Lucene99HnswVectorsFormat.
An indexer that builds one forceMerge(1) segment per (M, efConstruction).
A brute-force exact top-k baseline (ground truth).
An ANN query path using KnnFloatVectorQuery with a tunable efSearch.
A sweep harness producing a recall@k + latency table across M, efConstruction, efSearch.
Observations: efSearch ↑ → recall ↑/latency ↑; bigger M/efConstruction → higher ceiling, slower build, bigger .vex; diminishing returns identified.
A mapping table from each Lucene knob to its OpenSearch k-NN method.parameters equivalent.

Troubleshooting

Symptom	Likely cause	Fix
Recall is ~1.0 everywhere	Corpus too small / `efSearch` already covers it	Raise `N` (e.g. 100k) and `DIM` (e.g. 256/768)
Recall is very low even at high `efSearch`	Similarity mismatch (query vs field) or wrong ground-truth metric	Use the same metric (L2) for brute force and the field
`OutOfMemoryError` during build	Vectors + graph in heap; big `M`/`N`	`-Xmx4g`; smaller `N`/`DIM`; fewer concurrent merges
Latency numbers are noisy/huge on first rows	No JIT warmup	Add a warmup pass before timing; or use JMH
`ClassNotFoundException: Lucene99HnswVectorsFormat`	Wrong/old `lucene-core` jar	Re-resolve `$CORE` from the built checkout
`.vex` size doesn't change with `M`	You compared the same index dir	Each `(M, efC)` writes its own `hnsw-index-*` dir
Slow build at high `efConstruction`	Expected — graph construction cost	That is the index-time cost of recall; note it

Coding Exercises

Each exercise extends HnswLab/HnswCodec and is proven by a number you produce or a test that passes. Keep the deterministic seeds so runs are comparable, and run everything with --add-modules jdk.incubator.vector so distances are SIMD-accelerated.

(warm-up) A multi-layer assertion test. HNSW is a layered graph; prove it. Write a JUnit test (HnswGraphTest.java) that builds an in-memory HNSW graph directly via Lucene's builder rather than through the codec: rg "class HnswGraphBuilder|OnHeapHnswGraph|numLevels" lucene/core/src/java to find the real API on your version (HnswGraphBuilder.create(...), then build(...) returning an OnHeapHnswGraph). Index ~5,000 vectors with M=16 and assert graph.numLevels() > 1, then assert the node count shrinks as you go up a layer (graph.getNodesOnLevel(L) is smaller than level L-1). This makes the "logarithmic layers" claim from the HNSW chapter a passing assertion.
(core) Recall vs efConstruction, isolated. The Step 6 sweep mixes M and efConstruction. Write a focused harness that fixes M=16 and sweeps efConstruction ∈ {16, 32, 64, 128, 256} at a single efSearch, printing a two-column table efConstruction → recall@10. Assert programmatically (not just visually) that recall is non-decreasing as efConstruction rises across your grid (allow a small epsilon for noise). This isolates the index-time-build-quality lever from the rest.
(core) Implement the diversity heuristic and compare. HNSW's neighbor selection uses a diversity heuristic (keep a candidate only if it is closer to the query than to already-selected neighbors) rather than naive top-M. Implement both selection strategies as small standalone methods over a candidate list of (neighborId, distance) plus the pairwise distances: selectNaive (just the M closest) and selectDiverse (the heuristic). Write a unit test on a hand-built tiny set where the two disagree, asserting selectDiverse drops a redundant close-cluster neighbor that selectNaive keeps. Then cross-read Lucene's real implementation (rg "diversit|selectAndLink|RandomVectorScorer" lucene/core/src/java/org/apache/lucene/util/hnsw/) and note in a comment which method yours mirrors.
(core) Measure recall vs efConstruction and the cost. Extend Exercise 2 to also record the index build time (System.nanoTime() around buildIndex) and the resulting .vex file size (Lab L1's find ... -name '*.vex' / dir.fileLength). Produce a four-column table efConstruction → recall@10 → build_ms → vex_bytes. Write one paragraph identifying the knee: the efConstruction past which recall barely moves but build time keeps climbing. This is the index-time half of the trade-off the chapter only describes.
(advanced) A scalar-quantized variant, head-to-head. Add a constructor flag to HnswCodec that selects Lucene99HnswScalarQuantizedVectorsFormat (int8) instead of the float32 Lucene99HnswVectorsFormat — grep for the exact class/constructor on your version (rg "class Lucene.*ScalarQuantized.*VectorsFormat"). Re-run the sweep with both formats at matched M/efConstruction/efSearch and tabulate recall, latency, and .vec size side by side. Assert in a test that the quantized .vec is meaningfully smaller, and report the recall delta. This mirrors OpenSearch k-NN's quantization modes — name the data_type/encoder equivalent.
(advanced) Advanced challenge — a recall/latency report tool with deletions and filtering. Turn the harness into HnswReport: parameterized over N, DIM, M, efConstruction, efSearch grids, emitting a CSV you could plot. Then add the two complications real systems hit: (a) delete 20% of the corpus before querying (IndexWriter.deleteDocuments on the stored id) and re-measure recall — confirm/quantify the recall hit from tombstoned nodes still in the graph; (b) add a pre-filter path using a KnnFloatVectorQuery constructed with a Query filter (grep the constructor on your version) restricting to a subset, and measure how recall and latency change vs unfiltered. Write up which effect is larger. This is the shape of a genuine k-NN benchmark issue (k-NN #2595) — you have built a tiny one.

Issues to Practice On

The HNSW graph and vector formats live in apache/lucene (Apache, on GitHub). Contributing there is a different workflow from OpenSearch: no DCO Signed-off-by, no changelog bot — you build and test with ./gradlew :lucene:core:test, format with ./gradlew tidy, and hand-edit CHANGES.txt. Higher-level k-NN/benchmark behavior lives in opensearch-project/k-NN (which does use DCO). Pick the repo your change actually targets. (Full Lucene mechanics: Lab L4.)

What	Command
Lucene good first issues	`gh issue list --repo apache/lucene --label "good first issue" --state open`
HNSW / vector area (search; labels drift)	`gh issue list --repo apache/lucene --search "hnsw OR vector in:title,body" --state open`
List live labels	`gh label list --repo apache/lucene`
k-NN recall/benchmark	`gh issue list --repo opensearch-project/k-NN --search "recall OR benchmark OR ef_search in:title,body" --state open`
k-NN good first issues	`gh issue list --repo opensearch-project/k-NN --label "good first issue" --state open`

Note: Labels move; confirm with gh label list and pick the live ones. Lucene uses GitHub issues but you'll still see legacy LUCENE-NNNN JIRA keys cited in code and CHANGES.txt.

Representative issue patterns for this subsystem (HNSW / vector formats / recall):

A recall or graph-construction quality issue — e.g. a neighbor-selection or layer-assignment edge case, or a benchmark gap. Approach: reproduce with a small recall harness (you now have one), locate the builder/format via rg "HnswGraphBuilder|diversit|numLevels" lucene/core/src/java/org/apache/lucene/util/hnsw/, make the change, add a deterministic test under .../util/hnsw/, and run ./gradlew :lucene:core:test --tests "*Hnsw*". Vector-format additions follow the Lab L2 round-trip discipline.
(k-NN side, DCO required) a benchmark/recall-reporting gap or a default-parameter discussion. Locate the engine wiring via rg "ef_construction|ef_search|Lucene.*HnswVectorsFormat" src/main/java, change it, add a test, PR with a CHANGELOG entry and git commit -s.

Planted-bug drill. In annTopK, change Math.max(k, efSearch) to plain k (so the beam never widens past k). Re-run the sweep and watch recall flatten — raising efSearch no longer helps, because you severed the lever. Confirm your Exercise 2 monotonicity assertion now fails. Fix it back, and add a regression assertion: at fixed M/efConstruction, recall(efSearch=200) > recall(efSearch=10) by a real margin. You have written the test that would have caught a silently-disabled efSearch. For the etiquette of taking a fix upstream — claim first, reproduce first; Lucene PRs need a test + CHANGES.txt (no DCO), k-NN PRs need a test + CHANGELOG + git commit -s — see community interaction.

Validation / Self-check

Define recall@k for ANN. What is the denominator, and how did you compute the ground truth?
Which parameters did you set at index time and which at query time? Show where each appears in your code, and explain why changing M forced a rebuild but changing efSearch did not.
From your table, describe the recall/latency effect of doubling efSearch at fixed M. Where is the knee of diminishing returns?
What does raising M/efConstruction buy and cost? Which file grows with M, and how did you verify it?
Why does the brute-force scan have to use the same distance metric as the indexed field for the recall number to mean anything?
Map each of your knobs (M, efConstruction, efSearch, similarity) to the exact OpenSearch knn_vector method.parameters/space_type field.
If a teammate reports "k-NN recall dropped after we lowered ef_search to cut p99 latency," explain the trade-off they hit using your data.

When your table shows recall climbing with efSearch and you can name the OpenSearch equivalent of every knob, you understand ANN tuning from the inside. Next, learn to give that knowledge back: Lab L4: Contribute to Apache Lucene.

Open-Source Engineer & Contributor