Was ist ein Vektor-Datenbank-Index (HNSW)? Schnelle Ähnlichkeitssuche erklärt

HNSW (Hierarchical Navigable Small World) ist ein graphbasierter Index für Vektor-Datenbanken, der eine sogenannte approximative Nächste-Nachbarn-Suche (englisch: Approximate Nearest Neighbor, kurz ANN) durchführt. Statt bei jeder Suchanfrage alle gespeicherten Vektoren einzeln zu vergleichen, navigiert HNSW über einen mehrschichtigen Graphen sehr schnell zur Umgebung des gesuchten Punkts. Das Ergebnis ist eine Ähnlichkeitssuche, die auch bei Millionen von Einträgen in Millisekunden antwortet – zum Preis einer geringen, steuerbaren Ungenauigkeit.

Warum ein Index bei Vektoren nötig ist

In einer Vektor-Datenbank werden Texte, Bilder oder andere Daten als Zahlenreihen gespeichert, sogenannte Embeddings. Ähnliche Inhalte liegen dabei nahe beieinander im Vektorraum. Um zu einer Suchanfrage die passendsten Einträge zu finden, muss man die „nächsten Nachbarn" bestimmen – also die Vektoren mit dem kleinsten Abstand.

Der naive Weg wäre, den Suchvektor mit jedem einzelnen gespeicherten Vektor zu vergleichen. Bei wenigen tausend Einträgen ist das kein Problem. Bei hochdimensionalen Daten und großen Beständen wird dieses vollständige Durchsuchen jedoch spürbar langsam (Tiger Data). Genau hier setzt ein Index an: Er organisiert die Daten so, dass die Suche nicht mehr den ganzen Bestand berühren muss.

HNSW gilt heute als der am häufigsten verwendete Standard-Algorithmus für diese Aufgabe und ist bei vielen Vektor-Datenbanken die Voreinstellung für mittelgroße Datenmengen (Zilliz, Milvus). Der Algorithmus geht auf die Arbeit von Malkov und Yashunin zurück (Tiger Data).

Wie HNSW funktioniert: der mehrschichtige Graph

HNSW baut aus den Vektoren einen Graphen auf. Jeder Vektor ist ein Knoten, und Kanten verbinden ähnliche Vektoren miteinander (Milvus). Das Besondere ist die hierarchische Struktur mit mehreren Schichten:

• Obere Schichten enthalten nur wenige Knoten mit weitreichenden Verbindungen. Sie dienen als grobe Übersichtskarte.
• Untere Schichten werden dichter, bis die unterste Schicht alle Vektoren enthält.

Eine Suchanfrage beginnt in der obersten Schicht und geht dort „gierig" (greedy) vor: Sie springt über die langen Verbindungen schnell in die grobe Nähe des gesuchten Punkts (VeloDB). Der beste gefundene Punkt dient dann als Einstiegspunkt für die nächsttiefere Schicht. So arbeitet sich die Suche Schicht für Schicht bis zur untersten Ebene vor, wo die genaue Nachbarschaft feiner abgesucht wird.

Man kann sich das wie Reisen mit unterschiedlichen Verkehrsmitteln vorstellen: Zuerst mit dem Flugzeug in die richtige Region, dann mit dem Zug in die richtige Stadt, zuletzt zu Fuß zur genauen Adresse. Dadurch muss die Suche nur einen Bruchteil aller Vektoren berühren.

Approximativ statt exakt: der bewusste Kompromiss

Das „approximativ" in ANN ist kein Zufall. HNSW garantiert nicht, dass es immer die exakt besten Nachbarn zurückgibt – es liefert sehr wahrscheinlich die besten. Dieser Kompromiss ist gewollt: Höhere Genauigkeit lässt sich einstellen, kostet dann aber Suchzeit (InterSystems).

Wie gut die Suche die tatsächlich besten Ergebnisse trifft, misst man mit dem Recall – dem Anteil der korrekten Nachbarn, die auch wirklich gefunden wurden. Für die meisten Anwendungen ist ein sehr hoher, aber nicht perfekter Recall völlig ausreichend, weil die Trefferliste ohnehin von einem LLM oder einem Menschen weiterverarbeitet wird.

Die wichtigsten Parameter: M, efConstruction, efSearch

Das Verhalten von HNSW wird über drei Parameter gesteuert (Milvus AI Reference):

• M – die Zahl der Verbindungen pro Knoten (typisch 16). Ein höherer Wert macht den Graphen dichter, verbessert den Recall, braucht aber mehr Speicher.
• efConstruction – die „Breite" der Suche beim Aufbau des Index (typisch 200). Höhere Werte erzeugen einen besseren Graphen, verlangsamen aber den einmaligen Aufbau.
• efSearch – die Suchbreite zur Anfragezeit. Sie steuert direkt den Kompromiss zwischen Geschwindigkeit und Recall und lässt sich pro Anfrage anpassen, ohne den Index neu zu bauen.

Eine mögliche Aufteilung: Ein Aufbau für maximale Genauigkeit könnte M=24, efConstruction=400 und efSearch=500 nutzen, während ein Echtzeit-System eher M=12, efConstruction=200 und efSearch=100 wählt, um Tempo und Ressourcen zu schonen (Milvus AI Reference). Als Startpunkt empfehlen sich die Standardwerte M=16 und efConstruction=200, die man dann schrittweise anpasst.

HNSW im Kontext von AI-Mitarbeitern

Für unsere AI-Mitarbeiter ist HNSW ein unsichtbarer, aber wichtiger Baustein. Wenn ein AI-Mitarbeiter Fragen auf Basis firmeneigener Dokumente beantwortet, geschieht das meist über Retrieval-Augmented Generation (RAG): Zu einer Frage werden zuerst die passendsten Textpassagen aus einer Vektor-Datenbank gesucht und dann dem Sprachmodell mitgegeben.

Genau diese Suche muss schnell und treffsicher sein – und dafür sorgt der Index. Ob bei der semantischen Suche im Wissensbestand oder bei der embeddingbasierten Suche im Vertrieb: Ein gut abgestimmter HNSW-Index entscheidet mit darüber, ob eine Antwort in Millisekunden oder Sekunden erscheint und wie relevant die herangezogenen Quellen sind. Die Wahl der Parameter ist deshalb keine reine Technikfrage, sondern eine Abwägung zwischen Antwortzeit, Speicherbedarf und Genauigkeit für den jeweiligen Anwendungsfall.

Häufige Fragen

Wann sollte ich HNSW statt einer exakten Suche verwenden?

Sobald der Datenbestand so groß wird, dass ein vollständiger Vergleich aller Vektoren pro Anfrage zu langsam ist. Bei einigen tausend Einträgen reicht oft die exakte Suche. Bei Hunderttausenden oder Millionen hochdimensionaler Vektoren wird HNSW interessant, weil es die Suchzeit stark verkürzt und die Genauigkeit über Parameter steuerbar bleibt.

Was bedeutet „approximativ" bei der Nächste-Nachbarn-Suche?

Approximativ heißt, dass der Algorithmus mit sehr hoher Wahrscheinlichkeit die besten Treffer findet, aber keine mathematische Garantie dafür gibt. Diese kleine Unschärfe ist der Preis für die hohe Geschwindigkeit. Über den efSearch-Parameter lässt sich der Recall – also die Trefferqualität – bei Bedarf erhöhen, was die Suche etwas langsamer macht.

Welchen Parameter passe ich an, wenn die Ergebnisse zu ungenau sind?

Zur Anfragezeit ist efSearch der erste Hebel: Ein höherer Wert verbessert den Recall, ohne dass der Index neu aufgebaut werden muss (Pinecone). Reicht das nicht, kann man M oder efConstruction erhöhen – das verbessert die Graphqualität grundlegend, erfordert aber einen Neuaufbau und mehr Speicher.

Ist HNSW an eine bestimmte Datenbank gebunden?

Nein. HNSW ist ein Algorithmus, der in vielen Systemen umgesetzt ist. So unterstützt etwa die PostgreSQL-Erweiterung pgvector HNSW-Indizes (Tiger Data), und auch spezialisierte Vektor-Datenbanken bieten ihn an. Die Grundprinzipien und Parameter bleiben dabei ähnlich, auch wenn die Voreinstellungen je nach System variieren.

Wie hängt HNSW mit Embeddings und RAG zusammen?

Embeddings verwandeln Inhalte in Vektoren, HNSW sorgt für deren schnelles Auffinden, und RAG nutzt diese Treffer, um einem Sprachmodell relevanten Kontext zu geben. Die drei greifen ineinander: Ohne gute Embeddings findet auch der beste Index nichts Sinnvolles, und ohne schnellen Index bleibt selbst gutes Suchmaterial im großen Bestand liegen.