From structured search to learning-to-rank-and-retrieve

Using reinforcement learning improves candidate selection and ranking for search, ad platforms, and recommender systems.

Most modern search applications, ad platforms, and recommender systems share a similar multitier information retrieval (IR) architecture with (at a minimum) a candidate selection or retrieval phase and a candidate ordering or ranking phase. Given a query and a context, the retrieval phase reduces the space of possible candidates from millions, sometimes billions, to (typically) hundreds or less. The ranking phase then fine-tunes the ordering of candidates to be presented to customers. This approach is both flexible and scalable.

Search funnel.png
A typical search funnel, from query understanding to displaying results.

At Amazon Music, we have previously improved our ranking of the top-k candidates by applying learning-to-rank (LTR) models, which learn from customer feedback or actions (clicks, likes, adding to favorites, playback, etc.). We combine input signals from the query, context, customer preferences, and candidate features to train the models.

Related content
Models adapted from information retrieval deal well with noisy GPS input and can leverage map information.

However, these benefits apply only to the candidates selected during the retrieval phase. If the best candidate is not in the candidate set, it doesn’t matter how good our ranking model is; customers will not get what they want.

More recently, we have extended the learning-to-rank approach to include retrieval, in what we are calling learning-to-rank-and-retrieve (LTR&R). Where most existing retrieval models are static (deterministic), learning to retrieve is dynamic and leverages customer feedback.

Consequently, we advocate an approach to learning to retrieve that uses contextual multiarmed bandits, a form of reinforcement learning that optimizes the trade-off between exploring new retrieval strategies and exploiting known ones, in order to minimize “regret”.

In what follows, we review prior approaches to both retrieval and ranking and show how, for all of their success, they still have shortcomings that LTR&R helps address.

Candidate selection strategies

Structured search and query understanding

A common candidate retrieval strategy is full-text search, which indexes free-text documents as bags of words stored in an inverted index using term statistics to generate relevance scores (e.g., the BM25 ranking function). The inverted index maps words to documents containing those words.

Full-text search solves for many search use cases, especially when there is an expectation that the candidates for display (e.g., track titles or artist names) should bear a lexical similarity to the query.

Related content
Applications in product recommendation and natural-language processing demonstrate the approach’s flexibility and ease of use.

We can extend full-text search in a couple of ways. One is to bias the results using some measure of entity quality. For example, we can take the popularity of a music track into account when computing a candidate score such that the more popular of two tracks with identical titles will be more likely to make it into the top page.

We can also extend full-text search by applying it in the context of structured data (often referred to as metadata). For instance, fields in a document might contain entity categories (e.g., product types or topics) or entity attributes (such as brand or color) that a more elaborate scoring function (e.g., Lucene scoring) could take into account.

Structured search (SS) can be effectively combined with query understanding (QU), which maps query tokens to entity categories, attributes, or combinations of the two, later used as retrieval constraints. These methods often use content understanding to extract metadata from free text in order to tag objects or entities with categories and attributes stored as fields, adding structure to the underlying text.

Neural retrieval models

More recently, inspired by advances in representation learning, transformers, and large language models for natural-language processing (NLP), search engineers and scientists have turned their attention to vector search (a.k.a. embedding-based retrieval). Vector search uses deep-learning models to produce dense (e.g., sentence-BERT) as well as sparse (e.g., SPLADE) vector representations, called embeddings, that capture the semantic content of queries, contexts, and entities. These models enable information retrieval through fast k-nearest-neighbor (k-NN) vector similarity searches using exact and approximate nearest-neighbor (ANN) algorithms.

Related content
Thorsten Joachims answers 3 questions about the work that earned him the award.

Vector-and-hybrid (lexical + vector) search yields more relevant results than traditional approaches and runs faster on zero-shot IR models, according to the BEIR benchmark. In recommender systems, customer and session embeddings (as query/context) and entity embeddings are also used to personalize candidates in the retrieval stage. These documents can be further reranked by another LTR neural model in a multistage ranking architecture.

A memory index

Research suggests that users’ actions (e.g., query-click information) are the single most important field for retrieval, serving as a running memory of which entities have worked and which haven’t for a given query/context. In a cold-start scenario, we can even train a model that, when given an input document, generates questions that the document might answer (or, more broadly, queries for which the document might be relevant).

Related content
Amazon scientist’s award-winning paper predates — but later found applications in — the deep-learning revolution.

These predicted questions (or queries) and scores are then appended to the original documents, which are indexed as predicted query-entity (Q2E) scores. Once query-entailed user actions on entities are captured, these computed statistics can replace predicted values, becoming actual Q2E scores that update the memory index used in ranking. As newly encountered queries show up, resulting from hits on other strategies, additional Q2E pairs and corresponding scores will be generated.

Real-world complications

In his article “Throwing needles into haystacks”, Daniel Tunkelang writes,

If you’re interested in a particular song, artist, or genre, your interaction with a search engine should be pretty straightforward. If you can express a simple search intent using words that map directly to structured data, you should reasonably expect the search application to understand what you mean and retrieve results accordingly.

However, as we will show, when building a product that serves millions of customers who express themselves in ways that are particular to their experiences and locales, we cannot reasonably expect queries “to express a search intent using words that map directly to structured data.”

Query processing.png
Processing of the query “tayler love” by a complex QU + SS retrieval system.

Let’s start by unpacking an example. Say we want to process the query “love” in a music search system. Even for a single domain (e.g., music/audio) there are many kinds of entities that could match this query, such as songs, artists, playlists, stations, and even podcasts. For each of these categories there could be hundreds and even thousands of possible candidates matching the keyword “love”. Beyond that, each category has different attributes that can also match the keyword (e.g., “love” maps to the genre “love songs”).

Customers may also expect to see related entities in the search results (e.g., artists related to a song returned). So while in the customer’s mind there is surely a main search intent, expressed via a keyword, there could be many possible mappings or interpretations that should be considered. Each of these has a likelihood of being correct, which would generate series of underlying structured searches, first to identify the possible targeted entities and then to bring along related or derived content.

Related content
Framework improves efficiency, accuracy of applications that search for a handful of solutions in a huge space of candidates.

As we have discovered, the crafting and maintenance of such a system is inherently non-scalable.

There is also the problem of compounding errors due to incorrect query understanding and/or content understanding. Category and attribute assignment to queries and entities, which typically uses a combination of human tagging and ML classification models, could be wrong or even completely missing. Furthermore, assignment values may not be binary. For example, “Taylor Swift” is clearly considered a pop artist, but some of her songs are also categorized as country music, alternative/indie, or indie folk.

Given the centrality of interpretation in selecting candidate results, the ability to learn from interactions with customers is essential to successful retrieval. Search applications based on QU+SS and/or FT search, however, usually use static query plans that cannot incorporate feedback in the retrieval stage.

On the other hand, while deep models show enormous promise, they also require significant investment and seem unlikely to completely replace keyword-based retrieval methods in the foreseeable future.

Learning to retrieve

In a world with infinite resources and no latency constraints, we wouldn’t need a retrieval funnel, and we might prefer to rank all possible candidates. But we don’t live in such a world. The reality is that deciding the right balance between increasing precision, usually by exploiting what we already know works, and increasing recall, by exploring more sources and increasing the number of candidates retrieved, is critical for search, ad platforms, and recommender systems. This is especially true in very dynamic applications such as music search, where context matters and new entities, categories, and attributes get added all the time.

And while it would be terrific if we could identify the single candidate selection strategy that produces an optimal top page for every query/context, in practice this is not achievable. The optimal candidate selection strategy depends on the query/context, but we do not know that dependency a priori. We need to learn to retrieve.

Related content
Two KDD papers demonstrate the power and flexibility of Amazon’s framework for “extreme multilabel ranking”.

One way to try to strike the right explore-exploit trade-off is to implement a multiarmed bandit (MAB) optimization, to learn a policy to select a subset of retrieval strategies (arms) that maximize the sum of stochastic rewards earned through a sequence of searches. That is, the policy should maximize the sum of the likelihoods that the expected results are present in the sets produced by such strategies, as later confirmed by user actions (such as clicking on a link).

The MAB approach uses reinforcement learning (RL) to draw more candidates from strategies that perform well while drawing fewer from underperforming strategies. In particular, for learning-to-retrieve, contextual multiarmed bandit algorithms are ideal, as they are designed to take the query/context features and action features (related to the candidate selection strategy) as input to maximize the reward while keeping healthy rate of exploration to minimize regret.

retrieval ensemble.png
Using reinforcement learning to blend podcast search results from different retrieval strategies.

For example, we expect that embeddings based on language models (i.e., a semantic strategy) will perform better for topic search, while the lexical strategy will be more useful for direct entity search (a.k.a. spearfishing queries).

Query/context features may include query information, such as language, type of query, QU slotting and intent classification, query length, etc.; demographic and profile information about your user; information about the current time, such as day of the week, weekend or not, morning or afternoon, holiday season or not, etc.; and historical (aggregate) data of user behavior, such as what genres of music this user has listened to the most.

Action features may include relevance/similarity scores; historical query-strategy performance and number of results; types of entities retrieved, e.g., newly added, popular, personalized, etc.; and information about the underlying retrieval source, e.g., lexical matching, text/graph embeddings, memory, etc.

The model learns a generalization based on these features and the combination of retrieval strategies that maximizes the reward. Finally, we use the union of results produced by the selected strategies to produce a single candidate list that bubbles up to the ranking layer.

LTR&R.png
Generic learning-to-rank-and-retrieve (LTR&R) architecture.

Summary

In conclusion, using query understanding (when available) and structured search is a good place to start when building search systems. By adding learning-to-rank, you can start to reap the benefits of factoring in customer feedback and improving the system’s quality. However, this is not sufficient to address the hard problems we observe in real-life applications like music search.

As an extension to the common retrieval-and-ranking phases present in the multitier IR architectures used in most search, ads, and recommender systems, we propose a generic learning-to-rank-and-retrieve (LTR&R) system architecture that comprises multiple candidate generators based on different retrieval strategies. Some produce well-known, exploitable results, like those based on our memory index, while others focus more on exploration, producing novel, riskier, or more-unexpected results that can increase the diversity of the feedback and provide counterfactual data.

This feedback cannot be collected by the static (i.e., fully deterministic) retrieval-and-ranking systems used nowadays. We also suggest using ML, and in particular RL, to optimize the selection of the subset of retrieval strategies and the number of candidates drawn from them, to maximize the likelihood of finding the expected result in such sets.

By incorporating customer feedback and using ML for LTR&R we can (1) simplify the search systems and (2) bubble up the best possible candidates for our customers. LTR&R is a promising path to solving both precision-oriented search and broad and ambiguous queries that require more recall and exploration.

Acknowledgments: Chris Chow, Adam Tang, Geetha Aluri, and Boris Lerner

Related content

US, WA, Seattle
The retail pricing science and research group is a team of scientists and economists who design and implement the analytics powering pricing for Amazon’s on-line retail business. The team uses world-class analytics to make sure that the prices for all of Amazon’s goods and services are aligned with Amazon’s corporate goals. We are seeking an experienced high-energy Economist to help envision, design and build the next generation of retail pricing capabilities. You will work at the intersection of economic theory, statistical inference, and machine learning to design new methods and pricing strategies to deliver game changing value to our customers. Roughly 85% of previous intern cohorts have converted to full time scientist employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com. Key job responsibilities Amazon’s Pricing Science and Research team is seeking an Economist to help envision, design and build the next generation of pricing capabilities behind Amazon’s on-line retail business. As an economist on our team, you will work at the intersection of economic theory, statistical inference, and machine learning to design new methods and pricing strategies with the potential to deliver game changing value to our customers. This is an opportunity for a high-energy individual to work with our unprecedented retail data to bring cutting edge research into real world applications, and communicate the insights we produce to our leadership. This position is perfect for someone who has a deep and broad analytic background and is passionate about using mathematical modeling and statistical analysis to make a real difference. You should be familiar with modern tools for data science and business analysis. We are particularly interested in candidates with research background in applied microeconomics, econometrics, statistical inference and/or finance. A day in the life Discussions with business partners, as well as product managers and tech leaders to understand the business problem. Brainstorming with other scientists and economists to design the right model for the problem in hand. Present the results and new ideas for existing or forward looking problems to leadership. Deep dive into the data. Modeling and creating working prototypes. Analyze the results and review with partners. Partnering with other scientists for research problems. About the team The retail pricing science and research group is a team of scientists and economists who design and implement the analytics powering pricing for Amazon’s on-line retail business. The team uses world-class analytics to make sure that the prices for all of Amazon’s goods and services are aligned with Amazon’s corporate goals.
US, CA, San Francisco
The retail pricing science and research group is a team of scientists and economists who design and implement the analytics powering pricing for Amazon's on-line retail business. The team uses world-class analytics to make sure that the prices for all of Amazon's goods and services are aligned with Amazon's corporate goals. We are seeking an experienced high-energy Economist to help envision, design and build the next generation of retail pricing capabilities. You will work at the intersection of statistical inference, experimentation design, economic theory and machine learning to design new methods and pricing strategies for assessing pricing innovations. Roughly 85% of previous intern cohorts have converted to full time scientist employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com. Key job responsibilities Amazon's Pricing Science and Research team is seeking an Economist to help envision, design and build the next generation of pricing capabilities behind Amazon's on-line retail business. As an economist on our team, you will will have the opportunity to work with our unprecedented retail data to bring cutting edge research into real world applications, and communicate the insights we produce to our leadership. This position is perfect for someone who has a deep and broad analytic background and is passionate about using mathematical modeling and statistical analysis to make a real difference. You should be familiar with modern tools for data science and business analysis. We are particularly interested in candidates with research background in experimentation design, applied microeconomics, econometrics, statistical inference and/or finance. A day in the life Discussions with business partners, as well as product managers and tech leaders to understand the business problem. Brainstorming with other scientists and economists to design the right model for the problem in hand. Present the results and new ideas for existing or forward looking problems to leadership. Deep dive into the data. Modeling and creating working prototypes. Analyze the results and review with partners. Partnering with other scientists for research problems. About the team The retail pricing science and research group is a team of scientists and economists who design and implement the analytics powering pricing for Amazon's on-line retail business. The team uses world-class analytics to make sure that the prices for all of Amazon's goods and services are aligned with Amazon's corporate goals.
US, WA, Bellevue
We are looking for detail-oriented, organized, and responsible individuals who are eager to learn how to work with large and complicated data sets. Some knowledge of econometrics, as well as basic familiarity with Python is necessary, and experience with SQL and UNIX would be a plus. These are full-time positions at 40 hours per week, with compensation being awarded on an hourly basis. You will learn how to build data sets and perform applied econometric analysis at Internet speed collaborating with economists, scientists, and product managers. These skills will translate well into writing applied chapters in your dissertation and provide you with work experience that may help you with placement. Roughly 85% of interns from previous cohorts have converted to full time economics employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com.
US
The Amazon Supply Chain Optimization Technology (SCOT) organization is looking for an Intern in Economics to work on exciting and challenging problems related to Amazon's worldwide inventory planning. SCOT provides unique opportunities to both create and see the direct impact of your work on billions of dollars’ worth of inventory, in one of the world’s most advanced supply chains, and at massive scale. We are looking for detail-oriented, organized, and responsible individuals who are eager to learn how to work with large and complicated data sets. We are looking for a PhD candidate with exposure to Program Evaluation/Causal Inference. Knowledge of econometrics and Stata/R/or Python is necessary, and experience with SQL, Hadoop, and Spark would be a plus. These are full-time positions at 40 hours per week, with compensation being awarded on an hourly basis. You will learn how to build data sets and perform applied econometric analysis at Internet speed collaborating with economists, scientists, and product managers. These skills will translate well into writing applied chapters in your dissertation and provide you with work experience that may help you with placement. Roughly 85% of previous cohorts have converted to full time scientist employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com.
US, WA, Seattle
The Selling Partner Fees team owns the end-to-end fees experience for two million active third party sellers. We own the fee strategy, fee seller experience, fee accuracy and integrity, fee science and analytics, and we provide scalable technology to monetize all services available to third-party sellers. We are looking for an Intern Economist with excellent coding skills to design and develop rigorous models to assess the causal impact of fees on third party sellers’ behavior and business performance. As a Science Intern, you will have access to large datasets with billions of transactions and will translate ambiguous fee related business problems into rigorous scientific models. You will work on real world problems which will help to inform strategic direction and have the opportunity to make an impact for both Amazon and our Selling Partners.
US, WA, Bellevue
We are looking for detail-oriented, organized, and responsible individuals who are eager to learn how to work with large and complicated data sets. We are looking for a PhD candidate with exposure to Program Evaluation/Causal Inference. Some knowledge of econometrics, as well as basic familiarity with Stata or R is necessary, and experience with SQL, Hadoop, Spark and Python would be a plus. These are full-time positions at 40 hours per week, with compensation being awarded on an hourly basis. You will learn how to build data sets and perform applied econometric analysis at Internet speed collaborating with economists, scientists, and product managers. These skills will translate well into writing applied chapters in your dissertation and provide you with work experience that may help you with placement. Roughly 85% of previous cohorts have converted to full time scientist employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com.
US, MA, Westborough
Are you inspired by invention? Is problem solving through teamwork in your DNA? Do you like the idea of seeing how your work impacts the bigger picture? Answer yes to any of these and you’ll fit right in here at Amazon Robotics. We are a smart team of doers that work passionately to apply cutting edge advances in robotics and software to solve real-world challenges that will transform our customers’ experiences in ways we can’t even imagine yet. We invent new improvements every day. We are Amazon Robotics and we will give you the tools and support you need to invent with us in ways that are rewarding, fulfilling and fun. Amazon Robotics is seeking interns and co-ops with a passion for robotic research to work on cutting edge algorithms for robotics. Our team works on challenging and high-impact projects, including allocating resources to complete a million orders a day, coordinating the motion of thousands of robots, autonomous navigation in warehouses, identifying objects and damage, and learning how to grasp all the products Amazon sells. We are seeking internship candidates with backgrounds in computer vision, machine learning, resource allocation, discrete optimization, search, and planning/scheduling. You will be challenged intellectually and have a good time while you are at it! Please note that by applying to this role you would be considered for Applied Scientist summer intern, spring co-op, and fall co-op roles on various Amazon Robotics teams. These teams work on robotics research within areas such as computer vision, machine learning, robotic manipulation, navigation, path planning, perception, artificial intelligence, human-robot interaction, optimization and more.
US, MA, Westborough
Are you inspired by invention? Is problem solving through teamwork in your DNA? Do you like the idea of seeing how your work impacts the bigger picture? Answer yes to any of these and you’ll fit right in here at Amazon Robotics. We are a smart team of doers that work passionately to apply cutting edge advances in robotics and software to solve real-world challenges that will transform our customers’ experiences in ways we can’t even imagine yet. We invent new improvements every day. We are Amazon Robotics and we will give you the tools and support you need to invent with us in ways that are rewarding, fulfilling and fun. Amazon Robotics is seeking interns and co-ops with a passion for robotic research to work on cutting edge algorithms for robotics. Our team works on challenging and high-impact projects, including allocating resources to complete a million orders a day, coordinating the motion of thousands of robots, autonomous navigation in warehouses, identifying objects and damage, and learning how to grasp all the products Amazon sells. We are seeking internship candidates with backgrounds in computer vision, machine learning, resource allocation, discrete optimization, search, and planning/scheduling. You will be challenged intellectually and have a good time while you are at it! Please note that by applying to this role you would be considered for Applied Scientist summer intern, spring co-op, and fall co-op roles on various Amazon Robotics teams. These teams work on robotics research within areas such as computer vision, machine learning, robotic manipulation, navigation, path planning, perception, artificial intelligence, human-robot interaction, optimization and more.
US, WA, Bellevue
We are looking for detail-oriented, organized, and responsible individuals who are eager to learn how to work with large and complicated data sets. Some knowledge of econometrics, as well as basic familiarity with Python is necessary, and experience with SQL and UNIX would be a plus. These are full-time positions at 40 hours per week, with compensation being awarded on an hourly basis. You will learn how to build data sets and perform applied econometric analysis at Internet speed collaborating with economists, scientists, and product managers. These skills will translate well into writing applied chapters in your dissertation and provide you with work experience that may help you with placement. Roughly 85% of previous cohorts have converted to full time scientist employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com.
US, MA, Boston
Are you inspired by invention? Is problem solving through teamwork in your DNA? Do you like the idea of seeing how your work impacts the bigger picture? Answer yes to any of these and you’ll fit right in here at Amazon Robotics. We are a smart team of doers that work passionately to apply cutting edge advances in robotics and software to solve real-world challenges that will transform our customers’ experiences in ways we can’t even imagine yet. We invent new improvements every day. We are Amazon Robotics and we will give you the tools and support you need to invent with us in ways that are rewarding, fulfilling and fun. Amazon Robotics, a wholly owned subsidiary of Amazon.com, empowers a smarter, faster, more consistent customer experience through automation. Amazon Robotics automates fulfillment center operations using various methods of robotic technology including autonomous mobile robots, sophisticated control software, language perception, power management, computer vision, depth sensing, machine learning, object recognition, and semantic understanding of commands. Amazon Robotics has a dedicated focus on research and development to continuously explore new opportunities to extend its product lines into new areas. AR is seeking uniquely talented and motivated data scientists to join our Global Services and Support (GSS) Tools Team. GSS Tools focuses on improving the supportability of the Amazon Robotics solutions through automation, with the explicit goal of simplifying issue resolution for our global network of Fulfillment Centers. The candidate will work closely with software engineers, Fulfillment Center operation teams, system engineers, and product managers in the development, qualification, documentation, and deployment of new - as well as enhancements to existing - operational models, metrics, and data driven dashboards. As such, this individual must possess the technical aptitude to pick-up new BI tools and programming languages to interface with different data access layers for metric computation, data mining, and data modeling. This role is a 6 month co-op to join AR full time (40 hours/week) from July – December 2023. The Co-op will be responsible for: Diving deep into operational data and metrics to identify and communicate trends used to drive development of new tools for supportability Translating operational metrics into functional requirements for BI-tools, models, and reporting Collaborating with cross functional teams to automate AR problem detection and diagnostics