HNSW (Hierarchical Navigable Small World) ist ein Algorithmus für die Vektordatenbank-Suche. Er findet in einem Graphen mit mehreren Ebenen schnell die ähnlichsten Vektoren zu einer Anfrage – eine der Standardtechniken für Approximate Nearest Neighbor (ANN)-Suche.
Wie funktioniert HNSW?
HNSW baut einen mehrschichtigen Graphen auf. Die oberste Ebene enthält nur wenige Knoten und ermöglicht große Sprünge, jede tiefere Ebene wird dichter. Bei einer Suche startet der Algorithmus ganz oben, nähert sich dem Zielknoten Ebene für Ebene an und verfeinert die Kandidatenliste in der untersten, vollständig verbundenen Ebene.
Die drei Parameter
- M: maximale Kantenzahl pro Knoten (typisch 16) – steuert Speicherverbrauch und Graphdichte.
- efConstruction: Größe der Kandidatenliste beim Aufbau (typisch 200) – höher = bessere Qualität, langsameres Einfügen.
- efSearch: Größe der Kandidatenliste bei der Suche (typisch 100) – höher = besserer Recall, höhere Latenz.
Wo wird HNSW eingesetzt?
HNSW ist in praktisch allen gängigen Vektordatenbanken verbaut: FAISS, pgvector, Qdrant, Weaviate, Milvus, Elasticsearch und Redis. Es skaliert auf Millionen bis Milliarden von Vektoren und ist zugleich ein zentraler Baustein der Hybrid Search, bei der die Vektorsuche den Volltext ergänzt.
Verwandte Grundlagen: Vektordatenbank, Embedding, Top-k-Retrieval.