Interleaving Tests

An interleaving test compares two rankers by blending their results for the same request into a single list, showing that list to the user, and crediting each click to the ranker that supplied the clicked item. The outcome for each request is a preference (the first ranker, the second, or a tie), not an absolute quality score.

In the description given by Hofmann et al. (2011), the interleaved list is generated for each query from the two rankers, the user’s clicks are attributed to each ranker according to how it ranked the clicked document, and the ranker that obtains more clicks is deemed superior.

How it differs from an A/B test

An A/B test assigns each user or request to one variant and compares the groups. In an interleaving test every impression contains results from both rankers, so the comparison is made within the same request and the same user. The price is that the test only applies when two ranked lists can be merged into one, and the only thing it reports is which ranker the credited clicks favored.

Chapelle, Joachims, Radlinski, and Yue studied interleaving on data from two commercial search engines and a scientific-literature retrieval system. According to the abstract of Chapelle et al. (2012), their analysis covered agreement with manual judgments and with observational implicit-feedback measures, statistical efficiency, a comparison of interleaving variants, and improved credit-assignment functions for clicks.

Three ways to build and credit the list

• Balanced interleaving alternates between the two lists and counts clicks in the top part of each list. It can favor one ranker even when clicks are random.
• Team draft interleaving lets the rankers take turns picking, records which ranker supplied each item, and credits a click only to its supplier.
• Probabilistic interleaving builds the list by sampling items from distributions derived from each ranking, which makes small ranking differences visible to the comparison.

What a result looks like

The per-request preferences are tallied. A simple option is to drop ties and apply a sign test to the remaining wins and losses, with the test and stopping rule fixed before the data arrive. Suppose, hypothetically, that 99 requests had a winner and the first ranker won 58 of them. A two-sided sign test gives p of about 0.11, which is not enough to call a winner. With ten times as many requests and the same proportion (580 wins, 410 losses), p is about 7×10⁻⁸. The proportion did not change; the amount of evidence did. Statistical Significance and Practical Significance separate whether an effect is detectable from whether it matters.

What the test cannot tell you

• It compares two rankers. It does not measure how good either one is on its own.
• It measures the signal whose clicks are credited. An effect that does not show up in those interactions is not measured.
• Clicks depend on position and presentation, so the credit rule must not favor a ranker for structural reasons. The balanced-interleaving entry works through a case where it does.
• The merged list is a product that users see, so the blend must be acceptable in its own right.

For the wider evaluation picture, Recommender Systems places online comparisons next to offline metrics, and A/B Testing and Experiment Design covers randomization units and interim decisions.

References:

• Hofmann, Whiteson, and de Rijke, A Probabilistic Method for Inferring Preferences from Clicks (CIKM 2011)
• Chapelle, Joachims, Radlinski, and Yue, Large-Scale Validation and Analysis of Interleaved Search Evaluation (ACM TOIS, 2012), abstract page