Most of the Embedding Lead in Code Search Came From How BM25 Was Set Up

A new preprint (arXiv:2611.20455) finds dense code search's lead over BM25 mostly comes from chunking BM25 and counting edited tests as relevant. Add LLM-written identifiers to the query and whole-file BM25 matches the encoder.

Share
Most of the Embedding Lead in Code Search Came From How BM25 Was Set Up

Code-search leaderboards say dense encoders beat keyword search by a wide margin. Coding agents that search with grep don't seem to mind. In its write-up of a SWE-bench Verified agent, Augment Code said that "for SWE-bench tasks this was not the bottleneck", since grep and find were sufficient (Augment Code blog). A new preprint by Siqiao Xue, Ziyin Zhang, Zihan Liao, Jin Qin, Yixiang Mu and Hang Yu of Ant Group, Embeddings vs. Grep: Rethinking the Dense Advantage in Code Search (arXiv:2611.20455, submitted 16 Nov 2026), shows how both can be true. Most of the measured dense advantage comes from how the lexical baseline is configured and how relevance is labeled. The rest sits on queries that don't contain the code's rare identifiers, and an LLM can write those in.

The benchmark

The authors built RepoPremium, a benchmark that ranks files inside real repositories. The input is a description of a change: either a curated SWE-bench Verified issue statement or the raw title and body of a merged pull request. The output is a ranking of the repository's files, and the relevant ones are the non-test source files the change actually edited. The core set has 1,265 queries over ten Python repositories and 10,200 indexed files, split into four pools: curated statements, plus raw PRs from 2022, 2023 and 2026. An extension set adds JavaScript, TypeScript, Go, Rust and Java, nine held-out Python repositories, and a preregistered lockbox of 539 queries over 91 repositories.

The paper calls dense retrieval's nDCG@10 lead over BM25 the "dense premium." The main encoder is jina-code-embeddings-0.5b, one of thirteen tested.

Chunking decides the sign

The usual comparison splits every file into the same 1,000-character chunks for both retrievers. Dense encoders need that, because they truncate long inputs. BM25 doesn't, and it gets better as the window grows. With shared chunking, the premium is +0.121 on curated queries and +0.128 to +0.191 on the raw pools (Table 4). Let BM25 index whole files and the curated premium drops to +0.034, with the raw pools at +0.059 to +0.125 (Table 2). On curated queries the remaining interval covers zero, and seven of the thirteen encoders fall significantly below whole-file BM25.

Labels do the rest. Dense retrievers rank a test file first far more often than BM25: on 59% of curated queries, against 34%. A PR's changed-file list includes the tests it edited, and SWE-bench gold patches include none. Count edited tests as relevant and the tuned premium rises from +0.034 to +0.165 on curated queries and from +0.059 to +0.136 on the 2026 PRs. With one rule applied to every pool, the curated and raw pools can't be told apart.

The dense premium (dense minus BM25, nDCG@10) in the four Python pools: against BM25 on the encoder's 1,000-character chunks (Table 4), against whole-file BM25 (Table 2), and against whole-file BM25 with LLM-written identifiers added to the query (Table 2). Encoder: jina-code-embeddings-0.5b, source-file labels. Redrawn from Xue et al., arXiv:2611.20455.

What is left is a vocabulary gap

Against whole-file BM25, the remaining dense lead is mostly coverage. Dense retrieval gets more gold files into its top ten (Recall@10 higher by 0.10 to 0.19), but it ranks its first hit significantly higher only on the 2022 pool. The premium concentrates on queries whose rarest word shared with the target file is still a common one. On 604 development queries it falls from +0.217 in the least distinctive quartile to +0.050 in the most distinctive, measured against chunked BM25. Against whole-file BM25 it goes from +0.125 to −0.046. The per-query correlation is weak (r = −0.124), so this is a statement about group means.

That suggests a test. If the encoder's edge comes from evidence the query lacks, supplying that evidence should help BM25 more. An LLM (qwen35-122B, temperature 0, one frozen prompt) read the stripped query, never the gold paths or patch, and wrote identifiers, module hints, APIs, error terms and a code skeleton. The authors prepend that text to the query and run BM25 over whole files, and they call this generate-then-grep. It adds 0.11 to 0.19 nDCG@10 to BM25 and never trails the encoder in any Python pool. On curated queries it leads by 0.081, with an interval that excludes zero. On the raw pools it leads by 0.054 to 0.062, with intervals that cover zero. In the paper's control comparison (Table 12), the same expanded query lifts the encoder by +0.03 to +0.07 and BM25 by +0.12 to +0.21. Prose search phrases don't close the gap. Identifiers, APIs and error terms do.

Contamination is the obvious objection, since the generator may know these repositories. On held-out PRs opened after the generator's release (116 queries, seven repositories), generate-then-grep still beats dense retrieval by 0.094. The authors note that this shows expansion can replace the premium, but it doesn't show where the premium comes from.

Fuse, don't route

BM25 strictly beats dense retrieval on 24% of curated queries and 21% of 2026 PR queries, and a per-query oracle would add about 0.09 nDCG@10 over dense alone. Nothing the authors tried could pick out those queries in advance. Classifiers, query-embedding models and two zero-shot LLM judges all landed at AUROC 0.47 to 0.54. They built about 30 routers, froze the only one whose development gain excluded zero, and scored it once on the lockbox. It gained +0.005 over always fusing, against +0.077 for the oracle, and missed its preregistered criterion.

Fixed reciprocal rank fusion held up instead. In Table 3, fusing dense retrieval with whole-file BM25 scores 0.551 on the lockbox against 0.533 for dense alone, and fusing dense with generate-then-grep scores 0.578, the best lockbox result.

What to do with this

If you are deciding whether a repository needs an embedding index, check the baseline before trusting a dense number. Index whole files for BM25, strip PR templates, and state which edited files count as relevant.

For coding agents, the model matters more than the search tool. With the LLM fixed, a SWE-agent on 96 held-out tasks scored within about 0.04 exact-match whether it had a shell with grep, a lexical index, a dense index or a router. Across four setups of three LLMs on a 30-task subset, exact-match ranged from 0.03 to 0.30.

Cost depends on how often you search. In the paper's estimate, one Qwen3-8B call takes about 1.5 seconds per query, while a dense index needs a one-off encoding pass per repository, about four minutes for django. Below roughly 158 queries per repository, generation is cheaper.

The paper is plain about its limits. The core covers ten Python repositories, each non-Python language is a single repository, BM25's setting was picked on the evaluation queries, and only file-level retrieval is tested. The authors still recommend keeping dense retrieval and fusing it with BM25. Their claim is narrower: a dense win reported against chunked BM25, with edited tests counted as relevant, mostly measures those two choices.

The queries, labels, pinned commits, PR stripper and harnesses are released on GitHub.

0 subscribers
0 average monthly readers