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

Technical Summary: Improving BM25 Code Retrieval Under Fixed Generic Tokenization

1. Problem Statement

In retrieval-augmented coding systems, a critical failure point occurs when the relevant source file is absent from the retrieved context. This often happens in "frozen generic tokenization" regimes, where a BM25 index is built by a search infrastructure (e.g., Lucene, Elasticsearch, Tantivy) using an analyzer tuned for natural language rather than code. Practitioners often cannot modify this tokenizer.

Under these constraints, standard BM25 fails to sufficiently distinguish between unique code identifiers (e.g., handleWebSocketUpgrade) and common, recurring tokens. The standard Robertson–Spärck-Jones (RSJ) Inverse Document Frequency (IDF) uses a logarithmic function: $\log((N - n_t + 0.5)/(n_t + 0.5))$. Because the logarithm grows slowly, it "under-separates" the tail of the distribution. A term appearing in a single file ($df=1$) and a term appearing in 50 files receive IDF weights that differ by a small constant rather than an order of magnitude. Consequently, "gold" files containing unique identifiers are often ranked below "distractor" files that share a few common, non-unique tokens, filling the agent's context window with irrelevant code.

2. Methodology: Adaptive q-Log Odds

The paper proposes a "drop-in" fix that modifies only the outer logarithm of the BM25 IDF calculation, leaving term-frequency saturation and tokenization untouched.

• The Transformation: The authors replace the standard logarithm with the Tsallis q-logarithm (or $q$-log), defined as:
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  The new IDF becomes:
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  where $\delta = 0.5$.

• Mathematical Properties:

  • Recovery of BM25: At $q=1$, the transform recovers the classical BM25 IDF exactly via L'Hôpital's rule ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • Power-Law Amplification: For $q < 1$, the transform acts as a Box-Cox transform of the RSJ odds with $\lambda = 1-q$. In the regime of ultra-rare tokens ($n_t \ll N$), the IDF grows as a power law ($x^{1-q}$), significantly amplifying the weight of $df=1$ hapaxes (unique identifiers) relative to less rare tokens.
  • Saturation: For $q > 1$, the IDF saturates, effectively discarding discrimination for rare tokens.

• Implementation: The method requires only a single pass over the sparse score matrix at index load time to rescale the IDF column. Query latency remains unchanged.

3. Key Contributions

1. q-Log RSJ-odds IDF: A one-parameter deformation of the BM25 IDF that recovers BM25 exactly at $q=1$ and acts as a power-law amplifier for rare tokens when $q < 1$.
2. Oracle Performance Bounds: On the CoIR CodeSearchNet Go corpus (182K documents) with frozen generic tokenization, tuning $q$ to $0.05$ improves NDCG@10 from 0.2575 to 0.4874 (+89.3% relative gain). This result is statistically significant ($p \le 10^{-4}$) with zero sign reversals in 10,000 paired-bootstrap resamples.
3. Corpus-Adaptive Predictor: A closed-form, label-free predictor $q_{pred} = 1 - 7.28 \cdot h_{tok}$ (where $h_{tok}$ is the hapax density) that estimates the optimal $q$ from corpus statistics alone. This predictor achieves a leave-one-language-out recovery of 0.72 and correctly defaults to $q \approx 1$ for corpora where BM25 is already optimal (e.g., Python).
4. Tokenizer Ablation: The study demonstrates that the performance gain from $q$-IDF is largely contingent on the tokenizer. When an identifier-aware tokenizer (splitting handleWebSocketUpgrade into sub-tokens) is used, the incremental gain from $q$-IDF collapses. This confirms the method's value is specific to the "frozen tokenizer" regime.
5. Agent-Relevant Proxies: The method shows significant gains in Recall@K-tokens (context window efficiency), increasing the likelihood of the gold file appearing within an 8K-token budget from 48.1% to 68.8% on Go.

4. Experimental Results

• Code vs. Text: The method yields massive gains on code corpora with heavy identifier tails (Go, Java, Ruby) but near-zero gains on natural language text (BEIR datasets) and Python.
  • Go: $q_{opt} = 0.05$, +89.3% NDCG@10 gain.
  • Java/Ruby: Significant positive gains ($q_{opt} \approx 0.70-0.90$).
  • Python: $q_{opt} = 1.00$. Python's identifiers are often dictionary-like words reused across files; the signal is in the middle-$df$ bins, which the standard log-IDF already handles optimally. Deviating from $q=1$ distorts these bins.
  • BEIR (Text): No significant gain; the method collapses to BM25 as the oracle $q$ sits at or above 1.
• Scaling: The performance gain scales monotonically with corpus size. On Go, the absolute gain increases from +0.061 at 1K documents to +0.227 at 182K documents.
• Baselines: The $q$-log method outperforms simple power-law IDF rescalings ($idf_\gamma$) and Divergence-from-Randomness (DFR-DPH) models, which fail on code due to miscalibrated term-frequency normalization.

5. Significance and Scope

The paper positions this work not as a replacement for proper tokenization, but as a necessary intervention when infrastructure constraints prevent it.

• Practical Utility: For practitioners using managed search clusters (Elasticsearch, OpenSearch) where the analyzer is fixed, this method offers a "one-line" change to the IDF calculation that can nearly double retrieval effectiveness for code search.
• Mechanism: The improvement is driven by the amplification of $df=1$ hapaxes (unique identifiers like handleWebSocketUpgrade), which are the primary discriminators in code retrieval but are flattened by standard logarithmic weighting.
• Limitations: The authors explicitly state that if an operator controls the tokenizer, the best approach is to use an identifier-aware analyzer and keep $q=1$. Stacking $q$-IDF on top of identifier-aware tokenization yields negligible or negative returns. The method is also language-dependent; it offers no benefit (and potentially slight degradation) on languages with low hapax density like Python or PHP at full scale.

In summary, the paper identifies a specific failure mode in code retrieval under frozen tokenization and provides a mathematically grounded, low-cost, and adaptive solution that restores the discriminative power of unique identifiers without requiring re-indexing or tokenizer changes.