Por favor, utiliza una carga de trabajo de transmisión para evaluar los bancos de datos vectoriales.

Por favor, emplea una carga de trabajo de transmisión para evaluar los conjuntos de datos vectoriales.

Por qué una carga de trabajo estática no es suficiente y lo que aprendí al comparar HNSWLIB y DiskANN usando una carga de trabajo de transmisión

Las bases de datos vectoriales se construyen para la recuperación de vectores de alta dimensionalidad. Hoy en día, muchos vectores son embeddings generados por redes neuronales profundas como GPTs y CLIP para representar puntos de datos como fragmentos de texto, imágenes o pistas de audio. Los embeddings se utilizan en muchas aplicaciones como motores de búsqueda, sistemas de recomendación y chatbots. Puedes indexar los embeddings en una base de datos vectorial, que utiliza un índice de vecino aproximado (ANN) para admitir la recuperación rápida de los vecinos principales mediante una función de distancia como Coseno o Euclidiana. La latencia es de 2 a 10 milisegundos para un índice de 1 millón de vectores, y escala de forma sublineal (es decir, O(log n)) en función del tamaño del índice.

En esta publicación, señalo varios problemas con la forma en que evaluamos actualmente los índices ANN y sugiero un nuevo tipo de evaluación. Esta publicación se centra en los índices ANN para vectores de embeddings, un área que está recibiendo mucha atención recientemente: startups de bases de datos vectoriales como Pinecone, Zilliz, Qdrant y Weaviate ofrecen indexación y recuperación de embeddings como su servicio principal.

1. Una carga de trabajo estática no es suficiente.

La forma estándar de evaluar los índices ANN es mediante una carga de trabajo estática, que consiste en un conjunto de datos fijo y un conjunto de consultas fijo.

Una carga de trabajo estática primero construye el índice ANN a partir del conjunto de datos fijo, y luego ejecuta el conjunto de consultas fijo varias veces con diferentes configuraciones de parámetros y mide el rendimiento de consulta más alto que se puede alcanzar en cada nivel mínimo de precisión. Después de realizar el mismo procedimiento para cada índice ANN, la carga de trabajo genera una gráfica como la siguiente:

• La nueva función de IA generativa en BigQuery
• Experimenta el nuevo y mejorado Amazon SageMaker Studio
• Impulsando el impacto del producto con análisis prácticos

La gráfica anterior compara diferentes índices ANN utilizando una carga de trabajo estática llamada glove-100-angular, que contiene embeddings de palabras.

Este enfoque de evaluación fue popularizado por el proyecto ann-benchmarks que comenzó hace 5 años. Muchas bases de datos vectoriales ahora están midiendo su rendimiento utilizando este enfoque en sus blogs técnicos. Consulta el benchmark de Qdrant y el benchmark de Timescale.

La prueba de carga estática ha sido útil porque los resultados son fáciles de entender y nos permiten comparar el equilibrio entre la precisión y el rendimiento de la consulta en diferentes algoritmos de indexación utilizando una misma gráfica.

Sin embargo, no es una evaluación completa de los índices ANN y no deberías elegir un índice ANN para tu proyecto basándote únicamente en esto. Se centra excesivamente en la precisión de recall y el rendimiento de la consulta, sin tener en cuenta otros aspectos importantes como el rendimiento de indexación y el uso de memoria.

Debe reflejarse el rendimiento de la indexación.

La velocidad de indexación mide qué tan rápido puede aceptar nuevos puntos de datos el índice ANN. Al igual que la velocidad de consulta, generalmente está inversamente correlacionada con la precisión de recall. Por ejemplo, la siguiente gráfica muestra la relación entre la velocidad de indexación y el recall de los índices HNSWLIB y DiskANN Vamana.

Esta gráfica es similar a la gráfica anterior de Recall-QPS, pero a partir de esta gráfica puedes observar que un recall más alto también es un compromiso en el rendimiento del índice. Sin embargo, si estoy interesado tanto en el rendimiento de indexación como en el rendimiento de consulta, esta gráfica todavía es insuficiente porque no muestra el margen en el cual se realiza el equilibrio entre el recall y el rendimiento, ya que la prueba de carga estática separa las cargas de indexación y consulta.

Muchos índices ANN admiten una API de indexación por lotes que puede estar mucho más optimizada que la indexación de puntos individuales (es decir, agregar vectores uno a la vez) y puede crear un índice más preciso. Por ejemplo, los índices ANN basados en clústeres crean clústeres de todos los vectores en lotes. La prueba de carga estática separa las cargas de indexación y consulta, por lo que fomenta la indexación por lotes, lo cual puede no ser realista.

Otro problema relacionado con la indexación es la cuantización de productos (PQ). Muchos índices ANN utilizan la PQ u otras formas de compresión de vectores para acelerar el cálculo. La prueba de carga estática permite que los índices ANN creen un libro de códigos de compresión optimizado antes de que comience la fase de consulta, pero la obtención de un código de libro óptimo puede no ser factible en la práctica.

El uso de memoria es importante.

La mayoría de los índices ANN populares son en memoria, lo que significa que su estructura de datos principal se almacena en memoria volátil (DRAM) desde donde se atienden las consultas. Por lo tanto, es importante medir la eficiencia de memoria y su compensación con el rendimiento y la precisión de recall. Por ejemplo, en este documento de investigación, los autores midieron el uso de memoria de HNSW con 1 billón de puntos en 490 GB, mientras que NSG utiliza 303 GB, pero en cuanto al rendimiento y la precisión de consulta, HNSW domina ligeramente a NSG. Este tipo de compromiso debe ser el foco principal al evaluar los índices ANN.

Sin embargo, es difícil obtener una imagen realista de la eficiencia de memoria con solo una prueba de carga estática por varias razones. Por un lado, el algoritmo de índice ANN puede crear un índice optimizado para la lectura que es muy compacto pero a expensas del rendimiento de indexación posterior. Además, la carga de trabajo solo captura la indexación pura o la consulta pura, pero no una combinación de ambas, que es más probable que ocurra en un escenario real como un motor de preguntas y respuestas o un chatbot cuando constantemente llegan nuevos datos.

La distribución de datos cambia con el tiempo.

En la prueba de carga estática, los conjuntos de datos y consultas no cambian. Esto no es realista, ya que los datos y las consultas son impulsados por el interés de los usuarios finales, que cambia con el tiempo. Si los conjuntos de datos y consultas siempre fueran fijos, entonces el mejor índice sería una caché que memoriza cada resultado de consulta. Recientemente, la investigación en índices ANN (por ejemplo, FreshDiskANN) ha comenzado a medir el rendimiento de consultas fuera de distribución, lo cual es un paso adelante.

¿Y qué hay de las eliminaciones?

La API de eliminación se ha vuelto estándar para los índices ANN, pero ninguna prueba de carga estática está midiendo esto. Ser capaz de manejar eliminaciones es importante, ya que los escenarios de aplicación relacionados con la IA emergente, como los chatbots, están utilizando índices ANN como almacenamiento operativo que se asemeja a las bases de datos de procesamiento de transacciones en línea (OLTP), ya que los datos se agregan y modifican constantemente.

2. La carga de trabajo en streaming te dice mucho más.

Si un índice ANN admite las siguientes API:

• Insertar(ID, vector)
• Consultar(vector)
• Borrar(ID)

y si el escenario de uso no es otra cosa que datos y consultas estáticas (como, ¿cada escenario?), entonces una prueba de carga de trabajo en streaming puede brindarte más información sobre las características de los índices ANN y su rendimiento para tu escenario de uso específico.

Una prueba de carga de trabajo en streaming consta de dos flujos: un flujo de datos que corresponde a una secuencia de llamadas API de Insertar y Borrar, y un flujo de consultas para una secuencia de llamadas API de Consultar. Puede realizarse utilizando un sistema de transmisión real como Kafka, o de manera más sencilla utilizando un manual de ejecución con secuencias de referencias a un conjunto de datos y un conjunto de consultas similares a los utilizados por una prueba estática.

El diagrama anterior ilustra la prueba de carga de trabajo en streaming utilizada en los ‘Big ANN Benchmarks’ de NeurIPS 23′. Específicamente, cada paso en el manual de ejecución corresponde a un lote de vectores, por lo que las operaciones se pueden ejecutar en paralelo. Esta aproximación tiene los siguientes beneficios:

1. Flexibilidad: se pueden modelar los distintos patrones de carga de trabajo y los cambios en la distribución de los datos como diferentes pruebas de carga de trabajo en streaming, que luego se compilán en diferentes manuales de ejecución.
2. Realista: la indexación y la consulta se intercalan, por lo que el índice ANN debe adaptarse a las futuras inserciones. Además, el perfil de memoria refleja de manera más precisa la carga de trabajo real.
3. Análisis simple: el rendimiento se puede describir utilizando la producción general en lugar de las producciones de indexación vs. consulta, de manera que se pueda visualizar fácilmente el equilibrio entre precisión y rendimiento.
4. Completo: también se evalúan las operaciones de inserción y borrado.

En esta publicación de blog, profundizaré en el punto (4) anterior y te mostraré una nueva perspectiva que descubrí utilizando una prueba de carga de trabajo en streaming.

Comparar la estabilidad de la precisión: HNSW vs. Vamana

Cuando ejecutamos una prueba de carga de trabajo en streaming, una métrica importante que recopilamos es la precisión de cada operación de consulta. Podemos comparar diferentes configuraciones de índices (parámetros, algoritmos, etc.) observando la estabilidad de su precisión a lo largo del tiempo, y decidir qué índice es adecuado para un escenario de uso determinado.

Medí la estabilidad de la precisión de Vamana de DiskANN y varias implementaciones de HNSW bajo la carga de trabajo en streaming definida por el último manual de ejecución en los ‘Big ANN Benchmarks’ de NeurIPS 23′.

Algunos datos sobre Vamana y HNSW: ambos son índices ANN basados en grafos, y son particularmente buenos para manejar incrustaciones. En un índice ANN basado en grafo, cada vector es un nodo, y la consulta se ejecuta como un recorrido de grafo. Los bordes dirigidos se construyen selectivamente para limitar el uso de memoria al tiempo que garantizan un recorrido rápido desde cualquier nodo hasta cualquier otro. Durante la eliminación en su lugar, para cada nodo vecino de entrada de un nodo eliminado, los índices ANN basados en grafos realizan una reparación de bordes para mantener la estructura de grafo dirigido.

Implementamos HNSW utilizando HNSWLIB y agregamos una API de Borrar implementada utilizando un algoritmo de reparación llamado repairConnectionsForUpdate, que ya forma parte del código fuente de HNSWLIB. La idea es realizar una “reinserción” del nodo que se va a reparar y actualizar a sus vecinos salientes en todos los niveles. La figura siguiente muestra la estabilidad de la precisión a lo largo del tiempo tanto para Vamana como para HNSW.

Tenga en cuenta que configuré el parámetro de grado máximo de Vamana en 40 (R = 40) y el grado máximo de la capa base de HNSW también en 40 (M = 20, M0 = 40). Por lo tanto, deberían utilizar más o menos la misma memoria.

Es claro a partir de este gráfico que las eliminaciones tienen un efecto adverso en la recuperación, ya que la recuperación disminuye monótonamente durante las eliminaciones consecutivas. En comparación, HNSW se ve mucho más afectado por las eliminaciones que Vamana.

La segunda implementación de HNSW que utilizamos reemplaza el algoritmo de reparación de aristas de HNSWLIB con el de Vamana, que es bastante diferente. La idea detrás del algoritmo de reparación de aristas de Vamana es conectar cada vecino de entrada de un nodo eliminado con los vecinos de salida del nodo eliminado, mientras se aplica un paso de poda para mantener una restricción de grado máximo. En este caso, utilizamos el algoritmo de poda original de HNSW. Está implementado por HNSWLIB en una función llamada getNeighborsByHeuristic2.

Con todos los parámetros iguales, cambiar el algoritmo de reparación de aristas de HNSWLIB a Vamana mejoró inmediatamente la estabilidad de recuperación de HNSW.

Vamos un paso más allá y cambiemos el algoritmo de poda de aristas de HNSW por el de Vamana. Ahora el índice de HNSW es casi igual que el de Vamana, excepto que tiene múltiples capas. Llamamos a este índice “Vamana de múltiples capas”.

Puede ver que la recuperación de HNSW es ahora ligeramente mayor que la de Vamana mientras utiliza una cantidad similar de memoria. No he encontrado esta observación en ningún artículo de investigación. Además, aunque el rendimiento no se muestra en la figura, noté una desaceleración significativa al cambiar al algoritmo de poda de Vamana.

En conclusión, al utilizar el benchmark de carga de trabajo en tiempo real, pude descubrir algo nuevo sobre diferentes algoritmos de reparación y poda de aristas. Un paso lógico siguiente sería investigar las implicaciones de rendimiento de estos algoritmos, y puedo hacer esto utilizando el benchmark de carga de trabajo en tiempo real.

3. Conclusion

En resumen, en esta publicación del blog, señalé que los benchmarks de carga de trabajo estáticos son insuficientes para la evaluación realista de los índices de ANN, y describí el benchmark de carga de trabajo en tiempo real que creo que es un reemplazo mejor. También utilicé un benchmark de carga de trabajo específico para descubrir una nueva comparación entre los índices de HNSW y Vamana. ¡Felicitaciones al equipo detrás de los NeurIPS 23′ Big ANN Benchmarks! Ellos han abierto el código fuente del benchmark de carga de trabajo en tiempo real que utilicé en esta publicación del blog.

Necesitamos un TPC-C y TPC-H para bases de datos de vectores.

Todavía hay mucho trabajo por hacer en la evaluación comparativa. El índice de ANN es la característica principal de las bases de datos de vectores y han recaudado más de 350 millones de dólares. Sin embargo, muchos de ellos siguen midiendo el rendimiento utilizando un enfoque obsoleto que ya no refleja los escenarios de uso actuales. Los sistemas de bases de datos pasaron por una etapa similar en los años 90 y principios de los 2000. Luego, se desarrollaron benchmarks estándar como TPC-C y TPC-H y todavía se utilizan en la actualidad. Deberíamos tener algo similar para las bases de datos de vectores.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!