🤖 AI

ANN Search: Recall What Matters

Dieses Paper argumentiert, dass die Standardmetrik Recall@k für die Approximate Nearest Neighbor (ANN)-Suche ein fehlerhaftes Stellvertretermaß für den tatsächlichen Nutzen ist, da sie die Mengenüberschneidung gegenüber der Ergebnisqualität priorisiert, und schlägt stattdessen das inverse Approximationsverhältnis (1/Ratio@k) als ein genaueres, effizienteres und besser einsetzbares Maß vor, das besser mit der Leistung nachgelagerter Aufgaben korreliert und gleichzeitig unnötigen Rechenaufwand reduziert.

Ursprüngliche Autoren: Dimitris Dimitropoulos, Nikos Mamoulis

Veröffentlicht 2026-06-04

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Dimitris Dimitropoulos, Nikos Mamoulis

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie suchen in einem riesigen Obstgarten nach den drei besten Äpfeln, um einen Kuchen zu backen. Sie haben einen superschnellen Roboter-Helfer (den ANN-Algorithmus), der den Obstgarten in einem Bruchteil einer Sekunde scannen kann.

Jahrelang hat die Fachwelt diesen Roboter nach einer strengen Regel bewertet: Hat er exakt dieselben drei Äpfel ausgewählt, die ein menschlicher Experte ausgewählt hätte? Diese Regel wird Recall (Trefferquote) genannt. Wenn der Mensch die Äpfel A, B und C ausgewählt hat, der Roboter aber A, B und D auswählt, erhält er eine schlechte Bewertung, selbst wenn Apfel D genauso süß und perfekt für den Kuchen ist wie Apfel C.

Die Autoren dieser Arbeit argumentieren, dass diese Regel fehlerhaft ist. Sie sagen: „Hören Sie auf, sich auf die exakte ID des Apfels zu fixieren; schmecken Sie einfach den Apfel.“

Hier ist die Aufschlüsselung ihres Arguments anhand einfacher Analogien:

1. Das Problem: Die Besessenheit vom „Namensschild“

In der Welt der KI werden Daten oft als Punkte in einem mehrdimensionalen Raum dargestellt (wie eine riesige, unsichtbare Punktwolke). Wenn Sie die „nächsten“ Nachbarn (die besten Äpfel) abfragen, liefert das System eine Liste zurück.

Der alte Weg (Recall): Das System prüft, ob der Roboter exakt dieselben IDs zurückgegeben hat wie die perfekte Liste.
Die Realität: In hochdimensionalen Räumen (wie komplexen KI-Modellen) gibt es oft Tausende von Äpfeln, die im Geschmack und in der Distanz fast identisch sind. Der Roboter wählt vielleicht Apfel D statt Apfel C. Sie sind praktisch Zwillinge. Aber weil die ID anders ist, bricht der „Recall“-Wert ein, was den Roboter schlecht aussehen lässt.

Die Autoren sagen, das sei so, als würde ein Lehrer einen Schüler durchfallen lassen, der die richtige Antwort „4“ geschrieben hat, weil die Antwortlösung des Lehrers „4,00001“ lautete. Der Schüler hat recht, aber das Bewertungssystem ist zu starr.

2. Die neue Lösung: Der „Geschmackstest“ (1/Ratio)

Die Autoren schlagen eine neue Metrik namens 1/Ratio vor. Anstatt zu prüfen, ob der Roboter exakt dieselben Äpfel ausgewählt hat, misst sie, wie nah die Äpfel an den perfekten liegen.

Die Analogie: Stellen Sie sich vor, die perfekten Äpfel liegen auf einem Tisch.
- Recall fragt: „Hast du exakt dieselben Äpfel vom Tisch gepickt?“
- 1/Ratio fragt: „Wie weit weg vom Tisch musstest du laufen, um deine Äpfel zu finden?“

Wenn der Roboter einen Apfel wählt, der nur 1 Millimeter vom perfekten Ort entfernt ist, vergibt 1/Ratio eine nahezu perfekte Punktzahl. Wählt er einen Apfel, der 10 Meilen entfernt ist, sinkt die Punktzahl. Diese Metrik ignoriert das „Namensschild“ und konzentriert sich auf die tatsächliche Qualität (Distanz).

3. Die große Entdeckung: Man kann viel schneller sein

Die Autoren ließen Tests mit fünf verschiedenen Arten von Roboter-Helfern (Algorithmen) in sechs verschiedenen Arten von Obstgärten (Datensätzen) laufen. Dabei fanden sie eine massive Überraschung:

Der Preis der Perfektion: Um eine hohe Recall-Punktzahl zu erreichen (exakt dieselben IDs zu finden), mussten die Roboter unglaublich hart arbeiten und Millionen zusätzlicher Äpfel prüfen. Das verlangsamte sie erheblich.
Die Effizienz von „Gut genug“: Als man den Robotern erlaubte, auf 1/Ratio zu optimieren (Äpfel zu wählen, die den perfekten sehr nahe kommen, auch wenn die ID anders ist), konnten sie 3- bis 10-mal schneller arbeiten.

Die Metapher: Es ist wie der Versuch, eine bestimmte Person in einer Menge zu finden.

Recall verlangt, dass Sie exakt die Person finden, die den spezifischen Hut trägt, den Sie beschrieben haben. Sie müssen jedes Gesicht kontrollieren.
1/Ratio erlaubt es Ihnen, die Person direkt neben ihr zu greifen, die zu 99,9 % identisch aussieht. Sie greifen sofort zu. Das Ergebnis ist für Ihren Zweck dasselbe, aber Sie haben Stunden gespart.

4. Funktioniert „Gut genug“ tatsächlich?

Skeptiker könnten fragen: „Wenn wir aufhören, die exakten Äpfel zu wählen, wird unser Kuchen dann schlecht schmecken?“

Die Autoren testeten dies in zwei realen Szenarien:

Bildklassifizierung (Sortieren von Fotos): Sie versuchten, Fotos von Katzen und Hunden zu sortieren. Selbst wenn der „Recall“ des Roboters niedrig war (er verpasste die exakten „besten“ Fotos), blieb das Endergebnis beim Sortieren der Fotos fast perfekt genau. Die „Fehler“ spielten keine Rolle.
RAG (Chatbots, die eine Suche nutzen): Sie testeten einen Chatbot, der Fragen beantwortet, indem er eine Datenbank durchsucht. Selbst wenn die Suchmaschine die „exakten“ perfekten Dokumente verfehlte (niedriger Recall), lieferte der Chatbot immer noch hervorragende Antworten. Die Qualität der Antwort sank nicht.

Das Fazit: Die „schlechten“ Bewertungen der alten Metrik waren eine Lüge. Die Roboter haben eigentlich einen großartigen Job gemacht; sie haben nur nicht die exakten IDs ausgewählt.

5. Warum das wichtig ist

Die Autoren kommen zu dem Schluss, dass die KI-Community enorme Mengen an Rechenleistung verschwendet hat, um eine „perfekte“ Punktzahl (Recall) zu erreichen, die das eigentliche Ergebnis gar nicht besser macht.

Alter Weg: „Wir brauchen 100 % Recall!“ -> Ergebnis: Langsam, teuer und überdimensioniert.
Neuer Weg: „Wir brauchen ein hohes 1/Ratio!“ -> Ergebnis: Viel schneller, günstiger und das Endergebnis (der Kuchen, die Fotosortierung, die Chatbot-Antwort) ist genauso gut.

Kurz gesagt: Sorgen Sie sich nicht um den exakten Namen des Nachbarn, den Sie gefunden haben. Wenn er direkt neben dem perfekten Nachbarn wohnt, ist er gut genug. Und indem wir das akzeptieren, können wir KI-Systeme viel schneller und kostengünstiger machen.

Technisches Resümee: ANN-Suche: Recall verstehen, was zählt

Problemstellung

Die approximative Annäherungssuche (Approximate Nearest Neighbor, ANN) ist eine grundlegende Primitive in der modernen Informationsabfrage und im maschinellen Lernen, insbesondere für Aufgaben wie Klassifizierung und Retrieval-Augmented Generation (RAG). Die Fachwelt hat sich auf Recall@k (den Bruchteil der echten exakten $k$ -nächsten Nachbarn, die abgerufen wurden) als primäre Metrik zur Evaluierung und Abstimmung von ANN-Algorithmen geeinigt. Forscher optimieren für den Durchsatz (Queries-Per-Second, QPS) bei festen Recall-Schwellenwerten.

Die Autoren argumentieren, dass diese Konvention nicht mit dem tatsächlichen Nutzen von ANN-Systemen übereinstimmt. In hochdimensionalen Räumen (häufig bei modernen Embeddings) konzentrieren sich die Distanzen zu aufeinanderfolgenden Nachbarn, was dazu führt, dass viele „nahezu äquidistante“ Kandidaten existieren. Ein ANN-Algorithmus kann Punkte abrufen, die geometrisch gesehen genauso nah an der Abfrage liegen wie die wahren Nachbarn, aber andere Identifikatoren tragen. Unter Recall@k werden diese geometrisch korrekten Ergebnisse als Fehlgriffe gewertet, was Systeme dazu zwingt, unnötigen Rechenaufwand zu betreiben, um eine hohe Identifikator-Überlappung zu erreichen. Das Paper postuliert, dass Recall@k die Schwierigkeit der Aufgabe und die Kosten der Approximation überschätzt, was potenziell zu suboptimalen Systemkonfigurationen führt.

Methodik

Das Paper schlägt vor, Recall@k durch 1/Ratio@k, das Inverse des Approximationsverhältnisses, zu ersetzen. Im Gegensatz zu Recall, das Identifikator-Übereinstimmungen zählt, misst 1/Ratio@k die Qualität der abgerufenen Ergebnisse basierend auf den Distanzen der zurückgegebenen Nachbarn im Verhältnis zu den wahren $k$ -nächsten Nachbarn.

Kern-Definitionen:

Recall@k: $\frac{| \tilde{N}_k(q) \cap N_k(q) |}{k}$ , wobei $\tilde{N}_k$ die abgerufene Menge und $N_k$ die wahre Menge ist.
Ratio@k: Der Mittelwert der pro-Position Distanzverhältnisse: $\frac{1}{k} \sum_{i=1}^k \frac{\tilde{d}_i(q)}{d_i(q)}$ , wobei $\tilde{d}_i$ und $d_i$ die Distanzen zum $i$ -ten zurückgegebenen bzw. wahren Nachbarn sind.
1/Ratio@k: Das Inverse des obigen Verhältnisses, das von 0 bis 1 reicht (1 bedeutet perfekte Abrufe).

Experimenteller Aufbau:
Die Autoren haben fünf State-of-the-Art ANN-Algorithmen über diverse Datensätze mit variierender intrinsischer Dimensionalität (LID) benchmarkt:

Annoy (Baumbasiert)
SuCo (Kollisionsbasiert)
HNSW (Graphbasiert, Industriestandard)
RaBitQ (Quantisierungsbasiert)
SymphonyQG (Hybrider Graph-Quantisierungs-Ansatz)

Die Evaluierung deckte sechs Datensätze (Gist, SimpleWiki, ImageNet, AGNews, MNIST, Fashion-MNIST) ab und erweiterte dies auf Downstream-Aufgaben wie Bildklassifizierung (MNIST, Fashion-MNIST, CIFAR-10, SVHN) und RAG (SciFact, NFCorpus, HotpotQA, MS-MARCO, PubMedQA).

Evaluierungsstrategie:

Effizienzanalyse: Messung der Rechenkosten (QPS, Distanzberechnungen, Build-Zeit, Speicher) erforderlich, um spezifische Qualitäts-Schwellenwerte ( $T \in \{0,90, 0,95, 0,99\}$ ) unter beiden Metriken zu erreichen.
Downstream-Validierung: Verwendung einer synthetischen Recall-Kontrolle, um die Recall-Level künstlich zu verschlechtern ( $r \in [0,4, 1,0]$ ), während die geometrische Qualität beibehalten wurde. Sie maßen die Downstream-Performance (Label Precision für Klassifizierung; BERTScore, semantische Ähnlichkeit und LLM-bewertete Scores für RAG), um zu bestimmen, ob ein niedriger Recall tatsächlich den Nutzen mindert.
Metriken-Vergleich: Berechnung der mittleren absoluten Abweichung (Mean Absolute Deviation, MAD) zwischen den Metriken (Recall vs. 1/Ratio) und der wahren Downstream-Qualität, um zu bewerten, welche Metrik ein besserer Proxy ist.

Zentrale Beiträge

Vorschlag von 1/Ratio@k: Einführung einer Qualitätsmetrik, die richterfrei, hyperparameterfrei und ausschließlich aus Standard-ANN-Benchmark-Inputs berechenbar ist (Embeddings und Ground-Truth-Identifikatoren). Im Gegensatz zu Alternativen wie Semantic Recall oder Tolerant Recall benötigt sie keine externen LLM-Richter oder abstimmbaren Toleranzparameter.
Demonstration des Rechenaufwands: Zeigte, dass die Optimierung für Recall@k eine erhebliche Rechenstrafe gegenüber der Optimierung für 1/Ratio@k nach sich zieht.
Evidenz der Downstream-Stabilität: Lieferte empirische Belege dafür, dass die Downstream-Leistung (Klassifizierungsgenauigkeit und RAG-Antwortqualität) stabil bleibt, selbst wenn der Recall signifikant sinkt (z. B. auf 0,4), sofern die geometrische Qualitätslage (1/Ratio) hoch bleibt.
Geometrische Erklärung: Verknüpfte die Divergenz zwischen Recall und 1/Ratio mit der lokalen intrinsischen Dimensionalität (LID) und der Nachbarschaftsgröße $k$ . Mit steigender LID und $k$ steigt die Wahrscheinlichkeit, geometrisch nahe liegende, aber identifikatorisch abweichende Nachbarn abzurufen, was dazu führt, dass Recall sinkt, während 1/Ratio hoch bleibt.

Experimentelle Ergebnisse

1. Effizienz und Kosten (RQ1 & RQ2)

Durchsatz (QPS): Die Optimierung für 1/Ratio@k liefert signifikant höheren Durchsatz als die Optimierung für Recall@k. Bei einem Qualitätsschwellenwert von $T=0,95$ $T = 0, 95$ und $k=100$ $k = 100$ liegt die Beschleunigung bei den Distanzberechnungen zwischen 1,86× und 9,36× und bei der QPS zwischen 2× und 10×, abhängig vom Algorithmus und Datensatz.
- Beispiel: Beim ImageNet-Datensatz mit HNSW ist das Erreichen von 1/Ratio@100 $\ge$ 0,95 9,98× schneller als das Erreichen von Recall@100 $\ge$ 0,95.
Build-Zeit: Die Kosten für den Aufbau von Indizes für hohen Recall sind oft höher. Für HNSW auf Gist erforderte das Erreichen von Recall $\ge$ 0,90 eine 18,39× höhere Build-Zeit als das Erreichen von 1/Ratio $\ge$ 0,90.
Speicher: Die Unterschiede beim Speicherbedarf sind minimal. Der Gap liegt meist nahe bei 1,0×, da der Speicher primär durch die Vektorspeicherung und weniger durch die Parameter zur Abstimmung auf hohen Recall dominiert wird.
Algorithmen-Ranking: Das relative Ranking der Algorithmen (welcher am schnellsten/günstigsten ist) bleibt zwischen den beiden Metriken weitgehend stabil. Der Wechsel der Metrik beeinflusst die absoluten Kosten, um einen Schwellenwert zu erreichen, nicht die relative Performance der Algorithmen.

2. Geometrische Divergenz (RQ3)

Die Lücke zwischen Recall und 1/Ratio wird größer, wenn $k$ steigt und wenn die LID steigt.
In Räumen mit hoher LID sind Nachbarn nahezu äquidistant. Ein ANN-Algorithmus, der einen Vektor mit einem anderen ID, aber fast identischer Distanz zurückgibt, wird durch Recall stark bestraft, erhält aber von 1/Ratio eine hohe Punktzahl.
Recall sinkt erheblich, wenn $k$ wächst (z. B. deutlicher Abfall von $k=1$ zu $k=100$ ), während 1/Ratio relativ flach bleibt.

3. Downstream-Aufgabenqualität (RQ4)

Bildklassifizierung: Als der Recall von 1,0 auf 0,4 sank, blieb die Label Precision (LP@100) bemerkenswert stabil (sie sank z. B. bei SVHN nur von 1,0 auf ~0,94).
- MAD-Analyse: Recall hatte eine mittlere absolute Abweichung (Vorhersagefehler) von ~26 % zur wahren Qualität. Im Gegensatz dazu lag der Fehler von 1/Ratio bei < 3 % (oft < 1 %).
RAG-Aufgaben: Die Antwortqualität (gemessen durch BERTScore, semantische Ähnlichkeit und LLM-Grades) zeigte eine vernachlässigbare Degradation, selbst als der Recall auf 0,4 sank.
- Bei menschlich annotierten Benchmarks variierten die Textqualitätsmetriken um weniger als 1,2 %, obwohl der Recall um 60 % sank.
- 1/Ratio bildete diese Stabilität eng ab, während Recall fälschlicherweise einen massiven Qualitätsverlust signalisierte.
- MAD-Analyse: Für RAG betrug der Vorhersagefehler von Recall ~30 %, während der von 1/Ratio < 3 % (oft < 1 %) betrug.

Bedeutung und Behauptungen

Das Paper behauptet, dass die Abhängigkeit der Fachwelt von Recall@k zu einer unnötigen Überdimensionierung (Over-Engineering) von ANN-Systemen geführt hat. Durch die Abstimmung auf hohen Recall zahlen Praktiker einen erheblichen Rechenaufwand (Zeit, Energie, Latenz), um Ergebnisse abzurufen, die geometrisch ununterscheidbar vom Ground Truth sind, aber einen Identifikator-Matching-Test nicht bestehen.

Die Autoren kommen zu dem Schluss, dass:

1/Ratio@k ein überlegener Proxy für den tatsächlichen Downstream-Nutzen ist, da er die Stabilität der Retrieval-Qualität präzise widerspiegelt, selbst wenn der Recall niedrig ist.
Die Verwendung von 1/Ratio@k schnellere, günstigere und effizientere ANN-Deployments ermöglicht, ohne die Qualität der endgültigen Anwendung (Klassifizierung oder Generierung) zu opfern.
Konfigurationen, die derzeit aufgrund von niedrigem Recall als „unzulänglich“ verworfen werden, sind oft operativ ausreichend und können eingesetzt werden, um signifikante Effizienzgewinne zu erzielen.

Die Studie plädiert für einen Paradigmenwechsel in der ANN-Forschungsgemeinschaft: Weg von der Optimierung der Identifikator-Überlappung (Recall) hin zur Optimierung der geometrischen Nähe (1/Ratio), um die Systemabstimmung mit den tatsächlichen Anforderungen der Downstream-Machine-Learning-Aufgaben in Einklang zu bringen.