Pengantar Singkat tentang Indeks ScaNN

ScaNN merupakan jawaban Google terhadap tantangan yang sudah tidak asing lagi dalam pencarian vektor berskala besar: bagaimana cara meningkatkan throughput kueri dan mengurangi penggunaan memori tanpa mengorbankan kualitas hasil. Secara konseptual, ScaNN dimulai dari resep klasik IVF+PQ-pengelompokan kasar ditambah kuantisasi produk yang agresif-tetapi melapisi dua inovasi penting yang secara signifikan menggeser batas kinerja:

• Tujuan kuantisasi yangsadar skor yang lebih baik dalam menjaga urutan relatif dari tetangga yang sebenarnya, meningkatkan kualitas peringkat bahkan dalam kompresi yang berat.

• FastScan adalah jalur pencarian PQ 4-bit yang dioptimalkan untuk SIMD yang mengurangi hambatan beban memori tradisional dengan menyimpan lebih banyak pekerjaan di dalam register CPU.

Dalam praktiknya, ini adalah pilihan yang kuat ketika Anda tidak keberatan menukar beberapa pemanggilan dengan QPS tinggi dan jejak memori yang jauh lebih kecil (sering kali mengompresi vektor hingga ~1/16 dari ukuran aslinya), seperti pada beban kerja rekomendasi yang tidak peka terhadap pemanggilan.

Dalam artikel ini, kita akan meninjau kembali IVFPQ sebagai garis dasar, mengeksplorasi optimasi utama yang diperkenalkan ScaNN di atasnya, dan mengakhiri dengan hasil eksperimen yang mendasari diskusi dalam kinerja terukur.

Rekap IVFPQ

ScaNN diusulkan oleh Google pada tahun 2020, dan makalah tersebut melaporkan peningkatan kinerja 3 kali lipat dari HNSW pada dataset GloVe. Anda dapat merujuk ke makalah asli dan implementasi sumber terbuka untuk detailnya.

Sebelum memperkenalkan ScaNN, kami akan merangkum IVFPQ secara singkat, karena ScaNN dibangun di atas kerangka kerja yang sama.

IVFPQ adalah singkatan dari Inverted File with Product Quantization, sebuah algoritma yang digunakan untuk pencarian Approximate Nearest Neighbor (ANN) berskala besar yang efisien dan berskala besar dalam database vektor berdimensi tinggi. Ini adalah pendekatan hibrida yang menggabungkan dua teknik, yaitu inverted file index (IVF ) dan product quantization (PQ), untuk menyeimbangkan kecepatan pencarian, penggunaan memori, dan akurasi.

Bagaimana IVFPQ Bekerja

Proses ini melibatkan dua langkah utama selama pengindeksan dan pencarian:

• Lapisan IVF: vektor dikelompokkan ke dalam daftar terbalik (cluster) nlist. Pada waktu kueri, Anda hanya mengunjungi sebagian cluster (nprobe) untuk mengimbangi recall dan latensi/throughput.

• Lapisan PQ: di dalam setiap cluster yang dikunjungi, setiap vektor D-dimensi dipecah menjadi m subvektor, masing-masing berdimensi (D/m). Setiap subvektor dikuantisasi dengan menempatkannya pada centroid terdekat di dalam sub-codebook. Jika sebuah sub-kodeks memiliki 256 centroid, setiap subvektor dapat diwakili oleh kode uint8 (sebuah ID dalam [0, 255]).

Komputasi jarak kemudian dapat ditulis ulang sebagai jumlah dari subvektor:

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L(q, id1) + L(q, id2) + L(q, id3) + ... + L(q, idn)

Di sini, L merepresentasikan sebuah tabel pencarian. Pada waktu kueri, tabel pencarian dibuat, mencatat jarak antara kueri dan setiap subvektor yang dikuantisasi. Semua perhitungan jarak selanjutnya dikonversi ke dalam tabel pencarian yang diikuti dengan penjumlahan.

Sebagai contoh, untuk vektor 128 dimensi yang dipecah menjadi 32 subvektor dengan masing-masing 4 dimensi, jika setiap subvektor dikodekan dengan ID uint8, biaya penyimpanan per vektor turun dari (128 x 4) byte menjadi (32 x 1) byte-pengurangan sebesar 1/16.

Optimasi ScaNN Berdasarkan IVFPQ

Secara ringkas, ScaNN meningkatkan IVFPQ dalam dua aspek:

1. Kuantisasi: ScaNN mengusulkan sebuah tujuan yang lebih dari sekadar mengganti setiap subvektor dengan centroid k-means terdekat (yaitu meminimalkan kesalahan rekonstruksi).

2. Efisiensi pencarian: ScaNN mempercepat pencarian berbasis LUT, yang sering kali terikat dengan memori, melalui jalur FastScan yang ramah SIMD.

Kehilangan Kuantisasi yang sadar skor

Karena analisis didasarkan pada metrik IP, setelah ScaNN menguraikan kesalahan kuantisasi menjadi komponen paralel dan tegak lurus, hanya komponen paralel yang memengaruhi hasil, sehingga istilah penalti yang lebih besar harus diterapkan. Akibatnya, fungsi rugi-rugi dapat ditulis ulang sebagai berikut:

$$\begin{array}{r}{\displaystyle \mathrm{\ell }({\mathrm{xi}}_{},{\mathrm{x~i}}_{},w)}\end{array}$$$$∥2\begin{aligned} \ell\left(x_i, \tilde{x}_i, w\right) &=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$$$$\tilde{x}_i\right)\right\|^2 \end{aligned}$$ ℓ$$\begin{array}{r}(x\end{array}$$i, x~i,w) =h∥ $$\begin{array}{l}(w,\end{array}$$∥xi$$\begin{array}{l}\Vert )\end{array}$$ $$\begin{array}{l}r\end{array}$$∥ $$\begin{array}{l}(x\end{array}$$i, x~i) 2+h⊥ $$\begin{array}{l}(w,\Vert x\end{array}$$i$$\begin{array}{l}\Vert )\Vert r\end{array}$$⊥ $$\begin{array}{l}(x\end{array}$$i,

Gambar di bawah ini menunjukkan contoh dua dimensi yang mengilustrasikan bahwa kesalahan yang disebabkan oleh komponen paralel lebih besar dan dapat menyebabkan hasil tetangga terdekat yang salah, sehingga memerlukan penalti yang lebih berat.

Gambar sebelah kiri menunjukkan kuantisasi yang buruk karena offset paralel memengaruhi hasil akhir, sedangkan gambar sebelah kanan menunjukkan kuantisasi yang lebih baik.

Pemindaian Cepat PQ 4-bit

Pertama-tama, mari kita tinjau proses komputasi PQ: selama kueri, jarak antara kueri dan pusat klaster subvektor dihitung sebelumnya untuk membangun tabel pencarian. Komputasi jarak kemudian dilakukan melalui pencarian tabel untuk mendapatkan jarak segmen dan menjumlahkannya.

Namun, pembacaan memori yang sering masih menjadi hambatan kinerja. Jika tabel pencarian dapat dibuat cukup kecil agar muat dalam register, operasi pembacaan memori dapat diubah menjadi instruksi SIMD CPU yang efisien.

Pertama, setiap subvektor dikelompokkan ke dalam 16 kelas, sehingga nilai 4-bit dapat mewakili pusat klaster-ini adalah asal mula nama "PQ 4-bit." Kemudian, jarak yang biasanya direpresentasikan sebagai float selanjutnya dikonversi ke uint8 menggunakan Scalar Quantization (SQ). Dengan cara ini, tabel pencarian untuk satu subvektor dapat disimpan dalam sebuah register menggunakan 16 × 8 = 128 bit.

Terakhir, mari kita lihat tata letak penyimpanan register (menggunakan set instruksi AVX2 sebagai contoh): subvektor dari 32 vektor ditempatkan dalam sebuah register 128-bit, digabungkan dengan tabel pencarian. Operasi "pencarian" kemudian dapat diselesaikan secara efisien dengan menggunakan satu instruksi CPU pengacakan SIMD.

tata letak register

Kocokan SIMD untuk Pencarian

Ini adalah pengamatan yang menarik: makalah ScaNN berfokus sepenuhnya pada optimasi pertama, yang mana hal ini masuk akal karena makalah ini dapat dianggap sebagai makalah algoritma yang menekankan pada turunan matematika. Namun, hasil eksperimen yang disajikan dalam makalah tersebut sangat mengesankan.

Hasil eksperimen yang disajikan dalam makalah ScaNN .

Secara intuitif, mengoptimalkan kerugian saja seharusnya tidak menghasilkan efek yang begitu dramatis. Blog lain juga menunjukkan hal ini-apa yang benar-benar membuat perbedaan adalah bagian PQ FastScan 4-bit.

Hasil Eksperimental

Dengan menggunakan alat benchmark basis data vektor VectorDBBench, kami melakukan pengujian sederhana. Keunggulan performa ScaNN dibandingkan IVFFLAT dan IVF_PQ tradisional cukup jelas terlihat. Setelah diintegrasikan ke dalam Milvus, pada dataset Cohere1M dengan tingkat recall yang sama, QPS dapat mencapai 5x lipat dari IVFFLAT dan 6x lipat dari IVF_PQ.

Namun, QPS sedikit lebih rendah daripada indeks berbasis grafik seperti HNSW, jadi ini bukan pilihan pertama untuk kasus penggunaan QPS tinggi. Tetapi untuk skenario dengan recall yang lebih rendah, hal ini dapat diterima (seperti di beberapa sistem rekomendasi), menggunakan ScaNN tanpa memuat data mentah dapat mencapai QPS yang mengesankan dengan jejak memori yang sangat rendah (1/16 dari data asli), menjadikannya pilihan indeks yang sangat baik.

Jenis_Indeks	Kasus	QPS	latensi (p99)	mengingat	memori
IVFFLAT	Kinerja1M	266	0.0173s	0.9544	3G
HNSW	Kinerja1M	1885	0.0054s	0.9438	3.24G
IVF_PQ	Kinerja1M	208	0.0292s	0.928	0.375G
ScaNN (with_raw_data: true)	Performa1M	1215	0.0069s	0.9389	3.186G
ScaNN (dengan_raw_data: false)	Kinerja1M	1265	0.0071s	0.7066	0.186G

Kesimpulan

ScaNN dibangun di atas kerangka kerja IVFPQ yang sudah dikenal, namun mendorongnya lebih jauh melalui rekayasa mendalam dalam hal kuantisasi dan akselerasi pencarian tingkat rendah. Dengan menyelaraskan tujuan kuantisasi dengan kualitas peringkat dan menghilangkan kemacetan memori di loop dalam, ScaNN menggabungkan kuantisasi yang sadar skor dengan jalur PQ FastScan 4-bit yang mengubah proses yang biasanya terikat memori menjadi penghitungan yang efisien dan ramah SIMD.

Dalam praktiknya, hal ini memberikan ScaNN ceruk yang jelas dan terdefinisi dengan baik. ScaNN tidak dimaksudkan untuk menggantikan indeks berbasis grafik seperti HNSW dalam pengaturan recall tinggi. Sebaliknya, untuk beban kerja yang tidak sensitif terhadap pemanggilan dengan anggaran memori yang ketat, ScaNN memberikan throughput yang tinggi dengan jejak yang sangat kecil. Dalam percobaan kami, setelah diintegrasikan ke dalam Milvus VectorDB, ScaNN mencapai sekitar 5× QPS IVFFLAT pada dataset Cohere1M, menjadikannya pilihan yang kuat untuk pengambilan ANN dengan throughput tinggi dan latensi rendah di mana kompresi dan efisiensi lebih penting daripada pemanggilan yang sempurna.

Jika Anda tertarik untuk menjelajahi ScaNN lebih jauh atau mendiskusikan pemilihan indeks dalam sistem dunia nyata, bergabunglah dengan Slack Channel kami untuk mengobrol dengan teknisi kami dan teknisi AI lainnya di komunitas. Anda juga dapat memesan sesi tatap muka selama 20 menit untuk mendapatkan wawasan, panduan, dan jawaban atas pertanyaan Anda melalui Milvus Office Hours.