MUVERA – Multi-Vektor-Suche so schnell wie auf Single-Vektor-Niveau

• Suche auf Basis von Single-Vektor-Embeddings ist schnell und effizient, aber neuere Multi-Vektor-Modelle wie ColBERT liefern mit vielen Vektoren pro Token reichhaltigere Semantik und höhere Genauigkeit
• Der Multi-Vektor-Ansatz erhöht jedoch durch komplexe Ähnlichkeitsberechnungen wie Chamfer Similarity den Rechenaufwand und die Suchkosten erheblich und stellt damit ein Hindernis für großskalige Echtzeitsuche dar
• Das von Google Research vorgeschlagene MUVERA komprimiert Multi-Vektor-Informationen in Vektoren fester Länge (FDE, Fixed Dimensional Encoding), führt damit eine ultraschnelle Suche per MIPS (Maximum Inner Product Search) auf Single-Vektor-Basis durch und sortiert die Ergebnisse anschließend neu
• Der Ansatz ist datenunabhängig und theoretisch fundiert (garantierte Approximationsfehler für Chamfer Similarity) und erreicht gegenüber PLAID über 90 % weniger Latenz bei zugleich mehr als 10 % höherem Recall
• FDE unterstützt auch Kompression (32-fache Speicherersparnis), und eine Open-Source-Implementierung sowie das Paper sind veröffentlicht, was den Ansatz für produktive Such-, Empfehlungs- und NLP-Dienste geeignet macht

---

Die Entwicklung von Embedding-Modellen und Information Retrieval

• Deep-Learning-basierte Embedding-Modelle sind ein zentrales Werkzeug, um für Nutzeranfragen (z. B. „Wie hoch ist der Mount Everest?“) schnell relevante Informationen in großen Datensätzen (Dokumente, Bilder, Videos usw.) zu finden
• Durch die Umwandlung jedes Datenpunkts in ein Single-Vektor-Embedding werden semantisch ähnliche Daten so modelliert, dass sie auch numerisch eine ähnliche Vektorstruktur aufweisen
• Mithilfe der Inner-Product-Ähnlichkeitsberechnung liefern Algorithmen für Maximum Inner Product Search (MIPS) schnelle Suchleistung
• Neuere Multi-Vektor-Modelle wie ColBERT erhalten jedoch Aufmerksamkeit, weil sie höhere Suchgenauigkeit und ein besseres Verständnis komplexer Beziehungen ermöglichen

Einführung und Grenzen von Multi-Vektor-Modellen

• Multi-Vektor-Modelle stellen jeden Datenpunkt als Menge vieler Embedding-Vektoren dar
• Mit komplexen Ähnlichkeitsfunktionen wie der Chamfer-Ähnlichkeit erfassen sie Informationen und Beziehungen präzise, die mit bisherigen Single-Vektor-Ansätzen nicht erkannt werden konnten
• Dadurch werden präzisere Informationssuche und stärker relevante Dokumentenempfehlungen möglich
• Der Nachteil ist, dass durch die größere Zahl an Embeddings und die komplexere Ähnlichkeitsberechnung die für die Suche benötigten Rechenressourcen stark ansteigen
  • Mehr Vektoren pro Token → deutlich höherer Rechen- und Speicherbedarf
  • Nichtlineare Operationen (Matrixmultiplikation) sind erforderlich → keine sublineare (ultraschnelle) Suche auf Single-Vektor-Basis möglich
  • Bei Einsatz in großskaligen Diensten steigen Kosten und Latenz stark an

MUVERA: Revolution der Multi-Vektor-Suche mit FDE

• Das Paper “MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings” schlägt einen neuen Algorithmus vor, um dieses Effizienzproblem zu überwinden
• MUVERA wandelt Multi-Vektor-Informationen in einen einzelnen FDE-Vektor um und kann damit bestehende MIPS-Indizes und -Server unverändert für eine schnelle Kandidatensuche nutzen
  1. FDE-Erzeugung: Die Multi-Vektor-Mengen von Anfrage und Dokument werden in Vektoren fester Länge (FDE) umgewandelt (datenunabhängiges Mapping)
  2. MIPS-Suche: Die FDEs aller Dokumente werden in einem MIPS-Index gespeichert, und mit dem Anfrage-FDE werden Kandidaten ultraschnell gesucht
  3. Neurangierung mit garantierter Genauigkeit: Nur auf die Kandidatendokumente werden wieder die ursprünglichen Multi-Vektor-Operationen wie Chamfer Similarity angewendet, um die Endergebnisse präzise neu zu sortieren
• FDE kann unabhängig vom Datensatz eingesetzt werden und ist auch in dynamischen Umgebungen wie Streaming von Vorteil

Theoretische Grundlage

• Inspiriert von fortgeschrittenen geometrischen Algorithmen wie probabilistischem Tree Embedding approximiert FDE Multi-Vektor-Ähnlichkeiten sehr effektiv
• Der Embedding-Raum wird zufällig partitioniert; befinden sich Anfrage- und Dokumentvektoren im selben Abschnitt, wird eine approximierte Ähnlichkeit berechnet
• Das Paper präsentiert Theorie und experimentelle Daten mit Garantien innerhalb einer Fehlergrenze für die Approximation der Chamfer Similarity

Experimentelle Ergebnisse und Leistung

• Die Leistung von MUVERA wurde auf verschiedenen großen IR-Datensätzen wie dem BEIR-Benchmark evaluiert
  • Gegenüber bestehenden Verfahren wie PLAID wurde im Durchschnitt ein um 10 % höherer Recall erreicht
  • Über 90 % geringere Suchlatenz
  • Bei gleichem Recall ließ sich die Zahl der FDE-basierten Kandidatendokumente im Vergleich zu bisherigen Verfahren um das 5- bis 20-Fache reduzieren
  • Auch in Kombination mit zusätzlichen Kompressionstechniken wie Product Quantization sehr gut geeignet (32-fache Speicherersparnis)
• Die Praxistauglichkeit der Multi-Vektor-Suche verbessert sich damit erheblich, was den Ansatz für großskalige Such-, Empfehlungs- und NLP-Anwendungen geeignet macht

Fazit und Einsatzmöglichkeiten

• MUVERA ist ein innovativer Ansatz, der Multi-Vektor-Suche auf Single-Vektor-Niveau beschleunigt
• Open-Source-Implementierung (GitHub-Link), Paper und experimentelle Ergebnisse sind vollständig veröffentlicht
• Für Suchmaschinen, Empfehlungssysteme und Natural Language Processing bietet der Ansatz eine praktische Alternative zur Effizienzsteigerung bei großskaliger Multi-Vektor-Suche
• Mit weiterer Forschung und Optimierung dürfte eine Anwendung in noch breiteren industriellen Einsatzfeldern zu erwarten sein

[GN⁺]

Hacker-News-Kommentare

• Vorstellung der jüngsten Erfahrung, Muvera zu Weaviate hinzugefügt zu haben, sowie Verweise auf den Blog und den Podcast. Erwähnt wird das Kostenproblem beim ColBERT-artigen Multi-Vector-Ansatz, wenn für jedes Token ein Embedding erzeugt wird. Statt eines bisherigen 768-dimensionalen Vektors kann dies beispielsweise auf bis zu 16.640 Dimensionen oder mehr anwachsen, was in vielen Situationen eine unrealistische Belastung darstellt. Muvera wandelt mehrere Vektoren in einen einzelnen Vektor mit fester Dimension um, in der Regel mit weniger Dimensionen, sodass er direkt in jedem ANN-Index verwendet werden kann. Durch die Nutzung eines einzelnen Vektors lassen sich bestehende Algorithmen und verschiedene Quantisierungstechniken anwenden, was Speicher spart. Im Gegensatz zu PLAID werden weder eine bestimmte Indexstruktur noch Clustering-Annahmen benötigt, was auch geringere Latenzen als Vorteil hat

• Erwähnt wird ein jüngerer Trend weg vom Flattening per Mean-Pooling zu einem einzelnen Embedding. Da es zu viele Vektoren wären, alle Token-Embeddings einzeln zu behandeln, sei eine geeignete Reduktion nötig. Diese Methode clustert Token-Embeddings per zufälliger Partitionierung, führt für jede Partition Mean-Pooling durch und verkettet die Ergebnisse anschließend zu einem Embedding fester Länge. Da ein vollständiger Multi-Vector-Vergleich leistungstechnisch schwierig ist, werden die Token-Embeddings in k Vektoren geclustert und dann verkettet, damit sie hinsichtlich Performance mit Single-Vector-Tools verglichen werden können. Im Ergebnis wird die Anzahl der Partitionen fixiert, was einem k-means-artigen Clustering-Effekt für Token-Embeddings entspricht. Es wird auch angemerkt, dass dynamisches Clustering der Tokens Embeddings mit variabler Anzahl erzeugen könnte und damit möglicherweise bessere Resultate erlaubt

• Geteilt wird die Erfahrung, dass diese Methode sehr empfindlich gegenüber Hyperparametern war und in eigenen Experimenten keine Leistung ähnlich zu maxsim erreichte

• Es wurde so verstanden, dass Muvera die FDE (Fixed Dimensional Embedding) einer Query berechnet und dann im Modelldatensatz nach ähnlichen FDEs sucht; gefragt wird daher, ob man dann auch für alle Modelle FDEs derselben Größe berechnen müsse

  • Dazu wird erklärt, dass diese Arbeit nur einmal beim Laden der Daten nötig ist und die Suche danach per MIPS (Maximum Inner Product Search) auf den vorab berechneten FDEs erfolgen kann

• Jemand merkt an, mit diesem Gebiet nicht gut vertraut zu sein, und fragt, ob neuronale Embedding-Queries ähnlich funktionieren wie eine SQL-Abfrage, die alle Namen einer Tabelle zurückgibt, oder ob die Ergebnisse eher unschärfer werden

• Zusammenfassung des Ansatzes als im Wesentlichen ein Verdichten mehrerer Embeddings zu einem einzigen, also eine Art „Embedding von Embeddings“, um die Dimensionalität zu senken und die Performance zu steigern. Da mehrere Embeddings stark überlappende Informationen enthalten, wird vermutet, dass zusätzliche Embeddings meist nur geringen Mehrwert bringen, falls eine Kompression in ein einziges Embedding möglich ist. Falls die Leistung ähnlich bleibt, wird aus informations­theoretischer Sicht gefragt, ob die Darstellung möglicherweise verlustfrei sein könnte

  • Es wird darauf hingewiesen, dass die geringe Grenznützlichkeit zusätzlicher Embeddings den Kern des Papers ausmacht und dass ein einzelner Embedding-Vektor hinreichend spärlich sein kann, um zusätzliche Vektorinformation wirksam mit aufzunehmen und so die Retrieval-Performance zu verbessern

• Gefragt wird nach dem Unterschied zu bestehenden Feature-Hash-Methoden, die mehrere Embeddings auf eines reduzieren, und ob Verfahren zur Dimensionsreduktion eines einzelnen Vektors wie UMAP hilfreich sein könnten

  • Es wird angemerkt, dass UMAP Werte nicht in denselben Koordinatenraum projiziert und sich daher die Positionen im Koordinatensystem ändern; abstrakte Eigenschaften mögen ähnlich sein, die tatsächlichen Ergebnisse im Koordinatenraum können jedoch unterschiedlich ausfallen