À l’intérieur des bases de données vectorielles : IVF, arbres, HNSW et quantification produit.

Des termes tels que RAG, les bases de données vectorielles, le retraitement et le chunking sont constamment mentionnés, et ils semblent plus complexes qu’ils ne le sont en réalité. Cet article commence par les bases de données vectorielles : ce qu’elles stockent et comment les recherches s’y déroulent réellement.

D’où viennent les vecteurs

Les modèles d’incorporation, entraînés sur d’immenses collections de texte, transforment le sens d’une phrase en une liste de nombres. Certains sont hébergés en ligne, comme les modèles d’incorporation de texte d’OpenAI et ceux de Gemini de Google. D’autres fonctionnent localement, tels que la famille de modèles d’incorporation Qwen3 en versions 8B, 4B et 0,6B, ou le modèle de texte Jina v5-small comptant environ 677 millions de paramètres. En passant votre texte par l’un de ces modèles, vous obtenez un vecteur que vous pouvez stocker et récupérer ultérieurement.

Le vocabulaire

Quelques termes reviennent systématiquement dans toutes les bases de données vectorielles :

• Collection. Un espace de noms contenant des points qui partagent une même dimension fixe et une même métrique de distance.
• Point. Un vecteur accompagné de son identifiant et d’un en-tête de métadonnées.
• Métrique de distance. La manière de mesurer la proximité, généralement la similarité cosinus, le produit scalaire ou la distance euclidienne.
• Upsert. L’opération qui insère des données, en ajoutant de nouveaux points et en mettant à jour les existants.
• Recherche. L’opération de requête à laquelle tout le reste sert.

L’intuition : exact contre approximatif

La méthode naïve pour trouver les vecteurs liés à une requête parmi 10 000 ou plus consiste à calculer la similarité cosinus avec chaque vecteur stocké et à conserver les k meilleurs. Le résultat est l’ensemble des voisins les plus proches exacts. Cependant, avec des millions de vecteurs, cette recherche par force brute devient peu pratique en raison des contraintes de mémoire et de temps. C’est pourquoi les systèmes ont adopté la recherche de voisins les plus proches approximatifs (ANN), qui accepte une légère perte en précision en échange d’une grande amélioration de la vitesse.

Cette compromis peut être réalisé de deux manières principales. L’indexation réduit le nombre de comparaisons nécessaires. La quantification diminue le coût de chaque comparaison. Ensemble, elles forment l’ensemble des outils utilisés en ANN.

Indexation, première option : clustering avec IVF

Un index de fichiers inversé (IVF) divise les vecteurs en clusters, chacun possédant un centre de masse. Une requête est d’abord comparée uniquement aux centres de masse. Une fois le cluster le plus proche identifié, la requête est comparée uniquement aux vecteurs de ce cluster, et les k meilleurs résultats sont retournés.

Les faiblesses à connaître sont les suivantes :

• Les voisins situés près des limites des cellules sont manqués. Si la correspondance réelle se trouve dans une cellule qui n’a pas été examinée, elle ne sera jamais trouvée. Vérifier davantage de cellules aide, mais ralentit la recherche et nuit à son objectif.
• La qualité diminue à mesure que les données changent. Les clusters sont fixés au moment de leur création, de sorte que de nouvelles données finissent toujours dans des cellules anciennes, ce qui entraîne une dégradation de la qualité de la recherche. Des reconstructions périodiques sont nécessaires.

Des clusters inégaux rendent la vitesse imprévisible. Certaines cellules deviennent énormes tandis que d’autres restent minuscules, de sorte qu’une requête qui se retrouve dans une cellule grande est lente, tandis qu’une requête dans une cellule petite est rapide.

Des données d’entraînement sont nécessaires au préalable. L’index ne peut être créé qu’une fois que suffisamment de données existent pour former des clusters significatifs, ce qui est problématique pour les applications qui partent de zéro.

Deux paramètres sont difficiles à ajuster. Le nombre de clusters ainsi que le nombre de recherches par requête influencent tous deux les résultats, et des valeurs incorrectes ralentissent ou affaiblissent la précision de la recherche.

Les hautes dimensions brouillent les clusters. Avec des vecteurs très longs, les clusters deviennent flous, ce qui fait que la précision par unité de travail est inférieure à celle de HNSW.

En une phrase : l’IVF est simple et économise de la mémoire, mais elle perd en précision près des limites et n’aime pas les mises à jour fréquentes, c’est pourquoi elle excelle à l’échelle de milliards lorsqu’elle est associée à la quantification des produits, tandis que HNSW l’emporte pour les recherches en temps réel à haute précision.

Indexation, deuxième option : partitionnement basé sur des arbres

L’indexation basée sur des arbres s’inspire de la recherche binaire. Au lieu de comparer la requête à chaque vecteur, l’espace est divisé en deux répétitivement, et seule la moitié contenant la requête est examinée.

Pour construire l’index, on prend tout l’espace et on le divise avec une ligne de séparation, puis on divise à nouveau chaque moitié, en continuant jusqu’à ce que chaque petite région ne contienne que quelques vecteurs. Chaque région est une feuille. En deux dimensions, la première division peut se faire le long de l’axe x, la suivante le long de l’axe y, et ainsi de suite. Toutes ces divisions forment un arbre binaire dans lequel chaque nœud représente une question oui/non, comme par exemple savoir si x est inférieur à 5, et les feuilles se trouvent en bas de l’arbre.

Lorsqu’une requête arrive, on part de la racine et on répond à une question à la fois : à gauche de cette division ou à droite ? Chaque réponse élimine la moitié de l’espace restant. Après environ log n questions, soit environ 20 pour un million de vecteurs, on arrive à une petite feuille et on compare la requête avec les quelques vecteurs qu’elle contient.

Il y a un piège. Le véritable voisin le plus proche peut se trouver juste de l’autre côté d’une ligne de séparation, à courte distance mais dans une autre branche, et un seul arbre ne le détectera jamais. Des bibliothèques comme Annoy de Spotify construisent donc de nombreux arbres, chacun avec des divisions aléatoires différentes. Chaque arbre propose des candidats, ces propositions sont fusionnées et les meilleurs sont retournés. Ce que l’un des arbres rate, un autre le repère généralement.

Les inconvénients :

• Le problème des frontières est pire que dans l’IVF. Avec l’IVF, manquer une frontière signifie vérifier une cellule de plus. Dans un arbre, un mauvais choix de direction près du sommet envoie la recherche dans une région complètement différente.
• La solution entraîne des coûts en mémoire et en vitesse. Une forêt de 50 arbres signifie stocker l’index 50 fois et effectuer 50 recherches par requête, ce qui permet d’obtenir une précision au prix de ressources supplémentaires.
• Les vecteurs longs le surpassent. Les arbres fonctionnent bien en 2D, 3D, sur des cartes et dans les jeux. Les embeddings modernes possèdent des centaines ou des milliers de dimensions, où une ligne de séparation ne distingue presque rien de significatif, car les points situés des deux côtés peuvent être presque à égale distance. C’est la raison principale pour laquelle cette méthode a perdu en popularité pour la recherche par embedding.
• L’index est statique. Les arbres sont construits une seule fois à partir de données existantes et ne peuvent pas intégrer proprement de nouveaux vecteurs. Annoy, par exemple, nécessite une reconstruction complète pour ajouter des données, ce qui est peu adapté aux collections en évolution constante.
• Il est généralement surpassé. À égale précision, HNSW est plus rapide, et à égale mémoire, IVF avec quantification par produit permet une meilleure scalabilité. Les arbres restent principalement utilisés dans les systèmes anciens et là où des fichiers d’index de petite taille pouvant être mappés en mémoire sont importants.

En bref, les arbres sont simples et rapides à construire, mais les embeddings à haute dimension dissolvent leurs divisions et ne permettent pas de mises à jour ; par conséquent, ils servent aujourd’hui principalement de tremplin pour l’explication plutôt que d’option pour un usage en production.

Indexation, troisième option : HNSW

Hierarchical Navigable Small Worlds, ou HNSW, est la technique à l’origine de la plupart des bases de données vectorielles. Elle organise les vecteurs en un graphe composé de plusieurs couches. Les couches supérieures ne contiennent que quelques vecteurs reliés par des liens à longue portée, comme des autoroutes entre villes, tandis que les couches inférieures contiennent progressivement davantage de vecteurs reliés par des liens plus courts, jusqu’à la couche la plus basse qui regroupe tous les vecteurs.

Une recherche commence en haut et se déplace avidement vers le voisin le plus proche de la requête. Lorsqu’aucun voisin n’est plus proche, elle descend d’un niveau et recommence à partir de là, avec des liens plus détaillés. Au niveau le plus bas, elle explore un voisinage plus large et retourne les meilleures correspondances. De grands sauts couvrent rapidement de grandes distances, tandis que de petits pas affinent la réponse ; c’est pourquoi le nombre de comparaisons reste faible même pour de très grandes collections.

Quelques paramètres contrôlent l’équilibre entre vitesse et précision :

• M définit le nombre de liens que conserve chaque vecteur. Plus de liens améliorent la précision et la capacité de rappel, mais consomment plus de mémoire.
• efConstruction détermine l’étendue du voisinage exploré pendant la construction du graphe. Des valeurs plus élevées donnent un meilleur graphe, mais une construction plus lente.

efSearch détermine l’ampleur de la liste des résultats lors de la recherche. Une valeur élevée améliore à la fois la précision et le temps de réponse.

Comprendre comment une requête progresse à travers les différentes étapes, ainsi que la manière dont ces paramètres influencent ce parcours, permet d’expliquer comment leur modification affecte le comportement de recherche.

Quantification : rendre chaque comparaison moins coûteuse

L’indexation réduit le nombre de comparaisons nécessaires. La quantification diminue le coût de chacune d’elles. Un vecteur unique de 1536 dimensions composé de nombres flottants de 32 bits occupe 1536 fois 4, soit 6144 octets. Pour un milliard de vecteurs, cela représente des téraoctets de stockage, bien plus que ce qui peut tenir en RAM.

Quantification du produit

La quantification des produits divise chaque vecteur de grande taille en segments plus petits de taille égale. Un vecteur à 16 dimensions peut ainsi se transformer, par exemple, en quatre segments de quatre dimensions chacun. Pour chaque position de segment, un livre de codes est entraîné à partir des données stockées et comprend 256 entrées, chacune représentant un sous-vector typique. Chaque segment est ensuite remplacé par le numéro de l’entrée du livre de codes la plus proche, ce qui ne nécessite qu’un seul octet.

Ainsi, un vecteur qui nécessitait des milliers d’octets devient une courte séquence d’entiers petits. Pour effectuer une recherche, la requête est divisée de la même manière, et les distances par rapport aux entrées du livre de codes sont calculées une seule fois avant d’être réutilisées lors des recherches pour chaque vecteur stocké. Ce calcul est fortement approximatif, mais les gains en vitesse et en mémoire sont importants.

Choix parmi eux

Une comparaison rapide résume bien la situation :

• IVF est simple et peu gourmand en mémoire. Associez-la à la quantification des produits pour des collections statiques très volumineuses.
• Les arbres sont faciles à comprendre et peu coûteux à créer, mais ils conviennent aux données à faible dimension et inchangées.
• HNSW offre une grande précision et une recherche en temps réel rapide, au prix d’une consommation accrue de mémoire.
• La quantification des produits compresse les vecteurs et accélère les calculs de distance, avec une perte de précision contrôlée, et peut être combinée aux index mentionnés ci-dessus.

Connaître ces compromis vous aide à décider quand une recherche approximative est appropriée, quel algorithme convient à une tâche donnée, et quand la force brute reste la meilleure solution, par exemple pour de petites collections où la précision n’a pas un coût élevé.