Improving BM25 Code Retrieval Under Fixed Generic Tokenization Adaptive q q -Log Odds as a Drop-In BM25 Fix
Santosh Kumar Radha, Oktay Goktas · 2026
Read Improving BM25 Code Retrieval Under Fixed Generic Tokenization Adaptive q q -Log Odds as a Drop-In BM25 Fix by Santosh Kumar Radha, Oktay Goktas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18561.txt.
Introduction
Santosh Kumar Radha and Oktay Goktas fix, in a 2026 paper, BM25 code retrieval under frozen generic tokenization. They replace the outer logarithm of RSJ odds with a q-logarithm. At q equal to 1 it recovers BM25 exactly, and below 1 it gives a Box-Cox transform. On CodeSearchNet Go, oracle-tuned NDCG at 10 rises from 0.2575 to 0.4874, an 89.3 percent relative gain with zero sign reversals in 10,000 bootstrap resamples. A closed form estimates corpus-level q from hapax density, and query latency stays unchanged.
Catalog record
| CREATOR | Santosh Kumar Radha, Oktay Goktas |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58194 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18561
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improving BM25 Code Retrieval Under Fixed Generic Tokenization Adaptive q q -Log Odds as a Drop-In BM25 Fix Santosh Kumar Radha, Oktay Goktas Abstract In retrieval-augmented coding, failures often begin when the relevant file is absent from the retrieved context. Under frozen generic tokenization, where a BM25 index has been built by a search system whose analyzer the practitioner does not control, this failure is routine: BM25’s logarithmic RSJ-odds IDF under-separates the identifier tail that distinguishes one function from another. We replace the outer logarithm of the Robertson–Spärck-Jones odds with a q q -logarithm. At q = 1 q=1 the transform recovers BM25 exactly by L’Hôpital’s rule, and for q < 1 q<1 it is a Box-Cox transform of the RSJ odds with λ = 1 − q \lambda=1-q . On CoIR ( Li et al. 2024 ) CodeSearchNet ( Husain et al. 2019 ) Go (182K documents), oracle-tuned NDCG@10 rises from 0.2575 0.2575 to 0.4874 0.4874 (absolute + 0.2299 +0.2299 ; + 89.3 % +89.3\% relative; zero sign reversals in 10,000 10{,}000 paired-bootstrap resamples, reported as p ≤ 10 − 4 p\leq 10^{-4} ). The effect is graded across code languages and is near-zero on BEIR ( Thakur et al. 2021 ) text. A one-parameter closed form estimates a corpus-level q q from hapax density and stays near q = 1 q=1 on corpora where BM25 is already optimal. The index-time cost is a single pass over the sparse score matrix and query latency is unchanged. A tokenizer ablation shows that identifier-aware tokenization largely removes the incremental gain from q q -IDF. 1 Introduction A coding agent asked to patch a bug first has to find the gold file. When the function is called handleWebSocketUpgrade in a repository of fifty thousand files, the agent’s retriever should return one file, not a thousand. In practice the retriever is a commodity BM25 served through Lucene, Tantivy, Elasticsearch, or a similar indexer whose analyzer was tuned for natural-language text. Under frozen generic tokenization, the agent gets distractor files in its context, the model produces a wrong patch, and the failure is attributed to the model. Given an inherited generic tokenizer, the remaining under-separation is in the weighting. When analyzer changes are allowed, tokenization is the first fix and often the only one needed; this paper studies the regime where they are not. BM25 scores a query by summing term-level weights of the form \log((N-n_{t}+0.5)/(n_{t}+0.5)) ( Jones 1972 ; Robertson et al. 1994 ) , where n_{t} is the document frequency of term t and N the corpus size. The logarithm grows so slowly at the tail that it flattens the weight gap between ultra-rare and rare identifiers. A df=1 hapax like handleWebSocketUpgrade and a df=50 identifier that recurs across many files end up with IDF weights that differ by a small constant rather than an order of magnitude. The agent-relevant consequence is that the gold file is ranked below distractor files which happen to share a few of those rare-but-not-unique tokens, and the context window fills with code the agent does not need. When the retrieval system is owned end-to-end, the right fix is to change the analyzer: emit both the whole identifier and its sub-tokens, building on a decade of work on automatic identifier splitting in the software-engineering community ( Caprile and Tonella 2000 ; Enslen et al. 2009 ; Hill et al. 2014 ) , so that BM25 has the discriminative signal available. Many deployments do not have that option. The tokenizer is fixed by an infrastructure decision; practitioners who wire a retriever into an existing search cluster inherit a tokenizer built for English and are asked to improve retrieval without touching it. This is the same regime in which repository-scale code-retrieval benchmarks such as RepoBench ( Liu et al. 2024 ) and Long Code Arena ( Bogomolov et al. 2024 ) situate their evaluations, and the regime this paper addresses. The mechanism we propose is a one-parameter deformation of the outer logarithm in the RSJ IDF. Writing the classical RSJ IDF as \log\!\left((N-n_{t}+0.5)/(n_{t}+0.5)\right) , we replace the \log by the Tsallis q -logarithm \ln_{q}(x)=(x^{1-q}-1)/(1-q) , giving the q -log RSJ-odds form. At q=1 the transform recovers the classical BM25 IDF exactly via L’Hôpital’s rule; for q<1 the IDF grows as a power law in the very-rare regime, amplifying df=1 hapaxes that the log would flatten against their less-rare neighbours. Mathematically this is a Box-Cox transform of RSJ odds with \lambda=1-q ( Box and Cox 1964 ) : we are not proposing a new function family, only identifying the right base (the RSJ odds) to apply a classical power transform to, and re-parameterising the exponent so that q=1 is the identity. Under the same frozen generic tokenization used by out-of-the-box BM25, the q -log transform at q=0.05 improves NDCG@10 on CoIR CodeSearchNet Go (182K documents) by +89.3\% over BM25 (from 0.2575 to 0.4874 ; zero sign reversals in 10{,}000 paired-bootstrap resamples, reported as p\leq 10^{-4} ). The signal is graded across languages, scales with corpus size, and is near-zero on BEIR text. It is also estimated from corpus statistics alone: a one-parameter closed form q=1-7.28\,\mathrm{htok} , fit on the six CoIR code languages at three subset sizes, attains a leave-one-language-out grand-mean recovery of 0.72 on held-out languages, and falls back to plain BM25 on corpora where q_{\mathrm{opt}}\approx 1 . A tokenization confound qualifies the result. If the analyzer is changed to emit both whole identifiers and sub-tokens, BM25 already carries the distinguishing evidence and the q -log gain collapses. This is a property of the method’s scope: the tokenizer ablation shows that identifier-aware tokenization largely removes the incremental gain from q -IDF, and the q -log form is the path available when the tokenizer is not. The frozen-tokenizer regime is not a corner case: it covers managed Elasticsearch and OpenSearch deployments, hosted code-search products built on Lucene or Tantivy, and any internal corpus indexed once by a platform team and queried by many downstream agents. In each case the analyzer is set by infrastructure rather than by the practitioner wiring in the retriever, and changing it requires a reindex coordinated across consumers; a one-line IDF rescale at index-load time does not. 10^{-4} 10^{-3} 10^{-2} 10^{-1} 0 5 10 15 1/(q{-}1) Document frequency fraction n_{t}/N (log scale) \mathrm{idf}_{q}^{\mathrm{RSJ}}(t) q=0.5 (amplify) q=0.8 q=1 (BM25) q=1.2 q=1.5 (saturate) Figure 1 : The q -log deformation of RSJ odds. Each curve is \mathrm{idf}_{q}^{\mathrm{RSJ}}(t)=\ln_{q}\!\left((N-n_{t}+0.5)/(n_{t}+0.5)\right) with \ln_{q}(x)=(x^{1-q}-1)/(1-q) , plotted against the document-frequency fraction n_{t}/N . At q{=}1 (dashed gray) the expression recovers the classical RSJ log-IDF exactly via L’Hôpital. For q<1 the IDF amplifies ultra-rare tokens into a power-law tail x^{1-q}/(1-q) ; for q>1 it saturates at 1/(q-1) and the rarest tokens stop contributing new discrimination. The one-parameter lever is curvature at the tail. Contributions. 1. The q -log RSJ-odds IDF, a one-line change to BM25 that recovers BM25 exactly at q=1 by L’Hôpital and is a Box-Cox transform of the RSJ odds with \lambda=1-q ( section 3 ). 2. An oracle-sweep upper bound of +89.3\% NDCG@10 on CoIR CodeSearchNet Go (182K) at the best tested q=0.05 under frozen generic tokenization, with 95% paired-bootstrap CI strictly above zero and a monotone scaling curve from 1K to