A/B Testing Search Changes

Ranking changes are usually small and users are enormously variable, so the standard split test spends weeks proving nothing. The fix is not more traffic. It is a design that removes the variance you do not care about.

Why the obvious test is insensitive

Split users into two groups, give each a different ranker, compare a metric. The problem is what the metric’s variance is made of. One user runs forty queries a week and clicks everything; another runs one and abandons. That between-user variability has nothing to do with which ranker they saw, and in a between-subjects design it lands entirely in the noise term.

It is worse for ranking changes specifically, because most ranking changes affect a minority of queries. If a new ranker only produces a different result set for one query in five, four fifths of your measured traffic is identical in both arms and contributes nothing but variance. You are averaging a real effect over a large mass of no-effect.

There is a partial fix that costs nothing and is routinely skipped: analyse only the traffic the change could have affected. Compute, for every query in both arms, whether the two rankers would have produced different top-k lists, and restrict the comparison to the queries where they differ. This is a legitimate analysis — the trigger condition depends on the query rather than on the outcome, so it does not bias the estimate — and on a change that touches one query in five it removes four fifths of the noise for free. It does change what the number means: you are now measuring the effect on affected queries, not on all traffic, and to get the headline number back you multiply by the trigger rate.

The choice of metric is the other half of the sensitivity problem, and the obvious candidate is a bad one. Click-through rate on the results page goes up when results improve and also when results get worse in a way that makes people click around to find out, so it cannot distinguish satisfaction from confusion. The metrics worth making primary describe the outcome of the session rather than the page: successful sessions as a share of searching sessions, time to first long dwell, reformulation rate, abandonment rate. All of them are noisier per observation than raw clicks and all of them measure something you would actually want to increase, which is the trade to make.

The variance arithmetic

Write down the variance of the estimated difference under both designs. Unpaired, with n observations per arm and equal variances:

Var( mean_A - mean_B ) = sigma^2 / n  +  sigma^2 / n  =  2 * sigma^2 / n

Paired — the same query, the same user, both rankers — the quantity you average is the per-unit difference d, and:

Var(d) = sigma_A^2 + sigma_B^2 - 2 * rho * sigma_A * sigma_B

with sigma_A = sigma_B = sigma:

Var(d) = 2 * sigma^2 * (1 - rho)

  rho  correlation between the two arms' outcomes on the same unit

The ratio of the two variances is exactly (1 - rho). Assume rho = 0.8 — plausible when both arms answer the same query for the same user, and a number you should estimate from your own data:

unpaired variance   2 * sigma^2 / n
paired variance     2 * sigma^2 * 0.2 / n   =  one fifth

Sample size scales with variance for fixed power, so the paired
design needs about 1/5 the observations for the same sensitivity.

That is the entire argument, and notice what it depends on: rho. The benefit is large when the two rankers behave similarly on the same unit and vanishes as rho goes to zero. A radical redesign that shares nothing with the incumbent gains little from pairing; a parameter change gains a great deal. Interleaving is a way of manufacturing a high rho by construction, because both rankers are answering the identical query in the identical session.

Chapelle, Joachims, Radlinski and Yue published the large-scale validation of this in 2012 (“Large-scale validation and analysis of interleaved search evaluation”, ACM TOIS), comparing interleaving against conventional A/B outcomes across many experiments on real search traffic. It is the paper to cite when somebody asks whether the sensitivity gain survives contact with production, and it is worth reading rather than having its numbers repeated at you.

Team-draft interleaving

The construction is due to Radlinski, Kurup and Joachims (2008) and it is named after playground team selection, which is exactly what it does. For one query, take ranking A and ranking B and build a single list by alternating picks, with the order of picking randomised each round:

interleaved = []
team_of     = {}                       # document -> A or B

while len(interleaved) < k:
    first = random.choice(["A", "B"])  # coin flip each round
    second = "B" if first == "A" else "A"

    for team in (first, second):
        d = next unselected document from that team's ranking
        if d is not already in interleaved:
            interleaved.append(d)
            team_of[d] = team

# scoring one impression
clicks_A = count of clicked documents whose team_of is A
clicks_B = count of clicked documents whose team_of is B
this impression favours A if clicks_A > clicks_B, B if fewer, tie otherwise

Two properties make it work. Credit assignment is unambiguous, because every document in the list belongs to exactly one team even when both rankers wanted it — whoever drafted it first owns it. And the coin flip per round removes the positional advantage of going first, which is the bug in naive interleaving schemes: without it, the ranker that contributes rank 1 more often wins on position bias alone.

Aggregate over impressions as a sign test on the per-impression preference. Ties — impressions where both teams got equal clicks, including zero — carry no information and are excluded, which is why the effective sample size is much smaller than the impression count and why you should track both numbers.

What interleaving cannot tell you

• Any absolute number. The output is “A is preferred to B”. It is not revenue, not sessions, not retention, and it cannot be converted into any of them. Interleaving is a fast filter for ranking candidates; the winner still goes to a conventional A/B test if the decision has a business number attached.
• Anything that is not a ranking change. Layout, snippet length, a new result type, an answer box — none of these can be interleaved, because the two experiences cannot be merged into one list. Those are ordinary A/B tests and they are stuck with ordinary sensitivity.
• Long-run effects. A single interleaved impression says nothing about whether users come back. Novelty and learning effects show up over weeks, which is a duration interleaving is not designed for.
• Whether your pipeline is trustworthy. Run an A/A test first — the same ranker on both teams — and confirm the result is a coin flip and the traffic split matches the intended ratio. A sample-ratio mismatch invalidates everything downstream, and it is the single most common reason a search experiment produces a confident wrong answer.

The healthy arrangement is a ladder. Offline metrics over judged queries filter out the obviously bad ideas for free; interleaving cheaply orders the survivors; a conventional A/B test measures the one you intend to ship against a number the business recognises. Skipping the middle rung is why most search teams run far fewer experiments than they think they should.