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
| Rule | Example | BM25 ingredient |
|---|---|---|
| Rare words are more informative | "AML" tells us more than "customer", which appears everywhere | IDF |
| Repeats help, with diminishing returns | The 10th mention of "AML" adds far less than the 1st | Saturation, controlled by |
| Long documents mention everything eventually | A 300 page manual contains "AML" somewhere by chance | Length 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 kNotes:
- the tokenizer decides what counts as one word, so a plain
split()can break codes likeKYC-E052or hide them behind punctuation BM25Okapidefaults tok1=1.5andb=0.75, and the values are set above to match the lecturenp.argsort(-scores)sorts from high to low becauseargsortsorts 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.01For 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.