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

技術概要：固定された汎用トークナイゼーション下での BM25 コード検索の改善

1. 問題定義

検索拡張型コーディングシステムにおいて、関連するソースファイルが検索コンテキストから欠落することが重大な失敗点となります。これは、Lucene、Elasticsearch、Tantivy などの検索インフラが自然言語向けにチューニングされたアナライザーを使用して BM25 インデックスを構築する「凍結された汎用トークナイゼーション」環境で頻繁に発生します。実務者は、このトークナイザーを修正できないことが多くあります。

これらの制約下では、標準的な BM25 は、一意のコード識別子（例：handleWebSocketUpgrade）と一般的で反復的に現れるトークンの間で十分に区別できません。標準的なロバートソン・スパーク・ジョーンズ（RSJ）逆文書頻度（IDF）は、対数関数 $\log((N - n_t + 0.5)/(n_t + 0.5))$ を使用します。対数は緩やかに増加するため、分布の尾部を「過小に分離」してしまいます。1 つのファイルにのみ出現する用語（$df=1$）と 50 のファイルに出現する用語の IDF 重みは、桁違いではなく、わずかな定数の差しか生じません。その結果、一意の識別子を含む「ゴールド」ファイルは、いくつかの一般的で一意ではないトークンを共有する「ディストラクター」ファイルよりも低い順位にランク付けされることが多く、エージェントのコンテキストウィンドウが関連性の低いコードで埋め尽くされます。

2. 手法：適応的 q-Log オッズ

本論文は、BM25 の IDF 計算における外側の対数部分のみを変更し、用語頻度の飽和とトークナイゼーションは変更しない「ドロップイン」型の修正を提案します。

• 変換: 著者らは、標準的な対数をTsallis q-対数（または $q$-log）に置き換えます。これは以下のように定義されます：
  $$\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 は飽和し、稀なトークンの識別能力を実質的に排除します。

• 実装: この手法は、インデックス読み込み時にスパーススコア行列を 1 回走査して IDF 列を再スケーリングするだけで済み、クエリレイテンシーは変化しません。

3. 主要な貢献

1. q-Log 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%）。この結果は統計的に有意（$p \le 10^{-4}$）であり、10,000 回のペア・ブートストラップ再サンプリングにおいて符号の逆転は 0 回でした。
3. コーパス適応型予測子: コーパス統計のみから最適な $q$ を推定する、閉形式のラベルフリー予測子 $q_{pred} = 1 - 7.28 \cdot h_{tok}$（ここで $h_{tok}$ はハパクス密度）。この予測子は、言語を 1 つずつ除外した回復率で 0.72 を達成し、BM25 がすでに最適であるコーパス（例：Python）では $q \approx 1$ に適切にデフォルトします。
4. トークナイザーアブレーション: この研究は、$q$-IDF による性能向上が主にトークナイザーに依存することを示しています。識別子対応型トークナイザー（handleWebSocketUpgrade をサブトークンに分割するもの）を使用する場合、$q$-IDF による追加的な利益は崩壊します。これは、この手法の価値が「凍結されたトークナイザー」環境に固有であることを確認するものです。
5. エージェント関連プロキシ: この手法は、Recall@K-tokens（コンテキストウィンドウ効率）において顕著な向上を示し、Go 言語において 8K トークンの予算内でゴールドファイルが出現する確率を 48.1% から 68.8% に増加させました。

4. 実験結果

• コード対テキスト: この手法は、識別子の尾部が重いコードコーパス（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 の識別子は、ファイル間で再利用される辞書的な単語であることが多く、信号は中間-$df$ バインにあります。これは標準的な log-IDF がすでに最適に処理しています。$q=1$ から逸脱すると、これらのバインが歪められます。
  • BEIR（テキスト）: 有意な利益なし；オラクル $q$ が 1 以上にあるため、この手法は BM25 に収束します。
• スケーリング: 性能向上はコーパスサイズに対して単調にスケーリングします。Go において、絶対的な利益は 1K ドキュメントで +0.061 から 182K ドキュメントで +0.227 に増加します。
• ベースライン: $q$-log 手法は、単純なべき乗則 IDF 再スケーリング（$idf_\gamma$）や、用語頻度正規化の誤較正によりコードで失敗する発散ランダムモデル（DFR-DPH）を上回ります。

5. 意義と範囲

本論文は、この作業を適切なトークナイゼーションの代替としてではなく、インフラの制約によりそれが不可能な場合に必要となる介入として位置づけています。

• 実用性: アナライザーが固定されているマネージド検索クラスター（Elasticsearch、OpenSearch）を使用する実務者にとって、この手法は IDF 計算への「1 行」の変更を提供し、コード検索の検索効率をほぼ倍増させる可能性があります。
• メカニズム: 改善は、$df=1$ のハパクス（handleWebSocketUpgrade のような一意の識別子）の増幅によって駆動されます。これらはコード検索における主要な識別子ですが、標準的な対数重み付けによって平坦化されます。
• 限界: 著者は明示的に、オペレーターがトークナイザーを制御できる場合、最善のアプローチは識別子対応型アナライザーを使用し、$q=1$ を維持することであると述べています。識別子対応型トークナイゼーションの上に $q$-IDF を積み重ねても、利益は無視できるか、あるいは負になります。また、この手法は言語依存性があり、Python や PHP のようにハパクス密度が低い言語では、フルスケールで利益をもたらさず（場合によってはわずかな劣化をもたらす可能性があります）。

要約すると、本論文は凍結されたトークナイゼーション下でのコード検索における特定の失敗モードを特定し、再インデックス化やトークナイザーの変更を必要とせずに一意の識別子の識別力を回復する、数学的に裏付けられた低コストかつ適応的な解決策を提供しています。