Efficient Vector Search in the Wild: One Model for Multi-K Queries

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een enorme bibliotheek hebt met miljarden boeken, maar in plaats van titels, zijn ze allemaal geschreven in een geheim taal van cijfers (vectoren). Je wilt voor een klant de K meest vergelijkbare boeken vinden. Soms wil de klant 1 boek (K=1), soms 50, en soms 100.

Het probleem met de huidige bibliothecarissen (de software die deze zoekopdrachten doet) is dat ze vaak "stom" zijn. Ze zijn getraind om precies één aantal boeken te vinden.

Als je ze traint om 1 boek te vinden, en je vraagt er 50, dan stoppen ze te vroeg. Ze vinden maar 1 boek en zeggen: "Klaar!" (Te weinig boeken, slechte kwaliteit).
Als je ze traint om 50 boeken te vinden, en je vraagt er 1, dan zoeken ze nog steeds naar 50 boeken voordat ze stoppen. Ze verspillen tijd en energie (Te traag).

Om dit op te lossen, zouden bibliothecarissen getraind moeten worden voor elk mogelijk aantal boeken. Maar dat duurt eeuwen om te doen en kost een fortuin aan computerkracht voordat je überhaupt kunt beginnen.

OMEGA is de nieuwe, slimme bibliothecaris die dit probleem oplost. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De "Meester van de Eerste" (De Basis)

In plaats van een team van bibliothecarissen aan te stellen voor elk aantal boeken, trainen we één super-slimme bibliothecaris. Deze is gespecialiseerd in het vinden van het allerbeste boek (K=1). Hij is zo goed dat hij precies weet wanneer hij het juiste boek heeft gevonden zonder de hele bibliotheek te doorzoeken.

2. De "Magische Verbergtruc" (Refinement)

Nu wil je 50 boeken vinden. Hoe doet OMEGA dit met alleen die ene specialist?

De specialist vindt het beste boek.
Vervolgens doen we alsof dat boek niet bestaat (we "maskeren" het). We plakken er een post-it op en zeggen: "Dit boek telt niet mee."
Vraag de specialist nu opnieuw: "Wat is nu het beste boek van de rest?"
Omdat het eerste boek weg is, is het nieuwe "beste" eigenlijk het tweede beste boek van de originele lijst.
We herhalen dit: verberg het tweede, vraag om het beste van de rest (dat is het derde), enzovoort.

Dit klinkt misschien als veel werk, maar omdat de specialist zo snel is, is dit veel sneller dan een trage bibliothecaris die voor elk aantal boeken apart getraind moet worden.

3. De "Kijk in de Crystal Ball" (Statistieken)

Er is nog één probleem: als je 100 boeken wilt, moet je de specialist 100 keer vragen om te werken. Dat is nog steeds veel werk.
OMEGA heeft een slimme truc: Statistieken.

Stel je voor dat je de specialist hebt gevraagd om de eerste 20 boeken te vinden. OMEGA kijkt dan niet meer naar de specialist, maar pakt een voorspellingskaart (een tabel met statistieken).

De kaart zegt: "Als we al 20 goede boeken hebben gevonden, is de kans 99% dat we binnen de volgende 50 stappen de rest van de 100 boeken ook wel vinden."
Als de kaart zegt dat we waarschijnlijk genoeg hebben, stopt OMEGA met vragen aan de specialist. Hij zegt: "Oké, we zijn klaar!"
Dit bespaart enorm veel tijd omdat de specialist niet elke keer hoeft te worden opgeroepen.

Waarom is dit geweldig? (De Voordelen)

Snelheid: Omdat OMEGA niet overbodig zoekt (zoals de trage bibliothecaris die altijd naar 50 boeken zoekt, zelfs als je er 1 wilt), is hij veel sneller.
Kwaliteit: Hij mist nooit de goede boeken, zelfs niet als je een groot aantal (K) vraagt.
Kosten: Het kost veel minder tijd en energie om de "Meester van de Eerste" te trainen dan om een heel team voor elk aantal boeken te trainen. In de paper zeggen ze dat ze met 16% tot 30% van de voorbereidingstijd van andere systemen, net zo goed (of beter) presteren.

Kortom:
OMEGA is als een slimme jager die niet voor elke jacht een nieuw wapen nodig heeft. Hij heeft één perfect wapen om het eerste dier te vangen. Als hij meer dieren nodig heeft, gebruikt hij een slimme truc om het eerste dier even te verstoppen en vraagt hij om het volgende. En als hij genoeg heeft, kijkt hij even op zijn horloge en statistieken om te zien of hij kan stoppen, in plaats van blindelings verder te jagen.

Dit maakt het zoeken in enorme databases veel sneller, goedkoper en nauwkeuriger, of je nu 1 of 100 resultaten nodig hebt.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het paper "Efficient Vector Search in the Wild: One Model for Multi-K Queries" (OMEGA), geschreven in het Nederlands.

Titel: Efficiënte Vectorzoekopdrachten in het Wild: Eén Model voor Multi-K Query's

Auteurs: Yifan Peng et al. (Shanghai Jiao Tong University, Boston University, Alibaba Group)

1. Het Probleem

Vector-databases zijn essentieel voor toepassingen zoals aanbevelingssystemen en Retrieval-Augmented Generation (RAG). De kernoperatie is de Approximate Nearest Neighbor Search (ANNS), waarbij de $K$ meest vergelijkbare vectoren worden gevonden.

Huidige systemen kampen met twee fundamentele uitdagingen in real-world scenario's ("in the wild"):

Multi-K Query's: In productieomgevingen (zoals bij Alibaba) variëren de vereiste resultaten ( $K$ $K$ ) per query sterk, afhankelijk van de applicatiecontext. Bestaande "learned search" modellen (zoals DARTH en LAET) zijn echter getraind voor één specifieke $K$ $K$ -waarde.
- Als een model getraind is op een kleine $K$ en wordt gebruikt voor een grote $K$ , treedt er onderzoek op (accuracy degradeert).
- Als een model getraind is op een grote $K$ en wordt gebruikt voor een kleine $K$ , treedt er overzoek op (latentie neemt onnodig toe).
Preprocessing Kosten: Om modellen voor verschillende $K$ -waarden te ondersteunen, zouden meerdere modellen getraind moeten worden. Dit leidt tot een enorme toename in preprocessing-tijd (bijvoorbeeld een verdubbeling of meer), wat onacceptabel is omdat vendors vaak geen kosten doorberekenen voor preprocessing en deze tijd ten koste gaat van de beschikbaarheid van de database.

De bestaande aanpak vereist dus een afweging tussen hoge nauwkeurigheid, lage latentie en acceptabele preprocessing-kosten, wat met huidige methoden niet gelijktijdig haalbaar is voor diverse $K$ -waarden.

2. Methodologie: OMEGA

OMEGA (One-Model Efficient Generalized ANNS) is een nieuwe methode die één enkel model trainen op $K=1$ (top-1) en dit generaliseert naar willekeurige $K$ -waarden met dynamische verfijning.

Kernidee: Reductie tot Top-1

In plaats van een model te trainen dat direct $K$ resultaten voorspelt, reduceert OMEGA het probleem van het vinden van top- $K$ tot $K$ opeenvolgende top-1 zoekopdrachten:

Het model voorspelt of de huidige zoekset de top-1 vector bevat.
Zodra de top-1 gevonden is, wordt deze vector "gemaskerd" (uitgesloten) in de zoekset.
Hetzelfde model wordt opnieuw aangeroepen om de top-1 van de overgebleven vectoren te vinden (wat effectief de top-2 van de originele set is).
Dit proces wordt herhaald tot $K$ resultaten zijn gevonden.

Uitdaging 1: Effectieve Feature Engineering (Traject-gebaseerde Features)

Bestaande modellen gebruiken features zoals de "minimale afstand" van de zoekset. Deze features falen bij masking, omdat de afstand tot de nieuwe top-1 (oorspronkelijk top-2) anders is dan wat het model heeft geleerd.

Oplossing: OMEGA introduceert distance-trajectory features. Dit is het patroon van afstandsreductie tijdens het doorlopen van de graaf.
Generalisatie: Het patroon van een scherpe afname in afstand wanneer men de doelvector nadert, blijft consistent gelden, zelfs na het maskeren van eerdere vectoren. Hierdoor kan een model getraind op top-1 data succesvol worden gebruikt voor top- $K$ zoekopdrachten.

Uitdaging 2: Vermindering van Model-uitvoeringskosten

Het iteratief aanroepen van het model $K$ keer zou de voordelen teniet kunnen doen door de overhead van modelinvoeringen.

Oplossing: OMEGA gebruikt een statistische voorspelling.
Er wordt een vooraf berekende lookup-tabel gebruikt die de kans aangeeft dat de $r$ -de ground-truth vector in de zoekset zit, gegeven dat $N$ vectoren al zijn gevonden ( $N < r$ ).
Als de statistisch voorspelde recall de doelwaarde bereikt, wordt de zoekopdracht vroegtijdig stopgezet zonder het model verder aan te roepen. Dit elimineert veel overbodige modelinvoeringen voor grotere $K$ -waarden.

3. Belangrijkste Bijdragen

Eén Model voor Alle K: OMEGA is de eerste methode die één model (getraind op $K=1$ ) gebruikt om willekeurige $K$ -query's te bedienen met hoge nauwkeurigheid.
Dynamische Verfijning: Een innovatieve aanpak waarbij top- $K$ wordt opgelost door iteratief top-1 zoekopdrachten uit te voeren met gemaskerde zoeksets.
Traject-Features: De identificatie en validatie van "distance-trajectory" als een robuust feature dat generaliseert over gemaskerde vectoren, in tegenstelling tot statische afstandsfeatures.
Statistische Optimalisatie: Een hybride aanpak die machine learning combineert met statistische voorspelling om de kosten van modelinvoering te minimaliseren.
Open Source Implementatie: De code is beschikbaar gesteld en wordt geïntegreerd in Alibaba's open-source vectordatabase Zvec.

4. Resultaten

OMEGA is geëvalueerd op drie open-source datasets (BIGANN, DEEP, GIST) en drie productie-datasets van Alibaba, met gebruik van real-world multi-K traces.

Preprocessing Kosten: OMEGA vereist slechts 16–30% van de preprocessing-tijd van state-of-the-art methoden (zoals DARTH met meerdere modellen) om dezelfde recall-doelstellingen te bereiken.
Latentie:
- Bij gelijke preprocessing-budgetten is OMEGA 6–33% sneller dan bestaande learned search methoden.
- OMEGA bereikt de optimale latentie van de baselines met slechts een fractie van de trainingskosten.
- Er is een significante verbetering in de tail-latentie (P90 en P99), met reducties tot wel 42% voor de langzaamste query's.
Nauwkeurigheid: OMEGA behaalt consistent de doelrecall (bijv. 0.95 of 0.99) voor alle $K$ -waarden, terwijl andere methoden bij het generaliseren naar andere $K$ -waarden vaak in nauwkeurigheid of performance inleveren.
Totale CPU-kosten: Door de lagere latentie tijdens het serveren, verlaagt OMEGA de totale CPU-tijd (preprocessing + serving) met 4–24% ten opzichte van bestaande methoden.

5. Betekenis en Impact

Dit paper lost een kritiek probleem op in de productie van vector-databases: de onverenigbaarheid tussen de behoefte aan flexibele query's (multi-K) en de kosten van machine learning-modellen.

Praktische Toepasbaarheid: OMEGA maakt het mogelijk om learned search in productie te gebruiken zonder de onhoudbare preprocessing-kosten van het trainen van honderden modellen.
Efficiëntie: Het bewijst dat een goed ontworpen, generaliseerbaar model (gebaseerd op top-1 logica en traject-features) superieur is aan gespecialiseerde modellen voor elke specifieke $K$ .
Toekomst: De methode biedt een nieuwe richting voor het optimaliseren van graf-gebaseerde ANN-search, waarbij de focus ligt op dynamische aanpassing in plaats van statische configuratie.

Kortom, OMEGA biedt een schaalbare, kostenefficiënte oplossing voor de complexe realiteit van vectorzoekopdrachten in de cloud, waarbij hoge snelheid en nauwkeurigheid hand in hand gaan met minimale operationele overhead.