Hierarchical BM25: Lexical Search at Billion-Document Scale
Umesh Deshpande, Swaminathan Sundararaman
cs.IR, cs.AI
2026-08-01
Hierarchical BM25 cuts billion-document resident memory from ~400GB to ~4.4GB and latency to ~300ms, 4.7-5.6x faster than a flat index, trading exact ranking for fixed bounds.
BM25 is the workhorse of lexical search, but at a billion documents a flat inverted index runs about 400GB, and resident memory scales linearly with corpus size. Serve it from disk instead and a single query takes 4-12 seconds. That latency is a non-starter for any interactive pipeline, even one where lexical search is just supplying candidates alongside dense retrieval in a hybrid system. Dense retrieval solved this problem years ago with approximate nearest-neighbor indexes like HNSW and IVF that scale to billions of vectors in milliseconds. Lexical retrieval never got its equivalent: exact ranking at this scale is either too much memory or too slow.
Hierarchical BM25 gives up rank safety, the guarantee that the true top-10 documents are exactly what gets returned, in exchange for fixed bounds on memory and latency. The index has two levels. Level one is a resident coarse index over roughly 1,000 topically balanced document groups, built with LDA topic modeling and locally re-split whenever a cluster outgrows its target size, so there's no need to recluster the whole corpus; the whole level costs about 4.4GB. Level two holds fine per-document statistics for all one billion documents, with only a roughly one-million-entry cache kept resident and the rest served from NVMe on demand. At query time, two signals select about 40 promising clusters from level one: the total frequency of each query term within a cluster (a coarse topical-concentration signal), and, for terms that are discriminative but scattered thinly across many clusters, whether several of them actually co-occur in the same document, something the aggregate frequency signal alone can't see, so the paper builds a small dedicated index just to track that. The selected clusters are then searched exhaustively and scored exactly the same way a flat index would score them; the only approximation happens at cluster selection, never at scoring. The paper also fixes a subtle correctness bug: scoring each cluster with its own local inverse document frequency lets identical term frequencies land 1.6x apart in score purely because of which cluster a document sits in. The fix is a single shared, roughly 100KB global document-frequency table that every cluster scores against, matching a flat index exactly.
At one billion documents and roughly 1,000 clusters, 16-term queries return in about 300 milliseconds, 4.7-5.6x faster than a multi-threaded flat index, with resident memory at 4.4GB versus roughly 400GB for the flat version. The gap widens under concurrency: at 32 parallel queries, the flat index's throughput stays under 3 QPS because every query still pays for a full disk scan, while a warmed Hierarchical BM25 sustains roughly 25-32 QPS. The quality cost is measured at a smaller 500K-document, 500-cluster configuration: visiting just 5-10% of clusters recovers 83-92% of the exhaustive index's score, with shallow results (top-10) holding up better than deep ones (top-80). The paper also gives an analytical comparison to BlockMax-WAND, the standard dynamic-pruning alternative, for long queries: WAND's pruning power depends on multiple query terms hitting the same document, and its candidate pool balloons with query length (39 million documents at 8 terms to 148 million at 32 terms), while cluster selection relies on aggregate topical concentration, which doesn't grow with query length the same way, making it theoretically better suited to the 16-32 term queries common in retrieval-augmented pipelines.
In any hybrid retrieval system pairing lexical and dense search, the lexical side has long been the compromise: either it eats all your memory or it's too slow to fit an interactive latency budget. This gives lexical search a fixed 4.4GB memory footprint regardless of corpus size, small enough to run on the same machine as a dense index instead of needing a dedicated large-memory server. The paper is explicit that this is a structural tradeoff, approximate ranking for bounded resources, not a free performance win.
The authors are careful to note that recall was only measured at the smaller 500K-document configuration; the true recall at billion-document, 1,000-cluster scale is extrapolated, not measured. The benchmark queries are random terms drawn uniformly from a 20,680-word vocabulary, which lacks the long-tail distribution real queries have and stresses the clustering and co-occurrence signals only weakly, something the paper itself calls one of the least favorable settings for its own quality mechanisms. The comparison against BlockMax-WAND is purely analytical; no head-to-head benchmark has been run, and the paper flags that as the most important open next step. Whether clustering stays balanced at a natural-language vocabulary size, rather than the roughly 20,000-word compact vocabulary used here, is also left as an open question.