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

Riepilogo Tecnico: Miglioramento del Recupero di Codice BM25 Sotto Tokenizzazione Generica Fissa

1. Enunciato del Problema

Nei sistemi di codifica potenziati dal recupero, un punto critico di fallimento si verifica quando il file sorgente rilevante è assente dal contesto recuperato. Ciò accade spesso nei regimi di "tokenizzazione generica congelata", dove un indice BM25 è costruito da un'infrastruttura di ricerca (ad esempio Lucene, Elasticsearch, Tantivy) utilizzando un analizzatore sintonizzato sul linguaggio naturale piuttosto che sul codice. I praticanti spesso non possono modificare questo tokenizzatore.

Sotto questi vincoli, il BM25 standard non riesce a distinguere sufficientemente tra identificatori di codice unici (ad esempio handleWebSocketUpgrade) e token comuni e ricorrenti. L'Inversa Frequenza Documentale (IDF) Robertson–Spärck-Jones (RSJ) standard utilizza una funzione logaritmica: $\log((N - n_t + 0.5)/(n_t + 0.5))$. Poiché il logaritmo cresce lentamente, "sottosepara" la coda della distribuzione. Un termine che appare in un singolo file ($df=1$) e un termine che appare in 50 file ricevono pesi IDF che differiscono per una piccola costante piuttosto che per un ordine di grandezza. Di conseguenza, i file "gold" contenenti identificatori unici sono spesso classificati al di sotto dei file "distrattori" che condividono alcuni token comuni e non unici, riempiendo la finestra di contesto dell'agente con codice irrilevante.

2. Metodologia: Odds Logaritmici q-Adattivi

Il documento propone una soluzione "drop-in" che modifica solo il logaritmo esterno del calcolo IDF di BM25, lasciando inalterate la saturazione della frequenza dei termini e la tokenizzazione.

• La Trasformazione: Gli autori sostituiscono il logaritmo standard con il logaritmo q di Tsallis (o $q$-log), definito come:
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  Il nuovo IDF diventa:
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  dove $\delta = 0.5$.

• Proprietà Matematiche:

  • Recupero di BM25: A $q=1$, la trasformazione recupera esattamente l'IDF BM25 classico tramite la regola di L'Hôpital ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • Amplificazione a Legge di Potenza: Per $q < 1$, la trasformazione agisce come una trasformazione Box-Cox delle odds RSJ con $\lambda = 1-q$. Nel regime di token ultra-rari ($n_t \ll N$), l'IDF cresce come una legge di potenza ($x^{1-q}$), amplificando significativamente il peso degli hapax $df=1$ (identificatori unici) rispetto ai token meno rari.
  • Saturazione: Per $q > 1$, l'IDF satura, scartando efficacemente la discriminazione per i token rari.

• Implementazione: Il metodo richiede solo un singolo passaggio sulla matrice di punteggi sparsa al momento del caricamento dell'indice per ridimensionare la colonna IDF. La latenza delle query rimane invariata.

3. Contributi Chiave

1. IDF Odds RSJ-q-Log: Una deformazione a un parametro dell'IDF BM25 che recupera BM25 esattamente a $q=1$ e agisce come amplificatore a legge di potenza per i token rari quando $q < 1$.
2. Limiti di Prestazione Oracle: Sul corpus CoIR CodeSearchNet Go (182K documenti) con tokenizzazione generica congelata, sintonizzando $q$ a $0.05$ si migliora NDCG@10 da 0.2575 a 0.4874 (+89,3% di guadagno relativo). Questo risultato è statisticamente significativo ($p \le 10^{-4}$) con zero inversioni di segno in 10.000 ricampionamenti bootstrap accoppiati.
3. Predittore Adattivo al Corpus: Un predittore in forma chiusa e privo di etichette $q_{pred} = 1 - 7.28 \cdot h_{tok}$ (dove $h_{tok}$ è la densità degli hapax) che stima il $q$ ottimale dalle sole statistiche del corpus. Questo predittore ottiene un recupero leave-one-language-out di 0,72 e torna correttamente a $q \approx 1$ per i corpus dove BM25 è già ottimale (ad esempio Python).
4. Ablazione del Tokenizzatore: Lo studio dimostra che il guadagno di prestazioni derivante da $q$-IDF dipende largamente dal tokenizzatore. Quando viene utilizzato un tokenizzatore consapevole degli identificatori (che divide handleWebSocketUpgrade in sottotoken), il guadagno incrementale da $q$-IDF crolla. Ciò conferma che il valore del metodo è specifico per il regime di "tokenizzatore congelato".
5. Proxy Rilevanti per l'Agente: Il metodo mostra guadagni significativi in Recall@K-token (efficienza della finestra di contesto), aumentando la probabilità che il file gold appaia entro un budget di 8K token dal 48,1% al 68,8% su Go.

4. Risultati Sperimentali

• Codice vs Testo: Il metodo produce guadagni massicci sui corpus di codice con code di identificatori pesanti (Go, Java, Ruby) ma guadagni quasi nulli sul testo in linguaggio naturale (dataset BEIR) e su Python.
  • Go: $q_{opt} = 0.05$, +89,3% di guadagno NDCG@10.
  • Java/Ruby: Guadagni positivi significativi ($q_{opt} \approx 0.70-0.90$).
  • Python: $q_{opt} = 1.00$. Gli identificatori di Python sono spesso parole simili a dizionari riutilizzate tra i file; il segnale si trova nei bin di $df$ di medio livello, che il log-IDF standard gestisce già in modo ottimale. Discostarsi da $q=1$ distorce questi bin.
  • BEIR (Testo): Nessun guadagno significativo; il metodo collassa a BM25 poiché l'oracle $q$ si trova a 1 o superiore.
• Scalabilità: Il guadagno di prestazioni scala in modo monotono con la dimensione del corpus. Su Go, il guadagno assoluto aumenta da +0,061 a 1K documenti a +0,227 a 182K documenti.
• Baseline: Il metodo $q$-log supera le semplici ridimensionamenti IDF a legge di potenza ($idf_\gamma$) e i modelli Divergenza dal Caso (DFR-DPH), che falliscono sul codice a causa di una normalizzazione della frequenza dei termini non calibrata.

5. Significato e Scopo

Il documento posiziona questo lavoro non come una sostituzione per una corretta tokenizzazione, ma come un intervento necessario quando i vincoli infrastrutturali lo impediscono.

• Utilità Pratica: Per i praticanti che utilizzano cluster di ricerca gestiti (Elasticsearch, OpenSearch) dove l'analizzatore è fisso, questo metodo offre una modifica "a una riga" al calcolo IDF che può quasi raddoppiare l'efficacia del recupero per la ricerca di codice.
• Meccanismo: Il miglioramento è guidato dall'amplificazione degli hapax $df=1$ (identificatori unici come handleWebSocketUpgrade), che sono i principali discriminatori nel recupero del codice ma vengono appiattiti dalla ponderazione logaritmica standard.
• Limitazioni: Gli autori dichiarano esplicitamente che se un operatore controlla il tokenizzatore, il miglior approccio è utilizzare un analizzatore consapevole degli identificatori e mantenere $q=1$. Sovrapporre $q$-IDF alla tokenizzazione consapevole degli identificatori produce rendimenti trascurabili o negativi. Il metodo è anche dipendente dalla lingua; non offre benefici (e potenzialmente un leggero degrado) su lingue con bassa densità di hapax come Python o PHP su larga scala.

In sintesi, il documento identifica una specifica modalità di fallimento nel recupero del codice sotto tokenizzazione congelata e fornisce una soluzione matematicamente fondata, a basso costo e adattiva che ripristina il potere discriminatorio degli identificatori unici senza richiedere re-indicizzazione o modifiche al tokenizzatore.