Semantic Recall for Vector Search

1. Problématique

L'article aborde les limites des métriques d'évaluation actuelles pour la recherche de voisins les plus proches approximatifs (ANNS - Approximate Nearest Neighbor Search) dans les systèmes de recherche sémantique basés sur des embeddings.

• La limite du Rappel Traditionnel : Le rappel traditionnel mesure la proportion de voisins "vrais" (identifiés par une recherche exacte, brute-force) retrouvés par un algorithme approximatif. Cependant, cette métrique suppose que la proximité mathématique dans l'espace vectoriel équivaut à la pertinence sémantique.
• Le problème du "Bruit Mathématique" : Dans les espaces vectoriels de haute dimension, il existe souvent des points mathématiquement proches d'une requête mais sémantiquement non pertinents. Le rappel traditionnel pénalise les algorithmes s'ils ne récupèrent pas ces points "bruit", même si les résultats pertinents sont bien présents.
• Scénario critique : Les auteurs observent que de nombreuses requêtes dans les jeux de données d'embeddings ont très peu de résultats pertinents parmi leurs voisins les plus proches. Dans ces cas, le rappel traditionnel est trompeur et décourage l'optimisation de l'efficacité (coût) car il force les systèmes à chercher à tout prix des voisins mathématiquement proches mais inutiles.
• Limites des Ground Truth curatés : L'utilisation de ground truth manuellement annotés (où l'on juge la pertinence sans se soucier de la distance vectorielle) est problématique car elle peut pénaliser injustement les algorithmes ANNS pour des limitations inhérentes au modèle d'embedding lui-même (si le modèle ne place pas un objet pertinent près de la requête, aucun ANNS ne pourra le trouver).

2. Méthodologie et Contributions Clés

Les auteurs introduisent deux nouvelles métriques pour évaluer la qualité de la recherche :

A. Rappel Sémantique (Semantic Recall - srecall)

C'est la métrique principale proposée.

• Définition : Elle mesure la fraction des voisins sémantiques (un sous-ensemble du ground truth mathématique jugé pertinent par un juge externe) qui sont effectivement récupérés par l'algorithme ANNS.
• Fonctionnement :
  1. Calcul du ground truth par recherche exacte (top-$k$).
  2. Identification des "voisins sémantiques" (SN) parmi ce ground truth via un juge (humain ou LLM).
  3. Calcul du rappel uniquement sur ces SN : $srecall = \frac{|R \cap SN|}{|SN|}$.
• Avantage : Elle ne pénalise pas l'absence de voisins mathématiquement proches mais sémantiquement non pertinents. Elle se concentre uniquement sur la récupération des résultats qui comptent pour l'utilisateur final.

B. Rappel Tolérant (Tolerant Recall - trecall)

Proposée comme une métrique proxy lorsque l'identification des voisins sémantiques est impossible (ex: absence des données brutes, seulement les embeddings).

• Définition : Elle permet de remplacer un voisin du ground truth par un résultat récupéré si leurs scores de similarité sont proches (dans une marge de tolérance $x\%$).
• Logique : Si un document non pertinent a un score très proche d'un document pertinent, le système peut être considéré comme performant même s'il a récupéré le premier au lieu du second, car la différence est minime et souvent due au bruit de quantification.
• Robustesse : Cette métrique est moins sensible aux petites perturbations de distance (comme celles induites par la quantification 8-bit) et aux mises à jour fréquentes des bases de données.

C. Méthodologie d'Évaluation

• Jugement par LLM : Les auteurs utilisent des modèles de langage (Gemini 2.5, Claude Haiku) pour étiqueter les voisins du ground truth comme "Pertinents" ou "Non pertinents", validant ainsi que cette approche est plus efficace que l'annotation manuelle de masses de données.
• Expérimentations : Évaluations sur les corpus MSMARCO (anglais) et MIRACL (thaï), utilisant différents modèles d'embedding (Gemini, Cohere) et index ANNS (ScaNN, FAISS IVF).

3. Résultats Expérimentaux

• Distribution des voisins sémantiques : L'analyse montre une distribution bimodale : 40 % des requêtes ont très peu de voisins sémantiques (0-15), tandis que d'autres en ont beaucoup. Pour les requêtes avec peu de SN, le rappel traditionnel est significativement plus bas que le rappel sémantique (ex: 0.762 vs 0.903 sur MSMARCO pour les requêtes avec <20 SN).
• Impact de la quantification : Les erreurs de quantification (8-bit) réorganisent souvent les voisins non pertinents (qui ont des scores très proches). Le rappel traditionnel chute à cause de cela, tandis que le rappel sémantique et tolérant restent stables car ils ignorent ce bruit.
• Optimisation Coût-Qualité (Trade-off) :
  • En ajustant les hyperparamètres de ScaNN pour maximiser le rappel sémantique ou tolérant plutôt que le rappel traditionnel, les auteurs obtiennent des configurations strictement meilleures.
  • Pour un niveau de rappel cible équivalent, l'optimisation pour le rappel tolérant réduit le coût de calcul (bytes lus, opérations CPU) de 5 % à 35 % selon les jeux de données (BigANN, GloVe, MSMARCO).
  • Cela s'explique par le fait que les algorithmes n'ont plus besoin de dépenser des ressources coûteuses pour récupérer des voisins non pertinents mais mathématiquement proches.

4. Signification et Implications

• Alignement avec l'objectif réel : Ces métriques réalignent l'évaluation des systèmes de recherche sur l'objectif final : récupérer des réponses pertinentes, et non pas simplement minimiser l'erreur mathématique.
• Efficacité opérationnelle : En évitant d'optimiser pour le "bruit", les ingénieurs peuvent concevoir des systèmes plus rapides et moins coûteux sans dégrader l'expérience utilisateur.
• Adoption pratique : Le rappel tolérant offre une solution intermédiaire pratique pour les pipelines existants où l'annotation sémantique est impossible, tout en restant robuste aux mises à jour de données.
• Limites : Le rappel sémantique nécessite l'accès aux objets bruts pour le jugement et dépend de la qualité du juge (LLM). Cependant, juger uniquement le top-$k$ du ground truth est beaucoup plus faisable que l'annotation complète d'un dataset.

Conclusion : L'article démontre que le rappel traditionnel est une métrique obsolète pour la recherche sémantique moderne car elle pénalise injustement les algorithmes pour des limitations inhérentes à la géométrie des embeddings. Le Rappel Sémantique et le Rappel Tolérant offrent des indicateurs de qualité plus fidèles, permettant des compromis coût-performance bien supérieurs dans la conception d'algorithmes ANNS.