💬 NLP

CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

Dit artikel introduceert CRINN, een nieuw paradigma dat contrastief reinforcement learning benut om automatisch hoogwaardige algoritmen voor het zoeken naar benaderende dichtstbijzijnde buren te genereren door te optimaliseren voor executiesnelheid terwijl de nauwkeurigheid behouden blijft, waarbij state-of-the-art resultaten worden behaald op meerdere benchmarks en het potentieel van LLM's voor het automatiseren van complexe algoritmische optimalisatie wordt aangetoond.

Oorspronkelijke auteurs: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

Gepubliceerd 2026-07-14

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme bibliotheek hebt met miljarden boeken en je moet het ene boek vinden dat het meest lijkt op een specifieke zin die je zojuist hebt getypt. In de wereld van computers wordt dit "Approximate Nearest Neighbor Search" (ANNS) genoemd. Het is de motor achter coole technologie zoals AI-chatbots die je eerdere gesprekken onthouden of robots die vergelijkbare afbeeldingen vinden. Maar hier is de crux: het vinden van dat perfecte boek in een bibliotheek van miljarden gaat traag. Als je elk afzonderlijk boek controleert, duurt het eeuwig. Daarom hebben computerwetenschappers "slimme afkortingen" gebouwd om het juiste boek snel te vinden, waarbij ze een klein beetje nauwkeurigheid inruilen voor enorme snelheidswinsten.

Jarenlang was het sneller maken van deze afkortingen een taak die alleen door mensen kon worden uitgevoerd. Het is als het afstellen van een racewagenmotor: een expert-monteur moet naar de motor luisteren, raden welk onderdeel vertraagt, een schroefje hier aanpassen, een versnelling daar veranderen, en het dan weer testen. Dit vereist diepgaande kennis en veel geduld.

Maak kennis met CRINN, een nieuw systeem dat een grote vraag stelt: Kunnen we een AI leren om de motor zelf af te stellen?

De Robotmonteur met een Superkracht

CRINN is een "reinforcement learning"-framework. Denk aan een robotmonteur die niet alleen maar gokt, maar leert door een spelletje te spelen. Het spel is simpel: schrijf een stuk code om de bibliotheek te doorzoeken, voer het uit, en kijk hoe snel het is.

De Beloning: Als de code de boeken snel vindt, krijgt de robot een hoge score.
De Les: De robot vergelijkt zijn nieuwe code met zijn oude code. Hij kijkt niet alleen naar de score; hij kijkt naar waarom de ene sneller was. Is er een stap overgeslagen? Is de organisatie van de boeken verbeterd?
De Lus: De robot gebruikt deze vergelijking om de volgende keer een nog snellere versie te schrijven. Hij blijft dit doen en wordt slimmer en sneller bij elke poging.

Het paper laat zien dat deze robotmonteur ongelooflijk goed is in zijn werk. Bij tests op zes verschillende soorten "bibliotheken" (datasets variërend van afbeeldingen van cijfers tot woord-embeddings) slaagde CRINN erin om zoeksystemen te bouwen die de snelste ter wereld waren voor drie van hen (GIST-960, MNIST-784 en GloVe-25) en gedeeld de eerste plaats belegden voor twee anderen (SIFT-128 en GloVe-25).

Hoe het leerde te winnen

Het geheime ingrediënt heet Contrastive Reinforcement Learning. Stel je voor dat de robot twee versies van een coderegel krijgt gekregen: één die 1 seconde draait en één die 2 seconden draait. De robot krijgt de opdracht uit te leggen waarom de eerste sneller is. Hij merkt misschien op: "Ah, de snelle versie controleert drie boeken tegelijk, terwijl de trage versie ze één voor één controleert." Door deze patronen te leren, begint de robot code te schrijven die van nature die snelheid-verhogende trucjes bevat.

De onderzoekers lieten de robot niet zomaar willekeurig gokken. Ze gaven hem een specifiek doel: vind de beste balans tussen snelheid en nauwkeurigheid. Ze maten de prestaties met behulp van Queries Per Second (QPS) — hoeveel zoekopdrachten het systeem in één seconde kan uitvoeren — terwijl ze de nauwkeurigheid (de recall) hoog hielden. Bijvoorbeeld, op de MNIST-dataset (handgeschreven cijfers) was CRINN 85,25% sneller dan het vorige beste systeem bij een zeer hoge nauwkeurigheid (0,999 recall). Dat is een enorme sprong!

De "One Size Fits All" Verrassing

Hier wordt het echt interessant. De robot werd getraind met slechts één type bibliotheek: de SIFT-128 dataset, die een specifieke manier van afstand meten gebruikt, genaamd "Euclidean distance" (zoals het meten van een rechte lijn op een kaart). Je zou kunnen denken: "Als ik een monteur train op een sedan, zal hij dan wel weten hoe hij een motorfiets moet repareren?"

Maar het paper vond dat de training van CRINN op Euclidische afstand verrassend goed werkte op "Angular distance" datasets (zoals de GloVe woord-embeddings), die wiskundig gezien heel anders zijn. Dit suggereert dat de robot algemene principes van snelheid heeft geleerd die ook van toepassing zijn wanneer de regels van het spel licht veranderen. Echter, het paper merkt een duidelijke grens op: bij tests op de NYTimes-256 dataset presteerde CRINN zelfs 82,85% slechter dan het beste bestaande systeem. Dit vertelt ons dat hoewel de robot een genie is, hij niet magisch is; hij worstelt nog steeds met bepaalde soorten data die heel verschillend zijn van wat hij heeft geleerd.

De Stap-voor-Stap Upgrade

De onderzoekers gooiden de robot niet in één keer op het hele probleem. Ze braken het zoekproces op in drie fasen, zoals het upgraden van een auto in fases:

Het Bouwen van de Kaart (Graph Construction): Dit is waar de bibliotheek wordt georganiseerd. CRINN verbeterde deze fase het meest, met een gemiddelde snelheidswinst van 22,11%. Het leerde "adaptieve zoekopdrachten" gebruiken, wat betekent dat het meer moeite doet om een boek te vinden wanneer dat echt nodig is, en "multi-entry points", waardoor het vanaf meerdere deuren tegelijk kan beginnen te zoeken.
Het Zoeken op de Kaart (Search): Zodra de kaart is gebouwd, moet je het boek vinden. CRINN verbeterde dit met 18,30%, door gebruik te maken van trucs zoals "batch processing" (groepen boeken tegelijk controleren) en "early termination" (stoppen met zoeken zodra zeker is dat de beste match is gevonden).
Het Polijsten van het Resultaat (Refinement): De laatste stap om te zorgen dat het antwoord perfect is. Dit gaf een kleinere boost van 9,69%, omdat er in deze fase minder ruimte was voor verbetering.

Wat dit Betekent

Het paper betoogt dat CRINN een krachtig idee bewijst: AI kan complexe, expert-niveau taken automatiseren. Decennialang vereiste het sneller maken van deze zoekalgoritmen menselijke experts met jarenlange training. Nu kan een systeem dat leert door zijn eigen code te vergelijken, dit automatisch doen.

De auteurs benadrukken voorzichtig dat dit geen opgelost probleem is voor álle datasets (zoals te zien aan het NYTimes-resultaat), maar het is een grote stap voorwaarts. Ze suggereren dat naarmate AI-toepassingen zoals "Retrieval-Augmented Generation" (waarbij AI externe kennis gebruikt om vragen te beantwoorden) populairder worden, tools zoals CRINN essentieel zullen zijn om alles snel te laten blijven draaien zonder dat er een mens nodig is om elke instelling handmatig aan te passen.

Kortom, CRINN is een robot die heeft geleerd een meestermonteur te zijn voor datadatabeheer, en bewijst dat met de juiste training, machines niet alleen code kunnen schrijven, maar ook kunnen uitzoeken hoe ze die sneller kunnen laten draaien dan mensen ooit zouden kunnen.

Technische Samenvatting: CRINN

Probleemstelling

Approximate Nearest-Neighbor Search (ANNS) is een kritieke component voor moderne AI-toepassingen, met name voor Retrieval-Augmented Generation (RAG) en agent-gebaseerde Large Language Model (LLM) systemen, die snelle extractie uit massieve vectordatabases vereisen. Hoewel bestaande open-source ANNS-oplossingen (bijv. FAISS, DiskANN, ParlayANN) vertrouwen op robuuste backbones zoals HNSW (Hierarchical Navigable Small World), blijft hun optimalisatie een grotendeendeels handmatig proces. Dit proces vereist diepgaande expertise in computerarchitectuur, parallel programmeren en algoritmische eigenschappen om knelpunten te identificeren, parameters (zoals graafgraad en zoekbreedte) af te stemmen en datastructuren voor geheugenlokaliteit te ontwerpen. Het artikel stelt dat deze handmatige verfijning arbeidsintensief is en roept de vraag op of LLM's, versterkt met reinforcement learning (RL), de generatie en het testen van algoritmische verbeteringen kunnen automatiseren om optimalisatiepatronen te ontdekken die menselijke ingenieurs mogelijk over het hoofd zien.

Methodologie

De auteurs stellen CRINN (Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search) voor, een framework dat ANNS-optimalisatie behandelt als een reinforcement learning-probleem waarbij de uitvoeringssnelheid dient als het beloningssignaal.

Kernframework

CRINN maakt gebruik van een contrastief RL-model om ANNS-algoritmen module voor module te optimaliseren (specifiek gericht op Graph Construction, Search en Refinement binnen een HNSW-backbone). Het proces omvat:

Contrastieve Prompting: De LLM krijgt een prompt met eerdere code-implementaties gekoppeld aan hun uitvoeringsscores. Het model krijgt de instructie om een vergelijkende analyse uit te voeren om te identificeren waarom bepaalde implementaties andere presteren, waarbij onderscheid wordt gemaakt tussen effectieve en ineffectieve strategieën.
Iteratieve Generatie: Op basis van deze analyse synthetiseert de LLM nieuwe codevarianten.
Beloningssignaal: De gegenereerde code wordt uitgevoerd en de beloning wordt berekend op basis van prestaties. Om de moeilijkheid van het vergelijken van ANNS-algoritmen te adresseren vanwege de afweging tussen Queries Per Second (QPS) en Recall, hanteren de auteurs een specifieke evaluatiestrategie:
- Ze variëren de zoekparameter $ef$ om een set (QPS, recall)-punten te genereren.
- Ze filteren punten binnen het recall-bereik van $[0.85, 0.95]$ , een "sweet spot" waar de meeste algoritmen voldoende data hebben en prestatieverschillen betekenisvol zijn.
- De beloning wordt gedefinieerd als de Area Under the Curve (AUC) gevormd door deze gefilterde punten, wat een enkele scalaire waarde biedt voor het RL-doel.
Trainingsalgoritme: Het systeem maakt gebruik van Group Relative Policy Optimization (GRPO). Voor elke inputprompt genereert het model een groep code-completions. Beloningen worden binnen de groep genormaliseerd en het beleid (policy) wordt bijgewerkt om de waarschijnlijkheid te maximalen van het genereren van code met een hogere beloning, terwijl een beperking wordt gehandhaafd tegen te ver afwijken van een referentiebeleid (KL-divergentie).

Implementatiedetails

Baseline: Het framework gebruikt GLASS als het initiële startpunt, een graafgebaseerde ANNS-bibliotheek, en optimaliseert sequentieel de constituerende modules.
Trainingsdata: Het RL-model wordt uitsluitend getraind op de SIFT-128-Euclidean dataset om een enkel generaliseerbaar codebase te behouden.
Outputstructuur: De LLM wordt beperkt tot het produceren van een gestructureerde respons die een "Performance Analysis", "Algorithm Design" en "Code Implementation" bevat.

Belangrijkste Bijdragen

Geautomatiseerd Optimalisatieparadigma: CRINN introduceert een nieuw paradigma waarbij ANNS-optimalisatie wordt geautomatiseerd via RL-versterkte LLM's, waardoor de noodzaak voor handmatige, door expertise gedreven afstemming wordt weggenomen.
Contrastief Leermechanisme: Door voorbeeldcode en uitvoeringsmetrieken direct in de prompt te integreren, leert het model te redeneren over prestatie-kritieke patronen door directe vergelijking in plaats van enkel door trial-and-error.
Reward Engineering: Het artikel adresseert de uitdaging van het definiëren van een scalaire beloning voor ANNS door gebruik te maken van de AUC van de QPS-recall curve binnen een specifiek, praktisch recall-bereik ( $[0.85, 0.95]$ ), wat een eerlijke vergelijking tussen discrete parameterinstellingen mogelijk maakt.
Progressieve Optimalisatie: Het systeem demonstreert dat sequentiële optimalisatie van afzonderlijke modules (Graph Construction, Search en Refinement) cumulatieve prestatiewinsten oplevert.

Experimentele Resultaten

De auteurs evalueerden CRINN op zes veelgebruikte benchmark-datasets: SIFT-128, GIST-960, MNIST-784, GloVe-100, GloVe-25 en NYTimes-256.

Prestaties: CRINN behaalde best-in-class prestaties op drie datasets (GIST-960-Euclidean, MNIST-784-Euclidean en GloVe-25-angular) en verdeelde de eerste plaats op twee andere (SIFT-128-Euclidean en GloVe-25-angular).
Kwantitatieve Winsten:
- Op MNIST-784 liet CRINN een verbetering van tot wel 85,25% in QPS zien bij een 0,999 recall vergeleken met de beste baseline (ParlayANN).
- Op GIST-960 behaalde het een verbetering van 72,68% bij 0,99 recall.
- Op SIFT-128 (de trainingsdataset) varieerden de verbeteringen van +3,25% tot +25,57% over verschillende recall-niveaus.
Beperkingen: CRINN presteerde op NYTimes-256 (een dataset met angular distance) 82,85% minder goed dan de beste baseline bij een 0,9 recall. De auteurs schrijven dit toe aan het feit dat het model uitsluitend is getraind op Euclidean distance data, wat suggereert dat optimalisatiepatronen voor angular similarity aanzienlijk kunnen verschillen.
Modulebijdragen: De Graph Construction module leverde de meest significante individuele winsten op (gemiddeld +22,11%), gevolgd door Search (+18,30%) en Refinement (+9,69%).

Betekenis en Claims

Het artikel claimt dat het succes van CRINN verder reikt dan de specifieke optimalisatie van ANNS-algoritmen. Het valideert dat LLM's versterkt met reinforcement learning effectieve instrumenten kunnen zijn voor het automatiseren van geavanceerde algoritmische optimalisaties die traditioneel gespecialiseerde domeinkennis en arbeidsintensieve handmatige verfijning vereisen.

De auteurs stellen dat naarmate de vraag naar efficiënte vectorzoekopdrachten groeit met de proliferatie van RAG en agent-gebaseerde LLM-toepassingen, frameworks zoals CRINN steeds waardevoller zullen worden voor het behoud van competitieve prestaties over evoluerende hardwarearchitecturen en applicatie-eisen heen. Het werk demonstreert dat geautomatiseerde systemen niet alleen menselijke engineering-oplossingen kunnen evenaren, maar in specifieke contexten zelfs kunnen overtreffen.