Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

Dit paper introduceert PAG, een nieuw framework voor benaderde dichtstbijzijnde buurzoekopdrachten dat projectietechnieken integreert in een grafindex om tegelijkertijd hoge query-efficiëntie, snelle indexering, een beperkt geheugengebruik en schaalbaarheid te bieden, wat resulteert tot vijf keer snellere prestaties dan HNSW.

De kern

Stel je voor dat je een enorme bibliotheek hebt met miljarden boeken, maar je weet niet precies welke titel je zoekt. Je wilt gewoon een paar boeken vinden die lijken op wat je in gedachten hebt. In de wereld van kunstmatige intelligentie (AI) noemen we dit "Approximate Nearest Neighbor Search" (ANNS). Het is de techniek die zorgt dat je foto's kunt zoeken met een andere foto, of dat een chatbot de juiste context uit een enorme hoeveelheid data haalt.

Het probleem is: hoe vind je die boeken snel, zonder dat je elke stap in de bibliotheek moet aflopen? Bestaande methoden zijn vaak traag bij het aanleggen van de index (het ordenen van de boeken) of vergeten dat moderne AI-datasets heel anders zijn dan oude.

De auteurs van dit paper hebben een nieuwe oplossing bedacht: PAG (Projection-Augmented Graph). Laten we dit uitleggen met een paar creatieve vergelijkingen.

1. Het Probleem: De "Grote Druk"

Stel je voor dat je een enorme kaart van een stad hebt (de data). Je wilt weten welke huizen het dichtst bij een nieuw punt liggen.

• Oude methoden (zoals HNSW): Dit is alsof je een routeplanner gebruikt die elke straat exact uitrekent. Het is nauwkeurig, maar het duurt eeuwen om de kaart te tekenen (indexeren) en kost veel ruimte op je harde schijf.
• De nieuwe eisen: Moderne AI (zoals Chatbots of beeldherkenning) heeft datasets die gigantisch groot zijn, met heel veel details (hoge dimensies). We willen dat het systeem:
  1. Snel zoekt.
  2. Snel de kaart maakt.
  3. Niet te veel geheugen gebruikt.
  4. Snel nieuwe boeken (data) toevoegt zonder alles opnieuw te hoeven ordenen.

2. De Oplossing: PAG (De Slimme Gids)

PAG is als een slimme gids die een kaart tekent, maar die gids heeft een magische bril en een notitieblok.

De Magische Brillen: Projectie

In plaats van elke afstand exact uit te rekenen (wat veel rekenkracht kost), kijkt de gids eerst door een "magische bril" (een wiskundige techniek genaamd projectie).

• De analogie: Stel je voor dat je in een donkere kamer staat en iemand vraagt: "Is die persoon links of rechts van mij?" In plaats van de persoon aan te raken en de exacte afstand te meten, kijkt de gids naar de schaduw die de persoon werpt op de muur.
• Als de schaduw duidelijk te ver weg is, hoeft de gids de persoon niet eens aan te raken. Hij zegt: "Nee, die is te ver, we zoeken verder."
• Dit bespaart enorm veel tijd omdat de gids duizenden mensen niet hoeft aan te raken, maar alleen diegene die er echt dichtbij lijken.

Het Notitieblok: De "Test Feedback Buffer" (TFB)

Soms kijkt de gids door de bril en denkt hij: "Die persoon is dichtbij!", maar als hij hem toch even meet, blijkt hij net iets te ver weg te zijn. Dit noemen we een "valse positief".

• Het oude probleem: De gids zou die persoon dan vergeten en nooit meer kijken.
• De PAG-methode: De gids schrijft die persoon op in een speciaal notitieblok (de Test Feedback Buffer). Als de gids later weer door de bril kijkt, zegt hij: "Oh, die persoon stond al op mijn lijstje als 'misschien dichtbij', dus ik geef hem nog een kans."
• Dit zorgt ervoor dat de gids geen fouten maakt en steeds slimmer wordt tijdens het zoeken.

De Slimme Route: "Probabilistic Edge Selection" (PES)

Bij het aanleggen van de kaart (indexeren) moet de gids beslissen welke huizen met elkaar verbonden moeten worden.

• Het oude probleem: Soms mist de gids een belangrijke verbinding omdat hij alleen naar de directe buren keek.
• De PAG-methode: De gids kijkt ook naar mensen die hij al heeft bezocht tijdens zijn zoektocht, niet alleen naar de directe buren. Hij zegt: "Ik heb deze persoon al eens gezien, hij lijkt op mijn doel, dus ik maak een verbinding tussen hen."
• Hierdoor wordt de kaart veel robuuster. Zelfs als je een heel groot gebied moet doorzoeken, kun je altijd een weg vinden.

3. Waarom is dit zo goed?

De auteurs hebben dit getest op moderne datasets (zoals tekst van AI-modellen en afbeeldingen). De resultaten zijn indrukwekkend:

• Snelheid: PAG is tot 5 keer sneller dan de huidige standaard (HNSW) bij het zoeken.
• Snelheid bij bouwen: Het aanleggen van de index gaat veel sneller, wat betekent dat je AI-applicaties sneller kunt lanceren.
• Geheugen: Het gebruikt minder geheugen, wat belangrijk is voor grote systemen.
• Levendig: Je kunt nieuwe data toevoegen terwijl het systeem draait (zoals een chatbot die nieuwe gesprekken leert), zonder dat het systeem vastloopt.

Samenvatting in één zin

PAG is als een super-snelle, slimme bibliothecaris die niet elke boekenplank hoeft te controleren, maar door slim te gissen (met projecties) en fouten op te slaan in een notitieblok, de juiste boeken in een fractie van de tijd vindt, terwijl hij tegelijkertijd de bibliotheek razendsnel ordent.

Het is een grote stap voorwaarts voor AI-systemen die snel, efficiënt en slim moeten werken in de echte wereld.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach" in het Nederlands.

1. Probleemstelling

Approximate Nearest Neighbor Search (ANNS) is fundamenteel voor moderne AI-toepassingen zoals beeldzoekopdrachten, aanbevelingssystemen en Retrieval-Augmented Generation (RAG). Bestaande oplossingen, zoals HNSW (Hierarchical Navigable Small World), optimaliseren vaak de query-efficiëntie, maar sluiten niet volledig aan bij de eisen van moderne werklasten.

De auteurs identificeren zes kritieke eisen waaraan een moderne ANNS-oplossing moet voldoen, die vaak in conflict staan met bestaande methoden:

1. Hoge query-efficiëntie (QPS-recall): Snelheid bij hoge nauwkeurigheid.
2. Snelle indexering: Huidige grafische indexen (zoals HNSW) zijn vaak traag om te bouwen, wat instant-deployments belemmert.
3. Laag geheugengebruik: Een goede afweging tussen indexgrootte en nauwkeurigheid.
4. Schaalbaarheid naar hoge dimensies: Moderne embedding-modellen (zoals CLIP) genereren vectoren met zeer hoge dimensies (bijv. 1536 of 3072), waarbij bestaande methoden in nauwkeurigheid kunnen inboeten.
5. Robuustheid bij variërende zoekgroottes (K): Prestaties moeten stabiel blijven, of het nu gaat om K=10 (voor RAG) of K=1000+ (voor aanbevelingssystemen).
6. Ondersteuning voor online inserties: Het vermogen om data dynamisch toe te voegen zonder de index volledig te herbouwen.

Bestaande methoden (grafisch, kwantisatie-gebaseerd, projectie-gebaseerd) slagen er zelden in om aan alle zes deze eisen tegelijk te voldoen. Grafische methoden zijn snel in zoekopdrachten maar traag in indexering; kwantisatiemethoden zijn snel in indexering maar minder nauwkeurig bij hoge K of hoge dimensies.

2. Methodologie: Projection-Augmented Graph (PAG)

De auteurs introduceren PAG, een nieuw framework dat projectietechnieken naadloos integreert in een grafische index. In tegenstelling tot eerdere "Projectie + Grafiek" (PG) methoden die projectie als een plug-in gebruiken, behandelt PAG projectie als een fundamenteel bouwsteen van de grafiekconstructie.

Het kernprincipe is het verminderen van onnodige exacte afstandsberaken door asymmetrische vergelijkingen tussen exacte en benaderde afstanden te gebruiken, geleid door statistische tests op basis van random projecties.

Drie Kerncomponenten

PAG bestaat uit drie geïntegreerde componenten:

1. Probabilistic Routing Test (PRT):

   • Een testfunctie die bepaalt of een exacte afstand tussen een query en een kandidaat-buurnode berekend moet worden.
   • Het gebruikt een set van random projectievectoren om hoeken tussen vectoren te schatten zonder de volledige dimensie te verwerken.
   • Als de geschatte hoek een bepaalde drempel overschrijdt, wordt de exacte berekening overgeslagen. Dit versnelt zowel het zoeken als het bouwen van de index.

2. Test Feedback Buffer (TFB):

   • Een datastructuur die de drempelwaarden voor PRT dynamisch optimaliseert.
   • TFB verzamelt "false positives" (kandidaten die de PRT-test passeerden maar uiteindelijk niet tot de beste resultaten behoorden) en hergebruikt deze in latere rondes van de zoektocht.
   • Dit zorgt voor een incrementele verhoging van de drempel, waardoor onnodige berekeningen worden geminimaliseerd en de indexering sneller verloopt.

3. Probabilistic Edge Selection (PES):

   • Een statistische test die wordt gebruikt tijdens het bouwen van de grafiek om de connectiviteit te verbeteren.
   • Waar traditionele methoden (zoals RobustPrune) alleen kijken naar de huidige uit-buurnodes, gebruikt PES random projecties om te bepalen of andere bezochte nodes (die verder weg liggen) toch waardevolle in-buurnodes zouden kunnen zijn.
   • Dit lost het probleem op van nodes met een te klein in-degraad, wat de zoekkwaliteit in complexe datasets verbetert.

Deze componenten werken samen in een search-and-insertion paradigma, wat betekent dat PAG natuurlijk online inserties ondersteunt zonder de index te hoeven herbouwen.

3. Belangrijkste Bijdragen

• Unificatie van Exacte en Benaderde Afstanden: PAG biedt een theoretisch onderbouwd raamwerk dat exacte en benaderde afstanden combineert via asymmetrische vergelijkingen, in plaats van symmetrische vergelijkingen zoals bij kwantisatie-gebaseerde grafieken.
• Theoretische Fundamenten: De auteurs leveren een complete theoretische verklaring voor de PRT-functie (via Theorem 3.1) en tonen aan hoe random projecties asymptotisch hoeken in hoge dimensies kunnen schatten.
• Nieuwe Datastructuren: De introductie van de Test Feedback Buffer (TFB) en Probabilistic Edge Selection (PES) als nieuwe mechanismen om de efficiëntie van indexering en zoekopdrachten te maximaliseren.
• Uitgebreide Evaluatie: Experimenten op zes moderne datasets (post-2023) met dimensies van 384 tot 3072, inclusief tekst, afbeeldingen en multimodale data.

4. Resultaten

De experimenten tonen aan dat PAG superieure prestaties levert ten opzichte van state-of-the-art methoden zoals HNSW, Vamana, SymQG en ScaNN:

• Snelheid (QPS): PAG-Base is tot 5 keer sneller dan HNSW bij vergelijkbare recall-waarden.
• Indexeringstijd: PAG-Base vereist slechts 20-40% van de tijd die HNSW nodig heeft voor indexering. PAG-Lite (geoptimaliseerd voor snelheid) is zelfs nog sneller, vergelijkbaar met kwantisatiemethoden.
• Geheugengebruik: PAG heeft een gematigd geheugengebruik en is aanzienlijk efficiënter dan SymQG, vooral bij hoge dimensies.
• Schaalbaarheid: PAG presteert consistent goed bij toenemende dimensies (tot 3072), waar andere methoden (zoals SymQG) in recall sterk dalen.
• Robuustheid: De prestaties blijven stabiel bij variërende zoekgroottes (K=10 tot K=1000).
• Online Inserties: PAG ondersteunt online inserties met een amortisatiekosten die vergelijkbaar is met zoekopdrachten, wat essentieel is voor zelfevoluerende agents.

5. Betekenis en Impact

Dit paper is significant omdat het de kloof overbrugt tussen de theoretische efficiëntie van projectie-gebaseerde methoden en de praktische robuustheid van grafische methoden.

• Modernisering van ANNS: Het adresseert de beperkingen van bestaande benchmarks (die vaak verouderde datasets gebruiken) en biedt een oplossing die specifiek is ontworpen voor de eisen van moderne Large Language Models (LLMs) en multimodale AI.
• Praktische Toepasbaarheid: Door de combinatie van snelle indexering, lage geheugeneisen en ondersteuning voor dynamische data, maakt PAG ANNS haalbaar voor real-time toepassingen zoals self-evolving agents en live aanbevelingssystemen.
• Open Source: De broncode is beschikbaar gesteld, wat de adoptie en verdere ontwikkeling in de gemeenschap bevordert.

Kortom, PAG stelt een nieuwe standaard voor Approximate Nearest Neighbor Search die niet alleen sneller is, maar ook schaalbaarder en flexibeler voor de toekomst van AI-toepassingen.