TL;DR
This paper explores the effectiveness of Abstract Syntax Tree (AST) edit distance (TSED) for evaluating code similarity across various programming languages, comparing it to traditional metrics and a novel GPT-based approach. They propose an optimized TSED metric that shows strong correlation with execution matches and structural similarity, offering a more robust evaluation than purely semantic methods.
What Problem Does This Paper Address?
Evaluating the quality of generated code is crucial, but traditional methods like BLEU and Jaccard similarity rely on statistical characteristics and overlook the intricate grammatical structures and logical relationships inherent in programming languages. While recent advancements in NLP have introduced new evaluation metrics, there's a need to thoroughly assess their applicability and limitations, especially for code similarity tasks. This paper aims to bridge this gap by revisiting AST edit distance, comparing it with prompt-based GPT similarity, and traditional metrics, and proposing an improved, adaptable metric.
Methods
The core of this research revolves around two primary metrics:
- Tree Similarity of Edit Distance (TSED): This metric, originally designed for SQL, is adapted for general programming languages. It involves parsing code into an Abstract Syntax Tree (AST), calculating the tree edit distance using the APTED algorithm, and then normalizing the result. The APTED algorithm quantifies the minimum cost of edit operations (insert, delete, rename) to transform one AST into another. Normalization considers the maximum number of nodes between the two trees to provide a structural similarity score between 0 and 1.
- GPT Structure Similarity: This approach leverages large language models (LLMs) like GPT-4. By providing specific prompts, the model is asked to generate a similarity score (0-1) based on the grammatical structure of two code snippets. This method is treated as a "black box" as the internal calculation is not transparent.
The paper also compares these with traditional metrics:
- BLEU Score: A standard metric for evaluating text similarity, based on n-gram precision.
- Jaccard Similarity: Measures the overlap between sets of tokens.
- Execution Match: Evaluates whether generated code produces the same output as the ground truth when executed.
Datasets
The study utilizes several datasets for evaluation:
- MBXP: A function-level benchmark dataset covering 13 programming languages. However, ground truth solutions are available for only 7 languages, with C# excluded due to compilation issues.
- CoderEval: Used for comparing Python and Java code generation, featuring longer test samples.
- InterCode: Utilized for Bash-Shell scenarios, with the SPIDER dataset (a human-labeled dataset for text-to-SQL) identified as a baseline within it.
Key Insights and Ideas
- AST Edit Distance Captures Structure: TSED proves effective in capturing intricate code structures, showing a high correlation with established metrics and execution matches. This highlights its advantage over purely semantic metrics.
- GPT's Black Box Nature: While GPT-4 can generate similarity scores, its internal workings are opaque, making it difficult to understand how it arrives at a score. This lack of transparency, coupled with observed instability in its outputs, raises concerns for reliable evaluation.
- TSED's Adaptability: The research demonstrates TSED's successful application across multiple programming languages, especially those with functional parsers, suggesting its broad utility.
- Parameter Sensitivity of TSED: The performance of TSED can be influenced by the penalty weights assigned to tree operations (delete, insert, rename). The study found that for Java, an insert penalty weight of 0.8, with delete and rename at 1.0, yielded optimal results, though this might vary across languages.
- Efficiency Matters: TSED is computationally efficient, comparable to BLEU score and significantly faster than GPT-3.5, making it suitable for large-scale evaluations.
Key Results
- Strong Correlation: TSED and GPT similarity show consistently high Pearson correlations with semantic metrics like BLEU and Jaccard Similarity.
- Execution Match Performance: Both TSED and GPT similarity exhibit higher accuracy in matching execution outcomes compared to semantic metrics. GPT similarity achieved a slightly superior F1 score, while TSED demonstrated good accuracy.
- GPT Instability: Repeated scoring of the same code snippets by GPT-4 showed limited stability, with noticeable variations in Mean Squared Error and Mean Absolute Error.
- TSED vs. Semantic Metrics: In case studies, TSED often produced higher scores than BLEU when structural similarity was high but semantic similarity was low, demonstrating its strength in capturing structural nuances. For instance, in one case, TSED scored 0.8 while BLEU scored 0.359 for code with similar loops but different variable names.
Limitations and Future Work
- Dataset Generalizability: The generalizability of findings might be limited by the specific datasets and programming languages used.
- GPT Stability: The inherent instability of GPT-based similarity metrics poses a challenge for consistent and reliable code assessment.
- Parser Dependence: The effectiveness of TSED can be contingent on the quality of the employed parsers.
- Future Work: The authors suggest further research to address these limitations, particularly exploring optimizations for TSED and investigating methods to improve the stability and interpretability of GPT-based metrics. They also plan to address the observed disparity between high execution match and semantic similarity in certain scenarios.
Summary updated