- La recherche basée sur des embeddings à vecteur unique est rapide et efficace, mais les modèles multi-vecteurs récents comme ColBERT offrent une sémantique plus riche et une meilleure précision grâce à de multiples vecteurs par token
- L’approche multi-vecteur augmente fortement le volume de calcul et le coût de recherche en raison de calculs de similarité complexes comme la Chamfer similarity, ce qui freine son usage à grande échelle en temps réel
- MUVERA, proposé par l’équipe de recherche de Google, compresse l’information multi-vecteur en un vecteur de longueur fixe (FDE, Fixed Dimensional Encoding), puis effectue une recherche ultra-rapide via un MIPS (recherche du produit scalaire maximal) à vecteur unique avant reranking
- Cette approche est indépendante des données et fournit une base théorique (garantie sur l’erreur d’approximation de la Chamfer similarity), avec plus de 90 % de réduction de latence et plus de 10 % d’amélioration du recall par rapport à PLAID
- Le FDE prend aussi en charge la compression (jusqu’à 32× moins de mémoire), et l’implémentation open source ainsi que l’article sont disponibles, ce qui la rend adaptée à un déploiement en production pour la recherche, la recommandation et le NLP
Progrès des modèles d’embedding et de la recherche d’information
- Les modèles d’embedding basés sur le deep learning sont devenus un outil clé pour retrouver rapidement des informations pertinentes dans de vastes jeux de données (documents, images, vidéos, etc.) à partir de requêtes utilisateur (ex. : « hauteur du mont Everest »)
- En convertissant chaque point de données en embedding à vecteur unique, ils sont conçus pour que des données sémantiquement proches présentent aussi une structure vectorielle numériquement similaire
- En exploitant le calcul de similarité par produit scalaire entre vecteurs, ils offrent de hautes performances grâce aux algorithmes MIPS (Maximum Inner Product Search)
- Mais récemment, des modèles multi-vecteurs comme ColBERT attirent l’attention grâce à leur meilleure précision de recherche et à leur capacité à capturer des relations plus complexes
Adoption et limites des modèles multi-vecteurs
- Les modèles multi-vecteurs représentent chaque point de données sous forme d’un ensemble de plusieurs vecteurs d’embedding
- En utilisant des fonctions de similarité composites comme la Chamfer similarity, ils capturent avec précision des informations et des relations qu’un vecteur unique ne pouvait pas détecter
- Cette approche permet une recherche d’information plus précise et des recommandations de documents plus pertinentes
- Son inconvénient est qu’avec l’augmentation du nombre d’embeddings et la complexité du calcul de similarité, les ressources de calcul nécessaires à la recherche deviennent considérables
- augmentation du nombre de vecteurs par token → forte hausse du calcul et de la mémoire
- opérations non linéaires (multiplication matricielle) indispensables → impossibilité d’une recherche sublinéaire (ultra-rapide) fondée sur un vecteur unique
- explosion des coûts et de la latence lors d’un déploiement à grande échelle
MUVERA : révolutionner la recherche multi-vecteur avec le FDE
- L’article “MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings” propose un nouvel algorithme pour surmonter ce problème d’efficacité
- MUVERA convertit l’information multi-vecteur en un unique vecteur FDE, ce qui permet de réutiliser tel quel l’infrastructure d’indexation et les serveurs MIPS existants pour une recherche rapide de candidats
- Création du FDE : conversion des ensembles multi-vecteurs des requêtes et documents en vecteurs de longueur fixe (FDE) via un mapping indépendant des données
- Recherche MIPS : stockage des FDE de tous les documents dans un index MIPS, puis exploration ultra-rapide des candidats à partir du FDE de la requête
- Reranking avec garantie de précision : application des opérations multi-vecteurs d’origine, comme la Chamfer similarity, uniquement aux documents candidats afin de produire le résultat final via un reranking précis
- Le FDE peut être appliqué indépendamment du jeu de données, ce qui le rend aussi avantageux dans des environnements dynamiques comme le streaming
Fondements théoriques
- En s’inspirant d’algorithmes géométriques avancés comme les probabilistic tree embeddings, le FDE approxime efficacement la similarité multi-vecteur
- L’espace d’embedding est partitionné aléatoirement, et une similarité approximative est calculée lorsque les vecteurs de la requête et du document se trouvent dans la même section
- L’article présente à la fois la théorie garantissant une borne d’erreur pour l’approximation de la Chamfer similarity et des résultats expérimentaux
Résultats expérimentaux et performances
- Les performances de MUVERA ont été validées sur divers grands jeux de données d’IR, notamment le benchmark BEIR
- recall moyen supérieur de 10 % à celui de PLAID et d’autres approches existantes
- réduction de plus de 90 % de la latence de recherche
- à recall équivalent, réduction du nombre de documents candidats fondés sur le FDE d’un facteur 5 à 20 par rapport à l’existant
- bonne compatibilité avec des techniques de compression supplémentaires comme Product Quantization (mémoire divisée par 32)
- Cela améliore fortement la praticité de la recherche multi-vecteur et la rend adaptée aux applications de recherche, de recommandation et de NLP à grande échelle
Conclusion et usages
- MUVERA est une approche innovante qui accélère la recherche multi-vecteur jusqu’au niveau d’un système à vecteur unique
- L’implémentation open source (lien GitHub), l’article et les résultats expérimentaux sont tous publics
- Une alternative concrète pour améliorer l’efficacité de la recherche multi-vecteur à grande échelle dans les moteurs de recherche, systèmes de recommandation et traitements du langage naturel
- Avec de futurs travaux et optimisations, cette approche pourrait être adoptée dans un éventail industriel encore plus large
1 commentaires
Discussion sur Hacker News
Présentation d’un retour d’expérience sur l’ajout récent de Muvera à Weaviate, avec partage de liens vers le blog et le podcast. Dans une approche multi-vector de style ColBERT, il est mentionné que le coût explose lorsqu’on crée un embedding pour chaque token. Par exemple, au lieu d’un vecteur classique de 768 dimensions, on peut monter à 16 640 dimensions ou plus, ce qui devient irréaliste dans de nombreux cas. Muvera convertit plusieurs vecteurs en un seul vecteur de dimension fixe, généralement plus petite, utilisable directement dans n’importe quel index ANN. Grâce à l’usage d’un vecteur unique, il est aussi possible d’appliquer les algorithmes existants et diverses techniques de quantification, avec à la clé des économies de mémoire. Contrairement à PLAID, Muvera ne nécessite ni structure d’index spécifique ni hypothèse de clustering particulière, ce qui permet aussi de réduire la latence
Mention d’une tendance récente à s’éloigner des méthodes qui aplatissent les embeddings en un seul embedding via mean-pooling. Comme il y a trop de vecteurs pour traiter tous les embeddings token par token, il faut une méthode pour les réduire de manière appropriée. Ici, les embeddings de tokens sont clusterisés par partitions arbitraires, puis chaque groupe est agrégé par mean-pooling avant d’être concaténé pour former un embedding de longueur fixe. Comme une comparaison multi-vector complète est difficile en termes de performances, ils regroupent et comparent cela avec les outils et performances du mono-vecteur en clusterisant en k vecteurs puis en les concaténant. Au final, comme le nombre de partitions est fixe, cela revient à un effet de clustering des embeddings de tokens de type k-means. Il est aussi suggéré qu’un clustering dynamique des tokens pourrait produire des embeddings à nombre variable de composantes et éventuellement de meilleurs résultats
Partage d’une expérience indiquant que cette méthode était très sensible aux hyperparamètres et que, dans ses essais, elle n’atteignait pas des performances comparables à maxsim
Compréhension proposée selon laquelle Muvera calcule le FDE (Fixed Dimensional Embedding) de la requête, puis cherche des FDE similaires dans le dataset du modèle ; question posée : faut-il alors calculer aussi tous les FDE de même taille pour l’ensemble du modèle ?
Question d’une personne peu familière avec le domaine : une requête par neural embedding fonctionne-t-elle comme une requête SQL qui renvoie tous les noms d’une table, ou les résultats sont-ils plus ambigus ?
Résumé de cette approche comme une tentative de compresser plusieurs embeddings en un seul — autrement dit un « embedding of embeddings » — afin de réduire la dimension et d’améliorer les performances. Comme plusieurs embeddings contiennent en grande partie des informations qui se recoupent, l’idée est que si on peut les compresser en un seul, la valeur apportée par les embeddings supplémentaires est probablement limitée. Si les performances restent similaires, cela soulève une question, du point de vue de la théorie de l’information, sur la possibilité de représenter cela sans perte
Question sur la différence avec les méthodes classiques de feature hashing (réduire plusieurs embeddings en un seul), et sur l’intérêt possible de techniques de réduction de dimension mono-vecteur comme UMAP