# HLATR: Enhance Multi-stage Text Retrieval with
Hybrid List Aware Transformer Reranking

Yanzhao Zhang, Dingkun Long, Guangwei Xu, Pengjun Xie
Alibaba Group
<EMAIL_ADDRESS>

###### Abstract

Deep pre-trained language models (e,g. BERT) are effective at large-scale text
retrieval task. Existing text retrieval systems with state-of-the-art
performance usually adopt a retrieve-then-reranking architecture due to the
high computational cost of pre-trained language models and the large corpus
size. Under such a multi-stage architecture, previous studies mainly focused
on optimizing single stage of the framework thus improving the overall
retrieval performance. However, how to directly couple multi-stage features
for optimization has not been well studied. In this paper, we design Hybrid
List Aware Transformer Reranking (HLATR) as a subsequent reranking module to
incorporate both retrieval and reranking stage features. HLATR is lightweight
and can be easily parallelized with existing text retrieval systems so that
the reranking process can be performed in a single yet efficient processing.
Empirical experiments on two large-scale text retrieval datasets show that
HLATR can efficiently improve the ranking performance of existing multi-stage
text retrieval methods111Our code will be available at
https://github.com/Alibaba-NLP/HLATR.

HLATR: Enhance Multi-stage Text Retrieval with
Hybrid List Aware Transformer Reranking

Yanzhao Zhang, Dingkun Long, Guangwei Xu, Pengjun Xie Alibaba Group
<EMAIL_ADDRESS>

##  1 Introduction

Text retrieval is a task which aims to search in a large corpus for texts that
are most relevant given a query. The final retrieval result is informative and
can benefit a wide range of down streaming applications, such as open domain
question answering Karpukhin et al. (2020); Li and Lin (2021), machine reading
comprehension Rajpurkar et al. (2016); Nishida et al. (2018), and web search
systems Huang et al. (2020); Liu et al. (2021).

Since the corpus is massive in general, a practical text retrieval system
usually leverages a retrieve-then-reranking architecture due to the efficiency
and effectiveness trade-off. Specifically, given a search query, a retriever
is involved to efficiently recall a relatively small size of relevant texts
from the large corpus. Then the query and the initial retrieval results will
be passed through more delicate reranking stages to produce the final ranked
results. In recent years, the emergence of deep pre-trained language models
(PTM) Kenton and Toutanova (2019); Liu et al. (2019) has brought a storm in
natural language processing (NLP) and information retrieval fields. Text
retrieval systems armed with pre-trained language models have become a
dominant paradigm to improve the overall performance compared to traditional
statistical methods (e,g. BM25). Considering the large computational cost of
transformer-based PTMs, the retrieval stage and reranking stage usually use
different model architectures: representation-focused model and interaction-
focused model respectively Fan et al. (2021), as illustrated in Figure 1.

Figure 1: Model architectures of representation-focused model (left) and
interaction based model (right).

Based on the model structures presented in Figure 1, previous approaches to
multi-stage text retrieval roughly fall into two groups. The first group tend
to separately optimize the retrieval or reranking stage by designing task-
oriented PTMs Gao and Callan (2021a, b); Ma et al. (2021) or better model
training strategies Xiong et al. (2021); Gao et al. (2021). Studies in the
second group attend to jointly optimize the two stages by adversarial training
Zhang et al. (2021) or knowledge distillation Ren et al. (2021); Lu et al.
(2022). However, this kind of joint learning method mainly focused on
improving the retrieval stage performance by absorbing merits from the
reranking stage.

In a global view, the retrieval stage and reranking stage are highly
correlated. Intuitively, better retrieval results will definitely provide a
more enlightening signal to the reranking stage Gao et al. (2021) for both the
training and inference phase. Furthermore, since the two individual stages
adopt different model architectures (representation-focused vs interaction-
focused), we infer that the focus of the two stages is also different despite
the sharing target to estimate the relevance of query and document.
Empirically, we find that simply a weighted combination of the relevance
scores produced by the two stages can further improve the overall performance,
which also supports our hypothesis above. These observations inspire us
whether it is possible to make an additional module that couples both coarse
retrieval and fine reranking features to facilitate the final retrieval
performance.

In this paper, we propose to add an additional reranking stage with a
lightweight reranking model, which we noted as Hybrid List Aware Transformer
Ranker (HLATR). As we tend to incorporate both the two-stage features and the
reranking training objective is list aware, we adopt the transformer model
structure Vaswani et al. (2017) for HLATR. As introduced in Vaswani et al.
(2017), the content for each position of the sequential inputs includes the
embedding itself and the position embedding corresponded. Here, we carry out
the feature coupling process by taking the logit produced by the PTM based
reranking model as the embedding of each document, and we compute the position
embedding based on the retrieval ranking order of each document in the
retrieval stage. A stack of transformer layers will be used as the encoder
part. In HLATR, we can effectively fuse the retrieval and reranking features
and model the list aware text ranking process.

To verify the effectiveness and robustness of HLATR model, we conduct
experiments on two commonly used large text retrieval benchmarks, namely the
MS MARCO passage and document ranking datasets Campos et al. (2016).
Empirically experiment results demonstrate that HLATR can remarkable improve
the final text retrieval performance with different combinations of retrieval
and reranking architectures. Further we design sufficient subsidiary
experiments to prove that HLATR is lightweight and easy to practical.

##  2 Related Work

In order to balance efficiency and effectiveness, existing text retrieval
systems usually leverage a retrieval-then-reranking framework.

For the retrieval stage, traditional sparse retrieval methods adopt the exact
term matching signal for text relevance estimation (e,g. TF-IDF Luhn (1957)
and BM25 Robertson and Zaragoza (2009) method). Recently, with the rapid
development of the deep text representation method, many works shifted to
training dense retrievers by taking BERT or other deep neural networks as text
encoders Karpukhin et al. (2020); Nogueira and Cho (2019). These models
utilize dual encoders to encode queries and documents separately, which allows
pre-encoding and indexing of corpus. Under this paradigm, various optimization
strategies have been proposed to improve the retrieval performance including
designing task-specific pre-trained model Gao and Callan (2021b, a), hard
negatives mining strategy Xiong et al. (2021) and multi-view text
representation Hu et al. (2021).

For the reranking stage, previous studies use an interaction-focused model
which takes the pair of query and document as input. By considering the token
level similarity, these models always have a better ranking power Guo et al.
(2016). By such a full interaction computation strategy, the PTM based
reranking model usually reranks a small number of documents produced by the
retrieval stage. Ma et al. (2021) propose to enhance the pre-trained language
model by constructing scale pseudo relevant query-document pairs. Gao et al.
(2021) propose to replace the traditional binary cross-entropy loss Nogueira
and Cho (2019) with a contrastive loss for better list aware ranking. Pu et
al. (2021) attend to dynamically select hard negative samples to construct
high-quality semantic space the trained reranking model.

Apart from the separate optimization methods presented above, there are also
studies seeking to jointly optimize the retrieval and reranking stage. In Ren
et al. (2021), they simultaneously optimize the retrieval model and the
ranking model with a hybrid data augmentation technology. AR2 Zhang et al.
(2021) uses a Generative adversarial network (GAN) Creswell et al. (2018)
method which regards the retrieval model as the “generative mode” and the
ranker model as the “discriminative model”. All of these jointly learning
methods need a large extra training cost than the traditional two-stage
training method. In contrast, HLTAR requires only a very small additional
consumption cost.

Figure 2: An illusion of the conventional retrieve-then-reranking framework
(solid line part) and our HLTAR ranking model (solid line and dashed line
part).

##  3 Methodology

###  3.1 Problem Overview

The retrieve-then-reranking framework for text retrieval task is presented in
Fig 2. Given a query $q$, a text retrieval system aims to return a small size
list of relevant documents from a large document set
$\mathcal{D}=\\{d_{i}\\}_{i=1}^{N}$. Existing retrieval systems usually
consist of a retrieval stage and a reranking stage with different focuses on
efficiency and effectiveness. Here, for simplicity, we only introduce the
dense retrieval model and reranking model based on pre-trained language model
(as illustrated in Figure 1).

The retrieval stage takes $q$ and $\mathcal{D}$ as input and aims to return
all potentially relevant documents $\mathcal{D}_{r}\in\mathcal{D}$ refer to
the relevance between query and document, where $|\mathcal{D}_{r}|\ll N$.
Dense retrieval model focuses on leaning to map text into quality continuous
vector representation. By taking the pre-trained language model as the
encoder, the retrieval model can be formulated as:

$score(q,d)=f(E^{Q}(q),E^{D}(d)),$ (1)

where $E^{Q}$ and $E^{D}$ are query and document encoders, and $f$ is the
relevance estimation function.

Following the retrieval stage, a reranking stage takes $q$ and
$\mathcal{D}_{r}$ as input to perform a more refined relevance evaluation for
each query-document pair $(q,d)$, where $d\in\mathcal{D}_{r}$. Commonly, the
reranking model adopts the interaction-based model. Without loss of
generality, the reranking method could be abstracted by the following
formulation:

$score(q,d)=f(E^{R}(q,d)),$ (2)

where $E^{R}$ notes the PTM based encoder and $f$ is the evaluation function
that computes the relevance score.

In the retrieval stage, query and document are encoded independently.
Therefore, the embedding representation of $\mathcal{D}$ can be pre-encoded.
While in the reranking stage, the final representation of each query-document
pair can not be pre-encoded due to the interaction-based architecture. As the
result, we can only rerank a small set of documents as a result of the large
computational cost of PTM.

Despite adopting different model architectures, the retrieval and reranking
stage share the same target for evaluating the relevance of query and
document. Certainly, the training of retrieval and reranking models relies on
large-scale labeled data. Previous studies Karpukhin et al. (2020); Gao et al.
(2021) proposed to optimize the PTM based retrieval and reranking model with a
contrastive learning objective. Concretely, for each query $q$, we form a
group $G_{d}$ with a single relevant positive document $d^{+}$ and multiple
negatives. By taking the scoring function defined in equations (1)(2), the
contrastive loss for each query $q$ can be denoted as:

$\mathcal{L}_{q}:=-log\frac{exp(score(q,d^{+}))}{\sum_{p\in
G_{d}}exp(score(q,d))}.$ (3)

###  3.2 HLATR

We target on building a lightweight reranking module that couples feature from
both the retrieval and reranking stage. The overall architecture of our
proposed model is illustrated in Figure 3. Specifically, our model consists of
a feature combination layer along with a transformer encoder.

####  3.2.1 Multi-stage Feature Fusion

As the HLATR model is pipelined with the previous reranking model, HLATR takes
the query $q$ and $D_{r}^{{}^{\prime}}$ as input, where $D_{r}^{{}^{\prime}}$
is the ranking results produced by the PTM based reranking module. Obviously,
$|D_{r}|=|D_{r}^{{}^{\prime}}|=Z$, where $Z$ denotes the reranking size. Since
we adopt the transformer model architecture as the encoder, we carry out the
multi-stage features fusion via coupling the retrieval ranking order in the
retrieval stage and the final logit representation generated by the reranking
model of each document.

For document $d\in D_{r}^{{}^{\prime}}$ with retrieval order $i$ (where $0\leq
i\leq Z$), we map the $i$-th order into a learnable position embedding
$\mathbf{pe_{i}}\in{\mathbf{R}^{d}}$ with dimension $d$, and which will be
jointly optimized during the learning process. The position embedding is
randomly initialized. The strategy of introducing retrieval order as a feature
makes our model not only practicable for systems that use dense retrieval
models, but also for others based on traditional statistical retrieval methods
(e.g, BM25).

For the reranking stage, we hire the final encoded representation
$E^{R}(q,d)$, which is converted to an embedding representation sharing the
same dimension as the position embedding:

$v_{i}=W_{v}^{T}E^{R}(q,d_{i}),$ (4)

where $W_{v}$ is the trainable projection matrix.

Then, for each $d_{i}$ in $D_{r}^{{}^{\prime}}$, we can directly add $pe_{i}$
and $v_{i}$ to build the input matrix $H^{0}\in R^{d\times Z}$:

$\displaystyle H^{0}=\begin{pmatrix}LN(pe_{1}+v_{1})\\\ LN(pe_{2}+v_{2})\\\
...\\\ LN(pe_{Z}+v_{Z})\end{pmatrix},$

where LN represents the LayerNorm Ba et al. (2016) operation.

####  3.2.2 Transformer Encoder

The learning process of the reranking model is list aware. The key point of a
reranking module is to model and learn the partial order relationship between
different documents within the entire candidates pool. Thus, we adopt the
transformer architecture Vaswani et al. (2017) as the encoder owing to its
long-distance modeling ability and full attention mechanism. The self-
attention mechanism in the transformer can directly model the mutual
influences for any different query-documents pair sample.

The entire encoder module consists of $L$ transformer layers. The hidden size
of each Transformer layer is set equal to the input dimension $d$. For the
first Transformer layer, it takes $H^{0}$ as input. While for the $l$-th
Transformer layer $T^{l}$, it takes the output of the previous layer as input:

$\displaystyle H^{1}=T^{1}(H^{0}),$ $\displaystyle H^{l}=T^{l}(H^{l-1}).$

####  3.2.3 Learning Objective

Finally, we use a linear projection layer to predict the relevance score
between the input query $q$ and $D_{r}^{{}^{\prime}}$. For each $d_{i}\in
D_{r}^{{}^{\prime}}$, the final relevance score can be represented as:

$score(q,d_{i})=W^{T}H^{l}_{i}.$ (5)

Similar to the previous stage, we optimize HLATR with a list-wise contrastive
loss Gao et al. (2021):

$\mathcal{L}_{\\{q,D_{r}^{{}^{\prime}}\\}}=-log\frac{exp(score(q,d^{+}))}{\sum_{d\in
D_{r}^{{}^{\prime}}}exp(score(q,d))}.$ (6)

Figure 3: Thee detailed network structure of our HLATR (Hybrid List Aware
Transformer Reranking) model.

From the perspective of the learning objective, HLATR can also be classified
as a reranking model, which takes a query $q$ and a document list as input and
then produces the relevance score of each query-document pair among all
candidate documents. HLATR is different from the previous reranking model
based on the pre-trained language model. We sort out the difference between
the two modules from three aspects:

1) Superficially, the input of HLATR and the PTM based reranking model is the
query $q$ and its corresponding candidate document list. Indeed, the PTM based
reranking model uses the raw content of query and document as input, but HLATR
uses the combination of features generated by the previous two stages as
input.

2) Moreover, the calculation paradigm of the final ranking score is also
different. In the PTM based reranking model, the relevance score of each
query-doc pair is calculated independently. In the HLATR model, the relevance
score of the entire input document list is calculated at one time through the
serialization computing mechanism of the transformer architecture. Such a list
aware calculation method allows us to better model the mutual relationship
between the different documents in the entire input document list.

3) During the training process, for PTM based reranking model, we have to
control the data size of each mini-batch via a random sampling strategy when
constructing $G_{q}$ for each query $q$ due to the high computational cost of
PTM. The lightweight nature of HLATR allows us to use the entire retrieval
results to construct the set of negatives, thereby greatly expanding the
number of negative samples in each mini-batch. A previous study has proven
that the larger number of negative samples can effectively improve the
reranking performance under the contrastive learning optimization objective
Gao et al. (2021).

##  4 Experiment

###  4.1 Setup

Dataset In this paper, we conduct experiments on two widely-used large-scale
text retrieval datasets: MS MARCO Passage (called “Passage” below for
simplicity) dataset and MS MARCO Document (called “Document” below) dataset.
The MS MARCO dataset is constructed from Bingś search query logs and web
documents retrieved by Bing. The statistic information of MS MARCO dataset is
presented in Table 1. Since the number of parameters of HLATR is much smaller
compared with the PTM reranking model, we only need to use a small amount of
data to train the HLATR model. For the passage dataset, there exists an extra
dev dataset which contains $34,000$ queries which can be used as training
dataset. For the document dataset, we split $50,000$ queries from the orinal
training dataset as the final training dataset for HLATR.

Evaluation Metric Following the evaluation methodology used in previous work,
we report MRR@10 and MRR@100 results for the MS MARCO dev dataset due to the
label of test data is not available.

Table 1: Statistics of MA MARCO dataset. “#Length” represents the average text length and “#Relvant” represents the number of the labeled relevant documents per query. We only count the query which at least has one relevant document. Dataset | Document | Passage
---|---|---
#Query | 367013/5193 | 502939/6980
#Document | 3213835 | 8841823
#Length | 56.8 | 1127.8
#Relevant | 1.04 | 1.06
Table 2: MRR@10 and MRR@100 metrics for MS MARCO Passage and Document Dataset
with different kinds of retrieval and reranking models. We bold the best
performances of each combination of retrieval and reraking model. The results
of HLATR are statistically significant difference ($p$ < $0.01$) compared to
other models.

Model/Dataset | Passage | Document
---|---|---
PTM |  | Sparse | Dense | Sparse | Dense
MRR@10 | MRR@100 | MRR@10 | MRR@100 | MRR@10 | MRR@100 | MRR@10 | MRR@100
Retrieval Only | 18.7 | 19.8 | 38.3 | 39.4 | 20.9 | 22.2 | 36.8 | 37.9
BERT${}_{\text{b}ase}$ | Reranking | 34.4 | 35.5 | 40.1 | 41.1 | 40.4 | 40.9 | 43.4 | 44.2
WCR | 34.5 | 35.6 | 41.5 | 42.4 | 40.6 | 41.1 | 44.3 | 45.1
HLATR | 35.0 | 36.0 | 42.0 | 42.9 | 42.0 | 42.5 | 44.5 | 45.2
BERT${}_{\text{l}arge}$ | Reranking | 35.4 | 36.3 | 41.0 | 42.0 | 40.6 | 41.1 | 44.2 | 45.0
WCR | 35.6 | 36.6 | 42.0 | 42.9 | 40.8 | 41.3 | 45.2 | 45.9
HLATR | 35.9 | 36.7 | 42.4 | 43.4 | 42.2 | 42.8 | 45.6 | 46.3
RoBERTa${}_{\text{b}ase}$ | Reranking | 34.9 | 36.1 | 40.8 | 41.7 | 40.6 | 41.0 | 44.3 | 45.1
WCR | 35.2 | 36.3 | 42.0 | 42.9 | 41.0 | 41.6 | 45.1 | 45.8
HLATR | 35.5 | 36.5 | 42.5 | 43.5 | 42.0 | 42.4 | 45.4 | 46.1
RoBERTa${}_{\text{l}arge}$ | Reranking | 36.2 | 37.2 | 41.6 | 42.6 | 40.8 | 41.2 | 45.2 | 45.9
WCR | 36.4 | 37.4 | 42.9 | 43.9 | 41.2 | 41.6 | 45.7 | 46.4
HLATR | 36.8 | 37.8 | 43.7 | 44.5 | 42.3 | 42.7 | 45.9 | 46.6

Table 3: Hyperameters for HLATR, Ranker for Passage Dataset (Ranker(P)) and Document (Ranker(D)), lr represents learning rate, $k$ is the number of hard negatives, $n$ is the number of transformer layers, head is the attention head for each transformer layer, $d$ is the dimension of $v$. | HLATR | Rerenk(P) | Ranker(D)
---|---|---|---
lr | 1e-3 | 1e-5 | 1e-5
batch size | 1024 | 256 | 128
epoch | 40 | 3 | 3
k | 100 | 8 | 4
n | 4 | 12/24 | 12/24
head | 2 | 12 | 12
d | 128 | 768/1024 | 768/1024

Implementation Details To verify the efficiency and robustness of the HLATR
module, we implement the experiments with different retrieval and reranking
models. For the retrieval stage, we report results based on both sparse and
dense retrieval methods. Specifically, we choose the BM25 method as the sparse
retrieval model, and two state-of-the-art dense retrieval models coCondenser
Gao and Callan (2021b) and ANCE Xiong et al. (2021) for passage and document
retrieval respectively. For the reranking stage, we leverage the commonly used
reranking method based on the pre-trained language model as presented in
Nogueira and Cho (2019); Gao et al. (2021). However, we conduct experiments
based on different pre-trained language models (BERT${}_{\text{b}ase}$,
BERT${}_{\text{l}arge}$, RoBERTa${}_{\text{b}ase}$,
RoBERTa${}_{\text{l}arge}$) to verify the robustness of HLATR.

We implement the BM25 retrieval process by the pyserini toolkit Lin et al.
(2021). For ANCE222https://github.com/microsoft/ANCE and
coCondenser333https://github.com/luyug/Condenser methods, we use the publicly
released checkpoint by authors. Following previous studies, for the passage
dataset, we use the body field as the document text. For the document dataset,
we combine the url, title and body field as the final document text. The
maximum token length is set to $128$ and $512$ respectively. Detailed hype-
parameters used in our experiments can be found in Table 3.

Baselines We compare HLATR with the conventional retrieve-then-reranking
models and the simple Weighted Combination of two-stage Ranking models (WCR).
For each query-document pair, the WCR method directly weights combined the
relevance scores produced by the retrieval stage reranking stage as the final
ranking score:

$\alpha f(E^{Q}(q),E^{D}(d))+(1-\alpha)f(E^{R}(q,d)),$ (7)

where $\alpha\in(0,1)$.

###  4.2 Results

Table 2 presents the final results of our method for both passage and document
datasets. We highlight the best performances of each metric in bold. We find
that our approach achieves the best performance among all the baselines.

Our model improves the text retrieval performances by a large margin compared
to the conventional retrieve-then-reranking two-stage architecture.
Specifically, the HLATR enhanced text retrieval systems improve the MRR@10
metric on passage and document datasets from $40.1$ to $42.0$ and $43.4$ to
$44.5$ respectively under the dense retrieval and BERT-base reranking setting.
This observation illustrates the effectiveness of combining features from the
previous retrieval and reranking stage to improve the final ranking
performance.

We can also observe that HLATR achieves consistent improvement whether using
sparse or dense retrieval methods. We train the reranking models based on
different pre-trained language models. Firstly, whether for the BERT or
RoBERTa model, the performance of the large model is stably better than that
of the base model, which is consistent with the results of previous studies
Gao et al. (2021); Ma et al. (2021). Moreover, based on different reranking
models, the improvement of the HLATR model is consistent. The above
experimental result strongly depicts the robustness of our HLATR model.

For each experimental setting, we also report the results of the WCR method.
We can see that the WCR method can effectively improve the retrieval
performance, which once again proves the effectiveness of the motivation in
coupling retrieval and reranking features. However, we can also observe that
the effect of the WCR model still lags behind the HLATR model, which further
illustrates that HLATR is a model advisable architecture for large-scale text
retrieval task from the perspective of coupling features.

###  4.3 Discussion and Analysis

Multi-stage Feature Coupling We further evaluate the influence of the feature
coupling mechanism in HLATR. The experimental results are presented in Table
4. “w/o retrieval” denotes the setting that removes the retrieval feature and
only uses the reranking stage feature as input for HLATR. Similarly, “w/o
reranking” notes the setting that we remove the reranking stage feature for
HLATR. Unlike the “w/o retrieval” setting, only adopting “position embedding”
as input for the transformer encoder is extra-conventional. Therefore, we
replace the reranking stage feature vector with the query embedding and
document embedding generated by the dense retrieval model. We tried several
methods to concatenate these two embeddings and we find that the element-wise
multiply performs best. So we only report the result based on the element-wise
multiply concatenation method.

From Table 4, we can observe that when the input feature of HLATR only
contains one of the retrieval or reranking features alone, the overall ranking
performance is still slightly improved. For example, the “w/o reranking”
setting improves the MRR@10 value from $38.3$ to $39.0$ compared to the simple
retrieval performance. Notably, the coupled feature input will lead to an
improvement with a larger margin. This experimental result shows that coupling
multi-stage features can indeed improve the final reranking performance.

Table 4: Ablation experiments result on MS MARCO Passage dataset. Dense model for retrieval stage and BERTbase model for reranking stage. Model | Passage
---|---
MRR@10 | MRR@100
Retrieval | 38.3 | 39.4
Reranking | 40.8 | 41.8
HLATR | 42.6 | 43.5
w/o retrieval | 41.2 | 42.2
w/o ranker | 39.0 | 39.9
Table 5: Experiment result on MS MARCO Passage dataset of HLATR and its two variants. Model | Passage
---|---
MRR@10 | MRR@100
HLATR | 42.6 | 43.5
WCR | 41.8 | 42.8
HLATRlinear | 42.4 | 43.3
HLATRbce | 41.7 | 42.6

Architecture analysis of HLATR To better analyze the advantages of our model
in tackling the list aware text reranking problem, we conduct experiments with
two variants:

1) HLATRlinear: In this model, we replace the multi-layer transformer with a
two-layer MLP model with ReLU as the activation function.

2) HLATRbce: In this model, we replace the original contrastive loss with
binary cross-entropy loss, which can be formulated as:

$\displaystyle\mathcal{L}_{bce}(q,D_{r}^{{}^{\prime}})=\frac{1}{Z}\sum_{i}^{Z}(y_{i}\log(\sigma(score(q,d_{i})))$
$\displaystyle+(1-y_{i})\log(1-\sigma(score(q,d_{i}))),$

where $y_{i}$ is the $\\{0,1\\}$ label indicates whether this document is
relevant to the query and $\sigma$ denotes the sigmoid activation function.

The experiment result is presented in table 5, from which we can see that with
just a $2$-layer MLP encoder, HLATR can still outperform the WCR method
significantly. However, compared with the HLATR model that uses the
transformer structure as encoder, the performance of HLATRlinear is degraded.
We can infer that for such a list aware reranking task, the transformer model
has a better ability in modeling the mutual associations between different
documents in the input sequence.

Further, by comparing the performance of the HLATRbce model and the original
model, we can conclude that the contrastive learning objective is more proper
for the text ranking learning process. The essential reason is that the text
reranking task is an optimization problem with imbalanced data. In the input
sequence, the number of negative samples is much larger than the number of
positive samples, and the loss of contrastive learning is more advantageous in
dealing with such a data imbalance scenario.

Table 6: Time cost for different reranking models and HLATR model for per 1000 queries. The time cost for RoBERTabase and RoBERTalarge is similar with the BERTbase/large model. So we only report the result of BERT models. Model | Passage | Document
---|---|---
BERT${}_{\text{b}ase}$ | 600ms | 800ms
BERT${}_{\text{l}arge}$ | 900ms | 1200ms
HLATR | 2ms | 2ms

Computational Cost of HLATR To test the efficiency of HLATR, here we report
the inference time cost for different kinds of ranking models and the HLATR
model. All experiments are conducted on NVIDIA Tesla 32G V100.

In Table 6, we can see that the time cost of HLATR is significantly smaller
than the PTM based reranking models. On the passage reranking dataset, HLATR
is $300$/$450$ times more computationally efficient. Therefore, although we
add an extra reranking stage, it only adds a little time cost compared with
the whole retrieve-then-reranking process due to its small size of parameters
and effective way to calculate the relevance score.

Hyper-parameters of Transformer In this part, we wish to explore how the
architecture of the transformer-based encoder affects the ranking performance.
In Fig 4, we compare the MRR@10 metric with different settings of number of
transformer layers and its hidden dimension $d$ on the Passage Ranking
dataset. We can see that the performance increases first and drop later when
the number of layer increases. The larger $d$ is, the inflection point comes
earlier. A small dimension size like $128$ leads to a better performance than
a large dimension size like $512$. This can be attributed that the aim of
HLATR is only designed to make use of the first two-stages features produced
by the large-scale pre-trained model. So that it does not need a big number of
parameters. Consequently, we need to balance the “width” and the “depth” of
HLATR to achieve the best performance.

Figure 4: The impact of Transformer architecture with different dimensions of
hidden states $d$ and number of layers. The horizontal axis represents the
number of transformer layers and the vertical axis represents the MRR@10
metric.

##  5 Conclusion

In this paper, we intuitively propose a unified hybrid list aware transformer
reranking (HLATR) model via coupling retrieval and reranking features for
multi-stage text retrieval task. The HLATR model is lightweight and can be
easily applied to existing systems. Experiments on two large scale text
retrieval datasets show our framework significantly outperforms previous
baselines.

## References

  * Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. 2016.  Layer normalization.  _arXiv preprint arXiv:1607.06450_.
  * Campos et al. (2016) Daniel Fernando Campos, Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, Li Deng, and Bhaskar Mitra. 2016.  Ms marco: A human generated machine reading comprehension dataset.  _ArXiv_.
  * Creswell et al. (2018) Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil A Bharath. 2018.  Generative adversarial networks: An overview.  _IEEE Signal Processing Magazine_.
  * Fan et al. (2021) Yixing Fan, Xiaohui Xie, Yinqiong Cai, Jia Chen, Xinyu Ma, Xiangsheng Li, Ruqing Zhang, Jiafeng Guo, and Yiqun Liu. 2021.  Pre-training methods in information retrieval.  _arXiv preprint arXiv:2111.13853_.
  * Gao and Callan (2021a) Luyu Gao and Jamie Callan. 2021a.  Condenser: a pre-training architecture for dense retrieval.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 981–993.
  * Gao and Callan (2021b) Luyu Gao and Jamie Callan. 2021b.  Unsupervised corpus aware language model pre-training for dense passage retrieval.  _arXiv preprint arXiv:2108.05540_.
  * Gao et al. (2021) Luyu Gao, Zhuyun Dai, and Jamie Callan. 2021.  Rethink training of bert rerankers in multi-stage retrieval pipeline.  In _European Conference on Information Retrieval_.
  * Guo et al. (2016) Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft. 2016.  A deep relevance matching model for ad-hoc retrieval.  In _Proceedings of the 25th ACM international on conference on information and knowledge management_.
  * Hu et al. (2021) Zechuan Hu, Yong Jiang, Nguyen Bach, Tao Wang, Zhongqiang Huang, Fei Huang, and Kewei Tu. 2021.  Multi-view cross-lingual structured prediction with minimum supervision.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. Association for Computational Linguistics.
  * Huang et al. (2020) Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giuseppe Ottaviano, and Linjun Yang. 2020.  Embedding-based retrieval in facebook search.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2553–2561.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  _arXiv preprint arXiv:2004.04906_.
  * Kenton and Toutanova (2019) Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of NAACL-HLT_ , pages 4171–4186.
  * Li and Lin (2021) Minghan Li and Jimmy Lin. 2021.  Encoder adaptation of dense passage retrieval for open-domain question answering.  _arXiv preprint arXiv:2110.01599_.
  * Lin et al. (2021) Jimmy Lin, Xueguang Ma, Sheng-Chieh Lin, Jheng-Hong Yang, Ronak Pradeep, and Rodrigo Nogueira. 2021.  Pyserini: A python toolkit for reproducible information retrieval research with sparse and dense representations.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 2356–2362.
  * Liu et al. (2021) Yiding Liu, Weixue Lu, Suqi Cheng, Daiting Shi, Shuaiqiang Wang, Zhicong Cheng, and Dawei Yin. 2021.  Pre-trained language model for web-scale retrieval in baidu search.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 3365–3375.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Lu et al. (2022) Yuxiang Lu, Yiding Liu, Jiaxiang Liu, Yunsheng Shi, Zhengjie Huang, Shikun Feng Yu Sun, Hao Tian, Hua Wu, Shuaiqiang Wang, Dawei Yin, and Haifeng Wang. 2022\.  Ernie-search: Bridging cross-encoder with dual-encoder via self on-the-fly distillation for dense passage retrieval.
  * Luhn (1957) Hans Peter Luhn. 1957.  A statistical approach to mechanized encoding and searching of literary information.  _IBM Journal of research and development_.
  * Ma et al. (2021) Xinyu Ma, Jiafeng Guo, Ruqing Zhang, Yixing Fan, Yingyan Li, and Xueqi Cheng. 2021\.  B-prop: bootstrapped pre-training with representative words prediction for ad-hoc retrieval.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 1513–1522.
  * Nishida et al. (2018) Kyosuke Nishida, Itsumi Saito, Atsushi Otsuka, Hisako Asano, and Junji Tomita. 2018\.  Retrieve-and-read: Multi-task learning of information retrieval and reading comprehension.  _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_.
  * Nogueira and Cho (2019) Rodrigo Nogueira and Kyunghyun Cho. 2019.  Passage re-ranking with bert.  _arXiv preprint arXiv:1901.04085_.
  * Pu et al. (2021) Ruizhi Pu, Xinyu Zhang, Ruofei Lai, Zikai Guo, Yinxia Zhang, Hao Jiang, Yongkang Wu, Yantao Jia, Zhicheng Dou, and Zhao Cao. 2021.  Yes sir! optimizing semantic space of negatives with self-involvement ranker.  _arXiv preprint arXiv:2109.06436_.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392.
  * Ren et al. (2021) Ruiyang Ren, Yingqi Qu, Jing Liu, Wayne Xin Zhao, Qiaoqiao She, Hua Wu, Haifeng Wang, and Ji-Rong Wen. 2021.  Rocketqav2: A joint training method for dense passage retrieval and passage re-ranking.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2825–2835.
  * Robertson and Zaragoza (2009) Stephen Robertson and Hugo Zaragoza. 2009.  _The probabilistic relevance framework: BM25 and beyond_.  Now Publishers Inc.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Xiong et al. (2021) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  In _International Conference on Learning Representations_.
  * Zhang et al. (2021) Hang Zhang, Yeyun Gong, Yelong Shen, Jiancheng Lv, Nan Duan, and Weizhu Chen. 2021\.  Adversarial retriever-ranker for dense text retrieval.  _arXiv preprint arXiv:2110.03611_.


# Unique continuation on planar graphs

Ahmed Bou-Rabee  ,  William Cooperman  and  Shirshendu Ganguly

###### Abstract.

We show that a discrete harmonic function which is bounded on a large portion
of a periodic planar graph is constant. A key ingredient is a new unique
continuation result for the weighted graph Laplacian. The proof relies on the
structure of level sets of discrete harmonic functions, using arguments as in
Bou-Rabee–Cooperman–Dario (2023) which exploit the fact that, on a planar
graph, the sub- and super-level sets cannot cross over each other. In the
special case of the square lattice this yields a new, geometric proof of the
Liouville theorem of Buhovsky–Logunov–Malinnikova–Sodin (2017).

##  1\. Introduction

A periodic planar graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is a graph for
which there exists an embedding into the plane $\operatorname{\mathbb{R}}^{2}$
which is invariant under translation by a two-dimensional-lattice
$\mathcal{L}$. We fix such an embedding and consider the weighted graph
Laplacian on $\mathcal{G}$,

$\Delta f(u)=\sum_{w\sim u}\mathbf{a}(u,w)(f(u)-f(w))\,,$

where the sum is over the vertices $w\in\mathcal{V}$ adjacent to $u$ and the
conductance, $\mathbf{a}$, is a strictly positive function on the set of
undirected edges $\mathcal{E}$. Designate a vertex closest to zero as the
origin and let $B_{n}$ denote the graph-metric ball of radius $n$ centered at
the origin. We write $\mathcal{F}:=\mathcal{G}/2\mathcal{L}$ to denote a
(finite) quotient of the graph which, together with $\mathcal{L}$, contains
all of the information needed to reconstruct $\mathcal{G}$. Abusing notation,
we identify the vertex set $\mathcal{V}$ of $\mathcal{G}$ with its image in
$\operatorname{\mathbb{R}}^{2}$ under the embedding.

Figure 1. Some periodic planar graphs.

Recall that any bounded harmonic function on $\mathcal{G}$ is constant. Our
main result is the following improvement of this Liouville theorem.

######  Theorem 1.1.

Suppose that the conductances $\mathbf{a}$ are invariant under translation by
$\mathcal{L}$. Then there is some $\varepsilon=\varepsilon(\mathbf{a})>0$ such
that, if $\Delta f=0$ on $\mathcal{G}$ and

$\lim_{n\to\infty}\frac{|\\{|f|\leq 1\\}\cap B_{n}|}{|B_{n}|}\geq
1-\varepsilon\,,$

then $f$ is constant.

In the special case of $\operatorname{\mathbb{Z}}^{2}$ with unit conductance,
Buhovsky–Logunov–Malinnikova–Sodin in [BLMS22] established Theorem 1.1 via a
delicate argument involving the polynomial structure of discrete harmonic
functions on $\operatorname{\mathbb{Z}}^{2}$. They proved two competing
statements. First they showed, using the three-ball inequality, that a non-
constant discrete harmonic function which is bounded on most of
$\operatorname{\mathbb{Z}}^{2}$ must grow at least exponentially. This result
is quite general and, as we indicate in the appendix, also holds for periodic
graphs. Second, using the square lattice structure, they proved an exponential
upper bound for the growth of such a function, with an exponent which tends to
zero as $\varepsilon\to 0$. One of their key observations is that a discrete
harmonic function on $\operatorname{\mathbb{Z}}^{2}$, which vanishes on two
parallel diagonals, is equal (up to a sign) to a polynomial on subsequent
diagonals. Unfortunately, this polynomial structure is no longer present on
general planar graphs, or even on $\operatorname{\mathbb{Z}}^{2}$ when the
conductances are not constant.

Our main contribution is a completely new proof of this exponential upper
bound. This may also be thought of as a unique continuation result. The
argument is based on a topological property of the level sets of planar
discrete harmonic functions and is therefore robust to changes in the
underlying graph. Similar topological arguments were previously used by Dario
and the first two authors in a study of harmonic functions on the
supercritical percolation cluster [BRCD23].

Some basic features of non-crossing level sets in the plane have been used
previously, e.g., in Serrin’s proof of the Harnack inequality [Ser56]. We take
a more quantitative approach and study the structure of the intersection
points between sub- and super-level sets of zero. On the one hand, planarity
forces these two sets to interleave and this ensures the existence of many
distinct connected components of each set. On the other, each component
intersects at least one vertex on the boundary of the domain, so there cannot
be too many.

######  Theorem 1.2.

Suppose the conductances are uniformly bounded via
$0<\lambda<\mathbf{a}<\Lambda<\infty$. Then there exist positive constants
$\varepsilon_{0}(\mathcal{F},\Lambda/\lambda)$, $n_{0}(\mathcal{F})$, and
$A(\mathcal{F},\Lambda/\lambda)$ such that for all $n\geq n_{0}$ and
$\varepsilon<\varepsilon_{0}$, if $\Delta f=0$ on $B_{2n}$ and $|\\{x\in
B_{2n}\mid|f(x)|>1\\}|\leq\varepsilon|B_{2n}|$, then $\max_{B_{n}}|f|\leq
e^{(A\sqrt{\varepsilon})n}$.

Following the arguments in [BLMS22], the exponential lower bound, Theorem A.1,
together with the exponential upper bound, Theorem 1.2, establishes Theorem
1.1.

The same argument to prove Theorem 1.2 can be used to provide a short proof of
Theorem 1.1 (with no assumptions on $\mathbf{a}$ other than positivity) when
the discrete harmonic function is not just bounded but also vanishes on a
large portion of the graph.

######  Theorem 1.3.

There exist positive constants $\varepsilon_{0}(\mathcal{F})$ and
$n_{0}(\mathcal{F})$ such that if $\Delta f=0$ on $B_{2n}$ for $n\geq n_{0}$
and $|\\{x\in B_{2n}\mid|f(x)|\neq 0\\}|\leq\varepsilon|B_{2n}|$, for
$\varepsilon<\varepsilon_{0}$, then $f\equiv 0$ on $B_{n}$.

Our theorems require the discrete two-dimensional structure as encapsulated in
Lemma 2.1 below. As explained in [BLMS22, Remark 1.3], there counterexamples
on $\operatorname{\mathbb{Z}}^{d}$ for $d\geq 3$ and on
$\operatorname{\mathbb{R}}^{2}$. For instance, the function $(x,y,z)\to
c^{z}(-1)^{x}1_{\\{x=y\\}}$ for $c$ satisfying $c+c^{-1}=6$ is harmonic on
$\operatorname{\mathbb{Z}}^{3}$. Planarity is also essential — as indicated in
Section 5, there is a family of non-planar conductances on
$\operatorname{\mathbb{Z}}^{2}$ for which Theorem 1.3 fails.

An important application of unique continuation results of this form is
Anderson localization. Ding–Smart [DS20] used ideas from [BLMS22] as input
into the program of Bourgain–Kenig [BK05] to prove localization near the edge
for the Anderson–Bernoulli model on $\operatorname{\mathbb{Z}}^{2}$. This
result was generalized to $\operatorname{\mathbb{Z}}^{3}$ by Li–Zhang [LZ22],
where, as part of their argument, they proved a version of Theorem 1.2 on the
triangular lattice using ideas from [BLMS22].

Throughout $c,C$ denote positive constants that may differ in each instance.
Dependence is indicated by, e.g., $C(d)$.

### Acknowledgments

Thank you to Scott Armstrong, Paul Dario, Lionel Levine, and Charles Smart for
useful discussions and suggestions. A.B. was partially supported by NSF grant
DMS-2202940 and a Stevanovich fellowship. W.C. was partially supported by NSF
grant DMS-2303355. S.G. was partially supported by NSF grants DMS-1855688,
DMS-1945172, and a Sloan Fellowship.

##  2\. A topological lemma

Figure 2. Sets satisfying the properties of Lemma 2.1. The cycle $\gamma$ is
drawn as a black circle, the set $Z$ as dark orange crosses, and sets $P$ and
$M$ as red dotted and blue dashed lines respectively.

We give a geometric constraint on the level sets of a discrete harmonic
function $f$ on a planar graph. This is the key topological observation
underlying our arguments. One may think of the set $Z$ as the zero set of $f$,
the set $P$ as the zero superlevel set (pluses), and the set $M$ as the zero
sublevel set (minuses). Roughly, the conclusion is that $f$ cannot have too
many zeros on a circle without being identically zero in the half ball.

######  Lemma 2.1.

Let $\gamma:=\\{v_{0},v_{1},\dots,v_{k}=v_{0}\\}$ be a cycle in $\mathcal{G}$
and let sets $Z,P,M\subseteq\mathcal{V}$ be disjoint and satisfy the following
properties.

  1. (1)

$Z\subseteq\gamma$.

  2. (2)

$P$ and $M$ are contained in the union of $\gamma$ and the finite component of
$\mathcal{G}\setminus\gamma$.

  3. (3)

For every $z\in Z$, there is a path
$\beta:=\\{z=w_{0},w_{1},\dots,w_{\ell}\\}$ along a face of $\mathcal{G}$
adjacent to $z$, such that $\beta\cap(P\cup M)=\emptyset$ and $w_{\ell}$ is
adjacent to vertices $p(z)\in P$ and $m(z)\in M$. If there are multiple such
vertices, we choose $p(z)$ and $m(z)$ arbitrarily.

  4. (4)

Every connected component of the induced subgraph $\mathcal{G}[P]$
(respectively of $\mathcal{G}[M]$) intersects $\gamma\setminus Z$.

Then, for a constant $\alpha_{\mathcal{F}}\in(0,1)$ depending only on the
maximum degree in the graph $\mathcal{G}$, we have
$|Z|\leq\alpha_{\mathcal{F}}|\gamma|$.

###### Proof.

For each $v_{i}\in Z$, we define
$\operatorname{\mbox{prev}}_{P}(v_{i})\in\gamma\setminus Z$ (resp.
$\operatorname{\mbox{prev}}_{M}(v_{i})$) to be $v_{i-j\pmod{k}}$, where $j$ is
smallest in $\\{1,\dots,k\\}$ such that $v_{i-j\pmod{k}}$ lies in the
connected component of $p(v_{i})$ in $\mathcal{G}[P]$ (resp. $m(v_{i})$ in
$\mathcal{G}[M]$).

Let $Z=\\{v_{j_{1}},v_{j_{2}},\dots,v_{j_{|Z|}}\\}$, where $0\leq
j_{1}<j_{2}<\cdots<j_{|Z|}<k$ and choose a maximal subset
$Z^{\prime}=\\{v_{i_{1}},v_{i_{2}},\dots,v_{i_{|Z|}}\\}$ so that $p(z)\neq
p(\tilde{z})$ and $m(z)\neq m(\tilde{z})$ for $z\neq\tilde{z}\in Z^{\prime}$.
Note that by (3), we have that

(1) $\frac{|Z^{\prime}|}{|Z|}\geq(2(\mbox{max degree in
$\mathcal{G}$}))^{-1}\,.$

We trace out the cycle $\gamma$ and argue, using planarity, that each time we
encounter a vertex in $Z^{\prime}$, there must be a new vertex in
$\gamma\setminus Z$. To that end, for each $j=0,\dots,|Z^{\prime}|$, we
iteratively build sets $S_{j}\subseteq\gamma\setminus Z$ as follows. Start
with $S_{0}:=\emptyset$. Given $j\geq 0$, consider three cases.

  1. (1)

If $\operatorname{\mbox{prev}}_{P}(v_{i_{j}})\not\in S_{j}$ then set
$S_{j+1}:=S_{j}\cup\\{\operatorname{\mbox{prev}}_{P}(v_{i_{j}})\\}$.

  2. (2)

Otherwise, let $k<j$ be the smallest index such that
$\operatorname{\mbox{prev}}_{P}(v_{i_{k}})=\operatorname{\mbox{prev}}_{P}(v_{i_{j}})$.
If $k=j-1$, then set $S_{j+1}:=S_{j}$.

  3. (3)

Otherwise, we set
$S_{j+1}:=S_{j}\cup\\{\operatorname{\mbox{prev}}_{M}(v_{i_{j-1}})\\}$.

We claim that in each step we are only adding vertices which are not already
in the set. We need only argue that in the third case,
$\operatorname{\mbox{prev}}_{M}(v_{i_{j-1}})\not\in S_{j}$. However, observe
that a vertex in $M$ is in $S_{j}$ only if it is enclosed by a loop with
vertices $v_{i_{j}}$ and $v_{i_{k}}$ – see Figure 3 – and only one such vertex
which is enclosed by the loop is added. Thus, by the Jordan curve theorem, the
vertices in $M$ which are added must be disjoint.

Hence, by construction and (1), we have

$|\gamma\setminus
Z|\geq|S_{|Z^{\prime}|}|\geq\frac{1}{2}|Z^{\prime}|\geq(4(\mbox{max degree in
$\mathcal{G}$}))^{-1}|Z|\,,$

which concludes the proof. ∎

Figure 3. Case 3 in the proof of Lemma 2.1. Although the loop enclosing
$\operatorname{\mbox{prev}}_{M}(v_{i-1})$ could touch $\gamma$ in multiple
places this does not affect the proof. Note that the loop ensures that for all
$j>i$ we have $\operatorname{\mbox{prev}}_{M}(v_{j})\neq v_{j^{\prime}}$ for
each $j^{\prime}\in[i-4,i]$. The same color scheme as Figure 2 is used.

##  3\. Many zeros implies identically zero

Let $\mathcal{G}^{*}$ be the dual graph of $\mathcal{G}$ whose vertices are
the faces of $\mathcal{G}$ and whose edges correspond to adjacent faces of
$\mathcal{G}$. Denote by $\partial B_{m}$ the set of faces in
$\mathcal{G}^{*}$ which are adjacent to both $B_{m}$ and its complement.

We prove Theorem 1.3 in steps. In the first two steps, we reduce to the case
where $\mathcal{G}^{*}$ is a graph (not a multigraph) and there are few
nonzeros on the boundary of $B_{n}$. The third step is an argument by
contradiction: if there were a nonzero vertex in $B_{n/2}$, then by Lemma 2.1
this would force many nonzeros on the boundary of $B_{n}$.

Step 1: Reduction to case when $\mathcal{G}^{*}$ is a graph.
First, we assume without loss of generality that $\mathcal{G}$ is 2-edge
connected, because any harmonic function is constant on finite 2-edge
connected components of $\mathcal{G}$.

Next, if $\mathcal{G}^{*}$ had multiple edges, then there would exist a finite
connected component $K$ of $\mathcal{G}$ which is 3-edge connected and for
which there are only two edges, $e_{1}$ and $e_{2}$, which connect $K$ to
$\mathcal{G}\setminus K$. Let $\mathcal{G}^{\prime}$ be the graph
$\mathcal{G}$, with $K$ replaced by a single edge connecting the endpoints of
$e_{1}$ and $e_{2}$ in $\mathcal{G}\setminus K$. The weight of this new edge
is given by the effective conductance of $K$ between the endpoints. Then any
harmonic function on $\mathcal{G}$ is also harmonic when restricted to
$\mathcal{G}^{\prime}$. Furthermore, since $\mathcal{G}$ is periodic, we can
repeat this process for each finite 3-edge connected component of
$\mathcal{G}$ and only remove a constant fraction of vertices from
$\mathcal{G}$. Modifying the $\varepsilon_{0}$ in Theorem 1.3 appropriately
according to this fraction, we see that proving the theorem for
$\mathcal{G}^{\prime}$ implies the result for $\mathcal{G}$, and therefore we
assume that $\mathcal{G}^{*}$ is a graph without loss of generality.

Step 2: Reduction to few non-zeros on the boundary.
By the pigeonhole principle and the assumption that $f=0$ on a
$(1-\varepsilon)$ portion of $B_{2n}$, we may assume that there is some
$\partial B_{m}$ for $m\in[1.5n,2n]$ such the number of vertices for which
$f(v)\neq 0$ and which are adjacent to a face in $\partial B_{m}$ is at most
$C\varepsilon n$.

Step 3: Bounding the number of zeros.
Let $m\in[1.5n,2n]$ be given by Step 2. Assume for contradiction that there is
some $x_{0}\in B_{n}$ with $f(x_{0})\neq 0$. Let $N$ be the set of faces of
$\mathcal{G}[B_{m}]$ which are adjacent to at least one vertex where $f$ is
nonzero. Then the maximal connected component $K\subseteq N$ in
$\mathcal{G}^{*}$ which contains every face adjacent to $x_{0}$ also contains,
by the maximum principle, a face in $\partial B_{m}$. Let
$\gamma:=\\{v_{0},v_{1},\dots,v_{k}=v_{0}\\}$ be a cycle in $\mathcal{G}$
around the boundary of $K\cup\\{\text{vertices in finite connected components
of $\mathcal{G}^{*}\setminus K$}\\}$.

Let $D$ be the unique finite connected component of
$\mathcal{G}\setminus\gamma$. First, we note that $D$ contains $x_{0}\in
B_{n}$ and a vertex adjacent to $\partial B_{m}$, so it has diameter at least
$n/2$ and therefore its boundary, $\gamma$, has length at least $n/2$. Our
goal is to find suitable sets $Z,P,M$ to apply Lemma 2.1. Let
$Z:=\gamma\setminus\\{\mbox{vertices adjacent to $\partial B_{m}$}\\}$ and let
$P:=\\{x\in\gamma\cup D\mid f(x)>0\\}$ and $M:=\\{x\in\gamma\cup D\mid
f(x)<0\\}$.

By maximality, $f(z)=0$ for every vertex $z\in Z$. It is clear that $Z,P,M$
are disjoint. Furthermore, the first two hypotheses of Lemma 2.1 are clearly
satisfied. The fourth hypothesis of Lemma 2.1 is satisfied by the maximum
principle. It remains to check the third hypothesis: fix any $z\in Z$. Since
$z$ is adjacent to a face $F\in K$, there is some vertex $w$ adjacent to $F$
on which $f(w)\neq 0$. Choose $w$ to be the vertex closest to $z$ with this
property, and let $\beta=\\{z=w_{0},w_{1},\dots,w_{\ell}\\}$ be a shortest
path such that $w_{\ell}$ is adjacent to $w$. By minimality of $\beta$, we
have $f(w_{\ell})=0$ and therefore $w_{\ell}$ is also adjacent to some vertex
$y$ with $\operatorname{\mathop{\bf sgn}}f(y)=-\operatorname{\mathop{\bf
sgn}}f(w)$. Then we set $p(z)$ to be the vertex in $\\{w,y\\}$ on which $f$ is
positive, and $m(z)$ to be the other vertex in $\\{w,y\\}$. Since $f$ vanishes
on $\beta$, we see that the third hypothesis of Lemma 2.1 is satisfied.

Applying Lemma 2.1, we conclude that $|Z|\leq\alpha_{\mathcal{F}}|\gamma|$.
Hence, at least $(1-\alpha_{\mathcal{F}})$ vertices in $\gamma$ are adjacent
to a face in $\partial B_{m}$. Each of these faces must be adjacent to a
vertex for which $f$ is nonzero. However, since $|\gamma|\geq n/2$, this
contradicts Step 2 for $\varepsilon_{0}$ sufficiently small, completing the
proof.∎

######  Remark 3.1.

The argument shows that the density hypothesis in Theorem 1.3 may be replaced,
as in Step 2, by a bound on the number of non-zero vertices adjacent to
$\partial B_{2n}$. In particular, this shows that if there are infinitely many
contours surrounding the origin for which the harmonic function has a high
density of zeros, then the function must be zero identically.

##  4\. Exponential upper bound

For the proof of Theorem 1.2, we have the additional hypothesis of uniformly
ellipticity, $0<\lambda<\mathbf{a}<\Lambda$. This allows us to exploit the
following observation: if $f(x)$ is small and there is a neighbor $y\sim x$
for which $f(y)$ has large magnitude, then there is a different neighbor
$z\sim x$ with large magnitude of the opposite sign. Equipped with this
observation we argue along similar lines as the proof of Theorem 1.3.

Step 1: An exponential bound.
In this step we prove that there exists $\varepsilon_{1}\in(0,1)$ such that if
$\varepsilon\leq\varepsilon_{1}$

(2) $\max_{B_{n}}|f|\leq C\alpha^{n}\,,$

for constant exponent $\alpha$ depending only on $\mathcal{F}$ and the
ellipticity ratio $\Theta:=\Lambda/\lambda$.

By the pigeonhole principle, for each $\delta\in(0,1)$, there is a
sufficiently large $K(\delta)$ and an integer $A\in[1,K^{n}]$ for which
$|\\{v\in\mathcal{G}[B_{2n}]:|A|<|f(v)|<2\Theta\mbox{(max degree in
$\mathcal{G}$)}A\\}|<\delta n$. We may then repeat the proof of Theorem 1.3,
treating $\\{v\in\mathcal{G}[B_{2n}]\mid|f(v)|<|A|\\}$ as the zero set. The
only difference is that there is a $\delta$-fraction of “zeros” which do not
satisfy condition (3) of Lemma 2.1, but since $\delta$ can be made arbitrarily
small, we may discard those points from $Z$ before applying Lemma 2.1 and we
have (2).

Step 2: Improve the exponent by covering.
Following the argument at the end of the proof of [BLMS22, Theorem A’], we
upgrade the exponential bound from Step 1 to a bound involving $\varepsilon$.
Let $\delta=C^{-1}\varepsilon_{1}^{-1/2}\varepsilon^{1/2}$ and cover $B_{n}$
by $\delta^{2}$ balls of radius $\delta n$ contained in $B_{2n}$, decreasing
$\varepsilon_{0}$ if necessary. Observe that for each such ball $B_{\delta
n}(z_{i})$, we have $|v\in B_{\delta
n}(z_{i})\mid|f(v)|>1|<C\varepsilon\delta^{-2}|B_{\delta
n}|=\varepsilon_{1}|B_{\delta n}|$ and hence, by applying Step 1 to each such
ball, we have
$\max_{B_{n}}|f|\leq\alpha^{(C^{-1}\varepsilon_{1}^{-1/2})\varepsilon^{1/2}n}$
which completes the proof. ∎

##  5\. A non-planar counterexample on the square lattice

We present a collection of periodic conductances with crossing edges on
$\operatorname{\mathbb{Z}}^{2}$ for which Theorem 1.3 fails. For each vertex
$x$ such that $x_{1}+x_{2}$ is even, assign (undirected) conductances as
follows

$\mathbf{a}(x,x-e_{2})\,,\,\mathbf{a}(x,x-e_{1}):=A_{1}\qquad\mathbf{a}(x,x+e_{2})\,,\,\mathbf{a}(x,x+e_{1}):=A_{2}$
$\mathbf{a}(x,x+(2e_{1},2e_{2}))\,,\,\mathbf{a}(x,x-(2e_{1},2e_{2})):=A_{3}\qquad\mathbf{a}(x,x+(e_{1},e_{2}))\,,\,\mathbf{a}(x,x-(e_{1},e_{2})):=A_{4}\,,$

see Figure 4. Denote this graph by
$(\operatorname{\mathbb{Z}}^{2},\mathcal{E}(A_{1},A_{2},A_{3},A_{4}))$.

Figure 4. Conductances $A_{1},A_{2},A_{3},A_{4}$ are dashed violet lines,
orange solid lines, red dash dotted lines, and blue dotted lines respectively.

######  Theorem 5.1.

For each choice of positive $A_{1}\neq A_{2}$ and
$A_{3}>\frac{2A_{1}^{2}A_{2}^{2}}{{(A_{1}-A_{2})}^{2}(A_{1}+A_{2})}$ there is
a choice of $A_{4}>0$ for which there is a harmonic function on
$(\operatorname{\mathbb{Z}}^{2},\mathcal{E}(A_{1},A_{2},A_{3},A_{4}))$
supported on the diagonal line $\\{x_{1}=x_{2}\\}$.

###### Proof.

For the sequence $\\{z_{i}\\}_{i\in\operatorname{\mathbb{Z}}}$ determined by
the equalities $z_{0}=1$ and $A_{1}z_{i}+A_{2}z_{i-1}=0$, a short computation
shows that the function $h(x_{1},x_{2})=1_{\\{x_{1}=x_{2}\\}}z_{x_{1}}$ is
harmonic on
$(\operatorname{\mathbb{Z}}^{2},\mathcal{E}(A_{1},A_{2},A_{3},A_{4}))$ for
some $A_{4}>0$. ∎

##  Appendix A Exponential lower bound

We follow the arguments of [BLMS22] and prove the following exponential lower
bound, which, when combined with Theorem 1.2, implies Theorem 1.1. Let $Q_{N}$
denote the cube centered at 0 of side length $2N$.

######  Theorem A.1 (Theorem (B) in [BLMS22]).

There is some $b>0$ such that the following holds. If $\varepsilon>0$ is
sufficiently small, $N$ is sufficiently large,
$\max_{Q_{\lfloor\sqrt{N}\rfloor}}f\geq 2$, and

$\frac{|\\{|f|\leq 1\\}\cap Q_{K}|}{|Q_{K}\cap\mathcal{V}|}\geq
1-\varepsilon,$

for each $K\in[\sqrt{N},2N]$, then

(3) $\max_{Q_{N}}|f|\geq\exp(bN)\,.$

The proof in [BLMS22] relied on a discrete three-ball inequality and our only
modification is to prove this inequality in the more general setting of a
periodic graph. The argument is effectively a simplified version of that in
[AKS23].

We first approximate a harmonic function on $\mathcal{G}$ by a polynomial with
periodic coefficients.

######  Lemma A.2.

For any $\alpha>0$, there is a constant $c(\alpha)>0$ such that, for every
sufficiently large $R>0$, natural number $m\leq cR$, and $v\in\mathcal{V}$, if
$f$ is discrete harmonic in $Q_{3R}$, then there exists a polynomial $p$ of
degree $m$ such that

(4)
$\|f-p\|_{L^{\infty}(Q_{cR}\cap(v+\mathcal{L}))}\leq\alpha^{m}\|f\|_{L^{\infty}(Q_{3R})}\,.$

###### Proof.

Fix generators $e_{1},e_{2}\in\mathcal{L}$. For $i=1,2$, let $D_{i}$ denote
the forward-difference operator $D_{i}f(x):=f(x+e_{i})-f(x)$. We write
$D:=(D_{1},D_{2})$.

Iterating the discrete Caccioppoli inequality (see, e.g., [BDCKY15,
Proposition 12]) and applying a discrete Moser estimate, [Del97, Proposition
5.3], we obtain

(5) $R\|D^{m}f\|_{L^{\infty}(Q_{R})}\leq
C\|D^{m}f\|_{L^{2}(Q_{2R})}\leq{\left(\frac{Cm}{R}\right)}^{m}\|f\|_{L^{2}(Q_{3R})}\quad\forall
m\leq cR\,.$

Here we use the fact that if $f$ is harmonic then $Df$ is also harmonic. This
is the only place in our argument where $\mathcal{L}$-invariance of
$\mathbf{a}$ is used.

Given $v\in\mathcal{V}$, choose $v_{0}\in v+\mathcal{L}$ to be closest to the
origin, breaking ties arbitrarily. Let
$p\in\operatorname{\mathbb{R}}[x_{1},x_{2}]$ be the unique polynomial of
degree $m$ such that $D^{k}p(v_{0})=D^{k}f(v_{0})$ for all $k\in[0,m]$. For
any $z\in Q_{cR}\cap(v+\mathcal{L})$, integrating $m+1$ times from $v_{0}$ to
$z$ yields

$|f(z)-p(z)|\leq\frac{{\left(cR\right)}^{m+1}}{(m+1)!}\sup_{Q_{cR+C(m+1)}\cap(v+\mathcal{L})}|D^{m+1}f|\,.$

The desired conclusion follows by applying (5) at order $m+1$ and choosing
$c(\alpha)>0$ sufficiently small. ∎

######  Proposition A.3.

There is some $\varepsilon=\varepsilon(\mathcal{G})$ such that, if

$\frac{|\\{|f|\leq 1\\}\cap Q_{N}|}{|Q_{N}\cap\mathcal{V}|}\geq
1-\varepsilon,$

and $|f|\leq M$ on $Q_{4N}$, then

(6) $\max_{Q_{2N}}|f|\leq CM^{1/2}+C\exp(-cN)M\,,$

where $c,C>0$ are constants.

###### Proof.

We closely follow the proof of [BLMS22, Theorem 3.1], making a small
modification to use Lemma A.2 instead of the exact formula for the Poisson
kernel on squares in $\operatorname{\mathbb{Z}}^{2}$.

As in [BLMS22], it suffices to prove the following statement which implies the
desired result by a routine covering argument.

_There is some $\varepsilon>0$ and $k\in\operatorname{\mathbb{N}}$ such that,
if $f$ is discrete harmonic with $|f|\leq M$ on $Q_{kN}$ and $|f|\leq 1$ on at
least $(1-\varepsilon)|Q_{N}\cap\mathcal{V}|$ vertices in $Q_{N}$, then
$|f|\leq C(M^{1/2}+\exp(-cN)M)$ on $Q_{2N}$._

By choosing $\varepsilon$ sufficiently small, it suffices to prove this
statement only for vertices in the translated lattice $v+\mathcal{L}$ for some
fixed $v\in\mathcal{V}$. Fix such a $v$ and choose vectors $e_{1},e_{2}$ that
generate $\mathcal{L}$. Without loss of generality, assume that $e_{1}=(1,0)$
and $e_{2}=(0,1)$. Consider an integer $t\in[-N,N]$ where
$|f(v+se_{1}+te_{2})|\leq 1$ for at least half of integers $s\in[-N,N]$. We
estimate $\sup_{s\in[-2N,2N]}|f(v+se_{1}+te_{2})|$ and then repeat,
propagating the bounds from the horizontal direction to the vertical
direction.

Let $\beta<0$ and $\alpha\in(0,1)$ be constants chosen at the end of the
proof. At each occurrence of these parameters, we will make a note of any
necessary conditions.

We consider two cases, depending on the size of $M$.

  1. (1)

Suppose $M\exp(\beta N)\leq 1$ and choose $\gamma>0$ to be minimal such that
$\gamma N$ is an integer and

$\alpha^{\gamma N}M\leq 1\,.$

By the assumption of this case and minimality of $\gamma$, we conclude that
$\gamma\leq\frac{\beta}{\log\alpha}+\frac{1}{N}$. Let $p$ be the polynomial
given by Lemma A.2 of degree $m=\gamma N$, which satisfies, for $k$
sufficiently large,

$\|f-p\|_{L^{\infty}(Q_{N}\cap(v+\mathcal{L}))}\leq\alpha^{\gamma N}M\,.$

By a discrete version of Remez’s inequality [BLMS22, Corollary 2.2], we deduce

$|p(v+se_{1}+te_{2})|\leq 2{\left(\frac{16N}{(1-\gamma)N}\right)}^{\gamma
N},\quad\forall s\in[-2N,2N]\,.$

Combining the previous three displays, for each $s\in[-2N,2N]$ we get

$|f(v+se_{1}+te_{2})|\leq 2{\left(\frac{16N}{(1-\gamma)N}\right)}^{\gamma
N}+1\leq 3\alpha^{-\gamma N/2}\leq\frac{3}{\alpha}M^{1/2}\,,$

where the second inequality above holds as long as
$\log\frac{16}{1-\gamma}\leq-\frac{1}{2}\log\alpha$ and the third follows by
minimality of $\gamma$. In turn,
$\log\frac{16}{1-\gamma}\leq-\frac{1}{2}\log\alpha$ holds if
$\gamma\leq\frac{3}{4}$ (which holds for $N\geq 4$ when
$\frac{\beta}{\log\alpha}\leq\frac{1}{2}$) and $\log
64\leq-\frac{1}{2}\log\alpha$.

  2. (2)

Otherwise, assume that $\delta:=M\exp(\beta N)>1$. In this case, approximate
$u$ instead by a polynomial of degree $\frac{1}{2}N$, given by Lemma A.2, with
error

$\|f-p\|_{L^{\infty}(Q_{N}\cap(v+\mathcal{L}))}\leq\exp(\beta N)M\,.$

By the assumption of this case and the above inequality, we have
$|p(v+se_{1}+te_{2})|\leq 2\delta$ for at least half of the $s\in[-N,N]$.
Applying [BLMS22, Corollary 2.2] again, we get, for each $s\in[-2N,2N]$,

$|p(v+se_{1}+te_{2})|\leq 2\delta{\left(\frac{32N}{N}\right)}^{N/2}\,.$

Combining the previous two displays, we get, for each $s\in[-2N,2N]$,

$|f(v+se_{1}+te_{2})|\leq{32}^{N/2}2\delta+\exp(\beta N)M\leq C\exp(-cN)M\,,$

where we use the fact that $\beta<-\log(32)/2$.

We observe that the desired constraints are satisfied for $\beta:=-\log 32$
and $\alpha:=2^{-12}$. ∎

###### Proof of Theorem A.1.

Follow the proof of Theorem (B) in [BLMS22], replacing each reference to
Theorem 3.1 (the discrete three-circle theorem) with Proposition A.3, which is
the same statement generalized to periodic planar graphs. ∎

## References

  * [AKS23] Scott Armstrong, Tuomo Kuusi, and Charles Smart.  Large-scale analyticity and unique continuation for periodic elliptic equations.  Comm. Pure Appl. Math., 76(1):73–113, 2023.
  * [BDCKY15] Itai Benjamini, Hugo Duminil-Copin, Gady Kozma, and Ariel Yadin.  Disorder, entropy and harmonic functions.  Ann. Probab., 43(5):2332–2373, 2015.
  * [BK05] Jean Bourgain and Carlos E. Kenig.  On localization in the continuous Anderson-Bernoulli model in higher dimension.  Invent. Math., 161(2):389–426, 2005.
  * [BLMS22] Lev Buhovsky, Alexander Logunov, Eugenia Malinnikova, and Mikhail Sodin.  A discrete harmonic function bounded on a large portion of $\mathbb{Z}^{2}$ is constant.  Duke Math. J., 171(6):1349–1378, 2022.
  * [BRCD23] Ahmed Bou-Rabee, William Cooperman, and Paul Dario.  Rigidity of harmonic functions on the supercritical percolation cluster.  arXiv preprint arXiv:2303.04736, 2023.
  * [Del97] T. Delmotte.  Inégalité de Harnack elliptique sur les graphes.  Colloq. Math., 72(1):19–37, 1997.
  * [DS20] Jian Ding and Charles Smart.  Localization near the edge for the Anderson Bernoulli model on the two dimensional lattice.  Invent. Math., 219(2):467–506, 2020.
  * [LZ22] Linjun Li and Lingfu Zhang.  Anderson-Bernoulli localization on the three-dimensional lattice and discrete unique continuation principle.  Duke Math. J., 171(2):327–415, 2022.
  * [Ser56] James Serrin.  On the Harnack inequality for linear elliptic equations.  J. Analyse Math., 4:292–308, 1955/56.