Im Inneren von Vektordatenbanken: IVF, Bäume, HNSW und Produktquantisierung

Begriffe wie RAG, Vektordatenbanken, Abrufverfahren und Chunking werden ständig verwendet und klingen komplizierter, als sie tatsächlich sind. Dieser Artikel beginnt mit Vektordatenbanken: Was sie speichern und wie die Suche darin eigentlich funktioniert.

Woher die Vektoren stammen

Embedding-Modelle, die anhand riesiger Textsammlungen trainiert wurden, wandeln die Bedeutung eines Satzes in eine Liste von Zahlen um. Einige davon sind in der Cloud verfügbar, wie OpenAI’s Text-Embeddings und Google’s Gemini-Embedding-Modelle. Andere laufen lokal, wie die Qwen3-Embedding-Familie in den Größen 8B, 4B und 0,6B oder Jina’s v5-text-small-Modell mit etwa 677 M Parametern. Wenn man seinen Text durch eines dieser Modelle leitet, erhält man einen Vektor, den man speichern und später abrufen kann.

Das Vokabular

Einige wenige Begriffe tauchen in jeder Vektordatenbank immer wieder auf:

• Sammlung. Ein Namensraum, der Punkte enthält, die eine feste Dimension und eine gemeinsame Abstandsmetrik teilen.
• Punkt. Ein Vektor zusammen mit seiner ID und einem Metadaten-Teil.
• Abstandsmetrik. Die Methode zur Messung der Nähe, in der Regel Kosinusähnlichkeit, Skalarprodukt oder euklidischer Abstand.
• Upsert. Die Operation, bei der Daten eingefügt werden, indem neue Punkte hinzugefügt und vorhandene aktualisiert werden.
• Suche. Die Abfragemethode, für die alles andere bestimmt ist.

Die Intuition: exakt versus annähernd

Die naive Methode, um unter 10.000 oder mehr Vektoren die mit einer Abfrage verbundenen Vektoren zu finden, besteht darin, die Kosinusähnlichkeit mit jedem gespeicherten Vektor zu berechnen und die k besten zu behalten. Das Ergebnis ist die Menge der exakten nächsten Nachbarn. Bei Millionen von Vektoren wird jedoch diese brute-Force-Suche aufgrund von Speicher- und Zeitbeschränkungen unpraktisch. Deshalb wechselten Systeme auf die Suche nach annähernden nächsten Nachbarn (ANN), bei der ein geringer Genauigkeitsverlust im Austausch für eine erhebliche Geschwindigkeitssteigerung in Kauf genommen wird.

Dieser Kompromiss kann auf zwei grundlegende Weisen erreicht werden. Indexierung verringert die Anzahl der notwendigen Vergleiche. Quantisierung senkt die Kosten pro Vergleich. Gemeinsam bilden sie das Werkzeugset für ANN.

Indexierung, Option eins: Clustering mit IVF

Ein umgekehrter Dateinachweis (IVF) teilt die Vektoren in Cluster auf, von denen jeder einen Schwerpunkt hat. Zunächst wird die Abfrage nur mit den Schwerpunkten verglichen. Sobald der nächstgelegene Cluster gefunden wurde, wird die Abfrage ausschließlich mit den Vektoren in diesem Cluster verglichen, und die besten k Ergebnisse werden ausgewählt.

Die Schwächen sind bekannt zu machen:

• Nachbarn in der Nähe der Zellgrenzen werden übersehen. Wenn die tatsächliche Übereinstimmung in einer Zelle liegt, die nicht überprüft wurde, wird sie niemals gefunden. Das Überprüfen mehrerer Zellen hilft, verlangsamt aber die Suche und untergräbt den Zweck.
• Die Qualität nimmt mit Datenänderungen ab. Die Cluster werden zur Erstellung festgelegt, sodass neue Daten ständig in alten Zellen landen und die Suchqualität nachlässt. Regelmäßige Neuerstellungen sind erforderlich.

Ungleichmäßige Cluster machen die Geschwindigkeit unvorhersehbar. Einige Zellen wachsen riesig an, während andere klein bleiben, wodurch eine Abfrage, die in einer großen Zelle landet, langsam abläuft, während eine Abfrage, die in einer kleinen Zelle landet, schnell ist.

Es werden im Voraus Trainingsdaten benötigt. Der Index kann erst dann erstellt werden, wenn genügend Daten vorhanden sind, um sinnvolle Cluster zu bilden, was für Anwendungen, die von Null an beginnen, problematisch ist.

Zwei Einstellungen sind schwierig zu optimieren. Sowohl die Anzahl der Cluster als auch die Anzahl der pro Abfrage durchsuchten Elemente beeinflussen die Ergebnisse, und falsche Werte führen zu langsamen oder ungenauen Suchergebnissen.

Hohe Dimensionen verwässern die Cluster. Bei sehr langen Vektoren werden die Cluster unklar, wodurch die Genauigkeit pro durchgeführter Aufgabe hinter der von HNSW zurückbleibt.

In einem Satz: IVF ist einfach und spart Speicher, verliert aber bei Rändern an Genauigkeit und leidet unter häufigen Aktualisierungen, weshalb es in der Milliarden-Skala in Kombination mit Produktquantisierung hervorragt, während HNSW bei Echtzeit-Suchen mit hoher Genauigkeit vorteilhaft ist.

Indexierung, Option zwei: baumbasierte Partitionierung

Die baumbasierte Indexierung übernimmt das Konzept der binären Suche. Anstatt die Abfrage mit jedem Vektor zu vergleichen, wird der Speicherbereich immer wieder halbiert, und nur die Hälfte, die die Abfrage enthält, wird untersucht.

Zum Erstellen des Indexes nimmt man den gesamten Bereich und teilt ihn mit einer Trennlinie, teilt anschließend jede Hälfte erneut, bis jede kleine Region nur noch wenige Vektoren enthält. Jede Region ist ein Blatt. In zwei Dimensionen könnte die erste Teilung entlang der x-Achse erfolgen, die nächste entlang der y-Achse und so weiter. Alle Teilungen bilden einen Binärbaum, bei dem jeder Knoten eine Ja-oder-Nein-Frage darstellt, wie zum Beispiel ob x unter 5 liegt, wobei die Blätter am unteren Ende liegen.

Wenn eine Abfrage eintrifft, beginnt man am Wurzelknoten und beantwortet nacheinander eine Frage: Links oder rechts dieser Teilung? Jede Antwort eliminiert die Hälfte des verbleibenden Bereichs. Nach etwa log n Fragen, ungefähr 20 für eine Million Vektoren, erreicht man ein kleines Blatt und vergleicht die Abfrage mit den wenigen Vektoren darin.

Es gibt jedoch einen Haken. Der wahre nächste Nachbar könnte sich direkt jenseits einer Trennlinie befinden – in geringer Entfernung, aber in einem anderen „Blatt“ – und ein einzelner Baum würde ihn niemals erkennen. Daher erstellen Bibliotheken wie Spottys Annoy viele Bäume, wobei jeder Baum unterschiedliche zufällige Aufteilungen verwendet. Jeder Baum schlägt Kandidaten vor, diese Vorschläge werden zusammengeführt und die besten ausgewählt. Was ein Baum übersehen hat, bemerkt in der Regel ein anderer.

Die Nachteile:

• Das Grenzproblem ist schlimmer als bei IVF. Bei IVF bedeutet ein Verpassen der Grenze, dass eine weitere Zelle überprüft werden muss. In einem Baum führt ein falscher Weg in der Nähe der Spitze die Suche in eine völlig andere Region.
• Die Lösung kostet Speicherplatz und Rechenzeit. Ein Wald aus 50 Bäumen bedeutet, dass der Index 50 Mal gespeichert und bei jeder Abfrage 50 Mal durchsucht werden muss, wodurch Genauigkeit auf Kosten von Ressourcen erreicht wird.

Lange Vektoren überwinden dieses Problem. Bäume funktionieren gut in 2D, 3D, Karten und Spielen. Moderne Embeddings haben Hunderte oder Tausende von Dimensionen, wobei eine Trennlinie kaum etwas Bedeutendes unterscheidet, da Punkte auf gegenüberliegenden Seiten nahezu gleich weit entfernt sein können. Das ist der Hauptgrund, warum diese Methode für die Embedding-Suche an Bedeutung verloren hat.

Der Index ist statisch. Bäume werden einmal aus vorhandenen Daten erstellt und können keine neuen Vektoren sauber aufnehmen. Annoy benötigt beispielsweise einen vollständigen Neubau, um Daten hinzuzufügen, was sich schlecht für sich ändernde Sammlungen eignet.

Im Allgemeinen wird sie übertroffen. Bei gleicher Genauigkeit ist HNSW schneller, und bei gleicher Speicherkapazität lässt sich IVF mit Produktquantisierung weiter skalieren. Bäume finden hauptsächlich in veralteten Systemen sowie dort Verwendung, wo kleine, im Speicher abrufbare Indexdateien wichtig sind.

Kurz gesagt sind Bäume einfach und schnell zu erstellen, doch hochdimensionale Embeddings zerstören ihre Struktur und ermöglichen keine Aktualisierungen, weshalb sie heute hauptsächlich als Zwischenstufe für Erklärungen dienen und keine Wahl für die Produktion sind.

Indexierung, Option drei: HNSW

Hierarchical Navigable Small Worlds, kurz HNSW, ist die Technik hinter den meisten Vektordatenbanken. Sie organisiert Vektoren als Graph mit mehreren Ebenen. Die oberen Ebenen enthalten nur wenige Vektoren mit langreichweiten Verbindungen, ähnlich Autobahnen zwischen Städten, während die unteren Ebenen allmählich mehr Vektoren mit kürzeren Verbindungen enthalten, bis hin zur untersten Ebene, die alle Vektoren enthält.

Die Suche beginnt an der Oberfläche und bewegt sich gierig zu dem Nachbarn, der der Abfrage am nächsten ist. Wenn kein Nachbar näher liegt, geht sie eine Ebene tiefer und wiederholt den Vorgang von dort aus mit feinerer Gliederung der Verbindungen. In der untersten Ebene erkundet sie ein größeres Umfeld und gibt die besten Ergebnisse zurück. Lange Sprünge überbrücken große Entfernungen schnell, während kurze Schritte die Ergebnisse präzisieren – deshalb bleibt die Anzahl der Vergleiche auch bei riesigen Datensätzen gering.

Mehrere Parameter steuern das Gleichgewicht zwischen Geschwindigkeit und Genauigkeit:

• M legt fest, wie viele Verbindungen jeder Vektor beibehält. Mehr Verbindungen verbessern Genauigkeit und Vollständigkeit, kosten aber mehr Speicherplatz.
• efConstruction bestimmt, wie breit das Suchgebiet während des Aufbaus des Graphen ist. Höhere Werte ergeben einen besseren Graphen, führen aber zu einem langsameren Aufbau.

efSearch bestimmt, wie breit die Liste der Ergebnisse zum Zeitpunkt der Abfrage ist. Eine Erhöhung dieses Wertes erhöht sowohl die Genauigkeit als auch die Latenz.

Wenn man sieht, wie eine Abfrage durch die verschiedenen Ebenen geht und wie diese Einstellungen den Ablauf beeinflussen, wird klar, wie sich Änderungen an ihnen auf das Suchverhalten auswirken.

Quantisierung: Jede Vergleich wird günstiger

Das Indexieren verringert die Anzahl der Vergleiche. Die Quantisierung senkt den Kosten pro Vergleich. Ein einzelner 1536-dimensionaler Vektor aus 32-Bit-Flotten nimmt 1536 mal 4, also 6144 Bytes ein. Für eine Milliarde Vektoren bedeutet das Terabyte an Speicherplatz – weitaus mehr, als in der RAM untergebracht werden kann.

Produktquantisierung

Die Quantisierung von Produkten teilt jeden großen Vektor in kleinere, gleich große Abschnitte auf. Ein 16-dimensionaler Vektor könnte beispielsweise in vier 4-dimensionalen Abschnitte unterteilt werden. Für jede Abschnittsposition wird ein Codebuch anhand der gespeicherten Daten mit 256 Einträgen trainiert, wobei jeder Eintrag einen typischen Teilvektor darstellt. Jeder Abschnitt wird anschließend durch die Nummer seines nächsten Codebuch-Eintrags ersetzt, wofür lediglich ein Byte benötigt wird.

So wird ein Vektor, der ursprünglich Tausende von Bytes in Anspruch nahm, zu einer kurzen Folge kleiner Ganzzahlen. Zur Suche wird die Abfrage auf dieselbe Weise aufgeteilt, und die Entfernungen zu den Codebuch-Einträgen werden einmal berechnet und bei der Abfrage jedes gespeicherten Vektors wiederverwendet. Die Berechnung ist stark annähernd, doch die Geschwindigkeitssteigerung und der Speichereinsparungseffekt sind erheblich.

Die Auswahl unter ihnen

Ein kurzer Vergleich fasst alles zusammen:

• IVF ist einfach und erfordert wenig Speicher. Kombinieren Sie es mit Produktquantisierung für sehr große, statische Sammlungen.
• Bäume sind leicht verständlich und kostengünstig zu erstellen, eignen sich aber nur für niedrige Dimensionen und unveränderliche Daten.
• HNSW bietet hohe Genauigkeit und schnelle Suchfunktionen in Echtzeit, kommt aber mit höherem Speicherverbrauch daher.
• Produktquantisierung komprimiert Vektoren und beschleunigt die Distanzberechnungen, führt dabei zu einem kontrollierten Verlust an Präzision, und kann mit den oben genannten Indizes kombiniert werden.

Diese Abwägungen zu kennen hilft Ihnen dabei, zu entscheiden, wann eine annähernde Suche angebracht ist, welcher Algorithmus zu einer bestimmten Arbeitslast passt und wann brute force weiterhin die richtige Lösung ist – beispielsweise bei kleinen Sammlungen, bei denen Genauigkeit wenig kostet.