Interleaving Experiments for Ranking Changes

An A/B test on a ranking change needs a lot of traffic, because the two populations differ in every way except the ranking and that variance swamps the signal. Interleaving removes the population entirely: both rankings compete inside one result list, shown to the same user, and each click votes for whichever ranking contributed the clicked document. The result is a comparison that typically reaches significance with one to two orders of magnitude less traffic. This page implements it, and marks the cases where it is the wrong tool. It sits under relevance evaluation and offline testing in ranking algorithms and relevance tuning.

Prerequisites

  1. The ability to execute two ranking configurations for the same query within one request, with a latency budget that accommodates both.
  2. Impression and click logging keyed on a request identifier, with the interleaving assignment recorded alongside.
  3. A stable identity for consistent assignment, so a user does not see a differently blended list on every keystroke.
  4. Agreement that the comparison is about preference between two rankings, not about a business metric — interleaving answers only the first.

Diagnosis: why an A/B test struggles here

In a conventional A/B test, one population sees ranking A and another sees ranking B, and their behaviour is compared. The problem is that almost all the variance in click-through comes from who the users are and what they were looking for, not from the ranking difference. Detecting a small ranking improvement therefore requires enough users for those differences to average out, which for a modest ranking change can be weeks of traffic.

The arithmetic is stark on a mid-sized product:

A/B test, 2% relative CTR change, 80% power
  required sessions per arm ......... 412,000
  at 9,000 search sessions/day ...... 46 days per arm, run in parallel: 46 days

Interleaving, same effect size
  required impressions .............. 11,400
  at 9,000 sessions/day ............. under 2 days

The difference is not a modelling trick. It comes from the comparison being within a result list rather than between populations, which removes the dominant source of noise.

A/B testing compared with interleaving An A/B test splits users between two rankings and compares populations, while interleaving blends both rankings into one list shown to every user. A/B test users A → ranking A users B → ranking B compare populations variance dominates interleaving ranking A ranking B one blended list same user judges both the population difference is the noise; interleaving removes it entirely which is where the order-of-magnitude sensitivity gain comes from
Both designs compare two rankings. Only one of them asks the same person to judge both, which is why their traffic requirements differ so sharply.

Solution Steps

1. Blend the two rankings with team-draft

Team-draft alternates which ranking gets to pick the next slot, choosing the picking order randomly at each round so neither ranking systematically occupies better positions. Every document carries a record of which ranking contributed it.

# team_draft.py — fair blending with per-document credit
import random

def team_draft(a: list[str], b: list[str], k: int = 10):
    out, credit, used = [], {}, set()
    ia = ib = 0
    while len(out) < k and (ia < len(a) or ib < len(b)):
        pick_a = random.random() < 0.5          # fresh coin each round
        src, lst, idx = ("a", a, ia) if pick_a else ("b", b, ib)
        while idx < len(lst) and lst[idx] in used:
            idx += 1
        if idx >= len(lst):                     # that side is exhausted
            src, lst, idx = ("b", b, ib) if pick_a else ("a", a, ia)
            while idx < len(lst) and lst[idx] in used:
                idx += 1
            if idx >= len(lst):
                break
        doc = lst[idx]
        out.append(doc); used.add(doc); credit[doc] = src
        if src == "a": ia = idx + 1
        else:          ib = idx + 1
    return out, credit

2. Assign consistently within a session

A user who sees a differently blended list on every request is being asked to judge a moving target, and the clicks cannot be attributed cleanly. Seed the blending from a stable identity so the same query in the same session produces the same list.

# assign.py — deterministic blending per session and query
import hashlib

def seeded_random(session_id: str, query: str) -> random.Random:
    seed = int(hashlib.sha256(f"{session_id}:{query}".encode()).hexdigest()[:8], 16)
    return random.Random(seed)

3. Attribute clicks to the contributing ranking

The credit map from step 1 is the entire measurement apparatus. A click on a document credited to a is a vote for ranking A, regardless of the position it occupied.

# tally.py — one vote per impression, not per click
def score_impression(clicks: list[str], credit: dict[str, str]) -> str | None:
    a = sum(1 for c in clicks if credit.get(c) == "a")
    b = sum(1 for c in clicks if credit.get(c) == "b")
    if a == b:
        return None            # tie, including zero clicks: carries no information
    return "a" if a > b else "b"

4. Test significance with a sign test

Because each impression yields at most one vote, the analysis is a straightforward binomial test on the wins, which needs no assumptions about the click distribution.

# significance.py — two-sided sign test on impression-level wins
from math import comb

def p_value(wins_a: int, wins_b: int) -> float:
    n = wins_a + wins_b
    if n == 0:
        return 1.0
    k = max(wins_a, wins_b)
    tail = sum(comb(n, i) for i in range(k, n + 1)) / (2 ** n)
    return min(1.0, 2 * tail)

5. Stop on a pre-declared rule

Checking significance repeatedly and stopping when it first appears inflates the false-positive rate substantially. Declare the sample size or a sequential testing procedure before starting, and hold to it.

# stop.py — fixed-horizon rule declared up front
PLANNED_IMPRESSIONS = 12_000

def should_stop(n_impressions: int) -> bool:
    return n_impressions >= PLANNED_IMPRESSIONS     # no peeking-based early stop

Verification

Confirm the blend is fair — neither ranking should systematically get better positions:

python3 audit.py --field position_by_source
# ranking a: mean position 5.48  (n=61,204)
# ranking b: mean position 5.52  (n=60,918)
# => within noise; the draft is not favouring either side

Confirm attribution is working before trusting any result:

python3 audit.py --field credit_coverage
# clicks with a credited source: 99.7%
# => the 0.3% are documents that appeared in both rankings and were deduplicated

Confirm the outcome with its p-value:

python3 analyse.py --experiment ltr-v8-vs-v7
# impressions      12,041
# wins  a (v7)      2,884
# wins  b (v8)      3,301
# ties              5,856
# p-value           0.0000  -> v8 preferred

Reading the result honestly

An interleaving outcome is a preference, and preferences have magnitudes that the p-value does not convey. A statistically certain win in which ranking B takes 51% of the decided impressions is a real but tiny improvement; one at 62% is a substantial one. Report both the significance and the win rate, because the two answer different questions — whether the difference is real, and whether it is worth the complexity of the change that produced it.

It is also worth looking at where the wins came from. Segmenting the result by query length, by whether the query was navigational, or by result-set size frequently reveals that the aggregate win is concentrated in one segment and absent or reversed elsewhere. That is actionable in a way the headline number is not: a change that helps long descriptive queries and hurts short ones may be worth shipping conditionally rather than universally.

Win rate by query segment The aggregate win is concentrated in long descriptive queries, is neutral on medium ones and slightly negative on short navigational queries. 50% long queries 64% medium 52% short / navigational 46% The aggregate says "ship it"; the segments say "ship it for long queries".
Segmenting the result usually changes the decision from a binary ship-or-not into a conditional rollout, which is both safer and better.

Common Pitfalls

Peeking at significance and stopping early

Checking the p-value daily and stopping the first time it crosses 0.05 produces a false-positive rate far above 5%, because you have effectively run many tests. Either fix the sample size in advance, as in step 5, or use a sequential procedure designed for repeated looks. The temptation is strongest when the result is going the way you hoped, which is exactly when the discipline matters.

Interleaving rankings with very different latency

If ranking B takes 200 ms longer than A, every impression carries both costs and the blended list arrives late — which changes user behaviour independently of ranking quality. Interleaving compares orderings on the assumption that everything else is equal, and a large latency gap breaks that assumption. Compare latency first, and if it differs materially, fix that before running the experiment.

Reading an interleaving result as a business outcome

Interleaving answers one question precisely: which ordering do users prefer to click. It says nothing about revenue, conversion, or long-term engagement, and a ranking that wins on clicks can lose on all three — most obviously when it promotes cheaper items. Use interleaving to select a candidate quickly, then confirm the business outcome with a conventional canary as described in canary deploying relevance models.

Operational notes

The main operational cost is that every request in the experiment executes both rankings, which roughly doubles the search work for the traffic slice under test. On a small slice that is negligible; run interleaving across all traffic and it is a capacity decision. Because interleaving needs so little traffic to reach significance, a slice of a few per cent is almost always sufficient and keeps the cost invisible.

The second consideration is that interleaved results are, by construction, neither ranking. A user in the experiment sees a blend, which is usually fine — both inputs are plausible orderings — but it means an interleaving experiment is not a safe way to test a ranking you suspect might be bad. Screen candidates offline first so that both sides of the blend are known to be reasonable, and reserve interleaving for deciding between two credible options rather than for discovering whether one of them is broken.

Where interleaving sits between offline scoring and a canary Offline scoring screens candidates, interleaving picks between credible options quickly, and a canary confirms the business outcome. offline scoring screens out bad candidates interleaving picks between two good ones canary confirms the business outcome each stage answers a question the others cannot, and skipping the first makes the second unsafe
Interleaving is a selection tool, not a validation tool. It is fast precisely because it assumes both candidates are already plausible.