ExecRetrieval: Measuring the Functional-Correctness Gap in Code-Embedding Retrieval

AI summary

Overview

Research area: Software engineering / information retrieval — specifically embedding-based code retrieval and retrieval-augmented code generation (cs.SE).

Technical level: Intermediate. The retrieval metrics and statistical tests assume some familiarity with embedding search, but the central finding is stated plainly enough for a general software-engineering audience.

Scope: The paper introduces ExecRetrieval, a 939-task Python code-retrieval benchmark whose search pool contains execution-verified single-edit buggy variants of each query's canonical implementation, and uses it to measure whether 23 dense embedding configurations plus BM25 can rank a passing implementation above its near-clones.

What This Paper Is About

Embedding models are the first stage of most coding assistants and retrieval-augmented code pipelines: they decide which candidate snippets ever reach reranking, tests, or an agent. Existing code-retrieval benchmarks (CodeSearchNet, CodeXGLUE, CoSQA, CoIR, CodeRAG-Bench) score topical or identity similarity, so a retriever that finds lexically similar but functionally wrong code can score identically to one that finds correct code. This paper builds a benchmark that plants near-identical, execution-verified buggy variants directly in the search pool, so that a retriever's rank ordering can be tested for functional discrimination rather than topical overlap.

Key Contributions

1. Dataset. ExecRetrieval: 939 Python tasks spanning ten algorithmic domains, each with one canonical implementation, up to four mechanically mutated buggy distractors (one query has 3, the rest 4), and a 7–10-test execution oracle. All canonicals pass all their own tests; all distractors fail at least one. The total corpus is 4,694 snippets (939 canonicals plus 3,755 distractors).

2. Construction pipeline. A registry-driven, two-phase reasoning-LLM pipeline (GPT-5.4 with high reasoning effort) with a 91% first-attempt validation rate (91 of 100 validation-batch entries), a five-stage validation gate (schema, AST semantics, canonical execution, distractor execution, corpus integrity), and an isolated-subprocess execution runner.

3. Provider-native evaluation. 23 dense embedding configurations plus BM25, each invoked under its documented best-fair-shot setup (task types, prefixes, dtype, normalization, batch size, similarity metric). Reports exec@k and execution_precision@k alongside canonical-ID nDCG, with paired McNemar tests and query-level bootstrap intervals.

4. Empirical findings. Top-k retrieval saturates (exec@10 = 1.00 for the best hosted system) while rank-1 retrieval is weak (0.331 at best), and rank-1 misses are almost always paired buggy variants rather than unrelated code.

Main Findings

• Top-k is easy, rank-1 is hard. The top exec@1 system, Gemini Embedding 2, reaches only exec@1 = 0.331 (95% bootstrap CI [0.299, 0.362]). Gemini Embedding 001 reaches 0.329 and is statistically indistinguishable at exec@1 (paired McNemar exact p = 0.958; difference +0.002, 95% CI [-0.038, +0.042]). Mistral Embed ranks third at 0.224, followed by the open-weight Qwen3 family.

• Top-10 is essentially saturated. Gemini Embedding 2 reaches exec@10 = 1.00 across all 939 queries; Gemini Embedding 001 and Codestral Embed 2505 also achieve 1.00. Mid-tier models such as BGE-base and E5-large-v2 reach exec@10 in [0.94, 0.95].

• Lexical retrieval is a poor proxy. BM25 reaches exec@1 = 0.058 and exec@10 = 0.422, below the worst dense embedding model (paraphrase-MiniLM at exec@10 = 0.671).

• Misses are near-clones, not arbitrary errors. Between 91.5% and 99.4% of rank-1 misses across the four leading systems are paired buggy variants of the same query's canonical: Gemini Embedding 2, 624 of 628 (99.4%); Gemini Embedding 001, 618 of 630 (98.1%); Mistral Embed, 667 of 729 (91.5%); Qwen3-Embedding-8B, 718 of 738 (97.3%).

• The canonical frequently scores below its own mutations. For the 938 queries with at least one mechanical-type paired distractor, the canonical has lower query cosine than at least one paired distractor in 66.8% of queries on Gemini Embedding 2 and 78.4% on Qwen3-Embedding-8B (median and mean per-query gap both -0.002 for both models). The abstract summarizes this as 67–78% on the leading systems.

• A single near-clone creates most of the gap. In the pool-density ablation, retaining zero near-clones gives exec@1 of 0.93–0.99 for the four leading systems (0.532–0.993 across all 23 configurations, 6 at or above 0.95). Retaining one drops the strongest system from 0.993 to 0.678; the relative one-clone drop is 27–49% across all 23. With all distractors: Gemini Embedding 2 0.331, Gemini Embedding 001 0.329, Mistral Embed 0.224, Qwen3-Embedding-8B 0.214.

• Deception is spread across bug types. Across 23 dense configurations, 86,135 evaluable paired triples show a 44.3% deception rate, spanning a narrow 39.3%–48.0% band. remove_edge_case_check is least deceptive (39.3%) and wrong_comparison most (48.0%); the other four cluster between 42.8% and 47.0%.

• Deception is not an artifact of tiny edits. Rates span 39.5–47.5% across character-span buckets (1 to 21+ characters) with tie-aware Spearman |ρ| ≤ 0.07, and stacking 2–4 execution-verified, line-disjoint mutations leaves deception within 1.7 points of the single-mutation rate (matched 371-query comparison, four locally run embedders).

• Between-family gaps are detectable; within-family scaling is not. Gemini Embedding 2 beats Mistral Embed (+0.108, p = 6.5×10⁻⁸) and Qwen3-8B (+0.117, p = 3.4×10⁻⁹) at exec@1, roughly 110 more queries than Qwen3-8B out of 939. But Qwen3-8B is not significantly better than Qwen3-4B BF16 at exec@1 (p = 0.622), nor is 4B-BF16 better than 4B-FP16 (p = 0.456).

• Execution and identity ranking disagree. Gemini Embedding 001 leads on nDCG@5 and exec@3, while Gemini Embedding 2 has the highest exec@1 (Gemini 001 is significantly stronger at exec@3, p ≈ 2.7×10⁻⁵). The median query is solved at rank 1 by only 3 of 24 systems, 88 queries by none, and date-time is the hardest domain (mean exec@1 = 0.091 across all 24 systems, versus 0.107–0.151 elsewhere).

Methodology in Plain English

The authors first used Claude Sonnet 4.6 to draft 1,000 candidate (function name, natural-language query, domain) triples, 100 per domain, then deduplicated manually to 962 and then 954 entries. Crucially, this registry contains only the query text and function name — no implementations — so the model that later writes code cannot collude with itself on task selection.

In a second phase, GPT-5.4 with high reasoning effort was asked, one API call per validated entry, to produce a canonical implementation, a 7–10-statement assert-only test suite, and four distractors that each make a single mechanical edit. The prompt forbids writing an alternative algorithm ("wrong_semantics") and restricts distractors to six bug types: off_by_one, wrong_operator, swap_arguments, remove_edge_case_check, wrong_comparison, and off_by_one_boundary.

Every entry must clear five gates: schema checks, AST-level checks that the target function is defined, execution of the canonical against all tests, execution of each distractor (each must fail at least one test, and almost all must fail on output rather than crash), and corpus-integrity checks. Execution runs in a fresh Python subprocess (-I, minimal environment, fresh namespace per test, 5-second per-suite timeout), producing the per-test outcome cache of 46,458 rows. Two further sweeps confirmed that 0 distractors pass all their own tests and that there are 0 module-level cross-entry name collisions.

For evaluation, each embedding model is called the way its provider documents: Gemini Embedding 001 uses the CODE_RETRIEVAL_QUERY and RETRIEVAL_DOCUMENT task types, Qwen3 models get the official instruction prefix, E5 gets "query: "/"passage: ", BGE gets its retrieval prefix, and OpenAI, Mistral, GTE, and Sentence-Transformers receive raw text. All use cosine similarity over L2-normalized embeddings except multi-qa-mpnet-base-dot-v1, which uses unnormalized dot product per its card. Results are scored with exec@k (at least one passing snippet in the top k), execution_precision@k, and canonical-ID nDCG for k ∈ {1, 3, 5, 10}, averaged unweighted over the 939 queries, with 5,000-replicate bootstrap intervals and exact McNemar tests on discordant pairs.

Why This Matters

Impact on research. The paper isolates a signal that prior code-retrieval benchmarks structurally cannot measure. Because every wrong retrieval is traceable to one test-checkable edit, failures become attributable rather than diffuse, and the released oracle plus frozen embedding matrices make reranking experiments (the obvious next stage) deterministic to re-run.

Real-world applications:

• Coding assistants and IDEs that retrieve prior occurrences of a function from a local repository, where a stale pre-fix or copy-pasted diverged variant may sit one cosine step from the correct version.
• Retrieval-augmented code generation pipelines, where the embedding stage determines which candidates later reranking, tests, or LLM post-processing ever see and in what order.
• Agentic coding loops that cache failed attempts or sample several implementations of the same task, placing near-clones directly in the retrieval pool.
• Monorepos and commit-history indices, which hold pre-fix versions of code that was later corrected — the paper cites clone studies finding that 70% of GitHub code consists of file-level clones of earlier files and that about half of clone groups contain inconsistently modified members.

Industry relevance. The result reframes embedding retrieval as a candidate-recall component rather than a correctness filter: any system that relies on rank-1 embedding output as "the answer" inherits a substantial correctness burden. The finding that Gemini Embedding 2 and Qwen3-8B differ by +0.117 at exec@1 (p = 3.4×10⁻⁹) while Qwen3-8B and Qwen3-4B BF16 show no rank-1 difference gives practitioners a concrete signal about where model choice matters and where scaling does not.

Future Directions

• Cross-encoder and LLM rerankers. Running rerankers over the embedding-retrieved top-k may close the rank-1 gap without retraining first-stage embedders; the released oracle and frozen matrices make that lift measurable deterministically.

• Cross-language porting. Adding JavaScript, Rust, or Go would test whether near-clone deception is Python-specific or general. The generation pipeline is language-agnostic in design, but each language needs its own runner.

• Free-form LLM-generated bugs. Naturally written buggy implementations, retained only when they fail the tests, would probe a broader bug distribution. The authors note this complements rather than replaces mechanical mutation, since a free-form rewrite loses the single-attributable-edit control, and execution filtering is not optional — 127 of 400 pilot buggy-rewrite requests were accidentally correct (31.8%), with 40 of those 127 self-admitting "actually correct" in the bug_description field.

• Measuring how often deployed corpora pose the choice. Every reported magnitude is conditional on a near-clone being present in the pool. How often real retrieval corpora present that choice is unmeasured, and doing so would require an execution oracle over open-domain code.

Target Audience

Researchers and engineers working on code retrieval, code embeddings, retrieval-augmented generation, and coding agents — particularly those choosing an embedding model or designing a retrieval-plus-reranking pipeline. It is also useful for benchmark designers interested in execution-grounded, attributable evaluation, and for practitioners who need to know how much correctness work their first-stage retrieval is passing downstream. Readers should be comfortable with standard retrieval metrics (recall at k, nDCG) and basic significance testing.

Authors’ abstract

Embedding-based code retrieval is a core component of coding agents and retrieval-augmented code generation, where retrieving correct code matters more than retrieving lexically similar code. Existing code-retrieval benchmarks do not plant controlled, execution-verified single-edit variants of each query's canonical implementation in the search pool, leaving the question of whether embeddings can functionally discriminate correct from near-clone-but-incorrect code unanswered in a retrieval setting. Resolving this requires a benchmark whose search pool itself contains the relevant counterfactuals -- execution-verified buggy variants near-identical to each canonical -- so that a retriever's rank ordering can be directly tested for functional discrimination rather than topical or identity overlap. We introduce ExecRetrieval, 939 Python tasks each paired with one execution-verified canonical implementation and up to four execution-verified buggy distractors, each generated by a mechanical mutation making a single targeted edit, and evaluate 23 dense embedding configurations plus BM25 under provider-native invocation with paired McNemar tests and query-level bootstrap intervals. With near-clone counterfactuals in the pool, the top hosted system reaches exec@10 = 1.00 but only exec@1 = 0.331; rank-1 misses are paired buggy variants 91.5-99.4% of the time across the four leading systems, and the canonical scores below at least one of its four paired distractors in 67-78% of queries on the leading systems. The full dataset, execution oracle, embedding matrices, environment snapshot, and pairwise statistical tests are released at the URL in Appendix D.