MUVERA: hacer que la búsqueda multivector sea tan rápida como la de un solo vector

• La búsqueda basada en embeddings de un solo vector es rápida y eficiente, pero recientemente los modelos multivector como ColBERT ofrecen un significado más rico y mayor precisión con múltiples vectores por token
• El enfoque multivector aumenta mucho el volumen de cómputo y el costo de búsqueda debido a cálculos de similitud complejos como Chamfer similarity, lo que se convierte en un obstáculo para la búsqueda en tiempo real a gran escala
• MUVERA, propuesto por el equipo de investigación de Google, comprime la información multivector en vectores de longitud fija (FDE, Fixed Dimensional Encoding) y luego realiza una búsqueda ultrarrápida con MIPS (búsqueda de máximo producto interno) basada en un solo vector antes de reordenar los resultados
• Este método es independiente de los datos y ofrece una base teórica (garantía del error de aproximación de Chamfer similarity), logrando más de un 90% de reducción en latencia y más de un 10% de mejora en recall frente a PLAID
• FDE también admite compresión (hasta 32 veces menos memoria), y tanto la implementación open source como el paper ya están disponibles, por lo que es apto para adoptarse en servicios reales de búsqueda, recomendación y NLP

---

Evolución de los modelos de embedding y la recuperación de información

• Los modelos de embedding basados en deep learning son una herramienta clave para encontrar rápidamente información relacionada dentro de conjuntos de datos masivos (documentos, imágenes, video, etc.) ante consultas de usuario (por ejemplo, “altura del monte Everest”)
• Al convertir cada punto de datos en un embedding de un solo vector, se diseña el sistema para que los datos semánticamente similares tengan estructuras vectoriales numéricamente parecidas
• Aprovechando el cálculo de similitud por producto interno entre vectores, se logra un rendimiento de búsqueda rápido mediante algoritmos de MIPS (Maximum Inner Product Search)
• Sin embargo, recientemente los modelos multivector como ColBERT han llamado la atención por su mayor precisión de búsqueda y su capacidad para captar relaciones complejas

Adopción y límites de los modelos multivector

• Los modelos multivector representan cada punto de datos como un conjunto de múltiples vectores de embedding
• Usan funciones de similitud compuestas como la medición de Chamfer similarity para capturar con precisión información y relaciones que los vectores únicos tradicionales no podían detectar
• Gracias a este enfoque, es posible lograr una recuperación de información más precisa y recomendaciones de documentos con mayor relevancia
• Como desventaja, el aumento en la cantidad de embeddings y la complejidad del cálculo de similitud elevan considerablemente los recursos de cómputo requeridos para la búsqueda
  • Más vectores por token → gran aumento en cómputo y memoria
  • Operaciones no lineales (multiplicación de matrices) obligatorias → imposibilidad de usar búsqueda sublineal (ultrarrápida) basada en un solo vector
  • Al aplicarlo en servicios a gran escala, se disparan el costo y la latencia

MUVERA: innovación en la búsqueda multivector con FDE

• El paper “MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings” propone un nuevo algoritmo para superar este problema de eficiencia
• MUVERA convierte la información multivector en un solo vector FDE, lo que permite reutilizar directamente los índices y servidores MIPS existentes para una búsqueda rápida de candidatos
  1. Generación de FDE: convierte los conjuntos multivector de consultas y documentos en vectores de longitud fija (FDE) mediante un mapeo independiente de los datos
  2. Búsqueda MIPS: almacena los FDE de todos los documentos en un índice MIPS y explora candidatos a gran velocidad usando el FDE de la consulta
  3. Reordenamiento con garantía de precisión: aplica operaciones multivector originales como Chamfer similarity solo a los documentos candidatos y entrega el resultado final con un reordenamiento preciso
• FDE puede aplicarse sin depender del dataset, por lo que también resulta favorable en entornos dinámicos como streaming

Base teórica

• Inspirado en algoritmos geométricos avanzados como el probabilistic tree embedding, FDE aproxima con solidez la similitud multivector
• El espacio de embeddings se divide aleatoriamente, y cuando los vectores de consulta/documento quedan ubicados en la misma sección, se calcula la similitud aproximada
• El paper presenta teoría y datos experimentales que garantizan el error de aproximación dentro de un rango para Chamfer similarity

Resultados experimentales y rendimiento

• Se validó el rendimiento de MUVERA en diversos datasets masivos de IR, incluido el benchmark BEIR
  • Frente a PLAID y otros métodos existentes, logró en promedio 10% más recall
  • Más de 90% de reducción en latencia de búsqueda
  • Con el mismo recall, reduce entre 5 y 20 veces la cantidad de documentos candidatos basada en FDE frente a métodos previos
  • También combina bien con técnicas adicionales de compresión como Product Quantization (32 veces menos memoria)
• Mejora ampliamente la viabilidad práctica de la búsqueda multivector y resulta apto para aplicaciones de búsqueda, recomendación y NLP a gran escala

Conclusión y uso

• MUVERA es un enfoque innovador que acelera la búsqueda multivector hasta un nivel comparable al de un solo vector
• Ya se publicaron la implementación open source (enlace de GitHub), el paper y los resultados experimentales
• Es una alternativa práctica para mejorar la eficiencia de la búsqueda multivector a gran escala en motores de búsqueda, sistemas de recomendación y procesamiento de lenguaje natural
• Si en el futuro se le suman más investigaciones y optimizaciones, se espera que pueda aplicarse en un abanico industrial todavía más amplio

[GN⁺]

Opiniones en Hacker News

• Presentación de la experiencia reciente al agregar Muvera a Weaviate, junto con enlaces al blog y al podcast. Se menciona que, en el enfoque multi-vector estilo ColBERT, si se hace embedding por token, el costo se dispara. Por ejemplo, en lugar de un vector tradicional de 768 dimensiones, puede crecer hasta 16,640 dimensiones o más, lo que en muchas situaciones representa una carga poco realista. Muvera convierte varios vectores en un solo vector de dimensión fija, generalmente con menos dimensiones, que puede usarse directamente en cualquier índice ANN. Gracias al uso de un solo vector, se pueden aplicar algoritmos existentes y diversas técnicas de cuantización, con ahorro de memoria. A diferencia de PLAID, no requiere una estructura de índice específica ni supuestos de clustering, por lo que también destaca por tener menor latencia

• Se menciona una tendencia reciente de alejarse del enfoque de aplanar mediante mean-pooling para crear un solo embedding. Como manejar todos los embeddings por token genera demasiados vectores, se señala la necesidad de una forma adecuada de reducirlos. Este método agrupa los embeddings de tokens mediante particiones arbitrarias, aplica mean-pooling a cada grupo y luego los concatena para formar un embedding de longitud fija. Como la comparación multi-vector completa es difícil en términos de rendimiento, se agrupan en k vectores y se concatenan para poder compararlos en la misma categoría de herramientas y rendimiento que los métodos de vector único. En consecuencia, al fijar el número de particiones, se obtiene un efecto de clustering de embeddings de tokens al estilo k-means. También se plantea que, si los tokens se agruparan dinámicamente, podrían obtenerse embeddings con número variable de componentes y quizás mejores resultados

• Se comparte la experiencia de que este método era muy sensible a los hiperparámetros y que, en sus experimentos, no logró un rendimiento parecido al de maxsim

• Se entiende que Muvera calcula el FDE (Fixed Dimensional Embedding) de la consulta y luego busca FDE similares en el dataset del modelo, y se pregunta si eso significa que también hay que calcular todos los FDE del mismo tamaño para el modelo

  • Sin embargo, se explica que ese trabajo solo debe hacerse una vez al cargar los datos, y que después la búsqueda puede procesarse sobre los FDE precalculados mediante MIPS (Maximum Inner Product Search)

• Aunque no conoce mucho este campo, se pregunta si una consulta con embeddings neuronales funciona de la misma manera que una consulta SQL que devuelve todos los nombres de una tabla, o si los resultados terminan siendo más ambiguos

• Se resume este enfoque como una forma de comprimir varios embeddings en uno solo, es decir, un “embedding de embeddings”, para reducir dimensión y mejorar el rendimiento. Como varios embeddings contienen información que se solapa en gran medida, se considera que si es posible comprimirlos en uno solo, el valor adicional que aportan los embeddings extra probablemente sea bajo. Si el rendimiento es parecido, surge la duda de si, desde la teoría de la información, esto podría representarse sin pérdida

  • Se señala que la baja utilidad marginal de los embeddings adicionales es justamente el núcleo del artículo, y se explica que la idea es que un solo vector de embedding puede ser lo suficientemente disperso como para incorporar de forma efectiva la información adicional de otros vectores y así mejorar el rendimiento de búsqueda

• Se pregunta en qué se diferencia de los métodos tradicionales de feature hash, que también reducen varios embeddings a uno, y si técnicas de reducción de dimensionalidad para vector único como UMAP podrían ayudar

  • Se apunta que UMAP no proyecta los valores en el mismo espacio de coordenadas, y que, por eso, aunque las características abstractas sean similares, los resultados en las coordenadas reales pueden ser distintos