BOA: Beamwidth Online Adaptation for Filtered-ANNS on a GPU

Online beamwidth adaptation customizes search effort per query within a batch, delivering 7x-12.5x throughput gains for filtered approximate nearest neighbor search on a single GPU.

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

The core problem

Filtered approximate nearest neighbor search (ANNS) — 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 typically use a high fixed beamwidth of 100 or greater to ensure high recall. However, the authors 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. Consequently, 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 the majority of queries can be resolved by a shallow search. This paper presents BOA, a filtered ANNS engine for a single GPU that uses online beamwidth adaptation to customize the search effort across queries within a batch under multi-attribute range filters.

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. The recall is largely insensitive to the starting beamwidth, meaning that even if the initial narrow beam is very small, the final recall remains high due to progressive refinement. The average beamwidth of 22 to 77 is significantly lower than the fixed 500 required by non-adaptive methods, leading to substantial throughput gains. The experiments were conducted on multiple data sets, and the observation that more than half of queries can be solved with beamwidth \leq 50 held across these data sets.

Filtered approximate nearest neighbor search (ANNS) — 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 typically use a high fixed beamwidth of 100 or greater to ensure high recall. However, the authors 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. Consequently, 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 the majority of queries can be resolved by a shallow search. This paper presents BOA, a filtered ANNS engine for a single GPU that uses online beamwidth adaptation to customize the search effort across queries within a batch under multi-attribute range filters.

BOA addresses 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. The adaptation is performed online, meaning the beamwidth is adjusted dynamically during the search process based on the observed uncertainty of each query. BOA+ overlaps the execution of phases to further enhance throughput. The system is designed for a single GPU, leveraging parallel processing of query batches. The core algorithm can be summarized as follows:

The key insight of BOA is that not all queries in a batch require the same search effort. By adapting the beamwidth online, BOA avoids the inefficiency of forcing every query to search as thoroughly as the hardest query. This is particularly important for filtered ANNS, where attribute predicates can make some queries easier to resolve than others. The multi-phase approach ensures that recall is not compromised, as uncertain queries are refined until confidence is achieved. The overlap of phases in BOA+ further improves throughput by utilizing GPU resources more efficiently. The results demonstrate that online adaptation can achieve high recall with much lower average beamwidth, leading to significant throughput improvements. This approach is broadly applicable to any graph-based ANNS system that uses beam search, and could be extended to other hardware accelerators. Future work may explore more sophisticated uncertainty criteria and adaptive scheduling of phases.

CS practitioners and researchers

Opening member content…