Le paysage des index ANN

Au chapitre précédent, HNSW nous a offert un petit miracle : retrouver un plus proche voisin en de l’ordre de $\log n$ sauts, au lieu de balayer les $n$ vecteurs un par un. On a même refermé le chapitre sur un aveu : c’est superbe, mais ce n’est ni gratuit ni unique. La hiérarchie de graphes dévore la mémoire, la mettre à jour ou y filtrer des résultats est délicat, et surtout, d’autres façons d’éviter le balayage complet existent, qui font des compromis tout différents.

Ce chapitre prend de la hauteur. Plutôt que de plonger dans un nouvel algorithme, on va dresser la carte de tous ses cousins, ranger HNSW à sa place, et se donner une grille de lecture pour choisir. Une seule question nous guide, et elle est inconfortable : si aucun index ne peut être à la fois exact, rapide et léger, lequel sacrifie quoi, et comment décider ?

Trois richesses, et la loi qui interdit de les cumuler

Quand on indexe des millions de vecteurs, on convoite trois choses à la fois.

Le rappel : retrouver vraiment les bons voisins, sans en manquer. C’est la qualité de la réponse, exactement la mesure qu’on a posée au chapitre 2 en comparant un index à l’oracle exhaustif.

La latence : répondre vite, en touchant le moins de vecteurs possible. Une recherche qui compare la requête à toute la base est lente ; une recherche qui n’en touche qu’une poignée est rapide.

La mémoire : loger l’index dans la RAM disponible. Un vecteur d’embedding de dimension 1536 en simple précision pèse déjà 6 kilo-octets ; multiplié par cent millions de documents, on parle de centaines de giga-octets.

Voici la loi cruelle de ce domaine : on ne maximise jamais ces trois richesses ensemble. C’est un triangle dont on ne peut occuper qu’un côté à la fois. Gagner de la vitesse, c’est renoncer à toucher tous les vecteurs, donc risquer d’en manquer, ou bien payer plus de mémoire pour des raccourcis. Économiser la mémoire, c’est compresser, donc perdre en précision. Chaque famille d’index est, au fond, un choix assumé sur quel sommet du triangle on accepte de perdre.

Deux questions, deux axes orthogonaux

Pour ne pas se perdre dans la zoologie des index, une grille toute simple suffit. Tout index ANN répond, à sa manière, à deux questions indépendantes.

Première question : comment éviter de tout scanner ? Trois réponses possibles. Ne rien faire de spécial et tout parcourir (l’index plat). Découper l’espace en cellules et ne visiter que les plus prometteuses (le partitionnement). Relier les vecteurs par un graphe et y naviguer de proche en proche (l’approche de HNSW, vue au chapitre précédent).

Deuxième question : comment stocker et comparer les vecteurs ? Deux réponses. Les garder en pleine précision, exacts mais lourds. Ou les compresser en codes minuscules, légers mais approximatifs.

Ces deux axes sont orthogonaux : on peut combiner n’importe quelle réponse de la première avec n’importe quelle réponse de la seconde. C’est précisément ce qui explique la prolifération des index réels, qui ne sont souvent que des assemblages de ces deux briques.

Faisons maintenant le tour des quatre familles repères, une par case marquante de cette grille.

Flat : l’exact, le lent, l’oracle

L’index plat ne fait rien pour éviter le scan : il compare la requête à tous les vecteurs, en pleine précision. C’est la recherche exhaustive du chapitre 2. Son rappel est parfait, par construction : il ne peut rien manquer. Mais il touche les $n$ vecteurs à chaque requête, et les stocke tous en clair.

$$\text{cout} = O(n \times d) \qquad \text{rappel} = 1$$

Cette ligne se lit : le coût grandit comme le produit du nombre de vecteurs par leur dimension, et le rappel vaut exactement un. C’est le pire des mondes pour la vitesse et la mémoire, le meilleur pour la qualité. D’où son vrai rôle : on le garde comme oracle, la référence de vérité contre laquelle on mesure le rappel de tous les autres.

IVF : partitionner l’espace en quartiers

La première vraie idée pour aller plus vite : ne pas chercher partout. On découpe l’espace en cellules, comme une ville en quartiers, et on range chaque vecteur dans le quartier de son centre le plus proche. Ce découpage se calcule une fois, par un algorithme de regroupement (le k-means) qui place les centres là où les points s’agglutinent.

À la recherche, on ne compare d’abord la requête qu’aux centres des quartiers, peu nombreux. On choisit les quelques quartiers les plus proches, et on ne scanne que leurs habitants. Ce nombre de quartiers visités s’appelle $\mathit{nprobe}$. C’est l’ IVF IVF (fichier inversé) Inverted File. Index qui partitionne l'espace en cellules, calculées par un k-means, et range chaque vecteur dans la cellule de son centroïde le plus proche. À la recherche, on ne scanne que les nprobe cellules les plus proches de la requête, pas toute la base. IVF gagne de la latence sans réduire la mémoire, car les vecteurs restent stockés en clair. Le nombre nprobe règle le compromis entre vitesse et rappel. , pour Inverted File, le fichier inversé.

Le compromis saute aux yeux. Avec un petit $\mathit{nprobe}$, on touche peu de vecteurs, donc on répond vite, mais on risque de rater un voisin tapi dans un quartier qu’on n’a pas visité : le rappel baisse. En montant $\mathit{nprobe}$, on visite plus de quartiers, le rappel remonte, jusqu’à tout visiter et redevenir exact. IVF achète donc de la vitesse avec un peu de rappel. Mais remarque ce qu’il ne touche pas : la mémoire. Les vecteurs restent stockés en clair, exactement comme dans l’index plat. IVF gagne la latence, pas la RAM.

PQ : compresser pour faire tenir l’éléphant

L’autre grande idée attaque l’axe orthogonal : la mémoire. Et si, au lieu de stocker chaque vecteur en entier, on le résumait par quelques octets ?

La quantification produit Quantification produit Product Quantization (PQ). Technique de compression des vecteurs : on découpe chaque vecteur en plusieurs tranches, et dans chaque tranche on remplace le sous-vecteur par l'indice du centroïde le plus proche d'un petit dictionnaire appris (un codebook). Un vecteur devient ainsi une poignée de codes, souvent un octet chacun, au lieu de centaines de réels. La quantification produit gagne énormément de mémoire, au prix d'un rappel réduit, car les distances ne sont plus qu'estimées. procède ainsi. On découpe chaque vecteur en plusieurs tranches. Pour chaque tranche, on apprend d’avance un petit dictionnaire de morceaux types (un codebook), encore par k-means. Un vecteur n’est alors plus qu’une suite d’indices : pour chaque tranche, le numéro du morceau type le plus ressemblant. Là où un vecteur de dimension 1536 pesait 6 kilo-octets, ses huit à seize codes tiennent dans une poignée d’octets. On divise la mémoire par cent ou plus.

Le prix se lit dans le mot quantification : on a remplacé chaque tranche par une approximation, donc les distances calculées ne sont plus qu’estimées. Le rappel baisse. Et surtout, attention au piège : la quantification produit, seule, ne fait pas gagner de vitesse. On scanne toujours les $n$ codes, un par un. Chaque comparaison est juste devenue très bon marché. PQ gagne la mémoire, pas la latence.

Voir le triangle des compromis en direct

Le composant ci-dessous construit un vrai jeu de vecteurs groupés, puis y mesure pour de bon les quatre familles : leur rappel face à l’oracle exact, le nombre de vecteurs qu’elles comparent (le proxy honnête de la latence) et la mémoire de leur index. Chaque famille est un point dans le plan rappel-latence, et la taille de sa bulle dit sa mémoire. Tourne les molettes et regarde les points glisser le long de leurs compromis, sans jamais qu’aucun n’atteigne le coin idéal en haut à droite avec une toute petite bulle.

IVF : quartiers visités (nprobe) 3HNSW : largeur de faisceau (ef) 12PQ : tranches par vecteur 8

Taille de la bulle : mémoire de l'index

	rappel	comparaisons	mémoire
Flat (exact)	100.0 %	600	75.0 ko
IVF (partition)	100.0 %	110	80.3 ko
HNSW (graphe)	100.0 %	79	118.3 ko
PQ (compressé)	35.6 %	600	8.7 ko

• Flat : rappel parfait, mais touche tout et stocke tout.
• IVF : moins de comparaisons, mémoire pleine.
• HNSW : très peu de comparaisons, grosse bulle mémoire.
• PQ : petite bulle, mais comparaisons toujours de l'ordre de n.

Personne n'atteint le coin parfait : rappel haut, peu de comparaisons, petite bulle.

Trois questions à te poser en jouant :

1. Pousse $\mathit{nprobe}$ d’IVF à son maximum. Son point rejoint-il le rappel de Flat ? Que devient alors le nombre de comparaisons ?
2. Compare les bulles de HNSW et de Flat. Laquelle est la plus grosse, et pourquoi un graphe coûte-t-il plus de mémoire qu’un simple tableau de vecteurs ?
3. Réduis le nombre de tranches de PQ. Sa bulle rétrécit-elle ou grossit-elle, et qu’arrive-t-il à son rappel ? La position horizontale de PQ bouge-t-elle vraiment sur l’axe des comparaisons ?

Les familles se marient

Le plus beau, c’est que ces briques se combinent, justement parce que les deux axes sont indépendants. L’index le plus répandu à très grande échelle, l’IVFPQ, partitionne l’espace (pour la vitesse) et compresse les vecteurs (pour la mémoire) : il gagne deux côtés du triangle d’un coup, en sacrifiant davantage de rappel. On peut de même greffer la quantification sous un graphe. La grille de lecture n’est donc pas une étagère de produits rivaux, mais une boîte de Lego : on assemble une stratégie de routage et une stratégie de stockage selon la richesse qu’on est prêt à sacrifier.

Exercices

En une phrase

Aucun index ne maximise à la fois rappel, latence et mémoire : Flat est exact mais lourd et lent, IVF achète la vitesse en partitionnant, HNSW l’achète encore mieux mais paie la mémoire, la quantification produit achète la mémoire mais scanne toujours tout, et les vrais index combinent ces briques selon le côté du triangle qu’ils acceptent de sacrifier.

Quiz

1. 1. Pourquoi parle-t-on d'un triangle des compromis pour les index ANN ?

   • Parce qu'il existe exactement trois familles d'index
   • Parce qu'on ne peut pas maximiser à la fois le rappel, la latence et la mémoire
   • Parce que chaque index a trois paramètres de réglage
   • Parce que les vecteurs ont toujours trois dimensions
   Valider

2. 2. Que gagne, et que ne gagne pas, la quantification produit (PQ) employée seule ?

   • Elle gagne la vitesse mais pas la mémoire
   • Elle gagne le rappel mais pas la vitesse
   • Elle gagne la mémoire mais pas la vitesse, car elle scanne toujours tous les codes
   • Elle gagne à la fois la mémoire, la vitesse et le rappel
   Valider

3. 3. Sur quels deux axes orthogonaux se range tout index ANN ?

   • La dimension des vecteurs et leur nombre
   • Comment éviter le scan (rien, partition, graphe) et comment stocker (plein, compressé)
   • Le rappel visé et le budget financier
   • La vitesse d'écriture et la vitesse de lecture
   Valider

Vers le chapitre 5

Tout au long de ce chapitre, un mot est revenu sans qu’on ose le regarder en face : on mesure le rappel d’un index approché en le comparant à l’oracle exact. Mais cet oracle, justement, qui le fournit, et à quel prix ? Mesurer honnêtement la qualité d’un index suppose de connaître la vraie réponse, donc de lancer une recherche exhaustive de référence, et de la confronter méthodiquement aux résultats approchés. Le chapitre 5 construit ce juge : l’oracle différentiel, le banc d’essai qui met l’index rapide face à la vérité lente, mesure rappel et latence côte à côte, et transforme le choix d’un index, jusqu’ici intuitif, en une décision chiffrée. C’est le climax du cours, là où l’on cesse de croire un index sur parole.

Sources

• Jégou, H., Douze, M. & Schmid, C. (2011). « Product Quantization for Nearest Neighbor Search. » IEEE Transactions on Pattern Analysis and Machine Intelligence 33(1), 117-128. DOI 10.1109/TPAMI.2010.57
• Johnson, J., Douze, M. & Jégou, H. (2021). « Billion-scale Similarity Search with GPUs. » IEEE Transactions on Big Data 7(3), 535-547. arXiv:1702.08734

Pour aller plus loin

• Subramanya, S. J. et al. (2019). « DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. » NeurIPS. Lien éditeur
• Malkov, Y. A. & Yashunin, D. A. (2018). « Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. » IEEE TPAMI. arXiv:1603.09320