Search Ranking System

Learning to Rank Search Results

Design the ranking layer of a search engine: retrieve candidates cheaply, order them with a learned model such as LambdaMART, measure quality with NDCG, and learn from clicks without being fooled by position bias.

Overview

Finding documents that match a query is the easy half of search. The hard half is ordering them: users look at the first few results, so the value of a search engine is almost entirely in what it puts at the top. This problem is about that ranking layer: the models, the features they use, how they are trained and measured, and how they run fast enough for every query.

The building blocks of the index (tokenizing, the inverted index, sharding, replication) are covered in the Search System Design topic; here they are simply the stage that hands the ranker about a thousand candidates.

The interview turns on three ideas. Two stages: cheap retrieval over everything for recall, then an expensive ranker over a few hundred candidates for precision at the top. Learning to rank: a model such as LambdaMART (Burges, 2010) trained to optimize a ranking metric directly, where the metric is usually NDCG, introduced by Järvelin and Kekäläinen (2002). Biased feedback: clicks are cheap labels, but users click what is shown high, so training on raw clicks teaches the model to repeat its own past choices.

Questions to ask first

What is searched? — 100 million documents (products, articles or listings)
How much traffic? — 200 million queries a day, peaks at 3× the average
How fast? — Ranking must fit in about 50 ms of a 200 ms search budget (targets we chose)
What does good mean? — Relevant results at the top; judged by people on a sample, measured by clicks online
Personalized? — Some user features, but the same query mostly gets the same order
How often do models change? — Retrained regularly; every change goes through an experiment

What you will be able to do

Explain why ranking is split into retrieval and ranking stages, and size each stage.
Compute NDCG by hand and explain why it suits ranking.
Explain how LambdaMART turns a ranking metric into a trainable objective.
Build training labels from judgments and clicks, correcting for position bias.
Take a new ranker from offline evaluation through an online experiment to production.

Key concepts

Two-stage ranking
Recall versus precision at the top
Learning to rank
LambdaMART
NDCG
Graded judgments
Position bias
Inverse propensity weighting
Feature logging
Interleaving and A/B tests

Functional requirements

Return the top results for a query, ordered by predicted relevance
Use query, document, query-document and user features in the ranking
Log every impression (what was shown, where, with which model and features) and every click
Train new rankers from judgments and clicks, and compare them offline
Run online experiments that send a share of traffic to a new ranker
Apply diversity and business rules after ranking (for example, no more than two results from one seller)

Non-functional requirements

Ranking adds at most about 50 ms at p99 to a search (a budget we chose)
A model can be rolled out and rolled back without downtime
Features at serving time are computed the same way as in training
No change ships without an offline gate and an online experiment
If the main ranker fails, search still answers with a simpler order

Interview questions

Why two stages instead of one great model?
Define NDCG and explain why it suits search.
How does LambdaMART work?
How do you use clicks for training when users click whatever is on top?
Offline NDCG went up, but online metrics went down. Why?
How do you personalize ranking?
How do you roll out a new ranker safely?