Re-ranking and diversity

Because the ranker scores items one at a time while the user sees the list as a whole, with the items interacting. Two items with a click probability of 0.20 give 0.36 if they are independent and only 0.20 if they are duplicates. And the original plus a less relevant item from another topic (0.12) gives 0.296 — a slate 48% better.

So «choose the best k items» and «assemble the best list of k items» are different problems, and the second does not reduce to the first by sorting.

By the goal, not the mechanism. In exploration we deviate from the greedy top in order to obtain data about what we have not been showing — we pay with present quality for the future quality of the model. In working with diversity we deviate for product reasons: a list of ten nearly identical products is bad here and now, regardless of what data we will collect.

The mechanism is similar, but the budgets and the metrics of success are different.

At three levels. Inside the output — intra-list diversity (the average dissimilarity of pairs) and the entropy of categories. Per user over a period — the share of categories new to them, serendipity. Across the system — coverage and Gini over impressions.

Entropy is more convenient than a simple count of categories because it also penalises a skew: the slates «8 + 1 + 1» and «4 + 3 + 3» both contain three categories, but the entropies are 0.639 against 1.089 — nearly double. And «8 + 1 + 1» is an output from one topic with two random specks.

Greedy selection with a penalty for similarity to what is already chosen: at every step we take \(\arg\max [\lambda\,\mathrm{rel}(u,i) - (1-\lambda)\max_{j\in S}\mathrm{sim}(i,j)]\). The penalty runs over the nearest item already chosen rather than the average: one duplicate in the slate poisons a candidate entirely.

The shape of the trade-off curve is typical: the first few percent of diversity are almost free (all three clusters are covered for 7.6% of relevance, and diversity grows from 0.32 to 0.82), after which the price rises sharply — the remaining 0.07 of diversity costs another 13 percentage points. Work at the knee.

Only by A/B. Offline metrics always vote for λ = 1: at that value the sum of relevance is maximal by definition, and so are NDCG and Recall@k. They evaluate an output as a set of independent items — the very assumption because of which the re-ranking layer was needed at all.

What has to be measured is product metrics: return rate, session length, the share of users interacting with more than one topic.

We define a distribution over subsets with \(P(S) \propto \det(L_S)\), where \(L = \mathrm{diag}(q)\,S\,\mathrm{diag}(q)\), and sample from it. The determinant of a Gram matrix is the squared volume of the parallelepiped on those vectors.

Collinear vectors (nearly identical items) give a volume of zero, and such a subset is never sampled at all. Orthogonal ones give the maximum. For two unit vectors det = sin²θ: 0 at 0°, 0.75 at 60°, 1 at 90°. And the lengths are responsible for relevance — the determinant grows as its square.

The advantage over MMR: one construction accounts for both relevance and diversity, with no manual λ balancing two terms of different natures. But it is rarely used in production — even approximate algorithms require the similarity matrix to be computed explicitly and decomposed, which does not fit the budget.

Because the usefulness of a slate is usually monotone and submodular: every next item adds no more than it would have added earlier — a formalisation of saturation. For such functions the greedy algorithm gives no worse than 1 − 1/e ≈ 0.632 of the optimum.

And that is not a consolation prize: enumerating a slate of 10 from 500 candidates is 2.5·10²⁰ options. At the real sizes of the problem, greediness is the only option that has any lower bound at all.

Yes, if the slate is built autoregressively: solving the problem as predicting the next item given those already chosen. Then the model learns for itself that after a pair of trainers it should not show four more — diversity comes out as a side effect of the formulation, with no manual λ.

The price: k sequential passes instead of one batch, because position k cannot be computed without choosing the previous ones — and that is exactly what the ranking budget cannot bear. Plus the model inherits its diversity from logs collected by a previous policy.