New GPU Trick Makes AI Search Up to 12x Faster

Filtered approximate nearest neighbor search — returning the top-k vectors nearest a query among those satisfying attribute predicates — is a fundamental operation in modern vector search systems. Existing graph-based systems use beam search with a high fixed beamwidth of 100 or greater to ensure high recall, forcing every query to search as thoroughly as the hardest query in the batch, even though the authors observe that more than half of queries across multiple data sets can be solved precisely with a beamwidth of 50 or less. Farhana Akter Tumpa and Rajiv Gupta present BOA, a filtered ANNS engine for a single GPU that uses online beamwidth adaptation: all queries are first evaluated under a narrow beam, and only those with uncertain results are progressively refined with wider beamwidths. BOA+ overlaps execution of phases to further enhance throughput. 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 — increasing throughput by 7x to 12.5x.