Die Nadel im Milliarden-Heuhaufen: Approximate Nearest Neighbor Search, HNSW und die Architektur der Vektordatenbanken

Der Aufhänger: Die Frage, die kein Datenbankindex beantworten kann

Stell dir vor, du tippst in eine Suchleiste nicht mehr ein Stichwort, sondern eine Bedeutung. Du fragst nicht „Dokumente, die das Wort Kündigungsfrist enthalten", sondern „Textstellen, die ungefähr dasselbe meinen wie dieser Absatz hier". Genau das tun moderne KI-Systeme ständig: Sie verwandeln Texte, Bilder, Gesichter, Moleküle oder Musikstücke in lange Zahlenreihen – Vektoren mit hunderten oder tausenden Dimensionen – und behaupten, dass Nähe in diesem Zahlenraum Ähnlichkeit in der Bedeutung entspricht. Ein Sprachmodell bettet den Satz „Wie kündige ich meinen Vertrag?" in einen Punkt ein; die passende Antwort im Handbuch liegt in der Nähe.

Damit verschiebt sich die Frage der Suche fundamental. Sie lautet nicht mehr „Wo steht dieser exakte Wert?", sondern: „Welche der Milliarde gespeicherten Punkte liegen diesem Anfragepunkt am nächsten?" Das ist das Problem der nächsten Nachbarn (Nearest Neighbor Search), und es ist die stille Infrastruktur hinter semantischer Suche, Empfehlungssystemen, Gesichtserkennung, Plagiatsprüfung und – seit dem Boom der großen Sprachmodelle – hinter Retrieval-Augmented Generation (RAG), jenem Verfahren, mit dem ein Chatbot vor der Antwort erst die relevanten Wissensschnipsel aus einer Datenbank holt.

Der Haken: Die naheliegende Lösung – vergleiche den Anfragepunkt einfach mit allen gespeicherten Punkten und nimm die nächsten – ist bei Milliarden hochdimensionaler Vektoren hoffnungslos zu langsam. Und die klassischen Tricks der Informatik, mit denen wir eindimensionale oder zweidimensionale Daten in Bäumen organisieren, versagen in hohen Dimensionen auf eine geradezu unheimliche Weise. Dieser Artikel erzählt, wie ein überraschender Umweg über die Soziologie der 1960er Jahre – das berühmte Experiment zu den „sechs Handschlägen" – zu einer Datenstruktur namens HNSW führte, die heute in fast jeder Vektordatenbank der Welt steckt und das Problem in logarithmischer Zeit knackt.

Teil 1: Das Problem – und warum es in hohen Dimensionen so bösartig wird

Was „nächster Nachbar" genau heißt

Formal ist die Aufgabe simpel. Gegeben eine Menge von N Punkten in einem d-dimensionalen Raum und ein Anfragepunkt q, finde denjenigen (oder die k Punkte), der q nach einem Abstandsmaß am nächsten liegt. Als Abstandsmaß dient in der Praxis meist der euklidische Abstand (L2), das innere Produkt oder die Kosinus-Ähnlichkeit – Letztere misst den Winkel zwischen zwei Vektoren und ignoriert deren Länge, was bei normalisierten Text-Embeddings die übliche Wahl ist.

Die brachiale Lösung, der lineare Scan (brute force), berechnet den Abstand zu jedem einzelnen Punkt. Das ist mathematisch exakt und für ein paar tausend Punkte völlig in Ordnung. Aber die Kosten wachsen linear mit N und linear mit d: Bei einer Milliarde Vektoren mit je 768 Dimensionen bedeutet eine einzige Suche eine Milliarde Abstandsberechnungen über je 768 Zahlen. Auf Web-Skala, bei tausenden Anfragen pro Sekunde, ist das ökonomisch aussichtslos.

Der Fluch der Dimensionalität

Der naheliegende Ausweg der klassischen Algorithmik lautet: Bau einen Suchbaum. In zwei oder drei Dimensionen funktioniert das glänzend. Ein k-d-Baum unterteilt den Raum rekursiv entlang der Achsen, ein R-Baum oder SR-Baum gruppiert Punkte in verschachtelte Rechtecke, und eine Suche muss nur einen kleinen Teil des Baums besuchen. Räumliche Datenbanken und Kartendienste leben davon.

Doch je höher die Dimension, desto gründlicher zerbricht diese Idee – ein Phänomen, das Richard Bellman den Fluch der Dimensionalität taufte. Der Kern des Problems ist geometrisch kontraintuitiv: In sehr hochdimensionalen Räumen rücken die Abstände zwischen einem beliebigen Anfragepunkt und allen anderen Punkten immer dichter zusammen. Der nächste und der entfernteste Nachbar unterscheiden sich in ihrer Distanz kaum noch. Damit verliert der Begriff „nächster Nachbar" seine Trennschärfe, und – schlimmer für die Baumverfahren – die Beschneidungsregeln greifen nicht mehr: Ein Suchbaum kann keine Zweige mehr guten Gewissens ausschließen, weil in fast jedem Zweig ein Kandidat lauern könnte, der ähnlich nah ist.

Das Ergebnis ist empirisch gut dokumentiert und ernüchternd: Ab ungefähr zehn bis zwanzig Dimensionen schlagen exakte baumbasierte Verfahren den simplen linearen Scan kaum noch – oft sind sie sogar langsamer, weil sie fast alle Knoten besuchen und dabei noch Verwaltungsaufwand mitschleppen. Es gibt zudem theoretische Hinweise darauf, dass die exakte nächste-Nachbarn-Suche in hohen Dimensionen den Fluch auf fundamentaler Ebene trägt: Alle bekannten exakten Algorithmen verschlechtern sich exponentiell mit der Dimension. Text-Embeddings haben typischerweise 384, 768, 1536 oder mehr Dimensionen. Exakt geht hier nicht bezahlbar.

Der Ausweg: Approximation

Die rettende Einsicht ist pragmatisch. In den allermeisten Anwendungen brauchen wir gar nicht den garantiert nächsten Nachbarn. Wenn eine semantische Suche statt der zehn objektiv ähnlichsten Dokumente die neun ähnlichsten plus ein fast ebenso gutes zurückgibt, merkt das kein Mensch. Wir dürfen also einen kleinen, kontrollierten Fehler zulassen und bekommen dafür einen gewaltigen Geschwindigkeitsgewinn. Das ist die Approximate Nearest Neighbor Search (ANN).

Die entscheidende Kennzahl heißt Recall: der Anteil der wahren nächsten Nachbarn, den ein Verfahren tatsächlich zurückliefert. Ein Recall von 0,95 bedeutet, dass im Schnitt 95 % der „richtigen" Treffer gefunden werden. Die ganze Kunst von ANN besteht darin, einen hohen Recall (nahe an der exakten Suche) bei drastisch reduzierter Rechenzeit zu erreichen – und beides über eine Handvoll Parameter feinjustierbar zu machen. Historisch gab es dafür mehrere Familien: Locality-Sensitive Hashing (LSH), das ähnliche Punkte absichtlich in dieselben Hash-Töpfe wirft; inverted-file-Verfahren (IVF), die den Raum in Zellen aufteilen und nur die nächstliegenden Zellen durchsuchen; sowie die Produktquantisierung (PQ), die Vektoren komprimiert. Doch die Methode, die in den letzten Jahren zum De-facto-Standard aufgestiegen ist, kommt aus einer ganz anderen Ecke: aus der Graphentheorie sozialer Netzwerke.

Teil 2: Die kleine Welt – von Milgrams Briefen zu Kleinbergs Beweis

Sechs Handschläge

1967 verschickte der Sozialpsychologe Stanley Milgram Briefe an zufällig ausgewählte Menschen im mittleren Westen der USA. Die Aufgabe: den Brief an eine bestimmte Zielperson in Massachusetts weiterzuleiten – aber nur über persönliche Bekannte, immer eine Station weiter, an jemanden, von dem man glaubte, er stehe dem Ziel näher. Verblüffenderweise erreichten viele Briefe ihr Ziel, und die durchschnittliche Kettenlänge lag bei etwa sechs. Aus diesem Befund wurde die populäre Rede von den „sechs Graden der Trennung".

An diesem Experiment ist zweierlei bemerkenswert, und die Informatik hat lange nur die eine Hälfte beachtet. Die erste, offensichtliche Aussage: Das soziale Netz hat einen kleinen Durchmesser – zwei beliebige Menschen sind über wenige Zwischenstationen verbunden. Die zweite, subtilere Aussage steckt im Verfahren selbst: Die Menschen haben diese kurzen Wege dezentral gefunden, jeder nur mit lokalem Wissen über seine eigenen Bekannten, ohne Landkarte des gesamten Netzes. Nicht nur existieren kurze Wege – man kann sie mit einer einfachen gierigen Strategie auch effizient finden.

Watts, Strogatz und die Struktur

1998 gaben Duncan Watts und Steven Strogatz diesem Phänomen ein mathematisches Modell (Nature). Sie zeigten, dass viele reale Netze – von neuronalen Verschaltungen bis zu Stromnetzen – zwei scheinbar widersprüchliche Eigenschaften vereinen: eine hohe lokale Klumpung (meine Bekannten kennen einander) und gleichzeitig einen kleinen Durchmesser. Ihr Rezept: Man nehme ein reguläres Gitter mit vielen lokalen Verbindungen und „verdrahte" einige wenige davon zufällig zu weit entfernten Knoten um. Schon eine Handvoll solcher Fernverbindungen (long-range links) genügt, um den Durchmesser des ganzen Netzes dramatisch zu senken, während die lokale Struktur erhalten bleibt. Das ist die Geburtsstunde des Begriffs Small-World-Netzwerk.

Kleinbergs entscheidende Präzisierung

Watts und Strogatz erklärten, warum kurze Wege existieren. Aber sie erklärten nicht, warum Milgrams Teilnehmer diese Wege auch finden konnten. Diese Lücke schloss Jon Kleinberg im Jahr 2000 (Nature, „Navigation in a small world"). Sein Ergebnis ist für unsere Zwecke der Dreh- und Angelpunkt.

Kleinberg betrachtete ein Gittermodell, in dem jeder Knoten kurze Verbindungen zu seinen unmittelbaren Nachbarn hat und zusätzlich eine Fernverbindung, deren Ziel zufällig gewählt wird – aber nicht gleichverteilt, sondern mit einer Wahrscheinlichkeit, die mit der Distanz r wie r^(−α) abfällt. Der Exponent α steuert, ob die Fernverbindungen eher in die Nähe oder quer durchs ganze Netz zeigen. Kleinbergs Satz: Eine gierige Wegfindung, bei der jeder Knoten die Nachricht einfach an denjenigen seiner Bekannten weitergibt, der dem Ziel geometrisch am nächsten liegt, findet nur bei einem einzigen, ausgezeichneten Wert von α (nämlich α gleich der Dimension des Gitters) kurze Wege – dann sogar in polylogarithmischer Zeit. Bei jedem anderen Exponenten braucht die gierige Suche polynomiell viele Schritte.

Die Botschaft, die man daraus für den Bau von Datenstrukturen mitnimmt, ist tiefgründig: Ein Netz ist genau dann navigierbar – also mit rein lokaler, gieriger Suche schnell durchquerbar –, wenn seine Verbindungen die richtige Mischung aus Reichweiten besitzen: viele kurze für die Feinabstimmung, wenige lange für den groben Sprung, und diese über alle Distanzskalen hinweg ausgewogen verteilt. Genau diese Eigenschaft werden HNSW-Graphen künstlich herstellen.

Teil 3: Von NSW zu HNSW – den Datenraum in einen navigierbaren Graphen verwandeln

Der Sprung von sozialen Netzen zu Vektoren

Die zündende Idee ist, den Datenraum selbst als Small-World-Netz zu behandeln. Man baut einen Graphen, in dem jeder gespeicherte Vektor ein Knoten ist und Kanten Knoten verbinden, die einander im Vektorraum nahe liegen. Eine Suche wird dann zur Navigation: Man startet an irgendeinem Knoten und wandert gierig immer zu demjenigen Nachbarn weiter, der dem Anfragepunkt näher liegt – so lange, bis kein Nachbar mehr näher ist als der aktuelle Knoten. Dieses lokale Minimum ist der (approximative) nächste Nachbar.

Der erste vollständige Entwurf dieser Idee, das Navigable Small World (NSW)-Verfahren von Malkov und Kollegen (2014), baute den Graphen einfach durch inkrementelles Einfügen: Jeder neue Punkt wird mit seinen M nächsten bereits vorhandenen Nachbarn verbunden. Der Clou dabei ist, dass die früh eingefügten Verbindungen tendenziell lang werden (weil der Graph noch dünn war) und die späten kurz – so entstehen von selbst die von Kleinberg geforderten Fernverbindungen. NSW funktionierte gut, hatte aber eine Schwäche: Die gierige Suche konnte in dicht besetzten Regionen viele unnötige Schritte machen, und im schlimmsten Fall degenerierte die Suchzeit auf polylogarithmische bis lineare Größenordnungen, weil es keine saubere Trennung zwischen „großen" und „kleinen" Sprüngen gab.

Die hierarchische Wendung

2016 lösten Yury Malkov und Dmitry Yashunin dieses Problem mit einer eleganten Ergänzung und tauften das Ergebnis Hierarchical Navigable Small World (HNSW) (arXiv 1603.09320; die ausgereifte Fassung erschien 2020 in den IEEE Transactions on Pattern Analysis and Machine Intelligence, Bd. 42, S. 824–836). Die Grundidee: Statt eines einzigen Graphen baut man einen Stapel von Schichten, wie die Etagen eines Hochhauses.

• Die unterste Schicht (Layer 0) enthält alle Punkte und ist am dichtesten verknüpft – hier findet die Feinsuche statt.
• Jede höhere Schicht enthält nur noch eine exponentiell schrumpfende Teilmenge der Punkte, dafür mit weit reichenden Verbindungen. Die oberste Schicht hat nur eine Handvoll Knoten, die den ganzen Raum grob überspannen.

In welcher höchsten Schicht ein Punkt landet, wird beim Einfügen zufällig bestimmt, mit einer exponentiell abfallenden Wahrscheinlichkeit. Konkret zieht man eine Zufallszahl und berechnet die Ebene über eine Formel, deren Faktor – der sogenannte Level-Multiplikator mL – idealerweise bei 1 / ln(M) liegt. Ein Punkt ist immer in allen Schichten unterhalb seiner höchsten Ebene ebenfalls präsent.

Die Skip-List-Analogie

Wer die Datenstruktur der Skip-List kennt (Pugh, 1990), erkennt HNSW sofort wieder: Eine Skip-List beschleunigt die Suche in einer sortierten verketteten Liste, indem sie über der Grundliste zusätzliche, immer dünnere „Express-Ebenen" mit Sprungzeigern einzieht. Man beginnt oben, springt in großen Schritten so weit wie möglich, fällt dann eine Ebene tiefer und verfeinert. HNSW ist im Grunde die Verallgemeinerung dieser Idee vom eindimensionalen, sortierten Fall auf einen hochdimensionalen, ungeordneten Vektorraum: Die oberen Schichten sind die Express-Ebenen für den groben Sprung, Layer 0 ist die vollständige Grundliste für die letzte Feinabstimmung. Genau diese saubere Trennung der Distanzskalen – der von Kleinberg beschriebene Mix aus langen und kurzen Verbindungen, jetzt explizit über Etagen organisiert – ist es, die HNSW die begehrte logarithmische Skalierung der Suchzeit verleiht.

Teil 4: Wie HNSW sucht und baut

Die Suche: von grob nach fein

Eine Anfrage läuft immer von oben nach unten:

1. Einstieg oben. Die Suche beginnt an einem festen Einstiegsknoten in der obersten, dünn besetzten Schicht.
2. Gieriges Absteigen. Innerhalb einer Schicht wandert man gierig zum jeweils näher am Anfragepunkt liegenden Nachbarn, bis kein Nachbar mehr eine Verbesserung bringt. Diesen lokal besten Knoten nimmt man als Einstiegspunkt in die nächsttiefere Schicht.
3. Wiederholen. So arbeitet man sich Etage für Etage nach unten, wobei jede Ebene den Suchbereich weiter einengt.
4. Feinsuche auf Layer 0. Auf der untersten Schicht wechselt der Algorithmus von der reinen Gier zu einer strahlensuchenähnlichen Erkundung: Er hält eine dynamische Kandidatenliste der bislang besten Treffer und expandiert deren Nachbarn, bis die Liste sich nicht mehr verbessert. Am Ende gibt er die besten k Kandidaten zurück.

Die Größe dieser dynamischen Kandidatenliste ist der wichtigste Suchparameter und heißt ef (bzw. efSearch, von „size of the dynamic candidate list"). Ein großes ef lässt den Algorithmus mehr Kandidaten gleichzeitig betrachten und senkt die Gefahr, in einem schlechten lokalen Minimum steckenzubleiben – das erhöht den Recall, kostet aber mehr Zeit. Ein kleines ef ist blitzschnell, aber ungenauer. Wichtig: ef muss mindestens so groß sein wie das gewünschte k.

Der Aufbau: dieselbe Suche, rückwärts genutzt

Der Index wird inkrementell durch Einfügen aufgebaut, und das Verblüffende ist, dass das Einfügen fast dasselbe Verfahren nutzt wie die Suche. Für jeden neuen Punkt:

1. Ziehe zufällig seine maximale Ebene (exponentiell abfallend).
2. Führe von oben eine Suche nach den nächsten schon vorhandenen Knoten durch, um gute Einstiegspunkte zu finden.
3. Verbinde den neuen Punkt in jeder Schicht ab seiner Maximalebene abwärts mit einer Auswahl seiner nächsten Nachbarn.

Zwei Parameter steuern den Aufbau. M ist die Anzahl der Verbindungen, die ein Knoten pro Schicht behält – gewissermaßen der Verzweigungsgrad des Graphen. (In der untersten Schicht erlaubt man oft die doppelte Menge, M0 ≈ 2·M, weil dort die Nachbarschaft am dichtesten ist.) efConstruction ist das Gegenstück zu ef beim Bauen: die Größe der Kandidatenliste, aus der beim Einfügen die besten Nachbarn ausgewählt werden. Ein hoher Wert erzeugt einen sorgfältigeren, hochwertigeren Graphen, verlängert aber die Bauzeit.

Ein oft unterschätztes Detail ist die Nachbarauswahl-Heuristik. Statt schlicht die M absolut nächsten Punkte zu verbinden, verwendet HNSW eine Heuristik, die auch auf Vielfalt der Richtungen achtet: Sie bevorzugt Nachbarn, die den Raum um den Knoten in verschiedene Richtungen aufspannen, statt mehrere sehr nahe beieinanderliegende Punkte in dieselbe Richtung zu wählen. Das verhindert, dass Cluster nur intern gut vernetzt, untereinander aber schlecht verbunden sind – ein Effekt, der sonst „Brücken" zwischen dichten Regionen zerstören und die gierige Suche in Sackgassen führen würde.

Warum das logarithmisch skaliert

Die anschauliche Begründung für die logarithmische Suchzeit: Die Zahl der Schichten wächst nur logarithmisch mit der Punktzahl (jede Ebene ist um einen konstanten Faktor dünner als die darunter). Auf jeder Schicht leistet die gierige Suche dank des begrenzten Verzweigungsgrads M nur konstant bzw. gering wachsend viel Arbeit. Das Produkt aus „logarithmisch viele Schichten" und „pro Schicht wenig Arbeit" ergibt eine Gesamtkomplexität, die in der Praxis wie O(log N) skaliert – der Grund, warum HNSW auch bei Milliarden Vektoren noch antwortet, während der lineare Scan längst kapituliert hat.

Teil 5: Die Stellschrauben – der Kompromiss zwischen Recall, Tempo und Speicher

HNSW ist kein Selbstläufer, sondern ein System aus bewusst gewählten Kompromissen. Drei Parameter spannen den Möglichkeitsraum auf, und es lohnt sich, ihre Wirkung präzise zu verstehen, weil sie in jeder Vektordatenbank – ob FAISS, pgvector, Milvus oder Qdrant – unter denselben Namen wieder auftauchen.

Die praktische Konsequenz ist erhellend: efSearch lässt sich zur Laufzeit pro Anfrage verstellen, ohne den Index neu zu bauen. Man kann also denselben Index einmal mit niedrigem ef für schnelle, tolerante Abfragen und ein andermal mit hohem ef für präzisionskritische Fälle nutzen. M und efConstruction hingegen sind in den Graphen „eingebacken" – wer sie ändern will, muss neu indizieren.

Der große Preis, den HNSW zahlt, ist Speicher. Der Graph mit all seinen Kanten muss für schnelle Zugriffe im Arbeitsspeicher liegen, und die Kanten kommen zusätzlich zu den ohnehin voluminösen Vektoren obendrauf. Ein höheres M verbessert den Recall, bläht aber genau diesen Kantenspeicher auf. Bei Milliarden von 1536-dimensionalen Vektoren wird der RAM-Bedarf schnell zum dominierenden Kostenfaktor eines ganzen Systems.

Die zweite, oft übersehene Schwäche betrifft Löschungen und Änderungen. HNSW ist von Natur aus eine „append-freundliche" Struktur: Einfügen ist billig, aber ein Knoten sauber zu entfernen ist heikel, weil er als wichtige Brücke im Graphen dienen kann. In der Praxis behilft man sich mit „tombstones" (Markieren statt echtem Löschen) und periodischem Neuaufbau – ein Kompromiss, der in schreibintensiven, sich ständig ändernden Datenbeständen unangenehm werden kann. Ich bin der Meinung, dass genau dieser Punkt – nicht die reine Suchgeschwindigkeit – in vielen Produktivsystemen der eigentliche Engpass ist und bei der Wahl einer Vektordatenbank stärker gewichtet werden sollte, als es die üblichen Benchmark-Tabellen nahelegen.

Um den Speicherhunger zu zähmen, kombiniert man HNSW in der Praxis gern mit Quantisierung: Die Produktquantisierung (PQ) komprimiert die Vektoren verlustbehaftet auf einen Bruchteil ihrer Größe, sodass der Graph über kompakten Codes navigiert und der volle Vektor nur zur finalen Genauigkeitsprüfung („re-ranking") herangezogen wird. Für Datenmengen, die selbst dann nicht in den RAM passen, gibt es plattenbasierte Verwandte wie DiskANN (Microsofts Vamana-Graph) oder das partitionierende SPANN, die den Löwenanteil des Index auf SSDs auslagern und nur wenige gezielte Leseoperationen pro Anfrage benötigen. Sie zeigen, dass die Graph-Idee nicht auf den Arbeitsspeicher beschränkt ist – aber HNSW im RAM bleibt für die meisten mittelgroßen Anwendungen der schnellste und einfachste Weg.

Teil 6: HNSW in freier Wildbahn – der Motor der Vektordatenbanken und von RAG

Wo HNSW heute steckt

Man kann kaum ein System für semantische Suche bauen, ohne HNSW zu begegnen. FAISS, Metas Open-Source-Bibliothek für Ähnlichkeitssuche, bietet HNSW als eine ihrer zentralen Indexklassen (oft in Kombination mit PQ). pgvector, die Erweiterung, die Vektorsuche direkt in PostgreSQL bringt, führte HNSW als Indextyp ein und machte ihn damit für unzählige bestehende Anwendungen ohne separate Spezialdatenbank verfügbar. Spezialisierte Vektordatenbanken wie Milvus, Qdrant und Weaviate setzen HNSW als Standard- oder Kernindex ein; Milvus etwa unterstützt daneben IVF und DiskANN für andere Betriebspunkte. Diese Allgegenwart ist kein Zufall: HNSW liefert über einen weiten Bereich von Datengrößen einen exzellenten Kompromiss aus hohem Recall und niedriger Latenz, ohne dass man den Datenraum vorher trainieren oder in Zellen zerlegen müsste.

Die Rolle in Retrieval-Augmented Generation

Der jüngste Popularitätsschub für Vektordatenbanken kommt von den großen Sprachmodellen. Ein Sprachmodell weiß nur, was in seinen Trainingsdaten stand, und es „halluziniert" bei allem, was es nicht kennt. RAG löst das, indem es dem Modell vor der Antwort relevantes Wissen unterschiebt: Die Nutzerfrage wird in einen Vektor eingebettet, per ANN-Suche werden die ähnlichsten Wissensschnipsel aus einer Vektordatenbank geholt, und diese werden dem Modell zusammen mit der Frage in den Kontext gelegt. Die Qualität der ganzen Kette hängt unmittelbar an der Retrieval-Stufe – wie es in der Literatur heißt, „lebt und stirbt RAG mit der Qualität und Geschwindigkeit des Abrufs". Genau hier arbeitet HNSW im Maschinenraum: Es ist die Komponente, die aus Millionen von Dokumentschnipseln in wenigen Millisekunden die passenden findet.

Die Embeddings selbst, mit denen HNSW hantiert, stammen übrigens meist aus genau den Architekturen, die dieser Vault an anderer Stelle behandelt: Die Transformer-Modelle erzeugen die Vektoren, deren Nähe HNSW dann durchsucht. Und die Frage, ob Nähe im Embedding-Raum wirklich Bedeutungsähnlichkeit einfängt, führt tief in die Debatte um die innere Repräsentation neuronaler Netze.

Ein ehrlicher Blick auf die Grenzen

So dominant HNSW ist, es ist kein Allheilmittel. Drei Vorbehalte sind wichtig. Erstens verschiebt die gefilterte Suche – „finde ähnliche Dokumente, aber nur aus dem Jahr 2025 und nur auf Deutsch" – das Problem erheblich, weil Filter die Navigierbarkeit des Graphen stören können; dies ist ein aktives Forschungsfeld mit eigenen Verfahren. Zweitens ist, wie erwähnt, die Dynamik (viele Löschungen) eine Achillesferse. Drittens gilt weiterhin: Approximation heißt Approximation. Für Anwendungen, in denen ein verpasster Treffer teuer ist – etwa in der forensischen Suche oder bei rechtlich bindenden Ähnlichkeitsprüfungen –, muss man den Recall bewusst hoch einstellen und im Zweifel mit exakter Nachprüfung kombinieren.

Ich bin der Meinung, dass die eigentliche konzeptionelle Schönheit von HNSW weniger im Algorithmus selbst liegt als in der zugrundeliegenden Übertragung: Ein Befund über die Navigierbarkeit sozialer Netze aus den 1960er Jahren, mathematisch geschärft um 2000, wurde ein halbes Jahrhundert später zur tragenden Infrastruktur der KI-Suche. Das ist ein Musterbeispiel dafür, wie Grundlagenforschung an einer scheinbar entlegenen Frage – „Wie finden Menschen kurze Wege in ihrem Bekanntennetz?" – Jahrzehnte später einen milliardenschweren Anwendungsfall trägt.

Erkenntnis zum Mitnehmen

Die zentrale Lektion von HNSW ist eine über den Umgang mit Unmöglichkeit. In hohen Dimensionen ist die exakte nächste-Nachbarn-Suche praktisch nicht bezahlbar – der Fluch der Dimensionalität lässt sich nicht wegprogrammieren. Statt gegen diese Wand zu rennen, tauscht HNSW eine winzige, messbare und einstellbare Ungenauigkeit gegen einen gewaltigen Geschwindigkeitsgewinn: Aus linearer Suche über Milliarden Punkte wird eine logarithmische Wanderung durch einen navigierbaren Graphen.

Für die eigene Praxis heißt das zweierlei. Erstens: Wenn du semantische Suche, Empfehlungen oder RAG baust, denke in den drei Größen M, efConstruction und efSearch – und merke dir, dass nur die letzte zur Laufzeit anpassbar ist, während die ersten beiden den Index prägen. Zweitens, und allgemeiner: Frage bei jedem teuren exakten Problem, ob du wirklich Exaktheit brauchst oder ob eine kontrollierte Approximation mit einer klaren Recall-Kennzahl genügt. Oft ist die pragmatische Näherung nicht der faule Kompromiss, sondern die einzige Lösung, die überhaupt skaliert.

Eine Frage zum Nachdenken

In welchen deiner eigenen Systeme behandelst du eine Suche oder einen Abgleich noch als exaktes Problem – und würde eine bewusst zugelassene, gemessene Ungenauigkeit (mit einem definierten Recall-Ziel) dort einen Geschwindigkeits- oder Kostensprung ermöglichen, den du bisher für unmöglich gehalten hast? Und umgekehrt: Wo wäre selbst ein Recall von 99 % ein inakzeptables Risiko?

Querverweise im Vault

• Aufmerksamkeit ist alles: Der Transformer, Self-Attention und die Architektur moderner KI – die Architektur, die die Embedding-Vektoren erzeugt, die HNSW durchsucht.
• Der Geist in der Maschine: Wie man ein neuronales Netz von innen liest – die Frage, was ein Vektor im hochdimensionalen Raum überhaupt „bedeutet".
• Wie groß ist groß genug? Skalierungsgesetze, Chinchilla und die Vermessung der KI – die Skalengesetze der Modelle, deren Wissen RAG mit externem Abruf ergänzt.
• Der Ring, der die Last verteilt: Consistent Hashing und die Kunst des sanften Umzugs – wie man Vektor-Indizes über viele Maschinen verteilt (Sharding).
• Schreiben statt Suchen – Log-Structured Merge-Trees und die Umkehrung der Datenbank – eine verwandte Speicher-Engine und das gleiche Löschen-per-Tombstone-Problem.
• Einigkeit ohne Abstimmung: CRDTs und die Kunst der konfliktfreien Replikation – die Replikation verteilter Datenbestände, auf denen auch Vektordatenbanken aufsetzen.

Quellen

• Malkov, Yashunin: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320, 2016; IEEE TPAMI 42(4):824–836, 2020): https://arxiv.org/abs/1603.09320
• Malkov, Ponomarenko, Logvinov, Krylov: Approximate nearest neighbor algorithm based on navigable small world graphs, Information Systems 45 (2014) – der NSW-Vorläufer.
• Kleinberg: Navigation in a small world, Nature 406, 845 (2000): https://www.researchgate.net/publication/12350387_Kleinberg_J_Navigation_in_a_small_world_Nature_406_845
• Watts, Strogatz: Collective dynamics of 'small-world' networks, Nature 393 (1998).
• Milgram: The Small-World Problem, Psychology Today (1967) – Ursprung der „sechs Grade".
• Pinecone: Hierarchical Navigable Small Worlds (HNSW) – anschauliche Erklärung: https://www.pinecone.io/learn/series/faiss/hnsw/
• Zilliz/Milvus FAQ: Key configuration parameters for an HNSW index (M, efConstruction, efSearch): https://zilliz.com/ai-faq/what-are-the-key-configuration-parameters-for-an-hnsw-index-such-as-m-and-efconstructionefsearch-and-how-does-each-influence-the-tradeoff-between-index-size-build-time-query-speed-and-recall
• Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement (arXiv 1610.02455) – zum Fluch der Dimensionalität und Verfahrensvergleich: https://arxiv.org/pdf/1610.02455
• Subramanya et al.: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (NeurIPS 2019) – der plattenbasierte Vamana-Graph.
• Chen et al.: SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (arXiv 2111.08566): https://arxiv.org/pdf/2111.08566
• Crunchy Data: HNSW Indexes with Postgres and pgvector: https://www.crunchydata.com/blog/hnsw-indexes-with-postgres-and-pgvector

← All articles