Re-ranking systems are typically limited by the recall of the initial retrieval function. A recent work proposed adaptive re-ranking, which modifies the re-ranking loop to progressively prioritise documents likely to receive high scores based on the highest scoring ones thus far. The original work framed this process as an incarnation of the well-established clustering hypothesis. In this work, we argue that the approach can also be framed as an information-seeking agent. From this perspective, we explore several variations of the graph-based adaptive re-ranking algorithm and find that there is substantial room for improvement by modifying the agent. However, the agents that we explore are more sensitive to the new parameters they introduce than the simple-yet-efective approach proposed in the original adaptive re-ranking work.
the incremental nature of re-ranking documents, typically done in batches to make the best use
of specialised hardware like GPUs and TPUs. After each batch, information is gained about
which documents get the highest relevance score, which can be leveraged to make a more
informed decision about which documents to rank next (a process the authors call Adaptive
Re-Ranking). By making use of the clustering hypothesis [
We argue that the approach for re-ranking can be thought of as an information-seeking agent and explained in terms of user browsing strategies. For instance, an agent using the traditional re-ranking approach simply scans down a list of search results looking for items that are relevant to its information need. Meanwhile, an agent using the A l t e r n a t e Adaptive approach alternates between exploring documents from the search results and similar documents to the most relevant ones it found so far. We observe that this may not be the process by which a reasonable human user would traverse search results; for instance, a user may only look at similar documents to those that are suficiently relevant. Therefore, in this work we explore a variety of agent-based strategies for adaptive re-ranking, inspired by behaviours that a human may take when seeking information.
In summary, we explore new agent-based strategies for the recently-proposed Graph-based Adaptive Re-Ranking approach. We establish an upper-bound performance for smarter agents and explore several other strategies. In doing so, we demonstrate the potential breadth of possible strategies that can be applied to GAR.
Cascading architectures are commonly deployed in information retrieval. In principle, these
are driven by an eficiency-efectiveness tradeof – the most efective models cannot be applied
on all documents in the index in a timely manner [
More recently, multi-stage ranking has been commonly used for applying neural re-ranking
models. For instance, cross-encoder neural models [
To address this gap, several recent neural ranking models of have been used proposed: (i) dense retrieval models based on bi-encoders and (ii) learned sparse models.
In bi-encoder-based dense retrieval models [
Learned sparse models encompass the use of the PLMs upon the document representation to make a refined representation that can be indexed by existing sparse inverted indexing tools. For instance, doc2query [18, 19] enriches the sparse document representation with possible queries that the document could be retrieved for. DeepCT [20], uniCOIL [21, 22], DeepImpact [23, 24] and SPLADE [25, 26] all use a PLM to generate a new sparse representation of the document.
This work focuses on a recently-proposed complementary approach: Graph-Based Adaptive
Re-Ranking (GAR) [
GAR is formulated as a re-ranking process. In a re-ranking process, the documents from an initial candidate set, 0, are re-ranked by a scoring function, Score(), to obtain a final ranking of 1 documents. The scoring function can be expensive to apply, for instance a cross-encoder neural model such as monoT5. This means that eficiency constraints may limit the number of applications of Score() that can be undertaken, which is called the re-ranking budget. In practice, batches of documents are scored at the same time, making efective use of GPU or TPU hardware.
A typical is non-adaptive re-ranking is shown in Algorithm 1, where an initial ranking (prioritised by rank) is scored in batches until the re-ranking budget is fully consumed.
In contrast, GAR proposed an adaptive approach to re-ranking, where highly scored documents are used as seeds for nearest neighbour retrieval, rather than continuing down the ranking. To perform this eficiently, a graph of document-document similarity ( ) is created at index time, which records the nearest documents for each given document. Since this is precomputed do 0 ← 0 ⧵ while | 1| < Algorithm 1 Non-Adaptive Re-Ranking
←
Score(top documents from 0, subject to ) and small, it can be used eficiently at ranking time to identify more documents to score.
In particular, after each batch of documents is scored, the nearest documents to those in the batch are added to a “frontier” set of documents . The frontier is prioritised by the scores of the re-ranked documents, so the neighbours of the highest-scored documents are explored ifrst. The process then alternates between scoring the top documents from the initial ranking 0 and scoring the top documents in the frontier . Algorithm 2 shows this process.
We call this A l t e r n a t e , due to the manner in which it alternates between the initial ranking and the frontier . In the following, we link GAR with intelligent agents, and shows us how this allows further agent-based implementations.
We argue that GAR re-ranking approaches can be interpreted as information-seeking agents, which peruse retrieved documents, and decide how to act based on the relevance of the documents found (such actions could be selecting more documents from the candidate set, or selecting similar documents to those already scored highly). In doing so, they act like a user who was deciding how to progress through a ranked list.
We treat existing re-ranking strategies as information-seeking agents, and in the following we introduce new alternative agents. In all cases, we have the following: an environment which consists of an initial ranking of candidate documents, denoted as 0, a graph of documentdocument similarities , and the final retrieved documents list 1; and a set of available actions, namely scoring documents from 0 and placing in 1, and scoring documents from and placing into 1. Some agents may also maintain a new state, such as a prioritised frontier of documents collected from the graph. We argue that such a fully-capable agent can be classified as a model-based reflex agent within the classes of [27]. Indeed, a scoring model (e.g., monoT5) estimates relevance, which is only partially observable. It can choose actions based on the state, i.e., the current frontier.
In the following, we list four possible agents based on the GAR formulation. 4.1. T w o P h a s e A simple alternative to A l t e r n a t e is to operate in two sequential phases. In the first phase, all documents up to rank < are scored. In the second phase, the remaining re-ranking budget − is utilised by prioritising the neighbours of the highest-scoring documents. The behaviour models a user who first investigates numerous pages of search results to find the most relevant content, and then goes back to check for similar documents to the best ones identified. Algorithm 3 shows this process. We consider two variations of this T w o P h a s e strategy: one where the frontier continues to be updated based on the scores of the documents in the second phase (T w o P h a s e - R e f i n e ), and one where the frontier only considers the first phase documents (T w o P h a s e - F i x e d ). 4.2. T h r e s h o l d The T h r e s h o l d agent only explores the corpus graph for suficiently relevant documents. In this setting, the initial ranking pool is updated to include the neighbours of scored documents
Input: Initial ranking 0, batch size , budget , corpus graph , first phase size Output: Re-Ranked pool 1 1 ← ∅ do ← Score(top from 0, subject to ) 1 ← 1 ∪ 0 ← 0 ⧵ while | 1| < ← Neighbours( 1, ) do ← Score(top from , subject to ) 1 ← 1 ∪ ← ⧵ ← ∪ ( Neighbours(, ) ⧵ 1) while | 1| < ▷ If “Refine” variant, otherwise skip this step Algorithm 4 T h r e s h o l d Re-Ranking Input: Initial ranking 0, batch size , budget , corpus graph
Score(top from 0, subject to ) 0 ← 0∪ (Neighbours(documents from that satisfy , G) ⧵ 1) do while | 1| < do 0 ← ∞ ← ∞ that exceed a relevance score threshold . By adding these documents to the pool with infinite priority, they are always scored before other documents in the pool. This agent is akin to a searcher who, as they traverse a ranked list, investigate similar documents to ones that they deem suficiently relevant as they are encountered. Importantly, this agent considers the absolute relevance score of documents, rather than the relative ordering of retrieved documents so far, which is used by techniques like A l t e r n a t e and T w o P h a s e . Algorithm 4 shows this process. 4.3. G r e e d y We next explore a strategy that attempts to identify which pool of documents – the initial ranking or the frontier – is has recently given the most relevant document. We approach this as a G r e e d y strategy, by always choosing the pool with the largest maximum score from the most recent batch. This process is akin to a searcher who switches between searching through a ranked list and the documents close to the best ones they found so far based on the most relevant document they identified recently from each pool. Algorithm
←MaxScore(B) ←
if 4.4. Oracle Finally, to explore whether there is further room for improvement in adaptive re-ranking, we apply an oracle strategy. This strategy makes use of the relevance assessments (qrels) to choose which batch of documents to score. At each step, both the initial ranking and the frontier are scored. Then, the algorithm proceeds by adding only the batch that improves the ranking efectiveness (e.g., through a measure like nDCG) the most at that step. Naturally, this algorithm is not useful in practice, given that it relies on ground-truth relevant knowledge.1 However, it helps us establish whether there is further room for improvement in adaptive re-ranking agents. Algorithm 6 shows this process.
We conduct experiments using various adaptive re-ranking agents to answer the following research questions: RQ1 Is there room for further improvement in adaptive re-ranking strategies? RQ2 Can smarter adaptive re-ranking strategies outperform the A l t e r n a t e approach? RQ3 How sensitive are alternative adaptive re-ranking strategies to their parameters?
We conduct experiments using the TREC Deep Learning 2019 and 2020 passage ranking datasets [28, 29]. We use 2019 as our “development” data, leaving 2020 as a held-out test set. For both datasets, we report nDCG and Recall@1000 (with a minimum relevance threshold of 2) performance. We fix our study to a MonoT5 (base) scoring function [ 30], a re-ranking budget = 1000 , and a batch size = 16 . We explore four initial ranking functions: BM25, TCTColBERT [31, 32], Doc2Query [19], and SPLADE++ (C o C o n d e n s e r - E n s e m b l e D i s t i l version) [26]. 1Of course, a perfect agent would ignore the scoring function entirely and just return documents by their human assessments to get a perfect ranking. We limit the usage of the assessments for this agent to the decision of which batch to score to help us identify whether better decisions about which batches to score can further improve adaptive re-ranking efectiveness.
Pipeline BM25»MonoT5 TCT»MonoT5 D2Q»MonoT5 SPLADE»MonoT5
Agent Non-Adaptive Oracle Alternate TwoPhase-Fixed TwoPhase-Refine Threshold Greedy Non-Adaptive Oracle Alternate TwoPhase-Fixed TwoPhase-Refine Threshold Greedy Non-Adaptive Oracle Alternate TwoPhase-Fixed TwoPhase-Refine Threshold Greedy Non-Adaptive Oracle Alternate TwoPhase-Fixed TwoPhase-Refine Threshold Greedy GAR25
GAR
TREC DL 2020 (test) GAR25
GAR nDCG performing (non-oracle) agent in section is listed in bold. Significant diferences compared to the Non-Adaptive, Oracle, and A d a p t i v e systems are marked with , respectively (paired t-test, < 0.05 ). distribution, from 0.022 to 0.20 (by 0.02).3 Following the original G A R paper, we use two corpus graphs, based on BM25 similarity and TCT-ColBERT.
As we will show in Section 6, T w o P h a s e and T h r e s h o l d are rather sensitive to their parameters, so the results we present use the parameters that yield the highest nDCG performance on TREC values ranging from 100 to 900 (by 100). For DL 2019. For T w o P h a s e , we test first-stage cutof T h r e s h o l d , we first identify the distribution of scores using the MS MARCO dev (small) dataset, re-ranking 100 BM25 results. We then pick threshold values based on percentiles from this
2Here, 0.02 represents the top 2% of scores. 3This range was chosen after an initial study of orders of magnitude from 0.001 to 0.3 identified it as the most promising.
We first explore whether there exists room for improvement by exploring alternative agents (RQ1). In all cases, the Oracle agent, which has knowledge of the relevance assessments when choosing which batches of documents to score, has a higher nDCG performance than all other agents. The diference in performance can often be considerable; for instance, the best-performing non-oracle agent over a the TCT pipeline using a BM25 graph has an nDCG of 0.733, while the oracle achieves an nDCG of 0.793. Diferences between non-oracle agents and the Oracle are not always significant, however. We note that while nDCG is often improved using either oracle technique, recall often sufers compared to alternative agents. Perhaps this is unsurprising, given that the oracles aim to directly optimise nDCG (recall is only considered insofar as it would improve the nDCG). Significant improvements compared to the Oracle are found more frequently when measuring nDCG using TCT corpus graph (GAR ) than the BM25 graph (GAR25 ).
In summary, to answer RQ1, by exploring an oracle agent, we find that there is considerable room for improvement in adaptive re-ranking. In particular, exploration of the semantic graph (GAR ) by non-oracle agents is likely sub-optimal and has room for considerable improvement.
Next, we look to answer RQ2 and RQ3. We find that each of the proposed alternative agents to be the most efective in at least one measurement. In one case, an alternative agent significantly outperforms the existing A l t e r n a t e agent (T h r e s h o l d when re-ranking BM25 results using GAR ). Further, there are 11 cases where alternative strategies outperform the non-adaptive, while A l t e r n a t e does not. However, there are sometimes significant reductions in efectiveness when using the alternative agents (18 cases, all of which on the held-out DL20 data). There is also no clear pattern in which strategy is generally most efective. These results answer RQ2: while some strategies can outperform A l t e r n a t e , we do not find a clearly superior strategy among the agents we test.
Given that significant reductions are present when using the held-out DL20 data, we dive
deeper into the performance of T w o P h a s e and T h r e s h o l d by plotting their performance for the
parameters they introduce (T w o P h a s e adds the first stage cutof and T h r e s h o l d adds the relevance
threshold ). Figure 1 present the nDCG performance. We see that in all cases, performance
varies considerably as the parameters are adjusted. Further, the optimal parameters for DL19
are often diferent than the optimal parameters for DL20, suggesting that the alternative agents
are not very robust to the selection parameter selection. This is in particular contrast with the
robustness of the A l t e r n a t e approach to parameters, shown by MacAvaney et al. [
In this work we investigated the recently-proposed Adaptive Re-Ranking process from the perspective of information-seeking agents. We find that there is considerable room to improve adaptive re-ranking by changing the agent strategy. We further proposed several alternative strategies, and found that although they are promising, they are more sensitive to their parameters than the simple A l t e r n a t e approach. This work sets the stage for future work that investigates additional agent strategies, such as those inspired by multi-armed bandit models. 100 200 300 400 500 600 700 800 900
Cutoff k 100 200 300 400 500 600 700 800 900
Cutoff k
T w o P h a s e - F i x e d DL19 GARBM25
DL19 GARTCT DL20 GARBM25
DL20 GARTCT 100 200 300 400 500 600 700 800 900
Cutoff k 100 200 300 400 500 600 700 800 900
Cutoff k
T h r e s h o l d DL19 GARBM25
DL19 GARTCT
T w o P h a s e - R e f i n e DL19 GARBM25
DL19 GARTCT DL20 GARBM25
DL20 GARTCT
Sean and Craig acknowledge EPSRC grant EP/R018634/1: Closed-Loop Data Science for Complex, Computationally- & Data-Intensive Analytics. [18] R. Nogueira, W. Yang, J. Lin, K. Cho, Document expansion by query prediction, Preprint: arXiv:1904.08375 (2019). [19] R. Nogueira, J. Lin, From doc2query to docTTTTTquery, Online preprint (2019). [20] Z. Dai, J. Callan, Context-aware sentence/passage term importance estimation for first stage retrieval, Preprint: arXiv:1910.10687 (2019). [21] L. Gao, Z. Dai, J. Callan, COIL: Revisit Exact Lexical Match in Information Retrieval with
Contextualized Inverted List, in: Proc. NAACL-HLT, 2021, pp. 3030–3042. [22] J. Lin, X. Ma, A few brief notes on DeepImpact, COIL, and a conceptual framework for information retrieval techniques, Preprint: arXiv:2106.14807 (2021). [23] A. Mallia, O. Khattab, T. Suel, N. Tonellotto, Learning passage impacts for inverted indexes, in: Proc. SIGIR, 2021. [24] A. Mallia, J. Mackenzie, T. Suel, N. Tonellotto, Faster Learned Sparse Retrieval with Guided
Traversal, in: Proc. SIGIR, 2022, p. 5. [25] T. Formal, B. Piwowarski, S. Clinchant, SPLADE: Sparse Lexical and Expansion Model for
First Stage Ranking, in: Proc. SIGIR, 2021, p. 2288–2292. [26] T. Formal, C. Lassance, B. Piwowarski, S. Clinchant, Splade v2: Sparse lexical and expansion model for information retrieval, 2021. [27] S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 3 ed., Prentice Hall, 2010. [28] N. Craswell, B. Mitra, E. Yilmaz, D. Campos, E. Voorhees, Overview of the trec 2019 deep learning track, in: TREC 2019, 2019. [29] N. Craswell, B. Mitra, E. Yilmaz, D. Campos, Overview of the trec 2020 deep learning track, in: TREC, 2020. [30] R. Nogueira, Z. Jiang, R. Pradeep, J. Lin, Document ranking with a pretrained sequence-tosequence model, in: Proc. EMNLP, 2020. [31] S.-C. Lin, J.-H. Yang, J. J. Lin, Distilling dense representations for ranking using tightlycoupled teachers, ArXiv abs/2010.11386 (2020). [32] S.-C. Lin, J.-H. Yang, J. Lin, In-batch negatives for knowledge distillation with tightlycoupled teachers for dense retrieval, in: RepL4NLP-2021 Workshop, 2021, pp. 163–173.