# Term-Sets Can Be Strong Document Identifiers For Auto-Regressive Search
Engines

Peitian Zhang1, Zheng Liu2, Yujia Zhou1, Zhicheng Dou1, Zhao Cao2
1: Renmin University, Beijing, China
2: Huawei Tech Co. Ltd., Shenzhen, China
<EMAIL_ADDRESS>Corresponding author

###### Abstract

Auto-regressive search engines emerge as a promising paradigm for next-gen
information retrieval systems. These methods work with Seq2Seq models, where
each query can be directly mapped to the identifier of its relevant document.
As such, they are praised for merits like being end-to-end differentiable.
However, auto-regressive search engines also confront challenges in retrieval
quality, given the requirement for the exact generation of the document
identifier. That’s to say, the targeted document will be missed from the
retrieval result if a false prediction about its identifier is made in any
step of the generation process. In this work, we propose a novel framework,
namely AutoTSG (Auto-regressive Search Engine with Term-Set Generation), which
is featured by 1) the unordered term-based document identifier and 2) the set-
oriented generation pipeline. With AutoTSG, any permutation of the term-set
identifier will lead to the retrieval of the corresponding document, thus
largely relaxing the requirement of exact generation. Besides, the Seq2Seq
model is enabled to flexibly explore the optimal permutation of the document
identifier for the presented query, which may further contribute to the
retrieval quality. AutoTSG is empirically evaluated with Natural Questions and
MS MARCO, where notable improvements can be achieved against the existing
auto-regressive search engines.

##  1 Introduction

Search engines, standing as the most representative form of information
retrieval, are fundamentally important to real-world applications like web
search, question answering, advertising, and recommendation (Karpukhin et al.,
2020; Lewis et al., 2021). Nowadays, they are also regarded as a critical tool
for the augmentation of large language models (LLMs), where external
information can be introduced to facilitate faithful and knowledge-grounded
generation (Komeili et al., 2021; Nakano et al., 2022; Wang et al., 2023). A
typical search engine calls for the utilization of two basic modules:
representation and indexing. For example, a sparse retrieval system uses
lexicon-based representations and an inverted index, while a dense retrieval
system is based on latent embeddings and an ANN index (Robertson and Zaragoza,
2009; Malkov and Yashunin, 2018).

Recently, a new type of method, the auto-regressive search engines, e.g.,
GENRE (Cao et al., 2021), DSI (Tay et al., 2022), emerge as a promising
direction for next-gen information retrieval (Metzler et al., 2021b). Briefly
speaking, the auto-regressive search engine allocates each document with a
sequential ID, called document identifier111In this work, we focus on document
identifiers based on explicit features, e.g., text. Unlike those based on
implicit features, such identifiers are directly compatible with the pre-
trained language models and do not depend on an addition embedding model and
hierarchical clustering.; e.g., n-grams within the document (Bevilacqua et
al., 2022), or semantic IDs acquired by hierarchical clustering (Tay et al.,
2022). Next, it learns to predict the document identifier for an input query
with a Seq2Seq model. Compared with traditional retrieval methods, the
autoregressive search engine is praised for being end-to-end differentiable:
instead of optimizing each module individually, the entire retrieval pipeline
can be optimized by the Seq2Seq learning and does not need a separate index
(Metzler et al., 2021b; Tay et al., 2022).

Despite the preliminary progresses achieved by recent works (Tay et al., 2022;
Cao et al., 2021; Bevilacqua et al., 2022; Wang et al., 2022), we argue that
the auto-regressive search is much more challenging than typical Seq2Seq
problems. Particularly, auto-regressive search engines require the exact
generation of identifier for the targeted document. If incorrect predictions
are made in any steps of the generation process, it will falsely produce the
identifier of a different document, which causes the missing of targeted
document in the final retrieval result (a.k.a. false pruning). Furthermore,
considering that the sequence length of the identifier must be large enough to
guarantee the discrimination of all documents, the generation process has to
go through a large number of decoding steps. If we regard the generation
process as sequential decision making, the probability of false pruning will
gradually accumulate step-by-step and finally result in a bad retrieval
quality. A derived problem from false-pruning is that the permutation of
document identifier becomes critical. While retrieving, the targeted document
will be falsely pruned if the prefix of its predefined identifier is bad, i.e.
relatively hard to generate conditioned on the query. However, it can be
successfully retrieved as long as its prefix is sufficiently good. We
introduce the following concrete example to better illustrate the above
points.

Figure 1:  (A) The targeted document (D3) is falsely pruned given the
predefined sequential identifier. (B) The targeted document (D3) is retrieved
via the highlighted permutation on top of AutoTSG.

###### Example 1

We use a sample query from Natural Questions, "Who cooks for the president of
the United States", for discussion. We have three candidate documents from
Wikipedia: D1, D2, and D3. D3 is the target as it contains the correct answer.
Each document is identified by keywords from its title and first paragraph.
All document identifiers are organized by a prefix tree (trie) as Figure 1
(A).

We apply the Seq2Seq model from GENRE (Cao et al., 2021) for our example. As
we may observe, D3 is falsely pruned in the first step, as the generation
likelihood $P(\textit{cristeta}|\textbf{Q})$ is lower than the other
candidates, “white” and “executive”. We may also derive two interesting
observations from this example. Firstly, if the identifier of D3 can be re-
ordered as “executive, chef, cristeta, comerford”, it will achieve a much
higher generation likelihood -12.8, making D3 successfully retrieved (greater
than -16.5 from D1, and -31.0 from D2). This reflects the importance of
identifier’s permutation. Secondly, although the document identifier is
problematic regarding the presented query, it can be favorable to other
queries, like “who is cristeta comerford?”. In other words, there is probably
no universally favorable permutation of identifier for the document.

Our Method. We propose a novel framework, namely AutoTSG, to overcome the
above challenges in auto-regressive search engines. The proposed framework is
highlighted by two featured designs. First of all, the document identifier is
no longer one (or a few) predefined sequence, but a set of unordered terms
from the document, known as the unordered term-based identifier. Any
permutation of the term-set will be a valid identification for the
corresponding document; that is, the targeted document can be retrieved if any
permutation of its identifier is generated by the Seq2Seq model. Thus, it will
be more tolerable and largely relaxed for the requirement of exact generation.
Secondly, given the change of document identifier, the Seq2Seq model is
switched to perform the set-oriented generation: it aims to generate the
included terms of the document identifier, rather than exactly predict any
required sequences. With such flexibility, the Seq2Seq model may explore the
“favorable permutation” of the document identifier given different queries.
This model is easier to train and therefore contributes to a better retrieval
quality for the generation process.

Back to our example (Figure 1 B.), the terms white, house, executive, chef,
etc., are selected as the document identifier of D3. Therefore, all
permutations, like “white, house, …, executive, chef”, “white, house, …,
cristeta, comerford”, etc., will be valid identification of D3. Given the
query “Q: who cooks for the president of the United States”, the Seq2Seq
explores the entire term space ($\bigcup_{\text{Terms}}$), where it figures
out “executive” to be the most probable (with the highest generation
likelihood) and valid (belongs to a valid document) term to decode. In the
second step, it further explores the term space. This time, it selects “chef”
given its high likelihood and validity. Note that although combinations like
“executive, director”, “executive, manager” may also give large enough
likelihood, they will be reckoned invalid since they do not belong to any
existing document identifiers. The Seq2Seq model will keep on exploring; with
the permutation “executive, chef, white, house, …” generated (other terms are
omitted due to limited space), document D3 is successfully retrieved for the
query.

While the framework is upgraded in terms of document identifier and generation
pipeline, it still needs to conquer several challenges in order to achieve
competitive retrieval performance, including how to select appropriate terms
for a document identifier, how to explore the optimal permutation of document
identifier while ensuring its validity, how to learn the Seq2Seq model
effectively to perform the exploration task. In our work, we develop the
following techniques to address these challenges. (1) The matching-oriented
term selection for constructing document identifiers, which determines a
concise and discriminative set of terms for each document based on the
importance to query-document matching. (2) The constrained greedy search,
which explores the optimal identifier permutation while ensuring its validity.
(3) Likelihood-adapted Seq2Seq learning: as there is no predefined permutation
of document identifier, the Seq2Seq learning is performed with iteratively
updated objectives determined by concrete query and model snapshot.

In summary, the main technical contributions of this paper are highlighted by
the following points.

  * •

We propose a novel framework AutoTSG for auto-regressive search engines. The
proposed method is featured by its unordered term-based document identifier
and the set-oriented generation pipeline. With both designs, the requirement
for exact generation of the identifier is relaxed, and the Seq2Seq model is
enabled to explore its favorable identifier permutation.

  * •

We devise three technical components which jointly contribute to AutoTSG’s
retrieval performance: 1) the matching-oriented term selection, 2) the
constrained greedy search for document identifier’s generation, and 3) the
likelihood-adapted Seq2Seq learning.

  * •

We conduct comprehensive empirical analyses on top of popular evaluation
benchmarks: Natural Questions and MSMARCO. Experimental results verify the
effectiveness of AutoTSG, as notable improvements in retrieval quality can be
achieved over the existing auto-regressive search engines under a variety of
experimental settings.

##  2 Related Work

Document retrieval has been extensively studied for a long time. Conventional
methods resort to lexical representations and inverted indexes, where query-
document relationships can be estimated by relevance functions, like BM25
(Robertson and Zaragoza, 2009). With the development of pre-trained language
models (Devlin et al., 2019), dense retrieval becomes another popular option
(Karpukhin et al., 2020; Xiong et al., 2021; Izacard et al., 2021), where the
relevance is measured by embedding similarity. Apart from these well-
established methods, the auto-regressive search engines emerge as a promising
direction (Metzler et al., 2021a; Tay et al., 2022; Cao et al., 2021). These
methods treat document retrieval as a Seq2Seq problem, where the document
identifier can be directly generated for the query. The document identifier is
one of the most decisive factors for the corresponding methods (Tay et al.,
2022; Bevilacqua et al., 2022): the Seq2Seq model must generate the exact same
identifier for the targeted document, and the ranking of the document is
determined by the generation likelihood of its identifier. Based on different
formations, the current works can be roughly partitioned into three groups: 1)
the semantic ID based methods (Tay et al., 2022; Mehta et al., 2022), 2) the
atomic ID based methods (Tay et al., 2022; Zhou et al., 2022), 3) the explicit
term based methods (Cao et al., 2021; De Cao et al., 2022; Bevilacqua et al.,
2022). By comparison, the last category is more compatible with pre-trained
language models, as the explicit terms are directly perceptible. Thus, our
proposed framework also adopts such features. As discussed, the existing works
call for the exact generation of the document identifier, which is a too
challenging requirement. It is a major cause for the false pruning of the
relevant document, which severely restricts the retrieval quality. In light of
such a deficiency, our work reformulates the document identifier based on
unordered terms; together with the set-oriented generation pipeline, it
achieves substantial improvements in retrieval quality.

##  3 Methodology

An auto-regressive search engine usually constitutes two basic components (Tay
et al., 2022; Bevilacqua et al., 2022). One is a document identifier schema -
a unique identifier set $\mathcal{I}(D)$ (e.g., a family of sequences) needs
to be assigned to each document $D$. The other one is a Seq2Seq model
$\boldsymbol{\Theta}(\cdot)$. For an input query $Q$, the Seq2Seq model
estimates the relevance between $Q$ and $D$ based on the following generation
likelihood:

$\mathrm{Rel}(Q,D)=\mathrm{Agg}\left(\left\\{\prod\nolimits_{i=1}^{|I|}\Pr(I_{i}\mid
I_{<i},Q;\boldsymbol{\Theta}):~{}I\in\mathcal{I}(D)\right\\}\right),$ (1)

where $I$ is an element of $\mathcal{I}(D)$; $\Pr(I_{i}\mid
I_{<i},Q;\boldsymbol{\Theta})$ indicates the generation probability of $i$-th
element $I_{i}$ given the prefix $I_{<i}$, the query $Q$, and the Seq2Seq
model $\boldsymbol{\Theta}$. The function $\mathrm{Agg}(\cdot)$ stands for
aggregation of the likelihood for sequences within $\mathcal{I}(D)$. Many of
the existing works (Tay et al., 2022; Cao et al., 2021; Wang et al., 2022)
make use of one single sequence for document identification. In those cases,
$\mathrm{Agg}(\cdot)$ will simply be the identity function
$\mathbbm{1}(\cdot)$. In SEAL (Bevilacqua et al., 2022), the whole collection
of n-grams from the document are used as the identifier, where an intersective
scoring function is introduced to aggregate the generation likelihood of
different n-grams. With the above formulation, the document retrieval can be
made through a sequence generation workflow: the Seq2Seq model generates the
most likely identifiers for the given query via a beam search, then the
corresponding documents, ranked by their generation likelihoods, are returned
as the retrieval result.

Although AutoTSG also relies on a Seq2Seq model for document retrieval as
existing methods, it is fundamentally different in terms of document
identification. Particularly, it uses a set of $N$ unordered terms to form the
document identifier: $\mathcal{T}(D)=\\{t_{1},\dots,t_{N}\\}$. With the
assumption that $\mathcal{T}(D)$ is unique within the corpus, any permutation
of $\mathcal{T}(D)$ is unique as well. Then, we define that $D$ is retrieved
if one permutation of $\mathcal{T}(D)$ is generated by the Seq2Seq model; and
if multiple permutations are generated for a single document, we take their
maximum likelihood: $\mathrm{Agg}(\cdot)\leftarrow\mathrm{max}(\cdot)$.

In the remaining part of this section, we will introduce corresponding
components of AutoTSG: (1) the document identifier schema: how to decide the
terms in the document identifier in the pre-processing stage (Section 3.1) and
how to generate it in the prediction stage (Section 3.2). (2) the Seq2Seq
generation model: how to train the document identifier generation model
(Section 3.3).

###  3.1 Matching-oriented Term Selection For Document Identifier

The selection of terms in a document identifier is performed based on the
following principles. Firstly, the number of terms $N$ should be sufficiently
large that all documents within the corpus can be uniquely identified, i.e.,
no collision of identifiers between two different documents. Secondly, the
term selection needs to be concise as well. As mentioned, longer sequences are
more prone to false prediction. Thirdly, the selected terms must sufficiently
capture the semantic information within the document; by doing so, the query-
document relevance can be precisely reflected by the generation likelihood.
With the above principles, we introduce the following mechanism for term
selection, where representative terms are selected depending on their
importance to the query-document matching.

Each document $D$ is partitioned into a list of terms in the first place:
$[t^{D}_{1},\dots,t^{D}_{L}]$. Then, the term importance is acquired through
the estimation pipeline in Eq. (2).

$\mathcal{M}([t^{D}_{1},\dots,t^{D}_{L}])\xRightarrow{1.}[\boldsymbol{e}^{D}_{1},\dots,\boldsymbol{e}^{D}_{L}]\xRightarrow{2.}[\sigma(W^{T}\boldsymbol{e}^{D}_{1}),\dots,\sigma(W^{T}\boldsymbol{e}^{D}_{L})]\xRightarrow{3.}[w^{D}_{1},\dots,w^{D}_{L}]$
(2)

The encoding model $\mathcal{M}(\cdot)$ is applied to transform each term
$t_{i}$ into its latent representation
$\boldsymbol{e}^{D}_{i}\in\mathbb{R}^{d\times 1}$. Following the common
practice, we leverage BERT (Devlin et al., 2019) for this operation. The
latent representation is further mapped into real-valued importance
$w^{D}_{i}$ via linear transformation $W\in\mathbb{R}^{d\times 1}$ and ReLU
activation $\sigma(\cdot)$. Following the existing practice on semantic
matching (Mallia et al., 2021; Gao et al., 2021; Lin and Ma, 2021), the
selection modules, i.e., $\mathcal{M}$ and $W$, are learned to optimize the
semantic matching between query and document. Particularly, given the
annotations $\mathcal{A}=\\{\langle
Q,D^{+},\\{D_{i}^{-}\\}_{i=1}^{M}\rangle\\}$ where $D^{+}$ is the relevant
document to $Q$, and $\\{D_{i}^{-}\\}_{i=1}^{M}$ are $M$ irrelevant documents
to $Q$, the following InfoNCE loss is optimized for estimating term
importance:

$\min\left(-\log\frac{\exp(\sum_{t^{Q}_{i}=t^{D^{+}}_{j}}w^{Q}_{i}w^{D^{+}}_{j}/\tau)}{\exp(\sum_{t^{Q}_{i}=t^{D^{+}}_{j}}w^{Q}_{i}w^{D^{+}}_{j}/\tau)+\sum_{m=1}^{M}\exp(\sum_{t^{Q}_{i}=t^{D_{m}^{+}}_{j}}w^{Q}_{i}w^{D_{m}^{+}}_{j}/\tau)}\right).$
(3)

In this place, $\tau$ is the temperature; “$t^{Q}_{i}=t^{D}_{j}$” indicates
the constraint which regularizes $t^{Q}_{i}$ and $t^{D}_{j}$ to be the same
term. By minimizing the above loss, large importance scores can be learned for
the terms which bridge the matching between query and its relevant document.
We select the top-$N$ terms as the identifier:
$\mathcal{T}(D)\leftarrow\\{t_{i}^{D}:w^{D}_{i}\in\text{top-}N\left(\\{w^{D}_{i}\\}_{i=1}^{L}\right)\\}$.
The same number of selection is applied to all documents. We choose the
smallest value of $N$ while ensuring the discrimination; e.g., for a moderate-
scale corpus like NQ320K, $N=12$ is already enough to have all documents
discriminated.

###  3.2 Constrained Greedy Search

Given the unordered term-based identifier, the relevance between query and
document can be measured in the following naive way: firstly, the generation
likelihood is enumerated for all possible permutations of the document
identifier ($N!$); then, the highest value is used as the measurement of
relevance. Since the naive method is intractable, we need to design a
mechanism where the language model may generate plausible document identifiers
and their near optimal permutations for the given query, to ensure acceptable
generation efficiency. The search mechanism needs to satisfy the following two
properties: optimality and validity. First of all, it is expected to produce
the document identifier of the highest generation likelihood. Knowing that the
optimal solution is intractable, we resort to the greedy algorithm for its
approximation. Particularly, we set the following local optimality while
making stepwise term selection. At the $i$-th decoding step, given the
collection of previously generated terms $\\{I_{<i}^{*}\\}_{K}$ ($K$: the beam
size), the decoding result of the current step ($\\{I_{\leq i}^{*}\\}_{K}$) is
made w.r.t. the following condition:

$\\{I_{\leq i}^{*}\\}_{K}\leftarrow\underset{I_{\leq
i}}{\text{argtop-}K}\left(\left\\{\prod\nolimits_{j=1,\dots,i}\Pr(I_{j}\mid
I_{<j};Q;\boldsymbol{\Theta})\right\\}\right).$ (4)

In other words, we greedily select the terms which give rise to the top-$K$
generation likelihood until the current step. Apart from the optimality, the
generated term set must also correspond to valid document identifiers. To
guarantee the validity, for each prefix $I_{<i}\in\\{I_{<i}^{*}\\}_{K}$, we
regularize the selection of $I_{i}$ with the following set-difference based
constraint:

$1.~{}I_{i}\notin\\{I_{1},\dots,I_{i-1}\\}\wedge 2.~{}\exists
D:I_{i}\in\mathcal{T}(D)/\\{I_{1},\dots,I_{i-1}\\}.$ (5)

The first condition prevents the selection of a repetitive term given the
current prefix $I_{<i}$; while the second condition ensures that the newly
selected term and its prefix, i.e., $\\{I_{1},\dots,I_{i-1}\\}\cup I_{i}$,
will always constitute a subset of a valid document identifier.

Since it’s time consuming to verify the constraint case-by-case, we implement
the following data structure for efficient generation. We maintain an inverted
index during generation, pointing from each prefix $I_{<i}$ to the documents
whose identifiers constitute the super sets of $\\{I_{1},\dots,I_{i-1}\\}$.
The union is computed for all such identifiers:
$\boldsymbol{X}=\bigcup\\{\mathcal{T}(D^{\prime}):~{}\\{I_{1},\dots,I_{i-1}\\}\subseteq\mathcal{T}(D^{\prime})\\}$,
and let the difference set $\boldsymbol{X}/\\{I_{1},\dots,I_{i-1}\\}$ be the
feasible scope for next-step decoding. Note that at the begining of decoding,
all terms in all document identifiers are valid. With the selection of
$I_{i}$, the inverted index is updated accordingly, with the invalid documents
pruned from the entry of $I_{<=i}$. As most of the documents will be pruned
for one specific prefix within very few steps, the above data structure helps
to achieve a high running efficiency for the constrained greedy search.

###  3.3 Likelihood-Adapted Sequence-to-Sequence Learning

Unlike the existing works where ground-truth sequences are predefined, the
document identifier becomes a term-set in AutoTSG. Since one document is
retrieved if any permutation of its identifier is generated, it is
straightforward to make random sampling from the $N!$ permutations, so that
the Seq2Seq learning can be conducted. However, the sampled sequence will
probably be inconsistent with the decoding order of constrained greedy search
(unfavorable to recall), nor will it likely be the one with the highest
generation likelihood of document identifier (unfavorable to the final
ranking).

To facilitate the recall of relevant documents from the generation process and
have them better ranked in the final retrieval result, we expect the Seq2Seq
model to learn from the permutations of document identifiers. Therefore, we
propose a new training workflow named likelihood-adapted Seq2Seq learning. The
proposed method adopts an iterative pipeline. In each iteration, it samples
the favorable permutation of document identifier as the learning objective.
Specifically, given the current Seq2Seq model $\boldsymbol{\Theta}^{t-1}$, the
query, and the previously generated terms $I_{<i}$, the top-K sampling is
performed to the difference set of $\mathcal{T}(D)$ and $I_{<i}$ according to
the following distribution:

$P(I_{i})\propto\Pr(I_{i}\mid
I_{<i};Q;\boldsymbol{\Theta}^{t-1}),~{}I_{i}\in\mathcal{T}(D)/\\{I_{0},\dots,I_{i-1}\\}.$
(6)

With the sampling of multiple candidate sequences $\boldsymbol{I}$, the one
with the highest overall likelihood is selected as the learning objective for
the current iteration ($I^{t}$):

$I^{t}\leftarrow\mathrm{argmax}\left(\left\\{\prod\nolimits_{i=1,\dots,N}\Pr(I_{i}\mid
I_{<i};Q;\boldsymbol{\Theta}^{t-1}):~{}I\in\boldsymbol{I}\right\\}\right).$
(7)

With this new objective, the Seq2Seq model is updated as
$\boldsymbol{\Theta}^{t}$ via another round of learning. The above process,
i.e., the likelihood-dependent permutation sampling and the Seq2Seq learning,
is iteratively conducted until a desirable model is produced.

There are still two remaining issues. One is the initial order of permutation.
Although there are different options, e.g., purely randomized permutation, or
sampling from a pre-trained LM (T5, GPT), we find that ordering the terms by
their estimated importance in term selection brings forth the best empirical
performance. The other one is about the convergence. Although the sampled
permutation is always changing, we keep track of the Seq2Seq model’s retrieval
accuracy on a hold-out validation set. In our experiment, it merely takes two
iterations to reach the convergence of accuracy growth.

##  4 Experiments

The experimental studies are performed to explore the following research
questions. RQ 1\. AutoTSG’s impact on retrieval quality against the existing
auto-regressive search engines. RQ 2\. The impact from each of the technical
designs in AutoTSG. RQ 3\. The impact on running efficiency.

###  4.1 Settings

Datasets. We leverage two popular datasets which are widely used by previous
evaluations for auto-regressive search engines. One is the NQ320k dataset (Tay
et al., 2022; Bevilacqua et al., 2022) curated from Natural Questions
(Kwiatkowski et al., 2019), including 320k training queries and 7830 testing
queries. Each query is corresponding to a Wikipedia article containing its
answer. The other one is the MS300k dataset (Chen et al., 2023; Zhou et al.,
2022) curated from MSMARCO (Nguyen et al., 2016), which contains 320k
documents, 360k training queries, and 772 testing queries.

Metrics. Two evaluation metrics are introduced to measure the retrieval
quality at the top-$K$ cut-off: MRR@K and Recall@K, which focus on the
perspective of ranking and recall, respectively.

Implementations. Some critical facts about the implementations are presented
as follows. Backbone LM. We leverage T5 (Raffel et al., 2020) as our backbone,
which is consistent with the majority of previous works (Chen et al., 2023;
Mehta et al., 2022; Wang et al., 2022). T5 (base) is the default option, yet
T5 (large) is also explored. Term Granularity. We treat each single word,
separated by space, as one term. Since a term may contain multiple tokens, we
append a “,” to the last token, which indicates the termination of term. (The
same treatment can be applied to handle other granularities, e.g., n-grams.)
Data Augmentation. Following the previous works (Wang et al., 2022; Mehta et
al., 2022; Zhou et al., 2022), we leverage DocT5 (Cheriton, 2019) to generate
pseudo training queries. Beam Size. The beam size is 100 throughout the
experiments, which is also same as previous works. We’ve uploaded our
implementations to an anonymous repo 222https://github.com/namespace-
Pt/Adon/tree/AutoTSG for the reference of more details.

Table 1: Overall evaluations on NQ320k. $\dagger$ denotes the results copied from (Wang et al., 2022). Method | MRR@10 | MRR@100 | Recall@1 | Recall@10 | Recall@100
---|---|---|---|---|---
BM25$\dagger$ | – | 0.211 | 0.151 | 0.325 | 0.505
DPR$\dagger$ | – | 0.366 | 0.287 | 0.534 | 0.732
GENRE | 0.653 | 0.656 | 0.591 | 0.756 | 0.814
DSI | 0.594 | 0.598 | 0.533 | 0.715 | 0.816
SEAL$\dagger$ | – | 0.655 | 0.570 | 0.800 | 0.914
Ultron | 0.726 | 0.729 | 0.654 | 0.854 | 0.911
NCI$\dagger$ | – | 0.731 | 0.659 | 0.852 | 0.924
AutoTSG | 0.757 | 0.760 | 0.690 | 0.875 | 0.932
Table 2: Overall evaluations on MS300k. Method | MRR@10 | MRR@100 | Recall@1 | Recall@10 | Recall@100
---|---|---|---|---|---
BM25 | 0.313 | 0.325 | 0.196 | 0.591 | 0.861
DPR | 0.424 | 0.433 | 0.271 | 0.764 | 0.948
GENRE | 0.361 | 0.368 | 0.266 | 0.579 | 0.751
DSI | 0.339 | 0.346 | 0.257 | 0.538 | 0.692
SEAL | 0.393 | 0.402 | 0.259 | 0.686 | 0.879
Ultron | 0.432 | 0.437 | 0.304 | 0.676 | 0.794
NCI | 0.408 | 0.417 | 0.301 | 0.643 | 0.851
AutoTSG | 0.484 | 0.491 | 0.359 | 0.766 | 0.907

Baselines. To analyze the effectiveness of AutoTSG, especially the proposed
formulation of document identifier and its generation workflow, we introduce a
diverse collection of auto-regressive search engines with different forms of
document identifier. GENRE (Cao et al., 2021): using titles; DSI (Tay et al.,
2022): using semantic IDs; SEAL (Bevilacqua et al., 2022): using n-grams and
FM index; Ultron (Zhou et al., 2022): using titles and urls; NCI (Wang et al.,
2022): enhancing DSI with data augmentation. Given the limitation of space, we
omit many of the repetitive comparisons with other conventional retrieval
methods, as they have been extensively analyzed in the above works.

###  4.2 Main Analysis

The overall evaluations on NQ320k and MS300k are shown in Table 1 and 2,
respectively. According to the experiment results, AutoTSG notably improves
the retrieval quality over the existing auto-regressive search engines. For
example, on NQ320k, it outperforms the strongest baseline by $+3.9\%$ and
$+2.4\%$ on MRR@100 and Recall@10; on MS300k, it also achieves the relative
improvements of $+12.3\%$ on MRR@100 and $+11.6\%$ on Recall@10 over the
baseline methods. In our detailed analysis, we’ll demonstrate that the new
formulation of document identifier and the corresponding generation workflow
are the main contributors to such advantages. Despite the overall advantages,
we may observe that the conventional approach DPR (Karpukhin et al., 2020)
leads to the highest recall@100 on MS300k. In fact, this observation reveals a
general challenge for the current auto-regressive search engines: it is easier
to achieve high ranking performances (reflected by MRR) thanks to the
expressiveness of Seq2Seq models, but comparatively difficult to achieve
equally competitive recall. Much of the reason is due to the aforementioned
false-pruning problem: once the document identifier is false predicted in any
step of the generation process, it is impossible for back-tracking (thus
unfavorable for recall); however, if the document can be returned by
generation, it will probably be ranked with a favorable position. Fortunately
with AutoTSG, we make a critical step-forward to mitigate the above problem:
it relaxes the requirement of exact generation, and enables the Seq2Seq model
to explore the optimal permutation of identifier w.r.t. the given query. Both
designs substantially improve the recall, and further expand the advantage on
ranking.

Besides the above overall evaluations, we present more detailed analysis
between the auto-regressive search engines in terms of their memorization and
generation capability. Particularly, the existing auto-regressive search
engines highly rely on the presence of training queries (Wang et al., 2022;
Zhou et al., 2022; Tay et al., 2022; Mehta et al., 2022): it is desirable to
provide each document identifier with sufficient training queries. By learning
to generate a document’s identifier with training queries, it will be much
easier to make exact generation of the document’s identifier for its testing
queries, given that the queries associated with the same document are somewhat
similar. In other words, the existing auto-regressive models are more of
memorization rather than generalization, which is unfavorable to handling a
massive or constantly changing corpus. To evaluate AutoTSG’s impact for the
corresponding capabilities, we design the experiment where the corpus is
partitioned into two halves: with training queries preserved for 50% of the
documents (Seen), and with training queries removed for the other 50% of the
documents (Unseen). Given the above setting, the Seq2Seq model is prevented
from memorizing the document identifiers on the unseen half during the
training stage. According to the experiment results in Table 3 and 4: AutoTSG
marginally outperforms the baselines on the “seen” half; nevertheless, its
advantage is significantly magnified on the “unseen” half. As discussed,
AutoTSG is largely relaxed from the requirement of exact generation, making it
is less restricted by memorization; and together with the flexibility to
explore optimal identifier permutation, it becomes more generalizable when
dealing with unseen documents.

Table 3: Analysis of retrieval quality w.r.t. seen and unseen documents on NQ320k. | Seen (50%) | Unseen (50%) | Seen+Unseen (100%)
---|---|---|---
Method | MRR@10 | Recall@10 | MRR@10 | Recall@10 | MRR@10 | Recall@10
GENRE | 0.763 | 0.869 | 0.138 | 0.187 | 0.448 | 0.558
DSI | 0.713 | 0.802 | 0.011 | 0.040 | 0.360 | 0.428
Ultron | 0.782 | 0.891 | 0.300 | 0.383 | 0.471 | 0.570
NCI | 0.751 | 0.842 | 0.050 | 0.159 | 0.393 | 0.459
AutoTSG | 0.809 | 0.900 | 0.466 | 0.654 | 0.552 | 0.700
Table 4: Analysis of retrieval quality w.r.t. seen and unseen documents on MS300k. | Seen (50%) | Unseen (50%) | Seen+Unseen (100%)
---|---|---|---
Method | MRR@10 | Recall@10 | MRR@10 | Recall@10 | MRR@10 | Recall@10
GENRE | 0.361 | 0.579 | 0.150 | 0.312 | 0.196 | 0.411
DSI | 0.339 | 0.538 | 0.030 | 0.075 | 0.171 | 0.298
Ultron | 0.432 | 0.676 | 0.197 | 0.246 | 0.313 | 0.492
NCI | 0.408 | 0.643 | 0.034 | 0.082 | 0.260 | 0.412
AutoTSG | 0.484 | 0.766 | 0.390 | 0.588 | 0.391 | 0.642

###  4.3 Ablation Studies

The ablation studies are performed for each influential factor based on NQ320k
dataset as Table 5.

Identifiers. We compare the proposed formulation of document identifier, the
one based on unordered terms (term-set), with the conventional sequence-based
formulation; that is, the terms are ordered as a sequence by their estimated
importance (empirically more competitive than other sequence orders). It can
be observed that the retrieval quality can be notably improved for both recall
and ranking metrics on top of the proposed formulation. As discussed, the
generation task is largely relaxed with term-set: there are no longer
requirements to follow the exact sequence order; in contrast, any permutations
of the identifier may lead to the retrieval of the corresponding document, and
the Seq2Seq model may flexibly explore the favorable permutation depending on
the presented query.

Term Selection. We compare three alternative term selection methods. Random:
purely randomized selection (from the document); Title: terms within the
title; Matching Oriented: the default option used by AutoTSG. We may derive
the following observations from the experiment. Firstly, there are huge
differences between different selection methods, which verifies the importance
of term selection. Secondly, although directly making use of title is a strong
baseline (also a common practice in many works (Cao et al., 2021; De Cao et
al., 2022; Zhou et al., 2022)), the matching-oriented approach is more
effective: by estimating the term’s importance based on its utility to query-
document matching, the selected terms will not only facilitate the
identifier’s generation (considering the higher relevance to the potential
queries), but also better reflect the relationship between query and document.

Table 5: Ablation studies on NQ320k. The default settings of AutoTSG are marked with *. Factor | Setting | MRR@10 | MRR@100 | Recall@1 | Recall@10 | Recall@100
---|---|---|---|---|---|---
Identify | Sequence | 0.733 | 0.736 | 0.668 | 0.848 | 0.904
Term Set∗ | 0.757 | 0.760 | 0.690 | 0.875 | 0.932
Select | Random | 0.628 | 0.631 | 0.568 | 0.739 | 0.811
Title | 0.743 | 0.745 | 0.677 | 0.856 | 0.915
Matching Oriented∗ | 0.757 | 0.760 | 0.690 | 0.875 | 0.932
Learning | Non-adaptive | 0.743 | 0.745 | 0.671 | 0.865 | 0.927
Likelihood Adapted∗ | 0.757 | 0.760 | 0.690 | 0.875 | 0.932
Initialize | Random | 0.723 | 0.727 | 0.652 | 0.854 | 0.925
Likelihood | 0.715 | 0.718 | 0.643 | 0.844 | 0.916
Importance∗ | 0.757 | 0.760 | 0.690 | 0.875 | 0.932
Q-Gen | Ultron w.o. QG | 0.670 | 0.672 | 0.605 | 0.779 | 0.845
NCI w.o. QG | – | 0.679 | 0.602 | 0.802 | 0.909
AutoTSG w.o. QG | 0.707 | 0.710 | 0.635 | 0.836 | 0.916
AutoTSG∗ | 0.757 | 0.760 | 0.690 | 0.875 | 0.932
Scale | DSI large | 0.613 | 0.620 | 0.553 | 0.733 | 0.835
SEAL large | – | 0.677 | 0.599 | 0.812 | 0.909
NCI large | – | 0.734 | 0.662 | 0.853 | 0.925
AutoTSG large | 0.766 | 0.768 | 0.697 | 0.882 | 0.938

Learning. We compare our proposed likelihood-adapted sequence-to-sequence
learning with its non-adaptive variation: the document identifier’s
permutation is fixed as its initialization. Note that the constrained greedy
search is still maintained in the testing stage for the non-adaptive baseline,
despite that it relies on a fixed permutation in the training stage. It can be
observed that our proposed learning method indeed contributes to the retrieval
quality. Such an advantage is easy to comprehend, considering that the
training objective (the permutation of document identifier) can be iteratively
adapted to keep consistent with the plausible permutations in the testing
stage.

Initialization. We make evaluations for the three alternative initialization
approaches for the Seq2Seq learning. 1) Random: the selected terms are
randomly permuted; 2) Likelihood: the selected terms are permuted based on the
generation likelihood of a pre-trained T5; 3) Importance: the selected terms
are permuted by their estimated importance (default option). We can observe
that the initialization turns out to be another critical factor for the
Seq2Seq learning: the importance-based method is notably stronger than the
other two baselines. This is probably because the importance-based
initialization presents “a more plausible permutation” of document identifier,
that is, easier to be generated and better reflect the query-document
relationship. Besides, considering the iterative workflow of the learning
process, the initialization will not only determine the current training
objective, but also largely influence the final permutation where the Seq2Seq
model will converge.

Query Generation. Query generation is a widely used data augmentation strategy
to enhance auto-regressive search engines (Wang et al., 2022; Zhou et al.,
2022; Mehta et al., 2022). It is also found helpful in AutoTSG (by using the
off-the-shelf DocT5 (Cheriton, 2019)), whose impact is explored in the
ablation studies. As expected, the retrieval quality is substantially improved
on top of query generation. Note that the relative improvement of AutotSG is
mainly from the proposed formulation of document identifier and its generation
workflow, rather than the extra data augmentation. When query generation is
disabled, AutoTSG maintains its advantage over the baselines.

Model Scaling. The scaling-up of backbone Seq2Seq model is another common
approach for the enhancement of auto-regressive search engines. In our
experiment, empirical improvements may also be observed when we switch to a
T5-large backbone. Meanwhile, it maintains the advantage when other baselines
are scaled up as well.

Table 6: Efficiency analysis on NQ320k. Method | Memory | Query Latency (s)
---|---|---
| (MB) | bs = 10 | bs = 100
GENRE | 27 | 0.05 | 0.57
DSI | 12 | 0.03 | 0.21
SEAL | 210 | 0.32 | 3.14
Ultron | 27 | 0.05 | 0.57
NCI | 12 | 0.03 | 0.21
AutoTSG | 35 | 0.06 | 0.69

Efficiency. The running efficiency is evaluated in Table 6. Particularly, we
measure the memory consumption for hosting the entire corpus; we also measure
the time cost (query latency) with different beam sizes. We may observe that
most of the approaches incur very close memory and time costs given their
similar workflow. However, one exception is SEAL (Bevilacqua et al., 2022),
where much more memory and running time are resulted from the usage of FM
index.

##  5 Conclusion

In this work, we propose a novel framework for auto-regressive search engines.
The new framework is featured by two designs: 1) the unordered term-based
document identifier, 2) the set-oriented generation pipeline. With both
features, the challenge of generating document identifier becomes
significantly relaxed, where the Seq2Seq model may flexibly explore the
favorable permutation of document identifier. To support high-quality document
retrieval, we devise three key techniques for the proposed framework: the
matching-oriented term selection, the constrained greedy search for the
document identifier and its optimal permutation, the likelihood-adapted
Seq2Seq learning. With comprehensive experiments, we empirically verify the
following technical contributions: 1) the proposed framework achieves
substantial improvements over the existing auto-regressive search engines,
especially in terms of generalizability, where superior retrieval quality can
be achieved; 2) all of the proposed technical designs bring forth notable
positive impacts to the retrieval quality; and 3) the improvements are
achieved with very little extra cost on running efficiency.

## References

  * Bevilacqua et al. [2022] Michele Bevilacqua, Giuseppe Ottaviano, Patrick Lewis, Scott Yih, Sebastian Riedel, and Fabio Petroni.  Autoregressive search engines: Generating substrings as document identifiers.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=Z4kZxAjg8Y.
  * Cao et al. [2021] Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni.  Autoregressive entity retrieval.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=5k8F6UU39V.
  * Chen et al. [2023] Xiaoyang Chen, Yanjiang Liu, Ben He, Le Sun, and Yingfei Sun.  Understanding differential search index for text retrieval.  _CoRR_ , abs/2305.02073, 2023.  doi: 10.48550/arXiv.2305.02073.  URL https://doi.org/10.48550/arXiv.2305.02073.
  * Cheriton [2019] David R. Cheriton.  From doc2query to doctttttquery.  2019\.
  * De Cao et al. [2022] Nicola De Cao, Ledell Wu, Kashyap Popat, Mikel Artetxe, Naman Goyal, Mikhail Plekhanov, Luke Zettlemoyer, Nicola Cancedda, Sebastian Riedel, and Fabio Petroni.  Multilingual autoregressive entity linking.  _Transactions of the Association for Computational Linguistics_ , 10:274–290, 2022.  doi: 10.1162/tacl_a_00460.  URL https://aclanthology.org/2022.tacl-1.16.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Jill Burstein, Christy Doran, and Thamar Solorio, editors, _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186. Association for Computational Linguistics, 2019\.  doi: 10.18653/v1/n19-1423.  URL https://doi.org/10.18653/v1/n19-1423.
  * Gao et al. [2021] Luyu Gao, Zhuyun Dai, and Jamie Callan.  COIL: revisit exact lexical match in information retrieval with contextualized inverted list.  In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tür, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , pages 3030–3042. Association for Computational Linguistics, 2021\.  doi: 10.18653/v1/2021.naacl-main.241.  URL https://doi.org/10.18653/v1/2021.naacl-main.241.
  * Izacard et al. [2021] Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave.  Unsupervised dense information retrieval with contrastive learning, 2021\.  URL https://arxiv.org/abs/2112.09118.
  * Karpukhin et al. [2020] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick S. H. Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih.  Dense passage retrieval for open-domain question answering.  In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 6769–6781. Association for Computational Linguistics, 2020.  doi: 10.18653/v1/2020.emnlp-main.550.  URL https://doi.org/10.18653/v1/2020.emnlp-main.550.
  * Komeili et al. [2021] Mojtaba Komeili, Kurt Shuster, and Jason Weston.  Internet-augmented dialogue generation.  In _Annual Meeting of the Association for Computational Linguistics_ , 2021.
  * Kwiatkowski et al. [2019] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur P. Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov.  Natural questions: a benchmark for question answering research.  _Trans. Assoc. Comput. Linguistics_ , 7:452–466, 2019.  doi: 10.1162/tacl\\_a\\_00276.  URL https://doi.org/10.1162/tacl_a_00276.
  * Lewis et al. [2021] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela.  Retrieval-augmented generation for knowledge-intensive nlp tasks, 2021\.
  * Lin and Ma [2021] Jimmy Lin and Xueguang Ma.  A few brief notes on deepimpact, coil, and a conceptual framework for information retrieval techniques.  _CoRR_ , abs/2106.14807, 2021.  URL https://arxiv.org/abs/2106.14807.
  * Malkov and Yashunin [2018] Yu A Malkov and Dmitry A Yashunin.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(4):824–836, 2018.
  * Mallia et al. [2021] Antonio Mallia, Omar Khattab, Torsten Suel, and Nicola Tonellotto.  Learning passage impacts for inverted indexes.  In Fernando Diaz, Chirag Shah, Torsten Suel, Pablo Castells, Rosie Jones, and Tetsuya Sakai, editors, _SIGIR ’21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual Event, Canada, July 11-15, 2021_ , pages 1723–1727. ACM, 2021\.  doi: 10.1145/3404835.3463030.  URL https://doi.org/10.1145/3404835.3463030.
  * Mehta et al. [2022] Sanket Vaibhav Mehta, Jai Prakash Gupta, Yi Tay, Mostafa Dehghani, Vinh Q. Tran, Jinfeng Rao, Marc Najork, Emma Strubell, and Donald Metzler.  DSI++: updating transformer memory with new documents.  _CoRR_ , abs/2212.09744, 2022.  doi: 10.48550/arXiv.2212.09744.  URL https://doi.org/10.48550/arXiv.2212.09744.
  * Metzler et al. [2021a] Donald Metzler, Yi Tay, Dara Bahri, and Marc Najork.  Rethinking search.  _ACM SIGIR Forum_ , 55(1):1–27, 2021a.
  * Metzler et al. [2021b] Donald Metzler, Yi Tay, Dara Bahri, and Marc Najork.  Rethinking search: making domain experts out of dilettantes.  _SIGIR Forum_ , 55(1):13:1–13:27, 2021b.  doi: 10.1145/3476415.3476428.  URL https://doi.org/10.1145/3476415.3476428.
  * Nakano et al. [2022] Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Eloundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman.  Webgpt: Browser-assisted question-answering with human feedback, 2022\.
  * Nguyen et al. [2016] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng.  MS MARCO: A human generated machine reading comprehension dataset.  In Tarek Richard Besold, Antoine Bordes, Artur S. d’Avila Garcez, and Greg Wayne, editors, _Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, December 9, 2016_ , volume 1773 of _CEUR Workshop Proceedings_. CEUR-WS.org, 2016.  URL https://ceur-ws.org/Vol-1773/CoCoNIPS_2016_paper9.pdf.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67, 2020.  URL http://jmlr.org/papers/v21/20-074.html.
  * Robertson and Zaragoza [2009] Stephen E. Robertson and Hugo Zaragoza.  The probabilistic relevance framework: BM25 and beyond.  _Found. Trends Inf. Retr._ , 3(4):333–389, 2009\.  doi: 10.1561/1500000019.  URL https://doi.org/10.1561/1500000019.
  * Tay et al. [2022] Yi Tay, Vinh Q. Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Prakash Gupta, Tal Schuster, William W. Cohen, and Donald Metzler.  Transformer memory as a differentiable search index.  _CoRR_ , abs/2202.06991, 2022.  URL https://arxiv.org/abs/2202.06991.
  * Wang et al. [2023] Boxin Wang, Wei Ping, Peng Xu, Lawrence McAfee, Zihan Liu, Mohammad Shoeybi, Yi Dong, Oleksii Kuchaiev, Bo Li, Chaowei Xiao, Anima Anandkumar, and Bryan Catanzaro.  Shall we pretrain autoregressive language models with retrieval? a comprehensive study, 2023.
  * Wang et al. [2022] Yujing Wang, Yingyan Hou, Haonan Wang, Ziming Miao, Shibin Wu, Hao Sun, Qi Chen, Yuqing Xia, Chengmin Chi, Guoshuai Zhao, Zheng Liu, Xing Xie, Hao Allen Sun, Weiwei Deng, Qi Zhang, and Mao Yang.  A neural corpus indexer for document retrieval.  _CoRR_ , abs/2206.02743, 2022.  doi: 10.48550/arXiv.2206.02743.  URL https://doi.org/10.48550/arXiv.2206.02743.
  * Xiong et al. [2021] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=zeFrfgyZln.
  * Zhou et al. [2022] Yujia Zhou, Jing Yao, Zhicheng Dou, Ledell Wu, Peitian Zhang, and Ji-Rong Wen.  Ultron: An ultimate retriever on corpus with a model-based indexer, 2022\.


# StereoSpike: Depth Learning with a Spiking Neural Network

Ulysse Rançon 1, 2, Javier Cuadrado-Anibarro 1, Benoit R. Cottereau 1,
Timothée Masquelier 1

###### Abstract

Depth estimation is an important computer vision task, useful in particular
for navigation in autonomous vehicles, or for object manipulation in robotics.
Here we solved it using an end-to-end neuromorphic approach, combining two
event-based cameras and a Spiking Neural Network (SNN) with a slightly
modified U-Net-like encoder-decoder architecture, that we named _StereoSpike_.
More specifically, we used the Multi Vehicle Stereo Event Camera Dataset
(MVSEC). It provides a depth ground-truth, which was used to train StereoSpike
in a supervised manner, using surrogate gradient descent. We propose a novel
readout paradigm to obtain a dense analog prediction –the depth of each pixel–
from the spikes of the decoder. We demonstrate that this architecture
generalizes very well, even better than its non-spiking counterparts, leading
to state-of-the-art test accuracy. To the best of our knowledge, it is the
first time that such a large-scale regression problem is solved by a fully
spiking network. Finally, we show that low firing rates (<10%) can be obtained
via regularization, with a minimal cost in accuracy. This means that
StereoSpike could be efficiently implemented on neuromorphic chips, opening
the door for low power and real time embedded systems.

##  1 Introduction

Depth is an important feature of the surrounding space whose estimation finds
its place in various tasks across many different fields. Potential
applications can be as diverse as object manipulation in robotics or collision
avoidance for autonomous vehicles during navigation. In humans, depth
processing is extremely well developed and relies on monocular (e.g.,
occlusions, perspectives or motion parallax) and binocular (retinal
disparities) visual cues (Cutting and Vishton 1995). This processing consumes
very little energy as the visual system encodes retinal information under the
form of action potential, or _spikes_ and it is believed that the brain only
requires about 20 Watts to function (Mink, Blumenschine, and Adams 1981). Over
the last years, it has motivated the development of numerous bio-inspired
approaches based on neuromorphic sensors and spiking neural networks to
process depth in embedded systems.

Dynamic Vision Sensors (DVS) have recently gathered the interest of scientists
and industrial actors, thanks to a growing number of research paper explaining
how to process their output (Gallego et al. 2020). Reasons for this recent
popularity are the very high dynamic range, excellent temporal resolution and
unrivaled energy efficiency of these event cameras, hence making them
especially suitable in automotive scenarios with strong energy and latency
constraints. Similarly, as retinal ganglion cells in the animal retina, their
pixels asynchronously emit an action potential (i.e., a _spike_ , or _event_)
whenever the change in log-luminance at this location since the last event,
reaches a threshold.

Spiking Neural Networks (SNNs) are a good fit for DVSs, as they can leverage
the sparsity of their output event streams. Implemented on dedicated chips
such as Intel Loihi (Davies et al. 2018), IBM TrueNorth (Akopyan et al. 2015)
or Brainchip Akida (Vanarse et al. 2019), these models could become a new
paradigm for ultra-low power computation in the coming years. In addition,
SNNs maintain the same level of biological plausibility as silicon retinae,
making them new models of choice among computational neuroscientists. SNNs
have recently attracted the deep learning community since the breakthrough of
Surrogate Gradient (SG) learning (Neftci, Mostafa, and Zenke 2019) (Zenke et
al. 2021), which enabled the training of networks with back-propagation
despite the non-differentiable condition for spike emission. While SNNs
generally remain less accurate than their analog counterpart (i.e., Analog
Neural Networks or ANNs), the gap in accuracy is decreasing, even on
challenging problems like ImageNet (Fang et al. 2021b).

In this context, we propose an ultra-low power spiking neural network for
depth estimation, capable of dense depth predictions even at places without
events and performing on par with the current state-of-the-art. Despite the
dynamic nature of DVS data, we show that the task of depth estimation from
such neuromorphic event streams can be treated as a non-temporal task;
therefore, our model is purely stateless in the sense that we reset all
neurons to a membrane potential of zero at each timesteps. This feature
certainly does not take advantage of the temporal processing abilities of
SNNs, but reveals itself to decrease even further the computational and energy
footprint of our model.

In section 2, we introduce a few related works that inspired our approach. We
explain our methodology in section 3, including the data pre-processing,
network architecture, and training details. In section 4, we compare our
method with prior studies in terms on performances. We also show that
StereoSpike surpasses equivalent analog Neural Networks (ANNs) with similar
architectures, both in terms of performances and energy-efficiency.

##  2 Related Work

Deep learning approaches for depth estimation have had a long tradition on the
timescale of modern deep learning techniques. Initial methods were based on
luminance-field data from traditional frame-based cameras, either in mono- or
binocular setups. The model in (Eigen and Fergus 2015) was the first
successful multi-scale architecture designed for depth estimation from RGB
images, and was consequently followed by advances based on similar approaches
(Mayer et al. 2016) (Li and Snavely 2018) (Godard, Aodha, and Brostow 2017).

Consistently with the recent interest of the scientific community in event
cameras, a few works have successfully tackled the problem with neuromorphic
data. Historically, several groups have used bio-inspired approaches such as
Spiking Neural Networks (SNNs), in a very hardware-oriented direction, but not
in a “deep learning” setting. For instance, the authors of (Risi, Calabrese,
and Indiveri 2021) implemented a spike-based algorithm on a FPGA to regress
low-resolution depth maps on a small size dataset. Furthermore, (Haessig et
al. 2019) proposed a SNN for processing depth from defocus (DFD); this work
targeted neuromorphic chips that enabled depth recover at full resolution, but
the reconstruction was not dense.

Following the latter, (Zhu et al. 2019) presented a neural network that
jointly predicted camera pose and per-pixel disparity from stereo inputs.
However, their reconstructed depth maps remained sparse as they restricted
their analyses to pixels where events occurred. The work in (Tulyakov et al.
2019) addressed this problem and pushed even further the state-of-the-art on
indoor scenarios thanks to 3D convolutions exploiting a specific event
embedding. In (Hidalgo-Carrio, Gehrig, and Scaramuzza 2020), dense metric
depth was recovered from only one camera, and showed very good performances
with a recurrent, monocular encoder-decoder architecture on outdoor sequences.

Another inspiration for our work has been the task of large-scale optical flow
regression from neuromorphic data, which is very similar to depth
reconstruction because it is also based on a large-scale image regression task
with the same dataset. Similarly, large-scale optical flow regression from
neuromorphic data has been an active area of research over the past few years,
and has seen the emergence of methods with growing hardware-friendliness. EV-
FlowNet (Zhu et al. 2018a), arguably considered as the precursor of encoder-
decoder models for optical flow reconstruction from event data, consisted in a
feedforward analog encoder-decoder architecture. As a direct sequel, the
hybrid model Spike-FlowNet (Lee et al. 2020) made the effort of using spiking
neurons in the encoder of a similar backbone, while maintaining the same
levels of performances. On one hand, in this approach, spiking neurons were
shown to be able of encoding abilities close to analog ones and at a reduced
computational cost. On the other hand, authors kept the remaining part of
their network analog, to counteract the lack of expressivity in SNNs. More
recently, the model proposed in (Paredes-Valles, Hagenaars, and de Croon 2021)
showed very good performances but it cannot be considered as a fully spiking
network because real-value intermediate predictions of the outputs were
reinjected within the network and mixed with binary spike tensors. In
addition, they upsampled low-scale representations with the bilinear
upsampling method, which breaks the binary spike constraint necessary for an
implementation on neuromorphic hardware. Nevertheless, it is the first success
in a large-scale regression task with a network that is spiking for its vast
majority.

So far, SNNs have been used for classification tasks like image recognition
(Fang et al. 2021b), object detection (Perot et al. 2020), or motion
segmentation (Parameshwara et al. 2021). Only a few works employed them for
regression tasks. A notable exception is (Gehrig et al. 2020), but they only
regressed 3 variables, while we propose here to regress the values of
$260\times 346=89960$ pixels.

##  3 Method

We used PyTorch and
SpikingJelly111https://github.com/fangwei123456/spikingjelly (Fang et al.
2020) as our main development libraries. PyTorch is currently one of the most
popular tools for deep learning and automatic differentiation, while
Spikingjelly is an open-source framework for spiking neural networks, based on
PyTorch and with rising popularity. Our codes will be released on GitHub upon
publication of the paper at the following address:
https://github.com/urancon/StereoSpike

###  3.1 Dataset

We trained and tested our network on the Multi Vehicle Stereo Event Camera
(MVSEC) dataset (Zhu et al. 2018b). Because of its large size and variability,
it has become one of the most popular benchmarks for depth reconstruction from
neuromorphic events. It was collected from two DAVIS346 cameras with a
resolution of $346\times 260$ pixels, mounted on several vehicles such as a
car, a motorbike or a drone. The depth groundtruth was provided by a Velodyne
Puck Lite LIDAR mounted on the top of the two event cameras and with a
sampling frequency of 20 Hz, hence providing a depth map every 50 ms.

We applied our method on the indoor_flying sequences of MVSEC, which was
recorded on a quadricopter flying inside a large room. We used the data splits
that were defined in (Zhu, Chen, and Daniilidis 2018) and (Tulyakov et al.
2019). We followed these previous works and removed take-off and landing parts
of the sequence, because they contained very noisy event streams and
inaccurate groundtruths.

###  3.2 Event Representation

We adopted a rather common representation of data: we binned all incoming
spikes on each pixel on a time window of a given length, typically 50 ms.
Furthermore, we accumulated spikes for each polarity in a different channels.
Because there are two polarities, the input tensor had a shape of
$(2,Height,Width)$ and contained positive integers, corresponding to the
number of spikes of each polarity that showed up at each position of the scene
during the time window. We further refer to this format as _spike histograms_
or _spike frames_ interchangeably.

Many ANN approaches normalize this kind of input tensor (e.g. divide by the
maximum number of spike count) for an easier-to-learn distribution of data and
better generalization. We believe that this operation is not adapted to
neuromorphic hardware, and can lead to non-integer number of spikes in the
normalized input tensor. For this reason, we prefer feeding raw spike frames
directly to our network.

Finally, we enhanced the input data with a temporal context by concatenating
$n$ subsequent frames channel-wise. As a result, the final input tensor has a
shape of $(n\times 2,H,W)$.

###  3.3 Architecture

Our model was based on a U-Net backbone (Ronneberger, Fischer, and Brox 2015)
consisting of an encoder, a bottleneck and a decoder whose non-linearities
(activation functions) were replaced by spiking neurons. We used the
Integrate-and-Fire (IF) model with a threshold potential of $v_{thresh}=1.0$
and $v_{reset}=0.0$.

Figure 1: Detailed architecture of StereoSpike. Its encoder contains one or
two branches (depending on the modality), each for a different DVS camera. The
output of both branches are combined with a sum function, and further
processed through a bottleck consisting of 2 chained SEW-Resblocks. As a
result, the tensor out of these residual layers is composed of integers in
range [0, 4]. This latent representation is progressively upsampled by decoder
layers and whose outputs are summed with same-level encoder spike tensors,
leading to integer values in range [0, 3]. In parallel, prediction synapses
from different scales directly project to output I-neurons whose potentials
bear the final prediction. The numbers indicate the size of channel dimension
for each spike volume. Best viewed in color.

Downsampling in the encoder was performed by 2-strided convolutions, which
divided the spatial resolution by 2 while doubling the channel resolution. The
bottleneck consisted in 2 SEWResBlocks (Fang et al. 2021a) following each
other and with $ADD$ connect function.

Because transposed convolutions are known to generate checkerboard artifacts
(Odena, Dumoulin, and Olah 2016), we rather used nearest neighbor (NN)
upsampling followed by a convolution. Contrarily to bilinear upsampling, we
believe NN to be neuromorphic hardware friendly, because it essentially keeps
integer spike counts in the upsampled volume. In terms of biological
plausibility, it can be viewed as a single neuron at low scale projecting
synapses towards several higher-scale neurons.

In addition, all layers in our network did not use a bias term nor Batch
Normalization (BatchNorm) because adding constant biases is costly on
neuromorphic hardware. Furthermore, they are not biologically plausible.

The output of the network was carried by the potentials of a pool of non-leaky
neurons with an infinite threshold. Before each inference and like all neurons
in the network, their membrane potentials were set to $0$. One problem of SNNs
is their lack of expressivity, since they can only update the membrane
potentials of output neurons with discrete weighted spikes. With synapses
coming from the full scale level of the encoder only, the model would always
predict a “mean depth image” learned from the natural statistics of depth
scenes: small depth values at the bottom and high values at the top of the
prediction. To counteract this effect, we increased the number of spikes
generated by lower levels (i.e. lower scales) of the network. Essentially,
depth prediction layers consisted in nearest neighbor upsampling followed by
convolution; they were the same as the upsampling layers in the decoder,
except that they upsampled spike tensors directly up to the full, original
scale.

###  3.4 Loss Function

Similarly as in (Hidalgo-Carrio, Gehrig, and Scaramuzza 2020), we used a
combination of a multiscale regression loss with a multiscale regularization
loss. Noting $R=\hat{D}-D$ the residual between the groundtruth depth map and
intermediary $i$, the first term can be written as:

$L_{regression}=\frac{1}{n}\sum_{i}(\sum_{u}(R(u))^{2}-\frac{1}{n^{2}}(\sum_{u}R(u))^{2})$
(1)

where $n$ is the number of valid groundtruth pixels u. With the same
notations, the regularization loss is computed with:

$L_{smooth}=\frac{1}{n}\sum_{i}\sum_{u}|\nabla_{x}R_{s}(u)|+|\nabla_{y}R_{s}(u)|$
(2)

According to (Hidalgo-Carrio, Gehrig, and Scaramuzza 2020), the minimization
of this term encourages smooth depth changes as well as sharp depth
discontinuities in the depth map prediction, hence helping the network to
represent objects that stand out of the background of the scene (e.g., because
they are closer), while respecting its overall topology. Finally, we weighted
both terms with a factor $\lambda$ in the total loss:

$L_{tot}=L_{regression}+\lambda L_{smooth}$ (3)

We used a value of $0.5$ for $\lambda$, which was determined empirically.

###  3.5 Training Procedure

Learning of parameter values in our model was done using surrogate gradient
learning (Neftci, Mostafa, and Zenke 2019), as implemented in Spikingjelly
Python library (Fang et al. 2020). We used $\arctan$ surrogate function for
all IF spiking neurons.

Because our network is feed-forward and only processes one step for inference,
we trained it with regular back-propagation, not Back-Propagation Through Time
(BPTT) and on the shuffled dataset. We adopted the following procedure: 1)
initialize all potentials (including output) to zero, 2) forward pass a sample
or a batch of them, 3) calculate loss and back-propagate it, 4) update the
weights and 5) start again with a new sample.

As explained in subsection 3.2, the input tensor consisted in $n=5$ frames of
50 ms concatenated along channel dimension.

We used Adam optimizer (Kingma and Ba 2015) with $\beta_{1}=0.9$ and
$\beta_{2}=0.999$. We trained the network for 30 epochs with an initial
learning rate set to $2.10^{-4}$ and divided by 10 at epoch 8. Batch size was
set to 1 and we did not use any weight decay.

##  4 Experiments

###  4.1 Performances

Our model performances are almost as good as those obtained from DDES
(Tulyakov et al. 2019) (the current state of the art), which is a fully-
fledged ANN using 3D convolutions within a less general framework. In
addition, StereoSpike’s architecture is not specific to the estimation of
depth and could be used for any other large-scale regression task. StereoSpike
also performs better than TSES and CopNet, which by the way only predict depth
at places where there have been events. Please refer to Figure 2 for
qualitative visualizations of depth reconstructions obtained with our model
and to Table 1 for a quantitative comparison with previous works on the Mean
Depth Error (MDE), the most common metric used for characterizing depth
estimation on the MVSEC.

Table 1: Evaluation Mean Depth Error (MDE) in centimeters on several dataset splits of indoor_flying sequence. * indicates that the evaluation is done on the sparse groundtruth, i.e., only at pixels where events occurred Model | MDE [cm]
---|---
| Split 1 | Split 2 | Split 3
Tulyakov et al. (2019) | 16.7 | 29.4 | 27.8
Ours (Binocular) | 19.8 | 29.9 | 26.1
Ours (Monocular) | 20.4 | 30.0 | 25.0
TSES* | 36 | 44 | 36
CopNet* | 61 | 100 | 64
Figure 2: Qualitative comparison of our method with the current state-of-the-
art detained by (Tulyakov et al. 2019). Similarly to what they did in their
paper, we selected the same input frames and run our model to infer depth from
this data; Event groundtruth and other prediction images were borrowed from
their article. The top row corresponds to frame #1700 of indoor_flying3 and
frame #980 of indoor_flying1 sequences. The pixelated aspect of our
predictions comes from the Nearest-Neighbor interpolation in the prediction
layer from very-low to full scale. Even so, it can be seen that our fully
spiking network captures the scene just as well as a cutting edge ANN using a
heavy framework and 3D convolutions. Adapted from (Tulyakov et al. 2019).

In terms of MDE, performances obtained from the monocular and binocular
encoders are similar. This suggests that in addition to being –for the most
part– a non-temporal task, depth reconstruction from DVS data can be
efficiently tackled on a monocular setting. The predictions of our model are
mainly driven by monocular cues, but further work on the architecture could
leverage the presence of a second event camera.

###  4.2 StereoSpike - ANN comparison

A lesson learnt from our study and (Lee et al. 2020) is that SNNs can encode
information very optimally, even with binary values. While Spike-FlowNet used
ANNs to decode the latent space representation, we only use spiking neurons
without mixing real-valued intermediary predictions with integer spikes as in
(Paredes-Valles, Hagenaars, and de Croon 2021). SNNs can therefore efficiently
encode information as well as decode it, even for large scale regression
tasks.

In an attempt to compare our model with fully-fledged ANNs, we trained
equivalent ANN models. These models had a very similar architecture and output
paradigm consisting in a pool of I-neurons; however, and with the idea of
using the full power of analog models, we replaced IFNodes by common
activation functions, used Batch Normalization (BN) (Ioffe and Szegedy 2015)
and trainable biases in convolution layers. Very surprisingly, these analog
models showed much worse test metrics than their spiking counterparts (see
Table 2). It suggests that SNNs have better generalization abilities than
ANNs. To our knowledge, this is one of the few –if not the first– case of SNNs
outperforming equivalent ANNs.

Table 2: Comparative evaluation of our SNN vs equivalent ANN models on split 1 of indoor_flying sequence. For a given model, the train MDE, train loss and test loss are all sampled from the epoch yielding the best test MDE. Surprisingly, our fully spiking network surpasses by a large margin all of its analog relatives.  Model | MDE [cm] | Loss [au]
---|---|---
train | test | train | test
StereoSpike | 15.7 | 19.8 | 0.97 | 1.34
ANN (Tanh + BN) | 14.0 | 28.0 | 0.86 | 1.83
ANN (Sigmoid + BN) | 11.6 | 28.2 | 0.80 | 1.56
ANN (LeakyReLU + BN) | 12.3 | 34.9 | 0.74 | 1.69

The LeakyReLU ANN achieves the lowest training loss and among the lowest
training MDE, but has the worst test metrics by a large margin, hinting at a
strong overfitting. Network with step-like activations (Sigmoid, Tanh) show
better results on test sets and higher error on training sets, therefore
suggesting a reduced overfitting phenomenon. Finally, the StereoSpike network
–equivalent to an ANN with Heaviside step function as activation– achieves the
best test loss and MDE but also the worst training metrics, therefore
generalizing best, despite the absence of BN.

###  4.3 Computational Efficiency

In order to quantifiy the computational efficiency of our network, we report
in table 3 the firing rates of its layers, i.e., the density of intermediary
tensors computed during inference. Sparse volumes can be leveraged by
dedicated hardware capable of sparse computation, hence diminishing inference
time as well as energy consumption.

It appears that the firing rates of our best model grow as layers become
closer to the output I-neuron pool. We suggest that in this large-scale
regression task, a minimum number of pre-synaptic spikes preceding output
neurons is necessary to faithfully render the visual scene. Similarly, a
certain amount of spikes could be necessary to encode the information
contained in the input histograms.

To encompass this trade-off and estimate these minimal firing rates, we apply
a regularization loss term explained in (Pellegrini, Zimmer, and Masquelier
2021) and train a new binocular model on split 1. This secondary loss, which
we also call _quadratic spike penalization loss_ , penalizes the mean of the
squared spike tensor. Therefore, for a given layer containing K spiking units
whose output at time-step $n$ is $S_{k}[n]\in\\{0\ldots 4\\}$, it can be
defined as:

$\begin{split}L_{spikes}&=\frac{1}{2NK}\sum_{n}\sum_{k}S_{k}[n]^{2}\\\
&=\frac{1}{2K}\sum_{k}S_{k}[n]^{2}\end{split}$ (4)

Because the number of time-steps to do one prediction is $N=1$, as our model
is purely stateless/feedforward. We apply this loss on the tensor out of the
bottleneck –$out\\_rconv$– and on $out\\_addX$ tensors, which the resulting
tensors of the skip connections that are used by predictions layers at
different scales. Penalizing these tensors also indirectly affects the
activity of encoder layers, as their output conditions the density of same-
level decoder volumes because of the skip connections. Therefore, this
regularization is less aggressive than penalizing all intermediary tensors and
performances are less negatively affected.

We then evaluate the network trained with spike penalization on its test set
and compare obtained firing rates with our unconstrained model (see table 3).
The regularized model show a drastic decrease in activity, at a very
reasonable accuracy loss ($\sim$ 2 cm MDE). With these results, we can imagine
our model implemented efficiently on dedicated hardware.

Table 3: Detailed firing rates across layers of our network. $out\\_bottom$ and $out\\_conv$ spike tensors are the output of the encoders layers (Left or Right). $\\_combined$ and $\\_add$ spike tensors are sums of tensors at the end of encoders or skip connections. To be noted is that prediction layers take $\\_add$ tensors as inputs, and their synapses project to the final neuron pool. Layer | Density (%)
---|---
No Penalization | Penalization
$out\\_bottomL$ | 20.1 | 6.9
$out\\_conv1L$ | 7.6 | 7.1
$out\\_conv2L$ | 2.9 | 1.9
$out\\_conv3L$ | 4.4 | 2.3
$out\\_conv4L$ | 5.4 | 2.3
Left Encoder Mean | 8.1 | 4.1
$out\\_bottomR$ | 11.4 | 5.7
$out\\_conv1R$ | 3.8 | 2.1
$out\\_conv2R$ | 2.2 | 1.3
$out\\_conv3R$ | 1.2 | 1.5
$out\\_conv4R$ | 0.3 | 0.5
Right Encoder Mean | 3.8 | 2.2
$out\\_combined$ | 5.6 | 2.7
$out\\_resconv$ | 18.8 | 6.8
Bottleneck Mean | 12.2 | 4.8
$out\\_deconv4$ | 20.4 | 7.9
$out\\_add4$ | 24.9 | 11.5
$out\\_deconv3$ | 16.3 | 4.3
$out\\_add3$ | 20.7 | 7.5
$out\\_deconv2$ | 23.1 | 2.2
$out\\_add2$ | 32.7 | 11.4
$out\\_deconv1$ | 38.1 | 0.5
$out\\_add1$ | 62.5 | 12.1
Decoder Mean | 29.9 | 7.2
Model MDE [cm] | 19.8 | 22.1

#### Target Hardware

Our model has resolutely been developed in the philosophy of spiking neural
networks. As a result, it is essentially implementable on dedicated
neuromorphic hardware, such as Intel Loihi (Davies et al. 2018), IBM TrueNorth
(Akopyan et al. 2015) or Brainchip Akida 222https://brainchipinc.com/about/.
These chips can leverage the binarity and sparsity of spike tensors navigating
through the network. In addition, we believe that our model being feedforward
and requiring a reset on all of its neurons at each timestep is not a problem,
because resetting membrane potentials is actually less costly than applying a
leak. Therefore, statelesness can be seen as an advantage over recurrence in
spiking models with similar performances. However, we are aware that current
neuromorphic chips are initially designed for the implementation of stateful
units, and acknowledge that we do not leverage this feature. Consequently, we
believe that it rather fits to dedicated hardware for stateless models with
sparse activations quantized on 1 bit. This ideal target hardware does not
exist yet, but we emphasize that our class of model with binary activations
and less constrained weights provides a good compromise between Spiking Neural
Networks (SNNs) and Binary Neural Networks (BNNs).

#### Handling integer (non-binary spike counts)

Because of the sum operations present in residual layers of our architecture
and at skip connections, bottleneck and decoder tensors can contain integer
(non-binary) numbers of spikes. We explain here why we do not consider it as a
problem. On most digital neuromorphic chips, spikes are represented by multi-
bit messages containing destination and/or source addressing, and a few bits
for a graded-value payloads; this is the case for Loihi, see (Davies et al.
2021). In our case, the spike counts are included in $[0,4]$ and thus require
at most 3 bits to encode. For the chips that can only handle binary spikes, a
spike count of N could be handled by N serial binary spike operations

##  5 Conclusion

We have proposed StereoSpike, the first fully spiking, deep neural network
architecture for large scale regression task with sparse activity. The key is
expressivity and we tackle this problem by increasing the number of spikes
generated by deeper layers, with a pool of perfect integrator neurons bearing
the final prediction with their membrane potential. The same strategy could
presumably be used for other dense regression problems with SNNs, for example
optic flow prediction.

We have shown that depth estimation from DVS data can be brought back to a
stateless, static, non-temporal task. As a result, hardware implementations of
StereoSpike could consume substantially less than recurrent versions. However,
we are aware that our model neither takes advantage of this implicit
recurrence of SNNs to capture temporal dependencies, nor of the very high
temporal resolution of DVSs; these two aspects deserve investigation for
further improvement of our algorithm.

Finally, our experiments hint towards the fact that because of the constraint
on their output (i.e. binarity) SNNs might generalize better than their ANN
counterparts. Consequently, our work is yet another evidence that binary
encoding in latent space can represent input data as efficiently as real-
valued projections. This encourages more research in the field of SNNs and
neuromorphic computing in general, or Binarized Neural Networks (BNNs).

## References

  * Akopyan et al. (2015) Akopyan, F.; Sawada, J.; Cassidy, A.; Alvarez-Icaza, R.; Arthur, J.; Merolla, P.; Imam, N.; Nakamura, Y.; Datta, P.; Nam, G.-J.; Taba, B.; Beakes, M.; Brezzo, B.; Kuang, J. B.; Manohar, R.; Risk, W. P.; Jackson, B.; and Modha, D. S. 2015.  TrueNorth: Design and Tool Flow of a 65 mW 1 Million Neuron Programmable Neurosynaptic Chip.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 34(10): 1537–1557.
  * Cutting and Vishton (1995) Cutting, J.; and Vishton, P. 1995.  _Perceiving layout and knowing distances: The integration, relative potency, and contextual use of different information about depth_.  Academic Press.
  * Davies et al. (2018) Davies, M.; Srinivasa, N.; Lin, T.-H.; Chinya, G.; Lines, A.; Wild, A.; Wang, H.; and Mathaikutty, D. 2018.  Loihi: A Neuromorphic Manycore Processor with On-Chip Learning.  _IEEE Micro_ , PP: 1–1.
  * Davies et al. (2021) Davies, M.; Wild, A.; Orchard, G.; Sandamirskaya, Y.; Guerra, G. A. F.; Joshi, P.; Plank, P.; and Risbud, S. R. 2021.  Advancing Neuromorphic Computing With Loihi: A Survey of Results and Outlook.  _Proceedings of the IEEE_ , X: 1–24.
  * Eigen and Fergus (2015) Eigen, D.; and Fergus, R. 2015.  Predicting Depth, Surface Normals and Semantic Labels with a Common Multi-scale Convolutional Architecture.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , 2650–2658.
  * Fang et al. (2020) Fang, W.; Chen, Y.; Ding, J.; Chen, D.; Yu, Z.; Zhou, H.; Tian, Y.; and other contributors. 2020.  SpikingJelly.  https://github.com/fangwei123456/spikingjelly.  Accessed: 2021-08-01.
  * Fang et al. (2021a) Fang, W.; Yu, Z.; Chen, Y.; Huang, T.; Masquelier, T.; and Tian, Y. 2021a.  Deep Residual Learning in Spiking Neural Networks.  arXiv:2102.04159.
  * Fang et al. (2021b) Fang, W.; Yu, Z.; Chen, Y.; Masquelier, T.; Huang, T.; and Tian, Y. 2021b.  Incorporating Learnable Membrane Time Constant to Enhance Learning of Spiking Neural Networks.  In _IEEE/CVF ICCV_.
  * Gallego et al. (2020) Gallego, G.; Delbruck, T.; Orchard, G. M.; Bartolozzi, C.; Taba, B.; Censi, A.; Leutenegger, S.; Davison, A.; Conradt, J.; Daniilidis, K.; and Scaramuzza, D. 2020\.  Event-based Vision: A Survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 1–1.
  * Gehrig et al. (2020) Gehrig, M.; Shrestha, S. B.; Mouritzen, D.; and Scaramuzza, D. 2020.  Event-Based Angular Velocity Regression with Spiking Networks.  In _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 4195–4202.
  * Godard, Aodha, and Brostow (2017) Godard, C.; Aodha, O. M.; and Brostow, G. J. 2017.  Unsupervised Monocular Depth Estimation with Left-Right Consistency.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 6602–6611.
  * Haessig et al. (2019) Haessig, G.; Berthelon, X.; Ieng, S.-H.; and Benosman, R. 2019.  A Spiking Neural Network Model of Depth from Defocus for Event-based Neuromorphic Vision.  _Scientific Reports_ , 9: 3744.
  * Hidalgo-Carrio, Gehrig, and Scaramuzza (2020) Hidalgo-Carrio, J.; Gehrig, D.; and Scaramuzza, D. 2020.  Learning Monocular Dense Depth from Events.  _IEEE International Conference on 3D Vision.(3DV)_.
  * Ioffe and Szegedy (2015) Ioffe, S.; and Szegedy, C. 2015.  Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift.  _CoRR_ , abs/1502.03167.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A Method for Stochastic Optimization.  _CoRR_ , abs/1412.6980.
  * Lee et al. (2020) Lee, C.; Kosta, A.; Zhu, A. Z.; Chaney, K.; Daniilidis, K.; and Roy, K. 2020.  Spike-FlowNet: Event-based Optical Flow Estimation with Energy-Efficient Hybrid Neural Networks.  In _European Conference on Computer Vision_ , 366–382. Springer.
  * Li and Snavely (2018) Li, Z.; and Snavely, N. 2018.  MegaDepth: Learning Single-View Depth Prediction from Internet Photos.  _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2041–2050.
  * Mayer et al. (2016) Mayer, N.; Ilg, E.; Häusser, P.; Fischer, P.; Cremers, D.; Dosovitskiy, A.; and Brox, T. 2016.  A Large Dataset to Train Convolutional Networks for Disparity, Optical Flow, and Scene Flow Estimation.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 4040–4048.
  * Mink, Blumenschine, and Adams (1981) Mink, J. W.; Blumenschine, R. J.; and Adams, D. B. 1981.  Ratio of central nervous system to body metabolism in vertebrates: its constancy and functional basis.  _The American journal of physiology_ , 241(3): R203–R212.
  * Neftci, Mostafa, and Zenke (2019) Neftci, E. O.; Mostafa, H.; and Zenke, F. 2019.  Surrogate Gradient Learning in Spiking Neural Networks: Bringing the Power of Gradient-Based Optimization to Spiking Neural Networks.  _IEEE Signal Processing Magazine_ , 36(6): 51–63.
  * Odena, Dumoulin, and Olah (2016) Odena, A.; Dumoulin, V.; and Olah, C. 2016.  Deconvolution and Checkerboard Artifacts.  _Distill_.
  * Parameshwara et al. (2021) Parameshwara, C. M.; Li, S.; Fermüller, C.; Sanket, N. J.; Evanusa, M.; and Aloimonos, Y. 2021.  SpikeMS: Deep Spiking Neural Network for Motion Segmentation.  _CoRR_ , abs/2105.06562.
  * Paredes-Valles, Hagenaars, and de Croon (2021) Paredes-Valles, F.; Hagenaars, J.; and de Croon, G. 2021.  Self-Supervised Learning of Event-Based Optical Flow with Spiking Neural Networks.  arXiv:2106.01862.
  * Pellegrini, Zimmer, and Masquelier (2021) Pellegrini, T.; Zimmer, R.; and Masquelier, T. 2021.  Low-Activity Supervised Convolutional Spiking Neural Networks Applied to Speech Commands Recognition.  In _2021 IEEE Spoken Language Technology Workshop (SLT)_ , 97–103. IEEE.  ISBN 978-1-7281-7066-4.
  * Perot et al. (2020) Perot, E.; de Tournemire, P.; Nitti, D.; Masci, J.; and Sironi, A. 2020.  Learning to Detect Objects with a 1 Megapixel Event Camera.  In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M. F.; and Lin, H., eds., _Advances in Neural Information Processing Systems_ , volume 33, 16639–16652. Curran Associates, Inc.
  * Risi, Calabrese, and Indiveri (2021) Risi, N.; Calabrese, E.; and Indiveri, G. 2021.  Instantaneous Stereo Depth Estimation of Real-World Stimuli with a Neuromorphic Stereo-Vision Setup.  In _2021 IEEE International Symposium on Circuits and Systems (ISCAS)_ , 1–5.
  * Ronneberger, Fischer, and Brox (2015) Ronneberger, O.; Fischer, P.; and Brox, T. 2015.  U-Net: Convolutional Networks for Biomedical Image Segmentation.  _CoRR_ , abs/1505.04597.
  * Tulyakov et al. (2019) Tulyakov, S.; Fleuret, F.; Kiefel, M.; Gehler, P.; and Hirsch, M. 2019.  Learning an event sequence embedding for event-based deep stereo.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_.
  * Vanarse et al. (2019) Vanarse, A.; Osseiran, A.; Rassau, A.; and van der Made, P. 2019.  A Hardware-Deployable Neuromorphic Solution for Encoding and Classification of Electronic Nose Data.  _Sensors_ , 19(22).
  * Zenke et al. (2021) Zenke, F.; Bohté, S. M.; Clopath, C.; Comşa, I. M.; Göltz, J.; Maass, W.; Masquelier, T.; Naud, R.; Neftci, E. O.; Petrovici, M. A.; Scherr, F.; and Goodman, D. F. 2021.  Visualizing a joint future of neuroscience and neuromorphic engineering.  _Neuron_ , 109(4): 571–575.
  * Zhu et al. (2018a) Zhu, A.; Yuan, L.; Chaney, K.; and Daniilidis, K. 2018a.  EV-FlowNet: Self-Supervised Optical Flow Estimation for Event-based Cameras.  In _Proceedings of Robotics: Science and Systems_. Pittsburgh, Pennsylvania.
  * Zhu, Chen, and Daniilidis (2018) Zhu, A. Z.; Chen, Y.; and Daniilidis, K. 2018.  Realtime Time Synchronized Event-Based Stereo.  In Ferrari, V.; Hebert, M.; Sminchisescu, C.; and Weiss, Y., eds., _Computer Vision – ECCV 2018_ , 438–452. Cham: Springer International Publishing.
  * Zhu et al. (2018b) Zhu, A. Z.; Thakur, D.; Ozaslan, T.; Pfrommer, B.; Kumar, V.; and Daniilidis, K. 2018b.  The Multivehicle Stereo Event Camera Dataset: An Event Camera Dataset for 3D Perception.  _IEEE Robotics and Automation Letters_ , 3(3): 2032–2039.
  * Zhu et al. (2019) Zhu, A. Z.; Yuan, L.; Chaney, K.; and Daniilidis, K. 2019.  Unsupervised Event-Based Learning of Optical Flow, Depth, and Egomotion.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 989–997.

##  6 Acknowledgments

We would like to thank Amirreza Yousefzadeh for his help and expertise on
digital neuromorphic hardware. Our thanks also go to Wei Fang for his
wonderful SpikingJelly library, without which this work would not have been
possible. This research was supported by a grant from the ‘Agence Nationale de
la Recherche’ (ANR-16-CE37-0002-01, ANR JCJC 3D3M) awarded to Benoit
Cottereau.