Paper deep dive

Hierarchical BM25: Lexical Search at Billion-Document Scale

Umesh Deshpande, Swaminathan Sundararaman

Year: 2026Venue: arXiv preprintArea: cs.IRType: PreprintEmbeddings: 77

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%

Last extracted: 8/4/2026, 4:07:12 AM

Summary

The paper introduces Hierarchical BM25, a two-level lexical search index designed to handle one billion documents with fixed memory (~4.4 GB) and latency (~300 ms) bounds. It replaces a flat 400 GB index with a resident coarse Level-1 index over ~1K topical clusters and a Level-2 index served from cache/NVMe. The method uses aggregate term frequency and same-document co-occurrence signals to select relevant clusters, sacrificing exact rank safety for significant throughput improvements over flat indexing and dynamic pruning methods like BlockMax-WAND.

Entities (11)

Hierarchical BM25 · algorithm · 98%BM25 · algorithm · 95%Level-1 Index · component · 95%Level-2 Index · component · 95%BlockMax-WAND · algorithm · 92%IBM Research · organization · 90%Latent Dirichlet Allocation · algorithm · 90%Swaminathan Sundararaman · person · 90%Umesh Deshpande · person · 90%DRAM · hardware · 85%NVMe · hardware · 85%

Relation Signals (8)

Hierarchical BM25 → achieveslatency → ~300 ms

confidence 95% · Sixteen-term queries over one billion documents return in ~300 ms

Hierarchical BM25 → achievesmemoryfootprint → ~4.4 GB

confidence 95% · The resident footprint is ~4.4 GB, independent of corpus size.

Hierarchical BM25 → uses → Level-1 Index

confidence 95% · A coarse Level-1 index over ~1K document groups is pre-computed and kept resident.

Hierarchical BM25 → uses → Level-2 Index

confidence 95% · A fine Level-2 index over the full billion documents is served from a fixed-size cache plus NVMe.

Umesh Deshpande → affiliatedwith → IBM Research

confidence 90% · Umesh Deshpande ... IBM Research

Swaminathan Sundararaman → affiliatedwith → IBM Research

confidence 90% · Swaminathan Sundararaman ... IBM Research

Hierarchical BM25 → partitionscorpususing → Latent Dirichlet Allocation

confidence 90% · We therefore partition topically, using Latent Dirichlet Allocation (LDA)

Hierarchical BM25 → comparesagainst → BlockMax-WAND

confidence 85% · A direct comparison against document-reordered BlockMax-WAND remain open.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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 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 ~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 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 GB, independent of corpus size. Sixteen-term queries over one billion documents return in ~300 ms (4.7x to 5.6x the throughput of a flat multi-threaded index), and a warmed cache sustains ~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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

75,466 characters extracted from source content.

Expand or collapse full 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 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 ∼ 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 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 4.4 GB, independent of corpus size. Sixteen-term queries over one billion documents return in ∼300 300 ms (4.7–5.6× the throughput of a flat multi-threaded index), and a warmed cache sustains ∼32 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 ∼400 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 d1,…,d10d_1,…,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 ∼4.4 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 ∼1 1K 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 ∼300 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 ∼1 1K 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×1.6× apart in score purely because of which cluster they sit in. We fix this (Section 3.4) by scoring every cluster from one ∼100 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 BM25’s latency and throughput directly at billion-document scale (Section 5). A companion paper addresses lexical recall for the semantic vocabulary gap via query expansion. That is a distinct problem, evaluated separately. 2 Background and Related Work BM25 scores a document D for a query Q as a sum over query terms: each term contributes an inverse-document-frequency weight times a saturated, length-normalized term-frequency factor [3]. The parameter k1k_1 caps repetition; b discounts long documents. Computing the scores requires two corpus-wide statistics per term—document frequency and per-document term frequency—materialized in an inverted index; Okapi first deployed the design at TREC [4]. Dense retrieval encodes queries and documents into a shared embedding space and ranks by vector similarity [8]; HNSW [6] and IVF with product quantization [7] make it tractable at billions of vectors. The semantic half of hybrid retrieval scales this way. The lexical half does not. The baseline strategy for a multi-term BM25 query is ranked-OR: treat the query as a disjunction, score every document matching at least one term, keep the top-k. Turtle and Flood analyze its two exhaustive executions—term-at-a-time and document-at-a-time [11]. Its cost is the size of the posting-list union: ranked-OR grades every exam that answers at least one of the query’s questions, and with 32 questions nearly the whole school hands one in. On this corpus the union grows from 39M to 148M documents as queries grow from 8 to 32 terms (Section 4.1), and the flat baselines of Section 5 are exhaustive ranked-OR over a disk-resident index. Dynamic pruning accelerates ranked-OR without changing what it returns. MaxScore [11] and WAND [9] maintain per-term upper bounds on score contributions and skip documents that provably cannot enter the top-k—a high-jump qualifier: once early jumpers set a high bar, later competitors whose personal bests fall short are waved off without jumping. BlockMax-WAND stores a bound per ∼ 128-posting block instead of one per term, enabling far larger skips [10]. MaxScore partitions terms into essential and non-essential lists rather than pivoting through a dense document-id stream, which makes it the sturdier of the two on long disjunctive queries—a distinction Section 4.1 returns to. ASC [17] and Block-Max Pruning [18] extend the idea to learned sparse retrieval. All of these are exact: they return ranked-OR’s top-k and differ only in how much of the union they can prove skippable. Organized by their relation to ranked-OR: exhaustive evaluation pays for the full union; the pruning line keeps ranked-OR’s semantics and shrinks its work; Hierarchical BM25 shrinks its scope, running plain exhaustive ranked-OR inside each visited cluster with only ∼4% 4\% of the corpus in the union. The pruning line also assumes an index available for traversal—resident, or on fast local storage—so its first question is how many postings a query touches. At 10910^9 documents the first question is DRAM. A flat index is ∼400 400 GB: holdable on a large-memory server, but a cost that is linear in the corpus (10B documents would demand ∼4 4 TB) and that competes with the dense-retrieval structures sharing the node in a hybrid deployment. The coarse level of Section 3 converts that linear DRAM cost into a ∼4.4 4.4 GB constant (Table 3). The two approaches compose: BMW-style pruning can run inside each selected cluster—though unlike BMW, cluster selection here is not rank-safe. A complementary line reorders document ids instead of pruning: recursive graph bisection assigns topically similar documents adjacent ids, shortening the runs a postings scan must skip [12]. Section 4 returns to this technique. The closest architecture is selective search: partition the corpus into topic-based shards, select a few shards per query, and search only those, exactly [13]. Hierarchical BM25 shares that skeleton—including its resource bounds, which come with sharding itself, and comparable within-shard scoring, routine in the cooperative single-owner setting. The difference is the selection evidence. CORI scores shards from per-term collection statistics—document counts per term, combined by query operators—and stores no document-level information at all [14]. Taily models, per shard, the score distribution of the documents containing all query terms, but estimates how many such documents exist from single-term counts under an explicit term-independence assumption, adopted precisely to avoid counting mutual term occurrences [16]. Neither can tell whether the query’s terms hit the same document or different documents inside a shard. ReDDE is the partial exception: it ranks documents in a sampled central index and credits their source shards [15], so it does observe same-document co-occurrence—but only for documents in the sample, typically 1–4% of each shard [16], and a shard’s few documents that co-locate several rare query terms are usually not among them. The evaluations that established these selectors also sat where such limits cost little—mean query lengths of 2.1–3.1 terms for Taily and 3–7 for ReDDE; CORI’s 1995 evaluation did use long structured INQUERY queries, but per-term statistics discard co-occurrence at any query length. At the 16–32-term queries of retrieval-augmented pipelines, same-document co-occurrence separates the right shard from the wrong one, and the B(c,Q)B(c,Q) signal of Section 3.5 tracks it exactly, for every document rather than a sample, for the informative terms whose scattered occurrences raise no single cluster’s aggregate score. At query time the signal turns into a selection decision as follows: the query’s discriminative terms are looked up in a small inverted index whose postings carry cluster ids; merging those posting lists by document id reveals which documents contain several of the terms at once, and yields, per cluster, the strongest such document’s combined idf; that per-cluster score is added to the cluster’s aggregate score—the idf-weighted total frequency of the query’s terms across all of the cluster’s documents—and the top clusters are selected on the sum. Cluster selection thus rests on exactly two measures: how much of the query’s vocabulary a cluster holds in aggregate, and whether any single document inside it brings the discriminative terms together. A cluster holding one document where the query’s rare terms meet outranks a cluster where the same terms appear only scattered—the distinction every selector above misses. An effectiveness comparison against these selectors remains open, alongside the BMW benchmark (Section 6). Tables 1 and 2 summarize the landscape on the axes the paper turns on: whether the top-k is exact, what signal each method needs to save work, and how cost moves as query length q grows. Table 2 separates the design’s two selection signals (Section 3.5). Table 1: Three strategies for a long disjunctive BM25 query. Exhaustive ranked-OR scores the full posting-list union and is exact by construction. BlockMax-WAND (BMW) returns the same top-k but skips documents it can prove cannot enter it; that skipping works only where multi-term co-occurrence exists in the data. Hierarchical BM25 gives up exactness and visits a fixed number of topically selected clusters, so its cost is set by a budget, not by the data. Sections 4.1 and 4.2 develop the last two rows quantitatively. Ranked-OR BMW Hier. BM25 Exact top-k yes yes no Work avoided none provably-losing documents unselected clusters Signal needed — multi-term co-occur. single-term concentration Cost as q grows grows (union) grows (data-dep.) fixed (budget) Table 2: The same field re-sorted by co-occurrence evidence: where each method’s evidence comes from, and what its query cost tracks as query length grows. “TMT_M” is the fixed set of discriminative-but-spread-out terms of Section 3.5: high idf, yet scattered across clusters so that no single cluster’s aggregate score reflects them; “agg.” is selection by the aggregate signal alone (Section 3.4); “+B” is the full design, adding the exact same-document co-occurrence signal B(c,Q)B(c,Q) over TMT_M. Only the two rightmost designs keep cost independent of query length; the rightmost additionally recovers co-occurrence for TMT_M terms, which reduces—but does not eliminate—the aggregate signal’s dilution, since A’s noise from terms outside TMT_M persists in the combined score. Ranked-OR BMW Hier. (agg.) Hier. (+B) Co-occurrence signal not needed (scores all) exact, all terms none exact, TMT_M terms Query cost driver posting union candidate pool fixed budget budget + TMT_M df Degrades as q↑q cost cost SNR SNR (reduced) BEIR is the standard zero-shot benchmark for retrieval quality [5]; we do not use it. The contribution here concerns latency and memory at 10910^9 documents, beyond BEIR’s largest datasets. Section 5 measures those two axes directly, and Section 6 confronts the resulting quality gap explicitly. 3 Hierarchical BM25 The design target is a hard guarantee: every lexical query returns in under one second over one billion documents, without provisioning hundreds of gigabytes of RAM per node. Hierarchical BM25 meets it by replacing one flat index with two indexes at different granularities. Only a small, bounded fraction is resident at query time. The design mirrors how a person searches a library. Nobody scans every shelf. You first read the aisle signs and pick the two or three aisles whose labels match your topic. Only then do you search those shelves carefully. Level-1 is the aisle signs: small enough to keep entirely in memory, consulted on every query. Level-2 is the shelf search: large, kept on NVMe, and touched only for the aisles that survived the first step. The trade from Section 1.1 lives entirely in that first step—if the right book sits in an aisle whose sign never mentions your topic, you will not find it. Everything after the first step is exact. queryLevel-1∼ 1K groups∼ 4 GBresidentLevel-21B documents1M cache+ NVMetop-kkcandidatesprune Flat index (no hierarchy): 1B documents, ∼ 400 GB, disk-bound Hierarchical BM25 (∼ 4.4 GB resident) Figure 1: Hierarchical BM25. A resident coarse index over document groups prunes the corpus before a fixed-size, NVMe-backed fine index scores survivors, cutting the resident footprint from ∼400 400 GB to ∼4.4 4.4 GB. Table 3: Flat vs. hierarchical lexical index. The hierarchy cuts resident memory ∼90× 90×, which is what makes the latency guarantee structural rather than average-case. The global DF table (Section 3.4) lets every cluster score with the same corpus-wide statistics. Configuration Granularity Size Residency Flat (no hier.) 1B documents ∼ 400 GB disk-bound Hier. Level-1 ∼ 1K groups ∼ 4 GB resident Hier. Level-2 1B documents ∼ 400 GB total (∼ 400 MB res.) 1M cache + NVMe Global DF table |V||V| terms ∼ 100 KB resident 3.1 Why a flat index fails at a billion documents A flat inverted index stores, per term, the document frequency and per-document keyword frequencies BM25 needs. At one billion documents this is ∼400 400 GB. Holding it resident is possible on large-memory servers, but at a DRAM cost that is both large and linear in the corpus (Section 2); the economical deployment—and the baseline we measure—serves it from disk. The postings for a multi-term query are scattered, so each query issues many random reads. Latency then scales with fan-out rather than with the number of relevant documents. Tail latency routinely exceeds one second. This is the “no-hierarchy” baseline. 3.2 A two-level index Hierarchical BM25 organizes the corpus into two levels (Figure 1, Table 3). Level-1 (document groups). Documents are aggregated into ∼1 1K groups. The Level-1 index carries group-level document- and keyword-frequency statistics. It is ∼4 4 GB, pre-computed, and resident. It acts as a coarse filter: it identifies the groups most likely to contain relevant documents, before any fine scoring runs. Level-2 (documents). The Level-2 index holds fine per-document statistics for all one billion documents. We do not pin it in memory. Instead, we serve it through a fixed-size cache of ∼1 1M entries (∼400 400 MB resident). The remainder lives on NVMe and is paged in on demand. The cache size is fixed and independent of corpus size. The resident footprint—and therefore the worst-case query cost—does not grow as the corpus grows. Section 3.3 describes how the ∼1 1K groups are formed in the first place; Section 3.4 then details how we build Level-1 over them and how we make scores from different Level-2 clusters comparable before merging. 3.3 Forming the clusters: balanced topical LDA How the corpus is partitioned into ∼1 1K groups is not a free choice. It is the assumption everything downstream stands on. Level-1 is selective only if term statistics differ sharply between clusters: if documents were grouped by ingestion order or by hash, every cluster’s vocabulary would approximate the global distribution, the ∼1 1K per-cluster term statistics of Section 3.4 would be nearly interchangeable, and selecting the top 40 would be close to arbitrary—precisely where the recall surrendered by the trade would collapse. In the library analogy: aisle signs help only if books are shelved by subject. A library shelved by arrival date has signs, but every sign reads the same. We therefore partition topically, using Latent Dirichlet Allocation (LDA) [2] with two deliberate constraints: which terms the model sees, and how large a cluster is allowed to grow. Features: the mid-frequency band only. Luhn’s classic observation, built on Zipf’s law, is that a term’s power to discriminate content peaks at mid frequency [1]. The highest-frequency terms appear everywhere and say nothing about topic—knowing a document contains “the” or “system” places it on no particular shelf. The rarest terms are individually informative but statistically useless for clustering: a term appearing in a few dozen documents out of a billion gives a topic model almost nothing to generalize from, and produces sparse, unstable assignments. So each document’s feature vector is restricted to the ∼ 10K mid-idf terms of the |V|≈20,680|V|≈ 20,680-term vocabulary, dropping the highest-df head and the rare tail. This band overlaps the discriminative-but-spread-out terms that the co-occurrence signal tracks (Section 3.5); both mechanisms want terms discriminative enough to carry topical signal, but the two select differently within it: clustering features favor terms that concentrate (they define where a document lives), while the co-occurrence signal’s TMT_M deliberately favors the discriminative terms that do not concentrate, since those are exactly the ones no single cluster’s score can surface. The vocabulary’s topical middle feeds both, split by whether a term localizes or spreads. Balance is enforced, not hoped for. The latency bound assumes the top-kclu=40k_clu=40 clusters cover ∼4% 4\% of the corpus. Topic popularity is itself Zipfian, so assigning each document to its single most probable topic would produce a few enormous clusters—one popular-topic cluster holding 10–20% of all documents, which breaks the budget the moment a query selects it. No aisle may hold a fifth of the library. We therefore use LDA with a modest topic count for representation (each document gets a topic-proportion vector) and impose balance at assignment: documents are grouped into ∼1 1K equal-size clusters over those topic vectors, via capacity-capped assignment with overflow splitting. A document capped out of its best-fitting cluster goes to its next-best; the cost is a small loss of topical purity at cluster boundaries, paid to keep every cluster’s size—and therefore per-query work—bounded. This is the build-time twin of the query-time guarantee in Section 3.6: the fixed cluster budget bounds cost only because no single cluster can be oversized. Growing K by splitting, without reclustering. The cluster count is not frozen at build time. As the corpus grows or its topic mix drifts, individual clusters cross the size threshold that the balance invariant protects: a cluster exceeding, say, 1.5×1.5× the target size N/KN/K inflates the per-query work of any query that selects it. Rather than re-running LDA over the whole corpus to raise K globally, we split only the offending clusters, locally. Because every document already carries its LDA topic-proportion vector from the representation stage, a split needs no new clustering pass: we partition the oversized cluster’s documents by their dominant secondary topic (the strongest topic other than the one that placed them here), sending each sub-topic to a child cluster. This is a partition of vectors already in hand, O(|cluster|)O(|cluster|) and local to one cluster’s documents. Three properties make it cheap in the parts that matter. The two child Level-2 indexes are re-partitioned from the parent’s postings alone, touching no other cluster. The two children’s Level-1 statistics are recomputed from each child’s own vocabulary (Section 3.4)—two small rows in the resident table. And the global DF table is untouched: df(t)=∑cdfc(t)df(t)= _cdf_c(t) splits the parent’s contribution across two children without changing the total, so the cross-cluster scoring correction of Section 3.4 needs no update and Level-2 scoring stays exactly correct through the split. Splits are per-cluster and independent, so they parallelize and can run online while the rest of the index serves. The one thing splitting does not do is restore global optimality: a document trapped in a lineage stays there, since splits subdivide but never migrate documents across the cluster tree. Splitting is the fast incremental path that keeps clusters near target size between the periodic full reclusterings discussed in Section 6; it defers those rebuilds rather than eliminating them. One caveat on what this buys. Topical partitioning makes the single-term concentration signal of Section 4 exist; it does not by itself say how much recall the top-40 selection preserves. That number—and the gap between this partitioning and cheaper alternatives such as cutting a recursive-graph-bisection ordering [12] into equal segments—belongs to the Recall@k measurement flagged in Section 6 as the most important open step. 3.4 Building Level-1 and normalizing across clusters The first of the two selection signals is the aggregate one: the idf-weighted total frequency of the query’s terms across a cluster’s documents. Level-1 is not a hand-designed summary; it is built mechanically from each cluster’s own index, and two details decide whether it works. The first is the per-cluster statistic each term contributes: get it wrong and the coarse filter stops being selective. The second is how independently computed per-cluster scores are made comparable at merge time: get it wrong and the merged ranking stops being valid. The per-cluster term statistic. For each Level-2 cluster, we scan that cluster’s inverted index in parallel across its segments, sum each term’s raw occurrence count—its collection frequency fc(t)f_c(t) within the cluster—and keep the highest-frequency terms. Each kept term contributes one entry to a resident table: a saturated weight wc(t)=(log2⁡max⁡(fc(t),1))2.w_c(t)= ( _2 (f_c(t),1) )^2. The saturation matters, in the same spirit as BM25’s own term-frequency saturation: a term ten times more frequent contributes roughly four times the weight, not ten, so one very common term cannot dominate a cluster’s representation and crowd out the rest of its vocabulary. The whole of Level-1 is this table—per term, a sparse vector of cluster weights—plus each cluster’s document count. Nothing else is needed at the coarse level. One property of this construction matters later. It sums a term’s evidence across every document in the cluster, rather than taking the best single document. A query term’s Level-1 signal in a cluster therefore reflects that term’s aggregate presence there. Section 4 returns to this observation when comparing against WAND-style pruning. Making per-cluster scores comparable. The second specification is subtler. Level-2 is not one shared index but ∼1 1K independent per-cluster BM25 indexes. Left to itself, each cluster’s search engine infers BM25’s inverse-document-frequency term from what that cluster alone contains: its own document count NcN_c and its own per-term document frequency dfc(t)df_c(t). This is a correctness bug, not just an approximation. BM25 is additive across terms—S(d,Q)=∑tidf(t)TF(t,d)S(d,Q)= _tidf(t)\,TF(t,d)—and a term’s true, corpus-wide idf(t)idf(t) can differ sharply from its cluster-local estimate, in either direction. Two documents with identical term frequencies can then receive different scores purely because of which cluster they sit in. The bug is easiest to see as grading on a curve. Two students hand in identical exams. One sits in a class of experts, the other in a class of beginners. Curved, per-class grades score the same exam differently. An absolute standard scores it the same everywhere. Per-cluster IDF is the curve; the global table we introduce below is the absolute standard. A concrete retrieval example. A document group organized by topic concentrates that topic’s characteristic terms. Inside a cluster of Kansas-related documents, a term like “kansas” looks common (dfc/Ncdf_c/N_c is high) even though it is globally rare. “Population” looks unremarkable in both places. Two documents with the same term frequencies for kansas, population, sitting in different clusters, can end up 1.6×1.6× apart in score. No single per-cluster correction factor can repair this after the fact. The distortion is per-term and hidden inside a sum; a single scalar cannot undo per-term errors that do not move together. We avoid the problem instead of correcting for it. At build time, alongside the Level-1 vocabulary extraction, we aggregate df(t)=∑cdfc(t)df(t)= _cdf_c(t) and the global average document length avgdlavgdl across all ∼1 1K clusters into one table, keyed by term. The table is small: one count per term, |V|≈20,680|V|≈ 20,680 in our setting, ∼100 100 KB total (Table 3). It is the only piece of global state Level-2 scoring needs. At query time, we construct each cluster’s BM25 weight from the global N, df(t)df(t), and avgdlavgdl in this table—not from the cluster’s own inferred statistics. Every other input to the score—raw term frequency ft,df_t,d, document length |d||d|—is already a correct, local property of the document. Supplying only these three global quantities makes each cluster’s score identical to the score a single flat index over the whole corpus would have returned. Merging the per-cluster top-k lists into one global ranking is then a plain concatenate-and-sort. No per-cluster correction factor, and nothing left to get wrong. The only cost is building and keeping resident a ∼100 100 KB table. It changes neither the postings read per query nor the clusters visited, so it leaves the latency and throughput results in Section 5 unaffected. It only changes which number each visited cluster reports as a document’s score—and makes that number correct. This fix is also what confines the trade of Section 1.1 to cluster selection alone. Rank safety is surrendered only in deciding which clusters to visit—never in how a visited document is scored. 3.5 The co-occurrence selection signal The aggregate score is deliberately only half of cluster selection. The design pairs it with a second signal, built by the same scan, that supplies the one kind of evidence aggregation cannot: whether several of the query’s discriminative terms meet in a single document. The set of terms worth tracking for co-occurrence is not simply “the important terms.” It is, more precisely, the terms the aggregate signal A(c,Q)A(c,Q) fails to route—fails, that is, to place their clusters among the selected ones—because B is redundant wherever A already succeeds. Two properties define that set, and both are necessary. First, the term must be discriminative: high idf. A term with idf(t)≈0idf(t)≈ 0 contributes almost nothing to S(d,Q)=∑tidf(t)TF(t,d)S(d,Q)= _tidf(t)\,TF(t,d) wherever it occurs, so two such terms co-occurring in a document means nothing—their combined score is negligible. Tracking co-occurrence among low-idf terms detects coincidences, not matches. Only for high-idf terms does same-document co-occurrence imply a genuine top-k candidate. Second, and this is the property the aggregate signal makes essential, the term must be spread across many clusters, not concentrated in a few. Here the two signals divide the vocabulary cleanly. A concentrated discriminative term, one confined to a handful of clusters, already routes correctly under A alone: those few clusters score high on single-term concentration and clear the top-kcluk_clu cutoff without any co-occurrence information. For such a term B adds nothing: its clusters were going to be visited regardless. A spread-out discriminative term is the opposite case: scattered thinly across many clusters, it pushes no single cluster over the cutoff, so to A it is nearly invisible, almost a stopword. Its only path to mattering is to co-occur, in one document, with another such term—and detecting that requires exactly the document-level tracking A lacks. These spread-out, high-idf terms are the terms B exists for. This inverts a natural but wrong intuition. One might select TMT_M by concentration, reasoning that the most topical terms deserve tracking. But a concentrated term is precisely the term A handles best; tracking its co-occurrence is wasted effort. The terms that need B are the discriminative terms that refuse to concentrate—individually meaningful, yet localized nowhere, so that a real match built from two of them is invisible to any aggregate. We therefore define TMT_M as the M terms scoring highest on the product of discriminativeness and cluster spread: idf(t)⋅Hclu(t)idf(t)· H_clu(t), where Hclu(t)H_clu(t) is the entropy of t’s document-frequency distribution across the ∼1 1K clusters, high when t is smeared evenly and low when t concentrates. Both factors are already materialized: idf(t)idf(t) from the global DF table (Section 3.4), and the per-cluster dfc(t)df_c(t) that HcluH_clu needs from the same Level-1 aggregation. The signal adds one cheap question per cluster—does any single document here contain several of the query’s spread-out discriminative terms together?—which is exactly the question A(c,Q)A(c,Q) cannot answer and, for these terms, the only question that routes them. We therefore build a second, small inverted index over only TMT_M (we use M=1,000M=1,000 of the |V|≈20,680|V|≈ 20,680 terms). Concretely, it is an ordinary inverted index with one addition: each posting stores the pair (document id,cluster id)(document id,cluster id) rather than the document id alone, and each term’s postings are kept sorted by document id. The cluster id riding along in every posting is what lets the query-time computation below attribute a document to its cluster without a second document-to-cluster lookup. The whole index’s size is ∑t∈TMdf(t) _t∈ T_Mdf(t); because TMT_M excludes the high-df head—those terms have low idf and are filtered out by the discriminativeness factor—this sum stays bounded, though the spread criterion means the terms are not the very rarest in the vocabulary and their lists are correspondingly longer than a rare-tail selection would give (Section 4.2 quantifies the resulting cost). It is built from the same postings scan already used for the rest of Level-1 (Section 3.4): the cluster id is known at build time, so tagging costs nothing extra and adds no new traversal. At query time, for the query terms that fall in TMT_M (call this subset QM=Q∩TMQ_M=Q∩ T_M), we retrieve their posting lists, group matches by document, and compute, per cluster c, the best co-occurring document’s TMT_M-term score: B(c,Q)=maxd∈c∑t∈QM∩didf(t).B(c,Q)= _d∈ c _t∈ Q_M∩ didf(t). B(c,Q)B(c,Q) is exact, not estimated. It directly answers whether this cluster contains one document that hits several of the query’s spread-out discriminative terms at once—precisely the question A(c,Q)A(c,Q) cannot answer, and, for terms too scattered to raise any cluster’s aggregate score, the only question that routes them. A cluster containing a document that matches five terms from QMQ_M scores higher under B than one whose best document matches two, in proportion to those terms’ idf. This matches the intuition: co-occurrence among discriminative terms should move the ranking, while co-occurrence among terms like “consists” or “together” should not—and indeed cannot, since such terms carry negligible idf and are excluded from TMT_M in the first place. Selecting clusters at query time. Selection computes both signals over resident structures and ranks their sum. For the aggregate signal, we tokenize the query and, for each query term, fetch its row of cluster weights from the routing table; every cluster accumulates A(c,Q)=∑t∈Qidf(t)wc(t)A(c,Q)= _t∈ Qidf(t)\,w_c(t)—q×∼1q× 1K multiply-adds, negligible next to everything downstream. A cluster holding evidence for several query terms therefore outranks one that matches a single term very strongly: the aggregate half rewards coverage of the query, not a single lucky match. For the co-occurrence signal, the query’s TMT_M terms drive the posting-list merge described next, yielding B(c,Q)B(c,Q) per cluster. The two combine additively: Score(c,Q)=A(c,Q)+λB(c,Q).Score(c,Q)=A(c,Q)+λ\,B(c,Q). Retaining A(c,Q)A(c,Q) means a cluster still earns credit for single-term concentration among the q−|QM|q-|Q_M| terms outside TMT_M; B(c,Q)B(c,Q) contributes the document-level evidence for the terms most likely to determine the true top-k. λ is a tunable weight; both terms are already idf-scaled, so λ=1λ=1 is a reasonable starting point pending empirical tuning. Only the top-scoring clusters proceed to Level-2, not the whole ∼1 1K. Section 5 uses 40. Computing B at query time. The definition of B(c,Q)B(c,Q) takes a max, over documents in a cluster, of a per-document idf sum—so the computation must group TMT_M-term hits by document first, then reduce to a per-cluster max. Because the TMT_M index keeps each posting list sorted by document id, this is a document-at-a-time merge, the same traversal an ordinary inverted index uses for a conjunctive query. We advance a cursor into each of the |QM||Q_M| query-TMT_M lists, always stepping the one at the smallest document id; galloping search over the sorted lists keeps the merge efficient when the lists differ sharply in length. Two small hash maps hold the running state: one keyed by document id accumulates that document’s idf sum as each list contributes a hit, and one keyed by cluster id keeps the largest per-document sum seen so far in that cluster. When a document is finalized (all cursors have passed it), its accumulated sum updates its cluster’s running max—and the cluster id needed for that update is already in the posting, so no separate lookup is required. After the merge, the cluster map holds B(c,Q)B(c,Q) for every cluster the TMT_M query terms touched; all other clusters take B=0B=0. Both maps are bounded by the number of distinct documents the QMQ_M terms reach, i.e. ∑t∈QMdf(t) _t∈ Q_Mdf(t)—the same quantity that bounds query cost below. Two structural choices keep this cheap rather than merely correct. First, we deliberately do not precompute a cluster-by-term co-occurrence table: such a table would store each cluster’s aggregate TMT_M-term presence, which is exactly the document-blind signal A(c,Q)A(c,Q) already carries and B exists to go beyond; it cannot tell whether two such terms landed in the same document or two different ones. Second, we do not materialize pairwise term-term co-occurrence counts either; those are O(|TM|2)O(|T_M|^2), mostly empty, and answer a corpus-wide question rather than the per-cluster, per-document one B needs. The plain cluster-tagged inverted index avoids both extremes: it stores document-level evidence, so the merge can see same-document co-occurrence, without precomputing any pair, so storage stays linear in ∑t∈TMdf(t) _t∈ T_Mdf(t). If the per-cluster max reduction ever dominates, a secondary posting sort (cluster id major, document id minor) lets the merge finish one cluster at a time and bound the document-keyed map to a single cluster’s documents, trading a little build-time sort for a smaller query-time working set. 3.6 Query processing and the guarantee A query is answered in two passes. First, the resident selection structures score the ∼1 1K groups—the aggregate signal from the routing table plus, for the query’s TMT_M terms, the co-occurrence signal of Section 3.5—and prune to the promising ones. This pass is cheap: the structure is small and in memory. Second, only the survivors are scored against Level-2, whose postings come from the fixed-size cache or are paged in from NVMe. Serving the per-cluster indexes. Rather than reopening a cluster’s Level-2 index from disk on every query, we open a handle—index, reader, and schema—for every cluster once, ahead of query serving, and reuse those handles across queries. The underlying index files are memory-mapped. Postings for frequently accessed clusters therefore stay resident under ordinary OS page-cache pressure, while postings for cold clusters remain on NVMe until a query actually reaches them. This is the mechanism that realizes the fixed memory budget in Table 3 in aggregate, without an explicit least-recently-used table keyed by individual postings. Query (16–32 terms) signal A: which clusters are rich in the query’s terms? signal B: where do rare terms meet in a single document? ∼ 40 clusters selected exact BM25 inside each global top-k ++ Figure 2: Query time, conceptually. Routing first, exactness after. Two complementary signals pick the clusters: A asks which clusters are rich in the query’s terms overall, and B asks where several discriminative terms meet in one document—the evidence A cannot see. Only the ∼ 40 selected clusters are searched, with exact BM25 scores throughout, so the approximation lives entirely in the selection step. (Mechanics in Sections 3.6 and 3.5.) Two facts make the sub-second bound structural rather than merely average-case at this operating point. The Level-1 pass bounds how many documents reach fine scoring. The fixed-size Level-2 cache bounds resident memory and worst-case paging. The two bounds have different scopes, and it matters. The memory bound is corpus-independent: the resident footprint stays ∼4.4 4.4 GB whether the corpus is one billion documents or larger, because nothing resident grows with N. The latency bound is not: at a fixed cluster count, a growing corpus puts more documents inside each visited cluster, so per-query work grows with N/KN/K (Section 6); holding it requires growing K, incrementally via the splits of Section 3.3. The sub-second guarantee is therefore a property of the one-billion-document, ∼1 1K-cluster configuration measured in Section 5, maintained under growth by rebalancing—not an asymptotic invariant. The particular split—∼1 1K groups at Level-1, a 1M-entry cache at Level-2—is not arbitrary. Fewer, larger groups would shrink Level-1 further but prune less precisely, pushing more documents into the expensive disk-backed pass. More, smaller groups approach the flat baseline and re-introduce its memory cost. ∼1 1K groups is the point at which the coarse index is cheap enough to keep fully resident, yet selective enough that only a small fraction of the corpus survives to Level-2. The Level-2 cache size follows the same logic in the other direction. It is sized to the working set of frequently accessed postings under realistic query skew, not to the corpus. Growing the corpus grows only the cold tail on NVMe, not the resident footprint. 4 Comparison to BlockMax-WAND at Long Query Lengths Retrieval-augmented pipelines issue longer queries than the 2–5-term web queries WAND-family pruning was originally evaluated against—often 16–32 terms, once a query is combined with expansion terms, related fields, or metadata filters expressed as additional disjuncts. This section argues that this regime specifically favors cluster-level selection over WAND-style pruning. It gives a quantified mechanism for why, and states plainly what remains unmeasured. 4.1 Why WAND’s pruning power depends on query length Section 2 introduced the WAND-family mechanism and its high-jump intuition: a running score threshold θ—the current k-th best score—lets the pivot advance past any run of documents whose upper-bound score cannot exceed it. What that summary leaves open is quantitative. The size of each skip is governed by how far apart, in document-id order, the matching documents are. Sparse candidates permit large skips. Dense candidates force the pivot to advance one small step at a time. For a term with document frequency df(t)df(t) over N documents, the probability that an arbitrary document matches at least one of q independent query terms of similar frequency p=df(t)/Np=df(t)/N is P(matches≥1)=1−(1−p)q.P(matches≥ 1)=1-(1-p)^q. Using this corpus’s own term statistics (N=109N=10^9, |V|≈20,680|V|≈ 20,680, ∼400 400 GB of keyword-frequency data ⇒ average df(t)≈5×106df(t)≈ 5× 10^6, p≈0.005p≈ 0.005), the candidate pool—the set of documents WAND’s pivot must at least consider—grows substantially with query length: q (terms) 8 16 32 Candidates matching ≥1≥ 1 term 39M 77M 148M Longer queries do raise θ faster in principle. More terms give more ways for a document to accumulate score. But this holds only when query terms correlate—when the same documents that match one term are disproportionately likely to match others. For topically unrelated terms drawn independently, the true top-k requires rare multi-term co-occurrences scattered across the corpus. θ then climbs slowly while the candidate pool grows as shown above. This is the opposite of WAND’s favorable regime (short queries, correlated terms)—and it is the mechanism behind MaxScore’s robustness on long disjunctive queries noted in Section 2, since MaxScore does not pivot through the dense docid stream at all. A fair baseline for this comparison should therefore include MaxScore; we have not yet benchmarked it. 4.2 Why cluster selection does not have the same growth driver An everyday version of the contrast first. Finding one person who speaks all 16 languages on a list is hard: such people are rare, and you must check candidates one by one. Finding a neighborhood where each of the 16 languages is spoken by someone is easy: many districts qualify. WAND’s pruning accelerates only when the first kind of match exists. Cluster selection needs only the second. In index terms: Level-1 selection (Section 3.4) needs a structurally weaker signal than WAND’s pivot condition. WAND’s threshold rises only when a single document accumulates score from several query terms at once, that is, document-level co-occurrence. Level-1’s per-cluster score for a query term, by contrast, sums that term’s evidence across every document in the cluster (Section 3.4). It requires only that the term be well represented somewhere in the cluster. No other query term needs to co-occur with it in the same document. A cluster can be correctly identified as promising because it is rich in one of the 16–32 query terms, even if the other terms are topically unrelated to it. In exactly the regime where WAND struggles, this signal is more available. The signal does not occur naturally: the balanced topical clustering of Section 3.3 creates it at build time. Under an arbitrary partition, no cluster would be richer in any term than any other, and this section’s argument would have nothing to stand on. Architecturally, Level-1’s cost also does not grow with query length the way WAND’s candidate pool does. The number of clusters visited is fixed by the top-kcluk_clu selection policy (Section 3.4), not by how many documents happen to match a term. Table 1 (Section 2) states this three-way contrast in full. This picture is incomplete in one important way. The aggregate signal that gives Level-1 its query-length independence has a cost of its own. Recall the cluster score A(c,Q)=∑t∈Qidf(t)wc(t)A(c,Q)= _t∈ Qidf(t)\,w_c(t), where wc(t)w_c(t) is term t’s saturated aggregate weight in cluster c (Section 3.4). As q grows, this sum is increasingly dominated by terms with no special relationship to any one cluster. Suppose only a handful of query terms are strongly cluster-discriminative. Their contribution to A(c,Q)A(c,Q) stays roughly fixed as q grows, while the noise from the remaining terms grows with q; under a rough independence assumption, its variance scales linearly in the number of such terms. A(c,Q)A(c,Q)’s signal-to-noise ratio therefore falls at roughly 1/q1/ q. At q=32q=32, this can wash out the very topical concentration this section’s argument relies on. The intuition: judging a cluster by summing 32 terms’ evidence, when only three terms are actually informative about it, is like rating a restaurant by averaging 32 reviews when only three reviewers ate there. The informative few are diluted by the uninformative many. A second, sharper problem: A(c,Q)A(c,Q) cannot tell whether several query terms’ evidence came from the same document or from several different documents scattered across the cluster. That distinction is exactly what determines whether the cluster actually contains a genuinely strong match. The co-occurrence signal (Section 3.5) exists for precisely these two failure modes; Section 4.3 prices it against BMW. 4.3 The co-occurrence signal against BMW’s candidate pool The co-occurrence signal’s cost profile is what makes it viable exactly where BMW degrades. Query cost is bounded by ∑t∈QMdf(t) _t∈ Q_Mdf(t)—the total postings touched across the query’s TMT_M terms. These terms are not the rarest in the vocabulary, so their lists are longer than a rare-tail selection would give; the cost is therefore higher than tracking the rarest M terms, but still bounded, because the discriminativeness factor excludes the high-df head entirely. Critically, this cost does not grow with q the way BlockMax-WAND’s candidate pool does. It grows with how many of the query’s terms fall in TMT_M, not with q itself. A 32-term query with no TMT_M terms costs the same as an 8-term query with none. WAND’s candidate pool, by contrast, grows from 39M to 148M documents across that same range, regardless of which specific terms are involved. Positioned this way, the two-signal selection is better suited than either pure alternative at the query lengths this paper is concerned with. Relative to the aggregate signal alone, the co-occurrence signal supplies exactly the two kinds of evidence Section 4.2 showed missing, at a cost bounded by how many TMT_M terms a query contains rather than by q. Against BlockMax-WAND, it recovers real, exact, document-level co-occurrence—the same signal BMW’s own pivot condition relies on—restricted to the subset of terms where tracking it is cheap. Its query cost is governed by how many TMT_M terms a query happens to contain, not by the corpus-wide candidate pool a disjunctive query touches. It should therefore avoid BMW’s degradation on long, weakly-correlated queries while adding back the one signal the pure aggregate score could not detect—though it mitigates rather than eliminates the dilution of Section 4.2, since A’s noise from the q−|QM|q-|Q_M| terms outside TMT_M remains in the combined score. Table 2 (Section 2) places the two-signal selection alongside exhaustive ranked-OR, BMW, and the aggregate-only baseline on exactly these dimensions. Three further limits apply to the co-occurrence signal specifically, on top of the two already stated for cluster selection in general. First, it helps only when a query actually contains terms from TMT_M, and when at least two of them co-occur in one document within a cluster that A would otherwise rank below the cutoff. This is a genuinely narrow window, since a single TMT_M term contributes nothing new (with one term there is no co-occurrence to detect). On this paper’s own evaluation queries (terms drawn uniformly from the full 20,680-word dictionary), the expected number of TMT_M terms in a query is small and the two-term co-occurrence event smaller still, so the signal fires rarely on the benchmark in Section 5. It helps instead on realistic or expanded queries that concentrate on discriminative terms—plausibly including a companion query-expansion method’s own output, since attribution-selected expansion terms are themselves chosen for high discriminative value, and are exactly the spread-out discriminative terms TMT_M targets. Second, M and the idf-versus-spread weighting in the TMT_M score both trade coverage against storage and query cost, and we have not swept them. Third, and most fundamentally, Score(c,Q)Score(c,Q) is still not a bound of any kind. Nothing prevents a cluster with a low combined score from containing a genuine top-k document whose relevant terms all fall outside TMT_M. This remains, like the rest of Section 3, an approximate heuristic rather than a rank-safe one. Its contribution to selection quality has not been isolated empirically; that measurement joins the open list of Section 6. 4.4 What this argument does and does not establish Two limits on this argument matter as much as the mechanism itself. First, this is not an equal-accuracy comparison; it is the price side of the trade from Section 1.1, stated plainly. BMW is rank-safe: it returns exactly the top-k an exhaustive scan would. Hierarchical BM25’s cluster selection carries no such guarantee. A cluster with a low selection score can still contain a document that would rank in the global top-k. Section 5.4 measures how much this costs at a 500K-document configuration—visiting 5–10% of clusters recovers 0.83–0.92 of the exhaustive result score—though not yet at billion scale. The comparison in this section therefore remains about cost given approximate operation, not cost at equal quality. Section 6 returns to this limitation. Second, document reordering narrows the gap this section relies on. WAND’s density problem is a property of document-id order, not an inherent limit: the recursive graph bisection reordering described in Section 2 makes a term’s postings locally dense in id-space, restoring much of WAND’s ability to make large skips. Cluster selection and document reordering are, at bottom, two different data structures for exploiting the same topical signal. A fair resolution of this comparison therefore requires benchmarking against BlockMax-WAND with such reordering—something we have not done. Until then, this section’s conclusion should be read as a mechanism-level hypothesis with analytical support, not as a settled result. 5 Evaluation 5.1 Setup We measure Hierarchical BM25 in isolation: no query expansion, no semantic stage. The corpus is one billion documents, partitioned into ∼1 1K balanced topical clusters (Section 3.3). The hardware is a single node with 64 AMD EPYC 7343 CPU cores and eight Intel P5500 NVMe SSDs in a RAID-0 array. The index is read from disk rather than pre-warmed into the page cache, so these numbers reflect cold-start I/O, not a best case. Single-query latency is measured with 8-, 16-, and 32-term queries built from terms drawn at random from the corpus dictionary. This mix is deliberately adversarial. It is designed to maximize postings fan-out, not to resemble a natural query, because fan-out is what stresses the index structure. At this setting, Hierarchical BM25 visits about 4% of the corpus per query—the fraction of documents whose Level-1 clusters survive the coarse filter. One property of this corpus must be stated for the term-statistics arguments to be interpreted correctly. Its vocabulary is compact (|V|≈20,680|V|≈ 20,680 terms over 10910^9 documents), so every term is frequent (average df(t)≈5×106df(t)≈ 5× 10^6) and there is no natural rare tail. This is well suited to what the benchmark measures: uniform-random queries over a compact, uniformly frequent vocabulary maximize postings fan-out, which is the structural stress the latency and throughput claims are about. It is poorly suited to everything else: a natural corpus at this scale carries a vocabulary orders of magnitude larger with a Zipfian tail, and the clustering-feature selection of Section 3.3 and the TMT_M selection of Section 3.5 are specified for that setting and exercised only weakly here. The same uniform-random query mix is also maximally adversarial to the paper’s own quality mechanisms, since it neutralizes topical routing and TMT_M alike; nothing about retrieval quality should be inferred from this setup, in either direction. Validation on a natural-vocabulary corpus is open. We compare against two flat (non-hierarchical) baselines built over the same one billion documents: a single-threaded flat index, and a multi-threaded flat index (Flat-MT) that parallelizes the same disk-bound scan across cores. Both implement exhaustive ranked-OR (Section 2): every document matching at least one query term is scored, so their per-query cost tracks the posting-list union sizes tabulated in Section 4.1. We do not compare against BlockMax-WAND empirically in this evaluation. Section 4’s comparison is analytical, and closing that gap is the most direct next step for this work. Figure 3: Measured single-query latency (log scale) over 1B documents in 1K clusters, with ∼4% 4\% of the corpus visited per hierarchical query; 8/16/32-term queries. Hierarchical BM25 stays near 300 ms while the flat and flat multi-threaded indexes run 4–30× slower and breach the 1 s budget as query length grows. Figure 4: Single-query throughput over 1B documents, by query length. This chart is derived, not separately measured: QPS =1000/ms=1000/ms applied to the latencies of Figure 3. Hierarchical BM25 holds 2.6–3.5 QPS while both flat baselines fall as queries lengthen: the gap vs. Flat-MT widens from 4.7× (8 terms) to 5.6× (32 terms), and vs. flat single-threaded from 15× to over 30×. 5.2 Single-query latency and throughput Over one billion documents, Hierarchical BM25 answers 16-term queries in ∼300 300 ms. It stays inside the one-second budget across 8-, 16-, and 32-term queries (Figure 3). Against the flat multi-threaded baseline on the same hardware, it delivers 4.7–5.6× lower latency across the query-length range, with a resident footprint of ∼4.4 4.4 GB versus ∼400 400 GB (Table 3). The gain is structural: the resident Level-1 filter removes most of the corpus before any disk-backed scoring, so the number of random NVMe reads per query drops sharply. The drop holds as query length—and therefore naive fan-out—grows from 8 to 32 terms, where the flat baselines degrade the most. Latency and throughput are two views of the same single-query measurement. At one query in flight, throughput is simply the reciprocal of latency (QPS=1000/msQPS=1000/ms). We plot both because each makes a different comparison easy. The latency plot (Figure 3) makes the absolute one-second budget easy to check. The throughput plot (Figure 4) makes the relative gap between configurations readable directly as a multiplier. Read this way, Hierarchical BM25 sustains 2.6–3.5 QPS single-threaded across 8–32 terms. That is 4.7–5.6× the flat multi-threaded baseline (0.47–0.74 QPS) and 15–31× the flat single-threaded baseline (0.08–0.23 QPS). The gap widens as query length grows. Hierarchical BM25’s latency is nearly flat: 287–387 ms, a 1.35×1.35× increase from 8 to 32 terms. The flat baseline degrades far faster—2.74×2.74× over the same range—as postings fan-out increases. Flat-MT falls in between (1.58×1.58×): threading parallelizes the scan but does not reduce how much of the corpus each query still has to touch. This single-query throughput advantage is the baseline the parallel-query results in Section 5.3 build on. It already holds with no concurrency and no cache warming, before either of those further amplifies it. Note also that the widening gap with query length matches Section 4’s argument: Hierarchical BM25’s cost is governed by a fixed cluster budget, not by how much the candidate pool grows as q increases. Figure 5: Measured average response time under concurrent 16-term queries over 1B documents in 1K clusters (∼4% 4\% visited per hierarchical query). The flat baselines’ latency grows with concurrency, because every query pays the full disk-bound fan-out and parallel queries contend for the same NVMe bandwidth; Hierarchical BM25 stays near its single-query latency until cores saturate. Figure 6: Measured throughput under concurrent 16-term queries over 1B documents in 1K clusters (∼4% 4\% visited per hierarchical query). The flat baselines stay I/O-bound under 3 QPS regardless of concurrency; Hierarchical BM25 scales with the number of parallel queries once Level-1 has pruned the disk-bound work, and a warmed Level-2 cache removes most of the remaining I/O cost. 5.3 Throughput under concurrent queries Single-query latency bounds the tail, but a lexical index also has to sustain concurrent traffic. We hold the query mix fixed (16-term queries, as above) and issue 2, 4, 8, 16, and 32 queries in parallel against the same billion-document corpus and hardware. We compare four configurations: flat (LanceDB), flat multi-threaded, Hierarchical BM25, and Hierarchical BM25 with a warmed Level-2 cache (Hierarchical-Cached). The warmed configuration is the steady state once the fixed-size cache (Section 3) has been populated by prior traffic, rather than measured cold. Latency and throughput diverge sharply across the four configurations (Figures 5 and 6). On the latency side (Figure 5), the flat baselines’ average response time climbs with concurrency—parallel queries contend for the same NVMe bandwidth while each still pays its full fan-out—whereas Hierarchical BM25 holds near its single-query latency. On the throughput side (Figure 6), the flat baselines stay under 3 QPS even at 32 concurrent queries. Every query still pays the same disk-bound fan-out regardless of how many other queries run alongside it, and parallelism helps latency hiding only marginally when every query is I/O-bound on the same ∼400 400 GB structure. Hierarchical BM25 (cold Level-2) reaches ∼10.9 10.9 QPS at 32 parallel queries—roughly 4–6× the flat multi-threaded baseline across the range, widening toward 6×6× as concurrency increases. This is consistent with the Level-1 filter cutting the amount of disk-bound work per query, regardless of concurrency. Hierarchical BM25 with a warmed cache reaches ∼ 25–32 QPS from as few as 2 parallel queries and plateaus there. Once the frequently accessed Level-2 postings are cache-resident, throughput is limited by CPU scoring rather than NVMe I/O, so additional concurrency mostly fills otherwise-idle cores rather than contending for disk bandwidth. 5.4 Selection quality against the exhaustive index Figure 7: Measured aggregate score of the hierarchical top-k relative to the flat exhaustive index (1.0 = identical result strength), over 500K documents in 500 balanced clusters, sweeping the fraction of clusters visited and the result depth. Quality rises steeply with the visited fraction, and shallow result lists are preserved best. Figure 8: Measured recall at depths 20 and 100 for hierarchical selection versus the flat exhaustive index over the same 500K-document configuration. Hierarchical recall climbs steeply as the visited fraction grows and approaches the flat index’s own recall by 10%. The price side of the trade is measured at a smaller configuration: 500K documents in 500 balanced clusters, evaluated against the flat exhaustive index over the same corpus, sweeping the fraction of clusters visited per query from 1% to 10% and the result depth from top-10 to top-80. Two metrics capture two different failure modes. The first (Figure 7) is the aggregate score ratio: the summed BM25 score of the hierarchical top-k divided by the flat index’s, so 1.0 means the selected clusters contained results exactly as strong as exhaustive search found. The second (Figure 8) is recall of the flat index’s own result lists at depths 20 and 100. Both move the same way. Visiting 1% of clusters already recovers 0.76–0.83 of the exhaustive score, depending on depth; 5% recovers 0.83–0.91; 10% recovers 0.85–0.92. Shallow lists are preserved best (top-10 reaches 0.92 of the flat score at 10% visited, top-80 reaches 0.85), and that is the shape the design predicts: the strongest documents concentrate in the strongest clusters, while a deeper list depends increasingly on middling documents scattered through clusters the selection skipped. Recall behaves the same: hierarchical recall at both depths climbs steeply from 1% to 5% visited and approaches the flat index’s own recall by 10%. The billion-document configuration of Sections 5.2 and 5.3 visits ∼4% 4\% of clusters, which sits on the steep, favorable part of these curves. Three caveats bound this measurement. It is taken at 500K documents and 500 clusters, not at 10910^9 and ∼1 1K: the trends match the design’s argument, but billion-scale recall is extrapolated from them, not measured. Selection in this study is driven by the aggregate signal, because the query mix contains too few TMT_M terms for the co-occurrence signal to fire (Section 4.3); so these curves measure the aggregate half of selection; isolating B’s contribution remains open. And the corpus shares the compact vocabulary of Section 5.1, so quality on a natural-vocabulary corpus remains open as well. 6 Discussion and Limitations The most important limitation is that the price of the trade is only partly measured. Section 1.1 argued that giving up rank safety is worth structural bounds on memory and latency, on the grounds that a swap deep in the top-k rarely changes a hybrid pipeline’s output while a multi-second lexical query breaks it. That argument holds only if the approximation misses little. Section 5.4 measures this directly at a 500K-document configuration: visiting 5–10% of clusters recovers 0.83–0.92 of the exhaustive index’s result score, and recall approaches the flat index’s own by 10%. This is consistent with the argument and covers the operating region the billion-document benchmark uses. What remains unmeasured is the same price at 10910^9 documents, on a natural-vocabulary corpus, and with the co-occurrence signal’s contribution isolated; nDCG against relevance judgments is unmeasured everywhere. Until those measurements exist, the billion-scale latency and throughput results describe the cost side of a trade whose price is known only at smaller scale. Closing that gap remains the most important open step, ahead of even the BMW comparison in Section 4. A second limitation concerns how the guarantee scales. It is structural for a fixed cluster count, but not for a growing corpus held at that fixed count. Holding ∼1 1K clusters fixed while the corpus grows increases the amount of data each visited cluster holds, and therefore the per-query work at a fixed top-kcluk_clu. Holding per-query work fixed by growing the cluster count instead grows Level-1’s resident size—but that growth can be paid incrementally rather than through a global rebuild, by splitting only oversized clusters as they appear (Section 3.3). The ∼4.4 4.4 GB figure and the sub-second guarantee both describe the one-billion-document operating point measured in Section 5, not an asymptotic property independent of scale. Related to this, adversarial or skewed query distributions degrade the guarantee, in a way that connects back to Section 4’s analysis. The cost bound depends on the Level-1 grouping being selective and the Level-2 cache achieving a high hit rate under the live query distribution. A workload that defeats grouping—for instance, one dominated by very common terms spread uniformly across clusters—pushes more work onto the disk-backed path. This failure mode is structural, not incidental: the terms such a workload leans on are exactly the high-df head that Section 3.3 excludes from the clustering features because they carry no topical signal, so no topical partition can concentrate them. By the same mechanism discussed in Section 4, such a workload would likely degrade WAND-family pruning at the same time, for a related reason. A further build-time consequence of Section 3.3: as a live corpus grows and its topic mix drifts, the balance enforced at build time erodes, so the partition needs maintenance flat indexes do not—incremental rebalancing by splitting oversized clusters (Section 3.3), which is local and keeps Level-2 scoring exactly correct, punctuated by occasional full reclustering to restore the global optimality that repeated splitting cannot. Finally, this paper’s scope is deliberately limited to the scaling problem alone. A separate line of work addresses lexical retrieval’s blindness to the semantic vocabulary gap via query expansion. That method only rewrites the query text, and this paper’s index answers ordinary BM25 queries regardless of how they were produced. The two therefore compose without architectural changes to either—though we have not measured the composition end-to-end. 7 Conclusion At a billion documents, a flat BM25 index costs either ∼400 400 GB of resident memory or disk-bound multi-second latency. Hierarchical BM25 trades rank safety for structural bounds on both. It bounds resident memory to ∼4.4 4.4 GB with a resident coarse index plus a fixed-size fine cache. It holds single-query latency near 300 ms—4.7–5.6× faster than a flat multi-threaded index—and sustains up to ∼32 32 QPS under concurrent load with a warmed cache, versus under 3 QPS for flat indexing. The sacrifice is confined to cluster selection. Every scored document receives its exact, corpus-wide BM25 score. We identify and correct a cross-cluster scoring bug that silently biased rankings by cluster membership, fixed at a cost of ∼100 100 KB of global statistics. We also argue, analytically, that Hierarchical BM25’s cluster selection should outperform WAND-style dynamic pruning specifically at the long query lengths common in retrieval-augmented pipelines. It needs only single-term topical concentration, rather than the document-level multi-term co-occurrence WAND’s pruning depends on. The aggregate signal alone dilutes as query length grows and cannot tell whether several terms’ evidence came from one document or many; the design’s second signal covers exactly that gap, tracking co-occurrence for the discriminative terms too spread out across clusters to self-select, at a cost governed by how many such terms a query contains rather than by query length. All of this comes with the caveats stated throughout. Hierarchical BM25 is not rank-safe where BMW is. Selection quality is priced at a 500K-document configuration—0.83–0.92 of the exhaustive result score at 5–10% of clusters visited—but not yet at billion scale, not on a natural vocabulary, and not with the co-occurrence signal’s contribution isolated. Document-reordered BMW is the fair baseline still to be tested. Those measurements, and that comparison, are the open steps that would turn this architectural case into a settled one. Acknowledgments We thank Cornel Constantinescu for his help in the investigation. References [1] H. P. Luhn. The Automatic Creation of Literature Abstracts. IBM Journal of Research and Development, 2(2):159–165, 1958. [2] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Dirichlet Allocation. Journal of Machine Learning Research, 3:993–1022, 2003. [3] S. Robertson and H. Zaragoza. The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in IR, 3(4):333–389, 2009. [4] S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. In TREC-3, NIST SP 500-225, 109–126, 1994. [5] N. Thakur, N. Reimers, A. Rücklé, A. Srivastava, and I. Gurevych. BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In NeurIPS Datasets and Benchmarks, 2021. [6] Y. A. Malkov and D. A. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI, 42(4):824–836, 2018. [7] H. Jégou, M. Douze, and C. Schmid. Product Quantization for Nearest Neighbor Search. IEEE TPAMI, 33(1):117–128, 2011. [8] V. Karpukhin, B. Oğuz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W. Yih. Dense Passage Retrieval for Open-Domain Question Answering. In EMNLP, 6769–6781, 2020. [9] A. Z. Broder, D. Carmel, M. Herscovici, A. Soffer, and J. Zien. Efficient Query Evaluation Using a Two-Level Retrieval Process. In CIKM, 426–434, 2003. [10] S. Ding and T. Suel. Faster Top-k Document Retrieval Using Block-Max Indexes. In SIGIR, 993–1002, 2011. [11] H. Turtle and J. Flood. Query Evaluation: Strategies and Optimizations. Information Processing & Management, 31(6):831–850, 1995. [12] L. Dhulipala, I. Kabiljo, B. Karrer, G. Ottaviano, S. Pupyrev, and A. Shalita. Compressing Graphs and Indexes with Recursive Graph Bisection. In SIGKDD, 1535–1544, 2016. [13] A. Kulkarni and J. Callan. Selective Search: Efficient and Effective Search of Large Textual Collections. ACM Transactions on Information Systems, 33(4):17:1–17:33, 2015. [14] J. P. Callan, Z. Lu, and W. B. Croft. Searching Distributed Collections with Inference Networks. In SIGIR, 21–28, 1995. [15] L. Si and J. Callan. Relevant Document Distribution Estimation Method for Resource Selection. In SIGIR, 298–305, 2003. [16] R. Aly, D. Hiemstra, and T. Demeester. Taily: Shard Selection Using the Tail of Score Distributions. In SIGIR, 673–676, 2013. [17] Y. Qiao, P. Carlson, S. He, Y. Yang, and T. Yang. Threshold-driven Pruning with Segmented Maximum Term Weights for Approximate Cluster-based Sparse Retrieval. In EMNLP, 19742–19757, 2024. [18] A. Mallia, T. Suel, and N. Tonellotto. Faster Learned Sparse Retrieval with Block-Max Pruning. In SIGIR, 2411–2415, 2024.

Instant research discovery