  Learned sparse retrieval systems aim to combine the effectiveness of
contextualized language models with the scalability of conventional data
structures such as inverted indexes. Nevertheless, the indexes generated by
these systems exhibit significant deviations from the ones that use traditional
retrieval models, leading to a discrepancy in the performance of existing query
optimizations that were specifically developed for traditional structures.
These disparities arise from structural variations in query and document
statistics, including sub-word tokenization, leading to longer queries, smaller
vocabularies, and different score distributions within posting lists. This
paper introduces Block-Max Pruning (BMP), an innovative dynamic pruning
strategy tailored for indexes arising in learned sparse retrieval environments.
BMP employs a block filtering mechanism to divide the document space into
small, consecutive document ranges, which are then aggregated and sorted on the
fly, and fully processed only as necessary, guided by a defined safe early
termination criterion or based on approximate retrieval requirements. Through
rigorous experimentation, we show that BMP substantially outperforms existing
dynamic pruning strategies, offering unparalleled efficiency in safe retrieval
contexts and improved tradeoffs between precision and efficiency in approximate
retrieval tasks.
