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

Resumen Técnico: Mejora de la Recuperación de Código con BM25 bajo Tokenización Genérica Fija

1. Declaración del Problema

En los sistemas de codificación aumentados por recuperación, un punto crítico de fallo ocurre cuando el archivo fuente relevante está ausente del contexto recuperado. Esto sucede a menudo en regímenes de "tokenización genérica congelada", donde un índice BM25 es construido por una infraestructura de búsqueda (por ejemplo, Lucene, Elasticsearch, Tantivy) utilizando un analizador ajustado para el lenguaje natural en lugar del código. Los profesionales a menudo no pueden modificar este tokenizador.

Bajo estas restricciones, el BM25 estándar falla en distinguir suficientemente entre identificadores únicos de código (por ejemplo, handleWebSocketUpgrade) y tokens comunes y recurrentes. La Inversa de la Frecuencia de Documento (IDF) estándar de Robertson–Spärck-Jones (RSJ) utiliza una función logarítmica: $\log((N - n_t + 0.5)/(n_t + 0.5))$. Debido a que el logaritmo crece lentamente, "sub-separa" la cola de la distribución. Un término que aparece en un solo archivo ($df=1$) y un término que aparece en 50 archivos reciben pesos IDF que difieren por una pequeña constante en lugar de un orden de magnitud. En consecuencia, los archivos "oro" que contienen identificadores únicos a menudo se clasifican por debajo de los archivos "distractores" que comparten unos pocos tokens comunes y no únicos, llenando la ventana de contexto del agente con código irrelevante.

2. Metodología: Odds Logarítmicos q Adaptativos

El artículo propone una solución "lista para usar" que modifica únicamente el logaritmo externo del cálculo IDF de BM25, dejando la saturación de la frecuencia de términos y la tokenización intactas.

• La Transformación: Los autores reemplazan el logaritmo estándar con el logaritmo q de Tsallis (o $q$-log), definido como:
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  La nueva IDF se convierte en:
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  donde $\delta = 0.5$.

• Propiedades Matemáticas:

  • Recuperación de BM25: En $q=1$, la transformación recupera exactamente la IDF clásica de BM25 mediante la regla de L'Hôpital ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • Amplificación de Ley de Potencia: Para $q < 1$, la transformación actúa como una transformación de Box-Cox de las odds RSJ con $\lambda = 1-q$. En el régimen de tokens ultra-raros ($n_t \ll N$), la IDF crece como una ley de potencia ($x^{1-q}$), amplificando significativamente el peso de los hapax de $df=1$ (identificadores únicos) en relación con tokens menos raros.
  • Saturación: Para $q > 1$, la IDF satura, descartando efectivamente la discriminación para tokens raros.

• Implementación: El método requiere únicamente un pase sobre la matriz de puntuaciones dispersa en el momento de la carga del índice para reescalar la columna IDF. La latencia de consulta permanece sin cambios.

3. Contribuciones Clave

1. IDF de Odds RSJ con q-Log: Una deformación de un parámetro de la IDF de BM25 que recupera BM25 exactamente en $q=1$ y actúa como un amplificador de ley de potencia para tokens raros cuando $q < 1$.
2. Límites de Rendimiento de Oráculo: En el corpus CoIR CodeSearchNet Go (182K documentos) con tokenización genérica congelada, ajustar $q$ a $0.05$ mejora el NDCG@10 de 0.2575 a 0.4874 (+89.3% de ganancia relativa). Este resultado es estadísticamente significativo ($p \le 10^{-4}$) con cero inversiones de signo en 10,000 remuestreos de pares bootstrap.
3. Predictor Adaptativo al Corpus: Un predictor de forma cerrada y sin etiquetas $q_{pred} = 1 - 7.28 \cdot h_{tok}$ (donde $h_{tok}$ es la densidad de hapax) que estima el $q$ óptimo a partir de las estadísticas del corpus únicamente. Este predictor logra una recuperación de "uno fuera" de 0.72 y se establece correctamente en $q \approx 1$ para corpus donde BM25 ya es óptimo (por ejemplo, Python).
4. Ablación de Tokenizador: El estudio demuestra que la ganancia de rendimiento de $q$-IDF depende en gran medida del tokenizador. Cuando se utiliza un tokenizador consciente de identificadores (dividiendo handleWebSocketUpgrade en sub-tokens), la ganancia incremental de $q$-IDF colapsa. Esto confirma que el valor del método es específico del régimen de "tokenizador congelado".
5. Proxies Relevantes para Agentes: El método muestra ganancias significativas en Recall@K-tokens (eficiencia de la ventana de contexto), aumentando la probabilidad de que el archivo oro aparezca dentro de un presupuesto de 8K tokens del 48.1% al 68.8% en Go.

4. Resultados Experimentales

• Código vs. Texto: El método produce ganancias masivas en corpus de código con colas pesadas de identificadores (Go, Java, Ruby) pero ganancias cercanas a cero en texto de lenguaje natural (conjuntos de datos BEIR) y Python.
  • Go: $q_{opt} = 0.05$, +89.3% de ganancia en NDCG@10.
  • Java/Ruby: Ganancias positivas significativas ($q_{opt} \approx 0.70-0.90$).
  • Python: $q_{opt} = 1.00$. Los identificadores de Python a menudo son palabras tipo diccionario reutilizadas entre archivos; la señal está en los bins de $df$ media, que el log-IDF estándar ya maneja óptimamente. Desviarse de $q=1$ distorsiona estos bins.
  • BEIR (Texto): Sin ganancia significativa; el método colapsa a BM25 ya que el $q$ de oráculo se sitúa en o por encima de 1.
• Escalado: La ganancia de rendimiento escala de manera monótona con el tamaño del corpus. En Go, la ganancia absoluta aumenta de +0.061 en 1K documentos a +0.227 en 182K documentos.
• Líneas Base: El método $q$-log supera a las reescaladas simples de IDF de ley de potencia ($idf_\gamma$) y a los modelos de Desviación de la Aleatoriedad (DFR-DPH), que fallan en código debido a una normalización de frecuencia de términos mal calibrada.

5. Significado y Alcance

El artículo posiciona este trabajo no como un reemplazo para una tokenización adecuada, sino como una intervención necesaria cuando las restricciones de infraestructura lo impiden.

• Utilidad Práctica: Para profesionales que utilizan clústeres de búsqueda gestionados (Elasticsearch, OpenSearch) donde el analizador es fijo, este método ofrece un cambio de "una línea" en el cálculo IDF que puede casi duplicar la efectividad de la recuperación para la búsqueda de código.
• Mecanismo: La mejora es impulsada por la amplificación de los hapax de $df=1$ (identificadores únicos como handleWebSocketUpgrade), que son los discriminadores principales en la recuperación de código pero que son aplanados por la ponderación logarítmica estándar.
• Limitaciones: Los autores declaran explícitamente que si un operador controla el tokenizador, el mejor enfoque es utilizar un analizador consciente de identificadores y mantener $q=1$. Apilar $q$-IDF sobre una tokenización consciente de identificadores produce retornos insignificantes o negativos. El método también depende del lenguaje; no ofrece beneficio (y potencialmente una ligera degradación) en lenguajes con baja densidad de hapax como Python o PHP a escala completa.

En resumen, el artículo identifica un modo de fallo específico en la recuperación de código bajo tokenización congelada y proporciona una solución matemáticamente fundamentada, de bajo costo y adaptable que restaura el poder discriminatorio de los identificadores únicos sin requerir reindexación ni cambios en el tokenizador.