Sparse Retrieval

The core scoring mechanism is based on exact term overlap between a query and a document. Classic algorithms like BM25 and TF-IDF calculate relevance by analyzing:

• Term Frequency (TF): How often a query term appears in a document.
• Inverse Document Frequency (IDF): How rare or common a term is across the entire corpus.
• Document Length Normalization: Penalizing very long documents that might accumulate many matches by chance. This results in a precise, interpretable score for each query-document pair.

Each document is represented as a vector where each dimension corresponds to a unique term (word) in the vocabulary. The vector is sparse, meaning most dimensions have a value of zero, as any single document contains only a small subset of the total vocabulary.

• Dimensionality: Equals the size of the vocabulary (can be 100k+ dimensions).
• Non-zero values: Represent the weighted importance of terms present (e.g., BM25 score).
• Efficiency: Sparse representations enable efficient storage and computation using inverted indexes, as only non-zero entries are processed.

The primary data structure enabling fast sparse retrieval. An inverted index maps each term (vocabulary word) to a postings list of all documents containing that term and the term's weight within each.

• Query Processing: For a query, the system fetches the postings lists for each query term.
• Intersection/Union: Scores are aggregated across these lists to rank documents.
• Speed: Allows retrieval from massive corpora in milliseconds, as the search complexity scales with the number of query terms, not the total number of documents.

A key advantage is full interpretability. The relevance score is directly decomposable into contributions from individual matched terms.

• Debugging: Engineers can trace why a document ranked highly (e.g., 'it contains the exact phrase "neural network" 5 times').
• Predictability: Matches are based on surface form, making system behavior deterministic and controllable.
• Vocabulary Mismatch Limitation: This is also its weakness—it cannot match synonyms or related concepts without exact term overlap (e.g., 'car' vs. 'automobile').

Sparse retrieval operates on a fundamentally different principle than modern dense retrieval.

• Representation: Sparse uses lexical, sparse vectors vs. Dense uses semantic, dense embeddings (e.g., from a transformer).
• Matching: Sparse uses exact term overlap vs. Dense uses vector similarity (e.g., cosine) in a continuous space.
• Strengths: Sparse excels at keyword search, precision for specific terms, and efficiency. Dense excels at semantic search and handling vocabulary mismatch.
• Hybrid Retrieval: Modern systems often combine both to leverage their complementary strengths.

TF-IDF (Term Frequency-Inverse Document Frequency) is a foundational weighting scheme. It emphasizes terms frequent in a document but rare in the corpus.

BM25 (Best Match 25) is the state-of-the-art probabilistic sparse retrieval function. It improves upon TF-IDF with:

• Saturation: Term frequency benefits saturate, preventing very frequent terms from dominating.
• Length Normalization: More sophisticated handling of document length via tunable parameters (k1, b).
• Robustness: Proven empirically robust across diverse text corpora and remains a standard baseline in IR research and production.

TF-IDF is a statistical weighting scheme used to evaluate the importance of a word in a document relative to a collection. It is the foundational scoring function for sparse retrieval.

• Term Frequency (TF): Measures how often a term appears in a document.
• Inverse Document Frequency (IDF): Penalizes terms that appear in many documents (common words like 'the').
• The final score is the product: TF * IDF. A high score indicates a term is frequent in a specific document but rare across the corpus, making it a good keyword discriminator.

It is computationally efficient and forms the basis for the Bag-of-Words model, but it lacks semantic understanding and cannot handle synonyms or polysemy.

BM25 (Okapi BM25) is a probabilistic retrieval function that ranks documents based on query terms appearing in each document. It is a state-of-the-art, robust improvement over TF-IDF.

Its core innovations include:

• Term Frequency Saturation: Uses non-linear saturation to prevent very high term frequencies from dominating the score disproportionately.
• Document Length Normalization: Penalizes or rewards documents based on their length relative to the average document length in the corpus, controlled by parameters b and k1.
• Query Term Weighting: Can incorporate IDF for query terms.

BM25's parameters (k1, b) allow tuning for specific datasets. It is the default algorithm in search engines like Elasticsearch and Lucene for text relevance scoring.

BM25F is an extension of BM25 designed for documents with structured fields (e.g., title, body, author). It aggregates evidence from multiple fields to compute a final relevance score.

How it works:

• Each field (e.g., title, abstract) can be assigned a different boost weight reflecting its importance.
• The term frequency for a query term is calculated per field, normalized by field length, and then multiplied by the field's boost.
• These weighted frequencies are summed across all fields before being plugged into the BM25 scoring formula.

This allows a search system to prioritize matches in a title field over matches in a body field, mimicking how a human would assess relevance. It is crucial for searching semi-structured data like product catalogs or research papers.

The Query Likelihood Model is a classic probabilistic retrieval model based on Language Modeling. It ranks documents by the probability that the document's language model generated the query: P(Q | D).

Core Mechanism:

1. A simple language model (e.g., a multinomial distribution) is estimated for each document D, typically using maximum likelihood estimation (term frequencies).
2. To avoid zero probabilities for query terms not in the document, the model uses smoothing (e.g., Jelinek-Mercer or Dirichlet prior).
3. The probability of the query under the smoothed document model is calculated, often as the sum of log probabilities.

While conceptually different from BM25, the two are closely related; the Dirichlet-smoothed QLM has been shown to be a form of TF-IDF weighting. It provides a direct probabilistic interpretation of retrieval.

SPLADE (Sparse Lexical and Expansion) and uniCOIL are modern neural models that produce learned sparse representations. They bridge the gap between traditional sparse retrieval and dense retrieval.

Key Innovations:

• They use a Transformer-based encoder (like BERT) to map a text passage to a sparse, high-dimensional vector in the vocabulary space.
• The model learns to assign weights to vocabulary terms, including related terms not explicitly present (expansion) and down-weighting unimportant terms (pruning).
• SPLADE uses a log-saturation effect and FLOPS regularization to induce sparsity.
• uniCOIL is a simplified version that uses a linear layer on top of [CLS] token embeddings.

These models achieve the interpretability of sparse retrieval (you can see which terms contributed) with the semantic power of neural models, often outperforming BM25 and competing with dense retrievers.

An Inverted Index is the fundamental data structure that enables efficient sparse retrieval at scale. It is a mapping from terms (words) to the list of documents containing that term.

Structure:

• Dictionary: A sorted list of all unique terms (the vocabulary) in the corpus.
• Postings Lists: For each term, a list of document identifiers (DocIDs) where the term appears, often accompanied by payloads like term frequency (tf) and positions.

Retrieval Process:

1. For a query, look up the postings list for each query term.
2. Perform a merge operation (like conjunctive AND or disjunctive OR) on these lists to find candidate documents.
3. For each candidate, compute the relevance score (e.g., BM25) using the stored tf and global idf statistics.

This structure allows queries to be resolved by scanning only the lists for query terms, not the entire corpus. It is the backbone of every major search engine.

Hybrid retrieval is a search strategy that combines the results from both sparse (e.g., BM25) and dense retrieval methods to improve overall recall and precision. It leverages the lexical precision of sparse methods with the semantic understanding of dense methods.

• Implementation: Typically uses a weighted sum of scores (e.g., score_hybrid = α * score_sparse + (1-α) * score_dense).
• Architecture: Often implemented as a two-branch system where results from separate indexes are merged and re-scored.
• Benefit: Mitigates the weaknesses of either approach alone, providing robust performance across diverse query types.

Reranking is a two-stage retrieval process where a large set of candidate items is first retrieved using a fast method (sparse or dense), and then a more powerful, computationally expensive model reorders the top candidates. The reranker is typically a cross-encoder that processes the query and document text together.

• Cross-Encoder: A single model that takes the concatenated query and document as input to produce a direct relevance score, enabling deep interaction analysis.
• Purpose: Drastically improves precision at the top of the ranked list (e.g., Precision@10).
• Cost: Too slow for full corpus search, hence its use as a second-stage refinement.

TF-IDF is a classic statistical measure used to evaluate the importance of a word to a document in a corpus. It forms the historical foundation for sparse vector representations.

• Term Frequency (TF): Measures how frequently a term appears in a document.
• Inverse Document Frequency (IDF): Measures how rare or common a term is across the entire corpus. Common words (e.g., "the") receive low IDF scores.
• Sparse Vector: A document's TF-IDF vector is high-dimensional and sparse, with non-zero values only for terms present in the document.

An inverted index is the core data structure that enables efficient sparse retrieval. It maps each term (or token) to a list of all documents containing that term, along with metadata like term frequency and position.

• Function: Allows rapid lookup of documents containing specific query terms without scanning every document.
• Query Processing: For a multi-term query, the search engine retrieves the posting lists for each term and intersects/merges them to find candidate documents.
• Scale: Used by all major search engines (Elasticsearch, Apache Lucene) to power keyword search at internet scale.