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

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