Probabilistic Interleaving
1. Definition
- Probabilistic Interleaving is an online evaluation method for comparing ranking algorithms.
- Unlike Balanced Interleaving (alternating picks) or Team Draft Interleaving (TDI) (draft pick style), Probabilistic Interleaving creates a single shared ranking list probabilistically, where the probability of choosing an item depends on how high it is ranked by each algorithm.
It’s designed to handle:
- More than two algorithms (not just A vs B).
- Overlapping results fairly (items appearing in multiple lists).
- Ambiguity in ownership with a probabilistic model.
2. Why It’s Used
- A/B Testing: Needs huge traffic, wastes users on worse variants.
- Balanced Interleaving: Can introduce bias if lists overlap.
- TDI: Works well for 2 algorithms but doesn’t scale easily.
- Probabilistic Interleaving: Flexible, scalable, and statistically principled.
3. How Probabilistic Interleaving Works
- Take ranking results from algorithms (say A, B, and C).
- Construct a probability distribution for each algorithm based on item rank:
- Items ranked higher → higher probability of being chosen.
- Example: Use a softmax over ranking positions.
- Sample items from these probability distributions to construct the interleaved list.
- Show the interleaved list to users.
- Attribute clicks probabilistically:
- Instead of each click belonging deterministically to one algorithm (like in TDI), attribution is shared according to probabilities.
- Compare expected credit across algorithms to see which performs better.
4. Example
Suppose two algorithms produce top-3 results:
- Algorithm A: [A1, A2, A3]
- Algorithm B: [B1, A2, B3]
Step 1 – Assign probabilities (higher rank → higher probability):
- A gives A1 more weight, B gives B1 more weight, both give A2 some weight.
Step 2 – Interleave list (probabilistically sampled):
- Possible combined list: [A1, B1, A2, B3, A3].
Step 3 – User clicks A2.
- In TDI: click goes fully to one algorithm (A or B, whichever drafted it).
- In Probabilistic Interleaving: click credit is shared probabilistically between A and B, because both ranked A2 highly.
5. Advantages
- Can handle more than 2 algorithms.
- Fair when rankings overlap heavily (shared items get shared credit).
- Statistically principled (reduces bias).
- Often more sensitive (detects small differences with fewer clicks).
6. Limitations
- More complex to implement and explain to stakeholders.
- Click attribution is probabilistic, not deterministic → harder to interpret directly.
- Requires careful design of the probability function (e.g., softmax temperature).
7. Comparison of Interleaving Methods
| Feature | Balanced Interleaving | Team Draft Interleaving (TDI) | Probabilistic Interleaving |
|---|---|---|---|
| Method | Alternate A/B items | Draft picks, randomized order | Sample based on rank probabilities |
| Bias | May favor one side if overlap | More fair, randomized | Very fair (shared attribution) |
| Algorithms supported | 2 only | 2 only | 2+ (scalable) |
| Attribution | Deterministic | Deterministic | Probabilistic |
| Complexity | Low | Medium | High |
| Sensitivity | Moderate | High | Very high |
In short:
Probabilistic Interleaving builds a shared ranking list by sampling items based on ranking probabilities from each algorithm. It attributes clicks probabilistically, making it fairer and scalable to multiple algorithms, though more complex to interpret than Balanced or TDI.