Une brève introduction à l'indice ScaNN

ScaNN est la réponse de Google à un défi familier de la recherche vectorielle à grande échelle : comment augmenter le débit des requêtes et réduire l'utilisation de la mémoire sans porter un coup inacceptable à la qualité des résultats. Sur le plan conceptuel, ScaNN part de la recette classique IVF+PQ (regroupement grossier et quantification agressive des produits), mais y ajoute deux innovations importantes qui déplacent de manière significative la frontière des performances :

• Un objectif de quantification sensible au score qui préserve mieux l'ordre relatif des vrais voisins, améliorant ainsi la qualité du classement même en cas de forte compression.

• FastScan est un chemin de recherche PQ 4 bits optimisé SIMD qui réduit le goulot d'étranglement traditionnel de la charge de mémoire en gardant plus de travail dans les registres de l'unité centrale.

En pratique, il s'agit d'un choix judicieux lorsque vous êtes d'accord pour échanger un peu de rappel contre un QPS élevé et une empreinte mémoire beaucoup plus petite (en compressant souvent les vecteurs à ~1/16 de la taille d'origine), comme dans les charges de travail de recommandation insensibles au rappel.

Dans ce billet, nous allons revisiter IVFPQ comme base de référence, explorer les optimisations clés que ScaNN introduit par-dessus, et conclure avec des résultats expérimentaux qui ancrent la discussion dans les performances mesurées.

Récapitulatif de l'IVFPQ

ScaNN a été proposé par Google en 2020, et l'article fait état d'une amélioration des performances de 3× par rapport à HNSW sur l'ensemble de données GloVe. Vous pouvez vous référer à l'article original et à l'implémentation open-source pour plus de détails.

Avant de présenter ScaNN, nous allons brièvement récapituler IVFPQ, puisque ScaNN est construit sur le même cadre général.

IVFPQ signifie Inverted File with Product Quantization (fichier inversé avec quantification de produit), un algorithme utilisé pour la recherche efficace et à grande échelle du plus proche voisin (ANN) dans des bases de données vectorielles de haute dimension. Il s'agit d'une approche hybride qui combine deux techniques, l'index de fichier inversé (IVF) et la quantification de produit (PQ), afin d'équilibrer la vitesse de recherche, l'utilisation de la mémoire et la précision.

Fonctionnement de l'IVFPQ

Le processus comprend deux étapes principales pendant l'indexation et la recherche :

• Couche IVF : les vecteurs sont regroupés en nlist listes inversées (clusters). Au moment de la requête, vous ne visitez qu'un sous-ensemble de grappes (nprobe) afin de trouver un compromis entre le rappel et la latence/le débit.

• Couche PQ : dans chaque grappe visitée, chaque vecteur de dimension D est divisé en m sous-vecteurs, chacun de dimension (D/m). Chaque sous-vecteur est quantifié en l'assignant au centroïde le plus proche dans son sous-codebook. Si un sous-codebook comporte 256 centroïdes, chaque sous-secteur peut être représenté par un code uint8 (un ID dans [0, 255]).

Le calcul de la distance peut alors être réécrit comme la somme des sous-vecteurs :

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L(q, id1) + L(q, id2) + L(q, id3) + ... + L(q, idn)

Ici, L représente une table de recherche. Au moment de la requête, la table de recherche est construite, enregistrant la distance entre la requête et chaque sous-vecteur quantifié. Tous les calculs de distance ultérieurs sont convertis en consultations de table suivies d'une sommation.

Par exemple, pour des vecteurs à 128 dimensions divisés en 32 sous-vecteurs de 4 dimensions chacun, si chaque sous-vecteur est codé par un ID uint8, le coût de stockage par vecteur passe de (128 x 4) octets à (32 x 1) octets, soit une réduction de 1/16.

Optimisations du ScaNN basées sur l'IVFPQ

En résumé, ScaNN améliore l'IVFPQ sur deux points :

1. Quantification : ScaNN propose un objectif qui va au-delà du simple remplacement de chaque sous-vecteur par son centroïde k-moyen le plus proche (c'est-à-dire la minimisation de l'erreur de reconstruction).

2. Efficacité de la recherche : ScaNN accélère la recherche basée sur les LUT, qui est souvent limitée par la mémoire, par le biais d'un chemin FastScan adapté à SIMD.

Perte de quantification en fonction du score

L'analyse étant basée sur la métrique IP, après que ScaNN a décomposé l'erreur de quantification en composantes parallèles et perpendiculaires, seule la composante parallèle affecte le résultat, de sorte qu'un terme de pénalité plus important doit être appliqué. Par conséquent, la fonction de perte peut être réécrite comme suit :

$$\begin{array}{r}{\displaystyle \mathrm{\ell }({\mathrm{xi}}_{},{\mathrm{x~i}}_{},w)}\end{array}$$$$∥2\begin{aligned} \ell\left(x_i, \tilde{x}_i, w\right) &=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$$ \tilde{x}_i\right$$)\right\|^2 \end{aligned}$$ ℓ$$\begin{array}{r}(x\end{array}$$i, x~i,w) =h∥$$\begin{array}{l}(w,\end{array}$$∥xi$$\begin{array}{l}\Vert )\end{array}$$ $$\begin{array}{l}r\end{array}$$∥ $$\begin{array}{l}(x\end{array}$$i, x~i) 2+h⊥ $$\begin{array}{l}(w,\Vert x\end{array}$$i$$\begin{array}{l}\Vert )\Vert r\end{array}$$⊥ $$\begin{array}{l}(x\end{array}$$i,

La figure ci-dessous montre un exemple bidimensionnel illustrant le fait que l'erreur causée par la composante parallèle est plus importante et peut conduire à des résultats incorrects pour le plus proche voisin, justifiant ainsi une pénalité plus sévère.

La figure de gauche montre une mauvaise quantification parce que le décalage parallèle affecte le résultat final, tandis que la figure de droite montre une meilleure quantification.

PQ FastScan 4 bits

Examinons tout d’abord le processus de calcul du PQ : lors de l’interrogation, les distances entre la requête et les centres de grappes du sous-vecteur sont calculées à l’avance pour construire une table de recherche. Le calcul de la distance est ensuite effectué par le biais de consultations de la table afin d’obtenir les distances entre les segments et de les additionner.

Cependant, les lectures fréquentes de la mémoire constituent toujours un goulot d'étranglement pour les performances. Si la table de recherche peut être suffisamment petite pour tenir dans des registres, les opérations de lecture de la mémoire peuvent être transformées en instructions SIMD efficaces de l'unité centrale.

Tout d'abord, chaque sous-vecteur est regroupé en 16 classes, de sorte qu'une valeur de 4 bits peut représenter un centre de cluster - d'où le nom de "PQ 4 bits". Ensuite, les distances généralement représentées sous forme de valeurs flottantes sont converties en uint8 à l'aide de la quantification scalaire (SQ). De cette manière, la table de recherche pour un sous-vecteur peut être stockée dans un registre utilisant 16 × 8 = 128 bits.

Enfin, examinons la disposition du stockage des registres (en utilisant le jeu d'instructions AVX2 comme exemple) : les sous-vecteurs de 32 vecteurs sont placés dans un registre de 128 bits, associé à la table de recherche. L'opération de "lookup" peut alors être réalisée efficacement en utilisant une seule instruction SIMD de l'unité centrale de traitement.

disposition des registres

SIMD Shuffle pour la recherche

Voici une observation intéressante : le document ScaNN se concentre entièrement sur la première optimisation, ce qui est raisonnable puisqu'il peut être considéré comme un document sur les algorithmes mettant l'accent sur les dérivations mathématiques. Cependant, les résultats expérimentaux présentés dans l'article sont remarquablement impressionnants.

Les résultats expérimentaux présentés dans le document ScaNN.

Intuitivement, l'optimisation de la perte seule ne devrait pas produire des effets aussi spectaculaires. Un autre blog l'a également souligné : ce qui fait vraiment la différence, c'est la partie FastScan du PQ 4 bits.

Résultats expérimentaux

Nous avons effectué un test simple à l'aide de l'outil d'évaluation des bases de données vectorielles VectorDBBench. L'avantage de ScaNN en termes de performances par rapport à IVFFLAT et IVF_PQ traditionnels est tout à fait évident. Après intégration dans Milvus, sur l'ensemble de données Cohere1M et avec le même taux de rappel, le QPS peut atteindre 5 fois celui d'IVFFLAT et 6 fois celui d'IVF_PQ.

Cependant, le QPS est légèrement inférieur à celui d'index basés sur des graphes comme HNSW, et n'est donc pas le premier choix pour les cas d'utilisation avec un QPS élevé. L'utilisation de ScaNN sans chargement de données brutes permet d'obtenir un QPS impressionnant avec une empreinte mémoire extrêmement faible (1/16 des données d'origine), ce qui en fait un excellent choix d'index.

Type d'index	Cas	QPS	latence(p99)	rappel	mémoire
IVFFLAT	Performance1M	266	0.0173s	0.9544	3G
HNSW	Performance1M	1885	0.0054s	0.9438	3.24G
IVF_PQ	Performance1M	208	0.0292s	0.928	0.375G
ScaNN（with_raw_data : true）	Performance1M	1215	0.0069s	0.9389	3.186G
ScaNN（with_raw_data : false）	Performance1M	1265	0.0071s	0.7066	0.186G

Conclusion

ScaNN s'appuie sur le cadre familier de l'IVFPQ, mais le pousse considérablement plus loin grâce à un travail d'ingénierie approfondi en matière de quantification et d'accélération de la recherche de bas niveau. En alignant l'objectif de quantification sur la qualité du classement et en éliminant les goulets d'étranglement de la mémoire dans la boucle interne, ScaNN combine une quantification sensible au score avec un chemin FastScan PQ 4 bits qui transforme un processus traditionnellement limité à la mémoire en un calcul efficace et adapté à la SIMD.

Dans la pratique, cela donne à ScaNN un créneau clair et bien défini. Il n'est pas destiné à remplacer les index basés sur les graphes tels que HNSW dans les environnements à fort rappel. Au contraire, pour les charges de travail insensibles aux rappels avec des budgets de mémoire serrés, ScaNN offre un débit élevé avec un encombrement très faible. Dans nos expériences, après intégration dans Milvus VectorDB, ScaNN a atteint environ 5 fois le QPS d'IVFFLAT sur l'ensemble de données Cohere1M, ce qui en fait un choix solide pour la recherche ANN à haut débit et à faible latence où la compression et l'efficacité comptent plus que le rappel parfait.

Si vous souhaitez explorer ScaNN plus avant ou discuter de la sélection d'index dans des systèmes réels, rejoignez notre canal Slack pour discuter avec nos ingénieurs et d'autres ingénieurs en IA de la communauté. Vous pouvez également réserver une session individuelle de 20 minutes pour obtenir des informations, des conseils et des réponses à vos questions dans le cadre des Milvus Office Hours.