Candidate Generation

The core trade-off of candidate generation is sub-linear query time for approximate results. Instead of an exhaustive (linear) scan comparing the query to every vector, it uses specialized indices like Inverted File (IVF) or Hierarchical Navigable Small World (HNSW) graphs to search only a promising subset of the data. This reduces latency from O(N) to O(log N) or better, enabling real-time search over billion-scale datasets, albeit with a controlled loss in recall.

This stage is optimized for high recall@K, aiming to retrieve as many of the true nearest neighbors as possible within its candidate set. The philosophy is 'cast a wide net'—it's acceptable to include some irrelevant candidates, as long as most relevant items are captured. The subsequent re-ranking stage is responsible for culling false positives and perfecting the final ranking order. Parameters like nprobe in IVF or ef_search in HNSW directly control this recall/latency trade-off.

Candidate generation is rarely the final step. It feeds into a multi-stage retrieval and ranking architecture:

• Stage 1 (Candidate Gen): Fast, approximate search returns 100-10k candidates.
• Stage 2 (Re-ranking): A more computationally expensive, precise model (e.g., a cross-encoder, refined distance calculation, or business logic) scores and re-orders the candidate subset.
• Stage 3 (Final Ranking): May incorporate personalized features, diversity filters, or policy rules. This separation allows the system to combine the scale of approximate search with the precision of complex models.

Performance hinges on the underlying Approximate Nearest Neighbor (ANN) index. Key algorithms include:

• Inverted File Index (IVF): Partitions data into clusters (Voronoi cells). Search is limited to the nprobe nearest clusters.
• Hierarchical Navigable Small World (HNSW): A multi-layer graph where search begins at a top-layer entry point and navigates to the nearest neighbors, layer by layer.
• Locality-Sensitive Hashing (LSH): Hashes similar vectors into the same 'bucket' with high probability, searching only within the query's bucket. Each method makes different trade-offs between index build time, memory footprint, query speed, and accuracy.

Real-world queries often require combining semantic vector search with structured metadata filters (e.g., date > 2024 and category = 'news'). Candidate generation systems implement strategies to execute these filtered searches efficiently:

• Pre-filtering: Apply metadata filters first, then perform vector search on the filtered subset. Risk: can eliminate all relevant vectors if the filter is too restrictive.
• Post-filtering: Perform vector search first, then filter the resulting candidates. Risk: may return fewer than K results if filters are strict.
• Single-Stage Filtered Search: Advanced indexes (e.g., Milvus's scalar-field indexes) evaluate filters during the graph traversal or IVF probe, providing a more integrated optimization.

The choice of candidate generation strategy influences overall system design:

• Memory vs. Disk: IVF-PQ indices can operate largely on compressed vectors in RAM, while some graph indices have larger memory footprints.
• Update Friendliness: IVF indices can be updated relatively easily by adding vectors to existing clusters, while HNSW graph modifications are more complex, often requiring partial rebuilds.
• Parameter Tuning: Production deployment requires tuning parameters (e.g., IVF's nprobe, HNSW's ef_construction and ef_search) against benchmark datasets to hit target latency Service-Level Objectives (SLOs) and recall thresholds. This is a key task for ML and performance engineers.

The foundational algorithmic class for candidate generation. ANN search trades perfect accuracy for sub-linear query time, enabling fast retrieval from massive vector datasets. It is the core engine behind candidate generation, using indexes like HNSW or IVF to avoid comparing the query against every vector in the database.

• Purpose: Enable real-time similarity search at scale.
• Trade-off: Configurable balance between recall and query latency.
• Example: Finding 100 similar product images from a catalog of 100 million in <10ms.

A prevalent index structure for candidate generation. IVF partitions the vector space into clusters (Voronoi cells) via k-means. At query time, the system finds the nearest centroids and searches only the vectors within those corresponding cells.

• Mechanism: Uses an inverted index mapping centroids to member vectors.
• Performance: Search complexity is O(n_probe * cluster_size), where n_probe is the number of cells searched.
• Use Case: Ideal for balanced speed/recall when combined with a secondary quantization step like Product Quantization (PQ).

The primary metric for evaluating candidate generation quality. Recall@K measures the fraction of the true top-K nearest neighbors (from an exhaustive search) that are present in the approximate top-K results returned by the candidate generator.

• Formula: (True positives in retrieved K) / K.
• Interpretation: A Recall@100 of 0.95 means 95 of the true top 100 neighbors were in the candidate set.
• Engineering Impact: Directly trades off with query latency; higher recall typically requires searching more of the index.

A critical hybrid query pattern that constrains candidate generation by metadata. It combines a vector similarity search with conditional filters (e.g., status = 'in_stock' AND price < 50).

• Challenge: Applying filters naively can break the index's proximity assumptions.
• Strategies:
  • Pre-filtering: Apply metadata filters first, then search the subset. Risks missing relevant vectors filtered out early.
  • Post-filtering: Generate vector candidates first, then apply filters. Can reduce result count below K if filters are strict.
• Advanced Solution: Native integrated filtering where the index is aware of metadata partitions.

The optimizer process that determines how to execute a search request. For a candidate generation query with filters and parameters, the query planner selects the most efficient index access path and execution strategy.

• Inputs: Query vector, k, filters, distance metric, and index types available.
• Decisions: Chooses between pre-filtering, post-filtering, or using a specialized filtered index. Adjusts internal parameters like n_probe for IVF or ef_search for HNSW.
• Goal: Minimize P99 latency while meeting the target Recall@K for the given workload.

The core traversal algorithm used in graph-based ANN indexes like HNSW. Beam search maintains a fixed-width priority queue (the 'beam') of the most promising candidate nodes during graph exploration.

• Function: Balances exploration (finding global neighbors) and efficiency (limiting visited nodes).
• Parameter: Beam width is often controlled by the ef_search parameter in HNSW.
• Analogy: Like searching a friendship network by only tracking your top N most promising leads at each step.
• Optimization: Enables dynamic pruning, where unpromising paths are abandoned early.