Rank Fusion #1 - RRF 알고리즘 공부

안녕하세요. 추석을 쇠고 오니 몸도(?) 마음도 풍족해진 것 같습니다.

 

그런데 정신 차려보니 2026년이 100일도 안 남았더라고요 ㄷㄷㄷ

12월에는 올 한해를 어떻게 기억하고 있을지 기대되네요 :)

 

이번에는 Rank Fusion에서 많이 사용되는 Reciprocal Rank Fusion(RRF) 알고리즘에 대해 공부한 내용을 정리하려고 합니다.

• CORMACK, Gordon V.; CLARKE, Charles LA; BUETTCHER, Stefan. Reciprocal rank fusion outperforms condorcet and individual rank learning methods. In: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. 2009. p. 758-759.
• https://dl.acm.org/doi/pdf/10.1145/1571941.1572114

 

2009년에 발표된 2장짜리 short paper지만 RAG에도 사용되는 등 단순하고 강력한 알고리즘입니다!

---

1. RRF 알고리즘이란

검색 혹은 Retrieval 단계에서는 여러 소스를 사용하는 것이 일반적입니다.

• 소스라는 것은 Elastic Search, Milvus 등의 인프라 레벨에서 다를 수도 있고
• '사람들이 많이 본', '리뷰가 많은' 정도로 풀이 다른 수준일 수도 있습니다.

 

사용자에게 어떤 항목이 적절할지 알 수 없기 때문에 일단 다양하게 조회하는 것인데요.

여기서 문제가 생깁니다.

 

어떤 항목들을 상위에 보여줘야 할까요?

앞서 말씀드렸던 것처럼 여러 소스에서 데이터를 조회했기 때문 결과의 정확도를 비교하는 것부터가 문제입니다.

 

어떤 소스는 BM25 알고리즘을 사용했고, 어떤 소스는 벡터 검색을 사용했다면 두 소스 간의 점수를 정규화 하는 과정이 필요합니다.

 

정규화 과정은 생각보다 복잡한 작업인데 RRF 알고리즘은 이 복잡함을 단순하게 해결합니다.

 

RRF 점수를 계산하는 식부터가 단순합니다. 각 소스들에서 얼마나 상위였는지에만 의미를 두는 것인데요.

참고: Reciprocal Rank Fusion outperforms Condorcet and Individual Rank Learning Methods

 

A, B, C 소스가 있고, 항목 1, 2, 3이 있을 때 조회 결과가 다음과 같다고 하면

	항목1	항목2	항목3
A	1등	2등	3등
B	1등	3등	2등
C	2등	3등	1등

 

항목 1, 2, 3의 RRF 점수는 아래와 같이 계산됩니다.

• 항목1 = 1/(60+1) + 1/(60+1) + 1/(60+2)
• 항목2 = 1/(60+2) + 1/(60+3) + 1/(60+3)
• 항목3 = 1/(60+3) + 1/(60+2) + 1/(60+1)
• k는 특정 소스에서의 순위가 너무 큰 영향을 주는 것을 막기 위해 설정하는 상수인데 원문에서 k=60 일 때 거의 최적이었다고 작성되어 있어서 60을 바로 대입했습니다.

참고: Reciprocal Rank Fusion outperforms Condorcet and Individual Rank Learning Methods

 

이렇게 간단한 알고리즘의 성능이 상당히 좋다고 합니다...!

 

2. 왜 좋지?

이 간단한 알고리즘이 왜 좋을까요? 다음에는 이걸 공부해보려고 합니다.