Cinq façons d’indexer des vecteurs pour RAG, testées sur un million d’embeddings de Wikipédia

Un système RAG vit ou meurt en fonction de sa capacité de récupération des informations, et cette tâche devient de plus en plus difficile à mesure que le corpus s’agrandit. Cette présentation compare cinq méthodes d’indexation des vecteurs à l’aide d’une expérience réelle, de sorte que le choix de la méthode repose sur des données chiffrées et non sur des habitudes.

Qu’est-ce que l’indexation vectorielle et pourquoi est-elle importante ?

L’indexation vectorielle est un moyen d’organiser un grand ensemble de vecteurs afin de pouvoir trouver rapidement ceux qui sont similaires, sans devoir comparer la requête à chaque vecteur individuellement. Les bases de données relationnelles disposent d’équivalents sous forme de bucketing et de Z-ordering, qui réduisent la quantité de données à analyser pour une requête. Les bases de données vectorielles utilisent des structures spécialisées dans le même but : réduire l’espace de recherche.

Un système de récupération précis et à faible latence constitue la base de toute architecture RAG scalable. Les grandes entreprises en dépendent déjà : Amazon récupère des informations dans des catalogues contenant des millions de produits, Netflix dans des milliers de titres personnalisés pour un public mondial, et X dans des milliards de publications et de comptes. Les données arrivent désormais par teraoctets par jour, il est donc impensable de ne pas penser à l’échelle dès le départ ; cela doit faire partie de l’architecture dès la conception initiale.

Chaque méthode présentée ci-dessous est évaluée selon trois critères :

• Latence : vitesse à laquelle l’index restitue les résultats les plus pertinents (top-K).
• Précision de la récupération : degré de correspondance entre les résultats obtenus et ceux d’une recherche exacte.

Complexité de maintenance : difficulté à maintenir l’index à jour. La vérité de référence derrière une application RAG évolue rarement, et les données peuvent nécessiter un renouvellement toutes les 24 heures, ce qui exige que l’index puisse être mis à jour facilement dans ce délai sans un effort technique important.

Configuration du test

L’expérience a utilisé les un million de premières lignes du jeu de données CohereLabs/wikipedia-2023-11-embed-multilingual-v3, une taille suffisante pour mettre en évidence les différences entre les méthodes. Les requêtes ont été encodées avec mxbai-embed-large, qui génère des vecteurs de 1 024 dimensions correspondant aux encodages du jeu de données. Les index ont été créés dans PostgreSQL à l’aide de pgvector.

Méthode 1 : recherche plate

La recherche plate, également appelée force brute, est l’option la plus simple. On calcule la similarité entre la requête et chaque vecteur, puis on conserve les meilleures correspondances.

• Latence : la pire du groupe, car chaque vecteur est comparé. Le temps augmente de manière linéaire avec le nombre de vecteurs.
• Précision : la meilleure, car la recherche est exacte et retourne les vecteurs les plus proches réels.
• Entretien : aucun, puisqu’il n’y a pas d’index.

La latence moyenne lors des tests était de 6,25 secondes. Un grand distributeur la rejetterait immédiatement, tout comme une petite startup.

Méthode 2 : IVFFlat

Inverted File Flat est une technique de voisin le plus proche approximative. Elle utilise K-Means pour diviser l’espace vectoriel en clusters. Au lieu de scanner tout le contenu, elle identifie les centres de masse les plus proches de la requête et ne cherche que à l’intérieur de ces clusters, en utilisant des calculs de distance précis au sein d’eux.

Le flux s’effectue comme suit :

Query → closest centroids → search selected clusters → Top-K

Dans pgvector, deux paramètres le contrôlent. Le nombre de clusters, appelés listes, est déterminé à l’avance, et l’essai a utilisé 1 000 listes. Lors de la requête, un deuxième paramètre, probes, décide de combien de ces listes seront explorées. Lorsque probes est réglé sur 10, les dix listes dont les centres de masse se trouvent le plus près de la requête sont examinées.

La latence était acceptable. Avec un million de vecteurs et 1 000 clusters, les requêtes étaient traitées en au plus une seconde.

La précision était faible, pour deux raisons. D’abord, il y a le problème des limites : la proximité est mesurée par rapport aux centres de masse et non par rapport aux vecteurs eux-mêmes, ce qui fait que certains vecteurs très proches échappent à la détection s’ils appartiennent à un cluster dont le centre de masse se trouve par hasard plus loin de la requête. Deuxièmement, probes limite la recherche à un nombre fixe de clusters, de sorte que les vecteurs pertinents présents dans des clusters non explorés ne sont jamais pris en compte.

L’augmentation du nombre de sondes de 10 à 500 a accru la latence, bien que de manière légère dans ce test. Cependant, il est impossible de savoir à l’avance si 10, 100, 500 ou 900 sondes donneront le meilleur taux de récupération, car les véritables voisins pourraient se trouver dans un cluster qui a été ignoré. Utiliser les 1 000 sondes rend la méthode inutile, car cela transforme à nouveau l’index en une approche par force brute.

La maintenance était également médiocre. La création de l’index pour plus d’un million de vecteurs a pris environ 2,37 minutes, ce qui est acceptable. Les problèmes apparaissent lors des mises à jour : les index basés sur les centres de masse peuvent nécessiter un rec calcul ou un réindexage des vecteurs chaque fois qu’un nouveau lot de données arrive. Avec des milliards de vecteurs, ces coûts techniques pourraient ne pas en valoir la peine.

Pour ce cas d’usage, le compromis entre latence et précision n’était tout simplement pas acceptable. La question suivante est de savoir s’une autre méthode peut réduire la latence tout en améliorant les résultats de récupération.

Méthode 3 : HNSW

Un facteur cherchant une maison constitue une bonne analogie. Face à une adresse, il ne cherche pas dans chaque rue. Il emprunte les autoroutes principales menant à la région appropriée, où les connexions sont rares mais couvrent de longues distances. Ensuite, il passe aux routes principales, où le réseau est plus dense. Finalement, il parcourt les rues locales, où le réseau est le plus dense, jusqu’à atteindre la porte exacte.

HNSW, pour hierarchical navigable small world, fonctionne de la même manière. Il commence par des liens espacés et à long rayon d’action aux niveaux supérieurs, puis passe à des liens de plus en plus denses aux niveaux inférieurs, jusqu’à atteindre les vecteurs les plus proches. Si la hiérarchie des routes est bien organisée, la recherche se dirige directement vers la cible, et une bonne construction se traduit par un bon taux de rappel.

La latence était à nouveau acceptable, avec au plus une seconde pour un million de vecteurs.

La précision était bonne, mais présentait des réserves dues aux paramètres de construction. L’index est créé à l’aide d’une instruction de cette forme :

    CREATE INDEX wikipedia_embeddings_hnsw_idx
    ON wikipedia_embeddings
    USING hnsw (emb vector_cosine_ops)
    WITH (
        m = 16,
        ef_construction = 64
    );

Cette déclaration permet de construire l’index à partir du corpus. Trois paramètres sont importants :

• m représente le nombre de voisins à lesquels chaque vecteur peut être relié dans le graphe. Il contrôle la connectivité et la densité.
• ef_construction indique le nombre de voisins candidats pris en compte lors de la construction. Il détermine l’espace de recherche pendant cette étape.
• ef_search limite l’espace de recherche au moment de la requête, en définissant le nombre de candidats explorés pour y répondre.

Comment le graphe choisit-il ses m liens ? Pour un million de vecteurs, chacun dispose de 999 999 voisins potentiels. Le mécanisme de construction ne choisit pas au hasard : il évalue les candidats en fonction de la distance ainsi que d’une heuristique de sélection des voisins, puis retient un petit ensemble, d’environ 16 éléments, utiles pour naviguer dans le graphe.

Pourquoi cela améliore-t-il la précision ?

1. Un petit nombre de voisins utiles par vecteur forme les artères du graphe.
2. Ces liens sont sélectionnés pour maintenir le graphe connecté et facile à naviguer.
3. Lors d’une recherche, celle-ci suit ces liens pas à pas vers des vecteurs qui ressemblent davantage à la requête.
4. Puisque le graphe propose des chemins efficaces vers la région pertinente, il est plus probable d’atteindre les véritables voisins les plus proches.
5. Ainsi, une construction et une navigation minutieuses améliorent la précision tout en évitant une comparaison exhaustive.

En bref, le graphe est construit de manière intentionnelle et non aléatoire. La définition des valeurs m et ef_construction détermine sa structure, ce qui influence à son tour le taux de rappel.

La maintenance est le point faible de HNSW. La création de l’index pour un million de vecteurs a nécessité étonnamment 37 minutes. Lors des mises à jour, si l’ensemble de données initial est volumineux et représente bien la distribution globale des données, de nouvelles données peuvent continuer à être ajoutées sans avoir à reconstruire l’index. Cependant, à mesure que les données nouvelles augmentent par rapport à l’ensemble initial, la distribution peut changer, le graphe devient moins optimal et une reconstruction devient finalement nécessaire. Cela se produit moins souvent que avec IVF, mais cela arrive malgré tout.

Comme le graphe repose sur une construction fondée sur des principes clairs, c’est une meilleure option que IVF, malgré le travail d’ingénierie supplémentaire requis. L’équilibre entre latence et taux de récupération est acceptable, voire excellent.

Méthode 4 : BM25 associé à une recherche vectorielle

Parfois, la réponse évidente est la bonne. Alors que l’attention se porte sur des approches de plus en plus complexes, un algorithme ancien de trente ans reste pourtant très efficace. BM25 est un algorithme de classement lexical qui évalue les documents en fonction de la fréquence d’apparition des termes de la requête, de la rareté de ces termes dans l’ensemble du corpus et de la longueur du document.

Mécanisme d’action :

1. Les documents sont divisés en termes, et un index inversé associe chaque terme aux documents qui le contiennent.
2. La fréquence de terme mesure la fréquence d’apparition d’un terme dans un document donné.
3. La fréquence inverse de document mesure le degré de rareté ou de fréquence d’un terme dans l’ensemble de la collection.
4. Un terme fréquent dans un document mais peu courant dans l’ensemble reçoit une importance plus élevée.
5. BM25 combine ces éléments avec la longueur du document pour évaluer le degré de pertinence.
6. Lors de la requête, les termes de recherche sont recherchés dans l’index inversé, évalués par rapport aux documents correspondants, et ceux qui obtiennent les meilleures notes sont retournés.

La formule elle-même n’est pas très élégante, mais l’idée est simple : trouver les documents les plus pertinents par rapport aux mots de la recherche.

Une fois ces documents récupérés, l’espace de recherche a considérablement rétréci. Une recherche vectorielle sur cet ensemble restreint permet alors de trouver les meilleurs résultats. Il s’agit d’une récupération hybride.

Une précaution : la première étape cherche des mots-clés exacts, donc une erreur d’orthographe de l’utilisateur peut nuire. Une étape de normalisation assistée par l’IA, qui corrige les fautes d’orthographe et les variantes avant le début de la recherche, résout facilement ce problème.

Latence. La partie vectorielle répond en quelques millisecondes comme attendu, mais la partie lexicale a mis entre 12 et 14 secondes dans cette configuration. Le cache peut résoudre ce problème, bien que la première requête reste lente. Le cache mérite une mention ici car il fonctionne particulièrement bien avec BM25 : les documents exacts sont récupérés en correspondance avec des mots-clés. Pour d’autres méthodes d’indexation, le cache doit être sémantique, ce qui nécessite un seuil de similarité et peut nuire à une certaine précision de recherche.

Entretien. Aucun, puisqu’aucun index vectoriel n’est créé.

En pratique, pour la plupart des produits d’IA comptant jusqu’à environ 50 000 documents, la recherche hybride avec BM25 s’est avérée être le choix le plus fiable, offrant un bon équilibre entre latence et précision à cette échelle.

Méthode 5 : DiskANN et le graphe Vamana

Cette méthode est plus abstraite, tout comme les embeddings eux-mêmes. Le processus se déroule en huit étapes :

1. Commencez par la grande collection de vecteurs nécessitant une recherche efficace.
2. Créez un graphe en reliant chaque vecteur à un ensemble soigneusement choisi de voisins. C’est le graphe Vamana.
3. Stockez le graphe sur disque et non en mémoire, afin de pouvoir gérer des ensembles de données bien plus grands que la RAM.
4. Lorsqu’une requête arrive, partez d’un point d’entrée dans le graphe.
5. Suivez les connexions entre vecteurs, en avançant pas à pas vers les régions proches de la requête.
6. Chargez les nœuds nécessaires depuis le SSD au fur et à mesure que la recherche progresse.
7. Après avoir exploré suffisamment du graphe, collectez un petit ensemble de candidats prometteurs.
8. Comparez ces candidats plus précisément et retournez les K plus proches.

Le point clé est que le graphe de navigation est stocké sur SSD et non en RAM, ce qui fait que la taille n’est plus un obstacle majeur par rapport au coût en mémoire.

Filtrez d’abord les métadonnées

Une technique mérite une mention honorable et devrait être privilégiée par rapport aux méthodes mentionnées ci-dessus. Le filtrage des métadonnées repose sur le même principe que le regroupement dans une base de données relationnelle : on réduit l’ensemble des documents potentiels en fonction d’attributs tels que la catégorie, la date ou le propriétaire avant de lancer toute recherche vectorielle.

Lequel choisir ?

• Force brute : ensembles de données de petite à moyenne taille, jusqu’à environ 20 000 documents. Meilleure précision avec une latence acceptable.
• BM25 associé à une recherche vectorielle : ensembles de données de taille moyenne, d’environ 20 000 à 100 000 documents. Équilibre efficace entre la récupération lexicale et sémantique.
• HNSW : ensembles de données très volumineux contenant des millions de vecteurs ou plus. Bonne latence et précision, mais à un coût en termes de complexité de mise en place.
• DiskANN et Vamana : lorsque la RAM devient chère. Les SSD offrent une très grande capacité, donc c’est la mémoire, et non la taille, qui constitue la contrainte.
• IVFFlat : grands ensembles de données, comptant d’un à dix millions de vecteurs, lorsque la distribution des données se regroupe bien. Sinon, la précision diminue.