Qu'est-ce que FAISS ?

FAISS est une bibliothèque open-source qui cherche, dans un ensemble de vecteurs denses, les vecteurs les plus proches d’un vecteur de requête. Le nom signifie Facebook AI Similarity Search. Le projet écrit le nom « Faiss ».

Fonctionnement

Un vecteur dense est une liste de nombres de longueur fixe. Un réseau de neurones peut transformer une image ou un texte en un tel vecteur, appelé plongement (embedding). FAISS stocke de nombreux vecteurs dans un index. Pour un vecteur de requête, il renvoie les vecteurs les plus proches et leurs distances. Il compare les vecteurs par distance L2 (euclidienne) ou par produit scalaire. Il prend aussi en charge la similarité cosinus, qui est le produit scalaire des vecteurs normalisés.

Le groupe Fundamental AI Research de Meta développe FAISS. La bibliothèque est écrite en C++ et possède des interfaces pour Python. Certains algorithmes s’exécutent aussi sur un GPU.

Types d’index

Le type d’index fixe l’équilibre entre vitesse et exactitude.

• IndexFlatL2 et IndexFlatIP comparent la requête à chaque vecteur, le résultat est donc exact. IndexFlatIP utilise le produit scalaire. Avec des vecteurs normalisés, il donne la similarité cosinus.
• IndexIVFFlat répartit les vecteurs en nlist cellules. Une requête ne parcourt que nprobe d’entre elles. C’est plus rapide, mais le plus proche voisin peut être manqué si sa cellule n’est pas parcourue.
• IndexHNSWFlat parcourt un graphe des vecteurs (un graphe hiérarchique navigable à petit monde).
• IndexIVFPQ ajoute la quantification produit, qui stocke chaque vecteur sous une forme compressée.

La plupart des index doivent être entraînés sur des vecteurs d’exemple avant leur utilisation. IndexFlatL2 n’a pas besoin d’entraînement.

Échelle

FAISS peut parcourir des ensembles de vecteurs qui ne tiennent pas dans la RAM. Dans l’article de 2017, les auteurs ont construit un graphe de plus proches voisins de 1 milliard de vecteurs en moins de 12 heures sur 4 GPU.