# Selecting which Dense Retriever to use for Zero-Shot Search

Ekaterina Khramtsova  The University of Queensland4072 St
LuciaBrisbaneQLDAustralia<EMAIL_ADDRESS>,  Shengyao Zhuang  The
University of Queensland4072 St LuciaBrisbaneQLDAustralia<EMAIL_ADDRESS>,
Mahsa Baktashmotlagh  The University of Queensland4072 St
LuciaBrisbaneQLDAustralia<EMAIL_ADDRESS>,  Xi Wang
NeusoftShenyangChina<EMAIL_ADDRESS>and  Guido Zuccon  The University of
Queensland4072 St LuciaBrisbaneQLDAustralia<EMAIL_ADDRESS>
(2023)

###### Abstract.

We propose the new problem of choosing which dense retrieval model to use when
searching on a new collection for which no labels are available, i.e. in a
zero-shot setting. Many dense retrieval models are readily available. Each
model however is characterized by very differing search effectiveness – not
just on the test portion of the datasets in which the dense representations
have been learned but, importantly, also across different datasets for which
data was not used to learn the dense representations. This is because dense
retrievers typically require training on a large amount of labeled data to
achieve satisfactory search effectiveness in a specific dataset or domain.
Moreover, effectiveness gains obtained by dense retrievers on datasets for
which they are able to observe labels during training, do not necessarily
generalise to datasets that have not been observed during training.

This is however a hard problem: through empirical experimentation we show that
methods inspired by recent work in unsupervised performance evaluation with
the presence of domain shift in the area of computer vision and machine
learning are not effective for choosing highly performing dense retrievers in
our setup. The availability of reliable methods for the selection of dense
retrieval models in zero-shot settings that do not require the collection of
labels for evaluation would allow to streamline the widespread adoption of
dense retrieval. This is therefore an important new problem we believe the
information retrieval community should consider. Implementation of methods,
along with raw result files and analysis scripts are made publicly available
at https://www.github.com/<anonymized>

Model selection, Dense retrievers, Zero Shot Model Evaluation

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
1st International ACM SIGIR Conference on Information Retrieval in the Asia
Pacific; November 26–29, 2023; Beijing, China††booktitle: Proceedings of the
1st International ACM SIGIR Conference on Information Retrieval in the Asia
Pacific (SIGIR-AP ’23, November 26–29, 2023, Beijing, China††price:
15.00††doi: xxxxxx††isbn: 978-1-4503-8037-9/21/07††ccs: Information systems
Evaluation of retrieval results

##  1\. Introduction

Model analysis in zero-shot scenarios involves comparing and evaluating
different models based on their ability to generalize to new datasets, that
have not been seen during training. In many real-world settings, it may not be
possible to obtain judgments for these new datasets (which we refer to as the
target dataset), as labeling data can be expensive, time-consuming and
sometimes even impossible (e.g., in medical or legal domain, access to labeled
data can be restricted due to privacy concerns or regulations). Therefore, the
reliance on standard evaluation practices and metrics on these new dataset is
not possible.

Furthermore, the data distribution in the target dataset is often different
from the data distribution in the training dataset: this is also known as the
domain shift problem. This can have a significant impact on the effectiveness
of the model, as it may not be able to generalize to the new domain/target
dataset (Chen et al., 2022). Therefore, judging the model based exclusively on
its effectiveness on the training dataset might result in inaccurate
predictions.

The issue of data distribution shifting has gained increasing attention in the
field of information retrieval (IR). This is largely due to the recognition
that dense retrievers (DRs) based on pre-trained language models (PLMs) have
shown exceptional effectiveness on in-domain data. However, recent studies
(Thakur et al., 2021; Ren et al., 2022; Zhuang and Zuccon, 2021, 2022) have
also highlighted the problem of domain shift for these DRs, whereby the
effectiveness of a DR varies depending on the target domain, which may differ
from the domain of the data it was trained on. This poses a significant
challenge to the practical deployment of DRs in real-world applications.
Researchers in the IR community are focusing on developing novel pre-training
or fine-tuning techniques to improve the zero-shot ability of DR models
(Gururangan et al., 2020; Wang et al., 2022a; Ma et al., 2021; Lin et al.,
2023). However, the analysis of the leaderboard of a common zero-shot dense
retrieval benchmark dataset, BEIR (Thakur et al., 2021), reveals that the
effectiveness of different DR models varies across different domains/datasets,
and no clear one-size-fits-all DR has emerged. Given the rapid development of
new DR models, it is crucial to explore an alternative research direction.
Rather than attempting to train a generalized DR model that performs well
across all domains and datasets, we propose to develop methods that search
engine practitioners can reliably use to select a DR model from an existing
pool of DR checkpoints that performs best on their application’s domain or
dataset. This line of research is vital for the practical deployment of DRs in
real-world scenarios.

In this paper, we introduce, formalize and operationalize the problem of model
selection in IR, which involves selecting the best DR model from a pool of
trained models, or alternatively ranking the pool based on a criterion that is
indicative of their effectiveness on the unlabeled target dataset. We
demonstrate the soundness of the problem by illustrating that the
effectiveness of a model varies across target datasets due to differences in
data quality, the nature of domain shift, and the evaluation metric employed,
as each metric prioritizes different aspects of model effectiveness. In other
words, a model might perform well on some datasets, while failing on others.
We further provide evidence that the performance of a model on the source
dataset is not always a reliable indicator of its effectiveness on target
datasets, highlighting the necessity for an alternative criterion specifically
tailored to each target dataset. An example of such a criterion is the
evaluation of the model’s level of uncertainty, with the hypothesis that
models with lower uncertainty are more likely to produce accurate predictions.

The goal of this paper is thus to provide an extensive overview of the current
state-of-the-art methods for model selection, which have been mostly developed
in the fields of computer vision and machine learning. We outline their
limitations and summarize the main challenges in their adaptation to IR tasks.
We further provide an outline of our findings along with associated
reflections and challenges, and propose possible future directions for
exploration. It is worth noting that while the problem of unsupervised model
selection has been explored in the general machine learning field, there has
been little to no exploration of this problem in the context of information
retrieval.

##  2\. Related Work

In this section, we will give an overview of the current state-of-the-art
methods of unsupervised model selection and its relation to IR. In particular,
we target the problem of selecting the best dense retriever model for the
datasets from BEIR collection, that contains a wide range of corpora from
diverse text retrieval tasks and domains for zero-shot evaluation.

###  2.1. Unsupervised Model Selection

The problem of Unsupervised Model Selection is actively researched in the
context of general deep learning tasks. It involves choosing the best model
for an unsupervised target dataset, that belongs to a distribution different
from the original training dataset.

Corneanu et al. (Corneanu et al., 2019) analyze various topological
statistics, calculated from the correlation matrix of the network’s
activations, and show that they are correlated with model generalizability.

You et al. (You et al., 2019) introduce Deep embedded validation (DEV)- a
method to obtain estimations of the target risk by assessing the likelihood of
each validation sample to belong to the target domain. The authors show that
the small value of DEV correspond to a large generalizability of the model and
can be therefore used for selecting the best performing model for the dataset
in hand.

Soft Neighborhood Density method (SND) was proposed by Saito et al. (Saito et
al., 2021) to evaluate the generalisability of the classifier networks by
measuring the quality of clustering via a relative distance of the neighboring
samples. The intuition is that the desired model should encode target samples
of the same class into dense neighborhoods. Another method of cluster
evaluation, called Topological Uncertainty, was proposed by Lacombe et al.
(Lacombe et al., 2021). For each class (or label), the authors create a
prototype of the topological activation footprint, and evaluate how different
is the embedding of each target sample from its closest prototype. Our
retrieval task is drastically different from classification: in our case,
well-performing model does not necessarily generate well-separated clusters in
their embedding space.

Neural Persistence measure, proposed by Rieck et al. (Rieck et al., 2019),
compares the networks based on the topological features of their last fully
connected layers. Despite showing a correlation with model generalizability,
Neural persistance-based ranking will provide the same result for all the
datasets, as it is purely weight-based and dataset-independent. Additionally,
for a fair comparison, Neural Persistence requires the same layer
dimensionality across models, which is not the case in our experimental setup.

###  2.2. Unsupervised OOD Performance Evaluation

The problem of unsupervised Out-Of-Ditribution (OOD) performance evaluation
involves estimating the performance of a model with the presence of domain
shift between the train and test data. Note that the experimental setup of
performance estimation is slightly different to model selection: here, only
one model is given, and the task is to predict its performance on several
target datasets.

The first group of methods analyzes the quality of model predictions through a
range of metrics, calculated from the network output. For example, Miller et
al. (Miller et al., 2021) show a positive correlation between in-domain and
out-of-domain performances (Method 1 in our analysis); Hendrycks et al.
(Hendrycks and Gimpel, 2017) use the statistics of softmax outputs to identify
misclassifications; Guillory et al. (Guillory et al., 2021) evaluate the
performance of the models based on the uncertainty of its predictions,
approximated via the difference of confidences between the base dataset
predictions and the target dataset predictions. Garg et al. (Garg et al.,
2022) estimate the average confidence threshold (ATC) from the validation
data, above which the prediction of the network is considered to be incorrect.

The second group of methods evaluate the quality of the model embeddings. For
example, Deng et al. (Deng et al., 2021) show negative correlation between
recognition accuracy and the Frechet distance between network activations to
the source and the target datasets; while Jiang et al. (Jiang et al., 2019)
predict generalization gap using margin distribution - the distances of
training points to the decision boundary. Margin distribution requires class
predictions, while Frechet distance only relies on hidden embeddings, that is
why we use Frechet distance in our analysis (see Method 3).

The last group of methods for performance evaluation focuses on behaviour
analysis of the network. For example, Bridal et.al. (Birdal et al., 2021)
analyze training dynamics of the model; in particular, the authors measure
generalization of a model via the topological properties of its optimization
trajectories. Instead of monitoring the network during training, the authors
of (Chuang et al., 2020; Jiang et al., 2022; Chen et al., 2021) perform the
training of the same network several times, and measure the disagreement
between the resulting trained models on the target dataset. Another work by
Deng et al. (Deng et al., 2021) shows how the performance on auxiliary task
can be used to estimate the performance on the main task. Finally, Khratmtsova
et al. (2023) propose to analyze how the network changes when it is fine-tuned
on the target dataset with an unsupervised loss (e.g., entropy minimization).
The authors show that the degree of change in network weights is negatively
correlated with the effectiveness of the network on target dataset.

###  2.3. Zero-shot Dense Retrieval

Bi-encoder dense retrievers, initialized with pre-trained language models
(PLMs) and fine-tuned with supervised data, have shown remarkable
effectiveness in in-domain information retrieval tasks (Zhao et al., 2022;
Yates et al., 2021). However, recent studies on the BEIR benchmark dataset
(Thakur et al., 2021; Ren et al., 2022) have revealed that DRs suffer from the
domain shift problem: the effectiveness of a DR varies depending on the corpus
domain, which can be different from the domain of the data it was trained on.

The most straightforward domain adaptation method for PLM-based DRs is to
first continue pre-training the PLMs on the target domain corpus before fine-
tuning them with labeled data (Gururangan et al., 2020). However, it is often
difficult, and costly, to obtain sufficient in-domain labeled training data
for IR tasks. Furthermore, it is often the case that DRs must be deployed in a
zero-shot setting on a target corpus, which presents additional challenges for
domain adaptation. One simple solution for this issue is to pre-train on the
target domain data using unsupervised training tasks, followed by fine-tuning
on the source domain data where there is sufficient labeled training data
(Wang et al., 2022a).

Another line of work aimed at improving the zero-shot ability of dense
retrievers (DRs) is through query generation. This technique has been widely
used for enhancing retrieval effectiveness on in-domain data (Nogueira and
Lin, 2019), and recent studies have shown its effectiveness in the BEIR zero-
shot dataset as well (Thakur et al., 2021; Bonifacio et al., 2022; Jeronymo et
al., 2023). In one approach, a query generator trained on general domain data
is employed to synthesize domain-targeted queries for a target corpus, on
which a dense retriever is trained from scratch (Ma et al., 2021). This method
has also yielded promising results and has been utilized as a post-training
method for adapting powerful MS MARCO retrievers to target domains (Thakur et
al., 2021). More recently, Wang et al. (2022a) proposed GPL, which further
improves the DR’s domain shift ability by combining a query generator with
pseudo labeling from a cross-encoder.

However, our paper’s aim is fundamentally different from the works mentioned
in this section, where the focus is on enhancing the effectiveness of DRs on
domain transfer tasks. Instead, we focus on selecting the best-performing DR
model on the target corpus from a pool of existing models.

###  2.4. Query Performance Prediction

In this paper we are interested in predicting the relative effectiveness of a
DR model among a pool of available DR models. This problem shares several
common aspects with the well known information retrieval task of query
performance prediction (QPP) (He and Ounis, 2006; Zhou and Croft, 2007; Raiber
and Kurland, 2014; Hauff et al., 2008; Carmel and Kurland, 2012). The goal of
query performance prediction is to determine which queries, among a set pool
of queries, a target system will perform best/worst on. The task we examine
instead, is to determine which dense retriever model performs best/worst among
a pool of dense retrievers. Nevertheless, evaluation practices in QPP can be
adapted to our task, for example the measurement of the Kendall Tau
correlation between two query rankings, popular in QPP works, can be adapted
to our settings – we in fact do this in Section 4.3. We further note that
other measures developed to evaluate QPPs, e.g., the $\tau_{AP}$ measure
(Yilmaz et al., 2008), can also be adapted to our task, but we leave this to
future work.

##  3\. Model Selection for Dense Retrievers

In this section we first introduce the formalization of the problem of model
selection for dense retrievers. We then discuss the challenges of model
selection task, specific to DRs. We finally provide a description of the
methods we investigate for model selection and how they are adapted within the
context of DRs.

###  3.1. Problem Formulation

Consider a set of rankers $\mathcal{R}=\\{R_{1},R_{2},\ldots R_{n}\\}$ and the
source dataset $\mathcal{S}$, which was used for training the rankers. Each
ranker represents a dense retriever (dual- or bi- encoder model)
$R=\\{E_{Q},E_{D}\\}$, that separately encodes the query and the document into
dense vectors. The relevance score between the query and the document is
computed using a similarity function. In this work, we consider dense
retrievers that use either cosine similarity or dot product:

$dot(q,d)=E_{Q}(q)^{T}E_{P}(p);\hskip
8.0pt\operatorname*{cos\\_sim}(q,d)=\dfrac{E_{Q}(q)^{T}E_{D}(d)}{||E_{Q}(q)||||E_{D}(d)||}$

Consider further a target dataset $\mathcal{T}$ for which no labeled data was
observed during the training of the rankers in $\mathcal{R}$. The target
dataset $\mathcal{T}$ consists of a set of queries $Q_{\mathcal{T}}$ and a set
of documents $D_{\mathcal{T}}$, i.e.
$\mathcal{T}=\\{Q_{\mathcal{T}},D_{\mathcal{T}}\\}$. In addition, a set of
relevance judgments (also called labels) is denoted as
$\mathcal{J}_{Q_{\mathcal{T}},D_{\mathcal{T}}}$; below we use $\mathcal{J}$ as
a shorthand for $\mathcal{J}_{Q_{\mathcal{T}},D_{\mathcal{T}}}$ when this
cannot be confused. The elements of this set are pairs that establish a
relationship between the elements in $Q_{\mathcal{T}}$ and those in
$D_{\mathcal{T}}$. Practitioners can construct an ordering of the rankers in
$\mathcal{R}$, or a ranking of models, according to a target evaluation
measure $\mathcal{E}$ by applying each ranker to the dataset and use the
relevance judgments to compute the evaluation measure. Then, the rankers would
be ordered in decreasing value of $\mathcal{E}$, forming the true ranking of
rankers $\mathcal{O(R,T,E,J)}$ .

###### Definition 3.1 (Zero-shot Model Selection).

The problem of model selection consists of predicting the ranking
$\mathcal{O(R,T,E,J)}$ without accessing the relevance judgments
$\mathcal{J}_{Q_{\mathcal{T}},D_{\mathcal{T}}}$. This is equivalent to
producing a ranking $\mathcal{\hat{O}(R,T,E)}$ of the rankers in $\mathcal{R}$
for dataset $\mathcal{T}$ and evaluation measure $\mathcal{E}$, such that
$\mathcal{\hat{O}(R,T,E)}$ corresponds to the true ranking
$\mathcal{O(R,T,E,J)}$. Note that $\mathcal{\hat{O}(R,T,E)}$ does not include
the relevance assessments $\mathcal{J}_{Q_{\mathcal{T}},D_{\mathcal{T}}}$ as
input.

Given the problem of zero-shot model selection, we are interested in devising
a method $\mathcal{M(R,T,E)}$ that produces the ranking
$\mathcal{\hat{O}(R,T,E)}$.

###### Definition 3.2 (Methods for Zero-shot Model Selection).

A method $\mathcal{M(R,T,E)}$ for zero-shot model selection takes as input the
set of rankers $\mathcal{R}$, the target dataset $\mathcal{T}$ and the
evaluation measure $\mathcal{E}$ and produces the predicted ranking
$\mathcal{\hat{O}(R,T,E)}$.

The effectiveness of the model selection method can be measured by its
correlation with the ground truth performance across various target datasets.
A high correlation, denoted as $corr(\mathcal{\hat{O}(R,T,E)},$
$\mathcal{O(R,T,E,J)})$, indicates that the method can closely approximate the
ground truth ranking without relying on target labels $\mathcal{J}$.

Note that the problem of zero-shot model selection can be relaxed to allow for
the prediction methods to access a subset of the relevance judgments
$\mathcal{J}_{Q_{\mathcal{T}},D_{\mathcal{T}}}$. For example, this problem
could be revisited in the context of few-shot retrieval, where the model
selection method (and possibly but not necessarily also the rankers in
$\mathcal{R}$) have access to a subset
$F\in\mathcal{J}_{Q_{\mathcal{T}},D_{\mathcal{T}}}$ of all relevance judgments
available for the dataset. We do not consider this setting in this paper.

###  3.2. Challenges of model selection in IR

Before proceeding with the formalization of the chosen model selection
methods, it is important to emphasize the challenges associated with adapting
existing approaches to the information retrieval setting. We demonstrate that
the specificity of the field prevents a straightforward adaptation of many
existing methods. This reinforces our reasoning for choosing the final set of
methods for comparison.

  1. (1)

Variance in network structure: dense retrievers differ in types and numbers of
network layers.

The machine learning research community lacks a consensus on the way a set of
models for model selection is constructed. As a result, researchers employ
different techniques to generate a pool of models, such as varying training
hyper-parameters (Saito et al., 2021), taking different subsets of data for
training (Lacombe et al., 2021), changing initialization strategies (Rieck et
al., 2019) or using the combination of these techniques (Miller et al., 2021).
However, in all of these scenarios, the models’ structure and depth remains
the same, which significantly simplifies the task of model selection.

However, in this paper, we focus on a more realistic scenario for model
selection in IR. In particular, instead of artificially synthesizing a
collection of models and deriving a measure for early stopping (Rieck et al.,
2019) or for hyper-parameter search (Saito et al., 2021), we aim to select the
best model for the target dataset among the latest available state-of-the-art
dense retrievers. As an example, consider the scenario of a hospital, that has
a small highly specialized dataset in hand. With the appearance of a new
model, that outperforms the other known baselines on the source dataset (e.g.,
MS MARCO), the question arises: Will the new model perform similarly well on
the hospital’s local unlabeled dataset?

In practice, we use models from the leaderboard for zero-shot learning from
the BEIR benchmark (Thakur et al., 2021), that includes models with different
architectures (Bert-based; DistilBert-based, Roberta-Based). Therefore, in
order to meet the realistic demands for model selection, an essential
additional constraint is that the model selection method must be insensitive
to the architecture of the models.

  1. (2)

Variance in scoring function: based on the training procedure, document
relevance is estimated by different scoring functions, e.g., cosine similarity
or dot product.

While classifier models produce a unified output that represents the
probability of the input sample belonging to a certain class, dense retriever
scores do not represent probabilities. This difference prevents the direct
adaptation of several methods (You et al., 2019; Hendrycks and Gimpel, 2017;
Guillory et al., 2021; Jiang et al., 2019) to dense retrieval model selection.

Comparing models directly by the score is also not possible due to the
variation in score range based on the score function used (for instance,
cosine similarity with scores ranging from -1 to 1 vs. unbound dot product).
Simultaneously, substituting one scoring function with the other is
inadvisable as it results in a different ranking result. To mitigate this, we
propose to use cosine similarity solely for model selection, while preserving
the original score function for retrieval (see Method 2 in the following
section for more details).

The final score-related challenge is that not only do score distributions
differ among various models, but they also vary across different queries
within a single model. It implies that unlike ATC (Garg et al., 2022), there
is no unified threshold across queries, below which the document is more
likely to be irrelevant.

  1. (3)

Large number of both network parameters and source dataset samples, which
makes re-training impractical.

Several existing approaches require access to the training process, either for
generating training trajectories from several consecutive training checkpoints
(Birdal et al., 2021); or for evaluating the disagreement in judgments between
similar models (Chuang et al., 2020; Jiang et al., 2022; Chen et al., 2021).
However, retraining dense retrievers require significant computational
resources and expertise. In addition, if the code was not made publicly
available, it can be difficult to reproduce the exact training conditions,
including hyper-parameters and data pre-processing steps. Therefore, in this
work, we focus on methods that do not require re-training on the source
dataset.

###  3.3. Method 1: In-Domain Performance

A most naive approach is to rank models by their in-domain performance, or the
performance on the source dataset. Let $e_{S}(R)$ be an evaluation measure of
a ranker $R$ on the source dataset $S$. Then, the In-Domain Performance-based
model ranking is defined as follows:

(1) $Method_{1}=argmax_{R\in\mathcal{R}}(e_{S}(R))$

###  3.4. Method 2: Query Similarity

Query Similarity Score evaluates a ranker by the proximity of its source and
target query representations. The premise behind this score is that the most
generalizable ranker should produce similar embeddings for both source and
target queries.

Let target query relevance score - $tqr$ \- be the cosine similarity between a
target query and its closest counterpart within source queries:

$tqr(q_{t},Q_{S})=\operatorname*{arg\,max}_{q_{s}\in
Q_{S}}(\operatorname*{cos\\_sim}(q_{t},q_{s}))$

Then the Query Similarity Score of a ranker $R$ is the average target query
relevance score across target queries:

(2) $Q\\_sim(Q_{S},Q_{T})=\dfrac{\sum_{q_{t}\in
Q_{T}}{tqr(q_{t},Q_{S})}}{|Q_{T}|}$

Finally, the Query Similarity Score-based model ranker is defined as follows:

(3) $Method_{2}=argmax_{R\in\mathcal{R}}(Q\\_sim_{R})$

###  3.5. Method 3: Corpus Similarity

Corpus Similarity Score evaluates the similarity of corpus representations.
The intuition is that the ranker should generalize well if the source and the
target corpora are encoded in a similar way.

Using per-sample cosine similarity from the previous section proves to be
impractical for corpus comparison due to a high dimensionality of their
representations. Instead, we propose to employ Fréchet distance (Chong and
Forsyth, 2020a) between network activations of the source and target corpora.
Deng and Zheng (Deng and Zheng, 2021) show that small Frechet distance between
network activations is correlated with the high recognition accuracy of
convolutional classifiers.

Let $\mu_{s},\mu_{t},\Sigma_{S},\Sigma_{T}$ be the mean and the covariance
matrix of the network representations, produced by the source and the target
corpora:

$\mu_{s}=\dfrac{\sum_{d_{s}\in
D_{S}}{E_{D}(d_{s})}}{|D_{s}|};\mu_{t}=\dfrac{\sum_{d_{t}\in
D_{t}}{E_{D}(d_{t})}}{|D_{t}|}$

$\Sigma_{S}=\dfrac{\sum_{d_{s}\in
D_{S}}{[E_{D}(d_{s})-\mu_{s}][E_{D}(d_{s})-\mu_{s}]^{T}}}{|D_{S}|-1}$

$\Sigma_{T}=\dfrac{\sum_{d_{t}\in
D_{T}}{[E_{D}(d_{t})-\mu_{t}][E_{D}(d_{t})-\mu_{t}]^{T}}}{|D_{T}|-1}$

Then, Fréchet distance between source and target corpus representations is
defined as following:

(4)
$FD(D_{S},D_{T})=(||\mu_{s}-\mu_{t}||)^{2}+Tr(\Sigma_{S}+\Sigma_{T}-2Tr\sqrt{\Sigma_{S}\Sigma_{T}})$

Finally, the Corpus Similarity-based model ranker is defined as follows:

(5) $Method_{3}=argmin_{R\in\mathcal{R}}(FD_{R})$

Model | In-dom. | Zero-shot | Zero-Shot Datasets
---|---|---|---
| Rank | MS MARCO | Rank | Avg. | COVID | NF | NQ | Hotpot | FiQA | ArguAna | DBPEDIA | SCIDOCS | SciFact | Quora
Contriever | 4 | 0.407 | 1 | 0.496 | 0.596 | 0.329 | 0.498 | 0.638 | 0.329 | 0.446 | 0.413 | 0.165 | 0.677 | 0.865
CoCondenser | 2 | 0.433 | 2 | 0.472 | 0.752 | 0.297 | 0.495 | 0.562 | 0.297 | 0.377 | 0.364 | 0.137 | 0.556 | 0.856
DistilBERT (TAS-B) | 3 | 0.408 | 3 | 0.459 | 0.481 | 0.319 | 0.463 | 0.584 | 0.300 | 0.427 | 0.384 | 0.149 | 0.643 | 0.835
SimLM | 1 | 0.458 | 4 | 0.443 | 0.527 | 0.318 | 0.502 | 0.568 | 0.297 | 0.376 | 0.351 | 0.137 | 0.559 | 0.796
ANCE | 7 | 0.388 | 5 | 0.426 | 0.653 | 0.236 | 0.444 | 0.451 | 0.295 | 0.419 | 0.281 | 0.122 | 0.511 | 0.852
DistilBERT v3 | 5 | 0.389 | 6 | 0.425 | 0.477 | 0.256 | 0.450 | 0.513 | 0.257 | 0.426 | 0.338 | 0.133 | 0.538 | 0.855
DistilBERT (dot) | 6 | 0.389 | 7 | 0.418 | 0.633 | 0.269 | 0.442 | 0.477 | 0.253 | 0.329 | 0.315 | 0.114 | 0.515 | 0.833
MiniLM-L-12 | 8 | 0.385 | 8 | 0.403 | 0.473 | 0.252 | 0.422 | 0.456 | 0.240 | 0.407 | 0.307 | 0.113 | 0.503 | 0.854
BERT-DPR | 10 | 0.364 | 9 | 0.398 | 0.619 | 0.216 | 0.442 | 0.454 | 0.216 | 0.354 | 0.297 | 0.111 | 0.452 | 0.792
MiniLM-L-6 | 9 | 0.379 | 10 | 0.395 | 0.479 | 0.255 | 0.394 | 0.448 | 0.231 | 0.394 | 0.292 | 0.116 | 0.495 | 0.845
DistilBERT v2 | 11 | 0.336 | 11 | 0.364 | 0.242 | 0.258 | 0.362 | 0.427 | 0.212 | 0.429 | 0.288 | 0.133 | 0.495 | 0.815

Table 1. Effectiveness of the considered Dense Retrievers on the in-domain
dataset (MS MARCO, from which the training data was also drawn) and on the
BEIR zero-shot target datasets.

###  3.6. Method 4: Extracted Document Similarity

A particularity of IR setup in comparison to other ML fields is a large
dataset size: target corpora, and in particular source corpora often consist
of millions of documents. For that reason, comparing full corpus
representations might lead to over-generalization and, as a consequence,
result in an inaccurate metric. Instead, we propose to adapt Method 3.5 to IR
task by only comparing the subset of documents, extracted by the target query
from the source corpus and from the target corpus.

Let $l_{S}^{q}=[d_{1},d_{2},\ldots,d_{k}],d_{i}\in S$ be a list of $k$
documents, extracted by a ranker with a query $q$ from a source dataset $S$.
In addition, let
$l_{T}^{q}=[d_{1}^{\prime},d_{2}^{\prime},\ldots,d_{k}^{\prime}],d_{i}^{\prime}\in
T$ be a list of $k$ documents, extracted with the same query from a target
dataset $T$. Then, for a target query $q\in Q_{T}$, Fréchet distance between
extracted subsets of source and target document representations is denoted as
$FD(l_{S}^{q},l_{T}^{q})$.

We average the resulting distances across target queries to obtain an adapted
version of Fréchet distance:

(6) $FD\\_IR(D_{S},D_{T})=\dfrac{\sum_{q\in
Q^{T}}FD(l_{S}^{q},l_{T}^{q})}{|Q^{T}|}$

Finally, the Extracted Document Similarity-based model ranker is defined as
follows:

(7) $Method_{4}=argmin_{R\in\mathcal{R}}(FD\\_IR_{R})$

###  3.7. Method 5: Binary Entropy

In the context of classification tasks, entropy is commonly employed to
measure the level of uncertainty in a model’s predictions. However, in our
scenario, it cannot be directly applied due to the possibility of multiple
relevant documents per query. To adapt the entropy-based method for our task,
we apply a two-step process. First, we transform the scores, produced by the
dense retriever, into probabilities indicating the relevance of each document
to the query. Next, we compute binary entropy for each document in the rank.
We then calculate the probability-at-rank distribution by adding up the binary
probabilities for all the documents in the ranking.

Let $s_{T}^{q}=[s_{1},s_{2},..,s_{k}]$ be a list of scores, obtained by a
ranker with the query $q$ from the target dataset $T$; scores can be either a
dot product or a cosine similarity, depending on the model. We first need to
normalize the scores. For that, we mine for the negative samples as follows:
$\tilde{s}_{T}^{q}=[\tilde{s}_{1},\tilde{s}_{2},...,\tilde{s}_{100}]$;
$\tilde{s}_{T}^{q}\cap s_{T}^{q}=\emptyset$. Then we approximate the minimum
score for the rank and normalize the scores to get probabilities:
$min_{T}^{q}=\operatorname*{arg\,min}(\tilde{s}_{T}^{q})$;
$p(d_{i})=(s_{i}-min_{T}^{q})/(s_{1}-s_{i})$

Assume that $p(d_{i})$ is the probability that the document at rank $i$ is
relevant, while $p(d_{1},\ldots,d_{k})$ is a probability distribution over the
relevance associated with a document list of length $k$ (i.e., probability-
at-rank). Then, the binary entropy is:

(8) $H(p(d_{i}))=-p(d_{i})\log p(d_{i})-(1-p(d_{i}))\log(1-p(d_{i}))$

The entropy probability-at-rank distribution for query $q$ is therefore
defined as follows:

(9) $\displaystyle H^{q}(p(d_{1},\ldots,d_{k}))=\sum_{i=1}^{k}H(p_{i})$ (10)
$\displaystyle H_{R}=\sum_{q\in Q^{T}}{H^{q}}\mathbin{/}|Q^{T}|$

Finally, the Binary Entropy-based model ranker is defined as follows:

(11) $Method_{5}=argmin_{R\in\mathcal{R}}(H_{R})$

###  3.8. Method 6: Query Alteration

This method aims to rank models by assessing their ability to handle changes
in the queries of the target dataset. The intuition is that if a model is
robust enough to the queries and documents in the target domain, then the
relevance scores should remain stable even after introducing noise to the
queries. To evaluate model robustness, we follow a query perturbation-based
approach. Specifically, we issue the original queries to each model on the
target domain dataset and record the top k retrieved documents of each query.
We then randomly replace some tokens in the original queries with [MASK]
tokens, with the proportion of replaced tokens controlled by a hyper-parameter
p that ranges from 0 to 1. Subsequently, we recompute the relevance scores
between the altered queries and the originally retrieved documents. By
comparing the scores of the original and perturbed queries, we obtain an
indication of how well the model can handle variations and noise in query
inputs. We quantify the model robustness by calculating the standard deviation
of the score changes, with lower standard deviation implying better
robustness.

##  4\. Experimental Setup

###  4.1. Datasets

To evaluate the ability of the predictors to select the most performing model
for a target dataset, we employ the BEIR evaluation benchmark (Thakur et al.,
2021), which has been commonly employed to evaluate the generalisation and
zero-shot effectiveness of retrieval models (Gururangan et al., 2020; Wang et
al., 2022a; Ma et al., 2021; Ren et al., 2022). BEIR contains a heterogeneous
set of 18 datasets drawn from 9 text retrieval tasks and domains. We refer the
reader to the original work describing BEIR for an in-depth analysis of each
dataset and baseline results (Thakur et al., 2021) – however, as the complete
set of BEIR subsets is not publicly available, we follow the standard practice
of selecting a representative subset of the available subsets for our
experiments. Specifically, we select 10 out of the 18 available subsets to
conduct our experiments. The selected subsets are consistent with prior work
on the dataset, allowing for comparability across studies. We highlight that a
key finding of that work was that dense retrievers exhibited poor
generalization capabilities.

###  4.2. Dense Retrieval Models

To evaluate our proposed dense retrieval model selection methods, we require a
diverse pool of DR models that exhibit varying performance across different
BEIR subsets. To this end, we consider DR models that have been submitted to
the BEIR leaderboard 111https://github.com/beir-cellar/beir/wiki/Leaderboard,
including Contriver (Izacard et al., [n.d.]), DistilBERT (TAS-B) (Hofstätter
et al., 2021), ANCE (Xiong et al., [n.d.]), DistilBERT v3 (Reimers and
Gurevych, 2019), DistilBERT (dot) (Reimers and Gurevych, 2019), MiniLM-L-12
(Reimers and Gurevych, 2019), MiniLM-L-6 (Reimers and Gurevych, 2019), and
DistilBERT v2 (Reimers and Gurevych, 2019). Additionally, we include some
advanced DR models that are not on the leaderboard, such as CoCondenser (Gao
and Callan, 2021) and SimLM (Wang et al., 2022b), as well as a DR model that
we trained ourselves (BERT-DPR) by using Tevatron DR training toolkit (Gao et
al., 2022). We obtain all model checkpoints from the Huggingface model hub, as
uploaded by the original authors. Notably, all DR models considered in this
study are trained on MS MARCO training data (Nguyen et al., 2016), and
therefore perform zero-shot retrieval on BEIR datasets.

###  4.3. Evaluation Measures for Dense Retrievers Selection

For evaluating considered model selection methods, we need to first have the
ideal model ranking on the target corpus to compare with the rankings
generated by the model selection methods. To this end, for each of the
considered datasets, we record the effectiveness of each dense retrievers
according to several evaluation measures $e$. Specifically we consider
nDCG@10, which is the official evaluation measure for the BEIR leaderboard. We
report these measures for the Dense Retrievers we consider in our main
experiments in Table 1.

After having the real nDCG@10 scores of methods on BEIR dataset, then given a
dataset, we identify the best Dense Retriever model $M$ according to the
evaluation measure $e$ among the set $\mathcal{M}$ of dense retrievers we
consider, i.e. $M=argmax_{\widetilde{M}\in\mathcal{M}}(e(\widetilde{M}))$. For
each prediction method $\theta$ we then identify the model $\hat{M}_{\theta}$
that has been predicted as being the most effective for that dataset. Then, we
measure the loss for the evaluation measure $e$ when using $\hat{M}_{\theta}$,
i.e. the model predicted to be the best by the prediction method $\theta$, in
place of $M$, i.e. the true best model. We define this loss as:

(12) $\Delta_{e}=e(\hat{M}_{\theta})-e(M)$

We also consider the relative loss produced when choosing $\hat{M}_{\theta}$
in place of $M$: this measure is interesting in that a search engine
practitioner may tolerate to select a sub-optimal model up to a certain
percentage of loss.

(13) $\%\Delta_{e}=100*\frac{e(\hat{M}_{\theta})-e(M)}{e(M)}$

In addition the above loss based evaluation method, we also consider the
Kendall Tau correlation, which measures the similarity between the rankings
generated by the model selection methods and the ranking by true nDCG values.
Specifically, the Kendall Tau correlation measures the proportion of pairs of
documents that are ranked in the same order by both rankings. A perfect
correlation between the rankings of two models results in a Kendall Tau score
of 1 in case of positive correlation and -1 in case of negative correlation,
while a completely random correlation results in a score of 0.

##  5\. Results

Table 1 presents the effectiveness in terms of nDCG@10 of the considered DR
models on the source MS MARCO dataset and the target collection BEIR, as well
as the in-domain and out-of-domain (zero-shot) ground truth model ranking. It
is evident that the zero-shot ranking differs from the in-domain ranking,
highlighting the necessity for a better model selection criterion.
Furthermore, we provide the effectiveness of our proposed model selection
methods in terms of Kendall Tau correlation, $\Delta_{e}$, and $\%\Delta_{e}$
in Tables 2, 3, and 4, respectively. These tables allow us to compare the
effectiveness of the selected models and provide a comprehensive overview of
the investigated methods for model selection.

| COVID | NF | NQ | HotpotQA | FiQA | ArguAna | DBPedia | SciDocs | SciFact | Quora | Avrg
---|---|---|---|---|---|---|---|---|---|---|---
In-Domain Performance (1) | 0.273 | 0.455 | 0.782 | 0.709 | 0.745 | 0.018 | 0.6 | 0.636 | 0.745 | 0.273 | 0.524
Query Similarity (2) | 0.673 | 0.127 | 0.345 | 0.091 | 0.2 | -0.164 | 0.055 | 0.091 | 0.018 | -0.091 | 0.135
Corpus Similarity (3) | 0.2 | 0.056 | 0.345 | 0.309 | 0.455 | 0.055 | 0.200 | 0.382 | 0.309 | 0.164 | 0.247
Extracted Doc similarly @100 (4) | 0.273 | -0.018 | 0.491 | 0.200 | 0.345 | -0.018 | 0.236 | 0.236 | 0.200 | 0.127 | 0.207
Binary entropy 10 (5) | 0.418 | 0.491 | -0.127 | -0.055 | 0.055 | 0.491 | -0.345 | 0.127 | 0.309 | 0.236 | 0.16
Binary entropy 1000 (5) | 0.418 | 0.491 | -0.127 | -0.055 | 0.055 | 0.491 | -0.345 | 0.127 | 0.309 | 0.236 | 0.16
Query Alteration Std p=0.1 (6) | -0.127 | 0.091 | 0.345 | 0.309 | 0.273 | 0.127 | 0.164 | 0.309 | 0.2 | 0.2 | 0.189
Query Alteration Std p=0.2 (6) | -0.164 | 0.055 | 0.345 | 0.273 | 0.273 | 0.164 | 0.164 | 0.2 | 0.2 | 0.236 | 0.175
Query Alteration Std p=0.3 (6) | -0.236 | -0.018 | 0.236 | 0.164 | 0.2 | 0.091 | 0.164 | 0.127 | 0.091 | 0.164 | 0.098

Table 2. Kendall Tau Correlation value, calculated based on nDCG@10 (the
higher, the better)

| TREC-COVID | NFCorpus | NQ | HotpotQA | FiQA | ArguAna | DBPedia | SciDocs | SciFact | Quora | Avrg
---|---|---|---|---|---|---|---|---|---|---|---
In-Domain Performance (1) | 0.225 | 0.01 | 0.0 | 0.07 | 0.032 | 0.07 | 0.062 | 0.028 | 0.118 | 0.068 | 0.068
Query Similarity (2) | 0.099 | 0.092 | 0.058 | 0.186 | 0.035 | 0.027 | 0.132 | 0.043 | 0.165 | 0.013 | 0.085
Corpus Similarity (3) | 0.225 | 0.01 | 0.0 | 0.07 | 0.032 | 0.07 | 0.062 | 0.028 | 0.118 | 0.068 | 0.068
Extracted Doc similarly @100 (4) | 0.225 | 0.01 | 0.0 | 0.07 | 0.032 | 0.07 | 0.062 | 0.028 | 0.118 | 0.068 | 0.068
Binary entropy @10 (5) | 0.099 | 0.07 | 0.058 | 0.186 | 0.035 | 0.019 | 0.132 | 0.043 | 0.034 | 0.0 | 0.067
Binary entropy @1000 (5) | 0.099 | 0.07 | 0.058 | 0.186 | 0.035 | 0.019 | 0.132 | 0.043 | 0.034 | 0.0 | 0.067
Query Alteration Std p=0.1 (6) | 0.225 | 0.01 | 0.0 | 0.07 | 0.032 | 0.07 | 0.062 | 0.028 | 0.118 | 0.068 | 0.068
Query Alteration Std p=0.2 (6) | 0.225 | 0.01 | 0.0 | 0.07 | 0.032 | 0.07 | 0.062 | 0.028 | 0.118 | 0.068 | 0.068
Query Alteration Std p=0.3 (6) | 0.225 | 0.01 | 0.0 | 0.07 | 0.032 | 0.07 | 0.062 | 0.028 | 0.118 | 0.068 | 0.068

Table 3. $\Delta_{e}$, calculated based on nDCG@10 (the lower, the better)

| TREC-COVID | NFCorpus | NQ | HotpotQA | FiQA | ArguAna | DBPedia | SciDocs | SciFact | Quora | Avrg
---|---|---|---|---|---|---|---|---|---|---|---
In-Domain Performance (1) | 29.88 | 3.03 | 0.0 | 10.91 | 9.69 | 15.63 | 14.97 | 16.8 | 17.38 | 7.87 | 12.62
Query Similarity (2) | 13.12 | 28.16 | 11.52 | 29.23 | 10.5 | 6.09 | 31.9 | 26.25 | 24.44 | 1.46 | 18.27
Corpus Similarity (3) | 29.88 | 3.03 | 0.0 | 10.91 | 9.69 | 15.63 | 14.97 | 16.8 | 17.38 | 7.87 | 12.62
Extracted Doc similarly @100 (4) | 29.88 | 3.03 | 0.0 | 10.91 | 9.69 | 15.63 | 14.97 | 16.8 | 17.38 | 7.87 | 12.62
Binary entropy @10 (5) | 13.12 | 21.36 | 11.52 | 29.23 | 10.5 | 4.29 | 31.9 | 26.25 | 5.03 | 0.0 | 15.32
Binary entropy @1000 (5) | 13.12 | 21.36 | 11.52 | 29.23 | 10.5 | 4.29 | 31.9 | 26.25 | 5.03 | 0.0 | 15.32
Query Alteration Std p=0.1 (6) | 29.88 | 3.03 | 0.0 | 10.91 | 9.69 | 15.63 | 14.97 | 16.8 | 17.38 | 7.87 | 12.62
Query Alteration Std p=0.2 (6) | 29.88 | 3.03 | 0.0 | 10.91 | 9.69 | 15.63 | 14.97 | 16.8 | 17.38 | 7.87 | 12.62
Query Alteration Std p=0.3 (6) | 29.88 | 3.03 | 0.0 | 10.91 | 9.69 | 15.63 | 14.97 | 16.8 | 17.38 | 7.87 | 12.62

Table 4. $\%\Delta_{e}$, calculated based on nDCG@10 (the lower, the better)

###  5.1. Desired ranking

To gain an understanding of the desired model ranking, we first evaluate the
actual effectiveness of the considered DR models on the BEIR dataset. The
results are presented in Table 1. While Contriever may not perform the best on
the in-domain corpus (i.e. the dataset that is aligned to the training data),
it outperforms other DRs on most of the zero-shot datasets, ranking at number
one in terms of average zero-shot effectiveness. CoCondense and SimLM, on the
other hand, exhibit better in-domain effectiveness than Contriever, but only
achieve the best zero-shot effectiveness on NQ and COVID, respectively,
ranking at four and two on average in terms of zero-shot effectiveness.
Similarly, the effectiveness of all other models varies on the zero-shot
datasets, irrespective of their effectiveness on the in-domain data.

It is important to keep in mind that our objective is to rank the DR models on
the target dataset as closely as possible to the true ranking of the models.
Therefore, the naive baseline of ranking models solely based on their in-
domain effectiveness is evidently inadequate, which is quantified in Tables 2,
3 and 4 (first row of each table).

We next analyze how each of the methods we considered for model selection
perform, compared to the naive baseline of ranking models solely based on
their in-domain effectiveness.

###  5.2. Query Similarity

The Query Similarity method identifies ANCE as the top-ranked model across all
zero-shot datasets. This may be because most of ANCE’s top scores have values
close to 1, unlike the other DR models. CoCondenser is always ranked as the
second best model, followed by BERT-DPR in third place. However, it should be
noted that predicting BERT-DPR to be ranked high is not desirable, as its
actual rank position based on the ground-truth is usually near the bottom of
the list, regardless of the zero-shot dataset, as shown in Table 1. Overall,
Query Similarity displays weak average correlation with the true rankings of
DR models (Table 2), and is the worst method in terms of $\Delta_{e}$ and
$\%\Delta_{e}$.

###  5.3. Corpus Similarity

According to the Corpus Similarity method, SimLM is consistently ranked as the
best model across all datasets, followed by Contriever as the second-best
model. The third-place ranking varies between ANCE and MiniLM-L-12 depending
on the zero-shot dataset. The bottom-ranking models are almost identical
across all datasets. Notably, this method provides the best Kendall Tau
correlation among all considered methods, but is inferior to the In-Domain
performance baseline. Additionally, unlike most other unsupervised methods,
the Fréchet distance, which defines the corpus similarity, consistently
exhibits a negative correlation with the accuracy across all target datasets.
This characteristic makes Corpus Similarity the most reliable measure for
unsupervised model selection among considered methods.

###  5.4. Extracted Document Similarity

The ranking of the top three DRs according to the Extracted Document
Similarity method is consistent across all datasets, with Contriever securing
the first place, followed by ANCE and MiniLM-12. Although this method is
slightly less effective than corpus similarity, it still yields the best
$\Delta_{e}$ and $\%\Delta_{e}$ values, matching those of the baseline as well
as those of some of the other methods.

###  5.5. Binary Entropy

Binary Entropy is the only method that selects different models across
different zero-shot datasets: either DistilBERT (TAS-B) or ANCE. According to
Table 3 the cut-off of the documents per query does not matter as it does not
affect the ranking of models. Binary Entropy provides the best ranking of DRs
for the Arguana and NF datasets ($\tau=0.491$), even outperforming the In-
Domain performance method on these datasets. However, the biggest drawback of
Binary Entropy is that it does not have a consistent correlation pattern
across datasets: for example, it shows moderate negative correlation for
DBPedia with $\tau=-0.345$, while moderate positive correlation of the two
datasets for which it performs best, Arguana and NF. The analysis of
$\Delta_{e}$ and $\%\Delta_{e}$ values paint a similar picture. We discuss the
origins of this inconsistency in the next section.

###  5.6. Query Alteration

Across all datasets, Query Alteration indicates as the best model SimLM,
followed by DistillBert. The method displays the lowest average
$\%\Delta_{e}$, at par with the baseline; the individual values of
$\%\Delta_{e}$ across the zero-shot datasets are often the best recorded,
except in the case of the TREC-COVID dataset. We also note that the
$\%\Delta_{e}$ of this method matches exactly the one of the In-Domain
performance baseline. Note that the probability $p$ of replaced tokens affects
the effectiveness of the predictions, with the best $p$ being 0.1.

##  6\. Outlook

We have examined the effectiveness of adapting methods of unsupervised
performance evaluation with the presence of domain shift, proposed in the area
of computer vision and machine learning, to the problem of choosing which
dense retriever model to use when searching on a new collection for which no
labels are available, i.e. in a zero-shot setting.

Our first finding is that the in-domain effectiveness of the dense retrievers,
trained on a large corpus like MS MARCO, represents a strong indicator of
model generalizability on the target domains, despite the existence of domain
gap. However, we note that the problem of dense retrieval selection, i.e.
which dense retriever model to select in a new domain, remains an important
and unresolved issue. Specifically, we observe that the straightforward in-
domain-based model selection method fails to choose the best model across all
the datasets examined. Furthermore, for certain datasets, the ranking of
models based on this method is significantly flawed. The methods we have
investigated and that we have adapted from computer vision and machine
learning can only do as well as this simple baseline (though some do notably
worse). These findings highlight the need for further research to improve the
effectiveness of model selection techniques to make feasible the practical
application of dense retrieval in domain-specific tasks characterized by low
labeled data availability.

In this work, we focus on a realistic model selection scenario in information
retrieval, which differs from the artificially-created setups investigated in
prior work in machine learning (see Challenge 1 in Section 3.2). Due to the
challenges in adapting model selection methods to the information retrieval
setup, we primarily considered two broad groups of methods: uncertainty-based
and activation-based.

Uncertainty-based methods. In the field of machine learning, entropy-based
methods are often used to measure the level of uncertainty of a model. These
methods analyze the score distribution produced by the model and use it to
assess the model’s level of confidence in its predictions.

In classification tasks, the concept of uncertainty is naturally linked to the
score distribution since there is only one correct class per input sample.
When a model predicts two classes with similar probabilities, it indicates
uncertainty about the sample’s classification.

In information retrieval tasks, the requirement for an ideal ranker is to
maximize the binary entropy of relevant document predictions and minimize the
binary entropy of irrelevant ones, as defined by Aslam et al. (2005). This
presents a challenge since the number of relevant documents in an unjudged
collection is unknown. As a result, the connection between score distribution
and model uncertainty in ranking tasks is not intuitive. For instance, a
retriever that produces a steep score distribution with a top-ranked document
having a significantly higher score than other retrieved documents will have a
small entropy score. On the other hand, a retriever with a more gradually-
declining score distribution will have a larger entropy score. However, having
a large entropy of predictions does not necessarily imply that the model is
uncertain. It may instead reflect that the model predicts more of the top-k
retrieved documents to be equally relevant. In addition, the nature of the
dataset itself could highly influence the score distributions. Large datasets
with many documents that are relevant to a query will likely result in
rankings with low entropy; while small datasets with very different documents
and with just a handful of documents that are close to the query will likely
result in rankings with a high entropy. In this example, however, the case
with higher entropy does not indicate the model is more certain about its
predictions.

Another way to define the uncertainty of the model is to evaluate its
robustness to query perturbation. The intuition is that if the model is
confident in its predictions, it should not be affected by a slight
perturbation of the query. Consequently, network robustness can be used as a
quality measure of the model, and employed as an unsupervised criterion for
model selection. Indeed, according to our results, this approach provides
competitive model ranking, with an average Tau Correlation of 0.189. Despite
this, the correlation is very weak and the method falls noticeably behind the
top-performing baseline, indicating that there is still ample opportunity for
improvement, which we recommend the information retrieval community should
explore in future research.

The issue of uncertainty estimation in information retrieval is a significant
yet largely under-explored problem, as noted in several prior studies (Turtle
and Croft, 1997; Crestani et al., 1998; Collins-Thompson and Callan, 2007).
This is particularly true for rankers that rely on pre-trained language models
(Lesota et al., 2021). While some efforts have been made to leverage
uncertainty in relevance estimation for traditional keyword-based best-match
models like BM25 and language models, the current approaches are based on
assumptions and heuristics that use similarities or covariance between term
occurrences (Zhu et al., 2009; Wang and Zhu, 2009; Zuccon et al., 2009),
follow the Dirichlet distribution (Wang and Zhu, 2009), or calculate score
distributions by resampling query terms (Collins-Thompson and Callan, 2007).
Recently, researchers have attempted to model uncertainty for neural rankers,
such as with the Transformer Pointer Generator Network (T-PGN) model (Lesota
et al., 2021) However, these models are not easily adaptable to the dense
retrieval ranker architectures that we have examined in this paper. More
effective and meaningful estimations of uncertainty might be a promising
future direction also in our context.

Activation-based methods. Activation-based methods approximate the domain gap
between the source and target distributions via the proximity of its hidden
representations. The underlying idea is that a model with good generalization
capabilities should produce similar encodings for both datasets. The advantage
of this method if adapted to information retrieval is that it is not affected
by variations in network architectures or scoring functions used, which
enables the comparison of models within the constraints of the information
retrieval setup (i.e. across different pre-trained language models and
architectures). This makes it easier to identify models that perform well on
both source and target datasets, without being biased towards specific network
architectures or scoring functions.

In our experiments, we used the Fréchet distance between the activations of
the network for the source and target datasets (Method 3, Corpus Similarity).
This approach, highly effective for example in computer vision tasks, in our
experiments selects the same best model for all the datasets, similarly to the
in-domain performance-based method, but produces an inferior model ranking
(see Table 2). To handle the high dimensionality of the activation spaces, the
Fréchet-based approximation assumes that they conform to a normal distribution
(Chong and Forsyth, 2020b), which may not hold for NLP-induced hidden
representations. We believe that designing NLP-oriented distance
approximations between activation spaces is a promising future direction for
more accurate unsupervised model selection, especially in the context of
selecting dense retrieval models.

Weight- and Performance-based methods. The last direction we would like to
mention is inspired the recent work by Khratmtsova et al. (2023) and Deng et
al. (2021) which involves fine-tuning the network on the target dataset with
the unsupervised loss (e.g., it can be a masked token prediction task) and
evaluating the degree of the network change or the performance on the
unsupervised task. Despite being computationally expensive, these approaches
have been shown very effective in general machine learning model selection,
and can be further explored in the information retrieval context.

##  7\. Conclusion

This paper proposes a novel research direction for zero-shot dense retrieval.
While traditional information retrieval research in this area concentrates on
developing universal domain-agnostic DR models, our work shifts the focus
towards developing a method to rank and select pre-trained state-of-the-art DR
models that are best suited for a specific target domain corpus. We
acknowledge that the proposed direction does not contradict traditional
research on training zero-shot DR models, but rather complements it. As newly
developed DR models are likely to have varying effects on different domains,
selecting the best model is still beneficial. To explore this research
direction, we adapt various methods from computer vision and machine learning,
along with some approaches designed for IR. We outline our reasoning and
challenges with the investigated approaches and present empirical results on a
popular zero-shot benchmark dataset. Our findings shed light on future
research avenues within this research direction. We believe that an effective
method for selecting a good DR model can provide a principled way for search
engine developers to identify the most suitable model for their application,
ultimately enhancing user experience.

## References

  * (1)
  * Aslam et al. (2005) Javed A. Aslam, Emine Yilmaz, and Virgiliu Pavlu. 2005\.  The Maximum Entropy Method for Analyzing Retrieval Measures. In _Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Salvador, Brazil) _(SIGIR ’05)_. Association for Computing Machinery, New York, NY, USA, 27–34.  https://doi.org/10.1145/1076034.1076042
  * Birdal et al. (2021) Tolga Birdal, Aaron Lou, Leonidas J. Guibas, and Umut cSimcsekli. 2021.  Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks. In _NeurIPS_.
  * Bonifacio et al. (2022) Luiz Bonifacio, Hugo Abonizio, Marzieh Fadaee, and Rodrigo Nogueira. 2022.  Inpars: Data augmentation for information retrieval using large language models.  _arXiv preprint arXiv:2202.05144_ (2022).
  * Carmel and Kurland (2012) David Carmel and Oren Kurland. 2012.  Query performance prediction for ir. In _Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval_. 1196–1197.
  * Chen et al. (2021) Jiefeng Chen, Frederick Liu, Besim Avci, Xi Wu, Yingyu Liang, and Somesh Jha. 2021\.  Detecting Errors and Estimating Accuracy on Unlabeled Data with Self-training Ensembles. In _Advances in Neural Information Processing Systems_.
  * Chen et al. (2022) Tao Chen, Mingyang Zhang, Jing Lu, Michael Bendersky, and Marc Najork. 2022.  Out-of-Domain Semantics to the Rescue! Zero-Shot Hybrid Retrieval Models. In _European Conference on Information Retrieval_.
  * Chong and Forsyth (2020a) Min Jin Chong and David A. Forsyth. 2020a.  Effectively Unbiased FID and Inception Score and Where to Find Them.  (2020), 6069–6078.
  * Chong and Forsyth (2020b) Min Jin Chong and David A. Forsyth. 2020b.  Effectively Unbiased FID and Inception Score and Where to Find Them.  (2020), 6069–6078.
  * Chuang et al. (2020) Ching-Yao Chuang, Antonio Torralba, and Stefanie Jegelka. 2020\.  Estimating Generalization under Distribution Shifts via Domain-Invariant Representations.  _International Conference of Machine Learning (ICML)_ (2020).
  * Collins-Thompson and Callan (2007) Kevyn Collins-Thompson and Jamie Callan. 2007.  Estimation and use of uncertainty in pseudo-relevance feedback. In _Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval_. 303–310.
  * Corneanu et al. (2019) Ciprian A. Corneanu, Meysam Madadi, Sergio Escalera, and Aleix M. Martinez. 2019.  What Does It Mean to Learn in Deep Networks? And, How Does One Detect Adversarial Attacks?. In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_.
  * Crestani et al. (1998) Fabio Crestani, Mounia Lalmas, and Cornelis Joost van Rijsbergen. 1998\.  _Information retrieval: Uncertainty and logics: Uncertainty and logics: Advanced models for the representation and retrieval of information_. Vol. 4.  Springer Science & Business Media.
  * Deng et al. (2021) Weijian Deng, Stephen Gould, and Liang Zheng. 2021\.  What Does Rotation Prediction Tell Us about Classifier Accuracy under Varying Testing Environments?. In _International Conference of Machine Learning (ICML)_.
  * Deng and Zheng (2021) Weijian Deng and Liang Zheng. 2021.  Are Labels Always Necessary for Classifier Accuracy Evaluation?. In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Gao and Callan (2021) Luyu Gao and Jamie Callan. 2021.  Condenser: a Pre-training Architecture for Dense Retrieval. In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. 981–993.
  * Gao et al. (2022) Luyu Gao, Xueguang Ma, Jimmy J. Lin, and Jamie Callan. 2022\.  Tevatron: An Efficient and Flexible Toolkit for Dense Retrieval.  _ArXiv_ abs/2203.05765 (2022).
  * Garg et al. (2022) Saurabh Garg, Sivaraman Balakrishnan, Zachary Chase Lipton, Behnam Neyshabur, and Hanie Sedghi. 2022\.  Leveraging Unlabeled Data to Predict Out-of-Distribution Performance. In _International Conference on Learning Representations, ICLR_.  https://arxiv.org/abs/2201.04234
  * Guillory et al. (2021) Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. 2021.  Predicting with Confidence on Unseen Distributions.  _IEEE/CVF International Conference on Computer Vision (ICCV)_ (2021), 1114–1124.
  * Gururangan et al. (2020) Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A. Smith. 2020.  Don’t Stop Pretraining: Adapt Language Models to Domains and Tasks. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Online, 8342–8360.  https://aclanthology.org/2020.acl-main.740
  * Hauff et al. (2008) Claudia Hauff, Djoerd Hiemstra, and Franciska de Jong. 2008\.  A survey of pre-retrieval query performance predictors. In _Proceedings of the 17th ACM conference on Information and knowledge management_. 1419–1420.
  * He and Ounis (2006) Ben He and Iadh Ounis. 2006\.  Query performance prediction.  _Information Systems_ 31, 7 (2006), 585–594.
  * Hendrycks and Gimpel (2017) Dan Hendrycks and Kevin Gimpel. 2017.  A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks.  _Proceedings of International Conference on Learning Representations_ (2017).
  * Hofstätter et al. (2021) Sebastian Hofstätter, Sheng-Chieh Lin, Jheng-Hong Yang, Jimmy Lin, and Allan Hanbury. 2021\.  Efficiently teaching an effective dense retriever with balanced topic aware sampling. In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 113–122.
  * Izacard et al. ([n.d.]) Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. [n.d.].  Unsupervised Dense Information Retrieval with Contrastive Learning.  _Transactions on Machine Learning Research_ ([n. d.]).
  * Jeronymo et al. (2023) Vitor Jeronymo, Luiz Bonifacio, Hugo Abonizio, Marzieh Fadaee, Roberto Lotufo, Jakub Zavrel, and Rodrigo Nogueira. 2023.  InPars-v2: Large Language Models as Efficient Dataset Generators for Information Retrieval.  _arXiv preprint arXiv:2301.01820_ (2023).
  * Jiang et al. (2019) Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. 2019.  Predicting the Generalization Gap in Deep Networks with Margin Distributions. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=HJlQfnCqKX
  * Jiang et al. (2022) Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and J. Zico Kolter. 2022.  Assessing Generalization of SGD via Disagreement.  _ArXiv_ abs/2106.13799 (2022).
  * Khratmtsova et al. (2023) Ekaterina Khratmtsova, Guido Zuccon, Wang Xi, and Mahsa Baktashmotlagh. 2023.  Weight-Based Performance Estimation for Diverse Domains.  _arXiv preprint_ (2023).
  * Lacombe et al. (2021) Théo Lacombe, Yuichi Ike, and Yuhei Umeda. 2021.  Topological Uncertainty: Monitoring trained neural networks through persistence of activation graphs. In _IJCAI_.
  * Lesota et al. (2021) Oleg Lesota, Navid Rekabsaz, Daniel Cohen, Klaus Antonius Grasserbauer, Carsten Eickhoff, and Markus Schedl. 2021.  A modern perspective on query likelihood with deep generative retrieval models. In _Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval_. 185–195.
  * Lin et al. (2023) Sheng-Chieh Lin, Akari Asai, Minghan Li, Barlas Oguz, Jimmy Lin, Yashar Mehdad, Wen-tau Yih, and Xilun Chen. 2023\.  How to Train Your DRAGON: Diverse Augmentation Towards Generalizable Dense Retrieval.  _arXiv preprint arXiv:2302.07452_ (2023).
  * Ma et al. (2021) Ji Ma, Ivan Korotkov, Yinfei Yang, Keith Hall, and Ryan McDonald. 2021.  Zero-shot Neural Passage Retrieval via Domain-targeted Synthetic Question Generation. In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_. 1075–1088.
  * Miller et al. (2021) John Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. 2021.  Accuracy on the Line: on the Strong Correlation Between Out-of-Distribution and In-Distribution Generalization.  (2021).
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A human generated machine reading comprehension dataset.  _choice_ 2640 (2016), 660.
  * Nogueira and Lin (2019) Rodrigo Nogueira and Jimmy Lin. 2019.  From doc2query to docTTTTTquery.
  * Raiber and Kurland (2014) Fiana Raiber and Oren Kurland. 2014.  Query-performance prediction: setting the expectations straight. In _Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval_. 13–22.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.  http://arxiv.org/abs/1908.10084
  * Ren et al. (2022) Ruiyang Ren, Yingqi Qu, Jing Liu, Wayne Xin Zhao, Qifei Wu, Yuchen Ding, Hua Wu, Haifeng Wang, and Ji-Rong Wen. 2022.  A thorough examination on zero-shot dense retrieval.  _arXiv preprint arXiv:2204.12755_ (2022).
  * Rieck et al. (2019) Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and Karsten Borgwardt. 2019.  Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology. In _International Conference on Learning Representations_.
  * Saito et al. (2021) K. Saito, D. Kim, P. Teterwak, S. Sclaroff, T. Darrell, and K. Saenko. 2021\.  Tune it the Right Way: Unsupervised Validation of Domain Adaptation via Soft Neighborhood Density. In _IEEE/CVF International Conference on Computer Vision (ICCV)_. IEEE Computer Society, 9164–9173.
  * Thakur et al. (2021) Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. 2021\.  BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)_.
  * Turtle and Croft (1997) Howard R Turtle and W Bruce Croft. 1997.  Uncertainty in information retrieval systems.  _Uncertainty management in information systems: from needs to solutions_ (1997), 189–224.
  * Wang and Zhu (2009) Jun Wang and Jianhan Zhu. 2009.  Portfolio theory of information retrieval. In _Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval_. 115–122.
  * Wang et al. (2022a) Kexin Wang, Nandan Thakur, Nils Reimers, and Iryna Gurevych. 2022a.  GPL: Generative Pseudo Labeling for Unsupervised Domain Adaptation of Dense Retrieval. In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 2345–2360.
  * Wang et al. (2022b) Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. 2022b.  SimLM: Pre-training with Representation Bottleneck for Dense Passage Retrieval.  _arXiv preprint arXiv:2207.02578_ (2022).
  * Xiong et al. ([n.d.]) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N Bennett, Junaid Ahmed, and Arnold Overwijk. [n.d.].  Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In _International Conference on Learning Representations_.
  * Yates et al. (2021) Andrew Yates, Rodrigo Nogueira, and Jimmy Lin. 2021\.  Pretrained transformers for text ranking: BERT and beyond. In _Proceedings of the 14th ACM International Conference on web search and data mining_. 1154–1156.
  * Yilmaz et al. (2008) Emine Yilmaz, Javed A. Aslam, and Stephen Robertson. 2008\.  A New Rank Correlation Coefficient for Information Retrieval. In _Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Singapore, Singapore) _(SIGIR ’08)_. Association for Computing Machinery, New York, NY, USA, 587–594.  https://doi.org/10.1145/1390334.1390435
  * You et al. (2019) Kaichao You, Ximei Wang, Mingsheng Long, and Michael Jordan. 2019\.  Towards Accurate Model Selection in Deep Unsupervised Domain Adaptation. In _Proceedings of the 36th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 7124–7133.  https://proceedings.mlr.press/v97/you19a.html
  * Zhao et al. (2022) Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. 2022\.  Dense text retrieval based on pretrained language models: A survey.  _arXiv preprint arXiv:2211.14876_ (2022).
  * Zhou and Croft (2007) Yun Zhou and W Bruce Croft. 2007.  Query performance prediction in web search environments. In _Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval_. 543–550.
  * Zhu et al. (2009) Jianhan Zhu, Jun Wang, Ingemar J Cox, and Michael J Taylor. 2009\.  Risky business: modeling and exploiting uncertainty in information retrieval. In _Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval_. 99–106.
  * Zhuang and Zuccon (2021) Shengyao Zhuang and Guido Zuccon. 2021.  Dealing with Typos for BERT-based Passage Retrieval and Ranking. In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Online and Punta Cana, Dominican Republic, 2836–2842.
  * Zhuang and Zuccon (2022) Shengyao Zhuang and Guido Zuccon. 2022.  CharacterBERT and Self-Teaching for Improving the Robustness of Dense Retrievers on Queries with Typos _(SIGIR ’22)_. Association for Computing Machinery, New York, NY, USA, 1444–1454.
  * Zuccon et al. (2009) Guido Zuccon, Leif A Azzopardi, and Keith Van Rijsbergen. 2009\.  The quantum probability ranking principle for information retrieval. In _Advances in Information Retrieval Theory: Second International Conference on the Theory of Information Retrieval, ICTIR 2009 Cambridge, UK, September 10-12, 2009 Proceedings 2_. Springer, 232–240.


# Pairwise intersecting convex sets and cylinders in $\mathbb{R}^{3}$

Imre Bárány

###### Abstract.

We prove that given a finite collection of cylinders in $\mathbb{R}^{3}$ with
the property that any two them intersect, then there is a line intersecting an
$\alpha$ fraction of the cylinders where $\alpha=\frac{1}{28}$. This is a
special case of an interesting conjecture.

###### Key words and phrases:

Convex bodies, Helly’s theorem, transversals.

###### 2010 Mathematics Subject Classification:

52A35, 52A15

##  1\. Introduction and main result

The following beautiful conjecture about finite families of convex bodies in
$\mathbb{R}^{3}$ was raised by Martínez, Roldán, and Rubin in [4].

######  Conjecture 1.

There is a constant $\alpha>0$ such that every finite family $\mathcal{F}$ of
convex sets in $\mathbb{R}^{3}$ whose elements are pairwise intersecting
contains a subfamily $\mathcal{F}^{*}$ of size at least $\alpha|\mathcal{F}|$
that has a line transversal, that is, there is a line intersecting every
element of $\mathcal{F}^{*}$.

The condition of pairwise intersecting implies that there is a two-dimensional
plane intersecting every set in $\mathcal{F}$. Indeed, projection of the sets
in $\mathcal{F}$ to a line gives a finite family of pairwise intersecting
intervals in this line. These intervals have a common point (for instance by
Helly’s theorem, one-dimensional version, see [1]), and the plane whose
projection is the common point intersects every set in $\mathcal{F}$. But we
need a line and not a plane intersecting a positive fraction of the sets in
$\mathcal{F}$.

Projecting the sets in $\mathcal{F}$ to a two-dimensional plane gives a family
of convex sets in that plane. Assume that a positive fraction of the triples
of the projected family have a point in common. The two-dimensional version of
the fractional Helly theorem of Katchalski and Liu [2] implies that a positive
fraction of the projected sets have a point in common. Thus the line whose
projection is this point intersects a positive fraction of the sets in
$\mathcal{F}$. So the conjecture holds under the more restrictive condition
that a positive fraction of the triples in $\mathcal{F}$ are intersecting.

The conjecture also holds under the condition that the sets in $\mathcal{F}$
are well-rounded. This means that there is a number $D$ such for every
$A\in\mathcal{F}$ there are concentric balls of radii $r$ and $R$ with
$r<R<Dr$ such that $A$ contains the smaller ball and the larger ball contains
$A$.

######  Proposition 1.

If $\mathcal{F}$ is well-rounded with parameter $D$, then there is a set of
lines, $\mathcal{L}$, of size at most $32D^{2}$ such that every
$A\in\mathcal{F}$ is intersected by some line in $\mathcal{L}$.

The simple proof is given in the last section.

But both conditions (“well-rounded” and “many triples intersecting”) are too
restrictive. For instance, if the family $\mathcal{F}$ consists of (finitely
many) coplanar lines with no two parallel, then any two of them intersect.
But, assuming general position, there is no intersecting triple in
$\mathcal{F}$, and $\mathcal{F}$ is not well-rounded. Yet any line in that
plane intersects every set in $\mathcal{F}$. This example shows one of the
difficulties that emerge when trying to settle Conjecture 1.

There are examples with 5 convex sets in $\mathbb{R}^{3}$ with any two of them
intersecting but with no transversal line, that is, no line intersecting all 5
of them. For instance, let $\Delta$ be a regular simplex in $\mathbb{R}^{3}$,
its closed inscribed ball be $D$. Its facets are four triangles
$F_{1},F_{2},F_{3},F_{4}$ considered without their edges. Each pair
$F_{i},F_{j}$ shares an edge. Now to both of them add the same point, one
which is very close to one endpoint if their common edge but distinct from the
endpoint. Then any two sets in the family
$\mathcal{F}=\\{D,F_{1},F_{2},F_{3},F_{4}\\}$ of convex sets have a point in
common. But they have no line transversal as one can check easily. So a line
can meet at most 4/5 of the sets in $\mathcal{F}$. Repeating $\mathcal{F}$ $m$
times is a family (of size $5m$) of pairwise intersecting convex sets in
$\mathbb{R}^{3}$ and no line can meet more than $4m$ sets in the family.

In this short note I’m going to prove a simple special case of the conjecture,
namely when $\mathcal{F}$ consists of cylinders. A cylinder in
$\mathbb{R}^{3}$ is the Minkowksi sum of a convex set $C$ and a line in in
$\mathbb{R}^{3}$.

######  Theorem 1.

Assume $\mathcal{F}$ is a finite family of cylinders in $\mathbb{R}^{3}$
having the property that any two cylinders in $\mathcal{F}$ intersect. Then
there is a line $L$ intersecting at least $\alpha|\mathcal{F}|$ elements of
$\mathcal{F}$ where $\alpha=\frac{1}{28}$.

I find Conjecture 1 and its companion Conjecture 2 (to be given in the last
section) very interesting. These conjectures are the first and apparently hard
instances of a series of analogous conjectures, see [4]. They represent a fine
and subtle version of Helly type theorems, see the old but excellent survey by
Danzer, Grünbaum, and Klee [1], or the relevant parts of Matousek’s
comprehensive book [3].

##  2\. Proof of Theorem 1

Assume $|\mathcal{F}|=n$. Every set in $\mathcal{F}$ is of the form $A=K+L$
where $K$ is a convex body and $L$ is a line in $\mathbb{R}^{3}$. We suppose,
rather for convenience than necessity, that the line $L$ contains the origin.
This implies that $K\subset A$.

We assume further that $K$ is compact using the method which is usual in Helly
type problems. Namely, for every pair $A,B\in\mathcal{F}$ where $A=K+L$ fix a
point $z(A,B)\in A\cap B$ and define $K^{new}$ as the convex hull of all
$z(A,B)$ with $B\in\mathcal{F}$, $B\neq A$. Then $K^{new}$ is compact,
$A^{new}=K^{new}+L\subset A$ is a cylinder again, and in the new system
$\\{A^{new}:A\in\mathcal{F}\\}$ any two sets intersect. Moreover, if a line
intersects $\alpha n$ sets in the new system, then the same line intersects
the same sets in the old system because $A^{new}\subset A$.

At this point we also assume that the lines of the cylinders in $\mathcal{F}$
all have different directions. This assumption will be justified at the end of
the proof.

Figure 1. A pair representing an $A$ to $B$ arc in $G$.

We are going to work with an unspecified $\alpha>0$ that will be fixed later.
We define a directed graph $G$ whose vertex set is $\mathcal{F}$, and
$A,B\in\mathcal{F}$ form an arrow $\overrightarrow{AB}$ in $G$ if $A\setminus
B$ is disconnected in $\mathbb{R}^{3}$, see Figure 1. The outdegree of every
$A\in\mathcal{F}$ is at most $\alpha n$ as otherwise every line in $A$
intersects $\alpha n$ members of $\mathcal{F}$. Then the average outdegree in
$G$ is also at most $\alpha n$. Consequently at least half of the indegrees in
$G$ is at most $2\alpha n$.

Let $\mathcal{F}^{\prime}$ be the subfamily of $\mathcal{F}$ consisting of
cylinders with indegree at most $2\alpha n$, so $|\mathcal{F}^{\prime}|\geq
n/2$. Let $C$ be the set in $\mathcal{F}^{\prime}$ whose width is minimal.
Delete all $A\in\mathcal{F}^{\prime}$ with $\overrightarrow{AC}$ an arrow in
$G$ to obtain another subfamily $\mathcal{F}^{*}\subset\mathcal{F}^{\prime}$.
Then $C\in\mathcal{F}^{*}$ and
$|\mathcal{F}^{*}|\geq\left(\frac{1}{2}-2\alpha\right)n$.

Let $P$ be the plane orthogonal to the line of $C$ and project orthogonally
every $A\in\mathcal{F}^{*}$ to $P$. The set $C$ projects to a convex (compact)
set $K\subset P$ whose width is $w\geq 0$. Each $A\in\mathcal{F}^{*}$ projects
to a slab $A^{*}\subset P$. This is the point where we use the assumption that
the directions of the lines of the cylinders in $\mathcal{F}$ are distinct.
The width of $A^{*}$ is at least $w$ because $C$ has minimal width in
$\mathcal{F}^{*}$. Note that for each $A\in\mathcal{F}^{*}$

  1. (1)

$A^{*}\setminus K$ is connected because $\overrightarrow{AC}$ is not an arrow
in the digraph $G$, and

  2. (2)

$A^{*}\cap K\neq\emptyset$.

We consider first the simple case $w=0$. Then $K$ is a segment with endpoints
$x,y$ in $P$ and $K\cap A^{*}\neq\emptyset$ because of (2). Further (1) shows
that $A^{*}\setminus K$ is connected. This together with (2) implies that
$A^{*}$ contains at least one endpoint of the segment $K$ for every
$A\in\mathcal{F}^{*}$. Consequently one of the lines $x+L$ and $y+L$
intersects half of the sets in $\mathcal{F}^{*}$, so at least
$\left(\frac{1}{4}-\alpha\right)n$ sets form $F$.

Thus $w>0$, and we may assume that $w=1$. Write $\mathcal{H}$ for the set of
all slabs $S\subset P$ of width at least 1 that intersect but do not cross
$K$, that is $S\setminus K$ is connected. In particular, $A^{*}\in\mathcal{H}$
for every $A\in\mathcal{F}^{*}$ distinct from C. We have now arrived at a
statement in plane geometry.

######  Lemma 1.

Under these conditions there is a set $T\subset P$ of at most 12 points that
intersects every $S\in\mathcal{H}$.

Figure 2. Illustration for Lemma 1.

Proof. We use the notation on Figure 2. The minimal slab containing $K$ has
width 1, the middle line of this slab intersects the boundary of $K$ in points
$a$ and $c$. Let $b$ resp. $d$ be the left-most and right-most (in the
direction of the middle line) point of $K$, as in Figure 2. Write
$\overline{ab}$ for the arc connecting points $a,b$ on the boundary of $K$,
and similarly for the arcs $\overline{bc},\overline{cd},\overline{da}$.

Suppose that $S\in\mathcal{H}$ contains none of $a,b,c,d$. Such a slab
intersects the boundary of $K$ in a subarc of one of the arcs
$\overline{ab},\overline{bc},\overline{cd},\overline{da}$. We can simply
ignore the arc $\overline{ab}$ when $a=b$, and the same for $c=d$. Consider
for instance the arc $\overline{ad}$ and build a rectangle with vertices
$a,d,e,f$ (see Figure 2) that contains this arc and where the segments $de$
and $fa$ have length $\frac{1}{2}$. It is easy to check that in this case $S$
has to contain either $e$ or $f$, we omit the details.

With each arc $\overline{bc},\overline{cd},\overline{da}$ we create 2 more
points the same way. These points, together with $a,b,c,d$, form the set $T$.∎

Finally, the twelve parallel lines $t+L$, one for each $t\in T$ intersect the
slab $A^{*}$ for every $A\in\mathcal{F}^{*}$. So one of the lines, say $\ell$
intersects $\frac{1}{12}\left(\frac{1}{2}-2\alpha\right)n$ sets from
$\mathcal{F}$. Requiring $\alpha=\frac{1}{12}\left(\frac{1}{2}-2\alpha\right)$
gives $\alpha=\frac{1}{28}$. This also covers the case $w=0$. We remark that
the direction of $\ell$ coincides with the direction of one of the sets in
$\mathcal{F}$, namely with that of $C$.

In conclusion we return to the assumption that the lines of the cylinders in
$\mathcal{F}$ have distinct directions. This is done by a standard argument
again using the previously defined points $z(A,B)$. This time it is convenient
to write $A\in\mathcal{F}$ as $A=K(A)+L(A)$ where $K(A)$ is the convex hull of
the set $\\{z(A,B):B\in\mathcal{F},B\neq A\\}$. Replace the line $L=L(A)$ of
each set $A\in\mathcal{F}$ by a sequence of lines $L_{m}(A)$, $m=1,2,\ldots$
that tends to $L$ such that the lines $\\{L_{m}(A):A\in\mathcal{F}\\}$ have
distinct directions. We assume of course that $L_{m}(A)$ contains the origin.
The system $\mathcal{F}_{m}=\\{A_{m}=K(A)+L_{m}(A):A\in\mathcal{F}\\}$
consists of cylinders that are pairwise intersecting since $z(A,B)\in
A_{m}\cap B_{m}$ for every $m$.

We just proved that for system
$\mathcal{F}_{m}=\\{A_{m}=K(A)+L_{m}(A):A\in\mathcal{F}\\}$ there is a line
$\ell_{m}$ intersecting $\alpha n$ elements of $\mathcal{F}_{m}$, and
direction of $\ell_{m}$ coincides with the direction of $L_{m}(C)$ for some
$C_{m}\in\mathcal{F}_{m}$. Along a subsequence $m^{\prime}$ (tending to
infinity) $C_{m}$ comes from the same $C\in\mathcal{F}$, that is,
$C_{m}=K(C)+L_{m}(C)$. Since $K(C)$ is compact, the lines $\ell_{m^{\prime}}$
tend to a line $\ell$ as $m^{\prime}$ goes to infinity. As every cylinder is
closed $\ell$ intersects at least $\alpha n$ sets in $\mathcal{F}$. ∎

Remarks. This proof works for the special case of cylinders but does not work
in other cases, for instance for half-cylinders that are the Minkowski sum of
a convex sets and a halfline in $\mathbb{R}^{3}$. The value of $\alpha$ can be
improved to $(1+\sqrt{13})^{-2}\approx\frac{1}{21.111}$. An interesting
extension or strengthening of Theorem 1 would be to show that, under the same
conditions, there is a set of 100 lines such that each cylinder in
$\mathcal{F}$ is intersected by one of them. Of course, any fixed number
instead of 100 would do as well.

##  3\. The bipartite case

The paper [4] gives in fact the following, more general conjecture.

######  Conjecture 2.

There is a constant $\beta>0$ such that if $\mathcal{F}$ and $\mathcal{G}$ are
finite families of convex sets in $\mathbb{R}^{3}$ with the property that
$A\cap B\neq\emptyset$ for every pair $A\in\mathcal{F}$ and $B\in\mathcal{G}$,
then there is a line intersecting at least either $\beta|\mathcal{F}|$ members
of $\mathcal{F}$ or $\beta|\mathcal{G}|$ elements of $\mathcal{G}$.

This conjecture implies the one from the introduction. An interesting example
is when $\mathcal{F}$ and $\mathcal{G}$ are (finite subsets) of the two sets
of lines on the hyperboloid with equation $x^{2}+y^{2}-z^{2}=1$. The proof
method of Theorem 1 works in the case when the sets in both families are
cylinders but only when their sizes are (approximately) equal.

######  Theorem 2.

Assume $\mathcal{F}$and $\mathcal{G}$ are finite families of cylinders in
$\mathbb{R}^{3}$ with the property that $A\cap B\neq\emptyset$ whenever
$A\in\mathcal{F}$ and $B\in\mathcal{G}$. If $|\mathcal{F}|=|\mathcal{G}|=n$,
then there is a line intersecting at least $\beta n$ members of one of
$\mathcal{F}$ and $\mathcal{G}$ where $\beta=\frac{1}{28}$.

We only give a sketch of the proof as it is similar to the previous argument.
The bipartite and directed graph with classes $\mathcal{F}$ and $\mathcal{G}$,
and the arcs $\overrightarrow{AB}$ and $\overrightarrow{BA}$ are defined the
same way as before. The outdegrees are bounded by $\beta n$ again otherwise we
have a suitable line. The average indegree in both classes is then at most
$\beta n$ and we arrive at subfamilies $\mathcal{F}^{\prime}$ and
$\mathcal{G}^{\prime}$ of size $n/2$ such that the indegrees in each are at
most $2\beta n$. Again, $C$ is the minimum width cylinder in
$\mathcal{F}^{\prime}\cup\mathcal{G}^{\prime}$, say
$C\in\mathcal{F}^{\prime}$. Deleting at most $2\beta n$ sets from
$\mathcal{G}^{\prime}$, the ones with $\overrightarrow{BC}$ an arc in the
directed graph, we have a subfamily
$\mathcal{G}^{*}\subset\mathcal{G}^{\prime}$ whose size is
$\left(\frac{1}{2}-2\beta\right)n$ and where there is no arc from
$\mathcal{G}^{*}$ to $C$. An application of Lemma 1 finishes the proof. ∎

Remark. The same argument works when $|\mathcal{F}|=n$, $|\mathcal{G}|=m$ and
$n\neq m$ but $c<n/m<1/c$ for some $c>0$. In this case the resulting $\beta$
depends on $c$ as well.

##  4\. Proof of Proposition 1

Write $G(a,r)$ for the Euclidean ball of radius $r$ centred at
$a\in\mathbb{R}^{3}$. For every $A\in\mathcal{F}$ we fix a pair of concentric
balls $G(a,r)$ and $G(a,R)$ such that $G(a,r)\subset A\subset G(a,R)$ and
$r<R<Dr$. Let $A_{0}$ be the convex body in $\mathcal{F}$ for which the radius
of the smaller ball is minimal. We can assume that this ball $G(0,1)$, that
is, the unit ball centred at the origin. Then $A_{0}$ is contained in
$G(0,D)$.

Consider $A\in\mathcal{F}$, $A\neq A_{0}$ and let $G(a,r)$ and $G(a,R)$ be the
pair of concentric balls fixed with $A$. Then $G(0,D)$ intersects $G(a,R)$
since $A_{0}\cap A\neq\emptyset$. If $a$ is at distance $T$ from the origin,
then $T\leq D+R\leq D+Dr\leq 2rD$ because $r\leq 1$ by the choice of $A_{0}$.
Thus $\frac{r}{T}>\frac{1}{2D}$. Assume $\ell$ is a line passing through the
origin and it makes an angle at most $\varphi=\arcsin\frac{1}{2D}$ with the
vector $a$. Such a line must intersect $A$ as it intersects $G(a,r)$.

The next (and last) step in the proof is to find a finite set of lines
$\mathcal{L}$ (whose size is at most $32D^{2})$, all passing through the
origin so that for every vector $a\neq 0$ there is a line $\ell\in\mathcal{L}$
such that the angle between $a$ and $\ell$ is less than $\varphi$. This is a
well-known fact, see for instance Lemma 13.1.1 in [3]. Here is a quick proof:
Let $S$ denote the sphere of radius one centred at the origin and for $x\in S$
write $C(x)$ for the set of point $y\in S$ such that the angle between $x$ and
$y$ is less than $\varphi/2$. So $C(x)$ is a cap in $S$, and of course, so is
$C(-x)$. Choose points $x_{1},x_{2},\ldots,x_{n}$ one by one as long as you
can so that the caps $C(x_{j})$ and $C(-x_{j})$ are disjoint from all previous
caps $C(x_{i})$ and $C(-x_{i})$. The area of such a cap $C(x)$ is at least
$\pi\sin^{2}(\varphi/2)$ and these $2n$ caps are disjoint, so
$2n\pi\sin^{2}(\varphi/2)\leq 4\pi$. A simple calculation shows then that
$n\leq 32D^{2}$. ∎

Remark. This proof works in higher dimensions as well showing that if
$\mathcal{F}$ is a finite family of well-rounded (with parameter $D$) convex
bodies in $\mathbb{R}^{d}$, then there is a set of lines, $\mathcal{L}$, of
size $O(D^{d-1})$ such that every $A\in\mathcal{F}$ is intersected by some
line in $\mathcal{L}$. The proof is almosy identical with the previous one.

Acknowledgements. This piece of work was partially supported by Hungarian
National Research Grants No 131529, 131696, and 133919.

## References

  * [1] L. Danzer, B. Grünbaum, B. and V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Society, Providence, R.I. 1963, 101–180,
  * [2] M. Katchalski and A. Liu, A problem of geometry in $\mathbb{R}^{n}$, Proc. Amer. Math. Soc., 75 (1979), 284–288.
  * [3] J. Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, New York, 2002.
  * [4] L. Martínez-Sandoval, E. Roldán-Pensado, N. Rubin, Further consequences of the colorful Helly hypothesis. Discrete Comput. Geom., 63 (2020), 848–866.

Imre Bárány
Rényi Institute of Mathematics
13-15 Reáltanoda Street, Budapest, 1053 Hungary,
e-mail<EMAIL_ADDRESS>and
Department of Mathematics, University College London
Gower Street, London WC1E 6BT, UK