Inverted index and BM25

The Russian edition of this catalogue, as it stood when the index was taken, had 77 articles and 119,076 words. To find where shortest paths are discussed, you can read them all, or you can write down in advance, once, for each word, which articles it occurs in. Then a two-word query reads two short lists. Below is such a search over the catalogue itself. Each word of the query turns into a strip: a cell for each article, bright if the word is there. Under the strips is the result list, sorted by the BM25 formula, with each word’s contribution to the score.

For «кратчайший путь» (“shortest path”) the search read 48 index entries: «кратч» is in 15 articles, «путь» in 33, at least one of the two in 34. The top three are A*, Bellman–Ford and Floyd–Warshall. The article on Dijkstra is fourth and trails the third by 0.005. The formula does not know which article is the main one for a topic: it counts words. Below is how the strips are built, how to intersect them, compress them and turn them into the order of the results.

The idea

Usually a document is a list of words. An inverted index turns it over: for each word, a list of the documents where it occurs. The numbers in the list go in increasing order, and with each is written how many times the word occurred in the document. Such a list is called a posting list. A query does not touch the texts: it finds the lists of its words in the dictionary and works only with them.

It is the index at the back of a thick book: “hash table: 211, 340, 517”. It is built in one pass over all the words. The word is looked up in the dictionary, a hash table or a sorted array, and the number of the current document is appended to the end of its list if it is not there yet. The documents go in order, so the lists come out sorted by themselves. From the very beginning, from a search engine that goes through all the texts, this idea is taken apart in the course chapter “A search engine for our textbooks”. Here is what happens next, when the lists get long.

In the catalogue’s index a word is not quite a word. It is its first five letters: «кратчайший», «кратчайшего» and «кратчайшая» (forms of “shortest”) give one term, «кратч». This is a crude replacement for a stemmer, which cuts off endings by the rules of the language, or a lemmatiser, which reduces a word to its dictionary form. Short words do not merge this way: «путь» and «пути» (“path”, “paths”) are different terms. There came out 7151 terms and 43,805 “term, article” pairs.

The lists are very unequal. 3357 terms, almost half, occur in exactly one article. Thirteen occur in all seventy-seven: «и», «а», «в», «что», «это», «по», «на», «же», «если», «код», «задач», «больш», «сколь» (“and”, “but”, “in”, “that”, “this”, “by”, “on”, an emphatic particle, “if”, “code”, “problem”, “large”, “how many”). Every text is built like this: a few very frequent words and a long tail of rare ones. Three questions follow from this inequality, and the whole article rests on them: how to intersect a short list with a long one, how to store long lists, and how not to drown in documents that have only frequent words.

Intersection: a short list against a long one

The query «двоичный поиск» (“binary search”) in “all words” mode is an intersection of two lists: «двоичный» is in 33 articles, «поиск» in 50, both in 27. The lists are sorted, and the standard way to intersect them is two fingers, as in the merge of merge sort: the finger on the smaller number steps forward, and a match goes into the answer. There are at most m + n steps, where m and n are the lengths of the lists.

While the lists are of similar length, nothing better can be done. But War and Peace has 31,252 sentences, and the word «бал» (“ball”) stands in 18 of them, while «и» (“and”) is in 13,480. To find the 11 sentences that have both, two fingers would have to go 12,246 steps, almost the whole long list. The short list sets what to look for; the long one is needed only for checking. Checking can be done by binary search: for each of the 18 sentences about log₂ 13,480 ≈ 14 looks into the long list, 249 in all.

Better still is galloping. The sentences of the short list go in increasing order, so the next one should be searched for not from the start of the long list but from where the previous search stopped. From that place make jumps of 1, 2, 4, 8… positions forward until the number sought is overshot, and inside the last jump search by binary search. If the target is d positions ahead, there are about log₂ d jumps and as many steps of binary search. On the pair «бал» and «и» that is 232 looks instead of 12,246. Choose a pair of words and see what it looks like: the whole novel above, and below a magnifier showing the jumps to the next sentence.

In the magnifier the scale is logarithmic, and the jumps 1, 2, 4, 8 are equal steps on it. So a distant sentence takes only a few more jumps than a near one. In the overview above, the orange strip is everything the two fingers went through, and the sparse marks under it are everything the galloping looked at.

For «бал» and «и» the bound gives 380, in practice 232. If m = n, the bound is 4n, the same order as two fingers. If m ≪ n, it grows as m·log(n/m), not as n. This is a natural bound: even merging two ordered lists needs log₂ C(m+n, m) comparisons in the worst case, which for m ≪ n is about m·log₂(n/m), and Frank Hwang and Shen Lin built a merge in 1972 that almost reaches this minimum. Measurements from the listing below:

Binary search from scratch is good only while the short list is very short: on the pair Natasha and Pierre it is four times worse than two fingers. Galloping is no worse than either in any row. If a query has more than two words, the lists are taken from the shortest: its numbers are the candidates, and each next list can only weed them out. The candidates become fewer, while they have to be checked in ever longer lists, exactly where galloping wins most.

Real indexes add skip pointers to the lists: for each block of numbers, its first number and its address in the file. With them galloping jumps over whole blocks without unpacking them, and unpacks only the block where a candidate may be. Skip pointers in inverted files were described by Alistair Moffat and Justin Zobel in 1996; in Lucene they stand on every block of 128 numbers.

Compression: differences and bytes

If each “article, how many times” pair is stored as two 4-byte numbers, the lists of the catalogue’s index take 350,440 bytes. But the numbers in a list grow, and instead of them the differences of neighbours can be stored: the list 3, 7, 8, 15, 16 becomes 3, 4, 1, 7, 1. A frequent term has small differences, since it is in almost every article; a rare one has large ones, but there are few such numbers. Small numbers are written with a variable-length code: 7 bits per byte, with the top bit saying whether another byte follows. Numbers up to 127 take one byte, up to 16,383 two.

After this the same lists take 87,610 bytes, 4.0 times less, about two bytes per pair. The gain is not only in space. A compressed index fits in memory whole, and unpacking a byte is faster than waiting for it from the disk: a read from an SSD takes hundreds of times longer than a memory access. Lucene from version 4.1 goes further: it packs differences in blocks of 128 numbers, giving all the numbers of a block the same number of bits, as many as the largest needs, and writes the tail of the list that does not fill a block with variable bytes. The PForDelta family of codes, proposed by Marcin Zukowski and colleagues in 2006, moves rare large differences into a separate list of exceptions, so that one large difference does not bloat the whole block.

BM25: rarity, saturation, length

Finding the articles that contain the query words is half the job. «очередь с приоритетом» (“priority queue”, literally “queue with priority”) matches 76 articles of 77: the preposition «с» (“with”) is almost everywhere. They have to be ordered, and the most widespread formula for that is BM25. The score of article D is the sum of the contributions of the query words it contains:

$$\text{BM25}(D) = \sum_{t} \text{idf}(t) \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)},$$

$$\text{idf}(t) = \ln\left(1 + \frac{N - \text{df} + 0.5}{\text{df} + 0.5}\right).$$

Here tf is how many times term t occurs in D, |D| is the length of the article in words, avgdl the mean length (1546 words in the catalogue), N the number of articles, df how many of them contain t. The three factors answer three questions.

How rare is the word. idf is larger the fewer documents contain the word: for «приор» it is 2.85 (4 articles), for «очере» 0.88 (32 articles), for «с» 0.02. In the original formula of Robertson and Spärck Jones there is no one under the logarithm. Then a word that occurs in more than half of the documents has a negative idf: «алгор» (“algorithm”) is in 56 articles of 77 and would get −0.97. For the query “sorting algorithm” an article with the word “algorithm” would lose to the same article without it. «и», which is in all the articles, would get −5.04. Lucene adds one under the logarithm: «алгор» weighs 0.32, «и» 0.006. SQLite in FTS5 keeps the original formula but replaces a non-positive idf with 10⁻⁶; a comment in the source explains just that: a negative weight is undesirable.

How much do repeats mean. The fraction with tf grows with the number of repeats, but ever more slowly, and runs into a ceiling of k₁ + 1: the tenth mention adds less than the first. This is saturation, a simple approximation of a model in which a document is either devoted to the word or mentions it in passing: Stephen Robertson and Steve Walker were looking for such a replacement for the “two Poisson” model in 1994. With k₁ = 0 only presence counts; with a large k₁ the score is almost proportional to tf.

How long is the article. In a long article a word occurs more often simply because there are more words. The factor 1 − b + b·|D|/avgdl compares the length with the mean, and b decides how strictly: with b = 0 length does not matter, with b = 1 the frequency is divided by the length fully. The formulas with b = 1 and b = 0 were called BM11 and BM15 by the team of the Okapi system; at the TREC-3 conference in 1994 it combined them into one, BM25, with b in between.

Move the knobs on the query «очередь с приоритетом». The curves show a word’s contribution against the number of repeats for an article half the average length, of average length, and twice the average.

The contest is between three articles. In “Binary heap” “queue” occurs 6 times and “priority” 5, but it is the longest article of the catalogue, 2978 words. In “Stack and queue” “queue” occurs 36 times, “priority” 2, length 1690. In the article “Choosing a data structure”, 2 and 1 with length 662. With k₁ = 0 all three have exactly 3.75: each contains all three terms, and only that counts. With k₁ = 1.2 the heap is ahead, 5.94 against 5.72. With k₁ = 3 the thirty-six “queues” tip the scales, and “Stack and queue” comes first, 7.66 against 7.62. The b knob moves something else: with b = 0 the long heap article pulls away, 6.71 against 5.83, and with b = 1 the short article on choosing a structure catches it up: both have 5.72.

For a one-word query k₁ does not change the order at all. Document 1 beats document 2 if tf₁/(tf₁ + k₁L₁) > tf₂/(tf₂ + k₁L₂), where L is the length factor. Cross-multiplying gives tf₁·L₂ > tf₂·L₁, and k₁ cancels. Saturation decides what repeats of one word are worth against the presence of another, which is why it matters only in multi-word queries. The usual values are k₁ from 1.2 to 2 and b = 0.75; Lucene defaults to 1.2 and 0.75, and in SQLite these numbers are hard-coded.

The best ten without counting them all

The listing below ranks “term at a time”: it goes through the list of each query word and accumulates scores in an array, a cell per document. The work is proportional to the total length of the lists, and for a frequent word that is almost all the documents. But the reader needs the first ten. Can they be chosen without finishing the scores of the rest?

They can, if the ceiling of each term is known: the largest contribution it makes to any document. It is computed in advance, at indexing time. Suppose k documents have already been found, and the worst of them scored θ. Arrange the query terms in increasing order of ceiling. If the ceilings of the first few add up to no more than θ, a document that has only these terms can no longer get into the best, and there is no need to look at it. So candidate documents are taken only from the lists of the remaining terms, while the “weak” lists are searched by galloping, for checking. The better the documents found, the higher θ and the more terms become weak. This is the MaxScore algorithm of Howard Turtle and James Flood, 1995.

For «кратчайший путь» with the best three, MaxScore looked at 16 of the 34 articles containing at least one word and finished the score of 7. The answer is the same: A*, Bellman–Ford, Floyd–Warshall. On millions of documents the difference is much bigger: frequent words give long lists but with small ceilings, and almost all of their lists go unread. Andrei Broder and co-authors proposed the WAND algorithm in 2003, and Shuai Ding and Torsten Suel in 2011 proposed keeping ceilings not for the whole list but for each block. This block-max WAND went into Lucene 8.0 and Elasticsearch 7.0 in 2019. The Elasticsearch developers reported a 3–7-fold speed-up of single-term queries. The price is the exact number of documents found: nobody counted the documents skipped. That is why Elasticsearch from version 7.0 by default counts matches exactly only up to 10,000 and after that answers “at least 10,000”.

Code

The first listing works with the same catalogue index as the scene: BM25 term at a time, the best three by MaxScore, intersection by two fingers and the size of the lists before and after compression. The index is a snapshot: 77 articles as they were on 16 October 2026.

The second builds an index of the sentences of War and Peace and intersects lists in three ways. The output is the same table as above and the same numbers the scene with the jumps shows.

In both listings the index is a dictionary of lists in memory. For texts that do not fit in memory it is built differently: the “term, document” pairs are written out, sorted in pieces and merged; this is how the first web search engines built their indexes. Lucene writes small immutable segments, each an index in itself, and merges them into big ones in the background, like an LSM tree. A deleted document is not struck out of the lists but marked, and disappears at the next merge.

What it costs

Building is one pass over all the words, O(number of words) with an in-memory hash table; on disk, a sort of the pairs. Memory is O(number of “term, document” pairs): 43,805 pairs for 119,076 words in the catalogue, about two bytes per pair after compression. Word positions, needed for phrase search, would add an entry for every word of the text.

An “all words” query is O(m·log(n/m)) per list, where m is the length of the shortest, with galloping intersection, and O(m + n) with two fingers. Term-at-a-time ranking is O(total length of the query words’ lists), plus choosing the k best with a heap, O(T·log k) for T documents touched. MaxScore and WAND are no better in the worst case, but on real queries they skip most of the long lists.

The weak points come from the index knowing only words. “Heap” and “priority queue” are unrelated for it. A typo is a different term, and separate techniques are needed: n-grams or search with edit distance. The phrase “binary search” and the words “search” and “binary” in different paragraphs are the same for an index without positions. That is why vector search by meaning is often put beside BM25, and the results of the two systems are blended.

Where it works

Search libraries. Lucene and Elasticsearch, OpenSearch and Solr built on it store exactly such lists, compressed in blocks, with skip pointers, and rank by BM25, by default since Lucene 6.0 in 2016; before that it was a TF-IDF variant.

Databases. In SQLite an FTS5 full-text table is an inverted index, and the bm25() function returns the score with a minus sign so that ORDER BY bm25(t) in ascending order gives the best first. In PostgreSQL full-text search rests on a GIN index, also inverted, over a tsvector column, but ranks with its own ts_rank functions, not BM25.

Logs. Log stores choose whether to pay for an index. Elasticsearch builds posting lists over all the words of each line, and a line with a given identifier is found through the index, without a scan. Grafana Loki deliberately indexes only the stream labels, service and host, and scans the text of the lines at query time: storage is cheaper, text search slower.

History

The first word index to a large text, a concordance of the Latin Bible, was compiled in the 1230s–1240s by Dominican friars under Hugh of Saint-Cher. There were no verse numbers yet, and a reference looked like a book, a chapter and a letter from a to g, one of seven parts of the chapter. This is a posting list with coarse positions. Karen Spärck Jones proposed in 1972 weighting words by rarity, what was later called idf. The probabilistic model from which BM25 came was developed by Stephen Robertson and Karen Spärck Jones from 1976. The formula itself appeared in the Okapi team’s report at TREC-3 in 1994.

Algorithms for lists developed in parallel. The Hwang–Lin merge is from 1972. Search by jumps in an unbounded array was described by Jon Bentley and Andrew Yao in 1976. Skip pointers in inverted files, Moffat and Zobel, 1996. Adaptive set intersection, where the number of steps depends on how the lists interleave, Erik Demaine, Alejandro López-Ortiz and Ian Munro, 2000. MaxScore, WAND and block-max WAND, 1995, 2003 and 2011.

Problems