On Sample-Efficient Code Generation (2023)

Abstract: Large language models often struggle to predict runtime behavior in code generation tasks, leading to a reliance on rejection sampling (best-of-n) to generate multiple code snippets then select the best. Our distinction is reducing sampling costs, without compromising generation quality. We introduce EFFICODE, a novel framework that prioritizes sampling on test problems that models can solve. We show how EFFICODE estimates solvability to optimize computational costs during multiple sampling. Based on empirical evidence, EFFICODE consistently demonstrates reduced sampling budgets while maintaining comparable code generation performance, especially when problems are challenging. In addition, utilizing EFFICODE to rank sampled code snippets also shows its effectiveness in answer code selection for reducing temporal costs, by not requiring any execution or test case generation.

## introduction recently, large language models (llms) have achieved success in code generation, aiming at synthesizing a functionally correct program based on a natural language problem description @xcite . ensuring functional correctness is a rigorous objective, as a single token error during generation can render the entire output incorrect, while some grammatical and semantic errors in natural language are tolerable to human readers. to achieve rigor despite noise during generation, existing approaches utilize rejection sampling (multiple sampling then selecting the best) to increase the likelihood of finding a correct code among the candidates @xcite @xcite . in this context, the widely used metric is pass@k @xcite , which assigns a score of 1 if at least one of the k ˚is also affiliated with the university of illinois chicago. : corresponding author. however, the use of multiple sampling in code generation incurs high computational costs. while considerable efforts have been made to optimize the computational expense of pre-training, including addressing its environmental impact @xcite , resource-intensive inference from excessive sampling have been largely overlooked. to motivate, alphacode @xcite generates 1 million code samples for each competition-level problem, resulting in hundreds of petaflops days of computation-equivalent to the cost of pre-training the model. in addition, recent approaches @xcite @xcite self-validate the sampled code, by executing them with (generated) test cases. this results in a significant response time overhead, as the samples are often inefficiently implemented and may cause time-outs that take several seconds @xcite . thus, there is a critical need to reduce the expense of multiple sampling and refining, for deploying an industry-scale code generation with efficiency and sustainability. in our research, we aim to minimize the computational and temporal costs in code generation by reducing the sample size and avoiding execution in validation without compromising accuracy. figure 1 illustrates the contrast between conventional sampling with a uniform sampling cost of k and our proposed approach, referred to as efficode, which prioritizes the necessary k samples on average (k ă k) with the following characteristics: first, necessary: we prioritize investing the sampling budget in solving simple problems that terminate early (e.g., x 3 in figure 1a ), or avoiding wasting resources on hard problems that never terminate (e.g., x 1 in figure 1a ), unlike conventional sampling investing equally to all problems. to achieve this, we propose a solvability estimator, which determines if a problem is likely to be solvable based on either 1) producing fewer errors, or 2) close to the problems successfully solved in the past. second, adaptive: we can assess the correctness of a partially decoded sample even before its completion. in contrast, conventional sampling continues decoding until their completion without verification. this adaptability allows us to make more informed decisions during the decoding process to potentially save computational resources by terminating the decoding early. in our main experiment, we validate the effectiveness of efficode in improving the sample efficiency of gpt-3.5 (openai, 2022) on code-contests @xcite , humaneval @xcite , and mbpp @xcite benchmarks. in addition, we empirically confirm the effectiveness of using efficode as a ranker to select correct code for reducing temporal costs, without requiring any code execution. in summary, the key contributions of this study are as follows: ## preliminaries in this section, we define code generation task and its characteristic of requiring multiple sampling. next, we explain our research goal, sample efficiency. code generation. given a set of problems x and a code generation model θ, code generation is the task of synthesizing a correct solution code for each problem x i p x: ## efficode efficode is a novel framework that aims to achieve sample-efficient code generation by estimating the solvability for each problem, then prioritizing the problems to allocate the sampling budget. ## experimental setup we evaluate the effectiveness of efficode by assessing its impact on the sample efficiency of gpt-3.5-turbo-0301 (openai, 2022), a sibling model of instructgpt @xcite . throughout the experiments, we use nucleus sampling @xcite with the top p " 0.95 and the temperature t " 0.8 @xcite @xcite . the implementation details for efficode is explained in appendix a. ## conclusion this paper studies sample efficiency in code generation, which significantly affects the computational/temporal costs and environmental consequences yet has been neglected. our proposed approach efficode prioritizes sampling on test problems by estimating solvability. we conduct extensive experiments on the codecontests, humaneval, and mbpp benchmarks, consistently showing the improved sample efficiency. additionally, effi-code can be used as correct code selection while reducing temporal costs by alleviating code execution.