Inverted Index
- Inverted Index
- An inverted index is a data structure that maps each term in a corpus to the list of documents containing it, with optional term frequencies and positions, enabling BM25 and keyword retrieval to find matching documents in milliseconds instead of scanning the full corpus.
An inverted index is a data structure that maps each word to the list of documents containing it, so search engines can return matching documents in milliseconds instead of scanning every document for each query.
What It Is
The reason BM25 and keyword search feel instant on a billion-document corpus is the inverted index. Without it, every query would scan every document looking for matching words — fine for one query, ruinous at scale. The inverted index flips the workload: instead of asking “which words are in this document,” it asks “which documents contain this word?” For anyone building a hybrid-search RAG pipeline, the inverted index is the engine on the keyword side, paired with HNSW or IVF on the vector side.
The structure has two pieces. The term dictionary lists every distinct word in the corpus. Each entry points to a posting list — the document IDs where that word appears, usually with the term’s frequency in each document and sometimes its positions. When BM25 ranks documents for the query “vector database scaling,” the engine walks just three posting lists, intersects them, computes scores using TF-IDF-style statistics, and returns the top results. According to Stanford IR Book, this turns retrieval from O(corpus size) into O(matching documents).
Modern implementations add two layers on top. Posting lists are delta-encoded and chunked into skip-list blocks so the engine can leap over irrelevant segments without decoding them. Weak-AND (WAND) and BlockMax WAND go further, pruning entire blocks that cannot beat the current top-k score. According to Weaviate Blog, BlockMax WAND in Weaviate v1.30 reduced BM25 query latency by up to 94% on a 5.4-million-document benchmark. The same machinery now runs inside vector databases — Weaviate, Milvus, LanceDB — so hybrid search can fan out to BM25 and dense vectors over the same data without a separate search engine.
How It’s Used in Practice
For most teams building RAG today, the inverted index shows up the moment they enable hybrid search in their vector database. A query goes out twice: once to the dense-vector index for semantic matches, once to the inverted index for exact keyword and BM25 matches. The two result sets are merged with a fusion function. Teams rarely touch the index directly — it is configured per field at collection time and updated in the background. The visible effect is that queries with rare jargon, product codes, or proper names start returning the right documents that pure semantic search kept missing.
The second common encounter is sparse-learned retrieval. Models like SPLADE and ELSER produce term-weight vectors that look different from BM25 statistics but live in the same inverted index. According to Elastic Search Labs, the structure is identical — only the weights change. Swapping between classical BM25 and learned sparse retrieval becomes a tuning knob, not a rebuild.
Pro Tip: Most hybrid-search problems start with a stale or misconfigured inverted index, not with the vector side. Check that your tokenizer matches your domain — default English tokenization is rough on code, product IDs, and multi-language content — and that updates flush on a sane schedule. Vector embeddings get the attention; the keyword half quietly carries half the recall.
When to Use / When Not
| Scenario | Use | Avoid |
|---|---|---|
| Hybrid-search RAG combining BM25 with dense vectors | ✅ | |
| Pure semantic similarity search with no exact-match needs | ❌ | |
| Domain with rare jargon, error codes, or product SKUs | ✅ | |
| Tiny in-memory corpus under a few thousand documents | ❌ | |
| Sparse-learned retrieval with SPLADE or ELSER | ✅ | |
| Image or audio similarity search with no text terms | ❌ |
Common Misconception
Myth: Vector databases made inverted indexes obsolete — embeddings handle everything keywords used to. Reality: Modern vector databases ship inverted indexes alongside HNSW because dense vectors miss exact matches: error codes, product names, rare technical terms. According to Weaviate Docs, the recommended hybrid-search default fuses BM25 results from an inverted index with vector similarity from HNSW.
One Sentence to Remember
The inverted index is a fifty-year-old data structure now promoted from search-engine internals to first-class citizen in your vector database — every BM25, sparse-learned, and hybrid retriever in your RAG stack runs on top of it.
FAQ
Q: What is the difference between an inverted index and a vector index? A: An inverted index maps terms to documents for exact and BM25 keyword matching. A vector index like HNSW maps points in embedding space for semantic similarity. Hybrid search uses both together.
Q: Do I need an inverted index if I use a vector database? A: According to Weaviate Docs, modern vector databases ship inverted indexes built in for BM25. You enable BM25 on a field at collection creation and queries automatically fan out to both indexes.
Q: What does BlockMax WAND do? A: According to Weaviate Blog, BlockMax WAND prunes entire blocks of an inverted index that cannot beat the current top-k score. In Weaviate v1.30 it reduced BM25 latency by up to 94% on benchmark data.
Sources
- Weaviate Docs: Inverted indexes — Weaviate Documentation - reference for inverted-index concepts as implemented inside a modern vector database.
- Weaviate Blog: BlockMax WAND: How Weaviate Achieved 10x Faster Keyword Search - documentation of the BlockMax WAND optimization and its measured latency impact.
Expert Takes
The inverted index is the simplest powerful idea in retrieval — invert the relationship between documents and terms, and lookup costs collapse from corpus-wide scans to posting-list walks. BM25 ranking sits on top of this same structure, treating term frequency and document length as ingredients of a probabilistic relevance score. SPLADE and ELSER reuse the same machinery with learned weights. Same data structure, decades of optimization compounding underneath it.
Treat the inverted index as a contract, not a black box. Tokenizer choice, analyzer pipeline, and field-level BM25 parameters all live in the spec — the agent calling your search tool only knows what your schema describes. Most “search returns the wrong things” tickets I see come from drift between what the index was built to handle and what the queries now look like. Write the analyzer rules down, version them, and review them when your domain changes.
The market quietly merged two product categories. Search engines built around inverted indexes used to compete with vector databases built around HNSW. Now every serious vector database ships both, and every modern search engine ships dense vectors. Buyers are no longer choosing between keyword and semantic — they are choosing whose hybrid story is most operable. Vendors still selling pure-vector or pure-keyword stacks for general-purpose RAG are running out of room.
What gets indexed shapes what can be found. The inverted index is built from a tokenizer’s view of language — its stopword list, its stemming rules, its handling of casing and punctuation. Every one of those choices is a quiet editorial decision about which terms become first-class signals and which dissolve into the corpus. Audit the analyzer pipeline before you trust the relevance scores. The index is not neutral; it never was.