apache
Why doesn't RRF handle tied scores with equal ranking instead of using positional ranking?
Description
Hello, I have a question about the RRF method in TopDocs and would like to raise this issue.
In the current code:
for (int i = 0; i < topDoc.scoreDocs.length; ++i) { ScoreDoc scoreDoc = topDoc.scoreDocs[i]; int rank = i + 1; double rrfScoreContribution = 1d / Math.addExact(k, rank); rrfScore.compute( new ShardIndexAndDoc(scoreDoc.shardIndex, scoreDoc.doc), (key, score) -> (score == null ? 0 : score) + rrfScoreContribution); }
The rank is unconditionally incremented by 1 (i + 1) based on position. However, when all documents have identical scores (such as search results on keyword fields), this approach could lead to incorrect RRF scores.
I'm curious about why documents with identical scores are not assigned the same rank. Shouldn't tied scores receive equal ranking treatment?
However, when all documents have identical scores (such as search results on keyword fields), this approach could lead to incorrect RRF scores.
I don't think this makes the RRF scores incorrect. RRF is positionally focused and Lucene utilizes segment ordinal & doc ID as tie breakers for duplicate scores.
I agree that using internal doc ID as a tie-breaker for sorting documents with identical scores within a single query result is reasonable. However, I'm concerned about a specific scenario in multi-query RRF fusion.
Consider a case with keyword search + vector search. If all documents from the keyword search have identical scores, but the vector search provides different rankings, shouldn't the RRF scores reflect the vector search rankings rather than arbitrary positional rankings from the keyword search?
Example:
Let's say we have 4 documents (A, B, C, D) and two queries:
Query 1 (Keyword Search) - All tied but sorted by doc ID:
- Doc A: score = 0.16, position = 0 → rank = 1
- Doc B: score = 0.16, position = 1 → rank = 2
- Doc C: score = 0.16, position = 2 → rank = 3
- Doc D: score = 0.16, position = 3 → rank = 4 (pushed down due to doc ID)
Query 2 (Vector Search):
- Doc D: score = 0.9, position = 0 → rank = 1 (best match!)
- Doc A: score = 0.8, position = 1 → rank = 2
- Doc B: score = 0.7, position = 2 → rank = 3
- Doc C: score = 0.6, position = 3 → rank = 4
Current RRF Calculation (k=60):
Document | Query1 Rank | Query2 Rank | RRF Score Calculation | Final Score
---------|-------------|-------------|------------------------------------------|------------
Doc A | 1 | 2 | 1/(60+1) + 1/(60+2) = 0.0164 + 0.0161 = 0.0325
Doc B | 2 | 3 | 1/(60+2) + 1/(60+3) = 0.0161 + 0.0159 = 0.0320
Doc C | 3 | 4 | 1/(60+3) + 1/(60+4) = 0.0159 + 0.0156 = 0.0315
Doc D | 4 | 1 | 1/(60+4) + 1/(60+1) = 0.0156 + 0.0164 = 0.0320
Expected RRF Calculation (if tied scores got equal rank=1):
Document | Query1 Rank | Query2 Rank | RRF Score Calculation | Final Score
---------|-------------|-------------|------------------------------------------|------------
Doc D | 1 | 1 | 1/(60+1) + 1/(60+1) = 0.0164 + 0.0164 = 0.0328 ← Should be #1!
Doc A | 1 | 2 | 1/(60+1) + 1/(60+2) = 0.0164 + 0.0161 = 0.0325
Doc B | 1 | 3 | 1/(60+1) + 1/(60+3) = 0.0164 + 0.0159 = 0.0323
Doc C | 1 | 4 | 1/(60+1) + 1/(60+4) = 0.0164 + 0.0156 = 0.0320
In this example, Doc D should be ranked #1 since it's the best vector match while being tied in keyword search. However, the current implementation ranks Doc A highest due to arbitrary positional ranking, even though Doc D is clearly the better overall match.
This demonstrates how positional ranking for tied scores can lead to suboptimal RRF results that don't properly reflect the true relevance across multiple query types.
Am I missing something or misunderstanding anything here?
I'm happy to see this API being used as it was only added in the last minor release. The change that you are suggested makes sense to me. I'd like to then use doc IDs as a tie-breaker again after computing the RRF score in case there are ties, but I don't expect you to object to that?
One thing that is a bit annoying with your suggestion is that it would be hard to apply to hits sorted by field rather than score. See e.g. how TopDocs#merge needs to handle this, by taking a Sort object when hits are sorted by field. Or maybe we shouldn't care too much and document that this RRF helper should only be used for hits sorted by descending score.
I'm happy to see this API being used as it was only added in the last minor release. The change that you are suggested makes sense to me. I'd like to then use doc IDs as a tie-breaker again after computing the RRF score in case there are ties, but I don't expect you to object to that?
Yes, I completely agree. :D
One thing that is a bit annoying with your suggestion is that it would be hard to apply to hits sorted by field rather than score. See e.g. how
TopDocs#mergeneeds to handle this, by taking aSortobject when hits are sorted by field. Or maybe we shouldn't care too much and document that this RRF helper should only be used for hits sorted by descending score.
Thank you for pointing that out; I hadn't considered this aspect. upon reflection, You're absolutely right about the complexity of handling field-sorted results—it would require knowing which fields were used for sorting to resolve ties correctly, which makes the implementation significantly more complex. That said, what do you think about allowing users to opt into a simpler fallback behavior when scores are null (e.g., when doDocScores is set to false by the user in IndexSearcher)? there might be cases where users want to apply RRF to field-sorted results (e.g., giving more weight to recently added documents or other custom sorting criteria). In such cases, we could assign ranks purely based on position. It's not perfect, but it gives users a way to still apply RRF in score-less contexts with clear trade-offs, as long as it's well documented.