Sorted scores do not imply fixed document IDs when scores tie. If the kth position cuts through a tied group, several result sets can satisfy the same top-k score requirement. Those sets can have identical scores and different retrieval recall. First define a tie policy, then decide which alternatives the evaluation regards as equivalent.

For “Why are tied torch.topk indices unstable, and how can RAG rankings be reproduced?”, this article provides a six-document counterexample, a recall-range derivation and an executable reference ranker. A random seed is not used as a ranking contract, and synthetic numbers are not presented as search-system measurements. 中文版.

Sorted scores and fixed documents are different guarantees

The PyTorch 2.8 topk documentation states that sorted=True orders the returned k elements, while tied indices are not guaranteed stable. This does not say that every run must change. It says a caller cannot promote one observed tied order into an interface guarantee.

Distinguish three requirements: repeatability for an identical candidate input; invariance when candidate arrival order changes; and agreement across devices, versions or numerical precision. Passing a repeated-run experiment addresses only the first. If the candidate scores themselves change, the investigation already extends beyond how exact ties are ordered.

Capture candidate IDs and the actual scores used for selection before comparing outputs. Two scores displayed as 0.82 may be distinct stored values such as 0.821 and 0.824. Conversely, quantized or discrete scoring can genuinely create many identical values. Diagnose the values participating in ranking rather than their formatted display strings.

A boundary tie changes Recall@3

Construct six fictional documents. A scores nine; B, C and D each score eight; E scores seven; F scores six. For k=3, A must be selected, but any two of B, C and D satisfy the highest-three-score requirement. Valid member sets are {A,B,C}, {A,B,D} and {A,C,D}; all have the score list [9,8,8].

Let the relevant ground-truth set be G={A,B,D}, and define Recall@3 as the number of selected relevant documents divided by three. The three valid sets score 2/3, one and 2/3 respectively. The denominator is the fixed ground-truth set size, not the result count. With no model or score change, choosing different tied boundary members creates a one-third recall difference.

This deliberately large teaching example does not predict the same variation in a real application. Before comparing models, inspect whether a tied group crosses the cutoff. When every member of a tie lies entirely inside or outside the boundary, this particular membership ambiguity disappears. Ordering within a fully selected group can still affect order-sensitive metrics such as MRR and needs its own policy.

Derive an interpretable range from boundary counts

Suppose a candidates score strictly above the boundary, the boundary group contains t tied candidates, and s=k−a slots remain. Let rₕ strictly higher candidates and rₜ tied candidates be relevant, with fixed ground-truth size g>0. At least max(0,s−(t−rₜ)) relevant tied candidates must be chosen; at most min(s,rₜ) can be chosen.

Without an additional tie rule, recall therefore ranges from [rₕ+max(0,s−(t−rₜ))]/g to [rₕ+min(s,rₜ)]/g. For the lower bound, fill as many slots as possible with irrelevant tied candidates; relevance occupies only the remaining slots. Reverse that preference for the upper bound. Here a=1, t=3, s=2, rₕ=1, rₜ=2 and g=3, giving [2/3,1].

This is not a confidence interval or an estimate of unknown relevance. It uses a complete scored candidate list and existing labels to describe exact boundary-tie ambiguity. The bounds assume 0≤s≤t and a fixed ground-truth set. They cannot recover a document that approximate candidate generation never returned. Candidate-generation changes, incomplete relevance labels and tie selection must be logged separately rather than folded into this range.

A stable sort still needs a stable secondary key

torch.sort with stable=True preserves the original order of equivalent elements. The Python sorting documentation defines the same stability property. If upstream input order follows concurrent shard arrivals, preserving that order can still change the final documents. A stable algorithm does not supply a stable input.

One explicit reference contract is descending score, followed by ascending unique document ID. It selects A, B and C here. That is reproducible when candidates, scores and the ID rule are unchanged, not guaranteed relevance-optimal: the ID rule does not establish that B is more relevant than D. If a product uses a meaningful secondary business score, document the full priority chain and its final unique key.

Avoid silently adding a tiny ID-dependent epsilon to scores. When two genuinely different scores are closer than that perturbation, it can reverse their primary order. A lexicographic score-and-ID key keeps tie handling distinct from the score. A pairwise rule that treats differences below epsilon as equality can also lose transitivity: 0,0.75ε and1.5ε have close neighboring pairs but not close endpoints. If the chosen policy buckets or rounds scores, acknowledge that it redefines which values count as tied and record the bucket rule.

Reference implementation before optimization

The ranker below accepts unique string IDs, finite floating-point scores and 0≤k≤the candidate count. It sorts by (-score,ID), checks all 720 permutations of the six inputs for arrival-order invariance, and enumerates the three possible member sets at the tied boundary.

# Synthetic retrieval ranking; no PyTorch or search-server benchmark.
from itertools import permutations
from fractions import Fraction
from math import isfinite

rows = [('A',9.), ('B',8.), ('C',8.), ('D',8.), ('E',7.), ('F',6.)]
gold = {'A','B','D'}

def rank(rows, k):
    if not 0 <= k <= len(rows):
        raise ValueError('k outside candidate count')
    ids = [doc for doc, score in rows]
    if len(set(ids)) != len(ids):
        raise ValueError('duplicate document ID')
    if not all(isfinite(score) for doc, score in rows):
        raise ValueError('nonfinite score')
    return tuple(doc for doc, score in sorted(rows, key=lambda r: (-r[1],r[0]))[:k])

def recall(ids):
    return Fraction(len(set(ids) & gold), len(gold))

assert rank(rows,3) == ('A','B','C')
assert all(rank(list(p),3) == ('A','B','C') for p in permutations(rows))
sets = {frozenset(['A'] + list(p[:2])) for p in permutations(['B','C','D'])}
assert len(sets) == 3
assert min(map(recall,sets)) == Fraction(2,3)
assert max(map(recall,sets)) == 1
inclusive = {doc for doc,score in rows if score >= 8}
assert len(inclusive) == 4 and recall(inclusive) == 1
assert rank(rows,0) == ()
assert rank(rows,len(rows)) == ('A','B','C','D','E','F')
for bad,k in [(rows,7), ([('A',1.),('A',2.)],1), ([('A',float('nan'))],1)]:
    try:
        rank(bad,k)
    except ValueError:
        continue
    raise AssertionError('invalid input accepted')
print('11 ranking checks passed, including all 720 input permutations')

Eleven checks consist of eight assertions and three invalid-input rejection cases, all executed locally. The program does not call torch.topk, test a GPU kernel or benchmark approximate vector search. For n candidates, full sorting needs O(n log n) comparison-scale work and O(n) auxiliary space; string-comparison cost additionally depends on ID length.

A partial-selection algorithm supporting the same composite key can optimize a large candidate set, but first compare its semantics with this reference. Sorting only the k documents that one topk call already selected cannot recover tied documents excluded at the boundary. If a lower layer returns only a truncated set, the caller generally lacks enough information to reconstruct the entire tied group. It needs a stronger upstream ranking contract or sufficient candidates, rather than a claim that postprocessing repaired the selection.

Including every tie changes the result count

Another interpretable policy retains every candidate whose score is at least the kth score. Here it returns A, B, C and D and achieves recall one, but returns four documents. The policy is legitimate if result counts and metric definitions are reported accurately. It is not directly the same outcome as a system restricted to three returned documents.

Including every tie changes reranking work or context budgets, especially for a large boundary group. If a generator can receive only three passages, a rule for choosing those passages is still required. Moving ambiguity to the next stage does not remove it. Compare experiments under the same final visible-result and resource constraints rather than interpreting extra retrieved documents as an unqualified model improvement.

The earlier RAG permission-filter ordering article concerns candidate eligibility. This article concerns tie handling inside the eligible set. Establish candidates first, fix score and tie contracts second, and compute metrics last. An experiment record should make all three stages traceable.

What evidence reproduces a ranking?

Retain version identifiers for the query and candidate snapshot, candidate IDs, the score representation actually used, k, the secondary key and the relevance-label version. Keep user data only in authorized local records; public examples can use fictional identifiers. Differences in precision or normalization paths should be listed explicitly rather than collectively described as random top-k behavior.

Compare the score sequence, member set and full order separately. Equal scores with different membership point toward a cutoff boundary; equal members with different order require checking whether the metric is order-sensitive. If the candidate sets already differ, return to candidate generation first. This layered diagnosis is more informative than comparing only the final Recall scalar.

If the counterexample, bounds and reference ranker help prevent a misleading retrieval comparison, voluntary support through the section below is welcome. Their value is a ranking contract that can be checked in the next model comparison, rather than a promise that any model will score higher.

Sources and backfill note

torch.topk · torch.sort · Python sorting

Checked against versioned PyTorch 2.8 definitions available before the planned October 20 23:30 Beijing slot. This backfill retains that article date; actual public release time is recorded separately. Derivations and diagrams are original. Standard-library code ran locally, without a PyTorch integration test or device benchmark.