BM25

BM25 is a scoring function that ranks documents by how well their words match a query’s, and it has been the standard answer to that problem since the 1990s because it gets three things right that counting shared words gets wrong.

Term frequency is how many times a word appears in one document. A law that mentions hydrant twice is a better match than one that mentions it once, but not twice as good: BM25 saturates, so the third mention adds less than the second.

Inverse document frequency is how rare a word is across all the documents. Park appears in a dozen of the twenty-seven laws and hydrant in one, so a question containing both is about the hydrant, and BM25 weights the rare word up and the common one down. The formula is log(1 + (N - n + 0.5) / (n + 0.5)), where N is the number of documents and n the number containing the word, and the shape of it is all that matters: a word in every document scores near zero, a word in one document scores high.

Length normalisation stops a long law from outscoring a short one just by having more words. A law’s term frequencies are scaled by its length relative to the average, and the parameter b sets how much.

The two parameters, k1 = 1.2 and b = 0.75, are the values every implementation uses, and nobody in this pipeline has tuned them. The score of a document for a query is the sum over the query’s words of a term that combines the three ideas, and the forty lines below are that sum.