HNSW is a graph index. Every vector is a node linked to its nearest neighbours, and the nodes are arranged in layers so that a search can hop quickly towards the question vector. It was proposed by Malkov and Yashunin.

Meaning of the name

Word in the nameWhat it means
GraphEach vector is a node, linked to a few of its closest vectors
Small worldAny 2 nodes are connected by a few hops, as in "six degrees of separation"
NavigableFrom any node, stepping to the neighbour closest to the question moves you nearer to it
HierarchicalUpper layers have few nodes and long links (highways), and the bottom layer has every node and short links (local streets)

Search steps

  • start at the top layer
  • keep stepping to the neighbour that is closest to the question
  • drop one layer when no neighbour is closer
  • finish at the bottom layer, after about hops in total

When to use

  • very high recall at low latency
  • the cost is extra memory for the links
  • it is the default index in most vector databases, see the comparison of indexes in the ANN search note

Code

import faiss
 
d = 768
index = faiss.IndexHNSWFlat(d, 32)     # 32 links per node
index.hnsw.efConstruction = 200        # effort while building the graph
index.add(xb)                          # no training step is needed
index.hnsw.efSearch = 64               # effort while searching, higher means better recall and slower
distances, ids = index.search(xq, 10)

Notes:

  • unlike IVF, HNSW needs no train step, so new vectors can be added at any time
  • efSearch plays the same role as nprobe in IVF: it trades speed for recall

Fast search only helps if the vectors stand for good units of text, so the next question is how to cut the documents, see Chunking.