Code search engines, including the best neural embedding models, find functions mostly by reading their names. When the words in a developer's request and the words in the code do not overlap, which is the vocabulary mismatch or "lexical gap" problem, retrieval quality drops sharply. It collapses when identifiers are scrambled or code exists only in compiled form. We propose to stop matching words and match behavior instead. An LLM turns the natural-language query into a small executable specification: a reference implementation plus a set of probe inputs. The system repairs and sharpens that specification in an execution loop. It then runs every type-compatible candidate function on the probes and ranks candidates by how closely their outputs agree with the specification. A function's input–output behavior does not change when its variables are renamed or when it is compiled to assembly, so this matching signal is unaffected by the surface changes that break embedding models.
The idea connects three lines of work in a specific way. Execution serves as the verifier. Iterative refinement is applied to the query, not to a patch. The lexical gap is the regime where the method should pay off most. Two findings motivate it. Code only helps reasoning when it is actually run, not when a model imagines running it (Is Code Better Than Language for Algorithmic Reasoning?). Current code embeddings lean on identifier names as a crutch (CLARC).
Core Claim
On retrieval tasks where identifiers are randomized or code is compiled, ranking candidates by agreement on execution outputs should shrink the gap between "readable" and "neutralized" code far more than any method that reads code. The claim is also that refining the query-side specification through execution is what makes this work. Without the loop, hallucinated reference programs and uninformative probes produce a noisy signal.
The evidence gap is concrete. On CLARC, voyage-code-3 reaches 94.06 NDCG (a ranking-quality metric that rewards placing the correct item near the top) on standard Group 2 code but only 75.22 with randomized identifiers. It falls to 34.12 on Group 1 assembly, and text-embedding-3-large falls to 11.50 there (CLARC). CLARC also reports that fine-tuning on its training split does not close this gap. A behavior-matching retriever should, in principle, score the same on standard, randomized, and compiled versions of the same function. Measuring how close it gets to that invariance is the central test.
Relation to Prior Work
Three papers are the closest neighbours, and each leaves out a piece this proposal needs.
CoSQA+ generates unit tests and executes them to decide whether a snippet matches a query. It reaches 93.9% labeling accuracy against 89.1% for human experts, which is strong evidence that execution judges relevance better than reading. That pipeline, however, runs offline, pair by pair, to build a benchmark. We instead build one executable specification per query, reuse it across the whole candidate pool at inference time, and refine it using signals from that pool.
Generation-Augmented Query Expansion for Code Retrieval (GACR) drafts hypothetical code to expand the query. Its own ablation attributes nearly all of the gain to the generated function name, while the unexecuted body contributes little. That is exactly the lexical cue that disappears under identifier randomization. We execute the draft and discard its surface form entirely.
Hypothesis Search supplies the method we reuse. It writes programs from verbal hypotheses and debugs them against examples in an execution loop. It operates only on self-contained puzzles with no retrieval, so we point that loop at the query of a search system.
On the reasoning side, Retro* reranks with natural-language reasoning against a rubric. It is the strongest "read and judge" competitor. Its reported numbers are on BRIGHT (36.6 nDCG@10 at 7B, 40.6 at 32B with 16 samples), not on code with neutralized identifiers.
Two findings constrain the design. The observation that LLMs mis-simulate correct code roughly a third of the time (Is Code Better Than Language for Algorithmic Reasoning?) predicts that reading-based rerankers will struggle once names are gone. The observation that refinement gains plateau after 2–3 rounds (Yan et al.) caps our loop budget at a small number of rounds.
Research Program
The system has three stages.
Stage 1: build the specification. From the natural-language query, an LLM produces $k$ independent reference drafts and a pool of probe inputs typed to plausible signatures.
Stage 2: refine the specification. A refinement loop of at most three rounds runs the drafts in a sandbox and applies three repair rules. Drafts that crash are repaired from their tracebacks. Probes on which the drafts disagree are either resolved by asking the LLM to reconcile the draft with the query text, or flagged as ambiguous and down-weighted. Probes on which all top candidates behave identically are replaced, since they carry no discriminative information. This last rule makes the pool of candidates shape the probes, a form of active testing absent from both CoSQA+ and GACR.
Stage 3: match candidates. Candidates are filtered by type signature, which survives identifier randomization. Each surviving candidate is executed on the refined probes. Because argument order and conventions differ between the specification and the candidate, we search over type-consistent argument permutations and a small LLM-written adapter, keeping the best one. The score of candidate $c$ is
$$s(c) = \max_{a \in A(c)} \frac{1}{\sum_{x \in P} w_x} \sum_{x \in P} w_x \, \mathbb{1}\left[c(a(x)) \simeq r(x)\right],$$
where $P$ is the refined probe set, $w_x$ is the weight on probe $x$ (lowered when reference drafts disagree on it), $r(x)$ is the consensus reference output, $A(c)$ is the set of allowed adapters, and $\simeq$ is equality with tolerance for floating point.
For assembly and WebAssembly candidates, we execute the compiled artifact directly through a generated harness. Execution needs no source text, which is precisely where readers fail.
Because execution is run over all type-compatible candidates rather than a top-100 list from a first-stage retriever, the method is not bounded by first-stage recall, which the research file identifies as a limit on rerankers. We will report the resulting compute cost honestly, measured in sandbox seconds per query. We will also report a cheaper variant that executes only the top-$N$ candidates from an embedding model.
Known failure regimes will be measured, not hidden. These include functions with side effects, file or network I/O, heavy repository dependencies (CLARC's higher dependency tiers), and nondeterminism. Results are broken down by tier, and the fraction of candidates that could not be executed is reported.
Baselines
Do-nothing reference. The first reference is BM25 and voyage-code-3 embeddings applied directly to the query. This is the setting CLARC reports: 94.06, 75.22, and 34.12 NDCG on standard, randomized-identifier, and assembly code, and 11.50 for text-embedding-3-large on assembly. We rerun these on the identical evaluation pairs with CLARC's metric, so that our numbers are directly comparable to the published ones. Beating this reference means exceeding 75.22 on randomized Group 2 and 34.12 on Group 1 assembly. More importantly, it means cutting the standard-to-neutralized drop by at least half.
Strongest reading-based competitor. The second baseline is a Retro-style pointwise reasoning reranker (Retro*). It uses the same base LLM as our system, the rubric prompt, and multiple reasoning samples. It is given a sampling budget matched to our total LLM tokens, and it reads the same candidate pool. It is the strongest competitor because it already turns test-time compute into retrieval gains across large lexical gaps. We found no reported result on Lacuna for Retro on CLARC or CoSQA+. We will therefore report its only published numbers (BRIGHT: 36.6 and 40.6 nDCG@10) as context, and run it ourselves on our benchmarks. Beating it means higher NDCG at equal LLM tokens on neutralized code, with the margin growing from randomized identifiers to assembly.
Code-generation expansion. The third baseline is GACR-style expansion: one unexecuted draft, embedded alongside the query and retrieved with voyage-code-3 (GACR). Its reported result is a 27.8% relative improvement over GraphCodeBERT on PHP in CodeSearchNet. We have no Lacuna result for it on CLARC.
Ablations that isolate the key ingredients. The first ablation drops the refinement loop, keeping one draft and the initial probes, unrepaired. The second keeps the loop but replaces execution with LLM self-critique of the drafts. This tests whether execution, not merely more LLM calls, drives any gain, mirroring the Route 2 versus Route 3 contrast in the algorithmic-reasoning study. The third removes candidate-driven probe replacement.
All systems share the same base LLM, the same candidate pools, and the same hyperparameter-search budget on a CLARC training-split dev set. Token and wall-clock cost are reported for every row.
Why not just…?
Why not just have an LLM restore meaningful identifier names and then embed as usual? This is the most serious threat on randomized-identifier code. If an LLM can guess that f_x9q is binary_search, embeddings recover much of their lost accuracy cheaply. We will run this rename-then-embed pipeline with the same LLM. Our expectation is that it helps on source code but degrades badly on assembly, where "renaming" becomes full decompilation. We also expect it to fail where behaviorally equivalent code looks different, the case CoSQA+ shows human readers miss. If rename-then-embed matches us on randomized source, we will say so plainly and narrow the claim to compiled code and functional-equivalence queries. We will also test the combination of the two methods.
Why not just use a strong reasoning reranker that reads the code? Reading requires the model to simulate execution in its head. The finding that LLMs mis-simulate correct code about 33% of the time, and that code without execution gains only 0.15 points over plain language on algorithmic tasks (Is Code Better Than Language for Algorithmic Reasoning?), predicts this breaks down once names are removed. Text-only self-checking also tends to rationalize its own errors (Solving Challenging Math Word Problems Using GPT-4 Code Interpreter with Code-based Self-Verification). The token-matched Retro*-style baseline settles this directly.
Why not just fine-tune the embedding model on neutralized code? CLARC ran this experiment: fine-tuning raised scores on standard code but left the standard-versus-neutralized gap open. We still include a fine-tuned bi-encoder as a row, so readers can see whether that finding holds under our evaluation.
Proposed Experiments
Primary benchmark. The primary benchmark is CLARC's 1,245 evaluation pairs, evaluated on standard, randomized-identifier, and assembly/WebAssembly variants, with results reported by dependency tier and NDCG as the metric.
Decisive check 1: invariance. For the same underlying function, compare our score across the three surface forms. Embedding models lose roughly 19 NDCG points going to randomized identifiers and about 60 going to assembly. Our method should show a small fraction of that loss on executable functions. If our assembly score falls far below our standard-code score even on functions we could execute, the invariance argument is wrong.
Decisive check 2: refinement. The full system must beat both the one-shot-execution ablation and the self-critique-without-execution ablation at equal tokens. Otherwise the iterative component is not doing work.
Secondary benchmark. CoSQA+_verified (1,000 Python pairs) tests whether behavior matching finds functionally matching code that differs lexically. No reported retrieval result was found on Lacuna for this split; the published 93.9% is labeling accuracy, not retrieval. The execution-verified labels make this benchmark a natural fit.
Reporting. We report sandbox cost per query and the fraction of candidates that were not executable, and we identify where the method stops applying.
References
- Is Code Better Than Language for Algorithmic Reasoning?
- CLARC: C/C++ Benchmark for Robust Code Search
- CoSQA+: Pioneering the Multi-Choice Code Search Benchmark with Test-Driven Agents
- Generation-Augmented Query Expansion For Code Retrieval
- Hypothesis Search: Inductive Reasoning with Language Models
- Retro*: Optimizing LLMs for Reasoning-Intensive Document Retrieval
- CodeTransOcean: A Comprehensive Multilingual Benchmark for Code Translation
- Solving Challenging Math Word Problems Using GPT-4 Code Interpreter with Code-based Self-Verification