{"id":107,"date":"2026-04-02T23:51:00","date_gmt":"2026-04-02T23:51:00","guid":{"rendered":"https:\/\/byte64.com\/?p=107"},"modified":"2026-04-02T23:51:00","modified_gmt":"2026-04-02T23:51:00","slug":"bm25-search-index-encoding","status":"publish","type":"post","link":"https:\/\/byte64.com\/?p=107","title":{"rendered":"BM25 &amp; Search Index Encoding"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/es.wikipedia.org\/wiki\/Okapi_BM25\" data-type=\"link\" data-id=\"https:\/\/es.wikipedia.org\/wiki\/Okapi_BM25\">Okapi BM25<\/a> is a standard ranking formula that has been used in search engines since the 1980s. For each word in a query, it uses the frequency of that word in a document, the length of the document and the number documents that contain the word to decide how significant the word is for the document. <\/p>\n\n\n\n<div class=\"wp-block-math\"><math display=\"block\"><semantics><mrow><mtext>score<\/mtext><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>D<\/mi><mo separator=\"true\">,<\/mo><mi>Q<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>=<\/mo><mrow><munder><mo movablelimits=\"false\">\u2211<\/mo><mrow><mi>q<\/mi><mo>\u2208<\/mo><mi>Q<\/mi><\/mrow><\/munder><\/mrow><mtext>IDF<\/mtext><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mfrac><mrow><mi>f<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo separator=\"true\">,<\/mo><mi>D<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mi>k<\/mi><\/mrow><mrow><mi>f<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo separator=\"true\">,<\/mo><mi>D<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>+<\/mo><mi>k<\/mi><mrow><mo fence=\"true\" form=\"prefix\">(<\/mo><mn>1<\/mn><mo>\u2212<\/mo><mi>b<\/mi><mrow><mo fence=\"true\" form=\"prefix\">(<\/mo><mn>1<\/mn><mo>\u2212<\/mo><mfrac><mrow><mtext>len<\/mtext><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>D<\/mi><mo form=\"postfix\" stretchy=\"false\" lspace=\"0em\" rspace=\"0em\">)<\/mo><\/mrow><mtext>avgDL<\/mtext><\/mfrac><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><\/mrow><\/mfrac><\/mrow><annotation encoding=\"application\/x-tex\">\\text{score}(D,Q) = \\sum_{q \\in Q} \\text{IDF}(q) \\frac{f(q,D)k}{f(q,D) + k\\left(1 &#8211; b\\left(1 &#8211; \\frac{\\text{len}(D)}{\\text{avgDL}}\\right)\\right)}<\/annotation><\/semantics><\/math><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Here <math data-latex=\"f(q,D)\"><semantics><mrow><mi>f<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo separator=\"true\">,<\/mo><mi>D<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">f(q,D)<\/annotation><\/semantics><\/math> is the frequency of word <math data-latex=\"q\"><semantics><mi>q<\/mi><annotation encoding=\"application\/x-tex\">q<\/annotation><\/semantics><\/math> in document <math data-latex=\"D\"><semantics><mi>D<\/mi><annotation encoding=\"application\/x-tex\">D<\/annotation><\/semantics><\/math>, while <math data-latex=\"k,b\"><semantics><mrow><mi>k<\/mi><mo separator=\"true\">,<\/mo><mi>b<\/mi><\/mrow><annotation encoding=\"application\/x-tex\">k,b<\/annotation><\/semantics><\/math> are tuned constants and <math data-latex=\"\\text{IDF}(q)\"><semantics><mrow><mtext>IDF<\/mtext><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><\/mrow><annotation encoding=\"application\/x-tex\">\\text{IDF}(q)<\/annotation><\/semantics><\/math> is the inverse document frequency given by<\/p>\n\n\n\n<div class=\"wp-block-math\"><math display=\"block\"><semantics><mrow><mtext>IDF<\/mtext><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>=<\/mo><mrow><mi>ln<\/mi><mo>\u2061<\/mo><\/mrow><mrow><mo fence=\"true\" form=\"prefix\">(<\/mo><mfrac><mrow><mi>N<\/mi><mo>\u2212<\/mo><mi>n<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>+<\/mo><mn>0.5<\/mn><\/mrow><mrow><mi>n<\/mi><mo form=\"prefix\" stretchy=\"false\">(<\/mo><mi>q<\/mi><mo form=\"postfix\" stretchy=\"false\">)<\/mo><mo>+<\/mo><mn>0.5<\/mn><\/mrow><\/mfrac><mo>+<\/mo><mn>1<\/mn><mo fence=\"true\" form=\"postfix\">)<\/mo><\/mrow><mi>.<\/mi><\/mrow><annotation encoding=\"application\/x-tex\">\\text{IDF}(q) = \\ln \\left( \\frac{ N &#8211; n(q) + 0.5}{n(q) + 0.5} +1\\right).<\/annotation><\/semantics><\/math><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">These are all basic statistics to calculate, but it&#8217;s tricky to implement efficiently. I&#8217;ve got two core tables powering the search engine.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Search Index: A mapping of keywords to documents that contain them encoded as a <a href=\"https:\/\/ir.cwi.nl\/pub\/15564\/15564B.pdf\">PFOR<\/a>. The table is stored as an SSTable and is largely kept on disk.<\/li>\n\n\n\n<li>Scoring Info: A mapping of documents to their URLs, important words and embedding. This is kept entirely in memory and is accessed by index with the results of the intersection computed using the search index.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">For each search request, we perform one lookup in the search index per search term. This can come back with 10&#8217;s of thousands of documents that need to be scored. That&#8217;s why the scoring info needs to be kept in memory.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">When implementing BM25, my main concern was that the per-doc word frequency information is a ton of information to store and lookup during scoring. The trick is to store this information in the search index so the keywords don&#8217;t need to be repeated again and again.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">There&#8217;s no one way to encode the search index. Gemini suggested either storing a list of (docid, freq) pairs, or keeping them as separate PFORs of the deltas of the docids and frequencies. It further suggested quantization schemes for the frequencies.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Finally, it suggested breaking the documents into those with high frequencies and low frequencies. This was meant to help with retrieval optimizations by only looking at those documents with high frequencies for the terms, and ignoring the lower frequencies. This didn&#8217;t make sense to me, since when searching across multiple terms, we might find high scoring documents where one term is high scoring and the other is not. Also, if we ignore the low frequency words in a document, we&#8217;ll drop erroneously drop documents from the intersection.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">When I looked at statistics for my PFOR encoding, I found it wasn&#8217;t particularly efficient on average. On average, 10 bytes were being used for each uint32 local document id &#8212; which in any sane world should take at most 4 bytes. The reason for the bloat was that many keywords showed up in a small number of documents and I was encoding blocks of 128 document ids at a time, wasting space. For more common keywords, the PFOR was providing good compression. For instance, aardvark shows up in 1500 documents and was using only 2 bytes per docid.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s get down to my encoding. My main design choice was to find frequencies in a second pass after the intersection is computed. This keeps us from having to read frequencies of documents that match one search term but aren&#8217;t in the intersection of all search terms. This means we need to be able to jump right to the frequencies we want. So, the frequencies have have a fixed width and be stored in an array. Consequently, I couldn&#8217;t store them with a PFOR or variable length ints. So, instead I mapped each frequency to  a nibble &#8212; i.e. 4 bits used to represent 16 different frequency buckets. This loses some precision, but means I only use half a byte per document to store the frequencies.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">For example, if &#8220;aardvark&#8221; appears in documents 1000, 2000, 3000 and 4000 with frequencies 1, 13, 20 and 600 respectively (which fall in buckets 0, 9, 10 and 15) then the encoding is:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>uint32 1 \/\/ PFOR type\nuint32 4 \/\/ doc count\nbyte 0x09 \/\/ freq 1, freq 13\nbyte 0xAF \/\/ freq 20, freq 600\npfor(1000, 2000, 3000, 4000)<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">I have a second encoding type which replaces the PFOR with a list of document ids in a variable length integer format. This solves the problem of wasting space for keywords with few documents. The document count is not only useful for the BM25 metric, but also helps us jump over the document frequencies to the document ids.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I&#8217;ve added a fancy scoring table to the search results so you can see the breakdown of frequencies and score per search term. Some work needs to be done to scale the BM25 score to play nicely with the embedding score, but that&#8217;ll be future work.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"603\" src=\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-02-at-5.48.05-p.m-1024x603.png\" alt=\"\" class=\"wp-image-108\" srcset=\"https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-02-at-5.48.05-p.m-1024x603.png 1024w, https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-02-at-5.48.05-p.m-300x177.png 300w, https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-02-at-5.48.05-p.m-768x452.png 768w, https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-02-at-5.48.05-p.m-1536x905.png 1536w, https:\/\/byte64.com\/wp-content\/uploads\/2026\/04\/Screenshot-2026-04-02-at-5.48.05-p.m.png 1640w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Okapi BM25 is a standard ranking formula that has been used in search engines since the 1980s. For each word in a query, it uses the frequency of that word in a document, the length of the document and the number documents that contain the word to decide how significant the word is for the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,18],"tags":[19,27,7],"class_list":["post-107","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-search","tag-doc-ids","tag-scoring","tag-wikipedia"],"_links":{"self":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=107"}],"version-history":[{"count":1,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/107\/revisions"}],"predecessor-version":[{"id":109,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/107\/revisions\/109"}],"wp:attachment":[{"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}