When evaluating machine learning models, we often rely on ranking. Whether it is information retrieval, recommendation systems, or link prediction, the standard workflow is simple: sort items by a predicted score and calculate metrics like Mean Reciprocal Rank (MRR), Average Precision (AP), or Area Under the ROC Curve (AUC).
We generally treat these metrics as deterministic ground truths. However, a silent assumption underlies almost all ranking metrics: that every item has a unique score. In reality, models frequently assign identical scores to different items, creating ties. How a system handles these ties can completely distort evaluation metrics, introduce non-determinism, and cause models to overfit to arbitrary data orderings.
The Anatomy of a Tie: Why Metrics Lie
Ties appear naturally in discrete distance spaces (such as Hamming distance in binary hashing) or when models output collapsed or uniform distributions. However, they are also surprisingly common in continuous spaces.
Anguelos Nicolaou et al. demonstrated in Non-deterministic Behavior of Ranking-based Metrics when Evaluating Embeddings that numerical ties frequently occur in continuous vector embeddings when multiple database items are equidistant from a query. Because standard sorting libraries break ties based on arbitrary factors like memory allocation or input order, the resulting performance scores become non-deterministic. The authors showed that this ambiguity allows the same model to produce different performance scores across different hardware or software environments, a flaw that can even be exploited by adversaries to artificially inflate leaderboard rankings without learning meaningful features.
Similarly, Miao Chen et al. discovered in Commonly used software tools produce conflicting and overly-optimistic AUPRC values that popular software tools for calculating the Area Under the Precision-Recall Curve (AUPRC) yield conflicting and overly optimistic values because they handle tied classification scores inconsistently, ordering tied scores based on input order rather than treating them identically.
In Knowledge Graph Completion (KGC), Zhiqing Sun et al. revealed in A Re-evaluation of Knowledge Graph Completion Methods that many high-profile neural models produce identical scores for both true and false facts. When evaluation frameworks use an "optimistic" tie-breaking protocol (always placing the true fact at the top of a tied group), metrics are artificially inflated, masking the model's true discriminative weaknesses and making them appear superior to simpler baselines.
Optimistic Sorting: [True Fact (Rank 1), False Fact 1, False Fact 2] -> Inflated Metric
Pessimistic Sorting: [False Fact 1, False Fact 2, True Fact (Rank 3)] -> Deflated Metric
Deterministic Tie-Aware: Average or distribute the rank across all positions.
Tie-Aware Evaluation Frameworks
To fix this, researchers have developed frameworks that explicitly account for ties rather than sweeping them under the rug of an arbitrary sorting algorithm. The core intuition is to replace arbitrary tie-breaking with deterministic or mathematically bounded strategies.
1. Bounding and Averaging Ranks
One intuitive solution is to evaluate the full range of possible rankings. In PyKEEN 1.0: A Python Library for Training and Evaluating Knowledge Graph Embeddings, Mehdi Ali et al. implemented a framework that tracks optimistic, pessimistic, and average ranks. By exposing instances where a model assigns identical scores to different triples, this transparency prevents inflated performance metrics and reveals hidden discriminative weaknesses.
2. Distributed Ranking
Instead of forcing a single permutation, distributed ranking spreads an entity's rank across all possible positions it could occupy. As proposed by Takuma Ebisu et al. in Graph Pattern Entity Ranking Model for Knowledge Graph Completion, this method provides a deterministic evaluation strategy that eliminates the variance introduced by random tie-breaking. Similarly, in large-scale image retrieval using hashing, Kun He 0003 et al. showed in Hashing as Tie-Aware Learning to Rank that implementing tie-aware metrics that analytically average over all possible permutations eliminates ambiguity and provides a stable, deterministic objective for optimization.
3. Stochastic Tie-Breaking
Alternatively, Zhiqing Sun et al. advocate for a stochastic tie-breaking protocol, which handles tied scores by assigning the ground truth a random position among all candidates with the same score. This approach ensures that evaluation metrics reflect the model's actual discriminative power rather than an optimistic bias in the ranking algorithm, allowing for fair comparisons between models with continuous outputs and those with discrete or collapsed output distributions.
Stochastic Regularization in Training
Handling ties is not just an evaluation problem; integrating tie-awareness directly into the training process can serve as a powerful regularizer.
In real-world recommendation systems, datasets frequently contain ties (e.g., a user giving the same 5-star rating or interaction to multiple items). Standard listwise ranking frameworks struggle with this, often forcing the model to learn a fixed, arbitrary sequence based on the initial data ordering, which leads to overfitting.
To solve this, LIWEI WU et al. developed SQL-Rank in Large-scale Collaborative Ranking in Near-Linear Time and SQL-Rank: A Listwise Approach to Collaborative Ranking. The authors introduced a "Stochastic Queuing Process" that dynamically shuffles items with identical scores during each training iteration.
Why does this work? Treating ties as a dynamic, random permutation rather than a fixed constraint acts as a form of stochastic regularization. It allows the model to explore multiple valid permutations of the same data, preventing it from overfitting to an arbitrary initial sequence and significantly boosting final recommendation precision and generalization to unseen user preferences.
Iteration 1: [Item A (Score 5), Item B (Score 5)] -> Shuffled to -> [Item B, Item A]
Iteration 2: [Item A (Score 5), Item B (Score 5)] -> Shuffled to -> [Item A, Item B]
Result: Model learns they are equally good, rather than memorizing A > B.
Furthermore, integrating tie-breaking mechanisms directly into the optimization framework ensures consistency between the training objective and real-world evaluation scenarios. For instance, Harikrishna Narasimhan et al. demonstrated in A Structural SVM Based Approach for Optimizing Partial AUC that incorporating robust tie-breaking mechanisms directly into a Structural SVM framework is necessary to maintain consistency when optimizing for partial AUC in applications where score ties are common.
Ubiquity Across Domains
The challenge of tie-breaking spans numerous other domains where ranking is fundamental:
- Machine Translation: In system selection, Lluís Formiga et al. showed in The TALP-UPC Approach to System Selection: Asiya Features and Pairwise Classification Using Random Forests that accurately identifying and handling ties between translation systems of similar quality is critical; forcing an artificial preference introduces noise and reduces leaderboard reliability.
- Tournament Predictions: In sports analytics, Claus Thorn Ekstrøm et al. designed the Tournament Rank Probability Score (TRPS) in Evaluating one-shot tournament predictions to process collapsed ranks for teams eliminated in the same round without requiring arbitrary tie-breaking procedures that could bias results.
- Social Choice Benchmarking: In Vote'n'Rank: Revision of Benchmarking with Social Choice Theory, Mark Rofin et al. applied voting rules to aggregate model performance, highlighting that robust tie-breaking protocols are essential to maintain the discriminative power of leaderboards when multiple models exhibit similar performance profiles.
By moving from arbitrary tie-breaking to tie-aware learning and evaluation, researchers ensure that performance metrics reflect true discriminative capability rather than the hidden biases of sorting implementations.
Key Foundational Work
The TALP-UPC Approach to System Selection: Asiya Features and Pairwise Classification Using Random Forests (2013) — contributed 2 concept elements to this direction.
A Structural SVM Based Approach for Optimizing Partial AUC (2013) — contributed 1 concept elements to this direction.
Bayesian rating systems with additional information on tournament results (2014) — contributed 1 concept elements to this direction.