Interleaving and Online Evaluation

An A/B test on a search ranker splits users into two groups and compares aggregate metrics. Most of the variance in those metrics comes from differences between users and between queries, not from the ranker, so the experiment spends its traffic measuring noise. Interleaving removes that variance by making the comparison within a single result list.

Both rankers produce a ranking for the same query, the two are merged into one list shown to the user, and the clicks are attributed back to whichever ranker contributed each clicked result. Every impression becomes a paired comparison.

Team draft, and why the merging rule matters

The naive merge, alternating results, has a defect: it introduces a position advantage for whichever ranker goes first. Team-draft interleaving borrows the playground procedure. Flip a coin to decide who picks first, each ranker in turn contributes its highest-ranked result not already in the list, and the coin is flipped again at each round. The randomised order removes the systematic position advantage, and a click on a document contributed by ranker A counts as a win for A.

Chapelle and colleagues validated interleaving at scale against absolute online metrics and against offline judgments, finding it agrees with the ground truth substantially more reliably per unit of traffic (Chapelle, Joachims, Radlinski and Yue, 2012, Large-Scale Validation and Analysis of Interleaved Search Evaluation, ACM TOIS 30(1)). The reported sensitivity advantage over conventional A/B metrics is large, typically expressed as needing one to two orders of magnitude less traffic to reach the same confidence, which is what makes it standard practice at search companies.

Probabilistic interleaving extends the family by sampling from softmax distributions over both rankings instead of a strict draft, which makes it compatible with importance weighting and so allows the logs to be reused for off-policy comparison of rankers that were never deployed.

What it does and does not measure

Interleaving answers one question well: which of these two rankers do users prefer, holding query and user constant. It does not measure absolute metrics. It cannot tell you the new ranker's click-through rate, its effect on sessions per user, its revenue impact, or whether the improvement is worth the latency it costs. Nothing about a preference signal converts into a business quantity.

The standard architecture reflects this. Interleaving is the fast filter, running many candidate rankers cheaply to find the ones users prefer; an A/B test then measures the winner's effect on the metrics a decision actually needs. Using either alone is a mistake, and using interleaving as the launch criterion is the more common one.

When it breaks

The results must be mixable. Interleaving assumes the merged list is a coherent thing to show. Rankers that differ in presentation, that return different result types, or whose value comes from the composition of the whole page rather than the ordering of items cannot be interleaved meaningfully.

Clicks remain the signal, with all their problems. A click is not satisfaction, and interleaving inherits every click-bias issue. Team draft handles the relative position advantage between the two rankers; it does not make clicks a measure of quality.

Ties and overlap dilute the comparison. When two rankers agree on most results, most clicks land on documents both contributed, giving no signal. Sensitivity comes from disagreement, so interleaving is efficient for genuinely different rankers and slow for small variations, which is the opposite of most people's intuition.

Whole-page and long-term effects are invisible. An interleaved list is not the page either ranker would have produced, so page-level effects are unmeasurable. Anything that accumulates over sessions, learning, trust, habit formation, is outside the method entirely.

It compares two things. Extending to many rankers is possible and the statistics get harder, and the pairwise preferences need not be transitive. A ranking of rankers is not simply read off from pairwise interleaving results.