Score Tie Repeatability Eval

score-tie-repeatability-eval

Repeatability Corner Cases in Document Ranking: The Impact of Score Ties — Lin et al. (2018) (arXiv:1807.05798, 2018)

What this evaluates

This evaluation protocol measures the impact of score ties on document ranking repeatability across diverse information retrieval collections. It quantifies how non-deterministic tie-breaking during multi-threaded indexing causes variability in standard ranking metrics, even when using identical queries and ranking models.

Datasets

• TREC 2004 Robust Track (Disks 4 & 5) — total ?; splits: test (-1)
• TREC 2005 Robust Track (AQUAINT) — total ?; splits: test (-1)
• TREC 2017 Common Core Track (NYT Annotated Corpus) — total ?; splits: test (-1)
• TREC 2011/2012 Microblog Tracks (Tweets2011) — total ?; splits: test (-1)
• TREC 2013/2014 Microblog Tracks (Tweets2013) — total ?; splits: test (-1)
• TREC 2010–2012 Web Tracks (ClueWeb09b) — total ?; splits: test (-1)
• TREC 2013–2014 Web Tracks (ClueWeb12-B13) — total ?; splits: test (-1)

Metrics

• AP (primary) — range: [0, 1]
  • Average Precision: the mean of precision values computed at each rank where a relevant document is retrieved, averaged over all queries.
• P30 (primary) — range: [0, 1]
  • Precision at rank 30: the fraction of relevant documents in the top 30 retrieved results.
• NDCG@20 — range: [0, 1]
  • Normalized Discounted Cumulative Gain at cutoff 20: measures ranking quality by discounting the relevance score logarithmically based on position, normalized by the ideal ranking.

Input / output format

Input: Queries (TREC topics) and a document collection indexed via Lucene/Anserini. The retriever processes each query to generate a ranked list of document IDs.

Output: A ranked list of up to 1000 document IDs per query, formatted in TREC run format with scores.

Scoring recipe

def compute_metrics(run_file, qrel_file, collection_type):
    if collection_type in ['newswire', 'tweet']:
        # Use trec_eval for AP and P30
        return trec_eval(qrel_file, run_file, metrics=['ap', 'P.30'])
    else: # web
        # Use gdeval.pl for NDCG@20
        return gdeval(qrel_file, run_file, cutoff=20, metric='ndcg')

Common pitfalls

• External evaluation tools like trec_eval sort results by score internally, which can override the system's intended tie-breaking order and introduce artificial variability.
• Multi-threaded indexing assigns unstable internal document IDs, causing arbitrary tie-breaking and non-reproducible rankings across different index builds.
• Average Precision (AP) is unreliable for shallow web collections with limited relevance judgments; NDCG@20 should be used instead.

Evidence (verbatim from paper)

All runs retrieved up to 1000 hits and were evaluated in terms of standard retrieval metrics: for newswire and tweet collections, we computed average precision (AP) and precision at rank 30 (P30) using trec_eval. For the web collections, we computed NDCG@20 using gdeval.pl (since the shallow pool depths make AP unreliable).

Citation

@misc{lin2018repeatability,
  title={Repeatability Corner Cases in Document Ranking: The Impact of Score Ties},
  author={Lin et al. (2018)},
  year={2018},
  note={arXiv:1807.05798}
}

• arXiv: 1807.05798