HNSW Vector Search in Lucene

Everything you know about Lucene so far — the inverted index, BKD trees, columnar DocValues — answers a lexical question: "which documents contain this term, this number, this range?" Vector search answers a semantic one: "which documents are nearest to this point in a high-dimensional space?" An embedding model turns text or an image into a float[] of, say, 768 or 1024 dimensions; two vectors that are close (by cosine or Euclidean distance) mean two things that are semantically similar. The problem is that an exact nearest-neighbour scan over millions of 768-dim vectors is a brute-force O(N·d) dot-product per query — too slow for interactive search.

The answer Lucene ships is HNSW — a Hierarchical Navigable Small World graph — an approximate nearest-neighbour (ANN) index that finds the k nearest vectors in roughly O(log N) distance computations instead of O(N). This chapter covers the HNSW algorithm itself (layers, greedy search, the M / efConstruction / efSearch knobs), the concrete org.apache.lucene.* classes that implement it, the on-disk vector format and its scalar-quantized variants, how it integrates with merges, and exactly how OpenSearch's k-NN lucene engine reuses all of it.

After this chapter you should be able to: explain what an HNSW graph is and why greedy search over it is fast; name the Lucene classes that build, store, and query it; map the .vec/.vex/.vem files to a chapter concept; reason about the recall/latency/memory trade-offs the parameters control; and connect a Lucene HNSW concept to the OpenSearch k-NN setting that exposes it.

Note: This is the Lucene layer. OpenSearch's k-NN plugin has three engines — faiss (default, native C++), lucene (this chapter), and the deprecated nmslib. Only the lucene engine uses the classes below; faiss writes its own graph into a custom codec. See the k-NN engines chapter for the full comparison.

Why approximate? The cost of exact nearest-neighbour

Exact k-NN ("flat" or "brute-force" search) computes the distance from the query vector to every stored vector and keeps the best k. For N documents of dimension d, that is N·d multiply-adds per query. At N = 10M, d = 768, a single query is ~7.7 billion float operations — even with SIMD that is tens of milliseconds per shard per query, and it scales linearly with the corpus. Exact search is correct but does not scale.

ANN trades a small, bounded loss of recall (the fraction of the true top-k you actually return) for a large gain in speed. HNSW is the dominant ANN structure in production search because it has high recall at low latency, supports incremental insertion (important for a mutable index), and — critically for Lucene — can be persisted to immutable segment files and merged.

The HNSW algorithm

HNSW is a proximity graph: each vector is a node, and edges connect a node to a bounded number of its near neighbours. Searching means walking the graph greedily toward the query. The "hierarchical" part is the trick that makes the walk start close: the graph is built in layers, like a skip list for geometry.

Layers

• Layer 0 contains every node and is densely connected — it is the fine-grained graph.
• Each higher layer contains a random, exponentially smaller subset of nodes (a node's top layer is drawn from a geometric distribution). The top layer might have a handful of nodes; layer 0 has all of them.
• Higher layers are the "express lanes": long-range hops that get the search into the right neighbourhood quickly before it descends to the dense bottom layer for the precise finish.

flowchart TD
    subgraph L2["Layer 2 (sparse, long hops)"]
      A2((entry))
    end
    subgraph L1["Layer 1"]
      A1((n)) --- B1((n)) --- C1((n))
    end
    subgraph L0["Layer 0 (all nodes, dense)"]
      A0((n)) --- B0((n)) --- C0((n)) --- D0((n)) --- E0((n))
    end
    A2 -->|descend| B1
    C1 -->|descend| C0

Greedy search

A k-NN query enters at the single entry point on the top layer and runs a greedy best-first search:

1. At the current layer, look at the current node's neighbours, compute each one's distance to the query, and move to the closest neighbour that improves on the current best. Repeat until no neighbour is closer — a local minimum for this layer.
2. Drop down one layer (same node) and repeat. Higher layers are sparse, so each is a few hops.
3. At layer 0, run a wider search: maintain a candidate set of size efSearch (a priority queue), expanding the closest unexpanded candidate and tracking the best k found so far. A larger efSearch explores more of the graph → higher recall, more distance computations.

flowchart LR
    Q["query vector"] --> Entry["entry point, top layer"]
    Entry --> G1["greedy hop to local min (layer 2)"]
    G1 --> Down1["descend to layer 1"]
    Down1 --> G2["greedy hop to local min"]
    G2 --> Down0["descend to layer 0"]
    Down0 --> Beam["beam search, candidate set size = efSearch"]
    Beam --> Top["return best k by distance"]

The number of distance computations is dominated by the layer-0 beam, which is bounded by efSearch · M rather than N — that is where the O(log N)-ish behaviour comes from.

Construction and the parameters

Insertion mirrors search: to add a node, find its nearest neighbours at each layer (a search with beam width efConstruction), then connect it to up to M of them, pruning each neighbour's edge list back down to M (a heuristic that keeps the graph diverse, not just locally clustered). The three knobs you will tune everywhere — in Lucene and in OpenSearch — are:

Note: M and efConstruction are baked into the graph at index time — you cannot change them without reindexing/rebuilding the graph. efSearch is a query-time knob. This asymmetry matters: pick M/efConstruction conservatively-high, and tune efSearch per query for the recall/latency you need.

The Lucene classes

Lucene's vector support lives under org.apache.lucene.codecs.* (format/IO), org.apache.lucene.util.hnsw.* (the graph), org.apache.lucene.document.* (the field), and org.apache.lucene.search.* (the query). Grep the version you are on — names are stable but the codec version number moves:

# In an apache/lucene checkout:
find lucene -name "KnnFloatVectorField.java" -o -name "HnswGraph*.java" \
  -o -name "*HnswVectorsFormat.java" -o -name "VectorSimilarityFunction.java"
grep -rln "class HnswGraphBuilder" lucene/core/src/java
grep -rln "Lucene9.*HnswVectorsFormat\|Lucene10.*ScalarQuantized" lucene/core/src/java

Fields: what you put in a document

// Indexing a float vector into a document.
float[] embedding = embed("the quick brown fox");          // e.g. 768 dims from a model
Document doc = new Document();
doc.add(new KnnFloatVectorField("vector", embedding, VectorSimilarityFunction.COSINE));
doc.add(new StoredField("id", docId));
writer.addDocument(doc);

VectorSimilarityFunction is the single most consequential choice after dimension. It is fixed per field at index time and the query must use the same one:

The graph: HnswGraph and HnswGraphBuilder

HnswGraph is the abstract in-memory/on-disk graph: given a node and a level, iterate its neighbours. HnswGraphBuilder constructs it — it is the code that runs the insertion-with-pruning described above, parameterized by M and beamWidth (== efConstruction). At search time HnswGraphSearcher runs the greedy + beam traversal, collecting results into a KnnCollector/NeighborQueue bounded by efSearch.

grep -n "beamWidth\|maxConn\|M\b\|addGraphNode\|class HnswGraphBuilder" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java | head
grep -n "search\|EntryPoint\|class HnswGraphSearcher" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java | head

The query: KnnFloatVectorQuery

// Search for the 10 nearest neighbours of queryVector in field "vector".
Query knn = new KnnFloatVectorQuery("vector", queryVector, 10);
TopDocs hits = searcher.search(knn, 10);

KnnFloatVectorQuery (and KnnByteVectorQuery) is a two-phase query: per segment it runs the HNSW search to get k approximate neighbours, then rewrites into the equivalent of a doc-id + score list that the rest of Lucene's collector machinery consumes. It also accepts a filter Query — the lucene engine's headline feature — which restricts the candidate set so the graph walk only returns docs matching the filter (Lucene applies the filter during traversal, falling back to exact search if the filter is very selective). Compare this with the faiss engine, where pre-/post-filtering is handled differently; see the k-NN query path.

The vector format and the files on disk

Like every other Lucene data structure, vectors are written by a codec component — a KnnVectorsFormat. The format owns three file extensions:

# After indexing vectors, find them on disk (mnemonic: vec=values, vex=graph, vem=meta):
find /path/to/index -name "*.vec" -o -name "*.vex" -o -name "*.vem"

The format classes

Lucene99HnswVectorsFormat is the baseline HNSW format (full-precision float32 vectors + the graph). Storing raw float32 is expensive: 768 dims × 4 bytes = 3 KB per vector, and the working set must be in memory (or page cache) for fast search. Scalar quantization shrinks each component to fewer bits, trading a little recall for a large memory cut:

Scalar quantization for vectors entered Lucene with the int8 work in LUCENE-10577 / apache/lucene #11613, and the scalar-quantized codec format landed in apache/lucene #12497. The newer Lucene104* formats generalize the bit width (1/2/4/7/8 bits) so you can dial memory vs recall much more finely. To see which codec/format your Lucene version defaults to:

grep -rln "Lucene9.*HnswVectorsFormat\|Lucene10.*HnswScalarQuantized" lucene/core/src/java
grep -n "knnVectorsFormat\|getKnnVectorsFormatForField" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/Lucene*Codec.java

You select a non-default vector format per field by overriding getKnnVectorsFormatForField in a custom codec — exactly the technique Lab L2 builds, and exactly how OpenSearch's k-NN plugin injects its own format.

Note: Quantization is lossy. The standard production pattern is: search the quantized graph to get a candidate set quickly, then rescore those candidates against the full-precision vectors for the final ranking. OpenSearch's disk-based ANN does exactly this; see quantization and disk-ANN.

HNSW and merges: the graph is rebuilt

Here is the part that connects vectors to the rest of Lucene. Segments are immutable (segments and codecs), and so is the HNSW graph inside a segment. When merges combine N segments into one, the merged segment needs a single graph covering all the surviving documents — and you cannot simply concatenate the old graphs, because their node ordinals and neighbour edges are local to each old segment.

So merge rebuilds the HNSW graph for the merged segment. The naive approach re-inserts every vector from scratch (expensive — graph construction is the dominant cost of a vector merge). Lucene's optimization, IncrementalHnswGraphMerger, seeds the new graph from the largest input segment's existing graph and only inserts the vectors from the smaller segments, which cuts merge cost substantially. This is also where the SIMD story pays off: faster distance computations make both construction and merge faster, contributing to the ~25% indexing speedups Lucene reported.

flowchart TD
    S1["segment A: vectors + graph A"] --> M["merge"]
    S2["segment B: vectors + graph B"] --> M
    S3["segment C: vectors + graph C"] --> M
    M --> Seed["IncrementalHnswGraphMerger: seed from largest graph"]
    Seed --> Insert["insert remaining vectors (HnswGraphBuilder)"]
    Insert --> New["merged segment: ONE rebuilt graph + concatenated .vec"]

Practical consequence: vector-heavy indices have expensive merges. A big force-merge of a vector index re-builds the whole graph and can run for a long time and use a lot of CPU/heap. This is why vector indexing throughput is so sensitive to merge policy and why remote/GPU index-build RFCs exist on the OpenSearch side (see the k-NN architecture and the GPU/remote-build RFCs).

# Watch a vector merge rebuild the graph: index vectors, force-merge, observe .vex churn.
grep -rln "IncrementalHnswGraphMerger\|class .*VectorsWriter" lucene/core/src/java

How OpenSearch's k-NN lucene engine uses exactly this

OpenSearch's k-NN plugin's lucene engine is not a reimplementation — it is a thin mapping onto the classes above. When you create a knn_vector field with engine: lucene:

PUT /products
{
  "settings": { "index.knn": true },
  "mappings": {
    "properties": {
      "embedding": {
        "type": "knn_vector",
        "dimension": 768,
        "space_type": "cosinesimil",
        "method": {
          "name": "hnsw",
          "engine": "lucene",
          "parameters": { "m": 16, "ef_construction": 128 }
        }
      }
    }
  }
}

maps onto Lucene as follows:

The lucene engine's two big advantages over faiss/nmslib are that the vectors live inside the JVM/Lucene segment files (no separate native memory pool, no circuit breaker to manage) and that filtered search is first-class. Its disadvantage is that for the very largest, highest-throughput workloads the native faiss engine can be faster and offers IVF/PQ. The full trade-off table is in the k-NN engines chapter; the algorithm details (HNSW vs IVF vs PQ) are in k-NN algorithms.

Note: Because the lucene engine is Lucene HNSW, a bug or improvement in Lucene's HNSW (e.g. a new quantization format, a faster merger) flows into OpenSearch the moment OpenSearch upgrades its bundled Lucene. This is the upstream-first dynamic that Lab L4 is about: some vector work must land in Lucene before OpenSearch can expose it.

Reading exercise

# In an apache/lucene checkout:

# 1. The graph builder — find M (maxConn) and beamWidth (efConstruction).
grep -n "maxConn\|beamWidth\|addGraphNode" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java

# 2. The searcher — find the entry-point descent and the layer-0 beam.
grep -n "graphSearch\|findBestEntryPoint\|class HnswGraphSearcher" \
  lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java

# 3. The similarity functions.
grep -n "EUCLIDEAN\|DOT_PRODUCT\|COSINE\|MAXIMUM_INNER_PRODUCT" \
  lucene/core/src/java/org/apache/lucene/index/VectorSimilarityFunction.java

# 4. The default codec's vector format.
grep -rn "knnVectorsFormat\|HnswVectorsFormat" \
  lucene/core/src/java/org/apache/lucene/codecs/lucene*/Lucene*Codec.java | head

# 5. The merger that rebuilds the graph.
grep -rln "IncrementalHnswGraphMerger" lucene/core/src/java

Answer:

1. What does the hierarchical part of HNSW buy you over a single flat proximity graph? Describe the role of the top layers vs layer 0.
2. Walk a greedy HNSW search from entry point to the final top-k. Where does efSearch enter, and what does increasing it cost and buy?
3. Which two parameters are fixed at index time and which is a query-time knob? Why does that distinction matter operationally?
4. Map each of .vec, .vex, .vem to what it stores. Which one grows with M?
5. Why must a merge rebuild the HNSW graph rather than concatenate the inputs' graphs? What does IncrementalHnswGraphMerger optimize?
6. Translate this OpenSearch field config to its Lucene equivalents: engine: lucene, space_type: innerproduct, m: 32, ef_construction: 256.

Common bugs and symptoms

Validation: prove you understand this

1. Draw the HNSW layered graph and trace a single query through it, marking where the greedy descent ends and the layer-0 beam begins. Label where efSearch controls the search.
2. Explain in one paragraph why HNSW is ~O(log N) while flat search is O(N), and what recall you give up to get there.
3. List the three tuning parameters, say which are index-time vs query-time, and state the recall/latency/memory effect of raising each.
4. Name the Lucene classes for: the field you index, the per-segment reader of vectors, the graph, the graph builder, and the query. Map each .vec/.vex/.vem file to one of them.
5. Explain why a merge rebuilds the graph, and what makes vector merges expensive.
6. Given an OpenSearch knn_vector field with engine: lucene, name the exact Lucene VectorSimilarityFunction, M, and beamWidth it produces, and one capability the lucene engine has that the faiss engine handles differently.

When you can do all six, continue to SIMD and the Panama Vector API — the hot loop inside every distance computation HNSW makes — and then build a real HNSW index in Lab L3. For the plugin layer on top, read the k-NN engines chapter.