Sparse Retrieval in vector search

Module 08 · Embeddings & Search · 17 concepts

In depth / 15 lines

Sparse Retrieval, in more detail

Sparse retrieval is keyword search, and it has been the backbone of search for decades.

A document is represented by which vocabulary words it contains.

The vector has one dimension per word, so it is almost entirely zeros.

That is what sparse means, and it is why it can be stored as an inverted index.

An inverted index maps each word to the documents containing it.

Looking up a rare word touches only the handful of documents that hold it.

BM25 is the standard scoring function and remains a very strong baseline.

It weights by how often a term appears, damped so ten mentions is not ten times better.

It penalises terms that appear everywhere and adjusts for document length.

It is excellent for exact matches: names, codes, error strings and identifiers.

It is transparent, since you can see exactly which term caused a match.

It needs no training, no GPU and no embedding step at all.

It fails completely when query and document use different words for one idea.

A search for laptop misses every document that says notebook.

That single weakness is what dense retrieval was built to cover.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Sparse Retrieval

BM25, the formula everything is measured against

\mathrm{score}(q, d) = \sum_{t \in q} \mathrm{IDF}(t) \cdot \frac{f_{t,d} \, (k_1 + 1)}{f_{t,d} + k_1 \left(1 - b + b \frac{|d|}{\overline{|d|}}\right)}

$f_{t,d}$ : how often term $t$ occurs in document $d$ .
$|d|$ : the document length, and $\overline{|d|}$ the average length.
$k_1$ : the saturation parameter, usually 1.2 to 2.0.
$b$ : the length normalisation, usually 0.75.

Every part of that expression is a correction to counting words, and each one earns its place.

\mathrm{IDF}(t) = \ln\left( \frac{N - n_t + 0.5}{n_t + 0.5} + 1 \right)

A term appearing in almost every document tells you nothing, so its weight falls towards zero.

The two corrections that make it work

\lim_{f \to \infty} \frac{f(k_1+1)}{f + k_1} = k_1 + 1

Term frequency saturates. The fifth occurrence of a word adds far less than the second, which stops a document from winning by repetition alone.

b = 1 \implies \text{full length normalisation}, \qquad b = 0 \implies \text{none}

Longer documents contain more of everything, so the count is divided by length relative to the average, with $b$ controlling how aggressively.

Set $b$ too high and short documents dominate. Too low and a long document wins every query by accident of size.

Why it is fast

\text{inverted index} : t \mapsto [(d_1, f_1), (d_2, f_2), \dots]

A term maps to the list of documents containing it, so a query touches only the documents that share a word with it rather than the whole corpus.

O\left(\sum_{t \in q} |posting(t)|\right)

Rare terms have short lists, and rare terms are the ones with high IDF, so the expensive part of the query is also the least useful part.

Skipping and early termination exploit exactly that, which is how a keyword index answers over a billion documents in milliseconds.

One query, in order

Tokenise the query with the same analyser used at indexing time.
Look up the posting list for each term.
Accumulate the BM25 contribution of each term into each candidate document.
Keep the top $k$ by total score.
Return them, with the matched terms available for highlighting.

Learned sparse retrieval

\mathbf{w} \in \mathbb{R}^{|V|}, \quad \text{mostly zero}

SPLADE and similar models predict a weight for every vocabulary term rather than counting occurrences, so a document can be given weight on a word it never contains.

That adds the synonym matching dense retrieval has, while keeping the inverted index and its exact-match behaviour.

\mathcal{L} + \lambda \sum_i |w_i|

An L1 penalty keeps the output sparse, because a dense vector over 30,000 terms would destroy the whole reason for using an inverted index.

The result sits between the two families: better than BM25 on paraphrase, worse than a good bi-encoder on meaning, and far cheaper to serve than either at scale.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

A user searches for a specific part number. Which retrieval method is most likely to find it?

Embeddings & Search

17 concepts in this module, then a graded test with every answer explained.

Study this module →