Mit nur zwei Codezeilenänderungen steigt die Effizienz von RAG um 30 %. Es ist für verschiedene Aufgaben geeignet und kann auf Anwendungen mit einer Datengröße von hunderten Milliarden erweitert werden.

Mit nur zwei Codezeilenänderungen steigt die Effizienz der Vektorretrieval in RAG um 30%!

Es eignet sich nicht nur für verschiedene Aufgaben wie "Text-zu-Text-Suche", "Bild-zu-Bild-Suche", "Text-zu-Bild-Suche" und "Rückruf in Empfehlungssystemen"; außerdem verfügt es über eine gute Erweiterbarkeit und eignet sich für Massenanwendungen im Milliarden- und Billionenbereich.

Das Team von Gao Yunjun und Ke Xiangyu der Zhejiang-Universität hat sich mit Fu Cong, einem Experten im Bereich der Vektorretrieval, zusammengeschlossen und eine neue Open-Source-Methode namens PSP (Proximity graph with Spherical Pathway) entwickelt, die zwei große Probleme in der RAG überwindet.

Einfach ausgedrückt: Die gängigen Methoden zur Vektorretrieval basieren auf der euklidischen Distanz und betrachten hauptsächlich, "wer am nächsten zu Ihnen ist"; manchmal braucht die KI jedoch eher die "semantische Relevanz", d. h. das maximale innere Produkt und die Ähnlichkeit.

Frühere Methoden zur inneren Produktretrieval erfüllen nicht die mathematische Dreiecksungleichung wie die Methoden zur euklidischen Distanzretrieval, weshalb viele alte Methoden nicht funktionieren.

PSP hat festgestellt, dass man mit kleinen Änderungen auch in alten Graphenstrukturen die optimale Lösung für das maximale innere Produkt finden kann.

Außerdem hat PSP eine Strategie zum vorzeitigen Stoppen implementiert, die entscheiden kann, ob die Suche vorzeitig beendet werden sollte, um Rechenleistung zu sparen und die Suche zu beschleunigen.

Der technische Kern hinter KI-Produkten

Die Vektorretrieval ist die zentrale technische Komponente, die erfolgreiche KI-Produkte unterstützt. Sie erweitert nicht nur die Grenzen der traditionellen semantischen Suche (Schlüsselwortsuche), sondern passt auch perfekt zu großen Modellen.

Der Schlüssel zur Entfaltung des wahren Potenzials dieser Technologie und zur effektiven Kombination von Vektormodellen und Vektordatensätzen liegt in der richtigen Wahl des "Metrikraums".

Obwohl auf Graphen basierende Algorithmen zur Vektorretrieval wie HNSW und NSG wegen ihrer schnellen Suchgeschwindigkeit beliebt sind, wird oft übersehen, dass sie für euklidische Räume entwickelt wurden.

Die "Metrikfehlanpassung" kann in vielen Szenarien fatal sein. Vektordaten, die besser mit der "maximalen inneren Produkt"-Suche behandelt werden sollten, führen bei der Verwendung von euklidischen Vektoralgorithmen oft zu Problemen wie "Suchergebnisse, die semantisch nicht mit der Abfrage übereinstimmen".

In der Domäne der maximalen inneren Produktretrieval gibt es bisher keine so phänomenalen Suchalgorithmen wie HNSW und NSG. Viele frühere Arbeiten haben nur auf bestimmten Datensätzen gute Ergebnisse gezeigt, aber bei anderen Datensätzen hat die Leistung stark nachgelassen.

Der Schlüssel zum Durchbruch: Mit nur zwei Codezeilenänderungen die globale Lösung für das maximale innere Produkt erzielen

Das Forschungsunternehmen hat durch theoretische Untersuchungen festgestellt, dass die Forschung in der Domäne der maximalen inneren Produktretrieval in zwei Paradigmen geteilt ist:

Erstens wird das maximale innere Produkt in die minimale euklidische Distanz umgewandelt, sodass HNSW und NSG angewendet werden können. Diese Umwandlung ist jedoch oft mit Informationsverlust oder nichtlinearer Transformation des topologischen Raums verbunden, was die Suchergebnisse in unterschiedlichem Maße beeinträchtigt.

Zweitens wird keine Raumumwandlung vorgenommen, und die Suche erfolgt direkt im Raum des inneren Produkts. Der Vorteil besteht darin, dass Informationsverlust oder Raumverzerrung vermieden werden. Der Nachteil ist jedoch, dass es keine effektiven Mittel gibt, um den ineffektiven Suchraum zu reduzieren, was es schwierig macht, eine bessere Suchgeschwindigkeit zu erreichen.

Warum ist es so schwierig, direkt im Raum des inneren Produkts zu suchen?

Der Kerngrund liegt darin, dass der Raum des inneren Produkts nicht strikt als "Metrikraum" definiert werden kann. Mathematisch betrachtet muss ein Raum viele Bedingungen erfüllen, um als "Metrikraum" bezeichnet zu werden. Der euklidische Raum, mit dem wir am häufigsten in Kontakt kommen, ist ein typischer Metrikraum. Als "unvollständiger Raum" fehlt dem Raum des inneren Produkts die wichtigste Eigenschaft, nämlich die "Dreiecksungleichung".

Nach der theoretischen Grundlage der NSG-Publikation sind die hochaktuellen Algorithmen zur Vektorretrieval wie HNSW, NSG und SSG so effizient, weil sie alle die Dreiecksungleichung nutzen, um die Indexstruktur (Graphenstruktur) effizient zu reduzieren.

Ein Dreieck, das auf dem inneren Produkt als Distanzmetrik basiert, erfüllt nicht die bekannte Regel "In einem Dreieck ist die Summe der Längen zweier Seiten größer als die Länge der dritten Seite, und die Differenz der Längen zweier Seiten ist kleiner als die Länge der dritten Seite". Das Fehlen dieser Eigenschaft hindert die Weiterentwicklung der Algorithmen zur maximalen inneren Produktretrieval.

Das PSP-Forschungsunternehmen hat diese Problematik eingehend untersucht und theoretisch bewiesen, dass für jede Suchanfrage, d. h. für jeden Query-Punkt q, in einer für die euklidische Distanz entworfenen Graphenindexstruktur die globale optimale Lösung für das maximale innere Produkt mit einem einfachen Greedy-Algorithmus gefunden werden kann.

Alle auf Graphen basierenden Algorithmen zur Vektorretrieval nutzen Greedy-Algorithmen für die Suche: Wenn wir von einem zufälligen Punkt im Graphen ausgehen, suchen Algorithmen wie NSG unter den Nachbarn des aktuellen Punkts den "nächsten" Nachbarn in Bezug auf das Ziel und springen zu ihm, um so schrittweise zur globalen optimalen Lösung zu gelangen.

Früher war die implizite theoretische Anforderung dieses Greedy-Algorithmus, dass, wenn der Graph mit der euklidischen Distanz zur Definition von "fern" und "nah" erstellt wurde, auch der Greedy-Algorithmus die euklidische Distanz zur Definition von "fern" und "nah" nutzen muss.

Das Ergebnis der PSP-Forschung ist, dass wenn der Graph mit der euklidischen Distanz erstellt wurde, der Greedy-Algorithmus beim Durchlaufen des Graphen das innere Produkt zur Definition von "fern" und "nah" nutzen kann, und das Endresultat ist die globale optimale Lösung für das maximale innere Produkt!

Das Forschungsunternehmen kann daher durch nur zwei Codezeilenänderungen im Suchalgorithmus (Greedy-Algorithmus) einen bestehenden euklidischen Algorithmus an die maximale innere Produktretrieval anpassen:

△

Optimierung: Die Suchaktionen gezielt lenken, um redundante Berechnungen zu vermeiden

Das PSP-Forschungsunternehmen hat festgestellt, dass bei der maximalen inneren Produktretrieval eine Vielzahl von redundanten Berechnungen auftreten, die durch eine gezielte Lenkung der Suchaktionen vermieden werden können.

Die Suchaktionen bei der maximalen inneren Produktretrieval unterscheiden sich stark von denen im euklidischen Raum, wie in der folgenden Abbildung gezeigt:

In der linken Abbildung ist der nächste euklidische Nachbar des grünen Rechtecks (Query) das rote Dreieck, aber der Nachbar mit dem maximalen inneren Produkt ist das orangefarbene Quadrat. Wenn man also den nächsten euklidischen Nachbarn des Query sucht, wird die Suche schnell in der Nähe des Dreiecks stoppen, aber die Suche nach dem Nachbarn mit dem maximalen inneren Produkt wird weiter in die "Außenbereiche" in die Nähe des orangefarbenen Quadrats gehen.

Im größeren Zusammenhang hat das Forschungsunternehmen festgestellt, dass der Lösungssraum der maximalen inneren Produktretrieval oft in den "Außenbereichen" des Datensatzes liegt (im Gegensatz zu den nächsten Nachbarn in Bezug auf die euklidische Distanz, die sich an beliebigen Positionen im Datenraum befinden können). Daher folgt die Suchaktion bei der maximalen inneren Produktretrieval oft einem Muster "von innen nach außen und dann in die Außenbereiche erweitern" (wie in der rechten Abbildung oben).

Angesichts dieser Eigenschaften entwickelt PSP gezielte Strategien, damit die Startpunkte der Suche im Graphen möglichst in Bereichen liegen, die näher an der "Lösung" sind.

Außerdem treten Redundanzen nicht nur in der Anfangsphase der Suche auf, sondern auch in der Endphase.

Wie in der obigen Abbildung gezeigt, hat das PSP-Forschungsunternehmen festgestellt, dass die "minimale Anzahl von Schritten", um die exakte Lösung in der Graphenindexstruktur zu finden, je nach Query variiert und einer deutlichen Langschwanzverteilung folgt (Abbildung a). Durch zahlreiche Experimente haben sie auch vier Arten von "Merkmalen" identifiziert, die uns helfen, zu entscheiden, wann die Suche beendet werden sollte (Abbildung b). Diese vier Merkmale können während der Suche mit sehr geringem Aufwand berechnet und aufgezeichnet werden, um eine adaptive "Frühstopp"-Strategie zu implementieren.

Konkret kann man eine Teilmenge von Punkten aus der Datenbank zufällig auswählen und als Query verwenden. Durch die Suche nach diesen Punkten können Daten vor und nach der optimalen Stoppzahl gesammelt werden, um klassifizierbare Stichproben zu bilden. Dann kann man einen Entscheidungsbaum mit diesen Stichproben trainieren, um die Stoppbedingungen bei der Suche zu bestimmen:

Wie in der obigen Abbildung gezeigt, kann das Forschungsunternehmen durch das Beschneiden des Entscheidungsbaums die Höhe des gesamten Baums reduzieren. Die Wahl eines Entscheidungsbaums als Klassifikator ermöglicht es, wenige Stichproben effektiv anzupassen und direkt in if-else-Anweisungen umzuwandeln, die in den Suchcode eingebettet werden können, um eine effiziente "Stoppentscheidung" zu ermöglichen.

Leistungstests: Stabilität, Effizienz und Erweiterbarkeit

Um die Effektivität des PSP-Algorithmus gründlich zu testen, hat das Forschungsunternehmen umfangreiche Tests auf acht großen Datensätzen mit hoher Dimensionalität durchgeführt. In Bezug auf die Dimensionalität betragen die Dimensionen von DBpedia100K und DBpedia1M jeweils 1536 und 3072, und die Daten wurden mit dem OpenAI text-embedding-3-large-Modell extrahiert. In Bezug auf die Anzahl der Datenpunkte enthält der größte Datensatz, Commerce100M, 100 Millionen Datenbankpunkte.

Beim Vergleich von Algorithmen zur Vektorretrieval wird oft die Suchgeschwindigkeit bei gleicher Rückrufrate betrachtet, d. h. die Querys pro Sekunde (QPS). Aus der obigen Abbildung geht hervor, dass PSP im Vergleich zu den aktuellen hochaktuellen Methoden eine stabile und deutliche Verbesserung aufweist. Auf den MNIST-Daten ist die Leistung sogar mehr als viermal so hoch wie die der zweiten Stelle.

Es ist bemerkenswert, dass einige Baseline-Methoden in den Graphen fehlen. Dies liegt daran, dass ihre Leistung weit hinter der anderer Methoden zurückbleibt und es schwierig ist, sie in demselben Graphen darzustellen. Beispielsweise fehlt ip-HNSW im MNIST-Datensatz, und ScaNN fehlt in Laion10M und Commerce100M. Dies unterstreicht die Stabilität der Leistung von PSP.

Darüber hinaus enthalten die verwendeten Datensätze verschiedene Datenmodalitäten wie "Text-zu-Text-Suche", "Bild-zu-Bild-Suche", "Text-zu-Bild-Suche" und "Rückruf in Empfehlungssystemen", was die starke Generalisierungsfähigkeit von PSP zeigt.

Neben der Vergleichung der Suchleistung ist die Skalierbarkeit ein weiterer wichtiger Aspekt bei der Bewertung der Anwendbarkeit von Algorithmen zur Vektorretrieval. Eine gute Suche sollte eine Zeitkomplexität haben, die weit unter einer linearen Zunahme liegt.

Aus der obigen Abbildung geht hervor, dass PSP bei der Suche nach dem Top-1-Nachbarn eine Zeitkomplexität mit einer Wachstumsrate von log(N) aufweist. Bei der Top-K-Retrieval liegt die Komplexität nahe bei log(N). Dies zeigt die hervorragende Skalierbarkeit von PSP und das Potenzial für eine effiziente Suche