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

Resumo Técnico: Melhoria na Recuperação de Código BM25 Sob Tokenização Genérica Fixa

1. Declaração do Problema

Em sistemas de codificação aumentados por recuperação, um ponto crítico de falha ocorre quando o arquivo de origem relevante está ausente no contexto recuperado. Isso frequentemente acontece em regimes de "tokenização genérica congelada", onde um índice BM25 é construído por uma infraestrutura de busca (por exemplo, Lucene, Elasticsearch, Tantivy) usando um analisador ajustado para linguagem natural e não para código. Os praticantes frequentemente não podem modificar esse tokenizador.

Sob essas restrições, o BM25 padrão falha em distinguir suficientemente identificadores de código únicos (por exemplo, handleWebSocketUpgrade) de tokens comuns e recorrentes. A Frequência Inversa de Documento (IDF) Robertson–Spärck-Jones (RSJ) padrão usa uma função logarítmica: $\log((N - n_t + 0.5)/(n_t + 0.5))$. Como o logaritmo cresce lentamente, ele "subsepara" a cauda da distribuição. Um termo que aparece em um único arquivo ($df=1$) e um termo que aparece em 50 arquivos recebem pesos IDF que diferem por uma pequena constante em vez de uma ordem de magnitude. Consequentemente, arquivos "ouro" contendo identificadores únicos são frequentemente classificados abaixo de arquivos "distratores" que compartilham alguns tokens comuns e não únicos, preenchendo a janela de contexto do agente com código irrelevante.

2. Metodologia: Odds Logarítmicos q Adaptativos

O artigo propõe uma correção "plug-and-play" que modifica apenas o logaritmo externo do cálculo de IDF do BM25, deixando a saturação de frequência de termos e a tokenização intactas.

• A Transformação: Os autores substituem o logaritmo padrão pelo logaritmo q de Tsallis (ou $q$-log), definido como:
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  O novo IDF torna-se:
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  onde $\delta = 0.5$.

• Propriedades Matemáticas:

  • Recuperação do BM25: Em $q=1$, a transformada recupera exatamente o IDF clássico do BM25 via regra de L'Hôpital ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • Amplificação Lei de Potência: Para $q < 1$, a transformada atua como uma transformada Box-Cox das odds RSJ com $\lambda = 1-q$. No regime de tokens ultra-raros ($n_t \ll N$), o IDF cresce como uma lei de potência ($x^{1-q}$), amplificando significativamente o peso de hapax $df=1$ (identificadores únicos) em relação a tokens menos raros.
  • Saturação: Para $q > 1$, o IDF satura, descartando efetivamente a discriminação para tokens raros.

• Implementação: O método requer apenas uma passagem sobre a matriz de pontuação esparsa no momento da carga do índice para reescalar a coluna IDF. A latência de consulta permanece inalterada.

3. Contribuições Principais

1. IDF de Odds RSJ-q-Log: Uma deformação de um parâmetro do IDF do BM25 que recupera o BM25 exatamente em $q=1$ e atua como um amplificador de lei de potência para tokens raros quando $q < 1$.
2. Limites de Desempenho Oracle: No corpus CoIR CodeSearchNet Go (182K documentos) com tokenização genérica congelada, ajustar $q$ para $0.05$ melhora o NDCG@10 de 0,2575 para 0,4874 (+89,3% de ganho relativo). Este resultado é estatisticamente significativo ($p \le 10^{-4}$) com zero reversões de sinal em 10.000 reamostragens bootstrap pareadas.
3. Preditor Adaptativo ao Corpus: Um preditor de forma fechada e sem rótulos $q_{pred} = 1 - 7.28 \cdot h_{tok}$ (onde $h_{tok}$ é a densidade de hapax) que estima o $q$ ótimo apenas a partir de estatísticas do corpus. Este preditor alcança uma recuperação leave-one-language-out de 0,72 e define corretamente o padrão para $q \approx 1$ para corpora onde o BM25 já é ótimo (por exemplo, Python).
4. Ablação de Tokenizador: O estudo demonstra que o ganho de desempenho do $q$-IDF é largamente contingente ao tokenizador. Quando um tokenizador consciente de identificadores (dividindo handleWebSocketUpgrade em sub-tokens) é usado, o ganho incremental do $q$-IDF colapsa. Isso confirma que o valor do método é específico ao regime de "tokenizador congelado".
5. Proxies Relevantes para Agentes: O método mostra ganhos significativos em Recall@K-tokens (eficiência da janela de contexto), aumentando a probabilidade do arquivo ouro aparecer dentro de um orçamento de 8K tokens de 48,1% para 68,8% em Go.

4. Resultados Experimentais

• Código vs. Texto: O método produz ganhos massivos em corpora de código com caudas pesadas de identificadores (Go, Java, Ruby), mas ganhos próximos de zero em texto de linguagem natural (conjuntos de dados BEIR) e Python.
  • Go: $q_{opt} = 0.05$, +89,3% de ganho no NDCG@10.
  • Java/Ruby: Ganhos positivos significativos ($q_{opt} \approx 0.70-0.90$).
  • Python: $q_{opt} = 1.00$. Os identificadores do Python são frequentemente palavras tipo dicionário reutilizadas em vários arquivos; o sinal está nos bins de $df$ intermediários, que o log-IDF padrão já lida de forma ótima. Desviar de $q=1$ distorce esses bins.
  • BEIR (Texto): Nenhum ganho significativo; o método colapsa para o BM25 à medida que o $q$ oracle fica em ou acima de 1.
• Escala: O ganho de desempenho escala monotonicamente com o tamanho do corpus. Em Go, o ganho absoluto aumenta de +0,061 em 1K documentos para +0,227 em 182K documentos.
• Baselines: O método $q$-log supera simples reescalonamentos de IDF de lei de potência ($idf_\gamma$) e modelos de Divergência do Aleatório (DFR-DPH), que falham em código devido à normalização de frequência de termos mal calibrada.

5. Significado e Escopo

O artigo posiciona este trabalho não como uma substituição para a tokenização adequada, mas como uma intervenção necessária quando restrições de infraestrutura a impedem.

• Utilidade Prática: Para praticantes usando clusters de busca gerenciados (Elasticsearch, OpenSearch) onde o analisador é fixo, este método oferece uma mudança de "uma linha" no cálculo do IDF que pode quase dobrar a eficácia da recuperação para busca de código.
• Mecanismo: A melhoria é impulsionada pela amplificação de hapax $df=1$ (identificadores únicos como handleWebSocketUpgrade), que são os principais discriminadores na recuperação de código, mas são achatados pela ponderação logarítmica padrão.
• Limitações: Os autores afirmam explicitamente que, se um operador controlar o tokenizador, a melhor abordagem é usar um analisador consciente de identificadores e manter $q=1$. Empilhar $q$-IDF sobre tokenização consciente de identificadores produz retornos negligenciáveis ou negativos. O método também é dependente de linguagem; não oferece benefício (e potencialmente uma leve degradação) em linguagens com baixa densidade de hapax como Python ou PHP em escala total.

Em resumo, o artigo identifica um modo de falha específico na recuperação de código sob tokenização congelada e fornece uma solução matematicamente fundamentada, de baixo custo e adaptativa que restaura o poder discriminativo de identificadores únicos sem exigir reindexação ou alterações no tokenizador.