In this paper
AbstractCCS CONCEPTSIntroductionBackground and Related WorkProblem SettingChain Merging Is Exact under Row Support One-DCGERR-IAHardness and Certificates under Intent OverlapHardness at standard parametersPrefix-LP certificateEmpirical EvaluationImplementation and ProtocolResultsApplicability and LimitationsConclusionEthical ConsiderationsA Detailed ResultsAcknowledgmentsReferencesWorksComputer 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- ranking in time from preordered intent groups, or in time from globally preordered candidates, instead of the of the greedy rule. When intent judgments overlap, exact -DCG optimization is NP-hard under the standard logarithmic discount and , 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 -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 -th candidate of the group receives a metric-specific virtual score. For -DCG it is the -th largest gain in the group multiplied by . For ERR-IA it is the intent prior times the -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 . (a) Each document is positive for one intent, so a stable partition of the globally ordered list yields one chain per intent, with its members in gain order. (b) The -th member keeps the fraction 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 -IDCG denominator and a globally optimal ERR-IA top- ranking, replacing repeated full scans with an output-sensitive heap merge.
For -DCG, row support one also sits on one side of a sparse complexity boundary. Under the evaluator’s standard settings, namely fixed , 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 -DCG and ERR-IA are both instances of classical decreasing-marginal allocation. ChainMerge is therefore globally optimal under arbitrary nonincreasing discounts.
For documents, intent groups, and cutoff , ChainMerge takes time from materialized ordered chains and time from a globally preordered list, compared with for marginal greedy. In the binary case, group counts alone give the exact -IDCG. An evaluator can check row support while reading judgments and switch to ChainMerge whenever it holds.
For overlapping -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. -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 -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 -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 -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, , 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 -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 be a set of candidates, the intents, and the cutoff. Discounts satisfy , and standard DCG uses [21]. A ranking lists 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 into groups , one per intent. We replace by , because omitted zero-gain documents can fill any remaining ranks without changing the objective. Below, , , and refer to this reduced instance.
For , let be its intrinsic gain, and set , with the convention . The partitioned -DCG objective is
where counts the earlier positions assigned to group . Binary TREC judgments use . In the graded convention used below, supplies the intrinsic utility, while the exponent counts preceding positive judgments for the intent.
For ERR-IA, group has prior , with , and candidate has satisfaction probability :
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 . For nonincreasing nonnegative discounts, sorting all items by , with ties respecting chain order, and taking the first maximizes .
Proof. Without chain constraints, the rearrangement inequality pairs the 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.
-DCG
Within each group write and define
Theorem 1 (Exact -ChainMerge). For every , every nonincreasing nonnegative discount, and every cutoff, globally merging the chains gives a global maximizer of (1).
Proof. Fix the positions occupied by group . Their coefficients are nonnegative and decrease with . Rearrangement therefore transforms any selection without loss into the prefix , assigned in decreasing gain order. Hence a global maximizer exists with this prefix form. Once these within-group orders are fixed, each occurrence contributes , and
This holds throughout , including under the convention . Thus each chain decreases and Lemma 1 applies.
A worked instance. Figure 1 applies the theorem to eight graded documents, three intents, and . Each document is positive for one intent, so a single pass over the globally ordered list splits it into the chains , , (Fig. 1a). Within a chain, the -th member keeps only the fraction of its intrinsic gain, because earlier members already cover its intent. For example, document has gain but virtual score as the second member of (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 , cutoff |
| 1 initialize a max-heap with for each nonempty group; |
| 2 for do |
| 3 pop maximum , and output candidate ; |
| 4 if then |
| 5 push ; |
Table 1.
Marginal greedy is exact under every tie-break. At rank , a remaining member adds , so all members of a group share the multiplier . 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 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 time and 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 time and gives an path from scratch. Unsorted groups require preprocessing. With binary judgments, every chain is the geometric sequence truncated after terms, so the merged scores, and hence the exact -IDCG, depend only on the group counts . These counts can be accumulated while judgments are read. Table 1 summarizes the cost of each input representation.
| Method / input | Time | Extra space |
| Marginal greedy | ||
| ChainMerge, unsorted | ||
| Global preordered list | ||
| Materialized chains | ||
| Binary list, count-only | ||
| Binary group counts |
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 , sort and define
When chain is ranked in this order, its virtual score is the prior-weighted probability that the -th member is the first document to satisfy intent , because the 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 . Consider two consecutive occurrences of this intent in the ranking, at global positions , with satisfaction probabilities and . Let be their prior-weighted prefix survival. No occurrence of lies between them. Placing before rather than before changes their combined contribution by . 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 has satisfaction and prior-weighted prefix survival . Let 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 . Future first-satisfaction events have total probability at most one and occur at discounts no larger than , so . Replacing by an unselected changes the objective by .
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 ,
Thus every virtual-score chain is nonincreasing, and Lemma 1 applies. □
The greedy argument given after Theorem 1 carries over with the group multiplier in place of , 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 and intent weights , let . The objective in this section is
It reduces to Eq. (1) under row support one, and the hardness result uses unit intent weights.

(a) Hardness at row support three

(b) Greedy fails with three documents

(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 , while ranking both endpoints of an edge loses times the later discount. (b) With and , 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 , , and covering documents, the prefix LP caps the coverage gain by every tangent (dashed) of the concave interpolation of . The cap equals 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 , exact binary -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 of size , every vertex initially contributes three units. If both endpoints of edge are selected, its later endpoint contributes instead of one. Therefore the exact identity is
All discounts and are positive, so the explicit cap is reached if and only if is independent. An exact ranking oracle therefore returns an independent -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 times the discount of the later endpoint. The exclusion of 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 , strict failure is impossible. Let be the total weight of their shared intents and and the weights exclusive to each document. Greedy ranks first the document with the larger exclusive weight, say , and the two complete rankings differ by in its favor, because the shared contributions cancel. Figure 2b gives a three-document failure under the evaluator’s defaults , , and . Intents and have weight 1, intents and have weight 0.8, and the documents cover A = , B = , and C = . 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 . 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 . Empty intents contribute nothing to the objective. Define the concave coverage function
For the ranking prefix , the cumulative novelty gain before position discount is exactly , because each intent contributes occurrence marginals regardless of interleaving. Set and . Abel summation gives
Because every is nonnegative, upper bounds on the prefix gains combine into an upper bound on the full objective. The LP below bounds all prefix gains jointly while keeping the prefixes nested.
Linearly interpolate between its integer points. Its segment slopes are , so the interpolation is concave and its hypograph is the intersection of tangent halfspaces, drawn in Figure 2c. Introduce , the fractional membership of document in the length- prefix, and , which stands for the coverage gain of intent in that prefix. Write . The prefix LP is
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 the tightest of these caps is exactly . The LP has variables and constraints.6
Theorem 4 (Global -DCG overlap certificate). For arbitrary binary overlap, every , and every nonincreasing nonnegative discount,
Thus any feasible ranking has the deterministic certificate
Proof. Embed any integral ranking by setting . Cardinality and nesting hold. At the integer count , set . 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 . Such nested prefixes define a ranking ,7 and
A strict gap 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 carries gain , with count-based decay . Sort the gains incident to as , and define
Replacing Eq. (13) by the tangent constraints
gives an upper bound on the optimal graded count-decay objective. At an integral prefix, the envelope is exact when its selected -incidences are the largest available gains and occur in nonincreasing gain order.
Proof. If a prefix contains incidences for intent , rearrangement bounds its cumulative contribution by pairing the largest incident gains with , yielding . The slopes 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 , and the LP relaxation preserves the upper bound. The stated prefix condition attains the rearrangement bound. □
Projection bound without an LP solver. Write in the binary case. For every positive document, choose one retained intent , keep only that incidence, and solve the resulting row-support-one instance exactly. Let denote its ChainMerge optimum. For intent , let be the multiset of deleted gains, sorted as . Then
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 . Enumerate the ranked deleted incidences of intent in occurrence order. Its -th such incidence has global position at least and at least preceding occurrences of , so its coefficient is at most . 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 , so minimizing it over 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 -DCG instances and 1,000 row-support-one ERR-IA instances. We draw uniformly from , assign each item independently to one of at most four intents, and draw uniformly from . For -DCG, gains are uniform on and is uniform on . For ERR-IA, satisfaction probabilities are uniform on , while intent weights are independent uniforms on normalized to sum to one. We compare ChainMerge with exhaustive enumeration of every ordered top- 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 and logarithmic discount . 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 , exact subset DP provides the optimum for all pools. We compare this optimum with marginal greedy, the prefix LP, and the projection bound. We then apply the LP at to each complete positive-document pool. For small pools, let be the marginal-greedy value and the corresponding LP or projection upper bound.8 Because subset DP supplies the exact optimum, we report the certificate width as . For complete queries, where the exact optimum is unavailable, we report the certified relative gap .
The 20 complete queries with row support one also provide a real-data ERR-IA test. With binary relevance, the standard ERR mapping gives satisfaction 0.5 for each positive judgment. We use uniform intent priors, reciprocal-rank discount, and , and compare ChainMerge with marginal greedy over 200 repetitions per query.
Leaderboard robustness. We collect the published mean -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 , let be the evaluator’s greedy denominator and the prefix-LP upper bound. The exact denominator lies in , so replacing never raises a query score and lowers it by at most . A run with published mean over topics therefore has an exact-denominator mean in , where is half a unit in the last published decimal and averages the largest 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 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 , sort candidates once by utility, and use prefixes of 5,000, 10,000, 20,000, 30,000, 45,000, and 65,238 candidates with . For graded -DCG with , 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. 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 -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 -IDCG denominator at . 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 , and one partition followed by a small heap merge. Figure 4b shows how the full-pool speedup changes with . 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 -DCG with the subcategory grouping () at 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 -DCG path over binary marginal greedy (dashed). Squares mark the category grouping () and squares the subcategory grouping (), 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 -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 -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 -DCG, the prefix LP upper-bounds the optimum and recovers an optimal ranking only when an optimal 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 -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 -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 -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.
| Year | Queries | Positive documents | ||
| Total | Row support one | Total | Row support one | |
| 2009 | 50 | 12 (24.0%) | 4,942 | 3,622 (73.3%) |
| 2010 | 48 | 3 (6.3%) | 6,553 | 4,862 (74.2%) |
| 2011 | 50 | 2 (4.0%) | 5,030 | 2,707 (53.8%) |
| 2012 | 50 | 3 (6.0%) | 5,559 | 3,111 (56.0%) |
| Total | 198 | 20 (10.1%) | 22,084 | 14,302 (64.8%) |
Table 2. Structure of positive TREC Web diversity judgments.
| Year | Queries | Certified | Mean gap | Median sec. |
| 2009 | 50 | 46 | 0.0783% | 0.084 |
| 2010 | 48 | 45 | 0.0001% | 0.161 |
| 2011 | 50 | 49 | 0.0060% | 0.132 |
| 2012 | 50 | 49 | 0.0002% | 0.189 |
| Total | 198 | 189 | 0.0213% | 0.137 |
Table 3. Complete-query prefix-LP certificates at . Gaps are relative to the LP upper bound. Certificate decisions use exact rational arithmetic, and times are numerical HiGHS medians.
| (a) Graded -DCG, | |||||
| Field | Marginal greedy | ChainMerge | Speedup | ||
| Category | 18 | 10 | 136.4 | 7.41 | 18.4 |
| Category | 18 | 100 | 1,550.5 | 8.04 | 192.8 |
| Category | 18 | 500 | 8,098.3 | 8.01 | 1,010.9 |
| Subcategory | 270 | 10 | 127.9 | 7.54 | 17.0 |
| Subcategory | 270 | 100 | 1,326.9 | 8.09 | 164.0 |
| Subcategory | 270 | 500 | 7,191.5 | 7.84 | 917.1 |
| (b) Binary -IDCG from group counts, | |||||
| Field | Marginal greedy | Count-only | Speedup | ||
| Category | 18 | 10 | 134.4 | 0.0102 | 13,120 |
| Category | 18 | 100 | 1,520.0 | 0.0664 | 22,907 |
| Category | 18 | 500 | 7,989.5 | 0.314 | 25,427 |
| Subcategory | 270 | 10 | 134.2 | 0.0597 | 2,250 |
| Subcategory | 270 | 100 | 1,339.4 | 0.120 | 11,161 |
| Subcategory | 270 | 500 | 6,682.8 | 0.411 | 16,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]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]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]Yossi Azar and Iftah Gamzu. 2011. Ranking with Submodular Valuations. In Proceedings of SODA. 1070–1079. doi:10.1137/1.9781611973082.81DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]Bennett Fox. 1966. Discrete Optimization Via Marginal Analysis. Management Science 13, 3 (1966), 210–216. doi:10.1287/mnsc.13.3.210DOI
- [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]Toshihide Ibaraki and Naoki Katoh. 1988. Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, MA.DOI
- [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]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]Sean MacAvaney. 2021. pyndeval: Python Bindings for pndeval. https://github.com/seanmacavaney/pyndeval.
- [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]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]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]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]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]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]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]Saúl Vargas. 2015. RankSys: A Java Framework for Recommender Systems. https://ranksys.github.io/. Accessed 2026-08-25.
- [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]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]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]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]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]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]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]Yadong Zhu, Yanyan Lan, Jafeng Guo, and Xueqi Cheng. 2015. Structural Learning of Diverse Ranking. arXiv preprint arXiv:1504.04596 (2015).DOI


