PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Aaryan Kapoor, Md Abdullah Al Hafiz Khan

arXiv:2609.01865v1cs.SEcs.CLcs.IR

TL;DR

Existing code-retrieval benchmarks do not test whether embeddings rank execution-correct code above controlled near-clone bugs. ExecRetrieval fills this gap with a 939-task benchmark containing execution-verified canonical implementations and mechanically mutated distractors, finding strong top-10 but weak top-1 functional retrieval.

  • Problem

    Existing benchmarks do not place controlled, execution-verified single-edit buggy variants beside each canonical, leaving functional discrimination in retrieval unmeasured.

  • Method

    ExecRetrieval constructs 939 Python tasks with one execution-verified canonical and up to four mechanically mutated distractors, evaluating 23 dense configurations plus BM25.

  • Results

    The best hosted system reaches exec@10=1.00 but exec@1=0.331, while rank-1 misses are paired buggy variants 91.5–99.4% of the time across four leading systems.

  • Takeaways & Limitations

    Current code embeddings are strong candidate-recall components but leave substantial correctness-discrimination burden to downstream verification.

  • Takeaways & Limitations

    The benchmark uses a closed-world corpus and reports magnitudes conditional on a near-clone candidate being present, so exec@k is not comparable to open-domain code-search results.

Abstract

from arXiv · show

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.

1 Introduction

Embedding retrieval supports coding assistants and related systems, but existing benchmarks do not isolate whether retrievers distinguish tested-correct code from near-identical buggy variants. ExecRetrieval addresses this gap by placing execution-verified counterfactuals directly in the search pool.

  • Motivation: Embedding retrieval supplies code candidates for coding assistants, IDE search, and retrieval-augmented generation pipelines.Later stages may rerank, execute, test, or otherwise process retrieved candidates, but first-stage ranking determines which candidates they receive.
  • Measurement gap: Existing benchmarks measure canonical identity or topical similarity rather than controlled functional discrimination.They do not pair each canonical implementation with single-edit buggy variants in the search pool.
  • Contribution: ExecRetrieval tests whether embeddings rank a passing implementation above near-identical buggy variants.The benchmark isolates the functional-correctness gap in retrieval rather than measuring complete coding-agent performance.

2 RANK BY COSINE TO QUERY

ExecRetrieval evaluates retrieval by cosine similarity against execution-verified canonical and mutated implementations, using a functionally grounded search pool and paired evaluation. Results show strong top-k recall but brittle rank-1 functional discrimination, with even one near-clone substantially affecting performance.

  • Benchmark design: ExecRetrieval requires canonical code and near-identical, execution-verified single-edit buggy variants in each query’s search pool.Correctness is verified with deterministic test suites, and comparisons use per-query paired statistics.
  • Benchmark design: 939 tasks contain one canonical implementation and up to four mechanically mutated buggy distractors, totaling 4,694 snippets.The dataset spans ten algorithmic domains, and canonicals pass all tests while distractors fail at least one.
  • Empirical findings: exec@10=1.00 across all 939 queries, but the best rank-1 result is 33.1%.The evaluation covers 23 dense embedding configurations plus BM25 under provider-native invocation, reporting execution and canonical-ID metrics with paired tests and bootstrap intervals.
  • Empirical findings: 91.5–99.4% of rank-1 misses across the four leading systems are paired buggy variants.The canonical scores below at least one paired distractor in 66.8% of Gemini Embedding 2 queries and 78.4% of Qwen3-Embedding-8B queries.

2 Related Work

Prior code-retrieval benchmarks generally do not isolate rank ordering between each query’s canonical implementation and controlled, execution-verified single-edit variants. ExecRetrieval differs by planting such counterfactuals in the natural-language query-to-code retrieval pool itself.

  • Code-retrieval benchmarks: Existing benchmarks score canonical identity, topical relevance, annotated correctness, or downstream generation quality rather than controlled near-clone discrimination.This includes CodeSearchNet, CoSQA, CodeXGLUE, CoIR, and CodeRAG-Bench.
  • Code-retrieval benchmarks: CoQuIR annotates naturally occurring code for correctness and other quality dimensions but does not plant controlled edits of each query’s canonical.Its data include online-judge verdicts and Defects4J bug/fix pairs.
  • Closest functional comparison: Li et al. study execution-validated syntactically similar variants for pairwise classification and code-to-code retrieval over a standard pool.ExecRetrieval instead places each counterfactual in a natural-language query-to-code search pool, testing rank ordering after a single targeted edit.
  • Execution-based evaluation: Execution-based generation benchmarks test whether sampled code passes held-out tests, extending from function-level tasks to repository issue resolution.These benchmarks evaluate generation or issue resolution rather than the specific retrieval-ranking gap targeted here.

3 The EXECRETRIEVAL Dataset

ExecRetrieval is a 939-task Python benchmark whose search corpus pairs tested canonical implementations with mechanically mutated distractors across ten domains. A staged generation and validation pipeline retains only entries satisfying structural, execution, and corpus-integrity checks.

  • Task and structure: Each instance contains a natural-language query, target function, canonical implementation, 7–10 tests, and three or four single-mutation distractors.The canonical must pass every test, while each distractor must fail at least one.
  • Task and structure: The corpus contains 4,694 snippets spanning ten algorithmic domains, with one canonical and up to four distractors per task.One task contributes three distractors; the remaining tasks contribute four.
  • Generation pipeline: The registry-driven pipeline generated and deduplicated candidate task descriptions before retaining 939 validated entries.The initial registry contained 954 entries after manual deduplication.
  • Generation pipeline: Earlier Sonnet iterations produced accidentally correct distractors in 127 of 400 cases, whereas GPT-5.4 reduced this to 3 of 4,112 first-attempt distractors.The locked prompt restricts distractors to targeted mutations rather than broad rewrites.
  • Validation oracle and integrity audit: Five sequential validation gates check schema, AST semantics, canonical execution, distractor execution, and corpus integrity.A process-isolated runner executes each code-and-test pair in a fresh Python subprocess with a five-second suite timeout.
  • Validation oracle and integrity audit: The released corpus contains 99.7% distractors from six mechanical mutation types, with ten pilot-era legacy distractors remaining.The integrity sweeps found no distractor passing all of its own tests, and the final set retains 3,755 paired distractors.

4 Experimental Setup

The evaluation ranks corpus snippets for 939 queries and assesses retrieval using execution-based and canonical-identity metrics at multiple cutoffs. It compares 23 dense embedding configurations plus BM25 under documented invocation settings, with frozen artifacts and paired statistical procedures supporting reproducibility.

  • Metrics: exec@k measures whether at least one passing snippet appears in the top k, while execution_precision@k measures the passing fraction.PASS(c, Tq) indicates whether snippet c passes all tests for query q.
  • Metrics: Canonical-ID nDCG is reported alongside execution metrics, with unweighted means over queries for k ∈ {1, 3, 5, 10}.All three metric families are evaluated at the same four cutoffs.
  • Statistical Analysis: Metric confidence intervals use 5,000-replicate query bootstrap resampling, while binary model comparisons additionally use exact McNemar tests.Continuous metrics receive paired-bootstrap intervals; binary exec@k comparisons report paired-bootstrap differences and query-level 95% intervals.
  • Systems: The benchmark compares 23 dense embedding configurations across multiple model families with a BM25 baseline.Models use provider- or card-documented best fair-shot settings and model-specific prefixes or conditioning where specified.
  • Systems: Cosine similarity over L2-normalized embeddings is used generally, except for multi-qa-mpnet-base-dot-v1, which uses unnormalized dot product.Additional implementation controls include BF16 for Qwen3-8B and dense-only operation for BGE-M3.
  • Evaluation Data: 939 queries are evaluated against a frozen corpus of 4,694 snippets with deterministic identifiers and execution-result caching.The released evaluation package also includes saved embedding matrices, environment metadata, and validation manifests.

5 Results

ExecRetrieval reveals a sharp separation between strong top-k recall and weak rank-1 functional discrimination: embeddings usually retrieve a passing implementation quickly, but often rank a near-clone buggy variant first. The failures are structural, persist with one near-clone, and span models and mutation types.

  • 5.1 Top-k saturates while rank-1 fails: 0.331 is the best exec@1, achieved by Gemini Embedding 2 with bootstrap 95% CI [0.299, 0.362].Gemini Embedding 001 reaches exec@1=0.329, and the difference is statistically indistinguishable.
  • 5.1 Top-k saturates while rank-1 fails: 1.00 is Gemini Embedding 2’s exec@10 across all 939 queries, while mid-tier models reach exec@10 ∈[0.94, 0.95].Gemini Embedding 001 and Codestral Embed 2505 also achieve exec@10=1.00.
  • 5.1 Top-k saturates while rank-1 fails: 0.058 and 0.422 are BM25’s exec@1 and exec@10, respectively, with top-10 success below the weakest dense embedding model.Paraphrase-MiniLM reaches exec@10=0.671.
  • 5.2 When the model misses, what does it retrieve?: 91.5–99.4% of rank-1 misses for the four leading models are paired buggy variants, indicating a specific canonical-versus-near-clone separation failure.The comparison is defined over rank-1 misses whose retrieved snippets fail the tests.
  • 5.3 One near-clone is enough: pool-density ablation: 0.993 falls to 0.678 for the strongest system when retaining one near-clone, while the relative one-clone drop spans 27–49% across all 23 models.With zero near-clones retained, leading systems reach 0.93–0.99, showing that topical retrieval is not the hard part for those systems.
  • 5.4 Canonical-vs-best-distractor similarity gap: 66.8% and 78.4% of queries place the canonical below at least one paired distractor for Gemini Embedding 2 and Qwen3-Embedding-8B, respectively.The mean per-query cosine gap is −0.002 for both systems, so the sign is wrong despite near-indistinguishable similarities.

6 Discussion and Conclusion

With execution-verified near-clones in the pool, top-k retrieval remains strong while rank-1 correctness is brittle. The benchmark measures the correctness-discrimination burden passed to downstream verification rather than complete coding-agent failure.

  • 6 Discussion and Conclusion: The canonical scores below at least one paired distractor in 67–78% of queries on the leading systems.This directly measures functional discrimination when a near-clone candidate is present in the retrieval pool.
  • 6 Discussion and Conclusion: EXECRETRIEVAL measures the correctness-discrimination burden that candidate retrieval passes to downstream reranking, execution, or LLM examination.It does not measure the failure of complete coding-agent systems.

Limitations

The benchmark is deliberately scoped to execution-verified Python functions and mechanically mutated distractors in a closed corpus. Its runner, retrieval stage, reproducibility, scale, and generalization each impose additional boundaries.

  • Limitations: Python-only evaluation leaves cross-language generalization open.The pipeline is language-agnostic in design, but each new language requires its own runner.
  • Limitations: Mechanical single-edit distractors do not exhaust subtler real-world bugs or stylistic confounds.The distractors are LLM mutations rather than natural human-written bugs.
  • Limitations: The closed-world corpus makes exec@k incomparable to open-domain code-search numbers.All reported magnitudes are conditional on a near-clone candidate being present in the pool, while deployed-corpus frequency is unmeasured.
  • Limitations: The execution runner provides process isolation and a 5-second timeout but does not constrain filesystem or network access.The authors do not recommend using it on untrusted code outside this benchmark.
  • Limitations: EXECRETRIEVAL measures embedding-only first-stage retrieval, leaving cross-encoder and LLM reranking for future work.The benchmark evaluates the first retrieval stage rather than the behavior of complete downstream systems.
  • Limitations: Hosted-API embeddings are not permanently reproducible across provider model updates.Released embedding matrices and execution caches make rescoring deterministic despite live endpoint changes.
  • Limitations: The 939 self-contained queries are small relative to million-scale topical retrieval corpora and exclude repository-scale cross-file context.Per-query execution verification is the intentional cost of uniform, attributable single-edit failures.

B Generation Economics

The generation pipeline incurred substantial token usage and reported a native list-price cost, while validation limitations affect reproducibility budgeting.

  • Generation Economics: 915,178 prompt tokens and 7,083,062 completion tokens were consumed across 926 GPT-5.4 API calls.The completion total includes 5,871,712 hidden reasoning tokens.
  • Generation Economics: $108.53 is the reported native real-time list-price generation cost for the 926 instrumented entries.The headline uses list pricing despite approximately 57% of calls using the discounted Batch API.
  • Generation Economics: 62–70% end-to-end validation rates result when either prompt fix from Section 3.2 is missing.The reported cost would scale roughly inversely with the validation rate.
  • Generation Economics: The median query is solved by exactly 3 of 24 systems, while 88 queries are solved by none and 1 by every system.Figure 6 also reports per-domain exec@1 for the top-9 systems.

D Released Artifacts

The release packages the corpus, execution records, embeddings, evaluation machinery, statistical outputs, and environment metadata needed to reproduce ExecRetrieval analyses offline.

  • Released Artifacts: The release includes a 4,694-row corpus, 939-row query file, and metadata for 926 instrumented entries.Metadata includes deterministic IDs, generator information, timestamps, token counts, and latency.
  • Released Artifacts: The bundle contains 3,755 paired distractor descriptions, 46,458 execution-cache rows, and 23 saved dense-embedding matrices.These artifacts preserve bug explanations, execution outcomes, and model representations used in evaluation.
  • Released Artifacts: The release provides the full leaderboard and raw pairwise-test JSON for k ∈ {1, 3, 5, 10} across exec@k, execution_precision@k, and nDCG@k.Table 7 defines exec@k, execution_precision@k, and canonical-ID nDCG, with the three metrics coinciding at k = 1.
  • Released Artifacts: A runtime pip freeze, SHA-256 manifest, analysis scripts, and a one-command leaderboard reproduction script accompany the release.Table 7 reports exec@k for every system so figure-level claims can be verified from the paper alone.
  • Released Artifacts: The evaluation harness recomputes the entire leaderboard offline from frozen embedding matrices and diffs it against released results.It includes the subprocess executor, scoring engine, BM25 baseline, embedder scripts, and pairwise tests.

G Robustness Analyses: Edit Size and Stacked Mutations

The robustness analyses test whether deception depends on microscopic edits or changes when multiple verified mutations are stacked.

  • Robustness Analyses: The analyses are derived from released artifacts, and their scripts ship with the release.They address edit size and stacked mutations as potential explanations for the deception measurement.

G.1 Deception vs. edit size

Deception remains broadly stable across mutation size and stacking, indicating that larger or combined verified edits do not restore detectability for the analyzed embedders.

  • G.1 Deception vs. edit size: 1–540 characters span the mechanical edits, with a one-character median mutation across 3,745 pairs.The analysis aggregates 86,135 pair-configuration triples over 23 dense configurations.
  • G.1 Deception vs. edit size: |ρ| ≤0.07 indicates negligible association between edit size and per-pair deception.Relative edit size has ρ = −0.069, while absolute edit size has ρ = +0.035.
  • G.1 Deception vs. edit size: 39.3% is the overall deception rate for remove_edge_case_check mutations, the least deceptive type.Multi-line edits comprise 8.5% of mechanical pairs and account for the largest bucket’s dip.
  • G.2 Deception vs. number of stacked mutations: 4,633 execution-verified multi-mutation variants remain after discarding 13 compositions that accidentally pass all tests.The variants cover 915 of 939 queries and combine 2–4 disjoint line-block mutations.
  • G.2 Deception vs. number of stacked mutations: Deception stays within 1.7 percentage points of the single-mutation baseline, with no statistically distinguishable drop.The matched analysis uses 5,000 query-level bootstrap replicates and leaves deception near 45% at the most pessimistic interval edge.
  • G.2 Deception vs. number of stacked mutations: Stacking up to four verified bugs into one function does not restore detectability for the four analyzed local embedders.The analysis uses all-mpnet-base-v2, bge-base-en-v1.5, e5-base-v2, and gte-large under the release’s exact passage-side conventions.
Loading 2609.01865v1…