BM25 and lexical search

An inverted index maps each term to a postings list — the set of documents containing it, usually with per-document term frequency and positions. “Inverted” because it inverts the natural document→terms mapping into terms→documents. Retrieval for a query then intersects/unions the postings lists of the query terms and scores only those documents, instead of scanning the corpus. Postings are stored sorted by document id and heavily compressed (delta + variable-byte / PForDelta), and query evaluation uses skip pointers and dynamic pruning (WAND / block-max WAND) to avoid fully scoring documents that cannot enter the top-k. This structure is what makes keyword search over billions of documents sub-millisecond.

For query Q and document D:

score(D, Q) = sum over terms t in Q of:

    IDF(t) * ( f(t, D) * (k1 + 1) ) / ( f(t, D) + k1 * (1 - b + b * |D| / avgdl) )

where:
    IDF(t) = ln( 1 + (N - n(t) + 0.5) / (n(t) + 0.5) )

    f(t, D)  = frequency of term t in document D
    |D|      = length of D in tokens
    avgdl    = average document length in the corpus
    N        = total number of documents
    n(t)     = number of documents containing t
    k1       = term-frequency saturation parameter (typ. 1.2 - 2.0)
    b        = length-normalization strength, 0..1 (typ. 0.75)

• IDF(t) — rare terms carry more signal; the +0.5 smoothing keeps it well-defined and this form stays non-negative for all n(t) < N.
• The TF factor — increases with f(t, D) but saturates: controlled by k1. Going from 1 to 2 occurrences matters a lot; 20 to 21 barely moves the score. This is BM25’s key improvement over raw TF-IDF.
• (1 - b + b * |D|/avgdl) — length normalization. b = 1 fully normalizes by length (a term in a long document is discounted); b = 0 ignores length. It prevents long documents from winning just by containing more words.

Classic TF-IDF scores a term as roughly tf * idf, which has two problems BM25 fixes:

• Unbounded term frequency — under raw TF, a document that repeats a keyword 100 times scores ~100x a document that uses it once, which does not match how relevance actually works. BM25’s f / (f + k1 * ...) shape asymptotically approaches k1 + 1, so extra repetitions give diminishing returns.
• No principled length handling — TF-IDF either ignores length or divides by it crudely. BM25’s b parameter interpolates between “no normalization” and “full normalization” and is tuned to the corpus.

BM25 is a probabilistic-retrieval model (derived from the Robertson–Sparck Jones weighting), not just a heuristic, which is part of why it has stayed the lexical baseline for 30 years.

Before indexing or querying, text passes through an analyzer: character filters → tokenizer → token filters (lowercasing, stopword removal, stemming or lemmatization, synonym expansion, ASCII-folding, n-grams). Bugs are silent because a mismatch produces fewer results, not an error:

• Index-time and query-time analyzers must agree — if you stem at index time but not at query time, “running” (query) never matches “run” (indexed).
• Over-aggressive stemming conflates distinct terms (“university”/“universe” → “univers”).
• Stopword removal breaks phrase queries and hurts for queries that are stopwords (“The Who”, “to be or not to be”).
• Language detection — applying an English analyzer to German text mangles compounds.
• Custom synonyms applied one-directionally or with multi-word terms behave surprisingly.

Always test with the analyze API on real examples.

BM25 wins on:

• Exact-match needs — error codes, function names, SKUs, legal citations, proper nouns, identifiers. Dense models blur these together.
• Rare / out-of-vocabulary terms the embedding model never learned.
• Long-tail and keyword-style queries, and any domain far from the embedding model’s training distribution.
• Zero training, full interpretability, trivial updates, cheap — a strong baseline for free.

BM25 loses on:

• Vocabulary mismatch — “car” vs “automobile”, “how do I cancel” vs “termination procedure”. No term overlap, no score.
• Semantic / conceptual queries where the answer paraphrases rather than repeats.
• Cross-lingual retrieval.

This complementarity is exactly why hybrid search exists (next subtopic).

Learned sparse models (SPLADE, uniCOIL) use a transformer to produce, for each document, a sparse vector over the vocabulary — most entries zero, non-zero entries are learned term weights plus term expansions (the model adds related terms the document did not literally contain). It is stored in an inverted index and scored like BM25 (dot product of sparse vectors), so it inherits BM25’s efficiency and exact-match strength, but the learned weighting and expansion close much of the vocabulary-mismatch gap. Trade-offs: it needs a GPU to encode, the expansions inflate the index, and it is still weaker than dense on purely conceptual matching. It is increasingly used as the sparse half of a hybrid system instead of raw BM25.

Defaults k1 = 1.2 and b = 0.75 (Elasticsearch/Lucene defaults) are good for typical prose and should be the starting point.

• k1 — raise it (toward 2.0+) when repeated terms genuinely indicate relevance (long technical documents); lower it (toward 0.5) for short, uniform documents (product titles, tweets) where a term appears at most once or twice anyway.
• b — lower it when document length is meaningful rather than incidental (a longer answer really is more comprehensive); raise toward 1.0 when long documents are just padded and you want them discounted. For very short fields (names, titles) b near 0 often helps.

Tune against a labeled query set with a grid search on nDCG@10, per field if fields differ in character. Do not tune on anecdotes — the effect sizes are small and easy to fool yourself about.