Recherche vectorielle : ANN

Un embedding place un texte comme un point dans un espace à plusieurs centaines de dimensions, arrangé pour que la proximité géométrique traduise la proximité de sens. Chercher les documents pertinents pour une requête revient alors à une question de géométrie : quels vecteurs de la base sont les plus proches du vecteur de la requête ? La réponse exacte est triviale à écrire — et c'est précisément là qu'est le problème.

Comparer la requête à chaque vecteur stocké fonctionne parfaitement jusqu'à quelques dizaines de milliers d'entrées, puis s'effondre. Les index ANN (approximate nearest neighbor, recherche approximative de voisins) contournent ce mur en acceptant de rater, de temps en temps, un vrai voisin — en échange d'un gain de vitesse de plusieurs ordres de grandeur.

La recherche exacte : simple, et vite intenable

Une recherche exacte (brute force, ou flat) calcule la similarité entre le vecteur requête et les N vecteurs de la base, trie, renvoie les k meilleurs. Le coût est linéaire : O(N × d) multiplications-additions par requête, où d est la dimension.

Avec 10 000 vecteurs en dimension 1024, c'est ~10 millions d'opérations : imperceptible. Avec 50 millions de vecteurs — un corpus documentaire d'entreprise moyen — c'est ~50 milliards d'opérations par requête, à multiplier par le nombre de requêtes par seconde. On passe de la milliseconde à la seconde, et la facture mémoire suit. La recherche exacte ne devient pas fausse à l'échelle : elle devient trop lente pour être servie en ligne.

L'idée de l'ANN : accepter de rater un peu

Un index approximatif ne promet plus « les k plus proches voisins » mais « k voisins probablement parmi les plus proches ». La qualité se mesure par le rappel (recall@k) : la fraction des vrais k voisins effectivement retrouvés. Un rappel de 0,95 signifie qu'en moyenne on récupère 19 des 20 meilleurs résultats — souvent invisible pour l'utilisateur final, pour un index 100 à 1000 fois plus rapide.

Tous les index ANN exposent un curseur qui échange rappel contre latence. Le régler, c'est décider combien d'erreur silencieuse le cas d'usage tolère. Deux familles dominent.

IVF : partitionner l'espace

L'Inverted File Index découpe l'espace en nlist régions, chacune représentée par un centroïde calculé par k-means à la construction. Chaque vecteur de la base est rangé dans la région de son centroïde le plus proche. À la requête, on ne compare qu'aux vecteurs des nprobe régions dont le centroïde est le plus proche de la requête — pas à toute la base.

Le compromis est explicite : nprobe petit = peu de régions visitées = très rapide mais rappel plus faible ; nprobe grand = on se rapproche de la recherche exacte. Le mode de défaillance est structurel : si un vrai voisin se trouve juste de l'autre côté d'une frontière de région, dans une cellule non explorée, il est manqué. IVF est économe en mémoire et se construit vite ; c'est un bon défaut pour des bases qui tiennent en RAM sans être gigantesques.

HNSW : un graphe navigable multi-niveaux

HNSW (Hierarchical Navigable Small World) ne partitionne pas : il construit un graphe où chaque vecteur est relié à ses voisins proches, avec plusieurs niveaux superposés — une poignée de nœuds très connectés au sommet, tous les nœuds à la base, comme une skip list en 2D. Une recherche part d'un nœud d'entrée au niveau haut, suit à chaque étape l'arête vers le voisin le plus proche de la requête, puis descend d'un niveau et recommence. On atteint le voisinage en un nombre de sauts logarithmique.

Paramètres clés : M (nombre de liens par nœud), efConstruction (effort à la construction) et efSearch (taille de la liste de candidats explorés à la requête — le curseur rappel/latence). HNSW offre le meilleur rappel à latence donnée, au prix d'un graphe volumineux à garder en mémoire et d'insertions plus coûteuses que dans un IVF.

Compresser les vecteurs : la quantification de produit

À très grande échelle, ce sont les vecteurs eux-mêmes qui saturent la RAM : 50 millions de vecteurs float32 en dimension 1024, c'est ~200 Go. La quantification de produit découpe chaque vecteur en sous-blocs, remplace chaque sous-bloc par l'indice du centroïde le plus proche dans un petit codebook appris, et ne stocke que ces indices — d'un facteur 10 à 50 de compression. Les distances sont alors estimées sur les codes, sans décompresser. C'est la même intuition que la quantification des poids d'un modèle : troquer de la précision numérique contre de la place mémoire et de la vitesse, en pariant que l'erreur introduite reste sous le seuil qui changerait le résultat.

Quand la recherche exacte suffit

L'ANN est une réponse à un problème d'échelle. En dessous de ~100 000 vecteurs, ou quand un pré-filtrage par métadonnées réduit déjà la recherche à un petit sous-ensemble, la recherche exacte est plus simple, sans paramètre à régler, et sans rappel à surveiller. Un cache sémantique de quelques milliers d'entrées se compare parfaitement en brute force. De même, si la question est « faut-il chercher dans une base de connaissances ou appeler un outil qui a la réponse exacte », l'arbitrage se joue d'abord côté RAG contre tool use, pas côté type d'index.

La règle de décision tient en une phrase : on passe à l'ANN quand la recherche exacte ne tient plus le budget de latence — et on choisit alors le rappel qu'on est prêt à sacrifier, en connaissance de cause.

FAQ

Que signifie « approximatif » dans recherche approximative de voisins ?

L'index peut renvoyer un résultat qui n'est pas exactement dans les k plus proches voisins. La proportion de vrais voisins retrouvés s'appelle le rappel ; on l'échange contre de la vitesse via un paramètre (nprobe pour IVF, efSearch pour HNSW).

IVF ou HNSW ?

HNSW donne le meilleur rappel à latence donnée mais consomme beaucoup de mémoire et supporte mal les mises à jour fréquentes. IVF est plus léger, se construit vite et se met à jour facilement, au prix d'un rappel un peu inférieur à effort égal.

À partir de quelle taille faut-il un index ANN ?

En pratique autour de 100 000 vecteurs, ou plus tôt si le débit de requêtes est élevé. En dessous, une recherche exacte en mémoire répond en quelques millisecondes sans aucun réglage.