# Submodular Optimization for Placement of Intelligent Reflecting Surfaces in
sensing systems

###### Abstract

Intelligent reflecting surfaces (IRS) are increasingly being investigated for
novel sensing applications for improving target estimation and detection.
While the optimization of IRS phase-shifts has been studied extensively, the
optimal placement of multiple IRS platforms for sensing applications is
relatively unexamined. In this paper, we focus on selecting optimized
locations of IRS platforms by considering a mutual information (MI)-based
criterion within the radar coverage area. We demonstrate the submodularity of
the MI criterion and then tackle the design problem by means of a constant-
factor approximation algorithm for submodular optimization. Numerical results
validate the proposed submodular optimization framework for optimal IRS
placement with the worst-case performance bounded to $1-1/e\approx 63\%$.

Index Terms—  Mutual information, non-line-of-sight radar, reconfigurable
intelligent surface, sensor placement, submodularity.

##  1 Introduction

The performance of wireless communications and sensing systems is severely
reduced in poor channel conditions and blockage [1, 2]. Recently, the
deployment of an intelligent reflecting surface (IRS) in the channel has been
investigated to enhance the system performance for blocked or high-noise
channels. In wireless communications, IRS has shown improvement in channel
capacity [3] and security [4], interference mitigation [5], and integrated
sensing and communications [1, 6, 7, 8, 9] and index modulation [10]. Similar
gains for radar systems have been demonstrated by optimizing IRS phase-shifts
for target estimation [11, 12, 13] and detection [14].

The optimal placement of IRSs in the coverage area plays a crucial role in the
performance of wireless systems. In IRS-aided wireless communications, there
have been studies on the optimal placement of IRS for optimizing the
throughput [15] and coverage [16]. In [17], the positioning of IRS platforms
in mobile user environments is achieved by imposing a desired minimum
threshold on the received power at users. In [18], the optimal distance
between the IRS and users in a device-to-device communications system was
derived analytically. Other placement criteria such as maximization of receive
signal-to-noise-ratio (SNR) [19] and blind zone improvement [20] have also
been considered for optimal IRS placement in millimeter-wave communications
scenario.

In general, prior works on IRS-aided radars keep the deployment location of
IRSs fixed and then focus on optimizing IRS phase-shifts. Recently, a near-
optimal placement was investigated in [21] to maximize the extended line-of-
sight (LoS) coverage provided by IRS platforms in an urban infrastructure.
However, this study treated the IRS platforms as specular surfaces [22],
thereby implying that the optimal IRS placement is determined irrespective of
the IRS phase-shifts.

Contrary to prior works, we address the problem of optimal placement of IRS
platforms tuned with predetermined phase-shifts. We employ the mutual
information (MI) between the channel state information (CSI) modified by IRS
phase-shifts and the received signal. Previous works have employed MI for
designing radar systems and signals [23, 24, 25, 26]. The IRS placement is a
combinatorial search problem, wherein the best placement for IRS platforms is
determined exhaustively from a finite set of possibilities. In the context of
sensor selection, combinatorial search has been avoided by relaxing the
problem to convex optimization [27]. Similarly, [28] formulates the selection
of the sensors as a knapsack problem for a distributed multiple-radar scenario
and solves it through greedy search with the Cramér-Rao lower bound (CRB) as a
performance metric. More recently, deep learning methods [29] have been
employed.

A framework for combinatorial optimization with optimality guarantees is,
indeed, of broad interest. We propose to employ submodular optimization to
obtain optimal placement of IRSs with a proper optimality guarantee.
Previously, sensor placement in [30, 31] has shown that submodular
optimization provides a greedy algorithm for constant-factor approximation of
the optimal solution. The approximation factor is dependent on the curvature
of the submodular function. The solution obtained at the worst-case execution
of the greedy algorithm is only up to a known factor of the optimal solution.
In this paper, we prove the monotonicity and submodularity of the MI-based
cost function for optimal IRS placement. Then, we develop a constant-factor
approximation algorithm to decide the IRS locations in a greedy manner by
exploiting the submodularity of the cost function. Our numerical experiments
illustrate the superiority of the IRS placements obtained via the greedy
algorithm in comparison to a random placement. We also compare our proposed
method with the theoretical lower bound on the worst-case performance of the
greedy algorithm.

Throughout this paper, we use bold lowercase and bold uppercase letters for
vectors and matrices, respectively. $(\cdot)^{\mathrm{H}}$ is the
vector/matrix Hermitian transpose; The determinant of a matrix is denoted by
$\operatorname{det}(.)$; the function $\textrm{diag}(.)$ returns the diagonal
elements of the input matrix, while $\textrm{Diag}(.)$ produces a diagonal
matrix with the same diagonal entries as its vector argument. Given a
reference set $\mathcal{A}$ and a subset $\mathcal{U}\subseteq\mathcal{A}$,
the absolute complement of $\mathcal{A}$ in relation to $\mathcal{U}$ is
denoted by $\mathcal{U}\setminus\mathcal{A}$. $|\mathcal{A}|$ is the
cardinality of the set $\mathcal{A}$. The positive semidefiniteness of the
matrix $\mathbf{A}$ is denoted by $\mathbf{A}\succeq 0$. Finally,
$\mathbf{A}=\left[\begin{array}[]{c|c|c}\mathbf{A}_{{}_{1}}&\ldots&\mathbf{A}_{{}_{M}}\end{array}\right]$
is a matrix made by stacking the blocks
$\mathbf{A}_{{}_{1}},\ldots,\mathbf{A}_{{}_{M}}$ horizontally.

##  2 Signal Model

Consider a multi-IRS-assisted radar system (Fig.1), which comprises a co-
located MIMO radar with $N_{t}$ transmit and $N_{r}$ receive antennas, each
arranged as uniform linear arrays (ULA) with inter-element spacing $d$. We
deploy $M$ IRS platforms indexed as IRS1, IRS2, $\ldots$, IRSM, each equipped
with $N_{m}$ reflecting elements arranged as ULA. Denote the $N_{t}\times 1$
vector of all transmit signals as
$\bm{x}(t)=[x_{{}_{1}}(t),\ldots,x_{{}_{N_{t}}}(t)]^{\top}$, where the
continuous-time signal transmitted from the $n$-th antenna at time instant $t$
is $x_{n}(t)$. The steering vectors of the radar transmitter, receiver, and
the $m$-th IRS are, respectively,

$\displaystyle\mathbf{a}_{t}(\theta)$
$\displaystyle=[1,e^{\textrm{j}\frac{2\pi}{\lambda}dsin\theta},\ldots,e^{\textrm{j}\frac{2\pi}{\lambda}d(N_{t}-1)sin\theta}]^{\top},$
(1) $\displaystyle\mathbf{a}_{r}(\theta)$
$\displaystyle=[1,e^{\textrm{j}\frac{2\pi}{\lambda}dsin\theta},\ldots,e^{\textrm{j}\frac{2\pi}{\lambda}d(N_{r}-1)sin\theta}]^{\top},and$
(2) $\displaystyle\mathbf{b}_{m}(\theta)$
$\displaystyle=[1,e^{\textrm{j}\frac{2\pi}{\lambda}d_{m}sin\theta},\ldots,e^{\textrm{j}\frac{2\pi}{\lambda}d_{m}(N_{m}-1)sin\theta}]^{\top},$
(3)

where $\lambda$ is the carrier wavelength; $d$ and $d_{m}$ are inter-element
spacings in the transceiver and IRS arrays, respectively. While $d$ is usually
set to be half of the carrier wavelength, $d_{m}$ is much smaller at the
subwavelength level. The IRS platforms are mounted on static platforms, whose
optimal locations we intend to determine later.

Denote the angle between the radar-target, radar–IRSm, and target-IRSm by
$\theta_{tr}$, $\theta_{ri,m}$, and $\theta_{ti,m}$, respectively. For the
multi-IRS aided radar the non-line-of-sight (NLoS) channels associated with
IRSm are
$\mathbf{H}_{ri,m}=\mathbf{b}_{m}(\theta_{ri,m})\mathbf{a}_{t}^{\top}(\theta_{ri,m})\in\mathbb{C}^{N_{m}\times
N_{t}}$ for radar-IRSm;
$\mathbf{H}_{it,m}=\mathbf{b}_{m}^{\top}(\theta_{ti,m})\in\mathbb{C}^{1\times
N_{m}}$ for IRSm-target;
$\mathbf{H}_{ti,m}=\mathbf{b}_{m}(\theta_{ti,m})\in\mathbb{C}^{N_{m}\times 1}$
for target-IRSm; and
$\mathbf{H}_{ir,m}=\mathbf{a}_{r}(\theta_{ri,m})\mathbf{b}^{\top}_{m}(\theta_{ri,m})\in\mathbb{C}^{N_{r}\times
N_{m}}$ for IRSm-radar paths. Assume the $k$-th passive element of IRSm is
tuned at the phase-shift $\phi{{}_{m,k}}\in[0,2\pi)$. Then, IRSm is
characterized by the phase-shift matrix

$\bm{\Phi}_{m}=\mathrm{Diag}\left([e^{\textrm{j}\phi_{{}_{m,1}}},\ldots,e^{\textrm{j}\phi_{{}_{m,N_{m}}}}]\right)\;\in\mathds{C}^{N_{m}\times
N_{m}}.$ (4)

Consider a target located at a distance $d_{tr}$ with respect to (w.r.t.) the
radar transceiver and complex reflectivity $\alpha_{{}_{{m}}}$, which depends
on the target size, target shape, and propagation path loss. The delay of the
signal propagated in the radar-IRSm-target-IRSm-radar path is
$\tau_{ritir,m}$. The line-of-sight (LoS) or radar-target-radar path is
obstructed (Fig. 1). The transmit signal backscattered by the target and
received by all $N_{r}$ receive antennas is

$\displaystyle\mathbf{y}(t)$
$\displaystyle=\sum_{m=1}^{M}\alpha_{{}_{m}}\mathbf{H}_{ir,m}\bm{\Phi}_{m}\mathbf{H}_{ti,m}\mathbf{H}_{it,m}\bm{\Phi}_{m}\mathbf{H}_{ri,m}\bm{x}(t-\tau_{ritir,m})$
$\displaystyle\hskip 142.26378pt+\mathbf{w}(t),\;\;\in\mathds{C}^{N_{r}\times
1}.$ (5)

where $\mathbf{w}(t)\sim\mathcal{CN}(\bm{0},\sigma^{2}\mathbf{I}_{N_{t}})$
denotes a stationary additive white Gaussian noise (AWGN). The relative time
gaps between any two multipath signals are very small in comparison to the
actual roundtrip delays, i.e.,
$\tau_{ritir,m}\approx\tau_{0}=\frac{2d_{tr}}{c}$ for $m\in\\{1,\ldots,M\\}$
and $c$ is the speed of light. Denote

$\mathbf{H}_{m}=\mathbf{H}_{ir,m}\bm{\Phi}_{m}\mathbf{H}_{ti,m}\mathbf{H}_{it,m}\bm{\Phi}_{m}\mathbf{H}_{ri,m}\in\mathbb{C}^{N_{r}\times
N_{t}}.$

We collect $N$ samples at the rate $1/T_{s}$ from $\mathbf{y}(t)$,
corresponding to the range cell of a notional target located at range
$d_{tr}$, The $N_{r}\times 1$ discrete-time received signal vector
$\mathbf{y}[n]=\mathbf{y}(nT_{s})$ is

$\mathbf{y}[n]=\sum_{m=1}^{M}\alpha_{{}_{m}}\mathbf{H}_{m}\mathbf{x}[n]+\mathbf{w}[n],\;n=0,\ldots,N-1,$
(6)

where $\mathbf{x}[n]=\mathbf{x}(\tau_{0}+nT_{s})\in\mathbb{C}^{N_{t}\times
1}$. The delay $\tau_{0}$ is aligned on-the-grid so that
$n_{0}=\tau_{0}/T_{s}$ is an integer [32]. Define
$\overline{\mathbf{H}}=\left[\begin{array}[]{c|c|c}\alpha_{{}_{1}}\mathbf{H}_{{}_{1}}^{\mathrm{H}}&\ldots&\alpha_{{}_{M}}\mathbf{H}_{{}_{M}}^{\mathrm{H}}\end{array}\right]^{\mathrm{H}}\in\mathbb{C}^{N_{t}\times
MN_{r}}$ and rewrite the discrete-time $N_{r}\times 1$ received signal vector
as

$\mathbf{y}[n]=\overline{\mathbf{H}}\mathbf{x}[n]+\mathbf{w}[n],\;n=0,\ldots,N-1,$
(7)

where $\mathbf{w}[n]$ is the circularly symmetric complex white Gaussian noise
vector, with a zero mean and variance $\sigma^{2}\mathbf{I}_{N_{r}}$. Stacking
$N$ discrete-time samples for all $N_{r}$ receiver antennas, the received
signal is the $N_{r}\times N$ matrix
$\mathbf{Y}=\left[\begin{array}[]{c|c|c}\mathbf{y}[0]&\ldots&\mathbf{y}[N-1]\end{array}\right]$.
i.e.,

$\mathbf{Y}=\overline{\mathbf{H}}\mathbf{X}+\mathbf{W},$ (8)

where
$\mathbf{X}=\left[\begin{array}[]{c|c|c}\mathbf{x}[0]&\ldots&\mathbf{x}[N-1]\end{array}\right]\in\mathbb{C}^{N_{t}\times
N}$ and
$\mathbf{W}=\left[\begin{array}[]{c|c|c}\mathbf{w}[0]&\ldots&\mathbf{w}[N-1]\end{array}\right]\in\mathbb{C}^{N_{r}\times
N}$.

In general, the placement of the IRS affects the SNR in the received signal.
In the next section, we investigate the optimal placement of the IRS platforms
based on a mutual information criterion.

IRS2IRS3IRS1TargetRadar$(\delta,\mu)$$((K_{r}-1)\delta,(K_{\theta}-1)\mu)$$((K_{{}_{r}}-1)\delta,\mu)$$(\delta,(K_{{}_{\theta}}-1)\mu)$$((K_{{}_{r}}-1)\delta,0)$$(\delta,0)$

Fig. 1: Simplified illustration of IRS-aided radar system and range-azimuth
bins $(r,\theta)\in\mathcal{A}$. When the LoS is blocked, the target is sensed
by the radar through the NLoS paths via the IRSs.

##  3 IRS Placement

Our criterion for optimizing the placement of IRS platforms is the MI

$\displaystyle\mathrm{I}\left(\mathbf{Y};\overline{\mathbf{H}}\bigg{|}\mathbf{X}\right)$
$\displaystyle=\mathcal{H}\left(\mathbf{Y}\bigg{|}\mathbf{X}\right)-\mathcal{H}\left(\mathbf{Y}\bigg{|}\overline{\mathbf{H}},\mathbf{X}\right)$
$\displaystyle=\mathcal{H}\left(\mathbf{Y}\bigg{|}\mathbf{X}\right)-\mathcal{H}\left(\mathbf{W}\right)$
(9)

where $\mathcal{H}(\cdot)$ is the Shannon entropy. Discretize the range-
azimuth plane of the radar coverage area, within which the IRSs are installed,
with $K$ ranges with a spacing of $\delta$ denoted by the set
$\mathcal{R}=\\{\delta,2\delta,\ldots,(K_{{}_{r}}-1)\delta\\}$ and with $K$
azimuth angles with a spacing of $\mu$ denoted by the set
$\mathcal{M}=\\{\mu,2\mu,\ldots,(K_{{}_{\theta}}-1)\mu\\}$; see Fig.1. Define
the range-azimuth set $\mathcal{A}$ as

$\displaystyle\mathcal{A}=\mathcal{R}\times\mathcal{M}=\left\\{(r,\theta)\mid
r\in\mathcal{R},\theta\in\mathcal{M}\right\\}.$ (10)

Denote the channel matrix contributed by the set of IRS platforms implemented
in two-dimensional (2-D) locations in the set $\mathcal{S}$ by
$\overline{\mathbf{H}}_{{}_{\mathcal{S}}}$. Then, we choose $\mathcal{S}$ by
solving the optimization problem

$\displaystyle\mathcal{P}_{1}:\leavevmode\nobreak\
\underset{\mathcal{S}\subseteq\mathcal{A}}{\textrm{maximize}}$
$\displaystyle\quad\mathrm{I}\left(\mathbf{Y};\overline{\mathbf{H}}_{{}_{\mathcal{S}}}\bigg{|}\mathbf{X}\right)$
subject to $\displaystyle\quad|\mathcal{S}|\leq M.$ (11)

Note that monotone submodular maximization is nontrivial only when
constrained. Our goal is to deploy at most $M$ IRS platforms in the radar
aperture $\mathcal{A}$. Theorem 1 below demonstrates the submodularity and
monotonicity of the objective function in (3), which we then employ for a
greedy algorithm with constant-factor approximation error to tackle the
problem.

######  Theorem 1.

The conditional entropy of $\mathbf{Y}$ given $\mathbf{X}$ is

$\displaystyle\mathcal{H}\left(\mathbf{Y}\bigg{|}\mathbf{X}\right)$
$\displaystyle=N\frac{\mathrm{ln}\left(\mathrm{det}(\overline{\mathbf{H}}\bm{\Sigma}_{{}_{\mathbf{X}}}\overline{\mathbf{H}}^{\mathrm{H}}+\sigma^{2}\mathbf{I})\right)}{2}$
$\displaystyle+\frac{NN_{r}}{2}\left(1+\mathrm{ln}(2\pi)\right),$ (12)

where
$\bm{\Sigma}_{{}_{\mathbf{X}}}=\mathds{E}\left\\{{\mathbf{X}\mathbf{X}^{H}}\right\\}$
is the total transmit power.

Considering that $\mathbf{y}[n]$ is a multivariate complex Gaussian
distribution, the conditional entropy is

$\displaystyle\mathcal{H}\left(\mathbf{Y}\bigg{|}\mathbf{X}\right)$
$\displaystyle=\mathcal{H}\left(\mathbf{y}[0],\ldots,\mathbf{y}[N-1]\bigg{|}\mathbf{x}[0],\ldots,\mathbf{x}[N-1]\right)$
$\displaystyle=\sum_{n=0}^{N-1}\mathcal{H}\left(\mathbf{y}[n]\bigg{|}\mathbf{x}[n]\right)=N\frac{\mathrm{ln}\left(\mathrm{det}(\overline{\mathbf{H}}\bm{\Sigma}_{{}_{\mathbf{X}}}\overline{\mathbf{H}}^{\mathrm{H}}+\sigma^{2}\mathbf{I})\right)}{2}$
$\displaystyle+\frac{NN_{r}}{2}\left(1+\mathrm{ln}(2\pi)\right),$ (13)

where the second equality follows from the chain rule for entropy and
independence of samples and the last equality is based on the entropy of a
multivariate Gaussian distribution [33].

For notational simplicity, denote $\bm{\Sigma}_{x}=P_{{}_{T}}\mathbf{I}$ and
$\mathbf{H}_{{}_{\mathcal{S}}}=\frac{\sqrt{P_{{}_{T}}}}{\sigma}\overline{\mathbf{H}}_{{}_{\mathcal{S}}}$,
and substituting the result of Theorem 1 in $\mathcal{P}_{1}$, we reach at the
equivalent problem

$\displaystyle\mathcal{P}_{2}:\leavevmode\nobreak\
\underset{\mathcal{S}\subseteq\mathcal{A}}{\textrm{maximize}}$
$\displaystyle\quad\mathrm{ln}\left(\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}+\mathbf{I})\right)$
subject to $\displaystyle\quad|\mathcal{S}|\leq M.$ (14)

We aim to tackle the problem $\mathcal{P}_{2}$ through submodular
optimization. To this end, we show in Theorem 2 below that the objective
function in $\mathcal{P}_{2}$ is monotonic and submodular.

######  Theorem 2.

The set function $f(\mathcal{S}):2^{\mathcal{S}}\rightarrow\mathds{R}$, where
$f(\mathcal{S})=\mathrm{ln}\left(\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}+\mathbf{I})\right)$
is a monotonically increasing and submodular function of the set
$\mathcal{S}$.

###### Proof.

For $\mathcal{S}\subseteq\mathcal{T}\subseteq\mathcal{A}$, a monotone set
function should satisfy

$f(\mathcal{S}\cup\mathcal{T})\geq f(\mathcal{S}).$ (15)

The function $f(\mathcal{S})$ is submodular if it satisfies the diminishing
returns property [31], i.e., $\forall\,u\in\mathcal{A}\setminus\mathcal{T}$,

$f(\mathcal{S}\cup\\{u\\})-f(\mathcal{S})\geq
f(\mathcal{T}\cup\\{u\\})-f(\mathcal{T}).$ (16)

In the context of our problem, we have

$\displaystyle f(\mathcal{S}\cup\mathcal{T})-f(\mathcal{S})$
$\displaystyle=\mathrm{ln}\left(\frac{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}^{\mathrm{H}}+\mathbf{I})}{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}+\mathbf{I})}\right)$
$\displaystyle=\mathrm{ln}\left(\frac{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}+\mathbf{I})}{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{I})}\right)$
$\displaystyle=\mathrm{ln}\left(\frac{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}+\mathbf{I})}{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{I})}\right)\geq
0,$ (17)

where the second equality follows from, without loss of generality,
$\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}=\left[\begin{array}[]{c|c}\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}&\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\end{array}\right]^{\mathrm{H}}$
leading to
$\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}\cup\mathcal{T}}}=\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}$.
Additionally, positive semidefiniteness of
$\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}$ i.e.
$\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}\succeq\bm{0}$
leads to
$\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}\succeq\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}$.
This proves the monotonicity of the set function $f(\mathcal{S})$. We define
$\mathbf{H}_{{}_{\mathcal{S}\cup\\{u\\}}}=\left[\begin{array}[]{c|c}\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}&\mathbf{H}_{{}_{\\{u\\}}}^{\mathrm{H}}\end{array}\right]^{\mathrm{H}}$
and
$\mathbf{H}_{{}_{\mathcal{T}\cup\\{u\\}}}=\left[\begin{array}[]{c|c}\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}&\mathbf{H}_{{}_{\\{u\\}}}^{\mathrm{H}}\end{array}\right]^{\mathrm{H}}$,
similar to (3) we have

$\displaystyle
f(\mathcal{S}\cup\\{u\\})-f(\mathcal{S})-f(\mathcal{T}\cup\\{u\\})+f(\mathcal{T})$
$\displaystyle=\mathrm{ln}\left(\frac{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}\cup\\{u\\}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}\cup\\{u\\}}}+\mathbf{I})\mathrm{det}(\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}+\mathbf{I})}{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{I})\mathrm{det}(\mathbf{H}_{{}_{\mathcal{T}\cup\\{u\\}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}\cup\\{u\\}}}+\mathbf{I})}\right)$
$\displaystyle=\mathrm{ln}\left(\frac{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{H}_{{}_{\\{u\\}}}^{\mathrm{H}}\mathbf{H}_{{}_{\\{u\\}}}+\mathbf{I})\mathrm{det}(\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}+\mathbf{I})}{\mathrm{det}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{I})\mathrm{det}(\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}+\mathbf{H}_{{}_{\\{u\\}}}^{\mathrm{H}}\mathbf{H}_{{}_{\\{u\\}}}+\mathbf{I})}\right)$
$\displaystyle=\mathrm{ln}\left(\frac{\mathrm{det}\left(\mathbf{H}_{{}_{\\{u\\}}}^{\mathrm{H}}(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{I})^{-1}\mathbf{H}_{{}_{\\{u\\}}}\right)}{\mathrm{det}\left(\mathbf{H}_{{}_{\\{u\\}}}^{\mathrm{H}}(\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}+\mathbf{I})^{-1}\mathbf{H}_{{}_{\\{u\\}}}\right)}\right)\geq
0,$ (18)

where the second inequality follows from the determinant lemma and the last
equality follows from $\mathcal{S}\subseteq\mathcal{T}$ that leads to
$\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}\succeq\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}$
and, hence,
$\left(\mathbf{H}_{{}_{\mathcal{S}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{S}}}+\mathbf{I}\right)^{-1}\succeq\left(\mathbf{H}_{{}_{\mathcal{T}}}^{\mathrm{H}}\mathbf{H}_{{}_{\mathcal{T}}}+\mathbf{I}\right)^{-1}$.
∎

Algorithm 1 below summarizes the greedy algorithm for optimally placing $M$
IRS platforms. It has been shown before [30, 34] that the worst-case
optimality guarantee for the performance of the greedy algorithm is evaluated
as

$f(\mathcal{S}^{gr})\geq
c^{-1}\left(1-\frac{1}{e^{c}}\right)f(\mathcal{S}^{*})\geq\left(1-\frac{1}{e}\right)f(\mathcal{S}^{*}),$
(19)

where $e$ is the Euler’s constant, $f(\mathcal{S}^{*})$ represents the optimal
objective value of (3) and $c\in[0,1]$ is the curvature of the submodular
objective $f(.)$ [35]:

$c=1-\leavevmode\nobreak\
\underset{\\{j\\}\in\mathcal{A}}{\textrm{minimize}}\quad\frac{f(\mathcal{A})-f(\mathcal{A}-\\{j\\})}{f(\\{j\\})}.$
(20)

We compute the tighter bound in (19) numerically and use it as a benchmark to
evaluate the performance of the greedy algorithm. The greedy algorithm often
outperforms the worst-case lower bounds, as demonstrated in our numerical
experiments.

Algorithm 1 Greedy algorithm for IRS placement.

1:Input $\mathcal{A}$

2:Output $\mathcal{S}^{gr}$

3:Initialization $\mathcal{S}=\varnothing$

4:While $|\mathcal{S}|<M$ do

5:
$u^{*}\leftarrow\underset{u\in\mathcal{A}\setminus\mathcal{S}}{\textrm{argmax}}\quad
f\left(\mathcal{S}\cup\\{u\\}\right)$

6: $\mathcal{S}\leftarrow\mathcal{S}\cup\\{u^{*}\\}$

7:Return $\mathcal{S}^{gr}\leftarrow\mathcal{S}$

##  4 Numerical Experiments

We validated our algorithm through numerical experiments in which We set
$N_{r}=N_{t}=8$ antennas for the radar transmitter and receiver and the radar
was located in the 2-D Cartesian plane at [$0$ m, $0$ m]. The target was at
the range $d_{tr}=60$ m and azimuth angle of arrival $\theta_{tr}=\pi/4$. The
discretized radar aperture $\mathcal{A}$ is chosen to be the Cartesian product
of the set $\mathcal{R}$ with $K_{{}_{\theta}}=100$ candidate ranges spaced
with $\delta=1$ m in the interval $[0,100]$m and the set $\mathcal{M}$
comprised of $K_{{}_{r}}=12$ azimuth angles from the interval $[0,2\pi)$
spaced with $\mu=\pi/6$.

Fig. 2: The value of cost function of (3) plotted against the increasing
number of IRS platforms $M$ that are sequentially placed in the radar coverage
area $\mathcal{A}$.  Fig. 3: Optimal placement of $M=5$ IRS platforms (green
star) to illuminate the target (red triangle). The radar (blue circle) is
located at the origin.

We employed Algorithm 1 to decide the ranges and azimuth angles
$(r_{m},\theta_{ri,m})\in\mathcal{A}$ of $M$ IRS platforms tuned at randomly
generated phase-shifts comprised in $\bm{\Phi}_{m}$, for
$m\in\\{1,\ldots,M\\}$. Fig. 2 compares the optimized MI-based cost function
$f(\mathcal{S})$ for different numbers $M$ of deployed IRS platforms with
random placement and the worst-case optimality guarantee of the greedy
algorithm. In order to compute the worst-case optimality guarantee of the
greedy algorithm, we computed the curvature of the submodular objective
function defined in (19) through an exhaustive search. Our experiments showed
that $c\approx 0.996$. Fig. 3 illustrates the optimal IRS locations in polar
coordinates as obtained by Algorithm 1, for $M=5$ IRS platforms.

##  5 Summary

We considered an IRS-assisted sensing system and optimized the placement of
IRS platforms using the recently proposed tools of submodular optimization. We
showed that our MI-based design criterion is submodular and monotonic. The
greedy algorithm for submodular optimization yields the optimal placement of
IRS platforms in the radar coverage area with a constant suboptimality
guarantee. The IRS-aided radar with optimized IRS locations outperforms random
placement and the theoretical worst-case optimality guarantee of the greedy
algorithm.

## References

  * [1] A. M. Elbir, K. V. Mishra, M. B. Shankar, and S. Chatzinotas, “The rise of intelligent reflecting surfaces in integrated sensing and communications paradigms,” _IEEE Network_ , 2022, in press.
  * [2] T. Wei, L. Wu, K. V. Mishra, and M. Shankar, “RIS-aided wideband holographic DFRC,” _arXiv preprint arXiv:2305.04602_ , 2023.
  * [3] J. An, C. Xu, D. W. K. Ng, G. C. Alexandropoulos, C. Huang, C. Yuen, and L. Hanzo, “Stacked intelligent metasurfaces for efficient holographic MIMO communications in 6G,” _IEEE Journal on Selected Areas in Communications_ , vol. 41, no. 8, pp. 2380–2396, 2023.
  * [4] D. Tyrovolas, S. A. Tegos, E. C. Dimitriadou-Panidou, P. D. Diamantoulakis, C. K. Liaskos, and G. K. Karagiannidis, “Performance analysis of cascaded reconfigurable intelligent surface networks,” _IEEE Wireless Communications Letters_ , vol. 11, no. 9, pp. 1855–1859, 2022.
  * [5] F. Wang and A. L. Swindlehurst, “Hybrid RIS-assisted interference mitigation for spectrum sharing,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2023, pp. 1–5.
  * [6] Z. Esmaeilbeig, A. Eamaz, K. V. Mishra, and M. Soltanalian, “Quantized phase-shift design of active IRS for integrated sensing and communications,” in _IEEE International Conference on Acoustics, Speech, and Signal Processing Workshops_ , 2023, pp. 1–5.
  * [7] Z. Wang, X. Mu, and Y. Liu, “STARS enabled integrated sensing and communications,” _IEEE Transactions on Wireless Communications_ , vol. 22, no. 10, pp. 6750–6765, 2023.
  * [8] T. Wei, L. Wu, K. V. Mishra, and S. M. Bhavani, “Simultaneous active-passive beamformer design in IRS-enabled multi-carrier DFRC system,” in _European Signal Processing Conference_ , 2022, pp. 1007–1011.
  * [9] T. Wei, L. Wu, K. V. Mishra, and M. Shankar, “Multi-IRS-aided Doppler-tolerant wideband DFRC system,” _IEEE Transactions on Communications_ , 2023, in press.
  * [10] J. A. Hodge, K. V. Mishra, B. M. Sadler, and A. I. Zaghloul, “Index-modulated metasurface transceiver design using reconfigurable intelligent surfaces for 6G wireless networks,” _IEEE Journal of Selected Topics in Signal Processing_ , 2023, in press.
  * [11] Z. Esmaeilbeig, K. V. Mishra, and M. Soltanalian, “IRS-aided radar: Enhanced target parameter estimation via intelligent reflecting surfaces,” in _IEEE Sensor Array and Multichannel Signal Processing Workshop_ , 2022, pp. 286–290.
  * [12] Z. Esmaeilbeig, A. Eamaz, K. V. Mishra, and M. Soltanalian, “Joint waveform and passive beamformer design in multi-IRS aided radar,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2023, in press.
  * [13] Z. Esmaeilbeig, K. V. Mishra, A. Eamaz, and M. Soltanalian, “Cramér-Rao lower bound optimization for hidden moving target sensing via multi-IRS-aided radar,” _IEEE Signal Processing Letters_ , vol. 29, pp. 2422–2426, 2022.
  * [14] Z. Esmaeilbeig, A. Eamaz, K. V. Mishra, and M. Soltanalian, “Moving target detection via multi-IRS-aided OFDM radar,” in _IEEE Radar Conference_ , 2023, pp. 1–6.
  * [15] P.-Q. Huang, Y. Zhou, K. Wang, and B.-C. Wang, “Placement optimization for multi-IRS-aided wireless communications: An adaptive differential evolution algorithm,” _IEEE Wireless Communications Letters_ , vol. 11, no. 5, pp. 942–946, 2022.
  * [16] S. Zeng, H. Zhang, B. Di, Z. Han, and L. Song, “Reconfigurable intelligent surface (RIS) assisted wireless coverage extension: RIS orientation and location optimization,” _IEEE Communications Letters_ , vol. 25, no. 1, pp. 269–273, 2020.
  * [17] G. Stratidakis, S. Droulias, and A. Alexiou, “Optimal position and orientation study of reconfigurable intelligent surfaces in a mobile user environment,” _IEEE Transactions on Antennas and Propagation_ , vol. 70, no. 10, pp. 8863–8871, 2022.
  * [18] S. Ghose, D. Mishra, S. P. Maity, and G. C. Alexandropoulos, “RIS reflection and placement optimisation for underlay D2D communications in cognitive cellular networks,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2023, pp. 1–5.
  * [19] K. Ntontin, D. Selimis, A.-A. A. Boulogeorgos, A. Alexandridis, A. Tsolis, V. Vlachodimitropoulos, and F. Lazarakis, “Optimal reconfigurable intelligent surface placement in millimeter-wave communications,” in _European Conference on Antennas and Propagation_ , 2021, pp. 1–5.
  * [20] A. Chen, Y. Chen, and Z. Wang, “Reconfigurable intelligent surface deployment for blind zone improvement in mmWave wireless networks,” _IEEE Communications Letters_ , vol. 26, no. 6, pp. 1423–1427, 2022.
  * [21] E. Tohidi, S. Haesloop, L. Thiele, and S. Stanczak, “Near-optimal LoS and orientation aware intelligent reflecting surface placement,” _arXiv preprint arXiv:2305.03451_ , 2023.
  * [22] F. T. Ulaby, R. K. Moore, and A. K. Fung, _Microwave Remote Sensing: Active and Passive. Volume 1 - Microwave Remote Sensing Fundamentals and Radiometry_. Artech House, 1981.
  * [23] M. M. Naghsh, M. Modarres-Hashemi, S. ShahbazPanahi, M. Soltanalian, and P. Stoica, “Majorization-minimization technique for multi-static radar code design,” in _European Signal Processing Conference_ , 2013, pp. 1–5.
  * [24] M. M. Naghsh, M. Modarres-Hashemi, A. Sheikhi, M. Soltanalian, and P. Stoica, “Unimodular code design for MIMO radar using bhattacharyya distance,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2014, pp. 5282–5286.
  * [25] M. Alaee-Kerahroodi, M. Soltanalian, P. Babu, and M. R. B. Shankar, _Signal design for modern radar systems_. Artech House, 2022.
  * [26] J. Liu, K. V. Mishra, and M. Saquib, “Co-designing statistical MIMO radar and in-band full-duplex multi-user MIMO communications,” _arXiv preprint arXiv:2006.14774_ , 2020.
  * [27] S. Joshi and S. Boyd, “Sensor selection via convex optimization,” _IEEE Transactions on Signal Processing_ , vol. 57, no. 2, pp. 451–462, 2009.
  * [28] H. Godrich, A. P. Petropulu, and H. V. Poor, “Sensor selection in distributed multiple-radar architectures for localization: A knapsack problem formulation,” _IEEE Transactions on Signal Processing_ , vol. 60, no. 1, pp. 247–260, 2012.
  * [29] K. V. Mishra, A. M. Elbir, and K. Ichige, “Sparse array design for direction finding using deep learning,” in _Sparse Arrays for Radar, Sonar, and Communications_. Wiley-IEEE Press, 2023, in press.
  * [30] G. Shulkind, S. Jegelka, and G. W. Wornell, “Sensor array design through submodular optimization,” _IEEE Transactions on Information Theory_ , vol. 65, no. 1, pp. 664–675, 2018.
  * [31] E. Tohidi, R. Amiri, M. Coutino, D. Gesbert, G. Leus, and A. Karbasi, “Submodularity in action: From machine learning to signal processing applications,” _IEEE Signal Processing Magazine_ , vol. 37, no. 5, pp. 120–133, 2020.
  * [32] K. V. Mishra and Y. C. Eldar, “Sub-Nyquist channel estimation over IEEE 802.11ad link,” in _IEEE International Conference on Sampling Theory and Applications_ , 2017, pp. 355–359.
  * [33] T. M. Cover, _Elements of information theory_. John Wiley & Sons, 1999.
  * [34] U. Feige, “A threshold of ln $n$ for approximating set cover,” _Journal of the ACM_ , vol. 45, no. 4, pp. 634–652, 1998.
  * [35] M. Sviridenko, J. Vondrák, and J. Ward, “Optimal approximation for submodular and supermodular optimization with bounded curvature,” _Mathematics of Operations Research_ , vol. 42, no. 4, pp. 1197–1218, 2017\.


# Modular Retrieval for Generalization and Interpretation

Juhao Liang${}^{\includegraphics[width=8.5359pt]{figures/red_lego.png}}$, Chen
Zhang${}^{\includegraphics[width=8.5359pt]{figures/orange_lego.png}\includegraphics[width=8.5359pt]{figures/red_lego.png}}$,
Zhengyang Tang${}^{\includegraphics[width=8.5359pt]{figures/red_lego.png}}$,
Jie Fu${}^{\includegraphics[width=8.5359pt]{figures/blue_lego.png}}$, Dawei
Song${}^{\includegraphics[width=8.5359pt]{figures/orange_lego.png}}$, Benyou
Wang${}^{\includegraphics[width=8.5359pt]{figures/red_lego.png}}$
SDS & SRIBD, The Chinese University of Hong Kong, Shenzhen
Beijing Institute of Technology
Beijing Academy of Artificial Intelligence
<EMAIL_ADDRESS>
Benyou is the corresponding author.

###### Abstract

New retrieval tasks have always been emerging, thus urging the development of
new retrieval models. However, instantiating a retrieval model for each new
retrieval task is resource-intensive and time-consuming, especially for a
retrieval model that employs a large-scale pre-trained language model. To
address this issue, we shift to a novel retrieval paradigm called modular
retrieval, which aims to solve new retrieval tasks by instead composing
multiple existing retrieval modules. Built upon the paradigm, we propose a
retrieval model with modular prompt tuning named REMOP. It constructs
retrieval modules subject to task attributes with deep prompt tuning, and
yields retrieval models subject to tasks with module composition. We validate
that, REMOP inherently with modularity not only has appealing generalizability
and interpretability in preliminary explorations, but also achieves comparable
performance to state-of-the-art retrieval models on a zero-shot retrieval
benchmark.111Our code is available at
https://github.com/FreedomIntelligence/REMOP

##  1 Introduction

The use of large-scale pre-trained language models (PLMs) has become the de
facto standard for various natural language processing (NLP) tasks due to
their compelling performance in a wide range of applications, such as
sentiment analysis [1; 2; 3] and named entity recognition [4; 5]. Similarly,
in retrieval, representative retrieval models [6; 7] also use PLMs as
backbones.

However, new retrieval tasks have continuously been emerging due to various
requirements, possibly involving distinguished task objectives, domains, and
languages. A quick example is personalized retrieval [8], which requires
retrieving documents given solely user preferences. These complex tasks bring
great challenges for retrieval models. Fortunately, with fine-tuning (FT),
retrieval models enhanced by PLMs could be effectively adapted to tasks via
tuning all parameters of the model. As a lightweight alternative to FT,
parameter-efficient approaches [9] like deep prompt tuning (DPT) [10; 11]
adapt PLMs by only tuning a small set of parameters and have shown performance
comparable to FT in retrieval scenarios [12]. However, such a one-model-to-
one-task (one-to-one) retrieval paradigm may fail to handle unseen retrieval
tasks due to its limited generalizability, thereby being resource-intensive
and time-consuming when the number of tasks explodes.

Inspired by the success of modular learning applied to other NLP tasks [13;
14], in this paper, we formally propose a novel many-modules-to-many-tasks
(many-to-many) retrieval paradigm: modular retrieval. Modular retrieval is
designed to enhance the generalizability of the retrieval process by combining
multiple retrieval modules to solve numerous retrieval tasks. Specifically, we
associate a task into multiple task attributes (e.g., domain) that are exactly
in correspondence to reusable modules. Since we decouple tasks and modules,
modular retrieval can be generalized to a new task by selectively composing
these modules. In particular, this process does not require any further
training.

Apart from generalization, interpretation is another advantage of modular
retrieval. By delving deeply into the attributes of each task, we can ground
these characteristics to a specific group of parameters, known as a module.
The composition of these modules can be used in a simple yet effective
additive mechanism (see a gradient accumulation analogy for a better
understanding). This process of module decomposition and composition
contributes to decomposability, a crucial aspect of transparency in model
interpretability, which expects that each sub-component of a network provides
an intuitive explanation [15]. It is particularly beneficial for various use
cases in downstream tasks. For instance, when the need arises to improve
certain features, such as updating a domain knowledge module, we can directly
locate a grounded module and update it without affecting other parts of the
model. More interestingly, we can even add or remove some module parameters in
a plug-and-play manner, if necessary.

Figure 1: Overview of modular retrieval. Train specific retrieval modules from
available tasks and selectively combine them into a PLM to solve complex
retrieval tasks, such as personalized retrieval.

Based on the paradigm, we propose a new modular retrieval approach, REMOP
(REtrieval with MOdular Prompt Tuning), which leverages the DPT technique to
construct retrieval modules subject to task attributes and uses the module
composition to obtain retrieval models subject to tasks. As shown in Figure 1,
REMOP trains several attribute-specific retrieval modules on available tasks
and generalizes to unseen tasks via flexible module composition via operating
prompts. We conduct multiple explorations to verify the generalizability and
interpretability of module composition, and demonstrate its effectiveness on
zero-shot retrieval tasks.

To sum up, our contributions are as follows:

  * •

We formally introduce a new retrieval paradigm: modular retrieval and its
merits compared to conventional retrieval.

  * •

We implement modular retrieval using deep prompt tuning, resulting in a novel
modular retrieval approach called REMOP that enables a simple-yet-effective
module composition. Note that we are the first to leverage modular prompt in
general modular training.

  * •

We explore and validate the generalizability and interpretability of various
module compositions in REMOP.

  * •

We apply modular retrieval in a new application: zero-shot retrieval.
Experiments demonstrated the effectiveness of REMOP.

##  2 Modular Retrieval

###  2.1 Definition

The concept of modularity [16; 17] has loomed large in the philosophy of
psychology since the early 1980s, and it is defined as the correspondence
between strongly interconnected components of a system (i.e., modules) and the
functions they perform [18; 19]. Within the mechanism, each module is tailored
for a specific purpose and can be reused consistently. There are many studies
[20; 21] on the application of modularity in neural networks, and they exploit
different approaches to instantiate modules and pursue the design of modular
neural networks with reusability, generalizability, and interpretability.

To the best of our knowledge, we are the first to formally define modular
retrieval, to bring the merits of modularity to retrieval. Modular retrieval
is defined as a new information retrieval paradigm that aims to perform
retrieval tasks by composing retrieval modules. Each retrieval module is
specialized for an attribute of the retrieval task, such as the retrieval
goal, the language, or the domain involved.

The whole modular retrieval process is shown in Algorithm 1. Modular retrieval
first decomposes a given task into a set of attributes, where each attribute
is addressed by a module; and then selects the corresponding retrieval modules
according to the decomposed attributes; afterwards, combines the selected
retrieval modules with a PLM to form a task-specific model, and uses it to
perform the concerned retrieval task.

Algorithm 1 Modular Retrieval

Given a retrieval task $t$ and a set of retrieval modules $M$, where module
$m_{\alpha}\in M$ is specialized for retrieval task attribute $\alpha$.

Modular Retrieval Steps:

1\. Decompose the task into a set of modules on task attributes: $t\to
A=\\{\alpha,\beta,\dots\\}$;

2\. Select retrieval modules corresponding to the attributes:
$M_{\textrm{\scriptsize selected}}=\left\\{m_{k}\in M|k\in A\right\\}$;

3\. Obtain a task-tailored retrieval model by module composition:
Retriever$(PLM,M_{\textrm{\scriptsize selected}})$;

###  2.2 Module

Before delving into how tasks can be decomposed into attributes and naturally
how corresponding modules can form models for tasks, without losing any
generalizability, we formally define the module and its arithmetic thereof.

####  2.2.1 Atomic and Compound Modules

We first define two types of retrieval modules for modular retrieval according
to their functionalities:

######  Definition 1.

Atomic Module $\textsc{Module}(\alpha)$ refers to a retrieval module that is
specific for one and only one task attribute $\alpha$. For example, a
biomedical atomic module is only for solving biomedical-related retrieval
tasks, and performs poorly in other domains.

######  Definition 2.

Compound Module $\textsc{Module}(\alpha,\beta,\dots\,\theta)$ refers to a
retrieval module that is capable of many independent task attributes
$\alpha,\beta,\dots,\theta$. For example, using a single science-medical
compound module can effectively solve both science-related and medical-related
retrieval tasks.

####  2.2.2 Module Arithmetic

Module Arithmetic |
---|---
Scaling |  $w\times$Module($\alpha$) = Module($w\alpha$)
Addition | Module($\alpha$) + Module($\beta$) = Module($\alpha,\beta)$
Subtraction | Module($\alpha$, $\beta$) - Module($\alpha$) = Module($\beta$)
Table 1: Basic module operations for flexible module composition.

Given a set of retrieval modules, how to enable them with the ability to solve
new tasks is an important problem. Although modular retrieval is flexible in
this case, we should define three basic modular operations: module scaling,
module addition, and module subtraction to realize flexibility, as shown in
Table 1.

######  Definition 3.

Module Scaling is to add a scale weight to a module to control its
effectiveness. It is based on the recognition that task attributes have
different importance for different tasks. For example, questions asked by a
senior scholar can be considered more in-depth than those asked by a beginner.

######  Definition 4.

Module Addition, like math addition, is the process of putting together two
different (atomic/compound) modules to produce a new (compound) module; and
this is for complex retrieval scenarios with multiple task attributes.

######  Definition 5.

Module Subtraction, as opposed to module addition, is used to remove some
functions from a module to obtain a new module that better fits the task. For
example, when we only have a computer-biomedical compound module and a
computer atomic module, we can obtain a pure biomedical atomic module through
the subtraction of modules.

###  2.3 Task Decomposition and Module Composition

Figure 2: Generalize knowledge from seen retrieval tasks to unseen retrieval
tasks by task decomposition and module composition, thereby improving multi-
tasks learning’s generalizability.

One of the advantages of multi-scenario learning [22; 23] is that it could
learn the commonness between tasks and therefore easily generalizes to one of
the specific tasks. However, it cannot generalize to a new task that was never
seen. To overcome this limitation, we propose to decompose a task into
multiple attributes, each attribute is associated with a module, as shown in
Figure 2. It, therefore, results in a many-to-many mapping from modules to
tasks. For example, as shown in Table 2, task $A$ is decomposed into modules
$\alpha$ and $\beta$ while task $B$ is decomposed into modules $\alpha$ and
$\theta$. After jointly training tasks $A$ and $B$, we have well-trained
modules $\alpha$, $\beta$, and $\theta$, by using which, we could infer on
many new tasks, e.g., a new task $C$ with $\beta$ and $\theta$ and a new task
$D$ with $\alpha$, $\beta$ and $\theta$. Note that $C$ and $D$ are different
from $A$ and $B$, but they are composed of an identical module set.

Paradigm | Training Task | Inference Task
---|---|---
multi-task retrieval |  $A$, $B$ |  $A$, $B$
modular retreival |  $A$($\alpha$, $\beta$), $B$($\alpha$, $\theta$) |  $A$,$B$, $C$($\beta$ $\theta$), $D$($\alpha$, $\beta$, $\theta$), etc.
Table 2: Modular retriever could generalize to new (composed) tasks.

An extreme case of modular retrieval will degrade into a multi-task retrieval
when module-task mapping degrades to a bijective one, in which case it could
not generalize to new tasks. We could define a bipartite graph between modules
and tasks, where one set of vertexes is for modules and another is for tasks.
To balance training efficiency and generalization, each node in both sets in
the ideal mapping should not be sparse, in other words, each task should be
associated with multiple modules and each module should be associated with
multiple tasks. In doing so, not only the commonness between multiple tasks
(as multi-task learning does) can be learned, but also the generalization of
modules can be assured. One could design a human-written mapping based on some
heuristics. Alternatively, Section 3.3 introduces an automatic way for task
decomposition.

##  3 REMOP: Retrieval with Modular Prompt Tuning

###  3.1 Basic Architecture

Figure 3: Overview of REMOP framework, built upon a dual-encoder framework.
Blue blocks represent the frozen PLM backbone, dark gray blocks represent
general prompts, and other colored blocks represent different attribute
prompts.

##### Problem Definition

In our settings, modular retrieval aims to retrieve related passages according
to a given query and its task attributes.222Sometimes, a task is described by
a textual instruction. It requires the learning of attribute knowledge into
corresponding modules and the combination of selected modules to perform a new
retrieval task.

##### Architecture

Based on the proposed retrieval paradigm, we present an architecture shown in
Figure 3. It is built upon a dual-encoder framework, which is comprised of a
query encoder and a passage encoder. The function of the model is to retrieve
the passages with encoded vectors closest to the vector of the given query.
Specifically, we use a PLM-based dual-encoder to separately encode the query
and the passages and computes their vector similarities[24; 25] in the dense
vector space, the similarity score is computed as the inner product as
previous works indicated [6]:

$s(q,p)=E_{q}(q)\cdot E_{p}(p)$ (1)

##### Prompt Tuning Implementation

Unlike conventional dense passage retrieval models, REMOP adds deep modular
prompts to the two encoders respectively to steer the retrieval direction
specifically. The deep modular prompt essentially is a prefix prompt [10; 11],
but in the modular retrieval scenario, it is also a container of task
attribute knowledge and the realization of the retrieval module. The selection
of a deep prompt will be conditioned on a task and its associated attributes.
In general, there are many parameter-efficient ways to implement attribute-
specific modules, such as deep prompts [10; 11] (used in this work), adapters
[26; 14] (previously used in multi-tasking learning and also nowadays in fine-
tuning), experts in Mixture-of-Expert architecture [27] or LoRA [28]. The main
rationale for using deep prompt is that we believe that attribute-specific
information should be stored in self-attention networks [11] while deep prompt
could directly intervene in the computation of the self-attention network.

###  3.2 Separating Specificity from Commonness

We divide deep modular prompts into two types: a general prompt and many
attribute prompts. The former learns the commonness among tasks while the
latter learns the specificity of each attribute.

General Prompt is used to store the general knowledge of the retrieval tasks,
and can also be considered as an adapter between attribute prompts and the
PLM, because all attribute prompts are not directly attached to the PLM, but
attached to the general prompt.

Attribute Prompt is used to store specific task attribute knowledge. It has
the ability of module operations mentioned above, and can be flexibly combined
with each other as requirements. While both the query encoder and passage
encoder come with a general prompt, attribute prompts are only allowed to
attach on the query encoder. This is because otherwise we need to stores many
encoded passage vectors for tasks with different attributes. We can actually
reuse the same encoded passages, avoiding repeat computation and reducing the
cost of storage.

Necessity of the General and Attribute Prompts There are three types of
parameters: the frozen PLM backbone, the trainable general prompt and
trainable attribute prompts. Since the PLM backbone is frozen to align
standardized backbones among (classification or retrieval) tasks, the only
trainable parameters sharing between tasks are general prompt, without which
REMOP cannot learn the commonness between tasks. Attribute prompts are used to
learn the task specificity, or more accurately, attribute specificity.

###  3.3 Instruction Decomposition

Inspired by instruction tuning [29; 30; 31; 32; 33], we use task instructions
to build a task module mapping. Concretely, we decompose task instructions
into multiple task attribute labels, as shown in Table 3, and by leveraging
the task attributes labels, we can consider that a task consists of multiple
modules. Consequently, we transform a retrieval with instruction task [23]
into a modular learning task [34], where a module is refer to one or multiple
task attributes. To sum up, we utilize the modular learning method to solve
the retrieval with instruction tasks in order to obtain better
interpretability and flexibility.

Task | Instruction
---|---
NF Corpus | Retrieve scientific paper paragraph to answer this question.
Arguana | Retrieve an argument that counter argues the following paragraph.
SciFact | Retrieve a scientific paper sentence to verify if the following claim is true.
DBPedia | Retrieve an Wikipedia introduction paragraph of the following entity.
Attribute |  Science, QA, Fact-Checking, Wikipedia
Table 3: Examples of instruction decomposition for retrieval tasks: NF Corpus
[35], Arguana [36], SciFact [37], and DBPedia [38].

###  3.4 Modular Prompt Composition

It is a crucial problem about how to implement the module operations mentioned
in the modular retrieval paradigm in REMOP. Weighted averaging [39; 40] is a
commonly used approach to combine different models in federated learning [41;
42]. More specifically, weighted averaging involves assigning each local model
a weight that reflects its performance on a validation set or some other
metric, and then combining the models by taking a weighted average of their
parameters. In the modular retrieval case, we can consider a pre-trained
language model with different attribute prompts as several independent models,
and using the weighted averaging method to combine them can be considered as
building a new retrieval model with all the source models’ ability. To this
end, we apply the weighted averaging method to the trained attribute prompts
for module compositions.

For instance $x$, the final prefix prompt is $P_{\textrm{final}}(x)$, which is
calculated by a shared general prompt $P_{\textrm{general}}$ and $N$ attribute
prompts $P_{1}\dots P_{N}$, where $N$ indicates the total number of the kinds
of attributes in the whole training datasets. Besides, the instance $x$ has
$N$ weighting values $w_{x1}\dots w_{xN}$ corresponding to the task
attributes. Therefore, the final prompt $P_{\textrm{final}}$ for the instance
$x$ is calculated as following:

$P_{\textrm{final}}(x)=P_{\textrm{general}}+\frac{w}{N}\sum_{i}^{N}w_{xi}P_{i}$
(2)

where $w$ indicates the scale weight of the synthesized attribute prompt.
Section. 4.3 experimentally demonstrates the effectiveness of module scaling,
module addition, and module subtraction by using such a weighted averaging
composition approach.

##### An Intuitive Explanation:

Eq. 2 inherently assumes that modular prompts are additive. We argue that the
rationale behind additive prompts is nontrivial. In a parameter-efficient
fashion, prompts are the only trainable parameters while the basic backbone is
frozen. From an intuitive perspective, learned specific prompts w.r.t a
specific module could be considered as specific accumulated gradients on the
general prompt performed on all related tasks w.r.t the module. In other
words, specific prompts, previously considered as network parameters, could,
at least in some senses, be treated as gradients of general prompts; note that
they are the same shape. Gradient accumulation is a way to train deep learning
models that involves adding up gradients over multiple mini-batches before
updating the model’s weights; such gradients are additive. Therefore, weight
average between multiple prompts could be seen as accumulating ‘related
gradients learned from related tasks’ while excluding unrelated ones, namely,
selecting approximate modular prompts during inference.

For prompt training in REMOP, we use data with the same task attributes to
train an attribute prompt and directly add it to the general prompt, so that
the former can be considered as an update of the latter one (i.e., delta
value). Then, we add a weight to the attribute prompt, similar to imposing a
‘learning rate’ upon the the gradients, to control the effect of the update in
this training batch. The higher the weight, the faster the model is updated,
which may lead to task overfitting, or even move away from the optimal point.
In contrast, a lower scale weight may steer the model more general than
specific. Therefore, finding an appropriate scaling weight is crucial to
improve the generalization and adaptability of the retrieval model.

###  3.5 Modular Prompt Training

The proposed method needs to train both a general prompt and attribute prompts
on multiple source retrieval tasks. We divide the training into two phases:
general prompt training and attribute prompt training. The first stage uses
general retrieval tasks (e.g., MS-MARCO [43]) to solely train the general
prompt, which is to learn commonsense knowledge and guarantee its basic
general retrieval ability. In the second phase, we jointly train the attribute
prompts and the general prompts on all the available tasks. Specifically, we
employ a lower learning rate for the trained general prompt and a higher
learning rate for the attribute prompts, which is objective to learn specific
knowledge into the attribute prompts and fine-tune the general prompt to
better bridge the attribute prompt with PLM.

##  4 Exploration on Modularity

In this section, we separately verify the feasibility of module arithmetic of
deep modular prompts implemented by REMOP through conducting three exploratory
experiments. After that, there is a case study to show how to leverage these
three module operations to flexibly compose different modules to solve tasks
in complex scenarios. The overview of the experiment design is shown in Table
4.

Training Module Operations Evaluation Scaling Module($\alpha$)
$w$Module($\alpha$) Data{$\alpha$} Addition Module($\alpha$) Module($\beta$)
Module($\alpha$) + Module($\beta$) Data{$\alpha$, $\beta$} Subtraction
Module($\alpha$, $\beta$) Module($\alpha$) Module($\alpha$, $\beta$) -
Module($\alpha$) Data{$\beta$} Combination Module($\alpha$) Module($\beta$)
$w_{1}$Module($\alpha$) + $w_{2}$Module($\beta$) $w_{1}$Data{$\alpha$}+$w_{2}$
Data{$\beta$}

Table 4: Overview of module arithmetic experiments.

###  4.1 Experimental Setup

We use a RoBERTa-large model[44] as the backbone PLM for the following
experiments due to its outstanding performance compared with other publicly
available large language models. Besides, a previous research[12] has shown
that directly applying deep prompt tuning in dense passage retrieval largely
underperforms fine-tuning methods, and it is helpful and necessary to do the
retrieval-oriented intermediate pretraining (RIP)[12] for the large language
model. Therefore, we use the RoBERTa-large model which has been pre-trained on
MS-MARCO[43] by RIP as our final fixed backbone model. The length of all
prefix-prompts is set to 128, and the training epoch is set to 5.

For each experiment in this section, we use 100k data for training and 1k data
for evaluation, and all data are sourced from BERRI [23] and LOTTE [45].
Following the instruction decomposition method described in Section 3.3, we
extract the task attributes from the instructions for each task and map them
to the corresponding modules. The results reported are based on the
performance metric of Normalized Discounted Cumulative Gain at 10 (i.e.,
NDCG@10).

###  4.2 Module Scaling

As defined in Definition 3, module scaling is to add a scale weight to control
the effect of an attribute module on the generalist model. If the weight is
set too low (close to 0), the model will be more general instead of task-
attribute-specific, while if it is set too high (close to 1), the model tends
to overfit the training data, leading to poor generalizability. In order to
find a proper scale weight, we test the effect of seven different scale
weights on five downstream tasks which have different task attributes. As
shown in Table 5, the results show that using module weights close to 0 or
close to 1 will result in poor zero-shot retrieval ability. Also, 0.5 is a
module weight that performs well in most experiments. Therefore, we select 0.5
as the default module scale weight $w$ for the final attribute prompt, and it
is applied in the remaining experiments.

Task / Module General 0.1×$M_{\alpha}$ 0.3×$M_{\alpha}$ 0.5×$M_{\alpha}$
0.7×$M_{\alpha}$ 0.9×$M_{\alpha}$ 1.0×$M_{\alpha}$ QA (1k) 0.315 0.325 0.342
0.357 0.350 0.300 0.267 Science (1k) 0.152 0.154 0.155 0.155 0.153 0.147 0.144
Summarization (1k) 0.152 0.153 0.153 0.151 0.147 0.136 0.128 Wikipedia (1k)
0.448 0.460 0.474 0.474 0.451 0.379 0.312 Fact-Checking (1k) 0.134 0.152 0.181
0.194 0.186 0.164 0.145

Table 5: Results of module scaling experiments. Using a corresponding
attribute module $M_{\alpha}$ for each task: Module(QA), Module(Science),
Module(Summarization), Module(Wikipedia), Module(Fact-Checking), compare the
performance of different module scale weights.

###  4.3 Module Addition

To find the best way to implement the module addition arithmetic described in
Definition 4, which is to combine two modules into a new module, we try two
simple aggregation operations: sum aggregation (Sum) and average aggregation
(Avg). Specifically, we train two retrieval modules separately, a Wikipedia
module (wiki) and a Science module (sci), and evaluate the performance of
models with different module settings in a corresponding downstream task that
is associated with both science and Wikipedia. Table 6 shows that the effect
of using one of the trained modules is superior to the generalist model,
whereas the performance of combining modules through sum aggregation is the
worst. The module synthesized using average aggregation has the best
performance among the experiments. To this end, the average aggregation is
chosen as the implementation of module addition in REMOP.

Task / Module General Module(sci) Module(wiki) Sum(sci, wiki) Avg(sci, wiki)
Science+Wikipedia (1k) 0.357 0.382 0.376 0.353 0.385

Table 6: Results of module addition experiments.

###  4.4 Module Subtraction

As defined in Definition 5, module subtraction aims at creating a new module
by removing useless knowledge from a given module. Following Table 4, we train
two modules: a Wikipedia-Fact-Checking compound module and a Wikipedia atomic
module, namely Module(wiki, fc) and Module(wiki) respectively. Given an unseen
Fact-Checking retrieval task, we compare and analyze the effects of different
combinations of the above two trained modules. As shown in Table 7, results
show that even though the synthetic module is not better than the compound
module, it still outperforms the generalist model and the atomic module,
demonstrating the effectiveness of the module subtraction arithmetic.

Task / Module General Module(wiki) Module(wiki, fc) Module(wiki,
fc)-Module(wiki) Fact-Checking (1k) 0.131 0.172 0.195 0.187

Table 7: Results of module subtraction experiments.

###  4.5 Module Arithmetic Combination

Based on previous experiments, we observed that not all task attributes are
equally important for the same task. For example, in module addition
experiments (Section 4.3), the science atomic module has better performance
than the Wikipedia atomic module for the given Science-Wikipedia retrieval
task. To find out the primary reason behind the difference, in this part, we
investigate the relationship between module combination weights and task
attribute proportions. First, we use a QA-specific task and a Wikipedia-
specific task to synthesize new QA-Wikipedia tasks with different synthesis
ratios. Then, leveraging a trained QA module $M_{\textrm{\scriptsize QA}}$ and
a trained Fact-Checking module $M_{\textrm{\scriptsize FC}}$, we solve the
synthesis tasks under different module combination settings.

As shown in Table 8, combining two modules with different scale weights can
have different performance for the same task, and the ratio of module
combinations to task combinations can roughly be considered to be linearly
related. It shows that it is reasonable to assign different scale weights for
task attributes to obtain a more tailored model for a given task.

Task / Module General $M_{\textrm{\scriptsize QA}}$ 0.7$M_{\textrm{\scriptsize
QA}}$+0.3$M_{\textrm{\scriptsize FC}}$ 0.5$M_{\textrm{\scriptsize
QA}}$+0.5$M_{\textrm{\scriptsize FC}}$ 0.3$M_{\textrm{\scriptsize
QA}}$+0.7$M_{\textrm{\scriptsize FC}}$ $M_{\textrm{\scriptsize FC}}$
0.7QA+0.3FC (1k) 0.1827 0.1960 0.2034 0.2061 0.2072 0.2040 0.5QA+0.5FC (1k)
0.1406 0.1570 0.1616 0.1633 0.1633 0.1600 0.3QA+0.7FC (1k) 0.1003 0.1214
0.1242 0.1247 0.1252 0.1220

Table 8: Results of module arithmetic combination experiment.

##  5 Generalizing to New Tasks: Zero-shot Retrieval

In this section, we evaluate the generalizability of REMOP in zero-shot
retrieval applications. Specifically, we train retrieval modules on a dataset
collection containing task instructions written by experts, and test the
performance on a zero-shot retrieval benchmark. The experimental settings are
shown on Section 5.1 and the results are demonstrated in Section 5.2. Section
5.3 analyzes the experimental results and gives a conclusion on this
experiment.

Retrieval Modules on Training Phase (from BERRI) Module #q in train Module #q
in train QA 2,355,072 Dialogue 159,064 Summarization 921,266 Fact-Checking
140,438 Wikipedia 831,003 Science 123,544 News 756,275 Caption 70,643 Medical
324,520 Legal 2,256 Sentence-Paraphrase 185,859 General 1,415,211 Retrieval
Tasks on Evaluation Phase (from BEIR) Task Attributes (#q in test) Task
Attributes (#q in test) Arguana (ARG) [36] Fact-Checking (1,406) NF Corpus
(NFC) [35] Science+QA (3,237) Climate-Fever (CLI) [46] Fact-Checking (1,535)
Touche-2020 (TOU) [47] Fact-Checking (49) DBPedia (DBP) [38] Wikipedia (467)
SciDocs (SCD) [48] Science+Summarization (1,000) FIQA (FQA) [49] QA (3,452)
SciFact (SCF) [37] Science+Fact-Checking (1,109) TREC-COVID (TREC) [50]
Science+QA (50)

Table 9: Data statistics in zero-shot retrieval experiments. # in train/test
indicates the number of queries used for module training and task evaluation.
Note that not all the trained modules are used for evaluation.

###  5.1 Experimental Settings

##### Datasets and Metrics

In the training phase, we use BERRI [23] for module training. BERRI is a
large-scale retrieval dataset with expert-written task instructions; and by
decomposing the given task instructions, we can obtain a list of task
attributes for each task and train the corresponding retrieval modules
following the above mentioned two-stage training strategy. In the evaluation
phase, we evaluate the performance of the trained modules on a zero-shot
retrieval benchmark: BEIR [51]. Following [23; 52], we exclude Natural
Questions, MS MARCO, HotpotQA, FEVER and CQADupStack from evaluation tasks. We
map the remaining tasks to one or more retrieval modules according to their
task instructions, and the data statistics of evaluation is shown at the lower
part of Table 9. We report the official NDCG@10 metric on BEIR.

##### Model Settings

We implement REMOP in this experiment using MS-MARCO[43] pre-trained
condenser-base model [53] as the PLM backbone. Following the previous work
[12], prompt length is set to 128, learning rate is set to 7e-3 for general
prompt training in phase 1 and attribute prompt training in phase 2, the
learning rate for phase 2 general prompt training is set to 7e-6. And we adopt
the instruction-unfollowing negative sampling to select 5 negative passages
for each positive document as BERRI did [23]. The rest of hyper-parameter
settings is following coCondenser [53] (e.g., warm-up ratio, and mixed-
precision training). All training and inference are conducted on a single
server with 4 GPUs.

##### Baselines

Essentially, we empirically found that the retrieval performance of REMOP
strongly depends on the PLM backbone. For this reason, the main research
objective in this part is to find out if REMOP can enhance the original PLM
backbone’s generalizability on zero-shot retrieval tasks. We choose a pre-
trained condenser as the backbone and compare the zero-shot retrieval
performance of DPR (fine-tune all parameters), DPR with single prompt
(training a single prompt, following DPTDR [12]) and REMOP (fine-tune multiple
specific modular prompt). Besides, we also demonstrate the results of other
widely used retrieval methods for readers’ reference, including a lexical
retrieval model, sparse retrieval models, and multiple dense retrieval models;
these results are reported from BEIR and BERRI [51; 23].

###  5.2 Experimental Results

Method PLM (# Params) TREC NFC FQA ARG TOU DBP SCD CLI SCF Avg. SCIQA SCIQA QA
FC FC WIKI SCISUM FC SCIFC BM25 - 65.6 32.5 23.6 31.5 36.7 31.3 15.8 21.3 66.5
36.0 DeepCT BERT-base (110M) 40.6 28.3 19.1 30.9 15.6 17.7 12.4 6.6 63.0 26.2
SPARTA DistilBERT (66M) 53.8 30.1 19.8 27.9 17.5 31.4 12.6 8.2 58.2 28.8
Contriever BERT-base (110M) 27.4 31.7 24.5 37.9 19.3 29.2 14.9 15.5 64.9 29.3
ANCE RoBERTa-base (110M) 65.4 23.7 29.5 41.5 24.0 28.1 12.2 19.8 50.7 32.8
TAS-B DistilBERT (66M) 48.1 31.9 30.0 42.9 16.2 38.4 14.9 22.8 64.3 34.4 GenQ
DistilBERT (66M) 61.9 31.9 30.8 49.3 18.2 32.8 14.3 17.5 64.4 35.7 DPR-vanilla
Condenser-base (110M) 69.4 29.3 33.3 41.1 28.0 36.0 14.5 15.6 54.6 35.8 DPR-
prompt Condenser-base (2.3M) 62.8 30.3 31.5 40.1 25.1 33.3 15.2 15.9 50.3 33.8
REMOP Condenser-base (2.3M×7) 65.3 31.4 31.6 41.7 25.3 36.0 15.4 21.0 54.0
35.8

Table 10: Zero-shot retrieval results on BEIR, reported in NDCG@10. # Params
are the number of trainable parameters. The last group of models is the
results of DPR models based on a pre-trained condenser with different prompt
settings: DPR-vanilla (no prompts used), DPR-prompt (adding a single prompt),
and REMOP (using modular prompts); and the highest results of the three is
bolded. The labeled task attributes for each task are listed in colors:
Science, QA, Fact-Checking, Wikipedia, Summarization.

As shown in Table 10, compared to the fine-tuned DPR model (DPR-vanilla),
REMOP can achieve comparable zero-shot retrieval performance with fewer
trainable parameters. The DPR-prompt model, which is only trained on a single
prefix prompt (2.3M parameters), shows relatively poor performance on zero-
shot retrieval tasks; and REMOP, using module composition to enhance model
generalizability, outperforms the DPR-prompt on all the evaluation tasks.
Compared to the other listed retrieval methods, REMOP shows its advantage in
parameter-efficiency and generalizability that only training on a small number
of parameters (2.3M×7) can achieve comparable performance. It is worth noting
that most of the dense passage retrieval methods and sparse passage retrieval
methods underperform the basic lexical retrieval method BM25 on zero-shot
retrieval tasks, and we give an analysis of this phenomenon in Section 5.3.

###  5.3 Analysis

First, from the last group of Table 10, it shows that the proposed modular
retrieval approach, REMOP, outperforms the model using a single general prompt
on all the evaluation tasks, which indicates that each task module (composed
of several task attribute modules) can indeed match the given task and improve
model specificity. Compared to the fine-tuned DPR model, REMOP demonstrates
comparable performance over the evaluation tasks, which shows that it’s
feasible to train a few parameters and obtain fine-tuned performance on zero-
shot retrieval scenarios.

Second, it is also clear to see that the results of most of the listed dense
passage retrieval methods are lower than the BM25, which is an acceptable
phenomenon since previous research [54] has indicated that dense passage
retriever perform worse than lexical retrieval models on zero-shot retrieval
task. From this perspective, we can consider the proposed modular retrieval
paradigm as a feasible solution to alleviate this shortcoming of dense
retrieval.

Lastly, besides parameter efficiency and generalization, the interpretability
advantage of REMOP is also shown in the results. For example, REMOP can have a
higher enhancement over the fine-tuned model and the single-prompt model on
Fact-Checking-related tasks, which indicates that the Fact-Checking retrieval
module is well-trained in the training phase. This observation provides a
valuable reference for subsequent improvements, guiding us in which part we
should invest more training resources for improvement.

##  6 Related Works on Modularity

Modular learning techniques have been extensively utilized in machine learning
and demonstrated impressive performance in various tasks such as machine
translation [55; 56], speech processing [57], and computer vision [58]. DEMIX
[59] employs expert layers as modules to store domain-specific knowledge and
leverages modularity to enhance model generalization. ATTEMPT [60] trains
task-specific soft prompts for each task and combines them using attention
routing, which is a one-to-one mapping case discussed in Section 2.3. MAD-X
[14] and AdapterSoup [61] employ adapter structures [14; 62] to implement
domain-specific modules 333Compared to other parameter-efficient methods,
adapter layers usually require more parameters as they depend on a model’s
input and hidden size for the new function [34].. The former uses adapter
layers with fixed routing for zero-shot cross-lingual transfer, while the
latter employs a text clustering approach for module routing.

As shown in Table 11, compared with the previous works, the main differences
of our proposed approach are: 1) we first apply modular learning in the
information retrieval field; 2) we enhance the generalizability of modularity
by using task attribute decomposition to implement many-to-many task module
mapping; 3) we associate modules with specific task attributes, which vastly
improves the interpretability of modularity; 4) lastly, we implement the
module using a parameter-efficient approach, which is friendly to low-resource
scenarios and efficient in computation and storage.

Related Works Information Retrieval Generalizability Interpretability
Parameter-efficiency REMOP $\surd$ $\surd$ $\surd$ $\surd\surd$ DPR [6]
$\surd$ DPTDR [12] $\surd$ $\surd\surd$ DEMIX [59] $\surd$ $\surd$ ATTEMPT
[60] $\surd$ $\surd\surd$ MAD-X [14] $\surd$ $\surd$ AdapterSoup [61] $\surd$
$\surd$ $\surd$

Table 11: Comparison with Related Works.

##  7 Conclusion

This paper formally defines a new information retrieval paradigm, modular
retrieval, which aims to bring the benefits of modular learning to information
retrieval tasks and increase the interpretability of the retrieval process.
Based on the proposed retrieval paradigm, we propose a novel modular retrieval
method REMOP, which utilizes three modular operations to flexibly combine
retrieval modules to perform zero-shot retrieval tasks, with high
interpretability and generalization ability. We explore and verify the
effectiveness of the proposed module arithmetic, and experiments on a zero-
shot retrieval benchmark show that REMOP has comparable performance to the
fine-tuned model in zero-shot retrieval.

## References

  * [1] Fang Ma, Chen Zhang, and Dawei Song.  Exploiting position bias for robust aspect sentiment classification.  In Findings of the Association for Computational Linguistics: ACL/IJCNLP 2021, Online Event, August 1-6, 2021, volume ACL/IJCNLP 2021 of Findings of ACL, pages 1352–1358. Association for Computational Linguistics, 2021.
  * [2] Chen Zhang, Lei Ren, Fang Ma, Jingang Wang, Wei Wu, and Dawei Song.  Structural bias for aspect sentiment triplet extraction.  In Proceedings of the 29th International Conference on Computational Linguistics, COLING 2022, Gyeongju, Republic of Korea, October 12-17, 2022, pages 6736–6745. International Committee on Computational Linguistics, 2022.
  * [3] Rui Mao, Qian Liu, Kai He, Wei Li, and Erik Cambria.  The biases of pre-trained language models: An empirical study on prompt-based sentiment analysis and emotion detection.  IEEE Transactions on Affective Computing, 2022.
  * [4] Ehsan Taher, Seyed Abbas Hoseini, and Mehrnoush Shamsfard.  Beheshti-ner: Persian named entity recognition using bert.  arXiv preprint arXiv:2003.08875, 2020.
  * [5] Lin Sun, Jiquan Wang, Kai Zhang, Yindu Su, and Fangsheng Weng.  Rpbert: a text-image relation propagation-based bert model for multimodal ner.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 13860–13868, 2021.
  * [6] Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih.  Dense passage retrieval for open-domain question answering.  arXiv preprint arXiv:2004.04906, 2020.
  * [7] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  arXiv preprint arXiv:2007.00808, 2020.
  * [8] Susan Dumais, Edward Cutrell, Jonathan J Cadiz, Gavin Jancke, Raman Sarin, and Daniel C Robbins.  Stuff i’ve seen: a system for personal information retrieval and re-use.  In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 72–79, 2003.
  * [9] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly.  Parameter-efficient transfer learning for nlp.  In International Conference on Machine Learning, pages 2790–2799. PMLR, 2019.
  * [10] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  arXiv preprint arXiv:2107.13586, 2021.
  * [11] Xiang Lisa Li and Percy Liang.  Prefix-tuning: Optimizing continuous prompts for generation.  arXiv preprint arXiv:2101.00190, 2021.
  * [12] Zhengyang Tang, Benyou Wang, and Ting Yao.  Dptdr: Deep prompt tuning for dense passage retrieval.  arXiv preprint arXiv:2208.11503, 2022.
  * [13] Xiao Zhang and Dan Goldwasser.  Sentiment tagging with partial labels using modular architectures.  arXiv preprint arXiv:1906.00534, 2019.
  * [14] Jonas Pfeiffer, Ivan Vulić, Iryna Gurevych, and Sebastian Ruder.  Mad-x: An adapter-based framework for multi-task cross-lingual transfer.  arXiv preprint arXiv:2005.00052, 2020.
  * [15] Zachary C Lipton.  The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery.  Queue, 16(3):31–57, 2018.
  * [16] Jerry A Fodor.  The modularity of mind.  MIT press, 1983.
  * [17] Dana H Ballard.  Cortical connections and parallel processing: Structure and function.  Behavioral and brain sciences, 9(1):67–90, 1986.
  * [18] Carliss Young Baldwin and Kim B Clark.  Design rules: The power of modularity, volume 1.  MIT press, 2000.
  * [19] Karl Ulrich.  The role of product architecture in the manufacturing firm.  Research policy, 24(3):419–440, 1995.
  * [20] Robert A Jacobs, Michael I Jordan, and Andrew G Barto.  Task decomposition through competition in a modular connectionist architecture: The what and where vision tasks.  Cognitive science, 15(2):219–250, 1991.
  * [21] Clemens Rosenbaum, Tim Klinger, and Matthew Riemer.  Routing networks: Adaptive selection of non-linear functions for multi-task learning.  arXiv preprint arXiv:1711.01239, 2017.
  * [22] Jean Maillard, Vladimir Karpukhin, Fabio Petroni, Wen-tau Yih, Barlas Oğuz, Veselin Stoyanov, and Gargi Ghosh.  Multi-task retrieval for knowledge-intensive tasks.  arXiv preprint arXiv:2101.00117, 2021.
  * [23] Akari Asai, Timo Schick, Patrick Lewis, Xilun Chen, Gautier Izacard, Sebastian Riedel, Hannaneh Hajishirzi, and Wen-tau Yih.  Task-aware retrieval with instructions.  arXiv preprint arXiv:2211.09260, 2022.
  * [24] Stephen Mussmann and Stefano Ermon.  Learning and inference via maximum inner product search.  In International Conference on Machine Learning, pages 2587–2596. PMLR, 2016.
  * [25] Parikshit Ram and Alexander G Gray.  Maximum inner-product search using cone trees.  In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 931–939, 2012.
  * [26] Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi.  Efficient parametrization of multi-domain deep neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8119–8127, 2018.
  * [27] Mikel Artetxe, Shruti Bhosale, Naman Goyal, Todor Mihaylov, Myle Ott, Sam Shleifer, Xi Victoria Lin, Jingfei Du, Srinivasan Iyer, Ramakanth Pasunuru, et al.  Efficient large scale language modeling with mixtures of experts.  arXiv preprint arXiv:2112.10684, 2021.
  * [28] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models.  arXiv preprint arXiv:2106.09685, 2021.
  * [29] Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le.  Finetuned language models are zero-shot learners.  arXiv preprint arXiv:2109.01652, 2021.
  * [30] Victor Sanh, Albert Webson, Colin Raffel, Stephen H Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, et al.  Multitask prompted training enables zero-shot task generalization.  arXiv preprint arXiv:2110.08207, 2021.
  * [31] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  arXiv preprint arXiv:2203.02155, 2022.
  * [32] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al.  Scaling instruction-finetuned language models.  arXiv preprint arXiv:2210.11416, 2022.
  * [33] Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Atharva Naik, Arjun Ashok, Arut Selvan Dhanasekaran, Anjana Arunkumar, David Stap, et al.  Super-naturalinstructions: Generalization via declarative instructions on 1600+ nlp tasks.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 5085–5109, 2022.
  * [34] Jonas Pfeiffer, Sebastian Ruder, Ivan Vulić, and Edoardo Maria Ponti.  Modular deep learning.  arXiv preprint arXiv:2302.11529, 2023.
  * [35] Vera Boteva, Demian Gholipour, Artem Sokolov, and Stefan Riezler.  A full-text learning to rank dataset for medical information retrieval.  In Advances in Information Retrieval: 38th European Conference on IR Research, ECIR 2016, Padua, Italy, March 20–23, 2016. Proceedings 38, pages 716–722. Springer, 2016.
  * [36] Henning Wachsmuth, Shahbaz Syed, and Benno Stein.  Retrieval of the best counterargument without prior topic knowledge.  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 241–251, Melbourne, Australia, July 2018. Association for Computational Linguistics.
  * [37] David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine van Zuylen, Arman Cohan, and Hannaneh Hajishirzi.  Fact or fiction: Verifying scientific claims.  arXiv preprint arXiv:2004.14974, 2020.
  * [38] Faegheh Hasibi, Fedor Nikolaev, Chenyan Xiong, Krisztian Balog, Svein Erik Bratsberg, Alexander Kotov, and Jamie Callan.  Dbpedia-entity v2: a test collection for entity search.  In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1265–1268, 2017.
  * [39] H Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas.  Federated learning of deep networks using model averaging.  arXiv preprint arXiv:1602.05629, 2, 2016.
  * [40] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [41] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  IEEE signal processing magazine, 37(3):50–60, 2020.
  * [42] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  arXiv preprint arXiv:1610.05492, 2016.
  * [43] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng.  Ms marco: A human generated machine reading comprehension dataset.  choice, 2640:660, 2016.
  * [44] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * [45] Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia.  Colbertv2: Effective and efficient retrieval via lightweight late interaction.  arXiv preprint arXiv:2112.01488, 2021.
  * [46] Thomas Diggelmann, Jordan Boyd-Graber, Jannis Bulian, Massimiliano Ciaramita, and Markus Leippold.  CLIMATE-FEVER: A Dataset for Verification of Real-World Climate Claims, January 2021.  arXiv:2012.00614 [cs].
  * [47] Alexander Bondarenko, Maik Fröbe, Meriem Beloucif, Lukas Gienapp, Yamen Ajjour, Alexander Panchenko, Chris Biemann, Benno Stein, Henning Wachsmuth, Martin Potthast, et al.  Overview of touché 2020: Argument retrieval-extended abstract.  Arampatzis et al.[7], pages 384–395, 2020.
  * [48] Arman Cohan, Sergey Feldman, Iz Beltagy, Doug Downey, and Daniel Weld.  SPECTER: Document-level representation learning using citation-informed transformers.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2270–2282, Online, July 2020. Association for Computational Linguistics.
  * [49] Macedo Maia, Siegfried Handschuh, André Freitas, Brian Davis, Ross McDermott, Manel Zarrouk, and Alexandra Balahur.  Www’18 open challenge: financial opinion mining and question answering.  In Companion proceedings of the the web conference 2018, pages 1941–1942, 2018.
  * [50] Ellen Voorhees, Tasmeer Alam, Steven Bedrick, Dina Demner-Fushman, William R Hersh, Kyle Lo, Kirk Roberts, Ian Soboroff, and Lucy Lu Wang.  Trec-covid: constructing a pandemic information retrieval test collection.  In ACM SIGIR Forum, volume 54, pages 1–12. ACM New York, NY, USA, 2021.
  * [51] Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych.  Beir: A heterogenous benchmark for zero-shot evaluation of information retrieval models.  arXiv preprint arXiv:2104.08663, 2021.
  * [52] Zhuyun Dai, Vincent Y Zhao, Ji Ma, Yi Luan, Jianmo Ni, Jing Lu, Anton Bakalov, Kelvin Guu, Keith B Hall, and Ming-Wei Chang.  Promptagator: Few-shot dense retrieval from 8 examples.  arXiv preprint arXiv:2209.11755, 2022.
  * [53] Luyu Gao and Jamie Callan.  Unsupervised corpus aware language model pre-training for dense passage retrieval.  arXiv preprint arXiv:2108.05540, 2021.
  * [54] Ruiyang Ren, Yingqi Qu, Jing Liu, Wayne Xin Zhao, Qifei Wu, Yuchen Ding, Hua Wu, Haifeng Wang, and Ji-Rong Wen.  A thorough examination on zero-shot dense retrieval.  arXiv preprint arXiv:2204.12755, 2022.
  * [55] Ankur Bapna, Naveen Arivazhagan, and Orhan Firat.  Simple, scalable adaptation for neural machine translation.  arXiv preprint arXiv:1909.08478, 2019.
  * [56] NLLB Team, Marta R. Costa-jussà, James Cross, Onur Çelebi, Maha Elbayad, Kenneth Heafield, Kevin Heffernan, Elahe Kalbassi, Janice Lam, Daniel Licht, Jean Maillard, Anna Sun, Skyler Wang, Guillaume Wenzek, Al Youngblood, Bapi Akula, Loic Barrault, Gabriel Mejia Gonzalez, Prangthip Hansanti, John Hoffman, Semarley Jarrett, Kaushik Ram Sadagopan, Dirk Rowe, Shannon Spruit, Chau Tran, Pierre Andrews, Necip Fazil Ayan, Shruti Bhosale, Sergey Edunov, Angela Fan, Cynthia Gao, Vedanuj Goswami, Francisco Guzmán, Philipp Koehn, Alexandre Mourachko, Christophe Ropers, Safiyyah Saleem, Holger Schwenk, and Jeff Wang.  No language left behind: Scaling human-centered machine translation, 2022\.
  * [57] Hang Le, Juan Pino, Changhan Wang, Jiatao Gu, Didier Schwab, and Laurent Besacier.  Lightweight adapter tuning for multilingual speech translation.  arXiv preprint arXiv:2106.01463, 2021.
  * [58] Xuehai He, Chunyuan Li, Pengchuan Zhang, Jianwei Yang, and Xin Eric Wang.  Parameter-efficient fine-tuning for vision transformers.  arXiv preprint arXiv:2203.16329, 2022.
  * [59] Suchin Gururangan, Mike Lewis, Ari Holtzman, Noah A Smith, and Luke Zettlemoyer.  Demix layers: Disentangling domains for modular language modeling.  arXiv preprint arXiv:2108.05036, 2021.
  * [60] Akari Asai, Mohammadreza Salehi, Matthew E Peters, and Hannaneh Hajishirzi.  Attentional mixtures of soft prompt tuning for parameter-efficient multi-task knowledge sharing.  arXiv preprint arXiv:2205.11961, 2022.
  * [61] Alexandra Chronopoulou, Matthew E Peters, Alexander Fraser, and Jesse Dodge.  Adaptersoup: Weight averaging to improve generalization of pretrained language models.  arXiv preprint arXiv:2302.07027, 2023.
  * [62] Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi.  Efficient parametrization of multi-domain deep neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.