HNSW Parameters `≥0.1.0`¶

When creating an index, its HNSW parameters can be configured via the optional hnsw field. All parameters are optional as well and can be omitted.

{
  "idSize": 36,
  "aspects": [
    {
      "name": "description",
      "type": "text",
      "path": "$.description",
      "settings": {
        "model": "nomic-embed-text-v1.5.f16.gguf"
      }
    }
  ],
  "hnsw": {
    "M": 48,
    "Mmax": 48,
    "Mmax0": 96,
    "mL": 0.2583177668,
    "efConstruction": 200,
    "efSearch": 200
  }
}

Parameter	Type	Default	Description
`M`	integer	\(16\)	Number of established connections.
`Mmax`	integer	\(M\)	Maximum number of connections for each element on upper layers.
`Mmax0`	integer	\(2M\)	Maximum number of connections for each element on layer 0, important for high recall.
`mL`	number	\(\frac{1}{\ln(M)}\)	Normalization factor for level generation.
`efConstruction`	integer	\(200\)	Size of the dynamic candidate neighbour list during construction.
`efSearch`	integer	\(100\)	Size of the dynamic candidate list during search.
`extendCandidates`	boolean	`true`	Extend candidate neighbour list, useful for clustered data.
`keepPrunedConnections`	boolean	`true`	Prefer diverse candidate neighbour list rather than simply choosing the nearest \(M\).
`maxStoreSize`	integer	\(10000\)	Maximum number of vectors stored in a single file on disk.

M¶

\(M\) controls how many neighbours a newly inserted element tries to connect to on each layer. It is the most important construction-time parameter and one of the main memory/quality knobs. During insertion, HNSW searches for candidate neighbours and then selects up to \(M\) of them as graph neighbours for the inserted vector.

Increasing \(M\):

Creates a denser graph;
Improves recall, especially at high recall targets;
Helps in high-dimensional or difficult datasets;
Increases memory consumption roughly linearly;
Increases construction time;
Can increase query time because each visited node has more neighbours to inspect.

Decreasing \(M\):

Reduces memory consumption;
Usually improves speed at low recall;
Can hurt recall and graph connectivity;
Is more suitable for low-dimensional or easy datasets.

The suggested reasonable range for \(M\) is approximately:

\[ M \in[5,48] \]

Mmax¶

\(M_{\max}\) is the maximum number of graph connections a node may have on layers above the base layer. When a new bidirectional edge is added to an existing node, that existing node may exceed its allowed degree. If its connection list becomes larger than \(M_{\max}\), HNSW prunes the list back down using the neighbor-selection algorithm.

Increasing \(M_{\max}\):

Allows more edges on upper layers;
May improve navigability slightly;
Increases memory consumption;
Can increase query time because each visited node has more neighbors.

Decreasing \(M_{\max}\):

Reduces memory consumption;
Reduces branching factor;
May make upper-layer navigation worse if too small.

The standard recommendation is:

\[ M_{\max} = M \]

Usually this should not be tuned independently unless you have a specific reason.

Mmax0¶

\(M_{\max 0}\) is the maximum number of connections for nodes on the base layer, layer 0. Layer 0 contains every indexed vector and is where the final high-accuracy search happens. Because this layer is the most important for recall, the maximum degree is treated separately from upper layers.

Increasing \(M_{\max 0}\):

Improves recall;
Improves local graph connectivity;
Increases memory consumption;
Increases the number of neighbors checked during search; can eventually hurt speed if set too high.

Decreasing \(M_{\max 0}\):

Reduces memory consumption;
May significantly hurt high-recall search.
Setting \(M_{\max 0} = M\) can cause a strong performance penalty at high recall.

The standard recommendation is:

\[ M_{\max 0} = 2M \]

mL¶

\(m_L\) controls the random assignment of vectors to HNSW layers. For each inserted element, HNSW chooses a maximum layer \(l\) using approximately:

\[ l = \lfloor -\ln(U) \cdot m_L \rfloor \]

where \(U\) is uniformly sampled from \((0, 1)\).

This gives an exponentially decreasing probability of appearing in higher layers. Most vectors exist only in layer 0; fewer exist in layer 1; even fewer in layer 2, and so on.

The layer hierarchy is what makes HNSW different from a flat NSW graph. Upper layers contain long-range links and are used for fast coarse navigation. Lower layers contain shorter-range links and are used for refinement. \(m_L\) controls how quickly layer membership decays.

Increasing \(m_L\):

More elements in upper layers;
More overlap between layers;
Possibly less useful hierarchy if layers become too similar.

Decreasing \(m_L\):

Fewer elements in upper layers;
Less overlap between layers;
Potentially longer greedy paths within each layer;

The recommended value is:

\[ m_L = \frac{1}{\ln(M)} \]

This corresponds roughly to a skip-list-style promotion probability of about \(\frac{1}{M}\).

Usually this should be derived from \(M\) and not be tuned independently, unless you know what you are doing.

efConstruction¶

\(\text{efConstruction}\) controls how thoroughly HNSW searches for neighbors while inserting vectors. During construction, when a new vector is inserted, HNSW searches the existing graph to find candidate neighbors. \(\text{efConstruction}\) is the size of the dynamic candidate list used during this search.

Increasing \(\text{efConstruction}\):

Improves the quality of the graph;
Usually improves recall;
Can improve search speed;
Increases construction time, often significantly.

Decreasing \(\text{efConstruction}\):

Faster construction time;
May require larger \(\text{efSearch}\) later to reach the same recall;
May reduce maximum achievable recall.

The suggested reasonable range for \(\text{efConstruction}\) is approximately:

\[ \text{efConstruction} = v \, \cdot M, \; v \in[5,20] \]

efSearch¶

\(\text{efSearch}\) controls the number of candidate neighbors retained during the layer-0 search. At query time, HNSW first performs greedy search from the top layer down to layer 1 with \(ef = 1\). Then, on layer 0, it performs a broader search using \(ef = \max(k, \text{efSearch})\). Then it returns the best \(k\) results from the resulting set.

Increasing \(\text{efSearch}\):

Improves recall;
Increases query latency;

Decreasing \(\text{efSearch}\):

Reduces latency;
Reduces recall;
May be appropriate for low-recall or highly latency-sensitive applications.

The suggested value is in the same range as \(\text{efConstruction}\). However, note that setting it lower than \(k\) has no effect.

extendCandidates¶

This parameter is used by the heuristic neighbor-selection algorithm. When HNSW inserts a new element, it first obtains a set of candidate neighbors. The heuristic then selects a diverse subset of those candidates.

If extendCandidates is enabled, the candidate set is expanded by also considering the neighbors of the candidate elements.

Enabling extendCandidates:

Can improve graph quality on highly clustered data;
Helps discover inter-cluster or boundary connections;
Can improve robustness when nearest candidates are all from the same local cluster;
Increases construction time;

keepPrunedConnections¶

This parameter is also part of the heuristic neighbor-selection algorithm. The heuristic prefers diverse neighbors rather than simply choosing the nearest \(M\) vectors. Some close candidates may be rejected because they are considered redundant with already selected neighbors.

If keepPrunedConnections is enabled, some of those rejected candidates are added back if the selected neighbor list has fewer than \(M\) elements.

Enabling keepPrunedConnections:

Tends to produce fuller adjacency lists;
Makes the graph closer to fixed degree \(M\);
Can improve recall and robustness;

maxStoreSize¶

This parameter has no effect on the actual output of the HNSW search, it merely distributes all stored vectors (and their neighbour links) over files on disk. maxStoreSize determines the maximum number of vectors in a file. Combined with \(M_{\max 0}\) this imposes an implicit maximum file size.

HNSW Parameters ≥0.1.0¶

M¶