Fünf Methoden zur Indizierung von Vektoren für RAG, getestet an einer Million Wikipedia-Embeddings

Fünf Methoden zur Indizierung von Vektoren für RAG, getestet an einer Million Wikipedia-Embeddings: flat, IVFFlat, HNSW, BM25-Hybrid und DiskANN, zusammen mit Werten für Latenz und Recall.

Verlag: REACTAPP.TOPAuf dieser Website hinzugefügt 28. Okt. 20269 Min. Lesezeit1993 Wörter

Quellen: **Scaling RAG Infrastructure: The Journey from Flat Search to DiskANN**

Ein RAG-System hängt von der Suchfunktion ab – und diese wird schwieriger, je größer das Korpus wird. In dieser Übersichtsbeschreibung werden fünf Methoden zum Indizieren von Vektoren anhand eines echten Experiments verglichen, sodass die Wahl der Methode auf Zahlen und nicht auf Gewohnheit beruht.

Was Vektorindizierung ist und warum sie wichtig ist

Die Vektorindizierung ist eine Methode, um eine große Anzahl von Vektoren so zu organisieren, dass ähnliche Vektoren schnell gefunden werden können, ohne den Abfragesatz mit jedem einzelnen Vektor vergleichen zu müssen. Relationale Datenbanken verfügen über ähnliche Ansätze wie Bucketing und Z-Ordering, die die Menge an Daten reduzieren, die eine Abfrage durchsuchen muss. Vektordatenbanken wenden spezialisierte Strukturen an, um im selben Sinne den Suchraum zu verkleinern.

Eine genaue, niedrigzeitige Abrufung ist die Grundlage jeder skalierbaren RAG-Lösung. Schon große Anwendungen sind davon abhängig: Amazon zieht Informationen aus Katalogen mit Millionen von Produkten ab, Netflix aus Tausenden von Titeln, die für ein globales Publikum personalisiert werden, und X aus Milliarden von Beiträgen und Konten. Der Datenaufkommen beträgt mittlerweile Terabyte pro Tag, weshalb die Skalierbarkeit nicht erst später berücksichtigt werden darf – sie muss bereits bei der ersten Architekturplanung integriert sein.

Jede der unten aufgeführten Methoden wird anhand von drei Kriterien bewertet:

Verzögerung: wie schnell der Index die Top-K-Ergebnisse liefert.
Abrufgenauigkeit: inwieweit die Ergebnisse mit denen einer exakten Suche übereinstimmen.

Wartungskomplexität: wie aufwendig es ist, den Index auf dem neuesten Stand zu halten. Die zugrunde liegenden Daten einer RAG-Anwendung verändern sich selten nicht, und die Daten müssen möglicherweise bereits alle 24 Stunden aktualisiert werden, weshalb der Index innerhalb dieses Zeitraums ohne große ingenieurtechnische Anstrengungen aktualisierbar sein muss.

Die Testumgebung

Im Experiment wurden die ersten eine Million Zeilen des Datensatzes CohereLabs/wikipedia-2023-11-embed-multilingual-v3 verwendet, eine Größenordnung, die groß genug ist, um Unterschiede zwischen den Methoden sichtbar zu machen. Die Abfragen wurden mit mxbai-embed-large verarbeitet, welches 1.024-dimensionalen Vektoren erzeugt, die mit den Embeddings des Datensatzes übereinstimmen. Die Indizes wurden in PostgreSQL mithilfe von pgvector erstellt.

Method 1: flache Suche

Die flache Suche, auch als Brute-Force-Suche bezeichnet, ist die einfachste Option. Es wird die Ähnlichkeit zwischen der Abfrage und jedem Vektor berechnet, anschließend werden die besten Ergebnisse behalten.

Verzögerung: die schlechteste im Vergleich, da jeder Vektor verglichen wird. Die Zeit nimmt linear mit der Anzahl der Vektoren zu.
Genauigkeit: die beste, da die Suche präzise ist und die tatsächlich nächsten Vektoren zurückgibt.
Wartung: keine, da es keinen Index gibt.

Die durchschnittliche Verzögerung im Test betrug 6,25 Sekunden. Ein großer Einzelhändler würde das sofort ablehnen, genauso wie ein kleines Startup.

Method 2: IVFFlat

Inverted File Flat ist eine annähernde Technik des nächsten Nachbarn. Sie verwendet K-Means, um den Vektorraum in Cluster aufzuteilen. Anstatt alles durchzusuchen, findet sie die zu der Abfrage nächstgelegenen Mittelpunkte und durchsucht nur diese Cluster, wobei innerhalb von ihnen genaue Entfernungsrechnungen durchgeführt werden.

Der Ablauf sieht wie folgt aus:

Query → closest centroids → search selected clusters → Top-K

In pgvector werden zwei Einstellungen zur Steuerung verwendet. Die Anzahl der Clustern, die als Listen bezeichnet werden, wird im Voraus festgelegt; in dem Test wurden 1.000 Listen verwendet. Zum Zeitpunkt der Abfrage entscheidet eine zweite Einstellung, die Probes, darüber, wie viele dieser Listen durchsucht werden. Wenn Probes auf 10 gesetzt ist, werden die zehn Listen durchsucht, deren Centroiden dem Abfragedaten am nächsten liegen.

Latenz war akzeptabel. Bei einer Million Vektoren und 1.000 Clustern wurden die Abfragen in höchstens einer Sekunde abgeschlossen.

Genauigkeit war aus zwei Gründen schlecht. Erstens gibt es das Problem der Grenzen: Die Nähe wird anhand der Centroiden und nicht anhand der tatsächlichen Vektoren gemessen, wodurch einige der am nächsten liegenden Vektoren übersehen werden, wenn sie zu einem Cluster gehören, dessen Centroid zufällig weiter vom Abfragedaten entfernt liegt. Zweitens begrenzt Probes die Suche auf eine feste Anzahl von Clustern, sodass relevante Vektoren in unersuchten Clustern niemals berücksichtigt werden.

Die Erhöhung der Anzahl der Proben von 10 auf 500 führte zu einer geringfügigen Steigerung der Latenz in diesem Test. Es gibt jedoch keine Möglichkeit, im Voraus zu wissen, ob 10, 100, 500 oder 900 Proben die beste Wiedererkennungsrate liefern werden, da die tatsächlichen Nachbarn in einem übersprungenen Cluster liegen könnten. Die Verwendung aller 1.000 Proben macht den Sinn zunichte, da dadurch der Index wieder zu einer Brute-Force-Lösung wird.

Wartung war ebenfalls mangelhaft. Der Aufbau des Index für mehr als eine Million Vektoren dauerte etwa 2,37 Minuten, was akzeptabel ist. Das Problem tritt bei Aktualisierungen auf: Bei indexbasierten Methoden, die auf dem Mittelpunkt beruhen, muss der Index möglicherweise neu berechnet oder die Vektoren neu indiziert werden, sobald eine neue Datenserie eintrifft. Bei Milliarden von Vektoren lohnt sich dieser technische Aufwand möglicherweise nicht.

Für diesen Anwendungsfall war das Verhältnis zwischen Latenz und Genauigkeit einfach nicht akzeptabel. Die nächste Frage ist, ob eine andere Methode die Latenz verringern und dennoch bessere Ergebnisse liefern kann.

Method 3: HNSW

Ein Postbote, der nach einem Haus sucht, liefert eine gute Analogie. Bei einer Adresse durchsucht er nicht jede Straße. Er nimmt die Hauptautobahnen in die richtige Region, wo die Verbindungen spärlich sind, aber große Entfernungen überbrücken. Danach wechselt er zu den Hauptstraßen, wo das Netz dichter ist. Schließlich geht er über die örtlichen Straßen, wo das Netz am dichtesten ist, bis er zur genauen Haustür gelangt.

HNSW, abgekürzt für hierarchical navigable small world, funktioniert auf dieselbe Weise. Es beginnt mit spärlichen, langstreckigen Verbindungen auf den oberen Ebenen und arbeitet sich durch zunehmend dichtere Verbindungen auf den unteren Ebenen vor, bis es die nächsten Vektoren erreicht. Wenn die Straßenhierarchie gut organisiert ist, führt die Suche direkt zum Ziel, und eine gute Konstruktion führt zu einer guten Trefferquote.

Latenz war erneut akzeptabel – höchstens eine Sekunde bei einer Million Vektoren.

Genauigkeit war gut, wobei es Einschränkungen aufgrund der Konfigurationsparameter gibt. Der Index wird mit einer Aussage in dieser Form erstellt:

    CREATE INDEX wikipedia_embeddings_hnsw_idx
    ON wikipedia_embeddings
    USING hnsw (emb vector_cosine_ops)
    WITH (
        m = 16,
        ef_construction = 64
    );

Diese Angabe erstellt den Index über dem Korpus. Drei Parameter sind wichtig:

m ist die Anzahl der Nachbarn, mit denen jeder Vektor im Graphen verbunden sein kann. Er bestimmt die Verbindbarkeit und Dichte.
ef_construction ist die Anzahl der potenziellen Nachbarn, die bei der Erstellung berücksichtigt werden. Er steuert den Suchraum während des Aufbaus.
ef_search begrenzt den Suchraum zum Zeitpunkt der Abfrage, da er festlegt, wie viele Kandidaten bei der Beantwortung untersucht werden.

Wie wählt der Graph seine m Verbindungen aus? Bei einer Million Vektoren hat jeder 999.999 potenzielle Nachbarn. Der Ersteller wählt nicht zufällig. Er bewertet die Kandidaten anhand der Entfernung sowie einer Heuristik zur Nachberauswahl und behält eine kleine Gruppe von etwa 16 Nachbarn bei, die zum Navigieren im Graphen nützlich sind.

Warum führt das zu höherer Genauigkeit?

Eine kleine Anzahl nützlicher Nachbarn pro Vektor bildet die „Autobahnen“ des Graphen.
Diese Verbindungen werden ausgewählt, um den Graphen verbunden und leicht zu navigieren zu halten.
Während einer Abfrage folgt die Suche Schritt für Schritt diesen Pfaden zu Vektoren, die der Abfrage mehr ähneln.
Da der Graph effiziente Wege in die relevante Region bietet, ist es wahrscheinlicher, die wahren nächstgelegenen Nachbarn zu finden.
Durch eine sorgfältige Konstruktion und Navigation wird die Genauigkeit erhöht, während eine ausführliche Vergleichsanalyse vermieden wird.

Kurz gesagt: Der Graph wird absichtlich und nicht zufällig konstruiert. Die Einstellungen m und ef_construction bestimmen, wie er aufgebaut wird, was wiederum den Recall beeinflusst.

Wartung ist der Punkt, an dem HNSW nachlässt. Die Erstellung des Index für über eine Million Vektoren dauerte erstaunliche 37 Minuten. Bei Aktualisierungen kann neues Datenmaterial hinzugefügt werden, solange das ursprüngliche Datensatz groß genug ist und die gesamte Datenverteilung gut widerspiegelt, ohne dass ein Neubau erforderlich ist. Wenn jedoch die Menge der neu hinzukommenden Daten im Verhältnis zum ursprünglichen Datensatz zunimmt, kann sich die Verteilung verändern, der Graph wird weniger optimal und letztendlich ist ein Neubau notwendig. Das tritt seltener auf als bei IVF, kommt aber dennoch vor.

Aufgrund der prinzipiellen Konstruktion des Graphen ist er trotz der zusätzlichen Entwicklungsarbeit eine bessere Option als IVF. Das Gleichgewicht zwischen Latenz und Trefferquote ist akzeptabel, wenn auch nicht herausragend.

Method 4: BM25 plus Vektorabfrage

Manchmal ist die offensichtliche Antwort die richtige. Während die Aufmerksamkeit immer komplexeren Ansätzen gilt, existiert bereits seit dreißig Jahren ein einfacher, effektiver Ansatz. BM25 ist ein lexikalischer Ranking-Algorithmus, der Dokumente danach bewertet, wie oft die Abfrageschlüsselwörter vorkommen, wie selten diese Wörter im gesamten Korpus sind und wie lang das Dokument ist.

Die Funktionsweise:

Dokumente werden in Schlüsselwörter aufgeteilt, und ein umgekehrter Index verknüpft jedes Schlüsselwort mit den Dokumenten, die es enthalten.
Die Schlüsselworthäufigkeit misst, wie oft ein Schlüsselwort in einem bestimmten Dokument vorkommt.
Die umgekehrte Dokumentenhäufigkeit misst, wie selten oder häufig ein Schlüsselwort in der gesamten Sammlung vorkommt.
Ein Schlüsselwort, das in einem Dokument häufig, aber insgesamt selten vorkommt, erhält eine höhere Bedeutung.
BM25 kombiniert diese Faktoren mit der Länge des Dokuments, um die Relevanz zu bewerten.
Zur Abfrageszeit werden die Abfrageschlüssel im umgekehrten Index gesucht, gegen die passenden Dokumente bewertet, und die am höchsten bewerteten Dokumente zurückgegeben.

Die Formel an sich ist nicht besonders ansprechend, aber die Idee ist einfach: Die am besten zu den Suchbegriffen passenden Dokumente finden.

Sobald diese Dokumente abgerufen wurden, ist der Suchraum erheblich geschrumpft. Eine einfache Vektorabfrage in dieser kleinen Menge findet anschließend die besten Ergebnisse. Das ist eine hybride Suchmethode.

Eine Vorsichtsmaßnahme: In der ersten Phase werden genaue Schlüsselwörter gesucht, wodurch Rechtschreibfehler des Benutzers problematisch sein können. Ein durch KI unterstützter Normalisierungsprozess, der vor Beginn der Suche Tippfehler und Varianten korrigiert, löst dieses Problem mühelos.

Latenz. Der vektorbasierte Teil antwortet in den erwarteten Millisekunden, doch der lexikalische Teil benötigte in dieser Konfiguration etwa 12 bis 14 Sekunden. Caching kann dieses Problem lösen, wobei die erste Anfrage weiterhin langsam bleibt. Caching verdient hier eine Erwähnung, da es insbesondere für BM25 besonders gut funktioniert: Genaue Dokumente werden durch das Abgleichen von Schlüsselwörtern abgerufen. Bei anderen Indexierungsverfahren muss das Caching semantisch sein, was einen Ähnlichkeitsschwellenwert erfordert und möglicherweise zu einer gewissen Abnahme der Suchgenauigkeit führt.

Wartung. Keine, da kein vektorbasierter Index erstellt wird.

In der Praxis ist bei den meisten KI-Produkten mit bis zu etwa 50.000 Dokumenten die hybride Suche mit BM25 eine zuverlässige Wahl, da sie bei dieser Größenordnung ein gutes Gleichgewicht zwischen Latenz und Genauigkeit bietet.

Method 5: DiskANN und das Vamana-Graph

Diese Methode ist abstrakter als die Embeddings selbst. Der Prozess erfolgt in acht Schritten:

Beginnen Sie mit der umfangreichen Sammlung von Vektoren, die eine effiziente Suche erfordern.
Erstellen Sie ein Graphenmodell, indem Sie jeden Vektor mit einer sorgfältig ausgewählten Gruppe von Nachbarn verbinden. Dies ist der Vamana-Graph.
Speichern Sie den Graphen auf der Festplatte und nicht im Arbeitsspeicher, damit mit Datensätzen um ein Vielfaches größer als der RAM umgegangen werden kann.
Wenn eine Abfrage eintrifft, starten Sie von einem Eingangspunkt im Graphen aus.
Folgen Sie den Verbindungen zwischen Vektoren und bewegen Sie sich Schritt für Schritt in Richtung der Bereiche in der Nähe der Abfrage.
Laden Sie im Laufe der Suche die benötigten Knoten von der SSD.
Nachdem Sie ausreichend Teile des Graphen untersucht haben, sammeln Sie eine kleine Anzahl vielversprechender Kandidaten.
Vergleichen Sie diese Kandidaten genauer und geben Sie die K-K- nächsten Ergebnisse zurück.

Der entscheidende Punkt ist, dass das Navigationsgraphenmodell auf der SSD und nicht im RAM gespeichert wird, wodurch die Größe weniger ein Limit darstellt als die Speicherkosten.

Führen Sie zunächst ein Metadaten-Filtering durch

Eine Technik verdient eine besondere Erwähnung und sollte vor allen oben genannten Methoden kommen. Das Filtern von Metadaten basiert auf demselben Prinzip wie das Bucketing in relationellen Datenbanken: Das Kandidatenset wird bereits vor dem Ausführen einer Vektorabfrage durch Attribute wie Kategorie, Datum oder Eigentümer eingegrenzt.

Welche Methode wählen?

Brute Force: Kleine bis mittlere Datensätze, bis zu etwa 20.000 Dokumenten. Beste Genauigkeit bei akzeptabler Latenz.
BM25 in Kombination mit Vektorabfrage: Mittlere Datensätze, etwa 20.000 bis 100.000 Dokumente. Eine ausgezeichnete Balance zwischen lexikalischer und semantischer Suche.
HNSW: Große Datensätze mit Millionen von Vektoren oder mehr. Gute Latenz und Genauigkeit – auf Kosten einer höheren Konfigurationskomplexität.
DiskANN und Vamana: wenn RAM teuer wird. SSDs ermöglichen sehr große Kapazitäten, wodurch der Speicher selbst – und nicht die Größe – die Beschränkung darstellt.
IVFFlat: große Datensätze mit etwa einer bis zehn Millionen Vektoren, sofern sich die Datenverteilung gut klustert. Andernfalls leidet die Genauigkeit der Ergebnisse.