Metraipolis › archive › dc_e7b033eabf5b
BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU — arXiv:2609.16175
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.16175
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T19:29:34.353Z
- SHA-256 of the archived text
29edb37a4402cb0664b4b200b04252c14bd3349fc72a4a4afd0fba31ba5ed0da- Stable URL of this page
https://metraipolis.com/documento/dc_e7b033eabf5b
How to cite
BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU — arXiv:2609.16175 — arXiv (en), https://arxiv.org/abs/2609.16175 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e7b033eabf5b (Metraipolis archive dc_e7b033eabf5b, sha256 29edb37a4402cb0664b4b200b04252c14bd3349fc72a4a4afd0fba31ba5ed0da)
BibTeX
@misc{dce7b033eabf5b,
title = {BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU — arXiv:2609.16175},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.16175},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e7b033eabf5b; sha256 29edb37a4402cb0664b4b200b04252c14bd3349fc72a4a4afd0fba31ba5ed0da},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16175. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Filtered approximate nearest neighbor search, i.e. returning the top-k vectors nearest to a query vector among those satisfying one or more attribute predicates, has become a fundamental operation in modern vector search systems. Graph-based solutions employ beam search to solve a batch of queries in parallel for high throughput and employ high fixed beamwidth of 100 or greater for ensuring high recall. We observe that, given a batch of queries, more than half of the queries across multiple data sets can be solved precisely with a beamwidth of just 50 or less. Therefore, existing systems based on fixed high beamwidth sacrifice throughput to achieve high recall by forcing every query to search as thoroughly as the hardest query in the batch even though majority of queries can be resolved by a shallow search. In this paper we present a filtered ANNS engine for a single GPU named BOA that uses online beamwidth adaptation to customize the search effort across queries within a batch under multi-attribute range filters. We address the recall throughput tradeoff with a multi-phase search: all queries are first evaluated under a narrow beam, and only those with uncertain results are progressively refined with wider beamwidths. This renders recall largely insensitive to the starting beamwidth, whereas prior methods must use a fixed high beamwidth for high recall. BOA+ overlaps execution of phases to further enhance throughput. Our experiments show that, for 10,000 queries, online adaptation achieves 94.05% to 99.96% recall with average beamwidth ranging from 22 to 77, while a non-adaptive approach requires a fixed beamwidth of 500 to achieve similar or lower recall. Consequently, adaptivity increases throughput by 7x to 12.5x Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DC). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2609.16175 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T18:35:05.416Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).