Users may strive to formulate an adequate textual query for
their information need. Search engines assist the users by
presenting query suggestions. To preserve the original search
intent, suggestions should be context-aware and account for
the previous queries issued by the user. Achieving context
awareness is challenging due to data sparsity. We present
a probabilistic suggestion model that is able to account for
sequences of previous queries of arbitrary lengths. Our novel
hierarchical recurrent encoder-decoder architecture allows
the model to be sensitive to the order of queries in the context
while avoiding data sparsity. Additionally, our model
can suggest for rare, or long-tail, queries. The produced suggestions
are synthetic and are sampled one word at a time,
using computationally cheap decoding techniques. This is in
contrast to current synthetic suggestion models relying upon
machine learning pipelines and hand-engineered feature sets.
Results show that it outperforms existing context-aware approaches
in a next query prediction setting. In addition to
query suggestion, our model is general enough to be used in
a variety of other applications.