Sparse retrieval judges relevance by matching words. A passage is a vector of word counts where almost every entry is zero, which is why it is called sparse. The standard scorer is Best Match 25 (BM25), from the term weighting topic.

Running example

A bank's compliance assistant has thousands of policy passages and gets 2 kinds of question:

  • Question A: "What must happen before we onboard a senior government official?" The answer passage never uses these words, it talks about politically exposed persons (PEPs)
  • Question B: "What does error KYC-E052 mean?" The answer is one entry in a list of near-identical error codes, so the exact token matters

Sparse retrieval handles Question B well and Question A badly.

BM25 in 3 rules

RuleExampleBM25 ingredient
Rare words are more informative"AML" tells us more than "customer", which appears everywhereIDF
Repeats help, with diminishing returnsThe 10th mention of "AML" adds far less than the 1stSaturation, controlled by
Long documents mention everything eventuallyA 300 page manual contains "AML" somewhere by chanceLength normalisation, controlled by

The result is one score per passage for this query, and passages are ranked by it. Scores are only comparable within the same query.

Worked example

Query "AML threshold" with passages, average length 100 words, , . "AML" appears in 10 passages and "threshold" in 100.

  • D1 has 100 words, with "AML" once and "threshold" 3 times, and scores about 8.17
  • D2 has 300 words, with "AML" 3 times and no "threshold", and scores about 5.01

D1 wins although D2 says "AML" three times:

  • covering both query words beats repeating one word (rule 2)
  • D2 is long, so its length term is instead of (rule 3)
  • the rare word "AML" carries most of the weight (rule 1)

Inverted index

  • it works like the index at the back of a textbook, where each word points to the list of passages that contain it
  • a query reads only the lists of its own words, so the work does not grow with the size of the whole collection
  • this makes keyword search very fast

Strengths and weakness

  • strength: exact matches on rare tokens such as product codes, clause numbers and error codes (Question B)
  • weakness, vocabulary mismatch: "anti-money laundering" does not match "AML", and "senior government official" does not match "PEP" (Question A)
  • learned sparse retrieval (for example SPLADE) uses a transformer to add related words to each passage, so it keeps the fast index and reduces the mismatch

Code

import re
import numpy as np
from rank_bm25 import BM25Okapi
 
def tokenize(text):
    """Lower-case and split into tokens, keeping hyphens so 'kyc-e052' stays one token."""
    return re.findall(r"[a-z0-9§\-]+", text.lower())
 
# DOCS is a list of passage strings
bm25 = BM25Okapi([tokenize(d) for d in DOCS], k1=1.2, b=0.75)   # builds the index once
 
def sparse_search(query, k=50):
    """Return the indices of the k highest-scoring passages."""
    scores = bm25.get_scores(tokenize(query))   # one BM25 score per passage
    return list(np.argsort(-scores)[:k])        # sort from high to low, keep the top k

Notes:

  • the tokenizer decides what counts as one word, so a plain split() can break codes like KYC-E052 or hide them behind punctuation
  • BM25Okapi defaults to k1=1.5 and b=0.75, and the values are set above to match the lecture
  • np.argsort(-scores) sorts from high to low because argsort sorts from low to high

The score of one query word can also be written by hand, to see the 3 rules without a library:

def idf(n_docs_with_term, N):
    """Rule 1: rare words get a large weight, common words a small one."""
    return np.log((N - n_docs_with_term + 0.5) / (n_docs_with_term + 0.5) + 1)
 
def tf_part(f, doc_len, avg_len, k1=1.2, b=0.75):
    """Rules 2 and 3: saturating term frequency with document length normalisation."""
    length_term = k1 * (1 - b + b * doc_len / avg_len)   # above k1 for long docs, below k1 for short ones
    return f * (k1 + 1) / (f + length_term)              # grows with f but levels off at k1 + 1
 
N, avg_len = 1000, 100
d1 = idf(10, N) * tf_part(1, 100, avg_len) + idf(100, N) * tf_part(3, 100, avg_len)
d2 = idf(10, N) * tf_part(3, 300, avg_len)
print(round(d1, 2), round(d2, 2))   # 8.17 5.01

For an average length passage, 1, 3 and 10 mentions give term values of about 1.0, 1.57 and 1.96, which shows the saturation.

Sparse retrieval fails on meaning, and the way to match meaning is Dense Retrieval.