Threshold-driven Pruning with Segmented Maximum Term Weights for Approximate Cluster-based Sparse Retrieval (2024)

Abstract: This paper revisits dynamic pruning through rank score thresholding in cluster-based sparse retrieval to skip the index partially at cluster and document levels during inference. It proposes a two-parameter pruning control scheme called ASC with a probabilistic guarantee on rank-safeness competitiveness. ASC uses cluster-level maximum weight segmentation to improve accuracy of rank score bound estimation and threshold-driven pruning, and is targeted for speeding up retrieval applications requiring high relevance competitiveness. The experiments with MS MARCO and BEIR show that ASC improves the accuracy and safeness of pruning for better relevance while delivering a low latency on a single-threaded CPU.

## introduction fast and effective document retrieval is a critical component of large-scale search systems. this can also be important for retrieval-augmented generation systems which are gaining in popularity. retrieval systems fall into two broad categories: dense (single or multi-vector) @xcite @xcite @xcite and sparse (lexical or learned) @xcite @xcite @xcite . efficient dense retrieval relies on approximation techniques with notable relevance drops @xcite @xcite , whereas sparse retrieval takes advantage of fast inverted index implementations on cpus. well-trained models from these two categories can achieve similar relevance numbers on the standard ms marco passage ranking task. however, for zero-shot out-of-domain search on the beir datasets, learned sparse retrieval exhibits stronger relevance than bert-based dense models. accordingly, this paper focuses on optimizing online inference efficiency for sparse retrieval. another reason for this focus is that sparse retrieval does not require expensive gpus, and thus can significantly lower the infrastructure cost for a largescale retrieval system that hosts data partitions on a massive number of inexpensive cpu servers. a traditional optimization for sparse retrieval is rank-safe threshold-driven pruning algorithms, such as maxscore @xcite , wand @xcite , and blockmax wand (bmw) @xcite , which accurately skip the evaluation of low-scoring documents that are unable to appear in the final top-k results. two key extensions of these pruning methods are cluster-based pruning and rank-unsafe threshold over-estimation. cluster-based (or block-based) pruning extends rank-safe methods to skip the evaluation of groups of documents @xcite @xcite . however, the cluster bounds estimated by current methods are often loose, which limits pruning opportunities. threshold over-estimation @xcite @xcite relaxes the safeness, and allows some potentially relevant documents to be skipped, trading relevance for faster retrieval. however, there are no formal analysis or guarantee on the impact of rank-unsafeness on relevance and its speed gain can often come with a substantial relevance drop. this paper revisits rank score threshold-driven pruning for cluster-based retrieval in both safe and unsafe settings. we introduce a two-parameter threshold control scheme called asc, which addresses the above two limitations of current threshold-driven pruning methods. asc uses cluster-level maximum weight segmentation to improve the accuracy of cluster bound estimation and offer a probabilistic guarantee on rank-safeness when used with threshold over-estimation. consequently, asc is targeted at speeding up retrieval in applications that desire high relevance. our evaluation shows that asc makes sparse retrieval with splade @xcite , uni-coil @xcite , and lexmae @xcite much faster while effectively retaining their relevance. asc takes only 9.7ms with @xmath0.4252 mrr. it takes only 5.59ms and 15.8ms respectively for splade with over 0.3962 mrr. when prioritizing for a small mrr relevance loss, asc can be an order of magnitude faster than other approximation baselines. threshold-driven skipping. during sparse retrieval, a pruning strategy computes the upper bound rank score of a candidate document d, referred to as bound(d), satisfying rankscore(d) ≤ bound(d). if bound(d) ≤ θ, where θ is the rank score threshold to be in the topk list, this document can be safely skipped. wand uses the maximum term weight of documents in a posting list for their score upper bound, while bmw and its variants (e.g. vbmw @xcite ) use block-based maximum weights. maxscore uses a similar skipping strategy with term partitioning. a retrieval method is called rank-safe if it guarantees that the top-k documents returned are the k highest scoring documents. all of the above algorithms are rank-safe. threshold over-estimation is a "rank-unsafe" skipping strategy that deliberately over-estimates the current top-k threshold by a factor @xcite @xcite . there is no formal analysis of the above rank-safeness approximation, whereas our work generalizes and improves threshold over-estimation for better rank-safeness control in cluster-based retrieval with a formal guarantee. live block filtering and cluster-based retrieval. live block filtering @xcite clusters document ids within a range and estimates a rangebased maximum score for pruning. anytime ranking @xcite extends cluster skipping inverted index @xcite which arranges each posting list as "clusters" for selective retrieval, and searches top clusters under a time budget. without early termination, anytime ranking is rank-safe and conceptually the same as live block filtering with an optimization that cluster visitation is ordered dynamically. contemporary work in @xcite introduces several optimizations for live block filtering called bmp with block reordering and threshold overestimation and shows that a block-based (cluster-based, equivalently) retrieval still represents a state-of-the-art approach for safe pruning and for approximate search. our work can be effectively combined with the above work using maximum cluster-level score bounds and threshold over-estimation, and is focused on improving accuracy of cluster score bounds and threshold-driven pruning to increase index-skipping opportunities and introduce a probabilistic rank-safeness assurance. efficiency optimization for learned sparse retrieval. there are orthogonal techniques to speedup learned sparse retrieval. bm25-guided pruning skips documents during learned index traversal @xcite . static index pruning @xcite removes low-scoring term weights during index generation. an efficient version of splade @xcite uses l1 regularization for query vectors, dual document and query encoders, and language model middle training. term impact decomposition @xcite partitions each posting list into two groups with high and low impact weights. our work is complementary to the above techniques. approximation with score-at-a-time retrieval (saat). the above retrieval approaches often conduct document-at-a-time (daat) traversal over document-ordered indexes. the saat retrieval over impact-ordered indexes is an alternative method used together with earlier termination such as jass @xcite and ioqp @xcite ). an experimental study @xcite ) compares daat and saat for a number of sparse models and indicates that while no single system dominates all scenarios, it confirms that daat anytime code is a strong contender, especially for splade when maintaining the small mrr@10 loss. since ioqp has been shown to be highly competitive to an optimized version of jass, the baselines in section 4 includes anytime and ioqp. big-ann competition for sparse retrieval. neurips 2023 big-ann competition sparse track (big-ann, 2024) uses 90% recall of safe search top 10 results as the relevance budget to select the fastest entry for ms marco dev set with splade, and this metric drives a different optimization tradeoff compared to our paper. our paper prioritizes mrr@10 competitiveness of approximate retrieval with a much tighter relevance loss budget before considering gains in latency reduction. appendix d provides a comparison of asc with two top winners of this competition. reference @xcite is listed for the pinecone entry with no open source code released, and it presents an approach to combine dense and sparse retrieval representations with random projection, which is orthogonal to our approach. ## cluster-based retrieval with approximation and segmentation the overall online inference flow of the proposed scheme during retrieval is shown in figure 1 . initially, sparse clusters are sorted in a non-increasing order of their estimated cluster upper bounds. then, search traverses the sorted clusters one-by-one to conduct approximate retrieval with two-level pruning with segmented term maximum weight. we follow the notation in @xcite : asc predicts more accurate cluster bounds, which allows it to prune more aggressively. cluster bound tightness is the average ratio of the actual and estimated cluster bounds, calculated with formula (1). given query q, the boundsum formula below estimates the maximum rank score of a document in a cluster. anytime ranking visits clusters in a non-increasing order of boundsum values. the visitation to cluster c i can be pruned if boundsum(c i ) ≤ θ, where θ is the current topk threshold. if this cluster is not pruned, then document-level index traversal and skipping can be conducted within each cluster following a standard retrieval algorithm. any document within such a cluster may be skipped for evaluation if bound(d) ≤ θ where bound(d) is computed on the fly based on an underlying retrieval algorithm such as maxscore and vbmw. ## evaluation datasets and metrics. we use the ms marco passage ranking dataset @xcite with 8.8 million english passages. we report mean reciprocal rank (mrr@10) for the dev set which contains 6980 queries, and ndcg@10 for the trec deep learning (dl) 2019 and 2020 sets. we also report recall, which is the percentage of relevant-labeled results that appear in the final topk results. retrieval depth k tested is 10 or 1000. we also evaluate on beir @xcite , a collection of 13 publicly available english datasets totaling 24.6 million documents. the size of each dataset ranges from 3,633 to 5.4m documents. experimental setup. documents are clustered using k-means on dense vectors. details, including a comparison between a few alternatives such as sparse vectors, are in appendix b. sparse models tested include a version of splade @xcite , uni-coil @xcite , and lexmae @xcite . we primarily use splade to assess asc because lexmae, following dense models such as simlm @xcite and retromae @xcite , uses ms marco title annotations. this is considered as non-standard @xcite . splade does not use title annotations. asc's implementation uses c++, extended from anytime ranking code's release based on the pisa retrieval package @xcite . the index is compressed with simd-bp128. maxscore is used to process queries because it is faster than vbmw for long queries @xcite generated by splade and lexmae. we applied an efficiency optimization to both the asc and anytime ranking code in extracting cluster-based term maximum weights when dealing with a large number of clusters. ioqp uses the authors' code release @xcite . a comparison to other recent methods in the neurips big-ann competition are presented in appendix d. all timing results are collected by running as a single thread on a linux server with intel i7-1260p and 64gb memory. before timing queries, all compressed posting lists and metadata for tested queries are pre-loaded into memory, following the common practice. our code will be released under the apache license 2.0 at https://github.com/qiaoyf96/asc . for all of our experiments on ms marco dev queries, we perform pairwise t-tests on the relevance between asc and corresponding baselines. " † " is tagged when significant drop is observed from maxscore retrieval at 95% confidence level. baseline comparison on ms marco. anytime ranking is configured to use 512 clusters with no early termination. asc is configured with 4096 clusters and 8 segments. appendix c explains the above cluster configuration for anytime and asc to deliver low latency under competitive relevance. rank-safe asc uses µ = η = 1 and rank-unsafe asc uses η = 1 with µ = 0.9 for @xmath2.5 for @xmath3. as shown in comparing the three rank-safe versions in for approximate retrieval when @xmath7, asc has 3.9% higher mrr@10, 11% higher recall, and is 2.7x faster than anytime with µ = 0.9. when @xmath8, asc is 2.3x faster than anytime under similar relevance. even with µ being as low as 0.5, asc offers competitive relevance. this demonstrates the importance of theorem 4. for this reason, asc is configured to be probabilistically safe with η = 1 while choosing µ value modestly below 1 for efficiency. for @xmath9, there is a very small mrr loss (≤ 0.1%) compared to the original retrieval, but asc performs competitively while it is up to 4.7x faster than the original maxscore without using clusters. approximate ioqp is configured to visit 10% of documents, which is a default choice in @xcite . asc outperforms ioqp-10% with 4.8% higher mrr@10 and 3.7% higher recall while asc is 4.3x faster. choice of η for asc. while η = 1 is recommended for probabilistic safeness, setting η < 1 is useful in some cases to obtain a shorter latency when relevance loss budget allows. for example, when mrr@10 loss is allowed to be 5% or 10%, asc uses η = 0.95 in ## compatibility with other speedup techniques we also apply asc with static index pruning @xcite for a version of splade used in big-ann competition as discussed in appendix d below. the exact search with safe anytime ranking delivers 0.383 mrr@10 with 20.2ms with @xmath11. asc takes 3.8ms with 0.5% mrr loss, and it only takes 0.81ms when following the big-ann relevance budget (90.5% recall to top-10 exact search results). term impact decomposition @xcite ) is an orthogonal optimization on posting lists. our preliminary test shows that it does not work well with splade as its posting clipping and list splitting increase original splade latency from 66ms to 95ms and 110ms, respectively. thus our evaluation didn't include this optimization. ## concluding remarks asc is an (µ, η)-approximate control scheme for dynamic threshold-driven pruning that aggressively skips clusters while being probabilistically safe. asc can speed up retrieval applications that still desire high relevance effectiveness. for example, when mrr loss is constrained to under 1-2%, the mean latency of asc is about 4x faster than anytime ranking and is 13x to 33x faster than ioqp for ms marco passage dev set with @xmath12. our evaluations with the ms marco and beir datasets show that µ = 0.5 for @xmath13, and µ = 0.9 for @xmath14. our findings recommend η = 1 for probabilistic safeness and varying µ from 1 to 0.5 for a tradeoff between efficiency and effectiveness. setting η < 1 is useful to obtain a shorter latency when relevance loss budget allows.