Inverted Indexing & BM25 Scoring Engine

Inverted indexes and BM25 still win on exact terms: product codes, names and error strings.

Part 1 of 5

Basics

The whole idea first, then the terms the rest of this page uses.

1.1Whole idea

An inverted index maps each term to the documents holding it, so search reads only relevant lists. BM25 then scores each document: rare terms count most, repeated terms help with diminishing returns, and long documents get discounted.

Why it matters

Inverted indexes and BM25 still win on exact terms: product codes, names and error strings.

1.2Key concepts

One idea per card, in plain words.

01Postings list

Holds the documents and term counts for one term.

02IDF

Rewards rare terms: 'NullPointerException' tells you more than 'error'.

03k1

Saturates term frequency. The tenth mention adds far less than the second. Typically 1.2–2.0.

04b

Discounts long documents. 0.75 by default; 0 turns length normalisation off.

Part 2 of 5

Question

What exactly you must answer, and what to settle before you start.

2.1Question

Interviewer

Vector search misses the exact error code ERR_4021 in your logs. Build the sparse index that finds it, and show how a document's score is computed.

Part 3 of 5

Detailed answer

How it works, and how to build or explain it.

3.1Step by step

The mechanism, in the order you would explain it.

  1. Tokenise

    Lowercase and split consistently at index and query time. A mismatch here breaks search silently.

  2. Build postings

    For each term, record every document and its count.

  3. Compute IDF

    ln(1 + (N − df + 0.5) / (df + 0.5)), with N documents and df holding the term.

  4. Score each match

    IDF × tf × (k1 + 1) / (tf + k1 × (1 − b + b × length / average length)).

  5. Sum across terms

    Add the scores for each query term and return the top results.

3.2Code

Working code for the core of it.

Keyword ranking with BM25

Exact terms such as error codes are where vectors do worst and BM25 does best.

bm25.tsTypeScriptCopy
1const tokenize = (s: string) => s.toLowerCase().match(/[a-z0-9]+/g) ?? [];2 3/** Okapi BM25 over an inverted index: term -> list of [doc, term frequency]. */4export class Bm25 {5  private index = new Map<string, [number, number][]>();6  private ids: string[] = [];7  private lengths: number[] = [];8  private k1: number;9  private b: number;10 11  constructor(k1 = 1.2, b = 0.75) {12    this.k1 = k1;13    this.b = b;14  }15 16  add(id: string, text: string): void {17    const doc = this.ids.push(id) - 1;18    const terms = tokenize(text);19    this.lengths.push(terms.length);20    const tf = new Map<string, number>();21    for (const t of terms) tf.set(t, (tf.get(t) ?? 0) + 1);22    for (const [t, n] of tf) {23      if (!this.index.has(t)) this.index.set(t, []);24      this.index.get(t)!.push([doc, n]);25    }26  }27 28  search(query: string, top = 10): { id: string; score: number }[] {29    const N = this.ids.length;30    const avg = this.lengths.reduce((a, b) => a + b, 0) / Math.max(N, 1);31    const scores = new Map<number, number>();32    for (const term of new Set(tokenize(query))) {33      const postings = this.index.get(term) ?? [];34      const idf = Math.log(1 + (N - postings.length + 0.5) / (postings.length + 0.5));35      for (const [doc, tf] of postings) {36        const norm = tf + this.k1 * (1 - this.b + (this.b * this.lengths[doc]) / avg);37        scores.set(doc, (scores.get(doc) ?? 0) + (idf * tf * (this.k1 + 1)) / norm);38      }39    }40    return [...scores]41      .sort((a, b) => b[1] - a[1])42      .slice(0, top)43      .map(([doc, score]) => ({ id: this.ids[doc], score }));44  }45}
45 linesUTF-8TypeScript
Math.log(1 + (N - postings.length + 0.5) / ...)
Inverse document frequency: rare terms count for more.
tf * (this.k1 + 1)
Repeats help, but saturate, so stuffing a term doesn't win.
this.lengths[doc]) / avg
Long documents get discounted, since they match more by chance.

Tested by npm run test:modules.

Part 4 of 5

Q&A

What interviewers ask next. Answer out loud, then open.

4.1Interview questions

Why does term frequency saturate?
Ten mentions rarely mean ten times the relevance. Saturation also blunts keyword stuffing.
When does BM25 beat embeddings?
On exact identifiers, rare names and error codes, which embeddings tend to blur.
Why normalise by length?
A long document holds more terms by chance. Without b, long documents win unfairly.
Part 5 of 5

Extra depth

Edge cases, counterpoints and what to read next.

5.1Edge cases and counterpoints

Includes the strongest argument against this approach.

Show detailsHide details
Analysers
Stemming and stop words help English prose and hurt code. Index identifiers without stemming.
Learned sparse
SPLADE predicts term weights with a model, combining sparse speed with some semantic matching.
Counterpoint
BM25 cannot match synonyms at all. It belongs beside vector search, not instead of it.