Lab VI1: HNSW Graph Construction

Background

The intensive walked the HNSW insertion algorithm line by line: the geometric level draw, greedy descent from the entry point, the per-layer efConstruction beam, the diversity neighbour-selection heuristic, the entry-point update. This lab makes you build a real graph with Lucene's own classes and then look inside it — count the levels, read a node's neighbour list, find the entry node — using the HnswGraph reader API. Then you sweep M / efConstruction / efSearch and tabulate recall@k vs brute force, build time, and graph size, turning the intensive's prose trade-offs into numbers you measured yourself.

You will use Lucene directly — no OpenSearch build in the way. Everything you observe maps straight onto the k-NN lucene engine's m / ef_construction / ef_search (the k-NN algorithms chapter gives the exact name mapping), because the k-NN lucene engine is these classes.

Why This Matters for Contributors

When someone files "k-NN recall dropped after we lowered m to save memory," or "vector indexing got slow when we raised ef_construction," the answer lives in the construction algorithm — the beam width, the edge caps, the diversity pruning. To triage or fix that, you need to have felt the recall/latency/memory surface these parameters trace out, and to be able to read HnswGraphBuilder / OnHeapHnswGraph and know what each field is. This lab is that on a tight, OpenSearch-free feedback loop. The recall harness you build here is the same shape as the one you'd attach to a real recall regression.

Prerequisites

• Java 21+ (java -version).
• A Lucene core jar on the classpath. Two easy ways: - From an apache/lucene checkout: ./gradlew :lucene:core:jar, then find it under lucene/core/build/libs/. - From an OpenSearch checkout, the Lucene jars are already downloaded: find ~/.gradle -name 'lucene-core-*.jar' | head.
• You've read the intensive Part 1 (HNSW construction) — the diversity heuristic and the M0 = 2·M cap especially.

# Pin the jar once so the snippets below just work:
export LUCENE_CORE=$(find ~/.gradle -name 'lucene-core-*.jar' 2>/dev/null | sort | tail -1)
echo "$LUCENE_CORE"          # should print a path; if empty, build the jar (above)

Note: Lucene's HnswGraphBuilder is in the org.apache.lucene.util.hnsw package and some of its constructors/factory methods are package-private or shift between minor versions. This lab uses the stable public path — index with KnnFloatVectorField + Lucene99HnswVectorsFormat, then read the graph back with the public HnswGraph API exposed by the codec reader. The stretch goal drives HnswGraphBuilder directly. Grep your version to confirm method names: grep -rn "public.*HnswGraphBuilder\|static.*create" lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java.

Step-by-Step Tasks

Step 1 — Read the real builder first

Before you build anything, read the four mechanisms from the intensive in the actual source:

cd ~/src/lucene      # an apache/lucene checkout
B=lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
# (1) the level draw — find the normalization constant mL = 1/ln(M):
grep -n "Math.log\|getRandomGraphLevel\|randomLevel\|ml\b" "$B"
# (2) insertion — descent + beam + link:
grep -n "addGraphNode\|searchLevel\|beamWidth\|entryNode" "$B"
# (3) the diversity heuristic — candidate compared to already-selected neighbours:
grep -rn "diversit\|isDiverse\|selectAndLink\|checkDiverse" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/
# (4) the layer-0 double cap M0 = 2*M:
grep -rn "M0\|maxConn\|2 \* M" lucene/core/src/java/org/apache/lucene/util/hnsw/

In your notes: which line draws the level, and which method decides whether a candidate becomes a neighbour? You will recognise these as the code behind the numbers you measure below.

Step 2 — Generate synthetic clustered vectors

Real embeddings are clustered, not uniform — that is what makes the diversity heuristic matter. Generate N vectors in C Gaussian blobs so brute-force recall is a meaningful target.

// Vectors.java — synthetic clustered data + a deterministic seed.
import java.util.*;

public final class Vectors {
  public static float[][] clustered(int n, int dim, int clusters, long seed) {
    Random rnd = new Random(seed);
    float[][] centers = new float[clusters][dim];
    for (float[] c : centers) for (int d = 0; d < dim; d++) c[d] = rnd.nextFloat() * 10f;
    float[][] out = new float[n][dim];
    for (int i = 0; i < n; i++) {
      float[] c = centers[rnd.nextInt(clusters)];
      for (int d = 0; d < dim; d++) out[i][d] = c[d] + (float) rnd.nextGaussian();
    }
    return out;
  }

  // Squared L2 — the same order as Lucene's EUCLIDEAN before its score transform.
  public static double l2(float[] a, float[] b) {
    double s = 0; for (int i = 0; i < a.length; i++) { double d = a[i] - b[i]; s += d * d; }
    return s;
  }

  // Brute-force exact top-k by ascending L2 (the ground truth recall is measured against).
  public static int[] exactTopK(float[][] data, float[] q, int k) {
    Integer[] idx = new Integer[data.length];
    for (int i = 0; i < idx.length; i++) idx[i] = i;
    Arrays.sort(idx, Comparator.comparingDouble(i -> l2(data[i], q)));
    int[] out = new int[k];
    for (int i = 0; i < k; i++) out[i] = idx[i];
    return out;
  }
}

Step 3 — Build a Lucene HNSW index and read the graph back

This is the heart of the lab: index float[] vectors with a configured Lucene99HnswVectorsFormat, then open the segment reader and walk the HnswGraph.

// BuildAndInspect.java
import org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat;
import org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat;
import org.apache.lucene.codecs.KnnVectorsFormat;
import org.apache.lucene.codecs.lucene101.Lucene101Codec;   // codec name varies by version
import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.store.*;
import org.apache.lucene.util.hnsw.HnswGraph;
import org.apache.lucene.codecs.hnsw.HnswGraphProvider;     // exposes getGraph(field)
import java.nio.file.*;

public class BuildAndInspect {
  static final String FIELD = "vec";

  // A codec that forces our M / efConstruction for the vector field.
  static Codec hnswCodec(int m, int efC) {
    KnnVectorsFormat fmt = new Lucene99HnswVectorsFormat(m, efC);   // (maxConn, beamWidth)
    return new Lucene101Codec() {                                   // base codec name varies
      @Override public KnnVectorsFormat getKnnVectorsFormatForField(String f) { return fmt; }
    };
  }

  public static void main(String[] args) throws Exception {
    int n = 5000, dim = 64, m = 16, efC = 100;
    float[][] data = Vectors.clustered(n, dim, 20, 42L);
    Path dir = Paths.get("/tmp/vi1-index");

    try (Directory d = FSDirectory.open(dir)) {
      IndexWriterConfig cfg = new IndexWriterConfig().setCodec(hnswCodec(m, efC));
      long t0 = System.nanoTime();
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        for (int i = 0; i < n; i++) {
          Document doc = new Document();
          doc.add(new KnnFloatVectorField(FIELD, data[i], VectorSimilarityFunction.EUCLIDEAN));
          doc.add(new StoredField("id", i));
          w.addDocument(doc);
        }
        w.forceMerge(1);   // ONE segment -> ONE graph, so inspection is unambiguous
      }
      long buildMs = (System.nanoTime() - t0) / 1_000_000;

      try (DirectoryReader r = DirectoryReader.open(d)) {
        LeafReaderContext leaf = r.leaves().get(0);         // single segment after forceMerge(1)
        CodecReader cr = (CodecReader) leaf.reader();
        HnswGraph g = ((HnswGraphProvider) cr.getVectorReader()).getGraph(FIELD);
        inspect(g, buildMs);
      }
    }
  }

  static void inspect(HnswGraph g, long buildMs) throws Exception {
    System.out.println("build_ms=" + buildMs);
    System.out.println("size(layer0)=" + g.size());
    System.out.println("numLevels=" + g.numLevels());
    System.out.println("entryNode=" + g.entryNode());      // the single top-layer entry point
    // Nodes-per-level: higher layers should be exponentially sparser (~1/M thinning).
    for (int level = g.numLevels() - 1; level >= 0; level--) {
      HnswGraph.NodesIterator it = g.getNodesOnLevel(level);
      System.out.println("level=" + level + " nodes=" + it.size());
    }
    // Dump the neighbour list of the entry node on layer 0 (its edges).
    g.seek(0, g.entryNode());
    StringBuilder nbrs = new StringBuilder();
    for (int nb = g.nextNeighbor(); nb != HnswGraph.NO_MORE_DOCS; nb = g.nextNeighbor())
      nbrs.append(nb).append(' ');
    System.out.println("entry_layer0_neighbors=[" + nbrs.toString().trim() + "]");
  }
}

Note: Class names with a version number — Lucene99HnswVectorsFormat, Lucene101Codec, the getVectorReader() accessor — drift across Lucene releases. If compilation fails on one, grep for the current name: grep -rln "HnswVectorsFormat\|class Lucene.*Codec\|getVectorReader\|interface HnswGraphProvider" lucene/core/src/java. The HnswGraph reader API (numLevels, entryNode, getNodesOnLevel, seek, nextNeighbor) has been stable for many releases.

Compile and run:

javac -cp "$LUCENE_CORE" Vectors.java BuildAndInspect.java
java  -cp ".:$LUCENE_CORE" BuildAndInspect

You should see a handful of levels, an entryNode, level sizes thinning by roughly 1/M per layer, and a neighbour list on layer 0 of up to 2·M ids — the M0 cap from the intensive, observed.

Step 4 — Search the graph and measure recall@k vs brute force

Add a recall harness: run KnnFloatVectorQuery (the lucene engine's query) for a set of held-out queries, compare its top-k against Vectors.exactTopK, and average the overlap.

// Recall.java
import org.apache.lucene.document.KnnFloatVectorField;     // field type re-used
import org.apache.lucene.index.*;
import org.apache.lucene.search.*;
import org.apache.lucene.store.*;
import java.nio.file.*;
import java.util.*;

public class Recall {
  static final String FIELD = "vec";

  // recall@k = avg over queries of |approx_topk ∩ exact_topk| / k
  static double recallAtK(IndexSearcher s, float[][] data, float[][] queries,
                          int k, int efSearch) throws Exception {
    StoredFields sf = s.getIndexReader().storedFields();
    double sum = 0;
    for (float[] q : queries) {
      // efSearch is expressed as the query's k-expansion: ask for max(k, efSearch).
      KnnFloatVectorQuery knn = new KnnFloatVectorQuery(FIELD, q, Math.max(k, efSearch));
      TopDocs td = s.search(knn, Math.max(k, efSearch));
      Set<Integer> approx = new HashSet<>();
      for (int i = 0; i < Math.min(k, td.scoreDocs.length); i++)
        approx.add(Integer.parseInt(sf.document(td.scoreDocs[i].doc).get("id")));
      Set<Integer> exact = new HashSet<>();
      for (int id : Vectors.exactTopK(data, q, k)) exact.add(id);
      approx.retainAll(exact);
      sum += approx.size() / (double) k;
    }
    return sum / queries.length;
  }

  public static void main(String[] args) throws Exception {
    int n = 5000, dim = 64, k = 10, nq = 200;
    float[][] data = Vectors.clustered(n, dim, 20, 42L);
    float[][] queries = Vectors.clustered(nq, dim, 20, 7L);   // different seed = held out
    try (Directory d = FSDirectory.open(Paths.get("/tmp/vi1-index"));
         DirectoryReader r = DirectoryReader.open(d)) {
      IndexSearcher s = new IndexSearcher(r);
      for (int ef : new int[]{10, 25, 50, 100, 200}) {
        long t0 = System.nanoTime();
        double rec = recallAtK(s, data, queries, k, ef);
        long us = (System.nanoTime() - t0) / 1000 / nq;       // microseconds per query
        System.out.printf("efSearch=%-4d recall@%d=%.3f  us/query=%d%n", ef, k, rec, us);
      }
    }
  }
}

javac -cp "$LUCENE_CORE" Vectors.java Recall.java
java  -cp ".:$LUCENE_CORE" Recall

Step 5 — Sweep M / efConstruction / efSearch and tabulate

Rebuild the index for a grid of (m, efConstruction) (run BuildAndInspect with different constants, or loop in a single program), and for each rebuilt index sweep efSearch with Recall. Record build time, graph size on disk (.vex + .vec), and recall@10. The on-disk size:

# After a build, size the vector files (graph = .vex, raw vectors = .vec):
find /tmp/vi1-index -name '*.vex' -o -name '*.vec' | xargs ls -l | awk '{print $5, $9}'
du -sh /tmp/vi1-index

Fill in a table like this with your numbers:

You are reproducing the intensive's trade-off tables empirically: higher m and efConstruction raise build time and .vex size and lift the recall ceiling; higher efSearch lifts recall at a query-latency cost without rebuilding.

Step 6 — Map every knob to the k-NN lucene engine

These Lucene parameters are exactly the k-NN lucene-engine settings. Write the mapping that produces the same graph you just built with m=16, efC=100:

PUT /vi1-products
{
  "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": 100, "ef_search": 100 }
        }
      }
    }
  }
}

See k-NN algorithms § HNSW parameters for the full cross-engine name table and the index-time-vs-query-time split.

Deliverables

• BuildAndInspect output showing numLevels, entryNode, per-level node counts thinning by ~1/M, and an entry-node layer-0 neighbour list of up to 2·M ids.
• A filled recall/latency table from Recall across efSearch ∈ {10,25,50,100,200}.
• The Step-5 sweep table over (m, efConstruction) with build_ms, .vex bytes, and recall@10.
• The k-NN lucene-engine mapping (Step 6) and the param mapping table.

Troubleshooting

Expected Output

build_ms=812
size(layer0)=5000
numLevels=4
entryNode=3187
level=3 nodes=2
level=2 nodes=38
level=1 nodes=611
level=0 nodes=5000
entry_layer0_neighbors=[... up to 32 ids ...]

efSearch=10   recall@10=0.71  us/query=41
efSearch=25   recall@10=0.86  us/query=63
efSearch=50   recall@10=0.94  us/query=95
efSearch=100  recall@10=0.98  us/query=150
efSearch=200  recall@10=0.99  us/query=260

Exact numbers depend on data, seed, JVM, and Lucene version. What must hold: levels thin by ~1/M, layer 0 has all n nodes, the entry-node layer-0 neighbour list is ≤ 2·M, and recall climbs monotonically with efSearch while latency rises.

Stretch Goals

• Drive HnswGraphBuilder directly. Skip the codec and build an OnHeapHnswGraph straight from a RandomVectorScorerSupplier + HnswGraphBuilder.create(...). Grep the current factory signature first; this is the lowest-level public path and the one most exposed to version drift.
• Break the diversity heuristic. In a hand-rolled builder (or by reasoning about the source), keep the nearest-M instead of running the diversity predicate, and show recall on clustered/OOD queries falls off a cliff while easy-query recall looks fine. This is the intensive's §1.3 recall-cliff bug, reproduced.
• Vary the entry-point seed. Confirm the graph is seed-deterministic (same seed → identical entryNode and neighbour lists), then show a different seed yields a different but equal-recall graph.
• Filtered ANN. Add a Query filter to KnnFloatVectorQuery and observe how recall and latency change when the filter is selective — the lucene engine's headline feature (Lucene chapter).

Coding Exercises

These turn the graph you inspected into code that asserts HNSW invariants and probes the construction algorithm. Each produces a runnable artifact, not a note.

1. (warm-up) Assert the M0 = 2·M cap in a JUnit test. Wrap the Step-3 build in a JUnit/OpenSearchTestCase-style test (junit on the classpath, or plain assert-driven main if you have no test runner). For every node, seek(0, node) and count neighbours via nextNeighbor(); assert each layer-0 degree is <= 2*m and each higher-layer degree is <= m. Confirm by running with m=8 and m=32 — the bound must track m. This is the cap you read in Step 1 (grep "M0\|maxConn"), now machine-checked.

2. (warm-up) Assert the ~1/M level thinning. Add a test that walks getNodesOnLevel(level) for every level and asserts the count at level L+1 is no more than (2.0/m) times the count at level L (a loose bound that holds despite randomness; tighten it with averaging over seeds). Print the ratios. Tie the number you assert to the mL = 1/ln(M) constant you located in HnswGraphBuilder (Step 1) and to the geometry in vector-math foundations.

3. (core) A reusable recall harness as a graded method. Refactor Recall.recallAtK into a method double sweep(int[] efSearch, double minRecallAt(int idx)) and write a JUnit test asserting recall@10 is monotonically non-decreasing in efSearch and that efSearch=200 clears 0.9 on your clustered data. Monotonicity is the property a recall regression breaks; this is the test shape you'd attach to a real one.

4. (core) Drive HnswGraphBuilder directly and diff against the codec graph. Replace the codec path with HnswGraphBuilder.create(scorerSupplier, m, efC, seed) over a RandomVectorScorerSupplier (grep the current factory signature first: grep -n "static.*create\|RandomVectorScorerSupplier" .../hnsw/HnswGraphBuilder.java). Build with the same seed as your codec build and write a test asserting both graphs have identical numLevels() and entryNode(). This proves the codec is just a wrapper over the builder you read in Step 1.

5. (advanced) Instrument the diversity heuristic and prove the recall cliff. As a small patch, add a counter to the neighbour-selection path (the diversit/isDiverse/ selectAndLink method you found in Step 1) that records how many candidates the diversity predicate rejected per insertion; surface it through a test-only static. Then build a second variant that keeps the nearest-M (skip the predicate) and write a JUnit test asserting that on out-of-distribution / clustered queries the diverse graph's recall@10 beats the nearest-M graph's by a margin, while on easy uniform queries they tie. You have now reproduced — and measured — the intensive's §1.3 recall-cliff, deepening Stretch Goal 2.

6. (advanced challenge) A recall-frontier automation harness. Write a single standalone Java program Frontier.java that loops the full (m, efConstruction) grid from Step 5, rebuilds the index each time into a temp dir, sweeps efSearch, and emits a CSV (m,ef_construction,ef_search,build_ms,vex_bytes,recall@10,us_per_query) — sizing .vex with Files.size over the segment files, not a shell du. Add a JUnit assertion that for fixed efSearch, recall@10 is non-decreasing in m. Feed the CSV into Lab VI4's viz2_frontier.py to plot your Java engine's real frontier. This is a genuine recall-regression rig: parameterized, reproducible, plotted.

Issues to Practice On

The lucene k-NN engine is these classes, so HNSW-construction issues land in the k-NN repo (mapper/engine wiring) and upstream in Lucene (the builder itself). Start here:

Labels drift — list and pick (gh label list --repo opensearch-project/k-NN). k-NN commonly uses good first issue, bug, enhancement, Roadmap.

Representative issue patterns. (1) "Recall dropped after we lowered m / raised ef_construction" — reproduce with the harness from Exercise 3/6 at the reporter's params, rg the param plumbing from the mapping down to Lucene99HnswVectorsFormat constructor args (grep -rn "ef_construction\|KNNMethodContext\|maxConnections" src/main/java), confirm whether the regression is in OpenSearch's wiring or upstream in HnswGraphBuilder, and ship a test that pins the recall floor. (2) "Graph build is slow / OOMs at high ef_construction" — profile build_ms vs ef_construction with Exercise 6's CSV, then locate the beam-width allocation in the builder. Both demand a recall-or-timing assertion, never a screenshot.

Planted-bug exercise. In your direct-builder variant from Exercise 4 (or by patching a local Lucene checkout), change the layer-0 cap from 2*M to plain M in the addGraphNode/maxConn path you found in Step 1. Rebuild and run Exercise 1's degree test: it goes red where a layer-0 node now exceeds... nothing — the cap test still passes (it only checks <= 2*M), but your recall test (Exercise 3) drops because each node lost half its edges. That asymmetry is the lesson: a tighter cap silently degrades recall while structural bounds still hold, so only a recall assertion catches it. Restore 2*M, then add the recall floor assertion that would have caught it.

Etiquette. Claim an issue before working it, reproduce first, and every PR needs a regression test, a CHANGELOG.md entry, and a DCO sign-off (git commit -s). See community interaction.

Validation / Self-check

1. From your BuildAndInspect output, compute the observed thinning ratio between layer 1 and layer 0. Does it match ~1/M? Why is layer 0 the only layer with all n nodes?
2. Your entry node's layer-0 neighbour list — is it ≤ 2·M? Explain M0 = 2·M from the intensive and why layer 0 gets the double cap.
3. Plot (or describe) the recall@10-vs-efSearch curve. Where does it flatten, and what does increasing efSearch past that point cost for no recall gain?
4. From the Step-5 sweep: which parameter raised the recall ceiling, and which lets you trade latency for recall without rebuilding? Tie each to index-time vs query-time from the k-NN algorithms chapter.
5. Translate m=32, ef_construction=200 to the exact Lucene99HnswVectorsFormat constructor arguments and the k-NN method.parameters block.

When this all holds, move to Lab VI2: Faiss Index Types and JNI to see the other engine — native C++ — build IVF and PQ over these same vectors, then to Lab VI3: The Quantization Math to compress the vectors the graph stores. For the algorithm theory, re-read the intensive Part 1.