Algorithms: HNSW, IVF, and PQ

The k-NN plugin does not invent its own approximate-nearest-neighbour (ANN) math. It exposes a small set of well-known algorithms — HNSW (a layered proximity graph), IVF (an inverted file over coarse cluster centroids), and PQ (product quantization, a compression scheme) — and wires them to OpenSearch mappings and queries. Which algorithms you can use depends on which engine you pick: faiss offers HNSW and IVF, optionally combined with PQ; lucene offers HNSW (this is literally Lucene's HNSW); the deprecated nmslib offers HNSW only.

This chapter is the algorithm layer. It explains each structure at the depth a contributor needs to reason about a recall regression, a memory blow-up, or a mapping-validation bug — the math, the parameters, the trade-offs, and how each is surfaced through the method mapping object. It assumes you have read the k-NN architecture and engines chapters and the Lucene HNSW chapter; it does not re-derive HNSW's layered graph, it builds on it.

After this chapter you can:

• Explain HNSW, IVF, and PQ each in terms of what they index, what they store, and the one trade-off each makes.
• Map every method.parameters knob to its effect on recall, latency, and memory.
• Say which algorithms require training (_train API + model system index) and why, and which are train-free.
• Read a knn_vector mapping and predict the index structure and resource cost it produces.

Note on terminology: the term cluster manager (formerly master) is the node that owns cluster state. It matters here because the _train API and the .opensearch-knn-models system index are cluster-state-coordinated, not shard-local; more on that below.

The three algorithms at a glance

The mental model: HNSW and IVF are indexing structures that decide which vectors you compare against; PQ is a compression layer that decides how cheaply you store and compare each vector. They compose — faiss lets you build HNSW+PQ or IVF+PQ. The selection happens entirely through the method object in the knn_vector field mapping.

# In a k-NN checkout, the method/engine/algorithm abstraction lives here:
grep -rln "class KNNMethod\|enum KNNEngine\|class MethodComponent\|class SpaceType" \
  src/main/java/org/opensearch/knn
grep -rn "METHOD_HNSW\|METHOD_IVF\|ENCODER_PQ\|ENCODER_SQ\|ENCODER_FLAT" \
  src/main/java/org/opensearch/knn/common/KNNConstants.java

HNSW — the layered proximity graph

HNSW is covered in depth at the Lucene layer in HNSW Vector Search in Lucene; read that first. The short version: each vector is a node; edges connect a node to up to M near neighbours; the graph is built in layers (a skip-list-for-geometry), so a greedy walk starts with long hops on sparse top layers and finishes with a wide beam search on the dense bottom layer. Search is roughly O(log N) distance computations instead of the O(N) of an exact scan.

What matters here is how k-NN exposes HNSW's three knobs across engines, because the parameter names differ between the OpenSearch mapping, faiss, and Lucene.

The HNSW parameters

The index-time vs query-time split is the single most important operational fact about HNSW. m and ef_construction are baked into the graph — changing them means reindexing. ef_search is a per-query (or per-index-setting) dial you can move freely. The standard advice: pick m/ef_construction conservatively-high at index time, then tune ef_search to hit your recall/latency target.

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

flowchart TD
    Q["query vector"] --> E["entry point, top layer"]
    E --> H1["greedy hops on sparse layers (long-range)"]
    H1 --> D["descend to layer 0 (all nodes, dense)"]
    D --> B["beam search, width = ef_search"]
    B --> K["top-k by distance"]
    subgraph mem["what HNSW stores per node"]
      direction LR
      V["the vector (or its PQ code)"] --- N["up to m neighbour ids per layer"]
    end

HNSW memory: why graphs are big

HNSW stores the full graph in memory for fast traversal. The rough cost per vector is the vector itself (dimension × 4 bytes for float32) plus the neighbour lists (~m × 2 ids on layer 0, fewer above). At d=768, m=16, a million vectors is on the order of ~3 GB of vectors + a few hundred MB of graph — all of which the faiss/nmslib engines load into native memory outside the JVM heap (see native integration and memory). This is why HNSW's headline trade-off is memory: you pay RAM to keep the graph resident. PQ (below) is the answer when that RAM cost is unacceptable.

Note: HNSW is train-free. You can start indexing immediately — the graph is built incrementally as documents arrive. This is a major operational advantage over IVF/PQ, which need a training pass before they can index anything.

IVF — the inverted file

IVF (Inverted File index) attacks the O(N) scan from a different angle than HNSW. Instead of a graph, it partitions the vector space into nlist cells. Each cell is defined by a centroid (a representative vector), and every indexed vector is assigned to its nearest centroid's posting list. At query time you do not search all cells — you find the nprobes centroids closest to the query and only scan the vectors in those cells.

flowchart LR
    subgraph train["training (offline, on a sample)"]
      S["sample of vectors"] --> KM["k-means -> nlist centroids"]
    end
    subgraph index["indexing"]
      V["incoming vector"] --> A["assign to nearest centroid"]
      A --> P["append to that centroid's posting list"]
    end
    subgraph query["query time"]
      Q["query vector"] --> CQ["coarse quantizer: nearest nprobes centroids"]
      CQ --> SC["scan only those nprobes posting lists"]
      SC --> TK["top-k"]
    end
    KM -.centroids.-> A
    KM -.centroids.-> CQ

The IVF math

• Coarse quantizer: a function q(x) mapping a vector x to the index of its nearest centroid. The centroids {c_1, …, c_nlist} are learned by k-means over a training sample.
• Cells (Voronoi regions): each centroid owns the region of space closer to it than any other centroid. Posting list L_i holds every indexed vector assigned to c_i.
• Search: compute distances from the query to all nlist centroids (cheap if nlist ≪ N), pick the nprobes nearest, and do an exact scan over the ~N·nprobes/nlist vectors in those cells. Distance computations per query are nlist (centroid pass) + ~N·nprobes/nlist (cell scan), versus N for a flat scan.

The recall trade-off is structural: a true nearest neighbour can sit in a cell whose centroid is not among the nprobes you searched (it lives near a Voronoi boundary). Raising nprobes searches more cells → higher recall, more work. Raising nlist makes cells smaller (less work per cell) but increases the chance a neighbour is in an unsearched cell (you need more nprobes to compensate).

The IVF parameters

PUT /products-ivf
{
  "settings": { "index.knn": true },
  "mappings": {
    "properties": {
      "embedding": {
        "type": "knn_vector",
        "dimension": 768,
        "space_type": "l2",
        "method": {
          "name": "ivf",
          "engine": "faiss",
          "parameters": {
            "nlist": 4096,
            "nprobes": 8
          }
        }
      }
    }
  }
}

Warning: IVF is faiss-only and requires training — the centroids must be learned before any vector can be assigned to a cell. You cannot create a usable IVF field by mapping alone; you must train a model first (see Training, below) and reference it via model_id. The mapping above is the conceptual shape; the trained-model workflow is the real path.

HNSW vs IVF — when to reach for which

The rough rule: default to HNSW; reach for IVF when the corpus is so large that the HNSW graph's memory is the binding constraint, and you can tolerate running a training step. IVF also composes especially naturally with PQ (IVF+PQ), which is the classic faiss recipe for billion-scale, memory-bounded search.

PQ — product quantization

PQ is not an index structure — it is a compression scheme that sits underneath HNSW or IVF. Its job is to shrink the per-vector storage from dimension × 4 bytes (float32) down to a handful of bytes, at the cost of representing each vector approximately.

The PQ math

Split each d-dimensional vector into m contiguous sub-vectors of length d/m. For each sub-vector position, run k-means over the training sample to learn a codebook of 2^nbits centroids (typically nbits=8 → 256 centroids per sub-space). Now any vector is encoded by replacing each of its m sub-vectors with the id of the nearest centroid in that sub-space's codebook:

original:   [ ----------------- d floats (d*4 bytes) ----------------- ]
split:      [ sub_1 ][ sub_2 ] ... [ sub_m ]          (each d/m floats)
encode:     [ id_1  ][ id_2  ] ... [ id_m  ]          (each nbits, e.g. 8 bits)
stored as:  m bytes  (when nbits=8)  instead of  d*4 bytes

At d=768, m=96, nbits=8: a vector goes from 768×4 = 3072 bytes to 96 bytes — a 32× reduction. Distances are then computed approximately, between the reconstructed (codebook-centroid) representations, using precomputed lookup tables so the per-distance cost is small.

flowchart LR
    V["vector d=768"] --> SP["split into m=96 sub-vectors of length 8"]
    SP --> CB["per-position codebook (256 centroids each)"]
    CB --> ENC["encode: nearest centroid id per sub-vector"]
    ENC --> CODE["96-byte code (vs 3072-byte float32)"]
    CODE --> AD["approximate distance via lookup tables"]

The PQ parameters

Warning: PQ's m is not HNSW's m. PQ m is the sub-vector count (must divide dimension); HNSW m is the graph's max edges per node. They live in different parameters/encoder blocks but the name collision trips people up constantly. Grep KNNConstants for the exact keys your version uses.

PQ as an encoder under HNSW or IVF

In faiss, PQ is configured as an encoder on the method. The mapping nests it:

"method": {
  "name": "hnsw",
  "engine": "faiss",
  "parameters": {
    "m": 16,
    "ef_construction": 128,
    "encoder": {
      "name": "pq",
      "parameters": { "m": 96, "code_size": 8 }
    }
  }
}

This builds an HNSW graph whose stored vectors are PQ codes rather than float32. The graph still navigates as usual; only the vectors it stores and compares are compressed. IVF+PQ does the same for IVF cell contents. Both require training, because the PQ codebooks (and, for IVF, the centroids) must be learned.

The cost of PQ is recall: you are comparing approximations, so the top-k you retrieve is noisier. The production pattern is to use PQ for the fast candidate retrieval and then rescore the candidates against full-precision vectors — the disk-ANN story, covered in quantization and disk-ANN.

Note: PQ is one point on a spectrum of compression k-NN offers. Byte vectors, FP16 scalar quantization, and Binary Quantization (BQ) are alternatives with different recall/memory trade-offs. PQ is the most aggressive (and the only one requiring trained codebooks). The full compression menu lives in quantization and disk-ANN.

Training: when and why

HNSW is train-free; IVF and PQ are not. Their data structures depend on parameters learned from the data distribution:

• IVF's centroids are k-means cluster centers over a sample of your vectors.
• PQ's codebooks are per-sub-space k-means over a sample.

You cannot learn these from a single document, and you don't want to relearn them per segment. So k-NN has a dedicated training workflow: build a model once from a representative sample, store it, and reference it from every field that uses it.

The _train API and the model system index

# 1. Index a representative training set into some source index (e.g. train-index).

# 2. Train a model from it. This runs k-means (IVF centroids and/or PQ codebooks).
curl -XPOST "localhost:9200/_plugins/_knn/models/my-ivfpq-model/_train" -H 'Content-Type: application/json' -d '
{
  "training_index": "train-index",
  "training_field": "embedding",
  "dimension": 768,
  "description": "IVF4096 + PQ96x8 for product embeddings",
  "method": {
    "name": "ivf",
    "engine": "faiss",
    "space_type": "l2",
    "parameters": {
      "nlist": 4096,
      "encoder": { "name": "pq", "parameters": { "m": 96, "code_size": 8 } }
    }
  }
}'

# 3. Poll the model until state == created.
curl -s "localhost:9200/_plugins/_knn/models/my-ivfpq-model?pretty"

The trained model is serialized and stored in the .opensearch-knn-models system index (a regular, replicated OpenSearch index that k-NN manages). Training is coordinated through the cluster manager and runs as a task; the model has a lifecycle state (training → created, or failed). Once created, you point a knn_vector field at it by model_id instead of specifying a method inline:

PUT /products-trained
{
  "settings": { "index.knn": true },
  "mappings": {
    "properties": {
      "embedding": { "type": "knn_vector", "model_id": "my-ivfpq-model" }
    }
  }
}

sequenceDiagram
    participant U as User
    participant CM as Cluster manager
    participant T as Training node
    participant SI as .opensearch-knn-models
    U->>CM: POST _knn/models/<id>/_train (training_index, method)
    CM->>SI: create model doc (state=training)
    CM->>T: dispatch training task
    T->>T: read sample, run k-means (IVF centroids / PQ codebooks)
    T->>SI: write serialized model (state=created)
    Note over U: poll GET _knn/models/<id> until state=created
    U->>U: PUT index with knn_vector { model_id: <id> }

# Where to read the training + model code in a k-NN checkout:
grep -rln "TrainingJob\|ModelDao\|class Model\b\|MODEL_INDEX_NAME\|ModelState" \
  src/main/java/org/opensearch/knn
grep -rn "_train\|TrainingModelRequest\|TrainingModelTransportAction" \
  src/main/java/org/opensearch/knn/plugin/rest src/main/java/org/opensearch/knn/plugin/transport

Warning: Train on a representative sample. If your training set's distribution differs from production data, IVF cells and PQ codebooks will be mismatched and recall will quietly degrade. The training set should be large enough for nlist k-means (faiss wants on the order of tens of points per centroid as a minimum) — too few training points for the requested nlist is a common training failure.

Tuning: parameters → effect

The whole point of knowing the algorithms is to tune them. Here is the consolidated table a contributor reaches for when triaging a recall or latency report.

HNSW

IVF

PQ

The recurring pattern: query-time knobs (ef_search, nprobes) are your first, free lever for recall; index/train-time knobs (m, ef_construction, nlist, PQ m/nbits) require a rebuild and are second-line. Always exhaust the query-time dial before reindexing.

Common bugs and symptoms

Validation: prove you understand this

1. For each of HNSW, IVF, PQ, state in one sentence what it indexes/stores and the single trade-off it makes. Which two require training, and why can't HNSW be train-free if those two aren't?
2. A field is engine: faiss, method.name: hnsw, m: 16, ef_construction: 128. A user reports low recall. Give the ordered list of knobs you would try and say which require a reindex.
3. Explain, with the Voronoi-cell picture, why IVF recall depends on nprobes and why a true neighbour can be missed even at the same latency as HNSW.
4. Compute the storage per vector for d=1024 under (a) float32 HNSW and (b) PQ m=128, nbits=8. State the compression ratio and the cost you paid for it.
5. Walk the _train workflow end to end: what runs k-means, where the model is stored, what its lifecycle states are, and how a field references it. Which node coordinates it?
6. Translate this requirement into a method (or model_id) mapping: "1B vectors, memory-bounded, can tolerate a training step and a rescoring pass." Name the algorithm combination and why.

When you can do all six, move to native integration and memory to see where these structures actually live at runtime (native memory, the circuit breaker, the cache), then the k-NN query path to trace a query through them. For the compression menu these algorithms plug into, read quantization and disk-ANN; for the Lucene-engine HNSW these map onto, see HNSW in Lucene.