Mengapa HNSW Bukan Jawaban untuk Database Vektor

HNSW (Hierarchical Navigable Small World) telah menjadi algoritma yang digunakan untuk banyak database vektor. Struktur grafik berlapis-lapis dan kemampuannya menavigasi penyematan vektor secara efisien membuatnya sangat menarik. Namun, terlepas dari kelebihannya, HNSW mungkin bukan solusi optimal untuk pencarian kemiripan vektor berskala besar dan dinamis. Dalam postingan blog ini, kami menantang dominasi HNSW dan mengeksplorasi mengapa alternatif berbasis disk, seperti IVF (Inverted File Index), mungkin lebih praktis untuk kumpulan data yang sangat besar.

Banding HNSW

HNSW menawarkan beberapa keunggulan:

• Pencarian Efisien: Struktur berbasis grafiknya memungkinkan pencarian tetangga terdekat dengan cepat, terutama untuk kumpulan data yang lebih kecil.

• Pembaruan Tambahan: Kemampuan untuk menambahkan vektor baru secara bertahap tanpa perlu membangun kembali indeks merupakan keuntungan besar bagi lingkungan dinamis.

• Ingatan Tinggi: HNSW memberikan recall yang tinggi dengan latensi yang relatif rendah, menjadikannya pilihan ideal untuk aplikasi real-time.

Namun, manfaat ini disertai dengan trade-off yang menjadi lebih nyata seiring bertambahnya ukuran kumpulan data.

Masalah HNSW

Salah satu tantangan utama HNSW adalah ketergantungannya yang signifikan pada memori untuk operasi pengindeksan dan pencarian. Berikut adalah permasalahan utama yang muncul:

• Memori Overhead: Melintasi struktur grafik HNSW melibatkan pola akses yang sangat acak. Seluruh kumpulan data harus disimpan dalam memori untuk mencapai kinerja yang wajar. Hal ini menjadi tidak mungkin dilakukan untuk kumpulan data berskala besar dengan miliaran vektor berdimensi tinggi karena kebutuhan memori yang terlalu tinggi.

• Sensitivitas Kinerja terhadap Ukuran Memori: Kinerja HNSW menurun tajam jika memori tidak mencukupi untuk menampung semua vektor. Dalam kasus seperti ini, menukar data ke disk secara drastis berdampak pada kecepatan pencarian, sehingga tidak praktis untuk sistem dengan memori terbatas.

• Ketidaksesuaian untuk Lingkungan Berbasis Disk: HNSW pada dasarnya dirancang untuk operasi dalam memori dan berkinerja buruk dalam skenario berorientasi disk, seperti PostgreSQL. Ketergantungannya pada pola akses acak yang sering membuatnya tidak kompatibel dengan sifat akses berurutan dari penyimpanan disk.

• Biaya Penyisipan dan Penghapusan: Memperbarui indeks di HNSW melibatkan modifikasi berjenjang di seluruh grafik, yang menghasilkan komputasi dan amplifikasi penulisan yang signifikan. Hal ini membuat operasi penyisipan dan penghapusan menjadi lambat dan menghabiskan banyak sumber daya.

Sebaliknya, solusi berbasis disk seperti IVF unggul dalam skenario yang memerlukan skalabilitas dan efisiensi dengan biaya kompleksitas minimal.

Mengapa IVF Bisa Lebih Cepat Dibanding HNSW

Pengamatan penting di semua algoritma pencarian vektor adalah bahwa kinerjanya sebagian besar bergantung pada jumlah perhitungan jarak yang dilakukannya. Meminimalkan komputasi ini penting untuk meningkatkan kecepatan pencarian. Meskipun indeks IVF asli memerlukan pemindaian 1% hingga 5% dari total vektor, kemajuan modern dalam kuantisasi dan optimalisasi telah meningkatkan efisiensinya secara signifikan, menjadikan IVF sebagai pesaing kuat HNSW.

Kuantisasi: Pengubah Permainan

Kuantisasi memampatkan vektor berdimensi tinggi menjadi representasi yang ringkas. Misalnya:

• RaBitQ: Memanfaatkan konsentrasi fenomena ukuran untuk meningkatkan akurasi kuantisasi biner dan skalar, mengkuantisasi setiap dimensi menjadi 1 bit untuk rasio kompresi 32x.

• Kuantisasi Produk (PQ): Bekerja dengan membagi ruang vektor menjadi subruang, mengkuantisasi setiap subruang secara independen untuk meminimalkan kesalahan perkiraan. Metode ini menawarkan rasio kompresi yang fleksibel dari 4x hingga 64x di FAISS, memungkinkan kompresi yang lebih halus dan pencarian perkiraan yang lebih cepat.

• Kuantisasi Skalar (SQ): Mengkuantisasi setiap dimensi vektor secara independen dengan membagi rentangnya menjadi tingkat diskrit, biasanya mencapai rasio kompresi 4x dengan mengonversi dari float ke int8.

• Pemindaian: Menggunakan kuantisasi vektor anisotropik untuk mengoptimalkan keakuratan produk dalam dengan memberikan penalti terhadap kesalahan dalam arah yang berdampak pada produk dalam yang tinggi, sehingga mencapai perolehan dan kecepatan yang unggul.

Kuantisasi mengurangi penggunaan memori dan ruang disk secara signifikan—sering kali hingga 32x saat mengonversi float menjadi bit—sambil menurunkan overhead komputasi secara drastis. Meskipun ada beberapa kehilangan presisi, kuantisasi membuat perbandingan vektor jauh lebih efisien. Misalnya, kompleksitas komputasi jarak yang umum antara dua vektor berdimensi D adalah O(D^2), namun mengompresi float menjadi bit akan menguranginya dengan faktor 1024 (32×32). Dengan optimasi pemindaian cepat, komputasi ini semakin dipercepat melalui pencarian register CPU yang efisien. Dikombinasikan dengan IVF, banyak metode kuantisasi yang secara konsisten mengungguli HNSW dalam hal kecepatan dan skalabilitas. Alur kerja yang khas melibatkan:

1. Pencarian Awal: Memanfaatkan representasi terkompresi untuk mengidentifikasi kandidat vektor dengan cepat.

2. Pemeringkatan ulang: Menyempurnakan hasil menggunakan penghitungan jarak presisi penuh pada subkumpulan kandidat yang lebih kecil.

Membandingkan RaBitQ+IVF dan HNSW

IVF dengan kuantisasi menyediakan cara yang sangat efisien untuk menyimpan semua vektor terkuantisasi dalam memori. Dengan memanfaatkan RaBitQ, penggunaan memori berkurang 32 kali lipat dibandingkan dengan vektor ukuran penuh, sehingga seluruh kumpulan data terkuantisasi dapat masuk ke dalam memori. Desain ini memungkinkan indeks dengan cepat mengambil perkiraan tetangga terdekat menggunakan vektor bit dan menyusun ulang peringkatnya dengan vektor presisi penuh yang diambil dari disk. Untuk kueri Top-10 pada umumnya, IVF hanya mengambil 100-200 vektor dari disk, dibandingkan dengan HNSW, yang mungkin memerlukan 800-1000 vektor. Pendekatan efisien ini mencapai keseimbangan optimal antara penggunaan memori dan akses disk, sehingga menawarkan manfaat kinerja biaya yang luar biasa.

Meskipun teknik kuantisasi serupa secara teoritis dapat diterapkan pada HNSW, kendala praktis mengurangi efektivitasnya:

• Pengepakan Vektor: Pengoptimalan pemindaian cepat bergantung pada pengemasan 32 vektor terkompresi secara bersamaan, yang tidak kompatibel dengan struktur grafik HNSW.

• Biaya Akses Acak: HNSW melibatkan akses acak yang sering terjadi di seluruh node dan tepi grafik, sehingga membuat traversal menjadi tidak efisien. Sebaliknya, IVF mengatur vektor secara berurutan dalam daftar postingan, memungkinkan pengambilan awal yang lebih cepat dan pemindaian berurutan yang efisien.

• Biaya Pemeringkatan Ulang: Baik IVF dan HNSW memiliki biaya komputasi pemeringkatan ulang yang serupa karena ketergantungan mereka pada representasi terkuantisasi pada tahap pertama.

Pada akhirnya, perbedaan kinerja antara IVF terkuantisasi dan HNSW kemungkinan kecil, namun IVF menonjol karena kesederhanaan dan efisiensinya.

Kesederhanaan Operasional IVF

Kesederhanaan IVF menjadikannya pilihan yang lebih praktis untuk aplikasi dunia nyata:

• Penyisipan dan Penghapusan: Di HNSW, operasi ini memicu modifikasi berjenjang di seluruh grafik, sehingga menghasilkan komputasi dan amplifikasi tulis yang signifikan. Sebaliknya, IVF hanya memerlukan pembaruan daftar posting yang relevan.

• Penyimpanan Berbasis Disk: Ketergantungan IVF pada pengindeksan berbasis disk memungkinkannya melakukan penskalaan secara efisien tanpa biaya memori mahal yang terkait dengan HNSW.

• Kemampuan beradaptasi: IVF dapat dengan mudah dikombinasikan dengan teknik kuantisasi tingkat lanjut, sehingga memungkinkan pengoptimalan lebih lanjut.

Kesimpulan

Meskipun HNSW telah memperkuat reputasinya sebagai algoritma yang cepat dan akurat untuk pencarian kesamaan vektor, hal ini bukannya tanpa keterbatasan. Sifatnya yang intensif memori dan kompleksitas operasional membuatnya kurang cocok untuk aplikasi skala besar. Sebaliknya, IVF menawarkan alternatif yang terukur dan hemat biaya, terutama bila dipadukan dengan teknik kuantisasi modern.

Karena permintaan pencarian vektor terus meningkat, para praktisi harus hati-hati mengevaluasi trade-off antara solusi berbasis memori dan berbasis disk. HNSW mungkin mendominasi aplikasi skala kecil hingga menengah, namun untuk kumpulan data yang sangat besar, inilah saatnya untuk melihat lebih jauh dari HNSW dan menerapkan pendekatan yang lebih sederhana dan terukur seperti IVF.