Agnès Mustar

Sylvain Lamprier

Benjamin Piwowarski

On the Study of Transformers for Query Suggestion

When conducting a search task, users may find it difficult to articulate their need, even more so when the task is complex. To help them complete their search, search engine usually provide query suggestions. A good query suggestion system requires to model user behavior during the search session. In this paper, we study multiple Transformer architectures applied to the query suggestion task and compare them with RNN-based models. We experiment Transformer models with different tokenizers, with different Encoders (large pretrained models or fully trained ones), and with two kinds of architectures (flat or hierarchic). We study the performance and the behaviors of these various models, and observe that Transformer-based models outperform RNN-based ones. We show that while the hierarchical architectures exhibit very good performances for query suggestion, the flat models are more suitable for complex and long search tasks. Finally, we investigate the flat models behavior and demonstrate that they indeed learn to recover the hierarchy of a search session.

Introduction

To explore the space of potentially relevant documents, users interact with search engines through queries. This process can be improved, since when looking for information, users may have difficulties to express their needs at first sight, and hence may have to reformulate the queries multiple times to find the documents that satisfy their needs. This process is particularly exacerbated when the user is accomplishing a complex search task.

Among the different ways to help users in exploring the information space, modern search engines provide a list of query suggestions, which help users by either following their current search direction -e.g. by refining the current query -or by switching to a different aspect of a search task [Ozertem, 2012a]. Another use of query suggestions is to help the search engines by providing ways to diversify the presented information [Song, 2011]. 1 There are two ways to approach the task of query suggestions. Either in a direct way, seeking directly to improve the user experience. This involves searching for the most suitable queries so that the user accesses the most relevant information as quickly as possible [START_REF] Bhatia | [END_REF]. Such an approach requires a mean to assess what constitutes a relevant suggestion, or data on whether or not suggestions are relevant. The second approach consists in modeling the average user [Broccolo, 2012;Sordoni, 2015;Dehghani, 2017;Ahmad, 2018;[START_REF][END_REF]Wu, 2018]. The goal is to predict the next query based on the current search session -where the data is nowadays abundant. The hypothesis is that suggesting such queries from sessions usually helps users in their search. In the absence of a public dataset allowing to train and evaluate models on the first type of approach, this latter type of approach is usually pursued. This is the scope of this paper.

To suggest useful queries, most models build upon web search logs, where the actions of a user (queries, clicks, and timestamps) are recorded. User sessions are then extracted by segmenting the web search log. The first query suggestion models exploited the query co-occurrence graph extracted from user sessions [START_REF] Huang | [END_REF]Jain, 2011a]: if a query is often followed by another one, then the latter is a good potential reformulation. However, co-occurrence based models suffer from data sparsity, for instance when named entities are mentioned, and lack of coverage for rare or unseen queries. Moreover, these models are difficult to adapt when using a wider context than the last submitted query [Dehghani, 2017].

More recently, recurrent neural network-based (RNNs) methods have been proposed to exploit longer dependencies between queries [Sordoni, 2015;Dehghani, 2017;Ahmad, 2018;[START_REF][END_REF]Wu, 2018]. RNNs do so by keeping track of the user in a representation/vector space which depends on all the previous actions performed by the user. Such models have improved the quality of suggestions by capturing a broader context, but are limited by the relatively short span of interaction that RNNs are able to capture.

Beyond query suggestion, working with representation-based models such as neural networks is particularly interesting, since the learned representations can be useful for models exploiting user sessions, such as in interactive IR models. If a model is able to correctly generate a query, then it means that it has captured (at least partially) the user intent. Developing neural models able to predict with high accuracy the next queries of a user is thus important for building interactive and discussion-based retrieval systems.

Among all the models exploited in NLP and IR, most [Vaswani, 2017;Tan, 2018;Liu, 2018;Scialom, 2019;Qiao, 2019;Yang, 2019a] have benefited from the recently proposed Transformers architecture [Vaswani, 2017]. Transformer networks, such as Bert [Devlin, 2019], capture long-range dependencies between terms by refining each token representation based on its context before handling the task at hand. They are thus a particularly interesting architecture for query suggestion since query terms are often repeated throughout a session, and their interaction needs to be captured, to build a faithful representation of the current user state. Recently, Garg et al. [Garg, 2019] presented a Hierarchi-cal Transformer for Query Suggestion, with a two-level encoder. Their model outperforms the hierarchical recurrent based models [Dehghani, 2017;Sordoni, 2015], and shows that recurrence is not essential for the query suggestion task. In opposition to this type of hierarchical transformers, we refer in this paper to the classical transformer networks as flat transformers.

However, the authors of [Garg, 2019] do not provide a full analysis of whether the hierarchical architecture is important, especially for complex user sessions that are particularly interesting in the context of interactive IR. In this work, we contribute to the study of transformers for the query suggestion task -and more generally, for models able to analyze user sessions:

• We reproduce RNN-based models experiments [Dehghani, 2017;Sordoni, 2015] and extend them by segmenting queries using subword units, which allow transformers to avoid the problem of out-of-vocabulary tokens.

• We also reproduce the Hierarchical Transformer architecture [Garg, 2019], with word and sub-word units, and compare it with flat Transformers.

• We compare the flat Transformers with two pretrained transformers: Bert, Bart and T5, finetuned for our task. We also integrate these pretrained models to the Hierarchical Transformer.

The analysis is structured into three research questions that we detail below. First, we are interested in the performance of transformers from a global point of view.

Q1. How well the various presented transformers generate queries suggestions compared to the usual baselines?

When a user performs a complex search, it is more difficult to capture the intent of the user. However, such sessions are of particular interest for nowadays IR research, and in particular for interactive IR. We thus pay a particular attention to the robustness of the different models on sessions corresponding to so-called "complex" search tasks. This raises the question of whether all transformers have the same ability to handle long, complex or noisy sessions, or whether, on the contrary, the results are impacted differently depending on the pre-training or the architecture of the transformer.

Q2. Which model is the most robust? (a) to complex sessions (b) to noisy sessions (c) to long sessions Following the analyses conducted to answer Q2., we conclude that flatten pretrained transformers are more resilient to noise, length and complexity of sessions. We are investigating why these models are more robust, which leads us to our final research question: Q3. How does the flat transformer generate queries? (a) On which context's queries does it focus its attention? (b) On which context's tokens does it focus its attention? (c) How does it choose the next token to generate?

The analyses and answers to these questions aim to better understand the behavior of various Transformer architectures for user modeling.

Related Work

A large number of works have focused on the task of query suggestion [Ozertem, 2012b], and related tasks such as query auto-completion [START_REF][END_REF], based on search logs to extract query co-occurrences [START_REF] Huang | [END_REF]Jain, 2011a]. From a given single query formulated by a user, the goal is to identify related queries from logs, and to suggest reformulations based on what follows in the retrieved sessions, assuming subsequent queries as refinements of former ones [Sadikov, 2010]. These works rely on several methods, such as using term co-occurrence [START_REF] Huang | [END_REF], using users click information [START_REF] Mei | [END_REF], using word-level representation [Bonchi, 2012], capturing higher order collocation in query-document sub-graphs [Boldi, 2009], clustering queries from logs [Sadikov, 2010], or defining hierarchies of related search tasks and sub-tasks [START_REF] Awadallah | [END_REF][START_REF] Mehrotra | [END_REF]. Some methods finally prevent query sparsity via reformulations using NLP techniques [Ozertem, 2012b]. For instance, Jain et al. [Jain, 2011b] propose an end-to-end system to generate synthetic suggestions, based on query-level operations and information collected from available text resources. Broccolo et al. [Broccolo, 2012] propose to alleviate the sparsity issue by creating a knowledge base from query logs. The database is filled with train log queries to make synthetic documents. The idea is then to define a function which measures the similarity of a virtual document with this base and a new session. Each token of the session is taken into account independently to calculate this similarity, which allows unseen queries to be treated. The title from the closest virtual documents are the suggestions.

However, such log-based methods suffer from data sparsity and are not effective for rare or unseen queries [Sordoni, 2015]. In addition, these approaches are usually context-agnostic, focusing on matching candidates with a single query. When the query comes in a session with some previous attempts for finding relevant information, it is crucial to leverage such context for capturing the user intent and understanding its reformulation behavior. Note the approach in [Cao, 2008], which alleviates the problem by relating the user sessions to paths in a concept tree, but also suffers from data sparsity issues.

Instead of trying to predict directly a query, it is possible to learn how to transform it. Most approaches operate at a high level, with term retention, addition and removal as the possible reformulation actions [START_REF] Levine | [END_REF][START_REF] Sloan | [END_REF]. [START_REF] Levine | [END_REF] consider these actions as feedback from the user -e.g. a term that is retained during the whole session should be considered as central for the user intent. Depending on the previous sequence of users' actions, these methods seek to predict the next action. These methods are interesting because they model the user behavior in a session. However, they fail at capturing the semantic of words, which is essential.

To cope with limitations of log-based and action-based methods, some works propose to define probabilistic models for next query prediction [START_REF] He | Web Query Recommendation via Sequential Query Prediction[END_REF]. Due to their ability for processing sequences of variable size, Recurrent Neural Networks (RNNs) have been widely used for text modeling and generation tasks, with an encoder that processes an input sequence by updating a representation in R n , and a decoder that generates the target sequence from the last computed representation. Some works have adapted these ideas to a sequence of queries [Dehghani, 2017;[START_REF] Jiang | [END_REF]Sordoni, 2015]. HRED [Sordoni, 2015] proposes to use two encoders: a query-level encoder, which encodes each query of the user session independently, and a session-level encoder, which deals with the sequence of query representations. Instead of using a hierarchical representation, ACG [Dehghani, 2017] relies on attention mechanism giving a different importance to words and queries in the computed representation. Another improvement of ACG is to deal with Out-Of-Vocabulary (OOV) words through the use of a copy mechanism, which allows the model to pick tokens from the past user queries rather than generating them using a fixed-size vocabulary.

Other RNN-based approaches have also been recently proposed, such as [Wu, 2018], which leverages user clicks and document representations to specify the user intent [Ahmad, 2018;[START_REF][END_REF], or [START_REF] Jiang | [END_REF] which integrates click-through data into homomorphic term embeddings to capture semantic reformulations. Some works have explored the use of long-term search history of users [Chen, 2018], using a RNN-based hierarchical architecture, to score query suggestions. In this work, as a starting point, we restrict to queries in sessions as input data, but other sources of information can be added to such models.

In parallel, the Transformers architecture, a recent and effective alternative to RNNs models introduced in [Vaswani, 2017], was successfully applied to a large set of NLP applications, such as Constituency Parsing and Automatic Translation [Vaswani, 2017], Semantic Role Labeling [Tan, 2018], Machine Reading Comprehension [Liu, 2018], and Abstractive Text Summarization [Scialom, 2019].

The Transformer architecture has also has been used several times in the field of Information Retrieval. Nogueira et al. [Nogueira, 2019] and Han et al. [START_REF] Han | Inferring Search Queries from Web Documents via a Graph-Augmented Sequence to Attention Network[END_REF] applied transformers to infer the queries relevant to a document. Nogueira et al. [Nogueira, 2019] used the pretrained transformer BERT, and showed that expending the document with the predicted query improves the ad hoc retrieval results, while Han et al. [START_REF] Han | Inferring Search Queries from Web Documents via a Graph-Augmented Sequence to Attention Network[END_REF] presented a more complex seq2seq architecture: the encoder included a Graph Convolutional Network and a RNN; and the decoder is a transformer. Several works focused on transformers applied to conversational search [Yu, 2020;Aliannejadi, 2020;[START_REF][END_REF], in particular Yu et al. [Yu, 2020] used a pretrained model for conversational query rewriting, and showed that even with very limited training data it could achieve very good performances. Finally, transformers have been used for ad hoc retrieval [Yang, 2019a;Dai, 2019a;MacAvaney, 2019;Qiao, 2019], the latest works showing that the transformer-based architectures are outperforming stateof-the-art adhoc models. Dai et al. [Dai, 2019a] analyzed the attention weights of BERT to explain its performance in retrieval, but restricted their study to some selected examples.

For the query suggestion task, Garg et al. [Garg, 2019] presented a Hierarchical Transformer that outperforms RNN-based model, and thus showed that recurrence was not crucial for this task. Their model is composed of two encoders, namely a token-level and a query-level one. The first one gives a contextualized representation of each token that depends on the other tokens of the query, while the second one outputs a contextualized representation of each query depending on the other queries of the session. Our work extends this paper by providing a thorough analysis of the behavior of (hierarchical) transformer models, as well as experimenting with various pre-trained transformer models.

3 Transformers for Queries Suggestion lIn this section, we first present the transformer network architecture before describing how we use it for query suggestion.

The Transformer architecture

The transformer architecture was introduced in [Vaswani, 2017]. It is composed of parametric functions that successively refine the representation of sequences, both for the encoder and the decoder. In our case, the encoder is used to represent the session, and the decoder to generate the next query.

Each layer of the encoder or the decoder transforms a sequence x composed of n vectors x 1 , . . . , x n into a sequence y 1 , . . . , y n of the same length, through an attention over a context sequence c composed of n vectors c 1 , . . . , c n . Each time, the central mechanism is to use an attention mechanism -other operations are conducted to ensure a stable and efficient learning process, and are detailed in [Vaswani, 2017], but here we focus on the attention mechanism since it is important for our analysis (section 5).

Attention heads and transformations. At each layer of the encoder or the decoder, the transformation function T is based on the output of a series of H attention-based functions A h (called heads). For each head A h , the attention mechanism relies on:

• keys k h (c j ) ∈ R d k computed for each element of the context c j • values v h (c j ) ∈ R d k computed for each c j • queries q h (x i ) ∈ R d k computed for each input x i ∈ R d , with d = H × d k .
Each input is decomposed in H parts of the same dimension d k , i.e. x i = (x 1i ⊕ . . . ⊕ x Hi ) where ⊕ is a vector concatenation operation. Each x hi is modified by a linear combination of the values v h (c j ) based on weights derived from the match between the query q h (x i ) with the different keys k h (c j ). More formally, we define a head A h as:

A hi (x, c) = x hi + m j=1 α hij v h (c j ) β hij (cj ) with α hij ∝ exp 1 √ d k q h (x i ) • k h (c j ) (1)
where we can see that the attention mechanism only modifies the input if both the attention α hij and the value v h (c j ) are not null. Each key, query, and value function is unique to a given layer and head, but is the same for each input vector. The output of the layer is given by T (x, c) = (T 1 (x, c), . . . , T n (x, c))

with y i = T i (x, c) = f (A 1i (x, c) ⊕ . . . ⊕ A Hi (x, c))
where f is a normalization followed optionally by a feed-forward layer.

The full transformation performed at layer l for a part • of the model is denoted as T • l in the following. The parameters of the corresponding heads (queries, keys, and values) are specific to each T • l , where • is either the encoder self-attention e → e, the decoder self-attention d → d or the decoder to encoder attention e → d (see below).

Encoding. When encoding, i.e. processing the input sequence s (0) of token embeddings s (0) 1 , . . . , s (0) n , each layer transforms a sequence s (l-1) into s (l) using the transformation T e→e l (s (l-1) , s (l-1) ) based on the heads A e→e hi (e → e for "attention from the encoder on the encoder"). Since the context is simply the input here, this is called a self -attention mechanism -i.e. each input item representation is transformed by looking at the whole input sequence. This is repeated L e times until obtaining the final representation of the encoded sequence s (Le) which has the same length as the original input, but where each representation is contextualized depending on the other tokens of the input.

Decoding. The generating process (called decoding) is based on the same principle -with a small twist since we take into account not only the already generated sequence, but also the input. To compute the probability of generating a new token w given the sequence w 0 , w 1 , . . . , w n ′ , whose embeddings are t

(0) 0 , . . . , t (0)
n ′ , the decoder uses two attentions: one self-attention A d→d (decoder to decoder attention) followed by an attention on the encoded sequence A d→e (decoder to encoder attention). The representation at layer l is based on the representation at layer l -1 and on the final encoded sequence:

d (l) = T d→e l T d→d l t (l-1) , t (l-1) , s (Le)
The process is repeated L d times, giving rise to the representations t

(L d ) 1 , . . . , t (L d ) n ′ .
The distribution over the next token w (whose embedding is t) is then given by a parametric function applied to the representation of the last previously generated output t n ′ (which is why there is a token w 0 corresponding to "[START]" -in order to compute the first generated token):

p(w|w 1 , . . . , w n ′ ) = g(t; t (L d ) n ′ )
(2)

Pre Trained Transformers

Transformers models have a large number of parameters which make them costly to train. In addition to that, the attention mechanism is computationally expensive, particularly for long sequence: it has a complexity of O(n 2 ) with respect with the sequence length [Wang, 2020]. Thus they are complex to train. Fortunately, multiple pre-trained models trained on large datasets have been released recently [Devlin, 2019;Lewis, 2020;Radford, 2019;Yang, 2019b]. We compare the results of transformers trained from scratch, to three pre-trained models that we finetune, namely BERT [Devlin, 2019], BART [Lewis, 2020] and T5 [Raffel, 2020].

Bert The Bidirectional Encoder Representations from Transformers [Devlin, 2019] has been trained on a large dataset, the BooksCorpus [Zhu, 2015] on two tasks, namely predicting some masked tokens of the input, and on predicting whether one sentence follows another. It is a state-of-the-art model, which is used for different tasks. BERT corresponds to the encoder part only -we have to train a decoder for our specific task.

Bart Bidirectional and Auto-Regressive Transformer is made of an encoder and a decoder. It is trained on the same data than BERT, but on multiple tasks: token masking, token detection, text infilling, sentence permutation, and document rotation. Because it has a decoder and it is trained on these tasks, the authors claim that BART is better than BERT for text generation. They also released fine-tuned versions of BART for other tasks. We use the weights of the model fine-tuned on CNN/DM, a news summarization dataset, because as a text generation task it was the closest task to the query suggestion task.

T5 T5 [Raffel, 2020] is also a transformer with an encoder and a decoder as described in [Chen, 2018] with minor architecture modifications in the attention. T5 is trained simultaneously on multiple tasks, that's why the author called it a "unified" framework. The task is specified by adding the task name as a prefix in the original input. The network is the same for all inputs, while usually the mutli-task learning model have a specific network for each task [Liu, 2020]. Note that many pretrained transformers have been released in recent years (BERT [Devlin, 2019], BART [Lewis, 2020], GPT-2 [Radford, 2019], T5 [Raffel, 2020], XML [START_REF] Conneau | Alexis Conneau and Guillaume Lample. "Cross-lingual Language Model Pretraining[END_REF], RoBERTa [Liu, 2019], and the famous GPT-3 [Brown, 2020] -whose parameters have not been made public), so it is necessary to choose those we want to experiment with. We choose (1) BERT because it is the most used transformer, (2) BART because it has an encoder-decoder architecture with very good performance in generation, and especially in summarization, and finally (3) T5 because it is one of the last transformers that have been published.

Using Transformer networks for Query Suggestion

Problem Setting

Let us consider a session S = (Q 1 , ..., Q |S| ) as a sequence of |S| queries, where every

Q i = (w i,1 , ..., w i,|Qi| ) is a sequence of |Q i | words.
The goal of query suggestion is to suggest the most relevant query for the user intent represented by the session. However, no perfect ground truth can be easily established for such problems: defining the perfect query for a given specific under defined need, given a sequence of past queries, is an intractable problem, which requires to consider very diverse (in nature and complexity) search tasks, depends on the user state, the IR system and the available information in the targeted collection. Following other works on model-based query suggestion, we thus focus on predicting the next question within an observed session.

We suppose that our dataset is composed of pairs (S, Q) where Q is the query following a sequence of queries S. Our aim is thus to find the parameters θ that maximize the log probability of observing the dataset:

L(S; θ) = (S, Q) log p θ ( Q|S) = (S, Q) | Q| t=1 log p θ (w t |Q 1 , . . . , Q |S| ) (3)
where (w 1 , ..., w | Q| ) are the token of the query Q. We describe below how we use the transformer -we tried to build different architectures based on the transformer, but the simplest one worked the best throughout all our pilot experiments. The model is illustrated by Figure 1.

Input For a session, the input of the transformer is simply the concatenation of all the words of all the queries separated by a token [SEP], i.e. the [SEP] is used to mark the beginning of a new query in the session:

S = [[SEP ] w1,1 . . . w 1,|Q 1 | Q 1 [SEP ] . . . [SEP ] w |S|,1 . . . w |S|,|Q |S| | Q |S| [SEP ]]
This sequence is then transformed by using the token embeddings added to positional embeddings (one per distinct position) -this is how Transformers recover the sequence order [Vaswani, 2017].

We obtain a contextualized representation for each token of the session with the Encoder E: where n is the number of tokens in the whole session:

E(S) = (h 0 , ..., h n ) (4)
n = i |Q i |.
We train models with various encoders E described in the next sections (from 3.3.2 to 3.3.5). The decoding part is the same for all, as described in Section 3.1.

Fully trained Transformer (TS)

The encoder and a decoder and the decoder are fully trained, they have the architecture described in 3.1, with L d = 6 layers, with H = 12 heads each and a dropout p = 0.1. On the top of the decoder, we use a feedforward network with a hidden size of 2048. For the input tokens, we use the same embeddings for the encoder and the decoder to reduce the number of parameters and to regularize the network [Vaswani, 2017].

BERT

We use the pre-trained model Bert [Devlin, 2019], and extract each hidden layer of the model. We sum the last layer, with the average and the max of these layers1 . For each token of the input, we have a contextualized embedding of size 768 given by Bert. For the decoding part, we use the same transformer decoder and feedforward network as the ones described in 3.3.2. At the beginning of the training the encoder is frozen and the decoder is trained. We then use a "gradual unfreezing" of the encoder layers as recommended by [START_REF] Howard | [END_REF]: when the loss stabilizes, we unfreeze the last frozen layer of the encoder, until all the layers are fine-tuned.

BART

The architecture is complete for text generation, it has an encoder and a decoder. We also use gradual unfreezing to finetune the model, but starting from the last layer of the pre-trained decoder. We compare the results of the complete Bart model finetuned for our task, with the ones of the Bart Encoder followed by a fully trained Transformer Decoder.

T5

T5 is a transformer with a pretrained encoder and a pretrained decoder. As we did for BART, we compare two versions of the model: the encoder-only version Enc T 5, with a finetuned encoder and a fully trained decoder, and a version for which we finetuned the entire T5 model. We use the training protocol described for BART and BERT.

Hierarchical Transformer for Query Suggestion

We now describe the hierarchical transformer proposed by [Garg, 2019] (an illustration is given in Figure 2). It is composed of two levels of encoding: a token-level E T and a query-level one E Q , each following the same contextualization process as a standard encoder in a transformer model.

First, the token-level Encoder E T produces a contextualized representation E T (Q i ) = ( wi,1 , . . . , wi,K ) of each token of a given query Q i . Since queries might have a different length, padding is used (e.g. a special [blank] token) so that each query is of length K. This representation is then summarized into a query representation Qi using a linear transformation:

Qi = E T (Q i )W P (5)
The transformation matrix is W P ∈ R Kd×d where d is the output dimension of each token of the encoder. In our experiments we use K = 12, which is enough to cater for most of the queries -the remaining tokens are truncated. The session-level encoder takes these vectors Qi as input to transform them into final query representations S = ( S1 , ..., S|S| ) that embed context from neighbor queries, using positional encoding.

S = E Q Q1 , ..., Q|S| (6)
where |S| is the number of queries in the session.

We then obtain the final representation of a query token by summing its query-wise representation wi,j with the contextualized representation of its corresponding query Si : hi,j = wi,j + Si (7)

Finally, the decoding part is exactly the same as for other transformer models (Section 3.1).

Experiments

In this section, we report experimental results comparing the various flat and hierarchical transformer-based models, as well as other neural network baselines. We first describe the datasets, the compared models and the metrics (sections 4.1 to 4.3), before presenting our main results in section 4.4. In section 4.5, we pursue our analysis by studying how the models perform when exposed to noise, by altering the sessions (filtering or concatenating). In both cases, we show that hierarchy does not help as much as a good pre-training. Finally, in section 4.6, we present some queries generated by a selection of models.

Datasets.

Some datasets allow a fine evaluation of query suggestions, they consist of queries grouped by user sessions and associated with relevant documents. These datasets are: the TREC Session dataset [Carterette, 2016] which contains the names of the tasks and relevant documents associated with the user sessions, the conversational dataset SCSdata [START_REF] Trippas | Towards a model for spoken conversational search[END_REF] segmented by task and containing the documents read by the user, and the Webis-SMC-12 dataset [Hagen, 2013] which is a subset of AOL for which the sessions have been manually split and annotated into missions. However, these three datasets contain few sessions, respectively 1300, 1000 and 2200 sessions, which is insufficient to train the models we want to compare. To the best of our knowledge, there is no dataset of sufficient size better suited to the task of suggesting queries than the two query logs datasets: the real dataset AOL web search log and the artificial dataset, MS MARCO Conversational Search [Nguyen, 2016]. In both cases, the queries are processed by removing all non-alphanumeric characters and lowercasing following [Sordoni, 2015].

MS Marco is an artificial dataset, built from real queries. The authors filtered these queries: they removed navigation, bot, junk, and adult sessions and merged users queries with a nearest neighbor search based on their embeddings to create artificial sessions. The MS MARCO dataset is provided in two parts. We use 80% of the first part as the training set, the remaining 20% as the validation set, and the second part of the dataset as the test set. Each set contains respectively 540 267, 135 066 and 75 193 sessions.

The AOL dataset consists of 16 million real search log entries from the AOL Web Search Engine for 657,426 users. Following [Sordoni, 2015], we delimit sessions with a 30-minutes timeout for both datasets. The queries submitted before May 1, 2006, are used as the training set, the remaining four weeks are split into validation and test sets, as in [Sordoni, 2015]. After filtering, there are 1 708 224 sessions in the training set, 416 450 in the test set and 416 450 in the validation set. As the real-word AOL dataset is not filtered, it contains typos, and noisy sessions. It is made of 860 155 unique words, whereas the artificial dataset MS MARCO has 28 968. When building a vocabulary same manner as in [Sordoni, 2015] (i.e., using the most frequent 90k words of the training set), 8.9% of the words from the dataset are not in the vocabulary while all MS MARCO words are included in the selected vocabulary.

Compared Models.

In our experiments we compare a co-occurence based approach, two RNNbased approaches and fully trained and fine-tuned transformer models. The co-occurence based approach is the Inverted Index [Broccolo, 2012], RNN models are HRED [Sordoni, 2015] and ACG [Dehghani, 2017], which we described in section 2. The fully trained transformer, hereafter referred as TS, is composed of an encoder and a decoder presented in Section 3. The hierarchical transformer H TS with the two-level encoder is described in section 3.4. The pre-trained models that we finetune are Bert [Devlin, 2019], Bart [Lewis, 2020] and T5 [Raffel, 2020].

The two RNN-based models and the fully trained transformers TS and H TS use a fixed vocabulary composed of words, but Bert, Bart and T5 employ subword tokenizers (WPT) that segment the text into n-grams of varying lengths [START_REF] Sennrich | [END_REF]. For instance, the query "Robert Mitchum" is segmented as robert [UNK] with a Word Tokenizer while the WPT returns robert mitch ##um. Hence, there is no out-of-vocabulary problem (handled with special OOV token) with the WPT and the vocabulary size is kept below a predefined threshold (31K tokens for Bert, 32K for T5 and 50K for BART), which in turns speeds up learning. To analyse the importance of the tokenizer, we consider variants of HRED, ACG, TS and H TS based on the Bert tokenizer in our experiments, named HRED-WP, ACG-WP, TS-WP and H TS WP.

To leverage pre-trained models, which is especially important since the number of parameters in transformer models is high, we use the parameters of Bert [Devlin, 2019], Bart [Lewis, 2020] and T5 [Raffel, 2020] to initialize the parameters of our models. More precisely, for the flat architecture (TS), the encoder parameters are either initialized to those of the Bert model, the Bart or t5 encoder. The models are named respectively BERT, Enc BART and Enc T5. Since Bart and T5 are not only an encoder as Bert, we also consider a version with both encoder and decoder parameters initialized with pre-trained Bart and T5 parameters, that we refer respectively to BART and T5.

For the hierarchical architecture (H TS), the Query Encoder E T parameters can also be initialized with those from the Bert, Bart and T5 encoders, the rest of the architecture remaining trained from scratch. We refer to such models as H BERT, H BART and H T5.

For all models involving pre-trained transformers, the training procedure is the same: we use the "gradual unfreezing" method, as recommended by [START_REF] Howard | [END_REF] and described in 3.3.3.

Models optimization is performed on the training sets of sessions with the ADAM optimizer [START_REF] Kingma | [END_REF]. All hyper-parameters are tuned via gridsearch on a validation dataset.

Metrics

As many other tasks in IR, evaluating the quality of the models is problematic since they can generate many queries in response to a session -and there is no principled way to evaluate their quality. In the following, we describe the metrics that were reported in previous works to compare models, and which try to capture the quality of the system responses.

Perplexity. All compared models generate probability distributions over the sequences. This enables to check how surprised the model is by the target query. However, perplexities of some pairs of methods cannot be compared because the vocabulary size is different (90K tokens for models without WPT, 31K tokens with WPT, 50K for BART's tokenizer, and 32K for T5). Moreover, former versions of HRED, ACG, TS and H TS can generate OOV words, which strongly biases the results. Perplexity is not reported for these last methods.

Query suggestion metrics. As a metric to evaluate generated queries compared to the target ones, we first use the classical metric BLEU [Papineni, 2002], which corresponds to the rate of generated n-grams that are present in the target query. We refer to BLEU-1, BLEU-2, BLEU-3 and BLEU-4 for 1-gram, 2-grams, 3-grams and 4-grams respectively. We also calculate the exact match EM (equals to 1 if the predicted query is exactly the observed one, 0 otherwise).

As EM can be too harsh, we also use a metric, Sim extrema [Forgues, 2014], which computes the cosine similarity between the representation of the candidate query with the target one. The representation of a query q (either target or generated) is a component-wise maximum of the representations of the words making up the query (we use the GoogleNews embeddings, following [Sordoni, 2015]). The extrema vector method has the advantage of taking into account words carrying information, instead of other common words of the queries However, this component-wise maximum method might excessively degrade the representation of a query. As an alternative, we propose to compute Sim pairwise as the mean value of the maximum cosine similarity between each term of the target query and all the terms of the generated one.

Finally, as discussed in section 3.3, there is no ground truth on what the best queries to suggest are. For each generation metric, we consider the maximum performance of the top-10 queries generated by the models. More precisely, for each model, we first generate (through a beam search with K = 20) 10 queries to suggest to the user given the context2 . The reported value for each metric (BLEU, EM, Sim extrema and Sim pairwise ) is the maximum score over the 10 different generated queries. This is usually employed for assessing the performance of a probabilistic model w.r.t. a single target (see e.g., [Kumar, 2020]) and corresponds to a fair evaluation of models that try to find a good balance between quality and diversity.

Results

In this section we aim to answer our first question: Q1. How well the various presented transformers generate queries suggestions compared to the usual baselines?

Tables 1 (generation scores), and 2 (perplexity) report results obtained by all the models. We also added two further indicators. First, the ratio of new words (New Words), calculated by counting the number of unique words that appear in the suggested query but were not in the past queries of the session, divided by the count of unique words in this query. Second, the rank of the prediction in the beam search (Repetition Rank) if the predicted query appears in the context (or 10 if it doesn't).

We first note the difference between the two datasets. As expected, being synthetic, MS Marco is a much easier dataset -more restricted vocabulary and more regular sessions, as acknowledged by the fact that all the metrics are higher for MS Marco.

From a high level point of view, we see that transformers are better performing than the baseline II and that the RNN-based models, HRED and ACG. Among transformers, more complex and pre-trained models perform better, with the flat architecture with a pre-trained encoder and decoder Bart performing the best. Contrarily to [Garg, 2019], we do not observe a real difference between hierarchical and non hierarchical transformer architectures: The main factor of variation is on what task and dataset the model was pre-trained.

We note that models have different tendencies to copy one of the queries in the session. This is a standard behavior: 3% of queries for MS Marco and 6% for AOL are among the previous queries of the session. So it is not surprising that more powerful models learn to copy -transformer models have a tendency to repeat a seen query compared to ACG or HRED (lower Repetition Rank). We explain this tendency by their ability to retrieve information at arbitrary positions in the input.

Perplexity We only compare perplexity for models based on the same tokenizer, since otherwise the problem of evaluating prediction with OOV tokens, or of vocabulary with different sizes makes comparisons impossible. We observe that the transformers obtain a much better perplexity than ACG and HRED with WPT. The likelihood of target queries with these last two methods are both about half the one of the transformer model TS WP. This shows that transformers better explain users' behavior in search sessions. Among transformers, we observe that while the hierarchy is beneficial on the AOL dataset, it is not the case on the MS MARCO dataset. We will discuss this behavior in more details later.

Word Piece Tokenizer Among RNNs, using WPT is sometimes beneficial for HRED but not for ACG. We explain this because the copy mechanism already allows ACG to produce rare tokens. This ability appears lowered when using word pieces, as assembling unknown words from smaller tokens is much more difficult than copying a whole word for such architectures. For HRED, the Word Piece Tokenizer improves the scores on the AOL Dataset, while it degrades them on the MS MARCO one. This is explained by the fact that for the MS MARCO Dataset there is no OOV and hence using a WPT is not useful anymore.

For Transformers trained from scratch (TS, TS WP, H TS and H TS WP), the Word Piece tokenizer is always beneficial. It could be due to the use of positional embeddings, that makes the copy of consecutive tokens easier. Moreover the use of this tokenizer reduces the vocabulary size.

The pre-trained Models First, BART (flat transformers with a pre-trained encoder and decoder) outperforms all the models on all metrics. This shows the value of pre-trained models on large dataset and on generative tasks (summarization). When observing the flat pre-trained models scores, we note that they outperform the fully trained version: BERT, Enc BART, BART, Enc T5 and T5 are better than TS WP on the AOL dataset. For the MSMARCO dataset, while BERT and BART have better scores than TS WP, Enc BART and Enc T5 are similar to TS WP. We think that because the vocabulary used in the MSMARCO dataset is more restricted, and the dataset more regular, the use of large pre-trained models is less beneficial. While T5 largely outperforms BERT on the AOL dataset, BERT is much better than T5 on the MSMARCO dataset. The unified framework -consisting on training simultaneously the model for various tasks -used to pretrain T5 is useful on a complex dataset, as it probably allows the model to acquire more language knowledge, but it is less efficient on simpler data. Finally, for both datasets, BART performs the best for all metrics. On the AOL dataset, BART improvement is particularly important on BLEU 3 and BLEU 4 -which are calculated by considering 3-gram and 4-gram sequences. It indicates that when comparing longer word sequences between target and predictions, BART is the best model, thus it is better at generating longer queries, i.e. longer queries. We think this is because BART has been trained on a summarization task, and is therefore better than the other models at generating comprehensive sequences.

Its scores are also significantly better on the similarity scores sim extrema and sim pairwise on the AOL dataset, which means that this is the best model to capture the word semantic.

The Hierarchy On the AOL dataset, the hierarchical models perform better than their flat version: TS vs H TS, TS WP vs H TS WP, BERT vs H BERT, Enc BART vs H BART except for T5 for which Enc T5 outperforms H T5. This could be due to the fact that T5 uses relative positional embeddings, while other models use absolute positional embeddings. H T5 would have more difficulties to find the exact position of words within queries. Note that for fair comparison H BART and H T5 are compared to Enc BART and Enc T5 rather than BART and T5 because BART and T5 decoders are pre-trained while H BART and H T5 decoders are trained from scratch. This shows that with a suitable encoder the hierarchy is beneficial for the query suggestion task, the two-levels encoder allowing to have a more complex representation of the session.

The conclusions are different for the MSMARCO dataset. For the fully trained model TS and TS WP, and for BART, the hierarchy does not help significantly, while with BERT and T5, the hierarchy decreases the results. We explain this because the queries and the sessions of the MSMARCO dataset are longer, and the model has difficulty to focus its attention on the important queries. We discuss the behavior of the hierarchical models on longer and more complex sessions more in detail below.

Robustness of (transformer) models

We now look more in details in how the models behave regarding different types of sessions to answer the second question Q2: Which model is the most robust to complex sessions (a), to noisy sessions (b) and to long sessions (c)? For each type of session, a section is dedicated to the answer. (a) Transformers results on complex sessions Focusing on the real-word dataset AOL, which contains many very short and simple search sessions typical of web search, we were interested in how transformer models could handle complex sessions. To identify those, we used a simple heuristic: a complex session (1) consists of at least three queries;

(2) contains queries with more than one word; and (3) should not contain spelling corrections. For (3), we used the following heuristic: each of its queries must be sufficiently different from the previous one, i.e. its editing distance (in characters) should be greater than 3. Figure 3a reports the relative results obtained on this subset of 193 336 complex sessions. In particular, we want to compare the results of the flat and of the hierarchical models. We note the good behavior of flat transformers for query suggestion for the complex search task, while it emphasizes the weakness of the pre-trained hierarchical models on these sessions. The flat models improve the results on these sessions over the corresponding hierarchical model on all metrics: BERT is less deteriorated than H BERT, and likewise BART and Enc BART are less impacted than H BART by the complexity of the sessions, and the same is true for T5 models. For the fully trained models, TS WP is also less impacted that H TS WP on this subset of sessions on all metrics. This shows again the robustness of flat models.

(b) Results on noisy sessions

To assess the robustness of the approaches, we add one random session at the start of each session of the test set. Since the intent of these added sessions (in average) is not the same as the intent driving the user's behavior when formulating test queries, models must have learned to identify thematic breaks, and to ignore this noisy information. Figure 3b shows percentages of performance loss for every metric. We can see that for all models, the flat architectures are much less impacted than their corresponding hierarchical counterpart. This is an important result, since the test sessions were arbitrarily split according to a 30-minute timeout, which might not correspond to users' intent changes. It shows that with the hierarchy, the transformers lose their ability to focus on relevant part, and so to adapt themselves to longer sessions.

(c) Sessions Lengths We study the impact of the sessions lengths on the two pre-trained models BERT and BART (flat and hierarchical versions) on the AOL dataset. Results are reported in Figure 4. Whatever the metric, the hierarchical models (in green) perform better than the flat ones (in red) for short sessions. However, for longer sessions (above 7 queries), it is the other way around. The flat models scores remain stable while the scores of the hierarchical models decrease. The hierarchical architecture of [Garg, 2019] is adapted to short and more simple sessions search, but for longer and complex tasks the flat transformers are more suitable. We believe that this is due to the fact that hierarchical transformers cannot focus reliably on the relevant parts of the session.

Generated Queries

Finally, in table 3, we give examples of query suggestions for three sessions, and multiple models: HRED WP (which is the best among the RNN baselines), the fully trained transformers TS WP and H WP, and the pre-trained ones Enc BART, H BART, and BART.

First, we note that the RNN-based model HRED WP generates the same word several times in a row. This behavior is very common for HRED WP. For the session presented in the first column, it suggests "divorce groups groups", for the second "maryland hotel hotel ocean" and for the third "disney resorts resorts". Note that this is something the transformer models never do. Moreover, HRED WP doesn't introduce new words, it reformulates the queries of the context by mixing words order. On the contrary, the transformer models proposed more diverse suggestions.

We note that the hierarchical models have a greater tendency to copy words from the context compared to their flat version (we study this behavior in the next section). H TS introduces only one new word ("free") in the suggestions of the first session, while TS WP proposes several new themes ("listings", "ebay", "aol"). The second presented session contains a typo: "marylandocean" instead of "maryland ocean" with a blank space. The hierarchical H BART didn't succeed to correct this typo, it proposes "marylando ocean city" because it is more willing to copy words from the context, and thus a part of this typo, while the flat transformer models didn't.

The pre-trained models BART and H BART propose more diverse suggestions compared to the fully trained models. In the session of the third column, the user performs queries on several topics of the same subject. While the various models succeed to integrate the diverse themes in the suggestions, the pre-trained models introduced more new topics : "texas", "hotels", "ebay". Finally, we notice that the suggestions of BART tends to be longer than the ones of the other models, confirming the experimental results shown earlier.

Transformer for Queries Suggestion Analysis

We now investigate the behavior of this latter model BART and design experiments to answer the last question Q3: How does the flat transformer generate queries?

Several papers propose to analyze transformers to check which information is learned or used [Clark, 2019;[START_REF] Jawahar | [END_REF]Brunner, 2020] through either probing different parts of the layer, or by looking at the attention towards the input [Clark, 2019]. In this section, we follow this latter line of work, focusing on specific properties of transformers for query generation.

To do so, we focus on the attention of the decoder towards the encoder output (see section 3.1), i.e. the attention weights computed for A d→e . When generating the (t+1) th token, we denote α (t) lhij the attention from the i th decoder token into the j th encoded token for each layer l and attention head h. To summarize this information, we (1) average the attention over the different heads -following [Clark, 2019]; and (2) only look at the attention of the j th output token when generating the j + 1 th output The rationale for the latter is that the generated token at step j + 1 mostly depends on the final representation t (L d ) j of the decoder token j, as shown in equation ( 2). Moreover, we observed that the attention did not vary much during the generation process, and hence those values are close to their average. We denote those averaged and picked attentions of token i on token j at the layer l as αlij .

Finally, as shown in [Brunner, 2020], the attention weight might not be a reliable indicator in all cases, since the actual modification of the representation depends on the value v h (s (L) i ) as shown in equation (1). To cater for this problem, we define the importance (of an attention)

β (t) lhij as α (t) lhij ∥v lh (s (L) i )∥.
As for the attention, we summarize those values as βlij . Unless specified, we focus on results for Bart -but most of the behavior is shared by the different versions of the transformers we analyzed.

The growing importance of queries

In this section, we will answer the first sub-question Q3. (a) On which context's queries does the flat transformer focus its attention? [Sordoni, 2015] claim that the last query -which they called the anchor query -plays a crucial role in queries suggestions. We verify this claim by assessing whether more attention was paid to the last queries in a session or not. For long enough sessions (≥ 5 queries), and for each query, we first sum the importance βlij over its tokens, and normalize the value by dividing it by its maximum value, so that we can average sessions of varying length. For the same reason, we normalize the index of each query by the length of the session, i.e. i/|S|. In Figure 5, we plot the boxplot of the importances given the normalized index of the query in the session. The x-axis corresponds to the position of the query in the session (from left to right: from the beginning to the end of the session), and the y-axis to the importance of the query. We see that there is a trend showing that last queries are more important for the prediction of the transformers since they have more impact on the vector used for predicting the output. It also explains the robustness of BART on concatenated sessions 3b.

The importance of the context's tokens

We now answer the second sub question of Q3. (b) On which context's tokens does BART focuses its attention?

For each decoded token (including the special token START numbered 0), we first look at the importance assigned to encoded tokens. In figure 6, each cell (i, j) in the grid gives the importance of the jth token (of each query in the session, e.g. the second token of each query in the session is numbered "2") when decoding the ith token of the target query. We only plot the importance for two representative layers (1 and 12), we can distinguish two layers groups that behave similarly (not shown here: 1 to 4, and 8 to 12). We can observe that at layer 1 to 4, the importance focuses on tokens that match the same position (e.g. the first tokens of each query and the first decoded token). For the decoder token START (numbered 0), the importance is more broadly distributed -which is sensible since nothing has been generated so far. On layers 8 to 12, the importance focuses on tokens that match the next token position (e.g. the first tokens of each input query for START, the second tokens of each input query for t 1 , etc.). This shows that transformers first focus on the matching encoded token before selecting the next token to generate.

The figure also underlines that BART, even without explicit hierarchy architecture, is able to capture the basic structure of sessions, the attention being in average more focused around the matching tokens (i.e. same position) of the queries present in the context session (as shown by the diagonal in both graphs). This brings interesting questions in terms of the generative process of the transformer-based architectures. For the START decoder token, the only explanation is that they first focus on the "[SEP]" encoded tokens, and then shift their attention to the next ones -relying on the position embedding that is added to the encoded token representations. For the next tokens to be generated, this is less obvious since the model could simply focus on a matching token (e.g. the decoder token "cat" matches the encoded tokens "cat"). As queries are the encoder. The X-axis corresponds to the context -i.e. the encoder tokens (averaged over all queries), while the Y-axis corresponds to the decoder -i.e. the decoder tokens. For the decoder, 0 corresponds to the START token. For instance, from (a) we see that when generating the 3rd token (row of index 2), the attention is focused mostly on the second token, and also (but less) on the first and third ones. This is different for the same token at layer 12 (b), where most of the attention is focused on the third token of every past query. Results are averaged over 20000 sessions.

Generating a new token

often repeated within a session with small variations, the tokens might be in the same positions (in average) in the session queries and in the generated query. Consequently, to generate the next token, there are two possibilities: either the transformer shifts the attention towards a token to the right (position-based decision), or, the (query) language model of the decoder proposes a direction in the token space, which is then matched if an encoded token lies in this direction in the representation space.

To look into this, we used sub-sessions of the form

. . . . . . -. . . A B C . . . -. . . A B
for which the next query to be predicted (in red) contains a bi-gram of tokens (A,B) that exists in the past queries, followed by a different token C. For example, the target query contains "black/A cat/B" and the session contains a query with tokens "black/A cat/B sold/C". We calculate the probability of generating after "black/A" in the target:

• the target token ("cat/B") with a probability P (B|S, A)

• the token following the bi-gram in the context ("sold/C") with a probability P (C|S, A)

We do this for two settings: 1) using the original context session as S and 2) using a modified context session S for which we swapped tokens B and C in the context (i.e., substituting "black/A sold/C cat/B" to "black/A cat/B sold/C").

The goal is to assess whether the model favors a language model (LM) that captured that B usually follows A, or rather a copy mechanism that mainly considers positions from the context session (POS). Following this process, the average probabilities are computed over a set of 20000 sessions and are reported in table 4 for the different transformers. First, when position (in the context session) and language model agree (first and second columns), the probabilities are high for the real target and low otherwise. Among the different models, we note that the best performing models (section 4.4) have a very high probability of generating the token B (between 0.7 and 0.8).

When position (in the context session) and language model disagree (fourth and fifth column), the behavior of the architectures is quite different. Apart from the TS WP (and to a lesser extent its hierarchical version) which mostly follows the language model (0.03 vs 0.19) and ignores the context session, we see that all the other models assign balanced probabilities to position and language in these swapped sessions.

Sufficiently powerful flat models such as BART appear sufficient to capture the query organization of sessions, while keeping enough flexibility to adapt to perturbations. We indeed observe that BART has both high probabilities of either following the language model or the position-based prediction (total probability of 0.63), which is nearly as high as when the context session and language model match (0.70). This difference with the other models might explain why BART is performing so well: it leverages both the copying mechanism and its powerful language model.

Human evaluation

To further investigate the ability of the flat models, we conducted a human evaluation by comparing 100 queries predicted for AOL and MS Marco by all the models. The judges were presented complete sessions and corresponding suggestions predicted by each model. They had no knowledge of the ground truth or the user's goal. In our user modeling framework, we seek to evaluate whether suggestions make sense to annotators based on the user's session, not only whether they are syntactically correct. That's why judges were asked to evaluate the suggestions that were most likely to meet the user's need in the session by answering the question "is this query likely to follow in the session?".

They were asked to rank the predictions from most to least suitable. Annotators are supposed to be able to infer the user's purpose from the session. Indeed, no more can be expected from an optimal policy that only has the user session at its disposal, and this is what we are trying to assess. Giving the user's purpose to the annotators could have biased the evaluation by leading the annotators to evaluate too negatively many suggestions, even though they corresponded to average user behavior. We further asked the annotator to rank exact repetitions and generic queries (e.g. "google") as bad predictions. We report in table 5 the % of times a model is judged better than another one. The evaluation confirms the results obtained with the other metrics. The models ACG, HRED and the different transformers are increasingly better (e.g. on AOL, 27% of predicted queries are better for Bart than for HRED, and 17% for the other way around). Among transformers, pre-trained models perform better (5-10% gap), with Bart doing slightly better than Bert. Regarding WordPiece tokenization, they do perform better except for Transformer on AOL,

Conclusion

In this paper, inspired by the success of transformer-based models [Vaswani, 2017] in various NLP and IR tasks, we looked at the various architectures that could be applied to query generation. We compared tokenizers, architectures, and different pre-training methods. We show that while hierarchical models permit to obtain better performance than corresponding flat architectures, they are not adapted for long and complex sessions. We conducted a deeper analysis on the flat models to understand why they are better at handling these sessions. We analysed their generation process, and found that the flat transformer is, on one hand, a position model that is able to recover the structure of a web search session (input queries are concatenated), and on the other hand, a good (query) language model. Future work will focus on improving the hierarchical architecture, so the model can handle more complex search tasks, and incorporating signals of various natures (longer history, clicked documents) into transformer-based architectures. Our study is limited to query-based search sessions, but the hierarchical structure of data is also present in conversational searches [Aliannejadi, 2019;Zamani, 2020]. However, while in our case the user is modeled according to their own past actions only, the setting of conversational search requires to consider external data such as available documents in the collection, or the IR system's answers, to drive the user towards their target documents. Our study could be extended in future work to the conversational search setting by integrating actions from the search agent in the model. It will also focus on working on architectures able to cope with long sessions, potentially all the user history, using other recently introduced trans-formers [Dai, 2019b;[START_REF] Kitaev | [END_REF][START_REF] Beltagy | [END_REF] that overcome the limit of the maximum context length.

Figure 1 :

 1 Figure 1: Flat Transformer for Query Suggestion

Figure 2 :

 2 Figure 2: Hierarchical Transformer for Query Suggestion

Figure 3 :

 3 Figure 3: Difference between the performance on all the AOL sessions and on the noisy version (filtered/concatenated). Negative values indicate a degradation.

Figure 4 :

 4 Figure 4: Models scores depending on the length of the sessions

Figure 5 :

 5 Figure 5: Importance of the queries depending on their (normalized, and using quantiles) positions in a session (average over layers)

Finally

  we answer the last sub question Q3. (c) How does the model choose the next token to generate?

  Figure6: Importance of the tokens depending on their position in the queries (attention of the decoder on the encoder), for layer 1 (a) and layer 12 (b) the encoder. The X-axis corresponds to the context -i.e. the encoder tokens (averaged over all queries), while the Y-axis corresponds to the decoder -i.e. the decoder tokens. For the decoder, 0 corresponds to the START token. For instance, from (a) we see that when generating the 3rd token (row of index 2), the attention is focused mostly on the second token, and also (but less) on the first and third ones. This is different for the same token at layer 12 (b), where most of the attention is focused on the third token of every past query. Results are averaged over 20000 sessions.

Table 1 :

 1 Results on the MS MARCO (a) and the AOL dataset (b). We report different metrics, along with two quality indicators. Best results for a metric are reported with a bold font.

					(a) MS MARCO dataset
		II ACG ACG WP HRED HRED WP	TS TS WP H TS H TS WP BERT H BERT Enc BART BART H BART Enc T5	T5 H T5
	EM	0.173 0.044	0.041	0.139	0.129 0.174	0.197 0.164	0.170 0.223	0.182	0.184 0.226	0.183	0.175 0.203 0.121
	BLEU 1	0.584 0.435	0.416	0.572	0.555 0.579	0.596 0.574	0.589 0.617	0.597	0.591 0.618	0.592	0.598 0.576 0.565
	BLEU 2	0.369 0.200	0.182	0.341	0.320 0.372	0.377 0.363	0.371	0.402	0.378	0.385 0.419	0.383	0.379 0.375 0.335
	BLEU 3	0.218 0.092	0.087	0.193	0.176 0.223	0.248 0.218	0.224 0.274	0.234	0.238 0.275	0.236	0.230 0.238 0.174
	BLEU 4	0.202 0.073	0.068	0.175	0.161 0.213	0.239 0.201	0.206 0.268	0.217	0.222 0.266	0.221	0.212 0.231 0.149
	simextrema	0.835 0.798	0.780	0.828	0.817 0.833	0.840 0.834	0.837 0.846	0.839	0.837 0.848	0.839	0.837 0.837 0.830
	simpairwise	0.677 0.579	0.543	0.635	0.616 0.671	0.682 0.665	0.670 0.697	0.677	0.672 0.697	0.678	0.675 0.659 0.661
	New Words	0.950 0.138	0.354	0.594	0.604 0.886	0.880 0.902	0.899	0.870	0.902	0.902	0.858	0.911	0.879 0.910 0.895
	Repetion Rank 8.618 8.767	9.429	8.974	9.141 6.926	6.689 7.055	7.022	6.424	6.755	6.985	5.586	7.098	7.116 6.913 7.318
						(b) AOL dataset
		II ACG ACG WP HRED HRED WP	TS TS WP H TS H TS WP BERT H BERT Enc BART BART H BART Enc T5	T5 H T5
	EM	0.018 0.017	0.010	0.029	0.036 0.037	0.048 0.046	0.081	0.061	0.085	0.055 0.119	0.087	0.052 0.082 0.053
	BLEU 1	0.438 0.417	0.388	0.409	0.422 0.439	0.454 0.447	0.493	0.460	0.495	0.455 0.552	0.494	0.452 0.519 0.435
	BLEU 2	0.148 0.128	0.098	0.122	0.135 0.162	0.178 0.178	0.238	0.194	0.241	0.186 0.316	0.240	0.183 0.275 0.166
	BLEU 3	0.067 0.037	0.026	0.052	0.059 0.071	0.089 0.102	0.146	0.110	0.150	0.104 0.231	0.144	0.098 0.192 0.090
	BLEU 4	0.033 0.006	0.004	0.018	0.023 0.027	0.040 0.055	0.086	0.063	0.093	0.058 0.174	0.084	0.051 0.148 0.043
	simextrema	0.751 0.668	0.687	0.710	0.713 0.729	0.723 0.742	0.762	0.741	0.763	0.739 0.792	0.762	0.731 0.776 0.723
	simpairwise	0.484 0.408	0.390	0.404	0.415 0.447	0.457 0.462	0.501	0.466	0.504	0.459 0.558	0.499	0.454 0.537 0.435
	New Words	0.996 0.119	0.588	0.679	0.740 0.916	0.941 0.849	0.881	0.927	0.880	0.919	0.682	0.934	0.902 0.593 0.940
	Repetion Rank 9.711 7.138	9.128	7.841	7.157 8.683	8.300 6.830	4.970	6.668	4.203	6.132	2.204	3.665	6.203 1.468 6.324
		Table 2: Perplexities for Word-Piece Tokenizer-based models
			AOL MS MARCO
	ACG WP	1 175		242
	HRED WP 1 101		111
	TS WP	721		56
	H TS WP	486		56
	BERT		492		47
	H BERT	473		64
	Enc BART	557		52
	H BART	209		40
	BART		173		39
	Enc T5		92		22
	H T5		215		58
	T5		37		21

Table 3 :

 3 Generated queries for three sessions. The two first queries of the sessions are given in the top of the table (Q1 and Q2), and the first 5 suggestions of each model below.

		Q1. divorce chat rooms Q2. divorce support groups	Q1. maryland ocean city Q2. marylandocean vity hotel	Q1. carobean cruises Q2. spa resorts Q3. disney world
		-divorce support groups	-maryland hotel hotel	-disney world resorts
		-divorce chat groups	-maryland hotel ocean	-disney resorts resorts
	HRED WP	-divorce divorce groups	-maryland hotel hotel ocean	-disney world
		-divorce groups groups	-maryland hotel	-disney vacation resorts
		-divorce support	-maryland hotel ocean ocean	-disney resorts
		-chat room listings	-ocean city maryland	-disney world
		-ebay	-ocean city md	-travelocity
	TS WP	-aol chat	-mapquest	-disney world hotels
		-chat rooms	-ocean county maryland	-disney world cruise
		-divorce chat room	-expedia	-disney cruise
		-divorce support groups	-maryland ocean city	-disney world
		-free divorce support groups	-ocean city maryland	-sea world
	H TS WP	-divorce	-hotels in maryland	-disneyworld
		-divorce chat rooms	-hotel ocean city	-carnival cruise
		-divorce support	-mapquest	-spa resorts
		-divorce chat rooms	-maryland hotel	-disney world
		-divorce chat room	-maryland hotels	-disney world cruises
	Enc BART	-divorce support group	-mapquest	-disney world texas
		-divorce support	-maryland	-disney world hotels
		-divorce chat	-maryland beach hotel	-disney world resort
		-divorce support groups	-maryland ocean city	-disney world
		-divorce	-marriott hotels	-spa resorts
	H BART	-free divorce chat rooms	-marylando ocean city	-disney world cruise
		-divorce help	-marriott	-disney world resorts
		-free divorce help	-mapquest	-ebay
		-divorce chat rooms	-maryland ocean city hotel	-disney world
		-divorce support groups	-maryland ocean city	-spa resorts
	BART	-free divorce support groups	-maryland ocean city hotels	-disneyworld
		-divorce chat room	-maryland ocean town hotel	-disney world cruise
		-free divorce chat rooms	-maryland ocean city resort	-disney world hotels

Table 4 :

 4 Probabilities on mixed and unmixed sessions. For each original and swapped sessions, the preference of the model is highlighted in red (for differences above 0.01)

	Session S		original			B/C swapped
		... A B C ...			... A C B ...
	probability	p(B|S, A) p(C|S, A) total p(B|S, A) p(C|S, A)	total
	favors	LM/POS			LM	POS	LM/POS
	Transformer WP	0.19	0.03	0.22	0.19	0.03	0.22
	H Transformer WP	0.67	0.01	0.68	0.37	0.22	0.59
	BERT	0.46	0.01	0.47	0.17	0.23	0.40
	Enc BART	0.51	0.00	0.51	0.21	0.20	0.41
	Enc T5	0.57	0.02	0.59	0.21	0.26	0.47
	BART	0.70	0.03	0.73	0.35	0.28	0.63
	T5	0.80	0.02	0.82	0.36	0.36	0.72
	H BERT	0.63	0.01	0.64	0.20	0.34	0.54
	H BART	0.72	0.01	0.73	0.29	0.28	0.57
	H T5	0.68	0.01	0.69	0.31	0.27	0.58

Table 5 :

 5 Human evaluation on 100 queries for MS Marco and AOL. Each cell is the % of times model in row is better than model in column vs the reverse (and the remaining % is equality) .

		HRED	HRED WPT	ACG	ACG WPT	TS	TS-WPT	BERT
				MS Marco
	HRED WPT	19% vs 18%
	ACG	26% vs 29% 22% vs 22%
	ACG WPT	20% vs 22% 17% vs 21% 22% vs 24%
	TS	32% vs 11% 33% vs 13% 38% vs 16% 36% vs 13%
	TS WPT	37% vs 10% 35% vs 10% 42% vs 15% 39% vs 11% 15% vs 10%
	BERT	41% vs 10%	38% vs 8%	42% vs 15% 43% vs 11% 25% vs 15% 22% vs 18%
	BART	43% vs 9%	42% vs 11% 45% vs 11% 44% vs 9% 27% vs 15% 21% vs 16% 19% vs 16%
				AOL
	HRED WPT	23% vs 16%
	ACG	13% vs 24% 10% vs 29%
	ACG WPT	4% vs 24%	6% vs 32%	7% vs 15%
	TS	34% vs 17% 31% vs 20%	35% vs 3%	43% vs 5%
	TS WPT	28% vs 15% 24% vs 18%	32% vs 5%	38% vs 5% 13% vs 18%
	BERT	34% vs 13% 31% vs 18%	41% vs 9%	44% vs 6% 28% vs 24% 28% vs 19%
	BART	38% vs 17% 35% vs 20% 41% vs 11% 45% vs 8% 30% vs 28% 31% vs 24% 26% vs 24%
	and for ACG.

Based on https://github.com/hanxiao/bert-as-service, and our own preliminary experiments

As we want to encourage the models trained with a word tokenizer to generate tokens present in the vocabulary, we follow[START_REF][END_REF] and apply a penalty on the "OOV" token in the beam search. To compute the metrics, we ignored the OOV token that can be generated by HRED or ACG -queries composed only of OOV words are skipped.

Acknowledgement: This work was supported by the Agence National de la Recherche (ANR), through project CoST, code ANR-18-CE23-0016.