Efficient Neural Ranking using Forward Indexes and Lightweight Encoders

Jurek Leonhardt

Delft University of Technology
The Netherlands

L3S Research Center

Henrik Müller

L3S Research Center

Koustav Rudra

Indian Institute of Technology Kharagpur

Megha Khosla

Delft University of Technology

Abhijit Anand

L3S Research Center

Avishek Anand

Delft University of Technology

Dual-encoder-based dense retrieval models have become the standard in IR. They employ large Transformer-based language models, which are notoriously inefficient in terms of resources and latency.

We propose  indexes—vector forward indexes which exploit the semantic matching capabilities of dual-encoder models for efficient and effective re-ranking. Our framework enables re-ranking at very high retrieval depths and combines the merits of both lexical and semantic matching via score interpolation. Furthermore, in order to mitigate the limitations of dual-encoders, we tackle two main challenges: Firstly, we improve computational efficiency by either pre-computing representations, avoiding unnecessary computations altogether, or reducing the complexity of encoders. This allows us to considerably improve ranking efficiency and latency. Secondly, we optimize the memory footprint and maintenance cost of indexes; we propose two complementary techniques to reduce the index size and show that, by dynamically dropping irrelevant document tokens, the index maintenance efficiency can be improved substantially.

We perform evaluation to show the effectiveness and efficiency of  indexes—our method has low latency and achieves competitive results without the need for hardware acceleration, such as GPUs.

<concept_desc>Information systems Retrieval models and ranking</concept_desc>
<concept_desc>Information systems Search engine indexing</concept_desc>
<concept_desc>Information systems Search index compression</concept_desc>

[500]Information systems Retrieval models and ranking
[300]Information systems Search engine indexing
[300]Information systems Search index compression

§ INTRODUCTION

Neural rankers are typically based on large pre-trained language models, the most popular example being BERT <cit.>. Due to their architectural inductive bias (like self-attention units) and complexity, these models are able to capture the semantics of documents very well, mitigating the limitations of lexical retrievers. However, their capabilities come at a price, as the models commonly used often have upwards of hundreds of millions of parameters. This makes training and even inference without specialized hardware infeasible, and it is impossible to rank all documents in a large corpus in reasonable time. Furthermore, the resources required to run these models produce a considerable amount of emissions, creating a negative impact on the environment <cit.>.

There are two predominant approaches to deal with the inefficiency of neural ranking models. The first one, referred to as retrieve-and-re-rank <cit.>, uses an efficient lexical retriever to obtain a candidate set of documents for the given query. The idea is to maximize the recall, i.e., capture most of the relevant documents, in the first stage. Afterwards, the second stage employs a complex neural ranker, which re-ranks the documents in the candidate set, in order to promote the relevant documents to higher ranks. However, the retrieve-and-re-rank approach typically employs cross-attention re-rankers, which are expensive to compute even for a small set of candidate documents. This limits the first-stage retrieval depth, as low latency is essential for many applications (e.g., search engines).

The second approach skips the lexical retrieval step entirely and uses neural models for retrieval. The dual-encoder architecture employs a query encoder and a document encoder, both of which are neural models which map their string inputs to dense representations in a common vector space. Retrieval is then performed as a $k$-nearest-neighbor ($k$NN) search operation to find the documents whose representations are most similar to the query. This is referred to as dense retrieval <cit.>. Representing queries and documents independently means that most
of the computationally expensive processing happens during the indexing stage, where document representations are pre-computed. However, dense retrieval is still slower than lexical retrieval and benefits from GPU acceleration, because the query needs to be encoded during the query-processing phase. Furthermore, we find that dense retrievers generally have lower recall than term-matching-based models at higher retrieval depths.

In this paper, we argue that neither of the two approaches is ideal. Instead, our first key idea is to explore the utility of dual-encoders in the re-ranking phase instead of the retrieval phase. Using dual-encoders in the re-ranking phase allows for a drastic reduction of query processing times and resource utilization (i.e., GPUs) during document encoding. Towards this, we first show that simple interpolation-based re-ranking that combines the benefits of lexical (computed using sparse retrieval) and semantic (computed using dual-encoders) similarity can result in competitive and sometimes better performance than using cross-attention. We propose a novel index structure called  indexes, which exploits the ability of dual-encoders to pre-compute document representations, in order to substantially improve the runtime efficiency of re-ranking. We empirically establish that dual-encoder models show great performance as re-rankers, even though they do not use cross-attention.

Our second observation is that most current dual-encoder models use the same encoder for both documents and queries. While this design decision makes training easier, it also means that queries have to be encoded during runtime using a, potentially expensive, forward pass. We argue that this is suboptimal; rather, queries, which are often short and concise, do not require a complex encoder to compute their representations. We propose lightweight query encoders, some of which do not contain any self-attention layers, and show that they still perform well as re-rankers, while requiring only a fraction of the resources and time. In this work, we propose two families of lightweight query encoders to drastically reduce query-encoding costs without compromising ranking performance.

Lastly, we focus on the aspects of index footprint and index maintenance. Since dense indexes store the pre-computed representations of documents in the corpus, they exhibit much higher storage and memory requirements compared to sparse indexes <cit.>. At the same time, maintaining the index, i.e., adding new documents, requires expensive forward passes of the document encoder. We propose two means of reducing the memory footprint: On the one hand, we propose sequential coalescing to compress an index by reducing the number of vectors that need to be stored; on the other hand, we experiment with choosing a smaller number of dimensions, which reduces the size of each vector. Finally, we propose efficient document encoders, which dynamically drop irrelevant tokens prior to indexing using a very simple technique.

Our research questions are as follows:

RQ1 How suitable are dual-encoder models for interpolation-based re-ranking in terms of performance and efficiency?

RQ2 Can the re-ranking efficiency be improved by limiting the number of  look-ups?

RQ3 To what extent does query encoder complexity affect re-ranking performance?

RQ4 What is the trade-off between  index size and ranking performance?

RQ5 Can the indexing efficiency be improved by removing irrelevant document tokens?

We conduct extensive experimentation on existing ranking benchmarks and find that dual-encoder models are very suitable for interpolation-based re-ranking and exhibit highly desirable performance and efficiency trade-offs. We show that, with further optimizations (early stopping—cf. <ref>), re-ranking efficiency can be greatly improved by limiting the number of  look-ups. Additionally, we report a good trade-off between  index size and ranking performance by using our novel sequential coalescing algorithm (cf. <ref>). Our experiments show that we can indeed train extremely lightweight query encoders without adversely affecting ranking performance. Specifically, our most lightweight query encoders are orders of magnitude faster than  models with little performance degradation. More importantly, we can migrate query-processing to CPUs instead of relying on GPUs, improving on the environmental impact. Finally, we show that we can reduce index maintenance costs by around 50% by dynamically removing irrelevant document tokens. Our code is publicly available.

Note that this paper extends our previously published work <cit.>, where we introduced  indexes along with the sequential coalescing and early stopping techniques. This paper introduces the following new aspects:

* We identify the query encoder as an efficiency bottleneck of  indexes and propose lightweight query encoders.

* We show that the dimensionality of queries and documents can be reduced in order to reduce index size and compute dot products faster.

* We propose a selective document encoder that dynamically identifies irrelevant document tokens and drops them prior to indexing, reducing index maintenance cost.

* We perform additional experiments, including analyses of the trade-offs between efficiency and performance. We discuss the limitations of our method and its out-of-domain performance.

§ RELATED WORK

Classical ranking approaches, such as  <cit.> or the query likelihood model <cit.>, rely on the inverted index that stores term-level statistics like term frequency, inverse document frequency and positional information. We refer to this style of methods as sparse, since it assumes sparse document representations. The recent success of large pre-trained language models (e.g., BERT) shows that semantic or contextualized information is essential for many language tasks. In order to incorporate such information in the relevance measurement, <cit.> proposed , which stores contextualized scores for terms in the inverted index for text ranking.  <cit.> aims to enrich sparse document representations using a trained contextual Transformer model and sparsity regularization on the term weights. Similarly,  <cit.> enriches the document collection with expansion terms to learn improved term impacts. In our work, we employ efficient sparse models for high-recall first-stage retrieval and perform re-ranking using semantic models in a subsequent step.

The ability to accurately determine semantic similarity is essential in order to alleviate the vocabulary mismatch problem <cit.>. Computing the semantic similarity of a document given a query has been heavily researched in IR using smoothing methods <cit.>, topic models <cit.>, embeddings <cit.>, personalized models <cit.>, etc. In these classical approaches, ranking is performed by interpolating the semantic similarity scores with the lexical matching scores from the first-stage retrieval. More recently, dense neural ranking methods, which employ large pre-trained language models, have become increasingly popular. Dense rankers do not explicitly model terms, but rather compute low-dimensional dense vector representations through self-attention mechanisms in order to estimate relevance; this allows them to perform semantic matching. However, the inherent complexity of dense ranking models usually has a negative impact on latency and cost, especially with large corpora. Therefore, besides performance, efficiency has been another major concern in developing neural ranking models.

There are two common architectures of dense ranking models: Cross-attention models take a concatenation of a query and a document as input. This allows them to perform query-document attention in order to compute the corresponding relevance score. These models are typically used as re-rankers. Dual-encoder models employ two language models to independently encode queries and documents as fixed-size vector representations. Usually, a similarity metric between query and document vector determines their relevance. As a result, dual-encoders are mostly used for dense retrieval, but also, less commonly, for re-ranking.

We divide the remainder of the related work section into subcategories for cross-attention models, dual-encoder models, and hybrid models, which employ both lexical and semantic rankers. Finally, we briefly cover inference efficiency for BERT-based models.

§.§ Cross-Attention Models

The majority of cross-attention approaches have been dominated by large contextual models <cit.>. The input to these ranking models is a concatenation of the query and document. This combined input results in higher query processing times, since each document has to be processed in conjugation with the query string. Thereby, cross-attention models usually re-rank a relatively small number of potentially relevant candidates retrieved in the first stage by efficient sparse methods. The expensive re-ranking computation cost is then proportional to the retrieval depth (e.g., 1000 documents).

Another key limitation of using cross-attention models for document ranking is the maximum acceptable number of input tokens for Transformer models, which exhibit quadratic complexity w.r.t. input length. Some strategies address this limitation by document truncation <cit.>, or chunking documents into passages <cit.>. However, the performance of chunking-based strategies depends on the chunking properties, i.e., passage length or overlap among consecutive passages <cit.>. Recent proposals include a two-stage approach, where a query-specific summary is generated by selecting relevant parts of the document, followed by re-ranking strategies over the query and summarized document <cit.>. Due to the efficiency concerns, we do not consider cross-attention methods in our work, but focus on dual-encoders instead.

§.§ Dual-Encoders

Dual-encoders learn dense vector representations for queries and documents using contextual models <cit.>. The dense vectors are then indexed in an offline phase <cit.>, where retrieval is akin to performing an approximate nearest neighbor (ANN) search given a vectorized query. This allows dual-encoders to be used for both retrieval and re-ranking. Consequently, there has been a large number of follow-up works that boost the performance of dual-encoder models by improving pre-training <cit.>, optimization <cit.>, and negative sampling <cit.> techniques, or employing distillation approaches <cit.>. <cit.> propose a negative cache that allows for efficient training of dual-encoder models.  <cit.> uses a  model to enrich a dense encoder with lexical information. <cit.> propose , a dual-encoder model which aggregates and exploits all token representations (instead of only the classification token). In this work, we use dual-encoders for computing semantic similarity between queries and passages. Some approaches have also proposed architectural modifications to the aggregations between the query and passage embeddings <cit.>. <cit.> propose a simple document expansion model. We use dual-encoder models to perform efficient semantic re-ranking in our work.

Efficiency improvements of dual-encoder-based ranking and retrieval focus mostly on either inference efficiency of the encoders or memory footprint of the indexes.  <cit.> and  <cit.> efficiently re-rank documents using a deep query and document likelihood model instead of a query encoder. The  model <cit.> employs a dual document encoder that has a term weighting and term expansion component; it improves inference efficiency by using a vastly simplified query representation. <cit.> employ dynamic lexical routing in order to reduce the number of dot products in the late interaction step. <cit.> use auto-encoders to compress document representations into fewer dimensions in order to reduce the overall size. <cit.> propose an approach to split documents into variable-length segments and dynamically merge them based on similarity, such that each document has the same number of segments prior to indexing. <cit.> introduce , an extension of  <cit.>, which removes irrelevant word representations in order to reduce the number of stored vectors. In a similar fashion, <cit.> propose a learned token pruning approach, which is also used to reduce the size of  indexes by dropping tokens that are deemed irrelevant. <cit.> propose a contextual quantization approach for pre-computed document representations (such as the ones used by ) by compressing document-specific representations of terms.

In most of the previous work, dual-encoders are used in a homogeneous or symmetric fashion, meaning that both the query and document encoder have the same architecture or even share weights (Siamese encoders). <cit.> show that the characteristics of queries and documents are different and employ light fine-tuning in order to adapt each encoder to its specific role. <cit.> use model distillation for asymmetric dual-encoders, where the query encoder has fewer parameters than the document encoder. <cit.> separate the query and document encoder of  models in order to improve efficiency. In this work, we explore the use of light-weight query encoders for more efficient re-ranking.

§.§ Hybrid Models

Hybrid models combine sparse and dense retrieval. The most common approach is a simple linear combination of both scores <cit.>.  <cit.> takes the relevance of the lexical retriever into account in the loss function of the dense retriever.  <cit.> performs contextualized exact matching using pre-computed document token representations.  <cit.> extends this approach by factorizing token representations and approximating them using canonical representations in order to make retrieval more efficient.

Unlike classical methods, where score interpolation is the norm, semantic similarity from neural contextual models (e.g., cross-attention or dual-encoders) is not consistently combined with the matching score. Recently, <cit.> showed that the interpolation of BERT-based models and lexical retrieval methods can boost the performance. Furthermore, they analyze the role of interpolation in BERT-based dense retrieval strategies and find that dense retrieval alone is not enough, but interpolation with  scores is necessary. Similarly, <cit.> find that even providing the  score as part of the input text improves the re-ranking performance of BERT models.

§.§ Inference Efficiency

Several methods have been proposed to improve the inference efficiency of large Transformer-based models, which have quadratic time complexity w.r.t. the input length.  <cit.> progressively eliminates word vectors in the subsequent encoder layers in order to reduce the input size.  <cit.> implements an early-exit mechanism, which may stop the computation after any Transformer layer based on the entropy of its output distribution.  <cit.> uses a technique where intermediate Transformer layers can be skipped dynamically using pre-computed look-up tables. We use a simple  approach which dynamically removes irrelevant document tokens in order to make document encoding more efficient.

§ PRELIMINARIES

In this section, we introduce core concepts that are essential to this work, such as retrieval, re-ranking, and interpolation.

§.§ Interpolation-Based Re-Ranking

The retrieval of documents or passages given a query often happens in two stages <cit.>: In the first stage, a term frequency-based (sparse) retrieval method (such as  <cit.>) retrieves a set of documents from a large corpus. In the second stage, another model, which is usually much more computationally expensive, re-ranks the retrieved documents again.

In sparse retrieval, we denote the top-$k_S$ documents retrieved from the sparse index for a query $q$ as $K^q_S$. The sparse score of a query-document pair $(q, d)$ is denoted by $\phi_S(q, d)$. For the re-ranking part, we focus on self-attention models (such as BERT <cit.>) in this work. These models operate by creating (internal) high-dimensional dense representations of queries and documents, focusing on their semantic structure. We refer to the outputs of these models as dense or semantic scores and denote them by $\phi_D(q, d)$. Due to the quadratic time complexity of self-attention w.r.t. the document length (and decreasing performance with increasing document length <cit.>), long documents are often split into passages, and the score of a document is then computed as the maximum of its passage scores:

\begin{equation}
\label{eqn:prelims.interpolated_reranking.maxp}
\phi_D(q, d) = \max_{p_i \in d} {\phi_D(q, p_i)}
\end{equation}

This approach is referred to as maxP <cit.>.

The retrieval approach for a query $q$ starts by retrieving $K^q_S$ from the sparse index. For each retrieved document $d \in K^q_S$, the corresponding dense score $\phi_D(q, d)$ is computed. This dense score may then be used to re-rank the retrieved set to obtain the final ranking. However, it has been shown that the scores of the sparse retriever, $\phi_S$, can be beneficial for re-ranking as well <cit.>. To that end, an interpolation approach is employed <cit.>, where the final score of a query-document pair is computed as

\begin{equation}
\label{eqn:prelims.interpolated_reranking.interpolation}
\phi(q, d) = \alpha \cdot \phi_S(q, d) + (1 - \alpha) \cdot \phi_D(q, d).
\end{equation}

Setting $\alpha = 0$ recovers the standard re-ranking procedure.

Since the set of documents retrieved by the sparse model is typically large (e.g., $k_S = 1000$), computing the dense score for each query-document pair can be very computationally expensive. In this paper, we focus on efficient implementations of interpolation-based re-ranking, specifically the computation of the dense scores $\phi_D$.

§.§ Dual-Encoder Models

The dual-encoder architecture <cit.> employs neural semantic models to compute dense vector representations of queries and documents. Specifically, a query encoder $\zeta$ and a document encoder $\eta$ map queries and documents to representations in a common $a$-dimensional vector space. The relevance score $\phi_D(q, d)$ of a query-document pair is then computed as the similarity of their vector representations. A common choice for the similarity function is the dot product, such that

\begin{equation}
\phi_D(q, d) = \zeta(q) \cdot \eta(d),
\end{equation}

where $\zeta(q), \eta(d) \in \mathbb{R}^a$.

§.§.§ Dense Retrieval

Dual-encoder models are commonly utilized to perform dense retrieval <cit.>. A dense index contains pre-computed vector representations $\eta(d)$ for all documents $d$ in the corpus $\mathcal{D}$. To retrieve a set of documents $K^q_D$ for a query $q$, a $k$-nearest neighbor ($k$NN) search is performed to find the documents whose representations are most similar to the query:

\begin{equation}
K^q_D = \kargmax_{1 \leq i \leq |\mathcal{D}|} (\zeta(q) \cdot \eta(d_i))
\end{equation}

In order to make dense retrieval more efficient, approximate nearest neighbor (ANN) search is commonly employed <cit.>. ANN search can be further accelerated using special hardware, such as GPUs <cit.>.

§.§.§ Training

In contrast to cross-encoder models, which are often used for re-ranking (cf. <ref>), dual-encoders encode the query and document independently, i.e., there is no query-document attention. Typically, dual-encoders for retrieval are trained using a contrastive loss function <cit.>,

\begin{equation}
\label{eq:prelims.dual_encoders.training.loss}
\mathcal{L}(q, d^+, D^-) =
\left(
\frac
{\exp \left(\phi(q, d^+; \theta) / \tau \right)}
{\sum_{d \in D^- \cup \{d^+\}} \exp \left(\phi(q, d; \theta) / \tau \right)}
\right),
\end{equation}

where a training instance consists of a query $q$, a positive (relevant) document $d^+$, and a set $D^-$ of negative (irrelevant) documents. The temperature $\tau$ is a hyperparameter. Since it is usually infeasible to include all negative documents for a query in $D^-$, there are various negative sampling approaches, such as distillation <cit.>, asynchronous indexes <cit.>, or negative caches <cit.>. In this work, we use a simple in-batch strategy <cit.>, where, for a query $q$, $D^-$ contains a number of hard negatives (retrieved by BM25) along with all documents from the other queries in the same training batch.

§.§ Hybrid Retrieval

Hybrid retrieval <cit.> is similar to interpolation-based re-ranking (cf. <ref>). The key difference is that the dense scores $\phi_D(q, d)$ are not computed for all query-document pairs. Instead, $\phi_D$ is a dense retrieval model (cf. <ref>), which retrieves documents $d_i$ and their scores $\phi_D(q, d_i)$ using nearest neighbor search given a query $q$. A hybrid retriever combines the retrieved sets of a sparse and a dense retriever.

For a query $q$, we retrieve two sets of documents, $K^q_S$ and $K^q_D$, using the sparse and dense retriever, respectively. Note that the two retrieved sets are usually not equal.
One strategy proposed in <cit.> ranks all documents in $K^q_S \cup K^q_D$, approximating missing scores. In our experiments, however, we found that only considering documents from $K^q_S$ for the final ranking and discarding the rest works well. The final score is thus computed as

\begin{equation}
\label{eqn:prelims.hybrid_retrieval.hybrid}
\phi(q, d) = \alpha \cdot \phi_S(q, d) + (1 - \alpha) \cdot
\begin{cases}
\phi_D(q, d) & d \in K^q_D    \\
\phi_S(q, d) & d \notin K^q_D
\end{cases}.
\end{equation}

The re-ranking step in hybrid retrieval is essentially a sorting operation over the interpolated scores and takes negligible time in comparison to standard re-ranking.

§  INDEXES

The hybrid approach described in <ref> has two distinct disadvantages. Firstly, in order to retrieve $K_D^q$, an (approximate) nearest neighbor search has to be performed, which is time consuming. Secondly, some of the query-document scores are expected to be missed, leading to an incomplete interpolation, where the score of one of the retrievers needs to be approximated <cit.> for a number of query-document pairs.

Sequential coalescing combines the representations of similar consecutive passages as their average. Note that $p_3$ and $p_5$ are not combined, as they are not consecutive passages.

Early stopping reduces the number of interpolation steps by computing an approximate upper bound for the dense scores. This example depicts the most extreme case, where only the top-1 document is required.

In this section, we propose  indexes as an efficient way of computing dense scores for known documents that alleviates the aforementioned issues. Specifically,  indexes build upon dual-encoder dense retrieval models that compute the score of a query-document pair as a dot product

\begin{equation}
\phi_D(q, d) = \zeta(q) \cdot \eta(d),
\end{equation}

where $\zeta$ and $\eta$ are the query and document encoders, respectively. Examples of such models are  <cit.> and  <cit.>. Since the query and document representations are independent for two-tower models, we can pre-compute the document representations $\eta(d)$ for each document $d$ in the corpus. These document representations are then stored in an efficient hash map, allowing for look-ups in constant time. After the index is created, the score of a query-document pair can be computed as

\begin{equation}
\phi_D^{FF}(q, d) = \zeta(q) \cdot \eta^{FF}(d),
\end{equation}

where the superscript $FF$ indicates the look-up of a pre-computed document representation in the  index. At retrieval time, only $\zeta(q)$ needs to be computed once for each query. As queries are usually short, this can be done on CPUs. The main benefit of this method is that the number of documents to be re-ranked can be much higher than with cross-attention models; the scoring operation is a simple look-up and dot product computation.

Note that the use of large Transformer-based query encoders still remains a bottleneck in terms of latency (or, if it is run on GPUs, cost). In <ref>, we focus on lightweight encoder models.

§.§ Index Compression via Sequential Coalescing

A major disadvantage of dense indexes and dense retrieval in general is the size of the final index. This is caused by two factors: Firstly, in contrast to sparse indexes, the dense representations cannot be stored as efficiently as sparse vectors. Secondly, the dense encoders are typically Transformer-based, imposing a (soft) limit on their input lengths due to their quadratic time complexity with respect to the inputs. Thus, long documents are split into passages prior to indexing (maxP indexes).

list of passage vectors $P$ (original order) of a document, distance threshold $\delta$
coalesced passage vectors $P'$
$P' \leftarrow$ empty list
$\mathcal{A} \leftarrow \emptyset$
$v$ $P$
first iteration
do nothing

$\Dist(v, \overline{\mathcal{A}}) \geq \delta$
append $\overline{\mathcal{A}}$ to $P'$
$\mathcal{A} \leftarrow \emptyset$

add $v$ to $\mathcal{A}$
$\overline{\mathcal{A}} \leftarrow \Mean(\mathcal{A})$

append $\overline{\mathcal{A}}$ to $P'$
Compression of dense maxP indexes by sequential coalescing

As an increase in the index size has a negative effect on efficiency, both for nearest neighbor search and  indexing as used by our approach, we exploit a sequential coalescing approach as a way of dynamically combining the representations of consecutive passages within a single document in maxP indexes. The idea is to reduce the number of passage representations in the index for a single document. This is achieved by exploiting the topical locality that is inherent to documents <cit.>. For example, a single document might contain information regarding multiple topics; due to the way human readers naturally ingest information, we expect documents to be authored such that a single topic appears mostly in consecutive passages, rather than spread throughout the whole document. Our approach aims to combine consecutive passage representations that encode similar information. To that end, we employ the cosine distance function and a threshold parameter $\delta$ that controls the degree of coalescing. Within a single document, we iterate over its passage vectors in their original order and maintain a set $\mathcal{A}$, which contains the representations of the already processed passages, and continuously compute $\overline{\mathcal{A}}$ as the average of all vectors in $\mathcal{A}$. For each new passage vector $v$, we compute its cosine distance to $\overline{\mathcal{A}}$. If it exceeds the distance threshold $\delta$, the current passages in $\mathcal{A}$ are combined as their average representation $\overline{\mathcal{A}}$. Afterwards, the combined passages are removed from $\mathcal{A}$ and $\overline{\mathcal{A}}$ is recomputed. This approach is illustrated in <ref>. <ref> shows an example index after coalescing. To the best of our knowledge, there are no other forward index compression techniques proposed in literature so far.

§.§ Faster Interpolation by Early Stopping

As described in <ref>, by interpolating the scores of sparse and dense retrieval models, we perform implicit re-ranking, where the dense representations are pre-computed and can be looked up in a  index at retrieval time. Furthermore, increasing the sparse retrieval depth $k_S$, such that $k_S > k$, where $k$ is the final number of documents, improves the performance. A drawback of this is that an increase in the number of retrieved documents also results in an increase in the number of index look-ups.

Common term pruning mechanisms for term-at-a-time retrieval, such as  <cit.> or  <cit.>, accelerate query processing for inverted-index-based retrievers; however, these techniques are not compatible with neural ranking models based on contextual query and document representations. Our use case is more similar to top-k query evaluation, with algorithms such as the threshold algorithm <cit.> or probabilistic approximations <cit.>, but these approaches usually require sorted access, which is not available for the dense re-ranking scores in our case.

query $q$, sparse retrieval depth $k_S$, cut-off depth $k$, interpolation parameter $\alpha$
approximated top-$k$ scores $Q$
$Q \leftarrow$ priority queue of size $k$
$s_{D} \leftarrow -\infty$
$s_{min} \leftarrow -\infty$
$d$ $\Sparse(q, k_S)$
$Q$ is full
$s_{min} \leftarrow$ remove smallest item from Q
$s_{best} \leftarrow \alpha \cdot \phi_S(q, d) + (1 - \alpha) \cdot s_{D}$

$s_{best} \leq s_{min}$
early stopping
put $s_{min}$ into $Q$

approximate max. dense score
$s_{D} \leftarrow \Max(\phi_D(q, d), s_{D})$
$s \leftarrow \alpha \cdot \phi_S(q, d) + (1 - \alpha) \cdot \phi_D(q, d)$
put $\Max(s, s_{min})$ into $Q$

Interpolation with early stopping

In this section, we propose an extension to  indexes that allows for early stopping, i.e., avoiding a number of unnecessary look-ups, for cases where $k_S > k$ by approximating the maximum possible dense score. The early stopping approach takes advantage of the fact that documents are ordered by their sparse scores $\phi_S(q, d)$. Since the number of retrieved documents, $k_S$, is finite, there exists an upper limit $s_D$ for the corresponding dense scores such that $\phi_D(q, d) \leq s_D \forall d \in K^q_S$. Since the retrieved documents $K^q_S$ are ordered by their sparse scores, we can simultaneously perform interpolation and re-ranking by iterating over the ordered list of documents: Let $d_i$ be the $i$th highest ranked document by the sparse retriever. Recall that we compute the final score as

\begin{equation}
\phi(q, d_i) = \alpha \cdot \phi_S(q, d_i) + (1 - \alpha) \cdot \phi_D(q, d_i).
\end{equation}

If $i > k$, we can compute the upper bound for $\phi(q, d_i)$ by exploiting the aforementioned ordering:

\begin{equation}
s_{best} = \alpha \cdot \phi_S(q, d_{i-1}) + (1 - \alpha) \cdot s_D.
\end{equation}

In turn, this allows us to stop the interpolation and re-ranking if $s_{best} \leq s_{min}$, where $s_{min}$ denotes the score of the $k$th document in the current ranking (i.e., the currently lowest ranked document). Intuitively, this means that we stop the computation once the highest possible interpolated score $\phi(q, d_i)$ is too low to make a difference. The approach is illustrated in <ref> and <ref>. Since the dense scores $\phi_D$ are usually unnormalized, the upper limit $s_D$ is unknown in practice. We thus approximate it by using the highest observed dense score at any given step.

§.§.§ Theoretical Analysis

We first show that the early stopping criteria, when using the true maximum of the dense scores, is sufficient to obtain the top-$k$ scores.

Let $s_D$, as used in <ref>, be the true maximum of the dense scores. Then the returned scores are the actual top-$k$ scores.

First, note that the sparse scores, $\phi_S(q, d_i)$, are already sorted in decreasing order for a given query. By construction, the priority queue $Q$ always contains the highest scores corresponding to the list parsed so far. Let, after parsing $k$ scores, $Q$ be full. Now the possible best score $s_{best}$ is computed using the sparse score found next in the decreasing sequence and the maximum of all dense scores, $s_D$ (cf. <ref>). If $s_{best}$ is less than the minimum of the scores in $Q$, then $Q$ already contains the top-$k$ scores. To see this, note that the first component of $s_{best}$ is the largest among all unseen sparse scores (as the list is sorted) and $s_D$ is the maximum of the dense scores by our assumption.

Next, we show that a good approximation of the top-$k$ scores can be achieved by using the sample maximum. To prove our claim, we use the Dvoretzky–Kiefer–Wolfowitz (DKW) <cit.> inequality.

Let $X_1, X_2, ..., X_n$ be $n$ real-valued independent and identically distributed random variables with the cumulative distribution function $F(\cdot)$. Let $F_n(\cdot)$ denote the empirical cumulative distributive function, i.e.,

\begin{equation}
F_{n}(x)=\frac{1}{n} \sum_{i=1}^{n} \mathbbm{1}_{\left\{X_{i} \leq x\right\}}, \quad x \in \mathbb{R}.
\end{equation}

According to the DKW inequality, the following estimate holds:

\begin{equation}
\Pr \left( \sup_{x \in \mathbb{R}} \left( F_{n}(x) - F(x) \right) > \epsilon \right) \leq e^{-2n \epsilon^2} \forall \epsilon \geq \sqrt{\frac{1}{2n} \ln 2}.
\end{equation}

In the following, we show that, if $s_D$ is chosen as the maximum of a large random sample drawn from the set of dense scores, then the probability that any given dense score, chosen independently and uniformly at random from the dense scores, is greater than $s_D$ is exponentially small in the sample size.

Let $x_1, x_2, ..., x_n$ be a real-valued independent and identically distributed random sample drawn from the distribution of the dense scores with the cumulative distribution function $F(\cdot)$. Let $z = \max{(x_1, x_2, ..., x_n)}$. Then, for every $\epsilon > \frac{1}{\sqrt{2n}} \ln 2$, we obtain

\begin{equation}
\label{eq:ff_indexes.early_stopping.dkw_dense}
\Pr(F(z) < 1 - \epsilon) \leq e^{-2n \epsilon^2}.
\end{equation}

Let $F_n(\cdot)$ denote the empirical cumulative distribution function as above. Specifically, $F_n(x)$ is equal to the fraction of variables less than or equal to $x$. We then have $F_n(z) = 1$. By <ref>, we infer

\begin{equation}
\Pr(F_n(z) - F(z) > \epsilon) \leq e^{-2n \epsilon^2}.
\end{equation}

Substituting $F_n(z) = 1$, we obtain Equation (<ref>).

This implies that the probability of any random variable $X$, chosen randomly from the set of dense scores, being less than or equal to $s_D$, is greater than or equal to $1 - \epsilon$ with high probability, i.e.,

\begin{equation}
\Pr(P_D(X \leq s_D) \geq 1 - \epsilon) \geq 1 - e^{-2n \epsilon^2},
\end{equation}

where $P_D$ denotes the probability distribution of the dense scores. This means that, as our sample size grows until it reaches $k$, the approximation improves.
Note that, in our case, the dense scores are sorted (by corresponding sparse score) and thus the i.i.d. assumption cannot be ensured. However, we observed that the dense scores are positively correlated with the sparse scores. We argue that, due to this correlation, we can approximate the maximum score well.

§ EFFICIENT ENCODERS

BERT models are the de facto standard for both query and document encoders <cit.>. The encoders are often homogeneous, meaning that the architectures of both models are identical, or even Siamese, i.e., the same encoder weights are used for both queries and documents. Other approaches are semi-Siamese models <cit.>, where light fine-tuning is used to adapt each encoder to its input characteristics, or  <cit.> and  <cit.>, which do not require dense query representations. However, the most common choice remains the use of  for both encoders.

The distribution of query and passage lengths in the MS MARCO corpus. The statistics are computed based on the development set queries and the first 10000 passages from the corpus using a  tokenizer.

In this paper, we argue that the homogeneous structure is not ideal for dual-encoder IR models w.r.t. query processing efficiency, since the characteristics of queries and documents differ <cit.>. We illustrate those characteristics w.r.t. the average number of tokens in <ref>. This section focuses on model architectures for both query and document encoding that aim to improve the overall efficiency of the ranking process.

§.§ Lightweight Query Encoders

Query encoders need to be run online during query processing, i.e., the representations cannot be pre-computed. Consequently, query encoding latency is essential for many downstream applications, such as search engines. Our experiments reveal that even encoding a large batch of 256 queries using a  model on CPU takes more than 3 seconds (cf. <ref>), resulting in roughly 12 milliseconds per query (smaller batch sizes or even single queries lead to even slower encoding). Since queries are typically short and concise, we argue that query encoders require lower complexity (e.g., in terms of the number of parameters) than document encoders. Our proposed query encoders are considerably more lightweight than standard  models, and thus more efficient in terms of latency and resources.

Attention-based query encoder

Embedding-based query encoder

The query-encoder types used in this work. Note that the positional encoding that is added to BERT input tokens has been omitted in this figure.

§.§.§ Attention-based

Attention-based query encoders (such as models based on BERT <cit.>) use Transformer encoder layers <cit.> to compute query representations. Each of these layers has two main components — multi-head attention and a feed-forward sub-layer — both of which include residual connections and layer normalization operations.

Attention is computed based on three input matrices — the queries $\mat{Q}$, keys $\mat{K}$, and values $\mat{V}$:

\begin{equation}
\operatorname{Attn}(\mat{Q}, \mat{K}, \mat{V}) = \operatorname{softmax}\left(\frac{\mat{Q} \mat{K}^T}{\sqrt{d_k}}\right) \mat{V}.
\end{equation}

Multi-head attention computes attention multiple times (using $A$ attention heads $h_i$) and concatenates the results, as denoted by $\circ$, i.e.,

\begin{equation}
\begin{aligned}
\operatorname{MultiHead}(\mat{Q}, \mat{K}, \mat{V}) & = \left(h_1 \circ \ldots \circ h_A \right) \mat{W}^{O},                                            \\
\text{where } h_i                                   & = \operatorname{Attn} \left(\mat{Q} \mat{W}_i^Q, \mat{K} \mat{W}_i^K, \mat{V} \mat{W}_i^V \right).
\end{aligned}
\end{equation}

The matrices $\mat{W}_i^Q \in \mathbb{R}^{H \times d_k}$, $\mat{W}_i^K \in \mathbb{R}^{H \times d_k}$, $\mat{W}_i^V \in \mathbb{R}^{H \times d_v}$ and $\mat{W}^O \in \mathbb{R}^{A d_v \times H}$ are trainable parameters, $H$ denotes the dimension of hidden representations in the model, and $d_k = \frac{H}{A}$ is a scaling factor.

Since Transformer encoders compute self-attention, the three inputs $\mat{Q}$, $\mat{K}$ and $\mat{V}$ originate from the same place, i.e., they are projections of the output of the previous encoder layer. The inputs to the first encoder layer originate from a token embedding layer. We denote the embedding operation as $E: \mathbb{N} \mapsto \mathbb{R}^H$, such that $E(t)$ is the embedding vector of a token $t$.

Given a BERT-based encoder and a query $q = (t_1, ..., t_{|q|})$, where $t_i$ are  tokens, the query representation is computed as

\begin{equation}
\hat{\zeta}_\text{Attn}(q) = \operatorname{BERT}_\text{CLS}(\texttt{[CLS]}, t_1, ..., t_{|q|}, \texttt{[SEP]}),
\end{equation}

where $\operatorname{BERT}_\text{CLS}$ indicates that the output vector corresponding to the classification token, denoted by , is used. <Ref> shows attention-based query encoders.

The usual choice for query encoders, $\text{BERT}_\text{base}$, has $L=12$ layers, $H=768$ dimensions for hidden representations and $A=12$ attention heads. In this work, we investigate how less complex query encoders impact the re-ranking performance. Specifically, we vary three hyperparameters, namely the number of Transformer layers $L$, hidden dimensions $H$ and attention heads $A$. The pre-trained BERT models we use are provided by <cit.>.

§.§.§ Embedding-based

Embedding-based query encoders can be seen as a special case of BERT-based query encoders (cf. <ref>). Setting $L=0$, we obtain a model without any Transformer encoder layers; what's left is only the token embedding layer $E$.

Due to the omission of self-attention (and thus, contextualization) altogether, the usage of the  token is not feasible for this approach. Instead, a query $q = (t_1, ..., t_{|q|})$ is represented simply as the average of its token embeddings, i.e.,

\begin{equation}
\hat{\zeta}_\text{Emb}(q) = \frac{\sum_{t_i \in q} E(t_i)}{|q|}.
\end{equation}

Embedding-based query encoders are illustrated in <ref>.

§.§ Selective Document Encoders

Document encoders are not run during query processing time, since document representations are pre-computed and indexed. However, the computation of document representations still requires a substantial amount of time and resources. This is particularly important for applications like web search, where index maintenance plays an important role, usually due to large amounts of new documents constantly needing to be added to the index. The effect is further amplified by the maxP approach (cf. <ref>), where long documents require more than one encoding step. Since documents tend to be much longer and more complex than queries, lightweight document encoders would likely negatively affect performance, and recent research suggests that larger document encoders lead to better results <cit.>. However, due to the nature of documents obtained from web pages, we expect a considerable number of document tokens to be irrelevant for the encoding step; examples for this are stop words or redundant (repeated) information. Similar observations have been made in other approaches <cit.>. Furthermore, recent research <cit.> has shown that certain aspects, such as the position of tokens, are not essential for large language models to perform well. Our proposed document encoders assign a relevance score to each input token and dynamically drop low-scoring tokens before computing self-attention in order to make the document encoding step more efficient.

The fine-tuning and inference phase of  document encoders. In the given example, the documents in the input batch are dynamically shortened to four tokens each based on the corresponding relevance scores. Note that the positional encoding that is added to BERT input tokens has been omitted in this figure.

We refer to this approach as . It uses a scoring network $\Phi: \mathbb{N} \mapsto [0, 1]$ to determine the relevance of each input token before feeding it into the encoding BERT model $\Psi$. We denote the parameters of the scoring network as $\theta_\Phi$ and the parameters of the BERT model as $\theta_\Psi$. We use a lightweight, non-contextual scoring network with three 384-dimensional feed-forward layers and ReLU activations. The final layer outputs a scalar that is fed into a sigmoid activation function to compute the final score.  models are trained in two steps.

§.§.§ Pre-Training

The first step pre-trains the scoring network. $\theta_\Psi$ is initialized using the weights of a pre-trained  model (e.g., ), and $\theta_\Phi$ is initialized randomly. The complete model is then trained for a single epoch using the same data as during the unsupervised  pre-training step <cit.>. The scoring network $\Phi$ is taken into account by multiplying the embedding of an input token $t_i$ by its corresponding score, i.e.,

\begin{equation}
x_i = E(t_i) \cdot \Phi(t_i) + P(t_i),
\end{equation}

where $E(t_i)$ is the token embedding and $P(t_i)$ is the positional encoding. The resulting representation $x_i$ is then used to compute self-attention in the first encoder layer.

In order to encourage the scoring network to output scores less than one, we introduce a regularization term using the $L_1$-norm over the scores, where $n$ is the input sequence length:

\begin{equation}
\ell_1 = \sum_{i=0}^n \Phi(t_i).
\end{equation}

The final objective is a combination of the original BERT pre-training loss $\mathcal{L}$ and the scoring regularizer scaled by a hyperparameter $\lambda$:

\begin{equation}
\min_{\theta_\Psi, \theta_\Phi} \left[ \mathcal{L}(\theta_\Psi, \theta_\Phi) + \lambda \cdot \ell_1(\theta_\Phi)\right].
\end{equation}

§.§.§ Fine-Tuning and Inference

The second step, referred to as fine-tuning, only trains the BERT model $\Psi$, while the scoring network $\Phi$ remains frozen for the remainder of the training process. Furthermore, the weights of the BERT model obtained in the previous step, $\theta_\Psi$, are discarded and replaced by the same pre-trained model as before. The training objective during this stage is identical to that of other dual-encoder models (cf. <ref>).

During fine-tuning and inference (i.e., document encoding), we only retain the tokens with the highest scores; we set a ratio $p \in [0; 1]$ of the original input length to retain. As a result, the length of the input batch is shortened by $1-p$. This is achieved by removing the lowest scoring tokens from the input. Since individual documents within a batch are usually padded, $p$ always corresponds to the longest sequence in the batch. Consequently, padding tokens are always removed first before the scores of the other tokens are taken into account. The process is illustrated in <ref>.

§ EXPERIMENTAL SETUP

In this section, we outline the experimental setup, including baselines, datasets, and further details about training and evaluation.

§.§ Baselines

We consider the following baselines:

* Sparse retrievers rely on term-based matching between queries and documents. We consider , which uses term-based retrieval signals.  <cit.>,  <cit.>, and  <cit.> use sparse representations, but contextualize terms in some fashion.

* Dense retrievers retrieve documents that are semantically similar to the query in a common embedding space. We consider  <cit.>,  <cit.>, and the more recent  <cit.>. All three approaches are based on BERT encoders. Large documents are split into passages before indexing (maxP). These dense retrievers use exact (brute-force) nearest neighbor search as opposed to approximate nearest neighbor (ANN) search. We evaluate these methods in both the retrieval and re-ranking setting.

* Hybrid retrievers interpolate sparse and dense retriever scores. We consider  <cit.>, a retrieval model that complements lexical models with semantic matching. Additionally, we consider the hybrid strategy described in Section <ref> as a baseline, using the dense retrievers above.

* Re-rankers operate on the documents retrieved by a sparse retriever (e.g., ). Each query-document pair is input into the re-ranker, which outputs a corresponding score. In this paper, we use a  re-ranker, where the output corresponding to the classification token is used as the score. Note that re-ranking is performed using the full documents (i.e., documents are not split into passages). If an input exceeds 512 tokens, it is truncated. Furthermore, we consider  <cit.> with  expansion.

§.§ Datasets

We evaluate our models and baselines on a variety of diverse retrieval datasets:

* The TREC Deep Learning track <cit.> provides test sets and relevance judgments for retrieval and ranking evaluation on the MS MARCO corpora <cit.>. We use both the passage and document ranking test sets from the years 2019 and 2020 for our experiments. In addition, we use the MS MARCO development sets to determine the optimal values for hyperparameters.

* The BEIR benchmark <cit.> is a collection of various IR datasets, which are commonly evaluated in a zero-shot fashion, i.e., without using any of the data for training the model. We evaluate our models on a subset of the BEIR datasets, including tasks such as passage retrieval, question answering, and fact checking.

§.§ Evaluation Details

Our ranking experiments are performed on a single machine using an Intel Xeon Silver 4210 CPU and an NVIDIA Tesla V100 GPU. In our initial experiments (<ref>), we measured the per-query latency by performing each experiment four times and reporting the average latency, excluding the first measurement. In subsequent experiments (<ref>), we adjusted our way of measuring; we perform multiple runs of each experiment, where each run contains multiple latency measurements. We then report the average over all measurements of the fastest run. In <ref>, latency is reported as the sum of scoring (this includes operations like encoding queries and documents, obtaining representations from a  index, computing the scores as dot-products, and so on), interpolation (cf. <ref>), and sorting cost. Any pre-processing or tokenization cost is ignored. Where applicable, dense models use a batch size of 256. The first-stage (sparse) retrieval step is not included, as it is constant for all methods. The  indexes are loaded into the main memory entirely before they are accessed. In <ref>, we report end-to-end latency, which includes retrieval, re-ranking, and tokenization cost.

MS MARCO (documents)                                    MS MARCO (passages)

2[0pt][l]     2[0pt][l]-

The pre-trained dense encoders and corresponding indexes we used in our experiments. In each cell, the first line corresponds to a pre-trained encoder (to be obtained from the HuggingFace Hub) and the second line is a pre-built index provided by .

We use the  <cit.> toolkit, which provides a number of pre-trained encoders (available on the HuggingFace Hub[<https://huggingface.co/models>]) and corresponding indexes (see <ref>), for our retrieval experiments. Dense encoders (, , and ) output 768-dimensional representations. The sparse  retriever is provided by  as well. We use the pre-built indexes  ($k_1=0.82$, $b=0.68$) and  ($k_1=4.46$, $b=0.82$). Furthermore, we use  to run  with the provided  index and the pre-trained  model.

We use the MS MARCO development set to determine the interpolation parameter $\alpha$. We set $\alpha = 0.2$ for , $\alpha = 0.5$ for , and $\alpha = 0.7$ for  (<ref>). For , we set $\alpha = 0.3$ for  re-ranking and $\alpha = 0.1$ for  re-ranking. For the dual-encoder models we trained ourselves (<ref>), the value for $\alpha$ is determined based on nDCG@10 re-ranking results on the MS MARCO development set and varies slightly for each model.

§.§ Training Details

Our dual-encoder models are trained using the contrastive loss in <ref>. For each training instance, we sample 8 hard negative documents using BM25. Additionally, we use in-batch negatives and a batch size of 4, resulting in $|D^-| = 32$ negatives for each query. Each model is trained on four NVIDIA A100 GPUs. We set the learning rate to $1 \cdot 10^{-5}$ and use gradient accumulation of 32 batches (this results in an effective batch size of $4 \cdot 4 \cdot 32 = 512$). During training, we perform validation on the MS MARCO development set. Our models are trained until the average precision stops improving for five consecutive iterations. We exclusively train on the MS MARCO passage ranking corpus; the resulting models are then evaluated on multiple datasets (i.e., for BEIR, we do zero-shot evaluation). Our  model (cf. <ref>) uses $\lambda = 10^{-6}$ during pre-training. We implemented our models and training pipeline using PyTorch,[<https://pytorch.org/>] PyTorch-Lightning,[<https://pytorchlightning.ai/>] and Transformers.[<https://huggingface.co/>]

§.§.§ Dual-Encoder Architecture

Our dual-encoder rankers consist of a query encoder $\zeta$ and a document encoder $\eta$ (cf. <ref>):

\begin{align}
\zeta(q) & = || \mat{W}_\zeta \hat{\zeta}(q) + b_\zeta ||_2, \\
\eta(d)  & = || \mat{W}_\eta \hat{\eta}(d) + b_\eta ||_2.
\end{align}

The models $\hat{\zeta}$ and $\hat{\eta}$ map queries and documents to arbitrary vector representations; examples for these models are pre-trained Transformers or the encoders described in <ref>. We include optional trainable linear layers (with corresponding weights $\mat{W}_\zeta \in \mathbb{R}^{a \times d_\zeta}$, $\mat{W}_\eta \in \mathbb{R}^{a \times d_\eta}$, $b_\zeta \in \mathbb{R}^a$ and $b_\eta \in \mathbb{R}^a$) for heterogeneous encoders, where the dimensions of the representation vectors, $d_\zeta$ and $d_\eta$, do not match. We further $L_2$-normalize the representations during training and indexing; we do not normalize the query representations during ranking, as this would only scale the scores, but not change the final ranking.

§ RESULTS

In this section, we perform experiments to show the effectiveness and efficiency of  indexes. Each subsection corresponds to one of our research questions.

§ DISCUSSION

In this section, we reflect upon our work and present possible limitations.

§.§ Efficient Encoders for Dense Retrieval

$\text{AP}_\text{1k}$               $\text{R}_\text{1k}$     $\text{nDCG}_\text{10}$
$\text{AP}_\text{1k}$               $\text{R}_\text{1k}$     $\text{nDCG}_\text{10}$

0.301                         0.750              0.506                 0.331     0.697     0.519

-                                   -                        0.648                 -               -               0.628

-                                   -                        0.670                 -               -               -

7lOur Models

$L=0$, $H=768$      0.198                         0.486              0.424                 0.100     0.263     0.342

$L=12$, $H=768$     0.318                         0.691              0.545                 0.201     0.457     0.504

Retrieval results of dual-encoder models using lightweight query encoders and some baselines. For , the dense retrieval depth is set to $k_D=10000$ and maxP aggregation is applied (cf. <ref>). Our model with $L=0$ uses an embedding-based query-encoder, and the one with $L=12$ uses an attention-based query encoder. The document encoder is a $\text{BERT}_\text{base}$ model ($L=12$, $H=768$) in both cases.

Our research questions and experiments have focused exclusively on interpolation-based re-ranking using dual-encoders and  indexes. However, the most common application of dual-encoders in the field of IR is the use as dense retrieval models; a natural question that occurs is, whether the encoders proposed in <ref> can be used for more efficient dense retrieval.

In <ref>, we present passage and document retrieval results on the MS MARCO corpus. Dense retrievers use a  <cit.> vector index; no interpolation or re-ranking is performed. It is immediately obvious that our models do not achieve competitive results; on the contrary, the embedding-based encoder yields far worse performance than dense retrievers and even , and even the attention-based encoder fails to improve over sparse retrieval.

From these results, we infer that the models we trained are not suitable for dense retrieval. However, we assume that the main reason for this is not the architecture of the query encoder, but instead the following:

* We use a simple in-batch negative sampling strategy <cit.>, which has been shown to be less effective than more involved strategies <cit.>.

* The hardware we use for training the models is limiting w.r.t. the batch size and thus the number of negative samples, i.e., we cannot use a batch size greater than 4.

* We perform validation and early stopping based on re-ranking.

Considering the points above, we expect that our dual-encoder models, including ones with lightweight encoders, could also be used in retrieval settings if the shortcomings of the training setup are addressed, for example, by using more powerful hardware and state-of-the-art training approaches. On the other hand, we argue that the fact that our models perform well in the re-ranking setting (see <ref>) shows that it is both easier and more efficient (in terms of time and resources) to train models to be used with  indexes instead of for dense retrieval.

§.§ Out-of-Domain Performance

$L=0$, $H=768$                       $L=12$, $H=768$

0.477     0. 653                         0.677

0.649     0. 715                         0.777

0.254     0. 282                         0.313

0.808     0. 761                         0.804

0.602     0. 628                         0.674

0.320     0. 331                         0.393

0.691     0. 676                         0.698

0.327     0. 327                         0.330

Zero-shot ranking results on BEIR datasets (nDCG@10) using embedding-based ($L=0$) and attention-based ($L=12$) query encoders. The document encoder is a BERT model with 12 layers and 768-dimensional representations. The sparse retrieval depth is $k_S = 5000$.

In the previous sections, we found that  indexes and lightweight query encoders show good performance in in-domain ranking tasks. This raises the question whether the models generalize well to out-of-domain tasks.

In order to ascertain the out-of-domain capabilities of our models, we evaluate them on a number of test sets from the BEIR benchmark. The evaluation happens in a zero-shot fashion, meaning that we use the same models as before and do not re-train them on the respective datasets. The results are shown in <ref>. It is apparent that the attention-based query encoder yields better results than the embedding-based one in all cases, but the difference varies across datasets. Since both models were trained on MS MARCO, they perform well on the BEIR version of that dataset, as expected; notable differences in performance are observed on  and , however, both models manage to improve the  results. Finally, on ,  and , re-ranking does not lead to a performance improvement, but rather fails to improve or even degrades the results. We assume that the corresponding tasks either require specific in-domain knowledge of the model or would benefit greatly from query-document attention (cross-attention).

§.§ Threats to Validity

In this section, we outline and discuss certain aspects of the experimental evaluation in this article which result in possible threats to the validity of the results.

§.§.§ Performance of

In <ref>, we report the performance of dual-encoder ranking models, along with a cross-attention model (). We found that  performed notably worse, especially when the sparse retrieval depth $k_S$ is increased. This result is unexpected, especially considering the fact that the cross-attention architecture allows for query-document attention.

In addition to the architecture itself, the models differ in the way they are trained:  and  use complex distillation and negative sampling approaches, along with contrastive loss functions (cf. <ref>), while  is trained using simple pairwise loss. It is thus reasonable to assume that the negative sampling approach has a positive impact on the performance. Specifically, the contrastive loss trains the models to identify relevant documents among a very large number of irrelevant documents, while the pairwise loss focuses on re-ranking mostly related documents, which could explain the performance drop for higher retrieval depths.

Furthermore, it is important to note that, even if  performed similarly to the dual-encoder models, the difference in efficiency would remain the same, leaving the claims we make unaffected.

§.§.§ Latency Measurements

As  indexes aim at improving ranking efficiency, we mainly focus on the query processing latency, which is reported in <ref>. As the experiments in the paper have been performed over a longer period of time, there have been slight changes with respect to, for example, hardware or implementations. Consequently, the numbers in latency might not be directly comparable across experiments. Thus, we made sure to make each experiment self-contained, such that these comparisons are not necessary; rather, our results highlight relative latency improvements within each experiment, where all measurements are comparable. In general, one should also keep in mind that latency can be heavily influenced by the way a method is implemented.

§.§.§ Hybrid Retrieval Baselines

In <ref>, we presented, along with the results of our own method, some hybrid retrieval baselines. <Ref> shows the corresponding indexes that we used for the dense retrievers. It is important to note that those are brute-force indexes, i.e., they perform exact $k$NN retrieval. It is thus to be expected that the latency of hybrid retrieval can be further reduced by employing approximate dense retrieval instead; this would likely go hand in hand with a reduction in performance though.

§ CONCLUSION

In this paper, we proposed  indexes, a simple yet effective and efficient look-up-based interpolation method that combines lexical and semantic ranking.  indexes are based on dense dual-encoder models, exploiting the fact that document representations can be pre-processed and stored, providing efficient access in constant time. Using interpolation, we observed increased performance compared to hybrid retrieval. Furthermore, we achieved improvements of up to 75% in memory footprint and query processing latency due to our optimization techniques, sequential coalescing and early stopping.

Moreover, we introduced efficient encoders for dual-encoder models: Embedding-based and lightweight attention-based query encoders can be used to compute query representations significantly faster without compromising performance too much.  document encoders dynamically remove irrelevant tokens from input documents prior to indexing, reducing the document encoding latency by up to 50% and thus making index maintenance much faster.

Our method solely requires CPU computations for ranking, completely eliminating the need for expensive GPU-accelerated re-ranking.

This work is supported by the European Union – Horizon 2020 Program under the scheme “INFRAIA-01-2018-2019 – Integrating Activities for Advanced Communities”, Grant Agreement n.871042, “SoBigData++: European Integrated Infrastructure for Social Mining and Big Data Analytics” (http://www.sobigdata.eu).

This work is supported in part by the Science and Engineering Research Board, Department of Science and Technology, Government of India, under Project SRG/2022/001548 and Microsoft Academic Partnership Grant 2023 Agreement No. 7581365. Koustav Rudra is a recipient of the DST-INSPIRE Faculty Fellowship [DST/INSPIRE/04/2021/003055] in the year 2021 under Engineering Sciences.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Akkalyoncu Yilmaz et al(2019)]
authorpersonZeynep Akkalyoncu Yilmaz, personWei Yang, personHaotian Zhang, and personJimmy Lin. year2019.
Cross-Domain Modeling of Sentence-Level Evidence for Document Retrieval. In booktitleProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). publisherAssociation for Computational Linguistics, addressHong Kong, China, pages3490–3496.

[Askari et al(2023)]
authorpersonArian Askari, personAmin Abolghasemi, personGabriella Pasi, personWessel Kraaij, and personSuzan Verberne. year2023.
titleInjecting the BM25 Score as Text Improves BERT-Based Re-rankers.

[Broder et al(2003)]
authorpersonAndrei Z. Broder, personDavid Carmel, personMichael Herscovici, personAya Soffer, and personJason Zien. year2003.
Efficient Query Evaluation Using a Two-Level Retrieval Process. In booktitleProceedings of the Twelfth International Conference on Information and Knowledge Management (New Orleans, LA, USA) (seriesCIKM '03). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages426–434.

[Bruch et al(2023)]
authorpersonSebastian Bruch, personSiyu Gai, and personAmir Ingber. year2023.
An Analysis of Fusion Functions for Hybrid Retrieval.
journalACM Trans. Inf. Syst. volume42, number1, Article articleno20 (dateaug year2023), numpages35 pages.

[Chang et al(2020)]
authorpersonWei-Cheng Chang, personFelix X. Yu, personYin-Wen Chang, personYiming Yang, and personSanjiv Kumar. year2020.
Pre-training Tasks for Embedding-based Large-scale Retrieval. In booktitleInternational Conference on Learning Representations.

[Chen et al(2021)]
authorpersonXiaoyang Chen, personKai Hui, personBen He, personXianpei Han, personLe Sun, and personZheng Ye. year2021.
Co-BERT: A Context-Aware BERT Retrieval Model Incorporating Local and Query-specific Context.
journalarXiv preprint arXiv:2104.08523 (year2021).

[Choi et al(2022)]
authorpersonEunseong Choi, personSunkyung Lee, personMinjin Choi, personHyeseon Ko, personYoung-In Song, and personJongwuk Lee. year2022.
SpaDE: Improving Sparse Representations Using a Dual Document Encoder for First-Stage Retrieval. In booktitleProceedings of the 31st ACM International Conference on Information & Knowledge Management (Atlanta, GA, USA) (seriesCIKM '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages272–282.

[Cohen et al(2022)]
authorpersonNachshon Cohen, personAmit Portnoy, personBesnik Fetahu, and personAmir Ingber. year2022.
SDR: Efficient Neural Re-ranking using Succinct Document Representation. In booktitleProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). publisherAssociation for Computational Linguistics, addressDublin, Ireland, pages6624–6637.

[Craswell et al(2021)]
authorpersonNick Craswell, personBhaskar Mitra, personEmine Yilmaz, personDaniel Campos, personEllen M. Voorhees, and personIan Soboroff. year2021.
TREC Deep Learning Track: Reusable Test Collections in the Large Data Regime. In booktitleProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, Canada) (seriesSIGIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2369–2375.

[Dai and Callan(2019a)]
authorpersonZhuyun Dai and personJamie Callan. year2019a.
Deeper Text Understanding for IR with Contextual Neural Language Modeling. In booktitleProceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (Paris, France) (seriesSIGIR'19). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages985–988.

[Dai and Callan(2019b)]
authorpersonZhuyun Dai and personJamie Callan. year2019b.
An Evaluation of Weakly-Supervised DeepCT in the TREC 2019 Deep Learning Track. In booktitleTREC.

[Dai and Callan(2020a)]
authorpersonZhuyun Dai and personJamie Callan. year2020a.
Context-Aware Document Term Weighting for Ad-Hoc Search. In booktitleProceedings of The Web Conference 2020 (Taipei, Taiwan) (seriesWWW '20). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1897–1907.

[Dai and Callan(2020b)]
authorpersonZhuyun Dai and personJamie Callan. year2020b.
Context-Aware Term Weighting For First Stage Passage Retrieval. In booktitleProceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, China) (seriesSIGIR '20). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1533–1536.

[Devlin et al(2019)]
authorpersonJacob Devlin, personMing-Wei Chang, personKenton Lee, and personKristina Toutanova. year2019.
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In booktitleProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). publisherAssociation for Computational Linguistics, addressMinneapolis, Minnesota, pages4171–4186.

[Dong et al(2022)]
authorpersonSibo Dong, personJustin Goldstein, and personGrace Hui Yang. year2022.
SEINE: SEgment-based Indexing for NEural information retrieval.

[Fagin et al(2001)]
authorpersonRonald Fagin, personAmnon Lotem, and personMoni Naor. year2001.
Optimal Aggregation Algorithms for Middleware. In booktitleProceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Santa Barbara, California, USA) (seriesPODS '01). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages102–113.

[Fan et al(2023)]
authorpersonZhen Fan, personLuyu Gao, personRohan Jha, and personJamie Callan. year2023.
COILcr: Efficient Semantic Matching in Contextualized Exact Match Retrieval. In booktitleAdvances in Information Retrieval, editorpersonJaap Kamps, personLorraine Goeuriot, personFabio Crestani, personMaria Maistro, personHideo Joho, personBrian Davis, personCathal Gurrin, personUdo Kruschwitz, and personAnnalina Caputo (Eds.). publisherSpringer Nature Switzerland, addressCham, pages298–312.

[Formal et al(2021)]
authorpersonThibault Formal, personBenjamin Piwowarski, and personStéphane Clinchant. year2021.
SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking. In booktitleProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (seriesSIGIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2288–2292.

authorpersonLuke Gallagher. year2019.
titlePairwise t-test on TREC Run Files.

[Gao and Callan(2021)]
authorpersonLuyu Gao and personJamie Callan. year2021.
Condenser: a Pre-training Architecture for Dense Retrieval. In booktitleProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. publisherAssociation for Computational Linguistics, addressOnline and Punta Cana, Dominican Republic, pages981–993.

[Gao and Callan(2022)]
authorpersonLuyu Gao and personJamie Callan. year2022.
Unsupervised Corpus Aware Language Model Pre-training for Dense Passage Retrieval. In booktitleProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). publisherAssociation for Computational Linguistics, addressDublin, Ireland, pages2843–2853.

[Gao et al(2021a)]
authorpersonLuyu Gao, personZhuyun Dai, and personJamie Callan. year2021a.
COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List. In booktitleProceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. publisherAssociation for Computational Linguistics, addressOnline, pages3030–3042.

[Gao et al(2021b)]
authorpersonLuyu Gao, personZhuyun Dai, personTongfei Chen, personZhen Fan, personBenjamin Van Durme, and personJamie Callan. year2021b.
Complement Lexical Retrieval Model with Semantic Residual Embeddings. In booktitleAdvances in Information Retrieval, editorpersonDjoerd Hiemstra, personMarie-Francine Moens, personJosiane Mothe, personRaffaele Perego, personMartin Potthast, and personFabrizio Sebastiani (Eds.). publisherSpringer International Publishing, addressCham, pages146–160.

[Goyal et al(2020)]
authorpersonSaurabh Goyal, personAnamitra Roy Choudhury, personSaurabh M. Raje, personVenkatesan T. Chakaravarthy, personYogish Sabharwal, and personAshish Verma. year2020.
PoWER-BERT: Accelerating BERT Inference via Progressive Word-Vector Elimination. In booktitleProceedings of the 37th International Conference on Machine Learning (seriesICML'20). publisherJMLR.org, Article articleno346, numpages10 pages.

[Gupta et al(2018)]
authorpersonVishal Gupta, personManoj Chinnakotla, and personManish Shrivastava. year2018.
Retrieve and Re-rank: A Simple and Effective IR Approach to Simple Question Answering over Knowledge Graphs. In booktitleProceedings of the First Workshop on Fact Extraction and VERification (FEVER). publisherAssociation for Computational Linguistics, addressBrussels, Belgium, pages22–27.

[Hofstätter et al(2022)]
authorpersonSebastian Hofstätter, personOmar Khattab, personSophia Althammer, personMete Sertkan, and personAllan Hanbury. year2022.
Introducing Neural Bag of Whole-Words with ColBERTer: Contextualized Late Interactions Using Enhanced Reduction. In booktitleProceedings of the 31st ACM International Conference on Information & Knowledge Management (Atlanta, GA, USA) (seriesCIKM '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages737–747.

[Hofstätter et al(2021a)]
authorpersonSebastian Hofstätter, personSheng-Chieh Lin, personJheng-Hong Yang, personJimmy Lin, and personAllan Hanbury. year2021a.
booktitleEfficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling.
publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages113–122.

[Hofstätter et al(2021b)]
authorpersonSebastian Hofstätter, personBhaskar Mitra, personHamed Zamani, personNick Craswell, and personAllan Hanbury. year2021b.
Intra-Document Cascading: Learning to Select Passages for Neural Document Ranking. In booktitleProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, Canada) (seriesSIGIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1349–1358.

[Hofstätter et al(2020)]
authorpersonSebastian Hofstätter, personMarkus Zlabinger, and personAllan Hanbury. year2020.
Interpretable & Time-Budget-Constrained Contextualization for Re-Ranking. In booktitleProc. of ECAI.

[Hofstätter et al(2022)]
authorpersonSebastian Hofstätter, personNick Craswell, personBhaskar Mitra, personHamed Zamani, and personAllan Hanbury. year2022.
titleAre We There Yet? A Decision Framework for Replacing Term Based Retrieval with Dense Retrieval Systems.

[Jang et al(2021)]
authorpersonKyoung-Rok Jang, personJunmo Kang, personGiwon Hong, personSung-Hyon Myaeng, personJoohee Park, personTaewon Yoon, and personHeecheol Seo. year2021.
Ultra-High Dimensional Sparse Representations with Binarization for Efficient Text Retrieval. In booktitleProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. publisherAssociation for Computational Linguistics, addressOnline and Punta Cana, Dominican Republic, pages1016–1029.

[Johnson et al(2021)]
authorpersonJeff Johnson, personMatthijs Douze, and personHervé Jégou. year2021.
Billion-Scale Similarity Search with GPUs.
journalIEEE Transactions on Big Data volume7, number3 (year2021), pages535–547.

[Jung et al(2022)]
authorpersonEuna Jung, personJaekeol Choi, and personWonjong Rhee. year2022.
Semi-Siamese Bi-Encoder Neural Ranking Model Using Lightweight Fine-Tuning. In booktitleProceedings of the ACM Web Conference 2022 (Virtual Event, Lyon, France) (seriesWWW '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages502–511.

[Karpukhin et al(2020)]
authorpersonVladimir Karpukhin, personBarlas Oguz, personSewon Min, personPatrick Lewis, personLedell Wu, personSergey Edunov, personDanqi Chen, and personWen-tau Yih. year2020.
Dense Passage Retrieval for Open-Domain Question Answering. In booktitleProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). publisherAssociation for Computational Linguistics, addressOnline, pages6769–6781.

[Khattab and Zaharia(2020)]
authorpersonOmar Khattab and personMatei Zaharia. year2020.
booktitleColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT.
publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages39–48.

[Kim et al(2023)]
authorpersonSeungyeon Kim, personAnkit Singh Rawat, personManzil Zaheer, personSadeep Jayasumana, personVeeranjaneyulu Sadhanala, personWittawat Jitkrittum, personAditya Krishna Menon, personRob Fergus, and personSanjiv Kumar. year2023.
titleEmbedDistill: A Geometric Knowledge Distillation for Information Retrieval.

[Lafferty and Zhai(2001)]
authorpersonJohn Lafferty and personChengxiang Zhai. year2001.
Document Language Models, Query Models, and Risk Minimization for Information Retrieval. In booktitleProceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (seriesSIGIR '01). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages111–119.

[Lassance and Clinchant(2022)]
authorpersonCarlos Lassance and personStéphane Clinchant. year2022.
An Efficiency Study for SPLADE Models. In booktitleProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval (Madrid, Spain) (seriesSIGIR '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2220–2226.

[Lassance et al(2023)]
authorpersonCarlos Lassance, personHervé Déjean, and personStéphane Clinchant. year2023.
titleAn Experimental Study on Pretraining Transformers from Scratch for IR.

[Lassance et al(2022)]
authorpersonCarlos Lassance, personMaroua Maachou, personJoohee Park, and personStéphane Clinchant. year2022.
Learned Token Pruning in Contextualized Late Interaction over BERT (ColBERT). In booktitleProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval (Madrid, Spain) (seriesSIGIR '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2232–2236.

[Lavrenko and Croft(2001)]
authorpersonVictor Lavrenko and personW. Bruce Croft. year2001.
Relevance Based Language Models. In booktitleProceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (seriesSIGIR '01). publisherACM, addressNew York, NY, USA, pages120–127.

[Leonhardt et al(2020)]
authorpersonJurek Leonhardt, personAvishek Anand, and personMegha Khosla. year2020.
Boilerplate Removal Using a Neural Sequence Labeling Model. In booktitleCompanion Proceedings of the Web Conference 2020 (seriesWWW '20). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages226–229.

[Leonhardt et al(2023)]
authorpersonJurek Leonhardt, personKoustav Rudra, and personAvishek Anand. year2023.
Extractive Explanations for Interpretable Text Ranking.
journalACM Trans. Inf. Syst. volume41, number4, Article articleno88 (datemar year2023), numpages31 pages.

[Leonhardt et al(2022)]
authorpersonJurek Leonhardt, personKoustav Rudra, personMegha Khosla, personAbhijit Anand, and personAvishek Anand. year2022.
Efficient Neural Ranking Using Forward Indexes. In booktitleProceedings of the ACM Web Conference 2022 (Virtual Event, Lyon, France) (seriesWWW '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages266–276.

[Li et al(2020)]
authorpersonCanjia Li, personAndrew Yates, personSean MacAvaney, personBen He, and personYingfei Sun. year2020.
titlePARADE: Passage Representation Aggregation for Document Reranking.

[Li and Gaussier(2021)]
authorpersonMinghan Li and personEric Gaussier. year2021.
KeyBLD: Selecting Key Blocks with Local Pre-Ranking for Long Document Information Retrieval. In booktitleProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, Canada) (seriesSIGIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2207–2211.

[Li et al(2022)]
authorpersonMinghan Li, personSheng-Chieh Lin, personBarlas Oguz, personAsish Ghoshal, personJimmy Lin, personYashar Mehdad, personWen-tau Yih, and personXilun Chen. year2022.
titleCITADEL: Conditional Token Interaction via Dynamic Lexical Routing for Efficient and Effective Multi-Vector Retrieval.

[Li et al(2023)]
authorpersonMinghan Li, personDiana Nicoleta Popa, personJohan Chagnon, personYagmur Gizem Cinar, and personEric Gaussier. year2023.
The Power of Selecting Key Blocks with Local Pre-Ranking for Long Document Information Retrieval.
journalACM Trans. Inf. Syst. volume41, number3, Article articleno73 (datefeb year2023), numpages35 pages.

[Lin et al(2021a)]
authorpersonJimmy Lin, personXueguang Ma, personSheng-Chieh Lin, personJheng-Hong Yang, personRonak Pradeep, and personRodrigo Nogueira. year2021a.
booktitlePyserini: A Python Toolkit for Reproducible Information Retrieval Research with Sparse and Dense Representations.
publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2356–2362.

[Lin et al(2023)]
authorpersonSheng-Chieh Lin, personMinghan Li, and personJimmy Lin. year2023.
Aggretriever: A Simple Approach to Aggregate Textual Representations for Robust Dense Passage Retrieval.
journalTransactions of the Association for Computational Linguistics  volume11 (year2023), pages436–452.

[Lin et al(2021b)]
authorpersonSheng-Chieh Lin, personJheng-Hong Yang, and personJimmy Lin. year2021b.
In-Batch Negatives for Knowledge Distillation with Tightly-Coupled Teachers for Dense Retrieval. In booktitleProceedings of the 6th Workshop on Representation Learning for NLP (RepL4NLP-2021). publisherAssociation for Computational Linguistics, addressOnline, pages163–173.

[Lin et al(2021c)]
authorpersonSheng-Chieh Lin, personJheng-Hong Yang, and personJimmy Lin. year2021c.
In-Batch Negatives for Knowledge Distillation with Tightly-Coupled Teachers for Dense Retrieval. In booktitleProceedings of the 6th Workshop on Representation Learning for NLP (RepL4NLP-2021). publisherAssociation for Computational Linguistics, addressOnline, pages163–173.

[Lindgren et al(2021)]
authorpersonErik Lindgren, personSashank Reddi, personRuiqi Guo, and personSanjiv Kumar. year2021.
Efficient Training of Retrieval Models using Negative Cache. In booktitleAdvances in Neural Information Processing Systems, editorpersonM. Ranzato, personA. Beygelzimer, personY. Dauphin, personP.S. Liang, and personJ. Wortman Vaughan (Eds.), Vol. volume34. publisherCurran Associates, Inc., pages4134–4146.

[Liu et al(2022)]
authorpersonChang Liu, personChongyang Tao, personXiubo Geng, personTao Shen, personDongyan Zhao, personCan Xu, personBinxing Jiao, and personDaxin Jiang. year2022.
titleAdam: Dense Retrieval Distillation with Adaptive Dark Examples.

[Luan et al(2021)]
authorpersonYi Luan, personJacob Eisenstein, personKristina Toutanova, and personMichael Collins. year2021.
Sparse, Dense, and Attentional Representations for Text Retrieval.
journalTransactions of the Association for Computational Linguistics  volume9 (year2021), pages329–345.

[Luxenburger et al(2008)]
authorpersonJulia Luxenburger, personShady Elbassuoni, and personGerhard Weikum. year2008.
Matching Task Profiles and User Needs in Personalized Web Search. In booktitleProceedings of the 17th ACM Conference on Information and Knowledge Management (seriesCIKM '08). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages689–698.

[MacAvaney et al(2020)]
authorpersonSean MacAvaney, personFranco Maria Nardini, personRaffaele Perego, personNicola Tonellotto, personNazli Goharian, and personOphir Frieder. year2020.
booktitleExpansion via Prediction of Importance with Contextualization.
publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1573–1576.

[MacAvaney et al(2019)]
authorpersonSean MacAvaney, personAndrew Yates, personArman Cohan, and personNazli Goharian. year2019.
CEDR: Contextualized Embeddings for Document Ranking. In booktitleProceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (seriesSIGIR'19). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1101–1104.

[Mackenzie et al(2020)]
authorpersonJoel Mackenzie, personZhuyun Dai, personLuke Gallagher, and personJamie Callan. year2020.
Efficiency Implications of Term Weighting for Passage Retrieval. In booktitleProceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, China) (seriesSIGIR '20). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1821–1824.

[Malkov and Yashunin(2020)]
authorpersonYu A. Malkov and personD. A. Yashunin. year2020.
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.
journalIEEE Transactions on Pattern Analysis and Machine Intelligence volume42, number4 (year2020), pages824–836.

[Mallia et al(2021)]
authorpersonAntonio Mallia, personOmar Khattab, personTorsten Suel, and personNicola Tonellotto. year2021.
booktitleLearning Passage Impacts for Inverted Indexes.
publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1723–1727.

authorpersonPascal Massart. year1990.
The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality.
journalThe annals of Probability (year1990), pages1269–1283.

[Mitra et al(2016)]
authorpersonBhaskar Mitra, personEric Nalisnick, personNick Craswell, and personRich Caruana. year2016.
titleA Dual Embedding Space Model for Document Ranking.

[Mitra et al(2019)]
authorpersonBhaskar Mitra, personCorby Rosset, personDavid Hawking, personNick Craswell, personFernando Diaz, and personEmine Yilmaz. year2019.
Incorporating query term independence assumption for efficient retrieval and ranking using deep neural networks.
journalarXiv preprint arXiv:1907.03693 (year2019).

[Nguyen et al(2016)]
authorpersonTri Nguyen, personMir Rosenberg, personXia Song, personJianfeng Gao, personSaurabh Tiwary, personRangan Majumder, and personLi Deng. year2016.
MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. In booktitleProceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, December 9, 2016 (seriesCEUR Workshop Proceedings, Vol. volume1773), editorpersonTarek Richard Besold, personAntoine Bordes, personArtur S. d'Avila Garcez, and personGreg Wayne (Eds.). publisherCEUR-WS.org.

[Ni et al(2021)]
authorpersonJianmo Ni, personChen Qu, personJing Lu, personZhuyun Dai, personGustavo Hernández Ábrego, personJi Ma, personVincent Y. Zhao, personYi Luan, personKeith B. Hall, personMing-Wei Chang, and personYinfei Yang. year2021.
titleLarge Dual Encoders Are Generalizable Retrievers.

[Nogueira et al(2019)]
authorpersonRodrigo Nogueira, personJimmy Lin, and personAI Epistemic. year2019.
From doc2query to docTTTTTquery.
journalOnline preprint (year2019).

[Prakash et al(2021)]
authorpersonPrafull Prakash, personJulian Killingback, and personHamed Zamani. year2021.
Learning Robust Dense Retrieval Models from Incomplete Relevance Labels. In booktitleProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, Canada) (seriesSIGIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1728–1732.

[Rau and Kamps(2022)]
authorpersonDavid Rau and personJaap Kamps. year2022.
The Role of Complex NLP in Transformers for Text Ranking. In booktitleProceedings of the 2022 ACM SIGIR International Conference on Theory of Information Retrieval (Madrid, Spain) (seriesICTIR '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages153–160.

[Robertson and Zaragoza(2009)]
authorpersonStephen Robertson and personHugo Zaragoza. year2009.
The Probabilistic Relevance Framework: BM25 and Beyond.
journalFoundations and Trends® in Information Retrieval volume3, number4 (year2009), pages333–389.

[Robertson et al(1995)]
authorpersonStephen E Robertson, personSteve Walker, personSusan Jones, personMicheline M Hancock-Beaulieu, personMike Gatford, et al year1995.
Okapi at TREC-3.
journalNist Special Publication Sp  volume109 (year1995), pages109.

[Rudra and Anand(2020)]
authorpersonKoustav Rudra and personAvishek Anand. year2020.
Distant Supervision in BERT-Based Adhoc Document Retrieval. In booktitleProceedings of the 29th ACM International Conference on Information & Knowledge Management (seriesCIKM '20). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2197–2200.

[Rudra et al(2021)]
authorpersonKoustav Rudra, personZeon Trevor Fernando, and personAvishek Anand. year2021.
titleAn In-depth Analysis of Passage-Level Label Transfer for Contextual Document Ranking.

[Scells et al(2022)]
authorpersonHarrisen Scells, personShengyao Zhuang, and personGuido Zuccon. year2022.
Reduce, Reuse, Recycle: Green Information Retrieval Research. In booktitleProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval (Madrid, Spain) (seriesSIGIR '22). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages2825–2837.

authorpersonR. F. Simmons. year1965.
Answering English Questions by Computer: A Survey.
journalCommun. ACM volume8, number1 (datejan year1965), pages53–70.

[Thakur et al(2021)]
authorpersonNandan Thakur, personNils Reimers, personAndreas Rücklé, personAbhishek Srivastava, and personIryna Gurevych. year2021.
BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In booktitleThirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2).

[Theobald et al(2004)]
authorpersonMartin Theobald, personGerhard Weikum, and personRalf Schenkel. year2004.
Top-k Query Evaluation with Probabilistic Guarantees. In booktitleProceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (seriesVLDB '04). publisherVLDB Endowment, pages648–659.

[Turc et al(2019)]
authorpersonIulia Turc, personMing-Wei Chang, personKenton Lee, and personKristina Toutanova. year2019.
Well-Read Students Learn Better: The Impact of Student Initialization on Knowledge Distillation.
journalCoRR  volumeabs/1908.08962 (year2019).

[Turtle and Flood(1995)]
authorpersonHoward Turtle and personJames Flood. year1995.
Query Evaluation: Strategies and Optimizations.
journalInf. Process. Manage. volume31, number6 (datenov year1995), pages831–850.

[Vaswani et al(2017)]
authorpersonAshish Vaswani, personNoam Shazeer, personNiki Parmar, personJakob Uszkoreit, personLlion Jones, personAidan N. Gomez, personŁukasz Kaiser, and personIllia Polosukhin. year2017.
Attention is All You Need. In booktitleProceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (seriesNIPS'17). publisherCurran Associates Inc., addressRed Hook, NY, USA, pages6000–6010.

[Wang et al(2022a)]
authorpersonJue Wang, personKe Chen, personGang Chen, personLidan Shou, and personJulian McAuley. year2022a.
SkipBERT: Efficient Inference with Shallow Layer Skipping. In booktitleProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). publisherAssociation for Computational Linguistics, addressDublin, Ireland, pages7287–7301.

[Wang et al(2022b)]
authorpersonLiang Wang, personNan Yang, personXiaolong Huang, personBinxing Jiao, personLinjun Yang, personDaxin Jiang, personRangan Majumder, and personFuru Wei. year2022b.
titleText Embeddings by Weakly-Supervised Contrastive Pre-training.

[Wang et al(2021)]
authorpersonShuai Wang, personShengyao Zhuang, and personGuido Zuccon. year2021.
BERT-Based Dense Retrievers Require Interpolation with BM25 for Effective Passage Retrieval. In booktitleProceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval (Virtual Event, Canada) (seriesICTIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages317–324.

[Wei and Croft(2006)]
authorpersonXing Wei and personW. Bruce Croft. year2006.
LDA-Based Document Models for Ad-Hoc Retrieval. In booktitleProceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (seriesSIGIR '06). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages178–185.

[Xin et al(2020)]
authorpersonJi Xin, personRaphael Tang, personJaejun Lee, personYaoliang Yu, and personJimmy Lin. year2020.
DeeBERT: Dynamic Early Exiting for Accelerating BERT Inference. In booktitleProceedings of the 58th Annual Meeting of the Association for Computational Linguistics. publisherAssociation for Computational Linguistics, addressOnline, pages2246–2251.

[Xiong et al(2021)]
authorpersonLee Xiong, personChenyan Xiong, personYe Li, personKwok-Fung Tang, personJialin Liu, personPaul N. Bennett, personJunaid Ahmed, and personArnold Overwijk. year2021.
Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In booktitleInternational Conference on Learning Representations.

[Yang et al(2022)]
authorpersonYingrui Yang, personYifan Qiao, and personTao Yang. year2022.
Compact Token Representations with Contextual Quantization for Efficient Document Re-ranking. In booktitleProceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). publisherAssociation for Computational Linguistics, addressDublin, Ireland, pages695–707.

[Zhan et al(2021)]
authorpersonJingtao Zhan, personJiaxin Mao, personYiqun Liu, personJiafeng Guo, personMin Zhang, and personShaoping Ma. year2021.
booktitleOptimizing Dense Retrieval Model Training with Hard Negatives.
publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1503–1512.

[Zhang et al(2022)]
authorpersonKai Zhang, personChongyang Tao, personTao Shen, personCan Xu, personXiubo Geng, personBinxing Jiao, and personDaxin Jiang. year2022.
titleLED: Lexicon-Enlightened Dense Retriever for Large-Scale Retrieval.

[Zhou et al(2022)]
authorpersonYucheng Zhou, personTao Shen, personXiubo Geng, personChongyang Tao, personGuodong Long, personCan Xu, and personDaxin Jiang. year2022.
titleFine-Grained Distillation for Long Document Retrieval.

[Zhuang and Zuccon(2021a)]
authorpersonShengyao Zhuang and personGuido Zuccon. year2021a.
Fast passage re-ranking with contextualized exact term matching and efficient passage expansion.
journalarXiv preprint arXiv:2108.08513 (year2021).

[Zhuang and Zuccon(2021b)]
authorpersonShengyao Zhuang and personGuido Zuccon. year2021b.
TILDE: Term Independent Likelihood MoDEl for Passage Re-Ranking. In booktitleProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (Virtual Event, Canada) (seriesSIGIR '21). publisherAssociation for Computing Machinery, addressNew York, NY, USA, pages1483–1492.