# Uni-Retriever: Towards Learning The Unified Embedding Based Retriever in
Bing Sponsored Search

Jianjin Zhang${}^{\textbf{{\tiny\char 168}}}$, Zheng
Liu${}^{\textbf{{\tiny\char 168}}}$, Weihao Han${}^{\textbf{{\tiny\char
168}}}$, Shitao Xiao${}^{\textbf{{\tiny\char 171}}}$, Ruicheng
Zheng${}^{\textbf{{\tiny\char 168}}}$, Yingxia Shao${}^{\textbf{{\tiny\char
171}}}$, Hao Sun${}^{\textbf{{\tiny\char 168}}}$, Hanqing
Zhu${}^{\textbf{{\tiny\char 168}}}$, Premkumar
Srinivasan${}^{\textbf{{\tiny\char 168}}}$, Denvy Deng${}^{\textbf{{\tiny\char
168}}}$, Qi Zhang${}^{\textbf{{\tiny\char 168}}}$, Xing
Xie${}^{\textbf{{\tiny\char 168}}}$
♣: Microsoft WebXT and Microsoft Research Asia
♠: Beijing University of Posts and Telecommunications
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Embedding based retrieval (EBR) is a fundamental building block in many web
applications. However, EBR in sponsored search is distinguished from other
generic scenarios and technically challenging due to the need of serving
multiple retrieval purposes: firstly, it has to retrieve high-relevance ads,
which may exactly serve user’s search intent; secondly, it needs to retrieve
high-CTR ads so as to maximize the overall user clicks. In this paper, we
present a novel representation learning framework Uni-Retriever developed for
Bing Search, which unifies two different training modes knowledge distillation
and contrastive learning to realize both required objectives. On one hand, the
capability of making high-relevance retrieval is established by distilling
knowledge from the “relevance teacher model”. On the other hand, the
capability of making high-CTR retrieval is optimized by learning to
discriminate user’s clicked ads from the entire corpus. The two training modes
are jointly performed as a multi-objective learning process, such that the ads
of high relevance and CTR can be favored by the generated embeddings. Besides
the learning strategy, we also elaborate our solution for EBR serving pipeline
built upon the substantially optimized DiskANN, where massive-scale EBR can be
performed with competitive time and memory efficiency, and accomplished in
high-quality. We make comprehensive offline and online experiments to evaluate
the proposed techniques, whose findings may provide useful insights for the
future development of EBR systems. Uni-Retriever has been mainstreamed as the
major retrieval path in Bing’s production thanks to the notable improvements
on the representation and EBR serving quality.

Sponsored Search, Embedding Based Retrieval, Knowledge Distillation,
Contrastive Learning, Representation Learning

##  1\. Introduction

Embedding based retrieval (EBR) is highly emphasized in recent years (Kim,
2014; Karpukhin et al., 2020; Xiong et al., 2021; Huang et al., 2020; Liu et
al., 2021b). In EBR system, queries and answers are represented as latent
vectors. The semantic relationship between query and answer is reflected by
their embedding similarity; as such, the desirable answers to a query can be
efficiently retrieved on top of approximate nearest neighbour search (ANN)
(Johnson et al., 2019). The EBR system is typically learned via contrastive
learning (Karpukhin et al., 2020; Xiong et al., 2021): given the labeled data,
the representation model is learned to discriminate the ground-truth answers
to each query from the entire ads corpus. Thanks to the recent progress of
deep neural networks, especially the pretrained language models (Devlin et
al., 2018), the accuracy of EBR has been substantially improved, making it a
critical recall path in today’s web applications, such as online advertising,
search engines, and recommender systems.

###  1.1. EBR in Sponsored Search

Sponsored Search is the major source of income for search engines and online
shopping platforms. Given a query from user, the system is expected to
retrieve the ads which are not only closely related to user’s search intent,
but also associated with high CTR in order to maximize the revenue of
platform. As a result, EBR in sponsored search is distinguished from EBR in
other generic applications, e.g., web search and question answering, due to
the need of satisfying multiple retrieval purposes. In this place, a toy
example is introduced for better illustration of the above scenario.

###### Example 1.0.

Suppose the following query is specified by the user: “Secondhand Chevy” (shown as Figure 1). Meanwhile, three different ads are presented for sponsored search. Ad-1. “Used Chevrolet for sale in Los Angeles”. Although the first ad is highly relevant with user’s query, it suffers from low CTR probably due to the missing of merchant name. Ad-2 “Used SUV & Pickup for Sale | CarMax”. The second ad is associated with high CTR given its popularity to general crowd; however, it is weakly related with the user’s specified query. Ad-3. “Quality Used Chevrolet for Sale | CarMax”. The third ad is of both high relevance to the user’s query and high CTR thanks to the fascinating quality of the provided service. Therefore, only Ad-3 will be retrieved for the query given that both high-relevance and high-CTR conditions are satisfied by it.

The training of the embedding model for sponsored search is non-trivial.
Particularly, the typical training algorithms, which mainly rely on
contrastive learning, call for a huge collection of queries paired with
ground-truth answers. However, such a requirement will be impractical in
sponsored search considering that it is almost infeasible to manually label
the “high-relevance & high-CTR ads” for a great deal of queries. As a result,
most of the previous works tackle this problem with ad-hoc solutions, e.g.,
the detection of bad cases in (Fan et al., 2019). In this work, we develop our
unified representation learning framework in Bing Sponsored Search, called
Uni-Retriever (the Unified Embedding Based Retriever). The proposed framework
jointly leverages two different training modes: knowledge distillation and
contrastive learning, such that the desired embedding model can be effectively
trained based on user’s click data (which is abundant) and a pretrained
relevance teacher model capable of predicting the semantic closeness.

$\bullet$ Knowledge Distillation from Relevance Teacher. An off-the-shelf
teacher model is leveraged for the prediction of the semantic closeness
between the query and ad. Although many public sentence representation models,
like SBERT (Reimers and Gurevych, 2019) and DSSM (Kim, 2014) may play such a
role, we pretrain our in-house relevance teacher model for more precise
prediction using a moderate amount of manually labeled query-ad relevance
data. While training Uni-Retriever, the teacher’s relevance predictions are
required to be preserved by the generated embeddings, i.e., a pair of
semantic-close query and ad are expected to result in a large embedding
similarity.

$\bullet$ Contrastive Learning with Enhanced Negative Sampling. Uni-Retriever
is learned to retrieve high-CTR ads through contrastive learning.
Particularly, it extracts a massive scale of users’ queries and ads clicks
from the production log, and learns to discriminate the ground-truth to each
query (i.e., the clicked ad) from the entire ads corpus. Recent studies
indicate that the quality of contrastive learning is largely affected by both
scale and hardness of the negative samples (Luan et al., 2021; Qu et al.,
2021). In Uni-Retriever, we leverage the following two techniques for the
enhancement of negative sampling: 1) the Cross-Device negative Sampling (CDS),
which significantly augments the scale of negative samples by sharing the
cross-device encoding results with gradient compensation; 2) the Relevance-
filtered ANN negative Sampling (RAS), which increases the hardness of negative
samples by selecting those low-relevance ads from the neighbourhood of query
embedding.

Figure 1. Working Example. Ad-3, which is of both high CTR and high relevance
with the user’s specified query, is expected to be retrieved from ads corpus
for sponsored search.

The knowledge distillation and the contrastive learning are linearly combined
as a multi-objective learning process, where the generated embeddings are
learned to favor both high-relevance ads and user’s clicked ads. By doing so,
both required conditions in sponsored search can be satisfied by the resulted
embedding model.

###  1.2. Serving EBR At Scale

Aside from the learning of embedding model, another technical challenge, which
is more generic in real-world applications, is how to serve the EBR system at
scale. Particularly, it is extremely challenging to work with billion-scale
embeddings on the computation platforms, meanwhile supporting realtime and
high-quality ANN search towards these embeddings. The EBR system is required
to trade-off of three factors: 1) time consumption, 2) memory usage, and 3)
recall rate. The existing approaches intensively exploits two streams of
techniques: 1) the proximity-graph based algorithms, e.g., HNSW, NSG (Malkov
and Yashunin, 2018; Fu et al., 2017), and the vector-quantization based
algorithms, e.g., IVFADC, IVFOADC+G+P (Jégou et al., 2011; Baranchuk et al.,
2018). The former one is favorable to time efficiency and recall rate, but is
likely to result in high memory usage; in contrast, the latter one is memory
efficient, but can be relatively limited in time efficiency and recall rate.
In this paper, we showcase our scalable and high-quality EBR serving pipeline
built upon the substantially enhanced DiskANN (Subramanya et al., 2019).

$\bullet$ DiskANN. We take advantage of DiskANN for its competitive time and
memory efficiency. It compresses the ads embeddings via product quantization
and leverages Vanama graph (a close variant of NSG) for the quick routing to
the approximate nearest neighbours. The storage of the index follows a
hierarchical architecture: the tier-1 storage is on RAM, which merely keeps
the compressed embeddings; the tier-2 storage is on SSD, which maintains the
posting lists recording the dense embeddings and graph connections. The ANN
process is divided accordingly: with coarse-grained candidates searched based
on the compressed embeddings, and fine-grained result post-verified by the
full-precision embeddings.

$\bullet$ Optimization. The direct usage of DiskANN, though scalable, are
prone to severe loss of retrieval quality because of 1) the lossy compression
of PQ and 2) the inferior post-verification effect from the original dense
embeddings. To mitigate these problems, the following optimization treatments
are performed w.r.t. the adopted ANN index. Firstly, the quantization module
is jointly learned with the embedding model in order to maximize the retrieval
performance resulted from the compressed embeddings. Thanks to the adjusted
objective and the end-to-end optimization, the first-stage retrieval quality
(i.e., the coarse-grained candidates) can be significantly improved compared
with the conventional ad-hoc compression methods, like PQ (Jegou et al., 2010)
and OPQ (Ge et al., 2013). Secondly, the original dense embeddings are further
adapted w.r.t. the re-ranking scores for the coarse-grained candidates, such
that the top-ranked ads can be better discriminated from the first-stage
retrieval result.

The proposed techniques have been integrated as Uni-Retriever step-by-step and
mainstreamed into Bing’s production for the past period. In this paper,
comprehensive offline experiments and online A/B tests are provided for the
analysis of the proposed techniques. To the best of our knowledge, this is the
first work which elaborates the practice of the latest representation learning
algorithms in sponsored search, together with the systematic study of how to
best leverage the ANN index for massive-scalable EBR. Corresponding technical
discussions and experimental studies may provide useful insight for both
researchers and practitioners in the community. Finally, contributions of this
paper are summarized as follows.

  * •

We introduce our unified representation learning framework: Uni-Retriever,
developed for Bing sponsored search. The proposed framework integrates
knowledge distillation and contrastive learning, which enables high-relevance
and high-CTR ads to be retrieved for user’s query.

  * •

We elaborate our EBR serving pipeline, which inherits the high scalability
from DiskANN, and substantially improves the retrieval quality based on the
optimization processing.

  * •

We perform comprehensive offline and online experiments for the analysis of
Uni-Retriever, whose results verify the effectiveness of our proposed
techniques.

Figure 2. Overview of Uni-Retriever. (1) The query and ad are encoded as
latent embeddings, whose similarity is computed via inner-product; (2) the
semantic closeness (i.e., relevance score) between the query and ad is
computed by the relevance teacher model; (3) the knowledge distillation is
performed to minimize the difference between the query-ad similarity and the
relevance score; (4) the contrastive learning is performed to discriminate the
clicked ad.

##  2\. Uni-Retriever

Uni-Retriever is developed to select ads ($A_{q}$) from the entire corpus
($A$) for user’s input query ($q$), which are not only semantically close to
the query but also likely to be clicked by the user. The above objective is
formulated by the following equation:

(1)
$\mathrm{max.}\sum_{A_{q}}\mathrm{CTR}(q,A_{q}):~{}s.t.~{}\mathrm{REL}(q,a)\geq\varepsilon,~{}\forall
a\in{A_{q}},$

where $\varepsilon$ is the threshold of relevance score. For the ease of
optimization, we make the following relaxation to the above objective:

(2)
$\mathrm{max.}\sum_{A_{q}}\mathrm{CTR}(q,A_{q})+\lambda*\mathrm{REL}(q,a),$

where $\lambda$ is the positive value trading off the importance between CTR
and relevance. In Uni-Retriever, $A_{q}$ is retrieved based on MIPS (Maximum
Inner Product Search). That’s to say, the group of ads with the top-$K$
embedding similarities to the query (measured by inner product) are expected
to be the optimal solution of Eq. 2. Such an embedding model is learned by our
compound representation learning strategy (shown as Figure 2), which unifies
knowledge distillation and contrastive learning.

###  2.1. Knowledge Distillation

Firstly, we expect high-relevance ads to be favored by the learned embeddings.
To this end, we propose to learn query and ad embedding by distilling
knowledge from the relevance teacher model.

$\bullet$ Relevance Teacher Model. The relevance teacher model is a BERT based
binary classification model (denoted as $\mathrm{BERT}^{Tch}$), which predicts
whether the given query and ad are semantically close (e.g., label “0”/“1”
indicate the ad to be non-relevant or relevant with the input query). Unlike
the embedding model which adopts the bi-encoder architecture, the relevance
teacher model follows the cross-encoder, which is more expressive and capable
of making more precise classification. Without loss of generality, the
computation of relevance score is given as:

(3)
$\text{Rel}_{q,a}=\sigma\big{(}W^{T}\mathrm{BERT}^{Tch}([\text{CLS},Query,\text{SEP},Ad])\big{)},$

where $[\text{CLS},Query,\text{SEP},Ad]$ means the concatenation of query and
ad, with CLS and SEP token padded; we take the final layer’s hidden state
corresponding to CLS as the output of BERT; $W$ ($\in\mathrm{R}^{d\times 1}$)
is the linear projection which reduces the output vector to a real value; and
$\sigma(\cdot)$ is the sigmoid activation. The relevance teacher model is
pretrained based on manually labeled data from human experts.

$\bullet$ Knowledge Distillation. Based on the well-trained relevance teacher
model, Uni-Retriever can be learned by knowledge distillation (Hinton et al.,
2015) (in this place, the same backbone model is shared by the query encoder
and ad encoder, denoted as $\mathrm{BERT}^{Uni}$). Particularly, the relevance
teacher model is used to generate the relevance score $\text{Rel}_{q,a}$ for
the input query $q$ and ad $a$. Then, $\mathrm{BERT}^{Uni}$ is learned to
imitate the teacher’s prediction with the inner product of the query and ad
embedding, where the following loss is minimized:

(4)
$\mathrm{min.}\sum_{q}\sum_{a}\big{\|}\text{Rel}_{q,a}-\langle\mathrm{BERT}^{Uni}(q),\mathrm{BERT}^{Uni}(a)\rangle\big{\|}.$

In this place, $\langle\cdot\rangle$ indicates the inner product operator.
With the optimization of the above problem, the high-relevance ads to the
query can be favored by high inner products, therefore enabling them to be
retrieved via MIPS.

###  2.2. Constrastive Learning

We expect the high-CTR ads to be promoted by the learned embeddings as well.
To this end, the contrastive learning is performed, where the embedding model
is learned to discriminate the ground-truth (i.e., the clicked ad) for each
query from the rest of the ads within the corpus. In this place, the following
InfoNCE loss is formulated as our learning objective:

(5)
$\mathrm{max}.\sum_{q}\frac{\exp(\langle\mathrm{BERT}^{Uni}(q),\mathrm{BERT}^{Uni}(a_{q}^{+})\rangle)}{\sum_{a^{-}\in
N_{q}}\exp(\langle\mathrm{BERT}^{Uni}(q),\mathrm{BERT}^{Uni}(a^{-})\rangle)},$

where $a_{q}^{+}$ denotes the ground-truth, and $N_{q}$ are the negative
samples to the query. The contrastive learning’s performance is highly
affected by two factors: 1) the scale of negative samples (Chen et al., 2020;
He et al., 2020), and 2) the hardness of the negative samples (Xiong et al.,
2021; Luan et al., 2020). In our project, the following strategies are adopted
for the enhancement of scale and hardness of the negative samples.

Figure 3. Cross-device negative sampling with gradient compensation.
(Blue/Green/Red: query embedding/ground-truth embedding/hard-negative
embedding. Solid rectangles: locally encoded embeddings, which are
differentiable; shadowed rectangles: the broadcasted embeddings from other
GPUs, which are non-differentiable).

####  2.2.1. Cross-device Negative Sampling

The in-batch negative sampling is a widely used strategy which introduces a
large number of negative samples in a cost-free manner. Particularly, one
query $q$ will use the ground-truth ads of other queries within the same mini-
batch $B_{q}$ as its negative samples:
$N_{q}=\\{a^{+}_{q^{\prime}\neq{q}}\\}_{B_{q}}$; as a result, each query may
get as many as $|B_{q}|-1$ negative samples. The cross-device negative
sampling is a further augmentation of the conventional in-batch negative
sampling (Xiao et al., 2021b; Qu et al., 2021) when the model is trained on
multiple distributed GPU devices (where the entire collection of mini-batches
is denoted $B=\\{B_{1},...,B_{N}\\}$): the ground-truth ads from other
queries, not only within the same device ($B_{q}$) but also from the whole
devices ($B$), will be used as the negative samples of query $q$; in other
words, $N_{q}=\\{a^{+}_{q^{\prime}\neq{q}}\\}_{B}$. Such an operation will
enlarge the negative sample size by $N$-fold without introducing additional
computation cost (e.g., $8\times$ larger than in-batch negative sampling when
8 GPUs are used for distributed training).

It should be noted that the naive cross-batch negative sampling is problematic
and will result in limited performance (Xiao et al., 2021b); this is because
the embeddings from other devices are detached from the computation graph,
thus non-differentiable. In this place, we leverage the following gradient
compensation operation, with which all cross-device embeddings are make
“virtually differentiable” so that the model to be correctly optimized (shown
as Figure 3). Firstly, the entire encoding output, i.e., queries embeddings
($\\{\mathrm{BERT}^{Uni}(q)\\}_{B}$) and ads embeddings
($\\{\mathrm{BERT}^{Uni}(a)\\}_{B}$), will be broadcasted over all the devices
($B$). Secondly, for each of the devices $B_{i}$, the InfoNCE loss is computed
for all the queries (i.e., not only the queries encoded on $B_{i}$, but also
those broadcasted queries from other devices), with all ads embeddings (both
locally encoded and globally broadcasted) taken as the negative samples.
Finally, the InfoNCE losses are back propagated from all the devices and
reduced for the update of the model. It is straightforward that the above
processing is equivalent By doing so, the partial gradients from the rest of
the GPUs will compensate for the non-differentiable ads embeddings on one GPU.
Therefore, the InfoNCE losses generated on different devices will correctly
update the model parameters where the related queries and ads embeddings are
encoded.

####  2.2.2. Relevance Filtered Hard Negatives

. In addition to the cross-device negative samples, hard negatives are also
introduced for each query. Compared with other heuristically acquired hard
negatives, the ANN based hard negatives are proved to be much more useful in
contrastive learning (Gillick et al., 2019; Xiong et al., 2020; Qu et al.,
2021). Particularly, for each query $q$, the ads within $q$’s neighbourhood
are sampled as the hard negatives,
$a:\mathrm{BERT}^{Uni}(a)\in\text{ANN}(\mathrm{BERT}^{Uni}(q))$. The
conventional ANN hard negatives are randomly sampled from the $q$’s
neighbourhood. In our scenario, we expect high-relevance ads to be promoted;
therefore, we propose to filter the sampling by relevance score: the
neighbouring ads (e.g., the Top-$200$ nearest neighbours) are firstly ranked
by their relevance scores; then, the top ranked ads (e.g., Top-1$\sim$K) are
removed; finally, the sampling is performed within the remaining ads (e.g.,
Top-(K+1)$\sim$200). With this operation, we may select those hard yet low-
relevance ads as our negatives, which contributes to the representation
quality. We empirically find that sampling no more than 4 ANN hard negatives
from the filtered neighbours will be sufficient for the best recall
performance; further increasing of the ANN hard negatives leads to extra
training cost but shows no more improvement. The hard negatives of one query
will also be shared with other queries, which may further augment the scale of
negative samples.

###  2.3. Disentangle and Multi-objective Learning

The embeddings are disentangled w.r.t. the relevance and CTR objective for
better empirical performances. Particularly, instead of directly using the
output of $\mathrm{BERT}^{uni}$, different pooling heads are used for the two
objectives. While optimizing the relevance objective in knowledge
distillation, the output embedding becomes
$W_{\text{rel}}\mathrm{BERT}^{uni}(\cdot)$; and for the CTR objective in
contrastive learning, the output embedding is
$W_{\text{ctr}}\mathrm{BERT}^{uni}(\cdot)$. (Note that the encoding backbone
$\mathrm{BERT}^{uni}$ remain shared for the two objectives.)

Uni-Retriever is jointly trained with knowledge distillation and contrastive
learning. Given a mini-batch of triplets: {query: $q$, positive ad:
$a^{+}_{q}$, hard-negative ad: $a^{-}_{q}$} (the algorithm remains the same
when working with more than one hard negatives), Uni-Retriever will represent
them as their CTR and relevance embeddings, respectively; and compute their
inner-product similarities for CTR and relevance. Then, the relevance teacher
model will be used to predict the relevance scores between the input queries
and ads, based on which the knowledge distillation loss can be computed. Note
that the relevance teacher model is an cross-encoder, whose encoding cost will
be formidable when all input ads need to processed. Therefore, the knowledge
distillation will only be performed w.r.t. the clicked ads for the sake of
high cost-efficiency. Meanwhile, the contrastive loss will also be computed,
where $N_{q}$ will be composed of the hard-negative of $q$ and the cross-
device negatives. Both losses will be added up and back-propagated to update
the shared encoding backbone $\mathrm{BERT}^{Uni}$ and the individual pooling
heads: $W_{\text{rel}}$, $W_{\text{ctr}}$. Both pooling heads are $d\times d$;
and the two output embeddings $W_{\text{rel}}\mathrm{BERT}^{uni}(\cdot)$ and
$W_{\text{ctr}}\mathrm{BERT}^{uni}(\cdot)$ will be normalized and added up as
a single vector for EBR.

##  3\. EBR Serving Pipeline

In Bing Sponsored Search, Uni-Retriever needs to serve billion-scale of ads
from different advertisers. Conventional solutions, such as HNSW, NSG, IVFPQ,
will be limited by either the huge memory cost or severe loss of retrieval
quality. To confront this challenge, we leverage DiskANN (Subramanya et al.,
2019) as our ANN index, where the proximity graph and product quantization are
combined for competitive time and memory efficiency. We further introduce a
couple of optimization processing w.r.t. the index: MoPQ (Xiao et al., 2021b)
and Re-ranking oriented adaptation, which substantially improve the retrieval
quality for the first-stage retrieval and post-verification.

###  3.1. DiskANN

The ads embeddings are organized by Vamana graph (Subramanya et al., 2019), a
close variant of NSG (Fu et al., 2017) with parameterized RNG condition for
better connectivity of the graph nodes. Based on such a component, the input
query can be routed to its nearest ads with high time efficiency. Given that
the ads embeddings and their graph connections are too large to fit into
memory, the following hierarchical storage architecture is adopted.

$\bullet$ Tier-One Storage. The tier-one storage is hosted in RAM. To
accommodate the entire corpus, the ads embeddings are compressed based on
product quantization (more effective solution to be discussed in the next
part). The PQ compressed embeddings can be one or two magnitudes lighter than
the original dense embeddings; therefore, billion-scale of ads can be hosted
in the main memory with tens of GB RAM usage.

$\bullet$ Tier-Two Storage. The tier-two storage is hosted in SSD for the
posting lists, where each entry keeps the following three information: the ID
of each ad (int32/64), the full-precision dense embedding of each ad (d-dim
float32 vector), and the list of IDs for the neighbouring ads on Vamana graph
(int32/64).

$\bullet$ Two-steps ANN Search. The ANN search is performed with two
consecutive steps: coarse-grained search, and fine-grained post-verification.
For coarse-grained search, the input query is routed on Vamana graph to get
its approximate nearest neighbours. Starting from the entry point, it
continues to explore the close yet unvisited neighbours, and add the nearest
candidates to a fix-sized priority queue. The exploration on graph is guided
by the distance computed with the compressed embeddings. Once an graph node is
visited, its neighbours’ IDs will be loaded to RAM for future exploration. The
full-precision dense embeddings of the visited nodes will also be loaded into
RAM. The post-verification is performed once the exploration finishes, where
candidates within the priority queue will be refined based on their dense
embeddings (already loaded in RAM during the exploration, thus avoiding extra
I/O operations). The Top-K nearest ads will be returned as the final result.

Figure 4. Illustration of the two-tier storage. The lightweight PQ compressed
embeddings are stored in RAM. The full-precision dense embeddings and the
graph connections (NID: Neighbour’s ID) are stored in SSD. The compressed
embeddings are used for in-memory routing; once a node is visited, the dense
embeddings and neighbour IDs will be loaded to RAM for post-verification and
the next-round routing. Figure 5. Comparison between (A) the conventional tri-
stage EBR and (B) the optimized bi-stage EBR. The re-ranking operation is
omitted in (B) as it is virtually moved ahead to the post-verification step
thanks to the re-rank oriented adaptation.

###  3.2. Optimization Processing

The conventional DiskANN-based EBR goes through the Tri-stage workflow shown
as Figure 5 (A). Firstly, the query searches for its coarse-grained candidate
ads based on the Vamana graph and the compressed ads embeddings generated by
ad-hoc compression methods, e.g., PQ or OPQ. Secondly, the coarse-grained
candidates are post verified by the full-precision ads embeddings loaded from
SSD to RAM. Finally, the fine-grained candidates are further re-ranked in
order to generate the final retrieval output. Notice that the re-ranking
function111The concrete formula of $\Psi$ is kept confidential due to business
concern. is introduced for the optimal business outcome, which combines three
factors: CTR and Relevance (Rel) for the query and ad, and Bidding price of
the ad (Bid):

(6)
$\text{Rank}_{q,a}=\Psi(\text{CTR}_{q,a},\text{Rel}_{q,a},\text{Bid}_{a}).$

In our system, we optimize the conventional tri-stage workflow with the
following adaptations: 1) leveraging the Matching oriented Product
Quantization (MoPQ) for high-quality first-stage retrieval, and 2) the re-
ranking oriented adaptation of the dense embeddings for more effective post
verification.

####  3.2.1. MoPQ

The typical quantization methods used by ANN index, e.g., PQ (Jegou et al.,
2010; Jégou et al., 2011; Subramanya et al., 2019), OPQ (Ge et al., 2013),
ScaNN (Guo et al., 2020), are learned to minimize the reconstruction loss
between the original dense embeddings and the PQ compressed embeddings.
However, the reduction of reconstruction loss does not necessarily lead to the
improvement of retrieval performance (as proved by (Xiao et al., 2021b)),
which will severely limit the retrieval quality under large compression
ratios. Our system leverages MoPQ (Xiao et al., 2021b), the state-of-the-art
product quantization where the compressed embeddings are learned to optimize
the retrieval performance: for each ad embedding $a$, the compressed embedding
$\hat{a}$ is generated based on codebooks $\mathbf{C}$ ($M\times P$):

(7)
$\hat{a}=\mathrm{concat}([c_{1},...,c_{M}]):~{}c_{i}=\mathrm{argmin}_{j=1...P}(\|a_{i}-C_{i}^{j}\|),$

where $a_{i}$ is the $i$-th segment of ${a}$. The straight through estimator
is used for the codeword selection, which maintains the computation
differentiable. The compressed ads embeddings are learned together with the
original dense embeddings, following the same objectives as Eq. 4 and 5.
Thanks to the adjusted objective and the collaboration between the embedding
model and codebooks, the first-stage retrieval performance can be
substantially enhanced by the compressed embeddings.

####  3.2.2. Re-ranking oriented posting list

The original dense embeddings are learned to retrieve high-relevance and high-
CTR ads from the entire corpus. Therefore, they are inferior for the ranking
purpose considering that 1) the re-ranking function is different from the
retrieval objective, 2) the re-ranking emphasizes the local discrimination of
the candidates from the first-stage retrieval, rather than the global
discrimination of the ads within the entire corpus. To mitigate the problem,
we further adapt Uni-Retriever for better post-verification by distilling
knowledge from the re-ranking function, where the following loss is minimized:

(8)
$\mathrm{min.}\sum_{q}\sum_{\hat{A}_{q}}\big{\|}\text{Rank}_{q,a}-\langle\mathrm{BERT}^{rank}(q),\mathrm{BERT}^{rank}(a)\rangle\big{\|}.$

In this place, $\mathrm{BERT}^{rank}$ is the BERT model adapted from the
original $\mathrm{BERT}^{uni}$, $\hat{A}_{q}$ are the sampled ads from the
first stage retrieval result, $\text{Rank}_{q,a}$ is the ranking score
predicted in Eq. 6.

####  3.2.3. Optimized bi-stage retrieval

With the above optimized processing, EBR is simplified into the bi-stage
workflow shown as Figure 5 (B). There are two notable changes compared with
the conventional tri-stage workflow. Firstly, the ads embeddings are
compressed by MoPQ for the enhancement of the first-stage retrieval. Secondly,
the dense embeddings in posting lists are adapted to the re-ranking function;
therefore, the re-ranking operation is omitted as it is virtually moved ahead
to the post-verification step.

---
| Click | Relevance
Method |  Hit@10 |  Hit@100 |  Hit@200 |  Rel@10 |  Rel@100 |  Rel@200
Baseline |  0.2079 |  0.4092 |  0.5810 |  0.7260 |  0.6971 |  0.6675
\+ Multi-obj |  0.2347 |  0.4188 |  0.5841 |  0.7958 |  0.7481 |  0.7348
\+ Disentangle |  0.2441 |  0.5122 |  0.5944 |  0.7998 |  0.7553 |  0.7340
\+ In-batch |  0.2773 |  0.5263 |  0.6004 |  0.7753 |  0.7191 |  0.6999
\+ Cross-device |  0.2887 |  0.5358 |  0.6080 |  0.7833 |  0.7248 |  0.7050
\+ ANN negative |  0.3151 |  0.5750 |  0.6455 |  0.8344 |  0.7757 |  0.7527
\+ Score filter |  0.3156 |  0.5755 |  0.6464 |  0.8406 |  0.7827 |  0.7596
\+ Rank filter |  0.3286 |  0.5896 |  0.6574 |  0.8372 |  0.7755 |  0.7509
Table 1. Evaluation of the retrieval quality: the proposed techniques in Uni-
Retriever are added step-by-step. The integration of all techniques: “+ Score
filter” and “+ Rank filter” (with the utilization of disentangled embeddings,
cross-devices negative sampling, and ANN negatives filtered by relevance-score
/ relevance ranking-order) achieve the best overall performance.

##  4\. Experimental Studies

The offline experiments and online A/B tests are performed to clarify the
following problems: 1) the effectiveness of the proposed representation
learning framework, 2) the effectiveness of the proposed EBR serving pipeline,
3) the impact to online production.

###  4.1. Experiment Settings

####  4.1.1. Data preparations and Training details

A large-scale dataset is curated from Bing’s production for offline
experiments. There are a total of $1.5$ billion query-ad pairs from real-world
users, where $5.7$ million of them are held out for testing. Besides, 20
million ads are included by the ANN index for EBR evaluation. Our text encoder
follows BERT base architecture (Devlin et al., 2018); the output embedding’s
dimension is linearly projected to 64 from 768. We leverage WordPiece as our
tokenizer (Wu et al., 2016), which is trained based on the in-house ads corpus
for better empirical performances (Yao et al., 2021). There are a total of
$50,777$ vocabularies for the well-trained tokenizer. The models are
implemented with python 3.6 and pytorch 1.7.0, and trained on machines with 4*
NVIDIA-V100-32G GPUs and 2* AMD EPYC 7V12 64-Core CPUs.

####  4.1.2. Evaluation metrics

The following two metrics are utilized to evaluate retrieval quality: 1)
Recall of click (Hit@K): which measures whether the clicked ad can be included
by the Top-K retrieval result. 2) Relevance degree (Rel@K): which measures the
average relevance score for the Top-K retrieval result. Note that the
relevance is predicted by the high-precision relevance teacher, whose accuracy
is comparable to human annotator. One more metric is added to evaluate the
retrieval quality after re-ranking: 3) Re-ranking performance (NDCG, MRR),
which measures the post re-ranking quality for the retrieval result w.r.t. the
ground-truth ads selected by the re-ranking function from the entire corpus.

####  4.1.3. Method to compare

The proposed techniques are added to the Baseline one-by-one for the analysis
of their individual impact.

  * •

Baseline, which is the most basic approach purely based on contrastive
learning (i.e., without knowledge distillation from the relevance teacher
model). Besides, each query is sampled with 10 random negatives from the ads
corpus.

  * •

\+ Multi-obj, which improves the “Baseline” by adding the knowledge
distillation task.

  * •

\+ Disentangle, which improves “+ Multi-obj” by having the embeddings
disentangled w.r.t. different objectives in the training stage, and added up
as one vector for EBR serving.

  * •

\+ In-batch, which improves “+ Disentangle” by replacing the random negative
samples with the in-batch negative samples.

  * •

\+ Cross-device, which switches the in-batch negative samples to cross-device
negative samples for the above method.

  * •

\+ ANN negative, which further improves “+ Cross-device” by adding one more
hard negative sample for each query from ANN (randomly selected from the
Top-200 ANN result).

  * •

\+ Score filter, which improves “+ ANN negative” by using hard yet low-
relevance negative samples. Particularly, the ads with relevance scores
(normalized within 0 and 1) below threshold (set as 0.5 by experiment) are
filtered from the Top-200 ANN result for negative sampling.

  * •

\+ Rank filter, which also uses hard yet low-relevance negative samples.
Different from “+ Score filter”, the Top-200 ANN result is ranked by the
relevance teacher in the first place; then, the lower half (101$\sim$200) is
used for negative sampling.

###  4.2. Experiment Analysis

####  4.2.1. Analysis of retrieval quality

The experiment result is shown as Table 1, where the cumulative impact from
our propose techniques are analyzed. The Baseline is based on the simplest
contrastive learning method, which leads to the lowest performance. By adding
our proposed techniques step-by-step, the overall performances can be
gradually improved. Finally, the integration of all proposed techniques, i.e.,
“\+ Score filter” and “\+ Rank filter”, which jointly leverage “the
combination of knowledge distillation and contrastive learning”, “cross-device
negative sampling”, and “ANN hard negatives filtered by relevance score /
relevance ranking-order”, achieve the most competitive performances. More
detailed findings towards each of the techniques are analyzed as follows.

Firstly, with the combination of knowledge distillation (optimizing the
relevance) and contrastive learning (optimizing CTR), both metrics: Click and
Relevance, can be substantially improved by “+ Multi-obj” compared with the
Baseline. This finding indicates 1) the proposed multi-objective learning
framework is effective, 2) the optimization of relevance and CTR objectives
are not contradicted, which can be mutually reinforced to a large extent.
Besides, by generating disentangled embeddings (+ Disentangled) for the two
objectives, the representation quality can be further improved against our
basic multi-objective learning method.

Secondly, by using in-batch negatives (+ In-batch), the click metrics (Hit@K)
can be significantly improved over the previous methods, which rely on 10
randomly sampled negatives. And with cross-device negative sampling (+ Cross-
device), the click metrics can be further improved. Such observations verify
that the increased scale of negative samples is beneficial to the
representation quality. Note that the relevance metrics are not improved,
probably because both methods are simply applied to the contrastive learning.

Thirdly, the overall performances can be continually improved by introducing
the ANN hard negatives (+ ANN negative). Different from the “+ In-batch” and
“+ Cross-device” which augment the scale of negative samples, it is quite
interesting that both click and relevance metrics may benefit from the ANN
hard negatives. Moreover, additional improvements can be achieved with “+
Score filter” and “+ Rank filter”, as the high-relevance ads can be
effectively excluded from being selected as negative samples.

####  4.2.2. Impact from Re-rank oriented Adaptation

The impact from the re-rank oriented adaptation is shown in Table 2. “Base”
stands for the conventional post-verification method, where the original dense
embeddings are utilized; “Base + Re-rank” indicates that the post-verification
result is further re-ranked; “Adapt to Re-rank” is our method, where the post-
verification is made based on dense embeddings adapted to the re-ranking
function. It can be observed that “Adapt to Re-rank” notably outperforms
“Base”. Such a finding is expected, considering that with adaptation to the
re-ranking function, the candidate ads with high re-ranking scores can be
further promoted by the dense embeddings during post-verification. Besides, it
is interesting that “Adapt to Re-rank” also outperforms “Base + Re-rank”. This
is because a great deal of high-quality candidates are left out due to the
conventional post-verification. By comparison, “Adapt to Re-rank” is directly
applied to the coarse-grained search result; in other words, the re-ranking is
virtually moved ahead to process a much larger group of candidates. Thus, it
may better preserve the ads with high re-ranking scores and benefit the online
performance. Note that “Adapt to Re-rank” also contributes to the efficiency,
as the time cost can be saved from the conventional re-ranking step.

---
Method |  NDCG |  MRR
Base |  0.8568 |  0.4140
Base + Re-rank |  0.9033 |  0.4202
Adapt to Re-rank |  0.9096 |  0.4309
Table 2. Impact of re-rank oriented adaptation to the post re-rank retrieval
quality.
---
Method |  Recall@100 |  Recall@500 |  Recall@1000
PQ |  0.3167 |  0.5058 |  0.6000
OPQ |  0.3320 |  0.5172 |  0.6140
ScaNN |  0.4288 |  0.6396 |  0.7218
MoPQ |  0.5004 |  0.6963 |  0.7659
Table 3. First-stage retrieval result (coarse-grained result before post-
verification) from different compression methods.

####  4.2.3. Impact from MoPQ

The comparison between MoPQ and other commonly used PQ compression methods: PQ
(the default option in DiskANN), OPQ, and ScaNN, is shown as Table 3. The size
of codebooks is 64 bit (8 codebooks in total, each one has 256 codewords). We
may observe that MoPQ outperforms the baselines with notable advantages,
verifying that the first-stage retrieval quality can be substantially improved
from it.

####  4.2.4. Online A/B Test

The online A/B tests about Uni-Retriever are reported in Table 4. Since our
techniques are progressively developed, there are three versions shipped to
Bing’s production step-by-step. Particularly, the V1 version is highlighted
for being “Multi-Objective”: the contrastive learning is combined with
knowledge distillation to optimize both CTR and relevance; meanwhile, the
embeddings are disentangled for both objectives. This version achieves +3.27%
RPM growth in A/B test, with a P-Value of 1.82$e-2$ (P-Value below 5$e-2$ is
considered as significant in the production). The V2 version improves the
negative sampling strategy on top of the V1 version (with cross-device
negative sampling, and ANN hard negatives filtered by relevance). Such an
improvement gives rise to +3.06% RPM growth (with V1 version already
mainstreamed in production). Finally, with the EBR serving pipeline improved
by the optimized DiskANN, the V3 version further leads to another +1.63% RPM
gain after the mainstream of the previous two versions.

---
Shipped Version |  RPM Growth |  P-Value
V1 (Multi-Objective) |  +3.27% |  1.82$e^{-2}$
V2 (Negative Sampling) |  +3.06% |  1.57$e^{-2}$
V3 (Optimized DiskANN) |  +1.63% |  2.06$e^{-2}$
Table 4. Online A/B Tests for Uni-Retriever (V1-V3).

##  5\. Related Work

EBR has been widely applied to many applications, e.g., web search (Shen et
al., 2014; Liu et al., 2021a), question answering (Karpukhin et al., 2020; Qu
et al., 2021), online advertising (Lu et al., 2020; Li et al., 2021), and
recommender systems (Huang et al., 2020; Xiao et al., 2021a). Generic EBR
systems are designed for homogeneous objectives; e.g., the items users’ may
click in recommender systems, or the web-pages containing ground-truth answers
in web search. However, EBR in sponsored search is more complicated due to the
need of serving multiple retrieval purposes. For one thing, the retrieved ads
have to be semantically close to user’s specified query. For another thing,
the retrieved ads are expected to be clicked by the user with high
probabilities. Such a problem was recognized by prior works (Fan et al., 2019;
Lu et al., 2020; Li et al., 2019). However, the learning of a unified model
for the retrieval of ads with both high-CTR and high relevance still lacks of
systematic studies.

A typical EBR system consists of two fundamental components: the
representation model and the ANN index. In Recent years, the pretrained
language models (PLMs) (Devlin et al., 2018) are widely adopted as the
backbone of representation models (Reimers and Gurevych, 2019; Karpukhin et
al., 2020; Luan et al., 2020); besides, people also propose to learn specific
PLMs for EBR purpose (Chang et al., 2020; Gao and Callan, 2021; Lu et al.,
2021). In addition to the backbone model, the training algorithm is another
critical factor. Most of the representation model is trained via contrastive
learning (Hadsell et al., 2006), whose performance is affected by the negative
sampling strategy. On one hand, it is found that the representation quality
can be improved by using an increased amount of negative samples (Chen et al.,
2020; He et al., 2020; Qu et al., 2021). As a result, different methods are
used to improve the scale of negative samples in a cost-efficient way, e.g.,
in-batch negative sampling (Chen et al., 2020; Karpukhin et al., 2020), and
momentum encoder (He et al., 2020). On the other hand, the representation
quality may also benefit from hard negatives. It’s found that the negative
samples selected by lexical similarity (Luan et al., 2020; Karpukhin et al.,
2020) are helpful; later on, people observed additional gains by using
negatives from ANN (Gillick et al., 2019; Xiong et al., 2020).

The ANN index is another building block of EBR in addition to the
representation model, with which the Top-$N$ answers can be efficiently
retrieved from the entire corpus (Jégou et al., 2011; Ge et al., 2013; Malkov
and Yashunin, 2018; Fu et al., 2017). However, the existing methods are
limited by either time cost, memory usage, or retrieval quality when applied
to massive-scale EBR. The latest studies, e.g., DiskANN (Subramanya et al.,
2019), SPANN (Chen et al., 2021), propose to jointly leverage embedding
compression and graph-based index for time and memory scalable ANN. Knowing
that Bing needs to work with a billion-scale ads corpus, we leverage DiskANN
for its high scalability, and we move beyond by substantially optimizing the
compressed embeddings and posting lists for better retrieval quality.

##  6\. Conclusion

In this paper, we introduce our representation learning framework, Uni-
Retriever, developed for Bing Sponsored Search. In Uni-Retriever, the
knowledge distillation and contrastive learning are collaborated for the
retrieval of ads with both high relevance and high CTR. We elaborate our
optimization strategies designed for Uni-Retriever, including the cross-device
negative sampling, relevance filtered ANN hard negatives, and disentangled
representation learning. We also present our practice on massive-scale EBR
serving, which further contributes to the retrieval performance on top of the
substantially optimized DiskANN. Finally, we perform extensive offline
experiments and online A/B tests, whose results verify the effectiveness of
the proposed techniques.

## References

  * (1)
  * Baranchuk et al. (2018) Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018\.  Revisiting the inverted indices for billion-scale approximate nearest neighbors. In _Proceedings of the European Conference on Computer Vision (ECCV)_. 202–216.
  * Chang et al. (2020) Wei-Cheng Chang, Felix X Yu, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar. 2020.  Pre-training tasks for embedding-based large-scale retrieval.  _arXiv preprint arXiv:2002.03932_ (2020).
  * Chen et al. (2021) Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021\.  SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search.  _arXiv preprint arXiv:2111.08566_ (2021).
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020.  A simple framework for contrastive learning of visual representations. In _International conference on machine learning_. PMLR, 1597–1607.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Fan et al. (2019) Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li. 2019\.  MOBIUS: towards the next generation of query-ad matching in baidu’s sponsored search. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2509–2517.
  * Fu et al. (2017) Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017\.  Fast approximate nearest neighbor search with the navigating spreading-out graph.  _arXiv preprint arXiv:1707.00143_ (2017).
  * Gao and Callan (2021) Luyu Gao and Jamie Callan. 2021.  Condenser: a Pre-training Architecture for Dense Retrieval. In _EMNLP_. 981–993.
  * Ge et al. (2013) Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013\.  Optimized product quantization.  _IEEE transactions on pattern analysis and machine intelligence_ 36, 4 (2013), 744–755.
  * Gillick et al. (2019) Daniel Gillick, Sayali Kulkarni, Larry Lansing, Alessandro Presta, Jason Baldridge, Eugene Ie, and Diego Garcia-Olano. 2019.  Learning dense representations for entity retrieval.  _arXiv preprint arXiv:1909.10506_ (2019).
  * Guo et al. (2020) Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020.  Accelerating large-scale inference with anisotropic vector quantization. In _ICML_. PMLR, 3887–3896.
  * Hadsell et al. (2006) Raia Hadsell, Sumit Chopra, and Yann LeCun. 2006\.  Dimensionality reduction by learning an invariant mapping. In _2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06)_ , Vol. 2. IEEE, 1735–1742.
  * He et al. (2020) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. 2020.  Momentum contrast for unsupervised visual representation learning. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 9729–9738.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015\.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ (2015).
  * 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_. 2553–2561.
  * Jegou et al. (2010) Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010\.  Product quantization for nearest neighbor search.  _IEEE transactions on pattern analysis and machine intelligence_ 33, 1 (2010), 117–128.
  * Jégou et al. (2011) Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011.  Searching in one billion vectors: re-rank with source coding. In _ICASSP_. IEEE.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019\.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ (2019).
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020\.  Dense Passage Retrieval for Open-Domain Question Answering. In _EMNLP_. 6769–6781.
  * Kim (2014) Yoon Kim. 2014.  Convolutional Neural Networks for Sentence Classification. In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Doha, Qatar, 1746–1751.  https://doi.org/10.3115/v1/D14-1181
  * Li et al. (2021) Chaozhuo Li, Bochen Pang, Yuming Liu, Hao Sun, Zheng Liu, Xing Xie, Tianqi Yang, Yanling Cui, Liangjie Zhang, and Qi Zhang. 2021\.  AdsGNN: Behavior-Graph Augmented Relevance Modeling in Sponsored Search.  _arXiv preprint arXiv:2104.12080_ (2021).
  * Li et al. (2019) Xue Li, Zhipeng Luo, Hao Sun, Jianjin Zhang, Weihao Han, Xianqi Chu, Liangjie Zhang, and Qi Zhang. 2019\.  Learning Fast Matching Models from Weak Annotations. In _The World Wide Web Conference_. 2985–2991.
  * Liu et al. (2021a) Yiding Liu, Weixue Lu, Suqi Cheng, Daiting Shi, Shuaiqiang Wang, Zhicong Cheng, and Dawei Yin. 2021a.  Pre-trained Language Model for Web-scale Retrieval in Baidu Search. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 3365–3375.
  * Liu et al. (2021b) Yiqun Liu, Kaushik Rangadurai, Yunzhong He, Siddarth Malreddy, Xunlong Gui, Xiaoyi Liu, and Fedor Borisyuk. 2021b.  Que2search: Fast and accurate query and document understanding for search at facebook. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 3376–3384.
  * Lu et al. (2021) Shuqi Lu, Di He, Chenyan Xiong, Guolin Ke, Waleed Malik, Zhicheng Dou, Paul Bennett, Tieyan Liu, and Arnold Overwijk. 2021.  Less is More: Pre-train a Strong Text Encoder for Dense Retrieval Using a Weak Decoder.  _arXiv preprint arXiv:2102.09206_ (2021).
  * Lu et al. (2020) Wenhao Lu, Jian Jiao, and Ruofei Zhang. 2020.  Twinbert: Distilling knowledge to twin-structured compressed BERT models for large-scale retrieval. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 2645–2652.
  * Luan et al. (2020) Yi Luan, Jacob Eisenstein, Kristina Toutanova, and Michael Collins. 2020.  Sparse, dense, and attentional representations for text retrieval.  _arXiv preprint arXiv:2005.00181_ (2020).
  * Luan et al. (2021) Yi Luan, Jacob Eisenstein, Kristina Toutanova, and Michael Collins. 2021.  Sparse, Dense, and Attentional Representations for Text Retrieval.  _Transactions of the Association for Computational Linguistics_ 9 (2021), 329–345.
  * Malkov and Yashunin (2018) Yu A Malkov and Dmitry A Yashunin. 2018.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE transactions on pattern analysis and machine intelligence_ 42, 4 (2018), 824–836.
  * Qu et al. (2021) Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021.  RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 5835–5847.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _arXiv preprint arXiv:1908.10084_ (2019).
  * Shen et al. (2014) Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014.  Learning semantic representations using convolutional neural networks for web search. In _Proceedings of the 23rd international conference on world wide web_.
  * Subramanya et al. (2019) Suhas Jayaram Subramanya, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019\.  Diskann: Fast accurate billion-point nearest neighbor search on a single node. In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_. 13766–13776.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016\.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_ (2016).
  * Xiao et al. (2021a) Shitao Xiao, Zheng Liu, Yingxia Shao, Tao Di, and Xing Xie. 2021a.  Training Microsoft News Recommenders with Pretrained Language Models in the Loop.  _arXiv e-prints_ (2021), arXiv–2102.
  * Xiao et al. (2021b) Shitao Xiao, Zheng Liu, Yingxia Shao, Defu Lian, and Xing Xie. 2021b.  Matching-oriented Product Quantization For Ad-hoc Retrieval.  _arXiv preprint arXiv:2104.07858_ (2021).
  * Xiong et al. (2020) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N Bennett, Junaid Ahmed, and Arnold Overwijk. 2020\.  Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In _International Conference on Learning Representations_.
  * 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 _ICLR_.
  * Yao et al. (2021) Yunzhi Yao, Shaohan Huang, Wenhui Wang, Li Dong, and Furu Wei. 2021.  Adapt-and-Distill: Developing Small, Fast and Effective Pretrained Language Models for Domains.  _arXiv preprint arXiv:2106.13474_ (2021).


#  One dimensional directed polymer ”memory model”

Victor Dotsenko  LPTMC, Sorbonne Université, Paris, France

###### Abstract

In this paper we propose very simple statistical ”memory model” of one-
dimensional directed polymers which is capable to store and retrieve a given
random quenched trajectory. The model is defined in terms of the elastic
string Hamiltonian with the local attractive potential between the dynamic and
the quenched random strings. The average overlap between them is calculated as
a function of the temperature and the strength of the attractive potential.

###### pacs:

05.20.-y 75.10.Nr

##  I Introduction

Usually the statistical properties of one-dimensional directed polymers are
studied in the context of their free energy fluctuations caused by the
presence of quenched random potential (see e.g. KPZ ; hh_zhang_95 ; Corwin ;
Borodin ; Rev ). Here I would like to propose another type of the directed
polymer model in which quenched disorder is present in a form of a given
random trajectory. Namely, we will consider the model of directed polymers
defined in terms of an elastic string $\phi(\tau)$ directed along the
$\tau$-axes within an interval $[0,t]$ in the presence of another quenched
random string $\varphi(\tau)$ with an attractive interaction potential
$U\bigl{[}\phi(\tau)-\varphi(\tau)\bigr{]}$ between them. Both strings have
the same boundary constraints $\phi(0)=\phi(t)=0$ and
$\varphi(0)=\varphi(t)=0$. For a given quenched trajectory $\varphi(\tau)$ the
energy of the string $\phi(\tau)$ is

$H[\phi(\tau);\varphi(\tau)]=\int_{0}^{t}d\tau\Bigl{\\{}\frac{1}{2}\bigl{[}\partial_{\tau}\phi(\tau)\bigr{]}^{2}+U\bigl{[}\phi(\tau)-\varphi(\tau)\bigr{]}\Bigr{\\}}$
(1)

The interaction potential $U(\phi)$ is supposed to be short-ranged:

$U(\phi)\;=\;-\frac{u}{\epsilon\sqrt{2\pi}}\,\exp\Bigl{\\{}-\frac{1}{2\epsilon^{2}}\phi^{2}\Bigr{\\}}$
(2)

where positive parameter $u$ defines the strength of the interaction and
$\epsilon$ is the typical interaction distance of the quenched and the
dynamical trajectories. The (normalized) probability distribution function
${\cal P}\bigl{[}\varphi(\tau)\bigr{]}$ of the quenched random trajectories
$\varphi(\tau)$ (such that $\varphi(0)=\varphi(t)=0$) is taken in the Gaussian
form

${\cal P}\bigl{[}\varphi(\tau)\bigr{]}\;=\;\sqrt{\frac{2\pi
t}{\gamma}}\,\exp\biggl{\\{}-\frac{1}{2}\gamma\int_{0}^{t}d\tau\;\bigl{(}\partial\varphi(\tau)\bigr{)}^{2}\biggr{\\}}$
(3)

where $\gamma$ is the elasticity parameter.

For a given quenched trajectory $\varphi(\tau)$ the partition function of this
system is

$Z\bigl{[}\varphi(\tau)\bigr{]}\;=\;\int_{\phi(0)=0}^{\phi(t)=0}{\cal
D}\phi(\tau)\,\exp\biggl{\\{}-\beta\,\int_{0}^{t}d\tau\Bigl{[}\frac{1}{2}\bigl{(}\partial_{\tau}\phi(\tau)\bigr{)}^{2}\;+\;U\bigl{[}\phi(\tau)-\varphi(\tau)\bigr{]}\Bigr{]}\biggr{\\}}$
(4)

where $\beta=1/T$ is the inverse temperature, and the integration goes over
all (continuous) trajectories with the zero boundary conditions. The
integration measure is chosen such that

$\int_{\phi(0)=0}^{\phi(t)=x}{\cal
D}\phi(\tau)\,\exp\biggl{\\{}-\frac{1}{2}\beta\,\int_{0}^{t}d\tau\;\bigl{(}\partial_{\tau}\phi(\tau)\bigr{)}^{2}\biggr{\\}}\;=\;\sqrt{\frac{\beta}{2\pi\,t}}\,\exp\Bigl{\\{}-\frac{\beta}{2t}\,x^{2}\Bigr{\\}}$
(5)

The physical (selfaveraging) free energy of this system is defined in the
usual way

$F(T,u,m)\;=\;-\frac{1}{\beta}\,\overline{\log\Bigl{(}Z\bigl{[}\varphi(\tau)\bigr{]}\Bigr{)}}$
(6)

where $\overline{(...)}$ denotes the averaging over random trajectories
$\varphi(\tau)$ with the probability distribution (3).

We will study this system in the thermodynamic limit $t\to\infty$. The final
goal of this study is to calculate the mean square difference between
$\phi(\tau)$ and $\varphi(\tau)$, namely

$q\;=\;\lim_{t\to\infty}\,\frac{1}{t}\int_{0}^{t}d\tau\,\overline{\big{\langle}\bigl{(}\phi(\tau)-\varphi(\tau)\bigr{)}^{2}\big{\rangle}}$
(7)

where $\langle...\rangle$ denotes the thermal average over the string
trajectories $\phi(\tau)$ defined by the Hamiltonian (1). Then the ”order
parameter” which describe the quality of retrieval of a given quenched random
trajectory $\varphi(\tau)$ by the dynamic string $\phi(\tau)$ can be defined
as

$m\;=\;\frac{1}{1\,+\,q}$ (8)

In the case of perfect retrieval, when $q\to 0$, we get $m\to 1$, while in the
case of no retrieval, when $q\to\infty$, we get $m\to 0$

In this paper we will consider two limit cases cases. First (Section II),
supposing that the trajectories on average are close to each other, such that
$q\ll\epsilon^{2}$, the interaction potential can be approximated as

$U(\phi-\varphi)\;\simeq\;-\frac{u}{\epsilon\sqrt{2\pi}}\;+\;\frac{u}{2\epsilon^{3}\sqrt{2\pi}}\,\bigl{(}\phi-\varphi\bigr{)}^{2}$
(9)

Second (Section III), supposing that the trajectories on average are far far
from each other, such that $q\gg\epsilon^{2}$, the interaction potential can
be approximated as

$U(\phi-\varphi)\;\simeq\;-u\,\delta(\phi-\varphi)$ (10)

It will be shown that in both cases the retrieval parameter $m$, eq.(8), can
be computed explicitly exhibiting smooth dependence on $T$ and $u$. Finally,
Section IV is devoted to the brief discussion of the obtained results.

##  II Gaussian approximation

In the Gaussian approximation, eq.(9), (neglecting irrelevant constant term
$-u/\epsilon\sqrt{2\pi}$) the Hamiltonian of the considered system, eq.(1),
becomes

$H[\phi(\tau);\varphi(\tau)]=\int_{0}^{t}d\tau\Bigl{\\{}\frac{1}{2}\bigl{[}\partial_{\tau}\phi(\tau)\bigr{]}^{2}\;+\;\frac{1}{2}\lambda\,\bigl{(}\phi(\tau)-\varphi(\tau)\bigr{)}^{2}\Bigr{\\}};$
(11)

where

$\lambda\;=\;\frac{u}{\epsilon^{3}\sqrt{2\pi}}$ (12)

In terms of the standard replica approach the average free energy, eq.(6), can
be computed as

$F\;=\;-\lim_{N\to 0}\,\frac{1}{\beta N}\,\log\bigl{(}Z_{N}\bigr{)}$ (13)

where

$\displaystyle Z_{N}$ $\displaystyle\equiv$
$\displaystyle\overline{\Bigl{(}Z[\varphi(\tau)]\Bigr{)}^{N}}\;=\;$ (14)
$\displaystyle=$ $\displaystyle\int_{\varphi(0)=0}^{\varphi(t)=0}{\cal
D}\varphi(\tau)\,{\cal
P}\bigl{[}\varphi\bigr{]}\prod_{a=1}^{N}\biggl{[}\int_{\phi_{a}(0)=0}^{\phi_{a}(t)=0}{\cal
D}\phi_{a}(\tau)\biggr{]}\exp\biggl{\\{}-\frac{1}{2}\beta\sum_{a=1}^{N}\int_{0}^{t}d\tau\Bigl{[}\bigl{(}\partial_{\tau}\phi_{a}(\tau)\bigr{)}^{2}+\lambda\bigl{(}\phi_{a}(\tau)-\varphi(\tau)\bigr{)}^{2}\Bigr{]}\biggr{\\}}$

is the replica partition function. Substituting here the probability
distribution function ${\cal P}\bigl{[}\varphi\bigr{]}$, eq.(3), we get

$Z_{N}\;=\;\sqrt{\frac{2\pi
t}{\gamma}}\,\int_{\varphi(0)=0}^{\varphi(t)=0}{\cal
D}\varphi(\tau)\prod_{a=1}^{N}\biggl{[}\int_{\phi_{a}(0)=0}^{\phi_{a}(t)=0}{\cal
D}\phi_{a}(\tau)\biggr{]}\;\exp\Bigl{\\{}-{\cal
H}_{N}[\phi_{a};\varphi]\Bigr{\\}}$ (15)

with the replica Hamiltonian

${\cal
H}_{N}[\phi_{a};\varphi]\,=\,\frac{1}{2}\int_{0}^{t}\Bigl{[}\beta\sum_{a=1}^{N}\bigl{(}\partial_{\tau}\phi_{a}\bigr{)}^{2}+\gamma\bigl{(}\partial_{\tau}\varphi\bigr{)}^{2}+\beta\lambda\sum_{a=1}^{N}\bigl{(}\phi_{a}-\varphi\bigr{)}^{2}\Bigr{]}$
(16)

To compute the replica partition function (15) let us introduce more
complicated function

$\Psi[{\bf x};\,y;\,t]=\int_{\varphi(0)=0}^{\varphi(t)=y}{\cal
D}\varphi(\tau)\prod_{a=1}^{N}\biggl{[}\int_{\phi_{a}(0)=0}^{\phi_{a}(t)=x_{a}}{\cal
D}\phi_{a}(\tau)\biggr{]}\;\exp\Bigl{\\{}-{\cal
H}_{N}[\phi_{a};\varphi]\Bigr{\\}}$ (17)

(where ${\bf x}=\\{x_{1},x_{2},...,x_{N}\\}$ ) such that

$Z_{N}\;=\;\sqrt{\frac{2\pi t}{\gamma}}\,\Psi[{\bf 0};\,0;\,t]$ (18)

One can easily show that the above function $\Psi[{\bf x};\,y;\,t]$ satisfy
the imaginary-time Schrödinger equation for (N+1) quantum bosons

$\frac{\partial}{\partial
t}\Psi\;=\;\frac{1}{2\beta}\sum_{a=1}^{N}\frac{\partial^{2}}{\partial
x_{a}^{2}}\,\Psi\;+\;\frac{1}{2\gamma}\frac{\partial^{2}}{\partial
y^{2}}\,\Psi\;-\;\frac{1}{2}\beta\lambda\,\sum_{a=1}^{N}(x_{a}-y)^{2}\,\Psi$
(19)

In the limit $t\to\infty$ the solution $\Psi[{\bf x};\,y;\,t]$ of the above
equation is dominated by the ground state wave function

$\Psi[{\bf x};\,y;\,t]\;\simeq\;\exp\bigl{\\{}-E\,t\bigr{\\}}\,\psi({\bf
x};\,y)$ (20)

As in this limit we will be interested only in the extensive part of the free
energy, in what follows all pre-exponetial factors (like $\sqrt{2\pi
t/\gamma}$ in eq.(18)) will be omitted. The ground state energy $E$ and the
ground state eigenfunction $\psi({\bf x};\,y)$ are defined by the equation

$-E\,\psi\;=\;\frac{1}{2\beta}\sum_{a=1}^{N}\frac{\partial^{2}}{\partial
x_{a}^{2}}\,\psi\;+\;\frac{1}{2\gamma}\frac{\partial^{2}}{\partial
y^{2}}\,\psi\;-\;\frac{1}{2}\beta\lambda\,\sum_{a=1}^{N}(x_{a}-y)^{2}\,\psi$
(21)

It is evident that the solution of the above equation must have the Gaussian
form

$\psi({\bf
x};\,y)\;=\;\exp\biggl{\\{}-\frac{1}{2}A\sum_{a=1}^{N}x_{a}^{2}\;-\;\frac{1}{2}B\,y^{2}\;-\;C\Bigl{(}\sum_{a=1}^{N}x_{a}\Bigr{)}\,y\;-\;\frac{1}{2}D\Bigl{(}\sum_{a=1}^{N}x_{a}\Bigr{)}^{2}\biggr{\\}}$
(22)

where the parameters $A,\,B,\,C$ and $D$ are to be defined. Substituting
eq.(22) into eq.(21) we are getting the following set of equations

$\displaystyle A^{2}\;=\;\beta^{2}\lambda$ (23)
$\displaystyle\frac{1}{\gamma}B^{2}\,+\,\frac{N}{\beta}C^{2}\;=\;\beta\lambda\,N$
(24)
$\displaystyle\frac{N}{\beta}D^{2}\,+\,\frac{2}{\beta}AD\,+\,\frac{1}{\gamma}C^{2}\;=\;0$
(25) $\displaystyle
C\,\Bigl{(}\frac{1}{\beta}A\,+\,\frac{N}{\beta}D\,+\,\frac{1}{\gamma}B\Bigr{)}\;=\;-\beta\lambda$
(26)

and

$E\;=\;\frac{N}{2\beta}(A\,+\,D)\;+\;\frac{1}{2\gamma}B$ (27)

It can be easily shown that in the first order in $N\to 0$ the solution of
these equations is

$\displaystyle A$ $\displaystyle=$ $\displaystyle\beta\sqrt{\lambda}$ (28)
$\displaystyle B$ $\displaystyle\simeq$
$\displaystyle\beta\sqrt{\lambda}\,N\;+\;o(N)$ (29) $\displaystyle C$
$\displaystyle\simeq$
$\displaystyle-\beta\sqrt{\lambda}\;+\;\frac{1}{2\gamma}\beta^{2}\sqrt{\lambda}\,N\;+\;o(N)$
(30) $\displaystyle D$ $\displaystyle\simeq$
$\displaystyle-\frac{1}{2\gamma}\beta^{2}\sqrt{\lambda}\;+\;\frac{3}{8\gamma^{2}}\beta^{3}\sqrt{\lambda}\,N\;+\;o(N)$
(31)

so that

$E\;\simeq\;N\,\Bigl{(}\frac{1}{2}\sqrt{\lambda}\;+\;\frac{\beta}{4\gamma}\sqrt{\lambda}\Bigr{)}$
(32)

Substituting the above results into eqs.(20) and eq.(18) (and neglecting pre-
exponential factor) we get

$Z_{N}\;\simeq\;\exp\biggl{\\{}-N\biggl{(}\frac{1}{2}\,\sqrt{\lambda}\;+\;\frac{\beta}{4\gamma}\sqrt{\lambda}\biggr{)}\,t\biggr{\\}}$
(33)

Thus, according to eq.(13), for the extensive in $t$ part of the free energy
one finally obtains

$F(T,\lambda)\;=\;\biggl{(}\frac{1}{2}\,T\sqrt{\lambda}\;+\;\frac{1}{4\gamma}\sqrt{\lambda}\biggr{)}\,t$
(34)

One can easily see that according to its definition, eq.(7), the overlap
parameter $q$ can be obtained as

$q\;=\;\frac{2}{t}\,\frac{\partial}{\partial\lambda}\,F(T,\lambda)$ (35)

so that one immediately find the following result

$q\;=\;\frac{1}{2\sqrt{\lambda}}\Bigl{(}T\;+\;\frac{1}{2\gamma}\Bigr{)}$ (36)

or, in original notations, eq.(12),

$q\;=\;\Bigl{(}\frac{\pi}{8}\Bigr{)}^{1/4}\,\Bigl{(}T+\frac{1}{2\gamma}\Bigr{)}\,\sqrt{\frac{\epsilon^{3}}{u}}$
(37)

Correspondingly, for the retrieval order parameter, eq.(8), we get

$m(u,T)\;=\;\frac{\sqrt{u}}{\sqrt{u}\;+\;\bigl{(}\frac{\pi}{8}\bigr{)}^{1/4}\,\Bigl{(}T+\frac{1}{2\gamma}\Bigr{)}\epsilon^{3/2}}$
(38)

However, according to the discussion in the ending part of the Introduction,
the Gaussian approximation, eq.(9), considered in this Section is valid only
provided $q\ll\epsilon^{2}$. Using eq.(37) we find that the above result for
the retrieval parameter $m$ is valid only for

$\sqrt{u\,\epsilon}\;\gg\;\Bigl{(}T+\frac{1}{2\gamma}\Bigr{)}$ (39)

We see that according to the result (38), as the coupling parameter $u$
increases from it minimal allowed value
$\sim\Bigl{(}T+\frac{1}{2\gamma}\Bigr{)}^{2}/\epsilon$ to infinity, the value
of $m$ increases from a finite value to one (which corresponds to perfect
retrieval).

##  III Short range interaction limit

In the short range interaction approximation, eq.(10), the Hamiltonian of the
considered system, eq.(1), becomes

$H[\phi(\tau);\varphi(\tau)]=\int_{0}^{t}d\tau\Bigl{\\{}\frac{1}{2}\bigl{(}\partial_{\tau}\phi(\tau)\bigr{)}^{2}\;-\;u\,\delta\bigl{(}\phi(\tau)-\varphi(\tau)\bigr{)}\Bigr{\\}}$
(40)

Following the same rout of the replica formalism described in the previous
Section, instead of eq.(16) for the replica Hamiltonian we get

${\cal
H}_{N}[\phi_{a};\varphi]\,=\,\frac{1}{2}\int_{0}^{t}\Bigl{[}\beta\sum_{a=1}^{N}\bigl{(}\partial_{\tau}\phi_{a}\bigr{)}^{2}+\gamma\bigl{(}\partial_{\tau}\varphi\bigr{)}^{2}+2\beta
u\sum_{a=1}^{N}\delta\bigl{(}\phi_{a}-\varphi\bigr{)}^{2}\Bigr{]}$ (41)

Correspondingly, for the wave function (17) (which defines the replica
partition function according to eq.(18)) we are getting the imaginary-time
Schrödinger equation for (N+1) quantum bosons

$\frac{\partial}{\partial t}\Psi({\bf
x},y,t)\;=\;\frac{1}{2\beta}\sum_{a=1}^{N}\frac{\partial^{2}}{\partial
x_{a}^{2}}\,\Psi({\bf
x},y,t)\;+\;\frac{1}{2\gamma}\frac{\partial^{2}}{\partial y^{2}}\,\Psi({\bf
x},y,t)\;+\;\beta u\,\sum_{a=1}^{N}\delta(x_{a}-y)\;\Psi({\bf x},y,t)$ (42)

and in the representation (20) we find that the ground state energy and the
ground state wave function are defined by the equation

$-E\,\psi({\bf
x},y)\;=\;\frac{1}{2\beta}\sum_{a=1}^{N}\frac{\partial^{2}}{\partial
x_{a}^{2}}\,\psi({\bf x},y)\;+\;\frac{1}{2\gamma}\frac{\partial^{2}}{\partial
y^{2}}\,\psi({\bf x},y)\;+\;\beta u\,\sum_{a=1}^{N}\delta(x_{a}-y)\;\psi({\bf
x},y)$ (43)

The structure of the above equation implies that its solution is the function
of the differences $(x_{a}-y)=z_{a}$, namely, $\psi\bigl{(}{\bf
x},y\bigr{)}\,=\,\psi\bigl{(}{\bf z}\bigr{)}$. In terms of these new variables
instead of eq.(43) we get

$-E\,\psi({\bf
z})\;=\;\frac{1}{2\beta}\sum_{a=1}^{N}\frac{\partial^{2}}{\partial
z_{a}^{2}}\,\psi({\bf
z})\;+\;\frac{1}{2\gamma}\sum_{a,b=1}^{N}\frac{\partial^{2}}{\partial
z_{a}\partial z_{b}}\,\psi({\bf z})\;+\;\beta
u\,\sum_{a=1}^{N}\delta(z_{a})\;\psi({\bf z})$ (44)

Integrating this equation over a particular $z_{a}$ in a narrow interval
around zero from $-\eta$ to $+\eta$ (where $\eta\ll 1$) and assuming that
$\psi({\bf z})$ is a continuous function, we find that the derivatives of this
function has a singularity at $z_{a}=0$:

$\Bigl{(}\frac{1}{2\beta}\,+\,\frac{1}{2\gamma}\Bigr{)}\biggl{(}\frac{\partial}{\partial
z_{a}}\psi({\bf z})\bigg{|}_{z_{a}=+\eta}-\;\frac{\partial}{\partial
z_{a}}\psi({\bf z})\bigg{|}_{z_{a}=-\eta}\biggr{)}\;=\;-\beta u\,\psi({\bf
z})\Big{|}_{z_{a}=0}$ (45)

On the other hand, in the region of space where all $z_{a}\not=0$ the function
$\psi({\bf z})$ must satisfy the equation

$\frac{1}{2\beta}\sum_{a=1}^{N}\frac{\partial^{2}}{\partial
z_{a}^{2}}\,\psi({\bf
z})\;+\;\frac{1}{2\gamma}\sum_{a,b=1}^{N}\frac{\partial^{2}}{\partial
z_{a}\partial z_{b}}\,\psi({\bf z})\;=\;-E\,\psi({\bf z})$ (46)

One can easily show that for negative values of the energy $E$ the above
equation has $2^{N}$ solutions labeled by $N$ Ising parameters
$\\{\sigma_{a}=\pm 1\\}\;\;(a=1,...,N)$, such that a given set of $\sigma$’s

$\psi({\bf
z})\;=\;\psi_{0}\,\exp\biggl{\\{}-\omega\sum_{a=1}^{N}\sigma_{a}\,z_{a}\biggr{\\}}$
(47)

where $\psi_{0}$ is irrelevant normalization constant and

$\omega\;=\;\frac{\sqrt{2|E|}}{\sqrt{\frac{1}{\beta}N\;+\;\frac{1}{\gamma}\Bigl{(}\sum_{a=1}^{N}\sigma_{a}\Bigr{)}^{2}}}$
(48)

Let us consider a particular set $\\{\sigma_{1},\sigma_{2},...,\sigma_{N}\\}$
in which $k$ elements are positive and $(N-k)$ elements are negative (where
$k=0,1,...,N$). Reordering these $\sigma$’s, this particular set can always be
represented as

$\sigma_{a}\;=\;\left\\{\begin{array}[]{ll}+1,&\mbox{for $a=1,2,...,k$}\\\ \\\
-1,&\mbox{for $a=k+1,...,N$}\end{array}\right.$ (49)

In this case

$\sum_{a=1}^{N}\sigma_{a}=2k-N$ (50)

Thus, for such particular choice of $\sigma$’s, according to eq.(48),

$\omega\;=\;\frac{\sqrt{2|E|}}{\sqrt{\frac{1}{\beta}N\;+\;\frac{1}{\gamma}(2k-N)^{2}}}$
(51)

As the solution of eq.(46) must be symmetric with respect to permutations of
$z_{a}$ it can be represented as follows:

$\psi^{(+k)}({\bf z})\;=\;\psi_{0}\,\sum_{{\cal
P}^{k}_{N}}\exp\biggl{\\{}-\omega\sum_{a=1}^{N}\sigma_{a}\,z_{{\cal
P}^{k}_{N}(a)}\biggr{\\}}\;=\;\psi_{0}\,\sum_{{\cal
P}^{k}_{N}}\exp\Bigl{\\{}-\omega\sum_{a=1}^{k}z_{{\cal
P}^{k}_{N}(a)}+\omega\sum_{a=k+1}^{N}z_{{\cal P}^{k}_{N}(a)}\Bigr{\\}}$ (52)

where the summation goes over all permutations ${\cal P}^{k}_{N}$ of $N$
points $z_{a}$ over $(k\;+\;(N-k))$ elements $\sigma_{a}$ (which are defined
in eq.(49)). It is evident that for ”antisymmetric” choice:
$\sigma_{a}\to-\sigma_{a}$ (for which $\sum_{a=1}^{N}\sigma_{a}=-(2k-N)$) the
function

$\psi^{(-k)}({\bf z})\;=\;\psi_{0}\,\sum_{{\cal
P}^{k}_{N}}\exp\Bigl{\\{}\omega\sum_{a=1}^{k}z_{{\cal
P}^{k}_{N}(a)}-\omega\sum_{a=k+1}^{N}z_{{\cal P}^{k}_{N}(a)}\Bigr{\\}}$ (53)

is also the solution of eq.(46). Let us remind now that the solution of the
original equation (44) must satisfy the conditions (45). Taking into account
these conditions, one can easily see that for a given permutation ${\cal
P}^{k}_{N}$ the function which satisfy both eqs.(45) and eq.(46), and decaying
zero for all $z_{a}\to\pm\infty$ can be defined as follows

$\psi^{(k)}_{{\cal P}^{k}_{N}}({\bf
z})=\left\\{\begin{array}[]{ll}\exp\Bigl{\\{}-\omega\sum_{a=1}^{k}z_{{\cal
P}^{k}_{N}(a)}+\omega\sum_{a=k+1}^{N}z_{{\cal
P}^{k}_{N}(a)}\Bigr{\\}},&\mbox{for $\\{z_{{\cal P}^{k}_{N}(1)},...,z_{{\cal
P}^{k}_{N}(k)}\\}>0$ and $\\{z_{{\cal P}^{k}_{N}(k+1)},...,z_{{\cal
P}^{k}_{N}(N)}\\}<0$}\\\ \\\ \\\ \exp\Bigl{\\{}+\omega\sum_{a=1}^{k}z_{{\cal
P}^{k}_{N}(a)}-\omega\sum_{a=k+1}^{N}z_{{\cal
P}^{k}_{N}(a)}\Bigr{\\}},&\mbox{for $\\{z_{{\cal P}^{k}_{N}(1)},...,z_{{\cal
P}^{k}_{N}(k)}\\}<0$ and $\\{z_{{\cal P}^{k}_{N}(k+1)},...,z_{{\cal
P}^{k}_{N}(N)}\\}>0$}\end{array}\right.$ (54)

where, according to eq.(45), the parameter $\omega$ must satisfy the condition

$\Bigl{(}\frac{1}{2\beta}\,+\,\frac{1}{2\gamma}\Bigr{)}\bigl{(}-2\omega\bigr{)}\;=\;-\beta
u\,\psi({\bf z})\Big{|}_{z_{a}=0}$ (55)

or

$\omega\;=\;\frac{\beta^{2}u\gamma}{(\beta+\gamma)}$ (56)

Comparing this value of $\omega$ with the one in eq.(51) we find the
corresponding eigenenergy:

$E_{k}\;=\;-\frac{\beta^{4}u^{2}\gamma^{2}}{2(\beta+\gamma)^{2}}\,\Bigl{(}\frac{1}{\beta}N\;+\;\frac{1}{\gamma}(2k-N)^{2}\Bigr{)}$
(57)

Thus we conclude that eq.(44) exhibits the spectrum of solutions labeled by
the integer parameter $k\;=\;0,1,2,...,N$:

$\psi^{(k)}({\bf z})\;=\;\psi_{0}\,\sum_{{\cal P}^{k}_{N}}\,\psi^{(k)}_{{\cal
P}^{k}_{N}}({\bf z})$ (58)

where the function $\psi^{(k)}_{{\cal P}^{k}_{N}}({\bf z})$ is given in
eq.(54), the parameter $\omega$ is given in eq.(56) and the eigenenergy
$E_{k}$ is given in eq.(57). Correspondingly, according to eqs.(18) and (20),
for the replica partition function (neglecting pre-exponential factor) we get

$Z_{N}\;\sim\;\sum_{k=0}^{N}\;\exp\bigl{\\{}-E_{k}t\bigr{\\}}\sum_{{\cal
P}^{k}_{N}}\,\psi^{(k)}_{{\cal P}^{k}_{N}}({\bf
0})\;=\;\sum_{k=0}^{N}\frac{N!}{k!\,(N-k)!}\exp\biggl{\\{}\frac{\beta^{4}u^{2}\gamma^{2}}{2(\beta+\gamma)^{2}}\,\Bigl{(}\frac{1}{\beta}N\;+\;\frac{1}{\gamma}(2k-N)^{2}\Bigr{)}\;t\biggr{\\}}$
(59)

Simple calculations yield:

$Z_{N}\;\sim\;\exp\biggl{\\{}\frac{\beta^{2}u^{2}\gamma^{2}}{2(\beta+\gamma)^{2}}\,(\beta
N)\,t\biggr{\\}}\times S$ (60)

where

$\displaystyle S$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{N}\frac{N!}{k!\,(N-k)!}\exp\biggl{\\{}\frac{\beta^{4}u^{2}\gamma}{2(\beta+\gamma)^{2}}\,(2k-N)^{2}\,t\biggr{\\}}$
(61) $\displaystyle=$
$\displaystyle\int_{-\infty}^{+\infty}\frac{d\xi}{\sqrt{2\pi}}\exp\Bigl{\\{}-\frac{1}{2}\xi^{2}\Bigr{\\}}\;\sum_{k=0}^{N}\frac{N!}{k!\,(N-k)!}\exp\biggl{\\{}\frac{\beta^{2}u\sqrt{\gamma}}{(\beta+\gamma)}\,(2k-N)\sqrt{t}\;\xi\biggr{\\}}$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{+\infty}\frac{d\xi}{\sqrt{2\pi}}\exp\Bigl{\\{}-\frac{1}{2}\xi^{2}\Bigr{\\}}\;\biggl{[}2\,\cosh\Bigl{(}\frac{\beta^{2}u\sqrt{\gamma}}{(\beta+\gamma)}\sqrt{t}\;\xi\Bigr{)}\biggr{]}^{N}$

In the limit $t\to\infty$,

$S\;\simeq\;\int_{-\infty}^{+\infty}\frac{d\xi}{\sqrt{2\pi}}\exp\Bigl{\\{}-\frac{1}{2}\xi^{2}\;+\;\frac{\beta^{2}u\sqrt{\gamma}}{(\beta+\gamma)}\sqrt{t}\;N\;|\xi|\Bigr{\\}}\;\sim\;\exp\biggl{\\{}\frac{\beta^{2}u^{2}\gamma}{2(\beta+\gamma)^{2}}\,(\beta
N)^{2}\,t\biggr{\\}}$ (62)

Thus, for the replica partition function (60) (in the limit $t\to\infty$) we
get the following result

$Z_{N}\;\sim\;\exp\biggl{\\{}\frac{\beta^{2}u^{2}\gamma^{2}}{2(\beta+\gamma)^{2}}\,(\beta
N)\,t\;+\;\frac{\beta^{2}u^{2}\gamma}{2(\beta+\gamma)^{2}}\,(\beta
N)^{2}\,t\biggr{\\}}$ (63)

As the partition function of a system and its and free energy are related as
$Z=\exp\\{-\beta F\\}$, according to its definition, the replica partition
function $Z_{N}\;=\;\overline{Z^{N}}$ is related with the free energy
distribution function $P(F)$ as follows

$Z_{N}\;=\;\int_{-\infty}^{+\infty}dF\,P(F)\;\exp\bigl{\\{}-\beta
NF\bigr{\\}}$ (64)

According to eq.(63), we have

$\int_{-\infty}^{+\infty}dF\,P(F)\;\exp\bigl{\\{}-(\beta
N)F\bigr{\\}}\;=\;\exp\biggl{\\{}\frac{\beta^{2}u^{2}\gamma^{2}}{2(\beta+\gamma)^{2}}\,(\beta
N)\,t\;+\;\frac{\beta^{2}u^{2}\gamma}{2(\beta+\gamma)^{2}}\,(\beta
N)^{2}\,t\biggr{\\}}$ (65)

Using the above relation one easily finds that

$P(F)\;=\;\frac{1}{\sqrt{2\pi}(\delta
F)}\,\exp\Biggl{\\{}-\frac{\bigl{(}F-\overline{F}\bigr{)}^{2}}{2(\delta
F)^{2}}\Biggr{\\}}.$ (66)

where

$\overline{F}\;=\;\frac{\beta^{2}u^{2}\gamma^{2}}{2(\beta+\gamma)^{2}}\,t$
(67)

is the average free energy and

$\delta
F\;\equiv\;\sqrt{\overline{\bigl{(}F-\overline{F}\bigr{)}^{2}}}\;=\;\frac{\beta
u\sqrt{\gamma}}{(\beta+\gamma)}\;t^{1/2}$ (68)

is the mean square fluctuation of the free energy.

According to the definition, eq.(7), the overlap parameter $q$ can be
estimated as $q\,\sim\,\langle z^{2}\rangle$, where, according to eqs.(54) and
(56), $\langle z^{2}\rangle\,\sim\,1/\omega^{2}$, or

$q\;\sim\;\frac{(\beta+\gamma)^{2}}{\beta^{4}u^{2}\gamma^{2}}\;=\;\frac{1}{u^{2}}\,T^{2}\Bigl{(}T\,+\,\frac{1}{\gamma}\Bigr{)}^{2}$
(69)

Correspondingly, for the retrieval order parameter, eq.(8), we get

$m(u,T)\;\sim\;\frac{u^{2}}{u^{2}\;+\;T^{2}\Bigl{(}T\,+\,\frac{1}{\gamma}\Bigr{)}^{2}}$
(70)

Note that the short range approximation, eq.(10), considered in this Section
is valid only for $q\gg\epsilon^{2}$, or for

$\epsilon u\;\ll\;T\Bigl{(}T\,+\,\frac{1}{\gamma}\Bigr{)}$ (71)

##  IV Discussion

In conclusion, in this paper we have proposed very simple statistical ”memory
model” of one-dimensional directed polymers which is capable to store and
retrieve a given random quenched trajectory. The model is defined in terms of
the elastic string Hamiltonian (1) with the local attractive potential between
the dynamic and the quenched random strings. We have calculated the average
overlap between the dynamic and the quenched string $q(T,u)$, eq.(7), as well
as the effective ”retrieval parameter” $m(T,u)$, eq.(8). The explicit
expressions for these parameters as the functions of the temperature $T$ and
the coupling constant $u$ of the attractive potential $U(\phi)$ are calculated
in the two limit cases: first, in the harmonic approximation of the potential
$U(\phi)$, eq.(9), and second, in the $\delta$-function approximation of
$U(\phi)$, eq.(10). It is shown that $m(T,u)$ is the smooth function of $T$
and $u$, ranging from one (perfect retrieval) to zero (no retrieval).
Summarising the results derived in Section II and III, eqs.(39)-(38),
(70)-(71), for the ”retrieval parameter” $m(u,T)$ we get

$m(u,T)\;\sim\;\left\\{\begin{array}[]{ll}\frac{(\epsilon u)^{2}}{(\epsilon
u)^{2}\;+\;T^{2}\Bigl{(}T\,+\,\frac{1}{\gamma}\Bigr{)}^{2}\epsilon^{2}}=m_{\delta}(u,T),&\mbox{for
$u\;\ll\;\frac{1}{\epsilon}\,T\Bigl{(}T\,+\,\frac{1}{\gamma}\Bigr{)}\,=\,u_{\delta}(T)$}\\\
\\\ \frac{\sqrt{\epsilon u}}{\sqrt{\epsilon
u}\;+\;\bigl{(}\frac{\pi}{8}\bigr{)}^{1/4}\,\Bigl{(}T+\frac{1}{2\gamma}\Bigr{)}\epsilon^{2}}=m_{g}(u,T),&\mbox{for
$u\;\gg\;\frac{1}{\epsilon}\,\Bigl{(}T\,+\,\frac{1}{2\gamma}\Bigr{)}^{2}\,=\,u_{g}(T)$}\end{array}\right.$
(72)

where $\epsilon$ is the spatial size of the potential $U(\phi)$, eq.(2), and
$\gamma$ is the elastic parameter of quenched random string, eq.(3). Note that
at the crossover between the two regimes, the values of $m(u,T)$ nicely fits
with each other being independent of $T$ and $u$:

$m_{g}(u,T)\Big{|}_{u=u_{g}(T)}\,=\,\frac{1}{1\;+\;\bigl{(}\frac{\pi}{8}\bigr{)}^{1/4}\,\epsilon^{2}}\;\sim\;\frac{1}{1\;+\;\epsilon^{2}}\;\sim\;m_{\delta}(u,T)\Big{|}_{u=u_{\delta}(T)}$
(73)

The examples of the curves illustrating the dependence of the retrieval
parameter $m(u,T)$ on the coupling constant $u$ are shown in Figure 1.

Figure 1: The retrieval parameter $m(u,T)$, eq.(72), as a function of the
strength $u$ of the attractive potential $U(\phi)$, eq.(2), for three
different temperatures: (1) $T=0.5$, (2) $T=1$ and (3) $T=2$, with
$\epsilon=0.5$ (size of the potential $U(\phi)$) and $\gamma=1$ (elastic
parameter of a quenched random string)

Unfortunately, the generalization of the considered model for storing and
retrieving of several quenched trajectories (similar to storing of several
patterns in neural networks) looks rather problematic. The problem is that the
trajectories with independent distributions will be inevitably intersecting,
which makes the identification of a given trajectory ambiguous. On the other
hand, one can of course forbid the intersection of the quenched trajectories
(e.g. by introduction $\delta$-like repulsion in their joint distribution
function), but as a consequence one will face much more sophisticated
calculations (compared to the ones of the present paper) which still remains
to be done.

## References

  * (1) M.Kardar, G.Parisi,Y-C.Zhang, Phys. Rev. Lett. 56, 889 (1986)
  * (2) T. Halpin-Healy and Y-C. Zhang, Phys. Rep. 254, 215 (1995)
  * (3) I. Corwin, Random Matrices: Theory Appl. 1, 1130001 (2012)
  * (4) A. Borodin, I. Corwin and P. Ferrari, Comm. Pure Appl. Math. 67, 1129–1214 (2014)
  * (5) V.Dotsenko, Universal Randomness, Physics-Uspekhi, 54(3), 259 (2011);
Statistical properties of one-dimensional directed polymers in a random
potential, in Order, Disorder and Criticality, vol 5 (World Scientific, 2018);
arXiv:1703.04305

  * (6) D. Amit, H. Sompolinsky and H. Gutfreund, Ann.Phys. 173 30 (1987)
  * (7) V.S.Dotsenko, Introduction to the Theory of Spin Glasses and Neural Networks (World Scientific, 1994)