Candidate Generation

The primary objective is to maximize recall—the fraction of all relevant documents that are retrieved—while maintaining strict latency budgets typically under 100 milliseconds. This stage trades precision for coverage, accepting that many candidates will be irrelevant. Techniques like Approximate Nearest Neighbor (ANN) search and inverted index lookup are employed because they operate in sub-linear time, making them viable for corpus sizes exceeding one billion documents.

Candidate generation often combines results from heterogeneous retrieval systems to overcome individual weaknesses:

• Dense Vector Search: Captures semantic similarity using embeddings from models like DPR or ColBERT.
• Sparse Lexical Search: Uses BM25 or Learned Sparse Retrieval for exact keyword matching and handling of rare terms.
• Metadata Filtering: Applies structured constraints like date ranges or document types to prune the candidate set before or after vector search. This ensemble approach ensures robustness against vocabulary mismatches and semantic gaps.

Efficient candidate generation relies on specialized data structures that avoid exhaustive corpus scans:

• Hierarchical Navigable Small World (HNSW): A graph-based ANN index providing logarithmic search complexity by traversing multi-layered proximity graphs.
• Product Quantization (PQ): Compresses high-dimensional vectors into compact codes, dramatically reducing memory footprint for billion-scale indexes.
• Inverted Index: Maps each vocabulary term to a postings list of document IDs, enabling constant-time Boolean and ranked retrieval for sparse representations.

Raw user queries are rarely optimal for direct index lookup. A pre-processing pipeline transforms them to improve match probability:

• Query Rewriting: Expands or reformulates the query into multiple alternative versions to cover different phrasings.
• Intent Classification: Categorizes the query to trigger domain-specific retrieval logic or metadata filters.
• Query Embedding Generation: Encodes the processed query into a dense vector using the same model that indexed the document corpus, ensuring representation alignment.

When multiple retrieval sources contribute candidates, their raw scores are uncalibrated and cannot be directly compared. Fusion algorithms solve this:

• Reciprocal Rank Fusion (RRF): Merges ranked lists by assigning a score based on the reciprocal of each document's rank position, requiring no score calibration.
• Weighted Sum Fusion: Combines normalized scores using pre-defined weights reflecting each system's trustworthiness.
• Score Calibration: Transforms raw scores into probabilities using techniques like Platt scaling before fusion.

Metadata constraints can be applied at different stages of the retrieval pipeline, each with distinct trade-offs:

• Pre-Filtering: Applies filters to the index before vector search, ensuring only valid documents are considered. This guarantees results satisfy constraints but can be computationally expensive if filters are highly selective.
• Post-Filtering: Performs ANN search first, then applies filters to the top results. This is faster but risks returning empty result sets if the initial semantic matches do not satisfy the metadata criteria.

A probabilistic bag-of-words retrieval function that ranks documents by estimating the relevance of term frequencies. It accounts for document length normalization and term saturation.

• Mechanism: Calculates TF-IDF-like scores with non-linear term frequency saturation.
• Key Benefit: Provides a robust, computationally cheap baseline for lexical matching.
• Role: The standard sparse retrieval component in hybrid systems, excelling at exact keyword and rare term matching.

A class of algorithms that trade a small amount of accuracy for significant speed improvements when finding the closest vectors in high-dimensional embedding spaces.

• HNSW: A graph-based algorithm constructing a multi-layered navigable structure for logarithmic time complexity search.
• Product Quantization (PQ): A compression technique that decomposes vectors into sub-vectors and quantizes them using a learned codebook to reduce memory footprint.
• Role: The computational backbone enabling scalable dense vector candidate generation.

An algorithm that merges multiple ranked result lists into a single ranking by assigning a score based on the reciprocal of each document's rank position.

• Formula: score(d) = Σ 1 / (k + rank_i(d)) where k is a constant (typically 60).
• Key Benefit: Effectively balances contributions from heterogeneous retrieval systems without requiring score calibration.
• Role: The primary fusion method for combining dense and sparse candidate sets into a unified list for re-ranking.

A technique using neural models to predict term importance weights for vocabulary tokens, generating sparse vector representations.

• Mechanism: Models like SPLADE use MLM-based expansion and logarithmic saturation to predict token weights.
• Key Benefit: Combines the lexical precision of an inverted index with the contextual awareness of deep learning.
• Role: A modern alternative to BM25 that bridges the gap between sparse and dense retrieval.

A cascading pipeline architecture where an initial, computationally cheap first-pass retrieval stage generates a broad set of candidates, which is then progressively refined.

• Stage 1 (Candidate Generation): High-recall, low-precision retrieval using ANN or BM25 to narrow from billions to hundreds.
• Stage 2 (Re-ranking): Expensive cross-encoder models score the pruned candidate set for high precision.
• Key Benefit: Balances the opposing demands of massive scale and deep semantic understanding.