sparse retrieval
In plain wordsFinding documents by the words they contain, giving more weight to rare, telling words — the classic way search engines work.
Retrieval in which queries and documents are represented as sparse vectors over a vocabulary — one dimension per term, almost all zero — and scored by weighted term overlap, typically through an inverted indexinverted index, n.: A lookup table that lists, for every word, all the documents containing it — like the index at the back of a book — so a search engine can find matches almost instantly. that lists the documents containing each term. Classic weighting schemes such as TF-IDFTF-IDF, abbr.: A simple score for picking out the words that characterize a document: a word counts for more the more often it appears there, and for less the more of the collection's other documents also use it. and BM25BM25, prop. n.: A decades-old formula that search engines use to score how well a document matches a query, rewarding rare query words and repeated matches — with diminishing returns — and correcting for long documents. are unsupervised and need no training data. Learned sparse retrievers (for example DeepCT, doc2query and SPLADE) use a neural network to assign term weights and to add related terms a document does not literally contain, keeping inverted-index efficiency while narrowing the vocabulary-mismatch gap. Sparse retrieval excels at exact matches — names, codes, rare terms — and is cheap, interpretable and robust across domains, but misses paraphrases that share no words with the query.
Sparse retrieval nailed the error code ERR_4012 that the embedding search kept missing.
Origin
Term-weighted keyword retrieval dates from the 1950s–70s (Hans Peter Luhn, Karen Spärck Jones, Gerard Salton). The retronym 'sparse retrieval' became common from about 2019–2020 to contrast such methods with neural dense retrievaldense retrieval, n.: Finding relevant documents by turning the question and every document into lists of numbers that capture meaning, then picking the documents whose numbers are closest to the question's.; SPLADE (Thibault Formal, Benjamin Piwowarski and Stéphane Clinchant, SIGIR 2021) popularized learned sparse retrieval.
Related
- BM25BM25, prop. n.: A decades-old formula that search engines use to score how well a document matches a query, rewarding rare query words and repeated matches — with diminishing returns — and correcting for long documents.
- TF-IDFTF-IDF, abbr.: A simple score for picking out the words that characterize a document: a word counts for more the more often it appears there, and for less the more of the collection's other documents also use it.
- inverted indexinverted index, n.: A lookup table that lists, for every word, all the documents containing it — like the index at the back of a book — so a search engine can find matches almost instantly.
- dense retrievaldense retrieval, n.: Finding relevant documents by turning the question and every document into lists of numbers that capture meaning, then picking the documents whose numbers are closest to the question's.
- hybrid searchhybrid search, n.: Searching two ways at once — by exact keywords and by meaning — and merging the results, so you catch precise matches like product codes as well as differently worded matches.
- information retrievalinformation retrieval, n.: The study and engineering of search: how to organize huge piles of documents so that the few that matter to someone's question can be found and ranked quickly. AI systems rely on it to look things up.
- dense retrievaldense retrieval, n.: Finding relevant documents by turning the question and every document into lists of numbers that capture meaning, then picking the documents whose numbers are closest to the question's.
Sources
- Formal, T., Piwowarski, B. & Clinchant, S. (2021). SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking. SIGIR 2021. arXiv:2107.05720. arxiv.org/abs/2107.05720
Mentioned in
retrieval-augmented generationretrieval-augmented generation, n.: Giving an AI an open-book exam: before answering, it looks up relevant passages in a set of documents and bases its reply on them, often citing where each point came from., BM25BM25, prop. n.: A decades-old formula that search engines use to score how well a document matches a query, rewarding rare query words and repeated matches — with diminishing returns — and correcting for long documents., dense retrievaldense retrieval, n.: Finding relevant documents by turning the question and every document into lists of numbers that capture meaning, then picking the documents whose numbers are closest to the question's., hybrid searchhybrid search, n.: Searching two ways at once — by exact keywords and by meaning — and merging the results, so you catch precise matches like product codes as well as differently worded matches., inverted indexinverted index, n.: A lookup table that lists, for every word, all the documents containing it — like the index at the back of a book — so a search engine can find matches almost instantly., semantic searchsemantic search, n.: Search that understands what you mean, not just the words you typed, so a search for 'cheap places to stay' also finds 'budget hotels'., sparsitysparsity, n.: The property of being mostly zeros or mostly switched off. AI systems exploit it by skipping the empty parts, so they need less memory and computation., TF-IDFTF-IDF, abbr.: A simple score for picking out the words that characterize a document: a word counts for more the more often it appears there, and for less the more of the collection's other documents also use it., vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's., stemmingstemming, n.: Cutting words down to a common root so that variants count as the same word — 'connected', 'connecting' and 'connection' all become 'connect' — to help search and text analysis., vector space modelvector space model, n.: An early, still-influential idea for search: treat every document and query as an arrow in a space with one direction per word, and rank documents by how closely their arrows point the same way as the query's.