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.
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.
Holds the documents and term counts for one term.
Rewards rare terms: 'NullPointerException' tells you more than 'error'.
Saturates term frequency. The tenth mention adds far less than the second. Typically 1.2–2.0.
Discounts long documents. 0.75 by default; 0 turns length normalisation off.
Question
What exactly you must answer, and what to settle before you start.
2.1Question
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.
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.
- Tokenise
Lowercase and split consistently at index and query time. A mismatch here breaks search silently.
- Build postings
For each term, record every document and its count.
- Compute IDF
ln(1 + (N − df + 0.5) / (df + 0.5)), with N documents and df holding the term.
- Score each match
IDF × tf × (k1 + 1) / (tf + k1 × (1 − b + b × length / average length)).
- 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.
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}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.
Q&A
What interviewers ask next. Answer out loud, then open.
4.1Interview questions
Why does term frequency saturate?
When does BM25 beat embeddings?
Why normalise by length?
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.