🤖 AI

Do not copy and paste! Rewriting strategies for code retrieval

This paper introduces and evaluates a hierarchy of LLM-based rewriting strategies for code retrieval, demonstrating that while full natural-language query-corpus rewriting significantly boosts performance for lightweight encoders, its benefits are context-dependent and can be predicted by a new token entropy metric (Delta H) to optimize the cost-benefit trade-off of rewriting.

Original authors: Andrea Gurioli, Federico Pennino, Maurizio Gabbrielli

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Gurioli, Federico Pennino, Maurizio Gabbrielli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific recipe in a massive, chaotic library. The problem is that the library's search engine (the "encoder") is a bit literal-minded. It doesn't really understand what a recipe does; it just looks at the specific words and formatting used. If you search for "how to make a cake" but the recipe in the library is titled "Baking a Sponge," the search engine might miss it because the words don't match perfectly, even though the meaning is identical.

This paper is about teaching the search engine to look past the surface-level words and understand the actual meaning of the code. The authors tested a few different ways to "translate" the code before the search engine looks at it.

Here is the breakdown of their experiment and findings, using simple analogies:

The Problem: The Literal Search Engine

Current code search tools often get confused by different ways of writing the same thing. It's like if a librarian only found books if you used the exact same spelling and font as the book cover. If you ask for "how to loop," but the book says "iterate through a list," the librarian might say, "I don't have that."

The Solution: The "Translator" (Rewriting)

The authors tried using a smart AI (an LLM) to rewrite the code before the search engine sees it. They tested three different "translation styles":

Stylistic Rephrasing: Think of this as a "style fix." The AI rewrites the code to look cleaner and more uniform, like editing a messy handwritten note into neat print, but keeping it as code.
PseudoCode: This is like translating the code into a "simplified instruction manual." It's not quite human language, but it's not strict code either. It's like saying, "First, check the numbers, then add one, repeat until found."
Full Natural Language: This is the most drastic change. The AI translates the code entirely into a plain English sentence. Instead of code, the search engine sees: "Return the smallest missing positive number by ignoring negatives and counting up from one."

The Two Ways to Use the Translator

The authors tested two ways to apply these translations:

The "Offline" Method (Corpus Only): Imagine you rewrite the entire library of books once and put them on the shelf. Then, when a user asks a question, you search the rewritten books using the original question.
- The Result: This often failed. It was like translating all the books into French but asking the question in English. The search engine got confused because the question and the answers didn't speak the same "language" anymore.
The "Online" Method (Query + Corpus): Here, you translate the library and you translate the user's question into the same style before searching.
- The Result: This worked much better. It's like having a bilingual librarian who translates both the question and the books into the same language before matching them.

Key Findings

1. The "Full Translation" Wins (for Code)
When the search engine was looking for code, translating the code into Full Natural Language (Method #3) combined with translating the question (Online Method) gave the biggest boost.

Analogy: It's like realizing that for a specific type of puzzle, describing the picture in plain English helps you find the right piece faster than trying to match the puzzle piece shapes directly.
The Catch: This only helped when the search engine was "lightweight" (not very smart on its own). If the search engine was already very strong, rewriting didn't help much.

2. The "Offline" Trap
Rewriting the library but not the question (Offline Method) actually made things worse in about 62% of cases.

Analogy: It's like translating a cookbook into Spanish but asking for a recipe in English. The librarian can't match the request to the book, so you get nothing.

3. The "Entropy" Crystal Ball
The authors discovered a clever trick to predict if rewriting will help before you even run the search. They measured something called "Token Entropy" (a fancy way of measuring how diverse and varied the words are).

The Metaphor: Imagine the code as a bag of marbles. If the bag has only 3 colors of marbles (low entropy), the search engine gets confused easily. If the rewriting process turns that bag into a rainbow of many colors (high entropy), it usually means the search engine will do better.
The Magic: They found that if the rewriting process significantly increases this "colorfulness" (entropy), it's a safe bet that the search results will improve. This acts as a cheap "test drive" to see if the translation is worth the effort.

The Bottom Line

If you have a simple search tool and you are looking for code, translating the code into plain English (and translating the question too) is a powerful way to fix the search. However, you shouldn't do this if your search tool is already very smart, or if you are searching for things that are already written in plain English.

The authors also gave us a "litmus test" (the entropy check) to tell us when this translation trick will actually work, saving us from wasting time on methods that won't help.

Technical Summary: Rewriting Strategies for Code Retrieval

Problem Statement

Embedding-based code retrieval systems frequently suffer from a shallow understanding of program behavior, often overfitting to surface-level syntactic cues rather than semantic meaning. This leads to semantically distinct code snippets being mapped to similar vector representations. While prior work has attempted to mitigate this by using Large Language Models (LLMs) to rephrase queries and corpora into a normalized style, two critical questions remain unresolved:

Representational Shift: How much does shifting the representation level (e.g., from code to natural language or pseudo-code) actually improve retrieval?
Cost-Benefit Justification: When is the computational cost of an online LLM call per query justified, and can rewriting be performed offline?

Existing methods typically operate at a single representational level (code) and often treat intermediate representations (like pseudo-code) as transient bridges rather than final retrieval targets. Furthermore, they generally lack diagnostics to predict when rewriting will be beneficial.

Methodology

The authors conduct a systematic study evaluating a hierarchy of three rewriting strategies under two augmentation regimes:

Rewriting Strategies:
- Stylistic Rephrasing: Normalizing code syntax and style (following Li et al., 2024).
- NL-enriched PseudoCode: Converting code into structured pseudo-code with natural language comments, used directly as the retrieval representation.
- Full Natural Language (NL) Transcription: Converting code snippets entirely into natural language descriptions, used directly as the retrieval representation.
Augmentation Regimes:
- Joint Query–Corpus (QC, Online): Both the query and the corpus are rewritten by the LLM before embedding.
- Corpus-Only (C, Offline): Only the corpus is rewritten; queries remain in their original form.
Experimental Setup:
- Benchmarks: Six datasets from the CoIR suite (covering code-to-code, text-to-code, and hybrid modalities).
- Encoders: Five encoders ranging from general-purpose to code-specialized (e.g., MoSE-18, CodeXEmbed, E5-Base-V2).
- Rewriters: Three independent model families (Qwen3-Coder, DeepSeek-Coder-V2, Codestral) to ensure robustness against rewriter-specific artifacts.
Diagnostics: The paper introduces two metrics to analyze the effect of rewriting:
- $\Delta H$ (Token Entropy): The change in Shannon entropy of input tokens, measuring lexical diversity.
- $\Delta \bar{s}$ (Embedding Cosine): The change in mean pairwise cosine similarity of embeddings, measuring representation isotropy (discriminative spread).

Key Contributions

New Retrieval Representations: The authors are the first to evaluate NL-enriched PseudoCode and snippet-level Natural Language as direct retrieval targets, rather than transient intermediates.
Systematic Comparison: A controlled evaluation across three rewriting levels, two augmentation regimes, multiple encoders, and three rewriter families.
Diagnostic Framework: The introduction of $\Delta H$ and $\Delta \bar{s}$ as representation-level diagnostics. Crucially, the paper demonstrates that $\Delta H$ serves as a rewriter-agnostic predictor for retrieval gains under the QC regime.
Cost-Benefit Framework: The study reframes LLM rewriting not as a universal fix, but as a remediation layer with specific conditions for efficacy.

Results

Effectiveness of NL+QC: Full Natural Language rewriting with joint query-corpus augmentation (NL+QC) yields the largest performance gains. On the CT-Contest benchmark (code-to-code), it improved MoSE-18's NDCG@10 from 0.23 to 0.74 (+0.51 absolute). It remains the best or tied-best strategy for all three rewriters on code-heavy tasks.
Inefficacy of Corpus-Only (C): Corpus-only rewriting degrades retrieval performance in approximately 62% of configurations (56 out of 90). This is attributed to a modality mismatch between the rewritten corpus and the original queries. QC outperforms C in 78 out of 90 paired comparisons.
Encoder Dependency: Gains scale inversely with encoder capacity. Lightweight encoders (e.g., MoSE-18) benefit significantly from rewriting, while strong encoders (e.g., Qwen3-Emb) often see flat or negative returns, suggesting rewriting is most valuable as a remediation for weaker models.
Query Modality: The abstraction hierarchy (Rephrase < Pseudo < NL) holds for code-to-code tasks but breaks down for text-to-code tasks. When queries are already in natural language, rewriting the corpus to NL erases residual syntactic signals without creating new alignment, often hurting performance.
Predictive Power of $\Delta H$ : Under the QC regime, the change in token entropy ( $\Delta H$ $Δ H$ ) is a significant predictor of retrieval gain.
- For Codestral: $\rho = +0.593$ ( $p < 0.001$ ).
- For DeepSeek: $\rho = +0.274$ .
- Pooled (non-Qwen): $\rho = +0.436$ ( $p < 0.001$ ).
- This correlation holds across different rewriter families, establishing $\Delta H$ as a cheap, rewriter-agnostic proxy to decide if rewriting will pay off before running retrieval.

Significance and Claims

The paper claims to reframe LLM rewriting for code retrieval as a cost–benefit decision rather than a standard preprocessing step. The authors conclude that:

Rewriting is most effective as a remediation layer for lightweight encoders handling code-dominant queries.
It offers diminishing returns for strong encoders or queries that are already rich in natural language.
The $\Delta H$ metric provides a practical, low-cost mechanism for practitioners to predict whether a specific query/corpus pair will benefit from rewriting, allowing them to avoid unnecessary LLM calls when the diagnostic indicates low potential gain.

The authors explicitly state that their findings are modest regarding closed-source models and low-resource languages, noting these as limitations. They emphasize that while rewriting improves retrieval, it inherits the rewriter's biases and hallucination risks, recommending human audit and source pointers for deployment.