The Principled Approach to Early Ranking Stages

A systematic method for designing and evaluating candidate generation and early ranking stages in recommender systems, with an in-depth analysis of the core guiding principle.

It is well known that in recommendation systems, there are several stages of building recommendations: first comes candidate generation, also often referred to as retrieval, followed by one or more stages of ranking. Academic papers do not pay much attention to the early stages. But in practice, they are quite important. And it is important how to measure their quality.

Candidate generation is most often organized as a combination of different sources:

• the most popular items,
• similar to the user’s history,
• ),
• a combination of the previous methods at different levels: for instance, taking categories from the user’s history (or from ANN, or popular ones), and then selecting popular items from them.

Although each method here might not be complex on its own, the entire combination turns out to be quite non-trivial, prompting one to think: how can it be optimized? To do this, of course, it’s necessary to define what exactly needs to be optimized, i.e., what metric should be used to measure the quality of candidate generation.

Although our discussion focuses on the candidate generation phase, it’s worth noting that these principles can equally apply to all early ranking stages, as they also provide candidates for subsequent stages.

There are various approaches. Sometimes the quality is simply not measured (or just ‘eyeballed’) and this stage is not systematically optimized. Sometimes, the overall relevance of the candidates is measured in some way. If the system recommends something odd, it is also considered indicative of a bug in candidate generation. Sometimes, this relevance is even contrasted with what is optimized in the final stage. That is, the candidates should already be sufficiently relevant, no matter how measured, and the final ranking will select the most engaging ones (attractive, clickable, etc.)

Sometimes, especially in papers, metrics like HitRate@k, Recall@k, Precision@k, MRR, NDCG, etc., are used, focusing only on positive (relevant) documents. A document is considered relevant if the user subsequently interacted with it. I prefer this approach over the previous ones, although there is a significant issue with various biases: for example, users tend to interact more frequently with items that the system itself recommends.

At some point, I attempted to formulate a different approach to candidate generation and have since been an advocate of it. Fortunately, I am not the only one — this approach is already in use in various systems (for example, as detailed in . This principle dictates that all such rules, except for the hard ones, should be applied at the final stage, and the early stages will adapt to them. This refers not only to hacks but also to reasonable methods for improving various aspects of recommendations like exploration, diversity, etc. You have to provide diverse candidates simply because the ranking selects them.

— the denominator in NDCG) seems not to be very crucial. Any of these options can be chosen based on preference.

There’s a technical nuance to consider though. If such a metric is measured offline, one needs to be able to run ranking (or the entire recommendation stack) on custom candidates. This can be done either through simulation (offline replay — that is, attempting to retrospectively reproduce all the information about all entities) on historical queries, or through scraping — as mentioned earlier, sending a large number of new queries to the recommendation service, so that it uses the candidate generation methods of interest. In both cases, results (predictions of the final model) are obtained for different generation methods for the same queries. This is beneficial for the sensitivity of the metric.

If, however, this metric is measured online, on a production service, it can all be calculated simply based on the logged predictions of the model. This is much simpler, but not as flexible, and the comparison will be across different queries. The sensitivity of the metric decreases (it’s possible that one of the methods just happened to receive more complex queries).

Now let’s move on to the general case: final ranking is not just the predictions of a certain model, but also involves a lot of other logic, reranking, business rules, randomization, etc. When you think about how to compare different sets of candidates in such a loose formulation (what is good and what is bad), it’s not at all obvious.

However, I once devised a method for this, which turned out to be very simple and effective. And so far, I have not seen it mentioned anywhere else.

The method is as follows. We add a special source to the list of candidate sources, which produces random candidates (say, uniformly distributed). We assign this source a small fixed quota (say, 50 candidates). Then we observe what proportion of the recommended documents ultimately come from this source. If our main candidate generation is good enough, then random candidates will very rarely outperform it, i.e., make it to the top. If it is poor, they will do so frequently.

Of course, here we assume that adding random candidates does not significantly worsen the system: most of them will not be recommended, and those that are recommended will not greatly deteriorate the user experience, and will even add exploration both for users and for the ranking model (it will further train on these examples). If this is not the case, then it’s first necessary to ‘fix the ranking’. 😉

The coolest thing about this method is that it can serve not only as a metric for candidate generation, but also as a monitoring tool for the health of the entire system, including the final ranking. It checks how well candidate generation is aligned with ranking (optimized for ranking). If the ranking itself degrades for some reason, then the candidates also become less suitable for it. We have seen this in practice, when one of the components broke down, the proportion of random candidates in the response increased.

By the way, the randomness of this special source can be adjusted. If you use not a uniform distribution but one proportional to the popularity of the document, it becomes a stronger ‘adversarial’ player (which can also increase sensitivity). However, with uniform sampling, it’s possible to provide an analytical estimate of the proportion of queries where our candidate generation was ideal (i.e., the result would not have changed, even if we had added the entire database to the candidates):

In this formula, N represents the total number of candidates in the database, k is the number of random candidates used, and R denotes the ratio of queries where at least one random candidate appears in the output.

Conclusion

Throughout this exploration, we’ve centered on a specific principle for candidate generation and early ranking stages in recommendation systems. By thoroughly examining its advantages and challenges, and proposing practical evaluation methods, we underscored the principle’s potential as a powerful tool for refining these systems. Embracing this principle not only simplifies the complex process of recommendation but also ensures efficiency and effectiveness. As we continue to refine and apply this principle, it stands as a promising direction for advancing the field of recommendation systems.

on Medium, where people are continuing the conversation by highlighting and responding to this story.