HNSW (Hierarchical Navigable Small World) ist ein 2016 von Yury Malkov und Dmitry Yashunin vorgestellter Graphalgorithmus zur approximativen Ähnlichkeitssuche in hochdimensionalen Vektorräumen, der zum meistgenutzten Verfahren in heutigen Vektordatenbanken wurde.
Zusammenfassung
Bei sehr großen Sammlungen hochdimensionaler Vektoren – etwa Embeddings von Millionen Textabschnitten – wird die exakte Suche nach dem nächstgelegenen Vektor rechnerisch unpraktikabel, da sie im schlimmsten Fall jeden gespeicherten Vektor einzeln vergleichen müsste. HNSW löst dieses Problem, indem es die Vektoren in einer mehrschichtigen Graphstruktur organisiert, durch die sich mit wenigen Sprüngen navigieren lässt.
Begriffsgeschichte
Malkov und Yashunin veröffentlichten das Verfahren 2016 zunächst als Preprint; die überarbeitete Fassung erschien 2018 in der Fachzeitschrift IEEE Transactions on Pattern Analysis and Machine Intelligence. Der Algorithmus baut auf dem älteren Konzept der Navigable Small World Graphs auf, ergänzt diese jedoch um eine hierarchische Schichtstruktur, die die Suchgeschwindigkeit zusätzlich verbessert.
Methodische Grundlagen
Die oberste Graphschicht enthält nur wenige, weit verstreute Knoten und erlaubt große Sprünge durch den Vektorraum; jede darunterliegende Schicht enthält mehr Knoten und feinere Verbindungen. Eine Suche beginnt in der obersten, dünn besetzten Schicht und verfeinert sich schrittweise über die darunterliegenden Schichten – ähnlich einer Landkarte, die von der Kontinentalübersicht bis zur Straßenebene zoomt.
Anwendungsfelder
HNSW bildet den Kern der Ähnlichkeitssuche in den meisten heute verbreiteten Vektordatenbanken und ist damit ein zentraler Baustein von Retrieval-Augmented Generation, bei der Textabschnitte anhand ihrer Embedding-Nähe zu einer Suchanfrage gefunden werden müssen.
Kontroversen und Kritik
Als approximatives Verfahren garantiert HNSW nicht, stets den tatsächlich nächstgelegenen Vektor zu finden – ein Kompromiss zwischen Suchgeschwindigkeit und Genauigkeit, der sich über Parameter wie Graphverbindungsgrad und Suchtiefe nur begrenzt austarieren lässt.
Zudem wächst der Speicherbedarf der Graphstruktur mit der Zahl gespeicherter Vektoren, was HNSW bei sehr großen Sammlungen speicherintensiver macht als manche alternativen Indexierungsverfahren.
Verwandte Begriffe
- Semantische Suche – übergeordnetes Konzept, dem HNSW als technische Grundlage dient
- Embedding-Modell – erzeugt die Vektoren, die HNSW durchsucht
- Reranking – nachgelagerter Schritt derselben Suchpipeline, der die von HNSW gefundenen Kandidaten neu bewertet
Quellenangaben
- Malkov, Yury A. / Yashunin, Dmitry A., 2016. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. arXiv: 1603.09320.
- Malkov, Yury A. / Yashunin, Dmitry A., 2018. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42 (4), S. 824–836.