Improving BM25 Code Retrieval Under Fixed Generic Tokenization: Adaptive q-Log Odds as a Drop-In BM25 Fix

기술 요약: 고정된 범용 토크나이저 하에서 BM25 코드 검색 성능 개선

1. 문제 정의

검색 증강 코딩 시스템에서 중요한 실패 지점은 관련 소스 파일이 검색된 컨텍스트에 누락될 때 발생합니다. 이는 종종 "동결된 범용 토크나이징(frozen generic tokenization)" 환경에서 발생하는데, 여기서 BM25 인덱스는 Lucene, Elasticsearch, Tantivy와 같은 검색 인프라가 자연어에 맞춰 조정된 분석기를 사용하여 코드 대신 구축됩니다. 실무자들은 종종 이 토크나이저를 수정할 수 없습니다.

이러한 제약 하에서 표준 BM25는 고유한 코드 식별자 (예: handleWebSocketUpgrade) 와 일반적이고 반복되는 토큰 사이를 충분히 구별하지 못합니다. 표준 Robertson–Spärck-Jones (RSJ) 역문서빈도 (IDF) 는 로그 함수 $\log((N - n_t + 0.5)/(n_t + 0.5))$를 사용합니다. 로그 함수는 천천히 증가하므로 분포의 꼬리 부분을 "과소 분리"합니다. 단일 파일에 나타나는 용어 ($df=1$) 와 50 개 파일에 나타나는 용어는 몇 배의 차이보다 작은 상수만큼만 IDF 가중치가 달라집니다. 결과적으로 고유한 식별자를 포함하는 "골드" 파일은 몇 개의 일반적이고 고유하지 않은 토큰을 공유하는 "방해" 파일보다 낮은 순위로 배치되어, 에이전트의 컨텍스트 윈도우가 관련 없는 코드로 채워지게 됩니다.

2. 방법론: 적응형 q-로그 오즈

본 논문은 BM25 IDF 계산의 외부 로그 부분만 수정하고, 용어 빈도 포화 및 토크나이징은 변경하지 않는 "드롭인(drop-in)" 수정책을 제안합니다.

• 변환: 저자들은 표준 로그를 Tsallis q-로그 (또는 $q$-로그) 로 대체합니다. 이는 다음과 같이 정의됩니다:
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  새로운 IDF 는 다음과 같습니다:
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  여기서 $\delta = 0.5$입니다.

• 수학적 특성:

  • BM25 복원: $q=1$에서 변환은 로피탈의 법칙을 통해 기존 BM25 IDF 를 정확히 복원합니다 ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • 멱법칙 증폭: $q < 1$인 경우, 변환은 $\lambda = 1-q$인 RSJ 오즈의 Box-Cox 변환으로 작용합니다. 초희소 토큰 ($n_t \ll N$) 영역에서 IDF 는 멱법칙 ($x^{1-q}$) 으로 증가하여, 덜 희소한 토큰에 비해 $df=1$인 하팍스 (고유 식별자) 의 가중치를 크게 증폭시킵니다.
  • 포화: $q > 1$인 경우, IDF 는 포화되어 희소 토큰에 대한 구별력을 사실상 제거합니다.

• 구현: 이 방법은 인덱스 로드 시 희소 점수 행렬을 한 번만 순회하여 IDF 열을 재조정하면 되므로, 쿼리 지연 시간은 변하지 않습니다.

3. 주요 기여

1. q-로그 RSJ-오즈 IDF: $q=1$에서 BM25 를 정확히 복원하고 $q < 1$일 때 희소 토큰에 대해 멱법칙 증폭기로 작용하는 BM25 IDF 의 단일 매개변수 변형입니다.
2. 오라클 성능 한계: 동결된 범용 토크나이징을 적용한 CoIR CodeSearchNet Go 코퍼스 (182K 문서) 에서 $q$를 0.05 로 조정하면 NDCG@10 이 0.2575 에서 0.4874 로 향상되어 상대적 이득이 89.3% 증가합니다. 이 결과는 10,000 개의 쌍 부트스트랩 리샘플링에서 부호 반전이 전혀 없으며 통계적으로 유의미합니다 ($p \le 10^{-4}$).
3. 코퍼스 적응형 예측기: $q_{pred} = 1 - 7.28 \cdot h_{tok}$ (여기서 $h_{tok}$는 하팍스 밀도) 형태의 폐쇄형 라벨 없는 예측기는 코퍼스 통계만으로 최적의 $q$를 추정합니다. 이 예측기는 언어별 제외 (leave-one-language-out) 복원률 0.72 를 달성하며, BM25 가 이미 최적인 코퍼스 (예: Python) 에서는 $q \approx 1$로 자동으로 기본값을 설정합니다.
4. 토크나이저 애블레이션: 이 연구는 $q$-IDF 의 성능 향상이 주로 토크나이저에 의존함을 보여줍니다. 식별자 인식 토크나이저 (handleWebSocketUpgrade를 서브토큰으로 분할) 를 사용할 경우, $q$-IDF 로 인한 추가 이득은 무너집니다. 이는 방법론의 가치가 "동결된 토크나이저" 환경에 특화되어 있음을 확인시켜 줍니다.
5. 에이전트 관련 대리 지표: 이 방법은 Recall@K-tokens(컨텍스트 윈도우 효율성) 에서 유의미한 향상을 보여주며, Go 언어에서 8K 토큰 예산 내 골드 파일이 나타날 확률을 48.1% 에서 68.8% 로 높입니다.

4. 실험 결과

• 코드 vs 텍스트: 이 방법은 식별자 꼬리가 두드러진 코드 코퍼스 (Go, Java, Ruby) 에서는 막대한 이득을 주지만, 자연어 텍스트 (BEIR 데이터셋) 와 Python 에서는 거의 이득이 없습니다.
  • Go: $q_{opt} = 0.05$, NDCG@10 이 89.3% 증가.
  • Java/Ruby: 유의미한 양의 이득 ($q_{opt} \approx 0.70-0.90$).
  • Python: $q_{opt} = 1.00$. Python 의 식별자는 파일 간에 재사용되는 사전 같은 단어인 경우가 많으며, 신호는 표준 로그-IDF 가 이미 최적화하여 처리하는 중간-$df$구간에 있습니다.$q=1$에서 벗어나면 이러한 구간이 왜곡됩니다.
  • BEIR (텍스트): 유의미한 이득 없음; 오라클 $q$가 1 이상에 위치함에 따라 방법이 BM25 로 수렴합니다.
• 확장성: 성능 향상은 코퍼스 크기에 따라 단조롭게 증가합니다. Go 의 경우 절대적 이득은 1K 문서에서 +0.061 에서 182K 문서에서 +0.227 로 증가합니다.
• 베이스라인: $q$-로그 방법은 단순 멱법칙 IDF 재조정 ($idf_\gamma$) 과 Divergence-from-Randomness (DFR-DPH) 모델보다 우월합니다. 후자들은 용어 빈도 정규화 오보정 문제로 인해 코드에서 실패합니다.

5. 중요성 및 범위

본 논문은 이 작업을 적절한 토크나이징을 대체하는 것이 아니라, 인프라 제약으로 인해 그것이 불가능할 때 필요한 개입으로 위치시킵니다.

• 실용적 유용성: 분석기가 고정된 관리형 검색 클러스터 (Elasticsearch, OpenSearch) 를 사용하는 실무자들에게 이 방법은 IDF 계산에 "한 줄"의 변경만으로도 코드 검색의 검색 효과를 거의 두 배로 높일 수 있는 방법을 제공합니다.
• 메커니즘: 개선은 $df=1$인 하팍스 (예: handleWebSocketUpgrade와 같은 고유 식별자) 의 증폭에 의해 주도됩니다. 이들은 코드 검색의 주요 구별 요소이지만 표준 로그 가중치에 의해 평탄화됩니다.
• 한계점: 저자들은 운영자가 토크나이저를 제어할 수 있다면, 식별자 인식 분석기를 사용하고 $q=1$로 유지하는 것이 최선이라고 명시합니다. 식별자 인식 토크나이징 위에 $q$-IDF 를 쌓아도 미미하거나 부정적인 결과만 초래합니다. 또한 이 방법은 언어에 의존적이며, Python 이나 PHP 와 같이 하팍스 밀도가 낮은 언어의 전체 규모에서는 이득이 없거나 (심지어 약간의 저하가 있을 수 있음) 오히려 해가 될 수 있습니다.

요약하자면, 본 논문은 동결된 토크나이징 하의 코드 검색에서 발생하는 특정 실패 모드를 식별하고, 재인덱싱이나 토크나이저 변경 없이 고유 식별자의 구별력을 복원하는 수학적 기반을 갖춘 저비용 적응형 솔루션을 제시합니다.