BOA: Adaptasi Lebar Berkas Daring untuk Filtered-ANNS pada GPU

Adaptasi lebar berkas daring menyesuaikan upaya pencarian per kueri dalam satu batch, menghasilkan peningkatan throughput 7x-12,5x untuk pencarian tetangga terdekat perkiraan terfilter pada satu GPU.

Farhana Akter Tumpa; Rajiv Gupta· 2026· DOI 10.48550/arXiv.2609.16175

Masalah inti

Pencarian tetangga terdekat perkiraan terfilter (ANNS) — mengembalikan k vektor teratas yang paling dekat dengan vektor kueri di antara vektor yang memenuhi satu atau lebih predikat atribut — telah menjadi operasi fundamental dalam sistem pencarian vektor modern. Solusi berbasis graf memakai beam search untuk menyelesaikan sekumpulan kueri secara paralel demi throughput tinggi dan biasanya memakai lebar berkas tetap yang tinggi sebesar 100 atau lebih untuk memastikan recall tinggi. Namun, penulis mengamati bahwa, dengan sekumpulan kueri, lebih dari separuh kueri di berbagai dataset dapat diselesaikan secara tepat dengan lebar berkas hanya 50 atau kurang. Akibatnya, sistem yang ada berbasis lebar berkas tinggi tetap mengorbankan throughput untuk mencapai recall tinggi dengan memaksa setiap kueri mencari sedetail kueri tersulit dalam batch, meskipun mayoritas kueri dapat diselesaikan dengan pencarian dangkal. Makalah ini menyajikan BOA, mesin ANNS terfilter untuk satu GPU yang memakai adaptasi lebar berkas daring untuk menyesuaikan upaya pencarian antar-kueri dalam satu batch di bawah filter rentang multi-atribut.

Eksperimen menunjukkan bahwa, untuk 10.000 kueri, adaptasi daring mencapai recall 94,05% hingga 99,96% dengan lebar berkas rata-rata berkisar 22 hingga 77, sedangkan pendekatan non-adaptif memerlukan lebar berkas tetap 500 untuk mencapai recall serupa atau lebih rendah. Akibatnya, adaptivitas meningkatkan throughput sebesar 7x hingga 12,5x. Recall sebagian besar tidak sensitif terhadap lebar berkas awal, artinya bahkan jika berkas sempit awal sangat kecil, recall akhir tetap tinggi karena penyempurnaan progresif. Lebar berkas rata-rata 22 hingga 77 jauh lebih rendah daripada 500 tetap yang diperlukan metode non-adaptif, sehingga menghasilkan keuntungan throughput yang substansial. Eksperimen dilakukan pada berbagai dataset, dan pengamatan bahwa lebih dari separuh kueri dapat diselesaikan dengan lebar berkas \leq 50 berlaku di seluruh dataset tersebut.

Pencarian tetangga terdekat perkiraan terfilter (ANNS) — mengembalikan k vektor teratas yang paling dekat dengan vektor kueri di antara vektor yang memenuhi satu atau lebih predikat atribut — telah menjadi operasi fundamental dalam sistem pencarian vektor modern. Solusi berbasis graf memakai beam search untuk menyelesaikan sekumpulan kueri secara paralel demi throughput tinggi dan biasanya memakai lebar berkas tetap yang tinggi sebesar 100 atau lebih untuk memastikan recall tinggi. Namun, penulis mengamati bahwa, dengan sekumpulan kueri, lebih dari separuh kueri di berbagai dataset dapat diselesaikan secara tepat dengan lebar berkas hanya 50 atau kurang. Akibatnya, sistem yang ada berbasis lebar berkas tinggi tetap mengorbankan throughput untuk mencapai recall tinggi dengan memaksa setiap kueri mencari sedetail kueri tersulit dalam batch, meskipun mayoritas kueri dapat diselesaikan dengan pencarian dangkal. Makalah ini menyajikan BOA, mesin ANNS terfilter untuk satu GPU yang memakai adaptasi lebar berkas daring untuk menyesuaikan upaya pencarian antar-kueri dalam satu batch di bawah filter rentang multi-atribut.

BOA mengatasi tradeoff recall-throughput dengan pencarian multi-fase. Semua kueri pertama-tama dievaluasi dengan berkas sempit, dan hanya kueri dengan hasil tidak pasti yang secara progresif disempurnakan dengan lebar berkas yang lebih lebar. Hal ini membuat recall sebagian besar tidak sensitif terhadap lebar berkas awal, sedangkan metode sebelumnya harus memakai lebar berkas tinggi tetap untuk recall tinggi. Adaptasi dilakukan secara daring, artinya lebar berkas disesuaikan secara dinamis selama proses pencarian berdasarkan ketidakpastian yang teramati pada setiap kueri. BOA+ menumpang-tindihkan eksekusi fase untuk lebih meningkatkan throughput. Sistem ini dirancang untuk satu GPU, memanfaatkan pemrosesan paralel batch kueri. Algoritma inti dapat diringkas sebagai berikut:

Wawasan kunci BOA adalah bahwa tidak semua kueri dalam satu batch memerlukan upaya pencarian yang sama. Dengan mengadaptasi lebar berkas secara daring, BOA menghindari inefisiensi memaksa setiap kueri mencari sedetail kueri tersulit. Hal ini sangat penting untuk ANNS terfilter, di mana predikat atribut dapat membuat sebagian kueri lebih mudah diselesaikan daripada yang lain. Pendekatan multi-fase memastikan recall tidak dikorbankan, karena kueri yang tidak pasti disempurnakan hingga keyakinan tercapai. Tumpang-tindih fase pada BOA+ lebih meningkatkan throughput dengan memanfaatkan sumber daya GPU secara lebih efisien. Hasilnya menunjukkan bahwa adaptasi daring dapat mencapai recall tinggi dengan lebar berkas rata-rata jauh lebih rendah, sehingga menghasilkan peningkatan throughput yang signifikan. Pendekatan ini berlaku luas untuk sistem ANNS berbasis graf apa pun yang memakai beam search, dan dapat diperluas ke akselerator perangkat keras lain. Pekerjaan selanjutnya dapat mengeksplorasi kriteria ketidakpastian yang lebih canggih dan penjadwalan fase yang adaptif.

Praktisi dan peneliti ilmu komputer

Membuka konten member…