💬 NLP

CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

Cet article introduit CRINN, un nouveau paradigme qui exploite l'apprentissage par renforcement contrastif pour générer automatiquement des algorithmes de recherche de plus proches voisins approximatifs de haute performance en optimisant la vitesse d'exécution tout en maintenant la précision, atteignant des résultats de pointe sur plusieurs bancs d'essai et démontrant le potentiel des LLM pour automatiser l'optimisation algorithmique complexe.

Auteurs originaux : Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

Publié 2026-07-14

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

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 possédez une bibliothèque massive contenant des milliards de livres, et que vous deviez trouver celui qui ressemble le plus à une phrase spécifique que vous venez de taper. Dans le monde de l'informatique, cela s'appelle la « Recherche de Voisins les Plus Proches Approximatifs » (ANNS pour Approximate Nearest Neighbor Search). C'est le moteur qui propulse des technologies géniales comme les chatbots d'IA qui se souviennent de vos conversations passées ou les robots qui trouvent des images similaires. Mais voici le hic : trouver le livre parfait dans une bibliothèque de milliards d'ouvrages est lent. Si vous vérifiez chaque livre un par un, cela prendrait une éternité. C'est pourquoi les informaticiens ont construit des « raccourcis intelligents » pour trouver le bon livre rapidement, en échangeant une infime partie de la précision contre des gains de vitesse colossaux.

Pendant des années, rendre ces raccourcis plus rapides était un travail exclusivement humain. C'est comme accorder le moteur d'une voiture de course : un mécanicien expert doit écouter le moteur, deviner quelle pièce ralentit, ajuster une vis ici, changer un engrenage là, puis tester à nouveau. Cela demande des connaissances approfondies et beaucoup de patience.

Entrez en scène CRINN, un nouveau système qui pose une grande question : Pouvons-nous apprendre à une IA à accorder elle-même le moteur ?

Le mécanicien robotique doté d'un superpouvoir

CRINN est un cadre d'« apprentissage par renforcement ». Considérez-le comme un mécanicien robot qui ne se contente pas de deviner ; il apprend en jouant à un jeu. Le jeu est simple : écrire un morceau de code pour chercher dans la bibliothèque, l'exécuter, et voir à quelle vitesse il fonctionne.

La Récompense : Si le code trouve les livres rapidement, le robot obtient un score élevé.
La Leçon : Le robot compare son nouveau code à son ancien code. Il ne regarde pas seulement le score ; il regarde pourquoi l'un était plus rapide. A-t-il sauté une étape ? A-t-il mieux organisé les livres ?
La Boucle : Le robot utilise cette comparaison pour écrire une version encore plus rapide la fois suivante. Il continue ainsi, devenant plus intelligent et plus rapide à chaque essai.

L'article montre que ce mécanicien robot est incroyablement doué pour sa tâche. Testé sur six types différents de « bibliothèques » (des ensembles de données allant d'images de chiffres à des plongements de mots), CRINN a réussi à construire des systèmes de recherche qui étaient les plus rapides au monde pour trois d'entre eux (GIST-960, MNIST-784 et GloVe-25) et a partagé la première place pour deux autres (SIFT-128 et GloVe-25).

Comment il a appris à gagner

La recette secrète s'appelle l'Apprentissage par Renforcement Contrastif. Imaginez que le robot reçoive deux versions d'un fragment de code : une qui s'exécute en 1 seconde et une qui s'exécute en 2 secondes. On demande au robot d'expliquer pourquoi la première est plus rapide. Il pourrait remarquer : « Ah, la rapide vérifie trois livres à la fois, tandis que la lente en vérifie un par un. » En apprenant ces modèles, le robot commence à écrire du code qui inclut naturellement ces astuces de gain de vitesse.

Les chercheurs ne l'ont pas laissé deviner au hasard. Ils lui ont donné un objectif précis : trouver le meilleur équilibre entre vitesse et précision. Ils ont mesuré la performance en utilisant les Requêtes Par Seconde (QPS) — combien de recherches le système peut effectuer en une seconde — tout en maintenant une précision élevée (appelée « rappel » ou recall). Par exemple, sur l'ensemble de données MNIST (chiffres manuscrits), CRINN était 85,25 % plus rapide que le système précédent à un niveau de précision très élevé (0,999 de rappel). C'est un bond énorme !

La surprise du « Taille unique »

C'est ici que cela devient vraiment intéressant. Le robot a été entraîné en utilisant un seul type de bibliothèque : l'ensemble de données SIFT-128, qui utilise une méthode spécifique de mesure de distance appelée « distance Euclidienne » (comme mesurer une ligne droite sur une carte). Vous pourriez penser : « Si on entraîne un mécanicien sur une berline, il ne saura pas comment réparer une moto. »

Mais l'article a révélé que l'entraînement de CRINN sur la distance Euclidienne fonctionnait de manière surprenante sur les ensembles de données de « distance Angulaire » (comme les plongements de mots GloVe), qui sont mathématiquement différents. Cela suggère que le robot a appris des principes généraux de vitesse qui s'appliquent même lorsque les règles du jeu changent légèrement. Cependant, l'article note une limite claire : lorsqu'il a été testé sur l'ensemble de données NYTimes-256, CRINN a en réalité été 82,85 % moins performant que le meilleur système existant. Cela nous indique que si le robot est un génie, il n'est pas magique ; il éprouve toujours des difficultés avec certains types de données très différents de ce qu'il a appris.

L'amélioration étape par étape

Les chercheurs n'ont pas simplement jeté le robot face au problème global d'un coup. Ils ont décomposé le processus de recherche en trois étapes, comme pour améliorer une voiture par phases :

Construire la carte (Construction du graphe) : C'est ici que la bibliothèque est organisée. CRINN a le plus amélioré cette étape, augmentant la vitesse de 22,11 % en moyenne. Il a appris à utiliser la « recherche adaptative », ce qui signifie qu'il consacre plus d'efforts à trouver le livre uniquement quand c'est vraiment nécessaire, et des « points d'entrée multiples », permettant de commencer la recherche depuis plusieurs portes à la fois.
Parcourir la carte (Recherche) : Une fois la carte construite, il faut trouver le livre. CRINN a amélioré cette étape de 18,30 %, en utilisant des astuces comme le « traitement par lots » (vérifier des groupes de livres ensemble) et la « terminaison anticipée » (arrêter la recherche dès qu'il est sûr d'avoir trouvé la meilleure correspondance).
Polir le résultat (Raffinement) : L'étape finale pour s'assurer que la réponse est parfaite. Cela a donné un gain plus faible de 9,69 %, car il y avait moins de place pour l'amélioration à ce stade.

Ce que cela signifie

L'article soutient que CRINN prouve une idée puissante : l'IA peut automatiser des tâches complexes de niveau expert. Pendant des décennies, rendre ces algorithmes de recherche plus rapides nécessitait des experts humains dotés d'années de formation. Désormais, un système qui apprend en comparant son propre code peut le faire automatiquement.

Les auteurs précisent avec prudence que ce n'est pas un problème résolu pour chaque ensemble de données (comme l'indique le résultat de NYTimes), mais que c'est une avancée majeure. Ils suggèrent qu'à mesure que les applications d'IA comme la « Génération Augmentée par Récupération » (où l'IA utilise des connaissances externes pour répondre aux questions) deviennent plus populaires, des outils comme CRINN seront essentiels pour maintenir la rapidité de l'ensemble sans avoir besoin d'un humain pour ajuster chaque paramètre.

En résumé, CRINN est un robot qui a appris à être un maître mécanicien pour la recherche de données, prouvant qu'avec le bon entraînement, les machines peuvent non seulement écrire du code, mais aussi découvrir comment le faire fonctionner plus rapidement que les humains ne le pourraient jamais.

Résumé Technique : CRINN

Énoncé du Problème

La recherche de plus proches voisins approximatifs (ANNS - Approximate Nearest-Neighbor Search) est un composant critique pour les applications d'IA modernes, particulièrement pour la génération augmentée par récupération (RAG) et les systèmes de grands modèles de langage (LLM) basés sur des agents, qui nécessitent une récupération rapide à partir de bases de données vectorielles massives. Bien que les solutions ANNS open-source existantes (par exemple, FAISS, DiskANN, ParlayANN) s'appuient sur des noyaux robustes comme HNSW (Hierarchical Navigable Small World), leur optimisation reste un processus largement manuel. Ce processus nécessite une expertise approfondie en architecture informatique, en programmation parallèle et en propriétés algorithmiques pour identifier les goulots d'étranglement, ajuster les paramètres (tels que le degré du graphe et la largeur du faisceau de recherche) et concevoir des structures de données pour la localité de la mémoire. L'article pose comme postulat que ce raffinement manuel est laborieux et soulève la question de savoir si les LLM, augmentés par l'apprentissage par renforcement (RL), peuvent automatiser la génération et le test d'améliorations algorithmiques pour découvrir des modèles d'optimisation que les ingénieurs humains pourraient négliger.

Méthodologie

Les auteurs proposent CRINN (Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search), un cadre qui traite l'optimisation de l'ANNS comme un problème d'apprentissage par renforcement où la vitesse d'exécution sert de signal de récompense.

Cadre Fondamental

CRINN utilise un modèle de RL contrastif pour optimiser les algorithmes ANNS module par module (en ciblant spécifiquement la Construction du Graphe, la Recherche et le Raffinement au sein d'un noyau HNSW). Le processus comprend :

Prompting Contrastif : Le LLM reçoit un prompt contenant des implémentations de code précédentes couplées à leurs scores d'exécution. Le modèle est chargé d'effectuer une analyse comparative pour identifier pourquoi certaines implémentations surpassent d'autres, en distinguant les stratégies efficaces des stratégies inefficaces.
Génération Itérative : Sur la base de cette analyse, le LLM synthétise de nouvelles variantes de code.
Signal de Récompense : Le code généré est exécuté, et la récompense est calculée en fonction de la performance. Pour répondre à la difficulté de comparer les algorithmes ANNS en raison du compromis entre le nombre de requêtes par seconde (QPS) et le rappel (Recall), les auteurs emploient une stratégie d'évaluation spécifique :
- Ils font varier le paramètre de recherche $ef$ pour générer un ensemble de points (QPS, rappel).
- Ils filtrent les points dans la plage de rappel $[0,85, 0,95]$ , un « point idéal » où la plupart des algorithmes disposent de données suffisantes et où les différences de performance sont significatives.
- La récompense est définie comme l'Aire Sous la Courbe (AUC) formée par ces points filtrés, fournissant une valeur scalaire unique pour l'objectif de RL.
Algorithme d'Entraînement : Le système utilise l'Optimisation de Politique Relative de Groupe (GRPO - Group Relative Policy Optimization). Pour chaque prompt d'entrée, le modèle génère un groupe de complétions de code. Les récompenses sont normalisées au sein du groupe, et la politique est mise à jour pour maximiser la probabilité de générer un code à plus haute récompense tout en maintenant une contrainte contre l'écart trop important par rapport à une politique de référence (divergence KL).

Détails d'Implémentation

Base de Référence (Baseline) : Le cadre utilise GLASS comme point de départ initial, une bibliothèque d'ANNS basée sur les graphes, et optimise séquentiellement ses modules constitutifs.
Données d'Entraînement : Le modèle de RL est entraîné exclusivement sur le jeu de données SIFT-128-Euclidean afin de maintenir un code source unique et généralisable.
Structure de Sortie : Le LLM est contraint de produire une réponse structurée contenant une « Analyse de Performance », une « Conception d'Algorithme » et une « Implémentation de Code ».

Principales Contributions

Paradigme d'Optimisation Automatisée : CRINN introduit un nouveau paradigme où l'optimisation de l'ANNS est automatisée via des LLM augmentés par le RL, éliminant ainsi le besoin d'un réglage manuel fondé sur l'expertise.
Mécanisme d'Apprentissage Contrastif : En intégrant le code exemplaire et les métriques d'exécution directement dans le prompt, le modèle apprend à raisonner sur des motifs critiques de performance par comparaison directe plutôt que par simple essai et erreur.
Ingénierie de la Récompense : L'article répond au défi de définir une récompense scalaire pour l'ANNS en utilisant l'AUC de la courbe QPS-rappel dans une plage de rappel pratique spécifique ( $[0,85, 0,95]$ ), permettant une comparaison équitable entre les différents réglages de paramètres.
Optimisation Progressive : Le système démontre que l'optimisation séquentielle de modules distincts (Construction du Graphe, Recherche, Raffinement) produit des gains de performance cumulatifs.

Résultats Expérimentaux

Les auteurs ont évalué CRINN sur six jeux de données de référence largement utilisés : SIFT-128, GIST-960, MNIST-784, GloVe-100, GloVe-25 et NYTimes-256.

Performance : CRINN a atteint une performance de premier plan sur trois jeux de données (GIST-960-Euclidean, MNIST-784-Euclidean et GloVe-25-angular) et s'est classé ex æquo en première position sur deux autres (SIFT-128-Euclidean et GloVe-25-angular).
Gains Quantitatifs :
- Sur MNIST-784, CRINN a montré une amélioration allant jusqu'à 85,25 % du QPS à un rappel de 0,999 par rapport à la meilleure base de référence (ParlayANN).
- Sur GIST-960, il a obtenu une amélioration de 72,68 % à un rappel de 0,99.
- Sur SIFT-128 (le jeu de données d'entraînement), les améliorations allaient de +3,25 % à +25,57 % selon les niveaux de rappel.
Limites : CRINN a sous-performé la meilleure base de référence sur NYTimes-256 (un jeu de données de distance angulaire) de 82,85 % à un rappel de 0,9. Les auteurs attribuent cela au fait que le modèle a été entraîné uniquement sur des données de distance euclidienne, suggérant que les modèles d'optimisation pour la similitude angulaire peuvent différer considérablement.
Contributions des Modules : Le module de Construction du Graphe a généré les gains individuels les plus importants (moyenne de +22,11 %), suivi de la Recherche (+18,30 %) et du Raffinement (+9,69 %).

Signification et Revendications

L'article affirme que le succès de CRINN dépasse la simple optimisation spécifique des algorithmes ANNS. Il valide le fait que les LLM augmentés par l'apprentissage par renforcement peuvent fonctionner comme des outils efficaces pour automatiser des optimisations algorithmiques sophistiquées qui exigent traditionnellement des connaissances spécialisées du domaine et un raffinement manuel laborieux.

Les auteurs soutiennent qu'à mesure que la demande pour la recherche vectorielle efficace croît avec la prolifération des applications RAG et des applications de LLM basées sur des agents, des cadres comme CRINN deviendront de plus en plus précieux pour maintenir des performances compétitives face à l'évolution des architectures matérielles et des exigences applicatives. Le travail démontre que des systèmes automatisés peuvent non seulement égaler, mais dans certains contextes, dépasser les performances de solutions conçues par l'homme à l'état de l'art.