# PIVOT- Input-aware Path Selection for Energy-efficient ViT Inference

Abhishek Moitra, Abhiroop Bhattacharjee and Priyadarshini Panda
Yale University, New Haven, CT, 06511, USA

(2018; 2024)

###### Abstract.

The attention module in vision transformers(ViTs) performs intricate spatial
correlations, contributing significantly to accuracy and delay. It is thereby
important to modulate the number of attentions according to the input feature
complexity for optimal delay-accuracy tradeoffs. To this end, we propose PIVOT
- a co-optimization framework which selectively performs attention skipping
based on the input difficulty. For this, PIVOT employs a hardware-in-loop co-
search to obtain optimal attention skip configurations. Evaluations on the
ZCU102 MPSoC FPGA show that PIVOT achieves 2.7$\times$ lower EDP at 0.2%
accuracy reduction compared to LVViT-S ViT. PIVOT also achieves 1.3% and
1.8$\times$ higher accuracy and throughput than prior works on traditional
CPUs and GPUs. The PIVOT project can be found at this Github link.

Vision Transformers, Systolic Array Accelerators, Energy-efficiency

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn:
978-1-4503-XXXX-X/18/06††journalyear: 2024††copyright:
acmlicensed††conference: 61st ACM/IEEE Design Automation Conference; June
23–27, 2024; San Francisco, CA, USA††booktitle: 61st ACM/IEEE Design
Automation Conference (DAC ’24), June 23–27, 2024, San Francisco, CA,
USA††doi: 10.1145/3649329.3655679††isbn: 979-8-4007-0601-1/24/06

##  1\. Introduction

Vision Transformers (ViT) have demonstrated remarkable accuracy in large-scale
image classification tasks (Dehghani et al., 2023; Han et al., 2022;
Dosovitskiy et al., 2020). The success of ViTs can be attributed to the
attention module shown in Fig. 1a which utilizes the self-attention mechanism
to perform sophisticated spatial correlation operations (Han et al., 2022).
However, the attention module, involves computationally intensive operations,
including matrix multiplications and non-linear functions like softmax (Han et
al., 2022; Dehghani et al., 2023). Hence, as seen in Fig. 1b, the attention
module (QKV+QKT+SM+(SMxV)+Proj combined) contributes 77.5% to 81.9% of the
total ViT inference delay.

Recently, there have been several ViT inference optimization works that focus
on reducing the attention delay overhead. These mainly fall under two
categories 1) Attention sparsification (Kim et al., 2021; You et al., 2023) 2)
Token pruning techniques (Dong et al., 2023; Rao et al., 2021; Wang et al.,
2021). Attention sparsification techniques exploit the sparsity in the QKT and
(SMxV) layers (Kim et al., 2021; You et al., 2023) (Fig. 1a). In (Kim et al.,
2021), the authors algorithmically investigate the effect of structured
sparsity in the attention heads on ViT accuracy. In a more recent work (You et
al., 2023), the authors propose an accelerator co-design framework that
performs sparse-dense attention decomposition and develop a sparse accelerator
to exploit the attention sparsity. The objective of token pruning is to
selectively reduce the number of tokens in the ViT. In (Rao et al., 2021; Wang
et al., 2021), the authors use predictor networks to compute the global-local
token importance to eliminate redundant tokens. In HeatViT (Dong et al.,
2023), the authors use predictor networks to score the token importance based
on the information in each attention head. Along with the predictor networks,
the authors use a token packaging technique wherein unimportant tokens are
combined into one token to maintain a good accuracy-efficiency tradeoff.
Although, attention sparsification and token pruning works (Kim et al., 2021;
You et al., 2023; Rao et al., 2021; Dong et al., 2023) achieve good accuracy
at reduced computation, they have two major problems. Firstly, the portion of
delay optimized by these works is small. For example, attention sparsification
works are only able to optimize 7.3-7.7% of the overall delay since they
target the QKT and (SMxV) layers as shown in Fig. 1b. The second problem is
that attention sparsification and token pruning approaches require nuanced
hardware support to achieve optimal efficiency. For example, attention
sparsification works require sparse matrix multiplication hardware to fully
exploit sparse computations. Similarly, token pruning works require custom
hardware design to efficiently implement the token score predictor modules.
Thus, as shown in Fig. 1c, when implemented on general purpose platforms
(GPPs) such as CPUs and GPUs, they do not achieve any inference delay benefits
and, in fact, result in lower throughput compared to a dense baseline.

Figure 1. (a) Figure showing the encoder architecture of a vision transformer.
Q-Query, K-Key and V-Value. (b) Delay distribution across different ViT
modules for DeiT-S (left) and LVViT-S (right) ViTs. Note, Attention delay is
QKV+SM+QKT+(SMxV)+Proj. (c) Throughput of PIVOT compared with DeiT-S Baseline
(a standard DeiT-S (Touvron et al., 2021) ViT), prior token pruning (HeatViT
(Dong et al., 2023)) and attention sparsification (ViTCOD (You et al., 2023))
techniques implemented on GPUs- Nvidia V100, RTX2080ti, Jetson Orin Nano and
CPUs- Intel Xeon and Raspberry Pi 4. (d) PIVOT’s input difficulty-aware
inference

Another missing consideration in prior ViT optimization literature is the
input difficulty awareness. Interestingly, different images have different
feature complexity. For example, an easy image will contain simple, low-level
features compared to a difficult image with intricate feature representations
(Wu et al., 2018). Since attention modules are responsible for capturing
different levels of feature representations in the image, it is therefore
imperative to modulate the number of attentions in a ViT according to the
input difficulty (Fig. 1d). Modulating the number of attentions according to
input difficulty will ensure minimal attention activation to achieve high
accuracy at low inference delay. There have been several input difficulty-
aware network optimization works in the CNN literature (Panda et al., 2016; Wu
et al., 2018; Bhattacharjee et al., 2022). However, there are no works that
analyze the co-dependency between the number of attentions and input
difficulty from the perspective of accuracy and ViT inference delay.

To this end, we propose PIVOT, a hardware-algorithm co-design framework that
modulates the number of attentions in the ViT according to the input
difficulty. The goal of PIVOT is to achieve high classification accuracy by
using the minimum number of attentions in the ViT. As shown in Fig. 1d during
inference, PIVOT uses two kinds of ViTs - 1) Low Effort and 2) High Effort
ViT. The low effort ViT entails more attention skips compared to the high
effort and classifies the easy images. While the high effort ViT is used for
classifying the difficult images. An iterative hardware-in-the-loop co-search
is applied to obtain the optimal low and high effort ViTs according to the
user-provided delay constraints. For evaluation, we implement PIVOT on various
GPPs such as CPUs and GPUs. Additionally, we also evaluate PIVOT on Xilinx
ZCU102-implemented systolic array accelerator (Samajdar et al., 2018). Unlike
token pruning and attention sparsification works, PIVOT does not require any
application-specific hardware and can achieve 1.3$\times$-2$\times$ higher
throughput than baseline across various GPPs as shown in Fig. 1c.

In summary, the key contributions of our work are:

  1. (1)

We propose PIVOT- a hardware-algorithm co-optimization framework that
leverages input difficulty-aware attention skipping in ViTs to overcome the
high inference delay overhead of the attention module. During attention
optimization, PIVOT uses PIVOT-Sim, a cycle-accurate simulator for ViT
implemented on a Xilinx ZCU102 FPGA-based systolic array accelerator. PIVOT-
Sim will be made open-source and can benchmark different state-of-the-art
ViTs.

  2. (2)

Using PIVOT-Sim, we find that PIVOT achieves 1.73$\times$ (2.7$\times$) lower
energy-delay-product (EDP) at merely 0.4% (0.2%) accuracy reduction compared
to DeiT-S (Touvron et al., 2021) (LVViT-S (Jiang et al., 2021)) baselines.
End-to-end evaluations using PIVOT-Sim show that PIVOT is able to achieve more
than 1.7$\times$ energy reduction across different resources in the Xilinx
ZCU102 FPGA such as the ZynQ MPSoC PS, systolic array, on-chip buffers, and
communication/memory controller circuits.

  3. (3)

Through extensive experiments we show the overheads introduced by prior ViT
co-optimization works (Dong et al., 2023; You et al., 2023) when implemented
on GPPs such as GPUs and CPUs. As PIVOT does not require nuanced hardware
support, when implemented on GPPs, it achieves 1.8$\times$ higher throughput
at 0.4-1.3% higher accuracy compared to prior works.

##  2\. Background on Vision Transformer

A Vision Transformer (ViT) comprises multiple cascaded encoders, and each
encoder follows the architecture depicted in Fig. 1a. In each encoder, the
inputs of dimensions $t\times d$ undergo QKV operations wherein, weights
$W_{Q}$, $W_{K}$ and $W_{V}$ are multiplied with the input to generate the
Query (Q), Key (K) and Value (V) matrices. The attention module uses the
multi-head self-attention (MHSA) mechanism, that captures close relationships
between different image features (Touvron et al., 2021; Jiang et al., 2021;
Rao et al., 2021). For this, the Q, K and V outputs are partitioned into
multiple smaller attention heads ($Q_{i}$, $K_{i}$, $V_{i}$), where $i$
denotes a head of MHSA.

The attention is computed using Equation 1. In each head matrix
multiplications between $Q_{i}$, $K_{i}^{T}$ ($QK^{T}$) is performed followed
by the softmax (SM) and matrix multiplication with $V_{i}$ (SM$\times$V)
operations (Stevens et al., 2021). The softmax is computed using Equation 2.

(1)
$Attention(Q_{i},K_{i},V_{i})={Softmax(\frac{Q_{i}K_{i}^{T}}{\sqrt{d}})}V_{i},$
(2) $Softmax(x_{i})=\frac{e^{x_{i}-x_{max}}}{\sum_{i}{e^{x_{i}-x_{max}}}}.$

Next, the attention outputs are concatenated resulting in a $t\times d$ output
attention matrix. Following this, the projection and MLP layers project the
information into a higher dimension feature space. Each encoder outputs a
$t\times d$ vector that is forwarded to the subsequent encoder.

##  3\. PIVOT Methodology

Figure 2. Figure showing (a) Input difficulty-aware inference procedure with
PIVOT (b) PIVOT’s Phase 1 (b) Phase2 Methodology. $LEC$ denotes the user-
provided low effort constraint which implies the fraction of inputs that must
be classified by the low effort ViT. For PIVOT-Sim, ViT params include
embedding dim size, mlp ratio etc. and systolic array params include array
size, dataflow, etc.

###  3.1. PIVOT Inference with Low and High Efforts

During PIVOT’s inference, we use the entropy metric to determine the number of
attentions required to classify an input (Li et al., 2023). The entropy,
$E(x)$, for an input $x$ (belonging to a dataset with $K$ classes) is
calculated using Equation 3. Here, $\pi(\bm{y}|\bm{x})$ is the logit output of
the ViT. The term $1/\log K$ normalizes the final entropy to $(0,1]$.

(3) $E(\bm{x})=-\frac{1}{\log
K}\sum_{i=1}^{K}\pi(\bm{y}_{i}|\bm{x})\log\pi(\bm{y}_{i}|\bm{x}).$

The entropy measures the confidence of prediction. For example, if all classes
have an equal probability of $\frac{1}{K}$, the entropy value will be 1,
implying uncertainty in the prediction. Whereas, if one class’s prediction
probability reaches 1 while the other classes attain 0 probability, the
entropy reaches 0 implying confident prediction.

As shown in Fig. 2a, during inference, PIVOT uses a combination of two
efforts: 1) Low Effort and 2) High Effort. Here, Effort is defined as the
number of active attention modules (attentions that are not skipped) in the
ViT. First, all inputs are inferred with the low effort resulting in the logit
outputs ($\pi(\bm{y}|\bm{x})$) and the entropy values ($E(x)$). For inputs
with entropy values lower than the threshold ($Th$), the $\pi(\bm{y}|\bm{x})$
from the low effort ViT are used for class prediction. For inputs with
$E(x)>Th$, an additional inference is performed with high effort and then, all
inputs are inevitably classified. In Fig. 2a, $F_{L}$ and $F_{H}$ are defined
as the fraction of inputs classified by low ($E(x)<Th$) and high effort
($E(x)>Th$), respectively. Additionally, the number of inputs correctly
(incorrectly) classified with low and high efforts are denoted as $C_{L}$
($I_{L}$) and $C_{H}$ ($I_{H}$), respectively. The $C_{L}$ and $C_{H}$ values
are used to compute the accuracy.

Re-computation Overhead: During inference, some of the inputs that are
unclassified with the low-effort are re-inferred with the high effort which
entails re-computation overhead that needs to be managed to obtain a tradeoff
between accuracy vs. efficiency.

###  3.2. PIVOT Phase1: Optimal Path Selection

PIVOT uses a two-phase hardware-in-the-loop search to design the multi-effort
ViT. In Phase1, we select the optimal path for different efforts for a given
ViT. Each effort contains multiple Paths. For example, as shown in Fig. 2b, a
ViT with 5 encoders and Effort=3 entails ${5\choose 3}=10$ possible paths.
Here, a Path is uniquely defined by the position of encoders with active and
inactive attention modules. Having large number of paths for each effort
increases the search space size in Phase2. Therefore, we define a Path-Score
(shown in Algorithm 1) metric to single-out the Optimal Path (shown in yellow)
corresponding to each effort. The path with the highest Path-Score
($\mathcal{S}$) is chosen as the Optimal Path and trained with the loss
function shown in Fig 2b. The loss function contains cross-entropy loss
${L_{CE}}$, and the distillation loss ${L}_{Distill}$ between the final layer
features of the teacher and student ViT. The $L_{CE}$ and $L_{Distill}$ are
commonly used in prior works to train high performance ViTs (Touvron et al.,
2021; Jiang et al., 2021). In PIVOT, to improve the prediction confidence, we
add the regularization term $L_{En}$ that lowers the entropy for the correctly
classified inputs. $L_{En}$ is the mean of the entropy values for the
correctly classified inputs. Lowering the entropy ensures increased confident
classifications with low efforts and thereby improves the inference
efficiency.

Figure 3. (a) $CKA~{}Matrix$ computed between the MLP output of $Encoder_{i}$
($MLP_{i}$) and Attention output of $Encoder_{i+1}$ ($A_{i+1}$) for the DeiT-S
ViT (b) Higher $CKA(MLP_{i},A_{i+1})$ suggests data redundancy and the
attention can be skipped.

CKA Matrix Fig. 3a shows the center kernel alignment matrix ($CKA~{}Matrix$)
comprising of the CKA values computed between MLP outputs ($MLP_{i}$) and
attention outputs ($A_{i+1}$) of ViT encoders $Encoder_{i}$ and
$Encoder_{i+1}$, respectively. CKA measures the similarity between two
matrices (Cortes et al., 2012). A high $CKA(MLP_{i},A_{i+1})$ value implies
high similarity in $MLP_{i}$ and $A_{i+1}$ outputs, thus suggesting that
output $MLP_{i}$ can be directly forwarded to $MLP_{i+1}$ by skipping
$A_{i+1}$ as shown in Fig. 3b (top). Contrarily, for a low
$CKA(MLP_{i},A_{i+1})$ value, the attention cannot be skipped as shown in Fig.
3b (bottom).

Input: Effort Configuration ($Config$), #Encoders in ViT ($D$),
$CKA~{}Matrix$.

Output: Path-Score $(\mathcal{S})$

1 $\mathcal{S}=0$;

2 for  _$i$ $\epsilon$ $Config$_ do

3 for  _$j$ $\epsilon$ ($i+1$, $D$)_ do

4

5 if  _( $A_{j}$ is $Inactive$)_ then

6 $\mathcal{S}$ = $\mathcal{S}+CKA~{}Matrix(i,j)$;

7

8 else

9 break;

10

11

12

Algorithm 1 Path-Score Computation Algorithm Figure 4. (a) Path Accuracy vs.
Path-Score ($\mathcal{S}$) corresponding to Effort = 6 for DeiT-S ViT. (b)
Design space size if random search is performed in Phase2, without selecting
optimal path for each effort in Phase1 (size normalized to PIVOT’s design
space size) (c) GPU hours for training DeiT-S, LVViT-S and PIVOT Efforts
(normalized to GPU hours required for training DeiT-S from scratch).

Path-Score ($\mathcal{S}$): Algorithm 1 shows the methodology to compute
$\mathcal{S}$. Algorithm 1 requires the $CKA~{}Matrix$ (shown in Fig. 3a) and
the effort configuration ($Config$), containing encoder locations with active
and inactive attention. The $CKA~{}Matrix$ is generated for a small batch of
256 images. For a given $Config$, $\mathcal{S}$ is computed by summing up the
CKA values between the MLP outputs ($MLP$) of the encoders with active
attention and the attention outputs ($A$) of the encoders with inactive
attention. For example, $\mathcal{S}$ for $Config=$
[1,2,3,4,5,6,7,8,9,10,11,12], where encoder indices of inactive attentions are
denoted by cyan can be computed as
$CKA[MLP_{2},A_{3}]+CKA[MLP_{2},A_{4}]+CKA[MLP_{8},A_{9}]+CKA[MLP_{8},A{10}]$.
A high $\mathcal{S}$ signifies that the path contains highly redundant
attentions that can be easily pruned out. Fig. 4a shows the positive
correlation between $\mathcal{S}$ and path accuracy. As high $S$ paths ensure
pruning the most redundant attention blocks, they attain higher accuracy.

###  3.3. PIVOT Phase2: Selecting Optimal Effort Combinations

In Phase2, given a set of efforts with optimal paths (shown in blue in Fig.
2c), PIVOT determines the right effort combination to achieve optimal accuracy
while meeting the user-provided delay requirement. 1) First, we start with a
pair of low and high efforts (say, Effort 9 and Effort 12). 2) Next, the
threshold values $Th$ for the low effort inference is chosen. The $Th$ values
are iterated in an incremental manner. 3) A small batch of data (randomly
sampled batch of 256 images from the training set) is inferred with the low
and high efforts. This generates the $C_{L}$, $C_{H}$, $F_{L}$ and $F_{H}$
values. 4) Following this, the accuracy calculator uses $C_{L}$ and $C_{H}$ to
compute the accuracy (Fig. 2a). The thresholds are iterated until the
condition $F_{L}\geq LEC$ is met. Higher $LEC$ value ensures more inputs
classified by the low effort ViT. 5) The low ($Config_{L}$), high
($Config_{H}$) effort configurations, $F_{L}$ and $F_{H}$ values are passed to
the PIVOT-Sim framework for delay computation. The PIVOT-Sim platform first
computes the delays of low and high efforts ($D_{L}$ and $D_{H}$,
respectively) using $Config_{L}$, $Config_{H}$, ViT and systolic array
parameters (Refer Section 3.4). Then, it computes the delay of the effort
combination using $D_{L}$, $D_{H}$, $F_{L}$ and $F_{H}$. If the delay lies
within 5% of the user-provided delay constraint, the optimal effort
combination is obtained. If the delay constraint is not met, a new effort
combination (say, Effort 6 and Effort 9) is selected. In order to achieve high
accuracy, the sampling starts with efforts containing maximum active
attentions. In each iteration, a smaller effort combination is sampled than
the previous iteration until the desired delay is obtained.

Benefit of CKA Score-based Optimal Path Selection In Fig. 4b, we compare the
Phase2 design space size of random and PIVOT-based search. Since PIVOT uses
the Path-score to single out the optimal path for each effort, there exists
only one path for each effort combination. Whereas, Phase2 with random search
entails multiple paths due to the absence of optimal path selection. For
example, in random search as shown in Fig. 4b, effort combinations [3,6] can
contain ${12\choose 3}\times{12\choose 6}=2.03\times 10^{5}$ possible paths
for the DeiT-S ViT. For the DeiT-S ViT Phase2 with random search, the search
space size is $\sim 10^{5}\times$ higher than PIVOT’s search space size.

GPU Hours for Training all Efforts: Fig. 4c shows that the combined GPU hours
required for training all efforts (see Section 4.1) for DeiT-S (LVViT-S) ViTs
in PIVOT is 3$\times$ (2$\times$) less compared to training the DeiT-S
(LVViT-S) ViT from scratch. This is because, the training time reduces with
reduction in the ViT effort.

###  3.4. PIVOT-Sim Platform

Figure 5. Figure showing the PIVOT-Sim Platform.

Fig. 5 shows the overall architecture of the PIVOT-Sim platform. PIVOT-Sim
performs cycle-accurate delay estimation for a given ViT effort mapped on a
Xilinx ZCU102 MPSoC FPGA-based systolic array accelerator. Like the ZynQ MPSOC
FPGA, PIVOT-Sim contains two systems: 1) ZynQ MPSoC Processing System (PS) and
2) ZynQ MPSoC programmable logic (PL). All the linear matrix multiplication
layers (QKV, QKT, SMxV, Proj and MLP) are executed in the PL-implemented
systolic accelerator. Inputs and weights are first loaded from the PS DRAM to
the global SRAM buffer (GB) in the PL. Then the weights and inputs are fetched
from GB to the Weight SRAM (WTMEM) and Input SRAM (IPMEM), respectively. Then,
the weights from the WTMEM are loaded in to the PE array in a streaming
fashion following which, the inputs are fetched from the IPMEM in a streaming
fashion column by column. The multiply-and-accumulate (MAC) outputs are stored
in the output SRAM (OPMEM). The outputs are pushed to the GB and finally to
the DRAM. The non-linear operations such as softmax, entropy and GeLU are
implemented using the ZynQ MPSoC PS.

The PIVOT-Sim framework requires the ViT parameters (embedding dimension size,
number of tokens, mlp ratio and attention head count) and systolic array
parameters (array dimensions, dataflow, SRAM memory sizes, and the clock
frequency) and the low (high) effort configurations $Config_{L}$
($Config_{H}$) (discussed in Section 3.2) to compute the low (high) effort
delays $D_{L}$ ($D_{H}$). Additionally, it also computes the delay of low-high
effort combination using the $F_{L}$, $F_{H}$, $D_{L}$ and $D_{H}$ values as
shown in Fig. 5. The $D_{L}\times F_{H}$ term in the delay computation
accounts for the re-computation overhead. The energy is obtained by
multiplying the power with the delay of the effort combination.

Entropy Computation Overhead We find that entropy computation (Equation 3) in
the ZynQ MPSoC PS takes 0.03ms per image which is $<0.05\%$ of the inference
delay and thus, can be ignored.

##  4\. Experiments and Results

###  4.1. Experimental Setup

Datasets and ViTs: We benchmark all our results on the standard Imagenet-1K
dataset using state-of-the-art efficient ViTs such as DeiT (Touvron et al.,
2021) and LV-ViT (Jiang et al., 2021). Baseline: For all experiments, the
baseline is a ViT model without any effort modulation i.e., all ViT attention
modules will be activated irrespective of the input difficulty. PIVOT-
Optimized ViTs: For ease of expression, throughout the text, we will refer to
PIVOT-optimized DeiT-S and LVViT-S ViT as PVDS and PVLS, respectively.

Traning Details: In PIVOT, for the DeiT-S and LVViT-S ViTs, we create 7 (3, 4,
5, 6, 7, 8 and 9) and 9 (4, 5, 6, 7, 8, 9, 10, 11, 12) efforts, respectively.
Each effort is finetuned for 30 epochs with the full training data. The ViTs
are trained with 8-bit quantization. Training all the efforts is 3$\times$
(2$\times$) more efficient than training a DeiT-S (LVViT-S) ViT from scratch
(see Fig. 4c). For training we use Pytorch 1.3.1 with a single Nvidia V100 GPU
backend.

Hardware Evaluation: All baselines and PIVOT-optimized ViTs (PVDS and PVLS)
are evaluated using the PIVOT-Sim framework. The FPGA implementation
parameters for PIVOT-Sim are shown in Table 1. The FPGA implementation
requires 4566 LUTs, 20668 Registers, 48 Block RAMs and 2304 digital signal
processing cores.

FPGA Board | Xilinx ZCU102
---|---
Global SRAM (GB) Size | 16KB
IPMEM, WTMEM, OPMEM | 64Kb, 64Kb, 64Kb
PE Array Size |  64$\times$36
Clock Frequency | 125MHz
Dataflow | Input Stationary

Table 1. Table showing the FPGA implementation parameters.

###  4.2. Results on DeiT-S and LVViT-S ViTs

Table 2. Table comparing the performance of DeiT-S and PIVOT-optimized DeiT-S
ViTs (PVDS-$N$) sampled at delay=$N$.

Model |  Energy (J) |  Delay (ms) |  Power (W) |  EDP (J$\times$ms) | FPS/W |  Accuracy (%)
---|---|---|---|---|---|---
DeiT-S | 0.47 | 59.66 | 7.92 | 28.19 |  2.14(1$\times$) | 79.8
PVDS-50 |  0.38 (1.23$\times$) |  48.47 ($1.23\times$) | 7.92 |  16.21 (1.73$\times$) |  2.7(1.23$\times$) | 79.4
PVDS-35 |  0.292 (1.62$\times$) |  36.9 ($1.61\times$) | 7.92 |  10.5 (2.6$\times$) |  3.4(1.61$\times$) | 78.2

Table 3. Table comparing the performance of LVViT-S and PIVOT-optimized
LVViT-S ViTs (PVLS-$N$) sampled at delay=$N$.

Model |  Energy (J) |  Delay (ms) |  Power (W) |  EDP (J$\times$ms) | FPS/W |  Accuracy (%)
---|---|---|---|---|---|---
LVViT-S | 0.63 | 79.55 | 7.92 | 50.8 |  1.57(1$\times$) | 82.8
PVLS-50 |  0.410 (1.57$\times$) |  50 ($1.6\times$) | 7.92 |  20.13 (2.7$\times$) |  2.51(1.6$\times$) | 82.6
PVLS-35 |  0.312 (2.17$\times$) |  36.5 ($2.17\times$) | 7.92 |  10.57 (4.5$\times$) |  3.4(2.17$\times$) | 81.1

Table 2 and Table 3 compare the delay, energy-delay-product (EDP), energy
efficiency (FPS/W) and the accuracy of different PVDS and PVLS ViTs searched
at different target delays lesser than the baseline. Evidently, as seen in
Table 2 the PVDS-50 (PVLS-50) ViTs achieve 1.73$\times$ (2.7$\times$) EDP
reduction, 1.23$\times$ (1.6$\times$) higher FPS/W with merely 0.4% (0.2%)
accuracy reduction compared to the baseline DeiT-S (LVViT-S). At a slightly
higher accuracy reduction of 1.6% (1.7%) the PVDS-35 (PVLS-35) yields
2.6$\times$ (4.5$\times$) lower EDP and 1.62$\times$ (2.17$\times$) higher
FPS/W compared to baseline.

Figure 6. (a) Delay breakdown across encoder modules for different ViTs (b)
Energy breakdown across the PE Array, Periphery and SRAM (part of the ZynQ
MPSoC PL) and the PS (ZynQ MPSoC PS).

Fig. 6a shows the delay distributions across the Attention MAC (QKV, QKT,
(SMxV) and Proj), Softmax and MLP modules (refer Fig. 1a). Interestingly, the
softmax module consumes 60% (63%) of the overall delay in the DeiT-S (LVViT-S)
ViTs. With PIVOT, the softmax overhead reduces to 43% (48%) for the PVDS-50
(PVLS-50) ViTs. Similarly, the Attention MAC overhead reduces to 13% (14%) in
the PVDS-50 (PVLS-50) ViTs compared to 18% (19%) in DeiT-S (LVViT-S) ViTs.
Note, since PIVOT does not skip MLP modules, the delay overhead of MLP in
PVDS-50 (PVLS-50) increase by 21% (19%) compared to the baselines due to the
re-computation overhead (refer Section 3.1). However, due to high delay
reduction in softmax and attention MAC modules, PIVOT achieves an overall
delay reduction.

Energy Reduction across FPGA Resources: As seen in Fig. 6b, delay reduction in
PVDS-50 and PVLS-50 ViTs lead to an energy reduction across the ZynQ MPSoC PS
and PL systems. PVDS-50 and PVLS-50 ViTs achieve around 2$\times$ energy
reduction in the PS and 1.6$\times$, 1.7$\times$ and 1.8$\times$ energy
reduction in the PE-Array, SRAM memories and peripheral circuits, respectively
implemented on the ZynQ MPSoC PL (See Section. 3.4). The peripheral circuits
(periphery) include PS-PL interconnects, reset and memory controllers.

###  4.3. Comparison with Prior Works

Table 4. Performance comparison of ViTCOD (You et al., 2023), HeatViT (Dong et
al., 2023) and PVDS-50.

Work |  ViTCOD (You et al., 2023) |  HeatViT (Dong et al., 2023) | PIVOT (Ours)
---|---|---|---
ViT Backbone | DeiT-S | DeiT-S | DeiT-S
Effort Modulation | Constant | Constant | Input-aware
Prediction | Norm | Head | Entropy
Mechanism | Score | Level | Metric
Quantization | 8-bits | 8-bits | 8-bits
Accuracy | 78.1% | 79.1% | 79.4%
GPP Compatible | $\times$ | $\times$ | ✓

Table 4 performs a holistic comparison between PIVOT and prior state-of-the-
art algorithm-hardware co-design frameworks (Dong et al., 2023; You et al.,
2023). Soft token pruning in HeatViT (Dong et al., 2023) achieves a high token
pruning ratio of 40%, 74% and 87% in encoders 4-6, 7-9, and 10-12,
respectively, while achieving 79.1% accuracy. ViTCOD (You et al., 2023)
achieves 90% attention sparsity ratio at 78.1% accuracy. Accuracy advantage in
PIVOT: HeatViT (Dong et al., 2023) and ViTCOD (You et al., 2023) do not
modulate their efforts based on the input difficulty (token and attention
sparsity ratios remain constant for all inputs). Therefore, at high token and
attention pruning ratios, the accuracy suffers as difficult images are wrongly
classified. Whereas, due to input-awareness, PIVOT (PVDS-50) achieves the
highest accuracy of 79.4%.

Figure 7. Compute and overhead delay breakdowns for DeiT-S baseline, HeatViT
(Dong et al., 2023), ViTCOD (You et al., 2023) and PIVOT (PVDS-50) across (a)
Nvidia V100, NVidia RTX2080ti and Nvidia Jetson Orin Nano (b) Intel Xeon and
Raspberry Pi 4.

Evaluation on GPPs: As HeatViT (Dong et al., 2023) and ViTCOD (You et al.,
2023) require special hardware support for efficient implementation, we
perform the delay comparison on GPPs such as CPUs- Intel Xeon, Raspberry Pi,
and GPUs- Nvidia V100, Nvidia RTX2080ti and Nvidia Jetson Orin Nano for a fair
comparison. As seen in Fig. 7a and Fig. 7b, the PIVOT (PVDS-50) achieves
around 1.2-1.5$\times$ lower delay compared to the baseline across all GPPs.
Since ViTCOD requires sparse matrix multiplication support, the delay on GPP
is similar to the baseline. Due to hefty predictor networks and token
packaging modules for soft token pruning, HeatViT (Dong et al., 2023) entails
significant delay overhead when implemented on GPPs. PIVOT is general purpose
and entails a small overhead of 6% in the delay. This delay is majorly
contributed by the re-computation overhead. The contribution of entropy
computation (Equation 3) is negligibly small ($<0.05\%$).

###  4.4. Analysis with $LEC$ Constraints

Figure 8. Figure analysing the effect of different $LEC$ on the EDP and
accuracy for different effort combinations. (b) EDP distribution between the
low effort, high effort and the re-computation overhead (Overhead) for the
PVDS-50 ViT.

From Fig. 8 we find that $LEC=70$ and $LEC=80$ attain the best EDP and
accuracy tradeoff across different PVDS ViTs. At low $LEC=60$, the EDP is high
as merely 60% of the inputs are classified by the low effort. Additionally,
$LEC=90$ entails 90% of the inference with low effort but this leads to a
significant accuracy degradation.

The EDP is contributed by the low effort and high effort inference, and the
re-computation overhead (Section 3.1). At low $LEC$ values, both high-effort
and re-computation EDPs are high while the low effort EDP is less. As the
$LEC$ value increases, the low effort EDP increases marginally while the high
effort and re-computation EDP reduce significantly leading to overall low
EDPs.

Need for Input difficulty awareness As seen in Fig. 8a for $LEC=100$, all
inputs are inferred by the low effort. This leads to low EDP at the cost of
accuracy since the efforts are not modulated for difficult inputs. Therefore,
PIVOT’s input-aware effort modulation achieves optimal accuracy-efficiency
tradeoffs.

###  4.5. Efforts Combinations for Different Delays

Figure 9. Different PVDS ViTs sampled by PIVOT at different delay constraints.

As seen in Fig. 9, reduction in the delay requirement lowers the number of
active attentions in the ViT. The efforts shown here represent the optimal
path with the highest Path-score for each effort. Interestingly, we observe
that across all efforts, attentions skipping is preferred in the deeper layers
as the $CKA(MLP,A)$ value is higher in the latter layers.

##  5\. Conclusion

PIVOT motivates ViT attention optimization in an input difficulty-aware
manner. PIVOT’s input-awareness yields 0.4%-1.3% higher accuracy compared to
prior token pruning and attention sparsification works. Unlike prior works,
PIVOT is GPP compatible and yields 1.2-1.5$\times$ higher throughput compared
to baseline ViT across different CPU/GPU platforms. Additionally, PIVOT-Sim-
an end-to-end open source FPGA-based evaluation platform is developed that
will motivate future ViT-hardware co-optimization works.

## Acknowledgement

This work was supported in part by CoCoSys, a JUMP2.0 center sponsored by
DARPA and SRC, the National Science Foundation (CAREER Award, Grant #2312366,
Grant #2318152), and the DoE MMICC center SEA-CROGS (Award #DE-SC0023198)

## References

  * (1)
  * Bhattacharjee et al. (2022) Bhattacharjee et al. 2022\.  MIME: adapting a single neural network for multi-task inference with memory-efficient dynamic pruning. In _Proceedings of the 59th ACM/IEEE Design Automation Conference_. 499–504.
  * Cortes et al. (2012) Cortes et al. 2012\.  Algorithms for learning kernels based on centered alignment.  _The Journal of Machine Learning Research_ 13, 1 (2012), 795–828.
  * Dehghani et al. (2023) Dehghani et al. 2023\.  Scaling vision transformers to 22 billion parameters. In _International Conference on Machine Learning_. PMLR, 7480–7512.
  * Dong et al. (2023) Dong et al. 2023\.  Heatvit: Hardware-efficient adaptive token pruning for vision transformers. In _2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE, 442–455.
  * Dosovitskiy et al. (2020) Dosovitskiy et al. 2020\.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ (2020).
  * Han et al. (2022) Han et al. 2022\.  A survey on vision transformer.  _IEEE transactions on pattern analysis and machine intelligence_ 45, 1 (2022), 87–110.
  * Jiang et al. (2021) Jiang et al. 2021\.  All tokens matter: Token labeling for training better vision transformers.  _Advances in neural information processing systems_ 34 (2021), 18590–18602.
  * Kim et al. (2021) Kim et al. 2021\.  Rethinking the self-attention in vision transformers. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 3071–3075.
  * Li et al. (2023) Li et al. 2023\.  Input-aware dynamic timestep spiking neural networks for efficient in-memory computing. In _2023 60th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 1–6.
  * Panda et al. (2016) Panda et al. 2016\.  Conditional deep learning for energy-efficient and enhanced pattern recognition. In _2016 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 475–480.
  * Rao et al. (2021) Rao et al. 2021\.  Dynamicvit: Efficient vision transformers with dynamic token sparsification.  _Advances in neural information processing systems_ 34 (2021), 13937–13949.
  * Samajdar et al. (2018) Samajdar et al. 2018\.  Scale-sim: Systolic cnn accelerator simulator.  _arXiv preprint arXiv:1811.02883_ (2018).
  * Stevens et al. (2021) Stevens et al. 2021\.  Softermax: Hardware/software co-design of an efficient softmax for transformers. In _2021 58th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 469–474.
  * Touvron et al. (2021) Touvron et al. 2021\.  Training data-efficient image transformers & distillation through attention. In _International conference on machine learning_. PMLR, 10347–10357.
  * Wang et al. (2021) Wang et al. 2021\.  Spatten: Efficient sparse attention architecture with cascade token and head pruning. In _2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE, 97–110.
  * Wu et al. (2018) Wu et al. 2018\.  Blockdrop: Dynamic inference paths in residual networks. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 8817–8826.
  * You et al. (2023) You et al. 2023\.  Vitcod: Vision transformer acceleration via dedicated algorithm and accelerator co-design. In _2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE, 273–286.


# High Quality Related Search Query Suggestions using Deep Reinforcement
Learning

Praveen Kumar Bodigutla<EMAIL_ADDRESS>LinkedIn1000 W Maude
AveSunnyvaleCaliforniaUSA94085

###### Abstract.

“High Quality Related Search Query Suggestions” task aims at recommending
search queries which are real, accurate, diverse, relevant and engaging.
Obtaining large amounts of query-quality human annotations is expensive. Prior
work on supervised query suggestion models suffered from selection and
exposure bias, and relied on sparse and noisy immediate user-feedback (e.g.,
clicks), leading to low quality suggestions. Reinforcement Learning techniques
employed to reformulate a query using terms from search results, have limited
scalability to large-scale industry applications.

To recommend high quality related search queries, we train a Deep
Reinforcement Learning model to predict the query a user would enter next. The
reward signal is composed of long-term session-based user feedback, syntactic
relatedness and estimated naturalness of generated query. Over the baseline
supervised model, our proposed approach achieves a significant relative
improvement in terms of recommendation diversity ($3\%$), down-stream user-
engagement ($4.2\%$) and per-sentence word repetitions ($82\%$).

query suggestions, deep reinforcement learning, text generation

††copyright: rightsretained††conference: Marble-KDD ’21; August 16, 2021;
Singapore††ccs: Theory of computation Reinforcement learning††ccs: Information
systems Query suggestion

##  1\. Introduction

Related search query suggestions aims at suggesting queries that are related
to the user’s most recent search query. For example, search query “machine
learning jobs” is related to “machine learning”. These suggestions are
important to improve the usability of search engines (Cao et al., 2008). We
define high-quality related search query suggestions as query recommendations
which are natural (i.e., entered by a real user), diverse, relevant, error-
free and engaging.

Sequence-to-Sequence (Seq2Seq) encoder-decoder architectures are widely used
to generate query suggestions (Wang et al., 2020; Nogueira and Cho, 2017; Yu
et al., 2017; Kazi et al., 2020). Supervised autoregressive generative models
trained with ground-truth labels suffer from exposure bias (Yu et al., 2017;
Schmidt, 2019). Maximum Likelihood Estimation (MLE) training generates
repetitive sequences (Li et al., 2016). Machine learning approaches (Kazi et
al., 2020; Li et al., 2019) that are trained on immediate user feedback, such
as click on recommended query, are prone to selection-bias (Wang et al.,
2016). Reinforcement Learning techniques were proposed to address these
limitations (Wang et al., 2020).

“Local” Deep-Reinforcement-Learning (DRL) frameworks for query reformulation
(Wang et al., 2020; Nogueira and Cho, 2017) adjust a query relative to the
initial search results. Reward signals used in these approaches were computed
from mined search result documents. Processing search results to reformulate
the query and mining entire collection of documents is not practical in large-
scale real-world applications, due to rapidly changing and ever-growing user-
generated content. Hence, we employ “global” DRL approaches (Nogueira and Cho,
2017), that are independent of the set of documents returned by the original
query and instead depend on the actual queries entered by the users and the
feedback provided by them. Furthermore, we choose the more useful approach to
predict the queries a user will enter next, over simply reformulating the
current query (Cao et al., 2008). We mine search sessions and corresponding
co-occuring query pairs from LinkedIn search engine logs. Unlike general
purpose web search, our work is focused on domain-specific-search queries
(Tang et al., 2006), that users enter to search for job postings, people
profiles, user-groups, company pages and industry news.

DRL text generation approaches such as policy-gradient based Sequential
Generative Adversarial Networks (SeqGAN) (Yu et al., 2017) achieved excellent
performance on generating creative text sequences. Most recently, on summary
generation task, fine-tuning pre-trained supervised model using Proximal
Policy Optimization (PPO) (Schulman et al., 2017) method outperformed
supervised GPT3 (Brown et al., 2020) model 10x its size (Stiennon et al.,
2020). Motivated by the performance improvements achieved by DRL techniques on
text-generation problems, we solve the high quality query suggestions problem
by modeling the query generator as a stochastic parametrized policy.
Specifically, we fine-tune the state-of-the-practice Seq2Seq Neural Machine
Translation (NMT) model (Bahdanau et al., 2015) for query generation (Kazi et
al., 2020), using policy-gradient REINFORCE (Williams, 1992) algorithm.
Seq2Seq NMT models are widely popular in industry applications, especially in
low resource environments(Ganegedara, 2020).

Supervised reward estimation models are commonly used to optimize text-
generation policy (Wang et al., 2020; Nogueira and Cho, 2017; Stiennon et al.,
2020; Yu et al., 2017). SeqGAN model used GAN (Goodfellow et al., 2014)
discriminator output as reward signal. The supervised discriminator model
predicted if the generated sequence is “real”. The estimated reward is passed
back to the intermediate state-action steps using computationally expensive
Monte Carlo search (Chaslot et al., 2008). PPO based summary generation model
(Stiennon et al., 2020) used estimated annotated user feedback on generated
summaries as the reward signal. Immediate implicit user feedback is sparse,
asking users to provide explicit feedback is intrusive (Bodigutla et al.,
2019) and reliable annotations are expensive to obtain.

In our proposed approach, the DRL future-reward is composed of three signals,
which are: 1) long-term implicit user-feedback within a search-session; 2)
unnatural query generation penalty; and 3) syntactic similarity between
generated query and user’s most recent search query. Leveraging implicit user-
feedback from search-sessions as opposed to using immediate feedback, helps in
maximizing user engagement across search-sessions, addresses the reward-
sparsity problem and removes the need to obtain expensive human annotations
(Section 2.2.2). We design a weakly supervised context-aware-naturalness
estimator model, which estimates the naturalness probability of a generated
query. Similar to (Yu et al., 2017) we perform Monte Carlo search to propagate
rewards. However, we reduce the computation cost considerably by performing
policy roll-out only from the first time-step of the decoder (Section 2.2.1).

In summary, we employ DRL policy-gradient technique for making high-quality
related-query suggestions at scale. Our proposed approach achieves improvement
in-terms of recommendation diversity, down-stream user-engagement, relevance
and errors per sentence. To the best of our knowledge, this is the first time
a combination of long-term session-based user-feedback, un-natural sentence
penalty and syntactic relatedness reward signals are jointly optimized to
improve query suggestions’ quality.

The remainder of this paper is structured as follows: Section 2 describes our
proposed deep reinforcement learning approach. Section 3.2 presents the
experimental setup and discusses empirical results. Section 4 concludes.

##  2\. Approach for Improving Query Suggestions

We fine-tune a weakly supervised Sequence-to-Sequence (Seq2Seq) Neural Machine
Translation (NMT) model ($Seq2Seq_{NMT}$) to initialize the query generation
policy. The process then consists of two steps: 1) Learn a context-aware
weakly supervised naturalness estimator; and 2) Fine-tune pre-trained
supervised $Seq2Seq_{NMT}$ model using REINFORCE (Williams, 1992) algorithm.
The future-reward is composed of user-feedback in a search session ($U_{+}$),
syntactic similarity ($ROUGE$) and unnaturalness penalty
($-\eta*(1-D_{\phi})$) of the generated query given the co-occuring previous
query.

Figure 1.  Deep Reinforcement Learning for text-generation using REINFORCE
algorithm. Agent is an encoder-decoder Seq2Seq attention model.
$q^{bk}_{i\\{1:T\\}}$ is the input query, for batch-index $b\epsilon B$ and
Monte-Carlo sample index $k\epsilon K$. Generated words ($y^{{1:B},1:K}_{t}$)
concatenated with attention context ($c_{t+1}$) is passed as input to the
decoder’s $t+1$ time-step. For each generated sequence ($y^{bk}_{1:T}$) policy
update is done using RL reward ($R^{bk}_{1:T}$), which is calculated at the
end of each generated sequence.

###  2.1. Weakly Supervised Pre-Training

Variants of mono-lingual supervised $Seq2Seq_{NMT}$ models are used in
industry applications for query suggestions [14]. In the pre-training step, we
train the supervised $Seq2Seq_{NMT}$ model using co-occurring consecutive
query pairs in a search sessions. A search-session (Cao et al., 2008) is a
stream of queries entered by a user in a 5-min111Based on guidance from
internal search team’s proprietary analysis. time window. N-1 Consecutive
query pairs ($q_{i}$, $q_{i+1}$) are extracted from a search session
consisting of a sequence of N queries ($q_{1}$, $q_{2}$,…,$q_{N}$).
Consecutive queries could be unrelated, semantically and (or) syntactically
related. Our model is weakly supervised as we use all query pairs and do not
filter them using sparse click data, costly human-evaluations and weak
association rules. Weak supervision allows the training process to scale,
minimize selection-bias and we conjecture that it improves model
generalization too. For example, unlike [14], we do not apply syntactic
similarity heuristics to filter query pairs, as queries could be semantically
related yet syntactically dissimilar (e.g., “artificial intelligence” and
“machine learning”) . The $Seq2Seq_{NMT}$ encoder-decoder framework consists
of a BiLSTM (Graves et al., 2013) encoder, that encodes a batch (batch-size
$B$) of input queries ($q^{1:B}_{i}$) and the LSTM (Hochreiter and
Schmidhuber, 1997) decoder generates a batched sequence of words y =
($y^{1:B}_{1}$,…, $y^{1:B}_{T}$). Where, $T$ is the sequence length. During
training, we use teacher forcing (Williams and Zipser, 1989), i.e., use the
co-occuring query ($q^{1:B}_{i+1}$) as input to the decoder. Context attention
vector is obtained from the alignment model (Bahdanau et al., 2015) .
Categorical cross entropy loss is minimized during training and hyper-
parameters of the model are fine-tuned (see Section 3.2).

###  2.2. Fine-tuning using Deep Reinforcement Learning

This section describes the reward estimation and Deep Reinforcement Learning
(DRL) model training steps to fine-tune and improve the policy obtained via
pre-trained supervised model.

####  2.2.1. Deep Reinforcement Learning Model.

Parameters of the DRL agent $G_{\theta}$ are initialized with pre-trained
$Seq2Seq_{NMT}$ model (Section 2.1). The initial policy is fine-tuned using
the REINFORCE policy-gradient algorithm (Figure 1). ‘$K$’ complete sentences
($y^{b,{1:K}}_{1:T}$) generated per query ($q^{b}_{i}$) constitute the action
space at time-step $T$, where $b\epsilon B$ is the index in a mini-batch of
$B$ queries. To mitigate exposure-bias, generated words ($y^{1:B,1:K}_{t-1}$)
from previous time-step are passed as input to the next time-step ‘$t$’ of the
decoder. Future-reward ($R_{D_{\phi}}(y^{bk}_{1:T})$) computed at the end of
each generated sample, is back-propagated to the encoder-decoder model. Given
the start-state ($S^{b}_{0}$) comprising of the input query ($q_{i}^{b}$) and
¡START¿ token $y^{b}_{0}$, the objective of the agent is to generate related-
search query suggestions ($y^{b}_{1:T}$) which maximize objective:

(1) $J(\theta)=\mathbb{E}[R_{D_{\phi}}(y^{b}_{1:T})|S^{b}_{0},\theta]\\\ \
\scriptsize$

Where per-sample reward is:

(2)
$R_{D_{\phi}}(y^{bk}_{1:T})=U_{+}+(1-U_{+})*(ROUGE_{q^{b}_{i},y^{bk}_{1:T}}-\eta*(1-D_{\phi}(y^{bk}_{1:T})))\scriptsize$

MC approximation of the gradient using likelihood ratio trick:

(3) $\Delta_{\theta}J(\theta)\approx\frac{1}{K}*\Sigma_{k\epsilon
K}[R_{D_{\phi}}(y^{bk}_{1:T})*\Delta_{\theta}log\,G_{\theta}(y^{bk}_{1:T}|S^{b}_{0})],\,\,\,y^{bk}_{1:T}\,\epsilon\,MC^{G_{\beta}}(y^{bk}_{1:T})\scriptsize$

Unlike SeqGAN (Yu et al., 2017) DRL model training, where the action-value at
each intermediate time-step $t$ is evaluated by generating $K$ samples
($y^{b,1:K}_{t+1:T}$), we perform MC policy roll-out from the start state
alone. $K$ queries ($y^{b,1:K}_{1:T}$) are generated using roll-out policy
$G_{\beta}$, for each input query $q_{i}^{b}$. This modification reduces the
computation cost by a factor of $\mathcal{O}(T)$
($\mathcal{O}(KT^{2})\rightarrow\mathcal{O}(KT)$) per input query. $G_{\beta}$
is initialized with $G_{\theta}$ and is periodically updated during training,
using a configurable schedule (see Algorithm 1). At each time-step $t$, the
state $S_{t}^{bk}$ is comprised of the input query and the tokens produced so
far ($\\{q_{i}^{b},y^{bk}_{1:t-1}\\}$) and the action is the next token
$y^{bk}_{t}$ to be selected from stochastic policy
$G_{\theta}(y^{bk}_{t}|S_{t}^{bk})$.

Details of the constituents of future-reward ($U_{+}$,
$ROUGE_{q^{b}_{i},y^{bk}_{1:T}}$ and $D_{\phi}(y^{bk}_{1:T})$) are in the next
section (Section 2.2.2). Since the expectation $\mathbb{E}[.]$ can be
approximated by sampling methods, we then update the generator’s parameters
with $\alpha$ as the learning-rate as:

(4) $\theta\leftarrow\theta+\alpha*\Delta_{\theta}J(\theta)\scriptsize$

Require: Generator policy $\displaystyle G_{\theta}$; roll-out policy
$\displaystyle G_{\beta}$ ;naturalness-estimator $\displaystyle
D_{\phi}$;Query-pair in a search session
$\displaystyle\left(q_{i\\{1:T\\}}^{1:B},\
q_{\\{i+1\\}\\{1:T\\}}^{1:B}\right)$; Batch size: B; MC sampling-strategy
$\displaystyle\epsilon\ $[beam-search, sampling from categorical distribution]
1\. Fine-tune supervised model using MLE with$\displaystyle\
q_{i\\{1:T\\}}^{1:B}\ $as input sequence and $\displaystyle
q_{\\{i+1\\}\\{1:T\\}}^{1:B}\ $as target sequence. 2\. Initialize
$\displaystyle G_{\theta}$ with fine-tuned supervised model. 3\.
$\displaystyle\beta\ \leftarrow\ \theta$ 4\. Train contextual-naturalness-
estimator $\displaystyle D_{\phi}$ using negative examples generated from
$\displaystyle G_{\theta}$ 5\. repeat
6\. for n steps 7\. foreach $\displaystyle b\ \epsilon\ B$ 8\. Generate ”K”
sequences $\displaystyle y_{1:T}^{b,\ 1:K}$ using configured sampling-strategy
$\displaystyle y_{1:T}^{b,\ 1:K}$ = $\displaystyle\left(y_{1}^{b,\ 1:K},\
y_{2}^{b,\ 1:K},\ ...,y_{T}^{b,\ 1:K}\right)\ \sim\ G_{\beta}\ \ \ $ 9\.
Compute future-reward at the end of each generated sequence $\displaystyle
R_{1:T}^{b,k}=\ U_{+}\ +\ (1\ -\ U_{+})\ *\
(ROUGE(q_{i\\{1:T\\}}^{b}$,$\displaystyle y_{\\{1:T\\}}^{b,k})\ -\
\eta*(1-D_{\phi}))$ 10\. Compute gradient $\Delta J(\theta)$ (Equation 3) 11\.
Update $\displaystyle G_{\theta}$ parameters via policy-gradient (Equation 4)
12\. end foreach
13\. end for 14\. $\displaystyle\quad\quad\beta\ \leftarrow\ \theta$ 15\.
until convergence Algorithm 1: Deep Reinforcement Learning algorithm for
related-search query suggestions.

####  2.2.2. Reward Formulation.

This section describes the three components of the future-reward
$R_{D_{\phi}}(y^{bk}_{1:T})$ , which are session based positive user-feedback
($U_{+}$), syntactic-similarity ($ROUGE_{q^{b}_{i},y^{bk}_{1:T}}$) and
unnatural suggestion penalty ($-\eta*(1-D_{\phi}(y^{bk}_{1:T}))$).

  * •

Long-term user-feedback in a search session ($U_{+}$): Viewing search-results
(dwell time ¿= 5 seconds 222Determined by internal domain-specific search
user-behavior analysis.) or performing an engaging action such as: sending a
connection request or a message; applying for a job; favoriting a group,
profile or an article, constitute positive implicit user actions in a search-
session. Immediate user-feedback is sparse. However, positive user action
percentage increases by absolute $11\%$333Computed over a set of ~100 million
query pairs extracted from search-sessions in one month window. Actual $\%$ of
positive user actions is not included due to confidentiality., when the
remainder of the search session after the user enters $q_{i+1}$ is considered.
In our work we maximize session-based user-feedback, as we are interested in
maximizing user engagement across search sessions. For a generated query
$y_{1:T}^{bk}$, session-based user feedback ($U_{+}$) is “1” , if a positive
down-stream user action is observed in the remainder of the search-session and
“0” otherwise.

  * •

Relatedness of generated query to source query
($ROUGE_{q^{b}_{i},y^{bk}_{1:T}}$): Despite increasing the percentage of
associated positive user action by considering user’s feedback across a search
session, the label sparsity problem is not completely mitigated. In the search
query logs, when there is no positive downstream user action associated with a
generated query $y^{bk}_{1:T}$, we estimate the reward using a syntactic
similarity measure. Reformulated queries are syntactically and semantically
similar (Lee et al., 2021). We compute syntactic relatedness of generated
query ($y^{bk}_{1:T}$) with the source query ($q^{b}_{i}$) using ROUGE-1 (Lin,
2004) score.

  * •

Naturalness probability of generated query ($D_{\phi}(y^{bk}_{1:T})$): Users
enter either natural language search queries(Borges et al., 2020) (e.g., “jobs
requiring databases expertise in the bay area” ) or they just enter key-words
(e.g., “bay area jobs database” ). In the context of related query
suggestions, we define a “natural” query as one which a real user is likely to
enter. We train a contextual-naturalness-estimation model (see Section 2.2.3)
to predict naturalness probability $D_{\phi}(y^{bk}_{1:T})$ of a generated
query, given the previous query entered by the user as context. “AI jobs” is
an example of a natural query after the user searched for “Google”, even
though both queries are syntactically and semantically (jobs vs company)
dissimilar. However, “AI AI jobs jobs” is unnatural and is unlikely to be
entered by a real user. In our DRL reward formulation, we add penalty term
$-\eta*(1-D_{\phi}(y^{bk}_{1:T}))$ to syntactic-relatedness
($ROUGE_{q^{b}_{i},y^{bk}_{1:T}}$) score to discourage generation of unnatural
queries. Coefficient $\eta$ is the configurable penalty weight.

####  2.2.3. Contextual Naturalness Estimator.

Our proposed contextual-naturalness-estimator is a BiLSTM (Graves et al.,
2013) supervised model, which predicts the probability a generated query is
“natural” ($D_{\phi}(y^{bk}_{1:T})$) . Concatenated with query-context
($q_{i}$), user entered queries ($q_{i+1}$) serve as positive examples
($q_{i}\oplus q_{i+1}$) to train the model. We employ four methods to generate
negative examples ($q_{i}\oplus q^{neg}_{i}$) per each positive example, which
are: 1) With $q_{i}$ as input, sample query $q^{neg}_{i}$ from fine-tuned
$Seq2Seq_{NMT}$ model’s decoder (Section 2.1); 2) perturb $q_{i+1}$ by
duplicating a word in randomly selected position within the sentence; 3)
replace a word with unknown word token (“¡UNK¿”) at a randomly selected
position in $q_{i+1}$; and 4) generate a sentence by repeating a sampled word
from a categorical distribution ($p_{w_{1}}...p_{w_{|V|}}$) for (randomly
chosen) $r\epsilon[1,T-1]$ times. —V— is the size of the training data
vocabulary, $p_{w_{i}}$ = $n_{w_{i}}/N_{|V|}$, $n_{w_{i}}$ is word ($w_{i}$)
frequency and $N_{|V|}=\Sigma_{w_{i}\epsilon|V|}n_{w_{i}}$. Methods $1$, $2$
and $3$ generate hard-negative examples (Lee et al., 2021) and $4$ captures
popularity-bias (Abdollahpouri, 2019), a situation where popular terms are
generated more often than terms in long-tail.

To validate our hypothesis that sampled queries from $Seq2Seq_{NMT}$ are less
natural than the ones provided by the user, we asked three annotators to rate
$100$ randomly sampled query pairs ($q_{1},q_{2}$). Query $q_{1}$ is entered
by the user and $q_{2}$ is either sampled from a supervised model ($46\%$) or
was entered by the user ($54\%$) after searching for $q_{1}$. Without
revealing the source of $q_{2}$, we asked annotators to identify if the query
is “natural” (defined in Section 2.2.2) . On an average $58\%$ of model-
generated queries and $74\%$ of real-user queries were identified as natural.
The Inter Annotator Agreement (IAA), measured using Fleiss-Kappa (Schouten,
1986), was poor ($0.04$) when the users evaluated model-generated sentences.
In comparison, when they evaluated queries entered by real users, IAA was
better ($0.34$) between the three annotators’ ratings and it ranged from fair
($0.22$) to moderate ($0.52$) agreement between each pair of annotators.
Higher IAA and higher percentage of queries identified as “natural” imply that
real-user queries are more natural and distinguishable than queries sampled
from pre-trained $Seq2Seq_{NMT}$ model.

##  3\. Experiment Setup and Results

This section describes the experimental setup to train and evaluate the
naturalness-estimator, supervised and DRL query generation models.

###  3.1. Data

From user search-query logs, we randomly sampled 0.61 million (90% train), 34k
(5% valid) and 34k (5% test) query pairs to train the supervised
$Seq2Seq_{NMT}$ and DRL models. Dataset size to train the naturalness-
estimator model is 5x the aforementioned amount (See Section 2.2.3). Max-
length of a query is 8 and mean-length is ~2 words. Vocabulary size is 32k and
out of vocabulary words in validation and test sets are replaced with “¡UNK¿”
unknown-token.

###  3.2. Experimental Setup

We implemented all models in Tensorflow (Abadi et al., 2015) and tuned the
parameters using Ray[Tune] (Liaw et al., 2018) on Kubernetes (kubernetes.io,
2020) distributed cluster. As described in Section 2, the query suggestion
policy is initialized with fine-tuned $Seq2Seq_{NMT}$ model. $Seq2Seq_{NMT}$
model parameters are updated using Adam (Kingma and Ba, 2015) optimizer and
categorical-cross-entropy loss is minimized during training. During inference,
six444In production environment six related queries are suggested for each
user query. queries are generated per input query ($q_{i}$) using beam-search
(Freitag and Al-Onaizan, 2017) decoding. Negative examples to train the two-
layered BiLSTM contextual-naturalness-estimator are obtained from pre-trained
$Seq2Seq_{NMT}$ model. At inference, naturalness probability
($D_{\phi}(y^{bk}_{1:T}$)) is obtained from the output of fully-connected
layer with last time-step’s hidden state as its input.

The initial policy is fine-tuned using REINFORCE policy-gradient algorithm,
using future-reward described in Section 2.2.2. During training, “K” samples
for MC roll-out are generated using beam-search or from categorical
distribution of inferred word probabilities at each time-step (See Figure 1).
DRL model training stability is monitored using reward weighted Negative Log
Likelihood convergence performance, with $\frac{1}{KB}\Sigma_{(k\epsilon
K,b\epsilon B)}[-R_{D_{\phi}}(y^{bk}_{1:T})*log(G_{\theta}(y^{bk}_{1:T}))]$ as
the computed loss at each model training step.

We use SGD optimizer (Kiefer and Wolfowitz, 1952) to update the weights of the
agent (Equation 4). Appendix Figure 2 shows the convergence performance of the
DRL model for different values of unnaturalness penalty ($\eta$), number of MC
samples ($K$) and choice of sampling strategy. Complete set of hyper-
parameters we tuned are in Appendix Table A. Best combination of hyper-
parameters are chosen are based on performance on validation set (See Appendix
Table A).

###  3.3. Evaluation Metrics

The binary “natural/unnatural” class prediction performance of the contextual
naturalness estimator is evaluated using F1555F1 =
$\frac{2*Precision*Recall}{Precision+Recall}$ score and Accuracy666Categorical
accuracy: calculates how often predictions match one-hot labels. metrics. We
use the mean of the following metrics calculated on the test set, to evaluate
the relevance, engagement, accuracy and diversity of generated queries.

  * •

Sessions with positive user-action ($Sessions^{+}@6$): Long-term binary
engagement metric indicating if recommended queries lead to a successful
session. Its value is “1”, if any of the six generated queries belong to a
search-session in test-data with an associated down-stream positive user
action (Section 2.2.2).

  * •

Unique@6: Diversity metric indicating the percentage of unique sentences in
(six) query suggestions made per query $q^{test}_{i}$. Queries containing
unknown word token (“¡UNK¿”) are filtered out as only high-quality suggestions
are presented to the end user.

  * •

Precision@6: Measures relevance with respect to the query a user would enter
next. Is “1” if ($q^{test}_{i+1}$) is in the set of six query suggestions made
for ($q^{test}_{i}$) and “0” otherwise.

  * •

Word-repetitions per sentence ($Repetitions_{S}$): Fraction of word
repetitions per generated query ($S$). Unwanted word repetitions lead to lower
quality.

  * •

Prior Sentence Probability ($P_{S}$): $P_{S}=\Sigma_{w_{i}\epsilon
S}log(p_{w_{i}})$, measures the prior sentence probability. $p_{w_{i}}$ is
prior word probability defined in Section 2.2.3. Lower sentence probability
indicates higher diversity as generated queries contain less frequent words.

###  3.4. Results

The contextual-naturalness-estimator achieved $90\%$ accuracy and $80\%$ F1
performance on test set. Table 1 shows the performance of supervised
($Seq2Seq_{NMT}$) and proposed DRL model on the five metrics mentioned in
previous section. $DRL_{beam}$ and $DRL_{sampling}$ use “beam-search” and
“sampling from categorical distribution” MC sampling strategies respectively
(see Section 3.2). In order assess the impact of applying heuristics to filter
and improve quality of suggestions provided by supervised models, we analyzed
the performance of $Seq2Seq^{-}_{NMT}$, which is $Seq2Seq_{NMT}$ model with
post-processing filters to remove suggestions with repeated words.

Model\Metric $Sessions^{+}@6$ Unique@6 Precision@6 $Repetitions_{S}$ $P_{S}$
$Seq2Seq_{NMT}$ 0.1108 $\pm$ 0.002 5.8244 $\pm$ 0.0045 0.0456 $\pm$ 0.0025
2.21% $\pm$ 0.04% -6.4442 $\pm$ 0.0149 $Seq2Seq^{-}_{NMT}$ 0.1101 $\pm$ 0.001
5.5595 $\pm$ 0.0075 0.0456 $\pm$ 0.0025 0.00% $\pm$ 0.00%$\dagger$ -6.4875
$\pm$ 0.0151$\dagger$ $DRL_{beam}$ 0.1155 $\pm$ 0.002$\dagger$ 5.9606 $\pm$
0.0023$\dagger$ 0.0468 $\pm$ 0.0025 1.10% $\pm$ 0.03%$\dagger$ -6.4897 $\pm$
0.0140$\dagger$ $DRL_{sampling}$ 0.1149 $\pm$ 0.002$\dagger$ 5.9956 $\pm$
0.0007$\dagger$ 0.0467 $\pm$ 0.0024 0.40%$\pm$ 0.02%$\dagger$ -6.3932 $\pm$
0.0141

Table 1. Mean performance of supervised $Seq2Seq_{NMT}$ and $DRL$ models
across all query pairs in test data. Cells show the mean and 95% confidence
interval calculated using t-distribution. Best mean is in bold. $\dagger$
indicates statistically significant improvement over baseline $Seq2Seq_{NMT}$.

On offline test data set, in comparison to the baseline $Seq2Seq_{NMT}$ model,
$Seq2Seq^{-}_{NMT}$ removed query suggestions with repeated words completely,
however the heuristics-based model performed poorly in-terms of diversity
(4.5% relative drop in mean Unique@6) and average number of successful
sessions (0.6% relative drop in mean $Sessions^{+}@6$). On the other hand,
both versions of our proposed DRL models outperformed the baseline model on
all metrics. DRL variants achieved significant relative improvement in-terms
of user-engagement (mean $Session^{+}@6$) up to 4.2% ($0.1108\rightarrow
0.1155$), query suggestions’ diversity (mean Unique@6) up to 3%
($5.8244\rightarrow 5.9956$), sentence-level diversity (mean Prior Sentence
Probability) up to 0.7% ($-6.4442\rightarrow-6.4897$) and reduction in errors
per sentence up to 82% ($2.21\rightarrow 0.40$). Non significant improvement
in relevance (mean Precision@6) is not surprising as the supervised
$Seq2Seq_{NMT}$ model is also trained with consecutive query pairs.

##  4\. Conclusions

In this paper, we proposed a Deep Reinforcement Learning (DRL) framework to
improve the quality of related-search query suggestions. Using long-term user-
feedback, syntactic relatedness and estimated unnaturalness penalty as reward
signals, we fine-tuned the supervised text-generation policy at scale with
REINFORCE policy-gradient algorithm. We showed significant improvement in
recommendation diversity ($3\%$), query correctness ($82\%$), user-engagement
($4.2\%$) over industry-baselines. For future work, we plan to include
semantic relatedness as reward. Since the proposed DRL framework is agnostic
to the choice of an encoder-decoder architecture, we plan to fine-tune
different state-of-the-art language models using our proposed DRL framework.

###### Acknowledgements.

Thanks to Cong Gu, Ankit Goyal and LinkedIn Big Data team for their help in
setting up DRL experiments on Kubernetes. Thanks to Souvik Ghosh and RL
Foundations team for your valuable feedback.

## References

  * (1)
  * Abadi et al. (2015) Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2015\.  TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems.  http://tensorflow.org/ Software available from tensorflow.org.
  * Abdollahpouri (2019) Himan Abdollahpouri. 2019\.  Popularity Bias in Ranking and Recommendation.  https://doi.org/10.1145/3306618.3314309
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015\.  Neural Machine Translation by Jointly Learning to Align and Translate.  _CoRR_ abs/1409.0473 (2015).
  * Bodigutla et al. (2019) Praveen Kumar Bodigutla, Longshaokan Wang, Kate Ridgeway, Joshua Levy, Swanand Joshi, Alborz Geramifard, and Spyros Matsoukas. 2019.  Domain-Independent turn-level Dialogue Quality Evaluation via User Satisfaction Estimation.  arXiv:cs.LG/1908.07064
  * Borges et al. (2020) F. Borges, Georgios Balikas, Marc Brette, Guillaume Kempf, A. Srikantan, Matthieu Landos, Darya Brazouskaya, and Qianqian Shi. 2020\.  Query Understanding for Natural Language Enterprise Search.  _ArXiv_ abs/2012.06238 (2020).
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners.  arXiv:cs.CL/2005.14165
  * Cao et al. (2008) Huanhuan Cao, Daxin Jiang, Jian Pei, Qi He, Zhen Liao, Enhong Chen, and Hang Li. 2008.  Context-Aware Query Suggestion by Mining Click-through and Session Data. In _Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’08)_. Association for Computing Machinery, New York, NY, USA, 875–883.  https://doi.org/10.1145/1401890.1401995
  * Chaslot et al. (2008) Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. 2008.  Monte-Carlo Tree Search: A New Framework for Game AI. In _Proceedings of the Fourth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ _(AIIDE’08)_. AAAI Press, 216–217.
  * Freitag and Al-Onaizan (2017) Markus Freitag and Yaser Al-Onaizan. 2017.  Beam Search Strategies for Neural Machine Translation.  _CoRR_ abs/1702.01806 (2017).  arXiv:1702.01806 http://arxiv.org/abs/1702.01806
  * Ganegedara (2020) Thushan Ganegedara. 2020\.  Is the race over for Seq2Seq models?  https://towardsdatascience.com/is-the-race-over-for-seq2seq-models-adef2b24841c
  * Goodfellow et al. (2014) Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014\.  Generative Adversarial Nets. In _Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2_ _(NIPS’14)_. MIT Press, Cambridge, MA, USA, 2672–2680.
  * Graves et al. (2013) Alex Graves, Navdeep Jaitly, and Abdel-rahman Mohamed. 2013\.  Hybrid speech recognition with Deep Bidirectional LSTM. In _2013 IEEE Workshop on Automatic Speech Recognition and Understanding_. 273–278.  https://doi.org/10.1109/ASRU.2013.6707742
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Comput._ 9, 8 (Nov. 1997), 1735–1780.  https://doi.org/10.1162/neco.1997.9.8.1735
  * Kazi et al. (2020) Michaeel Kazi, Weiwei Guo, Huiji Gao, and Bo Long. 2020\.  Incorporating User Feedback into Sequence to Sequence Model Training. In _CIKM ’20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020_ , Mathieu d’Aquin, Stefan Dietze, Claudia Hauff, Edward Curry, and Philippe Cudré-Mauroux (Eds.). ACM, 2557–2564.  https://doi.org/10.1145/3340531.3412714
  * Kiefer and Wolfowitz (1952) J. Kiefer and J. Wolfowitz. 1952.  Stochastic Estimation of the Maximum of a Regression Function.  _The Annals of Mathematical Statistics_ 23, 3 (1952), 462–466.  http://www.jstor.org/stable/2236690
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization.  _CoRR_ abs/1412.6980 (2015).
  * kubernetes.io (2020) kubernetes.io. 2020\.  Cluster Architecture.  https://kubernetes.io/docs/concepts/architecture/
  * Lee et al. (2021) Seanie Lee, Dong Bok Lee, and Sung Ju Hwang. 2021.  Contrastive Learning with Adversarial Perturbations for Conditional Text Generation.  arXiv:cs.CL/2012.07280
  * Li et al. (2016) Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. 2016\.  Deep Reinforcement Learning for Dialogue Generation.  _CoRR_ abs/1606.01541 (2016).  arXiv:1606.01541 http://arxiv.org/abs/1606.01541
  * Li et al. (2019) Ruirui Li, Liangda Li, Xian Wu, Yunhong Zhou, and Wei Wang. 2019.  Click Feedback-Aware Query Recommendation Using Adversarial Examples. In _The World Wide Web Conference_ _(WWW ’19)_. Association for Computing Machinery, New York, NY, USA, 2978–2984.  https://doi.org/10.1145/3308558.3313412
  * Liaw et al. (2018) Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and Ion Stoica. 2018\.  Tune: A Research Platform for Distributed Model Selection and Training.  _arXiv preprint arXiv:1807.05118_ (2018).
  * Lin (2004) Chin-Yew Lin. 2004\.  ROUGE: A Package for Automatic Evaluation of Summaries. In _Text Summarization Branches Out_. Association for Computational Linguistics, Barcelona, Spain, 74–81.  https://www.aclweb.org/anthology/W04-1013
  * Nogueira and Cho (2017) Rodrigo Nogueira and Kyunghyun Cho. 2017.  Task-Oriented Query Reformulation with Reinforcement Learning. In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Copenhagen, Denmark, 574–583.  https://doi.org/10.18653/v1/D17-1061
  * Schmidt (2019) Florian Schmidt. 2019\.  Generalization in Generation: A closer look at Exposure Bias. In _Proceedings of the 3rd Workshop on Neural Generation and Translation_. Association for Computational Linguistics, Hong Kong, 157–167.  https://doi.org/10.18653/v1/D19-5616
  * Schouten (1986) Hubert J. A. Schouten. 1986\.  Nominal scale agreement among observers.  _Psychometrika_ 51, 3 (1986), 453–466.  https://doi.org/10.1007/BF02294066
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal Policy Optimization Algorithms.  _CoRR_ abs/1707.06347 (2017).  arXiv:1707.06347 http://arxiv.org/abs/1707.06347
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F. Christiano. 2020.  Learning to summarize from human feedback.  _CoRR_ abs/2009.01325 (2020).  arXiv:2009.01325 https://arxiv.org/abs/2009.01325
  * Tang et al. (2006) Thanh Tin Tang, Nick Craswell, David Hawking, Kathy Griffiths, and Helen Christensen. 2006\.  Quality and relevance of domain-specific search: A case study in mental health.  _Information Retrieval_ 9, 2 (2006), 207–225.  https://doi.org/10.1007/s10791-006-7150-5
  * Wang et al. (2016) Xuanhui Wang, Michael Bendersky, Donald Metzler, and Marc Najork. 2016.  Learning to Rank with Selection Bias in Personal Search. In _Proc. of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 115–124.
  * Wang et al. (2020) Xiao Wang, Craig Macdonald, and Iadh Ounis. 2020\.  Deep Reinforced Query Reformulation for Information Retrieval.  arXiv:cs.IR/2007.07987
  * Williams (1992) Ronald J. Williams. 1992\.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ 8, 3 (1992), 229–256.  https://doi.org/10.1007/BF00992696
  * Williams and Zipser (1989) Ronald J. Williams and David Zipser. 1989.  A Learning Algorithm for Continually Running Fully Recurrent Neural Networks.
  * Yu et al. (2017) Lantao Yu, W. Zhang, J. Wang, and Y. Yu. 2017\.  SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient. In _AAAI_.

##  Appendix A Appendices

Figure 2. Reward weighted Negative log-likelihood convergence performance
w.r.t the training epochs of $DRL_{sampling}$ (top figure) and $DRL_{beam}$
(bottom figure) models, for different values of learning-rate. Number of Monte
Carlo (MC) samples generated per query during training and unnatural
suggestion penalty are from best parameter combination for each MC sampling-
method (see Appendix Table A).

Table 2. Hyper parameter value ranges we used for training query generation
and contextual-naturalness-estimation models. Once hyper-params of
Supervised-$Seq2Seq_{NMT}$ are fine-tuned, same model architecture is used for
training supervised natural-estimator (encoder) model and DRL (encoder-
decoder) agent. Hence batch-size, sequence length, number of rnn layers and
hidden vector length remain consistent across all three models.

Table 3. Optimal hyper-parameter values for query generation and naturalness
estimation models with criteria applied on validation-set performance to
choose them.