🤖 AI

Hierarchical BM25: Lexical Search at Billion-Document Scale

Hierarchical BM25 enables interactive, billion-scale lexical search by replacing a memory-intensive flat index with a two-tier architecture that uses a small, resident coarse index to select relevant document groups, achieving fixed memory and latency bounds while preserving exact scoring for the retrieved subset.

Original authors: Umesh Deshpande, Swaminathan Sundararaman

Published 2026-08-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Umesh Deshpande, Swaminathan Sundararaman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific fact in a library that contains one billion books. In the world of computer science, this is the challenge of "lexical search"—finding documents based on exact word matches, like searching for the phrase "hierarchical BM25" rather than just the general idea of it. For decades, computers have been getting better at this, but there's a catch: to search a billion books instantly, you usually need to keep a massive map of every single word in every single book in your computer's main memory (RAM). This map is so huge—about 400 gigabytes—that it's like trying to carry the entire library in your backpack while you run. If you don't have that much memory, you have to run back and forth to the shelves (the hard drive) for every question, which takes seconds. In a world where we expect answers in a blink, waiting four to twelve seconds is like watching paint dry; it breaks the experience. This paper tackles that exact problem: how do we search a billion documents instantly without needing a supercomputer's memory?

The authors propose a clever new way to search called Hierarchical BM25. Instead of trying to memorize the whole library at once, they suggest a two-step strategy that mimics how a human librarian would help you. First, they organize the one billion documents into about 1,000 distinct "aisles" or groups based on their topics. They build a tiny, super-fast index of just these aisles that fits easily into memory (about 4.4 GB). When you ask a question, the computer doesn't scan every book; it first checks this small index to figure out which 40 aisles are most likely to have the answer. It then dives only into those specific aisles to find the exact books.

The magic here is a trade-off. The authors admit that by skipping the other 960 aisles, they might miss the absolute perfect answer once in a while. They call this giving up "rank safety"—the guarantee that you get the exact top 10 results every single time. However, they argue that in modern search systems, getting the 10th-best result instead of the 11th-best rarely matters because a second computer (a "reranker") will sort them out anyway. What does matter is speed. By making this trade, they achieve something previously impossible: they can search a billion documents in about 300 milliseconds (less than a third of a second) using a tiny amount of memory.

In their tests, this new method was 4.7 to 5.6 times faster than the old, standard way of searching, even when the old method used multiple processors to help out. While the old method struggled to handle more than 3 questions per second, this new system could handle up to 32 questions per second when the "aisles" were already warm and ready. The authors also discovered a subtle bug in how different groups of books were scored against each other and fixed it, ensuring that when they did search, the math was perfectly accurate.

However, the authors are very careful not to call this a perfect solution. They explicitly state that this method is an approximation, not a guarantee. They measured how well it worked on a smaller test of 500,000 documents and found that by checking just 5% to 10% of the groups, they recovered about 83% to 92% of the "quality" of a full search. They suggest this will likely hold up at the billion-document scale, but they haven't proven it yet on a natural, messy real-world dataset. They also note that their method works best for long, complex questions (16 to 32 words), which are common in modern AI systems, whereas older methods were designed for short, simple web searches.

In short, this paper suggests that if you are willing to accept a tiny chance of missing the absolute best answer, you can build a search engine for a billion documents that is fast, cheap, and fits in a standard computer's memory. It's a practical engineering win that prioritizes speed and efficiency over mathematical perfection, acknowledging that in the real world, a fast "good enough" answer is often better than a slow "perfect" one.

Technical Summary: Hierarchical BM25 at Billion-Document Scale

1. Problem Statement

The paper addresses the scalability bottleneck of lexical search (specifically BM25) in hybrid retrieval systems at the billion-document scale. While dense retrieval scales efficiently using Approximate Nearest Neighbor (ANN) indexes, flat BM25 inverted indexes over one billion documents present two critical failures:

Memory Cost: A flat index occupies approximately 400 GB. Keeping this entirely in DRAM is economically prohibitive, especially in hybrid deployments where memory is shared with dense retrieval structures.
Latency: Serving a flat index from disk results in massive random I/O fan-out for multi-term queries. This leads to tail latencies of 4–12 seconds, far exceeding the interactive budget (typically <1 second) required for retrieval-augmented pipelines.

Existing dynamic pruning techniques (e.g., BlockMax-WAND) are rank-safe (guaranteeing exact top-k results) but assume the index is resident or on fast local storage. At a billion-document scale, the sheer volume of postings makes even pruning insufficient if the underlying data structure cannot fit in memory without linear DRAM growth.

2. Methodology: Hierarchical BM25

The proposed solution, Hierarchical BM25, sacrifices strict rank safety (exact top-k guarantees) to achieve fixed bounds on memory and latency. It replaces a single flat index with a two-level architecture:

2.1 Two-Level Index Structure

Level-1 (Coarse Index): A resident, pre-computed index over ~1,000 topical, size-balanced document groups (clusters). This index is small (~4 GB) and fits entirely in memory. It acts as a filter to select which clusters a query should visit.
Level-2 (Fine Index): Contains the full inverted index for all one billion documents. It is not fully resident. Instead, it is served via a fixed-size cache (~1M entries, ~400 MB) backed by NVMe storage. The resident footprint remains constant regardless of corpus growth.

2.2 Cluster Formation (Level-1 Construction)

Clusters are formed using Latent Dirichlet Allocation (LDA) with specific constraints to ensure selectivity and balance:

Feature Selection: Only mid-frequency terms (high discriminative power, avoiding common stopwords and rare noise) are used for clustering.
Balance Constraint: To prevent "hot" topics from creating oversized clusters (which would break the latency budget), documents are assigned to clusters via capacity-capped assignment with overflow splitting. This ensures all ~1,000 clusters are roughly equal in size.
Incremental Maintenance: As the corpus grows, oversized clusters are split locally based on secondary topic vectors without requiring a global re-clustering.

2.3 Query Processing and Selection Signals

When a query arrives, the system performs a two-pass process:

Coarse Selection (Level-1): The system scores the ~1,000 clusters using two signals to select the top ~40 clusters (visiting ~4% of the corpus):
- Aggregate Signal ( $A$ ): The IDF-weighted total frequency of query terms across all documents in a cluster. This captures single-term topical concentration.
- Co-occurrence Signal ( $B$ ): A specialized signal for "spread-out" discriminative terms (high IDF but scattered across clusters). It tracks whether multiple such terms appear together in a single document within a cluster. This is computed via a small, cluster-tagged inverted index over a specific subset of terms ( $T_M$ ).
- Selection Score: $Score(c,Q) = A(c,Q) + \lambda B(c,Q)$ .
Exact Scoring (Level-2): Only the selected clusters are searched exhaustively. Crucially, documents are scored using global corpus statistics (global document frequency and average document length) stored in a small (~100 KB) resident table. This ensures that every scored document receives its exact, flat-index BM25 score, confining the approximation strictly to which clusters are visited, not how documents are scored.

3. Key Contributions

The paper makes three primary contributions:

Hierarchical BM25 Architecture: A two-level index that decouples resident memory from corpus size. It achieves a fixed ~4.4 GB resident footprint and ~300 ms latency for 16-term queries over 1 billion documents, compared to the 400 GB/4–12s baseline.
Cross-Cluster Scoring Correction: The authors identify and fix a correctness bug in multi-cluster retrieval where using local IDF statistics per cluster biases scores. They introduce a global DF table to ensure scores are comparable and exact across clusters, confining the approximation solely to cluster selection.
Analytical Comparison to BlockMax-WAND: The paper argues that for long queries (16–32 terms) common in retrieval-augmented pipelines, cluster selection is more effective than WAND-style pruning. WAND relies on document-level multi-term co-occurrence, which becomes scarce as query length increases and terms decorrelate. Hierarchical BM25 relies on single-term topical concentration (Signal A) and specific co-occurrence tracking for spread-out terms (Signal B), which remain bounded in cost regardless of query length.

4. Results

Evaluation was conducted on a single node with 1 billion documents and 16–32 term queries:

Latency: Hierarchical BM25 maintains ~300 ms latency for 16-term queries, staying within the 1-second budget. This is 4.7–5.6× faster than a flat multi-threaded index and 15–31× faster than a flat single-threaded index.
Throughput:
- Cold Start: Sustains ~2.6–3.5 QPS (single-threaded), significantly outperforming flat baselines.
- Warmed Cache: With a populated Level-2 cache, throughput reaches ~32 QPS (vs. <3 QPS for flat indexing).
Quality (500K Document Configuration):
- Visiting 5–10% of clusters recovers 0.83–0.92 of the exhaustive result score.
- Recall at depth 20 and 100 approaches the flat index's recall as the visited fraction increases to 10%.
- Note: Billion-scale recall is extrapolated from these smaller-scale measurements, not directly measured.

5. Significance and Claims

The paper positions Hierarchical BM25 as a structural solution to the "lexical scaling" problem in hybrid retrieval. Its significance lies in:

Enabling Hybrid Pipelines: It allows the lexical component of hybrid retrieval to scale to billions of documents without the prohibitive memory costs or latency penalties that currently bottleneck the system.
Trade-off Justification: The authors argue that giving up rank safety is a pragmatic trade for interactive systems. In a hybrid pipeline, the lexical top-k is merged with dense candidates and re-ranked; swapping the 10th for the 11th lexical candidate rarely impacts the final output, whereas a 4-second latency breaks the user experience entirely.
Architectural Insight: It demonstrates that for long, disjunctive queries, selecting topical clusters is computationally superior to pruning a dense document stream, provided the selection mechanism accounts for both aggregate term concentration and specific document-level co-occurrence.

6. Limitations and Open Questions

The paper is modest about its claims, explicitly noting:

Rank Safety: Unlike BlockMax-WAND, Hierarchical BM25 is not rank-safe. It does not guarantee returning the exact top-k documents.
Unmeasured Billion-Scale Recall: Quality metrics (nDCG, recall) are measured at 500K documents and extrapolated. The actual performance at 1 billion documents on a natural vocabulary remains unverified.
Co-occurrence Signal: The contribution of the co-occurrence signal ( $B$ ) has not been isolated empirically; current benchmarks rely heavily on the aggregate signal due to the query mix used.
Baseline Comparison: A direct, empirical comparison against BlockMax-WAND (especially with document reordering) has not yet been performed.
Vocabulary Bias: The evaluation uses a compact vocabulary to stress-test the index structure; performance on natural, large-vocabulary corpora is an open step.