ExecRetrieval: Measuring the Functional-Correctness Gap in Code-Embedding Retrieval
Aaryan Kapoor, Md Abdullah Al Hafiz Khan
EMNLP 2026 (Main Conference)
cs.SE, cs.CL, cs.IR
2026-09-02
ExecRetrieval plants test-verified one-edit bugs beside 939 Python canonicals. Gemini Embedding 2 hits exec@10=1.00 but only exec@1=0.331.
Embedding retrieval is the first stage of coding agents and retrieval-augmented code generation: rank candidates, then let reranking, execution, or a model pick. Public benchmarks score identity overlap or topical match. If the pool never contains a one-edit buggy twin of the correct implementation, a perfect topical retriever and a perfect functional retriever get the same score.
The case that matters for downstream use is both sitting in the pool: the passing implementation and a near-clone that fails the tests. Agent caches, commit histories, and copy-pasted utilities make that pairing plausible. If stage one cannot separate them, later stages only see a polluted shortlist.
ExecRetrieval is a functionally grounded retrieval benchmark. 939 Python tasks cover ten algorithmic domains, including bit manipulation, collections, date-time, geometry, and strings. Each task ships a natural-language query, a canonical that passes every test, up to four single-edit buggy distractors, and 7 to 10 asserts. The corpus is 4,694 snippets. Every canonical passes; every distractor fails at least one test.
The bugs are mechanical mutations, not alternative algorithms. Six locked types map onto classical mutation-testing operators: offbyone, wrongoperator, swaparguments, removeedgecasecheck, wrongcomparison, offbyoneboundary. wrongsemantics is banned because Claude Sonnet, asked to write wrong code, produced another correct implementation in 127 of 400 distractors (31.8%). GPT-5.4 with high reasoning cut accidental passes to 3 of 4,112 first-attempt distractors (0.07%). Claude Sonnet 4.6 writes the task registry; a different model writes the code, so the generator cannot pick its own exam.
Five gates: schema, AST semantics, canonical execution, distractor execution, corpus integrity. Tests run in an isolated subprocess with a 5-second timeout. A cross-canonical sweep finds no name collisions that would let foreign code pass a query's tests. Dataset, execution cache, and 23 embedding matrices are public. List-price generation cost is about $108.53.
The study evaluates 23 dense embedding setups plus BM25, each under its provider's documented best-fair-shot invocation. Metrics are exec@k (whether any of the top-k snippets pass the tests), executionprecision@k, and nDCG against canonical IDs. Comparisons use paired McNemar tests and 5,000 query-level bootstrap replicates.
The best hosted model, Gemini Embedding 2, reaches exec@1 of 0.331 (95% CI [0.299, 0.362]), exec@3 of 0.823, and exec@10 of 1.00. Gemini Embedding 001 is at 0.329 exec@1; the two are indistinguishable at rank 1. Open-weight Qwen3-Embedding-8B is 0.214. OpenAI text-embedding-3-large falls to 0.113. BM25 is 0.058 exec@1 and 0.422 exec@10, below even paraphrase-MiniLM at 0.671 exec@10.
| System | exec@1 | exec@5 | exec@10 |
| Gemini Embedding 2 | 0.331 | 0.997 | 1.000 |
| Gemini Embedding 001 | 0.329 | 0.988 | 1.000 |
| Mistral Embed | 0.224 | 0.937 | 0.984 |
| Qwen3-8B | 0.214 | 0.979 | 0.997 |
| OpenAI 3-large | 0.113 | 0.939 | 0.985 |
| BM25 | 0.058 | 0.328 | 0.422 |
When rank-1 is wrong, it is a paired buggy variant 91.5% to 99.4% of the time on the four leading systems. The canonical sits below at least one paired distractor on 66.8% of queries for Gemini 2 and 78.4% for Qwen3-8B. Deception across the six mutation types sits in a 39.3%-48.0% band, 44.3% overall. No single bug family carries the failure.
A density ablation closes the obvious objection. With zero near-clones in the pool, leading systems sit at 0.93-0.99 exec@1. Keep one near-clone, and the strongest system drops from 0.993 to 0.678. Edit span from 1 character to 21+ barely moves deception. Stacking 2 to 4 line-disjoint mutations in one function changes the rate by 1.7 points versus a single mutation.
Date-time is the hardest domain: mean exec@1 across 24 systems is 0.091. 88 of 939 queries have rank-1 success on zero systems. The median query is solved at rank 1 by 3 of 24.
For code RAG and coding agents this is a measurement warning: current embeddings are usable recallers and weak functional discriminators. Gemini 2 can put a passing implementation somewhere in the top 10 on every query, and still put a one-edit bug first most of the time. Downstream execution, tests, or reranking are not optional. Cosine-top-1 is not a runner.
The paper does not estimate how often deployed corpora pose this choice. It measures the discrimination load that stage one hands to later stages, given a near-clone in the pool. Clone studies and fix histories make co-occurrence plausible. Frequency is unmeasured.
Python only. Mechanical mutants are not human bugs. The corpus is a closed 4,694-snippet world, so exec@k is not comparable to open-domain code search. The runner isolates a process and times out at 5 seconds; it does not jail the filesystem or the network. Cross-encoder and LLM rerankers, the engineering move most likely to lift rank-1, are not evaluated. 939 queries are small next to topical retrieval sets; the binding cost is per-query execution. Hosted APIs drift; frozen embedding matrices keep scoring deterministic.
Generated tests can be stricter than the query text. Correctness is relative to those tests, not a formal spec. Inside the Qwen3 family, 8B is not detectably better than 4B at exec@1. Open-weight leadership here is not a scaling result.