🤖 AI

ANN Search: Recall What Matters

Dit artikel betoogt dat de standaard Recall@k-metriek voor Approximate Nearest Neighbor (ANN)-zoekopdrachten een gebrekkige proxy is voor werkelijke bruikbaarheid omdat deze de overlap tussen verzamelingen boven de kwaliteit van resultaten prioriteert, en stelt de inverse benaderingsratio (1/Ratio@k) voor als een nauwkeurigere, efficiëntere en inzetbare metriek die beter correleert met de prestaties van downstream-taken terwijl de onnodige computationele overhead wordt verminderd.

Oorspronkelijke auteurs: Dimitris Dimitropoulos, Nikos Mamoulis

Gepubliceerd 2026-06-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Dimitris Dimitropoulos, Nikos Mamoulis

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 op zoek bent naar de drie beste appels in een enorme boomgaard om een taart van te maken. Je hebt een supersnelle robothelper (het ANN-algoritme) die de boomgaard in een fractie van een seconde kan scannen.

Jarenlang heeft de gemeenschap deze robot beoordeeld op basis van één strikte regel: heeft hij exact dezelfde drie appels gepakt als een menselijke expert zou hebben gedaan? Deze regel wordt Recall genoemd. Als de mens appels A, B en C koos, en de robot koos A, B en D, dan krijgt de robot een slechte score, zelfs als appel D net zo zoet en perfect is voor de taart als appel C.

De auteurs van dit artikel betogen dat deze regel gebrekkig is. Ze zeggen: "Stop met het obsessief controleren van de exacte ID van de appel; proef gewoon de appel."

Hier is de uiteenzetting van hun argument met behulp van eenvoudige analogieën:

1. Het Probleen: De obsessie met het "Naamkaartje"

In de wereld van AI worden gegevens vaak gerepresenteerd als punten in een meerdimensionale ruimte (zoals een gigantische, onzichtbare wolk van stippen). Wanneer je de ANN vraagt om de "dichtstbijzijnde" buren (de beste appels) te vinden, geeft hij een lijst terug.

De Oude Manier (Recall): Het systeem controleert of de robot exact dezelfde ID's heeft geretourneerd als de perfecte lijst.
De Realiteit: In hoogdimensionale ruimtes (zoals complexe AI-modellen) zijn er vaak duizenden appels die bijna identiek zijn in smaak en afstand. De robot kan appel D kiezen in plaats van appel C. Ze zijn praktisch tweelingen. Maar omdat de ID anders is, stort de "Recall"-score in, waardoor de robot er slecht aan toe is.

De auteurs zeggen dat dit is alsof een leraar een leerling faalt die het juiste antwoord "4" heeft geschreven, omdat het antwoordmodel van de leraar "4,00001" zei. De leerling heeft het goed, maar het beoordelingssysteem is te rigide.

2. De Nieuwe Oplossing: De "Smaaktest" (1/Ratio)

De auteurs stellen een nieuwe metriek voor genaamd 1/Ratio. In plaats van te controleren of de robot de exacte appels heeft gekozen, meet het hoe dicht de appels bij de perfecte exemplaren liggen.

De Analogie: Stel je voor dat de perfecte appels op een tafel liggen.
- Recall vraagt: "Heb je exact de appels gepakt die op de tafel liggen?"
- 1/Ratio vraagt: "Hoe ver van de tafel moest je lopen om je appels te vinden?"

Als de robot een appel kiest die slechts 1 millimeter verwijderd is van de perfecte plek, geeft 1/Ratio een bijna perfecte score. Als hij een appel kiest die 10 kilometer verderop ligt, daalt de score. Deze metriek negeert het "naamkaartje" en focust op de werkelijke kwaliteit (afstand).

3. De Grote Ontdekking: Je kunt veel sneller gaan

De paper voerde tests uit op vijf verschillende soorten robothelpers (algoritmen) over zes verschillende soorten boomgaarden (datasets). Ze ontdekten een enorme verrassing:

De Kosten van Perfectie: Om een hoge Recall-score te halen (het kiezen van de exacte ID's), moesten de robots ongelooflijk hard werken door miljoenen extra appels te controleren. Dit vertraagde hen aanzienlijk.
De Efficiëntie van "Goed Genoeg": Wanneer de robots werden toegestaan te optimaliseren voor 1/Ratio (het kiezen van appels die zeer dicht bij de perfecte appels liggen, zelfs als de ID anders is), konden ze 3 tot 10 keer sneller werken.

De Metafoor: Het is alsof je probeert een specifere persoon in een menigte te vinden.

Recall eist dat je de exacte persoon vindt die de specifieke hoed draagt die je beschreven hebt. Je moet elk gezicht controleren.
1/Ratio staat je toe om de persoon direct naast hem te pakken die er voor 99,9% identiek uitziet. Je pakt diegene direct. Het resultaat is hetzelfde voor jouw doel, maar je bespaart uren tijd.

4. Werkt "Goed Genoeg" ook echt?

Sceptici zouden kunnen vragen: "Als we stoppen met het kiezen van de exacte appels, zal onze taart dan niet vies smaken?"

De auteurs testten dit in twee real-world scenario's:

Beeldclassificatie (Foto's sorteren): Ze probeerden foto's van katten en honden te sorteren. Zelfs toen de "Recall" van de robot laag was (hij miste de exacte "beste" foto's), bleef het uiteindelijke resultaat van het sorteren van de foto's bijna perfect accuraat. De "fouten" maakten niet uit.
RAG (Chatbots die zoeken): Ze testten een chatbot die vragen beantwoordt door een database te doorzoeken. Zelfs toen de zoekmachine de "exacte" perfecte documenten miste (lage Recall), gaf de chatbot nog steeds uitstekende antwoorden. De kwaliteit van het antwoord daalde niet.

De Conclusie: De "slechte" scores van de oude metriek waren een leugen. De robots deden eigenlijk een geweldig werk; ze kozen alleen niet de exacte ID's.

5. Waarom dit ertoe doet

De paper concludeert dat de AI-gemeenschap enorme hoeveelheden rekenkracht verspilt aan het streven naar een "perfecte" score (Recall) die de uiteindelijke resultaten eigenlijk niet beter maakt.

Oude Manier: "We hebben 100% Recall nodig!" -> Resultaat: Traag, duur en overontworpen.
Nieuwe Manier: "We hebben een hoge 1/Ratio nodig!" -> Resultaat: Veel sneller, goedkoper en het eindresultaat (de taart, de fotosortering, het antwoord van de chatbot) is net zo goed.

Kortom: Maak je niet druk om de exacte naam van de buurman die je hebt gevonden. Als hij vlak naast de perfecte buurman woont, is hij goed genoeg. En door dat te accepteren, kunnen we AI-systemen veel sneller en goedkoper laten draaien.

Technische Samenvatting: ANN Zoeken: Herinner wat ertoe doet

Probleemstelling

Approximate Nearest Neighbor (ANN) zoeken is een fundamentele primitieve in moderne informatieverwerking en machine learning, met name voor taken zoals classificatie en Retrieval-Augmented Generation (RAG). De gemeenschap heeft gestandaardiseerd op Recall@k (het deel van de ware exacte $k$ -dichtstbijzijnde buren dat wordt opgehaald) als de primaire metriek voor het evalueren en afstemmen van ANN-algoritmen. Onderzoekers optimaliseren voor doorvoer (Queries-Per-Second, QPS) bij vaste Recall-drempels.

De auteurs stellen dat deze conventie niet in lijn is met de werkelijke bruikbaarheid van ANN-systemen. In hoogdimensionale ruimtes (gebruikelijk in moderne embeddings) concentreren afstanden tot opeenvolgende buren zich, wat leidt tot veel "bijna-evenver`}elijke" kandidaten. Een ANN-algoritme kan punten ophalen die geometrisch even dicht bij de query liggen als de ware buren, maar andere identificatoren dragen. Onder Recall@k worden deze geometrisch accurate resultaten bestraft als missers, wat systemen dwingt om onnodige computationele overhead te dragen om een hoge overlap in identificatoren te bereiken. Het artikel stelt dat Recall@k de moeilijkheid van de taak en de kosten van benadering overschat, wat potentieel kan leiden tot suboptimale systeemconfiguraties.

Methodologie

Het artikel stelt voor om Recall@k te vervangen door 1/Ratio@k, de inverse van de benaderingsratio. In tegenstelling tot Recall, dat het aantal overeenkomende identificatoren telt, meet 1/Ratio@k de kwaliteit van de opgehaalde resultaten op basis van de afstanden van de teruggegeven buren ten opzichte van de ware $k$ -dichtstbijzijnde buren.

Kerndefinities:

Recall@k: $\frac{| \tilde{N}_k(q) \cap N_k(q) |}{k}$ , waarbij $\tilde{N}_k$ de opgehaalde verzameling is en $N_k$ de ware verzameling.
Ratio@k: Het gemiddelde van de afstandratio's per positie: $\frac{1}{k} \sum_{i=1}^k \frac{\tilde{d}_i(q)}{d_i(q)}$ , waarbij $\tilde{d}_i$ en $d_i$ de afstanden zijn naar respectievelijk de $i$ -de teruggegeven en de ware buur.
1/Ratio@k: De inverse van de bovenstaande ratio, variërend van 0 tot 1 (1 geeft perfecte retrieval aan).

Experimentele Opzet:
De auteurs hebben vijf state-of-the-art ANN-algoritmen getest over diverse datasets met variërende intrinsieke dimensionaliteit (LID):

Annoy (Boom-gebaseerd)
SuCo (Collision-gebaseerd)
HNSW (Graaf-gebaseerd, industriestandaard)
RaBitQ (Quantisatie-gebaseerd)
SymphonyQG (Hybride Graaf-Quantisatie)

De evaluatie omvatte zes datasets (Gist, SimpleWiki, ImageNet, AGNews, MNIST, Fashion-MNIST) en breidde zich uit naar downstream taken zoals beeldclassificatie (MNIST, Fashion-MNIST, CIFAR-10, SVHN) en RAG (SciFact, NFCorpus, HotpotQA, MS-MARCO, PubMedQA).

Evaluatiestrategie:

Efficiëntieanalyse: Gemeten de computationele kosten (QPS, afstandsberekeningen, bouwtijd, geheugen) die nodig zijn om specifieke kwaliteitsdrempels te bereiken ( $T \in \{0.90, 0.95, 0.99\}$ ) onder beide metrieken.
Downstream Validatie: Gebruikt synthetische recall-controle om de recall-niveaus kunstmatig te verslechteren ( $r \in [0.4, 1.0]$ ) terwijl de geometrische kwaliteit behouden bleef. Ze maten de downstream prestaties (Label Precision voor classificatie; BERTScore, Semantische Gelijkenis en door LLM beoordeelde scores voor RAG) om te bepalen of een lage Recall daadwerkelijk de bruikbaarheid vermindert.
Metriek Vergelijking: Berekende de Mean Absolute Deviation (MAD) tussen de metrieken (Recall versus 1/Ratio) en de ware downstream kwaliteit om te beoordelen welke metriek een betere proxy is.

Belangrijkste Bijdragen

Voorstel van 1/Ratio@k: Introduceerde een kwaliteitsmetriek die oordelingsvrij, hyperparameter-vrij en uitsluitend berekenbaar is vanuit standaard ANN-benchmarkinputs (embeddings en grondwaarheid-identificatoren). In tegenstelling tot alternatieven zoals Semantic Recall of Tolerant Recall, vereist het geen externe LLM-judges of instelbare tolerantieparameters.
Demonstratie van Computationele Overhead: Toonde aan dat het optimaliseren voor Recall@k een substantiële computationele straf oplegt vergeleken met het optimaliseren voor 1/Ratio@k.
Bewijs van Downstream Stabiliteit: Leverde empirisch bewijs dat downstream taakprestaties (classificatienauwkeurigheid en RAG-antwoordkwaliteit) stabiel blijven, zelfs wanneer de Recall aanzienlijk daalt (bijv. naar 0.4), mits de geometrische afstandskwaliteit (1/Ratio) hoog blijft.
Geometrische Verklaring: Koppelde de divergentie tussen Recall en 1/Ratio aan de Lokale Intrinsieke Dimensionaliteit (LID) en de buurtgrootte $k$ . Naarmate de LID en $k$ toenemen, neemt de kans toe dat een algoritme geometrisch nabije maar met een andere identificator gekoppelde buren ophaalt, wat de Recall doet dalen terwijl 1/Ratio hoog blijft.

Experimentele Resultaten

1. Efficiëntie en Kosten (RQ1 & RQ2)

Doorvoersnelheid (QPS): Het optimaliseren voor 1/Ratio@k levert een aanzienlijk hogere doorvoersnelheid op dan het optimaliseren voor Recall@k. Bij een kwaliteitsdrempel van $T=0.95$ $T = 0.95$ en $k=100$ $k = 100$ , varieert de versnelling van 1.86× tot 9.36× in afstandsberekeningen en 2× tot 10× in QPS, afhankelijk van het algoritme en de dataset.
- Voorbeeld: Op de ImageNet-dataset met HNSW is het bereiken van 1/Ratio@100 $\ge$ 0.95 9.98× sneller dan het bereiken van Recall@100 $\ge$ 0.95.
Bouwtijd: De kosten om indices te bouwen voor een hoge Recall zijn vaak hoger. Voor HNSW op Gist vereiste het bereiken van Recall $\ge$ 0.90 vaak 18.39× meer bouwtijd dan het bereiken van 1/Ratio $\ge$ 0.90.
Geheugen: De verschillen in geheugens footprint zijn minimaal. De kloof is meestal nabij 1.0×, aangezien het geheugen wordt gedomineerd door vectoropslag in plaats van de parameters die worden gebruikt om te tunen voor een hoge Recall.
Algoritme Rangschikking: De relatieve rangschikking van algoritmen (welke het snelst/goedkoopst is) blijft grotendeels stabiel tussen de twee metrieken. De verandering in metriek beïnvloedt de absolute kosten om een drempel te bereiken, niet de relatieve prestaties van de algoritmen.

2. Geometrische Divergentie (RQ3)

De kloof tussen Recall en 1/Ratio wordt groter naarmate $k$ toeneemt en naarmate de LID toeneemt.
In ruimtes met een hoge LID liggen buren bijna even ver weg. Een ANN-algoritme dat een vector teruggeeft met een andere ID maar een bijna identieke afstand, wordt zwaar gestraft door Recall, maar krijgt een hoge score van 1/Ratio.
Recall degradeert aanzienlijk naarmate $k$ groeit (bijv. een sterke daling van $k=1$ naar $k=100$ ), terwijl 1/Ratio relatief vlak blijft.

3. Downstream Taakkwaliteit (RQ4)

Beeldclassificatie: Terwijl de Recall daalde van 1.0 naar 0.4, bleef de Label Precision (LP@100) opmerkelijk stabiel (bijv. een daling van slechts 1.0 naar ~0.94 op SVHN).
- MAD Analyse: Recall had een Mean Absolute Deviation (voorspellingsfout) van ~26% van de ware kwaliteit. In tegenstelling hiertoe had 1/Ratio een fout van < 3% (vaak < 1%).
RAG Taken: De antwoordkwaliteit (gemeten via BERTScore, Semantische Gelijkenis en LLM-gradaties) vertoonde een verwaarloosbare degradatie wanneer de Recall daalde naar 0.4.
- Op menselijk geannoteerde benchmarks varieerden de tekstkwaliteitsmetrieken met minder dan 1.2%, ondanks een Recall-daling van 60%.
- 1/Ratio volgde deze stabiliteit nauwgezet, terwijl Recall een enorme kwaliteitsval signaleerde.
- MAD Analyse: Voor RAG was de voorspellingsfout van Recall ~30%, terwijl die van 1/Ratio < 3% was (vaak < 1%).

Betekenis en Claims

Het artikel beweert dat de afhankelijkheid van de community van Recall@k heeft geleid tot een onnodige over-engineering van ANN-systemen. Door te tunen voor een hoge Recall, dragen beoefenaars aanzienlijke computationele kosten (tijd, energie, latentie) voor het ophalen van resultaten die geometrisch ononderscheidbaar zijn van de grondwaarheid, maar falen op een identificator-matching test.

De auteurs concluderen dat:

1/Ratio@k een superieure proxy is voor de werkelijke downstream bruikbaarheid, omdat het de stabiliteit van de retrievalkwaliteit accuraat weerspieeft, zelfs wanneer de Recall laag is.
Het adopteren van 1/Ratio@k zorgt voor snellere, goedkopere en efficiëntere ANN-implementaties zonder de kwaliteit van de uiteindelijke toepassing (classificatie of generatie) op te offeren.
Configuraties die momenteel worden afgedaan als "onvoldoende" vanwege een lage Recall, zijn vaak operationeel voldoende en kunnen worden ingezet om aanzienlijke efficiëntiewinsten te behalen.

De studie pleit voor een verschuiving in het evaluatieparadigma van de ANN-onderzoeksgemeenschap: weg van het optimaliseren voor identificator-overlap (Recall) en naar het optimaliseren voor geometrische nabijheid (1/Ratio), waardoor de systeemtuning wordt afgestemd op de werkelijke vereisten van downstream machine learning taken.