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 name | What it means |
|---|---|
| Graph | Each vector is a node, linked to a few of its closest vectors |
| Small world | Any 2 nodes are connected by a few hops, as in "six degrees of separation" |
| Navigable | From any node, stepping to the neighbour closest to the question moves you nearer to it |
| Hierarchical | Upper 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
trainstep, so new vectors can be added at any time efSearchplays the same role asnprobein 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.