MUVERA - Membuat pencarian multi-vektor secepat pencarian vektor tunggal

• Pencarian berbasis embedding vektor tunggal cepat dan efisien, tetapi belakangan model multi-vektor seperti ColBERT menawarkan makna yang lebih kaya dan akurasi lebih tinggi melalui banyak vektor per token
• Pendekatan multi-vektor secara signifikan meningkatkan jumlah komputasi dan biaya pencarian karena perhitungan kemiripan yang kompleks seperti Chamfer similarity, sehingga menjadi hambatan untuk pencarian real-time berskala besar
• MUVERA yang diusulkan tim riset Google memampatkan informasi multi-vektor menjadi vektor panjang tetap (FDE, Fixed Dimensional Encoding), lalu melakukan pencarian ultra-cepat berbasis MIPS (maximum inner product search) vektor tunggal sebelum re-ranking
• Pendekatan ini independen terhadap data dan memiliki landasan teoretis (jaminan galat aproksimasi Chamfer similarity), mencapai pengurangan latensi lebih dari 90% dan peningkatan recall lebih dari 10% dibanding PLAID
• FDE juga mendukung kompresi (penghematan memori 32x), dan implementasi open source serta makalahnya telah dirilis, sehingga cocok untuk penerapan nyata pada layanan pencarian, rekomendasi, dan NLP

---

Perkembangan model embedding dan information retrieval

• Model embedding berbasis deep learning adalah alat inti untuk dengan cepat menemukan informasi relevan dari dataset besar (dokumen, gambar, video, dll.) terhadap kueri pengguna (misalnya: “berapa tinggi Gunung Everest”)
• Dengan mengubah setiap titik data menjadi embedding vektor tunggal, data yang mirip secara semantik dirancang agar memiliki struktur vektor yang juga mirip secara numerik
• Dengan memanfaatkan perhitungan kemiripan inner product antarvektor, performa pencarian cepat dapat dicapai melalui algoritme maximum inner product search (MIPS)
• Namun belakangan, model multi-vektor seperti ColBERT menarik perhatian karena akurasi pencarian yang lebih tinggi dan kemampuannya memahami hubungan yang lebih kompleks

Adopsi dan keterbatasan model multi-vektor

• Model multi-vektor merepresentasikan setiap titik data sebagai sekumpulan banyak vektor embedding
• Dengan menggunakan fungsi kemiripan gabungan seperti metode pengukuran Chamfer similarity, model ini dapat menangkap dengan tepat informasi dan relasi yang sebelumnya tidak dapat ditangkap oleh vektor tunggal
• Berkat pendekatan ini, information retrieval yang lebih akurat dan rekomendasi dokumen yang lebih relevan menjadi memungkinkan
• Kekurangannya, karena jumlah embedding bertambah dan perhitungan kemiripan menjadi lebih kompleks, sumber daya komputasi yang dibutuhkan untuk pencarian meningkat secara signifikan
  • Jumlah vektor per token bertambah → lonjakan besar pada komputasi dan memori
  • Operasi nonlinear (perkalian matriks) wajib dilakukan → pencarian sublinear (ultra-cepat) berbasis vektor tunggal tidak memungkinkan
  • Saat diterapkan pada layanan berskala besar, biaya dan latensi meningkat tajam

MUVERA: inovasi pencarian multi-vektor dengan FDE

• Makalah “MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings” mengusulkan algoritme baru untuk mengatasi masalah efisiensi ini
• MUVERA mengubah informasi multi-vektor menjadi satu vektor FDE, sehingga pencarian kandidat berkecepatan tinggi dapat dilakukan dengan tetap memanfaatkan indeks/server MIPS yang ada
  1. Pembuatan FDE: mengubah kumpulan multi-vektor kueri dan dokumen menjadi vektor panjang tetap (FDE) (pemetaan yang independen terhadap data)
  2. Pencarian MIPS: menyimpan FDE semua dokumen dalam indeks MIPS, lalu menelusuri kandidat dengan sangat cepat menggunakan FDE kueri
  3. Re-ranking dengan jaminan akurasi: hanya pada dokumen kandidat diterapkan operasi multi-vektor asli seperti Chamfer similarity, lalu hasil akhir diberikan melalui re-ranking presisi tinggi
• FDE dapat diterapkan tanpa bergantung pada dataset, sehingga juga menguntungkan untuk lingkungan dinamis seperti streaming

Landasan teoretis

• Terinspirasi dari algoritme geometri tingkat lanjut seperti probabilistic tree embedding, FDE memberikan aproksimasi yang kuat terhadap kemiripan multi-vektor
• Ruang embedding dipartisi secara acak, dan jika vektor kueri/dokumen berada di bagian yang sama maka kemiripan aproksimasi dihitung
• Makalah ini menyajikan teori dan data eksperimen tentang jaminan berada dalam rentang galat aproksimasi Chamfer similarity

Hasil eksperimen dan performa

• Kinerja MUVERA divalidasi pada berbagai dataset IR berskala besar seperti benchmark BEIR
  • Mencapai recall rata-rata 10% lebih tinggi dibanding metode sebelumnya seperti PLAID
  • Latensi pencarian berkurang lebih dari 90%
  • Pada recall yang sama, jumlah dokumen kandidat berbasis FDE berkurang 5 hingga 20 kali dibanding sebelumnya
  • Sangat cocok digabungkan dengan teknik kompresi tambahan seperti Product Quantization (penghematan memori 32x)
• Kepraktisan pencarian multi-vektor meningkat drastis, sehingga cocok untuk aplikasi pencarian, rekomendasi, dan NLP berskala besar

Kesimpulan dan pemanfaatan

• MUVERA adalah pendekatan inovatif yang mempercepat pencarian multi-vektor hingga setara tingkat vektor tunggal
• Implementasi open source (tautan GitHub), makalah, dan hasil eksperimennya semuanya telah dipublikasikan
• Mesin pencari, sistem rekomendasi, pemrosesan bahasa alami, dan lain-lain dapat memanfaatkannya sebagai alternatif praktis untuk mengefisienkan pencarian multi-vektor berskala besar
• Jika riset dan optimasi lanjutan terus ditambahkan, pendekatan ini diharapkan dapat diterapkan lebih luas lagi di berbagai industri

[GN⁺]

Opini Hacker News

• Berbagi pengalaman baru-baru ini menambahkan Muvera ke Weaviate, sekaligus membagikan tautan blog dan podcast. Disebutkan bahwa dalam pendekatan multi-vector bergaya ColBERT, jika embedding dibuat untuk setiap token, biayanya melonjak drastis. Misalnya, alih-alih vektor 768 dimensi yang umum, ukurannya bisa membesar hingga lebih dari 16.640 dimensi, sehingga menjadi beban yang tidak realistis dalam banyak situasi. Muvera mengubah beberapa vektor menjadi satu vektor berdimensi tetap, biasanya dengan jumlah dimensi yang lebih kecil, sehingga bisa langsung digunakan di ANN index apa pun. Karena memakai satu vektor, algoritme yang sudah ada dan berbagai teknik quantization juga bisa diterapkan, sehingga menghemat memori. Tidak seperti PLAID, pendekatan ini tidak memerlukan struktur index tertentu atau asumsi clustering, sehingga latensinya juga lebih rendah

• Disebutkan adanya tren belakangan ini untuk menjauh dari pendekatan flattening melalui mean-pooling menjadi satu embedding. Karena terlalu banyak vektor jika semua embedding per token ditangani, dibutuhkan cara untuk menguranginya secara tepat. Metode ini mengelompokkan embedding token ke dalam partisi acak, melakukan mean-pooling pada masing-masing, lalu menggabungkannya menjadi embedding panjang tetap. Karena perbandingan multi-vector penuh sulit dari sisi performa, embedding dikelompokkan menjadi k vektor lalu digabungkan agar bisa dibandingkan dalam kerangka alat dan performa single-vector. Hasilnya, karena jumlah partisi ditetapkan, muncul efek clustering embedding token bergaya k-means. Jika token dikelompokkan secara dinamis, mungkin bisa menghasilkan embedding dengan jumlah variabel dan berpotensi memberi hasil yang lebih baik

• Dibagikan pengalaman bahwa metode ini sangat sensitif terhadap hyperparameter, dan dalam eksperimennya sendiri tidak bisa mencapai performa yang mirip dengan maxsim

• Dipahami bahwa Muvera menghitung FDE (Fixed Dimensional Embedding) untuk query lalu mencari FDE yang mirip di dataset model; jika demikian, ditanyakan apakah semua FDE berukuran sama untuk seluruh model juga harus dihitung

  • Dijelaskan bahwa pekerjaan itu cukup dilakukan sekali saat data dimuat, dan setelah itu pencarian bisa diproses sebagai MIPS (Maximum Inner Product Search) terhadap FDE yang sudah dihitung sebelumnya

• Ada pertanyaan dari seseorang yang tidak terlalu memahami bidang ini: apakah query neural embedding bekerja seperti query SQL yang mengembalikan semua nama dari sebuah tabel, atau apakah hasilnya menjadi lebih ambigu

• Ringkasan pendekatan ini pada dasarnya adalah memampatkan beberapa embedding menjadi satu, yaitu semacam “embedding of embeddings”, untuk menurunkan dimensi dan meningkatkan performa. Karena beberapa embedding membawa informasi yang sangat tumpang tindih, jika bisa dipadatkan menjadi satu maka nilai tambahan dari embedding ekstra dinilai kebanyakan rendah. Jika performanya mirip, dari sudut pandang teori informasi muncul pertanyaan apakah representasi itu bisa dilakukan tanpa kehilangan informasi

  • Dijelaskan bahwa pendapat mengenai rendahnya manfaat marjinal dari embedding tambahan adalah inti dari makalah tersebut, dan argumennya adalah bahwa satu vektor embedding bisa cukup sparse sehingga mampu memuat informasi dari vektor tambahan secara efektif sekaligus meningkatkan performa pencarian

• Ditanyakan apa perbedaannya dengan metode feature hash yang sudah ada untuk mereduksi beberapa embedding menjadi satu, dan apakah teknik reduksi dimensi single-vector seperti UMAP dapat membantu

  • Ditunjukkan bahwa UMAP tidak memproyeksikan nilai ke ruang koordinat yang sama; posisinya di koordinat berubah, sehingga walaupun karakteristik abstraknya mirip, hasil aktual pada koordinatnya bisa berbeda