🤖 AI

ANN Search: Recall What Matters

Cet article soutient que la métrique standard Recall@k pour la recherche de plus proches voisins approximatifs (ANN) est un indicateur imparfait de l'utilité réelle car elle privilégie le chevauchement d'ensembles au détriment de la qualité des résultats, proposant ainsi l'inverse du ratio d'approximation (1/Ratio@k) comme une métrique plus précise, efficace et déployable qui corrèle mieux avec la performance des tâches en aval tout en réduisant la surcharge de calcul inutile.

Auteurs originaux : Dimitris Dimitropoulos, Nikos Mamoulis

Publié 2026-06-04

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Dimitris Dimitropoulos, Nikos Mamoulis

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous cherchiez les trois meilleures pommes dans un verger immense pour faire une tarte. Vous avez un robot assistant super rapide (l'algorithme ANN) capable de scanner le verger en une fraction de seconde.

Pendant des années, la communauté a jugé ce robot selon une règle stricte : a-t-il choisi exactement les trois mêmes pommes qu'un expert humain aurait choisies ? Cette règle est appelée Rappel (Recall). Si l'humain a choisi les pommes A, B et C, et que le robot a choisi A, B et D, le robot reçoit un mauvais score, même si la pomme D est tout aussi sucrée et parfaite pour la tarte que la pomme C.

Les auteurs de cet article soutiennent que cette règle est erronée. Ils disent : « Arrêtez de vous obséder pour l'identifiant exact de la pomme ; goûtez simplement la pomme. »

Voici la décomposition de leur argument utilisant des analogies simples :

1. Le Problème : L'obsession de l'étiquette de nom

Dans le monde de l'IA, les données sont souvent représentées comme des points dans un espace multidimensionnel (comme un immense nuage de points invisible). Lorsque vous demandez à l'IA de trouver les voisins les plus « proches » (les meilleures pommes), elle renvoie une liste.

L'ancienne méthode (Rappel) : Le système vérifie si le robot a renvoyé les identifiants exacts de la liste parfaite.
La réalité : Dans les espaces à haute dimension (comme les modèles d'IA complexes), il existe souvent des milliers de pommes qui sont presque identiques en termes de goût et de distance. Le robot peut choisir la pomme D au lieu de la pomme C. Elles sont pratiquement jumelles. Mais parce que l'identifiant est différent, le score de « Rappel » s'effondre, faisant paraître le robot médiocre.

Les auteurs disent que c'est comme un professeur qui échouerait un élève ayant écrit la bonne réponse « 4 » parce que la clé de correction du professeur indiquait « 4,00001 ». L'élève a raison, mais le système de notation est trop rigide.

2. La Nouvelle Solution : Le « Test de Goût » (1/Ratio)

Les auteurs proposent une nouvelle métrique appelée 1/Ratio. Au lieu de vérifier si le robot a choisi les mêmes pommes exactes, elle mesure à quel point les pommes sont proches de celles qui sont parfaites.

L'analogie : Imaginez que les pommes parfaites soient posées sur une table.
- Le Rappel demande : « Avez-vous choisi exactement les pommes sur la table ? »
- Le 1/Ratio demande : « À quelle distance de la table avez-vous dû marcher pour trouver vos pommes ? »

Si le robot choisit une pomme située à 1 millimètre de l'endroit parfait, le 1/Ratio lui donne un score presque parfait. S'il choisit une pomme située à 10 kilomètres, le score chute. Cette métrique ignore l'« étiquette de nom » et se concentre sur la qualité réelle (la distance).

3. La Grande Découverte : On peut aller beaucoup plus vite

L'article a testé cinq types différents de robots assistants (algorithmes) à travers six types de vergers (jeux de données). Ils ont fait une énorme surprise :

Le Coût de la Perfection : Pour obtenir un score de Rappel élevé (choisir exactement les mêmes identifiants), les robots devaient travailler incroyablement dur, en vérifiant des millions de pommes supplémentaires. Cela les ralentissait considérablement.
L'Efficacité du « Assez Bon » : Lorsque les robots étaient autorisés à optimiser pour le 1/Ratio (choisir des pommes qui sont très proches des parfaites, même si l'identifiant est différent), ils pouvaient travailler 3 à 10 fois plus vite.

La Métaphore : C'est comme essayer de trouver une personne spécifique dans une foule.

Le Rappel exige que vous trouviez la personne exacte portant le chapeau spécifique que vous avez décrit. Vous devez arrêter et vérifier chaque visage.
Le 1/Ratio vous permet de saisir la personne debout juste à côté d'elle qui ressemble à 99,9 % à la description. Vous la saisissez instantanément. Le résultat est le même pour votre objectif, mais vous avez économisé des heures de temps.

4. Est-ce que le « Assez Bon » fonctionne vraiment ?

Les sceptiques pourraient demander : « Si nous arrêtons de choisir les pommes exactes, est-ce que notre tarte aura un mauvais goût ? »

Les auteurs ont testé cela dans deux scénarios réels :

Classification d'images (Tri de photos) : Ils ont essayé de trier des photos de chats et de chiens. Même lorsque le « Rappel » du robot était bas (il a manqué les « meilleures » photos exactes), le résultat final du tri des photos restait presque parfaitement précis. Les « erreurs » n'avaient pas d'importance.
RAG (Chatbots utilisant la recherche) : Ils ont testé un chatbot qui répond à des questions en cherant dans une base de données. Même lorsque le moteur de recherche a manqué les documents « parfaits » exacts (faible Rappel), le chatbot donnait toujours des réponses excellentes. La qualité de la réponse n'a pas chuté.

La Conclusion : Les mauvais scores de l'ancienne métrique étaient un mensonge. Les robots faisaient en réalité un excellent travail ; ils ne choisissaient simplement pas les mêmes identifiants exacts.

5. Pourquoi cela importe

L'article conclut que la communauté de l'IA gaspille des quantités massives de puissance de calcul pour tenter d'atteindre un score « parfait » (le Rappel) qui n'améliore en réalité pas le résultat final.

L'ancienne méthode : « Nous avons besoin de 100 % de Rappel ! » -> Résultat : Lent, coûteux et surdimensionné.
La nouvelle méthode : « Nous avons besoin d'un 1/Ratio élevé ! » -> Résultat : Beaucoup plus rapide, moins cher, et le résultat final (la tarte, le tri de photos, la réponse du chatbot) est tout aussi bon.

En bref : Ne vous souciez plus du nom exact du voisin que vous avez trouvé. S'il habite juste à côté du voisin parfait, il est assez bon. Et en acceptant cela, nous pouvons rendre les systèmes d'IA beaucoup plus rapides et moins coûteux.

Résumé Technique : Recherche ANN : Rappeler ce qui compte

Énoncé du Problème

La recherche de plus proches voisins approximatifs (ANN - Approximate Nearest Neighbor) est une primitive fondamentale dans la recherche d'information moderne et l'apprentissage automatique, particulièrement pour des tâches telles que la classification et la génération augmentée par récupération (RAG). La communauté s'est standardisée sur le Recall@k (la fraction des $k$ -plus proches voisins exacts récupérés) comme métrique principale pour évaluer et ajuster les algorithmes ANN. Les chercheurs optimisent le débit (requêtes par seconde, QPS) à des seuils de Recall fixes.

Les auteurs soutiennent que cette convention est en décalage avec l'utilité réelle des systèmes ANN. Dans les espaces de haute dimension (communs dans les plongements vectoriels modernes), les distances vers les voisins successifs se concentrent, menant à de nombreux candidats « quasi-équidistants ». Un algorithme ANN peut récupérer des points qui sont géométriquement aussi proches de la requête que les vrais voisins, mais qui portent des identifiants différents. Sous la métrique Recall@k, ces résultats géométriquement précis sont pénalisés comme des échecs, forçant les systèmes à supporter une surcharge de calcul inutile pour atteindre un chevauchement d'identifiants élevé. L'article postule que le Recall@k surestime la difficulté de la tâche et le coût de l'approximation, ce qui peut conduire à des configurations de systèmes sous-optimales.

Méthodologie

L'article propose de remplacer le Recall@k par le 1/Ratio@k, l'inverse du ratio d'approximation. Contrairement au Recall, qui compte les correspondances d'identifiants, le 1/Ratio@k mesure la qualité des résultats récupérés en se basant sur les distances des voisins retournés par rapport aux $k$ -plus proches voisins réels.

Définitions Clés :

Recall@k : $\frac{| \tilde{N}_k(q) \cap N_k(q) |}{k}$ , où $\tilde{N}_k$ est l'ensemble récupéré et $N_k$ l'ensemble réel.
Ratio@k : La moyenne des ratios de distance par position : $\frac{1}{k} \sum_{i=1}^k \frac{\tilde{d}_i(q)}{d_i(q)}$ , où $\tilde{d}_i$ et $d_i$ sont respectivement les distances du $i$ -ème voisin retourné et du $i$ -ème voisin réel.
1/Ratio@k : L'inverse du ratio ci-dessus, variant de 0 à 1 (1 indiquant une récupération parfaite).

Configuration Expérimentale :
Les auteurs ont testé cinq algorithmes ANN de pointe à travers divers ensembles de données présentant des dimensions intrinsèques (LID) variables :

Annoy (basé sur les arbres)
SuCo (basé sur les collisions)
HNSW (basé sur les graphes, standard de l'industrie)
RaBitQ (basé sur la quantification)
SymphonyQG (hybride Graphe-Quantification)

L'évaluation a couvert six ensembles de données (Gist, SimpleWiki, ImageNet, AGNews, MNIST, Fashion-MNIST) et s'est étendue à des tâches en aval comme la classification d'images (MNIST, Fashion-MNIST, CIFAR-10, SVHN) et le RAG (SciFact, NFCorpus, HotpotQA, MS-MARCO, PubMedQA).

Stratégie d'Évaluation :

Analyse de l'Efficacité : Mesure du coût computationnel (QPS, calculs de distance, temps de construction, mémoire) requis pour atteindre des seuils de qualité spécifiques ( $T \in \{0,90, 0,95, 0,99\}$ ) sous les deux métriques.
Validation en Aval : Utilisation d'un contrôle de recall synthétique pour dégrader artificiellement les niveaux de recall ( $r \in [0,4, 1,0]$ ) tout en maintenant la qualité géométrique. Ils ont mesuré la performance des tâches en aval (Précision de l'étiquette pour la classification ; BERTScore, Similitude Sémantique, et scores évalués par LLM pour le RAG) afin de déterminer si un faible Recall dégrade réellement l'utilité.
Comparaison de Métriques : Calcul de la Déviation Absolue Moyenne (MAD) entre les métriques (Recall vs 1/Ratio) et la véritable qualité en aval pour évaluer laquelle est le meilleur indicateur.

Contributions Clés

Proposition du 1/Ratio@k : Introduction d'une métrique de qualité qui est sans juge, sans hyperparamètre et calculable uniquement à partir des entrées standards des benchmarks ANN (plongements et identifiants de vérité terrain). Contrairement aux alternatives comme le Semantic Recall ou le Tolerant Recall, elle ne nécessite ni juges LLM externes ni paramètres de tolérance ajustables.
Démonstration de la Surcharge Computationnelle : Montre que l'optimisation pour le Recall@k impose une pénalité de calcul substantielle par rapport à l'optimisation pour le 1/Ratio@k.
Preuve de Stabilité en Aval : Fournit des preuves empiriques que la performance des tâches en aval (précision de classification et qualité de réponse RAG) reste stable même lorsque le Recall diminue significativement (ex: à 0,4), à condition que la qualité géométrique (1/Ratio) reste élevée.
Explication Géométrique : Lie la divergence entre le Recall et le 1/Ratio à la Dimension Intrinsèque Locale (LID) et à la taille du voisinage $k$ . Lorsque la LID et $k$ augmentent, la probabilité de récupérer des voisins géométriquement proches mais avec des identifiants différents augmente, provoquant la dégradation du Recall tandis que le 1/Ratio reste élevé.

Résultats Expérimentaux

1. Efficacité et Coût (RQ1 & RQ2)

Débit (QPS) : L'optimisation pour le 1/Ratio@k produit un débit nettement plus élevé que l'optimisation pour le Recall@k. À un seuil de qualité $T=0,95$ $T = 0, 95$ et $k=100$ $k = 100$ , l'accélération varie de 1,86× à 9,36× pour les calculs de distance et de 2× à 10× pour le QPS selon l'algorithme et le jeu de données.
- Exemple : Sur le jeu de données ImageNet avec HNSW, atteindre 1/Ratio@100 $\ge$ 0,95 est 9,98× plus rapide que d'atteindre Recall@100 $\ge$ 0,95.
Temps de Construction : Le coût pour construire des index pour un Recall élevé est souvent plus élevé. Pour HNSW sur Gist, atteindre un Recall $\ge$ 0,90 a nécessité 18,39× plus de temps de construction que pour atteindre un 1/Ratio $\ge$ 0,90.
Mémoire : Les différences d'empreinte mémoire sont minimes. L'écart est généralement proche de 1,0×, car la mémoire est dominée par le stockage des vecteurs plutôt que par les paramètres utilisés pour ajuster le Recall élevé.
Classement des Algorithmes : Le classement relatif des algorithmes (lequel est le plus rapide/moins cher) reste largement stable entre les deux métriques. Le changement de métrique affecte le coût absolu pour atteindre un seuil, non la performance relative des algorithmes.

2. Divergence Géométrique (RQ3)

L'écart entre le Recall et le 1/Ratio s'élargit à mesure que $k$ augmente et que la LID augmente.
Dans les espaces à haute LID, les voisins sont presque équidistants. Un algorithme ANN retournant un vecteur avec un ID différent mais une distance quasi identique est lourdement pénalisé par le Recall, mais reçoit un score élevé par le 1/Ratio.
Le Recall se dégrade considérablement à mesure que $k$ croît (ex: chutant fortement de $k=1$ à $k=100$ ), tandis que le 1/Ratio reste relativement plat.

3. Qualité des Tâches en Aval (RQ4)

Classification d'Images : À mesure que le Recall chutait de 1,0 à 0,4, la Précision de l'Étiquette (LP@100) est restée remarquablement stable (passant seulement de 1,0 à ~0,94 sur SVHN).
- Analyse MAD : Le Recall présentait une Déviation Absolue Moyenne (erreur de prédiction) d'environ 26 % par rapport à la qualité réelle. En revanche, le 1/Ratio présentait une erreur de < 3 % (souvent < 1 %).
Tâches RAG : La qualité des réponses (mesurée par BERTScore, la similitude sémantique et les notes LLM) a montré une dégradation négligeable malgré la chute du Recall à 0,4.
- Sur les benchmarks annotés par des humains, les métriques de qualité textuelle ont varié de moins de 1,2 % malgré une baisse de 60 % du Recall.
- Le 1/Ratio a suivi de près cette stabilité, tandis que le Recall signalait faussement une chute massive de la qualité.
- Analyse MAD : Pour le RAG, l'erreur de prédiction du Recall était d'environ 30 %, tandis que celle du 1/Ratio était de < 3 % (souvent < 1 %).

Signification et Revendications

L'article affirme que la dépendance de la communauté vis-à-vis du Recall@k a conduit à un sur-dimensionnement inutile des systèmes ANN. En ajustant pour un Recall élevé, les praticiens encourrent des coûts de calcul substantiels (temps, énergie, latence) pour récupérer des résultats géométriquement indiscernables de la vérité terrain mais échouant à un test de correspondance d'identifiants.

Les auteurs concluent que :

Le 1/Ratio@k est un meilleur indicateur de l'utilité réelle en aval, reflétant avec précision la stabilité de la qualité de la récupération même lorsque le Recall est faible.
L'adoption du 1/Ratio@k permet des déploiements ANN plus rapides, moins chers et plus efficaces sans sacrifier la qualité de l'application finale (classification ou génération).
Les configurations actuellement rejetées comme « inadéquates » en raison d'un faible Recall sont souvent opérationnellement suffisantes et peuvent être déployées pour obtenir des gains d'efficacité significatifs.

L'étude préconise un changement de paradigme d'évaluation pour la communauté de la recherche en ANN : passer de l'optimisation du chevauchement d'identifiants (Recall) à l'optimisation de la proximité géométrique (1/Ratio), alignant ainsi l'ajustement des systèmes sur les véritables exigences des tâches d'apprentissage automatique en aval.