Search Beam Width

Search Beam Width defines the maximum number of candidate nodes (the 'beam') held in a priority queue during each step of a greedy graph traversal. The algorithm explores the neighbors of all nodes in the current beam, scores them, and keeps only the top beam width candidates for the next iteration. This mechanism prevents the search from degenerating into a simple, easily trapped greedy walk by maintaining a pool of promising paths.

• Primary Role: Balances exploration (searching more paths) against exploitation (focusing on the current best path).
• Analogy: Similar to how a chess engine evaluates multiple potential move sequences (the beam) before committing to a path.

Beam width creates a direct, tunable trade-off between search accuracy (recall) and query latency.

• Larger Beam Width: The algorithm explores more candidate nodes per layer. This increases the probability of finding the true nearest neighbors, thereby improving recall. However, it also increases the number of distance computations and priority queue operations, increasing latency and CPU cost.
• Smaller Beam Width: The search becomes more greedy and faster, reducing latency. However, with a narrower exploration scope, it is more likely to follow a sub-optimal path and miss the true nearest neighbors, potentially reducing recall.

Tuning this parameter is essential for matching application requirements, whether prioritizing millisecond responses or maximum accuracy.

In Hierarchical Navigable Small World (HNSW) graphs, beam width interacts with the graph's multi-layered structure. The search begins at the topmost, sparsest layer with a long 'zoom-out' view and proceeds downwards to denser layers.

• Upper Layers: A smaller beam width is often sufficient because the long-range connections help navigate quickly to the correct region of the vector space.
• Lower Layers: As the search nears the bottom (densest) layer where the final nearest neighbors reside, a larger beam width becomes more critical. It allows the algorithm to refine its search within a dense local neighborhood, ensuring high-precision results.

Some implementations use a dynamic or layer-dependent beam width to optimize this process.

Operationally, beam width is implemented using a min-heap or max-heap priority queue (often a 'candidate set' and a 'visited set').

Process per search layer:

1. Pop the best node from the candidate min-heap (closest to the query).
2. Explore its connections, computing distances to the query.
3. Add promising new candidates to the heap.
4. If the heap size exceeds the configured beam width, prune it by removing the worst (farthest) candidate.

This heap management is the core computational overhead. The cost scales with beam width * average node degree. Efficient heap implementations are crucial for performance.

Optimal beam width is dataset and index-dependent, but general guidelines exist:

• Start Point: A common default is between 32 and 128. For HNSW, values like 64 or 100 are frequently used as baselines.
• Tuning Method: Perform a sweep (e.g., 16, 32, 64, 128, 256) while measuring Recall@10 and Queries Per Second (QPS). Plot the trade-off curve to select a value that meets your accuracy/latency Service Level Objective (SLO).
• High-Dimensional Data: Often requires a larger beam width for equivalent recall due to the 'curse of dimensionality' and less reliable distance metrics.
• Production Consideration: A larger beam width also increases memory bandwidth pressure during search, as more vector data is fetched. This can become a bottleneck on large-scale systems.

Beam width is closely related to the strategy of Exact Re-ranking. In a common two-stage search pipeline:

1. Approximate Search: A graph-based index (e.g., HNSW) with a moderate beam width retrieves a broad candidate set (e.g., top 200 vectors). This stage is fast but approximate.
2. Exact Re-ranking: The candidate set is then re-scored using exact, full-precision distance calculations (e.g., full float32 Euclidean distance) to produce the final, accurate top-k results.

Here, the beam width in the first stage determines the size and quality of the candidate pool for re-ranking. A wider beam provides a better candidate pool for the second stage to work with, often yielding higher final accuracy than simply using a massive beam width in the first stage alone.

The standalone HNSWlib implements beam width identically to the core HNSW paper via the ef parameter.

• Direct Control: The ef parameter passed during search (knnQuery) explicitly sets the size of the dynamic candidate list.
• Resource Management: Larger ef values consume more temporary memory per query and increase latency linearly.
• Precision Tuning: It is the primary parameter for trading between search speed (low ef) and high recall (high ef), independent of the M parameter which controls graph connectivity.

Vector databases like Weaviate and Qdrant expose HNSW beam width as a configurable index setting, often named ef or ef_search.

• Per-Collection Configuration: Set at the collection/schema level during index configuration.
• Query-Time Overrides: Some databases allow temporary ef overrides via query parameters for dynamic tuning.
• Impact on SLA: This parameter is crucial for database operators to meet specific latency and recall Service Level Agreements (SLAs) in production.

Managed vector database services like Pinecone abstract low-level parameters but still allow control over the accuracy-speed trade-off.

• Abstraction Layer: Beam width may be managed internally or exposed via high-level concepts like "search precision" or "pod type."
• Automatic Optimization: Some services may dynamically adjust internal beam width based on query load and performance targets.
• User Control: Configuration is typically through API parameters or console settings that map to underlying ef values.

DiskANN uses beam search in its Vamana graph algorithm, controlled by the search_list_size (often labeled L).

• Persistent Caching: Designed for large datasets on disk, a larger search_list_size (beam width) increases I/O by fetching more candidate nodes from SSD but improves recall.
• Two-Phase Search: The algorithm often uses an expanded beam during the search phase compared to the prune phase during construction.
• Memory-Disk Trade-off: Tuning this parameter is critical for balancing SSD bandwidth usage with search accuracy.

Google's SCANN uses a different paradigm but employs an analogous concept in its Tree-AH (Tree Asymmetric Hashing) index.

• Leaves Searched: The leaves_to_search parameter acts as the beam width equivalent, controlling how many partitions (tree leaves) are probed.
• Anisotropic Quantization: The candidate set within a leaf is generated using anisotropic quantization, not graph traversal.
• Throughput Optimization: Increasing leaves_to_search improves recall but directly impacts throughput, as each leaf search is independent and can be parallelized.

HNSW is a state-of-the-art graph-based index where Search Beam Width is most prominently used. The algorithm constructs a hierarchical graph with layers of varying density. During search, it performs a greedy traversal from the top layer down, using a priority queue (the beam) to hold the best candidate nodes at each step. A wider beam explores more neighbors per layer, increasing recall but also computational cost.

• Core Mechanism: Uses beam search on a multi-layer graph.
• Relation to Beam Width: Directly controls the size of the candidate list during the greedy search on each graph layer.

Beam Search is a heuristic search algorithm that explores a graph or tree by expanding the most promising nodes in a limited set, called the beam. It is a breadth-first search variant that does not keep all nodes in memory, only the top-k (the beam width) at each depth or iteration. This makes it fundamental to efficient traversal in high-dimensional vector graphs.

• Key Characteristic: Maintains a fixed-width priority queue of partial solutions.
• Application in ANNS: Used in HNSW, DiskANN, and other graph indexes to navigate towards the query's nearest neighbors.

Recall@k is the primary accuracy metric for evaluating approximate nearest neighbor search. It measures the fraction of the true k-nearest neighbors found in the algorithm's top-k results. Search Beam Width has a direct, non-linear impact on this metric.

• Calculation: Recall@k = (|True Top-k ∩ Retrieved Top-k|) / k
• Trade-off with Beam Width: Increasing the beam width typically improves Recall@k but with diminishing returns, as the search explores a broader neighborhood. Tuning involves finding the point where additional width yields negligible recall gains for significant latency increases.

A Graph-Based Index is a data structure where data points are nodes, and edges connect similar nodes. Search is performed by starting at an entry point and traversing the graph. Search Beam Width is a defining hyperparameter for the traversal logic in these indexes.

• Common Examples: HNSW, NSG, DiskANN.
• Beam Width's Role: During traversal, the algorithm selects the beam width number of most promising neighboring nodes from the current candidate pool to visit next. This balances exploration (visiting new areas) and exploitation (refining within a local cluster).

In the context of vector search, a Priority Queue (often a min-heap or max-heap) is the in-memory data structure that implements the "beam." It continuously maintains the beam width number of candidate vectors with the best (closest) distances to the query during graph or tree traversal.

• Function: Efficiently inserts new candidates and pops the best ones for expansion.
• Performance Impact: The size of this queue (beam width) determines memory overhead and comparison operations per search step. A width of 200 requires maintaining 200 sorted candidates at each hop.

Search Latency (query latency) and Queries Per Second (QPS) are the core performance metrics inversely affected by Search Beam Width. Latency increases approximately linearly with beam width, as each step involves more distance computations and priority queue operations.

• Engineering Trade-off: The central challenge is selecting a beam width that achieves the target Recall@k while meeting strict Service Level Agreements (SLAs) for latency and throughput.
• Tuning Practice: Performance profiling involves sweeping beam width values and plotting the latency-recall curve to identify the optimal operating point for a production system.