Sparse Retrieval

Sparse retrieval is retrieval that scores text by the terms it shares with the query, represented as a vector with one position per vocabulary term in which nearly every position is zero.

The name describes the shape of the representation. A vocabulary of a hundred thousand terms gives a hundred-thousand-position vector, and a short passage has non-zero values only at the handful of positions belonging to words it actually contains. Everything else is empty, and empty positions cost nothing to store or compare.

That emptiness is what makes the method fast at scale. Rather than comparing full vectors, a sparse system keeps an inverted list per term — every location where that term appears — and a query touches only the lists for its own terms. Documents containing none of them are never examined.

The representation is interpretable in a way a dense one is not. Each position corresponds to a specific word, so a score can be decomposed into the contribution of each matched term, and a result can be explained.

Sparse retrieval is the older tradition, predating learned embeddings by decades. It remains the foundation of general-purpose search engines.

In practice

Two distinct families carry the label, and conflating them causes trouble.

Lexical sparse retrieval builds the representation by counting words. Term weights come from a formula rather than a model: how often the term occurs in this text, how rare it is across the corpus, and how long the text is. This is the classical family, and its best-known member is described in the entry on BM25.

Learned sparse retrieval builds the representation with a model that outputs weights over vocabulary positions, and may add terms the text does not literally contain. It keeps the sparse shape and the inverted-list machinery while learning the weights, which places it between the two traditions.

Both share the same operational profile. Retrieval requires exact term matching after normalisation, so behaviour is predictable and a missing result can be traced to a term that failed to match. Adding documents is incremental and cheap. There is no model to version and no space to invalidate.

The pre-processing decides what can be matched at all. Text is lowercased, punctuation is handled, words may be reduced to stems or lemmas, and very common words may be discarded. Query and corpus must be processed identically, and a mismatch between them silently removes matches. This pipeline is the usual explanation for a sparse search that fails on a term plainly present in the text.

Commonly confused with

Dense retrieval. The complement: learned vectors, every position in use, matching by meaning. Sparse retrieval cannot match a paraphrase that shares no words; dense retrieval cannot reliably match an exact identifier. See dense retrieval.

Keyword search. Effectively a synonym for the lexical family, and the term a non-specialist is likelier to use. “Keyword search” sometimes implies literal substring matching with no ranking, which is a narrower thing — sparse retrieval ranks by weighted term overlap rather than merely filtering.

Full-text search. The product-level name for the same capability in databases and search engines. It describes an offered feature; sparse retrieval names the underlying method.

Boolean search. Queries built from AND, OR, and NOT, returning a set rather than a ranking. Sparse retrieval scores and orders; Boolean retrieval only decides membership. Many systems support both over the same index.

Sparse vector, in the numerical sense. A storage format for arrays with mostly-zero values, used throughout scientific computing. Sparse retrieval uses such vectors, but the phrase alone says nothing about retrieval.

Usage notes

“Sparse” is often mistaken for “worse” or “older.” It is a statement about representation shape. On corpora full of identifiers, codes, names, and domain jargon, lexical sparse retrieval frequently beats dense retrieval outright, because those tokens carry their value in being exact.

Which family is meant is often left unstated. A claim about “sparse retrieval” may describe a term-counting formula or a learned model, and their properties differ substantially — most importantly, the learned kind has a model to version and re-run over the corpus, and the lexical kind does not.

The scores are not comparable with dense similarity scores. Lexical scores are unbounded and corpus-dependent; embedding similarities are bounded and model-dependent. Combining the two therefore normally merges by rank position rather than by value. See hybrid search.

Inverted-index terminology leaks into the description. “Posting list,” “term dictionary,” and “analyser” all belong to the implementation, not to the concept, but appear in documentation as though they were part of the definition.

See also

Inverted index · BM25 · Dense retrieval · Hybrid search · Corpus