Accélérer la fusion des graphiques de HNSW

De la recherche vectorielle aux puissantes API REST, Elasticsearch offre aux développeurs la boîte à outils de recherche la plus complète. Explorez nos notebooks d’exemples sur GitHub pour tester de nouveaux cas d’usage. Vous pouvez également démarrer votre essai gratuit ou exécuter Elasticsearch en local dès aujourd’hui.

Dans le passé, nous avons abordé certains des défis posés par la recherche dans plusieurs graphes de HNSW et la manière dont nous avons pu les atténuer. À cette occasion, nous avons fait allusion à d'autres améliorations que nous avions prévues. Ce billet est l'aboutissement de ce travail.

Vous vous demandez peut-être pourquoi utiliser des graphiques multiples ? Il s'agit d'un effet secondaire d'un choix architectural de Lucene : les segments immuables. Comme pour la plupart des choix architecturaux, il y a des avantages et des inconvénients. Par exemple, nous avons récemment obtenu la certification Serverless Elasticsearch. Dans ce contexte, nous avons tiré des avantages très importants des segments immuables, notamment une réplication efficace de l'index et la possibilité de découpler le calcul de l'index et de la requête et de les faire évoluer indépendamment. Pour la quantification vectorielle, les fusions de segments nous donnent la possibilité de mettre à jour les paramètres pour les adapter aux caractéristiques des données. Dans le même ordre d'idées, nous pensons que la possibilité de mesurer les caractéristiques des données et de revoir les choix d'indexation présente d'autres avantages.

Dans ce billet, nous discuterons du travail que nous avons effectué pour réduire de manière significative la charge de travail liée à la construction de plusieurs graphes HNSW et, en particulier, pour réduire le coût de la fusion des graphes.

Arrière-plan

Afin de maintenir un nombre raisonnable de segments, Lucene vérifie périodiquement s'il doit fusionner des segments. Cela revient à vérifier si le nombre de segments actuel dépasse un nombre de segments cible, qui est déterminé par la taille du segment de base et la politique de fusion. Si le nombre est dépassé, Lucene fusionne les groupes de segments alors que la contrainte n'est pas respectée. Ce processus a été décrit en détail dans d'autres documents.

Lucene choisit de fusionner des segments de taille similaire car cela permet d'obtenir une croissance logarithmique de l'amplification de l'écriture. Dans le cas d'un index vectoriel, l'amplification de l'écriture est le nombre de fois qu'un vecteur sera inséré dans un graphique. Lucene essaiera de fusionner les segments par groupes d'environ 10. Par conséquent, les vecteurs sont insérés dans un graphe environ 1+\frac{9}{10}\log_{10}\left (\frac{n}{n_0}\right ) fois, où $n est$ le nombre de vecteurs de l'index et $n_0$ est le nombre de vecteurs du segment de base attendu. En raison de la croissance logarithmique, l'amplification de l'écriture est à un chiffre, même pour les indices les plus importants. Cependant, le temps total passé à fusionner les graphes est linéairement proportionnel à l'amplification de l'écriture.

Lors de la fusion des graphes HNSW, nous procédons déjà à une petite optimisation : nous conservons le graphe du plus grand segment et y insérons les vecteurs des autres segments. C'est la raison pour laquelle le facteur 9/10 est mentionné ci-dessus. Nous montrons ci-dessous comment nous pouvons faire beaucoup mieux en utilisant les informations de tous les graphiques que nous fusionnons.

Fusion du graphique HNSW

Auparavant, nous retenions le plus grand graphe et insérions des vecteurs provenant des autres en ignorant les graphes qui les contiennent. L'idée clé que nous utilisons ci-dessous est que chaque graphe HNSW que nous écartons contient des informations de proximité importantes sur les vecteurs qu'il contient. Nous aimerions utiliser cette information pour accélérer l'insertion d'au moins une partie des vecteurs.

Nous nous concentrons sur le problème de l'insertion d'un petit graphe $G_s=(V_s,E_s)$ dans un graphe plus grand $G_l=(V_l,E_l)$, puisqu'il s'agit d'une opération atomique que nous pouvons utiliser pour construire n'importe quelle politique de fusion.

La stratégie consiste à trouver un sous-ensemble de sommets de l'$ensemble J\subset V_s$ à insérer dans le grand graphe. Nous utilisons ensuite la connectivité de ces sommets dans le petit graphe pour accélérer l'insertion des sommets restants $V_s \setminus J.$ Dans ce qui suit, nous utilisons $N_s(u)$ et $N_l(u)$ pour désigner les voisins d'un sommet $u$ dans le petit et le grand graphe, respectivement. Schématiquement, le processus est le suivant.

MERGE-HNSW

Inputs $G_s$ and $G_l$

1$\;\;$Find $J\subset V_s$ to insert into $G_l$ using COMPUTE-JOIN-SET
2$\;\;$Insert each vertex $u\in J$ into $G_l$
3$\;\;$for $u\in V_s \setminus J$ do
4$\;\;\;\;J_u\leftarrow J\cap N_s(u)$
5$\;\;\;\;E_u\leftarrow \cup_{v\in J_u} N_l(u)$
6$\;\;\;\;W\leftarrow\,$FAST-SEARCH-LAYER$(J_u, E_u)$
7$\;\;\;\;neighbors \leftarrow\,$SELECT-NEIGHBORS-HEURISTIC$(u, W)$
8$\;\;\;\;J\leftarrow J \cup \{u\}$

Nous calculons l'ensemble $J$ à l'aide d'une procédure que nous décrivons ci-dessous (ligne 1). Ensuite, nous insérons chaque sommet de $J$ dans le grand graphe à l'aide de la procédure d'insertion HNSW standard (ligne 2). Pour chaque sommet que nous n'avons pas inséré, nous trouvons ses voisins que nous avons insérés et leurs voisins dans le grand graphe (lignes 4 et 5). Nous utilisons une procédure FAST-SEARCH-LAYER avec cet ensemble (ligne 6) pour trouver les candidats pour le site SELECT-NEIGHBORS-HEURISTIC de l'article HNSW (ligne 7). En fait, nous remplaçons SEARCH-LAYER pour trouver l'ensemble de candidats dans la méthode INSERT (Algorithme 1 de l'article), qui est par ailleurs inchangée. Enfin, nous ajoutons le sommet que nous venons d'insérer dans $J$ (ligne 8).

Il est clair que pour que cela fonctionne, chaque sommet dans $V_s \setminus J$ doit avoir au moins un voisin dans $J.$ En fait, nous exigeons que pour chaque sommet dans $u\in V_s \setminus J$ que $|J\cap N_s(u) |\geq k_u$ pour quelque $k_u<$ M, la connectivité maximale de la couche. Nous observons que dans les graphes HNSW réels, les degrés des sommets sont assez variés. La figure ci-dessous montre une fonction de densité cumulative typique du degré de sommet pour la couche inférieure d'un graphique Lucene HNSW.

Nous avons étudié la possibilité d'utiliser une valeur fixe pour $k_u$ et de la faire dépendre du degré du sommet. Ce deuxième choix conduit à des accélérations plus importantes avec un impact minimal sur la qualité du graphe, nous avons donc opté pour ce qui suit

Notez que $|N_s(u)$| est égal au degré du sommet $u$ dans le petit graphe par définition. Le fait d'avoir une limite inférieure de deux signifie que nous insérerons tous les sommets dont le degré est inférieur à deux.

Un simple argument de comptage suggère que si nous choisissons $J$ avec soin, il nous suffit d'insérer directement dans $G_l$ $environ \frac |V_s|.{1}{5}$ Plus précisément, nous colorons une arête du graphe si nous insérons exactement l'un de ses sommets d'extrémité dans $J.$ Nous savons alors que pour que chaque sommet de $V_s \setminus J$ ait au moins $k_u$ voisins dans $J$, nous devons colorer au moins \sum_ ${u\in V_s\setminus J} k_u$ arêtes. En outre, nous nous attendons à ce que

Ici, \mathbb {E}_U\left [N_s(U)|\right] est le degré moyen des sommets dans le petit graphe. Pour chaque sommet $u\in J$, nous colorons au plus $|N_s(u)|$ arêtes. Par conséquent, le nombre total d'arêtes que nous prévoyons de colorer est au maximum de $|J|\, \mathbb{E}$_U\left [|N_s(U)|\right]. Nous espérons qu'en choisissant $J$ avec soin, nous colorerons un nombre d'arêtes proche de ce nombre et donc, pour couvrir tous les sommets, $|J|$ doit satisfaire à

Ceci implique que |J|=\frac{1}{4}(|V_s|-|J|)=\frac{4}{5}\frac {1}{4}|V_s|=\frac{1}{5}|V_s|.

Si SEARCH-LAYER domine le temps d'exécution, cela signifie que nous pourrions accélérer le temps de fusion jusqu'à $5 fois.$ Compte tenu de la croissance logarithmique de l'amplification de l'écriture, cela signifie que même pour de très grands indices, nous ne ferions que doubler le temps de construction par rapport à la construction d'un seul graphique.

Le risque de cette stratégie est de nuire à la qualité du graphique. Nous avons d'abord essayé avec une version sans option FAST-SEARCH-LAYER. Nous avons constaté que cela dégradait la qualité des graphes dans la mesure où le rappel en fonction de la latence était affecté, en particulier lors de la fusion en un seul segment. Nous avons ensuite exploré diverses alternatives en effectuant une recherche limitée dans le graphique. Finalement, le choix le plus efficace a été le plus simple. Utilisez SEARCH-LAYER mais avec une faible ef_construction. Ce paramétrage nous a permis d'obtenir des graphes d'excellente qualité tout en réduisant le temps de fusion d'un peu plus de 30% en moyenne.

Calcul de l'ensemble de jonction

La recherche d'un bon ensemble de jointures peut être formulée comme un problème de couverture de graphe HNSW. Une heuristique gourmande est une heuristique simple et efficace pour approximer les couvertures optimales des graphes. L'approche que nous adoptons consiste à sélectionner les sommets un par un pour les ajouter à $J$ dans l'ordre décroissant des gains. Le gain est défini comme suit :

Ici, $c(v)$ représente le nombre de voisins d'un vecteur $v$ dans $J$ et $1\{\cdot\}$ est la fonction indicatrice. Le gain comprend la variation du nombre de sommets que nous avons ajoutés à $J$, c'est-à-dire \max $(k_v-c(v),0)$, puisque nous nous rapprochons de notre objectif en ajoutant un sommet moins couvert. Le calcul du gain est illustré dans la figure ci-dessous pour le sommet central orange.

Nous conservons l'état suivant pour chaque sommet $v :$

1. S'il est périmé,
2. Son gain $Gain(v)$,
3. Le nombre de sommets adjacents dans $J$ est noté $c(v),$
4. Un nombre aléatoire dans l'intervalle [0,1] qui est utilisé pour départager les ex-aequo.

Le pseudo-code pour le calcul de l'ensemble de jonction est le suivant.

COMPUTE-JOIN-SET

Inputs $G_s$

1$\;\;C\leftarrow\emptyset$
2$\;\;Gain_{exit}\leftarrow 0$
3$\;\;$for $u\in G_s$ do
4$\;\;\;\;C\leftarrow C \cup \{(\text{false}, k_u+deg(u), 0, \text{rand in }[0,1])\}$
5$\;\;\;\;Gain_{exit}\leftarrow Gain_{exit}+k_u$
6$\;\;Gain_{tot}\leftarrow 0$
7$\;\;$while $Gain_{tot}<Gain_{exit}$ do
8$\;\;\;\;v^*\leftarrow\,$ maximum gain vertex in $C$
9$\;\;\;\;$Remove the state for $v^*$ from $C$
10$\;\;\;$if $v^*$ is not stale then
11$\;\;\;\;\;J\leftarrow J\cup\{v^*\}$
12$\;\;\;\;\;Gain_{tot}\leftarrow Gain_{tot}+Gain(v^*)$
13$\;\;\;\;\;$for $u \in N_s(v^*)$ do
14$\;\;\;\;\;\;\;$mark $u$ as stale if $c(v^*)<k_{v^*}$
15$\;\;\;\;\;\;\;$mark neighbors of $u$ stale if $c(u)=k_u-1$
16$\;\;\;\;\;\;\;c(u)\leftarrow c(u)+1$
17$\;\;\;$else
18$\;\;\;\;\;Gain(v^*)\leftarrow \max(k_v-c(v^*),0)+\sum_{u\in N_s(v^*)\setminus J} 1\left\{c(u)<k_u\right\}$
19$\;\;\;\;\;$if $Gain(v^*)>0$ then
20$\;\;\;\;\;\;\;C\leftarrow C \cup \{(\text{false},Gain(v^*),c(v^*),\text{copy rand})\}$
21$\;\;$return $J$

Nous commençons par initialiser l'état dans les lignes 1 à 5.

À chaque itération de la boucle principale, nous extrayons d'abord le sommet de gain maximal (ligne 8), en brisant les égalités de manière aléatoire. Avant de procéder à toute modification, nous devons vérifier si le gain du sommet est périmé. En particulier, chaque fois que nous ajoutons un sommet à $J$, nous affectons le gain d'autres sommets :

1. Puisque tous ses voisins ont un voisin supplémentaire en $J$, leurs gains peuvent changer (ligne 14)
2. Si l'un de ses voisins est maintenant entièrement couvert, tous les gains de ses voisins peuvent changer (lignes 14-16).

Nous recalculons les gains paresseusement, c'est-à-dire que nous ne recalculons le gain d'un sommet que si nous voulons l'insérer dans $J$ (lignes 18-20). Puisque les gains ne font que diminuer, nous ne pouvons jamais manquer un sommet que nous devrions insérer.

Notez que nous avons simplement besoin de suivre le gain total de sommets que nous avons ajoutés à $J$ pour déterminer quand sortir. En outre, pendant que Gain_{tot}< Gain_ {exit}au moins un sommet aura un gain non nul, de sorte que nous progressons toujours.

Résultats

Nous avons mené des expériences sur quatre ensembles de données qui, ensemble, couvrent les trois mesures de distance prises en charge (Euclidean, cosinus et produit intérieur) :

1. quora-E5-small : 522931 documents, 384 dimensions et utilise la similarité cosinus,
2. cohere-wikipedia-v2 : 1M documents, 768 dimensions et utilise la similarité cosinus,
3. gist : 1M documents, 960 dimensions et utilise la distance euclidienne, et
4. cohere-wikipedia-v3 : 1M documents, 1024 dimensions et utilise le produit intérieur maximum.

Pour chaque ensemble de données, nous évaluons deux niveaux de quantification :

1. int8 - qui utilise un entier de 1 octet par dimension et
2. BBQ - qui utilise un seul bit par dimension.

Enfin, pour chaque expérience, nous avons évalué la qualité de la recherche à deux profondeurs d'extraction et nous l'avons examinée après la construction de l'index, puis après la fusion forcée en un seul segment.

En résumé, nous obtenons des accélérations substantielles et constantes dans l'indexation et la fusion tout en maintenant la qualité du graphe et donc les performances de recherche dans tous les cas.

Expérience 1 : quantification int8

Les gains de vitesse moyens entre la ligne de base et le candidat, les changements proposés, sont les suivants :

Accélération du temps d'indexation : 1,$28$fois

Accélération de la fusion forcée : 1,$72$fois

Cela correspond à la répartition suivante des durées d'exécution

Par souci d'exhaustivité, les horaires exacts sont les suivants

Nous présentons ci-dessous les graphiques de rappel et de latence qui comparent le candidat (lignes pointillées) à la ligne de base à deux profondeurs de recherche : rappel@10 et rappel@100 pour les index avec plusieurs segments (le résultat final de notre stratégie de fusion par défaut après l'indexation de tous les vecteurs) et après la fusion forcée à un seul segment. Une courbe plus haute et plus à gauche est meilleure, ce qui signifie une meilleure mémorisation avec une latence plus faible.

Comme vous pouvez le constater, pour les indices de segments multiples, le candidat est meilleur pour l'ensemble de données Cohere v3 et légèrement moins bon, mais presque comparable, pour tous les autres ensembles de données. Après la fusion en un seul segment, les courbes de rappel sont presque identiques dans tous les cas.

Expérience 2 : Quantification BBQ

Les gains de vitesse moyens entre la ligne de base et le candidat sont les suivants :

Accélération du temps d'indexation : 1,$33$fois

Accélération de la fusion forcée : 1,$34$fois

Cela correspond à la répartition suivante des durées d'exécution

Par souci d'exhaustivité, les horaires exacts sont les suivants

Pour les indices de segments multiples, le candidat est meilleur pour presque tous les ensembles de données, à l'exception de cohere v2 où la ligne de base est légèrement meilleure. Pour les indices de segment unique, les courbes de rappel sont presque identiques dans tous les cas.

Conclusion

L'algorithme présenté dans ce blog sera disponible dans la prochaine version de Lucene 10.2, ainsi que dans la version d'Elasticsearch qui est basée sur cette dernière. Les utilisateurs pourront profiter de l'amélioration des performances de fusion et de la réduction du temps de construction de l'index dans ces nouvelles versions. Ce changement fait partie de nos efforts continus pour rendre Lucene et Elasticsearch rapides et efficaces pour la recherche vectorielle et hybride.