ECCO : Can We Improve Model-Generated Code Efficiency Without Sacrificing Functional Correctness? (2024)

Abstract: Although large language models (LLMs) have been largely successful in generating functionally correct programs, conditioning models to produce efficient solutions while ensuring correctness remains a challenge. Further, unreliability in benchmarking code efficiency is a hurdle across varying hardware specifications for popular interpreted languages such as Python. In this paper, we present ECCO, a reproducible benchmark for evaluating program efficiency via two paradigms: natural language (NL) based code generation and history-based code editing. On ECCO, we adapt and thoroughly investigate the three most promising existing LLM-based approaches: in-context learning, iterative refinement with execution or NL feedback, and fine-tuning conditioned on execution and editing history. While most methods degrade functional correctness and moderately increase program efficiency, we find that adding execution information often helps maintain functional correctness, and NL feedback enhances more on efficiency. We release our benchmark to support future work on LLM-based generation of efficient code.

## introduction the ability to write efficient code is a cornerstone of software development @xcite . while large language models (llms) have shown remarkable progress in generating functionally correct code @xcite , the ability to generate solutions that are both correct and efficient remains elusive @xcite . current methods for optimizing program efficiency improve performance measured by execution time. however, this apparent success often comes at the cost of severely decreasing the functional correctness @xcite ). an exam-ple of this issue is illustrated in figure 1 : when optimizing the program on the left, models sometimes perform spurious optimizations that, although they reduce the runtime, make the program no longer functionally correct so that it fails all test cases. on the other hand, a correct optimization (bottom right) -that improves efficiency while maintaining functional correctness -is often harder to achieve for current lms. this spurious optimization is certainly undesirable in practice, and can even increase debugging time for software developers @xcite . to achieve the goal of real and robust program optimization, we ask: can lms improve program efficiency without sacrificing functional correctness? in this work, we curate an efficiency-oriented programming benchmark ecco, short for ensuring correctness in code optimizations, which enables program evaluation in three aspects: execution correctness, runtime efficiency, and memory efficiency. ecco supports two optimization paradigms: (i) history-based code editing: based on a previous version of the program, test if an lm can further optimize the code while maintaining its correctness, and (ii) nl-based code generation: test the efficiency of a program generated by an lm given a programming problem described in nl. we collect over 50k python solution pairs, spanning 1.3k competitive programming problems @xcite , with an average of 3.1 public and 17.3 private test cases to support reliable executionbased evaluations of correctness and efficiency. further, to perform reliable and reproducible executions, we introduce an evaluation setup using a cloud-hosted code execution engine, judge0 (došilović and mekterović, 2020), which produces stable execution output on correctness, runtime, and memory usage, thanks to its agnostic nature to local hardware specifications. it supports up to 66 programming languages (pls), allowing future work to extend to other languages. to explore various correctness-preserving program optimization methods, we evaluate three classes of methods on ecco-in-context learning, iterative refinement, and fine-tuning, across a suite of open-source language models pre-trained on code -which previous works have used to attempt to improve efficiency, while however overlooking their effects on correctness. we find that execution information and fine-tuning help maintain functional correctness, and nl-involved prompting often yields higher efficiency improvements. however, we broadly reconfirm findings that no existing methods can improve time/space efficiency without sacrificing functional correctness. we hope ecco can serve as a solid testbed for program optimization, and call for more efforts in advancing correctness-preserving program optimizations. ## related work benchmarks for code efficiency some works have proposed benchmarks for optimizing program assembly code @xcite @xcite . more recently, @xcite evaluate the efficiency of python solutions for leetcode coding interview problems @xcite . although most efforts on llm-based code generation focus on evaluating functional correctness (e.g., @xcite , some works evaluate code efficiency @xcite @xcite by classifying the time complexity of programs. however, these works are limited in their singlereference evaluation paradigm, assembly language support, or by the limited problem space on leet-code @xcite . our work supports reliable evaluation across arbitrary coding problems and the widely-used python language. evaluating program efficiency it is challenging to robustly evaluate program efficiency, due to varying hardware platforms and setups. previous works have evaluated the efficiency of code by executing code in a local software environment @xcite or using containerized environments on local hardware @xcite , but this can result in varying runtime and memory usage across hardware, thus causing irreproducible evaluations. an alternative approach is to use an architecture simulator @xcite which ensures the execution of each program is exactly simulated at the hardware level, but is limited to compiled languages such as c++. a hardware counter though reliable @xcite , cannot measure memory usage. for popular interpreted languages such as python and java, some use leetcode's execution engine @xcite , but with a restricted space of testable problems. in our work, we propose an evaluation setup using an accessible cloud computing instance that ensures consistent virtual hardware and reliable benchmarking. ## the ecco benchmark in this section, we first introduce our evaluation platform ( §3.1), then describe the construction process of our ecco benchmark ( §3.2), and lastly, introduce our two task formulations with corresponding evaluation metrics ( §3.3). ## efficiency-improving approaches we explore various top-performing code generation approaches to improve program efficiency, while maintaining functional correctness, including incontext learning ( §4.1), iterative refinement ( §4.2), and fine-tuning ( §4.3). ## additional analysis does instruction tuning help in-context learning? as instruct model versions are expected to be better at in-context learning than their base counterparts, we compare base and instruct model versions in the editing paradigm. in does multi-iteration refinement help? multiple refinement iterations may improve results by allowing more turns for models to refine. to verify this, we evaluate the iterative refinement method using 1-4 iterations. while self-refine and exec-refine improve program speedup over iterations (figure 6b ), all methods continuously degrade the pass@1 to various extents. exec-refine preserves correctness more effectively in further iterations as well. for memory usage (figure 6c ), exec-refine consistently reduces memory usage, yet other methods exhibit big fluctuations. in general, more iterations can speed up the program, yet further sacrifice correctness, thus has limited gains in terms of correctnesspreserving optimization. ## conclusion in this paper, we introduce the ecco benchmark that enables two paradigms for python program optimization, using judge0, a language and platform-agnostic execution framework. we find that execution information and fine-tuning help llms maintain code correctness, and prompting with natural language often yields higher efficiency gains. however, we broadly reconfirm findings that no existing method can improve efficiency without sacrificing functional correctness. we hope ecco can serve as a testbed for program optimization, and we call for more efforts in advancing correctness-preserving program optimizations.