기술 요약: 10억 문서 규모에서의 계층적 BM25 (Hierarchical BM25)

1. 문제 정의

본 논문은 하이브리드 검색 시스템에서 렉시컬 검색(특히 BM25)이 10억 개 규모의 문서에서 직면하는 확장성 병목 현상을 다룹니다. 밀집 검색(Dense Retrieval)은 근사 최근접 이웃(ANN) 인덱스를 사용하여 효율적으로 확장되는 반면, 10억 개의 문서를 대상으로 하는 평면(Flat) BM25 역색인(Inverted Index)은 두 가지 결정적인 실패를 보입니다:

1. 메모리 비용: 평면 인덱스는 약 400 GB를 차지합니다. 이를 전부 DRAM에 유지하는 것은 경제적으로 매우 비효리적이며, 특히 밀집 검색 구조와 메모리를 공유해야 하는 하이브리드 배포 환경에서는 더욱 그렇습니다.
2. 지연 시간(Latency): 디스크에서 평면 인덱스를 서빙할 경우, 다중 용어 쿼리에 대해 막대한 무작위 I/O 팬아웃(Fan-out)이 발생합니다. 이는 검색 증강 파이프라인(RAG)에 필요한 인터랙티브 예산(통상 1초 미만)을 훨씬 초과하는 4~12초의 꼬리 지연 시간(Tail Latency)을 초래합니다.

기존의 동적 프루닝(Pruning) 기술(예: BlockMax-WAND)은 랭크 안전성(Rank-safe, 정확한 top-k 결과 보장)을 갖추고 있지만, 인덱스가 메모리에 상주하거나 빠른 로컬 스토리지에 있다는 것을 전제로 합니다. 10억 개 규모의 문서에서는 데이터 구조 자체가 선형적인 DRAM 증가 없이 메모리에 들어갈 수 없다면, 단순한 프루닝만으로는 불충분합니다.

2. 방법론: 계층적 BM25 (Hierarchical BM25)

제안된 솔루션인 계층적 BM25는 엄격한 랭크 안전성(정확한 top-k 보장)을 희생하는 대신, 메모리와 지연 시간에 대한 고정된 경계치를 달성합니다. 이는 단일 평면 인덱스를 두 단계 구조로 대체합니다:

2.1 2단계 인덱스 구조

• Level-1 (Coarse Index): **약 1,000개의 주제별, 크기가 균형 잡힌 문서 그룹(클러스터)**에 대해 사전 계산된 상주 인덱스입니다. 이 인덱스는 작으며(~4 GB), 전체가 메모리에 적재됩니다. 이는 쿼리가 방문해야 할 클러스터를 선택하는 필터 역할을 합니다.
• Level-2 (Fine Index): 10억 개의 모든 문서를 포함하는 전체 역색인을 포함합니다. 이 인덱스는 완전히 상주하지 않습니다. 대신, **고정된 크기의 캐시(~100만 엔트리, ~400 MB)**를 통해 제공되며, NVMe 스토리지에 의해 백업됩니다. 상주 풋프린트는 코퍼스 성장에 관계없이 일정하게 유지됩니다.

2.2 클러스터 형성 (Level-1 구축)

클러스터는 선택도(Selectivity)와 균형을 보장하기 위한 특정 제약 조건 하에 **잠재 디리클레 할당(LDA)**을 사용하여 형성됩니다:

• 특징 선택(Feature Selection): 클러스터링에는 중간 빈도의 용어(높은 변별력을 가지며, 흔한 불용어 및 희귀 노이즈를 피함)만을 사용합니다.
• 균형 제약(Balance Constraint): "핫(Hot)" 토픽이 거대 클러스터를 생성하여 지연 시간 예산을 깨뜨리는 것을 방지하기 위해, 용량 제한 할당(Capacity-capped assignment) 및 오버플로 분할(Overflow splitting)을 통해 문서를 클러스터에 할당합니다. 이를 통해 약 1,000개의 클러스터가 모두 대략 동일한 크기를 갖도록 보장합니다.
• 점진적 유지보수(Incremental Maintenance): 코퍼스가 성장함에 따라, 글로벌 재클러스터링 없이 이차 토픽 벡터를 기반으로 거대 클러스터를 로컬에서 분할할 수 있습니다.

2.3 쿼리 처리 및 선택 신호

쿼리가 도착하면 시스템은 다음의 2단계 과정을 수행합니다:

1. 조밀한 선택 (Level-1 Coarse Selection): 시스템은 두 가지 신호를 사용하여 ~1,000개의 클서터를 점수화하고, 상위 ~40개의 클러스터를 선택합니다(코퍼스의 ~4% 방문):
   • 집계 신호 (Aggregate Signal, $A$): 클러스터 내 모든 문서에 걸친 쿼리 용어의 IDF 가중치 합계입니다. 이는 단일 용어의 주제 집중도를 포착합니다.
   • 공출현 신호 (Co-occurrence Signal, $B$): "널리 퍼져 있는" 변별력 있는 용어(높은 IDF를 가지지만 여러 클러스터에 흩어져 있음)를 위한 특화된 신호입니다. 이는 특정 용어 집합($T_M$)에 대한 클러스터 태그가 붙은 작은 역색인을 통해, 이러한 용어들이 클러스터 내의 단일 문서 내에서 함께 나타나는지를 추적합니다.
   • 선택 점수: $Score(c,Q) = A(c,Q) + \lambda B(c,Q)$.
2. 정밀 스코어링 (Level-2 Exact Scoring): 선택된 클러스터에 대해서만 전수 조사를 수행합니다. 결정적으로, 문서는 작은(~100 KB) 상주 테이블에 저장된 글로벌 코퍼스 통계(전역 문서 빈도 및 평균 문서 길이)를 사용하여 점수가 매겨집니다. 이를 통해 스코어링되는 모든 문서는 정확한 평면 인덱스 BM25 점수를 받게 되며, 근사는 오직 방문할 클러스터에만 국한됩니다.

3. 주요 기여

본 논문의 세 가지 주요 기여는 다음과 같습니다:

1. 계층적 BM25 아키텍처: 코퍼스 크기와 상주 메모리를 분리하는 2단계 인덱스입니다. 10억 개의 문서에 대해 16개 용어 쿼리 시, 400 GB/4~12초의 베이스라인과 비교하여 고정된 ~4.4 GB 상주 풋프린트와 ~300 ms의 지연 시간을 달성합니다.
2. 교차 클러스터 스코어링 교정 (Cross-Cluster Scoring Correction): 저자들은 클러스터별 로컬 IDF 통계를 사용할 때 발생하는 멀티 클러스터 검색의 정확성 오류를 식별하고 수정했습니다. 이들은 점수를 클러스터 간에 비교 가능하고 정확하게 만들기 위해 전역 DF 테이블을 도입하여, 근사가 오직 클러스터 선택에만 국한되도록 했습니다.
3. BlockMax-WAND와의 분석적 비교: 본 논문은 RAG 파이프라인에서 흔히 발생하는 긴 쿼리(16~32개 용어)의 경우, 클러스터 선택이 WAND 방식의 프루닝보다 더 효과적이라고 주장합니다. WAND는 문서 수준의 다중 용어 공출현에 의존하는데, 이는 쿼리 길이가 길어지고 용어 간 상관관계가 낮아짐에 따라 희소해집니다. 계층적 BM25는 단일 용어의 주제 집중도(신호 A)와 특정 공출현 추적(신호 B)에 의존하며, 이는 쿼리 길이에 관계없이 비용이 제한적입니다.

4. 결과

평가는 10억 개의 문서와 16~32개 용어 쿼리가 있는 단일 노드에서 수행되었습니다:

• 지연 시간 (Latency): 계층적 BM25는 16개 용어 쿼리에 대해 ~300 ms의 지연 시간을 유지하여 1초 예산 내에 머물렀습니다. 이는 평면 멀티스레드 인덱스보다 4.7~5.6배 빠르며, 평면 싱글스레드 인덱스보다는 15~31배 빠릅니다.
• 처리량 (Throughput):
  • 콜드 스타트 (Cold Start): 2.63.5 QPS(싱글스레드)를 지속하며, 평면 베이스라인을 크게 앞섭니다.
  • 캐시 워밍 후 (Warmed Cache): Level-2 캐시가 채워지면 처리량이 ~32 QPS에 도달합니다(평면 인덱싱의 <3 QPS 대비).
• 품질 (500K 문서 구성 기준):
  • 510%의 클러스터를 방문하면 전수 조사 결과 점수의 **0.830.92**를 회복합니다.
  • 방문 비율이 10%로 증가함에 따라 depth 20 및 100에서의 재현율(Recall)이 평면 인덱스의 재현율에 근접합니다.
  • 참고: 10억 규모의 재현율은 직접 측정되지 않았으며, 더 작은 규모의 측정값을 통해 외삽(Extrapolated)되었습니다.

5. 의의 및 주장

본 논문은 계층적 BM25를 하이브리드 검색의 "렉시컬 스케일링" 문제를 해결하기 위한 구조적 솔루션으로 포지셔닝합니다. 그 의의는 다음과 같습니다:

• 하이브리드 파이프라인 활성화: 렉시컬 컴포넌트가 과도한 메모리 비용이나 현재 병목이 되고 있는 지연 시간 페널티 없이 수십억 개의 문서로 확장될 수 있게 합니다.
• 트레이드오프 정당화: 저자들은 인터랙티브 시스템에서 랭크 안전성을 포기하는 것이 실용적인 거래라고 주장합니다. 하이브리드 파이프라인에서 렉시컬 top-k를 밀집 후보들과 병합하고 재순위화(Re-ranking)할 때, 10번째 렉시컬 후보와 11번째 후보를 바꾸는 것은 최종 출력에 거의 영향을 주지 않지만, 4초의 지연 시간은 사용자 경험을 완전히 망가뜨립니다.
• 아키텍처적 통찰: 긴 디스정션(Disjunctive) 쿼리에 대해서는, 선택 메커니즘이 집계적 용어 집중도와 특정 문서 수준의 공출현을 모두 고려한다면, 밀집한 문서 스트림을 프루닝하는 것보다 주제적 클러스터를 선택하는 것이 계산적으로 우월함을 보여줍니다.

6. 한계 및 열린 질문

본 논문은 다음과 같은 사항을 명시하며 자신의 주장에 대해 겸허한 태도를 보입니다:

• 랭크 안전성: BlockMax-WAND와 달리, 계층적 BM25는 랭크 안전(Rank-safe)하지 않습니다. 즉, 정확한 top-k 문서를 반환한다고 보장하지 않습니다.
• 측정되지 않은 10억 규모의 재현율: 품질 지표(nDCG, Recall)는 50만 개 문서에서 측정되었으며 이를 외삽한 것입니다. 자연스러운 어휘를 가진 실제 10억 개 규모의 문서에서의 성능은 아직 검증되지 않았습니다.
• 공출현 신호 (Co-occurrence Signal): 공출현 신호($B$)의 기여도가 경험적으로 완전히 격리되어 입증되지 않았습니다. 현재의 벤치마크는 사용된 쿼리 믹스 덕분에 집계 신호(Signal A)에 크게 의존하고 있습니다.
• 베이스라인 비교: 문서 재정렬(Reordering)을 포함한 BlockMax-WAND와의 직접적인 경험적 비교는 아직 수행되지 않았습니다.
• 어휘 편향 (Vocabulary Bias): 평가에는 인덱스 구조를 테스트하기 위해 압축된 어휘 집합이 사용되었습니다. 자연스럽고 거대한 어휘를 가진 코퍼스에서의 성능은 향후 과제로 남아 있습니다.