A Comparative Study of Vector Indexing Strategies Using Facebook AI Similarity Search as a Case Study

Stel je voor dat je in een bibliotheek staat die elk boek bevat dat ooit geschreven is, maar de boeken zijn niet georganiseerd op titel of auteur. In plaats daarvan zijn ze gesorteerd op hoe "gelijkend" ze aan elkaar voelen. Als je vraagt om een verhaal over een dappere kat, zoekt de bibliothecaris niet alleen naar boeken met de woorden "dapper" en "kat"; ze vinden verhalen die voelen als dat idee, zelfs als de woorden anders zijn. Dit is de magie van moderne kunstmatige intelligentie: ideeën omzetten in lijsten met getallen (vectoren) en vervolgens de dichtstbijzijnde overeenkomsten zoeken in een zee van data.

Maar hier is de crux: als je bibliotheek een miljard boeken heeft, zou het controleren van elk afzonderlijk boek om de beste match te vinden een eeuwigheid duren. Het is alsof je probeert een specifiek zandkorreltje op een strand te vinden door elk korreltje één voor één op te pakken. Om dit op te lossen, hebben wetenschappers "indices" uitgevonden — speciale snelkoppelingen die de computer helpen om de saaie delen over te slaan en direct naar de interessante zaken te springen. Sommige snelkoppelingen zijn als een super goed georganiseerde kaart (exact zoeken), terwijl andere als een slim gokspel zijn dat je 99% van de weg naar het doel brengt in een fractie van een seconde (benaderend zoeken). De grote vraag is: welke snelkoppeling is de beste? Hangt het ervan af hoe groot je bibliotheek is? Maakt het uit of je een klein notitieblokje hebt of een enorme magazijnruimte om je boeken op te slaan?

Dit is precies waar een team onderzoekers van de Europese Universiteit van Armenië zich op wilde richten. Ze namen een populaire toolkit genaamd FAISS (Facebook AI Similarity Search), wat een soort Zwitsers zakmes is voor deze vector-snelkoppelingen, en zetten de verschillende tools ervan op de proef. Ze wilden zien hoe goed elke tool presteerde wanneer de data enorm werd, wanneer de getallen ingewikkeld werden en wanneer het geheugen beperkt was. Denk aan een enorme race waarbij verschillende soorten zoekmachines tegen elkaar strijden om te zien wie het snelst het juiste antwoord vindt zonder buiten adem te raken of door zijn geheugen heen te raken.

De onderzoekers testten verschillende strategieën, variërend van de "brute force"-methode (alles controleren) tot slimme trucs met clustering (het groeperen van gelijke items samen) en compressie (het samendrukken van data om ruimte te besparen) en graafgebaseerde navigatie (het gebruik van een web van verbindingen om richting het antwoord te springen). Ze maten twee belangrijke zaken: Recall (heb je het juiste antwoord gevonden?) en Latency (hoe lang duurde het?).

Hier is wat zij ontdekten tijdens hun experimenten:

De "Brute Force" Kampioen (IndexFlat)
Stel je een detective voor die weigert te gokken; hij controleert elke verdachte in de opstelling. Dit is de IndexFlat-methode. De onderzoekers ontdekten dat deze aanpak perfect is: hij mist nooit het juiste antwoord (100% recall). Echter, het is ongelooflijk traag. Naarmate het aantal "verdachten" (vectoren) groeide van 1.000 naar 10.000, nam de tijd die nodig was om het antwoord te vinden gestaag toe. Als je een kleine dataset hebt, is dit geweldig. Maar als je miljoenen vectoren hebt, wordt deze methode te traag om bruikbaar te zijn in de echte wereld. Het is als een microscoop gebruiken om een naald in een hooiberg te vinden; het werkt, maar het duurt eeuwen.

De "Groeperings" Strategie (IVFFlat)
Vervolgens probeerden ze een methode die gelijke vectoren groepeert in clusters, zoals boeken sorteren in bakken met labels als "Avontuur", "Romantiek" en "Mysterie". Dit is IndexIVFFlat. Wanneer er een zoekopdracht binnenkomt, controleert het systeem alleen de bakken die de grootste kans hebben het antwoord te bevatten. De studie toonde aan dat dit een fantastisch middenpad is. Het is veel sneller dan alles controleren, en je kunt het nauwkeuriger maken door meer bakken te controleren. De onderzoekers ontdekten dat als je meer clusters controleert (een instelling genaamd nprobe), je betere resultaten krijgt, maar het duurt iets langer. Het is een flexibel hulpmiddel dat de balans tussen snelheid en nauwkeurigheid goed bewaart voor middelgrote tot grote datasets.

De "Compressie" Experts (IVFPQ en IVFSQ)
Wat als je een miljard vectoren hebt maar niet genoeg harde schijfruimte om ze allemaal op te slaan? De onderzoekers keken naar IndexIVFPQ en IndexIVFSQ, die lijken op het comprimeren van een high-definition film naar een kleiner bestand. Ze drukken de data samen zodat het minder geheugen in beslag neemt.

• IVFPQ (Product Quantization) splitst vectoren in kleine stukjes en comprimeert ze. De studie vond dat dit de kampioen is voor enorme datasets waar geheugen het grootste probleem is. Het is ongelooflijk snel en gebruikt heel weinig ruimte, hoewel het het perfecte antwoord af en toe kan missen (iets lagere recall).
• IVFSQ (Scalar Quantization) is een simpelere versie van compressie. Het is een goede "middenkind"—het bespaart ruimte en is sneller dan de ongecomprimeerde versies, maar het comprimeert niet zo agressief als IVFPQ. De onderzoekers merkten op dat hoewel het een klein beetje nauwkeurigheid verliest vergeleken met de ongecomprimeerde versie, de geheugenbesparing vaak de moeite waard is voor grootschalige systemen.

De "Web van Verbindingen" (HNSW)
Ten slotte was er IndexHNSW, die de data organiseert in een meerlagig web, zoals een metrolijn met expresslijnen en lokale stations. Je begint op de bovenste laag (de expresslijn) om een algemene richting te krijgen, en zoom vervolgens laag voor laag in om het exacte station te vinden. De studie vond dit de absolute superster voor snelheid en nauwkeurigheid. Het is "Zeer Snel" en heeft een "Zeer Hoge" recall. Het vereist echter wat meer geheugen om het web te bouwen, en de onderzoekers merkten op dat je het zorgvuldig moet afstemmen. Als je het web te dicht maakt (te veel verbindingen), wordt het zoeken trager; als je het te ijl maakt, mis je misschien het beste antwoord. Maar wanneer het goed is afgesteld, biedt het de beste balans tussen snelheid en precisie.

Het Oordeel
Het paper concludeert dat er niet één enkele "beste" tool is voor elke taak. Het is als vragen of een hamer, een schroevendraaier of een moersleutel de beste tool is; het hangt ervan af wat je aan het bouwen bent.

• Als je een kleine dataset hebt en perfecte nauwkeurigheid nodig hebt, gebruik dan de Flat index.
• Als je een middelgrote dataset hebt en een balans nodig hebt, is IVFFlat een solide keuze.
• Als je te maken hebt met miljarden vectoren en je computer door zijn geheugen heen raakt, is IVFPQ je beste vriend.
• Als je de snelst mogelijke zoekopdracht met hoge nauwkeurigheid nodig hebt en voldoende geheugen hebt, is HNSW de winnaar.

De onderzoekers testten ook verschillende manieren om "gelijkenis" te meten (zoals hoe dicht twee punten in de ruimte bij elkaar liggen). Ze bevestigden dat voor bepaalde typen AI-modellen (zoals die gebruikt worden voor taal), je de data eerst moet normaliseren om de wiskunde correct te laten werken, maar zodra dat is gebeurd, houden de verschillende indexeringsstrategieën goed stand.

Kortom, deze studie biedt een praktische gids voor iedereen die AI-systemen bouwt. Het vertelt ons dat we niet alles tegelijk kunnen hebben (perfecte snelheid, perfecte nauwkeurigheid en nul geheugengebruik), maar dat we de juiste afweging kunnen maken voor onze specifieke behoeften. Of je nu een fraudedetectiesysteem voor een bank bouwt of een zoekmachine voor medische dossiers, er is een specifieke indexeringsstrategie in deze toolkit die je zal helpen de naald in de hooiberg te vinden zonder de weg kwijt te raken.