[LLM] 검색 알고리즘 최적화 및 하이브리드 검색(Hybrid Search)

1. 검색 시스템에서의 인덱싱과 쿼리 성능의 트레이드오프

검색 시스템을 설계할 때, 인덱싱 속도(Indexing Speed)와 쿼리 속도(Query Speed)의 균형을 맞추는 것이 중요합니다.

• 인덱스를 자세하게 만들수록 검색 정확도가 향상되지만, 인덱싱 속도가 느려지고 저장 공간이 많이 필요
• 간단한 인덱스를 사용하면 빠르게 검색할 수 있지만, 정확도가 낮아질 가능성 증가

📌 예제: 고객 데이터 검색 시스템

• 고객의 이름과 이메일만 저장하면 검색은 빠르지만, 원하는 고객을 정확히 찾기 어려울 수 있음
• 고객의 이름, 이메일, 전화번호, 관심사까지 저장하면 검색 정확도가 높아지지만, 인덱싱 속도와 저장 공간이 증가

📌 대표적인 인덱싱 기법

✅ HNSW (Hierarchical Navigable Small World) → 높은 정확도, 빠른 검색 속도, 하지만 메모리 사용량 많음

✅ LSH (Locality-Sensitive Hashing) → 빠른 인덱싱 속도, 적은 메모리 사용량, 하지만 검색 정확도가 낮음

📌 성능 평가 기준(ANN-Benchmarks)

다양한 검색 알고리즘을 평가할 때 고려하는 핵심 지표들:

1️⃣ Recall (재현율) → 검색된 문서 중에서 실제 관련 문서의 비율

2️⃣ QPS (Query Per Second) → 초당 처리 가능한 쿼리 수 (트래픽이 높은 시스템에서 중요)

3️⃣ Build Time → 인덱스를 구축하는 데 걸리는 시간 (데이터가 자주 변경되는 시스템에서는 중요한 요소)

4️⃣ Index Size → 인덱스 크기 (저장 공간과 확장성 고려)

---

2. 하이브리드 검색(Hybrid Search): 용어 기반 검색 + 임베딩 기반 검색

✅ 하이브리드 검색(Hybrid Search)란?

• 용어 기반 검색(Term-Based Retrieval)과 임베딩 기반 검색(Embedding-Based Retrieval)을 조합하여 검색 성능을 극대화하는 기법
• 검색을 2단계로 수행하여 속도와 정확도를 모두 확보 가능

📌 하이브리드 검색의 예제

1️⃣ 1단계: 용어 기반 검색 (빠른 후보 검색)

• "Transformer"라는 단어가 포함된 모든 문서를 검색 (BM25, Elasticsearch 활용)2️⃣ 2단계: 임베딩 기반 검색 (의미적 필터링)
• 검색된 문서 중에서 의미적으로 가장 관련성이 높은 문서를 벡터 검색(Vector Search)로 다시 필터링

✅ 병렬 처리(Parallel Processing)도 가능

• 여러 개의 검색 엔진을 동시에 실행하여 다양한 후보 문서를 가져온 후, 최종 랭킹을 조정하는 방식

---

3. 검색 랭킹 최적화: 순위 결합(Reciprocal Rank Fusion, RRF)

하이브리드 검색에서는 서로 다른 검색 결과를 결합하여 최종 랭킹을 결정해야 합니다.

• 용어 기반 검색과 임베딩 기반 검색의 결과가 다를 수 있기 때문

📌 RRF (Reciprocal Rank Fusion) 알고리즘

서로 다른 검색 기법에서 나온 결과의 순위를 결합하여 최종 점수를 계산하는 기법

📌 예제: 두 개의 검색 알고리즘이 서로 다른 순위를 부여한 경우

문서 ID	용어 기반 검색 순위	임베딩 기반 검색 순위
A	1	3
B	2	1
C	3	2

💡 RRF 점수 계산 공식

Score(D)=∑i=1n1k+ri(D)Score(D) = \sum_{i=1}^{n} \frac{1}{k + r_i(D)}

Score(D)=i=1∑nk+ri(D)1

• nnn: 검색 알고리즘 개수 (예: 용어 기반 검색 + 임베딩 기반 검색 = 2)
• ri(D)r_i(D)ri(D): 문서 D의 검색 결과에서의 순위 (Rank)
• DD
• kkk: 작은 숫자 (보통 60을 사용)

📌 예제: 문서 A의 최종 점수 계산 (k=60 사용)

Score(A)=160+1+160+3=161+163≈0.0328Score(A) = \frac{1}{60+1} + \frac{1}{60+3} = \frac{1}{61} + \frac{1}{63} \approx 0.0328

Score(A)=60+11+60+31=611+631≈0.0328

✅ RRF의 장점

• 각 검색 방법의 장점을 결합하여 최적의 결과 제공
• 특정 검색 기법이 오류를 일으키더라도, 다른 검색 기법이 이를 보완 가능
• 기존 검색 시스템에 쉽게 적용 가능

---

4. 검색 알고리즘 평가 및 최적화

📌 RAG 시스템의 검색 성능을 평가하려면?

✅ 1️⃣ 검색 품질 평가 (Evaluate Retrieval Quality)

• 검색된 문서가 쿼리와 얼마나 관련성이 있는지 확인 (Precision, Recall 등)

✅ 2️⃣ 최종 RAG 출력 평가 (Evaluate RAG Output)

• 검색된 정보를 기반으로 생성된 AI 응답의 품질 확인

✅ 3️⃣ 임베딩 모델 평가 (Evaluate Embeddings for Embedding-Based Retrieval)

• 임베딩 모델이 제대로 동작하는지 벡터 유사도를 분석

---

5. 결론: 하이브리드 검색이 미래다!

📌 🔹 검색 시스템 선택 가이드

상황	최적의 검색 방식
빠른 검색이 필요할 때	용어 기반 검색 (BM25, Elasticsearch)
의미적으로 유사한 문서를 찾을 때	임베딩 기반 검색 (FAISS, HNSW)
정확도와 속도를 모두 고려할 때	하이브리드 검색 (Hybrid Search)

미래의 검색 시스템은 "하이브리드 검색"과 "순위 결합(RRF)"을 통해 더욱 정교해질 것이다!