하이브리드 검색을 위한Reciprocal Rank Fusion[RRF]알고리즘

RRF알고리즘

최근 LLM을 이용한 어플리케이션 프로젝트를 진행 중인데 해당 프로젝트에서 중요한 부분 중 하나가 바로 LLM에 관련된 context를 제공하는 일이었습니다. 그러다 보니 검색 성능 향상이 하나의 포인트였고 이를 위해 하이브리드 검색을 위한 RRF 알고리즘에 대해 알아보게 되었습니다. RRF 알고리즘은 두 가지 이상의 검색 결과를 재조합해서 검색 순위를 매기는 하이브리드 알고리즘입니다. 이 알고리즘의 장점은 검색에 이용된 하위 알고리즘들의 성능지표가 서로 다르더라도 상관없이 사용할 수 있다는 것입니다. 그 이유는 알고리즘의 성능 지표에 초점을 맞춘것이 아니라 바로 각 알고리즘에서 검색된 결과의 "순위"에 초점을 맞추기 때문입니다.
아래는 Elasticsearch8.10 vesrion docs에 있는 RRF알고리즘의 동작 방식을 가져온 부분입니다.

score = 0.0
for q in queries:
	if d in result(q):
    	score += 1.0 / ( k + rank( result(q), d ))
return score
# k는 ranking constant로 rrf를 제안한 논문상에서는 60으로 되어있습니다.
# q는 질문들의 집합을 나타냅니다.
# d는 결과 집합의 문서입니다.
# result(q)는 q의 결과
# rank(result(q),d)는 result(q)에서의 d의 순위(rank)입니다.

queries는 검색하는 질문들의 집합으로 사용자의 질의어 정도로 이해했습니다. 그리고 q가 검색엔진을 거쳐서 나오게 되는 결과들을 result(q)로 정의했습니다. 저의 경우에는 특정 질문 q에 대해서 검색되어 나오는 context들의 집합 정도로 이해하면 되겠네요. 마지막으로 d는 하나의 context가 되겠습니다. 이렇게 각 d에 대해서 순위를 고려해 문서(context)의 score를 계산합니다.

예시

검색엔진A의 결과: ["사과", "바나나","포도"]
검색엔진B의 결과: ["바나나","포도","귤"]
(계산의 편의를 위해 rankign constants는 무시했습니다)

Reciprocal Ranks

• 검색엔진A:
  사과: 1/1 =1.0
  바나나: 1/2 = 0.5
  포도: 1/3 = 0.3333~

• 검색엔진B:
  바나나: 1/1 =1.0
  포도: 1/2 = 0.5
  귤: 1/3 = 0.3333~

Sum Reciprocal Ranks

사과: 1.0 + 0 = 1
바나나: 0.5 + 1.0 = 1.5
포도: 0.5 + 0.33 = 0.833
귤: 0 + 0.33 = 0.33

Re-Rank

1. 바나나: 1.5
2. 사과: 1
3. 포도: 0.833
4. 귤: 0.33

피드백은 언제나 환영입니다.