Accelerating Learned Sparse Indexes Via Term Impact Decomposition (2022)

Abstract: Novel inverted index-based learned sparse ranking models provide more effective, but less efficient, retrieval performance compared to traditional ranking models like BM25. In this paper, we introduce a technique we call postings clipping to improve the query efficiency of learned representations. Our technique amplifies the benefit of dynamic pruning query processing techniques by accounting for changes in term importance distributions of learned ranking models. The new clipping mechanism accelerates top-k retrieval by up to 9.6X without any loss in effectiveness.

## introduction sparse term importance representations such as deepimpact @xcite and unicoil @xcite have enabled the use of effective transformer-based text representations that can match the effectiveness of recent dense text representations @xcite while still being supported by inverted indexes and their query operations. this is of importance as inverted indexes have been optimized to provide search functionality in distributed settings at web-scale through 40 years of research, providing a variety of time, space and retrieval quality tradeoffs; while also supporting efficient updates, advanced querying modes such as phrase matching or filtering, and good scalability, all of which are crucial in real-world settings @xcite . one of the key techniques that enables efficient top-k query processing in inverted indexes is storing additional metadata about index term importance scores (also referred to as impacts), seeking to facilitate the bypassing of the majority of the matching documents, and thus allowing faster retrieval than would be possible via exhaustive disjunctive processing. for example, dynamic pruning algorithms such as maxscore (turtle and 2 b+1 ). classical schemes such as bm25 and doct5query exhibit small maximum impacts for long lists, whereas deepimpact and unicoil assign high importance to terms regardless of their document frequency. note the irregular scale on the horizontal axis. flood, 1995) and wand @xcite store the index-wide maximum impact of each term; at query-time, these impacts can be used to rapidly estimate document scores, allowing documents that have no prospect of entering the current min-heap of k results to be bypassed. traditional similarity models such as bm25 guarantee that frequent terms have low importance scores, a symbiotic relationship that allows fast query processing. on the other hand, recent transformer-based learned term importance techniques such as deepimpact are not constrained by term occurrence frequency when assigning importance scores to terms in documents. for example, consider the term "does" in an english corpus. traditional models such as bm25 would assign a low impact for this term in all documents, since it occurs so frequently; a direct effect of inverse document frequency (idf). on the other hand, learned impact msmarco-v1 passage 0.91 does are the females in the deer family of mammals, individually called a doe (pronounced doe as in toe). the plural of doe can also be doe. does is also the word meaning the present tense of the verb do. pronounced duz as opposed to the pronunciation for the female deer. contribution we adapt the maxscore and wand dynamic pruning mechanisms to enable efficient query processing for learned term importance schemes such as deepimpact via a simple technique we call term impact decomposition. we describe partitioning schemes that separate the postings for each term into two groups -those that are highimpact, and are likely to result in documents being scored; and those that are low-impact, and more likely to be associated with bypassed documents; and present a new form of impact decomposition that we call postings clipping. when integrated into the retrieval engine, impact decomposition allows almost 10× faster top-k term-based querying, with negligible increases to index storage costs, and no effect on result quality. ## background term-based similarity many retrieval similarity formulations can be expressed as a sum over per-document query-term impacts, computed for document d and query q as ## impact decomposition this section introduces the notion of postings list splitting, and shows how it can be combined with both maxscore and with wand variants. we then introduce a new technique, postings clipping that replicates the high-impact postings, rather than separating them from the low-impact postings. it has the benefit of allowing more precise score estimations, and hence faster pruned querying. list splitting @xcite , and later @xcite and @xcite , note that each postings list i t can be split into two parts, denoted here as h(t) and l(t), with h(t) containing the postings with the highest impacts for t, and l(t) containing all the remaining ones. since h(t) and l(t) are disjoint, query processing algorithms can treat them as independent terms. the top part of figure 3 illustrates list splitting. the complete set of postings for some term t (left) is reduced from (in the example) 21 postings to 17 posting to form l(t), with the other 4 postings assigned to h(t). each of l(t) and h(t) then high list low list single list (b) postings clipping | | = 21 ut t | | = 21 | | = 17 | | = 4 ut figure 3: two types of impact decomposition. list splitting involves moving high-impact postings into a separate postings list, h(t); whereas postings clipping involves trimming the impact scores in the low-impact list, and creating new postings in a separate list h(t) to account for the remainder. a number of splitting rules can be considered. for example, a fixed fraction of the original list might be taken; or the split could be based on local or global threshold scores. in this work, we take a fixed fraction, set at 1/64 (based on preliminary experimentation) and respecting quantized impact levels, so that |h(t)| is maximized subject to |h(t)| ≤ |i t |/64, and also subject to the smallest impact in h(t) being greater than u l(t) . we also only apply splitting to lists with more than 256 postings, as short lists are always handled quickly. where the impact score distribution of the postings is skewed and has a long tail, splitting results in reduced variance inside each part. the maximum term importance u t stored for any list i t is intended to approximate the distribution of the impacts of the postings in that list; and hence storing two upper bounds, one for h(t) and one for l(t), allows a better approximation to the underling distribution. note also that list splitting is performed at indexing time and results in only a modest increase in index size. at query time, each term is mapped to (one or) two postings lists, with at most twice as many cursors to maintain, but the same total number of postings to be processed. maxscore, wand, and bmw our first observation is simply that maxscore should be implemented so that the static ordering over terms assumed at step 25 of algorithm 1 is by decreasing list length, rather than by the more usual increas-ing u t , respecting the separation of these concepts that was noted above (that is, idf is not obeyed by learned sparse models). the maxscore pseudo-code presented earlier already shows this adaptation. there are then a number of ways of proceeding when list splitting is considered. the simplest option is to ignore any knowledge of the list pairings, and allow a q-term query to be processed in the standard document-at-a-time manner over as many as 2q postings lists @xcite . in terms of maxscore, any combination of low-and high-impact lists might be in passive, with the remainder in active. however the use of the u t limits to decide if a document that is in an active list should be scored remains valid -no document that might generate a similarity score greater than θ and thus should get scored will get bypassed. on the other hand, when the l(t) list for one of the terms is in passive (and because it is longer, it will enter earlier), only the postings in h(t) can now trigger a document scoring caused by term t, and hence there is a very real capacity for additional documents to be bypassed. similar considerations arise with wand and bmw: in all three processing modes the mere act of splitting the lists introduces the possibility of accelerated query processing, without risking any loss in terms of answer set correctness. as an orthogonal enhancement, priming can be applied whenever any high-impact list contains k or more postings, |h(t)| ≥ k. if that holds, then next, if additional bookkeeping operations can be tolerated, it is also possible to compute what we denote as smart bounds. when the low-impact list for some term t first joins passive, the variable sum_pass is correctly increased by u l(t) . but if and when the partner term h(t) also joins passive, increasing sum_pass by u h(t) is needlessly pessimistic, since no document can appear in both l(t) and h(t). hence, the correct second increment associated with term t is by u h(t) -u l(t) . in the case of maxscore, the corresponding smart bounds are easily computed, and are required only occasionally -when a postings list is moved from active to passive. however, for wand and bmw the estimations must be modified much more frequently, and while smart bounds can certainly be computed, their benefit is less clear. one key part of the experimentation in section 4 is to quantify the relationship between document scoring and bounds manipulation. @xcite and @xcite also noted the idea of smart bounds estimation in their descriptions of list splitting, but they did not consider maxscore-based processing. postings clipping our additional proposal -denoted postings clipping -is illustrated in the bottom half of figure 3 . rather than partitioning the set of postings in i t across l(t) and h(t), every posting remains in l(t), and we "clip" the highimpact postings by slicing them into two parts, and forming a posting pair. the base part remains in l(t) as a posting with an impact equal to u l(t) , the maximum score contribution permitted in l(t); and the second component of the pair becomes a new posting in h(t), to account for the "trimmed" part of the original impact value, and retain the same total. this arrangement has the singular advantage of no longer requiring any smart bounds management, or equivalent run-time manipulation of score estimates. smart bounds are needed in the list splitting approach of @xcite to adjust for the constraint that no document can appear in both l(t) and h(t), and hence that u l(t) + u h(t) is an over-estimate (by an addend of u l(t) ) of t's true upper bound u t . but with postings clipping, u h(t) is instead set to the maximum residual amount across all of t's postings, and hence we have u @xmath0. in turn, that means that when queries are being processed the lists l(t) and h(t) can be treated as if they were derived from completely independent terms, with all interactions between them handled by the underlying processing logic, be that maxscore, wand, or bmw. that is, while there are more total postings to be stored and processed, the change from list splitting with smart bounds to postings clipping substantially simplifies the query-time processing logic. indeed, with the exception of priming -which can still be applied on the basis that is noted in eqn. 2 -a maxscore-based postings clipping implementation remains exactly as is shown by the logic provided in algorithm 1. the result is that -as we demonstrate in section 4 -quite dramatic reductions in query processing times for the learned sparse retrieval models can be achieved. figure 4 crystallizes the difference between list splitting and postings clipping. in the left pane (list splitting) the u h(t) values rise as u l(t) increases, list splitting postings clipping 0.25 0.50 0.75 1.00 0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 normalized max impact [low] normalized max impact [high] plotted over the set of msmarco-v1 query terms; whereas in the right pane (postings clipping) u h(t) becomes increasingly constrained as u l(t) grows. the difference affects the pruning bounds estimation, and while it can be partially ameliorated by smart bounds adjustments, the postings clipping mechanism is more precise. ## experiments we now describe experiments that quantify the benefits arising from the postings clipping approach. our experiments make use of both msmarco-v1 (8.8 million passages) and msmarco-v2 (138.4 million passages) collections, four representative ranking algorithms, and the pisa query processing system which was recently shown to outperform the commonly used anserini system for document-at-a-time retrieval over learned sparse indexes @xcite . full details of the experimental setup are provided in appendix a. index size ## conclusion and future work to keep up with increasingly large volumes of data, search practitioners require sophisticated structures and processing algorithms, so that response times can remain plausible. in this paper, we have demonstrated the speed benefits that arise through the use of a new technique we call postings clipping. we have established new benchmarks for querying speed, with minimal costs overheads, for both shallow @xmath1. our techniques can also be embedded as part of a multiphase processing stack, and are applicable to both normal term-based search and also to retrieval via enhanced learned sparse approaches.