betaFeedback

WorksComputer Science

When Greedy Is Sorting: Exact and Certified Ideal Rankings for Novelty Metrics

Abstract

The ideal ranking that normalizes novelty metrics is NP-hard to compute in general, so widely used αα-nDCG evaluators approximate its denominator with a greedy rule that rescans every remaining document at each rank. We identify a regime in which this ideal ranking is exact and cheap for both αα-DCG and intent-aware expected reciprocal rank (ERR-IA). When each document is positively judged for at most one intent, each metric reduces to the classical allocation of a fixed budget across chains of decreasing marginal gains. A metric-specific virtual-score transformation followed by a multiway merge, which we call ChainMerge, returns the globally optimal top-KK ranking in O(G+Klog⁡G)O(G+K\log G) time from GG preordered intent groups, or in O(n+Klog⁡G)O(n+K\log G) time from nn globally preordered candidates, instead of the Θ(nK)Θ(nK) of the greedy rule. When intent judgments overlap, exact αα-DCG optimization is NP-hard under the standard logarithmic discount and α=0.5α=0.5, even when every document has three intents and every intent occurs in two documents. For arbitrary overlap, a polynomial-size LP over nested ranking prefixes upper-bounds the ideal score and certifies the optimality gap of any feasible ranking. In the official TREC Web 2009-2012 judgments, 64.8% of positive documents serve a single intent, yet only 20 of 198 complete queries do so throughout. Beyond this exact regime, the LP certifies 189 of the 198 greedy denominators as globally optimal, and the resulting score intervals preserve the winner in all eight matched comparison groups. On 65,238 MIND-small candidates, ChainMerge returns identical optimal objectives 17-1,011 times faster than the greedy rule. For αα-DCG, these results trace the hardness of the ideal ranking to intent overlap.

CCS CONCEPTS

• Information systems → Web searching and information discovery; Evaluation of retrieval results; • Theory of computation → Design and analysis of algorithms.

Introduction

Novelty-aware ranking is unusual in that evaluation itself contains a hard optimization problem. The numerator of α\alpha-nDCG is computed on a given list, but its ideal denominator maximizes a history-dependent gain over all rankings. Clarke et al. proved this ideal computation NP-hard 2 and Carterette later analyzed the resulting approximation problem in detail [7]. The reference NIST ndeval implementation therefore builds an ideal ranking by repeatedly taking the remaining document with the largest marginal gain, which rescans every unchosen candidate at each rank, and its source labels this construction a quadratic greedy approximation [30]. We call this procedure marginal greedy. pyndeval inherits the same routine, and ir_measures inherits it through pyndeval [23, 24]. Intent-aware expected reciprocal rank (ERR-IA) poses a parallel ideal-ranking problem under a cascade model, because a document’s contribution depends on earlier selections for the same intent.

This worst-case view hides a common structure that admits an exact solution. Many evaluation instances attach each candidate to one primary group. For example, MIND assigns every news article one category and one subcategory [32]. We define the row support of a document as the number of intents for which it has positive gain, that is, the number of nonzero entries in its row of the document–intent judgment matrix. An instance has row support one when every document has row support at most one. Marginal greedy still rescans every unchosen document after each selection, even though selecting from one group changes the gains of no other group. Within each group, the evolving gains form one diminishing sequence.

The metric structure turns this sequential computation into a static one. After the candidates of each intent group are ordered, the rr-th candidate of the group receives a metric-specific virtual score. For α\alpha-DCG it is the rr-th largest gain in the group multiplied by (1−α)r−1(1-\alpha)^{r-1}. For ERR-IA it is the intent prior times the rr-th satisfaction probability times the probability that all earlier members of the group fail to satisfy. Exchange arguments show that an optimum selects a prefix of each group and that the virtual scores decrease along that prefix. What remains is the classical allocation of a fixed budget across decreasing marginal returns, so merging the chains is feasible and globally optimal under every nonincreasing position discount. We call the resulting algorithm ChainMerge, and Figure 1 traces it on a small instance. Under row support one, ChainMerge

Figure 1. ChainMerge on eight graded documents with three intents and q=12q = \frac{1}{2}. (a) Each document is positive for one intent, so a stable partition of the globally ordered list yields one chain per intent, with its ngn_g members in gain order. (b) The rr-th member keeps the fraction qr−1q^{r-1} of its intrinsic gain (dashed), so every chain of virtual scores (solid) is nonincreasing. Halos mark the chain heads. (c) A max-heap over the chain heads emits the merged ranking, drawn on the scale of (b). It is optimal under every nonincreasing discount, and for positive discounts it is also the ranking that marginal greedy selects.

Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM ’27), February 15–19, 2027, Hong Kong, China. returns the exact α\alpha-IDCG denominator and a globally optimal ERR-IA top-KK ranking, replacing repeated full scans with an output-sensitive heap merge.

For α\alpha-DCG, row support one also sits on one side of a sparse complexity boundary. Under the evaluator’s standard settings, namely fixed α=0.5\alpha= 0.5, logarithmic discount, and binary judgments, exact optimization is NP-hard even when every document has exactly three intents and every intent occurs in exactly two documents. Tractability therefore holds at row support one and hardness at row support three, while row support two remains open. For arbitrary overlap, we bound the optimum instead of computing it. Rewriting the discounted objective as a nonnegative combination of prefix gains (Abel summation) and relaxing each intent’s coverage gain by its concave interpolation yields a polynomial-size LP, the prefix LP, whose value upper-bounds the exact optimum. Its gap above any feasible ranking is an instance-specific optimality certificate. Keeping one intent per document and bounding the deleted gains gives a second, solver-free certificate, the projection bound.

This paper makes four contributions.

  • We prove metric-specific prefix and virtual-score reductions showing that the ideal-ranking problems of row-support-one α\alpha-DCG and ERR-IA are both instances of classical decreasing-marginal allocation. ChainMerge is therefore globally optimal under arbitrary nonincreasing discounts.

  • For nn documents, GG intent groups, and cutoff KK, ChainMerge takes O(G+Klog⁡G)O(G+K\log G) time from materialized ordered chains and O(n+Klog⁡G)O(n+K\log G) time from a globally preordered list, compared with Θ(nK)\Theta(nK) for marginal greedy. In the binary case, group counts alone give the exact α\alpha-IDCG. An evaluator can check row support while reading judgments and switch to ChainMerge whenever it holds.

  • For overlapping α\alpha-DCG, we prove NP-hardness at row support three under fixed standard metric parameters. For arbitrary overlap, the prefix LP and the projection bound provide instance-specific optimality certificates.

  • Exhaustive enumeration and exact dynamic programming confirm the reductions and the certificates. In official TREC judgments, 64.8% of positive documents have row support one, and the LP certifies 189 of 198 complete-query greedy denominators as globally optimal. The resulting score intervals preserve the winner in all eight matched comparison groups. On MIND-small, ChainMerge is 17–1,011 times faster across the tested groupings and cutoffs while preserving the exact objective.

Background and Related Work

Metrics and ideal rankings. α\alpha-nDCG was introduced to reward nugget coverage while discounting redundant gain [12, 16]. ERR-IA instead averages a cascade satisfaction model over intent priors [8, 9, 12]. For general ERR-IA instances, Chapelle et al. proposed both greedy optimization and an exact branch-and-bound method [8]. Exact diversified ranking has also been formulated through integer programming for an implicit exemplar-based objective [36]. For the α\alpha-nDCG and ERR-IA denominators prescribed by the metrics, we identify a polynomial-time exact regime. When each document serves at most one intent, ERR-IA admits an intent-wise prefix reduction and a global chain merge, which replaces the permutation-tree search of branch and bound with an output-sensitive merge. The official TREC Web diversity tracks used NIST’s nddel implementation [11, 13, 14, 15, 30], and modern toolkit exposes the same metrics through its backend [23, 24]. Our work concerns the fixed ideal-ranking problem behind these evaluators.

Diversification and coverage. Sequential diversification makes a document’s utility depend on the results already selected. MMR balances query relevance against redundancy within the selected set [6], and subtopic retrieval formalized the resulting departure from independent relevance [37]. IA-Select and xQuAD later made intents explicit and scored marginal intent coverage [1, 27, 28]. Subsequent work developed scalable approximations and specialized objectives for large result pools [5], online methods combining cascade feedback, position bias, and submodular diversity [19], and ranking systems learned across queries by directly or differentially optimizing diversity objectives [10, 29, 33, 35, 39]. Ideal-ranking computation is the complementary fixed-instance problem, which optimizes a judged or predicted instance to obtain the metric denominator. The same coverage objectives now appear beyond web search. LANCER reranks RAG evidence for nugget coverage using α\alpha-nDCG [22], and systems based on query decomposition evaluate retrieval under the same metric [26].

Resource allocation. Classical discrete resource allocation assigns a fixed budget across activities with diminishing marginal returns. Marginal analysis for single-budget discrete allocation dates to Fox [18]. The greedy rule is optimal for separable concave objectives and extends to polymatroid constraints [17, 20]. This theory supplies the merge primitive in our algorithm. The new step is metric specific, namely showing that α\alpha-DCG and ERR-IA each generate one nonincreasing virtual-score chain per intent, with the ranking cutoff as the allocation budget and the virtual scores as its marginal returns. In particular, the ERR-IA reduction proves that an optimum selects a prefix of each intent’s satisfaction order despite the cascade survival products.

Hardness and certification. Beyond the general NP-hardness of ideal novelty ranking and its approximation analysis [7, 16], classical greedy approximation for monotone submodular set maximization concerns an unordered cardinality constraint [25]. Approximation algorithms and LP relaxations for ordered objectives include diversified search ranking [4], submodular cover-time ranking [3], and submodular ranking under prefix budgets [38]. Our hardness result fixes the standard logarithmic discount, α=0.5\alpha= 0.5, and binary judgments while restricting every document to three intents and every intent to two documents. Together with the exact row-support-one algorithm, this narrows the sparse tractability frontier, and row support two remains open. For arbitrary overlap, the prefix LP upper-bounds the ideal α\alpha-DCG denominator, so its gap above any feasible ranking is an instance-specific optimality certificate rather than a worst-case approximation ratio. The projection bound gives a further certificate without an LP solver.

Problem Setting

Let DD be a set of nn candidates, G={1,…,G}G = \{1, \ldots, G\} the intents, and K≤nK \le n the cutoff. Discounts satisfy d1≥⋯≥dK≥0d_1 \ge\cdots\ge d_K \ge0, and standard DCG uses dt=1/log⁡2(t+1)d_t = 1/\log_2(t + 1) [21]. A ranking π=(π1,…,πK)\pi= (\pi_1, \ldots, \pi_K) lists KK distinct documents. An instance has row support one when each candidate has positive gain for at most one intent. After dropping zero-gain candidates, row support one partitions the positive-gain set D+D_+ into groups CgC_g, one per intent. We replace (D,K)(D,K) by (D+,min⁡{K,∣D+∣})(D_+, \min\{K, |D_+|\}), because omitted zero-gain documents can fill any remaining ranks without changing the objective. Below, DD, n=∣D∣n = |D|, and KK refer to this reduced instance.

For i∈Cgi \in C_g, let ai≥0a_i \ge0 be its intrinsic gain, and set q=1−α∈[0,1]q = 1-\alpha\in[0,1], with the convention 00=10^0 = 1. The partitioned α\alpha-DCG objective is

Fα(π)=∑t=1KdtaπtqNg(πt)(t−1)(1)F_\alpha(\pi) = \sum_{t=1}^{K} d_t a_{\pi_t} q^{N_{g(\pi_t)}(t-1)} \tag*{(1)}

where Ng(t−1)=∣{s<t:g(πs)=g}∣N_g(t-1) = |\{s < t : g(\pi_s) = g\}| counts the earlier positions assigned to group gg. Binary TREC judgments use ai=1a_i = 1. In the graded convention used below, aia_i supplies the intrinsic utility, while the exponent counts preceding positive judgments for the intent.

For ERR-IA, group gg has prior pg≥0p_g \ge0, with ∑gpg=1\sum_g p_g = 1, and candidate i∈Cgi \in C_g has satisfaction probability si∈[0,1]s_i \in[0,1]:

FERR(π)=∑t=1Kdtpg(πt)sπt∏h<t:g(πh)=g(πt)(1−sπh).(2)F_{\mathrm{ERR}}(\pi) = \sum_{t=1}^{K} d_t p_{g(\pi_t)} s_{\pi_t} \prod_{\substack{h<t:\\g(\pi_h)=g(\pi_t)}} (1-s_{\pi_h}). \tag*{(2)}

Both objectives are history dependent, since the gain of a document depends on the earlier documents that share its intent. Section 4 removes this dependence under row support one, and Section 5 treats overlapping intents.

Chain Merging Is Exact under Row Support One

We first isolate the scheduling fact behind classical decreasing-marginal allocation, then reduce each metric to it.

Lemma 1 (Monotone-chain rearrangement). Suppose feasible items form predecessor chains, each with nonincreasing weights bg,1≥bg,2≥⋯≥0b_{g,1} \ge b_{g,2} \ge\cdots\ge0. For nonincreasing nonnegative discounts, sorting all items by bb, with ties respecting chain order, and taking the first KK maximizes ∑t≤Kdtbπt\sum_{t\le K} d_t b_{\pi_t}.

Proof. Without chain constraints, the rearrangement inequality pairs the KK largest weights with the largest discounts in non-increasing order. Because every chain is itself nonincreasing, this global order never places a successor before its predecessor. The unconstrained optimum is therefore feasible. □\square

-DCG

Within each group write ag,1≥⋯≥ag,nga_{g,1} \ge\cdots\ge a_{g,n_g} and define

bg,rα=ag,rqr−1.(3)b^\alpha_{g,r} = a_{g,r}q^{r-1}. \tag*{(3)}

Theorem 1 (Exact α\alpha-ChainMerge). For every α∈[0,1]\alpha\in[0,1], every nonincreasing nonnegative discount, and every cutoff, globally merging the chains bg,rαb^\alpha_{g,r} gives a global maximizer of (1).

Proof. Fix the positions t1<⋯<tmt_1 < \cdots< t_m occupied by group gg. Their coefficients dtrqr−1d_{t_r}q^{r-1} are nonnegative and decrease with rr. Rearrangement therefore transforms any selection without loss into the prefix ag,1,…,ag,ma_{g,1},\ldots,a_{g,m}, assigned in decreasing gain order. Hence a global maximizer exists with this prefix form. Once these within-group orders are fixed, each occurrence (g,r)(g,r) contributes dtbg,rαd_t b^\alpha_{g,r}, and

bg,r+1α=ag,r+1qr≤ag,rqr≤ag,rqr−1=bg,rα.b^\alpha_{g,r+1} = a_{g,r+1}q^r \le a_{g,r}q^r \le a_{g,r}q^{r-1} = b^\alpha_{g,r}.

This holds throughout q∈[0,1]q \in[0,1], including q=0q=0 under the convention 00=10^0 = 1. Thus each chain decreases and Lemma 1 applies. □\square

A worked instance. Figure 1 applies the theorem to eight graded documents, three intents, and q=12q = \frac{1}{2}. Each document is positive for one intent, so a single pass over the globally ordered list splits it into the chains C1C_1, C2C_2, C3C_3 (Fig. 1a). Within a chain, the rr-th member keeps only the fraction qr−1q^{r-1} of its intrinsic gain, because r−1r-1 earlier members already cover its intent. For example, document i4i_4 has gain 2.42.4 but virtual score 1.21.2 as the second member of C1C_1 (Fig. 1b). The chains are nonincreasing, and merging them gives the ranking in Fig. 1c, in which the three intents interleave as 3, 1, 2, 1, 2, 3, 1, 1.

Algorithm 1: ChainMerge for materialized, ordered chains
Input: chains bg,1≥⋯b_{g,1} \ge\cdots, cutoff KK
1 initialize a max-heap with (bg,1,g,1)(b_{g,1},g,1) for each nonempty group;
2 for t=1,…,Kt=1,\ldots,K do
3 pop maximum (bg,r,g,r)(b_{g,r},g,r), and output candidate (g,r)(g,r);
4 if r+1≤ngr+1 \le n_g then
5 push (bg,r+1,g,r+1)(b_{g,r+1},g,r+1);

Table 1.

Marginal greedy is exact under every tie-break. At rank tt, a remaining member i∈Cgi \in C_g adds dtaiqNg(t−1)d_t a_i q^{N_g(t-1)}, so all members of a group share the multiplier dtqNg(t−1)d_t q^{N_g(t-1)}. While the largest marginal gain is positive,3 the chosen group’s multiplier is positive, so greedy takes the largest remaining intrinsic gain of that group, and its addition is dtd_t times the group’s chain head. By induction, these selections form a prefix of a ChainMerge order, with ties among equal gains ordered consistently, and Lemma 1 makes every choice among tied heads optimal. Marginal greedy is thus exact under row support one for every tie-breaking rule, and its repeated scans are unnecessary. When ties are broken as in ChainMerge, the two procedures return the same ranking, which is the sense in which greedy is sorting.

Cost by input representation. Algorithm 1 stores only the head of every chain. If the within-group arrays are already materialized and ordered by intrinsic gain, the merge uses O(G+Klog⁡G)O(G+K\log G) time and O(G)O(G) extra memory.4 When the retrieval list is sorted by intrinsic gain, a stable partition, which appends each document to its group’s array in list order, materializes the arrays in O(n)O(n) time and gives an O(n+Klog⁡G)O(n+K\log G) path from scratch. Unsorted groups require O(nlog⁡n)O(n\log n) preprocessing. With binary judgments, every chain is the geometric sequence 1,q,q2,…1,q,q^2,\ldots truncated after ngn_g terms, so the merged scores, and hence the exact α\alpha-IDCG, depend only on the group counts ngn_g. These counts can be accumulated while judgments are read. Table 1 summarizes the cost of each input representation.

Method / inputTimeExtra space
Marginal greedyΘ(nK)\Theta(nK)O(n+G)O(n+G)
ChainMerge, unsortedO(nlog⁡n+Klog⁡G)O(n \log n + K \log G)O(n+G)O(n+G)
Global preordered listO(n+Klog⁡G)O(n + K \log G)O(n+G)O(n+G)
Materialized chainsO(G+Klog⁡G)O(G + K \log G)O(G)O(G)
Binary list, count-onlyO(n+G+Klog⁡G)O(n + G + K \log G)O(G)O(G)
Binary group countsO(G+Klog⁡G)O(G + K \log G)O(G)O(G)

Table 1. Worst-case time by input representation. Global-list paths include the stable partition or the counting pass, and materialized paths start from ordered group arrays or group counts.

ERR-IA

Within group gg, sort sg,1≥⋯≥sg,ngs_{g,1} \ge\cdots\ge s_{g,n_g} and define

bg,rERR=pg,sg,r∏h<r(1−sg,h).(4)b^{\mathrm{ERR}}_{g,r}=p_{g,s_g,r}\prod_{h<r}(1-s_{g,h}). \tag*{(4)}

When chain gg is ranked in this order, its virtual score is the prior-weighted probability that the rr-th member is the first document to satisfy intent gg, because the r−1r-1 members before it must all fail.

Theorem 2 (Exact ERR-IA ChainMerge). Merging the chains in Eq. (4) globally maximizes Eq. (2) for every nonincreasing nonnegative discount.

Proof. First fix the selected candidates of intent gg. Consider two consecutive occurrences of this intent in the ranking, at global positions t<t′t<t', with satisfaction probabilities xx and yy. Let P=pg∏k<t:gk=g(1−sgk)P=p_g\prod_{k<t:g_k=g}(1-s_{g_k}) be their prior-weighted prefix survival. No occurrence of gg lies between them. Placing xx before yy rather than yy before xx changes their combined contribution by P(x−y)(dt−dt′)P(x-y)(d_t-d_{t'}). Contributions of other intents are unchanged, and survival after both is the same. Eliminating adjacent inversions therefore orders the selected probabilities nonincreasingly within every intent.

It remains to establish prefix selection. Suppose an occurrence at global position tt has satisfaction ss and prior-weighted prefix survival PP. Let VV be the conditional expected discounted contribution from the future first satisfaction of this intent, given that the current occurrence does not satisfy. The contribution from the current occurrence and this suffix is P[sdt+(1−s)V]P[s d_t+(1-s)V]. Future first-satisfaction events have total probability at most one and occur at discounts no larger than dtd_t, so 0≤V≤dt0\le V\le d_t. Replacing ss by an unselected s′>ss'>s changes the objective by P(s′−s)(dt−V)≥0P(s'-s)(d_t-V)\ge0.

Repeated replacement, followed by the within-intent ordering above, transforms an optimum without loss into one that selects a prefix of each satisfaction order.

Finally, writing Qg,r=pg∏h<r(1−sg,h)≥0Q_{g,r}=p_g\prod_{h<r}(1-s_{g,h})\ge0,

bg,r+1ERR=Qg,rsg,r+1(1−sg,r)≤Qg,rsg,r=bg,rERR.b^{\mathrm{ERR}}_{g,r+1}=Q_{g,r}s_{g,r+1}(1-s_{g,r})\le Q_{g,r}s_{g,r}=b^{\mathrm{ERR}}_{g,r}.

Thus every virtual-score chain is nonincreasing, and Lemma 1 applies. □

The greedy argument given after Theorem 1 carries over with the group multiplier dtpg∏h<t:gh=g(1−sπh)d_t p_g\prod_{h<t:g_h=g}(1-s_{\pi_h}) in place of dtqNg(t−1)d_tq^{N_g(t-1)}, so marginal greedy is exact for ERR-IA under every tie-break as well. A count-based metric and a probabilistic cascade metric thus share the same chain structure, despite their different functional forms.

Hardness and Certificates under Intent Overlap

For an overlapping binary incidence matrix A∈{0,1}n×GA\in\{0,1\}^{n\times G} and intent weights wg≥0w_g\ge0, let Ngπ(t−1)=∑s<tAπsgN_g^\pi(t-1)=\sum_{s<t}A_{\pi_sg}. The objective in this section is

Fα(π)=∑t=1Kdt∑gAπtgwgqNgπ(t−1).(5)F_\alpha(\pi)=\sum_{t=1}^{K}d_t\sum_g A_{\pi_tg}w_gq^{N_g^\pi(t-1)}. \tag*{(5)}

It reduces to Eq. (1) under row support one, and the hardness result uses unit intent weights.

Hardness at row support three

(a) Hardness at row support three

Greedy fails with three documents

(b) Greedy fails with three documents

Prefix-LP coverage bound

(c) Prefix-LP coverage bound

Figure 2. Intent overlap breaks the chain structure. (a) In the reduction from Independent Set on cubic graphs, documents are vertices and intents are edges. A ranked independent set counts every touched intent once and reaches the cap 3∑tdt3\sum_t d_t, while ranking both endpoints of an edge loses α\alpha times the later discount. (b) With K=2K=2 and α=12\alpha=\frac{1}{2}, greedy ranks the heaviest document A first and ends 0.12 below the optimal ranking (B, C). Bar lengths are discounted contributions, darker for rank 1 and lighter for rank 2. (c) For one intent with wg=1w_g=1, q=12q=\frac{1}{2}, and mg=4m_g=4 covering documents, the prefix LP caps the coverage gain ugtu_{gt} by every tangent (dashed) of the concave interpolation of hgh_g. The cap equals hg(c)h_g(c) at integral coverage (filled) and interpolates at fractional coverage (hollow).

Hardness at standard parameters

When a document covers several intents, selecting it advances several chains at once, so neither static virtual scores nor Lemma 1 applies.

Theorem 3 (Sparse hardness at fixed standard parameters). For every fixed α∈(0,1]\alpha\in(0,1], exact binary α\alpha-DCG maximization with standard logarithmic discount is NP-hard, even when every document has exactly three intents and every intent occurs in exactly two documents.

Proof. Reduce from Independent Set on cubic graphs, which is NP-hard [2]. A vertex becomes a document and an edge becomes an intent, covered by its two endpoint documents. For a ranked vertex set SS of size KK, every vertex initially contributes three units. If both endpoints of edge ee are selected, its later endpoint contributes 1−α1-\alpha instead of one. Therefore the exact identity is

Fα(π)=3∑t=1Kdt−α∑e={u,v}∈E[S]dmax⁡{rank⁡π(u),rank⁡π(v)}.(6)F_\alpha(\pi) = 3\sum_{t=1}^{K} d_t-\alpha\sum_{e=\{u,v\}\in E[S]}d_{\max\{\operatorname{rank}_\pi(u),\operatorname{rank}_\pi(v)\}}. \tag*{(6)}

All discounts and α\alpha are positive, so the explicit cap 3∑tdt3\sum_t d_t is reached if and only if SS is independent. An exact ranking oracle therefore returns an independent KK-set exactly when one exists. Checking the returned set is combinatorial, so the reduction requires no arithmetic threshold comparison between logarithmic discounts. The construction has the stated 3-by-2 incidence.

Figure 2a shows the construction on the Petersen graph, which is cubic. Every intent touched by the ranked independent set is counted once, while ranking both endpoints of an edge forfeits α\alpha times the discount of the later endpoint. The exclusion of α=0\alpha=0 is necessary, because redundancy then disappears and the objective is modular. History dependence alone therefore does not make ideal novelty ranking hard. Hardness enters once documents cover several intents, already at row support three.

Greedy fails with three documents. Overlap also breaks the exactness of marginal greedy, and three documents suffice. With two documents and K=2K=2, strict failure is impossible. Let WW be the total weight of their shared intents and XX and YY the weights exclusive to each document. Greedy ranks first the document with the larger exclusive weight, say X≥YX \ge Y, and the two complete rankings differ by (d1−d2)(X−Y)≥0(d_1-d_2)(X-Y)\ge0 in its favor, because the shared contributions cancel. Figure 2b gives a three-document failure under the evaluator’s defaults α=0.5\alpha=0.5, d1=1d_1=1, and d2=1/log⁡23d_2=1/\log_2 3. Intents xx and yy have weight 1, intents zz and ww have weight 0.8, and the documents cover A = {x,y}\{x,y\}, B = {x,z}\{x,z\}, and C = {y,w}\{y,w\}. Greedy strictly prefers A, whose gain 2 exceeds 1.8. Every second choice then repeats x or y and adds only 1.3, so greedy attains 2+1.3d2≈2.8202+1.3d_2\approx2.820. The ranking (B, C) covers four intents once each and attains $1.8+1.8d_2\approx 2.936. Overlapping queries therefore need certificates rather than an exactness guarantee.5

Prefix-LP certificate

Because exact optimization is NP-hard under overlap, we instead bound the optimum with a polynomial-size LP. The cumulative novelty gain of a ranking prefix depends only on how many of its documents cover each intent, with diminishing returns for repeated coverage. Abel summation expresses the discounted score as a nonnegative combination of these prefix gains, and the LP bounds them jointly.

We first give (5) an exact prefix representation. We retain only intents covered by at least one document, so that mg=∣{i:Aig=1}∣≥1m_g = |\{i:A_{ig}=1\}|\ge1. Empty intents contribute nothing to the objective. Define the concave coverage function

hg(r)=wg∑j=0r−1qj,cg(S)=∑i∈SAig.(7)h_g(r)=w_g\sum_{j=0}^{r-1}q^j,\qquad c_g(S)=\sum_{i\in S}A_{ig}. \tag*{(7)}

For the ranking prefix St={π1,…,πt}S_t=\{\pi_1,\ldots,\pi_t\}, the cumulative novelty gain before position discount is exactly Γt=∑ghg(cg(St))\Gamma_t=\sum_g h_g(c_g(S_t)), because each intent contributes occurrence marginals wg,wgq,wgq2,…w_g,w_{gq},w_{gq^2},\ldots regardless of interleaving. Set dK+1=0d_{K+1}=0 and Δt=dt−dt+1≥0\Delta_t=d_t-d_{t+1}\ge0. Abel summation gives

Fα(π)=∑t=1Kdt(Γt−Γt−1)=∑t=1KΔtΓt.(8)F_\alpha(\pi)=\sum_{t=1}^{K}d_t(\Gamma_t-\Gamma_{t-1})=\sum_{t=1}^{K}\Delta_t\Gamma_t. \tag*{(8)}

Because every Δt\Delta_t is nonnegative, upper bounds on the prefix gains Γt\Gamma_t combine into an upper bound on the full objective. The LP below bounds all prefix gains jointly while keeping the prefixes nested.

Linearly interpolate hgh_g between its integer points. Its segment slopes are wgqrw_gq^r, so the interpolation is concave and its hypograph is the intersection of tangent halfspaces, drawn in Figure 2c. Introduce xitx_{it}, the fractional membership of document ii in the length-tt prefix, and ugtu_{gt}, which stands for the coverage gain of intent gg in that prefix. Write zgt(x)=∑iAigxitz_{gt}(x)=\sum_i A_{ig}x_{it}. The prefix LP is

ULP=max⁡∑t=1KΔt∑gugts.t.∑ixit=tt=1,…,K,0≤xi1≤⋯≤xiK≤1i∈D,0≤ugtg,t,ugt≤hg(r)+wgqr(zgt(x)−r)g,t, 0≤r<mg.(9)\begin{aligned} U_{\mathrm{LP}}&=\max&&\sum_{t=1}^{K}\Delta_t\sum_g u_{gt} \\ \text{s.t.}&&&\sum_i x_{it}=t &&t=1,\ldots,K,\\ &&&0\le x_{i1}\le\cdots\le x_{iK}\le1 &&i\in D,\\ &&&0\le u_{gt} &&g,t,\\ &&&u_{gt}\le h_g(r)+w_gq^r\left(z_{gt}(x)-r\right) &&g,t,\ 0\le r<m_g. \tag*{(9)} \end{aligned}

In this LP, Eq. (10) fixes the size of each prefix, and Eq. (11) keeps the prefixes nested, so a document that enters a prefix stays in every longer one. eq:13 caps the coverage gain of every intent by each tangent of its interpolation, and at an integral count zgt=cz_{gt}=c the tightest of these caps is exactly hg(c)h_g(c). The LP has O(nK+GK)O(nK+GK) variables and O(nK+K∑gmg)O(nK+K\sum_g m_g) constraints.6

Theorem 4 (Global α\alpha-DCG overlap certificate). For arbitrary binary overlap, every α∈[0,1]\alpha\in[0,1], and every nonincreasing nonnegative discount,

OPT⁡:=max⁡πFα(π)≤ULP.\operatorname{OPT}:=\max_{\pi}F_\alpha(\pi)\le U_{\mathrm{LP}}.

Thus any feasible ranking π^\hat{\pi} has the deterministic certificate

0≤OPT⁡−Fα(π^)≤ULP−Fα(π^).0\le\operatorname{OPT}-F_\alpha(\hat{\pi})\le U_{\mathrm{LP}}-F_\alpha(\hat{\pi}).

Proof. Embed any integral ranking by setting xit=I{i∈St}x_{it}=\mathbb{I}\{i\in S_t\}. Cardinality and nesting hold. At the integer count cg(St)c_g(S_t), set ugt=hg(cg(St))u_{gt}=h_g(c_g(S_t)). All tangent inequalities hold with the concave envelope, and Eq. (8) makes the LP objective exactly the ranking value. Every ranking is therefore LP-feasible, so the maximum LP value upper-bounds all of them. Subtract any feasible ranking value. □

The bound is tight whenever the LP has an optimum with xit∈{0,1}x_{it}\in\{0,1\}. Such nested prefixes define a ranking π\pi,7 and

ULP≤∑t=1KΔt∑ghg(zgt(x))=Fα(π)≤OPT⁡.U_{\mathrm{LP}}\le\sum_{t=1}^{K}\Delta_t\sum_g h_g(z_{gt}(x))=F_\alpha(\pi)\le\operatorname{OPT}.

A strict gap ULP>OPT⁡U_{\mathrm{LP}}>\operatorname{OPT} therefore requires fractional document memberships in every LP optimum, so that some document is split

across prefix positions and the interpolation credits coverage that no single ranking attains.

Proposition 1 (Graded overlap envelope). Suppose every incidence (i,g)(i,g) carries gain aig≥0a_{ig}\ge0, with count-based decay qq. Sort the gains incident to gg as ag,1≥ag,2≥⋯a_{g,1}\ge a_{g,2}\ge\cdots, and define

Hg(0)=0,Hg(r)=∑j=1rag,jqj−1(r≥1).H_g(0)=0,\qquad H_g(r)=\sum_{j=1}^{r}a_{g,j}q^{j-1}\quad(r\ge1).

Replacing Eq. (13) by the tangent constraints

ugt≤Hg(r)+ag,r+1qr(zgt(x)−r),0≤r<mg,(10)u_{gt}\le H_g(r)+a_{g,r+1}q^r\left(z_{gt}(x)-r\right),\qquad0\le r<m_g, \tag*{(10)}

gives an upper bound on the optimal graded count-decay objective. At an integral prefix, the envelope is exact when its selected gg-incidences are the largest available gains and occur in nonincreasing gain order.

Proof. If a prefix contains rr incidences for intent gg, rearrangement bounds its cumulative contribution by pairing the rr largest incident gains with 1,q,…,qr−11,q,\ldots,q^{r-1}, yielding Hg(r)H_g(r). The slopes ag,r+1qra_{g,r+1}q^r are nonincreasing, so the interpolation is concave and has the same tangent representation as Eq. (13). Abel summation combines the prefix bounds with nonnegative coefficients Δt\Delta_t, and the LP relaxation preserves the upper bound. The stated prefix condition attains the rearrangement bound. □

Projection bound without an LP solver. Write aig=wgAiga_{ig}=w_gA_{ig} in the binary case. For every positive document, choose one retained intent ϕ(i)∈{g:aig>0}\phi(i)\in\{g:a_{ig}>0\}, keep only that incidence, and solve the resulting row-support-one instance exactly. Let OPT⁡ϕ\operatorname{OPT}_{\phi} denote its ChainMerge optimum. For intent gg, let Rg={aig:aig>0, ϕ(i)≠g}R_g=\{a_{ig}:a_{ig}>0,\ \phi(i)\ne g\} be the multiset of deleted gains, sorted as rg,1≥rg,2≥⋯r_{g,1}\ge r_{g,2}\ge\cdots. Then

OPT⁡≤OPT⁡ϕ+∑g∑j=1min⁡{∣Rg∣,K}djrg,jqj−1.(11)\operatorname{OPT}\le\operatorname{OPT}_{\phi} +\sum_g\sum_{j=1}^{\min\{|R_g|,K\}}d_{j}r_{g,j}q^{j-1}. \tag*{(11)}

To see the bound, fix any ranking. Removing deleted incidences weakly reduces the preceding count for every retained incidence, so the retained contribution is no larger than the value of the same ranking in the projection and hence no larger than OPT⁡ϕ\operatorname{OPT}_{\phi}. Enumerate the ranked deleted incidences of intent gg in occurrence order. Its jj-th such incidence has global position at least jj and at least j−1j-1 preceding occurrences of gg, so its coefficient is at most djqj−1d_jq^{j-1}. The rearrangement inequality pairs these decreasing bounds with the largest deleted gains, yielding the residual term in Eq. (11). Summing over intents proves the claim. We call the right-hand side the projection bound. It requires no solver and holds for every choice of ϕ\phi, so minimizing it over ϕ\phi can only tighten the certificate.

Empirical Evaluation

We evaluate the exact and certified regimes through four research questions. RQ1 asks whether ChainMerge recovers the exact optimum, RQ2 how often row support one occurs in official data, RQ3 how tight the overlap certificates are, and RQ4 whether measured runtimes reflect the predicted complexity separation.

Implementation and Protocol

Existing evaluators. We examined the code of five evaluators, which are NIST ndeval, its pyndeval and PT-Ranking ports, ir_measures, and RankSys [23, 24, 30, 31, 34]. NIST’s reference routine builds the ideal ranking one position at a time by rescanning every unplaced document [30]. Its ports preserve this procedure, and ir_measures delegates diversity metrics to pyndeval [24]. None of them detects row support one or merges marginal chains.

Exact recovery. In each of three independent replicates, we generate 1,000 row-support-one α\alpha-DCG instances and 1,000 row-support-one ERR-IA instances. We draw nn uniformly from {3,…,8}\{3,\ldots,8\}, assign each item independently to one of at most four intents, and draw KK uniformly from {1,…,min⁡(5,n)}\{1,\ldots,\min(5,n)\}. For α\alpha-DCG, gains are uniform on [0.01,4][0.01,4] and α\alpha is uniform on [0,1][0,1]. For ERR-IA, satisfaction probabilities are uniform on [0.001,0.999][0.001,0.999], while intent weights are independent uniforms on [0.01,1][0.01,1] normalized to sum to one. We compare ChainMerge with exhaustive enumeration of every ordered top-KK list.

TREC Web diversity. We parse all 198 queries in the official 2009–2012 Web diversity qrels [11, 13, 14, 15]. We use the official binary subtopic judgments with α=0.5\alpha=0.5 and logarithmic discount dt=1/log⁡2(t+1)d_t=1/\log_2(t+1). The 178 queries containing at least one positive document assigned to multiple intents each contribute 50 pools of up to ten documents in each of the three replicates. Within each query, we cycle through its overlapping documents as mandatory anchors and sample up to nine remaining positive documents uniformly without replacement. The anchor places every pool outside the exact regime. At K=5K=5, exact subset DP provides the optimum for all 178×50×3=26,700178\times50\times3=26{,}700 pools. We compare this optimum with marginal greedy, the prefix LP, and the projection bound. We then apply the LP at K=min⁡(20,n)K=\min(20,n) to each complete positive-document pool. For small pools, let LL be the marginal-greedy value and UU the corresponding LP or projection upper bound.8 Because subset DP supplies the exact optimum, we report the certificate width as (U−L)/OPT(U-L)/\mathrm{OPT}. For complete queries, where the exact optimum is unavailable, we report the certified relative gap (U−L)/U(U-L)/U.

The 20 complete queries with row support one also provide a real-data ERR-IA test. With binary relevance, the standard ERR mapping (2rel−1)/2relmax(2^{\mathrm{rel}}-1)/2^{\mathrm{relmax}} gives satisfaction 0.5 for each positive judgment. We use uniform intent priors, reciprocal-rank discount, and K=min⁡(20,n)K=\min(20,n), and compare ChainMerge with marginal greedy over 200 repetitions per query.

Leaderboard robustness. We collect the published mean α\alpha-nDCG@20 of 124 official diversity runs and form eight comparison groups matched by year, collection category, and evaluated-topic count [11, 13, 14, 15]. Per-query run scores are not published, so we bound them conservatively. For query ℓ\ell, let LℓL_\ell be the evaluator’s greedy denominator and UℓU_\ell the prefix-LP upper bound. The exact denominator lies in [Lℓ,Uℓ][L_\ell,U_\ell], so replacing LℓL_\ell never raises a query score and lowers it by at most λℓ=Uℓ/Lℓ−1\lambda_\ell=U_\ell/L_\ell-1. A run with published mean σ\sigma over mm topics therefore has an exact-denominator mean in [σ−ϵ−λˉm,σ+ϵ][\sigma-\epsilon-\bar{\lambda}_m,\sigma+\epsilon], where ϵ\epsilon is half a unit in the last published decimal and λˉm\bar{\lambda}_m averages the mm largest λℓ\lambda_\ell of that year. An ordering of two runs counts as preserved when their intervals are disjoint, so every score consistent with the certificates keeps the published order. All calculations reproduce ndeval’s document-id tie-break.

Exact certificate arithmetic. We treat the evaluator’s stored IEEE-754 binary64 logarithmic discounts as exact dyadic rationals throughout subset DP, LP construction, scoring, and certificate comparisons. SoPlex 8.0.3 solves the LP in rational mode, and every returned solution is rechecked for exact feasibility. HiGHS supplies the numerical solver times reported below. For the projection bound, coordinate descent over the retained-intent assignment ϕ\phi minimizes the deleted-incidence term before the bound is evaluated exactly.

Runtime benchmarks. MIND-small assigns each news article one category and one subcategory [32]. Combining its train and development news tables gives 65,238 unique candidates, comprising 18 categories and 270 subcategories. We set item utility to 1+log⁡(1+training clicks)1+\log(1+\text{training clicks}), sort candidates once by utility, and use prefixes of 5,000, 10,000, 20,000, 30,000, 45,000, and 65,238 candidates with K∈{10,100,500}K\in\{10,100,500\}. For graded α\alpha-DCG with α=0.5\alpha=0.5, we compare marginal greedy, which scans every remaining candidate at each rank, with presorted ChainMerge, including its partition and heap construction. For binary gains, we additionally evaluate the count-only path, which computes exact IDCG from group counts accumulated while judgments are read.

For ERR-IA, we generate 65,238-candidate instances with either 18 or 270 intents. Candidate-group frequencies and intent priors are drawn independently from normalized lognormal weights, and satisfaction probabilities follow Beta(2,8)(2,8). Both methods receive the same instances and cutoffs. Runtime measurements use one CPU process and report the median of three repetitions. Input parsing, utility sorting, and retrieval are shared preprocessing and are excluded for both methods.

Results

RQ1: exact recovery. ChainMerge attains the exhaustive optimum on all 3,000 generated α\alpha-DCG instances and all 3,000 generated ERR-IA instances. On the 20 TREC queries with row support one, ChainMerge and marginal greedy also agree on every ERR-IA objective, and ChainMerge is 7.2 times faster on median.

RQ2: prevalence. Figure 3a shows that 64.8% of positive TREC documents have row support one, but only 20 of 198 complete queries satisfy the condition throughout. Document-level prevalence therefore does not carry over to queries. The exact path applies directly to these 20 queries, and the remaining queries require overlap certificates. In MIND, category and subcategory are each single-valued fields, so each induced judgment matrix has row support one globally.

Figure 3. Official TREC Web 2009–2012 diversity judgments. (a) Share of positive documents (light) and of complete queries (dark) with row support one. (b) Status of each complete query’s α\alpha-IDCG denominator at K=min⁡(20,n)K = \min(20,n). It is exact by ChainMerge, certified optimal by the prefix LP, or left with a positive certified gap. Labels give query counts, and Tables 2 and 3 list the exact values.

RQ3: overlap certificates. Small pools with exact optima. Across the 26,700 sampled overlapping pools, marginal greedy is strictly suboptimal on 168 instances (0.63%). The prefix LP is a valid upper bound in every instance and equals the exact subset-DP optimum on 26,692 (99.97%). In the eight remaining instances, its gap never exceeds 0.56%. The projection bound gives a zero-width certificate on 5,904 pools (22.1%), with a mean width of 7.4%.

Complete-query certificates. On the 198 complete TREC queries, the LP certifies 189 greedy denominators as globally optimal, including all 20 row-support-one queries and 169 overlapping queries (Figure 3b). Across all queries, the mean certified gap is 0.0213% and the maximum is 1.65%. The numerical LP solve takes 0.14 seconds per query at the median.

Leaderboard robustness. The resulting run-level intervals preserve the winner in all eight matched comparison groups and 1,069 of 1,074 strict pairwise orderings after accounting for published rounding. Replacing the greedy denominators with exact ones therefore cannot change any group winner on these tracks.

RQ4: runtime scaling. Over the six pool sizes in Figure 4a, the runtimes show the predicted separation between marginal greedy, whose cost grows with nKnK, and one partition followed by a small heap merge. Figure 4b shows how the full-pool speedup changes with KK. On the full MIND pool, graded ChainMerge is 17–1,011 times faster across the two groupings and three cutoffs while matching every marginal-greedy objective. The count-only path is 2,250–25,427 times faster than binary marginal greedy. On the MIND-sized ERR-IA instances, ChainMerge likewise matches every marginal-greedy objective and is 5–185 times faster across the six intent-count and cutoff settings. The speedup grows with the cutoff because marginal greedy rescans the whole pool at every rank, while ChainMerge pays for the pool only once.

Figure 4. Runtime on MIND-small, as medians of three runs. (a) Graded α\alpha-DCG with the subcategory grouping (G=270G = 270) at K=100K = 100 over six candidate-pool sizes. (b) Speedup on the full pool of 65,238 candidates, for graded ChainMerge over graded marginal greedy (solid) and for the count-only α\alpha-DCG path over binary marginal greedy (dashed). Squares mark the category grouping (G=18G = 18) and squares the subcategory grouping (G=270G = 270), as in (a). Table 4 lists the timings.

Applicability and Limitations

Use in evaluators. Row support can be checked as judgments are read. When row support one holds, ChainMerge returns the exact ideal denominator through the output-sensitive path. For an overlapping α\alpha-DCG query, an evaluator can instead pair its feasible ranking with the prefix-LP bound and report a certified upper bound on its optimality gap. Every reported α\alpha-DCG denominator can thus carry either an exactness guarantee or a certified gap.

Across the eight matched TREC comparison groups, these certified intervals preserve every winner and 99.5% of strict run pairs after published rounding.

Limits of the exact regime. The exact path requires row support one throughout a query, which held for only 20 of the 198 TREC queries. Forcing a multi-intent document into a single intent would change the objective rather than extend the exact regime, so the remaining queries depend on certificates.

Limits of certification. For overlapping α\alpha-DCG, the prefix LP upper-bounds the optimum and recovers an optimal ranking only when an optimal xx is integral. Equality with a feasible value proves global optimality, but when the certified gap is nonzero, the optimal ranking remains unresolved. The binary certificate extends to graded count-based decay through the envelope of Proposition 1, still as an upper bound rather than an exact algorithm. Overlapping ERR-IA is not covered by this certificate.

Open complexity boundary. For α\alpha-DCG, Theorems 1 and 3 establish tractability at row support one and hardness at row support three, even when each intent occurs twice. Row support two remains open, as does the complexity parameterized by the number of overlapping incidences or by the treewidth of the document–intent incidence graph.

Conclusion

Evaluators have approximated ideal novelty rankings with marginal greedy because computing them is NP-hard in general. For α\alpha-DCG, intent overlap, rather than history-dependent gain itself, separates the tractable cases from the hard ones. Under row support one, marginal greedy is exact for both metrics, and ChainMerge attains the same optimum by merging virtual-score chains instead of rescanning the pool. Under overlap, the prefix LP bounds the greedy α\alpha-DCG denominator without constructing an ideal ranking, certifying 189 of 198 official TREC denominators as optimal and leaving every matched group winner unchanged. Row support two and certification for overlapping ERR-IA remain open.

Ethical Considerations

This work develops algorithms for ranking-metric computation and conducts no user study or new data collection. The experiments use publicly released TREC judgments and MIND-small data. Click counts are used only to construct runtime workloads and support no behavioral or fairness conclusions.

A Detailed Results

This appendix lists the values plotted in Figure 3 and Figure 4. Table 2 gives the row-support structure of the official TREC judgments, Table 3 the per-year prefix-LP certificates with their gaps and solve times, and Table 4 the full-pool MIND-small timings behind Figure 4b. The certified gaps stay small in every year. The largest mean gap, 0.078%, occurs in 2009, the year with the most open queries.

YearQueriesPositive documents
TotalRow support oneTotalRow support one
20095012 (24.0%)4,9423,622 (73.3%)
2010483 (6.3%)6,5534,862 (74.2%)
2011502 (4.0%)5,0302,707 (53.8%)
2012503 (6.0%)5,5593,111 (56.0%)
Total19820 (10.1%)22,08414,302 (64.8%)

Table 2. Structure of positive TREC Web diversity judgments.

YearQueriesCertifiedMean gapMedian sec.
200950460.0783%0.084
201048450.0001%0.161
201150490.0060%0.132
201250490.0002%0.189
Total1981890.0213%0.137

Table 3. Complete-query prefix-LP certificates at K=min⁡(20,n)K = \min(20,n). Gaps are relative to the LP upper bound. Certificate decisions use exact rational arithmetic, and times are numerical HiGHS medians.

(a) Graded α\alpha-DCG, α=0.5\alpha= 0.5
FieldGGKKMarginal greedyChainMergeSpeedup
Category1810136.47.4118.4
Category181001,550.58.04192.8
Category185008,098.38.011,010.9
Subcategory27010127.97.5417.0
Subcategory2701001,326.98.09164.0
Subcategory2705007,191.57.84917.1
(b) Binary α\alpha-IDCG from group counts, α=0.5\alpha= 0.5
FieldGGKKMarginal greedyCount-onlySpeedup
Category1810134.40.010213,120
Category181001,520.00.066422,907
Category185007,989.50.31425,427
Subcategory27010134.20.05972,250
Subcategory2701001,339.40.12011,161
Subcategory2705006,682.80.41116,250

Table 4. Full-pool MIND-small runtime (65,238 candidates), in milliseconds. Panel (a) includes partition and heap construction, and panel (b) receives counts accumulated during input. Values are medians of three runs, and speedups use unrounded times.

Acknowledgments

The authors used AI tools to assist with manuscript preparation and code development. All AI-generated content was reviewed and verified by the authors, who take full responsibility for this work.

References

  1. [1]Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Leong. 2009. Diversifying Search Results. In Proceedings of WSDM. 5–14. doi:10.1145/1498759.1498766DOI
  2. [2]Paola Alimonti and Viggo Kann. 2000. Some APX-Completeness Results for Cubic Graphs. Theoretical Computer Science 237, 1–2 (2000), 123–134. doi:10.1016/S0304-3975(98)00158-3DOI
  3. [3]Yossi Azar and Iftah Gamzu. 2011. Ranking with Submodular Valuations. In Proceedings of SODA. 1070–1079. doi:10.1137/1.9781611973082.81DOI
  4. [4]Nikhil Bansal, Kamal Jain, Anna Kazeykina, and Joseph Naor. 2010. Approximation Algorithms for Diversified Search Ranking. In Proceedings of ICALP (Lecture Notes in Computer Science, Vol. 6198). 273–284. doi:10.1007/978-3-642-14162-1_23
  5. [5]Gabriele Capannini, Franco Maria Nardini, Raffaele Perego, and Fabrizio Silvestri. 2011. Efficient Diversification of Web Search Results. Proceedings of the VLDB Endowment 4, 7 (2011), 451–459. doi:10.14778/1988776.1988781DOI
  6. [6]Jaime G. Carbonell and Jade Goldstein. 1998. The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries. In Proceedings of SIGIR. 335–336. doi:10.1145/290941.291025DOI
  7. [7]Ben Carterette. 2011. An Analysis of NP-Completeness in Novelty and Diversity Ranking. Information Retrieval 14, 1 (2011), 89–106. doi:10.1007/s10791-010-9157-1
  8. [8]Olivier Chapelle, Shihhao Ji, Ciya Liao, Emre Velipasaoglu, Larry Lai, and Sun Lin Wu. 2011. Intent-Based Diversification of Web Search Results: Metrics and Algorithms. Information Retrieval 14, 6 (2011), 572–592. doi:10.1007/s10791-011-9167-7DOI
  9. [9]Olivier Chapelle, Donald Metzler, Ya Zhang, and Pierre Grinspan. 2009. Expected Reciprocal Rank for Graded Relevance. In Proceedings of CIKM. 621–630. doi:10.1145/1645953.1646033DOI
  10. [10]Yiqun Chen, Jiaxin Miao, Yi Zhang, Dehong Ma, Long Xia, Jun Fan, Daiting Shi, Zhichong Cheng, Simiu Gu, and Dawei Yin. 2025. MA4DIV: Multi-Agent Reinforcement Learning for Search Result Diversification. In Proceedings of the ACM on Web Conference 2025. 1703–1715. doi:10.1145/3696410.3714862DOI
  11. [11]Charles L. A. Clarke, Nick Craswell, and Ian Soboroff. 2009. Overview of the TREC 2009 Web Track. In Proceedings of TREC (NIST Special Publication, Vol. 500-278). National Institute of Standards and Technology. https://trec.nist.gov/pubs/trec18/papers/WEB09.OVERVIEW.pdf
  12. [12]Charles L. A. Clarke, Nick Craswell, Ian Soboroff, and Azin Ashkan. 2011. A Comparative Analysis of Cascade Measures for Novelty and Diversity. In Proceedings of WSDM. 75–84. doi:10.1145/1935826.1935847DOI
  13. [13]Charles L. A. Clarke, Nick Craswell, Ian Soboroff, and Gordon V. Cormack. 2010. Overview of the TREC 2010 Web Track. In Proceedings of TREC (NIST Special Publication, Vol. 500-294). National Institute of Standards and Technology. https://trec.nist.gov/pubs/trec19/papers/WEB.OVERVIEW.pdf
  14. [14]Charles L. A. Clarke, Nick Craswell, Ian Soboroff, and Ellen M. Voorhees. 2011. Overview of the TREC 2011 Web Track. In Proceedings of TREC (NIST Special Publication, Vol. 500-296). National Institute of Standards and Technology. doi:10.6028/NIST.SP.500-296.web-overview
  15. [15]Charles L. A. Clarke, Nick Craswell, and Ellen M. Voorhees. 2012. Overview of the TREC 2012 Web Track. In Proceedings of TREC (NIST Special Publication, Vol. 500-298). National Institute of Standards and Technology. doi:10.6028/NIST.SP.500-298.web-overview
  16. [16]Charles L. A. Clarke, Maheedhar Kolla, Gordon V. Cormack, Olga Vechtomova, Azin Ashkan, Stefan Büttcher, and Ian MacKinnon. 2008. Novelty and Diversity in Information Retrieval Evaluation. In Proceedings of SIGIR. 659–666. doi:10.1145/1390334.1390446
  17. [17]Awi Federgruen and Henri Groenevelt. 1986. The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality. Operations Research 34, 6 (1986), 909–918. doi:10.1287/opre.34.6.909
  18. [18]Bennett Fox. 1966. Discrete Optimization Via Marginal Analysis. Management Science 13, 3 (1966), 210–216. doi:10.1287/mnsc.13.3.210DOI
  19. [19]Gaurush Haridannani, Craig Macdonald, and Iadh Ounis. 2020. Cascading Linear Submodular Bandits: Accounting for Position Bias and Diversity in Online Learning to Rank. In Proceedings of UAI (Proceedings of Machine Learning Research, Vol. 115). 722–732.
  20. [20]Toshihide Ibaraki and Naoki Katoh. 1988. Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, MA.DOI
  21. [21]Kalervo Järvelin and Jaana Kekäläinen. 2002. Cumulated Gain-Based Evaluation of IR Techniques. ACM Transactions on Information Systems 20, 4 (2002), 422–446. doi:10.1145/582415.582418DOI
  22. [22]Jia-Huei Ju, François C. Landry, Eugene Yang, Suzan Verberne, and Andrew Yates. 2026. LancerLL: LLM Reranking for Nugget Coverage. arXiv preprint arXiv:2601.22008 (2026).
  23. [23]Sean MacAvaney. 2021. pyndeval: Python Bindings for pndeval. https://github.com/seanmacavaney/pyndeval.
  24. [24]Sean MacAvaney, Craig Macdonald, and Iadh Ounis. 2022. Streamlining Evaluation with ir-measures. In Advances in Information Retrieval (Lecture Notes in Computer Science, Vol. 13186). Springer, 305–310. doi:10.1007/978-3-030-99739-7_38DOI
  25. [25]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978. An Analysis of Approximations for Maximizing Submodular Set Functions—I. Mathematical Programming 14, 1 (1978), 265–294. doi:10.1007/BF01588971DOI
  26. [26]Roxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten de Rijke, Dawn Lawrie, and Kevin Duh. 2026. Query Decomposition for RAG: Balancing Exploration–Exploitation. In Proceedings of EACL. 6857–6871. doi:10.18653/v1/2026.eacl-long.322DOI
  27. [27]Rodrygo L. T. Santos, Craig Macdonald, and Iadh Ounis. 2010. Exploiting Query Reformulations for Web Search Result Diversification. In Proceedings of WWW. 881–890. doi:10.1145/1772690.1772780DOI
  28. [28]Rodrygo L. T. Santos, Craig Macdonald, and Iadh Ounis. 2015. Search Result Diversification. Foundations and Trends in Information Retrieval 9, 1 (2015), 1–90. doi:10.1561/1500000040DOI
  29. [29]Sonali Singh, Sachin Sudhakar Farfade, and Prakash Mandayam Comar. 2024. DiAL: Diversity Aware Listwise Ranking for Query Auto-Complete. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track. Association for Computational Linguistics, 1152–1162. doi:10.18653/v1/2024.emnlp-industry.87DOI
  30. [30]U.S. National Institute of Standards and Technology. 2010. ndeval.c, Version 4.4. https://trec.nist.gov/data/web/10/ndeval.c. Accessed 2026-08-14.
  31. [31]Saúl Vargas. 2015. RankSys: A Java Framework for Recommender Systems. https://ranksys.github.io/. Accessed 2026-08-25.
  32. [32]Fangzhao Wu, Ying Qiao, Jinshu Chen, Chuhan Wu, Tao Qi, Jianxun Lian, Danyang Liu, Xing Xie, Jianfeng Gao, Winnie Wu, and Ming Zhou. 2020. MIND: A Large-Scale Dataset for News Recommendation. In Proceedings of ACL. 3597–3606. doi:10.18653/v1/2020.acl-main.331
  33. [33]Jun Xu, Long Xia, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2017. Directly Optimize Diversity Evaluation Measures: A New Approach to Search Result Diversification. ACM Transactions on Intelligent Systems and Technology 8, 3, Article 41 (2017), 26 pages. doi:10.1145/2983921DOI
  34. [34]Hai-Tao Yu. 2020. P&T-Ranking: A Benchmarking Platform for Neural Learning-to-Rank. arXiv preprint arXiv:2008.13368 (2020).arxiv.org/abs/2008.13368
  35. [35]Hai-Tao Yu. 2022. Optimize What You Evaluate With: Search Result Diversification Based on Metric Optimization. In Proceedings of AAAI, Vol. 36. 10399–10407. doi:10.1609/aaai.v36i9.21282DOI
  36. [36]Hai-Tao Yu, Adam Jatowt, Roi Blanco, Hideo Joho, Joemon M. Jose, Long Chen, and Fajie Yuan. 2017. A Concise Integer Linear Programming Formulation for Implicit Search Result Diversification. In Proceedings of WSDM. 191–200. doi:10.1145/3018661.3018710DOI
  37. [37]ChengXiang Zhai, William W. Cohen, and John D. Lafferty. 2003. Beyond Independent Relevance: Methods and Evaluation Metrics for Subtopic Retrieval. In Proceedings of SIGIR. 10–17. doi:10.1145/860435.860440DOI
  38. [38]Guangyi Zhang, Nikolaj Tatti, and Aristides Gionis. 2022. Ranking with Submodular Functions on a Budget. Data Mining and Knowledge Discovery 36, 3 (2022), 1197–1218. doi:10.1007/s10618-022-00833-4DOI
  39. [39]Yadong Zhu, Yanyan Lan, Jafeng Guo, and Xueqi Cheng. 2015. Structural Learning of Diverse Ranking. arXiv preprint arXiv:1504.04596 (2015).DOI

Paper details

vlnc:W_jktfx6a7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI tools

View statement
Looking for related papers…
Contents