💬 NLP

CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

Dieses Paper stellt CRINN vor, ein neuartiges Paradigma, das kontrastives Reinforcement Learning nutzt, um automatisch hochperformante Algorithmen für die approximative Suche nach nächsten Nachbarn zu generieren, indem es auf die Ausführungsgeschwindigkeit optimiert und gleichzeitig die Genauigkeit beibehält, wodurch es auf mehreren Benchmarks Spitzenleistungen erzielt und das Potenzial von LLMs für die Automatisierung komplexer algorithmischer Optimierung demonstriert.

Ursprüngliche Autoren: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

Veröffentlicht 2026-07-14

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie besitzen eine riesige Bibliothek mit Milliarden von Büchern und müssen genau das eine Buch finden, das dem klingt, was Sie gerade getippt haben. In der Welt der Computer nennt man das „Approximate Nearest Neighbor Search“ (ANNS). Dies ist der Motor hinter cooler Technologie wie KI-Chatbots, die sich an vergangene Gespräche erinnern können, oder Robotern, die ähnliche Bilder finden. Aber hier ist der Haken: Das Finden des perfekten Buches in einer Bibliothek mit Milliarden von Büchern dauert lange. Wenn Sie jedes einzelne Buch prüfen, dauert es eine Ewigkeit. Deshalb haben Informatiker „schlaue Abkürzungen“ gebaut, um das richtige Buch schnell zu finden, wobei sie ein winziges Stück Genauigkeit gegen enorme Geschwindigkeitsgewinne eintauschen.

Jahrelang war das Schneller-Machen dieser Abkürzungen eine rein menschliche Aufgabe. Es ist wie das Tuning eines Rennwagenmotors: Ein Experte muss den Motor hören, raten, welches Teil bremst, eine Schraube hier drehen, ein Zahnrad dort ändern und dann wieder testen. Das erfordert tiefes Wissen und viel Geduld.

Hier kommt CRINN ins Spiel, ein neues System, das eine große Frage stellt: Können wir eine KI lehren, den Motor selbst zu tunen?

Der Roboter-Mechaniker mit einer Superkraft

CRINN ist ein „Reinforcement Learning“-Framework. Stellen Sie sich das wie einen Roboter-Mechaniker vor, der nicht nur rät, sondern durch Spielen lernt. Das Spiel ist einfach: Schreibe ein Stück Code, um die Bibliothek zu durchsuchen, führe ihn aus und schaue, wie schnell er ist.

Die Belohnung: Wenn der Code die Bücher schnell findet, bekommt der Roboter eine hohe Punktzahl.
Die Lektion: Der Roboter vergleicht seinen neuen Code mit seinem alten Code. Er schaut nicht nur auf die Punktzahl; er schaut darauf, warum der eine schneller war. Hat er einen Schritt übersprungen? Hat er die Bücher besser organisiert?
Die Schleife: Der Roboter nutzt diesen Vergleich, um beim nächsten Mal eine noch schnellere Version zu schreiben. Er macht dies immer wieder und wird mit jedem Versuch klüger und schneller.

Die Arbeit zeigt, dass dieser Roboter-Mechaniker unglaublich gut in seinem Job ist. Bei Tests auf sechs verschiedenen Arten von „Bibliotheken“ (Datensätze, die von Bildern von Ziffern bis hin zu Wort-Embeddings reichen) gelang es CRINN, Suchsysteme zu bauen, die für drei davon (die schnellsten der Welt waren: GIST-960, MNIST-784 und GloVe-25) und bei zwei anderen gleichauf mit dem ersten Platz lagen (SIFT-128 und GloVe-25).

Wie es lernte zu gewinnen

Das Geheimrezept heißt Contrastive Reinforcement Learning. Stellen Sie sich vor, der Roboter bekommt zwei Versionen eines Code-Schnipsels gegeben: eine, die in 1 Sekunde läuft, und eine, die in 2 Sekunden läuft. Der Roboter wird gebeten zu erklären, warum die erste schneller ist. Er könnte bemerken: „Ah, die schnelle prüft drei Bücher gleichzeitig, während die langsame sie nacheinander prüft.“ Durch das Lernen dieser Muster beginnt der Roboter, Code zu schreiben, der von Natur aus diese geschwindigkeitssteigernden Tricks enthält.

Die Forscher ließen den Roboter nicht einfach nur raten. Sie gaben ihm ein spezifisches Ziel: das beste Gleichgewicht zwischen Geschwindigkeit und Genauigkeit zu finden. Sie maßen die Leistung mittels Queries Per Second (QPS) – wie viele Suchanfragen das System in einer Sekunde durchführen kann – während sie gleichzeitig die Genauigkeit (genannt Recall) hoch hielten. Beispielsweise war CRINN beim MNIST-Datensatz (handgeschriebene Ziffern) 85,25 % schneller als das bisher beste System bei einem sehr hohen Genauigkeitsniveau (0,999 Recall). Das ist ein gewaltiger Sprung!

Die „Einheitsgröße“-Überraschung

Hier wird es wirklich interessant. Der Roboter wurde nur mit einer Art von Bibliothek trainiert: dem SIFT-128-Datensatz, der eine spezifische Art der Distanzmessung verwendet, die „Euklidische Distanz“ (wie das Messen einer geraden Linie auf einer Karte). Man könnte denken: „Wenn ich einen Mechaniker an einer Limousine trainiere, wird er nicht wissen, wie man ein Motorrad repariert.“

Aber die Arbeit fand heraus, dass das Training von CRINN auf euklidischer Distanz überraschend gut auf Datensätze mit „Winkel-Distanz“ (wie die GloVe-Wort-Embeddings) funktionierte, die mathematisch gesehen ganz anders sind. Dies deutet darauf hin, dass der Roboter allgemeine Prinzipien der Geschwindigkeit gelernt hat, die auch dann gelten, wenn sich die Regeln des Spiels leicht ändern. Die Arbeit stellt jedoch eine klare Grenze fest: Beim Test mit dem NYTimes-256-Datensatz schnitt CRINN tatsächlich 82,85 % schlechter ab als das beste bestehende System. Dies zeigt uns, dass der Roboter zwar ein Genie ist, aber keine Magie; er hat immer noch Schwierigkeiten mit bestimmten Arten von Daten, die sehr anders sind als das, was er gelernt hat.

Das schrittweise Upgrade

Die Forscher warfen den Roboter nicht einfach auf das gesamte Problem gleichzeitig. Sie unterteilten den Suchprozess in drei Phasen, wie das Tuning eines Autos in Etappen:

Die Karte erstellen (Graph Construction): Hier wird die Bibliothek organisiert. CRIMM verbesserte diese Phase am meisten und steigerte die Geschwindigkeit um durchschnittlich 22,11 %. Es lernte, eine „adaptive Suche“ zu nutzen, was bedeutet, dass es mehr Aufwand betreibt, das Buch erst dann zu suchen, wenn es wirklich nötig ist, sowie „Multi-Entry-Points“, was es ermöglicht, die Suche von mehreren Türen gleichzeitig zu starten.
Die Karte durchsuchen (Search): Sob es die Karte erstellt hat, muss man das Buch finden. CRINN verbesserte dies um 18,30 %, indem es Tricks wie „Batch Processing“ (das Prüfen von Gruppen von Büchern zusammen) und „Early Termination“ (das Abbrechen der Suche, sobald sicher ist, dass die beste Übereinstimmung gefunden wurde) anwandte.
Das Ergebnis verfeinern (Refinement): Der letzte Schritt, um sicherzustellen, dass die Antwort perfekt ist. Dies brachte einen kleineren Schub von 9,69 %, da in dieser Phase weniger Raum für Verbesserungen blieb.

Was das bedeutet

Die Arbeit argumentiert, dass CRINN beweist: KI kann komplexe, expertenbasierte Aufgaben automatisieren. Über Jahrzehnte hinweg erforderte das Schneller-Machen dieser Suchalgorithmen menschliche Experten mit jahrelanger Ausbildung. Jetzt kann ein System, das durch den Vergleich seines eigenen Codes lernt, dies automatisch tun.

Die Autoren sind vorsichtig zu sagen, dass dies kein gelöstes Problem für jeden einzelnen Datensatz ist (wie das NYTimes-Ergebnis zeigt), aber es ist ein bedeutender Schritt nach vorn. Sie deuten an, dass, wenn KI-Anwendungen wie „Retrieval-Augmented Generation“ (bei denen die KI externes Wissen nutzt, um Fragen zu beantworten) populärer werden, Werkzeuge wie CRINN essenziell sein werden, um alles schnell am Laufen zu halten, ohne dass ein Mensch jede einzelne Einstellung manuell anpassen muss.

Kurz gesagt: CRINN ist ein Roboter, der gelernt hat, ein Meistermechaniker für die Datensuche zu sein, und beweist, dass Maschinen mit dem richtigen Training nicht nur Code schreiben, sondern auch herausfinden können, wie sie ihn schneller laufen lassen können, als Menschen es je könnten.

Technisches Resümee: CRINN

Problemstellung

Die Suche nach ungefähren nächsten Nachbarn (Approximate Nearest-Neighbor Search, ANNS) ist eine kritische Komponente für moderne KI-Anwendungen, insbesondere für Retrieval-Augmented Generation (RAG) und agentenbasierte Large Language Model (LLM)-Systeme, die eine schnelle Abfrage aus massiven Vektordatenbanken erfordern. Während bestehende Open-Source-ANNS-Lösungen (z. B. FAISS, DiskANN, ParlayANN) auf robusten Backbones wie HNSW (Hierarchical Navigable Small World) basieren, bleibt deren Optimierung ein weitgehend manueller Prozess. Dieser Prozess erfordert tiefgreifende Expertise in Computerarchitektur, paralleler Programmierung und algorithmischen Eigenschaften, um Engpässe zu identifizieren, Parameter (wie den Graph-Grad und die Such-Beam-Breite) abzustimmen und Datenstrukturen für die Speicherlokalität zu entwerfen. Das Paper postuliert, dass diese manuelle Verfeinerung arbeitsintensiv ist und die Frage aufwirft, ob LLMs, ergänzt durch Reinforcement Learning (RL), die Generierung und das Testen algorithmischer Verbesserungen automatisieren können, um Optimierungsmuster zu entdecken, die menschlichen Ingenieuren entgehen könnten.

Methodik

Die Autoren schlagen CRINN (Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search) vor, ein Framework, das die ANNS-Optimierung als ein Reinforcement-Learning-Problem behandelt, bei dem die Ausführungsgeschwindigkeit als Belohnungssignal dient.

Kern-Framework

CRINN nutzt ein kontrastives RL-Modell, um ANNS-Algorithmen modulweise zu optimieren (speziell mit Fokus auf Graphkonstruktion, Suche und Verfeinerung innerhalb eines HNSW-Backbones). Der Prozess umfasst:

Kontrastives Prompting: Dem LLM wird ein Prompt bereitgestellt, der frühere Code-Implementierungen gepaart mit deren Ausführungswerten enthält. Das Modell wird angewiesen, eine vergleichende Analyse durchzuführen, um zu identifizieren, warum bestimmte Implementierungen andere übertreffen, indem es zwischen effektiven und ineffektiven Strategien unterscheidet.
Iterative Generierung: Basierend auf dieser Analyse synthetisiert das LLM neue Code-Varianten.
Belohnungssignal: Der generierte Code wird ausgeführt, und die Belohnung wird basierend auf der Performance berechnet. Um die Schwierigkeit des Vergleichs von ANNS-Algorithmen aufgrund des Trade-offs zwischen Queries Per Second (QPS) und Recall zu adressieren, verwenden die Autoren eine spezifische Evaluierungsstrategie:
- Sie variieren den Suchparameter $ef$, um einen Satz von (QPS, Recall)-Punkten zu generieren.
- Sie filtern Punkte innerhalb des Recall-Bereichs von $[0,85, 0,95]$ , einem „Sweet Spot“, in dem die meisten Algorithmen über ausreichende Daten verfügen und die Leistungsunterschiede aussagekräftig sind.
- Die Belohnung wird als die Fläche unter der Kurve (Area Under the Curve, AUC) definiert, die durch diese gefilterten Punkte gebildet wird, was einen einzelnen Skalarwert für das RL-Ziel liefert.
Trainingsalgorithmus: Das System verwendet Group Relative Policy Optimization (GRPO). Für jeden Input-Prompt generiert das Modell eine Gruppe von Code-Vervollständigungen. Die Belohnungen werden innerhalb der Gruppe normalisiert, und die Policy wird aktualisiert, um die Wahrscheinlichkeit der Generierung von höher belohntem Code zu maximieren, während gleichzeitig eine Beschränkung gegen eine zu starke Abweichung von einer Referenz-Policy (KL-Divergenz) eingehalten wird.

Implementierungsdetails

Baseline: Das Framework nutzt GLASS als Ausgangspunkt, eine graphbasierte ANNS-Bibliothek, und optimiert sequenziell deren konstituierende Module.
Trainingsdaten: Das RL-Modell wird ausschließlich auf dem SIFT-128-Euclidean Datensatz trainiert, um eine einzige generalisierbare Codebasis beizubehalten.
Ausgabestruktur: Das LLM wird dazu gezwungen, eine strukturierte Antwort auszugeben, die eine „Performance-Analyse“, ein „Algorithmus-Design“ und eine „Code-Implementierung“ enthält.

Zentrale Beiträge

Automatisierter Optimierungsparadigma: CRINN führt ein neuartiges Paradigma ein, bei dem die ANNS-Optimierung über RL-augmentierte LLMs automatisiert wird, wodurch die Notwendigkeit einer manuellen, durch Expertenwissen getriebenen Abstimmung entfällt.
Kontrastiver Lernmechanismus: Durch die Integration von Beispiel-Code und Ausführungsmetriken direkt in den Prompt lernt das Modell, über performancekritische Muster durch direkten Vergleich statt nur durch Trial-and-Error zu schlussfolgern.
Reward Engineering: Das Paper adressiert die Herausforderung, eine skalare Belohnung für ANNS zu definennen, indem es die AUC der QPS-Recall-Kurve innerhalb eines spezifischen, praktischen Recall-Bereichs ( $[0,85, 0,95]$ ) nutzt, was einen fairen Vergleich über diskrete Parametereinstellungen hinweg ermöglicht.
Progressive Optimierung: Das System zeigt, dass die sequentielle Optimierung distinkter Module (Graphkonstruktion, Suche, Verfeinerung) kumulative Leistungssteigerungen bewirkt.

Experimentelle Ergebnisse

Die Autoren evaluierten CRINN auf sechs weit verbreiteten Benchmark-Datensätzen: SIFT-128, GIST-960, MNIST-784, GloVe-100, GloVe-25 und NYTimes-256.

Performance: CRINN erreichte eine Best-in-Class-Performance auf drei Datensätzen (GIST-960-Euclidean, MNIST-784-Euclidean und GloVe-25-angular) und teilte sich den ersten Platz auf zwei weiteren (SIFT-128-Euclidean und GloVe-25-angular).
Quantitative Gewinne:
- Auf MNIST-784 zeigte CRINN eine bis zu 85,25 % Verbesserung in der QPS bei einem Recall von 0,999 im Vergleich zur besten Baseline (ParlayANN).
- Auf GIST-960 erzielte es eine 72,68 % Verbesserung bei 0,99 Recall.
- Auf SIFT-128 (dem Trainingsdatensatz) lagen die Verbesserungen je nach Recall-Level zwischen +3,25 % und +25,57 %.
Limitierungen: CRINN schnitt auf NYTimes-256 (einem Datensatz mit Winkelabstand/Angular Distance) mit 82,85 % bei einem Recall von 0,9 schlechter ab als die beste Baseline. Die Autoren führen dies darauf zurück, dass das Modell ausschließlich auf euklidischen Distanzdaten trainiert wurde, was darauf hindeutet, dass Optimierungsmuster für Winkelähnlichkeiten signifikant abweichen können.
Modul-Beiträge: Das Modul Graphkonstruktion lieferte die signifikantesten individuellen Gewinne (durchschnittlich +22,11 %), gefolgt von Suche (+18,30 %) und Verfeinerung (+9,69 %).

Signifikanz und Ansprüche

Das Paper behauptet, dass der Erfolg von CRINN über die spezifische Optimierung von ANNS-Algorithmen hinausgeht. Es validiert, dass LLMs, die durch Reinforcement Learning ergänzt werden, als effektive Werkzeuge zur Automatisierung komplexer algorithmischer Optimierungen fungieren können, die traditionell spezialisiertes Domänenwissen und arbeitsintensive manuelle Verfeinerung erfordern.

Die Autoren argumentieren, dass mit der steigenden Nachfrage nach effizienter Vektorsuche durch die Verbreitung von RAG- und agentenbasierten LLM-Anwendungen Frameworks wie CRINN zunehmend wertvoll werden, um eine wettbewerbsfähige Performance über sich entwickelnde Hardware-Architekturen und Anwendungsvoraussetzungen hinweg aufrechtzuerhalten. Die Arbeit zeigt, dass automatisierte Systeme in spezifischen Kontexten nicht nur menschliche State-of-the-Art-Lösungen erreichen, sondern diese sogar übertreffen können.