Interleaving as an Online Evaluation Method

Offline evaluation needs judgments, and judgments need someone to make them. Interleaving removes that requirement by running two rankers at the same moment, merging their results into a single list shown to a real user, and attributing whatever the user clicks to the ranker that contributed the clicked result. The comparison happens in the live system, on the queries users actually issue, with no assessor in the loop.

The method depends on a premise that off-line measures avoid: that clicks carry information about relevance. That premise is false in well-understood ways, and the design of interleaving is largely a set of repairs for those failures. What survives is a family of comparison methods that can detect small differences with far fewer observations than an A/B test, because it removes the variance caused by differences between users and queries.

Team draft: merging two lists by rotation

The simplest interleaving method is team draft, borrowed from the way teams are picked in a schoolyard. Take two rankings $A$ and $B$. Alternately pick a document for the merged list, choosing at each step from the ranking that has contributed fewer documents so far, and skipping documents already in the merged list.

The process has three properties that matter. Every document in the merged list comes from exactly one of the two systems, so the merged list can be partitioned into two contributions. The two contributions have sizes that differ by at most one, so neither system gets more exposure. And the merged ranking is a plausible search result in its own right, since the prefix of each contributing list is preserved in its relative order.

To decide the comparison, count clicks on documents contributed by $A$ and clicks on documents contributed by $B$, and compare the totals. If the two systems are equally good, the naming of which system is $A$ and which is $B$ is arbitrary, and a sound procedure randomises it per query. Randomisation converts a comparison into an unbiased test: under the null hypothesis that clicks do not depend on which system contributed a document, the expected difference is zero, and a paired test over queries becomes valid.

def team_draft(rank_a, rank_b, rng):
    """Return the merged list and a dict mapping docid -> 'A' or 'B'."""
    owner, merged = {}, []
    counts = {"A": 0, "B": 0}
    lists = {"A": list(rank_a), "B": list(rank_b)}
    # Randomise which team picks first so the trial stays unbiased.
    order = ["A", "B"] if rng.random() < 0.5 else ["B", "A"]
    while any(lists.values()):
        team = order[0] if counts[order[0]] <= counts[order[1]] else order[1]
        while lists[team]:
            doc = lists[team].pop(0)
            if doc not in owner:
                owner[doc] = team
                counts[team] += 1
                merged.append(doc)
                break
    return merged, owner

The inner loop skips documents already contributed by the other system, which is where the two lists intersect and where most of the interesting behaviour lies. A document that both systems rank highly is contributed by whichever system reached it first in the rotation, and its clicks are attributed accordingly. This is a source of bias: a shared document that both systems would rank first is attributed to the system that chose first, and the randomisation of first choice is what keeps that bias symmetric rather than removing it.

Balanced interleaving and credit assignment

Balanced interleaving replaces the rotation rule with a different fairness criterion. At each step, choose from the list whose next available document is ranked higher by its own system, and break ties randomly. The resulting merge has a property that team draft lacks: the relative order of the two systems’ prefixes is preserved in the merged list as nearly as possible.

The credit assignment problem remains. A click on a document contributed by $A$ is evidence that the document is relevant, but it is also evidence that the user found it because of where $A$ placed it. If $A$ placed it at rank 3 and $B$ placed it at rank 9, the merged list showed it at rank 3 or 4, and the click reflects the merged position rather than either system’s ranking. Both methods handle this the only way available: by making the assignment random across the two systems and aggregating over many queries, so that position effects cancel.

A related method, usually called probabilistic interleaving, abandons the deterministic merge. It draws the merged list from a distribution over rankings defined by the two systems, with the sampling probability tuned so that each system’s documents appear at the ranks they would occupy in that system’s own list. Clicks are then used with inverse probability weighting to estimate the difference in click-through at matched positions. The method needs more bookkeeping and yields an estimator with a known bias rather than an unknown one, which is the trade it makes.

Why click data is not relevance data

Interleaving’s validity rests on a click model, and the standard model has three named pathologies that every method must tolerate or correct.

Position bias. Users click higher results more often regardless of relevance. Interleaving does not remove this bias; it makes it symmetric, because both systems’ documents are subject to the same presentation effects in the merged list. Symmetry is enough for a comparison, since a constant bias cancels in the difference, but it is not enough to interpret the magnitude of the result. A click difference of a few percent says nothing about how much better one system is in any absolute sense.

Trust bias. The result shown at the top is clicked even when it is not relevant, because the user assumes it is. This bias interacts badly with merges that place one system’s documents consistently earlier. Randomising which system contributes the first position addresses it directly, which is why the randomisation in team draft is not a detail.

Presentation and snippet effects. A click depends on the snippet as well as the URL, and the snippet is generated by the system. A system with slightly better summarisation can win an interleaving comparison while returning the same documents, which is a legitimate outcome if the comparison is of the whole product and a false one if the comparison is of the ranking algorithm. The distinction has to be drawn before the experiment, not after.

Click data also records the absence of a click as weak evidence. A user who finds nothing useful may stop reading, and a user who finds nothing useful may reformulate immediately. Neither is distinguishable from a user who found what they wanted at rank 1 and left. Interleaving’s standard analysis handles this by conditioning on queries and comparing within them, so that a topic where nobody clicks at all contributes equally to both sides and cancels, but the tail of such queries inflates the variance and the effective sample size.

The efficiency argument and its limits

The reason interleaving is attractive is statistical, not philosophical. An A/B test compares two systems on disjoint user populations, so differences between users and between query populations contribute to the variance of the difference. An interleaving test compares two systems on the same query, in the same session, for the same user, and the between-query variance cancels exactly as it does in a paired offline test.

The gain in sensitivity is large enough to change the process. A difference too small to detect in an offline collection with a few dozen topics, or in an A/B test over a modest traffic share, can be detected in an interleaving experiment over a few thousand queries, because each query contributes a direct comparison rather than two independent measurements. The method also evaluates the deployed system on real query traffic rather than on authored topics, which addresses the topic-distribution bias discussed in How Many Topics a Benchmark Needs.

The limits are equally concrete. Interleaving requires a live system with users who click, so it cannot be used to choose between retrieval methods while the index is still being built. It requires an experiment framework that can merge two rankers’ output per request and log which contributed each result, which is a real engineering burden. It produces a significance verdict and a direction but, because of position and trust bias, not an interpretable effect size, so a team that must report “improvement of X percent” still needs an offline measure for the number. And it evaluates only the top positions users actually see, which for most interfaces means the first screen; a change that improves results at rank 30 is invisible to it.

The usual arrangement follows from these limits. Interleaving detects whether a change is better under live conditions; offline measures quantify how much and guard against regressions in regions the live experiment does not reach. Neither replaces the other, and a process that reports both answers questions that neither alone can address.