RAG: search that answers · Chapter 3 of 37

Search before AI

By the end of this chapter you can build keyword search from scratch: split text into words, build an inverted index, and rank Paisa Setu's chunks with BM25, the scoring that search engines have used for decades. Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.

  • Part: Why RAG
  • 4 tasks
  • In the all labs plan

The first 2 chapters of RAG: search that answers are free. This one comes with the all labs plan.

Why you need this

Chapter 2 showed that the answer is to send the model a few passages, not 145 documents. So something has to find those passages, out of 866 chunks, in a few milliseconds. Kabir has the questions that matter most: "what does U30 mean", "why is my settlement on hold with SH-03". Merchants type the exact code, and the passage with that code must come first.

What you know so far cannot do it. Asking the model to pick passages means sending it everything again. Checking which chunks contain the question's words finds hundreds, because nearly every chunk has "the", "my" and "payment" in it. You need a score that knows which words matter, and that is BM25. It is also the baseline: every smarter search in this lab must beat it on numbers, or it is not worth its cost.

What you build: 4 tasks

Each task has tests. You write the code in the lab's editor and press Check.

  1. Task 1

    tokenize: words, and codes kept whole

    Lowercase the text and return its words in order. A word is a run of letters a to z and digits; a hyphen between two such runs joins them, so codes like SH-03 and re-KYC stay one word. Everything else (spaces, punctuation, ₹, a plus sign, a hyphen on its own) separates words.

    tokenize('What does UPI error U30 mean?') is ['what', 'does', 'upi', 'error', 'u30', 'mean'], tokenize('Hold SH-03: re-KYC pending (₹2,000).') is ['hold', 'sh-03', 're-kyc', 'pending', '2', '000'], T+1 is ['t', '1'], and empty text is [].

  2. Task 2

    indexChunks: an inverted index

    For every chunk, in order, tokenize its searchText (title, heading and text). Return an Index: ids are the chunk ids in order, lengths how many words each chunk has, avgLength the average of lengths, and postings a Map from each word to a Map from chunk position (0, 1, 2 ...) to how many times the word is in that chunk. A chunk without the word has no entry.

    For all 866 chunks there are 3,403 different words, 'u30' is in 17 chunks, and the average length is about 80.27 words.

  3. Task 3

    idf: how rare a word is

    N is how many chunks the index has (the length of ids), n how many chunks contain the term (the size of its postings, or 0 when it has none). Return Math.log(1 + (N - n + 0.5) / (n + 0.5)).

    For Paisa Setu's chunks, idf of 'the' (in 787 of 866) is about 0.096, idf of 'u30' (in 17) about 3.903, and a word in no chunk gets ln(1 + 866.5 / 0.5).

  4. Task 4 · interview question

    Interview: search, BM25 top k

    For each distinct word of tokenize(query), and each chunk in that word's postings, add idf * tf * (K1 + 1) / (tf + K1 * (1 - B + B * len / avg)) to the chunk's score: tf is the word's count in the chunk, len the chunk's length, avg the index's avgLength. Return the k best (5 by default) as { id, score }, highest first, equal scores in chunk order; [] when no query word is in any chunk.

    search(index, 'what does UPI error U30 mean?', 1) is [{ id: 'help-upi-error-u30-z9#0', score: 13.857... }]. Capitals in the query do not matter, and a word repeated in the query counts once. Score only the chunks in the postings: the Check counts how many chunk lengths you read.

    Arjun will ask: a chunk says refund twelve times, so why does it not come first for a refund question?

What you will learn

  • Tokenising: turning text into the words you search for, with codes like U30 and SH-03 kept whole.
  • An inverted index: from each word to the chunks that have it, so a search looks only at those.
  • BM25: rare words count more (idf), repeating a word helps less and less (k1), and long chunks are held back (b).
  • Top k: the best few chunks, with their scores.

More in Why RAG

Build "Search before AI" yourself

Paisa Setu, a payments company, needs its help centre to answer merchants correctly. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.

The first 2 chapters of RAG: search that answers are free. This one comes with the all labs plan.