


\section{Deep Impact Framework}

\boldparagraph{Document Expansion.}
In our approach, we leverage \textsf{DocT5Query}\ document expansion to enrich the original document collection with expansion terms. As noted by \citet{doc2query}, document expansion can be seen as a two-fold approach. By adding terms that are already part of the document, it rewrites their frequencies, similar to \textsf{DeepCT}\xspace. Furthermore, it injects into the passage new terms, originally not part of the document, in order to address the term mismatch problem. We refer to the two as \textit{Rewrite} and \textit{Inject}, respectively. 
Table~\ref{tab:dtfq} summarizes 
the effect of \textsf{DocT5Query}\ when applied to the MSMARCO passage ranking collection, and isolates the two contributions.
While \textit{Rewrite} alone
achieves stronger MRR@10 than \textit{Inject}, the latter achieves higher recall. Using both significantly outperforms either one on both measures. Indeed, \textit{Inject} is important for capturing additional results, but \textit{Rewrite} is needed to then properly weight the injected terms. However, the comparison of \textit{Rewrite} vs. \textsf{DeepCT}\xspace indicates that \textsf{DocT5Query}\ is still sub-optimal in determining the right frequencies, and resulting impact scores, for the terms.

This motivates our approach, \textsf{DeepImpact}, where we first use the \textit{Inject} step of \textsf{DocT5Query}\ to add new terms, and then directly learn the right impact scores for both old and newly injected terms.

\begin{table}[h]
\renewcommand{\arraystretch}{0.7}
\caption{Different contributions to effectiveness metrics of \textsf{DocT5Query}\ on the MSMARCO passage ranking collection.}
\centering
\begin{tabular}{l ccccc}
\toprule
& \multirow{2}{*}{\textsf{BM25}\xspace} & \multirow{2}{*}{\textsf{DeepCT}\xspace} & \multicolumn{3}{c}{\textsf{DocT5Query}} \\
\cmidrule(lr){4-6}
& &  &\multicolumn{1}{c}{Cumulative} & \multicolumn{1}{c}{\textit{Rewrite}} & \multicolumn{1}{c}{\textit{Inject}}   \\
\midrule
MRR@10 & 0.188 & 0.244 & 0.278 & 0.215 & 0.194 \\ 
Recall & 0.858 & 0.910 & 0.947 & 0.878 & 0.912 \\ 
\bottomrule
\end{tabular}
\label{tab:dtfq}
\end{table}

\boldparagraph{Neural Network Architecture.}
\looseness -1 The overall architecture of the \textsf{DeepImpact}\ neural network is depicted in Figure~\ref{fig:architecture}. \textsf{DeepImpact}{} feeds a contextual LM encoder the original document terms (in white) and the injected expansion terms (in gray), separating both by a \texttt{[SEP]} separator token to distinguish both contexts. The LM encoder produces an embedding for each input term. The first occurrence of each \textit{unique} term is provided as input to the impact score encoder, which is a two-layer MLP with ReLU activations. This produces a single-value score for each unique term in the document, representing its impact. Given a query $q$, we model the score of document $d$ as simply the sum of impacts for the intersection of terms in $q$ and $d$.

\begin{figure}
\includegraphics[width=0.7\linewidth]{arch3.pdf}
\caption{Neural network architecture of \textsf{DeepImpact}.}\label{fig:architecture}

\vspace{-3mm}
\end{figure}

\boldparagraph{Network Training.}
We train our model using triples sampled from the official MS-MARCO training dataset, consisting of a query, a relevant passage, and a presumed non-relevant passage per sample. We expand each passage using the \textsf{DocT5Query}\ as discussed. 
The model converts each document into a list of scores, corresponding to the document terms matching the query. These scores are then summed up, obtaining an accumulated query-document score. For each triple, two scores for the corresponding two documents are computed. The model is optimized via pairwise softmax cross-entropy loss over the computed scores of the documents.  We use BERT-base as the contextualized language model. Max input text length was set to 160 tokens. Losses are back-propagated through the whole \textsf{DeepImpact}\ neural model with a learning rate of $3 \times 10^{-6}$ with the Adam optimizer. We used batches of 32 triples and train for 100,000 iterations.

\boldparagraph{Impact Scores Computation.}
Following the training phase, \textsf{DeepImpact}\ can leverage the learned term-weighting scheme to predict the semantic importance of each token of the documents without the need
for queries. Each document is represented as a list of term-score pairs, which are converted into an inverted index. The index can then be deployed and searched as usual for efficient query processing. We infer the scores using three digits of precision, and we do not perform any scaling.

\boldparagraph{Quantization and Query Processing.}
In our approach we predict real-valued document-term scores, also called impact scores, that we store in the inverted index. Since storing a floating point value per posting would blow up the space requirements of the inverted index, we decided to store impacts in a quantized form. The quantized impact scores belong to the range of $[1,2^b-1]$, where $b$ is the number of bits used to store each value. We experimented with $b = 8$ using linear quantization, and did not notice any loss in precision w.r.t. the original scores. Since we quantized all the scores in the index in the same way, to compute a query-document score at query processing we can just sum up all the quantized scores of the document terms matching the query. %

\section{Experimental Results}
In this section, we analyze the performance of the proposed method with an extensive experimental evaluation in a realistic and reproducible setting, using state-of-the-art baselines and a standard test collection and query logs.

\boldparagraph{Hardware.}
To evaluate the latency, we use a single core of a machine
with four Intel Xeon Platinum 8268 CPUs and 369 GB of RAM, running Linux 4.18.  
To run \textsf{ColBERT}\xspace\ a GPU is required, and we used an NVIDIA RTX8000 with 48GB of memory.

\boldparagraph{Dataset and query logs.}
We conduct our experiments on the MSMARCO passage ranking \cite{msmarco} dataset.
To evaluate query processing effectiveness and efficiency, we compare with existing methods using the \textsf{MSMARCO Dev Queries}\xspace{},\footnote{We have made a submission to the official leaderboard and obtained an MRR@10 of 0.318 on the ``eval'' queries.} and we test all methods on the \textsf{TREC 2019}\xspace{}~\cite{trec2019} and \textsf{TREC 2020}\xspace{}~\cite{trec2020} queries from the TREC Deep Learning passage ranking track.

\boldparagraph{Baselines.}
We perform two different sets of experiments. Our initial experiment aims at comparing the performance of \textsf{DeepImpact}\ as a first-stage ranker, processing queries on inverted indexes but without complex reranking. In this experiment we compare our proposed \textsf{DeepImpact}\ with the classical \textsf{BM25}\xspace\ relevance model over the unmodified collection, and state-of-the-art solutions dealing with inverted indexes, namely \textsf{DeepCT}\xspace, and \textsf{BM25}\xspace\ over a collection expanded with \textsf{DocT5Query}.
We do not compare with \textsf{DeepCT}\xspace\ over the collection expanded with \textsf{DocT5Query}, since that would involve training a new \textsf{DeepCT}\xspace{} model from scratch to learn how to weigh expanded documents.
Our second set of experiments compares \textsf{DeepImpact}\ in a re-ranking setting. First, the top 1000 documents retrieved by \textsf{DeepImpact}\ are re-ranked by \textsf{EPIC}\ and \textsf{ColBERT}\xspace and compared to \textsf{ColBERT}\xspace end-to-end (E2E) where the candidates are generated using ANN search. Finally, we look at first-stage recall and re-ranking-stage MRR@10 when applying \textsf{ColBERT}\xspace\ at several first-stage cutoffs to different candidate generation methods.

\boldparagraph{Implementations.}
We use Anserini~\cite{anserini} to generate the inverted indexes of the collections. We then export the Anserini indexes using the CIFF common index file format \cite{ciff}, and process them with PISA~\cite{pisa} using the MaxScore query processing algorithm~\cite{maxscore}. 
We use the \textsf{BM25}\xspace{} scoring method provided by Anserini.
For \textsf{DeepCT}\xspace{}, we  used the source code and data\footnote{\url{https://github.com/jmmackenzie/term-weighting-efficiency}} provided by \citet{deepct-efficiency}.
For \textsf{DocT5Query}{} we use the predicted queries available online\footnote{https://github.com/castorini/docTTTTTquery}, using 40 concatenated predictions for each passage in the corpus, as recommended by \citet{docTTTTTquery}.
We use the \textsf{EPIC}{} implementation in OpenNIR~\cite{onir} and the official pretrained model\footnote{\url{https://github.com/Georgetown-IR-Lab/epic-neural-ir}}.
We use the \textsf{ColBERT}\xspace{} implementation\footnote{\url{https://github.com/stanford-futuredata/ColBERT}} provided by \citet{colbert}, trained for 200k iterations.
Both training and indexing tasks of \textsf{DeepImpact}\ are implemented in Python. After the quantization step, the documents are indexed directly by PISA.  
Query processing efficiency is measured using PISA for all baselines. Query processing is performed using MaxScore to retrieve the top $1000$ documents. %
Our source code is publicly available\footnote{\url{https://github.com/DI4IR/SIGIR2021}}. 

\boldparagraph{Metrics.}
To measure effectiveness, we use the oﬃcial metrics for each query set, mean reciprocal rank (MRR@10) for MSMARCO queries, and normalised discounted cumulative gain (NDCG@10) as well as mean average precision (MAP) for TREC queries, following~\cite{hofstatter2020local}. We also report recall  on the first stage and MRR@10 on the re-ranking stage at different cutoff values. Finally, we compute the mean response time (MRT) for every query processing strategy, in ms.
We conduct Bonferroni corrected pairwise t-tests, and report significance with $p < 0.05$.

\boldparagraph{Overall comparison.}
Our first experiment aims to show the early-stage effectiveness improvements that \textsf{DeepImpact}\ achieves when compared to prior work.
The results are presented in Table~\ref{tab:overall}, which shows effectiveness and efficiency for the three query logs on MS MARCO. We retrieve the top $1000$ documents for each query, without re-ranking, and report the values of NDCG@10, MRR@10, and MAP, as well as MRT. 

\textsf{DeepImpact}\ significantly outperforms all methods and is statistically significantly better than other strategies for all effectiveness metrics on the \textsf{MSMARCO Dev Queries}\xspace. For the \textsf{TREC 2019}\xspace\ and \textsf{TREC 2020}\xspace\ queries, \textsf{DeepImpact}\ is always better than the competitors, with statistically significant improvements on NDCG@10 and MAP in some cases. Statistical significance on the latter two query traces is limited by their relatively small number of queries. 

We also see that \textsf{DeepImpact}\ mean response time exceeds the time reported for other methods. We trace this to the query processing strategy: the distribution of scores induced by BM25, used in \textsf{BM25}\xspace, \textsf{DeepCT}\xspace, and \textsf{DocT5Query}\ is exploited more efficiently by the MaxScore algorithm. In contrast, \textsf{DeepImpact}\ learns new scores, whose distribution is not efficiently exploited by MaxScore. We performed additional experiments using disjunctive query processing without optimizations, omitted for space limitations. These experiments show \textsf{DeepImpact}\ to be in line with the speed of the other approaches. Optimizing the query processing speed of \textsf{DeepImpact}{} is an interesting open problem for future research.

\input{figures/effectiveness}

\input{figures/reranking}

\boldparagraph{Re-ranking evaluation.}
Table~\ref{tab:reranking} shows the effect of re-ranking the top $1000$ candidates produced by \textsf{DeepImpact}\ using two complex re-rankers, \textsf{EPIC}\ and \textsf{ColBERT}\xspace. The table also shows, as a comparison, the performance obtained by \textsf{ColBERT}\xspace\ when used end-to-end by employing ANN search as the first-stage retrieval mechanism. \textsf{DeepImpact}\ followed by a \textsf{ColBERT}\xspace\ re-ranker obtains higher effectiveness values than \textsf{ColBERT}\xspace\ {\sf E2E} on all query sets. Moreover, \textsf{DeepImpact}\ + \textsf{ColBERT}\xspace\ exhibits a $4.4\times - 5.1\times$ speedup w.r.t. \textsf{ColBERT}\xspace\ {\sf E2E}.


\boldparagraph{First-stage cutoff evaluation.}
\textsf{DeepImpact}\ is able to achieve statistically significant higher recall than all the compared methods (with one single exception at cutoff 1000). In particular, Table~\ref{table:recall} shows that the gap with the other methods is greater with smaller cutoff values, which reduces the re-ranking cost and thus could enable the use of more complex pairwise ranking models, such as DuoBERT \cite{duobert}. In re-ranking, \textsf{DeepImpact}\ outperforms all other methods at cutoff 10. Moreover, it outperforms \textsf{DeepCT}\xspace on all cutoff values except 1000, and it is comparable with \textsf{DocT5Query}.

\input{figures/recall}



\section{Introduction}
Modern search engines employ complex, machine-learned ranking functions to retrieve the most relevant documents for a query. Recently, the development of pre-trained contextualized language models such as BERT~\cite{devlin2018bert} has resulted in impressive benefits in search effectiveness, at the cost of expensive query processing times, which can make their deployment in production scenarios challenging. \citet{nogueira2019bertranker} and \citet{cedr} showed the superior performance of BERT in term of effectiveness for passage and document re-ranking tasks, respectively, by fine-tuning the pre-trained transformer network to distinguish between relevant and non-relevant query--document pairs.
However, several recent studies~\cite{cedr,Hofsttter2019LetsMR} have shown that this can have very high computational cost, even if re-ranking just the top 1000 results.
Other studies~\cite{epic,prettr,colbert} proposed methods with lower lower computational cost but typically some loss in retrieval quality. BERT's Transformer encoder is composed of many neural layers performing expensive processing to compute the query-document relevance signals. Different solutions have been proposed to address this performance bottleneck, based on the pre-computation of query-document representations produced by BERT. \textsf{EPIC}~\cite{epic} proposes to build on top of BERT a new ranking model trained to generate query and document representations in a given fixed-length vector space, equal to the size of the lexicon. Document representations are pre-computed, while query representations are computed at retrieval time, and then used to obtain a ranking score by computing a similarity between the two representations. %

\textsf{PreTTR}~\cite{prettr} and \textsf{ColBERT}\xspace~\cite{colbert} experimentally show that the query-document interactions in most layers of BERT have little impact on the final effectiveness. This leads them to pre-compute document representations at indexing time, which are used at query processing time to compute the query-document interaction only in a final layer. While \textsf{PreTTR}\ still relies upon a first-stage candidate generation based on BM25, \textsf{ColBERT}\xspace investigates the ability of the pre-computed document representations to identify relevant documents among \textit{all} documents in the index. Due to space/time requirements of the document representation, \textsf{ColBERT}\xspace leverages approximate nearest neighbor (ANN) search applied to dense representations as a first-stage retrieval system, followed by an exact re-ranking stage, while similar approaches using exact nearest neighbor search~\cite{xiong2020approximate} can perform processing in a single stage. 


Following a different paradigm, \citet{deepct} investigated the use of the contextual word representations from BERT to generate more effective document term weights for bag-of-words retrieval. \textsf{DeepCT}\xspace~\cite{deepct}, for passages, and  \textsf{HDCT}\xspace~\cite{deepct2}, for documents,  estimate a term's context-specific importance in each passage/document, by projecting each word’s BERT representation into a single term weight. These term weights are then transformed into term frequency-like integer values that can be stored in an inverted index to be used with classical retrieval models. A main limitation of \textsf{DeepCT}\xspace\ that we address in this work is that it is trained as a \textit{per-token regression task}, in which a ground truth term weight for every word is needed, and which does not permit the individual impact scores to co-adapt for the downstream objective of identifying relevant documents. %

By storing new integer values as term frequencies in the inverted index, \textsf{DeepCT}\xspace and \textsf{HDCT}\xspace enrich a document's bag-of-words representation with additional document-level context information, to match queries more accurately. Using a different approach, \citet{docTTTTTquery} propose \textsf{DocT5Query}{}, a document expansion strategy to enrich each document with additional terms able to improve the retrieval effectiveness of documents w.r.t. queries for which they are relevant. \textsf{DocT5Query}{} trains a sequence-to-sequence model to predict queries potentially relevant to a given document, and appends these queries to the documents before indexing. As another way of expanding documents, the very recent {\sf SparTerm}~\cite{bai2020sparterm} method predicts an importance score for every term in the vocabulary and uses a gating mechanism to only keep a sparse subset of those, using them to learn an \textit{end-to-end} score for relevant and non-relevant documents. However, this only increases the MRR@10 of \textsf{DocT5Query}{} from 0.277 to 0.279.


\looseness -1 We propose \textsf{DeepImpact}, a more effective approach for learning a relevance score contribution for term-document pairs that can also be stored in a classical inverted index. \textsf{DeepImpact}{} improves impact-score modeling and tackles the vocabulary-mismatch problem~\cite{zhao2012modeling} between queries and documents. Instead of learning \textit{independent} term-level scores without taking into account the term co-occurrences in the document, as in \textsf{DeepCT}\xspace, or relying on unchanged BM25 scoring, as in \textsf{DocT5Query}, \textsf{DeepImpact}\ directly optimizes the \textit{sum} of query term impacts to maximize the score difference between relevant and non-relevant passages for the query.
In other words, while \textsf{DeepCT}\xspace learns the term frequency component of existing IR models, e.g., BM25, \textit{in this work we aim at learning the final term impact jointly across all query terms occurring in a passage}.
In this way, our proposed model learns richer interaction patterns among the impacts, when compared to training each impact in isolation. To address vocabulary mismatch, \textsf{DeepImpact}\ leverages \textsf{DocT5Query}\ to enrich every document  with new terms likely to occur in queries for which the document is relevant. Using a contextualized language model, it directly estimates the semantic importance of tokens in a document, producing a single-value representation for each token in each document that can be stored in an inverted index for efficient retrieval.
Our experiments show that \textsf{DeepImpact}\ significantly outperforms prior first-stage retrieval approaches by up to $17\%$ on effectiveness metrics w.r.t. \textsf{DocT5Query}. When deployed in a re-ranking scenario, it reaches the same effectiveness as state-of-the-art approaches up to $5.1\times$ faster.



In summary, this paper makes the following contributions:
\vspace{-0.4em}
\begin{itemize}
    \item We propose \textsf{DeepImpact}{}, a more effective scheme for \textit{jointly learning} term impacts over \textit{expanded documents}.
    \item We evaluate \textsf{DeepImpact}{} on the MS MARCO passage ranking task.
    We find that \textsf{DeepImpact}{} can improve ranking effectiveness for passage ranking versus prior first-stage retrieval approaches and is competitive when compared to complex systems based on ANN search, while exhibiting much lower computational costs.
    \item We evaluate \textsf{DeepImpact}\ as a first-stage model in a re-ranking pipeline, and show that this pipeline matches or outperforms strong baseline approaches, while being highly efficient.
\end{itemize}


\section{Conclusions and future work}
In this paper, we introduced \textsf{DeepImpact}, a new first-stage retrieval method that leverages a combination of a traditional inverted indexes and contextualized language models for efficient retrieval. By estimating semantic importance, \textsf{DeepImpact}\ produces a single-value impact score for each tokens of a document collection. Our results show that \textsf{DeepImpact}\ outperforms every inverted-index based baseline, in some cases even matching the effectiveness of more complex neural retrieval approaches such as \textsf{ColBERT}\xspace. Furthermore, when \textsf{ColBERT}\xspace\ is used to re-rank candidates retrieved by \textsf{DeepImpact}\, instead of approximate nearest neighbor, we find a dramatic reduction of query processing latency, and a more modest improvement in effectiveness of the whole pipeline.  
Future work will focus on further enhancing the underlying model. First, we would like to experiment with more relaxed matching conditions, instead of exact match, between the query-document terms. Second, we believe that we could improve further term expansion with more sophisticated techniques. Finally, we plan to investigate how changing the distribution of impact scores affects query processing algorithms such as MaxScore, and how we can address this issue.

