HNSW Explorer: Hierarchisch navigierbare „Small World“, visualisiert

Beobachten Sie, wie sich eine Suche durch den mehrschichtigen Graphen bewegt – von der spärlichen obersten Schicht (Autobahnen) hinunter zur dichten untersten Schicht (Ortsstraßen). Ziehen Sie den Abfragepunkt auf Ebene 0 und passen Sie „ M “ an / ef an, um zu sehen, wie sich der Graph verändert.

Maximale Anzahl von Nachbarn pro Knoten

ef8

Kandidatenpool der Ebene 0

Geschwindigkeit450ms

Pro Schritt

Aktueller Schritt

14 / 14

Suche abgeschlossen. Top-3: [3, 10, 4].

Suchstatistiken

Besucht

17 / 30

Ebenen

Eintrag

Knoten 0

Top-3

[3, 10, 4]

Ebenenverteilung

So funktioniert „ HNSW “

Geschichteter Graph: Jedem Knoten wird nach einer Exponentialverteilung zufällig eine maximale Ebene zugewiesen. Die meisten Knoten befinden sich nur auf Ebene 0; nur sehr wenige erreichen die oberste Ebene.
Innerhalb jeder Schicht: Jeder Knoten ist mit seinen M nächsten Nachbarn verbunden. Höhere Schichten sind spärlich (wenige Knoten, lange Kanten = „Autobahnen“). Schicht 0 ist dicht (alle Knoten, kurze Kanten = „Ortsstraßen“).
Die Suche beginnt oben: Von einem festen Einstiegspunktaus wird gierig zum Nachbarn gewandert, der der Abfrage am nächsten liegt; dies wird wiederholt, bis keine Verbesserung mehr erzielt wird.
Eine Ebene tiefer gehen und wiederholen: Die Position der vorherigen Ebene wird zum Startpunkt für den Durchlauf der nächsten Ebene. Mit jedem Schritt wird das Ergebnis durch feinkörnigere Kanten verfeinert.
Ebene 0 mit „ ef “: Auf der untersten Ebene hält „ HNSW “ – anstatt beim ersten lokalen Minimum anzuhalten – einen Pool der ef besten Kandidaten und erweitert deren Nachbarschaft. Größer ef → genauer, aber langsamer.

Warum es so schnell ist: Die obersten Schichten fungieren wie ein Index über dem Index – man legt riesige Entfernungen in nur wenigen Sprüngen zurück und zoomt dann heran. Bei N Punkten durchläuft die Suche etwa O(log N) Knoten statt N.

Was ist „ HNSW “?

HNSW (Hierarchical Navigable Small World) ist ein graphbasierter Algorithmus zur näherungsweisen Suche nach dem nächsten Nachbarn. Er organisiert Vektoren in einem Stapel navigierbarer „Small-World“-Graphen: spärliche obere Schichten mit Kanten großer Reichweite für die grobe Routenführung und eine dichte unterste Schicht mit kurzen Kanten für den abschließenden feinkörnigen Durchlauf. Eine Suche springt in jeder Schicht gierig in Richtung der Abfrage und springt dann nach unten – dabei werden etwa O(log N) Knoten besucht, anstatt alle N zu scannen.

HNSW ist der am häufigsten verwendete In-Memory-Vektorindex und der Standard-Graphindex in „ Milvus “. „ Milvus “ bietet außerdem HNSW_SQ sowie HNSW_PQ Varianten an, die die gespeicherten Vektoren quantisieren, um den Speicherbedarf auf Kosten eines geringen Recall-Verlusts zu reduzieren.

HNSW Parameter in Milvus

M (Bauzeit): Die maximale Anzahl von Kanten pro Knoten, derselbe Regler wie der Schieberegler oben. Typische Werte liegen zwischen 8 und 64. Ein höherer M-Wert verbessert den Recall und die Konnektivität des Graphen, erhöht jedoch den Speicherbedarf linear und verlangsamt die Konstruktion.
efConstruction (Erstellungszeit): Die Größe des Kandidatenpools, die beim Einfügen von Knoten verwendet wird. Höhere Werte führen zu einem qualitativ besseren Graphen (höherer erreichbarer Recall), allerdings auf Kosten einer langsameren Indexerstellung. Typische Werte liegen zwischen 100 und 500.
ef / „ ef_search “ (Abfragezeit): Der während des Layer-0-Durchlaufs beibehaltene Kandidatenpool – der wichtigste Regler für Recall und Latenz bei der Suche. Er muss mindestens so groß sein wie Ihr „ top-K “. Erhöhen Sie ihn, bis der Recall ein Plateau erreicht; die Latenz steigt dabei in etwa linear mit.

HNSW vs IVF vs DiskANN

HNSW liefert typischerweise die beste Abfragelatenz bei hohem Recall für die In-Memory-Suche – deshalb ist es die Standardwahl, wenn der Datensatz (zuzüglich des Graph-Overheads) in „ RAM “ passt. Die Kosten bestehen aus Speicherbedarf und Erstellungszeit: Der Graph verursacht einen spürbaren Overhead pro Vektor, und Einfügungen sind langsamer als die k-Means-Zuweisung von „ IVF “. Wählen Sie „ IVF “, wenn Sie schnelle Indexaufbauten oder aggressive Quantisierung benötigen, und „ DiskANN “, wenn der Datensatz zu groß für „ RAM “ ist, Sie aber dennoch einen hohen Recall benötigen.

Häufig gestellte Fragen

Was steuert der Parameter „M“ in „ HNSW “?

M begrenzt die Anzahl der Kanten, die jeder Knoten pro Schicht behält. Ein größeres M sorgt für eine bessere Vernetzung des Graphen – höhere Recall-Rate und robusteres Routing –, jedoch wächst der Speicherbedarf linear mit M und die Indexerstellung verlangsamt sich. Werte zwischen 8 und 64 decken die meisten Workloads ab; 16–32 ist ein gängiger „Sweet Spot“.

Was ist der Unterschied zwischen „ ef “ und „ efConstruction “?

Beides sind Größen des Kandidatenpools, die zu unterschiedlichen Zeitpunkten angewendet werden. „ efConstruction “ wird beim Aufbau des Indexes verwendet: Es bestimmt, wie gründlich jeder eingefügte Knoten nach Nachbarn sucht, und steuert somit die Qualität des Graphen. „ ef “ (ef_search) wird zum Zeitpunkt der Abfrage verwendet: Es steuert, wie breit die Layer-0-Suche ist, und tauscht bei jeder Abfrage Latenz gegen Recall ein.

Wie viel Speicher benötigt ein „ HNSW “-Index?

Grob gesagt die Rohvektoren plus der Graph: etwa d × 4 Byte pro Vektor für „float32“-Daten, plus in der Größenordnung von M × 2 × 8 Byte an Kanten pro Knoten. Für speicherbeschränkte Bereitstellungen bietet Milvus die Funktionen „ HNSW_SQ “ und „ HNSW_PQ “ an, die gespeicherte Vektoren quantisieren, oder „ DiskANN “, das vollständige Vektoren nach SSD verschiebt.

Wann sollte ich „ HNSW “ anstelle von „ IVF “ verwenden?

Verwenden Sie „ HNSW “, wenn die Abfragelatenz bei hohem Recall Priorität hat und der Index in den Arbeitsspeicher passt – diese Methode ist in der Regel am schnellsten. Bevorzugen Sie „ IVF “, wenn Sie Indizes häufig neu erstellen (deutlich schnellere Erstellungen) oder wenn Sie diese mit der Quantisierung „ SQ8 “ bzw. „PQ “ kombinieren, um ein knappes Speicherbudget einzuhalten.

Vertiefung: Lesen Sie die Dokumentation zu „HNSW “ für genaue Indexparameter oder sehen Sie sich „Index Explained“ als vollständigen Leitfaden an.