Dense and Sparse Retrieval

Interview answer (say this first). Dense retrieval embeds the query and the documents, then searches by meaning, so it matches paraphrases and synonyms. Sparse retrieval matches exact terms and ranks them with BM25, so it is precise for names, codes, acronyms, and rare words. They fail in opposite ways, which is why production systems usually run both.

Why this exists

Imagine a support search box. Two users type two different things, and the system fails both of them for opposite reasons.

Failure one: good meaning, no shared words. The user asks:

how do I stop the service from dying

The best document says:

Handling uncaught exceptions so the application does not terminate

A keyword search finds almost nothing. The words dying and uncaught exceptions do not overlap at all. The document has the answer; the search box never shows it. This is the lexical gap: the user and the document describe the same thing with different words.

Failure two: exact token, blurred meaning. A second user asks about a specific error:

what does ERR-4032 mean

An embedding model turns ERR-4032 into a vector. That vector points roughly at “error” and “code”, because the model saw those words during training. It does not have a precise direction for this one identifier. So the semantic search returns ten generic error pages, and the one page that actually contains ERR-4032 may rank low. Embeddings deliberately smooth away rare exact strings.

Now the important part: the two failures need opposite fixes. Failure one needs meaning. Failure two needs exact matching. A retrieval system that only does one of them will keep failing the other. That is why engineers say retrieval is a portfolio of methods, not a single method.

Note:

The one-sentence purpose. Dense retrieval searches by meaning; sparse retrieval searches by exact terms. You need to know which failure mode your queries have before choosing. Agents hit the same split: looking up a tool or error code needs exact matching, while recalling past conversation needs meaning.

Start from zero

Before going further, here are the words this topic keeps using.

Two confusions cause most mistakes, so pin them down now:

• Sparse vs dense is about the vector shape, not the quality. Sparse means “one slot per vocabulary item, almost all zeros”. Dense means “a short learned vector, mostly non-zero”. Both can be good.
• The index retrieves; the scorer ranks. The inverted index finds candidate documents that contain the query terms. BM25 then puts them in order. They are two separate jobs.

The core idea

Picture a library with two very different librarians.

The first librarian keeps a concordance: an alphabetical list of every word in every book, with page numbers. Ask “which books contain the word ERR-4032?” and she answers instantly and exactly. Ask “which books are about crashing services?” and she is stuck, because she only knows words, not ideas. She is sparse retrieval.

The second librarian has read everything and remembers themes. Ask about a crashing service and she points you at the chapter on uncaught exceptions, even though it never uses the word “dying”. She is wonderful with meaning, but if you ask for the exact string ERR-4032 she shrugs, because she remembers the gist, not the characters. She is dense retrieval.

You want both librarians at the desk, and you compare their answers.

flowchart LR
    Q["Query"] --> SP["Sparse path<br/>tokenize + stemming"]
    Q --> DP["Dense path<br/>embedding model"]
    SP --> SI["Inverted index<br/>term -> postings"]
    SI --> SB["BM25 score<br/>lexical match"]
    DP --> DV["Query vector"]
    DV --> DS["ANN search<br/>cosine similarity"]
    SB --> R["Two candidate lists"]
    DS --> R
    R --> M["Merge (hybrid search)"]

That table is the topic. Everything else is detail about the two columns.

How it works

The sparse path

1. Tokenize. Split each document into tokens.
2. Normalise. Lowercase, drop punctuation, and usually remove stop words.
3. Stem or lemmatize. Reduce running, runs, and ran toward run, so different forms match.
4. Build the inverted index. For every term, store a postings list: the document ids that contain it, and optionally the positions and counts. This is what lets a search skip most of the corpus.
5. Parse the query. Turn the user’s words into terms joined by operators: & (and), | (or), ! (not), and <-> (adjacent).
6. Collect candidates. The index gives every document that contains at least one query term.
7. Rank with BM25. Score each candidate and return the top ones.

The BM25 formula. For a query q and document d:

$$ \text{BM25}(q,d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{tf(t,d),(k_1+1)}{tf(t,d) + k_1\left(1-b+b,\frac{|d|}{\text{avgdl}}\right)} $$

with

$$ \text{IDF}(t) = \ln!\left(1 + \frac{N - n(t) + 0.5}{n(t) + 0.5}\right) $$

Read each piece in plain words:

• tf(t,d) is how often the term appears in this document. More occurrences usually means more relevant.
• The fraction saturates. Because tf appears in both the top and the bottom, going from 1 to 2 occurrences helps a lot, but going from 20 to 21 barely helps. That curve is controlled by k1 (commonly 1.2–2.0, often 1.5). A high k1 lets repetition keep adding score for longer.
• |d| / avgdl is the document’s length relative to the average. Long documents contain more words by chance, so BM25 divides them down. b (usually 0.75) controls how strong this penalty is. b=0 disables it; b=1 applies it fully.
• IDF(t) weights rare terms more. A term in almost every document gets a low weight; a term in one document gets a high weight. This is why BM25 is precise on codes and names.
• N is the number of documents and n(t) is how many contain the term. The +0.5 smoothing stops the value from exploding when a term is very rare or very common.

Warning:

PostgreSQL’s ts_rank is not BM25. PostgreSQL ranks a document against a query locally. It has no corpus-wide document frequency at query time, so it cannot compute IDF. Add more documents and ts_rank for the same document does not change. If you need real BM25 inside PostgreSQL, use an extension such as ParadeDB’s pg_search or put the index in a dedicated search engine.

The dense path

1. Choose an embedding model. It fixes the vector dimension and the whole index.
2. Embed every chunk once. Store the vector next to the text and metadata.
3. Build a vector index. HNSW or IVFFlat lets you search a large collection approximately, without comparing every vector.
4. Embed the query with the same model. A different model produces a vector in a different space, and the comparison becomes meaningless.
5. Find the nearest vectors. Usually by cosine similarity, or by dot product if vectors are normalised.
6. Return the top-k chunks. These become candidates for the answer.

The two paths are independent. They use different indexes, different scores, and different failure modes — which is exactly why merging them later (hybrid search) works.

The syntax you will use

Sparse: build a tsvector and a GIN index in PostgreSQL. A tsvector stores the document’s normalised terms and their positions. A GIN index makes @@ lookups fast.

ALTER TABLE docs ADD COLUMN tsv tsvector GENERATED ALWAYS AS (
  to_tsvector('english', coalesce(title,'') || ' ' || coalesce(body,''))
) STORED;

CREATE INDEX docs_tsv_gin ON docs USING GIN (tsv);

The generated column updates itself on write, so you never forget to re-index a row.

Sparse: parse queries into tsquery. Different functions produce different operator shapes.

SELECT plainto_tsquery('english', 'reset password');       -- 'reset' & 'password'
SELECT phraseto_tsquery('english', 'reset password');      -- 'reset' <-> 'password'
SELECT websearch_to_tsquery('english', 'reset password');  -- 'reset' & 'password'
SELECT websearch_to_tsquery('english', '"reset password"');-- 'reset' <-> 'password'
SELECT websearch_to_tsquery('english', 'reset OR password');-- 'reset' | 'password'

websearch_to_tsquery is the safest default: it mirrors search-engine syntax, including quotes, OR, and leading - for exclusion.

Sparse: match and rank. @@ is the match operator; ts_rank and ts_rank_cd score the match.

SELECT id, title
FROM docs
WHERE tsv @@ websearch_to_tsquery('english', 'reset password')
ORDER BY ts_rank(tsv, websearch_to_tsquery('english', 'reset password')) DESC;

ts_rank_cd uses “cover density”: it rewards query terms that appear close together. ts_rank only counts occurrences and weights.

Sparse: weight important columns. Terms in the title should count more than terms in the body. setweight labels positions with A–D, and the ranking function can weight those labels.

SELECT setweight(to_tsvector('english', title), 'A') ||
       setweight(to_tsvector('english', body),  'B');
-- 'password':3A 'reset':1A ... (A = title, B = body)

Then pass weights to the ranker: ts_rank('{0.1,0.2,0.4,1.0}', tsv, query) maps D, C, B, A.

Sparse: BM25 in plain Python. This is the formula above, written out. It is the mental model you should be able to reproduce on a whiteboard.

import math
from collections import Counter

corpus = ["python tutorial for beginners",
          "advanced python tutorial with decorators and generators",
          "a short python tutorial",
          "python python python tutorial",
          "javascript guide for beginners"]
tokenized = [doc.split() for doc in corpus]
N = len(tokenized)
avgdl = sum(len(d) for d in tokenized) / N          # 4.6

def idf(term: str) -> float:
    df = sum(1 for d in tokenized if term in d)
    return math.log(1 + (N - df + 0.5) / (df + 0.5))  # Lucene variant

def bm25(query: str, k1: float = 1.5, b: float = 0.75) -> list[tuple[int, float]]:
    scores = []
    for i, doc in enumerate(tokenized):
        tf, dl = Counter(doc), len(doc)
        score = 0.0
        for term in query.split():
            if term not in tf:
                continue
            numerator = tf[term] * (k1 + 1)
            denominator = tf[term] + k1 * (1 - b + b * dl / avgdl)
            score += idf(term) * numerator / denominator
        scores.append((i, score))
    return sorted(scores, key=lambda pair: -pair[1])

Dense: embed and search in Python. The model turns text into vectors; cosine similarity turns vectors into a ranking.

from sentence_transformers import SentenceTransformer
import numpy as np

model = SentenceTransformer("all-MiniLM-L6-v2")
docs = ["How to reset your password", "Factory reset the router"]
doc_vecs = model.encode(docs, normalize_embeddings=True)

q = model.encode(["I forgot my login"], normalize_embeddings=True)[0]
scores = doc_vecs @ q                 # normalized vectors: dot == cosine
best = int(np.argmax(scores))         # 0 -> the password document

Dense: search in PostgreSQL with pgvector. <=> is cosine distance (lower is closer). Create an HNSW index for large tables.

CREATE INDEX chunks_vec_hnsw ON chunks USING hnsw (embedding vector_cosine_ops);

SELECT id, content, embedding <=> :query_vector AS distance
FROM chunks
ORDER BY distance
LIMIT 5;

IDs and acronyms: pick the right text-search config. english stems words; simple only lowercases. For identifiers, simple keeps the token intact.

SELECT to_tsvector('english', 'running runs ran');  -- 'ran':3 'run':1,2
SELECT to_tsvector('simple',  'running runs ran');  -- 'ran':3 'running':1 'runs':2

Examples: simple to real

Example 1 — run BM25 and watch IDF and term frequency work. Using the corpus above, python appears in 4 of 5 documents and javascript in 1.

idf(python)     = 0.2877     (common term, low weight)
idf(javascript) = 1.3863     (rare term, high weight)

query "python tutorial":
  doc3: 0.8013   # repeats "python", so tf wins
  doc0: 0.6112
  doc2: 0.6112
  doc1: 0.4660   # longer document, so length normalisation lowers it
  doc4: 0.0000   # no query term at all

doc1 is the longest document. It contains both query terms once, exactly like doc0, but its score is lower because of b. doc3 repeats python and rises to the top. That is term frequency and length normalisation visible in numbers.

Example 2 — the length-normalisation knob b. Same query python tutorial, same corpus, only b changes:

b=0.00 -> doc3=0.767  doc0=0.575  doc2=0.575  doc1=0.575
b=0.75 -> doc3=0.801  doc0=0.611  doc2=0.611  doc1=0.466
b=1.00 -> doc3=0.813  doc0=0.624  doc2=0.624  doc1=0.438

At b=0 all documents with one occurrence tie, no matter how long they are. As b grows, the long document sinks. b=0.75 is the usual compromise.

Example 3 — the lexical gap in action. Sparse retrieval with TF-IDF, no expansion. The query shares no words with the right document.

original query: the service keeps dying unexpectedly
  top 3: d4 0.0000, d3 0.0000, d2 0.0000     # no term overlap at all

expanded query: the service keeps dying unexpectedly exceptions errors crash failure
  top 3: d0 0.4082, d4 0.0000, d3 0.0000     # d0 is "handle uncaught exceptions..."

A pure term matcher cannot cross the lexical gap. You bridge it by expanding the query, or by using dense retrieval, as Example 4 shows.

Example 4 — dense retrieval crosses the gap. A sentence embedding model places “I forgot my login” near “How to reset your password” even though the words differ. Both vectors are 384-dimensional; the cosine similarity is high because the sentences mean similar things. This is the failure one fix.

Example 5 — exact identifiers need sparse. Stemming changes tokens, but identifiers survive best under the simple config.

to_tsvector('english', 'SKU-4032 API v2 error XJ-9')
  -> '-4032':2 '-9':7 'api':3 'error':5 'sku':1 'v2':4 'xj':6
to_tsvector('simple',  'SKU-4032 API v2 error XJ-9')
  -> '-4032':2 '-9':7 'api':3 'error':5 'sku':1 'v2':4 'xj':6

Both configs keep 4032 and xj searchable. An embedding model, in contrast, has no dedicated direction for ERR-4032; it returns generic error text. For codes, ticket numbers, and product SKUs, sparse wins by a wide margin.

Example 6 — PostgreSQL’s rank does not use the corpus. Add 500 more documents, all containing password, and re-run ts_rank on the original row:

rank before (4 documents total)        = 0.31284000
rank after  (504 documents, 503 with   = 0.31284000   # unchanged!
             the term "password")

ts_rank is identical because it never looks at the rest of the corpus. BM25’s IDF for the same term collapses as the corpus grows:

idf("password") with N=4,   df=4   = 0.105361
idf("password") with N=504, df=503 = 0.002975   # 35x smaller

This is the single most important practical difference between PostgreSQL’s built-in full-text search and a real BM25 engine.

Example 7 — choose by query type. This is the decision table to reconstruct in an interview.

In production

• Measure both, then decide. Build a small labelled query set, run dense and sparse separately, and record Recall@K and MRR for each. Choosing by intuition is how teams ship the wrong retriever.
• The query mix decides the architecture. A support desk full of error codes needs strong sparse. A consumer assistant full of casual questions needs strong dense. Most real systems are a mix, which is the argument for hybrid search.
• Chunking hurts sparse more than people expect. BM25 needs a term to be in the same chunk as the query. Split a document badly and the term and its context land in different chunks. Keep overlap.
• Stemming is a trade-off. It improves running/run matching but can merge unrelated terms and mangle product names. For mixed text, use simple on identifier fields and english on prose.
• Stop words are not always safe to drop. Dropping not changes meaning and breaks negation. Modern systems often keep stop words in phrases and remove them only from loose matching.
• ts_rank has no IDF. Do not expect PostgreSQL’s built-in ranking to down-weight common terms. On a large corpus, common terms will dominate results unless you filter them or use a BM25 extension.
• Keep the exact-match field separate. Index identifiers and names in their own column with the simple config and boost it. Mixing codes and prose in one tsvector dilutes both.
• The planner may ignore a GIN index on small tables. A sequential scan is cheaper for a few rows. This is not a bug; it appears once the table grows.
• Sparse scoring is not comparable across queries. BM25 scores are unbounded and query-dependent. Rank position is comparable; raw scores are not. Normalise before fusion.
• Rare terms dominate BM25. A term in one document gets a huge IDF and can outrank a genuinely better document. This shows up in noisy corpora with typos and one-off tokens.
• Dense retrieval has no vocabulary limit but a real input limit. Text beyond the model’s max length is silently truncated, so a long chunk may be embedded from its first part only.
• Version the embedding model with the index. Re-embedding is expensive and changing the model without re-embedding silently returns wrong neighbours.

Tip:

Debugging shortcut. If a clearly relevant document is missing entirely, ask: does the query share a term with it (sparse), and does the embedding model place it near the query (dense)? Which question fails tells you which path is broken.

Interview questions

1. What is the difference between dense and sparse retrieval?

Answer. Sparse retrieval represents text as a high-dimensional vector with one slot per vocabulary item, almost all zero, and matches on shared exact terms. BM25 ranks those matches. Dense retrieval represents text as a short learned embedding and matches on meaning, so it can find paraphrases and synonyms. Sparse is precise on rare tokens; dense is robust to wording.

Follow-up: “Which one is better?” Neither. They have opposite failure modes, so the honest answer is “it depends on the query mix”, and the common production answer is both, fused by hybrid search.

Trap. Saying dense is “more advanced, so it replaces sparse”. Embeddings are bad at exact identifiers, and sparse is often cheaper and more interpretable. Dense did not replace sparse; it joined it.

2. Explain BM25.

Answer. BM25 scores a document for a set of query terms by summing, over each term, three things: the term’s IDF (rare terms weigh more), a saturating term-frequency factor (repeats help, but with diminishing returns), and a length-normalisation factor (long documents are penalised). The two knobs are k1 for saturation and b for length normalisation.

Follow-up: “Why saturate term frequency?” Because the tenth occurrence of a word says much less than the second. A linear term-frequency score lets one repeated word dominate. The (k1+1) numerator over tf + k1*(...) compresses the curve.

Trap. Claiming PostgreSQL’s ts_rank is BM25. It is not; it has no corpus-wide IDF. You need a BM25 extension or a search engine for true BM25.

3. What do k1 and b control, and what are good defaults?

Answer. k1 controls how quickly extra occurrences stop helping; higher values let repetition keep adding score. b controls length normalisation; b=0 ignores length and b=1 applies the full penalty. Typical defaults are k1=1.5 and b=0.75, then tune on labelled data.

Follow-up: “When would you change them?” Short fragments such as titles may want less length normalisation. Corpora where repetition is meaningful may want a higher k1. Tune with retrieval metrics, not vibes.

Trap. Treating the defaults as laws. They are starting points, and the best values depend on your documents and queries.

4. Why does dense retrieval fail on identifiers like ERR-4032?

Answer. The embedding model maps text into a continuous space trained on general language. It has no special direction for one rare identifier, so it places ERR-4032 near the general concept “error” and returns all error pages. Sparse retrieval indexes the exact token, so it can require it.

Follow-up: “How would you fix it?” Keep an exact-match path: index identifiers in a simple-config tsvector column, or a keyword field in a search engine, and boost it. Some teams also prepend the identifier to the chunk before embedding.

Trap. Assuming a bigger embedding model fixes it. Scale does not create a precise direction for an arbitrary string.

5. What is an inverted index, and why is it fast?

Answer. It maps each term to a postings list of the documents that contain it. A query only looks up its own terms and skips documents that cannot match, instead of scanning every document. That is sublinear in the corpus size, which is why keyword search scales.

Follow-up: “What does a postings list store?” At minimum document ids. Often positions for phrase and proximity queries, and term frequencies for scoring. PostgreSQL’s tsvector stores positions with A–D weight labels.

Trap. Confusing the inverted index (the data structure that finds candidates) with BM25 (the formula that ranks them). They are separate.

6. When does sparse retrieval beat dense?

Answer. When the query turns on an exact token: error codes, product SKUs, ticket numbers, names, acronyms, and rare technical terms. Sparse also wins when the vocabulary is out of domain, because an embedding model may never have learned it. And sparse is more interpretable: you can show which terms matched.

Follow-up: “And when does dense win?” When the user paraphrases, uses synonyms, or writes a full natural-language question. Dense also handles typos and morphology more gracefully than exact matching.

Trap. Forgetting the cold-start vocabulary problem. A brand-new product name is not in the embedding model but is trivially indexed by sparse retrieval.

7. How would you decide between dense and sparse for a new system?

Answer. Collect a representative query set with known relevant documents. Run both retrievers, and measure Recall@K and MRR separately. Look at which queries each one fails. If the failures are disjoint, which they usually are, plan for hybrid search rather than picking one.

Follow-up: “What if you have no labelled data?” Sample real query logs, have a human mark the best few documents per query, and grow the set. Even 50 labelled queries expose the pattern.

Trap. Benchmarking on a public dataset whose queries look nothing like yours. Retrieval quality is domain-specific.

8. What is the lexical gap, and what are two ways to bridge it?

Answer. The lexical gap is when a query and a relevant document mean the same thing but share no words. Two fixes: use dense retrieval, which compares meaning rather than terms; or transform the query, by adding synonyms and related terms (query expansion) so the sparse index can match. Production systems often do both.

Follow-up: “What is a risk of query expansion?” Adding the wrong synonyms drifts the query and lowers precision. Expansion should be measured, not assumed.

Trap. Thinking the lexical gap is solved forever by embeddings. Embeddings reduce it for common language but do not remove it, especially for jargon and new terms.

Remember this

• Sparse matches terms; dense matches meaning. They fail in opposite ways, so know your query mix.
• BM25 = IDF × saturating term frequency × length normalisation, with knobs k1 (saturation) and b (length).
• PostgreSQL’s ts_rank is not BM25: it has no corpus-wide IDF. Use pg_search or a search engine for real BM25.
• Exact codes, IDs, and acronyms go to sparse; paraphrases and questions go to dense.
• Debug by asking which path failed: no shared term (sparse) or far-away embedding (dense).