🗄️ Inverted index

Concept · 20 key papers · all concepts

Part of: 🗨️ Natural language processing

An inverted index is a data structure that maps each term of a vocabulary to a postings list of the documents containing it, usually with in-document frequencies and positions. A search engine can then find matching documents without scanning the whole collection.

Also: inverted file, reverse index

What it is

A book index sends you from a word to the pages where it appears. An inverted index does the same for a document collection. It has two parts:

• A dictionary holds every distinct term.
• Each term points to a postings list. Each entry in that list names one document containing the term. It often also stores how many times the term occurs there and at which positions.

It is called "inverted" because it reverses the natural order of the data. The collection stores, for each document, its words. The index stores, for each word, its documents. It is the core structure of most text search engines and a central tool of information retrieval.

Take three tiny documents. D1 is "the cat sat on the mat", D2 is "the dog sat", and D3 is "a cat and a dog". Counting word positions from 1, part of the index looks like this:

A query for "cat" reads one short list and returns D1 and D3. It never touches D2.

The key idea

Building the index

Construction is a pipeline:

1. Tokenization cuts each text into tokens.
2. Normalisation lowercases the tokens and may apply stemming or lemmatization. Stemming lets "sits" and "sitting" share an entry, while only lemmatization maps the irregular "sat" to "sit".
3. Every occurrence becomes a triple of term, document id and position.
4. The triples are sorted by term and then by document id.
5. Runs of identical terms are merged into postings lists.

For collections that do not fit in memory, the textbook method is to sort blocks separately and then merge them, much like an external merge sort.

Boolean queries

A conjunctive query such as cat AND dog intersects two postings lists. Both lists are sorted by document id, so the intersection walks them in step and keeps the ids they share. Here that is D3. The cost grows with the lengths of the lists, not the size of the collection. Engines start with the shortest list, and skip pointers let them jump over long stretches. OR is a union of lists, and NOT is a difference.

The same set logic appears higher up the stack. Open-domain question answering (QA) answers questions from the whole web rather than from a given passage. One such system breaks a complex question into simpler search queries. It then combines their answers through composition and conjunction, which is set intersection (Talmor & Berant 2018). Relation extraction from the web has been bootstrapped by fetching sentences that mention both members of a seed entity pair. That step is in effect a conjunctive query (Bunescu & Mooney 2007).

Ranked retrieval

Most users want a ranked list, not a set. The classic weighting is tf-idf:

w(t, d) = tf(t, d) · log(N / df(t))

Here tf(t, d) is how often term t occurs in document d, N is the number of documents, and df(t) is the number of documents containing t. Both tf and df can be read straight from the postings: tf is the stored frequency, and df is the length of the list.

The Okapi BM25 function adds saturation and length normalisation:

score(q, d) = Σ_{t ∈ q} idf(t) · tf(t,d)·(k₁+1) / (tf(t,d) + k₁·(1 − b + b·|d|/avgdl))

In this formula:

• q is the query, and the sum runs over its terms t.
• idf(t) is a variant of the log(N / df(t)) factor from tf-idf above. It rewards terms that occur in few documents.
• |d| is the length of document d, and avgdl is the average document length in the collection.
• k₁ controls how quickly repeated occurrences stop adding to the score.
• b sets how strongly long documents are penalised.

Ponte and Croft proposed ranking documents by the probability that each document's language model would generate the query. Their experiments compared it with the tf-idf weighting of the INQUERY retrieval system on ad hoc topics from TREC, the Text REtrieval Conference. Query-likelihood ranking came out ahead without hand-tuned heuristics (Ponte & Croft 1998). It needs exactly the statistics an inverted index already holds.

Compression

Postings lists for common words are long, because term frequencies follow Zipf's law. That length makes compression worthwhile. Each list is sorted by document id, so the gaps between successive ids are small, and engines store those gaps instead of the ids. The list 3, 7, 11 becomes 3, 4, 4. Small gaps fit into few bits.

Variable-byte coding writes each gap in 7-bit chunks, with one flag bit marking the last byte. Gamma and Golomb codes take other approaches. Newer codes are built for SIMD (single instruction, multiple data) processing, which decodes many values per instruction. Each trades decoding speed against size in its own way.

The resulting index can be much smaller than the text it covers. In one Arabic retrieval study, Lucene indexed about 180 MB of text into roughly 37 MB (Abderrahim 2013).

Positional indexes

Positions make phrase and proximity search possible. A query for "cat sat" first intersects the two lists. It then keeps only documents where the position of "sat" is exactly one more than a position of "cat". That is D1, positions 2 and 3. Positions cost space, but they also support proximity scoring. The early Google design used proximity cues and font information as ranking signals (Brin & Page 1998).

History and founding papers

Inverted files were used in library and document-retrieval systems from the 1950s and 1960s. In the 1960s, Gerard Salton's SMART system developed vector-space weighting on top of them. Karen Spärck Jones (1972) introduced inverse document frequency, and Robertson and Walker (1994) gave the BM25 family its standard form. Witten, Moffat and Bell (1994) made index compression a central engineering topic, and Zobel and Moffat (2006) later surveyed the field.

Two 1998 papers mark the start of the web era. Brin and Page described the full crawling, indexing and query architecture of a web-scale engine. Their prototype could build an index over at least 24 million pages in under a week (Brin & Page 1998). In the same year, Ponte and Croft founded the language-modelling approach to ranking described above (Ponte & Croft 1998).

Web indexes soon became research instruments in their own right. Keller and Lapata used search-engine hit counts to estimate frequencies for bigrams unseen in a corpus. At the time, Google indexed roughly 3,033 million pages (Keller & Lapata 2003).

How it is used today

Lexical engines

Open-source engines built on Lucene remain the default backbone. The TAGME entity linker stores about 3 million Wikipedia anchors and 2.7 million sense pages in Lucene indexes (Ferragina & Scaiella 2010). Domain search tools are also built on such indexes, including one for a large Ukrainian dictionary (Krashtan 2023).

Many systems also query commercial web search engines, whose indexes stay hidden, and use the returned results as context:

• Named entity recognition on short texts (Wang et al. 2021).
• Detecting text paraphrased by language models (Nguyen-Son et al. 2026).
• Benchmark construction, as in SearchQA. There a TF-IDF Max baseline reached only 12.7% unigram accuracy on the test set (Dunn et al. 2017).

Readability prediction has been motivated by search engines that could match results to a reader's level (Collins-Thompson & Callan 2004; Vajjala & Meurers 2012).

Beside dense vector indexes

Word embeddings and Transformer encoders brought approximate nearest-neighbour indexes over dense vectors. These sit beside inverted indexes rather than replacing them.

• ColBERT can re-rank BM25 candidates or retrieve end to end from a vector index. Shrinking its embeddings cut storage from 286 GiB to 27 GiB. The cost was about one point of MRR@10, the mean reciprocal rank of the first relevant passage within the top 10 (Khattab & Zaharia 2020).
• PseudoSeer holds BM25 and k-nearest-neighbour (k-NN) indexes in one Elasticsearch deployment. The k-NN side is built on HNSW (hierarchical navigable small world) graphs. BM25 held its own against pretrained encoders there, and fusing the two rankings gave the best recall (Toksoz et al. 2026).
• Learned sparse models keep the inverted index but let a network choose the term weights. Their test suite was BEIR, a set of heterogeneous zero-shot retrieval benchmarks. Across 14 of its datasets, DistilSPLADE-max averaged 0.500 NDCG@10 (normalised discounted cumulative gain over the top 10 results), against 0.440 for tuned BM25 (Formal et al. 2021).

A different line drops the separate index altogether. The Differentiable Search Index (DSI) trains a T5 (Text-to-Text Transfer Transformer) model to memorise the corpus and emit document ids directly. In a zero-shot setting on Natural Questions, it beat BM25 by about 14 points of Hits@1, the share of queries whose top result is correct (Tay et al. 2022).

Benchmarks show where exact term matching still matters:

• In a Lean theorem search engine, adding informal text hurt on queries that depend on lexical matching of Lean terms (Gao et al. 2024).
• On a Chinese web benchmark, dense retrievers transferred poorly across domains (Qiu et al. 2022).
• On BRIGHT, sparse and dense retrievers, open and proprietary alike, all struggled with queries that need reasoning (Su et al. 2024).

Retrieval for language models

Retrieval-augmented generation (RAG) has put search engines, and the inverted indexes behind them, inside large language model pipelines:

• SeeKeR writes a query, sends it to a web search API, and grounds its replies in the returned documents (Shuster et al. 2022).
• FreshPrompt inserts dated search results into the prompt (Vu et al. 2023).
• WebGLM pairs search-engine retrieval with a fine-tuned dense ranker (Liu et al. 2023).
• Search-R1 uses reinforcement learning to teach models when to issue queries (Jin et al. 2025).
• SeaKR retrieves only when the model's internal uncertainty is high (Yao et al. 2025).

Keyword mining over millions of documents also feeds taxonomy induction (Meisenbacher & Norlander 2026).

Open questions

• Hybrid design. It is still unclear how best to combine postings-based and vector-based candidates under a fixed latency budget. In one pseudocode search engine, simple fusion of BM25 and learned embeddings gave the best recall. How well such settings carry over to other tasks remains open (Toksoz et al. 2026).
• Vocabulary. Learned sparse models index units from a subword tokenization vocabulary and add expansion terms. This raises the question of whether the "terms" of an index should be chosen by a network rather than by a tokenizer (Formal et al. 2021).
• Updating. A model-as-index such as DSI must be retrained to add documents. Inverted indexes absorb new documents by merging new postings (Tay et al. 2022).
• Reach. Search indexes surface top-level pages more readily than deeply nested ones. Agents that click through sites can complement them (Wu et al. 2025).
• Relevance beyond overlap. Queries that require reasoning to connect them to relevant documents remain hard for every index type (Su et al. 2024).

Key papers

The works this page cites, the most cited first; citations as counted by OpenAlex plus the papers of this library that cite the work, read 2026-10-24.

Related concepts

• TF-IDF — Term frequency–inverse document frequency (TF-IDF) is a weighting scheme that scores how important a word is to one document in a…
• Latent semantic indexing — Latent semantic indexing (LSI) is a retrieval and text-analysis method that factorizes a weighted term–document matrix with a truncated…
• Stemming — Stemming is the reduction of inflected or derived word forms to a common stem, usually by stripping affixes with rules or statistics, so…
• Retrieval-augmented generation — Retrieval-augmented generation (RAG) is a technique in which a language model first fetches relevant passages from an external collection…

More papers

Topics: 🔍 Information retrieval & search

Shelves: 🤖 Artificial Intelligence

Updated 24 October 2026

This page in Markdown → https://md.research.elamur.ai/free/en/concepts/inverted-index/