Hierarchical BM25: Lexical Search at Billion-Document Scale
Umesh Deshpande, Swaminathan Sundararaman
cs.IR, cs.AI
2026-08-01
Hierarchical BM25用两级索引把十亿文档BM25检索的常驻内存从约400GB压到4.4GB,16词查询延迟约300毫秒,比扁平索引快4.7~5.6倍,代价是放弃精确排名。
BM25 是词法检索的基础算法,但一旦语料到了十亿文档规模,一份扁平的倒排索引要占约 400GB,常驻内存的开销和语料大小成正比;放到磁盘上服务,单次查询延迟要 412 秒。这个延迟量级放进任何要求交互式响应的检索流水线(哪怕只是混合检索里给稠密向量搭配的词法候选)都是不可接受的。密集检索这边早就有 HNSW、IVF 这类近似最近邻索引把百亿向量的搜索压到毫秒级,词法检索这边却还停留在「精确排名要么占满内存、要么等到天荒地老」的两难。
Hierarchical BM25 放弃精确排名(rank safety,即保证真正的 top-10 一定原样返回),换取内存和延迟的固定上限。索引分两级:第一级是常驻内存的粗筛索引,把十亿文档预先聚成约 1000 个大小均衡的「话题簇」(用 LDA 主题模型分配,超出目标大小的簇再局部拆分,不用重新聚类全量语料),每个簇只保留一张按词项聚合的统计表,整个第一级只占约 4.4GB。第二级是全量文档的精细索引,常驻内存的只有一个约 1M 条目的缓存,其余全放 NVMe,按需换入。查询到来时,系统先用两个信号在第一级里选出约 40 个最可能相关的簇:一是每个词项在簇里的总频率(粗粒度的话题浓度信号),二是针对那些「有区分度但分散在很多簇里」的词,单靠总频率信号看不出这类词是不是真的在同一份文档里凑齐了,所以论文额外建了一个小索引专门追踪这类词的同文档共现。选中的约 40 个簇会被完整搜索,用和扁平索引完全相同的方式打分,唯一被牺牲的近似性只发生在「选哪些簇」这一步,选中之后每份文档拿到的分数是精确的、和整份语料算出来的分数完全一致。论文还专门修了一个之前会被忽视的正确性 bug:如果每个簇用自己局部的逆文档频率(IDF)统计打分,同样的词频在不同簇里能差出 1.6 倍分数,论文的做法是全局共享一张约 100KB 的文档频率表,让每个簇的打分口径和全量索引完全一致。
在十亿文档、约 1000 个簇的配置下,16 词查询的响应时间稳定在约 300 毫秒以内,比多线程的扁平索引快 4.75.6 倍,常驻内存只要 4.4GB(对比扁平索引约 400GB)。并发场景下差距更大:32 路并发查询时,扁平索引的吞吐量始终卡在 3 QPS 以下(因为每个查询都要付出完整的磁盘扫描),而预热过缓存的 Hierarchical BM25 能吃到约 2532 QPS。检索质量的代价在一个 50 万文档、500 簇的小规模配置上测量:只访问 5%10% 的簇,就能拿到穷举搜索 83%92% 的总分,浅层结果(top-10)保留得比深层结果(top-80)更完整。论文也分析了这套方法和另一条主流的近似加速路线(BlockMax-WAND 动态剪枝)在长查询下的根本差异:WAND 的剪枝力度依赖单份文档里多个查询词同时命中的概率,查询词越多、词越不相关,这个概率越低,剪枝效果越差(候选池从 8 词查询的 3900 万份文档涨到 32 词查询的 1.48 亿份);簇选择用的是聚合的话题浓度信号,不随查询词数线性增长,理论上更适合检索增强生成里常见的 1632 词长查询。
对已经在做混合检索(词法+向量)的系统,词法这一侧长期是被将就的短板:要么占满整机内存,要么慢到没法放进交互式延迟预算。这篇论文提供的是一个具体可行的架构:把内存开销从「随语料线性增长」变成「固定 4.4GB」,这个数字级别的下降意味着词法检索终于能和向量索引部署在同一台机器上,而不用单独拉一台大内存服务器。论文强调这是一个用近似排名换资源上限的架构性权衡,不是免费的性能提升。
论文自己说得很清楚:检索质量的测量只做到 50 万文档、500 簇的规模,十亿文档、1000 簇配置下的真实召回率并没有实测,只是从小规模结果外推。论文用的评测查询是从 2 万词的语料词表里随机抽词拼出来的,这种查询没有真实查询该有的长尾分布,对聚类和共现信号的压力是偏弱的,论文明确说这个设置对自己的质量机制是「最不利的验证方式之一」。和 BlockMax-WAND 的对比目前只是理论分析,没有做过实际的头对头基准测试,论文把这个列为最需要补的下一步。另外,词表膨胀到自然语言级别(而不是论文里这种只有约 2 万词的紧凑词表)、聚类是否还能保持均衡,论文也留作未验证的开放问题。