PaperlayerView exact revision on arXiv

Source-linked AI summary

Tie Handling Is Part of the Evaluation Protocol: An Order-Invariance Audit for Tie-Heavy Recommender Scores

Chengkun Guo, Han Chen, Yilin Zhu, Yingrui Li

arXiv:2609.26977v1cs.IR

TL;DR

Offline recommender evaluation can leave exact-score tie handling implicit, allowing a stable sort to preserve a relevant-first input order. The paper formalizes and audits row-order invariance while holding candidates and scores fixed. Tie-heavy attribute scores show substantial metric changes under deterministic hash tie-breaking, while selected low-tie diagnostics are nearly unchanged.

  • Problem

    When equal-scored candidates are ordered by input position, a relevant-first row can affect ranking despite scores not distinguishing the tied items.

    Source: §1 · pp. 1–2

  • Method

    The paper defines row-order invariance, changes only the exact-tie ordering rule with candidates and scores fixed, derives random-tie expected metrics, and proposes a reporting checklist.

    Source: §1 · pp. 1–2

  • Results

    NDCG@10 for the Amazon weighted attribute-overlap score falls from 0.8474 to 0.1702, while the residualized score changes by 0.0004 in NDCG@10; MovieLens shows the same pattern for tag-attribute overlap and little change for popularity.

    Source: §5.1 · p. 5

  • Takeaways & Limitations

    Reporting candidate construction, tie prevalence, tie-breaking, and a permutation check makes the evaluated quantity clear and reproducible.

    Source: §8 · p. 7

    The audits cover two public datasets with one relevant item and 30 sampled negatives, and do not estimate prevalence across benchmarks or production systems.

    Source: §7 · p. 6

Abstract

from arXiv · show

Offline top-k evaluation often ranks one held-out relevant item together with sampled negatives. When several candidates receive exactly the same score, the tie-breaking rule becomes part of the ranking. A common implementation stores the relevant item first and then applies a stable sort, which preserves input order among equal scores; the relevant item therefore wins every tie. We call an evaluator row-order invariant when permuting the input candidates without changing their identities, labels, or scores leaves the final ranking unchanged. We audit this property by holding candidates and scores fixed and changing only the tie-breaking rule. On 30,000 Amazon Beauty & Personal Care rows, NDCG@10 for a rating-weighted attribute-overlap score is 0.85 under input-order tie-breaking. A deterministic hash tie-break based on user and item IDs lowers it to 0.17. The exact expectation under uniform random tie-breaking closely matches the mean over 100 independent hash seeds, while a residualized attribute score with few exact ties is nearly unchanged. MovieLens Tag Genome shows the same pattern for an attribute-overlap score, whereas item popularity is nearly unchanged. We derive expected Hit Rate and NDCG at cutoff k when the relevant item is randomly ordered among candidates with the same score, and we provide a practical reporting checklist. The same issue can occur in sampled or full-catalog evaluation whenever exact ties affect top-k membership or rank.

1. Introduction

Offline recommender results depend on the full evaluation protocol, including how exact score ties are ordered. This paper formalizes row-order invariance and tests tie handling while holding candidate sets and scores fixed.

1. Introduction

  • Offline evaluation depends on choices including data split, candidate set, negative sampling, relevance definition, ranking rule, cutoff, and aggregation method.Source: §1 · p. 1
  • Stable sorting can make a relevant-first input row rank the relevant item first among equal scores, and reordering candidates can change the metric without changing model output.The paper focuses on the interaction of relevant-item-first rows, tie-heavy scores, and stable sorting that reuses input order as an undeclared ranking criterion.Source: §1 · pp. 1–2
  • The paper formalizes row-order invariance and isolates tie handling by changing only the ordering rule while preserving candidates, labels, and scores.The definition requires the final ranking to remain unchanged under every candidate permutation that preserves identities, labels, and scores.Source: §1 · p. 1
  • The study derives expected Hit Rate and NDCG under uniform random ordering within ties, compares tie-breaking approaches across two domains, and offers a six-part reporting checklist.The checklist covers candidate set, pre-sort candidate order, tie prevalence, tie-breaking, permutation tests, and sensitivity analysis.Source: §1 · p. 2

2. Related Evaluation Methodology

This paper distinguishes its downstream audit of fixed scores and evaluator tie handling from other evaluation and ranking concerns. It isolates whether changing candidate order changes the result when candidates and scores stay fixed.

2. Related Evaluation Methodology

  • The audit begins after the candidate set is declared and tests whether presenting the same candidates and scores in another order changes the evaluator’s result.Sampled and full-catalog evaluation can define different candidate sets and produce different metric values or system orderings.Source: §2 · p. 2
  • Prior work studies ties in information retrieval and recommender comparisons; this paper isolates relevant-first rows, stable sorting, and exact ties with candidates and scores fixed.Source: §2 · p. 2
  • Listwise LLM ranking studies candidate-order effects on model outputs, whereas this audit fixes scores and examines only evaluator treatment of equal scores.Source: §2 · p. 2
  • Logged-feedback position bias acts during data collection and learning, while this audit occurs after candidate scores have been produced.Source: §2 · p. 2

3. When Tie-Breaking Changes the Metric

Exact-score ties can affect top-k membership and position-sensitive metrics, and stable sorting can preserve input order rather than produce a row-order-invariant ranking. The paper characterizes expected metrics under random tie ordering and compares practical tie-breaking approaches.

3.1. Candidate rows and exact-score ties

  • A tie block is a maximal consecutive group of equal-scored candidates; a block crossing the top-k boundary can change membership, while within-cutoff ties can change NDCG.A stable sort by score alone retains input positions among equal scores, so it is not row-order invariant; a disclosed reproducible hash key independent of candidate position provides an invariant tie-break.Source: §3.1 · p. 2

3.2. Expected metrics under uniform random tie-breaking

  • With one positive and 30 tied negatives, placing the positive first gives Hit@10 and NDCG@10 of 1, while uniform random tie-breaking gives expected Hit@10 = 10/31 = 0.3226 and expected NDCG@10 = 0.1466.A uniformly permuted complete candidate row gives an unbiased but noisy single-run estimate; repeated random tie-breaking or analytic averaging gives a clearer summary.Source: §3.2 · p. 3

3.3. Practical tie-breaking choices

  • The four approaches are input-order, deterministic hash, repeated random, and exact expected tie-breaking; the latter two estimate or compute the average over random tie orders.Hashing selects one repeatable ranking, while exact analytic averaging is available in the one-relevant-item setting.Source: §3.3 · p. 3

4. Audit Design

The audit compares two domains using rows with the held-out relevant item first and 30 sampled negatives, then applies multiple tie-breaking treatments to fixed scores. Amazon row-level arrays support reconstruction and additional analyses, but corresponding MovieLens arrays were not retained.

4.1. Candidate sets and scores

  • Both audits place the held-out relevant item before 30 sampled negatives, and the candidate-sampling seed is 42 in both domains.Amazon uses 30,000 sampled rows from 2,073,945 held-out interactions; MovieLens uses 10,000 test users.Source: §4.1 · p. 3, Table 1 · p. 4
  • Amazon’s weighted attribute-overlap score uses rating-weighted overlap with attributes in the user’s history; MovieLens evaluates Tag Genome attribute overlap, its centered version, and item popularity.The Amazon centered score uses catalog-mean-centered attributes; MovieLens treats ratings of at least four stars as positive and thresholds six Tag Genome concepts at 0.7.Source: §4.1 · p. 4
  • Amazon’s residualized score removes predictable item-attribute and interaction-weight components and is included as a low-tie stability check.Source: §4.1 · p. 4

4.2. Tie-breaking implementations and metrics

  • The audit reports NDCG@10, Hit Rate@10, and prevalence measures for exact ties, top-10 boundary-crossing ties, and relevant-item ties.The compared tie treatments include input order and a deterministic hash rule; the latter uses a fixed seed, user ID, and item ID, with item ID as fallback.Source: §4.2 · p. 4

4.3. Reproducibility

  • Reconstructed Amazon rows reproduce all 84 original aggregate values exactly, with maximum absolute difference zero, and support hash, expectation, seed, collision, and permutation analyses.Source: §4.3 · p. 5
  • MovieLens aggregate values match the accepted version, but retained row-level candidate and score arrays were unavailable for additional analyses; the artifact provides evaluator and Amazon reconstruction materials.Source: §4.3 · p. 5

5. Results

With candidates and scores fixed, changing only exact-tie handling substantially changes tie-heavy attribute-overlap results in both datasets, while scores with few consequential ties remain nearly unchanged. On Amazon, the exact expected metric under uniform random tie-breaking closely matches the mean over 100 hash seeds.

5.1. Cross-domain sensitivity to input order

  • For Amazon’s weighted attribute-overlap score, deterministic hash rather than input-order tie-breaking lowers NDCG@10 from 0.8474 to 0.1702; Hit@10 also falls from 0.9997 to 0.3526.By comparison, the residualized attribute score changes by 0.0004 in NDCG@10.Source: Table 2 · p. 5, §5.1 · p. 5
  • MovieLens tag-attribute overlap NDCG@10 changes from 0.8380 to 0.2332 under the two tie-breaking rules, while item popularity is unchanged to four decimals.The centered score behaves similarly; popularity’s stability is reported when tie-breaking has little effect on relevant rank.Source: §5.1 · p. 5

5.2. Deterministic, randomized, and expected tie-breaking

  • Deterministic hashing supplies a repeatable ranking, whereas expected metrics average unresolved positions within tie blocks.Repeated hashes numerically check the analytic result and reveal seed-to-seed variation.Source: §5.2 · p. 5
  • The exact expected Amazon NDCG@10 under uniform random tie-breaking and the mean over 100 independent hash seeds agree closely.The table compares four tie treatments; deterministic hashing selects one reproducible ordering and need not equal the expectation.Source: §5.2 · p. 5, Table 3 · p. 6

6. Reporting Tie-Heavy Evaluation

Tie-breaking can affect top-k membership and position-sensitive metrics, so reporting should make candidate construction and tie handling explicit. The checklist covers candidate order, tie prevalence, permutation tests, and sensitivity analysis.

6. Reporting Tie-Heavy Evaluation

  • Ties crossing the top-k cutoff can change Hit@k, while ties wholly within the top k can still change NDCG@k.The checklist recommends sensitivity analysis when ties affect membership or relevant-item positions.Source: §6 · p. 6
  • Report whether evaluation is sampled or full-catalog, candidate count, negative-sampling details, exclusions, deduplication behavior, and seeds.Also state whether the relevant item has a fixed position and whether rows are independently shuffled.Source: §6 · p. 6
  • Report tie prevalence, the tie-breaking rule, and a permutation test for implementations claimed to be input-position independent.For hashing, disclose key inputs, seed policy, and collision fallback; for repeated random ties, report variation across runs.Source: §6 · p. 6
  • A full-row permutation independent of relevance makes the relevant item’s position within its tie block uniform in expectation, unlike moving only that item.A single permutation is one random realization, not a fixed invariant ranking.Source: §6 · p. 6

7. Limitations

The empirical audit covers two public datasets, one relevant item per row, and 30 sampled negatives, and does not estimate prevalence across benchmarks or production systems. Its scores are metadata-based components rather than complete recommenders, and full-catalog evaluation is not empirically examined.

7. Limitations

  • The audit uses two public datasets, one relevant item per row, and 30 sampled negatives, so it does not estimate how often the issue occurs across benchmarks or production systems.Continuous rankers may have few exact ties, while quantization, coarse features, fallback scores, or count-based components may create many.Source: §7 · p. 6
  • Amazon attributes are lexical metadata proxies, and the evaluated score families are components rather than complete production recommenders.The residualized Amazon score and MovieLens popularity serve as comparison cases but are constructed differently.Source: §7 · pp. 6–7
  • Full-catalog evaluation is not examined empirically, and MovieLens is limited to an aggregate comparison because row-level candidate and score arrays were not retained.In a fixed full catalog, equal scores still require an explicit ordering or averaging rule.Source: §7 · p. 7

8. Conclusion

Exact-score ties leave part of a ranking unresolved, and input-order resolution can make row construction an undeclared ranking feature. In the audited tie-heavy scores, hash tie-breaking changes NDCG@10 substantially, while low-tie comparisons are nearly unchanged.

8. Conclusion

  • When exact ties are resolved by candidate input order, row construction can enter the metric as an undeclared ranking feature.The issue applies when ties affect top-k membership or relevant-item rank.Source: §8 · p. 7
  • Tie-heavy Amazon and MovieLens scores change by roughly 0.55–0.68 NDCG@10 under deterministic hash tie-breaking, while the residualized Amazon score and MovieLens popularity are nearly unchanged.The conclusion reports these comparisons after holding candidates and scores fixed.Source: §8 · p. 7
  • Reporting candidate construction, tie prevalence, tie-breaking, and a permutation check makes the evaluated quantity clear and reproducible.Deterministic hashing provides repeatability; analytic or repeated random tie-breaking describes the average over unresolved orders.Source: §8 · p. 7

Declaration on Generative AI

The authors used ChatGPT and Claude for language, formatting, structural, and implementation assistance. They determined the research and analysis decisions and take responsibility for the publication.

Declaration on Generative AI

  • ChatGPT and Claude assisted with grammar, spelling, paraphrasing, structural suggestions, LaTeX and CEURART formatting, and portions of code drafting and implementation.The assistance also included debugging and documenting experimental and analysis code.Source: Declaration on Generative AI · p. 7
  • The authors determined the research questions, methodology, experimental decisions, result interpretation, and conclusions.Source: Declaration on Generative AI · p. 7
  • The authors reviewed and edited affected material, inspected experiments, verified the text and research artifacts, and accepted responsibility for the publication’s content.They verified calculations, citations, tables, and code.Source: Declaration on Generative AI · p. 7
Loading 2609.26977v1…