The Inverted Index: Keyword Search, Instant

Part of the free Generative AI course on LogicWiz, module: Finding the Needle: Hybrid Search & Retrieval.

Episode 42: The Inverted Index — How Keyword Search Is Instant

"How does Google search a billion pages in half a second?" Arjun asked. Anjali smiled. "It never reads the pages at query time. It reads a list."

The Problem: Find a Word Without Reading Everything

Assume an e-commerce company has a million products. A shopper types "tea." Simple question: which products even mention that word?

The obvious way is to open every product's text and check for "tea" — a million reads, on every single search. It's the brute-force wall from Episode 40 all over again, this time for words. Google faces the same thing across billions of pages, yet answers in half a second. The secret is that it never reads the pages at query time — it reads a pre-built list. This episode builds that list.

But first, one thing has to be clear: what does "a word" even look like to a search engine?

Two Ways to Turn Text Into Numbers: Dense vs. Sparse

Everything in a vector search engine is a vector — just a list of numbers. There are two very different kinds, and keyword search needs the second one. Take the tiny sentence "fresh green tea."

Dense vector — what an embedding model produces. It's a short list — a few hundred numbers — and every slot is filled, like [0.21, -0.67, 0.05, …]. Those numbers capture the sentence's meaning, but no single slot stands for a word, so you can't read the words back out. This is what HNSW searches.

Sparse vector — picture a giant checklist with one checkbox for every word in the dictionary: around 30,000 boxes, one for apple, one for book, one for tea, and so on. To turn a piece of text into a sparse vector, you go down the whole checklist and tick the box for each word that appears, leaving every other box blank. A blank box is a 0; a ticked box is a 1.

For "fresh green tea" you tick exactly three boxes — fresh, green, tea — and the other ~29,997 boxes stay blank (0).

So why the sea of zeros? Because the checklist has to be long enough to hold any word that could ever show up anywhere in the entire catalogue — every brand name, every spec, every adjective across a million products. But one short sentence only ever uses a tiny handful of those words. Every word it doesn't use — apple, book, coffee, zebra, and 29,000 more — gets a 0. That's literally what "sparse" means: mostly empty — a few 1s floating in a sea of 0s. And because every box is a specific word, you can read the sentence's words straight off the ticked boxes.

{{visual:dense-vs-sparse}}

So keyword search is sparse-vector search: find the documents whose ticked boxes overlap your query's ticked boxes. That's the exact-match, "does this word appear?" question — a completely different job from dense/semantic search.

Why HNSW Can't Do This Job

HNSW is tuned for short, fully-packed dense vectors. A sparse vector is 30,000-dimensional and ~99.8% zeros — handing that to HNSW wastes enormous memory and time chewing through zeros. Sparse search needs its own structure, the one traditional search engines like Elasticsearch have used for decades: the inverted index.

The Solution: Forward Index vs. Inverted Index

Start with the obvious layout, the forward index: for each document, list all the words it contains. Here are five tiny product titles (real ones have dozens of words — these are short just to keep the example readable):

Doc 1 → [tea, leaf] · Doc 2 → [coffee, bean] · Doc 3 → [tea, coffee] · Doc 4 → [cocoa, nib] · Doc 5 → [coffee, cup]

To answer "which docs contain 'tea'?" you'd have to scan every document's word list. Slow.

Now invert it — flip the mapping so each word points to the documents that contain it:

Now "which docs contain 'tea'?" is an instant lookup — read the list [1, 3], done. No document scanning, ever. That flip, term → documents, is the inverted index.

{{visual:inverted-index}}

Multi-Term Queries: Set Intersection

Search for "tea AND coffee"? Grab each term's list and take the set intersection — the doc IDs that appear in both:

tea → [1, 3] ∩ coffee → [2, 3, 5] = [3] (only Doc 3, "tea coffee", has both)

Search for "tea" alone → [1, 3] instantly. The cost of a query is per term, proportional to how many words you typed — not to how many documents exist. That's why lexical search stays near-instant even as the corpus explodes into the billions. You'll build this exact index — and its intersection search — yourself in this lesson's lab.

💡 How are the term lists built and scored? Behind the scenes each document is first scored with something like TF-IDF or BM25 (weighing rare, meaningful words higher than "the" and "will"), producing a forward index of term→score; that gets inverted into the searchable structure above.

Dense vs. Sparse Search, Side by Side

You've now seen how each vector looks; here's how each one behaves as a search — the contrast that sets up hybrid search:

The Wall Lexical Search Still Hits

The inverted index is fast and precise — but it's still literal. If the shopper typed "bright" and the product says "luminous," the term "bright" simply isn't in that document's lists, so the product is never retrieved. The vocabulary-mismatch problem from Episode 39 is baked into how the index works.

Classic lexical methods (BM25, TF-IDF) can only match terms that are actually present. To fix that without abandoning the speed of sparse search, we need a way to put related words into the index too — even words the document never used.

What Nova Learns Next

Nova has fast semantic search and fast lexical search — but lexical is still trapped by exact wording. In Episode 43 we teach the sparse side to think: term expansion and SPLADE, learnable sparse embeddings that add synonyms the text never contained.