PaperlayerView exact revision on arXiv

Source-linked AI summary

Rank-Deviation Quality: A Distance-Aware Metric for Multi-Answer Retrieval and Ranking Evaluation

Xiaokun Zhou, Alessandro Moschitti, Danielle Class

arXiv:2608.25318v1cs.IR

TL;DR

Multi-answer retrieval needs evaluation that reflects both retrieved items and their order, without relying on query-invariant absolute relevance grades. RDQ scores candidate rankings against ordered reference lists using output-position weights and rank-deviation penalties, with configurable tolerance to misordering. On POI data it outperformed tested alternatives on median power and reached stable ordering agreement with fewer queries, while TREC-DL showed parity with NDCG at n=25 but favored NDCG at n=100.

  • Problem

    Multi-answer retrieval lacks a single evaluation approach that captures both item inclusion and ordering when absolute relevance grades are unavailable or difficult to calibrate across queries.

  • Method

    RDQ evaluates candidate rankings against ordered reference lists using output-position weights multiplied by rank-deviation penalties, with support for ties, variable list sizes, and configurable misordering tolerance.

  • Results

    RDQm2-a1 achieved the highest median power@100 on 5,000 POI queries, while TREC-DL RDQm1 matched native NDCG at n=25 but trailed it at n=100.

  • Takeaways & Limitations

    RDQ provides an ordinal-reference alternative that accounts for both retrieval and order, while native NDCG remains stronger at n=100 in the tested TREC-DL setting.

  • Takeaways & Limitations

    RDQ requires application-specific penalty and interface-weight choices, and TREC-DL comparisons require grade-to-rank conversion that discards spacing between grades.

Abstract

from arXiv · show

We introduce Rank-Deviation Quality (RDQ), an evaluation metric for retrieval and ranking systems that adapts to queries with varying numbers of reference items, from a single correct answer to many valid results. RDQ scores a candidate ranking against an ordered reference list (ORL): each retrieved reference item contributes its output-position weight multiplied by a rank-deviation penalty, and items outside the ORL receive zero credit. Application-specific parameters control tolerance to misordering. Larger values emphasize retrieving valid reference items, whereas smaller values place more weight on matching their reference order. The output-position weights can reflect visibility in the application's interface, such as a vertical list or a carousel. Unlike metrics that require absolute relevance grades, RDQ operates on ordinal rankings, which annotators can produce through pairwise or listwise judgments. Unlike rank-correlation measures such as Kendall's tau, RDQ accounts for both which items are returned and how they are ordered. On a 5,000-query point-of-interest (POI) dataset with 12 systems, RDQ has the highest median empirical power@100 among the 13 evaluated metric configurations. It reaches mean tau >= 0.8 agreement with its own full-query ordering at 200 queries; RBP(0.9), the strongest tested non-RDQ configuration, reaches the same threshold at 250. On TREC Deep Learning benchmarks, where NDCG uses native graded labels and RDQ uses ordinal tiers derived from them, RDQ reaches comparable median power at n=25, while NDCG is higher at n=100.

1 Introduction

RDQ addresses multi-answer retrieval settings where quality depends on both which acceptable items are retrieved and their relative order, without requiring globally calibrated relevance grades. It evaluates ordered reference lists with configurable tolerance to misordering and interface-aware output-position weights.

  • Motivation: Existing metrics leave a gap when queries have multiple acceptable results and no well-defined absolute relevance scale.Binary metrics miss differences among reference items, while graded metrics require fixed relevance labels; rank correlations can ignore retrieval errors.
  • Motivation: Ordinal supervision captures relative preferences without requiring globally calibrated relevance grades across queries.Grade meanings can differ between queries with one answer and queries with many acceptable results.
  • Metric contribution: RDQ scores candidate rankings against ordered reference lists by combining output-position weights with penalties for deviation from reference rank.Items outside the reference list receive zero credit.
  • Metric contribution: Larger tolerance values emphasize retrieving valid reference items, whereas smaller values emphasize matching their exact reference order.The metric also supports tied tiers, query-varying reference-list sizes, and application-specific interface positions.
  • Evaluation: 200 queries reach mean Kendall’s τ≥0.8 agreement for RDQ’s full-query ordering, compared with 250 for RBP(0.9).The comparison is reported for the strongest tested non-RDQ configuration, RBP(0.9).
  • Evaluation: 0.108 versus 0.102 shows comparable median power at n=25 for RDQm1 and native NDCG, while NDCG is higher at n=100: 0.437 versus 0.367.These results come from the TREC Deep Learning evaluation using ordinal tiers derived from native graded judgments.

2 Related Work

Related metrics differ in their judgment inputs, ranking assumptions, user models, and treatment of ranking errors. RDQ combines ordinal-reference evaluation with separate modeling of output-position importance and deviation from expected reference rank.

  • Gain-based effectiveness metrics: Gain-based metrics such as MAP and NDCG use binary or graded relevance, with NDCG discounting graded gains by output position.These metrics require numeric gain or satisfaction mappings whose spacing is not determined by tier order alone.
  • Ranking and rank-biased comparisons: Kendall’s τ and Spearman’s ρ compare complete rankings over the same item set, while partial-ranking extensions add top-k or weighting variants.These approaches focus on ordering comparisons rather than the full combination of retrieval and ranking quality.
  • Ranking and rank-biased comparisons: RBP evaluates top-ranked items using a geometric persistence model, while related measures vary how set overlap and ranking position are combined.Rank-Biased Recall ignores order within the observation, whereas Rank-Biased Alignment rewards items jointly high in both rankings.
  • Preference-based evaluation: Preference-based evaluation can elicit pairwise judgments that supply ordinal references without absolute grades.CMP handles weak orders, tied tiers, variable tier counts, and outputs that need not contain the same items as the reference.
  • Evaluating evaluation metrics: The paper evaluates metrics with two-sided randomization tests, empirical power estimates, system-pair discrimination, and query-subsampling stability analysis.These tools assess reliability and the query counts needed for metric comparisons.

3 Metric Definition

RDQ evaluates candidate rankings against query-specific ordered reference lists, combining output-position importance with penalties for deviation from expected reference ranks. It supports ties, variable reference-list sizes, and application-specific tolerance to misordering.

  • RDQ computes a normalized weighted sum over retrieved reference items using output-position weights and rank-deviation penalties.Items outside the ORL receive zero credit, and the normalization makes the ideal ranking score 1.
  • An ORL assigns consecutive integer ranks to reference items, with items sharing a rank forming a tied tier.A smaller rank denotes a better item, and tied-item order does not affect RDQ.
  • RDQ assumes the ORL is sufficiently complete at cutoff k because items absent from it receive zero credit.ORL length can vary with query breadth; a one-item ORL should represent a narrow query rather than incomplete annotation.
  • The metric handles incomplete outputs and duplicates by leaving empty positions uncredited and granting credit only to an item’s first occurrence.The denominator remains unchanged when fewer than k items are returned.
  • Output-position weights are positive, non-increasing, and adaptable to interface layouts such as vertical lists or carousels.Equal weights are also allowed when the application does not distinguish displayed positions.
  • M1 uses an asymmetric rank ratio, whereas M2 uses displacement with application-specific tolerance parameters.For M2, larger α weakens displacement penalties; the paper reports α=1 and α=4 with λ=0.2 unless otherwise specified.

4 Experimental Analysis

RDQ is evaluated using controlled examples, POI experiments across 12 reranking systems, and TREC Deep Learning experiments with tie-heavy ordinal reference lists.

  • Controlled examples isolate RDQ’s behavior.
  • POI experiments assess discriminative power, reference-list-size effects, ranking stability, and parameter sensitivity across 12 reranking systems.
  • TREC Deep Learning experiments evaluate RDQ on tie-heavy ORLs derived from graded relevance judgments.

4.1 Common Experimental Setup

The experiments compare three RDQ configurations and several baseline metrics under shared cutoff and weighting conventions. Graded NDCG uses native TREC grades or converts ORL ranks into grades in other settings.

  • Three RDQ configurations are compared: M1, M2 with α=1, and M2 with α=4.The α=1 setting applies the stronger displacement penalty; M2 uses λ=0.2 unless otherwise specified.
  • Binary NDCG, MAP, RBP, and CMP are evaluated across the analyses, with multiple persistence settings for RBP and CMP in POI and TREC-DL experiments.
  • Graded NDCG uses native 0–3 TREC-DL judgments or converts ORL ranks using inverse or linear grade mappings.The inverse mapping is grade(r)=1/r; the linear mapping is grade(r)=T_q−r+1.
  • All metrics use cutoff k=5 in Sections 4.2 and 4.3, while TREC-DL uses k=10.

4.2 Analysis with Controlled Examples

Controlled examples show that RDQ uniquely combines sensitivity to item order, invalid retrievals, reference-list size, and output-position importance. Its M2 variants respond to every tested property, while alpha controls displacement-penalty severity.

  • Positional sensitivity: All order-aware metrics decrease as the prediction becomes more misordered, but RDQ M2-a4 drops least because alpha=4 weakens its penalty.Binary metrics assign identical scores when the same reference items are returned, regardless of order.
  • Severe misranking and invalid items: RBP at 0.6723 and binary NDCG at 1.0000 retain ideal top-five values despite severe displacement, dropping only when an item leaves the ORL.RDQ and other order-aware effectiveness metrics account for the displacement.
  • Reference-list size adaptation: M2 scores increase with ORL size, reflecting normalization for queries ranging from one to 20 reference items.M1 remains flat at 0.7619 because its penalty has no size term.
  • Output-position importance: Changing output-position weights raises the RDQ score from 0.7429 to 0.8667 when an invalid item occupies a less important position.The prediction is identical in both experiments, so the change is attributable to output-position weighting.
  • Reversed order and tied relevance: For reversed two-item rankings, tau and rho assign −1, whereas order-aware effectiveness metrics provide graded partial credit.When both reference items are tied, standard rank correlations are undefined.
  • Overall behavior: RDQ M2 variants respond to item order, invalid items, reference-list size, tied relevance, and output-position weights.Other metrics are insensitive to at least one tested property; alpha controls how strongly displacement is penalized.

4.3 Experiments on the POI Dataset

The POI study evaluates RDQ across varied reference-list sizes, 12 systems, and 13 metric configurations using randomized pairwise tests and query subsampling. RDQ M2-a1 achieves the strongest overall discriminative power and ranking stability, although performance varies with parameters and reference-list size.

  • Experiment setup: 12 system configurations produce 66 pairwise comparisons, evaluated under 13 metric configurations with two-sided randomization tests.The tests use 1,000 permutations and alpha=0.05; power is estimated from 300 subsamples at each query budget.
  • Discriminative power: 46 of 66 system pairs are distinguished under all 13 configurations, while 64 of 66 are distinguished under at least one configuration.The analyses therefore compare both pairwise power and stability of overall system rankings.
  • Discriminative power: 0.353 is the highest median power@100, achieved by RDQ M2-a1@5; RBP(0.9)@5 reaches 0.287, and RDQ’s median N80 is 350 versus 450.RDQ M2-a1@5 remains 23% above RBP(0.9)@5 in median power@100.
  • Reference-list-size effects: For queries with ≤3 references, RDQ is the only metric family with nonzero median power, while power increases with reference-list size for every configuration.RDQ M2-a4@5 reaches 0.073 in the ≤3 bucket; the bucket contains exactly 100 queries and is evaluated once.
  • System-ranking stability: 200 queries suffice for RDQ M2-a1@5 to reach mean tau≥0.8 agreement with the full-query ranking, compared with 250 for the strongest RBP settings.RDQ M2-a1@5 also has the highest reported stability AUC_tau, at 0.904.
  • Parameter sensitivity: Across the parameter grid, median power@100 ranges from 0.230 to 0.353, and 16 of 25 configurations exceed RBP(0.9)@5 at 0.287.The peak occurs at (alpha=1, lambda=0.2), while higher power than tuned RBP does not hold throughout the grid.

4.4 Experiments on Standard IR Benchmarks

The TREC-DL evaluation tests RDQ on four pooled benchmarks using ordinal tiers derived from graded judgments, comparing its power and system-order agreement with established metrics. RDQ is comparable to native NDCG at n=25, while native NDCG leads at n=100; agreement is generally high but weakest in 2020.

  • Experiment setup: Four TREC-DL datasets from 2019–2022 are pooled into 221 queries with relevance judgments on a four-point scale.The datasets contain 43, 45, 57, and 76 judged queries respectively.
  • Experiment setup: RDQ, CMP, MAP, RBP, binary NDCG, and native NDCG are evaluated at cutoff k=10 using six system pairs.RDQ and CMP use ORL tiers derived from positive graded judgments, while native NDCG retains the original grades.
  • Discriminative power: At n=25, median power is 0.108 for RDQm1@10, 0.107 for MAP@10, and 0.102 for native NDCG@10.These estimates are close; at n=100, native NDCG reaches 0.437 versus 0.367 for RDQm1@10.
  • Discriminative power: At n=100, native NDCG@10 has median power 0.437 versus 0.367 for RDQm1@10, although their p90 values are 0.868 and 0.870.No RBP or CMP setting exceeds any RDQ variant or native NDCG at n=100.
  • Agreement with established metrics: RDQ generally agrees with established metrics, with higher agreement in 2021–2022 and weaker or divergent orderings in 2019–2020.In 2020, RDQm1 has τ = −1.0 against CMP(0.8) and CMP(0.9), while M2 variants have τ between −0.33 and 0 against CMP settings.

4.5 Discussion

The discussion links RDQ variant performance to reference-list structure and distinguishes its ordinal-reference use case from settings where calibrated graded judgments already support native NDCG. It also identifies application choices, conversion choices, limited system coverage, and reference completeness as important boundaries.

  • Reference structure: RDQm2 leads on nearly unique POI reference ranks, whereas RDQm1 has the largest median on tie-heavy, grade-derived TREC-DL references.M2’s size-scaled displacement penalty is weakened by large tiers, while M1’s rank-ratio penalty does not depend on list size.
  • Reference representation: On POI, RDQm2-a1 reaches median power 0.353 versus 0.233 for inverse-conversion NDCG and 0.213 for linear-conversion NDCG.The comparison does not exhaust all possible relevance mappings or establish lower annotation cost.
  • Limitations: RDQ requires application choices for penalty functions and UI weights, whose forms are not derived from a user-behavior model and whose learning is left to future work.The study evaluates M1, M2, and 25 M2 parameter configurations.
  • Limitations: Cross-format comparisons depend on conversion choices: grade-to-rank conversion discards grade spacing, while rank-to-grade conversion requires gain values absent from ordinal judgments.The evaluated conversions and persistence settings do not exhaust all plausible choices.
  • Limitations: The TREC-DL evaluation uses only four systems, producing noisy estimates, and the ≤3 bucket contains exactly 100 queries evaluated once.These settings limit the precision of the corresponding power and agreement estimates.
  • Limitations: RDQ assumes the ordered reference list is sufficiently complete; valid but unlisted items receive zero credit.This can penalize systems that retrieve valid items omitted from the reference.
  • Limitations: The POI experiment uses a 5,000-query subsample selected to bound the computational cost of power simulations.At submission time, POISS was not yet publicly available but was scheduled for release.

5 Conclusion

The paper concludes that RDQ evaluates rankings against ordered references without graded gains and targets ordinal-reference settings complementary to native NDCG and browsing-oriented metrics. Its strongest results occur on the POI panel, while TREC-DL shows parity at n=25 but higher NDCG power at n=100.

  • Conclusion: RDQ evaluates multi-answer retrieval against ordered reference lists without requiring graded gain values, while supporting tied tiers, variable reference sizes, and application-specific position weights.Its experiments characterize statistical sensitivity and subsampling consistency with supplied ordinal references.
  • Conclusion: RDQm2-a1 has median power@100 of 0.353 versus 0.287 for RBP(0.9), the strongest tested non-RDQ configuration, on the 12-system POI panel.RDQm2-a1 reaches mean τ ≥ 0.8 with 200 queries versus 250 for RBP(0.9).
  • Conclusion: On the four-system TREC-DL panel, RDQm1 and native NDCG have comparable median power at n=25, while NDCG is higher at n=100.The reported values are 0.108 versus 0.102 at n=25 and 0.437 versus 0.367 at n=100.
  • Conclusion: Native NDCG remains a strong choice with calibrated graded judgments, whereas RDQ targets the complementary setting of ordinal references.RBP and other persistence-based metrics are described as better suited when evaluation should model user browsing behavior.

Ethical Considerations

The ethical discussion notes that RDQ can influence systems and decisions through the rankings it favors, while inheriting errors or biases in its reference data. It recommends pairing metric scores with human evaluation for high-stakes decisions.

  • Ethical considerations: RDQ can affect systems and decisions through the rankings it favors and inherits errors or biases in its reference.The POI ordered references use GenAI-assisted, silver-standard labels.
  • Ethical considerations: For high-stakes decisions, metric scores should be paired with human evaluation.The ordinal judgments describe items rather than users, and no personal or identifying information is used.
Loading 2608.25318v1…