Hierarchical BM25: Lexical Search at Billion-Document Scale
Umesh Deshpande, Swaminathan Sundararaman IBM Research, San Jose, USA · 2026
Read Hierarchical BM25: Lexical Search at Billion-Document Scale by Umesh Deshpande, Swaminathan Sundararaman IBM Research, San Jose, USA (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2608-00229.txt.
Introduction
Deshpande and Sundararaman present Hierarchical BM25 for lexical search at billion-document scale. A flat BM25 index over a billion documents takes about 400 GB. Holding it in memory needs proportional DRAM. Serving it from disk takes four to twelve seconds per query. Exact top-k retrieval thus breaks interactive latency budgets.
Their design gives up exact ranking for fixed memory and latency bounds. A resident coarse index picks which topical groups a query visits. Two signals guide that choice: term frequency totals and co-occurrence in one document. Chosen groups are searched exhaustively with global statistics. Scores of returned hits equal the flat index's scores exactly. The resident footprint is about 4.4 GB, independent of corpus size. Sixteen-term queries return in about 300 ms, they report.
Catalog record
| CREATOR | Umesh Deshpande, Swaminathan Sundararaman IBM Research, San Jose, USA |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2608.00229
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hierarchical BM25: Lexical Search at Billion-Document Scale Umesh Deshpande, Swaminathan Sundararaman IBM Research, San Jose, USA Abstract A flat BM25 index over one billion documents occupies about 400 GB. Holding it in memory requires DRAM proportional to corpus size. Serving it from disk takes 4–12 seconds per query. Exact top- k k lexical retrieval at this scale is therefore impractical within an interactive latency budget. Hierarchical BM25 gives up exact ranking in exchange for fixed bounds on memory and latency. A resident coarse index selects which of ∼ {\sim} 1K topical, size-balanced document groups a query visits, using two signals: the total frequency of each query term within a group, and, for informative terms spread too thinly across groups for frequency totals to reflect, whether several of them appear together in one document. Selected groups are then searched exhaustively and scored against ∼ 100 {\sim}100 KB of global statistics. Every returned score therefore equals the flat index’s score, and the approximation is confined to selection alone. The resident footprint is ∼ 4.4 {\sim}4.4 GB, independent of corpus size. Sixteen-term queries over one billion documents return in ∼ 300 {\sim}300 ms (4.7–5.6 × \times the throughput of a flat multi-threaded index), and a warmed cache sustains ∼ 32 {\sim}32 queries per second versus under 3 for flat indexing. At a 500K-document configuration, visiting 5–10% of clusters recovers 0.83–0.92 of the exhaustive result score. Billion-scale recall and a direct comparison against document-reordered BlockMax-WAND remain open. Keywords: lexical search, BM25, rank safety, approximate retrieval, inverted index, cluster pruning, BlockMax-WAND, billion-scale retrieval. 1 Introduction Retrieval over large corpora uses two complementary paradigms. Lexical retrieval, anchored by BM25 within the probabilistic relevance framework [ 3 ] , scores documents from term-frequency and inverse-document-frequency statistics. It excels at exact keyword matches. Dense retrieval encodes queries and documents into a shared embedding space and ranks by vector similarity [ 8 ] . It stays tractable through approximate nearest-neighbor (ANN) indexes such as HNSW [ 6 ] or IVF with product quantization [ 7 ] . Neither paradigm wins on quality alone [ 5 ] . Hybrid retrieval, which runs both and merges results, is now standard practice. This paper is about the lexical half of that pipeline—specifically, the point at which it stops scaling. A flat BM25 inverted index over one billion documents is {\sim}400 GB. Keeping it in memory is uneconomical. Serving it from disk turns every multi-term query into a large fan-out of random reads, so tail latency drifts past the one-second bar interactive retrieval requires. The semantic side of hybrid retrieval is comparatively solved: mature ANN libraries scale to billions of vectors. The lexical index is the bottleneck we address. 1.1 The trade this paper makes The design rests on a deliberate trade, stated plainly before the mechanism. Rank safety is the following guarantee: if the true ten best documents for a query are d_{1},\ldots,d_{10} , a rank-safe method returns exactly those ten, every time. An approximate method might return nine of them plus the eleventh-best. Dynamic-pruning methods like BlockMax-WAND are rank-safe; Hierarchical BM25 is not. That guarantee is valuable, but consider what it costs and who needs it. In a retrieval-augmented pipeline, the lexical top- k is not the final answer. It is merged with dense-retrieval candidates and passed downstream—often through a reranker—before anything reaches the user. Swapping the tenth-best lexical candidate for the eleventh rarely changes what the pipeline produces. A lexical query that takes 4–12 seconds, however, breaks the pipeline outright. An exact answer that cannot arrive inside the latency budget delivers no retrieval quality at all: the quality of a retrieval system, end to end, is bounded by whether it answers in time. We therefore give up rank safety and buy, with it, two properties otherwise unavailable at this scale: a resident footprint fixed at {\sim}4.4 GB, and query latency near 300 ms. Both are structural bounds—consequences of the index shape—not averages that degrade under load. The sacrifice is also confined: as Section 3.4 shows, the approximation lives entirely in which document groups a query visits . Every document that is scored receives its exact, corpus-wide BM25 score. The only possible failure is a missed group, never a mis-scored document. Sections 5.4 and 6 state the price directly: at a 500K-document configuration the approximation recovers 0.83–0.92 of the exhaustive result score when visiting 5–10% of clusters, while billion-scale recall remains extrapolated—so the trade is priced at small scale and stated as a bet, with analytical support, at large scale. This paper makes three contributions, each responding to a specific gap in how lexical search is currently scaled. First, Hierarchical BM25 itself (Section 3 ). It is a two-level lexical index that decouples resident memory from corpus size. A coarse Level-1 index over {\sim}1 K document groups is pre-computed and kept resident. A fine Level-2 index over the full billion documents is served from a fixed-size cache plus NVMe. This holds 16-term query latency at {\sim}300 ms. What distinguishes this from prior two-level methods is what the first level is for . WAND [ 9 ] and recent dynamic-pruning schemes such as ASC [ 17 ] and BMP [ 18 ] assume a single index is already resident or on fast local storage; their first level skips computation within it. At a billion documents, keeping the index resident is possible on large-memory nodes but costs DRAM proportional to corpus size. Our first level therefore bounds the residency budget , not the computation. The architecture itself—topical shards plus per-query shard selection—is shared with selective search [ 13 ] ; what it adds is a selection signal that sees same-document co-occurrence exactly and for every document—evidence existing shard selectors either cannot represent or observe only through a thin document sample (Section 2 ). Second, a correctness fix for cross-cluster score merging. Building the two-level index surfaced a bug in how scores from different clusters get merged. Scoring each of {\sim}1 K independent per-cluster indexes with its own local IDF is not an approximation—it is an outright error. Two documents with identical term frequencies can land 1.6\times apart in score purely because of which cluster they sit in. We fix this (Section 3.4 ) by scoring every cluster from one {\sim}100 KB table of global corpus statistics. The merged ranking then needs no per-cluster correction factor at all. Third, an analytical comparison against BlockMax-WAND at long query lengths (Section 4 ). Retrieval-augmented pipelines issue much longer queries—16 to 32 terms—than the 2–5-term web queries WAND-style pruning was designed around. We argue this regime favors cluster selection. WAND’s pruning power depends on document-level multi-term co-occurrence, which grows scarce as queries lengthen and terms decorrelate. Cluster selection here rests on two signals: aggregate term frequency, which needs only single-term topical concentration, a substantially weaker requirement; and exact document-level co-occurrence tracking for informative terms spread too thinly across clusters to raise any one cluster’s total. For such terms, several of them meeting in one document is the evidence that marks a genuine match. We analyze why each signal’s cost stays bounded as queries lengthen while WAND’s does not. All of this is an architectural argument, quantified where we can, not a measured head-to-head result. We evaluate Hierarchical