Novel inverted index-based learned sparse ranking models provide more efective, but less eficient, retrieval performance compared to traditional ranking models like BM25. In this paper, we introduce a technique we call postings clipping to improve the query eficiency 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- retrieval without any loss in efectiveness.
Sparse term importance representations such as DeepImpact [
One of the key indexing techniques that enables eficient top- query processing 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 allow faster
retrieval than would be possible via exhaustive disjunctive processing. For example, dynamic
pruning algorithms such as MaxScore [
BM25 0 2 4 6 8 10 14 16 18 20 21 22 23 24
List Bucket [b ]
DocT5Query DeepImpact uniCOIL
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 [
Indeed, learned representations assign high term importance to even very frequent terms, whereas BM25 always assigns low importance to such terms. This divergent behavior substantially reduces the ability of MaxScore and WAND to bypass low-impact documents during querying, with both techniques relying on maximum list-wise impact scores to prune the search space. Figure 1 highlights the pervasive nature of this issue.
We present a new form of impact decomposition that we call postings clipping and adapt dynamic pruning mechanisms to enable eficient query processing for learned term importance schemes. When integrated into the retrieval engine, postings clipping allows faster top- term-based querying, with negligible increases to index storage costs, and no efect on result quality.
Several authors have proposed explicitly or implicitly splitting postings lists into two (or
more) parts, a high-impact segment ℋ() and a low-impact segment ℒ() to facilitate eficient
processing; see, for example, Strohman and Croft [
Our proposal – denoted postings clipping – is illustrated in Figure 2. Rather than partitioning the set of postings in ℐ across ℒ() and ℋ(), every posting remains in ℒ(), and we “clip” the high-impact postings by slicing them into two parts, and forming a posting pair. The base part remains in ℒ() as a posting with an impact equal to ℒ(), the maximum score contribution permitted in ℒ(); and the second component of the pair becomes a new posting in ℋ(), to account for the “trimmed” part of the original impact value, and retain the same total.
This arrangement has the singular advantage of no additional upper bounds management t t (a) List Splitting
Ut
(t) (smart bounds) being needed, nor equivalent run-time manipulation of score estimates. Such adjustments in the list splitting approach of Kane and Tompa [15] to correct for the constraint that no document can appear in both ℒ() and ℋ(), and hence that ℒ() + ℋ() is an overestimate (by an addend of ℒ()) of ’s true upper bound . With postings clipping, ℋ() is instead set to the maximum residual amount across all of ’s postings, and hence we have = ℒ() + ℋ(). In turn, that means that when queries are being processed the lists ℒ() and ℋ() 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.
As an orthogonal enhancement, priming can be applied whenever any high-impact list contains or more postings, |ℋ()| ≥ . If that holds, then 0 = max{ℒ() | ∈ ∧ |ℋ()| ≥ } (1) can be used as an initial value for the heap bound, without risking top- integrity. In combination, the result is that – as we demonstrate in Section 3 – quite dramatic reductions in query processing times for learned sparse retrieval models can be achieved.
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 MSMARCOv2 (138.4 million passages) collections, four representative ranking algorithms, and the PISA [17] query processing system which was recently shown to outperform the commonly used Anserini system for document-at-a-time retrieval over learned sparse indexes [18].
Index Size Since clipping is applied only to postings with more than 256 elements, and even then only adds 1/64 as many new postings, the space overhead compared to the default index is negligible. For instance, the largest overhead of 600 MiB to the ≈ 33 GiB index for the uniCOIL model on MSMARCO-v2 represents an increase of only 1.8%.
Query Speed Table 1 presents query processing times recorded for the MSMARCO-v1 collection and DeepImpact retrieval, with response latency measured as average milliseconds per query, and with the three blocks of values corresponding to dynamic query pruning approaches.
The last row in each block shows the combination of postings clipping, with 1/64 postings taken into ℋ(), in conjunction with priming (and length-based ordering for MaxScore). The fastest query time in each of the six sections is highlighted in blue.
As can be seen, for DeepImpact retrieval, the fastest querying is achieved by MaxScore pruning with postings clipping. That combination takes less than half the time of standard MaxScore processing. The gains from posting clipping are less for WAND and VBMW, in part because both algorithms exhibit greater sensitivity to doubling the number of query terms.
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 novel technique we call postings clipping. We have established new benchmarks for querying speed, with minimal costs overheads, for both shallow = 10 and deep = 1000 retrieval. [14] C. M. Daoud, E. S. de Moura, D. Fernandes, A. S. da Silva, C. Rossi, A. Carvalho, Waves: A fast multi-tier top- query processing algorithm, Information Retrieval 20 (2017) 292–316. doi:10.1007/s10791-017-9298-6. [15] A. Kane, F. W. Tompa, Split-lists and initial thresholds for WAND-based search, in: Proc.
ACM Int. Conf. on Research and Development in Information Retrieval (SIGIR), 2018, pp. 877–880. doi:10.1145/3209978.3210066. [16] J. Mackenzie, M. Petri, A. Mofat, Anytime ranking on document-ordered indexes, ACM
Trans. on Information Systems 40 (2022) 13:1–13:32. doi:10.1145/3467890. [17] A. Mallia, M. Siedlaczek, J. Mackenzie, T. Suel, PISA: Performant indexes and search for academia, in: Proc. OSIRRC at SIGIR 2019, 2019, pp. 50–56. URL: http://ceur-ws.org/ Vol-2409/docker08.pdf. [18] J. Mackenzie, A. Trotman, J. Lin, Wacky weights in learned sparse representations and the revenge of score-at-a-time query evaluation, arXiv:2110.11540 (2021). URL: https: //arxiv.org/abs/2110.11540.