Zero-Shot Retrieval with Search Agents and Hybrid Environments
Authors: Michelle Chen Huebscher
Christian Buck
Massimiliano Ciaramita
Sascha Rothe
Venue: Submitted to ICLR 2023 (2023)
Keywords: learning to search
information retrieval
document ranking
relevance feedback
zero shot
language models
behavioral cloning

Abstract: Learning to search is the task of building artificial agents that learn to autonomously use a search box to find information. So far, it has been shown that current language models can learn symbolic query reformulation policies, in combination with traditional term-based retrieval, but fall short of outperforming neural retrievers. We extend the previous learning to search setup to a hybrid environment, which accepts discrete query refinement operations, after a first-pass retrieval step performed by a dual encoder. Experiments on the BEIR task show that search agents, trained via behavioral cloning, outperform the underlying search system based on a combined dual encoder retriever and cross encoder reranker. Furthermore, we find that simple heuristic Hybrid Retrieval Environments (HRE) can improve baseline performance by several nDCG points. The search agent based on the HRE environment (HaRE) produces state-of-the-art performance on both zero-shot and in-domain evaluations. We carry out an extensive qualitative analysis to shed light on the agents policies.

Under review as a conference paper at ICLR 2023
ZERO-SHOT RETRIEVAL WITH SEARCH AGENTS AND HYBRID ENVIRONMENTS
Anonymous authors Paper under double-blind review
ABSTRACT
Learning search is the task of building artificial agents that learn to tonomously use a search box to find information. So far, it has been shown that current language models can learn symbolic query reformulation policies, in combination with traditional term- based retrieval, but fall short of outperform- ing neural retrievers. We extend the previous learning to search setup to a hybrid environment, which accepts discrete query refinement operations, after a first-pass retrieval step via a dual encoder. Experiments on the BEIR task show that search agents, trained via behavioral cloning, outperform the underlying search system based on a combined dual encoder retriever and cross encoder reranker. Further- more, we find that simple heuristic Hybrid Retrieval Environments (HRE) can improve baseline performance by several nDCG points. The search agent based HRE (HARE) matches state-of of-the-arttt performance, balanced in both zero- shot and in-domain evaluations, via interpretable actions, and at twice the speed.
INTRODUCTION
Transformer- baase based dual encoders for retrieval, and cross encoders for ranking (cf. e.g., Karpukhin itt al. (2020); Nogueira & Cho (2019)), have redefined the architecture of choice for information search systems. However, sparse term-based inverted index architectures still hold their ground, es- pecially in out-of-domain, or zero-shot, evaluations. On the one hand, neural encoders are prone to overfitting on training artifacts (Lewis et al.] [02I]. On the other, sparse methods such as BM25 (Robertson & Zaragoza 2009) may implicitly benefit from term-overlap bias in common datasets (Ren et al. (0022). Recent work has explored various forms of dense-sparse hybrid com- binations, to strike better variance-bias tradcoffss (Khattab & Zaharia 2020: Formal et al. 2021b
Chen et al.
2021 2022).
Rosa et al.
2022) evaluate simple hybrid design which takes out the dual encoder altogether and simply applies a cross encoder reranker to the top documents retrieved by BM25. This solution couples the better generalization properties of BM25 and high-capacity cross encoders, setting the current SOTA on BEIR by reranking 1000 documents. However, this is not very practical as rerank- ing is computationally expensive. More fundamentally, it is not easy get insights on why results are reranked the way they are. Thus, the implicit opacity of neural systems is not addressed.
We propose a novel hybrid design based on the Learning to Search (L2S) framework (Adolphs) ett al. (2022). In L2S the goal is to learn a search agent that autonomously interacts with the retrieval environment to improve results. By iteratively leveraging pseudo relevance feedback (Rocchio) 1971], and language models' understanding, search agents engage in a goal-oriented traversal of the answer space, which aspires model the ability to 'rabbit hole' of human searchers (Russell 2019) The framework is also appealing because of the interpretability of the agent's 's actions.
Adolphs al. (2022) show that search agents based on large language models can learn effective symbolic search policies, in a sparse retrieval environment, but fail to outperform neural retriev- ers. We extend L2S to a dense-sparse hybrid agent-environment framework structured as follows. The environment relies on both state-of-the-arr dual encoder, GTR (Ni et al. 2021). and BM25 which separately access the document collection. Results are combined and sorted by means of a transformer cross encoder reranker (Jagerman al. (2022). We call this Hybrid Retrieval Envi- ronment (HRE). Our search agent (HARE) interacts with HRE by iteratively refining the query via search operators, and aggregating the best results. HARE matches state-of-the-an results the

---

Under review as a conference paper at ICLR 2023
BEIR dataset (Thakur et al., 2021) by reranking order of magnitude less documents than the SOTA system (Rosa et al. 2022). reducing latency by 50%. Furthermore, HARE does not sacrifice in-domain performance. The agent's actions are interpretable and dig deep in HRE's rankings.
what is the weather like in germany june
Juue, ally, and Aupust. Nansch Germany veathe het. (sscecially city cunter) can constantly reachang even surpeasing 30 degrees Gulsius (98*F), Enjoy the time as nuch as you can, because it probably won't last long.
nDCG=0
what is the weather like in germany june *temeeratures
auacagg tesperatuoss for Cermany. dintt Aitt. dhrsughout
terperatures Histed belon
Ge Gelstus and Fahrechett, The tables give the frrala la for naxt win etstrus aonthly
nDCG=0
what is the weather like in germany june
Weather in Hannover in Jane 2018. Expect 21"0 daytime maximue tomper atures Harnover in June. Check more long tore weather averages for Hamover an June before you book your next holiday Germany in 2018."
+temperatures +average
nDCG=1
Figure 1: Sequential query refinements combining pseudo relevance feedback and search operators.
Figure M shows an example of a search session performed by the HARE search agent applying structured query refinement operations. The agent adds two successive filtering actions to the query "what is the weather like in germany in june" (data from MS MARCO (Nguyen et al.] (0066). In the first step it restricts results to documents containing the term 'temperatures' which occurs the first set of results. In the second step, results are further limited to documents containing the term "average'. This fully solves the original query by producing nDCG@ @ 10 score of 1.
2 RELATED WORK
Classic retrieval systems such as BM25 (Robertson & Zaragoza 2009) use term frequency statistics determine the relevancy of a document for given query. Recently, neural retrieval models have become more popular and started to outperform classic systems on multiple search tasks. Karpukhin jet al.) (200)) use a dual-encoder setup based on BERT (Devlin et al., 2019), called DPR, to encode query and documents separately and use maximum inner product search (Shrivastava & Li 2014) to find a match. They use this model to improve recall and answer quality for multiple open-domain question-answer datasets. Large encoder-decoder models such as T5 (Raffel al. 2020) are now preferred as the basis for dual encoding as they outperform encoders-only retrievers retrreeeveer
et 2021
It has been observed that dense retrievers can fail to catch trivial query-docunme syntactic matches involving n-grams or entities (Karpukhin et al. 2020 Xiong et al.) 2021 (Sciavolino et al.) 2021). ColBERT (Khattab & Zaharia 2020) gives more importance to individual terms by means of a late interaction multi-vector representation framework, in which individual term embeddings are ac- counted in the computation of the query-document relevance score. This is expensive as many more vectors need to be stored for each indexed object. ColBERTv2 (Santhanam et al. (002)) combines late interaction with more lightweight token representations. SPLADE (Formal al. 222 lb) is an- other approach that relies on sparse representations, this time induced from a transformer's 's masked heads. SPLADEv2 (Formal al.] 2021ai 2022) further improves performance introducing hard- negative mining and distillation. Chen et al. (202T) propose to close the gap with sparse methods on phrase matching and better generalization by combining dense retriever with a dense lexical model trained to mimic the output of sparse retriever (BM25). Ma al. (2021) combine single hybrid vectors and data augmentation via question generation. In Section 3 (Table 2b) we evaluate search environment and some of the methods above.
The application of large LMs to retrieval, and ranking, presents significant computational costs for which model distillation (Hinton et al.) 2015) is one solution, e.g. DistillBERT (Sanh et al. 2019). The generalization capacity of dual encoders have been scrutinized recently in QA and IR tasks (Lewis et al. 2021: Zhan al. 2022 Ren et al. 2022). Zhan et al. (2022) claims that dense
2

---

Under review as a conference paper at ICLR 2023
Environments performance at
BEIR subset nDCG@
ColB.
SPAR.
SPL.
0.50
Brergee BBR -000610
ColBERTv2
0.481
0:40
SPAR
0.475
0.482
SPLADE+
0,475
0.508
0.482
0.46
BM25
HRE, 770M
0.543
0.526
0.507
0.44
GTR
HRE, 11B
0.529
0.530
0.507
044
HRE
(b) Our HRE, compared, at k=10, vs. other dense/sparse methods. The BEIR average score computed on subsets of tasks selected by each method. HRE 770M is trained on BM25 top 100 documents, HRE 1IB on BM25 top 1000.
40
30
1000
Number of documents scored
(a) Average nDCG@ 10 of the BM25, GTR and HRE at different retrieval depths.
Figure 2: Preliminary evaluation of our HRE and benchmark environments on BEIR tasks.
rerankers generalize better than dense retrievers. Ni et al. (2021) suggests that increasing the dual encoder model size increases its ability generalize. Rosa al. (2022) argue that large rerankers provide the most effective approach, particularly in zero-shot performance and in combination with sparse retriever. Their best MonoT5 (Nogueira al.] 2020b) model, a pretrained transformer encoder-decoder finetuned for query documett scoring, yields the state-of-the-we results on 12 out of 18, zero-shot tasks on the BEIR task (Rosa et al. 2022). They observe that in-domain performance is not good indicator of zero-shot performance. Consequently, they regularize the reranker, trading off in-domain performance and improving zero-shot results.
Another interesting line of research is inspired by large decoder-only language models, where in- creasing size systematically improves zero-shot performance, as proven by GPT (Brown et al. 2020) and PaLM (Chowdhery et al., 2022). Accordingly, SGPT (Muennighofii 2022) extends the encoder/deecderr-nll approach to search to decoder-only modeling, via prompting and finetuning. Also related is the line of work on retrieval-augmmnted language models (Lewis al. 2020 Guu et al.
2020) and iterative query reformulation for question answering (Guo et al. 2017
Buck et al.
2018
Qi et al. 2019 2021 Zhu et al. 2021 Nakano al. 2021).
3 HYBRID RETRIEVAL ENVIRONMENT (HRE) AND BENCHMARKS
search environment composed of reirievers operating document collection, whose output is possibly combined, and eventually rescored by dedicated model, the reranker.
3.1 RETRIEVERS
We experiment with three types of retrieval methods. The first, BM25, uses Lucene's implementa- tion of BM255 as the retriever. This is the setting of (Adolphs et al. 2022). The second environment, GTR, uses GTR-XXL (Ni et al. 202T) as the retriever. The last a hybrid environment that com- bines the results of the BM25 and GTR retrievers. We call this Hybrid Retrieval Environment (HRE). After retrieval, HRE simply joins the two k-sized results sets, removing duplicates. Thus, for fixed value of k; HRE has available slightly larger pool of documents, most 2k.
3.2 THE T5 RERANKER (T5-R)
After retrieval, and, in the case of HRE, the combination step, the top documents are reranked by the environment's s reranker, which we refer to as T5-R. In contrast encoder-decoders (Nogueira et al. 2020a) we follow the work of Zhuang et al. (2022) and only train T5-R's 's encoder and add a classification layer on top the encoder output for the first token, similar to how BERT (Devlin al. 2019) is often used for classification.
3

---

Under review as a conference paper at ICLR 2023
Instead of using point- classification loss, we list-based loss (Jagerman et al., 2022 Zhuang et al. 2022): for each query, we obtain one positive (y = 1) and m negative (y 0)
documents to which the model assigns scores y of We use a list-wise softmax cross-entropy loss (Bruch et al. 2019:
112
e
e(y, 9)
Y/ log
-j=1 6%
We train T5-R on MS MARCO and the output of BM25. We find that T3-Large trained on the top-100 documents works well on the top results, but a T5-11B model trained on the top- 1000 BM25 documents works better in combination with a search agent (Table 2). For HRE we consider the latter reranker. Figure 2 provides first evaluation of the ranking performance of our environments on the BEIR dataset- see S for more details on the task. Figure reprrtss the effect of reranking an increasing number of documents. BM25 provides a baseline performance, and benefits the most from reranking more results with T5-R. GTR starts from a higher point, at k=10, and plateaus around k=300 with average nDCG@ 10 (normalized Discounted Cumulative Gain) of 0.507 on the 19 datasets. Despite its simplicity, HRE is effective at combining the best of BM25 and GTR at small values of k. HRE reaches its maximum, 0.509, at 4=40 but scores 0.508 at k=20.
In Figure 2b we situate our environments in a broader context, by comparing zero shot performance against recent dense/sparse combined retrieval proposals: ColBERTv2 (Santhanam
2022), SPAR (Chen et al. 2021) and SPLADE++ (Formal et al. 2022). discussed also in 2 Each of them evaluates on different subset of the BEIR zero shot tasks, which we select appropriately. HRE pro- duces the best performance by substantial margin in two configurations. ColBERT and SPLADE do not use a reranker but require more involved training through cross-attention distillation, and rely on token-level retrieval. The best SPAR model needs an additional dense lexical model and relies on a more sophisticated base retriever, Contriever (Izacard et al., 20.I). As the results show, a reranker combined with HRE at (k=10) provides simple and effective hybrid search system.
HYBRID AGENT RETRIEVAL ENVIRONMENT (HARE)
search agent generates a sequence of queries, go Q1, ................................ QT, to be passed on, one at a time, to the environment. Here, q0=q is the initial query and gr is the last one, in what we also call search session, At each step, the environment returns a list of documents Dr for q:. We also maintain a list, A, of the best l documents found during the whole session
A {d. D. Hd, E D- f(qu d,) ff(90 d,)} < k}
(2)
where f:(g, d) + I. is the score, P(y=1/g, d). predicted by the T5-R model. When no documents can be retrieved after issuing 4++1 or after a maximum number of steps, the search session stops and Ae is returned the agent's output. The agent's goal is to generate queries such that the output, Ar, has high score under a given ranking quality metric, in our case nDCG@ 10.
4.1 QUERY REFINEMENT OPERATIONS
As in (Adolphs et al. 2022). g++1 is obtained from by augmentation. That is, either by adding single term, which will be interpreted by Lucene as disjunctive keyword and contribute a com- ponent to the BM25 score, or including an additional unary search operator. We experiment with the same three unary operators: '+', which limits results documents that contain a specific term, '-' which excludes results that contain the term, and 'x," which boosts term weight in the BM25 score by a factor i E R. We don't limit the operators effect to a specific document field, e.g., the content or title, because in the BEIR evaluation there is no such information in the training data (MS MARCO). Formally, a refinement takes the following simplified form:
4++1 := qt Aqe. Age = [+| - |M,] Wy, we E Σ,
(3)
where Σg is the vocabulary of terms present in A,. This latest condition introduces a relevance feedback dimension (Rocchio| 1971). If available, document relevance labels can be used to build an optimal query, e.g.. for training. Or, in the absence of human labels, the search results are used for inference purposes as pseudo relevance feedback.
4

---

Under review as a conference paper at ICLR 2023
D
A
qt
1-1
Corpus
D.
D
T5-R
A
11
GTR
BM25
9++
D 1.2
T5-Q
q tt>
Top-K
9
A
Figure 3: Schematic view of the HARE search agent. The information flows from the input query go to the output Ar. In between, retrieval steps (the blue components) and aggregation and refinement steps (the yellow components) alternate in cycle.
4.2 THE T5 QUERY EXPANDER (T5-Q)
A search agent includes an encoder-decoder transformer based on T5 (Rattel et al. 2020) that gen- erates query refinements. We call this component T5-Q. At each step, an observation o,:=(q: Ar) is formed by concatenating l and A,, which is string with minimal set of structural identifiers. T5-Q takes 0g as input and outputs Dgt, allowing the composition of 1++1 as in Eq. (3)
4.3 HARE AND BENCHMARK SEARCH AGENTS
Figure 3 iillustrates the HARE search agent. On the first search step only, GTR retrieves the top-1000 documents for 4o- These define sub-collection, Top- K, kept frozen through the search session. The top-k documents from Top-K, Do,2, combined with the top-k from BM25, D also retrieved from the full collection. GTR is not used again. Top-K is further accessed only through BM25, i.e., for f > O. At every step, t,, the results from the full corpus, Dr,1, and those from Top-K, D22,, are joined to form D,. Dr, in turn, is joined with the current session results At-1, to form At- At is passed to the query expander model, T5-Q, which compiles the observation o,= qt). and generates Aqr. The new query, Qt+1 1-+1- Age. is sent to BM25 for another round of search. When the termination condition is met, the agent returns Ar
Besides HARE we evaluate two simpler search agents, in alignment with the simpler environments, BM25 and GTR. The first agent (BM25) only uses the BM25 components of HARE (the BM25 environment), thus, it has only access to the results Dr.1 in Figure 3 Analogously, the second agent (GTR), only uses the GTR components of HARE (the GTR environment), and has access exclusively to the Dt,2 results.
5 EXPERIMENTS
We run experiments on the zero-shot retrieval evaluation framework of BEIR Thakur et al. 2021 which includes 19 datasets domains. Only MS MARCO used for training and development. Each dataset has its own document collection which is indexed separately. We use the official TREC eval scripf" for our results, Results for the benchmarks from the corresponding publications.
5.1 DATA
To generate training data for T5-R we retrieve (100, 1000} documents per query for each query in the MS MARCO training set (532,761 questions) using BM25. To make one example list of length
5

---

Under review as a conference paper at ICLR 2023
m, we take query and one gold document and sample m-1 negatives from the top-k documents. We skip queries if no gold document occurs within the top-k documents which removes about 20% of the data.
The training data for T5-Q is generated as follows. Synthetic search sessions are simulated from labeled query documents pairs, (g, d), where d is the relevant document for q. in the MS MARCO training set. We then use the Rocchio Session Algorithm of [Adolphs et al. (2022). to search for the optimal expansion. In nutshell, at step terms in Ag d are evaluated as candidates for dis- junctive term augmentations, or in combination with '+' and "Ax" operators. Conversely, terms in A are candidates in combination with ' We attempt at most M candidates for each oper- ator using terms in the document set, A,, ranked by Lucene's 's IDF score. Starting from qo-g. a synthetic session expanded, one step at time, with the best scoring augmentation. The proce- dure stops when the nDCG@ 10 score of A, does not improve, or after five steps. We generate two sets of training data: high-throughput (HT) data, for faster turnaround in development, which sets M=20 and yields 120,563 training examples (single steps) from 23% of the questions where im- provements were found; and a high-quality (HQ) data using ==100 which yields 203,037 training examples from 40% of the questions for which improvements were found. Table 4 in the Appendix, provides an example gold Rocchio session for the query 'what's the difference between C++ and java'. The nDCG score of the HRE results is 0.0, and by applying two refinements ('+language' and "+platform") the score increases, first to 0.6, then to 1.0. In the training Rocchio sessions, the '+' operator is used for 83% of all refinements. The other operators are each used for only 2-3% of all refinements. Although '+' is used for the majority of refinements, when we evaluated the agent's headroom allowing only the '+' operator, the headroom was lower. We also evaluated the agent's headroom allowing only "A;" operators, the result was also worse. The synthetic data is used to finetune T5-Q via Behavioral Cloning, where each step defines an independent generation task.
5.2 MODELS
We use the published model checkpoint for GTR-XXL (Ni et al. 2021). as the off-the-sheif dual encoder For BM25 we use Lucene's implementation with default parameters (k=0.9 and b=0.4).
As detailed in Section 3 the query-document reranker, T5-R. is initialized from the encoder of a pretrained T5 model. The encoder output of the first token is fed into feed-forward layer to generate a score which we use for ranking query-document pairs. The input is structured as follows:
query: {query) document: {document}
We experimented with several published checkpoints, including TS-large and T5- 11B and found the latter to perform better"] Note that while T5-1iB has 1 IBB parameters we only train roughly half of them (the encoder side). We train with a batch size of 64 and lists of length m = 32, yielding an effective batch size of 2048. To limit memory consumption truncate inputs 256 tokens.
The query expander, T5-Q, is based on the 1XXX model. The input is structured as follows: query: {query} document: [document: .... document: {document 1 0}}
When examining the training data (55.I). we found multiple examples of that we consider unlearn- able, e.g., involving stop words. As we do not want the search agent to concentrate and overfit on these examples, we employ a simple self-supervised training trick. In each batch, we sort the se- quences by their negative log-likelihood (NI..) and we mask out the loss for 50% of the training examples with the highest NL... Examples can be seen in Table in the Appendix. We are essen- tially training with only a halved batch size while wasting the other half, but given that the model converges quickly, this technique is sufficient. To further avoid overfitting, we use a small constant learning rate of 3 10-3 We train for 12,000 steps with batch size of 128 (forward pass before masking), which is equivalent to around 1.5 epochs. The input sequences have a maximum length of 1024 and the maximum target length is set to 32. All other hyperparameters are the T5 defaults.
5.3 RESULTS
Table I holds the detailed BEIR results. We report the average over all datasets (Average), and mi- nus MS MARCO (Avg. Zero-shot). As benchmarks, we compare with Mono'T5, the current SOTA,

---

Under review as a conference paper at ICLR 2023
Benchmarks
Environments
Agents
RS
Dataset
MonoT5
SGPT
BM25
GTR
HRE
BM25
GTR
RM3
HARE
BM25
MS MARCO
0.398
0.399
0.285
0.470
0.479
0.361
0,480
0.483
0.483
0.557
Trec-Covid
0.794
0.873
0.579
0.537
0.666
0.778
0.703
0.744
0.765
0.921
BioASQ
0.574
0.413
0.315
0.344
0.427
0.453
0.470
0.468
0.493
0.654
NFCorpus
0.383
0,362
0.343
0.358
0.377
0.380
0.368
0.380
0.383
0,508
NQ
0.633
0.524
0,419
0.637
0.655
0.528
0.664
0.661
0.669
0.724
HotpotQA
0.758
0.593
0.605
0.651
0.713
0.694
0.734
0.734
0.759
0.850
FIQA-2018
0.513
0.372
0.268
0.504
0.513
0.355
0,516
0.520
0.525
0.564
Signal-IM
0.314
0.276
0.371
0.273
0.320
0.355
0.313
0.310
0.318
0.476
Tree-News
0.472
0.481
0.300
0.368
0.394
0.353
0,368
0.420
0.406
0.521
Robust04
0.540
0.514
0.384
0.513
0.556
0.513
0.514
0.565
0.589
0.728
ArguAna
0,287
0.514
0.318
0.352
0.327
0.246
0.362
0.237
0.260
0.389
Touche-2020
0.299
0.254
0.536
0.249
0.325
0.518
0.251
0.321
0.320
0.673
Quora
0.840
0.846
0.650
0.875
0.876
0.769
0.874
0.873
0.873
0.880
DBPedia
0.477
0.399
0.290
0.428
0.453
0.383
0,432
0.463
0.476
0.549
SCIDOCS
0.197
0.197
0.166
0.173
0.196
0.181
0.197
0.198
0.201
0.280
Fever
0.849
0.783
0.783
0.811
0.829
0.813
0.817
0.831
0.832
0.866
Climate-Fever
0.280
0.305
0,222
0.282
0.296
0.258
0.287
0.300
0.300
0.408
SciFact
0.777
0.747
0.683
0.707
0.751
0.707
0.743
0.751
0.756
0.797
CQADupStack
0.415
0.381
0.316
0.431
0.448
0.364
0.448
0.451
0.452
0.526
#does reranked
1000
10
10
17.5
21.6
23.6
33.4
66.7
15.5
Average 0.516
0.485
0.412
0.472
0,505
0.474
0,502
0,511
0.519
0.625
Avg. Zero-shot
0.522
0.490
0.419
0.472
0.507
0.480
0.503
0.513
0.521
0.628
Table I: Full results on BEIR. MonoT5 refers to the best-performing system in (Rosa et al. current SOTA performance holder. Mono'T5 reranks the top 1000 documents from BM25 with cross encoder. SGPT refers the best performing GPT-style system from (Muennighofi 2022) SGPT-BE 5.8B. As environments, we evaluate BM25, GTR and HRE (B The last four columns report the results of the BM25,, GTR and HARE agents (#4.3) including a variant (RM3, based on HRE) that replaces T5-Q with RM3 (Pal et al. 2013). As customary on BEIR evals, we report the all datasets average and without MS MARCO (zero shot only). We also report the number of unique documents scored with the reranker, the average value for agents and HRE. The SGPT model retrieves over the full collection. The last column (RS) reports the performance the (HQ) Rocchio Session algorithm used to generate the training data when run all BEIR eval sets. Having access to the labeled document(s), it provides an estimate of the headroom for search agents.
2022
which reranks the top 1000 documents from BM25, with cross encoder transformer reranker (Rosal lt 2022). We also report the results of the best performing GPT-style system from (Muennighoff) 2022). SGPT is intriguing because of its unique performance profile ge.g., see on Trec-Covid and Ar- guana), reinforcing the suggestion that large decoder-only LMs introduce genuinely novel qualitative dimensions to explore. Next, we discuss the results of our BM25, GTR and HRE and corresponding agents. For all our systems, reranking depth is fixed at k=10.
All search agents run fixed 5-steps sessions at inference time. They all outperform their environ- ment. One needs to factor in that agents score more documents, because of the multi-step sessions. The BM25 and GTR agents collect on average about 20 documents per session, HARE 66.7. One of the desired features of search agents is deep but efficient exploration, which is observable from the experiments. For the BM25 environment to match the BM25 agent performance (0.474/0.480) one needs to go down to ks0300, ef. Figure 2a Overall, the BM25 agent outperforms the BM25 environment by more than points. We highlight that the BM25 agent outperforms also the GTR en- vironment, though not in io-domain MS MARCO consistently with the findings of Adolphs et al. (2022). The GTR agent outperforms the GTR environment by points, with the GTR environment beginning perform better than the GTR agent only between k= and 1000

---

Under review as a conference paper at ICLR 2023
Depth documents in HaRE's top-10
Outcome and session steps
GTR
Rocchio Session (oracle)
Relative frequency
HaRE (predictions)
Selettve feequency
BM25
HRE RM3 (predictions)
40
30-
10
1.10
13-50
51-100 101-250 251-500501-100 >1000
Neutral
Original BM25 GTR rank position
Step when max performance achieved
(a) Depth of the documents returned by HARE in the original retrieval results, in different depth in- terval buckets. Results are averages over all BEIR datasets.
(b) Outcome of Rocchio sessions (oracle) com- pared to HARE's and RM3's predictions, function the steps required achieve the max- imum score. Averages over all BEIR datascts.
Figure 4: Analysis of BEIR tasks results.
With HRE, performance starts saturate. However, HARE outperforms HRE by 1.4 nDCG points, scoring on average 66.7 documents vs. the 17.5 of HRE. Note that HRE's maximum performance 0.509/0.510, at k 40, thus is never near HARE at any retrieval depth. HARE's performance is comparable to MonoT5, the current SOTA: better on all datasets average by 0.3 points and worse on zero-shot only, by 0.1 points. However, HARE scores 15X fewer documents. A conservative estimate shows a consequent 50% latency reduction (cf. A..I. Furthermore, HARE's in-domain performance (0.483 on MS MARCO) keeps improving and 8.5 points better than MonoT5. HARE has the best performance on 8 datasets (5 for M5noTS). We also evaluate a variant of the HRE search agent based on RM3 (Jaleel et al. 20044] Pal al. (013) robust pseudo relevance feedback query expansion method (Lvv & Zhai 2009] Miao et al. (012), which replaces T5-Q as the query expander. At each step, we pick the highest scoring term based on the RM3 score and add the selected term to the previous query with a '+' operator. The RM3 search agent is also effective, it improves over HRE but it does not perform as well as HARE, the reason being that does not pull in enough new documents (33.4).
The last column in Table I reports an oracle headroom estimate. This is obtained by running the same Rocchio Session algorithm used to produce T5-Q's training data (55.1) at inference time. As the numbers show, there is substantial room for improvement. In the next section we continue with an in-depth analysis and open questions.
5.4 QUALITATIVE ANALYSIS
Figure 4a plots the average depth of the documents in HARE's final top-10, all BEIR tasks in the retrieval results from BM25, and GTR, for the original query. HARE digs deep in the original retrievers rankings, even beyond position 1000: 16.3% of HARE top-10 does for BM25, and 6.9% for GTR. In this respect, HARE extends the finding of (Adolphs et al. 2022) to neural retrievers.
Figure 4b looks at the outcomes of HARE and HRE-RM3 episodes, compared to oracle sessions. 49% of the time HARE doesn't i change the outcome (RM3, 52.8), 14% of the results are worse for both, 21 % of the examples are resolved at the initial query for HARE (18.9 for RM3). However, 16% are improved by HARE (14 for RM3) and 8.3% need two or more steps. Table in Appendix, looks in detail at an example HARE win at step 2: 'what do you use dtp for +software +publishing'. Another, 'when did rosalind franklin take ray pictures of dna +52 +taken +franklin +photo' needs four steps. A single step one, but particularly transparent semantically is 'what is the age for joining aarp +requirements' Hence, find evidence of multistep inference and interpretable actions. Compared to HRE-RM3. HARE explores more documents in fewer steps. This is in part due to RM3 term weighting over-relying the query. For example, RM3 needs three refinements solve the query 'what make up the pistil in the female flower', '+pistil +female +stigma', while HARE solves it in with "ovarr"".
8

---

Under review as a conference paper at ICLR 2023
T5-R BM25-100 Large
TS-R BM25-100 11B
Environment
T5-R
T5-Q Large
T3-Q 11B
T5-R
T3-Q Large
T5-Q 11B
BM25
0.437
0,450
0.447
0,439
0,449
0,456
GTR
0.467
0,491
0,493
0,472
0,493
0,495
HRE 0.506
0.506
0.507
0.506
0.510
0,511
Table 2: Average nDCG@ 10 on BEIR. "T5-R BM25-100 Large" and 'T5-R BM25-100 11B' are, respectively, T5-Large and T5-v1.I-XXL reranker models trained on the Top 100 BM25 documents from MS MARCO. T5-Q Large and T5-Q 1IB are L5-Large and T5-11B agent models trained on data generated via the high-throughput Rocchio Session process (HT, cf. $5.1
We find that the HARE learns only use '+', and completely ignores other operators. Part of the problem may be an unbalanced learning task for T5-Q ('+' covers 83% of training). One way to make the task more expressive and balanced would be defining more operators. Lucene, for exam- ple, makes available several other operators including proximity, phrase and fuzzy match, and more. More generally, while interpretable, such operators are also rigid in their strict syntactic implemen- tation in traditional search architectures. An interesting direction to explore is that of implementing such operators
semantic framework, that is via neural networks, combining transparency and flexibility. SPAR's ' approach to modeling phrase matches (Chen et al., 202T), for instance, is one step in this direction. Another possible limitation is the lack of title information in the training data, as more structure in the data may partition the learning space in more interesting ways. The importance of the document title, for one, is well-known in IR.
In early development phases on MS MARCO we trained several, T5-R and T5-Q, models using different configurations. We first trained T5-R models with the top 100 documents from BM25. We call these models 'T5-R BM25-100', The T5-R model is used to generate training data for T5-Q, but it is also paired with the trained T5-Q model at inference time. Thus, the T5-R model needs to be robust when faced with documents originating from deeper than at training time. Larger TS-R models seem more robust in this respect, consistently with previous findings (Ni et al.) 2021 Rosa al., 2022). Similarly, larger T5-Q models seem more robust when training data generated by the Rocchio Session procedure. Some of those steps are genuinely meaningful, some are spurious actions with little chance of being learnable. Eventually, we settled on the largest models available and trained the T5-R models with the top 1000 documents from BM25. Table P provides a sample of these explorations, evaluated on the BEIR dataset as an ablation study.
the noisy
There are still open questions on how to properly train these models. For instance, it is apparent that our reranker is not as robust as as we would hope for the document depth that is usually explored by agents. Figure (ajureeaalllrryy shows performance declining at k>550. This may, at least partially, explain why we don't squeeze more performance from the existing headroom. A natural option, despite the negative findings of (Adolphs et al. 2022 is joint reinforcement learning of the agent.
6 CONCLUSION
In this paper extended the learning to search (L2S) framework to hybrid environments. In our approach, we simply combine dense and sparse retrievers, in what we call a hybrid retrieval environ- ment (HRE), and leave results aggregation to reranker which operates efficiently, only the very top retrieved results. Our experiments show that our search environment, while simple, is competi- tive with respect to other hybrid proposals based on more complex design, relying reranking retrieval results very deeply. Our search agent, HARE, learns to explore the indexed document collection deeply, but nimbly, keeping the number of documents to rescore low. HARE leverages discrete query refinement steps which produce SOTA-level retrieval performance in competitive zero-shot task, without degrading in-domain performance. Furthermore, we find evidence of effec- tive multi-step inference, and the actions of the search agent are often easy to interpret and intuitive. Overall, we are inclined to conclude that search agents can support the investigation of performant information retrieval systems, capable of generalization. At the same time, they provide plenty of unexplored opportunities, and challenges, on the architectural and learning side.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Leonard Adolphs, Benjamin Börschinger, Christian Buck, Michelle Chen Huebscher, Massimil- iano Ciaramita, Lasse Espeholt, Thomas Hofmann, Yannic Kilcher, Sascha Rothe, Pier Giuseppe Sessa, and Lierni Sestorain. Boosting search engines with interactive agents. Transactions on Machine Learning Research, 2022. URL bttps://openrev// httpi/ewww.ee..oett.eeee www.:neenfforeeeee
02bPmmB61g
Tom Brown, Benjamin Mann, Nick Ryder. Melanie Subbiah, Jared D Kaplan. Prafulla Dhariwal, Arvind Ncelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Sebastian Bruch, Xuanhui Wang, Mike Bendersky, and Mare Najork. An analysis of the softmax cross entropy loss for learning-to tr-nk with binary relevance. In Proceedings of the 2019 ACM SIGIR International Conference on the Theory of Information Retrieval (ICTIR 20/9), pp. 75-78, 2019.
Christian Buck, Jannis Bulian, Massimiliano Ciaramita, Wojciech Gajewski, Andrea Gesmundo, Neil Houlsby, and Wei Wang. Ask the right questions: Active question reformulation with re- inforcement learning. In International Conference on Learning Representations, 2018. URL
https::/opennevier Lttp:areeeeee..ete/oooooeoll--e- S0cc/ S1CCh2-CC
Tao Chen, Mingyang Zhang, Jing Lu, Michael Bendersky, and Mare Najork. Out-of-domain se- mantics to the rescue! zero-shot hybrid retrieval models. In Advances in Information Re- frieval: 44th European Conference on IR Research, ECIR 2022, Suavanger, Norway, April 10-14, 2022, Proceedings, Part I, pp. 95-110, 2022. URL htthhhtpps/d/dm .ttg/10.1007. 978-3-030-997366
Xilun Chen, Kushal Lakhotia, Barlas Oguz, Anchit Gupta, Patrick Lewis, Stan Peshterliev, Yashar Mehdad, Sonal Gupta, and Wen tau Yih. Salient phrase aware dense retrieval: Can a dense retriever imitate a sparse one? arXiv preprint arXiv:2110.06918, 2021.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin. Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev. Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph. Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Bren- nan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier- Hellstern,,, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways, 2022. URL /ectps://arx..e orq/ abs 2200222422..22 02311
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT; Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171-4186, 2019.
Thibault Formal, Carlos Lassance, Benjamin Piwowarski, and Stéphane Clinchant. Splade v2:
Sparse lexical and expansion model for information retrieval, 2021a. URL tttps://aaxxiv
org/ org/abs/ 210.. 10086
Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. SPLADE: Sparse Lexical and Expansion for First Stage Ranking, pp. 2288 2292. Association for Computing Machinery, New York, NY, USA, 2021b. ISBN 978 145088037. URL https:
3404 8.04835.00 3463098
10

---

Under review as a conference paper at ICLR 2023
Thibault Formal, Carlos Lassance, Benjamin Piwowarski, and Stéphane Clinchant. From distillation to hard negative sampling: Making sparse neural ir models more effective. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '22, pp. 2353-2359, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 45834333.. doi: 10.1 10.1145/547449533318877
URL https://doi.
org/10. 0tc//00.1165/377495..33 3531857
Xiaoxiao Guo, Tim Klinger, Clemens Rosenbaum, Joseph P. Bigus, Murray Campbell, Ban Kawas, Kartik Talamadupula, Gerry Tesauro, and Satinder Singh. Learning to query, reason, and answer questions on ambiguous texts. In International Conference on Learning Representations, 2017.
URL https: /tttps:://ppenreieew nett http:///eppppaeeeeeeeeeeeereerrr forum?id==:O-tt355
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming- Wei Chang. REALM: Retrieval- augmented language model pre-training. https:/arrti.orr/aab2200....0000 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network, 2015.
URL httt::t/p//riitio org/ abs/ 1503. 02531
Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. Unsupervised dense information retrieval with contrastive learning. 2021. URL http://aaxiiv.rooo abs/ 2112. 09118
Rolf Jagerman, Xuanhui Wang, Honglei Zhuang, Zhen Qin, Mike Bendersky, and Mare Najork. Rax: Composable learning-to-rank using jax. In Proceedings of the 28th ACM SIGKDD Interna- tional Conference on Knowledge Discovery & Data Mining, 2022.
Nasreen Jaleel, James Allan, W. Croft, Fernando Diaz, Leah Larkey, Xiaoyan Li, Mark Smucker, and Courtney Wade. Umass at tree 2004: Novelty and hard. In TREC, 01 2004.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), 2020.
Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development Information Retrieval, SIGIR '20, pp. 39-48, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781 9781450380164 3401075. URL URL
doi: 10.1145/3397271.
11t.:1..1111111111111 3401075
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmentedd generation for knowledge-inennsive nip tasks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Pro- cessing Systems, volume 33, pp. 9459-94744 2020.
Patrick Lewis, Pontus Stenetorp, and Sebastian Riedel. Question and answer test-train overlap in open-domain question answering datasets. In Proceedings the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, 2021.
Yuanhua Lv and ChengXiang Zhai. comparative study of methods for estimating query language models with pseudo feedback. In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM '09, pp. 1895-1898,,.88888111181881118818 New York, NY, USA, 2009. Association for Computing Machinery. ISBN 978 17718655551122 123. doi: 10.1 11445///44993.16466655 URL https:
7/doi. (ebii.org/000 1114411111553333 1646259
Ji Ma, Ivan Korotkov, Yinfei Yang. Keith Hall, and Ryan McDonald. Zero-shot neural passage trieval via ttraen-targeted synthetic question generation. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp- 1075-1088 Online, April 2021. Association for Computational Linguistics. doi: 10.18653/v1/
wel..eal-main... URL htt.hhtpsscc. //acl anthalooyy.org///a.... eaal meacl 92

---

Under review as a conference paper at ICLR 2023
Jun Miao, Jimmy Xiangji Huang, and Zheng Ye.
rocchio's model for pseudo
relevance. In Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 12, pp. 535-544, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450314725. doi: 10.114552244828322488566
htRlhhtps:///dde http:///oo.ooo1..11111 01/1//00111552228283338 RAA.44888822883885 2348356
Niklas Muennighoff. Sgpt: Gpt sentence embeddings for semantic search. arXiv preprint arXiv:2202.08904, 2022.
Reiichiro Nakano, Jacob Hilton, S. Arun Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Floundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman. Webgpt: with human feedback. ArXiv, abs/2 2021.
Browser-assisted question-answenn
Tri Nguyen, Mir Rosenberg, Xia Song. Jianfeng Gao, Saurabh Tiwary, Ran- gan Majumder, and Li Deng. MS MARCO: A Human Generated MA- chine Reading COmprehension Dataset. CoRR, November 2016. wwwpw/wwwwooo....twwww.wwwwww.we ms marco human generated machine rescing--coppeehennne
URL
https:
dataset/
Jianmo Ni, Chen Qu, Jing Lu, Zhuyun Dai, Gustavo Hernández Abrego, Ji Ma, Vincent Y. Zhao, Yi Luan, Keith B. Hall, Ming- Wei Chang, and Yinfei Yang. Large dual encoders are generalizable retrievers. CoRR, abs/2 12.07899, 2021. /ttphttss://axiii org/ abs///b///// 2112. 07899
Rodrigo Nogueira and Kyunghyun Cho. W:Xiv:1901.04085 2019.
Passage re-ranking with bert.
arXiv preprint
Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Document ranking with a pretrained sequence-to sequence model. CoRR, abs/2003.06713, 2020a. URL htttts::/aax.i..ottttt http://aaax..vo.orr//////200
06713
Rodrigo Nogucira, Zhiying Jiang, Ronak Pradeep, and Jimmy Lin. Document ranking with a pre- trained sertennce-t-scqueene model. In Findings of the Association for Computational Linguis- tics: EMNLP 2020, pp. 708-718, Online, November 2020b. Association for Computational Lin- .orplllogooorrgo//oooooooooo
guisties. doi: 1t1.///////220..nnniiii
findingg--emll.663. URL
2020. findingg-eengnmllppp.... 63
Dipasree Pal, Mandar Mitra, and Kalyankumar Datta. Query expansion using term distribution and term association. CoRR, has/1303.066, 03 2013. URL http:://aax....rr/ab////////////
0667
Peng Qi, Xiaowen Lin, Leo Mehr, Zijian Wang, and Christopher D. Manning. Answering com- plex open-domain questions through iterative query generation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language P Processing (EMNLP-IJCNLP), November 2019. URL httppp///ccaatttoooo.oooo//////
Peng Qi, Haejun Lee, OghenetegiriTGSido, and Christopher D. Manning. Answering open- domain questions of varying reasoning steps from text. EMNLP, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with unified text-to- text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020. URL http: 7/jmlr. http://ppppppppps///./a
html
Ruiyang Ren, Yingqi Qu, Jing Liu, Wayne Xin Zhao, Qifei Wu, Yuchen Ding, Hua Wu, Haifeng Wang, and Ji-Rong Wen. A thorough examination on zero-shot dense retrieval, 2022. URL
https://arxiz: o wwt//as////ooooooooot.g//t..aera 2204 .1.00.11277 12755
Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends in Information Rerrieval, 3(4):333-388 2009. ISSN 1554-0669. doi:
URL TRI.http://dd
12

---

Under review as a conference paper at ICLR 2023
J. J. Rocchio. Relevance feedback in information retrieval. In G. Salton (ed.), The Smart retrieval system experiments in automatic document processing, pp. 313-323. Englewood Cliffs, NJ: Prentice- Hall, 1971. URL
files httee///mmeemm////ee
X
pdf
Guilherme Moraes Rosa, Luiz Bonifacio, Vitor Jeronymo, Hugo Abonizio, Marzieh Fadaee, Roberto Lotufo, and Rodrigo Nogueira. No parameter left behind: How distillation and model size affect zero-shot retrieval. arXiv preprint arXiv:2206.0287. 2022.
Daniel M. Russell. The Joy of Search: A Google Insider's Guide to Going Beyond the Basics. The MIT Press, 2019.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. ArXiv, abs/1910.01108, 2019.
Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. Col- BERTv2: Effective and efficient retrieval via lightweight late interaction. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguis-
fics:
Human Language Technologies, pp. 3715-3734 Seattle, United States, July 2022. Asso- URL https:
ciation for Computational Linguistics. doi: 10. 1202.///002...aaammmmmm
crg/2022. //aclanthologee www.aa/howooo....g/22222.... naacl mw... 272
Christopher Sciavolino, Zexuan Zhong, Jinhyuk Lee, and Danqi Chen. Simple entity-centric ques- tions challenge dense retrievers. Proceedings of the 202/ Conference on Empirical Methods in Natural Language Processing, pp. 6138-6148, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 10. 10.18663/112022.emllp---o 496. URL httpp:://acaaataolllogoooooo
org/ 20211 www.p-nnnnaaaaa. 496
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner prod- uct search (mips). In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Wein- berger (eds.), Advances Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL
mew.eeeeddiinnn..ee.e..ee...eeee wwtps.ccpppppee cc./paper/2011//1ee 3ICCeei:00B3344333eee3333 Papp:e700000PPppppppppp pdf
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. BEIR: A heterogenous benchmark for zero-shot evaluation of information retrieval models. CoRR, abs/2104.08863,, 2021. URL URthtt.ss://axiiv..oo
abs/ 04.04440 08663
Lee Xiong, Chenyan Xiong. Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Amold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. In International Conference on Learning Representutions, 2021. URL https: //openreview. net. http://oooummdddeeefeffee/e
Jingtao Zhan, Xiaohui Xie, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma. Evaluating extrapolation performance of dense retrieval. In CIKM, 2022.
Yunchang Zhu, Liang Pang, Yanyan Lan, Huawei Shen, and Xueqi Cheng. Adaptive information seeking for open-domain question answering. In EMNLP, 2021.
Honglei Zhuang. Zhen Qin, Rolf Jagerman, Kai Hui, Ji Ma, Jing Lu, Jianmo Ni, Xuanhui Wang, and Michael Bendersky. Rankt5: Fine-tuning 15 for text ranking with ranking losses. CORR, 2022. doi:
httthhttp///aae org/ wttg/bss////oooooooo/o.ooo...ere 2210.2202 10634
13

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
query
query expansion (target)
NLL
what is the age for hitting puberty trigeminal definition
around
75.6
a
71.2
is rhinitis painful
common '6
70.0
how many glasses of water is required a day how soon do symptoms show up for hiv
every"4
67.5
acute"4 4
67.5
the collection film cast
+collection
0.5
what kind of fossil is made by an imprint?
+ fossil
1.5
who invented corn flakes
+john
1.7
what does gelastic mean what acha
+ +laughter
1.7
+hockey
1.8
Table 3: Examples from the evaluation set with highest respectively lowest negative log-likelihood (NLL) using the trained HARE search agent.
A.1 LATENCY
We estimate latency by measuring the wall clock time of each individual step for HaRE, and MonoT5, running the same setup; i.e., using the same sub-systems and configurations. For both MonoT5 and HARE we don't include the full collection indexing times which are performed once, and focus on inference.
For MonoT5, we consider only the BM25 retrieval step, plus the T5-R inference to rerank the top 1000 documents returned. We call this Mo For HARE, we count: BM25 retrieval + GTR retrieval T5-R inference + 4x (T5-Q inference BM25 retrieval BM25 Top-K retrieval T5-R inference). We call this LHARE- The resulting ratio is
LHRRE 0.51.
LonoTTS
Notice that, while we count the T5-R reranking latency in full for each step, in practice the same documents are often retrieved multiple times and caching can be used effectively.
More importantly, for simplicity sake, in the current implementation, Lucene index for the GTR Top-IK sub-corpus. Instead, to search on GTR's Top- corpus, we search on the full collection but restrict the query the Top- documents by means of Lucene's 'id' query operator. Hence, we append Ik document ids to the query, thus constraining retrieval to Top- 1K only. This turns to be by far the slowest step for HARE. A conservative back of the envelope calculation shows that by refactoring the search step by indexing separately Top- 1K for each episode and executing separate BM25 retrieval steps, the the full and Top- 1K collections, would overall latency by another 50%.
don't create a separate
In general, while more complex, HARE'S architecture offer's many options for refactoring and optimization.
A.2 EXAMPLES
14

---

Under review as a conference paper at ICLR 2023
Query and Results
Score
9o what's the difference between c++ and java The difference between C#/Java and C is too big, but the differences between C#/Java and C++ are easier to pick and the most important, other than said updates to the language, are the adoption of pure OOP approach to programming.
0.0
d1
d2 JavaScript is an interpreted computer programming language. The main difference between Java and JavaScript is that while Java is programming language, JavaScript scripting language. It prototype- baseed scripting language that is dynamic, weakly typed, and has first-class functions. However, like Java, JavaScript is heavily influenced by the programming language.
what's 's the difference between c++ and java +lanuaage q1
0.6
d1
The most important difference is that Java is memory-safe language, whereas C++ not. This means that errors in Java programs are detected defined ways; for example, attempting bad cast indexing an array out of bounds results in ex- ception.
d2 Java (bottom) is contrasted with C/C++ (top). Unlike C/C++, which is compiled into machine language for specific hardware platform, Java programs are compiled into an intermediate bytecode language. The bytecode then compiled into ma- chine language by a runtime program called the Java Virtual Machine (JVM). Unlike C/C++, which is compiled into machine language for a specific hardware platform, Java programs are compiled into an intermediate bytecode language. The bytecode then compiled into machine language by a runtime program called the Java Virtual Machine (JVM).
what's the difference between c++ and java tlanguage +platform Q2
1.0
di C++ is an evolution to C. Which was a system programming language. C++ Added many features the language make it object oriented. It became the mainstream programming language for that reason. Java is an evolution of C++, with different goals cross platform for instance It remove some of the features that make C++ so hard to learn. Simplify others and remove others.
d2
Java (bottom) is contrasted with C/C++ (top). Unlike C/C++, which is compiled into machine language for specific hardware platform, Java programs are compiled into an intermediate bytecode language. The bytecode then compiled into ma- chine language by runtime program called the Java Virtual Machine (JVM). Unlike C/C++, which is compiled into machine language for a specific hardware platform, Java programs are compiled into intermediate bytecode language. The bytecode is then compiled into machine language by a runtime program called the Java Virtual Machine (JVM).
Table Example of multistep gold search session that forms the training data for T5-Q. This is one of few examples from MS MARCO where more than one document is annotated as relevant. The first set of results are on topic but too generic, and slightly off the mark: the first document talks also about c#f, the second document is about JavaScript. By restricting document to those containing the term 'language' relevant document is in 2nd position the results from step Here new term discovered, 'platform', which was not present in the results for go (it does not occurr in any of the top 10 results, which we omit for simplicity). By further refining the query with +platform, the second-step results contain the two relevant documents at the top and and the session achieves full score.
15

---

Under review as a conference paper at ICLR 2023
Query and Results
Score
9o what do you use dtp for The Dynamic Trunking Protocol (DTP) is proprictary networking protocol devel- oped by Cisco Systems for the purpose of negotiating trunking on a link between two VLAN-aware switches, and for negotiating the type of trunking encapsulation to be used. It works on Layer 2 of the OSI model.
0.0
d1
d2 DTP (diptheria, tetanus toxoids and pertussis) Vaccine Adsorbed (For Pediatric Use) is a vaccine used for active immunization of children up to age 7 years against diph- theria, tetanus, and pertussis (whooping cough) simultaneously. DTP is available in generic form.
dg Page Layout Software (Generally Known as DTP Software). Since page layout soft- ware commonly known as DTP software, this can lead to some confusion but now you know better. These software programs are the workhorses of DTP and they do exactly what you might think they would in accordance with the name.
what do you use dtp for +software
0.0
d1 the operating systems main interface screen. desktop publishing. DTP; application software and hardware system that involves mixing text and graphics to produce high quality output for commercial printing using microcomputer and mouse, scanner, digital cameras, laser or ink jet printer, and dip software.
d2 Page Layout Software (Generally Known as DTP Software). Since page layout soft- ware is commonly known as DTP software, this can lead to some confusion but now you know better. These software programs are workhorses DTP and they exactly what you might think they would in accordance with the name.
Q2 what do you dtp for +software +publishing d1 Desktop publishing. Desktop publishing (abbreviated DTP) is the creation docu- ments using page layout skills personal computer primarily for print. Desktop publishing software can generate layouts and produce typographic quality text and images comparable traditional typography and printing.
1.0
d2 Scribus, an open source desktop publishing application. Desktop publishing (ab- breviated DTP) the creation of documents using page layout skills on personal computer primarily for print. Desktop publishing software can generate layouts and produce typographic quality text and images comparable to traditional typography and printing.
Table 5: Example of multistep search session performed by HARE. The first set of results gets an nDCG score of 0.0, and the top 2 seem clearly wrong. Curiously, none the top-10 documents mentions the word "publishing". HARE first selects the refinement '+software". The corresponding results, while still scoring 0, lead to the presence of the term 'publishing' which used by HARE as the next refinement 'ppbblishin',, which leads to full nDCG score the next round.
16


Reviews:
[{"review_id": "VSrBP9LyFe9", "reviewer": "Reviewer_iyX7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper extends the learning-to-search (L2S) framework to hybrid environments. The paper simply combines two dense and sparse retrievers and a reranker to construct a hybrid retrieval environment (HRE). Based on the hybrid environment HRE, this paper conducts a multi-step retrieval by a search agent HaRE, in which each step involves a reranker to rank the newly top-retrieved and previously collected documents, and a query expander to reformulate a query for the next step. Experimental results show that HRE outperforms its baseline retrievers and some hybrid methods. Besides, HaRE produces state-of-the-art performance on both zero-shot and in-domain evaluations and keeps the number of documents to rescore low.", "summary_of_the_review": "The proposed method is interesting, but has limited novelty, is similar to many missing related works, and unfair comparisons with baselines do not fully demonstrate its effectiveness.\n\n1. Related work on query expansion and pseudo-relevant feedback is not discussed.\n2. In Section 4.3, why GTR is used only one time? And after the first step, it is better to explain why the top 1000 documents from GTR and the entire corpus are simultaneously retrieved by BM25.\n3. Minor Issues\n  a. The third paragraph of the introduction,  “implicit relevance feedback” -> “pseudo relevance feedback”?\n  b. No caption in Figure 1\n  c. Equation 2 is hard to understand", "strength_and_weaknesses": "Strengths:\n\n1. The proposed method sounds reasonable.\n2. The proposed method achieved SOTA performance on both zero-shot and in-domain evaluations and keeps the number of documents to rescore low.\n3. The paper is easy to follow.\n\nWeaknesses:\n\n1. Considering Adolphs et al., 2022, the contribution of the hybrid retrieval environment appears too marginal, especially the simple combination of sparse retrieval and dense retrieval results, which has been explored by many works.\n\n  [1] Karpukhin, Vladimir, et al. \"Dense Passage Retrieval for Open-Domain Question Answering.\" EMNLP. 2020.\n\n  [2] Sidiropoulos, Georgios, et al. \"Combining Lexical and Dense Retrieval for Computationally Efficient Multi-hop Question Answering.\" Proceedings of the Second Workshop on Simple and Efficient Natural Language Processing. 2021.\n\n  [3] Gangi Reddy, Revanth, et al. \"Synthetic Target Domain Supervision for Open Retrieval QA.\" SIGIR. 2021.\n\n  [4] Chen, Tao, et al. \"Out-of-Domain Semantics to the Rescue! Zero-Shot Hybrid Retrieval Models.\" ECIR. Springer, Cham, 2022.\n\n2. There are many related works on iterative retrieval in the open-domain QA that have not been mentioned and compared, such as:\n\n  [1] Guo, Xiaoxiao, et al. \"Learning to query, reason, and answer questions on ambiguous texts.\" ICLR. 2016.\n\n  [2] Qi, Peng, et al. \"Answering Complex Open-domain Questions Through Iterative Query Generation.\" EMNLP. 2019.\n\n  [3] Qi, Peng, et al. \"Answering Open-Domain Questions of Varying Reasoning Steps from Text.\" EMNLP. 2021.\n\n  [4] Zhu, Yunchang, et al. \"Adaptive Information Seeking for Open-Domain Question Answering.\" EMNLP. 2021.\n\n  [5] Nakano, Reiichiro, et al. \"WebGPT: Browser-assisted question-answering with human feedback.\" arXiv preprint arXiv:2112.09332 (2021).\n\n3. Some comparisons with the baseline experimental results do not seem to be fair, especially in terms of model size, and it is recommended to provide detailed comparisons of parametric quantities. Besides, in Fig. 2(b), as far as I know, ColBERTv2 and SPLADE++ are dense and sparse retrieval, respectively, not hybrid retrieval, and in addition, neither of them has re-ranking, so it is not fair to compare them with HRE. Also, in Table 1, although I believe that iterative agents are better than single-step retrieval environments, the retrieval depth used by the environments is too small to adequately account for this. It is recommended that the retrieval depth used by the environment be set to 5*k or the average number of doc reranked of the agents.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DNErHMbcslS", "reviewer": "Reviewer_PtJd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper combines the methods proposed in the works of Rosa et al., 2022 [1] and Adolphs et al., 2022 [2] to achieve near-state-of-the-art on the BEIR benchmark with promising in-domain performance. Specifically, as in [1], the authors use the sparse retriever and dense retrieval to retrieve the set of relevant documents which are sorted using a cross-encoder reranker named T5-R, which they call Hybrid Retrieval Environment (HRE). After the initial retrieval, the query is augmented by a query refinement model named T5-Q proposed in [2]. T5-Q is trained to generate an operator with a term, where the term is from the top-ranked documents and the operator is whether to (1) limit the retrieval to the chosen term, (2) exclude the term from the retrieval results, or (3) boost the BM25 term weight of the chosen term. The augmented query is used to run another round of BM25 retrieval, and the newly retrieved documents together with the top-reranked documents serve as the new set of documents to be reranked. The refinement is done iteratively (5 times in the experiments).\n\n**References**\n\n[1] Guilherme Moraes Rosa, Luiz Bonifacio, Vitor Jeronymo, Hugo Abonizio, Marzieh Fadaee, Roberto Lotufo, and Rodrigo Nogueira.  No parameter left behind: How distillation and model size affect zero-shot retrieval. arXiv preprint arXiv:2206.02873, 2022.\n\n[2] Leonard Adolphs, Benjamin B ̈orschinger, Christian Buck, Michelle Chen Huebscher, Massimil- iano Ciaramita, Lasse Espeholt, Thomas Hofmann, Yannic Kilcher, Sascha Rothe, Pier Giuseppe Sessa, and Lierni Sestorain. Boosting search engines with interactive agents. Transactions on Machine Learning Research, 2022. URL https://openreview.net/forum?id=0ZbPmmB61g.", "summary_of_the_review": "While the paper is meaningful in that it shows the effectiveness of using dense and hybrid retrieval with an iterative query-expansion method, its technical novelty is limited as the proposed method is a combination of the methods proposed in two previous works. Considering the necessity of the complicated training data creation process for T5-Q and the pipeline approach of iterative retrieval-reranking-query refinement, the advantage of the proposed method does not seem significant compared to the simple state-of-the-art method. While the authors emphasize the reduced number of reranked documents as an advantage, whether it actually results in decreased latency remains a question for now.", "strength_and_weaknesses": "**Strengths**\n\n- The paper is meaningful in that it shows the combination of dense and hybrid retrieval with an iterative query-expansion method is robust on both in-domain and zero-shot retrieval.\n\n**Weaknesses**\n\n- The proposed method is a combination of the methods of previous works [1] and [2], which limits the technical novelty of the paper.\n- While the authors emphasize that the proposed system reranks one order of magnitude smaller number of documents compared to the state-of-the-art [1], pointing out that it is time-consuming to cross-encoder reranking of 1000 documents as in [1], it is unclear whether this leads to actual latency improvement of the proposed system because the authors do not report the end-to-end retrieval latency. Since the proposed system uses iterative query refinement (five times) which generates the augmented query based on the previous top-ranked documents, the latency of this step would not be negligible. The authors should report the actual latency in order to show the superiority of the proposed system in terms of time cost.\n- While the proposed method achieves near-state-of-the-art zero-shot (BEIR) retrieval performance while achieving much higher in-domain (MS MARCO) retrieval performance, it uses a much more complicated pipeline approach for both training and inference than the state-of-the-art method. The creation of the training data for T5-Q using Rocchio Session would be time-consuming considering that it requires calculating nDCG on multiple (M=100) candidate augmented queries to generate one label for a query. Considering this, the gain in retrieval performance seems insufficient to claim a significant advantage over the method of [1].", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3yldSnINoyn", "reviewer": "Reviewer_ettj", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Adolphs et al., 2022 propose to train a question refinement component as a search agent — a sparse retriever (BM25) first returns a list of results, and then the question refiner edits the original question (add/remove keyword or changes BM25 weight) to get a list of new results, mimicking human agent behavior. \n\nThis paper is an extension of Adolphs et al., by (1) using the combination of a dense retriever (GTR) and a sparse retriever (BM25) for the initial list and (2) using a cross-encoder for reranking. The experiment results show that the hybrid retriever is much better than just using either GTR or BM25 with the reranker. \n\nThen the authors conduct comprehensive experiments towards a series baseline, including the state-of-the-art MonoT5. The proposed HARE is better than other models using different environments or agents, and it achieved comparable performance to MonoT5. The authors also conduct some analysis on the agent behavior; for example, they found that HARE learns to use “adding keywords” the most.", "summary_of_the_review": "If my understanding is correct, the main contribution lies in the use of \"hybrid environment\" -- combing dense and sparse retrievers and rerankers. Also, there are some flaws in the experiments -- the authors should really compare the retrieval time of different models instead of the number of retrieved documents. Thus I am leaning towards rejection.", "strength_and_weaknesses": "## Strength\n\nThe authors present a finding that using the combination of dense and sparse agents in a retrieve-then-rerank setting leads to much better performance than a single agent (with fewer than 100 retrieved documents). The final model (hybrid search environment + query refinement) leads to a state-of-the-art model. The ablation study and analysis are comprehensive, showing the strength of the proposed hybrid environment.\n\n## Weakness\n\nIf my understanding is correct, the main contribution of the paper is to propose using sparse+dense retrievers +reranking at the first step. Though I don’t think previous works have reported this before, either combing sparse and dense retrievers [1] or using rerankers is not new. \n\nThe authors also sell the hybrid environment as it does not need to retrieve hundreds or thousands of documents for reranking, compared to state-of-the-art models like MonoT5. However, it is not fair to only compare the document numbers — first, sparse and dense retrievers have very different efficiencies; second, the proposed model has a multi-step question refinement procedure, which makes it much slower. To truly show the proposed model’s strength, the authors should really show the retrieval time per query of each model. \n\n\n[1] Ma et al., 2021. A Replication Study of Dense Passage Retriever. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject