EVOR: Evolving Retrieval for Code Generation

1 Introduction

• Existing RACG approaches use a given or rewritten query to retrieve from a static knowledge base containing a single information type.The introduction motivates using additional sources, including web content and code snippets, and notes that execution can provide information on the fly.Source: §1 · p. 1
• EVOR updates queries and knowledge bases using execution feedback and LLM outputs, and adds web search content, execution feedback, and generated code snippets to library documentation.The pipeline aims to retrieve more pertinent information through these updates.Source: §1 · pp. 1–2
• 18.6%: EVOR outperforms DocPrompting on average using CodeLlama.The introduction reports average performance across the four EVOR-BENCH datasets.Source: §1 · p. 2
• EVOR-BENCH comprises four datasets for realistic RACG settings involving frequently updated libraries and long-tail programming languages.The introduction identifies Scipy and Tensorflow updates and the Ring and Pony languages as the two settings.Source: §1 · p. 2
• Analyses identify synchronous evolution and diverse knowledge sources as critical to EVOR, which can also be combined with other code-generation approaches for further improvement.The introduction includes agent-based approaches among the combinations.Source: §1 · p. 2

2 Evolving Retrieval

• EVOR’s core design synchronously evolves queries and diverse knowledge bases to retrieve information for code generation in domains unfamiliar to the LLM.The section frames this as an alternative to relying on static knowledge bases.Source: §2 · p. 2

2.1 Query evolution

• After an initial retrieval using the problem statement, an LLM generates each new query from the problem, prior program, test inputs, and execution feedback.The updated query is used for retrieval in the next iteration.Source: §2.1 · p. 2

2.2.1 Construction

• The knowledge soup draws on web search, documentation, compiler or interpreter feedback, and code snippets that demonstrate usage.The paper also collects syntax-verified snippets and LLM-generated code solutions.Source: §2.2.1 · pp. 2–3

2.2.2 Evolution

• Successful programs are added as syntax-correct examples, while unsuccessful programs are added with their error messages, enriching the knowledge base over iterations.The paper identifies execution feedback and code snippets as the primary contributors to knowledge-base evolution.Source: §2.2.2 · p. 3

2.3 EVOR Pipeline

• Each iteration retrieves with the current query, generates a program, executes it on LLM-generated inputs, and updates the knowledge base with the program or its error pair.The experiments cap the process at 30 iterations and stop after successful execution or the same error in three consecutive iterations.Source: §2.2.1 · p. 3, §2.3 · p. 4

2.4 Datasets

• EVOR-BENCH contains four datasets: modified Scipy and Tensorflow libraries, plus Ring and Pony problems for long-tail languages.For each problem, the authors manually write a reference solution and annotate oracle documentation.Source: §2.4 · p. 4

3 Experiment

• The evaluation uses ChatGPT and CodeLlama and includes modified Scipy and Tensorflow libraries plus the less-common languages Ring and Pony.The library modifications avoid using real updates that may appear in LLM training data.Source: §3 · p. 4

3.1 Baselines

• The baselines include vanilla generation, MPSC, ExeDec, Reflexion, and DocPrompting, which retrieves documentation without evolving queries or its knowledge base.The comparison also includes combinations of EVOR with other methods.Source: §3.1 · pp. 4–5

3.2 Default EVOR Configuration

• The experiments use ChatGPT for query evolution and test-input generation, vary ChatGPT and CodeLlama as code generators, and default to execution accuracy (pass@1).The default retrieval model is INSTRUCTOR-xl, and both code generators have a 4,096-token context limit.Source: §3 · p. 4, §3.2 · p. 5

3.3 Results

• Existing code-generation methods improve by less than 2% on average over vanilla generation with CodeLlama, while DocPrompting significantly surpasses MPSC, ExeDec, and Reflexion.The three methods retain 0 execution accuracy on Ring; the passage attributes the contrast to the need to retrieve and use external information.Source: §3.3 · p. 5
• EVOR adds 16.1% and 16.2% absolute gain over DocPrompting with ChatGPT and CodeLlama, respectively.The comparison is reported for EVOR-BENCH.Source: §3.3 · p. 5, Table 2 · p. 5
• Combining EVOR with MPSC, ExeDec, or Reflexion yields up to 2.6% average performance improvement with ChatGPT.The paper presents this as evidence of EVOR's flexibility for integration with existing approaches.Source: §3.3 · p. 6

4.1 Synchronous evolution

• EVOR's synchronous evolution of queries and knowledge outperforms evolving either one alone across all EVOR-BENCH datasets.The ablation also finds that evolving either queries or knowledge improves results over evolving neither.Source: §4.1 · p. 6

4.2 Diverse Knowledge

• Adding documentation to execution feedback and code snippets raises CodeLlama's average result from 25.3% to 32.2% (+6.9%) when both queries and knowledge evolve.Without evolution, the corresponding result rises from 15.9% to 20.4% (+4.5%); more diverse sources generally improve performance, with larger gains under evolution.Source: §4.2 · pp. 6–7, Table 4 · p. 6

4.3 Repo-level Code Generation

• On SWE-bench-Lite, EVOR outperforms traditional RAG by a large margin and is comparable with SWE-agent; combining EVOR with SWE-agent improves on both.The evaluation uses repository content as documentation and tests GPT-4-1106 and Claude-3-opus settings.Source: §4.3 · p. 7, Figure 2 · p. 7

4.4 Effective Token Usage

• EVOR has significantly higher performance than DocPrompting at every tested token level for both ChatGPT and CodeLlama, with larger gains as token consumption increases.The comparison uses pass@t and token thresholds from 4,000 to 24,000.Source: §4.4 · p. 7

LLM-based Code Generation

• Many code-generation methods are evaluated on familiar tasks where LLMs can perform well using internal knowledge, while this work studies updated libraries and less-common languages requiring external knowledge.The paper characterizes this setting as more realistic and challenging for LLMs.Source: §5 · p. 8

Retrieval-Augmented Generation

• Prior RACG work includes documentation-based code generation, API retrieval, repository-level iterative generation, and query rewriting; EVOR adopts synchronous evolution of queries and diverse knowledge for external-information code generation.The paper describes this combination as novel to its knowledge.Source: §5 · p. 8

Code Execution

• Prior code-execution work uses execution results for program selection, interactive coding, and code refinement; EVOR uses execution feedback to evolve queries and knowledge in RACG.Source: §5 · p. 8

• EVOR achieves two to four times execution accuracy compared to existing code-generation methods.Source: §6 · p. 8
• EVOR can be combined with existing methods, including agent-based approaches, to further improve performance on challenging tasks such as repo-level code generation.Source: §6 · p. 8
• Analysis finds complementary benefits from synchronous query-and-document evolution and more diverse knowledge sources, with larger performance margins as sources diversify.Source: §6 · p. 8

• Multiple rounds of retriever, LLM, and executor interactions are required to produce the code answer.Source: §7 · pp. 8–9
• The iterative process can increase latency, a concern for real-time applications.Source: §7 · p. 9
• The iterative process can increase energy consumption, a concern in energy-constrained environments; future work could seek more efficient architectures while maintaining or improving performance.Source: §7 · p. 9

• Biased or incorrect retrieved code snippets can propagate errors or introduce vulnerabilities in generated code.Source: §8 · p. 9
• Retrieval can raise privacy and security concerns if sensitive code snippets are inadvertently included.Source: §8 · p. 9
• The paper identifies careful source curation, robust validation, and continuous monitoring as ways to address these risks.Source: §8 · p. 9

A Dataset curation

• The appendix covers curation for updated libraries and long-tail languages, plus test-case construction for Ring and Pony.Source: A Dataset curation · p. 12

A.1 Library-oriented data collection

• Updated-library APIs use renamed names or arguments, merged APIs, and new classes, with ground-truth solutions rewritten for the new APIs.Documentation is modified, oracle documentation is annotated for each question, and DS-1000 test cases are reused.Source: §A.1 · p. 12

A.2 Language-oriented data collection

• For Ring and Pony problems, function signatures are adapted and oracle documentation identifies the grammar used in each ground-truth solution.The selected syntax documentation is concatenated into a minimum document for each question.Source: §A.2 · p. 12

A.3 Test-case generation for language-oriented data

• Long-tail-language tests are built from manually checked validation and solution scripts, expanded to 200 cases per problem through mutation, and reduced while preserving their right-or-wrong judgments.Generated cases must pass both scripts, finish within one second, and match the solution script's answer; reduction uses code coverage, mutant killing, and LLM sample killing.Source: §A.3 · p. 12

B Prvate Library

• Compared with TorchDataEval, MonkeyEval, and BeatNumEval, the updated-library datasets add API combinations and new classes beyond simple renaming, which the authors say may cover broader real-life updates.The authors suspect CodeLlama may have trained on those earlier GitHub-hosted benchmarks because they were available before its release, limiting their value for measuring generalization.Source: B Prvate Library · p. 13

C LLM-generated program inputs

• In an ablation, ChatGPT and CodeLlama generated test inputs that performed well as syntax verifiers when run against gold programs.Inputs were counted as valid when execution reported no error; the evaluation used five generated inputs per problem.Source: C LLM-generated program inputs · p. 13

D Sample code snippets and execution feedback

• LLMs are prompted to write short usage scripts for each documented function.These scripts provide sample code snippets for the knowledge base.Source: D Sample code snippets and execution… · p. 13
• Each generated script is executed, and failures are stored as (code, error) pairs.Source: D Sample code snippets and execution… · p. 13
• Successful executions are treated as snippets demonstrating syntax and function usage.Source: D Sample code snippets and execution… · p. 13

F More Experimental Setting

• The experimental prompt allocates up to 300 tokens to code snippets, prioritizes other knowledge before documentation, and retains correct-syntax examples during iterative retrieval.The process rectifies code with syntax errors; Table 5 also notes that unusually high zero-shot CodeLlama accuracy on three private libraries suggests possible data leakage.Source: F More Experimental Setting · pp. 13–14, Table 5 · p. 14

G Web Search

• Google search fails to find relevant Pony knowledge in the example, returning C++ guidance and long, mixed-source content that can burden LLM filtering.Figure 4 illustrates top-three results spanning tutorials, blogs, and Q&A discussions.Source: G Web Search · p. 14, Figure 4 · p. 14

E Cost Analysis

• 2.9% and 4.1% average execution-accuracy gains over Single-time-Q cost around 25% more tokens; active retrieval adds 15.4% and 15.1%, with more than 2 times the tokens for both models.The gains are for ChatGPT and CodeLlama, respectively.Source: E Cost Analysis · p. 13, Table 7 · p. 15

H Retrieval Model

• Dense retrievers significantly outperform BM25, and SFR-Embedding-Mistral performs best; EVOR uses INSTRUCTOR-xl after considering performance and cost.The gap among dense retrievers is not significant.Source: Figure 5 · p. 15, H Retrieval Model · p. 15

I Long-context Model

• ChatGPT performs best with 4k tokens of external knowledge, and longer contexts do not further improve performance.Possible explanations include that the gold documentation fits within 4k and that relevant content in long contexts may receive low attention.Source: I Long-context Model · p. 16

J Personally Identifying Infomation

• The authors report that collected code-generation data contains no information identifying individuals and no offensive content.Source: J Personally Identifying Infomation · p. 16

K Intended use

• EVOR is intended for customized code generation, while EVOR-BENCH is intended to evaluate RACG systems.Source: K Intended use · p. 16

M Data Documentation

• EVOR-BENCH is English-language data adapted from DS-1000, originally collected from StackOverflow, and from LeetCode.Source: M Data Documentation · p. 16

N Machines

• The experiments use Nvidia A100 GPUs and take around one hour per EVOR-BENCH dataset, or around 24 hours overall.Source: N Machines · p. 16

O Packages

• The paper uses the latest pip or conda implementation for all code packages.Source: O Packages · p. 16

P Instructions for Human Annotators

• Human annotators are instructed to write code in the target language and identify documentation for the syntax used.Source: P Instructions for Human Annotators · p. 16

Q Data Consent

• The dataset includes DS1000 data released under CC-BY-SA-4.0 and LeetCode data, which the authors state they are eligible to use.Source: Q Data Consent · p. 16