The recording

The inverted index

Information Retrieval for AI

Session 2 - Wed 02 Sep 2026

KAIST AI - Seong Joon Oh

Announcements

Groups. Propose your own on the first-day survey by Mon 14 Sep. Remaining places filled at random after that.
Discussions begin Wed 30 Sep, with BEIRBEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval ModelsThakur, Reimers, Ruckle, Srivastava & Gurevych - 2021 - NeurIPS D&Balso session 1, 8, 13. The first review is due Tue 29 Sep, 18:00.
Recording. Lectures are recorded. Wednesdays and workshops are not.

Today

Why grep does not scale
What the index is
How postings merge
Phrases
Finding the term at all
Building the index when it does not fit in memory

We stop where we stop. The rest opens next time.

Where we start

The inverted index: 1960s, and still what sits under Lucene, BM25, and the sparse half of a hybrid retriever.

We start here because the shapes it uses come back all term.

What it is

An inverted index maps each term to the list of documents that contain it.

retrieval  ->  d1, d3, d7, d9, ...
memory     ->  d2, d3, d9
hnsw       ->  d4, d11, d23

Where it came from

1945 - Bush imagines the memex: “an enlarged intimate supplement to his memory”
c. 1950 - Mooers coins information retrieval
1958 - IBM demonstrates auto-indexing machines, built on Luhn’s work

IIR §1.5, p. 17

What it is now

Lucene - the engine under Elasticsearch, OpenSearch and Solr.

BM25 over an inverted index is the sparse half of the hybrid search those systems ship natively.

As of 2026.

The task

Find every paper on the reading list that mentions

retrieval and memory but not reinforcement

The naive answer

No index. Scan every file, top to bottom, keep the ones that match.

$ grep -l retrieval *.pdf | xargs grep -l memory | ...

And it is the right answer

For a hundred papers, grep wins.

Do not build an index to search your own downloads folder.

Until it is not

It re-reads every document for every query.
retrieval but not reinforcement needs a second full pass, and a set difference held in your head.

Write it down instead

One row per term. One column per paper. One bit per cell.

	d1	d2	d3	d4
retrieval	1	0	1	1
memory	0	1	1	0
reinforcement	0	1	0	0

Now the query is arithmetic

	d1	d2	d3	d4
`retrieval`	1	0	1	1
`memory`	0	1	1	0
`NOT reinforcement`	1	0	1	1
`AND`	0	0	1	0

Two row fetches, one complement, one bitwise AND - and the answer is d3.

Then scale it

arXiv held 3,146,222 submissions on 26 Aug 2026, over a vocabulary of order 10M terms.

A paper holds about 2,000 distinct terms.

So one cell in five thousand is set. The matrix is a lie about where the information lives.

Distinct terms measured over the 97 papers in prep/papers/.

Record only the ones

For each term, keep the sorted list of documents where the bit is set.

That is the inverted index.

Two halves, two lifetimes

The dictionary is the list of terms. One entry per distinct term, holding its document frequency and a pointer.

The postings list is what the pointer reaches: the sorted docIDs for that one term.

dictionary                postings
-----------------------   -------------------------
retrieval  df=93   -----> d1, d3, d7, d9, ...
memory     df=67   -----> d2, d3, d9, ...
hnsw       df=5    -----> d4, d11, d23, d41, d55

	Lives	Read
Dictionary	in memory	once per query term
Postings	on disk	streamed

Building it is a transpose

Parsing gives you document order. The index needs term order.

emit    (caesar,d1) (brutus,d1) (caesar,d2) ...
sort    by term, then docID
collapse equal-key runs into postings lists

Why sorting is the transpose

Sort by term, and every pair for a term lands in one unbroken run - a pair with a different term is either smaller or larger, so nothing falls in between.

before   (2,d1) (1,d1) (2,d2) (4,d2)
after    (1,d1) (2,d1) (2,d2) (4,d2)
                |__ term 2 __|

So the collapse is one forward scan, no lookups - and a lookup per pair is the random access disk forbids.

Our own postings are lopsided

Term	Papers
`retrieval`	93 of 97
`memory`	67
`transformer`	44
`bm25`	34
`hnsw`	5

Nineteen-fold. The cost of an AND is set by the shorter list.

`AND` is one merge

Two pointers, both moving forward, never backward.

p:  1  4  7  9  13
q:  4  9  14
    ^  ^        ->  4, 9

Linear in the sum of their lengths, never in the size of the collection.

Shortest first

The intersection can never be longer than the smallest operand.

So process the shortest list first - and to know which that is before reading either, the dictionary stores document frequency next to the pointer.

retrieval  df=93  -> ...
hnsw       df=5   -> ...

Skip pointers

Pre-store jumps of about sqrt(length) so a long list can leap past documents the short list will not contain.

1  4  9 [skip->] 47  52  61 [skip->] 89 ...

And when they stop paying

Skips pay when the lists are lopsided and the index is static.

They were designed when stepping over a posting saved a 5 ms disk seek.

In memory it saves a few cache misses.

Seek time from IIR Table 4.1.

Heaps’ law

Our 97 papers: 1.24M tokens, 52,074 distinct terms, and the curve is still climbing at the last token read.

Measured over prep/papers/, papers shuffled so the curve is not an artefact of alphabetical order. Book fit from IIR §5.1.

Zipf’s law

24,654 of 52,074 terms occur exactly once - 47% of the vocabulary, one occurrence each.

That head is where idf comes from. That tail is where retrieval gets hard.

Measured over prep/papers/. Fitted exponent 1.18.

The queries users actually type

retrieval augmented generation

chain of thought

mixture of experts

What does the index return?

mixture AND experts returns every paper containing both words anywhere.

	Papers
`mixture`	31 of 97
`experts`	34 of 97

The index we built cannot tell adjacency from co-occurrence.

Biword index

Make consecutive pairs the terms.

"mixture of experts"  ->  mixture-of, of-experts

Answers two-word phrases exactly. Longer phrases only by conjunction plus a post-check on the documents.

And it does not hold

The dictionary blows up - pairs, not terms.
retrieval augmented generation still comes back wrong.

So the general answer is to store positions inside the postings.

retrieval -> d1:[7, 112]  d3:[45]

A merge inside a merge

intersect documents        (as before)
  then for each document:
    intersect position lists
      under an offset constraint

p2 - p1 == 1 for adjacency.

The cost

One posting per occurrence, rather than one per document.

Index	Postings for a term
Non-positional	one per document containing it
Positional	one per occurrence, each with its offsets

The book’s rule of thumb: a positional index is two to four times the size of a non-positional index, depending on average document length.

IIR §2.4, p. 43.

One thing we assumed

The dictionary lookup is free.

It is not - and the structure you pick decides whether retriev* is answerable at all.

Two structures

	Lookup	Prefix queries	Ordering	Growth
Hash	`O(1)`	no	no	rehash
Search tree	`O(log M)`	yes	yes	cheap

Wildcards

Occurrence counts over the 97 papers in prep/papers/.

Both ends of the word

vallalavlelanoitarlaveirterlaveirterreveirterlevellexisintersect the two term setsreval → retrieval

A B-tree keeps terms in order, so retriev* is one range scan. A reverse B-tree does the same over reversed terms, so *val is a range scan too.

General wildcards

A k-gram index over character sequences.

A second index, over a different alphabet, that the system now has to build, store and keep consistent.

The k-gram index, and what it gets wrong

Write $ for a word boundary, so the term red is indexed as $red$ and its 3-grams are $re, red, ed$.

Then red* becomes the Boolean query $re AND red - starts with re, contains red.

red      ->  $re  red  ed$        matches
retired  ->  $re  ret  eti  tir  ire  red  ed$   also matches

retired contains both 3-grams and does not match the pattern.

So every candidate is checked against the original pattern before it is used.

IIR §3.2.2, p. 55.

Before you go

No reading due this week.
The recording goes up on the session page.