RRF (Reciprocal Rank Fusion)

개요

RRF(Reciprocal Rank Fusion, 상호 순위 융합)는 여러 검색 시스템이나 쿼리로부터 얻은 결과를 하나의 통합된 순위로 결합하는 알고리즘이다. 2009년 Gordon V. Cormack, Charles L.A. Clarke, Stefan Buettcher가 발표한 논문¹에서 소개되었다.

RRF는 특히 하이브리드 검색에서 키워드 기반 검색(BM25 등)과 벡터 검색(밀집 벡터 검색)의 결과를 결합할 때 널리 사용된다.

동작 원리

RRF 알고리즘은 다음 과정을 통해 여러 결과를 결합한다:

1. 상호 순위 점수 계산

각 문서의 점수는 다음 공식으로 계산된다:

$$\text{RRF}(d)=\sum _{q\in Q}\frac{1}{k+{\text{rank}}_q(d)}$$

여기서:

• $d$ = 점수를 계산할 문서
• $Q$ = 쿼리 집합 (또는 검색 시스템 집합)
• $k$ = 순위 상수 (일반적으로 60)
• ${\text{rank}}_q(d)$ = 쿼리 $q$의 결과에서 문서 $d$의 순위 (1부터 시작)

2. 점수 집계 및 재정렬

• 각 검색 시스템/쿼리에서 얻은 순위를 기반으로 상호 순위 점수를 계산
• 모든 검색 시스템에 걸쳐 각 문서의 점수를 합산
• 최종 점수를 기준으로 문서를 내림차순 정렬

예시

두 개의 검색 시스템(키워드 검색, 벡터 검색)이 있고, k=60일 때:

키워드 검색 결과:

1. 문서 A (순위 1)
2. 문서 B (순위 2)
3. 문서 C (순위 3)

벡터 검색 결과:

1. 문서 C (순위 1)
2. 문서 A (순위 2)
3. 문서 D (순위 3)

RRF 점수 계산:

• 문서 A: $\frac{1}{60+1}+\frac{1}{60+2}=0.0164+0.0161=0.0325$
• 문서 B: $\frac{1}{60+2}+0=0.0161$
• 문서 C: $\frac{1}{60+3}+\frac{1}{60+1}=0.0159+0.0164=0.0323$
• 문서 D: $0+\frac{1}{60+3}=0.0159$

최종 순위: A → C → B → D

k 상수의 역할

k 값의 의미

상수 $k$는 다음과 같은 역할을 한다:

1. 평활화(Smoothing): 특정 검색 시스템이 결과를 지배하는 것을 방지
2. 순위 간 차이 조절: 낮은 순위의 문서들이 최종 결과에 미치는 영향을 조절

왜 k=60인가?

• 실험적으로 k=60이 가장 좋은 성능을 보임
• k < 60: 상위 1위에 과도하게 집중, 급격한 점수 감소
• k > 60: RRF 점수가 너무 평평해져 순위 구분이 모호해짐

비선형적 감소

$\frac{1}{k+\text{rank}}$ 공식은 순위가 증가할수록 점수가 비선형적으로 감소한다. 이는 다음과 같은 직관을 반영한다:

• 1위와 2위의 관련성 차이 > 100위와 101위의 관련성 차이
• 여러 검색 시스템에서 모두 높은 순위를 받은 문서에 더 높은 가중치 부여

하이브리드 검색에서의 활용

RRF는 하이브리드 검색에서 다음과 같이 활용된다:

희소 벡터 + 밀집 벡터 결합

1. 희소 벡터 검색 (BM25, 학습된 희소 검색 등)

   • 키워드 매칭에 강점
   • 정확한 용어 일치가 중요한 경우 효과적

2. 밀집 벡터 검색 (의미적 벡터 검색)

   • 문맥과 의미 이해에 강점
   • 정확한 키워드가 없어도 관련 문서 검색 가능

3. RRF를 통한 결합

   • 두 검색 방식의 순위를 RRF로 융합
   • 키워드 정확성과 의미적 관련성을 모두 고려한 결과 생성

주요 검색 플랫폼의 RRF 지원

• Elasticsearch: rrf retriever를 통해 렉시컬 검색과 벡터 검색 결합 지원
• OpenSearch: 하이브리드 검색을 위한 RRF 제공
• Azure AI Search: 하이브리드 검색에서 RRF 스코어링 사용
• Google Vertex AI: 토큰 기반 검색과 의미적 검색 결합에 RRF 활용

RRF의 장점

1. 순위 기반 접근

• 점수 정규화 문제 회피: 서로 다른 검색 시스템의 점수 스케일을 통일할 필요 없음
• 순위만 사용하므로 다양한 데이터 소스에서 일관된 처리 가능

2. 강건성(Robustness)

• 여러 소스의 증거를 합산하여 더 견고한 순위 생성
• 단일 검색 시스템의 편향이나 특성에 덜 민감

3. 이상치 저항성

• Min-max 정규화, L2 정규화는 이상치(outlier)에 민감
• RRF는 순위를 집계하므로 극단적인 점수 값이 결과를 왜곡하지 못함

4. 조정 불필요

• 파라미터 튜닝이 거의 필요 없음 (k=60이 일반적으로 잘 작동)
• 서로 다른 검색 시스템의 점수가 관련이 없어도 고품질 결과 생성 가능

Python 구현 예시

def reciprocal_rank_fusion(search_results_list, k=60):
    """
    RRF 알고리즘 구현
 
    Args:
        search_results_list: 각 검색 시스템의 결과 리스트
                            (문서 ID의 리스트들을 담은 리스트)
        k: 순위 상수 (기본값 60)
 
    Returns:
        (문서 ID, RRF 점수) 튜플의 정렬된 리스트
    """
    # 모든 고유 문서 수집
    all_docs = set()
    for results in search_results_list:
        all_docs.update(results)
 
    # 각 문서의 RRF 점수 계산
    doc_scores = {}
    for doc in all_docs:
        score = 0.0
        for results in search_results_list:
            if doc in results:
                rank = results.index(doc) + 1  # 1부터 시작
                score += 1.0 / (k + rank)
        doc_scores[doc] = score
 
    # 점수 기준 내림차순 정렬
    return sorted(doc_scores.items(), key=lambda x: x[1], reverse=True)
 
# 사용 예시
keyword_results = ['doc_a', 'doc_b', 'doc_c']
vector_results = ['doc_c', 'doc_a', 'doc_d']
 
fused_results = reciprocal_rank_fusion([keyword_results, vector_results])
print(fused_results)
# 출력: [('doc_a', 0.0325), ('doc_c', 0.0323), ('doc_b', 0.0161), ('doc_d', 0.0159)]

참고 자료

• Reciprocal Rank Fusion - Elasticsearch
• Hybrid search scoring (RRF) - Azure AI Search
• Implementing Reciprocal Rank Fusion in Python

Footnotes

1. Cormack, G. V., Clarke, C. L., & Buettcher, S. (2009). “Reciprocal rank fusion outperforms condorcet and individual rank learning methods”. SIGIR ‘09: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. ↩