Inverted Index

Definition

An inverted index maps each term to the documents that contain it. This lets you start a search with a term and look up the IDs of matching documents, without scanning every document’s terms.

Each term has a postings list. Each posting points to a matching document and can also store the term’s frequency or its positions within the document. A positional inverted index includes these positions to enable phrase and proximity queries. Terms are generated by text analysis, which may involve lowercasing or stemming.

Simple example

Suppose you have three short documents:

If you count word positions starting at 1, the index entries for two terms look like this:

A query for rollback AND deployment intersects the document IDs, returning A and C. The phrase query “rollback deployment” also checks word positions. It matches A, where the words are adjacent and in order, but skips C, where “failed” comes between them.

Why it matters

A retriever can read the postings lists for the query terms instead of scanning every document’s text. Common terms may still have long lists, so the lookup cost depends on the terms and the query.

In a RAG system, an inverted index supports lexical retrieval of passages containing a specific error code or configuration key, as long as text analysis preserves the identifier. The indexed IDs can point to chunks instead of whole source documents.

One important nuance

An inverted index organizes matches, but a ranking function like BM25 uses term statistics to score them. The index alone does not tell you which matching passage best answers a question.

Use an inverted index for efficient term lookup and, when it stores positions, for phrase matching. Don’t rely on literal term postings alone to retrieve a relevant passage that shares no indexed terms with the query.