Functional Overlap Reranking for Neural Code Generation (2024)

Abstract: Code Large Language Models (CodeLLMs) have ushered in a new era in code generation advancements. However, selecting the best code solutions from all possible CodeLLM outputs remains a challenge. Previous methods often overlooked the intricate functional similarities and interactions between solution clusters. We introduce SRank, a novel reranking strategy for selecting the best solutions from code generation, focusing on modeling the relationships between clusters of solutions. By quantifying the functional overlap between solution clusters, our approach provides a better ranking strategy for code solutions. Empirical results show that our method achieves remarkable results on the pass@1 score. For instance, on the Human-Eval benchmark, we achieve 69.66% in pass@1 with Codex002, 75.31% with WizardCoder, 53.99% with StarCoder, and 60.55% with CodeGen, surpassing state-of-the-art code generation reranking methods such as CodeT and Coder-Reviewer on the same CodeLLM by a significant margin approx 6.1% improvement on average. Even in scenarios with a limited number of sampled solutions and test cases, our approach demonstrates robustness and superiority, marking a new benchmark in code generation reranking. Our implementation can be found at https://github.com/FSoft-AI4Code/SRank-CodeRanker.

## introduction recent advancements in language models tailored for code, known as code large language models (codellms) @xcite @xcite @xcite @xcite @xcite , have garnered significant interest, particularly due to the expansion of large-scale language models and the volume of pre-training data @xcite . a primary utility of codellms is their capacity to generate code given natural lan-guage descriptions written by humans @xcite @xcite . however, prior studies @xcite have highlighted that the sequences generated by these models can be prone to errors, especially when likelihood-based decoding techniques like greedy search and beam search are employed. alternatively, sampling-based decoding techniques @xcite extract multiple solutions from the model's multinomial distribution. this method generates a wide range of code solutions, many of which are correct @xcite . as a result, there is a growing interest in developing reranking strategies for code generation @xcite @xcite @xcite , with the goal of sorting through an abundance of sampled solutions to identify high-quality and accurate ones. the goal of reranking is to organize the set of candidate programs so that accurate programs are prioritized. @xcite , @xcite , and @xcite have clustered code solutions based on their functionality, then used cluster-specific data to determine ranking scores. given that language models frequently produce code solutions that differ syntactically but are semantically analogous, functional clustering narrows the candidate pool. the emphasis then shifts from ranking individual solutions to ranking clusters themselves. previous ranking strategies, such as alphacode @xcite and @xcite , provide approaches to clustering and reranking code solutions. while alphacode @xcite focuses on identical outputs from model-generated test inputs, @xcite focuses on solutions that pass model-generated test cases. the coder-reviewer approach @xcite , inspired by collaborative software development, uses a dualmodel system to cross-check generated programs against language instructions. however, by treating clusters in isolation, they fail to model potentially informative functional similarities and interactions across clusters. to address this limitation, we propose srank, a novel reranking approach emphasizing modeling inter-cluster relationships. specifically, we introduce a new metric called functional overlap to quantify the similarity between clusters based on their execution outputs. this allows for identifying the most representative cluster that exhibits maximal overlap with all other clusters. as inconsistencies often indicate incorrect functionality, the cluster interacting most comprehensively likely represents the optimal solution. by incorporating these inter-cluster relationships into the ranking pipeline, we can better identify the most promising solutions. through extensive evaluation, we demonstrate that modeling inter-cluster relationships and functional overlap provides significant and consistent improvements over prior state-of-the-art solution ranking methods @xcite @xcite on a wide range of state-of-the-art codellms, including codex, wizardcoder, starcoder, and codegen. for instance, on the humaneval benchmark, our method achieved a pass@1 score of 75.31% with wizard-coder34b, outperforming the coder-reviewer's score of 66.9%. similarly, on the mbpp-s benchmark, our method improved the pass@1 score for wizardcoder from 50.3% with coder-reviewer to 51.03% with our approach. similar improvements are applied for other codellms, including starcoder, codegen, and codex002. if we compare srankwith a simple random sampling method to get code solutions, we observe massive improvements across the models, with average improvements of 23.07% and 17.64% for humaneval and mbpp-s, respectively. our evaluation is more comprehensive because we include many sota codellms of varying sizes, whereas codet and coder-reviewer did not. this provides compelling evidence of our approach's robustness across a wide range of models. we also conducted an extensive analysis to demonstrate some of our advantages, such as our approach's remarkable robustness even with limited solutions and test cases. in summary, by moving from isolated clusters to interacting clusters with quantified functional overlap, our novel reranking strategy aims to address the limitations of prior ranking techniques for code generation. to summarize our contributions, they are as follows: ## experimental setup models we evaluate our method on several stateof-the-art codellms, including codex, wizard-coder, starcoder, and codegen. each model family has different model sizes (e.g., wizardcoder 15b and 34b) and different training methods (e.g., base model and instruction fine-tuned model). as a result, we chose a diverse set of models, ranging from small to large scale, and from base models to instruction fine-tuned models, to demonstrate the efficacy of our ranking method. in total, we demonstrate our approach on 6 models ranging from 6b to 34b parameters. ## experimental results to assess the effectiveness of our proposed method on a wide range of coding problem difficulties, we evaluate srank on apps using the codex002. results are shown in in addition, to validate our method on closed source and high capability models, we select an-thropic claude 3 opus (anthropic, 2024) as a representative llm in our experiment. please refer to appendix f for results. ## analysis assumption validation we provide a comprehensive analysis to validate our assumption that incorrect solutions are diverse and there is a low probability of functional agreement among incorrect solutions. formally, let s denote the set of solutions sampled from a certain codellm, s i be the i-th solution in s, c k be the k-th cluster by our clustering algorithm, c i be the cluster including the solution s i , and |c k | and |c k | * be the number of solutions and quantity of incorrect solutions in the k-th cluster, respectively. the function f (s i , s j ) is defined as the computation of the functional overlap between s i and s j , similar to eq. 1. we then compute the probability of incorrect solutions with varying levels of functional overlap. p(@xmath0, s j ) < h, s i and s j are incorrect) here, m is comprised of pairs of (s i , s j ) where @xmath1, s j ) < h, and l and h are the two hyperparameters. we consider two range values, (l 1 , h 1 ) and (l 2 , h 2 ) with the same length, where l 1 < l 2 and h 1 < h 2 . according to our assumption, we anticipate that the following inequality holds: the left term denotes the probability of lower functional agreement among incorrect solutions, while the right term signifies the corresponding probability of higher functional agreement among incorrect solutions. the observed relationship indicates that the probability of lower functional agreement surpasses that of higher functional agreement, substantiating our assumption. results in figure 3 show a general decline in probability with increasing values of l and h. particularly for the range (l, h) = (0, 0.1), the probability is significantly higher compared to those of other ranges, and at the next range, (l, h) = (0.1, 0.2), the probability experiences a notable decrease. moreover, when incorrect solutions exhibit a high functional overlap, exceeding 0.7, the probability is low at around 3%. these findings are consistent with our assumption. more results can be found in appendix a. ## conclusion we propose srank, a novel reranking strategy designed to extract optimal code generation solutions from codellms. srankfocuses on modeling intercluster relationships to identify clusters with the highest functional overlap with others. by prioritizing the cluster with the most comprehensive interaction, often indicating correct functionality, we can pinpoint the most promising solution. incorporating these inter-cluster relationships into the ranking pipeline enhances solution identification. we showcase the state-of-the-art performance of srank on pass@1 across various well-known codellms, surpassing other ranking methods like codet and coder-reviewer in extensive evaluations. our thorough analysis further highlights the method's effectiveness in realistic scenarios with a limited number of solutions and test cases. these findings are crucial as they address the challenges of code generation in real-world applications, illuminating strategies for selecting superior solutions within constrained coding environments.