PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Farhana Akter Tumpa, Rajiv Gupta

arXiv:2609.16175v1cs.DC

TL;DR

Fixed-width filtered ANNS makes every query pay for wider searches, while sparse valid regions also challenge graph traversal. BOA adapts beamwidth in phases, reporting higher throughput than fixed-width search while maintaining high recall at lower average beamwidth.

  • Problem

    Fixed beamwidth forces every query to use the wider search needed by the hardest queries, while selective filters leave valid neighbors sparse and difficult to reach.

    Source: §I · pp. 1–2

  • Method

    BOA searches queries in phases, increasing beamwidth only for unresolved queries and carrying a filter signal through GPU beam search for multi-attribute range filters.

    Source: §I · p. 2, A. Adaptive Filtered Search Algorithm · p. 4

  • Results

    94.05% to 99.96% recall at average beamwidth 22 to 77 accompanies 7× to 12.5× higher throughput than the non-adaptive approach, which uses fixed beamwidth 500 for similar or lower recall.

    Source: §I · p. 2

  • Takeaways & Limitations

    The authors report that throughput improvements over fixed-width search are greater for more challenging workloads.

    Source: §VI · p. 10

Abstract

from arXiv · show

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

I. INTRODUCTION

Filtered ANNS must find nearest vectors subject to metadata predicates, while fixed beamwidth makes recall gains cost throughput across every query. BOA adapts beamwidth and supports multi-attribute filtering on a GPU while preserving graph connectivity.

I. INTRODUCTION

  • Fixed-width GPU searches must widen the beam for every query to improve recall, even though only a minority of queries need greater search effort.Most queries already retrieve their true neighbors at small beamwidth; query difficulty becomes apparent during the search.Source: §I · pp. 1–2
  • BOA searches all queries first with a small beam, then re-searches only queries whose results remain uncertain using wider beams.The introduction reports that more than half of queries across multiple datasets can be solved with beamwidth 50 or less.Source: §I · p. 2
  • For multi-attribute range filters, BOA carries a filter signal through GPU beam search, demoting invalid candidates rather than removing them so valid regions remain reachable.The engine supports multiple range filters while preserving graph connectivity.Source: §I · p. 2
  • 94.05% to 99.96% recall at average beamwidth 22 to 77, versus fixed beamwidth 500 for similar or lower recall, accompanies 7× to 12.5× higher throughput.The comparison is reported for online adaptation versus a non-adaptive approach.Source: §I · p. 2

II. BACKGROUND & MOTIVATION

Filtered k-nearest-neighbor search ranks only points satisfying the query’s attribute predicates, and range-filtered queries constrain selected numeric attributes with intervals. The background describes graph construction and beam search as the indexing and traversal mechanisms for this task.

II. BACKGROUND & MOTIVATION

  • Filtered k-NNS returns the k nearest points that satisfy every queried predicate; RFNNS applies numeric range intervals to selected attributes.When fewer than k points satisfy the filter, the eligible set is the answer.Source: A. Background: Problem Definition · pp. 2–3
  • For multi-attribute traversal, φ counts violated predicates and λφ is added to vector distance; threshold pruning keeps the merged graph degree bounded by R.The resulting index occupies O(nR) space, independent of the number of thresholds.Source: A. Background: Problem Definition · p. 3
  • Beam search keeps L candidates, expands the closest unvisited point, and returns the closest k; each iteration costs at most R distance computations.A small L can discard candidates early and prevent recovery from a path into the wrong graph region.Source: A. Background: Problem Definition · p. 3

B. Motivation: Beamwidth vs. Recall

Beamwidth L controls the size of the candidate set, linking search cost and accuracy. On Garfield, recall and normalized throughput move in opposite directions as L increases.

B. Motivation: Beamwidth vs. Recall

  • A larger candidate set raises recall but lowers throughput because admitted candidates are expanded; a smaller set can discard paths to true neighbors.Recall also falls as the number of filter attributes m grows at fixed L.Source: B. Motivation: Beamwidth vs. Recall · p. 3
  • The search reaches 0.9 recall at L = 500 with a 17× throughput loss, and 0.97 at L = 1700 after throughput falls by more than 190×.At L = 10, recall is 0.21 and throughput is at its maximum.Source: B. Motivation: Beamwidth vs. Recall · p. 4
  • Across SIFT1M, DBLP, Deep1M, and YouTube, Garfield’s recall and throughput curves move in opposite directions with L; the trade-off also appears at m = 1 and m = 2.The figure’s throughput is normalized to its maximum over the displayed range of L.Source: B. Motivation: Beamwidth vs. Recall · pp. 3–4, Figure 1 · p. 3

III. BOA: BEAMWIDTH ONLINE ADAPTATION

Query difficulty varies within and across datasets, so fixed beamwidths waste work on queries already solved by narrower searches. BOA adapts beamwidth in phases, escalating only unresolved queries.

III. BOA: BEAMWIDTH ONLINE ADAPTATION

  • Fig. 2 shows that, in most cases, half the queries require a beamwidth of 50 or lower, with the distribution varying by dataset and workload.The location of neighbors in the graph relative to the filter also affects the distribution.Source: Figure 2 · p. 4, §III · p. 4
  • A query already solved at L = 10 gains no recall from a wider search, so fixed-width systems pay for unnecessary work across the batch.Increasing the fixed width from 10 to 500 substantially reduces throughput.Source: §III · p. 4
  • BOA searches every query first with a small beamwidth, then advances unresolved queries through wider phases while answered queries leave the batch.This limits the wider-beam cost to the queries that need it.Source: §III · p. 4
  • For YouTube with m = 4, L = 50 resolves 40% of queries, while recall above 90% requires L well over 200.The adaptive experiments achieve 94.05% recall at average L = 77.Source: §III · p. 4
  • BOA supports multi-attribute filtering across phases on the GPU, changing both graph traversal and the surviving query set between phases.The paper states that no prior system combines these features.Source: §III · p. 4

A. Adaptive Filtered Search Algorithm

BOA runs filtered graph search in progressively wider phases, using a confidence test to stop work on resolved queries. Its filter-aware traversal retains invalid candidates as navigational intermediaries, and BOA+ overlaps batched phases.

A. Adaptive Filtered Search Algorithm

  • Each phase increases beamwidth and evaluates only queries still unresolved from the preceding phase.The number of phases depends on query difficulty; most may finish with a narrow beam, while sparse or heavily filtered neighborhoods can require several phases.Source: A. Adaptive Filtered Search Algorithm · pp. 4–5
  • A query is confident when the relative gap between the kth result and the farthest additional filter-valid candidate is small; the test uses ε = 0.05 across datasets.The gap is normalized by dmax.Source: A. Adaptive Filtered Search Algorithm · pp. 4–5
  • When fewer than τρ queries remain active, BOA stops pursuing the residual queries and returns their best answers found.Every query returns a result.Source: A. Adaptive Filtered Search Algorithm · p. 5
  • Each query traverses from the medoid with its own worklist, while CPU-side neighbor and filter processing supplies candidates scored and merged on the GPU.A per-query Bloom filter drops previously seen candidates to prevent duplicates from displacing better worklist entries.Source: A. Adaptive Filtered Search Algorithm · p. 6
  • Filter-aware beam search adds a penalty for predicate violations, ranking valid candidates ahead while retaining invalid candidates for possible expansion.Only filter-valid candidates are eligible for the final k-nearest-neighbor result; the penalty guides navigation rather than determining validity.Source: A. Adaptive Filtered Search Algorithm · p. 6
  • To avoid repeating work across widths L and αL, BOA evaluates the first L children in one phase and the next αL−L children in the following phase, then combines their results.The combined top-k results represent all αL children.Source: A. Adaptive Filtered Search Algorithm · p. 6
  • BOA+ splits the initial Lmin search into sub-batches and pools their survivors for wider searches overlapping the remaining initial searches.BOA and BOA+ reach the same recall; BOA+ reaches it sooner, and that shorter execution span yields higher throughput.Source: A. Adaptive Filtered Search Algorithm · p. 6

B. BOA Implementation on a GPU System

BOA divides graph-search work between CPU and GPU to address the traversal’s dependent steps and data placement. Its implementation overlaps transfers with GPU work and launches survivors contiguously for later phases.

B. BOA Implementation on a GPU System

  • Graph traversal has dependent steps, and each step can require data the GPU does not hold, making coordination between processors a central design concern.Batching independent queries supplies parallelism but does not remove dependencies within a query.Source: B. BOA Implementation on a GPU System · p. 6
  • The CPU holds the graph and handles adjacency lookup and filter evaluation, while the GPU performs PQ distance evaluation, candidate ranking, worklist maintenance, and the final exact-distance pass.Asynchronous transfers on dedicated streams overlap with kernel execution.Source: B. BOA Implementation on a GPU System · pp. 6–7
  • In each iteration, the CPU reads neighbors and evaluates predicate violations, then the GPU removes visited candidates, computes penalized distances, sorts and merges candidates, and selects the next node.After convergence, the GPU ranks candidates by exact distance under a hard predicate penalty and returns the top-k identifiers.Source: B. BOA Implementation on a GPU System · p. 7
  • Separate kernels configure stages for their different workloads, while survivor gathering makes later-phase launches track the number of queries that need further search.The implementation assigns one block per query and gathers survivor state into contiguous arrays before the next phase.Source: B. BOA Implementation on a GPU System · p. 7

IV. EXPERIMENTS

The evaluation compares fixed-width search, BOA, and pipelined BOA+ on four datasets, using synthesized attributes for two vector-only datasets and range-filter queries.

IV. EXPERIMENTS

  • The evaluation contrasts Fixed L, which uses beamwidth 500 to achieve recall >90%, with BOA’s online adaptation using phases at beamwidths 10, 100, and 200 to achieve recall >90%.Source: §IV · p. 7
  • Experiments use SIFT1M, Deep1M, DBLP, and YouTube; attributes are synthesized for SIFT1M and Deep1M, while DBLP and YouTube use real-world vectors with naturally skewed numeric attributes.Each query has a range predicate per attribute, with selectivity generated uniformly from 1% to 100%.Source: §IV · p. 7
  • The experiments use a system with two AMD EPYC 7543 32-core CPUs and an NVIDIA A100 GPU with 80GB of memory.BOA is implemented in C++/CUDA using CUDA 12.4.Source: §IV · p. 7

A. BOA: Recall and Throughput

BOA’s recall@10 and throughput were measured for a 10,000-query batch across datasets and filter counts. Recall stayed above 90% as both metrics declined with more filter attributes.

A. BOA: Recall and Throughput

B. BOA: Achieving Steady High Recall

BOA resolves queries over successive beamwidth phases, with the phase count and query distribution varying by dataset. Across the reported workloads, Recall@10 ranges from 94.05% to 99.96%.

B. BOA: Achieving Steady High Recall

C. Beamwidth Needed for High Recall: BOA vs. Fixed L

BOA pairs dynamically adapted beamwidths with high recall, while the fixed-width baseline uses L = 500 for similar or lower recall.

C. Beamwidth Needed for High Recall: BOA vs. Fixed L

D. Throughput Enhancement: BOA and BOA+ vs. Fixed L

BOA and BOA+ improve throughput over fixed L, with BOA+ adding pipelining across smaller query batches. The reported BOA+ throughput gains are larger than BOA’s alone.

D. Throughput Enhancement: BOA and BOA+ vs. Fixed L

V. RELATED WORK

Prior filtered-search systems differ in filter support, graph construction, and filter timing. The conclusion presents BOA and BOA+ beamwidth adaptation as a way to reduce wasteful computation and improve throughput.

V. RELATED WORK

  • Nearly all filtered-search work targets CPUs, and existing systems vary in whether they support multiple, single, or no filter attributes.Source: §V · p. 9
  • This work considers range filters and identifies equality and subset filters as straightforward extensions.Source: §V · p. 9
  • BOA and JAG use one attribute-unaware graph and apply filters during traversal, whereas Garfield and other systems build attribute-aware partitions or related structures.These partitioned structures inflate the index; GAAF instead maintains an ensemble of graphs and routes queries by label frequency.Source: §V · p. 9
  • Filtered-search systems apply predicates before search, after retrieval, or within traversal.Source: §V · p. 9
  • PANNS adapts search in two phases within one traversal, but supports neither filtering nor GPU execution.It switches phases when a query’s top-k beam entries have all been visited, then widens the step size and reduces the cutoff factor.Source: §V · p. 9

VI. CONCLUSION

  • The conclusion reports that throughput improvements grow as workloads become more challenging.Source: §VI · p. 10

Related papers

Loading 2609.16175v1…