TF-IDF & BM25

Lexical Search Fundamentals

Before neural vector embeddings, search engines relied on Lexical Keyword Matching.

Instead of comparing deep neural vectors, lexical algorithms compare exact text tokens between search queries and documents.

┌──────────────────────────┬──────────────────────────┐
│ 1. TF-IDF                │ 2. OKAPI BM25            │
├──────────────────────────┼──────────────────────────┤
│ TF * IDF multiplication. │ Industry standard for    │
│ Linear term frequency    │ keyword search. Adds     │
│ scaling (flawed!).       │ TF Saturation + Document │
│ Simple baseline.         │ Length Normalization.    │
└──────────────────────────┴──────────────────────────┘

1. TF-IDF (Term Frequency - Inverse Document Frequency)

Calculates a relevance score for word $t$ in document $d$ across corpus $D$:

$$\text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \text{IDF}(t, D)$$

1. Term Frequency $\text{TF}(t, d)$: How many times word $t$ appears in document $d$.
2. Inverse Document Frequency $\text{IDF}(t, D)$: Measures word rarity across all $N$ documents:

$$\text{IDF}(t, D) = \log\left( \frac{N}{|{d \in D : t \in d}|} \right)$$

• Common words ("the", "is") appear in all documents $\implies \text{IDF} \approx 0$.
• Rare words ("photosynthesis", "quantum") appear in few documents $\implies \text{IDF}$ is high.

2. Okapi BM25 (Best Matching 25)

BM25 fixes two major weaknesses in raw TF-IDF:

Weakness 1: Linear Term Frequency Flaw

In TF-IDF, if a document mentions "diabetes" 50 times, it scores 50x higher than a document mentioning it 1 time.

BM25 Solution (TF Saturation): Uses non-linear scaling where additional occurrences of a keyword yield diminishing relevance returns.

Weakness 2: Document Length Bias

Long 500-page documents naturally contain more words by accident.

BM25 Solution (Length Normalization): Penalizes long documents, normalizing word counts relative to average corpus document length.

$$\text{BM25 Score}(q, d) = \sum_{i=1}^{|q|} \text{IDF}(q_i) \cdot \frac{f(q_i, d) \cdot (k_1 + 1)}{f(q_i, d) + k_1 \cdot \left( 1 - b + b \cdot \frac{|d|}{\text{avgdl}} \right)}$$

• $k_1$ (typically 1.2 to 2.0): Controls term frequency saturation speed.
• $b$ (typically 0.75): Controls document length penalty strength.

BM25 vs Dense Vector Search

  SEARCH METHOD             STRENGTHS                               WEAKNESSES
  BM25 (Lexical)            Exact SKUs, part numbers, rare names,   Zero semantic understanding
                            acronyms, code identifiers.             ("dog" misses "canine").

  Dense Vector (Semantic)   Captures concepts, synonyms,            Fails on exact serial numbers,
                            paraphrases, and intent.                rare names, and code tokens.

Production Search engines (Elasticsearch, Pinecone, Vespa) use Hybrid Search, combining BM25 and Vector scores using Reciprocal Rank Fusion (RRF).

Say this out loud

TF-IDF weights keywords by multiplying term frequency by inverse document frequency to discount common words. Okapi BM25 improves TF-IDF by adding term frequency saturation and document length normalization. BM25 remains the industry standard for exact keyword search, and is combined with dense vector embeddings in hybrid search pipelines.

Followups to expect

1. What is Reciprocal Rank Fusion (RRF)? A algorithm that merges ranked lists from different search engines (BM25 + Dense Vectors) by scoring items based on their position rank: $\text{RRF Score} = \sum \frac{1}{k + r_i}$.
2. Why does BM25 require zero GPU hardware? BM25 operates on inverted index hash tables stored on CPU disk drives, executing searches in sub-millisecond speeds.