At Spotify, search has been traditionally seen as a tool for retrieving content, with the search system optimized for when the user has a specific search target in mind. In particular we have relied on an instant search system providing results for each keystroke, which works well for known-item search, when queries are straightforward, and the catalog is small. However, as Spotify's catalog grows in size and variety, it becomes increasingly difficult for users to define their search intents accurately. Furthermore, as we expand the offering, we need to help users discover more content both when it comes to new content types, e.g. audiobooks, as well as for new content/creators within existing content types. To solve this we have introduced a hybrid Query Recommendation system (QR) that helps the user formulate more complex exploratory search intents, while still serving known-item lookups efficiently. This experience has been rolled out worldwide to all mobile users resulting in an increase in exploratory intent queries of ~9% in online A/B tests.