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

Résumé Technique : Amélioration de la Récupération de Code par BM25 sous Tokenisation Générique Fixe

1. Énoncé du Problème

Dans les systèmes de codage augmentés par la récupération, un point de défaillance critique survient lorsque le fichier source pertinent est absent du contexte récupéré. Cela se produit souvent dans les régimes de « tokenisation générique figée », où un index BM25 est construit par une infrastructure de recherche (par exemple, Lucene, Elasticsearch, Tantivy) à l'aide d'un analyseur calibré pour le langage naturel plutôt que pour le code. Les praticiens ne peuvent souvent pas modifier ce tokenizer.

Sous ces contraintes, le BM25 standard échoue à distinguer suffisamment les identifiants de code uniques (par exemple, handleWebSocketUpgrade) des tokens communs et récurrents. L'Inversion de Fréquence de Document (IDF) standard de Robertson–Spärck-Jones (RSJ) utilise une fonction logarithmique : $\log((N - n_t + 0.5)/(n_t + 0.5))$. Comme le logarithme croît lentement, il « sous-sépare » la queue de la distribution. Un terme apparaissant dans un seul fichier ($df=1$) et un terme apparaissant dans 50 fichiers reçoivent des poids IDF qui diffèrent par une petite constante plutôt que par un ordre de grandeur. Par conséquent, les fichiers « or » contenant des identifiants uniques sont souvent classés en dessous des fichiers « distracteurs » qui partagent quelques tokens communs et non uniques, remplissant la fenêtre de contexte de l'agent avec du code non pertinent.

2. Méthodologie : Log-Odds Adaptatifs q

L'article propose une correction « plug-and-play » qui modifie uniquement le logarithme externe du calcul IDF de BM25, laissant la saturation de la fréquence des termes et la tokenisation intactes.

• La Transformation : Les auteurs remplacent le logarithme standard par le q-logarithme de Tsallis (ou $q$-log), défini par :
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  Le nouvel IDF devient :
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  où $\delta = 0.5$.

• Propriétés Mathématiques :

  • Récupération de BM25 : À $q=1$, la transformation récupère exactement l'IDF BM25 classique via la règle de L'Hôpital ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • Amplification de Loi de Puissance : Pour $q < 1$, la transformation agit comme une transformation Box-Cox des cotes RSJ avec $\lambda = 1-q$. Dans le régime des tokens ultra-rares ($n_t \ll N$), l'IDF croît selon une loi de puissance ($x^{1-q}$), amplifiant considérablement le poids des hapax $df=1$ (identifiants uniques) par rapport aux tokens moins rares.
  • Saturation : Pour $q > 1$, l'IDF sature, rejetant efficacement la discrimination pour les tokens rares.

• Implémentation : La méthode ne nécessite qu'un seul passage sur la matrice de scores épars au moment du chargement de l'index pour redimensionner la colonne IDF. La latence de requête reste inchangée.

3. Contributions Clés

1. IDF des cotes RSJ q-Log : Une déformation à un paramètre de l'IDF BM25 qui récupère exactement BM25 à $q=1$ et agit comme un amplificateur de loi de puissance pour les tokens rares lorsque $q < 1$.
2. Bornes de Performance Oracle : Sur le corpus CoIR CodeSearchNet Go (182K documents) avec tokenisation générique figée, le réglage de $q$ à $0.05$ améliore le NDCG@10 de 0,2575 à 0,4874 (+89,3 % de gain relatif). Ce résultat est statistiquement significatif ($p \le 10^{-4}$) avec zéro inversion de signe dans 10 000 rééchantillonnages bootstrap appariés.
3. Prédicteur Adaptatif au Corpus : Un prédicteur en forme close et sans étiquette $q_{pred} = 1 - 7,28 \cdot h_{tok}$ (où $h_{tok}$ est la densité d'hapax) qui estime le $q$ optimal à partir des statistiques du corpus uniquement. Ce prédicteur atteint une récupération leave-one-language-out de 0,72 et revient par défaut correctement à $q \approx 1$ pour les corpus où BM25 est déjà optimal (par exemple, Python).
4. Ablation du Tokenizer : L'étude démontre que le gain de performance de l'q-IDF dépend largement du tokenizer. Lorsqu'un tokenizer sensible aux identifiants (divisant handleWebSocketUpgrade en sous-tokens) est utilisé, le gain incrémental de l'q-IDF s'effondre. Cela confirme que la valeur de la méthode est spécifique au régime de « tokenizer figé ».
5. Proxies Pertinents pour l'Agent : La méthode montre des gains significatifs en Rappel@K-tokens (efficacité de la fenêtre de contexte), augmentant la probabilité que le fichier or apparaisse dans un budget de 8K tokens de 48,1 % à 68,8 % sur Go.

4. Résultats Expérimentaux

• Code vs Texte : La méthode produit des gains massifs sur les corpus de code avec des queues d'identifiants lourdes (Go, Java, Ruby) mais des gains quasi nuls sur le texte en langage naturel (jeux de données BEIR) et Python.
  • Go : $q_{opt} = 0,05$, +89,3 % de gain NDCG@10.
  • Java/Ruby : Gains positifs significatifs ($q_{opt} \approx 0,70-0,90$).
  • Python : $q_{opt} = 1,00$. Les identifiants de Python sont souvent des mots de type dictionnaire réutilisés à travers les fichiers ; le signal se trouve dans les bins de $df$ intermédiaires, que l'IDF logarithmique standard gère déjà de manière optimale. S'écarter de $q=1$ déforme ces bins.
  • BEIR (Texte) : Aucun gain significatif ; la méthode s'effondre vers BM25 car l'oracle $q$ se situe à 1 ou au-dessus.
• Mise à l'échelle : Le gain de performance évolue de manière monotone avec la taille du corpus. Sur Go, le gain absolu passe de +0,061 à 1K documents à +0,227 à 182K documents.
• Lignes de Base : La méthode q-log surpasse les redimensionnements simples de loi de puissance de l'IDF ($idf_\gamma$) et les modèles de Divergence du Hasard (DFR-DPH), qui échouent sur le code en raison d'une normalisation de la fréquence des termes mal calibrée.

5. Signification et Portée

L'article positionne ce travail non pas comme un remplacement d'une tokenisation appropriée, mais comme une intervention nécessaire lorsque les contraintes d'infrastructure l'empêchent.

• Utilité Pratique : Pour les praticiens utilisant des clusters de recherche gérés (Elasticsearch, OpenSearch) où l'analyseur est fixe, cette méthode offre un changement « d'une ligne » dans le calcul IDF qui peut presque doubler l'efficacité de la récupération pour la recherche de code.
• Mécanisme : L'amélioration est pilotée par l'amplification des hapax $df=1$ (identifiants uniques comme handleWebSocketUpgrade), qui sont les principaux discriminateurs dans la récupération de code mais sont aplatis par le pondération logarithmique standard.
• Limites : Les auteurs déclarent explicitement que si un opérateur contrôle le tokenizer, la meilleure approche est d'utiliser un analyseur sensible aux identifiants et de maintenir $q=1$. Empiler l'q-IDF sur une tokenisation sensible aux identifiants produit des rendements négligeables ou négatifs. La méthode est également dépendante de la langue ; elle n'offre aucun avantage (et potentiellement une légère dégradation) sur les langues à faible densité d'hapax comme Python ou PHP à pleine échelle.

En résumé, l'article identifie un mode de défaillance spécifique dans la récupération de code sous tokenisation figée et fournit une solution mathématiquement fondée, peu coûteuse et adaptative qui restaure le pouvoir discriminant des identifiants uniques sans nécessiter de réindexation ni de modification du tokenizer.